robot: Combination of remove and filter causes stack overflow

Thanks @ignazio1977! Sorry for the delay in response, we’ve been getting ready for a conference. This patch works great at resolving the stack overflow. I’m not sure why I didn’t use sets in the first place… silly oversight. It looks like all our tests still pass as well.

Hi, @matentzn pointed me at this issue to see if I had any clues as to what’s going wrong.

I’ve played around with the code where the stack overflow issue happens, and I believe there’s an issue in RelatedObjectsHelper - the gap spanning axioms are created from lists of relations, but when recurring to create the elements for these lists there is no test to check if the relation being added is already in the list. If it is, it means that particular path has already been explored and it’s not necessary to continue the recursion.

I am guessing as to what the intent in the code is - haven’t looked into it enough to be sure I’m not missing something important. However, if I’m right, the fix is straightforward and computationally inexpensive: simply stop the recursion once the relation being examined is already in the list of known relations. Replacing the list with a set slightly increases the memory requirements, but it also removes the creation of duplicate axioms that would happen even in a DAG scenario, and it allows the code to deal with cycles as the ones found here (@matentzn example finishes running in a few seconds on my very dated laptop, with default memory allocation).

The patch implementing my fix is as follows:

diff --git a/robot-core/src/main/java/org/obolibrary/robot/RelatedObjectsHelper.java b/robot-core/src/main/java/org/obolibrary/robot/RelatedObjectsHelper.java
index bc9a40a..ec4a80d 100644
--- a/robot-core/src/main/java/org/obolibrary/robot/RelatedObjectsHelper.java
+++ b/robot-core/src/main/java/org/obolibrary/robot/RelatedObjectsHelper.java
@@ -770,10 +770,10 @@
    * @return set of OWLAxioms to maintain hierarchy
    */
   public static Set<OWLAxiom> spanGaps(OWLOntology ontology, Set<OWLObject> objects) {
-    List<Map<String, OWLAnnotationProperty>> aPropPairs = new ArrayList<>();
-    List<Map<String, OWLClassExpression>> classPairs = new ArrayList<>();
-    List<Map<String, OWLDataPropertyExpression>> dPropPairs = new ArrayList<>();
-    List<Map<String, OWLObjectPropertyExpression>> oPropPairs = new ArrayList<>();
+    Set<Map<String, OWLAnnotationProperty>> aPropPairs = new HashSet<>();
+    Set<Map<String, OWLClassExpression>> classPairs = new HashSet<>();
+    Set<Map<String, OWLDataPropertyExpression>> dPropPairs = new HashSet<>();
+    Set<Map<String, OWLObjectPropertyExpression>> oPropPairs = new HashSet<>();
     Set<OWLAxiom> axioms = new HashSet<>();
     OWLDataFactory dataFactory = OWLManager.getOWLDataFactory();
 
@@ -1342,7 +1342,7 @@
   private static void spanGapsHelper(
       OWLOntology ontology,
       Set<OWLObject> objects,
-      List<Map<String, OWLAnnotationProperty>> propPairs,
+      Set<Map<String, OWLAnnotationProperty>> propPairs,
       OWLAnnotationProperty property,
       Collection<OWLAnnotationProperty> superProperties) {
     for (OWLAnnotationProperty sp : superProperties) {
@@ -1351,14 +1351,15 @@
           Map<String, OWLAnnotationProperty> propertyPair = new HashMap<>();
           propertyPair.put(SUB, property);
           propertyPair.put(SUPER, sp);
-          propPairs.add(propertyPair);
-          property = sp;
-          spanGapsHelper(
-              ontology,
-              objects,
-              propPairs,
-              property,
-              EntitySearcher.getSuperProperties(property, ontology));
+          if (propPairs.add(propertyPair)) {
+            property = sp;
+            spanGapsHelper(
+                ontology,
+                objects,
+                propPairs,
+                property,
+                EntitySearcher.getSuperProperties(property, ontology));
+          }
         }
       } else if (!sp.isAnonymous()) {
         spanGapsHelper(
@@ -1385,22 +1386,22 @@
   private static void spanGapsHelper(
       OWLOntology ontology,
       Set<OWLObject> objects,
-      List<Map<String, OWLClassExpression>> classPairs,
-      OWLClass cls,
+      Set<Map<String, OWLClassExpression>> classPairs, OWLClass cls,
       Collection<OWLClassExpression> superClasses) {
     for (OWLClassExpression sc : superClasses) {
       if (objects.containsAll(sc.getSignature())) {
         Map<String, OWLClassExpression> classPair = new HashMap<>();
         classPair.put(SUB, cls);
         classPair.put(SUPER, sc);
-        classPairs.add(classPair);
-        if (!sc.isAnonymous()) {
-          spanGapsHelper(
-              ontology,
-              objects,
-              classPairs,
-              sc.asOWLClass(),
+        if (classPairs.add(classPair)) {
+          // only recurse if the pair just added was not already present in the set.
+          if (!sc.isAnonymous()) {
+            spanGapsHelper(ontology,
+                objects,
+                classPairs,
+                sc.asOWLClass(),
               getSuperClasses(ontology, sc.asOWLClass()));
+          }
         }
       } else if (!sc.isAnonymous()) {
         spanGapsHelper(
@@ -1423,7 +1424,7 @@
   private static void spanGapsHelper(
       OWLOntology ontology,
       Set<OWLObject> objects,
-      List<Map<String, OWLDataPropertyExpression>> propPairs,
+      Set<Map<String, OWLDataPropertyExpression>> propPairs,
       OWLDataProperty property,
       Collection<OWLDataPropertyExpression> superProperties) {
     for (OWLDataPropertyExpression sp : superProperties) {
@@ -1431,15 +1432,16 @@
         Map<String, OWLDataPropertyExpression> propertyPair = new HashMap<>();
         propertyPair.put(SUB, property);
         propertyPair.put(SUPER, sp);
-        propPairs.add(propertyPair);
-        if (!sp.isAnonymous()) {
-          property = (OWLDataProperty) sp;
-          spanGapsHelper(
-              ontology,
-              objects,
-              propPairs,
-              property,
-              EntitySearcher.getSuperProperties(property, ontology));
+        if (propPairs.add(propertyPair)) {
+          if (!sp.isAnonymous()) {
+            property = (OWLDataProperty) sp;
+            spanGapsHelper(
+                ontology,
+                objects,
+                propPairs,
+                property,
+                EntitySearcher.getSuperProperties(property, ontology));
+          }
         }
       } else if (!sp.isAnonymous()) {
         spanGapsHelper(
@@ -1466,7 +1468,7 @@
   private static void spanGapsHelper(
       OWLOntology ontology,
       Set<OWLObject> objects,
-      List<Map<String, OWLObjectPropertyExpression>> propPairs,
+      Set<Map<String, OWLObjectPropertyExpression>> propPairs,
       OWLObjectProperty property,
       Collection<OWLObjectPropertyExpression> superProperties) {
     for (OWLObjectPropertyExpression sp : superProperties) {
@@ -1474,15 +1476,16 @@
         Map<String, OWLObjectPropertyExpression> propertyPair = new HashMap<>();
         propertyPair.put(SUB, property);
         propertyPair.put(SUPER, sp);
-        propPairs.add(propertyPair);
-        if (!sp.isAnonymous()) {
-          property = (OWLObjectProperty) sp;
-          spanGapsHelper(
-              ontology,
-              objects,
-              propPairs,
-              property,
-              EntitySearcher.getSuperProperties(property, ontology));
+        if (propPairs.add(propertyPair)) {
+          if (!sp.isAnonymous()) {
+            property = (OWLObjectProperty) sp;
+            spanGapsHelper(
+                ontology,
+                objects,
+                propPairs,
+                property,
+                EntitySearcher.getSuperProperties(property, ontology));
+          }
         }
       } else if (!sp.isAnonymous()) {
         spanGapsHelper(

I agree with Jim

On Mon, Jul 22, 2019, 04:40 Jim Balhoff notifications@github.com wrote:

Does this mean, that maybe, relax should not relax equivalences between named classes

This makes sense to me. I don’t see the value in it for the graph traversal use case. Of course when a named class is part of an expression (A and r some B), A would still get relaxed.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ontodev/robot/issues/527?email_source=notifications&email_token=AAAMMOKPPHXVR336OES4XQLQAUMZNA5CNFSM4H6T45X2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2OTJJI#issuecomment-513619109, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAMMOMTJ4EC342RSFBAC53QAUMZNANCNFSM4H6T45XQ .

Does this mean, that maybe, relax should not relax equivalences between named classes

This makes sense to me. I don’t see the value in it for the graph traversal use case. Of course when a named class is part of an expression (A and r some B), A would still get relaxed.