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