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: polybori-0.7.0.p1.patch​

[malb]

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]

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

[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

[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

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

[malb]

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

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

[AlexanderDreyer]

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

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

[AlexanderDreyer]

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.

[AlexanderDreyer]

I refreshed to patch.

[AlexanderDreyer]

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]

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]

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

[malb]

builds & doctests pass on a fresh 4.6.2.rc1.

[jdemeyer]

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

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

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

[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?

[jdemeyer]

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

[malb]

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]

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?

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

[AlexanderDreyer]

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

[AlexanderDreyer]

Sorry, this doesn't fix it.

[AlexanderDreyer]

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

[malb]

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

[AlexanderDreyer]

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

[malb]

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

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

[burcin]

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.

[AlexanderDreyer]

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

[malb]

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

[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?

[malb]

All done.

[jdemeyer]

New spkg with fixed SPKG.txt: ​http://boxen.math.washington.edu/home/jdemeyer/spkg/polybori-0.7.0.p1.spkg

[jdemeyer]

New SPKG.txt needs review.

[jdemeyer]

Diff for SPKG.txt, needs review

[malb]

polybori-SPKG.txt.diff​ looks fine.