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