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;fp=bundles%2Forg.simantics.graph.db%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fdb%2FGraphDependencyAnalyzer.java;h=5c5b1500c58836a5f2928d421b56751373778423;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;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
new file mode 100644
index 000000000..5c5b1500c
--- /dev/null
+++ b/bundles/org.simantics.graph.db/src/org/simantics/graph/db/GraphDependencyAnalyzer.java
@@ -0,0 +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:
+ * <pre>
+GraphDependencyAnalyzer<TransferableGraph1> analyzer =
+    new GraphDependencyAnalyzer<TransferableGraph1>();
+for(TransferableGraph1 tg : tgs)
+    analyzer.addGraph(tg, tg);
+if(!analyzer.analyzeDependency()) {
+    <Report problems> analyzer.getConflicts()
+}
+else if(!analyzer.doesSatisfyExternalDependencies(graph)) {
+    <Report problems> analyzer.getUnsatisfiedDependencies()
+}
+else
+    for(TransferableGraph1 tg : analyzer.getSortedGraphs())
+		<Import> tg
+}
+ * </pre>
+ * @author Hannu Niemist�
+ */
+public class GraphDependencyAnalyzer<T extends Comparable<T>> {
+
+	private ArrayList<IU> graphs = new ArrayList<IU>();
+	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<IU> toCollection(IUList list) {
+	    ArrayList<IU> result = new ArrayList<IU>();
+	    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<String, IdentityNode> 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<String, IdentityNode>(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<IU> {
+		final Comparable id;
+		final TransferableGraph1 tg;
+		IdentityNode[] identities;
+		THashMap<IUList, IUList> tgLists = new THashMap<IUList, IUList>();
+		THashSet<IU> dependencies = new THashSet<IU>();
+
+		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<tg.identities.length;i++) {
+				Identity id = tg.identities[i];
+				identityIdToIdentityIndex.put(id.resource, i);
+			}
+			for(Identity identity : tg.identities) {
+				defineIdentity(root, identityIdToIdentityIndex, identity);
+			}
+		}
+
+        @Override
+        public int compareTo(IU o) {
+            return id.compareTo(o.id);
+        }
+	}
+	
+	private static class IUPair {
+		public final IU a, b;
+		public IUPair(IU a, IU b) {		
+			this.a = a;
+			this.b = b;
+		}
+		@Override
+		public int hashCode() {
+			return a.hashCode() + 31 * b.hashCode();
+		}
+		@Override
+		public boolean equals(Object obj) {
+			if(this == obj)
+				return true;
+			IUPair other = (IUPair)obj;
+			return a==other.a && b == other.b;
+		}
+	}
+	
+	private static class IUListPair {
+		public final IUList a;
+		public final IU b;
+		public IUListPair(IUList a, IU b) {		
+			this.a = a;
+			this.b = b;
+		}
+		@Override
+		public int hashCode() {
+			return a.hashCode() + 31 * b.hashCode();
+		}
+		@Override
+		public boolean equals(Object obj) {
+			if(this == obj)
+				return true;
+			IUListPair other = (IUListPair)obj;
+			return a==other.a && b == other.b;
+		}
+	}
+	
+	private THashSet<IUPair> conflicts = new THashSet<IUPair>();
+	private THashSet<IUListPair> handled = new THashSet<IUListPair>();
+	
+	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<T> sortedGraphs = new ArrayList<T>();
+	
+	class Sorter {
+		THashSet<IU> alreadyInList = new THashSet<IU>();
+		@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<IU> list = new ArrayList<IU>(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<IdentityNode> unsatisfiedRequirements = new ArrayList<IdentityNode>();
+	
+	private void doesSatisfyExternalDependencies(final ReadGraph g, IdentityNode node, Resource resource) {		
+		try {
+			final Map<String, Resource> childMap = g.syncRequest(new UnescapedChildMapOfResource(resource));
+			if(node.children != null)
+				node.children.forEachEntry(new TObjectObjectProcedure<String, GraphDependencyAnalyzer.IdentityNode>() {
+					@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<Boolean> queryExternalDependenciesSatisfied = new Read<Boolean>() {
+		@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<IdentityNode> getUnsatisfiedDependencies() {
+		return unsatisfiedRequirements;
+	}
+	
+	/**
+	 * Returns all conflicting pairs of graphs. This method can be called after 
+	 * {@code analyzeDependency} method. 
+	 */
+	@SuppressWarnings("unchecked")
+    public Collection<Pair<T, T>> getConflicts() {
+		ArrayList<Pair<T,T>> result = new ArrayList<Pair<T,T>>();
+		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<T> getSortedGraphs() {
+		return sortedGraphs;
+	}
+		
+}