Sage: Ticket #13882: Deal with a trivial case in dlx_solver
https://trac.sagemath.org/ticket/13882
<p>
Using Sage's debug version from <a class="closed ticket" href="https://trac.sagemath.org/ticket/13864" title="task: Configure Python with pydebug when SAGE_DEBUG is set (closed: fixed)">#13864</a>, the following crashes:
</p>
<pre class="wiki">sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: x = dlx_solver([])
python: sage/combinat/matrices/dancing_links_c.h:217: void dancing_links::setup_columns(): Assertion `nr_columns > 0' failed.
Program received signal SIGABRT, Aborted.
0x00007ffff6d95d95 in raise () from /lib64/libc.so.6
(gdb) bt
#0 0x00007ffff6d95d95 in raise () from /lib64/libc.so.6
#1 0x00007ffff6d972ab in abort () from /lib64/libc.so.6
#2 0x00007ffff6d8e8fe in __assert_fail_base () from /lib64/libc.so.6
#3 0x00007ffff6d8e9a2 in __assert_fail () from /lib64/libc.so.6
#4 0x00007fffc3e38dc2 in dancing_links::setup_columns (this=0x7fffc2cc3e90) at sage/combinat/matrices/dancing_links_c.h:217
#5 0x00007fffc3e39101 in dancing_links::add_rows (this=0x7fffc2cc3e90, rows=...) at sage/combinat/matrices/dancing_links_c.h:268
#6 0x00007fffc3e3251d in __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_14add_rows (__pyx_v_self=0x7fffc2cc3e70, __pyx_v_rows=0x7ffff2375498)
at sage/combinat/matrices/dancing_links.cpp:2666
#7 0x00007fffc3e31c18 in __pyx_pw_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_15add_rows (__pyx_v_self=0x7fffc2cc3e70, __pyx_v_rows=0x7ffff2375498)
at sage/combinat/matrices/dancing_links.cpp:2464
#8 0x00007ffff7a21151 in PyCFunction_Call (func=0x7fffc2a0da38, arg=0x7fffefaad920, kw=0x0) at Objects/methodobject.c:101
#9 0x00007ffff79be33e in PyObject_Call (func=0x7fffc2a0da38, arg=0x7fffefaad920, kw=0x0) at Objects/abstract.c:2529
#10 0x00007fffc3e30130 in __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_2__cinit__ (__pyx_v_self=0x7fffc2cc3e70, __pyx_v_rows=0x7ffff2375498)
at sage/combinat/matrices/dancing_links.cpp:2010
#11 0x00007fffc3e2fe79 in __pyx_pw_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_3__cinit__ (__pyx_v_self=0x7fffc2cc3e70, __pyx_args=0x7fffefab74c0, __pyx_kwds=0x0)
at sage/combinat/matrices/dancing_links.cpp:1946
#12 0x00007fffc3e33b28 in __pyx_tp_new_4sage_8combinat_8matrices_13dancing_links_dancing_linksWrapper (t=0x7fffc4045000 <__pyx_type_4sage_8combinat_8matrices_13dancing_links_dancing_linksWrapper>,
a=0x7fffefab74c0, k=0x0) at sage/combinat/matrices/dancing_links.cpp:3037
#13 0x00007ffff7a4bfe3 in type_call (type=0x7fffc4045000 <__pyx_type_4sage_8combinat_8matrices_13dancing_links_dancing_linksWrapper>, args=0x7fffefab74c0, kwds=0x0) at Objects/typeobject.c:721
#14 0x00007ffff79be33e in PyObject_Call (func=0x7fffc4045000 <__pyx_type_4sage_8combinat_8matrices_13dancing_links_dancing_linksWrapper>, arg=0x7fffefab74c0, kw=0x0) at Objects/abstract.c:2529
#15 0x00007fffc3e32f12 in __pyx_pf_4sage_8combinat_8matrices_13dancing_links_dlx_solver (__pyx_self=0x0, __pyx_v_rows=0x7ffff2375498) at sage/combinat/matrices/dancing_links.cpp:2888
#16 0x00007fffc3e32e33 in __pyx_pw_4sage_8combinat_8matrices_13dancing_links_1dlx_solver (__pyx_self=0x0, __pyx_v_rows=0x7ffff2375498) at sage/combinat/matrices/dancing_links.cpp:2852
#17 0x00007ffff7ac6943 in call_function (pp_stack=0x7fffffffaab0, oparg=1) at Python/ceval.c:4009
#18 0x00007ffff7ac16ba in PyEval_EvalFrameEx (f=0x2f17a50, throwflag=0) at Python/ceval.c:2666
#19 0x00007ffff7ac40aa in PyEval_EvalCodeEx (co=0x7ffff6a9b460, globals=0x9b0080, locals=0x9b0080, args=0x0, argcount=0, kws=0x0, kwcount=0, defs=0x0, defcount=0, closure=0x0) at Python/ceval.c:3253
#20 0x00007ffff7ab9a88 in PyEval_EvalCode (co=0x7ffff6a9b460, globals=0x9b0080, locals=0x9b0080) at Python/ceval.c:667
#21 0x00007ffff7ac9693 in exec_statement (f=0x297f8c0, prog=0x7ffff6a9b460, globals=0x9b0080, locals=0x9b0080) at Python/ceval.c:4718
#22 0x00007ffff7abde26 in PyEval_EvalFrameEx (f=0x297f8c0, throwflag=0) at Python/ceval.c:1880
#23 0x00007ffff7ac40aa in PyEval_EvalCodeEx (co=0x7ffff280c720, globals=0x909bf0, locals=0x0, args=0x297f150, argcount=2, kws=0x297f160, kwcount=0, defs=0x0, defcount=0, closure=0x0)
at Python/ceval.c:3253
#24 0x00007ffff7ac71b5 in fast_function (func=0x7ffff235b450, pp_stack=0x7fffffffb430, n=2, na=2, nk=0) at Python/ceval.c:4117
#25 0x00007ffff7ac6d76 in call_function (pp_stack=0x7fffffffb430, oparg=1) at Python/ceval.c:4042
#26 0x00007ffff7ac16ba in PyEval_EvalFrameEx (f=0x297efa0, throwflag=0) at Python/ceval.c:2666
...
</pre><p>
My guess is that one can check whether the input is empty, dealing with that special case separately. Alternatively, if empty columns are acceptable, the assertion should be <code>nr_columns >= 0</code> rather than <code>nr_columns > 0</code>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13882
Trac 1.1.6SimonKingSat, 29 Dec 2012 21:24:47 GMT
https://trac.sagemath.org/ticket/13882#comment:1
https://trac.sagemath.org/ticket/13882#comment:1
<p>
Smaller example:
</p>
<pre class="wiki">sage: from sage.combinat.matrices.dancing_links import dancing_linksWrapper
sage: dancing_linksWrapper([])
<BOOM>
</pre>
TicketSimonKingSat, 29 Dec 2012 22:01:46 GMTattachment set
https://trac.sagemath.org/ticket/13882
https://trac.sagemath.org/ticket/13882
<ul>
<li><strong>attachment</strong>
set to <em>trac13882_trivial_dlx_solver.patch</em>
</li>
</ul>
TicketSimonKingSat, 29 Dec 2012 22:03:59 GMTstatus changed; author set
https://trac.sagemath.org/ticket/13882#comment:2
https://trac.sagemath.org/ticket/13882#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
The problem occurs in the add_rows method, if no rows are given: we would then have an uninitialised vector_vector_int that is used in some c-level function - and this is asking for trouble.
</p>
<p>
My suggestion: If the input is empty, then return before using the uninitialized value.
</p>
TicketfbisseySat, 29 Dec 2012 23:58:02 GMT
https://trac.sagemath.org/ticket/13882#comment:3
https://trac.sagemath.org/ticket/13882#comment:3
<p>
Nice we had that crash previously in sage-on-gentoo good to have a fix. I remember that in the original tiling.py the test would fail in the command after the call to the solver and for that reason that command wasn't tested. So I think that particular test should also be re-enabled in tiling.py.
</p>
TicketfbisseySun, 30 Dec 2012 10:30:04 GMT
https://trac.sagemath.org/ticket/13882#comment:4
https://trac.sagemath.org/ticket/13882#comment:4
<p>
With your change the following in combinat/tiling.py will have to be changed
</p>
<pre class="wiki"> def is_suitable(self):
r"""
Return whether the volume of the box is equal to sum of the volume
of the polyominoes and the number of rows sent to the DLX solver is
larger than zero.
If these conditions are not verified, then the problem is not suitable
in the sense that there are no solution.
.. NOTE::
The DLX solver throws a Segmentation Fault when the
number of rows is zero::
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search() # not tested
BOOM !!!
</pre>
TicketSimonKingSun, 30 Dec 2012 12:16:37 GMT
https://trac.sagemath.org/ticket/13882#comment:5
https://trac.sagemath.org/ticket/13882#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13882#comment:4" title="Comment 4">fbissey</a>:
</p>
<blockquote class="citation">
<p>
With your change the following in combinat/tiling.py will have to be changed
</p>
<pre class="wiki"> sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search() # not tested
BOOM !!!
</pre></blockquote>
<p>
Why? It still goes "BOOM". Actually, the fix from here is responsible for the fact that in the debug version the line <code>x = dlx_solver(rows)</code> does not crash. But the segfault in <code>x.search()</code> will still occur.
</p>
TicketfbisseySun, 30 Dec 2012 20:06:25 GMT
https://trac.sagemath.org/ticket/13882#comment:6
https://trac.sagemath.org/ticket/13882#comment:6
<p>
Apologies! When I saw your patch I became convinced it would do something for this. To the point of obsession only once, I posted (and gone to bed) did it occur to me that it wouldn't. I'll do one or two extra tests and give this ticket a positive review later today.
</p>
TicketfbisseySun, 30 Dec 2012 22:05:38 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/13882#comment:7
https://trac.sagemath.org/ticket/13882#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Francois Bissey</em>
</li>
</ul>
<p>
Pass my tests. Looks good to me. Positive review as is.
</p>
TicketjdemeyerMon, 07 Jan 2013 20:58:01 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/13882#comment:8
https://trac.sagemath.org/ticket/13882#comment:8
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.6.beta3</em>
</li>
</ul>
TicketjdemeyerMon, 21 Jan 2013 09:36:31 GMTreviewer changed
https://trac.sagemath.org/ticket/13882#comment:9
https://trac.sagemath.org/ticket/13882#comment:9
<ul>
<li><strong>reviewer</strong>
changed from <em>Francois Bissey</em> to <em>François Bissey</em>
</li>
</ul>
Ticket