[RenderTreeBuilder] Introduce RenderTreebuilder::takeChild
[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 "RenderButton.h"
30 #include "RenderElement.h"
31 #include "RenderRuby.h"
32 #include "RenderRubyBase.h"
33 #include "RenderRubyRun.h"
34 #include "RenderTable.h"
35 #include "RenderTableRow.h"
36 #include "RenderTableSection.h"
37 #include "RenderText.h"
38 #include "RenderTreeBuilderBlock.h"
39 #include "RenderTreeBuilderBlockFlow.h"
40 #include "RenderTreeBuilderFirstLetter.h"
41 #include "RenderTreeBuilderFormControls.h"
42 #include "RenderTreeBuilderInline.h"
43 #include "RenderTreeBuilderList.h"
44 #include "RenderTreeBuilderMathML.h"
45 #include "RenderTreeBuilderMultiColumn.h"
46 #include "RenderTreeBuilderRuby.h"
47 #include "RenderTreeBuilderSVG.h"
48 #include "RenderTreeBuilderTable.h"
49
50 namespace WebCore {
51
52 RenderTreeBuilder* RenderTreeBuilder::s_current;
53
54 static void markBoxForRelayoutAfterSplit(RenderBox& box)
55 {
56     // FIXME: The table code should handle that automatically. If not,
57     // we should fix it and remove the table part checks.
58     if (is<RenderTable>(box)) {
59         // Because we may have added some sections with already computed column structures, we need to
60         // sync the table structure with them now. This avoids crashes when adding new cells to the table.
61         downcast<RenderTable>(box).forceSectionsRecalc();
62     } else if (is<RenderTableSection>(box))
63         downcast<RenderTableSection>(box).setNeedsCellRecalc();
64
65     box.setNeedsLayoutAndPrefWidthsRecalc();
66 }
67
68 static void getInlineRun(RenderObject* start, RenderObject* boundary, RenderObject*& inlineRunStart, RenderObject*& inlineRunEnd)
69 {
70     // Beginning at |start| we find the largest contiguous run of inlines that
71     // we can. We denote the run with start and end points, |inlineRunStart|
72     // and |inlineRunEnd|. Note that these two values may be the same if
73     // we encounter only one inline.
74     //
75     // We skip any non-inlines we encounter as long as we haven't found any
76     // inlines yet.
77     //
78     // |boundary| indicates a non-inclusive boundary point. Regardless of whether |boundary|
79     // is inline or not, we will not include it in a run with inlines before it. It's as though we encountered
80     // a non-inline.
81
82     // Start by skipping as many non-inlines as we can.
83     auto* curr = start;
84     bool sawInline;
85     do {
86         while (curr && !(curr->isInline() || curr->isFloatingOrOutOfFlowPositioned()))
87             curr = curr->nextSibling();
88
89         inlineRunStart = inlineRunEnd = curr;
90
91         if (!curr)
92             return; // No more inline children to be found.
93
94         sawInline = curr->isInline();
95
96         curr = curr->nextSibling();
97         while (curr && (curr->isInline() || curr->isFloatingOrOutOfFlowPositioned()) && (curr != boundary)) {
98             inlineRunEnd = curr;
99             if (curr->isInline())
100                 sawInline = true;
101             curr = curr->nextSibling();
102         }
103     } while (!sawInline);
104 }
105
106 RenderTreeBuilder::RenderTreeBuilder(RenderView& view)
107     : m_view(view)
108     , m_firstLetterBuilder(std::make_unique<FirstLetter>(*this))
109     , m_listBuilder(std::make_unique<List>(*this))
110     , m_multiColumnBuilder(std::make_unique<MultiColumn>(*this))
111     , m_tableBuilder(std::make_unique<Table>(*this))
112     , m_rubyBuilder(std::make_unique<Ruby>(*this))
113     , m_formControlsBuilder(std::make_unique<FormControls>(*this))
114     , m_blockBuilder(std::make_unique<Block>(*this))
115     , m_blockFlowBuilder(std::make_unique<BlockFlow>(*this))
116     , m_inlineBuilder(std::make_unique<Inline>(*this))
117     , m_svgBuilder(std::make_unique<SVG>(*this))
118     , m_mathMLBuilder(std::make_unique<MathML>(*this))
119 {
120     RELEASE_ASSERT(!s_current || &m_view != &s_current->m_view);
121     m_previous = s_current;
122     s_current = this;
123 }
124
125 RenderTreeBuilder::~RenderTreeBuilder()
126 {
127     s_current = m_previous;
128 }
129
130 void RenderTreeBuilder::insertChild(RenderElement& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
131 {
132     auto insertRecursiveIfNeeded = [&](RenderElement& parentCandidate) {
133         if (&parent == &parentCandidate) {
134             parent.addChild(*this, WTFMove(child), beforeChild);
135             return;
136         }
137         insertChild(parentCandidate, WTFMove(child), beforeChild);
138     };
139
140     ASSERT(&parent.view() == &m_view);
141
142     if (is<RenderText>(beforeChild)) {
143         if (auto* wrapperInline = downcast<RenderText>(*beforeChild).inlineWrapperForDisplayContents())
144             beforeChild = wrapperInline;
145     }
146
147     if (is<RenderTableRow>(parent)) {
148         insertRecursiveIfNeeded(tableBuilder().findOrCreateParentForChild(downcast<RenderTableRow>(parent), *child, beforeChild));
149         return;
150     }
151
152     if (is<RenderTableSection>(parent)) {
153         insertRecursiveIfNeeded(tableBuilder().findOrCreateParentForChild(downcast<RenderTableSection>(parent), *child, beforeChild));
154         return;
155     }
156
157     if (is<RenderTable>(parent)) {
158         insertRecursiveIfNeeded(tableBuilder().findOrCreateParentForChild(downcast<RenderTable>(parent), *child, beforeChild));
159         return;
160     }
161
162     if (is<RenderRubyAsBlock>(parent)) {
163         insertRecursiveIfNeeded(rubyBuilder().findOrCreateParentForChild(downcast<RenderRubyAsBlock>(parent), *child, beforeChild));
164         return;
165     }
166
167     if (is<RenderRubyAsInline>(parent)) {
168         insertRecursiveIfNeeded(rubyBuilder().findOrCreateParentForChild(downcast<RenderRubyAsInline>(parent), *child, beforeChild));
169         return;
170     }
171
172     if (is<RenderRubyRun>(parent)) {
173         rubyBuilder().insertChild(downcast<RenderRubyRun>(parent), WTFMove(child), beforeChild);
174         return;
175     }
176
177     if (is<RenderButton>(parent)) {
178         insertRecursiveIfNeeded(formControlsBuilder().createInnerRendererIfNeeded(downcast<RenderButton>(parent)));
179         return;
180     }
181
182     if (is<RenderMenuList>(parent)) {
183         insertRecursiveIfNeeded(formControlsBuilder().createInnerRendererIfNeeded(downcast<RenderMenuList>(parent)));
184         return;
185     }
186
187     parent.addChild(*this, WTFMove(child), beforeChild);
188 }
189
190 RenderPtr<RenderObject> RenderTreeBuilder::takeChild(RenderElement& parent, RenderObject& child)
191 {
192     if (is<RenderRubyAsInline>(parent))
193         return rubyBuilder().takeChild(downcast<RenderRubyAsInline>(parent), child);
194
195     if (is<RenderRubyAsBlock>(parent))
196         return rubyBuilder().takeChild(downcast<RenderRubyAsBlock>(parent), child);
197
198     if (is<RenderRubyRun>(parent))
199         return rubyBuilder().takeChild(downcast<RenderRubyRun>(parent), child);
200
201     return parent.takeChild(*this, child);
202 }
203
204 void RenderTreeBuilder::insertChild(RenderTreePosition& position, RenderPtr<RenderObject> child)
205 {
206     insertChild(position.parent(), WTFMove(child), position.nextSibling());
207 }
208
209 void RenderTreeBuilder::insertChildToRenderElement(RenderElement& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
210 {
211     if (tableBuilder().childRequiresTable(parent, *child)) {
212         RenderTable* table;
213         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : parent.lastChild();
214         if (afterChild && afterChild->isAnonymous() && is<RenderTable>(*afterChild) && !afterChild->isBeforeContent())
215             table = downcast<RenderTable>(afterChild);
216         else {
217             auto newTable = RenderTable::createAnonymousWithParentRenderer(parent);
218             table = newTable.get();
219             insertChild(parent, WTFMove(newTable), beforeChild);
220         }
221
222         insertChild(*table, WTFMove(child));
223         return;
224     }
225     parent.RenderElement::insertChildInternal(WTFMove(child), beforeChild);
226 }
227
228 void RenderTreeBuilder::insertChildToRenderBlock(RenderBlock& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
229 {
230     blockBuilder().insertChild(parent, WTFMove(child), beforeChild);
231 }
232
233 void RenderTreeBuilder::insertChildToRenderBlockIgnoringContinuation(RenderBlock& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
234 {
235     blockBuilder().insertChildIgnoringContinuation(parent, WTFMove(child), beforeChild);
236 }
237
238 void RenderTreeBuilder::makeChildrenNonInline(RenderBlock& parent, RenderObject* insertionPoint)
239 {
240     // makeChildrenNonInline takes a block whose children are *all* inline and it
241     // makes sure that inline children are coalesced under anonymous
242     // blocks. If |insertionPoint| is defined, then it represents the insertion point for
243     // the new block child that is causing us to have to wrap all the inlines. This
244     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
245     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
246     // splitting them.
247     ASSERT(parent.isInlineBlockOrInlineTable() || !parent.isInline());
248     ASSERT(!insertionPoint || insertionPoint->parent() == &parent);
249
250     parent.setChildrenInline(false);
251
252     auto* child = parent.firstChild();
253     if (!child)
254         return;
255
256     parent.deleteLines();
257
258     while (child) {
259         RenderObject* inlineRunStart = nullptr;
260         RenderObject* inlineRunEnd = nullptr;
261         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
262
263         if (!inlineRunStart)
264             break;
265
266         child = inlineRunEnd->nextSibling();
267
268         auto newBlock = parent.createAnonymousBlock();
269         auto& block = *newBlock;
270         parent.insertChildInternal(WTFMove(newBlock), inlineRunStart);
271         parent.moveChildrenTo(*this, &block, inlineRunStart, child, RenderBoxModelObject::NormalizeAfterInsertion::No);
272     }
273 #ifndef NDEBUG
274     for (RenderObject* c = parent.firstChild(); c; c = c->nextSibling())
275         ASSERT(!c->isInline());
276 #endif
277     parent.repaint();
278 }
279
280 RenderObject* RenderTreeBuilder::splitAnonymousBoxesAroundChild(RenderBox& parent, RenderObject* beforeChild)
281 {
282     bool didSplitParentAnonymousBoxes = false;
283
284     while (beforeChild->parent() != &parent) {
285         auto& boxToSplit = downcast<RenderBox>(*beforeChild->parent());
286         if (boxToSplit.firstChild() != beforeChild && boxToSplit.isAnonymous()) {
287             didSplitParentAnonymousBoxes = true;
288
289             // We have to split the parent box into two boxes and move children
290             // from |beforeChild| to end into the new post box.
291             auto newPostBox = boxToSplit.createAnonymousBoxWithSameTypeAs(parent);
292             auto& postBox = *newPostBox;
293             postBox.setChildrenInline(boxToSplit.childrenInline());
294             RenderBox* parentBox = downcast<RenderBox>(boxToSplit.parent());
295             // We need to invalidate the |parentBox| before inserting the new node
296             // so that the table repainting logic knows the structure is dirty.
297             // See for example RenderTableCell:clippedOverflowRectForRepaint.
298             markBoxForRelayoutAfterSplit(*parentBox);
299             parentBox->insertChildInternal(WTFMove(newPostBox), boxToSplit.nextSibling());
300             boxToSplit.moveChildrenTo(*this, &postBox, beforeChild, nullptr, RenderBoxModelObject::NormalizeAfterInsertion::Yes);
301
302             markBoxForRelayoutAfterSplit(boxToSplit);
303             markBoxForRelayoutAfterSplit(postBox);
304
305             beforeChild = &postBox;
306         } else
307             beforeChild = &boxToSplit;
308     }
309
310     if (didSplitParentAnonymousBoxes)
311         markBoxForRelayoutAfterSplit(parent);
312
313     ASSERT(beforeChild->parent() == &parent);
314     return beforeChild;
315 }
316
317 void RenderTreeBuilder::childFlowStateChangesAndAffectsParentBlock(RenderElement& child)
318 {
319     auto* parent = child.parent();
320     if (!child.isInline()) {
321         if (is<RenderBlock>(parent))
322             blockBuilder().childBecameNonInline(downcast<RenderBlock>(*parent), child);
323         else if (is<RenderInline>(*parent))
324             inlineBuilder().childBecameNonInline(downcast<RenderInline>(*parent), child);
325     } else {
326         // An anonymous block must be made to wrap this inline.
327         auto newBlock = downcast<RenderBlock>(*parent).createAnonymousBlock();
328         auto& block = *newBlock;
329         parent->insertChildInternal(WTFMove(newBlock), &child);
330         auto thisToMove = parent->takeChildInternal(child);
331         block.insertChildInternal(WTFMove(thisToMove), nullptr);
332     }
333 }
334
335 void RenderTreeBuilder::removeAnonymousWrappersForInlineChildrenIfNeeded(RenderElement& parent)
336 {
337     if (!is<RenderBlock>(parent))
338         return;
339     auto& blockParent = downcast<RenderBlock>(parent);
340     if (!blockParent.canDropAnonymousBlockChild())
341         return;
342
343     // We have changed to floated or out-of-flow positioning so maybe all our parent's
344     // children can be inline now. Bail if there are any block children left on the line,
345     // otherwise we can proceed to stripping solitary anonymous wrappers from the inlines.
346     // FIXME: We should also handle split inlines here - we exclude them at the moment by returning
347     // if we find a continuation.
348     auto* current = blockParent.firstChild();
349     while (current && ((current->isAnonymousBlock() && !downcast<RenderBlock>(*current).isContinuation()) || current->style().isFloating() || current->style().hasOutOfFlowPosition()))
350         current = current->nextSibling();
351
352     if (current)
353         return;
354
355     RenderObject* next;
356     for (current = blockParent.firstChild(); current; current = next) {
357         next = current->nextSibling();
358         if (current->isAnonymousBlock())
359             blockBuilder().dropAnonymousBoxChild(blockParent, downcast<RenderBlock>(*current));
360     }
361 }
362
363 void RenderTreeBuilder::childFlowStateChangesAndNoLongerAffectsParentBlock(RenderElement& child)
364 {
365     ASSERT(child.parent());
366     removeAnonymousWrappersForInlineChildrenIfNeeded(*child.parent());
367 }
368
369 void RenderTreeBuilder::multiColumnDescendantInserted(RenderMultiColumnFlow& flow, RenderObject& newDescendant)
370 {
371     multiColumnBuilder().multiColumnDescendantInserted(flow, newDescendant);
372 }
373
374 static bool isAnonymousAndSafeToDelete(RenderElement& element)
375 {
376     if (!element.isAnonymous())
377         return false;
378     if (element.isRenderView() || element.isRenderFragmentedFlow())
379         return false;
380     return true;
381 }
382
383 static RenderObject& findDestroyRootIncludingAnonymous(RenderObject& renderer)
384 {
385     auto* destroyRoot = &renderer;
386     while (true) {
387         auto& destroyRootParent = *destroyRoot->parent();
388         if (!isAnonymousAndSafeToDelete(destroyRootParent))
389             break;
390         bool destroyingOnlyChild = destroyRootParent.firstChild() == destroyRoot && destroyRootParent.lastChild() == destroyRoot;
391         if (!destroyingOnlyChild)
392             break;
393         destroyRoot = &destroyRootParent;
394     }
395     return *destroyRoot;
396 }
397
398 void RenderTreeBuilder::removeFromParentAndDestroyCleaningUpAnonymousWrappers(RenderObject& child)
399 {
400     // If the tree is destroyed, there is no need for a clean-up phase.
401     if (child.renderTreeBeingDestroyed()) {
402         child.removeFromParentAndDestroy(*this);
403         return;
404     }
405
406     // Remove intruding floats from sibling blocks before detaching.
407     if (is<RenderBox>(child) && child.isFloatingOrOutOfFlowPositioned())
408         downcast<RenderBox>(child).removeFloatingOrPositionedChildFromBlockLists();
409     auto& destroyRoot = findDestroyRootIncludingAnonymous(child);
410     if (is<RenderTableRow>(destroyRoot))
411         tableBuilder().collapseAndDestroyAnonymousSiblingRows(downcast<RenderTableRow>(destroyRoot));
412
413     auto& destroyRootParent = *destroyRoot.parent();
414     destroyRootParent.removeAndDestroyChild(*this, destroyRoot);
415     removeAnonymousWrappersForInlineChildrenIfNeeded(destroyRootParent);
416
417     // Anonymous parent might have become empty, try to delete it too.
418     if (isAnonymousAndSafeToDelete(destroyRootParent) && !destroyRootParent.firstChild())
419         removeFromParentAndDestroyCleaningUpAnonymousWrappers(destroyRootParent);
420     // WARNING: child is deleted here.
421 }
422
423 void RenderTreeBuilder::dropAnonymousBoxChild(RenderBlock& parent, RenderBlock& child)
424 {
425     blockBuilder().dropAnonymousBoxChild(parent, child);
426 }
427
428 void RenderTreeBuilder::multiColumnRelativeWillBeRemoved(RenderMultiColumnFlow& flow, RenderObject& relative)
429 {
430     multiColumnBuilder().multiColumnRelativeWillBeRemoved(flow, relative);
431 }
432
433 void RenderTreeBuilder::insertChildToRenderInline(RenderInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
434 {
435     inlineBuilder().insertChild(parent, WTFMove(child), beforeChild);
436 }
437
438 void RenderTreeBuilder::insertChildToRenderInlineIgnoringContinuation(RenderInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
439 {
440     inlineBuilder().insertChildIgnoringContinuation(parent, WTFMove(child), beforeChild);
441 }
442
443 void RenderTreeBuilder::insertChildToSVGContainer(RenderSVGContainer& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
444 {
445     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
446 }
447
448 void RenderTreeBuilder::insertChildToSVGInline(RenderSVGInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
449 {
450     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
451 }
452
453 void RenderTreeBuilder::insertChildToSVGRoot(RenderSVGRoot& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
454 {
455     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
456 }
457
458 void RenderTreeBuilder::insertChildToSVGText(RenderSVGText& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
459 {
460     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
461 }
462
463 void RenderTreeBuilder::insertChildToRenderTable(RenderTable& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
464 {
465     tableBuilder().insertChild(parent, WTFMove(child), beforeChild);
466 }
467
468 void RenderTreeBuilder::insertChildToRenderTableSection(RenderTableSection& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
469 {
470     tableBuilder().insertChild(parent, WTFMove(child), beforeChild);
471 }
472
473 void RenderTreeBuilder::insertChildToRenderTableRow(RenderTableRow& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
474 {
475     tableBuilder().insertChild(parent, WTFMove(child), beforeChild);
476 }
477
478 void RenderTreeBuilder::moveRubyChildren(RenderRubyBase& from, RenderRubyBase& to)
479 {
480     rubyBuilder().moveChildren(from, to);
481 }
482
483 void RenderTreeBuilder::insertChildToRenderBlockFlow(RenderBlockFlow& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
484 {
485     blockFlowBuilder().insertChild(parent, WTFMove(child), beforeChild);
486 }
487
488 void RenderTreeBuilder::insertChildToRenderMathMLFenced(RenderMathMLFenced& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
489 {
490     mathMLBuilder().insertChild(parent, WTFMove(child), beforeChild);
491 }
492
493 RenderPtr<RenderObject> RenderTreeBuilder::takeChildFromRenderBlock(RenderBlock& parent, RenderObject& oldChild)
494 {
495     return blockBuilder().takeChild(parent, oldChild);
496 }
497
498 void RenderTreeBuilder::updateAfterDescendants(RenderElement& renderer)
499 {
500     if (is<RenderBlock>(renderer))
501         firstLetterBuilder().updateAfterDescendants(downcast<RenderBlock>(renderer));
502     if (is<RenderListItem>(renderer))
503         listBuilder().updateItemMarker(downcast<RenderListItem>(renderer));
504     if (is<RenderBlockFlow>(renderer))
505         multiColumnBuilder().updateAfterDescendants(downcast<RenderBlockFlow>(renderer));
506 }
507
508 RenderObject* RenderTreeBuilder::resolveMovedChildForMultiColumnFlow(RenderFragmentedFlow& enclosingFragmentedFlow, RenderObject* beforeChild)
509 {
510     return multiColumnBuilder().resolveMovedChild(enclosingFragmentedFlow, beforeChild);
511 }
512
513 }