Opened 10 years ago

Closed 10 years ago

#10797 closed enhancement (fixed)

update PolyBoRi to newest upstream release 0.7.0

Reported by: malb Owned by: AlexanderDreyer
Priority: blocker Milestone: sage-4.7
Component: packages: standard Keywords: polybori spkg
Cc: AlexanderDreyer, PolyBoRi, fbissey, burcin Merged in: sage-4.7.alpha2
Authors: Martin Albrecht, Alexander Dreyer Reviewers: Martin Albrecht, Burcin Erocal
Report Upstream: Fixed upstream, in a later stable release. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

A new version of PolyBoRi is available.

Changelog

  • Polynomials, monomials, variables, and BooleSets now own a reference to a fully-functionally BoolePolyRing (including ordering)
  • Orderings can work independently from ring
  • Simplified interface: remove *Assign() variants from diagrams
  • Added polybori.nf.simple_nf
  • Simplification of declare_ring in ipbori
  • Rename BoolePolynomials::reducibleBy -> BoolePolynomials::firstReducibleBy
  • Unittests for libpolybori are available, covering 98% of libpolybori
  • Added experimental PolyGUI

Summary

Attachments (2)

polybori-0.7.0.p1.patch (21.4 KB) - added by malb 10 years ago.
polybori-SPKG.txt.diff (1.1 KB) - added by jdemeyer 10 years ago.
Diff for SPKG.txt, needs review

Download all attachments as: .zip

Change History (53)

comment:1 Changed 10 years ago by malb

  • Cc AlexanderDreyer PolyBoRi added
  • Status changed from new to needs_work

I've cut a first SPKG:

http://sage.math.washington.edu/home/malb/spkgs/polybori-0.7.0.spkg

It compiles on my 64-bit Debian/GNU Linux, but the Sage interface doesn't play ball yet:

sage/rings/polynomial/pbori.cpp:3182: error: ‘CDDInterface’ is not a template
sage/rings/polynomial/pbori.cpp:3182: error: ‘dd_base’ is not a member of ‘polybori::CTypes’
sage/rings/polynomial/pbori.cpp:3182: error: ‘dd_base’ is not a member of ‘polybori::CTypes’
sage/rings/polynomial/pbori.cpp:3187: error: ‘CDDInterface’ is not a template
sage/rings/polynomial/pbori.cpp:3187: error: ‘dd_base’ is not a member of ‘polybori::CTypes’

It seems the type of CDDInterface changed. Alexander, can you comment?

comment:2 Changed 10 years ago by malb

With the attached patch Sage compiles with the SPKG linked to above. However, I do get segmentation faults:

sage: B.<a,b,c> = BooleanPolynomialRing()
sage: B.random_element()
terminate called after throwing an instance of 'std::runtime_error'
  what():  Operands come from different manager.
/home/malb/Sage/sage-current/local/bin/sage-sage: line 300: 23133 Aborted                 sage-ipython "$@" -i

comment:3 Changed 10 years ago by AlexanderDreyer

Hi Martin, I was out of office. That's not a segfault, that an uncaught C++ exception. But it should not occur there. I'll check it out. Alexander

comment:4 Changed 10 years ago by malb

Sorry for the mixup. But I think there are a few SEGFAULTs in there as well too:

sage: B.<a,b,c> = BooleanPolynomialRing()
sage: M = a.lm().parent()
sage: M.gen(0)
Program received signal SIGSEGV, Segmentation fault.
Cudd_ReadZero (dd=0x0) at Cudd/cudd/cuddAPI.c:1034
1034    Cudd/cudd/cuddAPI.c: No such file or directory.
        in Cudd/cudd/cuddAPI.c
