Opened 11 years ago

Last modified 8 years ago

#9880 closed defect

Segfault in PyNaC 0.2.0.p4 — at Version 42

Reported by: jpflori Owned by: burcin
Priority: major Milestone: sage-5.11
Component: symbolics Keywords: pynac spkg
Cc: kcrisman, zimmerma Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by burcin)

Here is a short example found by Burcin and reproducing the bug:

b = [var('b_%s'%i) for i in range(4)]

precomp = (2^b_2 + 2)*(2^b_1 + 2^(-b_1) + 2^b_1*2^b_0 - 2^b_1*2^(-b_0)
- 2^(-b_1)*2^b_0 - 2^(-b_1)*2^(-b_0) + 2^b_0 + 2^(-b_0) - 9) + (2^b_1 +
2^(-b_1) + 2^b_1*2^b_0 - 2^b_1*2^(-b_0) - 2^(-b_1)*2^b_0 -
2^(-b_1)*2^(-b_0) + 2^b_0 + 2^(-b_0) - 9)/2^b_2

repl_dict = {b_0: b_0, b_3: b_1, b_2: b_3, b_1: b_2}
P = precomp.substitute(repl_dict)
P.expand() 

This is already being discussed here: http://groups.google.com/group/sage-support/browse_thread/thread/7c85f02c76012722

The following patches are for the Sage library to enable access to the PyNaC order and randomly test that it is a SWO:

Apply trac_9880_fix_import.patch, trac_9880_pynac_order.take2.patch, trac_9880_randomized_testing.patch

Change History (53)

comment:1 Changed 11 years ago by burcin

  • Description modified (diff)
  • Milestone set to sage-4.6

comment:2 in reply to: ↑ description Changed 11 years ago by jpflori

  • Description modified (diff)

The bug happened because of the comparison functions which are used in a call to std::sort.

I have finally looked at the comparison functions and exchanging :

cmpval = seq[0].coeff.compare(other.exponent);

by

cmpval = -seq[0].coeff.compare(other.exponent);

in mul::compare_pow (mul.cpp:1265) seems to prevent the above bug from happening.

It seems to fit better with the change made by William Stein in power::compare_same_type (power.cpp:951).

However it doesn't mean the problem is completely solved...

I'll try to take a deeper look at the comparison functions at some point.

I tested the above fix with pynac 0.2.1.

Changed 11 years ago by jpflori

Burcin original patch

Changed 11 years ago by jpflori

Patch to apply on top of the other one

comment:3 follow-up: Changed 11 years ago by jpflori

We've been working on a patch to fix the issue.

Original discussion is here:

http://groups.google.com/group/pynac-devel/browse_thread/thread/a36020bf9208bf08/abdf6671ef0b926a#abdf6671ef0b926a

Burcin produced a patch restoring GiNaC original order for internal use and using the new ones only for printing ; thus fixing the bug.

I then worked on top of it to get a more consistent order.

You can test them using pynac 0.2.1 from #9901 ("cd spkg/standard/pynac-0.2.1/src/" then "hg import" both patches and build/install, you should "./sage -b" if upgrading from a previous version of pynac).

I don't consider that version as definitve, but would like to get some feedback on the order used for printing.

I don't use everything pynac provides so it is more than probable that some expression are not correctly printed now.

Do not hesitate to report it.

comment:4 Changed 10 years ago by jpflori

  • Status changed from new to needs_review

comment:5 Changed 10 years ago by kcrisman

  • Cc kcrisman jason added

#10282 almost certainly is the same thing.

comment:6 Changed 10 years ago by kcrisman

  • Cc jason removed

Fixing this probably will close #9632 - just putting that here for the record.

comment:7 Changed 10 years ago by vbraun

Apply trac_9880_revert_marking_random_from_trac_10187.patch to re-enable doctests that fail on OSX/PPC.

comment:8 Changed 10 years ago by kcrisman

(Just OS X, not any particular architecture, I think.)

Changed 10 years ago by vbraun

Re-enable doctests that fail on PPC due to this issue (updated)

comment:9 in reply to: ↑ 3 Changed 10 years ago by kcrisman

I don't use everything pynac provides so it is more than probable that some expression are not correctly printed now.

Do not hesitate to report it.

I'd like to test this at some point, but have two problems.

  • There is too much C++ for me to review it properly, unless a lot of it really is just reverting. Is there an easy way to figure out what is actual new code, and what is going back to something more-or-less Ginac?
  • I am not sure exactly what sort of expressions would not be properly printed. Can you give any kind of example of what sort of bad behavior to look for with testing (perhaps randomized)?

comment:10 Changed 10 years ago by jpflori

