Build HTMLFormElement::m_associatedElements lazily

Source/core/html/HTMLFormElement.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
  *           (C) 2006 Alexey Proskuryakov (ap@nypop.com)
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
@@ skipping 14 matching lines @@
 #include "config.h"
 #include "core/html/HTMLFormElement.h"
 
 #include <limits>
 #include "HTMLNames.h"
 #include "bindings/v8/ScriptController.h"
 #include "bindings/v8/ScriptEventListener.h"
 #include "core/dom/Attribute.h"
 #include "core/dom/Document.h"
 #include "core/dom/ElementTraversal.h"
+#include "core/dom/IdTargetObserverRegistry.h"
 #include "core/events/AutocompleteErrorEvent.h"
 #include "core/events/Event.h"
 #include "core/events/ScopedEventQueue.h"
 #include "core/events/ThreadLocalEventNames.h"
 #include "core/html/HTMLCollection.h"
 #include "core/html/HTMLDialogElement.h"
 #include "core/html/HTMLImageElement.h"
 #include "core/html/HTMLInputElement.h"
 #include "core/html/HTMLObjectElement.h"
 #include "core/html/RadioNodeList.h"
 #include "core/html/forms/FormController.h"
 #include "core/loader/FrameLoader.h"
 #include "core/loader/FrameLoaderClient.h"
 #include "core/frame/ContentSecurityPolicy.h"
 #include "core/frame/DOMWindow.h"
 #include "core/frame/Frame.h"
 #include "core/frame/UseCounter.h"
 #include "core/rendering/RenderTextControl.h"
 #include "platform/UserGestureIndicator.h"
 
 using namespace std;
 
 namespace WebCore {
 
 using namespace HTMLNames;
 
 HTMLFormElement::HTMLFormElement(Document& document)
     : HTMLElement(formTag, document)
-    , m_associatedElementsBeforeIndex(0)
-    , m_associatedElementsAfterIndex(0)
     , m_weakPtrFactory(this)
+    , m_associatedElementsAreDirty(false)
     , m_imageElementsAreDirty(false)
     , m_hasElementsAssociatedByParser(false)
     , m_didFinishParsingChildren(false)
     , m_wasUserSubmitted(false)
     , m_isSubmittingOrPreparingForSubmission(false)
     , m_shouldSubmit(false)
     , m_isInResetFunction(false)
     , m_wasDemoted(false)
     , m_requestAutocompleteTimer(this, &HTMLFormElement::requestAutocompleteTimerFired)
 {
@@ skipping 45 matching lines @@
         this->document().didAssociateFormControl(this);
     return InsertionDone;
 }
 
 template<class T>
 void notifyFormRemovedFromTree(const Vector<T*>& elements, Node* root)
 {
     size_t size = elements.size();
     for (size_t i = 0; i < size; ++i)
         elements[i]->formRemovedFromTree(root);
+    ASSERT(elements.size() == size);
 }
 
 void HTMLFormElement::removedFrom(ContainerNode* insertionPoint)
 {
-    // FIXME: We don't need to notify formRemovedFromTree to associated elements
-    // which are descendants of this form. We can skip this process if we know
-    // that this form doesn't have elements associated by parser or associated
-    // with 'form' content attribute.
-    Node* root = highestAncestor();
-    Vector<FormAssociatedElement*> elements(associatedElements());
-    notifyFormRemovedFromTree(elements, root);
+    // We don't need to take care of form association by 'form' content
+    // attribute becuse IdTargetObserver handles it.
+    if (m_hasElementsAssociatedByParser) {
+        Node* root = highestAncestor();
+        if (!m_associatedElementsAreDirty) {
+            Vector<FormAssociatedElement*> elements(associatedElements());
+            notifyFormRemovedFromTree(elements, root);
+        } else {
+            Vector<FormAssociatedElement*> elements;
+            collectAssociatedElements(insertionPoint->highestAncestor(), elements);
+            notifyFormRemovedFromTree(elements, root);
+            collectAssociatedElements(root, elements);
+            notifyFormRemovedFromTree(elements, root);
+        }
 
-    if (m_hasElementsAssociatedByParser) {
         if (!m_imageElementsAreDirty) {
             Vector<HTMLImageElement*> images(imageElements());
             notifyFormRemovedFromTree(images, root);
         } else {
             Vector<HTMLImageElement*> images;
             collectImageElements(insertionPoint->highestAncestor(), images);
             notifyFormRemovedFromTree(images, root);
             collectImageElements(root, images);
             notifyFormRemovedFromTree(images, root);
         }
@@ skipping 359 matching lines @@
     else if (name == accept_charsetAttr)
         m_attributes.setAcceptCharset(value);
     else if (name == onautocompleteAttr)
         setAttributeEventListener(EventTypeNames::autocomplete, createAttributeEventListener(this, name, value));
     else if (name == onautocompleteerrorAttr)
         setAttributeEventListener(EventTypeNames::autocompleteerror, createAttributeEventListener(this, name, value));
     else
         HTMLElement::parseAttribute(name, value);
 }
 
-template<class T, size_t n> static void removeFromVector(Vector<T*, n> & vec, T* item)
-{
-    size_t size = vec.size();
-    for (size_t i = 0; i != size; ++i)
-        if (vec[i] == item) {
-            vec.remove(i);
-            break;
-        }
-}
-
-unsigned HTMLFormElement::formElementIndexWithFormAttribute(Element* element, unsigned rangeStart, unsigned rangeEnd)
-{
-    if (m_associatedElements.isEmpty())
-        return 0;
-
-    ASSERT(rangeStart <= rangeEnd);
-
-    if (rangeStart == rangeEnd)
-        return rangeStart;
-
-    unsigned left = rangeStart;
-    unsigned right = rangeEnd - 1;
-    unsigned short position;
-
-    // Does binary search on m_associatedElements in order to find the index
-    // to be inserted.
-    while (left != right) {
-        unsigned middle = left + ((right - left) / 2);
-        ASSERT(middle < m_associatedElementsBeforeIndex || middle >= m_associatedElementsAfterIndex);
-        position = element->compareDocumentPosition(toHTMLElement(m_associatedElements[middle]));
-        if (position & DOCUMENT_POSITION_FOLLOWING)
-            right = middle;
-        else
-            left = middle + 1;
-    }
-
-    ASSERT(left < m_associatedElementsBeforeIndex || left >= m_associatedElementsAfterIndex);
-    position = element->compareDocumentPosition(toHTMLElement(m_associatedElements[left]));
-    if (position & DOCUMENT_POSITION_FOLLOWING)
-        return left;
-    return left + 1;
-}
-
-unsigned HTMLFormElement::formElementIndex(FormAssociatedElement& associatedElement)
-{
-    HTMLElement& associatedHTMLElement = toHTMLElement(associatedElement);
-    // Treats separately the case where this element has the form attribute
-    // for performance consideration.
-    if (associatedHTMLElement.fastHasAttribute(formAttr)) {
-        unsigned short position = compareDocumentPosition(&associatedHTMLElement);
-        if (position & DOCUMENT_POSITION_PRECEDING) {
-            ++m_associatedElementsBeforeIndex;
-            ++m_associatedElementsAfterIndex;
-            return HTMLFormElement::formElementIndexWithFormAttribute(&associatedHTMLElement, 0, m_associatedElementsBeforeIndex - 1);
-        }
-        if (position & DOCUMENT_POSITION_FOLLOWING && !(position & DOCUMENT_POSITION_CONTAINED_BY))
-            return HTMLFormElement::formElementIndexWithFormAttribute(&associatedHTMLElement, m_associatedElementsAfterIndex, m_associatedElements.size());
-    }
-
-    // Check for the special case where this element is the very last thing in
-    // the form's tree of children; we don't want to walk the entire tree in that
-    // common case that occurs during parsing; instead we'll just return a value
-    // that says "add this form element to the end of the array".
-    if (ElementTraversal::next(associatedHTMLElement, this)) {
-        unsigned i = m_associatedElementsBeforeIndex;
-        for (Element* element = this; element; element = ElementTraversal::next(*element, this)) {
-            if (element == associatedHTMLElement) {
-                ++m_associatedElementsAfterIndex;
-                return i;
-            }
-            if (!element->isFormControlElement() && !element->hasTagName(objectTag))
-                continue;
-            if (!element->isHTMLElement() || toHTMLElement(element)->formOwner() != this)
-                continue;
-            ++i;
-        }
-    }
-    return m_associatedElementsAfterIndex++;
-}
-
 void HTMLFormElement::associate(FormAssociatedElement& e)
 {
-    m_associatedElements.insert(formElementIndex(e), &e);
+    m_associatedElementsAreDirty = true;
+    m_associatedElements.clear();
 }
 
 void HTMLFormElement::disassociate(FormAssociatedElement& e)
 {
-    unsigned index;
-    for (index = 0; index < m_associatedElements.size(); ++index) {
-        if (m_associatedElements[index] == &e)
-            break;
-    }
-    ASSERT_WITH_SECURITY_IMPLICATION(index < m_associatedElements.size());
-    if (index < m_associatedElementsBeforeIndex)
-        --m_associatedElementsBeforeIndex;
-    if (index < m_associatedElementsAfterIndex)
-        --m_associatedElementsAfterIndex;
+    m_associatedElementsAreDirty = true;
+    m_associatedElements.clear();
     removeFromPastNamesMap(toHTMLElement(e));
-    removeFromVector(m_associatedElements, &e);
 }
 
 bool HTMLFormElement::isURLAttribute(const Attribute& attribute) const
 {
     return attribute.name() == actionAttr || HTMLElement::isURLAttribute(attribute);
 }
 
 void HTMLFormElement::associate(HTMLImageElement& e)
 {
     m_imageElementsAreDirty = true;
@@ skipping 18 matching lines @@
         return;
     m_hasElementsAssociatedByParser = true;
     UseCounter::count(document(), UseCounter::FormAssociationByParser);
 }
 
 PassRefPtr<HTMLCollection> HTMLFormElement::elements()
 {
     return ensureCachedHTMLCollection(FormControls);
 }
 
+void HTMLFormElement::collectAssociatedElements(Node* root, Vector<FormAssociatedElement*>& elements) const
+{
+    elements.clear();
+    for (Node* node = root; node; node = NodeTraversal::next(*node)) {
+        if (!node->isHTMLElement())
+            continue;
+        FormAssociatedElement* element = 0;
+        if (toElement(node)->isFormControlElement())
+            element = toHTMLFormControlElement(node);
+        else if (node->hasTagName(objectTag))
+            element = toHTMLObjectElement(node);
+        else
+            continue;
+        if (element->form()== this)
+            elements.append(element);
+    }
+}
+
+// This function should be const conceptually. However we update some fields
+// because of lazy evaluation.
+const Vector<FormAssociatedElement*>& HTMLFormElement::associatedElements() const
+{
+    if (!m_associatedElementsAreDirty)
+        return m_associatedElements;
+    HTMLFormElement* mutableThis = const_cast<HTMLFormElement*>(this);
+    Node* scope = mutableThis;
+    if (m_hasElementsAssociatedByParser)
+        scope = highestAncestor();
+    if (inDocument() && treeScope().idTargetObserverRegistry().hasObservers(fastGetAttribute(idAttr)))
+        scope = &treeScope().rootNode();
+    collectAssociatedElements(scope, mutableThis->m_associatedElements);
+    mutableThis->m_associatedElementsAreDirty = false;
+    return m_associatedElements;
+}
+
 void HTMLFormElement::collectImageElements(Node* root, Vector<HTMLImageElement*>& elements)
 {
     elements.clear();
     for (Node* node = root; node; node = NodeTraversal::next(*node)) {
         if (node->isHTMLElement() && node->hasTagName(imgTag) && toHTMLElement(node)->formOwner() == this)
             elements.append(toHTMLImageElement(node));
     }
 }
 
 const Vector<HTMLImageElement*>& HTMLFormElement::imageElements()
@@ skipping 193 matching lines @@
 }
 
 void HTMLFormElement::setDemoted(bool demoted)
 {
     if (demoted)
         UseCounter::count(document(), UseCounter::DemotedFormElement);
     m_wasDemoted = demoted;
 }
 
 } // namespace