# Fix segfault when multiplying x * ((3*i + 4)*x - 5)

Reported by: Owned by: Emmanuel Charpentier critical sage-9.4 symbolics pynac, segfault Emmanuel Charpentier, Andrew, Peter Mueller, Nils Bruin, Samuel Lelièvre Dave Morris Travis Scrimshaw N/A 48f7a07 48f7a070bd168a3a039b6592f035c62a387b02bb

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 sage-support 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/sage-python: 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/sage-python: line 2: ... Segmentation fault: 11 sage -python "$@"


### comment:1 follow-up:  2 Changed 19 months ago by Emmanuel Charpentier

For one, this isn't a Maxima problem :

sage: maxima_calculus.interact()

--> Switching to Maxima_lib <--

maxima_lib: subst([y=%i], -(15*z/(17*y + 11) + 1)*(5*z/(4*y + 1) - 1)*(15*z/(3*y - 4) + 1)) ;
((15*z)/(3*%i-4)+1)*((5*z)/(4*%i+1)-1)*((-(15*z)/(17*%i+11))-1)
maxima_lib:
--> Exiting back to Sage <--



But :

maxima_calculus.subst([y==i],f).sage()


sends Sage in an infinite loop again...

the problem might lie in the Maxima-->Sage translation layer :

sage: foo = f._maxima_lib_()
sage: bar = maxima_calculus.subst((y==I)._maxima_lib_(), foo)
sage: bar
-((15*_SAGE_VAR_z)/(3*%i-4)+1)*((5*_SAGE_VAR_z)/(4*%i+1)-1)*((15*_SAGE_VAR_z)/(17*%i+11)+1)


works fine ; but asking for bar.sage() sends Sage in an infinite loop...

### comment:2 in reply to:  1 ; follow-up:  3 Changed 19 months ago by Nils Bruin

Putting the example in self-contained 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*%i-4)+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)$.

Last edited 19 months ago by Nils Bruin (previous) (diff)

### comment:3 in reply to:  2 Changed 19 months ago by Andrew

traceback often shows sage is constructing $\sqrt(17)$.

I see

• parse_sequence from misc/parser.pyx, it goes to
• __mul__ from structure/element.pyx line 1513
         if HAVE_SAME_PARENT(cl):
return (<Element>left)._mul_(right)

• _mul_ from symbolic/expression.pyx line 3792
         else:
x = left._gobj * _right._gobj

• and it jumps in GiNaC::operator* from pynac-0.7.27/ginac/operators.cpp:78
• GiNaC::exmul from pynac-0.7.27/ginac/operators.cpp:53
• GiNaC::ex::ex from pynac-0.7.27/ginac/ex.h:314
• GiNaC::ex::construct_from_basic from pynac-0.7.27/ginac/ex.cpp:923
• GiNaC::mul::eval from pynac-0.7.27/ginac/mul.cpp:783
• and here in jumps back to GiNaC::ex::ex from pynac-0.7.27/ginac/ex.h:314 and repeat calls GiNaC::ex::ex -> GiNaC::ex::construct_from_basic -> GiNaC::mul::eval more than 36500 times :(

### comment:4 follow-up:  5 Changed 19 months ago by Peter Mueller

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 in reply to:  4 Changed 19 months ago by Nils Bruin

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 straight-up 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 Peter Mueller

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*I-4)+1)/I causes segfault? (And indeed it does!)

### comment:7 Changed 18 months ago by Samuel Lelièvre

Cc: Emmanuel Charpentier Andrew Peter Mueller Nils Bruin Samuel Lelièvre added modified (diff) pynac segfault added 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 Dave Morris

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 Dave Morris

Branch: → public/31869

### comment:10 Changed 18 months ago by Dave Morris

Commit: → 48f7a070bd168a3a039b6592f035c62a387b02bb 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
Last edited 18 months ago by Dave Morris (previous) (diff)

### comment:11 Changed 18 months ago by Dave Morris

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 follow-up:  13 Changed 18 months ago by Travis Scrimshaw

Reviewers: → Travis Scrimshaw needs_review → positive_review

LGTM. Please also create a PR upstream and link it in the ticket description.

### comment:13 in reply to:  12 Changed 18 months ago by Emmanuel Charpentier

Same results here : passes ptestlong with the sae results as 9.4.betaO).