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