update PolyBoRi to newest upstream release 0.7.0

[malb]

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

• SPKG: http://boxen.math.washington.edu/home/jdemeyer/spkg/polybori-0.7.0.p1.spkg
• Apply: attachment: polybori-0.7.0.p1.patch

Upstream: Fixed upstream, in a later stable release.

CC: @alexanderdreyer @sagetrac-PolyBoRi @kiwifb @burcin

Component: packages: standard

Keywords: polybori spkg

Author: Martin Albrecht, Alexander Dreyer

Reviewer: Martin Albrecht, Burcin Erocal

Merged: sage-4.7.alpha2

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

[malb]

comment:1

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?

[malb]

comment:2

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:3

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

[malb]

comment:4

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:5

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.

[malb]

comment:6

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:7

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.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:9

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:10

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.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Description changed:

--- 
+++ 
@@ -10,3 +10,9 @@
 * Rename `BoolePolynomials::reducibleBy` ->  `BoolePolynomials::firstReducibleBy`
 * Unittests for libpolybori are available, covering 98% of libpolybori
 * Added experimental PolyGUI
+
+## Summary
+* Most recent spkg: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.spkg
+* Patches to Sage-lib (apply in the following order):
+  * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7.patch.gz
+  * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev1.patch.gz

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Changed author from Martin Albrecht to Martin Albrecht,AlexanderDreyer

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:11

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.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Description changed:

--- 
+++ 
@@ -15,4 +15,4 @@
 * Most recent spkg: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.spkg
 * Patches to Sage-lib (apply in the following order):
   * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7.patch.gz
-  * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev1.patch.gz
+  * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev1.2.patch.gz

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:12

I refreshed to patch.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Description changed:

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Description changed:

--- 
+++ 
@@ -12,7 +12,7 @@
 * Added experimental PolyGUI

 ## Summary
-* Most recent spkg: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.spkg
+* Most recent spkg: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p0.spkg
 * Patches to Sage-lib (apply in the following order):
   * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7.patch.gz
   * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev1.2.patch.gz

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:14

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

[malb]

Description changed:

--- 
+++ 
@@ -12,7 +12,5 @@
 * Added experimental PolyGUI

 ## Summary
-* Most recent spkg: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p0.spkg
-* Patches to Sage-lib (apply in the following order):
-  * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7.patch.gz
-  * https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev1.2.patch.gz
+* SPKG: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p0.spkg
+* Apply: [attachment: polybori-0.7.0.p0.patch](https://github.com/sagemath/sage/files/ticket10797/polybori-0.7.0.p0.patch.gz)

[malb]

comment:16

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.

[malb]

comment:17

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

[malb]

Reviewer: Martin Albrecht

[malb]

comment:19

builds & doctests pass on a fresh 4.6.2.rc1.

[jdemeyer]

comment:21

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]
**********************************************************************

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:22

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.

[jdemeyer]

comment:23

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.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:24

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?

[jdemeyer]

comment:25

You are right, the problem is unrelated to PolyBoRi.

[malb]

comment:26

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.

[malb]

comment:27

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?

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:28

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.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Description changed:

--- 
+++ 
@@ -12,5 +12,5 @@
 * Added experimental PolyGUI

 ## Summary
-* SPKG: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p0.spkg
+* SPKG: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p1.spkg
 * Apply: [attachment: polybori-0.7.0.p0.patch](https://github.com/sagemath/sage/files/ticket10797/polybori-0.7.0.p0.patch.gz)

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Upstream: Fixed upstream, in a later stable release.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:29

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:30

Sorry, this doesn't fix it.

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:31

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Description changed:

--- 
+++ 
@@ -14,3 +14,4 @@
 ## Summary
 * SPKG: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p1.spkg
 * Apply: [attachment: polybori-0.7.0.p0.patch](https://github.com/sagemath/sage/files/ticket10797/polybori-0.7.0.p0.patch.gz)
+* Apply: [attachment: polybori_0_7rev2.patch](https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev2.patch.gz)

[malb]

comment:33

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:34

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

[malb]

Description changed:

--- 
+++ 
@@ -13,5 +13,4 @@

 ## Summary
 * SPKG: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p1.spkg
-* Apply: [attachment: polybori-0.7.0.p0.patch](https://github.com/sagemath/sage/files/ticket10797/polybori-0.7.0.p0.patch.gz)
-* Apply: [attachment: polybori_0_7rev2.patch](https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev2.patch.gz)
+* Apply: [attachment: polybori-0.7.0.p1.patch](https://github.com/sagemath/sage-prod/files/10652118/polybori-0.7.0.p1.patch.gz)

[malb]

Description changed:

--- 
+++ 
@@ -12,5 +12,5 @@
 * Added experimental PolyGUI

 ## Summary
-* SPKG: http://sage.math.washington.edu/home/dreyer/spkg/polybori-0.7.0.p1.spkg
+* SPKG: http://sage.math.washington.edu/home/malb/spkgs/polybori-0.7.0.p1.spkg
 * Apply: [attachment: polybori-0.7.0.p1.patch](https://github.com/sagemath/sage-prod/files/10652118/polybori-0.7.0.p1.patch.gz)

[malb]

comment:36

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:37

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.

[burcin]

comment:38

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.

[burcin]

Changed reviewer from Martin Albrecht to Martin Albrecht, Burcin Erocal

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:39

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

Description changed:

--- 
+++ 
@@ -14,3 +14,4 @@
 ## Summary
 * SPKG: http://sage.math.washington.edu/home/malb/spkgs/polybori-0.7.0.p1.spkg
 * Apply: [attachment: polybori-0.7.0.p1.patch](https://github.com/sagemath/sage-prod/files/10652118/polybori-0.7.0.p1.patch.gz)
+* Apply: [attachment: polybori_0_7rev3.patch](https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev3.patch.gz)

[malb]

comment:42

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

[d46d2cb1-860f-484d-8329-8ebfc9f5d004]

comment:43

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?

[malb]

Description changed:

--- 
+++ 
@@ -14,4 +14,3 @@
 ## Summary
 * SPKG: http://sage.math.washington.edu/home/malb/spkgs/polybori-0.7.0.p1.spkg
 * Apply: [attachment: polybori-0.7.0.p1.patch](https://github.com/sagemath/sage-prod/files/10652118/polybori-0.7.0.p1.patch.gz)
-* Apply: [attachment: polybori_0_7rev3.patch](https://github.com/sagemath/sage/files/ticket10797/polybori_0_7rev3.patch.gz)

[malb]

comment:44

Attachment: polybori-0.7.0.p1.patch.gz

All done.