New implementation NearestOwnerFinder of CommonDBUtils.getNearestOwner 66/2366/1
authorHannu Niemistö <hannu.niemisto@semantum.fi>
Fri, 26 Oct 2018 13:19:20 +0000 (16:19 +0300)
committerHannu Niemistö <hannu.niemisto@semantum.fi>
Fri, 26 Oct 2018 13:19:20 +0000 (16:19 +0300)
Deprecated CommonDBUtils.getNearestOwner and replaced most of its uses
by new methods in the class NearestOwnerFinder. Note that this modifies
the behavior in some previously unclear cases.

gitlab #163

Change-Id: Ic56671ee549765ce67fa574967c103f2ab7aac0e

bundles/org.simantics.db.common/src/org/simantics/db/common/request/PossibleOwner.java
bundles/org.simantics.db.common/src/org/simantics/db/common/utils/CommonDBUtils.java
bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java [new file with mode: 0644]
bundles/org.simantics.db.layer0/src/org/simantics/db/layer0/function/All.java
bundles/org.simantics.structural2/src/org/simantics/structural2/variables/ConnectionBrowser.java

index a39b257d2d4141fc771c341fba6c2994834fa0a8..6df6910267c59e109d10dea329e13b5179f38e85 100644 (file)
@@ -1,12 +1,9 @@
 package org.simantics.db.common.request;
 
-import java.util.Collections;
-
 import org.simantics.db.ReadGraph;
 import org.simantics.db.Resource;
-import org.simantics.db.common.utils.CommonDBUtils;
+import org.simantics.db.common.utils.NearestOwnerFinder;
 import org.simantics.db.exception.DatabaseException;
