f75376b390baa37ed29fe4052a7babfee2a4f2a6
[WebKit-https.git] / Source / WebCore / rendering / GridTrackSizingAlgorithm.cpp
1 /*
2  * Copyright (C) 2017 Igalia S.L.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "GridTrackSizingAlgorithm.h"
28
29 #include "Grid.h"
30 #include "GridArea.h"
31 #include "GridLayoutFunctions.h"
32 #include "RenderGrid.h"
33
34 namespace WebCore {
35
36 const LayoutUnit& GridTrack::baseSize() const
37 {
38     ASSERT(isGrowthLimitBiggerThanBaseSize());
39     return m_baseSize;
40 }
41
42 const LayoutUnit& GridTrack::growthLimit() const
43 {
44     ASSERT(isGrowthLimitBiggerThanBaseSize());
45     ASSERT(!m_growthLimitCap || m_growthLimitCap.value() >= m_growthLimit || m_baseSize >= m_growthLimitCap.value());
46     return m_growthLimit;
47 }
48
49 void GridTrack::setBaseSize(LayoutUnit baseSize)
50 {
51     m_baseSize = baseSize;
52     ensureGrowthLimitIsBiggerThanBaseSize();
53 }
54
55 void GridTrack::setGrowthLimit(LayoutUnit growthLimit)
56 {
57     m_growthLimit = growthLimit == infinity ? growthLimit : std::min(growthLimit, m_growthLimitCap.value_or(growthLimit));
58     ensureGrowthLimitIsBiggerThanBaseSize();
59 }
60
61 const LayoutUnit& GridTrack::growthLimitIfNotInfinite() const
62 {
63     ASSERT(isGrowthLimitBiggerThanBaseSize());
64     return m_growthLimit == infinity ? m_baseSize : m_growthLimit;
65 }
66
67 void GridTrack::setTempSize(const LayoutUnit& tempSize)
68 {
69     ASSERT(tempSize >= 0);
70     ASSERT(growthLimitIsInfinite() || growthLimit() >= tempSize);
71     m_tempSize = tempSize;
72 }
73
74 void GridTrack::growTempSize(const LayoutUnit& tempSize)
75 {
76     ASSERT(tempSize >= 0);
77     m_tempSize += tempSize;
78 }
79
80 void GridTrack::setGrowthLimitCap(Optional<LayoutUnit> growthLimitCap)
81 {
82     ASSERT(!growthLimitCap || growthLimitCap.value() >= 0);
83     m_growthLimitCap = growthLimitCap;
84 }
85
86 void GridTrack::ensureGrowthLimitIsBiggerThanBaseSize()
87 {
88     if (m_growthLimit != infinity && m_growthLimit < m_baseSize)
89         m_growthLimit = m_baseSize;
90 }
91
92 // Static helper methods.
93
94 static GridAxis gridAxisForDirection(GridTrackSizingDirection direction)
95 {
96     return direction == ForColumns ? GridRowAxis : GridColumnAxis;
97 }
98
99 static GridTrackSizingDirection gridDirectionForAxis(GridAxis axis)
100 {
101     return axis == GridRowAxis ? ForColumns : ForRows;
102 }
103
104 static bool shouldClearOverrideContainingBlockContentSizeForChild(const RenderBox& child, GridTrackSizingDirection direction)
105 {
106     if (direction == ForColumns)
107         return child.hasRelativeLogicalWidth() || child.style().logicalWidth().isIntrinsicOrAuto();
108     return child.hasRelativeLogicalHeight() || child.style().logicalHeight().isIntrinsicOrAuto();
109 }
110
111 static void setOverrideContainingBlockContentSizeForChild(RenderBox& child, GridTrackSizingDirection direction, Optional<LayoutUnit> size)
112 {
113     if (direction == ForColumns)
114         child.setOverrideContainingBlockContentLogicalWidth(size);
115     else
116         child.setOverrideContainingBlockContentLogicalHeight(size);
117 }
118
119 // FIXME: we borrowed this from RenderBlock. We cannot call it from here because it's protected for RenderObjects.
120 static LayoutUnit marginIntrinsicLogicalWidthForChild(const RenderGrid* renderGrid, RenderBox& child)
121 {
122     // A margin has three types: fixed, percentage, and auto (variable).
123     // Auto and percentage margins become 0 when computing min/max width.
124     // Fixed margins can be added in as is.
125     Length marginLeft = child.style().marginStartUsing(&renderGrid->style());
126     Length marginRight = child.style().marginEndUsing(&renderGrid->style());
127     LayoutUnit margin;
128     if (marginLeft.isFixed())
129         margin += marginLeft.value();
130     if (marginRight.isFixed())
131         margin += marginRight.value();
132     return margin;
133 }
134
135 // GridTrackSizingAlgorithm private.
136
137 void GridTrackSizingAlgorithm::setFreeSpace(GridTrackSizingDirection direction, Optional<LayoutUnit> freeSpace)
138 {
139     if (direction == ForColumns)
140         m_freeSpaceColumns = freeSpace;
141     else
142         m_freeSpaceRows = freeSpace;
143 }
144
145 Optional<LayoutUnit> GridTrackSizingAlgorithm::availableSpace() const
146 {
147     ASSERT(wasSetup());
148     return availableSpace(m_direction);
149 }
150
151 void GridTrackSizingAlgorithm::setAvailableSpace(GridTrackSizingDirection direction, Optional<LayoutUnit> availableSpace)
152 {
153     if (direction == ForColumns)
154         m_availableSpaceColumns = availableSpace;
155     else
156         m_availableSpaceRows = availableSpace;
157 }
158
159 const GridTrackSize& GridTrackSizingAlgorithm::rawGridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex) const
160 {
161     bool isRowAxis = direction == ForColumns;
162     auto& renderStyle = m_renderGrid->style();
163     auto& trackStyles = isRowAxis ? renderStyle.gridColumns() : renderStyle.gridRows();
164     auto& autoRepeatTrackStyles = isRowAxis ? renderStyle.gridAutoRepeatColumns() : renderStyle.gridAutoRepeatRows();
165     auto& autoTrackStyles = isRowAxis ? renderStyle.gridAutoColumns() : renderStyle.gridAutoRows();
166     unsigned insertionPoint = isRowAxis ? renderStyle.gridAutoRepeatColumnsInsertionPoint() : renderStyle.gridAutoRepeatRowsInsertionPoint();
167     unsigned autoRepeatTracksCount = m_grid.autoRepeatTracks(direction);
168
169     // We should not use GridPositionsResolver::explicitGridXXXCount() for this because the
170     // explicit grid might be larger than the number of tracks in grid-template-rows|columns (if
171     // grid-template-areas is specified for example).
172     unsigned explicitTracksCount = trackStyles.size() + autoRepeatTracksCount;
173
174     int untranslatedIndexAsInt = translatedIndex + m_grid.smallestTrackStart(direction);
175     unsigned autoTrackStylesSize = autoTrackStyles.size();
176     if (untranslatedIndexAsInt < 0) {
177         int index = untranslatedIndexAsInt % static_cast<int>(autoTrackStylesSize);
178         // We need to traspose the index because the first negative implicit line will get the last defined auto track and so on.
179         index += index ? autoTrackStylesSize : 0;
180         ASSERT(index >= 0);
181         return autoTrackStyles[index];
182     }
183
184     unsigned untranslatedIndex = static_cast<unsigned>(untranslatedIndexAsInt);
185     if (untranslatedIndex >= explicitTracksCount)
186         return autoTrackStyles[(untranslatedIndex - explicitTracksCount) % autoTrackStylesSize];
187
188     if (!autoRepeatTracksCount || untranslatedIndex < insertionPoint)
189         return trackStyles[untranslatedIndex];
190
191     if (untranslatedIndex < (insertionPoint + autoRepeatTracksCount)) {
192         unsigned autoRepeatLocalIndex = untranslatedIndexAsInt - insertionPoint;
193         return autoRepeatTrackStyles[autoRepeatLocalIndex % autoRepeatTrackStyles.size()];
194     }
195
196     return trackStyles[untranslatedIndex - autoRepeatTracksCount];
197 }
198
199 LayoutUnit GridTrackSizingAlgorithm::computeTrackBasedSize() const
200 {
201     LayoutUnit size;
202     auto& allTracks = tracks(m_direction);
203     for (auto& track : allTracks)
204         size += track.baseSize();
205
206     size += m_renderGrid->guttersSize(m_grid, m_direction, 0, allTracks.size(), availableSpace());
207
208     return size;
209 }
210
211 LayoutUnit GridTrackSizingAlgorithm::initialBaseSize(const GridTrackSize& trackSize) const
212 {
213     const GridLength& gridLength = trackSize.minTrackBreadth();
214     if (gridLength.isFlex())
215         return 0;
216
217     const Length& trackLength = gridLength.length();
218     if (trackLength.isSpecified())
219         return valueForLength(trackLength, std::max<LayoutUnit>(availableSpace().value_or(0), 0));
220
221     ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
222     return 0;
223 }
224
225 LayoutUnit GridTrackSizingAlgorithm::initialGrowthLimit(const GridTrackSize& trackSize, LayoutUnit baseSize) const
226 {
227     const GridLength& gridLength = trackSize.maxTrackBreadth();
228     if (gridLength.isFlex())
229         return baseSize;
230
231     const Length& trackLength = gridLength.length();
232     if (trackLength.isSpecified())
233         return valueForLength(trackLength, std::max<LayoutUnit>(availableSpace().value_or(0), 0));
234
235     ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
236     return infinity;
237 }
238
239 void GridTrackSizingAlgorithm::sizeTrackToFitNonSpanningItem(const GridSpan& span, RenderBox& gridItem, GridTrack& track)
240 {
241     unsigned trackPosition = span.startLine();
242     GridTrackSize trackSize = gridTrackSize(m_direction, trackPosition);
243
244     if (trackSize.hasMinContentMinTrackBreadth()) {
245         track.setBaseSize(std::max(track.baseSize(), m_strategy->minContentForChild(gridItem)));
246     } else if (trackSize.hasMaxContentMinTrackBreadth()) {
247         track.setBaseSize(std::max(track.baseSize(), m_strategy->maxContentForChild(gridItem)));
248     } else if (trackSize.hasAutoMinTrackBreadth()) {
249         track.setBaseSize(std::max(track.baseSize(), m_strategy->minSizeForChild(gridItem)));
250     }
251
252     if (trackSize.hasMinContentMaxTrackBreadth()) {
253         track.setGrowthLimit(std::max(track.growthLimit(), m_strategy->minContentForChild(gridItem)));
254     } else if (trackSize.hasMaxContentOrAutoMaxTrackBreadth()) {
255         LayoutUnit growthLimit = m_strategy->maxContentForChild(gridItem);
256         if (trackSize.isFitContent())
257             growthLimit = std::min(growthLimit, valueForLength(trackSize.fitContentTrackBreadth().length(), availableSpace().value_or(0)));
258         track.setGrowthLimit(std::max(track.growthLimit(), growthLimit));
259     }
260 }
261
262 bool GridTrackSizingAlgorithm::spanningItemCrossesFlexibleSizedTracks(const GridSpan& itemSpan) const
263 {
264     for (auto trackPosition : itemSpan) {
265         const GridTrackSize& trackSize = gridTrackSize(m_direction, trackPosition);
266         if (trackSize.minTrackBreadth().isFlex() || trackSize.maxTrackBreadth().isFlex())
267             return true;
268     }
269
270     return false;
271 }
272
273 class GridItemWithSpan {
274 public:
275     GridItemWithSpan(RenderBox& gridItem, GridSpan span)
276         : m_gridItem(gridItem)
277         , m_span(span)
278     {
279     }
280
281     RenderBox& gridItem() const { return m_gridItem; }
282     GridSpan span() const { return m_span; }
283
284     bool operator<(const GridItemWithSpan other) const { return m_span.integerSpan() < other.m_span.integerSpan(); }
285
286 private:
287     std::reference_wrapper<RenderBox> m_gridItem;
288     GridSpan m_span;
289 };
290
291 struct GridItemsSpanGroupRange {
292     Vector<GridItemWithSpan>::iterator rangeStart;
293     Vector<GridItemWithSpan>::iterator rangeEnd;
294 };
295
296 enum TrackSizeRestriction {
297     AllowInfinity,
298     ForbidInfinity,
299 };
300
301 LayoutUnit GridTrackSizingAlgorithm::itemSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, RenderBox& gridItem) const
302 {
303     switch (phase) {
304     case ResolveIntrinsicMinimums:
305     case ResolveIntrinsicMaximums:
306         return m_strategy->minSizeForChild(gridItem);
307     case ResolveContentBasedMinimums:
308         return m_strategy->minContentForChild(gridItem);
309     case ResolveMaxContentMinimums:
310     case ResolveMaxContentMaximums:
311         return m_strategy->maxContentForChild(gridItem);
312     case MaximizeTracks:
313         ASSERT_NOT_REACHED();
314         return 0;
315     }
316
317     ASSERT_NOT_REACHED();
318     return 0;
319 }
320
321 static bool shouldProcessTrackForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
322 {
323     switch (phase) {
324     case ResolveIntrinsicMinimums:
325         return trackSize.hasIntrinsicMinTrackBreadth();
326     case ResolveContentBasedMinimums:
327         return trackSize.hasMinOrMaxContentMinTrackBreadth();
328     case ResolveMaxContentMinimums:
329         return trackSize.hasMaxContentMinTrackBreadth();
330     case ResolveIntrinsicMaximums:
331         return trackSize.hasIntrinsicMaxTrackBreadth();
332     case ResolveMaxContentMaximums:
333         return trackSize.hasMaxContentOrAutoMaxTrackBreadth();
334     case MaximizeTracks:
335         ASSERT_NOT_REACHED();
336         return false;
337     }
338
339     ASSERT_NOT_REACHED();
340     return false;
341 }
342
343 static LayoutUnit trackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track, TrackSizeRestriction restriction)
344 {
345     switch (phase) {
346     case ResolveIntrinsicMinimums:
347     case ResolveContentBasedMinimums:
348     case ResolveMaxContentMinimums:
349     case MaximizeTracks:
350         return track.baseSize();
351     case ResolveIntrinsicMaximums:
352     case ResolveMaxContentMaximums:
353         return restriction == AllowInfinity ? track.growthLimit() : track.growthLimitIfNotInfinite();
354     }
355
356     ASSERT_NOT_REACHED();
357     return track.baseSize();
358 }
359
360 static void updateTrackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
361 {
362     switch (phase) {
363     case ResolveIntrinsicMinimums:
364     case ResolveContentBasedMinimums:
365     case ResolveMaxContentMinimums:
366         track.setBaseSize(track.plannedSize());
367         return;
368     case ResolveIntrinsicMaximums:
369     case ResolveMaxContentMaximums:
370         track.setGrowthLimit(track.plannedSize());
371         return;
372     case MaximizeTracks:
373         ASSERT_NOT_REACHED();
374         return;
375     }
376
377     ASSERT_NOT_REACHED();
378 }
379
380 static bool trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
381 {
382     switch (phase) {
383     case ResolveIntrinsicMinimums:
384     case ResolveContentBasedMinimums:
385         return trackSize.hasAutoOrMinContentMinTrackBreadthAndIntrinsicMaxTrackBreadth();
386     case ResolveMaxContentMinimums:
387         return trackSize.hasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth();
388     case ResolveIntrinsicMaximums:
389     case ResolveMaxContentMaximums:
390         return true;
391     case MaximizeTracks:
392         ASSERT_NOT_REACHED();
393         return false;
394     }
395
396     ASSERT_NOT_REACHED();
397     return false;
398 }
399
400 static void markAsInfinitelyGrowableForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
401 {
402     switch (phase) {
403     case ResolveIntrinsicMinimums:
404     case ResolveContentBasedMinimums:
405     case ResolveMaxContentMinimums:
406         return;
407     case ResolveIntrinsicMaximums:
408         if (trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity) == infinity  && track.plannedSize() != infinity)
409             track.setInfinitelyGrowable(true);
410         return;
411     case ResolveMaxContentMaximums:
412         if (track.infinitelyGrowable())
413             track.setInfinitelyGrowable(false);
414         return;
415     case MaximizeTracks:
416         ASSERT_NOT_REACHED();
417         return;
418     }
419
420     ASSERT_NOT_REACHED();
421 }
422
423 template <TrackSizeComputationPhase phase>
424 void GridTrackSizingAlgorithm::increaseSizesToAccommodateSpanningItems(const GridItemsSpanGroupRange& gridItemsWithSpan)
425 {
426     Vector<GridTrack>& allTracks = tracks(m_direction);
427     for (const auto& trackIndex : m_contentSizedTracksIndex) {
428         GridTrack& track = allTracks[trackIndex];
429         track.setPlannedSize(trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity));
430     }
431
432     Vector<GridTrack*> growBeyondGrowthLimitsTracks;
433     Vector<GridTrack*> filteredTracks;
434     for (auto it = gridItemsWithSpan.rangeStart; it != gridItemsWithSpan.rangeEnd; ++it) {
435         GridItemWithSpan& gridItemWithSpan = *it;
436         ASSERT(gridItemWithSpan.span().integerSpan() > 1);
437         const GridSpan& itemSpan = gridItemWithSpan.span();
438
439         filteredTracks.shrink(0);
440         growBeyondGrowthLimitsTracks.shrink(0);
441         LayoutUnit spanningTracksSize;
442         for (auto trackPosition : itemSpan) {
443             const GridTrackSize& trackSize = gridTrackSize(m_direction, trackPosition);
444             GridTrack& track = tracks(m_direction)[trackPosition];
445             spanningTracksSize += trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
446             if (!shouldProcessTrackForTrackSizeComputationPhase(phase, trackSize))
447                 continue;
448
449             filteredTracks.append(&track);
450
451             if (trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(phase, trackSize))
452                 growBeyondGrowthLimitsTracks.append(&track);
453         }
454
455         if (filteredTracks.isEmpty())
456             continue;
457
458         spanningTracksSize += m_renderGrid->guttersSize(m_grid, m_direction, itemSpan.startLine(), itemSpan.integerSpan(), availableSpace());
459
460         LayoutUnit extraSpace = itemSizeForTrackSizeComputationPhase(phase, gridItemWithSpan.gridItem()) - spanningTracksSize;
461         extraSpace = std::max<LayoutUnit>(extraSpace, 0);
462         auto& tracksToGrowBeyondGrowthLimits = growBeyondGrowthLimitsTracks.isEmpty() ? filteredTracks : growBeyondGrowthLimitsTracks;
463         distributeSpaceToTracks<phase>(filteredTracks, &tracksToGrowBeyondGrowthLimits, extraSpace);
464     }
465
466     for (const auto& trackIndex : m_contentSizedTracksIndex) {
467         GridTrack& track = allTracks[trackIndex];
468         markAsInfinitelyGrowableForTrackSizeComputationPhase(phase, track);
469         updateTrackSizeForTrackSizeComputationPhase(phase, track);
470     }
471 }
472
473 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
474 {
475     // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
476     // (forall x: NOT x < x).
477     bool track1HasInfiniteGrowthPotentialWithoutCap = track1->infiniteGrowthPotential() && !track1->growthLimitCap();
478     bool track2HasInfiniteGrowthPotentialWithoutCap = track2->infiniteGrowthPotential() && !track2->growthLimitCap();
479
480     if (track1HasInfiniteGrowthPotentialWithoutCap && track2HasInfiniteGrowthPotentialWithoutCap)
481         return false;
482
483     if (track1HasInfiniteGrowthPotentialWithoutCap || track2HasInfiniteGrowthPotentialWithoutCap)
484         return track2HasInfiniteGrowthPotentialWithoutCap;
485
486     LayoutUnit track1Limit = track1->growthLimitCap().value_or(track1->growthLimit());
487     LayoutUnit track2Limit = track2->growthLimitCap().value_or(track2->growthLimit());
488     return (track1Limit - track1->baseSize()) < (track2Limit - track2->baseSize());
489 }
490
491 static void clampGrowthShareIfNeeded(TrackSizeComputationPhase phase, const GridTrack& track, LayoutUnit& growthShare)
492 {
493     if (phase != ResolveMaxContentMaximums || !track.growthLimitCap())
494         return;
495
496     LayoutUnit distanceToCap = track.growthLimitCap().value() - track.tempSize();
497     if (distanceToCap <= 0)
498         return;
499
500     growthShare = std::min(growthShare, distanceToCap);
501 }
502
503 template <TrackSizeComputationPhase phase>
504 void GridTrackSizingAlgorithm::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* growBeyondGrowthLimitsTracks, LayoutUnit& freeSpace) const
505 {
506     ASSERT(freeSpace >= 0);
507
508     for (auto* track : tracks)
509         track->setTempSize(trackSizeForTrackSizeComputationPhase(phase, *track, ForbidInfinity));
510
511     if (freeSpace > 0) {
512         std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
513
514         unsigned tracksSize = tracks.size();
515         for (unsigned i = 0; i < tracksSize; ++i) {
516             GridTrack& track = *tracks[i];
517             const LayoutUnit& trackBreadth = trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
518             bool infiniteGrowthPotential = track.infiniteGrowthPotential();
519             LayoutUnit trackGrowthPotential = infiniteGrowthPotential ? track.growthLimit() : track.growthLimit() - trackBreadth;
520             // Let's avoid computing availableLogicalSpaceShare as much as possible as it's a hot spot in performance tests.
521             if (trackGrowthPotential > 0 || infiniteGrowthPotential) {
522                 LayoutUnit availableLogicalSpaceShare = freeSpace / (tracksSize - i);
523                 LayoutUnit growthShare = infiniteGrowthPotential ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, trackGrowthPotential);
524                 clampGrowthShareIfNeeded(phase, track, growthShare);
525                 ASSERT_WITH_MESSAGE(growthShare >= 0, "We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function. We can still have 0 as growthShare if the amount of tracks greatly exceeds the freeSpace.");
526                 track.growTempSize(growthShare);
527                 freeSpace -= growthShare;
528             }
529         }
530     }
531
532     if (freeSpace > 0 && growBeyondGrowthLimitsTracks) {
533         // We need to sort them because there might be tracks with growth limit caps (like the ones
534         // with fit-content()) which cannot indefinitely grow over the limits.
535         if (phase == ResolveMaxContentMaximums)
536             std::sort(growBeyondGrowthLimitsTracks->begin(), growBeyondGrowthLimitsTracks->end(), sortByGridTrackGrowthPotential);
537
538         unsigned tracksGrowingBeyondGrowthLimitsSize = growBeyondGrowthLimitsTracks->size();
539         for (unsigned i = 0; i < tracksGrowingBeyondGrowthLimitsSize; ++i) {
540             GridTrack* track = growBeyondGrowthLimitsTracks->at(i);
541             LayoutUnit growthShare = freeSpace / (tracksGrowingBeyondGrowthLimitsSize - i);
542             clampGrowthShareIfNeeded(phase, *track, growthShare);
543             track->growTempSize(growthShare);
544             freeSpace -= growthShare;
545         }
546     }
547
548     for (auto* track : tracks)
549         track->setPlannedSize(track->plannedSize() == infinity ? track->tempSize() : std::max(track->plannedSize(), track->tempSize()));
550 }
551
552 LayoutSize GridTrackSizingAlgorithm::estimatedGridAreaBreadthForChild(const RenderBox& child) const
553 {
554     return {estimatedGridAreaBreadthForChild(child, ForColumns), estimatedGridAreaBreadthForChild(child, ForRows)};
555 }
556
557 LayoutUnit GridTrackSizingAlgorithm::estimatedGridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction) const
558 {
559     const GridSpan& span = m_grid.gridItemSpan(child, direction);
560     LayoutUnit gridAreaSize;
561     bool gridAreaIsIndefinite = false;
562     Optional<LayoutUnit> availableSize = availableSpace(direction);
563     for (auto trackPosition : span) {
564         // We may need to estimate the grid area size before running the track
565         // sizing algorithm in order to perform the pre-layout of orthogonal
566         // items.
567         GridTrackSize trackSize = wasSetup() ? gridTrackSize(direction, trackPosition) : rawGridTrackSize(direction, trackPosition);
568         GridLength maxTrackSize = trackSize.maxTrackBreadth();
569         if (maxTrackSize.isContentSized() || maxTrackSize.isFlex() || isRelativeGridLengthAsAuto(maxTrackSize, direction))
570             gridAreaIsIndefinite = true;
571         else
572             gridAreaSize += valueForLength(maxTrackSize.length(), availableSize.value_or(0_lu));
573     }
574
575     gridAreaSize += m_renderGrid->guttersSize(m_grid, direction, span.startLine(), span.integerSpan(), availableSize);
576
577     GridTrackSizingDirection childInlineDirection = GridLayoutFunctions::flowAwareDirectionForChild(*m_renderGrid, child, ForColumns);
578     if (gridAreaIsIndefinite)
579         return direction == childInlineDirection ? std::max(child.maxPreferredLogicalWidth(), gridAreaSize) : -1_lu;
580     return gridAreaSize;
581 }
582
583 LayoutUnit GridTrackSizingAlgorithm::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction) const
584 {
585     bool addContentAlignmentOffset =
586         direction == ForColumns && m_sizingState == RowSizingFirstIteration;
587     // To determine the column track's size based on an orthogonal grid item we need it's logical
588     // height, which may depend on the row track's size. It's possible that the row tracks sizing
589     // logic has not been performed yet, so we will need to do an estimation.
590     if (direction == ForRows && (m_sizingState == ColumnSizingFirstIteration || m_sizingState == ColumnSizingSecondIteration)) {
591         ASSERT(GridLayoutFunctions::isOrthogonalChild(*m_renderGrid, child));
592         // FIXME (jfernandez) Content Alignment should account for this heuristic.
593         // https://github.com/w3c/csswg-drafts/issues/2697
594         if (m_sizingState == ColumnSizingFirstIteration)
595             return estimatedGridAreaBreadthForChild(child, ForRows);
596         addContentAlignmentOffset = true;
597     }
598
599     const Vector<GridTrack>& allTracks = tracks(direction);
600     const GridSpan& span = m_grid.gridItemSpan(child, direction);
601     LayoutUnit gridAreaBreadth;
602     for (auto trackPosition : span)
603         gridAreaBreadth += allTracks[trackPosition].baseSize();
604
605     if (addContentAlignmentOffset)
606         gridAreaBreadth += (span.integerSpan() - 1) * m_renderGrid->gridItemOffset(direction);
607
608     gridAreaBreadth += m_renderGrid->guttersSize(m_grid, direction, span.startLine(), span.integerSpan(), availableSpace(direction));
609
610     return gridAreaBreadth;
611 }
612
613 bool GridTrackSizingAlgorithm::isRelativeGridLengthAsAuto(const GridLength& length, GridTrackSizingDirection direction) const
614 {
615     return length.isPercentage() && !availableSpace(direction);
616 }
617
618 bool GridTrackSizingAlgorithm::isIntrinsicSizedGridArea(const RenderBox& child, GridAxis axis) const
619 {
620     ASSERT(wasSetup());
621     GridTrackSizingDirection direction = gridDirectionForAxis(axis);
622     const GridSpan& span = m_grid.gridItemSpan(child, direction);
623     for (auto trackPosition : span) {
624         GridTrackSize trackSize = rawGridTrackSize(direction, trackPosition);
625         // We consider fr units as 'auto' for the min sizing function.
626         // FIXME(jfernandez): https://github.com/w3c/csswg-drafts/issues/2611
627         //
628         // The use of AvailableSize function may imply different results
629         // for the same item when assuming indefinite or definite size
630         // constraints depending on the phase we evaluate the item's
631         // baseline participation.
632         // FIXME(jfernandez): https://github.com/w3c/csswg-drafts/issues/3046
633         if (trackSize.isContentSized() || trackSize.isFitContent() || trackSize.minTrackBreadth().isFlex() || (trackSize.maxTrackBreadth().isFlex() && !availableSpace(direction)))
634             return true;
635     }
636     return false;
637 }
638
639 GridTrackSize GridTrackSizingAlgorithm::gridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex) const
640 {
641     ASSERT(wasSetup());
642     // Collapse empty auto repeat tracks if auto-fit.
643     if (m_grid.hasAutoRepeatEmptyTracks(direction) && m_grid.isEmptyAutoRepeatTrack(direction, translatedIndex))
644         return { Length(Fixed), LengthTrackSizing };
645
646     auto& trackSize = rawGridTrackSize(direction, translatedIndex);
647     if (trackSize.isFitContent())
648         return trackSize;
649
650     GridLength minTrackBreadth = trackSize.minTrackBreadth();
651     GridLength maxTrackBreadth = trackSize.maxTrackBreadth();
652     // If the logical width/height of the grid container is indefinite, percentage
653     // values are treated as <auto>.
654     if (isRelativeGridLengthAsAuto(trackSize.minTrackBreadth(), direction))
655         minTrackBreadth = Length(Auto);
656     if (isRelativeGridLengthAsAuto(trackSize.maxTrackBreadth(), direction))
657         maxTrackBreadth = Length(Auto);
658
659     // Flex sizes are invalid as a min sizing function. However we still can have a flexible |minTrackBreadth|
660     // if the track size is just a flex size (e.g. "1fr"), the spec says that in this case it implies an automatic minimum.
661     if (minTrackBreadth.isFlex())
662         minTrackBreadth = Length(Auto);
663
664     return GridTrackSize(minTrackBreadth, maxTrackBreadth);
665 }
666
667 double GridTrackSizingAlgorithm::computeFlexFactorUnitSize(const Vector<GridTrack>& tracks, double flexFactorSum, LayoutUnit& leftOverSpace, const Vector<unsigned, 8>& flexibleTracksIndexes, std::unique_ptr<TrackIndexSet> tracksToTreatAsInflexible) const
668 {
669     // We want to avoid the effect of flex factors sum below 1 making the factor unit size to grow exponentially.
670     double hypotheticalFactorUnitSize = leftOverSpace / std::max<double>(1, flexFactorSum);
671
672     // product of the hypothetical "flex factor unit" and any flexible track's "flex factor" must be grater than such track's "base size".
673     bool validFlexFactorUnit = true;
674     for (auto index : flexibleTracksIndexes) {
675         if (tracksToTreatAsInflexible && tracksToTreatAsInflexible->contains(index))
676             continue;
677         LayoutUnit baseSize = tracks[index].baseSize();
678         double flexFactor = gridTrackSize(m_direction, index).maxTrackBreadth().flex();
679         // treating all such tracks as inflexible.
680         if (baseSize > hypotheticalFactorUnitSize * flexFactor) {
681             leftOverSpace -= baseSize;
682             flexFactorSum -= flexFactor;
683             if (!tracksToTreatAsInflexible)
684                 tracksToTreatAsInflexible = std::make_unique<TrackIndexSet>();
685             tracksToTreatAsInflexible->add(index);
686             validFlexFactorUnit = false;
687         }
688     }
689     if (!validFlexFactorUnit)
690         return computeFlexFactorUnitSize(tracks, flexFactorSum, leftOverSpace, flexibleTracksIndexes, WTFMove(tracksToTreatAsInflexible));
691     return hypotheticalFactorUnitSize;
692 }
693
694 void GridTrackSizingAlgorithm::computeFlexSizedTracksGrowth(double flexFraction, Vector<LayoutUnit>& increments, LayoutUnit& totalGrowth) const
695 {
696     size_t numFlexTracks = m_flexibleSizedTracksIndex.size();
697     ASSERT(increments.size() == numFlexTracks);
698     const Vector<GridTrack>& allTracks = tracks(m_direction);
699     for (size_t i = 0; i < numFlexTracks; ++i) {
700         unsigned trackIndex = m_flexibleSizedTracksIndex[i];
701         auto trackSize = gridTrackSize(m_direction, trackIndex);
702         ASSERT(trackSize.maxTrackBreadth().isFlex());
703         LayoutUnit oldBaseSize = allTracks[trackIndex].baseSize();
704         LayoutUnit newBaseSize = std::max(oldBaseSize, LayoutUnit(flexFraction * trackSize.maxTrackBreadth().flex()));
705         increments[i] = newBaseSize - oldBaseSize;
706         totalGrowth += increments[i];
707     }
708 }
709
710 double GridTrackSizingAlgorithm::findFrUnitSize(const GridSpan& tracksSpan, LayoutUnit leftOverSpace) const
711 {
712     if (leftOverSpace <= 0)
713         return 0;
714
715     const Vector<GridTrack>& allTracks = tracks(m_direction);
716     double flexFactorSum = 0;
717     Vector<unsigned, 8> flexibleTracksIndexes;
718     for (auto trackIndex : tracksSpan) {
719         GridTrackSize trackSize = gridTrackSize(m_direction, trackIndex);
720         if (!trackSize.maxTrackBreadth().isFlex())
721             leftOverSpace -= allTracks[trackIndex].baseSize();
722         else {
723             double flexFactor = trackSize.maxTrackBreadth().flex();
724             flexibleTracksIndexes.append(trackIndex);
725             flexFactorSum += flexFactor;
726         }
727     }
728     // We don't remove the gutters from left_over_space here, because that was already done before.
729
730     // The function is not called if we don't have <flex> grid tracks.
731     ASSERT(!flexibleTracksIndexes.isEmpty());
732
733     return computeFlexFactorUnitSize(allTracks, flexFactorSum, leftOverSpace, flexibleTracksIndexes);
734 }
735
736 void GridTrackSizingAlgorithm::computeGridContainerIntrinsicSizes()
737 {
738     m_minContentSize = m_maxContentSize = 0_lu;
739
740     Vector<GridTrack>& allTracks = tracks(m_direction);
741     for (auto& track : allTracks) {
742         ASSERT(!track.infiniteGrowthPotential());
743         m_minContentSize += track.baseSize();
744         m_maxContentSize += track.growthLimit();
745         // The growth limit caps must be cleared now in order to properly sort
746         // tracks by growth potential on an eventual "Maximize Tracks".
747         track.setGrowthLimitCap(WTF::nullopt);
748     }
749 }
750
751 // GridTrackSizingAlgorithmStrategy.
752 LayoutUnit GridTrackSizingAlgorithmStrategy::logicalHeightForChild(RenderBox& child) const
753 {
754     GridTrackSizingDirection childBlockDirection = GridLayoutFunctions::flowAwareDirectionForChild(*renderGrid(), child, ForRows);
755     // If |child| has a relative logical height, we shouldn't let it override its intrinsic height, which is
756     // what we are interested in here. Thus we need to set the block-axis override size to -1 (no possible resolution).
757     if (shouldClearOverrideContainingBlockContentSizeForChild(child, ForRows)) {
758         setOverrideContainingBlockContentSizeForChild(child, childBlockDirection, WTF::nullopt);
759         child.setNeedsLayout(MarkOnlyThis);
760     }
761
762     // We need to clear the stretched height to properly compute logical height during layout.
763     if (child.needsLayout())
764         child.clearOverrideContentLogicalHeight();
765
766     child.layoutIfNeeded();
767     return child.logicalHeight() + GridLayoutFunctions::marginLogicalSizeForChild(*renderGrid(), childBlockDirection, child) + m_algorithm.baselineOffsetForChild(child, gridAxisForDirection(direction()));
768 }
769
770 LayoutUnit GridTrackSizingAlgorithmStrategy::minContentForChild(RenderBox& child) const
771 {
772     GridTrackSizingDirection childInlineDirection = GridLayoutFunctions::flowAwareDirectionForChild(*renderGrid(), child, ForColumns);
773     if (direction() == childInlineDirection) {
774         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
775         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
776         return child.minPreferredLogicalWidth() + GridLayoutFunctions::marginLogicalSizeForChild(*renderGrid(), childInlineDirection, child) + m_algorithm.baselineOffsetForChild(child, gridAxisForDirection(direction()));
777     }
778
779     if (updateOverrideContainingBlockContentSizeForChild(child, childInlineDirection))
780         child.setNeedsLayout(MarkOnlyThis);
781     return logicalHeightForChild(child);
782 }
783
784 LayoutUnit GridTrackSizingAlgorithmStrategy::maxContentForChild(RenderBox& child) const
785 {
786     GridTrackSizingDirection childInlineDirection = GridLayoutFunctions::flowAwareDirectionForChild(*renderGrid(), child, ForColumns);
787     if (direction() == childInlineDirection) {
788         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
789         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
790         return child.maxPreferredLogicalWidth() + GridLayoutFunctions::marginLogicalSizeForChild(*renderGrid(), childInlineDirection, child) + m_algorithm.baselineOffsetForChild(child, gridAxisForDirection(direction()));
791     }
792
793     if (updateOverrideContainingBlockContentSizeForChild(child, childInlineDirection))
794         child.setNeedsLayout(MarkOnlyThis);
795     return logicalHeightForChild(child);
796 }
797
798 LayoutUnit GridTrackSizingAlgorithmStrategy::minSizeForChild(RenderBox& child) const
799 {
800     GridTrackSizingDirection childInlineDirection = GridLayoutFunctions::flowAwareDirectionForChild(*renderGrid(), child, ForColumns);
801     bool isRowAxis = direction() == childInlineDirection;
802     const Length& childMinSize = isRowAxis ? child.style().logicalMinWidth() : child.style().logicalMinHeight();
803     const Length& childSize = isRowAxis ? child.style().logicalWidth() : child.style().logicalHeight();
804
805     bool overflowIsVisible = isRowAxis ? child.style().overflowInlineDirection() == Overflow::Visible : child.style().overflowBlockDirection() == Overflow::Visible;
806     if (childSize.isAuto() && childMinSize.isAuto() && overflowIsVisible) {
807         auto minSize = minContentForChild(child);
808         LayoutUnit maxBreadth;
809         for (auto trackPosition : m_algorithm.grid().gridItemSpan(child, direction())) {
810             GridTrackSize trackSize = m_algorithm.gridTrackSize(direction(), trackPosition);
811             if (!trackSize.hasFixedMaxTrackBreadth())
812                 return minSize;
813             maxBreadth += valueForLength(trackSize.maxTrackBreadth().length(), availableSpace().value_or(0_lu));
814         }
815         if (minSize > maxBreadth) {
816             auto marginAndBorderAndPadding = GridLayoutFunctions::marginLogicalSizeForChild(*renderGrid(), direction(), child);
817             marginAndBorderAndPadding += isRowAxis ? child.borderAndPaddingLogicalWidth() : child.borderAndPaddingLogicalHeight();
818             minSize = std::max(maxBreadth, marginAndBorderAndPadding);
819         }
820         return minSize;
821     }
822
823     if (!childSize.isAuto())
824         return minContentForChild(child);
825
826     LayoutUnit baselineShim = m_algorithm.baselineOffsetForChild(child, gridAxisForDirection(direction()));
827     LayoutUnit gridAreaSize = m_algorithm.gridAreaBreadthForChild(child, childInlineDirection);
828     if (isRowAxis)
829         return minLogicalWidthForChild(child, childMinSize, gridAreaSize) + baselineShim;
830
831     bool overrideSizeHasChanged = updateOverrideContainingBlockContentSizeForChild(child, childInlineDirection, gridAreaSize);
832     layoutGridItemForMinSizeComputation(child, overrideSizeHasChanged);
833
834     return child.computeLogicalHeightUsing(MinSize, childMinSize, WTF::nullopt).value_or(0) + child.marginLogicalHeight() + child.scrollbarLogicalHeight() + baselineShim;
835 }
836
837 bool GridTrackSizingAlgorithm::canParticipateInBaselineAlignment(const RenderBox& child, GridAxis baselineAxis) const
838 {
839     ASSERT(baselineAxis == GridColumnAxis ? m_columnBaselineItemsMap.contains(&child) : m_rowBaselineItemsMap.contains(&child));
840
841     // Baseline cyclic dependencies only happen with synthesized
842     // baselines. These cases include orthogonal or empty grid items
843     // and replaced elements.
844     bool isParallelToBaselineAxis = baselineAxis == GridColumnAxis ? !GridLayoutFunctions::isOrthogonalChild(*m_renderGrid, child) : GridLayoutFunctions::isOrthogonalChild(*m_renderGrid, child);
845     if (isParallelToBaselineAxis && child.firstLineBaseline())
846         return true;
847
848     // Baseline cyclic dependencies only happen in grid areas with
849     // intrinsically-sized tracks. 
850     if (!isIntrinsicSizedGridArea(child, baselineAxis))
851         return true;
852
853     return isParallelToBaselineAxis ? !child.hasRelativeLogicalHeight() : !child.hasRelativeLogicalWidth() && !child.style().logicalWidth().isAuto();
854 }
855
856 bool GridTrackSizingAlgorithm::participateInBaselineAlignment(const RenderBox& child, GridAxis baselineAxis) const
857 {
858     return baselineAxis == GridColumnAxis ? m_columnBaselineItemsMap.get(&child) : m_rowBaselineItemsMap.get(&child);
859 }
860
861 void GridTrackSizingAlgorithm::updateBaselineAlignmentContext(const RenderBox& child, GridAxis baselineAxis)
862 {
863     ASSERT(wasSetup());
864     ASSERT(canParticipateInBaselineAlignment(child, baselineAxis));
865     ASSERT(!child.needsLayout());
866
867     ItemPosition align = m_renderGrid->selfAlignmentForChild(baselineAxis, child).position();
868     const auto& span = m_grid.gridItemSpan(child, gridDirectionForAxis(baselineAxis));
869     m_baselineAlignment.updateBaselineAlignmentContext(align, span.startLine(), child, baselineAxis);
870 }
871
872 LayoutUnit GridTrackSizingAlgorithm::baselineOffsetForChild(const RenderBox& child, GridAxis baselineAxis) const
873 {
874     if (!participateInBaselineAlignment(child, baselineAxis))
875         return LayoutUnit();
876
877     ItemPosition align = m_renderGrid->selfAlignmentForChild(baselineAxis, child).position();
878     const auto& span = m_grid.gridItemSpan(child, gridDirectionForAxis(baselineAxis));
879     return m_baselineAlignment.baselineOffsetForChild(align, span.startLine(), child, baselineAxis);
880 }
881
882 void GridTrackSizingAlgorithm::clearBaselineItemsCache()
883 {
884     m_columnBaselineItemsMap.clear();
885     m_rowBaselineItemsMap.clear();
886 }
887
888 void GridTrackSizingAlgorithm::cacheBaselineAlignedItem(const RenderBox& item, GridAxis axis)
889 {
890     ASSERT(m_renderGrid->isBaselineAlignmentForChild(item, axis));
891     if (axis == GridColumnAxis)
892         m_columnBaselineItemsMap.add(&item, true);
893     else
894         m_rowBaselineItemsMap.add(&item, true);
895 }
896
897 void GridTrackSizingAlgorithm::copyBaselineItemsCache(const GridTrackSizingAlgorithm& source, GridAxis axis)
898 {
899     if (axis == GridColumnAxis)
900         m_columnBaselineItemsMap = source.m_columnBaselineItemsMap;
901     else
902         m_rowBaselineItemsMap = source.m_rowBaselineItemsMap;
903 }
904
905 bool GridTrackSizingAlgorithmStrategy::updateOverrideContainingBlockContentSizeForChild(RenderBox& child, GridTrackSizingDirection direction, Optional<LayoutUnit> overrideSize) const
906 {
907     if (!overrideSize)
908         overrideSize = m_algorithm.gridAreaBreadthForChild(child, direction);
909     if (GridLayoutFunctions::hasOverrideContainingBlockContentSizeForChild(child, direction) && GridLayoutFunctions::overrideContainingBlockContentSizeForChild(child, direction) == overrideSize)
910         return false;
911
912     setOverrideContainingBlockContentSizeForChild(child, direction, overrideSize);
913     return true;
914 }
915
916 class IndefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
917 public:
918     IndefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
919         : GridTrackSizingAlgorithmStrategy(algorithm) { }
920
921 private:
922     LayoutUnit minLogicalWidthForChild(RenderBox&, Length childMinSize, LayoutUnit availableSize) const override;
923     void layoutGridItemForMinSizeComputation(RenderBox&, bool overrideSizeHasChanged) const override;
924     void maximizeTracks(Vector<GridTrack>&, Optional<LayoutUnit>& freeSpace) override;
925     double findUsedFlexFraction(Vector<unsigned>& flexibleSizedTracksIndex, GridTrackSizingDirection, Optional<LayoutUnit> freeSpace) const override;
926     bool recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const override;
927     LayoutUnit freeSpaceForStretchAutoTracksStep() const override;
928 };
929
930 LayoutUnit IndefiniteSizeStrategy::minLogicalWidthForChild(RenderBox& child, Length childMinSize, LayoutUnit availableSize) const
931 {
932     return child.computeLogicalWidthInFragmentUsing(MinSize, childMinSize, availableSize, *renderGrid(), nullptr) + marginIntrinsicLogicalWidthForChild(renderGrid(), child);
933 }
934
935 void IndefiniteSizeStrategy::layoutGridItemForMinSizeComputation(RenderBox& child, bool overrideSizeHasChanged) const
936 {
937     if (overrideSizeHasChanged && direction() != ForColumns)
938         child.setNeedsLayout(MarkOnlyThis);
939     child.layoutIfNeeded();
940 }
941
942 void IndefiniteSizeStrategy::maximizeTracks(Vector<GridTrack>& tracks, Optional<LayoutUnit>& freeSpace)
943 {
944     UNUSED_PARAM(freeSpace);
945     for (auto& track : tracks)
946         track.setBaseSize(track.growthLimit());
947 }
948
949
950 static inline double normalizedFlexFraction(const GridTrack& track, double flexFactor)
951 {
952     return track.baseSize() / std::max<double>(1, flexFactor);
953 }
954
955 double IndefiniteSizeStrategy::findUsedFlexFraction(Vector<unsigned>& flexibleSizedTracksIndex, GridTrackSizingDirection direction, Optional<LayoutUnit> freeSpace) const
956 {
957     UNUSED_PARAM(freeSpace);
958     auto allTracks = m_algorithm.tracks(direction);
959
960     double flexFraction = 0;
961     for (const auto& trackIndex : flexibleSizedTracksIndex) {
962         // FIXME: we pass TrackSizing to gridTrackSize() because it does not really matter
963         // as we know the track is a flex sized track. It'd be nice not to have to do that.
964         flexFraction = std::max(flexFraction, normalizedFlexFraction(allTracks[trackIndex], gridTrackSize(direction, trackIndex).maxTrackBreadth().flex()));
965     }
966
967     const Grid& grid = m_algorithm.grid();
968     if (!grid.hasGridItems())
969         return flexFraction;
970
971     for (unsigned i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
972         GridIterator iterator(grid, direction, flexibleSizedTracksIndex[i]);
973         while (auto* gridItem = iterator.nextGridItem()) {
974             const GridSpan& span = grid.gridItemSpan(*gridItem, direction);
975
976             // Do not include already processed items.
977             if (i > 0 && span.startLine() <= flexibleSizedTracksIndex[i - 1])
978                 continue;
979
980             // Removing gutters from the max-content contribution of the item, so they are not taken into account in FindFrUnitSize().
981             LayoutUnit leftOverSpace = maxContentForChild(*gridItem) - renderGrid()->guttersSize(m_algorithm.grid(), direction, span.startLine(), span.integerSpan(), availableSpace());
982             flexFraction = std::max(flexFraction, findFrUnitSize(span, leftOverSpace));
983         }
984     }
985
986     return flexFraction;
987 }
988
989 bool IndefiniteSizeStrategy::recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const
990 {
991     if (direction() == ForColumns)
992         return false;
993
994     const RenderGrid* renderGrid = this->renderGrid();
995
996     auto minSize = renderGrid->computeContentLogicalHeight(MinSize, renderGrid->style().logicalMinHeight(), WTF::nullopt);
997     auto maxSize = renderGrid->computeContentLogicalHeight(MaxSize, renderGrid->style().logicalMaxHeight(), WTF::nullopt);
998
999     // Redo the flex fraction computation using min|max-height as definite available space in case
1000     // the total height is smaller than min-height or larger than max-height.
1001     LayoutUnit rowsSize = totalGrowth + computeTrackBasedSize();
1002     bool checkMinSize = minSize && rowsSize < minSize.value();
1003     bool checkMaxSize = maxSize && rowsSize > maxSize.value();
1004     if (!checkMinSize && !checkMaxSize)
1005         return false;
1006
1007     LayoutUnit freeSpace = checkMaxSize ? maxSize.value() : -1_lu;
1008     const Grid& grid = m_algorithm.grid();
1009     freeSpace = std::max(freeSpace, minSize.value()) - renderGrid->guttersSize(grid, ForRows, 0, grid.numTracks(ForRows), availableSpace());
1010
1011     size_t numberOfTracks = m_algorithm.tracks(ForRows).size();
1012     flexFraction = findFrUnitSize(GridSpan::translatedDefiniteGridSpan(0, numberOfTracks), freeSpace);
1013     return true;
1014 }
1015
1016 class DefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
1017 public:
1018     DefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
1019         : GridTrackSizingAlgorithmStrategy(algorithm) { }
1020
1021 private:
1022     LayoutUnit minLogicalWidthForChild(RenderBox&, Length childMinSize, LayoutUnit availableSize) const override;
1023     void layoutGridItemForMinSizeComputation(RenderBox&, bool overrideSizeHasChanged) const override;
1024     void maximizeTracks(Vector<GridTrack>&, Optional<LayoutUnit>& freeSpace) override;
1025     double findUsedFlexFraction(Vector<unsigned>& flexibleSizedTracksIndex, GridTrackSizingDirection, Optional<LayoutUnit> freeSpace) const override;
1026     bool recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const override;
1027     LayoutUnit freeSpaceForStretchAutoTracksStep() const override;
1028 };
1029
1030 LayoutUnit IndefiniteSizeStrategy::freeSpaceForStretchAutoTracksStep() const
1031 {
1032     ASSERT(!m_algorithm.freeSpace(direction()));
1033     if (direction() == ForColumns)
1034         return 0_lu;
1035
1036     auto minSize = renderGrid()->computeContentLogicalHeight(MinSize, renderGrid()->style().logicalMinHeight(), WTF::nullopt);
1037     if (!minSize)
1038         return 0_lu;
1039     return minSize.value() - computeTrackBasedSize();
1040 }
1041
1042 LayoutUnit DefiniteSizeStrategy::minLogicalWidthForChild(RenderBox& child, Length childMinSize, LayoutUnit availableSize) const
1043 {
1044     LayoutUnit marginLogicalWidth =
1045         GridLayoutFunctions::computeMarginLogicalSizeForChild(*renderGrid(), ForColumns, child);
1046     return child.computeLogicalWidthInFragmentUsing(MinSize, childMinSize, availableSize, *renderGrid(), nullptr) + marginLogicalWidth;
1047 }
1048
1049 void DefiniteSizeStrategy::maximizeTracks(Vector<GridTrack>& tracks, Optional<LayoutUnit>& freeSpace)
1050 {
1051     size_t tracksSize = tracks.size();
1052     Vector<GridTrack*> tracksForDistribution(tracksSize);
1053     for (size_t i = 0; i < tracksSize; ++i) {
1054         tracksForDistribution[i] = tracks.data() + i;
1055         tracksForDistribution[i]->setPlannedSize(tracksForDistribution[i]->baseSize());
1056     }
1057
1058     ASSERT(freeSpace);
1059     distributeSpaceToTracks(tracksForDistribution, freeSpace.value());
1060
1061     for (auto* track : tracksForDistribution)
1062         track->setBaseSize(track->plannedSize());
1063 }
1064
1065
1066 void DefiniteSizeStrategy::layoutGridItemForMinSizeComputation(RenderBox& child, bool overrideSizeHasChanged) const
1067 {
1068     if (overrideSizeHasChanged)
1069         child.setNeedsLayout(MarkOnlyThis);
1070     child.layoutIfNeeded();
1071 }
1072
1073 double DefiniteSizeStrategy::findUsedFlexFraction(Vector<unsigned>&, GridTrackSizingDirection direction, Optional<LayoutUnit> freeSpace) const
1074 {
1075     GridSpan allTracksSpan = GridSpan::translatedDefiniteGridSpan(0, m_algorithm.tracks(direction).size());
1076     ASSERT(freeSpace);
1077     return findFrUnitSize(allTracksSpan, freeSpace.value());
1078 }
1079
1080 LayoutUnit DefiniteSizeStrategy::freeSpaceForStretchAutoTracksStep() const
1081 {
1082     return m_algorithm.freeSpace(direction()).value();
1083 }
1084
1085 bool DefiniteSizeStrategy::recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const
1086 {
1087     UNUSED_PARAM(flexFraction);
1088     UNUSED_PARAM(totalGrowth);
1089     return false;
1090 }
1091
1092 // GridTrackSizingAlgorithm steps.
1093
1094 void GridTrackSizingAlgorithm::initializeTrackSizes()
1095 {
1096     ASSERT(m_contentSizedTracksIndex.isEmpty());
1097     ASSERT(m_flexibleSizedTracksIndex.isEmpty());
1098     ASSERT(m_autoSizedTracksForStretchIndex.isEmpty());
1099     ASSERT(!m_hasPercentSizedRowsIndefiniteHeight);
1100
1101     Vector<GridTrack>& allTracks = tracks(m_direction);
1102     const bool hasDefiniteFreeSpace = !!availableSpace();
1103     const bool indefiniteHeight = m_direction == ForRows && !m_renderGrid->hasDefiniteLogicalHeight();
1104     LayoutUnit maxSize = std::max(0_lu, availableSpace().value_or(0_lu));
1105     // 1. Initialize per Grid track variables.
1106     for (unsigned i = 0; i < allTracks.size(); ++i) {
1107         GridTrack& track = allTracks[i];
1108         const GridTrackSize& trackSize = gridTrackSize(m_direction, i);
1109
1110         track.setBaseSize(initialBaseSize(trackSize));
1111         track.setGrowthLimit(initialGrowthLimit(trackSize, track.baseSize()));
1112         track.setInfinitelyGrowable(false);
1113
1114         if (trackSize.isFitContent()) {
1115             GridLength gridLength = trackSize.fitContentTrackBreadth();
1116             if (!gridLength.isPercentage() || hasDefiniteFreeSpace)
1117                 track.setGrowthLimitCap(valueForLength(gridLength.length(), maxSize));
1118         }
1119         if (trackSize.isContentSized())
1120             m_contentSizedTracksIndex.append(i);
1121         if (trackSize.maxTrackBreadth().isFlex())
1122             m_flexibleSizedTracksIndex.append(i);
1123         if (trackSize.hasAutoMaxTrackBreadth() && !trackSize.isFitContent())
1124             m_autoSizedTracksForStretchIndex.append(i);
1125
1126         if (!m_hasPercentSizedRowsIndefiniteHeight && indefiniteHeight) {
1127             auto& rawTrackSize = rawGridTrackSize(m_direction, i);
1128             if (rawTrackSize.minTrackBreadth().isPercentage() || rawTrackSize.maxTrackBreadth().isPercentage())
1129                 m_hasPercentSizedRowsIndefiniteHeight = true;
1130         }
1131     }
1132 }
1133
1134 void GridTrackSizingAlgorithm::resolveIntrinsicTrackSizes()
1135 {
1136     Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
1137     HashSet<RenderBox*> itemsSet;
1138     Vector<GridTrack>& allTracks = tracks(m_direction);
1139     if (m_grid.hasGridItems()) {
1140         for (auto trackIndex : m_contentSizedTracksIndex) {
1141             GridIterator iterator(m_grid, m_direction, trackIndex);
1142             GridTrack& track = allTracks[trackIndex];
1143
1144             while (auto* gridItem = iterator.nextGridItem()) {
1145                 if (itemsSet.add(gridItem).isNewEntry) {
1146                     const GridSpan& span = m_grid.gridItemSpan(*gridItem, m_direction);
1147                     if (span.integerSpan() == 1)
1148                         sizeTrackToFitNonSpanningItem(span, *gridItem, track);
1149                     else if (!spanningItemCrossesFlexibleSizedTracks(span))
1150                         itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, span));
1151                 }
1152             }
1153         }
1154         std::sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end());
1155     }
1156
1157     auto it = itemsSortedByIncreasingSpan.begin();
1158     auto end = itemsSortedByIncreasingSpan.end();
1159     while (it != end) {
1160         GridItemsSpanGroupRange spanGroupRange = { it, std::upper_bound(it, end, *it) };
1161         increaseSizesToAccommodateSpanningItems<ResolveIntrinsicMinimums>(spanGroupRange);
1162         increaseSizesToAccommodateSpanningItems<ResolveContentBasedMinimums>(spanGroupRange);
1163         increaseSizesToAccommodateSpanningItems<ResolveMaxContentMinimums>(spanGroupRange);
1164         increaseSizesToAccommodateSpanningItems<ResolveIntrinsicMaximums>(spanGroupRange);
1165         increaseSizesToAccommodateSpanningItems<ResolveMaxContentMaximums>(spanGroupRange);
1166         it = spanGroupRange.rangeEnd;
1167     }
1168
1169     for (auto trackIndex : m_contentSizedTracksIndex) {
1170         GridTrack& track = allTracks[trackIndex];
1171         if (track.growthLimit() == infinity)
1172             track.setGrowthLimit(track.baseSize());
1173     }
1174 }
1175
1176 void GridTrackSizingAlgorithm::stretchFlexibleTracks(Optional<LayoutUnit> freeSpace)
1177 {
1178     if (m_flexibleSizedTracksIndex.isEmpty())
1179         return;
1180
1181     double flexFraction = m_strategy->findUsedFlexFraction(m_flexibleSizedTracksIndex, m_direction, freeSpace);
1182
1183     LayoutUnit totalGrowth;
1184     Vector<LayoutUnit> increments;
1185     increments.grow(m_flexibleSizedTracksIndex.size());
1186     computeFlexSizedTracksGrowth(flexFraction, increments, totalGrowth);
1187
1188     if (m_strategy->recomputeUsedFlexFractionIfNeeded(flexFraction, totalGrowth)) {
1189         totalGrowth = 0_lu;
1190         computeFlexSizedTracksGrowth(flexFraction, increments, totalGrowth);
1191     }
1192
1193     size_t i = 0;
1194     Vector<GridTrack>& allTracks = tracks(m_direction);
1195     for (auto trackIndex : m_flexibleSizedTracksIndex) {
1196         auto& track = allTracks[trackIndex];
1197         if (LayoutUnit increment = increments[i++])
1198             track.setBaseSize(track.baseSize() + increment);
1199     }
1200     if (this->freeSpace(m_direction))
1201         setFreeSpace(m_direction, this->freeSpace(m_direction).value() - totalGrowth);
1202     m_maxContentSize += totalGrowth;
1203 }
1204
1205 void GridTrackSizingAlgorithm::stretchAutoTracks()
1206 {
1207     auto currentFreeSpace = m_strategy->freeSpaceForStretchAutoTracksStep();
1208     if (m_autoSizedTracksForStretchIndex.isEmpty() || currentFreeSpace <= 0
1209         || (m_renderGrid->contentAlignment(m_direction).distribution() != ContentDistribution::Stretch))
1210         return;
1211
1212     Vector<GridTrack>& allTracks = tracks(m_direction);
1213     unsigned numberOfAutoSizedTracks = m_autoSizedTracksForStretchIndex.size();
1214     LayoutUnit sizeToIncrease = currentFreeSpace / numberOfAutoSizedTracks;
1215     for (const auto& trackIndex : m_autoSizedTracksForStretchIndex) {
1216         auto& track = allTracks[trackIndex];
1217         track.setBaseSize(track.baseSize() + sizeToIncrease);
1218     }
1219     setFreeSpace(m_direction, 0_lu);
1220 }
1221
1222 void GridTrackSizingAlgorithm::advanceNextState()
1223 {
1224     switch (m_sizingState) {
1225     case ColumnSizingFirstIteration:
1226         m_sizingState = RowSizingFirstIteration;
1227         return;
1228     case RowSizingFirstIteration:
1229         m_sizingState = ColumnSizingSecondIteration;
1230         return;
1231     case ColumnSizingSecondIteration:
1232         m_sizingState = RowSizingSecondIteration;
1233         return;
1234     case RowSizingSecondIteration:
1235         m_sizingState = ColumnSizingFirstIteration;
1236         return;
1237     }
1238     ASSERT_NOT_REACHED();
1239     m_sizingState = ColumnSizingFirstIteration;
1240 }
1241
1242 bool GridTrackSizingAlgorithm::isValidTransition() const
1243 {
1244     switch (m_sizingState) {
1245     case ColumnSizingFirstIteration:
1246     case ColumnSizingSecondIteration:
1247         return m_direction == ForColumns;
1248     case RowSizingFirstIteration:
1249     case RowSizingSecondIteration:
1250         return m_direction == ForRows;
1251     }
1252     ASSERT_NOT_REACHED();
1253     return false;
1254 }
1255
1256 // GridTrackSizingAlgorithm API.
1257
1258 void GridTrackSizingAlgorithm::setup(GridTrackSizingDirection direction, unsigned numTracks, SizingOperation sizingOperation, Optional<LayoutUnit> availableSpace, Optional<LayoutUnit> freeSpace)
1259 {
1260     ASSERT(m_needsSetup);
1261     m_direction = direction;
1262     setAvailableSpace(direction, availableSpace);
1263
1264     m_sizingOperation = sizingOperation;
1265     switch (m_sizingOperation) {
1266     case IntrinsicSizeComputation:
1267         m_strategy = std::make_unique<IndefiniteSizeStrategy>(*this);
1268         break;
1269     case TrackSizing:
1270         m_strategy = std::make_unique<DefiniteSizeStrategy>(*this);
1271         break;
1272     }
1273
1274     m_contentSizedTracksIndex.shrink(0);
1275     m_flexibleSizedTracksIndex.shrink(0);
1276     m_autoSizedTracksForStretchIndex.shrink(0);
1277
1278     setFreeSpace(direction, freeSpace);
1279     tracks(direction).resize(numTracks);
1280
1281     m_needsSetup = false;
1282     m_hasPercentSizedRowsIndefiniteHeight = false;
1283
1284     computeBaselineAlignmentContext();
1285 }
1286
1287 void GridTrackSizingAlgorithm::computeBaselineAlignmentContext()
1288 {
1289     GridAxis axis = gridAxisForDirection(m_direction);
1290     m_baselineAlignment.clear(axis);
1291     m_baselineAlignment.setBlockFlow(m_renderGrid->style().writingMode());
1292     BaselineItemsCache& baselineItemsCache = axis == GridColumnAxis ? m_columnBaselineItemsMap : m_rowBaselineItemsMap;
1293     BaselineItemsCache tmpBaselineItemsCache = baselineItemsCache;
1294     for (auto* child : tmpBaselineItemsCache.keys()) {
1295         // FIXME (jfernandez): We may have to get rid of the baseline participation
1296         // flag (hence just using a HashSet) depending on the CSS WG resolution on
1297         // https://github.com/w3c/csswg-drafts/issues/3046
1298         if (canParticipateInBaselineAlignment(*child, axis)) {
1299             updateBaselineAlignmentContext(*child, axis);
1300             baselineItemsCache.set(child, true);
1301         } else
1302             baselineItemsCache.set(child, false);
1303     }
1304 }
1305
1306 void GridTrackSizingAlgorithm::run()
1307 {
1308     ASSERT(wasSetup());
1309     StateMachine stateMachine(*this);
1310
1311     // Step 1.
1312     const Optional<LayoutUnit> initialFreeSpace = freeSpace(m_direction);
1313     initializeTrackSizes();
1314
1315     // Step 2.
1316     if (!m_contentSizedTracksIndex.isEmpty())
1317         resolveIntrinsicTrackSizes();
1318
1319     // This is not exactly a step of the track sizing algorithm, but we use the track sizes computed
1320     // up to this moment (before maximization) to calculate the grid container intrinsic sizes.
1321     computeGridContainerIntrinsicSizes();
1322
1323     if (freeSpace(m_direction)) {
1324         LayoutUnit updatedFreeSpace = freeSpace(m_direction).value() - m_minContentSize;
1325         setFreeSpace(m_direction, updatedFreeSpace);
1326         if (updatedFreeSpace <= 0)
1327             return;
1328     }
1329
1330     // Step 3.
1331     m_strategy->maximizeTracks(tracks(m_direction), m_direction == ForColumns ? m_freeSpaceColumns : m_freeSpaceRows);
1332
1333     // Step 4.
1334     stretchFlexibleTracks(initialFreeSpace);
1335
1336     // Step 5.
1337     stretchAutoTracks();
1338 }
1339
1340 void GridTrackSizingAlgorithm::reset()
1341 {
1342     ASSERT(wasSetup());
1343     m_sizingState = ColumnSizingFirstIteration;
1344     m_columns.shrink(0);
1345     m_rows.shrink(0);
1346     m_contentSizedTracksIndex.shrink(0);
1347     m_flexibleSizedTracksIndex.shrink(0);
1348     m_autoSizedTracksForStretchIndex.shrink(0);
1349     setAvailableSpace(ForRows, WTF::nullopt);
1350     setAvailableSpace(ForColumns, WTF::nullopt);
1351     m_hasPercentSizedRowsIndefiniteHeight = false;
1352 }
1353
1354 #ifndef NDEBUG
1355 bool GridTrackSizingAlgorithm::tracksAreWiderThanMinTrackBreadth() const
1356 {
1357     const Vector<GridTrack>& allTracks = tracks(m_direction);
1358     for (size_t i = 0; i < allTracks.size(); ++i) {
1359         GridTrackSize trackSize = gridTrackSize(m_direction, i);
1360         if (initialBaseSize(trackSize) > allTracks[i].baseSize())
1361             return false;
1362     }
1363     return true;
1364 }
1365 #endif
1366
1367 GridTrackSizingAlgorithm::StateMachine::StateMachine(GridTrackSizingAlgorithm& algorithm)
1368     : m_algorithm(algorithm)
1369 {
1370     ASSERT(m_algorithm.isValidTransition());
1371     ASSERT(!m_algorithm.m_needsSetup);
1372 }
1373
1374 GridTrackSizingAlgorithm::StateMachine::~StateMachine()
1375 {
1376     m_algorithm.advanceNextState();
1377     m_algorithm.m_needsSetup = true;
1378 }
1379
1380 } // namespace WebCore