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;
}
}