Opened 7 years ago

Closed 7 years ago

#14951 closed defect (fixed)

tokenize() function in logic/ infinite loop

Reported by: pmscurek Owned by: Paul Scurek
Priority: major Milestone: sage-5.12
Component: misc Keywords: logic, propcalc, logicparser
Cc: Merged in: sage-5.12.beta2
Authors: Paul Scurek Reviewers: William Stein
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by pmscurek)

The tokenize() function in logic/ is called when a new formula of propositional calculus is created using propcalc.formula(<formula_expression>). The tokenize() function enters an infinite loop if the characters '<', '>', or '-', are used in <formula_expression> incorrectly (i.e. not as a part of one of the operators '<->' or '->'). The following code would cause an infinite loop because of the '-':

sage: import sage.logic.propcalc as propcalc

sage: f = propcalc.formula("a-b")

The BooleanFormula? class located in logic/ also needs a method that returns the full syntax parse tree of a boolean formula, so that each formula has a unique parse tree. The BooleanFormula? tree() method does not serve this purpose.

Attachments (1)

trac_14951_tokenize_tree_fix.patch (41.3 KB) - added by pmscurek 7 years ago.
fixes issues raised in ticket and issues raised by revewers

Download all attachments as: .zip

Change History (11)

comment:1 Changed 7 years ago by pmscurek

  • Description modified (diff)

comment:2 Changed 7 years ago by was

It is OK that the docstrings are not formatted as in the reference manual, for *consistency* with the rest of this file. We'll apply Mike Hansen's automatic old docstring --> new docstring conversion tool to the whole logic/ module later.

[ ] Rewrite polish_notation to use


[ ] Move this comment (below) so it aligns correctly, and there is a space after #:

    tree = tree_parse(toks, polish = True)
        #special case where the formula s is a single variable
    if type(tree) is StringType and len([tree]) == 1:

[ ] This looks suspicious since it is always tautologically true -- see if you can figure out what's up with this craziness:

    len([tree]) == 1

[ ] The Python way to do this

type(tree) is StringType

is to do this:

isinstance(tree, StringType)

[ ] Clean up this comment:

 #check to see if '-', '<' or '>' are used incorretly 


 # check to see if '-', '<' or '>' are used incorrectly 

[ ] Typo: When true, caues the function to produce the full (missing letter in "caues")

[ ] Mention the default values in docstrings.

[ ] In python replace if polish == False: by the more idomatic if not polish

comment:3 Changed 7 years ago by was

  • Reviewers set to William Stein
  • Status changed from new to needs_review

comment:4 Changed 7 years ago by was

  • Status changed from needs_review to needs_work

Changed 7 years ago by pmscurek

fixes issues raised in ticket and issues raised by revewers

comment:5 Changed 7 years ago by pmscurek

  • Status changed from needs_work to needs_review

The attachment trac_14951_tokenize_tree_fix.patch is large because it includes some changes to indentation, and hence I configured my .hgrc file to have Mercurial recognize whitespace. Here are the files and functions that are relevant to the ticket:

in -- init(), polish_notation(), full_tree()

in -- parse(), polish_parse(), tokenize(), tree_parse(), parse_ltor()

comment:6 Changed 7 years ago by was

Almost there:

  • typo "a boolean formlua".
  • typo "incorretly"

Positive review once you post another little patch to fix those two typos.

And yes, release manager, the docstrings are all scary -- there will be another ticket that uniformly modernizes the docstring formatting.

comment:7 Changed 7 years ago by pmscurek

I am currently working on a patch to update all of the docstrings in the logic module. The typos "a boolean formlua" and "incorretly" will be addressed in that patch.

comment:8 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 Changed 7 years ago by was

  • Status changed from needs_review to positive_review

Positive review since the typos are fixed as part of #15013.

comment:10 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.12.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.