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