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

[cu...@apache.org]

Author: cutting
Date: Fri May 22 20:45:01 2009
New Revision: 777705

URL: http://svn.apache.org/viewvc?rev=777705&view=rev
Log:
AVRO-12.  Fix recursive schemas so that equals() and hashCode() do not cause stack overflow.

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

Modified: hadoop/avro/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/avro/trunk/CHANGES.txt?rev=777705&r1=777704&r2=777705&view=diff
==============================================================================
--- hadoop/avro/trunk/CHANGES.txt (original)
+++ hadoop/avro/trunk/CHANGES.txt Fri May 22 20:45:01 2009
@@ -60,3 +60,6 @@
     (sharad via cutting)
 
     AVRO-21. Default Java namespace from containing definition. (cutting)
+
+    AVRO-12. Fix recursive schemas in Java so that equals() and
+    hashCode() do not cause a stack overflow.  (cutting)

Modified: hadoop/avro/trunk/src/java/org/apache/avro/Schema.java
URL: http://svn.apache.org/viewvc/hadoop/avro/trunk/src/java/org/apache/avro/Schema.java?rev=777705&r1=777704&r2=777705&view=diff
==============================================================================
--- hadoop/avro/trunk/src/java/org/apache/avro/Schema.java (original)
+++ hadoop/avro/trunk/src/java/org/apache/avro/Schema.java Fri May 22 20:45:01 2009
@@ -25,9 +25,12 @@
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.LinkedHashMap;
+import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 import org.codehaus.jackson.JsonFactory;
 import org.codehaus.jackson.JsonParseException;
@@ -253,6 +256,25 @@
     }
   }
 
+  private static class SeenPair {
+    private Object s1; private Object s2;
+    private SeenPair(Object s1, Object s2) { this.s1 = s1; this.s2 = s2; }
+    public boolean equals(Object o) {
+      return this.s1 == ((SeenPair)o).s1 && this.s2 == ((SeenPair)o).s2;
+    }
+    public int hashCode() {
+      return System.identityHashCode(s1) + System.identityHashCode(s2);
+    }
+  }
+
+  private static final ThreadLocal<Set> SEEN_EQUALS = new ThreadLocal<Set>() {
+    protected Set initialValue() { return new HashSet(); }
+  };
+  private static final ThreadLocal<Map> SEEN_HASHCODE = new ThreadLocal<Map>() {
+    protected Map initialValue() { return new IdentityHashMap(); }
+  };
+
+  @SuppressWarnings(value="unchecked")
   private static class RecordSchema extends NamedSchema {
     private Map<String,Field> fields;
     private Iterable<Map.Entry<String,Schema>> fieldSchemas;
@@ -285,9 +307,28 @@
       if (o == this) return true;
       if (!(o instanceof RecordSchema)) return false;
       RecordSchema that = (RecordSchema)o;
-      return equalNames(that) && fields.equals(that.fields);
+      if (!equalNames(that)) return false;
+      if (!(o instanceof RecordSchema)) return false;
+      Set seen = SEEN_EQUALS.get();
+      SeenPair here = new SeenPair(this, o);
+      if (seen.contains(here)) return true;       // prevent stack overflow
+      try {
+        seen.add(here);
+        return fields.equals(((RecordSchema)o).fields);
+      } finally {
+        seen.remove(here);
+      }
+    }
+    public int hashCode() {
+      Map seen = SEEN_HASHCODE.get();
+      if (seen.containsKey(this)) return 0;       // prevent stack overflow
+      try {
+        seen.put(this, this);
+        return super.hashCode() + fields.hashCode();
+      } finally {
+        seen.remove(this);
+      }
     }
-    public int hashCode() { return super.hashCode() + fields.hashCode(); }
     public String toString(Names names) {
       if (this.equals(names.get(name))) return "\""+name+"\"";
       else if (name != null) names.put(name, this);

Modified: hadoop/avro/trunk/src/test/java/org/apache/avro/TestSchema.java
URL: http://svn.apache.org/viewvc/hadoop/avro/trunk/src/test/java/org/apache/avro/TestSchema.java?rev=777705&r1=777704&r2=777705&view=diff
==============================================================================
--- hadoop/avro/trunk/src/test/java/org/apache/avro/TestSchema.java (original)
+++ hadoop/avro/trunk/src/test/java/org/apache/avro/TestSchema.java Fri May 22 20:45:01 2009
@@ -129,6 +129,16 @@
   }
 
   @Test
+  public void testRecursiveEquals() throws Exception {
+    String jsonSchema = "{\"type\":\"record\", \"name\":\"List\", \"fields\": ["
+      +"{\"name\":\"next\", \"type\":\"List\"}]}";
+    Schema s1 = Schema.parse(jsonSchema);
+    Schema s2 = Schema.parse(jsonSchema);
+    assertEquals(s1, s2);
+    s1.hashCode();                                // test no stackoverflow
+  }
+
+  @Test
   public void testLisp() throws Exception {
     check("{\"type\": \"record\", \"name\": \"Lisp\", \"fields\": ["
           +"{\"name\":\"value\", \"type\":[\"null\", \"string\","