Opened 10 years ago

Closed 6 years ago

#11814 closed defect (fixed)

Catch and fix the segmentation fault in dlx_solver

Reported by: jdemeyer Owned by: sage-combinat
Priority: critical Milestone: sage-6.8
Component: combinatorics Keywords:
Cc: slabbe Merged in:
Authors: Sébastien Labbé Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: dcdfd06 (Commits, GitHub, GitLab) Commit: dcdfd06c1e924a72a49cf0c13929930ddcb61e08
Dependencies: Stopgaps:

Status badges

Description (last modified by boothby)

On a 64-bit Gentoo Linux system running sage-4.7.2.alpha2:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search()
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0x31)[0x7f6c37015e02]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0x7f6c37015e34]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handler+0x20c)[0x7f6c37015a82]
/lib/libpthread.so.0(+0xf400)[0x7f6c3c26e400]
/usr/local/src/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/combinat/matrices/dancing_links.so(+0x738b)[0x7f6c1612f38b]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x4c32)[0x7f6c3c55d842]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f6c3c55f912]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x4ccb)[0x7f6c3c55d8db]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5a8a)[0x7f6c3c55e69a]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f6c3c55f912]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_FileExFlags+0xb0)[0x7f6c3c581d20]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_SimpleFileExFlags+0xdf)[0x7f6c3c58275f]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(Py_Main+0xb23)[0x7f6c3c58fa23]
/lib/libc.so.6(__libc_start_main+0xe6)[0x7f6c3b897ba6]
python[0x4006e9]

------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------

Note that this behaviour is actually documented in sage/combinat/tiling.py:

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

For sage-on-gentoo, there is an assertion failure:

