1/*
2 * Copyright (C) 2018 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 "RenderTreeBuilderInline.h"
28
29#include "FullscreenManager.h"
30#include "RenderChildIterator.h"
31#include "RenderFullScreen.h"
32#include "RenderInline.h"
33#include "RenderTable.h"
34#include "RenderTreeBuilderMultiColumn.h"
35#include "RenderTreeBuilderTable.h"
36
37namespace WebCore {
38
39static bool canUseAsParentForContinuation(const RenderObject* renderer)
40{
41 if (!renderer)
42 return false;
43 if (!is<RenderBlock>(renderer) && renderer->isAnonymous())
44 return false;
45 if (is<RenderTable>(renderer))
46 return false;
47 return true;
48}
49
50static RenderBoxModelObject* nextContinuation(RenderObject* renderer)
51{
52 if (is<RenderInline>(*renderer) && !renderer->isReplaced())
53 return downcast<RenderInline>(*renderer).continuation();
54 return downcast<RenderBlock>(*renderer).inlineContinuation();
55}
56
57static RenderBoxModelObject* continuationBefore(RenderInline& parent, RenderObject* beforeChild)
58{
59 if (beforeChild && beforeChild->parent() == &parent)
60 return &parent;
61
62 RenderBoxModelObject* curr = nextContinuation(&parent);
63 RenderBoxModelObject* nextToLast = &parent;
64 RenderBoxModelObject* last = &parent;
65 while (curr) {
66 if (beforeChild && beforeChild->parent() == curr) {
67 if (curr->firstChild() == beforeChild)
68 return last;
69 return curr;
70 }
71
72 nextToLast = last;
73 last = curr;
74 curr = nextContinuation(curr);
75 }
76
77 if (!beforeChild && !last->firstChild())
78 return nextToLast;
79 return last;
80}
81
82static RenderPtr<RenderInline> cloneAsContinuation(RenderInline& renderer)
83{
84 RenderPtr<RenderInline> cloneInline = createRenderer<RenderInline>(*renderer.element(), RenderStyle::clone(renderer.style()));
85 cloneInline->initializeStyle();
86 cloneInline->setFragmentedFlowState(renderer.fragmentedFlowState());
87 cloneInline->setHasOutlineAutoAncestor(renderer.hasOutlineAutoAncestor());
88 cloneInline->setIsContinuation();
89 return cloneInline;
90}
91
92static RenderElement* inFlowPositionedInlineAncestor(RenderElement& renderer)
93{
94 auto* ancestor = &renderer;
95 while (ancestor && ancestor->isRenderInline()) {
96 if (ancestor->isInFlowPositioned())
97 return ancestor;
98 ancestor = ancestor->parent();
99 }
100 return nullptr;
101}
102
103RenderTreeBuilder::Inline::Inline(RenderTreeBuilder& builder)
104 : m_builder(builder)
105{
106}
107
108void RenderTreeBuilder::Inline::attach(RenderInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
109{
110 auto* beforeChildOrPlaceholder = beforeChild;
111 if (auto* fragmentedFlow = parent.enclosingFragmentedFlow())
112 beforeChildOrPlaceholder = m_builder.multiColumnBuilder().resolveMovedChild(*fragmentedFlow, beforeChild);
113 if (parent.continuation()) {
114 insertChildToContinuation(parent, WTFMove(child), beforeChildOrPlaceholder);
115 return;
116 }
117 attachIgnoringContinuation(parent, WTFMove(child), beforeChildOrPlaceholder);
118}
119
120void RenderTreeBuilder::Inline::insertChildToContinuation(RenderInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
121{
122 auto* flow = continuationBefore(parent, beforeChild);
123 // It may or may not be the direct parent of the beforeChild.
124 RenderBoxModelObject* beforeChildAncestor = nullptr;
125 if (!beforeChild) {
126 auto* continuation = nextContinuation(flow);
127 beforeChildAncestor = continuation ? continuation : flow;
128 } else if (canUseAsParentForContinuation(beforeChild->parent()))
129 beforeChildAncestor = downcast<RenderBoxModelObject>(beforeChild->parent());
130 else if (beforeChild->parent()) {
131 // In case of anonymous wrappers, the parent of the beforeChild is mostly irrelevant. What we need is the topmost wrapper.
132 auto* parent = beforeChild->parent();
133 while (parent && parent->parent() && parent->parent()->isAnonymous()) {
134 // The ancestor candidate needs to be inside the continuation.
135 if (parent->isContinuation())
136 break;
137 parent = parent->parent();
138 }
139 ASSERT(parent && parent->parent());
140 beforeChildAncestor = downcast<RenderBoxModelObject>(parent->parent());
141 } else
142 ASSERT_NOT_REACHED();
143
144 if (child->isFloatingOrOutOfFlowPositioned())
145 return m_builder.attachIgnoringContinuation(*beforeChildAncestor, WTFMove(child), beforeChild);
146
147 if (flow == beforeChildAncestor)
148 return m_builder.attachIgnoringContinuation(*flow, WTFMove(child), beforeChild);
149 // A continuation always consists of two potential candidates: an inline or an anonymous
150 // block box holding block children.
151 bool childInline = newChildIsInline(parent, *child);
152 // The goal here is to match up if we can, so that we can coalesce and create the
153 // minimal # of continuations needed for the inline.
154 if (childInline == beforeChildAncestor->isInline())
155 return m_builder.attachIgnoringContinuation(*beforeChildAncestor, WTFMove(child), beforeChild);
156 if (flow->isInline() == childInline)
157 return m_builder.attachIgnoringContinuation(*flow, WTFMove(child)); // Just treat like an append.
158 return m_builder.attachIgnoringContinuation(*beforeChildAncestor, WTFMove(child), beforeChild);
159}
160
161void RenderTreeBuilder::Inline::attachIgnoringContinuation(RenderInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
162{
163 // Make sure we don't append things after :after-generated content if we have it.
164 if (!beforeChild && parent.isAfterContent(parent.lastChild()))
165 beforeChild = parent.lastChild();
166
167 bool childInline = newChildIsInline(parent, *child);
168 // This code is for the old block-inside-inline model that uses continuations.
169 if (!childInline && !child->isFloatingOrOutOfFlowPositioned()) {
170 // We are placing a block inside an inline. We have to perform a split of this
171 // inline into continuations. This involves creating an anonymous block box to hold
172 // |newChild|. We then make that block box a continuation of this inline. We take all of
173 // the children after |beforeChild| and put them in a clone of this object.
174 auto newStyle = RenderStyle::createAnonymousStyleWithDisplay(parent.style(), DisplayType::Block);
175
176 // If inside an inline affected by in-flow positioning the block needs to be affected by it too.
177 // Giving the block a layer like this allows it to collect the x/y offsets from inline parents later.
178 if (auto positionedAncestor = inFlowPositionedInlineAncestor(parent))
179 newStyle.setPosition(positionedAncestor->style().position());
180
181 auto newBox = createRenderer<RenderBlockFlow>(parent.document(), WTFMove(newStyle));
182 newBox->initializeStyle();
183 newBox->setIsContinuation();
184 RenderBoxModelObject* oldContinuation = parent.continuation();
185 if (oldContinuation)
186 oldContinuation->removeFromContinuationChain();
187 newBox->insertIntoContinuationChainAfter(parent);
188
189 splitFlow(parent, beforeChild, WTFMove(newBox), WTFMove(child), oldContinuation);
190 return;
191 }
192
193 auto& childToAdd = *child;
194 m_builder.attachToRenderElement(parent, WTFMove(child), beforeChild);
195 childToAdd.setNeedsLayoutAndPrefWidthsRecalc();
196}
197
198void RenderTreeBuilder::Inline::splitFlow(RenderInline& parent, RenderObject* beforeChild, RenderPtr<RenderBlock> newBlockBox, RenderPtr<RenderObject> child, RenderBoxModelObject* oldCont)
199{
200 auto& addedBlockBox = *newBlockBox;
201 RenderBlock* pre = nullptr;
202 RenderBlock* block = parent.containingBlock();
203
204 // Delete our line boxes before we do the inline split into continuations.
205 block->deleteLines();
206
207 RenderPtr<RenderBlock> createdPre;
208 bool madeNewBeforeBlock = false;
209 if (block->isAnonymousBlock() && (!block->parent() || !block->parent()->createsAnonymousWrapper())) {
210 // We can reuse this block and make it the preBlock of the next continuation.
211 pre = block;
212 pre->removePositionedObjects(nullptr);
213 // FIXME-BLOCKFLOW: The enclosing method should likely be switched over
214 // to only work on RenderBlockFlow, in which case this conversion can be
215 // removed.
216 if (is<RenderBlockFlow>(*pre))
217 downcast<RenderBlockFlow>(*pre).removeFloatingObjects();
218 block = block->containingBlock();
219 } else {
220 // No anonymous block available for use. Make one.
221 createdPre = block->createAnonymousBlock();
222 pre = createdPre.get();
223 madeNewBeforeBlock = true;
224 }
225
226 auto createdPost = pre->createAnonymousBoxWithSameTypeAs(*block);
227 auto& post = downcast<RenderBlock>(*createdPost);
228
229 RenderObject* boxFirst = madeNewBeforeBlock ? block->firstChild() : pre->nextSibling();
230 if (createdPre)
231 m_builder.attachToRenderElementInternal(*block, WTFMove(createdPre), boxFirst);
232 m_builder.attachToRenderElementInternal(*block, WTFMove(newBlockBox), boxFirst);
233 m_builder.attachToRenderElementInternal(*block, WTFMove(createdPost), boxFirst);
234 block->setChildrenInline(false);
235
236 if (madeNewBeforeBlock) {
237 RenderObject* o = boxFirst;
238 while (o) {
239 RenderObject* no = o;
240 o = no->nextSibling();
241 auto childToMove = m_builder.detachFromRenderElement(*block, *no);
242 m_builder.attachToRenderElementInternal(*pre, WTFMove(childToMove));
243 no->setNeedsLayoutAndPrefWidthsRecalc();
244 }
245 }
246
247 splitInlines(parent, pre, &post, &addedBlockBox, beforeChild, oldCont);
248
249 // We already know the newBlockBox isn't going to contain inline kids, so avoid wasting
250 // time in makeChildrenNonInline by just setting this explicitly up front.
251 addedBlockBox.setChildrenInline(false);
252
253 // We delayed adding the newChild until now so that the |newBlockBox| would be fully
254 // connected, thus allowing newChild access to a renderArena should it need
255 // to wrap itself in additional boxes (e.g., table construction).
256 m_builder.attach(addedBlockBox, WTFMove(child));
257
258 // Always just do a full layout in order to ensure that line boxes (especially wrappers for images)
259 // get deleted properly. Because objects moves from the pre block into the post block, we want to
260 // make new line boxes instead of leaving the old line boxes around.
261 pre->setNeedsLayoutAndPrefWidthsRecalc();
262 block->setNeedsLayoutAndPrefWidthsRecalc();
263 post.setNeedsLayoutAndPrefWidthsRecalc();
264}
265
266void RenderTreeBuilder::Inline::splitInlines(RenderInline& parent, RenderBlock* fromBlock, RenderBlock* toBlock, RenderBlock* middleBlock, RenderObject* beforeChild, RenderBoxModelObject* oldCont)
267{
268 // Create a clone of this inline.
269 RenderPtr<RenderInline> cloneInline = cloneAsContinuation(parent);
270#if ENABLE(FULLSCREEN_API)
271 // If we're splitting the inline containing the fullscreened element,
272 // |beforeChild| may be the renderer for the fullscreened element. However,
273 // that renderer is wrapped in a RenderFullScreen, so |this| is not its
274 // parent. Since the splitting logic expects |this| to be the parent, set
275 // |beforeChild| to be the RenderFullScreen.
276 const Element* fullScreenElement = parent.document().fullscreenManager().currentFullscreenElement();
277 if (fullScreenElement && beforeChild && beforeChild->node() == fullScreenElement)
278 beforeChild = parent.document().fullscreenManager().fullscreenRenderer();
279#endif
280 // Now take all of the children from beforeChild to the end and remove
281 // them from |this| and place them in the clone.
282 for (RenderObject* rendererToMove = beforeChild; rendererToMove;) {
283 RenderObject* nextSibling = rendererToMove->nextSibling();
284 // When anonymous wrapper is present, we might need to move the whole subtree instead.
285 if (rendererToMove->parent() != &parent) {
286 auto* anonymousParent = rendererToMove->parent();
287 while (anonymousParent && anonymousParent->parent() != &parent) {
288 ASSERT(anonymousParent->isAnonymous());
289 anonymousParent = anonymousParent->parent();
290 }
291 if (!anonymousParent) {
292 ASSERT_NOT_REACHED();
293 break;
294 }
295 // If beforeChild is the first child in the subtree, we could just move the whole subtree.
296 if (!rendererToMove->previousSibling()) {
297 // Reparent the whole anonymous wrapper tree.
298 rendererToMove = anonymousParent;
299 // Skip to the next sibling that is not in this subtree.
300 nextSibling = anonymousParent->nextSibling();
301 } else if (!rendererToMove->nextSibling()) {
302 // This is the last renderer in the subtree. We need to jump out of the wrapper subtree, so that
303 // the siblings are getting reparented too.
304 nextSibling = anonymousParent->nextSibling();
305 }
306 // Otherwise just move the renderer to the inline clone. Should the renderer need an anon
307 // wrapper, the addChild() will generate one for it.
308 // FIXME: When the anonymous wrapper has multiple children, we end up traversing up to the topmost wrapper
309 // every time, which is a bit wasteful.
310 }
311 auto childToMove = m_builder.detachFromRenderElement(*rendererToMove->parent(), *rendererToMove);
312 m_builder.attachIgnoringContinuation(*cloneInline, WTFMove(childToMove));
313 rendererToMove->setNeedsLayoutAndPrefWidthsRecalc();
314 rendererToMove = nextSibling;
315 }
316 // Hook |clone| up as the continuation of the middle block.
317 cloneInline->insertIntoContinuationChainAfter(*middleBlock);
318 if (oldCont)
319 oldCont->insertIntoContinuationChainAfter(*cloneInline);
320
321 // We have been reparented and are now under the fromBlock. We need
322 // to walk up our inline parent chain until we hit the containing block.
323 // Once we hit the containing block we're done.
324 RenderBoxModelObject* current = downcast<RenderBoxModelObject>(parent.parent());
325 RenderBoxModelObject* currentChild = &parent;
326
327 // FIXME: Because splitting is O(n^2) as tags nest pathologically, we cap the depth at which we're willing to clone.
328 // There will eventually be a better approach to this problem that will let us nest to a much
329 // greater depth (see bugzilla bug 13430) but for now we have a limit. This *will* result in
330 // incorrect rendering, but the alternative is to hang forever.
331 unsigned splitDepth = 1;
332 const unsigned cMaxSplitDepth = 200;
333 while (current && current != fromBlock) {
334 if (splitDepth < cMaxSplitDepth) {
335 // Create a new clone.
336 RenderPtr<RenderInline> cloneChild = WTFMove(cloneInline);
337 cloneInline = cloneAsContinuation(downcast<RenderInline>(*current));
338
339 // Insert our child clone as the first child.
340 m_builder.attachIgnoringContinuation(*cloneInline, WTFMove(cloneChild));
341
342 // Hook the clone up as a continuation of |curr|.
343 cloneInline->insertIntoContinuationChainAfter(*current);
344
345 // Now we need to take all of the children starting from the first child
346 // *after* currentChild and append them all to the clone.
347 for (auto* sibling = currentChild->nextSibling(); sibling;) {
348 auto* next = sibling->nextSibling();
349 auto childToMove = m_builder.detachFromRenderElement(*current, *sibling);
350 m_builder.attachIgnoringContinuation(*cloneInline, WTFMove(childToMove));
351 sibling->setNeedsLayoutAndPrefWidthsRecalc();
352 sibling = next;
353 }
354 }
355
356 // Keep walking up the chain.
357 currentChild = current;
358 current = downcast<RenderBoxModelObject>(current->parent());
359 ++splitDepth;
360 }
361
362 // Clear the flow thread containing blocks cached during the detached state insertions.
363 for (auto& cloneBlockChild : childrenOfType<RenderBlock>(*cloneInline))
364 cloneBlockChild.resetEnclosingFragmentedFlowAndChildInfoIncludingDescendants();
365
366 // Now we are at the block level. We need to put the clone into the toBlock.
367 m_builder.attachToRenderElementInternal(*toBlock, WTFMove(cloneInline));
368
369 // Now take all the children after currentChild and remove them from the fromBlock
370 // and put them in the toBlock.
371 for (auto* current = currentChild->nextSibling(); current;) {
372 auto* next = current->nextSibling();
373 auto childToMove = m_builder.detachFromRenderElement(*fromBlock, *current);
374 m_builder.attachToRenderElementInternal(*toBlock, WTFMove(childToMove));
375 current = next;
376 }
377}
378
379bool RenderTreeBuilder::Inline::newChildIsInline(const RenderInline& parent, const RenderObject& child)
380{
381 // inline parent generates inline-table.
382 return child.isInline() || (m_builder.tableBuilder().childRequiresTable(parent, child) && parent.style().display() == DisplayType::Inline);
383}
384
385void RenderTreeBuilder::Inline::childBecameNonInline(RenderInline& parent, RenderElement& child)
386{
387 // We have to split the parent flow.
388 auto newBox = parent.containingBlock()->createAnonymousBlock();
389 newBox->setIsContinuation();
390 auto* oldContinuation = parent.continuation();
391 if (oldContinuation)
392 oldContinuation->removeFromContinuationChain();
393 newBox->insertIntoContinuationChainAfter(parent);
394 auto* beforeChild = child.nextSibling();
395 auto removedChild = m_builder.detachFromRenderElement(parent, child);
396 splitFlow(parent, beforeChild, WTFMove(newBox), WTFMove(removedChild), oldContinuation);
397}
398
399}
400