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
35namespace WebCore {
36
37void RenderTreePosition::computeNextSibling(const Node& node)
38{
39 ASSERT(!node.renderer());
40 if (m_hasValidNextSibling) {
41#if !ASSERT_DISABLED
42 const unsigned oNSquaredAvoidanceLimit = 20;
43 bool skipAssert = m_parent.isRenderView() || ++m_assertionLimitCounter > oNSquaredAvoidanceLimit;
44 ASSERT(skipAssert || nextSiblingRenderer(node) == m_nextSibling);
45#endif
46 return;
47 }
48 m_nextSibling = makeWeakPtr(nextSiblingRenderer(node));
49 m_hasValidNextSibling = true;
50}
51
52void RenderTreePosition::invalidateNextSibling(const RenderObject& siblingRenderer)
53{
54 if (!m_hasValidNextSibling)
55 return;
56 if (m_nextSibling == &siblingRenderer)
57 m_hasValidNextSibling = false;
58}
59
60RenderObject* RenderTreePosition::nextSiblingRenderer(const Node& node) const
61{
62 ASSERT(!node.renderer());
63
64 auto* parentElement = m_parent.element();
65 if (!parentElement)
66 return nullptr;
67 // FIXME: PlugingReplacement shadow trees are very wrong.
68 if (parentElement == &node)
69 return nullptr;
70
71 Vector<Element*, 30> elementStack;
72
73 // In the common case ancestor == parentElement immediately and this just pushes parentElement into stack.
74 auto* ancestor = node.parentElementInComposedTree();
75 while (true) {
76 elementStack.append(ancestor);
77 if (ancestor == parentElement)
78 break;
79 ancestor = ancestor->parentElementInComposedTree();
80 ASSERT(ancestor);
81 }
82 elementStack.reverse();
83
84 auto composedDescendants = composedTreeDescendants(*parentElement);
85
86 auto initializeIteratorConsideringPseudoElements = [&] {
87 if (is<PseudoElement>(node)) {
88 auto* host = downcast<PseudoElement>(node).hostElement();
89 if (node.isBeforePseudoElement()) {
90 if (host != parentElement)
91 return composedDescendants.at(*host).traverseNext();
92 return composedDescendants.begin();
93 }
94 ASSERT(node.isAfterPseudoElement());
95 elementStack.removeLast();
96 if (host != parentElement)
97 return composedDescendants.at(*host).traverseNextSkippingChildren();
98 return composedDescendants.end();
99 }
100 return composedDescendants.at(node).traverseNextSkippingChildren();
101 };
102
103 auto pushCheckingForAfterPseudoElementRenderer = [&] (Element& element) -> RenderElement* {
104 ASSERT(!element.isPseudoElement());
105 if (auto* before = element.beforePseudoElement()) {
106 if (auto* renderer = before->renderer())
107 return renderer;
108 }
109 elementStack.append(&element);
110 return nullptr;
111 };
112
113 auto popCheckingForAfterPseudoElementRenderers = [&] (unsigned iteratorDepthToMatch) -> RenderElement* {
114 while (elementStack.size() > iteratorDepthToMatch) {
115 auto& element = *elementStack.takeLast();
116 if (auto* after = element.afterPseudoElement()) {
117 if (auto* renderer = after->renderer())
118 return renderer;
119 }
120 }
121 return nullptr;
122 };
123
124 auto it = initializeIteratorConsideringPseudoElements();
125 auto end = composedDescendants.end();
126
127 while (it != end) {
128 if (auto* renderer = popCheckingForAfterPseudoElementRenderers(it.depth()))
129 return renderer;
130
131 if (auto* renderer = it->renderer())
132 return renderer;
133
134 if (is<Element>(*it)) {
135 auto& element = downcast<Element>(*it);
136 if (element.hasDisplayContents()) {
137 if (auto* renderer = pushCheckingForAfterPseudoElementRenderer(element))
138 return renderer;
139 it.traverseNext();
140 continue;
141 }
142 }
143
144 it.traverseNextSkippingChildren();
145 }
146
147 return popCheckingForAfterPseudoElementRenderers(0);
148}
149
150}
151