1/*
2 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 * * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include "config.h"
32#include "TreeScopeOrderedMap.h"
33
34#include "ContainerNodeAlgorithms.h"
35#include "ElementIterator.h"
36#include "HTMLImageElement.h"
37#include "HTMLLabelElement.h"
38#include "HTMLMapElement.h"
39#include "HTMLNameCollection.h"
40
41namespace WebCore {
42
43using namespace HTMLNames;
44
45void TreeScopeOrderedMap::clear()
46{
47 m_map.clear();
48}
49
50void TreeScopeOrderedMap::add(const AtomicStringImpl& key, Element& element, const TreeScope& treeScope)
51{
52 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&element.treeScope() == &treeScope);
53 ASSERT_WITH_SECURITY_IMPLICATION(treeScope.rootNode().containsIncludingShadowDOM(&element));
54
55 if (!element.isInTreeScope())
56 return;
57 Map::AddResult addResult = m_map.ensure(&key, [&element] {
58 return MapEntry(&element);
59 });
60 MapEntry& entry = addResult.iterator->value;
61
62#if !ASSERT_DISABLED || ENABLE(SECURITY_ASSERTIONS)
63 ASSERT_WITH_SECURITY_IMPLICATION(!entry.registeredElements.contains(&element));
64 entry.registeredElements.add(&element);
65#endif
66
67 if (addResult.isNewEntry)
68 return;
69
70 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(entry.count);
71 entry.element = nullptr;
72 entry.count++;
73 entry.orderedList.clear();
74}
75
76void TreeScopeOrderedMap::remove(const AtomicStringImpl& key, Element& element)
77{
78 m_map.checkConsistency();
79 auto it = m_map.find(&key);
80
81 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(it != m_map.end());
82
83 MapEntry& entry = it->value;
84 ASSERT_WITH_SECURITY_IMPLICATION(entry.registeredElements.remove(&element));
85 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(entry.count);
86 if (entry.count == 1) {
87 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(!entry.element || entry.element == &element);
88 m_map.remove(it);
89 } else {
90 if (entry.element == &element)
91 entry.element = nullptr;
92 entry.count--;
93 entry.orderedList.clear(); // FIXME: Remove the element instead if there are only few items left.
94 }
95}
96
97template <typename KeyMatchingFunction>
98inline Element* TreeScopeOrderedMap::get(const AtomicStringImpl& key, const TreeScope& scope, const KeyMatchingFunction& keyMatches) const
99{
100 m_map.checkConsistency();
101
102 auto it = m_map.find(&key);
103 if (it == m_map.end())
104 return nullptr;
105
106 MapEntry& entry = it->value;
107 ASSERT(entry.count);
108 if (entry.element) {
109 auto& element = *entry.element;
110 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&element.treeScope() == &scope);
111 ASSERT_WITH_SECURITY_IMPLICATION(entry.registeredElements.contains(&element));
112 return &element;
113 }
114
115 // We know there's at least one node that matches; iterate to find the first one.
116 for (auto& element : descendantsOfType<Element>(scope.rootNode())) {
117 if (!keyMatches(key, element))
118 continue;
119 entry.element = &element;
120 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&element.treeScope() == &scope);
121 ASSERT_WITH_SECURITY_IMPLICATION(entry.registeredElements.contains(entry.element));
122 return &element;
123 }
124
125#if !ASSERT_DISABLED
126 // FormAssociatedElement may call getElementById to find its owner form in the middle of a tree removal.
127 if (auto* currentScope = ContainerChildRemovalScope::currentScope()) {
128 ASSERT(&scope.rootNode() == &currentScope->parentOfRemovedTree().rootNode());
129 Node& removedTree = currentScope->removedChild();
130 ASSERT(is<ContainerNode>(removedTree));
131 for (auto& element : descendantsOfType<Element>(downcast<ContainerNode>(removedTree))) {
132 if (!keyMatches(key, element))
133 continue;
134 bool removedFromAncestorHasNotBeenCalledYet = element.isConnected();
135 ASSERT(removedFromAncestorHasNotBeenCalledYet);
136 return nullptr;
137 }
138 }
139 ASSERT_NOT_REACHED();
140#endif
141
142 return nullptr;
143}
144
145Element* TreeScopeOrderedMap::getElementById(const AtomicStringImpl& key, const TreeScope& scope) const
146{
147 return get(key, scope, [] (const AtomicStringImpl& key, const Element& element) {
148 return element.getIdAttribute().impl() == &key;
149 });
150}
151
152Element* TreeScopeOrderedMap::getElementByName(const AtomicStringImpl& key, const TreeScope& scope) const
153{
154 return get(key, scope, [] (const AtomicStringImpl& key, const Element& element) {
155 return element.getNameAttribute().impl() == &key;
156 });
157}
158
159HTMLMapElement* TreeScopeOrderedMap::getElementByMapName(const AtomicStringImpl& key, const TreeScope& scope) const
160{
161 return downcast<HTMLMapElement>(get(key, scope, [] (const AtomicStringImpl& key, const Element& element) {
162 return is<HTMLMapElement>(element) && downcast<HTMLMapElement>(element).getName().impl() == &key;
163 }));
164}
165
166HTMLImageElement* TreeScopeOrderedMap::getElementByUsemap(const AtomicStringImpl& key, const TreeScope& scope) const
167{
168 return downcast<HTMLImageElement>(get(key, scope, [] (const AtomicStringImpl& key, const Element& element) {
169 // FIXME: HTML5 specification says we should match both image and object elements.
170 return is<HTMLImageElement>(element) && downcast<HTMLImageElement>(element).matchesUsemap(key);
171 }));
172}
173
174HTMLLabelElement* TreeScopeOrderedMap::getElementByLabelForAttribute(const AtomicStringImpl& key, const TreeScope& scope) const
175{
176 return downcast<HTMLLabelElement>(get(key, scope, [] (const AtomicStringImpl& key, const Element& element) {
177 return is<HTMLLabelElement>(element) && element.attributeWithoutSynchronization(forAttr).impl() == &key;
178 }));
179}
180
181Element* TreeScopeOrderedMap::getElementByWindowNamedItem(const AtomicStringImpl& key, const TreeScope& scope) const
182{
183 return get(key, scope, [] (const AtomicStringImpl& key, const Element& element) {
184 return WindowNameCollection::elementMatches(element, &key);
185 });
186}
187
188Element* TreeScopeOrderedMap::getElementByDocumentNamedItem(const AtomicStringImpl& key, const TreeScope& scope) const
189{
190 return get(key, scope, [] (const AtomicStringImpl& key, const Element& element) {
191 return DocumentNameCollection::elementMatches(element, &key);
192 });
193}
194
195const Vector<Element*>* TreeScopeOrderedMap::getAllElementsById(const AtomicStringImpl& key, const TreeScope& scope) const
196{
197 m_map.checkConsistency();
198
199 auto it = m_map.find(&key);
200 if (it == m_map.end())
201 return nullptr;
202
203 MapEntry& entry = it->value;
204 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(entry.count);
205
206 if (entry.orderedList.isEmpty()) {
207 entry.orderedList.reserveCapacity(entry.count);
208 auto elementDescandents = descendantsOfType<Element>(scope.rootNode());
209 auto it = entry.element ? elementDescandents.beginAt(*entry.element) : elementDescandents.begin();
210 auto end = elementDescandents.end();
211 for (; it != end; ++it) {
212 auto& element = *it;
213 if (element.getIdAttribute().impl() != &key)
214 continue;
215 entry.orderedList.append(&element);
216 }
217 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(entry.orderedList.size() == entry.count);
218 }
219
220 return &entry.orderedList;
221}
222
223} // namespace WebCore
224