Iterating backwards over HTMLCollection is O(n^2)
[WebKit-https.git] / Source / WebCore / html / HTMLFormCollection.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2010, 2011, 2012 Apple Inc. All rights reserved.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB.  If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  *
21  */
22
23 #include "config.h"
24 #include "HTMLFormCollection.h"
25
26 #include "HTMLFieldSetElement.h"
27 #include "HTMLFormControlElement.h"
28 #include "HTMLFormElement.h"
29 #include "HTMLImageElement.h"
30 #include "HTMLNames.h"
31
32 namespace WebCore {
33
34 using namespace HTMLNames;
35
36 // Since the collections are to be "live", we have to do the
37 // calculation every time if anything has changed.
38
39 HTMLFormCollection::HTMLFormCollection(Element* base)
40     : HTMLCollection(base, FormControls, DoNotSupportItemBefore)
41 {
42     ASSERT(base->hasTagName(formTag) || base->hasTagName(fieldsetTag));
43 }
44
45 PassRefPtr<HTMLFormCollection> HTMLFormCollection::create(Element* base)
46 {
47     return adoptRef(new HTMLFormCollection(base));
48 }
49
50 HTMLFormCollection::~HTMLFormCollection()
51 {
52 }
53
54 const Vector<FormAssociatedElement*>& HTMLFormCollection::formControlElements() const
55 {
56     ASSERT(base());
57     ASSERT(base()->hasTagName(formTag) || base()->hasTagName(fieldsetTag));
58     if (base()->hasTagName(formTag))
59         return static_cast<HTMLFormElement*>(base())->associatedElements();
60     return static_cast<HTMLFieldSetElement*>(base())->associatedElements();
61 }
62
63 const Vector<HTMLImageElement*>& HTMLFormCollection::formImageElements() const
64 {
65     ASSERT(base());
66     ASSERT(base()->hasTagName(formTag));
67     return static_cast<HTMLFormElement*>(base())->imageElements();
68 }
69
70 Element* HTMLFormCollection::itemAfter(unsigned& offset, Element* previousItem) const
71 {
72     const Vector<FormAssociatedElement*>& elementsArray = formControlElements();
73     if (previousItem)
74         offset++;
75     while (offset < elementsArray.size()) {
76         FormAssociatedElement* element = elementsArray[offset];
77         if (element->isEnumeratable())
78             return toHTMLElement(element);
79         offset++;
80     }
81     return 0;
82 }
83
84 static HTMLElement* firstNamedItem(const Vector<FormAssociatedElement*>& elementsArray,
85     const Vector<HTMLImageElement*>* imageElementsArray, const QualifiedName& attrName, const String& name)
86 {
87     ASSERT(attrName == idAttr || attrName == nameAttr);
88
89     for (unsigned i = 0; i < elementsArray.size(); ++i) {
90         HTMLElement* element = toHTMLElement(elementsArray[i]);
91         if (elementsArray[i]->isEnumeratable() && element->fastGetAttribute(attrName) == name)
92             return element;
93     }
94
95     if (!imageElementsArray)
96         return 0;
97
98     for (unsigned i = 0; i < imageElementsArray->size(); ++i) {
99         HTMLImageElement* element = (*imageElementsArray)[i];
100         if (element->fastGetAttribute(attrName) == name)
101             return element;
102     }
103
104     return 0;
105 }
106
107 Node* HTMLFormCollection::namedItem(const AtomicString& name) const
108 {
109     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
110     // This method first searches for an object with a matching id
111     // attribute. If a match is not found, the method then searches for an
112     // object with a matching name attribute, but only on those elements
113     // that are allowed a name attribute.
114     const Vector<HTMLImageElement*>* imagesElements = base()->hasTagName(fieldsetTag) ? 0 : &formImageElements();
115     if (HTMLElement* item = firstNamedItem(formControlElements(), imagesElements, idAttr, name))
116         return item;
117
118     return firstNamedItem(formControlElements(), imagesElements, nameAttr, name);
119 }
120
121 void HTMLFormCollection::updateNameCache() const
122 {
123     if (hasNameCache())
124         return;
125
126     HashSet<AtomicStringImpl*> foundInputElements;
127
128     const Vector<FormAssociatedElement*>& elementsArray = formControlElements();
129
130     for (unsigned i = 0; i < elementsArray.size(); ++i) {
131         FormAssociatedElement* associatedElement = elementsArray[i];
132         if (associatedElement->isEnumeratable()) {
133             HTMLElement* element = toHTMLElement(associatedElement);
134             const AtomicString& idAttrVal = element->getIdAttribute();
135             const AtomicString& nameAttrVal = element->getNameAttribute();
136             if (!idAttrVal.isEmpty()) {
137                 appendIdCache(idAttrVal, element);
138                 foundInputElements.add(idAttrVal.impl());
139             }
140             if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal) {
141                 appendNameCache(nameAttrVal, element);
142                 foundInputElements.add(nameAttrVal.impl());
143             }
144         }
145     }
146
147     if (base()->hasTagName(formTag)) {
148         const Vector<HTMLImageElement*>& imageElementsArray = formImageElements();
149         for (unsigned i = 0; i < imageElementsArray.size(); ++i) {
150             HTMLImageElement* element = imageElementsArray[i];
151             const AtomicString& idAttrVal = element->getIdAttribute();
152             const AtomicString& nameAttrVal = element->getNameAttribute();
153             if (!idAttrVal.isEmpty() && !foundInputElements.contains(idAttrVal.impl()))
154                 appendIdCache(idAttrVal, element);
155             if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && !foundInputElements.contains(nameAttrVal.impl()))
156                 appendNameCache(nameAttrVal, element);
157         }
158     }
159
160     setHasNameCache();
161 }
162
163 }