`RecursionError` when comparing two dictionaries referenced to itself

[vodkar]

Bug report

Bug description:

Is this expected behavior?

d = {}
d["a"] = d
d2 = {}
d2["a"] = d2
d == d2

Error:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded in comparison

CPython versions tested on:

3.12

Operating systems tested on:

macOS

[nineteendo]

Also note that you can reference the other dictionary:

d1 = {}
d2 = {}
d1["a"] = d2
d2["a"] = d1
print(d1 == d2)

[ZeroIntensity]

Well, if you play stupid games with circular references, you win stupid RecursionError prizes 😄

I guess if we really wanted to fix this, we could check the identity first when comparing. Does this have precedent (e.g. does the same thing happen with circular references on list)?

[nineteendo]

Peter, it already checks for identity:

d1, d2 = {}, {}
d1["a"] = d2["a"] = d1
print(d1 == d2) # True

You could link back to an arbitrary ancestor making this somewhat difficult to fix.

[vodkar]

Well, if you play stupid games with circular references, you win stupid RecursionError prizes 😄

Initially, I found this bug report at pydantic: pydantic/pydantic#10630
There is a dict comparison in__eq__, so I made a similar construction in pure python with dictionaries, and I got this error 😄
I was trying to search this problem in issues, but no luck. So I want to check, is this proper behavior?

I guess if we really wanted to fix this, we could check the identity first when comparing. Does this have precedent (e.g. does the same thing happen with circular references on list)?

I can't provide such precedents.
I'm not sure about the following way to check correctness of current logic in Python but I check other programming languages, and this is what I got:

Language	Result
Java	raises StackOverflowError
JavaScript	false
Golang	true

So, I have no idea which logic is correct 🤷‍♂️

[zhangyx1998]

Just being curious: if it does not error out, what result do you expect it to return? True or False?

[terryjreedy]

In the first case, d1 == d2 if and only if d1 == d2. So the answer is indeterminate (not determined). In the C world, this means that any arbitrary answer is considered correct. In Python, guessing is frowned upon, and refusing to answer, by raising, is considered more correct. (This is better than the alternative non-answer of looping forever.) In the second case, d1 == d2 if and only if d2 == d1, which is the same thing. In the particular case of 1 key k, d1 == d2 if and only if (d1 is d2 or d1[k] == d2[k]), where the latter is a condensed and partly checkable form of an infinite proposition d1[k] is d2[k] or d1[k][k] is d2[k][k] or d1[k][k][k] is d2[k][k][k] or ...). I think we can close.

[ZeroIntensity]

Since this did appear in a large library downstream, I want to wait for any extra input before brushing it off as a non-issue.

[terryjreedy]

Raising an exception for buggy code is not a brush-off.

[ZeroIntensity]

Not disagreeing, but it's not exactly helpful to Pydantic :)

I'll deal with communicating with them downstream, thanks for your help!