1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "third_party/blink/renderer/core/layout/grid_track_sizing_algorithm.h"
6
7 #include "third_party/blink/renderer/core/frame/deprecation.h"
8 #include "third_party/blink/renderer/core/layout/grid.h"
9 #include "third_party/blink/renderer/core/layout/grid_layout_utils.h"
10 #include "third_party/blink/renderer/core/layout/layout_grid.h"
11 #include "third_party/blink/renderer/platform/geometry/length_functions.h"
12
13 namespace blink {
14
15 class GridSizingData;
16
BaseSize() const17 LayoutUnit GridTrack::BaseSize() const {
18 DCHECK(IsGrowthLimitBiggerThanBaseSize());
19 return base_size_;
20 }
21
GrowthLimit() const22 LayoutUnit GridTrack::GrowthLimit() const {
23 DCHECK(IsGrowthLimitBiggerThanBaseSize());
24 DCHECK(!growth_limit_cap_ || growth_limit_cap_.value() >= growth_limit_ ||
25 base_size_ >= growth_limit_cap_.value());
26 return growth_limit_;
27 }
28
SetBaseSize(LayoutUnit base_size)29 void GridTrack::SetBaseSize(LayoutUnit base_size) {
30 base_size_ = base_size;
31 EnsureGrowthLimitIsBiggerThanBaseSize();
32 }
33
SetGrowthLimit(LayoutUnit growth_limit)34 void GridTrack::SetGrowthLimit(LayoutUnit growth_limit) {
35 growth_limit_ =
36 growth_limit == kInfinity
37 ? growth_limit
38 : std::min(growth_limit, growth_limit_cap_.value_or(growth_limit));
39 EnsureGrowthLimitIsBiggerThanBaseSize();
40 }
41
InfiniteGrowthPotential() const42 bool GridTrack::InfiniteGrowthPotential() const {
43 return GrowthLimitIsInfinite() || infinitely_growable_;
44 }
45
SetPlannedSize(LayoutUnit planned_size)46 void GridTrack::SetPlannedSize(LayoutUnit planned_size) {
47 DCHECK(planned_size >= 0 || planned_size == kInfinity);
48 planned_size_ = planned_size;
49 }
50
SetSizeDuringDistribution(LayoutUnit size_during_distribution)51 void GridTrack::SetSizeDuringDistribution(LayoutUnit size_during_distribution) {
52 DCHECK_GE(size_during_distribution, 0);
53 DCHECK(GrowthLimitIsInfinite() || GrowthLimit() >= size_during_distribution);
54 size_during_distribution_ = size_during_distribution;
55 }
56
GrowSizeDuringDistribution(LayoutUnit size_during_distribution)57 void GridTrack::GrowSizeDuringDistribution(
58 LayoutUnit size_during_distribution) {
59 DCHECK_GE(size_during_distribution, 0);
60 size_during_distribution_ += size_during_distribution;
61 }
62
SetInfinitelyGrowable(bool infinitely_growable)63 void GridTrack::SetInfinitelyGrowable(bool infinitely_growable) {
64 infinitely_growable_ = infinitely_growable;
65 }
66
SetGrowthLimitCap(base::Optional<LayoutUnit> growth_limit_cap)67 void GridTrack::SetGrowthLimitCap(base::Optional<LayoutUnit> growth_limit_cap) {
68 DCHECK(!growth_limit_cap || *growth_limit_cap >= 0);
69 growth_limit_cap_ = growth_limit_cap;
70 }
71
SetCachedTrackSize(const GridTrackSize & cached_track_size)72 void GridTrack::SetCachedTrackSize(const GridTrackSize& cached_track_size) {
73 cached_track_size_ = cached_track_size;
74 }
75
IsGrowthLimitBiggerThanBaseSize() const76 bool GridTrack::IsGrowthLimitBiggerThanBaseSize() const {
77 return GrowthLimitIsInfinite() || growth_limit_ >= base_size_;
78 }
79
EnsureGrowthLimitIsBiggerThanBaseSize()80 void GridTrack::EnsureGrowthLimitIsBiggerThanBaseSize() {
81 if (growth_limit_ != kInfinity && growth_limit_ < base_size_)
82 growth_limit_ = base_size_;
83 }
84
GridAxisForDirection(GridTrackSizingDirection direction)85 static GridAxis GridAxisForDirection(GridTrackSizingDirection direction) {
86 return direction == kForColumns ? kGridRowAxis : kGridColumnAxis;
87 }
88
GridDirectionForAxis(GridAxis axis)89 static GridTrackSizingDirection GridDirectionForAxis(GridAxis axis) {
90 return axis == kGridRowAxis ? kForColumns : kForRows;
91 }
92
93 class IndefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
94 public:
IndefiniteSizeStrategy(GridTrackSizingAlgorithm & algorithm)95 IndefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
96 : GridTrackSizingAlgorithmStrategy(algorithm) {}
97
98 private:
99 void LayoutGridItemForMinSizeComputation(
100 LayoutBox&,
101 bool override_size_has_changed) const override;
102 void MaximizeTracks(Vector<GridTrack>&,
103 base::Optional<LayoutUnit>& free_space) override;
104 double FindUsedFlexFraction(
105 Vector<size_t>& flexible_sized_tracks_index,
106 GridTrackSizingDirection,
107 base::Optional<LayoutUnit> free_space) const override;
108 bool RecomputeUsedFlexFractionIfNeeded(
109 Vector<size_t>& flexible_sized_tracks_index,
110 double& flex_fraction,
111 Vector<LayoutUnit>& increments,
112 LayoutUnit& total_growth) const override;
113 LayoutUnit FreeSpaceForStretchAutoTracksStep() const override;
114 LayoutUnit MinContentForChild(LayoutBox&) const override;
115 LayoutUnit MaxContentForChild(LayoutBox&) const override;
116 bool IsComputingSizeContainment() const override;
117 };
118
119 class DefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
120 public:
DefiniteSizeStrategy(GridTrackSizingAlgorithm & algorithm)121 DefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
122 : GridTrackSizingAlgorithmStrategy(algorithm) {}
123
124 private:
125 void LayoutGridItemForMinSizeComputation(
126 LayoutBox&,
127 bool override_size_has_changed) const override;
128 void MaximizeTracks(Vector<GridTrack>&,
129 base::Optional<LayoutUnit>& free_space) override;
130 double FindUsedFlexFraction(
131 Vector<size_t>& flexible_sized_tracks_index,
132 GridTrackSizingDirection,
133 base::Optional<LayoutUnit> free_space) const override;
RecomputeUsedFlexFractionIfNeeded(Vector<size_t> & flexible_sized_tracks_index,double & flex_fraction,Vector<LayoutUnit> & increments,LayoutUnit & total_growth) const134 bool RecomputeUsedFlexFractionIfNeeded(
135 Vector<size_t>& flexible_sized_tracks_index,
136 double& flex_fraction,
137 Vector<LayoutUnit>& increments,
138 LayoutUnit& total_growth) const override {
139 return false;
140 }
141 LayoutUnit FreeSpaceForStretchAutoTracksStep() const override;
142 LayoutUnit MinContentForChild(LayoutBox&) const override;
143 LayoutUnit MinLogicalSizeForChild(LayoutBox&,
144 const Length& child_min_size,
145 LayoutUnit available_size) const override;
IsComputingSizeContainment() const146 bool IsComputingSizeContainment() const override { return false; }
147 };
148
149 GridTrackSizingAlgorithmStrategy::~GridTrackSizingAlgorithmStrategy() = default;
150
HasRelativeMarginOrPaddingForChild(const LayoutGrid & grid,const LayoutBox & child,GridTrackSizingDirection direction)151 bool GridTrackSizingAlgorithmStrategy::HasRelativeMarginOrPaddingForChild(
152 const LayoutGrid& grid,
153 const LayoutBox& child,
154 GridTrackSizingDirection direction) {
155 GridTrackSizingDirection child_inline_direction =
156 GridLayoutUtils::FlowAwareDirectionForChild(grid, child, kForColumns);
157 if (direction == child_inline_direction) {
158 return child.StyleRef().MarginStart().IsPercentOrCalc() ||
159 child.StyleRef().MarginEnd().IsPercentOrCalc() ||
160 child.StyleRef().PaddingStart().IsPercentOrCalc() ||
161 child.StyleRef().PaddingEnd().IsPercentOrCalc();
162 }
163 return child.StyleRef().MarginBefore().IsPercentOrCalc() ||
164 child.StyleRef().MarginAfter().IsPercentOrCalc() ||
165 child.StyleRef().PaddingBefore().IsPercentOrCalc() ||
166 child.StyleRef().PaddingAfter().IsPercentOrCalc();
167 }
168
HasRelativeOrIntrinsicSizeForChild(const LayoutGrid & grid,const LayoutBox & child,GridTrackSizingDirection direction)169 bool GridTrackSizingAlgorithmStrategy::HasRelativeOrIntrinsicSizeForChild(
170 const LayoutGrid& grid,
171 const LayoutBox& child,
172 GridTrackSizingDirection direction) {
173 GridTrackSizingDirection child_inline_direction =
174 GridLayoutUtils::FlowAwareDirectionForChild(grid, child, kForColumns);
175 if (direction == child_inline_direction) {
176 return child.HasRelativeLogicalWidth() ||
177 child.StyleRef().LogicalWidth().IsIntrinsicOrAuto();
178 }
179 return child.HasRelativeLogicalHeight() ||
180 child.StyleRef().LogicalHeight().IsIntrinsicOrAuto();
181 }
182
183 bool GridTrackSizingAlgorithmStrategy::
ShouldClearOverrideContainingBlockContentSizeForChild(const LayoutGrid & grid,const LayoutBox & child,GridTrackSizingDirection direction)184 ShouldClearOverrideContainingBlockContentSizeForChild(
185 const LayoutGrid& grid,
186 const LayoutBox& child,
187 GridTrackSizingDirection direction) {
188 return HasRelativeOrIntrinsicSizeForChild(grid, child, direction) ||
189 HasRelativeMarginOrPaddingForChild(grid, child, direction);
190 }
191
192 void GridTrackSizingAlgorithmStrategy::
SetOverrideContainingBlockContentSizeForChild(LayoutBox & child,GridTrackSizingDirection direction,LayoutUnit size)193 SetOverrideContainingBlockContentSizeForChild(
194 LayoutBox& child,
195 GridTrackSizingDirection direction,
196 LayoutUnit size) {
197 if (direction == kForColumns)
198 child.SetOverrideContainingBlockContentLogicalWidth(size);
199 else
200 child.SetOverrideContainingBlockContentLogicalHeight(size);
201 }
202
EstimatedGridAreaBreadthForChild(const LayoutBox & child) const203 LayoutSize GridTrackSizingAlgorithm::EstimatedGridAreaBreadthForChild(
204 const LayoutBox& child) const {
205 return {EstimatedGridAreaBreadthForChild(child, kForColumns),
206 EstimatedGridAreaBreadthForChild(child, kForRows)};
207 }
208
EstimatedGridAreaBreadthForChild(const LayoutBox & child,GridTrackSizingDirection direction) const209 LayoutUnit GridTrackSizingAlgorithm::EstimatedGridAreaBreadthForChild(
210 const LayoutBox& child,
211 GridTrackSizingDirection direction) const {
212 const GridSpan& span = grid_.GridItemSpan(child, direction);
213 LayoutUnit grid_area_size;
214 bool grid_area_is_indefinite = false;
215 base::Optional<LayoutUnit> available_size = AvailableSpace(direction);
216 for (auto track_position : span) {
217 // We may need to estimate the grid area size before running the track
218 // sizing algorithm in order to perform the pre-layout of orthogonal
219 // items.
220 // We cannot use Tracks(direction)[track_position].CachedTrackSize()
221 // because Tracks(direction) is empty, since we are either performing
222 // pre-layout or are running the track sizing algorithm in the opposite
223 // direction and haven't run it in the desired direction yet.
224 const GridTrackSize& track_size =
225 WasSetup() ? CalculateGridTrackSize(direction, track_position)
226 : RawGridTrackSize(direction, track_position);
227 GridLength max_track_size = track_size.MaxTrackBreadth();
228 if (max_track_size.IsContentSized() || max_track_size.IsFlex() ||
229 IsRelativeGridLengthAsAuto(max_track_size, direction)) {
230 grid_area_is_indefinite = true;
231 } else {
232 grid_area_size += ValueForLength(max_track_size.length(),
233 available_size.value_or(LayoutUnit()));
234 }
235 }
236
237 grid_area_size += layout_grid_->GuttersSize(
238 grid_, direction, span.StartLine(), span.IntegerSpan(), available_size);
239
240 GridTrackSizingDirection child_inline_direction =
241 GridLayoutUtils::FlowAwareDirectionForChild(*layout_grid_, child,
242 kForColumns);
243 if (grid_area_is_indefinite) {
244 return direction == child_inline_direction
245 ? std::max(child.PreferredLogicalWidths().max_size,
246 grid_area_size)
247 : LayoutUnit(-1);
248 }
249 return grid_area_size;
250 }
251
GridAreaBreadthForChild(const LayoutBox & child,GridTrackSizingDirection direction) const252 LayoutUnit GridTrackSizingAlgorithm::GridAreaBreadthForChild(
253 const LayoutBox& child,
254 GridTrackSizingDirection direction) const {
255 bool add_content_alignment_offset =
256 direction == kForColumns && sizing_state_ == kRowSizingFirstIteration;
257 if (direction == kForRows &&
258 (sizing_state_ == kColumnSizingFirstIteration ||
259 sizing_state_ == kColumnSizingSecondIteration)) {
260 DCHECK(GridLayoutUtils::IsOrthogonalChild(*layout_grid_, child));
261 // TODO (jfernandez) Content Alignment should account for this heuristic
262 // https://github.com/w3c/csswg-drafts/issues/2697
263 if (sizing_state_ == kColumnSizingFirstIteration)
264 return EstimatedGridAreaBreadthForChild(child, kForRows);
265 add_content_alignment_offset = true;
266 }
267
268 const Vector<GridTrack>& all_tracks = Tracks(direction);
269 const GridSpan& span = grid_.GridItemSpan(child, direction);
270 LayoutUnit grid_area_breadth;
271 for (const auto& track_position : span)
272 grid_area_breadth += all_tracks[track_position].BaseSize();
273
274 if (add_content_alignment_offset) {
275 grid_area_breadth +=
276 (span.IntegerSpan() - 1) * layout_grid_->GridItemOffset(direction);
277 }
278
279 grid_area_breadth +=
280 layout_grid_->GuttersSize(grid_, direction, span.StartLine(),
281 span.IntegerSpan(), AvailableSpace(direction));
282
283 return grid_area_breadth;
284 }
285
IsIntrinsicSizedGridArea(const LayoutBox & child,GridAxis axis) const286 bool GridTrackSizingAlgorithm::IsIntrinsicSizedGridArea(const LayoutBox& child,
287 GridAxis axis) const {
288 DCHECK(WasSetup());
289 GridTrackSizingDirection direction = GridDirectionForAxis(axis);
290 const GridSpan& span = grid_.GridItemSpan(child, direction);
291 for (const auto& track_position : span) {
292 const GridTrackSize& track_size =
293 RawGridTrackSize(direction, track_position);
294 // We consider fr units as 'auto' for the min sizing function.
295 // TODO(jfernandez): https://github.com/w3c/csswg-drafts/issues/2611
296 //
297 // The use of AvailableSize function may imply different results
298 // for the same item when assuming indefinite or definite size
299 // constraints depending on the phase we evaluate the item's
300 // baseline participation.
301 // TODO(jfernandez): https://github.com/w3c/csswg-drafts/issues/3046
302 if (track_size.IsContentSized() || track_size.IsFitContent() ||
303 track_size.MinTrackBreadth().IsFlex() ||
304 (track_size.MaxTrackBreadth().IsFlex() && !AvailableSpace(direction)))
305 return true;
306 }
307 return false;
308 }
309
310 bool GridTrackSizingAlgorithmStrategy::
UpdateOverrideContainingBlockContentSizeForChild(LayoutBox & child,GridTrackSizingDirection direction,base::Optional<LayoutUnit> override_size) const311 UpdateOverrideContainingBlockContentSizeForChild(
312 LayoutBox& child,
313 GridTrackSizingDirection direction,
314 base::Optional<LayoutUnit> override_size) const {
315 if (!override_size)
316 override_size = algorithm_.GridAreaBreadthForChild(child, direction);
317 if (GridLayoutUtils::OverrideContainingBlockContentSizeForChild(
318 child, direction) == override_size.value())
319 return false;
320
321 SetOverrideContainingBlockContentSizeForChild(child, direction,
322 override_size.value());
323 return true;
324 }
325
LogicalHeightForChild(LayoutBox & child) const326 LayoutUnit GridTrackSizingAlgorithmStrategy::LogicalHeightForChild(
327 LayoutBox& child) const {
328 GridTrackSizingDirection child_block_direction =
329 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
330 kForRows);
331 // If |child| has a relative block-axis size, we shouldn't let it override its
332 // intrinsic size, which is what we are interested in here. Thus we
333 // need to set the block-axis OverrideContainingBlock size to -1 (no possible
334 // resolution).
335 if (ShouldClearOverrideContainingBlockContentSizeForChild(
336 *GetLayoutGrid(), child, child_block_direction)) {
337 SetOverrideContainingBlockContentSizeForChild(child, child_block_direction,
338 LayoutUnit(-1));
339 child.SetSelfNeedsLayoutForAvailableSpace(true);
340 }
341
342 child.LayoutIfNeeded();
343
344 return child.LogicalHeight() +
345 GridLayoutUtils::MarginLogicalHeightForChild(*GetLayoutGrid(), child) +
346 algorithm_.BaselineOffsetForChild(child,
347 GridAxisForDirection(Direction()));
348 }
349
350 DISABLE_CFI_PERF
MinContentForChild(LayoutBox & child) const351 LayoutUnit GridTrackSizingAlgorithmStrategy::MinContentForChild(
352 LayoutBox& child) const {
353 GridTrackSizingDirection child_inline_direction =
354 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
355 kForColumns);
356 if (Direction() == child_inline_direction) {
357 // FIXME: It's unclear if we should return the intrinsic width or the
358 // preferred width.
359 // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
360 return child.PreferredLogicalWidths().min_size +
361 GridLayoutUtils::MarginLogicalWidthForChild(*GetLayoutGrid(),
362 child) +
363 algorithm_.BaselineOffsetForChild(child,
364 GridAxisForDirection(Direction()));
365 }
366
367 if (UpdateOverrideContainingBlockContentSizeForChild(
368 child, child_inline_direction)) {
369 child.SetSelfNeedsLayoutForAvailableSpace(true);
370 }
371 return LogicalHeightForChild(child);
372 }
373
374 DISABLE_CFI_PERF
MaxContentForChild(LayoutBox & child) const375 LayoutUnit GridTrackSizingAlgorithmStrategy::MaxContentForChild(
376 LayoutBox& child) const {
377 GridTrackSizingDirection child_inline_direction =
378 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
379 kForColumns);
380 if (Direction() == child_inline_direction) {
381 // FIXME: It's unclear if we should return the intrinsic width or the
382 // preferred width.
383 // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
384 return child.PreferredLogicalWidths().max_size +
385 GridLayoutUtils::MarginLogicalWidthForChild(*GetLayoutGrid(),
386 child) +
387 algorithm_.BaselineOffsetForChild(child,
388 GridAxisForDirection(Direction()));
389 }
390
391 if (UpdateOverrideContainingBlockContentSizeForChild(
392 child, child_inline_direction)) {
393 child.SetSelfNeedsLayoutForAvailableSpace(true);
394 }
395 return LogicalHeightForChild(child);
396 }
397
MinSizeForChild(LayoutBox & child) const398 LayoutUnit GridTrackSizingAlgorithmStrategy::MinSizeForChild(
399 LayoutBox& child) const {
400 GridTrackSizingDirection child_inline_direction =
401 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
402 kForColumns);
403 bool is_row_axis = Direction() == child_inline_direction;
404 const Length& child_size = is_row_axis ? child.StyleRef().LogicalWidth()
405 : child.StyleRef().LogicalHeight();
406 if (!child_size.IsAuto() && !child_size.IsPercentOrCalc())
407 return MinContentForChild(child);
408
409 const Length& child_min_size = is_row_axis
410 ? child.StyleRef().LogicalMinWidth()
411 : child.StyleRef().LogicalMinHeight();
412 bool overflow_is_visible =
413 is_row_axis
414 ? child.StyleRef().OverflowInlineDirection() == EOverflow::kVisible
415 : child.StyleRef().OverflowBlockDirection() == EOverflow::kVisible;
416 LayoutUnit baseline_shim = algorithm_.BaselineOffsetForChild(
417 child, GridAxisForDirection(Direction()));
418
419 if (child_min_size.IsAuto() && overflow_is_visible) {
420 LayoutUnit min_size = MinContentForChild(child);
421 const GridSpan& span =
422 algorithm_.GetGrid().GridItemSpan(child, Direction());
423 LayoutUnit max_breadth;
424 const Vector<GridTrack>& all_tracks = algorithm_.Tracks(Direction());
425 for (const auto& track_position : span) {
426 const GridTrackSize& track_size =
427 all_tracks[track_position].CachedTrackSize();
428 if (!track_size.HasFixedMaxTrackBreadth())
429 return min_size;
430 max_breadth += ValueForLength(track_size.MaxTrackBreadth().length(),
431 AvailableSpace().value_or(LayoutUnit()));
432 }
433 if (min_size > max_breadth) {
434 LayoutUnit margin_and_border_and_padding =
435 is_row_axis ? GridLayoutUtils::MarginLogicalWidthForChild(
436 *GetLayoutGrid(), child) +
437 child.BorderAndPaddingLogicalWidth()
438 : GridLayoutUtils::MarginLogicalHeightForChild(
439 *GetLayoutGrid(), child) +
440 child.BorderAndPaddingLogicalHeight();
441 min_size =
442 std::max(max_breadth, margin_and_border_and_padding + baseline_shim);
443 }
444 return min_size;
445 }
446
447 LayoutUnit grid_area_size =
448 algorithm_.GridAreaBreadthForChild(child, child_inline_direction);
449 return MinLogicalSizeForChild(child, child_min_size, grid_area_size) +
450 baseline_shim;
451 }
452
CanParticipateInBaselineAlignment(const LayoutBox & child,GridAxis baseline_axis) const453 bool GridTrackSizingAlgorithm::CanParticipateInBaselineAlignment(
454 const LayoutBox& child,
455 GridAxis baseline_axis) const {
456 DCHECK(baseline_axis == kGridColumnAxis
457 ? column_baseline_items_map_.Contains(&child)
458 : row_baseline_items_map_.Contains(&child));
459
460 // Baseline cyclic dependencies only happen with synthesized
461 // baselines. These cases include orthogonal or empty grid items
462 // and replaced elements.
463 bool is_parallel_to_baseline_axis =
464 baseline_axis == kGridColumnAxis
465 ? !GridLayoutUtils::IsOrthogonalChild(*layout_grid_, child)
466 : GridLayoutUtils::IsOrthogonalChild(*layout_grid_, child);
467 if (is_parallel_to_baseline_axis && child.FirstLineBoxBaseline() != -1)
468 return true;
469
470 // Baseline cyclic dependencies only happen in grid areas with
471 // intrinsically-sized tracks.
472 if (!IsIntrinsicSizedGridArea(child, baseline_axis))
473 return true;
474
475 return is_parallel_to_baseline_axis
476 ? !child.HasRelativeLogicalHeight()
477 : !child.HasRelativeLogicalWidth() &&
478 !child.StyleRef().LogicalWidth().IsAuto();
479 }
480
ParticipateInBaselineAlignment(const LayoutBox & child,GridAxis baseline_axis) const481 bool GridTrackSizingAlgorithm::ParticipateInBaselineAlignment(
482 const LayoutBox& child,
483 GridAxis baseline_axis) const {
484 return baseline_axis == kGridColumnAxis
485 ? column_baseline_items_map_.at(&child)
486 : row_baseline_items_map_.at(&child);
487 }
488
UpdateBaselineAlignmentContext(const LayoutBox & child,GridAxis baseline_axis)489 void GridTrackSizingAlgorithm::UpdateBaselineAlignmentContext(
490 const LayoutBox& child,
491 GridAxis baseline_axis) {
492 DCHECK(WasSetup());
493 DCHECK(CanParticipateInBaselineAlignment(child, baseline_axis));
494 DCHECK(!child.NeedsLayout());
495
496 ItemPosition align =
497 layout_grid_->SelfAlignmentForChild(baseline_axis, child).GetPosition();
498 const auto& span =
499 grid_.GridItemSpan(child, GridDirectionForAxis(baseline_axis));
500 baseline_alignment_.UpdateBaselineAlignmentContext(align, span.StartLine(),
501 child, baseline_axis);
502 }
503
BaselineOffsetForChild(const LayoutBox & child,GridAxis baseline_axis) const504 LayoutUnit GridTrackSizingAlgorithm::BaselineOffsetForChild(
505 const LayoutBox& child,
506 GridAxis baseline_axis) const {
507 if (!ParticipateInBaselineAlignment(child, baseline_axis))
508 return LayoutUnit();
509
510 ItemPosition align =
511 layout_grid_->SelfAlignmentForChild(baseline_axis, child).GetPosition();
512 const auto& span =
513 grid_.GridItemSpan(child, GridDirectionForAxis(baseline_axis));
514 return baseline_alignment_.BaselineOffsetForChild(align, span.StartLine(),
515 child, baseline_axis);
516 }
517
ClearBaselineItemsCache()518 void GridTrackSizingAlgorithm::ClearBaselineItemsCache() {
519 column_baseline_items_map_.clear();
520 row_baseline_items_map_.clear();
521 }
522
CacheBaselineAlignedItem(const LayoutBox & item,GridAxis axis)523 void GridTrackSizingAlgorithm::CacheBaselineAlignedItem(const LayoutBox& item,
524 GridAxis axis) {
525 DCHECK(layout_grid_->IsBaselineAlignmentForChild(item, axis));
526 if (axis == kGridColumnAxis)
527 column_baseline_items_map_.insert(&item, true);
528 else
529 row_baseline_items_map_.insert(&item, true);
530 }
531
CopyBaselineItemsCache(const GridTrackSizingAlgorithm & source,GridAxis axis)532 void GridTrackSizingAlgorithm::CopyBaselineItemsCache(
533 const GridTrackSizingAlgorithm& source,
534 GridAxis axis) {
535 if (axis == kGridColumnAxis)
536 column_baseline_items_map_ = source.column_baseline_items_map_;
537 else
538 row_baseline_items_map_ = source.row_baseline_items_map_;
539 }
540
ComputeTrackBasedSize() const541 LayoutUnit GridTrackSizingAlgorithmStrategy::ComputeTrackBasedSize() const {
542 return algorithm_.ComputeTrackBasedSize();
543 }
544
FindFrUnitSize(const GridSpan & tracks_span,LayoutUnit left_over_space) const545 double GridTrackSizingAlgorithmStrategy::FindFrUnitSize(
546 const GridSpan& tracks_span,
547 LayoutUnit left_over_space) const {
548 return algorithm_.FindFrUnitSize(tracks_span, left_over_space);
549 }
550
DistributeSpaceToTracks(Vector<GridTrack * > & tracks,LayoutUnit & available_logical_space) const551 void GridTrackSizingAlgorithmStrategy::DistributeSpaceToTracks(
552 Vector<GridTrack*>& tracks,
553 LayoutUnit& available_logical_space) const {
554 algorithm_.DistributeSpaceToTracks<kMaximizeTracks>(tracks, nullptr,
555 available_logical_space);
556 }
557
MinLogicalSizeForChild(LayoutBox & child,const Length & child_min_size,LayoutUnit available_size) const558 LayoutUnit GridTrackSizingAlgorithmStrategy::MinLogicalSizeForChild(
559 LayoutBox& child,
560 const Length& child_min_size,
561 LayoutUnit available_size) const {
562 GridTrackSizingDirection child_inline_direction =
563 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
564 kForColumns);
565 bool is_row_axis = Direction() == child_inline_direction;
566
567 if (is_row_axis) {
568 return child.ComputeLogicalWidthUsing(kMinSize, child_min_size,
569 available_size, GetLayoutGrid()) +
570 GridLayoutUtils::MarginLogicalWidthForChild(*GetLayoutGrid(), child);
571 }
572
573 bool override_size_has_changed =
574 UpdateOverrideContainingBlockContentSizeForChild(
575 child, child_inline_direction, available_size);
576 LayoutGridItemForMinSizeComputation(child, override_size_has_changed);
577
578 return child.ComputeLogicalHeightUsing(kMinSize, child_min_size,
579 child.IntrinsicLogicalHeight()) +
580 GridLayoutUtils::MarginLogicalHeightForChild(*GetLayoutGrid(), child);
581 }
582
MinLogicalSizeForChild(LayoutBox & child,const Length & child_min_size,LayoutUnit available_size) const583 LayoutUnit DefiniteSizeStrategy::MinLogicalSizeForChild(
584 LayoutBox& child,
585 const Length& child_min_size,
586 LayoutUnit available_size) const {
587 GridTrackSizingDirection child_inline_direction =
588 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
589 kForColumns);
590 LayoutUnit indefinite_size =
591 Direction() == child_inline_direction ? LayoutUnit() : LayoutUnit(-1);
592 if (HasRelativeMarginOrPaddingForChild(*GetLayoutGrid(), child,
593 Direction()) ||
594 (Direction() != child_inline_direction &&
595 HasRelativeOrIntrinsicSizeForChild(*GetLayoutGrid(), child,
596 Direction()))) {
597 SetOverrideContainingBlockContentSizeForChild(child, Direction(),
598 indefinite_size);
599 }
600 return GridTrackSizingAlgorithmStrategy::MinLogicalSizeForChild(
601 child, child_min_size, available_size);
602 }
603
LayoutGridItemForMinSizeComputation(LayoutBox & child,bool override_size_has_changed) const604 void DefiniteSizeStrategy::LayoutGridItemForMinSizeComputation(
605 LayoutBox& child,
606 bool override_size_has_changed) const {
607 if (override_size_has_changed) {
608 child.SetSelfNeedsLayoutForAvailableSpace(true);
609 child.LayoutIfNeeded();
610 }
611 }
612
MaximizeTracks(Vector<GridTrack> & tracks,base::Optional<LayoutUnit> & free_space)613 void DefiniteSizeStrategy::MaximizeTracks(
614 Vector<GridTrack>& tracks,
615 base::Optional<LayoutUnit>& free_space) {
616 size_t tracks_size = tracks.size();
617 Vector<GridTrack*> tracks_for_distribution(tracks_size);
618 for (size_t i = 0; i < tracks_size; ++i) {
619 tracks_for_distribution[i] = tracks.data() + i;
620 tracks_for_distribution[i]->SetPlannedSize(
621 tracks_for_distribution[i]->BaseSize());
622 }
623
624 DCHECK(free_space);
625 DistributeSpaceToTracks(tracks_for_distribution, free_space.value());
626
627 for (auto* track : tracks_for_distribution)
628 track->SetBaseSize(track->PlannedSize());
629 }
630
FindUsedFlexFraction(Vector<size_t> & flexible_sized_tracks_index,GridTrackSizingDirection direction,base::Optional<LayoutUnit> free_space) const631 double DefiniteSizeStrategy::FindUsedFlexFraction(
632 Vector<size_t>& flexible_sized_tracks_index,
633 GridTrackSizingDirection direction,
634 base::Optional<LayoutUnit> free_space) const {
635 GridSpan all_tracks_span = GridSpan::TranslatedDefiniteGridSpan(
636 0, algorithm_.Tracks(direction).size());
637 DCHECK(free_space);
638 return FindFrUnitSize(all_tracks_span, free_space.value());
639 }
640
FreeSpaceForStretchAutoTracksStep() const641 LayoutUnit DefiniteSizeStrategy::FreeSpaceForStretchAutoTracksStep() const {
642 DCHECK(algorithm_.FreeSpace(Direction()));
643 return algorithm_.FreeSpace(Direction()).value();
644 }
645
646 DISABLE_CFI_PERF
MinContentForChild(LayoutBox & child) const647 LayoutUnit DefiniteSizeStrategy::MinContentForChild(LayoutBox& child) const {
648 GridTrackSizingDirection child_inline_direction =
649 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
650 kForColumns);
651 if (Direction() == child_inline_direction && child.NeedsLayout() &&
652 ShouldClearOverrideContainingBlockContentSizeForChild(
653 *GetLayoutGrid(), child, child_inline_direction)) {
654 SetOverrideContainingBlockContentSizeForChild(child, child_inline_direction,
655 LayoutUnit());
656 }
657
658 return GridTrackSizingAlgorithmStrategy::MinContentForChild(child);
659 }
660
LayoutGridItemForMinSizeComputation(LayoutBox & child,bool override_size_has_changed) const661 void IndefiniteSizeStrategy::LayoutGridItemForMinSizeComputation(
662 LayoutBox& child,
663 bool override_size_has_changed) const {
664 if (override_size_has_changed && Direction() != kForColumns) {
665 child.SetSelfNeedsLayoutForAvailableSpace(true);
666 child.LayoutIfNeeded();
667 }
668 }
669
MaximizeTracks(Vector<GridTrack> & tracks,base::Optional<LayoutUnit> &)670 void IndefiniteSizeStrategy::MaximizeTracks(Vector<GridTrack>& tracks,
671 base::Optional<LayoutUnit>&) {
672 for (auto& track : tracks)
673 track.SetBaseSize(track.GrowthLimit());
674 }
675
NormalizedFlexFraction(const GridTrack & track)676 static inline double NormalizedFlexFraction(const GridTrack& track) {
677 double flex_factor = track.CachedTrackSize().MaxTrackBreadth().Flex();
678 return track.BaseSize() / std::max<double>(1, flex_factor);
679 }
680
FindUsedFlexFraction(Vector<size_t> & flexible_sized_tracks_index,GridTrackSizingDirection direction,base::Optional<LayoutUnit>) const681 double IndefiniteSizeStrategy::FindUsedFlexFraction(
682 Vector<size_t>& flexible_sized_tracks_index,
683 GridTrackSizingDirection direction,
684 base::Optional<LayoutUnit>) const {
685 auto all_tracks = algorithm_.Tracks(direction);
686
687 double flex_fraction = 0;
688 for (const auto& track_index : flexible_sized_tracks_index) {
689 flex_fraction = std::max(flex_fraction,
690 NormalizedFlexFraction(all_tracks[track_index]));
691 }
692
693 const Grid& grid = algorithm_.GetGrid();
694 if (!grid.HasGridItems())
695 return flex_fraction;
696
697 for (size_t i = 0; i < flexible_sized_tracks_index.size(); ++i) {
698 auto iterator =
699 grid.CreateIterator(direction, flexible_sized_tracks_index[i]);
700 while (LayoutBox* grid_item = iterator->NextGridItem()) {
701 const GridSpan& span = grid.GridItemSpan(*grid_item, direction);
702
703 // Do not include already processed items.
704 if (i > 0 && span.StartLine() <= flexible_sized_tracks_index[i - 1])
705 continue;
706
707 // Removing gutters from the max-content contribution of the item,
708 // so they are not taken into account in FindFrUnitSize().
709 LayoutUnit left_over_space =
710 MaxContentForChild(*grid_item) -
711 GetLayoutGrid()->GuttersSize(algorithm_.GetGrid(), direction,
712 span.StartLine(), span.IntegerSpan(),
713 AvailableSpace());
714 flex_fraction =
715 std::max(flex_fraction, FindFrUnitSize(span, left_over_space));
716 }
717 }
718
719 return flex_fraction;
720 }
721
RecomputeUsedFlexFractionIfNeeded(Vector<size_t> & flexible_sized_tracks_index,double & flex_fraction,Vector<LayoutUnit> & increments,LayoutUnit & total_growth) const722 bool IndefiniteSizeStrategy::RecomputeUsedFlexFractionIfNeeded(
723 Vector<size_t>& flexible_sized_tracks_index,
724 double& flex_fraction,
725 Vector<LayoutUnit>& increments,
726 LayoutUnit& total_growth) const {
727 if (Direction() == kForColumns)
728 return false;
729
730 const LayoutGrid* layout_grid = GetLayoutGrid();
731 LayoutUnit min_size = layout_grid->ComputeContentLogicalHeight(
732 kMinSize, layout_grid->StyleRef().LogicalMinHeight(), LayoutUnit(-1));
733 LayoutUnit max_size = layout_grid->ComputeContentLogicalHeight(
734 kMaxSize, layout_grid->StyleRef().LogicalMaxHeight(), LayoutUnit(-1));
735
736 // Redo the flex fraction computation using min|max-height as definite
737 // available space in case the total height is smaller than min-height or
738 // larger than max-height.
739 LayoutUnit rows_size = total_growth + ComputeTrackBasedSize();
740 bool check_min_size = min_size && rows_size < min_size;
741 bool check_max_size = max_size != -1 && rows_size > max_size;
742 if (!check_min_size && !check_max_size)
743 return false;
744
745 LayoutUnit free_space = check_max_size ? max_size : LayoutUnit(-1);
746 const Grid& grid = algorithm_.GetGrid();
747 free_space =
748 std::max(free_space, min_size) -
749 layout_grid->GuttersSize(grid, kForRows, 0, grid.NumTracks(kForRows),
750 AvailableSpace());
751
752 size_t number_of_tracks = algorithm_.Tracks(Direction()).size();
753 flex_fraction = FindFrUnitSize(
754 GridSpan::TranslatedDefiniteGridSpan(0, number_of_tracks), free_space);
755 return true;
756 }
757
FreeSpaceForStretchAutoTracksStep() const758 LayoutUnit IndefiniteSizeStrategy::FreeSpaceForStretchAutoTracksStep() const {
759 DCHECK(!algorithm_.FreeSpace(Direction()));
760 if (Direction() == kForColumns)
761 return LayoutUnit();
762
763 LayoutUnit min_size = GetLayoutGrid()->ComputeContentLogicalHeight(
764 kMinSize, GetLayoutGrid()->StyleRef().LogicalMinHeight(), LayoutUnit(-1));
765 return min_size - ComputeTrackBasedSize();
766 }
767
768 DISABLE_CFI_PERF
MinContentForChild(LayoutBox & child) const769 LayoutUnit IndefiniteSizeStrategy::MinContentForChild(LayoutBox& child) const {
770 GridTrackSizingDirection child_inline_direction =
771 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
772 kForColumns);
773 if (Direction() == child_inline_direction || Direction() == kForRows)
774 return GridTrackSizingAlgorithmStrategy::MinContentForChild(child);
775
776 // This code is executed only when computing the grid's intrinsic
777 // width based on an orthogonal child. We rely on the pre-layout
778 // performed in LayoutGrid::LayoutOrthogonalWritingModeRoots.
779 DCHECK(GridLayoutUtils::IsOrthogonalChild(*GetLayoutGrid(), child));
780
781 return child.LogicalHeight() +
782 GridLayoutUtils::MarginLogicalHeightForChild(*GetLayoutGrid(), child) +
783 algorithm_.BaselineOffsetForChild(child,
784 GridAxisForDirection(Direction()));
785 }
786
787 DISABLE_CFI_PERF
MaxContentForChild(LayoutBox & child) const788 LayoutUnit IndefiniteSizeStrategy::MaxContentForChild(LayoutBox& child) const {
789 GridTrackSizingDirection child_inline_direction =
790 GridLayoutUtils::FlowAwareDirectionForChild(*GetLayoutGrid(), child,
791 kForColumns);
792 if (Direction() == child_inline_direction || Direction() == kForRows)
793 return GridTrackSizingAlgorithmStrategy::MaxContentForChild(child);
794
795 // This code is executed only when computing the grid's intrinsic
796 // width based on an orthogonal child. We rely on the pre-layout
797 // performed in LayoutGrid::LayoutOrthogonalWritingModeRoots.
798 DCHECK(GridLayoutUtils::IsOrthogonalChild(*GetLayoutGrid(), child));
799
800 return child.LogicalHeight() +
801 GridLayoutUtils::MarginLogicalHeightForChild(*GetLayoutGrid(), child);
802 }
803
IsComputingSizeContainment() const804 bool IndefiniteSizeStrategy::IsComputingSizeContainment() const {
805 return GetLayoutGrid()->ShouldApplySizeContainment();
806 }
807
FreeSpace(GridTrackSizingDirection direction) const808 base::Optional<LayoutUnit> GridTrackSizingAlgorithm::FreeSpace(
809 GridTrackSizingDirection direction) const {
810 return direction == kForRows ? free_space_rows_ : free_space_columns_;
811 }
812
AvailableSpace(GridTrackSizingDirection direction) const813 base::Optional<LayoutUnit> GridTrackSizingAlgorithm::AvailableSpace(
814 GridTrackSizingDirection direction) const {
815 return direction == kForRows ? available_space_rows_
816 : available_space_columns_;
817 }
818
AvailableSpace() const819 base::Optional<LayoutUnit> GridTrackSizingAlgorithm::AvailableSpace() const {
820 DCHECK(WasSetup());
821 return AvailableSpace(direction_);
822 }
823
SetAvailableSpace(GridTrackSizingDirection direction,base::Optional<LayoutUnit> available_space)824 void GridTrackSizingAlgorithm::SetAvailableSpace(
825 GridTrackSizingDirection direction,
826 base::Optional<LayoutUnit> available_space) {
827 if (direction == kForColumns)
828 available_space_columns_ = available_space;
829 else
830 available_space_rows_ = available_space;
831 }
832
Tracks(GridTrackSizingDirection direction)833 Vector<GridTrack>& GridTrackSizingAlgorithm::Tracks(
834 GridTrackSizingDirection direction) {
835 return direction == kForColumns ? columns_ : rows_;
836 }
837
Tracks(GridTrackSizingDirection direction) const838 const Vector<GridTrack>& GridTrackSizingAlgorithm::Tracks(
839 GridTrackSizingDirection direction) const {
840 return direction == kForColumns ? columns_ : rows_;
841 }
842
SetFreeSpace(GridTrackSizingDirection direction,base::Optional<LayoutUnit> free_space)843 void GridTrackSizingAlgorithm::SetFreeSpace(
844 GridTrackSizingDirection direction,
845 base::Optional<LayoutUnit> free_space) {
846 if (direction == kForColumns)
847 free_space_columns_ = free_space;
848 else
849 free_space_rows_ = free_space;
850 }
851
RawGridTrackSize(GridTrackSizingDirection direction,size_t translated_index) const852 const GridTrackSize& GridTrackSizingAlgorithm::RawGridTrackSize(
853 GridTrackSizingDirection direction,
854 size_t translated_index) const {
855 bool is_row_axis = direction == kForColumns;
856 const Vector<GridTrackSize>& track_styles =
857 is_row_axis ? layout_grid_->StyleRef().GridTemplateColumns()
858 : layout_grid_->StyleRef().GridTemplateRows();
859 const Vector<GridTrackSize>& auto_repeat_track_styles =
860 is_row_axis ? layout_grid_->StyleRef().GridAutoRepeatColumns()
861 : layout_grid_->StyleRef().GridAutoRepeatRows();
862 const Vector<GridTrackSize>& auto_track_styles =
863 is_row_axis ? layout_grid_->StyleRef().GridAutoColumns()
864 : layout_grid_->StyleRef().GridAutoRows();
865 size_t insertion_point =
866 is_row_axis
867 ? layout_grid_->StyleRef().GridAutoRepeatColumnsInsertionPoint()
868 : layout_grid_->StyleRef().GridAutoRepeatRowsInsertionPoint();
869 size_t auto_repeat_tracks_count = grid_.AutoRepeatTracks(direction);
870
871 // We should not use GridPositionsResolver::explicitGridXXXCount() for this
872 // because the explicit grid might be larger than the number of tracks in
873 // grid-template-rows|columns (if grid-template-areas is specified for
874 // example).
875 size_t explicit_tracks_count = track_styles.size() + auto_repeat_tracks_count;
876
877 int untranslated_index_as_int =
878 translated_index + grid_.SmallestTrackStart(direction);
879 size_t auto_track_styles_size = auto_track_styles.size();
880 if (untranslated_index_as_int < 0) {
881 int index =
882 untranslated_index_as_int % static_cast<int>(auto_track_styles_size);
883 // We need to traspose the index because the first negative implicit line
884 // will get the last defined auto track and so on.
885 index += index ? auto_track_styles_size : 0;
886 return auto_track_styles[index];
887 }
888
889 size_t untranslated_index = static_cast<size_t>(untranslated_index_as_int);
890 if (untranslated_index >= explicit_tracks_count) {
891 return auto_track_styles[(untranslated_index - explicit_tracks_count) %
892 auto_track_styles_size];
893 }
894
895 if (LIKELY(!auto_repeat_tracks_count) || untranslated_index < insertion_point)
896 return track_styles[untranslated_index];
897
898 if (untranslated_index < (insertion_point + auto_repeat_tracks_count)) {
899 size_t auto_repeat_local_index =
900 untranslated_index_as_int - insertion_point;
901 return auto_repeat_track_styles[auto_repeat_local_index %
902 auto_repeat_track_styles.size()];
903 }
904
905 return track_styles[untranslated_index - auto_repeat_tracks_count];
906 }
907
IsRelativeGridLengthAsAuto(const GridLength & length,GridTrackSizingDirection direction) const908 bool GridTrackSizingAlgorithm::IsRelativeGridLengthAsAuto(
909 const GridLength& length,
910 GridTrackSizingDirection direction) const {
911 return length.HasPercentage() && !AvailableSpace(direction);
912 }
913
IsRelativeSizedTrackAsAuto(const GridTrackSize & track_size,GridTrackSizingDirection direction) const914 bool GridTrackSizingAlgorithm::IsRelativeSizedTrackAsAuto(
915 const GridTrackSize& track_size,
916 GridTrackSizingDirection direction) const {
917 if (track_size.MinTrackBreadth().HasPercentage())
918 return IsRelativeGridLengthAsAuto(track_size.MinTrackBreadth(), direction);
919 if (track_size.MaxTrackBreadth().HasPercentage())
920 return IsRelativeGridLengthAsAuto(track_size.MaxTrackBreadth(), direction);
921 return false;
922 }
923
CalculateGridTrackSize(GridTrackSizingDirection direction,size_t translated_index) const924 GridTrackSize GridTrackSizingAlgorithm::CalculateGridTrackSize(
925 GridTrackSizingDirection direction,
926 size_t translated_index) const {
927 DCHECK(WasSetup());
928 // Collapse empty auto repeat tracks if auto-fit.
929 if (grid_.HasAutoRepeatEmptyTracks(direction) &&
930 grid_.IsEmptyAutoRepeatTrack(direction, translated_index))
931 return {Length::Fixed(), kLengthTrackSizing};
932
933 const GridTrackSize& track_size =
934 RawGridTrackSize(direction, translated_index);
935 if (track_size.IsFitContent()) {
936 return IsRelativeGridLengthAsAuto(track_size.FitContentTrackBreadth(),
937 direction)
938 ? GridTrackSize(Length::Auto(), Length::MaxContent())
939 : track_size;
940 }
941
942 GridLength min_track_breadth = track_size.MinTrackBreadth();
943 GridLength max_track_breadth = track_size.MaxTrackBreadth();
944 if (strategy_->IsComputingSizeContainment())
945 return GridTrackSize(min_track_breadth, max_track_breadth);
946
947 // If the logical width/height of the grid container is indefinite, percentage
948 // values are treated as <auto>.
949 if (IsRelativeSizedTrackAsAuto(track_size, direction)) {
950 if (direction == kForRows) {
951 UseCounter::Count(layout_grid_->GetDocument(),
952 WebFeature::kGridRowTrackPercentIndefiniteHeight);
953 }
954 if (min_track_breadth.HasPercentage())
955 min_track_breadth = Length::Auto();
956 if (max_track_breadth.HasPercentage())
957 max_track_breadth = Length::Auto();
958 }
959
960 // Flex sizes are invalid as a min sizing function. However we still can have
961 // a flexible |minTrackBreadth| if the track had a flex size directly (e.g.
962 // "1fr"), the spec says that in this case it implies an automatic minimum.
963 // TODO(jfernandez): https://github.com/w3c/csswg-drafts/issues/2611
964 // TODO(jfernandez): We may have to change IsIntrinsicSizedGridArea too.
965 if (min_track_breadth.IsFlex())
966 min_track_breadth = Length::Auto();
967
968 return GridTrackSize(min_track_breadth, max_track_breadth);
969 }
970
InitialBaseSize(const GridTrackSize & track_size) const971 LayoutUnit GridTrackSizingAlgorithm::InitialBaseSize(
972 const GridTrackSize& track_size) const {
973 const GridLength& grid_length = track_size.MinTrackBreadth();
974 if (grid_length.IsFlex())
975 return LayoutUnit();
976
977 const Length& track_length = grid_length.length();
978 if (track_length.IsSpecified()) {
979 return ValueForLength(track_length,
980 AvailableSpace().value_or(LayoutUnit()));
981 }
982
983 DCHECK(track_length.IsMinContent() || track_length.IsAuto() ||
984 track_length.IsMaxContent());
985 return LayoutUnit();
986 }
987
InitialGrowthLimit(const GridTrackSize & track_size,LayoutUnit base_size) const988 LayoutUnit GridTrackSizingAlgorithm::InitialGrowthLimit(
989 const GridTrackSize& track_size,
990 LayoutUnit base_size) const {
991 const GridLength& grid_length = track_size.MaxTrackBreadth();
992 if (grid_length.IsFlex())
993 return base_size;
994
995 const Length& track_length = grid_length.length();
996 if (track_length.IsSpecified()) {
997 return ValueForLength(track_length,
998 AvailableSpace().value_or(LayoutUnit()));
999 }
1000
1001 DCHECK(track_length.IsMinContent() || track_length.IsAuto() ||
1002 track_length.IsMaxContent());
1003 return LayoutUnit(kInfinity);
1004 }
1005
InitializeTrackSizes()1006 void GridTrackSizingAlgorithm::InitializeTrackSizes() {
1007 DCHECK(content_sized_tracks_index_.IsEmpty());
1008 DCHECK(flexible_sized_tracks_index_.IsEmpty());
1009 DCHECK(auto_sized_tracks_for_stretch_index_.IsEmpty());
1010 DCHECK(!has_percent_sized_rows_indefinite_height_);
1011 Vector<GridTrack>& track_list = Tracks(direction_);
1012 bool indefinite_height =
1013 direction_ == kForRows && !layout_grid_->CachedHasDefiniteLogicalHeight();
1014 size_t num_tracks = track_list.size();
1015 for (size_t i = 0; i < num_tracks; ++i) {
1016 const GridTrackSize& track_size = CalculateGridTrackSize(direction_, i);
1017 GridTrack& track = track_list[i];
1018 track.SetCachedTrackSize(track_size);
1019 track.SetBaseSize(InitialBaseSize(track_size));
1020 track.SetGrowthLimit(InitialGrowthLimit(track_size, track.BaseSize()));
1021 track.SetInfinitelyGrowable(false);
1022
1023 if (track_size.IsFitContent()) {
1024 track.SetGrowthLimitCap(
1025 ValueForLength(track_size.FitContentTrackBreadth().length(),
1026 AvailableSpace().value_or(LayoutUnit())));
1027 }
1028
1029 if (track_size.IsContentSized())
1030 content_sized_tracks_index_.push_back(i);
1031 if (track_size.MaxTrackBreadth().IsFlex())
1032 flexible_sized_tracks_index_.push_back(i);
1033 if (track_size.HasAutoMaxTrackBreadth() && !track_size.IsFitContent())
1034 auto_sized_tracks_for_stretch_index_.push_back(i);
1035
1036 if (!has_percent_sized_rows_indefinite_height_ && indefinite_height) {
1037 const GridTrackSize& raw_track_size = RawGridTrackSize(direction_, i);
1038 if (raw_track_size.MinTrackBreadth().HasPercentage() ||
1039 raw_track_size.MaxTrackBreadth().HasPercentage())
1040 has_percent_sized_rows_indefinite_height_ = true;
1041 }
1042 }
1043 }
1044
SizeTrackToFitNonSpanningItem(const GridSpan & span,LayoutBox & grid_item,GridTrack & track)1045 void GridTrackSizingAlgorithm::SizeTrackToFitNonSpanningItem(
1046 const GridSpan& span,
1047 LayoutBox& grid_item,
1048 GridTrack& track) {
1049 const size_t track_position = span.StartLine();
1050 const GridTrackSize& track_size =
1051 Tracks(direction_)[track_position].CachedTrackSize();
1052
1053 if (track_size.HasMinContentMinTrackBreadth()) {
1054 track.SetBaseSize(
1055 std::max(track.BaseSize(), strategy_->MinContentForChild(grid_item)));
1056 } else if (track_size.HasMaxContentMinTrackBreadth()) {
1057 track.SetBaseSize(
1058 std::max(track.BaseSize(), strategy_->MaxContentForChild(grid_item)));
1059 } else if (track_size.HasAutoMinTrackBreadth()) {
1060 track.SetBaseSize(
1061 std::max(track.BaseSize(), strategy_->MinSizeForChild(grid_item)));
1062 }
1063
1064 if (track_size.HasMinContentMaxTrackBreadth()) {
1065 track.SetGrowthLimit(std::max(track.GrowthLimit(),
1066 strategy_->MinContentForChild(grid_item)));
1067 } else if (track_size.HasMaxContentOrAutoMaxTrackBreadth()) {
1068 LayoutUnit growth_limit = strategy_->MaxContentForChild(grid_item);
1069 if (track_size.IsFitContent()) {
1070 growth_limit =
1071 std::min(growth_limit,
1072 ValueForLength(track_size.FitContentTrackBreadth().length(),
1073 AvailableSpace().value_or(LayoutUnit())));
1074 }
1075 track.SetGrowthLimit(std::max(track.GrowthLimit(), growth_limit));
1076 }
1077 }
1078
SpanningItemCrossesFlexibleSizedTracks(const GridSpan & span) const1079 bool GridTrackSizingAlgorithm::SpanningItemCrossesFlexibleSizedTracks(
1080 const GridSpan& span) const {
1081 const Vector<GridTrack>& track_list = Tracks(direction_);
1082 for (const auto& track_position : span) {
1083 const GridTrackSize& track_size =
1084 track_list[track_position].CachedTrackSize();
1085 if (track_size.MinTrackBreadth().IsFlex() ||
1086 track_size.MaxTrackBreadth().IsFlex())
1087 return true;
1088 }
1089
1090 return false;
1091 }
1092
1093 // We're basically using a class instead of a std::pair because of accessing
1094 // gridItem() or getGridSpan() is much more self-explanatory that using .first
1095 // or .second members in the pair. Having a std::pair<LayoutBox*, size_t>
1096 // does not work either because we still need the GridSpan so we'd have to add
1097 // an extra hash lookup for each item.
1098 class GridItemWithSpan {
1099 public:
GridItemWithSpan(LayoutBox & grid_item,const GridSpan & grid_span)1100 GridItemWithSpan(LayoutBox& grid_item, const GridSpan& grid_span)
1101 : grid_item_(&grid_item), grid_span_(grid_span) {}
1102
GridItem() const1103 LayoutBox& GridItem() const { return *grid_item_; }
GetGridSpan() const1104 GridSpan GetGridSpan() const { return grid_span_; }
1105
operator <(const GridItemWithSpan other) const1106 bool operator<(const GridItemWithSpan other) const {
1107 return grid_span_.IntegerSpan() < other.grid_span_.IntegerSpan();
1108 }
1109
1110 private:
1111 LayoutBox* grid_item_;
1112 GridSpan grid_span_;
1113 };
1114
1115 struct GridItemsSpanGroupRange {
1116 Vector<GridItemWithSpan>::iterator range_start;
1117 Vector<GridItemWithSpan>::iterator range_end;
1118 };
1119
1120 enum TrackSizeRestriction {
1121 kAllowInfinity,
1122 kForbidInfinity,
1123 };
1124
TrackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase,const GridTrack & track,TrackSizeRestriction restriction)1125 static LayoutUnit TrackSizeForTrackSizeComputationPhase(
1126 TrackSizeComputationPhase phase,
1127 const GridTrack& track,
1128 TrackSizeRestriction restriction) {
1129 switch (phase) {
1130 case kResolveIntrinsicMinimums:
1131 case kResolveContentBasedMinimums:
1132 case kResolveMaxContentMinimums:
1133 case kMaximizeTracks:
1134 return track.BaseSize();
1135 case kResolveIntrinsicMaximums:
1136 case kResolveMaxContentMaximums:
1137 const LayoutUnit& growth_limit = track.GrowthLimit();
1138 if (restriction == kAllowInfinity)
1139 return growth_limit;
1140 return growth_limit == kInfinity ? track.BaseSize() : growth_limit;
1141 }
1142
1143 NOTREACHED();
1144 return track.BaseSize();
1145 }
1146
ShouldProcessTrackForTrackSizeComputationPhase(TrackSizeComputationPhase phase,const GridTrackSize & track_size)1147 static bool ShouldProcessTrackForTrackSizeComputationPhase(
1148 TrackSizeComputationPhase phase,
1149 const GridTrackSize& track_size) {
1150 switch (phase) {
1151 case kResolveIntrinsicMinimums:
1152 return track_size.HasIntrinsicMinTrackBreadth();
1153 case kResolveContentBasedMinimums:
1154 return track_size.HasMinOrMaxContentMinTrackBreadth();
1155 case kResolveMaxContentMinimums:
1156 return track_size.HasMaxContentMinTrackBreadth();
1157 case kResolveIntrinsicMaximums:
1158 return track_size.HasIntrinsicMaxTrackBreadth();
1159 case kResolveMaxContentMaximums:
1160 return track_size.HasMaxContentOrAutoMaxTrackBreadth();
1161 case kMaximizeTracks:
1162 NOTREACHED();
1163 return false;
1164 }
1165
1166 NOTREACHED();
1167 return false;
1168 }
1169
TrackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(TrackSizeComputationPhase phase,const GridTrackSize & track_size)1170 static bool TrackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(
1171 TrackSizeComputationPhase phase,
1172 const GridTrackSize& track_size) {
1173 switch (phase) {
1174 case kResolveIntrinsicMinimums:
1175 case kResolveContentBasedMinimums:
1176 return track_size
1177 .HasAutoOrMinContentMinTrackBreadthAndIntrinsicMaxTrackBreadth();
1178 case kResolveMaxContentMinimums:
1179 return track_size
1180 .HasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth();
1181 case kResolveIntrinsicMaximums:
1182 case kResolveMaxContentMaximums:
1183 return true;
1184 case kMaximizeTracks:
1185 NOTREACHED();
1186 return false;
1187 }
1188
1189 NOTREACHED();
1190 return false;
1191 }
1192
MarkAsInfinitelyGrowableForTrackSizeComputationPhase(TrackSizeComputationPhase phase,GridTrack & track)1193 static void MarkAsInfinitelyGrowableForTrackSizeComputationPhase(
1194 TrackSizeComputationPhase phase,
1195 GridTrack& track) {
1196 switch (phase) {
1197 case kResolveIntrinsicMinimums:
1198 case kResolveContentBasedMinimums:
1199 case kResolveMaxContentMinimums:
1200 return;
1201 case kResolveIntrinsicMaximums:
1202 if (TrackSizeForTrackSizeComputationPhase(phase, track, kAllowInfinity) ==
1203 kInfinity &&
1204 track.PlannedSize() != kInfinity)
1205 track.SetInfinitelyGrowable(true);
1206 return;
1207 case kResolveMaxContentMaximums:
1208 if (track.InfinitelyGrowable())
1209 track.SetInfinitelyGrowable(false);
1210 return;
1211 case kMaximizeTracks:
1212 NOTREACHED();
1213 return;
1214 }
1215
1216 NOTREACHED();
1217 }
1218
UpdateTrackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase,GridTrack & track)1219 static void UpdateTrackSizeForTrackSizeComputationPhase(
1220 TrackSizeComputationPhase phase,
1221 GridTrack& track) {
1222 switch (phase) {
1223 case kResolveIntrinsicMinimums:
1224 case kResolveContentBasedMinimums:
1225 case kResolveMaxContentMinimums:
1226 track.SetBaseSize(track.PlannedSize());
1227 return;
1228 case kResolveIntrinsicMaximums:
1229 case kResolveMaxContentMaximums:
1230 track.SetGrowthLimit(track.PlannedSize());
1231 return;
1232 case kMaximizeTracks:
1233 NOTREACHED();
1234 return;
1235 }
1236
1237 NOTREACHED();
1238 }
1239
ItemSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase,LayoutBox & grid_item) const1240 LayoutUnit GridTrackSizingAlgorithm::ItemSizeForTrackSizeComputationPhase(
1241 TrackSizeComputationPhase phase,
1242 LayoutBox& grid_item) const {
1243 switch (phase) {
1244 case kResolveIntrinsicMinimums:
1245 case kResolveIntrinsicMaximums:
1246 return strategy_->MinSizeForChild(grid_item);
1247 case kResolveContentBasedMinimums:
1248 return strategy_->MinContentForChild(grid_item);
1249 case kResolveMaxContentMinimums:
1250 case kResolveMaxContentMaximums:
1251 return strategy_->MaxContentForChild(grid_item);
1252 case kMaximizeTracks:
1253 NOTREACHED();
1254 return LayoutUnit();
1255 }
1256
1257 NOTREACHED();
1258 return LayoutUnit();
1259 }
1260
SortByGridTrackGrowthPotential(const GridTrack * track1,const GridTrack * track2)1261 static bool SortByGridTrackGrowthPotential(const GridTrack* track1,
1262 const GridTrack* track2) {
1263 // This check ensures that we respect the irreflexivity property of the strict
1264 // weak ordering required by std::sort(forall x: NOT x < x).
1265 bool track1_has_infinite_growth_potential_without_cap =
1266 track1->InfiniteGrowthPotential() && !track1->GrowthLimitCap();
1267 bool track2_has_infinite_growth_potential_without_cap =
1268 track2->InfiniteGrowthPotential() && !track2->GrowthLimitCap();
1269
1270 if (track1_has_infinite_growth_potential_without_cap &&
1271 track2_has_infinite_growth_potential_without_cap)
1272 return false;
1273
1274 if (track1_has_infinite_growth_potential_without_cap ||
1275 track2_has_infinite_growth_potential_without_cap)
1276 return track2_has_infinite_growth_potential_without_cap;
1277
1278 LayoutUnit track1_limit =
1279 track1->GrowthLimitCap().value_or(track1->GrowthLimit());
1280 LayoutUnit track2_limit =
1281 track2->GrowthLimitCap().value_or(track2->GrowthLimit());
1282 return (track1_limit - track1->BaseSize()) <
1283 (track2_limit - track2->BaseSize());
1284 }
1285
ClampGrowthShareIfNeeded(TrackSizeComputationPhase phase,const GridTrack & track,LayoutUnit & growth_share)1286 static void ClampGrowthShareIfNeeded(TrackSizeComputationPhase phase,
1287 const GridTrack& track,
1288 LayoutUnit& growth_share) {
1289 if (phase != kResolveMaxContentMaximums || !track.GrowthLimitCap())
1290 return;
1291
1292 LayoutUnit distance_to_cap =
1293 track.GrowthLimitCap().value() - track.SizeDuringDistribution();
1294 if (distance_to_cap <= 0)
1295 return;
1296
1297 growth_share = std::min(growth_share, distance_to_cap);
1298 }
1299
1300 template <TrackSizeComputationPhase phase>
DistributeSpaceToTracks(Vector<GridTrack * > & tracks,Vector<GridTrack * > * grow_beyond_growth_limits_tracks,LayoutUnit & available_logical_space) const1301 void GridTrackSizingAlgorithm::DistributeSpaceToTracks(
1302 Vector<GridTrack*>& tracks,
1303 Vector<GridTrack*>* grow_beyond_growth_limits_tracks,
1304 LayoutUnit& available_logical_space) const {
1305 DCHECK_GE(available_logical_space, 0);
1306
1307 for (auto* track : tracks) {
1308 track->SetSizeDuringDistribution(
1309 TrackSizeForTrackSizeComputationPhase(phase, *track, kForbidInfinity));
1310 }
1311
1312 if (available_logical_space > 0) {
1313 std::sort(tracks.begin(), tracks.end(), SortByGridTrackGrowthPotential);
1314
1315 size_t tracks_size = tracks.size();
1316 for (size_t i = 0; i < tracks_size; ++i) {
1317 GridTrack& track = *tracks[i];
1318 LayoutUnit available_logical_space_share =
1319 available_logical_space / (tracks_size - i);
1320 const LayoutUnit& track_breadth =
1321 TrackSizeForTrackSizeComputationPhase(phase, track, kForbidInfinity);
1322 LayoutUnit growth_share =
1323 track.InfiniteGrowthPotential()
1324 ? available_logical_space_share
1325 : std::min(available_logical_space_share,
1326 track.GrowthLimit() - track_breadth);
1327 ClampGrowthShareIfNeeded(phase, track, growth_share);
1328 DCHECK_GE(growth_share, 0) << "We must never shrink any grid track or "
1329 "else we can't guarantee we abide by our "
1330 "min-sizing function.";
1331 track.GrowSizeDuringDistribution(growth_share);
1332 available_logical_space -= growth_share;
1333 }
1334 }
1335
1336 if (available_logical_space > 0 && grow_beyond_growth_limits_tracks) {
1337 // We need to sort them because there might be tracks with growth limit caps
1338 // (like the ones with fit-content()) which cannot indefinitely grow over
1339 // the limits.
1340 if (phase == kResolveMaxContentMaximums) {
1341 std::sort(grow_beyond_growth_limits_tracks->begin(),
1342 grow_beyond_growth_limits_tracks->end(),
1343 SortByGridTrackGrowthPotential);
1344 }
1345
1346 size_t tracks_growing_above_max_breadth_size =
1347 grow_beyond_growth_limits_tracks->size();
1348 for (size_t i = 0; i < tracks_growing_above_max_breadth_size; ++i) {
1349 GridTrack* track = grow_beyond_growth_limits_tracks->at(i);
1350 LayoutUnit growth_share =
1351 available_logical_space / (tracks_growing_above_max_breadth_size - i);
1352 ClampGrowthShareIfNeeded(phase, *track, growth_share);
1353 DCHECK_GE(growth_share, 0) << "We must never shrink any grid track or "
1354 "else we can't guarantee we abide by our "
1355 "min-sizing function.";
1356 track->GrowSizeDuringDistribution(growth_share);
1357 available_logical_space -= growth_share;
1358 }
1359 }
1360
1361 for (auto* track : tracks) {
1362 track->SetPlannedSize(
1363 track->PlannedSize() == kInfinity
1364 ? track->SizeDuringDistribution()
1365 : std::max(track->PlannedSize(), track->SizeDuringDistribution()));
1366 }
1367 }
1368
1369 template <TrackSizeComputationPhase phase>
IncreaseSizesToAccommodateSpanningItems(const GridItemsSpanGroupRange & grid_items_with_span)1370 void GridTrackSizingAlgorithm::IncreaseSizesToAccommodateSpanningItems(
1371 const GridItemsSpanGroupRange& grid_items_with_span) {
1372 Vector<GridTrack>& all_tracks = Tracks(direction_);
1373 for (const auto& track_index : content_sized_tracks_index_) {
1374 GridTrack& track = all_tracks[track_index];
1375 track.SetPlannedSize(
1376 TrackSizeForTrackSizeComputationPhase(phase, track, kAllowInfinity));
1377 }
1378
1379 Vector<GridTrack*> grow_beyond_growth_limits_tracks;
1380 Vector<GridTrack*> filtered_tracks;
1381 for (auto* it = grid_items_with_span.range_start;
1382 it != grid_items_with_span.range_end; ++it) {
1383 GridItemWithSpan& grid_item_with_span = *it;
1384 DCHECK_GT(grid_item_with_span.GetGridSpan().IntegerSpan(), 1u);
1385 const GridSpan& item_span = grid_item_with_span.GetGridSpan();
1386
1387 grow_beyond_growth_limits_tracks.Shrink(0);
1388 filtered_tracks.Shrink(0);
1389 LayoutUnit spanning_tracks_size;
1390 for (const auto& track_position : item_span) {
1391 GridTrack& track = all_tracks[track_position];
1392 const GridTrackSize& track_size = track.CachedTrackSize();
1393 spanning_tracks_size +=
1394 TrackSizeForTrackSizeComputationPhase(phase, track, kForbidInfinity);
1395 if (!ShouldProcessTrackForTrackSizeComputationPhase(phase, track_size))
1396 continue;
1397
1398 filtered_tracks.push_back(&track);
1399
1400 if (TrackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(
1401 phase, track_size))
1402 grow_beyond_growth_limits_tracks.push_back(&track);
1403 }
1404
1405 if (filtered_tracks.IsEmpty())
1406 continue;
1407
1408 spanning_tracks_size +=
1409 layout_grid_->GuttersSize(grid_, direction_, item_span.StartLine(),
1410 item_span.IntegerSpan(), AvailableSpace());
1411
1412 LayoutUnit extra_space = ItemSizeForTrackSizeComputationPhase(
1413 phase, grid_item_with_span.GridItem()) -
1414 spanning_tracks_size;
1415 extra_space = extra_space.ClampNegativeToZero();
1416 auto& tracks_to_grow_beyond_growth_limits =
1417 grow_beyond_growth_limits_tracks.IsEmpty()
1418 ? filtered_tracks
1419 : grow_beyond_growth_limits_tracks;
1420 DistributeSpaceToTracks<phase>(
1421 filtered_tracks, &tracks_to_grow_beyond_growth_limits, extra_space);
1422 }
1423
1424 for (const auto& track_index : content_sized_tracks_index_) {
1425 GridTrack& track = all_tracks[track_index];
1426 MarkAsInfinitelyGrowableForTrackSizeComputationPhase(phase, track);
1427 UpdateTrackSizeForTrackSizeComputationPhase(phase, track);
1428 }
1429 }
1430
ResolveIntrinsicTrackSizes()1431 void GridTrackSizingAlgorithm::ResolveIntrinsicTrackSizes() {
1432 Vector<GridTrack>& all_tracks = Tracks(direction_);
1433 Vector<GridItemWithSpan> items_sorted_by_increasing_span;
1434 if (grid_.HasGridItems()) {
1435 HashSet<LayoutBox*> items_set;
1436 for (const auto& track_index : content_sized_tracks_index_) {
1437 auto iterator = grid_.CreateIterator(direction_, track_index);
1438 GridTrack& track = all_tracks[track_index];
1439 while (auto* grid_item = iterator->NextGridItem()) {
1440 if (items_set.insert(grid_item).is_new_entry) {
1441 const GridSpan& span = grid_.GridItemSpan(*grid_item, direction_);
1442 if (span.IntegerSpan() == 1) {
1443 SizeTrackToFitNonSpanningItem(span, *grid_item, track);
1444 } else if (!SpanningItemCrossesFlexibleSizedTracks(span)) {
1445 items_sorted_by_increasing_span.push_back(
1446 GridItemWithSpan(*grid_item, span));
1447 }
1448 }
1449 }
1450 }
1451 std::sort(items_sorted_by_increasing_span.begin(),
1452 items_sorted_by_increasing_span.end());
1453 }
1454
1455 auto* it = items_sorted_by_increasing_span.begin();
1456 auto* end = items_sorted_by_increasing_span.end();
1457 while (it != end) {
1458 GridItemsSpanGroupRange span_group_range = {it,
1459 std::upper_bound(it, end, *it)};
1460 IncreaseSizesToAccommodateSpanningItems<kResolveIntrinsicMinimums>(
1461 span_group_range);
1462 IncreaseSizesToAccommodateSpanningItems<kResolveContentBasedMinimums>(
1463 span_group_range);
1464 IncreaseSizesToAccommodateSpanningItems<kResolveMaxContentMinimums>(
1465 span_group_range);
1466 IncreaseSizesToAccommodateSpanningItems<kResolveIntrinsicMaximums>(
1467 span_group_range);
1468 IncreaseSizesToAccommodateSpanningItems<kResolveMaxContentMaximums>(
1469 span_group_range);
1470 it = span_group_range.range_end;
1471 }
1472
1473 for (const auto& track_index : content_sized_tracks_index_) {
1474 GridTrack& track = all_tracks[track_index];
1475 if (track.GrowthLimit() == kInfinity)
1476 track.SetGrowthLimit(track.BaseSize());
1477 }
1478 }
1479
ComputeGridContainerIntrinsicSizes()1480 void GridTrackSizingAlgorithm::ComputeGridContainerIntrinsicSizes() {
1481 min_content_size_ = max_content_size_ = LayoutUnit();
1482
1483 Vector<GridTrack>& all_tracks = Tracks(direction_);
1484 for (auto& track : all_tracks) {
1485 DCHECK(strategy_->IsComputingSizeContainment() ||
1486 !track.InfiniteGrowthPotential());
1487 min_content_size_ += track.BaseSize();
1488 max_content_size_ +=
1489 track.GrowthLimitIsInfinite() ? track.BaseSize() : track.GrowthLimit();
1490 // The growth limit caps must be cleared now in order to properly sort
1491 // tracks by growth potential on an eventual "Maximize Tracks".
1492 track.SetGrowthLimitCap(base::nullopt);
1493 }
1494 }
1495
ComputeTrackBasedSize() const1496 LayoutUnit GridTrackSizingAlgorithm::ComputeTrackBasedSize() const {
1497 LayoutUnit size;
1498
1499 const Vector<GridTrack>& all_tracks = Tracks(direction_);
1500 for (auto& track : all_tracks) {
1501 size +=
1502 track.GrowthLimitIsInfinite() ? track.BaseSize() : track.GrowthLimit();
1503 }
1504
1505 size += layout_grid_->GuttersSize(grid_, direction_, 0, all_tracks.size(),
1506 AvailableSpace());
1507
1508 return size;
1509 }
1510
FindFrUnitSize(const GridSpan & tracks_span,LayoutUnit left_over_space) const1511 double GridTrackSizingAlgorithm::FindFrUnitSize(
1512 const GridSpan& tracks_span,
1513 LayoutUnit left_over_space) const {
1514 if (left_over_space <= 0)
1515 return 0;
1516
1517 const Vector<GridTrack>& all_tracks = Tracks(direction_);
1518 double flex_factor_sum = 0;
1519 Vector<size_t, 8> flexible_tracks_indexes;
1520 for (const auto& track_index : tracks_span) {
1521 const GridTrackSize& track_size = all_tracks[track_index].CachedTrackSize();
1522 if (!track_size.MaxTrackBreadth().IsFlex()) {
1523 left_over_space -= all_tracks[track_index].BaseSize();
1524 } else {
1525 flexible_tracks_indexes.push_back(track_index);
1526 flex_factor_sum += track_size.MaxTrackBreadth().Flex();
1527 }
1528 }
1529 // We don't remove the gutters from left_over_space here, because that was
1530 // already done before.
1531
1532 // The function is not called if we don't have <flex> grid tracks.
1533 DCHECK(!flexible_tracks_indexes.IsEmpty());
1534
1535 return ComputeFlexFactorUnitSize(all_tracks, flex_factor_sum, left_over_space,
1536 flexible_tracks_indexes);
1537 }
1538
ComputeFlexFactorUnitSize(const Vector<GridTrack> & tracks,double flex_factor_sum,LayoutUnit & left_over_space,const Vector<size_t,8> & flexible_tracks_indexes,std::unique_ptr<TrackIndexSet> tracks_to_treat_as_inflexible) const1539 double GridTrackSizingAlgorithm::ComputeFlexFactorUnitSize(
1540 const Vector<GridTrack>& tracks,
1541 double flex_factor_sum,
1542 LayoutUnit& left_over_space,
1543 const Vector<size_t, 8>& flexible_tracks_indexes,
1544 std::unique_ptr<TrackIndexSet> tracks_to_treat_as_inflexible) const {
1545 // We want to avoid the effect of flex factors sum below 1 making the factor
1546 // unit size to grow exponentially.
1547 double hypothetical_factor_unit_size =
1548 left_over_space / std::max<double>(1, flex_factor_sum);
1549
1550 // product of the hypothetical "flex factor unit" and any flexible track's
1551 // "flex factor" must be grater than such track's "base size".
1552 std::unique_ptr<TrackIndexSet> additional_tracks_to_treat_as_inflexible =
1553 std::move(tracks_to_treat_as_inflexible);
1554 bool valid_flex_factor_unit = true;
1555 for (auto index : flexible_tracks_indexes) {
1556 if (additional_tracks_to_treat_as_inflexible &&
1557 additional_tracks_to_treat_as_inflexible->Contains(index))
1558 continue;
1559 LayoutUnit base_size = tracks[index].BaseSize();
1560 double flex_factor =
1561 tracks[index].CachedTrackSize().MaxTrackBreadth().Flex();
1562 // treating all such tracks as inflexible.
1563 if (base_size > hypothetical_factor_unit_size * flex_factor) {
1564 left_over_space -= base_size;
1565 flex_factor_sum -= flex_factor;
1566 if (!additional_tracks_to_treat_as_inflexible) {
1567 additional_tracks_to_treat_as_inflexible =
1568 std::make_unique<TrackIndexSet>();
1569 }
1570 additional_tracks_to_treat_as_inflexible->insert(index);
1571 valid_flex_factor_unit = false;
1572 }
1573 }
1574 if (!valid_flex_factor_unit) {
1575 return ComputeFlexFactorUnitSize(
1576 tracks, flex_factor_sum, left_over_space, flexible_tracks_indexes,
1577 std::move(additional_tracks_to_treat_as_inflexible));
1578 }
1579 return hypothetical_factor_unit_size;
1580 }
1581
ComputeFlexSizedTracksGrowth(double flex_fraction,Vector<LayoutUnit> & increments,LayoutUnit & total_growth) const1582 void GridTrackSizingAlgorithm::ComputeFlexSizedTracksGrowth(
1583 double flex_fraction,
1584 Vector<LayoutUnit>& increments,
1585 LayoutUnit& total_growth) const {
1586 size_t num_flex_tracks = flexible_sized_tracks_index_.size();
1587 DCHECK_EQ(increments.size(), num_flex_tracks);
1588 const Vector<GridTrack>& all_tracks = Tracks(direction_);
1589 for (size_t i = 0; i < num_flex_tracks; ++i) {
1590 size_t track_index = flexible_sized_tracks_index_[i];
1591 const GridTrackSize& track_size = all_tracks[track_index].CachedTrackSize();
1592 DCHECK(track_size.MaxTrackBreadth().IsFlex());
1593 LayoutUnit old_base_size = all_tracks[track_index].BaseSize();
1594 LayoutUnit new_base_size = std::max(
1595 old_base_size,
1596 LayoutUnit(flex_fraction * track_size.MaxTrackBreadth().Flex()));
1597 increments[i] = new_base_size - old_base_size;
1598 total_growth += increments[i];
1599 }
1600 }
1601
StretchFlexibleTracks(base::Optional<LayoutUnit> free_space)1602 void GridTrackSizingAlgorithm::StretchFlexibleTracks(
1603 base::Optional<LayoutUnit> free_space) {
1604 if (flexible_sized_tracks_index_.IsEmpty())
1605 return;
1606
1607 double flex_fraction = strategy_->FindUsedFlexFraction(
1608 flexible_sized_tracks_index_, direction_, free_space);
1609
1610 LayoutUnit total_growth;
1611 Vector<LayoutUnit> increments;
1612 increments.Grow(flexible_sized_tracks_index_.size());
1613 ComputeFlexSizedTracksGrowth(flex_fraction, increments, total_growth);
1614
1615 if (strategy_->RecomputeUsedFlexFractionIfNeeded(flexible_sized_tracks_index_,
1616 flex_fraction, increments,
1617 total_growth)) {
1618 total_growth = LayoutUnit(0);
1619 ComputeFlexSizedTracksGrowth(flex_fraction, increments, total_growth);
1620 }
1621
1622 size_t i = 0;
1623 Vector<GridTrack>& all_tracks = Tracks(direction_);
1624 for (auto track_index : flexible_sized_tracks_index_) {
1625 auto& track = all_tracks[track_index];
1626 if (LayoutUnit increment = increments[i++])
1627 track.SetBaseSize(track.BaseSize() + increment);
1628 }
1629 if (FreeSpace(direction_)) {
1630 SetFreeSpace(direction_, FreeSpace(direction_).value() - total_growth);
1631 }
1632 max_content_size_ += total_growth;
1633 }
1634
StretchAutoTracks()1635 void GridTrackSizingAlgorithm::StretchAutoTracks() {
1636 LayoutUnit free_space = strategy_->FreeSpaceForStretchAutoTracksStep();
1637 if (auto_sized_tracks_for_stretch_index_.IsEmpty() || (free_space <= 0) ||
1638 (layout_grid_->ContentAlignment(direction_).Distribution() !=
1639 ContentDistributionType::kStretch))
1640 return;
1641
1642 unsigned number_of_auto_sized_tracks =
1643 auto_sized_tracks_for_stretch_index_.size();
1644 LayoutUnit size_to_increase = free_space / number_of_auto_sized_tracks;
1645 Vector<GridTrack>& all_tracks = Tracks(direction_);
1646 for (const auto& track_index : auto_sized_tracks_for_stretch_index_) {
1647 auto& track = all_tracks[track_index];
1648 LayoutUnit base_size = track.BaseSize() + size_to_increase;
1649 track.SetBaseSize(base_size);
1650 }
1651 SetFreeSpace(direction_, LayoutUnit());
1652 }
1653
AdvanceNextState()1654 void GridTrackSizingAlgorithm::AdvanceNextState() {
1655 switch (sizing_state_) {
1656 case kColumnSizingFirstIteration:
1657 sizing_state_ = kRowSizingFirstIteration;
1658 return;
1659 case kRowSizingFirstIteration:
1660 if (!strategy_->IsComputingSizeContainment())
1661 sizing_state_ = kColumnSizingSecondIteration;
1662 return;
1663 case kColumnSizingSecondIteration:
1664 sizing_state_ = kRowSizingSecondIteration;
1665 return;
1666 case kRowSizingSecondIteration:
1667 sizing_state_ = kColumnSizingFirstIteration;
1668 return;
1669 }
1670 NOTREACHED();
1671 sizing_state_ = kColumnSizingFirstIteration;
1672 }
1673
IsValidTransition() const1674 bool GridTrackSizingAlgorithm::IsValidTransition() const {
1675 switch (sizing_state_) {
1676 case kColumnSizingFirstIteration:
1677 case kColumnSizingSecondIteration:
1678 return direction_ == kForColumns;
1679 case kRowSizingFirstIteration:
1680 case kRowSizingSecondIteration:
1681 return direction_ == kForRows;
1682 }
1683 NOTREACHED();
1684 return false;
1685 }
1686
Setup(GridTrackSizingDirection direction,size_t num_tracks,base::Optional<LayoutUnit> available_space)1687 void GridTrackSizingAlgorithm::Setup(
1688 GridTrackSizingDirection direction,
1689 size_t num_tracks,
1690 base::Optional<LayoutUnit> available_space) {
1691 DCHECK(needs_setup_);
1692 direction_ = direction;
1693 SetAvailableSpace(
1694 direction, available_space ? available_space.value().ClampNegativeToZero()
1695 : available_space);
1696
1697 if (available_space)
1698 strategy_ = std::make_unique<DefiniteSizeStrategy>(*this);
1699 else
1700 strategy_ = std::make_unique<IndefiniteSizeStrategy>(*this);
1701
1702 content_sized_tracks_index_.Shrink(0);
1703 flexible_sized_tracks_index_.Shrink(0);
1704 auto_sized_tracks_for_stretch_index_.Shrink(0);
1705 has_percent_sized_rows_indefinite_height_ = false;
1706
1707 if (available_space) {
1708 LayoutUnit gutters_size = layout_grid_->GuttersSize(
1709 grid_, direction, 0, grid_.NumTracks(direction), available_space);
1710 SetFreeSpace(direction, available_space.value() - gutters_size);
1711 } else {
1712 SetFreeSpace(direction, base::nullopt);
1713 }
1714 Tracks(direction).resize(num_tracks);
1715
1716 ComputeBaselineAlignmentContext();
1717
1718 needs_setup_ = false;
1719 }
1720
ComputeBaselineAlignmentContext()1721 void GridTrackSizingAlgorithm::ComputeBaselineAlignmentContext() {
1722 GridAxis axis = GridAxisForDirection(direction_);
1723 baseline_alignment_.Clear(axis);
1724 baseline_alignment_.SetBlockFlow(layout_grid_->StyleRef().GetWritingMode());
1725 BaselineItemsCache& baseline_items_cache = axis == kGridColumnAxis
1726 ? column_baseline_items_map_
1727 : row_baseline_items_map_;
1728 for (auto* child : baseline_items_cache.Keys()) {
1729 // TODO (jfernandez): We may have to get rid of the baseline participation
1730 // flag (hence just using a HashSet) depending on the CSS WG resolution on
1731 // https://github.com/w3c/csswg-drafts/issues/3046
1732 if (CanParticipateInBaselineAlignment(*child, axis)) {
1733 UpdateBaselineAlignmentContext(*child, axis);
1734 baseline_items_cache.Set(child, true);
1735 } else {
1736 baseline_items_cache.Set(child, false);
1737 }
1738 }
1739 }
1740
1741 // Described in https://drafts.csswg.org/css-grid/#algo-track-sizing
Run()1742 void GridTrackSizingAlgorithm::Run() {
1743 DCHECK(WasSetup());
1744 StateMachine state_machine(*this);
1745
1746 // Step 1.
1747 base::Optional<LayoutUnit> initial_free_space = FreeSpace(direction_);
1748 InitializeTrackSizes();
1749
1750 if (strategy_->IsComputingSizeContainment()) {
1751 ComputeGridContainerIntrinsicSizes();
1752 return;
1753 }
1754
1755 // Step 2.
1756 if (!content_sized_tracks_index_.IsEmpty())
1757 ResolveIntrinsicTrackSizes();
1758
1759 // This is not exactly a step of the track sizing algorithm, but we use the
1760 // track sizes computed
1761 // up to this moment (before maximization) to calculate the grid container
1762 // intrinsic sizes.
1763 ComputeGridContainerIntrinsicSizes();
1764
1765 if (FreeSpace(direction_)) {
1766 LayoutUnit updated_free_space =
1767 FreeSpace(direction_).value() - min_content_size_;
1768 SetFreeSpace(direction_, updated_free_space);
1769 if (updated_free_space <= 0)
1770 return;
1771 }
1772
1773 // Step 3.
1774 strategy_->MaximizeTracks(Tracks(direction_), direction_ == kForColumns
1775 ? free_space_columns_
1776 : free_space_rows_);
1777
1778 // Step 4.
1779 StretchFlexibleTracks(initial_free_space);
1780
1781 // Step 5.
1782 StretchAutoTracks();
1783 }
1784
Reset()1785 void GridTrackSizingAlgorithm::Reset() {
1786 DCHECK(WasSetup());
1787 sizing_state_ = kColumnSizingFirstIteration;
1788 columns_.Shrink(0);
1789 rows_.Shrink(0);
1790 content_sized_tracks_index_.Shrink(0);
1791 flexible_sized_tracks_index_.Shrink(0);
1792 auto_sized_tracks_for_stretch_index_.Shrink(0);
1793 has_percent_sized_rows_indefinite_height_ = false;
1794 SetAvailableSpace(kForRows, base::nullopt);
1795 SetAvailableSpace(kForColumns, base::nullopt);
1796 }
1797
1798 #if DCHECK_IS_ON()
TracksAreWiderThanMinTrackBreadth() const1799 bool GridTrackSizingAlgorithm::TracksAreWiderThanMinTrackBreadth() const {
1800 const Vector<GridTrack>& all_tracks = Tracks(direction_);
1801 for (size_t i = 0; i < all_tracks.size(); ++i) {
1802 const GridTrackSize& track_size = all_tracks[i].CachedTrackSize();
1803 if (InitialBaseSize(track_size) > all_tracks[i].BaseSize())
1804 return false;
1805 }
1806 return true;
1807 }
1808 #endif
1809
StateMachine(GridTrackSizingAlgorithm & algorithm)1810 GridTrackSizingAlgorithm::StateMachine::StateMachine(
1811 GridTrackSizingAlgorithm& algorithm)
1812 : algorithm_(algorithm) {
1813 DCHECK(algorithm_.IsValidTransition());
1814 DCHECK(!algorithm_.needs_setup_);
1815 }
1816
~StateMachine()1817 GridTrackSizingAlgorithm::StateMachine::~StateMachine() {
1818 algorithm_.AdvanceNextState();
1819 algorithm_.needs_setup_ = true;
1820 }
1821
1822 } // namespace blink
1823