svn commit: r1028539 - in /avro/trunk: CHANGES.txt lang/java/src/java/org/apache/avro/Schema.java lang/java/src/test/java/org/apache/avro/TestSchema.java

[cu...@apache.org]

Author: cutting
Date: Thu Oct 28 23:21:18 2010
New Revision: 1028539

URL: http://svn.apache.org/viewvc?rev=1028539&view=rev
Log:
AVRO-685. Java: Fix Schema#equals() and hashCode() to not require exponential time for some recursive schemas.  Contributed by Richard Ahrens.

Modified:
    avro/trunk/CHANGES.txt
    avro/trunk/lang/java/src/java/org/apache/avro/Schema.java
    avro/trunk/lang/java/src/test/java/org/apache/avro/TestSchema.java

Modified: avro/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/avro/trunk/CHANGES.txt?rev=1028539&r1=1028538&r2=1028539&view=diff
==============================================================================
--- avro/trunk/CHANGES.txt (original)
+++ avro/trunk/CHANGES.txt Thu Oct 28 23:21:18 2010
@@ -30,6 +30,10 @@ Avro 1.5.0 (unreleased)
     AVRO-681. IDL: Fix documentation example with illegal syntax.
     (Jingguo Yao via cutting)
 
+    AVRO-685. Java: Fix Schema#equals() and hashCode() to not require
+    exponential time for some recursive schemas.
+    (Richard Ahrens via cutting)
+
 Avro 1.4.1 (13 October 2010)
 
   NEW FEATURES

Modified: avro/trunk/lang/java/src/java/org/apache/avro/Schema.java
URL: http://svn.apache.org/viewvc/avro/trunk/lang/java/src/java/org/apache/avro/Schema.java?rev=1028539&r1=1028538&r2=1028539&view=diff
==============================================================================
--- avro/trunk/lang/java/src/java/org/apache/avro/Schema.java (original)
+++ avro/trunk/lang/java/src/java/org/apache/avro/Schema.java Thu Oct 28 23:21:18 2010
@@ -587,21 +587,23 @@ public abstract class Schema {
       Set seen = SEEN_EQUALS.get();
       SeenPair here = new SeenPair(this, o);
       if (seen.contains(here)) return true;       // prevent stack overflow
+      boolean first = seen.isEmpty();
       try {
         seen.add(here);
         return fields.equals(((RecordSchema)o).fields);
       } finally {
-        seen.remove(here);
+        if (first) seen.clear();
       }
     }
     public int hashCode() {
       Map seen = SEEN_HASHCODE.get();
       if (seen.containsKey(this)) return 0;       // prevent stack overflow
+      boolean first = seen.isEmpty();
       try {
         seen.put(this, this);
         return super.hashCode() + fields.hashCode();
       } finally {
-        seen.remove(this);
+        if (first) seen.clear();
       }
     }
     void toJson(Names names, JsonGenerator gen) throws IOException {

Modified: avro/trunk/lang/java/src/test/java/org/apache/avro/TestSchema.java
URL: http://svn.apache.org/viewvc/avro/trunk/lang/java/src/test/java/org/apache/avro/TestSchema.java?rev=1028539&r1=1028538&r2=1028539&view=diff
==============================================================================
--- avro/trunk/lang/java/src/test/java/org/apache/avro/TestSchema.java (original)
+++ avro/trunk/lang/java/src/test/java/org/apache/avro/TestSchema.java Thu Oct 28 23:21:18 2010
@@ -35,6 +35,7 @@ import java.util.List;
 import java.util.Collection;
 
 import org.apache.avro.Schema.Type;
+import org.apache.avro.Schema.Field;
 import org.apache.avro.generic.GenericData;
 import org.apache.avro.generic.GenericDatumReader;
 import org.apache.avro.generic.GenericDatumWriter;
@@ -233,6 +234,33 @@ public class TestSchema {
   }
 
   @Test
+  /** Test that equals() and hashCode() don't require exponential time on
+   *  certain pathological schemas. */
+  public void testSchemaExplosion() throws Exception {
+    for (int i = 1; i < 15; i++) {                // 15 is big enough to trigger
+      // create a list of records, each with a single field whose type is a
+      // union of all of the records.
+      List<Schema> recs = new ArrayList<Schema>();
+      for (int j = 0; j < i; j++)
+        recs.add(Schema.createRecord(""+(char)('A'+j), null, null, false));
+      for (Schema s : recs) {
+        Schema union = Schema.createUnion(recs);
+        Field f = new Field("x", union, null, null);
+        List<Field> fields = new ArrayList<Field>();
+        fields.add(f);
+        s.setFields(fields);
+      }
+      // check that equals and hashcode are correct and complete in a
+      // reasonable amount of time
+      for (Schema s1 : recs) {
+        Schema s2 = Schema.parse(s1.toString());
+        assertEquals(s1.hashCode(), s2.hashCode()); 
+        assertEquals(s1, s2);
+      }
+    }                 
+  }
+
+  @Test
   public void testLisp() throws Exception {
     check("{\"type\": \"record\", \"name\": \"Lisp\", \"fields\": ["
           +"{\"name\":\"value\", \"type\":[\"null\", \"string\","