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