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