Prevent infinite recursion in getNearestOwner 49/2349/1
authorHannu Niemistö <hannu.niemisto@semantum.fi>
Wed, 24 Oct 2018 10:57:06 +0000 (13:57 +0300)
committerHannu Niemistö <hannu.niemisto@semantum.fi>
Wed, 24 Oct 2018 10:57:06 +0000 (13:57 +0300)
Change-Id: I58e0646daba1e41d9013085501bc1cee8fde1f13

bundles/org.simantics.db.common/src/org/simantics/db/common/utils/CommonDBUtils.java

index 77eacf2055e9002c86aa99da5fed5c96a3f15906..80924148e85e88fad749b5f360bc43ec804d5ab4 100644 (file)
@@ -32,6 +32,7 @@ import org.slf4j.LoggerFactory;
 
 import gnu.trove.list.array.TIntArrayList;
 import gnu.trove.procedure.TIntProcedure;
+import gnu.trove.set.hash.THashSet;
 import gnu.trove.set.hash.TIntHashSet;
 
 public class CommonDBUtils {
@@ -58,88 +59,153 @@ public class CommonDBUtils {
         return graph.syncRequest(new PossibleOwner(resource));
     }
     
+    /**
+     * Finds a resource that is reachable from both input resources by as short as possible IsOwnedBy chain
+     */
     public static Resource commonAncestor(ReadGraph graph, Resource r1, Resource r2) throws DatabaseException {
+        if(r1.equals(r2))
+            return r1;
+        
         Layer0 L0 = Layer0.getInstance(graph);
-       if(r1.equals(r2)) return r1;
-       HashSet<Resource> visited = new HashSet<Resource>();
-       visited.add(r1);
-       visited.add(r2);
-       while(true) {
-               if(r1 != null) {
-                       r1 = graph.getPossibleObject(r1, L0.IsOwnedBy);
-                       if(r1 != null)
-                               if(!visited.add(r1)) return r1;
-               }
-               else if(r2 == null) return null;
-               if(r2 != null) {
-                       r2 = graph.getPossibleObject(r2, L0.IsOwnedBy);
-                       if(r2 != null)
-                               if(!visited.add(r2)) return r2;
-               }
-       }
+        HashSet<Resource> visited = new HashSet<Resource>();
+        visited.add(r1);
+        visited.add(r2);
+        while(true) {
+            if(r1 != null) {
+                r1 = graph.getPossibleObject(r1, L0.IsOwnedBy);
+                if(r1 != null && !visited.add(r1))
+                    return r1;
+            }
+            else if(r2 == null)
+                return null;
+            if(r2 != null) {
+                r2 = graph.getPossibleObject(r2, L0.IsOwnedBy);
+                if(r2 != null && !visited.add(r2))
+                    return r2;
+            }
+        }
     }
-       
+    
+    private static Collection<Resource> getDirectOwners(ReadGraph graph, Resource resource) throws DatabaseException {
+        // TODO is necessary?
+        if(resource.equals(graph.getRootLibrary()))
+            return Collections.emptyList();
+        
+        Layer0 L0 = Layer0.getInstance(graph);
+        
+        Collection<Resource> owners = graph.getObjects(resource, L0.IsOwnedBy);
+        if(owners.isEmpty()) {
+            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;
+    }
+    
     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>();
         
-        Set<Resource> direct = new HashSet<Resource>();
-        Set<Resource> owners = 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> objects = graph.getObjects(r, L0.IsOwnedBy);
-            // FIXME: 
+            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 (objects.size() > 1) objects = new HashSet<Resource>(objects);
+            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 (objects.size() == 1)
-                direct.addAll(objects);
-            else if (objects.isEmpty()) {
+            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()))
-                                owners.add(stm.getObject());
+                            if(r.equals(stm.getObject()))
+                                continue;
+                            referringResources.add(stm.getObject());
                         }
                     }
                 }
-            } else {
-                System.err.println("Multiple owners for " + graph.getPossibleURI(r) + " id : " + r);
-                for (Resource r2 : objects)
-                    System.err.println("owner : " + graph.getPossibleURI(r2) + " id " + r2);
-                return null;
             }
+            else
+                directOwners.addAll(owners);
         }
         
-        if(!direct.isEmpty()) {
-            Iterator<Resource> iter = direct.iterator();
+        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) break;
+                if (common == null)
+                    return null; // The
             }
-               if(common != null)
-                       owners.add(common);
+            referringResources.add(common);
         }
+        if(referringResources.isEmpty())
+            return null;
         
-        if(!Collections.disjoint(owners, resources)) {
-            System.err.println("Overlapping owners:");
+        if(!Collections.disjoint(referringResources, resources)) {
+            LOGGER.error("Overlapping owners:");
             for(Resource r : resources)
-                System.err.println("-resource " + NameUtils.getSafeName(graph, r, true));
-            for(Resource r : owners)
-                System.err.println("-owner " + NameUtils.getSafeName(graph, r, true));
+                LOGGER.error("    resource {}", NameUtils.getSafeName(graph, r, true));
+            for(Resource r : referringResources)
+                LOGGER.error("    owner {}", NameUtils.getSafeName(graph, r, true));
             return null;
         }
         
-        if(owners.size() == 1) return owners.iterator().next();
-        if(owners.size() == 0) 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, owners);
+        return getNearestOwner(graph, referringResources, infiniteRecursionBreaker);
         
     }