Adding support for getUserData() and setUserData() to DOM nodes.

Also making sure both Document and DocumentType get assigned
a Document value when possible; this is necessary to store the
user data objects.
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DOMImplementationImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DOMImplementationImpl.java
index 991a707..b662a13 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DOMImplementationImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DOMImplementationImpl.java
@@ -46,7 +46,7 @@
 
     public DocumentType createDocumentType(String qualifiedName,
             String publicId, String systemId) throws DOMException {
-        return new DocumentTypeImpl(this, qualifiedName, publicId, systemId);
+        return new DocumentTypeImpl(null, qualifiedName, publicId, systemId);
     }
 
     public boolean hasFeature(String feature, String version) {
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentImpl.java
index b009128..b1802a6 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentImpl.java
@@ -33,6 +33,12 @@
 import org.w3c.dom.NodeList;
 import org.w3c.dom.ProcessingInstruction;
 import org.w3c.dom.Text;
+import org.w3c.dom.UserDataHandler;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.WeakHashMap;
 
 /**
  * Provides a straightforward implementation of the corresponding W3C DOM
@@ -60,14 +66,26 @@
     private boolean xmlStandalone = false;
     private boolean strictErrorChecking = true;
 
+    /**
+     * A lazily initialized map of user data values for this document's own
+     * nodes. The map is weak because the document may live longer than its
+     * nodes.
+     *
+     * <p>Attaching user data directly to the corresponding node would cost a
+     * field per node. Under the assumption that user data is rarely needed, we
+     * attach user data to the document to save those fields. Xerces also takes
+     * this approach.
+     */
+    private WeakHashMap<Node, Map<String, UserData>> nodeToUserData;
+
     public DocumentImpl(DOMImplementationImpl impl, String namespaceURI,
             String qualifiedName, DocumentType doctype, String inputEncoding) {
         super(null);
 
         this.domImplementation = impl;
         this.inputEncoding = inputEncoding;
-        // this.document = this;
-        
+        this.document = this;
+
         if (doctype != null) {
             appendChild(doctype);
         }
@@ -113,8 +131,6 @@
      * @return The new node.
      */
     Node cloneNode(Node node, boolean deep) throws DOMException {
-        // TODO: callback the UserDataHandler with a NODE_CLONED event
-
         Node target;
         
         switch (node.getNodeType()) {
@@ -191,10 +207,12 @@
                 target.appendChild(child);
             }
         }
-        
+
+        notifyUserDataHandlers(UserDataHandler.NODE_CLONED, node, target);
+
         return target;
     }
-    
+
     public AttrImpl createAttribute(String name) throws DOMException {
         return new AttrImpl(this, name);
     }
@@ -382,4 +400,48 @@
         // TODO: callback the UserDataHandler with a NODE_RENAMED event
         throw new UnsupportedOperationException(); // TODO
     }
+
+    /**
+     * Returns a map with the user data objects attached to the specified node.
+     * This map is readable and writable.
+     */
+    Map<String, UserData> getUserDataMap(Node node) {
+        if (nodeToUserData == null) {
+            nodeToUserData = new WeakHashMap<Node, Map<String, UserData>>();
+        }
+        Map<String, UserData> userDataMap = nodeToUserData.get(node);
+        if (userDataMap == null) {
+            userDataMap = new HashMap<String, UserData>();
+            nodeToUserData.put(node, userDataMap);
+        }
+        return userDataMap;
+    }
+
+    /**
+     * Returns a map with the user data objects attached to the specified node.
+     * The returned map may be read-only.
+     */
+    Map<String, UserData> getUserDataMapForRead(Node node) {
+        if (nodeToUserData == null) {
+            return Collections.emptyMap();
+        }
+        Map<String, UserData> userDataMap = nodeToUserData.get(node);
+        return userDataMap == null
+                ? Collections.<String, UserData>emptyMap()
+                : userDataMap;
+    }
+
+    /**
+     * Calls {@link UserDataHandler#handle} on each of the source node's
+     * value/handler pairs.
+     */
+    private void notifyUserDataHandlers(short operation, Node src, Node dst) {
+        for (Map.Entry<String, UserData> entry : getUserDataMapForRead(src).entrySet()) {
+            UserData userData = entry.getValue();
+            if (userData.handler != null) {
+                userData.handler.handle(
+                        operation, entry.getKey(), userData.value, src, dst);
+            }
+        }
+    }
 }
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentTypeImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentTypeImpl.java
index 67947b7..b0e8eda 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentTypeImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/DocumentTypeImpl.java
@@ -31,7 +31,7 @@
  * the DOM implementation can easily access them while maintaining the DOM tree
  * structure.
  */
