1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package org.apache.harmony.xml.dom;
18
19import java.net.URI;
20import java.net.URISyntaxException;
21import java.util.ArrayList;
22import java.util.List;
23import java.util.Map;
24import org.w3c.dom.Attr;
25import org.w3c.dom.CharacterData;
26import org.w3c.dom.DOMException;
27import org.w3c.dom.Document;
28import org.w3c.dom.Element;
29import org.w3c.dom.NamedNodeMap;
30import org.w3c.dom.Node;
31import org.w3c.dom.NodeList;
32import org.w3c.dom.ProcessingInstruction;
33import org.w3c.dom.TypeInfo;
34import org.w3c.dom.UserDataHandler;
35
36/**
37 * A straightforward implementation of the corresponding W3C DOM node.
38 *
39 * <p>Some fields have package visibility so other classes can access them while
40 * maintaining the DOM structure.
41 *
42 * <p>This class represents a Node that has neither a parent nor children.
43 * Subclasses may have either.
44 *
45 * <p>Some code was adapted from Apache Xerces.
46 */
47public abstract class NodeImpl implements Node {
48
49    private static final NodeList EMPTY_LIST = new NodeListImpl();
50
51    static final TypeInfo NULL_TYPE_INFO = new TypeInfo() {
52        public String getTypeName() {
53            return null;
54        }
55        public String getTypeNamespace() {
56            return null;
57        }
58        public boolean isDerivedFrom(
59                String typeNamespaceArg, String typeNameArg, int derivationMethod) {
60            return false;
61        }
62    };
63
64    /**
65     * The containing document. This is non-null except for DocumentTypeImpl
66     * nodes created by the DOMImplementation.
67     */
68    DocumentImpl document;
69
70    NodeImpl(DocumentImpl document) {
71        this.document = document;
72    }
73
74    public Node appendChild(Node newChild) throws DOMException {
75        throw new DOMException(DOMException.HIERARCHY_REQUEST_ERR, null);
76    }
77
78    public final Node cloneNode(boolean deep) {
79        return document.cloneOrImportNode(UserDataHandler.NODE_CLONED, this, deep);
80    }
81
82    public NamedNodeMap getAttributes() {
83        return null;
84    }
85
86    public NodeList getChildNodes() {
87        return EMPTY_LIST;
88    }
89
90    public Node getFirstChild() {
91        return null;
92    }
93
94    public Node getLastChild() {
95        return null;
96    }
97
98    public String getLocalName() {
99        return null;
100    }
101
102    public String getNamespaceURI() {
103        return null;
104    }
105
106    public Node getNextSibling() {
107        return null;
108    }
109
110    public String getNodeName() {
111        return null;
112    }
113
114    public abstract short getNodeType();
115
116    public String getNodeValue() throws DOMException {
117        return null;
118    }
119
120    public final Document getOwnerDocument() {
121        return document == this ? null : document;
122    }
123
124    public Node getParentNode() {
125        return null;
126    }
127
128    public String getPrefix() {
129        return null;
130    }
131
132    public Node getPreviousSibling() {
133        return null;
134    }
135
136    public boolean hasAttributes() {
137        return false;
138    }
139
140    public boolean hasChildNodes() {
141        return false;
142    }
143
144    public Node insertBefore(Node newChild, Node refChild) throws DOMException {
145        throw new DOMException(DOMException.HIERARCHY_REQUEST_ERR, null);
146    }
147
148    public boolean isSupported(String feature, String version) {
149        return DOMImplementationImpl.getInstance().hasFeature(feature, version);
150    }
151
152    public void normalize() {
153    }
154
155    public Node removeChild(Node oldChild) throws DOMException {
156        throw new DOMException(DOMException.HIERARCHY_REQUEST_ERR, null);
157    }
158
159    public Node replaceChild(Node newChild, Node oldChild) throws DOMException {
160        throw new DOMException(DOMException.HIERARCHY_REQUEST_ERR, null);
161    }
162
163    public final void setNodeValue(String nodeValue) throws DOMException {
164        switch (getNodeType()) {
165            case CDATA_SECTION_NODE:
166            case COMMENT_NODE:
167            case TEXT_NODE:
168                ((CharacterData) this).setData(nodeValue);
169                return;
170
171            case PROCESSING_INSTRUCTION_NODE:
172                ((ProcessingInstruction) this).setData(nodeValue);
173                return;
174
175            case ATTRIBUTE_NODE:
176                ((Attr) this).setValue(nodeValue);
177                return;
178
179            case ELEMENT_NODE:
180            case ENTITY_REFERENCE_NODE:
181            case ENTITY_NODE:
182            case DOCUMENT_NODE:
183            case DOCUMENT_TYPE_NODE:
184            case DOCUMENT_FRAGMENT_NODE:
185            case NOTATION_NODE:
186                return; // do nothing!
187
188            default:
189                throw new DOMException(DOMException.NOT_SUPPORTED_ERR,
190                        "Unsupported node type " + getNodeType());
191        }
192    }
193
194    public void setPrefix(String prefix) throws DOMException {
195    }
196
197    /**
198     * Validates the element or attribute namespace prefix on this node.
199     *
200     * @param namespaceAware whether this node is namespace aware
201     * @param namespaceURI this node's namespace URI
202     */
203    static String validatePrefix(String prefix, boolean namespaceAware, String namespaceURI) {
204        if (!namespaceAware) {
205            throw new DOMException(DOMException.NAMESPACE_ERR, prefix);
206        }
207
208        if (prefix != null) {
209            if (namespaceURI == null
210                    || !DocumentImpl.isXMLIdentifier(prefix)
211                    || "xml".equals(prefix) && !"http://www.w3.org/XML/1998/namespace".equals(namespaceURI)
212                    || "xmlns".equals(prefix) && !"http://www.w3.org/2000/xmlns/".equals(namespaceURI)) {
213                throw new DOMException(DOMException.NAMESPACE_ERR, prefix);
214            }
215        }
216
217        return prefix;
218    }
219
220    /**
221     * Sets {@code node} to be namespace-aware and assigns its namespace URI
222     * and qualified name.
223     *
224     * @param node an element or attribute node.
225     * @param namespaceURI this node's namespace URI. May be null.
226     * @param qualifiedName a possibly-prefixed name like "img" or "html:img".
227     */
228    static void setNameNS(NodeImpl node, String namespaceURI, String qualifiedName) {
229        if (qualifiedName == null) {
230            throw new DOMException(DOMException.NAMESPACE_ERR, qualifiedName);
231        }
232
233        String prefix = null;
234        int p = qualifiedName.lastIndexOf(":");
235        if (p != -1) {
236            prefix = validatePrefix(qualifiedName.substring(0, p), true, namespaceURI);
237            qualifiedName = qualifiedName.substring(p + 1);
238        }
239
240        if (!DocumentImpl.isXMLIdentifier(qualifiedName)) {
241            throw new DOMException(DOMException.INVALID_CHARACTER_ERR, qualifiedName);
242        }
243
244        switch (node.getNodeType()) {
245        case ATTRIBUTE_NODE:
246            if ("xmlns".equals(qualifiedName)
247                    && !"http://www.w3.org/2000/xmlns/".equals(namespaceURI)) {
248                throw new DOMException(DOMException.NAMESPACE_ERR, qualifiedName);
249            }
250
251            AttrImpl attr = (AttrImpl) node;
252            attr.namespaceAware = true;
253            attr.namespaceURI = namespaceURI;
254            attr.prefix = prefix;
255            attr.localName = qualifiedName;
256            break;
257
258        case ELEMENT_NODE:
259            ElementImpl element = (ElementImpl) node;
260            element.namespaceAware = true;
261            element.namespaceURI = namespaceURI;
262            element.prefix = prefix;
263            element.localName = qualifiedName;
264            break;
265
266        default:
267            throw new DOMException(DOMException.NOT_SUPPORTED_ERR,
268                    "Cannot rename nodes of type " + node.getNodeType());
269        }
270    }
271
272    /**
273     * Sets {@code node} to be not namespace-aware and assigns its name.
274     *
275     * @param node an element or attribute node.
276     */
277    static void setName(NodeImpl node, String name) {
278        int prefixSeparator = name.lastIndexOf(":");
279        if (prefixSeparator != -1) {
280            String prefix = name.substring(0, prefixSeparator);
281            String localName = name.substring(prefixSeparator + 1);
282            if (!DocumentImpl.isXMLIdentifier(prefix) || !DocumentImpl.isXMLIdentifier(localName)) {
283                throw new DOMException(DOMException.INVALID_CHARACTER_ERR, name);
284            }
285        } else if (!DocumentImpl.isXMLIdentifier(name)) {
286            throw new DOMException(DOMException.INVALID_CHARACTER_ERR, name);
287        }
288
289        switch (node.getNodeType()) {
290        case ATTRIBUTE_NODE:
291            AttrImpl attr = (AttrImpl) node;
292            attr.namespaceAware = false;
293            attr.localName = name;
294            break;
295
296        case ELEMENT_NODE:
297            ElementImpl element = (ElementImpl) node;
298            element.namespaceAware = false;
299            element.localName = name;
300            break;
301
302        default:
303            throw new DOMException(DOMException.NOT_SUPPORTED_ERR,
304                    "Cannot rename nodes of type " + node.getNodeType());
305        }
306    }
307
308    public final String getBaseURI() {
309        switch (getNodeType()) {
310            case DOCUMENT_NODE:
311                return sanitizeUri(((Document) this).getDocumentURI());
312
313            case ELEMENT_NODE:
314                Element element = (Element) this;
315                String uri = element.getAttributeNS(
316                        "http://www.w3.org/XML/1998/namespace", "base"); // or "xml:base"
317
318                try {
319                    // if this node has no base URI, return the parent's.
320                    if (uri == null || uri.isEmpty()) {
321                        return getParentBaseUri();
322                    }
323
324                    // if this node's URI is absolute, return it
325                    if (new URI(uri).isAbsolute()) {
326                        return uri;
327                    }
328
329                    // this node has a relative URI. Try to resolve it against the
330                    // parent, but if that doesn't work just give up and return null.
331                    String parentUri = getParentBaseUri();
332                    if (parentUri == null) {
333                        return null;
334                    }
335
336                    return new URI(parentUri).resolve(uri).toString();
337                } catch (URISyntaxException e) {
338                    return null;
339                }
340
341            case PROCESSING_INSTRUCTION_NODE:
342                return getParentBaseUri();
343
344            case NOTATION_NODE:
345            case ENTITY_NODE:
346                // When we support these node types, the parser should
347                // initialize a base URI field on these nodes.
348                return null;
349
350            case ENTITY_REFERENCE_NODE:
351                // TODO: get this value from the parser, falling back to the
352                // referenced entity's baseURI if that doesn't exist
353                return null;
354
355            case DOCUMENT_TYPE_NODE:
356            case DOCUMENT_FRAGMENT_NODE:
357            case ATTRIBUTE_NODE:
358            case TEXT_NODE:
359            case CDATA_SECTION_NODE:
360            case COMMENT_NODE:
361                return null;
362
363            default:
364                throw new DOMException(DOMException.NOT_SUPPORTED_ERR,
365                        "Unsupported node type " + getNodeType());
366        }
367    }
368
369    private String getParentBaseUri() {
370        Node parentNode = getParentNode();
371        return parentNode != null ? parentNode.getBaseURI() : null;
372    }
373
374    /**
375     * Returns the sanitized input if it is a URI, or {@code null} otherwise.
376     */
377    private String sanitizeUri(String uri) {
378        if (uri == null || uri.length() == 0) {
379            return null;
380        }
381        try {
382            return new URI(uri).toString();
383        } catch (URISyntaxException e) {
384            return null;
385        }
386    }
387
388    public short compareDocumentPosition(Node other)
389            throws DOMException {
390        throw new UnsupportedOperationException(); // TODO
391    }
392
393    public String getTextContent() throws DOMException {
394        return getNodeValue();
395    }
396
397    void getTextContent(StringBuilder buf) throws DOMException {
398        String content = getNodeValue();
399        if (content != null) {
400            buf.append(content);
401        }
402    }
403
404    public final void setTextContent(String textContent) throws DOMException {
405        switch (getNodeType()) {
406            case DOCUMENT_TYPE_NODE:
407            case DOCUMENT_NODE:
408                return; // do nothing!
409
410            case ELEMENT_NODE:
411            case ENTITY_NODE:
412            case ENTITY_REFERENCE_NODE:
413            case DOCUMENT_FRAGMENT_NODE:
414                // remove all existing children
415                Node child;
416                while ((child = getFirstChild()) != null) {
417                    removeChild(child);
418                }
419                // create a text node to hold the given content
420                if (textContent != null && textContent.length() != 0) {
421                    appendChild(document.createTextNode(textContent));
422                }
423                return;
424
425            case ATTRIBUTE_NODE:
426            case TEXT_NODE:
427            case CDATA_SECTION_NODE:
428            case PROCESSING_INSTRUCTION_NODE:
429            case COMMENT_NODE:
430            case NOTATION_NODE:
431                setNodeValue(textContent);
432                return;
433
434            default:
435                throw new DOMException(DOMException.NOT_SUPPORTED_ERR,
436                        "Unsupported node type " + getNodeType());
437        }
438    }
439
440    public boolean isSameNode(Node other) {
441        return this == other;
442    }
443
444    /**
445     * Returns the element whose namespace definitions apply to this node. Use
446     * this element when mapping prefixes to URIs and vice versa.
447     */
448    private NodeImpl getNamespacingElement() {
449        switch (this.getNodeType()) {
450            case ELEMENT_NODE:
451                return this;
452
453            case DOCUMENT_NODE:
454                return (NodeImpl) ((Document) this).getDocumentElement();
455
456            case ENTITY_NODE:
457            case NOTATION_NODE:
458            case DOCUMENT_FRAGMENT_NODE:
459            case DOCUMENT_TYPE_NODE:
460                return null;
461
462            case ATTRIBUTE_NODE:
463                return (NodeImpl) ((Attr) this).getOwnerElement();
464
465            case TEXT_NODE:
466            case CDATA_SECTION_NODE:
467            case ENTITY_REFERENCE_NODE:
468            case PROCESSING_INSTRUCTION_NODE:
469            case COMMENT_NODE:
470                return getContainingElement();
471
472            default:
473                throw new DOMException(DOMException.NOT_SUPPORTED_ERR,
474                        "Unsupported node type " + getNodeType());
475        }
476    }
477
478    /**
479     * Returns the nearest ancestor element that contains this node.
480     */
481    private NodeImpl getContainingElement() {
482        for (Node p = getParentNode(); p != null; p = p.getParentNode()) {
483            if (p.getNodeType() == ELEMENT_NODE) {
484                return (NodeImpl) p;
485            }
486        }
487        return null;
488    }
489
490    public final String lookupPrefix(String namespaceURI) {
491        if (namespaceURI == null) {
492            return null;
493        }
494
495        // the XML specs define some prefixes (like "xml" and "xmlns") but this
496        // API is explicitly defined to ignore those.
497
498        NodeImpl target = getNamespacingElement();
499        for (NodeImpl node = target; node != null; node = node.getContainingElement()) {
500            // check this element's namespace first
501            if (namespaceURI.equals(node.getNamespaceURI())
502                    && target.isPrefixMappedToUri(node.getPrefix(), namespaceURI)) {
503                return node.getPrefix();
504            }
505
506            // search this element for an attribute of this form:
507            //   xmlns:foo="http://namespaceURI"
508            if (!node.hasAttributes()) {
509                continue;
510            }
511            NamedNodeMap attributes = node.getAttributes();
512            for (int i = 0, length = attributes.getLength(); i < length; i++) {
513                Node attr = attributes.item(i);
514                if (!"http://www.w3.org/2000/xmlns/".equals(attr.getNamespaceURI())
515                        || !"xmlns".equals(attr.getPrefix())
516                        || !namespaceURI.equals(attr.getNodeValue())) {
517                    continue;
518                }
519                if (target.isPrefixMappedToUri(attr.getLocalName(), namespaceURI)) {
520                    return attr.getLocalName();
521                }
522            }
523        }
524
525        return null;
526    }
527
528    /**
529     * Returns true if the given prefix is mapped to the given URI on this
530     * element. Since child elements can redefine prefixes, this check is
531     * necessary: {@code
532     * <foo xmlns:a="http://good">
533     *   <bar xmlns:a="http://evil">
534     *     <a:baz />
535     *   </bar>
536     * </foo>}
537     *
538     * @param prefix the prefix to find. Nullable.
539     * @param uri the URI to match. Non-null.
540     */
541    boolean isPrefixMappedToUri(String prefix, String uri) {
542        if (prefix == null) {
543            return false;
544        }
545
546        String actual = lookupNamespaceURI(prefix);
547        return uri.equals(actual);
548    }
549
550    public final boolean isDefaultNamespace(String namespaceURI) {
551        String actual = lookupNamespaceURI(null); // null yields the default namespace
552        return namespaceURI == null
553                ? actual == null
554                : namespaceURI.equals(actual);
555    }
556
557    public final String lookupNamespaceURI(String prefix) {
558        NodeImpl target = getNamespacingElement();
559        for (NodeImpl node = target; node != null; node = node.getContainingElement()) {
560            // check this element's namespace first
561            String nodePrefix = node.getPrefix();
562            if (node.getNamespaceURI() != null) {
563                if (prefix == null // null => default prefix
564                        ? nodePrefix == null
565                        : prefix.equals(nodePrefix)) {
566                    return node.getNamespaceURI();
567                }
568            }
569
570            // search this element for an attribute of the appropriate form.
571            //    default namespace: xmlns="http://resultUri"
572            //          non default: xmlns:specifiedPrefix="http://resultUri"
573            if (!node.hasAttributes()) {
574                continue;
575            }
576            NamedNodeMap attributes = node.getAttributes();
577            for (int i = 0, length = attributes.getLength(); i < length; i++) {
578                Node attr = attributes.item(i);
579                if (!"http://www.w3.org/2000/xmlns/".equals(attr.getNamespaceURI())) {
580                    continue;
581                }
582                if (prefix == null // null => default prefix
583                        ? "xmlns".equals(attr.getNodeName())
584                        : "xmlns".equals(attr.getPrefix()) && prefix.equals(attr.getLocalName())) {
585                    String value = attr.getNodeValue();
586                    return value.length() > 0 ? value : null;
587                }
588            }
589        }
590
591        return null;
592    }
593
594    /**
595     * Returns a list of objects such that two nodes are equal if their lists
596     * are equal. Be careful: the lists may contain NamedNodeMaps and Nodes,
597     * neither of which override Object.equals(). Such values must be compared
598     * manually.
599     */
600    private static List<Object> createEqualityKey(Node node) {
601        List<Object> values = new ArrayList<Object>();
602        values.add(node.getNodeType());
603        values.add(node.getNodeName());
604        values.add(node.getLocalName());
605        values.add(node.getNamespaceURI());
606        values.add(node.getPrefix());
607        values.add(node.getNodeValue());
608        for (Node child = node.getFirstChild(); child != null; child = child.getNextSibling()) {
609            values.add(child);
610        }
611
612        switch (node.getNodeType()) {
613            case DOCUMENT_TYPE_NODE:
614                DocumentTypeImpl doctype = (DocumentTypeImpl) node;
615                values.add(doctype.getPublicId());
616                values.add(doctype.getSystemId());
617                values.add(doctype.getInternalSubset());
618                values.add(doctype.getEntities());
619                values.add(doctype.getNotations());
620                break;
621
622            case ELEMENT_NODE:
623                Element element = (Element) node;
624                values.add(element.getAttributes());
625                break;
626        }
627
628        return values;
629    }
630
631    public final boolean isEqualNode(Node arg) {
632        if (arg == this) {
633            return true;
634        }
635
636        List<Object> listA = createEqualityKey(this);
637        List<Object> listB = createEqualityKey(arg);
638
639        if (listA.size() != listB.size()) {
640            return false;
641        }
642
643        for (int i = 0; i < listA.size(); i++) {
644            Object a = listA.get(i);
645            Object b = listB.get(i);
646
647            if (a == b) {
648                continue;
649
650            } else if (a == null || b == null) {
651                return false;
652
653            } else if (a instanceof String || a instanceof Short) {
654                if (!a.equals(b)) {
655                    return false;
656                }
657
658            } else if (a instanceof NamedNodeMap) {
659                if (!(b instanceof NamedNodeMap)
660                        || !namedNodeMapsEqual((NamedNodeMap) a, (NamedNodeMap) b)) {
661                    return false;
662                }
663
664            } else if (a instanceof Node) {
665                if (!(b instanceof Node)
666                        || !((Node) a).isEqualNode((Node) b)) {
667                    return false;
668                }
669
670            } else {
671                throw new AssertionError(); // unexpected type
672            }
673        }
674
675        return true;
676    }
677
678    private boolean namedNodeMapsEqual(NamedNodeMap a, NamedNodeMap b) {
679        if (a.getLength() != b.getLength()) {
680            return false;
681        }
682        for (int i = 0; i < a.getLength(); i++) {
683            Node aNode = a.item(i);
684            Node bNode = aNode.getLocalName() == null
685                    ? b.getNamedItem(aNode.getNodeName())
686                    : b.getNamedItemNS(aNode.getNamespaceURI(), aNode.getLocalName());
687            if (bNode == null || !aNode.isEqualNode(bNode)) {
688                return false;
689            }
690        }
691        return true;
692    }
693
694    public final Object getFeature(String feature, String version) {
695        return isSupported(feature, version) ? this : null;
696    }
697
698    public final Object setUserData(String key, Object data, UserDataHandler handler) {
699        if (key == null) {
700            throw new NullPointerException("key == null");
701        }
702        Map<String, UserData> map = document.getUserDataMap(this);
703        UserData previous = data == null
704                ? map.remove(key)
705                : map.put(key, new UserData(data, handler));
706        return previous != null ? previous.value : null;
707    }
708
709    public final Object getUserData(String key) {
710        if (key == null) {
711            throw new NullPointerException("key == null");
712        }
713        Map<String, UserData> map = document.getUserDataMapForRead(this);
714        UserData userData = map.get(key);
715        return userData != null ? userData.value : null;
716    }
717
718    static class UserData {
719        final Object value;
720        final UserDataHandler handler;
721        UserData(Object value, UserDataHandler handler) {
722            this.value = value;
723            this.handler = handler;
724        }
725    }
726}
727