everit-org · tmarsteel · Jul 17, 2020 · Jul 17, 2020 · Jul 17, 2020 · Jul 24, 2020
diff --git a/core/src/main/java/org/everit/json/schema/ReferenceSchema.java b/core/src/main/java/org/everit/json/schema/ReferenceSchema.java
@@ -1,11 +1,13 @@
 package org.everit.json.schema;
 
-import static java.util.Objects.requireNonNull;
+import org.everit.json.schema.internal.EqualsCycleBreaker;
 
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Objects;
 
+import static java.util.Objects.requireNonNull;
+
 /**
  * This class is used by {@link org.everit.json.schema.loader.SchemaLoader} to resolve JSON pointers
  * during the construction of the schema. This class has been made mutable to permit the loading of
@@ -145,18 +147,22 @@ public boolean equals(Object o) {
             return that.canEqual(this) &&
                     Objects.equals(refValue, that.refValue) &&
                     Objects.equals(unprocessedProperties, that.unprocessedProperties) &&
-                    Objects.equals(referredSchema, that.referredSchema) &&
                     Objects.equals(title, that.title) &&
                     Objects.equals(description, that.description) &&
-                    super.equals(that);
+                    super.equals(that) &&
+                    EqualsCycleBreaker.equalsWithoutCycle(this, that, true, ReferenceSchema::equalsPossiblyCyclic);
         } else {
             return false;
         }
     }
 
+    private boolean equalsPossiblyCyclic(ReferenceSchema that) {
+        ret
8000
urn Objects.equals(referredSchema, that.referredSchema);
+    }
+
     @Override
     public int hashCode() {
-        return Objects.hash(super.hashCode(), referredSchema, refValue, unprocessedProperties, title, description);
+        return Objects.hash(super.hashCode(), refValue, unprocessedProperties, title, description);
     }
 
     @Override

diff --git a/core/src/main/java/org/everit/json/schema/internal/EqualsCycleBreaker.java b/core/src/main/java/org/everit/json/schema/internal/EqualsCycleBreaker.java
@@ -0,0 +1,124 @@
+package org.everit.json.schema.internal;
+
+import java.util.HashSet;
+import java.util.Set;
+import java.util.WeakHashMap;
+import java.util.function.BiFunction;
+
+public final class EqualsCycleBreaker
+{
+    private EqualsCycleBreaker()
+    {
+        throw new UnsupportedOperationException();
+    }
+
+    /**
+     * ThreadLocal because this class doesn't bother with stack overflows across multiple threads, if that
+     * is even possible.
+     * <br>
+     * A <i>weak</i> map so that this consumes less memory.
+     * <br>
+     * For each ongoing equality check via {@link #equalsWithoutCycle(Object, Object, boolean, BiFunction)},
+     * maps the <code>this</code> pointer of the <code>equals</code> invocation to all of the objects it is
+     * being compared against. Each mapping is removed when `equals` returns.
+     * <br>
+     * This way, when {@link Object#equals(Object)} is called with the same parameters (this and the other reference)
+     * a second time before the first invocation has returned (= cyclic!), it can be detected and handled.
+     */
+    private static final ThreadLocal<WeakHashMap<Identity, Set>> >
+
+    /**
+     * Use to break cycles in equality checks. For example:
+     *
+     * <pre>
+     *     class A {
+     *         B b;
+     *
+     *         public boolean equals(Object o) {
+     *             if (!(o instanceof A)) {
+     *                 return false;
+     *             }
+     *
+     *             return this.b.equals(((A) o).b);
+     *         }
+     *     }
+     *     class B {
+     *         int i;
+     *         A a;
+     *
+     *         public boolean equals(Object o) {
+     *             if (!(o instanceof B)) {
+     *                 return false;
+     *             }
+     *
+     *             B that = (B) o;
+     *             if (i != that.i) {
+     *                 return false;
+     *             }
+     *
+     *             return EqualsCycleBreaker.equalsWithoutCycle(this, that, true, B::equalsPossiblyCyclic);
+     *         }
+     *
+     *         private boolean equalsPossiblyCyclic(B that) {
+     *             return this.a.equals(that.a);
+     *         }
+     *     }
+     * </pre>
+     *
+     * If you now construct a cyclic object tree and call equals on it, it will not explode with a stack overflow:
+     * <pre>
+     *     A a = new A();
+     *     B b = new B();
+     *     b.i = 10;
+     *     b.a = a;
+     *     a.b = b;
+     *
+     *     b.equals(b); // returns true
+     * </pre>
+     *
+     * @param self The receiver of an invocation to {@link Object#equals(Object)}. E.g. in <code>a.equals(b)</code>, this
+     *             parameter is <code>a</code>.
+     * @param other The parameter of an invocation to {@link Object#equals(Object)}. E.g. in <code>a.equals(b)</code>, this
+     *              parameter is <code>b</code>.
+     * @param equalsOnCycle What this method should return when it detects a cycle
+     * @param equalityFunction The part of the equality check that can cause cyclic invocations / stack overflows.
+     * @return If this method is called in a cycle, returns <code>equalsOnCycle</code>. Otherwise defers to <code>equalityFunction</code>.
+     */
+    public static <T> boolean equalsWithoutCycle(T self, T other, boolean equalsOnCycle, BiFunction<T, T, Boolean> equalityFunction) {
+        Set<T> localOngoingEqualityChecks = ongoingEqualityChecks.get()
+            .computeIfAbsent(new Identity<>(self), (_k) -> new HashSet<>());
+        if (localOngoingEqualityChecks.add(other)) {
+            try {
+                return equalityFunction.apply(self, other);
+            }
+            finally {
+                localOngoingEqualityChecks.remove(other);
+                if (localOngoingEqualityChecks.isEmpty()) {
+                    ongoingEqualityChecks.remove();
+                }
+            }
+        } else {
+            return equalsOnCycle;
+        }
+    }
+
+    private static class Identity<E> {
+        private final E e;
+
+        public Identity(E e)
+        {
+            this.e = e;
+        }
+
+        public int hashCode() {
+            return System.identityHashCode(e);
+        }
+
+        public boolean equals(Object o) {
+            if (!(o instanceof Identity)) {
+                return false;
+            }
+            return ((Identity<?>) o).e == e;
+        }
+    }
+}
diff --git a/core/src/test/java/org/everit/json/schema/HashCodeRecursionTest.java b/core/src/test/java/org/everit/json/schema/HashCodeRecursionTest.java
@@ -0,0 +1,43 @@
+package org.everit.json.schema;
+
+import org.everit.json.schema.loader.SchemaLoader;
+import org.json.JSONObject;
+import org.json.JSONTokener;
+import org.junit.Test;
+
+import java.io.IOException;
+import java.io.InputStream;
+
+import static org.junit.Assert.assertEquals;
+
+public class HashCodeRecursionTest
+{
+    @Test
+    public void hashCodeShouldNotProduceStackoverflowOnCyclicSchema() throws IOException
+    {
+        loadSelfCyclic().hashCode();
+    }
+
+    @Test
+    public void equalsShouldNotProduceStackoverflowOnCyclicSchema() throws IOException
+    {
+        CombinedSchema cyclic = (CombinedSchema) loadSelfCyclic();
+        CombinedSchema cyclicCopy = (CombinedSchema) loadSelfCyclic();
+
+        assertEquals(cyclic, cyclicCopy);
+    }
+
+    private Schema loadSelfCyclic() throws IOException
+    {
+        JSONObject schemaJson;
+        try (InputStream inStream = getClass().getResourceAsStream("/org/everit/jsonvalidator/cyclic.json")) {
+            schemaJson = new JSONObject(new JSONTokener(inStream));
+        }
+
+        return new SchemaLoader.SchemaLoaderBuilder()
+            .schemaJson(schemaJson)
+            .build()
+            .load()
+            .build();
+    }
+}
diff --git a/core/src/test/java/org/everit/json/schema/ReferenceSchemaTest.java b/core/src/test/java/org/everit/json/schema/ReferenceSchemaTest.java
@@ -15,21 +15,19 @@
  */
 package org.everit.json.schema;
 
