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