deep recursion in coercion framework during polynomial multiplication

[videlec]

sage: R1 = PolynomialRing(QQ, 't', 1000)
sage: S1 = PolynomialRing(R1, 'b', 10)
sage: S2 = PolynomialRing(QQ, 'b', 10)
sage: S1.an_element() * S2.an_element()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-64-f42ed114011e> in <module>()
----> 1 S1.an_element() * S2.an_element()

/opt/sage/src/sage/structure/element.pyx in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12068)()
   1519             return (<Element>left)._mul_(right)
   1520         if BOTH_ARE_ELEMENT(cl):
-> 1521             return coercion_model.bin_op(left, right, mul)
   1522 
   1523         try:

/opt/sage/src/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel_cache_maps.bin_op (build/cythonized/sage/structure/coerce.c:9419)()
   1078             if xp is yp:
   1079                 return op(x,y)
-> 1080             action = self.get_action(xp, yp, op, x, y)
   1081             if action is not None:
   1082                 return (<Action>action)._call_(x, y)

/opt/sage/src/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel_cache_maps.get_action (build/cythonized/sage/structure/coerce.c:16738)()
   1625         except KeyError:
   1626             pass
-> 1627         action = self.discover_action(R, S, op, r, s)
   1628         action = self.verify_action(action, R, S, op)
   1629         self._action_maps.set(R, S, op, action)

/opt/sage/src/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel_cache_maps.discover_action (build/cythonized/sage/structure/coerce.c:18300)()
   1777 
   1778         if isinstance(R, Parent):
-> 1779             action = (<Parent>R).get_action(S, op, True, r, s)
   1780             if action is not None:
   1781                 return action

/opt/sage/src/sage/structure/parent.pyx in sage.structure.parent.Parent.get_action (build/cythonized/sage/structure/parent.c:21508)()
   2447             pass
   2448 
-> 2449         action = self._get_action_(S, op, self_on_left)
   2450         if action is None:
   2451             action = self.discover_action(S, op, self_on_left, self_el, S_el)

/opt/sage/src/sage/structure/parent_old.pyx in sage.structure.parent_old.Parent._get_action_ (build/cythonized/sage/structure/parent_old.c:7659)()
    371     cpdef _get_action_(self, other, op, bint self_on_left):
    372         if self._element_constructor is None:
--> 373             return self.get_action_c(other, op, self_on_left)
    374         else:
    375             return parent.Parent._get_action_(self, other, op, self_on_left)

/opt/sage/src/sage/structure/parent_old.pyx in sage.structure.parent_old.Parent.get_action_c (build/cythonized/sage/structure/parent_old.c:4388)()
    204             pass
    205         if HAS_DICTIONARY(self):
--> 206             action = self.get_action_impl(S, op, self_on_left)
    207         else:
    208             action = self.get_action_c_impl(S, op, self_on_left)

/opt/sage/src/sage/structure/parent_old.pyx in sage.structure.parent_old.Parent.get_action_impl (build/cythonized/sage/structure/parent_old.c:4752)()
    216     def get_action_impl(self, S, op, self_on_left):
    217         check_old_coerce(self)
--> 218         return self.get_action_c_impl(S, op, self_on_left)
    219 
    220     cdef get_action_c_impl(self, S, op, bint self_on_left):

/opt/sage/src/sage/structure/parent_old.pyx in sage.structure.parent_old.Parent.get_action_c_impl (build/cythonized/sage/structure/parent_old.c:4814)()
    220     cdef get_action_c_impl(self, S, op, bint self_on_left):
    221         check_old_coerce(self)
--> 222         return self.discover_action(S, op, self_on_left, None, None)
    223 
    224     #################################################################################

/opt/sage/src/sage/structure/parent.pyx in sage.structure.parent.Parent.discover_action (build/cythonized/sage/structure/parent.c:22838)()
   2525                 # detect actions defined by _rmul_, _lmul_, _act_on_, and _acted_upon_ methods
   2526                 from .coerce_actions import detect_element_action
-> 2527                 action = detect_element_action(self, S, self_on_left, self_el, S_el)
   2528                 if action is not None:
   2529                     return action

/opt/sage/src/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.detect_element_action (build/cythonized/sage/structure/coerce_actions.c:5558)()
    230         # Elements defining _lmul_ and _rmul_
    231         try:
--> 232             return (RightModuleAction if X_on_left else LeftModuleAction)(Y, X, y, x)
    233         except CoercionException as msg:
    234             _record_exception()

/opt/sage/src/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.ModuleAction.__init__ (build/cythonized/sage/structure/coerce_actions.c:6457)()
    339                 from sage.categories.pushout import pushout
    340                 # this may raise a type error, which we propagate
--> 341                 self.extended_base = pushout(G, S)
    342                 # make sure the pushout actually gave a correct base extension of S
    343                 if self.extended_base.base() != pushout(G, base):

/opt/sage/local/lib/python2.7/site-packages/sage/categories/pushout.pyc in pushout(R, S)
   3919     else:
   3920         # Rc is a list of functors from Z to R and Sc is a list of functors from Z to S
