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