Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(11)

Side by Side Diff: third_party/WebKit/Source/core/layout/ColumnBalancer.h

Issue 2395683002: Revert of Reformat comments in core/layout up until LayoutBox (Closed)
Patch Set: Created 4 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/core/layout/ClipRectsCache.h ('k') | third_party/WebKit/Source/core/layout/ColumnBalancer.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698