WebCore/dom/Document.cpp

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