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 25 matching lines...) Expand all Loading... |
36 opportunity.size.inline_size -= origin_point.inline_offset; | 36 opportunity.size.inline_size -= origin_point.inline_offset; |
37 opportunity.size.block_size -= origin_point.block_offset; | 37 opportunity.size.block_size -= origin_point.block_offset; |
38 return opportunity; | 38 return opportunity; |
39 } | 39 } |
40 | 40 |
41 // Whether 2 edges overlap with each other. | 41 // Whether 2 edges overlap with each other. |
42 bool IsOverlapping(const NGEdge& edge1, const NGEdge& edge2) { | 42 bool IsOverlapping(const NGEdge& edge1, const NGEdge& edge2) { |
43 return std::max(edge1.start, edge2.start) <= std::min(edge1.end, edge2.end); | 43 return std::max(edge1.start, edge2.start) <= std::min(edge1.end, edge2.end); |
44 } | 44 } |
45 | 45 |
46 // Whether the exclusion is out of bounds of the LayoutNG constraint space. | |
47 bool IsExclusionWithinSpace(const NGLayoutOpportunity& opportunity, | |
48 const NGExclusion& exclusion) { | |
49 LayoutUnit left = opportunity.offset.inline_offset; | |
50 LayoutUnit top = opportunity.offset.block_offset; | |
51 LayoutUnit right = left + opportunity.size.inline_size; | |
52 LayoutUnit bottom = top + opportunity.size.block_size; | |
53 | |
54 return !(exclusion.Right() <= left || exclusion.Bottom() <= top || | |
55 exclusion.Left() >= right || exclusion.Top() >= bottom); | |
56 } | |
57 | |
58 // Creates the *BOTTOM* positioned Layout Opportunity tree node by splitting | 46 // Creates the *BOTTOM* positioned Layout Opportunity tree node by splitting |
59 // the parent node with the exclusion. | 47 // the parent node with the exclusion. |
60 // | 48 // |
61 // @param parent_node Node that needs to be split. | 49 // @param parent_node Node that needs to be split. |
62 // @param exclusion Exclusion existed in the parent node constraint space. | 50 // @param exclusion Exclusion existed in the parent node constraint space. |
63 // @return New node or nullptr if the new block size == 0. | 51 // @return New node or nullptr if the new block size == 0. |
64 NGLayoutOpportunityTreeNode* CreateBottomNGLayoutOpportunityTreeNode( | 52 NGLayoutOpportunityTreeNode* CreateBottomNGLayoutOpportunityTreeNode( |
65 const NGLayoutOpportunityTreeNode* parent_node, | 53 const NGLayoutOpportunityTreeNode* parent_node, |
66 const NGExclusion& exclusion) { | 54 const NGLogicalRect& exclusion) { |
67 const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity; | 55 const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity; |
68 LayoutUnit left = parent_opportunity.offset.inline_offset; | 56 LayoutUnit bottom_opportunity_block_size = |
69 LayoutUnit top = exclusion.Bottom(); | 57 parent_opportunity.BlockEndOffset() - exclusion.BlockEndOffset(); |
70 LayoutUnit right = left + parent_opportunity.size.inline_size; | 58 if (bottom_opportunity_block_size > 0) { |
71 LayoutUnit bottom = parent_opportunity.offset.block_offset + | 59 NGLayoutOpportunity opportunity; |
72 parent_opportunity.size.block_size; | 60 opportunity.offset.inline_offset = parent_opportunity.InlineStartOffset(); |
73 | 61 opportunity.offset.block_offset = exclusion.BlockEndOffset(); |
74 NGEdge exclusion_edge = {exclusion.Left(), exclusion.Right()}; | 62 opportunity.size.inline_size = parent_opportunity.InlineSize(); |
75 LayoutUnit block_size = bottom - top; | 63 opportunity.size.block_size = bottom_opportunity_block_size; |
76 if (block_size > 0) { | 64 NGEdge exclusion_edge = {/* start */ exclusion.InlineStartOffset(), |
77 NGLayoutOpportunity opportunity(left, top, right - left, block_size); | 65 /* end */ exclusion.InlineEndOffset()}; |
78 return new NGLayoutOpportunityTreeNode(opportunity, exclusion_edge); | 66 return new NGLayoutOpportunityTreeNode(opportunity, exclusion_edge); |
79 } | 67 } |
80 return nullptr; | 68 return nullptr; |
81 } | 69 } |
82 | 70 |
83 // Creates the *LEFT* positioned Layout Opportunity tree node by splitting | 71 // Creates the *LEFT* positioned Layout Opportunity tree node by splitting |
84 // the parent node with the exclusion. | 72 // the parent node with the exclusion. |
85 // | 73 // |
86 // @param parent_node Node that needs to be split. | 74 // @param parent_node Node that needs to be split. |
87 // @param exclusion Exclusion existed in the parent node constraint space. | 75 // @param exclusion Exclusion existed in the parent node constraint space. |
88 // @return New node or nullptr if the new inline size == 0 or the parent's | 76 // @return New node or nullptr if the new inline size == 0 or the parent's |
89 // exclusion edge doesn't limit the new node's constraint space. | 77 // exclusion edge doesn't limit the new node's constraint space. |
90 NGLayoutOpportunityTreeNode* CreateLeftNGLayoutOpportunityTreeNode( | 78 NGLayoutOpportunityTreeNode* CreateLeftNGLayoutOpportunityTreeNode( |
91 const NGLayoutOpportunityTreeNode* parent_node, | 79 const NGLayoutOpportunityTreeNode* parent_node, |
92 const NGExclusion& exclusion) { | 80 const NGLogicalRect& exclusion) { |
93 const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity; | 81 const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity; |
94 LayoutUnit left = parent_opportunity.offset.inline_offset; | |
95 LayoutUnit top = parent_opportunity.offset.block_offset; | |
96 LayoutUnit right = exclusion.Left(); | |
97 LayoutUnit bottom = top + parent_opportunity.size.block_size; | |
98 | 82 |
99 NGEdge node_edge = {left, right}; | 83 LayoutUnit left_opportunity_inline_size = |
100 LayoutUnit inline_size = right - left; | 84 exclusion.InlineStartOffset() - parent_opportunity.InlineStartOffset(); |
101 if (inline_size > 0 && | 85 NGEdge node_edge = {/* start */ parent_opportunity.InlineStartOffset(), |
| 86 /* end */ exclusion.InlineStartOffset()}; |
| 87 |
| 88 if (left_opportunity_inline_size > 0 && |
102 IsOverlapping(parent_node->exclusion_edge, node_edge)) { | 89 IsOverlapping(parent_node->exclusion_edge, node_edge)) { |
103 NGLayoutOpportunity opportunity(left, top, inline_size, bottom - top); | 90 NGLayoutOpportunity opportunity; |
| 91 opportunity.offset.inline_offset = parent_opportunity.InlineStartOffset(); |
| 92 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); |
| 93 opportunity.size.inline_size = left_opportunity_inline_size; |
| 94 opportunity.size.block_size = parent_opportunity.BlockSize(); |
104 return new NGLayoutOpportunityTreeNode(opportunity); | 95 return new NGLayoutOpportunityTreeNode(opportunity); |
105 } | 96 } |
106 return nullptr; | 97 return nullptr; |
107 } | 98 } |
108 | 99 |
109 // Creates the *RIGHT* positioned Layout Opportunity tree node by splitting | 100 // Creates the *RIGHT* positioned Layout Opportunity tree node by splitting |
110 // the parent node with the exclusion. | 101 // the parent node with the exclusion. |
111 // | 102 // |
112 // @param parent_node Node that needs to be split. | 103 // @param parent_node Node that needs to be split. |
113 // @param exclusion Exclusion existed in the parent node constraint space. | 104 // @param exclusion Exclusion existed in the parent node constraint space. |
114 // @return New node or nullptr if the new inline size == 0 or the parent's | 105 // @return New node or nullptr if the new inline size == 0 or the parent's |
115 // exclusion edge doesn't limit the new node's constraint space. | 106 // exclusion edge doesn't limit the new node's constraint space. |
116 NGLayoutOpportunityTreeNode* CreateRightNGLayoutOpportunityTreeNode( | 107 NGLayoutOpportunityTreeNode* CreateRightNGLayoutOpportunityTreeNode( |
117 const NGLayoutOpportunityTreeNode* parent_node, | 108 const NGLayoutOpportunityTreeNode* parent_node, |
118 const NGExclusion& exclusion) { | 109 const NGLogicalRect& exclusion) { |
119 const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity; | 110 const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity; |
120 LayoutUnit left = exclusion.Right(); | |
121 LayoutUnit top = parent_opportunity.offset.block_offset; | |
122 LayoutUnit right = parent_opportunity.offset.inline_offset + | |
123 parent_opportunity.size.inline_size; | |
124 LayoutUnit bottom = top + parent_opportunity.size.block_size; | |
125 | 111 |
126 NGEdge node_edge = {left, right}; | 112 NGEdge node_edge = {/* start */ exclusion.InlineEndOffset(), |
127 LayoutUnit inline_size = right - left; | 113 /* end */ parent_opportunity.InlineEndOffset()}; |
128 if (inline_size > 0 && | 114 LayoutUnit right_opportunity_inline_size = |
| 115 parent_opportunity.InlineEndOffset() - exclusion.InlineEndOffset(); |
| 116 if (right_opportunity_inline_size > 0 && |
129 IsOverlapping(parent_node->exclusion_edge, node_edge)) { | 117 IsOverlapping(parent_node->exclusion_edge, node_edge)) { |
130 NGLayoutOpportunity opportunity(left, top, inline_size, bottom - top); | 118 NGLayoutOpportunity opportunity; |
| 119 opportunity.offset.inline_offset = exclusion.InlineEndOffset(); |
| 120 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); |
| 121 opportunity.size.inline_size = right_opportunity_inline_size; |
| 122 opportunity.size.block_size = parent_opportunity.BlockSize(); |
131 return new NGLayoutOpportunityTreeNode(opportunity); | 123 return new NGLayoutOpportunityTreeNode(opportunity); |
132 } | 124 } |
133 return nullptr; | 125 return nullptr; |
134 } | 126 } |
135 | 127 |
136 // Gets/Creates the "TOP" positioned constraint space by splitting | 128 // Gets/Creates the "TOP" positioned constraint space by splitting |
137 // the parent node with the exclusion. | 129 // the parent node with the exclusion. |
138 // | 130 // |
139 // @param parent_node Node that needs to be split. | 131 // @param parent_opportunity Parent opportunity that is being split. |
140 // @param exclusion Exclusion existed in the parent node constraint space. | 132 // @param exclusion Exclusion existed in the parent node constraint space. |
141 // @return New node or nullptr if the new block size == 0. | 133 // @return New node or nullptr if the new block size == 0. |
142 NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& rect, | 134 NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& parent_opportunity, |
143 const NGExclusion& exclusion) { | 135 const NGLogicalRect& exclusion) { |
144 LayoutUnit left = rect.offset.inline_offset; | 136 LayoutUnit top_opportunity_block_size = |
145 LayoutUnit top = rect.offset.block_offset; | 137 exclusion.BlockStartOffset() - parent_opportunity.BlockStartOffset(); |
146 LayoutUnit right = left + rect.size.inline_size; | 138 if (top_opportunity_block_size > 0) { |
147 LayoutUnit bottom = exclusion.Top(); | 139 NGLayoutOpportunity opportunity; |
148 | 140 opportunity.offset.inline_offset = parent_opportunity.InlineStartOffset(); |
149 LayoutUnit block_size = bottom - top; | 141 opportunity.offset.block_offset = parent_opportunity.BlockStartOffset(); |
150 if (block_size > 0) | 142 opportunity.size.inline_size = parent_opportunity.InlineSize(); |
151 return NGLayoutOpportunity(left, top, right - left, block_size); | 143 opportunity.size.block_size = top_opportunity_block_size; |
152 | 144 return opportunity; |
| 145 } |
153 return NGLayoutOpportunity(); | 146 return NGLayoutOpportunity(); |
154 } | 147 } |
155 | 148 |
156 // Inserts the exclusion into the Layout Opportunity tree. | 149 // Inserts the exclusion into the Layout Opportunity tree. |
157 void InsertExclusion(NGLayoutOpportunityTreeNode* node, | 150 void InsertExclusion(NGLayoutOpportunityTreeNode* node, |
158 const NGExclusion* exclusion, | 151 const NGLogicalRect* exclusion, |
159 NGLayoutOpportunities& opportunities) { | 152 NGLayoutOpportunities& opportunities) { |
160 // Base case: there is no node. | 153 // Base case: there is no node. |
161 if (!node) | 154 if (!node) |
162 return; | 155 return; |
163 | 156 |
164 // Base case: exclusion is not in the node's constraint space. | 157 // Base case: exclusion is not in the node's constraint space. |
165 if (!IsExclusionWithinSpace(node->opportunity, *exclusion)) | 158 if (!exclusion->IsContained(node->opportunity)) |
166 return; | 159 return; |
167 | 160 |
168 if (node->exclusion) { | 161 if (node->exclusion) { |
169 InsertExclusion(node->left, exclusion, opportunities); | 162 InsertExclusion(node->left, exclusion, opportunities); |
170 InsertExclusion(node->bottom, exclusion, opportunities); | 163 InsertExclusion(node->bottom, exclusion, opportunities); |
171 InsertExclusion(node->right, exclusion, opportunities); | 164 InsertExclusion(node->right, exclusion, opportunities); |
172 return; | 165 return; |
173 } | 166 } |
174 | 167 |
175 // Split the current node. | 168 // Split the current node. |
176 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, *exclusion); | 169 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, *exclusion); |
177 node->right = CreateRightNGLayoutOpportunityTreeNode(node, *exclusion); | 170 node->right = CreateRightNGLayoutOpportunityTreeNode(node, *exclusion); |
178 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, *exclusion); | 171 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, *exclusion); |
179 | 172 |
180 NGLayoutOpportunity top_layout_opp = | 173 NGLayoutOpportunity top_layout_opp = |
181 GetTopSpace(node->opportunity, *exclusion); | 174 GetTopSpace(node->opportunity, *exclusion); |
182 if (!top_layout_opp.IsEmpty()) | 175 if (!top_layout_opp.IsEmpty()) |
183 opportunities.append(top_layout_opp); | 176 opportunities.append(top_layout_opp); |
184 | 177 |
185 node->exclusion = exclusion; | 178 node->exclusion = exclusion; |
186 } | 179 } |
187 | 180 |
188 // Compares exclusions by their top position. | 181 // Compares exclusions by their top position. |
189 bool CompareNGExclusionsByTopAsc(const Member<const NGExclusion>& lhs, | 182 bool CompareNGExclusionsByTopAsc( |
190 const Member<const NGExclusion>& rhs) { | 183 const std::unique_ptr<const NGLogicalRect>& lhs, |
191 return rhs->Top() > lhs->Top(); | 184 const std::unique_ptr<const NGLogicalRect>& rhs) { |
| 185 return rhs->offset.block_offset > lhs->offset.block_offset; |
192 } | 186 } |
193 | 187 |
194 // Compares Layout Opportunities by Start Point. | 188 // Compares Layout Opportunities by Start Point. |
195 // Start point is a TopLeft position from where inline content can potentially | 189 // Start point is a TopLeft position from where inline content can potentially |
196 // start positioning itself. | 190 // start positioning itself. |
197 bool CompareNGLayoutOpportunitesByStartPoint(const NGLayoutOpportunity& lhs, | 191 bool CompareNGLayoutOpportunitesByStartPoint(const NGLayoutOpportunity& lhs, |
198 const NGLayoutOpportunity& rhs) { | 192 const NGLayoutOpportunity& rhs) { |
199 // sort by TOP. | 193 // sort by TOP. |
200 if (rhs.offset.block_offset > lhs.offset.block_offset) { | 194 if (rhs.offset.block_offset > lhs.offset.block_offset) { |
201 return true; | 195 return true; |
(...skipping 15 matching lines...) Expand all Loading... |
217 } | 211 } |
218 | 212 |
219 } // namespace | 213 } // namespace |
220 | 214 |
221 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( | 215 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( |
222 NGConstraintSpace* space, | 216 NGConstraintSpace* space, |
223 const NGLogicalOffset origin_point, | 217 const NGLogicalOffset origin_point, |
224 const NGLogicalOffset leader_point) | 218 const NGLogicalOffset leader_point) |
225 : constraint_space_(space), leader_point_(leader_point) { | 219 : constraint_space_(space), leader_point_(leader_point) { |
226 // TODO(chrome-layout-team): Combine exclusions that shadow each other. | 220 // TODO(chrome-layout-team): Combine exclusions that shadow each other. |
227 auto exclusions = constraint_space_->PhysicalSpace()->Exclusions(); | 221 auto& exclusions = constraint_space_->PhysicalSpace()->Exclusions(); |
228 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), | 222 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), |
229 &CompareNGExclusionsByTopAsc)) | 223 &CompareNGExclusionsByTopAsc)) |
230 << "Exclusions are expected to be sorted by TOP"; | 224 << "Exclusions are expected to be sorted by TOP"; |
231 | 225 |
232 NGLayoutOpportunity initial_opportunity = | 226 NGLayoutOpportunity initial_opportunity = |
233 CreateLayoutOpportunityFromConstraintSpace(*space, origin_point); | 227 CreateLayoutOpportunityFromConstraintSpace(*space, origin_point); |
234 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(initial_opportunity); | 228 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(initial_opportunity); |
235 | 229 |
236 for (const auto exclusion : exclusions) { | 230 for (const auto& exclusion : exclusions) { |
237 InsertExclusion(MutableOpportunityTreeRoot(), exclusion, opportunities_); | 231 InsertExclusion(MutableOpportunityTreeRoot(), exclusion.get(), |
| 232 opportunities_); |
238 } | 233 } |
239 CollectAllOpportunities(OpportunityTreeRoot(), opportunities_); | 234 CollectAllOpportunities(OpportunityTreeRoot(), opportunities_); |
240 std::sort(opportunities_.begin(), opportunities_.end(), | 235 std::sort(opportunities_.begin(), opportunities_.end(), |
241 &CompareNGLayoutOpportunitesByStartPoint); | 236 &CompareNGLayoutOpportunitesByStartPoint); |
242 | 237 |
243 opportunity_iter_ = opportunities_.begin(); | 238 opportunity_iter_ = opportunities_.begin(); |
244 } | 239 } |
245 | 240 |
246 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { | 241 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { |
247 if (opportunity_iter_ == opportunities_.end()) | 242 if (opportunity_iter_ == opportunities_.end()) |
248 return NGLayoutOpportunity(); | 243 return NGLayoutOpportunity(); |
249 auto* opportunity = opportunity_iter_; | 244 auto* opportunity = opportunity_iter_; |
250 opportunity_iter_++; | 245 opportunity_iter_++; |
251 return NGLayoutOpportunity(*opportunity); | 246 return NGLayoutOpportunity(*opportunity); |
252 } | 247 } |
253 | 248 |
254 } // namespace blink | 249 } // namespace blink |
OLD | NEW |