Opened 19 months ago
Closed 18 months ago
#31869 closed defect (fixed)
Fix segfault when multiplying x * ((3*i + 4)*x  5)
Reported by:  Emmanuel Charpentier  Owned by:  

Priority:  critical  Milestone:  sage9.4 
Component:  symbolics  Keywords:  pynac, segfault 
Cc:  Emmanuel Charpentier, Andrew, Peter Mueller, Nils Bruin, Samuel Lelièvre  Merged in:  
Authors:  Dave Morris  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  48f7a07 (Commits, GitHub, GitLab)  Commit:  48f7a070bd168a3a039b6592f035c62a387b02bb 
Dependencies:  Stopgaps: 
Description (last modified by )
The following crashes Sage:
sage: x = SR.var('x') sage: h = (3*I + 4)*x  5 sage: x * h # hangs then crashes
Small variations work fine:
sage: h = (3*I + 4)*x  4 sage: x * h x*((3*I + 4)*x  4)
sage: h = (3*I + 5)*x  5 sage: x * h x*((3*I + 5)*x  5)
Priority set to critical as such a simple operation should not crash Sage.
From a report on sagesupport which involved substitutions.
The original report can be rephrased as follows.
Define f
:
sage: y, z = SR.var('y, z') sage: f = (15*z/(17*y + 11) + 1)*(5*z/(4*y + 1)  1)*(15*z/(3*y  4) + 1)
We want to substitute y = I
into f
. Tweaking f
first works:
sage: f.expand()(y=I) (3735/1394*I + 405/1394)*z^3  (606/697*I  942/697)*z^2  (8681/6970*I + 15973/6970)*z + 1 sage: f.partial_fraction(y)(y=I) (3735/1394*I + 405/1394)*z^3  (606/697*I  942/697)*z^2  (8681/6970*I + 15973/6970)*z + 1 sage: f.simplify_full()(y=I) (3735/1394*I + 405/1394)*z^3  (606/697*I  942/697)*z^2  (8681/6970*I + 15973/6970)*z + 1
but doing it directly crashes:
sage: f(y=I) # hangs then crashes  (no backtrace available)  Unhandled SIGSEGV: A segmentation fault occurred. This probably occurred because a *compiled* module has a bug in it and is not properly wrapped with sig_on(), sig_off(). Python will now terminate.  .../src/bin/sagepython: line 2: ... Segmentation fault: 11 sage python "$@"
A simpler example that boils down to the minimal reproducer:
sage: a, x = SR.var('a, x') sage: g = x * ((3*a + 4)*x  5) sage: g ((3*a + 4)*x  5)*x sage: g(a=I) # hangs then crashes  (no backtrace available)  Unhandled SIGSEGV: A segmentation fault occurred. This probably occurred because a *compiled* module has a bug in it and is not properly wrapped with sig_on(), sig_off(). Python will now terminate.  .../src/bin/sagepython: line 2: ... Segmentation fault: 11 sage python "$@"
Change History (14)
comment:1 followup: 2 Changed 19 months ago by
comment:2 followup: 3 Changed 19 months ago by
Replying to charpent:
Putting the example in selfcontained form here:
sage: var('z y') sage: f = (15*z/(17*y + 11) + 1)*(5*z/(4*y + 1)  1)*(15*z/(3*y  4) + 1) sage: foo = f._maxima_lib_() sage: bar = maxima_calculus.subst((y==I)._maxima_lib_(), foo) sage: bar ((15*_SAGE_VAR_z)/(3*%i4)+1)*((5*_SAGE_VAR_z)/(4*%i+1)1)*((15*_SAGE_VAR_z)/(17*%i+11)+1)but asking the following throws sage in an apparently infinite loop.
sage: bar.sage()
Oddly enough, interrupting the process and looking at the traceback often shows sage is constructing $\sqrt(17)$.
comment:3 Changed 19 months ago by
Replying to nbruin:
traceback often shows sage is constructing $\sqrt(17)$.
I see
parse_sequence
frommisc/parser.pyx
, it goes to__mul__
fromstructure/element.pyx
line 1513if HAVE_SAME_PARENT(cl): return (<Element>left)._mul_(right)
_mul_
fromsymbolic/expression.pyx
line 3792else: x = left._gobj * _right._gobj
 and it jumps in
GiNaC::operator*
frompynac0.7.27/ginac/operators.cpp:78
GiNaC::exmul
frompynac0.7.27/ginac/operators.cpp:53
GiNaC::ex::ex
frompynac0.7.27/ginac/ex.h:314
GiNaC::ex::construct_from_basic
frompynac0.7.27/ginac/ex.cpp:923
GiNaC::mul::eval
frompynac0.7.27/ginac/mul.cpp:783
 and here in jumps back to
