[RenderTreeBuilder] Introduce RenderTreebuilder::takeChild
[WebKit-https.git] / Source / WebCore / rendering / updating / RenderTreeBuilderMultiColumn.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2007 David Smith (catfish.man@gmail.com)
5  * Copyright (C) 2003-2015, 2017 Apple Inc. All rights reserved.
6  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25 #include "RenderTreeBuilderMultiColumn.h"
26
27 #include "RenderBlockFlow.h"
28 #include "RenderChildIterator.h"
29 #include "RenderLinesClampFlow.h"
30 #include "RenderMultiColumnFlow.h"
31 #include "RenderMultiColumnSet.h"
32 #include "RenderMultiColumnSpannerPlaceholder.h"
33 #include "RenderTreeBuilder.h"
34
35 namespace WebCore {
36
37 static RenderMultiColumnSet* findSetRendering(const RenderMultiColumnFlow& fragmentedFlow, const RenderObject& renderer)
38 {
39     // Find the set inside which the specified renderer would be rendered.
40     for (auto* multicolSet = fragmentedFlow.firstMultiColumnSet(); multicolSet; multicolSet = multicolSet->nextSiblingMultiColumnSet()) {
41         if (multicolSet->containsRendererInFragmentedFlow(renderer))
42             return multicolSet;
43     }
44     return nullptr;
45 }
46
47 static RenderObject* spannerPlacehoderCandidate(const RenderObject& renderer, const RenderMultiColumnFlow& stayWithin)
48 {
49     // Spanner candidate is a next sibling/ancestor's next child within the flow thread and
50     // it is in the same inflow/out-of-flow layout context.
51     if (renderer.isOutOfFlowPositioned())
52         return nullptr;
53
54     ASSERT(renderer.isDescendantOf(&stayWithin));
55     auto* current = &renderer;
56     while (true) {
57         // Skip to the first in-flow sibling.
58         auto* nextSibling = current->nextSibling();
59         while (nextSibling && nextSibling->isOutOfFlowPositioned())
60             nextSibling = nextSibling->nextSibling();
61         if (nextSibling)
62             return nextSibling;
63         // No sibling candidate, jump to the parent and check its siblings.
64         current = current->parent();
65         if (!current || current == &stayWithin || current->isOutOfFlowPositioned())
66             return nullptr;
67     }
68     return nullptr;
69 }
70
71 static bool isValidColumnSpanner(const RenderMultiColumnFlow& fragmentedFlow, const RenderObject& descendant)
72 {
73     // We assume that we're inside the flow thread. This function is not to be called otherwise.
74     ASSERT(descendant.isDescendantOf(&fragmentedFlow));
75     // First make sure that the renderer itself has the right properties for becoming a spanner.
76     if (!is<RenderBox>(descendant))
77         return false;
78
79     auto& descendantBox = downcast<RenderBox>(descendant);
80     if (descendantBox.isFloatingOrOutOfFlowPositioned())
81         return false;
82
83     if (!fragmentedFlow.isColumnSpanningDescendant(descendantBox))
84         return false;
85
86     auto* parent = descendantBox.parent();
87     if (!is<RenderBlockFlow>(*parent) || parent->childrenInline()) {
88         // Needs to be block-level.
89         return false;
90     }
91
92     // We need to have the flow thread as the containing block. A spanner cannot break out of the flow thread.
93     auto* enclosingFragmentedFlow = descendantBox.enclosingFragmentedFlow();
94     if (enclosingFragmentedFlow != &fragmentedFlow)
95         return false;
96
97     // This looks like a spanner, but if we're inside something unbreakable, it's not to be treated as one.
98     for (auto* ancestor = descendantBox.containingBlock(); ancestor; ancestor = ancestor->containingBlock()) {
99         if (is<RenderView>(*ancestor))
100             return false;
101         if (is<RenderFragmentedFlow>(*ancestor)) {
102             // Don't allow any intervening non-multicol fragmentation contexts. The spec doesn't say
103             // anything about disallowing this, but it's just going to be too complicated to
104             // implement (not to mention specify behavior).
105             return ancestor == &fragmentedFlow;
106         }
107         // This ancestor (descendent of the fragmentedFlow) will create columns later. The spanner belongs to it.
108         if (is<RenderBlockFlow>(*ancestor) && downcast<RenderBlockFlow>(*ancestor).willCreateColumns())
109             return false;
110         ASSERT(ancestor->style().columnSpan() != ColumnSpanAll || !isValidColumnSpanner(fragmentedFlow, *ancestor));
111         if (ancestor->isUnsplittableForPagination())
112             return false;
113     }
114     ASSERT_NOT_REACHED();
115     return false;
116 }
117
118 RenderTreeBuilder::MultiColumn::MultiColumn(RenderTreeBuilder& builder)
119     : m_builder(builder)
120 {
121 }
122
123 void RenderTreeBuilder::MultiColumn::updateAfterDescendants(RenderBlockFlow& flow)
124 {
125     bool needsFragmentedFlow = flow.requiresColumns(flow.style().columnCount());
126     bool hasFragmentedFlow = flow.multiColumnFlow();
127
128     if (!hasFragmentedFlow && needsFragmentedFlow) {
129         createFragmentedFlow(flow);
130         return;
131     }
132     if (hasFragmentedFlow && !needsFragmentedFlow) {
133         destroyFragmentedFlow(flow);
134         return;
135     }
136 }
137
138 void RenderTreeBuilder::MultiColumn::createFragmentedFlow(RenderBlockFlow& flow)
139 {
140     flow.setChildrenInline(false); // Do this to avoid wrapping inline children that are just going to move into the flow thread.
141     flow.deleteLines();
142     // If this soon-to-be multicolumn flow is already part of a multicolumn context, we need to move back the descendant spanners
143     // to their original position before moving subtrees around.
144     auto* enclosingflow = flow.enclosingFragmentedFlow();
145     if (is<RenderMultiColumnFlow>(enclosingflow)) {
146         auto& spanners = downcast<RenderMultiColumnFlow>(enclosingflow)->spannerMap();
147         Vector<RenderMultiColumnSpannerPlaceholder*> placeholdersToDelete;
148         for (auto& spannerAndPlaceholder : spanners) {
149             auto& placeholder = *spannerAndPlaceholder.value;
150             if (!placeholder.isDescendantOf(&flow))
151                 continue;
152             placeholdersToDelete.append(&placeholder);
153         }
154         for (auto* placeholder : placeholdersToDelete) {
155             auto* spanner = placeholder->spanner();
156             if (!spanner) {
157                 ASSERT_NOT_REACHED();
158                 continue;
159             }
160             // Move the spanner back to its original position.
161             auto& spannerOriginalParent = *placeholder->parent();
162             // Detaching the spanner takes care of removing the placeholder (and merges the RenderMultiColumnSets).
163             auto spannerToReInsert = m_builder.takeChild(*spanner->parent(), *spanner);
164             m_builder.insertChild(spannerOriginalParent, WTFMove(spannerToReInsert));
165         }
166     }
167
168     auto newFragmentedFlow = !flow.style().hasLinesClamp() ? WebCore::createRenderer<RenderMultiColumnFlow>(flow.document(), RenderStyle::createAnonymousStyleWithDisplay(flow.style(), BLOCK)) :  WebCore::createRenderer<RenderLinesClampFlow>(flow.document(), RenderStyle::createAnonymousStyleWithDisplay(flow.style(), BLOCK));
169     newFragmentedFlow->initializeStyle();
170     auto& fragmentedFlow = *newFragmentedFlow;
171     m_builder.insertChildToRenderBlock(flow, WTFMove(newFragmentedFlow));
172
173     // Reparent children preceding the fragmented flow into the fragmented flow.
174     flow.moveChildrenTo(m_builder, &fragmentedFlow, flow.firstChild(), &fragmentedFlow, RenderBoxModelObject::NormalizeAfterInsertion::Yes);
175     if (flow.isFieldset()) {
176         // Keep legends out of the flow thread.
177         for (auto& box : childrenOfType<RenderBox>(fragmentedFlow)) {
178             if (box.isLegend())
179                 fragmentedFlow.moveChildTo(m_builder, &flow, &box, RenderBoxModelObject::NormalizeAfterInsertion::Yes);
180         }
181     }
182
183     if (flow.style().hasLinesClamp()) {
184         // Keep the middle block out of the flow thread.
185         for (auto& element : childrenOfType<RenderElement>(fragmentedFlow)) {
186             if (!downcast<RenderLinesClampFlow>(fragmentedFlow).isChildAllowedInFragmentedFlow(flow, element))
187                 fragmentedFlow.moveChildTo(m_builder, &flow, &element, RenderBoxModelObject::NormalizeAfterInsertion::Yes);
188         }
189     }
190
191     flow.setMultiColumnFlow(fragmentedFlow);
192 }
193
194 void RenderTreeBuilder::MultiColumn::destroyFragmentedFlow(RenderBlockFlow& flow)
195 {
196     auto& multiColumnFlow = *flow.multiColumnFlow();
197     multiColumnFlow.deleteLines();
198
199     // Move spanners back to their original DOM position in the tree, and destroy the placeholders.
200     auto& spanners = multiColumnFlow.spannerMap();
201     Vector<RenderMultiColumnSpannerPlaceholder*> placeholdersToDelete;
202     for (auto& spannerAndPlaceholder : spanners)
203         placeholdersToDelete.append(spannerAndPlaceholder.value.get());
204     Vector<std::pair<RenderElement*, RenderPtr<RenderObject>>> parentAndSpannerList;
205     for (auto* placeholder : placeholdersToDelete) {
206         auto* spannerOriginalParent = placeholder->parent();
207         if (spannerOriginalParent == &multiColumnFlow)
208             spannerOriginalParent = &flow;
209         // Detaching the spanner takes care of removing the placeholder (and merges the RenderMultiColumnSets).
210         auto* spanner = placeholder->spanner();
211         parentAndSpannerList.append(std::make_pair(spannerOriginalParent, m_builder.takeChild(*spanner->parent(), *spanner)));
212     }
213     while (auto* columnSet = multiColumnFlow.firstMultiColumnSet())
214         columnSet->removeFromParentAndDestroy(m_builder);
215
216     flow.clearMultiColumnFlow();
217     multiColumnFlow.moveAllChildrenTo(m_builder, &flow, RenderBoxModelObject::NormalizeAfterInsertion::Yes);
218     multiColumnFlow.removeFromParentAndDestroy(m_builder);
219     for (auto& parentAndSpanner : parentAndSpannerList)
220         m_builder.insertChild(*parentAndSpanner.first, WTFMove(parentAndSpanner.second));
221 }
222
223
224 RenderObject* RenderTreeBuilder::MultiColumn::resolveMovedChild(RenderFragmentedFlow& enclosingFragmentedFlow, RenderObject* beforeChild)
225 {
226     if (!beforeChild)
227         return nullptr;
228
229     if (!is<RenderBox>(*beforeChild))
230         return beforeChild;
231
232     if (!is<RenderMultiColumnFlow>(enclosingFragmentedFlow))
233         return beforeChild;
234
235     // We only need to resolve for column spanners.
236     if (beforeChild->style().columnSpan() != ColumnSpanAll)
237         return beforeChild;
238
239     // The renderer for the actual DOM node that establishes a spanner is moved from its original
240     // location in the render tree to becoming a sibling of the column sets. In other words, it's
241     // moved out from the flow thread (and becomes a sibling of it). When we for instance want to
242     // create and insert a renderer for the sibling node immediately preceding the spanner, we need
243     // to map that spanner renderer to the spanner's placeholder, which is where the new inserted
244     // renderer belongs.
245     if (auto* placeholder = downcast<RenderMultiColumnFlow>(enclosingFragmentedFlow).findColumnSpannerPlaceholder(downcast<RenderBox>(beforeChild)))
246         return placeholder;
247
248     // This is an invalid spanner, or its placeholder hasn't been created yet. This happens when
249     // moving an entire subtree into the flow thread, when we are processing the insertion of this
250     // spanner's preceding sibling, and we obviously haven't got as far as processing this spanner
251     // yet.
252     return beforeChild;
253 }
254
255 static bool gShiftingSpanner = false;
256
257 void RenderTreeBuilder::MultiColumn::multiColumnDescendantInserted(RenderMultiColumnFlow& flow, RenderObject& newDescendant)
258 {
259     if (gShiftingSpanner || newDescendant.isInFlowRenderFragmentedFlow())
260         return;
261
262     auto* subtreeRoot = &newDescendant;
263     auto* descendant = subtreeRoot;
264     while (descendant) {
265         // Skip nested multicolumn flows.
266         if (is<RenderMultiColumnFlow>(*descendant)) {
267             descendant = descendant->nextSibling();
268             continue;
269         }
270         if (is<RenderMultiColumnSpannerPlaceholder>(*descendant)) {
271             // A spanner's placeholder has been inserted. The actual spanner renderer is moved from
272             // where it would otherwise occur (if it weren't a spanner) to becoming a sibling of the
273             // column sets.
274             RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*descendant);
275             ASSERT(!flow.spannerMap().get(placeholder.spanner()));
276             flow.spannerMap().add(placeholder.spanner(), makeWeakPtr(downcast<RenderMultiColumnSpannerPlaceholder>(descendant)));
277             ASSERT(!placeholder.firstChild()); // There should be no children here, but if there are, we ought to skip them.
278         } else
279             descendant = processPossibleSpannerDescendant(flow, subtreeRoot, *descendant);
280         if (descendant)
281             descendant = descendant->nextInPreOrder(subtreeRoot);
282     }
283 }
284
285 RenderObject* RenderTreeBuilder::MultiColumn::processPossibleSpannerDescendant(RenderMultiColumnFlow& flow, RenderObject*& subtreeRoot, RenderObject& descendant)
286 {
287     RenderBlockFlow* multicolContainer = flow.multiColumnBlockFlow();
288     RenderObject* nextRendererInFragmentedFlow = spannerPlacehoderCandidate(descendant, flow);
289     RenderObject* insertBeforeMulticolChild = nullptr;
290     RenderObject* nextDescendant = &descendant;
291
292     if (isValidColumnSpanner(flow, descendant)) {
293         // This is a spanner (column-span:all). Such renderers are moved from where they would
294         // otherwise occur in the render tree to becoming a direct child of the multicol container,
295         // so that they live among the column sets. This simplifies the layout implementation, and
296         // basically just relies on regular block layout done by the RenderBlockFlow that
297         // establishes the multicol container.
298         RenderBlockFlow* container = downcast<RenderBlockFlow>(descendant.parent());
299         RenderMultiColumnSet* setToSplit = nullptr;
300         if (nextRendererInFragmentedFlow) {
301             setToSplit = findSetRendering(flow, descendant);
302             if (setToSplit) {
303                 setToSplit->setNeedsLayout();
304                 insertBeforeMulticolChild = setToSplit->nextSibling();
305             }
306         }
307         // Moving a spanner's renderer so that it becomes a sibling of the column sets requires us
308         // to insert an anonymous placeholder in the tree where the spanner's renderer otherwise
309         // would have been. This is needed for a two reasons: We need a way of separating inline
310         // content before and after the spanner, so that it becomes separate line boxes. Secondly,
311         // this placeholder serves as a break point for column sets, so that, when encountered, we
312         // end flowing one column set and move to the next one.
313         auto newPlaceholder = RenderMultiColumnSpannerPlaceholder::createAnonymous(flow, downcast<RenderBox>(descendant), container->style());
314         auto& placeholder = *newPlaceholder;
315         m_builder.insertChild(*container, WTFMove(newPlaceholder), descendant.nextSibling());
316         auto takenDescendant = m_builder.takeChild(*container, descendant);
317
318         // This is a guard to stop an ancestor flow thread from processing the spanner.
319         gShiftingSpanner = true;
320         m_builder.insertChildToRenderBlock(*multicolContainer, WTFMove(takenDescendant), insertBeforeMulticolChild);
321         gShiftingSpanner = false;
322
323         // The spanner has now been moved out from the flow thread, but we don't want to
324         // examine its children anyway. They are all part of the spanner and shouldn't trigger
325         // creation of column sets or anything like that. Continue at its original position in
326         // the tree, i.e. where the placeholder was just put.
327         if (subtreeRoot == &descendant)
328             subtreeRoot = &placeholder;
329         nextDescendant = &placeholder;
330     } else {
331         // This is regular multicol content, i.e. not part of a spanner.
332         if (is<RenderMultiColumnSpannerPlaceholder>(nextRendererInFragmentedFlow)) {
333             // Inserted right before a spanner. Is there a set for us there?
334             RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*nextRendererInFragmentedFlow);
335             if (RenderObject* previous = placeholder.spanner()->previousSibling()) {
336                 if (is<RenderMultiColumnSet>(*previous))
337                     return nextDescendant; // There's already a set there. Nothing to do.
338             }
339             insertBeforeMulticolChild = placeholder.spanner();
340         } else if (RenderMultiColumnSet* lastSet = flow.lastMultiColumnSet()) {
341             // This child is not an immediate predecessor of a spanner, which means that if this
342             // child precedes a spanner at all, there has to be a column set created for us there
343             // already. If it doesn't precede any spanner at all, on the other hand, we need a
344             // column set at the end of the multicol container. We don't really check here if the
345             // child inserted precedes any spanner or not (as that's an expensive operation). Just
346             // make sure we have a column set at the end. It's no big deal if it remains unused.
347             if (!lastSet->nextSibling())
348                 return nextDescendant;
349         }
350     }
351     // Need to create a new column set when there's no set already created. We also always insert
352     // another column set after a spanner. Even if it turns out that there are no renderers
353     // following the spanner, there may be bottom margins there, which take up space.
354     auto newSet = flow.createMultiColumnSet(RenderStyle::createAnonymousStyleWithDisplay(multicolContainer->style(), BLOCK));
355     newSet->initializeStyle();
356     auto& set = *newSet;
357     m_builder.insertChildToRenderBlock(*multicolContainer, WTFMove(newSet), insertBeforeMulticolChild);
358     flow.invalidateFragments();
359
360     // We cannot handle immediate column set siblings at the moment (and there's no need for
361     // it, either). There has to be at least one spanner separating them.
362     ASSERT_UNUSED(set, !RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(&set)
363         || !RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet());
364     ASSERT(!RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(&set)
365         || !RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet());
366
367     return nextDescendant;
368 }
369
370 void RenderTreeBuilder::MultiColumn::handleSpannerRemoval(RenderMultiColumnFlow& flow, RenderObject& spanner)
371 {
372     // The placeholder may already have been removed, but if it hasn't, do so now.
373     if (auto placeholder = flow.spannerMap().take(&downcast<RenderBox>(spanner)))
374         placeholder->removeFromParentAndDestroy(m_builder);
375
376     if (auto* next = spanner.nextSibling()) {
377         if (auto* previous = spanner.previousSibling()) {
378             if (previous->isRenderMultiColumnSet() && next->isRenderMultiColumnSet()) {
379                 // Merge two sets that no longer will be separated by a spanner.
380                 next->removeFromParentAndDestroy(m_builder);
381                 previous->setNeedsLayout();
382             }
383         }
384     }
385 }
386
387 void RenderTreeBuilder::MultiColumn::multiColumnRelativeWillBeRemoved(RenderMultiColumnFlow& flow, RenderObject& relative)
388 {
389     flow.invalidateFragments();
390     if (is<RenderMultiColumnSpannerPlaceholder>(relative)) {
391         // Remove the map entry for this spanner, but leave the actual spanner renderer alone. Also
392         // keep the reference to the spanner, since the placeholder may be about to be re-inserted
393         // in the tree.
394         ASSERT(relative.isDescendantOf(&flow));
395         flow.spannerMap().remove(downcast<RenderMultiColumnSpannerPlaceholder>(relative).spanner());
396         return;
397     }
398     if (relative.style().columnSpan() == ColumnSpanAll) {
399         if (relative.parent() != flow.parent())
400             return; // not a valid spanner.
401
402         handleSpannerRemoval(flow, relative);
403     }
404     // Note that we might end up with empty column sets if all column content is removed. That's no
405     // big deal though (and locating them would be expensive), and they will be found and re-used if
406     // content is added again later.
407 }
408
409 }