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