Repository: sympy/sympy

Issue:
Regression: RecursionError in cse since gh-24303
I got a recursion error after updating SymPy to `master` in a project of mine, I managed to minimize the expression to a minimal reproducer: `cse(-1-UnevaluatedExpr(Symbol('x')+1))`

Here's a shell session identifying gh-24303 as the point of regression (cc @sylee957):
<details>
<summary> <pre>$ git checkout 978de3ace373 </pre> </summary>

```shell-session
HEAD is now at 978de3ace3 Merge pull request #24303 from sylee957/evaluate
$ python -c "from sympy import cse, UnevaluatedExpr, Symbol; print(cse(-1-UnevaluatedExpr(Symbol('x')+1)))"
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/bjorn/vc/sympy/sympy/simplify/cse_main.py", line 824, in cse
    replacements, reduced_exprs = tree_cse(reduced_exprs, symbols, opt_subs,
                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/bjorn/vc/sympy/sympy/simplify/cse_main.py", line 694, in tree_cse
    reduced_e = _rebuild(e)
                ^^^^^^^^^^^
  File "/home/bjorn/vc/sympy/sympy/simplify/cse_main.py", line 668, in _rebuild
    new_args = list(map(_rebuild, args))
               ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/bjorn/vc/sympy/sympy/simplify/cse_main.py", line 668, in _rebuild
    new_args = list(map(_rebuild, args))
               ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/bjorn/vc/sympy/sympy/simplify/cse_main.py", line 668, in _rebuild
    new_args = list(map(_rebuild, args))
               ^^^^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 990 more times]
  File "/home/bjorn/vc/sympy/sympy/simplify/cse_main.py", line 657, in _rebuild
    if c == [1]:
       ^^^^^^^^
  File "/home/bjorn/vc/sympy/sympy/core/numbers.py", line 2243, in __eq__
    return (self.p == other)
            ^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded in comparison
$ git checkout 978de3ace373~1
HEAD is now at c303e9e4d3 Merge pull request #24302 from eagleoflqj/flake8
$ python -c "from sympy import cse, UnevaluatedExpr, Symbol; print(cse(-1-UnevaluatedExpr(Symbol('x')+1)))"
([], [-(1 + (x + 1))])
```

</details>

This might do as a regression test for a future fix (untested of course so no guarantees):
<details>
<summary>Proposed regression test</summary>

```patch
diff --git a/sympy/simplify/tests/test_cse.py b/sympy/simplify/tests/test_cse.py
index df82df3b84..08213f6e47 100644
--- a/sympy/simplify/tests/test_cse.py
+++ b/sympy/simplify/tests/test_cse.py
@@ -5,6 +5,7 @@
 from sympy.codegen.matrix_nodes import MatrixSolve
 from sympy.core.add import Add
 from sympy.core.containers import Tuple
+from sympy.core.expr import UnevaluatedExpr
 from sympy.core.function import Function
 from sympy.core.mul import Mul
 from sympy.core.power import Pow
@@ -534,6 +535,18 @@ def test_cse_ignore_issue_15002():
     rl = [e.subs(reversed(substs)) for e in reduced]
     assert rl == l
 
+
+def test_cse_unevaluated():
+    xp1 = UnevaluatedExpr(x + 1)
+    (x0, ue), red = cse([(-1-xp1)/(1-xp1)])  # this used to cause RecursionError
+    if ue == xp1:
+        assert red == [(-1-x0)/(1-x0)]
+    elif ue == -xp1:
+        assert red == [(-1+x0)/(1+x0)]
+    else:
+        raise ValueError("Unexpected common subexpression found")
+
+
 def test_cse__performance():
     nexprs, nterms = 3, 20
     x = symbols('x:%d' % nterms)
```

</details>

Discussion:

Patch:
diff --git a/sympy/simplify/cse_main.py b/sympy/simplify/cse_main.py
index d603560f59..3b7a2d9665 100644
--- a/sympy/simplify/cse_main.py
+++ b/sympy/simplify/cse_main.py
@@ -512,7 +512,14 @@ def _find_opts(expr):
         list(map(_find_opts, expr.args))
 
         if not isinstance(expr, MatrixExpr) and expr.could_extract_minus_sign():
-            neg_expr = -expr
+            # XXX -expr does not always work rigorously for some expressions
+            # containing UnevaluatedExpr.
+            # https://github.com/sympy/sympy/issues/24818
+            if isinstance(expr, Add):
+                neg_expr = Add(*(-i for i in expr.args))
+            else:
+                neg_expr = -expr
+
             if not neg_expr.is_Atom:
                 opt_subs[expr] = Unevaluated(Mul, (S.NegativeOne, neg_expr))
                 seen_subexp.add(neg_expr)


Test patch:
diff --git a/sympy/simplify/tests/test_cse.py b/sympy/simplify/tests/test_cse.py
index df82df3b84..c2f1c7eccf 100644
--- a/sympy/simplify/tests/test_cse.py
+++ b/sympy/simplify/tests/test_cse.py
@@ -5,6 +5,7 @@
 from sympy.codegen.matrix_nodes import MatrixSolve
 from sympy.core.add import Add
 from sympy.core.containers import Tuple
+from sympy.core.expr import UnevaluatedExpr
 from sympy.core.function import Function
 from sympy.core.mul import Mul
 from sympy.core.power import Pow
@@ -534,6 +535,20 @@ def test_cse_ignore_issue_15002():
     rl = [e.subs(reversed(substs)) for e in reduced]
     assert rl == l
 
+
+def test_cse_unevaluated():
+    xp1 = UnevaluatedExpr(x + 1)
+    # This used to cause RecursionError
+    [(x0, ue)], [red] = cse([(-1 - xp1) / (1 - xp1)])
+    if ue == xp1:
+        assert red == (-1 - x0) / (1 - x0)
+    elif ue == -xp1:
+        assert red == (-1 + x0) / (1 + x0)
+    else:
+        msg = f'Expected common subexpression {xp1} or {-xp1}, instead got {ue}'
+        assert False, msg
+
+
 def test_cse__performance():
     nexprs, nterms = 3, 20
     x = symbols('x:%d' % nterms)