c3a7153cae45ad601a85c85099e3f151899727c9
[WebKit-https.git] / Source / WebCore / html / HTMLCollection.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, 2008, 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 "HTMLCollection.h"
25
26 #include "HTMLDocument.h"
27 #include "HTMLElement.h"
28 #include "HTMLNames.h"
29 #include "HTMLObjectElement.h"
30 #include "HTMLOptionElement.h"
31 #include "NodeList.h"
32
33 #include <utility>
34
35 namespace WebCore {
36
37 using namespace HTMLNames;
38
39 HTMLCollection::HTMLCollection(Node* base, CollectionType type)
40     : m_includeChildren(shouldIncludeChildren(type))
41     , m_type(type)
42     , m_base(base)
43 {
44     ASSERT(m_base);
45     m_cache.clear();
46 }
47
48 bool HTMLCollection::shouldIncludeChildren(CollectionType type)
49 {
50     switch (type) {
51     case DocAll:
52     case DocAnchors:
53     case DocApplets:
54     case DocEmbeds:
55     case DocForms:
56     case DocImages:
57     case DocLinks:
58     case DocObjects:
59     case DocScripts:
60     case DocumentNamedItems:
61     case MapAreas:
62     case OtherCollection:
63     case SelectOptions:
64     case SelectedOptions:
65     case DataListOptions:
66     case WindowNamedItems:
67 #if ENABLE(MICRODATA)
68     case ItemProperties:
69 #endif
70         return true;
71     case NodeChildren:
72     case TRCells:
73     case TSectionRows:
74     case TableTBodies:
75         return false;
76     }
77     ASSERT_NOT_REACHED();
78     return false;
79 }
80
81 PassOwnPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
82 {
83     return adoptPtr(new HTMLCollection(base, type));
84 }
85
86 HTMLCollection::~HTMLCollection()
87 {
88 }
89
90 void HTMLCollection::invalidateCacheIfNeeded() const
91 {
92     uint64_t docversion = static_cast<HTMLDocument*>(m_base->document())->domTreeVersion();
93
94     if (m_cache.version == docversion)
95         return;
96
97     m_cache.clear();
98     m_cache.version = docversion;
99 }
100
101 inline bool HTMLCollection::isAcceptableElement(Element* element) const
102 {
103     switch (m_type) {
104     case DocImages:
105         return element->hasLocalName(imgTag);
106     case DocScripts:
107         return element->hasLocalName(scriptTag);
108     case DocForms:
109         return element->hasLocalName(formTag);
110     case TableTBodies:
111         return element->hasLocalName(tbodyTag);
112     case TRCells:
113         return element->hasLocalName(tdTag) || element->hasLocalName(thTag);
114     case TSectionRows:
115         return element->hasLocalName(trTag);
116     case SelectOptions:
117         return element->hasLocalName(optionTag);
118     case SelectedOptions:
119         if (element->hasLocalName(optionTag)) {
120             HTMLOptionElement* option = static_cast<HTMLOptionElement*>(element);
121             if (option->selected())
122                 return true;
123         }
124         return false;
125     case DataListOptions:
126         if (element->hasLocalName(optionTag)) {
127             HTMLOptionElement* option = static_cast<HTMLOptionElement*>(element);
128             if (!option->disabled() && !option->value().isEmpty())
129                 return true;
130         }
131         return false;
132     case MapAreas:
133         return element->hasLocalName(areaTag);
134     case DocApplets:
135         return element->hasLocalName(appletTag) || (element->hasLocalName(objectTag) && static_cast<HTMLObjectElement*>(element)->containsJavaApplet());
136     case DocEmbeds:
137         return element->hasLocalName(embedTag);
138     case DocObjects:
139         return element->hasLocalName(objectTag);
140     case DocLinks:
141         return (element->hasLocalName(aTag) || element->hasLocalName(areaTag)) && element->fastHasAttribute(hrefAttr);
142     case DocAnchors:
143         return element->hasLocalName(aTag) && element->fastHasAttribute(nameAttr);
144     case DocAll:
145     case NodeChildren:
146         return true;
147 #if ENABLE(MICRODATA)
148     case ItemProperties:
149         return element->isHTMLElement() && element->fastHasAttribute(itempropAttr);
150 #endif
151     case DocumentNamedItems:
152     case OtherCollection:
153     case WindowNamedItems:
154         ASSERT_NOT_REACHED();
155     }
156     return false;
157 }
158
159 static Node* nextNodeOrSibling(Node* base, Node* node, bool includeChildren)
160 {
161     return includeChildren ? node->traverseNextNode(base) : node->traverseNextSibling(base);
162 }
163
164 Element* HTMLCollection::itemAfter(Element* previous) const
165 {
166     Node* current;
167     if (!previous)
168         current = m_base->firstChild();
169     else
170         current = nextNodeOrSibling(m_base, previous, m_includeChildren);
171
172     for (; current; current = nextNodeOrSibling(m_base, current, m_includeChildren)) {
173         if (!current->isElementNode())
174             continue;
175         Element* element = static_cast<Element*>(current);
176         if (isAcceptableElement(element))
177             return element;
178     }
179
180     return 0;
181 }
182
183 unsigned HTMLCollection::calcLength() const
184 {
185     unsigned len = 0;
186     for (Element* current = itemAfter(0); current; current = itemAfter(current))
187         ++len;
188     return len;
189 }
190
191 // since the collections are to be "live", we have to do the
192 // calculation every time if anything has changed
193 unsigned HTMLCollection::length() const
194 {
195     invalidateCacheIfNeeded();
196     if (!m_cache.hasLength) {
197         m_cache.length = calcLength();
198         m_cache.hasLength = true;
199     }
200     return m_cache.length;
201 }
202
203 Node* HTMLCollection::item(unsigned index) const
204 {
205      invalidateCacheIfNeeded();
206      if (m_cache.current && m_cache.position == index)
207          return m_cache.current;
208      if (m_cache.hasLength && m_cache.length <= index)
209          return 0;
210      if (!m_cache.current || m_cache.position > index) {
211          m_cache.current = itemAfter(0);
212          m_cache.position = 0;
213          if (!m_cache.current)
214              return 0;
215      }
216      Element* e = m_cache.current;
217      for (unsigned pos = m_cache.position; e && pos < index; pos++)
218          e = itemAfter(e);
219      m_cache.current = e;
220      m_cache.position = index;
221      return m_cache.current;
222 }
223
224 Node* HTMLCollection::firstItem() const
225 {
226      return item(0);
227 }
228
229 Node* HTMLCollection::nextItem() const
230 {
231      invalidateCacheIfNeeded();
232
233      // Look for the 'second' item. The first one is currentItem, already given back.
234      Element* retval = itemAfter(m_cache.current);
235      m_cache.current = retval;
236      m_cache.position++;
237      return retval;
238 }
239
240 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
241 {
242     // The document.all collection returns only certain types of elements by name,
243     // although it returns any type of element by id.
244     return element->hasLocalName(appletTag)
245         || element->hasLocalName(embedTag)
246         || element->hasLocalName(formTag)
247         || element->hasLocalName(imgTag)
248         || element->hasLocalName(inputTag)
249         || element->hasLocalName(objectTag)
250         || element->hasLocalName(selectTag);
251 }
252
253 bool HTMLCollection::checkForNameMatch(Element* element, bool checkName, const AtomicString& name) const
254 {
255     if (!element->isHTMLElement())
256         return false;
257     
258     HTMLElement* e = toHTMLElement(element);
259     if (!checkName)
260         return e->getIdAttribute() == name;
261
262     if (m_type == DocAll && !nameShouldBeVisibleInDocumentAll(e))
263         return false;
264
265     return e->getNameAttribute() == name && e->getIdAttribute() != name;
266 }
267
268 Node* HTMLCollection::namedItem(const AtomicString& name) const
269 {
270     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
271     // This method first searches for an object with a matching id
272     // attribute. If a match is not found, the method then searches for an
273     // object with a matching name attribute, but only on those elements
274     // that are allowed a name attribute.
275     invalidateCacheIfNeeded();
276
277     for (Element* e = itemAfter(0); e; e = itemAfter(e)) {
278         if (checkForNameMatch(e, /* checkName */ false, name)) {
279             m_cache.current = e;
280             return e;
281         }
282     }
283
284     for (Element* e = itemAfter(0); e; e = itemAfter(e)) {
285         if (checkForNameMatch(e, /* checkName */ true, name)) {
286             m_cache.current = e;
287             return e;
288         }
289     }
290
291     m_cache.current = 0;
292     return 0;
293 }
294
295 void HTMLCollection::updateNameCache() const
296 {
297     if (m_cache.hasNameCache)
298         return;
299
300     for (Element* element = itemAfter(0); element; element = itemAfter(element)) {
301         if (!element->isHTMLElement())
302             continue;
303         HTMLElement* e = toHTMLElement(element);
304         const AtomicString& idAttrVal = e->getIdAttribute();
305         const AtomicString& nameAttrVal = e->getNameAttribute();
306         if (!idAttrVal.isEmpty())
307             append(m_cache.idCache, idAttrVal, e);
308         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (m_type != DocAll || nameShouldBeVisibleInDocumentAll(e)))
309             append(m_cache.nameCache, nameAttrVal, e);
310     }
311
312     m_cache.hasNameCache = true;
313 }
314
315 bool HTMLCollection::hasNamedItem(const AtomicString& name) const
316 {
317     if (name.isEmpty())
318         return false;
319
320     invalidateCacheIfNeeded();
321     updateNameCache();
322
323     if (Vector<Element*>* idCache = m_cache.idCache.get(name.impl())) {
324         if (!idCache->isEmpty())
325             return true;
326     }
327
328     if (Vector<Element*>* nameCache = m_cache.nameCache.get(name.impl())) {
329         if (!nameCache->isEmpty())
330             return true;
331     }
332
333     return false;
334 }
335
336 void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Node> >& result) const
337 {
338     ASSERT(result.isEmpty());
339     if (name.isEmpty())
340         return;
341
342     invalidateCacheIfNeeded();
343     updateNameCache();
344
345     Vector<Element*>* idResults = m_cache.idCache.get(name.impl());
346     Vector<Element*>* nameResults = m_cache.nameCache.get(name.impl());
347
348     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
349         result.append(idResults->at(i));
350
351     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
352         result.append(nameResults->at(i));
353 }
354
355 PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
356 {
357     return m_base->getElementsByTagName(name);
358 }
359
360 void HTMLCollection::append(NodeCacheMap& map, const AtomicString& key, Element* element)
361 {
362     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).iterator->second;
363     if (!vector)
364         vector = adoptPtr(new Vector<Element*>);
365     vector->append(element);
366 }
367
368 } // namespace WebCore