1/*
2 * Copyright (C) 2008, 2010 Apple Inc. All rights reserved.
3 * Copyright (C) 2008 David Smith <catfish.man@gmail.com>
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#pragma once
23
24#include "ChildNodeList.h"
25#include "HTMLCollection.h"
26#include "HTMLNames.h"
27#include "LiveNodeList.h"
28#include "MutationObserverRegistration.h"
29#include "QualifiedName.h"
30#include "TagCollection.h"
31#include <wtf/HashSet.h>
32#include <wtf/text/AtomicString.h>
33
34namespace WebCore {
35
36class LabelsNodeList;
37class NameNodeList;
38class RadioNodeList;
39class TreeScope;
40
41template <class ListType> struct NodeListTypeIdentifier;
42template <> struct NodeListTypeIdentifier<NameNodeList> { static int value() { return 0; } };
43template <> struct NodeListTypeIdentifier<RadioNodeList> { static int value() { return 1; } };
44template <> struct NodeListTypeIdentifier<LabelsNodeList> { static int value() { return 2; } };
45
46class NodeListsNodeData {
47 WTF_MAKE_NONCOPYABLE(NodeListsNodeData); WTF_MAKE_FAST_ALLOCATED;
48public:
49 NodeListsNodeData()
50 : m_childNodeList(nullptr)
51 , m_emptyChildNodeList(nullptr)
52 {
53 }
54
55 void clearChildNodeListCache()
56 {
57 if (m_childNodeList)
58 m_childNodeList->invalidateCache();
59 }
60
61 Ref<ChildNodeList> ensureChildNodeList(ContainerNode& node)
62 {
63 ASSERT(!m_emptyChildNodeList);
64 if (m_childNodeList)
65 return *m_childNodeList;
66 auto list = ChildNodeList::create(node);
67 m_childNodeList = list.ptr();
68 return list;
69 }
70
71 void removeChildNodeList(ChildNodeList* list)
72 {
73 ASSERT(m_childNodeList == list);
74 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode()))
75 return;
76 m_childNodeList = nullptr;
77 }
78
79 Ref<EmptyNodeList> ensureEmptyChildNodeList(Node& node)
80 {
81 ASSERT(!m_childNodeList);
82 if (m_emptyChildNodeList)
83 return *m_emptyChildNodeList;
84 auto list = EmptyNodeList::create(node);
85 m_emptyChildNodeList = list.ptr();
86 return list;
87 }
88
89 void removeEmptyChildNodeList(EmptyNodeList* list)
90 {
91 ASSERT(m_emptyChildNodeList == list);
92 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode()))
93 return;
94 m_emptyChildNodeList = nullptr;
95 }
96
97 struct NodeListCacheMapEntryHash {
98 static unsigned hash(const std::pair<unsigned char, AtomicString>& entry)
99 {
100 return DefaultHash<AtomicString>::Hash::hash(entry.second) + entry.first;
101 }
102 static bool equal(const std::pair<unsigned char, AtomicString>& a, const std::pair<unsigned char, AtomicString>& b) { return a.first == b.first && DefaultHash<AtomicString>::Hash::equal(a.second, b.second); }
103 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<AtomicString>::Hash::safeToCompareToEmptyOrDeleted;
104 };
105
106 typedef HashMap<std::pair<unsigned char, AtomicString>, LiveNodeList*, NodeListCacheMapEntryHash> NodeListAtomicNameCacheMap;
107 typedef HashMap<std::pair<unsigned char, AtomicString>, HTMLCollection*, NodeListCacheMapEntryHash> CollectionCacheMap;
108 typedef HashMap<QualifiedName, TagCollectionNS*> TagCollectionNSCache;
109
110 template<typename T, typename ContainerType>
111 ALWAYS_INLINE Ref<T> addCacheWithAtomicName(ContainerType& container, const AtomicString& name)
112 {
113 NodeListAtomicNameCacheMap::AddResult result = m_atomicNameCaches.fastAdd(namedNodeListKey<T>(name), nullptr);
114 if (!result.isNewEntry)
115 return static_cast<T&>(*result.iterator->value);
116
117 auto list = T::create(container, name);
118 result.iterator->value = &list.get();
119 return list;
120 }
121
122 ALWAYS_INLINE Ref<TagCollectionNS> addCachedTagCollectionNS(ContainerNode& node, const AtomicString& namespaceURI, const AtomicString& localName)
123 {
124 QualifiedName name(nullAtom(), localName, namespaceURI);
125 TagCollectionNSCache::AddResult result = m_tagCollectionNSCache.fastAdd(name, nullptr);
126 if (!result.isNewEntry)
127 return *result.iterator->value;
128
129 auto list = TagCollectionNS::create(node, namespaceURI, localName);
130 result.iterator->value = list.ptr();
131 return list;
132 }
133
134 template<typename T, typename ContainerType>
135 ALWAYS_INLINE Ref<T> addCachedCollection(ContainerType& container, CollectionType collectionType, const AtomicString& name)
136 {
137 CollectionCacheMap::AddResult result = m_cachedCollections.fastAdd(namedCollectionKey(collectionType, name), nullptr);
138 if (!result.isNewEntry)
139 return static_cast<T&>(*result.iterator->value);
140
141 auto list = T::create(container, collectionType, name);
142 result.iterator->value = &list.get();
143 return list;
144 }
145
146 template<typename T, typename ContainerType>
147 ALWAYS_INLINE Ref<T> addCachedCollection(ContainerType& container, CollectionType collectionType)
148 {
149 CollectionCacheMap::AddResult result = m_cachedCollections.fastAdd(namedCollectionKey(collectionType, starAtom()), nullptr);
150 if (!result.isNewEntry)
151 return static_cast<T&>(*result.iterator->value);
152
153 auto list = T::create(container, collectionType);
154 result.iterator->value = &list.get();
155 return list;
156 }
157
158 template<typename T>
159 T* cachedCollection(CollectionType collectionType)
160 {
161 return static_cast<T*>(m_cachedCollections.get(namedCollectionKey(collectionType, starAtom())));
162 }
163
164 template <class NodeListType>
165 void removeCacheWithAtomicName(NodeListType* list, const AtomicString& name = starAtom())
166 {
167 ASSERT(list == m_atomicNameCaches.get(namedNodeListKey<NodeListType>(name)));
168 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode()))
169 return;
170 m_atomicNameCaches.remove(namedNodeListKey<NodeListType>(name));
171 }
172
173 void removeCachedTagCollectionNS(HTMLCollection& collection, const AtomicString& namespaceURI, const AtomicString& localName)
174 {
175 QualifiedName name(nullAtom(), localName, namespaceURI);
176 ASSERT(&collection == m_tagCollectionNSCache.get(name));
177 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(collection.ownerNode()))
178 return;
179 m_tagCollectionNSCache.remove(name);
180 }
181
182 void removeCachedCollection(HTMLCollection* collection, const AtomicString& name = starAtom())
183 {
184 ASSERT(collection == m_cachedCollections.get(namedCollectionKey(collection->type(), name)));
185 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(collection->ownerNode()))
186 return;
187 m_cachedCollections.remove(namedCollectionKey(collection->type(), name));
188 }
189
190 void invalidateCaches();
191 void invalidateCachesForAttribute(const QualifiedName& attrName);
192
193 void adoptTreeScope()
194 {
195 invalidateCaches();
196 }
197
198 void adoptDocument(Document& oldDocument, Document& newDocument)
199 {
200 if (&oldDocument == &newDocument) {
201 invalidateCaches();
202 return;
203 }
204
205 for (auto& cache : m_atomicNameCaches.values())
206 cache->invalidateCacheForDocument(oldDocument);
207
208 for (auto& list : m_tagCollectionNSCache.values()) {
209 ASSERT(!list->isRootedAtDocument());
210 list->invalidateCacheForDocument(oldDocument);
211 }
212
213 for (auto& collection : m_cachedCollections.values())
214 collection->invalidateCacheForDocument(oldDocument);
215 }
216
217private:
218 std::pair<unsigned char, AtomicString> namedCollectionKey(CollectionType type, const AtomicString& name)
219 {
220 return std::pair<unsigned char, AtomicString>(type, name);
221 }
222
223 template <class NodeListType>
224 std::pair<unsigned char, AtomicString> namedNodeListKey(const AtomicString& name)
225 {
226 return std::pair<unsigned char, AtomicString>(NodeListTypeIdentifier<NodeListType>::value(), name);
227 }
228
229 bool deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(Node&);
230
231 // These two are currently mutually exclusive and could be unioned. Not very important as this class is large anyway.
232 ChildNodeList* m_childNodeList;
233 EmptyNodeList* m_emptyChildNodeList;
234
235 NodeListAtomicNameCacheMap m_atomicNameCaches;
236 TagCollectionNSCache m_tagCollectionNSCache;
237 CollectionCacheMap m_cachedCollections;
238};
239
240class NodeMutationObserverData {
241 WTF_MAKE_NONCOPYABLE(NodeMutationObserverData); WTF_MAKE_FAST_ALLOCATED;
242public:
243 Vector<std::unique_ptr<MutationObserverRegistration>> registry;
244 HashSet<MutationObserverRegistration*> transientRegistry;
245
246 NodeMutationObserverData() { }
247};
248
249class NodeRareData : public NodeRareDataBase {
250 WTF_MAKE_NONCOPYABLE(NodeRareData); WTF_MAKE_FAST_ALLOCATED;
251public:
252#if defined(DUMP_NODE_STATISTICS) && DUMP_NODE_STATISTICS
253 enum class UseType : uint16_t {
254 ConnectedFrameCount = 1 << 0,
255 NodeList = 1 << 1,
256 MutationObserver = 1 << 2,
257
258 TabIndex = 1 << 3,
259 StyleFlags = 1 << 4,
260 MinimumSize = 1 << 5,
261 ScrollingPosition = 1 << 6,
262 ComputedStyle = 1 << 7,
263 Dataset = 1 << 8,
264 ClassList = 1 << 9,
265 ShadowRoot = 1 << 10,
266 CustomElementQueue = 1 << 11,
267 AttributeMap = 1 << 12,
268 InteractionObserver = 1 << 13,
269 PseudoElements = 1 << 14,
270 };
271#endif
272
273 NodeRareData(RenderObject* renderer)
274 : NodeRareDataBase(renderer)
275 , m_connectedFrameCount(0)
276 { }
277
278 void clearNodeLists() { m_nodeLists = nullptr; }
279 NodeListsNodeData* nodeLists() const { return m_nodeLists.get(); }
280 NodeListsNodeData& ensureNodeLists()
281 {
282 if (!m_nodeLists)
283 m_nodeLists = std::make_unique<NodeListsNodeData>();
284 return *m_nodeLists;
285 }
286
287 NodeMutationObserverData* mutationObserverData() { return m_mutationObserverData.get(); }
288 NodeMutationObserverData& ensureMutationObserverData()
289 {
290 if (!m_mutationObserverData)
291 m_mutationObserverData = std::make_unique<NodeMutationObserverData>();
292 return *m_mutationObserverData;
293 }
294
295 unsigned connectedSubframeCount() const { return m_connectedFrameCount; }
296 void incrementConnectedSubframeCount(unsigned amount)
297 {
298 m_connectedFrameCount += amount;
299 }
300 void decrementConnectedSubframeCount(unsigned amount)
301 {
302 ASSERT(m_connectedFrameCount);
303 ASSERT(amount <= m_connectedFrameCount);
304 m_connectedFrameCount -= amount;
305 }
306
307#if DUMP_NODE_STATISTICS
308 OptionSet<UseType> useTypes() const
309 {
310 OptionSet<UseType> result;
311 if (m_connectedFrameCount)
312 result.add(UseType::ConnectedFrameCount);
313 if (m_nodeLists)
314 result.add(UseType::NodeList);
315 if (m_mutationObserverData)
316 result.add(UseType::MutationObserver);
317 return result;
318 }
319#endif
320
321private:
322 unsigned m_connectedFrameCount : 10; // Must fit Page::maxNumberOfFrames.
323
324 std::unique_ptr<NodeListsNodeData> m_nodeLists;
325 std::unique_ptr<NodeMutationObserverData> m_mutationObserverData;
326};
327
328inline bool NodeListsNodeData::deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(Node& ownerNode)
329{
330 ASSERT(ownerNode.nodeLists() == this);
331 if ((m_childNodeList ? 1 : 0) + (m_emptyChildNodeList ? 1 : 0) + m_atomicNameCaches.size()
332 + m_tagCollectionNSCache.size() + m_cachedCollections.size() != 1)
333 return false;
334 ownerNode.clearNodeLists();
335 return true;
336}
337
338inline NodeRareData* Node::rareData() const
339{
340 ASSERT_WITH_SECURITY_IMPLICATION(hasRareData());
341 return static_cast<NodeRareData*>(m_data.m_rareData);
342}
343
344inline NodeRareData& Node::ensureRareData()
345{
346 if (!hasRareData())
347 materializeRareData();
348 return *rareData();
349}
350
351} // namespace WebCore
352