(gdb) bt
#0  Cudd_ReadZero (dd=0x0) at Cudd/cudd/cuddAPI.c:1034
#1  0x00007fffd5336c42 in isZero (this=0x4242628, os=...) at polybori/include/CCuddDDFacade.h:243
#2  isZero (this=0x4242628, os=...) at polybori/include/BoolePolynomial.h:290
#3  polybori::BoolePolynomial::print (this=0x4242628, os=...) at polybori/src/BoolePolynomial.cc:497
#4  0x00007fffd560bfb0 in _to_PyString<polybori::BooleMonomial> (x=<value optimized out>) at /home/malb/Sage/sage-current/local//include/csage/ccobject.h:102
#5  0x00007fffd55a8b3d in __pyx_pf_4sage_5rings_10polynomial_5pbori_15BooleanMonomial__repr_ (__pyx_v_self=<value optimized out>, unused=0x7fffffffb4b0) at sage/rings/polynomial/pbori.cpp:15503
#6  0x00007ffff7a6be13 in PyObject_Call (func=0x7ffff5382a70, arg=0x7fffffffb4b0, kw=0x7ffff20ed130) at Objects/abstract.c:2492
#7  0x00007ffff0d65c2c in __pyx_pf_4sage_9structure_11sage_object_10SageObject___repr__ (__pyx_v_self=0x4242600) at sage/structure/sage_object.c:1356
#8  0x00007ffff7ab0c95 in PyObject_Repr (v=0x4242600) at Objects/object.c:376
#9  0x00007ffff7b0d850 in PyEval_EvalFrameEx (f=0x4235130, throwflag=<value optimized out>) at Python/ceval.c:1091
#10 0x00007ffff7b10932 in fast_function (f=0x4234f60, throwflag=<value optimized out>) at Python/ceval.c:3792
#11 call_function (f=0x4234f60, throwflag=<value optimized out>) at Python/ceval.c:3727
#12 PyEval_EvalFrameEx (f=0x4234f60, throwflag=<value optimized out>) at Python/ceval.c:2389
#13 0x00007ffff7b11d1d in PyEval_EvalCodeEx (co=0x4148738, globals=<value optimized out>, locals=<value optimized out>, args=0x4150d10, argcount=<value optimized out>, kws=0x2, kwcount=0, defs=0x0, 
    defcount=0, closure=0x0) at Python/ceval.c:2968
#14 0x00007ffff7a981db in function_call (func=0x4148aa0, arg=0x4150cf8, kw=0x41816b0) at Objects/funcobject.c:524
#15 0x00007ffff7a6be13 in PyObject_Call (func=0x4148aa0, arg=0x7fffffffb4b0, kw=0x7ffff20ed130) at Objects/abstract.c:2492
#16 0x00007ffff7b0e973 in ext_do_call (f=0x4185d20, throwflag=<value optimized out>) at Python/ceval.c:4019
#17 PyEval_EvalFrameEx (f=0x4185d20, throwflag=<value optimized out>) at Python/ceval.c:2429
#18 0x00007ffff7b11d1d in PyEval_EvalCodeEx (co=0x7ffff2c67f30, globals=<value optimized out>, locals=<value optimized out>, args=0x4151b18, argcount=<value optimized out>, kws=0x1, kwcount=0, defs=0x0, 
    defcount=0, closure=0x0) at Python/ceval.c:2968
