recursion error on imported models

[rubenkindt]

CPMpy: version v0.9.9 commit e79b3af

Importing this file works but doing anything with the imported model causes a recursion error.

input.zip

from cpmpy import *

file = "input" # don't forget to unzip
m = Model().from_file(file)
print(m) # m.solve() would cause the same bug.

expected behavior:
Print the model.

Bug found while working on my master thesis.

[JoD]

One part of the issue is that an expression tree gets constructed that contains a cycle (so it is not really a tree). This can lead to lots of issues, the one exhibited here is just printing the expression.

Digging deeper...

[JoD]

Can you please attach the model that was pickled? I.e., how input.zip was generated.

[rubenkindt]

This could be tricky, since I modify an already imported file and once modified It crashes as soon as I touch it. The best I can do is upload the way I found the bug.
metamorphic.zip
You will need to change the folder path in the main, the sport scheduling example will need to be in the example path and the resulting path just need to exist, the bug will be created at that location with the folder name "maximum recursion depth exceeded in instancecheck0" the bug should occur in loop iteration 41.

edits: spelling + I created the zip manually since I can't upload pickle file to GitHub

[JoD]

Thanks for the files! Here is what I get now on b60310d:

41
file 0/1: prob026_sport_scheduling16650537264701257
Crashmaximum recursion depth exceeded in __instancecheck__
None
Traceback (most recent call last):
  File "/home/jod/Downloads/metamorphic/metamorphic.py", line 493, in __main__
    mmodel.modifModel.solve(solver=mmodel.solver, time_limit=timeout)
  File "/home/jod/workspace/cpmpy/cpmpy/model.py", line 137, in solve
    s = SolverLookup.get(solver, self)
  File "/home/jod/workspace/cpmpy/cpmpy/solvers/utils.py", line 104, in get
    return cls(model, subsolver=subname)
  File "/home/jod/workspace/cpmpy/cpmpy/solvers/ortools.py", line 93, in __init__
    super().__init__(name="ortools", cpm_model=cpm_model)
  File "/home/jod/workspace/cpmpy/cpmpy/solvers/solver_interface.py", line 83, in __init__
    self += cpm_model.constraints
  File "/home/jod/workspace/cpmpy/cpmpy/solvers/ortools.py", line 312, in __add__
    self.user_vars.update(get_variables(cpm_con))
  File "/home/jod/workspace/cpmpy/cpmpy/transformations/get_variables.py", line 46, in get_variables
    vars_ += get_variables(subexpr)
  File "/home/jod/workspace/cpmpy/cpmpy/transformations/get_variables.py", line 49, in get_variables
    vars_ += get_variables(subexpr)
  File "/home/jod/workspace/cpmpy/cpmpy/transformations/get_variables.py", line 49, in get_variables
    vars_ += get_variables(subexpr)
  File "/home/jod/workspace/cpmpy/cpmpy/transformations/get_variables.py", line 49, in get_variables
    vars_ += get_variables(subexpr)
  [Previous line repeated 985 more times]
  File "/home/jod/workspace/cpmpy/cpmpy/transformations/get_variables.py", line 44, in get_variables
    if is_any_list(expr):
  File "/home/jod/workspace/cpmpy/cpmpy/expressions/utils.py", line 48, in is_any_list
    return isinstance(arg, (list, tuple, np.ndarray))
RecursionError: maximum recursion depth exceeded in __instancecheck__

During handling of the above exception, another exception occurred:
...

Which is consistent with what you describe. Looking into get_variables.py now...

[JoD]

Allright, think I got to the root of the issue. In attachment you find an adjusted metamorphic.py:
metamorphic_adjusted.zip. Use your favorite diff tool to see the diff.

The root cause are the mutations in the algorithm used to generate fuzzing tests, which may introduce cycles in the expression tree. CPMpy expects expression trees to be acyclic (i.e., they must be trees), an infinite recursion error will happen if they are not. E.g., printing an expression requests to print the arguments of the expression, these print their arguments in turn, etc. But if one of these subarguments was the original expression, we the recursion never finishes.

When running the adjusted metamorphic.py, we get the following output:

x: (away[2,0] == 2) == (BV7045)
y: ((home[4,3] == 4) == (BV8505)) -> (((BV5163) and (BV5164)) == (BV5165))
xr: (b699) != (((home[4,3] == 4) == (BV8505)) -> (((BV5163) and (BV5164)) == (BV5165)))
yr: (b699) != ((away[2,0] == 2) == (BV7045))
[...]

A: home[4,3] == 4 (home[4,3] == 4) == (BV8505)
AA: CRASH

In essence, y is the constraint ((home[4,3] == 4) == (BV8505)) -> (((BV5163) and (BV5164)) == (BV5165)) and xr is (b699) != (((home[4,3] == 4) == (BV8505)) -> (((BV5163) and (BV5164)) == (BV5165))). Looking at the references, we actually have xr is (b699) != y, so xr has y as descendant.

Then A: home[4,3] == 4 (home[4,3] == 4) == (BV8505) means we will replace home[4,3] == 4 in (presumably) y with xr. So then y will have xr as descendant, creating the expression loop, and creating the crash when printing the AA line.

[JoD]

So, right now, I think the issue is not in CPMpy, but in the mutations used to generate fuzzing tests. I'm not certain what the best fix would be (as these mutations are definitely proving their usefulness!). Maybe check that x/y are terminal expressions (variables, constants, anything without arguments) before doing the # replace some X, Y by xr, yr in semanticFusionBoolBool and semanticFusionIntInt, as then no expression loop should be possible (I think).

[JoD]

@rubenkindt If you agree with the above, then I'll close the issue. In any case, thanks for taking the time to report!