I guess there are two main parts in this ticket, I did not have a look for a long time, so all this should be taken carefully :

  • Burcin patch which (more or less) revert the internal ordering in Pynac to the original one in Ginac and create new methods to use a different order for printing. We could maybe only apply the part reverting the internal order to Ginac original one to get the bug solved and close this ticket.
  • However, it is not a solution to use Ginac order for printing because it is quite random and unpredictable, it depends on variable order creation among others. That's the reason for the different order for printing (and getting operands and so on). It was not quite coherent, whence my patch to make it a little better. We could merge that in a second ticket. By the way, the order implemented right now should be more or less degrevlex.
  • With that new framework, we could also quite easily allow the use of different orders for manipulating (ie printing, getting operands...) symbolic expressions in Sage (Burcin already mentionned that somewhere on the Web IIRC).
  • I think there is still work to do regarding expressions manipulation (see #9989)
  • I don't really have an idea of what could get misprinted with Burcin+my patch applied. You could try multivariate polynomials to check it follows degrevlex, then such expressions times exponentials and let me know what you feel.

comment:11 Changed 10 years ago by vbraun

I could review the c++ but the code in the ticket seems to work for me. If it segfaults for you, how about including a full sage session with a stack backtrace at the very least?

comment:12 Changed 10 years ago by jpflori

There is all you are asking for in the original discussion linked in the ticket description.

Maybe something changed since then, the ticket is quite old.

comment:13 Changed 10 years ago by jpflori

As far as I'm concerned, it still segfaults with the Sage 4.6 package for 32-bit Ubuntu provided on sagemath.org, as well as on a 64 bit Sage 4.6 that I built myself.

I did not test it any 4.6.1 alpha or rc yet.

comment:14 Changed 10 years ago by jpflori

I finally got Sage 4.6.1 final built from scratch, and:

  • indeed the specific instance of the bug mentionned here is no longer present
  • however, it does not mean that the bug is solved because:
    • nothing changed in pynac (IIRC)
    • the problem in the ordering used by pynac (which caused the bug when called within std::sort) are still present, I'll post a problematic expression asap

By the way, the problem of different ordering on different architecture should still be present (10187#comment:39).

comment:15 Changed 10 years ago by jpflori

Ok, here is a kind of strange example for the problems of ordering still hapenning with Sage 4.6.1:

sage: b_0,b_1,b_2=var('b_0,b_1,b_2')
sage: f = 1/27*b_2^2/(2^b_2)^2 + 1/27*b_1^2/(2^b_1)^2 + 1/27*b_0^2/(2^b_0)^2 + 1/27*b_2/(2^b_2)^2 - 2/81/(2^b_2)^2 + 1/27*b_1/(2^b_1)^2 + 8/243/(2^b_2)^2 - 1/81*b_0/(2^b_0)^2 - 1/27*b_1^2/((2^b_2)^2*(2^b_1)^2) - 1/27*b_0^2/((2^b_2)^2*(2^b_0)^2) - 20/243/(2^b_1)^2 + 1/9/2^b_0 + 4/81*b_0/(2^b_0)^2 - 8/243/(2^b_2)^2 - 2/9/(2^b_2*2^b_1) - 2/9/(2^b_2*2^b_0) + 8/243/(2^b_1)^2 - 1/9/2^b_0 + 2/9/(2^b_2*2^b_1) + 2/9/(2^b_2*2^b_0) - 2/27*b_1*b_2/((2^b_2)^2*(2^b_1)^2) - 1/27*b_2^2/((2^b_2)^2*(2^b_1)^2) - 2/27*b_0*b_2/((2^b_2)^2*(2^b_0)^2) - 1/27*b_2^2/((2^b_2)^2*(2^b_0)^2) + 2/81/(2^b_1)^2 - 1/27*b_0^2/((2^b_1)^2*(2^b_0)^2) - 2/27*b_0*b_1/((2^b_1)^2*(2^b_0)^2) - 1/27*b_1^2/((2^b_1)^2*(2^b_0)^2) - 2/81/(2^b_0)^2 + 5/27*b_1/((2^b_2)^2*(2^b_1)^2) + 5/27*b_2/((2^b_2)^2*(2^b_1)^2) + 5/27*b_0/((2^b_2)^2*(2^b_0)^2) + 5/27*b_2/((2^b_2)^2*(2^b_0)^2) + 5/27*b_0/((2^b_1)^2*(2^b_0)^2) + 5/27*b_1/((2^b_1)^2*(2^b_0)^2) - 4/81/((2^b_2)^2*(2^b_1)^2) + 1/27*b_0^2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 2/27*b_0*b_1/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 2/27*b_0*b_2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 1/27*b_1^2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 2/27*b_1*b_2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 1/27*b_2^2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) - 4/81/((2^b_2)^2*(2^b_0)^2) - 4/81/((2^b_1)^2*(2^b_0)^2) - 11/27*b_0/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) - 11/27*b_1/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) - 11/27*b_2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 64/81/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 35/81
sage: f
1/27*b_2^2/(2^b_2)^2 + 1/27*b_1^2/(2^b_1)^2 + 1/27*b_0^2/(2^b_0)^2 + 1/27*b_2/(2^b_2)^2 + 1/27*b_1/(2^b_1)^2 - 8/243/(2^b_2)^2 + 2/9/(2^b_2*2^b_1) + 2/9/(2^b_2*2^b_0) - 2/27*b_1*b_2/((2^b_2)^2*(2^b_1)^2) - 1/27*b_2^2/((2^b_2)^2*(2^b_1)^2) - 2/27*b_0*b_2/((2^b_2)^2*(2^b_0)^2) - 1/27*b_2^2/((2^b_2)^2*(2^b_0)^2) + 14/243/(2^b_1)^2 + 1/27*b_0/(2^b_0)^2 + 2/243/(2^b_2)^2 - 2/9/(2^b_2*2^b_1) - 2/9/(2^b_2*2^b_0) - 1/27*b_1^2/((2^b_2)^2*(2^b_1)^2) - 1/27*b_0^2/((2^b_2)^2*(2^b_0)^2) - 20/243/(2^b_1)^2 - 1/27*b_0^2/((2^b_1)^2*(2^b_0)^2) - 2/27*b_0*b_1/((2^b_1)^2*(2^b_0)^2) - 1/27*b_1^2/((2^b_1)^2*(2^b_0)^2) - 2/81/(2^b_0)^2 + 5/27*b_1/((2^b_2)^2*(2^b_1)^2) + 5/27*b_2/((2^b_2)^2*(2^b_1)^2) + 5/27*b_0/((2^b_2)^2*(2^b_0)^2) + 5/27*b_2/((2^b_2)^2*(2^b_0)^2) + 5/27*b_0/((2^b_1)^2*(2^b_0)^2) + 5/27*b_1/((2^b_1)^2*(2^b_0)^2) - 4/81/((2^b_2)^2*(2^b_1)^2) + 1/27*b_0^2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 2/27*b_0*b_1/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 2/27*b_0*b_2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 1/27*b_1^2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 2/27*b_1*b_2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 1/27*b_2^2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) - 4/81/((2^b_2)^2*(2^b_0)^2) - 4/81/((2^b_1)^2*(2^b_0)^2) - 11/27*b_0/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) - 11/27*b_1/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) - 11/27*b_2/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 64/81/((2^b_2)^2*(2^b_1)^2*(2^b_0)^2) + 35/81


