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
UpdateFromNG(LayoutUnit logical_height)330 void MultiColumnFragmentainerGroup::UpdateFromNG(LayoutUnit logical_height) {
331 logical_height_ = logical_height;
332 is_logical_height_known_ = true;
333 }
334
HeightAdjustedForRowOffset(LayoutUnit height) const335 LayoutUnit MultiColumnFragmentainerGroup::HeightAdjustedForRowOffset(
336 LayoutUnit height) const {
337 LayoutUnit adjusted_height =
338 height - LogicalTop() - column_set_.LogicalTopFromMulticolContentEdge();
339 return adjusted_height.ClampNegativeToZero();
340 }
341
CalculateMaxColumnHeight() const342 LayoutUnit MultiColumnFragmentainerGroup::CalculateMaxColumnHeight() const {
343 LayoutMultiColumnFlowThread* flow_thread =
344 column_set_.MultiColumnFlowThread();
345 LayoutUnit max_column_height = flow_thread->MaxColumnLogicalHeight();
346 LayoutUnit max_height = HeightAdjustedForRowOffset(max_column_height);
347 if (FragmentationContext* enclosing_fragmentation_context =
348 flow_thread->EnclosingFragmentationContext()) {
349 if (enclosing_fragmentation_context->IsFragmentainerLogicalHeightKnown()) {
350 // We're nested inside another fragmentation context whose fragmentainer
351 // heights are known. This constrains the max height.
352 LayoutUnit remaining_outer_logical_height =
353 enclosing_fragmentation_context->RemainingLogicalHeightAt(
354 BlockOffsetInEnclosingFragmentationContext());
355 if (max_height > remaining_outer_logical_height)
356 max_height = remaining_outer_logical_height;
357 }
358 }
359 return max_height;
360 }
361
SetAndConstrainColumnHeight(LayoutUnit new_height)362 void MultiColumnFragmentainerGroup::SetAndConstrainColumnHeight(
363 LayoutUnit new_height) {
364 logical_height_ = new_height;
365 if (logical_height_ > max_logical_height_)
366 logical_height_ = max_logical_height_;
367 }
368
RebalanceColumnHeightIfNeeded() const369 LayoutUnit MultiColumnFragmentainerGroup::RebalanceColumnHeightIfNeeded()
370 const {
371 if (ActualColumnCount() <= column_set_.UsedColumnCount()) {
372 // With the current column height, the content fits without creating
373 // overflowing columns. We're done.
374 return logical_height_;
375 }
376
377 if (logical_height_ >= max_logical_height_) {
378 // We cannot stretch any further. We'll just have to live with the
379 // overflowing columns. This typically happens if the max column height is
380 // less than the height of the tallest piece of unbreakable content (e.g.
381 // lines).
382 return logical_height_;
383 }
384
385 MinimumSpaceShortageFinder shortage_finder(
386 ColumnSet(), LogicalTopInFlowThread(), LogicalBottomInFlowThread());
387
388 if (shortage_finder.ForcedBreaksCount() + 1 >=
389 column_set_.UsedColumnCount()) {
390 // Too many forced breaks to allow any implicit breaks. Initial balancing
391 // should already have set a good height. There's nothing more we should do.
392 return logical_height_;
393 }
394
395 // If the initial guessed column height wasn't enough, stretch it now. Stretch
396 // by the lowest amount of space.
397 LayoutUnit min_space_shortage = shortage_finder.MinimumSpaceShortage();
398
399 DCHECK_GT(min_space_shortage, 0); // We should never _shrink_ the height!
400
401 if (min_space_shortage == LayoutUnit::Max()) {
402 // We failed to find an amount to stretch the columns by. This is a bug; see
403 // e.g. crbug.com/510340 . If this happens, though, we need bail out rather
404 // than looping infinitely.
405 return logical_height_;
406 }
407
408 return logical_height_ + min_space_shortage;
409 }
410
ColumnRectAt(unsigned column_index) const411 LayoutRect MultiColumnFragmentainerGroup::ColumnRectAt(
412 unsigned column_index) const {
413 LayoutUnit column_logical_width = column_set_.PageLogicalWidth();
414 LayoutUnit column_logical_height = LogicalHeightInFlowThreadAt(column_index);
415 LayoutUnit column_logical_top;
416 LayoutUnit column_logical_left;
417 LayoutUnit column_gap = column_set_.ColumnGap();
418
419 if (column_set_.StyleRef().IsLeftToRightDirection()) {
420 column_logical_left += column_index * (column_logical_width + column_gap);
421 } else {
422 column_logical_left += column_set_.ContentLogicalWidth() -
423 column_logical_width -
424 column_index * (column_logical_width + column_gap);
425 }
426
427 LayoutRect column_rect(column_logical_left, column_logical_top,
428 column_logical_width, column_logical_height);
429 if (!column_set_.IsHorizontalWritingMode())
430 return column_rect.TransposedRect();
431 return column_rect;
432 }
433
FlowThreadPortionRectAt(unsigned column_index) const434 LayoutRect MultiColumnFragmentainerGroup::FlowThreadPortionRectAt(
435 unsigned column_index) const {
436 LayoutUnit logical_top = LogicalTopInFlowThreadAt(column_index);
437 LayoutUnit portion_logical_height = LogicalHeightInFlowThreadAt(column_index);
438 if (column_set_.IsHorizontalWritingMode())
439 return LayoutRect(LayoutUnit(), logical_top, column_set_.PageLogicalWidth(),
440 portion_logical_height);
441 return LayoutRect(logical_top, LayoutUnit(), portion_logical_height,
442 column_set_.PageLogicalWidth());
443 }
444
FlowThreadPortionOverflowRectAt(unsigned column_index) const445 LayoutRect MultiColumnFragmentainerGroup::FlowThreadPortionOverflowRectAt(
446 unsigned column_index) const {
447 // This function determines the portion of the flow thread that paints for the
448 // column.
449 //
450 // In the block direction, we will not clip overflow out of the top of the
451 // first column, or out of the bottom of the last column. This applies only to
452 // the true first column and last column across all column sets.
453 //
454 // FIXME: Eventually we will know overflow on a per-column basis, but we can't
455 // do this until we have a painting mode that understands not to paint
456 // contents from a previous column in the overflow area of a following column.
457 bool is_first_column_in_row = !column_index;
458 bool is_last_column_in_row = column_index == ActualColumnCount() - 1;
459
460 LayoutRect portion_rect = FlowThreadPortionRectAt(column_index);
461 bool is_first_column_in_multicol_container =
462 is_first_column_in_row &&
463 this == &column_set_.FirstFragmentainerGroup() &&
464 !column_set_.PreviousSiblingMultiColumnSet();
465 bool is_last_column_in_multicol_container =
466 is_last_column_in_row && this == &column_set_.LastFragmentainerGroup() &&
467 !column_set_.NextSiblingMultiColumnSet();
468 // Calculate the overflow rectangle. It will be clipped at the logical top
469 // and bottom of the column box, unless it's the first or last column in the
470 // multicol container, in which case it should allow overflow. It will also
471 // be clipped in the middle of adjacent column gaps. Care is taken here to
472 // avoid rounding errors.
473 LayoutRect overflow_rect(
474 IntRect(-kMulticolMaxClipPixels, -kMulticolMaxClipPixels,
475 2 * kMulticolMaxClipPixels, 2 * kMulticolMaxClipPixels));
476 if (column_set_.IsHorizontalWritingMode()) {
477 if (!is_first_column_in_multicol_container)
478 overflow_rect.ShiftYEdgeTo(portion_rect.Y());
479 if (!is_last_column_in_multicol_container)
480 overflow_rect.ShiftMaxYEdgeTo(portion_rect.MaxY());
481 } else {
482 if (!is_first_column_in_multicol_container)
483 overflow_rect.ShiftXEdgeTo(portion_rect.X());
484 if (!is_last_column_in_multicol_container)
485 overflow_rect.ShiftMaxXEdgeTo(portion_rect.MaxX());
486 }
487 return overflow_rect;
488 }
489
ColumnIndexAtOffset(LayoutUnit offset_in_flow_thread,LayoutBox::PageBoundaryRule page_boundary_rule) const490 unsigned MultiColumnFragmentainerGroup::ColumnIndexAtOffset(
491 LayoutUnit offset_in_flow_thread,
492 LayoutBox::PageBoundaryRule page_boundary_rule) const {
493 // Handle the offset being out of range.
494 if (offset_in_flow_thread < logical_top_in_flow_thread_)
495 return 0;
496
497 if (!IsLogicalHeightKnown())
498 return 0;
499 LayoutUnit column_height = ColumnLogicalHeight();
500 unsigned column_index =
501 ((offset_in_flow_thread - logical_top_in_flow_thread_) / column_height)
502 .Floor();
503 if (page_boundary_rule == LayoutBox::kAssociateWithFormerPage &&
504 column_index > 0 &&
505 LogicalTopInFlowThreadAt(column_index) == offset_in_flow_thread) {
506 // We are exactly at a column boundary, and we've been told to associate
507 // offsets at column boundaries with the former column, not the latter.
508 column_index--;
509 }
510 return column_index;
511 }
512
ConstrainedColumnIndexAtOffset(LayoutUnit offset_in_flow_thread,LayoutBox::PageBoundaryRule page_boundary_rule) const513 unsigned MultiColumnFragmentainerGroup::ConstrainedColumnIndexAtOffset(
514 LayoutUnit offset_in_flow_thread,
515 LayoutBox::PageBoundaryRule page_boundary_rule) const {
516 unsigned index =
517 ColumnIndexAtOffset(offset_in_flow_thread, page_boundary_rule);
518 return std::min(index, ActualColumnCount() - 1);
519 }
520
ColumnIndexAtVisualPoint(const LayoutPoint & visual_point) const521 unsigned MultiColumnFragmentainerGroup::ColumnIndexAtVisualPoint(
522 const LayoutPoint& visual_point) const {
523 LayoutUnit column_length = column_set_.PageLogicalWidth();
524 LayoutUnit offset_in_column_progression_direction =
525 column_set_.IsHorizontalWritingMode() ? visual_point.X()
526 : visual_point.Y();
527 if (!column_set_.StyleRef().IsLeftToRightDirection()) {
528 offset_in_column_progression_direction =
529 column_set_.LogicalWidth() - offset_in_column_progression_direction;
530 }
531 LayoutUnit column_gap = column_set_.ColumnGap();
532 if (column_length + column_gap <= 0)
533 return 0;
534 // Column boundaries are in the middle of the column gap.
535 int index = ((offset_in_column_progression_direction + column_gap / 2) /
536 (column_length + column_gap))
537 .ToInt();
538 if (index < 0)
539 return 0;
540 return std::min(unsigned(index), ActualColumnCount() - 1);
541 }
542
ColumnIntervalForBlockRangeInFlowThread(LayoutUnit logical_top_in_flow_thread,LayoutUnit logical_bottom_in_flow_thread,unsigned & first_column,unsigned & last_column) const543 void MultiColumnFragmentainerGroup::ColumnIntervalForBlockRangeInFlowThread(
544 LayoutUnit logical_top_in_flow_thread,
545 LayoutUnit logical_bottom_in_flow_thread,
546 unsigned& first_column,
547 unsigned& last_column) const {
548 logical_top_in_flow_thread =
549 std::max(logical_top_in_flow_thread, LogicalTopInFlowThread());
550 logical_bottom_in_flow_thread =
551 std::min(logical_bottom_in_flow_thread, LogicalBottomInFlowThread());
552 first_column = ConstrainedColumnIndexAtOffset(
553 logical_top_in_flow_thread, LayoutBox::kAssociateWithLatterPage);
554 if (logical_bottom_in_flow_thread <= logical_top_in_flow_thread) {
555 // Zero-height block range. There'll be one column in the interval. Set it
556 // right away. This is important if we're at a column boundary, since
557 // calling ConstrainedColumnIndexAtOffset() with the end-exclusive bottom
558 // offset would actually give us the *previous* column.
559 last_column = first_column;
560 } else {
561 last_column = ConstrainedColumnIndexAtOffset(
562 logical_bottom_in_flow_thread, LayoutBox::kAssociateWithFormerPage);
563 }
564 }
565
ColumnIntervalForVisualRect(const LayoutRect & rect,unsigned & first_column,unsigned & last_column) const566 void MultiColumnFragmentainerGroup::ColumnIntervalForVisualRect(
567 const LayoutRect& rect,
568 unsigned& first_column,
569 unsigned& last_column) const {
570 bool is_column_ltr = column_set_.StyleRef().IsLeftToRightDirection();
571 if (column_set_.IsHorizontalWritingMode()) {
572 if (is_column_ltr) {
573 first_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
574 last_column = ColumnIndexAtVisualPoint(rect.MaxXMinYCorner());
575 } else {
576 first_column = ColumnIndexAtVisualPoint(rect.MaxXMinYCorner());
577 last_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
578 }
579 } else {
580 if (is_column_ltr) {
581 first_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
582 last_column = ColumnIndexAtVisualPoint(rect.MinXMaxYCorner());
583 } else {
584 first_column = ColumnIndexAtVisualPoint(rect.MinXMaxYCorner());
585 last_column = ColumnIndexAtVisualPoint(rect.MinXMinYCorner());
586 }
587 }
588 DCHECK_LE(first_column, last_column);
589 }
590
UnclampedActualColumnCount() const591 unsigned MultiColumnFragmentainerGroup::UnclampedActualColumnCount() const {
592 // We must always return a value of 1 or greater. Column count = 0 is a
593 // meaningless situation, and will confuse and cause problems in other parts
594 // of the code.
595 if (!IsLogicalHeightKnown())
596 return 1;
597 // Our flow thread portion determines our column count. We have as many
598 // columns as needed to fit all the content.
599 LayoutUnit flow_thread_portion_height = LogicalHeightInFlowThread();
600 if (!flow_thread_portion_height)
601 return 1;
602
603 LayoutUnit column_height = ColumnLogicalHeight();
604 unsigned count = (flow_thread_portion_height / column_height).Floor();
605 // flowThreadPortionHeight may be saturated, so detect the remainder manually.
606 if (count * column_height < flow_thread_portion_height)
607 count++;
608
609 DCHECK_GE(count, 1u);
610 return count;
611 }
612
MultiColumnFragmentainerGroupList(LayoutMultiColumnSet & column_set)613 MultiColumnFragmentainerGroupList::MultiColumnFragmentainerGroupList(
614 LayoutMultiColumnSet& column_set)
615 : column_set_(column_set) {
616 Append(MultiColumnFragmentainerGroup(column_set_));
617 }
618
619 // An explicit empty destructor of MultiColumnFragmentainerGroupList should be
620 // in MultiColumnFragmentainerGroup.cpp, because if an implicit destructor is
621 // used, msvc 2015 tries to generate its destructor (because the class is
622 // dll-exported class) and causes a compile error because of lack of
623 // MultiColumnFragmentainerGroup::operator=. Since
624 // MultiColumnFragmentainerGroup is non-copyable, we cannot define the
625 // operator=.
626 MultiColumnFragmentainerGroupList::~MultiColumnFragmentainerGroupList() =
627 default;
628
629 MultiColumnFragmentainerGroup&
AddExtraGroup()630 MultiColumnFragmentainerGroupList::AddExtraGroup() {
631 Append(MultiColumnFragmentainerGroup(column_set_));
632 return Last();
633 }
634
DeleteExtraGroups()635 void MultiColumnFragmentainerGroupList::DeleteExtraGroups() {
636 Shrink(1);
637 }
638
639 } // namespace blink
640