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