bf6ac02dfefdf08eb1125b58f25cac60d324e1e3
[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 void RenderTreeBuilder::insertChild(RenderTreePosition& position, RenderPtr<RenderObject> child)
191 {
192     insertChild(position.parent(), WTFMove(child), position.nextSibling());
193 }
194
195 void RenderTreeBuilder::insertChildToRenderElement(RenderElement& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
196 {
197     if (tableBuilder().childRequiresTable(parent, *child)) {
198         RenderTable* table;
199         RenderObject* afterChild = beforeChild ? beforeChild->previousSibling() : parent.lastChild();
200         if (afterChild && afterChild->isAnonymous() && is<RenderTable>(*afterChild) && !afterChild->isBeforeContent())
201             table = downcast<RenderTable>(afterChild);
202         else {
203             auto newTable = RenderTable::createAnonymousWithParentRenderer(parent);
204             table = newTable.get();
205             insertChild(parent, WTFMove(newTable), beforeChild);
206         }
207
208         insertChild(*table, WTFMove(child));
209         return;
210     }
211     parent.RenderElement::insertChildInternal(WTFMove(child), beforeChild);
212 }
213
214 void RenderTreeBuilder::insertChildToRenderBlock(RenderBlock& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
215 {
216     blockBuilder().insertChild(parent, WTFMove(child), beforeChild);
217 }
218
219 void RenderTreeBuilder::insertChildToRenderBlockIgnoringContinuation(RenderBlock& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
220 {
221     blockBuilder().insertChildIgnoringContinuation(parent, WTFMove(child), beforeChild);
222 }
223
224 void RenderTreeBuilder::makeChildrenNonInline(RenderBlock& parent, RenderObject* insertionPoint)
225 {
226     // makeChildrenNonInline takes a block whose children are *all* inline and it
227     // makes sure that inline children are coalesced under anonymous
228     // blocks. If |insertionPoint| is defined, then it represents the insertion point for
229     // the new block child that is causing us to have to wrap all the inlines. This
230     // means that we cannot coalesce inlines before |insertionPoint| with inlines following
231     // |insertionPoint|, because the new child is going to be inserted in between the inlines,
232     // splitting them.
233     ASSERT(parent.isInlineBlockOrInlineTable() || !parent.isInline());
234     ASSERT(!insertionPoint || insertionPoint->parent() == &parent);
235
236     parent.setChildrenInline(false);
237
238     auto* child = parent.firstChild();
239     if (!child)
240         return;
241
242     parent.deleteLines();
243
244     while (child) {
245         RenderObject* inlineRunStart = nullptr;
246         RenderObject* inlineRunEnd = nullptr;
247         getInlineRun(child, insertionPoint, inlineRunStart, inlineRunEnd);
248
249         if (!inlineRunStart)
250             break;
251
252         child = inlineRunEnd->nextSibling();
253
254         auto newBlock = parent.createAnonymousBlock();
255         auto& block = *newBlock;
256         parent.insertChildInternal(WTFMove(newBlock), inlineRunStart);
257         parent.moveChildrenTo(&block, inlineRunStart, child, RenderBoxModelObject::NormalizeAfterInsertion::No);
258     }
259 #ifndef NDEBUG
260     for (RenderObject* c = parent.firstChild(); c; c = c->nextSibling())
261         ASSERT(!c->isInline());
262 #endif
263     parent.repaint();
264 }
265
266 RenderObject* RenderTreeBuilder::splitAnonymousBoxesAroundChild(RenderBox& parent, RenderObject* beforeChild)
267 {
268     bool didSplitParentAnonymousBoxes = false;
269
270     while (beforeChild->parent() != &parent) {
271         auto& boxToSplit = downcast<RenderBox>(*beforeChild->parent());
272         if (boxToSplit.firstChild() != beforeChild && boxToSplit.isAnonymous()) {
273             didSplitParentAnonymousBoxes = true;
274
275             // We have to split the parent box into two boxes and move children
276             // from |beforeChild| to end into the new post box.
277             auto newPostBox = boxToSplit.createAnonymousBoxWithSameTypeAs(parent);
278             auto& postBox = *newPostBox;
279             postBox.setChildrenInline(boxToSplit.childrenInline());
280             RenderBox* parentBox = downcast<RenderBox>(boxToSplit.parent());
281             // We need to invalidate the |parentBox| before inserting the new node
282             // so that the table repainting logic knows the structure is dirty.
283             // See for example RenderTableCell:clippedOverflowRectForRepaint.
284             markBoxForRelayoutAfterSplit(*parentBox);
285             parentBox->insertChildInternal(WTFMove(newPostBox), boxToSplit.nextSibling());
286             boxToSplit.moveChildrenTo(&postBox, beforeChild, nullptr, RenderBoxModelObject::NormalizeAfterInsertion::Yes);
287
288             markBoxForRelayoutAfterSplit(boxToSplit);
289             markBoxForRelayoutAfterSplit(postBox);
290
291             beforeChild = &postBox;
292         } else
293             beforeChild = &boxToSplit;
294     }
295
296     if (didSplitParentAnonymousBoxes)
297         markBoxForRelayoutAfterSplit(parent);
298
299     ASSERT(beforeChild->parent() == &parent);
300     return beforeChild;
301 }
302
303 void RenderTreeBuilder::childFlowStateChangesAndAffectsParentBlock(RenderElement& child)
304 {
305     auto* parent = child.parent();
306     if (!child.isInline()) {
307         if (is<RenderBlock>(parent))
308             blockBuilder().childBecameNonInline(downcast<RenderBlock>(*parent), child);
309         else if (is<RenderInline>(*parent))
310             inlineBuilder().childBecameNonInline(downcast<RenderInline>(*parent), child);
311     } else {
312         // An anonymous block must be made to wrap this inline.
313         auto newBlock = downcast<RenderBlock>(*parent).createAnonymousBlock();
314         auto& block = *newBlock;
315         parent->insertChildInternal(WTFMove(newBlock), &child);
316         auto thisToMove = parent->takeChildInternal(child);
317         block.insertChildInternal(WTFMove(thisToMove), nullptr);
318     }
319 }
320
321 static bool isAnonymousAndSafeToDelete(RenderElement& element)
322 {
323     if (!element.isAnonymous())
324         return false;
325     if (element.isRenderView() || element.isRenderFragmentedFlow())
326         return false;
327     return true;
328 }
329
330 static RenderObject& findDestroyRootIncludingAnonymous(RenderObject& renderer)
331 {
332     auto* destroyRoot = &renderer;
333     while (true) {
334         auto& destroyRootParent = *destroyRoot->parent();
335         if (!isAnonymousAndSafeToDelete(destroyRootParent))
336             break;
337         bool destroyingOnlyChild = destroyRootParent.firstChild() == destroyRoot && destroyRootParent.lastChild() == destroyRoot;
338         if (!destroyingOnlyChild)
339             break;
340         destroyRoot = &destroyRootParent;
341     }
342     return *destroyRoot;
343 }
344
345 void RenderTreeBuilder::removeFromParentAndDestroyCleaningUpAnonymousWrappers(RenderObject& child)
346 {
347     // If the tree is destroyed, there is no need for a clean-up phase.
348     if (child.renderTreeBeingDestroyed()) {
349         child.removeFromParentAndDestroy();
350         return;
351     }
352
353     // Remove intruding floats from sibling blocks before detaching.
354     if (is<RenderBox>(child) && child.isFloatingOrOutOfFlowPositioned())
355         downcast<RenderBox>(child).removeFloatingOrPositionedChildFromBlockLists();
356     auto& destroyRoot = findDestroyRootIncludingAnonymous(child);
357     if (is<RenderTableRow>(destroyRoot))
358         tableBuilder().collapseAndDestroyAnonymousSiblingRows(downcast<RenderTableRow>(destroyRoot));
359
360     auto& destroyRootParent = *destroyRoot.parent();
361     destroyRootParent.removeAndDestroyChild(*this, destroyRoot);
362     destroyRootParent.removeAnonymousWrappersForInlinesIfNecessary();
363
364     // Anonymous parent might have become empty, try to delete it too.
365     if (isAnonymousAndSafeToDelete(destroyRootParent) && !destroyRootParent.firstChild())
366         removeFromParentAndDestroyCleaningUpAnonymousWrappers(destroyRootParent);
367     // WARNING: child is deleted here.
368 }
369
370 void RenderTreeBuilder::insertChildToRenderInline(RenderInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
371 {
372     inlineBuilder().insertChild(parent, WTFMove(child), beforeChild);
373 }
374
375 void RenderTreeBuilder::insertChildToRenderInlineIgnoringContinuation(RenderInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
376 {
377     inlineBuilder().insertChildIgnoringContinuation(parent, WTFMove(child), beforeChild);
378 }
379
380 void RenderTreeBuilder::insertChildToSVGContainer(RenderSVGContainer& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
381 {
382     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
383 }
384
385 void RenderTreeBuilder::insertChildToSVGInline(RenderSVGInline& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
386 {
387     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
388 }
389
390 void RenderTreeBuilder::insertChildToSVGRoot(RenderSVGRoot& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
391 {
392     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
393 }
394
395 void RenderTreeBuilder::insertChildToSVGText(RenderSVGText& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
396 {
397     svgBuilder().insertChild(parent, WTFMove(child), beforeChild);
398 }
399
400 void RenderTreeBuilder::insertChildToRenderTable(RenderTable& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
401 {
402     tableBuilder().insertChild(parent, WTFMove(child), beforeChild);
403 }
404
405 void RenderTreeBuilder::insertChildToRenderTableSection(RenderTableSection& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
406 {
407     tableBuilder().insertChild(parent, WTFMove(child), beforeChild);
408 }
409
410 void RenderTreeBuilder::insertChildToRenderTableRow(RenderTableRow& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
411 {
412     tableBuilder().insertChild(parent, WTFMove(child), beforeChild);
413 }
414
415 void RenderTreeBuilder::moveRubyChildren(RenderRubyBase& from, RenderRubyBase& to)
416 {
417     rubyBuilder().moveChildren(from, to);
418 }
419
420 void RenderTreeBuilder::insertChildToRenderBlockFlow(RenderBlockFlow& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
421 {
422     blockFlowBuilder().insertChild(parent, WTFMove(child), beforeChild);
423 }
424
425 void RenderTreeBuilder::insertChildToRenderMathMLFenced(RenderMathMLFenced& parent, RenderPtr<RenderObject> child, RenderObject* beforeChild)
426 {
427     mathMLBuilder().insertChild(parent, WTFMove(child), beforeChild);
428 }
429
430 void RenderTreeBuilder::updateAfterDescendants(RenderElement& renderer)
431 {
432     if (is<RenderBlock>(renderer))
433         firstLetterBuilder().updateAfterDescendants(downcast<RenderBlock>(renderer));
434     if (is<RenderListItem>(renderer))
435         listBuilder().updateItemMarker(downcast<RenderListItem>(renderer));
436     if (is<RenderBlockFlow>(renderer))
437         multiColumnBuilder().updateAfterDescendants(downcast<RenderBlockFlow>(renderer));
438 }
439
440 RenderObject* RenderTreeBuilder::resolveMovedChildForMultiColumnFlow(RenderFragmentedFlow& enclosingFragmentedFlow, RenderObject* beforeChild)
441 {
442     return multiColumnBuilder().resolveMovedChild(enclosingFragmentedFlow, beforeChild);
443 }
444
445 }