The expression for f should get (a little bit) simplified.

For example, there are different summands where the only symbolic expressions used are (2^b_2)^-2 and they should get automatically gathered when pynac creates the object.

In fact calling expand() method on f gives you the right expression, but if things were working correctly you should not have to do this.

comment:16 Changed 10 years ago by gagern

Can someone experiencing this bug please provide a gdb backtrace? There is a (small) possibility that this issue here might be related to an issue I encounter with sage on Gentoo Linux (with segfault in PyNaC as well), and I'd like to know for sure whether the error occurs inside the function __cxxabiv1::__cxa_allocate_exception or not.

comment:17 follow-up: Changed 10 years ago by jpflori

The detailed description of the segfault mentionned here is available in the discussion mentionned in the ticket description.

I'll put it here so that everybody finds it:

  • the segfault happens in a call to std::sort() in a call to compare() because the ordering used by pynac is not a strict weak ordering. so it is kind of random. and I think youre bug is completely unrelated.
  • the piece of code in the ticket description do not produce the segfault anymore since sage 4.6.1 (still present in 4.6.0), however the order was not changed, so it could still happen with other pieces of code, so here is a backtrace produce with a previous version of sage:

#0  GiNaC::power::compare (this=0x449be20, other=...) at power.cpp:899
#1  0x00007fffd7a9cc18 in void
std::__unguarded_linear_insert<__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair,
GiNaC::expair_rest_is_less>(__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair, GiNaC::expair_rest_is_less) ()
   from /home/jp/boulot/thèse/sage/sage-4.5.2/local/lib/
libpynac-0.2.so.0
#2  0x00007fffd7a9cefa in void
std::__final_insertion_sort<__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair_rest_is_less>(__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair_rest_is_less) () from /home/jp/boulot/thèse/sage/
sage-4.5.2/local/lib/libpynac-0.2.so.0
#3  0x00007fffd7a95657 in
sort<__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair_rest_is_less> (this=<value optimized out>) at /usr/
include/c++/4.4/bits/stl_algo.h:5260
#4  GiNaC::expairseq::canonicalize (this=<value optimized out>) at
expairseq.cpp:1177
#5  0x00007fffd7a994a4 in GiNaC::expairseq::construct_from_epvector
(this=0x44a5070, v=<value optimized out>,
    do_index_renaming=<value optimized out>) at expairseq.cpp:1055
