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