Circular references should be handled gracefully by `equals`

[acarstoiu]

Currently, the equals matcher recurses for Maps and Iterables, but in a way that rejects circular references, while they are perfectly valid for certain applications.

The limit argument is a cap on recursive calls and, as simple as it is, it works fine. But the correct handling of circular references is not to recurse, but to compare by ==/identity. So, you should use a Set when walking the data so as to watch for repeated iterables and avoid the silly recursion.

[liamappelbe]

Another possible fix would be to maintain a Map<Object, Object> matched during recursion. The keys are all the objects on the left of the matcher, and the values are the corresponding objects on the right. Then when the matcher is comparing two objects, if the left object is already a key in the map, instead of recursing just check whether the right object matches the corresponding value in the map. This map would replace whatever data structure is currently used to reject circular references (presumably some sort of set of visited objects).

The advantage of this approach is that the self referential objects on the left don't have to be identical to the ones on the right.

[acarstoiu]

The equals matcher applies == for comparison, except for certain structures on which it recurses, If a circular reference is encountered while walking the left data, you want the same structure to be observed on right, namely a similar circular reference.

So, to refine and correct my statement above, here's what needs to be done. While walking in parallel the left and right data, a Map<Object, int> from node to depth level must be maintained for each side. Before any recursion, a circular reference on the left is easy to detect by looking at the left map, from where you get the depth at which the very same node was already encountered. Then you look for the corresponding right node inside the right map, it should be there and have the same depth as the left circular reference, otherwise the process ends immediately with a negative answer.

Your huge Map<Object, Object> matched is in general a waste of memory space and time since it will end up containing all nodes of the structures (the maps I described contain a number of nodes limited by the height of structures). It could be helpful for the case where there are many correspondent node repetitions within the compared structures, but that's certainly irrelevent for a general purpose matcher package.