X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=org.simantics.interop%2Fsrc%2Forg%2Fsimantics%2Finterop%2Ftest%2FGraphComparator.java;h=7ea8f4db055c02fa00d8c685c47e9621113e2294;hb=88fcf43b9eb2e217b50bf67cee58edaef4637a59;hp=aa2ddee72f84c3cd23dbb25cdc32768deb8852a3;hpb=97c68766209d534318dfc146727eb5670fca848e;p=simantics%2Finterop.git diff --git a/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java b/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java index aa2ddee..7ea8f4d 100644 --- a/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java +++ b/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java @@ -8,6 +8,8 @@ * * Contributors: * Foster Wheeler Energia Oy - initial API and implementation + * VTT Technical Research Centre of Finland - Improvements to comparison. + * Semantum Oy - Improvements to comparison, various bug fixes. *******************************************************************************/ package org.simantics.interop.test; @@ -20,9 +22,13 @@ import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; +import java.util.Map.Entry; import java.util.Set; import java.util.Stack; +import org.eclipse.core.runtime.IProgressMonitor; +import org.eclipse.core.runtime.NullProgressMonitor; +import org.simantics.databoard.Bindings; import org.simantics.db.ReadGraph; import org.simantics.db.Resource; import org.simantics.db.Session; @@ -30,6 +36,8 @@ import org.simantics.db.Statement; import org.simantics.db.common.request.ReadRequest; import org.simantics.db.common.utils.NameUtils; import org.simantics.db.exception.DatabaseException; +import org.simantics.db.request.Read; +import org.simantics.interop.test.GraphChanges.Modification; import org.simantics.layer0.Layer0; import org.simantics.utils.datastructures.BijectionMap; import org.simantics.utils.datastructures.MapList; @@ -53,21 +61,21 @@ public class GraphComparator { private Resource r1; private Resource r2; - private Set strong = new HashSet(); // List of relations that identify object, if subject is already identified. - private List traversed = new ArrayList(); // list of relations that are traversed (and tested) - private List tested = new ArrayList(); // list of relations that are tested, but not traversed - private List nonTraversed = new ArrayList(); // list of relations that are not traversed - private List nonTested = new ArrayList(); // list of relations that are not tested - - private List changes1 = new ArrayList(); - private List changes2 = new ArrayList(); - private List> modifications = new ArrayList>(); - private Set changes1Set = new HashSet(); - private Set changes2Set = new HashSet(); - private Set> modificationsSet = new HashSet>(); + private Set strong = new HashSet<>(); // List of relations that identify object, if subject is already identified. + private List traversed = new ArrayList<>(); // list of relations that are traversed (and tested) + private List tested = new ArrayList<>(); // list of relations that are tested, but not traversed + private List nonTraversed = new ArrayList<>(); // list of relations that are not traversed + private List nonTested = new ArrayList<>(); // list of relations that are not tested + + private List changes1 = new ArrayList<>(); + private List changes2 = new ArrayList<>(); + private List modifications = new ArrayList<>(); + private Set changes1Set = new HashSet<>(); + private Set changes2Set = new HashSet<>(); + private Set modificationsSet = new HashSet<>(); - private BijectionMap comparableStatements = new BijectionMap(); - private BijectionMap comparableResources = new BijectionMap(); + private BijectionMap comparableStatements = new BijectionMap<>(); + private BijectionMap comparableResources = new BijectionMap<>(); private Set processedResources = new HashSet(); @@ -79,11 +87,16 @@ public class GraphComparator { private Set nonMatchedLeft = new HashSet(); private Set nonMatchedRight = new HashSet(); + private long iter = 0; + private long maxIter = -1; + // runtime attributes private ReadGraph g; private Layer0 b; + private boolean mapLiterals = true; + public GraphComparator(Resource r1, Resource r2) { this.r1 = r1; this.r2 = r2; @@ -149,10 +162,16 @@ public class GraphComparator { } public void addComparableResources(Resource r1, Resource r2) { + if (DEBUG) + System.out.println("Preset " + r1 + " = " + r2); comparableResources.map(r1, r2); } public void addComparableResources(BijectionMap matching) { + if (DEBUG) { + for (Entry entry : matching.getEntries()) + System.out.println("Preset " + entry.getKey() + " = " + entry.getValue()); + } comparableResources.addAll(matching); } @@ -172,10 +191,75 @@ public class GraphComparator { nonMatchedRight.add(r); } + public long getMaxIter() { + return maxIter; + } + + /** + * Sets maximum iteration done on a single DB transaction. Affects only test(Session) methods. + * Default value is -1, which disables iteration limit. + * Note that using iteration limit causes comparison to repeat some work, thus total execution time will increase. + * + * @param maxIter + */ + public void setMaxIter(long maxIter) { + this.maxIter = maxIter; + } + + public boolean isMapLiterals() { + return mapLiterals; + } + + public void setMapLiterals(boolean mapLiterals) { + this.mapLiterals = mapLiterals; + } + + private void clear() { + changes1.clear(); + changes1Set.clear(); + changes2.clear(); + changes2Set.clear(); + comparableResources.clear(); + comparableStatements.clear(); + modifications.clear(); + modificationsSet.clear(); + processedResources.clear(); + } + + public void dispose() { + changes1 = null; + changes1Set = null; + changes2 = null; + changes2Set = null; + comparableResources = null; + comparableStatements = null; + comparator = null; + modifications = null; + modificationsSet = null; + processedResources = null; + nonMatchedLeft = null; + nonMatchedRight = null; + nonTested = null; + nonTraversed = null; + ss1 = null; + ss2 = null; + strong = null; + tested = null; + traversed = null; + } + public void test(ReadGraph g) throws DatabaseException { + test(g,null); + } + + public void test(ReadGraph g, IProgressMonitor monitor) throws DatabaseException { this.g = g; this.b = Layer0.getInstance(g); comparator.setComparator(this); + comparator.initialize(g, r1, r2); + + if (monitor == null) + monitor = new NullProgressMonitor(); Stack objectsLeft = new Stack(); Stack objectsRight = new Stack(); @@ -185,45 +269,66 @@ public class GraphComparator { Set unreliableLeft = new HashSet(); Set unreliableRight = new HashSet(); + boolean changed = false; while (true) { - if (objectsLeft.isEmpty()) + if (objectsLeft.isEmpty() && !changed) break; - + if (monitor.isCanceled()) { + clear(); + return; + } + monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight)); + changed = false; // process compares objects that are identified and searches for more resources to process. - process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified statements subject and object have been identified - processUnreliable(unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified resources have path of length one to identified resource - processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); - if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { - // comparison is ending, but we have still unprocessed unidentified resources left. - // These cases have longer path than one to identified objects. - processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); - } + changed = compareIter(g, objectsLeft, objectsRight, unreliableLeft, unreliableRight); + monitor.worked(1); } for (Statement s : unreliableLeft) { - if (!comparableStatements.containsLeft(s)) + if (!comparableStatements.containsLeft(s)) { + if (DEBUG) System.out.println("Unreliable Object deletion " + printStatement(g,s)); addDeletion(s); + } } for (Statement s : unreliableRight) { - if (!comparableStatements.containsRight(s)) + if (!comparableStatements.containsRight(s)) { + if (DEBUG) System.out.println("Unreliable Object addition " + printStatement(g,s)); addAddition(s); + } } - - + monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight) + " done."); + //printStats(); } public void test(Session session) throws DatabaseException { - test(session, r1, r2); + test(session, r1, r2, null); + } + + public void test(Session session, IProgressMonitor monitor) throws DatabaseException { + test(session, r1, r2, monitor); } public void test(Session session, Resource r1, Resource r2) throws DatabaseException { + test(session, r1, r2, null); + } + + public void test(Session session, Resource r1, Resource r2, IProgressMonitor monitor) throws DatabaseException { comparator.setComparator(this); - addComparable(r1, r2, false); + if (monitor == null) + monitor = new NullProgressMonitor(); + + session.syncRequest(new ReadRequest() { + + @Override + public void run(ReadGraph graph) throws DatabaseException { + comparator.initialize(graph, r1, r2); + } + }); + + addComparable(r1, r2); final Stack objectsLeft = new Stack(); final Stack objectsRight = new Stack(); @@ -233,29 +338,26 @@ public class GraphComparator { final Set unreliableLeft = new HashSet(); final Set unreliableRight = new HashSet(); + boolean changed = false; while (true) { - if (objectsLeft.isEmpty()) + if (objectsLeft.isEmpty() && !changed) break; - session.syncRequest(new ReadRequest() { + if (monitor.isCanceled()) { + clear(); + return; + } + monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight)); + changed = session.syncRequest(new Read() { @Override - public void run(ReadGraph graph) throws DatabaseException { + public Boolean perform(ReadGraph graph) throws DatabaseException { + //System.out.println("Iter " + monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight)); g = graph; b = Layer0.getInstance(graph); - // process compares objects that are identified and searches for more resources to process. - process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified statements subject and object have been identified - processUnreliable(unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified resources have path of length one to identified resource - processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); - if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { - // comparison is ending, but we have still unprocessed unidentified resources left. - // These cases have longer path than one to identified objects. - processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); - } + return compareIter(graph, objectsLeft, objectsRight, unreliableLeft, unreliableRight); } }); - + monitor.worked(1); } @@ -267,21 +369,58 @@ public class GraphComparator { if (!comparableStatements.containsRight(s)) addAddition(s); } + unreliableLeft.clear(); + unreliableRight.clear(); - + monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight) + " done."); + //printStats(); } - private void process(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { + private boolean compareIter(ReadGraph graph, Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { + // process compares objects that are identified and searches for more resources to process. + iter = 0; + boolean c = process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); + if (objectsLeft.isEmpty()) { + // process unreliable handles cases where unidentified statements subject and object have been identified + c |= processUnreliable(unreliableLeft, unreliableRight); + // process unreliable handles cases where unidentified resources have path of length one to identified resource + if (!c) { + c |= processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + if (!c && objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { + c |= processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + } + if (!c && objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { + // comparison is ending, but we have still unprocessed unidentified resources left. + // These cases have longer path than one to identified objects. + c |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); + } + if (!c && objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { + // comparison is ending, but we have still unprocessed unidentified resources left. + // These cases have longer path than one to identified objects. + c |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); + } + } + } + return c; + + } + + private String monitorTaskName(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) { + int cr = comparableResources.size(); + int ch = Math.max(changes1.size(), changes2.size()); + return "Graph compare " + (cr + ch) + " / " + (cr+ch+(Math.max(objectsLeft.size(), objectsRight.size())+Math.max(unreliableLeft.size(), unreliableRight.size()))); + } + + private boolean process(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { List ss1 = new ArrayList(); List ss2 = new ArrayList(); - - while (!objectsLeft.isEmpty()) { + boolean didSomething = false; + while (!objectsLeft.isEmpty()&& (maxIter < 0 || iter < maxIter)) { Resource r1 = objectsLeft.pop(); Resource r2 = objectsRight.pop(); if (r1.equals(r2)) continue; - if (processedResources.contains(r1)) continue; processedResources.add(r1); @@ -290,8 +429,8 @@ public class GraphComparator { if((comparableResources.containsLeft(r1)||comparableResources.containsRight(r2)) && !comparableResources.contains(r1, r2)) { throw new DatabaseException("Comparator error: Trying to map " + r1 + " to " + r2 + " while mappings " + r1 + " to " + comparableResources.getRight(r1) + " and " + comparableResources.getLeft(r2) + " to " + r2 + " exist."); } - addComparable(r1, r2, false); - + addComparable(r1, r2); + didSomething = true; //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); compareProps(r1, r2); @@ -304,7 +443,8 @@ public class GraphComparator { ss2 = filterTraversed(ss2); ss1 = filterNonTested(ss1); ss2 = filterNonTested(ss2); - + ss1 = filter(Collections.singletonList(b.HasProperty), ss1); + ss2 = filter(Collections.singletonList(b.HasProperty), ss2); compareStatements(ss1, ss2, null, null,null,null); ss1.clear(); @@ -323,15 +463,17 @@ public class GraphComparator { ss2.clear(); } + iter++; } + return didSomething; } - private void processUnreliable(Set unreliableLeft, Set unreliableRight) throws DatabaseException { + private boolean processUnreliable(Set unreliableLeft, Set unreliableRight) throws DatabaseException { MapList subjectLeft = new MapList(); MapList subjectRight = new MapList(); MapList objectLeft = new MapList(); MapList objectRight = new MapList(); - + boolean didSomething = false; for (Statement s : unreliableLeft) { subjectLeft.add(s.getSubject(),s); objectLeft.add(s.getObject(),s); @@ -342,16 +484,18 @@ public class GraphComparator { } for (Resource left : subjectLeft.getKeys()) { - if (!comparableResources.containsLeft(left)) - continue; + if (maxIter > 0 && iter > maxIter) + break; Resource right = comparableResources.getRight(left); + if (right == null) + continue; for (Statement leftS : subjectLeft.getValues(left)) { Resource leftO = leftS.getObject(); - if (!comparableResources.containsLeft(leftO)) - continue; if (!unreliableLeft.contains(leftS)) continue; Resource rightO = comparableResources.getRight(leftO); + if (rightO == null) + continue; for (Statement rightS : subjectRight.getValues(right)) { if (!rightS.getObject().equals(rightO)) continue; @@ -361,19 +505,22 @@ public class GraphComparator { comparableResources.contains(leftS.getPredicate(), rightS.getPredicate())) { unreliableLeft.remove(leftS); unreliableRight.remove(rightS); - addComparable(leftS, rightS, false); + addComparable(leftS, rightS); + didSomething = true; + iter++; } } } } + return didSomething; } - private void processUnreliable(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { + private boolean processUnreliable(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { MapList subjectLeft = new MapList(); MapList subjectRight = new MapList(); MapList objectLeft = new MapList(); MapList objectRight = new MapList(); - + boolean didSomething = false; for (Statement s : unreliableLeft) { subjectLeft.add(s.getSubject(),s); objectLeft.add(s.getObject(),s); @@ -382,8 +529,9 @@ public class GraphComparator { subjectRight.add(s.getSubject(),s); objectRight.add(s.getObject(),s); } - for (Resource ol : objectLeft.getKeys()) { + if (maxIter > 0 && iter > maxIter) + break; // all statements to the left side object List left = objectLeft.getValues(ol); // all subjects that have statements to the left side object (ol) @@ -407,6 +555,8 @@ public class GraphComparator { } } + compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); + for (Resource similarOl : comparableOLeft.getKeys()) { List similarLeft = comparableOLeft.getValues(similarOl); if (similarLeft.size() == left.size()) { @@ -420,12 +570,18 @@ public class GraphComparator { for (int j = 0; j < left.size(); j++) { if (useSL[j]) continue; + // compare predicates Resource pl = left.get(i).getPredicate(); Resource psl = similarLeft.get(j).getPredicate(); if (pl.equals(psl)) { - useL[i] = true; - useSL[j] = true; - break; + // compare objects (unreliable result is interpreted as positive match) + + int comp = comparator.compare(g, left.get(i).getObject(), similarLeft.get(j).getObject(), true); + if (comp >= 0 && comp < ResourceComparator.NO_MATCH) { + useL[i] = true; + useSL[j] = true; + break; + } } } } @@ -482,9 +638,16 @@ public class GraphComparator { Statement rs = right.get(r); if (!comparableResources.contains(ls.getSubject(), rs.getSubject())) continue; + if ((comparableResources.containsLeft(ls.getObject()) || comparableResources.containsRight(rs.getObject())) && !comparableResources.contains(ls.getObject(), rs.getObject())) + continue; if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) { - iLeft[l] = r; - iRight[r] = l; + // compare objects (unreliable result is not accepted) + int comp = comparator.compare(g, ls.getObject(), rs.getObject()); + if (comp > 0 && comp < Integer.MAX_VALUE) { + iLeft[l] = r; + iRight[r] = l; + break; + } break; } } @@ -516,29 +679,34 @@ public class GraphComparator { objectsLeft.add(ol); objectsRight.add(or); - addComparable(ol, or, false); + addComparable(ol, or); + didSomething = true; for (int l = 0; l < left.size(); l++) { int r = indices.first[l]; Statement sl = left.get(l); Statement sr = right.get(r); - addComparable(sl, sr, true); + addComparable(sl, sr); unreliableLeft.remove(sl); unreliableRight.remove(sr); } + iter++; + + } else { } } + return didSomething; } - private void processUnreliableDeep(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { + private boolean processUnreliable2(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { MapList subjectLeft = new MapList(); MapList subjectRight = new MapList(); MapList objectLeft = new MapList(); MapList objectRight = new MapList(); - + boolean didSomething = false; for (Statement s : unreliableLeft) { subjectLeft.add(s.getSubject(),s); objectLeft.add(s.getObject(),s); @@ -547,7 +715,88 @@ public class GraphComparator { subjectRight.add(s.getSubject(),s); objectRight.add(s.getObject(),s); } + Set> processed = new HashSet>(); for (Resource ol : objectLeft.getKeys()) { + if (maxIter > 0 && iter > maxIter) + break; + // all statements to the left side object + List left = objectLeft.getValues(ol); + // all subjects that have statements to the left side object (ol) + Set sLeft = new HashSet(); + // all matching subjects on the right side + Set sRight = new HashSet(); + for (Statement s : left) { + sLeft.add(s.getSubject()); + sRight.add(comparableResources.getRight(s.getSubject())); + } + + if (sLeft.size() == 1 && sRight.size() == 1) { + Resource sl = sLeft.iterator().next(); + Resource sr = sRight.iterator().next(); + Pair p = new Pair(sl, sr); + if (processed.contains(p)) + continue; + processed.add(p); + List ss1 = new ArrayList(subjectLeft.getValuesSnapshot(sl)); + List ss2 = new ArrayList(subjectRight.getValuesSnapshot(sr)); + for (int i = ss1.size() -1; i >= 0; i--) { + if (!unreliableLeft.contains(ss1.get(i))) + ss1.remove(i); + } + for (int i = ss2.size() -1; i >= 0; i--) { + if (!unreliableRight.contains(ss2.get(i))) + ss2.remove(i); + } + + int ccount = comparableStatements.size(); + int lcount = changes1.size(); + int rcount = changes2.size(); + + compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); + if (comparableStatements.size() > ccount) { + didSomething = true; + for (Entry entry : comparableStatements.getEntries()) { + unreliableLeft.remove(entry.getKey()); + unreliableRight.remove(entry.getValue()); + iter++; + } + } + if (changes1.size() > lcount) { + didSomething = true; + for (Statement stm : changes1) { + unreliableLeft.remove(stm); + iter++; + } + } + if (changes2.size() > rcount) { + didSomething = true; + for (Statement stm : changes2) { + unreliableRight.remove(stm); + iter++; + } + } + } + } + return didSomething; + } + + private boolean processUnreliableDeep(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { + MapList subjectLeft = new MapList(); + MapList subjectRight = new MapList(); + MapList objectLeft = new MapList(); + MapList objectRight = new MapList(); + boolean didSomething = false; + for (Statement s : unreliableLeft) { + subjectLeft.add(s.getSubject(),s); + objectLeft.add(s.getObject(),s); + } + for (Statement s : unreliableRight) { + subjectRight.add(s.getSubject(),s); + objectRight.add(s.getObject(),s); + } + for (Resource ol : objectLeft.getKeys()) { + if (maxIter > 0 && iter > maxIter) + break; Set pathsLeft = new HashSet(); for (Resource rel : traversed) { pathsLeft.addAll(Path.create(g.getStatements(ol, rel))); @@ -587,11 +836,12 @@ public class GraphComparator { } if (matchingPaths.size() > 0) { if (matchingPaths.size() == 1) { + didSomething = true; Resource or = matchingPaths.keySet().iterator().next(); objectsLeft.add(ol); objectsRight.add(or); - addComparable(ol, or, false); + addComparable(ol, or); Collection statementsLeft = objectLeft.getValues(ol); Collection statementsRight = objectRight.getValues(or); unreliableLeft.removeAll(statementsLeft); @@ -600,25 +850,28 @@ public class GraphComparator { for (Path left : map.getLeftSet()) { Path right = map.getRight(left); for (int i = 0; i < left.getLength(); i++) { - addComparable(left.getStatements().get(i),right.getStatements().get(i),false); + addComparable(left.getStatements().get(i),right.getStatements().get(i)); + iter++; } } + iter++; } } } } + return didSomething; } - private boolean hasMatchingPaths(Set leftPaths, Set rightPaths) { + private boolean hasMatchingPaths(Set leftPaths, Set rightPaths) throws DatabaseException { if (leftPaths.size() != rightPaths.size()) return false; BijectionMap map = getMatchingPaths(leftPaths, rightPaths); return map.size() == leftPaths.size(); } - private BijectionMap getMatchingPaths(Set leftPaths, Set rightPaths) { + private BijectionMap getMatchingPaths(Set leftPaths, Set rightPaths) throws DatabaseException { BijectionMap map = new BijectionMap(); for (Path leftPath : leftPaths) { for (Path rightPath : rightPaths) { @@ -627,8 +880,27 @@ public class GraphComparator { if (leftPath.getLength() != rightPath.getLength()) continue; if (comparableResources.contains(leftPath.getEnd(), rightPath.getEnd())) { - map.map(leftPath, rightPath); - break; + boolean match = true; + for (int i = 0; i < leftPath.getLength(); i++) { + Statement sl = leftPath.getStatements().get(i); + Statement sr = rightPath.getStatements().get(i); + if (!sl.getPredicate().equals(sr.getPredicate()) && !comparableResources.contains(sl.getPredicate(), sr.getPredicate())) { + match = false; + break; + } + if ((getComparableResources().containsLeft(sl.getObject()) || getComparableResources().containsRight(sr.getObject())) && !getComparableResources().contains(sl.getObject(), sr.getObject())) { + match = false; + break; + } + if (comparator.compare(g, sl.getObject(), sr.getObject()) == ResourceComparator.NO_MATCH) { + match = false; + break; + } + } + if (match) { + map.map(leftPath, rightPath); + break; + } } } } @@ -691,24 +963,38 @@ public class GraphComparator { return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources); } - private void addComparable(Statement left, Statement right, boolean process) throws DatabaseException { - addComparable(left.getObject(), right.getObject(), process); + public List getChanges1() { + return changes1; + } + + public List getChanges2() { + return changes2; + } + + private void addComparable(Statement left, Statement right) throws DatabaseException { + addComparable(left.getObject(), right.getObject()); comparableStatements.map(left, right); - //comparableResources.map(left.getObject(), right.getObject()); } - private void addComparable(Resource left, Resource right, boolean process) throws DatabaseException { + private void addComparable(Resource left, Resource right) throws DatabaseException { if(!comparableResources.contains(left, right)) { if (comparableResources.containsLeft(left)||comparableResources.containsRight(right)) { throw new DatabaseException("Comparator error: Trying to map " + left + " to " + right + " while mappings " + left + " to " + comparableResources.getRight(left) + " and " + comparableResources.getLeft(right) + " to " + right + " exist."); } else { if (DEBUG) System.out.println(left + " = " + right); - comparableResources.map(left, right); + comparableResources.map(left, right); + +// if (comparableResources.size() % 1000 == 0) +// printStats(); } } } + public void printStats() { + System.out.println("Comp " + comparableResources.size() + " L " + changes1.size() + " R " + changes2.size() + " M " + modifications.size() + " P " + processedResources.size()); + } + public List filterAsserted(Resource r, Collection in) throws DatabaseException { List out = new ArrayList(); for (Statement s : in) { @@ -719,6 +1005,26 @@ public class GraphComparator { return out; } + public List filterAssertedDuplicates(Resource r, List in) throws DatabaseException { + List out = new ArrayList(); + for (int i = 0; i < in.size(); i++) { + Statement s = in.get(i); + if (!s.isAsserted(r)) + out.add(s); + else { + boolean has = false; + if (i > 0 && in.get(i-1).getPredicate().equals(s.getPredicate())) + has = true; + else if (i < in.size()-1 && in.get(i+1).getPredicate().equals(s.getPredicate())) + has = true; + if (!has) + out.add(s); + } + + } + return out; + } + private String printStatement(ReadGraph graph, Statement s) throws DatabaseException { @@ -760,6 +1066,7 @@ public class GraphComparator { private void addDeletion(Statement s) { if (!changes1Set.contains(s)) { + if (DEBUG) System.out.println("- " +s.getSubject() + " " + s.getPredicate() + " " + s.getObject()) ; changes1Set.add(s); changes1.add(s); } @@ -768,12 +1075,13 @@ public class GraphComparator { private void addAddition(Statement s) { if (!changes2Set.contains(s)) { changes2Set.add(s); + if (DEBUG) System.out.println("+ " +s.getSubject() + " " + s.getPredicate() + " " + s.getObject()) ; changes2.add(s); } } - private void addModification(Statement s1, Statement s2) { - Pair mod = new Pair(s1,s2); + private void addModification(Resource left, Statement leftstm, Resource right, Statement rightstm) { + Modification mod = new Modification(left, right, leftstm, rightstm); if (!modificationsSet.contains(mod)) { modificationsSet.add(mod); modifications.add(mod); @@ -952,7 +1260,7 @@ public class GraphComparator { for (int i = 0; i < used2.length; i++) { used2[i] = false; } - + // left, right, difference List> differences = new ArrayList>(); for (int i1 = off1; i1 < off1 + len1; i1++) { @@ -984,7 +1292,118 @@ public class GraphComparator { Integer[] pris = priorities.getKeys(new Integer[]{}); Arrays.sort(pris); - + boolean matchFail = priorityMatching(ss1, off1, len1, ss2, off2, len2, pris, differences, priorities, used1, used2, objectsLeft, objectsRight, false); + if (matchFail) + matchFail = priorityMatching(ss1, off1, len1, ss2, off2, len2, pris, differences, priorities, used1, used2, objectsLeft, objectsRight, objectsLeft == null); + if (unreliableLeft != null) { + if (matchFail) { + // With match failure, statement matching was aborted. We must move all unmatched statements to unreliable. + for (Integer pri : pris) { + if (pri == 0 || pri == Integer.MAX_VALUE) + continue; + priorityProcessUnmatched(ss1, off1, len1, ss2, off2, len2, differences, priorities, used1, used2, unreliableLeft, unreliableRight, pri); + } + } + // Zero means unreliable comparison result, move all unmatched to unreliable. + if (org.simantics.utils.datastructures.Arrays.contains(pris, 0)) { + priorityProcessUnmatched(ss1, off1, len1, ss2, off2, len2, differences, priorities, used1, used2, unreliableLeft, unreliableRight, 0); + } + } +// Previous version processed 0 priority statements, even when unreliableLeft collection was null. +// The problem was that property relations were not filtered in process() from "tested" statements. +// else { +// if (org.simantics.utils.datastructures.Arrays.contains(pris, 0)) { +// priorityProcessUnmatched(ss1, off1, len1, ss2, off2, len2, differences, priorities, used1, used2, unreliableLeft, unreliableRight, 0); +// } +// } + // Report unmatched statements as changes. + for (int i1 = off1; i1 < off1 + len1; i1++) { + if (!used1[i1-off1]) { + if (DEBUG) System.out.println("Compare Object deletion " + printStatement(g,ss1.get(i1))); + addDeletion(ss1.get(i1)); + } + } + for (int i2 = off2; i2 < off2 + len2; i2++) { + if (!used2[i2-off2]) { + if (DEBUG) System.out.println("Compare Object addition " + printStatement(g,ss2.get(i2))); + addAddition(ss2.get(i2)); + } + } + } + + /** + * Moves unmatched statements to unreliable collections. + * @param ss1 + * @param off1 + * @param len1 + * @param ss2 + * @param off2 + * @param len2 + * @param differences + * @param priorities + * @param used1 + * @param used2 + * @param unreliableLeft + * @param unreliableRight + * @param pri + */ + private void priorityProcessUnmatched(List ss1, int off1, int len1, List ss2, int off2, int len2,List> differences,MapList priorities,boolean used1[],boolean used2[], Collection unreliableLeft, Collection unreliableRight, int pri) { + Set s1s = new HashSet(); + Set s2s = new HashSet(); + Set s1i = new HashSet(); + Set s2i = new HashSet(); + List i1s = priorities.getValues(pri); + for (Integer i1 : i1s) { + if (used1[i1]) + continue; + List i2diff = differences.get(i1); + for (int i2 = 0; i2 < i2diff.size(); i2++) { + if (i2diff.get(i2) == pri) { + if (used2[i2]) + continue; + Statement s1 = ss1.get(i1+off1); + Statement s2 = ss2.get(i2+off2); + s1s.add(s1); + s2s.add(s2); + s1i.add(i1); + s2i.add(i2); + } + } + } + if (unreliableLeft != null) { + unreliableLeft.addAll(s1s); + unreliableRight.addAll(s2s); + } + for (Integer i : s1i) + used1[i] = true; + for (Integer i : s2i) + used2[i] = true; + } + /** + * Matches left and right side statements. + * + * When there are two or more equally good matching objects, the behaviour depends on force flag. + * False: Matching is aborted and matchFail is returned (method return true). + * True: equally good matches will be paired randomly. Method always returns false. + * @param ss1 + * @param off1 + * @param len1 + * @param ss2 + * @param off2 + * @param len2 + * @param pris + * @param differences + * @param priorities + * @param used1 + * @param used2 + * @param objectsLeft + * @param objectsRight + * @param force + * @return + * @throws DatabaseException + */ + private boolean priorityMatching(List ss1, int off1, int len1, List ss2, int off2, int len2, Integer[] pris, List> differences, MapList priorities, boolean used1[],boolean used2[], Collection objectsLeft, Collection objectsRight, boolean force) throws DatabaseException { + boolean matchFail = false; for (Integer pri : pris) { if (pri == Integer.MAX_VALUE) { @@ -992,89 +1411,48 @@ public class GraphComparator { } else { List i1s = priorities.getValues(pri); + for (Integer i1 : i1s) { if (used1[i1]) continue; List i2diff = differences.get(i1); + List matches = new ArrayList(); for (int i2 = 0; i2 < i2diff.size(); i2++) { - if (i2diff.get(i2) == pri) { + if (i2diff.get(i2) == pri) { if (used2[i2]) continue; - used1[i1] = true; - used2[i2] = true; - Statement s1 = ss1.get(i1+off1); - Statement s2 = ss2.get(i2+off2); - - if (objectsLeft != null) { - objectsLeft.add(s1.getObject()); - objectsRight.add(s2.getObject()); - } - addComparable(s1, s2, true); - break; + matches.add(i2); } } - } - } - } - - for (Integer pri : pris) { - if (pri != 0) - continue; - Set s1s = new HashSet(); - Set s2s = new HashSet(); - Set s1i = new HashSet(); - Set s2i = new HashSet(); - List i1s = priorities.getValues(pri); - for (Integer i1 : i1s) { - if (used1[i1]) - continue; - List i2diff = differences.get(i1); - for (int i2 = 0; i2 < i2diff.size(); i2++) { - if (i2diff.get(i2) == pri) { - if (used2[i2]) - continue; + if (matches.size() == 1 || (force && matches.size() > 1)) { + int i2 = matches.get(0); + used1[i1] = true; + used2[i2] = true; Statement s1 = ss1.get(i1+off1); Statement s2 = ss2.get(i2+off2); - s1s.add(s1); - s2s.add(s2); - s1i.add(i1); - s2i.add(i2); + + if (objectsLeft != null) { + objectsLeft.add(s1.getObject()); + objectsRight.add(s2.getObject()); + } + addComparable(s1, s2); + } else if (matches.size() > 1) { + matchFail = true; } } - } - if (unreliableLeft != null) { - unreliableLeft.addAll(s1s); - unreliableRight.addAll(s2s); - } - for (Integer i : s1i) - used1[i] = true; - for (Integer i : s2i) - used2[i] = true; - - } - for (int i1 = off1; i1 < off1 + len1; i1++) { - if (!used1[i1-off1]) { - if (DEBUG) System.out.println("Compare Object deletion " + printStatement(g,ss1.get(i1))); - addDeletion(ss1.get(i1)); - } - } - for (int i2 = off2; i2 < off2 + len2; i2++) { - if (!used2[i2-off2]) { - if (DEBUG) System.out.println("Compare Object addition " + printStatement(g,ss2.get(i2))); - addAddition(ss2.get(i2)); + if (matchFail) + break; } } + return matchFail; } - - + /** * compares properties, assumes functional relations * @param r1 * @param r2 - * @throws ServiceException - * @throws DoesNotContainValueException - * @throws ValidationException + * @throws DatabaseException */ private void compareProps(Resource r1, Resource r2) throws DatabaseException { if (DEBUG) System.out.println("compareProps " + r1 + " " + NameUtils.getSafeName(g, r1) + " " + r2 + " " + NameUtils.getSafeName(g, r2)); @@ -1085,6 +1463,9 @@ public class GraphComparator { ss1 = filterNonTested(ss1); ss2 = filterNonTested(ss2); sortStatement(ss1, ss2); + // getStatements(r1, b.HasProperty) returns both instance and asserted statements for the same property relation. + ss1 = filterAssertedDuplicates(r1, ss1); + ss2 = filterAssertedDuplicates(r2, ss2); int i1 = 0; int i2 = 0; @@ -1095,16 +1476,20 @@ public class GraphComparator { break; else { while (i2 < ss2.size()) { - if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,ss2.get(i2))); - addAddition(ss2.get(i2)); + Statement s = ss2.get(i2); + if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,s)); + if (!s.isAsserted(r2)) + addAddition(s); i2++; } break; } } else if (i2 >= ss2.size()) { while (i1 < ss1.size()) { - if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,ss1.get(i1))); - addDeletion(ss1.get(i1)); + Statement s = ss1.get(i1); + if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,s)); + if (!s.isAsserted(r1)) + addDeletion(s); i1++; } break; @@ -1121,22 +1506,43 @@ public class GraphComparator { case 0:{ boolean b1 = g.hasValue(s1.getObject()); boolean b2 = g.hasValue(s2.getObject()); + boolean a1 = s1.isAsserted(r1); + boolean a2 = s2.isAsserted(r2); if (b1 == b2) { if (b1) { - Object v1 = g.getValue(s1.getObject()); - Object v2 = g.getValue(s2.getObject()); - boolean eq = compareValue(v1, v2); + // Literals + boolean eq = compareValue(g,b,s1.getObject(), s2.getObject()); if (!eq) { - addModification(s1, s2); - addComparable(s1, s2, false); + addModification(r1,s1,r2,s2); } + if (mapLiterals && !a1 && !a2) + addComparable(s1, s2); } else { - if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject())) - compareProps(s1.getObject(), s2.getObject()); + // Non literal properties. + int comp = comparator.compare(g, s1.getObject(), s2.getObject()); + if (comp == ResourceComparator.NO_MATCH) { + addModification(r1,s1,r2,s2); + } else if (comp != ResourceComparator.EXACT_MATCH) { + if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject())) { + if (!a1 && !a2) { + // compare props matches objects, so we can call that only for non asserted statements + compareProps(s1.getObject(), s2.getObject()); + } else if (a1 && a2) { + // TODO : compare asserted statements? + } else { + addModification(r1,s1,r2,s2); + } + } else { + addModification(r1,s1,r2,s2); + } + } else { + // Exact match, nothing to do. + if (!a1 && !a2) + addComparable(s1, s2); + } } } else { - addModification(s1, s2); - addComparable(s1, s2, false); + addModification(r1,s1,r2,s2); } i1++; i2++; @@ -1144,14 +1550,18 @@ public class GraphComparator { } case -1:{ if (DEBUG) System.out.println("Compare Prop diff1s " + printStatement(g,s1)); - addDeletion(s1); + // Use modification, since deletions do not support asserted statements + addModification(r1,s1,r2,null); + //addDeletion(s1); i1++; break; } case 1:{ if (DEBUG) System.out.println("Compare Prop diff2s " + printStatement(g,s2)); - addAddition(s2); + // Use modification, since additions do not support asserted statements + addModification(r1,null,r2,s2); + //addAddition(s2); i2++; break; } @@ -1164,6 +1574,75 @@ public class GraphComparator { } + public static boolean compareValue(ReadGraph g, Layer0 b, Resource r1, Resource r2) throws DatabaseException { + Resource t1 = g.getSingleType(r1); + Resource t2 = g.getSingleType(r2); + if (!t1.equals(t2)) + return false; + if (t1.equals(b.Integer)) { + int v1 = g.getValue(r1, Bindings.INTEGER); + int v2 = g.getValue(r2, Bindings.INTEGER); + return v1 == v2; + } else if (t1.equals(b.Float)) { + float v1 = g.getValue(r1, Bindings.FLOAT); + float v2 = g.getValue(r2, Bindings.FLOAT); + return v1 == v2; + } else if (t1.equals(b.Double)) { + double v1 = g.getValue(r1, Bindings.DOUBLE); + double v2 = g.getValue(r2, Bindings.DOUBLE); + return v1 == v2; + } else if (t1.equals(b.String)) { + String v1 = g.getValue(r1, Bindings.STRING); + String v2 = g.getValue(r2, Bindings.STRING); + return v1.equals(v2); + } else if (t1.equals(b.Boolean)) { + boolean v1 = g.getValue(r1, Bindings.BOOLEAN); + boolean v2 = g.getValue(r2, Bindings.BOOLEAN); + return v1 == v2; + } else if (t1.equals(b.Byte)) { + byte v1 = g.getValue(r1, Bindings.BYTE); + byte v2 = g.getValue(r2, Bindings.BYTE); + return v1 == v2; + } else if (t1.equals(b.Long)) { + long v1 = g.getValue(r1, Bindings.LONG); + long v2 = g.getValue(r2, Bindings.LONG); + return v1 == v2; + } else if (t1.equals(b.IntegerArray)) { + int[] v1 = g.getValue(r1, Bindings.INT_ARRAY); + int[] v2 = g.getValue(r2, Bindings.INT_ARRAY); + return Arrays.equals(v1,v2); + } else if (t1.equals(b.FloatArray)) { + float[] v1 = g.getValue(r1, Bindings.FLOAT_ARRAY); + float[] v2 = g.getValue(r2, Bindings.FLOAT_ARRAY); + return Arrays.equals(v1,v2); + } else if (t1.equals(b.DoubleArray)) { + double[] v1 = g.getValue(r1, Bindings.DOUBLE_ARRAY); + double[] v2 = g.getValue(r2, Bindings.DOUBLE_ARRAY); + return Arrays.equals(v1,v2); + } else if (t1.equals(b.StringArray)) { + String[] v1 = g.getValue(r1, Bindings.STRING_ARRAY); + String[] v2 = g.getValue(r2, Bindings.STRING_ARRAY); + return Arrays.equals(v1,v2); + } else if (t1.equals(b.BooleanArray)) { + boolean[] v1 = g.getValue(r1, Bindings.BOOLEAN_ARRAY); + boolean[] v2 = g.getValue(r2, Bindings.BOOLEAN_ARRAY); + return Arrays.equals(v1,v2); + } else if (t1.equals(b.ByteArray)) { + byte[] v1 = g.getValue(r1, Bindings.BYTE_ARRAY); + byte[] v2 = g.getValue(r2, Bindings.BYTE_ARRAY); + return Arrays.equals(v1,v2); + } else if (t1.equals(b.LongArray)) { + long[] v1 = g.getValue(r1, Bindings.LONG_ARRAY); + long[] v2 = g.getValue(r2, Bindings.LONG_ARRAY); + return Arrays.equals(v1,v2); + } else { + Object v1 = g.getValue(r1); + Object v2 = g.getValue(r2); + return compareValue(v1, v2); + } + + } + public static boolean compareValue(Object v1, Object v2) { if (v1 instanceof Object[] && v2 instanceof Object[]) return Arrays.deepEquals((Object[])v1, (Object[])v2);