067a76300563c2d27b56a549009353eac4d12f58
[WebKit-https.git] / Source / WebCore / style / RenderTreePosition.cpp
1 /*
2  * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "RenderTreePosition.h"
28
29 #include "ComposedTreeIterator.h"
30 #include "PseudoElement.h"
31 #include "RenderInline.h"
32 #include "RenderObject.h"
33 #include "ShadowRoot.h"
34
35 namespace WebCore {
36
37 void RenderTreePosition::insert(RenderPtr<RenderObject> renderer)
38 {
39     ASSERT(m_hasValidNextSibling);
40     auto* insertBefore = m_nextSibling;
41     if (is<RenderText>(insertBefore)) {
42         if (auto* wrapperInline = downcast<RenderText>(*insertBefore).inlineWrapperForDisplayContents())
43             insertBefore = wrapperInline;
44     }
45     m_parent.addChild(WTFMove(renderer), insertBefore);
46 }
47
48 void RenderTreePosition::computeNextSibling(const Node& node)
49 {
50     ASSERT(!node.renderer());
51     if (m_hasValidNextSibling) {
52 #if !ASSERT_DISABLED
53         const unsigned oNSquaredAvoidanceLimit = 20;
54         bool skipAssert = m_parent.isRenderView() || ++m_assertionLimitCounter > oNSquaredAvoidanceLimit;
55         ASSERT(skipAssert || nextSiblingRenderer(node) == m_nextSibling);
56 #endif
57         return;
58     }
59     m_nextSibling = nextSiblingRenderer(node);
60     m_hasValidNextSibling = true;
61 }
62
63 void RenderTreePosition::invalidateNextSibling(const RenderObject& siblingRenderer)
64 {
65     if (!m_hasValidNextSibling)
66         return;
67     if (m_nextSibling == &siblingRenderer)
68         m_hasValidNextSibling = false;
69 }
70
71 RenderObject* RenderTreePosition::nextSiblingRenderer(const Node& node) const
72 {
73     ASSERT(!node.renderer());
74
75     auto* parentElement = m_parent.element();
76     if (!parentElement)
77         return nullptr;
78     // FIXME: PlugingReplacement shadow trees are very wrong.
79     if (parentElement == &node)
80         return nullptr;
81
82     Vector<Element*, 30> elementStack;
83
84     // In the common case ancestor == parentElement immediately and this just pushes parentElement into stack.
85     auto* ancestor = is<PseudoElement>(node) ? downcast<PseudoElement>(node).hostElement() : node.parentElementInComposedTree();
86     while (true) {
87         elementStack.append(ancestor);
88         if (ancestor == parentElement)
89             break;
90         ancestor = ancestor->parentElementInComposedTree();
91         ASSERT(ancestor);
92     }
93     elementStack.reverse();
94
95     auto composedDescendants = composedTreeDescendants(*parentElement);
96
97     auto initializeIteratorConsideringPseudoElements = [&] {
98         if (is<PseudoElement>(node)) {
99             auto* host = downcast<PseudoElement>(node).hostElement();
100             if (node.isBeforePseudoElement()) {
101                 if (host != parentElement)
102                     return composedDescendants.at(*host).traverseNext();
103                 return composedDescendants.begin();
104             }
105             ASSERT(node.isAfterPseudoElement());
106             elementStack.removeLast();
107             if (host != parentElement)
108                 return composedDescendants.at(*host).traverseNextSkippingChildren();
109             return composedDescendants.end();
110         }
111         return composedDescendants.at(node).traverseNextSkippingChildren();
112     };
113
114     auto pushCheckingForAfterPseudoElementRenderer = [&] (Element& element) -> RenderElement* {
115         ASSERT(!element.isPseudoElement());
116         if (auto* before = element.beforePseudoElement()) {
117             if (auto* renderer = before->renderer())
118                 return renderer;
119         }
120         elementStack.append(&element);
121         return nullptr;
122     };
123
124     auto popCheckingForAfterPseudoElementRenderers = [&] (unsigned iteratorDepthToMatch) -> RenderElement* {
125         while (elementStack.size() > iteratorDepthToMatch) {
126             auto& element = *elementStack.takeLast();
127             if (auto* after = element.afterPseudoElement()) {
128                 if (auto* renderer = after->renderer())
129                     return renderer;
130             }
131         }
132         return nullptr;
133     };
134
135     auto it = initializeIteratorConsideringPseudoElements();
136     auto end = composedDescendants.end();
137
138     while (it != end) {
139         if (auto* renderer = popCheckingForAfterPseudoElementRenderers(it.depth()))
140             return renderer;
141
142         if (auto* renderer = it->renderer())
143             return renderer;
144
145         if (is<Element>(*it)) {
146             auto& element = downcast<Element>(*it);
147             if (element.hasDisplayContents()) {
148                 if (auto* renderer = pushCheckingForAfterPseudoElementRenderer(element))
149                     return renderer;
150                 it.traverseNext();
151                 continue;
152             }
153         }
154
155         it.traverseNextSkippingChildren();
156     }
157
158     return popCheckingForAfterPseudoElementRenderers(0);
159 }
160
161 }