LayoutTests:
[WebKit-https.git] / WebCore / dom / Node.cpp
1 /**
2  * This file is part of the DOM implementation for KDE.
3  *
4  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
5  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
6  *           (C) 2001 Dirk Mueller (mueller@kde.org)
7  * Copyright (C) 2004, 2005, 2006 Apple Computer, Inc.
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Library General Public
11  * License as published by the Free Software Foundation; either
12  * version 2 of the License, or (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17  * Library General Public License for more details.
18  *
19  * You should have received a copy of the GNU Library General Public License
20  * along with this library; see the file COPYING.LIB.  If not, write to
21  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
22  * Boston, MA 02111-1307, USA.
23  */
24
25 #include "config.h"
26 #include "Node.h"
27
28 #include "ChildNodeList.h"
29 #include "DOMImplementation.h"
30 #include "Document.h"
31 #include "ExceptionCode.h"
32 #include "Frame.h"
33 #include "NamedAttrMap.h"
34 #include "Text.h"
35 #include "htmlediting.h"
36 #include "HTMLNames.h"
37 #include "kjs_binding.h"
38 #include "RenderObject.h"
39 #include "TextStream.h"
40
41 namespace WebCore {
42
43 using namespace HTMLNames;
44
45 /**
46  * NodeList which lists all Nodes in a document with a given tag name
47  */
48 class TagNodeList : public NodeList
49 {
50 public:
51     TagNodeList(Node *n, const AtomicString& namespaceURI, const AtomicString& localName);
52
53     // DOM methods overridden from  parent classes
54     virtual unsigned length() const;
55     virtual Node *item (unsigned index) const;
56
57     // Other methods (not part of DOM)
58
59 protected:
60     virtual bool nodeMatches(Node *testNode) const;
61
62     AtomicString m_namespaceURI;
63     AtomicString m_localName;
64 };
65
66 TagNodeList::TagNodeList(Node *n, const AtomicString& namespaceURI, const AtomicString& localName)
67     : NodeList(n), 
68       m_namespaceURI(namespaceURI), 
69       m_localName(localName)
70 {
71 }
72
73 unsigned TagNodeList::length() const
74 {
75     return recursiveLength();
76 }
77
78 Node *TagNodeList::item(unsigned index) const
79 {
80     return recursiveItem(index);
81 }
82
83 bool TagNodeList::nodeMatches(Node *testNode) const
84 {
85     if (!testNode->isElementNode())
86         return false;
87
88     if (m_namespaceURI != starAtom && m_namespaceURI != testNode->namespaceURI())
89         return false;
90     
91     return m_localName == starAtom || m_localName == testNode->localName();
92 }
93
94
95 #ifndef NDEBUG
96 struct NodeImplCounter { 
97     static int count; 
98     ~NodeImplCounter() { if (count != 0) fprintf(stderr, "LEAK: %d Node\n", count); }
99 };
100 int NodeImplCounter::count = 0;
101 static NodeImplCounter nodeImplCounter;
102 #endif
103
104 Node::Node(Document *doc)
105     : m_document(doc),
106       m_previous(0),
107       m_next(0),
108       m_renderer(0),
109       m_nodeLists(0),
110       m_tabIndex(0),
111       m_hasId(false),
112       m_hasClass(false),
113       m_hasStyle(false),
114       m_attached(false),
115       m_changed(false),
116       m_hasChangedChild(false),
117       m_inDocument(false),
118       m_isLink(false),
119       m_specified(false),
120       m_focused(false),
121       m_active(false),
122       m_hovered(false),
123       m_inActiveChain(false),
124       m_styleElement(false),
125       m_implicit(false),
126       m_inDetach(false)
127 {
128 #ifndef NDEBUG
129     ++NodeImplCounter::count;
130 #endif
131 }
132
133 void Node::setDocument(Document *doc)
134 {
135     if (inDocument())
136         return;
137     
138     m_document = doc;
139 }
140
141 Node::~Node()
142 {
143 #ifndef NDEBUG
144     --NodeImplCounter::count;
145 #endif
146     if (renderer())
147         detach();
148     delete m_nodeLists;
149     if (m_previous)
150         m_previous->setNextSibling(0);
151     if (m_next)
152         m_next->setPreviousSibling(0);
153 }
154
155 String Node::nodeValue() const
156 {
157   return String();
158 }
159
160 void Node::setNodeValue( const String &/*_nodeValue*/, ExceptionCode& ec)
161 {
162     // NO_MODIFICATION_ALLOWED_ERR: Raised when the node is readonly
163     if (isReadOnlyNode()) {
164         ec = NO_MODIFICATION_ALLOWED_ERR;
165         return;
166     }
167
168     // be default nodeValue is null, so setting it has no effect
169 }
170
171 PassRefPtr<NodeList> Node::childNodes()
172 {
173     return new ChildNodeList(this);
174 }
175
176 Node *Node::firstChild() const
177 {
178   return 0;
179 }
180
181 Node *Node::lastChild() const
182 {
183   return 0;
184 }
185
186 Node *Node::lastDescendant() const
187 {
188     Node *n = const_cast<Node *>(this);
189     while (n && n->lastChild())
190         n = n->lastChild();
191     return n;
192 }
193
194 Node* Node::firstDescendant() const
195 {
196     Node *n = const_cast<Node *>(this);
197     while (n && n->firstChild())
198         n = n->firstChild();
199     return n;
200 }
201
202 bool Node::insertBefore(PassRefPtr<Node>, Node*, ExceptionCode& ec)
203 {
204     ec = HIERARCHY_REQUEST_ERR;
205     return false;
206 }
207
208 bool Node::replaceChild(PassRefPtr<Node>, Node*, ExceptionCode& ec)
209 {
210     ec = HIERARCHY_REQUEST_ERR;
211     return false;
212 }
213
214 bool Node::removeChild(Node*, ExceptionCode& ec)
215 {
216     ec = NOT_FOUND_ERR;
217     return false;
218 }
219
220 bool Node::appendChild(PassRefPtr<Node>, ExceptionCode& ec)
221 {
222     ec = HIERARCHY_REQUEST_ERR;
223     return false;
224 }
225
226 void Node::remove(ExceptionCode& ec)
227 {
228     ref();
229     if (Node *p = parentNode())
230         p->removeChild(this, ec);
231     else
232         ec = HIERARCHY_REQUEST_ERR;
233     deref();
234 }
235
236 bool Node::hasChildNodes(  ) const
237 {
238   return false;
239 }
240
241 void Node::normalize ()
242 {
243     ExceptionCode ec = 0;
244     Node *child = firstChild();
245
246     if (isElementNode()) {
247         // Normalize any attribute children we might have 
248         Element *element = static_cast<Element *>(this);
249         NamedAttrMap *attrMap = element->attributes();
250         
251         if (attrMap) {
252             unsigned numAttrs = attrMap->length();
253             
254             for (unsigned i = 0; i < numAttrs; i++) {
255                 Attribute *attribute = attrMap->attributeItem(i);
256                 Attr *attr = attribute->attr();
257                 
258                 if (attr)
259                     attr->normalize();
260             }
261         }
262     }
263     
264     // Recursively go through the subtree beneath us, normalizing all nodes. In the case
265     // where there are two adjacent text nodes, they are merged together
266     while (child) {
267         Node *nextChild = child->nextSibling();
268
269         if (nextChild && child->nodeType() == TEXT_NODE && nextChild->nodeType() == TEXT_NODE) {
270             // Current child and the next one are both text nodes... merge them
271             Text *currentText = static_cast<Text*>(child);
272             Text *nextText = static_cast<Text*>(nextChild);
273
274             currentText->appendData(nextText->data(),ec);
275             if (ec)
276                 return;
277
278             nextChild->remove(ec);
279             if (ec)
280                 return;
281         }
282         else {
283             child->normalize();
284             child = nextChild;
285         }
286     }
287     
288     // Check if we have a single empty text node left and remove it if so
289     child = firstChild();
290     if (child && !child->nextSibling() && child->isTextNode()) {
291         Text *text = static_cast<Text*>(child);
292         if (text->data().isEmpty())
293             child->remove(ec);
294     }
295 }
296
297 const AtomicString& Node::prefix() const
298 {
299     // For nodes other than elements and attributes, the prefix is always null
300     return nullAtom;
301 }
302
303 void Node::setPrefix(const AtomicString &/*_prefix*/, ExceptionCode& ec)
304 {
305     // The spec says that for nodes other than elements and attributes, prefix is always null.
306     // It does not say what to do when the user tries to set the prefix on another type of
307     // node, however mozilla throws a NAMESPACE_ERR exception
308     ec = NAMESPACE_ERR;
309 }
310
311 const AtomicString& Node::localName() const
312 {
313     return emptyAtom;
314 }
315
316 const AtomicString& Node::namespaceURI() const
317 {
318     return nullAtom;
319 }
320
321 ContainerNode* Node::addChild(PassRefPtr<Node>)
322 {
323     return 0;
324 }
325
326 bool Node::isContentEditable() const
327 {
328     return parent() && parent()->isContentEditable();
329 }
330
331 bool Node::isContentRichlyEditable() const
332 {
333     return parent() && parent()->isContentRichlyEditable();
334 }
335
336 IntRect Node::getRect() const
337 {
338     int _x, _y;
339     if (renderer() && renderer()->absolutePosition(_x, _y))
340         return IntRect( _x, _y, renderer()->width(), renderer()->height() + renderer()->borderTopExtra() + renderer()->borderBottomExtra());
341
342     return IntRect();
343 }
344
345 void Node::setChanged(bool b)
346 {
347     if (b && !attached()) // changed compared to what?
348         return;
349
350     m_changed = b;
351     if ( b ) {
352         Node *p = parentNode();
353         while ( p ) {
354             p->setHasChangedChild( true );
355             p = p->parentNode();
356         }
357         document()->setDocumentChanged(true);
358     }
359 }
360
361 bool Node::isFocusable() const
362 {
363     return false;
364 }
365
366 bool Node::isKeyboardFocusable(KeyboardEvent*) const
367 {
368     return isFocusable();
369 }
370
371 bool Node::isMouseFocusable() const
372 {
373     return isFocusable();
374 }
375
376 unsigned Node::nodeIndex() const
377 {
378     Node *_tempNode = previousSibling();
379     unsigned count=0;
380     for( count=0; _tempNode; count++ )
381         _tempNode = _tempNode->previousSibling();
382     return count;
383 }
384
385 void Node::registerNodeList(NodeList* list)
386 {
387     if (!m_nodeLists)
388         m_nodeLists = new NodeListSet;
389     m_nodeLists->add(list);
390 }
391
392 void Node::unregisterNodeList(NodeList* list)
393 {
394     if (!m_nodeLists)
395         return;
396     m_nodeLists->remove(list);
397 }
398
399 void Node::notifyLocalNodeListsAttributeChanged()
400 {
401     if (!m_nodeLists)
402         return;
403
404     NodeListSet::iterator end = m_nodeLists->end();
405     for (NodeListSet::iterator i = m_nodeLists->begin(); i != end; ++i)
406         (*i)->rootNodeAttributeChanged();
407 }
408
409 void Node::notifyNodeListsAttributeChanged()
410 {
411     for (Node *n = this; n; n = n->parentNode())
412         n->notifyLocalNodeListsAttributeChanged();
413 }
414
415 void Node::notifyLocalNodeListsChildrenChanged()
416 {
417     if (!m_nodeLists)
418         return;
419
420     NodeListSet::iterator end = m_nodeLists->end();
421     for (NodeListSet::iterator i = m_nodeLists->begin(); i != end; ++i)
422         (*i)->rootNodeChildrenChanged();
423 }
424
425 void Node::notifyNodeListsChildrenChanged()
426 {
427     for (Node *n = this; n; n = n->parentNode())
428         n->notifyLocalNodeListsChildrenChanged();
429 }
430
431 unsigned Node::childNodeCount() const
432 {
433     return 0;
434 }
435
436 Node *Node::childNode(unsigned /*index*/) const
437 {
438     return 0;
439 }
440
441 Node *Node::traverseNextNode(const Node *stayWithin) const
442 {
443     if (firstChild()) {
444         assert(!stayWithin || firstChild()->isDescendantOf(stayWithin));
445         return firstChild();
446     }
447     if (this == stayWithin)
448         return 0;
449     if (nextSibling()) {
450         assert(!stayWithin || nextSibling()->isDescendantOf(stayWithin));
451         return nextSibling();
452     }
453     const Node *n = this;
454     while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
455         n = n->parentNode();
456     if (n) {
457         assert(!stayWithin || !n->nextSibling() || n->nextSibling()->isDescendantOf(stayWithin));
458         return n->nextSibling();
459     }
460     return 0;
461 }
462
463 Node *Node::traverseNextSibling(const Node *stayWithin) const
464 {
465     if (this == stayWithin)
466         return 0;
467     if (nextSibling()) {
468         assert(!stayWithin || nextSibling()->isDescendantOf(stayWithin));
469         return nextSibling();
470     }
471     const Node *n = this;
472     while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
473         n = n->parentNode();
474     if (n) {
475         assert(!stayWithin || !n->nextSibling() || n->nextSibling()->isDescendantOf(stayWithin));
476         return n->nextSibling();
477     }
478     return 0;
479 }
480
481 Node *Node::traversePreviousNode(const Node *stayWithin) const
482 {
483     if (this == stayWithin)
484         return 0;
485     if (previousSibling()) {
486         Node *n = previousSibling();
487         while (n->lastChild())
488             n = n->lastChild();
489         return n;
490     }
491     return parentNode();
492 }
493
494 Node *Node::traversePreviousNodePostOrder(const Node *stayWithin) const
495 {
496     if (lastChild()) {
497         assert(!stayWithin || lastChild()->isDescendantOf(stayWithin));
498         return lastChild();
499     }
500     if (this == stayWithin)
501         return 0;
502     if (previousSibling()) {
503         assert(!stayWithin || previousSibling()->isDescendantOf(stayWithin));
504         return previousSibling();
505     }
506     const Node *n = this;
507     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
508         n = n->parentNode();
509     if (n) {
510         assert(!stayWithin || !n->previousSibling() || n->previousSibling()->isDescendantOf(stayWithin));
511         return n->previousSibling();
512     }
513     return 0;
514 }
515
516 void Node::checkSetPrefix(const AtomicString &_prefix, ExceptionCode& ec)
517 {
518     // Perform error checking as required by spec for setting Node.prefix. Used by
519     // Element::setPrefix() and Attr::setPrefix()
520
521     // FIXME: Implement support for INVALID_CHARACTER_ERR: Raised if the specified prefix contains an illegal character.
522     
523     // NO_MODIFICATION_ALLOWED_ERR: Raised if this node is readonly.
524     if (isReadOnlyNode()) {
525         ec = NO_MODIFICATION_ALLOWED_ERR;
526         return;
527     }
528
529     // FIXME: Implement NAMESPACE_ERR: - Raised if the specified prefix is malformed
530     // We have to comment this out, since it's used for attributes and tag names, and we've only
531     // switched one over.
532     /*
533     // - if the namespaceURI of this node is null,
534     // - if the specified prefix is "xml" and the namespaceURI of this node is different from
535     //   "http://www.w3.org/XML/1998/namespace",
536     // - if this node is an attribute and the specified prefix is "xmlns" and
537     //   the namespaceURI of this node is different from "http://www.w3.org/2000/xmlns/",
538     // - or if this node is an attribute and the qualifiedName of this node is "xmlns" [Namespaces].
539     if ((namespacePart(id()) == noNamespace && id() > ID_LAST_TAG) ||
540         (_prefix == "xml" && String(document()->namespaceURI(id())) != "http://www.w3.org/XML/1998/namespace")) {
541         ec = NAMESPACE_ERR;
542         return;
543     }*/
544 }
545
546 void Node::checkAddChild(Node *newChild, ExceptionCode& ec)
547 {
548     // Perform error checking as required by spec for adding a new child. Used by
549     // appendChild(), replaceChild() and insertBefore()
550
551     // Not mentioned in spec: throw NOT_FOUND_ERR if newChild is null
552     if (!newChild) {
553         ec = NOT_FOUND_ERR;
554         return;
555     }
556
557     // NO_MODIFICATION_ALLOWED_ERR: Raised if this node is readonly
558     if (isReadOnlyNode()) {
559         ec = NO_MODIFICATION_ALLOWED_ERR;
560         return;
561     }
562
563     bool shouldAdoptChild = false;
564
565     // WRONG_DOCUMENT_ERR: Raised if newChild was created from a different document than the one that
566     // created this node.
567     // We assume that if newChild is a DocumentFragment, all children are created from the same document
568     // as the fragment itself (otherwise they could not have been added as children)
569     if (newChild->document() != document()) {
570         // but if the child is not in a document yet then loosen the
571         // restriction, so that e.g. creating an element with the Option()
572         // constructor and then adding it to a different document works,
573         // as it does in Mozilla and Mac IE.
574         if (!newChild->inDocument()) {
575             shouldAdoptChild = true;
576         } else {
577             ec = WRONG_DOCUMENT_ERR;
578             return;
579         }
580     }
581
582     // HIERARCHY_REQUEST_ERR: Raised if this node is of a type that does not allow children of the type of the
583     // newChild node, or if the node to append is one of this node's ancestors.
584
585     // check for ancestor/same node
586     if (newChild == this || isDescendantOf(newChild)) {
587         ec = HIERARCHY_REQUEST_ERR;
588         return;
589     }
590     
591     if (newChild->nodeType() != DOCUMENT_FRAGMENT_NODE) {
592         if (!childTypeAllowed(newChild->nodeType())) {
593             ec = HIERARCHY_REQUEST_ERR;
594             return;
595         }
596     }
597     else {
598         for (Node *n = newChild->firstChild(); n; n = n->nextSibling()) {
599             if (!childTypeAllowed(n->nodeType())) {
600                 ec = HIERARCHY_REQUEST_ERR;
601                 return;
602             }
603         }
604     }
605     
606     // change the document pointer of newChild and all of its children to be the new document
607     if (shouldAdoptChild) {
608         for (Node* node = newChild; node; node = node->traverseNextNode(newChild)) {
609             KJS::ScriptInterpreter::updateDOMNodeDocument(node, node->document(), document());
610             node->setDocument(document());
611         }
612     }
613 }
614
615 bool Node::isDescendantOf(const Node *other) const
616 {
617     // Return true if other is an ancestor of this, otherwise false
618     if (!other)
619         return false;
620     for (const Node *n = parentNode(); n; n = n->parentNode()) {
621         if (n == other)
622             return true;
623     }
624     return false;
625 }
626
627 bool Node::childAllowed( Node *newChild )
628 {
629     return childTypeAllowed(newChild->nodeType());
630 }
631
632 Node::StyleChange Node::diff( RenderStyle *s1, RenderStyle *s2 ) const
633 {
634     // FIXME: The behavior of this function is just totally wrong.  It doesn't handle
635     // explicit inheritance of non-inherited properties and so you end up not re-resolving
636     // style in cases where you need to.
637     StyleChange ch = NoInherit;
638     EDisplay display1 = s1 ? s1->display() : NONE;
639     bool fl1 = s1 && s1->hasPseudoStyle(RenderStyle::FIRST_LETTER);
640     EDisplay display2 = s2 ? s2->display() : NONE;
641     bool fl2 = s2 && s2->hasPseudoStyle(RenderStyle::FIRST_LETTER);
642         
643     if (display1 != display2 || fl1 != fl2)
644         ch = Detach;
645     else if (!s1 || !s2)
646         ch = Inherit;
647     else if (*s1 == *s2)
648         ch = NoChange;
649     else if (s1->inheritedNotEqual(s2))
650         ch = Inherit;
651     
652     // If the pseudoStyles have changed, we want any StyleChange that is not NoChange
653     // because setStyle will do the right thing with anything else.
654     if (ch == NoChange && s1->hasPseudoStyle(RenderStyle::BEFORE)) {
655         RenderStyle* ps2 = s2->getPseudoStyle(RenderStyle::BEFORE);
656         if (!ps2)
657             ch = NoInherit;
658         else {
659             RenderStyle* ps1 = s1->getPseudoStyle(RenderStyle::BEFORE);
660             ch = ps1 && *ps1 == *ps2 ? NoChange : NoInherit;
661         }
662     }
663     if (ch == NoChange && s1->hasPseudoStyle(RenderStyle::AFTER)) {
664         RenderStyle* ps2 = s2->getPseudoStyle(RenderStyle::AFTER);
665         if (!ps2)
666             ch = NoInherit;
667         else {
668             RenderStyle* ps1 = s1->getPseudoStyle(RenderStyle::AFTER);
669             ch = ps2 && *ps1 == *ps2 ? NoChange : NoInherit;
670         }
671     }
672     
673     return ch;
674 }
675
676 #ifndef NDEBUG
677 void Node::dump(TextStream *stream, DeprecatedString ind) const
678 {
679     // ### implement dump() for all appropriate subclasses
680
681     if (m_hasId) { *stream << " hasId"; }
682     if (m_hasClass) { *stream << " hasClass"; }
683     if (m_hasStyle) { *stream << " hasStyle"; }
684     if (m_specified) { *stream << " specified"; }
685     if (m_focused) { *stream << " focused"; }
686     if (m_active) { *stream << " active"; }
687     if (m_styleElement) { *stream << " styleElement"; }
688     if (m_implicit) { *stream << " implicit"; }
689
690     *stream << " tabIndex=" << m_tabIndex;
691     *stream << endl;
692
693     Node *child = firstChild();
694     while(child) {
695         *stream << ind << child->nodeName().deprecatedString().ascii() << ": ";
696         child->dump(stream,ind+"  ");
697         child = child->nextSibling();
698     }
699 }
700 #endif
701
702 void Node::attach()
703 {
704     assert(!attached());
705     assert(!renderer() || (renderer()->style() && renderer()->parent()));
706     document()->incDOMTreeVersion();
707     m_attached = true;
708 }
709
710 void Node::willRemove()
711 {
712 }
713
714 void Node::detach()
715 {
716     m_inDetach = true;
717
718     if (renderer())
719         renderer()->destroy();
720     setRenderer(0);
721
722     Document* doc = document();
723     if (m_hovered)
724         doc->hoveredNodeDetached(this);
725     if (m_inActiveChain)
726         doc->activeChainNodeDetached(this);
727     doc->incDOMTreeVersion();
728
729     m_active = false;
730     m_hovered = false;
731     m_inActiveChain = false;
732     m_attached = false;
733     m_inDetach = false;
734 }
735
736 void Node::insertedIntoDocument()
737 {
738     setInDocument(true);
739     insertedIntoTree(false);
740 }
741
742 void Node::removedFromDocument()
743 {
744     setInDocument(false);
745     removedFromTree(false);
746 }
747
748 void Node::childrenChanged()
749 {
750 }
751
752 bool Node::isReadOnlyNode()
753 {
754     // Entity & Entity Reference nodes and their descendants are read-only
755     Node *n = this;
756     while (n) {
757         if (n->nodeType() == ENTITY_NODE || n->nodeType() == ENTITY_REFERENCE_NODE)
758             return true;
759         n = n->parentNode();
760     }
761     return false;
762 }
763
764 Node *Node::previousEditable() const
765 {
766     Node *node = previousLeafNode();
767     while (node) {
768         if (node->isContentEditable())
769             return node;
770         node = node->previousLeafNode();
771     }
772     return 0;
773 }
774
775 // Offset specifies the child node to start at.  If it is past
776 // the last child, it specifies to start at next sibling.
777 Node *Node::nextEditable(int offset) const
778 {
779     assert(offset>=0);
780     Node *node;
781     if (hasChildNodes())
782         node = (offset >= (int)childNodeCount()) ? nextSibling() : childNode(offset)->nextLeafNode();
783     else
784         node = nextLeafNode();
785     while (node) {
786         if (node->isContentEditable())
787             return node;
788         node = node->nextLeafNode();
789     }
790     return 0;
791 }
792
793 Node *Node::nextEditable() const
794 {
795     Node *node = nextLeafNode();
796     while (node) {
797         if (node->isContentEditable())
798             return node;
799         node = node->nextLeafNode();
800     }
801     return 0;
802 }
803
804 RenderObject * Node::previousRenderer()
805 {
806     for (Node *n = previousSibling(); n; n = n->previousSibling()) {
807         if (n->renderer())
808             return n->renderer();
809     }
810     return 0;
811 }
812
813 RenderObject * Node::nextRenderer()
814 {
815     // Avoid an O(n^2) problem with this function by not checking for nextRenderer() when the parent element hasn't even 
816     // been attached yet.
817     if (parent() && !parent()->attached())
818         return 0;
819
820     for (Node *n = nextSibling(); n; n = n->nextSibling()) {
821         if (n->renderer())
822             return n->renderer();
823     }
824     return 0;
825 }
826
827 // FIXME: This code is used by editing.  Seems like it could move over there and not pollute Node.
828 Node *Node::previousNodeConsideringAtomicNodes() const
829 {
830     if (previousSibling()) {
831         Node *n = previousSibling();
832         while (!isAtomicNode(n) && n->lastChild())
833             n = n->lastChild();
834         return n;
835     }
836     else if (parentNode()) {
837         return parentNode();
838     }
839     else {
840         return 0;
841     }
842 }
843
844 Node *Node::nextNodeConsideringAtomicNodes() const
845 {
846     if (!isAtomicNode(this) && firstChild())
847         return firstChild();
848     if (nextSibling())
849         return nextSibling();
850     const Node *n = this;
851     while (n && !n->nextSibling())
852         n = n->parentNode();
853     if (n)
854         return n->nextSibling();
855     return 0;
856 }
857
858 Node *Node::previousLeafNode() const
859 {
860     Node *node = previousNodeConsideringAtomicNodes();
861     while (node) {
862         if (isAtomicNode(node))
863             return node;
864         node = node->previousNodeConsideringAtomicNodes();
865     }
866     return 0;
867 }
868
869 Node *Node::nextLeafNode() const
870 {
871     Node *node = nextNodeConsideringAtomicNodes();
872     while (node) {
873         if (isAtomicNode(node))
874             return node;
875         node = node->nextNodeConsideringAtomicNodes();
876     }
877     return 0;
878 }
879
880 void Node::createRendererIfNeeded()
881 {
882     if (!document()->shouldCreateRenderers())
883         return;
884     
885     assert(!attached());
886     assert(!renderer());
887     
888     Node *parent = parentNode();    
889     assert(parent);
890     
891     RenderObject *parentRenderer = parent->renderer();
892     if (parentRenderer && parentRenderer->canHaveChildren()
893 #ifdef SVG_SUPPORT
894         && parent->childShouldCreateRenderer(this)
895 #endif
896         ) {
897         RenderStyle* style = styleForRenderer(parentRenderer);
898         if (rendererIsNeeded(style)) {
899             setRenderer(createRenderer(document()->renderArena(), style));
900             if (renderer()) {
901                 renderer()->setStyle(style);
902                 parentRenderer->addChild(renderer(), nextRenderer());
903             }
904         }
905         style->deref(document()->renderArena());
906     }
907 }
908
909 RenderStyle *Node::styleForRenderer(RenderObject *parent)
910 {
911     RenderStyle *style = parent->style();
912     style->ref();
913     return style;
914 }
915
916 bool Node::rendererIsNeeded(RenderStyle *style)
917 {
918     return (document()->documentElement() == this) || (style->display() != NONE);
919 }
920
921 RenderObject *Node::createRenderer(RenderArena *arena, RenderStyle *style)
922 {
923     assert(false);
924     return 0;
925 }
926
927 RenderStyle* Node::renderStyle() const
928
929     return m_renderer ? m_renderer->style() : 0; 
930 }
931
932 void Node::setRenderStyle(RenderStyle* s)
933 {
934     if (m_renderer)
935         m_renderer->setStyle(s); 
936 }
937
938 int Node::maxOffset() const
939 {
940     return 1;
941 }
942
943 // FIXME: Shouldn't these functions be in the editing code?  Code that asks questions about HTML in the core DOM class
944 // is obviously misplaced.
945 int Node::caretMinOffset() const
946 {
947     return renderer() ? renderer()->caretMinOffset() : 0;
948 }
949
950 int Node::caretMaxOffset() const
951 {
952     return renderer() ? renderer()->caretMaxOffset() : 1;
953 }
954
955 unsigned Node::caretMaxRenderedOffset() const
956 {
957     return renderer() ? renderer()->caretMaxRenderedOffset() : 1;
958 }
959
960 int Node::previousOffset (int current) const
961 {
962     return renderer() ? renderer()->previousOffset(current) : current - 1;
963 }
964
965 int Node::nextOffset (int current) const
966 {
967     return renderer() ? renderer()->nextOffset(current) : current + 1;
968 }
969
970 Node* Node::shadowAncestorNode()
971 {
972     Node *n = this;    
973     while (n) {
974         if (n->isShadowNode())
975             return n->shadowParentNode();
976         n = n->parentNode();
977     } 
978     return this;
979 }
980
981 bool Node::isBlockFlow() const
982 {
983     return renderer() && renderer()->isBlockFlow();
984 }
985
986 bool Node::isBlockFlowOrBlockTable() const
987 {
988     return renderer() && (renderer()->isBlockFlow() || renderer()->isTable() && !renderer()->isInline());
989 }
990
991 bool Node::isEditableBlock() const
992 {
993     return isContentEditable() && isBlockFlow();
994 }
995
996 Element *Node::enclosingBlockFlowOrTableElement() const
997 {
998     Node *n = const_cast<Node *>(this);
999     if (isBlockFlowOrBlockTable())
1000         return static_cast<Element *>(n);
1001
1002     while (1) {
1003         n = n->parentNode();
1004         if (!n)
1005             break;
1006         if (n->isBlockFlowOrBlockTable() || n->hasTagName(bodyTag))
1007             return static_cast<Element *>(n);
1008     }
1009     return 0;
1010 }
1011
1012 Element *Node::enclosingBlockFlowElement() const
1013 {
1014     Node *n = const_cast<Node *>(this);
1015     if (isBlockFlow())
1016         return static_cast<Element *>(n);
1017
1018     while (1) {
1019         n = n->parentNode();
1020         if (!n)
1021             break;
1022         if (n->isBlockFlow() || n->hasTagName(bodyTag))
1023             return static_cast<Element *>(n);
1024     }
1025     return 0;
1026 }
1027
1028 Element *Node::enclosingInlineElement() const
1029 {
1030     Node *n = const_cast<Node *>(this);
1031     Node *p;
1032
1033     while (1) {
1034         p = n->parentNode();
1035         if (!p || p->isBlockFlow() || p->hasTagName(bodyTag))
1036             return static_cast<Element *>(n);
1037         // Also stop if any previous sibling is a block
1038         for (Node *sibling = n->previousSibling(); sibling; sibling = sibling->previousSibling()) {
1039             if (sibling->isBlockFlow())
1040                 return static_cast<Element *>(n);
1041         }
1042         n = p;
1043     }
1044     ASSERT_NOT_REACHED();
1045     return 0;
1046 }
1047
1048 Element* Node::rootEditableElement() const
1049 {
1050     Element* result = 0;
1051     for (Node* n = const_cast<Node*>(this); n && n->isContentEditable(); n = n->parentNode()) {
1052         if (n->isElementNode())
1053             result = static_cast<Element*>(n);
1054         if (n->hasTagName(bodyTag))
1055             break;
1056     }
1057     return result;
1058 }
1059
1060 bool Node::inSameContainingBlockFlowElement(Node *n)
1061 {
1062     return n ? enclosingBlockFlowElement() == n->enclosingBlockFlowElement() : false;
1063 }
1064
1065 // FIXME: End of obviously misplaced HTML editing functions.  Try to move these out of Node.
1066
1067 PassRefPtr<NodeList> Node::getElementsByTagName(const String& name)
1068 {
1069     return getElementsByTagNameNS("*", name);
1070 }
1071  
1072 PassRefPtr<NodeList> Node::getElementsByTagNameNS(const String &namespaceURI, const String &localName)
1073 {
1074     if (namespaceURI.isNull() || localName.isNull())
1075         return 0; // FIXME: Who relies on getting 0 instead of a node list in this case?
1076     
1077     String name = localName;
1078     if (document()->isHTMLDocument())
1079         name = localName.lower();
1080     return new TagNodeList(this, AtomicString(namespaceURI), AtomicString(name));
1081 }
1082
1083 bool Node::isSupported(const String &feature, const String &version)
1084 {
1085     return DOMImplementation::instance()->hasFeature(feature, version);
1086 }
1087
1088 Document *Node::ownerDocument() const
1089 {
1090     Document *doc = document();
1091     return doc == this ? 0 : doc;
1092 }
1093
1094 bool Node::hasAttributes() const
1095 {
1096     return false;
1097 }
1098
1099 NamedAttrMap *Node::attributes() const
1100 {
1101     return 0;
1102 }
1103
1104 bool Node::isEqualNode(Node *other) const
1105 {
1106     if (!other)
1107         return false;
1108     
1109     if (nodeType() != other->nodeType())
1110         return false;
1111     
1112     if (nodeName() != other->nodeName())
1113         return false;
1114     
1115     if (localName() != other->localName())
1116         return false;
1117     
1118     if (namespaceURI() != other->namespaceURI())
1119         return false;
1120     
1121     if (prefix() != other->prefix())
1122         return false;
1123     
1124     if (nodeValue() != other->nodeValue())
1125         return false;
1126     
1127     NamedAttrMap *attrs = attributes();
1128     NamedAttrMap *otherAttrs = other->attributes();
1129     
1130     if (!attrs && otherAttrs)
1131         return false;
1132     
1133     if (attrs && !attrs->mapsEquivalent(otherAttrs))
1134         return false;
1135     
1136     Node *child = firstChild();
1137     Node *otherChild = other->firstChild();
1138     
1139     while (child) {
1140         if (!child->isEqualNode(otherChild))
1141             return false;
1142         
1143         child = child->nextSibling();
1144         otherChild = otherChild->nextSibling();
1145     }
1146     
1147     if (otherChild)
1148         return false;
1149     
1150     // FIXME: For DocumentType nodes we should check equality on
1151     // the entities and notations NamedNodeMaps as well.
1152     
1153     return true;
1154 }
1155
1156 bool Node::isDefaultNamespace(const String &namespaceURI) const
1157 {
1158     // Implemented according to
1159     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#isDefaultNamespaceAlgo
1160     
1161     switch (nodeType()) {
1162         case ELEMENT_NODE: {
1163             const Element *elem = static_cast<const Element *>(this);
1164             
1165             if (elem->prefix().isNull())
1166                 return elem->namespaceURI() == namespaceURI;
1167
1168             if (elem->hasAttributes()) {
1169                 NamedAttrMap *attrs = elem->attributes();
1170                 
1171                 for (unsigned i = 0; i < attrs->length(); i++) {
1172                     Attribute *attr = attrs->attributeItem(i);
1173                     
1174                     if (attr->localName() == "xmlns")
1175                         return attr->value() == namespaceURI;
1176                 }
1177             }
1178
1179             if (Element* ancestor = ancestorElement())
1180                 return ancestor->isDefaultNamespace(namespaceURI);
1181
1182             return false;
1183         }
1184         case DOCUMENT_NODE:
1185             return static_cast <const Document *>(this)->documentElement()->isDefaultNamespace(namespaceURI);
1186         case ENTITY_NODE:
1187         case NOTATION_NODE:
1188         case DOCUMENT_TYPE_NODE:
1189         case DOCUMENT_FRAGMENT_NODE:
1190             return false;
1191         case ATTRIBUTE_NODE: {
1192             const Attr *attr = static_cast<const Attr *>(this);
1193             if (attr->ownerElement())
1194                 return attr->ownerElement()->isDefaultNamespace(namespaceURI);
1195             return false;
1196         }
1197         default:
1198             if (Element* ancestor = ancestorElement())
1199                 return ancestor->isDefaultNamespace(namespaceURI);
1200             return false;
1201     }
1202 }
1203
1204 String Node::lookupPrefix(const String &namespaceURI) const
1205 {
1206     // Implemented according to
1207     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespacePrefixAlgo
1208     
1209     if (namespaceURI.isEmpty())
1210         return String();
1211     
1212     switch (nodeType()) {
1213         case ELEMENT_NODE:
1214             return lookupNamespacePrefix(namespaceURI, static_cast<const Element *>(this));
1215         case DOCUMENT_NODE:
1216             return static_cast<const Document *>(this)->documentElement()->lookupPrefix(namespaceURI);
1217         case ENTITY_NODE:
1218         case NOTATION_NODE:
1219         case DOCUMENT_FRAGMENT_NODE:
1220         case DOCUMENT_TYPE_NODE:
1221             return String();
1222         case ATTRIBUTE_NODE: {
1223             const Attr *attr = static_cast<const Attr *>(this);
1224             if (attr->ownerElement())
1225                 return attr->ownerElement()->lookupPrefix(namespaceURI);
1226             return String();
1227         }
1228         default:
1229             if (Element* ancestor = ancestorElement())
1230                 return ancestor->lookupPrefix(namespaceURI);
1231             return String();
1232     }
1233 }
1234
1235 String Node::lookupNamespaceURI(const String &prefix) const
1236 {
1237     // Implemented according to
1238     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespaceURIAlgo
1239     
1240     if (!prefix.isNull() && prefix.isEmpty())
1241         return String();
1242     
1243     switch (nodeType()) {
1244         case ELEMENT_NODE: {
1245             const Element *elem = static_cast<const Element *>(this);
1246             
1247             if (!elem->namespaceURI().isNull() && elem->prefix() == prefix)
1248                 return elem->namespaceURI();
1249             
1250             if (elem->hasAttributes()) {
1251                 NamedAttrMap *attrs = elem->attributes();
1252                 
1253                 for (unsigned i = 0; i < attrs->length(); i++) {
1254                     Attribute *attr = attrs->attributeItem(i);
1255                     
1256                     if (attr->prefix() == "xmlns" && attr->localName() == prefix) {
1257                         if (!attr->value().isEmpty())
1258                             return attr->value();
1259                         
1260                         return String();
1261                     } else if (attr->localName() == "xmlns" && prefix.isNull()) {
1262                         if (!attr->value().isEmpty())
1263                             return attr->value();
1264                         
1265                         return String();
1266                     }
1267                 }
1268             }
1269             if (Element* ancestor = ancestorElement())
1270                 return ancestor->lookupNamespaceURI(prefix);
1271             return String();
1272         }
1273         case DOCUMENT_NODE:
1274             return static_cast<const Document *>(this)->documentElement()->lookupNamespaceURI(prefix);
1275         case ENTITY_NODE:
1276         case NOTATION_NODE:
1277         case DOCUMENT_TYPE_NODE:
1278         case DOCUMENT_FRAGMENT_NODE:
1279             return String();
1280         case ATTRIBUTE_NODE: {
1281             const Attr *attr = static_cast<const Attr *>(this);
1282             
1283             if (attr->ownerElement())
1284                 return attr->ownerElement()->lookupNamespaceURI(prefix);
1285             else
1286                 return String();
1287         }
1288         default:
1289             if (Element* ancestor = ancestorElement())
1290                 return ancestor->lookupNamespaceURI(prefix);
1291             return String();
1292     }
1293 }
1294
1295 String Node::lookupNamespacePrefix(const String &_namespaceURI, const Element *originalElement) const
1296 {
1297     if (_namespaceURI.isNull())
1298         return String();
1299             
1300     if (originalElement->lookupNamespaceURI(prefix()) == _namespaceURI)
1301         return prefix();
1302     
1303     if (hasAttributes()) {
1304         NamedAttrMap *attrs = attributes();
1305         
1306         for (unsigned i = 0; i < attrs->length(); i++) {
1307             Attribute *attr = attrs->attributeItem(i);
1308             
1309             if (attr->prefix() == "xmlns" &&
1310                 attr->value() == _namespaceURI &&
1311                 originalElement->lookupNamespaceURI(attr->localName()) == _namespaceURI)
1312                 return attr->localName();
1313         }
1314     }
1315     
1316     if (Element* ancestor = ancestorElement())
1317         return ancestor->lookupNamespacePrefix(_namespaceURI, originalElement);
1318     return String();
1319 }
1320
1321 String Node::textContent(bool convertBRsToNewlines) const
1322 {
1323     switch (nodeType()) {
1324         case TEXT_NODE:
1325         case CDATA_SECTION_NODE:
1326         case COMMENT_NODE:
1327         case PROCESSING_INSTRUCTION_NODE:
1328             return nodeValue();
1329         
1330         case ELEMENT_NODE:
1331             if (hasTagName(brTag) && 
1332                 convertBRsToNewlines)
1333                 return "\n";
1334         case ATTRIBUTE_NODE:
1335         case ENTITY_NODE:
1336         case ENTITY_REFERENCE_NODE:
1337         case DOCUMENT_FRAGMENT_NODE: {
1338             String s = "";
1339         
1340             for (Node *child = firstChild(); child; child = child->nextSibling()) {
1341                 if (child->nodeType() == COMMENT_NODE || child->nodeType() == PROCESSING_INSTRUCTION_NODE)
1342                     continue;
1343             
1344                 s += child->textContent(convertBRsToNewlines);
1345             }
1346         
1347             return s;
1348         }
1349         
1350         case DOCUMENT_NODE:
1351         case DOCUMENT_TYPE_NODE:
1352         case NOTATION_NODE:
1353         default:
1354             return String();            
1355     }
1356 }
1357
1358 void Node::setTextContent(const String &text, ExceptionCode& ec)
1359 {           
1360     switch (nodeType()) {
1361         case TEXT_NODE:
1362         case CDATA_SECTION_NODE:
1363         case COMMENT_NODE:
1364         case PROCESSING_INSTRUCTION_NODE:
1365             setNodeValue(text, ec);
1366             break;
1367         case ELEMENT_NODE:
1368         case ATTRIBUTE_NODE:
1369         case ENTITY_NODE:
1370         case ENTITY_REFERENCE_NODE:
1371         case DOCUMENT_FRAGMENT_NODE: {
1372             ContainerNode *container = static_cast<ContainerNode *>(this);
1373             
1374             container->removeChildren();
1375             
1376             if (!text.isEmpty())
1377                 appendChild(document()->createTextNode(text), ec);
1378             break;
1379         }
1380         case DOCUMENT_NODE:
1381         case DOCUMENT_TYPE_NODE:
1382         case NOTATION_NODE:
1383         default:
1384             // Do nothing
1385             break;
1386     }
1387 }
1388
1389 Element* Node::ancestorElement() const
1390 {
1391     // In theory, there can be EntityReference nodes between elements, but this is currently not supported.
1392     for (Node* n = parentNode(); n; n = n->parentNode()) {
1393         if (n->isElementNode())
1394             return static_cast<Element*>(n);
1395     }
1396     return 0;
1397 }
1398
1399 bool Node::offsetInCharacters() const
1400 {
1401     return false;
1402 }
1403
1404 #ifndef NDEBUG
1405
1406 static void appendAttributeDesc(const Node *node, String &string, const QualifiedName& name, DeprecatedString attrDesc)
1407 {
1408     if (node->isElementNode()) {
1409         String attr = static_cast<const Element *>(node)->getAttribute(name);
1410         if (!attr.isEmpty()) {
1411             string += attrDesc;
1412             string += attr;
1413         }
1414     }
1415 }
1416
1417 void Node::showNode(const char* prefix) const
1418 {
1419     if (!prefix)
1420         prefix = "";
1421     if (isTextNode()) {
1422         DeprecatedString value = nodeValue().deprecatedString();
1423         value.replace('\\', "\\\\");
1424         value.replace('\n', "\\n");
1425         fprintf(stderr, "%s%s\t%p \"%s\"\n", prefix, nodeName().deprecatedString().utf8().data(), this, value.utf8().data());
1426     } else {
1427         String attrs = "";
1428         appendAttributeDesc(this, attrs, classAttr, " CLASS=");
1429         appendAttributeDesc(this, attrs, styleAttr, " STYLE=");
1430         fprintf(stderr, "%s%s\t%p%s\n", prefix, nodeName().deprecatedString().utf8().data(), this, attrs.deprecatedString().ascii());
1431     }
1432 }
1433
1434 void Node::showTreeForThis() const
1435 {
1436     showTreeAndMark(this, "*");
1437 }
1438
1439 void Node::showTreeAndMark(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char * markedLabel2) const
1440 {
1441     const Node* rootNode;
1442     const Node* node = this;
1443     while (node->parentNode() && !node->hasTagName(bodyTag))
1444         node = node->parentNode();
1445     rootNode = node;
1446         
1447     for (node = rootNode; node; node = node->traverseNextNode()) {
1448         if (node == markedNode1)
1449             fprintf(stderr, "%s", markedLabel1);
1450         if (node == markedNode2)
1451             fprintf(stderr, "%s", markedLabel2);
1452                         
1453         for (const Node* tmpNode = node; tmpNode && tmpNode != rootNode; tmpNode = tmpNode->parentNode())
1454             fprintf(stderr, "\t");
1455         node->showNode();
1456     }
1457 }
1458
1459 void Node::formatForDebugger(char *buffer, unsigned length) const
1460 {
1461     String result;
1462     String s;
1463     
1464     s = nodeName();
1465     if (s.length() == 0)
1466         result += "<none>";
1467     else
1468         result += s;
1469           
1470     strncpy(buffer, result.deprecatedString().latin1(), length - 1);
1471 }
1472
1473 #endif
1474
1475 }
1476
1477 #ifndef NDEBUG
1478
1479 void showTree(const WebCore::Node* node)
1480 {
1481     if (node)
1482         node->showTreeForThis();
1483 }
1484
1485 #endif