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