Moves with non-unique values and addition/deletions of duplicates
We cannot always ignore the "moved" values when computing the LCS. ADD
and DELETE of duplicates of the moved one need to be taken into account.
Change-Id: I5e97b89ae34f9dfd1ef7b9db69c1bf7feb3a5f54
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/DiffUtil.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/DiffUtil.java
index 706a744..23ea9b9 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/DiffUtil.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/DiffUtil.java
@@ -16,11 +16,9 @@
import static com.google.common.collect.Lists.newArrayList;
import com.google.common.base.Predicate;
-import com.google.common.collect.HashMultiset;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
-import com.google.common.collect.Multiset;
import com.google.common.collect.Sets;
import java.lang.ref.WeakReference;
@@ -917,23 +915,22 @@
}
if (lcsIndexOfSubsequenceStart > -1) {
- // Do we have duplicates before A in the lcs?
- final Multiset<E> dupesLCS = HashMultiset.create(lcs.subList(0, lcsIndexOfSubsequenceStart + 1));
- final E subsequenceStart = lcs.get(lcsIndexOfSubsequenceStart);
- int duplicatesToGo = dupesLCS.count(subsequenceStart) - 1;
+ // Now browse our target list to find the index of that lcs element in it
+ int targetCursor = 0;
+ for (int i = 0; i <= lcsIndexOfSubsequenceStart; i++) {
+ E lcsElement = lcs.get(i);
- // Then, find the index of "A" in target
- for (int i = 0; i < target.size() && insertionIndex == -1; i++) {
- final E targetElement = target.get(i);
+ boolean isInLCS = false;
+ for (int j = targetCursor; j < target.size() && !isInLCS; j++) {
+ E targetElement = target.get(j);
- if (equalityHelper.matchingValues(subsequenceStart, targetElement)) {
- if (duplicatesToGo > 0) {
- duplicatesToGo--;
- } else {
- insertionIndex = i + 1;
+ if (equalityHelper.matchingValues(lcsElement, targetElement)) {
+ isInLCS = true;
+ targetCursor = j + 1;
}
}
}
+ insertionIndex = targetCursor;
}
return insertionIndex;
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/AttributeChangeMerger.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/AttributeChangeMerger.java
index 200e362..c7ac57d 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/AttributeChangeMerger.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/AttributeChangeMerger.java
@@ -25,7 +25,9 @@
import org.eclipse.emf.compare.AttributeChange;
import org.eclipse.emf.compare.Comparison;
import org.eclipse.emf.compare.Diff;
+import org.eclipse.emf.compare.DifferenceKind;
import org.eclipse.emf.compare.DifferenceSource;
+import org.eclipse.emf.compare.DifferenceState;
import org.eclipse.emf.compare.Match;
import org.eclipse.emf.compare.internal.ThreeWayTextDiff;
import org.eclipse.emf.compare.internal.utils.DiffUtil;
@@ -372,10 +374,39 @@
Set<Object> ignoredElements = DiffUtil.computeIgnoredElements(comparison, equalityHelper, targetList,
diff, rightToLeft);
- if (ignoredElements.isEmpty()) {
- ignoredElements = Collections.singleton(valueToMove);
- } else {
- ignoredElements.add(valueToMove);
+ // We're "moving" an element, so it is present on both sides and should not be part of the LCS
+ // computation since it is our move target. However, if we also have a diff on that same value, we do
+ // not have to ignore it.
+ Iterator<Diff> siblingDiffs = diff.getMatch().getDifferences().stream()
+ .filter(AttributeChange.class::isInstance)
+ .filter(d -> d.getState() == DifferenceState.UNRESOLVED && equalityHelper
+ .matchingAttributeValues(valueToMove, ((AttributeChange)d).getValue()))
+ .iterator();
+ boolean ignoreValue = true;
+ while (siblingDiffs.hasNext()) {
+ Diff sibling = siblingDiffs.next();
+ if (sibling.getKind() == DifferenceKind.ADD) {
+ // We have another duplicate of that value on this side that corresponds to none on the other
+ if (sibling.getSource() == DifferenceSource.LEFT && rightToLeft) {
+ ignoreValue = false;
+ } else if (sibling.getSource() == DifferenceSource.RIGHT && !rightToLeft) {
+ ignoreValue = false;
+ }
+ } else if (sibling.getKind() == DifferenceKind.DELETE) {
+ // reverse the above
+ if (sibling.getSource() == DifferenceSource.LEFT && !rightToLeft) {
+ ignoreValue = false;
+ } else if (sibling.getSource() == DifferenceSource.RIGHT && rightToLeft) {
+ ignoreValue = false;
+ }
+ }
+ }
+ if (ignoreValue) {
+ if (ignoredElements.isEmpty()) {
+ ignoredElements = Collections.singleton(valueToMove);
+ } else {
+ ignoredElements.add(valueToMove);
+ }
}
List<Object> lcs = DiffUtil.longestCommonSubsequence(comparison, ignoredElements, sourceList,
copyTarget);