sage:  x = dlx_solver(rows)
python2.7: sage/combinat/matrices/dancing_links_c.h:217: void dancing_links::setup_columns(): Assertion `nr_columns > 0' failed.
/usr/lib64/libcsage.so(print_backtrace+0x24)[0x7fea73a945f7]
/usr/lib64/libcsage.so(sigdie+0x1d)[0x7fea73a94687]
/usr/lib64/libcsage.so(sage_signal_handler+0x157)[0x7fea73a94822]
/lib64/libpthread.so.0(+0xfee0)[0x7fea79206ee0]
/lib64/libc.so.6(gsignal+0x35)[0x7fea78ea5ee5]
/lib64/libc.so.6(abort+0x186)[0x7fea78ea7896]
/lib64/libc.so.6(__assert_fail+0xf5)[0x7fea78e9e7a5]
/usr/lib64/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x855d)[0x7fea4e73255d]

Additionally, we can segfault with a different kind of trivial problem,

    sage: from sage.combinat.matrices.dancing_links import dlx_solver
    sage: d = dlx([[]])
    sage: d.search()
    *boom!*

And even adding rows can be a problem... this doesn't always go boom

    sage: d = dlx_solver([[0,1],[2]])
    sage: d.add_rows([[0,1],[1]])
    *boom!*

Actually... *why the hell* would we ever support the following:

    sage: d = dlx_solver(anything)
    sage: d.search()
    sage: d.add_rows(anything else)

Change History (43)

comment:1 Changed 10 years ago by leif

A bit more information on the platform, or did you try this on different systems?

On Ubuntu 10.04.3 x86_64 I get:

...
sage: sage: from sage.combinat.matrices.dancing_links import dlx_solver
==27537== Invalid read of size 4
==27537==    at 0x4EB5E83: PyObject_Free (obmalloc.c:931)
==27537==    by 0x4EDBE00: unicode_dealloc (unicodeobject.c:369)
==27537==    by 0x4E9C8E0: frame_dealloc (frameobject.c:420)
==27537==    by 0x4F1562E: PyEval_EvalCodeEx (ceval.c:2979)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==  Address 0x6156020 is 2,256 bytes inside a block of size 4,400 free'd
==27537==    at 0x4C27058: realloc (vg_replace_malloc.c:525)
==27537==    by 0x9F13E6A: xrealloc (xmalloc.c:74)
==27537==    by 0x9F1442E: add_history (history.c:302)
==27537==    by 0x9F1761F: read_history_range (histfile.c:270)
==27537==    by 0x9CE3089: read_history_file (readline.c:102)
==27537==    by 0x4F13E19: PyEval_EvalFrameEx (ceval.c:3706)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4E9DC2A: function_call (funcobject.c:524)
==27537== 
==27537== Invalid read of size 4
==27537==    at 0x4EB5E83: PyObject_Free (obmalloc.c:931)
==27537==    by 0x4E68C66: freechildren (node.c:135)
==27537==    by 0x4E68FAD: PyNode_Free (node.c:123)
==27537==    by 0x4F370C8: PyParser_ASTFromString (pythonrun.c:1439)
==27537==    by 0x4F37221: Py_CompileStringFlags (pythonrun.c:1382)
==27537==    by 0x4F0CE6B: builtin_compile (bltinmodule.c:546)
==27537==    by 0x4F13E19: PyEval_EvalFrameEx (ceval.c:3706)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4E9DB2E: function_call (funcobject.c:524)
==27537==    by 0x4E741A1: PyObject_Call (abstract.c:2492)
==27537==    by 0x4E868BC: instancemethod_call (classobject.c:2579)
==27537==    by 0x4E741A1: PyObject_Call (abstract.c:2492)
==27537==  Address 0xa73d020 is not stack'd, malloc'd or (recently) free'd
==27537== 
sage: sage: rows = []
sage: sage: x = dlx_solver(rows)
sage: sage: x.search()
==27537== Conditional jump or move depends on uninitialised value(s)
==27537==    at 0x2F2C3281: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:75)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Use of uninitialised value of size 8
==27537==    at 0x2F2C32AA: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Conditional jump or move depends on uninitialised value(s)
==27537==    at 0x2F2C32A8: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Conditional jump or move depends on uninitialised value(s)
==27537==    at 0x2F2C3291: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Invalid read of size 4
==27537==    at 0x2F2C328C: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==  Address 0x30 is not stack'd, malloc'd or (recently) free'd
==27537== 
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0x31)[0xbfa6817]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0xbfa6849]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handler+0x20e)[0xbfa6474]
/lib/libpthread.so.0(+0xf8f0)[0x52018f0]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/combinat/matrices/dancing_links.so(+0x828c)[0x2f2c328c]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x4af7)[0x4f13b47]
... (same backtrace)

comment:2 Changed 10 years ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 9 years ago by slabbe

  • Cc slabbe added

comment:4 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 8 years ago by boothby

Amusingly I found this in add_rows

        The following example would crash in Sage's debug version
        from :trac:`13864` prior to the fix from :trac:`13822`::

            sage: from sage.combinat.matrices.dancing_links import dlx_solver
            sage: x = dlx_solver([])          # indirect doctest
            sage: x.get_solution()
            []

comment:6 Changed 8 years ago by boothby

  • Description modified (diff)

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 follow-up: Changed 6 years ago by slabbe

  • Branch set to u/slabbe/11814
  • Commit set to 8ee8dd81d654d6d68baa335b15251a2427c3dc8e

I just pushed a branch (based on 6.6.rc2) where the segmentation fault is catch using sig_on and sig_off.

Do we want to also solve the segmentation fault itself in this ticket?


New commits:

8ee8dd8Trac #11814: Catch the segmentation fault in dancing links

comment:11 Changed 6 years ago by git

  • Commit changed from 8ee8dd81d654d6d68baa335b15251a2427c3dc8e to 25741dfc1c52709faa59042024248824247275f4

Branch pushed to git repo; I updated commit sha1. New commits:

25741dfTrac #11814: Merge with 6.8.rc1

comment:12 in reply to: ↑ 10 ; follow-up: Changed 6 years ago by jdemeyer

Replying to slabbe:

I just pushed a branch (based on 6.6.rc2) where the segmentation fault is catch using sig_on and sig_off.

Do we want to also solve the segmentation fault itself in this ticket?

First of all, I would absolutely never doctest segfaults unless you know that it's safe to do so.

I don't mind just adding the sig_on/sig_off in this ticket provided that you create a new ticket for the segmentation fault itself.

comment:13 Changed 6 years ago by jdemeyer

Also: add your author name please.

comment:14 Changed 6 years ago by git

  • Commit changed from 25741dfc1c52709faa59042024248824247275f4 to 35f074c4a0a48af5583582e25fe76d0483ca7778

Branch pushed to git repo; I updated commit sha1. New commits:

35f074cTrac #11814: Added not tested flag for segmentation fault

comment:15 Changed 6 years ago by slabbe

  • Authors set to Sébastien Labbé
  • Status changed from new to needs_review
  • Summary changed from Segmentation fault in dlx_solver to Catch the segmentation fault in dlx_solver

comment:16 in reply to: ↑ 12 Changed 6 years ago by slabbe

Replying to jdemeyer:

I don't mind just adding the sig_on/sig_off in this ticket provided that you create a new ticket for the segmentation fault itself.

I just created #18950 for the segmentation fault itself.

comment:17 Changed 6 years ago by slabbe

  • Status changed from needs_review to needs_work

comment:18 follow-up: Changed 6 years ago by jdemeyer

Why needs_work?

comment:19 Changed 6 years ago by git

  • Commit changed from 35f074c4a0a48af5583582e25fe76d0483ca7778 to 549575955408f4ca4c8c24341c6c8149d14e4a1d

Branch pushed to git repo; I updated commit sha1. New commits:

5495759Trac #11814: Fix segmentation Fault raised by an assert

comment:20 in reply to: ↑ 18 Changed 6 years ago by slabbe

Replying to jdemeyer:

Why needs_work?

Because I found the problem and was about to push the solution here. #18950 will not be necessary.

comment:21 Changed 6 years ago by slabbe

  • Status changed from needs_work to needs_review

comment:22 Changed 6 years ago by slabbe

I also removed the dumps method which was broken and useless:

sage: x = dlx_solver([])                                                
sage: x.dumps()                                          
Traceback (most ...
...              
AttributeError: 'list' object has no attribute 'dumps'   

I was about to remove make_dlxwrapper from the sage namespace, but decided it belongs to another ticket.

comment:23 Changed 6 years ago by slabbe

  • Summary changed from Catch the segmentation fault in dlx_solver to Catch and fix the segmentation fault in dlx_solver

comment:24 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-6.4 to sage-6.8
  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to needs_work

The initialization of self.rows is a pure Python-level initialization, so I recommend to move it to __init__ instead of __cinit__.

comment:25 Changed 6 years ago by jdemeyer

  • Branch changed from u/slabbe/11814 to u/jdemeyer/11814

comment:26 Changed 6 years ago by jdemeyer

  • Commit changed from 549575955408f4ca4c8c24341c6c8149d14e4a1d to 392b62c70d342679c41799e0b45857c537ad8a8e
  • Status changed from needs_work to needs_review

I took the opportunity to fix the initialization even more and really clean up the whole file.


New commits:

392b62cSimplify dancing links code

comment:27 Changed 6 years ago by slabbe

  • Branch changed from u/jdemeyer/11814 to u/slabbe/11814
  • Commit changed from 392b62c70d342679c41799e0b45857c537ad8a8e to 3a3dd8be8ff50d04bc84dc60401ea9af11871af6

Great! I was feeling those Py_INCREF were not necessary and old fashion. You were the good guy to clean/update that part. I removed the cimport Integer which was unused.

There is one doctest failing in combinat/tiling.py because of the __str__ -> __repr__ change. I did not fix the doctest because I wonder if showing a list of list is really what we want for the __repr__? Maybe a repr saying Dancing links of 34 rows would be better together with a method rows returning the rows?


New commits:

3a3dd8bRemoved cimport Integer from dancing links

comment:28 Changed 6 years ago by slabbe

Note: I started to fix the repr thing. Will push something soon.

comment:29 follow-up: Changed 6 years ago by jdemeyer

I would prefer to see the rows in __repr__, so maybe Dancing links of 2 rows [0,1,2], [0,2].

Note: the only reason I changed it is because it looked strange to me that the class had a __str__ method but not a __repr__.

comment:30 Changed 6 years ago by git

  • Commit changed from 3a3dd8be8ff50d04bc84dc60401ea9af11871af6 to 56c74ed227fb8def88644a7e2371bd33701d8f28

Branch pushed to git repo; I updated commit sha1. New commits:

56c74edBetter __repr__ for dancing links, added rows method

comment:31 in reply to: ↑ 29 Changed 6 years ago by slabbe

With the last commit we now have:

sage: from sage.games.quantumino import QuantuminoSolver
sage: q = QuantuminoSolver(0)                           
sage: T = q.tiling_solver()                             
sage: T.dlx_solver()                                    
Dancing links solver for 96 columns and 5484 rows

I think it is better like this instead of printing the whole list of rows.

comment:32 Changed 6 years ago by jdemeyer

There is a doctest failure in src/sage/games/quantumino.py related to the printing.

comment:33 Changed 6 years ago by git

  • Commit changed from 56c74ed227fb8def88644a7e2371bd33701d8f28 to e2b82a4b7b035d84955c3c15a41cd740fc050eaf

Branch pushed to git repo; I updated commit sha1. New commits:

e2b82a4Fix doctest in games/quantumino.py

comment:34 Changed 6 years ago by slabbe

Just to say that I agree with the changes made by Jeroen in this ticket.

comment:35 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:36 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

When building with SAGE_DEBUG=yes:

sage: from sage.combinat.matrices.dancing_links import dlx_solver ## line 163 ##
sage: x = dlx_solver([])          # indirect doctest ## line 164 ##
python: /mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/combinat/matrices/dancing_links_c.h:217: void dancing_links::setup_columns(): Assertion `nr_columns > 0' failed.
------------------------------------------------------------------------
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/ext/interrupt/interrupt.so(+0x3747)[0x7f012e49a747]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/ext/interrupt/interrupt.so(+0x3902)[0x7f012e49a902]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/ext/interrupt/interrupt.so(+0x3257)[0x7f012e49a257]
/lib64/libpthread.so.0(+0x10430)[0x7f013a8b8430]
/lib64/libc.so.6(gsignal+0x38)[0x7f0139e0d9c8]
/lib64/libc.so.6(abort+0x16a)[0x7f0139e0f65a]
/lib64/libc.so.6(+0x2d187)[0x7f0139e06187]
/lib64/libc.so.6(+0x2d232)[0x7f0139e06232]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(_ZN13dancing_links13setup_columnsEv+0x36)[0x7f00f9ec3fe8]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(_ZN13dancing_links8add_rowsESt6vectorIS0_IiSaIiEESaIS2_EE+0x153)[0x7f00f9ec4335]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x1301a)[0x7f00f9ebf01a]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x121c9)[0x7f00f9ebe1c9]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x161b6)[0x7f00f9ec21b6]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x16378)[0x7f00f9ec2378]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x1091e)[0x7f00f9ebc91e]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x106dd)[0x7f00f9ebc6dd]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(+0xdf3ed)[0x7f013aba33ed]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x160bb)[0x7f00f9ec20bb]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x13c13)[0x7f00f9ebfc13]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x13ac4)[0x7f00f9ebfac4]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(+0x15a60b)[0x7f013ac1e60b]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x7c85)[0x7f013ac19290]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x113f)[0x7f013ac1bd59]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x41)[0x7f013ac115e6]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(+0x15d369)[0x7f013ac21369]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x432d)[0x7f013ac15938]
/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x113f)[0x7f013ac1bd59]

