From 68a9ec79344f44499f9a92c95ee81b8b052a22e7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Hannu=20Niemist=C3=B6?= Date: Fri, 26 Oct 2018 16:19:20 +0300 Subject: [PATCH] New implementation NearestOwnerFinder of CommonDBUtils.getNearestOwner 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 --- .../db/common/request/PossibleOwner.java | 10 +- .../db/common/utils/CommonDBUtils.java | 100 +-------- .../db/common/utils/NearestOwnerFinder.java | 207 ++++++++++++++++++ .../org/simantics/db/layer0/function/All.java | 4 +- .../variables/ConnectionBrowser.java | 3 +- 5 files changed, 224 insertions(+), 100 deletions(-) create mode 100644 bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/request/PossibleOwner.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/request/PossibleOwner.java index a39b257d2..6df691026 100644 --- a/bundles/org.simantics.db.common/src/org/simantics/db/common/request/PossibleOwner.java +++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/request/PossibleOwner.java @@ -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 { @@ -16,10 +13,7 @@ public class PossibleOwner extends ResourceRead { @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 diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/CommonDBUtils.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/CommonDBUtils.java index 80924148e..a07d42519 100644 --- a/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/CommonDBUtils.java +++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/CommonDBUtils.java @@ -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 resources) throws DatabaseException { - return getNearestOwner(graph, resources, null); - } - - private static Resource getNearestOwner(ReadGraph graph, Collection resources, THashSet infiniteRecursionBreaker) throws DatabaseException { - - Layer0 L0 = Layer0.getInstance(graph); - - // These are resources that are linked to some of the input resources by IsComposedOf - Set directOwners = new HashSet(); - - // These are resources that refer to some of the input resources which don't have an owner - Set referringResources = new HashSet(); - - for(Resource r : resources) { - - Collection owners = graph.getObjects(r, L0.IsOwnedBy); - - // TODO: getObjects returns duplicate entries (https://www.simantics.org/redmine/issues/4885) and therefore direct is Set. Fix getObjects to not return duplicate entries - if (owners.size() > 1) { - owners = new HashSet(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 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()); @@ -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()); } 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 index 000000000..062d1c88a --- /dev/null +++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java @@ -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; + +/** + *

A utility to finds the nearest owner of a real or imaginary resource.

+ * + *

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.

+ * + *

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.

+ * + * @see {@link #getNearestOwner(ReadGraph, Resource)} + * @see {@link #getNearestOwner(ReadGraph, Collection)}

+ * + */ +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 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 owners) throws DatabaseException { + Iterator 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 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 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 getDirectOwners(ReadGraph graph, Layer0 L0, Resource resource) throws DatabaseException { + Collection owners = graph.getObjects(resource, L0.IsOwnedBy); + if(owners.isEmpty()) { + if(resource.equals(graph.getRootLibrary())) + return Collections.emptyList(); + + owners = new THashSet(); + + // 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. + // Fix getObjects to not return duplicate entries + owners = new HashSet(owners); + } + + return owners; + } + + /** + *

Finds the nearest owner of a resource. Nearest owner is the + * immediate dominator + * 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.

+ * + *

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.

+ * + * @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 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; + } + + /** + *

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.

+ * + *

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.

+ */ + public static Resource getNearestOwnerFromDirectOwners(ReadGraph graph, Collection 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; + } +} diff --git a/bundles/org.simantics.db.layer0/src/org/simantics/db/layer0/function/All.java b/bundles/org.simantics.db.layer0/src/org/simantics/db/layer0/function/All.java index 991a0500c..f93023b77 100644 --- a/bundles/org.simantics.db.layer0/src/org/simantics/db/layer0/function/All.java +++ b/bundles/org.simantics.db.layer0/src/org/simantics/db/layer0/function/All.java @@ -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); diff --git a/bundles/org.simantics.structural2/src/org/simantics/structural2/variables/ConnectionBrowser.java b/bundles/org.simantics.structural2/src/org/simantics/structural2/variables/ConnectionBrowser.java index 4a40723ef..b2b92039f 100644 --- a/bundles/org.simantics.structural2/src/org/simantics/structural2/variables/ConnectionBrowser.java +++ b/bundles/org.simantics.structural2/src/org/simantics/structural2/variables/ConnectionBrowser.java @@ -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 result = colls.createList(); result.add(ancestor); -- 2.47.1