bundles/org.simantics.graph.db/src/org/simantics/graph/db/GraphDependencyAnalyzer.java

   1 package org.simantics.graph.db;
   2
   3 import java.util.ArrayList;
   4 import java.util.Collection;
   5 import java.util.Collections;
   6 import java.util.List;
   7 import java.util.Map;
   8
   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;
  23
  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;
  28
  29 /**
  30  * Analyses the dependencies between transferable graphs. Usage:
  31  * <pre>
  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()
  38 }
  39 else if(!analyzer.doesSatisfyExternalDependencies(graph)) {
  40     <Report problems> analyzer.getUnsatisfiedDependencies()
  41 }
  42 else
  43     for(TransferableGraph1 tg : analyzer.getSortedGraphs())
  44                 <Import> tg
  45 }
  46  * </pre>
  47  * @author Hannu Niemist�
  48  */
  49 public class GraphDependencyAnalyzer<T extends Comparable<T>> {
  50
  51         private ArrayList<IU> graphs = new ArrayList<IU>();
  52         private IdentityNode root = new IdentityNode(null, null);
  53
  54         public static class IUList {
  55                 IU head;
  56                 IUList tail;
  57
  58                 public IUList(IU head, IUList tail) {
  59                         this.head = head;
  60                         this.tail = tail;
  61                 }
  62         }
  63
  64         public static Collection<IU> toCollection(IUList list) {
  65             ArrayList<IU> result = new ArrayList<IU>();
  66             while(list != null) {
  67                 result.add(list.head);
  68                 list = list.tail;
  69             }
  70             return result;
  71         }
  72
  73         public static class IdentityNode {
  74                 IdentityNode parent;
  75                 String name;
  76                 IUList provides = null;
  77                 IUList providesOptionally = null;
  78                 IUList requires = null;
  79                 THashMap<String, IdentityNode> children = null;
  80
  81                 public IdentityNode(IdentityNode parent, String name) {
  82                         this.parent = parent;
  83                         this.name = name;
  84                 }
  85
  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);
  91                                 return node;
  92                         }
  93                         else {
  94                                 IdentityNode node = children.get(name);
  95                                 if(node == null) {
  96                                         node = new IdentityNode(this, name);
  97                                         children.put(name, node);
  98                                 }
  99                                 return node;
 100                         }
 101                 }
 102
 103                 @Override
 104                 public String toString() {
 105                         if(parent == null || parent.parent == null) {
 106                                 if(name.equals(""))
 107                                         return "http:/";
 108                                 else
 109                                         return name;
 110                         }
 111                         return parent.toString() + "/" + name;
 112                 }
 113
 114                 public IUList getRequires() {
 115             return requires;
 116         }
 117         }
 118
 119         public static class IU implements Comparable<IU> {
 120                 final Comparable id;
 121                 final TransferableGraph1 tg;
 122                 IdentityNode[] identities;
 123                 THashMap<IUList, IUList> tgLists = new THashMap<IUList, IUList>();
 124                 THashSet<IU> dependencies = new THashSet<IU>();
 125
 126                 public IU(Comparable id, TransferableGraph1 tg) {
 127                         this.id = id;
 128                         this.tg = tg;
 129                 }
 130
 131                 public Object getId() {
 132             return id;
 133         }
 134
 135                 public IUList pushThis(IUList node) {
 136                         IUList result = tgLists.get(node);
 137                         if(result == null) {
 138                                 result = new IUList(this, node);
 139                                 tgLists.put(node, result);
 140                         }
 141                         return result;
 142                 }
 143
 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];
 150                                 if(in == null)
 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;
 155                                 return node;
 156                         }
 157                         else if(definition instanceof Internal) {
 158                                 Internal def = (Internal)definition;
 159                                 IdentityNode in = identities[def.parent];
 160                                 if(in == null)
 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;
 165                                 return node;
 166                         }
 167                         else if(definition instanceof Root) {
 168                                 Root def = (Root)definition;
 169                                 IdentityNode node = root.get(def.name);
 170                                 identities[identity.resource] = node;
 171                                 return node;
 172                         }
 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;
 178                                 return node;
 179                         }
 180                         throw new IllegalStateException("definition: " + definition);
 181                 }
 182
 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);
 189                         }
 190                         for(Identity identity : tg.identities) {
 191                                 defineIdentity(root, identityIdToIdentityIndex, identity);
 192                         }
 193                 }
 194
 195         @Override
 196         public int compareTo(IU o) {
 197             return id.compareTo(o.id);
 198         }
 199         }
 200
 201         private static class IUPair {
 202                 public final IU a, b;
 203                 public IUPair(IU a, IU b) {
 204                         this.a = a;
 205                         this.b = b;
 206                 }
 207                 @Override
 208                 public int hashCode() {
 209                         return a.hashCode() + 31 * b.hashCode();
 210                 }
 211                 @Override
 212                 public boolean equals(Object obj) {
 213                         if(this == obj)
 214                                 return true;
 215                         IUPair other = (IUPair)obj;
 216                         return a==other.a && b == other.b;
 217                 }
 218         }
 219
 220         private static class IUListPair {
 221                 public final IUList a;
 222                 public final IU b;
 223                 public IUListPair(IUList a, IU b) {
 224                         this.a = a;
 225                         this.b = b;
 226                 }
 227                 @Override
 228                 public int hashCode() {
 229                         return a.hashCode() + 31 * b.hashCode();
 230                 }
 231                 @Override
 232                 public boolean equals(Object obj) {
 233                         if(this == obj)
 234                                 return true;
 235                         IUListPair other = (IUListPair)obj;
 236                         return a==other.a && b == other.b;
 237                 }
 238         }
 239
 240         private THashSet<IUPair> conflicts = new THashSet<IUPair>();
 241         private THashSet<IUListPair> handled = new THashSet<IUListPair>();
 242
 243         private void addConflicts(IUList a) {
 244                 while(a != null) {
 245                         IUList b = a.tail;
 246                         while(b != null) {
 247                                 conflicts.add(new IUPair(a.head, b.head));
 248                                 b=b.tail;
 249                         }
 250                         a = a.tail;
 251                 }
 252         }
 253
 254         private void addDependencies(IUList ius, IU dependency) {
 255                 while(ius != null) {
 256                         ius.head.dependencies.add(dependency);
 257                         ius = ius.tail;
 258                 }
 259         }
 260
 261         private void analyzeDependency(IdentityNode node) {
 262                 if(node.provides != null) {
 263                         if(node.provides.tail != null) {
 264                                 addConflicts(node.provides);
 265                         }
 266                         else {
 267                                 if(node.requires != null && handled.add(new IUListPair(node.requires, node.provides.head)))
 268                                         addDependencies(node.requires, node.provides.head);
 269                         }
 270                 }
 271                 else if(node.providesOptionally != null) {
 272                         if(handled.add(new IUListPair(node.requires, node.providesOptionally.head)))
 273                                 addDependencies(node.requires, node.providesOptionally.head);
 274                 }
 275                 if(node.children != null)
 276                         for(IdentityNode child : node.children.values())
 277                                 analyzeDependency(child);
 278         }
 279
 280         /**
 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.
 284          */
 285         public void addGraph(T id, TransferableGraph1 tg) {
 286                 assert(id != null);
 287                 IU iu = new IU(id, tg);
 288                 graphs.add(iu);
 289                 iu.findIdentities(root);
 290         }
 291
 292         ArrayList<T> sortedGraphs = new ArrayList<T>();
 293
 294         class Sorter {
 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);
 302                                 */
 303                             ArrayList<IU> list = new ArrayList<IU>(iu.dependencies);
 304                             Collections.sort(list);
 305                                 for(IU dep : list)
 306                                         add(dep);
 307                                 sortedGraphs.add((T)iu.id);
 308                         }
 309                 }
 310         }
 311
 312         private void sortByDependency() {
 313                 //System.out.println("SortByDependency");
 314                 sortedGraphs.clear();
 315                 Sorter sorter = new Sorter();
 316                 Collections.sort(graphs);
 317                 for(IU iu : graphs)
 318                         sorter.add(iu);
 319         }
 320
 321         /**
 322          * Analyzes the dependency between transferable graphs
 323          * @return true, if there are no conflicts or cyclic dependencies
 324          */
 325         public boolean analyzeDependency() {
 326                 analyzeDependency(root);
 327                 sortByDependency();
 328                 return conflicts.isEmpty();
 329         }
 330
 331         private ArrayList<IdentityNode> unsatisfiedRequirements = new ArrayList<IdentityNode>();
 332
 333         private void doesSatisfyExternalDependencies(final ReadGraph g, IdentityNode node, Resource resource) {
 334                 try {
 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>() {
 338                                         @Override
 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);
 344                                                 }
 345                                                 else
 346                                                         doesSatisfyExternalDependencies(g, child, childResource);
 347                                                 return true;
 348                                         }
 349                                 });
 350                 } catch(DatabaseException e) {
 351                         throw new RuntimeDatabaseException(e);
 352                 }
 353         }
 354
 355         /**
 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.
 359          */
 360         public boolean doesSatisfyExternalDependencies(ReadGraph g) throws DatabaseException {
 361                 unsatisfiedRequirements.clear();
 362                 IdentityNode rootLibrary = root.get("");
 363                 if(rootLibrary != null)
 364                         try {
 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;
 370                                 else
 371                                         throw e;
 372                         }
 373                 return unsatisfiedRequirements.isEmpty();
 374         }
 375
 376         public Read<Boolean> queryExternalDependenciesSatisfied = new Read<Boolean>() {
 377                 @Override
 378                 public Boolean perform(ReadGraph graph) throws DatabaseException {
 379                         return doesSatisfyExternalDependencies(graph);
 380                 }
 381         };
 382
 383         /**
 384          * Returns a collection URIs of all resources not found in the database.
 385          * This method can be called after {@code doesSatisfyExternalDependencies} method.
 386          * @return
 387          */
 388         public ArrayList<IdentityNode> getUnsatisfiedDependencies() {
 389                 return unsatisfiedRequirements;
 390         }
 391
 392         /**
 393          * Returns all conflicting pairs of graphs. This method can be called after
 394          * {@code analyzeDependency} method.
 395          */
 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));
 401                 return result;
 402         }
 403
 404         /**
 405          * Returns a list sorted by dependency so that if A depends on B
 406          * then A is in the list later than B.
 407          * @return
 408          */
 409         public List<T> getSortedGraphs() {
 410                 return sortedGraphs;
 411         }
 412
 413 }