Reviewed by darin
[WebKit-https.git] / WebCore / dom / Document.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 "Document.h"
27
28 #include "AXObjectCache.h"
29 #include "CDATASection.h"
30 #include "CSSStyleSheet.h"
31 #include "CSSValueKeywords.h"
32 #include "Comment.h"
33 #include "DOMImplementation.h"
34 #include "Decoder.h"
35 #include "DocLoader.h"
36 #include "DocumentFragment.h"
37 #include "DocumentType.h"
38 #include "EditingText.h"
39 #include "EntityReference.h"
40 #include "Event.h"
41 #include "EventListener.h"
42 #include "EventNames.h"
43 #include "ExceptionCode.h"
44 #include "Frame.h"
45 #include "FrameTree.h"
46 #include "HTMLBodyElement.h"
47 #include "HTMLDocument.h"
48 #include "HTMLElementFactory.h"
49 #include "HTMLImageLoader.h"
50 #include "HTMLInputElement.h"
51 #include "HTMLLinkElement.h"
52 #include "HTMLMapElement.h"
53 #include "HTMLNameCollection.h"
54 #include "HTMLNames.h"
55 #include "HTMLStyleElement.h"
56 #include "JSEditor.h"
57 #include "KeyboardEvent.h"
58 #include "Logging.h"
59 #include "MouseEvent.h"
60 #include "MouseEventWithHitTestResults.h"
61 #include "MutationEvent.h"
62 #include "NameNodeList.h"
63 #include "NodeFilter.h"
64 #include "NodeIterator.h"
65 #include "PlatformKeyboardEvent.h"
66 #include "ProcessingInstruction.h"
67 #include "RegisteredEventListener.h"
68 #include "RegularExpression.h"
69 #include "RenderArena.h"
70 #include "RenderView.h"
71 #include "RenderWidget.h"
72 #include "SegmentedString.h"
73 #include "SelectionController.h"
74 #include "StringHash.h"
75 #include "StyleSheetList.h"
76 #include "SystemTime.h"
77 #include "TextIterator.h"
78 #include "TreeWalker.h"
79 #include "UIEvent.h"
80 #include "csshelper.h"
81 #include "cssstyleselector.h"
82 #include "kjs_binding.h"
83 #include "kjs_proxy.h"
84 #include "XMLTokenizer.h"
85 #include "xmlhttprequest.h"
86
87 #if XPATH_SUPPORT
88 #include "XPathEvaluator.h"
89 #include "XPathExpression.h"
90 #include "XPathNSResolver.h"
91 #include "XPathResult.h"
92 #endif
93
94 #ifdef KHTML_XSLT
95 #include "XSLTProcessor.h"
96 #endif
97
98 #ifndef KHTML_NO_XBL
99 #include "xbl_binding_manager.h"
100 using XBL::XBLBindingManager;
101 #endif
102
103 #if SVG_SUPPORT
104 #include "SVGDocumentExtensions.h"
105 #include "SVGElementFactory.h"
106 #include "SVGZoomEvent.h"
107 #include "SVGStyleElement.h"
108 #include "KSVGTimeScheduler.h"
109 #endif
110
111 using namespace std;
112
113 namespace WebCore {
114
115 using namespace EventNames;
116 using namespace HTMLNames;
117
118 // #define INSTRUMENT_LAYOUT_SCHEDULING 1
119
120 // This amount of time must have elapsed before we will even consider scheduling a layout without a delay.
121 // FIXME: For faster machines this value can really be lowered to 200.  250 is adequate, but a little high
122 // for dual G5s. :)
123 const int cLayoutScheduleThreshold = 250;
124
125 // Use 1 to represent the document's default form.
126 HTMLFormElement* const defaultForm = (HTMLFormElement*) 1;
127
128 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
129 static const unsigned PHI = 0x9e3779b9U;
130
131 // DOM Level 2 says (letters added):
132 //
133 // a) Name start characters must have one of the categories Ll, Lu, Lo, Lt, Nl.
134 // b) Name characters other than Name-start characters must have one of the categories Mc, Me, Mn, Lm, or Nd.
135 // c) Characters in the compatibility area (i.e. with character code greater than #xF900 and less than #xFFFE) are not allowed in XML names.
136 // d) Characters which have a font or compatibility decomposition (i.e. those with a "compatibility formatting tag" in field 5 of the database -- marked by field 5 beginning with a "<") are not allowed.
137 // e) The following characters are treated as name-start characters rather than name characters, because the property file classifies them as Alphabetic: [#x02BB-#x02C1], #x0559, #x06E5, #x06E6.
138 // f) Characters #x20DD-#x20E0 are excluded (in accordance with Unicode, section 5.14).
139 // g) Character #x00B7 is classified as an extender, because the property list so identifies it.
140 // h) Character #x0387 is added as a name character, because #x00B7 is its canonical equivalent.
141 // i) Characters ':' and '_' are allowed as name-start characters.
142 // j) Characters '-' and '.' are allowed as name characters.
143 //
144 // It also contains complete tables. If we decide it's better, we could include those instead of the following code.
145
146 static inline bool isValidNameStart(UChar32 c)
147 {
148     // rule (e) above
149     if ((c >= 0x02BB && c <= 0x02C1) || c == 0x559 || c == 0x6E5 || c == 0x6E6)
150         return true;
151
152     // rule (i) above
153     if (c == ':' || c == '_')
154         return true;
155
156     // rules (a) and (f) above
157     const uint32_t nameStartMask = U_GC_LL_MASK | U_GC_LU_MASK | U_GC_LO_MASK | U_GC_LT_MASK | U_GC_NL_MASK;
158     if (!(U_GET_GC_MASK(c) & nameStartMask))
159         return false;
160
161     // rule (c) above
162     if (c >= 0xF900 && c < 0xFFFE)
163         return false;
164
165     // rule (d) above
166     UDecompositionType decompType = static_cast<UDecompositionType>(u_getIntPropertyValue(c, UCHAR_DECOMPOSITION_TYPE));
167     if (decompType == U_DT_FONT || decompType == U_DT_COMPAT)
168         return false;
169
170     return true;
171 }
172
173 static inline bool isValidNamePart(UChar32 c)
174 {
175     // rules (a), (e), and (i) above
176     if (isValidNameStart(c))
177         return true;
178
179     // rules (g) and (h) above
180     if (c == 0x00B7 || c == 0x0387)
181         return true;
182
183     // rule (j) above
184     if (c == '-' || c == '.')
185         return true;
186
187     // rules (b) and (f) above
188     const uint32_t otherNamePartMask = U_GC_MC_MASK | U_GC_ME_MASK | U_GC_MN_MASK | U_GC_LM_MASK | U_GC_ND_MASK;
189     if (!(U_GET_GC_MASK(c) & otherNamePartMask))
190         return false;
191
192     // rule (c) above
193     if (c >= 0xF900 && c < 0xFFFE)
194         return false;
195
196     // rule (d) above
197     UDecompositionType decompType = static_cast<UDecompositionType>(u_getIntPropertyValue(c, UCHAR_DECOMPOSITION_TYPE));
198     if (decompType == U_DT_FONT || decompType == U_DT_COMPAT)
199         return false;
200
201     return true;
202 }
203
204 DeprecatedPtrList<Document> * Document::changedDocuments = 0;
205
206 // FrameView might be 0
207 Document::Document(DOMImplementation* impl, FrameView *v)
208     : ContainerNode(0)
209     , m_implementation(impl)
210     , m_domtree_version(0)
211     , m_styleSheets(new StyleSheetList)
212     , m_title("")
213     , m_titleSetExplicitly(false)
214     , m_imageLoadEventTimer(this, &Document::imageLoadEventTimerFired)
215 #if !KHTML_NO_XBL
216     , m_bindingManager(new XBLBindingManager(this))
217 #endif
218 #ifdef KHTML_XSLT
219     , m_transformSource(0)
220 #endif
221     , m_savedRenderer(0)
222     , m_passwordFields(0)
223     , m_secureForms(0)
224     , m_designMode(inherit)
225     , m_selfOnlyRefCount(0)
226 #if SVG_SUPPORT
227     , m_svgExtensions(0)
228 #endif
229 #if __APPLE__
230     , m_hasDashboardRegions(false)
231     , m_dashboardRegionsDirty(false)
232 #endif
233     , m_accessKeyMapValid(false)
234     , m_createRenderers(true)
235     , m_inPageCache(false)
236 {
237     m_document.resetSkippingRef(this);
238
239     m_printing = false;
240
241     m_view = v;
242     m_renderArena = 0;
243
244     m_axObjectCache = 0;
245     
246     m_docLoader = new DocLoader(v ? v->frame() : 0, this);
247
248     visuallyOrdered = false;
249     m_loadingSheet = false;
250     m_bParsing = false;
251     m_docChanged = false;
252     m_tokenizer = 0;
253
254     pMode = Strict;
255     hMode = XHtml;
256     m_textColor = Color::black;
257     m_listenerTypes = 0;
258     m_inDocument = true;
259     m_styleSelectorDirty = false;
260     m_inStyleRecalc = false;
261     m_closeAfterStyleRecalc = false;
262     m_usesDescendantRules = false;
263     m_usesSiblingRules = false;
264
265     m_styleSelector = new CSSStyleSelector(this, m_usersheet, m_styleSheets.get(), !inCompatMode());
266     m_pendingStylesheets = 0;
267     m_ignorePendingStylesheets = false;
268
269     m_cssTarget = 0;
270
271     resetLinkColor();
272     resetVisitedLinkColor();
273     resetActiveLinkColor();
274
275     m_processingLoadEvent = false;
276     m_startTime = currentTime();
277     m_overMinimumLayoutThreshold = false;
278     
279     m_jsEditor = 0;
280
281     static int docID = 0;
282     m_docID = docID++;
283 }
284
285 void Document::removedLastRef()
286 {
287     if (m_selfOnlyRefCount) {
288         // if removing a child removes the last self-only ref, we don't
289         // want the document to be destructed until after
290         // removeAllChildren returns, so we guard ourselves with an
291         // extra self-only ref
292
293         DocPtr<Document> guard(this);
294
295         // we must make sure not to be retaining any of our children through
296         // these extra pointers or we will create a reference cycle
297         m_docType = 0;
298         m_focusNode = 0;
299         m_hoverNode = 0;
300         m_activeNode = 0;
301         m_titleElement = 0;
302         m_documentElement = 0;
303
304         removeAllChildren();
305
306         deleteAllValues(m_markers);
307         m_markers.clear();
308
309         delete m_tokenizer;
310         m_tokenizer = 0;
311     } else
312         delete this;
313 }
314
315 Document::~Document()
316 {
317     assert(!renderer());
318     assert(!m_inPageCache);
319     assert(m_savedRenderer == 0);
320
321 #if SVG_SUPPORT
322     delete m_svgExtensions;
323 #endif
324
325     XMLHttpRequest::detachRequests(this);
326     KJS::ScriptInterpreter::forgetAllDOMNodesForDocument(this);
327
328     if (m_docChanged && changedDocuments)
329         changedDocuments->remove(this);
330     delete m_tokenizer;
331     m_document.resetSkippingRef(0);
332     delete m_styleSelector;
333     delete m_docLoader;
334     
335     if (m_renderArena) {
336         delete m_renderArena;
337         m_renderArena = 0;
338     }
339
340 #ifdef KHTML_XSLT
341     xmlFreeDoc((xmlDocPtr)m_transformSource);
342 #endif
343
344 #ifndef KHTML_NO_XBL
345     delete m_bindingManager;
346 #endif
347
348     deleteAllValues(m_markers);
349
350     if (m_axObjectCache) {
351         delete m_axObjectCache;
352         m_axObjectCache = 0;
353     }
354     m_decoder = 0;
355     
356     if (m_jsEditor) {
357         delete m_jsEditor;
358         m_jsEditor = 0;
359     }
360     
361     deleteAllValues(m_selectedRadioButtons);
362 }
363
364 void Document::resetLinkColor()
365 {
366     m_linkColor = Color(0, 0, 238);
367 }
368
369 void Document::resetVisitedLinkColor()
370 {
371     m_visitedLinkColor = Color(85, 26, 139);    
372 }
373
374 void Document::resetActiveLinkColor()
375 {
376     m_activeLinkColor.setNamedColor("red");
377 }
378
379 void Document::setDocType(PassRefPtr<DocumentType> docType)
380 {
381     m_docType = docType;
382 }
383
384 DocumentType *Document::doctype() const
385 {
386     return m_docType.get();
387 }
388
389 DOMImplementation* Document::implementation() const
390 {
391     return m_implementation.get();
392 }
393
394 void Document::childrenChanged()
395 {
396     // invalidate the document element we have cached in case it was replaced
397     m_documentElement = 0;
398 }
399
400 Element* Document::documentElement() const
401 {
402     if (!m_documentElement) {
403         Node* n = firstChild();
404         while (n && !n->isElementNode())
405             n = n->nextSibling();
406         m_documentElement = static_cast<Element*>(n);
407     }
408
409     return m_documentElement.get();
410 }
411
412 PassRefPtr<Element> Document::createElement(const String &name, ExceptionCode& ec)
413 {
414     return createElementNS(nullAtom, name, ec);
415 }
416
417 PassRefPtr<DocumentFragment> Document::createDocumentFragment()
418 {
419     return new DocumentFragment(document());
420 }
421
422 PassRefPtr<Text> Document::createTextNode(const String &data)
423 {
424     return new Text(this, data);
425 }
426
427 PassRefPtr<Comment> Document::createComment (const String &data)
428 {
429     return new Comment(this, data);
430 }
431
432 PassRefPtr<CDATASection> Document::createCDATASection(const String &data, ExceptionCode& ec)
433 {
434     if (isHTMLDocument()) {
435         ec = NOT_SUPPORTED_ERR;
436         return 0;
437     }
438     return new CDATASection(this, data);
439 }
440
441 PassRefPtr<ProcessingInstruction> Document::createProcessingInstruction(const String &target, const String &data, ExceptionCode& ec)
442 {
443     if (!isValidName(target)) {
444         ec = INVALID_CHARACTER_ERR;
445         return 0;
446     }
447     if (isHTMLDocument()) {
448         ec = NOT_SUPPORTED_ERR;
449         return 0;
450     }
451     return new ProcessingInstruction(this, target, data);
452 }
453
454 PassRefPtr<EntityReference> Document::createEntityReference(const String &name, ExceptionCode& ec)
455 {
456     if (!isValidName(name)) {
457         ec = INVALID_CHARACTER_ERR;
458         return 0;
459     }
460     if (isHTMLDocument()) {
461         ec = NOT_SUPPORTED_ERR;
462         return 0;
463     }
464     return new EntityReference(this, name.impl());
465 }
466
467 PassRefPtr<EditingText> Document::createEditingTextNode(const String &text)
468 {
469     return new EditingText(this, text);
470 }
471
472 PassRefPtr<CSSStyleDeclaration> Document::createCSSStyleDeclaration()
473 {
474     return new CSSMutableStyleDeclaration;
475 }
476
477 PassRefPtr<Node> Document::importNode(Node* importedNode, bool deep, ExceptionCode& ec)
478 {
479     ec = 0;
480     
481     if (!importedNode) {
482         ec = NOT_SUPPORTED_ERR;
483         return 0;
484     }
485
486     switch (importedNode->nodeType()) {
487         case TEXT_NODE:
488             return createTextNode(importedNode->nodeValue());
489         case CDATA_SECTION_NODE:
490             return createCDATASection(importedNode->nodeValue(), ec);
491         case ENTITY_REFERENCE_NODE:
492             return createEntityReference(importedNode->nodeName(), ec);
493         case PROCESSING_INSTRUCTION_NODE:
494             return createProcessingInstruction(importedNode->nodeName(), importedNode->nodeValue(), ec);
495         case COMMENT_NODE:
496             return createComment(importedNode->nodeValue());
497         case ELEMENT_NODE: {
498             Element *oldElement = static_cast<Element *>(importedNode);
499             RefPtr<Element> newElement = createElementNS(oldElement->namespaceURI(), oldElement->tagQName().toString(), ec);
500                         
501             if (ec != 0)
502                 return 0;
503
504             NamedAttrMap* attrs = oldElement->attributes(true);
505             if (attrs) {
506                 unsigned length = attrs->length();
507                 for (unsigned i = 0; i < length; i++) {
508                     Attribute* attr = attrs->attributeItem(i);
509                     newElement->setAttribute(attr->name(), attr->value().impl(), ec);
510                     if (ec != 0)
511                         return 0;
512                 }
513             }
514
515             newElement->copyNonAttributeProperties(oldElement);
516
517             if (deep) {
518                 for (Node* oldChild = oldElement->firstChild(); oldChild; oldChild = oldChild->nextSibling()) {
519                     RefPtr<Node> newChild = importNode(oldChild, true, ec);
520                     if (ec != 0)
521                         return 0;
522                     newElement->appendChild(newChild.release(), ec);
523                     if (ec != 0)
524                         return 0;
525                 }
526             }
527
528             return newElement.release();
529         }
530         case ATTRIBUTE_NODE:
531         case ENTITY_NODE:
532         case DOCUMENT_NODE:
533         case DOCUMENT_TYPE_NODE:
534         case DOCUMENT_FRAGMENT_NODE:
535         case NOTATION_NODE:
536         case XPATH_NAMESPACE_NODE:
537             break;
538     }
539
540     ec = NOT_SUPPORTED_ERR;
541     return 0;
542 }
543
544
545 PassRefPtr<Node> Document::adoptNode(PassRefPtr<Node> source, ExceptionCode& ec)
546 {
547     if (!source) {
548         ec = NOT_SUPPORTED_ERR;
549         return 0;
550     }
551     
552     switch (source->nodeType()) {
553         case ENTITY_NODE:
554         case NOTATION_NODE:
555         case DOCUMENT_NODE:
556         case DOCUMENT_TYPE_NODE:
557         case XPATH_NAMESPACE_NODE:
558             ec = NOT_SUPPORTED_ERR;
559             return 0;            
560         case ATTRIBUTE_NODE: {                   
561             Attr* attr = static_cast<Attr*>(source.get());
562             if (attr->ownerElement())
563                 attr->ownerElement()->removeAttributeNode(attr, ec);
564             attr->m_specified = true;
565             break;
566         }       
567         default:
568             if (source->parentNode())
569                 source->parentNode()->removeChild(source.get(), ec);
570     }
571                 
572     for (Node* node = source.get(); node; node = node->traverseNextNode(source.get())) {
573         KJS::ScriptInterpreter::updateDOMNodeDocument(node, node->document(), this);
574         node->setDocument(this);
575     }
576
577     return source;
578 }
579
580 PassRefPtr<Element> Document::createElementNS(const String &_namespaceURI, const String &qualifiedName, ExceptionCode& ec)
581 {
582     // FIXME: We'd like a faster code path that skips this check for calls from inside the engine where the name is known to be valid.
583     String prefix, localName;
584     if (!parseQualifiedName(qualifiedName, prefix, localName)) {
585         ec = INVALID_CHARACTER_ERR;
586         return 0;
587     }
588
589     RefPtr<Element> e;
590     QualifiedName qName = QualifiedName(AtomicString(prefix), AtomicString(localName), AtomicString(_namespaceURI));
591     
592     // FIXME: Use registered namespaces and look up in a hash to find the right factory.
593     if (_namespaceURI == xhtmlNamespaceURI) {
594         e = HTMLElementFactory::createHTMLElement(qName.localName(), this, 0, false);
595         if (e && !prefix.isNull()) {
596             e->setPrefix(qName.prefix(), ec);
597             if (ec)
598                 return 0;
599         }
600     }
601 #if SVG_SUPPORT
602     else if (_namespaceURI == SVGNames::svgNamespaceURI)
603         e = SVGElementFactory::createSVGElement(qName, this, false);
604 #endif
605     
606     if (!e)
607         e = new Element(qName, document());
608     
609     return e.release();
610 }
611
612 Element *Document::getElementById(const AtomicString& elementId) const
613 {
614     if (elementId.length() == 0)
615         return 0;
616
617     Element *element = m_elementsById.get(elementId.impl());
618     if (element)
619         return element;
620         
621     if (m_duplicateIds.contains(elementId.impl())) {
622         for (Node *n = traverseNextNode(); n != 0; n = n->traverseNextNode()) {
623             if (n->isElementNode()) {
624                 element = static_cast<Element*>(n);
625                 if (element->hasID() && element->getAttribute(idAttr) == elementId) {
626                     m_duplicateIds.remove(elementId.impl());
627                     m_elementsById.set(elementId.impl(), element);
628                     return element;
629                 }
630             }
631         }
632     }
633     return 0;
634 }
635
636 String Document::readyState() const
637 {
638     if (Frame* f = frame()) {
639         if (f->isComplete()) 
640             return "complete";
641         if (parsing()) 
642             return "loading";
643       return "loaded";
644       // FIXME: What does "interactive" mean?
645       // FIXME: Missing support for "uninitialized".
646     }
647     return String();
648 }
649
650 String Document::inputEncoding() const
651 {
652     if (Decoder* d = decoder())
653         return d->encodingName();
654     return String();
655 }
656
657 String Document::defaultCharset() const
658 {
659     if (Frame* f = frame())
660         return f->settings()->encoding();
661     return String();
662 }
663
664 void Document::setCharset(const String& charset)
665 {
666     if (!decoder())
667         return;
668     decoder()->setEncodingName(charset.deprecatedString().ascii(), Decoder::UserChosenEncoding);
669 }
670
671 Element* Document::elementFromPoint(int x, int y) const
672 {
673     if (!renderer())
674         return 0;
675
676     RenderObject::NodeInfo nodeInfo(true, true);
677     renderer()->layer()->hitTest(nodeInfo, IntPoint(x, y)); 
678
679     Node* n = nodeInfo.innerNode();
680     while (n && !n->isElementNode())
681         n = n->parentNode();
682     if (n)
683         n = n->shadowAncestorNode();
684     return static_cast<Element*>(n);
685 }
686
687 void Document::addElementById(const AtomicString& elementId, Element* element)
688 {
689     if (!m_elementsById.contains(elementId.impl()))
690         m_elementsById.set(elementId.impl(), element);
691     else
692         m_duplicateIds.add(elementId.impl());
693 }
694
695 void Document::removeElementById(const AtomicString& elementId, Element* element)
696 {
697     if (m_elementsById.get(elementId.impl()) == element)
698         m_elementsById.remove(elementId.impl());
699     else
700         m_duplicateIds.remove(elementId.impl());
701 }
702
703 Element* Document::getElementByAccessKey(const String& key) const
704 {
705     if (key.isEmpty())
706         return 0;
707     if (!m_accessKeyMapValid) {
708         for (Node* n = firstChild(); n; n = n->traverseNextNode()) {
709             if (!n->isElementNode())
710                 continue;
711             Element* element = static_cast<Element*>(n);
712             const AtomicString& accessKey = element->getAttribute(accesskeyAttr);
713             if (!accessKey.isEmpty())
714                 m_elementsByAccessKey.set(accessKey.impl(), element);
715         }
716         m_accessKeyMapValid = true;
717     }
718     return m_elementsByAccessKey.get(key.impl());
719 }
720
721 void Document::updateTitle()
722 {
723     if (Frame* f = frame())
724         f->setTitle(m_title);
725 }
726
727 void Document::setTitle(const String& title, Node* titleElement)
728 {
729     if (!titleElement) {
730         // Title set by JavaScript -- overrides any title elements.
731         m_titleSetExplicitly = true;
732         m_titleElement = 0;
733     } else if (titleElement != m_titleElement) {
734         if (m_titleElement)
735             // Only allow the first title element to change the title -- others have no effect.
736             return;
737         m_titleElement = titleElement;
738     }
739
740     if (m_title == title)
741         return;
742
743     m_title = title;
744     updateTitle();
745 }
746
747 void Document::removeTitle(Node* titleElement)
748 {
749     if (m_titleElement != titleElement)
750         return;
751
752     // FIXME: Ideally we might want this to search for the first remaining title element, and use it.
753     m_titleElement = 0;
754
755     if (!m_title.isEmpty()) {
756         m_title = "";
757         updateTitle();
758     }
759 }
760
761 String Document::nodeName() const
762 {
763     return "#document";
764 }
765
766 Node::NodeType Document::nodeType() const
767 {
768     return DOCUMENT_NODE;
769 }
770
771 Frame* Document::frame() const 
772 {
773     return m_view ? m_view->frame() : 0; 
774 }
775
776 PassRefPtr<Range> Document::createRange()
777 {
778     return new Range(this);
779 }
780
781 PassRefPtr<NodeIterator> Document::createNodeIterator(Node* root, unsigned whatToShow, 
782     PassRefPtr<NodeFilter> filter, bool expandEntityReferences, ExceptionCode& ec)
783 {
784     if (!root) {
785         ec = NOT_SUPPORTED_ERR;
786         return 0;
787     }
788     return new NodeIterator(root, whatToShow, filter, expandEntityReferences);
789 }
790
791 PassRefPtr<TreeWalker> Document::createTreeWalker(Node *root, unsigned whatToShow, 
792     PassRefPtr<NodeFilter> filter, bool expandEntityReferences, ExceptionCode& ec)
793 {
794     if (!root) {
795         ec = NOT_SUPPORTED_ERR;
796         return 0;
797     }
798     return new TreeWalker(root, whatToShow, filter, expandEntityReferences);
799 }
800
801 void Document::setDocumentChanged(bool b)
802 {
803     if (b) {
804         if (!m_docChanged) {
805             if (!changedDocuments)
806                 changedDocuments = new DeprecatedPtrList<Document>;
807             changedDocuments->append(this);
808         }
809         if (m_accessKeyMapValid) {
810             m_accessKeyMapValid = false;
811             m_elementsByAccessKey.clear();
812         }
813     } else {
814         if (m_docChanged && changedDocuments)
815             changedDocuments->remove(this);
816     }
817
818     m_docChanged = b;
819 }
820
821 void Document::recalcStyle(StyleChange change)
822 {
823     if (m_inStyleRecalc)
824         return; // Guard against re-entrancy. -dwh
825         
826     m_inStyleRecalc = true;
827     
828     ASSERT(!renderer() || renderArena());
829     if (!renderer() || !renderArena())
830         goto bail_out;
831
832     if (change == Force) {
833         RenderStyle* oldStyle = renderer()->style();
834         if (oldStyle)
835             oldStyle->ref();
836         RenderStyle* _style = new (m_renderArena) RenderStyle();
837         _style->ref();
838         _style->setDisplay(BLOCK);
839         _style->setVisuallyOrdered(visuallyOrdered);
840         // ### make the font stuff _really_ work!!!!
841
842         FontDescription fontDescription;
843         fontDescription.setUsePrinterFont(printing());
844         if (m_view) {
845             const Settings *settings = m_view->frame()->settings();
846             if (printing() && !settings->shouldPrintBackgrounds())
847                 _style->setForceBackgroundsToWhite(true);
848             const AtomicString& stdfont = settings->stdFontName();
849             if (!stdfont.isEmpty()) {
850                 fontDescription.firstFamily().setFamily(stdfont);
851                 fontDescription.firstFamily().appendFamily(0);
852             }
853             m_styleSelector->setFontSize(fontDescription, m_styleSelector->fontSizeForKeyword(CSS_VAL_MEDIUM, inCompatMode()));
854         }
855
856         _style->setFontDescription(fontDescription);
857         _style->font().update();
858         if (inCompatMode())
859             _style->setHtmlHacks(true); // enable html specific rendering tricks
860
861         StyleChange ch = diff(_style, oldStyle);
862         if (renderer() && ch != NoChange)
863             renderer()->setStyle(_style);
864         if (change != Force)
865             change = ch;
866
867         _style->deref(m_renderArena);
868         if (oldStyle)
869             oldStyle->deref(m_renderArena);
870     }
871
872     for (Node* n = fastFirstChild(); n; n = n->nextSibling())
873         if (change >= Inherit || n->hasChangedChild() || n->changed())
874             n->recalcStyle(change);
875
876     if (changed() && m_view)
877         m_view->layout();
878
879 bail_out:
880     setChanged(false);
881     setHasChangedChild(false);
882     setDocumentChanged(false);
883     
884     m_inStyleRecalc = false;
885     
886     // If we wanted to emit the implicitClose() during recalcStyle, do so now that we're finished.
887     if (m_closeAfterStyleRecalc) {
888         m_closeAfterStyleRecalc = false;
889         implicitClose();
890     }
891 }
892
893 void Document::updateRendering()
894 {
895     if (hasChangedChild())
896         recalcStyle(NoChange);
897 }
898
899 void Document::updateDocumentsRendering()
900 {
901     if (!changedDocuments)
902         return;
903
904     while (Document* doc = changedDocuments->take()) {
905         doc->m_docChanged = false;
906         doc->updateRendering();
907     }
908 }
909
910 void Document::updateLayout()
911 {
912     // FIXME: Dave Hyatt's pretty sure we can remove this because layout calls recalcStyle as needed.
913     updateRendering();
914
915     // Only do a layout if changes have occurred that make it necessary.      
916     if (m_view && renderer() && (m_view->layoutPending() || renderer()->needsLayout()))
917         m_view->layout();
918 }
919
920 // FIXME: This is a bad idea and needs to be removed eventually.
921 // Other browsers load stylesheets before they continue parsing the web page.
922 // Since we don't, we can run JavaScript code that needs answers before the
923 // stylesheets are loaded. Doing a layout ignoring the pending stylesheets
924 // lets us get reasonable answers. The long term solution to this problem is
925 // to instead suspend JavaScript execution.
926 void Document::updateLayoutIgnorePendingStylesheets()
927 {
928     bool oldIgnore = m_ignorePendingStylesheets;
929     
930     if (!haveStylesheetsLoaded()) {
931         m_ignorePendingStylesheets = true;
932         updateStyleSelector();    
933     }
934
935     updateLayout();
936
937     m_ignorePendingStylesheets = oldIgnore;
938 }
939
940 void Document::attach()
941 {
942     assert(!attached());
943     assert(!m_inPageCache);
944
945     if (!m_renderArena)
946         m_renderArena = new RenderArena();
947     
948     // Create the rendering tree
949     setRenderer(new (m_renderArena) RenderView(this, m_view));
950
951     recalcStyle(Force);
952
953     RenderObject* render = renderer();
954     setRenderer(0);
955
956     ContainerNode::attach();
957
958     setRenderer(render);
959 }
960
961 void Document::detach()
962 {
963     RenderObject* render = renderer();
964
965     // indicate destruction mode,  i.e. attached() but renderer == 0
966     setRenderer(0);
967     
968     if (m_inPageCache) {
969         if (render)
970             axObjectCache()->remove(render);
971         return;
972     }
973
974     // Empty out these lists as a performance optimization, since detaching
975     // all the individual render objects will cause all the RenderImage
976     // objects to remove themselves from the lists.
977     m_imageLoadEventDispatchSoonList.clear();
978     m_imageLoadEventDispatchingList.clear();
979     
980     m_hoverNode = 0;
981     m_focusNode = 0;
982     m_activeNode = 0;
983
984     ContainerNode::detach();
985
986     if (render)
987         render->destroy();
988
989     m_view = 0;
990     
991     if (m_renderArena) {
992         delete m_renderArena;
993         m_renderArena = 0;
994     }
995 }
996
997 void Document::removeAllEventListenersFromAllNodes()
998 {
999     m_windowEventListeners.clear();
1000     removeAllDisconnectedNodeEventListeners();
1001     for (Node *n = this; n; n = n->traverseNextNode()) {
1002         if (!n->isEventTargetNode())
1003             continue;
1004         EventTargetNodeCast(n)->removeAllEventListeners();
1005     }
1006 }
1007
1008 void Document::registerDisconnectedNodeWithEventListeners(Node* node)
1009 {
1010     m_disconnectedNodesWithEventListeners.add(node);
1011 }
1012
1013 void Document::unregisterDisconnectedNodeWithEventListeners(Node* node)
1014 {
1015     m_disconnectedNodesWithEventListeners.remove(node);
1016 }
1017
1018 void Document::removeAllDisconnectedNodeEventListeners()
1019 {
1020     HashSet<Node*>::iterator end = m_disconnectedNodesWithEventListeners.end();
1021     for (HashSet<Node*>::iterator i = m_disconnectedNodesWithEventListeners.begin(); i != end; ++i)
1022         EventTargetNodeCast(*i)->removeAllEventListeners();
1023     m_disconnectedNodesWithEventListeners.clear();
1024 }
1025
1026 AXObjectCache* Document::axObjectCache() const
1027 {
1028     // The only document that actually has a AXObjectCache is the top-level
1029     // document.  This is because we need to be able to get from any WebCoreAXObject
1030     // to any other WebCoreAXObject on the same page.  Using a single cache allows
1031     // lookups across nested webareas (i.e. multiple documents).
1032     
1033     if (m_axObjectCache) {
1034         // return already known top-level cache
1035         if (!ownerElement())
1036             return m_axObjectCache;
1037         
1038         // In some pages with frames, the cache is created before the sub-webarea is
1039         // inserted into the tree.  Here, we catch that case and just toss the old
1040         // cache and start over.
1041         delete m_axObjectCache;
1042         m_axObjectCache = 0;
1043     }
1044
1045     // ask the top-level document for its cache
1046     Document* doc = topDocument();
1047     if (doc != this)
1048         return doc->axObjectCache();
1049     
1050     // this is the top-level document, so install a new cache
1051     m_axObjectCache = new AXObjectCache;
1052     return m_axObjectCache;
1053 }
1054
1055 void Document::setVisuallyOrdered()
1056 {
1057     visuallyOrdered = true;
1058     if (renderer())
1059         renderer()->style()->setVisuallyOrdered(true);
1060 }
1061
1062 void Document::updateSelection()
1063 {
1064     if (!renderer())
1065         return;
1066     
1067     RenderView *canvas = static_cast<RenderView*>(renderer());
1068     SelectionController s = frame()->selection();
1069         
1070     if (!s.isRange())
1071         canvas->clearSelection();
1072     else {
1073         // Use the rightmost candidate for the start of the selection, and the leftmost candidate for the end of the selection.
1074         // Example: foo <a>bar</a>.  Imagine that a line wrap occurs after 'foo', and that 'bar' is selected.   If we pass [foo, 3]
1075         // as the start of the selection, the selection painting code will think that content on the line containing 'foo' is selected
1076         // and will fill the gap before 'bar'.
1077         Position startPos = s.selection().visibleStart().deepEquivalent();
1078         if (startPos.downstream().inRenderedContent())
1079             startPos = startPos.downstream();
1080         Position endPos = s.selection().visibleEnd().deepEquivalent();
1081         if (endPos.upstream().inRenderedContent())
1082             endPos = endPos.upstream();
1083         
1084         // We can get into a state where the selection endpoints map to the same VisiblePosition when a selection is deleted
1085         // because we don't yet notify the SelectionController of text removal.
1086         if (startPos.isNotNull() && endPos.isNotNull() && s.selection().visibleStart() != s.selection().visibleEnd()) {
1087             RenderObject *startRenderer = startPos.node()->renderer();
1088             RenderObject *endRenderer = endPos.node()->renderer();
1089             static_cast<RenderView*>(renderer())->setSelection(startRenderer, startPos.offset(), endRenderer, endPos.offset());
1090         }
1091     }
1092     
1093 #if __APPLE__
1094     // FIXME: We shouldn't post this AX notification here since updateSelection() is called far to often: every time Safari gains
1095     // or loses focus, and once for every low level change to the selection during an editing operation.
1096     // FIXME: We no longer blow away the selection before starting an editing operation, so the isNotNull checks below are no 
1097     // longer a correct way to check for user-level selection changes.
1098     if (AXObjectCache::accessibilityEnabled() && s.start().isNotNull() && s.end().isNotNull()) {
1099         axObjectCache()->postNotificationToTopWebArea(renderer(), "AXSelectedTextChanged");
1100     }
1101 #endif
1102 }
1103
1104 Tokenizer *Document::createTokenizer()
1105 {
1106     return newXMLTokenizer(this, m_view);
1107 }
1108
1109 void Document::open()
1110 {
1111     if ((frame() && frame()->isLoadingMainResource()) || (tokenizer() && tokenizer()->executingScript()))
1112         return;
1113
1114     implicitOpen();
1115
1116     if (frame())
1117         frame()->didExplicitOpen();
1118
1119     // This is work that we should probably do in clear(), but we can't have it
1120     // happen when implicitOpen() is called unless we reorganize Frame code.
1121     setURL(DeprecatedString());
1122     if (Document *parent = parentDocument())
1123         setBaseURL(parent->baseURL());
1124 }
1125
1126 void Document::cancelParsing()
1127 {
1128     if (m_tokenizer) {
1129         // We have to clear the tokenizer to avoid possibly triggering
1130         // the onload handler when closing as a side effect of a cancel-style
1131         // change, such as opening a new document or closing the window while
1132         // still parsing
1133         delete m_tokenizer;
1134         m_tokenizer = 0;
1135         close();
1136     }
1137 }
1138
1139 void Document::implicitOpen()
1140 {
1141     cancelParsing();
1142
1143     clear();
1144     m_tokenizer = createTokenizer();
1145     setParsing(true);
1146 }
1147
1148 HTMLElement* Document::body()
1149 {
1150     Node *de = documentElement();
1151     if (!de)
1152         return 0;
1153     
1154     // try to prefer a FRAMESET element over BODY
1155     Node* body = 0;
1156     for (Node* i = de->firstChild(); i; i = i->nextSibling()) {
1157         if (i->hasTagName(framesetTag))
1158             return static_cast<HTMLElement*>(i);
1159         
1160         if (i->hasTagName(bodyTag))
1161             body = i;
1162     }
1163     return static_cast<HTMLElement *>(body);
1164 }
1165
1166 void Document::close()
1167 {
1168     if (frame())
1169         frame()->endIfNotLoading();
1170     implicitClose();
1171 }
1172
1173 void Document::implicitClose()
1174 {
1175     // If we're in the middle of recalcStyle, we need to defer the close until the style information is accurate and all elements are re-attached.
1176     if (m_inStyleRecalc) {
1177         m_closeAfterStyleRecalc = true;
1178         return;
1179     }
1180
1181     bool wasLocationChangePending = frame() && frame()->isScheduledLocationChangePending();
1182     bool doload = !parsing() && m_tokenizer && !m_processingLoadEvent && !wasLocationChangePending;
1183     
1184     if (!doload)
1185         return;
1186
1187     m_processingLoadEvent = true;
1188
1189     // We have to clear the tokenizer, in case someone document.write()s from the
1190     // onLoad event handler, as in Radar 3206524.
1191     delete m_tokenizer;
1192     m_tokenizer = 0;
1193
1194     // Create a body element if we don't already have one.
1195     // In the case of Radar 3758785, the window.onload was set in some javascript, but never fired because there was no body.  
1196     // This behavior now matches Firefox and IE.
1197     HTMLElement *body = this->body();
1198     if (!body && isHTMLDocument()) {
1199         Node *de = documentElement();
1200         if (de) {
1201             body = new HTMLBodyElement(this);
1202             ExceptionCode ec = 0;
1203             de->appendChild(body, ec);
1204             if (ec != 0)
1205                 body = 0;
1206         }
1207     }
1208     
1209     dispatchImageLoadEventsNow();
1210     this->dispatchWindowEvent(loadEvent, false, false);
1211     if (Frame *p = frame())
1212         p->handledOnloadEvents();
1213 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1214     if (!ownerElement())
1215         printf("onload fired at %d\n", elapsedTime());
1216 #endif
1217
1218     m_processingLoadEvent = false;
1219
1220     // Make sure both the initial layout and reflow happen after the onload
1221     // fires. This will improve onload scores, and other browsers do it.
1222     // If they wanna cheat, we can too. -dwh
1223
1224     if (frame() && frame()->isScheduledLocationChangePending() && elapsedTime() < cLayoutScheduleThreshold) {
1225         // Just bail out. Before or during the onload we were shifted to another page.
1226         // The old i-Bench suite does this. When this happens don't bother painting or laying out.        
1227         view()->unscheduleRelayout();
1228         return;
1229     }
1230
1231     if (frame())
1232         frame()->checkEmitLoadEvent();
1233
1234     // Now do our painting/layout, but only if we aren't in a subframe or if we're in a subframe
1235     // that has been sized already.  Otherwise, our view size would be incorrect, so doing any 
1236     // layout/painting now would be pointless.
1237     if (!ownerElement() || (ownerElement()->renderer() && !ownerElement()->renderer()->needsLayout())) {
1238         updateRendering();
1239         
1240         // Always do a layout after loading if needed.
1241         if (view() && renderer() && (!renderer()->firstChild() || renderer()->needsLayout()))
1242             view()->layout();
1243     }
1244 #if __APPLE__
1245     if (renderer() && AXObjectCache::accessibilityEnabled())
1246         axObjectCache()->postNotification(renderer(), "AXLoadComplete");
1247 #endif
1248
1249 #if SVG_SUPPORT
1250     // FIXME: Officially, time 0 is when the outermost <svg> receives its
1251     // SVGLoad event, but we don't implement those yet.  This is close enough
1252     // for now.  In some cases we should have fired earlier.
1253     if (svgExtensions())
1254         accessSVGExtensions()->startAnimations();
1255 #endif
1256 }
1257
1258 void Document::setParsing(bool b)
1259 {
1260     m_bParsing = b;
1261     if (!m_bParsing && view())
1262         view()->scheduleRelayout();
1263
1264 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1265     if (!ownerElement() && !m_bParsing)
1266         printf("Parsing finished at %d\n", elapsedTime());
1267 #endif
1268 }
1269
1270 bool Document::shouldScheduleLayout()
1271 {
1272     // We can update layout if:
1273     // (a) we actually need a layout
1274     // (b) our stylesheets are all loaded
1275     // (c) we have a <body>
1276     return (renderer() && renderer()->needsLayout() && haveStylesheetsLoaded() &&
1277             documentElement() && documentElement()->renderer() &&
1278             (!documentElement()->hasTagName(htmlTag) || body()));
1279 }
1280
1281 int Document::minimumLayoutDelay()
1282 {
1283     if (m_overMinimumLayoutThreshold)
1284         return 0;
1285     
1286     int elapsed = elapsedTime();
1287     m_overMinimumLayoutThreshold = elapsed > cLayoutScheduleThreshold;
1288     
1289     // We'll want to schedule the timer to fire at the minimum layout threshold.
1290     return max(0, cLayoutScheduleThreshold - elapsed);
1291 }
1292
1293 int Document::elapsedTime() const
1294 {
1295     return static_cast<int>((currentTime() - m_startTime) * 1000);
1296 }
1297
1298 void Document::write(const String &text)
1299 {
1300     write(text.deprecatedString());
1301 }
1302
1303 void Document::write(const DeprecatedString &text)
1304 {
1305 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1306     if (!ownerElement())
1307         printf("Beginning a document.write at %d\n", elapsedTime());
1308 #endif
1309     
1310     if (!m_tokenizer) {
1311         open();
1312         assert(m_tokenizer);
1313         if (!m_tokenizer)
1314             return;
1315         write(DeprecatedString("<html>"));
1316     }
1317     m_tokenizer->write(text, false);
1318     
1319 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1320     if (!ownerElement())
1321         printf("Ending a document.write at %d\n", elapsedTime());
1322 #endif    
1323 }
1324
1325 void Document::writeln(const String &text)
1326 {
1327     write(text);
1328     write(String("\n"));
1329 }
1330
1331 void Document::finishParsing()
1332 {
1333 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1334     if (!ownerElement())
1335         printf("Received all data at %d\n", elapsedTime());
1336 #endif
1337     
1338     // Let the tokenizer go through as much data as it can.  There will be three possible outcomes after
1339     // finish() is called:
1340     // (1) All remaining data is parsed, document isn't loaded yet
1341     // (2) All remaining data is parsed, document is loaded, tokenizer gets deleted
1342     // (3) Data is still remaining to be parsed.
1343     if (m_tokenizer)
1344         m_tokenizer->finish();
1345 }
1346
1347 void Document::clear()
1348 {
1349     delete m_tokenizer;
1350     m_tokenizer = 0;
1351
1352     removeChildren();
1353
1354     RegisteredEventListenerList::iterator end = m_windowEventListeners.end();
1355     for (RegisteredEventListenerList::iterator it = m_windowEventListeners.begin(); it != end; ++it)
1356         m_windowEventListeners.remove(it);
1357 }
1358
1359 void Document::setURL(const DeprecatedString& url)
1360 {
1361     m_url = url;
1362     if (m_styleSelector)
1363         m_styleSelector->setEncodedURL(m_url);
1364 }
1365
1366 void Document::setStyleSheet(const String &url, const String &sheet)
1367 {
1368     m_sheet = new CSSStyleSheet(this, url);
1369     m_sheet->parseString(sheet);
1370     m_loadingSheet = false;
1371
1372     updateStyleSelector();
1373 }
1374
1375 void Document::setUserStyleSheet(const String& sheet)
1376 {
1377     if (m_usersheet != sheet) {
1378         m_usersheet = sheet;
1379         updateStyleSelector();
1380     }
1381 }
1382
1383 CSSStyleSheet* Document::elementSheet()
1384 {
1385     if (!m_elemSheet)
1386         m_elemSheet = new CSSStyleSheet(this, baseURL());
1387     return m_elemSheet.get();
1388 }
1389
1390 void Document::determineParseMode(const DeprecatedString &/*str*/)
1391 {
1392     // For XML documents use strict parse mode.  HTML docs will override this method to
1393     // determine their parse mode.
1394     pMode = Strict;
1395     hMode = XHtml;
1396 }
1397
1398 Node *Document::nextFocusNode(Node *fromNode)
1399 {
1400     unsigned short fromTabIndex;
1401
1402     if (!fromNode) {
1403         // No starting node supplied; begin with the top of the document
1404         Node *n;
1405
1406         int lowestTabIndex = 65535;
1407         for (n = this; n != 0; n = n->traverseNextNode()) {
1408             if (n->isKeyboardFocusable()) {
1409                 if ((n->tabIndex() > 0) && (n->tabIndex() < lowestTabIndex))
1410                     lowestTabIndex = n->tabIndex();
1411             }
1412         }
1413
1414         if (lowestTabIndex == 65535)
1415             lowestTabIndex = 0;
1416
1417         // Go to the first node in the document that has the desired tab index
1418         for (n = this; n != 0; n = n->traverseNextNode()) {
1419             if (n->isKeyboardFocusable() && (n->tabIndex() == lowestTabIndex))
1420                 return n;
1421         }
1422
1423         return 0;
1424     }
1425     else {
1426         fromTabIndex = fromNode->tabIndex();
1427     }
1428
1429     if (fromTabIndex == 0) {
1430         // Just need to find the next selectable node after fromNode (in document order) that doesn't have a tab index
1431         Node *n = fromNode->traverseNextNode();
1432         while (n && !(n->isKeyboardFocusable() && n->tabIndex() == 0))
1433             n = n->traverseNextNode();
1434         return n;
1435     }
1436     else {
1437         // Find the lowest tab index out of all the nodes except fromNode, that is greater than or equal to fromNode's
1438         // tab index. For nodes with the same tab index as fromNode, we are only interested in those that come after
1439         // fromNode in document order.
1440         // If we don't find a suitable tab index, the next focus node will be one with a tab index of 0.
1441         unsigned short lowestSuitableTabIndex = 65535;
1442         Node *n;
1443
1444         bool reachedFromNode = false;
1445         for (n = this; n != 0; n = n->traverseNextNode()) {
1446             if (n->isKeyboardFocusable() &&
1447                 ((reachedFromNode && (n->tabIndex() >= fromTabIndex)) ||
1448                  (!reachedFromNode && (n->tabIndex() > fromTabIndex))) &&
1449                 (n->tabIndex() < lowestSuitableTabIndex) &&
1450                 (n != fromNode)) {
1451
1452                 // We found a selectable node with a tab index at least as high as fromNode's. Keep searching though,
1453                 // as there may be another node which has a lower tab index but is still suitable for use.
1454                 lowestSuitableTabIndex = n->tabIndex();
1455             }
1456
1457             if (n == fromNode)
1458                 reachedFromNode = true;
1459         }
1460
1461         if (lowestSuitableTabIndex == 65535) {
1462             // No next node with a tab index -> just take first node with tab index of 0
1463             Node *n = this;
1464             while (n && !(n->isKeyboardFocusable() && n->tabIndex() == 0))
1465                 n = n->traverseNextNode();
1466             return n;
1467         }
1468
1469         // Search forwards from fromNode
1470         for (n = fromNode->traverseNextNode(); n != 0; n = n->traverseNextNode()) {
1471             if (n->isKeyboardFocusable() && (n->tabIndex() == lowestSuitableTabIndex))
1472                 return n;
1473         }
1474
1475         // The next node isn't after fromNode, start from the beginning of the document
1476         for (n = this; n != fromNode; n = n->traverseNextNode()) {
1477             if (n->isKeyboardFocusable() && (n->tabIndex() == lowestSuitableTabIndex))
1478                 return n;
1479         }
1480
1481         assert(false); // should never get here
1482         return 0;
1483     }
1484 }
1485
1486 Node *Document::previousFocusNode(Node *fromNode)
1487 {
1488     Node *lastNode = this;
1489     while (lastNode->lastChild())
1490         lastNode = lastNode->lastChild();
1491
1492     if (!fromNode) {
1493         // No starting node supplied; begin with the very last node in the document
1494         Node *n;
1495
1496         int highestTabIndex = 0;
1497         for (n = lastNode; n != 0; n = n->traversePreviousNode()) {
1498             if (n->isKeyboardFocusable()) {
1499                 if (n->tabIndex() == 0)
1500                     return n;
1501                 else if (n->tabIndex() > highestTabIndex)
1502                     highestTabIndex = n->tabIndex();
1503             }
1504         }
1505
1506         // No node with a tab index of 0; just go to the last node with the highest tab index
1507         for (n = lastNode; n != 0; n = n->traversePreviousNode()) {
1508             if (n->isKeyboardFocusable() && (n->tabIndex() == highestTabIndex))
1509                 return n;
1510         }
1511
1512         return 0;
1513     }
1514     else {
1515         unsigned short fromTabIndex = fromNode->tabIndex();
1516
1517         if (fromTabIndex == 0) {
1518             // Find the previous selectable node before fromNode (in document order) that doesn't have a tab index
1519             Node *n = fromNode->traversePreviousNode();
1520             while (n && !(n->isKeyboardFocusable() && n->tabIndex() == 0))
1521                 n = n->traversePreviousNode();
1522             if (n)
1523                 return n;
1524
1525             // No previous nodes with a 0 tab index, go to the last node in the document that has the highest tab index
1526             int highestTabIndex = 0;
1527             for (n = this; n != 0; n = n->traverseNextNode()) {
1528                 if (n->isKeyboardFocusable() && (n->tabIndex() > highestTabIndex))
1529                     highestTabIndex = n->tabIndex();
1530             }
1531
1532             if (highestTabIndex == 0)
1533                 return 0;
1534
1535             for (n = lastNode; n != 0; n = n->traversePreviousNode()) {
1536                 if (n->isKeyboardFocusable() && (n->tabIndex() == highestTabIndex))
1537                     return n;
1538             }
1539
1540             assert(false); // should never get here
1541             return 0;
1542         }
1543         else {
1544             // Find the lowest tab index out of all the nodes except fromNode, that is less than or equal to fromNode's
1545             // tab index. For nodes with the same tab index as fromNode, we are only interested in those before
1546             // fromNode.
1547             // If we don't find a suitable tab index, then there will be no previous focus node.
1548             unsigned short highestSuitableTabIndex = 0;
1549             Node *n;
1550
1551             bool reachedFromNode = false;
1552             for (n = this; n != 0; n = n->traverseNextNode()) {
1553                 if (n->isKeyboardFocusable() &&
1554                     ((!reachedFromNode && (n->tabIndex() <= fromTabIndex)) ||
1555                      (reachedFromNode && (n->tabIndex() < fromTabIndex)))  &&
1556                     (n->tabIndex() > highestSuitableTabIndex) &&
1557                     (n != fromNode)) {
1558
1559                     // We found a selectable node with a tab index no higher than fromNode's. Keep searching though, as
1560                     // there may be another node which has a higher tab index but is still suitable for use.
1561                     highestSuitableTabIndex = n->tabIndex();
1562                 }
1563
1564                 if (n == fromNode)
1565                     reachedFromNode = true;
1566             }
1567
1568             if (highestSuitableTabIndex == 0) {
1569                 // No previous node with a tab index. Since the order specified by HTML is nodes with tab index > 0
1570                 // first, this means that there is no previous node.
1571                 return 0;
1572             }
1573
1574             // Search backwards from fromNode
1575             for (n = fromNode->traversePreviousNode(); n != 0; n = n->traversePreviousNode()) {
1576                 if (n->isKeyboardFocusable() && (n->tabIndex() == highestSuitableTabIndex))
1577                     return n;
1578             }
1579             // The previous node isn't before fromNode, start from the end of the document
1580             for (n = lastNode; n != fromNode; n = n->traversePreviousNode()) {
1581                 if (n->isKeyboardFocusable() && (n->tabIndex() == highestSuitableTabIndex))
1582                     return n;
1583             }
1584
1585             assert(false); // should never get here
1586             return 0;
1587         }
1588     }
1589 }
1590
1591 int Document::nodeAbsIndex(Node *node)
1592 {
1593     assert(node->document() == this);
1594
1595     int absIndex = 0;
1596     for (Node *n = node; n && n != this; n = n->traversePreviousNode())
1597         absIndex++;
1598     return absIndex;
1599 }
1600
1601 Node *Document::nodeWithAbsIndex(int absIndex)
1602 {
1603     Node *n = this;
1604     for (int i = 0; n && (i < absIndex); i++) {
1605         n = n->traverseNextNode();
1606     }
1607     return n;
1608 }
1609
1610 void Document::processHttpEquiv(const String &equiv, const String &content)
1611 {
1612     assert(!equiv.isNull() && !content.isNull());
1613
1614     Frame *frame = this->frame();
1615
1616     if (equalIgnoringCase(equiv, "default-style")) {
1617         // The preferred style set has been overridden as per section 
1618         // 14.3.2 of the HTML4.0 specification.  We need to update the
1619         // sheet used variable and then update our style selector. 
1620         // For more info, see the test at:
1621         // http://www.hixie.ch/tests/evil/css/import/main/preferred.html
1622         // -dwh
1623         m_selectedStylesheetSet = content;
1624         m_preferredStylesheetSet = content;
1625         updateStyleSelector();
1626     } else if (equalIgnoringCase(equiv, "refresh")) {
1627         // get delay and url
1628         DeprecatedString str = content.deprecatedString().stripWhiteSpace();
1629         int pos = str.find(RegularExpression("[;,]"));
1630         if (pos == -1)
1631             pos = str.find(RegularExpression("[ \t]"));
1632
1633         if (pos == -1) // There can be no url (David)
1634         {
1635             bool ok = false;
1636             int delay = 0;
1637             delay = str.toInt(&ok);
1638             // We want a new history item if the refresh timeout > 1 second
1639             if (ok && frame)
1640                 frame->scheduleRedirection(delay, frame->url().url(), delay <= 1);
1641         } else {
1642             double delay = 0;
1643             bool ok = false;
1644             delay = str.left(pos).stripWhiteSpace().toDouble(&ok);
1645
1646             pos++;
1647             while(pos < (int)str.length() && str[pos].isSpace()) pos++;
1648             str = str.mid(pos);
1649             if (str.find("url", 0,  false) == 0)
1650                 str = str.mid(3);
1651             str = str.stripWhiteSpace();
1652             if (str.length() && str[0] == '=')
1653                 str = str.mid(1).stripWhiteSpace();
1654             str = parseURL(String(str)).deprecatedString();
1655             if (ok && frame)
1656                 // We want a new history item if the refresh timeout > 1 second
1657                 frame->scheduleRedirection(delay, completeURL(str), delay <= 1);
1658         }
1659     } else if (equalIgnoringCase(equiv, "expires")) {
1660         DeprecatedString str = content.deprecatedString().stripWhiteSpace();
1661         time_t expire_date = str.toInt();
1662         if (m_docLoader)
1663             m_docLoader->setExpireDate(expire_date);
1664     } else if ((equalIgnoringCase(equiv, "pragma") || equalIgnoringCase(equiv, "cache-control")) && frame) {
1665         DeprecatedString str = content.deprecatedString().lower().stripWhiteSpace();
1666         KURL url = frame->url();
1667     } else if (equalIgnoringCase(equiv, "set-cookie")) {
1668         // ### FIXME: make setCookie work on XML documents too; e.g. in case of <html:meta .....>
1669         if (isHTMLDocument())
1670             static_cast<HTMLDocument *>(this)->setCookie(content);
1671     }
1672 }
1673
1674 MouseEventWithHitTestResults Document::prepareMouseEvent(bool readonly, bool active, bool mouseMove,
1675                                                          const IntPoint& point, const PlatformMouseEvent& event)
1676 {
1677     if (!renderer())
1678         return MouseEventWithHitTestResults(event, 0, false);
1679
1680     assert(renderer()->isRenderView());
1681     RenderObject::NodeInfo renderInfo(readonly, active, mouseMove);
1682     renderer()->layer()->hitTest(renderInfo, point);
1683
1684     if (!readonly)
1685         updateRendering();
1686
1687     bool isOverLink = renderInfo.URLElement() && !renderInfo.URLElement()->getAttribute(hrefAttr).isNull();
1688     return MouseEventWithHitTestResults(event, renderInfo.innerNode(), isOverLink);
1689 }
1690
1691 // DOM Section 1.1.1
1692 bool Document::childTypeAllowed(NodeType type)
1693 {
1694     switch (type) {
1695         case ATTRIBUTE_NODE:
1696         case CDATA_SECTION_NODE:
1697         case DOCUMENT_FRAGMENT_NODE:
1698         case DOCUMENT_NODE:
1699         case ENTITY_NODE:
1700         case ENTITY_REFERENCE_NODE:
1701         case NOTATION_NODE:
1702         case TEXT_NODE:
1703         case XPATH_NAMESPACE_NODE:
1704             return false;
1705         case COMMENT_NODE:
1706         case PROCESSING_INSTRUCTION_NODE:
1707             return true;
1708         case DOCUMENT_TYPE_NODE:
1709         case ELEMENT_NODE:
1710             // Documents may contain no more than one of each of these.
1711             // (One Element and one DocumentType.)
1712             for (Node* c = firstChild(); c; c = c->nextSibling())
1713                 if (c->nodeType() == type)
1714                     return false;
1715             return true;
1716     }
1717     return false;
1718 }
1719
1720 PassRefPtr<Node> Document::cloneNode(bool /*deep*/)
1721 {
1722     // Spec says cloning Document nodes is "implementation dependent"
1723     // so we do not support it...
1724     return 0;
1725 }
1726
1727 StyleSheetList* Document::styleSheets()
1728 {
1729     return m_styleSheets.get();
1730 }
1731
1732 String Document::preferredStylesheetSet() const
1733 {
1734   return m_preferredStylesheetSet;
1735 }
1736
1737 String Document::selectedStylesheetSet() const
1738 {
1739   return m_selectedStylesheetSet;
1740 }
1741
1742 void Document::setSelectedStylesheetSet(const String& aString)
1743 {
1744   m_selectedStylesheetSet = aString;
1745   updateStyleSelector();
1746   if (renderer())
1747     renderer()->repaint();
1748 }
1749
1750 // This method is called whenever a top-level stylesheet has finished loading.
1751 void Document::stylesheetLoaded()
1752 {
1753   // Make sure we knew this sheet was pending, and that our count isn't out of sync.
1754   assert(m_pendingStylesheets > 0);
1755
1756   m_pendingStylesheets--;
1757   
1758 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1759   if (!ownerElement())
1760       printf("Stylesheet loaded at time %d. %d stylesheets still remain.\n", elapsedTime(), m_pendingStylesheets);
1761 #endif
1762
1763   updateStyleSelector();    
1764 }
1765
1766 void Document::updateStyleSelector()
1767 {
1768     // Don't bother updating, since we haven't loaded all our style info yet.
1769     if (!haveStylesheetsLoaded())
1770         return;
1771
1772 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1773     if (!ownerElement())
1774         printf("Beginning update of style selector at time %d.\n", elapsedTime());
1775 #endif
1776
1777     recalcStyleSelector();
1778     recalcStyle(Force);
1779
1780 #ifdef INSTRUMENT_LAYOUT_SCHEDULING
1781     if (!ownerElement())
1782         printf("Finished update of style selector at time %d\n", elapsedTime());
1783 #endif
1784
1785     if (renderer()) {
1786         renderer()->setNeedsLayoutAndMinMaxRecalc();
1787         if (view())
1788             view()->scheduleRelayout();
1789     }
1790 }
1791
1792
1793 DeprecatedStringList Document::availableStyleSheets() const
1794 {
1795     return m_availableSheets;
1796 }
1797
1798 void Document::recalcStyleSelector()
1799 {
1800     if (!renderer() || !attached())
1801         return;
1802
1803     DeprecatedPtrList<StyleSheet> oldStyleSheets = m_styleSheets->styleSheets;
1804     m_styleSheets->styleSheets.clear();
1805     m_availableSheets.clear();
1806     Node *n;
1807     for (n = this; n; n = n->traverseNextNode()) {
1808         StyleSheet *sheet = 0;
1809
1810         if (n->nodeType() == PROCESSING_INSTRUCTION_NODE)
1811         {
1812             // Processing instruction (XML documents only)
1813             ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(n);
1814             sheet = pi->sheet();
1815 #ifdef KHTML_XSLT
1816             // Don't apply XSL transforms to already transformed documents -- <rdar://problem/4132806>
1817             if (pi->isXSL() && !transformSourceDocument()) {
1818                 // Don't apply XSL transforms until loading is finished.
1819                 if (!parsing())
1820                     applyXSLTransform(pi);
1821                 return;
1822             }
1823 #endif
1824             if (!sheet && !pi->localHref().isEmpty())
1825             {
1826                 // Processing instruction with reference to an element in this document - e.g.
1827                 // <?xml-stylesheet href="#mystyle">, with the element
1828                 // <foo id="mystyle">heading { color: red; }</foo> at some location in
1829                 // the document
1830                 Element* elem = getElementById(pi->localHref().impl());
1831                 if (elem) {
1832                     String sheetText("");
1833                     Node *c;
1834                     for (c = elem->firstChild(); c; c = c->nextSibling()) {
1835                         if (c->nodeType() == TEXT_NODE || c->nodeType() == CDATA_SECTION_NODE)
1836                             sheetText += c->nodeValue();
1837                     }
1838
1839                     CSSStyleSheet *cssSheet = new CSSStyleSheet(this);
1840                     cssSheet->parseString(sheetText);
1841                     pi->setStyleSheet(cssSheet);
1842                     sheet = cssSheet;
1843                 }
1844             }
1845
1846         }
1847         else if (n->isHTMLElement() && (n->hasTagName(linkTag) || n->hasTagName(styleTag))) {
1848             HTMLElement *e = static_cast<HTMLElement *>(n);
1849             DeprecatedString title = e->getAttribute(titleAttr).deprecatedString();
1850             bool enabledViaScript = false;
1851             if (e->hasLocalName(linkTag)) {
1852                 // <LINK> element
1853                 HTMLLinkElement* l = static_cast<HTMLLinkElement*>(n);
1854                 if (l->isLoading() || l->isDisabled())
1855                     continue;
1856                 if (!l->sheet())
1857                     title = DeprecatedString::null;
1858                 enabledViaScript = l->isEnabledViaScript();
1859             }
1860
1861             // Get the current preferred styleset.  This is the
1862             // set of sheets that will be enabled.
1863             if (e->hasLocalName(linkTag))
1864                 sheet = static_cast<HTMLLinkElement*>(n)->sheet();
1865             else
1866                 // <STYLE> element
1867                 sheet = static_cast<HTMLStyleElement*>(n)->sheet();
1868
1869             // Check to see if this sheet belongs to a styleset
1870             // (thus making it PREFERRED or ALTERNATE rather than
1871             // PERSISTENT).
1872             if (!enabledViaScript && !title.isEmpty()) {
1873                 // Yes, we have a title.
1874                 if (m_preferredStylesheetSet.isEmpty()) {
1875                     // No preferred set has been established.  If
1876                     // we are NOT an alternate sheet, then establish
1877                     // us as the preferred set.  Otherwise, just ignore
1878                     // this sheet.
1879                     DeprecatedString rel = e->getAttribute(relAttr).deprecatedString();
1880                     if (e->hasLocalName(styleTag) || !rel.contains("alternate"))
1881                         m_preferredStylesheetSet = m_selectedStylesheetSet = title;
1882                 }
1883                       
1884                 if (!m_availableSheets.contains(title))
1885                     m_availableSheets.append(title);
1886                 
1887                 if (title != m_preferredStylesheetSet)
1888                     sheet = 0;
1889             }
1890         }
1891 #if SVG_SUPPORT
1892         else if (n->isSVGElement() && n->hasTagName(SVGNames::styleTag)) {
1893             DeprecatedString title;
1894             // <STYLE> element
1895             SVGStyleElement *s = static_cast<SVGStyleElement*>(n);
1896             if (!s->isLoading()) {
1897                 sheet = s->sheet();
1898                 if(sheet)
1899                     title = s->getAttribute(SVGNames::titleAttr).deprecatedString();
1900             }
1901
1902             if (!title.isEmpty() && m_preferredStylesheetSet.isEmpty())
1903                 m_preferredStylesheetSet = m_selectedStylesheetSet = title;
1904
1905             if (!title.isEmpty()) {
1906                 if (title != m_preferredStylesheetSet)
1907                     sheet = 0; // don't use it
1908
1909                 title = title.replace('&', "&&");
1910
1911                 if (!m_availableSheets.contains(title))
1912                     m_availableSheets.append(title);
1913             }
1914        }
1915 #endif
1916
1917         if (sheet) {
1918             sheet->ref();
1919             m_styleSheets->styleSheets.append(sheet);
1920         }
1921     
1922         // For HTML documents, stylesheets are not allowed within/after the <BODY> tag. So we
1923         // can stop searching here.
1924         if (isHTMLDocument() && n->hasTagName(bodyTag))
1925             break;
1926     }
1927
1928     // De-reference all the stylesheets in the old list
1929     DeprecatedPtrListIterator<StyleSheet> it(oldStyleSheets);
1930     for (; it.current(); ++it)
1931         it.current()->deref();
1932
1933     // Create a new style selector
1934     delete m_styleSelector;
1935     String usersheet = m_usersheet;
1936     if (m_view && m_view->mediaType() == "print")
1937         usersheet += m_printSheet;
1938     m_styleSelector = new CSSStyleSelector(this, usersheet, m_styleSheets.get(), !inCompatMode());
1939     m_styleSelector->setEncodedURL(m_url);
1940     m_styleSelectorDirty = false;
1941 }
1942
1943 void Document::setHoverNode(PassRefPtr<Node> newHoverNode)
1944 {
1945     m_hoverNode = newHoverNode;
1946 }
1947
1948 void Document::setActiveNode(PassRefPtr<Node> newActiveNode)
1949 {
1950     m_activeNode = newActiveNode;
1951 }
1952
1953 void Document::hoveredNodeDetached(Node* node)
1954 {
1955     if (!m_hoverNode || (node != m_hoverNode && (!m_hoverNode->isTextNode() || node != m_hoverNode->parent())))
1956         return;
1957
1958     m_hoverNode = node->parent();
1959     while (m_hoverNode && !m_hoverNode->renderer())
1960         m_hoverNode = m_hoverNode->parent();
1961     if (view())
1962         view()->scheduleHoverStateUpdate();
1963 }
1964
1965 void Document::activeChainNodeDetached(Node* node)
1966 {
1967     if (!m_activeNode || (node != m_activeNode && (!m_activeNode->isTextNode() || node != m_activeNode->parent())))
1968         return;
1969
1970     m_activeNode = node->parent();
1971     while (m_activeNode && !m_activeNode->renderer())
1972         m_activeNode = m_activeNode->parent();
1973 }
1974
1975 bool Document::relinquishesEditingFocus(Node *node)
1976 {
1977     assert(node);
1978     assert(node->isContentEditable());
1979
1980     Node *root = node->rootEditableElement();
1981     if (!frame() || !root)
1982         return false;
1983
1984     return frame()->shouldEndEditing(rangeOfContents(root).get());
1985 }
1986
1987 bool Document::acceptsEditingFocus(Node *node)
1988 {
1989     assert(node);
1990     assert(node->isContentEditable());
1991
1992     Node *root = node->rootEditableElement();
1993     if (!frame() || !root)
1994         return false;
1995
1996     return frame()->shouldBeginEditing(rangeOfContents(root).get());
1997 }
1998
1999 void Document::didBeginEditing()
2000 {
2001     if (!frame())
2002         return;
2003     
2004     frame()->didBeginEditing();
2005 }
2006
2007 void Document::didEndEditing()
2008 {
2009     if (!frame())
2010         return;
2011     
2012     frame()->didEndEditing();
2013 }
2014
2015 #if __APPLE__
2016 const DeprecatedValueList<DashboardRegionValue> & Document::dashboardRegions() const
2017 {
2018     return m_dashboardRegions;
2019 }
2020
2021 void Document::setDashboardRegions (const DeprecatedValueList<DashboardRegionValue>& regions)
2022 {
2023     m_dashboardRegions = regions;
2024     setDashboardRegionsDirty (false);
2025 }
2026 #endif
2027
2028 static Widget *widgetForNode(Node *focusNode)
2029 {
2030     if (!focusNode)
2031         return 0;
2032     RenderObject *renderer = focusNode->renderer();
2033     if (!renderer || !renderer->isWidget())
2034         return 0;
2035     return static_cast<RenderWidget*>(renderer)->widget();
2036 }
2037
2038 bool Document::setFocusNode(PassRefPtr<Node> newFocusNode)
2039 {    
2040     // Make sure newFocusNode is actually in this document
2041     if (newFocusNode && (newFocusNode->document() != this))
2042         return true;
2043
2044     if (m_focusNode == newFocusNode)
2045         return true;
2046
2047     if (m_focusNode && m_focusNode.get() == m_focusNode->rootEditableElement() && !relinquishesEditingFocus(m_focusNode.get()))
2048         return false;
2049         
2050     bool focusChangeBlocked = false;
2051     RefPtr<Node> oldFocusNode = m_focusNode;
2052     m_focusNode = 0;
2053     clearSelectionIfNeeded(newFocusNode.get());
2054
2055     // Remove focus from the existing focus node (if any)
2056     if (oldFocusNode && !oldFocusNode->m_inDetach) { 
2057         if (oldFocusNode->active())
2058             oldFocusNode->setActive(false);
2059
2060         oldFocusNode->setFocus(false);
2061                 
2062         // Dispatch a change event for text fields or textareas that have been edited
2063         RenderObject *r = static_cast<RenderObject*>(oldFocusNode.get()->renderer());
2064         if (r && (r->isTextArea() || r->isTextField()) && r->isEdited()) {
2065             EventTargetNodeCast(oldFocusNode.get())->dispatchHTMLEvent(changeEvent, true, false);
2066             if ((r = static_cast<RenderObject*>(oldFocusNode.get()->renderer())))
2067                 r->setEdited(false);
2068         }
2069
2070         // Dispatch the blur event and let the node do any other blur related activities (important for text fields)
2071         EventTargetNodeCast(oldFocusNode.get())->dispatchBlurEvent();
2072
2073         if (m_focusNode) {
2074             // handler shifted focus
2075             focusChangeBlocked = true;
2076             newFocusNode = 0;
2077         }
2078         clearSelectionIfNeeded(newFocusNode.get());
2079         EventTargetNodeCast(oldFocusNode.get())->dispatchUIEvent(DOMFocusOutEvent);
2080         if (m_focusNode) {
2081             // handler shifted focus
2082             focusChangeBlocked = true;
2083             newFocusNode = 0;
2084         }
2085         clearSelectionIfNeeded(newFocusNode.get());
2086         if ((oldFocusNode.get() == this) && oldFocusNode->hasOneRef())
2087             return true;
2088             
2089         if (oldFocusNode.get() == oldFocusNode->rootEditableElement())
2090             didEndEditing();
2091     }
2092
2093     if (newFocusNode) {
2094         if (newFocusNode == newFocusNode->rootEditableElement() && !acceptsEditingFocus(newFocusNode.get())) {
2095             // delegate blocks focus change
2096             focusChangeBlocked = true;
2097             goto SetFocusNodeDone;
2098         }
2099         // Set focus on the new node
2100         m_focusNode = newFocusNode.get();
2101
2102         // Dispatch the focus event and let the node do any other focus related activities (important for text fields)
2103         EventTargetNodeCast(m_focusNode.get())->dispatchFocusEvent();
2104
2105         if (m_focusNode != newFocusNode) {
2106             // handler shifted focus
2107             focusChangeBlocked = true;
2108             goto SetFocusNodeDone;
2109         }
2110         EventTargetNodeCast(m_focusNode.get())->dispatchUIEvent(DOMFocusInEvent);
2111         if (m_focusNode != newFocusNode) { 
2112             // handler shifted focus
2113             focusChangeBlocked = true;
2114             goto SetFocusNodeDone;
2115         }
2116         m_focusNode->setFocus();
2117         
2118         if (m_focusNode.get() == m_focusNode->rootEditableElement())
2119             didBeginEditing();
2120         
2121         // eww, I suck. set the qt focus correctly
2122         // ### find a better place in the code for this
2123         if (view()) {
2124             Widget *focusWidget = widgetForNode(m_focusNode.get());
2125             if (focusWidget) {
2126                 // Make sure a widget has the right size before giving it focus.
2127                 // Otherwise, we are testing edge cases of the Widget code.
2128                 // Specifically, in WebCore this does not work well for text fields.
2129                 updateLayout();
2130                 // Re-get the widget in case updating the layout changed things.
2131                 focusWidget = widgetForNode(m_focusNode.get());
2132             }
2133             if (focusWidget)
2134                 focusWidget->setFocus();
2135             else
2136                 view()->setFocus();
2137         }
2138    }
2139
2140 #if __APPLE__
2141     if (!focusChangeBlocked && m_focusNode && AXObjectCache::accessibilityEnabled())
2142         axObjectCache()->handleFocusedUIElementChanged();
2143 #endif
2144
2145 SetFocusNodeDone:
2146     updateRendering();
2147     return !focusChangeBlocked;
2148 }
2149
2150 void Document::clearSelectionIfNeeded(Node *newFocusNode)
2151 {
2152     if (!frame())
2153         return;
2154
2155     // Clear the selection when changing the focus node to null or to a node that is not 
2156     // contained by the current selection.
2157     Node *startContainer = frame()->selection().start().node();
2158     if (!newFocusNode || (startContainer && startContainer != newFocusNode && !(startContainer->isAncestor(newFocusNode)) && startContainer->shadowAncestorNode() != newFocusNode))
2159         // FIXME: 6498 Should just be able to call m_frame->selection().clear()
2160         frame()->setSelection(SelectionController());
2161 }
2162
2163 void Document::setCSSTarget(Node* n)
2164 {
2165     if (m_cssTarget)
2166         m_cssTarget->setChanged();
2167     m_cssTarget = n;
2168     if (n)
2169         n->setChanged();
2170 }
2171
2172 Node* Document::getCSSTarget() const
2173 {
2174     return m_cssTarget;
2175 }
2176
2177 void Document::attachNodeIterator(NodeIterator *ni)
2178 {
2179     m_nodeIterators.append(ni);
2180 }
2181
2182 void Document::detachNodeIterator(NodeIterator *ni)
2183 {
2184     m_nodeIterators.remove(ni);
2185 }
2186
2187 void Document::notifyBeforeNodeRemoval(Node *n)
2188 {
2189     if (Frame* f = frame()) {
2190         f->selection().nodeWillBeRemoved(n);
2191         f->dragCaret().nodeWillBeRemoved(n);
2192     }
2193     DeprecatedPtrListIterator<NodeIterator> it(m_nodeIterators);
2194     for (; it.current(); ++it)
2195         it.current()->notifyBeforeNodeRemoval(n);
2196 }
2197
2198 DOMWindow* Document::defaultView() const
2199 {
2200     if (!frame())
2201         return 0;
2202     
2203     return frame()->domWindow();
2204 }
2205
2206 PassRefPtr<Event> Document::createEvent(const String &eventType, ExceptionCode& ec)
2207 {
2208     if (eventType == "UIEvents" || eventType == "UIEvent")
2209         return new UIEvent();
2210     if (eventType == "MouseEvents" || eventType == "MouseEvent")
2211         return new MouseEvent();
2212     if (eventType == "MutationEvents" || eventType == "MutationEvent")
2213         return new MutationEvent();
2214     if (eventType == "KeyboardEvents" || eventType == "KeyboardEvent")
2215         return new KeyboardEvent();
2216     if (eventType == "HTMLEvents" || eventType == "Event" || eventType == "Events")
2217         return new Event();
2218 #if SVG_SUPPORT
2219     if (eventType == "SVGEvents")
2220         return new Event();
2221     if (eventType == "SVGZoomEvents")
2222         return new SVGZoomEvent();
2223 #endif
2224     ec = NOT_SUPPORTED_ERR;
2225     return 0;
2226 }
2227
2228 CSSStyleDeclaration *Document::getOverrideStyle(Element */*elt*/, const String &/*pseudoElt*/)
2229 {
2230     return 0; // ###
2231 }
2232
2233 void Document::handleWindowEvent(Event *evt, bool useCapture)
2234 {
2235     if (m_windowEventListeners.isEmpty())
2236         return;
2237         
2238     // if any html event listeners are registered on the window, then dispatch them here
2239     RegisteredEventListenerList listenersCopy = m_windowEventListeners;
2240     RegisteredEventListenerList::iterator it = listenersCopy.begin();
2241     
2242     for (; it != listenersCopy.end(); ++it)
2243         if ((*it)->eventType() == evt->type() && (*it)->useCapture() == useCapture && !(*it)->removed()) 
2244             (*it)->listener()->handleEvent(evt, true);
2245 }
2246
2247
2248 void Document::defaultEventHandler(Event *evt)
2249 {
2250     // handle accesskey
2251     if (evt->type() == keydownEvent) {
2252         KeyboardEvent* kevt = static_cast<KeyboardEvent *>(evt);
2253         if (kevt->ctrlKey()) {
2254             const PlatformKeyboardEvent* ev = kevt->keyEvent();
2255             String key = (ev ? ev->unmodifiedText() : kevt->keyIdentifier()).lower();
2256             Element* elem = getElementByAccessKey(key);
2257             if (elem) {
2258                 elem->accessKeyAction(false);
2259                 evt->setDefaultHandled();
2260             }
2261         }
2262     }
2263 }
2264
2265 void Document::setHTMLWindowEventListener(const AtomicString &eventType, PassRefPtr<EventListener> listener)
2266 {
2267     // If we already have it we don't want removeWindowEventListener to delete it
2268     removeHTMLWindowEventListener(eventType);
2269     if (listener)
2270         addWindowEventListener(eventType, listener, false);
2271 }
2272
2273 EventListener *Document::getHTMLWindowEventListener(const AtomicString &eventType)
2274 {
2275     RegisteredEventListenerList::iterator it = m_windowEventListeners.begin();
2276        for (; it != m_windowEventListeners.end(); ++it)
2277         if ( (*it)->eventType() == eventType && (*it)->listener()->isHTMLEventListener())
2278             return (*it)->listener();
2279     return 0;
2280 }
2281
2282 void Document::removeHTMLWindowEventListener(const AtomicString &eventType)
2283 {
2284     RegisteredEventListenerList::iterator it = m_windowEventListeners.begin();
2285     for (; it != m_windowEventListeners.end(); ++it)
2286         if ( (*it)->eventType() == eventType && (*it)->listener()->isHTMLEventListener()) {
2287             m_windowEventListeners.remove(it);
2288             return;
2289         }
2290 }
2291
2292 void Document::addWindowEventListener(const AtomicString &eventType, PassRefPtr<EventListener> listener, bool useCapture)
2293 {
2294     // Remove existing identical listener set with identical arguments.
2295     // The DOM 2 spec says that "duplicate instances are discarded" in this case.
2296     removeWindowEventListener(eventType, listener.get(), useCapture);
2297     m_windowEventListeners.append(new RegisteredEventListener(eventType, listener, useCapture));
2298 }
2299
2300 void Document::removeWindowEventListener(const AtomicString &eventType, EventListener *listener, bool useCapture)
2301 {
2302     RegisteredEventListener rl(eventType, listener, useCapture);
2303     RegisteredEventListenerList::iterator it = m_windowEventListeners.begin();
2304     for (; it != m_windowEventListeners.end(); ++it)
2305         if (*(*it) == rl) {
2306             m_windowEventListeners.remove(it);
2307             return;
2308         }
2309 }
2310
2311 bool Document::hasWindowEventListener(const AtomicString &eventType)
2312 {
2313     RegisteredEventListenerList::iterator it = m_windowEventListeners.begin();
2314     for (; it != m_windowEventListeners.end(); ++it)
2315         if ((*it)->eventType() == eventType) {
2316             return true;
2317         }
2318     return false;
2319 }
2320
2321 PassRefPtr<EventListener> Document::createHTMLEventListener(const String& functionName, const String& code, Node *node)
2322 {
2323     if (Frame* frm = frame())
2324         if (KJSProxy* proxy = frm->jScript())
2325             return proxy->createHTMLEventHandler(functionName, code, node);
2326     return 0;
2327 }
2328
2329 void Document::setHTMLWindowEventListener(const AtomicString& eventType, Attribute* attr)
2330 {
2331     setHTMLWindowEventListener(eventType,
2332         createHTMLEventListener(attr->localName().domString(), attr->value(), 0));
2333 }
2334
2335 void Document::dispatchImageLoadEventSoon(HTMLImageLoader *image)
2336 {
2337     m_imageLoadEventDispatchSoonList.append(image);
2338     if (!m_imageLoadEventTimer.isActive())
2339         m_imageLoadEventTimer.startOneShot(0);
2340 }
2341
2342 void Document::removeImage(HTMLImageLoader* image)
2343 {
2344     // Remove instances of this image from both lists.
2345     // Use loops because we allow multiple instances to get into the lists.
2346     while (m_imageLoadEventDispatchSoonList.removeRef(image)) { }
2347     while (m_imageLoadEventDispatchingList.removeRef(image)) { }
2348     if (m_imageLoadEventDispatchSoonList.isEmpty())
2349         m_imageLoadEventTimer.stop();
2350 }
2351
2352 void Document::dispatchImageLoadEventsNow()
2353 {
2354     // need to avoid re-entering this function; if new dispatches are
2355     // scheduled before the parent finishes processing the list, they
2356     // will set a timer and eventually be processed
2357     if (!m_imageLoadEventDispatchingList.isEmpty()) {
2358         return;
2359     }
2360
2361     m_imageLoadEventTimer.stop();
2362     
2363     m_imageLoadEventDispatchingList = m_imageLoadEventDispatchSoonList;
2364     m_imageLoadEventDispatchSoonList.clear();
2365     for (DeprecatedPtrListIterator<HTMLImageLoader> it(m_imageLoadEventDispatchingList); it.current();) {
2366         HTMLImageLoader* image = it.current();
2367         // Must advance iterator *before* dispatching call.
2368         // Otherwise, it might be advanced automatically if dispatching the call had a side effect
2369         // of destroying the current HTMLImageLoader, and then we would advance past the *next* item,
2370         // missing one altogether.
2371         ++it;
2372         image->dispatchLoadEvent();
2373     }
2374     m_imageLoadEventDispatchingList.clear();
2375 }
2376
2377 void Document::imageLoadEventTimerFired(Timer<Document>*)
2378 {
2379     dispatchImageLoadEventsNow();
2380 }
2381
2382 Element *Document::ownerElement() const
2383 {
2384     if (!frame())
2385         return 0;
2386     return frame()->ownerElement();
2387 }
2388
2389 String Document::referrer() const
2390 {
2391     if (frame())
2392         return frame()->incomingReferrer();
2393     
2394     return String();
2395 }
2396
2397 String Document::domain() const
2398 {
2399     if (m_domain.isEmpty()) // not set yet (we set it on demand to save time and space)
2400         m_domain = KURL(URL()).host(); // Initially set to the host
2401     return m_domain;
2402 }
2403
2404 void Document::setDomain(const String &newDomain, bool force /*=false*/)
2405 {
2406     if (force) {
2407         m_domain = newDomain;
2408         return;
2409     }
2410     if (m_domain.isEmpty()) // not set yet (we set it on demand to save time and space)
2411         m_domain = KURL(URL()).host(); // Initially set to the host
2412
2413     // Both NS and IE specify that changing the domain is only allowed when
2414     // the new domain is a suffix of the old domain.
2415     int oldLength = m_domain.length();
2416     int newLength = newDomain.length();
2417     if (newLength < oldLength) // e.g. newDomain=kde.org (7) and m_domain=www.kde.org (11)
2418     {
2419         String test = m_domain.copy();
2420         if (test[oldLength - newLength - 1] == '.') // Check that it's a subdomain, not e.g. "de.org"
2421         {
2422             test.remove(0, oldLength - newLength); // now test is "kde.org" from m_domain
2423             if (test == newDomain)                 // and we check that it's the same thing as newDomain
2424                 m_domain = newDomain;
2425         }
2426     }
2427 }
2428
2429 bool Document::isValidName(const String &name)
2430 {
2431     const UChar* s = reinterpret_cast<const UChar*>(name.characters());
2432     unsigned length = name.length();
2433
2434     if (length == 0)
2435         return false;
2436
2437     unsigned i = 0;
2438
2439     UChar32 c;
2440     U16_NEXT(s, i, length, c)
2441     if (!isValidNameStart(c))
2442         return false;
2443
2444     while (i < length) {
2445         U16_NEXT(s, i, length, c)
2446         if (!isValidNamePart(c))
2447             return false;
2448     }
2449
2450     return true;
2451 }
2452
2453 bool Document::parseQualifiedName(const String &qualifiedName, String &prefix, String &localName)
2454 {
2455     unsigned length = qualifiedName.length();
2456
2457     if (length == 0)
2458         return false;
2459
2460     bool nameStart = true;
2461     bool sawColon = false;
2462     int colonPos = 0;
2463
2464     const UChar* s = reinterpret_cast<const UChar*>(qualifiedName.characters());
2465     for (unsigned i = 0; i < length;) {
2466         UChar32 c;
2467         U16_NEXT(s, i, length, c)
2468         if (c == ':') {
2469             if (sawColon)
2470                 return false; // multiple colons: not allowed
2471             nameStart = true;
2472             sawColon = true;
2473             colonPos = i - 1;
2474         } else if (nameStart) {
2475             if (!isValidNameStart(c))
2476                 return false;
2477             nameStart = false;
2478         } else {
2479             if (!isValidNamePart(c))
2480                 return false;
2481         }
2482     }
2483
2484     if (!sawColon) {
2485         prefix = String();
2486         localName = qualifiedName.copy();
2487     } else {
2488         prefix = qualifiedName.substring(0, colonPos);
2489         localName = qualifiedName.substring(colonPos + 1, length - (colonPos + 1));
2490     }
2491
2492     return true;
2493 }
2494
2495 void Document::addImageMap(HTMLMapElement* imageMap)
2496 {
2497     // Add the image map, unless there's already another with that name.
2498     // "First map wins" is the rule other browsers seem to implement.
2499     m_imageMapsByName.add(imageMap->getName().impl(), imageMap);
2500 }
2501
2502 void Document::removeImageMap(HTMLMapElement* imageMap)
2503 {
2504     // Remove the image map by name.
2505     // But don't remove some other image map that just happens to have the same name.
2506     // FIXME: Use a HashCountedSet as we do for IDs to find the first remaining map
2507     // once a map has been removed.
2508     const AtomicString& name = imageMap->getName();
2509     ImageMapsByName::iterator it = m_imageMapsByName.find(name.impl());
2510     if (it != m_imageMapsByName.end() && it->second == imageMap)
2511         m_imageMapsByName.remove(it);
2512 }
2513
2514 HTMLMapElement *Document::getImageMap(const String& URL) const
2515 {
2516     if (URL.isNull())
2517         return 0;
2518     int hashPos = URL.find('#');
2519     AtomicString name = (hashPos < 0 ? URL : URL.substring(hashPos + 1)).impl();
2520     return m_imageMapsByName.get(name.impl());
2521 }
2522
2523 void Document::setDecoder(Decoder *decoder)
2524 {
2525     m_decoder = decoder;
2526 }
2527
2528 UChar Document::backslashAsCurrencySymbol() const
2529 {
2530     if (!m_decoder)
2531         return '\\';
2532     return m_decoder->encoding().backslashAsCurrencySymbol();
2533 }
2534
2535 DeprecatedString Document::completeURL(const DeprecatedString &URL)
2536 {
2537     // If both the URL and base URL are empty, like they are for documents
2538     // created using DOMImplementation::createDocument, just return the passed in URL.
2539     // (We do this because URL() returns "about:blank" for empty URLs.
2540     if (m_url.isEmpty() && m_baseURL.isEmpty())
2541         return URL;
2542     
2543     if (!m_decoder)
2544         return KURL(baseURL(), URL).url();
2545     return KURL(baseURL(), URL, m_decoder->encoding()).url();
2546 }
2547
2548 String Document::completeURL(const String &URL)
2549 {
2550     if (URL.isNull())
2551         return URL;
2552     return completeURL(URL.deprecatedString());
2553 }
2554
2555 bool Document::inPageCache()
2556 {
2557     return m_inPageCache;
2558 }
2559
2560 void Document::setInPageCache(bool flag)
2561 {
2562     if (m_inPageCache == flag)
2563         return;
2564
2565     m_inPageCache = flag;
2566     if (flag) {
2567         ASSERT(m_savedRenderer == 0);
2568         m_savedRenderer = renderer();
2569         if (m_view)
2570             m_view->resetScrollBars();
2571     } else {
2572         ASSERT(renderer() == 0 || renderer() == m_savedRenderer);
2573         ASSERT(m_renderArena);
2574         setRenderer(m_savedRenderer);
2575         m_savedRenderer = 0;
2576     }
2577 }
2578
2579 void Document::passwordFieldAdded()
2580 {
2581     m_passwordFields++;
2582 }
2583
2584 void Document::passwordFieldRemoved()
2585 {
2586     assert(m_passwordFields > 0);
2587     m_passwordFields--;
2588 }
2589
2590 bool Document::hasPasswordField() const
2591 {
2592     return m_passwordFields > 0;
2593 }
2594
2595 void Document::secureFormAdded()
2596 {
2597     m_secureForms++;
2598 }
2599
2600 void Document::secureFormRemoved()
2601 {
2602     assert(m_secureForms > 0);
2603     m_secureForms--;
2604 }
2605
2606 bool Document::hasSecureForm() const
2607 {
2608     return m_secureForms > 0;
2609 }
2610
2611 void Document::setShouldCreateRenderers(bool f)
2612 {
2613     m_createRenderers = f;
2614 }
2615
2616 bool Document::shouldCreateRenderers()
2617 {
2618     return m_createRenderers;
2619 }
2620
2621 String Document::toString() const
2622 {
2623     String result;
2624
2625     for (Node *child = firstChild(); child != NULL; child = child->nextSibling()) {
2626         result += child->toString();
2627     }
2628
2629     return result;
2630 }
2631
2632 // Support for Javascript execCommand, and related methods
2633
2634 JSEditor *Document::jsEditor()
2635 {
2636     if (!m_jsEditor)
2637         m_jsEditor = new JSEditor(this);
2638     return m_jsEditor;
2639 }
2640
2641 bool Document::execCommand(const String &command, bool userInterface, const String &value)
2642 {
2643     return jsEditor()->execCommand(command, userInterface, value);
2644 }
2645
2646 bool Document::queryCommandEnabled(const String &command)
2647 {
2648     return jsEditor()->queryCommandEnabled(command);
2649 }
2650
2651 bool Document::queryCommandIndeterm(const String &command)
2652 {
2653     return jsEditor()->queryCommandIndeterm(command);
2654 }
2655
2656 bool Document::queryCommandState(const String &command)
2657 {
2658     return jsEditor()->queryCommandState(command);
2659 }
2660
2661 bool Document::queryCommandSupported(const String &command)
2662 {
2663     return jsEditor()->queryCommandSupported(command);
2664 }
2665
2666 String Document::queryCommandValue(const String &command)
2667 {
2668     return jsEditor()->queryCommandValue(command);
2669 }
2670
2671 static IntRect placeholderRectForMarker(void)
2672 {
2673     return IntRect(-1,-1,-1,-1);
2674 }
2675
2676 void Document::addMarker(Range *range, DocumentMarker::MarkerType type)
2677 {
2678     // Use a TextIterator to visit the potentially multiple nodes the range covers.
2679     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
2680         RefPtr<Range> textPiece = markedText.range();
2681         int exception = 0;
2682         DocumentMarker marker = {type, textPiece->startOffset(exception), textPiece->endOffset(exception)};
2683         addMarker(textPiece->startContainer(exception), marker);
2684     }
2685 }
2686
2687 void Document::removeMarkers(Range *range, DocumentMarker::MarkerType markerType)
2688 {
2689     // Use a TextIterator to visit the potentially multiple nodes the range covers.
2690     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
2691         RefPtr<Range> textPiece = markedText.range();
2692         int exception = 0;
2693         unsigned startOffset = textPiece->startOffset(exception);
2694         unsigned length = textPiece->endOffset(exception) - startOffset + 1;
2695         removeMarkers(textPiece->startContainer(exception), startOffset, length, markerType);
2696     }
2697 }
2698
2699 // Markers are stored in order sorted by their location.  They do not overlap each other, as currently
2700 // required by the drawing code in RenderText.cpp.
2701
2702 void Document::addMarker(Node *node, DocumentMarker newMarker) 
2703 {
2704     assert(newMarker.endOffset >= newMarker.startOffset);
2705     if (newMarker.endOffset == newMarker.startOffset)
2706         return;
2707     
2708     MarkerMapVectorPair* vectorPair = m_markers.get(node);
2709     
2710     if (!vectorPair) {
2711         vectorPair = new MarkerMapVectorPair;
2712         vectorPair->first.append(newMarker);
2713         vectorPair->second.append(placeholderRectForMarker());
2714         m_markers.set(node, vectorPair);
2715     } else {
2716         Vector<DocumentMarker>& markers = vectorPair->first;
2717         Vector<IntRect>& rects = vectorPair->second;
2718         ASSERT(markers.size() == rects.size());
2719         Vector<DocumentMarker>::iterator it;
2720         for (it = markers.begin(); it != markers.end();) {
2721             DocumentMarker marker = *it;
2722             
2723             if (newMarker.endOffset < marker.startOffset+1) {
2724                 // This is the first marker that is completely after newMarker, and disjoint from it.
2725                 // We found our insertion point.\10
2726                 break;
2727             } else if (newMarker.startOffset > marker.endOffset) {
2728                 // maker is before newMarker, and disjoint from it.  Keep scanning.
2729                 it++;
2730             } else if (newMarker == marker) {
2731                 // already have this one, NOP
2732                 return;
2733             } else {
2734                 // marker and newMarker intersect or touch - merge them into newMarker
2735                 newMarker.startOffset = min(newMarker.startOffset, marker.startOffset);
2736                 newMarker.endOffset = max(newMarker.endOffset, marker.endOffset);
2737                 // remove old one, we'll add newMarker later
2738                 unsigned removalIndex = it - markers.begin();
2739                 markers.remove(removalIndex);
2740                 rects.remove(removalIndex);
2741                 // it points to the next marker to consider
2742             }
2743         }
2744         // at this point it points to the node before which we want to insert
2745         unsigned insertionIndex = it - markers.begin();
2746         markers.insert(insertionIndex, newMarker);
2747         rects.insert(insertionIndex, placeholderRectForMarker());
2748     }
2749     
2750     // repaint the affected node
2751     if (node->renderer())
2752         node->renderer()->repaint();
2753 }
2754
2755 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies.  The shift is
2756 // useful if, e.g., the caller has created the dstNode from a non-prefix substring of the srcNode.
2757 void Document::copyMarkers(Node *srcNode, unsigned startOffset, int length, Node *dstNode, int delta, DocumentMarker::MarkerType markerType)
2758 {
2759     if (length <= 0)
2760         return;
2761     
2762     MarkerMapVectorPair* vectorPair = m_markers.get(srcNode);
2763     if (!vectorPair)
2764         return;
2765
2766     ASSERT(vectorPair->first.size() == vectorPair->second.size());
2767
2768     bool docDirty = false;
2769     unsigned endOffset = startOffset + length - 1;
2770     Vector<DocumentMarker>::iterator it;
2771     Vector<DocumentMarker>& markers = vectorPair->first;
2772     for (it = markers.begin(); it != markers.end(); ++it) {
2773         DocumentMarker marker = *it;
2774
2775         // stop if we are now past the specified range
2776         if (marker.startOffset > endOffset)
2777             break;
2778         
2779         // skip marker that is before the specified range or is the wrong type
2780         if (marker.endOffset < startOffset || (marker.type != markerType && markerType != DocumentMarker::AllMarkers))
2781             continue;
2782
2783         // pin the marker to the specified range and apply the shift delta
2784         docDirty = true;
2785         if (marker.startOffset < startOffset)
2786             marker.startOffset = startOffset;
2787         if (marker.endOffset > endOffset)
2788             marker.endOffset = endOffset;
2789         marker.startOffset += delta;
2790         marker.endOffset += delta;
2791         
2792         addMarker(dstNode, marker);
2793     }
2794     
2795     // repaint the affected node
2796     if (docDirty && dstNode->renderer())
2797         dstNode->renderer()->repaint();
2798 }
2799
2800 void Document::removeMarkers(Node *node, unsigned startOffset, int length, DocumentMarker::MarkerType markerType)
2801 {
2802     if (length <= 0)
2803         return;
2804
2805     MarkerMapVectorPair* vectorPair = m_markers.get(node);
2806     if (!vectorPair)
2807         return;
2808
2809     Vector<DocumentMarker>& markers = vectorPair->first;
2810     Vector<IntRect>& rects = vectorPair->second;
2811     ASSERT(markers.size() == rects.size());
2812     bool docDirty = false;
2813     unsigned endOffset = startOffset + length - 1;
2814     Vector<DocumentMarker>::iterator it;
2815     for (it = markers.begin(); it < markers.end();) {
2816         DocumentMarker marker = *it;
2817
2818         // markers are returned in order, so stop if we are now past the specified range
2819         if (marker.startOffset > endOffset)
2820             break;
2821         
2822         // skip marker that is wrong type or before target
2823         if (marker.endOffset < startOffset || (marker.type != markerType && markerType != DocumentMarker::AllMarkers)) {
2824             it++;
2825             continue;
2826         }
2827
2828         // at this point we know that marker and target intersect in some way
2829         docDirty = true;
2830
2831         // pitch the old marker and any associated rect
2832         unsigned removalIndex = it - markers.begin();
2833         markers.remove(removalIndex);
2834         rects.remove(removalIndex);
2835         // it now points to the next node
2836         
2837         // add either of the resulting slices that are left after removing target
2838         if (startOffset > marker.startOffset) {
2839             DocumentMarker newLeft = marker;
2840             newLeft.endOffset = startOffset;
2841             unsigned insertionIndex = it - markers.begin();
2842             markers.insert(insertionIndex, newLeft);
2843             rects.insert(insertionIndex, placeholderRectForMarker());
2844             // it now points to the newly-inserted node, but we want to skip that one
2845             it++;
2846         }
2847         if (marker.endOffset > endOffset) {
2848             DocumentMarker newRight = marker;
2849             newRight.startOffset = endOffset;
2850             unsigned insertionIndex = it - markers.begin();
2851             markers.insert(insertionIndex, newRight);
2852             rects.insert(insertionIndex, placeholderRectForMarker());
2853             // it now points to the newly-inserted node, but we want to skip that one
2854             it++;
2855         }
2856     }
2857
2858     if (markers.isEmpty()) {
2859         ASSERT(rects.isEmpty());
2860         m_markers.remove(node);
2861         delete vectorPair;
2862     }
2863
2864     // repaint the affected node
2865     if (docDirty && node->renderer())
2866         node->renderer()->repaint();
2867 }
2868
2869 Vector<DocumentMarker> Document::markersForNode(Node* node)
2870 {
2871     MarkerMapVectorPair* vectorPair = m_markers.get(node);
2872     if (vectorPair)
2873         return vectorPair->first;
2874     return Vector<DocumentMarker>();
2875 }
2876
2877 Vector<IntRect> Document::renderedRectsForMarkers(DocumentMarker::MarkerType markerType)
2878 {
2879     Vector<IntRect> result;
2880     
2881     // outer loop: process each node
2882     MarkerMap::iterator end = m_markers.end();
2883     for (MarkerMap::iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
2884         // inner loop; process each marker in this node
2885         MarkerMapVectorPair* vectorPair = nodeIterator->second;
2886         Vector<DocumentMarker>& markers = vectorPair->first;
2887         Vector<IntRect>& rects = vectorPair->second;
2888         ASSERT(markers.size() == rects.size());
2889         unsigned markerCount = markers.size();
2890         for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
2891             DocumentMarker marker = markers[markerIndex];
2892             
2893             // skip marker that is wrong type
2894             if (marker.type != markerType && markerType != DocumentMarker::AllMarkers)
2895                 continue;
2896             
2897             IntRect r = rects[markerIndex];
2898             // skip placeholder rects
2899             if (r == placeholderRectForMarker())
2900                 continue;
2901
2902             result.append(r);
2903         }
2904     }
2905     
2906     return result;
2907 }
2908
2909
2910 void Document::removeMarkers(Node* node)
2911 {
2912     MarkerMap::iterator i = m_markers.find(node);
2913     if (i != m_markers.end()) {
2914         delete i->second;
2915         m_markers.remove(i);
2916         if (RenderObject* renderer = node->renderer())
2917             renderer->repaint();
2918     }
2919 }
2920
2921 void Document::removeMarkers(DocumentMarker::MarkerType markerType)
2922 {
2923     // outer loop: process each markered node in the document
2924     MarkerMap markerMapCopy = m_markers;
2925     MarkerMap::iterator end = markerMapCopy.end();
2926     for (MarkerMap::iterator i = markerMapCopy.begin(); i != end; ++i) {
2927         Node* node = i->first.get();
2928         bool nodeNeedsRepaint = false;
2929
2930         // inner loop: process each marker in the current node
2931         MarkerMapVectorPair* vectorPair = i->second;
2932         Vector<DocumentMarker>& markers = vectorPair->first;
2933         Vector<IntRect>& rects = vectorPair->second;
2934         ASSERT(markers.size() == rects.size());
2935         Vector<DocumentMarker>::iterator markerIterator;
2936         for (markerIterator = markers.begin(); markerIterator != markers.end();) {
2937             DocumentMarker marker = *markerIterator;
2938
2939             // skip nodes that are not of the specified type
2940             if (marker.type != markerType && markerType != DocumentMarker::AllMarkers) {
2941                 ++markerIterator;
2942                 continue;
2943             }
2944
2945             // pitch the old marker
2946             markers.remove(markerIterator - markers.begin());
2947             rects.remove(markerIterator - markers.begin());
2948             nodeNeedsRepaint = true;
2949             // markerIterator now points to the next node
2950         }
2951
2952         // Redraw the node if it changed. Do this before the node is removed from m_markers, since 
2953         // m_markers might contain the last reference to the node.
2954         if (nodeNeedsRepaint) {
2955             RenderObject* renderer = node->renderer();
2956             if (renderer)
2957                 renderer->repaint();
2958         }
2959
2960         // delete the node's list if it is now empty
2961         if (markers.isEmpty()) {
2962             ASSERT(rects.isEmpty());
2963             m_markers.remove(node);
2964             delete vectorPair;
2965         }
2966     }
2967 }
2968
2969 void Document::repaintMarkers(DocumentMarker::MarkerType markerType)
2970 {
2971     // outer loop: process each markered node in the document
2972     MarkerMap::iterator end = m_markers.end();
2973     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
2974         Node* node = i->first.get();
2975         
2976         // inner loop: process each marker in the current node
2977         MarkerMapVectorPair* vectorPair = i->second;
2978         Vector<DocumentMarker>& markers = vectorPair->first;
2979         Vector<DocumentMarker>::iterator markerIterator;
2980         bool nodeNeedsRepaint = false;
2981         for (markerIterator = markers.begin(); markerIterator != markers.end(); ++markerIterator) {
2982             DocumentMarker marker = *markerIterator;
2983             
2984             // skip nodes that are not of the specified type
2985             if (marker.type == markerType || markerType == DocumentMarker::AllMarkers) {
2986                 nodeNeedsRepaint = true;
2987                 break;
2988             }
2989         }
2990         
2991         if (!nodeNeedsRepaint)
2992             continue;
2993         
2994         // cause the node to be redrawn
2995         if (RenderObject* renderer = node->renderer())
2996             renderer->repaint();
2997     }
2998 }
2999
3000 void Document::setRenderedRectForMarker(Node* node, DocumentMarker marker, const IntRect& r)
3001 {
3002     MarkerMapVectorPair* vectorPair = m_markers.get(node);
3003     if (!vectorPair) {
3004         ASSERT_NOT_REACHED(); // shouldn't be trying to set the rect for a marker we don't already know about
3005         return;
3006     }
3007     
3008     Vector<DocumentMarker>& markers = vectorPair->first;
3009     ASSERT(markers.size() == vectorPair->second.size());
3010     unsigned markerCount = markers.size();
3011     for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
3012         DocumentMarker m = markers[markerIndex];
3013         if (m == marker) {
3014             vectorPair->second[markerIndex] = r;
3015             return;
3016         }
3017     }
3018     
3019     ASSERT_NOT_REACHED(); // shouldn't be trying to set the rect for a marker we don't already know about
3020 }
3021
3022 void Document::invalidateRenderedRectsForMarkersInRect(const IntRect& r)
3023 {
3024     // outer loop: process each markered node in the document
3025     MarkerMap::iterator end = m_markers.end();
3026     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
3027         
3028         // inner loop: process each rect in the current node
3029         MarkerMapVectorPair* vectorPair = i->second;
3030         Vector<IntRect>& rects = vectorPair->second;
3031         
3032         unsigned rectCount = rects.size();
3033         for (unsigned rectIndex = 0; rectIndex < rectCount; ++rectIndex)
3034             if (rects[rectIndex].intersects(r))
3035                 rects[rectIndex] = placeholderRectForMarker();
3036     }
3037 }
3038
3039 void Document::shiftMarkers(Node *node, unsigned startOffset, int delta, DocumentMarker::MarkerType markerType)
3040 {
3041     MarkerMapVectorPair* vectorPair = m_markers.get(node);
3042     if (!vectorPair)
3043         return;
3044     
3045     Vector<DocumentMarker>& markers = vectorPair->first;
3046     Vector<IntRect>& rects = vectorPair->second;
3047     ASSERT(markers.size() == rects.size());
3048     
3049     bool docDirty = false;
3050     Vector<DocumentMarker>::iterator it;
3051     for (it = markers.begin(); it != markers.end(); ++it) {
3052         DocumentMarker &marker = *it;
3053         if (marker.startOffset >= startOffset && (markerType == DocumentMarker::AllMarkers || marker.type == markerType)) {
3054             assert((int)marker.startOffset + delta >= 0);
3055             marker.startOffset += delta;
3056             marker.endOffset += delta;
3057             docDirty = true;
3058             
3059             // Marker moved, so previously-computed rendered rectangle is now invalid
3060             rects[it - markers.begin()] = placeholderRectForMarker();
3061         }
3062     }
3063     
3064     // repaint the affected node
3065     if (docDirty && node->renderer())
3066         node->renderer()->repaint();
3067 }
3068
3069 #ifdef KHTML_XSLT
3070
3071 void Document::applyXSLTransform(ProcessingInstruction* pi)
3072 {
3073     RefPtr<XSLTProcessor> processor = new XSLTProcessor;
3074     processor->setXSLStylesheet(static_cast<XSLStyleSheet*>(pi->sheet()));
3075     
3076     DeprecatedString resultMIMEType;
3077     DeprecatedString newSource;
3078     DeprecatedString resultEncoding;
3079     if (!processor->transformToString(this, resultMIMEType, newSource, resultEncoding))
3080         return;
3081     // FIXME: If the transform failed we should probably report an error (like Mozilla does).
3082     processor->createDocumentFromSource(newSource, resultEncoding, resultMIMEType, this, view());
3083 }
3084
3085 #endif
3086
3087 void Document::setDesignMode(InheritedBool value)
3088 {
3089     m_designMode = value;
3090 }
3091
3092 Document::InheritedBool Document::getDesignMode() const
3093 {
3094     return m_designMode;
3095 }
3096
3097 bool Document::inDesignMode() const
3098 {
3099     for (const Document* d = this; d; d = d->parentDocument()) {
3100         if (d->m_designMode != inherit)
3101             return d->m_designMode;
3102     }
3103     return false;
3104 }
3105
3106 Document *Document::parentDocument() const
3107 {
3108     Frame *childPart = frame();
3109     if (!childPart)
3110         return 0;
3111     Frame *parent = childPart->tree()->parent();
3112     if (!parent)
3113         return 0;
3114     return parent->document();
3115 }
3116
3117 Document *Document::topDocument() const
3118 {
3119     Document *doc = const_cast<Document *>(this);
3120     Element *element;
3121     while ((element = doc->ownerElement()) != 0)
3122         doc = element->document();
3123     
3124     return doc;
3125 }
3126
3127 PassRefPtr<Attr> Document::createAttributeNS(const String &namespaceURI, const String &qualifiedName, ExceptionCode& ec)
3128 {
3129     if (qualifiedName.isNull()) {
3130         ec = NAMESPACE_ERR;
3131         return 0;
3132     }
3133
3134     String localName = qualifiedName;
3135     String prefix;
3136     int colonpos;
3137     if ((colonpos = qualifiedName.find(':')) >= 0) {
3138         prefix = qualifiedName.copy();
3139         localName = qualifiedName.copy();
3140         prefix.truncate(colonpos);
3141         localName.remove(0, colonpos+1);
3142     }
3143
3144     if (!isValidName(localName)) {
3145         ec = INVALID_CHARACTER_ERR;
3146         return 0;
3147     }
3148     
3149     // FIXME: Assume this is a mapped attribute, since createAttribute isn't namespace-aware.  There's no harm to XML
3150     // documents if we're wrong.
3151     return new Attr(0, this, new MappedAttribute(QualifiedName(prefix.impl(), 
3152                                                                        localName.impl(),
3153                                                                        namespaceURI.impl()), String("").impl()));
3154 }
3155
3156 #if SVG_SUPPORT
3157 const SVGDocumentExtensions* Document::svgExtensions()
3158 {
3159     return m_svgExtensions;
3160 }
3161
3162 SVGDocumentExtensions* Document::accessSVGExtensions()
3163 {
3164     if (!m_svgExtensions)
3165         m_svgExtensions = new SVGDocumentExtensions(this);
3166     return m_svgExtensions;
3167 }
3168 #endif
3169
3170 void Document::radioButtonChecked(HTMLInputElement *caller, HTMLFormElement *form)
3171 {
3172     // Without a name, there is no group.
3173     if (caller->name().isEmpty())
3174         return;
3175     if (!form)
3176         form = defaultForm;
3177     // Uncheck the currently selected item
3178     NameToInputMap* formRadioButtons = m_selectedRadioButtons.get(form);
3179     if (!formRadioButtons) {
3180         formRadioButtons = new NameToInputMap;
3181         m_selectedRadioButtons.set(form, formRadioButtons);
3182     }
3183     
3184     HTMLInputElement* currentCheckedRadio = formRadioButtons->get(caller->name().impl());
3185     if (currentCheckedRadio && currentCheckedRadio != caller)
3186         currentCheckedRadio->setChecked(false);
3187
3188     formRadioButtons->set(caller->name().impl(), caller);
3189 }
3190
3191 HTMLInputElement* Document::checkedRadioButtonForGroup(AtomicStringImpl* name, HTMLFormElement *form)
3192 {
3193     if (!form)
3194         form = defaultForm;
3195     NameToInputMap* formRadioButtons = m_selectedRadioButtons.get(form);
3196     if (!formRadioButtons)
3197         return 0;
3198     
3199     return formRadioButtons->get(name);
3200 }
3201
3202 void Document::removeRadioButtonGroup(AtomicStringImpl* name, HTMLFormElement *form)
3203 {
3204     if (!form)
3205         form = defaultForm;
3206     NameToInputMap* formRadioButtons = m_selectedRadioButtons.get(form);
3207     if (formRadioButtons) {
3208         formRadioButtons->remove(name);
3209         if (formRadioButtons->isEmpty()) {
3210             m_selectedRadioButtons.remove(form);
3211             delete formRadioButtons;
3212         }
3213     }
3214 }
3215
3216 PassRefPtr<HTMLCollection> Document::images()
3217 {
3218     return new HTMLCollection(this, HTMLCollection::DocImages);
3219 }
3220
3221 PassRefPtr<HTMLCollection> Document::applets()
3222 {
3223     return new HTMLCollection(this, HTMLCollection::DocApplets);
3224 }
3225
3226 PassRefPtr<HTMLCollection> Document::embeds()
3227 {
3228     return new HTMLCollection(this, HTMLCollection::DocEmbeds);
3229 }
3230
3231 PassRefPtr<HTMLCollection> Document::objects()
3232 {
3233     return new HTMLCollection(this, HTMLCollection::DocObjects);
3234 }
3235
3236 PassRefPtr<HTMLCollection> Document::scripts()
3237 {
3238     return new HTMLCollection(this, HTMLCollection::DocScripts);
3239 }
3240
3241 PassRefPtr<HTMLCollection> Document::links()
3242 {
3243     return new HTMLCollection(this, HTMLCollection::DocLinks);
3244 }
3245
3246 PassRefPtr<HTMLCollection> Document::forms()
3247 {
3248     return new HTMLCollection(this, HTMLCollection::DocForms);
3249 }
3250
3251 PassRefPtr<HTMLCollection> Document::anchors()
3252 {
3253     return new HTMLCollection(this, HTMLCollection::DocAnchors);
3254 }
3255
3256 PassRefPtr<HTMLCollection> Document::all()
3257 {
3258     return new HTMLCollection(this, HTMLCollection::DocAll);
3259 }
3260
3261 PassRefPtr<HTMLCollection> Document::windowNamedItems(const String &name)
3262 {
3263     return new HTMLNameCollection(this, HTMLCollection::WindowNamedItems, name);
3264 }
3265
3266 PassRefPtr<HTMLCollection> Document::documentNamedItems(const String &name)
3267 {
3268     return new HTMLNameCollection(this, HTMLCollection::DocumentNamedItems, name);
3269 }
3270
3271 HTMLCollection::CollectionInfo* Document::nameCollectionInfo(HTMLCollection::Type type, const String& name)
3272 {
3273     HashMap<AtomicStringImpl*, HTMLCollection::CollectionInfo>& map = m_nameCollectionInfo[type - HTMLCollection::UnnamedCollectionTypes];
3274     
3275     AtomicString atomicName(name);
3276     
3277     HashMap<AtomicStringImpl*, HTMLCollection::CollectionInfo>::iterator iter = map.find(atomicName.impl());
3278     if (iter == map.end())
3279         iter = map.add(atomicName.impl(), HTMLCollection::CollectionInfo()).first;
3280     
3281     return &iter->second;
3282 }
3283
3284 PassRefPtr<NameNodeList> Document::getElementsByName(const String &elementName)
3285 {
3286     return new NameNodeList(this, elementName);
3287 }
3288
3289 void Document::finishedParsing()
3290 {
3291     setParsing(false);
3292     if (Frame* f = frame())
3293         f->finishedParsing();
3294 }
3295
3296 Vector<String> Document::formElementsState() const
3297 {
3298     Vector<String> stateVector;
3299     stateVector.reserveCapacity(m_formElementsWithState.size() * 3);
3300     typedef HashSet<HTMLGenericFormElement*>::const_iterator Iterator;
3301     Iterator end = m_formElementsWithState.end();
3302     for (Iterator it = m_formElementsWithState.begin(); it != end; ++it) {
3303         HTMLGenericFormElement* e = *it;
3304         stateVector.append(e->name().domString());
3305         stateVector.append(e->type().domString());
3306         stateVector.append(e->stateValue());
3307     }
3308     return stateVector;
3309 }
3310
3311 #if XPATH_SUPPORT
3312
3313 PassRefPtr<XPathExpression> Document::createExpression(const String& expression,
3314                                                        XPathNSResolver* resolver,
3315                                                        ExceptionCode& ec)
3316 {
3317     if (!m_xpathEvaluator)
3318         m_xpathEvaluator = new XPathEvaluator;
3319     return m_xpathEvaluator->createExpression(expression, resolver, ec);
3320 }
3321
3322 PassRefPtr<XPathNSResolver> Document::createNSResolver(Node* nodeResolver)
3323 {
3324     if (!m_xpathEvaluator)
3325         m_xpathEvaluator = new XPathEvaluator;
3326     return m_xpathEvaluator->createNSResolver(nodeResolver);
3327 }
3328
3329 PassRefPtr<XPathResult> Document::evaluate(const String& expression,
3330                                            Node* contextNode,
3331                                            XPathNSResolver* resolver,
3332                                            unsigned short type,
3333                                            XPathResult* result,
3334                                            ExceptionCode& ec)
3335 {
3336     if (!m_xpathEvaluator)
3337         m_xpathEvaluator = new XPathEvaluator;
3338     return m_xpathEvaluator->evaluate(expression, contextNode, resolver, type, result, ec);
3339 }
3340
3341 #endif // XPATH_SUPPORT
3342
3343 void Document::setStateForNewFormElements(const Vector<String>& stateVector)
3344 {
3345     // Walk the state vector backwards so that the value to use for each
3346     // name/type pair first is the one at the end of each individual vector
3347     // in the FormElementStateMap. We're using them like stacks.
3348     typedef FormElementStateMap::iterator Iterator;
3349     m_formElementsWithState.clear();
3350     for (size_t i = stateVector.size() / 3 * 3; i; i -= 3) {
3351         AtomicString a = stateVector[i - 3];
3352         AtomicString b = stateVector[i - 2];
3353         const String& c = stateVector[i - 1];
3354         FormElementKey key(a.impl(), b.impl());
3355         Iterator it = m_stateForNewFormElements.find(key);
3356         if (it != m_stateForNewFormElements.end())
3357             it->second.append(c);
3358         else {
3359             Vector<String> v(1);
3360             v[0] = c;
3361             m_stateForNewFormElements.set(key, v);
3362         }
3363     }
3364 }
3365
3366 bool Document::hasStateForNewFormElements() const
3367 {
3368     return !m_stateForNewFormElements.isEmpty();
3369 }
3370
3371 bool Document::takeStateForFormElement(AtomicStringImpl* name, AtomicStringImpl* type, String& state)
3372 {
3373     typedef FormElementStateMap::iterator Iterator;
3374     Iterator it = m_stateForNewFormElements.find(FormElementKey(name, type));
3375     if (it == m_stateForNewFormElements.end())
3376         return false;
3377     ASSERT(it->second.size());
3378     state = it->second.last();
3379     if (it->second.size() > 1)
3380         it->second.removeLast();
3381     else
3382         m_stateForNewFormElements.remove(it);
3383     return true;
3384 }
3385
3386 FormElementKey::FormElementKey(AtomicStringImpl* name, AtomicStringImpl* type)
3387     : m_name(name), m_type(type)
3388 {
3389     ref();
3390 }
3391
3392 FormElementKey::~FormElementKey()
3393 {
3394     deref();
3395 }
3396
3397 FormElementKey::FormElementKey(const FormElementKey& other)
3398     : m_name(other.name()), m_type(other.type())
3399 {
3400     ref();
3401 }
3402
3403 FormElementKey& FormElementKey::operator=(const FormElementKey& other)
3404 {
3405     other.ref();
3406     deref();
3407     m_name = other.name();
3408     m_type = other.type();
3409     return *this;
3410 }
3411
3412 void FormElementKey::ref() const
3413 {
3414     if (name() && name() != HashTraits<AtomicStringImpl*>::deletedValue())
3415         name()->ref();
3416     if (type())
3417         type()->ref();
3418 }
3419
3420 void FormElementKey::deref() const
3421 {
3422     if (name() && name() != HashTraits<AtomicStringImpl*>::deletedValue())
3423         name()->deref();
3424     if (type())
3425         type()->deref();
3426 }
3427
3428 unsigned FormElementKeyHash::hash(const FormElementKey& k)
3429 {
3430     ASSERT(sizeof(k) % (sizeof(uint16_t) * 2) == 0);
3431
3432     unsigned l = sizeof(k) / (sizeof(uint16_t) * 2);
3433     const uint16_t* s = reinterpret_cast<const uint16_t*>(&k);
3434     uint32_t hash = PHI;
3435
3436     // Main loop
3437     for (; l > 0; l--) {
3438         hash += s[0];
3439         uint32_t tmp = (s[1] << 11) ^ hash;
3440         hash = (hash << 16) ^ tmp;
3441         s += 2;
3442         hash += hash >> 11;
3443     }
3444         
3445     // Force "avalanching" of final 127 bits
3446     hash ^= hash << 3;
3447     hash += hash >> 5;
3448     hash ^= hash << 2;
3449     hash += hash >> 15;
3450     hash ^= hash << 10;
3451
3452     // this avoids ever returning a hash code of 0, since that is used to
3453     // signal "hash not computed yet", using a value that is likely to be
3454     // effectively the same as 0 when the low bits are masked
3455     if (hash == 0)
3456         hash = 0x80000000;
3457
3458     return hash;
3459 }
3460
3461 FormElementKey FormElementKeyHashTraits::deletedValue()
3462 {
3463     return HashTraits<AtomicStringImpl*>::deletedValue();
3464 }
3465
3466 }