1 package org.simantics.graph.db;
3 import java.util.ArrayList;
4 import java.util.Collection;
5 import java.util.Collections;
9 import org.simantics.db.ReadGraph;
10 import org.simantics.db.Resource;
11 import org.simantics.db.common.uri.UnescapedChildMapOfResource;
12 import org.simantics.db.exception.DatabaseException;
13 import org.simantics.db.exception.RuntimeDatabaseException;
14 import org.simantics.db.request.Read;
15 import org.simantics.graph.representation.External;
16 import org.simantics.graph.representation.Identity;
17 import org.simantics.graph.representation.IdentityDefinition;
18 import org.simantics.graph.representation.Internal;
19 import org.simantics.graph.representation.Optional;
20 import org.simantics.graph.representation.Root;
21 import org.simantics.graph.representation.TransferableGraph1;
22 import org.simantics.utils.datastructures.Pair;
24 import gnu.trove.map.hash.THashMap;
25 import gnu.trove.map.hash.TIntIntHashMap;
26 import gnu.trove.procedure.TObjectObjectProcedure;
27 import gnu.trove.set.hash.THashSet;
30 * Analyses the dependencies between transferable graphs. Usage:
32 GraphDependencyAnalyzer<TransferableGraph1> analyzer =
33 new GraphDependencyAnalyzer<TransferableGraph1>();
34 for(TransferableGraph1 tg : tgs)
35 analyzer.addGraph(tg, tg);
36 if(!analyzer.analyzeDependency()) {
37 <Report problems> analyzer.getConflicts()
39 else if(!analyzer.doesSatisfyExternalDependencies(graph)) {
40 <Report problems> analyzer.getUnsatisfiedDependencies()
43 for(TransferableGraph1 tg : analyzer.getSortedGraphs())
47 * @author Hannu Niemist�
49 public class GraphDependencyAnalyzer<T extends Comparable<T>> {
51 private ArrayList<IU> graphs = new ArrayList<IU>();
52 private IdentityNode root = new IdentityNode(null, null);
54 public static class IUList {
58 public IUList(IU head, IUList tail) {
64 public static Collection<IU> toCollection(IUList list) {
65 ArrayList<IU> result = new ArrayList<IU>();
67 result.add(list.head);
73 public static class IdentityNode {
76 IUList provides = null;
77 IUList providesOptionally = null;
78 IUList requires = null;
79 THashMap<String, IdentityNode> children = null;
81 public IdentityNode(IdentityNode parent, String name) {
86 public IdentityNode get(String name) {
87 if(children == null) {
88 children = new THashMap<String, IdentityNode>(4);
89 IdentityNode node = new IdentityNode(this, name);
90 children.put(name, node);
94 IdentityNode node = children.get(name);
96 node = new IdentityNode(this, name);
97 children.put(name, node);
104 public String toString() {
105 if(parent == null || parent.parent == null) {
111 return parent.toString() + "/" + name;
114 public IUList getRequires() {
119 public static class IU implements Comparable<IU> {
121 final TransferableGraph1 tg;
122 IdentityNode[] identities;
123 THashMap<IUList, IUList> tgLists = new THashMap<IUList, IUList>();
124 THashSet<IU> dependencies = new THashSet<IU>();
126 public IU(Comparable id, TransferableGraph1 tg) {
131 public Object getId() {
135 public IUList pushThis(IUList node) {
136 IUList result = tgLists.get(node);
138 result = new IUList(this, node);
139 tgLists.put(node, result);
144 public IdentityNode defineIdentity(IdentityNode root, TIntIntHashMap identityIdToIdentityIndex, Identity identity) {
145 IdentityDefinition definition = identity.definition;
146 if(identities[identity.resource] != null) return identities[identity.resource];
147 if(definition instanceof External) {
148 External def = (External)definition;
149 IdentityNode in = identities[def.parent];
151 in = defineIdentity(root, identityIdToIdentityIndex, tg.identities[identityIdToIdentityIndex.get(def.parent)]);
152 IdentityNode node = in.get(def.name);
153 node.requires = pushThis(node.requires);
154 identities[identity.resource] = node;
157 else if(definition instanceof Internal) {
158 Internal def = (Internal)definition;
159 IdentityNode in = identities[def.parent];
161 in = defineIdentity(root, identityIdToIdentityIndex, tg.identities[identityIdToIdentityIndex.get(def.parent)]);
162 IdentityNode node = in.get(def.name);
163 node.provides = pushThis(node.provides);
164 identities[identity.resource] = node;
167 else if(definition instanceof Root) {
168 Root def = (Root)definition;
169 IdentityNode node = root.get(def.name);
170 identities[identity.resource] = node;
173 else if(definition instanceof Optional) {
174 Optional def = (Optional)definition;
175 IdentityNode node = identities[def.parent].get(def.name);
176 node.providesOptionally = pushThis(node.providesOptionally);
177 identities[identity.resource] = node;
180 throw new IllegalStateException("definition: " + definition);
183 public void findIdentities(IdentityNode root) {
184 identities = new IdentityNode[tg.resourceCount];
185 TIntIntHashMap identityIdToIdentityIndex = new TIntIntHashMap();
186 for(int i=0;i<tg.identities.length;i++) {
187 Identity id = tg.identities[i];
188 identityIdToIdentityIndex.put(id.resource, i);
190 for(Identity identity : tg.identities) {
191 defineIdentity(root, identityIdToIdentityIndex, identity);
196 public int compareTo(IU o) {
197 return id.compareTo(o.id);
201 private static class IUPair {
202 public final IU a, b;
203 public IUPair(IU a, IU b) {
208 public int hashCode() {
209 return a.hashCode() + 31 * b.hashCode();
212 public boolean equals(Object obj) {
215 IUPair other = (IUPair)obj;
216 return a==other.a && b == other.b;
220 private static class IUListPair {
221 public final IUList a;
223 public IUListPair(IUList a, IU b) {
228 public int hashCode() {
229 return a.hashCode() + 31 * b.hashCode();
232 public boolean equals(Object obj) {
235 IUListPair other = (IUListPair)obj;
236 return a==other.a && b == other.b;
240 private THashSet<IUPair> conflicts = new THashSet<IUPair>();
241 private THashSet<IUListPair> handled = new THashSet<IUListPair>();
243 private void addConflicts(IUList a) {
247 conflicts.add(new IUPair(a.head, b.head));
254 private void addDependencies(IUList ius, IU dependency) {
256 ius.head.dependencies.add(dependency);
261 private void analyzeDependency(IdentityNode node) {
262 if(node.provides != null) {
263 if(node.provides.tail != null) {
264 addConflicts(node.provides);
267 if(node.requires != null && handled.add(new IUListPair(node.requires, node.provides.head)))
268 addDependencies(node.requires, node.provides.head);
271 else if(node.providesOptionally != null) {
272 if(handled.add(new IUListPair(node.requires, node.providesOptionally.head)))
273 addDependencies(node.requires, node.providesOptionally.head);
275 if(node.children != null)
276 for(IdentityNode child : node.children.values())
277 analyzeDependency(child);
281 * Adds a graph to the analyzer
282 * @param id An identifier that is used when reporting the results.
283 * @param tg A tranferable graph.
285 public void addGraph(T id, TransferableGraph1 tg) {
287 IU iu = new IU(id, tg);
289 iu.findIdentities(root);
292 ArrayList<T> sortedGraphs = new ArrayList<T>();
295 THashSet<IU> alreadyInList = new THashSet<IU>();
296 @SuppressWarnings("unchecked")
297 public void add(IU iu) {
298 if(alreadyInList.add(iu)) {
299 /*System.out.println(iu.id);
300 for(IU dep : iu.dependencies)
301 System.out.println(" " + dep.id);
303 ArrayList<IU> list = new ArrayList<IU>(iu.dependencies);
304 Collections.sort(list);
307 sortedGraphs.add((T)iu.id);
312 private void sortByDependency() {
313 //System.out.println("SortByDependency");
314 sortedGraphs.clear();
315 Sorter sorter = new Sorter();
316 Collections.sort(graphs);
322 * Analyzes the dependency between transferable graphs
323 * @return true, if there are no conflicts or cyclic dependencies
325 public boolean analyzeDependency() {
326 analyzeDependency(root);
328 return conflicts.isEmpty();
331 private ArrayList<IdentityNode> unsatisfiedRequirements = new ArrayList<IdentityNode>();
333 private void doesSatisfyExternalDependencies(final ReadGraph g, IdentityNode node, Resource resource) {
335 final Map<String, Resource> childMap = g.syncRequest(new UnescapedChildMapOfResource(resource));
336 if(node.children != null)
337 node.children.forEachEntry(new TObjectObjectProcedure<String, GraphDependencyAnalyzer.IdentityNode>() {
339 public boolean execute(String name, IdentityNode child) {
340 Resource childResource = childMap.get(name);
341 if(childResource == null) {
342 if(child.provides == null && child.requires != null)
343 unsatisfiedRequirements.add(child);
346 doesSatisfyExternalDependencies(g, child, childResource);
350 } catch(DatabaseException e) {
351 throw new RuntimeDatabaseException(e);
356 * Returns true if previously analyzed graphs are importable,
357 * i.e. all external dependencies are satisfied. This method can be called
358 * after {@code analyzeDependency} method.
360 public boolean doesSatisfyExternalDependencies(ReadGraph g) throws DatabaseException {
361 unsatisfiedRequirements.clear();
362 IdentityNode rootLibrary = root.get("");
363 if(rootLibrary != null)
365 doesSatisfyExternalDependencies(g, root.get(""), g.getRootLibrary());
366 } catch(RuntimeDatabaseException e) {
367 Throwable cause = e.getCause();
368 if(cause instanceof DatabaseException)
369 throw (DatabaseException)cause;
373 return unsatisfiedRequirements.isEmpty();
376 public Read<Boolean> queryExternalDependenciesSatisfied = new Read<Boolean>() {
378 public Boolean perform(ReadGraph graph) throws DatabaseException {
379 return doesSatisfyExternalDependencies(graph);
384 * Returns a collection URIs of all resources not found in the database.
385 * This method can be called after {@code doesSatisfyExternalDependencies} method.
388 public ArrayList<IdentityNode> getUnsatisfiedDependencies() {
389 return unsatisfiedRequirements;
393 * Returns all conflicting pairs of graphs. This method can be called after
394 * {@code analyzeDependency} method.
396 @SuppressWarnings("unchecked")
397 public Collection<Pair<T, T>> getConflicts() {
398 ArrayList<Pair<T,T>> result = new ArrayList<Pair<T,T>>();
399 for(IUPair pair : conflicts)
400 result.add(Pair.make((T)pair.a.id, (T)pair.b.id));
405 * Returns a list sorted by dependency so that if A depends on B
406 * then A is in the list later than B.
409 public List<T> getSortedGraphs() {