36ffb596c9da5e1c6132f5d7d444ac4bbe3272fe
[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     ComposedTreeIterator(ContainerNode& root);
40     ComposedTreeIterator(ContainerNode& root, Node& current);
41
42     Node& operator*() { return current(); }
43     Node* operator->() { return &current(); }
44
45     bool operator==(const ComposedTreeIterator& other) const { return context().iterator == other.context().iterator; }
46     bool operator!=(const ComposedTreeIterator& other) const { return context().iterator != other.context().iterator; }
47
48     ComposedTreeIterator& operator++() { return traverseNext(); }
49
50     ComposedTreeIterator& traverseNext();
51     ComposedTreeIterator& traverseNextSkippingChildren();
52     ComposedTreeIterator& traverseNextSibling();
53     ComposedTreeIterator& traversePreviousSibling();
54
55     unsigned depth() const;
56
57     void dropAssertions();
58
59 private:
60     void initializeContextStack(ContainerNode& root, Node& current);
61     void traverseNextInShadowTree();
62     void traverseNextLeavingContext();
63     void traverseShadowRoot(ShadowRoot&);
64 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
65     bool advanceInSlot(int direction);
66     void traverseSiblingInSlot(int direction);
67 #endif
68
69     struct Context {
70         Context();
71         explicit Context(ContainerNode& root);
72         Context(ContainerNode& root, Node& node);
73
74 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
75         enum SlottedTag { Slotted };
76         Context(ContainerNode& root, Node& node, SlottedTag);
77 #endif
78         ElementAndTextDescendantIterator iterator;
79         ElementAndTextDescendantIterator end;
80         size_t slotNodeIndex { notFound };
81     };
82     Context& context() { return m_contextStack.last(); }
83     const Context& context() const { return m_contextStack.last(); }
84     Node& current() { return *context().iterator; }
85
86     bool m_didDropAssertions { false };
87     Vector<Context, 8> m_contextStack;
88 };
89
90 inline ComposedTreeIterator::ComposedTreeIterator()
91 {
92     m_contextStack.uncheckedAppend({ });
93 }
94
95 inline ComposedTreeIterator& ComposedTreeIterator::traverseNext()
96 {
97     if (auto* shadowRoot = context().iterator->shadowRoot()) {
98         traverseShadowRoot(*shadowRoot);
99         return *this;
100     }
101
102     if (m_contextStack.size() > 1) {
103         traverseNextInShadowTree();
104         return *this;
105     }
106
107     context().iterator.traverseNext();
108     return *this;
109 }
110
111 inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSkippingChildren()
112 {
113     context().iterator.traverseNextSkippingChildren();
114
115     if (context().iterator == context().end && m_contextStack.size() > 1)
116         traverseNextLeavingContext();
117     
118     return *this;
119 }
120
121 inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSibling()
122 {
123 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
124     if (current().parentNode()->shadowRoot()) {
125         traverseSiblingInSlot(1);
126         return *this;
127     }
128 #endif
129     context().iterator.traverseNextSibling();
130     return *this;
131 }
132
133 inline ComposedTreeIterator& ComposedTreeIterator::traversePreviousSibling()
134 {
135 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
136     if (current().parentNode()->shadowRoot()) {
137         traverseSiblingInSlot(-1);
138         return *this;
139     }
140 #endif
141     context().iterator.traversePreviousSibling();
142     return *this;
143 }
144
145 inline unsigned ComposedTreeIterator::depth() const
146 {
147     unsigned depth = 0;
148     for (auto& context : m_contextStack)
149         depth += context.iterator.depth();
150     return depth;
151 }
152
153 class ComposedTreeDescendantAdapter {
154 public:
155     ComposedTreeDescendantAdapter(ContainerNode& parent)
156         : m_parent(parent)
157     { }
158
159     ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent); }
160     ComposedTreeIterator end() { return { }; }
161     ComposedTreeIterator at(const Node& child) { return ComposedTreeIterator(m_parent, const_cast<Node&>(child)); }
162     
163 private:
164     ContainerNode& m_parent;
165 };
166
167 class ComposedTreeChildAdapter {
168 public:
169     class Iterator : public ComposedTreeIterator {
170     public:
171         Iterator() = default;
172         explicit Iterator(ContainerNode& root)
173             : ComposedTreeIterator(root)
174         { }
175         Iterator(ContainerNode& root, Node& current)
176             : ComposedTreeIterator(root, current)
177         { }
178
179         Iterator& operator++() { return static_cast<Iterator&>(traverseNextSibling()); }
180         Iterator& operator--() { return static_cast<Iterator&>(traversePreviousSibling()); }
181     };
182
183     ComposedTreeChildAdapter(ContainerNode& parent)
184         : m_parent(parent)
185     { }
186
187     Iterator begin() { return Iterator(m_parent); }
188     Iterator end() { return { }; }
189     Iterator at(const Node& child) { return Iterator(m_parent, const_cast<Node&>(child)); }
190
191 private:
192     ContainerNode& m_parent;
193 };
194
195 // FIXME: We should have const versions too.
196 inline ComposedTreeDescendantAdapter composedTreeDescendants(ContainerNode& parent)
197 {
198     return ComposedTreeDescendantAdapter(parent);
199 }
200
201 inline ComposedTreeChildAdapter composedTreeChildren(ContainerNode& parent)
202 {
203     return ComposedTreeChildAdapter(parent);
204 }
205
206 enum class ComposedTreeAsTextMode { Normal, WithPointers };
207 WEBCORE_EXPORT String composedTreeAsText(ContainerNode& root, ComposedTreeAsTextMode = ComposedTreeAsTextMode::Normal);
208
209 }
210
211 #endif