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