Opened 10 years ago

Closed 7 years ago

#12804 closed defect (fixed)

infinite loop in find method of a finite word

Reported by: slabbe Owned by: sage-combinat
Priority: major Milestone: sage-6.6
Component: combinatorics Keywords:
Cc: tjolivet, slabbe, tmonteil, sstarosta Merged in:
Authors: Vincent Delecroix Reviewers: Sébastien Labbé
Report Upstream: N/A Work issues:
Branch: 946d884 (Commits, GitHub, GitLab) Commit: 946d884ecec663d2fd6ac58db845b8e9939b6674
Dependencies: Stopgaps:

Status badges

Description (last modified by vdelecroix)

sage: w = Word(iter("a"))
sage: w.find("a")
... hanging ...

Original report (the bug appears in the last two lines):

Salut,

Un participant à un TP sage (à l'EJCIM 2012) a décelé un bug :

sage: s = WordMorphism("a->a")
sage: w = Word("a")
sage: w2 = s(w)
sage: w.find("a")
0
sage: w2.find(Word("a"))
0

Pour l'instant tout va bien. Les deux problèmes sont :

sage: w2.find("a",end=1)
-1
sage: w2.find("a")
--> ça boucle

À la prochaine,
Timo

Attachments (1)

trac_12804.patch (2.9 KB) - added by aapitzsch 10 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 10 years ago by aapitzsch

  • Authors set to André Apitzsch
  • Status changed from new to needs_review

comment:2 Changed 10 years ago by tjolivet

  • Status changed from needs_review to needs_work

Hi,

I also thought about using the python string methods to fix this, but the Word class allows arbitrary alphabets so we cannot use the string method directly.

The problem arises for example with u = Word([-1,-2,-3]), where str(u) returns the string '-1,-2,-3':

sage: u = Word([-1,-2,-3])
sage: v = Word([-2])
sage: u.find(v)
1
sage: str(u).find(str(v))
3
Last edited 10 years ago by tjolivet (previous) (diff)

Changed 10 years ago by aapitzsch

comment:3 Changed 10 years ago by aapitzsch

  • Status changed from needs_work to needs_review

Now string method is only used if we search for a string instead of a word.

comment:4 Changed 10 years ago by mhansen

  • Reviewers set to Mike Hansen
  • Status changed from needs_review to needs_work

Doesn't

Word([-1,-2,-3]).find("-2")

still return the wrong thing? Wouldn't it be better to do something like list(u).index(v) ?

comment:5 Changed 10 years ago by aapitzsch

  • Status changed from needs_work to needs_info
sage: u = Word([-1,-2,-3])
sage: v = Word([-2]) 
sage: vv = Word("-2")
sage: v
word: -2
sage: vv
word: -2
sage: u.find(v) 
1
sage: u.find(vv)          
-1

Is this the behaviour we expect or should u.find(vv) return 1, too?

Notice

sage: v == vv
False
sage: type(v)
<class 'sage.combinat.words.word.FiniteWord_list'>
sage: type(vv)
<class 'sage.combinat.words.word.FiniteWord_str'>

comment:6 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:11 Changed 7 years ago by vdelecroix

  • Authors changed from André Apitzsch to Vincent Delecroix
  • Branch set to u/vdelecroix/12804
  • Cc slabbe tmonteil sstarosta added
  • Commit set to 1b0cb8eaa64b8e11eafbb834682e1fa16b1e0f25
  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-6.6
  • Reviewers Mike Hansen deleted
  • Status changed from needs_info to needs_review

Let us restart from scratch.


New commits:

1b0cb8eTrac 12804: fix find/rfind for words

comment:12 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:13 Changed 7 years ago by slabbe

  • Status changed from needs_review to needs_info

I like the way the fix is done. But by coercing the sub into the parent, we may obtain a Value Error. Should we catch the Value Error and return -1 in this case?

sage: w = Words('ab')('babaabaaab')
sage: w.find('abc')      # find is overwritten in WordDatatype_str
-1
sage: 
sage: w = Words('ab')(tuple('babaabaaab'))
sage: w.find('abc')
Traceback (most recent call last):
...
ValueError: c not in alphabet!

comment:14 Changed 7 years ago by git

  • Commit changed from 1b0cb8eaa64b8e11eafbb834682e1fa16b1e0f25 to 2c45e2a880f267cb8df6b17fb54ec51123246041

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

2c45e2aTrac 12804: return -1 when it fails as it is specified

comment:15 Changed 7 years ago by vdelecroix

  • Status changed from needs_info to needs_review

Right... done!

Vincent

comment:16 Changed 7 years ago by slabbe

  • Status changed from needs_review to needs_work

The commit 2c45e2a is fine, but the new doctests do not test the good thing since they were already fine before 2c45e2a. The Value Error comes when the parent of w has a specified alphabet and when sub is outside of the language. At least one doctest should test that case.

comment:17 Changed 7 years ago by slabbe

  • Branch changed from u/vdelecroix/12804 to public/12804
  • Commit changed from 2c45e2a880f267cb8df6b17fb54ec51123246041 to 946d884ecec663d2fd6ac58db845b8e9939b6674
  • Reviewers set to Sébastien Labbé
  • Status changed from needs_work to needs_review

I added the doctest that I wanted you to add. To me this is a positive review. I let you change the status for positive review if you agree with my commit.


New commits:

946d884Trac #12804: added a doctest during review

comment:18 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Thanks!

comment:19 Changed 7 years ago by vbraun

  • Branch changed from public/12804 to 946d884ecec663d2fd6ac58db845b8e9939b6674
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.