#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)
Change History (10)
comment:1 Changed 8 years ago by
Changed 8 years ago by
comment:2 Changed 8 years ago by
- 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 8 years ago by
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: ↓ 5 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 8 years ago by
- Merged in set to sage-5.6.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
comment:9 Changed 8 years ago by
- Reviewers changed from Francois Bissey to François Bissey
Smaller example: