From 212801c71a012172929a33ffd9643e107eec4950 Mon Sep 17 00:00:00 2001 From: Marko Luukkainen Date: Wed, 10 Feb 2021 18:11:50 +0200 Subject: [PATCH] Preventing random matches did not work. In some cases objects were matched correctly, but also reported as added/removed at the same time. gitlab #30 Change-Id: I0cc6bf542a3555f57c1aa505d9fba8e01d3401c9 --- .../interop/test/GraphComparator.java | 212 ++++++++++++------ 1 file changed, 145 insertions(+), 67 deletions(-) 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 c59cbfc..52a8bab 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; @@ -32,6 +34,7 @@ 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; @@ -195,34 +198,39 @@ public class GraphComparator { Set unreliableLeft = new HashSet(); Set unreliableRight = new HashSet(); + boolean changed = false; while (true) { - if (objectsLeft.isEmpty()) + if (objectsLeft.isEmpty() && !changed) break; - + changed = false; // process compares objects that are identified and searches for more resources to process. - process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); + changed |= process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); // process unreliable handles cases where unidentified statements subject and object have been identified - processUnreliable(unreliableLeft, unreliableRight); + changed |= processUnreliable(unreliableLeft, unreliableRight); // process unreliable handles cases where unidentified resources have path of length one to identified resource - processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + changed |= processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { - processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + changed |= processUnreliable2(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 |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); } } 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); + } } } @@ -252,34 +260,36 @@ 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() { + changed = session.syncRequest(new Read() { @Override - public void run(ReadGraph graph) throws DatabaseException { + public Boolean perform(ReadGraph graph) throws DatabaseException { g = graph; b = Layer0.getInstance(graph); // process compares objects that are identified and searches for more resources to process. - process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); + boolean c = process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); // process unreliable handles cases where unidentified statements subject and object have been identified - processUnreliable(unreliableLeft, unreliableRight); + c |= processUnreliable(unreliableLeft, unreliableRight); // process unreliable handles cases where unidentified resources have path of length one to identified resource - processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + c |= processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { - processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + c |= processUnreliable2(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); + c |= processUnreliableDeep(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); + c |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); } + return c; } }); @@ -298,10 +308,10 @@ public class GraphComparator { } - private void process(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { + private boolean process(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { List ss1 = new ArrayList(); List ss2 = new ArrayList(); - + boolean didSomething = false; while (!objectsLeft.isEmpty()) { Resource r1 = objectsLeft.pop(); Resource r2 = objectsRight.pop(); @@ -317,7 +327,7 @@ public class GraphComparator { 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); - + didSomething = true; //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); compareProps(r1, r2); @@ -330,7 +340,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(); @@ -350,14 +361,15 @@ public class GraphComparator { } } + 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); @@ -388,18 +400,20 @@ public class GraphComparator { unreliableLeft.remove(leftS); unreliableRight.remove(rightS); addComparable(leftS, rightS); + didSomething = true; } } } } + 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); @@ -558,6 +572,7 @@ public class GraphComparator { objectsLeft.add(ol); objectsRight.add(or); addComparable(ol, or); + didSomething = true; for (int l = 0; l < left.size(); l++) { int r = indices.first[l]; Statement sl = left.get(l); @@ -572,16 +587,17 @@ public class GraphComparator { } } + return didSomething; } - private void processUnreliable2(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); @@ -610,6 +626,7 @@ public class GraphComparator { int count = comparableStatements.size(); compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); if (comparableStatements.size() > count) { + didSomething = true; for (Entry entry : comparableStatements.getEntries()) { unreliableLeft.remove(entry.getKey()); unreliableRight.remove(entry.getValue()); @@ -617,14 +634,15 @@ public class GraphComparator { } } } + return didSomething; } - private void processUnreliableDeep(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { + 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); @@ -673,6 +691,7 @@ public class GraphComparator { } if (matchingPaths.size() > 0) { if (matchingPaths.size() == 1) { + didSomething = true; Resource or = matchingPaths.keySet().iterator().next(); objectsLeft.add(ol); @@ -694,6 +713,7 @@ public class GraphComparator { } } + return didSomething; } @@ -807,7 +827,6 @@ public class GraphComparator { 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) throws DatabaseException { @@ -893,6 +912,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); } @@ -901,6 +921,7 @@ 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); } } @@ -1120,42 +1141,28 @@ public class GraphComparator { 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); - - for (Integer pri : pris) { - if (pri != 0 && !matchFail && unreliableLeft == null) - 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; - 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) { + 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); } } - if (unreliableLeft != null) { - unreliableLeft.addAll(s1s); - unreliableRight.addAll(s2s); + // 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); } - for (Integer i : s1i) - used1[i] = true; - for (Integer i : s2i) - used2[i] = true; - - } + } +// 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))); @@ -1170,6 +1177,77 @@ public class GraphComparator { } } + /** + * 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) { @@ -1220,9 +1298,7 @@ public class GraphComparator { * 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)); @@ -1307,6 +1383,8 @@ public class GraphComparator { } } else { // Exact match, nothing to do. + if (!a1 && !a2) + addComparable(s1, s2); } } } else { -- 2.47.1