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