-import static java.util.Collections.emptyMap;
-import static org.everit.json.schema.TestSupport.buildWithLocation;
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-
+import com.google.common.collect.ImmutableMap;
+import nl.jqno.equalsverifier.EqualsVerifier;
+import nl.jqno.equalsverifier.Warning;
 import org.everit.json.schema.ReferenceSchema.Builder;
 import org.everit.json.schema.loader.SchemaLoader;
 import org.json.JSONObject;
 import org.junit.Assert;
 import org.junit.Test;
 
-import com.google.common.collect.ImmutableMap;
-
-import nl.jqno.equalsverifier.EqualsVerifier;
-import nl.jqno.equalsverifier.Warning;
+import static java.util.Collections.emptyMap;
+import static org.everit.json.schema.TestSupport.buildWithLocation;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
 
 public class ReferenceSchemaTest {
 
@@ -80,6 +78,7 @@ public void equalsVerifier() {
                 //there are specifically some non final fields for loading of recursive schemas
                 .suppress(Warning.NONFINAL_FIELDS)
                 .suppress(Warning.STRICT_INHERITANCE)
+                .suppress(Warning.STRICT_HASHCODE)
                 .verify();
     }
 

diff --git a/core/src/test/resources/org/everit/jsonvalidator/cyclic.json b/core/src/test/resources/org/everit/jsonvalidator/cyclic.json
@@ -0,0 +1,27 @@
+{
+    "$schema": "http://json-schema.org/draft-06/schema#",
+    "title": "Foo Schema",
+    "allOf": [
+        {
+            "$ref": "#/definitions/Foo"
+        }
+    ],
+    "definitions": {
+        "Bar": {
+            "type": "object",
+            "properties": {
+                "foo": {
+                    "$ref": "#/definitions/Foo"
+                }
+            }
+        },
+        "Foo": {
+            "type": "object",
+            "properties": {
+                "bar": {
+                    "$ref": "#/definitions/Bar"
+                }
+            }
+        }
+    }
+}