Reduce ResourceRequest copying in loading code
[WebKit-https.git] / Source / WebCore / rendering / RenderGrid.cpp
1 /*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
3  * Copyright (C) 2013, 2014 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 #if ENABLE(CSS_GRID_LAYOUT)
31
32 #include "GridArea.h"
33 #include "GridPositionsResolver.h"
34 #include "LayoutRepainter.h"
35 #include "RenderLayer.h"
36 #include "RenderView.h"
37 #include <cstdlib>
38
39 namespace WebCore {
40
41 static const int infinity = -1;
42 static constexpr ItemPosition selfAlignmentNormalBehavior = ItemPositionStretch;
43
44 class GridTrack {
45 public:
46     GridTrack() {}
47
48     const LayoutUnit& baseSize() const
49     {
50         ASSERT(isGrowthLimitBiggerThanBaseSize());
51         return m_baseSize;
52     }
53
54     const LayoutUnit& growthLimit() const
55     {
56         ASSERT(isGrowthLimitBiggerThanBaseSize());
57         return m_growthLimit;
58     }
59
60     void setBaseSize(LayoutUnit baseSize)
61     {
62         m_baseSize = baseSize;
63         ensureGrowthLimitIsBiggerThanBaseSize();
64     }
65
66     void setGrowthLimit(LayoutUnit growthLimit)
67     {
68         m_growthLimit = growthLimit;
69         ensureGrowthLimitIsBiggerThanBaseSize();
70     }
71
72     bool growthLimitIsInfinite() const
73     {
74         return m_growthLimit == infinity;
75     }
76
77     bool infiniteGrowthPotential() const
78     {
79         return growthLimitIsInfinite() || m_infinitelyGrowable;
80     }
81
82     const LayoutUnit& growthLimitIfNotInfinite() const
83     {
84         ASSERT(isGrowthLimitBiggerThanBaseSize());
85         return (m_growthLimit == infinity) ? m_baseSize : m_growthLimit;
86     }
87
88     const LayoutUnit& plannedSize() const { return m_plannedSize; }
89
90     void setPlannedSize(LayoutUnit plannedSize)
91     {
92         m_plannedSize = plannedSize;
93     }
94
95     LayoutUnit& tempSize() { return m_tempSize; }
96
97     bool infinitelyGrowable() const { return m_infinitelyGrowable; }
98
99     void setInfinitelyGrowable(bool infinitelyGrowable)
100     {
101         m_infinitelyGrowable = infinitelyGrowable;
102     }
103
104 private:
105     bool isGrowthLimitBiggerThanBaseSize() const { return growthLimitIsInfinite() || m_growthLimit >= m_baseSize; }
106
107     void ensureGrowthLimitIsBiggerThanBaseSize()
108     {
109         if (m_growthLimit != infinity && m_growthLimit < m_baseSize)
110             m_growthLimit = m_baseSize;
111     }
112
113     LayoutUnit m_baseSize { 0 };
114     LayoutUnit m_growthLimit { 0 };
115     LayoutUnit m_plannedSize { 0 };
116     LayoutUnit m_tempSize { 0 };
117     bool m_infinitelyGrowable { false };
118 };
119
120 struct ContentAlignmentData {
121     WTF_MAKE_FAST_ALLOCATED;
122 public:
123     bool isValid() { return positionOffset >= 0 && distributionOffset >= 0; }
124     static ContentAlignmentData defaultOffsets() { return {-1, -1}; }
125
126     LayoutUnit positionOffset;
127     LayoutUnit distributionOffset;
128 };
129
130 class RenderGrid::GridIterator {
131     WTF_MAKE_NONCOPYABLE(GridIterator);
132 public:
133     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
134     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
135     GridIterator(const Vector<Vector<Vector<RenderBox*, 1>>>& grid, GridTrackSizingDirection direction, unsigned fixedTrackIndex, unsigned varyingTrackIndex = 0)
136         : m_grid(grid)
137         , m_direction(direction)
138         , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
139         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
140         , m_childIndex(0)
141     {
142         ASSERT(!m_grid.isEmpty());
143         ASSERT(!m_grid[0].isEmpty());
144         ASSERT(m_rowIndex < m_grid.size());
145         ASSERT(m_columnIndex < m_grid[0].size());
146     }
147
148     RenderBox* nextGridItem()
149     {
150         ASSERT(!m_grid.isEmpty());
151         ASSERT(!m_grid[0].isEmpty());
152
153         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
154         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
155         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
156             const auto& children = m_grid[m_rowIndex][m_columnIndex];
157             if (m_childIndex < children.size())
158                 return children[m_childIndex++];
159
160             m_childIndex = 0;
161         }
162         return 0;
163     }
164
165     bool isEmptyAreaEnough(unsigned rowSpan, unsigned columnSpan) const
166     {
167         ASSERT(!m_grid.isEmpty());
168         ASSERT(!m_grid[0].isEmpty());
169
170         // Ignore cells outside current grid as we will grow it later if needed.
171         unsigned maxRows = std::min<unsigned>(m_rowIndex + rowSpan, m_grid.size());
172         unsigned maxColumns = std::min<unsigned>(m_columnIndex + columnSpan, m_grid[0].size());
173
174         // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
175         for (unsigned row = m_rowIndex; row < maxRows; ++row) {
176             for (unsigned column = m_columnIndex; column < maxColumns; ++column) {
177                 auto& children = m_grid[row][column];
178                 if (!children.isEmpty())
179                     return false;
180             }
181         }
182
183         return true;
184     }
185
186     std::unique_ptr<GridArea> nextEmptyGridArea(unsigned fixedTrackSpan, unsigned varyingTrackSpan)
187     {
188         ASSERT(!m_grid.isEmpty());
189         ASSERT(!m_grid[0].isEmpty());
190         ASSERT(fixedTrackSpan >= 1);
191         ASSERT(varyingTrackSpan >= 1);
192
193         if (m_grid.isEmpty())
194             return nullptr;
195
196         unsigned rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
197         unsigned columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
198
199         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
200         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
201         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
202             if (isEmptyAreaEnough(rowSpan, columnSpan)) {
203                 std::unique_ptr<GridArea> result = std::make_unique<GridArea>(GridSpan::translatedDefiniteGridSpan(m_rowIndex, m_rowIndex + rowSpan), GridSpan::translatedDefiniteGridSpan(m_columnIndex, m_columnIndex + columnSpan));
204                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
205                 ++varyingTrackIndex;
206                 return result;
207             }
208         }
209         return nullptr;
210     }
211
212 private:
213     const Vector<Vector<Vector<RenderBox*, 1>>>& m_grid;
214     GridTrackSizingDirection m_direction;
215     unsigned m_rowIndex;
216     unsigned m_columnIndex;
217     unsigned m_childIndex;
218 };
219
220 class RenderGrid::GridSizingData {
221     WTF_MAKE_NONCOPYABLE(GridSizingData);
222 public:
223     GridSizingData(unsigned gridColumnCount, unsigned gridRowCount)
224         : columnTracks(gridColumnCount)
225         , rowTracks(gridRowCount)
226     {
227     }
228
229     Vector<GridTrack> columnTracks;
230     Vector<GridTrack> rowTracks;
231     Vector<unsigned> contentSizedTracksIndex;
232
233     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
234     Vector<GridTrack*> filteredTracks;
235     Vector<GridTrack*> growBeyondGrowthLimitsTracks;
236     Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
237
238     Optional<LayoutUnit> freeSpaceForDirection(GridTrackSizingDirection direction) { return direction == ForColumns ? freeSpaceForColumns : freeSpaceForRows; }
239     void setFreeSpaceForDirection(GridTrackSizingDirection, Optional<LayoutUnit> freeSpace);
240
241     enum SizingOperation { TrackSizing, IntrinsicSizeComputation };
242     SizingOperation sizingOperation { TrackSizing };
243
244 private:
245     Optional<LayoutUnit> freeSpaceForColumns;
246     Optional<LayoutUnit> freeSpaceForRows;
247 };
248
249 void RenderGrid::GridSizingData::setFreeSpaceForDirection(GridTrackSizingDirection direction, Optional<LayoutUnit> freeSpace)
250 {
251     if (direction == ForColumns)
252         freeSpaceForColumns = freeSpace;
253     else
254         freeSpaceForRows = freeSpace;
255 }
256
257 RenderGrid::RenderGrid(Element& element, RenderStyle&& style)
258     : RenderBlock(element, WTFMove(style), 0)
259     , m_orderIterator(*this)
260 {
261     // All of our children must be block level.
262     setChildrenInline(false);
263 }
264
265 RenderGrid::~RenderGrid()
266 {
267 }
268
269 static inline bool defaultAlignmentIsStretch(ItemPosition position)
270 {
271     return position == ItemPositionStretch || position == ItemPositionAuto;
272 }
273
274 static inline bool defaultAlignmentChangedToStretchInRowAxis(const RenderStyle& oldStyle, const RenderStyle& newStyle)
275 {
276     return !defaultAlignmentIsStretch(oldStyle.justifyItems().position()) && defaultAlignmentIsStretch(newStyle.justifyItems().position());
277 }
278
279 static inline bool defaultAlignmentChangedFromStretchInRowAxis(const RenderStyle& oldStyle, const RenderStyle& newStyle)
280 {
281     return defaultAlignmentIsStretch(oldStyle.justifyItems().position()) && !defaultAlignmentIsStretch(newStyle.justifyItems().position());
282 }
283
284 static inline bool defaultAlignmentChangedFromStretchInColumnAxis(const RenderStyle& oldStyle, const RenderStyle& newStyle)
285 {
286     return defaultAlignmentIsStretch(oldStyle.alignItems().position()) && !defaultAlignmentIsStretch(newStyle.alignItems().position());
287 }
288
289 static inline bool selfAlignmentChangedToStretchInRowAxis(const RenderStyle& oldStyle, const RenderStyle& newStyle, const RenderStyle& childStyle)
290 {
291     return childStyle.resolvedJustifySelf(oldStyle, selfAlignmentNormalBehavior).position() != ItemPositionStretch
292         && childStyle.resolvedJustifySelf(newStyle, selfAlignmentNormalBehavior).position() == ItemPositionStretch;
293 }
294
295 static inline bool selfAlignmentChangedFromStretchInRowAxis(const RenderStyle& oldStyle, const RenderStyle& newStyle, const RenderStyle& childStyle)
296 {
297     return childStyle.resolvedJustifySelf(oldStyle, selfAlignmentNormalBehavior).position() == ItemPositionStretch
298         && childStyle.resolvedJustifySelf(newStyle, selfAlignmentNormalBehavior).position() != ItemPositionStretch;
299 }
300
301 static inline bool selfAlignmentChangedFromStretchInColumnAxis(const RenderStyle& oldStyle, const RenderStyle& newStyle, const RenderStyle& childStyle)
302 {
303     return childStyle.resolvedAlignSelf(oldStyle, selfAlignmentNormalBehavior).position() == ItemPositionStretch
304         && childStyle.resolvedAlignSelf(newStyle, selfAlignmentNormalBehavior).position() != ItemPositionStretch;
305 }
306
307 void RenderGrid::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
308 {
309     RenderBlock::styleDidChange(diff, oldStyle);
310     if (!oldStyle || diff != StyleDifferenceLayout)
311         return;
312
313     const RenderStyle& newStyle = style();
314     if (defaultAlignmentChangedToStretchInRowAxis(*oldStyle, newStyle) || defaultAlignmentChangedFromStretchInRowAxis(*oldStyle, newStyle)
315         || defaultAlignmentChangedFromStretchInColumnAxis(*oldStyle, newStyle)) {
316         // Grid items that were not previously stretched in row-axis need to be relayed out so we can compute new available space.
317         // Grid items that were previously stretching in column-axis need to be relayed out so we can compute new available space.
318         // This is only necessary for stretching since other alignment values don't change the size of the box.
319         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
320             if (child->isOutOfFlowPositioned())
321                 continue;
322             if (selfAlignmentChangedToStretchInRowAxis(*oldStyle, newStyle, child->style()) || selfAlignmentChangedFromStretchInRowAxis(*oldStyle, newStyle, child->style())
323                 || selfAlignmentChangedFromStretchInColumnAxis(*oldStyle, newStyle, child->style())) {
324                 child->setChildNeedsLayout(MarkOnlyThis);
325             }
326         }
327     }
328 }
329
330 unsigned RenderGrid::gridColumnCount() const
331 {
332     ASSERT(!m_gridIsDirty);
333     // Due to limitations in our internal representation, we cannot know the number of columns from
334     // m_grid *if* there is no row (because m_grid would be empty). That's why in that case we need
335     // to get it from the style. Note that we know for sure that there are't any implicit tracks,
336     // because not having rows implies that there are no "normal" children (out-of-flow children are
337     // not stored in m_grid).
338     return m_grid.size() ? m_grid[0].size() : GridPositionsResolver::explicitGridColumnCount(style(), m_autoRepeatColumns);
339 }
340
341 unsigned RenderGrid::gridRowCount() const
342 {
343     ASSERT(!m_gridIsDirty);
344     return m_grid.size();
345 }
346
347 LayoutUnit RenderGrid::computeTrackBasedLogicalHeight(const GridSizingData& sizingData) const
348 {
349     LayoutUnit logicalHeight;
350
351     for (const auto& row : sizingData.rowTracks)
352         logicalHeight += row.baseSize();
353
354     logicalHeight += guttersSize(ForRows, sizingData.rowTracks.size());
355
356     return logicalHeight;
357 }
358
359 void RenderGrid::computeTrackSizesForDirection(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit freeSpace)
360 {
361     LayoutUnit totalGuttersSize = guttersSize(direction, direction == ForRows ? gridRowCount() : gridColumnCount());
362     sizingData.setFreeSpaceForDirection(direction, freeSpace - totalGuttersSize);
363     sizingData.sizingOperation = GridSizingData::TrackSizing;
364
365     LayoutUnit baseSizes, growthLimits;
366     computeUsedBreadthOfGridTracks(direction, sizingData, baseSizes, growthLimits);
367     ASSERT(tracksAreWiderThanMinTrackBreadth(direction, sizingData));
368 }
369
370 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
371 {
372     ASSERT(needsLayout());
373
374     if (!relayoutChildren && simplifiedLayout())
375         return;
376
377     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
378     LayoutStateMaintainer statePusher(view(), *this, locationOffset(), hasTransform() || hasReflection() || style().isFlippedBlocksWritingMode());
379
380     preparePaginationBeforeBlockLayout(relayoutChildren);
381
382     LayoutSize previousSize = size();
383
384     setLogicalHeight(0);
385     updateLogicalWidth();
386     bool logicalHeightWasIndefinite = !computeContentLogicalHeight(MainOrPreferredSize, style().logicalHeight(), Nullopt);
387
388     placeItemsOnGrid();
389
390     GridSizingData sizingData(gridColumnCount(), gridRowCount());
391
392     // At this point the logical width is always definite as the above call to updateLogicalWidth()
393     // properly resolves intrinsic sizes. We cannot do the same for heights though because many code
394     // paths inside updateLogicalHeight() require a previous call to setLogicalHeight() to resolve
395     // heights properly (like for positioned items for example).
396     computeTrackSizesForDirection(ForColumns, sizingData, availableLogicalWidth());
397
398     if (logicalHeightWasIndefinite)
399         computeIntrinsicLogicalHeight(sizingData);
400     else
401         computeTrackSizesForDirection(ForRows, sizingData, availableLogicalHeight(ExcludeMarginBorderPadding));
402     setLogicalHeight(computeTrackBasedLogicalHeight(sizingData) + borderAndPaddingLogicalHeight());
403
404     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
405     updateLogicalHeight();
406
407     // The above call might have changed the grid's logical height depending on min|max height restrictions.
408     // Update the sizes of the rows whose size depends on the logical height (also on definite|indefinite sizes).
409     if (logicalHeightWasIndefinite)
410         computeTrackSizesForDirection(ForRows, sizingData, contentLogicalHeight());
411
412     // Grid container should have the minimum height of a line if it's editable. That does not affect track sizing though.
413     if (hasLineIfEmpty()) {
414         LayoutUnit minHeightForEmptyLine = borderAndPaddingLogicalHeight()
415             + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes)
416             + scrollbarLogicalHeight();
417         setLogicalHeight(std::max(logicalHeight(), minHeightForEmptyLine));
418     }
419
420     applyStretchAlignmentToTracksIfNeeded(ForColumns, sizingData);
421     applyStretchAlignmentToTracksIfNeeded(ForRows, sizingData);
422
423     layoutGridItems(sizingData);
424
425     if (size() != previousSize)
426         relayoutChildren = true;
427
428     layoutPositionedObjects(relayoutChildren || isDocumentElementRenderer());
429
430     clearGrid();
431
432     computeOverflow(oldClientAfterEdge);
433     statePusher.pop();
434
435     updateLayerTransform();
436
437     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
438     // we overflow or not.
439     updateScrollInfoAfterLayout();
440
441     repainter.repaintAfterLayout();
442
443     clearNeedsLayout();
444 }
445
446 LayoutUnit RenderGrid::guttersSize(GridTrackSizingDirection direction, unsigned span) const
447 {
448     if (span <= 1)
449         return { };
450
451     const Length& trackGap = direction == ForColumns ? style().gridColumnGap() : style().gridRowGap();
452     return valueForLength(trackGap, 0) * (span - 1);
453 }
454
455 LayoutUnit RenderGrid::offsetBetweenTracks(GridTrackSizingDirection direction) const
456 {
457     return direction == ForColumns ? m_offsetBetweenColumns : m_offsetBetweenRows;
458 }
459
460 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
461 {
462     bool wasPopulated = !m_gridIsDirty;
463     if (!wasPopulated)
464         const_cast<RenderGrid*>(this)->placeItemsOnGrid();
465
466     GridSizingData sizingData(gridColumnCount(), gridRowCount());
467     sizingData.setFreeSpaceForDirection(ForColumns, Nullopt);
468     sizingData.sizingOperation = GridSizingData::IntrinsicSizeComputation;
469     const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, minLogicalWidth, maxLogicalWidth);
470
471     LayoutUnit totalGuttersSize = guttersSize(ForColumns, sizingData.columnTracks.size());
472     minLogicalWidth += totalGuttersSize;
473     maxLogicalWidth += totalGuttersSize;
474
475     LayoutUnit scrollbarWidth = intrinsicScrollbarLogicalWidth();
476     minLogicalWidth += scrollbarWidth;
477     maxLogicalWidth += scrollbarWidth;
478
479     if (!wasPopulated)
480         const_cast<RenderGrid*>(this)->clearGrid();
481 }
482
483 void RenderGrid::computeIntrinsicLogicalHeight(GridSizingData& sizingData)
484 {
485     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData));
486     sizingData.setFreeSpaceForDirection(ForRows, Nullopt);
487     sizingData.sizingOperation = GridSizingData::IntrinsicSizeComputation;
488     LayoutUnit minHeight, maxHeight;
489     computeUsedBreadthOfGridTracks(ForRows, sizingData, minHeight, maxHeight);
490
491     // FIXME: This should be really added to the intrinsic height in RenderBox::computeContentAndScrollbarLogicalHeightUsing().
492     // Remove this when that is fixed.
493     LayoutUnit scrollbarHeight = scrollbarLogicalHeight();
494     minHeight += scrollbarHeight;
495     maxHeight += scrollbarHeight;
496
497     LayoutUnit totalGuttersSize = guttersSize(ForRows, gridRowCount());
498     minHeight += totalGuttersSize;
499     maxHeight += totalGuttersSize;
500
501     m_minContentHeight = minHeight;
502     m_maxContentHeight = maxHeight;
503
504     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData));
505 }
506
507 Optional<LayoutUnit> RenderGrid::computeIntrinsicLogicalContentHeightUsing(Length logicalHeightLength, Optional<LayoutUnit> intrinsicLogicalHeight, LayoutUnit borderAndPadding) const
508 {
509     if (!intrinsicLogicalHeight)
510         return Nullopt;
511
512     if (logicalHeightLength.isMinContent())
513         return m_minContentHeight;
514
515     if (logicalHeightLength.isMaxContent())
516         return m_maxContentHeight;
517
518     if (logicalHeightLength.isFitContent()) {
519         LayoutUnit fillAvailableExtent = containingBlock()->availableLogicalHeight(ExcludeMarginBorderPadding);
520         return std::min(m_maxContentHeight.valueOr(0), std::max(m_minContentHeight.valueOr(0), fillAvailableExtent));
521     }
522
523     if (logicalHeightLength.isFillAvailable())
524         return containingBlock()->availableLogicalHeight(ExcludeMarginBorderPadding) - borderAndPadding;
525     ASSERT_NOT_REACHED();
526     return Nullopt;
527 }
528
529 static inline double normalizedFlexFraction(const GridTrack& track, double flexFactor)
530 {
531     return track.baseSize() / std::max<double>(1, flexFactor);
532 }
533
534 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& baseSizesWithoutMaximization, LayoutUnit& growthLimitsWithoutMaximization)
535 {
536     const Optional<LayoutUnit> initialFreeSpace = sizingData.freeSpaceForDirection(direction);
537     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
538     Vector<unsigned> flexibleSizedTracksIndex;
539     sizingData.contentSizedTracksIndex.shrink(0);
540
541     LayoutUnit maxSize = initialFreeSpace.valueOr(0);
542     // Grid gutters were removed from freeSpace by the caller (if freeSpace is definite),
543     // but we must use them to compute relative (i.e. percentages) sizes.
544     if (initialFreeSpace)
545         maxSize += guttersSize(direction, direction == ForColumns ? gridColumnCount() : gridRowCount());
546
547     // 1. Initialize per Grid track variables.
548     for (unsigned i = 0; i < tracks.size(); ++i) {
549         GridTrack& track = tracks[i];
550         const GridTrackSize& trackSize = gridTrackSize(direction, i);
551         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
552         const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
553
554         track.setBaseSize(computeUsedBreadthOfMinLength(minTrackBreadth, maxSize));
555         track.setGrowthLimit(computeUsedBreadthOfMaxLength(maxTrackBreadth, track.baseSize(), maxSize));
556         track.setInfinitelyGrowable(false);
557
558         if (trackSize.isContentSized())
559             sizingData.contentSizedTracksIndex.append(i);
560         if (trackSize.maxTrackBreadth().isFlex())
561             flexibleSizedTracksIndex.append(i);
562     }
563
564     // 2. Resolve content-based TrackSizingFunctions.
565     if (!sizingData.contentSizedTracksIndex.isEmpty())
566         resolveContentBasedTrackSizingFunctions(direction, sizingData);
567
568     baseSizesWithoutMaximization = growthLimitsWithoutMaximization = 0;
569
570     for (auto& track : tracks) {
571         ASSERT(!track.growthLimitIsInfinite());
572         baseSizesWithoutMaximization += track.baseSize();
573         growthLimitsWithoutMaximization += track.growthLimit();
574     }
575     LayoutUnit freeSpace = initialFreeSpace ? initialFreeSpace.value() - baseSizesWithoutMaximization : LayoutUnit(0);
576
577     const bool hasDefiniteFreeSpace = !!initialFreeSpace;
578
579     if (hasDefiniteFreeSpace && freeSpace <= 0) {
580         sizingData.setFreeSpaceForDirection(direction, freeSpace);
581         return;
582     }
583
584     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until freeSpace is exhausted.
585     if (hasDefiniteFreeSpace) {
586         const unsigned tracksSize = tracks.size();
587         Vector<GridTrack*> tracksForDistribution(tracksSize);
588         for (unsigned i = 0; i < tracksSize; ++i) {
589             tracksForDistribution[i] = tracks.data() + i;
590             tracksForDistribution[i]->setPlannedSize(tracksForDistribution[i]->baseSize());
591         }
592
593         distributeSpaceToTracks<MaximizeTracks>(tracksForDistribution, nullptr, freeSpace);
594
595         for (auto* track : tracksForDistribution)
596             track->setBaseSize(track->plannedSize());
597     } else {
598         for (auto& track : tracks)
599             track.setBaseSize(track.growthLimit());
600     }
601
602     if (flexibleSizedTracksIndex.isEmpty()) {
603         sizingData.setFreeSpaceForDirection(direction, freeSpace);
604         return;
605     }
606
607     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
608     double flexFraction = 0;
609     if (hasDefiniteFreeSpace)
610         flexFraction = findFlexFactorUnitSize(tracks, GridSpan::translatedDefiniteGridSpan(0, tracks.size()), direction, initialFreeSpace.value());
611     else {
612         for (const auto& trackIndex : flexibleSizedTracksIndex)
613             flexFraction = std::max(flexFraction, normalizedFlexFraction(tracks[trackIndex], gridTrackSize(direction, trackIndex).maxTrackBreadth().flex()));
614
615         if (!m_gridItemArea.isEmpty()) {
616             for (unsigned i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
617                 GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
618                 while (auto* gridItem = iterator.nextGridItem()) {
619                     GridSpan span = cachedGridSpan(*gridItem, direction);
620
621                     // Do not include already processed items.
622                     if (i > 0 && span.startLine() <= flexibleSizedTracksIndex[i - 1])
623                         continue;
624
625                     flexFraction = std::max(flexFraction, findFlexFactorUnitSize(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData)));
626                 }
627             }
628         }
629     }
630
631     for (auto trackIndex : flexibleSizedTracksIndex) {
632         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
633         GridTrack& track = tracks[trackIndex];
634         LayoutUnit oldBaseSize = track.baseSize();
635         LayoutUnit baseSize = std::max<LayoutUnit>(oldBaseSize, flexFraction * trackSize.maxTrackBreadth().flex());
636         if (LayoutUnit increment = baseSize - oldBaseSize) {
637             track.setBaseSize(baseSize);
638             freeSpace -= increment;
639
640             baseSizesWithoutMaximization += increment;
641             growthLimitsWithoutMaximization += increment;
642         }
643     }
644     sizingData.setFreeSpaceForDirection(direction, freeSpace);
645 }
646
647 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(const GridLength& gridLength, LayoutUnit maxSize) const
648 {
649     if (gridLength.isFlex())
650         return 0;
651
652     const Length& trackLength = gridLength.length();
653     if (trackLength.isSpecified())
654         return valueForLength(trackLength, maxSize);
655
656     ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
657     return 0;
658 }
659
660 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(const GridLength& gridLength, LayoutUnit usedBreadth, LayoutUnit maxSize) const
661 {
662     if (gridLength.isFlex())
663         return usedBreadth;
664
665     const Length& trackLength = gridLength.length();
666     if (trackLength.isSpecified())
667         return valueForLength(trackLength, maxSize);
668
669     ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
670     return infinity;
671 }
672
673 double RenderGrid::computeFlexFactorUnitSize(const Vector<GridTrack>& tracks, GridTrackSizingDirection direction, double flexFactorSum, LayoutUnit leftOverSpace, const Vector<unsigned, 8>& flexibleTracksIndexes, std::unique_ptr<TrackIndexSet> tracksToTreatAsInflexible) const
674 {
675     // We want to avoid the effect of flex factors sum below 1 making the factor unit size to grow exponentially.
676     double hypotheticalFactorUnitSize = leftOverSpace / std::max<double>(1, flexFactorSum);
677
678     // product of the hypothetical "flex factor unit" and any flexible track's "flex factor" must be grater than such track's "base size".
679     bool validFlexFactorUnit = true;
680     for (auto index : flexibleTracksIndexes) {
681         if (tracksToTreatAsInflexible && tracksToTreatAsInflexible->contains(index))
682             continue;
683         LayoutUnit baseSize = tracks[index].baseSize();
684         double flexFactor = gridTrackSize(direction, index).maxTrackBreadth().flex();
685         // treating all such tracks as inflexible.
686         if (baseSize > hypotheticalFactorUnitSize * flexFactor) {
687             leftOverSpace -= baseSize;
688             flexFactorSum -= flexFactor;
689             if (!tracksToTreatAsInflexible)
690                 tracksToTreatAsInflexible = std::unique_ptr<TrackIndexSet>(new TrackIndexSet());
691             tracksToTreatAsInflexible->add(index);
692             validFlexFactorUnit = false;
693         }
694     }
695     if (!validFlexFactorUnit)
696         return computeFlexFactorUnitSize(tracks, direction, flexFactorSum, leftOverSpace, flexibleTracksIndexes, WTFMove(tracksToTreatAsInflexible));
697     return hypotheticalFactorUnitSize;
698 }
699
700 double RenderGrid::findFlexFactorUnitSize(const Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit leftOverSpace) const
701 {
702     if (leftOverSpace <= 0)
703         return 0;
704
705     double flexFactorSum = 0;
706     Vector<unsigned, 8> flexibleTracksIndexes;
707     for (auto trackIndex : tracksSpan) {
708         GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
709         if (!trackSize.maxTrackBreadth().isFlex())
710             leftOverSpace -= tracks[trackIndex].baseSize();
711         else {
712             double flexFactor = trackSize.maxTrackBreadth().flex();
713             flexibleTracksIndexes.append(trackIndex);
714             flexFactorSum += flexFactor;
715         }
716     }
717
718     // The function is not called if we don't have <flex> grid tracks
719     ASSERT(!flexibleTracksIndexes.isEmpty());
720
721     return computeFlexFactorUnitSize(tracks, direction, flexFactorSum, leftOverSpace, flexibleTracksIndexes);
722 }
723
724 bool RenderGrid::hasDefiniteLogicalSize(GridTrackSizingDirection direction) const
725 {
726     return (direction == ForRows) ? hasDefiniteLogicalHeight() : hasDefiniteLogicalWidth();
727 }
728
729 const GridTrackSize& RenderGrid::rawGridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex) const
730 {
731     bool isRowAxis = direction == ForColumns;
732     auto& trackStyles = isRowAxis ? style().gridColumns() : style().gridRows();
733     auto& autoRepeatTrackStyles = isRowAxis ? style().gridAutoRepeatColumns() : style().gridAutoRepeatRows();
734     auto& autoTrackSize = isRowAxis ? style().gridAutoColumns() : style().gridAutoRows();
735     unsigned insertionPoint = isRowAxis ? style().gridAutoRepeatColumnsInsertionPoint() : style().gridAutoRepeatRowsInsertionPoint();
736     unsigned repetitions = autoRepeatCountForDirection(direction);
737
738     // We should not use GridPositionsResolver::explicitGridXXXCount() for this because the
739     // explicit grid might be larger than the number of tracks in grid-template-rows|columns (if
740     // grid-template-areas is specified for example).
741     unsigned explicitTracksCount = trackStyles.size() + repetitions;
742
743     int untranslatedIndexAsInt = translatedIndex + (isRowAxis ? m_smallestColumnStart : m_smallestRowStart);
744     if (untranslatedIndexAsInt < 0)
745         return autoTrackSize;
746
747     unsigned untranslatedIndex = static_cast<unsigned>(untranslatedIndexAsInt);
748     if (untranslatedIndex >= explicitTracksCount)
749         return autoTrackSize;
750
751     if (!repetitions || untranslatedIndex < insertionPoint)
752         return trackStyles[untranslatedIndex];
753
754     if (untranslatedIndex < (insertionPoint + repetitions))
755         return autoRepeatTrackStyles[0];
756
757     return trackStyles[untranslatedIndex - repetitions];
758 }
759
760 GridTrackSize RenderGrid::gridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex) const
761 {
762     auto& trackSize = rawGridTrackSize(direction, translatedIndex);
763
764     GridLength minTrackBreadth = trackSize.minTrackBreadth();
765     GridLength maxTrackBreadth = trackSize.maxTrackBreadth();
766
767     if (minTrackBreadth.isPercentage() || maxTrackBreadth.isPercentage()) {
768         if (!hasDefiniteLogicalSize(direction)) {
769             if (minTrackBreadth.isPercentage())
770                 minTrackBreadth = Length(Auto);
771             if (maxTrackBreadth.isPercentage())
772                 maxTrackBreadth = Length(Auto);
773         }
774     }
775
776     // Flex sizes are invalid as a min sizing function. However we still can have a flexible |minTrackBreadth|
777     // if the track size is just a flex size (e.g. "1fr"), the spec says that in this case it implies an automatic minimum.
778     if (minTrackBreadth.isFlex())
779         minTrackBreadth = Length(Auto);
780
781     return GridTrackSize(minTrackBreadth, maxTrackBreadth);
782 }
783
784 LayoutUnit RenderGrid::logicalHeightForChild(RenderBox& child, GridSizingData& sizingData)
785 {
786     Optional<LayoutUnit> oldOverrideContainingBlockContentLogicalWidth = child.hasOverrideContainingBlockLogicalWidth() ? child.overrideContainingBlockContentLogicalWidth() : LayoutUnit();
787     LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, sizingData.columnTracks);
788     if (child.hasOverrideLogicalContentHeight() || child.hasRelativeLogicalHeight() || !oldOverrideContainingBlockContentLogicalWidth || oldOverrideContainingBlockContentLogicalWidth.value() != overrideContainingBlockContentLogicalWidth)
789         child.setNeedsLayout(MarkOnlyThis);
790
791     // We need to clear the stretched height to properly compute logical height during layout.
792     if (child.needsLayout())
793         child.clearOverrideLogicalContentHeight();
794
795     // If |child| has a relative logical height, we shouldn't let it override its intrinsic height, which is
796     // what we are interested in here. Thus we need to set the override logical height to Nullopt (no possible resolution).
797     if (child.hasRelativeLogicalHeight())
798         child.setOverrideContainingBlockContentLogicalHeight(Nullopt);
799
800     child.layoutIfNeeded();
801     return child.logicalHeight() + child.marginLogicalHeight();
802 }
803
804 LayoutUnit RenderGrid::minSizeForChild(RenderBox& child, GridTrackSizingDirection direction, GridSizingData& sizingData)
805 {
806     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
807     // FIXME: Properly support orthogonal writing mode.
808     if (hasOrthogonalWritingMode)
809         return { };
810
811     bool isRowAxis = direction == ForColumns;
812     const Length& childMinSize = isRowAxis ? child.style().logicalMinWidth() : child.style().logicalMinHeight();
813     const Length& childSize = isRowAxis ? child.style().logicalWidth() : child.style().logicalHeight();
814     if (!childSize.isAuto() || childMinSize.isAuto())
815         return minContentForChild(child, direction, sizingData);
816
817     bool overrideLogicalWidthHasChanged = updateOverrideContainingBlockContentLogicalWidthForChild(child, sizingData);
818     if (isRowAxis) {
819         LayoutUnit marginLogicalWidth = sizingData.sizingOperation == GridSizingData::TrackSizing ? computeMarginLogicalSizeForChild(ForColumns, child) : marginIntrinsicLogicalWidthForChild(child);
820         return child.computeLogicalWidthInRegionUsing(MinSize, childMinSize, child.overrideContainingBlockContentLogicalWidth().valueOr(0), *this, nullptr) + marginLogicalWidth;
821     }
822
823     if (overrideLogicalWidthHasChanged)
824         child.setNeedsLayout(MarkOnlyThis);
825     child.layoutIfNeeded();
826     return child.computeLogicalHeightUsing(MinSize, childMinSize, Nullopt).valueOr(0) + child.marginLogicalHeight() + child.scrollbarLogicalHeight();
827 }
828
829 bool RenderGrid::updateOverrideContainingBlockContentLogicalWidthForChild(RenderBox& child, GridSizingData& sizingData)
830 {
831     LayoutUnit overrideWidth = gridAreaBreadthForChild(child, ForColumns, sizingData.columnTracks);
832     if (child.hasOverrideContainingBlockLogicalWidth() && child.overrideContainingBlockContentLogicalWidth() == overrideWidth)
833         return false;
834
835     child.setOverrideContainingBlockContentLogicalWidth(overrideWidth);
836     return true;
837 }
838
839 LayoutUnit RenderGrid::minContentForChild(RenderBox& child, GridTrackSizingDirection direction, GridSizingData& sizingData)
840 {
841     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
842     // FIXME: Properly support orthogonal writing mode.
843     if (hasOrthogonalWritingMode)
844         return 0;
845
846     if (direction == ForColumns) {
847         // If |child| has a relative logical width, we shouldn't let it override its intrinsic width, which is
848         // what we are interested in here. Thus we need to set the override logical width to Nullopt (no possible resolution).
849         if (child.hasRelativeLogicalWidth())
850             child.setOverrideContainingBlockContentLogicalWidth(Nullopt);
851
852         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
853         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
854         return child.minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
855     }
856
857     if (updateOverrideContainingBlockContentLogicalWidthForChild(child, sizingData))
858         child.setNeedsLayout(MarkOnlyThis);
859     return logicalHeightForChild(child, sizingData);
860 }
861
862 LayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirection direction, GridSizingData& sizingData)
863 {
864     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
865     // FIXME: Properly support orthogonal writing mode.
866     if (hasOrthogonalWritingMode)
867         return LayoutUnit();
868
869     if (direction == ForColumns) {
870         // If |child| has a relative logical width, we shouldn't let it override its intrinsic width, which is
871         // what we are interested in here. Thus we need to set the override logical width to Nullopt (no possible resolution).
872         if (child.hasRelativeLogicalWidth())
873             child.setOverrideContainingBlockContentLogicalWidth(Nullopt);
874
875         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
876         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
877         return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
878     }
879
880     if (updateOverrideContainingBlockContentLogicalWidthForChild(child, sizingData))
881         child.setNeedsLayout(MarkOnlyThis);
882     return logicalHeightForChild(child, sizingData);
883 }
884
885 class GridItemWithSpan {
886 public:
887     GridItemWithSpan(RenderBox& gridItem, GridSpan span)
888         : m_gridItem(gridItem)
889         , m_span(span)
890     {
891     }
892
893     RenderBox& gridItem() const { return m_gridItem; }
894     GridSpan span() const { return m_span; }
895
896     bool operator<(const GridItemWithSpan other) const
897     {
898         return m_span.integerSpan() < other.m_span.integerSpan();
899     }
900
901 private:
902     std::reference_wrapper<RenderBox> m_gridItem;
903     GridSpan m_span;
904 };
905
906 bool RenderGrid::spanningItemCrossesFlexibleSizedTracks(const GridSpan& itemSpan, GridTrackSizingDirection direction) const
907 {
908     for (auto trackPosition : itemSpan) {
909         const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition);
910         if (trackSize.minTrackBreadth().isFlex() || trackSize.maxTrackBreadth().isFlex())
911             return true;
912     }
913
914     return false;
915 }
916
917 struct GridItemsSpanGroupRange {
918     Vector<GridItemWithSpan>::iterator rangeStart;
919     Vector<GridItemWithSpan>::iterator rangeEnd;
920 };
921
922 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData)
923 {
924     sizingData.itemsSortedByIncreasingSpan.shrink(0);
925     HashSet<RenderBox*> itemsSet;
926     if (!m_gridItemArea.isEmpty()) {
927         for (auto trackIndex : sizingData.contentSizedTracksIndex) {
928             GridIterator iterator(m_grid, direction, trackIndex);
929             GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
930
931             while (auto* gridItem = iterator.nextGridItem()) {
932                 if (itemsSet.add(gridItem).isNewEntry) {
933                     GridSpan span = cachedGridSpan(*gridItem, direction);
934                     if (span.integerSpan() == 1)
935                         resolveContentBasedTrackSizingFunctionsForNonSpanningItems(direction, span, *gridItem, track, sizingData);
936                     else if (!spanningItemCrossesFlexibleSizedTracks(span, direction))
937                         sizingData.itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, span));
938                 }
939             }
940         }
941         std::sort(sizingData.itemsSortedByIncreasingSpan.begin(), sizingData.itemsSortedByIncreasingSpan.end());
942     }
943
944     auto it = sizingData.itemsSortedByIncreasingSpan.begin();
945     auto end = sizingData.itemsSortedByIncreasingSpan.end();
946     while (it != end) {
947         GridItemsSpanGroupRange spanGroupRange = { it, std::upper_bound(it, end, *it) };
948         resolveContentBasedTrackSizingFunctionsForItems<ResolveIntrinsicMinimums>(direction, sizingData, spanGroupRange);
949         resolveContentBasedTrackSizingFunctionsForItems<ResolveContentBasedMinimums>(direction, sizingData, spanGroupRange);
950         resolveContentBasedTrackSizingFunctionsForItems<ResolveMaxContentMinimums>(direction, sizingData, spanGroupRange);
951         resolveContentBasedTrackSizingFunctionsForItems<ResolveIntrinsicMaximums>(direction, sizingData, spanGroupRange);
952         resolveContentBasedTrackSizingFunctionsForItems<ResolveMaxContentMaximums>(direction, sizingData, spanGroupRange);
953         it = spanGroupRange.rangeEnd;
954     }
955
956     for (auto trackIndex : sizingData.contentSizedTracksIndex) {
957         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
958         if (track.growthLimitIsInfinite())
959             track.setGrowthLimit(track.baseSize());
960     }
961 }
962
963 void RenderGrid::resolveContentBasedTrackSizingFunctionsForNonSpanningItems(GridTrackSizingDirection direction, const GridSpan& span, RenderBox& gridItem, GridTrack& track, GridSizingData& sizingData)
964 {
965     unsigned trackPosition = span.startLine();
966     GridTrackSize trackSize = gridTrackSize(direction, trackPosition);
967
968     if (trackSize.hasMinContentMinTrackBreadth())
969         track.setBaseSize(std::max(track.baseSize(), minContentForChild(gridItem, direction, sizingData)));
970     else if (trackSize.hasMaxContentMinTrackBreadth())
971         track.setBaseSize(std::max(track.baseSize(), maxContentForChild(gridItem, direction, sizingData)));
972     else if (trackSize.hasAutoMinTrackBreadth())
973         track.setBaseSize(std::max(track.baseSize(), minSizeForChild(gridItem, direction, sizingData)));
974
975     if (trackSize.hasMinContentMaxTrackBreadth())
976         track.setGrowthLimit(std::max(track.growthLimit(), minContentForChild(gridItem, direction, sizingData)));
977     else if (trackSize.hasMaxContentOrAutoMaxTrackBreadth())
978         track.setGrowthLimit(std::max(track.growthLimit(), maxContentForChild(gridItem, direction, sizingData)));
979 }
980
981 const LayoutUnit& RenderGrid::trackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track, TrackSizeRestriction restriction)
982 {
983     switch (phase) {
984     case ResolveIntrinsicMinimums:
985     case ResolveContentBasedMinimums:
986     case ResolveMaxContentMinimums:
987     case MaximizeTracks:
988         return track.baseSize();
989     case ResolveIntrinsicMaximums:
990     case ResolveMaxContentMaximums:
991         return restriction == AllowInfinity ? track.growthLimit() : track.growthLimitIfNotInfinite();
992     }
993
994     ASSERT_NOT_REACHED();
995     return track.baseSize();
996 }
997
998 bool RenderGrid::shouldProcessTrackForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
999 {
1000     switch (phase) {
1001     case ResolveIntrinsicMinimums:
1002         return trackSize.hasIntrinsicMinTrackBreadth();
1003     case ResolveContentBasedMinimums:
1004         return trackSize.hasMinOrMaxContentMinTrackBreadth();
1005     case ResolveMaxContentMinimums:
1006         return trackSize.hasMaxContentMinTrackBreadth();
1007     case ResolveIntrinsicMaximums:
1008         return trackSize.hasMinOrMaxContentMaxTrackBreadth();
1009     case ResolveMaxContentMaximums:
1010         return trackSize.hasMaxContentOrAutoMaxTrackBreadth();
1011     case MaximizeTracks:
1012         ASSERT_NOT_REACHED();
1013         return false;
1014     }
1015
1016     ASSERT_NOT_REACHED();
1017     return false;
1018 }
1019
1020 bool RenderGrid::trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
1021 {
1022     switch (phase) {
1023     case ResolveIntrinsicMinimums:
1024     case ResolveContentBasedMinimums:
1025         return trackSize.hasAutoOrMinContentMinTrackBreadthAndIntrinsicMaxTrackBreadth();
1026     case ResolveMaxContentMinimums:
1027         return trackSize.hasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth();
1028     case ResolveIntrinsicMaximums:
1029     case ResolveMaxContentMaximums:
1030         return true;
1031     case MaximizeTracks:
1032         ASSERT_NOT_REACHED();
1033         return false;
1034     }
1035
1036     ASSERT_NOT_REACHED();
1037     return false;
1038 }
1039
1040 void RenderGrid::markAsInfinitelyGrowableForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
1041 {
1042     switch (phase) {
1043     case ResolveIntrinsicMinimums:
1044     case ResolveContentBasedMinimums:
1045     case ResolveMaxContentMinimums:
1046         return;
1047     case ResolveIntrinsicMaximums:
1048         if (trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity) == infinity  && track.plannedSize() != infinity)
1049             track.setInfinitelyGrowable(true);
1050         return;
1051     case ResolveMaxContentMaximums:
1052         if (track.infinitelyGrowable())
1053             track.setInfinitelyGrowable(false);
1054         return;
1055     case MaximizeTracks:
1056         ASSERT_NOT_REACHED();
1057         return;
1058     }
1059
1060     ASSERT_NOT_REACHED();
1061 }
1062
1063 void RenderGrid::updateTrackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
1064 {
1065     switch (phase) {
1066     case ResolveIntrinsicMinimums:
1067     case ResolveContentBasedMinimums:
1068     case ResolveMaxContentMinimums:
1069         track.setBaseSize(track.plannedSize());
1070         return;
1071     case ResolveIntrinsicMaximums:
1072     case ResolveMaxContentMaximums:
1073         track.setGrowthLimit(track.plannedSize());
1074         return;
1075     case MaximizeTracks:
1076         ASSERT_NOT_REACHED();
1077         return;
1078     }
1079
1080     ASSERT_NOT_REACHED();
1081 }
1082
1083 LayoutUnit RenderGrid::currentItemSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, RenderBox& gridItem, GridTrackSizingDirection direction, GridSizingData& sizingData)
1084 {
1085     switch (phase) {
1086     case ResolveIntrinsicMinimums:
1087         return minSizeForChild(gridItem, direction, sizingData);
1088     case ResolveContentBasedMinimums:
1089     case ResolveIntrinsicMaximums:
1090         return minContentForChild(gridItem, direction, sizingData);
1091     case ResolveMaxContentMinimums:
1092     case ResolveMaxContentMaximums:
1093         return maxContentForChild(gridItem, direction, sizingData);
1094     case MaximizeTracks:
1095         ASSERT_NOT_REACHED();
1096         return 0;
1097     }
1098
1099     ASSERT_NOT_REACHED();
1100     return 0;
1101 }
1102
1103 template <RenderGrid::TrackSizeComputationPhase phase>
1104 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, const GridItemsSpanGroupRange& gridItemsWithSpan)
1105 {
1106     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
1107     for (const auto& trackIndex : sizingData.contentSizedTracksIndex) {
1108         GridTrack& track = tracks[trackIndex];
1109         track.setPlannedSize(trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity));
1110     }
1111
1112     for (auto it = gridItemsWithSpan.rangeStart; it != gridItemsWithSpan.rangeEnd; ++it) {
1113         GridItemWithSpan& gridItemWithSpan = *it;
1114         ASSERT(gridItemWithSpan.span().integerSpan() > 1);
1115         const GridSpan& itemSpan = gridItemWithSpan.span();
1116
1117         sizingData.filteredTracks.shrink(0);
1118         sizingData.growBeyondGrowthLimitsTracks.shrink(0);
1119         LayoutUnit spanningTracksSize;
1120         for (auto trackPosition : itemSpan) {
1121             const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition);
1122             GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPosition] : sizingData.rowTracks[trackPosition];
1123             spanningTracksSize += trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
1124             if (!shouldProcessTrackForTrackSizeComputationPhase(phase, trackSize))
1125                 continue;
1126
1127             sizingData.filteredTracks.append(&track);
1128
1129             if (trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(phase, trackSize))
1130                 sizingData.growBeyondGrowthLimitsTracks.append(&track);
1131         }
1132
1133         if (sizingData.filteredTracks.isEmpty())
1134             continue;
1135
1136         spanningTracksSize += guttersSize(direction, itemSpan.integerSpan());
1137
1138         LayoutUnit extraSpace = currentItemSizeForTrackSizeComputationPhase(phase, gridItemWithSpan.gridItem(), direction, sizingData) - spanningTracksSize;
1139         extraSpace = std::max<LayoutUnit>(extraSpace, 0);
1140         auto& tracksToGrowBeyondGrowthLimits = sizingData.growBeyondGrowthLimitsTracks.isEmpty() ? sizingData.filteredTracks : sizingData.growBeyondGrowthLimitsTracks;
1141         distributeSpaceToTracks<phase>(sizingData.filteredTracks, &tracksToGrowBeyondGrowthLimits, extraSpace);
1142     }
1143
1144     for (const auto& trackIndex : sizingData.contentSizedTracksIndex) {
1145         GridTrack& track = tracks[trackIndex];
1146         markAsInfinitelyGrowableForTrackSizeComputationPhase(phase, track);
1147         updateTrackSizeForTrackSizeComputationPhase(phase, track);
1148     }
1149 }
1150
1151 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
1152 {
1153     // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
1154     // (forall x: NOT x < x).
1155     if (track1->infiniteGrowthPotential() && track2->infiniteGrowthPotential())
1156         return false;
1157
1158     if (track1->infiniteGrowthPotential() || track2->infiniteGrowthPotential())
1159         return track2->infiniteGrowthPotential();
1160
1161     return (track1->growthLimit() - track1->baseSize()) < (track2->growthLimit() - track2->baseSize());
1162 }
1163
1164 template <RenderGrid::TrackSizeComputationPhase phase>
1165 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, const Vector<GridTrack*>* growBeyondGrowthLimitsTracks, LayoutUnit& freeSpace)
1166 {
1167     ASSERT(freeSpace >= 0);
1168
1169     for (auto* track : tracks)
1170         track->tempSize() = trackSizeForTrackSizeComputationPhase(phase, *track, ForbidInfinity);
1171
1172     if (freeSpace > 0) {
1173         std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
1174
1175         unsigned tracksSize = tracks.size();
1176         for (unsigned i = 0; i < tracksSize; ++i) {
1177             GridTrack& track = *tracks[i];
1178             const LayoutUnit& trackBreadth = trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
1179             bool infiniteGrowthPotential = track.infiniteGrowthPotential();
1180             LayoutUnit trackGrowthPotential = infiniteGrowthPotential ? track.growthLimit() : track.growthLimit() - trackBreadth;
1181             // Let's avoid computing availableLogicalSpaceShare as much as possible as it's a hot spot in performance tests.
1182             if (trackGrowthPotential > 0 || infiniteGrowthPotential) {
1183                 LayoutUnit availableLogicalSpaceShare = freeSpace / (tracksSize - i);
1184                 LayoutUnit growthShare = infiniteGrowthPotential ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, trackGrowthPotential);
1185                 ASSERT_WITH_MESSAGE(growthShare >= 0, "We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function. We can still have 0 as growthShare if the amount of tracks greatly exceeds the freeSpace.");
1186                 track.tempSize() += growthShare;
1187                 freeSpace -= growthShare;
1188             }
1189         }
1190     }
1191
1192     if (freeSpace > 0 && growBeyondGrowthLimitsTracks) {
1193         unsigned tracksGrowingBeyondGrowthLimitsSize = growBeyondGrowthLimitsTracks->size();
1194         for (unsigned i = 0; i < tracksGrowingBeyondGrowthLimitsSize; ++i) {
1195             GridTrack* track = growBeyondGrowthLimitsTracks->at(i);
1196             LayoutUnit growthShare = freeSpace / (tracksGrowingBeyondGrowthLimitsSize - i);
1197             track->tempSize() += growthShare;
1198             freeSpace -= growthShare;
1199         }
1200     }
1201
1202     for (auto* track : tracks)
1203         track->setPlannedSize(track->plannedSize() == infinity ? track->tempSize() : std::max(track->plannedSize(), track->tempSize()));
1204 }
1205
1206 #ifndef NDEBUG
1207 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, GridSizingData& sizingData)
1208 {
1209     const Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
1210     const LayoutUnit maxSize = sizingData.freeSpaceForDirection(direction).valueOr(0);
1211     for (unsigned i = 0; i < tracks.size(); ++i) {
1212         const GridTrackSize& trackSize = gridTrackSize(direction, i);
1213         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
1214         if (computeUsedBreadthOfMinLength(minTrackBreadth, maxSize) > tracks[i].baseSize())
1215             return false;
1216     }
1217     return true;
1218 }
1219 #endif
1220
1221 void RenderGrid::ensureGridSize(unsigned maximumRowSize, unsigned maximumColumnSize)
1222 {
1223     const unsigned oldRowCount = gridRowCount();
1224     if (maximumRowSize > oldRowCount) {
1225         m_grid.grow(maximumRowSize);
1226         for (unsigned row = oldRowCount; row < gridRowCount(); ++row)
1227             m_grid[row].grow(gridColumnCount());
1228     }
1229
1230     if (maximumColumnSize > gridColumnCount()) {
1231         for (unsigned row = 0; row < gridRowCount(); ++row)
1232             m_grid[row].grow(maximumColumnSize);
1233     }
1234 }
1235
1236 void RenderGrid::insertItemIntoGrid(RenderBox& child, const GridArea& area)
1237 {
1238     ASSERT(area.rows.isTranslatedDefinite() && area.columns.isTranslatedDefinite());
1239     ensureGridSize(area.rows.endLine(), area.columns.endLine());
1240
1241     for (auto row : area.rows) {
1242         for (auto column : area.columns)
1243             m_grid[row][column].append(&child);
1244     }
1245 }
1246
1247 unsigned RenderGrid::computeAutoRepeatTracksCount(GridTrackSizingDirection direction) const
1248 {
1249     bool isRowAxis = direction == ForColumns;
1250     const auto& autoRepeatTracks = isRowAxis ? style().gridAutoRepeatColumns() : style().gridAutoRepeatRows();
1251
1252     if (!autoRepeatTracks.size())
1253         return 0;
1254
1255     ASSERT(autoRepeatTracks.size() == 1);
1256     auto autoTrackSize = autoRepeatTracks.at(0);
1257     ASSERT(autoTrackSize.minTrackBreadth().isLength());
1258     ASSERT(!autoTrackSize.minTrackBreadth().isFlex());
1259
1260     Optional<LayoutUnit> availableSize = isRowAxis ? availableLogicalWidth() : computeContentLogicalHeight(MainOrPreferredSize, style().logicalHeight(), Nullopt);
1261     if (!isRowAxis || containingBlock()) {
1262         if (!availableSize) {
1263             const Length& maxLength = isRowAxis ? style().logicalMaxWidth() : style().logicalMaxHeight();
1264             if (!maxLength.isUndefined()) {
1265                 availableSize = isRowAxis
1266                     ? computeLogicalWidthInRegionUsing(MaxSize, maxLength, containingBlockLogicalWidthForContent(), *containingBlock(), nullptr)
1267                     : computeContentLogicalHeight(MaxSize, maxLength, Nullopt);
1268             }
1269         } else {
1270             availableSize = isRowAxis
1271                 ? constrainLogicalWidthInRegionByMinMax(availableSize.value(), availableLogicalWidth(), *containingBlock())
1272                 : constrainLogicalHeightByMinMax(availableSize.value(), Nullopt);
1273         }
1274     }
1275
1276     bool needsToFulfillMinimumSize = false;
1277     if (!availableSize) {
1278         const Length& minSize = isRowAxis ? style().logicalMinWidth() : style().logicalMinHeight();
1279         if (!minSize.isSpecified())
1280             return 1;
1281
1282         LayoutUnit containingBlockAvailableSize = isRowAxis ? containingBlockLogicalWidthForContent() : containingBlockLogicalHeightForContent(ExcludeMarginBorderPadding);
1283         availableSize = valueForLength(minSize, containingBlockAvailableSize);
1284         needsToFulfillMinimumSize = true;
1285     }
1286
1287     bool hasDefiniteMaxTrackSizingFunction = autoTrackSize.maxTrackBreadth().isLength() && !autoTrackSize.maxTrackBreadth().isContentSized();
1288     const Length trackLength = hasDefiniteMaxTrackSizingFunction ? autoTrackSize.maxTrackBreadth().length() : autoTrackSize.minTrackBreadth().length();
1289     // For the purpose of finding the number of auto-repeated tracks, the UA must floor the track size to a UA-specified
1290     // value to avoid division by zero. It is suggested that this floor be 1px.
1291     LayoutUnit autoRepeatTrackSize = std::max<LayoutUnit>(LayoutUnit(1), valueForLength(trackLength, availableSize.value()));
1292
1293     // There will be always at least 1 auto-repeat track, so take it already into account when computing the total track size.
1294     LayoutUnit tracksSize = autoRepeatTrackSize;
1295     auto& trackSizes = isRowAxis ? style().gridColumns() : style().gridRows();
1296
1297     for (const auto& track : trackSizes) {
1298         bool hasDefiniteMaxTrackBreadth = track.maxTrackBreadth().isLength() && !track.maxTrackBreadth().isContentSized();
1299         ASSERT(hasDefiniteMaxTrackBreadth || (track.minTrackBreadth().isLength() && !track.minTrackBreadth().isContentSized()));
1300         tracksSize += valueForLength(hasDefiniteMaxTrackBreadth ? track.maxTrackBreadth().length() : track.minTrackBreadth().length(), availableSize.value());
1301     }
1302
1303     // Add gutters as if there where only 1 auto repeat track. Gaps between auto repeat tracks will be added later when
1304     // computing the repetitions.
1305     LayoutUnit gapSize = guttersSize(direction, 2);
1306     tracksSize += gapSize * trackSizes.size();
1307
1308     LayoutUnit freeSpace = availableSize.value() - tracksSize;
1309     if (freeSpace <= 0)
1310         return 1;
1311
1312     unsigned repetitions = 1 + (freeSpace / (autoRepeatTrackSize + gapSize)).toInt();
1313
1314     // Provided the grid container does not have a definite size or max-size in the relevant axis,
1315     // if the min size is definite then the number of repetitions is the largest possible positive
1316     // integer that fulfills that minimum requirement.
1317     if (needsToFulfillMinimumSize)
1318         ++repetitions;
1319
1320     return repetitions;
1321 }
1322
1323 void RenderGrid::placeItemsOnGrid()
1324 {
1325     ASSERT(m_gridIsDirty);
1326     ASSERT(m_gridItemArea.isEmpty());
1327
1328     m_autoRepeatColumns = computeAutoRepeatTracksCount(ForColumns);
1329     m_autoRepeatRows = computeAutoRepeatTracksCount(ForRows);
1330
1331     populateExplicitGridAndOrderIterator();
1332     m_gridIsDirty = false;
1333
1334     Vector<RenderBox*> autoMajorAxisAutoGridItems;
1335     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
1336     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
1337         if (child->isOutOfFlowPositioned())
1338             continue;
1339
1340         GridArea area = cachedGridArea(*child);
1341         if (!area.rows.isIndefinite())
1342             area.rows.translate(std::abs(m_smallestRowStart));
1343         if (!area.columns.isIndefinite())
1344             area.columns.translate(std::abs(m_smallestColumnStart));
1345         m_gridItemArea.set(child, area);
1346
1347         if (area.rows.isIndefinite() || area.columns.isIndefinite()) {
1348             bool majorAxisDirectionIsForColumns = autoPlacementMajorAxisDirection() == ForColumns;
1349             if ((majorAxisDirectionIsForColumns && area.columns.isIndefinite())
1350                 || (!majorAxisDirectionIsForColumns && area.rows.isIndefinite()))
1351                 autoMajorAxisAutoGridItems.append(child);
1352             else
1353                 specifiedMajorAxisAutoGridItems.append(child);
1354             continue;
1355         }
1356         insertItemIntoGrid(*child, GridArea(area.rows, area.columns));
1357     }
1358
1359     ASSERT(gridRowCount() >= GridPositionsResolver::explicitGridRowCount(style(), m_autoRepeatRows));
1360     ASSERT(gridColumnCount() >= GridPositionsResolver::explicitGridColumnCount(style(), m_autoRepeatColumns));
1361
1362     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
1363     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
1364
1365 #if ENABLE(ASSERT)
1366     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
1367         if (child->isOutOfFlowPositioned())
1368             continue;
1369
1370         GridArea area = cachedGridArea(*child);
1371         ASSERT(area.rows.isTranslatedDefinite() && area.columns.isTranslatedDefinite());
1372     }
1373 #endif
1374 }
1375
1376 void RenderGrid::populateExplicitGridAndOrderIterator()
1377 {
1378     OrderIteratorPopulator populator(m_orderIterator);
1379     m_smallestRowStart = m_smallestColumnStart = 0;
1380     unsigned maximumRowIndex = GridPositionsResolver::explicitGridRowCount(style(), m_autoRepeatRows);
1381     unsigned maximumColumnIndex = GridPositionsResolver::explicitGridColumnCount(style(), m_autoRepeatColumns);
1382
1383     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1384         if (child->isOutOfFlowPositioned())
1385             continue;
1386
1387         populator.collectChild(*child);
1388
1389         GridSpan rowPositions = GridPositionsResolver::resolveGridPositionsFromStyle(style(), *child, ForRows, m_autoRepeatRows);
1390         if (!rowPositions.isIndefinite()) {
1391             m_smallestRowStart = std::min(m_smallestRowStart, rowPositions.untranslatedStartLine());
1392             maximumRowIndex = std::max<int>(maximumRowIndex, rowPositions.untranslatedEndLine());
1393         } else {
1394             // Grow the grid for items with a definite row span, getting the largest such span.
1395             unsigned spanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), *child, ForRows);
1396             maximumRowIndex = std::max(maximumRowIndex, spanSize);
1397         }
1398
1399         GridSpan columnPositions = GridPositionsResolver::resolveGridPositionsFromStyle(style(), *child, ForColumns, m_autoRepeatColumns);
1400         if (!columnPositions.isIndefinite()) {
1401             m_smallestColumnStart = std::min(m_smallestColumnStart, columnPositions.untranslatedStartLine());
1402             maximumColumnIndex = std::max<int>(maximumColumnIndex, columnPositions.untranslatedEndLine());
1403         } else {
1404             // Grow the grid for items with a definite column span, getting the largest such span.
1405             unsigned spanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), *child, ForColumns);
1406             maximumColumnIndex = std::max(maximumColumnIndex, spanSize);
1407         }
1408
1409         m_gridItemArea.set(child, GridArea(rowPositions, columnPositions));
1410     }
1411
1412     m_grid.grow(maximumRowIndex + std::abs(m_smallestRowStart));
1413     for (auto& column : m_grid)
1414         column.grow(maximumColumnIndex + std::abs(m_smallestColumnStart));
1415 }
1416
1417 std::unique_ptr<GridArea> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox& gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
1418 {
1419     GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
1420     const unsigned endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount();
1421     unsigned crossDirectionSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), gridItem, crossDirection);
1422     GridSpan crossDirectionPositions = GridSpan::translatedDefiniteGridSpan(endOfCrossDirection, endOfCrossDirection + crossDirectionSpanSize);
1423     return std::make_unique<GridArea>(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions);
1424 }
1425
1426 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
1427 {
1428     bool isForColumns = autoPlacementMajorAxisDirection() == ForColumns;
1429     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
1430
1431     // Mapping between the major axis tracks (rows or columns) and the last auto-placed item's position inserted on
1432     // that track. This is needed to implement "sparse" packing for items locked to a given track.
1433     // See http://dev.w3.org/csswg/css-grid/#auto-placement-algo
1434     HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> minorAxisCursors;
1435
1436     for (auto& autoGridItem : autoGridItems) {
1437         GridSpan majorAxisPositions = cachedGridSpan(*autoGridItem, autoPlacementMajorAxisDirection());
1438         ASSERT(majorAxisPositions.isTranslatedDefinite());
1439         ASSERT(cachedGridSpan(*autoGridItem, autoPlacementMinorAxisDirection()).isIndefinite());
1440         unsigned minorAxisSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), *autoGridItem, autoPlacementMinorAxisDirection());
1441         unsigned majorAxisInitialPosition = majorAxisPositions.startLine();
1442
1443         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions.startLine(), isGridAutoFlowDense ? 0 : minorAxisCursors.get(majorAxisInitialPosition));
1444         std::unique_ptr<GridArea> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisSpanSize);
1445         if (!emptyGridArea)
1446             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(*autoGridItem, autoPlacementMajorAxisDirection(), majorAxisPositions);
1447
1448         m_gridItemArea.set(autoGridItem, *emptyGridArea);
1449         insertItemIntoGrid(*autoGridItem, *emptyGridArea);
1450
1451         if (!isGridAutoFlowDense)
1452             minorAxisCursors.set(majorAxisInitialPosition, isForColumns ? emptyGridArea->rows.startLine() : emptyGridArea->columns.startLine());
1453     }
1454 }
1455
1456 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
1457 {
1458     AutoPlacementCursor autoPlacementCursor = {0, 0};
1459     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
1460
1461     for (auto& autoGridItem : autoGridItems) {
1462         placeAutoMajorAxisItemOnGrid(*autoGridItem, autoPlacementCursor);
1463
1464         if (isGridAutoFlowDense) {
1465             autoPlacementCursor.first = 0;
1466             autoPlacementCursor.second = 0;
1467         }
1468     }
1469 }
1470
1471 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox& gridItem, AutoPlacementCursor& autoPlacementCursor)
1472 {
1473     ASSERT(cachedGridSpan(gridItem, autoPlacementMajorAxisDirection()).isIndefinite());
1474     unsigned majorAxisSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), gridItem, autoPlacementMajorAxisDirection());
1475
1476     const unsigned endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
1477     unsigned majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
1478     unsigned minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
1479
1480     std::unique_ptr<GridArea> emptyGridArea;
1481     GridSpan minorAxisPositions = cachedGridSpan(gridItem, autoPlacementMinorAxisDirection());
1482     if (minorAxisPositions.isTranslatedDefinite()) {
1483         // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
1484         if (minorAxisPositions.startLine() < minorAxisAutoPlacementCursor)
1485             majorAxisAutoPlacementCursor++;
1486
1487         if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
1488             GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions.startLine(), majorAxisAutoPlacementCursor);
1489             emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions.integerSpan(), majorAxisSpanSize);
1490         }
1491
1492         if (!emptyGridArea)
1493             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
1494     } else {
1495         unsigned minorAxisSpanSize = GridPositionsResolver::spanSizeForAutoPlacedItem(style(), gridItem, autoPlacementMinorAxisDirection());
1496
1497         for (unsigned majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
1498             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
1499             emptyGridArea = iterator.nextEmptyGridArea(majorAxisSpanSize, minorAxisSpanSize);
1500
1501             if (emptyGridArea) {
1502                 // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
1503                 unsigned minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.endLine() : emptyGridArea->rows.endLine();
1504                 const unsigned endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount();
1505                 if (minorAxisFinalPositionIndex <= endOfMinorAxis)
1506                     break;
1507
1508                 // Discard empty grid area as it does not fit in the minor axis direction.
1509                 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
1510                 emptyGridArea = nullptr;
1511             }
1512
1513             // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
1514             minorAxisAutoPlacementCursor = 0;
1515         }
1516
1517         if (!emptyGridArea)
1518             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), GridSpan::translatedDefiniteGridSpan(0, minorAxisSpanSize));
1519     }
1520
1521     m_gridItemArea.set(&gridItem, *emptyGridArea);
1522     insertItemIntoGrid(gridItem, *emptyGridArea);
1523     autoPlacementCursor.first = emptyGridArea->rows.startLine();
1524     autoPlacementCursor.second = emptyGridArea->columns.startLine();
1525 }
1526
1527 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
1528 {
1529     return style().isGridAutoFlowDirectionColumn() ? ForColumns : ForRows;
1530 }
1531
1532 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
1533 {
1534     return style().isGridAutoFlowDirectionColumn() ? ForRows : ForColumns;
1535 }
1536
1537 void RenderGrid::clearGrid()
1538 {
1539     m_grid.clear();
1540     m_gridItemArea.clear();
1541     m_gridIsDirty = true;
1542 }
1543
1544 static const StyleContentAlignmentData& contentAlignmentNormalBehaviorGrid()
1545 {
1546     static const StyleContentAlignmentData normalBehavior = {ContentPositionNormal, ContentDistributionStretch};
1547     return normalBehavior;
1548 }
1549
1550 void RenderGrid::applyStretchAlignmentToTracksIfNeeded(GridTrackSizingDirection direction, GridSizingData& sizingData)
1551 {
1552     Optional<LayoutUnit> freeSpace = sizingData.freeSpaceForDirection(direction);
1553     if (!freeSpace
1554         || freeSpace.value() <= 0
1555         || (direction == ForColumns && style().resolvedJustifyContentDistribution(contentAlignmentNormalBehaviorGrid()) != ContentDistributionStretch)
1556         || (direction == ForRows && style().resolvedAlignContentDistribution(contentAlignmentNormalBehaviorGrid()) != ContentDistributionStretch))
1557         return;
1558
1559     // Spec defines auto-sized tracks as the ones with an 'auto' max-sizing function.
1560     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
1561     Vector<unsigned> autoSizedTracksIndex;
1562     for (unsigned i = 0; i < tracks.size(); ++i) {
1563         const GridTrackSize& trackSize = gridTrackSize(direction, i);
1564         if (trackSize.hasAutoMaxTrackBreadth())
1565             autoSizedTracksIndex.append(i);
1566     }
1567
1568     unsigned numberOfAutoSizedTracks = autoSizedTracksIndex.size();
1569     if (numberOfAutoSizedTracks < 1)
1570         return;
1571
1572     LayoutUnit sizeToIncrease = freeSpace.value() / numberOfAutoSizedTracks;
1573     for (const auto& trackIndex : autoSizedTracksIndex) {
1574         auto& track = tracks[trackIndex];
1575         track.setBaseSize(track.baseSize() + sizeToIncrease);
1576     }
1577     sizingData.setFreeSpaceForDirection(direction, Optional<LayoutUnit>(0));
1578 }
1579
1580 void RenderGrid::layoutGridItems(GridSizingData& sizingData)
1581 {
1582     populateGridPositionsForDirection(sizingData, ForColumns);
1583     populateGridPositionsForDirection(sizingData, ForRows);
1584
1585     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1586         if (child->isOutOfFlowPositioned()) {
1587             prepareChildForPositionedLayout(*child);
1588             continue;
1589         }
1590
1591         // Because the grid area cannot be styled, we don't need to adjust
1592         // the grid breadth to account for 'box-sizing'.
1593         Optional<LayoutUnit> oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
1594         Optional<LayoutUnit> oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
1595
1596         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChildIncludingAlignmentOffsets(*child, ForColumns, sizingData);
1597         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChildIncludingAlignmentOffsets(*child, ForRows, sizingData);
1598         if (!oldOverrideContainingBlockContentLogicalWidth || oldOverrideContainingBlockContentLogicalWidth.value() != overrideContainingBlockContentLogicalWidth
1599             || ((!oldOverrideContainingBlockContentLogicalHeight || oldOverrideContainingBlockContentLogicalHeight.value() != overrideContainingBlockContentLogicalHeight)
1600                 && child->hasRelativeLogicalHeight()))
1601             child->setNeedsLayout(MarkOnlyThis);
1602
1603         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
1604         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
1605
1606         LayoutRect oldChildRect = child->frameRect();
1607
1608         // Stretching logic might force a child layout, so we need to run it before the layoutIfNeeded
1609         // call to avoid unnecessary relayouts. This might imply that child margins, needed to correctly
1610         // determine the available space before stretching, are not set yet.
1611         applyStretchAlignmentToChildIfNeeded(*child);
1612
1613         child->layoutIfNeeded();
1614
1615         // We need pending layouts to be done in order to compute auto-margins properly.
1616         updateAutoMarginsInColumnAxisIfNeeded(*child);
1617         updateAutoMarginsInRowAxisIfNeeded(*child);
1618
1619         child->setLogicalLocation(findChildLogicalPosition(*child));
1620
1621         // If the child moved, we have to repaint it as well as any floating/positioned
1622         // descendants. An exception is if we need a layout. In this case, we know we're going to
1623         // repaint ourselves (and the child) anyway.
1624         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
1625             child->repaintDuringLayoutIfMoved(oldChildRect);
1626     }
1627 }
1628
1629 void RenderGrid::prepareChildForPositionedLayout(RenderBox& child)
1630 {
1631     ASSERT(child.isOutOfFlowPositioned());
1632     child.containingBlock()->insertPositionedObject(child);
1633
1634     RenderLayer* childLayer = child.layer();
1635     childLayer->setStaticInlinePosition(borderAndPaddingStart());
1636     childLayer->setStaticBlockPosition(borderAndPaddingBefore());
1637 }
1638
1639 void RenderGrid::layoutPositionedObject(RenderBox& child, bool relayoutChildren, bool fixedPositionObjectsOnly)
1640 {
1641     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
1642     // FIXME: Properly support orthogonal writing mode.
1643     if (!hasOrthogonalWritingMode) {
1644         LayoutUnit columnOffset = LayoutUnit();
1645         LayoutUnit columnBreadth = LayoutUnit();
1646         offsetAndBreadthForPositionedChild(child, ForColumns, columnOffset, columnBreadth);
1647         LayoutUnit rowOffset = LayoutUnit();
1648         LayoutUnit rowBreadth = LayoutUnit();
1649         offsetAndBreadthForPositionedChild(child, ForRows, rowOffset, rowBreadth);
1650
1651         child.setOverrideContainingBlockContentLogicalWidth(columnBreadth);
1652         child.setOverrideContainingBlockContentLogicalHeight(rowBreadth);
1653         child.setExtraInlineOffset(columnOffset);
1654         child.setExtraBlockOffset(rowOffset);
1655
1656         if (child.parent() == this) {
1657             auto& childLayer = *child.layer();
1658             childLayer.setStaticInlinePosition(borderStart() + columnOffset);
1659             childLayer.setStaticBlockPosition(borderBefore() + rowOffset);
1660         }
1661     }
1662
1663     RenderBlock::layoutPositionedObject(child, relayoutChildren, fixedPositionObjectsOnly);
1664 }
1665
1666 void RenderGrid::offsetAndBreadthForPositionedChild(const RenderBox& child, GridTrackSizingDirection direction, LayoutUnit& offset, LayoutUnit& breadth)
1667 {
1668     ASSERT(child.isHorizontalWritingMode() == isHorizontalWritingMode());
1669     bool isRowAxis = direction == ForColumns;
1670
1671     unsigned autoRepeatCount = autoRepeatCountForDirection(direction);
1672     GridSpan positions = GridPositionsResolver::resolveGridPositionsFromStyle(style(), child, direction, autoRepeatCount);
1673     if (positions.isIndefinite()) {
1674         offset = LayoutUnit();
1675         breadth = isRowAxis ? clientLogicalWidth() : clientLogicalHeight();
1676         return;
1677     }
1678
1679     // 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.
1680     int smallestStart = std::abs(isRowAxis ? m_smallestColumnStart : m_smallestRowStart);
1681     int startLine = positions.untranslatedStartLine() + smallestStart;
1682     int endLine = positions.untranslatedEndLine() + smallestStart;
1683
1684     GridPosition startPosition = isRowAxis ? child.style().gridItemColumnStart() : child.style().gridItemRowStart();
1685     GridPosition endPosition = isRowAxis ? child.style().gridItemColumnEnd() : child.style().gridItemRowEnd();
1686     int lastLine = isRowAxis ? gridColumnCount() : gridRowCount();
1687
1688     bool startIsAuto = startPosition.isAuto()
1689         || (startPosition.isNamedGridArea() && !NamedLineCollection::isValidNamedLineOrArea(startPosition.namedGridLine(), style(), (direction == ForColumns) ? ColumnStartSide : RowStartSide))
1690         || (startLine < 0)
1691         || (startLine > lastLine);
1692     bool endIsAuto = endPosition.isAuto()
1693         || (endPosition.isNamedGridArea() && !NamedLineCollection::isValidNamedLineOrArea(endPosition.namedGridLine(), style(), (direction == ForColumns) ? ColumnEndSide : RowEndSide))
1694         || (endLine < 0)
1695         || (endLine > lastLine);
1696
1697     // We're normalizing the positions to avoid issues with RTL (as they're stored in the same order than LTR but adding an offset).
1698     LayoutUnit start;
1699     if (!startIsAuto) {
1700         if (isRowAxis) {
1701             if (style().isLeftToRightDirection())
1702                 start = m_columnPositions[startLine] - borderLogicalLeft();
1703             else
1704                 start = logicalWidth() - translateRTLCoordinate(m_columnPositions[startLine]) - borderLogicalRight();
1705         } else
1706             start = m_rowPositions[startLine] - borderBefore();
1707     }
1708
1709     LayoutUnit end = isRowAxis ? clientLogicalWidth() : clientLogicalHeight();
1710     if (!endIsAuto) {
1711         if (isRowAxis) {
1712             if (style().isLeftToRightDirection())
1713                 end = m_columnPositions[endLine] - borderLogicalLeft();
1714             else
1715                 end = logicalWidth() - translateRTLCoordinate(m_columnPositions[endLine]) - borderLogicalRight();
1716         } else
1717             end = m_rowPositions[endLine] - borderBefore();
1718
1719         // These vectors store line positions including gaps, but we shouldn't consider them for the edges of the grid.
1720         if (endLine > 0 && endLine < lastLine) {
1721             end -= guttersSize(direction, 2);
1722             end -= isRowAxis ? m_offsetBetweenColumns : m_offsetBetweenRows;
1723         }
1724     }
1725
1726     breadth = end - start;
1727     offset = start;
1728
1729     if (isRowAxis && !style().isLeftToRightDirection() && !child.style().hasStaticInlinePosition(child.isHorizontalWritingMode())) {
1730         // If the child doesn't have a static inline position (i.e. "left" and/or "right" aren't "auto",
1731         // we need to calculate the offset from the left (even if we're in RTL).
1732         if (endIsAuto)
1733             offset = LayoutUnit();
1734         else {
1735             offset = translateRTLCoordinate(m_columnPositions[endLine]) - borderLogicalLeft();
1736
1737             if (endLine > 0 && endLine < lastLine) {
1738                 offset += guttersSize(direction, 2);
1739                 offset += isRowAxis ? m_offsetBetweenColumns : m_offsetBetweenRows;
1740             }
1741         }
1742     }
1743 }
1744
1745 GridArea RenderGrid::cachedGridArea(const RenderBox& gridItem) const
1746 {
1747     ASSERT(m_gridItemArea.contains(&gridItem));
1748     return m_gridItemArea.get(&gridItem);
1749 }
1750
1751 GridSpan RenderGrid::cachedGridSpan(const RenderBox& gridItem, GridTrackSizingDirection direction) const
1752 {
1753     GridArea area = cachedGridArea(gridItem);
1754     return direction == ForColumns ? area.columns : area.rows;
1755 }
1756
1757 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
1758 {
1759     const GridSpan& span = cachedGridSpan(child, direction);
1760     LayoutUnit gridAreaBreadth = 0;
1761     for (auto trackPosition : span)
1762         gridAreaBreadth += tracks[trackPosition].baseSize();
1763
1764     gridAreaBreadth += guttersSize(direction, span.integerSpan());
1765
1766     return gridAreaBreadth;
1767 }
1768
1769 LayoutUnit RenderGrid::gridAreaBreadthForChildIncludingAlignmentOffsets(const RenderBox& child, GridTrackSizingDirection direction, const GridSizingData& sizingData) const
1770 {
1771     // We need the cached value when available because Content Distribution alignment properties
1772     // may have some influence in the final grid area breadth.
1773     const auto& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
1774     const auto& span = cachedGridSpan(child, direction);
1775     const auto& linePositions = (direction == ForColumns) ? m_columnPositions : m_rowPositions;
1776
1777     LayoutUnit initialTrackPosition = linePositions[span.startLine()];
1778     LayoutUnit finalTrackPosition = linePositions[span.endLine() - 1];
1779
1780     // Track Positions vector stores the 'start' grid line of each track, so we have to add last track's baseSize.
1781     return finalTrackPosition - initialTrackPosition + tracks[span.endLine() - 1].baseSize();
1782 }
1783
1784 void RenderGrid::populateGridPositionsForDirection(GridSizingData& sizingData, GridTrackSizingDirection direction)
1785 {
1786     // Since we add alignment offsets and track gutters, grid lines are not always adjacent. Hence we will have to
1787     // assume from now on that we just store positions of the initial grid lines of each track,
1788     // except the last one, which is the only one considered as a final grid line of a track.
1789
1790     // The grid container's frame elements (border, padding and <content-position> offset) are sensible to the
1791     // inline-axis flow direction. However, column lines positions are 'direction' unaware. This simplification
1792     // allows us to use the same indexes to identify the columns independently on the inline-axis direction.
1793     bool isRowAxis = direction == ForColumns;
1794     auto& tracks = isRowAxis ? sizingData.columnTracks : sizingData.rowTracks;
1795     unsigned numberOfTracks = tracks.size();
1796     unsigned numberOfLines = numberOfTracks + 1;
1797     unsigned lastLine = numberOfLines - 1;
1798
1799     ContentAlignmentData offset = computeContentPositionAndDistributionOffset(direction, sizingData.freeSpaceForDirection(direction).value(), numberOfTracks);
1800     LayoutUnit trackGap = guttersSize(direction, 2);
1801     auto& positions = isRowAxis ? m_columnPositions : m_rowPositions;
1802     positions.resize(numberOfLines);
1803     auto borderAndPadding = isRowAxis ? borderAndPaddingLogicalLeft() : borderAndPaddingBefore();
1804     positions[0] = borderAndPadding + offset.positionOffset;
1805     if (numberOfLines > 1) {
1806         unsigned nextToLastLine = numberOfLines - 2;
1807         for (unsigned i = 0; i < nextToLastLine; ++i)
1808             positions[i + 1] = positions[i] + offset.distributionOffset + tracks[i].baseSize() + trackGap;
1809         positions[lastLine] = positions[nextToLastLine] + tracks[nextToLastLine].baseSize();
1810     }
1811     auto& offsetBetweenTracks = isRowAxis ? m_offsetBetweenColumns : m_offsetBetweenRows;
1812     offsetBetweenTracks = offset.distributionOffset;
1813 }
1814
1815 static inline LayoutUnit computeOverflowAlignmentOffset(OverflowAlignment overflow, LayoutUnit trackBreadth, LayoutUnit childBreadth)
1816 {
1817     LayoutUnit offset = trackBreadth - childBreadth;
1818     switch (overflow) {
1819     case OverflowAlignmentSafe:
1820         // If overflow is 'safe', we have to make sure we don't overflow the 'start'
1821         // edge (potentially cause some data loss as the overflow is unreachable).
1822         return std::max<LayoutUnit>(0, offset);
1823     case OverflowAlignmentUnsafe:
1824     case OverflowAlignmentDefault:
1825         // If we overflow our alignment container and overflow is 'true' (default), we
1826         // ignore the overflow and just return the value regardless (which may cause data
1827         // loss as we overflow the 'start' edge).
1828         return offset;
1829     }
1830
1831     ASSERT_NOT_REACHED();
1832     return 0;
1833 }
1834
1835 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1836 bool RenderGrid::needToStretchChildLogicalHeight(const RenderBox& child) const
1837 {
1838     if (child.style().resolvedAlignSelf(style(), selfAlignmentNormalBehavior).position() != ItemPositionStretch)
1839         return false;
1840
1841     return isHorizontalWritingMode() && child.style().height().isAuto();
1842 }
1843
1844 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1845 LayoutUnit RenderGrid::marginLogicalHeightForChild(const RenderBox& child) const
1846 {
1847     return isHorizontalWritingMode() ? child.verticalMarginExtent() : child.horizontalMarginExtent();
1848 }
1849
1850 LayoutUnit RenderGrid::computeMarginLogicalSizeForChild(GridTrackSizingDirection direction, const RenderBox& child) const
1851 {
1852     if (!child.style().hasMargin())
1853         return 0;
1854
1855     LayoutUnit marginStart;
1856     LayoutUnit marginEnd;
1857     if (direction == ForColumns)
1858         child.computeInlineDirectionMargins(*this, child.containingBlockLogicalWidthForContentInRegion(nullptr), child.logicalWidth(), marginStart, marginEnd);
1859     else
1860         child.computeBlockDirectionMargins(*this, marginStart, marginEnd);
1861
1862     return marginStart + marginEnd;
1863 }
1864
1865 LayoutUnit RenderGrid::availableAlignmentSpaceForChildBeforeStretching(LayoutUnit gridAreaBreadthForChild, const RenderBox& child) const
1866 {
1867     // Because we want to avoid multiple layouts, stretching logic might be performed before
1868     // children are laid out, so we can't use the child cached values. Hence, we need to
1869     // compute margins in order to determine the available height before stretching.
1870     return gridAreaBreadthForChild - (child.needsLayout() ? computeMarginLogicalSizeForChild(ForRows, child) : marginLogicalHeightForChild(child));
1871 }
1872
1873 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1874 void RenderGrid::applyStretchAlignmentToChildIfNeeded(RenderBox& child)
1875 {
1876     ASSERT(child.overrideContainingBlockContentLogicalHeight());
1877
1878     // We clear height override values because we will decide now whether it's allowed or
1879     // not, evaluating the conditions which might have changed since the old values were set.
1880     child.clearOverrideLogicalContentHeight();
1881
1882     auto& gridStyle = style();
1883     auto& childStyle = child.style();
1884     bool isHorizontalMode = isHorizontalWritingMode();
1885     bool hasAutoSizeInColumnAxis = isHorizontalMode ? childStyle.height().isAuto() : childStyle.width().isAuto();
1886     bool allowedToStretchChildAlongColumnAxis = hasAutoSizeInColumnAxis && !childStyle.marginBeforeUsing(&gridStyle).isAuto() && !childStyle.marginAfterUsing(&gridStyle).isAuto();
1887     if (allowedToStretchChildAlongColumnAxis && childStyle.resolvedAlignSelf(style(), selfAlignmentNormalBehavior).position() == ItemPositionStretch) {
1888         // TODO (lajava): If the child has orthogonal flow, then it already has an override height set, so use it.
1889         // TODO (lajava): grid track sizing and positioning do not support orthogonal modes yet.
1890         if (child.isHorizontalWritingMode() == isHorizontalMode) {
1891             LayoutUnit stretchedLogicalHeight = availableAlignmentSpaceForChildBeforeStretching(child.overrideContainingBlockContentLogicalHeight().value(), child);
1892             LayoutUnit desiredLogicalHeight = child.constrainLogicalHeightByMinMax(stretchedLogicalHeight, Nullopt);
1893             child.setOverrideLogicalContentHeight(desiredLogicalHeight - child.borderAndPaddingLogicalHeight());
1894             if (desiredLogicalHeight != child.logicalHeight()) {
1895                 // TODO (lajava): Can avoid laying out here in some cases. See https://webkit.org/b/87905.
1896                 child.setLogicalHeight(0);
1897                 child.setNeedsLayout();
1898             }
1899         }
1900     }
1901 }
1902
1903 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1904 bool RenderGrid::hasAutoMarginsInColumnAxis(const RenderBox& child) const
1905 {
1906     if (isHorizontalWritingMode())
1907         return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1908     return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1909 }
1910
1911 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1912 bool RenderGrid::hasAutoMarginsInRowAxis(const RenderBox& child) const
1913 {
1914     if (isHorizontalWritingMode())
1915         return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1916     return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1917 }
1918
1919 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1920 void RenderGrid::updateAutoMarginsInRowAxisIfNeeded(RenderBox& child)
1921 {
1922     ASSERT(!child.isOutOfFlowPositioned());
1923
1924     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalWidth().value() - child.logicalWidth() - child.marginLogicalWidth();
1925     if (availableAlignmentSpace <= 0)
1926         return;
1927
1928     const RenderStyle& parentStyle = style();
1929     Length marginStart = child.style().marginStartUsing(&parentStyle);
1930     Length marginEnd = child.style().marginEndUsing(&parentStyle);
1931     if (marginStart.isAuto() && marginEnd.isAuto()) {
1932         child.setMarginStart(availableAlignmentSpace / 2, &parentStyle);
1933         child.setMarginEnd(availableAlignmentSpace / 2, &parentStyle);
1934     } else if (marginStart.isAuto()) {
1935         child.setMarginStart(availableAlignmentSpace, &parentStyle);
1936     } else if (marginEnd.isAuto()) {
1937         child.setMarginEnd(availableAlignmentSpace, &parentStyle);
1938     }
1939 }
1940
1941 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1942 void RenderGrid::updateAutoMarginsInColumnAxisIfNeeded(RenderBox& child)
1943 {
1944     ASSERT(!child.isOutOfFlowPositioned());
1945
1946     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalHeight().value() - child.logicalHeight() - child.marginLogicalHeight();
1947     if (availableAlignmentSpace <= 0)
1948         return;
1949
1950     const RenderStyle& parentStyle = style();
1951     Length marginBefore = child.style().marginBeforeUsing(&parentStyle);
1952     Length marginAfter = child.style().marginAfterUsing(&parentStyle);
1953     if (marginBefore.isAuto() && marginAfter.isAuto()) {
1954         child.setMarginBefore(availableAlignmentSpace / 2, &parentStyle);
1955         child.setMarginAfter(availableAlignmentSpace / 2, &parentStyle);
1956     } else if (marginBefore.isAuto()) {
1957         child.setMarginBefore(availableAlignmentSpace, &parentStyle);
1958     } else if (marginAfter.isAuto()) {
1959         child.setMarginAfter(availableAlignmentSpace, &parentStyle);
1960     }
1961 }
1962
1963 GridAxisPosition RenderGrid::columnAxisPositionForChild(const RenderBox& child) const
1964 {
1965     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
1966     bool hasSameWritingMode = child.style().writingMode() == style().writingMode();
1967
1968     switch (child.style().resolvedAlignSelf(style(), selfAlignmentNormalBehavior).position()) {
1969     case ItemPositionSelfStart:
1970         // If orthogonal writing-modes, this computes to 'start'.
1971         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1972         // self-start is based on the child's block axis direction. That's why we need to check against the grid container's block flow.
1973         return (hasOrthogonalWritingMode || hasSameWritingMode) ? GridAxisStart : GridAxisEnd;
1974     case ItemPositionSelfEnd:
1975         // If orthogonal writing-modes, this computes to 'end'.
1976         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1977         // self-end is based on the child's block axis direction. That's why we need to check against the grid container's block flow.
1978         return (hasOrthogonalWritingMode || hasSameWritingMode) ? GridAxisEnd : GridAxisStart;
1979     case ItemPositionLeft:
1980         // The alignment axis (column axis) and the inline axis are parallell in
1981         // orthogonal writing mode. Otherwise this this is equivalent to 'start'.
1982         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1983         return GridAxisStart;
1984     case ItemPositionRight:
1985         // The alignment axis (column axis) and the inline axis are parallell in
1986         // orthogonal writing mode. Otherwise this this is equivalent to 'start'.
1987         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1988         return hasOrthogonalWritingMode ? GridAxisEnd : GridAxisStart;
1989     case ItemPositionCenter:
1990         return GridAxisCenter;
1991     case ItemPositionFlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
1992     case ItemPositionStart:
1993         return GridAxisStart;
1994     case ItemPositionFlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
1995     case ItemPositionEnd:
1996         return GridAxisEnd;
1997     case ItemPositionStretch:
1998         return GridAxisStart;
1999     case ItemPositionBaseline:
2000     case ItemPositionLastBaseline:
2001         // FIXME: Implement the previous values. For now, we always 'start' align the child.
2002         return GridAxisStart;
2003     case ItemPositionAuto:
2004     case ItemPositionNormal:
2005         break;
2006     }
2007
2008     ASSERT_NOT_REACHED();
2009     return GridAxisStart;
2010 }
2011
2012 GridAxisPosition RenderGrid::rowAxisPositionForChild(const RenderBox& child) const
2013 {
2014     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
2015     bool hasSameDirection = child.style().direction() == style().direction();
2016     bool isLTR = style().isLeftToRightDirection();
2017
2018     switch (child.style().resolvedJustifySelf(style(), selfAlignmentNormalBehavior).position()) {
2019     case ItemPositionSelfStart:
2020         // For orthogonal writing-modes, this computes to 'start'
2021         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
2022         // self-start is based on the child's direction. That's why we need to check against the grid container's direction.
2023         return (hasOrthogonalWritingMode || hasSameDirection) ? GridAxisStart : GridAxisEnd;
2024     case ItemPositionSelfEnd:
2025         // For orthogonal writing-modes, this computes to 'start'
2026         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
2027         return (hasOrthogonalWritingMode || hasSameDirection) ? GridAxisEnd : GridAxisStart;
2028     case ItemPositionLeft:
2029         return isLTR ? GridAxisStart : GridAxisEnd;
2030     case ItemPositionRight:
2031         return isLTR ? GridAxisEnd : GridAxisStart;
2032     case ItemPositionCenter:
2033         return GridAxisCenter;
2034     case ItemPositionFlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
2035     case ItemPositionStart:
2036         return GridAxisStart;
2037     case ItemPositionFlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
2038     case ItemPositionEnd:
2039         return GridAxisEnd;
2040     case ItemPositionStretch:
2041         return GridAxisStart;
2042     case ItemPositionBaseline:
2043     case ItemPositionLastBaseline:
2044         // FIXME: Implement the previous values. For now, we always 'start' align the child.
2045         return GridAxisStart;
2046     case ItemPositionAuto:
2047     case ItemPositionNormal:
2048         break;
2049     }
2050
2051     ASSERT_NOT_REACHED();
2052     return GridAxisStart;
2053 }
2054
2055 LayoutUnit RenderGrid::columnAxisOffsetForChild(const RenderBox& child) const
2056 {
2057     const GridSpan& rowsSpan = cachedGridSpan(child, ForRows);
2058     unsigned childStartLine = rowsSpan.startLine();
2059     LayoutUnit startOfRow = m_rowPositions[childStartLine];
2060     LayoutUnit startPosition = startOfRow + marginBeforeForChild(child);
2061     if (hasAutoMarginsInColumnAxis(child))
2062         return startPosition;
2063     GridAxisPosition axisPosition = columnAxisPositionForChild(child);
2064     switch (axisPosition) {
2065     case GridAxisStart:
2066         return startPosition;
2067     case GridAxisEnd:
2068     case GridAxisCenter: {
2069         unsigned childEndLine = rowsSpan.endLine();
2070         LayoutUnit endOfRow = m_rowPositions[childEndLine];
2071         // m_rowPositions include distribution offset (because of content alignment) and gutters
2072         // so we need to subtract them to get the actual end position for a given row
2073         // (this does not have to be done for the last track as there are no more m_rowPositions after it).
2074         if (childEndLine < m_rowPositions.size() - 1)
2075             endOfRow -= guttersSize(ForRows, 2) + m_offsetBetweenRows;
2076         LayoutUnit childBreadth = child.logicalHeight() + child.marginLogicalHeight();
2077         auto overflow = child.style().resolvedAlignSelf(style(), selfAlignmentNormalBehavior).overflow();
2078         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(overflow, endOfRow - startOfRow, childBreadth);
2079         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
2080     }
2081     }
2082
2083     ASSERT_NOT_REACHED();
2084     return 0;
2085 }
2086
2087
2088 LayoutUnit RenderGrid::rowAxisOffsetForChild(const RenderBox& child) const
2089 {
2090     const GridSpan& columnsSpan = cachedGridSpan(child, ForColumns);
2091     unsigned childStartLine = columnsSpan.startLine();
2092     LayoutUnit startOfColumn = m_columnPositions[childStartLine];
2093     LayoutUnit startPosition = startOfColumn + marginStartForChild(child);
2094     if (hasAutoMarginsInRowAxis(child))
2095         return startPosition;
2096     GridAxisPosition axisPosition = rowAxisPositionForChild(child);
2097     switch (axisPosition) {
2098     case GridAxisStart:
2099         return startPosition;
2100     case GridAxisEnd:
2101     case GridAxisCenter: {
2102         unsigned childEndLine = columnsSpan.endLine();
2103         LayoutUnit endOfColumn = m_columnPositions[childEndLine];
2104         // m_columnPositions include distribution offset (because of content alignment) and gutters
2105         // so we need to subtract them to get the actual end position for a given column
2106         // (this does not have to be done for the last track as there are no more m_columnPositions after it).
2107         if (childEndLine < m_columnPositions.size() - 1)
2108             endOfColumn -= guttersSize(ForColumns, 2) + m_offsetBetweenColumns;
2109         LayoutUnit childBreadth = child.logicalWidth() + child.marginLogicalWidth();
2110         auto overflow = child.style().resolvedJustifySelf(style(), selfAlignmentNormalBehavior).overflow();
2111         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(overflow, endOfColumn - startOfColumn, childBreadth);
2112         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
2113     }
2114     }
2115
2116     ASSERT_NOT_REACHED();
2117     return 0;
2118 }
2119
2120 ContentPosition static resolveContentDistributionFallback(ContentDistributionType distribution)
2121 {
2122     switch (distribution) {
2123     case ContentDistributionSpaceBetween:
2124         return ContentPositionStart;
2125     case ContentDistributionSpaceAround:
2126         return ContentPositionCenter;
2127     case ContentDistributionSpaceEvenly:
2128         return ContentPositionCenter;
2129     case ContentDistributionStretch:
2130         return ContentPositionStart;
2131     case ContentDistributionDefault:
2132         return ContentPositionNormal;
2133     }
2134
2135     ASSERT_NOT_REACHED();
2136     return ContentPositionNormal;
2137 }
2138
2139 static ContentAlignmentData contentDistributionOffset(const LayoutUnit& availableFreeSpace, ContentPosition& fallbackPosition, ContentDistributionType distribution, unsigned numberOfGridTracks)
2140 {
2141     if (distribution != ContentDistributionDefault && fallbackPosition == ContentPositionNormal)
2142         fallbackPosition = resolveContentDistributionFallback(distribution);
2143
2144     if (availableFreeSpace <= 0)
2145         return ContentAlignmentData::defaultOffsets();
2146
2147     LayoutUnit distributionOffset;
2148     switch (distribution) {
2149     case ContentDistributionSpaceBetween:
2150         if (numberOfGridTracks < 2)
2151             return ContentAlignmentData::defaultOffsets();
2152         return {0, availableFreeSpace / (numberOfGridTracks - 1)};
2153     case ContentDistributionSpaceAround:
2154         if (numberOfGridTracks < 1)
2155             return ContentAlignmentData::defaultOffsets();
2156         distributionOffset = availableFreeSpace / numberOfGridTracks;
2157         return {distributionOffset / 2, distributionOffset};
2158     case ContentDistributionSpaceEvenly:
2159         distributionOffset = availableFreeSpace / (numberOfGridTracks + 1);
2160         return {distributionOffset, distributionOffset};
2161     case ContentDistributionStretch:
2162     case ContentDistributionDefault:
2163         return ContentAlignmentData::defaultOffsets();
2164     }
2165
2166     ASSERT_NOT_REACHED();
2167     return ContentAlignmentData::defaultOffsets();
2168 }
2169
2170 ContentAlignmentData RenderGrid::computeContentPositionAndDistributionOffset(GridTrackSizingDirection direction, const LayoutUnit& availableFreeSpace, unsigned numberOfGridTracks) const
2171 {
2172     bool isRowAxis = direction == ForColumns;
2173     auto position = isRowAxis ? style().resolvedJustifyContentPosition(contentAlignmentNormalBehaviorGrid()) : style().resolvedAlignContentPosition(contentAlignmentNormalBehaviorGrid());
2174     auto distribution = isRowAxis ? style().resolvedJustifyContentDistribution(contentAlignmentNormalBehaviorGrid()) : style().resolvedAlignContentDistribution(contentAlignmentNormalBehaviorGrid());
2175     // If <content-distribution> value can't be applied, 'position' will become the associated
2176     // <content-position> fallback value.
2177     auto contentAlignment = contentDistributionOffset(availableFreeSpace, position, distribution, numberOfGridTracks);
2178     if (contentAlignment.isValid())
2179         return contentAlignment;
2180
2181     auto overflow = isRowAxis ? style().justifyContentOverflowAlignment() : style().alignContentOverflowAlignment();
2182     if (availableFreeSpace <= 0 && overflow == OverflowAlignmentSafe)
2183         return {0, 0};
2184
2185     switch (position) {
2186     case ContentPositionLeft:
2187         // The align-content's axis is always orthogonal to the inline-axis.
2188         return {0, 0};
2189     case ContentPositionRight:
2190         if (isRowAxis)
2191             return {availableFreeSpace, 0};
2192         // The align-content's axis is always orthogonal to the inline-axis.
2193         return {0, 0};
2194     case ContentPositionCenter:
2195         return {availableFreeSpace / 2, 0};
2196     case ContentPositionFlexEnd: // Only used in flex layout, for other layout, it's equivalent to 'end'.
2197     case ContentPositionEnd:
2198         if (isRowAxis)
2199             return {style().isLeftToRightDirection() ? availableFreeSpace : LayoutUnit(), LayoutUnit()};
2200         return {availableFreeSpace, 0};
2201     case ContentPositionFlexStart: // Only used in flex layout, for other layout, it's equivalent to 'start'.
2202     case ContentPositionStart:
2203         if (isRowAxis)
2204             return {style().isLeftToRightDirection() ? LayoutUnit() : availableFreeSpace, LayoutUnit()};
2205         return {0, 0};
2206     case ContentPositionBaseline:
2207     case ContentPositionLastBaseline:
2208         // FIXME: Implement the previous values. For now, we always 'start' align.
2209         // http://webkit.org/b/145566
2210         if (isRowAxis)
2211             return {style().isLeftToRightDirection() ? LayoutUnit() : availableFreeSpace, LayoutUnit()};
2212         return {0, 0};
2213     case ContentPositionNormal:
2214         break;
2215     }
2216
2217     ASSERT_NOT_REACHED();
2218     return {0, 0};
2219 }
2220
2221 LayoutUnit RenderGrid::translateRTLCoordinate(LayoutUnit coordinate) const
2222 {
2223     ASSERT(!style().isLeftToRightDirection());
2224
2225     LayoutUnit alignmentOffset = m_columnPositions[0];
2226     LayoutUnit rightGridEdgePosition = m_columnPositions[m_columnPositions.size() - 1];
2227     return rightGridEdgePosition + alignmentOffset - coordinate;
2228 }
2229
2230 LayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox& child) const
2231 {
2232     LayoutUnit rowAxisOffset = rowAxisOffsetForChild(child);
2233     // We stored m_columnPositions's data ignoring the direction, hence we might need now
2234     // to translate positions from RTL to LTR, as it's more convenient for painting.
2235     if (!style().isLeftToRightDirection())
2236         rowAxisOffset = translateRTLCoordinate(rowAxisOffset) - child.logicalWidth();
2237
2238     return LayoutPoint(rowAxisOffset, columnAxisOffsetForChild(child));
2239 }
2240
2241 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset, PaintInfo& forChild, bool usePrintRect)
2242 {
2243     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next())
2244         paintChild(*child, paintInfo, paintOffset, forChild, usePrintRect, PaintAsInlineBlock);
2245 }
2246
2247 const char* RenderGrid::renderName() const
2248 {
2249     if (isFloating())
2250         return "RenderGrid (floating)";
2251     if (isOutOfFlowPositioned())
2252         return "RenderGrid (positioned)";
2253     if (isAnonymous())
2254         return "RenderGrid (generated)";
2255     if (isRelPositioned())
2256         return "RenderGrid (relative positioned)";
2257     return "RenderGrid";
2258 }
2259
2260 } // namespace WebCore
2261
2262 #endif /* ENABLE(CSS_GRID_LAYOUT) */