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 "RenderMultiColumnFlow.h"
30#include "RenderMultiColumnSet.h"
31#include "RenderMultiColumnSpannerPlaceholder.h"
32#include "RenderTreeBuilder.h"
33#include "RenderTreeBuilderBlock.h"
34
35namespace WebCore {
36
37static 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
47static 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
71static 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 (descendantBox.style().columnSpan() != ColumnSpan::All)
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() != ColumnSpan::All || !isValidColumnSpanner(fragmentedFlow, *ancestor));
111 if (ancestor->isUnsplittableForPagination())
112 return false;
113 }
114 ASSERT_NOT_REACHED();
115 return false;
116}
117
118RenderTreeBuilder::MultiColumn::MultiColumn(RenderTreeBuilder& builder)
119 : m_builder(builder)
120{
121}
122
123void 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
138void 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.detach(*spanner->parent(), *spanner);
164 m_builder.attach(spannerOriginalParent, WTFMove(spannerToReInsert));
165 }
166 }
167
168 auto newFragmentedFlow = WebCore::createRenderer<RenderMultiColumnFlow>(flow.document(), RenderStyle::createAnonymousStyleWithDisplay(flow.style(), DisplayType::Block));
169 newFragmentedFlow->initializeStyle();
170 auto& fragmentedFlow = *newFragmentedFlow;
171 m_builder.blockBuilder().attach(flow, WTFMove(newFragmentedFlow), nullptr);
172
173 // Reparent children preceding the fragmented flow into the fragmented flow.
174 m_builder.moveChildren(flow, fragmentedFlow, flow.firstChild(), &fragmentedFlow, RenderTreeBuilder::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 m_builder.move(fragmentedFlow, flow, box, RenderTreeBuilder::NormalizeAfterInsertion::Yes);
180 }
181 }
182
183 flow.setMultiColumnFlow(fragmentedFlow);
184}
185
186void RenderTreeBuilder::MultiColumn::destroyFragmentedFlow(RenderBlockFlow& flow)
187{
188 auto& multiColumnFlow = *flow.multiColumnFlow();
189 multiColumnFlow.deleteLines();
190
191 // Move spanners back to their original DOM position in the tree, and destroy the placeholders.
192 auto& spanners = multiColumnFlow.spannerMap();
193 Vector<RenderMultiColumnSpannerPlaceholder*> placeholdersToDelete;
194 for (auto& spannerAndPlaceholder : spanners)
195 placeholdersToDelete.append(spannerAndPlaceholder.value.get());
196 Vector<std::pair<RenderElement*, RenderPtr<RenderObject>>> parentAndSpannerList;
197 for (auto* placeholder : placeholdersToDelete) {
198 auto* spannerOriginalParent = placeholder->parent();
199 if (spannerOriginalParent == &multiColumnFlow)
200 spannerOriginalParent = &flow;
201 // Detaching the spanner takes care of removing the placeholder (and merges the RenderMultiColumnSets).
202 auto* spanner = placeholder->spanner();
203 parentAndSpannerList.append(std::make_pair(spannerOriginalParent, m_builder.detach(*spanner->parent(), *spanner)));
204 }
205 while (auto* columnSet = multiColumnFlow.firstMultiColumnSet())
206 m_builder.destroy(*columnSet);
207
208 flow.clearMultiColumnFlow();
209 m_builder.moveAllChildren(multiColumnFlow, flow, RenderTreeBuilder::NormalizeAfterInsertion::Yes);
210 m_builder.destroy(multiColumnFlow);
211 for (auto& parentAndSpanner : parentAndSpannerList)
212 m_builder.attach(*parentAndSpanner.first, WTFMove(parentAndSpanner.second));
213}
214
215
216RenderObject* RenderTreeBuilder::MultiColumn::resolveMovedChild(RenderFragmentedFlow& enclosingFragmentedFlow, RenderObject* beforeChild)
217{
218 if (!beforeChild)
219 return nullptr;
220
221 if (!is<RenderBox>(*beforeChild))
222 return beforeChild;
223
224 if (!is<RenderMultiColumnFlow>(enclosingFragmentedFlow))
225 return beforeChild;
226
227 // We only need to resolve for column spanners.
228 if (beforeChild->style().columnSpan() != ColumnSpan::All)
229 return beforeChild;
230
231 // The renderer for the actual DOM node that establishes a spanner is moved from its original
232 // location in the render tree to becoming a sibling of the column sets. In other words, it's
233 // moved out from the flow thread (and becomes a sibling of it). When we for instance want to
234 // create and insert a renderer for the sibling node immediately preceding the spanner, we need
235 // to map that spanner renderer to the spanner's placeholder, which is where the new inserted
236 // renderer belongs.
237 if (auto* placeholder = downcast<RenderMultiColumnFlow>(enclosingFragmentedFlow).findColumnSpannerPlaceholder(downcast<RenderBox>(beforeChild)))
238 return placeholder;
239
240 // This is an invalid spanner, or its placeholder hasn't been created yet. This happens when
241 // moving an entire subtree into the flow thread, when we are processing the insertion of this
242 // spanner's preceding sibling, and we obviously haven't got as far as processing this spanner
243 // yet.
244 return beforeChild;
245}
246
247static bool gShiftingSpanner = false;
248
249void RenderTreeBuilder::MultiColumn::multiColumnDescendantInserted(RenderMultiColumnFlow& flow, RenderObject& newDescendant)
250{
251 if (gShiftingSpanner || newDescendant.isInFlowRenderFragmentedFlow())
252 return;
253
254 auto* subtreeRoot = &newDescendant;
255 auto* descendant = subtreeRoot;
256 while (descendant) {
257 // Skip nested multicolumn flows.
258 if (is<RenderMultiColumnFlow>(*descendant)) {
259 descendant = descendant->nextSibling();
260 continue;
261 }
262 if (is<RenderMultiColumnSpannerPlaceholder>(*descendant)) {
263 // A spanner's placeholder has been inserted. The actual spanner renderer is moved from
264 // where it would otherwise occur (if it weren't a spanner) to becoming a sibling of the
265 // column sets.
266 RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*descendant);
267 ASSERT(!flow.spannerMap().get(placeholder.spanner()));
268 flow.spannerMap().add(placeholder.spanner(), makeWeakPtr(downcast<RenderMultiColumnSpannerPlaceholder>(descendant)));
269 ASSERT(!placeholder.firstChild()); // There should be no children here, but if there are, we ought to skip them.
270 } else
271 descendant = processPossibleSpannerDescendant(flow, subtreeRoot, *descendant);
272 if (descendant)
273 descendant = descendant->nextInPreOrder(subtreeRoot);
274 }
275}
276
277RenderObject* RenderTreeBuilder::MultiColumn::processPossibleSpannerDescendant(RenderMultiColumnFlow& flow, RenderObject*& subtreeRoot, RenderObject& descendant)
278{
279 RenderBlockFlow* multicolContainer = flow.multiColumnBlockFlow();
280 RenderObject* nextRendererInFragmentedFlow = spannerPlacehoderCandidate(descendant, flow);
281 RenderObject* insertBeforeMulticolChild = nullptr;
282 RenderObject* nextDescendant = &descendant;
283
284 if (isValidColumnSpanner(flow, descendant)) {
285 // This is a spanner (column-span:all). Such renderers are moved from where they would
286 // otherwise occur in the render tree to becoming a direct child of the multicol container,
287 // so that they live among the column sets. This simplifies the layout implementation, and
288 // basically just relies on regular block layout done by the RenderBlockFlow that
289 // establishes the multicol container.
290 RenderBlockFlow* container = downcast<RenderBlockFlow>(descendant.parent());
291 RenderMultiColumnSet* setToSplit = nullptr;
292 if (nextRendererInFragmentedFlow) {
293 setToSplit = findSetRendering(flow, descendant);
294 if (setToSplit) {
295 setToSplit->setNeedsLayout();
296 insertBeforeMulticolChild = setToSplit->nextSibling();
297 }
298 }
299 // Moving a spanner's renderer so that it becomes a sibling of the column sets requires us
300 // to insert an anonymous placeholder in the tree where the spanner's renderer otherwise
301 // would have been. This is needed for a two reasons: We need a way of separating inline
302 // content before and after the spanner, so that it becomes separate line boxes. Secondly,
303 // this placeholder serves as a break point for column sets, so that, when encountered, we
304 // end flowing one column set and move to the next one.
305 auto newPlaceholder = RenderMultiColumnSpannerPlaceholder::createAnonymous(flow, downcast<RenderBox>(descendant), container->style());
306 auto& placeholder = *newPlaceholder;
307 m_builder.attach(*container, WTFMove(newPlaceholder), descendant.nextSibling());
308 auto takenDescendant = m_builder.detach(*container, descendant);
309
310 // This is a guard to stop an ancestor flow thread from processing the spanner.
311 gShiftingSpanner = true;
312 m_builder.blockBuilder().attach(*multicolContainer, WTFMove(takenDescendant), insertBeforeMulticolChild);
313 gShiftingSpanner = false;
314
315 // The spanner has now been moved out from the flow thread, but we don't want to
316 // examine its children anyway. They are all part of the spanner and shouldn't trigger
317 // creation of column sets or anything like that. Continue at its original position in
318 // the tree, i.e. where the placeholder was just put.
319 if (subtreeRoot == &descendant)
320 subtreeRoot = &placeholder;
321 nextDescendant = &placeholder;
322 } else {
323 // This is regular multicol content, i.e. not part of a spanner.
324 if (is<RenderMultiColumnSpannerPlaceholder>(nextRendererInFragmentedFlow)) {
325 // Inserted right before a spanner. Is there a set for us there?
326 RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*nextRendererInFragmentedFlow);
327 if (RenderObject* previous = placeholder.spanner()->previousSibling()) {
328 if (is<RenderMultiColumnSet>(*previous))
329 return nextDescendant; // There's already a set there. Nothing to do.
330 }
331 insertBeforeMulticolChild = placeholder.spanner();
332 } else if (RenderMultiColumnSet* lastSet = flow.lastMultiColumnSet()) {
333 // This child is not an immediate predecessor of a spanner, which means that if this
334 // child precedes a spanner at all, there has to be a column set created for us there
335 // already. If it doesn't precede any spanner at all, on the other hand, we need a
336 // column set at the end of the multicol container. We don't really check here if the
337 // child inserted precedes any spanner or not (as that's an expensive operation). Just
338 // make sure we have a column set at the end. It's no big deal if it remains unused.
339 if (!lastSet->nextSibling())
340 return nextDescendant;
341 }
342 }
343 // Need to create a new column set when there's no set already created. We also always insert
344 // another column set after a spanner. Even if it turns out that there are no renderers
345 // following the spanner, there may be bottom margins there, which take up space.
346 auto newSet = createRenderer<RenderMultiColumnSet>(flow, RenderStyle::createAnonymousStyleWithDisplay(multicolContainer->style(), DisplayType::Block));
347 newSet->initializeStyle();
348 auto& set = *newSet;
349 m_builder.blockBuilder().attach(*multicolContainer, WTFMove(newSet), insertBeforeMulticolChild);
350 flow.invalidateFragments();
351
352 // We cannot handle immediate column set siblings at the moment (and there's no need for
353 // it, either). There has to be at least one spanner separating them.
354 ASSERT_UNUSED(set, !RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(&set)
355 || !RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet());
356 ASSERT(!RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(&set)
357 || !RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet());
358
359 return nextDescendant;
360}
361
362void RenderTreeBuilder::MultiColumn::handleSpannerRemoval(RenderMultiColumnFlow& flow, RenderObject& spanner)
363{
364 // The placeholder may already have been removed, but if it hasn't, do so now.
365 if (auto placeholder = flow.spannerMap().take(&downcast<RenderBox>(spanner)))
366 m_builder.destroy(*placeholder);
367
368 if (auto* next = spanner.nextSibling()) {
369 if (auto* previous = spanner.previousSibling()) {
370 if (previous->isRenderMultiColumnSet() && next->isRenderMultiColumnSet()) {
371 // Merge two sets that no longer will be separated by a spanner.
372 m_builder.destroy(*next);
373 previous->setNeedsLayout();
374 }
375 }
376 }
377}
378
379void RenderTreeBuilder::MultiColumn::multiColumnRelativeWillBeRemoved(RenderMultiColumnFlow& flow, RenderObject& relative)
380{
381 flow.invalidateFragments();
382 if (is<RenderMultiColumnSpannerPlaceholder>(relative)) {
383 // Remove the map entry for this spanner, but leave the actual spanner renderer alone. Also
384 // keep the reference to the spanner, since the placeholder may be about to be re-inserted
385 // in the tree.
386 ASSERT(relative.isDescendantOf(&flow));
387 flow.spannerMap().remove(downcast<RenderMultiColumnSpannerPlaceholder>(relative).spanner());
388 return;
389 }
390 if (relative.style().columnSpan() == ColumnSpan::All) {
391 if (relative.parent() != flow.parent())
392 return; // not a valid spanner.
393
394 handleSpannerRemoval(flow, relative);
395 }
396 // Note that we might end up with empty column sets if all column content is removed. That's no
397 // big deal though (and locating them would be expensive), and they will be found and re-used if
398 // content is added again later.
399}
400
401RenderObject* RenderTreeBuilder::MultiColumn::adjustBeforeChildForMultiColumnSpannerIfNeeded(RenderObject& beforeChild)
402{
403 if (!is<RenderBox>(beforeChild))
404 return &beforeChild;
405
406 auto* nextSibling = beforeChild.nextSibling();
407 if (!nextSibling)
408 return &beforeChild;
409
410 if (!is<RenderMultiColumnSet>(*nextSibling))
411 return &beforeChild;
412
413 auto* multiColumnFlow = downcast<RenderMultiColumnSet>(*nextSibling).multiColumnFlow();
414 if (!multiColumnFlow)
415 return &beforeChild;
416
417 return multiColumnFlow->findColumnSpannerPlaceholder(downcast<RenderBox>(&beforeChild));
418}
419
420}
421