#6  0x00007fffd7a58685 in GiNaC::add::add (this=0x44a5070, vp=...,
oc=<value optimized out>) at add.cpp:100
#7  0x00007fffd7a5871f in GiNaC::add::expand (this=0x449eb80,
options=<value optimized out>) at add.cpp:669
#8  0x00007fffd7a9231d in GiNaC::ex::expand (this=<value optimized
out>, options=3620337048) at ex.cpp:78
#9  0x00007fffd773e386 in
__pyx_pf_4sage_8symbolic_10expression_10Expression_expand
(__pyx_v_self=<value optimized out>,
    __pyx_args=0x601160, __pyx_kwds=0x0) at sage/symbolic/
expression.cpp:13604
#10 0x00007ffff7b107ca in call_function (f=0x44a4580, throwflag=<value
optimized out>) at Python/ceval.c:3706
#11 !PyEval_EvalFrameEx (f=0x44a4580, throwflag=<value optimized out>)
at Python/ceval.c:2389
#12 0x00007ffff7b124ad in !PyEval_EvalCodeEx (co=0x79c4c0,
globals=<value optimized out>, locals=<value optimized out>,
args=0x0,
    argcount=<value optimized out>, kws=0x0, kwcount=0, defs=0x0,
defcount=0, closure=0x0) at Python/ceval.c:2968
#13 0x00007ffff7b12582 in !PyEval_EvalCode (co=0x449be20,
globals=0x1135200007879, locals=0x7fffd7c9f598) at Python/ceval.c:522
#14 0x00007ffff7b3014c in run_mod (
.
.
.

And valgrind output also:
==27910== Invalid read of size 8
==27910==    at 0x282C4BF1: void
std::__unguarded_linear_insert<__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair,
GiNaC::expair_rest_is_less>(__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair, GiNaC::expair_rest_is_less) (ptr.h:99)
==27910==    by 0x282C4EF9: void
std::__final_insertion_sort<__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair_rest_is_less>(__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
__gnu_cxx::__normal_iterator<GiNaC::expair*, [[BR]] std::vector<GiNaC::expair, std::allocator<GiNaC::expair> > >,
GiNaC::expair_rest_is_less) (stl_algo.h:2161)
==27910==    by 0x282BD656: GiNaC::expairseq::canonicalize()
(stl_algo.h:5260)
==27910==    by 0x282C14A3:
GiNaC::expairseq::construct_from_epvector(std::vector<GiNaC::expair, [[BR]] std::allocator<GiNaC::expair> > const&, bool) (expairseq.cpp:1055)
==27910==    by 0x28280684:
GiNaC::add::add(std::auto_ptr<std::vector<GiNaC::expair, [[BR]] std::allocator<GiNaC::expair> > >, GiNaC::ex const&) (add.cpp:100)
==27910==    by 0x2828071E: GiNaC::add::expand(unsigned int) const
(add.cpp:669)
==27910==    by 0x282BA31C: GiNaC::ex::expand(unsigned int) const
(ex.cpp:78)
==27910==    by 0x28811385:
__pyx_pf_4sage_8symbolic_10expression_10Expression_expand(_object*,
_object*, _object*) (expression.cpp:13604)
==27910==    by 0x4F137C9: !PyEval_EvalFrameEx (ceval.c:3706)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F15581: !PyEval_EvalCode (ceval.c:522)
==27910==    by 0x4F3314B: !PyRun_StringFlags (pythonrun.c:1335)
==27910==    by 0x4F122DD: !PyEval_EvalFrameEx (ceval.c:4437)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4E9BDDE: function_call (funcobject.c:524)
==27910==    by 0x4E6FAA2: !PyObject_Call (abstract.c:2492)
==27910==    by 0xD7E0981:
__pyx_pf_4sage_9structure_11sage_object_load (sage_object.c:7304)
==27910==    by 0x4F137C9: !PyEval_EvalFrameEx (ceval.c:3706)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F15581: !PyEval_EvalCode (ceval.c:522)
==27910==    by 0x4F14853: !PyEval_EvalFrameEx (ceval.c:4401)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F13844: !PyEval_EvalFrameEx (ceval.c:3802)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F13844: !PyEval_EvalFrameEx (ceval.c:3802)
==27910==  Address 0x97e4280 is 16 bytes before a block of size 416
alloc'd
==27910==    at 0x4C24CCC: operator new(unsigned long)
(vg_replace_malloc.c:220)
==27910==    by 0x28286727: std::vector<GiNaC::expair, [[BR]] std::allocator<GiNaC::expair> >::reserve(unsigned long)
(new_allocator.h:89)
==27910==    by 0x282C0D4A:
GiNaC::expairseq::make_flat(std::vector<GiNaC::expair, [[BR]] std::allocator<GiNaC::expair> > const&, bool) (expairseq.cpp:1138)
==27910==    by 0x282C149B:
GiNaC::expairseq::construct_from_epvector(std::vector<GiNaC::expair, [[BR]] std::allocator<GiNaC::expair> > const&, bool) (expairseq.cpp:1051)
==27910==    by 0x28280684:
GiNaC::add::add(std::auto_ptr<std::vector<GiNaC::expair, [[BR]] std::allocator<GiNaC::expair> > >, GiNaC::ex const&) (add.cpp:100)
==27910==    by 0x2828071E: GiNaC::add::expand(unsigned int) const
(add.cpp:669)
==27910==    by 0x282BA31C: GiNaC::ex::expand(unsigned int) const
(ex.cpp:78)
==27910==    by 0x28811385:
__pyx_pf_4sage_8symbolic_10expression_10Expression_expand(_object*,
_object*, _object*) (expression.cpp:13604)
==27910==    by 0x4F137C9: !PyEval_EvalFrameEx (ceval.c:3706)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F15581: !PyEval_EvalCode (ceval.c:522)
==27910==    by 0x4F3314B: !PyRun_StringFlags (pythonrun.c:1335)
==27910==    by 0x4F122DD: !PyEval_EvalFrameEx (ceval.c:4437)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4E9BDDE: function_call (funcobject.c:524)
==27910==    by 0x4E6FAA2: !PyObject_Call (abstract.c:2492)
==27910==    by 0xD7E0981:
__pyx_pf_4sage_9structure_11sage_object_load (sage_object.c:7304)
==27910==    by 0x4F137C9: !PyEval_EvalFrameEx (ceval.c:3706)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F15581: !PyEval_EvalCode (ceval.c:522)
==27910==    by 0x4F14853: !PyEval_EvalFrameEx (ceval.c:4401)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F13844: !PyEval_EvalFrameEx (ceval.c:3802)
==27910==    by 0x4F154AC: !PyEval_EvalCodeEx (ceval.c:2968)
==27910==    by 0x4F13844: !PyEval_EvalFrameEx (ceval.c:3802)

