OLD | NEW |
---|---|
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 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/ng/ng_layout_opportunity_iterator.h" | 5 #include "core/layout/ng/ng_layout_opportunity_iterator.h" |
6 | 6 |
7 #include "core/layout/ng/ng_exclusion.h" | 7 #include "core/layout/ng/ng_exclusion.h" |
8 #include "wtf/NonCopyingSort.h" | 8 #include "wtf/NonCopyingSort.h" |
9 #include "wtf/text/StringBuilder.h" | |
9 | 10 |
10 namespace blink { | 11 namespace blink { |
11 namespace { | 12 namespace { |
12 | 13 |
14 void AppendNodeToString(const NGLayoutOpportunityTreeNode* node, | |
15 StringBuilder* string_builder, | |
16 unsigned indent = 0) { | |
17 DCHECK(string_builder); | |
18 if (!node) { | |
19 string_builder->append("'null'\n"); | |
20 return; | |
21 } | |
22 | |
23 string_builder->append(node->ToString()); | |
24 string_builder->append("\n"); | |
25 | |
26 StringBuilder indent_builder; | |
27 for (unsigned i = 0; i < indent; i++) | |
28 indent_builder.append("\t"); | |
29 | |
30 if (node->IsLeafNode()) | |
31 return; | |
32 | |
33 string_builder->append(indent_builder.toString()); | |
34 string_builder->append("Left:\t"); | |
35 AppendNodeToString(node->left, string_builder, indent + 2); | |
36 string_builder->append(indent_builder.toString()); | |
37 string_builder->append("Right:\t"); | |
38 AppendNodeToString(node->right, string_builder, indent + 2); | |
39 string_builder->append(indent_builder.toString()); | |
40 string_builder->append("Bottom:\t"); | |
41 AppendNodeToString(node->bottom, string_builder, indent + 2); | |
42 } | |
43 | |
13 // Collects all opportunities from leaves of Layout Opportunity spatial tree. | 44 // Collects all opportunities from leaves of Layout Opportunity spatial tree. |
14 void CollectAllOpportunities(const NGLayoutOpportunityTreeNode* node, | 45 void CollectAllOpportunities(const NGLayoutOpportunityTreeNode* node, |
15 NGLayoutOpportunities& opportunities) { | 46 NGLayoutOpportunities& opportunities) { |
16 if (!node) | 47 if (!node) |
17 return; | 48 return; |
18 if (node->IsLeafNode()) | 49 if (node->IsLeafNode()) |
19 opportunities.push_back(node->opportunity); | 50 opportunities.push_back(node->opportunity); |
20 CollectAllOpportunities(node->left, opportunities); | 51 CollectAllOpportunities(node->left, opportunities); |
21 CollectAllOpportunities(node->bottom, opportunities); | 52 CollectAllOpportunities(node->bottom, opportunities); |
22 CollectAllOpportunities(node->right, opportunities); | 53 CollectAllOpportunities(node->right, opportunities); |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
121 NGLayoutOpportunity opportunity; | 152 NGLayoutOpportunity opportunity; |
122 opportunity.offset.inline_offset = exclusion.InlineEndOffset(); | 153 opportunity.offset.inline_offset = exclusion.InlineEndOffset(); |
123 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); | 154 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); |
124 opportunity.size.inline_size = right_opportunity_inline_size; | 155 opportunity.size.inline_size = right_opportunity_inline_size; |
125 opportunity.size.block_size = parent_opportunity.BlockSize(); | 156 opportunity.size.block_size = parent_opportunity.BlockSize(); |
126 return new NGLayoutOpportunityTreeNode(opportunity); | 157 return new NGLayoutOpportunityTreeNode(opportunity); |
127 } | 158 } |
128 return nullptr; | 159 return nullptr; |
129 } | 160 } |
130 | 161 |
162 void SplitNGLayoutOpportunityTreeNode(const NGLogicalRect& rect, | |
163 NGLayoutOpportunityTreeNode* node) { | |
164 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, rect); | |
165 node->right = CreateRightNGLayoutOpportunityTreeNode(node, rect); | |
166 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, rect); | |
167 } | |
168 | |
131 // Gets/Creates the "TOP" positioned constraint space by splitting | 169 // Gets/Creates the "TOP" positioned constraint space by splitting |
132 // the parent node with the exclusion. | 170 // the parent node with the exclusion. |
133 // | 171 // |
134 // @param parent_opportunity Parent opportunity that is being split. | 172 // @param parent_opportunity Parent opportunity that is being split. |
135 // @param exclusion Exclusion existed in the parent node constraint space. | 173 // @param exclusion Exclusion existed in the parent node constraint space. |
136 // @return New node or nullptr if the new block size == 0. | 174 // @return New node or nullptr if the new block size == 0. |
137 NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& parent_opportunity, | 175 NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& parent_opportunity, |
138 const NGLogicalRect& exclusion) { | 176 const NGLogicalRect& exclusion) { |
139 LayoutUnit top_opportunity_block_size = | 177 LayoutUnit top_opportunity_block_size = |
140 exclusion.BlockStartOffset() - parent_opportunity.BlockStartOffset(); | 178 exclusion.BlockStartOffset() - parent_opportunity.BlockStartOffset(); |
141 if (top_opportunity_block_size > 0) { | 179 if (top_opportunity_block_size > 0) { |
142 NGLayoutOpportunity opportunity; | 180 NGLayoutOpportunity opportunity; |
143 opportunity.offset.inline_offset = parent_opportunity.InlineStartOffset(); | 181 opportunity.offset.inline_offset = parent_opportunity.InlineStartOffset(); |
144 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); | 182 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); |
145 opportunity.size.inline_size = parent_opportunity.InlineSize(); | 183 opportunity.size.inline_size = parent_opportunity.InlineSize(); |
146 opportunity.size.block_size = top_opportunity_block_size; | 184 opportunity.size.block_size = top_opportunity_block_size; |
147 return opportunity; | 185 return opportunity; |
148 } | 186 } |
149 return NGLayoutOpportunity(); | 187 return NGLayoutOpportunity(); |
150 } | 188 } |
151 | 189 |
190 // Combines 2 exclusions if possible. | |
191 // We can combine 2 exclusions if they | |
192 // - adjoining to each other and have the same exclusion type | |
193 // - new exclusion shadows the old one. That's because it's not allowed to | |
194 // position anything in the shadowed area. | |
195 // | |
196 // Example: | |
197 // <div id="SS" style="float: left; height: 10px; width: 10px"></div> | |
198 // <div id="BB" style="float: left; height: 20px; width: 20px"></div> | |
199 // +----------------+ | |
200 // |SSBB | |
201 // |**BB | |
202 // We combine SS and BB exclusions including the shadowed area (**). | |
203 bool MaybeCombineExclusions(const NGExclusion& in_exclusion, | |
cbiesinger
2017/03/07 19:10:42
I had a bit of a hard time keeping track of in and
| |
204 NGExclusion* out_exclusion) { | |
205 NGLogicalRect in_rect = in_exclusion.rect; | |
206 NGLogicalRect& out_rect = out_exclusion->rect; | |
207 | |
208 switch (in_exclusion.type) { | |
209 case NGExclusion::kFloatLeft: { | |
210 NGLogicalOffset out_rect_top_right = {out_rect.InlineEndOffset(), | |
211 out_rect.BlockStartOffset()}; | |
212 if (out_exclusion->type == NGExclusion::kFloatLeft && | |
213 in_rect.offset == out_rect_top_right && | |
214 in_rect.BlockEndOffset() >= out_rect.BlockEndOffset()) { | |
215 out_rect.size = {in_rect.InlineSize() + out_rect.InlineSize(), | |
216 in_rect.BlockSize()}; | |
217 return true; | |
218 } | |
219 } | |
220 case NGExclusion::kFloatRight: { | |
221 NGLogicalOffset in_rect_top_right = {in_rect.InlineEndOffset(), | |
222 in_rect.BlockStartOffset()}; | |
223 if (out_exclusion->type == NGExclusion::kFloatRight && | |
224 out_rect.offset == in_rect_top_right && | |
225 in_rect.BlockEndOffset() >= out_rect.BlockEndOffset()) { | |
226 out_rect.offset = in_rect.offset; | |
227 out_rect.size = {in_rect.InlineSize() + out_rect.InlineSize(), | |
228 in_rect.BlockSize()}; | |
229 return true; | |
230 } | |
231 } | |
232 default: | |
233 NOTREACHED(); | |
234 return false; | |
235 } | |
236 return false; | |
237 } | |
238 | |
152 // Inserts the exclusion into the Layout Opportunity tree. | 239 // Inserts the exclusion into the Layout Opportunity tree. |
153 void InsertExclusion(NGLayoutOpportunityTreeNode* node, | 240 void InsertExclusion(NGLayoutOpportunityTreeNode* node, |
154 const NGExclusion* exclusion, | 241 const NGExclusion* exclusion, |
155 NGLayoutOpportunities& opportunities) { | 242 NGLayoutOpportunities& opportunities) { |
156 // Base case: size of the exclusion is empty. | 243 // Base case: size of the exclusion is empty. |
157 if (exclusion->rect.size.IsEmpty()) | 244 if (exclusion->rect.size.IsEmpty()) |
158 return; | 245 return; |
159 | 246 |
160 // Base case: there is no node. | 247 // Base case: there is no node. |
161 if (!node) | 248 if (!node) |
162 return; | 249 return; |
163 | 250 |
164 // Base case: exclusion is not in the node's constraint space. | 251 // Base case: exclusion is not in the node's constraint space. |
165 if (!exclusion->rect.IsContained(node->opportunity)) | 252 if (!exclusion->rect.IsContained(node->opportunity)) |
166 return; | 253 return; |
167 | 254 |
168 if (node->exclusion) { | 255 if (node->exclusions.isEmpty()) { |
256 SplitNGLayoutOpportunityTreeNode(exclusion->rect, node); | |
257 | |
258 NGLayoutOpportunity top_layout_opp = | |
259 GetTopSpace(node->opportunity, exclusion->rect); | |
260 if (!top_layout_opp.IsEmpty()) | |
261 opportunities.push_back(top_layout_opp); | |
262 | |
263 node->exclusions.push_back(exclusion); | |
264 node->combined_exclusion = WTF::makeUnique<NGExclusion>(*exclusion); | |
265 return; | |
266 } | |
267 | |
268 DCHECK(!node->exclusions.isEmpty()); | |
269 | |
270 if (MaybeCombineExclusions(*exclusion, node->combined_exclusion.get())) { | |
271 SplitNGLayoutOpportunityTreeNode(node->combined_exclusion->rect, node); | |
272 node->exclusions.push_back(exclusion); | |
273 } else { | |
169 InsertExclusion(node->left, exclusion, opportunities); | 274 InsertExclusion(node->left, exclusion, opportunities); |
170 InsertExclusion(node->bottom, exclusion, opportunities); | 275 InsertExclusion(node->bottom, exclusion, opportunities); |
171 InsertExclusion(node->right, exclusion, opportunities); | 276 InsertExclusion(node->right, exclusion, opportunities); |
172 return; | |
173 } | 277 } |
174 | |
175 // Split the current node. | |
176 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, exclusion->rect); | |
177 node->right = CreateRightNGLayoutOpportunityTreeNode(node, exclusion->rect); | |
178 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, exclusion->rect); | |
179 | |
180 NGLayoutOpportunity top_layout_opp = | |
181 GetTopSpace(node->opportunity, exclusion->rect); | |
182 if (!top_layout_opp.IsEmpty()) | |
183 opportunities.push_back(top_layout_opp); | |
184 | |
185 node->exclusion = exclusion; | |
186 } | 278 } |
187 | 279 |
188 // Compares exclusions by their top position. | 280 // Compares exclusions by their top position. |
189 bool CompareNGExclusionsByTopAsc( | 281 bool CompareNGExclusionsByTopAsc( |
190 const std::unique_ptr<const NGExclusion>& lhs, | 282 const std::unique_ptr<const NGExclusion>& lhs, |
191 const std::unique_ptr<const NGExclusion>& rhs) { | 283 const std::unique_ptr<const NGExclusion>& rhs) { |
192 return rhs->rect.offset.block_offset > lhs->rect.offset.block_offset; | 284 return rhs->rect.offset.block_offset > lhs->rect.offset.block_offset; |
193 } | 285 } |
194 | 286 |
195 // Compares Layout Opportunities by Start Point. | 287 // Compares Layout Opportunities by Start Point. |
(...skipping 72 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
268 } | 360 } |
269 | 361 |
270 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { | 362 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { |
271 if (opportunity_iter_ == opportunities_.end()) | 363 if (opportunity_iter_ == opportunities_.end()) |
272 return NGLayoutOpportunity(); | 364 return NGLayoutOpportunity(); |
273 auto* opportunity = opportunity_iter_; | 365 auto* opportunity = opportunity_iter_; |
274 opportunity_iter_++; | 366 opportunity_iter_++; |
275 return NGLayoutOpportunity(*opportunity); | 367 return NGLayoutOpportunity(*opportunity); |
276 } | 368 } |
277 | 369 |
370 #ifndef NDEBUG | |
371 void NGLayoutOpportunityIterator::ShowLayoutOpportunityTree() const { | |
372 StringBuilder string_builder; | |
373 string_builder.append("\n.:: LayoutOpportunity Tree ::.\n\nRoot Node: "); | |
374 AppendNodeToString(opportunity_tree_root_.get(), &string_builder); | |
375 fprintf(stderr, "%s\n", string_builder.toString().utf8().data()); | |
376 } | |
377 #endif | |
378 | |
278 } // namespace blink | 379 } // namespace blink |
OLD | NEW |