#19 0x00007ffff7a980df in function_call (func=0x7ffff2c6a230, arg=0x4151b00, kw=0x0) at Objects/funcobject.c:524
#20 0x00007ffff7a6be13 in PyObject_Call (func=0x7ffff2c6a230, arg=0x7fffffffb4b0, kw=0x7ffff20ed130) at Objects/abstract.c:2492
#21 0x00007ffff7a7d19f in instancemethod_call (func=0x7ffff2c6a230, arg=0x4151b00, kw=0x0) at Objects/classobject.c:2579
#22 0x00007ffff7a6be13 in PyObject_Call (func=0x412faa0, arg=0x7fffffffb4b0, kw=0x7ffff20ed130) at Objects/abstract.c:2492
#23 0x00007ffff7a7c366 in instance_call (func=<value optimized out>, arg=0x7ffff0935290, kw=0x0) at Objects/classobject.c:2126
#24 0x00007ffff7a6be13 in PyObject_Call (func=0x7ffff29e7ab8, arg=0x7fffffffb4b0, kw=0x7ffff20ed130) at Objects/abstract.c:2492
#25 0x00007ffff7b0f77d in do_call (f=0x42349b0, throwflag=<value optimized out>) at Python/ceval.c:3924
#26 call_function (f=0x42349b0, throwflag=<value optimized out>) at Python/ceval.c:3729
#27 PyEval_EvalFrameEx (f=0x42349b0, throwflag=<value optimized out>) at Python/ceval.c:2389
#28 0x00007ffff7b10932 in fast_function (f=0x6df240, throwflag=<value optimized out>) at Python/ceval.c:3792
#29 call_function (f=0x6df240, throwflag=<value optimized out>) at Python/ceval.c:3727
#30 PyEval_EvalFrameEx (f=0x6df240, throwflag=<value optimized out>) at Python/ceval.c:2389
#31 0x00007ffff7b11d1d in PyEval_EvalCodeEx (co=0x7ffff2c4f198, globals=<value optimized out>, locals=<value optimized out>, args=0x414f0f8, argcount=<value optimized out>, kws=0x2, kwcount=0, 
    defs=0x7ffff2c587a8, defcount=1, closure=0x0) at Python/ceval.c:2968

comment:5 Changed 10 years ago by AlexanderDreyer

But examples show, that the actual ring is lost between the calls. Maybe some of the old work arounds (I see some calls of ._ring.activate() in the code) do something wrong here.

comment:6 Changed 10 years ago by malb

Shall I just remove all calls to activate()? I can give that a try.

comment:7 Changed 10 years ago by AlexanderDreyer

I'm no sure whether it cures it alone. It should not pick up null pointers anyway. I think I have to go deeper into the interface code.

comment:8 Changed 10 years ago by fbissey

  • Cc fbissey added

comment:9 Changed 10 years ago by AlexanderDreyer

There's a "hack" in PBMonom_construct_dd, which does not work any more. I'll have a deeper look into it.

comment:10 Changed 10 years ago by AlexanderDreyer

I fixed all segfaults and failed tests (even from out internal upstream-testsuite). Two tests fill fail, because there's something brocken upstream. I'll fix that in the (hopefully) final release candidate today.

comment:11 Changed 10 years ago by AlexanderDreyer

  • Authors changed from Martin Albrecht to Martin Albrecht,AlexanderDreyer
  • Cc Burcin added
  • Description modified (diff)
  • Status changed from needs_work to needs_review

Here's the next spkg: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.spkg

It contains the sources of the most recent release candidate of PolyBoRi 0.7, which will probably be the release version.

comment:12 Changed 10 years ago by AlexanderDreyer

  • Description modified (diff)

I refreshed to patch.

comment:13 Changed 10 years ago by AlexanderDreyer

  • Description modified (diff)
  • Owner changed from tbd to AlexanderDreyer

comment:14 Changed 10 years ago by AlexanderDreyer

  • Description modified (diff)

Just renamed and rebundled spkg http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p0.spkg (spkg still contains a tiny patch, therefore, I think, the .p0 extension is necessary.)

comment:15 Changed 10 years ago by malb

  • Description modified (diff)

comment:16 Changed 10 years ago by malb

The attached patch:

  • is rebased to 4.6.2.rc1
  • adds a doctest for cheap_reductions()
  • folds all previous patches into one

Note that I set Alexander as USER in this patch since he wrote most of the patch. Alexander, if you object to this for some reason let me know.

comment:17 Changed 10 years ago by malb

I'll do a build/ptestlong on geom.math and then I think we have a positive review.

comment:18 Changed 10 years ago by malb

  • Reviewers set to Martin Albrecht

comment:19 Changed 10 years ago by malb

  • Status changed from needs_review to positive_review

builds & doctests pass on a fresh 4.6.2.rc1.

comment:20 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.6.2 to sage-4.7

comment:21 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This ticket seems to cause an innocent doctest failure on sage.math.washington.edu:

sage -t  -force_lib devel/sage/sage/rings/number_field/number_field.py
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha2/devel/sage-main/sage/rings/number_field/number_field.py", line 2988:
    sage: K.selmer_group([K.ideal(2, -a+1), K.ideal(3, a+1), K.ideal(a)], 3)
