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