-> 3921         R_tower = expand_tower(R_tower[:len(Rs)+1])
   3922         S_tower = expand_tower(S_tower[:len(Ss)+1])
   3923     Rc = [c[0] for c in R_tower[1:]]

/opt/sage/local/lib/python2.7/site-packages/sage/categories/pushout.pyc in expand_tower(tower)
   4244             for ff in reversed(fs[1:]):
   4245                 new_tower.append((ff, R))
-> 4246                 R = ff(R)
   4247             new_tower.append((fs[0], R))
   4248     return list(reversed(new_tower))

/opt/sage/src/sage/categories/functor.pyx in sage.categories.functor.Functor.__call__ (build/cythonized/sage/categories/functor.c:3127)()
    381         if is_Morphism(x):
    382             return self._apply_functor_to_morphism(x)
--> 383         y = self._apply_functor(self._coerce_into_domain(x))
    384         if not ((y in self.__codomain) or (y in self.__codomain.hom_category())):
    385             raise TypeError("%s is ill-defined, since it sends x (=%s) to something that is not in %s." % (repr(self), x, self.__codomain))

/opt/sage/local/lib/python2.7/site-packages/sage/categories/pushout.pyc in _apply_functor(self, R)
   1001         """
   1002         from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
-> 1003         return PolynomialRing(R, self.vars)
   1004 
   1005     def __eq__(self, other):

/opt/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring_constructor.pyc in PolynomialRing(base_ring, *args, **kwds)
    583         return _multi_variate(base_ring, names, **kwds)
    584     else:
--> 585         return _single_variate(base_ring, names, **kwds)
    586 
    587 

/opt/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring_constructor.pyc in _single_variate(base_ring, name, sparse, implementation, order)
    662             R = m.PolynomialRing_field(base_ring, name, sparse)
    663 
--> 664         elif base_ring.is_integral_domain(proof = False):
    665             R = m.PolynomialRing_integral_domain(base_ring, name, sparse, implementation)
    666         else:

/opt/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring.pyc in is_integral_domain(self, proof)
    464             False
    465         """
--> 466         return self.base_ring().is_integral_domain(proof)
    467 
    468     def is_unique_factorization_domain(self, proof = True):

... last 1 frames repeated, from the frame below ...

/opt/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring.pyc in is_integral_domain(self, proof)
    464             False
    465         """
--> 466         return self.base_ring().is_integral_domain(proof)
    467 
    468     def is_unique_factorization_domain(self, proof = True):

RuntimeError: maximum recursion depth exceeded

Works fine with smaller number of variables for the base ring

sage: R1 = PolynomialRing(QQ, 't', 100)
sage: S1 = PolynomialRing(R1, 'b', 10)
sage: S2 = PolynomialRing(QQ, 'b', 10)
sage: S1.an_element() * S2.an_element()
b0^2

CC: @simon-king-jena @nthiery @nbruin

Component: coercion

Keywords: bug

Author: Marc Mezzarobba

Branch/Commit: u/mmezzarobba/ticket/23906 @ 1b96a28

Reviewer: Vincent Delecroix

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

[mezzarobba]

comment:3

A simple heuristic to avoid the issue is to limit the expansion of construction functors in pushout() to cases where it results in a reasonably small number of elementary functors. This is neither super elegant nor super robust, but pushout() itself is a heuristic in the first place...

---

New commits:

ed53296

limit expansion of functors in pushout()

[mezzarobba]

Branch: u/mmezzarobba/ticket/23906

[mezzarobba]

Commit: ed53296

[mezzarobba]

Author: Marc Mezzarobba

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ed53296 to 434ec4f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

434ec4f

limit expansion of functors in pushout()

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:5

Why this change

-            sage: R = PolynomialRing(ZZ, 'x', 500)
-            sage: S = PolynomialRing(GF(5), 'x', 200)
+            sage: R = PolynomialRing(ZZ, 'x', 50)
+            sage: S = PolynomialRing(GF(5), 'x', 20)
             sage: R.gen(0) + S.gen(0)
             2*x0

[videlec]

comment:6

Since _expand_threshold is completely static it would better be a class attribute.

[mezzarobba]

comment:7

Replying to @videlec:

Why this change

-            sage: R = PolynomialRing(ZZ, 'x', 500)
-            sage: S = PolynomialRing(GF(5), 'x', 200)
+            sage: R = PolynomialRing(ZZ, 'x', 50)
+            sage: S = PolynomialRing(GF(5), 'x', 20)
             sage: R.gen(0) + S.gen(0)
             2*x0

I don't remember.

[videlec]

comment:8

Indeed it breaks

TypeError: unsupported operand parent(s) for +:
'Multivariate Polynomial Ring in x0, x1, x2, ... x499 over Integer Ring'
and
'Multivariate Polynomial Ring in x0, x1, x2, ..., x199 over Finite Field of size 5'

[mezzarobba]

comment:10

I think we discussed the issue verbally in Bordeaux, and that I convinced myself at the time that breaking this example was an acceptable trade-off. But I don't remember the details (and I'm not planning to work on this ticket any further for the moment).

[videlec]

comment:11

update milestone 8.3 -> 8.4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1b96a28

limit expansion of functors in pushout()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 434ec4f to 1b96a28