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