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