comment:18 in reply to: ↑ 17 ; follow-up: Changed 10 years ago by vbraun

Replying to jpflori:

  • the segfault happens in a call to std::sort() in a call to compare() because the ordering used by pynac is not a strict weak ordering. so it is kind of random.

std::sort with anything but a strict weak ordering is a receipe for disaster. It is expected to crash, and it does in the example. So you are saying that we must never use GiNaC internal order for sorting.

I take it that expair_is_greater_degrevlex does implement a strict weak ordering, so it is safe to use with std::sort?

Is the patch in this ticket still relevant or has this been fixed elsewhere?

comment:19 in reply to: ↑ 18 Changed 10 years ago by jpflori

The problem is not the GiNaC original internal order (even if http://www.ginac.de/reference/structGiNaC_1_1expair__rest__is__less.html states it is not a SWO... at least using it makes the bug disappear and inconsistencies in automatic simplifications disappear; if it does not work, i guess it should be fixed by GiNaC team) but the modification of that order used in pynac (and so in Sage).

AFAIK the two patches here are still necessary, the segfault disappeared (!?!) but i still get some problems with automatic simplification as shown in http://trac.sagemath.org/sage_trac/ticket/9880#comment:15.

  • the first patch (by Burcin) reverts the original GiNaC ordering for internal use (e.g. to be used in call to std::sort) in pynac and use the modified order only for printing (it should also be uesd at some point for operands access and so on).
  • the second one (by me) should be applied on top of the first one and tries to polish the order used for printing so that is looks more like degrevlex.

It should not be much more difficult to implement other orders for printing (and operands access).

comment:20 Changed 10 years ago by vbraun

I have a suspicion that gcc's std::sort implementation changed which hides the bug. But just because its hidden doesn't mean that its still there. I'm currently trying to install some old versions to test.

comment:21 follow-up: Changed 10 years ago by vbraun

I don't understand the GiNaC documentation that you referred to (http://www.ginac.de/reference/structGiNaC_1_1expair__rest__is__less.html). They state it is not a SWO, and their example is that neither 3*x<2*x nor 2*x<3*x. But thats perfectly fine in a SWO, you can have incomparable elements. The only constraint on incomparable elements is transitivity, that is, if A and B are incomparable and B and C are incomparable then A and C are also incomparable. Do you understand why its not a SWO?

comment:22 Changed 10 years ago by burcin

#10833 was a duplicate of this. Here is the example from that ticket:

phi(x) = x^2 + c
def iterkate(n):
    pol = x
    for i in range(1,n):
        pol = phi(pol)
    return pol
g = expand(iterkate(7))

comment:23 in reply to: ↑ 21 Changed 10 years ago by jpflori

Replying to vbraun:

I don't understand the GiNaC documentation that you referred to (http://www.ginac.de/reference/structGiNaC_1_1expair__rest__is__less.html). They state it is not a SWO, and their example is that neither 3*x<2*x nor 2*x<3*x. But thats perfectly fine in a SWO, you can have incomparable elements. The only constraint on incomparable elements is transitivity, that is, if A and B are incomparable and B and C are incomparable then A and C are also incomparable. Do you understand why its not a SWO?

I have no idea why GiNaC order is not an SWO, my point was just to link that page where the GiNaC devs state it is not one.

However I never had problems with it so far, so maybe it is a SWO and the statement in GiNaC doc is just wrong.

We should post on GiNaC mailing list to get more info on that one. Maybe Burcin knows also.

What is definitely sure is that the modified order used in pynac is not correct. Because of it the result of a call to std::sort is flawed. This can be not too harmful (e.g. automatic simplification does not occur because terms which should be adjacent in the internal structure are not) but can also lead to segfaults (even if that dramatic side effect seems to depend on something mysterious, potentially on the gcc version used as you stated).

So at least for me, using the original GiNaC order solves many problems.

comment:24 follow-up: Changed 10 years ago by vbraun

Burcin: If you are working on pynac, can you add some private function/method that exposes the GiNaC order to Sage in addition to the Sage (printing) order? Then we can add some randomized testing to make sure that both are strict weak orders.

comment:25 in reply to: ↑ 24 Changed 10 years ago by jpflori

Replying to vbraun:

Burcin: If you are working on pynac, can you add some private function/method that exposes the GiNaC order to Sage in addition to the Sage (printing) order? Then we can add some randomized testing to make sure that both are strict weak orders.

Calling the _cmp_ method of an expression should give you access to pynac internal ordering (i.e. with the patched spkg, it is GiNaC original ordering; with the old one you would get the modified order currently used by pynac).

For example (with the new spkg):

sage: var('a b')
(a, b)
sage: x._cmp_(a)
1
sage: a._cmp_(b)
1
sage: a+b
a + b
sage: x+a
a + x

In GiNaC order, vars are ordered according to creation order iirc. So here we have x (automatically created) > a > b.

For printing, we use lexicographic order a > b > x and print bigger terms first.

To check it the only current way is to look at what gets printed, the internal ordering is used for everything else.

I'll try to post a minimal patch to have access to that order in sage.

comment:26 Changed 10 years ago by jpflori

Here you go:

  1. Install the new spkg available at http://perso.telecom-paristech.fr/~flori/pynac-0.2.1-order.spkg
  2. Apply pynac-order.patch
  3. Rebuild Sage
  4. Expession elements have now two new methods _cmp_add and _cmp_mul giving access to the order used for printing.

_cmp_add is (more or less) the function used to order elements in a sum and _cmp_mul in a product. Their behavior is not exactly the same (don't remember why, it's been a while).

Changed 10 years ago by jpflori

Access to comparison function used for printing.

comment:27 Changed 10 years ago by vbraun

Jean-Pierre: I think paristech.fr has some issues at the moment, can you upload it somewhere else?

comment:28 Changed 10 years ago by jpflori

  • Owner changed from burcin to jpflori

You can try accessing the same server at http://www.enst.fr/~flori/ or another one form the school at http://www.infres.enst.fr/~flori/ (same content, other server).

I've put also the package at http://viedethesarde.free.fr/sage/

You should get the file pynac-0.2.1-patched.spkg (not the -order one I deleted anyway).

It is quite the same as the one you would get by applying the patches of the ticket to pyanc-0.2.1.

comment:29 Changed 10 years ago by jpflori

  • Owner changed from jpflori to burcin

comment:30 Changed 10 years ago by vbraun

For the record, both the snippet in the ticket description and the iterkate() example reliably crash Sage-4.6.1 on Ubuntu-9.04.

The updated pynac-0.2.1-patched.spkg fixes this problem, and sage no longer crashes.

Changed 10 years ago by vbraun

Randomized testing of orders

comment:31 Changed 10 years ago by vbraun

With the attached script I find some examples in cmp_add where a<b<c<a. This violates SWO:

sage: attach strict_weak_order.py
sage: test_symbolic_expression_order(10000)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/home/vbraun/Sage/Order/<ipython console> in <module>()

/home/vbraun/Sage/Order/strict_weak_order.py in test_symbolic_expression_order(repetitions)
    113         c = make_random_expr()
    114         assert_strict_weak_order(a, b, c, lambda x,y: x._cmp_(y))
--> 115         assert_strict_weak_order(a, b, c, lambda x,y: x._cmp_add(y))
    116         assert_strict_weak_order(a, b, c, lambda x,y: x._cmp_mul(y))
    117 

/home/vbraun/Sage/Order/strict_weak_order.py in assert_strict_weak_order(a, b, c, cmp_func)
     63             
     64     for i,j,k in Permutations([0,1,2]):   # transitivity
---> 65         if cmp[i,j] and cmp[j,k] and not cmp[i,k]: raise ValueError, msg
     66 
     67     def incomparable(i,j):

ValueError: The binary relation failed to be a strict weak order on the elements
 a = 2*v10*(v5 - 2)*v7 + (-(v8 + e)*(-v8 + pi) + v6)*(v9*e - 2) - v2 - v3 - v5 - v9
 b = -(v3*v8 - 51*v2 - 105)*(v2 + 5)*(v3 - 1) + 3*v6*v9
 c = -v1*v6*brun + v6*v9*pi + 3*(7*(v5 + 1)*v7 - 3)*(-(v3 - 1)*e + v4) - (v5 - 4)*(v9 + 8) - v3 - 3
[0 0 1]
[1 0 0]
[0 1 0]

comment:32 Changed 10 years ago by jpflori

Not sure it is related, but i found the ordering of functions is currently random for functions having the same name.

I'm currently fixing this.

comment:33 Changed 10 years ago by jpflori

Ok that was unrelated.

It happened because some types were not handled by the new ordering and compared type ids directly which screw things up.

I launched a big test with your program and we'll see if it has reported any problems tomorrow.

comment:34 Changed 10 years ago by jpflori

I uploaded a new version of the spkg that you can get at:

http://www.infres.enst.fr/~flori/pynac-0.2.1-patched.spkg

or:

http://perso.telecom-paristech.fr/~flori/pynac-0.2.1-patched.spkg

I'm still running tests using test_symbolic_expression_order but did not get new errors.

Changed 10 years ago by jpflori

New version of patch, apply after burcin original one to build updated spkg

comment:35 Changed 10 years ago by vbraun

  • Status changed from needs_review to needs_work

Jean-Pierre: Are you now finished with running your tests? Can you bring the spkg into a reviewable state? At the very least it should be called pynac-0.2.1.p0.spkg and have a SPKG.txt entry.

comment:36 follow-up: Changed 10 years ago by burcin

Please excuse my ignorance, especially since I promised to make a pynac release which includes this patch ages ago, but I have a few questions and not enough time to test this and find out the answers on my own:

  • doesn't this require a patch to the Sage library at least to fix doctests? Is the new printing order exactly the same as the old (inconsistent) one?
  • Don't we also need to modify the operand access functions (at least the one in Sage - not the .op() function of ginac) to return the operands in the sorted order, not the stored (somewhat random) order?

BTW, Jean-Pierre, I wouldn't mind at all if you want to cut the new pynac release yourself. I can provide instructions on how to do this.

comment:37 in reply to: ↑ 36 Changed 10 years ago by jpflori

Replying to burcin:

  • doesn't this require a patch to the Sage library at least to fix doctests? Is the new printing order exactly the same as the old (inconsistent) one?

I don't think this order and the old one will coincide and a lot of doctests will have to be fixed if we use it. I'll try to have a look at all of this soon, I must admit I did not touch that code since my last post here.

  • Don't we also need to modify the operand access functions (at least the one in Sage - not the .op() function of ginac) to return the operands in the sorted order, not the stored (somewhat random) order?

I think you are right. I did not test it but it should return unexpected values with the new code. I'll include that when the new order seems consistent.

BTW, Jean-Pierre, I wouldn't mind at all if you want to cut the new pynac release yourself. I can provide instructions on how to do this.

Please go ahead, I'll find the time to do it.

I'm currently rebuilding everything and running some tests, but IIRC the piece of code Volker provided did not raise errors anymore. Of course there could be other inconsistencies here and there.

comment:38 Changed 10 years ago by jpflori

I did not get inconsistencies using Volker code yet. I'll package a candidate updated spkg today so that someone can have a look at the code update in pynac.

I'll do a proper pynac release when the code is positively reviewed and Burcin tells me how to.

Here is the list of doctests failure with the new spkg:

----------------------------------------------------------------------

The following tests failed:

	sage -t  -force_lib devel/sage/doc/en/constructions/polynomials.rst # 1 doctests failed
	sage -t  -force_lib devel/sage/doc/en/constructions/calculus.rst # 7 doctests failed
	sage -t  -force_lib devel/sage/doc/en/tutorial/tour_algebra.rst # 3 doctests failed
	sage -t  -force_lib devel/sage/doc/en/tutorial/introduction.rst # 2 doctests failed
	sage -t  -force_lib devel/sage/doc/en/a_tour_of_sage/index.rst # 1 doctests failed
	sage -t  -force_lib devel/sage/doc/en/bordeaux_2008/nf_introduction.rst # 1 doctests failed
	sage -t  -force_lib devel/sage/doc/fr/tutorial/tour_algebra.rst # 3 doctests failed
	sage -t  -force_lib devel/sage/doc/fr/tutorial/introduction.rst # 2 doctests failed
	sage -t  -force_lib devel/sage/doc/fr/a_tour_of_sage/index.rst # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/modules/vector_callable_symbolic_dense.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/modules/free_module_element.pyx # 3 doctests failed
	sage -t  -force_lib devel/sage/sage/interfaces/maxima_abstract.py # 3 doctests failed
	sage -t  -force_lib devel/sage/sage/interfaces/maxima_lib.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/numerical/optimize.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/tensor/differential_form_element.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/rings/integer.pyx # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/rings/qqbar.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/rings/power_series_ring.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/rings/number_field/number_field_element.pyx # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/rings/polynomial/polynomial_element.pyx # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/gsl/dft.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/functional.py # 12 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/tests.py # 16 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/desolvers.py # 14 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/calculus.py # 19 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/test_sympy.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/functions.py # 3 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/wester.py # 10 doctests failed
	sage -t  -force_lib devel/sage/sage/calculus/var.pyx # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/categories/classical_crystals.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/combinat/perfect_matching.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/combinat/partition.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/combinat/sf/ns_macdonald.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/ext/fast_callable.pyx # 3 doctests failed
	sage -t  -force_lib devel/sage/sage/schemes/elliptic_curves/ell_generic.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/stats/basic_stats.py # 7 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/log.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/hyperbolic.py # 3 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/special.py # 4 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/orthogonal_polys.py # 4 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/trig.py # 5 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/wigner.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/other.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/functions/piecewise.py # 12 doctests failed
	sage -t  -force_lib devel/sage/sage/matrix/matrix_symbolic_dense.pyx # 17 doctests failed
	sage -t  -force_lib devel/sage/sage/matrix/matrix2.pyx # 3 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/function_factory.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/maxima_wrapper.py # 14 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/expression_conversions.py # 7 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/ring.pyx # 3 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/constants.py # 4 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/random_tests.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/relation.py # 13 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/function.pyx # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/callable.py # 2 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/assumptions.py # 11 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/integration/integral.py # 9 doctests failed
	sage -t  -force_lib devel/sage/sage/symbolic/expression.pyx # 162 doctests failed
	sage -t  -force_lib devel/sage/sage/plot/plot3d/plot3d.py # 6 doctests failed
	sage -t  -force_lib devel/sage/sage/misc/preparser.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/misc/functional.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/graphs/generic_graph.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/misc/prandom.py # 1 doctests failed
	sage -t  -force_lib devel/sage/sage/misc/parser.pyx # 2 doctests failed
----------------------------------------------------------------------

I hope that all of them are trivial...

One question for Burcin: when you speak of operand access, are you thinking of #9989 or am I missing something in the current Sage code ?

comment:39 Changed 10 years ago by jpflori

A new spkg is available at http://perso.telecom-paristech.fr/~flori/sage/pynac-0.2.1.p0.spkg .

I just updated SPKG.txt and commited the changeset in comparison with pynac-0.2.1-patched.spkg .

The changes i pynac code from 0.2.1 are the result of applying:

  1. trac9880_pynac_order_burcin_original.patch
  2. trac_9880-pynac_order_jp_new-p2.patch

If you want to have access to the comparison functions used by the printing order (to stress pynac with Volker code strict_weak_order.py for example) you must also apply the patch access_order.patch .

comment:40 Changed 10 years ago by burcin

I don't want to delay this any further, but if this is merged all patches touching anything symbolic will need to be rebased. I suggest we try to review and merge any feasible symbolics tickets for the next release. Then this gets merged for 4.8 with big warnings, since users would also need to change doctests in any private code they might have.

I can actually spare time for such an effort now. I will see what I can do with the needs review/work tickets on trac starting tomorrow.

BTW, we should also include Volker's test script. Perhaps as a part of sage/symbolics/random_tests.py.

Jean-Pierre: Yes, by operand access I mean the .operands() and the recent .op from #9989.

Making a pynac release is just a matter of editing configure.ac, setting the version number according to the comments there and running autoreconf afterwards. I am not sure any more if the next pynac release should contain this. This can be pynac 0.3.0, and I will put in the patches in my queue corresponding to some of the tickets waiting on trac for 0.2.2.

Note that I imported the pynac-0.2.1 repository into bitbucket:

https://bitbucket.org/burcin/pynac

I hope to use the facilities there to streamline the development process.

Changed 10 years ago by vbraun

Initial patch

Changed 10 years ago by vbraun

Initial patch

Changed 10 years ago by vbraun

Initial patch

comment:41 Changed 10 years ago by vbraun

  • Description modified (diff)

comment:42 Changed 10 years ago by burcin

  • Description modified (diff)

I changed the structure of the order classes a little. New patches are available in my pynac queue:

https://bitbucket.org/burcin/pynac-patches/src

attachment:trac_9880_pynac_order.take2.patch should be applied to access these functions from Sage.

Changed 10 years ago by burcin

updated JP's patch for sage library to work with the new order patches

Changed 10 years ago by burcin

Note: See TracTickets for help on using tickets.