From 6d23985bc979c8b582bb7d856b432a6eba96df03 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Hannu=20Niemist=C3=B6?= Date: Wed, 24 Oct 2018 13:57:06 +0300 Subject: [PATCH] Prevent infinite recursion in getNearestOwner Change-Id: I58e0646daba1e41d9013085501bc1cee8fde1f13 --- .../db/common/utils/CommonDBUtils.java | 158 +++++++++++++----- 1 file changed, 112 insertions(+), 46 deletions(-) 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 2e16b2849..f63433e79 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 @@ -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 visited = new HashSet(); - 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 visited = new HashSet(); + 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 getDirectOwners(ReadGraph graph, Resource resource) throws DatabaseException { + // TODO is necessary? + if(resource.equals(graph.getRootLibrary())) + return Collections.emptyList(); + + Layer0 L0 = Layer0.getInstance(graph); + + Collection owners = graph.getObjects(resource, L0.IsOwnedBy); + if(owners.isEmpty()) { + 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; + } + 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(); - Set direct = new HashSet(); - Set owners = 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 objects = graph.getObjects(r, L0.IsOwnedBy); - // FIXME: + 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 (objects.size() > 1) objects = new HashSet(objects); + 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 (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 iter = direct.iterator(); + 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) 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); } -- 2.47.1