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
34namespace WebCore {
35
36const LayoutUnit& GridTrack::baseSize() const
37{
38 ASSERT(isGrowthLimitBiggerThanBaseSize());
39 return m_baseSize;
40}
41
42const 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
49void GridTrack::setBaseSize(LayoutUnit baseSize)
50{
51 m_baseSize = baseSize;
52 ensureGrowthLimitIsBiggerThanBaseSize();
53}
54
55void GridTrack::setGrowthLimit(LayoutUnit growthLimit)
56{
57 m_growthLimit = growthLimit == infinity ? growthLimit : std::min(growthLimit, m_growthLimitCap.valueOr(growthLimit));
58 ensureGrowthLimitIsBiggerThanBaseSize();
59}
60
61const LayoutUnit& GridTrack::growthLimitIfNotInfinite() const
62{
63 ASSERT(isGrowthLimitBiggerThanBaseSize());
64 return m_growthLimit == infinity ? m_baseSize : m_growthLimit;
65}
66
67void GridTrack::setTempSize(const LayoutUnit& tempSize)
68{
69 ASSERT(tempSize >= 0);
70 ASSERT(growthLimitIsInfinite() || growthLimit() >= tempSize);
71 m_tempSize = tempSize;
72}
73
74void GridTrack::growTempSize(const LayoutUnit& tempSize)
75{
76 ASSERT(tempSize >= 0);
77 m_tempSize += tempSize;
78}
79
80void GridTrack::setGrowthLimitCap(Optional<LayoutUnit> growthLimitCap)
81{
82 ASSERT(!growthLimitCap || growthLimitCap.value() >= 0);
83 m_growthLimitCap = growthLimitCap;
84}
85
86void GridTrack::ensureGrowthLimitIsBiggerThanBaseSize()
87{
88 if (m_growthLimit != infinity && m_growthLimit < m_baseSize)
89 m_growthLimit = m_baseSize;
90}
91
92// Static helper methods.
93
94static GridAxis gridAxisForDirection(GridTrackSizingDirection direction)
95{
96 return direction == ForColumns ? GridRowAxis : GridColumnAxis;
97}
98
99static GridTrackSizingDirection gridDirectionForAxis(GridAxis axis)
100{
101 return axis == GridRowAxis ? ForColumns : ForRows;
102}
103
104static 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
111static 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.
120static 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
137void GridTrackSizingAlgorithm::setFreeSpace(GridTrackSizingDirection direction, Optional<LayoutUnit> freeSpace)
138{
139 if (direction == ForColumns)
140 m_freeSpaceColumns = freeSpace;
141 else
142 m_freeSpaceRows = freeSpace;
143}
144
145Optional<LayoutUnit> GridTrackSizingAlgorithm::availableSpace() const
146{
147 ASSERT(wasSetup());
148 return availableSpace(m_direction);
149}
150
151void GridTrackSizingAlgorithm::setAvailableSpace(GridTrackSizingDirection direction, Optional<LayoutUnit> availableSpace)
152{
153 if (direction == ForColumns)
154 m_availableSpaceColumns = availableSpace;
155 else
156 m_availableSpaceRows = availableSpace;
157}
158
159const 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
199LayoutUnit 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
211LayoutUnit 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().valueOr(0), 0));
220
221 ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
222 return 0;
223}
224
225LayoutUnit 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().valueOr(0), 0));
234
235 ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
236 return infinity;
237}
238
239void 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().valueOr(0)));
258 track.setGrowthLimit(std::max(track.growthLimit(), growthLimit));
259 }
260}
261
262bool 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
273class GridItemWithSpan {
274public:
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
286private:
287 std::reference_wrapper<RenderBox> m_gridItem;
288 GridSpan m_span;
289};
290
291struct GridItemsSpanGroupRange {
292 Vector<GridItemWithSpan>::iterator rangeStart;
293 Vector<GridItemWithSpan>::iterator rangeEnd;
294};
295
296enum TrackSizeRestriction {
297 AllowInfinity,
298 ForbidInfinity,
299};
300
301LayoutUnit 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
321static 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
343static 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
360static 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
380static 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
400static 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
423template <TrackSizeComputationPhase phase>
424void 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
473static 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().valueOr(track1->growthLimit());
487 LayoutUnit track2Limit = track2->growthLimitCap().valueOr(track2->growthLimit());
488 return (track1Limit - track1->baseSize()) < (track2Limit - track2->baseSize());
489}
490
491static 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
503template <TrackSizeComputationPhase phase>
504void 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
552LayoutSize GridTrackSizingAlgorithm::estimatedGridAreaBreadthForChild(const RenderBox& child) const
553{
554 return {estimatedGridAreaBreadthForChild(child, ForColumns), estimatedGridAreaBreadthForChild(child, ForRows)};
555}
556
557LayoutUnit 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.valueOr(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
583LayoutUnit 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
613bool GridTrackSizingAlgorithm::isRelativeGridLengthAsAuto(const GridLength& length, GridTrackSizingDirection direction) const
614{
615 return length.isPercentage() && !availableSpace(direction);
616}
617
618bool 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
639GridTrackSize 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 isRelativeGridLengthAsAuto(trackSize.fitContentTrackBreadth(), direction) ? GridTrackSize(Length(Auto), Length(MaxContent)) : 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
667double 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
694void 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
710double 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
736void 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.
752LayoutUnit 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
770LayoutUnit 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
784LayoutUnit 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
798LayoutUnit GridTrackSizingAlgorithmStrategy::minSizeForChild(RenderBox& child) const
799{
800 GridTrackSizingDirection childInlineDirection = GridLayoutFunctions::flowAwareDirectionForChild(*renderGrid(), child, ForColumns);
801 bool isRowAxis = direction() == childInlineDirection;
802 const Length& childSize = isRowAxis ? child.style().logicalWidth() : child.style().logicalHeight();
803 if (!childSize.isAuto())
804 return minContentForChild(child);
805
806 const Length& childMinSize = isRowAxis ? child.style().logicalMinWidth() : child.style().logicalMinHeight();
807 bool overflowIsVisible = isRowAxis ? child.style().overflowInlineDirection() == Overflow::Visible : child.style().overflowBlockDirection() == Overflow::Visible;
808 LayoutUnit baselineShim = m_algorithm.baselineOffsetForChild(child, gridAxisForDirection(direction()));
809
810 if (childSize.isAuto() && childMinSize.isAuto() && overflowIsVisible) {
811 auto minSize = minContentForChild(child);
812 LayoutUnit maxBreadth;
813 for (auto trackPosition : m_algorithm.grid().gridItemSpan(child, direction())) {
814 GridTrackSize trackSize = m_algorithm.gridTrackSize(direction(), trackPosition);
815 if (!trackSize.hasFixedMaxTrackBreadth())
816 return minSize;
817 maxBreadth += valueForLength(trackSize.maxTrackBreadth().length(), availableSpace().valueOr(0_lu));
818 }
819 if (minSize > maxBreadth) {
820 auto marginAndBorderAndPadding = GridLayoutFunctions::marginLogicalSizeForChild(*renderGrid(), direction(), child);
821 marginAndBorderAndPadding += isRowAxis ? child.borderAndPaddingLogicalWidth() : child.borderAndPaddingLogicalHeight();
822 minSize = std::max(maxBreadth, marginAndBorderAndPadding + baselineShim);
823 }
824 return minSize;
825 }
826
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).valueOr(0) + child.marginLogicalHeight() + child.scrollbarLogicalHeight() + baselineShim;
835}
836
837bool 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
856bool GridTrackSizingAlgorithm::participateInBaselineAlignment(const RenderBox& child, GridAxis baselineAxis) const
857{
858 return baselineAxis == GridColumnAxis ? m_columnBaselineItemsMap.get(&child) : m_rowBaselineItemsMap.get(&child);
859}
860
861void 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
872LayoutUnit 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
882void GridTrackSizingAlgorithm::clearBaselineItemsCache()
883{
884 m_columnBaselineItemsMap.clear();
885 m_rowBaselineItemsMap.clear();
886}
887
888void 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
897void 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
905bool 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
916class IndefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
917public:
918 IndefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
919 : GridTrackSizingAlgorithmStrategy(algorithm) { }
920
921private:
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
930LayoutUnit IndefiniteSizeStrategy::minLogicalWidthForChild(RenderBox& child, Length childMinSize, LayoutUnit availableSize) const
931{
932 return child.computeLogicalWidthInFragmentUsing(MinSize, childMinSize, availableSize, *renderGrid(), nullptr) + marginIntrinsicLogicalWidthForChild(renderGrid(), child);
933}
934
935void IndefiniteSizeStrategy::layoutGridItemForMinSizeComputation(RenderBox& child, bool overrideSizeHasChanged) const
936{
937 if (overrideSizeHasChanged && direction() != ForColumns)
938 child.setNeedsLayout(MarkOnlyThis);
939 child.layoutIfNeeded();
940}
941
942void 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
950static inline double normalizedFlexFraction(const GridTrack& track, double flexFactor)
951{
952 return track.baseSize() / std::max<double>(1, flexFactor);
953}
954
955double 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
989bool 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
1016class DefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
1017public:
1018 DefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
1019 : GridTrackSizingAlgorithmStrategy(algorithm) { }
1020
1021private:
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
1030LayoutUnit 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
1042LayoutUnit 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
1049void 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
1066void DefiniteSizeStrategy::layoutGridItemForMinSizeComputation(RenderBox& child, bool overrideSizeHasChanged) const
1067{
1068 if (overrideSizeHasChanged)
1069 child.setNeedsLayout(MarkOnlyThis);
1070 child.layoutIfNeeded();
1071}
1072
1073double 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
1080LayoutUnit DefiniteSizeStrategy::freeSpaceForStretchAutoTracksStep() const
1081{
1082 return m_algorithm.freeSpace(direction()).value();
1083}
1084
1085bool 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
1094void 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 indefiniteHeight = m_direction == ForRows && !m_renderGrid->hasDefiniteLogicalHeight();
1103 LayoutUnit maxSize = std::max(0_lu, availableSpace().valueOr(0_lu));
1104 // 1. Initialize per Grid track variables.
1105 for (unsigned i = 0; i < allTracks.size(); ++i) {
1106 GridTrack& track = allTracks[i];
1107 const GridTrackSize& trackSize = gridTrackSize(m_direction, i);
1108
1109 track.setBaseSize(initialBaseSize(trackSize));
1110 track.setGrowthLimit(initialGrowthLimit(trackSize, track.baseSize()));
1111 track.setInfinitelyGrowable(false);
1112
1113 if (trackSize.isFitContent())
1114 track.setGrowthLimitCap(valueForLength(trackSize.fitContentTrackBreadth().length(), maxSize));
1115 if (trackSize.isContentSized())
1116 m_contentSizedTracksIndex.append(i);
1117 if (trackSize.maxTrackBreadth().isFlex())
1118 m_flexibleSizedTracksIndex.append(i);
1119 if (trackSize.hasAutoMaxTrackBreadth() && !trackSize.isFitContent())
1120 m_autoSizedTracksForStretchIndex.append(i);
1121
1122 if (!m_hasPercentSizedRowsIndefiniteHeight && indefiniteHeight) {
1123 auto& rawTrackSize = rawGridTrackSize(m_direction, i);
1124 if (rawTrackSize.minTrackBreadth().isPercentage() || rawTrackSize.maxTrackBreadth().isPercentage())
1125 m_hasPercentSizedRowsIndefiniteHeight = true;
1126 }
1127 }
1128}
1129
1130void GridTrackSizingAlgorithm::resolveIntrinsicTrackSizes()
1131{
1132 Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
1133 HashSet<RenderBox*> itemsSet;
1134 Vector<GridTrack>& allTracks = tracks(m_direction);
1135 if (m_grid.hasGridItems()) {
1136 for (auto trackIndex : m_contentSizedTracksIndex) {
1137 GridIterator iterator(m_grid, m_direction, trackIndex);
1138 GridTrack& track = allTracks[trackIndex];
1139
1140 while (auto* gridItem = iterator.nextGridItem()) {
1141 if (itemsSet.add(gridItem).isNewEntry) {
1142 const GridSpan& span = m_grid.gridItemSpan(*gridItem, m_direction);
1143 if (span.integerSpan() == 1)
1144 sizeTrackToFitNonSpanningItem(span, *gridItem, track);
1145 else if (!spanningItemCrossesFlexibleSizedTracks(span))
1146 itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, span));
1147 }
1148 }
1149 }
1150 std::sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end());
1151 }
1152
1153 auto it = itemsSortedByIncreasingSpan.begin();
1154 auto end = itemsSortedByIncreasingSpan.end();
1155 while (it != end) {
1156 GridItemsSpanGroupRange spanGroupRange = { it, std::upper_bound(it, end, *it) };
1157 increaseSizesToAccommodateSpanningItems<ResolveIntrinsicMinimums>(spanGroupRange);
1158 increaseSizesToAccommodateSpanningItems<ResolveContentBasedMinimums>(spanGroupRange);
1159 increaseSizesToAccommodateSpanningItems<ResolveMaxContentMinimums>(spanGroupRange);
1160 increaseSizesToAccommodateSpanningItems<ResolveIntrinsicMaximums>(spanGroupRange);
1161 increaseSizesToAccommodateSpanningItems<ResolveMaxContentMaximums>(spanGroupRange);
1162 it = spanGroupRange.rangeEnd;
1163 }
1164
1165 for (auto trackIndex : m_contentSizedTracksIndex) {
1166 GridTrack& track = allTracks[trackIndex];
1167 if (track.growthLimit() == infinity)
1168 track.setGrowthLimit(track.baseSize());
1169 }
1170}
1171
1172void GridTrackSizingAlgorithm::stretchFlexibleTracks(Optional<LayoutUnit> freeSpace)
1173{
1174 if (m_flexibleSizedTracksIndex.isEmpty())
1175 return;
1176
1177 double flexFraction = m_strategy->findUsedFlexFraction(m_flexibleSizedTracksIndex, m_direction, freeSpace);
1178
1179 LayoutUnit totalGrowth;
1180 Vector<LayoutUnit> increments;
1181 increments.grow(m_flexibleSizedTracksIndex.size());
1182 computeFlexSizedTracksGrowth(flexFraction, increments, totalGrowth);
1183
1184 if (m_strategy->recomputeUsedFlexFractionIfNeeded(flexFraction, totalGrowth)) {
1185 totalGrowth = 0_lu;
1186 computeFlexSizedTracksGrowth(flexFraction, increments, totalGrowth);
1187 }
1188
1189 size_t i = 0;
1190 Vector<GridTrack>& allTracks = tracks(m_direction);
1191 for (auto trackIndex : m_flexibleSizedTracksIndex) {
1192 auto& track = allTracks[trackIndex];
1193 if (LayoutUnit increment = increments[i++])
1194 track.setBaseSize(track.baseSize() + increment);
1195 }
1196 if (this->freeSpace(m_direction))
1197 setFreeSpace(m_direction, this->freeSpace(m_direction).value() - totalGrowth);
1198 m_maxContentSize += totalGrowth;
1199}
1200
1201void GridTrackSizingAlgorithm::stretchAutoTracks()
1202{
1203 auto currentFreeSpace = m_strategy->freeSpaceForStretchAutoTracksStep();
1204 if (m_autoSizedTracksForStretchIndex.isEmpty() || currentFreeSpace <= 0
1205 || (m_renderGrid->contentAlignment(m_direction).distribution() != ContentDistribution::Stretch))
1206 return;
1207
1208 Vector<GridTrack>& allTracks = tracks(m_direction);
1209 unsigned numberOfAutoSizedTracks = m_autoSizedTracksForStretchIndex.size();
1210 LayoutUnit sizeToIncrease = currentFreeSpace / numberOfAutoSizedTracks;
1211 for (const auto& trackIndex : m_autoSizedTracksForStretchIndex) {
1212 auto& track = allTracks[trackIndex];
1213 track.setBaseSize(track.baseSize() + sizeToIncrease);
1214 }
1215 setFreeSpace(m_direction, 0_lu);
1216}
1217
1218void GridTrackSizingAlgorithm::advanceNextState()
1219{
1220 switch (m_sizingState) {
1221 case ColumnSizingFirstIteration:
1222 m_sizingState = RowSizingFirstIteration;
1223 return;
1224 case RowSizingFirstIteration:
1225 m_sizingState = ColumnSizingSecondIteration;
1226 return;
1227 case ColumnSizingSecondIteration:
1228 m_sizingState = RowSizingSecondIteration;
1229 return;
1230 case RowSizingSecondIteration:
1231 m_sizingState = ColumnSizingFirstIteration;
1232 return;
1233 }
1234 ASSERT_NOT_REACHED();
1235 m_sizingState = ColumnSizingFirstIteration;
1236}
1237
1238bool GridTrackSizingAlgorithm::isValidTransition() const
1239{
1240 switch (m_sizingState) {
1241 case ColumnSizingFirstIteration:
1242 case ColumnSizingSecondIteration:
1243 return m_direction == ForColumns;
1244 case RowSizingFirstIteration:
1245 case RowSizingSecondIteration:
1246 return m_direction == ForRows;
1247 }
1248 ASSERT_NOT_REACHED();
1249 return false;
1250}
1251
1252// GridTrackSizingAlgorithm API.
1253
1254void GridTrackSizingAlgorithm::setup(GridTrackSizingDirection direction, unsigned numTracks, SizingOperation sizingOperation, Optional<LayoutUnit> availableSpace, Optional<LayoutUnit> freeSpace)
1255{
1256 ASSERT(m_needsSetup);
1257 m_direction = direction;
1258 setAvailableSpace(direction, availableSpace);
1259
1260 m_sizingOperation = sizingOperation;
1261 switch (m_sizingOperation) {
1262 case IntrinsicSizeComputation:
1263 m_strategy = std::make_unique<IndefiniteSizeStrategy>(*this);
1264 break;
1265 case TrackSizing:
1266 m_strategy = std::make_unique<DefiniteSizeStrategy>(*this);
1267 break;
1268 }
1269
1270 m_contentSizedTracksIndex.shrink(0);
1271 m_flexibleSizedTracksIndex.shrink(0);
1272 m_autoSizedTracksForStretchIndex.shrink(0);
1273
1274 setFreeSpace(direction, freeSpace);
1275 tracks(direction).resize(numTracks);
1276
1277 m_needsSetup = false;
1278 m_hasPercentSizedRowsIndefiniteHeight = false;
1279
1280 computeBaselineAlignmentContext();
1281}
1282
1283void GridTrackSizingAlgorithm::computeBaselineAlignmentContext()
1284{
1285 GridAxis axis = gridAxisForDirection(m_direction);
1286 m_baselineAlignment.clear(axis);
1287 m_baselineAlignment.setBlockFlow(m_renderGrid->style().writingMode());
1288 BaselineItemsCache& baselineItemsCache = axis == GridColumnAxis ? m_columnBaselineItemsMap : m_rowBaselineItemsMap;
1289 BaselineItemsCache tmpBaselineItemsCache = baselineItemsCache;
1290 for (auto* child : tmpBaselineItemsCache.keys()) {
1291 // FIXME (jfernandez): We may have to get rid of the baseline participation
1292 // flag (hence just using a HashSet) depending on the CSS WG resolution on
1293 // https://github.com/w3c/csswg-drafts/issues/3046
1294 if (canParticipateInBaselineAlignment(*child, axis)) {
1295 updateBaselineAlignmentContext(*child, axis);
1296 baselineItemsCache.set(child, true);
1297 } else
1298 baselineItemsCache.set(child, false);
1299 }
1300}
1301
1302void GridTrackSizingAlgorithm::run()
1303{
1304 ASSERT(wasSetup());
1305 StateMachine stateMachine(*this);
1306
1307 // Step 1.
1308 const Optional<LayoutUnit> initialFreeSpace = freeSpace(m_direction);
1309 initializeTrackSizes();
1310
1311 // Step 2.
1312 if (!m_contentSizedTracksIndex.isEmpty())
1313 resolveIntrinsicTrackSizes();
1314
1315 // This is not exactly a step of the track sizing algorithm, but we use the track sizes computed
1316 // up to this moment (before maximization) to calculate the grid container intrinsic sizes.
1317 computeGridContainerIntrinsicSizes();
1318
1319 if (freeSpace(m_direction)) {
1320 LayoutUnit updatedFreeSpace = freeSpace(m_direction).value() - m_minContentSize;
1321 setFreeSpace(m_direction, updatedFreeSpace);
1322 if (updatedFreeSpace <= 0)
1323 return;
1324 }
1325
1326 // Step 3.
1327 m_strategy->maximizeTracks(tracks(m_direction), m_direction == ForColumns ? m_freeSpaceColumns : m_freeSpaceRows);
1328
1329 // Step 4.
1330 stretchFlexibleTracks(initialFreeSpace);
1331
1332 // Step 5.
1333 stretchAutoTracks();
1334}
1335
1336void GridTrackSizingAlgorithm::reset()
1337{
1338 ASSERT(wasSetup());
1339 m_sizingState = ColumnSizingFirstIteration;
1340 m_columns.shrink(0);
1341 m_rows.shrink(0);
1342 m_contentSizedTracksIndex.shrink(0);
1343 m_flexibleSizedTracksIndex.shrink(0);
1344 m_autoSizedTracksForStretchIndex.shrink(0);
1345 setAvailableSpace(ForRows, WTF::nullopt);
1346 setAvailableSpace(ForColumns, WTF::nullopt);
1347 m_hasPercentSizedRowsIndefiniteHeight = false;
1348}
1349
1350#ifndef NDEBUG
1351bool GridTrackSizingAlgorithm::tracksAreWiderThanMinTrackBreadth() const
1352{
1353 const Vector<GridTrack>& allTracks = tracks(m_direction);
1354 for (size_t i = 0; i < allTracks.size(); ++i) {
1355 GridTrackSize trackSize = gridTrackSize(m_direction, i);
1356 if (initialBaseSize(trackSize) > allTracks[i].baseSize())
1357 return false;
1358 }
1359 return true;
1360}
1361#endif
1362
1363GridTrackSizingAlgorithm::StateMachine::StateMachine(GridTrackSizingAlgorithm& algorithm)
1364 : m_algorithm(algorithm)
1365{
1366 ASSERT(m_algorithm.isValidTransition());
1367 ASSERT(!m_algorithm.m_needsSetup);
1368}
1369
1370GridTrackSizingAlgorithm::StateMachine::~StateMachine()
1371{
1372 m_algorithm.advanceNextState();
1373 m_algorithm.m_needsSetup = true;
1374}
1375
1376} // namespace WebCore
1377