Coverage for /usr/lib/python3/dist-packages/sympy/core/operations.py: 37%
309 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1from __future__ import annotations
2from operator import attrgetter
3from collections import defaultdict
5from sympy.utilities.exceptions import sympy_deprecation_warning
7from .sympify import _sympify as _sympify_, sympify
8from .basic import Basic
9from .cache import cacheit
10from .sorting import ordered
11from .logic import fuzzy_and
12from .parameters import global_parameters
13from sympy.utilities.iterables import sift
14from sympy.multipledispatch.dispatcher import (Dispatcher,
15 ambiguity_register_error_ignore_dup,
16 str_signature, RaiseNotImplementedError)
19class AssocOp(Basic):
20 """ Associative operations, can separate noncommutative and
21 commutative parts.
23 (a op b) op c == a op (b op c) == a op b op c.
25 Base class for Add and Mul.
27 This is an abstract base class, concrete derived classes must define
28 the attribute `identity`.
30 .. deprecated:: 1.7
32 Using arguments that aren't subclasses of :class:`~.Expr` in core
33 operators (:class:`~.Mul`, :class:`~.Add`, and :class:`~.Pow`) is
34 deprecated. See :ref:`non-expr-args-deprecated` for details.
36 Parameters
37 ==========
39 *args :
40 Arguments which are operated
42 evaluate : bool, optional
43 Evaluate the operation. If not passed, refer to ``global_parameters.evaluate``.
44 """
46 # for performance reason, we don't let is_commutative go to assumptions,
47 # and keep it right here
48 __slots__: tuple[str, ...] = ('is_commutative',)
50 _args_type: type[Basic] | None = None
52 @cacheit
53 def __new__(cls, *args, evaluate=None, _sympify=True):
54 # Allow faster processing by passing ``_sympify=False``, if all arguments
55 # are already sympified.
56 if _sympify:
57 args = list(map(_sympify_, args))
59 # Disallow non-Expr args in Add/Mul
60 typ = cls._args_type
61 if typ is not None:
62 from .relational import Relational
63 if any(isinstance(arg, Relational) for arg in args):
64 raise TypeError("Relational cannot be used in %s" % cls.__name__)
66 # This should raise TypeError once deprecation period is over:
67 for arg in args:
68 if not isinstance(arg, typ):
69 sympy_deprecation_warning(
70 f"""
72Using non-Expr arguments in {cls.__name__} is deprecated (in this case, one of
73the arguments has type {type(arg).__name__!r}).
75If you really did intend to use a multiplication or addition operation with
76this object, use the * or + operator instead.
78 """,
79 deprecated_since_version="1.7",
80 active_deprecations_target="non-expr-args-deprecated",
81 stacklevel=4,
82 )
84 if evaluate is None:
85 evaluate = global_parameters.evaluate
86 if not evaluate:
87 obj = cls._from_args(args)
88 obj = cls._exec_constructor_postprocessors(obj)
89 return obj
91 args = [a for a in args if a is not cls.identity]
93 if len(args) == 0:
94 return cls.identity
95 if len(args) == 1:
96 return args[0]
98 c_part, nc_part, order_symbols = cls.flatten(args)
99 is_commutative = not nc_part
100 obj = cls._from_args(c_part + nc_part, is_commutative)
101 obj = cls._exec_constructor_postprocessors(obj)
103 if order_symbols is not None:
104 from sympy.series.order import Order
105 return Order(obj, *order_symbols)
106 return obj
108 @classmethod
109 def _from_args(cls, args, is_commutative=None):
110 """Create new instance with already-processed args.
111 If the args are not in canonical order, then a non-canonical
112 result will be returned, so use with caution. The order of
113 args may change if the sign of the args is changed."""
114 if len(args) == 0:
115 return cls.identity
116 elif len(args) == 1:
117 return args[0]
119 obj = super().__new__(cls, *args)
120 if is_commutative is None:
121 is_commutative = fuzzy_and(a.is_commutative for a in args)
122 obj.is_commutative = is_commutative
123 return obj
125 def _new_rawargs(self, *args, reeval=True, **kwargs):
126 """Create new instance of own class with args exactly as provided by
127 caller but returning the self class identity if args is empty.
129 Examples
130 ========
132 This is handy when we want to optimize things, e.g.
134 >>> from sympy import Mul, S
135 >>> from sympy.abc import x, y
136 >>> e = Mul(3, x, y)
137 >>> e.args
138 (3, x, y)
139 >>> Mul(*e.args[1:])
140 x*y
141 >>> e._new_rawargs(*e.args[1:]) # the same as above, but faster
142 x*y
144 Note: use this with caution. There is no checking of arguments at
145 all. This is best used when you are rebuilding an Add or Mul after
146 simply removing one or more args. If, for example, modifications,
147 result in extra 1s being inserted they will show up in the result:
149 >>> m = (x*y)._new_rawargs(S.One, x); m
150 1*x
151 >>> m == x
152 False
153 >>> m.is_Mul
154 True
156 Another issue to be aware of is that the commutativity of the result
157 is based on the commutativity of self. If you are rebuilding the
158 terms that came from a commutative object then there will be no
159 problem, but if self was non-commutative then what you are
160 rebuilding may now be commutative.
162 Although this routine tries to do as little as possible with the
163 input, getting the commutativity right is important, so this level
164 of safety is enforced: commutativity will always be recomputed if
165 self is non-commutative and kwarg `reeval=False` has not been
166 passed.
167 """
168 if reeval and self.is_commutative is False:
169 is_commutative = None
170 else:
171 is_commutative = self.is_commutative
172 return self._from_args(args, is_commutative)
174 @classmethod
175 def flatten(cls, seq):
176 """Return seq so that none of the elements are of type `cls`. This is
177 the vanilla routine that will be used if a class derived from AssocOp
178 does not define its own flatten routine."""
179 # apply associativity, no commutativity property is used
180 new_seq = []
181 while seq:
182 o = seq.pop()
183 if o.__class__ is cls: # classes must match exactly
184 seq.extend(o.args)
185 else:
186 new_seq.append(o)
187 new_seq.reverse()
189 # c_part, nc_part, order_symbols
190 return [], new_seq, None
192 def _matches_commutative(self, expr, repl_dict=None, old=False):
193 """
194 Matches Add/Mul "pattern" to an expression "expr".
196 repl_dict ... a dictionary of (wild: expression) pairs, that get
197 returned with the results
199 This function is the main workhorse for Add/Mul.
201 Examples
202 ========
204 >>> from sympy import symbols, Wild, sin
205 >>> a = Wild("a")
206 >>> b = Wild("b")
207 >>> c = Wild("c")
208 >>> x, y, z = symbols("x y z")
209 >>> (a+sin(b)*c)._matches_commutative(x+sin(y)*z)
210 {a_: x, b_: y, c_: z}
212 In the example above, "a+sin(b)*c" is the pattern, and "x+sin(y)*z" is
213 the expression.
215 The repl_dict contains parts that were already matched. For example
216 here:
218 >>> (x+sin(b)*c)._matches_commutative(x+sin(y)*z, repl_dict={a: x})
219 {a_: x, b_: y, c_: z}
221 the only function of the repl_dict is to return it in the
222 result, e.g. if you omit it:
224 >>> (x+sin(b)*c)._matches_commutative(x+sin(y)*z)
225 {b_: y, c_: z}
227 the "a: x" is not returned in the result, but otherwise it is
228 equivalent.
230 """
231 from .function import _coeff_isneg
232 # make sure expr is Expr if pattern is Expr
233 from .expr import Expr
234 if isinstance(self, Expr) and not isinstance(expr, Expr):
235 return None
237 if repl_dict is None:
238 repl_dict = {}
240 # handle simple patterns
241 if self == expr:
242 return repl_dict
244 d = self._matches_simple(expr, repl_dict)
245 if d is not None:
246 return d
248 # eliminate exact part from pattern: (2+a+w1+w2).matches(expr) -> (w1+w2).matches(expr-a-2)
249 from .function import WildFunction
250 from .symbol import Wild
251 wild_part, exact_part = sift(self.args, lambda p:
252 p.has(Wild, WildFunction) and not expr.has(p),
253 binary=True)
254 if not exact_part:
255 wild_part = list(ordered(wild_part))
256 if self.is_Add:
257 # in addition to normal ordered keys, impose
258 # sorting on Muls with leading Number to put
259 # them in order
260 wild_part = sorted(wild_part, key=lambda x:
261 x.args[0] if x.is_Mul and x.args[0].is_Number else
262 0)
263 else:
264 exact = self._new_rawargs(*exact_part)
265 free = expr.free_symbols
266 if free and (exact.free_symbols - free):
267 # there are symbols in the exact part that are not
268 # in the expr; but if there are no free symbols, let
269 # the matching continue
270 return None
271 newexpr = self._combine_inverse(expr, exact)
272 if not old and (expr.is_Add or expr.is_Mul):
273 check = newexpr
274 if _coeff_isneg(check):
275 check = -check
276 if check.count_ops() > expr.count_ops():
277 return None
278 newpattern = self._new_rawargs(*wild_part)
279 return newpattern.matches(newexpr, repl_dict)
281 # now to real work ;)
282 i = 0
283 saw = set()
284 while expr not in saw:
285 saw.add(expr)
286 args = tuple(ordered(self.make_args(expr)))
287 if self.is_Add and expr.is_Add:
288 # in addition to normal ordered keys, impose
289 # sorting on Muls with leading Number to put
290 # them in order
291 args = tuple(sorted(args, key=lambda x:
292 x.args[0] if x.is_Mul and x.args[0].is_Number else
293 0))
294 expr_list = (self.identity,) + args
295 for last_op in reversed(expr_list):
296 for w in reversed(wild_part):
297 d1 = w.matches(last_op, repl_dict)
298 if d1 is not None:
299 d2 = self.xreplace(d1).matches(expr, d1)
300 if d2 is not None:
301 return d2
303 if i == 0:
304 if self.is_Mul:
305 # make e**i look like Mul
306 if expr.is_Pow and expr.exp.is_Integer:
307 from .mul import Mul
308 if expr.exp > 0:
309 expr = Mul(*[expr.base, expr.base**(expr.exp - 1)], evaluate=False)
310 else:
311 expr = Mul(*[1/expr.base, expr.base**(expr.exp + 1)], evaluate=False)
312 i += 1
313 continue
315 elif self.is_Add:
316 # make i*e look like Add
317 c, e = expr.as_coeff_Mul()
318 if abs(c) > 1:
319 from .add import Add
320 if c > 0:
321 expr = Add(*[e, (c - 1)*e], evaluate=False)
322 else:
323 expr = Add(*[-e, (c + 1)*e], evaluate=False)
324 i += 1
325 continue
327 # try collection on non-Wild symbols
328 from sympy.simplify.radsimp import collect
329 was = expr
330 did = set()
331 for w in reversed(wild_part):
332 c, w = w.as_coeff_mul(Wild)
333 free = c.free_symbols - did
334 if free:
335 did.update(free)
336 expr = collect(expr, free)
337 if expr != was:
338 i += 0
339 continue
341 break # if we didn't continue, there is nothing more to do
343 return
345 def _has_matcher(self):
346 """Helper for .has() that checks for containment of
347 subexpressions within an expr by using sets of args
348 of similar nodes, e.g. x + 1 in x + y + 1 checks
349 to see that {x, 1} & {x, y, 1} == {x, 1}
350 """
351 def _ncsplit(expr):
352 # this is not the same as args_cnc because here
353 # we don't assume expr is a Mul -- hence deal with args --
354 # and always return a set.
355 cpart, ncpart = sift(expr.args,
356 lambda arg: arg.is_commutative is True, binary=True)
357 return set(cpart), ncpart
359 c, nc = _ncsplit(self)
360 cls = self.__class__
362 def is_in(expr):
363 if isinstance(expr, cls):
364 if expr == self:
365 return True
366 _c, _nc = _ncsplit(expr)
367 if (c & _c) == c:
368 if not nc:
369 return True
370 elif len(nc) <= len(_nc):
371 for i in range(len(_nc) - len(nc) + 1):
372 if _nc[i:i + len(nc)] == nc:
373 return True
374 return False
375 return is_in
377 def _eval_evalf(self, prec):
378 """
379 Evaluate the parts of self that are numbers; if the whole thing
380 was a number with no functions it would have been evaluated, but
381 it wasn't so we must judiciously extract the numbers and reconstruct
382 the object. This is *not* simply replacing numbers with evaluated
383 numbers. Numbers should be handled in the largest pure-number
384 expression as possible. So the code below separates ``self`` into
385 number and non-number parts and evaluates the number parts and
386 walks the args of the non-number part recursively (doing the same
387 thing).
388 """
389 from .add import Add
390 from .mul import Mul
391 from .symbol import Symbol
392 from .function import AppliedUndef
393 if isinstance(self, (Mul, Add)):
394 x, tail = self.as_independent(Symbol, AppliedUndef)
395 # if x is an AssocOp Function then the _evalf below will
396 # call _eval_evalf (here) so we must break the recursion
397 if not (tail is self.identity or
398 isinstance(x, AssocOp) and x.is_Function or
399 x is self.identity and isinstance(tail, AssocOp)):
400 # here, we have a number so we just call to _evalf with prec;
401 # prec is not the same as n, it is the binary precision so
402 # that's why we don't call to evalf.
403 x = x._evalf(prec) if x is not self.identity else self.identity
404 args = []
405 tail_args = tuple(self.func.make_args(tail))
406 for a in tail_args:
407 # here we call to _eval_evalf since we don't know what we
408 # are dealing with and all other _eval_evalf routines should
409 # be doing the same thing (i.e. taking binary prec and
410 # finding the evalf-able args)
411 newa = a._eval_evalf(prec)
412 if newa is None:
413 args.append(a)
414 else:
415 args.append(newa)
416 return self.func(x, *args)
418 # this is the same as above, but there were no pure-number args to
419 # deal with
420 args = []
421 for a in self.args:
422 newa = a._eval_evalf(prec)
423 if newa is None:
424 args.append(a)
425 else:
426 args.append(newa)
427 return self.func(*args)
429 @classmethod
430 def make_args(cls, expr):
431 """
432 Return a sequence of elements `args` such that cls(*args) == expr
434 Examples
435 ========
437 >>> from sympy import Symbol, Mul, Add
438 >>> x, y = map(Symbol, 'xy')
440 >>> Mul.make_args(x*y)
441 (x, y)
442 >>> Add.make_args(x*y)
443 (x*y,)
444 >>> set(Add.make_args(x*y + y)) == set([y, x*y])
445 True
447 """
448 if isinstance(expr, cls):
449 return expr.args
450 else:
451 return (sympify(expr),)
453 def doit(self, **hints):
454 if hints.get('deep', True):
455 terms = [term.doit(**hints) for term in self.args]
456 else:
457 terms = self.args
458 return self.func(*terms, evaluate=True)
460class ShortCircuit(Exception):
461 pass
464class LatticeOp(AssocOp):
465 """
466 Join/meet operations of an algebraic lattice[1].
468 Explanation
469 ===========
471 These binary operations are associative (op(op(a, b), c) = op(a, op(b, c))),
472 commutative (op(a, b) = op(b, a)) and idempotent (op(a, a) = op(a) = a).
473 Common examples are AND, OR, Union, Intersection, max or min. They have an
474 identity element (op(identity, a) = a) and an absorbing element
475 conventionally called zero (op(zero, a) = zero).
477 This is an abstract base class, concrete derived classes must declare
478 attributes zero and identity. All defining properties are then respected.
480 Examples
481 ========
483 >>> from sympy import Integer
484 >>> from sympy.core.operations import LatticeOp
485 >>> class my_join(LatticeOp):
486 ... zero = Integer(0)
487 ... identity = Integer(1)
488 >>> my_join(2, 3) == my_join(3, 2)
489 True
490 >>> my_join(2, my_join(3, 4)) == my_join(2, 3, 4)
491 True
492 >>> my_join(0, 1, 4, 2, 3, 4)
493 0
494 >>> my_join(1, 2)
495 2
497 References
498 ==========
500 .. [1] https://en.wikipedia.org/wiki/Lattice_%28order%29
501 """
503 is_commutative = True
505 def __new__(cls, *args, **options):
506 args = (_sympify_(arg) for arg in args)
508 try:
509 # /!\ args is a generator and _new_args_filter
510 # must be careful to handle as such; this
511 # is done so short-circuiting can be done
512 # without having to sympify all values
513 _args = frozenset(cls._new_args_filter(args))
514 except ShortCircuit:
515 return sympify(cls.zero)
516 if not _args:
517 return sympify(cls.identity)
518 elif len(_args) == 1:
519 return set(_args).pop()
520 else:
521 # XXX in almost every other case for __new__, *_args is
522 # passed along, but the expectation here is for _args
523 obj = super(AssocOp, cls).__new__(cls, *ordered(_args))
524 obj._argset = _args
525 return obj
527 @classmethod
528 def _new_args_filter(cls, arg_sequence, call_cls=None):
529 """Generator filtering args"""
530 ncls = call_cls or cls
531 for arg in arg_sequence:
532 if arg == ncls.zero:
533 raise ShortCircuit(arg)
534 elif arg == ncls.identity:
535 continue
536 elif arg.func == ncls:
537 yield from arg.args
538 else:
539 yield arg
541 @classmethod
542 def make_args(cls, expr):
543 """
544 Return a set of args such that cls(*arg_set) == expr.
545 """
546 if isinstance(expr, cls):
547 return expr._argset
548 else:
549 return frozenset([sympify(expr)])
551 @staticmethod
552 def _compare_pretty(a, b):
553 return (str(a) > str(b)) - (str(a) < str(b))
556class AssocOpDispatcher:
557 """
558 Handler dispatcher for associative operators
560 .. notes::
561 This approach is experimental, and can be replaced or deleted in the future.
562 See https://github.com/sympy/sympy/pull/19463.
564 Explanation
565 ===========
567 If arguments of different types are passed, the classes which handle the operation for each type
568 are collected. Then, a class which performs the operation is selected by recursive binary dispatching.
569 Dispatching relation can be registered by ``register_handlerclass`` method.
571 Priority registration is unordered. You cannot make ``A*B`` and ``B*A`` refer to
572 different handler classes. All logic dealing with the order of arguments must be implemented
573 in the handler class.
575 Examples
576 ========
578 >>> from sympy import Add, Expr, Symbol
579 >>> from sympy.core.add import add
581 >>> class NewExpr(Expr):
582 ... @property
583 ... def _add_handler(self):
584 ... return NewAdd
585 >>> class NewAdd(NewExpr, Add):
586 ... pass
587 >>> add.register_handlerclass((Add, NewAdd), NewAdd)
589 >>> a, b = Symbol('a'), NewExpr()
590 >>> add(a, b) == NewAdd(a, b)
591 True
593 """
594 def __init__(self, name, doc=None):
595 self.name = name
596 self.doc = doc
597 self.handlerattr = "_%s_handler" % name
598 self._handlergetter = attrgetter(self.handlerattr)
599 self._dispatcher = Dispatcher(name)
601 def __repr__(self):
602 return "<dispatched %s>" % self.name
604 def register_handlerclass(self, classes, typ, on_ambiguity=ambiguity_register_error_ignore_dup):
605 """
606 Register the handler class for two classes, in both straight and reversed order.
608 Paramteters
609 ===========
611 classes : tuple of two types
612 Classes who are compared with each other.
614 typ:
615 Class which is registered to represent *cls1* and *cls2*.
616 Handler method of *self* must be implemented in this class.
617 """
618 if not len(classes) == 2:
619 raise RuntimeError(
620 "Only binary dispatch is supported, but got %s types: <%s>." % (
621 len(classes), str_signature(classes)
622 ))
623 if len(set(classes)) == 1:
624 raise RuntimeError(
625 "Duplicate types <%s> cannot be dispatched." % str_signature(classes)
626 )
627 self._dispatcher.add(tuple(classes), typ, on_ambiguity=on_ambiguity)
628 self._dispatcher.add(tuple(reversed(classes)), typ, on_ambiguity=on_ambiguity)
630 @cacheit
631 def __call__(self, *args, _sympify=True, **kwargs):
632 """
633 Parameters
634 ==========
636 *args :
637 Arguments which are operated
638 """
639 if _sympify:
640 args = tuple(map(_sympify_, args))
641 handlers = frozenset(map(self._handlergetter, args))
643 # no need to sympify again
644 return self.dispatch(handlers)(*args, _sympify=False, **kwargs)
646 @cacheit
647 def dispatch(self, handlers):
648 """
649 Select the handler class, and return its handler method.
650 """
652 # Quick exit for the case where all handlers are same
653 if len(handlers) == 1:
654 h, = handlers
655 if not isinstance(h, type):
656 raise RuntimeError("Handler {!r} is not a type.".format(h))
657 return h
659 # Recursively select with registered binary priority
660 for i, typ in enumerate(handlers):
662 if not isinstance(typ, type):
663 raise RuntimeError("Handler {!r} is not a type.".format(typ))
665 if i == 0:
666 handler = typ
667 else:
668 prev_handler = handler
669 handler = self._dispatcher.dispatch(prev_handler, typ)
671 if not isinstance(handler, type):
672 raise RuntimeError(
673 "Dispatcher for {!r} and {!r} must return a type, but got {!r}".format(
674 prev_handler, typ, handler
675 ))
677 # return handler class
678 return handler
680 @property
681 def __doc__(self):
682 docs = [
683 "Multiply dispatched associative operator: %s" % self.name,
684 "Note that support for this is experimental, see the docs for :class:`AssocOpDispatcher` for details"
685 ]
687 if self.doc:
688 docs.append(self.doc)
690 s = "Registered handler classes\n"
691 s += '=' * len(s)
692 docs.append(s)
694 amb_sigs = []
696 typ_sigs = defaultdict(list)
697 for sigs in self._dispatcher.ordering[::-1]:
698 key = self._dispatcher.funcs[sigs]
699 typ_sigs[key].append(sigs)
701 for typ, sigs in typ_sigs.items():
703 sigs_str = ', '.join('<%s>' % str_signature(sig) for sig in sigs)
705 if isinstance(typ, RaiseNotImplementedError):
706 amb_sigs.append(sigs_str)
707 continue
709 s = 'Inputs: %s\n' % sigs_str
710 s += '-' * len(s) + '\n'
711 s += typ.__name__
712 docs.append(s)
714 if amb_sigs:
715 s = "Ambiguous handler classes\n"
716 s += '=' * len(s)
717 docs.append(s)
719 s = '\n'.join(amb_sigs)
720 docs.append(s)
722 return '\n\n'.join(docs)