ComposedTreeIterator may crash when first child of shadow root is a comment node
[WebKit-https.git] / Source / WebCore / dom / ComposedTreeIterator.h
1 /*
2  * Copyright (C) 2015-2016 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
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "ElementAndTextDescendantIterator.h"
27 #include "ShadowRoot.h"
28
29 #ifndef ComposedTreeIterator_h
30 #define ComposedTreeIterator_h
31
32 namespace WebCore {
33
34 class HTMLSlotElement;
35
36 class ComposedTreeIterator {
37 public:
38     ComposedTreeIterator();
39     enum FirstChildTag { FirstChild };
40     ComposedTreeIterator(ContainerNode& root, FirstChildTag);
41     ComposedTreeIterator(ContainerNode& root, Node& current);
42
43     Node& operator*() { return current(); }
44     Node* operator->() { return &current(); }
45
46     bool operator==(const ComposedTreeIterator& other) const { return context().iterator == other.context().iterator; }
47     bool operator!=(const ComposedTreeIterator& other) const { return context().iterator != other.context().iterator; }
48
49     ComposedTreeIterator& operator++() { return traverseNext(); }
50
51     ComposedTreeIterator& traverseNext();
52     ComposedTreeIterator& traverseNextSkippingChildren();
53     ComposedTreeIterator& traverseNextSibling();
54     ComposedTreeIterator& traversePreviousSibling();
55
56     unsigned depth() const;
57
58     void dropAssertions();
59
60 private:
61     void initializeContextStack(ContainerNode& root, Node& current);
62     void traverseNextInShadowTree();
63     void traverseNextLeavingContext();
64     void traverseShadowRoot(ShadowRoot&);
65 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
66     bool advanceInSlot(int direction);
67     void traverseSiblingInSlot(int direction);
68 #endif
69
70     struct Context {
71         Context();
72         Context(ContainerNode& root, FirstChildTag);
73         Context(ContainerNode& root, Node& node);
74
75 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
76         enum SlottedTag { Slotted };
77         Context(ContainerNode& root, Node& node, SlottedTag);
78 #endif
79         ElementAndTextDescendantIterator iterator;
80         ElementAndTextDescendantIterator end;
81         size_t slotNodeIndex { notFound };
82     };
83     Context& context() { return m_contextStack.last(); }
84     const Context& context() const { return m_contextStack.last(); }
85     Node& current() { return *context().iterator; }
86
87     bool m_didDropAssertions { false };
88     Vector<Context, 8> m_contextStack;
89 };
90
91 inline ComposedTreeIterator::ComposedTreeIterator()
92 {
93     m_contextStack.uncheckedAppend({ });
94 }
95
96 inline ComposedTreeIterator& ComposedTreeIterator::traverseNext()
97 {
98     if (auto* shadowRoot = context().iterator->shadowRoot()) {
99         traverseShadowRoot(*shadowRoot);
100         return *this;
101     }
102
103     if (m_contextStack.size() > 1) {
104         traverseNextInShadowTree();
105         return *this;
106     }
107
108     context().iterator.traverseNext();
109     return *this;
110 }
111
112 inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSkippingChildren()
113 {
114     context().iterator.traverseNextSkippingChildren();
115
116     if (context().iterator == context().end && m_contextStack.size() > 1)
117         traverseNextLeavingContext();
118     
119     return *this;
120 }
121
122 inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSibling()
123 {
124 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
125     if (current().parentNode()->shadowRoot()) {
126         traverseSiblingInSlot(1);
127         return *this;
128     }
129 #endif
130     context().iterator.traverseNextSibling();
131     return *this;
132 }
133
134 inline ComposedTreeIterator& ComposedTreeIterator::traversePreviousSibling()
135 {
136 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
137     if (current().parentNode()->shadowRoot()) {
138         traverseSiblingInSlot(-1);
139         return *this;
140     }
141 #endif
142     context().iterator.traversePreviousSibling();
143     return *this;
144 }
145
146 inline unsigned ComposedTreeIterator::depth() const
147 {
148     unsigned depth = 0;
149     for (auto& context : m_contextStack)
150         depth += context.iterator.depth();
151     return depth;
152 }
153
154 class ComposedTreeDescendantAdapter {
155 public:
156     ComposedTreeDescendantAdapter(ContainerNode& parent)
157         : m_parent(parent)
158     { }
159
160     ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent, ComposedTreeIterator::FirstChild); }
161     ComposedTreeIterator end() { return { }; }
162     ComposedTreeIterator at(const Node& child) { return ComposedTreeIterator(m_parent, const_cast<Node&>(child)); }
163     
164 private:
165     ContainerNode& m_parent;
166 };
167
168 class ComposedTreeChildAdapter {
169 public:
170     class Iterator : public ComposedTreeIterator {
171     public:
172         Iterator() = default;
173         explicit Iterator(ContainerNode& root)
174             : ComposedTreeIterator(root, ComposedTreeIterator::FirstChild)
175         { }
176         Iterator(ContainerNode& root, Node& current)
177             : ComposedTreeIterator(root, current)
178         { }
179
180         Iterator& operator++() { return static_cast<Iterator&>(traverseNextSibling()); }
181         Iterator& operator--() { return static_cast<Iterator&>(traversePreviousSibling()); }
182     };
183
184     ComposedTreeChildAdapter(ContainerNode& parent)
185         : m_parent(parent)
186     { }
187
188     Iterator begin() { return Iterator(m_parent); }
189     Iterator end() { return { }; }
190     Iterator at(const Node& child) { return Iterator(m_parent, const_cast<Node&>(child)); }
191
192 private:
193     ContainerNode& m_parent;
194 };
195
196 // FIXME: We should have const versions too.
197 inline ComposedTreeDescendantAdapter composedTreeDescendants(ContainerNode& parent)
198 {
199     return ComposedTreeDescendantAdapter(parent);
200 }
201
202 inline ComposedTreeChildAdapter composedTreeChildren(ContainerNode& parent)
203 {
204     return ComposedTreeChildAdapter(parent);
205 }
206
207 enum class ComposedTreeAsTextMode { Normal, WithPointers };
208 WEBCORE_EXPORT String composedTreeAsText(ContainerNode& root, ComposedTreeAsTextMode = ComposedTreeAsTextMode::Normal);
209
210 }
211
212 #endif