GiNaC::ex::ex
frompynac0.7.27/ginac/ex.h:314
and repeat callsGiNaC::ex::ex > GiNaC::ex::construct_from_basic > GiNaC::mul::eval
more than 36500 times :(
comment:4 followup: 5 Changed 19 months ago by
I don't know if that helps to pin down the problem, but even in
var('z') a = z/(4*I + 1) b = 15*z/(3*I  4) + 1 c = a*b
the execution of the last line hangs. Slight modifications of the assignment of b
, like b = z/(3*I  4) + 1
or b = 15*z/(3*I  4)
don't display that problem.
comment:5 Changed 19 months ago by
Replying to ghypfmde:
I don't know if that helps to pin down the problem
I think it does: as far as I can see, the code example you give does not involve maxima at all. This indicates it's a straightup bug in pynac, or at least in the way sage uses it (pynac is basically part of sage: I don't think there is any other package that uses it)
comment:6 Changed 19 months ago by
I'm new to sage trac (and more of a naive end user of sage), so I don't want to potentially mess up this ticket. But in view of the many tickets, wouldn't a more expressive title (and fix of the typo) be more useful? From A simple substitution can send Sage in an infiite loop
I would expect that some substitution generates an unlimited recursion. Maybe something explicit like y = x*(5*x/(3*I4)+1)/I causes segfault
? (And indeed it does!)
comment:7 Changed 18 months ago by
Cc:  Emmanuel Charpentier Andrew Peter Mueller Nils Bruin Samuel Lelièvre added 

Description:  modified (diff) 
Keywords:  pynac segfault added 
Summary:  A simple substitution can send Sage in an infiite loop. → Fix segfault when multiplying x * ((3*i + 4)*x  5) 
Here is a simpler reproducer: x * ((3*i + 4)*x  5)
.
Kept original expression in ticket description so the discussion still makes sense.
comment:8 Changed 18 months ago by
Authors:  → Dave Morris 

The infinite loop (in pynac) is caused by an incorrect calculation of the integer_content
of a polynomial (or other sum) that has complex coefficients. I will soon provide a patch and further explanation.
comment:9 Changed 18 months ago by
Branch:  → public/31869 

comment:10 Changed 18 months ago by
Commit:  → 48f7a070bd168a3a039b6592f035c62a387b02bb 

Status:  new → needs_review 
This pynac patch should solve the problem.
Diagnosis: Pynac automatically simplifies expressions to a standard form. In the situation here, it passes repeatedly through a loop, until no changes are made in a pass, so it knows that it is finished. One step of the simplification of a polynomial (or other sum) divides by the integer_content
. This is supposed to be the largest rational number that can be divided by to give a result that has no denominator.
For a polynomial with rational coefficients, the integer_content
can be calculated by taking the gcd of the numerators, and dividing by the lcm of the denominators. Pynac tries to use this same formula for polynomials with complex coefficients, but a "feature" of the gcd
function sends the calculation awry. Namely, pynac assumes that gcd(a,0)
is always abs(a)
. (See #31884 for a complaint about this.)
Here is what goes wrong: To calculate the integer_content
of the expression (3*i + 4)*x  5
, pynac calculates gcd(gcd(0, 3*i + 4), 5)
. Since gcd(0, 3*i + 4)
is abs(3*i + 4)
, which is 5
, the result is gcd(5, 5)
, which is 5
. (This is incorrect: the integer_content
of this polynomial is 1
.) So pynac divides by 5
, resulting in (3/5 * i + 4/5)*x  1
. In the next pass through the loop, pynac sees the denominator of 5
, and (correctly) concludes that the integer_content
of this polynomial is 1/5
. It therefore divides by 1/5
to get rid of the denominator. This gets us back to the original polynomial, so pynac is in an infinite loop.
Solution: The integer_content
of a polynomial with coefficient a + b*i
should be calculated as if a
and b
were the coefficients of two different terms.
New commits:
48f7a07  trac 31869 fix pynac integer_content

comment:11 Changed 18 months ago by
PS Thanks to everyone who contributed to this discussion. The simplified example, the traceback, and the other comments made it much easier to locate the bug!
comment:12 followup: 13 Changed 18 months ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
LGTM. Please also create a PR upstream and link it in the ticket description.
comment:13 Changed 18 months ago by
comment:14 Changed 18 months ago by
Branch:  public/31869 → 48f7a070bd168a3a039b6592f035c62a387b02bb 

Resolution:  → fixed 
Status:  positive_review → closed 
For one, this isn't a Maxima problem :
But :
sends Sage in an infinite loop again...
the problem might lie in the Maxima>Sage translation layer :
works fine ; but asking for
bar.sage()
sends Sage in an infinite loop...