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