1 // Copyright 2015 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "third_party/blink/renderer/core/layout/multi_column_fragmentainer_group.h"
6
7 #include "third_party/blink/renderer/core/layout/column_balancer.h"
8 #include "third_party/blink/renderer/core/layout/fragmentation_context.h"
9 #include "third_party/blink/renderer/core/layout/layout_multi_column_set.h"
10
11 namespace blink {
12
13 // Limit the maximum column count, to prevent potential performance problems.
14 static const unsigned kColumnCountClampMax = 10000;
15
16 // Clamp "infinite" clips to a number of pixels that can be losslessly
17 // converted to and from floating point, to avoid loss of precision.
18 // Note that tables have something similar, see
19 // TableLayoutAlgorithm::kTableMaxWidth.
20 static const int kMulticolMaxClipPixels = 1000000;
21
MultiColumnFragmentainerGroup(const LayoutMultiColumnSet & column_set)22 MultiColumnFragmentainerGroup::MultiColumnFragmentainerGroup(
23 const LayoutMultiColumnSet& column_set)
24 : column_set_(&column_set) {}
25
IsFirstGroup() const26 bool MultiColumnFragmentainerGroup::IsFirstGroup() const {
27 return &column_set_->FirstFragmentainerGroup() == this;
28 }
29
IsLastGroup() const30 bool MultiColumnFragmentainerGroup::IsLastGroup() const {
31 return &column_set_->LastFragmentainerGroup() == this;
32 }
33
OffsetFromColumnSet() const34 LayoutSize MultiColumnFragmentainerGroup::OffsetFromColumnSet() const {
35 LayoutSize offset(LayoutUnit(), LogicalTop());
36 if (!column_set_->FlowThread()->IsHorizontalWritingMode())
37 return offset.TransposedSize();
38 return offset;
39 }
40
41 LayoutUnit
BlockOffsetInEnclosingFragmentationContext() const42 MultiColumnFragmentainerGroup::BlockOffsetInEnclosingFragmentationContext()
43 const {
44 return LogicalTop() + column_set_->LogicalTopFromMulticolContentEdge() +
45 column_set_->MultiColumnFlowThread()
46 ->BlockOffsetInEnclosingFragmentationContext();
47 }
48
LogicalHeightInFlowThreadAt(unsigned column_index) const49 LayoutUnit MultiColumnFragmentainerGroup::LogicalHeightInFlowThreadAt(
50 unsigned column_index) const {
51 DCHECK(IsLogicalHeightKnown());
52 LayoutUnit column_height = ColumnLogicalHeight();
53 LayoutUnit logical_top = LogicalTopInFlowThreadAt(column_index);
54 LayoutUnit logical_bottom = logical_top + column_height;
55 unsigned actual_count = ActualColumnCount();
56 if (column_index + 1 >= actual_count) {
57 // The last column may contain overflow content, if the actual column count
58 // was clamped, so using the column height won't do. This is also a way to
59 // stay within the bounds of the flow thread, if the last column happens to
60 // contain LESS than the other columns. We also need this clamping if we're
61 // given a column index *after* the last column. Height should obviously be
62 // 0 then. We may be called with a column index that's one entry past the
63 // end if we're dealing with zero-height content at the very end of the flow
64 // thread, and this location is at a column boundary.
65 if (column_index + 1 == actual_count)
66 logical_bottom = LogicalBottomInFlowThread();
67 else
68 logical_bottom = logical_top;
69 }
70 return (logical_bottom - logical_top).ClampNegativeToZero();
71 }
72
ResetColumnHeight()73 void MultiColumnFragmentainerGroup::ResetColumnHeight() {
74 max_logical_height_ = CalculateMaxColumnHeight();
75
76 LayoutMultiColumnFlowThread* flow_thread =
77 column_set_->MultiColumnFlowThread();
78 if (column_set_->HeightIsAuto()) {
79 FragmentationContext* enclosing_fragmentation_context =
80 flow_thread->EnclosingFragmentationContext();
81 if (enclosing_fragmentation_context &&
82 enclosing_fragmentation_context->IsFragmentainerLogicalHeightKnown()) {
83 // Set an initial height, based on the fragmentainer height in the outer
84 // fragmentation context, in order to tell how much content this
85 // MultiColumnFragmentainerGroup can hold, and when we need to append a
86 // new one.
87 is_logical_height_known_ = true;
88 logical_height_ = max_logical_height_;
89 return;
90 }
91 }
92 // If the multicol container has a definite height, use it as the column
93 // height. This even applies when we are to balance the columns. We'll still
94 // use the definite height as an initial height, and lay out once at that
95 // column height. If it turns out that the content needs less than this
96 // height, we have to balance and shrink the height and lay out the columns
97 // over again.
98 if (LayoutUnit logical_height = flow_thread->ColumnHeightAvailable()) {
99 is_logical_height_known_ = true;
100 SetAndConstrainColumnHeight(HeightAdjustedForRowOffset(logical_height));
101 } else {
102 is_logical_height_known_ = false;
103 logical_height_ = LayoutUnit();
104 }
105 }
106
RecalculateColumnHeight(LayoutMultiColumnSet & column_set)107 bool MultiColumnFragmentainerGroup::RecalculateColumnHeight(
108 LayoutMultiColumnSet& column_set) {
109 LayoutUnit old_column_height = logical_height_;
110
111 max_logical_height_ = CalculateMaxColumnHeight();
112
113 // Only the last row may have auto height, and thus be balanced. There are no
114 // good reasons to balance the preceding rows, and that could potentially lead
115 // to an insane number of layout passes as well.
116 if (IsLastGroup() && column_set.HeightIsAuto()) {
117 LayoutUnit new_column_height;
118 if (!column_set.IsInitialHeightCalculated()) {
119 // Initial balancing: Start with the lowest imaginable column height. Also
120 // calculate the height of the tallest piece of unbreakable content.
121 // Columns should never get any shorter than that (unless constrained by
122 // max-height). Propagate this to our containing column set, in case there
123 // is an outer multicol container that also needs to balance. After having
124 // calculated the initial column height, the multicol container needs
125 // another layout pass with the column height that we just calculated.
126 InitialColumnHeightFinder initial_height_finder(
127 column_set, LogicalTopInFlowThread(), LogicalBottomInFlowThread());
128 column_set.PropagateTallestUnbreakableLogicalHeight(
129 initial_height_finder.TallestUnbreakableLogicalHeight());
130 new_column_height = initial_height_finder.InitialMinimalBalancedHeight();
131 } else {
132 // Rebalancing: After having laid out again, we'll need to rebalance if
133 // the height wasn't enough and we're allowed to stretch it, and then
134 // re-lay out. There are further details on the column balancing
135 // machinery in ColumnBalancer and its derivates.
136 new_column_height = RebalanceColumnHeightIfNeeded();
137 }
138 SetAndConstrainColumnHeight(new_column_height);
139 } else {
140 // The position of the column set may have changed, in which case height
141 // available for columns may have changed as well.
142 SetAndConstrainColumnHeight(logical_height_);
143 }
144
145 // We may not have found our final height yet, but at least we've found a
146 // height.
147 is_logical_height_known_ = true;
148
149 if (logical_height_ == old_column_height)
150 return false; // No change. We're done.
151
152 return true; // Need another pass.
153 }
154
FlowThreadTranslationAtOffset(LayoutUnit offset_in_flow_thread,LayoutBox::PageBoundaryRule rule,CoordinateSpaceConversion mode) const155 LayoutSize MultiColumnFragmentainerGroup::FlowThreadTranslationAtOffset(
156 LayoutUnit offset_in_flow_thread,
157 LayoutBox::PageBoundaryRule rule,
158 CoordinateSpaceConversion mode) const {
159 LayoutMultiColumnFlowThread* flow_thread =
160 column_set_->MultiColumnFlowThread();
161
162 // A column out of range doesn't have a flow thread portion, so we need to
163 // clamp to make sure that we stay within the actual columns. This means that
164 // content in the overflow area will be mapped to the last actual column,
165 // instead of being mapped to an imaginary column further ahead.
166 unsigned column_index =
167 offset_in_flow_thread >= LogicalBottomInFlowThread()
168 ? ActualColumnCount() - 1
169 : ColumnIndexAtOffset(offset_in_flow_thread, rule);
170
171 LayoutRect portion_rect(FlowThreadPortionRectAt(column_index));
172 flow_thread->DeprecatedFlipForWritingMode(portion_rect);
173 portion_rect.MoveBy(flow_thread->PhysicalLocation().ToLayoutPoint());
174
175 LayoutRect column_rect(ColumnRectAt(column_index));
176 column_rect.Move(OffsetFromColumnSet());
177 column_set_->DeprecatedFlipForWritingMode(column_rect);
178 column_rect.MoveBy(column_set_->PhysicalLocation().ToLayoutPoint());
179
180 LayoutSize translation_relative_to_flow_thread =
181 column_rect.Location() - portion_rect.Location();
182 if (mode == CoordinateSpaceConversion::kContaining)
183 return translation_relative_to_flow_thread;
184
185 LayoutSize enclosing_translation;
186 if (LayoutMultiColumnFlowThread* enclosing_flow_thread =
187 flow_thread->EnclosingFlowThread()) {
188 const MultiColumnFragmentainerGroup& first_row =
189 flow_thread->FirstMultiColumnSet()->FirstFragmentainerGroup();
190 // Translation that would map points in the coordinate space of the
191 // outermost flow thread to visual points in the first column in the first
192 // fragmentainer group (row) in our multicol container.
193 LayoutSize enclosing_translation_origin =
194 enclosing_flow_thread->FlowThreadTranslationAtOffset(
195 first_row.BlockOffsetInEnclosingFragmentationContext(),
196 LayoutBox::kAssociateWithLatterPage, mode);
197
198 // Translation that would map points in the coordinate space of the
199 // outermost flow thread to visual points in the first column in this
200 // fragmentainer group.
201 enclosing_translation =
202 enclosing_flow_thread->FlowThreadTranslationAtOffset(
203 BlockOffsetInEnclosingFragmentationContext(),
204 LayoutBox::kAssociateWithLatterPage, mode);
205
206 // What we ultimately return from this method is a translation that maps
207 // points in the coordinate space of our flow thread to a visual point in a
208 // certain column in this fragmentainer group. We had to go all the way up
209 // to the outermost flow thread, since this fragmentainer group may be in a
210 // different outer column than the first outer column that this multicol
211 // container lives in. It's the visual distance between the first
212 // fragmentainer group and this fragmentainer group that we need to add to
213 // the translation.
214 enclosing_translation -= enclosing_translation_origin;
215 }
216
217 return enclosing_translation + translation_relative_to_flow_thread;
218 }
219
ColumnLogicalTopForOffset(LayoutUnit offset_in_flow_thread) const220 LayoutUnit MultiColumnFragmentainerGroup::ColumnLogicalTopForOffset(
221 LayoutUnit offset_in_flow_thread) const {
222 unsigned column_index = ColumnIndexAtOffset(
223 offset_in_flow_thread, LayoutBox::kAssociateWithLatterPage);
224 return LogicalTopInFlowThreadAt(column_index);
225 }
226
VisualPointToFlowThreadPoint(const LayoutPoint & visual_point,SnapToColumnPolicy snap) const227 LayoutPoint MultiColumnFragmentainerGroup::VisualPointToFlowThreadPoint(
228 const LayoutPoint& visual_point,
229 SnapToColumnPolicy snap) const {
230 unsigned column_index = ColumnIndexAtVisualPoint(visual_point);
231 LayoutRect column_rect = ColumnRectAt(column_index);
232 LayoutPoint local_point(visual_point);
233 local_point.MoveBy(-column_rect.Location());
234 if (!column_set_->IsHorizontalWritingMode()) {
235 if (snap == kSnapToColumn) {
236 LayoutUnit column_start = column_set_->StyleRef().IsLeftToRightDirection()
237 ? LayoutUnit()
238 : column_rect.Height();
239 if (local_point.X() < 0)
240 local_point = LayoutPoint(LayoutUnit(), column_start);
241 else if (local_point.X() > ColumnLogicalHeight())
242 local_point = LayoutPoint(ColumnLogicalHeight(), column_start);
243 }
244 return LayoutPoint(local_point.X() + LogicalTopInFlowThreadAt(column_index),
245 local_point.Y());
246 }
247 if (snap == kSnapToColumn) {
248 LayoutUnit column_start = column_set_->StyleRef().IsLeftToRightDirection()
249 ? LayoutUnit()
250 : column_rect.Width();
251 if (local_point.Y() < 0)
252 local_point = LayoutPoint(column_start, LayoutUnit());
253 else if (local_point.Y() > ColumnLogicalHeight())
254 local_point = LayoutPoint(column_start, ColumnLogicalHeight());
255 }
256 return LayoutPoint(local_point.X(),
257 local_point.Y() + LogicalTopInFlowThreadAt(column_index));
258 }
259
FragmentsBoundingBox(const LayoutRect & bounding_box_in_flow_thread) const260 LayoutRect MultiColumnFragmentainerGroup::FragmentsBoundingBox(
261 const LayoutRect& bounding_box_in_flow_thread) const {
262 // Find the start and end column intersected by the bounding box.
263 LayoutRect flipped_bounding_box_in_flow_thread(bounding_box_in_flow_thread);
264 LayoutFlowThread* flow_thread = column_set_->FlowThread();
265 flow_thread->DeprecatedFlipForWritingMode(
266 flipped_bounding_box_in_flow_thread);
267 bool is_horizontal_writing_mode = column_set_->IsHorizontalWritingMode();
268 LayoutUnit bounding_box_logical_top =
269 is_horizontal_writing_mode ? flipped_bounding_box_in_flow_thread.Y()
270 : flipped_bounding_box_in_flow_thread.X();
271 LayoutUnit bounding_box_logical_bottom =
272 is_horizontal_writing_mode ? flipped_bounding_box_in_flow_thread.MaxY()
273 : flipped_bounding_box_in_flow_thread.MaxX();
274 if (bounding_box_logical_bottom <= LogicalTopInFlowThread() ||
275 bounding_box_logical_top >= LogicalBottomInFlowThread()) {
276 // The bounding box doesn't intersect this fragmentainer group.
277 return LayoutRect();
278 }
279 unsigned start_column;
280 unsigned end_column;
281 ColumnIntervalForBlockRangeInFlowThread(bounding_box_logical_top,
282 bounding_box_logical_bottom,
283 start_column, end_column);
284
285 LayoutRect start_column_flow_thread_overflow_portion =
286 FlowThreadPortionOverflowRectAt(start_column);
287 flow_thread->DeprecatedFlipForWritingMode(
288 start_column_flow_thread_overflow_portion);
289 LayoutRect start_column_rect(bounding_box_in_flow_thread);
290 start_column_rect.Intersect(start_column_flow_thread_overflow_portion);
291 start_column_rect.Move(
292 FlowThreadTranslationAtOffset(LogicalTopInFlowThreadAt(start_column),
293 LayoutBox::kAssociateWithLatterPage,
294 CoordinateSpaceConversion::kContaining));
295 if (start_column == end_column)
296 return start_column_rect; // It all takes place in one column. We're done.
297
298 LayoutRect end_column_flow_thread_overflow_portion =
299 FlowThreadPortionOverflowRectAt(end_column);
300 flow_thread->DeprecatedFlipForWritingMode(
301 end_column_flow_thread_overflow_portion);
302 LayoutRect end_column_rect(bounding_box_in_flow_thread);
303 end_column_rect.Intersect(end_column_flow_thread_overflow_portion);
304 end_column_rect.Move(FlowThreadTranslationAtOffset(
305 LogicalTopInFlowThreadAt(end_column), LayoutBox::kAssociateWithLatterPage,
306 CoordinateSpaceConversion::kContaining));
307 return UnionRect(start_column_rect, end_column_rect);
308 }
309
CalculateOverflow() const310 LayoutRect MultiColumnFragmentainerGroup::CalculateOverflow() const {
311 // Note that we just return the bounding rectangle of the column boxes here.
312 // We currently don't examine overflow caused by the actual content that ends
313 // up in each column.
314 LayoutRect overflow_rect;
315 if (unsigned column_count = ActualColumnCount()) {
316 overflow_rect = ColumnRectAt(0);
317 if (column_count > 1)
318 overflow_rect.UniteEvenIfEmpty(ColumnRectAt(column_count - 1));
319 }
320 return overflow_rect;
321 }
322
ActualColumnCount() const323 unsigned MultiColumnFragmentainerGroup::ActualColumnCount() const {
324 unsigned count = UnclampedActualColumnCount();
325 count = std::min(count, kColumnCountClampMax);
326 DCHECK_GE(count, 1u);
327 return count;
328 }
329
SetColumnBlockSizeFromNG(LayoutUnit block_size)330 void MultiColumnFragmentainerGroup::SetColumnBlockSizeFromNG(
331 LayoutUnit block_size) {
332 DCHECK(!is_logical_height_known_ || logical_height_ == block_size);
333 logical_height_ = block_size;
334 is_logical_height_known_ = true;
335 }
336
HeightAdjustedForRowOffset(LayoutUnit height) const337 LayoutUnit MultiColumnFragmentainerGroup::HeightAdjustedForRowOffset(
338 LayoutUnit height) const {
339 LayoutUnit adjusted_height =
340 height - LogicalTop() - column_set_->LogicalTopFromMulticolContentEdge();
341 return adjusted_height.ClampNegativeToZero();
342 }
343
CalculateMaxColumnHeight() const344 LayoutUnit MultiColumnFragmentainerGroup::CalculateMaxColumnHeight() const {
345 LayoutMultiColumnFlowThread* flow_thread =
346 column_set_->MultiColumnFlowThread();
347 LayoutUnit max_column_height = flow_thread->MaxColumnLogicalHeight();
348 LayoutUnit max_height = HeightAdjustedForRowOffset(max_column_height);
349 if (FragmentationContext* enclosing_fragmentation_context =
350 flow_thread->EnclosingFragmentationContext()) {
351 if (enclosing_fragmentation_context->IsFragmentainerLogicalHeightKnown()) {
352 // We're nested inside another fragmentation context whose fragmentainer
353 // heights are known. This constrains the max height.
354 LayoutUnit remaining_outer_logical_height =
355 enclosing_fragmentation_context->RemainingLogicalHeightAt(
356 BlockOffsetInEnclosingFragmentationContext());
357 if (max_height > remaining_outer_logical_height)
358 max_height = remaining_outer_logical_height;
359 }
360 }
361 return max_height;
362 }
363
SetAndConstrainColumnHeight(LayoutUnit new_height)364 void MultiColumnFragmentainerGroup::SetAndConstrainColumnHeight(
365 LayoutUnit new_height) {
366 logical_height_ = new_height;
367 if (logical_height_ > max_logical_height_)
368 logical_height_ = max_logical_height_;
369 }
370
RebalanceColumnHeightIfNeeded() const371 LayoutUnit MultiColumnFragmentainerGroup::RebalanceColumnHeightIfNeeded()
372 const {
373 if (ActualColumnCount() <= column_set_->UsedColumnCount()) {
374 // With the current column height, the content fits without creating
375 // overflowing columns. We're done.
376 return logical_height_;
377 }
378
379 if (logical_height_ >= max_logical_height_) {
380 // We cannot stretch any further. We'll just have to live with the
381 // overflowing columns. This typically happens if the max column height is
382 // less than the height of the tallest piece of unbreakable content (e.g.
383 // lines).
384 return logical_height_;
385 }
386
387 MinimumSpaceShortageFinder shortage_finder(
388 ColumnSet(), LogicalTopInFlowThread(), LogicalBottomInFlowThread());
389
390 if (shortage_finder.ForcedBreaksCount() + 1 >=
391 column_set_->UsedColumnCount()) {
392 // Too many forced breaks to allow any implicit breaks. Initial balancing
393 // should already have set a good height. There's nothing more we should do.
394 return logical_height_;
395 }
396
397 // If the initial guessed column height wasn't enough, stretch it now. Stretch
398 // by the lowest amount of space.
399 LayoutUnit min_space_shortage = shortage_finder.MinimumSpaceShortage();
400
401 DCHECK_GT(min_space_shortage, 0); // We should never _shrink_ the height!
402
403 if (min_space_shortage == LayoutUnit::Max()) {
404 // We failed to find an amount to stretch the columns by. This is a bug; see
405 // e.g. crbug.com/510340 . If this happens, though, we need bail out rather
406 // than looping infinitely.
407 return logical_height_;
408 }
409
410 return logical_height_ + min_space_shortage;
411 }
412
ColumnRectAt(unsigned column_index) const413 LayoutRect MultiColumnFragmentainerGroup::ColumnRectAt(
414 unsigned column_index) const {
415 LayoutUnit column_logical_width = column_set_->PageLogicalWidth();
416 LayoutUnit column_logical_height = LogicalHeightInFlowThreadAt(column_index);
417 LayoutUnit column_logical_top;
418 LayoutUnit column_logical_left;
419 LayoutUnit column_gap = column_set_->ColumnGap();
420
421 if (column_set_->StyleRef().IsLeftToRightDirection()) {
422 column_logical_left += column_index * (column_logical_width + column_gap);
423 } else {
424 column_logical_left += column_set_->ContentLogicalWidth() -
425 column_logical_width -
426 column_index * (column_logical_width + column_gap);
427 }
428
429 LayoutRect column_rect(column_logical_left, column_logical_top,
430 column_logical_width, column_logical_height);
431 if (!column_set_->IsHorizontalWritingMode())
432 return column_rect.TransposedRect();
433 return column_rect;
434 }
435
FlowThreadPortionRectAt(unsigned column_index) const436 LayoutRect MultiColumnFragmentainerGroup::FlowThreadPortionRectAt(
437 unsigned column_index) const {
438 LayoutUnit logical_top = LogicalTopInFlowThreadAt(column_index);
439 LayoutUnit portion_logical_height = LogicalHeightInFlowThreadAt(column_index);
440 if (column_set_->IsHorizontalWritingMode()) {
441 return LayoutRect(LayoutUnit(), logical_top,
442 column_set_->PageLogicalWidth(), portion_logical_height);
443 }
444 return LayoutRect(logical_top, LayoutUnit(), portion_logical_height,
445 column_set_->PageLogicalWidth());
446 }
447
FlowThreadPortionOverflowRectAt(unsigned column_index) const448 LayoutRect MultiColumnFragmentainerGroup::FlowThreadPortionOverflowRectAt(
449 unsigned column_index) const {
450 // This function determines the portion of the flow thread that paints for the
451 // column.
452 //
453 // In the block direction, we will not clip overflow out of the top of the
454 // first column, or out of the bottom of the last column. This applies only to
455 // the true first column and last column across all column sets.
456 //
457 // FIXME: Eventually we will know overflow on a per-column basis, but we can't
458 // do this until we have a painting mode that understands not to paint
459 // contents from a previous column in the overflow area of a following column.
460 bool is_first_column_in_row = !column_index;
461 bool is_last_column_in_row = column_index == ActualColumnCount() - 1;
462
463 LayoutRect portion_rect = FlowThreadPortionRectAt(column_index);
464 bool is_first_column_in_multicol_container =
465 is_first_column_in_row &&
466 this == &column_set_->FirstFragmentainerGroup() &&
467 !column_set_->PreviousSiblingMultiColumnSet();
468 bool is_last_column_in_multicol_container =
469 is_last_column_in_row && this == &column_set_->LastFragmentainerGroup() &&
470 !column_set_->NextSiblingMultiColumnSet();
471 // Calculate the overflow rectangle. It will be clipped at the logical top
472 // and bottom of the column box, unless it's the first or last column in the
473 // multicol container, in which case it should allow overflow. It will also
474 // be clipped in the middle of adjacent column gaps. Care is taken here to
475 // avoid rounding errors.
476 LayoutRect overflow_rect(
477 IntRect(-kMulticolMaxClipPixels, -kMulticolMaxClipPixels,
478 2 * kMulticolMaxClipPixels, 2 * kMulticolMaxClipPixels));
479 if (column_set_->IsHorizontalWritingMode()) {
480 if (!is_first_column_in_multicol_container)
481 overflow_rect.ShiftYEdgeTo(portion_rect.Y());
482 if (!is_last_column_in_multicol_container)
483 overflow_rect.ShiftMaxYEdgeTo(portion_rect.MaxY());
484 } else {
485 if (!is_first_column_in_multicol_container)
486 overflow_rect.ShiftXEdgeTo(portion_rect.X());
487 if (!is_last_column_in_multicol_container)
488 overflow_rect.ShiftMaxXEdgeTo(portion_rect.MaxX());
489 }
490 return overflow_rect;
491 }
492
ColumnIndexAtOffset(LayoutUnit offset_in_flow_thread,LayoutBox::PageBoundaryRule page_boundary_rule) const493 unsigned MultiColumnFragmentainerGroup::ColumnIndexAtOffset(
494 LayoutUnit offset_in_flow_thread,
495 LayoutBox::PageBoundaryRule page_boundary_rule) const {
496 // Handle the offset being out of range.
497 if (offset_in_flow_thread < logical_top_in_flow_thread_)
498 return 0;
499
500 if (!IsLogicalHeightKnown())
501 return 0;
502 LayoutUnit column_height = ColumnLogicalHeight();
503 unsigned column_index =
504 ((offset_in_flow_thread - logical_top_in_flow_thread_) / column_height)
505 .Floor();
506 if (page_boundary_rule == LayoutBox::kAssociateWithFormerPage &&
507 column_index > 0 &&
508 LogicalTopInFlowThreadAt(column_index) == offset_in_flow_thread) {
509 // We are exactly at a column boundary, and we've been told to associate
510 // offsets at column boundaries with the former column, not the latter.
511 column_index--;
512 }
513 return column_index;
514 }
515
ConstrainedColumnIndexAtOffset(LayoutUnit offset_in_flow_thread,LayoutBox::PageBoundaryRule page_boundary_rule) const516 unsigned MultiColumnFragmentainerGroup::ConstrainedColumnIndexAtOffset(
517 LayoutUnit offset_in_flow_thread,
518 LayoutBox::PageBoundaryRule page_boundary_rule) const {
519 unsigned index =
520 ColumnIndexAtOffset(offset_in_flow_thread, page_boundary_rule);
521 return std::min(index, ActualColumnCount() - 1);
522 }
523
ColumnIndexAtVisualPoint(const LayoutPoint & visual_point) const524 unsigned MultiColumnFragmentainerGroup::ColumnIndexAtVisualPoint(
525 const LayoutPoint& visual_point) const {
526 LayoutUnit column_length = column_set_->PageLogicalWidth();
527 LayoutUnit offset_in_column_progression_direction =
528 column_set_->IsHorizontalWritingMode() ? visual_point.X()
529 : visual_point.Y();
530 if (!column_set_->StyleRef().IsLeftToRightDirection()) {
531 offset_in_column_progression_direction =
532 column_set_->LogicalWidth() - offset_in_column_progression_direction;
533 }
534 LayoutUnit column_gap = column_set_->ColumnGap();
535 if (column_length + column_gap <= 0)
536 return 0;
537 // Column boundaries are in the middle of the column gap.
538 int index = ((offset_in_column_progression_direction + column_gap / 2) /
539 (column_length + column_gap))
540 .ToInt();
541 if (index < 0)
542 return 0;
543 return std::min(unsigned(index), ActualColumnCount() - 1);
544 }
545
ColumnIntervalForBlockRangeInFlowThread(LayoutUnit logical_top_in_flow_thread,LayoutUnit logical_bottom_in_flow_thread,unsigned & first_column,unsigned & last_column) const546 void MultiColumnFragmentainerGroup::ColumnIntervalForBlockRangeInFlowThread(
547 LayoutUnit logical_top_in_flow_thread,
548 LayoutUnit logical_bottom_in_flow_thread,
549 unsigned& first_column,
550 unsigned& last_column) const {
551 logical_top_in_flow_thread =
552 std::max(logical_top_in_flow_thread, LogicalTopInFlowThread());
553 logical_bottom_in_flow_thread =
554 std::min(logical_bottom_in_flow_thread, LogicalBottomInFlowThread());
555 first_column = ConstrainedColumnIndexAtOffset(
556 logical_top_in_flow_thread, LayoutBox::kAssociateWithLatterPage);
557 if (logical_bottom_in_flow_thread <= logical_top_in_flow_thread) {
558 // Zero-height block range. There'll be one column in the interval. Set it
559 // right away. This is important if we're at a column boundary, since
560 // calling ConstrainedColumnIndexAtOffset() with the end-exclusive bottom
561 // offset would actually give us the *previous* column.
562 last_column = first_column;
563 } else {
564 last_column = ConstrainedColumnIndexAtOffset(
565 logical_bottom_in_flow_thread, LayoutBox::kAssociateWithFormerPage);
566 }
567 }
568
ColumnIntervalForVisualRect(const LayoutRect & rect,unsigned & first_column,unsigned & last_column) const569 void MultiColumnFragmentainerGroup::ColumnIntervalForVisualRect(
570 const LayoutRect& rect,
571 unsigned& first_column,
572 unsigned& last_column) const {
573 bool is_column_ltr = column_set_->StyleRef().IsLeftToRightDirection();
574 if (column_set_->IsHorizontalWritingMode()) {
575 if (is_column_ltr) {
576 first_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
577 last_column = ColumnIndexAtVisualPoint(rect.MaxXMinYCorner());
578 } else {
579 first_column = ColumnIndexAtVisualPoint(rect.MaxXMinYCorner());
580 last_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
581 }
582 } else {
583 if (is_column_ltr) {
584 first_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
585 last_column = ColumnIndexAtVisualPoint(rect.MinXMaxYCorner());
586 } else {
587 first_column = ColumnIndexAtVisualPoint(rect.MinXMaxYCorner());
588 last_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
589 }
590 }
591 DCHECK_LE(first_column, last_column);
592 }
593
UnclampedActualColumnCount() const594 unsigned MultiColumnFragmentainerGroup::UnclampedActualColumnCount() const {
595 // We must always return a value of 1 or greater. Column count = 0 is a
596 // meaningless situation, and will confuse and cause problems in other parts
597 // of the code.
598 if (!IsLogicalHeightKnown())
599 return 1;
600 // Our flow thread portion determines our column count. We have as many
601 // columns as needed to fit all the content.
602 LayoutUnit flow_thread_portion_height = LogicalHeightInFlowThread();
603 if (!flow_thread_portion_height)
604 return 1;
605
606 LayoutUnit column_height = ColumnLogicalHeight();
607 unsigned count = (flow_thread_portion_height / column_height).Floor();
608 // flowThreadPortionHeight may be saturated, so detect the remainder manually.
609 if (count * column_height < flow_thread_portion_height)
610 count++;
611
612 DCHECK_GE(count, 1u);
613 return count;
614 }
615
MultiColumnFragmentainerGroupList(LayoutMultiColumnSet & column_set)616 MultiColumnFragmentainerGroupList::MultiColumnFragmentainerGroupList(
617 LayoutMultiColumnSet& column_set)
618 : column_set_(column_set) {
619 Append(MultiColumnFragmentainerGroup(column_set_));
620 }
621
622 // An explicit empty destructor of MultiColumnFragmentainerGroupList should be
623 // in MultiColumnFragmentainerGroup.cpp, because if an implicit destructor is
624 // used, msvc 2015 tries to generate its destructor (because the class is
625 // dll-exported class) and causes a compile error because of lack of
626 // MultiColumnFragmentainerGroup::operator=. Since
627 // MultiColumnFragmentainerGroup is non-copyable, we cannot define the
628 // operator=.
629 MultiColumnFragmentainerGroupList::~MultiColumnFragmentainerGroupList() =
630 default;
631
632 MultiColumnFragmentainerGroup&
AddExtraGroup()633 MultiColumnFragmentainerGroupList::AddExtraGroup() {
634 Append(MultiColumnFragmentainerGroup(column_set_));
635 return Last();
636 }
637
DeleteExtraGroups()638 void MultiColumnFragmentainerGroupList::DeleteExtraGroups() {
639 Shrink(1);
640 }
641
642 } // namespace blink
643