source: sage/structure/coerce.pyx @ 5858:90c27feeca40

Revision 5858:90c27feeca40, 18.6 KB checked in by Robert Bradshaw <robertwb@…>, 6 years ago (diff)

Improve pushout (multivariat poly), use pushout for coercion
Line 
1#*****************************************************************************
2#       Copyright (C) 2007 Robert Bradshaw <robertwb@math.washington.edu>
3#
4#  Distributed under the terms of the GNU General Public License (GPL)
5#
6#                  http://www.gnu.org/licenses/
7#*****************************************************************************
8
9
10include "../ext/stdsage.pxi"
11include "../ext/python_tuple.pxi"
12include "coerce.pxi"
13
14import operator
15import sage.categories.morphism
16
17cdef class CoercionModel_original(CoercionModel):
18    """
19    This is the original coercion model, as of SAGE 2.6 (2007-06-02)
20    """
21   
22    cdef canonical_coercion_c(self, x, y):
23        cdef int i
24        xp = parent_c(x)
25        yp = parent_c(y)
26        if xp is yp:
27            return x, y
28
29        if PY_IS_NUMERIC(x):
30            try:
31                x = yp(x)
32            except TypeError:
33                y = x.__class__(y)
34                return x, y
35            # Calling this every time incurs overhead -- however, if a mistake
36            # gets through then one can get infinite loops in C code hence core
37            # dumps.  And users define _coerce_ and __call__ for rings, which
38            # can easily have bugs in it, i.e., not really make the element
39            # have the correct parent.  Thus this check is *crucial*.
40            return _verify_canonical_coercion_c(x,y)
41       
42        elif PY_IS_NUMERIC(y):
43            try:
44                y = xp(y)
45            except TypeError:
46                x = y.__class__(x)
47                return x, y           
48            return _verify_canonical_coercion_c(x,y)
49
50        try:
51            if xp.has_coerce_map_from(yp):
52                y = (<Parent>xp)._coerce_c(y)
53                return _verify_canonical_coercion_c(x,y)
54        except AttributeError:
55            pass
56        try:
57            if yp.has_coerce_map_from(xp):
58                x = (<Parent>yp)._coerce_c(x)
59                return _verify_canonical_coercion_c(x,y)
60        except AttributeError:
61            pass
62        raise TypeError, "no common canonical parent for objects with parents: '%s' and '%s'"%(xp, yp)
63
64    cdef canonical_base_coercion_c(self, Element x, Element y):
65        if not have_same_base(x, y):
66            if (<Parent> x._parent._base).has_coerce_map_from_c(y._parent._base):
67                # coerce all elements of y to the base ring of x
68                y = y.base_extend_c(x._parent._base)
69            elif (<Parent> y._parent._base).has_coerce_map_from_c(x._parent._base):
70                # coerce x to have elements in the base ring of y
71                x = x.base_extend_c(y._parent._base)
72        return x,y
73
74    def canonical_base_coercion(self, x, y):
75        try:
76            xb = x.base_ring()
77        except AttributeError:
78            #raise TypeError, "unable to find base ring for %s (parent: %s)"%(x,x.parent())
79            raise TypeError, "unable to find base ring"
80        try:
81            yb = y.base_ring()
82        except AttributeError:
83            raise TypeError, "unable to find base ring"
84            #raise TypeError, "unable to find base ring for %s (parent: %s)"%(y,y.parent())
85        try:
86            b = self.canonical_coercion_c(xb(0),yb(0))[0].parent()
87        except TypeError:
88            raise TypeError, "unable to find base ring"
89            #raise TypeError, "unable to find a common base ring for %s (base ring: %s) and %s (base ring %s)"%(x,xb,y,yb)
90        return x.change_ring(b), y.change_ring(b)
91
92
93    cdef bin_op_c(self, x, y, op):
94        """
95        Compute x op y, where coercion of x and y works according to
96        SAGE's coercion rules.
97        """
98        # Try canonical element coercion.
99        try:
100            x1, y1 = self.canonical_coercion_c(x, y)
101            return op(x1,y1)       
102        except TypeError, msg:
103            # print msg  # this can be useful for debugging.
104            if not op is operator.mul:
105                raise TypeError, arith_error_message(x,y,op)
106
107        # If the op is multiplication, then some other algebra multiplications
108        # may be defined
109       
110        # 2. Try scalar multiplication.
111        # No way to multiply x and y using the ``coerce into a canonical
112        # parent'' rule.
113        # The next rule to try is scalar multiplication by coercing
114        # into the base ring.
115        cdef bint x_is_modelt, y_is_modelt
116
117        y_is_modelt = PY_TYPE_CHECK(y, ModuleElement)
118        if y_is_modelt:
119            # First try to coerce x into the base ring of y if y is an element.
120            try:
121                R = (<ModuleElement> y)._parent._base
122                if R is None:
123                    raise RuntimeError, "base of '%s' must be set to a ring (but it is None)!"%((<ModuleElement> y)._parent)
124                x = (<Parent>R)._coerce_c(x)
125                return (<ModuleElement> y)._rmul_c(x)     # the product x * y
126            except TypeError, msg:
127                pass
128
129        x_is_modelt = PY_TYPE_CHECK(x, ModuleElement)
130        if x_is_modelt:
131            # That did not work.  Try to coerce y into the base ring of x.
132            try:
133                R = (<ModuleElement> x)._parent._base
134                if R is None:
135                    raise RuntimeError, "base of '%s' must be set to a ring (but it is None)!"%((<ModuleElement> x)._parent)           
136                y = (<Parent> R)._coerce_c(y)
137                return (<ModuleElement> x)._lmul_c(y)    # the product x * y
138            except TypeError:
139                pass
140
141        if y_is_modelt and x_is_modelt:
142            # 3. Both canonical coercion failed, but both are module elements.
143            # Try base extending the right object by the parent of the left
144
145            ## TODO -- WORRY -- only unambiguous if one succeeds!
146            if  PY_TYPE_CHECK(x, RingElement):
147                try:
148                    return x * y.base_extend((<RingElement>x)._parent)
149                except (TypeError, AttributeError), msg:
150                    pass
151            # Also try to base extending the left object by the parent of the right
152            if  PY_TYPE_CHECK(y, RingElement):
153                try:
154                    return y * x.base_extend((<Element>y)._parent)
155                except (TypeError, AttributeError), msg:
156                    pass
157
158        # 4. Try _l_action or _r_action.
159        # Test to see if an _r_action or _l_action is
160        # defined on either side.
161        try:
162            return x._l_action(y)
163        except (AttributeError, TypeError):   
164            pass
165        try:
166            return y._r_action(x)
167        except (AttributeError, TypeError):
168            pass
169           
170        raise TypeError, arith_error_message(x,y,op)
171       
172
173# just so we can detect these fast to avoid action-searching
174cdef op_add, op_sub
175from operator import add as op_add, sub as op_sub
176
177cdef class CoercionModel_cache_maps(CoercionModel_original):
178
179    def __init__(self):
180        # This MUST be a mapping of tuples, where each
181        # tuple contains at least two elements that are either
182        # None or of type Morphism.
183        self._coercion_maps = {}
184        # This MUST be a mapping of actions.
185        self._action_maps = {}
186
187    cdef bin_op_c(self, x, y, op):
188               
189        if (op is not op_add) and (op is not op_sub):
190            # Actions take preference over common-parent coercions.
191            xp = parent_c(x)
192            yp = parent_c(y)
193            if xp is yp:
194                return op(x,y)
195            action = self.get_action_c(xp, yp, op)
196            if action is not None:
197                return (<Action>action)._call_c(x, y)
198       
199        try:
200            xy = self.canonical_coercion_c(x,y)
201            return op(<object>PyTuple_GET_ITEM(xy, 0), <object>PyTuple_GET_ITEM(xy, 1))
202        except TypeError:
203#            raise
204            pass
205           
206        if op is operator.mul:
207               
208            # elements may also act on non-elements
209            # (e.g. sequences or parents)
210            try:
211                return x._l_action(y)
212            except (AttributeError, TypeError):   
213                pass
214            try:
215                return y._r_action(x)
216            except (AttributeError, TypeError):
217                pass
218       
219        raise TypeError, arith_error_message(x,y,op)
220
221
222       
223    cdef canonical_coercion_c(self, x, y):
224        xp = parent_c(x)
225        yp = parent_c(y)
226        if xp is yp:
227            return x,y
228           
229        cdef Element x_elt, y_elt
230        coercions = self.coercion_maps_c(xp, yp)
231        if coercions is not None:
232            x_map, y_map = coercions
233            if x_map is not None:
234                x_elt = (<Morphism>x_map)._call_c(x)
235            else:
236                x_elt = x
237            if y_map is not None:
238                y_elt = (<Morphism>y_map)._call_c(y)
239            else:
240                y_elt = y
241            if x_elt._parent is y_elt._parent:
242                # We must verify this as otherwise we are prone to
243                # getting into an infinite loop in c, and the above
244                # morphisms may be written by (imperfect) users.
245                return x_elt,y_elt
246            elif x_elt._parent == y_elt._parent:
247                # TODO: Non-uniqueness of parents strikes again!
248                # print parent_c(x_elt), " is not ", parent_c(y_elt)
249                y_elt = parent_c(x_elt)(y_elt)
250                if x_elt._parent is y_elt._parent:
251                    return x_elt,y_elt
252            self._coercion_error(x, x_map, x_elt, y, y_map, y_elt)
253       
254        # Now handle the native python + sage object cases
255        # that were not taken care of above.
256        elif PY_IS_NUMERIC(x):
257            try:
258                x = yp(x)
259                if PY_TYPE_CHECK(yp, type): return x,y
260            except TypeError:
261                y = x.__class__(y)
262                return x, y
263            return _verify_canonical_coercion_c(x,y)
264
265        elif PY_IS_NUMERIC(y):
266            try:
267                y = xp(y)
268                if PY_TYPE_CHECK(xp, type): return x,y
269            except TypeError:
270                x = y.__class__(x)
271                return x, y           
272            return _verify_canonical_coercion_c(x,y)
273           
274        raise TypeError, "no common canonical parent for objects with parents: '%s' and '%s'"%(xp, yp)
275       
276
277    def _coercion_error(self, x, x_map, x_elt, y, y_map, y_elt):
278        raise RuntimeError, """There is a bug in the coercion code in SAGE.
279Both x (=%r) and y (=%r) are supposed to have identical parents but they don't.
280In fact, x has parent '%s'
281whereas y has parent '%s'
282
283Original elements %r (parent %s) and %r (parent %s) and morphisms
284%s %r
285%s %r"""%( x_elt, y_elt, parent_c(x_elt), parent_c(y_elt),
286            x, parent_c(x), y, parent_c(y),
287            type(x_map), x_map, type(y_map), y_map)
288   
289    def coercion_maps(self, R, S):
290        return self.coercion_maps_c(R, S)
291   
292    cdef coercion_maps_c(self, R, S):
293        try:
294            return self._coercion_maps[R,S]
295        except KeyError:
296            homs = self.discover_coercion_c(R, S)
297            if homs is not None:
298                self._coercion_maps[R,S] = homs
299                self._coercion_maps[S,R] = (homs[1], homs[0])
300            else:
301                self._coercion_maps[R,S] = self._coercion_maps[S,R] = None
302            return homs
303   
304    def get_action(self, R, S, op):
305        return self.get_action_c(R, S, op)
306   
307    cdef get_action_c(self, R, S, op):
308        try:
309            return self._action_maps[R,S,op]
310        except KeyError:
311            action = self.discover_action_c(R, S, op)
312            self._action_maps[R,S,op] = action
313            return action
314   
315    cdef discover_coercion_c(self, R, S):
316        from sage.categories.homset import Hom
317        if R is S:
318            return None, None
319           
320        # See if there is a natural coercion from R to S
321        if PY_TYPE_CHECK(R, Parent):
322            mor = (<Parent>R).coerce_map_from_c(S)
323            if mor is not None:
324                return None, mor
325
326        # See if there is a natural coercion from S to R
327        if PY_TYPE_CHECK(S, Parent):
328            mor = (<Parent>S).coerce_map_from_c(R)
329            if mor is not None:
330                return mor, None
331       
332        # Try base extending to left and right
333        # TODO: This is simple and ambiguous, add sophistication
334        if PY_TYPE_CHECK(R, ParentWithBase) and PY_TYPE_CHECK(S, Parent):
335            Z = (<ParentWithBase>R).base_extend_canonical_sym(S)
336            if Z is not None:
337                from sage.categories.homset import Hom
338                # Can I trust always __call__() to do the right thing in this case?
339                return sage.categories.morphism.CallMorphism(Hom(R, Z)), sage.categories.morphism.CallMorphism(Hom(S, Z))
340
341        return None
342       
343   
344    cdef discover_action_c(self, R, S, op):
345
346        if PY_TYPE_CHECK(S, Parent):
347            action = (<Parent>S).get_action_c(R, op, False)
348            if action is not None:
349#                print "found", action
350                return action
351   
352        if PY_TYPE_CHECK(R, Parent):
353            action = (<Parent>R).get_action_c(S, op, True)
354            if action is not None:
355#                print "found", action
356                return action
357       
358        if op is operator.div:
359            # Division on right is the same acting on right by inverse, if it is so defined.
360            # To return such an action, we need to verify that it would be an action for the mul
361            # operator, but the action must be over a parent containing inverse elements.
362            from sage.rings.ring import is_Ring
363            if is_Ring(S):
364                try:
365                    K = S.fraction_field()
366                except TypeError:
367                    K = None
368            else:
369                K = S
370               
371            if K is not None:           
372                if PY_TYPE_CHECK(S, Parent) and (<Parent>S).get_action_c(R, operator.mul, False) is not None:
373                    action = (<Parent>K).get_action_c(R, operator.mul, False)
374                    if action is not None and action.actor() is K:
375                        try:
376                            return ~action
377                        except TypeError:
378                            pass
379                           
380                if PY_TYPE_CHECK(R, Parent) and (<Parent>R).get_action_c(S, operator.mul, True) is not None:
381                    action = (<Parent>R).get_action_c(K, operator.mul, True)
382                    if action is not None and action.actor() is K:
383                        try:
384                            return ~action
385                        except TypeError:
386                            pass
387   
388
389from sage.structure.element cimport Element # workaround SageX bug
390
391cdef class LAction(Action):
392    """Action calls _l_action_ of the actor."""
393    def __init__(self, G, S):
394        Action.__init__(self, G, S, True, operator.mul)
395    cdef Element _call_c_impl(self, Element g, Element a):
396        return g._l_action_(a)  # a * g
397
398cdef class RAction(Action):
399    """Action calls _r_action_ of the actor."""
400    def __init__(self, G, S):
401        Action.__init__(self, G, S, False, operator.mul)
402    cdef Element _call_c_impl(self, Element a, Element g):
403        return g._r_action_(a)  # g * a
404
405cdef class LeftModuleAction(Action):
406    def __init__(self, G, S):
407        # Objects are implemented with the assumption that
408        # _rmul_ is given an element of the basering
409        if G is not S.base() and S.base() is not S:
410            # first we try the easy case of coercing G to the basering of S
411            self.connecting = S.base().coerce_map_from(G)
412            if self.connecting is None:
413                # otherwise, we try and find a base extension
414                from sage.categories.pushout import pushout
415                # this may raise a type error, which we propagate
416                self.extended_base = pushout(G, S)
417                # make sure the pushout actually gave correct a base extension of S
418                if self.extended_base.base() != pushout(G, S.base()):
419                    raise TypeError, "Actor must be coercable into base."
420                else:
421                    self.connecting = self.extended_base.base().coerce_map_from(G)
422               
423        # TODO: detect this better
424        # if this is bad it will raise a type error in the subsequent lines, which we propagate
425        cdef RingElement g = G._an_element()
426        cdef ModuleElement a = S._an_element()
427        res = self._call_c(g, a)
428       
429        if parent_c(res) is not S and parent_c(res) is not self.extended_base:
430            raise TypeError
431           
432        Action.__init__(self, G, S, True, operator.mul)
433
434    cdef Element _call_c_impl(self, Element g, Element a):
435        if self.connecting is not None:
436            g = self.connecting._call_c(g)
437        if self.extended_base is not None:
438            a = self.extended_base(a)
439        return (<ModuleElement>a)._rmul_c(g)  # a * g
440       
441    def _repr_name_(self):
442        return "scalar multiplication"
443
444       
445cdef class RightModuleAction(Action):
446    def __init__(self, G, S):
447        # Objects are implemented with the assumption that
448        # _lmul_ is given an element of the basering
449        if G is not S.base() and S.base() is not S:
450            self.connecting = S.base().coerce_map_from(G)
451            if self.connecting is None:
452                if not G.has_coerce_map_from(S) and not S.has_coerce_map_from(G):
453                    Z = G.base_extend_canonical_sym(S.base())
454                    if Z is not None:
455                        try:
456                            G.base_extend_canonical_sym(S)
457                        except TypeError, err:
458                            if err.message == "Ambiguous base extension": # TODO: detect this better
459                                raise
460                        self.connecting = Z.coerce_map_from(G)
461                        self.extended_base = S.base_extend(Z)
462                else:
463                    raise TypeError, "actor must be coercable into the basering"
464
465        # TODO: detect this better
466        # if this is bad it will raise a type error in the subsequent lines, which we propagate
467        cdef RingElement g = G._an_element()
468        cdef ModuleElement a = S._an_element()
469        res = self._call_c(a, g)
470
471        if parent_c(res) is not S and parent_c(res) is not self.extended_base:
472            raise TypeError
473           
474        Action.__init__(self, G, S, False, operator.mul)
475       
476    cdef Element _call_c_impl(self, Element a, Element g):
477        if self.connecting is not None:
478            g = self.connecting._call_c(g)
479        if self.extended_base is not None:
480            a = self.extended_base(a)
481        return (<ModuleElement>a)._lmul_c(g)  # a * g
482       
483    def _repr_name_(self):
484        return "scalar multiplication"
Note: See TracBrowser for help on using the repository browser.