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