path: root/chromium/third_party/blink/renderer/core/layout/column_balancer.h

// 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.

#ifndef THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_COLUMN_BALANCER_H_
#define THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_COLUMN_BALANCER_H_

#include "third_party/blink/renderer/core/layout/layout_multi_column_set.h"
#include "third_party/blink/renderer/platform/wtf/allocator.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 {
  STACK_ALLOCATED();

 protected:
  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 -
           GroupAtOffset(offset_in_flow_thread)
               .ColumnLogicalTopForOffset(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 ==
           group.ColumnLogicalTopForOffset(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();

 private:
  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 {
 public:
  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_;
  }

 private:
  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 {
    DISALLOW_NEW();

   public:
    explicit 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));
    }

   private:
    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] http://www.w3.org/TR/css3-break/#parallel-flows
  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 {
 public:
  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_; }

 private:
  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

#endif  // THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_COLUMN_BALANCER_H_