Expected:
    [2, a + 1, a]
Got:
    [2, a + 1, -a]
**********************************************************************

comment:22 follow-up: Changed 10 years ago by AlexanderDreyer

Are you sure, this is caused by PolyBoRi??

In fact, the doctest for selmer_group explicitely says, that [2, a + 1, -a] is the expected result for 64 bit systems.

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

Replying to AlexanderDreyer:

Are you sure, this is caused by PolyBoRi??

No, it is just the most likely suspect from a series of patches. I will do some more testing to track down the problem.

In fact, the doctest for selmer_group explicitely says, that [2, a + 1, -a] is the expected result for 64 bit systems.

Agreed, but this result changed by #2329.

comment:24 in reply to: ↑ 23 Changed 10 years ago by AlexanderDreyer

Replying to jdemeyer:

Replying to AlexanderDreyer:

Are you sure, this is caused by PolyBoRi??

No, it is just the most likely suspect from a series of patches. I will do some more testing to track down the problem.

Not really, PolyBoRi? is only imported into crypto/boolean_function.pyx.

Can I help? Is there a rc for Sage 4.7 somewhere?

comment:25 Changed 10 years ago by jdemeyer

  • Status changed from needs_work to positive_review

You are right, the problem is unrelated to PolyBoRi?.

comment:26 Changed 10 years ago by malb

  • Status changed from positive_review to needs_work

Hi,

it seems I found a regression in the PolyBoRi? 0.7.0 update:

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: F = Ideal(B.random_element() for _ in range(B.ngens()))
sage: F
Ideal (a*b + a + b*e + c*e + 1, a + b + c*d + c + 1, a*c + c + d*f + d + 1, a*c + c*f + c + d*f + 1, c*f + c + d + e + 1, a + b*c + b*d + e*f + 1) of Boolean PolynomialRing in a, b, c, d, e, f
sage: F.groebner_basis()

------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
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 (sorry).
------------------------------------------------------------

Backtrace

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7f192e07c6e0 (LWP 13588)]
linalg_step_modified (polys=@0x7ffffaaf3ea0, terms=@0x7ffffaaf3de0, leads_from_strat=@0x7ffffaaf3dc0, log=false, optDrawMatrices=false, matrixPrefix=0x2457108 "matrix") at groebner/src/nf.cc:2335
2335    groebner/src/nf.cc: No such file or directory.
        in groebner/src/nf.cc
Current language:  auto; currently c++
(gdb) bt
#0  linalg_step_modified (polys=@0x7ffffaaf3ea0, terms=@0x7ffffaaf3de0, leads_from_strat=@0x7ffffaaf3dc0, log=false, optDrawMatrices=false, matrixPrefix=0x2457108 "matrix") at groebner/src/nf.cc:2335
#1  0x00007f19020cd4b4 in polybori::groebner::GroebnerStrategy::faugereStepDense (this=0x35ad520, orig_system=<value optimized out>) at groebner/src/nf.cc:2451
#2  0x00007f1902bda8ed in __pyx_pf_4sage_5rings_10polynomial_5pbori_16GroebnerStrategy_faugere_step_dense (__pyx_v_self=0x35ad510, __pyx_v_v=<value optimized out>) at sage/rings/polynomial/pbori.cpp:32091

More detailed backtrace forthcoming.

comment:27 Changed 10 years ago by malb

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7f8af219b6e0 (LWP 16515)]
0x00007f8ac60d032a in linalg_step_modified (polys=@0x7fff3d788440, terms=@0x7fff3d788380, leads_from_strat=@0x7fff3d788360, log=false, optDrawMatrices=false, matrixPrefix=0x34a85d8 "matrix")
    at groebner/src/nf.cc:2332
2332                    assert(step1.terms_as_exp[row_start[from_it->second]]==e);
Current language:  auto; currently c++

Alexander, does that ring any bells?

comment:28 Changed 10 years ago by AlexanderDreyer

