Repository: sympy/sympy

Issue:
RecursionError in gcd for unevaluated Mul func with integer args
Spotted this earlier. I have workaround by just pre-evaluating before running gcd.

```python
>>> import sympy as sp
>>> sp.gcd(sp.Mul(2, 3, evaluate=False), 2)
---------------------------------------------------------------------------
PolificationFailed                        Traceback (most recent call last)
.../.venv/lib/python3.7/site-packages/sympy/polys/polytools.py in gcd(f, g, *gens, **args)
   5277     try:
-> 5278         (F, G), opt = parallel_poly_from_expr((f, g), *gens, **args)
   5279 

.../.venv/lib/python3.7/site-packages/sympy/polys/polytools.py in parallel_poly_from_expr(exprs, *gens, **args)
   4311     opt = options.build_options(gens, args)
-> 4312     return _parallel_poly_from_expr(exprs, opt)
   4313 

.../.venv/lib/python3.7/site-packages/sympy/polys/polytools.py in _parallel_poly_from_expr(exprs, opt)
   4366     if not opt.gens:
-> 4367         raise PolificationFailed(opt, origs, exprs, True)
   4368 

PolificationFailed: can't construct polynomials from 2*3, 2

During handling of the above exception, another exception occurred:

<stack repeats then eventually...>

RecursionError: maximum recursion depth exceeded
```

Using another operator works fine:

```python
>>> sp.gcd(sp.Pow(2, 3, evaluate=False), 2)
2
```

Discussion:
sympy-bot: :white_check_mark:

Hi, I am the [SymPy bot](https://github.com/sympy/sympy-bot) (v161). I'm here to help you write a release notes entry. Please read the [guide on how to write release notes](https://github.com/sympy/sympy/wiki/Writing-Release-Notes).



Your release notes are in good order.

Here is what the release notes will look like:
* core
  * gcd correctly handles unevaluated Mul containing only integers ([#20700](https://github.com/sympy/sympy/pull/20700) by [@AaronStiff](https://github.com/AaronStiff))

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.8.

<details><summary>Click here to see the pull request description that was parsed.</summary>

    <!-- Your title above should be a short description of what
    was changed. Do not include the issue number in the title. -->

    #### References to other Issues or PRs
    Fixes #20597 
    <!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
    format, e.g. "Fixes #1234" (see
    https://tinyurl.com/auto-closing for more information). Also, please
    write a comment on that issue linking back to this pull request once it is
    open. -->


    #### Brief description of what is fixed or changed
    `gcd` was not functioning correctly when given an unevaluated `Mul` containing only Integers. Added a line to handle these cases specifically.

    #### Other comments
    Similar behavior was observed with an unevaluated `Add` containing only Integers, but unlike `Mul`, there is no `_eval_expand_[hint]` to modify. Perhaps this would have to be added?

    #### Release Notes

    <!-- Write the release notes for this release below. See
    https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more information
    on how to write release notes. The bot will check your release notes
    automatically to see if they are formatted correctly. -->

    <!-- BEGIN RELEASE NOTES -->
    * core
       * gcd correctly handles unevaluated Mul containing only integers
    <!-- END RELEASE NOTES -->

</details><p>

oscarbenjamin: This fix should have an associated unit test which could go in `sympy/core/tests/test_expand.py`.

The OP says that this fixes #20597 which would mean that the issue would be closed if this was merged. However this does not completely fix the issue because there is still the same problem with unevaluated `Add` so the issue should not be closed unless further changes are made to this PR to address those problems as well.

Further commits can be pushed to this PR to address these points. If the intention is only to fix the issue for `Mul` then that is fine but the OP should be edited so that it does not say `Fixes #20597`.
AaronStiff: Oh sorry about that. I've removed the issue reference. Is a unit test still required for this partial fix? If so, are there unit test guidelines you could point me to?
oscarbenjamin: Unit tests are always required. I just looked at the dev guide and I'm not sure we have anything about writing tests... There are plenty of examples to look at though.

The tests for this PR on Github Actions have already shown a couple of failures which should be looked into. It might be possible just to change the tests if the new output is equivalent or it might indicate a problem with the change here.

That's why tests are useful!
AaronStiff: Agreed! 😁 I'll have to look into why they failed.

If I add a test on my fork, will I be able to add it on to this pull request?
oscarbenjamin: Yes. If you make a new commit on the same branch and push it to your fork on github then the pull request will automatically update with the changes.
AaronStiff: Great. Thanks again. I really appreciate all the help for what is literally my first pull request. 😃 

I verified the new test by hand so I'm fairly confident it's correct. Are the GitHub Action tests viewable so as to investigate where they failed?
naveensaigit: Yes, you can click on "Details" in the Checks section to view the run of each test. The following doctests have failed -
``` python
File "/home/runner/work/sympy/sympy/sympy/polys/polytools.py", line 6191, in
sympy.polys.polytools._torational_factor_list
Failed example:
    factors = _torational_factor_list(p, x); factors
Expected:
    (-2, [(-x*(1 + sqrt(2))/2 + 1, 1), (-x*(1 + sqrt(2)) - 1, 1), (-x*(1 + sqrt(2)) + 1, 1)])
Got:
    (-2, [(-2*x*(1 - sqrt(2)) + 1, 1), (-4*x*(1 - sqrt(2)) - 1, 1), (-4*x*(1 - sqrt(2)) + 1, 1)])
```
``` python
File "/home/runner/work/sympy/sympy/sympy/polys/polytools.py", line 6193, in
sympy.polys.polytools._torational_factor_list
Failed example:
    expand(factors[0]*Mul(*[z[0] for z in factors[1]])) == p
Expected:
    True
Got:
    False
```
``` python
File "/home/runner/work/sympy/sympy/sympy/polys/polytools.py", line 6079, in
sympy.polys.polytools.to_rational_coeffs
Failed example:
    Poly(lc*r**3*(g.as_expr()).subs({x:x*r1}), x, domain='EX') == p
Expected:
    True
Got:
    False
```
The following tests have failed -
``` python
_ sympy/solvers/ode/tests/test_systems.py:test_sysode_linear_neq_order1_type2 __
Traceback (most recent call last):
  File "/home/runner/work/sympy/sympy/sympy/solvers/ode/tests/test_systems.py", line 1161, in
test_sysode_linear_neq_order1_type2
    assert dsolve(eq13) == sol13
AssertionError
```
``` python
_ sympy/solvers/ode/tests/test_systems.py:test_sysode_linear_neq_order1_type3 __
Traceback (most recent call last):
  File "/home/runner/work/sympy/sympy/sympy/solvers/ode/tests/test_systems.py", line 1286, in
test_sysode_linear_neq_order1_type3
    assert dsolve(eqs2) == sol2
AssertionError
```
oscarbenjamin: I think that this could also fix #20715 which I think is the same issue.

We should see that it does and if so a regression test should be added for that case as well.
oscarbenjamin: I tried the following diff and it seems to pass the tests that apparently failed before:
```diff
diff --git a/sympy/core/mul.py b/sympy/core/mul.py
index 531770aa75..279a364093 100644
--- a/sympy/core/mul.py
+++ b/sympy/core/mul.py
@@ -869,9 +869,9 @@ def _eval_expand_mul(self, **hints):
         if d.is_Mul:
             n, d = [i._eval_expand_mul(**hints) if i.is_Mul else i
                 for i in (n, d)]
-            expr = n/d
-            if not expr.is_Mul:
-                return expr
+        expr = n/d
+        if not expr.is_Mul:
+            return expr
 
         plain, sums, rewrite = [], [], False
         for factor in expr.args:
```
AaronStiff: I see. So instead of checking if the denominator is 1, which breaks unevaluated expressions with fractions, it's checking instead if the expression is not a `Mul` and thus expanded properly. So 2 questions:

1. I've seen a couple of people mention that they made a change which passed the tests. How do I run the tests without creating a pull request and having the tests run automatically? Or is that only for users with higher privileges
2. Should I modify the pull request with this edit?
oscarbenjamin: Yes, I think let's try that edit and see if it fixes all the issues.

To run the tests yourself you can either use the `bin/test` testing script or install `pytest`. They work in similar ways but I prefer pytest personally.

With pytest you can run the tests like:
```
$ pytest   # runs all tests. extremely slow
$ pytest -m 'not slow'  # skips the slow tests but still takes maybe an hour
$ pytest sympy/solvers  -m 'not slow'  # all not slow tests in the sympy/solvers directory
```
More importantly you can run a precise test such as the ones that failed with e.g.:
```
$ pytest sympy/solvers/ode/tests/test_systems.py::test_sysode_linear_neq_order1_type3
```
There are many other options when running pytest (see the pytest docs).

You can also just look at the code for the test that failed and run it directly. The test failure should show both the filename and the name of the test function and the line on which it failed.
AaronStiff: Thanks so much Oscar. I really appreciate the information. I'll update the PR shortly.
oscarbenjamin: It shouldn't be necessary to keep merging in master like this. The tests had passed before and there were no conflicts.
AaronStiff: Oh okay. I was still getting a RecursionError testing #20715 so I thought I wasn't up to date with the changes made there. For some reason I'm getting the AttributeError or ValueError you were reporting now.
oscarbenjamin: Oh, actually that is a good reason for merging in master.
oscarbenjamin: Looks like #20715 is more complicated than I thought.

If you add a test for the original issue with `gcd` then this can be merged.
oscarbenjamin: This just needs a test for gcd as in the original issue.
AaronStiff: Oh I see. I thought you were referring to just the `expand` issue. Where should I put the `gcd` test?
oscarbenjamin: I think it should go in `sympy/polys/tests/test_polytools.py`.
oscarbenjamin: I thought this might lead to slowdowns in expand but I ran the benchmarks and they don't show a significant change.

I think this looks good but I think that the commits should be squashed. You can do that by running the commands below but first *save your work*. Make sure you have a copy of the changes you have made outside of git because it's easy to mess this up.

This is how to squash the commits. First checkout this branch and make sure the working directory is clean (no output from `git diff`). Make sure your master branch is up to date with sympy and then:
```
git merge master
git diff master > t.diff
git reset --hard HEAD^100  # This deletes the last 100 commits including all your work!
git pull master
# Reapply the changes and commit:
git apply t.diff
git commit ...
# Force push to change history:
git push --force
```
AaronStiff: So be to super clear, my local master and my remote master should both be in sync with the sympy master, and then I should checkout this issue branch, and then perform the commands?
oscarbenjamin: Yes, that's right. Actually the way I do this is that I have a remote called "upstream" which refers to the main sympy repo so I would start the above with `git fetch upstream` and then use `upstream/master` in place of `master` in the above commands.
oscarbenjamin: The idea is to squash this to a single commit with a clear commit message like:
```
fix(core): handle unevaluated Mul in expand
```

Patch:
diff --git a/sympy/core/mul.py b/sympy/core/mul.py
index 472fc377c0..193f43c00f 100644
--- a/sympy/core/mul.py
+++ b/sympy/core/mul.py
@@ -937,9 +937,9 @@ def _eval_expand_mul(self, **hints):
         if d.is_Mul:
             n, d = [i._eval_expand_mul(**hints) if i.is_Mul else i
                 for i in (n, d)]
-            expr = n/d
-            if not expr.is_Mul:
-                return expr
+        expr = n/d
+        if not expr.is_Mul:
+            return expr
 
         plain, sums, rewrite = [], [], False
         for factor in expr.args:


Test patch:
diff --git a/sympy/core/tests/test_expand.py b/sympy/core/tests/test_expand.py
index f39d250784..087ea89b7a 100644
--- a/sympy/core/tests/test_expand.py
+++ b/sympy/core/tests/test_expand.py
@@ -230,6 +230,15 @@ def test_expand_arit():
     W = W.expand()
     assert W.has(-1672280820*x**15)
 
+def test_expand_mul():
+    # part of issue 20597
+    e = Mul(2, 3, evaluate=False)
+    assert e.expand() == 6
+
+    e = Mul(2, 3, 1/x, evaluate = False)
+    assert e.expand() == 6/x
+    e = Mul(2, R(1, 3), evaluate=False)
+    assert e.expand() == R(2, 3)
 
 def test_power_expand():
     """Test for Pow.expand()"""
diff --git a/sympy/polys/tests/test_polytools.py b/sympy/polys/tests/test_polytools.py
index cddb69aa46..53d979bce0 100644
--- a/sympy/polys/tests/test_polytools.py
+++ b/sympy/polys/tests/test_polytools.py
@@ -2077,6 +2077,9 @@ def test_gcd_numbers_vs_polys():
     assert gcd(3.0, 9.0) == 1.0
     assert gcd(3.0*x, 9.0) == 1.0
 
+    # partial fix of 20597
+    assert gcd(Mul(2, 3, evaluate=False), 2) == 2
+
 
 def test_terms_gcd():
     assert terms_gcd(1) == 1