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_constraint_space.h" | 7 #include "core/layout/ng/ng_constraint_space.h" |
8 #include "core/layout/ng/ng_exclusion.h" | 8 #include "core/layout/ng/ng_exclusion.h" |
9 #include "wtf/NonCopyingSort.h" | 9 #include "wtf/NonCopyingSort.h" |
10 #include "wtf/text/StringBuilder.h" | 10 #include "wtf/text/StringBuilder.h" |
(...skipping 10 matching lines...) Expand all Loading... |
21 return; | 21 return; |
22 } | 22 } |
23 | 23 |
24 string_builder->append(node->ToString()); | 24 string_builder->append(node->ToString()); |
25 string_builder->append("\n"); | 25 string_builder->append("\n"); |
26 | 26 |
27 StringBuilder indent_builder; | 27 StringBuilder indent_builder; |
28 for (unsigned i = 0; i < indent; i++) | 28 for (unsigned i = 0; i < indent; i++) |
29 indent_builder.append("\t"); | 29 indent_builder.append("\t"); |
30 | 30 |
31 if (!node->exclusion) | 31 if (node->IsLeafNode()) |
32 return; | 32 return; |
33 | 33 |
34 string_builder->append(indent_builder.toString()); | 34 string_builder->append(indent_builder.toString()); |
35 string_builder->append("Left:\t"); | 35 string_builder->append("Left:\t"); |
36 AppendNodeToString(node->left, string_builder, indent + 2); | 36 AppendNodeToString(node->left, string_builder, indent + 2); |
37 string_builder->append(indent_builder.toString()); | 37 string_builder->append(indent_builder.toString()); |
38 string_builder->append("Right:\t"); | 38 string_builder->append("Right:\t"); |
39 AppendNodeToString(node->right, string_builder, indent + 2); | 39 AppendNodeToString(node->right, string_builder, indent + 2); |
40 string_builder->append(indent_builder.toString()); | 40 string_builder->append(indent_builder.toString()); |
41 string_builder->append("Bottom:\t"); | 41 string_builder->append("Bottom:\t"); |
(...skipping 111 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
153 NGLayoutOpportunity opportunity; | 153 NGLayoutOpportunity opportunity; |
154 opportunity.offset.inline_offset = exclusion.InlineEndOffset(); | 154 opportunity.offset.inline_offset = exclusion.InlineEndOffset(); |
155 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); | 155 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); |
156 opportunity.size.inline_size = right_opportunity_inline_size; | 156 opportunity.size.inline_size = right_opportunity_inline_size; |
157 opportunity.size.block_size = parent_opportunity.BlockSize(); | 157 opportunity.size.block_size = parent_opportunity.BlockSize(); |
158 return new NGLayoutOpportunityTreeNode(opportunity); | 158 return new NGLayoutOpportunityTreeNode(opportunity); |
159 } | 159 } |
160 return nullptr; | 160 return nullptr; |
161 } | 161 } |
162 | 162 |
| 163 void SplitNGLayoutOpportunityTreeNode(const NGLogicalRect& rect, |
| 164 NGLayoutOpportunityTreeNode* node) { |
| 165 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, rect); |
| 166 node->right = CreateRightNGLayoutOpportunityTreeNode(node, rect); |
| 167 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, rect); |
| 168 } |
| 169 |
163 // Gets/Creates the "TOP" positioned constraint space by splitting | 170 // Gets/Creates the "TOP" positioned constraint space by splitting |
164 // the parent node with the exclusion. | 171 // the parent node with the exclusion. |
165 // | 172 // |
166 // @param parent_opportunity Parent opportunity that is being split. | 173 // @param parent_opportunity Parent opportunity that is being split. |
167 // @param exclusion Exclusion existed in the parent node constraint space. | 174 // @param exclusion Exclusion existed in the parent node constraint space. |
168 // @return New node or nullptr if the new block size == 0. | 175 // @return New node or nullptr if the new block size == 0. |
169 NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& parent_opportunity, | 176 NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& parent_opportunity, |
170 const NGLogicalRect& exclusion) { | 177 const NGLogicalRect& exclusion) { |
171 LayoutUnit top_opportunity_block_size = | 178 LayoutUnit top_opportunity_block_size = |
172 exclusion.BlockStartOffset() - parent_opportunity.BlockStartOffset(); | 179 exclusion.BlockStartOffset() - parent_opportunity.BlockStartOffset(); |
(...skipping 17 matching lines...) Expand all Loading... |
190 return; | 197 return; |
191 | 198 |
192 // Base case: there is no node. | 199 // Base case: there is no node. |
193 if (!node) | 200 if (!node) |
194 return; | 201 return; |
195 | 202 |
196 // Base case: exclusion is not in the node's constraint space. | 203 // Base case: exclusion is not in the node's constraint space. |
197 if (!exclusion->rect.IsContained(node->opportunity)) | 204 if (!exclusion->rect.IsContained(node->opportunity)) |
198 return; | 205 return; |
199 | 206 |
200 if (node->exclusion) { | 207 if (node->exclusions.isEmpty()) { |
| 208 SplitNGLayoutOpportunityTreeNode(exclusion->rect, node); |
| 209 |
| 210 NGLayoutOpportunity top_layout_opp = |
| 211 GetTopSpace(node->opportunity, exclusion->rect); |
| 212 if (!top_layout_opp.IsEmpty()) |
| 213 opportunities.push_back(top_layout_opp); |
| 214 |
| 215 node->exclusions.push_back(exclusion); |
| 216 node->combined_exclusion = WTF::makeUnique<NGExclusion>(*exclusion); |
| 217 return; |
| 218 } |
| 219 |
| 220 DCHECK(!node->exclusions.isEmpty()); |
| 221 |
| 222 if (node->combined_exclusion->MaybeCombineWith(*exclusion)) { |
| 223 SplitNGLayoutOpportunityTreeNode(node->combined_exclusion->rect, node); |
| 224 node->exclusions.push_back(exclusion); |
| 225 } else { |
201 InsertExclusion(node->left, exclusion, opportunities); | 226 InsertExclusion(node->left, exclusion, opportunities); |
202 InsertExclusion(node->bottom, exclusion, opportunities); | 227 InsertExclusion(node->bottom, exclusion, opportunities); |
203 InsertExclusion(node->right, exclusion, opportunities); | 228 InsertExclusion(node->right, exclusion, opportunities); |
204 return; | |
205 } | 229 } |
206 | |
207 // Split the current node. | |
208 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, exclusion->rect); | |
209 node->right = CreateRightNGLayoutOpportunityTreeNode(node, exclusion->rect); | |
210 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, exclusion->rect); | |
211 | |
212 NGLayoutOpportunity top_layout_opp = | |
213 GetTopSpace(node->opportunity, exclusion->rect); | |
214 if (!top_layout_opp.IsEmpty()) | |
215 opportunities.push_back(top_layout_opp); | |
216 | |
217 node->exclusion = exclusion; | |
218 } | 230 } |
219 | 231 |
220 // Compares exclusions by their top position. | 232 // Compares exclusions by their top position. |
221 bool CompareNGExclusionsByTopAsc( | 233 bool CompareNGExclusionsByTopAsc( |
222 const std::unique_ptr<const NGExclusion>& lhs, | 234 const std::unique_ptr<const NGExclusion>& lhs, |
223 const std::unique_ptr<const NGExclusion>& rhs) { | 235 const std::unique_ptr<const NGExclusion>& rhs) { |
224 return rhs->rect.offset.block_offset > lhs->rect.offset.block_offset; | 236 return rhs->rect.offset.block_offset > lhs->rect.offset.block_offset; |
225 } | 237 } |
226 | 238 |
227 // Compares Layout Opportunities by Start Point. | 239 // Compares Layout Opportunities by Start Point. |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
310 #ifndef NDEBUG | 322 #ifndef NDEBUG |
311 void NGLayoutOpportunityIterator::ShowLayoutOpportunityTree() const { | 323 void NGLayoutOpportunityIterator::ShowLayoutOpportunityTree() const { |
312 StringBuilder string_builder; | 324 StringBuilder string_builder; |
313 string_builder.append("\n.:: LayoutOpportunity Tree ::.\n\nRoot Node: "); | 325 string_builder.append("\n.:: LayoutOpportunity Tree ::.\n\nRoot Node: "); |
314 AppendNodeToString(opportunity_tree_root_.get(), &string_builder); | 326 AppendNodeToString(opportunity_tree_root_.get(), &string_builder); |
315 fprintf(stderr, "%s\n", string_builder.toString().utf8().data()); | 327 fprintf(stderr, "%s\n", string_builder.toString().utf8().data()); |
316 } | 328 } |
317 #endif | 329 #endif |
318 | 330 |
319 } // namespace blink | 331 } // namespace blink |
OLD | NEW |