-import org.simantics.layer0.Layer0;
 
 public class PossibleOwner extends ResourceRead<Resource> {
 
@@ -16,10 +13,7 @@ public class PossibleOwner extends ResourceRead<Resource> {
 
     @Override
     public Resource perform(ReadGraph graph) throws DatabaseException {
-        Layer0 L0 = Layer0.getInstance(graph);
-        Resource directOwner = graph.getPossibleObject(resource, L0.IsOwnedBy);
-        if(directOwner != null) return directOwner;
-        return CommonDBUtils.getNearestOwner(graph, Collections.singleton(resource));
+        return NearestOwnerFinder.getNearestOwner(graph, resource);
     }
     
 }
\ No newline at end of file
index 80924148e85e88fad749b5f360bc43ec804d5ab4..a07d42519c45741c1cd5c8c038502ca06c4fab4e 100644 (file)
@@ -119,101 +119,23 @@ public class CommonDBUtils {
         return owners;
     }
     
+    /**
+     * This method didn't have a clear specification and therefore should not be used. Use instead
+     * the methods in the class {@link NearestOwnerFinder}.
+     */
+    @Deprecated
     public static Resource getNearestOwner(ReadGraph graph, Collection<Resource> resources) throws DatabaseException {
-        return getNearestOwner(graph, resources, null);
-    }
-       
-    private static Resource getNearestOwner(ReadGraph graph, Collection<Resource> resources, THashSet<Resource> infiniteRecursionBreaker) throws DatabaseException {
-
-        Layer0 L0 = Layer0.getInstance(graph);
-        
-        // These are resources that are linked to some of the input resources by IsComposedOf
-        Set<Resource> directOwners = new HashSet<Resource>();
-        
-        // These are resources that refer to some of the input resources which don't have an owner
-        Set<Resource> referringResources = new HashSet<Resource>();
-        
-        for(Resource r : resources) {
-            
-            Collection<Resource> owners = graph.getObjects(r, L0.IsOwnedBy);
-            // TODO: getObjects returns duplicate entries (https://www.simantics.org/redmine/issues/4885) and therefore direct is Set<Resource>. Fix getObjects to not return duplicate entries
-            if (owners.size() > 1) {
-                owners = new HashSet<Resource>(owners);
-                if (owners.size() > 1) {
-                    LOGGER.error("Multiple owners for {}, id: {}", graph.getPossibleURI(r), r);
-                    for (Resource r2 : owners)
-                        LOGGER.error("    owner: {}, id: {}", graph.getPossibleURI(r2), r2);
-                    return null;
-                }
-            }
-            
-            if (owners.isEmpty()) {
-                // If there are no owners, collect resources referring to this resource by IsRelatedTo
-                for(Statement stm : graph.getStatements(r, L0.IsWeaklyRelatedTo)) {
-                    Resource inverse = graph.getPossibleInverse(stm.getPredicate());
-                    if(inverse != null) {
-                        if(graph.isSubrelationOf(inverse, L0.IsRelatedTo)) {
-                            // Filter away tags
-                            if(r.equals(stm.getObject()))
-                                continue;
-                            referringResources.add(stm.getObject());
-                        }
-                    }
-                }
-            }
-            else
-                directOwners.addAll(owners);
-        }
-        
-        if(!directOwners.isEmpty()) {
-            Iterator<Resource> iter = directOwners.iterator();
-            Resource common = iter.next();
-            while (iter.hasNext()) {
-                Resource other = iter.next();
-                common = commonAncestor(graph, common, other);
-                if (common == null)
-                    return null; // The
-            }
-            referringResources.add(common);
-        }
-        if(referringResources.isEmpty())
-            return null;
-        
-        if(!Collections.disjoint(referringResources, resources)) {
-            LOGGER.error("Overlapping owners:");
-            for(Resource r : resources)
-                LOGGER.error("    resource {}", NameUtils.getSafeName(graph, r, true));
-            for(Resource r : referringResources)
-                LOGGER.error("    owner {}", NameUtils.getSafeName(graph, r, true));
-            return null;
-        }
-        
-        if(referringResources.size() == 1)
-            return referringResources.iterator().next();
-        
-        // Prevent recursion on current input resources
-        if(infiniteRecursionBreaker == null)
-            infiniteRecursionBreaker = new THashSet<>(resources);
-        else {
-            if(!Collections.disjoint(infiniteRecursionBreaker, resources)) {
-                infiniteRecursionBreaker.retainAll(resources);
-                LOGGER.error("Resources have a cyclic reference loop preventing the discovery their owner. {}", infiniteRecursionBreaker);
-                return null;
-            }
-
-            infiniteRecursionBreaker.addAll(resources);
-        }
-        
-        return getNearestOwner(graph, referringResources, infiniteRecursionBreaker);
-        
+        if(resources.size() == 1)
+            return NearestOwnerFinder.getNearestOwner(graph, resources.iterator().next());
+        else
+            return NearestOwnerFinder.getNearestOwnerFromDirectOwners(graph, resources);
     }
     
     public static Resource getClusterSetForNewResource(ReadGraph graph, Resource ... resources) throws DatabaseException {
 
        if(resources.length == 1) return getClusterSetForNewResource(graph, resources[0]);
        
-        Resource owner = getNearestOwner(graph, CollectionUtils.toList(resources));
+        Resource owner = NearestOwnerFinder.getNearestOwnerFromDirectOwners(graph, CollectionUtils.toList(resources));
         if(owner == null) return null;
         return getClusterSetForNewResource(graph, owner, new HashSet<Resource>());
         
@@ -223,7 +145,7 @@ public class CommonDBUtils {
 
        if(resources.size() == 1) return getClusterSetForNewResource(graph, resources.iterator().next());
 
-        Resource owner = getNearestOwner(graph, resources);
+        Resource owner = NearestOwnerFinder.getNearestOwnerFromDirectOwners(graph, resources);
         return getClusterSetForNewResource(graph, owner, new HashSet<Resource>());
         
     }
diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java
new file mode 100644 (file)
index 0000000..062d1c8
--- /dev/null
@@ -0,0 +1,207 @@
+package org.simantics.db.common.utils;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+
+import org.simantics.db.ReadGraph;
+import org.simantics.db.Resource;
+import org.simantics.db.Statement;
+import org.simantics.db.exception.DatabaseException;
+import org.simantics.layer0.Layer0;
+
+import gnu.trove.map.hash.TObjectIntHashMap;
+import gnu.trove.set.hash.THashSet;
+
+/**
+ * <p>A utility to finds the nearest owner of a real or imaginary resource.</p>
+ * 
+ * <p>The nearest owner
+ * is found by first finding a path (pilot path) from the input to a root resource and then
+ * trying to find other paths to the resources in the pilot path such that the other
+ * paths don't visit other resources of the pilot path. The farthest resource so found
+ * is then the nearest common owner. See the methods for the exact specification.</p>
+ * 
+ * <p>The time and space complexity of the algorithm is O(m),
+ * where m is the number of resources reachable by direct-owners relation from the input.</p>
+ * 
+ * @see {@link #getNearestOwner(ReadGraph, Resource)}
+ * @see {@link #getNearestOwner(ReadGraph, Collection)}</p>
+ * 
+ */
+public class NearestOwnerFinder {
+    private static final int FIRST_DISTANCE = 1;
+    private static final int UNVISITED = 0;
+    private static final int NOT_INTERESTING_ANYMORE = -1;
+
+    private final ReadGraph graph;
+    private final Layer0 L0;
+
+    private final TObjectIntHashMap<Resource> resourceStatus = new TObjectIntHashMap<>();
+
+    private int nearestOwnerDistance; // = 0
+    private Resource nearestOwner; // = null
+
+    private NearestOwnerFinder(ReadGraph graph, Layer0 L0) {
+        this.graph = graph;
+        this.L0 = L0;
+    }
+
+    /**
+     * Iterates the owners of the input resource. It first
+     * tries to find the pilot path and when it has been found,
+     * it browses other owners with {@link #browseNonpilot}.
+     */
+    private void browseOwnersOfInput(Collection<Resource> owners) throws DatabaseException {
+        Iterator<Resource> it = owners.iterator();
+        while(it.hasNext()) {
+            Resource owner = it.next();
+            if(browsePilot(owner, FIRST_DISTANCE)) {
+                // Because we found a path to root, {@code owner}
+                // becomes our first candidate for nearestOwner.
+                nearestOwner = owner;
+                nearestOwnerDistance = FIRST_DISTANCE;
+                
+                // Tries to find other paths to the resource in the pilot path.
+                while(it.hasNext())
+                    browseNonpilot(it.next());
+                return;
+            }
+        }
+    }
+
+    /**
+     * Tries to find a first path (=pilot path) to a root with DFS.
+     */
+    private boolean browsePilot(Resource resource, int distance) throws DatabaseException {
+        if(resourceStatus.putIfAbsent(resource, distance) != UNVISITED)
+            // We recursed back to the current path or encountered previously failed path.
+            return false;
+
+        Collection<Resource> owners = getDirectOwners(graph, L0, resource);
+        if(owners.isEmpty())
+            // We found a root
+            return true;
+
+        for(Resource owner : owners)
+            if(browsePilot(owner, distance+1)) {
+                // We found a path to a root
+                return true;
+            }
+
+        // Failed to find a path to a root
+        resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
+        return false;
+    }
+
+    /**
+     * Tries to find some path to a resource on a pilot path using DFS.
+     * Marks all visited resource by {@code NOT_INTERESTING_ANYMORE}
+     * to prevent visiting the same resources more than once.
+     */
+    private void browseNonpilot(Resource resource) throws DatabaseException {
+        // In the next statement, we may overwrite also information about resource being on pilot path,
+        // but that is ok, because we don't care resources that are nearer than nearestOwnerDistance.
+        int status = resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
+        if(status == UNVISITED) {
+            Collection<Resource> owners = getDirectOwners(graph, L0, resource);
+            if(owners.isEmpty()) {
+                // This is a root that differs from the root at the end of the pilot path.
+                // Therefore there cannot be a nearest owner.
+                nearestOwnerDistance = Integer.MAX_VALUE;
+                nearestOwner = null;
+                return;
+            }
+            for(Resource owner : owners)
+                browseNonpilot(owner);
+        }
+        else if(status > nearestOwnerDistance) {
+            nearestOwnerDistance = status;
+            nearestOwner = resource;
+        }
+    }
+
+    private static Collection<Resource> getDirectOwners(ReadGraph graph, Layer0 L0, Resource resource) throws DatabaseException {
+        Collection<Resource> owners = graph.getObjects(resource, L0.IsOwnedBy);
+        if(owners.isEmpty()) {
+            if(resource.equals(graph.getRootLibrary()))
+                return Collections.emptyList();
+
+            owners = new THashSet<Resource>();
+
+            // If there are no owners, collect resources referring to this resource by IsRelatedTo
+            for(Statement statement : graph.getStatements(resource, L0.IsWeaklyRelatedTo)) {
+                Resource inverse = graph.getPossibleInverse(statement.getPredicate());
+                if(inverse != null) {
+                    if(graph.isSubrelationOf(inverse, L0.IsRelatedTo)) {
+                        // Filter away tags
+                        if(resource.equals(statement.getObject()))
+                            continue;
+                        owners.add(statement.getObject());
+                    }
+                }
+            }
+        }
+        else if(owners.size() > 1) {
+            // TODO: getObjects returns duplicate entries (https://www.simantics.org/redmine/issues/4885) and therefore direct is Set<Resource>.
+            // Fix getObjects to not return duplicate entries
+            owners = new HashSet<Resource>(owners);
+        }
+
+        return owners;
+    }
+
+    /**
+     * <p>Finds the nearest owner of a resource. Nearest owner is the
+     * <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">immediate dominator</a>
+     * of the resource in a graph defined in the following way:
+     * Each IsComposedOf statement is an edge of the graph.
+     * Additionally an IsRelatedTo statement in an edge of graph if
+     * no IsComposedOf statement points to its object.</p>
+     * 
+     * <p>The root of the graph is any resource without owners or the root resource
+     * of the database. If the search encounters two distinct roots, there
+     * cannot be a nearest owner.</p>
+     * 
+     * @return The nearest owner or {@code null} if no roots or more than one roots are found.
+     */
+    public static Resource getNearestOwner(ReadGraph graph, Resource resource) throws DatabaseException {
+        // Handle cases of one or zero direct owners
+        Layer0 L0 = Layer0.getInstance(graph);
+        Collection<Resource> owners = getDirectOwners(graph, L0, resource);
+        if(owners.size() == 1)
+            return owners.iterator().next();
+        if(owners.isEmpty())
+            return null;
+
+        // There are two or more direct owners
+        NearestOwnerFinder finder = new NearestOwnerFinder(graph, L0);
+        finder.resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
+        finder.browseOwnersOfInput(owners);
+        return finder.nearestOwner;
+    }
+    
+    /**
+     * <p>Finds the nearest owner of a real or imaginary resource whose direct owners are known. This works in the same
+     * way as the method for one resource {@link #getNearestOwner(ReadGraph, Resource)}
+     * but we add one extra node to the graph that has the input resources as direct owners and
+     * find the immediate dominator of that extra node.</p>
+     * 
+     * <p>Note that this method may return one of the input resources if it is dominator of all other
+     * resources in the collection. Returns {@code null} if the input collection is empty.</p>
+     */
+    public static Resource getNearestOwnerFromDirectOwners(ReadGraph graph, Collection<Resource> owners) throws DatabaseException {
+        // Handle the cases of one or zero direct owners
+        if(owners.size() == 1)
+            return owners.iterator().next();
+        if(owners.isEmpty())
+            return null;
+
+        // There are two or more direct owners
+        Layer0 L0 = Layer0.getInstance(graph);
+        NearestOwnerFinder finder = new NearestOwnerFinder(graph, L0);
+        finder.browseOwnersOfInput(owners);
+        return finder.nearestOwner;
+    }
+}
index 991a0500ce93dac89f4715fd301296b04d330863..f93023b77ccd36a6db7d44af8d9981f4a47fc983 100644 (file)
@@ -38,13 +38,13 @@ import org.simantics.db.common.utils.Functions;
 import org.simantics.db.common.utils.ListUtils;
 import org.simantics.db.common.utils.Logger;
 import org.simantics.db.common.utils.NameUtils;
+import org.simantics.db.common.utils.NearestOwnerFinder;
 import org.simantics.db.common.validation.L0Validations;
 import org.simantics.db.exception.AdaptionException;
 import org.simantics.db.exception.DatabaseException;
 import org.simantics.db.exception.DoesNotContainValueException;
 import org.simantics.db.exception.NoSingleResultException;
 import org.simantics.db.exception.RuntimeDatabaseException;
-import org.simantics.db.exception.VariableException;
 import org.simantics.db.layer0.exception.InvalidVariableException;
 import org.simantics.db.layer0.exception.MissingVariableException;
 import org.simantics.db.layer0.exception.MissingVariableValueException;
@@ -1504,7 +1504,7 @@ public class All {
         ClusteringSupport cs = graph.getService(ClusteringSupport.class);
         if(cs.isClusterSet(resource) && !base.equals(resource)) return resource;
         
-        Resource nearest = CommonDBUtils.getNearestOwner(graph, Collections.singletonList(resource));
+        Resource nearest = NearestOwnerFinder.getNearestOwner(graph, resource);
         if(nearest == null) return null;
         
         return getPossibleNearestClusterSet(graph, base, nearest);
index 4a40723ef70110071c47447f57d952110738c02d..b2b92039f87f4f35870c31ed0564c624a89cec75 100644 (file)
@@ -19,6 +19,7 @@ import org.simantics.db.common.request.ResourceRead;
 import org.simantics.db.common.request.TransientUnaryRead;
 import org.simantics.db.common.utils.CommonDBUtils;
 import org.simantics.db.common.utils.NameUtils;
+import org.simantics.db.common.utils.NearestOwnerFinder;
 import org.simantics.db.exception.DatabaseException;
 import org.simantics.db.exception.NoSingleResultException;
 import org.simantics.db.layer0.exception.MissingVariableException;
@@ -276,7 +277,7 @@ public class ConnectionBrowser {
                for (Resource composite : graph.getObjects(join, STR.JoinsComposite))
                        ancestorGenerators.add(composite);
             }
-            Resource ancestor = ancestorGenerators.size() == 1 ? ancestorGenerators.iterator().next() : CommonDBUtils.getNearestOwner(graph, ancestorGenerators);
+            Resource ancestor = ancestorGenerators.size() == 1 ? ancestorGenerators.iterator().next() : NearestOwnerFinder.getNearestOwnerFromDirectOwners(graph, ancestorGenerators);
             
             List<Resource> result = colls.createList();
             result.add(ancestor);