File: ColumnBalancer.h

package info (click to toggle)
chromium-browser 57.0.2987.98-1~deb8u1
  • links: PTS, VCS
  • area: main
  • in suites: jessie
  • size: 2,637,852 kB
  • ctags: 2,544,394
  • sloc: cpp: 12,815,961; ansic: 3,676,222; python: 1,147,112; asm: 526,608; java: 523,212; xml: 286,794; perl: 92,654; sh: 86,408; objc: 73,271; makefile: 27,698; cs: 18,487; yacc: 13,031; tcl: 12,957; pascal: 4,875; ml: 4,716; lex: 3,904; sql: 3,862; ruby: 1,982; lisp: 1,508; php: 1,368; exp: 404; awk: 325; csh: 117; jsp: 39; sed: 37
file content (271 lines) | stat: -rw-r--r-- 12,755 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
// 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,
                                       EBreak 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,
                               EBreak 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,
                               EBreak 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