Opened 5 years ago

Closed 5 years ago

#23846 closed defect (fixed)

Fix containing_block

Reported by: Simon King Owned by:
Priority: major Milestone: sage-8.1
Component: combinatorics Keywords: balanced parentheses, containing_block
Cc: Merged in:
Authors: Simon King Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 3c01d71 (Commits, GitHub, GitLab) Commit: 3c01d712a8e763bb1e922a515307d853d6deb22b
Dependencies: Stopgaps:

Status badges

Description (last modified by Simon King)

First of all, the documentation sage.repl.preparse.containing_block function is unclear. Second, it seems to return wrong results.

I suppose that containing_block(s, idx) is supposed to contain a,b such that s[a:b] is the smallest substring with matching parentheses containing idx.

Actually the role of idx is not stated in the documentation. From some tests, it seems that we will have a<idx. The following seems wrong to me:

  1. s[a:b] actually is not always balanced:
    sage: from sage.repl.preparse import containing_block
    sage: containing_block('((a))',1)
    (0, 4)
    sage: '((a))'[0:4]
    '((a)'
    sage: containing_block('([a)',1)
    (0, 4)
    sage: '([a)'[0:4]
    '([a)'
    sage: containing_block('(a])',1)
    (0, 4)
    sage: '(a])'[0:4]
    '(a])'
    
  1. Some corner cases:
    sage: containing_block('()',1)
      File "<string>", line unknown
    SyntaxError: Unbalanced or missing ()'s
    sage: containing_block('()',0)
      File "<string>", line unknown
    SyntaxError: Unbalanced or missing ()'s
    

Suggested fix:

  1. The specification should be:
    • s[a:b] is minimal balanced (in particular we have s[a] and opening and s[b-1] a closing bracket)
    • a<=idx<b (in particular, the char at position idx is part of s[a:b])
  2. The specification should be documented.

Change History (10)

comment:1 Changed 5 years ago by Simon King

Description: modified (diff)

comment:2 Changed 5 years ago by Simon King

By the way: Why is there no proper traceback when containing_block raises a SyntaxError?

comment:3 Changed 5 years ago by Simon King

Description: modified (diff)

comment:4 Changed 5 years ago by Simon King

Description: modified (diff)

comment:5 Changed 5 years ago by Simon King

Branch: u/SimonKing/fix_containing_block

comment:6 Changed 5 years ago by Simon King

Authors: Simon King
Commit: b282e6d408d73e0c2e488ed6ed4a6c59790e3dfe
Status: newneeds_review

New commits:

b282e6dFix containing_block

comment:7 Changed 5 years ago by git

Commit: b282e6d408d73e0c2e488ed6ed4a6c59790e3dfe3c01d712a8e763bb1e922a515307d853d6deb22b

Branch pushed to git repo; I updated commit sha1. New commits:

3c01d71Cope with differing behaviour of SyntaxError in doctests

comment:8 Changed 5 years ago by Simon King

Apparently a SyntaxError does result in a traceback in doctest, although it doesn't in an interactive session. The new commit deals with it...

comment:9 Changed 5 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

LGTM.

comment:10 Changed 5 years ago by Volker Braun

Branch: u/SimonKing/fix_containing_block3c01d712a8e763bb1e922a515307d853d6deb22b
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.