third_party/WebKit/Source/core/layout/ColumnBalancer.h - chromium/src - Git at Google

 // 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/LayoutMultiColumnSet.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 {
  protected:
   ColumnBalancer(const LayoutMultiColumnSet&,
                  LayoutUnit logicalTopInFlowThread,
                  LayoutUnit logicalBottomInFlowThread);

   const LayoutMultiColumnSet& columnSet() const { return m_columnSet; }

   // 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 m_logicalTopInFlowThread;
   }
   const LayoutUnit logicalBottomInFlowThread() const {
     return m_logicalBottomInFlowThread;
   }

   const MultiColumnFragmentainerGroup& groupAtOffset(
       LayoutUnit offsetInFlowThread) const {
     return m_columnSet.fragmentainerGroupAtFlowThreadOffset(
         offsetInFlowThread, LayoutBox::AssociateWithLatterPage);
   }

   LayoutUnit offsetFromColumnLogicalTop(LayoutUnit offsetInFlowThread) const {
     return offsetInFlowThread -
            groupAtOffset(offsetInFlowThread)
                .columnLogicalTopForOffset(offsetInFlowThread);
   }

   // Flow thread offset for the layout object that we're currently examining.
   LayoutUnit flowThreadOffset() const { return m_flowThreadOffset; }

   // 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 flowThreadOffset) const {
     if (flowThreadOffset <= m_logicalTopInFlowThread) {
       // The first column is either not after any break at all, or after a break
       // in a previous fragmentainer group.
       return false;
     }
     return flowThreadOffset ==
            groupAtOffset(flowThreadOffset)
                .columnLogicalTopForOffset(flowThreadOffset);
   }

   bool isLogicalTopWithinBounds(LayoutUnit logicalTopInFlowThread) const {
     return logicalTopInFlowThread >= m_logicalTopInFlowThread &&
            logicalTopInFlowThread < m_logicalBottomInFlowThread;
   }

   bool isLogicalBottomWithinBounds(LayoutUnit logicalBottomInFlowThread) const {
     return logicalBottomInFlowThread > m_logicalTopInFlowThread &&
            logicalBottomInFlowThread <= m_logicalBottomInFlowThread;
   }

   // 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 childLogicalHeight,
       EBreakBetween previousBreakAfterValue) = 0;
   virtual void examineBoxBeforeLeaving(const LayoutBox&,
                                        LayoutUnit childLogicalHeight) = 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& m_columnSet;
   const LayoutUnit m_logicalTopInFlowThread;
   const LayoutUnit m_logicalBottomInFlowThread;

   LayoutUnit m_flowThreadOffset;
 };

 // 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 logicalTopInFlowThread,
                             LayoutUnit logicalBottomInFlowThread);

   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 m_tallestUnbreakableLogicalHeight;
   }

  private:
   void examineBoxAfterEntering(const LayoutBox&,
                                LayoutUnit childLogicalHeight,
                                EBreakBetween previousBreakAfterValue);
   void examineBoxBeforeLeaving(const LayoutBox&, LayoutUnit childLogicalHeight);
   void examineLine(const RootInlineBox&);

   // 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 offsetInFlowThread, LayoutUnit strut);

   // Return the accumulated space used by struts at all column boundaries
   // preceding the specified flowthread offset.
   LayoutUnit spaceUsedByStrutsAt(LayoutUnit offsetInFlowThread) 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 endOffsetInFlowThread);

   // 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 columnCount = columnSet().usedColumnCount();
     if (m_contentRuns.size() <= columnCount)
       return 0;
     unsigned lastRunIndex = m_contentRuns.size() - 1;
     return lastRunIndex / columnCount * columnCount;
   }

   // 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 {
    public:
     ContentRun(LayoutUnit breakOffset)
         : m_breakOffset(breakOffset), m_assumedImplicitBreaks(0) {}

     unsigned assumedImplicitBreaks() const { return m_assumedImplicitBreaks; }
     void assumeAnotherImplicitBreak() { m_assumedImplicitBreaks++; }
     LayoutUnit breakOffset() const { return m_breakOffset; }

     // Return the column height that this content run would require, considering
     // the implicit breaks assumed so far.
     LayoutUnit columnLogicalHeight(LayoutUnit startOffset) const {
       return LayoutUnit::fromFloatCeil(float(m_breakOffset - startOffset) /
                                        float(m_assumedImplicitBreaks + 1));
     }

    private:
     LayoutUnit m_breakOffset;  // Flow thread offset where this run ends.
     unsigned m_assumedImplicitBreaks;  // Number of implicit breaks in this run
                                        // assumed so far.
   };
   Vector<ContentRun, 32> m_contentRuns;

   // 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> m_shortestStruts;

   LayoutUnit m_tallestUnbreakableLogicalHeight;
   LayoutUnit m_lastBreakSeen;
 };

 // 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 logicalTopInFlowThread,
                              LayoutUnit logicalBottomInFlowThread);

   LayoutUnit minimumSpaceShortage() const { return m_minimumSpaceShortage; }
   unsigned forcedBreaksCount() const { return m_forcedBreaksCount; }

  private:
   void examineBoxAfterEntering(const LayoutBox&,
                                LayoutUnit childLogicalHeight,
                                EBreakBetween previousBreakAfterValue);
   void examineBoxBeforeLeaving(const LayoutBox&, LayoutUnit childLogicalHeight);
   void examineLine(const RootInlineBox&);

   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)
       m_minimumSpaceShortage = std::min(m_minimumSpaceShortage, shortage);
   }

   // The smallest amout of space shortage that caused a column break.
   LayoutUnit m_minimumSpaceShortage;

   // 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 m_pendingStrut;

   unsigned m_forcedBreaksCount;
 };

 }  // namespace blink
	// 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/LayoutMultiColumnSet.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 {
	protected:
	ColumnBalancer(const LayoutMultiColumnSet&,
	LayoutUnit logicalTopInFlowThread,
	LayoutUnit logicalBottomInFlowThread);

	const LayoutMultiColumnSet& columnSet() const { return m_columnSet; }

	// 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 m_logicalTopInFlowThread;
	}
	const LayoutUnit logicalBottomInFlowThread() const {
	return m_logicalBottomInFlowThread;
	}

	const MultiColumnFragmentainerGroup& groupAtOffset(
	LayoutUnit offsetInFlowThread) const {
	return m_columnSet.fragmentainerGroupAtFlowThreadOffset(
	offsetInFlowThread, LayoutBox::AssociateWithLatterPage);
	}

	LayoutUnit offsetFromColumnLogicalTop(LayoutUnit offsetInFlowThread) const {
	return offsetInFlowThread -
	groupAtOffset(offsetInFlowThread)
	.columnLogicalTopForOffset(offsetInFlowThread);
	}

	// Flow thread offset for the layout object that we're currently examining.
	LayoutUnit flowThreadOffset() const { return m_flowThreadOffset; }

	// 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 flowThreadOffset) const {
	if (flowThreadOffset <= m_logicalTopInFlowThread) {
	// The first column is either not after any break at all, or after a break
	// in a previous fragmentainer group.
	return false;
	}
	return flowThreadOffset ==
	groupAtOffset(flowThreadOffset)
	.columnLogicalTopForOffset(flowThreadOffset);
	}

	bool isLogicalTopWithinBounds(LayoutUnit logicalTopInFlowThread) const {
	return logicalTopInFlowThread >= m_logicalTopInFlowThread &&
	logicalTopInFlowThread < m_logicalBottomInFlowThread;
	}

	bool isLogicalBottomWithinBounds(LayoutUnit logicalBottomInFlowThread) const {
	return logicalBottomInFlowThread > m_logicalTopInFlowThread &&
	logicalBottomInFlowThread <= m_logicalBottomInFlowThread;
	}

	// 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 childLogicalHeight,
	EBreakBetween previousBreakAfterValue) = 0;
	virtual void examineBoxBeforeLeaving(const LayoutBox&,
	LayoutUnit childLogicalHeight) = 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& m_columnSet;
	const LayoutUnit m_logicalTopInFlowThread;
	const LayoutUnit m_logicalBottomInFlowThread;

	LayoutUnit m_flowThreadOffset;
	};

	// 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 logicalTopInFlowThread,
	LayoutUnit logicalBottomInFlowThread);

	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 m_tallestUnbreakableLogicalHeight;
	}

	private:
	void examineBoxAfterEntering(const LayoutBox&,
	LayoutUnit childLogicalHeight,
	EBreakBetween previousBreakAfterValue);
	void examineBoxBeforeLeaving(const LayoutBox&, LayoutUnit childLogicalHeight);
	void examineLine(const RootInlineBox&);

	// 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 offsetInFlowThread, LayoutUnit strut);

	// Return the accumulated space used by struts at all column boundaries
	// preceding the specified flowthread offset.
	LayoutUnit spaceUsedByStrutsAt(LayoutUnit offsetInFlowThread) 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 endOffsetInFlowThread);

	// 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 columnCount = columnSet().usedColumnCount();
	if (m_contentRuns.size() <= columnCount)
	return 0;
	unsigned lastRunIndex = m_contentRuns.size() - 1;
	return lastRunIndex / columnCount * columnCount;
	}

	// 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 {
	public:
	ContentRun(LayoutUnit breakOffset)
	: m_breakOffset(breakOffset), m_assumedImplicitBreaks(0) {}

	unsigned assumedImplicitBreaks() const { return m_assumedImplicitBreaks; }
	void assumeAnotherImplicitBreak() { m_assumedImplicitBreaks++; }
	LayoutUnit breakOffset() const { return m_breakOffset; }

	// Return the column height that this content run would require, considering
	// the implicit breaks assumed so far.
	LayoutUnit columnLogicalHeight(LayoutUnit startOffset) const {
	return LayoutUnit::fromFloatCeil(float(m_breakOffset - startOffset) /
	float(m_assumedImplicitBreaks + 1));
	}

	private:
	LayoutUnit m_breakOffset; // Flow thread offset where this run ends.
	unsigned m_assumedImplicitBreaks; // Number of implicit breaks in this run
	// assumed so far.
	};
	Vector<ContentRun, 32> m_contentRuns;

	// 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> m_shortestStruts;

	LayoutUnit m_tallestUnbreakableLogicalHeight;
	LayoutUnit m_lastBreakSeen;
	};

	// 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 logicalTopInFlowThread,
	LayoutUnit logicalBottomInFlowThread);

	LayoutUnit minimumSpaceShortage() const { return m_minimumSpaceShortage; }
	unsigned forcedBreaksCount() const { return m_forcedBreaksCount; }

	private:
	void examineBoxAfterEntering(const LayoutBox&,
	LayoutUnit childLogicalHeight,
	EBreakBetween previousBreakAfterValue);
	void examineBoxBeforeLeaving(const LayoutBox&, LayoutUnit childLogicalHeight);
	void examineLine(const RootInlineBox&);

	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)
	m_minimumSpaceShortage = std::min(m_minimumSpaceShortage, shortage);
	}

	// The smallest amout of space shortage that caused a column break.
	LayoutUnit m_minimumSpaceShortage;

	// 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 m_pendingStrut;

	unsigned m_forcedBreaksCount;
	};

	} // namespace blink