Opened 4 years ago

Closed 4 years ago

#23846 closed defect (fixed)

Fix containing_block

Reported by: SimonKing 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 SimonKing)

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 4 years ago by SimonKing

  • Description modified (diff)

comment:2 Changed 4 years ago by SimonKing

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

comment:3 Changed 4 years ago by SimonKing

  • Description modified (diff)

comment:4 Changed 4 years ago by SimonKing

  • Description modified (diff)

comment:5 Changed 4 years ago by SimonKing

  • Branch set to u/SimonKing/fix_containing_block

comment:6 Changed 4 years ago by SimonKing

  • Authors set to Simon King
  • Commit set to b282e6d408d73e0c2e488ed6ed4a6c59790e3dfe
  • Status changed from new to needs_review

New commits:

b282e6dFix containing_block

comment:7 Changed 4 years ago by git

  • Commit changed from b282e6d408d73e0c2e488ed6ed4a6c59790e3dfe to 3c01d712a8e763bb1e922a515307d853d6deb22b

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

3c01d71Cope with differing behaviour of SyntaxError in doctests

comment:8 Changed 4 years ago by SimonKing

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 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:10 Changed 4 years ago by vbraun

  • Branch changed from u/SimonKing/fix_containing_block to 3c01d712a8e763bb1e922a515307d853d6deb22b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.