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: exclusion is not in the node's constraint space. | 145 // Base case: exclusion is not in the node's constraint space. |
152 if (!IsExclusionWithinSpace(*node->space, *exclusion)) | 146 if (!IsExclusionWithinSpace(node->opportunity, *exclusion)) |
153 return; | 147 return; |
154 | 148 |
155 if (node->exclusion) { | 149 if (node->exclusion) { |
156 InsertExclusion(node->left, exclusion, opportunities); | 150 InsertExclusion(node->left, exclusion, opportunities); |
157 InsertExclusion(node->bottom, exclusion, opportunities); | 151 InsertExclusion(node->bottom, exclusion, opportunities); |
158 InsertExclusion(node->right, exclusion, opportunities); | 152 InsertExclusion(node->right, exclusion, opportunities); |
159 return; | 153 return; |
160 } | 154 } |
161 | 155 |
162 // Split the current node. | 156 // Split the current node. |
163 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, *exclusion); | 157 node->left = CreateLeftNGLayoutOpportunityTreeNode(node, *exclusion); |
164 node->right = CreateRightNGLayoutOpportunityTreeNode(node, *exclusion); | 158 node->right = CreateRightNGLayoutOpportunityTreeNode(node, *exclusion); |
165 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, *exclusion); | 159 node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, *exclusion); |
166 | 160 |
167 if (auto* topSpace = GetTopSpace(*node->space, *exclusion)) | 161 NGLogicalRect top_layout_opp = GetTopSpace(node->opportunity, *exclusion); |
168 opportunities.append(topSpace); | 162 if (!top_layout_opp.IsEmpty()) |
| 163 opportunities.append(top_layout_opp); |
| 164 |
169 node->exclusion = exclusion; | 165 node->exclusion = exclusion; |
170 } | 166 } |
171 | 167 |
172 // Compares exclusions by their top position. | 168 // Compares exclusions by their top position. |
173 bool CompareNGExclusionsByTopAsc(const Member<const NGExclusion>& lhs, | 169 bool CompareNGExclusionsByTopAsc(const Member<const NGExclusion>& lhs, |
174 const Member<const NGExclusion>& rhs) { | 170 const Member<const NGExclusion>& rhs) { |
175 return rhs->Top() > lhs->Top(); | 171 return rhs->Top() > lhs->Top(); |
176 } | 172 } |
177 | 173 |
178 // Compares Layout Opportunities by Start Point. | 174 // Compares Layout Opportunities by Start Point. |
179 // Start point is a TopLeft position from where inline content can potentially | 175 // Start point is a TopLeft position from where inline content can potentially |
180 // start positioning itself. | 176 // start positioning itself. |
181 bool CompareNGLayoutOpportunitesByStartPoint( | 177 bool CompareNGLayoutOpportunitesByStartPoint(const NGLogicalRect& lhs, |
182 const Member<const NGLayoutOpportunity>& lhs, | 178 const NGLogicalRect& rhs) { |
183 const Member<const NGLayoutOpportunity>& rhs) { | |
184 // sort by TOP. | 179 // sort by TOP. |
185 if (rhs->Offset().block_offset > lhs->Offset().block_offset) { | 180 if (rhs.offset.block_offset > lhs.offset.block_offset) { |
186 return true; | 181 return true; |
187 } | 182 } |
188 if (rhs->Offset().block_offset < lhs->Offset().block_offset) { | 183 if (rhs.offset.block_offset < lhs.offset.block_offset) { |
189 return false; | 184 return false; |
190 } | 185 } |
191 | 186 |
192 // TOP is the same -> Sort by LEFT | 187 // TOP is the same -> Sort by LEFT |
193 if (rhs->Offset().inline_offset > lhs->Offset().inline_offset) { | 188 if (rhs.offset.inline_offset > lhs.offset.inline_offset) { |
194 return true; | 189 return true; |
195 } | 190 } |
196 if (rhs->Offset().inline_offset < lhs->Offset().inline_offset) { | 191 if (rhs.offset.inline_offset < lhs.offset.inline_offset) { |
197 return false; | 192 return false; |
198 } | 193 } |
199 | 194 |
200 // TOP and LEFT are the same -> Sort by width | 195 // TOP and LEFT are the same -> Sort by width |
201 return rhs->Size().inline_size < lhs->Size().inline_size; | 196 return rhs.size.inline_size < lhs.size.inline_size; |
202 } | 197 } |
203 | 198 |
204 } // namespace | 199 } // namespace |
205 | 200 |
206 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( | 201 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( |
207 NGConstraintSpace* space, | 202 NGConstraintSpace* space, |
208 unsigned clear, | 203 unsigned clear, |
209 bool for_inline_or_bfc) | 204 bool for_inline_or_bfc) |
210 : constraint_space_(space) { | 205 : constraint_space_(space) { |
211 // TODO(chrome-layout-team): Combine exclusions that shadow each other. | 206 // TODO(chrome-layout-team): Combine exclusions that shadow each other. |
212 auto exclusions = constraint_space_->PhysicalSpace()->Exclusions(); | 207 auto exclusions = constraint_space_->PhysicalSpace()->Exclusions(); |
213 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), | 208 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), |
214 &CompareNGExclusionsByTopAsc)) | 209 &CompareNGExclusionsByTopAsc)) |
215 << "Exclusions are expected to be sorted by TOP"; | 210 << "Exclusions are expected to be sorted by TOP"; |
216 | 211 |
217 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(space); | 212 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode( |
| 213 NGLogicalRect(space->Offset().inline_offset, space->Offset().block_offset, |
| 214 space->Size().inline_size, space->Size().block_size)); |
| 215 |
218 for (const auto exclusion : exclusions) { | 216 for (const auto exclusion : exclusions) { |
219 InsertExclusion(opportunity_tree_root_, exclusion, opportunities_); | 217 InsertExclusion(opportunity_tree_root_, exclusion, opportunities_); |
220 } | 218 } |
221 CollectAllOpportunities(opportunity_tree_root_, opportunities_); | 219 CollectAllOpportunities(opportunity_tree_root_, opportunities_); |
222 std::sort(opportunities_.begin(), opportunities_.end(), | 220 std::sort(opportunities_.begin(), opportunities_.end(), |
223 &CompareNGLayoutOpportunitesByStartPoint); | 221 &CompareNGLayoutOpportunitesByStartPoint); |
224 opportunity_iter_ = opportunities_.begin(); | 222 opportunity_iter_ = opportunities_.begin(); |
225 } | 223 } |
226 | 224 |
227 const NGConstraintSpace* NGLayoutOpportunityIterator::Next() { | 225 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { |
228 if (opportunity_iter_ == opportunities_.end()) | 226 if (opportunity_iter_ == opportunities_.end()) |
229 return nullptr; | 227 return NGLayoutOpportunity(); |
230 auto* opportunity = opportunity_iter_->get(); | 228 auto* opportunity = opportunity_iter_; |
231 opportunity_iter_++; | 229 opportunity_iter_++; |
232 return opportunity; | 230 return NGLayoutOpportunity(*opportunity); |
233 } | 231 } |
234 | 232 |
235 } // namespace blink | 233 } // namespace blink |
OLD | NEW |