How to diff Lists?

[bartswen]

First of all, thanks for this great library!

I was wondering what is your idea about comparing collections? The DelegatingObjectDifferImpl uses the CollectionDiffer to compare both Sets and Lists. While List order is relevant, the differ does not detect changes in the order of the items.

Consider this code:

List<String> left = Arrays.asList("aaa", "bbb", "ccc");
List<String> right = Arrays.asList("aaa", "ccc", "bbb");
ObjectDiffer objectDiffer = ObjectDifferFactory.getInstance();
final Node root = objectDiffer.compare(left, right);
System.out.println("Equals: " + left.equals(right));
root.visit(new PrintingVisitor(left, right));

Results in:

Equals: false
Property at path '/' has not changed

The items 1 and 2 were swapped so the equals says 'false', but this was not detected as a change. Is this behaviour as intended? I would say that the List deserves a ListDiffer.

[SQiShER]

Thanks for your feedback!

This is a very good question. I'm still looking for a good way, to solve this problem. Currently the library treats Sets and Lists the same on purpose, because it seems to me, as if being aware of the position of List items would require some sort of advanced diffing techniques, similar to those used in textual diff tools. I found a couple of papers detailing those techniques, but currently I'm a little bit too short on time, to study them and cook up a solution. I definitely want to in the near future though.

Maybe I'm missing something and the solution is easier than I think, but currently I don't see it. I wish I could tell you that there is an easy way to achieve your desired behavior, but I'm afraid currently it's just not possible. However, if you think you found a way to make it work, I would be thrilled, if you'd try to implement it yourself! Of course I'll always be here to answer any further questions.

[clubpetey]

I had the same problem a few weeks ago, here's how I solved it: Use the existing functionality for collections (Maps), and treat an Array as a Map with the key equal to the index position. In my case I actually converted it to a map, but that may be a large performance hit in some cases. The output of your example would be:

Property at path '/[2]' has changed [ bbb ] => [ ccc ]
Property at path '/[3]' has changed [ ccc ] => [ bbb ]

One could argue the "right way" would be to notice that indexes 2 and 3 changed positions, however, THAT is rather complicated. And for what I'm doing wasn't required. If you agree with my logic, I can probably put everything together into a push/merge request.

[SQiShER]

Thanks for suggesting this nice workaround! It should actually work pretty well for simple types like primitives or strings. But if the values are complex objects, things get a little bit more complicated: since the map key would determine the identity of the value, the resulting diff wouldn't accurately reflect the changes, which could lead to some serious side-effects.

Lets say we have two name objects walter={"name":"Walter"} and jesse={"name":"Jesse"}. If we put those in a list (asList(walter, jesse)) in the working copy and a reversed version of the same list in the base version, key 0 would be walter in one and jesse in the other list. The differ would now say that the name of the value has changed from Walter to Jesse. That might be acceptable, if it's only about finding the differences. Where it gets hairy is the merging part: imagine jesse and walter are referenced by other objects as well. Then a merge would cause every jesse to become {"name":"Walter"} and vice versa. Yet the only real change was the order in the containing List.

Hence I think the only solution to this problem is the "real" solution. There needs to be a special ListDiffer, which must be aware of the list order. This is my ultimate goal. Even though it is far from easy. However, I think this paper describes an algorithm, which should be the solution. I just don't know, when I'll find the time to figure out how to implement it. But it will happen eventually!

[bartswen]

Interesting example, about the name objects. Made me think. As far as I see now, the main issue here is how to identify objects. The other objects that reference the name objects identify them by their object id's. So if you want a correct merge then the differ has to use the object id's to identify the list items.

I you do not need to merge, and you just need compare the lists then clubpetey's simple solution applies. There is no need to identify the object. You just need to compare each list item with the list item on the same index in the other list.

Just by comparing two lists it is impossible (and irrelevant) to say that two items switched position, even if you can identify the objects in the list. Most lists allow duplicate elements so you cannot be sure which one you're talking about in a comparison. Currently I am implementing a lists merge for my android app. I do this by tracking all individual user actions on the lists. But the author of the paper you mention seems pretty smart. I think you better listen to him instead of me.

[SQiShER]

@andimarek was so kind to implement the solution from the paper and give me the gist of it. But even though I now have a pretty good understanding on how to find all changes and transform one List into another, it's still not the whole story. Since I want to allow for selective merging, there may be some limitations, that I need to pin down and (hopefully) find a workaround for. At the moment, I'm not even convinced, that it's possible at all. But I won't give up on it. ;-)

[Steffeng5]

Hi,

this project is really interesting and nearly 100% what i am looking for. But we have really complex objects to compare with each other, including some nested lists where the order of items is necessary.

Have you thought again about the implementation of the solution from this paper? Thanks in advance for your answer.

[SQiShER]

I wish I could say yes, but unfortunately I didn't really get to it.

Do you only need to diff your Lists or do you also need to merge them? I don't think finding the differences will be an overly complicated problem. It's the merging that worries me. I could imagine doing it in two steps and leaving the merging out of the equation (for now), if you say that you don't really need it for your project.

That being said, even the diff part alone isn't exactly trivial, so I would probably need a couple weeks, considering how busy my day-job keeps me at the moment. But right now I can't really promise anything. Depending on how urgent this is for you, feel free to fork this repo and try to implement it yourself. I'd be happy to help you with any questions that arise.

Sorry, that this use-case is not yet supported.

[Steffeng5]

No, we would need diff and merge. Is your library working with any other kind of Lists/Maps or anything like this, regarding to the order elements?

[SQiShER]

No, not really. Maintaining the correct order is pretty hard nut to crack. It wouldn't be too hard if one could only merge into the base or working version (the ones that were used to create the diff). But since it's also possible to merge each item into a completely different Map/Collection, it's pretty hard to find the right position. Actually, maintaining the order when merging is the only part of the whole collection-diffing problem, that I have not the slightest idea how to solve, yet.

[zerounix]

So do you have a ready implemantation for diffing Lists and Arrays that you can share with us?
I would not be interested in merging.
Would it be possible to pass the CollectionDiffer in DifferFactory.createDiffer to get it work for Arrays?

[SQiShER]

No, not really, sorry. Recently requests for more flexible configuration options and more examples have been so frequent, compared to List diffing, that my priorities shifted in that direction. The best thing I can share so far is a Wiki page with an unfinished specification that more or less represents the behavior I would expect from a ListDiffer (it's work in progress, though…). I included Spock for specification-based testing a while ago, in order to turn these specs into real test cases, in order to start implementing the Differ. But that's all I got so far...