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