c1ec915ea2a8cb468af5defbe5b074b370b50447
[WebKit-https.git] / Source / WebCore / rendering / RenderGrid.cpp
1 /*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
3  * Copyright (C) 2013-2017 Igalia S.L.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "RenderGrid.h"
29
30 #include "GridArea.h"
31 #include "GridLayoutFunctions.h"
32 #include "GridPositionsResolver.h"
33 #include "GridTrackSizingAlgorithm.h"
34 #include "LayoutRepainter.h"
35 #include "LayoutState.h"
36 #include "RenderChildIterator.h"
37 #include "RenderLayer.h"
38 #include "RenderView.h"
39 #include <cstdlib>
40 #include <wtf/IsoMallocInlines.h>
41
42 namespace WebCore {
43
44 WTF_MAKE_ISO_ALLOCATED_IMPL(RenderGrid);
45
46 enum TrackSizeRestriction {
47     AllowInfinity,
48     ForbidInfinity,
49 };
50
51 struct ContentAlignmentData {
52     WTF_MAKE_FAST_ALLOCATED;
53 public:
54     bool isValid() { return positionOffset >= 0 && distributionOffset >= 0; }
55     static ContentAlignmentData defaultOffsets() { return {-1, -1}; }
56
57     LayoutUnit positionOffset;
58     LayoutUnit distributionOffset;
59 };
60
61 RenderGrid::RenderGrid(Element& element, RenderStyle&& style)
62     : RenderBlock(element, WTFMove(style), 0)
63     , m_grid(*this)
64     , m_trackSizingAlgorithm(this, m_grid)
65 {
66     // All of our children must be block level.
67     setChildrenInline(false);
68 }
69
70 RenderGrid::~RenderGrid() = default;
71
72 void RenderGrid::addChild(RenderPtr<RenderObject> newChild, RenderObject* beforeChild)
73 {
74     auto& child = *newChild;
75     RenderBlock::addChild(WTFMove(newChild), beforeChild);
76
77     // Positioned grid items do not take up space or otherwise participate in the layout of the grid,
78     // for that reason we don't need to mark the grid as dirty when they are added.
79     if (child.isOutOfFlowPositioned())
80         return;
81
82     // The grid needs to be recomputed as it might contain auto-placed items that
83     // will change their position.
84     dirtyGrid();
85 }
86
87 RenderPtr<RenderObject> RenderGrid::takeChild(RenderObject& child)
88 {
89     auto takenChild = RenderBlock::takeChild(child);
90
91     // Positioned grid items do not take up space or otherwise participate in the layout of the grid,
92     // for that reason we don't need to mark the grid as dirty when they are removed.
93     if (child.isOutOfFlowPositioned())
94         return takenChild;
95
96     // The grid needs to be recomputed as it might contain auto-placed items that
97     // will change their position.
98     dirtyGrid();
99     return takenChild;
100 }
101
102 StyleSelfAlignmentData RenderGrid::selfAlignmentForChild(GridAxis axis, const RenderBox& child, const RenderStyle* gridStyle) const
103 {
104     return axis == GridRowAxis ? justifySelfForChild(child, gridStyle) : alignSelfForChild(child, gridStyle);
105 }
106
107 bool RenderGrid::selfAlignmentChangedToStretch(GridAxis axis, const RenderStyle& oldStyle, const RenderStyle& newStyle, const RenderBox& child) const
108 {
109     return selfAlignmentForChild(axis, child, &oldStyle).position() != ItemPositionStretch
110         && selfAlignmentForChild(axis, child, &newStyle).position() == ItemPositionStretch;
111 }
112
113 bool RenderGrid::selfAlignmentChangedFromStretch(GridAxis axis, const RenderStyle& oldStyle, const RenderStyle& newStyle, const RenderBox& child) const
114 {
115     return selfAlignmentForChild(axis, child, &oldStyle).position() == ItemPositionStretch
116         && selfAlignmentForChild(axis, child, &newStyle).position() != ItemPositionStretch;
117 }
118
119 void RenderGrid::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
120 {
121     RenderBlock::styleDidChange(diff, oldStyle);
122     if (!oldStyle || diff != StyleDifferenceLayout)
123         return;
124
125     const RenderStyle& newStyle = this->style();
126     if (oldStyle->resolvedAlignItems(selfAlignmentNormalBehavior(this)).position() == ItemPositionStretch) {
127         // Style changes on the grid container implying stretching (to-stretch) or
128         // shrinking (from-stretch) require the affected items to be laid out again.
129         // These logic only applies to 'stretch' since the rest of the alignment
130         // values don't change the size of the box.
131         // In any case, the items' overrideSize will be cleared and recomputed (if
132         // necessary)  as part of the Grid layout logic, triggered by this style
133         // change.
134         for (auto& child : childrenOfType<RenderBox>(*this)) {
135             if (child.isOutOfFlowPositioned())
136                 continue;
137             if (selfAlignmentChangedToStretch(GridRowAxis, *oldStyle, newStyle, child)
138                 || selfAlignmentChangedFromStretch(GridRowAxis, *oldStyle, newStyle, child)
139                 || selfAlignmentChangedToStretch(GridColumnAxis, *oldStyle, newStyle, child)
140                 || selfAlignmentChangedFromStretch(GridColumnAxis, *oldStyle, newStyle, child)) {
141                 child.setNeedsLayout();
142             }
143         }
144     }
145
146     if (explicitGridDidResize(*oldStyle) || namedGridLinesDefinitionDidChange(*oldStyle) || oldStyle->gridAutoFlow() != style().gridAutoFlow()
147         || (style().gridAutoRepeatColumns().size() || style().gridAutoRepeatRows().size()))
148         dirtyGrid();
149 }
150
151 bool RenderGrid::explicitGridDidResize(const RenderStyle& oldStyle) const
152 {
153     return oldStyle.gridColumns().size() != style().gridColumns().size()
154         || oldStyle.gridRows().size() != style().gridRows().size()
155         || oldStyle.namedGridAreaColumnCount() != style().namedGridAreaColumnCount()
156         || oldStyle.namedGridAreaRowCount() != style().namedGridAreaRowCount()
157         || oldStyle.gridAutoRepeatColumns().size() != style().gridAutoRepeatColumns().size()
158         || oldStyle.gridAutoRepeatRows().size() != style().gridAutoRepeatRows().size();
159 }
160
161 bool RenderGrid::namedGridLinesDefinitionDidChange(const RenderStyle& oldStyle) const
162 {
163     return oldStyle.namedGridRowLines() != style().namedGridRowLines()
164         || oldStyle.namedGridColumnLines() != style().namedGridColumnLines();
165 }
166
167 // This method optimizes the gutters computation by skiping the available size
168 // call if gaps are fixed size (it's only needed for percentages).
169 std::optional<LayoutUnit> RenderGrid::availableSpaceForGutters(GridTrackSizingDirection direction) const
170 {
171     bool isRowAxis = direction == ForColumns;
172     const Length& gap = isRowAxis ? style().gridColumnGap() : style().gridRowGap();
173     if (!gap.isPercent())
174         return std::nullopt;
175
176     return isRowAxis ? availableLogicalWidth() : availableLogicalHeightForPercentageComputation();
177 }
178
179 LayoutUnit RenderGrid::computeTrackBasedLogicalHeight() const
180 {
181     LayoutUnit logicalHeight;
182
183     auto& allRows = m_trackSizingAlgorithm.tracks(ForRows);
184     for (const auto& row : allRows)
185         logicalHeight += row.baseSize();
186
187     logicalHeight += guttersSize(m_grid, ForRows, 0, allRows.size(), availableSpaceForGutters(ForRows));
188
189     return logicalHeight;
190 }
191
192 void RenderGrid::computeTrackSizesForDefiniteSize(GridTrackSizingDirection direction, LayoutUnit availableSpace)
193 {
194     LayoutUnit totalGuttersSize = guttersSize(m_grid, direction, 0, m_grid.numTracks(direction), availableSpace);
195     LayoutUnit freeSpace = availableSpace - totalGuttersSize;
196
197     m_trackSizingAlgorithm.setup(direction, numTracks(direction, m_grid), TrackSizing, availableSpace, freeSpace);
198     m_trackSizingAlgorithm.run();
199
200     ASSERT(m_trackSizingAlgorithm.tracksAreWiderThanMinTrackBreadth());
201 }
202
203 void RenderGrid::repeatTracksSizingIfNeeded(LayoutUnit availableSpaceForColumns, LayoutUnit availableSpaceForRows)
204 {
205     // In orthogonal flow cases column track's size is determined by using the computed
206     // row track's size, which it was estimated during the first cycle of the sizing
207     // algorithm. Hence we need to repeat computeUsedBreadthOfGridTracks for both,
208     // columns and rows, to determine the final values.
209     // TODO (lajava): orthogonal flows is just one of the cases which may require
210     // a new cycle of the sizing algorithm; there may be more. In addition, not all the
211     // cases with orthogonal flows require this extra cycle; we need a more specific
212     // condition to detect whether child's min-content contribution has changed or not.
213     if (m_grid.hasAnyOrthogonalGridItem()) {
214         computeTrackSizesForDefiniteSize(ForColumns, availableSpaceForColumns);
215         computeTrackSizesForDefiniteSize(ForRows, availableSpaceForRows);
216     }
217 }
218
219 bool RenderGrid::canPerformSimplifiedLayout() const
220 {
221     // We cannot perform a simplified layout if we need to position the items and we have some
222     // positioned items to be laid out.
223     if (m_grid.needsItemsPlacement() && posChildNeedsLayout())
224         return false;
225
226     return RenderBlock::canPerformSimplifiedLayout();
227 }
228
229 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
230 {
231     ASSERT(needsLayout());
232
233     if (!relayoutChildren && simplifiedLayout())
234         return;
235
236     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
237     {
238         LayoutStateMaintainer statePusher(*this, locationOffset(), hasTransform() || hasReflection() || style().isFlippedBlocksWritingMode());
239
240         preparePaginationBeforeBlockLayout(relayoutChildren);
241
242         LayoutSize previousSize = size();
243         // FIXME: We should use RenderBlock::hasDefiniteLogicalHeight() but it does not work for positioned stuff.
244         // FIXME: Consider caching the hasDefiniteLogicalHeight value throughout the layout.
245         bool hasDefiniteLogicalHeight = hasOverrideLogicalContentHeight() || computeContentLogicalHeight(MainOrPreferredSize, style().logicalHeight(), std::nullopt);
246
247         // We need to clear both own and containingBlock override sizes of orthogonal items to ensure we get the
248         // same result when grid's intrinsic size is computed again in the updateLogicalWidth call bellow.
249         if (sizesLogicalWidthToFitContent(MaxSize) || style().logicalWidth().isIntrinsicOrAuto()) {
250             for (auto* child = firstChildBox(); child; child = child->nextSiblingBox()) {
251                 if (child->isOutOfFlowPositioned() || !GridLayoutFunctions::isOrthogonalChild(*this, *child))
252                     continue;
253                 child->clearOverrideSize();
254                 child->clearContainingBlockOverrideSize();
255                 child->setNeedsLayout();
256                 child->layoutIfNeeded();
257             }
258         }
259
260         setLogicalHeight(0);
261         updateLogicalWidth();
262
263         // Fieldsets need to find their legend and position it inside the border of the object.
264         // The legend then gets skipped during normal layout. The same is true for ruby text.
265         // It doesn't get included in the normal layout process but is instead skipped.
266         layoutExcludedChildren(relayoutChildren);
267
268         LayoutUnit availableSpaceForColumns = availableLogicalWidth();
269         placeItemsOnGrid(m_grid, availableSpaceForColumns);
270
271         // At this point the logical width is always definite as the above call to updateLogicalWidth()
272         // properly resolves intrinsic sizes. We cannot do the same for heights though because many code
273         // paths inside updateLogicalHeight() require a previous call to setLogicalHeight() to resolve
274         // heights properly (like for positioned items for example).
275         computeTrackSizesForDefiniteSize(ForColumns, availableSpaceForColumns);
276
277         if (!hasDefiniteLogicalHeight) {
278             m_minContentHeight = LayoutUnit();
279             m_maxContentHeight = LayoutUnit();
280             computeTrackSizesForIndefiniteSize(m_trackSizingAlgorithm, ForRows, m_grid, *m_minContentHeight, *m_maxContentHeight);
281             // FIXME: This should be really added to the intrinsic height in RenderBox::computeContentAndScrollbarLogicalHeightUsing().
282             // Remove this when that is fixed.
283             ASSERT(m_minContentHeight);
284             ASSERT(m_maxContentHeight);
285             LayoutUnit scrollbarHeight = scrollbarLogicalHeight();
286             *m_minContentHeight += scrollbarHeight;
287             *m_maxContentHeight += scrollbarHeight;
288         } else
289             computeTrackSizesForDefiniteSize(ForRows, availableLogicalHeight(ExcludeMarginBorderPadding));
290         LayoutUnit trackBasedLogicalHeight = computeTrackBasedLogicalHeight() + borderAndPaddingLogicalHeight() + scrollbarLogicalHeight();
291         setLogicalHeight(trackBasedLogicalHeight);
292
293         LayoutUnit oldClientAfterEdge = clientLogicalBottom();
294         updateLogicalHeight();
295
296         // Once grid's indefinite height is resolved, we can compute the
297         // available free space for Content Alignment.
298         if (!hasDefiniteLogicalHeight)
299             m_trackSizingAlgorithm.setFreeSpace(ForRows, logicalHeight() - trackBasedLogicalHeight);
300
301         // 3- If the min-content contribution of any grid items have changed based on the row
302         // sizes calculated in step 2, steps 1 and 2 are repeated with the new min-content
303         // contribution (once only).
304         repeatTracksSizingIfNeeded(availableSpaceForColumns, contentLogicalHeight());
305
306         // Grid container should have the minimum height of a line if it's editable. That does not affect track sizing though.
307         if (hasLineIfEmpty()) {
308             LayoutUnit minHeightForEmptyLine = borderAndPaddingLogicalHeight()
309                 + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes)
310                 + scrollbarLogicalHeight();
311             setLogicalHeight(std::max(logicalHeight(), minHeightForEmptyLine));
312         }
313
314         layoutGridItems();
315         m_trackSizingAlgorithm.reset();
316
317         if (size() != previousSize)
318             relayoutChildren = true;
319
320         m_outOfFlowItemColumn.clear();
321         m_outOfFlowItemRow.clear();
322
323         layoutPositionedObjects(relayoutChildren || isDocumentElementRenderer());
324
325         computeOverflow(oldClientAfterEdge);
326     }
327
328     updateLayerTransform();
329
330     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
331     // we overflow or not.
332     updateScrollInfoAfterLayout();
333
334     repainter.repaintAfterLayout();
335
336     clearNeedsLayout();
337 }
338
339 LayoutUnit RenderGrid::gridGap(GridTrackSizingDirection direction, std::optional<LayoutUnit> availableSize) const
340 {
341     const Length& gap = direction == ForColumns ? style().gridColumnGap() : style().gridRowGap();
342     return valueForLength(gap, availableSize.value_or(0));
343 }
344
345 LayoutUnit RenderGrid::gridGap(GridTrackSizingDirection direction) const
346 {
347     return gridGap(direction, availableSpaceForGutters(direction));
348 }
349
350 LayoutUnit RenderGrid::gridItemOffset(GridTrackSizingDirection direction) const
351 {
352     return direction == ForRows ? m_offsetBetweenRows : m_offsetBetweenColumns;
353 }
354
355 LayoutUnit RenderGrid::guttersSize(const Grid& grid, GridTrackSizingDirection direction, unsigned startLine, unsigned span, std::optional<LayoutUnit> availableSize) const
356 {
357     if (span <= 1)
358         return { };
359
360     LayoutUnit gap = gridGap(direction, availableSize);
361
362     // Fast path, no collapsing tracks.
363     if (!grid.hasAutoRepeatEmptyTracks(direction))
364         return gap * (span - 1);
365
366     // If there are collapsing tracks we need to be sure that gutters are properly collapsed. Apart
367     // from that, if we have a collapsed track in the edges of the span we're considering, we need
368     // to move forward (or backwards) in order to know whether the collapsed tracks reach the end of
369     // the grid (so the gap becomes 0) or there is a non empty track before that.
370
371     LayoutUnit gapAccumulator;
372     unsigned endLine = startLine + span;
373
374     for (unsigned line = startLine; line < endLine - 1; ++line) {
375         if (!grid.isEmptyAutoRepeatTrack(direction, line))
376             gapAccumulator += gap;
377     }
378
379     // The above loop adds one extra gap for trailing collapsed tracks.
380     if (gapAccumulator && grid.isEmptyAutoRepeatTrack(direction, endLine - 1)) {
381         ASSERT(gapAccumulator >= gap);
382         gapAccumulator -= gap;
383     }
384
385     // If the startLine is the start line of a collapsed track we need to go backwards till we reach
386     // a non collapsed track. If we find a non collapsed track we need to add that gap.
387     if (startLine && grid.isEmptyAutoRepeatTrack(direction, startLine)) {
388         unsigned nonEmptyTracksBeforeStartLine = startLine;
389         auto begin = grid.autoRepeatEmptyTracks(direction)->begin();
390         for (auto it = begin; *it != startLine; ++it) {
391             ASSERT(nonEmptyTracksBeforeStartLine);
392             --nonEmptyTracksBeforeStartLine;
393         }
394         if (nonEmptyTracksBeforeStartLine)
395             gapAccumulator += gap;
396     }
397
398     // If the endLine is the end line of a collapsed track we need to go forward till we reach a non
399     // collapsed track. If we find a non collapsed track we need to add that gap.
400     if (grid.isEmptyAutoRepeatTrack(direction, endLine - 1)) {
401         unsigned nonEmptyTracksAfterEndLine = grid.numTracks(direction) - endLine;
402         auto currentEmptyTrack = grid.autoRepeatEmptyTracks(direction)->find(endLine - 1);
403         auto endEmptyTrack = grid.autoRepeatEmptyTracks(direction)->end();
404         // HashSet iterators do not implement operator- so we have to manually iterate to know the number of remaining empty tracks.
405         for (auto it = ++currentEmptyTrack; it != endEmptyTrack; ++it) {
406             ASSERT(nonEmptyTracksAfterEndLine >= 1);
407             --nonEmptyTracksAfterEndLine;
408         }
409         if (nonEmptyTracksAfterEndLine)
410             gapAccumulator += gap;
411     }
412
413     return gapAccumulator;
414 }
415
416 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
417 {
418     LayoutUnit childMinWidth;
419     LayoutUnit childMaxWidth;
420     bool hadExcludedChildren = computePreferredWidthsForExcludedChildren(childMinWidth, childMaxWidth);
421
422     Grid grid(const_cast<RenderGrid&>(*this));
423     placeItemsOnGrid(grid, std::nullopt);
424
425     GridTrackSizingAlgorithm algorithm(this, grid);
426     computeTrackSizesForIndefiniteSize(algorithm, ForColumns, grid, minLogicalWidth, maxLogicalWidth);
427
428     if (hadExcludedChildren) {
429         minLogicalWidth = std::max(minLogicalWidth, childMinWidth);
430         maxLogicalWidth = std::max(maxLogicalWidth, childMaxWidth);
431     }
432
433     LayoutUnit scrollbarWidth = intrinsicScrollbarLogicalWidth();
434     minLogicalWidth += scrollbarWidth;
435     maxLogicalWidth += scrollbarWidth;
436 }
437
438 void RenderGrid::computeTrackSizesForIndefiniteSize(GridTrackSizingAlgorithm& algorithm, GridTrackSizingDirection direction, Grid& grid, LayoutUnit& minIntrinsicSize, LayoutUnit& maxIntrinsicSize) const
439 {
440     algorithm.setup(direction, numTracks(direction, grid), IntrinsicSizeComputation, std::nullopt, std::nullopt);
441     algorithm.run();
442
443     size_t numberOfTracks = algorithm.tracks(direction).size();
444     LayoutUnit totalGuttersSize = guttersSize(grid, direction, 0, numberOfTracks, std::nullopt);
445
446     minIntrinsicSize = algorithm.minContentSize() + totalGuttersSize;
447     maxIntrinsicSize = algorithm.maxContentSize() + totalGuttersSize;
448
449     ASSERT(algorithm.tracksAreWiderThanMinTrackBreadth());
450 }
451
452 std::optional<LayoutUnit> RenderGrid::computeIntrinsicLogicalContentHeightUsing(Length logicalHeightLength, std::optional<LayoutUnit> intrinsicLogicalHeight, LayoutUnit borderAndPadding) const
453 {
454     if (!intrinsicLogicalHeight)
455         return std::nullopt;
456
457     if (logicalHeightLength.isMinContent())
458         return m_minContentHeight;
459
460     if (logicalHeightLength.isMaxContent())
461         return m_maxContentHeight;
462
463     if (logicalHeightLength.isFitContent()) {
464         LayoutUnit fillAvailableExtent = containingBlock()->availableLogicalHeight(ExcludeMarginBorderPadding);
465         return std::min(m_maxContentHeight.value_or(0), std::max(m_minContentHeight.value_or(0), fillAvailableExtent));
466     }
467
468     if (logicalHeightLength.isFillAvailable())
469         return containingBlock()->availableLogicalHeight(ExcludeMarginBorderPadding) - borderAndPadding;
470     ASSERT_NOT_REACHED();
471     return std::nullopt;
472 }
473
474 unsigned RenderGrid::computeAutoRepeatTracksCount(GridTrackSizingDirection direction, std::optional<LayoutUnit> availableSize) const
475 {
476     ASSERT(!availableSize || availableSize.value() != -1);
477     bool isRowAxis = direction == ForColumns;
478     const auto& autoRepeatTracks = isRowAxis ? style().gridAutoRepeatColumns() : style().gridAutoRepeatRows();
479     unsigned autoRepeatTrackListLength = autoRepeatTracks.size();
480
481     if (!autoRepeatTrackListLength)
482         return 0;
483
484     if (!isRowAxis && !availableSize) {
485         const Length& maxLength = style().logicalMaxHeight();
486         if (!maxLength.isUndefined()) {
487             availableSize = computeContentLogicalHeight(MaxSize, maxLength, std::nullopt);
488             if (availableSize)
489                 availableSize = constrainContentBoxLogicalHeightByMinMax(availableSize.value(), std::nullopt);
490         }
491     }
492
493     bool needsToFulfillMinimumSize = false;
494     if (!availableSize) {
495         const Length& minSize = isRowAxis ? style().logicalMinWidth() : style().logicalMinHeight();
496         if (!minSize.isSpecified())
497             return autoRepeatTrackListLength;
498
499         LayoutUnit containingBlockAvailableSize = isRowAxis ? containingBlockLogicalWidthForContent() : containingBlockLogicalHeightForContent(ExcludeMarginBorderPadding);
500         availableSize = valueForLength(minSize, containingBlockAvailableSize);
501         needsToFulfillMinimumSize = true;
502     }
503
504     LayoutUnit autoRepeatTracksSize;
505     for (auto& autoTrackSize : autoRepeatTracks) {
506         ASSERT(autoTrackSize.minTrackBreadth().isLength());
507         ASSERT(!autoTrackSize.minTrackBreadth().isFlex());
508         bool hasDefiniteMaxTrackSizingFunction = autoTrackSize.maxTrackBreadth().isLength() && !autoTrackSize.maxTrackBreadth().isContentSized();
509         auto trackLength = hasDefiniteMaxTrackSizingFunction ? autoTrackSize.maxTrackBreadth().length() : autoTrackSize.minTrackBreadth().length();
510         autoRepeatTracksSize += valueForLength(trackLength, availableSize.value());
511     }
512     // For the purpose of finding the number of auto-repeated tracks, the UA must floor the track size to a UA-specified
513     // value to avoid division by zero. It is suggested that this floor be 1px.
514     autoRepeatTracksSize = std::max<LayoutUnit>(LayoutUnit(1), autoRepeatTracksSize);
515
516     // There will be always at least 1 auto-repeat track, so take it already into account when computing the total track size.
517     LayoutUnit tracksSize = autoRepeatTracksSize;
518     auto& trackSizes = isRowAxis ? style().gridColumns() : style().gridRows();
519
520     for (const auto& track : trackSizes) {
521         bool hasDefiniteMaxTrackBreadth = track.maxTrackBreadth().isLength() && !track.maxTrackBreadth().isContentSized();
522         ASSERT(hasDefiniteMaxTrackBreadth || (track.minTrackBreadth().isLength() && !track.minTrackBreadth().isContentSized()));
523         tracksSize += valueForLength(hasDefiniteMaxTrackBreadth ? track.maxTrackBreadth().length() : track.minTrackBreadth().length(), availableSize.value());
524     }
525
526     // Add gutters as if there where only 1 auto repeat track. Gaps between auto repeat tracks will be added later when
527     // computing the repetitions.
528     LayoutUnit gapSize = gridGap(direction, availableSize);
529     tracksSize += gapSize * trackSizes.size();
530
531     LayoutUnit freeSpace = availableSize.value() - tracksSize;
532     if (freeSpace <= 0)
533         return autoRepeatTrackListLength;
534
535     unsigned repetitions = 1 + (freeSpace / (autoRepeatTracksSize + gapSize)).toInt();
536
537     // Provided the grid container does not have a definite size or max-size in the relevant axis,
538     // if the min size is definite then the number of repetitions is the largest possible positive
539     // integer that fulfills that minimum requirement.
540     if (needsToFulfillMinimumSize)
541         ++repetitions;
542
543     return repetitions * autoRepeatTrackListLength;
544 }
545
546
547 std::unique_ptr<OrderedTrackIndexSet> RenderGrid::computeEmptyTracksForAutoRepeat(Grid& grid, GridTrackSizingDirection direction) const
548 {
549     bool isRowAxis = direction == ForColumns;
550     if ((isRowAxis && style().gridAutoRepeatColumnsType() != AutoFit)
551         || (!isRowAxis && style().gridAutoRepeatRowsType() != AutoFit))
552         return nullptr;
553
554     std::unique_ptr<OrderedTrackIndexSet> emptyTrackIndexes;
555     unsigned insertionPoint = isRowAxis ? style().gridAutoRepeatColumnsInsertionPoint() : style().gridAutoRepeatRowsInsertionPoint();
556     unsigned firstAutoRepeatTrack = insertionPoint + std::abs(grid.smallestTrackStart(direction));
557     unsigned lastAutoRepeatTrack = firstAutoRepeatTrack + grid.autoRepeatTracks(direction);
558
559     if (!grid.hasGridItems()) {
560         emptyTrackIndexes = std::make_unique<OrderedTrackIndexSet>();
561         for (unsigned trackIndex = firstAutoRepeatTrack; trackIndex < lastAutoRepeatTrack; ++trackIndex)
562             emptyTrackIndexes->add(trackIndex);
563     } else {
564         for (unsigned trackIndex = firstAutoRepeatTrack; trackIndex < lastAutoRepeatTrack; ++trackIndex) {
565             GridIterator iterator(grid, direction, trackIndex);
566             if (!iterator.nextGridItem()) {
567                 if (!emptyTrackIndexes)
568                     emptyTrackIndexes = std::make_unique<OrderedTrackIndexSet>();
569                 emptyTrackIndexes->add(trackIndex);
570             }
571         }
572     }
573     return emptyTrackIndexes;
574 }
575
576 unsigned RenderGrid::clampAutoRepeatTracks(GridTrackSizingDirection direction, unsigned autoRepeatTracks) const
577 {
578     if (!autoRepeatTracks)
579         return 0;
580
581     unsigned insertionPoint = direction == ForColumns ? style().gridAutoRepeatColumnsInsertionPoint() : style().gridAutoRepeatRowsInsertionPoint();
582     unsigned maxTracks = static_cast<unsigned>(GridPosition::max());
583
584     if (!insertionPoint)
585         return std::min(autoRepeatTracks, maxTracks);
586
587     if (insertionPoint >= maxTracks)
588         return 0;
589
590     return std::min(autoRepeatTracks, maxTracks - insertionPoint);
591 }
592
593 // FIXME): We shouldn't have to pass the available logical width as argument. The problem is that
594 // availableLogicalWidth() does always return a value even if we cannot resolve it like when
595 // computing the intrinsic size (preferred widths). That's why we pass the responsibility to the
596 // caller who does know whether the available logical width is indefinite or not.
597 void RenderGrid::placeItemsOnGrid(Grid& grid, std::optional<LayoutUnit> availableSpace) const
598 {
599     unsigned autoRepeatColumns = computeAutoRepeatTracksCount(ForColumns, availableSpace);
600     unsigned autoRepeatRows = computeAutoRepeatTracksCount(ForRows, availableLogicalHeightForPercentageComputation());
601
602     autoRepeatRows = clampAutoRepeatTracks(ForRows, autoRepeatRows);
603     autoRepeatColumns = clampAutoRepeatTracks(ForColumns, autoRepeatColumns);
604
605     if (autoRepeatColumns != grid.autoRepeatTracks(ForColumns) || autoRepeatRows != grid.autoRepeatTracks(ForRows)) {
606         grid.setNeedsItemsPlacement(true);
607         grid.setAutoRepeatTracks(autoRepeatRows, autoRepeatColumns);
608     }
609
610     if (!grid.needsItemsPlacement())
611         return;
612
613     ASSERT(!grid.hasGridItems());
614     populateExplicitGridAndOrderIterator(grid);
615
616     Vector<RenderBox*> autoMajorAxisAutoGridItems;
617     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
618     bool hasAnyOrthogonalGridItem = false;
619     for (auto* child = grid.orderIterator().first(); child; child = grid.orderIterator().next()) {
620         if (grid.orderIterator().shouldSkipChild(*child))
621             continue;
622
623         hasAnyOrthogonalGridItem = hasAnyOrthogonalGridItem || GridLayoutFunctions::isOrthogonalChild(*this, *child);
624
625         GridArea area = grid.gridItemArea(*child);
626         if (!area.rows.isIndefinite())
627             area.rows.translate(std::abs(grid.smallestTrackStart(ForRows)));
628         if (!area.columns.isIndefinite())
629             area.columns.translate(std::abs(grid.smallestTrackStart(ForColumns)));
630
631         if (area.rows.isIndefinite() || area.columns.isIndefinite()) {
632             grid.setGridItemArea(*child, area);
633             bool majorAxisDirectionIsForColumns = autoPlacementMajorAxisDirection() == ForColumns;
634             if ((majorAxisDirectionIsForColumns && area.columns.isIndefinite())
635                 || (!majorAxisDirectionIsForColumns && area.rows.isIndefinite()))
636                 autoMajorAxisAutoGridItems.append(child);
637             else
638                 specifiedMajorAxisAutoGridItems.append(child);
639             continue;
640         }
641         grid.insert(*child, { area.rows, area.columns });
642     }
643     grid.setHasAnyOrthogonalGridItem(hasAnyOrthogonalGridItem);
644
645 #if ENABLE(ASSERT)
646     if (grid.hasGridItems()) {
647         ASSERT(grid.numTracks(ForRows) >= GridPositionsResolver::explicitGridRowCount(style(), grid.autoRepeatTracks(ForRows)));
648         ASSERT(grid.numTracks(ForColumns) >= GridPositionsResolver::explicitGridColumnCount(style(), grid.autoRepeatTracks(ForColumns)));
649     }
650 #endif
651
652     placeSpecifiedMajorAxisItemsOnGrid(grid, specifiedMajorAxisAutoGridItems);
653     placeAutoMajorAxisItemsOnGrid(grid, autoMajorAxisAutoGridItems);
654
655     // Compute collapsible tracks for auto-fit.
656     grid.setAutoRepeatEmptyColumns(computeEmptyTracksForAutoRepeat(grid, ForColumns));
657     grid.setAutoRepeatEmptyRows(computeEmptyTracksForAutoRepeat(grid, ForRows));
658
659     grid.setNeedsItemsPlacement(false);
660
661 #if ENABLE(ASSERT)
662     for (auto* child = grid.orderIterator().first(); child; child = grid.orderIterator().next()) {
663         if (grid.orderIterator().shouldSkipChild(*child))
664             continue;
665
666         GridArea area = grid.gridItemArea(*child);
667         ASSERT(area.rows.isTranslatedDefinite() && area.columns.isTranslatedDefinite());
668     }
669 #endif
670 }
671
672 void RenderGrid::populateExplicitGridAndOrderIterator(Grid& grid) const
673 {
674     OrderIteratorPopulator populator(grid.orderIterator());
675     int smallestRowStart = 0;
676     int smallestColumnStart = 0;
677     unsigned autoRepeatRows = grid.autoRepeatTracks(ForRows);
678     unsigned autoRepeatColumns = grid.autoRepeatTracks(ForColumns);
679     unsigned maximumRowIndex = GridPositionsResolver::explicitGridRowCount(style(), autoRepeatRows);
680     unsigned maximumColumnIndex = GridPositionsResolver::explicitGridColumnCount(style(), autoRepeatColumns);
681
682     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
683         if (!populator.collectChild(*child))
684             continue;
685         
686         GridSpan rowPositions = GridPositionsResolver::resolveGridPositionsFromStyle(style(), *child, ForRows, autoRepeatRows);
687         if (!rowPositions.isIndefinite()) {
688             smallestRowStart = std::min(smallestRowStart, rowPositions.untranslatedStartLine());
689             maximumRowIndex = std::max<int>(maximumRowIndex, rowPositions.untranslatedEndLine());
690         } else {
691             // Grow the grid for items with a definite row span, getting the largest such span.
692             unsigned spanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), *child, ForRows);
693             maximumRowIndex = std::max(maximumRowIndex, spanSize);
694         }
695
696         GridSpan columnPositions = GridPositionsResolver::resolveGridPositionsFromStyle(style(), *child, ForColumns, autoRepeatColumns);
697         if (!columnPositions.isIndefinite()) {
698             smallestColumnStart = std::min(smallestColumnStart, columnPositions.untranslatedStartLine());
699             maximumColumnIndex = std::max<int>(maximumColumnIndex, columnPositions.untranslatedEndLine());
700         } else {
701             // Grow the grid for items with a definite column span, getting the largest such span.
702             unsigned spanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), *child, ForColumns);
703             maximumColumnIndex = std::max(maximumColumnIndex, spanSize);
704         }
705
706         grid.setGridItemArea(*child, { rowPositions, columnPositions });
707     }
708
709     grid.setSmallestTracksStart(smallestRowStart, smallestColumnStart);
710     grid.ensureGridSize(maximumRowIndex + std::abs(smallestRowStart), maximumColumnIndex + std::abs(smallestColumnStart));
711 }
712
713 std::unique_ptr<GridArea> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(Grid& grid, const RenderBox& gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
714 {
715     GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
716     const unsigned endOfCrossDirection = grid.numTracks(crossDirection);
717     unsigned crossDirectionSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), gridItem, crossDirection);
718     GridSpan crossDirectionPositions = GridSpan::translatedDefiniteGridSpan(endOfCrossDirection, endOfCrossDirection + crossDirectionSpanSize);
719     return std::make_unique<GridArea>(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions);
720 }
721
722 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(Grid& grid, const Vector<RenderBox*>& autoGridItems) const
723 {
724     bool isForColumns = autoPlacementMajorAxisDirection() == ForColumns;
725     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
726
727     // Mapping between the major axis tracks (rows or columns) and the last auto-placed item's position inserted on
728     // that track. This is needed to implement "sparse" packing for items locked to a given track.
729     // See http://dev.w3.org/csswg/css-grid/#auto-placement-algorithm
730     HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> minorAxisCursors;
731
732     for (auto& autoGridItem : autoGridItems) {
733         GridSpan majorAxisPositions = grid.gridItemSpan(*autoGridItem, autoPlacementMajorAxisDirection());
734         ASSERT(majorAxisPositions.isTranslatedDefinite());
735         ASSERT(grid.gridItemSpan(*autoGridItem, autoPlacementMinorAxisDirection()).isIndefinite());
736         unsigned minorAxisSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), *autoGridItem, autoPlacementMinorAxisDirection());
737         unsigned majorAxisInitialPosition = majorAxisPositions.startLine();
738
739         GridIterator iterator(grid, autoPlacementMajorAxisDirection(), majorAxisPositions.startLine(), isGridAutoFlowDense ? 0 : minorAxisCursors.get(majorAxisInitialPosition));
740         std::unique_ptr<GridArea> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisSpanSize);
741         if (!emptyGridArea)
742             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(grid, *autoGridItem, autoPlacementMajorAxisDirection(), majorAxisPositions);
743
744         grid.insert(*autoGridItem, *emptyGridArea);
745
746         if (!isGridAutoFlowDense)
747             minorAxisCursors.set(majorAxisInitialPosition, isForColumns ? emptyGridArea->rows.startLine() : emptyGridArea->columns.startLine());
748     }
749 }
750
751 void RenderGrid::placeAutoMajorAxisItemsOnGrid(Grid& grid, const Vector<RenderBox*>& autoGridItems) const
752 {
753     AutoPlacementCursor autoPlacementCursor = {0, 0};
754     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
755
756     for (auto& autoGridItem : autoGridItems) {
757         placeAutoMajorAxisItemOnGrid(grid, *autoGridItem, autoPlacementCursor);
758
759         if (isGridAutoFlowDense) {
760             autoPlacementCursor.first = 0;
761             autoPlacementCursor.second = 0;
762         }
763     }
764 }
765
766 void RenderGrid::placeAutoMajorAxisItemOnGrid(Grid& grid, RenderBox& gridItem, AutoPlacementCursor& autoPlacementCursor) const
767 {
768     ASSERT(grid.gridItemSpan(gridItem, autoPlacementMajorAxisDirection()).isIndefinite());
769     unsigned majorAxisSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), gridItem, autoPlacementMajorAxisDirection());
770
771     const unsigned endOfMajorAxis = grid.numTracks(autoPlacementMajorAxisDirection());
772     unsigned majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
773     unsigned minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
774
775     std::unique_ptr<GridArea> emptyGridArea;
776     GridSpan minorAxisPositions = grid.gridItemSpan(gridItem, autoPlacementMinorAxisDirection());
777     if (minorAxisPositions.isTranslatedDefinite()) {
778         // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
779         if (minorAxisPositions.startLine() < minorAxisAutoPlacementCursor)
780             majorAxisAutoPlacementCursor++;
781
782         if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
783             GridIterator iterator(grid, autoPlacementMinorAxisDirection(), minorAxisPositions.startLine(), majorAxisAutoPlacementCursor);
784             emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions.integerSpan(), majorAxisSpanSize);
785         }
786
787         if (!emptyGridArea)
788             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(grid, gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
789     } else {
790         unsigned minorAxisSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), gridItem, autoPlacementMinorAxisDirection());
791
792         for (unsigned majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
793             GridIterator iterator(grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
794             emptyGridArea = iterator.nextEmptyGridArea(majorAxisSpanSize, minorAxisSpanSize);
795
796             if (emptyGridArea) {
797                 // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
798                 unsigned minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.endLine() : emptyGridArea->rows.endLine();
799                 const unsigned endOfMinorAxis = grid.numTracks(autoPlacementMinorAxisDirection());
800                 if (minorAxisFinalPositionIndex <= endOfMinorAxis)
801                     break;
802
803                 // Discard empty grid area as it does not fit in the minor axis direction.
804                 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
805                 emptyGridArea = nullptr;
806             }
807
808             // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
809             minorAxisAutoPlacementCursor = 0;
810         }
811
812         if (!emptyGridArea)
813             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(grid, gridItem, autoPlacementMinorAxisDirection(), GridSpan::translatedDefiniteGridSpan(0, minorAxisSpanSize));
814     }
815
816     grid.insert(gridItem, *emptyGridArea);
817     autoPlacementCursor.first = emptyGridArea->rows.startLine();
818     autoPlacementCursor.second = emptyGridArea->columns.startLine();
819 }
820
821 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
822 {
823     return style().isGridAutoFlowDirectionColumn() ? ForColumns : ForRows;
824 }
825
826 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
827 {
828     return style().isGridAutoFlowDirectionColumn() ? ForRows : ForColumns;
829 }
830
831 void RenderGrid::dirtyGrid()
832 {
833     if (m_grid.needsItemsPlacement())
834         return;
835
836     m_grid.setNeedsItemsPlacement(true);
837 }
838
839 Vector<LayoutUnit> RenderGrid::trackSizesForComputedStyle(GridTrackSizingDirection direction) const
840 {
841     bool isRowAxis = direction == ForColumns;
842     auto& positions = isRowAxis ? m_columnPositions : m_rowPositions;
843     size_t numPositions = positions.size();
844     LayoutUnit offsetBetweenTracks = isRowAxis ? m_offsetBetweenColumns : m_offsetBetweenRows;
845
846     Vector<LayoutUnit> tracks;
847     if (numPositions < 2)
848         return tracks;
849
850     ASSERT(!m_grid.needsItemsPlacement());
851     bool hasCollapsedTracks = m_grid.hasAutoRepeatEmptyTracks(direction);
852     LayoutUnit gap = !hasCollapsedTracks ? gridGap(direction) : LayoutUnit();
853     tracks.reserveCapacity(numPositions - 1);
854     for (size_t i = 0; i < numPositions - 2; ++i)
855         tracks.append(positions[i + 1] - positions[i] - offsetBetweenTracks - gap);
856     tracks.append(positions[numPositions - 1] - positions[numPositions - 2]);
857
858     if (!hasCollapsedTracks)
859         return tracks;
860
861     size_t remainingEmptyTracks = m_grid.autoRepeatEmptyTracks(direction)->size();
862     size_t lastLine = tracks.size();
863     gap = gridGap(direction);
864     for (size_t i = 1; i < lastLine; ++i) {
865         if (m_grid.isEmptyAutoRepeatTrack(direction, i - 1))
866             --remainingEmptyTracks;
867         else {
868             // Remove the gap between consecutive non empty tracks. Remove it also just once for an
869             // arbitrary number of empty tracks between two non empty ones.
870             bool allRemainingTracksAreEmpty = remainingEmptyTracks == (lastLine - i);
871             if (!allRemainingTracksAreEmpty || !m_grid.isEmptyAutoRepeatTrack(direction, i))
872                 tracks[i - 1] -= gap;
873         }
874     }
875
876     return tracks;
877 }
878
879 static const StyleContentAlignmentData& contentAlignmentNormalBehaviorGrid()
880 {
881     static const StyleContentAlignmentData normalBehavior = {ContentPositionNormal, ContentDistributionStretch};
882     return normalBehavior;
883 }
884
885 void RenderGrid::layoutGridItems()
886 {
887     populateGridPositionsForDirection(ForColumns);
888     populateGridPositionsForDirection(ForRows);
889
890     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
891         
892         if (m_grid.orderIterator().shouldSkipChild(*child)) {
893             if (child->isOutOfFlowPositioned())
894                 prepareChildForPositionedLayout(*child);
895             continue;
896         }
897
898         // Because the grid area cannot be styled, we don't need to adjust
899         // the grid breadth to account for 'box-sizing'.
900         std::optional<LayoutUnit> oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
901         std::optional<LayoutUnit> oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
902
903         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChildIncludingAlignmentOffsets(*child, ForColumns);
904         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChildIncludingAlignmentOffsets(*child, ForRows);
905         if (!oldOverrideContainingBlockContentLogicalWidth || oldOverrideContainingBlockContentLogicalWidth.value() != overrideContainingBlockContentLogicalWidth
906             || ((!oldOverrideContainingBlockContentLogicalHeight || oldOverrideContainingBlockContentLogicalHeight.value() != overrideContainingBlockContentLogicalHeight)
907                 && child->hasRelativeLogicalHeight()))
908             child->setNeedsLayout(MarkOnlyThis);
909
910         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
911         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
912
913         LayoutRect oldChildRect = child->frameRect();
914
915         // Stretching logic might force a child layout, so we need to run it before the layoutIfNeeded
916         // call to avoid unnecessary relayouts. This might imply that child margins, needed to correctly
917         // determine the available space before stretching, are not set yet.
918         applyStretchAlignmentToChildIfNeeded(*child);
919
920         child->layoutIfNeeded();
921
922         // We need pending layouts to be done in order to compute auto-margins properly.
923         updateAutoMarginsInColumnAxisIfNeeded(*child);
924         updateAutoMarginsInRowAxisIfNeeded(*child);
925
926         child->setLogicalLocation(findChildLogicalPosition(*child));
927
928         // If the child moved, we have to repaint it as well as any floating/positioned
929         // descendants. An exception is if we need a layout. In this case, we know we're going to
930         // repaint ourselves (and the child) anyway.
931         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
932             child->repaintDuringLayoutIfMoved(oldChildRect);
933     }
934 }
935
936 void RenderGrid::prepareChildForPositionedLayout(RenderBox& child)
937 {
938     ASSERT(child.isOutOfFlowPositioned());
939     child.containingBlock()->insertPositionedObject(child);
940
941     RenderLayer* childLayer = child.layer();
942     childLayer->setStaticInlinePosition(borderStart());
943     childLayer->setStaticBlockPosition(borderBefore());
944 }
945
946 bool RenderGrid::hasStaticPositionForChild(const RenderBox& child, GridTrackSizingDirection direction) const
947 {
948     return direction == ForColumns ? child.style().hasStaticInlinePosition(isHorizontalWritingMode()) : child.style().hasStaticBlockPosition(isHorizontalWritingMode());
949 }
950
951 void RenderGrid::layoutPositionedObject(RenderBox& child, bool relayoutChildren, bool fixedPositionObjectsOnly)
952 {
953     LayoutUnit columnBreadth = gridAreaBreadthForOutOfFlowChild(child, ForColumns);
954     LayoutUnit rowBreadth = gridAreaBreadthForOutOfFlowChild(child, ForRows);
955
956     child.setOverrideContainingBlockContentLogicalWidth(columnBreadth);
957     child.setOverrideContainingBlockContentLogicalHeight(rowBreadth);
958
959     // Mark for layout as we're resetting the position before and we relay in generic layout logic
960     // for positioned items in order to get the offsets properly resolved.
961     child.setChildNeedsLayout(MarkOnlyThis);
962
963     RenderBlock::layoutPositionedObject(child, relayoutChildren, fixedPositionObjectsOnly);
964
965     if (child.isGridItem() || !hasStaticPositionForChild(child, ForColumns) || !hasStaticPositionForChild(child, ForRows))
966         child.setLogicalLocation(findChildLogicalPosition(child));
967 }
968
969 LayoutUnit RenderGrid::gridAreaBreadthForChildIncludingAlignmentOffsets(const RenderBox& child, GridTrackSizingDirection direction) const
970 {
971     // We need the cached value when available because Content Distribution alignment properties
972     // may have some influence in the final grid area breadth.
973     const auto& tracks = m_trackSizingAlgorithm.tracks(direction);
974     const auto& span = m_grid.gridItemSpan(child, direction);
975     const auto& linePositions = (direction == ForColumns) ? m_columnPositions : m_rowPositions;
976
977     LayoutUnit initialTrackPosition = linePositions[span.startLine()];
978     LayoutUnit finalTrackPosition = linePositions[span.endLine() - 1];
979
980     // Track Positions vector stores the 'start' grid line of each track, so we have to add last track's baseSize.
981     return finalTrackPosition - initialTrackPosition + tracks[span.endLine() - 1].baseSize();
982 }
983
984 void RenderGrid::populateGridPositionsForDirection(GridTrackSizingDirection direction)
985 {
986     // Since we add alignment offsets and track gutters, grid lines are not always adjacent. Hence we will have to
987     // assume from now on that we just store positions of the initial grid lines of each track,
988     // except the last one, which is the only one considered as a final grid line of a track.
989
990     // The grid container's frame elements (border, padding and <content-position> offset) are sensible to the
991     // inline-axis flow direction. However, column lines positions are 'direction' unaware. This simplification
992     // allows us to use the same indexes to identify the columns independently on the inline-axis direction.
993     bool isRowAxis = direction == ForColumns;
994     auto& tracks = m_trackSizingAlgorithm.tracks(direction);
995     unsigned numberOfTracks = tracks.size();
996     unsigned numberOfLines = numberOfTracks + 1;
997     unsigned lastLine = numberOfLines - 1;
998     bool hasCollapsedTracks = m_grid.hasAutoRepeatEmptyTracks(direction);
999     size_t numberOfCollapsedTracks = hasCollapsedTracks ? m_grid.autoRepeatEmptyTracks(direction)->size() : 0;
1000     ContentAlignmentData offset = computeContentPositionAndDistributionOffset(direction, m_trackSizingAlgorithm.freeSpace(direction).value(), numberOfTracks - numberOfCollapsedTracks);
1001     auto& positions = isRowAxis ? m_columnPositions : m_rowPositions;
1002     positions.resize(numberOfLines);
1003     auto borderAndPadding = isRowAxis ? borderAndPaddingLogicalLeft() : borderAndPaddingBefore();
1004     positions[0] = borderAndPadding + offset.positionOffset;
1005     if (numberOfLines > 1) {
1006         // If we have collapsed tracks we just ignore gaps here and add them later as we might not
1007         // compute the gap between two consecutive tracks without examining the surrounding ones.
1008         LayoutUnit gap = !hasCollapsedTracks ? gridGap(direction) : LayoutUnit();
1009         unsigned nextToLastLine = numberOfLines - 2;
1010         for (unsigned i = 0; i < nextToLastLine; ++i)
1011             positions[i + 1] = positions[i] + offset.distributionOffset + tracks[i].baseSize() + gap;
1012         positions[lastLine] = positions[nextToLastLine] + tracks[nextToLastLine].baseSize();
1013
1014         // Adjust collapsed gaps. Collapsed tracks cause the surrounding gutters to collapse (they
1015         // coincide exactly) except on the edges of the grid where they become 0.
1016         if (hasCollapsedTracks) {
1017             gap = gridGap(direction);
1018             unsigned remainingEmptyTracks = numberOfCollapsedTracks;
1019             LayoutUnit offsetAccumulator;
1020             LayoutUnit gapAccumulator;
1021             for (unsigned i = 1; i < lastLine; ++i) {
1022                 if (m_grid.isEmptyAutoRepeatTrack(direction, i - 1)) {
1023                     --remainingEmptyTracks;
1024                     offsetAccumulator += offset.distributionOffset;
1025                 } else {
1026                     // Add gap between consecutive non empty tracks. Add it also just once for an
1027                     // arbitrary number of empty tracks between two non empty ones.
1028                     bool allRemainingTracksAreEmpty = remainingEmptyTracks == (lastLine - i);
1029                     if (!allRemainingTracksAreEmpty || !m_grid.isEmptyAutoRepeatTrack(direction, i))
1030                         gapAccumulator += gap;
1031                 }
1032                 positions[i] += gapAccumulator - offsetAccumulator;
1033             }
1034             positions[lastLine] += gapAccumulator - offsetAccumulator;
1035         }
1036     }
1037     auto& offsetBetweenTracks = isRowAxis ? m_offsetBetweenColumns : m_offsetBetweenRows;
1038     offsetBetweenTracks = offset.distributionOffset;
1039 }
1040
1041 static LayoutUnit computeOverflowAlignmentOffset(OverflowAlignment overflow, LayoutUnit trackSize, LayoutUnit childSize)
1042 {
1043     LayoutUnit offset = trackSize - childSize;
1044     switch (overflow) {
1045     case OverflowAlignmentSafe:
1046         // If overflow is 'safe', we have to make sure we don't overflow the 'start'
1047         // edge (potentially cause some data loss as the overflow is unreachable).
1048         return std::max<LayoutUnit>(0, offset);
1049     case OverflowAlignmentUnsafe:
1050     case OverflowAlignmentDefault:
1051         // If we overflow our alignment container and overflow is 'true' (default), we
1052         // ignore the overflow and just return the value regardless (which may cause data
1053         // loss as we overflow the 'start' edge).
1054         return offset;
1055     }
1056
1057     ASSERT_NOT_REACHED();
1058     return 0;
1059 }
1060
1061 LayoutUnit RenderGrid::availableAlignmentSpaceForChildBeforeStretching(LayoutUnit gridAreaBreadthForChild, const RenderBox& child) const
1062 {
1063     // Because we want to avoid multiple layouts, stretching logic might be performed before
1064     // children are laid out, so we can't use the child cached values. Hence, we need to
1065     // compute margins in order to determine the available height before stretching.
1066     GridTrackSizingDirection childBlockFlowDirection = GridLayoutFunctions::flowAwareDirectionForChild(*this, child, ForRows);
1067     return gridAreaBreadthForChild - GridLayoutFunctions::marginLogicalSizeForChild(*this, childBlockFlowDirection, child);
1068 }
1069
1070 StyleSelfAlignmentData RenderGrid::alignSelfForChild(const RenderBox& child, const RenderStyle* gridStyle) const
1071 {
1072     if (!gridStyle)
1073         gridStyle = &style();
1074     return child.style().resolvedAlignSelf(gridStyle, selfAlignmentNormalBehavior(&child));
1075 }
1076
1077 StyleSelfAlignmentData RenderGrid::justifySelfForChild(const RenderBox& child, const RenderStyle* gridStyle) const
1078 {
1079     if (!gridStyle)
1080         gridStyle = &style();
1081     return child.style().resolvedJustifySelf(gridStyle, selfAlignmentNormalBehavior(&child));
1082 }
1083
1084 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1085 void RenderGrid::applyStretchAlignmentToChildIfNeeded(RenderBox& child)
1086 {
1087     ASSERT(child.overrideContainingBlockContentLogicalHeight());
1088
1089     // We clear height override values because we will decide now whether it's allowed or
1090     // not, evaluating the conditions which might have changed since the old values were set.
1091     child.clearOverrideLogicalContentHeight();
1092
1093     GridTrackSizingDirection childBlockDirection = GridLayoutFunctions::flowAwareDirectionForChild(*this, child, ForRows);
1094     bool blockFlowIsColumnAxis = childBlockDirection == ForRows;
1095     bool allowedToStretchChildBlockSize = blockFlowIsColumnAxis ? allowedToStretchChildAlongColumnAxis(child) : allowedToStretchChildAlongRowAxis(child);
1096     if (allowedToStretchChildBlockSize) {
1097         LayoutUnit stretchedLogicalHeight = availableAlignmentSpaceForChildBeforeStretching(GridLayoutFunctions::overrideContainingBlockContentSizeForChild(child, childBlockDirection).value(), child);
1098         LayoutUnit desiredLogicalHeight = child.constrainLogicalHeightByMinMax(stretchedLogicalHeight, LayoutUnit(-1));
1099         child.setOverrideLogicalContentHeight(desiredLogicalHeight - child.borderAndPaddingLogicalHeight());
1100         if (desiredLogicalHeight != child.logicalHeight()) {
1101             // FIXME: Can avoid laying out here in some cases. See https://webkit.org/b/87905.
1102             child.setLogicalHeight(LayoutUnit());
1103             child.setNeedsLayout();
1104         }
1105     }
1106 }
1107
1108 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1109 bool RenderGrid::hasAutoMarginsInColumnAxis(const RenderBox& child) const
1110 {
1111     if (isHorizontalWritingMode())
1112         return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1113     return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1114 }
1115
1116 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1117 bool RenderGrid::hasAutoMarginsInRowAxis(const RenderBox& child) const
1118 {
1119     if (isHorizontalWritingMode())
1120         return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1121     return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1122 }
1123
1124 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1125 void RenderGrid::updateAutoMarginsInRowAxisIfNeeded(RenderBox& child)
1126 {
1127     ASSERT(!child.isOutOfFlowPositioned());
1128
1129     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalWidth().value() - child.logicalWidth() - child.marginLogicalWidth();
1130     if (availableAlignmentSpace <= 0)
1131         return;
1132
1133     const RenderStyle& parentStyle = style();
1134     Length marginStart = child.style().marginStartUsing(&parentStyle);
1135     Length marginEnd = child.style().marginEndUsing(&parentStyle);
1136     if (marginStart.isAuto() && marginEnd.isAuto()) {
1137         child.setMarginStart(availableAlignmentSpace / 2, &parentStyle);
1138         child.setMarginEnd(availableAlignmentSpace / 2, &parentStyle);
1139     } else if (marginStart.isAuto()) {
1140         child.setMarginStart(availableAlignmentSpace, &parentStyle);
1141     } else if (marginEnd.isAuto()) {
1142         child.setMarginEnd(availableAlignmentSpace, &parentStyle);
1143     }
1144 }
1145
1146 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1147 void RenderGrid::updateAutoMarginsInColumnAxisIfNeeded(RenderBox& child)
1148 {
1149     ASSERT(!child.isOutOfFlowPositioned());
1150
1151     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalHeight().value() - child.logicalHeight() - child.marginLogicalHeight();
1152     if (availableAlignmentSpace <= 0)
1153         return;
1154
1155     const RenderStyle& parentStyle = style();
1156     Length marginBefore = child.style().marginBeforeUsing(&parentStyle);
1157     Length marginAfter = child.style().marginAfterUsing(&parentStyle);
1158     if (marginBefore.isAuto() && marginAfter.isAuto()) {
1159         child.setMarginBefore(availableAlignmentSpace / 2, &parentStyle);
1160         child.setMarginAfter(availableAlignmentSpace / 2, &parentStyle);
1161     } else if (marginBefore.isAuto()) {
1162         child.setMarginBefore(availableAlignmentSpace, &parentStyle);
1163     } else if (marginAfter.isAuto()) {
1164         child.setMarginAfter(availableAlignmentSpace, &parentStyle);
1165     }
1166 }
1167
1168 // FIXME: This logic could be refactored somehow and defined in RenderBox.
1169 static int synthesizedBaselineFromBorderBox(const RenderBox& box, LineDirectionMode direction)
1170 {
1171     return (direction == HorizontalLine ? box.size().height() : box.size().width()).toInt();
1172 }
1173
1174 bool RenderGrid::isInlineBaselineAlignedChild(const RenderBox& child) const
1175 {
1176     return alignSelfForChild(child).position() == ItemPositionBaseline && !GridLayoutFunctions::isOrthogonalChild(*this, child) && !hasAutoMarginsInColumnAxis(child);
1177 }
1178
1179 // FIXME: This logic is shared by RenderFlexibleBox, so it might be refactored somehow.
1180 int RenderGrid::baselinePosition(FontBaseline, bool, LineDirectionMode direction, LinePositionMode mode) const
1181 {
1182 #if ENABLE(ASSERT)
1183     ASSERT(mode == PositionOnContainingLine);
1184 #else
1185     UNUSED_PARAM(mode);
1186 #endif
1187     int baseline = firstLineBaseline().value_or(synthesizedBaselineFromBorderBox(*this, direction));
1188
1189     int marginSize = direction == HorizontalLine ? verticalMarginExtent() : horizontalMarginExtent();
1190     return baseline + marginSize;
1191 }
1192
1193 std::optional<int> RenderGrid::firstLineBaseline() const
1194 {
1195     if (isWritingModeRoot() || !m_grid.hasGridItems())
1196         return std::nullopt;
1197
1198     const RenderBox* baselineChild = nullptr;
1199     // Finding the first grid item in grid order.
1200     unsigned numColumns = m_grid.numTracks(ForColumns);
1201     for (size_t column = 0; column < numColumns; column++) {
1202         for (const auto* child : m_grid.cell(0, column)) {
1203             // If an item participates in baseline alignment, we select such item.
1204             if (isInlineBaselineAlignedChild(*child)) {
1205                 // FIXME: self-baseline and content-baseline alignment not implemented yet.
1206                 baselineChild = child;
1207                 break;
1208             }
1209             if (!baselineChild)
1210                 baselineChild = child;
1211         }
1212     }
1213
1214     if (!baselineChild)
1215         return std::nullopt;
1216
1217     auto baseline = GridLayoutFunctions::isOrthogonalChild(*this, *baselineChild) ? std::nullopt : baselineChild->firstLineBaseline();
1218     // We take border-box's bottom if no valid baseline.
1219     if (!baseline) {
1220         // FIXME: We should pass |direction| into firstLineBaseline and stop bailing out if we're a writing
1221         // mode root. This would also fix some cases where the grid is orthogonal to its container.
1222         LineDirectionMode direction = isHorizontalWritingMode() ? HorizontalLine : VerticalLine;
1223         return synthesizedBaselineFromBorderBox(*baselineChild, direction) + baselineChild->logicalTop().toInt();
1224     }
1225     return baseline.value() + baselineChild->logicalTop().toInt();
1226 }
1227
1228 std::optional<int> RenderGrid::inlineBlockBaseline(LineDirectionMode direction) const
1229 {
1230     if (std::optional<int> baseline = firstLineBaseline())
1231         return baseline;
1232
1233     int marginAscent = direction == HorizontalLine ? marginTop() : marginRight();
1234     return synthesizedBaselineFromBorderBox(*this, direction) + marginAscent;
1235 }
1236
1237 GridAxisPosition RenderGrid::columnAxisPositionForChild(const RenderBox& child) const
1238 {
1239     bool hasSameWritingMode = child.style().writingMode() == style().writingMode();
1240     bool childIsLTR = child.style().isLeftToRightDirection();
1241     if (!hasStaticPositionForChild(child, ForRows))
1242         return GridAxisStart;
1243
1244     switch (alignSelfForChild(child).position()) {
1245     case ItemPositionSelfStart:
1246         // FIXME: Should we implement this logic in a generic utility function ?
1247         // Aligns the alignment subject to be flush with the edge of the alignment container
1248         // corresponding to the alignment subject's 'start' side in the column axis.
1249         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1250             // If orthogonal writing-modes, self-start will be based on the child's inline-axis
1251             // direction (inline-start), because it's the one parallel to the column axis.
1252             if (style().isFlippedBlocksWritingMode())
1253                 return childIsLTR ? GridAxisEnd : GridAxisStart;
1254             return childIsLTR ? GridAxisStart : GridAxisEnd;
1255         }
1256         // self-start is based on the child's block-flow direction. That's why we need to check against the grid container's block-flow direction.
1257         return hasSameWritingMode ? GridAxisStart : GridAxisEnd;
1258     case ItemPositionSelfEnd:
1259         // FIXME: Should we implement this logic in a generic utility function ?
1260         // Aligns the alignment subject to be flush with the edge of the alignment container
1261         // corresponding to the alignment subject's 'end' side in the column axis.
1262         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1263             // If orthogonal writing-modes, self-end will be based on the child's inline-axis
1264             // direction, (inline-end) because it's the one parallel to the column axis.
1265             if (style().isFlippedBlocksWritingMode())
1266                 return childIsLTR ? GridAxisStart : GridAxisEnd;
1267             return childIsLTR ? GridAxisEnd : GridAxisStart;
1268         }
1269         // self-end is based on the child's block-flow direction. That's why we need to check against the grid container's block-flow direction.
1270         return hasSameWritingMode ? GridAxisEnd : GridAxisStart;
1271     case ItemPositionLeft:
1272         // Aligns the alignment subject to be flush with the alignment container's 'line-left' edge.
1273         // The alignment axis (column axis) is always orthogonal to the inline axis, hence this value behaves as 'start'.
1274         return GridAxisStart;
1275     case ItemPositionRight:
1276         // Aligns the alignment subject to be flush with the alignment container's 'line-right' edge.
1277         // The alignment axis (column axis) is always orthogonal to the inline axis, hence this value behaves as 'start'.
1278         return GridAxisStart;
1279     case ItemPositionCenter:
1280         return GridAxisCenter;
1281     case ItemPositionFlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
1282         // Aligns the alignment subject to be flush with the alignment container's 'start' edge (block-start) in the column axis.
1283     case ItemPositionStart:
1284         return GridAxisStart;
1285     case ItemPositionFlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
1286         // Aligns the alignment subject to be flush with the alignment container's 'end' edge (block-end) in the column axis.
1287     case ItemPositionEnd:
1288         return GridAxisEnd;
1289     case ItemPositionStretch:
1290         return GridAxisStart;
1291     case ItemPositionBaseline:
1292     case ItemPositionLastBaseline:
1293         // FIXME: Implement the previous values. For now, we always 'start' align the child.
1294         return GridAxisStart;
1295     case ItemPositionAuto:
1296     case ItemPositionNormal:
1297         break;
1298     }
1299
1300     ASSERT_NOT_REACHED();
1301     return GridAxisStart;
1302 }
1303
1304 GridAxisPosition RenderGrid::rowAxisPositionForChild(const RenderBox& child) const
1305 {
1306     bool hasSameDirection = child.style().direction() == style().direction();
1307     bool gridIsLTR = style().isLeftToRightDirection();
1308     if (!hasStaticPositionForChild(child, ForColumns))
1309         return GridAxisStart;
1310
1311     switch (justifySelfForChild(child).position()) {
1312     case ItemPositionSelfStart:
1313         // FIXME: Should we implement this logic in a generic utility function ?
1314         // Aligns the alignment subject to be flush with the edge of the alignment container
1315         // corresponding to the alignment subject's 'start' side in the row axis.
1316         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1317             // If orthogonal writing-modes, self-start will be based on the child's block-axis
1318             // direction, because it's the one parallel to the row axis.
1319             if (child.style().isFlippedBlocksWritingMode())
1320                 return gridIsLTR ? GridAxisEnd : GridAxisStart;
1321             return gridIsLTR ? GridAxisStart : GridAxisEnd;
1322         }
1323         // self-start is based on the child's inline-flow direction. That's why we need to check against the grid container's direction.
1324         return hasSameDirection ? GridAxisStart : GridAxisEnd;
1325     case ItemPositionSelfEnd:
1326         // FIXME: Should we implement this logic in a generic utility function ?
1327         // Aligns the alignment subject to be flush with the edge of the alignment container
1328         // corresponding to the alignment subject's 'end' side in the row axis.
1329         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1330             // If orthogonal writing-modes, self-end will be based on the child's block-axis
1331             // direction, because it's the one parallel to the row axis.
1332             if (child.style().isFlippedBlocksWritingMode())
1333                 return gridIsLTR ? GridAxisStart : GridAxisEnd;
1334             return gridIsLTR ? GridAxisEnd : GridAxisStart;
1335         }
1336         // self-end is based on the child's inline-flow direction. That's why we need to check against the grid container's direction.
1337         return hasSameDirection ? GridAxisEnd : GridAxisStart;
1338     case ItemPositionLeft:
1339         // Aligns the alignment subject to be flush with the alignment container's 'line-left' edge.
1340         // We want the physical 'left' side, so we have to take account, container's inline-flow direction.
1341         return gridIsLTR ? GridAxisStart : GridAxisEnd;
1342     case ItemPositionRight:
1343         // Aligns the alignment subject to be flush with the alignment container's 'line-right' edge.
1344         // We want the physical 'right' side, so we have to take account, container's inline-flow direction.
1345         return gridIsLTR ? GridAxisEnd : GridAxisStart;
1346     case ItemPositionCenter:
1347         return GridAxisCenter;
1348     case ItemPositionFlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
1349         // Aligns the alignment subject to be flush with the alignment container's 'start' edge (inline-start) in the row axis.
1350     case ItemPositionStart:
1351         return GridAxisStart;
1352     case ItemPositionFlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
1353         // Aligns the alignment subject to be flush with the alignment container's 'end' edge (inline-end) in the row axis.
1354     case ItemPositionEnd:
1355         return GridAxisEnd;
1356     case ItemPositionStretch:
1357         return GridAxisStart;
1358     case ItemPositionBaseline:
1359     case ItemPositionLastBaseline:
1360         // FIXME: Implement the previous values. For now, we always 'start' align the child.
1361         return GridAxisStart;
1362     case ItemPositionAuto:
1363     case ItemPositionNormal:
1364         break;
1365     }
1366
1367     ASSERT_NOT_REACHED();
1368     return GridAxisStart;
1369 }
1370
1371 LayoutUnit RenderGrid::columnAxisOffsetForChild(const RenderBox& child) const
1372 {
1373     LayoutUnit startOfRow;
1374     LayoutUnit endOfRow;
1375     gridAreaPositionForChild(child, ForRows, startOfRow, endOfRow);
1376     LayoutUnit startPosition = startOfRow + marginBeforeForChild(child);
1377     if (hasAutoMarginsInColumnAxis(child))
1378         return startPosition;
1379     GridAxisPosition axisPosition = columnAxisPositionForChild(child);
1380     switch (axisPosition) {
1381     case GridAxisStart:
1382         return startPosition;
1383     case GridAxisEnd:
1384     case GridAxisCenter: {
1385         LayoutUnit columnAxisChildSize = GridLayoutFunctions::isOrthogonalChild(*this, child) ? child.logicalWidth() + child.marginLogicalWidth() : child.logicalHeight() + child.marginLogicalHeight();
1386         auto overflow = alignSelfForChild(child).overflow();
1387         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(overflow, endOfRow - startOfRow, columnAxisChildSize);
1388         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
1389     }
1390     }
1391
1392     ASSERT_NOT_REACHED();
1393     return 0;
1394 }
1395
1396 LayoutUnit RenderGrid::rowAxisOffsetForChild(const RenderBox& child) const
1397 {
1398     LayoutUnit startOfColumn;
1399     LayoutUnit endOfColumn;
1400     gridAreaPositionForChild(child, ForColumns, startOfColumn, endOfColumn);
1401     LayoutUnit startPosition = startOfColumn + marginStartForChild(child);
1402     if (hasAutoMarginsInRowAxis(child))
1403         return startPosition;
1404     GridAxisPosition axisPosition = rowAxisPositionForChild(child);
1405     switch (axisPosition) {
1406     case GridAxisStart:
1407         return startPosition;
1408     case GridAxisEnd:
1409     case GridAxisCenter: {
1410         LayoutUnit rowAxisChildSize = GridLayoutFunctions::isOrthogonalChild(*this, child) ? child.logicalHeight() + child.marginLogicalHeight() : child.logicalWidth() + child.marginLogicalWidth();
1411         auto overflow = justifySelfForChild(child).overflow();
1412         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(overflow, endOfColumn - startOfColumn, rowAxisChildSize);
1413         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
1414     }
1415     }
1416
1417     ASSERT_NOT_REACHED();
1418     return 0;
1419 }
1420
1421 bool RenderGrid::gridPositionIsAutoForOutOfFlow(GridPosition position, GridTrackSizingDirection direction) const
1422 {
1423     return position.isAuto() || (position.isNamedGridArea() && !NamedLineCollection::isValidNamedLineOrArea(position.namedGridLine(), style(), GridPositionsResolver::initialPositionSide(direction)));
1424 }
1425
1426 LayoutUnit RenderGrid::resolveAutoStartGridPosition(GridTrackSizingDirection direction) const
1427 {
1428     if (direction == ForRows || style().isLeftToRightDirection())
1429         return LayoutUnit();
1430
1431     int lastLine = numTracks(ForColumns, m_grid);
1432     ContentPosition position = style().resolvedJustifyContentPosition(contentAlignmentNormalBehaviorGrid());
1433     if (position == ContentPositionEnd)
1434         return m_columnPositions[lastLine] - clientLogicalWidth();
1435     if (position == ContentPositionStart || style().resolvedJustifyContentDistribution(contentAlignmentNormalBehaviorGrid()) == ContentDistributionStretch)
1436         return m_columnPositions[0] - borderAndPaddingLogicalLeft();
1437     return LayoutUnit();
1438 }
1439
1440 LayoutUnit RenderGrid::resolveAutoEndGridPosition(GridTrackSizingDirection direction) const
1441 {
1442     if (direction == ForRows)
1443         return clientLogicalHeight();
1444     if (style().isLeftToRightDirection())
1445         return clientLogicalWidth();
1446
1447     int lastLine = numTracks(ForColumns, m_grid);
1448     ContentPosition position = style().resolvedJustifyContentPosition(contentAlignmentNormalBehaviorGrid());
1449     if (position == ContentPositionEnd)
1450         return m_columnPositions[lastLine];
1451     if (position == ContentPositionStart || style().resolvedJustifyContentDistribution(contentAlignmentNormalBehaviorGrid()) == ContentDistributionStretch)
1452         return m_columnPositions[0] - borderAndPaddingLogicalLeft() + clientLogicalWidth();
1453     return clientLogicalWidth();
1454 }
1455
1456 LayoutUnit RenderGrid::gridAreaBreadthForOutOfFlowChild(const RenderBox& child, GridTrackSizingDirection direction)
1457 {
1458     ASSERT(child.isOutOfFlowPositioned());
1459     bool isRowAxis = direction == ForColumns;
1460     GridSpan span = GridPositionsResolver::resolveGridPositionsFromStyle(style(), child, direction, autoRepeatCountForDirection(direction));
1461     if (span.isIndefinite())
1462         return isRowAxis ? clientLogicalWidth() : clientLogicalHeight();
1463
1464     int smallestStart = abs(m_grid.smallestTrackStart(direction));
1465     int startLine = span.untranslatedStartLine() + smallestStart;
1466     int endLine = span.untranslatedEndLine() + smallestStart;
1467     int lastLine = numTracks(direction, m_grid);
1468     GridPosition startPosition = direction == ForColumns ? child.style().gridItemColumnStart() : child.style().gridItemRowStart();
1469     GridPosition endPosition = direction == ForColumns ? child.style().gridItemColumnEnd() : child.style().gridItemRowEnd();
1470
1471     bool startIsAuto = gridPositionIsAutoForOutOfFlow(startPosition, direction) || startLine < 0 || startLine > lastLine;
1472     bool endIsAuto = gridPositionIsAutoForOutOfFlow(endPosition, direction) || endLine < 0 || endLine > lastLine;
1473
1474     if (startIsAuto && endIsAuto)
1475         return isRowAxis ? clientLogicalWidth() : clientLogicalHeight();
1476
1477     LayoutUnit start;
1478     LayoutUnit end;
1479     auto& positions = isRowAxis ? m_columnPositions : m_rowPositions;
1480     auto& outOfFlowItemLine = isRowAxis ? m_outOfFlowItemColumn : m_outOfFlowItemRow;
1481     LayoutUnit borderEdge = isRowAxis ? borderLogicalLeft() : borderBefore();
1482     if (startIsAuto)
1483         start = resolveAutoStartGridPosition(direction) + borderEdge;
1484     else {
1485         outOfFlowItemLine.set(&child, startLine);
1486         start = positions[startLine];
1487     }
1488     if (endIsAuto)
1489         end = resolveAutoEndGridPosition(direction) + borderEdge;
1490     else {
1491         end = positions[endLine];
1492         // These vectors store line positions including gaps, but we shouldn't consider them for the edges of the grid.
1493         std::optional<LayoutUnit> availableSizeForGutters = availableSpaceForGutters(direction);
1494         if (endLine > 0 && endLine < lastLine) {
1495             ASSERT(!m_grid.needsItemsPlacement());
1496             end -= guttersSize(m_grid, direction, endLine - 1, 2, availableSizeForGutters);
1497             end -= isRowAxis ? m_offsetBetweenColumns : m_offsetBetweenRows;
1498         }
1499     }
1500     return std::max(end - start, LayoutUnit());
1501 }
1502
1503 LayoutUnit RenderGrid::logicalOffsetForChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit trackBreadth) const
1504 {
1505     if (hasStaticPositionForChild(child, direction))
1506         return LayoutUnit();
1507
1508     bool isRowAxis = direction == ForColumns;
1509     bool isFlowAwareRowAxis = GridLayoutFunctions::flowAwareDirectionForChild(*this, child, direction) == ForColumns;
1510     LayoutUnit childPosition = isFlowAwareRowAxis ? child.logicalLeft() : child.logicalTop();
1511     LayoutUnit gridBorder = isRowAxis ? borderLogicalLeft() : borderBefore();
1512     LayoutUnit childMargin = isFlowAwareRowAxis ? child.marginLogicalLeft() : child.marginBefore();
1513     LayoutUnit offset = childPosition - gridBorder - childMargin;
1514     if (!isRowAxis || style().isLeftToRightDirection())
1515         return offset;
1516
1517     LayoutUnit childBreadth = isFlowAwareRowAxis ? child.logicalWidth() + child.marginLogicalWidth() : child.logicalHeight() + child.marginLogicalHeight();
1518     return trackBreadth - offset - childBreadth;
1519 }
1520
1521 void RenderGrid::gridAreaPositionForOutOfFlowChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit& start, LayoutUnit& end) const
1522 {
1523     ASSERT(child.isOutOfFlowPositioned());
1524     ASSERT(GridLayoutFunctions::hasOverrideContainingBlockContentSizeForChild(child, direction));
1525     LayoutUnit trackBreadth = GridLayoutFunctions::overrideContainingBlockContentSizeForChild(child, direction).value();
1526     bool isRowAxis = direction == ForColumns;
1527     auto& outOfFlowItemLine = isRowAxis ? m_outOfFlowItemColumn : m_outOfFlowItemRow;
1528     start = isRowAxis ? borderLogicalLeft() : borderBefore();
1529     if (auto line = outOfFlowItemLine.get(&child)) {
1530         auto& positions = isRowAxis ? m_columnPositions : m_rowPositions;
1531         start = positions[line.value()];
1532     }
1533     start += logicalOffsetForChild(child, direction, trackBreadth);
1534     end = start + trackBreadth;
1535 }
1536
1537 void RenderGrid::gridAreaPositionForInFlowChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit& start, LayoutUnit& end) const
1538 {
1539     ASSERT(!child.isOutOfFlowPositioned());
1540     const GridSpan& span = m_grid.gridItemSpan(child, direction);
1541     // FIXME (lajava): This is a common pattern, why not defining a function like
1542     // positions(direction) ?
1543     auto& positions = direction == ForColumns ? m_columnPositions : m_rowPositions;
1544     start = positions[span.startLine()];
1545     end = positions[span.endLine()];
1546     // The 'positions' vector includes distribution offset (because of content
1547     // alignment) and gutters so we need to subtract them to get the actual
1548     // end position for a given track (this does not have to be done for the
1549     // last track as there are no more positions's elements after it).
1550     if (span.endLine() < positions.size() - 1)
1551         end -= gridGap(direction) + gridItemOffset(direction);
1552 }
1553
1554 void RenderGrid::gridAreaPositionForChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit& start, LayoutUnit& end) const
1555 {
1556     if (child.isOutOfFlowPositioned())
1557         gridAreaPositionForOutOfFlowChild(child, direction, start, end);
1558     else
1559         gridAreaPositionForInFlowChild(child, direction, start, end);
1560 }
1561
1562 ContentPosition static resolveContentDistributionFallback(ContentDistributionType distribution)
1563 {
1564     switch (distribution) {
1565     case ContentDistributionSpaceBetween:
1566         return ContentPositionStart;
1567     case ContentDistributionSpaceAround:
1568         return ContentPositionCenter;
1569     case ContentDistributionSpaceEvenly:
1570         return ContentPositionCenter;
1571     case ContentDistributionStretch:
1572         return ContentPositionStart;
1573     case ContentDistributionDefault:
1574         return ContentPositionNormal;
1575     }
1576
1577     ASSERT_NOT_REACHED();
1578     return ContentPositionNormal;
1579 }
1580
1581 static ContentAlignmentData contentDistributionOffset(const LayoutUnit& availableFreeSpace, ContentPosition& fallbackPosition, ContentDistributionType distribution, unsigned numberOfGridTracks)
1582 {
1583     if (distribution != ContentDistributionDefault && fallbackPosition == ContentPositionNormal)
1584         fallbackPosition = resolveContentDistributionFallback(distribution);
1585
1586     if (availableFreeSpace <= 0)
1587         return ContentAlignmentData::defaultOffsets();
1588
1589     LayoutUnit distributionOffset;
1590     switch (distribution) {
1591     case ContentDistributionSpaceBetween:
1592         if (numberOfGridTracks < 2)
1593             return ContentAlignmentData::defaultOffsets();
1594         return {0, availableFreeSpace / (numberOfGridTracks - 1)};
1595     case ContentDistributionSpaceAround:
1596         if (numberOfGridTracks < 1)
1597             return ContentAlignmentData::defaultOffsets();
1598         distributionOffset = availableFreeSpace / numberOfGridTracks;
1599         return {distributionOffset / 2, distributionOffset};
1600     case ContentDistributionSpaceEvenly:
1601         distributionOffset = availableFreeSpace / (numberOfGridTracks + 1);
1602         return {distributionOffset, distributionOffset};
1603     case ContentDistributionStretch:
1604     case ContentDistributionDefault:
1605         return ContentAlignmentData::defaultOffsets();
1606     }
1607
1608     ASSERT_NOT_REACHED();
1609     return ContentAlignmentData::defaultOffsets();
1610 }
1611
1612 StyleContentAlignmentData RenderGrid::contentAlignment(GridTrackSizingDirection direction) const
1613 {
1614     return direction == ForColumns ? style().resolvedJustifyContent(contentAlignmentNormalBehaviorGrid()) : style().resolvedAlignContent(contentAlignmentNormalBehaviorGrid());
1615 }
1616
1617 ContentAlignmentData RenderGrid::computeContentPositionAndDistributionOffset(GridTrackSizingDirection direction, const LayoutUnit& availableFreeSpace, unsigned numberOfGridTracks) const
1618 {
1619     bool isRowAxis = direction == ForColumns;
1620     auto contentAlignmentData = contentAlignment(direction);
1621     auto position = contentAlignmentData.position();
1622     // If <content-distribution> value can't be applied, 'position' will become the associated
1623     // <content-position> fallback value.
1624     auto contentAlignment = contentDistributionOffset(availableFreeSpace, position, contentAlignmentData.distribution(), numberOfGridTracks);
1625     if (contentAlignment.isValid())
1626         return contentAlignment;
1627
1628     if (availableFreeSpace <= 0 && contentAlignmentData.overflow() == OverflowAlignmentSafe)
1629         return {0, 0};
1630
1631     switch (position) {
1632     case ContentPositionLeft:
1633         // The align-content's axis is always orthogonal to the inline-axis.
1634         return {0, 0};
1635     case ContentPositionRight:
1636         if (isRowAxis)
1637             return {availableFreeSpace, 0};
1638         // The align-content's axis is always orthogonal to the inline-axis.
1639         return {0, 0};
1640     case ContentPositionCenter:
1641         return {availableFreeSpace / 2, 0};
1642     case ContentPositionFlexEnd: // Only used in flex layout, for other layout, it's equivalent to 'end'.
1643     case ContentPositionEnd:
1644         if (isRowAxis)
1645             return {style().isLeftToRightDirection() ? availableFreeSpace : LayoutUnit(), LayoutUnit()};
1646         return {availableFreeSpace, 0};
1647     case ContentPositionFlexStart: // Only used in flex layout, for other layout, it's equivalent to 'start'.
1648     case ContentPositionStart:
1649         if (isRowAxis)
1650             return {style().isLeftToRightDirection() ? LayoutUnit() : availableFreeSpace, LayoutUnit()};
1651         return {0, 0};
1652     case ContentPositionBaseline:
1653     case ContentPositionLastBaseline:
1654         // FIXME: Implement the previous values. For now, we always 'start' align.
1655         // http://webkit.org/b/145566
1656         if (isRowAxis)
1657             return {style().isLeftToRightDirection() ? LayoutUnit() : availableFreeSpace, LayoutUnit()};
1658         return {0, 0};
1659     case ContentPositionNormal:
1660         break;
1661     }
1662
1663     ASSERT_NOT_REACHED();
1664     return {0, 0};
1665 }
1666
1667 LayoutUnit RenderGrid::translateOutOfFlowRTLCoordinate(const RenderBox& child, LayoutUnit coordinate) const
1668 {
1669     ASSERT(child.isOutOfFlowPositioned());
1670     ASSERT(!style().isLeftToRightDirection());
1671
1672     if (m_outOfFlowItemColumn.get(&child))
1673         return translateRTLCoordinate(coordinate);
1674
1675     return borderLogicalLeft() + borderLogicalRight() + clientLogicalWidth() - coordinate;
1676 }
1677
1678 LayoutUnit RenderGrid::translateRTLCoordinate(LayoutUnit coordinate) const
1679 {
1680     ASSERT(!style().isLeftToRightDirection());
1681
1682     LayoutUnit alignmentOffset = m_columnPositions[0];
1683     LayoutUnit rightGridEdgePosition = m_columnPositions[m_columnPositions.size() - 1];
1684     return rightGridEdgePosition + alignmentOffset - coordinate;
1685 }
1686
1687 LayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox& child) const
1688 {
1689     LayoutUnit columnAxisOffset = columnAxisOffsetForChild(child);
1690     LayoutUnit rowAxisOffset = rowAxisOffsetForChild(child);
1691     bool isOrthogonalChild = GridLayoutFunctions::isOrthogonalChild(*this, child);
1692
1693     // We stored m_columnPositions's data ignoring the direction, hence we might need now
1694     // to translate positions from RTL to LTR, as it's more convenient for painting.
1695     if (!style().isLeftToRightDirection())
1696         rowAxisOffset = (child.isOutOfFlowPositioned() ? translateOutOfFlowRTLCoordinate(child, rowAxisOffset) : translateRTLCoordinate(rowAxisOffset)) - (isOrthogonalChild ? child.logicalHeight()  : child.logicalWidth());
1697
1698     // "In the positioning phase [...] calculations are performed according to the writing mode
1699     // of the containing block of the box establishing the orthogonal flow." However, the
1700     // resulting LayoutPoint will be used in 'setLogicalPosition' in order to set the child's
1701     // logical position, which will only take into account the child's writing-mode.
1702     LayoutPoint childLocation(rowAxisOffset, columnAxisOffset);
1703     return isOrthogonalChild ? childLocation.transposedPoint() : childLocation;
1704 }
1705
1706 unsigned RenderGrid::numTracks(GridTrackSizingDirection direction, const Grid& grid) const
1707 {
1708     // Due to limitations in our internal representation, we cannot know the number of columns from
1709     // m_grid *if* there is no row (because m_grid would be empty). That's why in that case we need
1710     // to get it from the style. Note that we know for sure that there are't any implicit tracks,
1711     // because not having rows implies that there are no "normal" children (out-of-flow children are
1712     // not stored in m_grid).
1713     ASSERT(!grid.needsItemsPlacement());
1714     if (direction == ForRows)
1715         return grid.numTracks(ForRows);
1716
1717     // FIXME: This still requires knowledge about m_grid internals.
1718     return grid.numTracks(ForRows) ? grid.numTracks(ForColumns) : GridPositionsResolver::explicitGridColumnCount(style(), grid.autoRepeatTracks(ForColumns));
1719 }
1720
1721 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset, PaintInfo& forChild, bool usePrintRect)
1722 {
1723     ASSERT(!m_grid.needsItemsPlacement());
1724     for (RenderBox* child = m_grid.orderIterator().first(); child; child = m_grid.orderIterator().next())
1725         paintChild(*child, paintInfo, paintOffset, forChild, usePrintRect, PaintAsInlineBlock);
1726 }
1727
1728 const char* RenderGrid::renderName() const
1729 {
1730     if (isFloating())
1731         return "RenderGrid (floating)";
1732     if (isOutOfFlowPositioned())
1733         return "RenderGrid (positioned)";
1734     if (isAnonymous())
1735         return "RenderGrid (generated)";
1736     if (isRelativelyPositioned())
1737         return "RenderGrid (relative positioned)";
1738     return "RenderGrid";
1739 }
1740
1741 } // namespace WebCore