--- /dev/null
+package org.simantics.graph.db;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.Collections;\r
+import java.util.List;\r
+import java.util.Map;\r
+\r
+import org.simantics.db.ReadGraph;\r
+import org.simantics.db.Resource;\r
+import org.simantics.db.common.uri.UnescapedChildMapOfResource;\r
+import org.simantics.db.exception.DatabaseException;\r
+import org.simantics.db.exception.RuntimeDatabaseException;\r
+import org.simantics.db.request.Read;\r
+import org.simantics.graph.representation.External;\r
+import org.simantics.graph.representation.Identity;\r
+import org.simantics.graph.representation.IdentityDefinition;\r
+import org.simantics.graph.representation.Internal;\r
+import org.simantics.graph.representation.Optional;\r
+import org.simantics.graph.representation.Root;\r
+import org.simantics.graph.representation.TransferableGraph1;\r
+import org.simantics.utils.datastructures.Pair;\r
+\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.map.hash.TIntIntHashMap;\r
+import gnu.trove.procedure.TObjectObjectProcedure;\r
+import gnu.trove.set.hash.THashSet;\r
+\r
+/**\r
+ * Analyses the dependencies between transferable graphs. Usage:\r
+ * <pre>\r
+GraphDependencyAnalyzer<TransferableGraph1> analyzer =\r
+ new GraphDependencyAnalyzer<TransferableGraph1>();\r
+for(TransferableGraph1 tg : tgs)\r
+ analyzer.addGraph(tg, tg);\r
+if(!analyzer.analyzeDependency()) {\r
+ <Report problems> analyzer.getConflicts()\r
+}\r
+else if(!analyzer.doesSatisfyExternalDependencies(graph)) {\r
+ <Report problems> analyzer.getUnsatisfiedDependencies()\r
+}\r
+else\r
+ for(TransferableGraph1 tg : analyzer.getSortedGraphs())\r
+ <Import> tg\r
+}\r
+ * </pre>\r
+ * @author Hannu Niemist�\r
+ */\r
+public class GraphDependencyAnalyzer<T extends Comparable<T>> {\r
+\r
+ private ArrayList<IU> graphs = new ArrayList<IU>();\r
+ private IdentityNode root = new IdentityNode(null, null);\r
+ \r
+ public static class IUList {\r
+ IU head;\r
+ IUList tail;\r
+ \r
+ public IUList(IU head, IUList tail) {\r
+ this.head = head;\r
+ this.tail = tail;\r
+ } \r
+ }\r
+ \r
+ public static Collection<IU> toCollection(IUList list) {\r
+ ArrayList<IU> result = new ArrayList<IU>();\r
+ while(list != null) {\r
+ result.add(list.head);\r
+ list = list.tail;\r
+ }\r
+ return result;\r
+ }\r
+ \r
+ public static class IdentityNode {\r
+ IdentityNode parent;\r
+ String name;\r
+ IUList provides = null;\r
+ IUList providesOptionally = null;\r
+ IUList requires = null;\r
+ THashMap<String, IdentityNode> children = null; \r
+\r
+ public IdentityNode(IdentityNode parent, String name) {\r
+ this.parent = parent;\r
+ this.name = name;\r
+ }\r
+\r
+ public IdentityNode get(String name) {\r
+ if(children == null) {\r
+ children = new THashMap<String, IdentityNode>(4);\r
+ IdentityNode node = new IdentityNode(this, name);\r
+ children.put(name, node);\r
+ return node;\r
+ }\r
+ else {\r
+ IdentityNode node = children.get(name);\r
+ if(node == null) {\r
+ node = new IdentityNode(this, name);\r
+ children.put(name, node); \r
+ }\r
+ return node;\r
+ }\r
+ }\r
+ \r
+ @Override\r
+ public String toString() {\r
+ if(parent == null || parent.parent == null) {\r
+ if(name.equals(""))\r
+ return "http:/";\r
+ else\r
+ return name;\r
+ }\r
+ return parent.toString() + "/" + name;\r
+ }\r
+ \r
+ public IUList getRequires() {\r
+ return requires;\r
+ }\r
+ }\r
+ \r
+ public static class IU implements Comparable<IU> {\r
+ final Comparable id;\r
+ final TransferableGraph1 tg;\r
+ IdentityNode[] identities;\r
+ THashMap<IUList, IUList> tgLists = new THashMap<IUList, IUList>();\r
+ THashSet<IU> dependencies = new THashSet<IU>();\r
+\r
+ public IU(Comparable id, TransferableGraph1 tg) {\r
+ this.id = id;\r
+ this.tg = tg;\r
+ }\r
+ \r
+ public Object getId() {\r
+ return id;\r
+ }\r
+ \r
+ public IUList pushThis(IUList node) {\r
+ IUList result = tgLists.get(node);\r
+ if(result == null) {\r
+ result = new IUList(this, node);\r
+ tgLists.put(node, result);\r
+ }\r
+ return result;\r
+ }\r
+ \r
+ public IdentityNode defineIdentity(IdentityNode root, TIntIntHashMap identityIdToIdentityIndex, Identity identity) {\r
+ IdentityDefinition definition = identity.definition;\r
+ if(identities[identity.resource] != null) return identities[identity.resource]; \r
+ if(definition instanceof External) {\r
+ External def = (External)definition;\r
+ IdentityNode in = identities[def.parent];\r
+ if(in == null)\r
+ in = defineIdentity(root, identityIdToIdentityIndex, tg.identities[identityIdToIdentityIndex.get(def.parent)]);\r
+ IdentityNode node = in.get(def.name); \r
+ node.requires = pushThis(node.requires);\r
+ identities[identity.resource] = node;\r
+ return node;\r
+ }\r
+ else if(definition instanceof Internal) {\r
+ Internal def = (Internal)definition;\r
+ IdentityNode in = identities[def.parent];\r
+ if(in == null)\r
+ in = defineIdentity(root, identityIdToIdentityIndex, tg.identities[identityIdToIdentityIndex.get(def.parent)]);\r
+ IdentityNode node = in.get(def.name); \r
+ node.provides = pushThis(node.provides);\r
+ identities[identity.resource] = node;\r
+ return node;\r
+ }\r
+ else if(definition instanceof Root) {\r
+ Root def = (Root)definition;\r
+ IdentityNode node = root.get(def.name);\r
+ identities[identity.resource] = node;\r
+ return node;\r
+ }\r
+ else if(definition instanceof Optional) {\r
+ Optional def = (Optional)definition;\r
+ IdentityNode node = identities[def.parent].get(def.name);\r
+ node.providesOptionally = pushThis(node.providesOptionally);\r
+ identities[identity.resource] = node;\r
+ return node;\r
+ }\r
+ throw new IllegalStateException("definition: " + definition);\r
+ }\r
+ \r
+ public void findIdentities(IdentityNode root) {\r
+ identities = new IdentityNode[tg.resourceCount];\r
+ TIntIntHashMap identityIdToIdentityIndex = new TIntIntHashMap();\r
+ for(int i=0;i<tg.identities.length;i++) {\r
+ Identity id = tg.identities[i];\r
+ identityIdToIdentityIndex.put(id.resource, i);\r
+ }\r
+ for(Identity identity : tg.identities) {\r
+ defineIdentity(root, identityIdToIdentityIndex, identity);\r
+ }\r
+ }\r
+\r
+ @Override\r
+ public int compareTo(IU o) {\r
+ return id.compareTo(o.id);\r
+ }\r
+ }\r
+ \r
+ private static class IUPair {\r
+ public final IU a, b;\r
+ public IUPair(IU a, IU b) { \r
+ this.a = a;\r
+ this.b = b;\r
+ }\r
+ @Override\r
+ public int hashCode() {\r
+ return a.hashCode() + 31 * b.hashCode();\r
+ }\r
+ @Override\r
+ public boolean equals(Object obj) {\r
+ if(this == obj)\r
+ return true;\r
+ IUPair other = (IUPair)obj;\r
+ return a==other.a && b == other.b;\r
+ }\r
+ }\r
+ \r
+ private static class IUListPair {\r
+ public final IUList a;\r
+ public final IU b;\r
+ public IUListPair(IUList a, IU b) { \r
+ this.a = a;\r
+ this.b = b;\r
+ }\r
+ @Override\r
+ public int hashCode() {\r
+ return a.hashCode() + 31 * b.hashCode();\r
+ }\r
+ @Override\r
+ public boolean equals(Object obj) {\r
+ if(this == obj)\r
+ return true;\r
+ IUListPair other = (IUListPair)obj;\r
+ return a==other.a && b == other.b;\r
+ }\r
+ }\r
+ \r
+ private THashSet<IUPair> conflicts = new THashSet<IUPair>();\r
+ private THashSet<IUListPair> handled = new THashSet<IUListPair>();\r
+ \r
+ private void addConflicts(IUList a) {\r
+ while(a != null) {\r
+ IUList b = a.tail;\r
+ while(b != null) {\r
+ conflicts.add(new IUPair(a.head, b.head));\r
+ b=b.tail;\r
+ }\r
+ a = a.tail;\r
+ }\r
+ }\r
+ \r
+ private void addDependencies(IUList ius, IU dependency) { \r
+ while(ius != null) {\r
+ ius.head.dependencies.add(dependency); \r
+ ius = ius.tail;\r
+ }\r
+ }\r
+ \r
+ private void analyzeDependency(IdentityNode node) {\r
+ if(node.provides != null) {\r
+ if(node.provides.tail != null) {\r
+ addConflicts(node.provides);\r
+ }\r
+ else {\r
+ if(node.requires != null && handled.add(new IUListPair(node.requires, node.provides.head)))\r
+ addDependencies(node.requires, node.provides.head);\r
+ }\r
+ } \r
+ else if(node.providesOptionally != null) {\r
+ if(handled.add(new IUListPair(node.requires, node.providesOptionally.head)))\r
+ addDependencies(node.requires, node.providesOptionally.head);\r
+ }\r
+ if(node.children != null)\r
+ for(IdentityNode child : node.children.values())\r
+ analyzeDependency(child);\r
+ } \r
+\r
+ /**\r
+ * Adds a graph to the analyzer\r
+ * @param id An identifier that is used when reporting the results.\r
+ * @param tg A tranferable graph.\r
+ */\r
+ public void addGraph(T id, TransferableGraph1 tg) {\r
+ assert(id != null);\r
+ IU iu = new IU(id, tg);\r
+ graphs.add(iu);\r
+ iu.findIdentities(root);\r
+ }\r
+ \r
+ ArrayList<T> sortedGraphs = new ArrayList<T>();\r
+ \r
+ class Sorter {\r
+ THashSet<IU> alreadyInList = new THashSet<IU>();\r
+ @SuppressWarnings("unchecked")\r
+ public void add(IU iu) {\r
+ if(alreadyInList.add(iu)) {\r
+ /*System.out.println(iu.id);\r
+ for(IU dep : iu.dependencies)\r
+ System.out.println(" " + dep.id);\r
+ */\r
+ ArrayList<IU> list = new ArrayList<IU>(iu.dependencies);\r
+ Collections.sort(list);\r
+ for(IU dep : list)\r
+ add(dep);\r
+ sortedGraphs.add((T)iu.id);\r
+ }\r
+ }\r
+ }\r
+ \r
+ private void sortByDependency() {\r
+ //System.out.println("SortByDependency");\r
+ sortedGraphs.clear();\r
+ Sorter sorter = new Sorter();\r
+ Collections.sort(graphs);\r
+ for(IU iu : graphs)\r
+ sorter.add(iu);\r
+ }\r
+\r
+ /**\r
+ * Analyzes the dependency between transferable graphs\r
+ * @return true, if there are no conflicts or cyclic dependencies\r
+ */\r
+ public boolean analyzeDependency() {\r
+ analyzeDependency(root);\r
+ sortByDependency();\r
+ return conflicts.isEmpty();\r
+ }\r
+\r
+ private ArrayList<IdentityNode> unsatisfiedRequirements = new ArrayList<IdentityNode>();\r
+ \r
+ private void doesSatisfyExternalDependencies(final ReadGraph g, IdentityNode node, Resource resource) { \r
+ try {\r
+ final Map<String, Resource> childMap = g.syncRequest(new UnescapedChildMapOfResource(resource));\r
+ if(node.children != null)\r
+ node.children.forEachEntry(new TObjectObjectProcedure<String, GraphDependencyAnalyzer.IdentityNode>() {\r
+ @Override\r
+ public boolean execute(String name, IdentityNode child) {\r
+ Resource childResource = childMap.get(name);\r
+ if(childResource == null) {\r
+ if(child.provides == null && child.requires != null)\r
+ unsatisfiedRequirements.add(child);\r
+ }\r
+ else\r
+ doesSatisfyExternalDependencies(g, child, childResource);\r
+ return true;\r
+ }\r
+ });\r
+ } catch(DatabaseException e) {\r
+ throw new RuntimeDatabaseException(e);\r
+ }\r
+ }\r
+ \r
+ /**\r
+ * Returns true if previously analyzed graphs are importable,\r
+ * i.e. all external dependencies are satisfied. This method can be called\r
+ * after {@code analyzeDependency} method.\r
+ */\r
+ public boolean doesSatisfyExternalDependencies(ReadGraph g) throws DatabaseException {\r
+ unsatisfiedRequirements.clear();\r
+ IdentityNode rootLibrary = root.get("");\r
+ if(rootLibrary != null)\r
+ try {\r
+ doesSatisfyExternalDependencies(g, root.get(""), g.getRootLibrary());\r
+ } catch(RuntimeDatabaseException e) {\r
+ Throwable cause = e.getCause();\r
+ if(cause instanceof DatabaseException)\r
+ throw (DatabaseException)cause;\r
+ else\r
+ throw e;\r
+ }\r
+ return unsatisfiedRequirements.isEmpty();\r
+ }\r
+ \r
+ public Read<Boolean> queryExternalDependenciesSatisfied = new Read<Boolean>() {\r
+ @Override\r
+ public Boolean perform(ReadGraph graph) throws DatabaseException {\r
+ return doesSatisfyExternalDependencies(graph);\r
+ }\r
+ }; \r
+ \r
+ /**\r
+ * Returns a collection URIs of all resources not found in the database.\r
+ * This method can be called after {@code doesSatisfyExternalDependencies} method.\r
+ * @return\r
+ */\r
+ public ArrayList<IdentityNode> getUnsatisfiedDependencies() {\r
+ return unsatisfiedRequirements;\r
+ }\r
+ \r
+ /**\r
+ * Returns all conflicting pairs of graphs. This method can be called after \r
+ * {@code analyzeDependency} method. \r
+ */\r
+ @SuppressWarnings("unchecked")\r
+ public Collection<Pair<T, T>> getConflicts() {\r
+ ArrayList<Pair<T,T>> result = new ArrayList<Pair<T,T>>();\r
+ for(IUPair pair : conflicts)\r
+ result.add(Pair.make((T)pair.a.id, (T)pair.b.id));\r
+ return result;\r
+ }\r
+ \r
+ /**\r
+ * Returns a list sorted by dependency so that if A depends on B\r
+ * then A is in the list later than B.\r
+ * @return\r
+ */\r
+ public List<T> getSortedGraphs() {\r
+ return sortedGraphs;\r
+ }\r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff