Sage: Ticket #6519: [with patch, positive review] improve the words library code
https://trac.sagemath.org/ticket/6519
<p>
The current words library in Sage needs to be improved (mainly for speed, better code organization, etc.).
</p>
<p>
We essentially got a patch ready to do this. I'll post it soon.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/6519
Trac 1.1.6saliolaSun, 12 Jul 2009 16:02:57 GMT
https://trac.sagemath.org/ticket/6519#comment:1
https://trac.sagemath.org/ticket/6519#comment:1
<p>
You can find comparisons of the new code and the old code at the bottom of
the site <a class="ext-link" href="http://wiki.sagemath.org/WordDesign"><span class="icon"></span>http://wiki.sagemath.org/WordDesign</a>. The new code is much
faster.
</p>
TicketsaliolaSun, 12 Jul 2009 17:36:02 GMTsummary changed
https://trac.sagemath.org/ticket/6519#comment:2
https://trac.sagemath.org/ticket/6519#comment:2
<ul>
<li><strong>summary</strong>
changed from <em>improve the words library code</em> to <em>[with patch; needs review] improve the words library code</em>
</li>
</ul>
<p>
This patch includes code from Sébastien Labbé, Vincent Delecroix and
myself, so we should all get author credit. (I added all names to the Author
field).
</p>
<p>
The development took place on the sage-combinat patch server, and the attached patch
is just a folding together and re-organizing of all the relevant patches
from the server. It applies cleanly to sage-4.1 and passes all doctests.
</p>
<p>
<strong>Partial Review:</strong> I reviewed and documented Vincent's code, to which give a positive
review. I also reviewed Sébastien's code, which also gets a positive review.
</p>
<p>
Sébastien, can you look over the changes that I made that you haven't yet
reviewed? I guess these are just the changes that I made this past week?
(You can find these changes as four independent patches in the sage-combinat
patches server history.)
</p>
TicketrlmMon, 13 Jul 2009 19:18:21 GMTsummary changed
https://trac.sagemath.org/ticket/6519#comment:3
https://trac.sagemath.org/ticket/6519#comment:3
<ul>
<li><strong>summary</strong>
changed from <em>[with patch; needs review] improve the words library code</em> to <em>[with patch; needs work] improve the words library code</em>
</li>
</ul>
<p>
On top of a fresh sage-4.1 build (OS X), this patch fails to build:
</p>
<pre class="wiki">building 'sage.combinat.words.word_datatypes' extension
gcc -fno-strict-aliasing -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -Isage/combinat/words -I/Users/rlmill/sage-4.1.32bit/local//include -I/Users/rlmill/sage-4.1.32bit/local//include/csage -I/Users/rlmill/sage-4.1.32bit/devel//sage/sage/ext -I/Users/rlmill/sage-4.1.32bit/local/include/python2.6 -c sage/combinat/words/word_cpp_basic_string.cpp -o build/temp.macosx-10.3-i386-2.6/sage/combinat/words/word_cpp_basic_string.o -w
cc1plus: warning: command line option "-Wstrict-prototypes" is valid for C/ObjC but not for C++
sage/combinat/words/word_cpp_basic_string.cpp: In member function ‘size_t Word::find_factor_naive(Word*)’:
sage/combinat/words/word_cpp_basic_string.cpp:70: error: ‘memmem’ was not declared in this scope
error: command 'gcc' failed with exit status 1
sage: There was an error installing modified sage library code.
</pre>
TicketsaliolaMon, 13 Jul 2009 23:20:00 GMTsummary changed
https://trac.sagemath.org/ticket/6519#comment:4
https://trac.sagemath.org/ticket/6519#comment:4
<ul>
<li><strong>summary</strong>
changed from <em>[with patch; needs work] improve the words library code</em> to <em>[with patch; needs review] improve the words library code</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6519#comment:3" title="Comment 3">rlm</a>:
</p>
<blockquote class="citation">
<p>
On top of a fresh sage-4.1 build (OS X), this patch fails to build:
</p>
</blockquote>
<p>
Okay, I've factored the offending code out of this patch (once it is fixed,
we will create a new ticket for it), so there should no longer be any
problems. Can you test it again?
</p>
TicketrlmTue, 14 Jul 2009 16:02:18 GMT
https://trac.sagemath.org/ticket/6519#comment:5
https://trac.sagemath.org/ticket/6519#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6519#comment:4" title="Comment 4">saliola</a>:
</p>
<blockquote class="citation">
<p>
Can you test it again?
</p>
</blockquote>
<p>
The patch now applies, builds and passes long doctests in <code>sage/combinat</code>. I've also skimmed the patch (<code>historic.txt</code> was interesting), and it looked good. If you want, I can also run a valgrind session.
</p>
<p>
Doesn't the date in the deprecation comments need to be updated?
</p>
<pre class="wiki">+ ###########################################################################
+ ##### DEPRECATION WARNINGS (next 4 functions) #############################
+ ##### Added 23 February 2008 ##############################################
+ ###########################################################################
</pre>
TicketrlmWed, 15 Jul 2009 16:27:38 GMT
https://trac.sagemath.org/ticket/6519#comment:6
https://trac.sagemath.org/ticket/6519#comment:6
<p>
I ran valgrind on sage-4.1 + the patch here on the <code>sage/combinat/words</code> directory, and all looks good!
</p>
TicketsaliolaWed, 15 Jul 2009 16:32:58 GMT
https://trac.sagemath.org/ticket/6519#comment:7
https://trac.sagemath.org/ticket/6519#comment:7
<p>
Robert! Thank you very much for doing this. That's great.
</p>
TicketrlmThu, 16 Jul 2009 18:34:27 GMTsummary changed; reviewer set
https://trac.sagemath.org/ticket/6519#comment:8
https://trac.sagemath.org/ticket/6519#comment:8
<ul>
<li><strong>reviewer</strong>
set to <em>Robert Miller</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch; needs review] improve the words library code</em> to <em>[with patch; positive review] improve the words library code</em>
</li>
</ul>
TicketrlmThu, 16 Jul 2009 18:35:04 GMT
https://trac.sagemath.org/ticket/6519#comment:9
https://trac.sagemath.org/ticket/6519#comment:9
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/6526" title="defect: [with patch, positive review] remove naive suffix trees (closed: fixed)">#6526</a> should probably be merged right after this, to avoid later conflicts.
</p>
TicketslabbeFri, 17 Jul 2009 02:44:09 GMT
https://trac.sagemath.org/ticket/6519#comment:10
https://trac.sagemath.org/ticket/6519#comment:10
<p>
Dear Robert, I want to thank you for reviewing this huge patch we are working on since so long time. It was an heavy task that was following us for more than one semester. And all this time, I was affraid not to find a reviewer so that the code get old again with another ReST sphinfixication 2 or something like that because things are moving so fast with Sage. So, I feel more light now that this will get merged apparently really soon. Thank you for your contribution.
</p>
<p>
By the way, I was having a good excuse to be absent from this ticket review this week. I was organising and giving a course on Sage this week in Montreal. There was between 10 and 20 persons present in the class at all time. We migth have triple the number of Sage users in all Quebec province with this course!! See the link here : <a class="ext-link" href="http://wiki.sagemath.org/SébastienLabbé/JoursSageUQAM"><span class="icon"></span>http://wiki.sagemath.org/SébastienLabbé/JoursSageUQAM</a>
</p>
<p>
Dear Franco, even if Robert already gave a positive review, I will look the modifications/improvements you have done in the last week tommorow and I will give you feedback if I have any.
</p>
TicketmvnguFri, 17 Jul 2009 09:53:28 GMTsummary changed
https://trac.sagemath.org/ticket/6519#comment:11
https://trac.sagemath.org/ticket/6519#comment:11
<ul>
<li><strong>summary</strong>
changed from <em>[with patch; positive review] improve the words library code</em> to <em>[with patch, needs work] improve the words library code</em>
</li>
</ul>
<p>
I'm getting a doctest failure:
</p>
<pre class="wiki">sage -t -long devel/sage-exp/sage/structure/sage_object.pyx
**********************************************************************
File "/scratch/mvngu/release/sage-4.1.1/devel/sage-exp/sage/structure/sage_object.pyx", line 813:
sage: sage.structure.sage_object.unpickle_all(std)
Expected:
doctest:...: DeprecationWarning: RQDF is deprecated; use RealField(212) instead.
Successfully unpickled 572 objects.
Failed to unpickle 0 objects.
Got:
** failed: _class__sage_combinat_words_morphism_WordMorphism__.sobj
** failed: _class__sage_combinat_words_shuffle_product_ShuffleProduct_overlapping__.sobj
** failed: _class__sage_combinat_words_shuffle_product_ShuffleProduct_overlapping_r__.sobj
** failed: _class__sage_combinat_words_shuffle_product_ShuffleProduct_shifted__.sobj
** failed: _class__sage_combinat_words_shuffle_product_ShuffleProduct_w1w2__.sobj
** failed: _class__sage_combinat_words_suffix_trees_ImplicitSuffixTree__.sobj
** failed: _class__sage_combinat_words_suffix_trees_SuffixTrie__.sobj
** failed: _class__sage_combinat_words_word_AbstractWord__.sobj
** failed: _class__sage_combinat_words_word_Word_over_Alphabet__.sobj
** failed: _class__sage_combinat_words_word_Word_over_OrderedAlphabet__.sobj
doctest:1: DeprecationWarning: ChristoffelWord_Lower is deprecated, use LowerChristoffelWord instead
doctest:1172: DeprecationWarning: RQDF is deprecated; use RealField(212) instead.
Failed:
_class__sage_combinat_words_morphism_WordMorphism__.sobj
_class__sage_combinat_words_shuffle_product_ShuffleProduct_overlapping__.sobj
_class__sage_combinat_words_shuffle_product_ShuffleProduct_overlapping_r__.sobj
_class__sage_combinat_words_shuffle_product_ShuffleProduct_shifted__.sobj
_class__sage_combinat_words_shuffle_product_ShuffleProduct_w1w2__.sobj
_class__sage_combinat_words_suffix_trees_ImplicitSuffixTree__.sobj
_class__sage_combinat_words_suffix_trees_SuffixTrie__.sobj
_class__sage_combinat_words_word_AbstractWord__.sobj
_class__sage_combinat_words_word_Word_over_Alphabet__.sobj
_class__sage_combinat_words_word_Word_over_OrderedAlphabet__.sobj
Successfully unpickled 562 objects.
Failed to unpickle 10 objects.
**********************************************************************
1 items had failures:
1 of 7 in __main__.example_18
***Test Failed*** 1 failures.
For whitespace errors, see the file /scratch/mvngu/release/sage-4.1.1/tmp/.doctest_sage_object.py
[6.6 s]
</pre>
TicketslabbeFri, 17 Jul 2009 19:32:55 GMT
https://trac.sagemath.org/ticket/6519#comment:12
https://trac.sagemath.org/ticket/6519#comment:12
<p>
I am currently trying to understand the pickle problem... Using debug=True, I am getting more information (see below). The 10 problems look the same... I still don't know how to fix this...
</p>
<p>
Sébastien
</p>
<pre class="wiki">sage: std = os.environ['SAGE_DATA'] + '/extcode/pickle_jar/pickle_jar.tar.bz2'
sage: sage.structure.sage_object.unpickle_all(std, debug=True)
...
[same thing as above]
...
Successfully unpickled 562 objects.
Failed to unpickle 10 objects.
[(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbef502c>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbef5c84>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf006bc>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf005cc>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf00554>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf091bc>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf095f4>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf0966c>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf09b6c>),
(<type 'exceptions.TypeError'>,
TypeError('__new__() takes at least 3 arguments (1 given)',),
<traceback object at 0xbf09c84>)]
</pre>
TicketslabbeFri, 17 Jul 2009 20:47:02 GMT
https://trac.sagemath.org/ticket/6519#comment:13
https://trac.sagemath.org/ticket/6519#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6519#comment:2" title="Comment 2">saliola</a>:
</p>
<blockquote class="citation">
<p>
<strong>Partial Review:</strong> I reviewed and documented Vincent's code, to which give a positive
review. I also reviewed Sébastien's code, which also gets a positive review.
</p>
<p>
Sébastien, can you look over the changes that I made that you haven't yet
reviewed? I guess these are just the changes that I made this past week?
</p>
</blockquote>
<p>
I just looked at the changes that Franco made in the last week and I am giving a positive review to them. We now have to tackle the pickle problem described above.
</p>
TicketsaliolaFri, 17 Jul 2009 21:16:15 GMT
https://trac.sagemath.org/ticket/6519#comment:14
https://trac.sagemath.org/ticket/6519#comment:14
<p>
I have a working patch right now. I am going to run a few more tests, and the post it.
</p>
TicketsaliolaFri, 17 Jul 2009 21:49:10 GMT
https://trac.sagemath.org/ticket/6519#comment:15
https://trac.sagemath.org/ticket/6519#comment:15
<p>
The problem. The picklejar contains objects saved with older versions of
Sage, and since we changed a bunch of things, these older objects don't get
loaded correctly.
</p>
<p>
The solution. The old word objects use the <code>WordContent</code> backend, which
my original patch completely removed (the new implementation is much
better). So my fix was to restore the (<code>word_content.py</code> and
<code>utils.py</code>); this way, an old-style word can be unpickled, and during
the unpickling, it gets converted to a new-style word, and the user is
given a warning to re-save the word:
</p>
<pre class="wiki">sage: load /tmp/foo
...DeprecationWarning: Your word object is saved in an old file format since FiniteWord_over_OrderedAlphabet is deprecated and will be deleted in a future version of Sage (you can use FiniteWord_list instead). You can re-save your word by typing "word.save(filename)" to ensure that it will load in future versions of Sage.
word: abbabaab
</pre><p>
I also added a bunch of deprecation warnings to these files and to the
documentation for these files.
</p>
<p>
This is a temporary fix: since the <code>WordContent</code> code is not necessary
for any other part of Sage, it will be deleted in a few months. In the
meantime, if there is anyone with some saved word objects, then unpickling
will work.
</p>
TicketsaliolaFri, 17 Jul 2009 21:54:28 GMTattachment set
https://trac.sagemath.org/ticket/6519
https://trac.sagemath.org/ticket/6519
<ul>
<li><strong>attachment</strong>
set to <em>trac_6519-words_ng.patch</em>
</li>
</ul>
<p>
(now with unpickle support for words save with older versions of Sage)
</p>
TicketsaliolaFri, 17 Jul 2009 21:55:09 GMTattachment set
https://trac.sagemath.org/ticket/6519
https://trac.sagemath.org/ticket/6519
<ul>
<li><strong>attachment</strong>
set to <em>old_pickle_support.patch</em>
</li>
</ul>
<p>
DO NOT APPLY!
</p>
TicketsaliolaFri, 17 Jul 2009 22:02:14 GMT
https://trac.sagemath.org/ticket/6519#comment:16
https://trac.sagemath.org/ticket/6519#comment:16
<p>
To make reviewing my fix easier: I've attached the file
<code>old_pickle_support.patch</code>, which contains only the changes that I made
to address the pickle issue. This patch has already been folded into o
<code>trac_6519-words_ng.patch</code>, so do not apply it.
</p>
<p>
Besides restoring the files <code>word_content.py</code> and <code>utils.py</code> (and
adding warnings), I needed to touch <code>word.py</code>, so this is where the
reviewer needs to concentrate their attention.
</p>
TicketsaliolaFri, 17 Jul 2009 22:02:51 GMTsummary changed
https://trac.sagemath.org/ticket/6519#comment:17
https://trac.sagemath.org/ticket/6519#comment:17
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] improve the words library code</em> to <em>[with patch, needs review] improve the words library code</em>
</li>
</ul>
TicketslabbeSat, 18 Jul 2009 13:04:48 GMTsummary changed
https://trac.sagemath.org/ticket/6519#comment:18
https://trac.sagemath.org/ticket/6519#comment:18
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] improve the words library code</em> to <em>[with patch, positive review] improve the words library code</em>
</li>
</ul>
<p>
I applied the latest <code>trac_6519-words_ng.patch</code> on a clean version of sage-4.1. The following now works :
</p>
<pre class="wiki">slabbe@slabbe-laptop:~/sage-4.1/devel/sage-words_ng$ sage -t "devel/sage/sage/structure/sage_object.pyx"
sage -t "devel/sage/sage/structure/sage_object.pyx"
[4.9 s]
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 4.9 seconds
</pre><p>
I also run sage -t -long on all the sage tree and the only tests that failed are the following :
</p>
<pre class="wiki">slabbe@slabbe-laptop:~/sage-4.1/devel/sage-words_ng$ sage -t -long "devel/sage-words_ng/sage/interfaces/r.py"
sage -t -long "devel/sage-words_ng/sage/interfaces/r.py"
**********************************************************************
File "/home/slabbe/sage-4.1/devel/sage-words_ng/sage/interfaces/r.py", line 549:
sage: r.library('foobar')
Expected:
Traceback (most recent call last):
...
ImportError: there is no package called 'foobar'
Got nothing
**********************************************************************
File "/home/slabbe/sage-4.1/devel/sage-words_ng/sage/interfaces/r.py", line 835:
sage: r.completions('tes')
Expected:
['testPlatformEquivalence', 'testVirtual']
Got:
['testPlatformEquivalence', 'testPlatformEquivalence', 'testVirtual', 'testVirtual']
**********************************************************************
2 items had failures:
1 of 5 in __main__.example_17
1 of 3 in __main__.example_34
***Test Failed*** 2 failures.
For whitespace errors, see the file /home/slabbe/sage-4.1/tmp/.doctest_r.py
[4.5 s]
exit code: 1024
----------------------------------------------------------------------
The following tests failed:
sage -t -long "devel/sage-words_ng/sage/interfaces/r.py"
Total time for all tests: 4.5 seconds
slabbe@slabbe-laptop:~/sage-4.1/devel/sage-words_ng$
</pre><p>
but those were also broken on my clean version of sage-4.1. Hence, I am giving a positive review to the changes made by Franco to solve the pickle problem.
</p>
TicketmvnguSat, 18 Jul 2009 13:49:25 GMTreviewer changed
https://trac.sagemath.org/ticket/6519#comment:19
https://trac.sagemath.org/ticket/6519#comment:19
<ul>
<li><strong>reviewer</strong>
changed from <em>Robert Miller</em> to <em>Robert Miller, Sébastien Labbé</em>
</li>
</ul>
TicketmvnguSat, 18 Jul 2009 14:07:07 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/6519#comment:20
https://trac.sagemath.org/ticket/6519#comment:20
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.1.1.alpha0</em>
</li>
</ul>
<p>
Merged <code>trac_6519-words_ng.patch</code>.
</p>
Ticket