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