1 /*
2 * Copyright (C) 2012 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. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS IN..0TERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26 #include "third_party/blink/renderer/core/layout/layout_multi_column_flow_thread.h"
27
28 #include "third_party/blink/renderer/core/layout/layout_multi_column_set.h"
29 #include "third_party/blink/renderer/core/layout/layout_multi_column_spanner_placeholder.h"
30 #include "third_party/blink/renderer/core/layout/layout_view.h"
31 #include "third_party/blink/renderer/core/layout/multi_column_fragmentainer_group.h"
32 #include "third_party/blink/renderer/core/layout/view_fragmentation_context.h"
33
34 namespace blink {
35
36 #if DCHECK_IS_ON()
37 const LayoutBox* LayoutMultiColumnFlowThread::style_changed_box_;
38 #endif
39 bool LayoutMultiColumnFlowThread::could_contain_spanners_;
40 bool LayoutMultiColumnFlowThread::toggle_spanners_if_needed_;
41
LayoutMultiColumnFlowThread()42 LayoutMultiColumnFlowThread::LayoutMultiColumnFlowThread()
43 : last_set_worked_on_(nullptr),
44 column_count_(1),
45 column_heights_changed_(false),
46 is_being_evacuated_(false) {
47 SetIsInsideFlowThread(true);
48 }
49
50 LayoutMultiColumnFlowThread::~LayoutMultiColumnFlowThread() = default;
51
CreateAnonymous(Document & document,const ComputedStyle & parent_style)52 LayoutMultiColumnFlowThread* LayoutMultiColumnFlowThread::CreateAnonymous(
53 Document& document,
54 const ComputedStyle& parent_style) {
55 LayoutMultiColumnFlowThread* layout_object =
56 new LayoutMultiColumnFlowThread();
57 layout_object->SetDocumentForAnonymous(&document);
58 layout_object->SetStyle(ComputedStyle::CreateAnonymousStyleWithDisplay(
59 parent_style, EDisplay::kBlock));
60 return layout_object;
61 }
62
FirstMultiColumnSet() const63 LayoutMultiColumnSet* LayoutMultiColumnFlowThread::FirstMultiColumnSet() const {
64 for (LayoutObject* sibling = NextSibling(); sibling;
65 sibling = sibling->NextSibling()) {
66 if (sibling->IsLayoutMultiColumnSet())
67 return ToLayoutMultiColumnSet(sibling);
68 }
69 return nullptr;
70 }
71
LastMultiColumnSet() const72 LayoutMultiColumnSet* LayoutMultiColumnFlowThread::LastMultiColumnSet() const {
73 for (LayoutObject* sibling = MultiColumnBlockFlow()->LastChild(); sibling;
74 sibling = sibling->PreviousSibling()) {
75 if (sibling->IsLayoutMultiColumnSet())
76 return ToLayoutMultiColumnSet(sibling);
77 }
78 return nullptr;
79 }
80
IsMultiColumnContainer(const LayoutObject & object)81 static inline bool IsMultiColumnContainer(const LayoutObject& object) {
82 auto* block_flow = DynamicTo<LayoutBlockFlow>(object);
83 if (!block_flow)
84 return false;
85 return block_flow->MultiColumnFlowThread();
86 }
87
88 // Return true if there's nothing that prevents the specified object from being
89 // in the ancestor chain between some column spanner and its containing multicol
90 // container. A column spanner needs the multicol container to be its containing
91 // block, so that the spanner is able to escape the flow thread. (Everything
92 // contained by the flow thread is split into columns, but this is precisely
93 // what shouldn't be done to a spanner, since it's supposed to span all
94 // columns.)
95 //
96 // We require that the parent of the spanner participate in the block formatting
97 // context established by the multicol container (i.e. that there are no BFCs or
98 // other formatting contexts in-between). We also require that there be no
99 // transforms, since transforms insist on being in the containing block chain
100 // for everything inside it, which conflicts with a spanners's need to have the
101 // multicol container as its direct containing block. We may also not put
102 // spanners inside objects that don't support fragmentation.
CanContainSpannerInParentFragmentationContext(const LayoutObject & object)103 static inline bool CanContainSpannerInParentFragmentationContext(
104 const LayoutObject& object) {
105 const auto* block_flow = DynamicTo<LayoutBlockFlow>(object);
106 if (!block_flow)
107 return false;
108 return !block_flow->CreatesNewFormattingContext() &&
109 !block_flow->StyleRef().CanContainFixedPositionObjects(false) &&
110 block_flow->GetPaginationBreakability() != LayoutBox::kForbidBreaks &&
111 !IsMultiColumnContainer(*block_flow);
112 }
113
HasAnyColumnSpanners(const LayoutMultiColumnFlowThread & flow_thread)114 static inline bool HasAnyColumnSpanners(
115 const LayoutMultiColumnFlowThread& flow_thread) {
116 LayoutBox* first_box = flow_thread.FirstMultiColumnBox();
117 return first_box && (first_box != flow_thread.LastMultiColumnBox() ||
118 first_box->IsLayoutMultiColumnSpannerPlaceholder());
119 }
120
121 // Find the next layout object that has the multicol container in its containing
122 // block chain, skipping nested multicol containers.
NextInPreOrderAfterChildrenSkippingOutOfFlow(LayoutMultiColumnFlowThread * flow_thread,LayoutObject * descendant)123 static LayoutObject* NextInPreOrderAfterChildrenSkippingOutOfFlow(
124 LayoutMultiColumnFlowThread* flow_thread,
125 LayoutObject* descendant) {
126 DCHECK(descendant->IsDescendantOf(flow_thread));
127 LayoutObject* object = descendant->NextInPreOrderAfterChildren(flow_thread);
128 while (object) {
129 // Walk through the siblings and find the first one which is either in-flow
130 // or has this flow thread as its containing block flow thread.
131 if (!object->IsOutOfFlowPositioned())
132 break;
133 if (object->ContainingBlock()->FlowThreadContainingBlock() == flow_thread) {
134 // This out-of-flow object is still part of the flow thread, because its
135 // containing block (probably relatively positioned) is part of the flow
136 // thread.
137 break;
138 }
139 object = object->NextInPreOrderAfterChildren(flow_thread);
140 }
141 if (!object)
142 return nullptr;
143 #if DCHECK_IS_ON()
144 // Make sure that we didn't stumble into an inner multicol container.
145 for (LayoutObject* walker = object->Parent(); walker && walker != flow_thread;
146 walker = walker->Parent())
147 DCHECK(!IsMultiColumnContainer(*walker));
148 #endif
149 return object;
150 }
151
152 // Find the previous layout object that has the multicol container in its
153 // containing block chain, skipping nested multicol containers.
PreviousInPreOrderSkippingOutOfFlow(LayoutMultiColumnFlowThread * flow_thread,LayoutObject * descendant)154 static LayoutObject* PreviousInPreOrderSkippingOutOfFlow(
155 LayoutMultiColumnFlowThread* flow_thread,
156 LayoutObject* descendant) {
157 DCHECK(descendant->IsDescendantOf(flow_thread));
158 LayoutObject* object = descendant->PreviousInPreOrder(flow_thread);
159 while (object && object != flow_thread) {
160 if (object->IsColumnSpanAll()) {
161 LayoutMultiColumnFlowThread* placeholder_flow_thread =
162 ToLayoutBox(object)->SpannerPlaceholder()->FlowThread();
163 if (placeholder_flow_thread == flow_thread)
164 break;
165 // We're inside an inner multicol container. We have no business there.
166 // Continue on the outside.
167 object = placeholder_flow_thread->Parent();
168 DCHECK(object->IsDescendantOf(flow_thread));
169 continue;
170 }
171 if (object->FlowThreadContainingBlock() == flow_thread) {
172 LayoutObject* ancestor;
173 for (ancestor = object->Parent();; ancestor = ancestor->Parent()) {
174 if (ancestor == flow_thread)
175 return object;
176 if (IsMultiColumnContainer(*ancestor)) {
177 // We're inside an inner multicol container. We have no business
178 // there.
179 break;
180 }
181 }
182 object = ancestor;
183 DCHECK(ancestor->IsDescendantOf(flow_thread));
184 continue; // Continue on the outside of the inner flow thread.
185 }
186 // We're inside something that's out-of-flow. Keep looking upwards and
187 // backwards in the tree.
188 object = object->PreviousInPreOrder(flow_thread);
189 }
190 if (!object || object == flow_thread)
191 return nullptr;
192 #if DCHECK_IS_ON()
193 // Make sure that we didn't stumble into an inner multicol container.
194 for (LayoutObject* walker = object->Parent(); walker && walker != flow_thread;
195 walker = walker->Parent())
196 DCHECK(!IsMultiColumnContainer(*walker));
197 #endif
198 return object;
199 }
200
FirstLayoutObjectInSet(LayoutMultiColumnSet * multicol_set)201 static LayoutObject* FirstLayoutObjectInSet(
202 LayoutMultiColumnSet* multicol_set) {
203 LayoutBox* sibling = multicol_set->PreviousSiblingMultiColumnBox();
204 if (!sibling)
205 return multicol_set->FlowThread()->FirstChild();
206 // Adjacent column content sets should not occur. We would have no way of
207 // figuring out what each of them contains then.
208 DCHECK(sibling->IsLayoutMultiColumnSpannerPlaceholder());
209 LayoutBox* spanner = ToLayoutMultiColumnSpannerPlaceholder(sibling)
210 ->LayoutObjectInFlowThread();
211 return NextInPreOrderAfterChildrenSkippingOutOfFlow(
212 multicol_set->MultiColumnFlowThread(), spanner);
213 }
214
LastLayoutObjectInSet(LayoutMultiColumnSet * multicol_set)215 static LayoutObject* LastLayoutObjectInSet(LayoutMultiColumnSet* multicol_set) {
216 LayoutBox* sibling = multicol_set->NextSiblingMultiColumnBox();
217 // By right we should return lastLeafChild() here, but the caller doesn't
218 // care, so just return nullptr.
219 if (!sibling)
220 return nullptr;
221 // Adjacent column content sets should not occur. We would have no way of
222 // figuring out what each of them contains then.
223 DCHECK(sibling->IsLayoutMultiColumnSpannerPlaceholder());
224 LayoutBox* spanner = ToLayoutMultiColumnSpannerPlaceholder(sibling)
225 ->LayoutObjectInFlowThread();
226 return PreviousInPreOrderSkippingOutOfFlow(
227 multicol_set->MultiColumnFlowThread(), spanner);
228 }
229
MapDescendantToColumnSet(LayoutObject * layout_object) const230 LayoutMultiColumnSet* LayoutMultiColumnFlowThread::MapDescendantToColumnSet(
231 LayoutObject* layout_object) const {
232 // Should not be used for spanners or content inside them.
233 DCHECK(!ContainingColumnSpannerPlaceholder(layout_object));
234 DCHECK_NE(layout_object, this);
235 DCHECK(layout_object->IsDescendantOf(this));
236 // Out-of-flow objects don't belong in column sets.
237 DCHECK(layout_object->ContainingBlock()->IsDescendantOf(this));
238 DCHECK_EQ(layout_object->FlowThreadContainingBlock(), this);
239 DCHECK(!layout_object->IsLayoutMultiColumnSet());
240 DCHECK(!layout_object->IsLayoutMultiColumnSpannerPlaceholder());
241 LayoutMultiColumnSet* multicol_set = FirstMultiColumnSet();
242 if (!multicol_set)
243 return nullptr;
244 if (!multicol_set->NextSiblingMultiColumnSet())
245 return multicol_set;
246
247 // This is potentially SLOW! But luckily very uncommon. You would have to
248 // dynamically insert a spanner into the middle of column contents to need
249 // this.
250 for (; multicol_set;
251 multicol_set = multicol_set->NextSiblingMultiColumnSet()) {
252 LayoutObject* first_layout_object = FirstLayoutObjectInSet(multicol_set);
253 LayoutObject* last_layout_object = LastLayoutObjectInSet(multicol_set);
254 DCHECK(first_layout_object);
255
256 for (LayoutObject* walker = first_layout_object; walker;
257 walker = walker->NextInPreOrder(this)) {
258 if (walker == layout_object)
259 return multicol_set;
260 if (walker == last_layout_object)
261 break;
262 }
263 }
264
265 return nullptr;
266 }
267
268 LayoutMultiColumnSpannerPlaceholder*
ContainingColumnSpannerPlaceholder(const LayoutObject * descendant) const269 LayoutMultiColumnFlowThread::ContainingColumnSpannerPlaceholder(
270 const LayoutObject* descendant) const {
271 DCHECK(descendant->IsDescendantOf(this));
272
273 if (!HasAnyColumnSpanners(*this))
274 return nullptr;
275
276 // We have spanners. See if the layoutObject in question is one or inside of
277 // one then.
278 for (const LayoutObject* ancestor = descendant; ancestor && ancestor != this;
279 ancestor = ancestor->Parent()) {
280 if (LayoutMultiColumnSpannerPlaceholder* placeholder =
281 ancestor->SpannerPlaceholder())
282 return placeholder;
283 }
284 return nullptr;
285 }
286
Populate()287 void LayoutMultiColumnFlowThread::Populate() {
288 LayoutBlockFlow* multicol_container = MultiColumnBlockFlow();
289 DCHECK(!NextSibling());
290 // Reparent children preceding the flow thread into the flow thread. It's
291 // multicol content now. At this point there's obviously nothing after the
292 // flow thread, but layoutObjects (column sets and spanners) will be inserted
293 // there as we insert elements into the flow thread.
294 multicol_container->RemoveFloatingObjectsFromDescendants();
295 multicol_container->MoveChildrenTo(this, multicol_container->FirstChild(),
296 this, true);
297 }
298
EvacuateAndDestroy()299 void LayoutMultiColumnFlowThread::EvacuateAndDestroy() {
300 LayoutBlockFlow* multicol_container = MultiColumnBlockFlow();
301 is_being_evacuated_ = true;
302
303 // Remove all sets and spanners.
304 while (LayoutBox* column_box = FirstMultiColumnBox()) {
305 DCHECK(column_box->IsAnonymous());
306 column_box->Destroy();
307 }
308
309 DCHECK(!PreviousSibling());
310 DCHECK(!NextSibling());
311
312 // Finally we can promote all flow thread's children. Before we move them to
313 // the flow thread's container, we need to unregister the flow thread, so that
314 // they aren't just re-added again to the flow thread that we're trying to
315 // empty.
316 multicol_container->ResetMultiColumnFlowThread();
317 MoveAllChildrenIncludingFloatsTo(multicol_container, true);
318
319 // We used to manually nuke the line box tree here, but that should happen
320 // automatically when moving children around (the code above).
321 DCHECK(!FirstLineBox());
322
323 Destroy();
324 }
325
MaxColumnLogicalHeight() const326 LayoutUnit LayoutMultiColumnFlowThread::MaxColumnLogicalHeight() const {
327 if (column_height_available_) {
328 // If height is non-auto, it's already constrained against max-height as
329 // well. Just return it.
330 return column_height_available_;
331 }
332 const LayoutBlockFlow* multicol_block = MultiColumnBlockFlow();
333 const Length& logical_max_height =
334 multicol_block->StyleRef().LogicalMaxHeight();
335 if (!logical_max_height.IsNone()) {
336 LayoutUnit resolved_logical_max_height =
337 multicol_block->ComputeContentLogicalHeight(
338 kMaxSize, logical_max_height, LayoutUnit(-1));
339 if (resolved_logical_max_height != -1)
340 return resolved_logical_max_height;
341 }
342 return LayoutUnit::Max();
343 }
344
TallestUnbreakableLogicalHeight(LayoutUnit offset_in_flow_thread) const345 LayoutUnit LayoutMultiColumnFlowThread::TallestUnbreakableLogicalHeight(
346 LayoutUnit offset_in_flow_thread) const {
347 if (LayoutMultiColumnSet* multicol_set = ColumnSetAtBlockOffset(
348 offset_in_flow_thread, kAssociateWithLatterPage))
349 return multicol_set->TallestUnbreakableLogicalHeight();
350 return LayoutUnit();
351 }
352
ColumnOffset(const LayoutPoint & point) const353 LayoutSize LayoutMultiColumnFlowThread::ColumnOffset(
354 const LayoutPoint& point) const {
355 return FlowThreadTranslationAtPoint(point,
356 CoordinateSpaceConversion::kContaining);
357 }
358
NeedsNewWidth() const359 bool LayoutMultiColumnFlowThread::NeedsNewWidth() const {
360 LayoutUnit new_width;
361 unsigned dummy_column_count; // We only care if used column-width changes.
362 CalculateColumnCountAndWidth(new_width, dummy_column_count);
363 return new_width != LogicalWidth();
364 }
365
IsPageLogicalHeightKnown() const366 bool LayoutMultiColumnFlowThread::IsPageLogicalHeightKnown() const {
367 return all_columns_have_known_height_;
368 }
369
MayHaveNonUniformPageLogicalHeight() const370 bool LayoutMultiColumnFlowThread::MayHaveNonUniformPageLogicalHeight() const {
371 const LayoutMultiColumnSet* column_set = FirstMultiColumnSet();
372 if (!column_set)
373 return false;
374 if (column_set->NextSiblingMultiColumnSet())
375 return true;
376 return EnclosingFragmentationContext();
377 }
378
FlowThreadTranslationAtOffset(LayoutUnit offset_in_flow_thread,PageBoundaryRule rule,CoordinateSpaceConversion mode) const379 LayoutSize LayoutMultiColumnFlowThread::FlowThreadTranslationAtOffset(
380 LayoutUnit offset_in_flow_thread,
381 PageBoundaryRule rule,
382 CoordinateSpaceConversion mode) const {
383 if (!HasValidColumnSetInfo())
384 return LayoutSize(0, 0);
385 LayoutMultiColumnSet* column_set =
386 ColumnSetAtBlockOffset(offset_in_flow_thread, rule);
387 if (!column_set)
388 return LayoutSize(0, 0);
389 return column_set->FlowThreadTranslationAtOffset(offset_in_flow_thread, rule,
390 mode);
391 }
392
FlowThreadTranslationAtPoint(const LayoutPoint & flow_thread_point,CoordinateSpaceConversion mode) const393 LayoutSize LayoutMultiColumnFlowThread::FlowThreadTranslationAtPoint(
394 const LayoutPoint& flow_thread_point,
395 CoordinateSpaceConversion mode) const {
396 LayoutPoint flipped_point = DeprecatedFlipForWritingMode(flow_thread_point);
397 LayoutUnit block_offset =
398 IsHorizontalWritingMode() ? flipped_point.Y() : flipped_point.X();
399
400 // If block direction is flipped, points at a column boundary belong in the
401 // former column, not the latter.
402 PageBoundaryRule rule = HasFlippedBlocksWritingMode()
403 ? kAssociateWithFormerPage
404 : kAssociateWithLatterPage;
405
406 return FlowThreadTranslationAtOffset(block_offset, rule, mode);
407 }
408
FlowThreadPointToVisualPoint(const LayoutPoint & flow_thread_point) const409 LayoutPoint LayoutMultiColumnFlowThread::FlowThreadPointToVisualPoint(
410 const LayoutPoint& flow_thread_point) const {
411 return flow_thread_point +
412 FlowThreadTranslationAtPoint(flow_thread_point,
413 CoordinateSpaceConversion::kVisual);
414 }
415
VisualPointToFlowThreadPoint(const LayoutPoint & visual_point) const416 LayoutPoint LayoutMultiColumnFlowThread::VisualPointToFlowThreadPoint(
417 const LayoutPoint& visual_point) const {
418 LayoutUnit block_offset =
419 IsHorizontalWritingMode() ? visual_point.Y() : visual_point.X();
420 const LayoutMultiColumnSet* column_set = nullptr;
421 for (const LayoutMultiColumnSet* candidate = FirstMultiColumnSet(); candidate;
422 candidate = candidate->NextSiblingMultiColumnSet()) {
423 column_set = candidate;
424 if (candidate->LogicalBottom() > block_offset)
425 break;
426 }
427 return column_set ? column_set->VisualPointToFlowThreadPoint(ToLayoutPoint(
428 visual_point + Location() - column_set->Location()))
429 : visual_point;
430 }
431
InlineBlockBaseline(LineDirectionMode line_direction) const432 LayoutUnit LayoutMultiColumnFlowThread::InlineBlockBaseline(
433 LineDirectionMode line_direction) const {
434 LayoutUnit baseline_in_flow_thread =
435 LayoutFlowThread::InlineBlockBaseline(line_direction);
436 LayoutMultiColumnSet* column_set =
437 ColumnSetAtBlockOffset(baseline_in_flow_thread, kAssociateWithLatterPage);
438 if (!column_set)
439 return baseline_in_flow_thread;
440 return LayoutUnit(
441 (baseline_in_flow_thread -
442 column_set->PageLogicalTopForOffset(baseline_in_flow_thread))
443 .Ceil());
444 }
445
ColumnSetAtBlockOffset(LayoutUnit offset,PageBoundaryRule page_boundary_rule) const446 LayoutMultiColumnSet* LayoutMultiColumnFlowThread::ColumnSetAtBlockOffset(
447 LayoutUnit offset,
448 PageBoundaryRule page_boundary_rule) const {
449 LayoutMultiColumnSet* column_set = last_set_worked_on_;
450 if (column_set) {
451 // Layout in progress. We are calculating the set heights as we speak, so
452 // the column set range information is not up to date.
453 while (column_set->LogicalTopInFlowThread() > offset) {
454 // Sometimes we have to use a previous set. This happens when we're
455 // working with a block that contains a spanner (so that there's a column
456 // set both before and after the spanner, and both sets contain said
457 // block).
458 LayoutMultiColumnSet* previous_set =
459 column_set->PreviousSiblingMultiColumnSet();
460 if (!previous_set)
461 break;
462 column_set = previous_set;
463 }
464 } else {
465 DCHECK(!column_sets_invalidated_);
466 if (multi_column_set_list_.IsEmpty())
467 return nullptr;
468 if (offset < LayoutUnit()) {
469 column_set = multi_column_set_list_.front();
470 } else {
471 MultiColumnSetSearchAdapter adapter(offset);
472 multi_column_set_interval_tree_
473 .AllOverlapsWithAdapter<MultiColumnSetSearchAdapter>(adapter);
474
475 // If no set was found, the offset is in the flow thread overflow.
476 if (!adapter.Result() && !multi_column_set_list_.IsEmpty())
477 column_set = multi_column_set_list_.back();
478 else
479 column_set = adapter.Result();
480 }
481 }
482 if (page_boundary_rule == kAssociateWithFormerPage && column_set &&
483 offset == column_set->LogicalTopInFlowThread()) {
484 // The column set that we found starts at the exact same flow thread offset
485 // as we specified. Since we are to associate offsets at boundaries with the
486 // former fragmentainer, the fragmentainer we're looking for is in the
487 // previous column set.
488 if (LayoutMultiColumnSet* previous_set =
489 column_set->PreviousSiblingMultiColumnSet())
490 column_set = previous_set;
491 }
492 // Avoid returning zero-height column sets, if possible. We found a column set
493 // based on a flow thread coordinate. If multiple column sets share that
494 // coordinate (because we have zero-height column sets between column
495 // spanners, for instance), look for one that has a height. Also look ahead to
496 // find a set that actually contains the coordinate. Note that when we do this
497 // during layout, it means that we might return a column set that hasn't got
498 // its flow thread boundaries updated yet (and thus using those from the
499 // previous layout), but that's the best we can do when our engine doesn't
500 // actually understand fragmentation. This may happen when there's a float
501 // that's split into multiple fragments because of column spanners, and we
502 // still perform all its layout at the position before the first spanner in
503 // question (i.e. where only the first fragment is supposed to be laid out).
504 for (LayoutMultiColumnSet* walker = column_set; walker;
505 walker = walker->NextSiblingMultiColumnSet()) {
506 if (!walker->IsPageLogicalHeightKnown())
507 continue;
508 if (page_boundary_rule == kAssociateWithFormerPage) {
509 if (walker->LogicalTopInFlowThread() < offset &&
510 walker->LogicalBottomInFlowThread() >= offset)
511 return walker;
512 } else if (walker->LogicalTopInFlowThread() <= offset &&
513 walker->LogicalBottomInFlowThread() > offset) {
514 return walker;
515 }
516 }
517 return column_set;
518 }
519
LayoutColumns(SubtreeLayoutScope & layout_scope)520 void LayoutMultiColumnFlowThread::LayoutColumns(
521 SubtreeLayoutScope& layout_scope) {
522 // Since we ended up here, it means that the multicol container (our parent)
523 // needed layout. Since contents of the multicol container are diverted to the
524 // flow thread, the flow thread needs layout as well.
525 layout_scope.SetChildNeedsLayout(this);
526
527 CalculateColumnHeightAvailable();
528
529 if (FragmentationContext* enclosing_fragmentation_context =
530 EnclosingFragmentationContext()) {
531 block_offset_in_enclosing_fragmentation_context_ =
532 MultiColumnBlockFlow()->OffsetFromLogicalTopOfFirstPage();
533 block_offset_in_enclosing_fragmentation_context_ +=
534 MultiColumnBlockFlow()->BorderAndPaddingBefore();
535
536 if (LayoutMultiColumnFlowThread* enclosing_flow_thread =
537 enclosing_fragmentation_context->AssociatedFlowThread()) {
538 if (LayoutMultiColumnSet* first_set = FirstMultiColumnSet()) {
539 // Before we can start to lay out the contents of this multicol
540 // container, we need to make sure that all ancestor multicol containers
541 // have established a row to hold the first column contents of this
542 // container (this multicol container may start at the beginning of a
543 // new outer row). Without sufficient rows in all ancestor multicol
544 // containers, we may use the wrong column height.
545 LayoutUnit offset = block_offset_in_enclosing_fragmentation_context_ +
546 first_set->LogicalTopFromMulticolContentEdge();
547 enclosing_flow_thread->AppendNewFragmentainerGroupIfNeeded(
548 offset, kAssociateWithLatterPage);
549 }
550 }
551 }
552
553 // We'll start by assuming that all columns have some known height, and flip
554 // it to false if we discover that this isn't the case.
555 all_columns_have_known_height_ = true;
556
557 for (LayoutBox* column_box = FirstMultiColumnBox(); column_box;
558 column_box = column_box->NextSiblingMultiColumnBox()) {
559 if (!column_box->IsLayoutMultiColumnSet()) {
560 // No other type is expected.
561 DCHECK(column_box->IsLayoutMultiColumnSpannerPlaceholder());
562 continue;
563 }
564 LayoutMultiColumnSet* column_set = ToLayoutMultiColumnSet(column_box);
565 layout_scope.SetChildNeedsLayout(column_set);
566 if (!column_heights_changed_) {
567 // This is the initial layout pass. We need to reset the column height,
568 // because contents typically have changed.
569 column_set->ResetColumnHeight();
570 }
571 if (all_columns_have_known_height_ &&
572 !column_set->IsPageLogicalHeightKnown()) {
573 // If any of the column sets requires a layout pass before it has any
574 // clue about its height, we cannot fragment in this pass, just measure
575 // the block sizes.
576 all_columns_have_known_height_ = false;
577 }
578 // Since column sets are regular block flow objects, and their position is
579 // changed in regular block layout code (with no means for the multicol code
580 // to notice unless we add hooks there), store the previous position now. If
581 // it changes in the imminent layout pass, we may have to rebalance its
582 // columns.
583 column_set->StoreOldPosition();
584 }
585
586 column_heights_changed_ = false;
587 InvalidateColumnSets();
588 UpdateLayout();
589 ValidateColumnSets();
590 }
591
ColumnRuleStyleDidChange()592 void LayoutMultiColumnFlowThread::ColumnRuleStyleDidChange() {
593 for (LayoutMultiColumnSet* column_set = FirstMultiColumnSet(); column_set;
594 column_set = column_set->NextSiblingMultiColumnSet()) {
595 column_set->SetShouldDoFullPaintInvalidation(
596 PaintInvalidationReason::kStyle);
597 }
598 }
599
RemoveSpannerPlaceholderIfNoLongerValid(LayoutBox * spanner_object_in_flow_thread)600 bool LayoutMultiColumnFlowThread::RemoveSpannerPlaceholderIfNoLongerValid(
601 LayoutBox* spanner_object_in_flow_thread) {
602 DCHECK(spanner_object_in_flow_thread->SpannerPlaceholder());
603 if (DescendantIsValidColumnSpanner(spanner_object_in_flow_thread))
604 return false; // Still a valid spanner.
605
606 // No longer a valid spanner. Get rid of the placeholder.
607 DestroySpannerPlaceholder(
608 spanner_object_in_flow_thread->SpannerPlaceholder());
609 DCHECK(!spanner_object_in_flow_thread->SpannerPlaceholder());
610
611 // We may have a new containing block, since we're no longer a spanner. Mark
612 // it for relayout.
613 spanner_object_in_flow_thread->ContainingBlock()
614 ->SetNeedsLayoutAndIntrinsicWidthsRecalc(
615 layout_invalidation_reason::kColumnsChanged);
616
617 // Now generate a column set for this ex-spanner, if needed and none is there
618 // for us already.
619 FlowThreadDescendantWasInserted(spanner_object_in_flow_thread);
620
621 return true;
622 }
623
EnclosingFlowThread(AncestorSearchConstraint constraint) const624 LayoutMultiColumnFlowThread* LayoutMultiColumnFlowThread::EnclosingFlowThread(
625 AncestorSearchConstraint constraint) const {
626 if (!MultiColumnBlockFlow()->IsInsideFlowThread())
627 return nullptr;
628 return ToLayoutMultiColumnFlowThread(
629 LocateFlowThreadContainingBlockOf(*MultiColumnBlockFlow(), constraint));
630 }
631
632 FragmentationContext*
EnclosingFragmentationContext(AncestorSearchConstraint constraint) const633 LayoutMultiColumnFlowThread::EnclosingFragmentationContext(
634 AncestorSearchConstraint constraint) const {
635 // If this multicol container is strictly unbreakable (due to having
636 // scrollbars, for instance), it's also strictly unbreakable in any outer
637 // fragmentation context. As such, what kind of fragmentation that goes on
638 // inside this multicol container is completely opaque to the ancestors.
639 if (constraint == kIsolateUnbreakableContainers &&
640 MultiColumnBlockFlow()->GetPaginationBreakability() == kForbidBreaks)
641 return nullptr;
642 if (auto* enclosing_flow_thread = EnclosingFlowThread(constraint))
643 return enclosing_flow_thread;
644 return View()->FragmentationContext();
645 }
646
AppendNewFragmentainerGroupIfNeeded(LayoutUnit offset_in_flow_thread,PageBoundaryRule page_boundary_rule)647 void LayoutMultiColumnFlowThread::AppendNewFragmentainerGroupIfNeeded(
648 LayoutUnit offset_in_flow_thread,
649 PageBoundaryRule page_boundary_rule) {
650 LayoutMultiColumnSet* column_set =
651 ColumnSetAtBlockOffset(offset_in_flow_thread, page_boundary_rule);
652 if (!column_set->NewFragmentainerGroupsAllowed())
653 return;
654
655 if (column_set->NeedsNewFragmentainerGroupAt(offset_in_flow_thread,
656 page_boundary_rule)) {
657 // We should never create additional fragmentainer groups unless we're in a
658 // nested fragmentation context.
659 DCHECK(EnclosingFragmentationContext());
660
661 // We have run out of columns here, so we need to add at least one more row
662 // to hold more columns.
663 LayoutMultiColumnFlowThread* enclosing_flow_thread =
664 EnclosingFragmentationContext()->AssociatedFlowThread();
665 do {
666 if (enclosing_flow_thread) {
667 // When we add a new row here, it implicitly means that we're inserting
668 // another column in our enclosing multicol container. That in turn may
669 // mean that we've run out of columns there too. Need to insert
670 // additional rows in ancestral multicol containers before doing it in
671 // the descendants, in order to get the height constraints right down
672 // there.
673 const MultiColumnFragmentainerGroup& last_row =
674 column_set->LastFragmentainerGroup();
675 // The top offset where where the new fragmentainer group will start in
676 // this column set, converted to the coordinate space of the enclosing
677 // multicol container.
678 LayoutUnit logical_offset_in_outer =
679 last_row.BlockOffsetInEnclosingFragmentationContext() +
680 last_row.GroupLogicalHeight();
681 enclosing_flow_thread->AppendNewFragmentainerGroupIfNeeded(
682 logical_offset_in_outer, kAssociateWithLatterPage);
683 }
684
685 column_set->AppendNewFragmentainerGroup();
686 } while (column_set->NeedsNewFragmentainerGroupAt(offset_in_flow_thread,
687 page_boundary_rule));
688 }
689 }
690
UpdateFromNG()691 void LayoutMultiColumnFlowThread::UpdateFromNG() {
692 all_columns_have_known_height_ = true;
693 for (LayoutBox* column_box = FirstMultiColumnBox(); column_box;
694 column_box = column_box->NextSiblingMultiColumnBox()) {
695 if (column_box->IsLayoutMultiColumnSet())
696 ToLayoutMultiColumnSet(column_box)->UpdateFromNG();
697 column_box->ClearNeedsLayout();
698 column_box->UpdateAfterLayout();
699 }
700 }
701
IsFragmentainerLogicalHeightKnown()702 bool LayoutMultiColumnFlowThread::IsFragmentainerLogicalHeightKnown() {
703 return IsPageLogicalHeightKnown();
704 }
705
FragmentainerLogicalHeightAt(LayoutUnit block_offset)706 LayoutUnit LayoutMultiColumnFlowThread::FragmentainerLogicalHeightAt(
707 LayoutUnit block_offset) {
708 DCHECK(IsPageLogicalHeightKnown());
709 return PageLogicalHeightForOffset(block_offset);
710 }
711
RemainingLogicalHeightAt(LayoutUnit block_offset)712 LayoutUnit LayoutMultiColumnFlowThread::RemainingLogicalHeightAt(
713 LayoutUnit block_offset) {
714 DCHECK(IsPageLogicalHeightKnown());
715 return PageRemainingLogicalHeightForOffset(block_offset,
716 kAssociateWithLatterPage);
717 }
718
CalculateColumnHeightAvailable()719 void LayoutMultiColumnFlowThread::CalculateColumnHeightAvailable() {
720 // Calculate the non-auto content box height, or set it to 0 if it's auto. We
721 // need to know this before layout, so that we can figure out where to insert
722 // column breaks. We also treat LayoutView (which may be paginated, which uses
723 // the multicol implementation) as having a fixed height, since its height is
724 // deduced from the viewport height. We use computeLogicalHeight() to
725 // calculate the content box height. That method will clamp against max-height
726 // and min-height. Since we're now at the beginning of layout, and we don't
727 // know the actual height of the content yet, only call that method when
728 // height is definite, or we might fool ourselves into believing that columns
729 // have a definite height when they in fact don't.
730 LayoutBlockFlow* container = MultiColumnBlockFlow();
731 LayoutUnit column_height;
732 if (container->HasDefiniteLogicalHeight() || IsA<LayoutView>(container)) {
733 LogicalExtentComputedValues computed_values;
734 container->ComputeLogicalHeight(LayoutUnit(), container->LogicalTop(),
735 computed_values);
736 column_height = computed_values.extent_ -
737 container->BorderAndPaddingLogicalHeight() -
738 container->ScrollbarLogicalHeight();
739 }
740 SetColumnHeightAvailable(std::max(column_height, LayoutUnit()));
741 }
742
CalculateColumnCountAndWidth(LayoutUnit & width,unsigned & count) const743 void LayoutMultiColumnFlowThread::CalculateColumnCountAndWidth(
744 LayoutUnit& width,
745 unsigned& count) const {
746 LayoutBlock* column_block = MultiColumnBlockFlow();
747 const ComputedStyle* column_style = column_block->Style();
748 LayoutUnit available_width = column_block->ContentLogicalWidth();
749 LayoutUnit column_gap = ColumnGap(*column_style, available_width);
750 LayoutUnit computed_column_width =
751 max(LayoutUnit(1), LayoutUnit(column_style->ColumnWidth()));
752 unsigned computed_column_count = max<int>(1, column_style->ColumnCount());
753
754 DCHECK(!column_style->HasAutoColumnCount() ||
755 !column_style->HasAutoColumnWidth());
756 if (column_style->HasAutoColumnWidth() &&
757 !column_style->HasAutoColumnCount()) {
758 count = computed_column_count;
759 width = ((available_width - ((count - 1) * column_gap)) / count)
760 .ClampNegativeToZero();
761 } else if (!column_style->HasAutoColumnWidth() &&
762 column_style->HasAutoColumnCount()) {
763 count = std::max(LayoutUnit(1), (available_width + column_gap) /
764 (computed_column_width + column_gap))
765 .ToUnsigned();
766 width = ((available_width + column_gap) / count) - column_gap;
767 } else {
768 count = std::max(std::min(LayoutUnit(computed_column_count),
769 (available_width + column_gap) /
770 (computed_column_width + column_gap)),
771 LayoutUnit(1))
772 .ToUnsigned();
773 width = ((available_width + column_gap) / count) - column_gap;
774 }
775 }
776
ColumnGap(const ComputedStyle & style,LayoutUnit available_width)777 LayoutUnit LayoutMultiColumnFlowThread::ColumnGap(const ComputedStyle& style,
778 LayoutUnit available_width) {
779 if (style.ColumnGap().IsNormal()) {
780 // "1em" is recommended as the normal gap setting. Matches <p> margins.
781 return LayoutUnit(style.GetFontDescription().ComputedSize());
782 }
783 return ValueForLength(style.ColumnGap().GetLength(), available_width);
784 }
785
CreateAndInsertMultiColumnSet(LayoutBox * insert_before)786 void LayoutMultiColumnFlowThread::CreateAndInsertMultiColumnSet(
787 LayoutBox* insert_before) {
788 LayoutBlockFlow* multicol_container = MultiColumnBlockFlow();
789 LayoutMultiColumnSet* new_set = LayoutMultiColumnSet::CreateAnonymous(
790 *this, multicol_container->StyleRef());
791 multicol_container->LayoutBlock::AddChild(new_set, insert_before);
792 InvalidateColumnSets();
793
794 // We cannot handle immediate column set siblings (and there's no need for it,
795 // either). There has to be at least one spanner separating them.
796 DCHECK(!new_set->PreviousSiblingMultiColumnBox() ||
797 !new_set->PreviousSiblingMultiColumnBox()->IsLayoutMultiColumnSet());
798 DCHECK(!new_set->NextSiblingMultiColumnBox() ||
799 !new_set->NextSiblingMultiColumnBox()->IsLayoutMultiColumnSet());
800 }
801
CreateAndInsertSpannerPlaceholder(LayoutBox * spanner_object_in_flow_thread,LayoutObject * inserted_before_in_flow_thread)802 void LayoutMultiColumnFlowThread::CreateAndInsertSpannerPlaceholder(
803 LayoutBox* spanner_object_in_flow_thread,
804 LayoutObject* inserted_before_in_flow_thread) {
805 LayoutBox* insert_before_column_box = nullptr;
806 LayoutMultiColumnSet* set_to_split = nullptr;
807 if (inserted_before_in_flow_thread) {
808 // The spanner is inserted before something. Figure out what this entails.
809 // If the next object is a spanner too, it means that we can simply insert a
810 // new spanner placeholder in front of its placeholder.
811 insert_before_column_box =
812 inserted_before_in_flow_thread->SpannerPlaceholder();
813 if (!insert_before_column_box) {
814 // The next object isn't a spanner; it's regular column content. Examine
815 // what comes right before us in the flow thread, then.
816 LayoutObject* previous_layout_object =
817 PreviousInPreOrderSkippingOutOfFlow(this,
818 spanner_object_in_flow_thread);
819 if (!previous_layout_object || previous_layout_object == this) {
820 // The spanner is inserted as the first child of the multicol container,
821 // which means that we simply insert a new spanner placeholder at the
822 // beginning.
823 insert_before_column_box = FirstMultiColumnBox();
824 } else if (LayoutMultiColumnSpannerPlaceholder* previous_placeholder =
825 ContainingColumnSpannerPlaceholder(
826 previous_layout_object)) {
827 // Before us is another spanner. We belong right after it then.
828 insert_before_column_box =
829 previous_placeholder->NextSiblingMultiColumnBox();
830 } else {
831 // We're inside regular column content with both feet. Find out which
832 // column set this is. It needs to be split it into two sets, so that we
833 // can insert a new spanner placeholder between them.
834 set_to_split = MapDescendantToColumnSet(previous_layout_object);
835 DCHECK_EQ(set_to_split,
836 MapDescendantToColumnSet(inserted_before_in_flow_thread));
837 insert_before_column_box = set_to_split->NextSiblingMultiColumnBox();
838 // We've found out which set that needs to be split. Now proceed to
839 // inserting the spanner placeholder, and then insert a second column
840 // set.
841 }
842 }
843 DCHECK(set_to_split || insert_before_column_box);
844 }
845
846 LayoutBlockFlow* multicol_container = MultiColumnBlockFlow();
847 LayoutMultiColumnSpannerPlaceholder* new_placeholder =
848 LayoutMultiColumnSpannerPlaceholder::CreateAnonymous(
849 multicol_container->StyleRef(), *spanner_object_in_flow_thread);
850 DCHECK(!insert_before_column_box ||
851 insert_before_column_box->Parent() == multicol_container);
852 multicol_container->LayoutBlock::AddChild(new_placeholder,
853 insert_before_column_box);
854 spanner_object_in_flow_thread->SetSpannerPlaceholder(*new_placeholder);
855
856 if (set_to_split)
857 CreateAndInsertMultiColumnSet(insert_before_column_box);
858 }
859
DestroySpannerPlaceholder(LayoutMultiColumnSpannerPlaceholder * placeholder)860 void LayoutMultiColumnFlowThread::DestroySpannerPlaceholder(
861 LayoutMultiColumnSpannerPlaceholder* placeholder) {
862 if (LayoutBox* next_column_box = placeholder->NextSiblingMultiColumnBox()) {
863 LayoutBox* previous_column_box =
864 placeholder->PreviousSiblingMultiColumnBox();
865 if (next_column_box && next_column_box->IsLayoutMultiColumnSet() &&
866 previous_column_box && previous_column_box->IsLayoutMultiColumnSet()) {
867 // Need to merge two column sets.
868 next_column_box->Destroy();
869 InvalidateColumnSets();
870 }
871 }
872 placeholder->Destroy();
873 }
874
DescendantIsValidColumnSpanner(LayoutObject * descendant) const875 bool LayoutMultiColumnFlowThread::DescendantIsValidColumnSpanner(
876 LayoutObject* descendant) const {
877 // This method needs to behave correctly in the following situations:
878 // - When the descendant doesn't have a spanner placeholder but should have
879 // one (return true).
880 // - When the descendant doesn't have a spanner placeholder and still should
881 // not have one (return false).
882 // - When the descendant has a spanner placeholder but should no longer have
883 // one (return false).
884 // - When the descendant has a spanner placeholder and should still have one
885 // (return true).
886
887 // We assume that we're inside the flow thread. This function is not to be
888 // called otherwise.
889 DCHECK(descendant->IsDescendantOf(this));
890
891 // The spec says that column-span only applies to in-flow block-level
892 // elements.
893 if (descendant->StyleRef().GetColumnSpan() != EColumnSpan::kAll ||
894 !descendant->IsBox() || descendant->IsInline() ||
895 descendant->IsFloatingOrOutOfFlowPositioned())
896 return false;
897
898 if (!descendant->ContainingBlock()->IsLayoutBlockFlow()) {
899 // Needs to be in a block-flow container, and not e.g. a table.
900 return false;
901 }
902
903 // This looks like a spanner, but if we're inside something unbreakable or
904 // something that establishes a new formatting context, it's not to be treated
905 // as one.
906 for (LayoutBox* ancestor = ToLayoutBox(descendant)->ParentBox(); ancestor;
907 ancestor = ancestor->ContainingBlock()) {
908 if (ancestor->IsLayoutFlowThread()) {
909 DCHECK_EQ(ancestor, this);
910 return true;
911 }
912 if (!CanContainSpannerInParentFragmentationContext(*ancestor))
913 return false;
914 }
915 NOTREACHED();
916 return false;
917 }
918
AddColumnSetToThread(LayoutMultiColumnSet * column_set)919 void LayoutMultiColumnFlowThread::AddColumnSetToThread(
920 LayoutMultiColumnSet* column_set) {
921 if (LayoutMultiColumnSet* next_set =
922 column_set->NextSiblingMultiColumnSet()) {
923 LayoutMultiColumnSetList::iterator it =
924 multi_column_set_list_.find(next_set);
925 DCHECK(it != multi_column_set_list_.end());
926 multi_column_set_list_.InsertBefore(it, column_set);
927 } else {
928 multi_column_set_list_.insert(column_set);
929 }
930 }
931
WillBeRemovedFromTree()932 void LayoutMultiColumnFlowThread::WillBeRemovedFromTree() {
933 // Detach all column sets from the flow thread. Cannot destroy them at this
934 // point, since they are siblings of this object, and there may be pointers to
935 // this object's sibling somewhere further up on the call stack.
936 for (LayoutMultiColumnSet* column_set = FirstMultiColumnSet(); column_set;
937 column_set = column_set->NextSiblingMultiColumnSet())
938 column_set->DetachFromFlowThread();
939 MultiColumnBlockFlow()->ResetMultiColumnFlowThread();
940 LayoutFlowThread::WillBeRemovedFromTree();
941 }
942
SkipColumnSpanner(LayoutBox * layout_object,LayoutUnit logical_top_in_flow_thread)943 void LayoutMultiColumnFlowThread::SkipColumnSpanner(
944 LayoutBox* layout_object,
945 LayoutUnit logical_top_in_flow_thread) {
946 DCHECK(layout_object->IsColumnSpanAll());
947 LayoutMultiColumnSpannerPlaceholder* placeholder =
948 layout_object->SpannerPlaceholder();
949 LayoutBox* previous_column_box = placeholder->PreviousSiblingMultiColumnBox();
950 if (previous_column_box && previous_column_box->IsLayoutMultiColumnSet())
951 ToLayoutMultiColumnSet(previous_column_box)
952 ->EndFlow(logical_top_in_flow_thread);
953 LayoutBox* next_column_box = placeholder->NextSiblingMultiColumnBox();
954 if (next_column_box && next_column_box->IsLayoutMultiColumnSet()) {
955 LayoutMultiColumnSet* next_set = ToLayoutMultiColumnSet(next_column_box);
956 last_set_worked_on_ = next_set;
957 next_set->BeginFlow(logical_top_in_flow_thread);
958 }
959
960 // We'll lay out of spanners after flow thread layout has finished (during
961 // layout of the spanner placeholders). There may be containing blocks for
962 // out-of-flow positioned descendants of the spanner in the flow thread, so
963 // that out-of-flow objects inside the spanner will be laid out as part of
964 // flow thread layout (even if the spanner itself won't). We need to add such
965 // out-of-flow positioned objects to their containing blocks now, or they'll
966 // never get laid out. Since it's non-trivial to determine if we need this,
967 // and where such out-of-flow objects might be, just go through the whole
968 // subtree.
969 for (LayoutObject* descendant = layout_object->SlowFirstChild(); descendant;
970 descendant = descendant->NextInPreOrder()) {
971 if (descendant->IsBox() && descendant->IsOutOfFlowPositioned())
972 descendant->ContainingBlock()->InsertPositionedObject(
973 ToLayoutBox(descendant));
974 }
975 }
976
FinishLayout()977 bool LayoutMultiColumnFlowThread::FinishLayout() {
978 all_columns_have_known_height_ = true;
979 for (const auto* column_set = FirstMultiColumnSet(); column_set;
980 column_set = column_set->NextSiblingMultiColumnSet()) {
981 if (!column_set->IsPageLogicalHeightKnown()) {
982 all_columns_have_known_height_ = false;
983 break;
984 }
985 }
986 return !ColumnHeightsChanged();
987 }
988
989 // When processing layout objects to remove or when processing layout objects
990 // that have just been inserted, certain types of objects should be skipped.
ShouldSkipInsertedOrRemovedChild(LayoutMultiColumnFlowThread * flow_thread,const LayoutObject & child)991 static bool ShouldSkipInsertedOrRemovedChild(
992 LayoutMultiColumnFlowThread* flow_thread,
993 const LayoutObject& child) {
994 if (child.IsSVGChild()) {
995 // Don't descend into SVG objects. What's in there is of no interest, and
996 // there might even be a foreignObject there with column-span:all, which
997 // doesn't apply to us.
998 return true;
999 }
1000 if (child.IsLayoutFlowThread()) {
1001 // Found an inner flow thread. We need to skip it and its descendants.
1002 return true;
1003 }
1004 if (child.IsLayoutMultiColumnSet() ||
1005 child.IsLayoutMultiColumnSpannerPlaceholder()) {
1006 // Column sets and spanner placeholders in a child multicol context don't
1007 // affect the parent flow thread.
1008 return true;
1009 }
1010 if (child.IsOutOfFlowPositioned() &&
1011 child.ContainingBlock()->FlowThreadContainingBlock() != flow_thread) {
1012 // Out-of-flow with its containing block on the outside of the multicol
1013 // container.
1014 return true;
1015 }
1016 return false;
1017 }
1018
FlowThreadDescendantWasInserted(LayoutObject * descendant)1019 void LayoutMultiColumnFlowThread::FlowThreadDescendantWasInserted(
1020 LayoutObject* descendant) {
1021 DCHECK(!is_being_evacuated_);
1022 // This method ensures that the list of column sets and spanner placeholders
1023 // reflects the multicol content after having inserted a descendant (or
1024 // descendant subtree). See the header file for more information. Go through
1025 // the subtree that was just inserted and create column sets (needed by
1026 // regular column content) and spanner placeholders (one needed by each
1027 // spanner) where needed.
1028 if (ShouldSkipInsertedOrRemovedChild(this, *descendant))
1029 return;
1030 LayoutObject* object_after_subtree =
1031 NextInPreOrderAfterChildrenSkippingOutOfFlow(this, descendant);
1032 LayoutObject* next;
1033 for (LayoutObject* layout_object = descendant; layout_object;
1034 layout_object = next) {
1035 if (layout_object != descendant &&
1036 ShouldSkipInsertedOrRemovedChild(this, *layout_object)) {
1037 next = layout_object->NextInPreOrderAfterChildren(descendant);
1038 continue;
1039 }
1040 next = layout_object->NextInPreOrder(descendant);
1041 if (ContainingColumnSpannerPlaceholder(layout_object))
1042 continue; // Inside a column spanner. Nothing to do, then.
1043 if (DescendantIsValidColumnSpanner(layout_object)) {
1044 // This layoutObject is a spanner, so it needs to establish a spanner
1045 // placeholder.
1046 CreateAndInsertSpannerPlaceholder(ToLayoutBox(layout_object),
1047 object_after_subtree);
1048 continue;
1049 }
1050 // This layoutObject is regular column content (i.e. not a spanner). Create
1051 // a set if necessary.
1052 if (object_after_subtree) {
1053 if (LayoutMultiColumnSpannerPlaceholder* placeholder =
1054 object_after_subtree->SpannerPlaceholder()) {
1055 // If inserted right before a spanner, we need to make sure that there's
1056 // a set for us there.
1057 LayoutBox* previous = placeholder->PreviousSiblingMultiColumnBox();
1058 if (!previous || !previous->IsLayoutMultiColumnSet())
1059 CreateAndInsertMultiColumnSet(placeholder);
1060 } else {
1061 // Otherwise, since |objectAfterSubtree| isn't a spanner, it has to mean
1062 // that there's already a set for that content. We can use it for this
1063 // layoutObject too.
1064 DCHECK(MapDescendantToColumnSet(object_after_subtree));
1065 DCHECK_EQ(MapDescendantToColumnSet(layout_object),
1066 MapDescendantToColumnSet(object_after_subtree));
1067 }
1068 } else {
1069 // Inserting at the end. Then we just need to make sure that there's a
1070 // column set at the end.
1071 LayoutBox* last_column_box = LastMultiColumnBox();
1072 if (!last_column_box || !last_column_box->IsLayoutMultiColumnSet())
1073 CreateAndInsertMultiColumnSet();
1074 }
1075 }
1076 }
1077
FlowThreadDescendantWillBeRemoved(LayoutObject * descendant)1078 void LayoutMultiColumnFlowThread::FlowThreadDescendantWillBeRemoved(
1079 LayoutObject* descendant) {
1080 // This method ensures that the list of column sets and spanner placeholders
1081 // reflects the multicol content that we'll be left with after removal of a
1082 // descendant (or descendant subtree). See the header file for more
1083 // information. Removing content may mean that we need to remove column sets
1084 // and/or spanner placeholders.
1085 if (is_being_evacuated_)
1086 return;
1087 if (ShouldSkipInsertedOrRemovedChild(this, *descendant))
1088 return;
1089 bool had_containing_placeholder =
1090 ContainingColumnSpannerPlaceholder(descendant);
1091 bool processed_something = false;
1092 LayoutObject* next;
1093 // Remove spanner placeholders that are no longer needed, and merge column
1094 // sets around them.
1095 for (LayoutObject* layout_object = descendant; layout_object;
1096 layout_object = next) {
1097 if (layout_object != descendant &&
1098 ShouldSkipInsertedOrRemovedChild(this, *layout_object)) {
1099 next = layout_object->NextInPreOrderAfterChildren(descendant);
1100 continue;
1101 }
1102 processed_something = true;
1103 LayoutMultiColumnSpannerPlaceholder* placeholder =
1104 layout_object->SpannerPlaceholder();
1105 if (!placeholder) {
1106 next = layout_object->NextInPreOrder(descendant);
1107 continue;
1108 }
1109 next = layout_object->NextInPreOrderAfterChildren(
1110 descendant); // It's a spanner. Its children are of no interest to us.
1111 DestroySpannerPlaceholder(placeholder);
1112 }
1113 if (had_containing_placeholder || !processed_something)
1114 return; // No column content will be removed, so we can stop here.
1115
1116 // Column content will be removed. Does this mean that we should destroy a
1117 // column set?
1118 LayoutMultiColumnSpannerPlaceholder* adjacent_previous_spanner_placeholder =
1119 nullptr;
1120 LayoutObject* previous_layout_object =
1121 PreviousInPreOrderSkippingOutOfFlow(this, descendant);
1122 if (previous_layout_object && previous_layout_object != this) {
1123 adjacent_previous_spanner_placeholder =
1124 ContainingColumnSpannerPlaceholder(previous_layout_object);
1125 if (!adjacent_previous_spanner_placeholder)
1126 return; // Preceded by column content. Set still needed.
1127 }
1128 LayoutMultiColumnSpannerPlaceholder* adjacent_next_spanner_placeholder =
1129 nullptr;
1130 LayoutObject* next_layout_object =
1131 NextInPreOrderAfterChildrenSkippingOutOfFlow(this, descendant);
1132 if (next_layout_object) {
1133 adjacent_next_spanner_placeholder =
1134 ContainingColumnSpannerPlaceholder(next_layout_object);
1135 if (!adjacent_next_spanner_placeholder)
1136 return; // Followed by column content. Set still needed.
1137 }
1138 // We have now determined that, with the removal of |descendant|, we should
1139 // remove a column set. Locate it and remove it. Do it without involving
1140 // mapDescendantToColumnSet(), as that might be very slow. Deduce the right
1141 // set from the spanner placeholders that we've already found.
1142 LayoutMultiColumnSet* column_set_to_remove;
1143 if (adjacent_next_spanner_placeholder) {
1144 column_set_to_remove = ToLayoutMultiColumnSet(
1145 adjacent_next_spanner_placeholder->PreviousSiblingMultiColumnBox());
1146 DCHECK(
1147 !adjacent_previous_spanner_placeholder ||
1148 column_set_to_remove ==
1149 adjacent_previous_spanner_placeholder->NextSiblingMultiColumnBox());
1150 } else if (adjacent_previous_spanner_placeholder) {
1151 column_set_to_remove = ToLayoutMultiColumnSet(
1152 adjacent_previous_spanner_placeholder->NextSiblingMultiColumnBox());
1153 } else {
1154 // If there were no adjacent spanners, it has to mean that there's only one
1155 // column set, since it's only spanners that may cause creation of
1156 // multiple sets.
1157 column_set_to_remove = FirstMultiColumnSet();
1158 DCHECK(column_set_to_remove);
1159 DCHECK(!column_set_to_remove->NextSiblingMultiColumnSet());
1160 }
1161 DCHECK(column_set_to_remove);
1162 column_set_to_remove->Destroy();
1163 }
1164
NeedsToReinsertIntoFlowThread(const ComputedStyle & old_style,const ComputedStyle & new_style)1165 static inline bool NeedsToReinsertIntoFlowThread(
1166 const ComputedStyle& old_style,
1167 const ComputedStyle& new_style) {
1168 // If we've become (or are about to become) a container for absolutely
1169 // positioned descendants, or if we're no longer going to be one, we need to
1170 // re-evaluate the need for column sets. There may be out-of-flow descendants
1171 // further down that become part of the flow thread, or cease to be part of
1172 // the flow thread, because of this change.
1173 if (old_style.CanContainFixedPositionObjects(false) !=
1174 new_style.CanContainFixedPositionObjects(false))
1175 return true;
1176 return (old_style.HasInFlowPosition() &&
1177 new_style.GetPosition() == EPosition::kStatic) ||
1178 (new_style.HasInFlowPosition() &&
1179 old_style.GetPosition() == EPosition::kStatic);
1180 }
1181
NeedsToRemoveFromFlowThread(const ComputedStyle & old_style,const ComputedStyle & new_style)1182 static inline bool NeedsToRemoveFromFlowThread(const ComputedStyle& old_style,
1183 const ComputedStyle& new_style) {
1184 // This function is called BEFORE computed style update. If an in-flow
1185 // descendant goes out-of-flow, we may have to remove column sets and spanner
1186 // placeholders. Note that we may end up with false positives here, since some
1187 // out-of-flow descendants still need to be associated with a column set. This
1188 // is the case when the containing block of the soon-to-be out-of-flow
1189 // positioned descendant is contained by the same flow thread as the
1190 // descendant currently is inside. It's too early to check for that, though,
1191 // since the descendant at this point is still in-flow positioned. We'll
1192 // detect this and re-insert it into the flow thread when computed style has
1193 // been updated.
1194 return (new_style.HasOutOfFlowPosition() &&
1195 !old_style.HasOutOfFlowPosition()) ||
1196 NeedsToReinsertIntoFlowThread(old_style, new_style);
1197 }
1198
NeedsToInsertIntoFlowThread(const LayoutMultiColumnFlowThread * flow_thread,const LayoutBox * descendant,const ComputedStyle & old_style,const ComputedStyle & new_style)1199 static inline bool NeedsToInsertIntoFlowThread(
1200 const LayoutMultiColumnFlowThread* flow_thread,
1201 const LayoutBox* descendant,
1202 const ComputedStyle& old_style,
1203 const ComputedStyle& new_style) {
1204 // This function is called AFTER computed style update. If an out-of-flow
1205 // descendant goes in-flow, we may have to insert column sets and spanner
1206 // placeholders.
1207 bool toggled_out_of_flow =
1208 new_style.HasOutOfFlowPosition() != old_style.HasOutOfFlowPosition();
1209 if (toggled_out_of_flow) {
1210 // If we're no longer out-of-flow, we definitely need the descendant to be
1211 // associated with a column set.
1212 if (!new_style.HasOutOfFlowPosition())
1213 return true;
1214 const auto* containing_flow_thread =
1215 descendant->ContainingBlock()->FlowThreadContainingBlock();
1216 // If an out-of-flow positioned descendant is still going to be contained by
1217 // this flow thread, the descendant needs to be associated with a column
1218 // set.
1219 if (containing_flow_thread == flow_thread)
1220 return true;
1221 }
1222 return NeedsToReinsertIntoFlowThread(old_style, new_style);
1223 }
1224
FlowThreadDescendantStyleWillChange(LayoutBox * descendant,StyleDifference diff,const ComputedStyle & new_style)1225 void LayoutMultiColumnFlowThread::FlowThreadDescendantStyleWillChange(
1226 LayoutBox* descendant,
1227 StyleDifference diff,
1228 const ComputedStyle& new_style) {
1229 toggle_spanners_if_needed_ = false;
1230 if (NeedsToRemoveFromFlowThread(descendant->StyleRef(), new_style)) {
1231 FlowThreadDescendantWillBeRemoved(descendant);
1232 return;
1233 }
1234 #if DCHECK_IS_ON()
1235 style_changed_box_ = descendant;
1236 #endif
1237 // Keep track of whether this object was of such a type that it could contain
1238 // column-span:all descendants. If the style change in progress changes this
1239 // state, we need to look for spanners to add or remove in the subtree of
1240 // |descendant|.
1241 toggle_spanners_if_needed_ = true;
1242 could_contain_spanners_ =
1243 CanContainSpannerInParentFragmentationContext(*descendant);
1244 }
1245
FlowThreadDescendantStyleDidChange(LayoutBox * descendant,StyleDifference diff,const ComputedStyle & old_style)1246 void LayoutMultiColumnFlowThread::FlowThreadDescendantStyleDidChange(
1247 LayoutBox* descendant,
1248 StyleDifference diff,
1249 const ComputedStyle& old_style) {
1250 bool toggle_spanners_if_needed = toggle_spanners_if_needed_;
1251 toggle_spanners_if_needed_ = false;
1252
1253 if (NeedsToInsertIntoFlowThread(this, descendant, old_style,
1254 descendant->StyleRef())) {
1255 FlowThreadDescendantWasInserted(descendant);
1256 return;
1257 }
1258 if (DescendantIsValidColumnSpanner(descendant)) {
1259 // We went from being regular column content to becoming a spanner.
1260 DCHECK(!descendant->SpannerPlaceholder());
1261
1262 // First remove this as regular column content. Note that this will walk the
1263 // entire subtree of |descendant|. There might be spanners there (which
1264 // won't be spanners anymore, since we're not allowed to nest spanners),
1265 // whose placeholders must die.
1266 FlowThreadDescendantWillBeRemoved(descendant);
1267
1268 CreateAndInsertSpannerPlaceholder(
1269 descendant,
1270 NextInPreOrderAfterChildrenSkippingOutOfFlow(this, descendant));
1271 return;
1272 }
1273
1274 if (!toggle_spanners_if_needed)
1275 return;
1276 #if DCHECK_IS_ON()
1277 // Make sure that we were preceded by a call to
1278 // flowThreadDescendantStyleWillChange() with the same descendant as we have
1279 // now.
1280 DCHECK_EQ(style_changed_box_, descendant);
1281 #endif
1282
1283 if (could_contain_spanners_ !=
1284 CanContainSpannerInParentFragmentationContext(*descendant))
1285 ToggleSpannersInSubtree(descendant);
1286 }
1287
ToggleSpannersInSubtree(LayoutBox * descendant)1288 void LayoutMultiColumnFlowThread::ToggleSpannersInSubtree(
1289 LayoutBox* descendant) {
1290 DCHECK_NE(could_contain_spanners_,
1291 CanContainSpannerInParentFragmentationContext(*descendant));
1292
1293 // If there are no spanners at all in this multicol container, there's no
1294 // need to look for any to remove.
1295 if (could_contain_spanners_ && !HasAnyColumnSpanners(*this))
1296 return;
1297
1298 bool walk_children;
1299 for (LayoutObject* object = descendant->NextInPreOrder(descendant); object;
1300 object = walk_children
1301 ? object->NextInPreOrder(descendant)
1302 : object->NextInPreOrderAfterChildren(descendant)) {
1303 walk_children = false;
1304 if (!object->IsBox())
1305 continue;
1306 LayoutBox& box = ToLayoutBox(*object);
1307 if (could_contain_spanners_) {
1308 // Remove all spanners (turn them into regular column content), as we can
1309 // no longer contain them.
1310 if (box.IsColumnSpanAll()) {
1311 DestroySpannerPlaceholder(box.SpannerPlaceholder());
1312 continue;
1313 }
1314 } else if (DescendantIsValidColumnSpanner(object)) {
1315 // We can now contain spanners, and we found a candidate. Turn it into a
1316 // spanner, if it's not already one. We have to check if it's already a
1317 // spanner, because in some cases we incorrectly think that we need to
1318 // toggle spanners. One known case is when some ancestor changes
1319 // writing-mode (which is an inherited property). Writing mode roots
1320 // establish block formatting context (which means that there can be no
1321 // column spanners inside). When changing the style on one object in the
1322 // tree at a time, we're going to see writing mode roots that are not
1323 // going to remain writing mode roots when all objects have been updated
1324 // (because then all will have got the same writing mode).
1325 if (!box.IsColumnSpanAll()) {
1326 CreateAndInsertSpannerPlaceholder(
1327 &box, NextInPreOrderAfterChildrenSkippingOutOfFlow(this, &box));
1328 }
1329 continue;
1330 }
1331 walk_children = CanContainSpannerInParentFragmentationContext(box);
1332 }
1333 }
1334
PreferredLogicalWidths() const1335 MinMaxSizes LayoutMultiColumnFlowThread::PreferredLogicalWidths() const {
1336 // The min/max intrinsic widths calculated really tell how much space elements
1337 // need when laid out inside the columns. In order to eventually end up with
1338 // the desired column width, we need to convert them to values pertaining to
1339 // the multicol container.
1340 auto* flow = MultiColumnBlockFlow();
1341 const ComputedStyle* multicol_style = flow->Style();
1342 LayoutUnit column_count(
1343 multicol_style->HasAutoColumnCount() ? 1 : multicol_style->ColumnCount());
1344 LayoutUnit gap_extra((column_count - 1) *
1345 ColumnGap(*multicol_style, LayoutUnit()));
1346 MinMaxSizes sizes;
1347
1348 if (flow->HasOverrideIntrinsicContentLogicalWidth()) {
1349 sizes = flow->OverrideIntrinsicContentLogicalWidth();
1350 } else if (flow->ShouldApplySizeContainment()) {
1351 sizes = LayoutUnit();
1352 } else {
1353 sizes = LayoutFlowThread::PreferredLogicalWidths();
1354 }
1355
1356 LayoutUnit column_width;
1357 if (multicol_style->HasAutoColumnWidth()) {
1358 sizes.min_size = sizes.min_size * column_count + gap_extra;
1359 } else {
1360 column_width = LayoutUnit(multicol_style->ColumnWidth());
1361 sizes.min_size = std::min(sizes.min_size, column_width);
1362 }
1363 // Note that if column-count is auto here, we should resolve it to calculate
1364 // the maximum intrinsic width, instead of pretending that it's 1. The only
1365 // way to do that is by performing a layout pass, but this is not an
1366 // appropriate time or place for layout. The good news is that if height is
1367 // unconstrained and there are no explicit breaks, the resolved column-count
1368 // really should be 1.
1369 sizes.max_size =
1370 std::max(sizes.max_size, column_width) * column_count + gap_extra;
1371 return sizes;
1372 }
1373
ComputeLogicalHeight(LayoutUnit logical_height,LayoutUnit logical_top,LogicalExtentComputedValues & computed_values) const1374 void LayoutMultiColumnFlowThread::ComputeLogicalHeight(
1375 LayoutUnit logical_height,
1376 LayoutUnit logical_top,
1377 LogicalExtentComputedValues& computed_values) const {
1378 // We simply remain at our intrinsic height.
1379 computed_values.extent_ = logical_height;
1380 computed_values.position_ = logical_top;
1381 }
1382
UpdateLogicalWidth()1383 void LayoutMultiColumnFlowThread::UpdateLogicalWidth() {
1384 LayoutUnit column_width;
1385 CalculateColumnCountAndWidth(column_width, column_count_);
1386 SetLogicalWidth(column_width);
1387 }
1388
UpdateLayout()1389 void LayoutMultiColumnFlowThread::UpdateLayout() {
1390 DCHECK(!last_set_worked_on_);
1391 last_set_worked_on_ = FirstMultiColumnSet();
1392 if (last_set_worked_on_)
1393 last_set_worked_on_->BeginFlow(LayoutUnit());
1394 LayoutFlowThread::UpdateLayout();
1395 if (LayoutMultiColumnSet* last_set = LastMultiColumnSet()) {
1396 DCHECK_EQ(last_set, last_set_worked_on_);
1397 if (!last_set->NextSiblingMultiColumnSet()) {
1398 // Include trailing overflow in the last column set (also if the last set
1399 // is followed by one or more spanner placeholders). The idea is that we
1400 // will generate additional columns and pages to hold that overflow,
1401 // since people do write bad content like <body style="height:0px"> in
1402 // multi-column layouts.
1403 // TODO(mstensho): Once we support nested multicol, adding in overflow
1404 // here may result in the need for creating additional rows, since there
1405 // may not be enough space remaining in the currently last row.
1406 LayoutRect layout_rect = LayoutOverflowRect();
1407 LayoutUnit logical_bottom_in_flow_thread =
1408 IsHorizontalWritingMode() ? layout_rect.MaxY() : layout_rect.MaxX();
1409 DCHECK_GE(logical_bottom_in_flow_thread, LogicalHeight());
1410 last_set->EndFlow(logical_bottom_in_flow_thread);
1411 }
1412 }
1413 last_set_worked_on_ = nullptr;
1414 }
1415
ContentWasLaidOut(LayoutUnit logical_bottom_in_flow_thread_after_pagination)1416 void LayoutMultiColumnFlowThread::ContentWasLaidOut(
1417 LayoutUnit logical_bottom_in_flow_thread_after_pagination) {
1418 // Check if we need another fragmentainer group. If we've run out of columns
1419 // in the last fragmentainer group (column row), we need to insert another
1420 // fragmentainer group to hold more columns.
1421
1422 // First figure out if there's any chance that we're nested at all. If we can
1423 // be sure that we're not, bail early. This code is run very often, and since
1424 // locating a containing flow thread has some cost (depending on tree depth),
1425 // avoid calling enclosingFragmentationContext() right away. This test may
1426 // give some false positives (hence the "mayBe"), if we're in an out-of-flow
1427 // subtree and have an outer multicol container that doesn't affect us, but
1428 // that's okay. We'll discover that further down the road when trying to
1429 // locate our enclosing flow thread for real.
1430 bool may_be_nested = MultiColumnBlockFlow()->IsInsideFlowThread() ||
1431 View()->FragmentationContext();
1432 if (!may_be_nested)
1433 return;
1434 AppendNewFragmentainerGroupIfNeeded(
1435 logical_bottom_in_flow_thread_after_pagination, kAssociateWithFormerPage);
1436 }
1437
CanSkipLayout(const LayoutBox & root) const1438 bool LayoutMultiColumnFlowThread::CanSkipLayout(const LayoutBox& root) const {
1439 // Objects containing spanners is all we need to worry about, so if there are
1440 // no spanners at all in this multicol container, we can just return the good
1441 // news right away.
1442 if (!HasAnyColumnSpanners(*this))
1443 return true;
1444
1445 LayoutObject* next;
1446 for (const LayoutObject* object = &root; object; object = next) {
1447 if (object->IsColumnSpanAll()) {
1448 // A spanner potentially ends one fragmentainer group and begins a new
1449 // one, and thus determines the flow thread portion bottom and top of
1450 // adjacent fragmentainer groups. It's just too hard to guess these values
1451 // without laying out.
1452 return false;
1453 }
1454 if (CanContainSpannerInParentFragmentationContext(*object))
1455 next = object->NextInPreOrder(&root);
1456 else
1457 next = object->NextInPreOrderAfterChildren(&root);
1458 }
1459 return true;
1460 }
1461
GetMultiColumnLayoutState() const1462 MultiColumnLayoutState LayoutMultiColumnFlowThread::GetMultiColumnLayoutState()
1463 const {
1464 return MultiColumnLayoutState(last_set_worked_on_);
1465 }
1466
RestoreMultiColumnLayoutState(const MultiColumnLayoutState & state)1467 void LayoutMultiColumnFlowThread::RestoreMultiColumnLayoutState(
1468 const MultiColumnLayoutState& state) {
1469 last_set_worked_on_ = state.ColumnSet();
1470 }
1471
1472 } // namespace blink
1473