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

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

Issue 2391893004: Reformat comments in core/layout up until LayoutBox (Closed)
Patch Set: Rebase w/HEAD (again) 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 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
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