WebCore/dom/Document.cpp

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