Unreviewed, rolling out r238220.
[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     auto borderAndPadding = isRowAxis ? borderAndPaddingLogicalLeft() : borderAndPaddingBefore();
1007     positions[0] = borderAndPadding + offset.positionOffset;
1008     if (numberOfLines > 1) {
1009         // If we have collapsed tracks we just ignore gaps here and add them later as we might not
1010         // compute the gap between two consecutive tracks without examining the surrounding ones.
1011         LayoutUnit gap = !hasCollapsedTracks ? gridGap(direction) : LayoutUnit();
1012         unsigned nextToLastLine = numberOfLines - 2;
1013         for (unsigned i = 0; i < nextToLastLine; ++i)
1014             positions[i + 1] = positions[i] + offset.distributionOffset + tracks[i].baseSize() + gap;
1015         positions[lastLine] = positions[nextToLastLine] + tracks[nextToLastLine].baseSize();
1016
1017         // Adjust collapsed gaps. Collapsed tracks cause the surrounding gutters to collapse (they
1018         // coincide exactly) except on the edges of the grid where they become 0.
1019         if (hasCollapsedTracks) {
1020             gap = gridGap(direction);
1021             unsigned remainingEmptyTracks = numberOfCollapsedTracks;
1022             LayoutUnit offsetAccumulator;
1023             LayoutUnit gapAccumulator;
1024             for (unsigned i = 1; i < lastLine; ++i) {
1025                 if (m_grid.isEmptyAutoRepeatTrack(direction, i - 1)) {
1026                     --remainingEmptyTracks;
1027                     offsetAccumulator += offset.distributionOffset;
1028                 } else {
1029                     // Add gap between consecutive non empty tracks. Add it also just once for an
1030                     // arbitrary number of empty tracks between two non empty ones.
1031                     bool allRemainingTracksAreEmpty = remainingEmptyTracks == (lastLine - i);
1032                     if (!allRemainingTracksAreEmpty || !m_grid.isEmptyAutoRepeatTrack(direction, i))
1033                         gapAccumulator += gap;
1034                 }
1035                 positions[i] += gapAccumulator - offsetAccumulator;
1036             }
1037             positions[lastLine] += gapAccumulator - offsetAccumulator;
1038         }
1039     }
1040 }
1041
1042 static LayoutUnit computeOverflowAlignmentOffset(OverflowAlignment overflow, LayoutUnit trackSize, LayoutUnit childSize)
1043 {
1044     LayoutUnit offset = trackSize - childSize;
1045     switch (overflow) {
1046     case OverflowAlignment::Safe:
1047         // If overflow is 'safe', we have to make sure we don't overflow the 'start'
1048         // edge (potentially cause some data loss as the overflow is unreachable).
1049         return std::max<LayoutUnit>(0, offset);
1050     case OverflowAlignment::Unsafe:
1051     case OverflowAlignment::Default:
1052         // If we overflow our alignment container and overflow is 'true' (default), we
1053         // ignore the overflow and just return the value regardless (which may cause data
1054         // loss as we overflow the 'start' edge).
1055         return offset;
1056     }
1057
1058     ASSERT_NOT_REACHED();
1059     return 0;
1060 }
1061
1062 LayoutUnit RenderGrid::availableAlignmentSpaceForChildBeforeStretching(LayoutUnit gridAreaBreadthForChild, const RenderBox& child) const
1063 {
1064     // Because we want to avoid multiple layouts, stretching logic might be performed before
1065     // children are laid out, so we can't use the child cached values. Hence, we need to
1066     // compute margins in order to determine the available height before stretching.
1067     GridTrackSizingDirection childBlockFlowDirection = GridLayoutFunctions::flowAwareDirectionForChild(*this, child, ForRows);
1068     return gridAreaBreadthForChild - GridLayoutFunctions::marginLogicalSizeForChild(*this, childBlockFlowDirection, child);
1069 }
1070
1071 StyleSelfAlignmentData RenderGrid::alignSelfForChild(const RenderBox& child, const RenderStyle* gridStyle) const
1072 {
1073     if (!gridStyle)
1074         gridStyle = &style();
1075     return child.style().resolvedAlignSelf(gridStyle, selfAlignmentNormalBehavior(&child));
1076 }
1077
1078 StyleSelfAlignmentData RenderGrid::justifySelfForChild(const RenderBox& child, const RenderStyle* gridStyle) const
1079 {
1080     if (!gridStyle)
1081         gridStyle = &style();
1082     return child.style().resolvedJustifySelf(gridStyle, selfAlignmentNormalBehavior(&child));
1083 }
1084
1085 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1086 void RenderGrid::applyStretchAlignmentToChildIfNeeded(RenderBox& child)
1087 {
1088     ASSERT(child.overrideContainingBlockContentLogicalHeight());
1089
1090     // We clear height override values because we will decide now whether it's allowed or
1091     // not, evaluating the conditions which might have changed since the old values were set.
1092     child.clearOverrideContentLogicalHeight();
1093
1094     GridTrackSizingDirection childBlockDirection = GridLayoutFunctions::flowAwareDirectionForChild(*this, child, ForRows);
1095     bool blockFlowIsColumnAxis = childBlockDirection == ForRows;
1096     bool allowedToStretchChildBlockSize = blockFlowIsColumnAxis ? allowedToStretchChildAlongColumnAxis(child) : allowedToStretchChildAlongRowAxis(child);
1097     if (allowedToStretchChildBlockSize) {
1098         LayoutUnit stretchedLogicalHeight = availableAlignmentSpaceForChildBeforeStretching(GridLayoutFunctions::overrideContainingBlockContentSizeForChild(child, childBlockDirection).value(), child);
1099         LayoutUnit desiredLogicalHeight = child.constrainLogicalHeightByMinMax(stretchedLogicalHeight, LayoutUnit(-1));
1100         child.setOverrideContentLogicalHeight(desiredLogicalHeight - child.borderAndPaddingLogicalHeight());
1101         if (desiredLogicalHeight != child.logicalHeight()) {
1102             // FIXME: Can avoid laying out here in some cases. See https://webkit.org/b/87905.
1103             child.setLogicalHeight(LayoutUnit());
1104             child.setNeedsLayout();
1105         }
1106     }
1107 }
1108
1109 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1110 bool RenderGrid::hasAutoMarginsInColumnAxis(const RenderBox& child) const
1111 {
1112     if (isHorizontalWritingMode())
1113         return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1114     return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1115 }
1116
1117 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1118 bool RenderGrid::hasAutoMarginsInRowAxis(const RenderBox& child) const
1119 {
1120     if (isHorizontalWritingMode())
1121         return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1122     return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1123 }
1124
1125 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1126 void RenderGrid::updateAutoMarginsInRowAxisIfNeeded(RenderBox& child)
1127 {
1128     ASSERT(!child.isOutOfFlowPositioned());
1129
1130     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalWidth().value() - child.logicalWidth() - child.marginLogicalWidth();
1131     if (availableAlignmentSpace <= 0)
1132         return;
1133
1134     const RenderStyle& parentStyle = style();
1135     Length marginStart = child.style().marginStartUsing(&parentStyle);
1136     Length marginEnd = child.style().marginEndUsing(&parentStyle);
1137     if (marginStart.isAuto() && marginEnd.isAuto()) {
1138         child.setMarginStart(availableAlignmentSpace / 2, &parentStyle);
1139         child.setMarginEnd(availableAlignmentSpace / 2, &parentStyle);
1140     } else if (marginStart.isAuto()) {
1141         child.setMarginStart(availableAlignmentSpace, &parentStyle);
1142     } else if (marginEnd.isAuto()) {
1143         child.setMarginEnd(availableAlignmentSpace, &parentStyle);
1144     }
1145 }
1146
1147 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1148 void RenderGrid::updateAutoMarginsInColumnAxisIfNeeded(RenderBox& child)
1149 {
1150     ASSERT(!child.isOutOfFlowPositioned());
1151
1152     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalHeight().value() - child.logicalHeight() - child.marginLogicalHeight();
1153     if (availableAlignmentSpace <= 0)
1154         return;
1155
1156     const RenderStyle& parentStyle = style();
1157     Length marginBefore = child.style().marginBeforeUsing(&parentStyle);
1158     Length marginAfter = child.style().marginAfterUsing(&parentStyle);
1159     if (marginBefore.isAuto() && marginAfter.isAuto()) {
1160         child.setMarginBefore(availableAlignmentSpace / 2, &parentStyle);
1161         child.setMarginAfter(availableAlignmentSpace / 2, &parentStyle);
1162     } else if (marginBefore.isAuto()) {
1163         child.setMarginBefore(availableAlignmentSpace, &parentStyle);
1164     } else if (marginAfter.isAuto()) {
1165         child.setMarginAfter(availableAlignmentSpace, &parentStyle);
1166     }
1167 }
1168
1169 // FIXME: This logic could be refactored somehow and defined in RenderBox.
1170 static int synthesizedBaselineFromBorderBox(const RenderBox& box, LineDirectionMode direction)
1171 {
1172     return (direction == HorizontalLine ? box.size().height() : box.size().width()).toInt();
1173 }
1174
1175 bool RenderGrid::isInlineBaselineAlignedChild(const RenderBox& child) const
1176 {
1177     return alignSelfForChild(child).position() == ItemPosition::Baseline && !GridLayoutFunctions::isOrthogonalChild(*this, child) && !hasAutoMarginsInColumnAxis(child);
1178 }
1179
1180 // FIXME: This logic is shared by RenderFlexibleBox, so it might be refactored somehow.
1181 int RenderGrid::baselinePosition(FontBaseline, bool, LineDirectionMode direction, LinePositionMode mode) const
1182 {
1183 #if !ASSERT_DISABLED
1184     ASSERT(mode == PositionOnContainingLine);
1185 #else
1186     UNUSED_PARAM(mode);
1187 #endif
1188     int baseline = firstLineBaseline().value_or(synthesizedBaselineFromBorderBox(*this, direction));
1189
1190     int marginSize = direction == HorizontalLine ? verticalMarginExtent() : horizontalMarginExtent();
1191     return baseline + marginSize;
1192 }
1193
1194 std::optional<int> RenderGrid::firstLineBaseline() const
1195 {
1196     if (isWritingModeRoot() || !m_grid.hasGridItems())
1197         return std::nullopt;
1198
1199     const RenderBox* baselineChild = nullptr;
1200     // Finding the first grid item in grid order.
1201     unsigned numColumns = m_grid.numTracks(ForColumns);
1202     for (size_t column = 0; column < numColumns; column++) {
1203         for (auto& child : m_grid.cell(0, column)) {
1204             ASSERT(child.get());
1205             // If an item participates in baseline alignment, we select such item.
1206             if (isInlineBaselineAlignedChild(*child)) {
1207                 // FIXME: self-baseline and content-baseline alignment not implemented yet.
1208                 baselineChild = child.get();
1209                 break;
1210             }
1211             if (!baselineChild)
1212                 baselineChild = child.get();
1213         }
1214     }
1215
1216     if (!baselineChild)
1217         return std::nullopt;
1218
1219     auto baseline = GridLayoutFunctions::isOrthogonalChild(*this, *baselineChild) ? std::nullopt : baselineChild->firstLineBaseline();
1220     // We take border-box's bottom if no valid baseline.
1221     if (!baseline) {
1222         // FIXME: We should pass |direction| into firstLineBaseline and stop bailing out if we're a writing
1223         // mode root. This would also fix some cases where the grid is orthogonal to its container.
1224         LineDirectionMode direction = isHorizontalWritingMode() ? HorizontalLine : VerticalLine;
1225         return synthesizedBaselineFromBorderBox(*baselineChild, direction) + baselineChild->logicalTop().toInt();
1226     }
1227     return baseline.value() + baselineChild->logicalTop().toInt();
1228 }
1229
1230 std::optional<int> RenderGrid::inlineBlockBaseline(LineDirectionMode direction) const
1231 {
1232     if (std::optional<int> baseline = firstLineBaseline())
1233         return baseline;
1234
1235     int marginAscent = direction == HorizontalLine ? marginTop() : marginRight();
1236     return synthesizedBaselineFromBorderBox(*this, direction) + marginAscent;
1237 }
1238
1239 GridAxisPosition RenderGrid::columnAxisPositionForChild(const RenderBox& child) const
1240 {
1241     bool hasSameWritingMode = child.style().writingMode() == style().writingMode();
1242     bool childIsLTR = child.style().isLeftToRightDirection();
1243     if (!hasStaticPositionForChild(child, ForRows))
1244         return GridAxisStart;
1245
1246     switch (alignSelfForChild(child).position()) {
1247     case ItemPosition::SelfStart:
1248         // FIXME: Should we implement this logic in a generic utility function ?
1249         // Aligns the alignment subject to be flush with the edge of the alignment container
1250         // corresponding to the alignment subject's 'start' side in the column axis.
1251         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1252             // If orthogonal writing-modes, self-start will be based on the child's inline-axis
1253             // direction (inline-start), because it's the one parallel to the column axis.
1254             if (style().isFlippedBlocksWritingMode())
1255                 return childIsLTR ? GridAxisEnd : GridAxisStart;
1256             return childIsLTR ? GridAxisStart : GridAxisEnd;
1257         }
1258         // 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.
1259         return hasSameWritingMode ? GridAxisStart : GridAxisEnd;
1260     case ItemPosition::SelfEnd:
1261         // FIXME: Should we implement this logic in a generic utility function ?
1262         // Aligns the alignment subject to be flush with the edge of the alignment container
1263         // corresponding to the alignment subject's 'end' side in the column axis.
1264         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1265             // If orthogonal writing-modes, self-end will be based on the child's inline-axis
1266             // direction, (inline-end) because it's the one parallel to the column axis.
1267             if (style().isFlippedBlocksWritingMode())
1268                 return childIsLTR ? GridAxisStart : GridAxisEnd;
1269             return childIsLTR ? GridAxisEnd : GridAxisStart;
1270         }
1271         // 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.
1272         return hasSameWritingMode ? GridAxisEnd : GridAxisStart;
1273     case ItemPosition::Left:
1274         // Aligns the alignment subject to be flush with the alignment container's 'line-left' edge.
1275         // The alignment axis (column axis) is always orthogonal to the inline axis, hence this value behaves as 'start'.
1276         return GridAxisStart;
1277     case ItemPosition::Right:
1278         // Aligns the alignment subject to be flush with the alignment container's 'line-right' edge.
1279         // The alignment axis (column axis) is always orthogonal to the inline axis, hence this value behaves as 'start'.
1280         return GridAxisStart;
1281     case ItemPosition::Center:
1282         return GridAxisCenter;
1283     case ItemPosition::FlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
1284         // Aligns the alignment subject to be flush with the alignment container's 'start' edge (block-start) in the column axis.
1285     case ItemPosition::Start:
1286         return GridAxisStart;
1287     case ItemPosition::FlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
1288         // Aligns the alignment subject to be flush with the alignment container's 'end' edge (block-end) in the column axis.
1289     case ItemPosition::End:
1290         return GridAxisEnd;
1291     case ItemPosition::Stretch:
1292         return GridAxisStart;
1293     case ItemPosition::Baseline:
1294     case ItemPosition::LastBaseline:
1295         // FIXME: Implement the previous values. For now, we always 'start' align the child.
1296         return GridAxisStart;
1297     case ItemPosition::Legacy:
1298     case ItemPosition::Auto:
1299     case ItemPosition::Normal:
1300         break;
1301     }
1302
1303     ASSERT_NOT_REACHED();
1304     return GridAxisStart;
1305 }
1306
1307 GridAxisPosition RenderGrid::rowAxisPositionForChild(const RenderBox& child) const
1308 {
1309     bool hasSameDirection = child.style().direction() == style().direction();
1310     bool gridIsLTR = style().isLeftToRightDirection();
1311     if (!hasStaticPositionForChild(child, ForColumns))
1312         return GridAxisStart;
1313
1314     switch (justifySelfForChild(child).position()) {
1315     case ItemPosition::SelfStart:
1316         // FIXME: Should we implement this logic in a generic utility function ?
1317         // Aligns the alignment subject to be flush with the edge of the alignment container
1318         // corresponding to the alignment subject's 'start' side in the row axis.
1319         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1320             // If orthogonal writing-modes, self-start will be based on the child's block-axis
1321             // direction, because it's the one parallel to the row axis.
1322             if (child.style().isFlippedBlocksWritingMode())
1323                 return gridIsLTR ? GridAxisEnd : GridAxisStart;
1324             return gridIsLTR ? GridAxisStart : GridAxisEnd;
1325         }
1326         // self-start is based on the child's inline-flow direction. That's why we need to check against the grid container's direction.
1327         return hasSameDirection ? GridAxisStart : GridAxisEnd;
1328     case ItemPosition::SelfEnd:
1329         // FIXME: Should we implement this logic in a generic utility function ?
1330         // Aligns the alignment subject to be flush with the edge of the alignment container
1331         // corresponding to the alignment subject's 'end' side in the row axis.
1332         if (GridLayoutFunctions::isOrthogonalChild(*this, child)) {
1333             // If orthogonal writing-modes, self-end will be based on the child's block-axis
1334             // direction, because it's the one parallel to the row axis.
1335             if (child.style().isFlippedBlocksWritingMode())
1336                 return gridIsLTR ? GridAxisStart : GridAxisEnd;
1337             return gridIsLTR ? GridAxisEnd : GridAxisStart;
1338         }
1339         // self-end is based on the child's inline-flow direction. That's why we need to check against the grid container's direction.
1340         return hasSameDirection ? GridAxisEnd : GridAxisStart;
1341     case ItemPosition::Left:
1342         // Aligns the alignment subject to be flush with the alignment container's 'line-left' edge.
1343         // We want the physical 'left' side, so we have to take account, container's inline-flow direction.
1344         return gridIsLTR ? GridAxisStart : GridAxisEnd;
1345     case ItemPosition::Right:
1346         // Aligns the alignment subject to be flush with the alignment container's 'line-right' edge.
1347         // We want the physical 'right' side, so we have to take account, container's inline-flow direction.
1348         return gridIsLTR ? GridAxisEnd : GridAxisStart;
1349     case ItemPosition::Center:
1350         return GridAxisCenter;
1351     case ItemPosition::FlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
1352         // Aligns the alignment subject to be flush with the alignment container's 'start' edge (inline-start) in the row axis.
1353     case ItemPosition::Start:
1354         return GridAxisStart;
1355     case ItemPosition::FlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
1356         // Aligns the alignment subject to be flush with the alignment container's 'end' edge (inline-end) in the row axis.
1357     case ItemPosition::End:
1358         return GridAxisEnd;
1359     case ItemPosition::Stretch:
1360         return GridAxisStart;
1361     case ItemPosition::Baseline:
1362     case ItemPosition::LastBaseline:
1363         // FIXME: Implement the previous values. For now, we always 'start' align the child.
1364         return GridAxisStart;
1365     case ItemPosition::Legacy:
1366     case ItemPosition::Auto:
1367     case ItemPosition::Normal:
1368         break;
1369     }
1370
1371     ASSERT_NOT_REACHED();
1372     return GridAxisStart;
1373 }
1374
1375 LayoutUnit RenderGrid::columnAxisOffsetForChild(const RenderBox& child) const
1376 {
1377     LayoutUnit startOfRow;
1378     LayoutUnit endOfRow;
1379     gridAreaPositionForChild(child, ForRows, startOfRow, endOfRow);
1380     LayoutUnit startPosition = startOfRow + marginBeforeForChild(child);
1381     if (hasAutoMarginsInColumnAxis(child))
1382         return startPosition;
1383     GridAxisPosition axisPosition = columnAxisPositionForChild(child);
1384     switch (axisPosition) {
1385     case GridAxisStart:
1386         return startPosition;
1387     case GridAxisEnd:
1388     case GridAxisCenter: {
1389         LayoutUnit columnAxisChildSize = GridLayoutFunctions::isOrthogonalChild(*this, child) ? child.logicalWidth() + child.marginLogicalWidth() : child.logicalHeight() + child.marginLogicalHeight();
1390         auto overflow = alignSelfForChild(child).overflow();
1391         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(overflow, endOfRow - startOfRow, columnAxisChildSize);
1392         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
1393     }
1394     }
1395
1396     ASSERT_NOT_REACHED();
1397     return 0;
1398 }
1399
1400 LayoutUnit RenderGrid::rowAxisOffsetForChild(const RenderBox& child) const
1401 {
1402     LayoutUnit startOfColumn;
1403     LayoutUnit endOfColumn;
1404     gridAreaPositionForChild(child, ForColumns, startOfColumn, endOfColumn);
1405     LayoutUnit startPosition = startOfColumn + marginStartForChild(child);
1406     if (hasAutoMarginsInRowAxis(child))
1407         return startPosition;
1408     GridAxisPosition axisPosition = rowAxisPositionForChild(child);
1409     switch (axisPosition) {
1410     case GridAxisStart:
1411         return startPosition;
1412     case GridAxisEnd:
1413     case GridAxisCenter: {
1414         LayoutUnit rowAxisChildSize = GridLayoutFunctions::isOrthogonalChild(*this, child) ? child.logicalHeight() + child.marginLogicalHeight() : child.logicalWidth() + child.marginLogicalWidth();
1415         auto overflow = justifySelfForChild(child).overflow();
1416         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(overflow, endOfColumn - startOfColumn, rowAxisChildSize);
1417         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
1418     }
1419     }
1420
1421     ASSERT_NOT_REACHED();
1422     return 0;
1423 }
1424
1425 bool RenderGrid::gridPositionIsAutoForOutOfFlow(GridPosition position, GridTrackSizingDirection direction) const
1426 {
1427     return position.isAuto() || (position.isNamedGridArea() && !NamedLineCollection::isValidNamedLineOrArea(position.namedGridLine(), style(), GridPositionsResolver::initialPositionSide(direction)));
1428 }
1429
1430 LayoutUnit RenderGrid::resolveAutoStartGridPosition(GridTrackSizingDirection direction) const
1431 {
1432     if (direction == ForRows || style().isLeftToRightDirection())
1433         return LayoutUnit();
1434
1435     int lastLine = numTracks(ForColumns, m_grid);
1436     ContentPosition position = style().resolvedJustifyContentPosition(contentAlignmentNormalBehaviorGrid());
1437     if (position == ContentPosition::End)
1438         return m_columnPositions[lastLine] - clientLogicalWidth();
1439     if (position == ContentPosition::Start || style().resolvedJustifyContentDistribution(contentAlignmentNormalBehaviorGrid()) == ContentDistribution::Stretch)
1440         return m_columnPositions[0] - borderAndPaddingLogicalLeft();
1441     return LayoutUnit();
1442 }
1443
1444 LayoutUnit RenderGrid::resolveAutoEndGridPosition(GridTrackSizingDirection direction) const
1445 {
1446     if (direction == ForRows)
1447         return clientLogicalHeight();
1448     if (style().isLeftToRightDirection())
1449         return clientLogicalWidth();
1450
1451     int lastLine = numTracks(ForColumns, m_grid);
1452     ContentPosition position = style().resolvedJustifyContentPosition(contentAlignmentNormalBehaviorGrid());
1453     if (position == ContentPosition::End)
1454         return m_columnPositions[lastLine];
1455     if (position == ContentPosition::Start || style().resolvedJustifyContentDistribution(contentAlignmentNormalBehaviorGrid()) == ContentDistribution::Stretch)
1456         return m_columnPositions[0] - borderAndPaddingLogicalLeft() + clientLogicalWidth();
1457     return clientLogicalWidth();
1458 }
1459
1460 LayoutUnit RenderGrid::gridAreaBreadthForOutOfFlowChild(const RenderBox& child, GridTrackSizingDirection direction)
1461 {
1462     ASSERT(child.isOutOfFlowPositioned());
1463     bool isRowAxis = direction == ForColumns;
1464     GridSpan span = GridPositionsResolver::resolveGridPositionsFromStyle(style(), child, direction, autoRepeatCountForDirection(direction));
1465     if (span.isIndefinite())
1466         return isRowAxis ? clientLogicalWidth() : clientLogicalHeight();
1467
1468     int smallestStart = abs(m_grid.smallestTrackStart(direction));
1469     int startLine = span.untranslatedStartLine() + smallestStart;
1470     int endLine = span.untranslatedEndLine() + smallestStart;
1471     int lastLine = numTracks(direction, m_grid);
1472     GridPosition startPosition = direction == ForColumns ? child.style().gridItemColumnStart() : child.style().gridItemRowStart();
1473     GridPosition endPosition = direction == ForColumns ? child.style().gridItemColumnEnd() : child.style().gridItemRowEnd();
1474
1475     bool startIsAuto = gridPositionIsAutoForOutOfFlow(startPosition, direction) || startLine < 0 || startLine > lastLine;
1476     bool endIsAuto = gridPositionIsAutoForOutOfFlow(endPosition, direction) || endLine < 0 || endLine > lastLine;
1477
1478     if (startIsAuto && endIsAuto)
1479         return isRowAxis ? clientLogicalWidth() : clientLogicalHeight();
1480
1481     LayoutUnit start;
1482     LayoutUnit end;
1483     auto& positions = isRowAxis ? m_columnPositions : m_rowPositions;
1484     auto& outOfFlowItemLine = isRowAxis ? m_outOfFlowItemColumn : m_outOfFlowItemRow;
1485     LayoutUnit borderEdge = isRowAxis ? borderLogicalLeft() : borderBefore();
1486     if (startIsAuto)
1487         start = resolveAutoStartGridPosition(direction) + borderEdge;
1488     else {
1489         outOfFlowItemLine.set(&child, startLine);
1490         start = positions[startLine];
1491     }
1492     if (endIsAuto)
1493         end = resolveAutoEndGridPosition(direction) + borderEdge;
1494     else {
1495         end = positions[endLine];
1496         // These vectors store line positions including gaps, but we shouldn't consider them for the edges of the grid.
1497         std::optional<LayoutUnit> availableSizeForGutters = availableSpaceForGutters(direction);
1498         if (endLine > 0 && endLine < lastLine) {
1499             ASSERT(!m_grid.needsItemsPlacement());
1500             end -= guttersSize(m_grid, direction, endLine - 1, 2, availableSizeForGutters);
1501             end -= isRowAxis ? m_offsetBetweenColumns.distributionOffset : m_offsetBetweenRows.distributionOffset;
1502         }
1503     }
1504     return std::max(end - start, LayoutUnit());
1505 }
1506
1507 LayoutUnit RenderGrid::logicalOffsetForChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit trackBreadth) const
1508 {
1509     if (hasStaticPositionForChild(child, direction))
1510         return LayoutUnit();
1511
1512     bool isRowAxis = direction == ForColumns;
1513     bool isFlowAwareRowAxis = GridLayoutFunctions::flowAwareDirectionForChild(*this, child, direction) == ForColumns;
1514     LayoutUnit childPosition = isFlowAwareRowAxis ? child.logicalLeft() : child.logicalTop();
1515     LayoutUnit gridBorder = isRowAxis ? borderLogicalLeft() : borderBefore();
1516     LayoutUnit childMargin = isFlowAwareRowAxis ? child.marginLogicalLeft() : child.marginBefore();
1517     LayoutUnit offset = childPosition - gridBorder - childMargin;
1518     if (!isRowAxis || style().isLeftToRightDirection())
1519         return offset;
1520
1521     LayoutUnit childBreadth = isFlowAwareRowAxis ? child.logicalWidth() + child.marginLogicalWidth() : child.logicalHeight() + child.marginLogicalHeight();
1522     return trackBreadth - offset - childBreadth;
1523 }
1524
1525 void RenderGrid::gridAreaPositionForOutOfFlowChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit& start, LayoutUnit& end) const
1526 {
1527     ASSERT(child.isOutOfFlowPositioned());
1528     ASSERT(GridLayoutFunctions::hasOverrideContainingBlockContentSizeForChild(child, direction));
1529     LayoutUnit trackBreadth = GridLayoutFunctions::overrideContainingBlockContentSizeForChild(child, direction).value();
1530     bool isRowAxis = direction == ForColumns;
1531     auto& outOfFlowItemLine = isRowAxis ? m_outOfFlowItemColumn : m_outOfFlowItemRow;
1532     start = isRowAxis ? borderLogicalLeft() : borderBefore();
1533     if (auto line = outOfFlowItemLine.get(&child)) {
1534         auto& positions = isRowAxis ? m_columnPositions : m_rowPositions;
1535         start = positions[line.value()];
1536     }
1537     start += logicalOffsetForChild(child, direction, trackBreadth);
1538     end = start + trackBreadth;
1539 }
1540
1541 void RenderGrid::gridAreaPositionForInFlowChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit& start, LayoutUnit& end) const
1542 {
1543     ASSERT(!child.isOutOfFlowPositioned());
1544     const GridSpan& span = m_grid.gridItemSpan(child, direction);
1545     // FIXME (lajava): This is a common pattern, why not defining a function like
1546     // positions(direction) ?
1547     auto& positions = direction == ForColumns ? m_columnPositions : m_rowPositions;
1548     start = positions[span.startLine()];
1549     end = positions[span.endLine()];
1550     // The 'positions' vector includes distribution offset (because of content
1551     // alignment) and gutters so we need to subtract them to get the actual
1552     // end position for a given track (this does not have to be done for the
1553     // last track as there are no more positions's elements after it, nor for
1554     // collapsed tracks).
1555     if (span.endLine() < positions.size() - 1
1556         && !(m_grid.hasAutoRepeatEmptyTracks(direction)
1557         && m_grid.isEmptyAutoRepeatTrack(direction, span.endLine()))) {
1558         end -= gridGap(direction) + gridItemOffset(direction);
1559     }
1560 }
1561
1562 void RenderGrid::gridAreaPositionForChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit& start, LayoutUnit& end) const
1563 {
1564     if (child.isOutOfFlowPositioned())
1565         gridAreaPositionForOutOfFlowChild(child, direction, start, end);
1566     else
1567         gridAreaPositionForInFlowChild(child, direction, start, end);
1568 }
1569
1570 ContentPosition static resolveContentDistributionFallback(ContentDistribution distribution)
1571 {
1572     switch (distribution) {
1573     case ContentDistribution::SpaceBetween:
1574         return ContentPosition::Start;
1575     case ContentDistribution::SpaceAround:
1576         return ContentPosition::Center;
1577     case ContentDistribution::SpaceEvenly:
1578         return ContentPosition::Center;
1579     case ContentDistribution::Stretch:
1580         return ContentPosition::Start;
1581     case ContentDistribution::Default:
1582         return ContentPosition::Normal;
1583     }
1584
1585     ASSERT_NOT_REACHED();
1586     return ContentPosition::Normal;
1587 }
1588
1589 static void contentDistributionOffset(ContentAlignmentData& offset, const LayoutUnit& availableFreeSpace, ContentPosition& fallbackPosition, ContentDistribution distribution, unsigned numberOfGridTracks)
1590 {
1591     if (distribution != ContentDistribution::Default && fallbackPosition == ContentPosition::Normal)
1592         fallbackPosition = resolveContentDistributionFallback(distribution);
1593
1594     // Initialize to an invalid offset.
1595     offset.positionOffset = LayoutUnit(-1);
1596     offset.distributionOffset = LayoutUnit(-1);
1597     if (availableFreeSpace <= 0)
1598         return;
1599
1600     LayoutUnit positionOffset;
1601     LayoutUnit distributionOffset;
1602     switch (distribution) {
1603     case ContentDistribution::SpaceBetween:
1604         if (numberOfGridTracks < 2)
1605             return;
1606         distributionOffset = availableFreeSpace / (numberOfGridTracks - 1);
1607         positionOffset = LayoutUnit();
1608         break;
1609     case ContentDistribution::SpaceAround:
1610         if (numberOfGridTracks < 1)
1611             return;
1612         distributionOffset = availableFreeSpace / numberOfGridTracks;
1613         positionOffset = distributionOffset / 2;
1614         break;
1615     case ContentDistribution::SpaceEvenly:
1616         distributionOffset = availableFreeSpace / (numberOfGridTracks + 1);
1617         positionOffset = distributionOffset;
1618         break;
1619     case ContentDistribution::Stretch:
1620     case ContentDistribution::Default:
1621         return;
1622     default:
1623         ASSERT_NOT_REACHED();
1624         return;
1625     }
1626
1627     offset.positionOffset = positionOffset;
1628     offset.distributionOffset = distributionOffset;
1629 }
1630
1631 StyleContentAlignmentData RenderGrid::contentAlignment(GridTrackSizingDirection direction) const
1632 {
1633     return direction == ForColumns ? style().resolvedJustifyContent(contentAlignmentNormalBehaviorGrid()) : style().resolvedAlignContent(contentAlignmentNormalBehaviorGrid());
1634 }
1635
1636 void RenderGrid::computeContentPositionAndDistributionOffset(GridTrackSizingDirection direction, const LayoutUnit& availableFreeSpace, unsigned numberOfGridTracks)
1637 {
1638     bool isRowAxis = direction == ForColumns;
1639     auto& offset =
1640         isRowAxis ? m_offsetBetweenColumns : m_offsetBetweenRows;
1641     auto contentAlignmentData = contentAlignment(direction);
1642     auto position = contentAlignmentData.position();
1643     // If <content-distribution> value can't be applied, 'position' will become the associated
1644     // <content-position> fallback value.
1645     contentDistributionOffset(offset, availableFreeSpace, position, contentAlignmentData.distribution(), numberOfGridTracks);
1646     if (offset.isValid())
1647         return;
1648
1649     if (availableFreeSpace <= 0 && contentAlignmentData.overflow() == OverflowAlignment::Safe) {
1650         offset.positionOffset = LayoutUnit();
1651         offset.distributionOffset = LayoutUnit();
1652         return;
1653     }
1654
1655     LayoutUnit positionOffset;
1656     switch (position) {
1657     case ContentPosition::Left:
1658         ASSERT(isRowAxis);
1659         break;
1660     case ContentPosition::Right:
1661         ASSERT(isRowAxis);
1662         positionOffset = availableFreeSpace;
1663         break;
1664     case ContentPosition::Center:
1665         positionOffset = availableFreeSpace / 2;
1666         break;
1667     case ContentPosition::FlexEnd: // Only used in flex layout, for other layout, it's equivalent to 'end'.
1668     case ContentPosition::End:
1669         if (isRowAxis)
1670             positionOffset = style().isLeftToRightDirection() ? availableFreeSpace : LayoutUnit();
1671         else
1672             positionOffset = availableFreeSpace;
1673         break;
1674     case ContentPosition::FlexStart: // Only used in flex layout, for other layout, it's equivalent to 'start'.
1675     case ContentPosition::Start:
1676         if (isRowAxis)
1677             positionOffset = style().isLeftToRightDirection() ? LayoutUnit() : availableFreeSpace;
1678         break;
1679     case ContentPosition::Baseline:
1680     case ContentPosition::LastBaseline:
1681         // FIXME: Implement the previous values. For now, we always 'start' align.
1682         // http://webkit.org/b/145566
1683         if (isRowAxis)
1684             positionOffset = style().isLeftToRightDirection() ? LayoutUnit() : availableFreeSpace;
1685         break;
1686     case ContentPosition::Normal:
1687     default:
1688         ASSERT_NOT_REACHED();
1689         return;
1690     }
1691
1692     offset.positionOffset = positionOffset;
1693     offset.distributionOffset = LayoutUnit();
1694 }
1695
1696 LayoutUnit RenderGrid::translateOutOfFlowRTLCoordinate(const RenderBox& child, LayoutUnit coordinate) const
1697 {
1698     ASSERT(child.isOutOfFlowPositioned());
1699     ASSERT(!style().isLeftToRightDirection());
1700
1701     if (m_outOfFlowItemColumn.get(&child))
1702         return translateRTLCoordinate(coordinate);
1703
1704     return borderLogicalLeft() + borderLogicalRight() + clientLogicalWidth() - coordinate;
1705 }
1706
1707 LayoutUnit RenderGrid::translateRTLCoordinate(LayoutUnit coordinate) const
1708 {
1709     ASSERT(!style().isLeftToRightDirection());
1710
1711     LayoutUnit alignmentOffset = m_columnPositions[0];
1712     LayoutUnit rightGridEdgePosition = m_columnPositions[m_columnPositions.size() - 1];
1713     return rightGridEdgePosition + alignmentOffset - coordinate;
1714 }
1715
1716 LayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox& child) const
1717 {
1718     LayoutUnit columnAxisOffset = columnAxisOffsetForChild(child);
1719     LayoutUnit rowAxisOffset = rowAxisOffsetForChild(child);
1720     bool isOrthogonalChild = GridLayoutFunctions::isOrthogonalChild(*this, child);
1721
1722     // We stored m_columnPositions's data ignoring the direction, hence we might need now
1723     // to translate positions from RTL to LTR, as it's more convenient for painting.
1724     if (!style().isLeftToRightDirection())
1725         rowAxisOffset = (child.isOutOfFlowPositioned() ? translateOutOfFlowRTLCoordinate(child, rowAxisOffset) : translateRTLCoordinate(rowAxisOffset)) - (isOrthogonalChild ? child.logicalHeight()  : child.logicalWidth());
1726
1727     // "In the positioning phase [...] calculations are performed according to the writing mode
1728     // of the containing block of the box establishing the orthogonal flow." However, the
1729     // resulting LayoutPoint will be used in 'setLogicalPosition' in order to set the child's
1730     // logical position, which will only take into account the child's writing-mode.
1731     LayoutPoint childLocation(rowAxisOffset, columnAxisOffset);
1732     return isOrthogonalChild ? childLocation.transposedPoint() : childLocation;
1733 }
1734
1735 unsigned RenderGrid::nonCollapsedTracks(GridTrackSizingDirection direction) const
1736 {
1737     auto& tracks = m_trackSizingAlgorithm.tracks(direction);
1738     size_t numberOfTracks = tracks.size();
1739     bool hasCollapsedTracks = m_grid.hasAutoRepeatEmptyTracks(direction);
1740     size_t numberOfCollapsedTracks = hasCollapsedTracks ? m_grid.autoRepeatEmptyTracks(direction)->size() : 0;
1741     return numberOfTracks - numberOfCollapsedTracks;
1742 }
1743
1744 unsigned RenderGrid::numTracks(GridTrackSizingDirection direction, const Grid& grid) const
1745 {
1746     // Due to limitations in our internal representation, we cannot know the number of columns from
1747     // m_grid *if* there is no row (because m_grid would be empty). That's why in that case we need
1748     // to get it from the style. Note that we know for sure that there are't any implicit tracks,
1749     // because not having rows implies that there are no "normal" children (out-of-flow children are
1750     // not stored in m_grid).
1751     ASSERT(!grid.needsItemsPlacement());
1752     if (direction == ForRows)
1753         return grid.numTracks(ForRows);
1754
1755     // FIXME: This still requires knowledge about m_grid internals.
1756     return grid.numTracks(ForRows) ? grid.numTracks(ForColumns) : GridPositionsResolver::explicitGridColumnCount(style(), grid.autoRepeatTracks(ForColumns));
1757 }
1758
1759 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset, PaintInfo& forChild, bool usePrintRect)
1760 {
1761     ASSERT(!m_grid.needsItemsPlacement());
1762     for (RenderBox* child = m_grid.orderIterator().first(); child; child = m_grid.orderIterator().next())
1763         paintChild(*child, paintInfo, paintOffset, forChild, usePrintRect, PaintAsInlineBlock);
1764 }
1765
1766 const char* RenderGrid::renderName() const
1767 {
1768     if (isFloating())
1769         return "RenderGrid (floating)";
1770     if (isOutOfFlowPositioned())
1771         return "RenderGrid (positioned)";
1772     if (isAnonymous())
1773         return "RenderGrid (generated)";
1774     if (isRelativelyPositioned())
1775         return "RenderGrid (relative positioned)";
1776     return "RenderGrid";
1777 }
1778
1779 } // namespace WebCore