Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Bug 369661

Summary:	org.eclipse.emf.ecore.util.EcoreUtil#EqualityHelper.haveEqualReference(...) does not ignore order for unordered lists
Product:	[Modeling] EMF	Reporter:	Max E. Kramer <max.kramer>
Component:	Core	Assignee:	Ed Merks <Ed.Merks>
Status:	RESOLVED WONTFIX	QA Contact:
Severity:	normal
Priority:	P3
Version:	unspecified
Target Milestone:	---
Hardware:	PC
OS:	Windows 7
Whiteboard:

Description Max E. Kramer

2012-01-25 08:35:27 EST

Build Identifier: 20110916-0149

The implementation of the method haveEqualReference(EObject, EObject, EReference) in the class EqualityHelper that is nested in org.eclipse.emf.ecore.util.EcoreUtil ignores the setting of the reference attribute ordered. It returns false when to objects containing the same elements in a different order as values for an unordered many reference are compared.

This can easily (but "costly") be fixed by inspecting the value of the ordered attribute and iterating over both lists when necessary.

Reproducible: Always

Steps to Reproduce:
1. Find two EObjects e1, e2 that are identical except for the fact that they contain the values for an unordered many reference in another order.
2. Call equals(e1,e2) and get false.

Comment 1 Ed Merks

2012-01-25 09:00:11 EST

The fix has been committed to git for 2.8.

Comment 2 Ed Merks

2012-01-25 09:07:37 EST

Oops, wrong bug.

Yes it ignores the ordered attribute. It would be very expensive and complex to do otherwise, and, in the end, multi-valued features are implemented as lists and lists with different order aren't equal according to Java's definition of equality.

Comment 3 Max E. Kramer

2012-01-25 09:59:24 EST

(In reply to comment #2)
> Oops, wrong bug.
> 
> Yes it ignores the ordered attribute. It would be very expensive and complex to
> do otherwise, and, in the end, multi-valued features are implemented as lists
> and lists with different order aren't equal according to Java's definition of
> equality.

I agree that a Java lists with different order but same elements should not be considered equal. But I doubt that in every model a reference to other elements that was explicitly marked as unordered in the metamodel should be treated the same way.

So it would be convenient to have a possibility to compare models while taking the intent of the designer of the metamodel into account (e.g. by having a new equals method with an additional boolean parameter "respectUnorderedReferences" or something similar). Of course, such a method would have to be marked cautiously with a hint that it will inevitably  need O(n^2) worst-case runtime (where n is the number of values).

Comment 4 Ed Merks

2012-01-25 10:19:34 EST

It's a theoretically interesting problem, but I don't think it's pragmatically interesting.  Imagine two lists with very large trees, where each tree is only slightly different for some leaf far to the right.  Each of the O(n^2) comparisons could involve O(size-of-entire-tree) of tree traversal.  And of course if those subtrees has lists with similar unordered lists, the problem just grows out of hand.  Algorithms with super quadratic performance just aren't a great idea...