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