Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on May 7th, 2013  |  syntax: Java  |  size: 12.45 KB  |  views: 37  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*******************************************************************************
  2.  * Copyright (c) 2012 Obeo.
  3.  * All rights reserved. This program and the accompanying materials
  4.  * are made available under the terms of the Eclipse Public License v1.0
  5.  * which accompanies this distribution, and is available at
  6.  * http://www.eclipse.org/legal/epl-v10.html
  7.  *
  8.  * Contributors:
  9.  *     Obeo - initial API and implementation
  10.  *******************************************************************************/
  11. package org.eclipse.emf.compare.match.eobject;
  12.  
  13. import com.google.common.collect.ImmutableList;
  14. import com.google.common.collect.Iterators;
  15. import com.google.common.collect.Lists;
  16. import com.google.common.collect.Maps;
  17.  
  18. import java.util.Iterator;
  19. import java.util.List;
  20. import java.util.Map;
  21.  
  22. import org.eclipse.emf.common.util.BasicEList;
  23. import org.eclipse.emf.common.util.BasicMonitor;
  24. import org.eclipse.emf.common.util.Monitor;
  25. import org.eclipse.emf.compare.CompareFactory;
  26. import org.eclipse.emf.compare.Comparison;
  27. import org.eclipse.emf.compare.Match;
  28. import org.eclipse.emf.compare.match.eobject.EObjectIndex.Side;
  29. import org.eclipse.emf.compare.match.eobject.internal.ByTypeIndex;
  30. import org.eclipse.emf.ecore.EObject;
  31.  
  32. /**
  33.  * This matcher is using a distance function to match EObject. It guarantees that elements are matched with
  34.  * the other EObject having the lowest distance. If two elements have the same distance regarding the other
  35.  * EObject it will arbitrary pick one. (You should probably not rely on this and make sure your distance only
  36.  * return 0 if both EObject have the very same content). The matcher will try to use the fact that it is a
  37.  * distance to achieve a suitable scalability. It is also build on the following assumptions :
  38.  * <ul>
  39.  * <li>Most EObjects have no difference and have their corresponding EObject on the other sides of the model
  40.  * (right and origins)</li>
  41.  * <li>Two consecutive calls on the distance function with the same parameters will give the same distance.</li>
  42.  * </ul>
  43.  * The scalability you'll get will highly depend on the complexity of the distance function. The
  44.  * implementation is not caching any distance result from two EObjects.
  45.  *
  46.  * @author <a href="mailto:cedric.brun@obeo.fr">Cedric Brun</a>
  47.  */
  48. public class ProximityEObjectMatcher implements IEObjectMatcher, ScopeQuery {
  49.  
  50.         private static final int SEARCH_WINDOW = 300;
  51.  
  52.         /**
  53.          * The index which keep the EObjects.
  54.          */
  55.         private EObjectIndex index;
  56.  
  57.         /**
  58.          * Keeps track of which side was the EObject from.
  59.          */
  60.         private Map<EObject, Side> eObjectsToSide = Maps.newHashMap();
  61.  
  62.         /**
  63.          * Create the matcher using the given distance function.
  64.          *
  65.          * @param meter
  66.          *            a function to measure the distance between two {@link EObject}s.
  67.          */
  68.         public ProximityEObjectMatcher(DistanceFunction meter) {
  69.                 this.index = new ByTypeIndex(meter, this);
  70.         }
  71.  
  72.         /**
  73.          * {@inheritDoc}
  74.          */
  75.  
  76.         public void createMatches(Comparison comparison, Iterator<? extends EObject> leftEObjects,
  77.                         Iterator<? extends EObject> rightEObjects, Iterator<? extends EObject> originEObjects,
  78.                         Monitor monitor) {
  79.  
  80.                 // FIXME: how to create an EMF submonitor
  81.                 Monitor subMonitor = new BasicMonitor();
  82.                 subMonitor.beginTask("indexing objects", 1);
  83.                 int nbElements = 0;
  84.                 int lastSegment = 0;
  85.                 /*
  86.                  * We are iterating through the three sides of the scope at the same time so that index might apply
  87.                  * pre-matching strategies elements if they wish.
  88.                  */
  89.                 while (leftEObjects.hasNext() || rightEObjects.hasNext() || leftEObjects.hasNext()) {
  90.  
  91.                         if (leftEObjects.hasNext()) {
  92.                                 EObject next = leftEObjects.next();
  93.                                 nbElements++;
  94.                                 index.index(next, Side.LEFT);
  95.                                 eObjectsToSide.put(next, Side.LEFT);
  96.                         }
  97.  
  98.                         if (rightEObjects.hasNext()) {
  99.                                 EObject next = rightEObjects.next();
  100.                                 nbElements++;
  101.                                 index.index(next, Side.RIGHT);
  102.                                 eObjectsToSide.put(next, Side.RIGHT);
  103.                         }
  104.  
  105.                         if (originEObjects.hasNext()) {
  106.                                 EObject next = originEObjects.next();
  107.                                 nbElements++;
  108.                                 index.index(next, Side.ORIGIN);
  109.                                 eObjectsToSide.put(next, Side.ORIGIN);
  110.                         }
  111.                         if (nbElements / SEARCH_WINDOW > lastSegment) {
  112.                                 doSomeMatch(comparison, false, subMonitor);
  113.                                 lastSegment++;
  114.                         }
  115.  
  116.                 }
  117.  
  118.                 subMonitor.worked(1);
  119.                 subMonitor.done();
  120.  
  121.                 // FIXME: how to create an EMF submonitor
  122.                 subMonitor = new BasicMonitor();
  123.                 subMonitor.beginTask("matching objects", nbElements);
  124.  
  125.                 doSomeMatch(comparison, true, subMonitor);
  126.  
  127.                 createMatchesForNotFound(comparison);
  128.                 subMonitor.done();
  129.                 restructureMatchModel(comparison);
  130.  
  131.         }
  132.  
  133.         public void doSomeMatch(Comparison comparison, boolean createNoMatch, Monitor subMonitor) {
  134.                 Iterator<EObject> todo = index.getValuesStillThere(Side.LEFT).iterator();
  135.                 while (todo.hasNext()) {
  136.                         Iterator<EObject> remainingResult = matchList(comparison, todo, createNoMatch, subMonitor)
  137.                                         .iterator();
  138.                         if (createNoMatch) {
  139.                                 todo = remainingResult;
  140.                         }
  141.  
  142.                 }
  143.                 todo = index.getValuesStillThere(Side.RIGHT).iterator();
  144.                 while (todo.hasNext()) {
  145.                         Iterator<EObject> remainingResult = matchList(comparison, todo, createNoMatch, subMonitor)
  146.                                         .iterator();
  147.                         if (createNoMatch) {
  148.                                 todo = remainingResult;
  149.                         }
  150.                 }
  151.  
  152.         }
  153.  
  154.         public void createMatchesForNotFound(Comparison comparison) {
  155.                 for (EObject notFound : index.getValuesStillThere(Side.RIGHT)) {
  156.                         areMatching(comparison, null, notFound, null);
  157.                 }
  158.                 for (EObject notFound : index.getValuesStillThere(Side.LEFT)) {
  159.                         areMatching(comparison, notFound, null, null);
  160.                 }
  161.                 for (EObject notFound : index.getValuesStillThere(Side.ORIGIN)) {
  162.                         areMatching(comparison, null, null, notFound);
  163.                 }
  164.         }
  165.  
  166.         /**
  167.          * Process the list of objects matching them. This method might not be able to process all the EObjects if
  168.          * - for instance, their container has not been matched already. Every object which could not be matched
  169.          * is returned in the list.
  170.          *
  171.          * @param comparison
  172.          *            the comparison being built.
  173.          * @param todo
  174.          *            the list of objects to process.
  175.          * @param monitor
  176.          *            a monitor to track progress.
  177.          * @return the list of
  178.          */
  179.         private Iterable<EObject> matchList(Comparison comparison, Iterator<EObject> todo, boolean createNoMatch,
  180.                         Monitor monitor) {
  181.                 List<EObject> remainingResult = Lists.newArrayList();
  182.                 while (todo.hasNext()) {
  183.                         EObject next = todo.next();
  184.                         if (next.eContainer() == null || comparison.getMatch(next.eContainer()) != null
  185.                                         || !isInScope(next.eContainer())) {
  186.                                 if (!tryToMatch(comparison, next, createNoMatch)) {
  187.                                         remainingResult.add(next);
  188.                                 }
  189.                                 monitor.worked(1);
  190.                         } else {
  191.                                 remainingResult.add(next);
  192.                         }
  193.                 }
  194.                 return remainingResult;
  195.         }
  196.  
  197.         /**
  198.          * Try to create a Match. If the match got created, register it (having actual left/right/origin matches
  199.          * or not), if not, then return false. Cases where it might not create the match : if some required data
  200.          * has not been computed yet (for instance if the container of an object has not been matched and if the
  201.          * distance need to know if it's match to find the children matches).
  202.          *
  203.          * @param comparison
  204.          *            the comparison under construction, it will be updated with the new match.
  205.          * @param a
  206.          *            object to match.
  207.          * @return false if the conditions are not fulfilled to create the match, true otherwhise.
  208.          */
  209.         private boolean tryToMatch(Comparison comparison, EObject a, boolean createNoMatch) {
  210.                 Side aSide = eObjectsToSide.get(a);
  211.                 assert aSide != null;
  212.                 Side bSide = Side.LEFT;
  213.                 Side cSide = Side.RIGHT;
  214.                 if (aSide == Side.RIGHT) {
  215.                         bSide = Side.LEFT;
  216.                         cSide = Side.ORIGIN;
  217.                 } else if (aSide == Side.LEFT) {
  218.                         bSide = Side.RIGHT;
  219.                         cSide = Side.ORIGIN;
  220.                 } else if (aSide == Side.ORIGIN) {
  221.                         bSide = Side.LEFT;
  222.                         cSide = Side.RIGHT;
  223.                 }
  224.                 assert aSide != bSide;
  225.                 assert bSide != cSide;
  226.                 assert cSide != aSide;
  227.                 Map<Side, EObject> closests = index.findClosests(comparison, a, aSide);
  228.                 if (closests != null) {
  229.                         EObject lObj = closests.get(bSide);
  230.                         EObject aObj = closests.get(cSide);
  231.                         if (lObj != null || aObj != null) {
  232.                                 // we have at least one other match
  233.                                 areMatching(comparison, closests.get(Side.LEFT), closests.get(Side.RIGHT), closests
  234.                                                 .get(Side.ORIGIN));
  235.                                 return true;
  236.                         } else if (createNoMatch) {
  237.                                 areMatching(comparison, closests.get(Side.LEFT), closests.get(Side.RIGHT), closests
  238.                                                 .get(Side.ORIGIN));
  239.                                 return true;
  240.                         }
  241.                 }
  242.                 return false;
  243.         }
  244.  
  245.         /**
  246.          * Process all the matches of the given comparison and re-attach them to their parent if one is found.
  247.          *
  248.          * @param comparison
  249.          *            the comparison to restructure.
  250.          */
  251.         private void restructureMatchModel(Comparison comparison) {
  252.                 Iterator<Match> it = ImmutableList.copyOf(Iterators.filter(comparison.eAllContents(), Match.class))
  253.                                 .iterator();
  254.  
  255.                 while (it.hasNext()) {
  256.                         Match cur = it.next();
  257.                         EObject possibleContainer = null;
  258.                         if (cur.getLeft() != null) {
  259.                                 possibleContainer = cur.getLeft().eContainer();
  260.                         }
  261.                         if (possibleContainer == null && cur.getRight() != null) {
  262.                                 possibleContainer = cur.getRight().eContainer();
  263.                         }
  264.                         if (possibleContainer == null && cur.getOrigin() != null) {
  265.                                 possibleContainer = cur.getOrigin().eContainer();
  266.                         }
  267.                         Match possibleContainerMatch = comparison.getMatch(possibleContainer);
  268.                         if (possibleContainerMatch != null) {
  269.                                 ((BasicEList<Match>)possibleContainerMatch.getSubmatches()).addUnique(cur);
  270.                         }
  271.                 }
  272.         }
  273.  
  274.         /**
  275.          * Register the given object as a match and add it in the comparison.
  276.          *
  277.          * @param comparison
  278.          *            container for the Match.
  279.          * @param left
  280.          *            left element.
  281.          * @param right
  282.          *            right element
  283.          * @param origin
  284.          *            origin element.
  285.          * @return the created match.
  286.          */
  287.         private Match areMatching(Comparison comparison, EObject left, EObject right, EObject origin) {
  288.                 Match result = CompareFactory.eINSTANCE.createMatch();
  289.                 result.setLeft(left);
  290.                 result.setRight(right);
  291.                 result.setOrigin(origin);
  292.                 ((BasicEList<Match>)comparison.getMatches()).addUnique(result);
  293.                 if (left != null) {
  294.                         index.remove(left, Side.LEFT);
  295.                 }
  296.                 if (right != null) {
  297.                         index.remove(right, Side.RIGHT);
  298.                 }
  299.                 if (origin != null) {
  300.                         index.remove(origin, Side.ORIGIN);
  301.                 }
  302.                 return result;
  303.         }
  304.  
  305.         /**
  306.          * This represent a distance function used by the {@link ProximityEObjectMatcher} to compare EObjects and
  307.          * retrieve the closest EObject from one side to another. Axioms of the distance are supposed to be
  308.          * respected more especially :
  309.          * <ul>
  310.          * <li>symetry : dist(a,b) == dist(b,a)</li>
  311.          * <li>separation :dist(a,a) == 0</li>
  312.          * </ul>
  313.          * Triangular inequality is not leveraged with the current implementation but might be at some point to
  314.          * speed up the indexing. <br/>
  315.          * computing the distance between two EObjects should be a <b> fast operation</b> or the scalability of
  316.          * the whole matching phase will be poor.
  317.          *
  318.          * @author cedric brun <cedric.brun@obeo.fr>
  319.          */
  320.         public interface DistanceFunction {
  321.                 /**
  322.                  * Return the distance between two EObjects. When the two objects should considered as completely
  323.                  * different the implementation is expected to return Integer.MAX_VALUE.
  324.                  *
  325.                  * @param inProgress
  326.                  *            the comparison being processed right now. This might be used for the distance to
  327.                  *            retrieve other matches for instance.
  328.                  * @param a
  329.                  *            first object.
  330.                  * @param b
  331.                  *            second object.
  332.                  * @return the distance between the two EObjects or Integer.MAX_VALUE when the objects are considered
  333.                  *         too different to be the same.
  334.                  */
  335.                 double distance(Comparison inProgress, EObject a, EObject b);
  336.  
  337.                 /**
  338.                  * Check that two objects are equals from the distance function point of view (distance should be 0)
  339.                  * You should prefer this method when you just want to check objects are not equals enabling the
  340.                  * distance to stop sooner.
  341.                  *
  342.                  * @param inProgress
  343.                  *            the comparison being processed right now. This might be used for the distance to
  344.                  *            retrieve other matches for instance.
  345.                  * @param a
  346.                  *            first object.
  347.                  * @param b
  348.                  *            second object.
  349.                  * @return true of the two objects are equals, false otherwise.
  350.                  */
  351.                 boolean areIdentic(Comparison inProgress, EObject a, EObject b);
  352.  
  353.         }
  354.  
  355.         /**
  356.          * {@inheritDoc}
  357.          */
  358.         public boolean isInScope(EObject eContainer) {
  359.                 return eObjectsToSide.get(eContainer) != null;
  360.         }
  361. }