You have found a bug in PolyBoRi?! This issue also occurs using or original interface. It somewhen showed up in the last weeks. I'll check it out.

comment:29 Changed 10 years ago by AlexanderDreyer

  • Description modified (diff)
  • Report Upstream changed from N/A to Fixed upstream, in a later stable release.
  • Status changed from needs_work to needs_review

I fixed that issue (also upstream), and put a revised spkg here: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p1.spkg

comment:30 Changed 10 years ago by AlexanderDreyer

  • Status changed from needs_review to needs_work

Sorry, this doesn't fix it.

comment:31 Changed 10 years ago by AlexanderDreyer

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I fixed soem coercion issue, which seem to cause that problem. Next try!

comment:32 Changed 10 years ago by burcin

  • Cc burcin added; Burcin removed

comment:33 Changed 10 years ago by malb

Hi Alexander, shall I try the new SPKG or just the patch?

comment:34 Changed 10 years ago by AlexanderDreyer

The spkg also fixes some minor issue, so please check the new spkg and both patches (did not fold them yet).

comment:35 Changed 10 years ago by malb

  • Description modified (diff)

comment:36 Changed 10 years ago by malb

  • Description modified (diff)
  • I couldn't apply your patch, so I copied the stuff over by hand and included it in the main patch
  • I added a doctest to check that the bug is indeed fixed (it is)
  • I cleaned up the SPKG somewhat (updated SPKG.txt + removed spkg-install~)
  • builds + passes tests for me

Alexander, since I touched it now, I think you need to do the final sign-off: i.e. you should check whether my patches are okay. If you think so, you set the positive review flag.

comment:37 Changed 10 years ago by AlexanderDreyer

I wasn't on 4.6.2 yet (compiling now), so I guess, this was the reason why the patch didn't apply. I'll check it as soon as I have 4.6.2 ready.

comment:38 Changed 10 years ago by burcin

  • Reviewers changed from Martin Albrecht to Martin Albrecht, Burcin Erocal
  • Status changed from needs_review to positive_review

The last patch applies cleanly to 4.6.2 and passes tests in the sage/{rings,crypto,libs} directories. The package and the patch look good to me. I'm switching this to a positive review.

Thanks for all the work guys.

comment:39 Changed 10 years ago by AlexanderDreyer

  • Status changed from positive_review to needs_work

I'm sorry, I forgot one minor issue with the variable names. (Occurs only if PolyBoRi?'s built-in frontend ipbori ist used instead of Sage.)

comment:40 Changed 10 years ago by AlexanderDreyer

  • Status changed from needs_work to needs_review

comment:41 Changed 10 years ago by AlexanderDreyer

  • Description modified (diff)

comment:42 Changed 10 years ago by malb

Change looks harmless enough, but can you add a doctest to show its behaviour?

comment:43 Changed 10 years ago by AlexanderDreyer

Noe, problem, the doctest is in attachment:polybori_0_7rev4.patch @malb since I do not have the permissions: can you replace the main patch with a fold of those three patches?

Changed 10 years ago by malb

comment:44 Changed 10 years ago by malb

  • Description modified (diff)
  • Status changed from needs_review to positive_review

All done.

comment:45 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:46 Changed 10 years ago by jdemeyer

  • Authors changed from Martin Albrecht,AlexanderDreyer to Martin Albrecht, Alexander Dreyer

comment:47 Changed 10 years ago by jdemeyer

  • Keywords spkg added
  • Priority changed from major to blocker
  • Resolution fixed deleted
  • Status changed from closed to new

comment:48 Changed 10 years ago by jdemeyer

  • Description modified (diff)
  • Status changed from new to needs_review

New SPKG.txt needs review.

Changed 10 years ago by jdemeyer

Diff for SPKG.txt, needs review

comment:49 Changed 10 years ago by jdemeyer

  • Summary changed from update PolyBoRi to newest upstream release 0.7 to update PolyBoRi to newest upstream release 0.7.0

comment:50 Changed 10 years ago by malb

  • Status changed from needs_review to positive_review

comment:51 Changed 10 years ago by jdemeyer

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.