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