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#ifndef NodeRareData_h 23#define NodeRareData_h 24 25#include "ChildNodeList.h" 26#include "ClassNodeList.h" 27#include "DOMSettableTokenList.h" 28#include "HTMLCollection.h" 29#include "HTMLNames.h" 30#include "LiveNodeList.h" 31#include "MutationObserver.h" 32#include "MutationObserverRegistration.h" 33#include "Page.h" 34#include "QualifiedName.h" 35#include "TagNodeList.h" 36#include <wtf/HashSet.h> 37#include <wtf/OwnPtr.h> 38#include <wtf/PassOwnPtr.h> 39#include <wtf/text/AtomicString.h> 40#include <wtf/text/StringHash.h> 41 42#if ENABLE(VIDEO_TRACK) 43#include "TextTrack.h" 44#endif 45 46namespace WebCore { 47 48class LabelsNodeList; 49class RadioNodeList; 50class TreeScope; 51 52template <class ListType> struct NodeListTypeIdentifier; 53template <> struct NodeListTypeIdentifier<ClassNodeList> { static int value() { return 0; } }; 54template <> struct NodeListTypeIdentifier<NameNodeList> { static int value() { return 1; } }; 55template <> struct NodeListTypeIdentifier<TagNodeList> { static int value() { return 2; } }; 56template <> struct NodeListTypeIdentifier<HTMLTagNodeList> { static int value() { return 3; } }; 57template <> struct NodeListTypeIdentifier<RadioNodeList> { static int value() { return 4; } }; 58template <> struct NodeListTypeIdentifier<LabelsNodeList> { static int value() { return 5; } }; 59 60class NodeListsNodeData { 61 WTF_MAKE_NONCOPYABLE(NodeListsNodeData); WTF_MAKE_FAST_ALLOCATED; 62public: 63 void clearChildNodeListCache() 64 { 65 if (m_childNodeList) 66 m_childNodeList->invalidateCache(); 67 } 68 69 PassRef<ChildNodeList> ensureChildNodeList(ContainerNode& node) 70 { 71 ASSERT(!m_emptyChildNodeList); 72 if (m_childNodeList) 73 return *m_childNodeList; 74 auto list = ChildNodeList::create(node); 75 m_childNodeList = &list.get(); 76 return list; 77 } 78 79 void removeChildNodeList(ChildNodeList* list) 80 { 81 ASSERT(m_childNodeList == list); 82 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode())) 83 return; 84 m_childNodeList = nullptr; 85 } 86 87 PassRef<EmptyNodeList> ensureEmptyChildNodeList(Node& node) 88 { 89 ASSERT(!m_childNodeList); 90 if (m_emptyChildNodeList) 91 return *m_emptyChildNodeList; 92 auto list = EmptyNodeList::create(node); 93 m_emptyChildNodeList = &list.get(); 94 return list; 95 } 96 97 void removeEmptyChildNodeList(EmptyNodeList* list) 98 { 99 ASSERT(m_emptyChildNodeList == list); 100 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode())) 101 return; 102 m_emptyChildNodeList = nullptr; 103 } 104 105 template <typename StringType> 106 struct NodeListCacheMapEntryHash { 107 static unsigned hash(const std::pair<unsigned char, StringType>& entry) 108 { 109 return DefaultHash<StringType>::Hash::hash(entry.second) + entry.first; 110 } 111 static bool equal(const std::pair<unsigned char, StringType>& a, const std::pair<unsigned char, StringType>& b) { return a.first == b.first && DefaultHash<StringType>::Hash::equal(a.second, b.second); } 112 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<StringType>::Hash::safeToCompareToEmptyOrDeleted; 113 }; 114 115 typedef HashMap<std::pair<unsigned char, AtomicString>, LiveNodeList*, NodeListCacheMapEntryHash<AtomicString>> NodeListAtomicNameCacheMap; 116 typedef HashMap<std::pair<unsigned char, String>, LiveNodeList*, NodeListCacheMapEntryHash<String>> NodeListNameCacheMap; 117 typedef HashMap<std::pair<unsigned char, AtomicString>, HTMLCollection*, NodeListCacheMapEntryHash<AtomicString>> CollectionCacheMap; 118 typedef HashMap<QualifiedName, TagNodeList*> TagNodeListCacheNS; 119 120 template<typename T, typename ContainerType> 121 ALWAYS_INLINE PassRef<T> addCacheWithAtomicName(ContainerType& container, const AtomicString& name) 122 { 123 NodeListAtomicNameCacheMap::AddResult result = m_atomicNameCaches.fastAdd(namedNodeListKey<T>(name), nullptr); 124 if (!result.isNewEntry) 125 return static_cast<T&>(*result.iterator->value); 126 127 auto list = T::create(container, name); 128 result.iterator->value = &list.get(); 129 return list; 130 } 131 132 template<typename T> 133 ALWAYS_INLINE PassRef<T> addCacheWithName(ContainerNode& node, const String& name) 134 { 135 NodeListNameCacheMap::AddResult result = m_nameCaches.fastAdd(namedNodeListKey<T>(name), nullptr); 136 if (!result.isNewEntry) 137 return static_cast<T&>(*result.iterator->value); 138 139 auto list = T::create(node, name); 140 result.iterator->value = &list.get(); 141 return list; 142 } 143 144 ALWAYS_INLINE PassRef<TagNodeList> addCacheWithQualifiedName(ContainerNode& node, const AtomicString& namespaceURI, const AtomicString& localName) 145 { 146 QualifiedName name(nullAtom, localName, namespaceURI); 147 TagNodeListCacheNS::AddResult result = m_tagNodeListCacheNS.fastAdd(name, nullptr); 148 if (!result.isNewEntry) 149 return *result.iterator->value; 150 151 auto list = TagNodeList::create(node, namespaceURI, localName); 152 result.iterator->value = &list.get(); 153 return list; 154 } 155 156 template<typename T, typename ContainerType> 157 ALWAYS_INLINE PassRef<T> addCachedCollection(ContainerType& container, CollectionType collectionType, const AtomicString& name) 158 { 159 CollectionCacheMap::AddResult result = m_cachedCollections.fastAdd(namedCollectionKey(collectionType, name), nullptr); 160 if (!result.isNewEntry) 161 return static_cast<T&>(*result.iterator->value); 162 163 auto list = T::create(container, collectionType, name); 164 result.iterator->value = &list.get(); 165 return list; 166 } 167 168 template<typename T, typename ContainerType> 169 ALWAYS_INLINE PassRef<T> addCachedCollection(ContainerType& container, CollectionType collectionType) 170 { 171 CollectionCacheMap::AddResult result = m_cachedCollections.fastAdd(namedCollectionKey(collectionType, starAtom), nullptr); 172 if (!result.isNewEntry) 173 return static_cast<T&>(*result.iterator->value); 174 175 auto list = T::create(container, collectionType); 176 result.iterator->value = &list.get(); 177 return list; 178 } 179 180 template<typename T> 181 T* cachedCollection(CollectionType collectionType) 182 { 183 return static_cast<T*>(m_cachedCollections.get(namedCollectionKey(collectionType, starAtom))); 184 } 185 186 template <class NodeListType> 187 void removeCacheWithAtomicName(NodeListType* list, const AtomicString& name = starAtom) 188 { 189 ASSERT(list == m_atomicNameCaches.get(namedNodeListKey<NodeListType>(name))); 190 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode())) 191 return; 192 m_atomicNameCaches.remove(namedNodeListKey<NodeListType>(name)); 193 } 194 195 template <class NodeListType> 196 void removeCacheWithName(NodeListType* list, const String& name) 197 { 198 ASSERT(list == m_nameCaches.get(namedNodeListKey<NodeListType>(name))); 199 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode())) 200 return; 201 m_nameCaches.remove(namedNodeListKey<NodeListType>(name)); 202 } 203 204 void removeCacheWithQualifiedName(LiveNodeList* list, const AtomicString& namespaceURI, const AtomicString& localName) 205 { 206 QualifiedName name(nullAtom, localName, namespaceURI); 207 ASSERT(list == m_tagNodeListCacheNS.get(name)); 208 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode())) 209 return; 210 m_tagNodeListCacheNS.remove(name); 211 } 212 213 void removeCachedCollection(HTMLCollection* collection, const AtomicString& name = starAtom) 214 { 215 ASSERT(collection == m_cachedCollections.get(namedCollectionKey(collection->type(), name))); 216 if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(collection->ownerNode())) 217 return; 218 m_cachedCollections.remove(namedCollectionKey(collection->type(), name)); 219 } 220 221 static PassOwnPtr<NodeListsNodeData> create() 222 { 223 return adoptPtr(new NodeListsNodeData); 224 } 225 226 void invalidateCaches(const QualifiedName* attrName = 0); 227 bool isEmpty() const 228 { 229 return m_atomicNameCaches.isEmpty() && m_nameCaches.isEmpty() && m_cachedCollections.isEmpty() && m_tagNodeListCacheNS.isEmpty(); 230 } 231 232 void adoptTreeScope() 233 { 234 invalidateCaches(); 235 } 236 237 void adoptDocument(Document* oldDocument, Document* newDocument) 238 { 239 ASSERT(oldDocument); 240 if (oldDocument == newDocument) { 241 invalidateCaches(); 242 return; 243 } 244 245 for (auto& cache : m_atomicNameCaches.values()) 246 cache->invalidateCache(*oldDocument); 247 248 for (auto& cache : m_nameCaches.values()) 249 cache->invalidateCache(*oldDocument); 250 251 for (auto& list : m_tagNodeListCacheNS.values()) { 252 ASSERT(!list->isRootedAtDocument()); 253 list->invalidateCache(*oldDocument); 254 } 255 256 for (auto& collection : m_cachedCollections.values()) 257 collection->invalidateCache(*oldDocument); 258 } 259 260private: 261 NodeListsNodeData() 262 : m_childNodeList(nullptr) 263 , m_emptyChildNodeList(nullptr) 264 { 265 } 266 267 std::pair<unsigned char, AtomicString> namedCollectionKey(CollectionType type, const AtomicString& name) 268 { 269 return std::pair<unsigned char, AtomicString>(type, name); 270 } 271 272 template <class NodeListType> 273 std::pair<unsigned char, String> namedNodeListKey(const String& name) 274 { 275 return std::pair<unsigned char, String>(NodeListTypeIdentifier<NodeListType>::value(), name); 276 } 277 278 bool deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(Node&); 279 280 // These two are currently mutually exclusive and could be unioned. Not very important as this class is large anyway. 281 ChildNodeList* m_childNodeList; 282 EmptyNodeList* m_emptyChildNodeList; 283 284 NodeListAtomicNameCacheMap m_atomicNameCaches; 285 NodeListNameCacheMap m_nameCaches; 286 TagNodeListCacheNS m_tagNodeListCacheNS; 287 CollectionCacheMap m_cachedCollections; 288}; 289 290class NodeMutationObserverData { 291 WTF_MAKE_NONCOPYABLE(NodeMutationObserverData); WTF_MAKE_FAST_ALLOCATED; 292public: 293 Vector<OwnPtr<MutationObserverRegistration>> registry; 294 HashSet<MutationObserverRegistration*> transientRegistry; 295 296 static PassOwnPtr<NodeMutationObserverData> create() { return adoptPtr(new NodeMutationObserverData); } 297 298private: 299 NodeMutationObserverData() { } 300}; 301 302class NodeRareData : public NodeRareDataBase { 303 WTF_MAKE_NONCOPYABLE(NodeRareData); WTF_MAKE_FAST_ALLOCATED; 304public: 305 static PassOwnPtr<NodeRareData> create(RenderObject* renderer) { return adoptPtr(new NodeRareData(renderer)); } 306 307 void clearNodeLists() { m_nodeLists.clear(); } 308 NodeListsNodeData* nodeLists() const { return m_nodeLists.get(); } 309 NodeListsNodeData& ensureNodeLists() 310 { 311 if (!m_nodeLists) 312 m_nodeLists = NodeListsNodeData::create(); 313 return *m_nodeLists; 314 } 315 316 NodeMutationObserverData* mutationObserverData() { return m_mutationObserverData.get(); } 317 NodeMutationObserverData& ensureMutationObserverData() 318 { 319 if (!m_mutationObserverData) 320 m_mutationObserverData = NodeMutationObserverData::create(); 321 return *m_mutationObserverData; 322 } 323 324 unsigned connectedSubframeCount() const { return m_connectedFrameCount; } 325 void incrementConnectedSubframeCount(unsigned amount) 326 { 327 m_connectedFrameCount += amount; 328 } 329 void decrementConnectedSubframeCount(unsigned amount) 330 { 331 ASSERT(m_connectedFrameCount); 332 ASSERT(amount <= m_connectedFrameCount); 333 m_connectedFrameCount -= amount; 334 } 335 336protected: 337 NodeRareData(RenderObject* renderer) 338 : NodeRareDataBase(renderer) 339 , m_connectedFrameCount(0) 340 { } 341 342private: 343 unsigned m_connectedFrameCount : 10; // Must fit Page::maxNumberOfFrames. 344 345 OwnPtr<NodeListsNodeData> m_nodeLists; 346 OwnPtr<NodeMutationObserverData> m_mutationObserverData; 347}; 348 349inline bool NodeListsNodeData::deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(Node& ownerNode) 350{ 351 ASSERT(ownerNode.nodeLists() == this); 352 if ((m_childNodeList ? 1 : 0) + (m_emptyChildNodeList ? 1 : 0) + m_atomicNameCaches.size() + m_nameCaches.size() 353 + m_tagNodeListCacheNS.size() + m_cachedCollections.size() != 1) 354 return false; 355 ownerNode.clearNodeLists(); 356 return true; 357} 358 359inline NodeRareData* Node::rareData() const 360{ 361 ASSERT_WITH_SECURITY_IMPLICATION(hasRareData()); 362 return static_cast<NodeRareData*>(m_data.m_rareData); 363} 364 365inline NodeRareData& Node::ensureRareData() 366{ 367 if (!hasRareData()) 368 materializeRareData(); 369 return *rareData(); 370} 371 372// Ensure the 10 bits reserved for the m_connectedFrameCount cannot overflow 373COMPILE_ASSERT(Page::maxNumberOfFrames < 1024, Frame_limit_should_fit_in_rare_data_count); 374 375} // namespace WebCore 376 377#endif // NodeRareData_h 378