diff options
Diffstat (limited to 'plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/DiffUtil.java')
| -rw-r--r-- | plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/DiffUtil.java | 967 |
1 files changed, 20 insertions, 947 deletions
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/DiffUtil.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/DiffUtil.java index 0a0bed18c..97a4ab054 100644 --- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/DiffUtil.java +++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/utils/DiffUtil.java @@ -10,49 +10,22 @@ *******************************************************************************/ package org.eclipse.emf.compare.utils; -import static com.google.common.collect.Iterables.addAll; -import static com.google.common.collect.Iterables.concat; - import com.google.common.base.Function; -import com.google.common.base.Predicate; -import com.google.common.collect.HashMultiset; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSet; -import com.google.common.collect.Iterables; -import com.google.common.collect.Lists; -import com.google.common.collect.Multiset; -import com.google.common.collect.Sets; -import java.util.Arrays; -import java.util.Collection; import java.util.Collections; -import java.util.HashSet; -import java.util.Iterator; -import java.util.LinkedHashSet; import java.util.List; -import java.util.ListIterator; -import java.util.Set; -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.EMFCompareMessages; -import org.eclipse.emf.compare.Match; -import org.eclipse.emf.compare.ReferenceChange; -import org.eclipse.emf.ecore.EObject; -import org.eclipse.emf.ecore.EReference; -import org.eclipse.emf.ecore.EStructuralFeature; -import org.eclipse.emf.ecore.EcorePackage; -import org.eclipse.emf.ecore.util.InternalEList; +import org.eclipse.emf.compare.internal.utils.ComparisonUtil; /** * This utility class will be used to provide similarity implementations. * * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> + * @deprecated Not intendended to be used by clients */ +@Deprecated public final class DiffUtil { /** This utility class does not need to be instantiated. */ private DiffUtil() { @@ -72,46 +45,7 @@ public final class DiffUtil { * @return The dice coefficient of the two given String's bigrams, ranging from 0 to 1. */ public static double diceCoefficient(String first, String second) { - final char[] str1 = first.toCharArray(); - final char[] str2 = second.toCharArray(); - - final double coefficient; - - if (Arrays.equals(str1, str2)) { - coefficient = 1d; - } else if (str1.length <= 2 || str2.length <= 2) { - int equalChars = 0; - - for (int i = 0; i < Math.min(str1.length, str2.length); i++) { - if (str1[i] == str2[i]) { - equalChars++; - } - } - - int union = str1.length + str2.length; - if (str1.length != str2.length) { - coefficient = (double)equalChars / union; - } else { - coefficient = ((double)equalChars * 2) / union; - } - } else { - Set<String> s1Bigrams = Sets.newHashSet(); - Set<String> s2Bigrams = Sets.newHashSet(); - - for (int i = 0; i < str1.length - 1; i++) { - char[] chars = new char[] {str1[i], str1[i + 1], }; - s1Bigrams.add(String.valueOf(chars)); - } - for (int i = 0; i < str2.length - 1; i++) { - char[] chars = new char[] {str2[i], str2[i + 1], }; - s2Bigrams.add(String.valueOf(chars)); - } - - Set<String> intersection = Sets.intersection(s1Bigrams, s2Bigrams); - coefficient = (2d * intersection.size()) / (s1Bigrams.size() + s2Bigrams.size()); - } - - return coefficient; + return org.eclipse.emf.compare.internal.utils.DiffUtil.diceCoefficient(first, second); } /** @@ -149,23 +83,8 @@ public final class DiffUtil { */ public static <E> List<E> longestCommonSubsequence(Comparison comparison, Iterable<E> ignoredElements, List<E> sequence1, List<E> sequence2) { - final List<E> copy1 = Lists.newArrayList(sequence1); - final List<E> copy2 = Lists.newArrayList(sequence2); - - // Reduce sets - final List<E> prefix = trimPrefix(comparison, ignoredElements, copy1, copy2); - final List<E> suffix = trimSuffix(comparison, ignoredElements, copy1, copy2); - - final List<E> subLCS; - // FIXME extract an interface for the LCS and properly separate these two differently typed - // implementations. - if (copy1.size() > Short.MAX_VALUE || copy2.size() > Short.MAX_VALUE) { - subLCS = intLongestCommonSubsequence(comparison, ignoredElements, copy1, copy2); - } else { - subLCS = shortLongestCommonSubsequence(comparison, ignoredElements, copy1, copy2); - } - - return ImmutableList.copyOf(Iterables.concat(prefix, subLCS, suffix)); + return org.eclipse.emf.compare.internal.utils.DiffUtil.longestCommonSubsequence(comparison, + ignoredElements, sequence1, sequence2); } /** @@ -208,300 +127,11 @@ public final class DiffUtil { */ public static <E> List<E> longestCommonSubsequence(Comparison comparison, List<E> sequence1, List<E> sequence2) { - return longestCommonSubsequence(comparison, Collections.<E> emptyList(), sequence1, sequence2); - } - - /** - * Trims and returns the common prefix of the two given sequences. All ignored elements within or after - * this common prefix will also be trimmed. - * <p> - * Note that the two given sequences will be modified in-place. - * </p> - * - * @param comparison - * This will be used in order to retrieve the Match for EObjects when comparing them. - * @param ignoredElements - * Specifies elements that should be excluded from the subsequences. - * @param sequence1 - * First of the two sequences to consider. - * @param sequence2 - * Second of the two sequences to consider. - * @param <E> - * Type of the sequences content. - * @return The common prefix of the two given sequences, less their ignored elements. As a side note, both - * {@code sequence1} and {@code sequence2} will have been trimmed of their prefix when this - * returns. - */ - private static <E> List<E> trimPrefix(Comparison comparison, Iterable<E> ignoredElements, - List<E> sequence1, List<E> sequence2) { - final IEqualityHelper equalityHelper = comparison.getEqualityHelper(); - final int size1 = sequence1.size(); - final int size2 = sequence2.size(); - - final List<E> prefix = Lists.newArrayList(); - int start1 = 1; - int start2 = 1; - boolean matching = true; - while (start1 <= size1 && start2 <= size2 && matching) { - final E first = sequence1.get(start1 - 1); - final E second = sequence2.get(start2 - 1); - if (equalityHelper.matchingValues(first, second)) { - prefix.add(first); - start1++; - start2++; - } else { - boolean ignore1 = contains(comparison, equalityHelper, ignoredElements, first); - boolean ignore2 = contains(comparison, equalityHelper, ignoredElements, second); - if (ignore1) { - start1++; - } - if (ignore2) { - start2++; - } - if (!ignore1 && !ignore2) { - matching = false; - } - } - } - sequence1.subList(0, start1 - 1).clear(); - sequence2.subList(0, start2 - 1).clear(); - - return prefix; - } - - /** - * Trims and returns the common suffix of the two given sequences. All ignored elements within or before - * this common suffix will also be trimmed. - * <p> - * Note that the two given sequences will be modified in-place. - * </p> - * - * @param comparison - * This will be used in order to retrieve the Match for EObjects when comparing them. - * @param ignoredElements - * Specifies elements that should be excluded from the subsequences. - * @param sequence1 - * First of the two sequences to consider. - * @param sequence2 - * Second of the two sequences to consider. - * @param <E> - * Type of the sequences content. - * @return The common suffix of the two given sequences, less their ignored elements. As a side note, both - * {@code sequence1} and {@code sequence2} will have been trimmed of their suffix when this - * returns. - */ - private static <E> List<E> trimSuffix(Comparison comparison, Iterable<E> ignoredElements, - List<E> sequence1, List<E> sequence2) { - final IEqualityHelper equalityHelper = comparison.getEqualityHelper(); - final int size1 = sequence1.size(); - final int size2 = sequence2.size(); - - final List<E> suffix = Lists.newArrayList(); - int end1 = size1; - int end2 = size2; - boolean matching = true; - while (end1 > 0 && end2 > 0 && matching) { - final E first = sequence1.get(end1 - 1); - final E second = sequence2.get(end2 - 1); - if (equalityHelper.matchingValues(first, second)) { - suffix.add(first); - end1--; - end2--; - } else { - boolean ignore1 = contains(comparison, equalityHelper, ignoredElements, first); - boolean ignore2 = contains(comparison, equalityHelper, ignoredElements, second); - if (ignore1) { - end1--; - } - if (ignore2) { - end2--; - } - if (!ignore1 && !ignore2) { - matching = false; - } - } - } - sequence1.subList(end1, size1).clear(); - sequence2.subList(end2, size2).clear(); - - return Lists.reverse(suffix); - } - - /** - * Checks whether the given {@code sequence} contains the given {@code element} according to the semantics - * of the given {@code equalityHelper}. - * - * @param comparison - * This will be used in order to retrieve the Match for EObjects when comparing them. - * @param equalityHelper - * The {@link EqualityHelper} gives us the necessary semantics for Object matching. - * @param sequence - * The sequence which elements we need to compare with {@code element}. - * @param element - * The element we are seeking in {@code sequence}. - * @param <E> - * Type of the sequence content. - * @return {@code true} if the given {@code sequence} contains an element matching {@code element}, - * {@code false} otherwise. - * @see EqualityHelper#matchingValues(Comparison, Object, Object) - */ - private static <E> boolean contains(Comparison comparison, IEqualityHelper equalityHelper, - Iterable<E> sequence, E element) { - final Iterator<E> iterator = sequence.iterator(); - while (iterator.hasNext()) { - E candidate = iterator.next(); - if (equalityHelper.matchingValues(candidate, element)) { - return true; - } - } - return false; + return org.eclipse.emf.compare.internal.utils.DiffUtil.longestCommonSubsequence(comparison, + sequence1, sequence2); } /** - * This is a classic, single-threaded implementation. We use shorts for the score matrix so as to limit - * the memory cost (we know the max LCS length is not greater than Short#MAX_VALUE). - * - * @param comparison - * This will be used in order to retrieve the Match for EObjects when comparing them. - * @param ignoredElements - * Specifies elements that should be excluded from the subsequences. - * @param sequence1 - * First of the two sequences to consider. - * @param sequence2 - * Second of the two sequences to consider. - * @param <E> - * Type of the sequences content. - * @return The LCS of the two given sequences. Will never be the same instance as one of the input - * sequences. - */ - private static <E> List<E> shortLongestCommonSubsequence(Comparison comparison, - Iterable<E> ignoredElements, List<E> sequence1, List<E> sequence2) { - final IEqualityHelper equalityHelper = comparison.getEqualityHelper(); - final int size1 = sequence1.size(); - final int size2 = sequence2.size(); - - final short[][] matrix = new short[size1 + 1][size2 + 1]; - - // Compute the LCS matrix - for (int i = 1; i <= size1; i++) { - final E first = sequence1.get(i - 1); - for (int j = 1; j <= size2; j++) { - // assume array dereferencing and arithmetics faster than equals - final short current = matrix[i - 1][j - 1]; - final short nextIfNoMatch = (short)Math.max(matrix[i - 1][j], matrix[i][j - 1]); - - if (nextIfNoMatch > current) { - matrix[i][j] = nextIfNoMatch; - } else { - final E second = sequence2.get(j - 1); - if (equalityHelper.matchingValues(first, second) - && !contains(comparison, equalityHelper, ignoredElements, second)) { - matrix[i][j] = (short)(1 + current); - } else { - matrix[i][j] = nextIfNoMatch; - } - } - } - } - - // Traceback the matrix to create the final LCS - int current1 = size1; - int current2 = size2; - final List<E> result = Lists.newArrayList(); - - while (current1 > 0 && current2 > 0) { - final short currentLength = matrix[current1][current2]; - final short nextLeft = matrix[current1][current2 - 1]; - final short nextUp = matrix[current1 - 1][current2]; - if (currentLength > nextLeft && currentLength > nextUp) { - result.add(sequence1.get(current1 - 1)); - current1--; - current2--; - } else if (nextLeft >= nextUp) { - current2--; - } else { - current1--; - } - } - - return Lists.reverse(result); - } - - /** - * This is a classic, single-threaded implementation. We know the max LCS length is greater than - * Short#MAX_VALUE... the score matrix will thus be int-typed, resulting in a huge memory cost. - * - * @param comparison - * This will be used in order to retrieve the Match for EObjects when comparing them. - * @param ignoredElements - * Specifies elements that should be excluded from the subsequences. - * @param sequence1 - * First of the two sequences to consider. - * @param sequence2 - * Second of the two sequences to consider. - * @param <E> - * Type of the sequences content. - * @return The LCS of the two given sequences. Will never be the same instance as one of the input - * sequences. - */ - private static <E> List<E> intLongestCommonSubsequence(Comparison comparison, - Iterable<E> ignoredElements, List<E> sequence1, List<E> sequence2) { - final IEqualityHelper equalityHelper = comparison.getEqualityHelper(); - final int size1 = sequence1.size(); - final int size2 = sequence2.size(); - - final int[][] matrix = new int[size1 + 1][size2 + 1]; - - // Compute the LCS matrix - for (int i = 1; i <= size1; i++) { - final E first = sequence1.get(i - 1); - for (int j = 1; j <= size2; j++) { - // assume array dereferencing and arithmetics faster than equals - final int current = matrix[i - 1][j - 1]; - final int nextIfNoMatch = Math.max(matrix[i - 1][j], matrix[i][j - 1]); - - if (nextIfNoMatch > current) { - matrix[i][j] = nextIfNoMatch; - } else { - final E second = sequence2.get(j - 1); - if (equalityHelper.matchingValues(first, second) - && !contains(comparison, equalityHelper, ignoredElements, second)) { - matrix[i][j] = 1 + current; - } else { - matrix[i][j] = nextIfNoMatch; - } - } - } - } - - // Traceback the matrix to create the final LCS - int current1 = size1; - int current2 = size2; - final List<E> result = Lists.newArrayList(); - - while (current1 > 0 && current2 > 0) { - final int currentLength = matrix[current1][current2]; - final int nextLeft = matrix[current1][current2 - 1]; - final int nextUp = matrix[current1 - 1][current2]; - if (currentLength > nextLeft && currentLength > nextUp) { - result.add(sequence1.get(current1 - 1)); - current1--; - current2--; - } else if (nextLeft >= nextUp) { - current2--; - } else { - current1--; - } - } - - return Lists.reverse(result); - } - - /* - * TODO perf : all "lookups" in source and target could be rewritten by using the lcs elements' matches. - * This may or may not help, should be profiled. - */ - /** * This will try and determine the index at which a given element from the {@code source} list should be * inserted in the {@code target} list. We expect {@code newElement} to be an element from the * {@code source} or to have a Match that allows us to map it to one of the {@code source} list's @@ -539,202 +169,8 @@ public final class DiffUtil { */ public static <E> int findInsertionIndex(Comparison comparison, Iterable<E> ignoredElements, List<E> source, List<E> target, E newElement) { - final IEqualityHelper equalityHelper = comparison.getEqualityHelper(); - - // We assume that "newElement" is in source but not in the target yet - final List<E> lcs; - if (ignoredElements != null) { - lcs = longestCommonSubsequence(comparison, ignoredElements, source, target); - } else { - lcs = longestCommonSubsequence(comparison, source, target); - } - - E firstLCS = null; - E lastLCS = null; - if (lcs.size() > 0) { - firstLCS = lcs.get(0); - lastLCS = lcs.listIterator(lcs.size()).previous(); - } - - final int noLCS = -2; - int currentIndex = -1; - int firstLCSIndex = -1; - int lastLCSIndex = -1; - if (firstLCS == null) { - // We have no LCS - firstLCSIndex = noLCS; - lastLCSIndex = noLCS; - } - - ListIterator<E> sourceIterator = source.listIterator(); - for (int i = 0; sourceIterator.hasNext() && (currentIndex == -1 || firstLCSIndex == -1); i++) { - final E sourceElement = sourceIterator.next(); - if (currentIndex == -1 && equalityHelper.matchingValues(sourceElement, newElement)) { - currentIndex = i; - } - if (firstLCSIndex == -1 && equalityHelper.matchingValues(sourceElement, firstLCS)) { - firstLCSIndex = i; - } - } - // The list may contain duplicates, use a reverse iteration to find the last from LCS. - final int sourceSize = source.size(); - sourceIterator = source.listIterator(sourceSize); - for (int i = sourceSize - 1; sourceIterator.hasPrevious() && lastLCSIndex == -1; i--) { - final E sourceElement = sourceIterator.previous(); - if (lastLCSIndex == -1 && equalityHelper.matchingValues(sourceElement, lastLCS)) { - lastLCSIndex = i; - } - } - - int insertionIndex = -1; - if (firstLCSIndex == noLCS) { - // We have no LCS. The two lists have no element in common. Insert at the very end of the target. - insertionIndex = target.size(); - } else if (currentIndex < firstLCSIndex) { - // The object we are to insert is before the LCS in source. - insertionIndex = insertBeforeLCS(target, equalityHelper, firstLCS); - } else if (currentIndex > lastLCSIndex) { - // The object we are to insert is after the LCS in source. - insertionIndex = findInsertionIndexAfterLCS(target, equalityHelper, lastLCS); - } else { - // Our object is in-between two elements A and B of the LCS in source - insertionIndex = findInsertionIndexWithinLCS(source, target, equalityHelper, lcs, currentIndex); - } - - // We somehow failed to determine the insertion index. Insert at the very end. - if (insertionIndex == -1) { - insertionIndex = target.size(); - } - - return insertionIndex; - } - - /** - * This will be called to try and find the insertion index for an element that is located in-between two - * elements of the LCS between {@code source} and {@code target}. - * - * @param source - * The List from which one element has to be added to the {@code target} list. - * @param target - * The List into which one element from {@code source} has to be added. - * @param equalityHelper - * The equality helper to use for this computation. - * @param lcs - * The lcs between {@code source} and {@code target}. - * @param currentIndex - * Current index (in {@code source} of the element we are to insert into {@code target}. - * @param <E> - * Type of the sequences content. - * @return The index in the target list in which should be inserted that element. - */ - private static <E> int findInsertionIndexWithinLCS(List<E> source, List<E> target, - final IEqualityHelper equalityHelper, final List<E> lcs, int currentIndex) { - int insertionIndex = -1; - /* - * If any element of the subsequence {<index of A>, <index of B>} from source had been in the same - * subsequence in target, it would have been part of the LCS. We thus know none is. - */ - // The insertion index will be just after A in target - - // First, find which element of the LCS is "A" - int lcsIndexOfSubsequenceStart = -1; - for (int i = 0; i < currentIndex; i++) { - final E sourceElement = source.get(i); - - boolean isInLCS = false; - for (int j = lcsIndexOfSubsequenceStart + 1; j < lcs.size() && !isInLCS; j++) { - final E lcsElement = lcs.get(j); - - if (equalityHelper.matchingValues(sourceElement, lcsElement)) { - isInLCS = true; - lcsIndexOfSubsequenceStart++; - } - } - } - - // 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; - - // Then, find the index of "A" in target - for (int i = 0; i < target.size() && insertionIndex == -1; i++) { - final E targetElement = target.get(i); - - if (equalityHelper.matchingValues(targetElement, subsequenceStart)) { - if (duplicatesToGo > 0) { - duplicatesToGo--; - } else { - insertionIndex = i + 1; - } - } - } - - return insertionIndex; - } - - /** - * This will be called when we are to insert an element after the LCS in the {@code target} list. - * - * @param target - * The List into which one element has to be added. - * @param equalityHelper - * The equality helper to use for this computation. - * @param lastLCS - * The last element of the LCS. - * @param <E> - * Type of the sequences content. - * @return The index to use for insertion into {@code target} in order to add an element just after the - * LCS. - */ - private static <E> int findInsertionIndexAfterLCS(List<E> target, IEqualityHelper equalityHelper, - E lastLCS) { - int insertionIndex = -1; - // The insertion index will be inside the subsequence {<LCS end>, <list.size()>} in target. - /* - * We'll insert it just after the LCS end : there cannot be any common element between the two lists - * "after" the LCS since it would be part of the LCS itself. - */ - for (int i = target.size() - 1; i >= 0 && insertionIndex == -1; i--) { - final E targetElement = target.get(i); - if (equalityHelper.matchingValues(targetElement, lastLCS)) { - // We've reached the last element of the LCS in target. insert after it. - insertionIndex = i + 1; - } - } - return insertionIndex; - } - - /** - * This will be called when we are to insert an element before the LCS in the {@code target} list. - * - * @param target - * The List into which one element has to be added. - * @param equalityHelper - * The equality helper to use for this computation. - * @param firstLCS - * The first element of the LCS. - * @param <E> - * Type of the sequences content. - * @return The index to use for insertion into {@code target} in order to add an element just before the - * LCS. - */ - private static <E> int insertBeforeLCS(List<E> target, IEqualityHelper equalityHelper, E firstLCS) { - int insertionIndex = -1; - // The insertion index will be inside the subsequence {0, <LCS start>} in target - /* - * We'll insert it just before the LCS start : there cannot be any common element between the two - * lists "before" the LCS since it would be part of the LCS itself. - */ - for (int i = 0; i < target.size() && insertionIndex == -1; i++) { - final E targetElement = target.get(i); - - if (equalityHelper.matchingValues(targetElement, firstLCS)) { - // We've reached the first element from the LCS in target. Insert here - insertionIndex = i; - } - } - return insertionIndex; + return org.eclipse.emf.compare.internal.utils.DiffUtil.findInsertionIndex(comparison, + ignoredElements, source, target, newElement); } /** @@ -779,7 +215,8 @@ public final class DiffUtil { */ public static <E> int findInsertionIndex(Comparison comparison, List<E> source, List<E> target, E newElement) { - return findInsertionIndex(comparison, null, source, target, newElement); + return org.eclipse.emf.compare.internal.utils.DiffUtil.findInsertionIndex(comparison, source, target, + newElement); } /** @@ -799,194 +236,22 @@ public final class DiffUtil { * inferred from {@code rightToLeft}. * @see #findInsertionIndex(Comparison, Iterable, List, List, Object) */ - @SuppressWarnings("unchecked") public static int findInsertionIndex(Comparison comparison, Diff diff, boolean rightToLeft) { - final EStructuralFeature feature; - final Object value; - if (diff instanceof AttributeChange) { - feature = ((AttributeChange)diff).getAttribute(); - value = ((AttributeChange)diff).getValue(); - } else if (diff instanceof ReferenceChange) { - feature = ((ReferenceChange)diff).getReference(); - value = ((ReferenceChange)diff).getValue(); - } else { - throw new IllegalArgumentException(EMFCompareMessages.getString( - "DiffUtil.IllegalDiff", diff.eClass().getName())); //$NON-NLS-1$ - } - if (!feature.isMany()) { - throw new IllegalArgumentException(EMFCompareMessages.getString( - "DiffUtil.IllegalFeature", feature.getName())); //$NON-NLS-1$ - } - final Match match = diff.getMatch(); - - final EObject expectedContainer; - if (feature instanceof EReference && ((EReference)feature).isContainment() - && diff.getKind() == DifferenceKind.MOVE) { - // The value can only be an EObject, and its match cannot be null. - // If any of these two assumptions is wrong, something went horribly awry beforehand. - final Match valueMatch = comparison.getMatch((EObject)value); - - final Match targetContainerMatch; - // If it exists, use the source side's container as reference - if (rightToLeft && valueMatch.getRight() != null) { - targetContainerMatch = comparison.getMatch(valueMatch.getRight().eContainer()); - } else if (!rightToLeft && valueMatch.getLeft() != null) { - targetContainerMatch = comparison.getMatch(valueMatch.getLeft().eContainer()); - } else { - // Otherwise, the value we're moving on one side has been removed from its source side. - targetContainerMatch = comparison.getMatch(valueMatch.getOrigin().eContainer()); - } - if (rightToLeft) { - expectedContainer = targetContainerMatch.getLeft(); - } else { - expectedContainer = targetContainerMatch.getRight(); - } - } else if (rightToLeft) { - expectedContainer = match.getLeft(); - } else { - expectedContainer = match.getRight(); - } - - final List<Object> sourceList = getSourceList(diff, feature, rightToLeft); - final List<Object> targetList; - - if (expectedContainer != null) { - final List<Object> temp = (List<Object>)ReferenceUtil.safeEGet(expectedContainer, feature); - if (feature == EcorePackage.Literals.ECLASS__ESUPER_TYPES - || feature == EcorePackage.Literals.EOPERATION__EEXCEPTIONS) { - // workaround 394286 - targetList = temp; - } else if (temp instanceof InternalEList<?>) { - // EMF ignores the "resolve" flag for containment lists... - targetList = ((InternalEList<Object>)temp).basicList(); - } else { - targetList = temp; - } - } else { - targetList = ImmutableList.of(); - } - - Iterable<Object> ignoredElements = Iterables.concat(computeIgnoredElements(targetList, diff), - Collections.singleton(value)); - // We know we'll have to iterate quite a number of times on this one. - ignoredElements = Lists.newArrayList(ignoredElements); - - return DiffUtil.findInsertionIndex(comparison, ignoredElements, sourceList, targetList, value); - } - - /** - * Retrieves the "source" list of the given {@code diff}. This will be different according to the kind of - * change and the direction of the merging. - * - * @param diff - * The diff for which merging we need a 'source'. - * @param feature - * The feature on which the merging is actually taking place. - * @param rightToLeft - * Direction of the merging. {@code true} if the merge is to be done on the left side, making - * 'source' the right side, {@code false} otherwise. - * @return The list that should be used as a source for this merge. May be empty, but never - * <code>null</code>. - */ - @SuppressWarnings("unchecked") - private static List<Object> getSourceList(Diff diff, EStructuralFeature feature, boolean rightToLeft) { - final Match match = diff.getMatch(); - final List<Object> sourceList; - final EObject expectedContainer; - - if (diff.getKind() == DifferenceKind.MOVE) { - final boolean undoingLeft = rightToLeft && diff.getSource() == DifferenceSource.LEFT; - final boolean undoingRight = !rightToLeft && diff.getSource() == DifferenceSource.RIGHT; - - if ((undoingLeft || undoingRight) && match.getOrigin() != null) { - expectedContainer = match.getOrigin(); - } else if (rightToLeft) { - expectedContainer = match.getRight(); - } else { - expectedContainer = match.getLeft(); - } - - } else { - if (match.getOrigin() != null && diff.getKind() == DifferenceKind.DELETE) { - expectedContainer = match.getOrigin(); - } else if (rightToLeft) { - expectedContainer = match.getRight(); - } else { - expectedContainer = match.getLeft(); - } - } - - if (expectedContainer != null) { - final List<Object> temp = (List<Object>)ReferenceUtil.safeEGet(expectedContainer, feature); - if (feature == EcorePackage.Literals.ECLASS__ESUPER_TYPES - || feature == EcorePackage.Literals.EOPERATION__EEXCEPTIONS) { - // workaround 394286 - sourceList = temp; - } else if (temp instanceof InternalEList<?>) { - // EMF ignores the "resolve" flag for containment lists... - sourceList = ((InternalEList<Object>)temp).basicList(); - } else { - sourceList = temp; - } - } else { - sourceList = ImmutableList.of(); - } - - return sourceList; - } - - /** - * When computing the insertion index of an element in a list, we need to ignore all elements present in - * that list that feature unresolved Diffs on the same feature. - * - * @param candidates - * The sequence in which we need to compute an insertion index. - * @param diff - * The diff we are computing an insertion index for. - * @param <E> - * Type of the list's content. - * @return The list of elements that should be ignored when computing the insertion index for a new - * element in {@code candidates}. - */ - private static <E> Iterable<E> computeIgnoredElements(Iterable<E> candidates, final Diff diff) { - final Match match = diff.getMatch(); - final Iterable<? extends Diff> filteredCandidates = Lists.newArrayList(match.getDifferences()); - final EStructuralFeature feature; - if (diff instanceof AttributeChange) { - feature = ((AttributeChange)diff).getAttribute(); - } else if (diff instanceof ReferenceChange) { - feature = ((ReferenceChange)diff).getReference(); - } else { - return Collections.emptyList(); - } - - final Set<E> ignored = Sets.newLinkedHashSet(); - for (E candidate : candidates) { - if (candidate instanceof EObject) { - final Iterable<? extends Diff> differences = match.getComparison().getDifferences( - (EObject)candidate); - if (Iterables.any(differences, new UnresolvedDiffMatching(feature, candidate))) { - ignored.add(candidate); - } - } else { - if (Iterables.any(filteredCandidates, new UnresolvedDiffMatching(feature, candidate))) { - ignored.add(candidate); - } - } - } - return ignored; + return org.eclipse.emf.compare.internal.utils.DiffUtil.findInsertionIndex(comparison, diff, + rightToLeft); } /** * When merging a {@link Diff}, returns the sub diffs of this given diff, and all associated diffs (see * {@link DiffUtil#getAssociatedDiffs(Iterable, boolean, Diff)}) of these sub diffs. * <p> - * If the diff is an {@link AttributeChange} or a @{code ResourceAttachmentChange}, this method will - * return an empty iterable. + * If the diff is an {@link org.eclipse.emf.compare.AttributeChange} or a @{code + * ResourceAttachmentChange}, this method will return an empty iterable. * </p> * <p> - * If the diff is a {@link ReferenceChange} this method will return all differences contained in the match - * that contains the value of the reference change, and all associated diffs of these differences. + * If the diff is a {@link org.eclipse.emf.compare.ReferenceChange} this method will return all + * differences contained in the match that contains the value of the reference change, and all associated + * diffs of these differences. * </p> * * @param leftToRight @@ -996,112 +261,7 @@ public final class DiffUtil { * @since 3.0 */ public static Function<Diff, Iterable<Diff>> getSubDiffs(final boolean leftToRight) { - return getSubDiffs(leftToRight, new LinkedHashSet<Diff>()); - } - - /** - * When merging a {@link Diff}, returns the sub diffs of this given diff, and all associated diffs (see - * {@link DiffUtil#getAssociatedDiffs(Iterable, boolean, Diff)}) of these sub diffs. - * <p> - * If the diff is an {@link AttributeChange} or a @{code ResourceAttachmentChange}, this method will - * return an empty iterable. - * </p> - * <p> - * If the diff is a {@link ReferenceChange} this method will return all differences contained in the match - * that contains the value of the reference change, and all associated diffs of these differences. - * </p> - * - * @param leftToRight - * the direction of merge. - * @param processedDiffs - * a set of diffs which have been already processed. - * @return an iterable containing the sub diffs of this given diff, and all associated diffs of these sub - * diffs. - * @since 3.0 - */ - private static Function<Diff, Iterable<Diff>> getSubDiffs(final boolean leftToRight, - final LinkedHashSet<Diff> processedDiffs) { - return new Function<Diff, Iterable<Diff>>() { - public Iterable<Diff> apply(Diff diff) { - if (diff instanceof ReferenceChange) { - Match matchOfValue = diff.getMatch().getComparison().getMatch( - ((ReferenceChange)diff).getValue()); - if (((ReferenceChange)diff).getReference().isContainment()) { - final Iterable<Diff> subDiffs = matchOfValue.getAllDifferences(); - addAll(processedDiffs, subDiffs); - final Iterable<Diff> associatedDiffs = getAssociatedDiffs(diff, subDiffs, - processedDiffs, leftToRight); - return ImmutableSet.copyOf(concat(subDiffs, associatedDiffs)); - } - } - return ImmutableSet.of(); - } - }; - } - - /** - * When merging a {@link Diff}, returns the associated diffs of the sub diffs of the diff, and all sub - * diffs (see {@link DiffUtil#getSubDiffs(boolean)}) of these associated diffs. - * <p> - * The associated diffs of a diff are : - * <p> - * - {@link Diff#getRequiredBy()} if the source of the diff is the left side and the direction of the - * merge is right to left. - * </p> - * <p> - * - {@link Diff#getRequiredBy()} if the source of the diff is the right side and the direction of the - * merge is left to right. - * </p> - * <p> - * - {@link Diff#getRequires()} if the source of the diff is the left side and the direction of the merge - * is left to right. - * </p> - * <p> - * - {@link Diff#getRequires()} if the source of the diff is the right side and the direction of the merge - * is right to left. - * </p> - * </p> - * - * @param diffRoot - * the given diff. - * @param subDiffs - * the iterable of sub diffs for which we want the associated diffs. - * @param processedDiffs - * a set of diffs which have been already processed. - * @param leftToRight - * the direction of merge. - * @return an iterable containing the associated diffs of these given sub diffs, and all sub diffs of - * these associated diffs. - * @since 3.0 - */ - private static Iterable<Diff> getAssociatedDiffs(final Diff diffRoot, Iterable<Diff> subDiffs, - LinkedHashSet<Diff> processedDiffs, boolean leftToRight) { - Collection<Diff> associatedDiffs = new HashSet<Diff>(); - for (Diff diff : subDiffs) { - final Collection<Diff> reqs = new LinkedHashSet<Diff>(); - if (leftToRight) { - if (diff.getSource() == DifferenceSource.LEFT) { - reqs.addAll(diff.getRequires()); - } else { - reqs.addAll(diff.getRequiredBy()); - } - } else { - if (diff.getSource() == DifferenceSource.LEFT) { - reqs.addAll(diff.getRequiredBy()); - } else { - reqs.addAll(diff.getRequires()); - } - } - reqs.remove(diffRoot); - associatedDiffs.addAll(reqs); - for (Diff req : reqs) { - if (!Iterables.contains(subDiffs, req) && !processedDiffs.contains(req)) { - processedDiffs.add(req); - addAll(associatedDiffs, getSubDiffs(leftToRight, processedDiffs).apply(req)); - } - } - } - return associatedDiffs; + return ComparisonUtil.getSubDiffs(leftToRight); } /** @@ -1142,91 +302,4 @@ public final class DiffUtil { boolean leftToRight) { return Collections.emptyList(); } - - /** - * This can be used to check whether a given Diff affects a value for which we can find another, - * unresolved Diff on a given Feature. - * - * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> - */ - private static class UnresolvedDiffMatching implements Predicate<Diff> { - /** Feature on which we expect an unresolved diff. */ - private final EStructuralFeature feature; - - /** Element for which we expect an unresolved diff. */ - private final Object element; - - /** - * Constructs a predicate that can be used to retrieve all unresolved diffs that apply to the given - * {@code feature} and {@code element}. - * - * @param feature - * The feature which our diffs must concern. - * @param element - * The element which must be our diffs' target. - */ - public UnresolvedDiffMatching(EStructuralFeature feature, Object element) { - this.feature = feature; - this.element = element; - } - - /** - * {@inheritDoc} - * - * @see com.google.common.base.Predicate#apply(java.lang.Object) - */ - public boolean apply(Diff input) { - boolean apply = false; - if (input instanceof AttributeChange) { - apply = input.getState() == DifferenceState.UNRESOLVED - && ((AttributeChange)input).getAttribute() == feature - && matchingValues((AttributeChange)input, element); - } else if (input instanceof ReferenceChange) { - apply = input.getState() == DifferenceState.UNRESOLVED - && ((ReferenceChange)input).getReference() == feature - && matchingValues((ReferenceChange)input, element); - } else { - apply = false; - } - return apply; - } - - /** - * Checks that the value of the given diff matches <code>value</code>, resorting to the equality - * helper if needed. - * - * @param diff - * The diff which value we need to check. - * @param value - * The expected value of <code>diff</code> - * @return <code>true</code> if the value matches. - */ - private boolean matchingValues(AttributeChange diff, Object value) { - if (diff.getValue() == value) { - return true; - } - // Only resort to the equality helper as "last resort" - final IEqualityHelper helper = diff.getMatch().getComparison().getEqualityHelper(); - return helper.matchingAttributeValues(diff.getValue(), value); - } - - /** - * Checks that the value of the given diff matches <code>value</code>, resorting to the equality - * helper if needed. - * - * @param diff - * The diff which value we need to check. - * @param value - * The expected value of <code>diff</code> - * @return <code>true</code> if the value matches. - */ - private boolean matchingValues(ReferenceChange diff, Object value) { - if (diff.getValue() == value) { - return true; - } - // Only resort to the equality helper as "last resort" - final IEqualityHelper helper = diff.getMatch().getComparison().getEqualityHelper(); - return helper.matchingValues(diff.getValue(), value); - } - } } |