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_physical_constraint_space.h" | 7 #include "core/layout/ng/ng_physical_constraint_space.h" |
8 #include "core/layout/ng/ng_units.h" | 8 #include "core/layout/ng/ng_units.h" |
9 #include "wtf/NonCopyingSort.h" | 9 #include "wtf/NonCopyingSort.h" |
10 | 10 |
(...skipping 132 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
143 opportunity.size.block_size = top_opportunity_block_size; | 143 opportunity.size.block_size = top_opportunity_block_size; |
144 return opportunity; | 144 return opportunity; |
145 } | 145 } |
146 return NGLayoutOpportunity(); | 146 return NGLayoutOpportunity(); |
147 } | 147 } |
148 | 148 |
149 // Inserts the exclusion into the Layout Opportunity tree. | 149 // Inserts the exclusion into the Layout Opportunity tree. |
150 void InsertExclusion(NGLayoutOpportunityTreeNode* node, | 150 void InsertExclusion(NGLayoutOpportunityTreeNode* node, |
151 const NGLogicalRect* exclusion, | 151 const NGLogicalRect* exclusion, |
152 NGLayoutOpportunities& opportunities) { | 152 NGLayoutOpportunities& opportunities) { |
153 // Base case: size of the exclusion is empty. | |
154 if (exclusion->size.IsEmpty()) | |
155 return; | |
156 | |
157 // Base case: there is no node. | 153 // Base case: there is no node. |
158 if (!node) | 154 if (!node) |
159 return; | 155 return; |
160 | 156 |
161 // Base case: exclusion is not in the node's constraint space. | 157 // Base case: exclusion is not in the node's constraint space. |
162 if (!exclusion->IsContained(node->opportunity)) | 158 if (!exclusion->IsContained(node->opportunity)) |
163 return; | 159 return; |
164 | 160 |
165 if (node->exclusion) { | 161 if (node->exclusion) { |
166 InsertExclusion(node->left, exclusion, opportunities); | 162 InsertExclusion(node->left, exclusion, opportunities); |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
207 return true; | 203 return true; |
208 } | 204 } |
209 if (rhs.offset.inline_offset < lhs.offset.inline_offset) { | 205 if (rhs.offset.inline_offset < lhs.offset.inline_offset) { |
210 return false; | 206 return false; |
211 } | 207 } |
212 | 208 |
213 // TOP and LEFT are the same -> Sort by width | 209 // TOP and LEFT are the same -> Sort by width |
214 return rhs.size.inline_size < lhs.size.inline_size; | 210 return rhs.size.inline_size < lhs.size.inline_size; |
215 } | 211 } |
216 | 212 |
217 void RunPreconditionChecks(const NGConstraintSpace& space, | |
218 const NGLogicalOffset& origin_point, | |
219 const NGLogicalOffset& leader_point) { | |
220 DCHECK_GE(origin_point, space.Offset()) | |
221 << "Origin point" << origin_point | |
222 << " should lay below the constraint space's offset " << space.Offset(); | |
223 | |
224 DCHECK_GE(leader_point, space.Offset()) | |
225 << "Leader point" << leader_point | |
226 << " should lay below the constraint space's offset " << space.Offset(); | |
227 } | |
228 | |
229 NGLogicalRect ToLeaderExclusion(const NGLogicalOffset& origin_point, | |
230 const NGLogicalOffset& leader_point) { | |
231 LayoutUnit inline_size = | |
232 leader_point.inline_offset - origin_point.inline_offset; | |
233 LayoutUnit block_size = leader_point.block_offset - origin_point.block_offset; | |
234 | |
235 NGLogicalRect leader_exclusion; | |
236 leader_exclusion.offset = origin_point; | |
237 leader_exclusion.size = {inline_size, block_size}; | |
238 return leader_exclusion; | |
239 } | |
240 | |
241 } // namespace | 213 } // namespace |
242 | 214 |
243 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( | 215 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( |
244 NGConstraintSpace* space, | 216 NGConstraintSpace* space, |
245 const NGLogicalOffset& origin_point, | 217 const NGLogicalOffset origin_point, |
246 const NGLogicalOffset& leader_point) | 218 const NGLogicalOffset leader_point) |
247 : constraint_space_(space) { | 219 : constraint_space_(space), leader_point_(leader_point) { |
248 RunPreconditionChecks(*space, origin_point, leader_point); | |
249 | |
250 // TODO(chrome-layout-team): Combine exclusions that shadow each other. | 220 // TODO(chrome-layout-team): Combine exclusions that shadow each other. |
251 auto& exclusions = constraint_space_->PhysicalSpace()->Exclusions(); | 221 auto& exclusions = constraint_space_->PhysicalSpace()->Exclusions(); |
252 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), | 222 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), |
253 &CompareNGExclusionsByTopAsc)) | 223 &CompareNGExclusionsByTopAsc)) |
254 << "Exclusions are expected to be sorted by TOP"; | 224 << "Exclusions are expected to be sorted by TOP"; |
255 | 225 |
256 NGLayoutOpportunity initial_opportunity = | 226 NGLayoutOpportunity initial_opportunity = |
257 CreateLayoutOpportunityFromConstraintSpace(*space, origin_point); | 227 CreateLayoutOpportunityFromConstraintSpace(*space, origin_point); |
258 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(initial_opportunity); | 228 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(initial_opportunity); |
259 | 229 |
260 const NGLogicalRect leader_exclusion = | |
261 ToLeaderExclusion(origin_point, leader_point); | |
262 InsertExclusion(MutableOpportunityTreeRoot(), &leader_exclusion, | |
263 opportunities_); | |
264 | |
265 for (const auto& exclusion : exclusions) { | 230 for (const auto& exclusion : exclusions) { |
266 InsertExclusion(MutableOpportunityTreeRoot(), exclusion.get(), | 231 InsertExclusion(MutableOpportunityTreeRoot(), exclusion.get(), |
267 opportunities_); | 232 opportunities_); |
268 } | 233 } |
269 CollectAllOpportunities(OpportunityTreeRoot(), opportunities_); | 234 CollectAllOpportunities(OpportunityTreeRoot(), opportunities_); |
270 std::sort(opportunities_.begin(), opportunities_.end(), | 235 std::sort(opportunities_.begin(), opportunities_.end(), |
271 &CompareNGLayoutOpportunitesByStartPoint); | 236 &CompareNGLayoutOpportunitesByStartPoint); |
272 | 237 |
273 opportunity_iter_ = opportunities_.begin(); | 238 opportunity_iter_ = opportunities_.begin(); |
274 } | 239 } |
275 | 240 |
276 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { | 241 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { |
277 if (opportunity_iter_ == opportunities_.end()) | 242 if (opportunity_iter_ == opportunities_.end()) |
278 return NGLayoutOpportunity(); | 243 return NGLayoutOpportunity(); |
279 auto* opportunity = opportunity_iter_; | 244 auto* opportunity = opportunity_iter_; |
280 opportunity_iter_++; | 245 opportunity_iter_++; |
281 return NGLayoutOpportunity(*opportunity); | 246 return NGLayoutOpportunity(*opportunity); |
282 } | 247 } |
283 | 248 |
284 } // namespace blink | 249 } // namespace blink |
OLD | NEW |