-public class DocumentTypeImpl extends LeafNodeImpl implements DocumentType {
+public final class DocumentTypeImpl extends LeafNodeImpl implements DocumentType {
 
     private String qualifiedName;
 
@@ -39,9 +39,9 @@
 
     private String systemId;
 
-    DocumentTypeImpl(DOMImplementationImpl impl, String qualifiedName,
+    public DocumentTypeImpl(DocumentImpl document, String qualifiedName,
             String publicId, String systemId) {
-        super(null);
+        super(document);
 
         if (qualifiedName == null || "".equals(qualifiedName)) {
             throw new DOMException(DOMException.NAMESPACE_ERR, qualifiedName);
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/ElementImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/ElementImpl.java
index df1383d..e272a3e 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/ElementImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/ElementImpl.java
@@ -315,7 +315,7 @@
     public Attr setAttributeNode(Attr newAttr) throws DOMException {
         AttrImpl newAttrImpl = (AttrImpl) newAttr;
         
-        if (newAttrImpl.document != this.getOwnerDocument()) {
+        if (newAttrImpl.document != this.document) {
             throw new DOMException(DOMException.WRONG_DOCUMENT_ERR, null);
         }
 
@@ -340,7 +340,7 @@
     public Attr setAttributeNodeNS(Attr newAttr) throws DOMException {
         AttrImpl newAttrImpl = (AttrImpl) newAttr;
 
-        if (newAttrImpl.document != this.getOwnerDocument()) {
+        if (newAttrImpl.document != this.document) {
             throw new DOMException(DOMException.WRONG_DOCUMENT_ERR, null);
         }
 
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/InnerNodeImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/InnerNodeImpl.java
index fa75e21..bd4affb 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/InnerNodeImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/InnerNodeImpl.java
@@ -43,7 +43,7 @@
     // Maintained by LeafNodeImpl and ElementImpl.
     List<LeafNodeImpl> children = new ArrayList<LeafNodeImpl>();
 
-    public InnerNodeImpl(DocumentImpl document) {
+    protected InnerNodeImpl(DocumentImpl document) {
         super(document);
     }
 
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NamedNodeMapImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NamedNodeMapImpl.java
index 0952d83..6eb8efa 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NamedNodeMapImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NamedNodeMapImpl.java
@@ -121,7 +121,7 @@
         
         // All nodes in the map must belong to the same document.
         if (list.size() != 0) {
-            Document document = list.get(0).getOwnerDocument();
+            Document document = list.get(0).document;
 
             if (document != null && arg.getOwnerDocument() != document) {
                 throw new DOMException(DOMException.HIERARCHY_REQUEST_ERR, null);
@@ -151,7 +151,7 @@
         
         // All nodes in the map must belong to the same document.
         if (list.size() != 0) {
-            Document document = list.get(0).getOwnerDocument();
+            Document document = list.get(0).document;
 
             if (document != null && arg.getOwnerDocument() != document) {
                 throw new DOMException(DOMException.HIERARCHY_REQUEST_ERR, null);
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NodeImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NodeImpl.java
index 24ed102..8376689 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NodeImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/NodeImpl.java
@@ -29,6 +29,7 @@
 
 import java.util.ArrayList;
 import java.util.List;
+import java.util.Map;
 
 /**
  * A straightforward implementation of the corresponding W3C DOM node.
@@ -45,7 +46,6 @@
 
     private static final NodeList EMPTY_LIST = new NodeListImpl();
     
-    // Maintained by InnerNodeImpl and ElementImpl.
     DocumentImpl document;
 
     NodeImpl(DocumentImpl document) {
@@ -98,8 +98,8 @@
         return null;
     }
 
-    public Document getOwnerDocument() {
-        return document;
+    public final Document getOwnerDocument() {
+        return document == this ? null : document;
     }
 
     public Node getParentNode() {
@@ -308,7 +308,7 @@
                 }
                 // create a text node to hold the given content
                 if (textContent != null && textContent.length() != 0) {
-                    appendChild(getOwnerDocument().createTextNode(textContent));
+                    appendChild(document.createTextNode(textContent));
                 }
                 return;
 
@@ -585,12 +585,32 @@
         return isSupported(feature, version) ? this : null;
     }
 
-    public Object setUserData(String key, Object data,
-            UserDataHandler handler) {
-        throw new UnsupportedOperationException(); // TODO
+    public final Object setUserData(String key, Object data, UserDataHandler handler) {
+        if (key == null) {
+            throw new NullPointerException();
+        }
+        Map<String, UserData> map = document.getUserDataMap(this);
+        UserData previous = data == null
+                ? map.remove(key)
+                : map.put(key, new UserData(data, handler));
+        return previous != null ? previous.value : null;
     }
 
-    public Object getUserData(String key) {
-        throw new UnsupportedOperationException(); // TODO
+    public final Object getUserData(String key) {
+        if (key == null) {
+            throw new NullPointerException();
+        }
+        Map<String, UserData> map = document.getUserDataMapForRead(this);
+        UserData userData = map.get(key);
+        return userData != null ? userData.value : null;
+    }
+
+    static class UserData {
+        final Object value;
+        final UserDataHandler handler;
+        UserData(Object value, UserDataHandler handler) {
+            this.value = value;
+            this.handler = handler;
+        }
     }
 }
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/TextImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/TextImpl.java
index d39dff2..7b61b02 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/dom/TextImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/dom/TextImpl.java
@@ -47,7 +47,7 @@
     }
 
     public final Text splitText(int offset) throws DOMException {
-        Text newText = getOwnerDocument().createTextNode(
+        Text newText = document.createTextNode(
                 substringData(offset, getLength() - offset));
         deleteData(0, offset);
 
diff --git a/libcore/xml/src/main/java/org/apache/harmony/xml/parsers/DocumentBuilderImpl.java b/libcore/xml/src/main/java/org/apache/harmony/xml/parsers/DocumentBuilderImpl.java
index 4b273fe..f3956f8 100644
--- a/libcore/xml/src/main/java/org/apache/harmony/xml/parsers/DocumentBuilderImpl.java
+++ b/libcore/xml/src/main/java/org/apache/harmony/xml/parsers/DocumentBuilderImpl.java
@@ -25,6 +25,7 @@
 
 import org.apache.harmony.xml.dom.CDATASectionImpl;
 import org.apache.harmony.xml.dom.DocumentImpl;
+import org.apache.harmony.xml.dom.DocumentTypeImpl;
 import org.apache.harmony.xml.dom.TextImpl;
 import org.kxml2.io.KXmlParser;
 import org.w3c.dom.Attr;
@@ -242,8 +243,8 @@
                     if (sysid != null && sysid.length() >= 2 && sysid.startsWith("\"") && sysid.endsWith("\"")) {
                         sysid = sysid.substring(1, sysid.length() - 1);
                     }
-                    
-                    document.appendChild(dom.createDocumentType(name, pubid, sysid));
+
+                    document.appendChild(new DocumentTypeImpl(document, name, pubid, sysid));
                 }
                 
             } else if (token == XmlPullParser.COMMENT) {
diff --git a/libcore/xml/src/test/java/tests/xml/DomTest.java b/libcore/xml/src/test/java/tests/xml/DomTest.java
index 69e8b37..0bb27dc 100644
--- a/libcore/xml/src/test/java/tests/xml/DomTest.java
+++ b/libcore/xml/src/test/java/tests/xml/DomTest.java
@@ -31,6 +31,7 @@
 import org.w3c.dom.Notation;
 import org.w3c.dom.ProcessingInstruction;
 import org.w3c.dom.Text;
+import org.w3c.dom.UserDataHandler;
 import org.xml.sax.InputSource;
 
 import javax.xml.parsers.DocumentBuilder;
@@ -44,7 +45,11 @@
 import java.io.StringWriter;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
+
+import static org.w3c.dom.UserDataHandler.NODE_CLONED;
 
 /**
  * Construct a DOM and then interrogate it.
@@ -87,6 +92,7 @@
     private Element name;
     private Attr standard;
     private Attr deluxe;
+    private Text waffles;
     private Element description;
     private Text descriptionText1;
     private CDATASection descriptionText2;
@@ -128,6 +134,7 @@
         name = (Element) item.getChildNodes().item(1);
         standard = name.getAttributeNode("a:standard");
         deluxe = name.getAttributeNode("deluxe");
+        waffles = (Text) name.getChildNodes().item(0);
         description = (Element) item.getChildNodes().item(3);
         descriptionText1 = (Text) description.getChildNodes().item(0);
         descriptionText2 = (CDATASection) description.getChildNodes().item(1);
@@ -153,7 +160,7 @@
         }
 
         allNodes.addAll(Arrays.asList(document, doctype, menu, item, itemXmlns,
-                itemXmlnsA, name, standard, deluxe, description,
+                itemXmlnsA, name, standard, deluxe, waffles, description,
                 descriptionText1, descriptionText2, descriptionText3, option1,
                 option2, option2Reference, wafflemaker, nutrition, vitamins,
                 vitaminsXmlnsA, comment, vitaminc, vitamincText));
@@ -740,6 +747,87 @@
         assertEquals(expected, domToString(document));
     }
 
+    public void testUserDataAttachments() {
+        Object a = new Object();
+        Object b = new Object();
+        for (Node node : allNodes) {
+            node.setUserData("a", a, null);
+            node.setUserData("b", b, null);
+        }
+        for (Node node : allNodes) {
+            assertSame(a, node.getUserData("a"));
+            assertSame(b, node.getUserData("b"));
+            assertEquals(null, node.getUserData("c"));
+            assertEquals(null, node.getUserData("A"));
+        }
+    }
+
+    public void testUserDataRejectsNullKey() {
+        try {
+            menu.setUserData(null, "apple", null);
+            fail();
+        } catch (NullPointerException e) {
+        }
+        try {
+            menu.getUserData(null);
+            fail();
+        } catch (NullPointerException e) {
+        }
+    }
+
+    /**
+     * A shallow clone requires cloning the attributes but not the child nodes.
+     */
+    public void testUserDataHandlerNotifiedOfShallowClones() {
+        RecordingHandler handler = new RecordingHandler();
+        name.setUserData("a", "apple", handler);
+        name.setUserData("b", "banana", handler);
+        standard.setUserData("c", "cat", handler);
+        waffles.setUserData("d", "dog", handler);
+
+        Element clonedName = (Element) name.cloneNode(false);
+        Attr clonedStandard = clonedName.getAttributeNode("a:standard");
+
+        Set<String> expected = new HashSet<String>();
+        expected.add(notification(NODE_CLONED, "a", "apple", name, clonedName));
+        expected.add(notification(NODE_CLONED, "b", "banana", name, clonedName));
+        expected.add(notification(NODE_CLONED, "c", "cat", standard, clonedStandard));
+        assertEquals(expected, handler.calls);
+    }
+
+    /**
+     * A deep clone requires cloning both the attributes and the child nodes.
+     */
+    public void testUserDataHandlerNotifiedOfDeepClones() {
+        RecordingHandler handler = new RecordingHandler();
+        name.setUserData("a", "apple", handler);
+        name.setUserData("b", "banana", handler);
+        standard.setUserData("c", "cat", handler);
+        waffles.setUserData("d", "dog", handler);
+
+        Element clonedName = (Element) name.cloneNode(true);
+        Attr clonedStandard = clonedName.getAttributeNode("a:standard");
+        Text clonedWaffles = (Text) clonedName.getChildNodes().item(0);
+
+        Set<String> expected = new HashSet<String>();
+        expected.add(notification(NODE_CLONED, "a", "apple", name, clonedName));
+        expected.add(notification(NODE_CLONED, "b", "banana", name, clonedName));
+        expected.add(notification(NODE_CLONED, "c", "cat", standard, clonedStandard));
+        expected.add(notification(NODE_CLONED, "d", "dog", waffles, clonedWaffles));
+        assertEquals(expected, handler.calls);
+    }
+
+    private class RecordingHandler implements UserDataHandler {
+        final Set<String> calls = new HashSet<String>();
+        public void handle(short operation, String key, Object data, Node src, Node dst) {
+            calls.add(notification(operation, key, data, src, dst));
+        }
+    }
+
+    private String notification(short operation, String key, Object data, Node src, Node dst) {
+        return "op:" + operation + " key:" + key + " data:" + data + " src:" + src + " dst:" + dst;
+    }
+
     private String domToString(Document document) throws TransformerException {
         StringWriter writer = new StringWriter();
         transformer.transform(new DOMSource(document), new StreamResult(writer));