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