Deal with a trivial case in dlx_solver

[simon-king-jena]

Using Sage's debug version from #13864, the following crashes:

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
...

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 nr_columns >= 0 rather than nr_columns > 0.

Component: combinatorics

Keywords: dlx_solver nr_columns

Author: Simon King

Reviewer: François Bissey

Merged: sage-5.6.beta3

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

[simon-king-jena]

comment:1

Smaller example:

sage: from sage.combinat.matrices.dancing_links import dancing_linksWrapper
sage: dancing_linksWrapper([])
<BOOM>

[simon-king-jena]

Attachment: trac13882_trivial_dlx_solver.patch.gz

[simon-king-jena]

comment:2

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.

My suggestion: If the input is empty, then return before using the uninitialized value.

[simon-king-jena]

Author: Simon King

[kiwifb]

comment:3

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.

[kiwifb]

comment:4

With your change the following in combinat/tiling.py will have to be changed

    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 !!!

[simon-king-jena]

comment:5

Replying to @kiwifb:

With your change the following in combinat/tiling.py will have to be changed

                sage: from sage.combinat.matrices.dancing_links import dlx_solver
                sage: rows = []
                sage: x = dlx_solver(rows)
                sage: x.search()        # not tested
                BOOM !!!

Why? It still goes "BOOM". Actually, the fix from here is responsible for the fact that in the debug version the line x = dlx_solver(rows) does not crash. But the segfault in x.search() will still occur.

[kiwifb]

comment:6

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.

[kiwifb]

Reviewer: Francois Bissey

[kiwifb]

comment:7

Pass my tests. Looks good to me. Positive review as is.

[jdemeyer]

Merged: sage-5.6.beta3

[jdemeyer]

Changed reviewer from Francois Bissey to François Bissey