| // Copyright 2015 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "core/layout/ColumnBalancer.h" |
| |
| #include "core/layout/LayoutMultiColumnFlowThread.h" |
| #include "core/layout/LayoutMultiColumnSet.h" |
| #include "core/layout/api/LineLayoutBlockFlow.h" |
| |
| namespace blink { |
| |
| ColumnBalancer::ColumnBalancer(const LayoutMultiColumnSet& column_set, |
| LayoutUnit logical_top_in_flow_thread, |
| LayoutUnit logical_bottom_in_flow_thread) |
| : column_set_(column_set), |
| logical_top_in_flow_thread_(logical_top_in_flow_thread), |
| logical_bottom_in_flow_thread_(logical_bottom_in_flow_thread) { |
| DCHECK_GE(column_set.UsedColumnCount(), 1U); |
| } |
| |
| void ColumnBalancer::Traverse() { |
| TraverseSubtree(*ColumnSet().FlowThread()); |
| DCHECK(!FlowThreadOffset()); |
| } |
| |
| void ColumnBalancer::TraverseSubtree(const LayoutBox& box) { |
| if (box.ChildrenInline() && box.IsLayoutBlockFlow()) { |
| // Look for breaks between lines. |
| TraverseLines(ToLayoutBlockFlow(box)); |
| } |
| |
| // Look for breaks between and inside block-level children. Even if this is a |
| // block flow with inline children, there may be interesting floats to examine |
| // here. |
| TraverseChildren(box); |
| } |
| |
| void ColumnBalancer::TraverseLines(const LayoutBlockFlow& block_flow) { |
| for (const RootInlineBox* line = block_flow.FirstRootBox(); line; |
| line = line->NextRootBox()) { |
| LayoutUnit line_top_in_flow_thread = |
| flow_thread_offset_ + line->LineTopWithLeading(); |
| if (line_top_in_flow_thread < LogicalTopInFlowThread()) { |
| // If the line is fully about the flow thread portion range we're working |
| // with, we can skip it. If its logical top is outside the range, but its |
| // logical bottom protrudes into the range, we need to examine it. |
| LayoutUnit line_bottom = line->LineBottomWithLeading(); |
| if (flow_thread_offset_ + line_bottom <= LogicalTopInFlowThread()) |
| continue; |
| } |
| if (line_top_in_flow_thread >= LogicalBottomInFlowThread()) |
| break; |
| ExamineLine(*line); |
| } |
| } |
| |
| void ColumnBalancer::TraverseChildren(const LayoutObject& object) { |
| // The break-after value from the previous in-flow block-level object to be |
| // joined with the break-before value of the next in-flow block-level sibling. |
| EBreakBetween previous_break_after_value = EBreakBetween::kAuto; |
| |
| for (const LayoutObject* child = object.SlowFirstChild(); child; |
| child = child->NextSibling()) { |
| if (!child->IsBox()) { |
| // Keep traversing inside inlines. There may be floats there. |
| if (child->IsLayoutInline()) |
| TraverseChildren(*child); |
| continue; |
| } |
| |
| const LayoutBox& child_box = ToLayoutBox(*child); |
| |
| LayoutUnit border_edge_offset; |
| LayoutUnit logical_top = child_box.LogicalTop(); |
| LayoutUnit logical_height = child_box.LogicalHeightWithVisibleOverflow(); |
| // Floats' margins don't collapse with column boundaries, and we don't want |
| // to break inside them, or separate them from the float's border box. Set |
| // the offset to the margin-before edge (rather than border-before edge), |
| // and include the block direction margins in the child height. |
| if (child_box.IsFloating()) { |
| LayoutUnit margin_before = child_box.MarginBefore(object.Style()); |
| LayoutUnit margin_after = child_box.MarginAfter(object.Style()); |
| logical_height = |
| std::max(logical_height, child_box.LogicalHeight() + margin_after); |
| logical_top -= margin_before; |
| logical_height += margin_before; |
| |
| // As soon as we want to process content inside this child, though, we |
| // need to get to its border-before edge. |
| border_edge_offset = margin_before; |
| } |
| |
| if (flow_thread_offset_ + logical_top + logical_height <= |
| LogicalTopInFlowThread()) { |
| // This child is fully above the flow thread portion we're examining. |
| continue; |
| } |
| if (flow_thread_offset_ + logical_top >= LogicalBottomInFlowThread()) { |
| // This child is fully below the flow thread portion we're examining. We |
| // cannot just stop here, though, thanks to negative margins. |
| // So keep looking. |
| continue; |
| } |
| if (child_box.IsOutOfFlowPositioned() || child_box.IsColumnSpanAll()) |
| continue; |
| |
| // Tables are wicked. Both table rows and table cells are relative to their |
| // table section. |
| LayoutUnit offset_for_this_child = |
| child_box.IsTableRow() ? LayoutUnit() : logical_top; |
| |
| flow_thread_offset_ += offset_for_this_child; |
| |
| ExamineBoxAfterEntering(child_box, logical_height, |
| previous_break_after_value); |
| // Unless the child is unsplittable, or if the child establishes an inner |
| // multicol container, we descend into its subtree for further examination. |
| if (child_box.GetPaginationBreakability() != LayoutBox::kForbidBreaks && |
| (!child_box.IsLayoutBlockFlow() || |
| !ToLayoutBlockFlow(child_box).MultiColumnFlowThread())) { |
| // We need to get to the border edge before processing content inside |
| // this child. If the child is floated, we're currently at the margin |
| // edge. |
| flow_thread_offset_ += border_edge_offset; |
| TraverseSubtree(child_box); |
| flow_thread_offset_ -= border_edge_offset; |
| } |
| previous_break_after_value = child_box.BreakAfter(); |
| ExamineBoxBeforeLeaving(child_box, logical_height); |
| |
| flow_thread_offset_ -= offset_for_this_child; |
| } |
| } |
| |
| InitialColumnHeightFinder::InitialColumnHeightFinder( |
| const LayoutMultiColumnSet& column_set, |
| LayoutUnit logical_top_in_flow_thread, |
| LayoutUnit logical_bottom_in_flow_thread) |
| : ColumnBalancer(column_set, |
| logical_top_in_flow_thread, |
| logical_bottom_in_flow_thread) { |
| shortest_struts_.resize(column_set.UsedColumnCount()); |
| for (auto& strut : shortest_struts_) |
| strut = LayoutUnit::Max(); |
| Traverse(); |
| // We have now found each explicit / forced break, and their location. Now we |
| // need to figure out how many additional implicit / soft breaks we need and |
| // guess where they will occur, in order |
| // to provide an initial column height. |
| DistributeImplicitBreaks(); |
| } |
| |
| LayoutUnit InitialColumnHeightFinder::InitialMinimalBalancedHeight() const { |
| LayoutUnit row_logical_top; |
| if (content_runs_.size() > ColumnSet().UsedColumnCount()) { |
| // We have not inserted additional fragmentainer groups yet (because we |
| // aren't able to calculate their constraints yet), but we already know for |
| // sure that there'll be more than one of them, due to the number of forced |
| // breaks in a nested multicol container. We will now attempt to take all |
| // the imaginary rows into account and calculate a minimal balanced logical |
| // height for everything. |
| unsigned stride = ColumnSet().UsedColumnCount(); |
| LayoutUnit row_start_offset = LogicalTopInFlowThread(); |
| for (unsigned i = 0; i < FirstContentRunIndexInLastRow(); i += stride) { |
| LayoutUnit row_end_offset = content_runs_[i + stride - 1].BreakOffset(); |
| float row_height = |
| float(row_end_offset - row_start_offset) / float(stride); |
| row_logical_top += LayoutUnit::FromFloatCeil(row_height); |
| row_start_offset = row_end_offset; |
| } |
| } |
| unsigned index = ContentRunIndexWithTallestColumns(); |
| LayoutUnit start_offset = index > 0 ? content_runs_[index - 1].BreakOffset() |
| : LogicalTopInFlowThread(); |
| LayoutUnit height = content_runs_[index].ColumnLogicalHeight(start_offset); |
| return row_logical_top + |
| std::max(height, tallest_unbreakable_logical_height_); |
| } |
| |
| void InitialColumnHeightFinder::ExamineBoxAfterEntering( |
| const LayoutBox& box, |
| LayoutUnit child_logical_height, |
| EBreakBetween previous_break_after_value) { |
| if (last_break_seen_ > FlowThreadOffset()) { |
| // We have moved backwards. We're probably in a parallel flow, caused by |
| // floats, sibling table cells, etc. |
| last_break_seen_ = LayoutUnit(); |
| } |
| if (IsLogicalTopWithinBounds(FlowThreadOffset() - box.PaginationStrut())) { |
| if (box.NeedsForcedBreakBefore(previous_break_after_value)) { |
| AddContentRun(FlowThreadOffset()); |
| } else if (IsFirstAfterBreak(FlowThreadOffset()) && |
| last_break_seen_ != FlowThreadOffset()) { |
| // This box is first after a soft break. |
| last_break_seen_ = FlowThreadOffset(); |
| RecordStrutBeforeOffset(FlowThreadOffset(), box.PaginationStrut()); |
| } |
| } |
| |
| if (box.GetPaginationBreakability() != LayoutBox::kAllowAnyBreaks) { |
| tallest_unbreakable_logical_height_ = |
| std::max(tallest_unbreakable_logical_height_, child_logical_height); |
| return; |
| } |
| // Need to examine inner multicol containers to find their tallest unbreakable |
| // piece of content. |
| if (!box.IsLayoutBlockFlow()) |
| return; |
| LayoutMultiColumnFlowThread* inner_flow_thread = |
| ToLayoutBlockFlow(box).MultiColumnFlowThread(); |
| if (!inner_flow_thread || inner_flow_thread->IsLayoutPagedFlowThread()) |
| return; |
| LayoutUnit offset_in_inner_flow_thread = |
| FlowThreadOffset() - |
| inner_flow_thread->BlockOffsetInEnclosingFragmentationContext(); |
| LayoutUnit inner_unbreakable_height = |
| inner_flow_thread->TallestUnbreakableLogicalHeight( |
| offset_in_inner_flow_thread); |
| tallest_unbreakable_logical_height_ = |
| std::max(tallest_unbreakable_logical_height_, inner_unbreakable_height); |
| } |
| |
| void InitialColumnHeightFinder::ExamineBoxBeforeLeaving( |
| const LayoutBox& box, |
| LayoutUnit child_logical_height) {} |
| |
| static inline LayoutUnit ColumnLogicalHeightRequirementForLine( |
| const ComputedStyle& style, |
| const RootInlineBox& last_line) { |
| // We may require a certain minimum number of lines per page in order to |
| // satisfy orphans and widows, and that may affect the minimum page height. |
| unsigned minimum_line_count = |
| std::max<unsigned>(style.Orphans(), style.Widows()); |
| const RootInlineBox* first_line = &last_line; |
| for (unsigned i = 1; i < minimum_line_count && first_line->PrevRootBox(); i++) |
| first_line = first_line->PrevRootBox(); |
| return last_line.LineBottomWithLeading() - first_line->LineTopWithLeading(); |
| } |
| |
| void InitialColumnHeightFinder::ExamineLine(const RootInlineBox& line) { |
| LayoutUnit line_top = line.LineTopWithLeading(); |
| LayoutUnit line_top_in_flow_thread = FlowThreadOffset() + line_top; |
| LayoutUnit minimum_logial_height = |
| ColumnLogicalHeightRequirementForLine(line.Block().StyleRef(), line); |
| if (line_top_in_flow_thread < LayoutUnit()) |
| minimum_logial_height += line_top_in_flow_thread; |
| tallest_unbreakable_logical_height_ = |
| std::max(tallest_unbreakable_logical_height_, minimum_logial_height); |
| if (IsFirstAfterBreak(line_top_in_flow_thread) && |
| last_break_seen_ != line_top_in_flow_thread) { |
| last_break_seen_ = line_top_in_flow_thread; |
| RecordStrutBeforeOffset(line_top_in_flow_thread, line.PaginationStrut()); |
| } |
| } |
| |
| void InitialColumnHeightFinder::RecordStrutBeforeOffset( |
| LayoutUnit offset_in_flow_thread, |
| LayoutUnit strut) { |
| unsigned column_count = ColumnSet().UsedColumnCount(); |
| DCHECK_EQ(shortest_struts_.size(), column_count); |
| unsigned index = |
| GroupAtOffset(offset_in_flow_thread) |
| .ColumnIndexAtOffset(offset_in_flow_thread - strut, |
| LayoutBox::kAssociateWithFormerPage); |
| if (index >= column_count) |
| return; |
| shortest_struts_[index] = std::min(shortest_struts_[index], strut); |
| } |
| |
| LayoutUnit InitialColumnHeightFinder::SpaceUsedByStrutsAt( |
| LayoutUnit offset_in_flow_thread) const { |
| unsigned stop_before_column = |
| GroupAtOffset(offset_in_flow_thread) |
| .ColumnIndexAtOffset(offset_in_flow_thread, |
| LayoutBox::kAssociateWithLatterPage) + |
| 1; |
| stop_before_column = |
| std::min(stop_before_column, ColumnSet().UsedColumnCount()); |
| DCHECK_LE(stop_before_column, shortest_struts_.size()); |
| LayoutUnit total_strut_space; |
| for (unsigned i = 0; i < stop_before_column; i++) { |
| if (shortest_struts_[i] != LayoutUnit::Max()) |
| total_strut_space += shortest_struts_[i]; |
| } |
| return total_strut_space; |
| } |
| |
| void InitialColumnHeightFinder::AddContentRun( |
| LayoutUnit end_offset_in_flow_thread) { |
| end_offset_in_flow_thread -= SpaceUsedByStrutsAt(end_offset_in_flow_thread); |
| if (!content_runs_.IsEmpty() && |
| end_offset_in_flow_thread <= content_runs_.back().BreakOffset()) |
| return; |
| // Append another item as long as we haven't exceeded used column count. What |
| // ends up in the overflow area shouldn't affect column balancing. However, if |
| // we're in a nested fragmentation context, we may still need to record all |
| // runs, since there'll be no overflow area in the inline direction then, but |
| // rather additional rows of columns in multiple outer fragmentainers. |
| if (content_runs_.size() >= ColumnSet().UsedColumnCount()) { |
| const auto* flow_thread = ColumnSet().MultiColumnFlowThread(); |
| if (!flow_thread->EnclosingFragmentationContext() || |
| ColumnSet().NewFragmentainerGroupsAllowed()) |
| return; |
| } |
| content_runs_.push_back(ContentRun(end_offset_in_flow_thread)); |
| } |
| |
| unsigned InitialColumnHeightFinder::ContentRunIndexWithTallestColumns() const { |
| unsigned index_with_largest_height = 0; |
| LayoutUnit largest_height; |
| LayoutUnit previous_offset = LogicalTopInFlowThread(); |
| size_t run_count = content_runs_.size(); |
| DCHECK(run_count); |
| for (size_t i = FirstContentRunIndexInLastRow(); i < run_count; i++) { |
| const ContentRun& run = content_runs_[i]; |
| LayoutUnit height = run.ColumnLogicalHeight(previous_offset); |
| if (largest_height < height) { |
| largest_height = height; |
| index_with_largest_height = i; |
| } |
| previous_offset = run.BreakOffset(); |
| } |
| return index_with_largest_height; |
| } |
| |
| void InitialColumnHeightFinder::DistributeImplicitBreaks() { |
| // Insert a final content run to encompass all content. This will include |
| // overflow if we're at the end of the multicol container. |
| AddContentRun(LogicalBottomInFlowThread()); |
| unsigned column_count = content_runs_.size(); |
| |
| // If there is room for more breaks (to reach the used value of column-count), |
| // imagine that we insert implicit breaks at suitable locations. At any given |
| // time, the content run with the currently tallest columns will get another |
| // implicit break "inserted", which will increase its column count by one and |
| // shrink its columns' height. Repeat until we have the desired total number |
| // of breaks. The largest column height among the runs will then be the |
| // initial column height for the balancer to use. |
| if (column_count > ColumnSet().UsedColumnCount()) { |
| // If we exceed used column-count (which we are allowed to do if we're at |
| // the initial balancing pass for a multicol that lives inside another |
| // to-be-balanced outer multicol container), we only care about content that |
| // could end up in the last row. We need to pad up the number of columns, so |
| // that all rows will contain as many columns as used column-count dictates. |
| column_count %= ColumnSet().UsedColumnCount(); |
| // If there are just enough explicit breaks to fill all rows with the right |
| // amount of columns, we won't be needing any implicit breaks. |
| if (!column_count) |
| return; |
| } |
| while (column_count < ColumnSet().UsedColumnCount()) { |
| unsigned index = ContentRunIndexWithTallestColumns(); |
| content_runs_[index].AssumeAnotherImplicitBreak(); |
| column_count++; |
| } |
| } |
| |
| MinimumSpaceShortageFinder::MinimumSpaceShortageFinder( |
| const LayoutMultiColumnSet& column_set, |
| LayoutUnit logical_top_in_flow_thread, |
| LayoutUnit logical_bottom_in_flow_thread) |
| : ColumnBalancer(column_set, |
| logical_top_in_flow_thread, |
| logical_bottom_in_flow_thread), |
| minimum_space_shortage_(LayoutUnit::Max()), |
| pending_strut_(LayoutUnit::Min()), |
| forced_breaks_count_(0) { |
| Traverse(); |
| } |
| |
| void MinimumSpaceShortageFinder::ExamineBoxAfterEntering( |
| const LayoutBox& box, |
| LayoutUnit child_logical_height, |
| EBreakBetween previous_break_after_value) { |
| LayoutBox::PaginationBreakability breakability = |
| box.GetPaginationBreakability(); |
| |
| // Look for breaks before the child box. |
| if (IsLogicalTopWithinBounds(FlowThreadOffset() - box.PaginationStrut())) { |
| if (box.NeedsForcedBreakBefore(previous_break_after_value)) { |
| forced_breaks_count_++; |
| } else { |
| if (IsFirstAfterBreak(FlowThreadOffset())) { |
| // This box is first after a soft break. |
| LayoutUnit strut = box.PaginationStrut(); |
| // Figure out how much more space we would need to prevent it from being |
| // pushed to the next column. |
| RecordSpaceShortage(child_logical_height - strut); |
| if (breakability != LayoutBox::kForbidBreaks && |
| pending_strut_ == LayoutUnit::Min()) { |
| // We now want to look for the first piece of unbreakable content |
| // (e.g. a line or a block-displayed image) inside this block. That |
| // ought to be a good candidate for minimum space shortage; a much |
| // better one than reporting space shortage for the entire block |
| // (which we'll also do (further down), in case we couldn't find |
| // anything more suitable). |
| pending_strut_ = strut; |
| } |
| } |
| } |
| } |
| |
| if (breakability != LayoutBox::kForbidBreaks) { |
| // See if this breakable box crosses column boundaries. |
| LayoutUnit bottom_in_flow_thread = |
| FlowThreadOffset() + child_logical_height; |
| const MultiColumnFragmentainerGroup& group = |
| GroupAtOffset(FlowThreadOffset()); |
| if (IsFirstAfterBreak(FlowThreadOffset()) || |
| group.ColumnLogicalTopForOffset(FlowThreadOffset()) != |
| group.ColumnLogicalTopForOffset(bottom_in_flow_thread)) { |
| // If the child crosses a column boundary, record space shortage, in case |
| // nothing inside it has already done so. The column balancer needs to |
| // know by how much it has to stretch the columns to make more content |
| // fit. If no breaks are reported (but do occur), the balancer will have |
| // no clue. Only measure the space after the last column boundary, in case |
| // it crosses more than one. |
| LayoutUnit space_used_in_last_column = |
| bottom_in_flow_thread - |
| group.ColumnLogicalTopForOffset(bottom_in_flow_thread); |
| RecordSpaceShortage(space_used_in_last_column); |
| } |
| } |
| |
| // If this is an inner multicol container, look for space shortage inside it. |
| if (!box.IsLayoutBlockFlow()) |
| return; |
| LayoutMultiColumnFlowThread* flow_thread = |
| ToLayoutBlockFlow(box).MultiColumnFlowThread(); |
| if (!flow_thread || flow_thread->IsLayoutPagedFlowThread()) |
| return; |
| for (const LayoutMultiColumnSet* column_set = |
| flow_thread->FirstMultiColumnSet(); |
| column_set; column_set = column_set->NextSiblingMultiColumnSet()) { |
| // Establish an inner shortage finder for this column set in the inner |
| // multicol container. We need to let it walk through all fragmentainer |
| // groups in one go, or we'd miss the column boundaries between each |
| // fragmentainer group. We need to record space shortage there too. |
| MinimumSpaceShortageFinder inner_finder( |
| *column_set, column_set->LogicalTopInFlowThread(), |
| column_set->LogicalBottomInFlowThread()); |
| RecordSpaceShortage(inner_finder.MinimumSpaceShortage()); |
| } |
| } |
| |
| void MinimumSpaceShortageFinder::ExamineBoxBeforeLeaving( |
| const LayoutBox& box, |
| LayoutUnit child_logical_height) { |
| if (pending_strut_ == LayoutUnit::Min() || |
| box.GetPaginationBreakability() != LayoutBox::kForbidBreaks) |
| return; |
| |
| // The previous break was before a breakable block. Here's the first piece of |
| // unbreakable content after / inside that block. We want to record the |
| // distance from the top of the column to the bottom of this box as space |
| // shortage. |
| LayoutUnit logical_offset_from_current_column = |
| OffsetFromColumnLogicalTop(FlowThreadOffset()); |
| RecordSpaceShortage(logical_offset_from_current_column + |
| child_logical_height - pending_strut_); |
| pending_strut_ = LayoutUnit::Min(); |
| } |
| |
| void MinimumSpaceShortageFinder::ExamineLine(const RootInlineBox& line) { |
| LayoutUnit line_top = line.LineTopWithLeading(); |
| LayoutUnit line_top_in_flow_thread = FlowThreadOffset() + line_top; |
| LayoutUnit line_height = line.LineBottomWithLeading() - line_top; |
| if (pending_strut_ != LayoutUnit::Min()) { |
| // The previous break was before a breakable block. Here's the first line |
| // after / inside that block. We want to record the distance from the top of |
| // the column to the bottom of this box as space shortage. |
| LayoutUnit logical_offset_from_current_column = |
| OffsetFromColumnLogicalTop(line_top_in_flow_thread); |
| RecordSpaceShortage(logical_offset_from_current_column + line_height - |
| pending_strut_); |
| pending_strut_ = LayoutUnit::Min(); |
| return; |
| } |
| DCHECK(IsFirstAfterBreak(line_top_in_flow_thread) || |
| !line.PaginationStrut() || |
| !IsLogicalTopWithinBounds(line_top_in_flow_thread - |
| line.PaginationStrut())); |
| if (IsFirstAfterBreak(line_top_in_flow_thread)) |
| RecordSpaceShortage(line_height - line.PaginationStrut()); |
| |
| // Even if the line box itself fits fine inside a column, some content may |
| // overflow the line box bottom (due to restrictive line-height, for |
| // instance). We should check if some portion of said overflow ends up in the |
| // next column. That counts as space shortage. |
| const MultiColumnFragmentainerGroup& group = |
| GroupAtOffset(line_top_in_flow_thread); |
| LayoutUnit line_bottom_with_overflow = |
| line_top_in_flow_thread + line.LineBottom() - line_top; |
| if (group.ColumnLogicalTopForOffset(line_top_in_flow_thread) != |
| group.ColumnLogicalTopForOffset(line_bottom_with_overflow)) { |
| LayoutUnit shortage = |
| line_bottom_with_overflow - |
| group.ColumnLogicalTopForOffset(line_bottom_with_overflow); |
| RecordSpaceShortage(shortage); |
| } |
| } |
| |
| } // namespace blink |