comment:37 Changed 6 years ago by jdemeyer

Sébastien, I won't have time in the coming month to look at this. If other people want to fix and to review, go ahead...

comment:38 Changed 6 years ago by slabbe

No problem Jeroen!

So how can I reproduce the problem? Like this?

make distclean
export SAGE_DEBUG="yes"
make
sage -t src/sage/combinat/matrices/dancing_links.pyx

or is there an easier way? Can I just recompile some packages (python and cython and gcc?) packages with SAGE_DEBUG=yes? Does sage -f <package> considers the SAGE_DEBUG flag?

Last edited 6 years ago by slabbe (previous) (diff)

comment:39 Changed 6 years ago by vbraun

You need to compile Python and everything that links to it, the only sure way is starting with make distclean imho.

comment:40 Changed 6 years ago by git

  • Commit changed from e2b82a4b7b035d84955c3c15a41cd740fc050eaf to dcdfd06c1e924a72a49cf0c13929930ddcb61e08

Branch pushed to git repo; I updated commit sha1. New commits:

dcdfd06Trac #11814: Fix failing Assertion nr_columns > 0 in setup_columns()

comment:41 Changed 6 years ago by slabbe

  • Status changed from needs_work to needs_review

comment:42 Changed 6 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:43 Changed 6 years ago by vbraun

  • Branch changed from u/slabbe/11814 to dcdfd06c1e924a72a49cf0c13929930ddcb61e08
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.