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