Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#13882 closed defect (fixed)

Deal with a trivial case in dlx_solver

Reported by: SimonKing Owned by: sage-combinat
Priority: major Milestone: sage-5.6
Component: combinatorics Keywords: dlx_solver nr_columns
Cc: Merged in: sage-5.6.beta3
Authors: Simon King Reviewers: François Bissey
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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.

Attachments (1)

trac13882_trivial_dlx_solver.patch (1.4 KB) - added by SimonKing 7 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 7 years ago by SimonKing

Smaller example:

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

Changed 7 years ago by SimonKing

comment:2 Changed 7 years ago by SimonKing

  • Authors set to Simon King
  • Status changed from new to needs_review

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.

comment:3 Changed 7 years ago by fbissey

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.

comment:4 follow-up: Changed 7 years ago by fbissey

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

comment:5 in reply to: ↑ 4 Changed 7 years ago by SimonKing

Replying to fbissey:

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.

comment:6 Changed 7 years ago by fbissey

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.

comment:7 Changed 7 years ago by fbissey

  • Reviewers set to Francois Bissey
  • Status changed from needs_review to positive_review

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

comment:8 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.6.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:9 Changed 7 years ago by jdemeyer

  • Reviewers changed from Francois Bissey to François Bissey
Note: See TracTickets for help on using tickets.