Scalable conflict detector
New algorithm searches for conflicts only where it makes sense,
which is basically in the same match generally, except for
ReferenceChanges,
for which an index on values is used.
Consequently, the algorithm shrinks from O(n²)
to O(n) or maybe O(n log(n)).
Change-Id: I021d90dd7a0429116edc071759ee65f2fa06b56c
Signed-off-by: Laurent Delaigue <laurent.delaigue@obeo.fr>
Signed-off-by: Mathieu Cartaud <mathieu.cartaud@obeo.fr>
diff --git a/performance/org.eclipse.emf.compare.tests.performance/src/data/models/Data.java b/performance/org.eclipse.emf.compare.tests.performance/src/data/models/Data.java
index 16fb8c3..c01a38d 100644
--- a/performance/org.eclipse.emf.compare.tests.performance/src/data/models/Data.java
+++ b/performance/org.eclipse.emf.compare.tests.performance/src/data/models/Data.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2012, 2014 Obeo.
+ * Copyright (c) 2012, 2016 Obeo.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -28,7 +28,7 @@
import org.eclipse.emf.common.util.WrappedException;
import org.eclipse.emf.compare.Comparison;
import org.eclipse.emf.compare.EMFCompare;
-import org.eclipse.emf.compare.conflict.DefaultConflictDetector;
+import org.eclipse.emf.compare.conflict.MatchBasedConflictDetector;
import org.eclipse.emf.compare.conflict.IConflictDetector;
import org.eclipse.emf.compare.diagram.internal.CompareDiagramPostProcessor;
import org.eclipse.emf.compare.diff.DefaultDiffEngine;
@@ -139,7 +139,7 @@
}
public void conflict() {
- final IConflictDetector conflictDetector = new DefaultConflictDetector();
+ final IConflictDetector conflictDetector = new MatchBasedConflictDetector();
conflictDetector.detect(comparison, new BasicMonitor());
}
diff --git a/performance/org.eclipse.emf.compare.tests.performance/src/data/models/DataGit.java b/performance/org.eclipse.emf.compare.tests.performance/src/data/models/DataGit.java
index 55d64a7..81ea645 100644
--- a/performance/org.eclipse.emf.compare.tests.performance/src/data/models/DataGit.java
+++ b/performance/org.eclipse.emf.compare.tests.performance/src/data/models/DataGit.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2015 Obeo.
+ * Copyright (c) 2015, 2016 Obeo.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -38,7 +38,7 @@
import org.eclipse.emf.common.util.TreeIterator;
import org.eclipse.emf.compare.Comparison;
import org.eclipse.emf.compare.EMFCompare;
-import org.eclipse.emf.compare.conflict.DefaultConflictDetector;
+import org.eclipse.emf.compare.conflict.MatchBasedConflictDetector;
import org.eclipse.emf.compare.conflict.IConflictDetector;
import org.eclipse.emf.compare.diagram.internal.CompareDiagramPostProcessor;
import org.eclipse.emf.compare.diff.DefaultDiffEngine;
@@ -209,7 +209,7 @@
}
public void conflict() {
- final IConflictDetector conflictDetector = new DefaultConflictDetector();
+ final IConflictDetector conflictDetector = new MatchBasedConflictDetector();
conflictDetector.detect(comparison, new BasicMonitor());
}
diff --git a/plugins/org.eclipse.emf.compare.rcp/plugin.xml b/plugins/org.eclipse.emf.compare.rcp/plugin.xml
index 487d5d1..9392160 100644
--- a/plugins/org.eclipse.emf.compare.rcp/plugin.xml
+++ b/plugins/org.eclipse.emf.compare.rcp/plugin.xml
@@ -104,6 +104,13 @@
label="Default Conflict Detector"
ranking="100">
</descriptor>
+ <descriptor
+ description="Faster and more scalable conflict detector provided by EMF Compare."
+ id="org.eclipse.emf.compare.rcp.fast.conflictDetector"
+ impl="org.eclipse.emf.compare.conflict.MatchBasedConflictDetector"
+ label="Scalable Conflict Detector"
+ ranking="100">
+ </descriptor>
</extension>
<extension
point="org.eclipse.emf.compare.rcp.reqEngine">
diff --git a/plugins/org.eclipse.emf.compare.specifications/src/3.2.0-release.mediawiki b/plugins/org.eclipse.emf.compare.specifications/src/3.2.0-release.mediawiki
index c0ee3e8..0ebeb7d 100644
--- a/plugins/org.eclipse.emf.compare.specifications/src/3.2.0-release.mediawiki
+++ b/plugins/org.eclipse.emf.compare.specifications/src/3.2.0-release.mediawiki
@@ -355,3 +355,38 @@
==== test cases ====
The work will be tested by non-regression tests
+== Improve performance of conflict detection on large model ==
+=== Description ===
+As a '''user''',<br/>
+I want to '''be able to compare large model (50'000 model elements) with many differences (~30'000 differences) in a reasonable time (less than 1 minute)'''<br/>
+so that '''I can compare large models without disrupting my work flow'''
+==== Categories ====
+[[./index.html#Core-related Specifications|Core]]
+
+=== Content ===
+==== Analysis ====
+Users who deal with large models complain about the duration of comparisons, especially when a large number of differences is involved.
+This is mostly due to:
+* The logical model computation (which has however been deeply optimized and for which we lack ideas for improvements)
+* The computation of conflicts, because the algorithm implement in class <code>DefaultConflictDetector</code> is ''O(n²)''
+An analysis of this algorithm showed that it could be improved to scale much better
+
+==== Design ====
+We introduce a new implementation of <code>IConflictDetector</code> called <code>FastConflictDetector</code>.
+
+Instead of iterating over each diff and, for each of them, going over every other diff to check whether it conflicts with it,
+the fast conflict detector iterates over each diff and, for each of them, looks for conflict candidates in specific relevant places.
+These places are:
+* The current diff's <code>Match</code>
+* The (indexed) <code>ReferenceChange</code>s that point to the "same" value as the current diff, only if diff is a '''containment''' <code>ReferenceChange</code>.
+Consequently, the number of candidates to check for conflict is much smaller than in the default algorithm.
+
+[[Image:./images/FastConflictDetection.png]]
+
+Technically, the implementation delegates the search for candidates to an instance of a specific class, which is instantiated by a factory which takes into account the type and the kind of the diff. This allows the code to be more readable and thus maintainable than previously, because each method acts in a more specific context, which reduces the number of <code>fi</code> statements, for instance. Each of these classes shares behavior by extending a common abstract class.
+
+==== Test Cases ====
+The testing strategy is the following:
+* to run all the existing tests with both the DefaultConflictDetector and the FastConflictDetector, and to check the results are identical.
+* to run manual tests on large models to make sure the user time is reasonable (less than 1 minute for a model as described above)
+* to verify the positive impact on the nightly EMFCompare performance measurements
diff --git a/plugins/org.eclipse.emf.compare.specifications/src/images/FastConflictDetection.png b/plugins/org.eclipse.emf.compare.specifications/src/images/FastConflictDetection.png
new file mode 100644
index 0000000..9127af8
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.specifications/src/images/FastConflictDetection.png
Binary files differ
diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/framework/junit/internal/ConflictStatement.java b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/framework/junit/internal/ConflictStatement.java
index f1a5b11..7188adc 100644
--- a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/framework/junit/internal/ConflictStatement.java
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/framework/junit/internal/ConflictStatement.java
@@ -1,5 +1,5 @@
/**
- * Copyright (c) 2013, 2014 Obeo.
+ * Copyright (c) 2013, 2016 Obeo.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -16,7 +16,7 @@
import org.eclipse.emf.common.util.BasicMonitor;
import org.eclipse.emf.common.util.Monitor;
import org.eclipse.emf.compare.Comparison;
-import org.eclipse.emf.compare.conflict.DefaultConflictDetector;
+import org.eclipse.emf.compare.conflict.MatchBasedConflictDetector;
import org.eclipse.emf.compare.conflict.IConflictDetector;
import org.eclipse.emf.compare.diff.DefaultDiffEngine;
import org.eclipse.emf.compare.diff.DiffBuilder;
@@ -87,7 +87,7 @@
final IComparisonScope scope = createComparisonScope(tuple, annotation);
final IMatchEngine matchEngine = createMatchEngine(annotation);
final IDiffEngine diffEngine = createDiffEngine(annotation);
- final IConflictDetector detector = new DefaultConflictDetector();
+ final IConflictDetector detector = new MatchBasedConflictDetector();
final Monitor monitor = new BasicMonitor();
final Comparison comparison = matchEngine.match(scope, new BasicMonitor());
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/EMFCompare.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/EMFCompare.java
index de47f52..cc9d813 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/EMFCompare.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/EMFCompare.java
@@ -25,8 +25,8 @@
import org.eclipse.emf.common.util.DiagnosticChain;
import org.eclipse.emf.common.util.EList;
import org.eclipse.emf.common.util.Monitor;
-import org.eclipse.emf.compare.conflict.DefaultConflictDetector;
import org.eclipse.emf.compare.conflict.IConflictDetector;
+import org.eclipse.emf.compare.conflict.MatchBasedConflictDetector;
import org.eclipse.emf.compare.diff.DefaultDiffEngine;
import org.eclipse.emf.compare.diff.DiffBuilder;
import org.eclipse.emf.compare.diff.IDiffEngine;
@@ -658,7 +658,7 @@
registry = new PostProcessorDescriptorRegistryImpl<Object>();
}
if (conflictDetector == null) {
- conflictDetector = new DefaultConflictDetector();
+ conflictDetector = new MatchBasedConflictDetector();
}
return new EMFCompare(this.matchEngineFactoryRegistry, this.diffEngine, this.reqEngine,
this.equiEngine, this.conflictDetector, this.registry);
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/conflict/DefaultConflictDetector.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/conflict/DefaultConflictDetector.java
index 840f965..ae3aa62 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/conflict/DefaultConflictDetector.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/conflict/DefaultConflictDetector.java
@@ -21,20 +21,17 @@
import static org.eclipse.emf.compare.utils.EMFComparePredicates.hasConflict;
import static org.eclipse.emf.compare.utils.EMFComparePredicates.ofKind;
import static org.eclipse.emf.compare.utils.EMFComparePredicates.onFeature;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.possiblyConflictingWith;
import static org.eclipse.emf.compare.utils.EMFComparePredicates.valueIs;
import com.google.common.base.Predicate;
-import com.google.common.base.Predicates;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
-import java.util.Iterator;
import java.util.List;
-import java.util.NoSuchElementException;
import org.apache.log4j.Logger;
import org.eclipse.emf.common.util.Monitor;
-import org.eclipse.emf.common.util.TreeIterator;
import org.eclipse.emf.compare.AttributeChange;
import org.eclipse.emf.compare.CompareFactory;
import org.eclipse.emf.compare.Comparison;
@@ -50,9 +47,8 @@
import org.eclipse.emf.compare.MatchResource;
import org.eclipse.emf.compare.ReferenceChange;
import org.eclipse.emf.compare.ResourceAttachmentChange;
-import org.eclipse.emf.compare.ResourceLocationChange;
-import org.eclipse.emf.compare.internal.SubMatchIterator;
import org.eclipse.emf.compare.internal.ThreeWayTextDiff;
+import org.eclipse.emf.compare.internal.conflict.DiffTreeIterator;
import org.eclipse.emf.compare.internal.utils.ComparisonUtil;
import org.eclipse.emf.compare.utils.IEqualityHelper;
import org.eclipse.emf.compare.utils.ReferenceUtil;
@@ -121,8 +117,7 @@
}
final Diff diff = differences.get(i);
- final Predicate<? super Diff> candidateFilter = new ConflictCandidateFilter(diff);
- checkConflict(comparison, diff, Iterables.filter(differences, candidateFilter));
+ checkConflict(comparison, diff, Iterables.filter(differences, possiblyConflictingWith(diff)));
}
handlePseudoUnderRealAdd(comparison);
@@ -239,9 +234,8 @@
// [381143] Every Diff "under" a containment deletion conflicts with it.
if (diff.getKind() == DifferenceKind.DELETE) {
- final Predicate<? super Diff> candidateFilter = new ConflictCandidateFilter(diff);
final DiffTreeIterator diffIterator = new DiffTreeIterator(comparison.getMatch(diff.getValue()));
- diffIterator.setFilter(candidateFilter);
+ diffIterator.setFilter(possiblyConflictingWith(diff));
diffIterator.setPruningFilter(isContainmentDelete());
while (diffIterator.hasNext()) {
@@ -392,9 +386,8 @@
// [381143] Every Diff "under" a containment deletion conflicts with it.
if (diff.getKind() == DifferenceKind.DELETE) {
- final Predicate<? super Diff> candidateFilter = new ConflictCandidateFilter(diff);
final DiffTreeIterator diffIterator = new DiffTreeIterator(valueMatch);
- diffIterator.setFilter(candidateFilter);
+ diffIterator.setFilter(possiblyConflictingWith(diff));
diffIterator.setPruningFilter(isContainmentDelete());
while (diffIterator.hasNext()) {
@@ -993,8 +986,8 @@
// [477607] DELETE does not necessarily mean that the element is removed from the model
EObject o = getRelatedModelElement(diff);
if (o != null && o.eContainer() == null) {
- final Predicate<? super Diff> candidateFilter = new ConflictCandidateFilter(diff);
- for (Diff extendedCandidate : Iterables.filter(match.getAllDifferences(), candidateFilter)) {
+ for (Diff extendedCandidate : Iterables.filter(match.getAllDifferences(),
+ possiblyConflictingWith(diff))) {
if (isDeleteOrUnsetDiff(extendedCandidate)) {
conflictOn(comparison, diff, extendedCandidate, ConflictKind.PSEUDO);
} else {
@@ -1287,201 +1280,4 @@
// This diff may have equivalences. These equivalences
}
-
- /**
- * This will be used to filter out the list of potential candidates for conflict with a given Diff.
- *
- * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a>
- */
- private static final class ConflictCandidateFilter implements Predicate<Diff> {
- /** The Diff for which we seek conflict candidates. */
- private final Diff reference;
-
- /**
- * Instantiates our filtering Predicate given the reference Diff for which to seek potential
- * conflicts.
- *
- * @param reference
- * The Diff for which we seek conflict candidates.
- */
- public ConflictCandidateFilter(Diff reference) {
- this.reference = reference;
- }
-
- /**
- * {@inheritDoc}
- *
- * @see com.google.common.base.Predicate#apply(java.lang.Object)
- */
- public boolean apply(Diff input) {
- return !(input instanceof ResourceLocationChange) && canConflictWith(reference, input);
- }
-
- /**
- * Checks if the given {@link Diff diff1} can be in conflict with the given {@link Diff diff2}.
- * <p>
- * Notably, we don't need to try and detect a conflict between two diffs if they're one and the same
- * or if they have already been detected as a conflicting couple. Likewise, there can be no conflict
- * if the two diffs originate from the same side.
- * </p>
- * <p>
- * bug 381143 : we'll also remove any containment deletion diff on other Matches from here.
- * </p>
- *
- * @param diff1
- * First of the two differences to consider for conflict detection.
- * @param diff2
- * Second of the two differences to consider for conflict detection.
- * @return {@code true} if the two given diffs can conflict, {@code false} otherwise.
- */
- private boolean canConflictWith(Diff diff1, Diff diff2) {
- if (diff1 == diff2 || diff1.getSource() == diff2.getSource()) {
- return false;
- }
- final Conflict conflict = diff1.getConflict();
-
- boolean canConflict = false;
- if (conflict == null || !conflict.getDifferences().contains(diff2)) {
- if (diff1.getMatch() != diff2.getMatch() && diff2 instanceof ReferenceChange
- && ((ReferenceChange)diff2).getReference().isContainment()) {
- canConflict = !isDeleteOrUnsetDiff(diff2);
- } else {
- canConflict = true;
- }
- }
- return canConflict;
- }
- }
-
- /**
- * A custom iterator that will walk a Match->submatch tree, and allow iteration over the Diffs of these
- * Matches.
- * <p>
- * Since we're walking over Matches but returning Diffs, this is not a good candidate for guava's filters.
- * We're providing the custom {@link DiffTreeIterator#setFilter(Predicate)} and
- * {@link DiffTreeIterator#setPruningFilter(Predicate)} to allow for filtering or pruning the the
- * iteration.
- * </p>
- *
- * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a>
- */
- private static class DiffTreeIterator implements Iterator<Diff> {
- /**
- * The tree iterator that will walk over our Match tree. Some of the paths can be pruned through the
- * use of a {@link #pruningFilter}.
- */
- private final TreeIterator<Match> subMatchIterator;
-
- /** An iterator over the differences of the current Match. */
- private Iterator<Diff> diffIterator;
-
- /** Current match. */
- private Match current;
-
- /** The Diff that will be returned by the next call to {@link #next()}. */
- private Diff nextDiff;
-
- /** Only Diffs that meet this criterion will be returned by this iterator. */
- private Predicate<? super Diff> filter = Predicates.alwaysTrue();
-
- /**
- * This particular filter can be used in order to prune a given Match and all of its differences and
- * sub-differences.
- */
- private Predicate<? super Match> pruningFilter = Predicates.alwaysFalse();
-
- /**
- * Constructs our iterator given the root of the Match tree to iterate over.
- *
- * @param start
- * Starting match of the tree we'll iterate over.
- */
- public DiffTreeIterator(Match start) {
- this.current = start;
- this.subMatchIterator = new SubMatchIterator(start);
- this.diffIterator = start.getDifferences().iterator();
- }
-
- /**
- * Sets the criterion that Diffs must meet to be returned by this iterator.
- *
- * @param filter
- * The filter differences must meet.
- */
- public void setFilter(Predicate<? super Diff> filter) {
- this.filter = filter;
- }
-
- /**
- * Sets the pruning filter for this iterator. Any Match that meets this criterion will be pruned along
- * with all of its differences and sub-differences.
- *
- * @param pruningFilter
- * The pruning filter for this iterator.
- */
- public void setPruningFilter(Predicate<? super Match> pruningFilter) {
- this.pruningFilter = pruningFilter;
- }
-
- /**
- * {@inheritDoc}
- *
- * @see java.util.Iterator#hasNext()
- */
- public boolean hasNext() {
- if (nextDiff != null) {
- return true;
- }
- if (!diffIterator.hasNext()) {
- computeNextMatch();
- }
- while (nextDiff == null && diffIterator.hasNext()) {
- final Diff next = diffIterator.next();
- if (filter.apply(next)) {
- nextDiff = next;
- }
- }
- return nextDiff != null;
- }
-
- /**
- * Computes the next match within the sub-match tree, pruning those that may meet
- * {@link #pruningFilter}.
- */
- private void computeNextMatch() {
- final Match old = current;
- while (current == old && subMatchIterator.hasNext()) {
- final Match next = subMatchIterator.next();
- if (pruningFilter.apply(next)) {
- subMatchIterator.prune();
- } else {
- current = next;
- diffIterator = current.getDifferences().iterator();
- }
- }
- }
-
- /**
- * {@inheritDoc}
- *
- * @see java.util.Iterator#next()
- */
- public Diff next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
- final Diff next = nextDiff;
- nextDiff = null;
- return next;
- }
-
- /**
- * {@inheritDoc}
- *
- * @see java.util.Iterator#remove()
- */
- public void remove() {
- diffIterator.remove();
- }
- }
}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/conflict/MatchBasedConflictDetector.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/conflict/MatchBasedConflictDetector.java
new file mode 100644
index 0000000..6a81c19
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/conflict/MatchBasedConflictDetector.java
@@ -0,0 +1,142 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.conflict;
+
+import static com.google.common.collect.Iterables.filter;
+import static com.google.common.collect.Iterables.isEmpty;
+import static org.eclipse.emf.compare.ConflictKind.PSEUDO;
+import static org.eclipse.emf.compare.ConflictKind.REAL;
+import static org.eclipse.emf.compare.DifferenceKind.ADD;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.CONTAINMENT_REFERENCE_CHANGE;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.hasConflict;
+
+import com.google.common.base.Predicate;
+
+import java.util.List;
+
+import org.apache.log4j.Logger;
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.Comparison;
+import org.eclipse.emf.compare.ComparisonCanceledException;
+import org.eclipse.emf.compare.Conflict;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.EMFCompareMessages;
+import org.eclipse.emf.compare.Match;
+import org.eclipse.emf.compare.ReferenceChange;
+import org.eclipse.emf.compare.internal.conflict.AbstractConflictSearch;
+import org.eclipse.emf.compare.internal.conflict.ConflictSearchFactory;
+import org.eclipse.emf.ecore.EObject;
+
+/**
+ * This conflict detector searches for conflicting {@link Diff}s in the same {@link Match} as the current
+ * {@link Diff}, as well as among {@link ReferenceChange}s that reference the same {@link EObject} as the
+ * current {@link Diff}, if it is a {@link ReferenceChange}.
+ * <p>
+ * This implementation of {@link IConflictDetector} is a generic as the default one but scales better since it
+ * is not O(n²) but rather O(n) or O(n log(n)), n being the number of differences in the comparison.
+ * </p>
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ * @since 3.3
+ */
+public class MatchBasedConflictDetector implements IConflictDetector {
+
+ /** The logger. */
+ private static final Logger LOGGER = Logger.getLogger(MatchBasedConflictDetector.class);
+
+ /**
+ * This can be used to check whether a given conflict involves add containment reference changes.
+ */
+ private static final Predicate<? super Conflict> IS_REAL_CONTAINMENT_ADD_CONFLICT = new Predicate<Conflict>() {
+ public boolean apply(Conflict input) {
+ boolean isRealAddContainmentConflict = false;
+ if (input != null && input.getKind() == REAL) {
+ Iterable<Diff> containmentRefs = filter(input.getDifferences(), CONTAINMENT_REFERENCE_CHANGE);
+ if (!isEmpty(containmentRefs)) {
+ for (Diff diff : containmentRefs) {
+ if (diff.getKind() != ADD) {
+ return false;
+ }
+ }
+ isRealAddContainmentConflict = true;
+ }
+ }
+ return isRealAddContainmentConflict;
+ }
+ };
+
+ /**
+ * {@inheritDoc}
+ *
+ * @see org.eclipse.emf.compare.conflict.IConflictDetector#detect(org.eclipse.emf.compare.Comparison,
+ * org.eclipse.emf.common.util.Monitor)
+ */
+ public void detect(Comparison comparison, Monitor monitor) {
+ long start = System.currentTimeMillis();
+ if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug("detect conflicts - START"); //$NON-NLS-1$
+ }
+ final List<Diff> differences = comparison.getDifferences();
+ final int diffCount = differences.size();
+
+ ConflictSearchFactory conflictSearchFactory = new ConflictSearchFactory(comparison, monitor);
+ for (int i = 0; i < diffCount; i++) {
+ if (i % 100 == 0) {
+ monitor.subTask(EMFCompareMessages.getString("DefaultConflictDetector.monitor.detect", //$NON-NLS-1$
+ Integer.valueOf(i + 1), Integer.valueOf(diffCount)));
+ }
+ if (monitor.isCanceled()) {
+ throw new ComparisonCanceledException();
+ }
+ final Diff diff = differences.get(i);
+ AbstractConflictSearch<? extends Diff> search = conflictSearchFactory.doSwitch(diff);
+ search.detectConflicts();
+ }
+
+ handlePseudoUnderRealAdd(comparison);
+ if (LOGGER.isInfoEnabled()) {
+ LOGGER.info(String.format(
+ "detect conflicts - END - Took %d ms", Long.valueOf(System.currentTimeMillis() - start))); //$NON-NLS-1$
+ }
+ }
+
+ /**
+ * If a real add conflict contains pseudo conflicts, these pseudo conflicts must be changed to real
+ * conflicts.
+ *
+ * @param comparison
+ * The originating comparison of those diffs.
+ */
+ private void handlePseudoUnderRealAdd(Comparison comparison) {
+ for (Conflict realContainmentAdd : filter(comparison.getConflicts(), IS_REAL_CONTAINMENT_ADD_CONFLICT)) {
+ changeKindOfPseudoConflictsUnder(realContainmentAdd);
+ }
+ }
+
+ /**
+ * Change all pseudo conflicts under the given real conflict to real conflicts.
+ *
+ * @param conflict
+ * the given conflict.
+ */
+ private void changeKindOfPseudoConflictsUnder(Conflict conflict) {
+ for (Diff diff : conflict.getDifferences()) {
+ final Match realConflictMatch = diff.getMatch();
+ for (Match subMatch : realConflictMatch.getSubmatches()) {
+ for (Diff conflictDiffUnder : filter(subMatch.getDifferences(), hasConflict(PSEUDO))) {
+ Conflict conflictUnder = conflictDiffUnder.getConflict();
+ conflictUnder.setKind(REAL);
+ changeKindOfPseudoConflictsUnder(conflictUnder);
+ }
+ }
+ }
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/AbstractConflictSearch.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/AbstractConflictSearch.java
new file mode 100644
index 0000000..15fa5d6
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/AbstractConflictSearch.java
@@ -0,0 +1,523 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+import static com.google.common.base.Predicates.and;
+import static org.eclipse.emf.compare.ConflictKind.PSEUDO;
+import static org.eclipse.emf.compare.ConflictKind.REAL;
+import static org.eclipse.emf.compare.DifferenceKind.DELETE;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.ofKind;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.onFeature;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.valueIs;
+
+import com.google.common.base.Predicate;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+
+import org.eclipse.emf.common.util.EList;
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.AttributeChange;
+import org.eclipse.emf.compare.CompareFactory;
+import org.eclipse.emf.compare.Comparison;
+import org.eclipse.emf.compare.Conflict;
+import org.eclipse.emf.compare.ConflictKind;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.DifferenceKind;
+import org.eclipse.emf.compare.DifferenceSource;
+import org.eclipse.emf.compare.EMFCompareMessages;
+import org.eclipse.emf.compare.Equivalence;
+import org.eclipse.emf.compare.FeatureMapChange;
+import org.eclipse.emf.compare.Match;
+import org.eclipse.emf.compare.MatchResource;
+import org.eclipse.emf.compare.ResourceAttachmentChange;
+import org.eclipse.emf.compare.internal.ThreeWayTextDiff;
+import org.eclipse.emf.compare.utils.ReferenceUtil;
+import org.eclipse.emf.ecore.EAttribute;
+import org.eclipse.emf.ecore.EObject;
+import org.eclipse.emf.ecore.EStructuralFeature;
+import org.eclipse.emf.ecore.resource.Resource;
+import org.eclipse.emf.ecore.util.EcoreUtil;
+
+/**
+ * Class in charge of finding conflicting diffs for a given diff of type T.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ * @param <T>
+ * The type of diff for which conflict are researched
+ */
+public abstract class AbstractConflictSearch<T extends Diff> {
+
+ /** The difference, never <code>null</code>. */
+ protected final T diff;
+
+ /** The comparison that contains diff. */
+ protected final Comparison comparison;
+
+ /** The index of the comparison. */
+ protected final ComparisonIndex index;
+
+ /** The monitor to report progress to. */
+ protected final Monitor monitor;
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search conflicts with, must not be <code>null</code> and have a non-null match
+ * that belongs to a non-null comparison. It must also have a non-null {@link DifferenceKind}
+ * and {@link DifferenceSource}.
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public AbstractConflictSearch(T diff, ComparisonIndex index, Monitor monitor) {
+ checkNotNull(diff);
+ if (diff.getMatch() == null || diff.getMatch().getComparison() == null) {
+ throw new IllegalArgumentException();
+ }
+ comparison = diff.getMatch().getComparison();
+ checkArgument(diff.getKind() != null && diff.getSource() != null);
+ this.diff = diff;
+ this.index = checkNotNull(index);
+ this.monitor = checkNotNull(monitor);
+ }
+
+ /**
+ * Detect conflicts with {@link AbstractConflictSearch#diff} in its comparison. This will add or update
+ * conflicts in <code>diff</code>'s comparison.
+ */
+ public abstract void detectConflicts();
+
+ /**
+ * Get the diffs in the same {@link Match} as diff.
+ *
+ * @return A never-null EList of differences in the same {@link Match} as diff, including diff.
+ */
+ protected EList<Diff> getDiffsInSameMatch() {
+ return diff.getMatch().getDifferences();
+ }
+
+ /**
+ * Specifies whether the given {@code diff1} and {@code diff2} are either {@link FeatureMapChange feature
+ * map changes} or mergeable {@link AttributeChange attribute changes} of String attributes.
+ *
+ * @param diff1
+ * One of the diffs to check.
+ * @param diff2
+ * The other diff to check.
+ * @return <code>true</code> if it is a {@link FeatureMapChange} or a mergeable {@link AttributeChange},
+ * <code>false</code> otherwise.
+ */
+ protected boolean isFeatureMapChangeOrMergeableStringAttributeChange(Diff diff1, Diff diff2) {
+ return isFeatureMapChange(diff1) || areMergeableStringAttributeChanges(diff1, diff2);
+ }
+
+ /**
+ * Specifies whether the given {@code diff} is a {@link FeatureMapChange}.
+ *
+ * @param toCheck
+ * The diff to check.
+ * @return <code>true</code> if it is a {@link FeatureMapChange}, <code>false</code> otherwise.
+ */
+ protected boolean isFeatureMapChange(Diff toCheck) {
+ return toCheck instanceof FeatureMapChange;
+ }
+
+ /**
+ * Specifies whether the two given diffs, {@code diff1} and {@code diff2}, are both
+ * {@link AttributeChange attribute changes} of String attributes and can be merged with a line-based
+ * three-way merge.
+ *
+ * @see org.eclipse.emf.compare.internal.ThreeWayTextDiff
+ * @param diff1
+ * One of the diffs to check.
+ * @param diff2
+ * The other diff to check.
+ * @return <code>true</code> if the diffs are mergeable changes of a string attribute, <code>false</code>
+ * otherwise.
+ */
+ protected boolean areMergeableStringAttributeChanges(Diff diff1, Diff diff2) {
+ final boolean mergeableStringAttributeChange;
+ if (isStringAttributeChange(diff1)) {
+ final AttributeChange attributeChange1 = (AttributeChange)diff1;
+ final AttributeChange attributeChange2 = (AttributeChange)diff2;
+ mergeableStringAttributeChange = isMergeable(attributeChange1, attributeChange2);
+ } else {
+ mergeableStringAttributeChange = false;
+ }
+ return mergeableStringAttributeChange;
+ }
+
+ /**
+ * Specifies whether the given {@code diff} is a {@link AttributeChange} of a String attribute.
+ *
+ * @param toCheck
+ * The diff to check.
+ * @return <code>true</code> if it is a {@link AttributeChange} of a String attribute, <code>false</code>
+ * otherwise.
+ */
+ protected boolean isStringAttributeChange(Diff toCheck) {
+ return toCheck instanceof AttributeChange
+ && ((AttributeChange)toCheck).getAttribute().getEAttributeType().getInstanceClass() == String.class;
+ }
+
+ /**
+ * Specifies whether the two given attribute changes, {@code diff1} and {@code diff2}, can be merged with
+ * a line-based three-way merge.
+ *
+ * @see org.eclipse.emf.compare.internal.ThreeWayTextDiff
+ * @param diff1
+ * One of the attribute changes to check.
+ * @param diff2
+ * The other attribute change to check.
+ * @return <code>true</code> if the attribute changes are mergeable, <code>false</code> otherwise.
+ */
+ protected boolean isMergeable(final AttributeChange diff1, final AttributeChange diff2) {
+ final String changedValue1 = getChangedValue(diff1);
+ final String changedValue2 = getChangedValue(diff2);
+ final EObject originalContainer = diff1.getMatch().getOrigin();
+ final EAttribute changedAttribute = diff1.getAttribute();
+ final String originalValue = (String)originalContainer.eGet(changedAttribute);
+ return isMergeableText(changedValue1, changedValue2, originalValue);
+ }
+
+ /**
+ * Specifies whether the given three versions of a text {@code left}, {@code right}, and {@code origin}
+ * are mergeable with a line-based three-way merge.
+ *
+ * @param left
+ * The left version.
+ * @param right
+ * The right version.
+ * @param origin
+ * The original version.
+ * @return <code>true</code> if they are mergeable, false otherwise.
+ * @since 3.2
+ */
+ protected boolean isMergeableText(final String left, final String right, final String origin) {
+ ThreeWayTextDiff textDiff = new ThreeWayTextDiff(origin, left, right);
+ return !textDiff.isConflicting();
+ }
+
+ /**
+ * Returns the changed attribute value denoted by the given {@code diff}.
+ *
+ * @param attributeChange
+ * The attribute change for which the changed value is requested.
+ * @return The changed attribute value.
+ */
+ protected String getChangedValue(final AttributeChange attributeChange) {
+ final String changedValue;
+ Match match = attributeChange.getMatch();
+ if (DifferenceSource.LEFT.equals(attributeChange.getSource())) {
+ changedValue = (String)match.getLeft().eGet(attributeChange.getAttribute());
+ } else if (DifferenceSource.RIGHT.equals(attributeChange.getSource())) {
+ changedValue = (String)match.getRight().eGet(attributeChange.getAttribute());
+ } else {
+ changedValue = (String)attributeChange.getValue();
+ }
+ return changedValue;
+ }
+
+ /**
+ * This will be used whenever we check for conflictual MOVEs in order to determine whether we have a
+ * pseudo conflict or a real conflict.
+ * <p>
+ * Namely, this will retrieve the value of the given {@code feature} on the right and left sides of the
+ * given {@code match}, then check whether the two given values are on the same index.
+ * </p>
+ * <p>
+ * Note that no sanity checks will be made on either the match's sides or the feature.
+ * </p>
+ *
+ * @param match
+ * Match for which we need to check a feature.
+ * @param feature
+ * The feature which values we need to check.
+ * @param value1
+ * First of the two values which index we are to compare.
+ * @param value2
+ * Second of the two values which index we are to compare.
+ * @return {@code true} if the two given values are located at the same index in the given feature's
+ * values list, {@code false} otherwise.
+ */
+ protected boolean matchingIndices(Match match, EStructuralFeature feature, Object value1, Object value2) {
+ boolean matching = false;
+ if (feature.isMany()) {
+ @SuppressWarnings("unchecked")
+ final List<Object> leftValues = (List<Object>)ReferenceUtil.safeEGet(match.getLeft(), feature);
+ @SuppressWarnings("unchecked")
+ final List<Object> rightValues = (List<Object>)ReferenceUtil.safeEGet(match.getRight(), feature);
+
+ // FIXME the detection _will_ fail for non-unique lists with multiple identical values...
+ int leftIndex = -1;
+ int rightIndex = -1;
+ for (int i = 0; i < leftValues.size(); i++) {
+ final Object left = leftValues.get(i);
+ if (comparison.getEqualityHelper().matchingValues(left, value1)) {
+ break;
+ } else if (hasDiff(match, feature, left) || hasDeleteDiff(match, feature, left)) {
+ // Do not increment.
+ } else {
+ leftIndex++;
+ }
+ }
+ for (int i = 0; i < rightValues.size(); i++) {
+ final Object right = rightValues.get(i);
+ if (comparison.getEqualityHelper().matchingValues(right, value2)) {
+ break;
+ } else if (hasDiff(match, feature, right) || hasDeleteDiff(match, feature, right)) {
+ // Do not increment.
+ } else {
+ rightIndex++;
+ }
+ }
+ matching = leftIndex == rightIndex;
+ } else {
+ matching = true;
+ }
+ return matching;
+ }
+
+ /**
+ * Checks whether the given {@code match} presents a difference of any kind on the given {@code feature}'s
+ * {@code value}.
+ *
+ * @param match
+ * The match which differences we'll check.
+ * @param feature
+ * The feature on which we expect a difference.
+ * @param value
+ * The value we expect to have changed inside {@code feature}.
+ * @return <code>true</code> if there is such a Diff on {@code match}, <code>false</code> otherwise.
+ */
+ protected boolean hasDiff(Match match, EStructuralFeature feature, Object value) {
+ return Iterables.any(match.getDifferences(), and(onFeature(feature.getName()), valueIs(value)));
+ }
+
+ /**
+ * Checks whether the given {@code value} has been deleted from the given {@code feature} of {@code match}
+ * .
+ *
+ * @param match
+ * The match which differences we'll check.
+ * @param feature
+ * The feature on which we expect a difference.
+ * @param value
+ * The value we expect to have been removed from {@code feature}.
+ * @return <code>true</code> if there is such a Diff on {@code match}, <code>false</code> otherwise.
+ */
+ protected boolean hasDeleteDiff(Match match, EStructuralFeature feature, Object value) {
+ checkArgument(match.getComparison() == comparison);
+ final Object expectedValue;
+ if (value instanceof EObject && comparison.isThreeWay()) {
+ final Match valueMatch = comparison.getMatch((EObject)value);
+ if (valueMatch != null) {
+ expectedValue = valueMatch.getOrigin();
+ } else {
+ expectedValue = value;
+ }
+ } else {
+ expectedValue = value;
+ }
+ return Iterables.any(match.getDifferences(), and(onFeature(feature.getName()),
+ valueIs(expectedValue), ofKind(DELETE)));
+ }
+
+ /**
+ * This will be called whenever we detect a new conflict in order to create (or update) the actual
+ * association.
+ *
+ * @param other
+ * Second of the two differences for which we detected a conflict.
+ * @param kind
+ * Kind of this conflict.
+ */
+ protected void conflict(Diff other, ConflictKind kind) {
+ // Pre-condition: diff and other are not already part of the same conflict
+ if (diff.getConflict() != null && diff.getConflict().getDifferences().contains(other)) {
+ return;
+ }
+
+ Conflict conflict = null;
+ Conflict toBeMerged = null;
+ if (diff.getConflict() != null) {
+ conflict = diff.getConflict();
+ if (conflict.getKind() == PSEUDO && conflict.getKind() != kind) {
+ conflict.setKind(kind);
+ }
+ if (other.getConflict() != null) {
+ // Merge the two
+ toBeMerged = other.getConflict();
+ }
+ } else if (other.getConflict() != null) {
+ conflict = other.getConflict();
+ if (conflict.getKind() == PSEUDO && conflict.getKind() != kind) {
+ conflict.setKind(kind);
+ }
+ } else if (diff.getEquivalence() != null) {
+ Equivalence equivalence = diff.getEquivalence();
+ for (Diff equ : equivalence.getDifferences()) {
+ if (equ.getConflict() != null) {
+ conflict = equ.getConflict();
+ if (other.getConflict() == conflict) {
+ // See initial pre-condition
+ return;
+ }
+ if (conflict.getKind() == PSEUDO && conflict.getKind() != kind) {
+ conflict.setKind(kind);
+ }
+ if (other.getConflict() != null) {
+ // Merge the two
+ toBeMerged = other.getConflict();
+ }
+ break;
+ }
+ }
+ } else if (other.getEquivalence() != null) {
+ Equivalence equivalence = other.getEquivalence();
+ for (Diff equ : equivalence.getDifferences()) {
+ if (equ.getConflict() != null) {
+ conflict = equ.getConflict();
+ if (conflict.getKind() == PSEUDO && conflict.getKind() != kind) {
+ conflict.setKind(kind);
+ }
+ break;
+ }
+ }
+ }
+
+ if (conflict == null) {
+ conflict = CompareFactory.eINSTANCE.createConflict();
+ conflict.setKind(kind);
+ comparison.getConflicts().add(conflict);
+ }
+
+ final EList<Diff> conflictDiffs = conflict.getDifferences();
+ if (toBeMerged != null) {
+ // These references are opposite. We can't simply iterate
+ for (Diff aDiff : Lists.newArrayList(toBeMerged.getDifferences())) {
+ conflictDiffs.add(aDiff);
+ }
+ if (toBeMerged.getKind() == REAL && conflict.getKind() != REAL) {
+ conflict.setKind(REAL);
+ }
+ EcoreUtil.remove(toBeMerged);
+ toBeMerged.getDifferences().clear();
+ }
+
+ conflict.getDifferences().add(diff);
+ conflict.getDifferences().add(other);
+ }
+
+ /**
+ * Returns the MatchResource corresponding to the given <code>resource</code>.
+ *
+ * @param resource
+ * Resource for which we need a MatchResource.
+ * @return The MatchResource corresponding to the given <code>resource</code>.
+ */
+ protected MatchResource getMatchResource(Resource resource) {
+ final List<MatchResource> matchedResources = comparison.getMatchedResources();
+ final int size = matchedResources.size();
+ MatchResource soughtMatch = null;
+ for (int i = 0; i < size && soughtMatch == null; i++) {
+ final MatchResource matchRes = matchedResources.get(i);
+ if (matchRes.getRight() == resource || matchRes.getLeft() == resource
+ || matchRes.getOrigin() == resource) {
+ soughtMatch = matchRes;
+ }
+ }
+ checkState(soughtMatch != null, EMFCompareMessages.getString(
+ "ResourceAttachmentChangeSpec.MissingMatch", resource.getURI().lastSegment())); //$NON-NLS-1$
+ return soughtMatch;
+ }
+
+ /**
+ * Provide the model element the given diff applies to.
+ *
+ * @param rac
+ * The change
+ * @return The model element of the given diff, or null if it cannot be found.
+ */
+ protected EObject getRelatedModelElement(ResourceAttachmentChange rac) {
+ Match m = rac.getMatch();
+ EObject o;
+ switch (rac.getSource()) {
+ case LEFT:
+ o = m.getLeft(); // null if DELETE
+ break;
+ case RIGHT:
+ o = m.getRight(); // null if DELETE
+ break;
+ default:
+ o = null;
+ }
+ return o;
+ }
+
+ /**
+ * Provide the non-null model element the given diff applies to.
+ *
+ * @param rac
+ * The change
+ * @return The model element of the given diff, cannot be null.
+ */
+ protected EObject getValue(ResourceAttachmentChange rac) {
+ Match m = rac.getMatch();
+ EObject o;
+ switch (rac.getKind()) {
+ case ADD:
+ // Voluntary pass-through
+ case CHANGE:
+ // Voluntary pass-through
+ case MOVE:
+ switch (rac.getSource()) {
+ case LEFT:
+ o = m.getLeft();
+ break;
+ case RIGHT:
+ o = m.getRight();
+ break;
+ default:
+ o = null;
+ }
+ break;
+ case DELETE:
+ o = m.getOrigin();
+ break;
+ default:
+ throw new IllegalStateException();
+ }
+ checkState(o != null);
+ return o;
+ }
+
+ // FIXME Move this elsewhere
+ /**
+ * This predicate will be <code>true</code> for any Match which represents a containment deletion.
+ *
+ * @return A Predicate that will be met by containment deletions.
+ */
+ protected Predicate<? super Match> isContainmentDelete() {
+ return new Predicate<Match>() {
+ public boolean apply(Match input) {
+ return input.getOrigin() != null && (input.getLeft() == null || input.getRight() == null);
+ }
+ };
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/AttributeChangeConflictSearch.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/AttributeChangeConflictSearch.java
new file mode 100644
index 0000000..30270e0
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/AttributeChangeConflictSearch.java
@@ -0,0 +1,205 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import static com.google.common.base.Predicates.and;
+import static com.google.common.base.Predicates.instanceOf;
+import static org.eclipse.emf.compare.ConflictKind.PSEUDO;
+import static org.eclipse.emf.compare.ConflictKind.REAL;
+import static org.eclipse.emf.compare.DifferenceKind.ADD;
+import static org.eclipse.emf.compare.DifferenceKind.CHANGE;
+import static org.eclipse.emf.compare.DifferenceKind.DELETE;
+import static org.eclipse.emf.compare.DifferenceKind.MOVE;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.ofKind;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.onFeature;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.possiblyConflictingWith;
+
+import com.google.common.collect.Iterables;
+
+import org.eclipse.emf.common.util.EList;
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.AttributeChange;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.DifferenceKind;
+import org.eclipse.emf.ecore.EAttribute;
+
+/**
+ * Search conflicts for {@link AttributeChange}s.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+public class AttributeChangeConflictSearch {
+
+ /**
+ * Search conflicts for {@link AttributeChange} of kind {@link DifferenceKind#ADD}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Add extends AbstractConflictSearch<AttributeChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Add(AttributeChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ EAttribute feature = diff.getAttribute();
+ // Only unique features can conflict
+ if (feature.isUnique()) {
+ Object value = diff.getValue();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(AttributeChange.class), onFeature(feature), ofKind(ADD)))) {
+ Object candidateValue = ((AttributeChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ // This is a conflict. Is it real?
+ if (matchingIndices(diff.getMatch(), feature, value, candidateValue)) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link AttributeChange} of kind {@link DifferenceKind#CHANGE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Change extends AbstractConflictSearch<AttributeChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Change(AttributeChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EAttribute feature = diff.getAttribute();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(AttributeChange.class), onFeature(feature), ofKind(CHANGE)))) {
+ Object candidateValue = ((AttributeChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ // Same value added on both side in the same container
+ conflict(candidate, PSEUDO);
+ } else if (!isFeatureMapChangeOrMergeableStringAttributeChange(diff, candidate)) {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link AttributeChange} of kind {@link DifferenceKind#DELETE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Delete extends AbstractConflictSearch<AttributeChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Delete(AttributeChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EAttribute feature = diff.getAttribute();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(AttributeChange.class), onFeature(feature), ofKind(MOVE, DELETE)))) {
+ Object candidateValue = ((AttributeChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ if (candidate.getKind() == MOVE) {
+ conflict(candidate, REAL);
+ } else if (diff.getMatch() == candidate.getMatch()) {
+ conflict(candidate, PSEUDO);
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link AttributeChange} of kind {@link DifferenceKind#MOVE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Move extends AbstractConflictSearch<AttributeChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Move(AttributeChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EAttribute feature = diff.getAttribute();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(AttributeChange.class), onFeature(feature), ofKind(MOVE)))) {
+ Object candidateValue = ((AttributeChange)candidate).getValue();
+ if (matchingIndices(diff.getMatch(), feature, value, candidateValue)) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ComparisonIndex.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ComparisonIndex.java
new file mode 100644
index 0000000..24a448c
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ComparisonIndex.java
@@ -0,0 +1,137 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import com.google.common.collect.LinkedHashMultimap;
+import com.google.common.collect.Multimap;
+
+import java.util.Collection;
+import java.util.Collections;
+
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.common.util.URI;
+import org.eclipse.emf.compare.Comparison;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.Match;
+import org.eclipse.emf.compare.ReferenceChange;
+import org.eclipse.emf.ecore.EObject;
+import org.eclipse.emf.ecore.util.EcoreUtil;
+
+/**
+ * Index of diffs in a comparison.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+public final class ComparisonIndex {
+
+ /**
+ * Index of reference changes by their target.
+ */
+ private final Multimap<Object, ReferenceChange> refChangeIndex;
+
+ /**
+ * The indexed comparison.
+ */
+ private final Comparison comparison;
+
+ /**
+ * Constructor.
+ *
+ * @param comparison
+ * The comparison
+ */
+ private ComparisonIndex(Comparison comparison) {
+ this.comparison = comparison;
+ refChangeIndex = LinkedHashMultimap.create();
+ index();
+ }
+
+ /**
+ * Utility method to index a comparison.
+ *
+ * @param comparison
+ * The comparison to index, O(nb. diff)
+ * @param monitor
+ * the monitor
+ * @return The index of the given comparison.
+ */
+ public static ComparisonIndex index(Comparison comparison, Monitor monitor) {
+ monitor.subTask("Indexing differences..."); //$NON-NLS-1$
+ ComparisonIndex index = new ComparisonIndex(comparison);
+ monitor.subTask("Indexing differences... Done."); //$NON-NLS-1$
+ return index;
+ }
+
+ /**
+ * Actually computes the index.
+ */
+ private void index() {
+ for (Diff diff : comparison.getDifferences()) {
+ if (diff instanceof ReferenceChange) {
+ final EObject value = ((ReferenceChange)diff).getValue();
+ Match match = comparison.getMatch(value);
+ if (match != null) {
+ refChangeIndex.put(match, (ReferenceChange)diff);
+ } else {
+ refChangeIndex.put(EcoreUtil.getURI(value), (ReferenceChange)diff);
+ }
+ } else {
+ continue;
+ }
+ }
+ }
+
+ /**
+ * The indexed {@link ReferenceChange}s whose value is in the given Match.
+ *
+ * @param value
+ * The target {@link EObject}
+ * @return A never null collection of {@link ReferenceChange}s whose value is in the same match as the
+ * given EObject, or has the same URI.
+ */
+ public Collection<ReferenceChange> getReferenceChangesByValue(EObject value) {
+ Match match = comparison.getMatch(value);
+ if (refChangeIndex.containsKey(match)) {
+ return refChangeIndex.get(match);
+ }
+ return getReferenceChangesByValueURI(EcoreUtil.getURI(value));
+ }
+
+ /**
+ * The indexed {@link ReferenceChange}s whose value is in the given Match.
+ *
+ * @param valueMatch
+ * The target {@link Match}
+ * @return A never null collection of {@link ReferenceChange}s whose value in the given match.
+ */
+ public Collection<ReferenceChange> getReferenceChangesByValueMatch(Match valueMatch) {
+ if (refChangeIndex.containsKey(valueMatch)) {
+ return refChangeIndex.get(valueMatch);
+ }
+ return Collections.emptyList();
+ }
+
+ /**
+ * The indexed {@link ReferenceChange}s whose value has the given URI (only unresolved proxies are indexed
+ * that way).
+ *
+ * @param valueURI
+ * The URI to look for
+ * @return A never null collection of {@link ReferenceChange}s whose value is unresolved and has the given
+ * URI
+ */
+ public Collection<ReferenceChange> getReferenceChangesByValueURI(URI valueURI) {
+ if (refChangeIndex.containsKey(valueURI)) {
+ return refChangeIndex.get(valueURI);
+ }
+ return Collections.emptyList();
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ConflictSearchFactory.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ConflictSearchFactory.java
new file mode 100644
index 0000000..d0abc3c
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ConflictSearchFactory.java
@@ -0,0 +1,159 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.AttributeChange;
+import org.eclipse.emf.compare.Comparison;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.FeatureMapChange;
+import org.eclipse.emf.compare.ReferenceChange;
+import org.eclipse.emf.compare.ResourceAttachmentChange;
+import org.eclipse.emf.compare.util.CompareSwitch;
+import org.eclipse.emf.ecore.EReference;
+
+/**
+ * Factory for ConflictSearch classes.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+public class ConflictSearchFactory extends CompareSwitch<AbstractConflictSearch<? extends Diff>> {
+
+ /**
+ * Index of reference changes by their target.
+ */
+ private final ComparisonIndex index;
+
+ /**
+ * The monitor that searches instantiated by this factory must use.
+ */
+ private final Monitor monitor;
+
+ /**
+ * Constructor.
+ *
+ * @param comparison
+ * The comparison
+ * @param monitor
+ * The progress monitor
+ */
+ public ConflictSearchFactory(Comparison comparison, Monitor monitor) {
+ checkNotNull(comparison);
+ this.monitor = checkNotNull(monitor);
+ this.index = ComparisonIndex.index(comparison, monitor);
+ }
+
+ @Override
+ public AbstractConflictSearch<AttributeChange> caseAttributeChange(AttributeChange diff) {
+ switch (diff.getKind()) {
+ case ADD:
+ return new AttributeChangeConflictSearch.Add(diff, index, monitor);
+ case CHANGE:
+ return new AttributeChangeConflictSearch.Change(diff, index, monitor);
+ case DELETE:
+ return new AttributeChangeConflictSearch.Delete(diff, index, monitor);
+ case MOVE:
+ return new AttributeChangeConflictSearch.Move(diff, index, monitor);
+ default:
+ throw new IllegalArgumentException();
+ }
+ }
+
+ @Override
+ public AbstractConflictSearch<? extends Diff> caseFeatureMapChange(FeatureMapChange diff) {
+ switch (diff.getKind()) {
+ case ADD:
+ return new FeatureMapChangeConflictSearch.Add(diff, index, monitor);
+ case CHANGE:
+ return new FeatureMapChangeConflictSearch.Change(diff, index, monitor);
+ case DELETE:
+ return new FeatureMapChangeConflictSearch.Delete(diff, index, monitor);
+ case MOVE:
+ return new FeatureMapChangeConflictSearch.Move(diff, index, monitor);
+ default:
+ throw new IllegalArgumentException();
+ }
+ }
+
+ @Override
+ public AbstractConflictSearch<? extends Diff> caseReferenceChange(ReferenceChange diff) {
+ EReference ref = diff.getReference();
+ checkNotNull(ref);
+ if (ref.isContainment()) {
+ return createContainmentSearch(diff);
+ } else {
+ return createNonContaimentSearch(diff);
+ }
+ }
+
+ /**
+ * Create a Conflict Search for containment reference change.
+ *
+ * @param diff
+ * The containment {@link ReferenceChange}
+ * @return A conflict search for the given diff.
+ */
+ private AbstractConflictSearch<? extends Diff> createContainmentSearch(ReferenceChange diff) {
+ switch (diff.getKind()) {
+ case ADD:
+ return new ContainmentRefChangeConflictSearch.Add(diff, index, monitor);
+ case CHANGE:
+ return new ContainmentRefChangeConflictSearch.Change(diff, index, monitor);
+ case DELETE:
+ return new ContainmentRefChangeConflictSearch.Delete(diff, index, monitor);
+ case MOVE:
+ return new ContainmentRefChangeConflictSearch.Move(diff, index, monitor);
+ default:
+ throw new IllegalArgumentException();
+ }
+ }
+
+ /**
+ * Create a Conflict Search for non-containment reference change.
+ *
+ * @param diff
+ * The non-containment {@link ReferenceChange}
+ * @return A conflict search for the given diff.
+ */
+ private AbstractConflictSearch<? extends Diff> createNonContaimentSearch(ReferenceChange diff) {
+ switch (diff.getKind()) {
+ case ADD:
+ return new NonContainmentRefChangeConflictSearch.Add(diff, index, monitor);
+ case CHANGE:
+ return new NonContainmentRefChangeConflictSearch.Change(diff, index, monitor);
+ case DELETE:
+ return new NonContainmentRefChangeConflictSearch.Delete(diff, index, monitor);
+ case MOVE:
+ return new NonContainmentRefChangeConflictSearch.Move(diff, index, monitor);
+ default:
+ throw new IllegalArgumentException();
+ }
+ }
+
+ @Override
+ public AbstractConflictSearch<? extends Diff> caseResourceAttachmentChange(ResourceAttachmentChange diff) {
+ switch (diff.getKind()) {
+ case ADD:
+ return new ResourceAttachmentChangeConflictSearch.Add(diff, index, monitor);
+ case CHANGE:
+ return new ResourceAttachmentChangeConflictSearch.Change(diff, index, monitor);
+ case DELETE:
+ return new ResourceAttachmentChangeConflictSearch.Delete(diff, index, monitor);
+ case MOVE:
+ return new ResourceAttachmentChangeConflictSearch.Move(diff, index, monitor);
+ default:
+ throw new IllegalArgumentException();
+ }
+ }
+
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ContainmentRefChangeConflictSearch.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ContainmentRefChangeConflictSearch.java
new file mode 100644
index 0000000..f8cbee5
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ContainmentRefChangeConflictSearch.java
@@ -0,0 +1,290 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import static com.google.common.base.Predicates.and;
+import static com.google.common.base.Predicates.instanceOf;
+import static org.eclipse.emf.compare.ConflictKind.PSEUDO;
+import static org.eclipse.emf.compare.ConflictKind.REAL;
+import static org.eclipse.emf.compare.DifferenceKind.ADD;
+import static org.eclipse.emf.compare.DifferenceKind.CHANGE;
+import static org.eclipse.emf.compare.DifferenceKind.MOVE;
+import static org.eclipse.emf.compare.internal.utils.ComparisonUtil.isAddOrSetDiff;
+import static org.eclipse.emf.compare.internal.utils.ComparisonUtil.isDeleteOrUnsetDiff;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.ofKind;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.onFeature;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.possiblyConflictingWith;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.valueMatches;
+
+import com.google.common.collect.Iterables;
+
+import java.util.Collection;
+
+import org.eclipse.emf.common.util.EList;
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.DifferenceKind;
+import org.eclipse.emf.compare.ReferenceChange;
+import org.eclipse.emf.ecore.EObject;
+import org.eclipse.emf.ecore.EReference;
+
+/**
+ * Search conflicts for containment {@link ReferenceChange}s.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+public class ContainmentRefChangeConflictSearch {
+
+ /**
+ * Search conflicts for containment {@link ReferenceChange} of kind {@link DifferenceKind#ADD}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Add extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Add(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ EObject value = diff.getValue();
+ EReference feature = diff.getReference();
+
+ // First let's see if non-containment diffs point to the EObject added
+ Collection<ReferenceChange> refChanges = index.getReferenceChangesByValue(value);
+ for (ReferenceChange candidate : Iterables.filter(refChanges, and(possiblyConflictingWith(diff),
+ ofKind(ADD, CHANGE)))) {
+ if (candidate.getReference().isContainment()) {
+ if (candidate.getReference() == feature && candidate.getMatch() == diff.getMatch()
+ && matchingIndices(diff.getMatch(), feature, value, candidate.getValue())) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+
+ // Can conflict with other ADD or SET if isMany() == false
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ if (!feature.isMany()) {
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), onFeature(feature)))) {
+ if (comparison.getEqualityHelper().matchingValues(
+ ((ReferenceChange)candidate).getValue(), diff.getValue())) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for containment {@link ReferenceChange} of kind {@link DifferenceKind#CHANGE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Change extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Change(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ EObject value = diff.getValue();
+ EReference feature = diff.getReference();
+
+ // First let's see if non-containment diffs point to the EObject added
+ Collection<ReferenceChange> refChanges = index.getReferenceChangesByValue(value);
+ for (ReferenceChange candidate : Iterables.filter(refChanges, and(possiblyConflictingWith(diff),
+ ofKind(ADD, CHANGE)))) {
+ if (candidate.getReference().isContainment()) {
+ if (candidate.getReference() == feature && candidate.getMatch() == diff.getMatch()) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+
+ // Can conflict with other ADD or SET if isMany() == false
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ if (!feature.isMany() && isAddOrSetDiff(diff)) {
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), onFeature(feature)))) {
+ if (comparison.getEqualityHelper().matchingValues(
+ ((ReferenceChange)candidate).getValue(), diff.getValue())) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ } else if (!isDeleteOrUnsetDiff(diff)) {
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), onFeature(feature)))) {
+ if (!isDeleteOrUnsetDiff(candidate)
+ && diff.getReference() == ((ReferenceChange)candidate).getReference()) {
+ // Same value added in the same container/reference couple
+ if (matchingIndices(diff.getMatch(), diff.getReference(), value,
+ ((ReferenceChange)candidate).getValue())) {
+ conflict(candidate, PSEUDO);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for containment {@link ReferenceChange} of kind {@link DifferenceKind#DELETE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Delete extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Delete(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ EObject value = diff.getValue();
+
+ // First let's see if non-containment diffs point to the EObject deleted from its parent
+ Collection<ReferenceChange> refChanges = index.getReferenceChangesByValue(value);
+ for (ReferenceChange candidate : Iterables.filter(refChanges, possiblyConflictingWith(diff))) {
+ if (isDeleteOrUnsetDiff(candidate)) {
+ // No conflict here
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+
+ // Now let's look for conflits with containment ReferenceChanges
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), valueMatches(comparison.getEqualityHelper(), value)))) {
+
+ if (isDeleteOrUnsetDiff(candidate)) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+
+ // [381143] Every Diff "under" a containment deletion conflicts with it.
+ final DiffTreeIterator diffIterator = new DiffTreeIterator(comparison.getMatch(value));
+ diffIterator.setFilter(possiblyConflictingWith(diff));
+ diffIterator.setPruningFilter(isContainmentDelete());
+
+ while (diffIterator.hasNext()) {
+ Diff extendedCandidate = diffIterator.next();
+ if (isDeleteOrUnsetDiff(extendedCandidate)) {
+ conflict(extendedCandidate, PSEUDO);
+ } else {
+ conflict(extendedCandidate, REAL);
+ }
+ }
+
+ }
+ }
+
+ /**
+ * Search conflicts for containment {@link ReferenceChange} of kind {@link DifferenceKind#MOVE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Move extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Move(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ EObject value = diff.getValue();
+ EReference feature = diff.getReference();
+
+ // First let's see if non-containment diffs point to the EObject added
+ Collection<ReferenceChange> refChanges = index.getReferenceChangesByValue(value);
+ for (ReferenceChange candidate : Iterables.filter(refChanges, and(possiblyConflictingWith(diff),
+ ofKind(MOVE)))) {
+ if (candidate.getReference().isContainment()) {
+ if (candidate.getReference() == feature && candidate.getMatch() == diff.getMatch()
+ && matchingIndices(diff.getMatch(), feature, value, candidate.getValue())) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ valueMatches(comparison.getEqualityHelper(), value), instanceOf(ReferenceChange.class),
+ onFeature(feature)))) {
+ if (matchingIndices(diff.getMatch(), diff.getReference(), value, ((ReferenceChange)candidate)
+ .getValue())) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/DiffTreeIterator.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/DiffTreeIterator.java
new file mode 100644
index 0000000..4ae1279
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/DiffTreeIterator.java
@@ -0,0 +1,152 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import org.eclipse.emf.common.util.TreeIterator;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.Match;
+import org.eclipse.emf.compare.internal.SubMatchIterator;
+
+/**
+ * A custom iterator that will walk a Match->submatch tree, and allow iteration over the Diffs of these
+ * Matches.
+ * <p>
+ * Since we're walking over Matches but returning Diffs, this is not a good candidate for guava's filters.
+ * We're providing the custom {@link DiffTreeIterator#setFilter(Predicate)} and
+ * {@link DiffTreeIterator#setPruningFilter(Predicate)} to allow for filtering or pruning the the iteration.
+ * </p>
+ *
+ * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a>
+ */
+public class DiffTreeIterator implements Iterator<Diff> {
+ /**
+ * The tree iterator that will walk over our Match tree. Some of the paths can be pruned through the use
+ * of a {@link #pruningFilter}.
+ */
+ private final TreeIterator<Match> subMatchIterator;
+
+ /** An iterator over the differences of the current Match. */
+ private Iterator<Diff> diffIterator;
+
+ /** Current match. */
+ private Match current;
+
+ /** The Diff that will be returned by the next call to {@link #next()}. */
+ private Diff nextDiff;
+
+ /** Only Diffs that meet this criterion will be returned by this iterator. */
+ private Predicate<? super Diff> filter = Predicates.alwaysTrue();
+
+ /**
+ * This particular filter can be used in order to prune a given Match and all of its differences and
+ * sub-differences.
+ */
+ private Predicate<? super Match> pruningFilter = Predicates.alwaysFalse();
+
+ /**
+ * Constructs our iterator given the root of the Match tree to iterate over.
+ *
+ * @param start
+ * Starting match of the tree we'll iterate over.
+ */
+ public DiffTreeIterator(Match start) {
+ this.current = start;
+ this.subMatchIterator = new SubMatchIterator(start);
+ this.diffIterator = start.getDifferences().iterator();
+ }
+
+ /**
+ * Sets the criterion that Diffs must meet to be returned by this iterator.
+ *
+ * @param filter
+ * The filter differences must meet.
+ */
+ public void setFilter(Predicate<? super Diff> filter) {
+ this.filter = filter;
+ }
+
+ /**
+ * Sets the pruning filter for this iterator. Any Match that meets this criterion will be pruned along
+ * with all of its differences and sub-differences.
+ *
+ * @param pruningFilter
+ * The pruning filter for this iterator.
+ */
+ public void setPruningFilter(Predicate<? super Match> pruningFilter) {
+ this.pruningFilter = pruningFilter;
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @see java.util.Iterator#hasNext()
+ */
+ public boolean hasNext() {
+ if (nextDiff != null) {
+ return true;
+ }
+ if (!diffIterator.hasNext()) {
+ computeNextMatch();
+ }
+ while (nextDiff == null && diffIterator.hasNext()) {
+ final Diff next = diffIterator.next();
+ if (filter.apply(next)) {
+ nextDiff = next;
+ }
+ }
+ return nextDiff != null;
+ }
+
+ /**
+ * Computes the next match within the sub-match tree, pruning those that may meet {@link #pruningFilter}.
+ */
+ private void computeNextMatch() {
+ final Match old = current;
+ while (current == old && subMatchIterator.hasNext()) {
+ final Match next = subMatchIterator.next();
+ if (pruningFilter.apply(next)) {
+ subMatchIterator.prune();
+ } else {
+ current = next;
+ diffIterator = current.getDifferences().iterator();
+ }
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @see java.util.Iterator#next()
+ */
+ public Diff next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ final Diff next = nextDiff;
+ nextDiff = null;
+ return next;
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @see java.util.Iterator#remove()
+ */
+ public void remove() {
+ diffIterator.remove();
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/FeatureMapChangeConflictSearch.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/FeatureMapChangeConflictSearch.java
new file mode 100644
index 0000000..7be4e9b
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/FeatureMapChangeConflictSearch.java
@@ -0,0 +1,213 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import static com.google.common.base.Predicates.and;
+import static com.google.common.base.Predicates.instanceOf;
+import static org.eclipse.emf.compare.ConflictKind.PSEUDO;
+import static org.eclipse.emf.compare.ConflictKind.REAL;
+import static org.eclipse.emf.compare.DifferenceKind.ADD;
+import static org.eclipse.emf.compare.DifferenceKind.CHANGE;
+import static org.eclipse.emf.compare.DifferenceKind.DELETE;
+import static org.eclipse.emf.compare.DifferenceKind.MOVE;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.ofKind;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.onFeature;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.possiblyConflictingWith;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.valueMatches;
+
+import com.google.common.collect.Iterables;
+
+import org.eclipse.emf.common.util.EList;
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.DifferenceKind;
+import org.eclipse.emf.compare.FeatureMapChange;
+import org.eclipse.emf.compare.Match;
+import org.eclipse.emf.compare.ReferenceChange;
+import org.eclipse.emf.ecore.EAttribute;
+import org.eclipse.emf.ecore.util.FeatureMap;
+
+/**
+ * Search conflicts for {@link FeatureMapChange}s.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+public class FeatureMapChangeConflictSearch {
+
+ /**
+ * Search conflicts for {@link FeatureMapChange} of kind {@link DifferenceKind#ADD}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Add extends AbstractConflictSearch<FeatureMapChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Add(FeatureMapChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ EAttribute feature = diff.getAttribute();
+ // Only unique features can conflict
+ // FIXME Make sure the above assumption is true
+ if (feature.isUnique()) {
+ Object value = diff.getValue();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(FeatureMapChange.class), onFeature(feature), ofKind(ADD)))) {
+ Object candidateValue = ((FeatureMapChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ // This is a conflict. Is it real?
+ if (matchingIndices(diff.getMatch(), feature, value, candidateValue)) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link ReferenceChange} of kind {@link DifferenceKind#CHANGE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Change extends AbstractConflictSearch<FeatureMapChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Change(FeatureMapChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EAttribute feature = diff.getAttribute();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(FeatureMapChange.class), onFeature(feature), ofKind(CHANGE)))) {
+ Object candidateValue = ((FeatureMapChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ // Same value added on both side in the same container
+ conflict(candidate, PSEUDO);
+ } else if (!isFeatureMapChangeOrMergeableStringAttributeChange(diff, candidate)) {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link FeatureMapChange} of kind {@link DifferenceKind#DELETE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Delete extends AbstractConflictSearch<FeatureMapChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Delete(FeatureMapChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EAttribute feature = diff.getAttribute();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(FeatureMapChange.class), onFeature(feature), ofKind(MOVE, DELETE)))) {
+ Object candidateValue = ((FeatureMapChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ if (candidate.getKind() == MOVE) {
+ conflict(candidate, REAL);
+ } else if (diff.getMatch() == candidate.getMatch()) {
+ conflict(candidate, PSEUDO);
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link FeatureMapChange} of kind {@link DifferenceKind#MOVE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Move extends AbstractConflictSearch<FeatureMapChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Move(FeatureMapChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Match diffMatch = diff.getMatch();
+ FeatureMap.Entry entry = (FeatureMap.Entry)diff.getValue();
+ Object value = entry.getValue();
+ EAttribute feature = diff.getAttribute();
+ EList<Diff> diffsInSameMatch = diffMatch.getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(FeatureMapChange.class), valueMatches(comparison.getEqualityHelper(), value),
+ onFeature(feature), ofKind(MOVE)))) {
+ Object candidateValue = ((FeatureMapChange)candidate).getValue();
+ if (matchingIndices(diff.getMatch(), feature, value, candidateValue)) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/NonContainmentRefChangeConflictSearch.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/NonContainmentRefChangeConflictSearch.java
new file mode 100644
index 0000000..185b618
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/NonContainmentRefChangeConflictSearch.java
@@ -0,0 +1,205 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import static com.google.common.base.Predicates.and;
+import static com.google.common.base.Predicates.instanceOf;
+import static org.eclipse.emf.compare.ConflictKind.PSEUDO;
+import static org.eclipse.emf.compare.ConflictKind.REAL;
+import static org.eclipse.emf.compare.DifferenceKind.ADD;
+import static org.eclipse.emf.compare.DifferenceKind.CHANGE;
+import static org.eclipse.emf.compare.DifferenceKind.DELETE;
+import static org.eclipse.emf.compare.DifferenceKind.MOVE;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.ofKind;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.onFeature;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.possiblyConflictingWith;
+
+import com.google.common.collect.Iterables;
+
+import org.eclipse.emf.common.util.EList;
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.DifferenceKind;
+import org.eclipse.emf.compare.ReferenceChange;
+import org.eclipse.emf.ecore.EReference;
+
+/**
+ * Search conflicts for non-containment {@link ReferenceChange}s.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+public class NonContainmentRefChangeConflictSearch {
+
+ /**
+ * Search conflicts for non-containment {@link ReferenceChange} of kind {@link DifferenceKind#ADD}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Add extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Add(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ EReference feature = diff.getReference();
+ // Only unique features can conflict
+ if (feature.isUnique()) {
+ Object value = diff.getValue();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), onFeature(feature), ofKind(ADD)))) {
+ Object candidateValue = ((ReferenceChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ // This is a conflict. Is it real?
+ if (matchingIndices(diff.getMatch(), feature, value, candidateValue)) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for non-containment {@link ReferenceChange} of kind {@link DifferenceKind#CHANGE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Change extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Change(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EReference feature = diff.getReference();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), onFeature(feature), ofKind(CHANGE)))) {
+ Object candidateValue = ((ReferenceChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ // Same value added on both side in the same container
+ conflict(candidate, PSEUDO);
+ } else if (!isFeatureMapChangeOrMergeableStringAttributeChange(diff, candidate)) {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for non-containment {@link ReferenceChange} of kind {@link DifferenceKind#DELETE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Delete extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Delete(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EReference feature = diff.getReference();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), onFeature(feature), ofKind(MOVE, DELETE)))) {
+ Object candidateValue = ((ReferenceChange)candidate).getValue();
+ if (comparison.getEqualityHelper().matchingValues(value, candidateValue)) {
+ if (candidate.getKind() == MOVE) {
+ conflict(candidate, REAL);
+ } else if (diff.getMatch() == candidate.getMatch()) {
+ conflict(candidate, PSEUDO);
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for non-containment {@link ReferenceChange} of kind {@link DifferenceKind#MOVE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Move extends AbstractConflictSearch<ReferenceChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Move(ReferenceChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void detectConflicts() {
+ Object value = diff.getValue();
+ EReference feature = diff.getReference();
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ReferenceChange.class), onFeature(feature), ofKind(MOVE)))) {
+ Object candidateValue = ((ReferenceChange)candidate).getValue();
+ if (matchingIndices(diff.getMatch(), feature, value, candidateValue)) {
+ conflict(candidate, PSEUDO);
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ResourceAttachmentChangeConflictSearch.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ResourceAttachmentChangeConflictSearch.java
new file mode 100644
index 0000000..5ef9781
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/conflict/ResourceAttachmentChangeConflictSearch.java
@@ -0,0 +1,289 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Obeo.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Obeo - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.emf.compare.internal.conflict;
+
+import static com.google.common.base.Predicates.and;
+import static com.google.common.base.Predicates.instanceOf;
+import static org.eclipse.emf.compare.ConflictKind.REAL;
+import static org.eclipse.emf.compare.DifferenceKind.ADD;
+import static org.eclipse.emf.compare.DifferenceKind.DELETE;
+import static org.eclipse.emf.compare.internal.utils.ComparisonUtil.isDeleteOrUnsetDiff;
+import static org.eclipse.emf.compare.utils.EMFComparePredicates.possiblyConflictingWith;
+
+import com.google.common.collect.Iterables;
+
+import java.util.Collection;
+
+import org.eclipse.emf.common.util.EList;
+import org.eclipse.emf.common.util.Monitor;
+import org.eclipse.emf.compare.Comparison;
+import org.eclipse.emf.compare.ConflictKind;
+import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.DifferenceKind;
+import org.eclipse.emf.compare.DifferenceSource;
+import org.eclipse.emf.compare.Match;
+import org.eclipse.emf.compare.ReferenceChange;
+import org.eclipse.emf.compare.ResourceAttachmentChange;
+import org.eclipse.emf.ecore.EObject;
+import org.eclipse.emf.ecore.resource.Resource;
+
+/**
+ * Search for {@link ResourceAttachmentChange} conflicts.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+public class ResourceAttachmentChangeConflictSearch {
+
+ /**
+ * Search conflicts for {@link ResourceAttachmentChange} of kind {@link DifferenceKind#ADD}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Add extends AbstractConflictSearch<ResourceAttachmentChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Add(ResourceAttachmentChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @Override
+ public void detectConflicts() {
+ // Can conflict with any containment reference change that concerns the same object
+ Match match = diff.getMatch();
+ EObject value = getValue(diff);
+
+ // First let's see if ReferenceChanges point to the EObject moved
+ Collection<ReferenceChange> refChanges = index.getReferenceChangesByValue(value);
+ for (ReferenceChange candidate : Iterables.filter(refChanges, possiblyConflictingWith(diff))) {
+ if (candidate.getReference().isContainment()) {
+ // The element is a new root on one side, but it has been moved to an EObject
+ // container on the other
+ conflict(candidate, REAL);
+ } else {
+ // [477607] DELETE does not necessarily mean that the element is removed from the
+ // model
+ if (value.eContainer() == null) {
+ // The root has been deleted.
+ // Anything other than a delete of this value in a reference is a conflict.
+ if (candidate.getKind() == DELETE) {
+ // No conflict here
+ } else {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+
+ // Then let's see if there's a conflict with another ResourceAttachmentChange
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ResourceAttachmentChange.class)))) {
+ ConflictKind kind = REAL;
+ if (candidate.getKind() == ADD) {
+ final Resource diffRes;
+ final Resource candidateRes;
+ if (diff.getSource() == DifferenceSource.LEFT) {
+ diffRes = match.getLeft().eResource();
+ candidateRes = match.getRight().eResource();
+ } else {
+ diffRes = match.getRight().eResource();
+ candidateRes = match.getLeft().eResource();
+ }
+ if (getMatchResource(diffRes) == getMatchResource(candidateRes)) {
+ kind = ConflictKind.PSEUDO;
+ }
+ }
+ conflict(candidate, kind);
+ }
+ }
+
+ /**
+ * This will be called from
+ * {@link #checkResourceAttachmentConflict(Comparison, ResourceAttachmentChange, Iterable)} for each
+ * ReferenceChange in the comparison model that is on the other side and that impacts the changed
+ * root.
+ *
+ * @param candidate
+ * A reference change that point to the same value as {@code diff}.
+ */
+ protected void checkResourceAttachmentConflict(ReferenceChange candidate) {
+ if (candidate.getReference().isContainment()) {
+ // The element is a new root on one side, but it has been moved to an EObject container on the
+ // other
+ conflict(candidate, ConflictKind.REAL);
+ } else if (diff.getKind() == DifferenceKind.DELETE) {
+ // [477607] DELETE does not necessarily mean that the element is removed from the model
+ EObject o = getRelatedModelElement(diff);
+ if (o == null) {
+ // The root has been deleted.
+ // Anything other than a delete of this value in a reference is a conflict.
+ if (candidate.getKind() != DifferenceKind.DELETE) {
+ conflict(candidate, ConflictKind.REAL);
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link ResourceAttachmentChange} of kind {@link DifferenceKind#CHANGE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Change extends AbstractConflictSearch<ResourceAttachmentChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Change(ResourceAttachmentChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @Override
+ public void detectConflicts() {
+ throw new IllegalStateException("ResourceAttachmentChanges of type CHANGE should not exist."); //$NON-NLS-1$
+ }
+ }
+
+ /**
+ * Search conflicts for {@link ResourceAttachmentChange} of kind {@link DifferenceKind#DELETE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Delete extends AbstractConflictSearch<ResourceAttachmentChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Delete(ResourceAttachmentChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @Override
+ public void detectConflicts() {
+ Match match = diff.getMatch();
+ EObject value = getRelatedModelElement(diff);
+
+ // First let's see if ReferenceChanges point to the EObject moved
+ if (value != null) {
+ Collection<ReferenceChange> refChanges = index.getReferenceChangesByValue(value);
+ for (ReferenceChange candidate : Iterables.filter(refChanges, possiblyConflictingWith(diff))) {
+ if (candidate.getReference().isContainment()) {
+ // The element is a new root on one side, but it has been moved to an EObject
+ // container on the other
+ conflict(candidate, REAL);
+ } else {
+ // [477607] DELETE does not necessarily mean that the element is removed from the
+ // model
+ if (value.eContainer() == null) {
+ // The root has been deleted.
+ // Anything other than a delete of this value in a reference is a conflict.
+ if (candidate.getKind() != DELETE) {
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+ }
+
+ // Then let's see if there's a conflict with another ResourceAttachmentChange
+ EList<Diff> diffsInSameMatch = diff.getMatch().getDifferences();
+ for (Diff candidate : Iterables.filter(diffsInSameMatch, and(possiblyConflictingWith(diff),
+ instanceOf(ResourceAttachmentChange.class)))) {
+ ConflictKind kind = REAL;
+ if (candidate.getKind() == DELETE) {
+ final Resource diffRes;
+ final Resource candidateRes;
+ diffRes = match.getOrigin().eResource();
+ candidateRes = match.getOrigin().eResource();
+ if (getMatchResource(diffRes) == getMatchResource(candidateRes)) {
+ kind = ConflictKind.PSEUDO;
+ }
+ }
+ conflict(candidate, kind);
+ }
+
+ // [381143] Every Diff "under" a root deletion conflicts with it.
+ // [477607] DELETE does not necessarily mean that the element is removed from the model
+ EObject o = getRelatedModelElement(diff);
+ if (o == null || o.eContainer() == null) {
+ for (Diff extendedCandidate : Iterables.filter(match.getAllDifferences(),
+ possiblyConflictingWith(diff))) {
+ if (isDeleteOrUnsetDiff(extendedCandidate)) {
+ conflict(extendedCandidate, ConflictKind.PSEUDO);
+ } else {
+ conflict(extendedCandidate, ConflictKind.REAL);
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Search conflicts for {@link ResourceAttachmentChange} of kind {@link DifferenceKind#MOVE}.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ public static class Move extends AbstractConflictSearch<ResourceAttachmentChange> {
+
+ /**
+ * Constructor.
+ *
+ * @param diff
+ * The diff to search for conflicts
+ * @param index
+ * Comparison index, must not be null
+ * @param monitor
+ * the monitor to report progress to, must not be null
+ */
+ public Move(ResourceAttachmentChange diff, ComparisonIndex index, Monitor monitor) {
+ super(diff, index, monitor);
+ }
+
+ @Override
+ public void detectConflicts() {
+ EObject value = getRelatedModelElement(diff);
+
+ // First let's see if ReferenceChanges point to the EObject moved
+ Collection<ReferenceChange> refChanges = index.getReferenceChangesByValue(value);
+ for (ReferenceChange candidate : Iterables.filter(refChanges, possiblyConflictingWith(diff))) {
+ if (candidate.getReference().isContainment()) {
+ // The element is a new root on one side, but it has been moved to an EObject container on
+ // the other
+ conflict(candidate, REAL);
+ }
+ }
+ }
+ }
+}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/spec/ReferenceChangeSpec.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/spec/ReferenceChangeSpec.java
index de9b046..140e5a4 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/spec/ReferenceChangeSpec.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/spec/ReferenceChangeSpec.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2012, 2015 Obeo.
+ * Copyright (c) 2012, 2016 Obeo.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -90,14 +90,13 @@
@Override
public String toString() {
// @formatter:off
- return Objects.toStringHelper(this)
+ StringBuilder b = new StringBuilder();
+ return b.append(getState()).append(' ').append(getSource()).append(' ').append(getKind()).append(' ').append(
+ Objects.toStringHelper(this)
.add("reference", getReference().getEContainingClass().getName() + "." + getReference().getName())
.add("value", EObjectUtil.getLabel(getValue()))
.add("parentMatch", getMatch().toString())
- .add("match of value", getMatch().getComparison().getMatch(getValue()))
- .add("kind", getKind())
- .add("source", getSource())
- .add("state", getState()).toString();
+ .add("match of value", getMatch().getComparison().getMatch(getValue()))).toString();
// @formatter:on
}
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/EMFComparePredicates.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/EMFComparePredicates.java
index 6948eb7..70e424a 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/EMFComparePredicates.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/EMFComparePredicates.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2012, 2015 Obeo and others.
+ * Copyright (c) 2012, 2016 Obeo and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -12,7 +12,9 @@
*******************************************************************************/
package org.eclipse.emf.compare.utils;
+import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Predicates.and;
+import static org.eclipse.emf.compare.internal.utils.ComparisonUtil.isDeleteOrUnsetDiff;
import com.google.common.base.Predicate;
@@ -37,6 +39,7 @@
import org.eclipse.emf.ecore.EReference;
import org.eclipse.emf.ecore.EStructuralFeature;
import org.eclipse.emf.ecore.EcorePackage;
+import org.eclipse.emf.ecore.util.FeatureMap;
/**
* This class will provide a number of Predicates that can be used to retrieve particular {@link Diff}s from
@@ -540,6 +543,18 @@
}
/**
+ * Accept only diffs that inherit either AttributeChange, ReferenceChange, or FeatureMapChange that
+ * concern the given feature.
+ *
+ * @param feature
+ * Feature to deal with
+ * @return a new predicate that accepts diffs that concern the given feature.
+ */
+ public static Predicate<Diff> onFeature(EStructuralFeature feature) {
+ return new OnFeature(feature);
+ }
+
+ /**
* This can be used to check that a given Diff originates from the given {@code source} side.
*
* @param source
@@ -666,6 +681,50 @@
}
/**
+ * Accept only diffs of the given kinds.
+ *
+ * @param kind1
+ * first kind of diff to accept
+ * @param kind2
+ * second kind of diff to accept
+ * @return The created predicate.
+ */
+ public static Predicate<Diff> ofKind(final DifferenceKind kind1, final DifferenceKind kind2) {
+ checkNotNull(kind1);
+ checkNotNull(kind2);
+ return new Predicate<Diff>() {
+ public boolean apply(Diff input) {
+ return input != null && (input.getKind() == kind1 || input.getKind() == kind2);
+ }
+ };
+ }
+
+ /**
+ * Accept only diffs whose value matches the given value.
+ *
+ * @param helper
+ * The helper to match values
+ * @param value
+ * The value to match
+ * @return The created predicate.
+ */
+ public static Predicate<Diff> valueMatches(final IEqualityHelper helper, final Object value) {
+ return new Predicate<Diff>() {
+ public boolean apply(Diff input) {
+ if (input instanceof ReferenceChange) {
+ return helper.matchingValues(value, ((ReferenceChange)input).getValue());
+ } else if (input instanceof AttributeChange) {
+ return helper.matchingValues(value, ((AttributeChange)input).getValue());
+ } else if (input instanceof FeatureMapChange) {
+ return helper.matchingValues(value, ((FeatureMap.Entry)((FeatureMapChange)input)
+ .getValue()).getValue());
+ }
+ return false;
+ }
+ };
+ }
+
+ /**
* This predicate can be used in order to check that a particular Diff describes either a
* {@link ReferenceChange}, {@link AttributeChange} or {@link FeatureMapChange} for the given
* {@code expectedValue}.
@@ -878,6 +937,17 @@
}
/**
+ * Predicate builder for diffs that can conflict with the given diff.
+ *
+ * @param diff
+ * The diff
+ * @return A predicate that accepts diffs that might conflict with the given diff.
+ */
+ public static Predicate<Diff> possiblyConflictingWith(Diff diff) {
+ return new ConflictCandidateFilter(diff);
+ }
+
+ /**
* This can be used to check whether a given Conflict is of one of the given kind.
*
* @param kinds
@@ -1238,4 +1308,108 @@
}
}
+ /**
+ * Predicate for diffs taht concern a given feature.
+ *
+ * @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
+ */
+ private static class OnFeature implements Predicate<Diff> {
+ /** The feature. */
+ private final EStructuralFeature feature;
+
+ /**
+ * Constructor.
+ *
+ * @param feature
+ * the feature
+ */
+ public OnFeature(EStructuralFeature feature) {
+ this.feature = checkNotNull(feature);
+ }
+
+ /**
+ * Apply the predicate.
+ *
+ * @param input
+ * The diff to filter.
+ * @return true if and only if input concerns the given feature.
+ */
+ public boolean apply(Diff input) {
+ if (input == null) {
+ return false;
+ }
+ boolean apply = false;
+ if (input instanceof ReferenceChange) {
+ apply = ((ReferenceChange)input).getReference() == feature;
+ } else if (input instanceof AttributeChange) {
+ apply = ((AttributeChange)input).getAttribute() == feature;
+ } else if (input instanceof FeatureMapChange) {
+ apply = ((FeatureMapChange)input).getAttribute() == feature;
+ }
+ return apply;
+ }
+ }
+
+ /**
+ * This will be used to filter out the list of potential candidates for conflict with a given Diff.
+ *
+ * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a>
+ */
+ private static final class ConflictCandidateFilter implements Predicate<Diff> {
+ /** The Diff for which we seek conflict candidates. */
+ private final Diff diff;
+
+ /**
+ * Instantiates our filtering Predicate given the reference Diff for which to seek potential
+ * conflicts.
+ *
+ * @param diff
+ * The Diff for which we seek conflict candidates, must not be null.
+ */
+ public ConflictCandidateFilter(Diff diff) {
+ this.diff = checkNotNull(diff);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @see com.google.common.base.Predicate#apply(java.lang.Object)
+ */
+ public boolean apply(Diff input) {
+ return !(input instanceof ResourceLocationChange) && canConflictWith(input);
+ }
+
+ /**
+ * Checks if the given {@link Diff diff1} can be in conflict with the given {@link Diff diff2}.
+ * <p>
+ * Notably, we don't need to try and detect a conflict between two diffs if they're one and the same
+ * or if they have already been detected as a conflicting couple. Likewise, there can be no conflict
+ * if the two diffs originate from the same side.
+ * </p>
+ * <p>
+ * bug 381143 : we'll also remove any containment deletion diff on other Matches from here.
+ * </p>
+ *
+ * @param other
+ * candidate difference to consider for conflict detection.
+ * @return {@code true} if the two given diffs can conflict, {@code false} otherwise.
+ */
+ private boolean canConflictWith(Diff other) {
+ if (diff == other || diff.getSource() == other.getSource()) {
+ return false;
+ }
+ final Conflict conflict = diff.getConflict();
+ boolean canConflict = false;
+ if (conflict == null || !conflict.getDifferences().contains(other)) {
+ if (diff.getMatch() != other.getMatch() && other instanceof ReferenceChange
+ && ((ReferenceChange)other).getReference().isContainment()) {
+ canConflict = !isDeleteOrUnsetDiff(other);
+ } else {
+ canConflict = true;
+ }
+ }
+ return canConflict;
+ }
+ }
+
}
