[WTF] Add makeUnique<T>, which ensures T is fast-allocated, makeUnique / makeUniqueWi...
[WebKit-https.git] / Source / WebCore / rendering / updating / RenderTreeBuilder.cpp
1 /*
2  * Copyright (C) 2017 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 "RenderTreeBuilder.h"
28
29 #include "AXObjectCache.h"
30 #include "Frame.h"
31 #include "FrameSelection.h"
32 #include "RenderButton.h"
33 #include "RenderCounter.h"
34 #include "RenderElement.h"
35 #include "RenderFullScreen.h"
36 #include "RenderGrid.h"
37 #include "RenderLineBreak.h"
38 #include "RenderMathMLFenced.h"
39 #include "RenderMenuList.h"
40 #include "RenderMultiColumnFlow.h"
41 #include "RenderRuby.h"
42 #include "RenderRubyBase.h"
43 #include "RenderRubyRun.h"
44 #include "RenderSVGContainer.h"
45 #include "RenderSVGInline.h"
46 #include "RenderSVGRoot.h"
47 #include "RenderSVGText.h"
48 #include "RenderTable.h"
49 #include "RenderTableRow.h"
50 #include "RenderTableSection.h"
51 #include "RenderText.h"
52 #include "RenderTextFragment.h"
53 #include "RenderTreeBuilderBlock.h"
54 #include "RenderTreeBuilderBlockFlow.h"
55 #include "RenderTreeBuilderContinuation.h"
56 #include "RenderTreeBuilderFirstLetter.h"
57 #include "RenderTreeBuilderFormControls.h"
58 #include "RenderTreeBuilderFullScreen.h"
59 #include "RenderTreeBuilderInline.h"
60 #include "RenderTreeBuilderList.h"
61 #include "RenderTreeBuilderMathML.h"
62 #include "RenderTreeBuilderMultiColumn.h"
63 #include "RenderTreeBuilderRuby.h"
64 #include "RenderTreeBuilderSVG.h"
65 #include "RenderTreeBuilderTable.h"
66
67 namespace WebCore {
68
69 RenderTreeBuilder* RenderTreeBuilder::s_current;
70
71 static void markBoxForRelayoutAfterSplit(RenderBox& box)
72 {
73     // FIXME: The table code should handle that automatically. If not,
74     // we should fix it and remove the table part checks.
75     if (is<RenderTable>(box)) {
76         // Because we may have added some sections with already computed column structures, we need to
77         // sync the table structure with them now. This avoids crashes when adding new cells to the table.
78         downcast<RenderTable>(box).forceSectionsRecalc();
79     } else if (is<RenderTableSection>(box))
80         downcast<RenderTableSection>(box).setNeedsCellRecalc();
81
82     box.setNeedsLayoutAndPrefWidthsRecalc();
83 }
84
85 static void getInlineRun(RenderObject* start, RenderObject* boundary, RenderObject*& inlineRunStart, RenderObject*& inlineRunEnd)
86 {
87     // Beginning at |start| we find the largest contiguous run of inlines that
88     // we can. We denote the run with start and end points, |inlineRunStart|
89     // and |inlineRunEnd|. Note that these two values may be the same if
90     // we encounter only one inline.
91     //
92     // We skip any non-inlines we encounter as long as we haven't found any
93     // inlines yet.
94     //
95     // |boundary| indicates a non-inclusive boundary point. Regardless of whether |boundary|
96     // is inline or not, we will not include it in a run with inlines before it. It's as though we encountered
97     // a non-inline.
98
99     // Start by skipping as many non-inlines as we can.
100     auto* curr = start;
101     bool sawInline;
102     do {
103         while (curr && !(curr->isInline() || curr->isFloatingOrOutOfFlowPositioned()))
104             curr = curr->nextSibling();
105
106         inlineRunStart = inlineRunEnd = curr;
107
108         if (!curr)
109             return; // No more inline children to be found.
110
111         sawInline = curr->isInline();
112
113         curr = curr->nextSibling();
114         while (curr && (curr->isInline() || curr->isFloatingOrOutOfFlowPositioned()) && (curr != boundary)) {
115             inlineRunEnd = curr;
116             if (curr->isInline())
117                 sawInline = true;
118             curr = curr->nextSibling();
119         }
120     } while (!sawInline);
121 }
122
123 RenderTreeBuilder::RenderTreeBuilder(RenderView& view)
124     : m_view(view)
125     , m_firstLetterBuilder(makeUnique<FirstLetter>(*this))
126     , m_listBuilder(makeUnique<List>(*this))
127     , m_multiColumnBuilder(makeUnique<MultiColumn>(*this))
128     , m_tableBuilder(makeUnique<Table>(*this))
129     , m_rubyBuilder(makeUnique<Ruby>(*this))
130     , m_formControlsBuilder(makeUnique<FormControls>(*this))
131     , m_blockBuilder(makeUnique<Block>(*this))
132     , m_blockFlowBuilder(makeUnique<BlockFlow>(*this))
133     , m_inlineBuilder(makeUnique<Inline>(*this))
134     , m_svgBuilder(makeUnique<SVG>(*this))
135 #if ENABLE(MATHML)
136     , m_mathMLBuilder(makeUnique<MathML>(*this))
137 #endif
138     , m_continuationBuilder(makeUnique<Continuation>(*this))
139 #if ENABLE(FULLSCREEN_API)
140     , m_fullScreenBuilder(makeUnique<FullScreen>(*this))
141 #endif
142 {
143     RELEASE_ASSERT(!s_current || &m_view != &s_current->m_view);
144     m_previous = s_current;
145     s_current = this;
146 }
147
148 RenderTreeBuilder::~RenderTreeBuilder()
149 {
150     s_current = m_previous;
151 }
152
153 void RenderTreeBuilder::destroy(RenderObject& renderer)
154 {
155     ASSERT(renderer.parent());
156     auto toDestroy = detach(*renderer.parent(), renderer);
157
158 #if ENABLE(FULLSCREEN_API)
159     if (is<RenderFullScreen>(renderer))
160         fullScreenBuilder().cleanupOnDestroy(downcast<RenderFullScreen>(renderer));
161 #endif
162
163     if (is<RenderTextFragment>(renderer))
164         firstLetterBuilder().cleanupOnDestroy(downcast<RenderTextFragment>(renderer));
165
166     if (is<RenderBoxModelObject>(renderer))
167         continuationBuilder().cleanupOnDestroy(downcast<RenderBoxModelObject>(renderer));
168
169     // We need to detach the subtree first so that the descendants don't have
170     // access to previous/next sublings at detach().
171     // FIXME: webkit.org/b/182909.
172     if (!is<RenderElement>(toDestroy.get()))
173         return;
174
175     auto& childToDestroy = downcast<RenderElement>(*toDestroy.get());
176     while (childToDestroy.firstChild()) {
177         auto& firstChild = *childToDestroy.firstChild();
178         if (auto* node = firstChild.node())
179             node->setRenderer(nullptr);
180         destroy(firstChild);
181     }
182 }
183
184 void RenderTreeBuilder::attach(RenderElement& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
185 {
186     auto insertRecursiveIfNeeded = [&](RenderElement& parentCandidate) {
187         if (&parent == &parentCandidate) {
188             attachToRenderElement(parent, WTFMove(child), beforeChild);
189             return;
190         }
191         attach(parentCandidate, WTFMove(child), beforeChild);
192     };
193
194     ASSERT(&parent.view() == &m_view);
195
196     if (is<RenderText>(beforeChild)) {
197         if (auto* wrapperInline = downcast<RenderText>(*beforeChild).inlineWrapperForDisplayContents())
198             beforeChild = wrapperInline;
199     }
200
201     if (is<RenderTableRow>(parent)) {
202         auto& parentCandidate = tableBuilder().findOrCreateParentForChild(downcast<RenderTableRow>(parent), *child, beforeChild);
203         if (&parentCandidate == &parent) {
204             tableBuilder().attach(downcast<RenderTableRow>(parentCandidate), WTFMove(child), beforeChild);
205             return;
206         }
207         insertRecursiveIfNeeded(parentCandidate);
208         return;
209     }
210
211     if (is<RenderTableSection>(parent)) {
212         auto& parentCandidate = tableBuilder().findOrCreateParentForChild(downcast<RenderTableSection>(parent), *child, beforeChild);
213         if (&parent == &parentCandidate) {
214             tableBuilder().attach(downcast<RenderTableSection>(parent), WTFMove(child), beforeChild);
215             return;
216         }
217         insertRecursiveIfNeeded(parentCandidate);
218         return;
219     }
220
221     if (is<RenderTable>(parent)) {
222         auto& parentCandidate = tableBuilder().findOrCreateParentForChild(downcast<RenderTable>(parent), *child, beforeChild);
223         if (&parentCandidate == &parent) {
224             tableBuilder().attach(downcast<RenderTable>(parentCandidate), WTFMove(child), beforeChild);
225             return;
226         }
227         insertRecursiveIfNeeded(parentCandidate);
228         return;
229     }
230
231     if (is<RenderRubyAsBlock>(parent)) {
232         insertRecursiveIfNeeded(rubyBuilder().findOrCreateParentForChild(downcast<RenderRubyAsBlock>(parent), *child, beforeChild));
233         return;
234     }
235
236     if (is<RenderRubyAsInline>(parent)) {
237         insertRecursiveIfNeeded(rubyBuilder().findOrCreateParentForChild(downcast<RenderRubyAsInline>(parent), *child, beforeChild));
238         return;
239     }
240
241     if (is<RenderRubyRun>(parent)) {
242         rubyBuilder().attach(downcast<RenderRubyRun>(parent), WTFMove(child), beforeChild);
243         return;
244     }
245
246     if (is<RenderButton>(parent)) {
247         formControlsBuilder().attach(downcast<RenderButton>(parent), WTFMove(child), beforeChild);
248         return;
249     }
250
251     if (is<RenderMenuList>(parent)) {
252         formControlsBuilder().attach(downcast<RenderMenuList>(parent), WTFMove(child), beforeChild);
253         return;
254     }
255
256     if (is<RenderSVGContainer>(parent)) {
257         svgBuilder().attach(downcast<RenderSVGContainer>(parent), WTFMove(child), beforeChild);
258         return;
259     }
260
261     if (is<RenderSVGInline>(parent)) {
262         svgBuilder().attach(downcast<RenderSVGInline>(parent), WTFMove(child), beforeChild);
263         return;
264     }
265
266     if (is<RenderSVGRoot>(parent)) {
267         svgBuilder().attach(downcast<RenderSVGRoot>(parent), WTFMove(child), beforeChild);
268         return;
269     }
270
271     if (is<RenderSVGText>(parent)) {
272         svgBuilder().attach(downcast<RenderSVGText>(parent), WTFMove(child), beforeChild);
273         return;
274     }
275
276 #if ENABLE(MATHML)
277     if (is<RenderMathMLFenced>(parent)) {
278         mathMLBuilder().attach(downcast<RenderMathMLFenced>(parent), WTFMove(child), beforeChild);
279         return;
280     }
281 #endif
282
283     if (is<RenderGrid>(parent)) {
284         attachToRenderGrid(downcast<RenderGrid>(parent), WTFMove(child), beforeChild);
285         return;
286     }
287
288     if (is<RenderBlockFlow>(parent)) {
289         blockFlowBuilder().attach(downcast<RenderBlockFlow>(parent), WTFMove(child), beforeChild);
290         return;
291     }
292
293     if (is<RenderBlock>(parent)) {
294         blockBuilder().attach(downcast<RenderBlock>(parent), WTFMove(child), beforeChild);
295         return;
296     }
297
298     if (is<RenderInline>(parent)) {
299         inlineBuilder().attach(downcast<RenderInline>(parent), WTFMove(child), beforeChild);
300         return;
301     }
302
303     attachToRenderElement(parent, WTFMove(child), beforeChild);
304 }
305
306 void RenderTreeBuilder::attachIgnoringContinuation(RenderElement& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
307 {
308     if (is<RenderInline>(parent)) {
309         inlineBuilder().attachIgnoringContinuation(downcast<RenderInline>(parent), WTFMove(child), beforeChild);
310         return;
311     }
312
313     if (is<RenderBlock>(parent)) {
314         blockBuilder().attachIgnoringContinuation(downcast<RenderBlock>(parent), WTFMove(child), beforeChild);
315         return;
316     }
317
318     attach(parent, WTFMove(child), beforeChild);
319 }
320
321 RenderPtr<RenderObject> RenderTreeBuilder::detach(RenderElement& parent, RenderObject& child, CanCollapseAnonymousBlock canCollapseAnonymousBlock)
322 {
323     if (is<RenderRubyAsInline>(parent))
324         return rubyBuilder().detach(downcast<RenderRubyAsInline>(parent), child);
325
326     if (is<RenderRubyAsBlock>(parent))
327         return rubyBuilder().detach(downcast<RenderRubyAsBlock>(parent), child);
328
329     if (is<RenderRubyRun>(parent))
330         return rubyBuilder().detach(downcast<RenderRubyRun>(parent), child);
331
332     if (is<RenderMenuList>(parent))
333         return formControlsBuilder().detach(downcast<RenderMenuList>(parent), child);
334
335     if (is<RenderButton>(parent))
336         return formControlsBuilder().detach(downcast<RenderButton>(parent), child);
337
338     if (is<RenderGrid>(parent))
339         return detachFromRenderGrid(downcast<RenderGrid>(parent), child);
340
341     if (is<RenderSVGText>(parent))
342         return svgBuilder().detach(downcast<RenderSVGText>(parent), child);
343
344     if (is<RenderSVGInline>(parent))
345         return svgBuilder().detach(downcast<RenderSVGInline>(parent), child);
346
347     if (is<RenderSVGContainer>(parent))
348         return svgBuilder().detach(downcast<RenderSVGContainer>(parent), child);
349
350     if (is<RenderSVGRoot>(parent))
351         return svgBuilder().detach(downcast<RenderSVGRoot>(parent), child);
352
353     if (is<RenderBlockFlow>(parent))
354         return blockBuilder().detach(downcast<RenderBlockFlow>(parent), child, canCollapseAnonymousBlock);
355
356     if (is<RenderBlock>(parent))
357         return blockBuilder().detach(downcast<RenderBlock>(parent), child, canCollapseAnonymousBlock);
358
359     return detachFromRenderElement(parent, child);
360 }
361
362 void RenderTreeBuilder::attach(RenderTreePosition& position, RenderPtr<RenderObject> child)
363 {
364     attach(position.parent(), WTFMove(child), position.nextSibling());
365 }
366
367 #if ENABLE(FULLSCREEN_API)
368 void RenderTreeBuilder::createPlaceholderForFullScreen(RenderFullScreen& renderer, std::unique_ptr<RenderStyle> style, const LayoutRect& frameRect)
369 {
370     fullScreenBuilder().createPlaceholder(renderer, WTFMove(style), frameRect);
371 }
372 #endif
373
374 void RenderTreeBuilder::attachToRenderElement(RenderElement& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
375 {
376     if (tableBuilder().childRequiresTable(parent, *child)) {
377         RenderTable* table;
378         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : parent.lastChild();
379         if (afterChild && afterChild->isAnonymous() && is<RenderTable>(*afterChild) && !afterChild->isBeforeContent())
380             table = downcast<RenderTable>(afterChild);
381         else {
382             auto newTable = RenderTable::createAnonymousWithParentRenderer(parent);
383             table = newTable.get();
384             attach(parent, WTFMove(newTable), beforeChild);
385         }
386
387         attach(*table, WTFMove(child));
388         return;
389     }
390     auto& newChild = *child.get();
391     attachToRenderElementInternal(parent, WTFMove(child), beforeChild);
392     parent.didAttachChild(newChild, beforeChild);
393 }
394
395 void RenderTreeBuilder::attachToRenderElementInternal(RenderElement& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
396 {
397     RELEASE_ASSERT_WITH_MESSAGE(!parent.view().frameView().layoutContext().layoutState(), "Layout must not mutate render tree");
398     ASSERT(parent.canHaveChildren() || parent.canHaveGeneratedChildren());
399     ASSERT(!child->parent());
400     ASSERT(!parent.isRenderBlockFlow() || (!child->isTableSection() && !child->isTableRow() && !child->isTableCell()));
401
402     while (beforeChild && beforeChild->parent() && beforeChild->parent() != &parent)
403         beforeChild = beforeChild->parent();
404
405     ASSERT(!beforeChild || beforeChild->parent() == &parent);
406     ASSERT(!is<RenderText>(beforeChild) || !downcast<RenderText>(*beforeChild).inlineWrapperForDisplayContents());
407
408     // Take the ownership.
409     auto* newChild = parent.attachRendererInternal(WTFMove(child), beforeChild);
410
411     newChild->initializeFragmentedFlowStateOnInsertion();
412     if (!parent.renderTreeBeingDestroyed()) {
413         newChild->insertedIntoTree();
414
415         auto* fragmentedFlow = newChild->enclosingFragmentedFlow();
416         if (is<RenderMultiColumnFlow>(fragmentedFlow))
417             multiColumnBuilder().multiColumnDescendantInserted(downcast<RenderMultiColumnFlow>(*fragmentedFlow), *newChild);
418
419         if (is<RenderElement>(*newChild))
420             RenderCounter::rendererSubtreeAttached(downcast<RenderElement>(*newChild));
421     }
422
423     newChild->setNeedsLayoutAndPrefWidthsRecalc();
424     parent.setPreferredLogicalWidthsDirty(true);
425     if (!parent.normalChildNeedsLayout())
426         parent.setChildNeedsLayout(); // We may supply the static position for an absolute positioned child.
427
428     if (AXObjectCache* cache = parent.document().axObjectCache())
429         cache->childrenChanged(&parent, newChild);
430     if (is<RenderBlockFlow>(parent))
431         downcast<RenderBlockFlow>(parent).invalidateLineLayoutPath();
432     if (parent.hasOutlineAutoAncestor() || parent.outlineStyleForRepaint().outlineStyleIsAuto() == OutlineIsAuto::On)
433         newChild->setHasOutlineAutoAncestor();
434 }
435
436 void RenderTreeBuilder::move(RenderBoxModelObject& from, RenderBoxModelObject& to, RenderObject& child, RenderObject* beforeChild, NormalizeAfterInsertion normalizeAfterInsertion)
437 {
438     // We assume that callers have cleared their positioned objects list for child moves so the
439     // positioned renderer maps don't become stale. It would be too slow to do the map lookup on each call.
440     ASSERT(normalizeAfterInsertion == NormalizeAfterInsertion::No || !is<RenderBlock>(from) || !downcast<RenderBlock>(from).hasPositionedObjects());
441
442     ASSERT(&from == child.parent());
443     ASSERT(!beforeChild || &to == beforeChild->parent());
444     if (normalizeAfterInsertion == NormalizeAfterInsertion::Yes && (to.isRenderBlock() || to.isRenderInline())) {
445         // Takes care of adding the new child correctly if toBlock and fromBlock
446         // have different kind of children (block vs inline).
447         auto childToMove = detachFromRenderElement(from, child);
448         attach(to, WTFMove(childToMove), beforeChild);
449     } else {
450         auto childToMove = detachFromRenderElement(from, child);
451         attachToRenderElementInternal(to, WTFMove(childToMove), beforeChild);
452     }
453 }
454
455 void RenderTreeBuilder::move(RenderBoxModelObject& from, RenderBoxModelObject& to, RenderObject& child, NormalizeAfterInsertion normalizeAfterInsertion)
456 {
457     move(from, to, child, nullptr, normalizeAfterInsertion);
458 }
459
460 void RenderTreeBuilder::moveAllChildren(RenderBoxModelObject& from, RenderBoxModelObject& to, NormalizeAfterInsertion normalizeAfterInsertion)
461 {
462     moveAllChildren(from, to, nullptr, normalizeAfterInsertion);
463 }
464
465 void RenderTreeBuilder::moveAllChildren(RenderBoxModelObject& from, RenderBoxModelObject& to, RenderObject* beforeChild, NormalizeAfterInsertion normalizeAfterInsertion)
466 {
467     moveChildren(from, to, from.firstChild(), nullptr, beforeChild, normalizeAfterInsertion);
468 }
469
470 void RenderTreeBuilder::moveChildren(RenderBoxModelObject& from, RenderBoxModelObject& to, RenderObject* startChild, RenderObject* endChild, NormalizeAfterInsertion normalizeAfterInsertion)
471 {
472     moveChildren(from, to, startChild, endChild, nullptr, normalizeAfterInsertion);
473 }
474
475 void RenderTreeBuilder::moveChildren(RenderBoxModelObject& from, RenderBoxModelObject& to, RenderObject* startChild, RenderObject* endChild, RenderObject* beforeChild, NormalizeAfterInsertion normalizeAfterInsertion)
476 {
477     // This condition is rarely hit since this function is usually called on
478     // anonymous blocks which can no longer carry positioned objects (see r120761)
479     // or when fullRemoveInsert is false.
480     if (normalizeAfterInsertion == NormalizeAfterInsertion::Yes && is<RenderBlock>(from)) {
481         downcast<RenderBlock>(from).removePositionedObjects(nullptr);
482         if (is<RenderBlockFlow>(from))
483             downcast<RenderBlockFlow>(from).removeFloatingObjects();
484     }
485
486     ASSERT(!beforeChild || &to == beforeChild->parent());
487     for (RenderObject* child = startChild; child && child != endChild; ) {
488         // Save our next sibling as moveChildTo will clear it.
489         RenderObject* nextSibling = child->nextSibling();
490
491         // FIXME: This logic here fails to detect the first letter in certain cases
492         // and skips a valid sibling renderer (see webkit.org/b/163737).
493         // Check to make sure we're not saving the firstLetter as the nextSibling.
494         // When the |child| object will be moved, its firstLetter will be recreated,
495         // so saving it now in nextSibling would leave us with a stale object.
496         if (is<RenderTextFragment>(*child) && is<RenderText>(nextSibling)) {
497             RenderObject* firstLetterObj = nullptr;
498             if (RenderBlock* block = downcast<RenderTextFragment>(*child).blockForAccompanyingFirstLetter()) {
499                 RenderElement* firstLetterContainer = nullptr;
500                 block->getFirstLetter(firstLetterObj, firstLetterContainer, child);
501             }
502
503             // This is the first letter, skip it.
504             if (firstLetterObj == nextSibling)
505                 nextSibling = nextSibling->nextSibling();
506         }
507
508         move(from, to, *child, beforeChild, normalizeAfterInsertion);
509         child = nextSibling;
510     }
511 }
512
513 void RenderTreeBuilder::moveAllChildrenIncludingFloats(RenderBlock& from, RenderBlock& to, RenderTreeBuilder::NormalizeAfterInsertion normalizeAfterInsertion)
514 {
515     if (is<RenderBlockFlow>(from)) {
516         blockFlowBuilder().moveAllChildrenIncludingFloats(downcast<RenderBlockFlow>(from), to, normalizeAfterInsertion);
517         return;
518     }
519     moveAllChildren(from, to, normalizeAfterInsertion);
520 }
521
522 void RenderTreeBuilder::normalizeTreeAfterStyleChange(RenderElement& renderer, RenderStyle& oldStyle)
523 {
524     if (!renderer.parent())
525         return;
526
527     auto& parent = *renderer.parent();
528
529     bool wasFloating = oldStyle.isFloating();
530     bool wasOufOfFlowPositioned = oldStyle.hasOutOfFlowPosition();
531     bool isFloating = renderer.style().isFloating();
532     bool isOutOfFlowPositioned = renderer.style().hasOutOfFlowPosition();
533     bool startsAffectingParent = false;
534     bool noLongerAffectsParent = false;
535
536     if (is<RenderBlock>(parent))
537         noLongerAffectsParent = (!wasFloating && isFloating) || (!wasOufOfFlowPositioned && isOutOfFlowPositioned);
538
539     if (is<RenderBlockFlow>(parent) || is<RenderInline>(parent)) {
540         startsAffectingParent = (wasFloating || wasOufOfFlowPositioned) && !isFloating && !isOutOfFlowPositioned;
541         ASSERT(!startsAffectingParent || !noLongerAffectsParent);
542     }
543
544     if (startsAffectingParent) {
545         // We have gone from not affecting the inline status of the parent flow to suddenly
546         // having an impact. See if there is a mismatch between the parent flow's
547         // childrenInline() state and our state.
548         // FIXME(186894): startsAffectingParent has clearly nothing to do with resetting the inline state.
549         if (!is<RenderSVGInline>(renderer))
550             renderer.setInline(renderer.style().isDisplayInlineType());
551         if (renderer.isInline() != renderer.parent()->childrenInline())
552             childFlowStateChangesAndAffectsParentBlock(renderer);
553         return;
554     }
555
556     if (noLongerAffectsParent) {
557         childFlowStateChangesAndNoLongerAffectsParentBlock(renderer);
558
559         if (is<RenderBlockFlow>(renderer)) {
560             // Fresh floats need to be reparented if they actually belong to the previous anonymous block.
561             // It copies the logic of RenderBlock::addChildIgnoringContinuation
562             if (isFloating && renderer.previousSibling() && renderer.previousSibling()->isAnonymousBlock())
563                 move(downcast<RenderBoxModelObject>(parent), downcast<RenderBoxModelObject>(*renderer.previousSibling()), renderer, RenderTreeBuilder::NormalizeAfterInsertion::No);
564         }
565     }
566 }
567
568 void RenderTreeBuilder::makeChildrenNonInline(RenderBlock& parent, RenderObject* insertionPoint)
569 {
570     // makeChildrenNonInline takes a block whose children are *all* inline and it
571     // makes sure that inline children are coalesced under anonymous
572     // blocks. If |insertionPoint| is defined, then it represents the insertion point for
573     // the new block child that is causing us to have to wrap all the inlines. This
574     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
575     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
576     // splitting them.
577     ASSERT(parent.isInlineBlockOrInlineTable() || !parent.isInline());
578     ASSERT(!insertionPoint || insertionPoint->parent() == &parent);
579
580     parent.setChildrenInline(false);
581
582     auto* child = parent.firstChild();
583     if (!child)
584         return;
585
586     parent.deleteLines();
587
588     while (child) {
589         RenderObject* inlineRunStart = nullptr;
590         RenderObject* inlineRunEnd = nullptr;
591         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
592
593         if (!inlineRunStart)
594             break;
595
596         child = inlineRunEnd->nextSibling();
597
598         auto newBlock = parent.createAnonymousBlock();
599         auto& block = *newBlock;
600         attachToRenderElementInternal(parent, WTFMove(newBlock), inlineRunStart);
601         moveChildren(parent, block, inlineRunStart, child, RenderTreeBuilder::NormalizeAfterInsertion::No);
602     }
603 #ifndef NDEBUG
604     for (RenderObject* c = parent.firstChild(); c; c = c->nextSibling())
605         ASSERT(!c->isInline());
606 #endif
607     parent.repaint();
608 }
609
610 RenderObject* RenderTreeBuilder::splitAnonymousBoxesAroundChild(RenderBox& parent, RenderObject& originalBeforeChild)
611 {
612     // Adjust beforeChild if it is a column spanner and has been moved out of its original position.
613     auto* beforeChild = RenderTreeBuilder::MultiColumn::adjustBeforeChildForMultiColumnSpannerIfNeeded(originalBeforeChild);
614     bool didSplitParentAnonymousBoxes = false;
615
616     while (beforeChild->parent() != &parent) {
617         auto& boxToSplit = downcast<RenderBox>(*beforeChild->parent());
618         if (boxToSplit.firstChild() != beforeChild && boxToSplit.isAnonymous()) {
619             didSplitParentAnonymousBoxes = true;
620
621             // We have to split the parent box into two boxes and move children
622             // from |beforeChild| to end into the new post box.
623             auto newPostBox = boxToSplit.createAnonymousBoxWithSameTypeAs(parent);
624             auto& postBox = *newPostBox;
625             postBox.setChildrenInline(boxToSplit.childrenInline());
626             RenderBox* parentBox = downcast<RenderBox>(boxToSplit.parent());
627             // We need to invalidate the |parentBox| before inserting the new node
628             // so that the table repainting logic knows the structure is dirty.
629             // See for example RenderTableCell:clippedOverflowRectForRepaint.
630             markBoxForRelayoutAfterSplit(*parentBox);
631             attachToRenderElementInternal(*parentBox, WTFMove(newPostBox), boxToSplit.nextSibling());
632             moveChildren(boxToSplit, postBox, beforeChild, nullptr, RenderTreeBuilder::NormalizeAfterInsertion::Yes);
633
634             markBoxForRelayoutAfterSplit(boxToSplit);
635             markBoxForRelayoutAfterSplit(postBox);
636
637             beforeChild = &postBox;
638         } else
639             beforeChild = &boxToSplit;
640     }
641
642     if (didSplitParentAnonymousBoxes)
643         markBoxForRelayoutAfterSplit(parent);
644
645     ASSERT(beforeChild->parent() == &parent);
646     return beforeChild;
647 }
648
649 void RenderTreeBuilder::childFlowStateChangesAndAffectsParentBlock(RenderElement& child)
650 {
651     auto* parent = child.parent();
652     if (!child.isInline()) {
653         if (is<RenderBlock>(parent))
654             blockBuilder().childBecameNonInline(downcast<RenderBlock>(*parent), child);
655         else if (is<RenderInline>(*parent))
656             inlineBuilder().childBecameNonInline(downcast<RenderInline>(*parent), child);
657
658         // childBecameNonInline might have re-parented us.
659         if (auto* newParent = child.parent()) {
660             // We need to re-run the grid items placement if it had gained a new item.
661             if (newParent != parent && is<RenderGrid>(*newParent))
662                 downcast<RenderGrid>(*newParent).dirtyGrid();
663         }
664     } else {
665         // An anonymous block must be made to wrap this inline.
666         auto newBlock = downcast<RenderBlock>(*parent).createAnonymousBlock();
667         auto& block = *newBlock;
668         attachToRenderElementInternal(*parent, WTFMove(newBlock), &child);
669         auto thisToMove = detachFromRenderElement(*parent, child);
670         attachToRenderElementInternal(block, WTFMove(thisToMove));
671     }
672 }
673
674 void RenderTreeBuilder::removeAnonymousWrappersForInlineChildrenIfNeeded(RenderElement& parent)
675 {
676     if (!is<RenderBlock>(parent))
677         return;
678     auto& blockParent = downcast<RenderBlock>(parent);
679     if (!blockParent.canDropAnonymousBlockChild())
680         return;
681
682     // We have changed to floated or out-of-flow positioning so maybe all our parent's
683     // children can be inline now. Bail if there are any block children left on the line,
684     // otherwise we can proceed to stripping solitary anonymous wrappers from the inlines.
685     // FIXME: We should also handle split inlines here - we exclude them at the moment by returning
686     // if we find a continuation.
687     Optional<bool> shouldAllChildrenBeInline;
688     for (auto* current = blockParent.firstChild(); current; current = current->nextSibling()) {
689         if (current->style().isFloating() || current->style().hasOutOfFlowPosition())
690             continue;
691         if (!current->isAnonymousBlock() || downcast<RenderBlock>(*current).isContinuation())
692             return;
693         // Anonymous block not in continuation. Check if it holds a set of inline or block children and try not to mix them.
694         auto* firstChild = current->firstChildSlow();
695         if (!firstChild)
696             continue;
697         auto isInlineLevelBox = firstChild->isInline();
698         if (!shouldAllChildrenBeInline.hasValue()) {
699             shouldAllChildrenBeInline = isInlineLevelBox;
700             continue;
701         }
702         // Mixing inline and block level boxes?
703         if (*shouldAllChildrenBeInline != isInlineLevelBox)
704             return;
705     }
706
707     RenderObject* next = nullptr;
708     for (auto* current = blockParent.firstChild(); current; current = next) {
709         next = current->nextSibling();
710         if (current->isAnonymousBlock())
711             blockBuilder().dropAnonymousBoxChild(blockParent, downcast<RenderBlock>(*current));
712     }
713 }
714
715 void RenderTreeBuilder::childFlowStateChangesAndNoLongerAffectsParentBlock(RenderElement& child)
716 {
717     ASSERT(child.parent());
718     removeAnonymousWrappersForInlineChildrenIfNeeded(*child.parent());
719 }
720
721 static bool isAnonymousAndSafeToDelete(RenderElement& element)
722 {
723     if (!element.isAnonymous())
724         return false;
725     if (element.isRenderView() || element.isRenderFragmentedFlow())
726         return false;
727     return true;
728 }
729
730 static RenderObject& findDestroyRootIncludingAnonymous(RenderObject& renderer)
731 {
732     auto* destroyRoot = &renderer;
733     while (true) {
734         auto& destroyRootParent = *destroyRoot->parent();
735         if (!isAnonymousAndSafeToDelete(destroyRootParent))
736             break;
737         bool destroyingOnlyChild = destroyRootParent.firstChild() == destroyRoot && destroyRootParent.lastChild() == destroyRoot;
738         if (!destroyingOnlyChild)
739             break;
740         destroyRoot = &destroyRootParent;
741     }
742     return *destroyRoot;
743 }
744
745 void RenderTreeBuilder::destroyAndCleanUpAnonymousWrappers(RenderObject& child)
746 {
747     // If the tree is destroyed, there is no need for a clean-up phase.
748     if (child.renderTreeBeingDestroyed()) {
749         destroy(child);
750         return;
751     }
752
753     // Remove intruding floats from sibling blocks before detaching.
754     if (is<RenderBox>(child) && child.isFloatingOrOutOfFlowPositioned())
755         downcast<RenderBox>(child).removeFloatingOrPositionedChildFromBlockLists();
756     auto& destroyRoot = findDestroyRootIncludingAnonymous(child);
757     if (is<RenderTableRow>(destroyRoot))
758         tableBuilder().collapseAndDestroyAnonymousSiblingRows(downcast<RenderTableRow>(destroyRoot));
759
760     // FIXME: Do not try to collapse/cleanup the anonymous wrappers inside destroy (see webkit.org/b/186746).
761     auto destroyRootParent = makeWeakPtr(*destroyRoot.parent());
762     destroy(destroyRoot);
763     if (!destroyRootParent)
764         return;
765     removeAnonymousWrappersForInlineChildrenIfNeeded(*destroyRootParent);
766
767     // Anonymous parent might have become empty, try to delete it too.
768     if (isAnonymousAndSafeToDelete(*destroyRootParent) && !destroyRootParent->firstChild())
769         destroyAndCleanUpAnonymousWrappers(*destroyRootParent);
770     // WARNING: child is deleted here.
771 }
772
773 void RenderTreeBuilder::updateAfterDescendants(RenderElement& renderer)
774 {
775     if (is<RenderBlock>(renderer))
776         firstLetterBuilder().updateAfterDescendants(downcast<RenderBlock>(renderer));
777     if (is<RenderListItem>(renderer))
778         listBuilder().updateItemMarker(downcast<RenderListItem>(renderer));
779     if (is<RenderBlockFlow>(renderer))
780         multiColumnBuilder().updateAfterDescendants(downcast<RenderBlockFlow>(renderer));
781 }
782
783 RenderPtr<RenderObject> RenderTreeBuilder::detachFromRenderGrid(RenderGrid& parent, RenderObject& child)
784 {
785     auto takenChild = blockBuilder().detach(parent, child);
786     // Positioned grid items do not take up space or otherwise participate in the layout of the grid,
787     // for that reason we don't need to mark the grid as dirty when they are removed.
788     if (child.isOutOfFlowPositioned())
789         return takenChild;
790
791     // The grid needs to be recomputed as it might contain auto-placed items that will change their position.
792     parent.dirtyGrid();
793     return takenChild;
794 }
795
796 RenderPtr<RenderObject> RenderTreeBuilder::detachFromRenderElement(RenderElement& parent, RenderObject& child)
797 {
798     RELEASE_ASSERT_WITH_MESSAGE(!parent.view().frameView().layoutContext().layoutState(), "Layout must not mutate render tree");
799
800     ASSERT(parent.canHaveChildren() || parent.canHaveGeneratedChildren());
801     ASSERT(child.parent() == &parent);
802
803     if (child.isFloatingOrOutOfFlowPositioned())
804         downcast<RenderBox>(child).removeFloatingOrPositionedChildFromBlockLists();
805
806     // So that we'll get the appropriate dirty bit set (either that a normal flow child got yanked or
807     // that a positioned child got yanked). We also repaint, so that the area exposed when the child
808     // disappears gets repainted properly.
809     if (!parent.renderTreeBeingDestroyed() && child.everHadLayout()) {
810         child.setNeedsLayoutAndPrefWidthsRecalc();
811         // We only repaint |child| if we have a RenderLayer as its visual overflow may not be tracked by its parent.
812         if (child.isBody())
813             parent.view().repaintRootContents();
814         else
815             child.repaint();
816     }
817
818     // If we have a line box wrapper, delete it.
819     if (is<RenderBox>(child))
820         downcast<RenderBox>(child).deleteLineBoxWrapper();
821     else if (is<RenderLineBreak>(child))
822         downcast<RenderLineBreak>(child).deleteInlineBoxWrapper();
823
824     if (!parent.renderTreeBeingDestroyed() && is<RenderFlexibleBox>(parent) && !child.isFloatingOrOutOfFlowPositioned() && child.isBox())
825         downcast<RenderFlexibleBox>(parent).clearCachedChildIntrinsicContentLogicalHeight(downcast<RenderBox>(child));
826
827     // If child is the start or end of the selection, then clear the selection to
828     // avoid problems of invalid pointers.
829     if (!parent.renderTreeBeingDestroyed() && child.isSelectionBorder())
830         parent.frame().selection().setNeedsSelectionUpdate();
831
832     if (!parent.renderTreeBeingDestroyed())
833         child.willBeRemovedFromTree();
834
835     child.resetFragmentedFlowStateOnRemoval();
836
837     // WARNING: There should be no code running between willBeRemovedFromTree() and the actual removal below.
838     // This is needed to avoid race conditions where willBeRemovedFromTree() would dirty the tree's structure
839     // and the code running here would force an untimely rebuilding, leaving |child| dangling.
840     auto childToTake = parent.detachRendererInternal(child);
841
842     // rendererRemovedFromTree() walks the whole subtree. We can improve performance
843     // by skipping this step when destroying the entire tree.
844     if (!parent.renderTreeBeingDestroyed() && is<RenderElement>(*childToTake))
845         RenderCounter::rendererRemovedFromTree(downcast<RenderElement>(*childToTake));
846
847     if (!parent.renderTreeBeingDestroyed()) {
848         if (AXObjectCache* cache = parent.document().existingAXObjectCache())
849             cache->childrenChanged(&parent);
850     }
851
852     return childToTake;
853 }
854
855 void RenderTreeBuilder::attachToRenderGrid(RenderGrid& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
856 {
857     auto& newChild = *child;
858     blockBuilder().attach(parent, WTFMove(child), beforeChild);
859
860     // Positioned grid items do not take up space or otherwise participate in the layout of the grid,
861     // for that reason we don't need to mark the grid as dirty when they are added.
862     if (newChild.isOutOfFlowPositioned())
863         return;
864
865     // The grid needs to be recomputed as it might contain auto-placed items that
866     // will change their position.
867     parent.dirtyGrid();
868 }
869
870 }