blob: 7dde35819699fde689cfcd5952ec5e2bbb288c7f [file] [log] [blame]
// 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 "third_party/blink/renderer/core/layout/layout_multi_column_set.h"
namespace blink {
// A column balancer traverses a portion of the subtree of a flow thread that
// belongs to one or more fragmentainer groups within one column set, in order
// to collect certain data to be used for column balancing. This is an abstract
// class that just walks the subtree and leaves it to subclasses to actually
// collect data.
class ColumnBalancer {
ColumnBalancer(const LayoutMultiColumnSet&,
LayoutUnit logical_top_in_flow_thread,
LayoutUnit logical_bottom_in_flow_thread);
const LayoutMultiColumnSet& ColumnSet() const { return column_set_; }
// The flow thread portion we're examining. It may be that of the entire
// column set, or just of a fragmentainer group.
const LayoutUnit LogicalTopInFlowThread() const {
return logical_top_in_flow_thread_;
const LayoutUnit LogicalBottomInFlowThread() const {
return logical_bottom_in_flow_thread_;
const MultiColumnFragmentainerGroup& GroupAtOffset(
LayoutUnit offset_in_flow_thread) const {
return column_set_.FragmentainerGroupAtFlowThreadOffset(
offset_in_flow_thread, LayoutBox::kAssociateWithLatterPage);
LayoutUnit OffsetFromColumnLogicalTop(
LayoutUnit offset_in_flow_thread) const {
return offset_in_flow_thread -
// Flow thread offset for the layout object that we're currently examining.
LayoutUnit FlowThreadOffset() const { return flow_thread_offset_; }
// Return true if the specified offset is at the top of a column, as long as
// it's not the first column in the flow thread portion.
bool IsFirstAfterBreak(LayoutUnit flow_thread_offset) const {
if (flow_thread_offset <= logical_top_in_flow_thread_) {
// The first column is either not after any break at all, or after a break
// in a previous fragmentainer group.
return false;
const auto& group = GroupAtOffset(flow_thread_offset);
if (!group.IsLogicalHeightKnown())
return false;
return flow_thread_offset ==
bool IsLogicalTopWithinBounds(LayoutUnit logical_top_in_flow_thread) const {
return logical_top_in_flow_thread >= logical_top_in_flow_thread_ &&
logical_top_in_flow_thread < logical_bottom_in_flow_thread_;
bool IsLogicalBottomWithinBounds(
LayoutUnit logical_bottom_in_flow_thread) const {
return logical_bottom_in_flow_thread > logical_top_in_flow_thread_ &&
logical_bottom_in_flow_thread <= logical_bottom_in_flow_thread_;
// Examine and collect column balancing data from a layout box that has been
// found to intersect with the flow thread portion we're examining. Does not
// recurse into children. flowThreadOffset() will return the offset from |box|
// to the flow thread. Two hooks are provided here. The first one is called
// right after entering and before traversing the subtree of the box, and the
// second one right after having traversed the subtree.
virtual void ExamineBoxAfterEntering(
const LayoutBox&,
LayoutUnit child_logical_height,
EBreakBetween previous_break_after_value) = 0;
virtual void ExamineBoxBeforeLeaving(const LayoutBox&,
LayoutUnit child_logical_height) = 0;
// Examine and collect column balancing data from a line that has been found
// to intersect with the flow thread portion. Does not recurse into layout
// objects on that line.
virtual void ExamineLine(const RootInlineBox&) = 0;
// Examine and collect column balancing data for everything in the flow thread
// portion. Will trigger calls to examineBoxAfterEntering(),
// examineBoxBeforeLeaving() and examineLine() for interesting boxes and
// lines.
void Traverse();
void TraverseSubtree(const LayoutBox&);
void TraverseLines(const LayoutBlockFlow&);
void TraverseChildren(const LayoutObject&);
const LayoutMultiColumnSet& column_set_;
const LayoutUnit logical_top_in_flow_thread_;
const LayoutUnit logical_bottom_in_flow_thread_;
LayoutUnit flow_thread_offset_;
// After an initial layout pass, we know the height of the contents of a flow
// thread. Based on this, we can estimate an initial minimal column height. This
// class will collect the necessary information from the layout objects to make
// this estimate. This estimate may be used to perform another layout iteration.
// If we after such a layout iteration cannot fit the contents with the given
// column height without creating overflowing columns, we will have to stretch
// the columns by some amount and lay out again. We may need to do this several
// times (but typically not more times than the number of columns that we have).
// The amount to stretch is provided by the sibling of this class, named
// MinimumSpaceShortageFinder.
class InitialColumnHeightFinder final : public ColumnBalancer {
InitialColumnHeightFinder(const LayoutMultiColumnSet&,
LayoutUnit logical_top_in_flow_thread,
LayoutUnit logical_bottom_in_flow_thread);
LayoutUnit InitialMinimalBalancedHeight() const;
// Height of the tallest piece of unbreakable content. This is the minimum
// column logical height required to avoid fragmentation where it shouldn't
// occur (inside unbreakable content, between orphans and widows, etc.). This
// will be used as a hint to the column balancer to help set a good initial
// column height.
LayoutUnit TallestUnbreakableLogicalHeight() const {
return tallest_unbreakable_logical_height_;
void ExamineBoxAfterEntering(
const LayoutBox&,
LayoutUnit child_logical_height,
EBreakBetween previous_break_after_value) override;
void ExamineBoxBeforeLeaving(const LayoutBox&,
LayoutUnit child_logical_height) override;
void ExamineLine(const RootInlineBox&) override;
// Record that there's a pagination strut that ends at the specified
// |offsetInFlowThread|, which is an offset exactly at the top of some column.
void RecordStrutBeforeOffset(LayoutUnit offset_in_flow_thread,
LayoutUnit strut);
// Return the accumulated space used by struts at all column boundaries
// preceding the specified flowthread offset.
LayoutUnit SpaceUsedByStrutsAt(LayoutUnit offset_in_flow_thread) const;
// Add a content run, specified by its end position. A content run is appended
// at every forced/explicit break and at the end of the column set. The
// content runs are used to determine where implicit/soft breaks will occur,
// in order to calculate an initial column height.
void AddContentRun(LayoutUnit end_offset_in_flow_thread);
// Normally we'll just return 0 here, because in most cases we won't add more
// content runs than used column-count. However, if we're at the initial
// balancing pass for a multicol that lives inside another to-be-balanced
// outer multicol container, and there is a sufficient number of forced column
// breaks, we may exceed used column-count. In such cases, we're going to
// assume a minimal number of fragmentainer groups (rows) that will eventually
// be created, and when distributing implicit column breaks to calculate an
// initial balanced height, we'll only focus on content that has any chance at
// all to end up in the last row.
unsigned FirstContentRunIndexInLastRow() const {
unsigned column_count = ColumnSet().UsedColumnCount();
if (content_runs_.size() <= column_count)
return 0;
unsigned last_run_index = content_runs_.size() - 1;
return last_run_index / column_count * column_count;
// Return the index of the content run with the currently tallest columns,
// taking all implicit breaks assumed so far into account.
unsigned ContentRunIndexWithTallestColumns() const;
// Given the current list of content runs, make assumptions about where we
// need to insert implicit breaks (if there's room for any at all; depending
// on the number of explicit breaks), and store the results. This is needed in
// order to balance the columns.
void DistributeImplicitBreaks();
// A run of content without explicit (forced) breaks; i.e. a flow thread
// portion between two explicit breaks, between flow thread start and an
// explicit break, between an explicit break and flow thread end, or, in cases
// when there are no explicit breaks at all: between flow thread portion start
// and flow thread portion end. We need to know where the explicit breaks are,
// in order to figure out where the implicit breaks will end up, so that we
// get the columns properly balanced. A content run starts out as representing
// one single column, and will represent one additional column for each
// implicit break "inserted" there.
class ContentRun {
ContentRun(LayoutUnit break_offset)
: break_offset_(break_offset), assumed_implicit_breaks_(0) {}
unsigned AssumedImplicitBreaks() const { return assumed_implicit_breaks_; }
void AssumeAnotherImplicitBreak() { assumed_implicit_breaks_++; }
LayoutUnit BreakOffset() const { return break_offset_; }
// Return the column height that this content run would require, considering
// the implicit breaks assumed so far.
LayoutUnit ColumnLogicalHeight(LayoutUnit start_offset) const {
return LayoutUnit::FromFloatCeil(float(break_offset_ - start_offset) /
float(assumed_implicit_breaks_ + 1));
LayoutUnit break_offset_; // Flow thread offset where this run ends.
unsigned assumed_implicit_breaks_; // Number of implicit breaks in this run
// assumed so far.
Vector<ContentRun, 32> content_runs_;
// Shortest strut found at each column boundary (index 0 being the boundary
// between the first and the second column, index 1 being the one between the
// second and the third boundary, and so on). There may be several objects
// that cross the same column boundary, and we're only interested in the
// shortest one. For example, when having a float beside regular in-flow
// content, we end up with two parallel fragmentation flows [1]. The shortest
// strut found at a column boundary is the amount of space that we wasted at
// said column boundary, and it needs to be deducted when estimating the
// initial balanced column height, or we risk making the column row too tall.
// An entry set to LayoutUnit::max() means that we didn't detect any object
// crossing that boundary.
// [1]
Vector<LayoutUnit, 32> shortest_struts_;
LayoutUnit tallest_unbreakable_logical_height_;
LayoutUnit last_break_seen_;
// If we have previously used InitialColumnHeightFinder to estimate an initial
// column height, and that didn't result in tall enough columns, we need
// subsequent layout passes where we increase the column height by the minimum
// space shortage at column breaks. This class finds the minimum space shortage
// after having laid out with the current column height.
class MinimumSpaceShortageFinder final : public ColumnBalancer {
MinimumSpaceShortageFinder(const LayoutMultiColumnSet&,
LayoutUnit logical_top_in_flow_thread,
LayoutUnit logical_bottom_in_flow_thread);
LayoutUnit MinimumSpaceShortage() const { return minimum_space_shortage_; }
unsigned ForcedBreaksCount() const { return forced_breaks_count_; }
void ExamineBoxAfterEntering(
const LayoutBox&,
LayoutUnit child_logical_height,
EBreakBetween previous_break_after_value) override;
void ExamineBoxBeforeLeaving(const LayoutBox&,
LayoutUnit child_logical_height) override;
void ExamineLine(const RootInlineBox&) override;
void RecordSpaceShortage(LayoutUnit shortage) {
// Only positive values are interesting (and allowed) here. Zero space
// shortage may be reported when we're at the top of a column and the
// element has zero height.
if (shortage > 0)
minimum_space_shortage_ = std::min(minimum_space_shortage_, shortage);
// The smallest amout of space shortage that caused a column break.
LayoutUnit minimum_space_shortage_;
// Set when breaking before a block, and we're looking for the first
// unbreakable descendant, in order to report correct space shortage for that
// one.
LayoutUnit pending_strut_;
unsigned forced_breaks_count_;
} // namespace blink