Iterating backwards over HTMLCollection is O(n^2)
[WebKit-https.git] / Source / WebCore / html / HTMLNameCollection.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, 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 "HTMLNameCollection.h"
25
26 #include "Element.h"
27 #include "HTMLDocument.h"
28 #include "HTMLNames.h"
29 #include "HTMLObjectElement.h"
30
31 namespace WebCore {
32
33 using namespace HTMLNames;
34
35 HTMLNameCollection::HTMLNameCollection(Document* document, CollectionType type, const AtomicString& name)
36     : HTMLCollection(document, type, DoNotSupportItemBefore)
37     , m_name(name)
38 {
39 }
40
41 HTMLNameCollection::~HTMLNameCollection()
42 {
43     ASSERT(base());
44     ASSERT(base()->isDocumentNode());
45     ASSERT(type() == WindowNamedItems || type() == DocumentNamedItems);
46     if (type() == WindowNamedItems)
47         static_cast<Document*>(base())->removeWindowNamedItemCache(this, m_name);
48     else
49         static_cast<Document*>(base())->removeDocumentNamedItemCache(this, m_name);
50 }
51
52 Element* HTMLNameCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
53 {
54     ASSERT_UNUSED(offsetInArray, !offsetInArray);
55     ASSERT(previous != base());
56
57     Node* current;
58     if (!previous)
59         current = base()->firstChild();
60     else
61         current = previous->traverseNextNode(base());
62
63     for (; current; current = current->traverseNextNode(base())) {
64         if (!current->isElementNode())
65             continue;
66         Element* e = static_cast<Element*>(current);
67         switch (type()) {
68             case WindowNamedItems:
69                 // find only images, forms, applets, embeds and objects by name, 
70                 // but anything by id
71                 if (e->hasTagName(imgTag) ||
72                     e->hasTagName(formTag) ||
73                     e->hasTagName(appletTag) ||
74                     e->hasTagName(embedTag) ||
75                     e->hasTagName(objectTag))
76                     if (e->getNameAttribute() == m_name)
77                         return e;
78                 if (e->getIdAttribute() == m_name)
79                     return e;
80                 break;
81             case DocumentNamedItems:
82                 // find images, forms, applets, embeds, objects and iframes by name, 
83                 // applets and object by id, and images by id but only if they have
84                 // a name attribute (this very strange rule matches IE)
85                 if (e->hasTagName(formTag) || e->hasTagName(embedTag) || e->hasTagName(iframeTag)) {
86                     if (e->getNameAttribute() == m_name)
87                         return e;
88                 } else if (e->hasTagName(appletTag)) {
89                     if (e->getNameAttribute() == m_name || e->getIdAttribute() == m_name)
90                         return e;
91                 } else if (e->hasTagName(objectTag)) {
92                     if ((e->getNameAttribute() == m_name || e->getIdAttribute() == m_name)
93                             && static_cast<HTMLObjectElement*>(e)->isDocNamedItem())
94                         return e;
95                 } else if (e->hasTagName(imgTag)) {
96                     if (e->getNameAttribute() == m_name || (e->getIdAttribute() == m_name && e->hasName()))
97                         return e;
98                 }
99                 break;
100         default:
101             ASSERT_NOT_REACHED();
102         }
103     }
104
105     return 0;
106 }
107
108 }