Recursive comparison with custom comparator throws AssertionError when objects are equal

[Soamid]

Describe the bug
I needed to combine assertion with a custom comparator and recursive comparison of an unordered collection. At first, it worked like a charm, but in a very specific case, it started to fail. I spent hours debugging it and I think I know what causes that problem. In RecursiveComparisonDifferenceCalculator#initDualValuesToCompare() detected dual values are filtered to remove already visited cases. However, the equals() method of DualValue only checks actual and expected values, ignoring fieldLocation (there is a comment there questioning this btw ;) ). As a result, similar dual values created in different locations (e.g. the same object in different collections) are marked as similar and removed. Then, the collection of differences is empty and then compareUnorderedIterables() wrongly assumes it found a match and removes investigated value from its iterator...

• assertj core version: 3.24.2
• java version: 17.0.3
• test framework version: JUnit 5.8.2

Test case reproducing the bug

It sounds a bit complicated so I highly recommend seeing the example code below and running it with a debugger. Ofc it's not my real case, just a minimal example to reproduce the problem.

It will throw AssertionError with the message: The following expected elements were not matched in the actual List12: [pl.edu.agh.mobint.db.application.statistics.phonenumber.Example$DataStore@7331196b]. If you remove the custom comparator, the test passes.

public class Example {

  class DataStore {
    List<Data> store1 = new ArrayList<>();

    List<Data> store2 = new ArrayList<>();
  }

  class Data {
    private String text;

    Data(String text) {
      this.text = text;
    }

    public String getText() {
      return text;
    }

    @Override
    public String toString() {
      return "Data: " + text;
    }
  }

  @Test
  void assertTest() {
    var dataStore1 = createDataStore(true);
    var dataStore2 = createDataStore(false);

    assertThat(List.of(dataStore1)).usingRecursiveComparison(RecursiveComparisonConfiguration.builder()
            .withComparatorForType(Comparator.comparing(Data::getText), Data.class)
            .build())
        .ignoringCollectionOrder()
        .isEqualTo(List.of(dataStore2));
  }

  private DataStore createDataStore(boolean reverse) {
    var data1 = new Data("123");
    var data2 = new Data("456");
    var data3 = new Data("987");

    var dataStore = new DataStore();
    dataStore.store1.addAll(reverse ? List.of(data3, data2, data1) : List.of(data1, data2, data3));
    dataStore.store2.addAll(reverse ? List.of(data3, data2) : List.of(data2, data3));
    return dataStore;
  }
}

[joel-costigliola]

Thanks for reporting this @Soamid

[joel-costigliola]

This one is tricky, as you pointed out the cause is how we deal with visited nodes, we compare them without evaluating the field location to be able to track potential cycles. Take for example a Person class with a neighbor field, it results in a cycle when comparing them: John has Tim as neighbor, Tim has John, but when looking at Tim.neighbor we fall back to John, if we evaluate it we cycle back falling in an infinite recursion.

To detect visited nodes, we compare them by reference, if we check the node location your test succeeds but the cycle detection does not work anymore, the Person example Tim.neighbor refers to John but the location is different from the John root object (location is neighbor)

Your test actually succeeds if we build the datastores object with new instances of data1, data2 and data3 because the visited nodes detection will find the references are different, try this with:

  private static DataStore createDataStore(boolean reverse) {
    DataStore dataStore = new DataStore();
    dataStore.store1.addAll(reverse ? list(new Data("987"), new Data("456"), new Data("123"))
        : list(new Data("123"), new Data("456"), new Data("987")));
    dataStore.store2.addAll(reverse ? list(new Data("987"), new Data("456")) : list(new Data("456"), new Data("987")));
    return dataStore;
  }

Having said that, it would be great to support both your use case and the cycle detection but I'm not sure if this is possible, I need to do think about it more. Comparing unordered collection increases the likeliness of the issue as it requires comparing all elements to all expected elements (cross product) leading to duplicate dual values when both collections share the same elements.

[joel-costigliola]

@Soamid I have found a way to address this issue, basically by caching the diff computed per node so that when the same node is visited again, it returns the diff (this addresses also the potential cycles)
Thanks for the detailed report that was really helpful.

[Soamid]

Oh, that's great. :) Thank you for the investigation! It will be really helpful in my case because I have no control if the objects are copied or only referenced in two places (they are populated by DB framework and I use AssertJ in integration tests to write more complex assertions). Having one object in two collections usually is not a good model design, but that's another story and I have to live with it. :D

[joel-costigliola]

@Soamid It would be great if you could check on your side that this was fixed properly, building assert is fairly straightforward (mvn install should do), then you can use the built snapshot version locally to run the unit tests. If you don't have time and can't it's okay.

The recursive comparison unit tests are a challenge because there is so much to cover, we test individual features on small tests but we can't cover all the possible combination, this is why tests from real projects are super valuable.

[Soamid]

I've checked it today and everything works now, not only on this small example but also in my main project (which is quite complex and I use this assertion in multiple scenarios). I've simply uncommented the assertion and all turned green. Thank you once again and looking forward to the release. :)

[joel-costigliola]

Awesome, appreciate you took the time to test.