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;
private Set<Resource> nonMatchedLeft = new HashSet<Resource>();
private Set<Resource> nonMatchedRight = new HashSet<Resource>();
+ 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;
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<Resource> objectsLeft = new Stack<Resource>();
Stack<Resource> objectsRight = new Stack<Resource>();
objectsLeft.push(r1);
while (true) {
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.
- changed |= process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
- // process unreliable handles cases where unidentified statements subject and object have been identified
- changed |= processUnreliable(unreliableLeft, unreliableRight);
- // process unreliable handles cases where unidentified resources have path of length one to identified resource
- changed |= processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
- if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
- 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.
- changed |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
- }
+ changed = compareIter(g, objectsLeft, objectsRight, unreliableLeft, unreliableRight);
+ monitor.worked(1);
}
for (Statement s : unreliableLeft) {
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);
+ if (monitor == null)
+ monitor = new NullProgressMonitor();
+
session.syncRequest(new ReadRequest() {
@Override
while (true) {
if (objectsLeft.isEmpty() && !changed)
break;
+ if (monitor.isCanceled()) {
+ clear();
+ return;
+ }
+ monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight));
changed = session.syncRequest(new Read<Boolean>() {
@Override
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.
- boolean c = process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
- // 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
- c |= processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
- if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
- 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.
- 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.
- c |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
- }
- return c;
+ return compareIter(graph, objectsLeft, objectsRight, unreliableLeft, unreliableRight);
}
});
-
+ monitor.worked(1);
}
if (!comparableStatements.containsRight(s))
addAddition(s);
}
+ unreliableLeft.clear();
+ unreliableRight.clear();
-
+ monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight) + " done.");
+ //printStats();
}
+ private boolean compareIter(ReadGraph graph, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> 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<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> 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<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
List<Statement> ss1 = new ArrayList<Statement>();
List<Statement> ss2 = new ArrayList<Statement>();
boolean didSomething = false;
- while (!objectsLeft.isEmpty()) {
+ while (!objectsLeft.isEmpty()&& (maxIter < 0 || iter < maxIter)) {
Resource r1 = objectsLeft.pop();
Resource r2 = objectsRight.pop();
ss2.clear();
}
+ iter++;
}
return didSomething;
}
}
for (Resource left : subjectLeft.getKeys()) {
+ if (maxIter > 0 && iter > maxIter)
+ break;
Resource right = comparableResources.getRight(left);
if (right == null)
continue;
unreliableRight.remove(rightS);
addComparable(leftS, rightS);
didSomething = true;
+ iter++;
}
}
}
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<Statement> left = objectLeft.getValues(ol);
// all subjects that have statements to the left side object (ol)
unreliableLeft.remove(sl);
unreliableRight.remove(sr);
}
+ iter++;
} else {
subjectRight.add(s.getSubject(),s);
objectRight.add(s.getObject(),s);
}
-
+ Set<Pair<Resource, Resource>> processed = new HashSet<Pair<Resource,Resource>>();
for (Resource ol : objectLeft.getKeys()) {
+ if (maxIter > 0 && iter > maxIter)
+ break;
// all statements to the left side object
List<Statement> left = objectLeft.getValues(ol);
// all subjects that have statements to the left side object (ol)
}
if (sLeft.size() == 1 && sRight.size() == 1) {
- List<Statement> ss1 = new ArrayList<Statement>(subjectLeft.getValues(sLeft.iterator().next()));
- List<Statement> ss2 = new ArrayList<Statement>(subjectRight.getValues(sRight.iterator().next()));
+ Resource sl = sLeft.iterator().next();
+ Resource sr = sRight.iterator().next();
+ Pair<Resource, Resource> p = new Pair<Resource, Resource>(sl, sr);
+ if (processed.contains(p))
+ continue;
+ processed.add(p);
+ List<Statement> ss1 = new ArrayList<Statement>(subjectLeft.getValuesSnapshot(sl));
+ List<Statement> ss2 = new ArrayList<Statement>(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();
- int count = comparableStatements.size();
compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
- if (comparableStatements.size() > count) {
+ if (comparableStatements.size() > ccount) {
didSomething = true;
for (Entry<Statement, Statement> 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++;
}
}
}
objectRight.add(s.getObject(),s);
}
for (Resource ol : objectLeft.getKeys()) {
+ if (maxIter > 0 && iter > maxIter)
+ break;
Set<Path> pathsLeft = new HashSet<Path>();
for (Resource rel : traversed) {
pathsLeft.addAll(Path.create(g.getStatements(ol, rel)));
Path right = map.getRight(left);
for (int i = 0; i < left.getLength(); i++) {
addComparable(left.getStatements().get(i),right.getStatements().get(i));
+ iter++;
}
}
+ iter++;
}
}
}
} else {
if (DEBUG) System.out.println(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<Statement> filterAsserted(Resource r, Collection<Statement> in) throws DatabaseException {
List<Statement> out = new ArrayList<Statement>();
for (Statement s : in) {
boolean eq = compareValue(g,b,s1.getObject(), s2.getObject());
if (!eq) {
addModification(r1,s1,r2,s2);
- if (!a1 && !a2)
- addComparable(s1, s2);
}
+ if (mapLiterals && !a1 && !a2)
+ addComparable(s1, s2);
} else {
// Non literal properties.
int comp = comparator.compare(g, s1.getObject(), s2.getObject());