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

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