OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "core/layout/LayoutMultiColumnSet.h" | 5 #include "core/layout/LayoutMultiColumnSet.h" |
6 | 6 |
7 namespace blink { | 7 namespace blink { |
8 | 8 |
9 // A column balancer traverses a portion of the subtree of a flow thread that be
longs to one or | 9 // A column balancer traverses a portion of the subtree of a flow thread that |
10 // more fragmentainer groups within one column set, in order to collect certain
data to be used for | 10 // belongs to one or more fragmentainer groups within one column set, in order |
11 // column balancing. This is an abstract class that just walks the subtree and l
eaves it to | 11 // to collect certain data to be used for column balancing. This is an abstract |
12 // subclasses to actually collect data. | 12 // class that just walks the subtree and leaves it to subclasses to actually |
| 13 // collect data. |
13 class ColumnBalancer { | 14 class ColumnBalancer { |
14 protected: | 15 protected: |
15 ColumnBalancer(const LayoutMultiColumnSet&, | 16 ColumnBalancer(const LayoutMultiColumnSet&, |
16 LayoutUnit logicalTopInFlowThread, | 17 LayoutUnit logicalTopInFlowThread, |
17 LayoutUnit logicalBottomInFlowThread); | 18 LayoutUnit logicalBottomInFlowThread); |
18 | 19 |
19 const LayoutMultiColumnSet& columnSet() const { return m_columnSet; } | 20 const LayoutMultiColumnSet& columnSet() const { return m_columnSet; } |
20 | 21 |
21 // The flow thread portion we're examining. It may be that of the entire colum
n set, or just of | 22 // The flow thread portion we're examining. It may be that of the entire |
22 // a fragmentainer group. | 23 // column set, or just of a fragmentainer group. |
23 const LayoutUnit logicalTopInFlowThread() const { | 24 const LayoutUnit logicalTopInFlowThread() const { |
24 return m_logicalTopInFlowThread; | 25 return m_logicalTopInFlowThread; |
25 } | 26 } |
26 const LayoutUnit logicalBottomInFlowThread() const { | 27 const LayoutUnit logicalBottomInFlowThread() const { |
27 return m_logicalBottomInFlowThread; | 28 return m_logicalBottomInFlowThread; |
28 } | 29 } |
29 | 30 |
30 const MultiColumnFragmentainerGroup& groupAtOffset( | 31 const MultiColumnFragmentainerGroup& groupAtOffset( |
31 LayoutUnit offsetInFlowThread) const { | 32 LayoutUnit offsetInFlowThread) const { |
32 return m_columnSet.fragmentainerGroupAtFlowThreadOffset( | 33 return m_columnSet.fragmentainerGroupAtFlowThreadOffset( |
33 offsetInFlowThread, LayoutBox::AssociateWithLatterPage); | 34 offsetInFlowThread, LayoutBox::AssociateWithLatterPage); |
34 } | 35 } |
35 | 36 |
36 LayoutUnit offsetFromColumnLogicalTop(LayoutUnit offsetInFlowThread) const { | 37 LayoutUnit offsetFromColumnLogicalTop(LayoutUnit offsetInFlowThread) const { |
37 return offsetInFlowThread - | 38 return offsetInFlowThread - |
38 groupAtOffset(offsetInFlowThread) | 39 groupAtOffset(offsetInFlowThread) |
39 .columnLogicalTopForOffset(offsetInFlowThread); | 40 .columnLogicalTopForOffset(offsetInFlowThread); |
40 } | 41 } |
41 | 42 |
42 // Flow thread offset for the layout object that we're currently examining. | 43 // Flow thread offset for the layout object that we're currently examining. |
43 LayoutUnit flowThreadOffset() const { return m_flowThreadOffset; } | 44 LayoutUnit flowThreadOffset() const { return m_flowThreadOffset; } |
44 | 45 |
45 // Return true if the specified offset is at the top of a column, as long as i
t's not the first | 46 // Return true if the specified offset is at the top of a column, as long as |
46 // column in the flow thread portion. | 47 // it's not the first column in the flow thread portion. |
47 bool isFirstAfterBreak(LayoutUnit flowThreadOffset) const { | 48 bool isFirstAfterBreak(LayoutUnit flowThreadOffset) const { |
48 if (flowThreadOffset <= m_logicalTopInFlowThread) { | 49 if (flowThreadOffset <= m_logicalTopInFlowThread) { |
49 // The first column is either not after any break at all, or after a break
in a | 50 // The first column is either not after any break at all, or after a break |
50 // previous fragmentainer group. | 51 // in a previous fragmentainer group. |
51 return false; | 52 return false; |
52 } | 53 } |
53 return flowThreadOffset == | 54 return flowThreadOffset == |
54 groupAtOffset(flowThreadOffset) | 55 groupAtOffset(flowThreadOffset) |
55 .columnLogicalTopForOffset(flowThreadOffset); | 56 .columnLogicalTopForOffset(flowThreadOffset); |
56 } | 57 } |
57 | 58 |
58 bool isLogicalTopWithinBounds(LayoutUnit logicalTopInFlowThread) const { | 59 bool isLogicalTopWithinBounds(LayoutUnit logicalTopInFlowThread) const { |
59 return logicalTopInFlowThread >= m_logicalTopInFlowThread && | 60 return logicalTopInFlowThread >= m_logicalTopInFlowThread && |
60 logicalTopInFlowThread < m_logicalBottomInFlowThread; | 61 logicalTopInFlowThread < m_logicalBottomInFlowThread; |
61 } | 62 } |
62 | 63 |
63 bool isLogicalBottomWithinBounds(LayoutUnit logicalBottomInFlowThread) const { | 64 bool isLogicalBottomWithinBounds(LayoutUnit logicalBottomInFlowThread) const { |
64 return logicalBottomInFlowThread > m_logicalTopInFlowThread && | 65 return logicalBottomInFlowThread > m_logicalTopInFlowThread && |
65 logicalBottomInFlowThread <= m_logicalBottomInFlowThread; | 66 logicalBottomInFlowThread <= m_logicalBottomInFlowThread; |
66 } | 67 } |
67 | 68 |
68 // Examine and collect column balancing data from a layout box that has been f
ound to intersect | 69 // Examine and collect column balancing data from a layout box that has been |
69 // with the flow thread portion we're examining. Does not recurse into | 70 // found to intersect with the flow thread portion we're examining. Does not |
70 // children. flowThreadOffset() will return the offset from |box| to the flow
thread. Two hooks | 71 // recurse into children. flowThreadOffset() will return the offset from |box| |
71 // are provided here. The first one is called right after entering and before
traversing the | 72 // to the flow thread. Two hooks are provided here. The first one is called |
72 // subtree of the box, and the second one right after having traversed the sub
tree. | 73 // right after entering and before traversing the subtree of the box, and the |
| 74 // second one right after having traversed the subtree. |
73 virtual void examineBoxAfterEntering(const LayoutBox&, | 75 virtual void examineBoxAfterEntering(const LayoutBox&, |
74 EBreak previousBreakAfterValue) = 0; | 76 EBreak previousBreakAfterValue) = 0; |
75 virtual void examineBoxBeforeLeaving(const LayoutBox&) = 0; | 77 virtual void examineBoxBeforeLeaving(const LayoutBox&) = 0; |
76 | 78 |
77 // Examine and collect column balancing data from a line that has been found t
o intersect with | 79 // Examine and collect column balancing data from a line that has been found |
78 // the flow thread portion. Does not recurse into layout objects on that line. | 80 // to intersect with the flow thread portion. Does not recurse into layout |
| 81 // objects on that line. |
79 virtual void examineLine(const RootInlineBox&) = 0; | 82 virtual void examineLine(const RootInlineBox&) = 0; |
80 | 83 |
81 // Examine and collect column balancing data for everything in the flow thread
portion. Will | 84 // Examine and collect column balancing data for everything in the flow thread |
82 // trigger calls to examineBoxAfterEntering(), examineBoxBeforeLeaving() and e
xamineLine() for | 85 // portion. Will trigger calls to examineBoxAfterEntering(), |
83 // interesting boxes and lines. | 86 // examineBoxBeforeLeaving() and examineLine() for interesting boxes and |
| 87 // lines. |
84 void traverse(); | 88 void traverse(); |
85 | 89 |
86 private: | 90 private: |
87 void traverseSubtree(const LayoutBox&); | 91 void traverseSubtree(const LayoutBox&); |
88 | 92 |
89 const LayoutMultiColumnSet& m_columnSet; | 93 const LayoutMultiColumnSet& m_columnSet; |
90 const LayoutUnit m_logicalTopInFlowThread; | 94 const LayoutUnit m_logicalTopInFlowThread; |
91 const LayoutUnit m_logicalBottomInFlowThread; | 95 const LayoutUnit m_logicalBottomInFlowThread; |
92 | 96 |
93 LayoutUnit m_flowThreadOffset; | 97 LayoutUnit m_flowThreadOffset; |
94 }; | 98 }; |
95 | 99 |
96 // After an initial layout pass, we know the height of the contents of a flow th
read. Based on | 100 // After an initial layout pass, we know the height of the contents of a flow |
97 // this, we can estimate an initial minimal column height. This class will colle
ct the necessary | 101 // thread. Based on this, we can estimate an initial minimal column height. This |
98 // information from the layout objects to make this estimate. This estimate may
be used to perform | 102 // class will collect the necessary information from the layout objects to make |
99 // another layout iteration. If we after such a layout iteration cannot fit the
contents with the | 103 // this estimate. This estimate may be used to perform another layout iteration. |
100 // given column height without creating overflowing columns, we will have to str
etch the columns by | 104 // If we after such a layout iteration cannot fit the contents with the given |
101 // some amount and lay out again. We may need to do this several times (but typi
cally not more | 105 // column height without creating overflowing columns, we will have to stretch |
102 // times than the number of columns that we have). The amount to stretch is prov
ided by the sister | 106 // the columns by some amount and lay out again. We may need to do this several |
103 // of this class, named MinimumSpaceShortageFinder. | 107 // times (but typically not more times than the number of columns that we have). |
| 108 // The amount to stretch is provided by the sister of this class, named |
| 109 // MinimumSpaceShortageFinder. |
104 class InitialColumnHeightFinder final : public ColumnBalancer { | 110 class InitialColumnHeightFinder final : public ColumnBalancer { |
105 public: | 111 public: |
106 InitialColumnHeightFinder(const LayoutMultiColumnSet&, | 112 InitialColumnHeightFinder(const LayoutMultiColumnSet&, |
107 LayoutUnit logicalTopInFlowThread, | 113 LayoutUnit logicalTopInFlowThread, |
108 LayoutUnit logicalBottomInFlowThread); | 114 LayoutUnit logicalBottomInFlowThread); |
109 | 115 |
110 LayoutUnit initialMinimalBalancedHeight() const; | 116 LayoutUnit initialMinimalBalancedHeight() const; |
111 | 117 |
112 // Height of the tallest piece of unbreakable content. This is the minimum col
umn logical height | 118 // Height of the tallest piece of unbreakable content. This is the minimum |
113 // required to avoid fragmentation where it shouldn't occur (inside unbreakabl
e content, between | 119 // column logical height required to avoid fragmentation where it shouldn't |
114 // orphans and widows, etc.). This will be used as a hint to the column balanc
er to help set a | 120 // occur (inside unbreakable content, between orphans and widows, etc.). This |
115 // good initial column height. | 121 // will be used as a hint to the column balancer to help set a good initial |
| 122 // column height. |
116 LayoutUnit tallestUnbreakableLogicalHeight() const { | 123 LayoutUnit tallestUnbreakableLogicalHeight() const { |
117 return m_tallestUnbreakableLogicalHeight; | 124 return m_tallestUnbreakableLogicalHeight; |
118 } | 125 } |
119 | 126 |
120 private: | 127 private: |
121 void examineBoxAfterEntering(const LayoutBox&, | 128 void examineBoxAfterEntering(const LayoutBox&, |
122 EBreak previousBreakAfterValue); | 129 EBreak previousBreakAfterValue); |
123 void examineBoxBeforeLeaving(const LayoutBox&); | 130 void examineBoxBeforeLeaving(const LayoutBox&); |
124 void examineLine(const RootInlineBox&); | 131 void examineLine(const RootInlineBox&); |
125 | 132 |
126 // Record that there's a pagination strut that ends at the specified |offsetIn
FlowThread|, which | 133 // Record that there's a pagination strut that ends at the specified |
127 // is an offset exactly at the top of some column. | 134 // |offsetInFlowThread|, which is an offset exactly at the top of some column. |
128 void recordStrutBeforeOffset(LayoutUnit offsetInFlowThread, LayoutUnit strut); | 135 void recordStrutBeforeOffset(LayoutUnit offsetInFlowThread, LayoutUnit strut); |
129 | 136 |
130 // Return the accumulated space used by struts at all column boundaries preced
ing the specified | 137 // Return the accumulated space used by struts at all column boundaries |
131 // flowthread offset. | 138 // preceding the specified flowthread offset. |
132 LayoutUnit spaceUsedByStrutsAt(LayoutUnit offsetInFlowThread) const; | 139 LayoutUnit spaceUsedByStrutsAt(LayoutUnit offsetInFlowThread) const; |
133 | 140 |
134 // Add a content run, specified by its end position. A content run is appended
at every | 141 // Add a content run, specified by its end position. A content run is appended |
135 // forced/explicit break and at the end of the column set. The content runs ar
e used to | 142 // at every forced/explicit break and at the end of the column set. The |
136 // determine where implicit/soft breaks will occur, in order to calculate an i
nitial column | 143 // content runs are used to determine where implicit/soft breaks will occur, |
137 // height. | 144 // in order to calculate an initial column height. |
138 void addContentRun(LayoutUnit endOffsetInFlowThread); | 145 void addContentRun(LayoutUnit endOffsetInFlowThread); |
139 | 146 |
140 // Return the index of the content run with the currently tallest columns, tak
ing all implicit | 147 // Return the index of the content run with the currently tallest columns, |
141 // breaks assumed so far into account. | 148 // taking all implicit breaks assumed so far into account. |
142 unsigned contentRunIndexWithTallestColumns() const; | 149 unsigned contentRunIndexWithTallestColumns() const; |
143 | 150 |
144 // Given the current list of content runs, make assumptions about where we nee
d to insert | 151 // Given the current list of content runs, make assumptions about where we |
145 // implicit breaks (if there's room for any at all; depending on the number of
explicit breaks), | 152 // need to insert implicit breaks (if there's room for any at all; depending |
146 // and store the results. This is needed in order to balance the columns. | 153 // on the number of explicit breaks), and store the results. This is needed in |
| 154 // order to balance the columns. |
147 void distributeImplicitBreaks(); | 155 void distributeImplicitBreaks(); |
148 | 156 |
149 // A run of content without explicit (forced) breaks; i.e. a flow thread porti
on between two | 157 // A run of content without explicit (forced) breaks; i.e. a flow thread |
150 // explicit breaks, between flow thread start and an explicit break, between a
n explicit break | 158 // portion between two explicit breaks, between flow thread start and an |
151 // and flow thread end, or, in cases when there are no explicit breaks at all:
between flow | 159 // explicit break, between an explicit break and flow thread end, or, in cases |
152 // thread portion start and flow thread portion end. We need to know where the
explicit breaks | 160 // when there are no explicit breaks at all: between flow thread portion start |
153 // are, in order to figure out where the implicit breaks will end up, so that
we get the columns | 161 // and flow thread portion end. We need to know where the explicit breaks are, |
154 // properly balanced. A content run starts out as representing one single colu
mn, and will | 162 // in order to figure out where the implicit breaks will end up, so that we |
155 // represent one additional column for each implicit break "inserted" there. | 163 // get the columns properly balanced. A content run starts out as representing |
| 164 // one single column, and will represent one additional column for each |
| 165 // implicit break "inserted" there. |
156 class ContentRun { | 166 class ContentRun { |
157 public: | 167 public: |
158 ContentRun(LayoutUnit breakOffset) | 168 ContentRun(LayoutUnit breakOffset) |
159 : m_breakOffset(breakOffset), m_assumedImplicitBreaks(0) {} | 169 : m_breakOffset(breakOffset), m_assumedImplicitBreaks(0) {} |
160 | 170 |
161 unsigned assumedImplicitBreaks() const { return m_assumedImplicitBreaks; } | 171 unsigned assumedImplicitBreaks() const { return m_assumedImplicitBreaks; } |
162 void assumeAnotherImplicitBreak() { m_assumedImplicitBreaks++; } | 172 void assumeAnotherImplicitBreak() { m_assumedImplicitBreaks++; } |
163 LayoutUnit breakOffset() const { return m_breakOffset; } | 173 LayoutUnit breakOffset() const { return m_breakOffset; } |
164 | 174 |
165 // Return the column height that this content run would require, considering
the implicit | 175 // Return the column height that this content run would require, considering |
166 // breaks assumed so far. | 176 // the implicit breaks assumed so far. |
167 LayoutUnit columnLogicalHeight(LayoutUnit startOffset) const { | 177 LayoutUnit columnLogicalHeight(LayoutUnit startOffset) const { |
168 return LayoutUnit::fromFloatCeil(float(m_breakOffset - startOffset) / | 178 return LayoutUnit::fromFloatCeil(float(m_breakOffset - startOffset) / |
169 float(m_assumedImplicitBreaks + 1)); | 179 float(m_assumedImplicitBreaks + 1)); |
170 } | 180 } |
171 | 181 |
172 private: | 182 private: |
173 LayoutUnit m_breakOffset; // Flow thread offset where this run ends. | 183 LayoutUnit m_breakOffset; // Flow thread offset where this run ends. |
174 unsigned | 184 unsigned m_assumedImplicitBreaks; // Number of implicit breaks in this run |
175 m_assumedImplicitBreaks; // Number of implicit breaks in this run assum
ed so far. | 185 // assumed so far. |
176 }; | 186 }; |
177 Vector<ContentRun, 32> m_contentRuns; | 187 Vector<ContentRun, 32> m_contentRuns; |
178 | 188 |
179 // Shortest strut found at each column boundary (index 0 being the boundary be
tween the first | 189 // Shortest strut found at each column boundary (index 0 being the boundary |
180 // and the second column, index 1 being the one between the second and the thi
rd boundary, and | 190 // between the first and the second column, index 1 being the one between the |
181 // so on). There may be several objects that cross the same column boundary, a
nd we're only | 191 // second and the third boundary, and so on). There may be several objects |
182 // interested in the shortest one. For example, when having a float beside reg
ular in-flow | 192 // that cross the same column boundary, and we're only interested in the |
183 // content, we end up with two parallel fragmentation flows [1]. The shortest
strut found at a | 193 // shortest one. For example, when having a float beside regular in-flow |
184 // column boundary is the amount of space that we wasted at said column bounda
ry, and it needs | 194 // content, we end up with two parallel fragmentation flows [1]. The shortest |
185 // to be deducted when estimating the initial balanced column height, or we ri
sk making the | 195 // strut found at a column boundary is the amount of space that we wasted at |
186 // column row too tall. An entry set to LayoutUnit::max() means that we didn't
detect any object | 196 // said column boundary, and it needs to be deducted when estimating the |
| 197 // initial balanced column height, or we risk making the column row too tall. |
| 198 // An entry set to LayoutUnit::max() means that we didn't detect any object |
187 // crossing that boundary. | 199 // crossing that boundary. |
188 // | 200 // |
189 // [1] http://www.w3.org/TR/css3-break/#parallel-flows | 201 // [1] http://www.w3.org/TR/css3-break/#parallel-flows |
190 Vector<LayoutUnit, 32> m_shortestStruts; | 202 Vector<LayoutUnit, 32> m_shortestStruts; |
191 | 203 |
192 LayoutUnit m_tallestUnbreakableLogicalHeight; | 204 LayoutUnit m_tallestUnbreakableLogicalHeight; |
193 }; | 205 }; |
194 | 206 |
195 // If we have previously used InitialColumnHeightFinder to estimate an initial c
olumn height, and | 207 // If we have previously used InitialColumnHeightFinder to estimate an initial |
196 // that didn't result in tall enough columns, we need subsequent layout passes w
here we increase | 208 // column height, and that didn't result in tall enough columns, we need |
197 // the column height by the minimum space shortage at column breaks. This class
finds the minimum | 209 // subsequent layout passes where we increase the column height by the minimum |
198 // space shortage after having laid out with the current column height. | 210 // space shortage at column breaks. This class finds the minimum space shortage |
| 211 // after having laid out with the current column height. |
199 class MinimumSpaceShortageFinder final : public ColumnBalancer { | 212 class MinimumSpaceShortageFinder final : public ColumnBalancer { |
200 public: | 213 public: |
201 MinimumSpaceShortageFinder(const LayoutMultiColumnSet&, | 214 MinimumSpaceShortageFinder(const LayoutMultiColumnSet&, |
202 LayoutUnit logicalTopInFlowThread, | 215 LayoutUnit logicalTopInFlowThread, |
203 LayoutUnit logicalBottomInFlowThread); | 216 LayoutUnit logicalBottomInFlowThread); |
204 | 217 |
205 LayoutUnit minimumSpaceShortage() const { return m_minimumSpaceShortage; } | 218 LayoutUnit minimumSpaceShortage() const { return m_minimumSpaceShortage; } |
206 unsigned forcedBreaksCount() const { return m_forcedBreaksCount; } | 219 unsigned forcedBreaksCount() const { return m_forcedBreaksCount; } |
207 | 220 |
208 private: | 221 private: |
209 void examineBoxAfterEntering(const LayoutBox&, | 222 void examineBoxAfterEntering(const LayoutBox&, |
210 EBreak previousBreakAfterValue); | 223 EBreak previousBreakAfterValue); |
211 void examineBoxBeforeLeaving(const LayoutBox&); | 224 void examineBoxBeforeLeaving(const LayoutBox&); |
212 void examineLine(const RootInlineBox&); | 225 void examineLine(const RootInlineBox&); |
213 | 226 |
214 void recordSpaceShortage(LayoutUnit shortage) { | 227 void recordSpaceShortage(LayoutUnit shortage) { |
215 // Only positive values are interesting (and allowed) here. Zero space short
age may | 228 // Only positive values are interesting (and allowed) here. Zero space |
216 // be reported when we're at the top of a column and the element has zero | 229 // shortage may be reported when we're at the top of a column and the |
217 // height. | 230 // element has zero height. |
218 if (shortage > 0) | 231 if (shortage > 0) |
219 m_minimumSpaceShortage = std::min(m_minimumSpaceShortage, shortage); | 232 m_minimumSpaceShortage = std::min(m_minimumSpaceShortage, shortage); |
220 } | 233 } |
221 | 234 |
222 // The smallest amout of space shortage that caused a column break. | 235 // The smallest amout of space shortage that caused a column break. |
223 LayoutUnit m_minimumSpaceShortage; | 236 LayoutUnit m_minimumSpaceShortage; |
224 | 237 |
225 // Set when breaking before a block, and we're looking for the first unbreakab
le descendant, in | 238 // Set when breaking before a block, and we're looking for the first |
226 // order to report correct space shortage for that one. | 239 // unbreakable descendant, in order to report correct space shortage for that |
| 240 // one. |
227 LayoutUnit m_pendingStrut; | 241 LayoutUnit m_pendingStrut; |
228 | 242 |
229 unsigned m_forcedBreaksCount; | 243 unsigned m_forcedBreaksCount; |
230 }; | 244 }; |
231 | 245 |
232 } // namespace blink | 246 } // namespace blink |
OLD | NEW |