Length of a finite word defined by an iterator is broken

[seblabbe]

---------- Forwarded message ----------  
From: Timo Jolivet
Date: 2010/3/20
Subject: bug WordMorphism ?


Un bug bizarre :

sage: s = WordMorphism('0->0,1->%s'%('1'*100))
sage: s(
KeyboardInterrupt
sage: s = WordMorphism('0->000,1->%s'%('1'*100))
sage: s('0')
word: 000
sage: s('1')
word: 1111111111111111111111111111111111111111...
sage: len(s('0'))
3
sage: len(s('1'))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
/slabbe_hacked_macbook/<ipython console> in <module>()
TypeError: an integer is required



C'est d'autant plus bizarre que le code suivant marche :

sage: len(Word('1'*100))
100

CC: @sagetrac-abmasse

Component: combinatorics

Author: Sébastien Labbé

Reviewer: Alexandre Blondin Massé

Merged: sage-4.4.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/8574

[seblabbe]

comment:1

I copy here my answer to Timo :

---------- Message transféré ----------
De : Sébastien Labbé
Date : 22 mars 2010 10:16
Objet : Re: bug WordMorphism ?
À : Timo Jolivet


En fait, la fonction __len__ teste que la valeur retournée est un
entier de python plus grand ou égal à zéro. Par exemple, ce n'est pas
approprié pour les mots infinis. Alors, c'est pourquoi on a créé la
fonction length qui ne fait pas ce test :

sage: w = Word('1')^oo
sage: len(w)
Traceback (most recent call last):
...
TypeError: an integer is required
sage: w.length()
+Infinity

> sage: s = WordMorphism('0->000,1->%s'%('1'*100))
> sage: s('0')
> word: 000
> sage: s('1')
> word: 1111111111111111111111111111111111111111...
> sage: len(s('0'))
> 3
> sage: len(s('1'))
> ---------------------------------------------------------------------------
> TypeError                                 Traceback (most recent call last)
> /slabbe_hacked_macbook/<ipython console> in <module>()
> TypeError: an integer is required

Dans ton cas, c'est plus bizarre, car le mot s('1') est fini ! En
fait, le problème c'est que pour les mots définis par itérateurs, on
retourne un entier sage plutôt qu'un entier python....chose qu'il
faudrait possiblement changer.

> C'est d'autant plus bizarre que le code suivant marche :
>
> sage: len(Word('1'*100))
> 100

En effet, pour les mots définis par un str, on délègue la question de
la longueur à python qui retourne un entier python:

sage: s = WordMorphism('0->1,1->%s'%('1'*100))
sage: type(s('1').length())
<type 'sage.rings.integer.Integer'>

sage: w = Word('1'*100)
sage: type(w.length())
<type 'int'>


En y réfléchissant, je crois qu'il y aurait une meilleure solution que
de retourner toujours un entier python pour les mots finis. Il
faudrait simplement remplacer la fonction __len__ par une fonction
_len_ qui effacerait le comportement de la fonction __len__. En Sage,
ce principe est utilisé pour d'autres fonctions comme _repr_  par
exemple.

Merci pour ce rapport de bug,

Sébastien

[seblabbe]

Attachment: trac_8574-length-sl.patch.gz

Depends on #8429.

[sagetrac-abmasse]

comment:4

Hello, Sébastien!

Starting reviewing your patch, I noticed another file prefixed with trac_8574. Does it mean that you're working on this patch and I should wait before reviewing it?

Thank you for the information.

[seblabbe]

comment:5

I was thinking to merge that patch into here. But finally I changed my mind and didn't change the prefix of the patch name in the sage-combinat tree.

Hence, only the patch attached here should be considered for the review.

[sagetrac-abmasse]

Attachment: trac_8574_review-abm.patch.gz

Review -- correct few typos only, apply on top of Sébastien's patch

[sagetrac-abmasse]

comment:6

I just uploaded a small review patch that correct two or three typos from Sébastien's patch.

I tested it on sage-4.3.5 and all tests passed. The bug reported by T. Jolivet is indeed fixed with a very reasonable solution. I also checked the documentation generated by Sphinx, which looked fine too.

Positive review.

[sagetrac-abmasse]

Reviewer: Alexandre Blondin Massé

[sagetrac-abmasse]

Author: Sébastien Labbé

[jhpalmieri]

Merged: sage-4.4.alpha1

[jhpalmieri]

comment:7

Merged into 4.4.alpha1:

• trac_8574-length-sl.patch
• trac_8574_review-abm.patch