[CSS Grid Layout] Skip items spanning flex tracks when sizing content based tracks
[WebKit-https.git] / Source / WebCore / rendering / RenderGrid.cpp
1 /*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
3  * Copyright (C) 2013, 2014 Igalia S.L.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "RenderGrid.h"
29
30 #if ENABLE(CSS_GRID_LAYOUT)
31
32 #include "GridCoordinate.h"
33 #include "GridResolvedPosition.h"
34 #include "LayoutRepainter.h"
35 #include "RenderLayer.h"
36 #include "RenderView.h"
37 #include <wtf/NeverDestroyed.h>
38
39 namespace WebCore {
40
41 static const int infinity = -1;
42
43 class GridTrack {
44 public:
45     GridTrack()
46         : m_usedBreadth(0)
47         , m_maxBreadth(0)
48     {
49     }
50
51     void growUsedBreadth(LayoutUnit growth)
52     {
53         ASSERT(growth >= 0);
54         m_usedBreadth += growth;
55     }
56     LayoutUnit usedBreadth() const { return m_usedBreadth; }
57
58     void growMaxBreadth(LayoutUnit growth)
59     {
60         if (m_maxBreadth == infinity)
61             m_maxBreadth = m_usedBreadth + growth;
62         else
63             m_maxBreadth += growth;
64     }
65     LayoutUnit maxBreadthIfNotInfinite() const
66     {
67         return (m_maxBreadth == infinity) ? m_usedBreadth : m_maxBreadth;
68     }
69
70     LayoutUnit m_usedBreadth;
71     LayoutUnit m_maxBreadth;
72 };
73
74 struct GridTrackForNormalization {
75     GridTrackForNormalization(const GridTrack& track, double flex)
76         : m_track(&track)
77         , m_flex(flex)
78         , m_normalizedFlexValue(track.m_usedBreadth / flex)
79     {
80     }
81
82     const GridTrack* m_track;
83     double m_flex;
84     LayoutUnit m_normalizedFlexValue;
85 };
86
87 class RenderGrid::GridIterator {
88     WTF_MAKE_NONCOPYABLE(GridIterator);
89 public:
90     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
91     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
92     GridIterator(const Vector<Vector<Vector<RenderBox*, 1>>>& grid, GridTrackSizingDirection direction, unsigned fixedTrackIndex, unsigned varyingTrackIndex = 0)
93         : m_grid(grid)
94         , m_direction(direction)
95         , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
96         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
97         , m_childIndex(0)
98     {
99         ASSERT(m_rowIndex < m_grid.size());
100         ASSERT(m_columnIndex < m_grid[0].size());
101     }
102
103     RenderBox* nextGridItem()
104     {
105         if (!m_grid.size())
106             return 0;
107
108         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
109         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
110         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
111             const Vector<RenderBox*>& children = m_grid[m_rowIndex][m_columnIndex];
112             if (m_childIndex < children.size())
113                 return children[m_childIndex++];
114
115             m_childIndex = 0;
116         }
117         return 0;
118     }
119
120     bool isEmptyAreaEnough(unsigned rowSpan, unsigned columnSpan) const
121     {
122         // Ignore cells outside current grid as we will grow it later if needed.
123         unsigned maxRows = std::min<unsigned>(m_rowIndex + rowSpan, m_grid.size());
124         unsigned maxColumns = std::min<unsigned>(m_columnIndex + columnSpan, m_grid[0].size());
125
126         // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
127         for (unsigned row = m_rowIndex; row < maxRows; ++row) {
128             for (unsigned column = m_columnIndex; column < maxColumns; ++column) {
129                 const Vector<RenderBox*>& children = m_grid[row][column];
130                 if (!children.isEmpty())
131                     return false;
132             }
133         }
134
135         return true;
136     }
137
138     std::unique_ptr<GridCoordinate> nextEmptyGridArea(unsigned fixedTrackSpan, unsigned varyingTrackSpan)
139     {
140         ASSERT(fixedTrackSpan >= 1 && varyingTrackSpan >= 1);
141
142         if (m_grid.isEmpty())
143             return nullptr;
144
145         unsigned rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
146         unsigned columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
147
148         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
149         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
150         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
151             if (isEmptyAreaEnough(rowSpan, columnSpan)) {
152                 std::unique_ptr<GridCoordinate> result = std::make_unique<GridCoordinate>(GridSpan(m_rowIndex, m_rowIndex + rowSpan - 1), GridSpan(m_columnIndex, m_columnIndex + columnSpan - 1));
153                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
154                 ++varyingTrackIndex;
155                 return result;
156             }
157         }
158         return nullptr;
159     }
160
161 private:
162     const Vector<Vector<Vector<RenderBox*, 1>>>& m_grid;
163     GridTrackSizingDirection m_direction;
164     unsigned m_rowIndex;
165     unsigned m_columnIndex;
166     unsigned m_childIndex;
167 };
168
169 class RenderGrid::GridSizingData {
170     WTF_MAKE_NONCOPYABLE(GridSizingData);
171 public:
172     GridSizingData(unsigned gridColumnCount, unsigned gridRowCount)
173         : columnTracks(gridColumnCount)
174         , rowTracks(gridRowCount)
175     {
176     }
177
178     Vector<GridTrack> columnTracks;
179     Vector<GridTrack> rowTracks;
180     Vector<unsigned> contentSizedTracksIndex;
181
182     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
183     Vector<LayoutUnit> distributeTrackVector;
184     Vector<GridTrack*> filteredTracks;
185     Vector<unsigned> growAboveMaxBreadthTrackIndexes;
186     Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
187 };
188
189 RenderGrid::RenderGrid(Element& element, Ref<RenderStyle>&& style)
190     : RenderBlock(element, WTF::move(style), 0)
191     , m_orderIterator(*this)
192 {
193     // All of our children must be block level.
194     setChildrenInline(false);
195 }
196
197 RenderGrid::~RenderGrid()
198 {
199 }
200
201 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
202 {
203     ASSERT(needsLayout());
204
205     if (!relayoutChildren && simplifiedLayout())
206         return;
207
208     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
209     // It would be nice to refactor some of the duplicate code.
210     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
211     LayoutStateMaintainer statePusher(view(), *this, locationOffset(), hasTransform() || hasReflection() || style().isFlippedBlocksWritingMode());
212
213     preparePaginationBeforeBlockLayout(relayoutChildren);
214
215     LayoutSize previousSize = size();
216
217     setLogicalHeight(0);
218     updateLogicalWidth();
219
220     layoutGridItems();
221
222     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
223     updateLogicalHeight();
224
225     if (size() != previousSize)
226         relayoutChildren = true;
227
228     layoutPositionedObjects(relayoutChildren || isRoot());
229
230     computeOverflow(oldClientAfterEdge);
231     statePusher.pop();
232
233     updateLayerTransform();
234
235     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
236     // we overflow or not.
237     updateScrollInfoAfterLayout();
238
239     repainter.repaintAfterLayout();
240
241     clearNeedsLayout();
242 }
243
244 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
245 {
246     bool wasPopulated = gridWasPopulated();
247     if (!wasPopulated)
248         const_cast<RenderGrid*>(this)->placeItemsOnGrid();
249
250     GridSizingData sizingData(gridColumnCount(), gridRowCount());
251     LayoutUnit availableLogicalSpace = 0;
252     const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace);
253
254     for (auto& column : sizingData.columnTracks) {
255         LayoutUnit minTrackBreadth = column.m_usedBreadth;
256         LayoutUnit maxTrackBreadth = column.m_maxBreadth;
257         maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth);
258
259         minLogicalWidth += minTrackBreadth;
260         maxLogicalWidth += maxTrackBreadth;
261
262         // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
263     }
264
265     if (!wasPopulated)
266         const_cast<RenderGrid*>(this)->clearGrid();
267 }
268
269 void RenderGrid::computePreferredLogicalWidths()
270 {
271     ASSERT(preferredLogicalWidthsDirty());
272
273     m_minPreferredLogicalWidth = 0;
274     m_maxPreferredLogicalWidth = 0;
275
276     // FIXME: We don't take our own logical width into account. Once we do, we need to make sure
277     // we apply (and test the interaction with) min-width / max-width.
278
279     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
280
281     LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
282     m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
283     m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
284
285     setPreferredLogicalWidthsDirty(false);
286 }
287
288 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData)
289 {
290     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
291     computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace);
292 }
293
294 bool RenderGrid::gridElementIsShrinkToFit()
295 {
296     return isFloatingOrOutOfFlowPositioned();
297 }
298
299 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
300 {
301     const LayoutUnit initialAvailableLogicalSpace = availableLogicalSpace;
302     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
303     Vector<unsigned> flexibleSizedTracksIndex;
304     sizingData.contentSizedTracksIndex.shrink(0);
305
306     // 1. Initialize per Grid track variables.
307     for (unsigned i = 0; i < tracks.size(); ++i) {
308         GridTrack& track = tracks[i];
309         const GridTrackSize& trackSize = gridTrackSize(direction, i);
310         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
311         const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
312
313         track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth);
314         track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.m_usedBreadth);
315
316         if (track.m_maxBreadth != infinity)
317             track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth);
318
319         if (trackSize.isContentSized())
320             sizingData.contentSizedTracksIndex.append(i);
321         if (trackSize.maxTrackBreadth().isFlex())
322             flexibleSizedTracksIndex.append(i);
323     }
324
325     // 2. Resolve content-based TrackSizingFunctions.
326     if (!sizingData.contentSizedTracksIndex.isEmpty())
327         resolveContentBasedTrackSizingFunctions(direction, sizingData);
328
329     for (auto& track : tracks) {
330         ASSERT(track.m_maxBreadth != infinity);
331         availableLogicalSpace -= track.m_usedBreadth;
332     }
333
334     const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style().logicalHeight().isAuto() : gridElementIsShrinkToFit();
335
336     if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0)
337         return;
338
339     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until availableLogicalSpace is exhausted.
340     if (!hasUndefinedRemainingSpace) {
341         const unsigned tracksSize = tracks.size();
342         Vector<GridTrack*> tracksForDistribution(tracksSize);
343         for (unsigned i = 0; i < tracksSize; ++i)
344             tracksForDistribution[i] = tracks.data() + i;
345
346         distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, sizingData, availableLogicalSpace);
347     } else {
348         for (auto& track : tracks)
349             track.m_usedBreadth = std::max(track.m_usedBreadth, track.m_maxBreadth);
350     }
351
352     if (flexibleSizedTracksIndex.isEmpty())
353         return;
354
355     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
356     double normalizedFractionBreadth = 0;
357     if (!hasUndefinedRemainingSpace)
358         normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, initialAvailableLogicalSpace);
359     else {
360         for (auto trackIndex : flexibleSizedTracksIndex) {
361             const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
362             normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].m_usedBreadth / trackSize.maxTrackBreadth().flex());
363         }
364
365         for (unsigned i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
366             GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
367             while (RenderBox* gridItem = iterator.nextGridItem()) {
368                 const GridCoordinate coordinate = cachedGridCoordinate(*gridItem);
369                 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
370
371                 // Do not include already processed items.
372                 if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1])
373                     continue;
374
375                 double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData.columnTracks));
376                 normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
377             }
378         }
379     }
380
381     for (auto trackIndex : flexibleSizedTracksIndex) {
382         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
383         GridTrack& track = tracks[trackIndex];
384         track.m_usedBreadth = std::max<LayoutUnit>(track.m_usedBreadth, normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
385     }
386 }
387
388 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
389 {
390     if (gridLength.isFlex())
391         return 0;
392
393     const Length& trackLength = gridLength.length();
394     ASSERT(!trackLength.isAuto());
395     if (trackLength.isSpecified())
396         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
397
398     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
399     return 0;
400 }
401
402 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const
403 {
404     if (gridLength.isFlex())
405         return usedBreadth;
406
407     const Length& trackLength = gridLength.length();
408     ASSERT(!trackLength.isAuto());
409     if (trackLength.isSpecified()) {
410         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
411         ASSERT(computedBreadth != infinity);
412         return computedBreadth;
413     }
414
415     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
416     return infinity;
417 }
418
419 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
420 {
421     ASSERT(trackLength.isSpecified());
422     return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style().logicalHeight()));
423 }
424
425 double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit spaceToFill) const
426 {
427     LayoutUnit allocatedSpace;
428     Vector<GridTrackForNormalization> tracksForNormalization;
429     for (auto& position : tracksSpan) {
430         GridTrack& track = tracks[position.toInt()];
431         allocatedSpace += track.m_usedBreadth;
432
433         const GridTrackSize& trackSize = gridTrackSize(direction, position.toInt());
434         if (!trackSize.maxTrackBreadth().isFlex())
435             continue;
436
437         tracksForNormalization.append(GridTrackForNormalization(track, trackSize.maxTrackBreadth().flex()));
438     }
439
440     // The function is not called if we don't have <flex> grid tracks
441     ASSERT(!tracksForNormalization.isEmpty());
442
443     std::sort(tracksForNormalization.begin(), tracksForNormalization.end(),
444               [](const GridTrackForNormalization& track1, const GridTrackForNormalization& track2) {
445                   return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
446               });
447
448     // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
449     // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
450     // fit into availableLogicalSpaceIgnoringFractionTracks.
451     double accumulatedFractions = 0;
452     LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
453     LayoutUnit availableLogicalSpaceIgnoringFractionTracks = spaceToFill - allocatedSpace;
454
455     for (auto& track : tracksForNormalization) {
456         if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
457             // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
458             // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
459             if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
460                 break;
461
462             fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
463         }
464
465         accumulatedFractions += track.m_flex;
466         // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
467         availableLogicalSpaceIgnoringFractionTracks += track.m_track->m_usedBreadth;
468     }
469
470     return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
471 }
472
473 GridTrackSize RenderGrid::gridTrackSize(GridTrackSizingDirection direction, unsigned i) const
474 {
475     bool isForColumns = (direction == ForColumns);
476     auto& trackStyles =  isForColumns ? style().gridColumns() : style().gridRows();
477     auto& trackSize = (i >= trackStyles.size()) ? (isForColumns ? style().gridAutoColumns() : style().gridAutoRows()) : trackStyles[i];
478
479     // If the logical width/height of the grid container is indefinite, percentage values are treated as <auto> (or in
480     // the case of minmax() as min-content for the first position and max-content for the second).
481     Length logicalSize = isForColumns ? style().logicalWidth() : style().logicalHeight();
482     if (logicalSize.isIntrinsicOrAuto()) {
483         const GridLength& oldMinTrackBreadth = trackSize.minTrackBreadth();
484         const GridLength& oldMaxTrackBreadth = trackSize.maxTrackBreadth();
485         return GridTrackSize(oldMinTrackBreadth.isPercentage() ? Length(MinContent) : oldMinTrackBreadth, oldMaxTrackBreadth.isPercentage() ? Length(MaxContent) : oldMaxTrackBreadth);
486     }
487
488     return trackSize;
489 }
490
491 LayoutUnit RenderGrid::logicalContentHeightForChild(RenderBox& child, Vector<GridTrack>& columnTracks)
492 {
493     LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child.hasOverrideContainingBlockLogicalWidth() ? child.overrideContainingBlockContentLogicalWidth() : LayoutUnit();
494     LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
495     if (child.style().logicalHeight().isPercent() || oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth)
496         child.setNeedsLayout(MarkOnlyThis);
497
498     child.setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
499     // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is
500     // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution).
501     child.setOverrideContainingBlockContentLogicalHeight(-1);
502     child.layoutIfNeeded();
503     return child.logicalHeight() + child.marginLogicalHeight();
504 }
505
506 LayoutUnit RenderGrid::minContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
507 {
508     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
509     // FIXME: Properly support orthogonal writing mode.
510     if (hasOrthogonalWritingMode)
511         return 0;
512
513     if (direction == ForColumns) {
514         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
515         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
516         return child.minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
517     }
518
519     return logicalContentHeightForChild(child, columnTracks);
520 }
521
522 LayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
523 {
524     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
525     // FIXME: Properly support orthogonal writing mode.
526     if (hasOrthogonalWritingMode)
527         return LayoutUnit();
528
529     if (direction == ForColumns) {
530         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
531         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
532         return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
533     }
534
535     return logicalContentHeightForChild(child, columnTracks);
536 }
537
538 class GridItemWithSpan {
539 public:
540     GridItemWithSpan(RenderBox& gridItem, GridCoordinate coordinate, GridTrackSizingDirection direction)
541         : m_gridItem(gridItem)
542         , m_coordinate(coordinate)
543     {
544         const GridSpan& span = (direction == ForRows) ? coordinate.rows : coordinate.columns;
545         m_span = span.resolvedFinalPosition.toInt() - span.resolvedInitialPosition.toInt() + 1;
546     }
547
548     RenderBox& gridItem() const { return m_gridItem; }
549     GridCoordinate coordinate() const { return m_coordinate; }
550
551     bool operator<(const GridItemWithSpan other) const
552     {
553         return m_span < other.m_span;
554     }
555
556 private:
557     std::reference_wrapper<RenderBox> m_gridItem;
558     GridCoordinate m_coordinate;
559     unsigned m_span;
560 };
561
562 bool RenderGrid::spanningItemCrossesFlexibleSizedTracks(const GridCoordinate& coordinate, GridTrackSizingDirection direction) const
563 {
564     const GridSpan itemSpan = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
565     for (auto trackPosition : itemSpan) {
566         const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition.toInt());
567         if (trackSize.minTrackBreadth().isFlex() || trackSize.maxTrackBreadth().isFlex())
568             return true;
569     }
570
571     return false;
572 }
573
574 static inline unsigned integerSpanForDirection(const GridCoordinate& coordinate, GridTrackSizingDirection direction)
575 {
576     return (direction == ForRows) ? coordinate.rows.integerSpan() : coordinate.columns.integerSpan();
577 }
578
579 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData)
580 {
581     sizingData.itemsSortedByIncreasingSpan.shrink(0);
582     HashSet<RenderBox*> itemsSet;
583     for (auto trackIndex : sizingData.contentSizedTracksIndex) {
584         GridIterator iterator(m_grid, direction, trackIndex);
585
586         while (RenderBox* gridItem = iterator.nextGridItem()) {
587             if (itemsSet.add(gridItem).isNewEntry) {
588                 const GridCoordinate& coordinate = cachedGridCoordinate(*gridItem);
589                 // We should not include items spanning more than one track that span tracks with flexible sizing functions.
590                 if (integerSpanForDirection(coordinate, direction) == 1 || !spanningItemCrossesFlexibleSizedTracks(coordinate, direction))
591                     sizingData.itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, coordinate, direction));
592             }
593         }
594     }
595     std::sort(sizingData.itemsSortedByIncreasingSpan.begin(), sizingData.itemsSortedByIncreasingSpan.end());
596
597     for (auto& itemWithSpan : sizingData.itemsSortedByIncreasingSpan) {
598         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, &GridTrackSize::hasMinContentMinTrackBreadthAndMinOrMaxContentMaxTrackBreadth);
599         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, &GridTrackSize::hasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth);
600         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
601         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
602     }
603
604     for (auto trackIndex : sizingData.contentSizedTracksIndex) {
605         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
606         if (track.m_maxBreadth == infinity)
607             track.m_maxBreadth = track.m_usedBreadth;
608     }
609 }
610
611 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, GridItemWithSpan& gridItemWithSpan, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, FilterFunction growAboveMaxBreadthFilterFunction)
612 {
613     const GridCoordinate& coordinate = gridItemWithSpan.coordinate();
614     const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
615     const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
616
617     sizingData.filteredTracks.shrink(0);
618     sizingData.growAboveMaxBreadthTrackIndexes.shrink(0);
619     for (GridResolvedPosition trackIndex = initialTrackPosition; trackIndex <= finalTrackPosition; ++trackIndex) {
620         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex.toInt());
621         if (!(trackSize.*filterFunction)())
622             continue;
623
624         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex.toInt()] : sizingData.rowTracks[trackIndex.toInt()];
625         sizingData.filteredTracks.append(&track);
626
627         if (growAboveMaxBreadthFilterFunction && (trackSize.*growAboveMaxBreadthFilterFunction)())
628             sizingData.growAboveMaxBreadthTrackIndexes.append(sizingData.filteredTracks.size() - 1);
629     }
630
631     if (sizingData.filteredTracks.isEmpty())
632         return;
633
634     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItemWithSpan.gridItem(), direction, sizingData.columnTracks);
635     for (GridResolvedPosition trackPositionForSpace = initialTrackPosition; trackPositionForSpace <= finalTrackPosition; ++trackPositionForSpace) {
636         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPositionForSpace.toInt()] : sizingData.rowTracks[trackPositionForSpace.toInt()];
637         additionalBreadthSpace -= (track.*trackGetter)();
638     }
639
640     // Specs mandate to floor additionalBreadthSpace (extra-space in specs) to 0. Instead we directly avoid the function
641     // call in those cases as it will be a noop in terms of track sizing.
642     if (additionalBreadthSpace > 0)
643         distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.growAboveMaxBreadthTrackIndexes, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
644 }
645
646 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
647 {
648     // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
649     // (forall x: NOT x < x).
650     if (track1->m_maxBreadth == infinity && track2->m_maxBreadth == infinity)
651         return false;
652
653     if (track1->m_maxBreadth == infinity || track2->m_maxBreadth == infinity)
654         return track2->m_maxBreadth == infinity;
655
656     return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
657 }
658
659 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<unsigned>* growAboveMaxBreadthTrackIndexes, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
660 {
661     ASSERT(availableLogicalSpace > 0);
662     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
663
664     unsigned tracksSize = tracks.size();
665     sizingData.distributeTrackVector.resize(tracksSize);
666
667     for (unsigned i = 0; i < tracksSize; ++i) {
668         GridTrack& track = *tracks[i];
669         LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
670         bool infiniteGrowthPotential = track.m_maxBreadth == infinity;
671         LayoutUnit trackGrowthPotential = infiniteGrowthPotential ? track.m_maxBreadth : track.m_maxBreadth - trackBreadth;
672         sizingData.distributeTrackVector[i] = trackBreadth;
673         // Let's avoid computing availableLogicalSpaceShare as much as possible as it's a hot spot in performance tests.
674         if (trackGrowthPotential > 0 || infiniteGrowthPotential) {
675             LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
676             LayoutUnit growthShare = infiniteGrowthPotential ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, trackGrowthPotential);
677             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 availableLogicalSpace.");
678             sizingData.distributeTrackVector[i] += growthShare;
679             availableLogicalSpace -= growthShare;
680         }
681     }
682
683     if (availableLogicalSpace > 0 && growAboveMaxBreadthTrackIndexes) {
684         unsigned indexesSize = growAboveMaxBreadthTrackIndexes->size();
685         unsigned tracksGrowingAboveMaxBreadthSize = indexesSize ? indexesSize : tracksSize;
686         // If we have a non-null empty vector of track indexes to grow above max breadth means that we should grow all
687         // affected tracks.
688         for (unsigned i = 0; i < tracksGrowingAboveMaxBreadthSize; ++i) {
689             LayoutUnit growthShare = availableLogicalSpace / (tracksGrowingAboveMaxBreadthSize - i);
690             unsigned distributeTrackIndex = indexesSize ? growAboveMaxBreadthTrackIndexes->at(i) : i;
691             sizingData.distributeTrackVector[distributeTrackIndex] += growthShare;
692             availableLogicalSpace -= growthShare;
693         }
694     }
695
696     for (unsigned i = 0; i < tracksSize; ++i) {
697         LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
698         if (growth >= 0)
699             (tracks[i]->*trackGrowthFunction)(growth);
700     }
701 }
702
703 #ifndef NDEBUG
704 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
705 {
706     for (unsigned i = 0; i < tracks.size(); ++i) {
707         const GridTrackSize& trackSize = gridTrackSize(direction, i);
708         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
709         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth)
710             return false;
711     }
712     return true;
713 }
714 #endif
715
716 void RenderGrid::ensureGridSize(unsigned maximumRowIndex, unsigned maximumColumnIndex)
717 {
718     const unsigned oldRowCount = gridRowCount();
719     if (maximumRowIndex >= oldRowCount) {
720         m_grid.grow(maximumRowIndex + 1);
721         for (unsigned row = oldRowCount; row < gridRowCount(); ++row)
722             m_grid[row].grow(gridColumnCount());
723     }
724
725     if (maximumColumnIndex >= gridColumnCount()) {
726         for (unsigned row = 0; row < gridRowCount(); ++row)
727             m_grid[row].grow(maximumColumnIndex + 1);
728     }
729 }
730
731 void RenderGrid::insertItemIntoGrid(RenderBox& child, const GridCoordinate& coordinate)
732 {
733     ensureGridSize(coordinate.rows.resolvedFinalPosition.toInt(), coordinate.columns.resolvedFinalPosition.toInt());
734
735     for (auto& row : coordinate.rows) {
736         for (auto& column : coordinate.columns)
737             m_grid[row.toInt()][column.toInt()].append(&child);
738     }
739     m_gridItemCoordinate.set(&child, coordinate);
740 }
741
742 void RenderGrid::placeItemsOnGrid()
743 {
744     ASSERT(!gridWasPopulated());
745     ASSERT(m_gridItemCoordinate.isEmpty());
746
747     populateExplicitGridAndOrderIterator();
748
749     Vector<RenderBox*> autoMajorAxisAutoGridItems;
750     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
751     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
752         // FIXME: We never re-resolve positions if the grid is grown during auto-placement which may lead auto / <integer>
753         // positions to not match the author's intent. The specification is unclear on what should be done in this case.
754         std::unique_ptr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForRows);
755         std::unique_ptr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForColumns);
756         if (!rowPositions || !columnPositions) {
757             GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get();
758             if (!majorAxisPositions)
759                 autoMajorAxisAutoGridItems.append(child);
760             else
761                 specifiedMajorAxisAutoGridItems.append(child);
762             continue;
763         }
764         insertItemIntoGrid(*child, GridCoordinate(*rowPositions, *columnPositions));
765     }
766
767     ASSERT(gridRowCount() >= GridResolvedPosition::explicitGridRowCount(style()));
768     ASSERT(gridColumnCount() >= GridResolvedPosition::explicitGridColumnCount(style()));
769
770     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
771     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
772 }
773
774 void RenderGrid::populateExplicitGridAndOrderIterator()
775 {
776     OrderIteratorPopulator populator(m_orderIterator);
777     unsigned maximumRowIndex = std::max<unsigned>(1, GridResolvedPosition::explicitGridRowCount(style()));
778     unsigned maximumColumnIndex = std::max<unsigned>(1, GridResolvedPosition::explicitGridColumnCount(style()));
779
780     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
781         populator.collectChild(*child);
782
783         // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
784         std::unique_ptr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForRows);
785         std::unique_ptr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForColumns);
786
787         // |positions| is 0 if we need to run the auto-placement algorithm.
788         if (rowPositions)
789             maximumRowIndex = std::max(maximumRowIndex, rowPositions->resolvedFinalPosition.next().toInt());
790         else {
791             // Grow the grid for items with a definite row span, getting the largest such span.
792             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *child, ForRows, GridResolvedPosition(0));
793             maximumRowIndex = std::max(maximumRowIndex, positions.resolvedFinalPosition.next().toInt());
794         }
795
796         if (columnPositions)
797             maximumColumnIndex = std::max(maximumColumnIndex, columnPositions->resolvedFinalPosition.next().toInt());
798         else {
799             // Grow the grid for items with a definite column span, getting the largest such span.
800             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *child, ForColumns, GridResolvedPosition(0));
801             maximumColumnIndex = std::max(maximumColumnIndex, positions.resolvedFinalPosition.next().toInt());
802         }
803     }
804
805     m_grid.grow(maximumRowIndex);
806     for (auto& column : m_grid)
807         column.grow(maximumColumnIndex);
808 }
809
810 std::unique_ptr<GridCoordinate> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox& gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
811 {
812     GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
813     const unsigned endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount();
814     GridSpan crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection));
815     return std::make_unique<GridCoordinate>(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions);
816 }
817
818 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
819 {
820     for (auto& autoGridItem : autoGridItems) {
821         std::unique_ptr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *autoGridItem, autoPlacementMajorAxisDirection());
822         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *autoGridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
823
824         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt());
825         std::unique_ptr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->integerSpan(), minorAxisPositions.integerSpan());
826         if (!emptyGridArea)
827             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(*autoGridItem, autoPlacementMajorAxisDirection(), *majorAxisPositions);
828         insertItemIntoGrid(*autoGridItem, *emptyGridArea);
829     }
830 }
831
832 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
833 {
834     AutoPlacementCursor autoPlacementCursor = {0, 0};
835     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
836
837     for (auto& autoGridItem : autoGridItems) {
838         placeAutoMajorAxisItemOnGrid(*autoGridItem, autoPlacementCursor);
839
840         if (isGridAutoFlowDense) {
841             autoPlacementCursor.first = 0;
842             autoPlacementCursor.second = 0;
843         }
844     }
845 }
846
847 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox& gridItem, AutoPlacementCursor& autoPlacementCursor)
848 {
849     std::unique_ptr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), gridItem, autoPlacementMinorAxisDirection());
850     ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(style(), gridItem, autoPlacementMajorAxisDirection()));
851     GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(0));
852
853     const unsigned endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
854     unsigned majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
855     unsigned minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
856
857     std::unique_ptr<GridCoordinate> emptyGridArea;
858     if (minorAxisPositions) {
859         // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
860         if (minorAxisPositions->resolvedInitialPosition.toInt() < minorAxisAutoPlacementCursor)
861             majorAxisAutoPlacementCursor++;
862
863         if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
864             GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions->resolvedInitialPosition.toInt(), majorAxisAutoPlacementCursor);
865             emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->integerSpan(), majorAxisPositions.integerSpan());
866         }
867
868         if (!emptyGridArea)
869             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
870     } else {
871         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
872
873         for (unsigned majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
874             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
875             emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan());
876
877             if (emptyGridArea) {
878                 // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
879                 GridResolvedPosition minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.resolvedFinalPosition : emptyGridArea->rows.resolvedFinalPosition;
880                 const unsigned endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount();
881                 if (minorAxisFinalPositionIndex.toInt() < endOfMinorAxis)
882                     break;
883
884                 // Discard empty grid area as it does not fit in the minor axis direction.
885                 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
886                 emptyGridArea = nullptr;
887             }
888
889             // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
890             minorAxisAutoPlacementCursor = 0;
891         }
892
893         if (!emptyGridArea)
894             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
895     }
896
897     insertItemIntoGrid(gridItem, *emptyGridArea);
898     autoPlacementCursor.first = emptyGridArea->rows.resolvedInitialPosition.toInt();
899     autoPlacementCursor.second = emptyGridArea->columns.resolvedInitialPosition.toInt();
900 }
901
902 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
903 {
904     return style().isGridAutoFlowDirectionColumn() ? ForColumns : ForRows;
905 }
906
907 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
908 {
909     return style().isGridAutoFlowDirectionColumn() ? ForRows : ForColumns;
910 }
911
912 void RenderGrid::clearGrid()
913 {
914     m_grid.clear();
915     m_gridItemCoordinate.clear();
916 }
917
918 void RenderGrid::layoutGridItems()
919 {
920     placeItemsOnGrid();
921
922     GridSizingData sizingData(gridColumnCount(), gridRowCount());
923     computeUsedBreadthOfGridTracks(ForColumns, sizingData);
924     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
925     computeUsedBreadthOfGridTracks(ForRows, sizingData);
926     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
927
928     populateGridPositions(sizingData);
929
930     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
931         // Because the grid area cannot be styled, we don't need to adjust
932         // the grid breadth to account for 'box-sizing'.
933         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
934         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
935
936         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(*child, ForColumns, sizingData.columnTracks);
937         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(*child, ForRows, sizingData.rowTracks);
938         if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && child->hasRelativeLogicalHeight()))
939             child->setNeedsLayout(MarkOnlyThis);
940
941         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
942         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
943
944         LayoutRect oldChildRect = child->frameRect();
945
946         // FIXME: Grid items should stretch to fill their cells. Once we
947         // implement grid-{column,row}-align, we can also shrink to fit. For
948         // now, just size as if we were a regular child.
949         child->layoutIfNeeded();
950
951         child->setLogicalLocation(findChildLogicalPosition(*child, sizingData));
952
953         // If the child moved, we have to repaint it as well as any floating/positioned
954         // descendants. An exception is if we need a layout. In this case, we know we're going to
955         // repaint ourselves (and the child) anyway.
956         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
957             child->repaintDuringLayoutIfMoved(oldChildRect);
958     }
959
960     for (auto& row : sizingData.rowTracks)
961         setLogicalHeight(logicalHeight() + row.m_usedBreadth);
962
963     // min / max logical height is handled in updateLogicalHeight().
964     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
965     clearGrid();
966 }
967
968 GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox& gridItem) const
969 {
970     ASSERT(m_gridItemCoordinate.contains(&gridItem));
971     return m_gridItemCoordinate.get(&gridItem);
972 }
973
974 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
975 {
976     const GridCoordinate& coordinate = cachedGridCoordinate(child);
977     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
978     LayoutUnit gridAreaBreadth = 0;
979     for (auto& trackPosition : span)
980         gridAreaBreadth += tracks[trackPosition.toInt()].m_usedBreadth;
981     return gridAreaBreadth;
982 }
983
984 void RenderGrid::populateGridPositions(const GridSizingData& sizingData)
985 {
986     m_columnPositions.resizeToFit(sizingData.columnTracks.size() + 1);
987     m_columnPositions[0] = borderAndPaddingStart();
988     for (unsigned i = 0; i < m_columnPositions.size() - 1; ++i)
989         m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].m_usedBreadth;
990
991     m_rowPositions.resizeToFit(sizingData.rowTracks.size() + 1);
992     m_rowPositions[0] = borderAndPaddingBefore();
993     for (unsigned i = 0; i < m_rowPositions.size() - 1; ++i)
994         m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].m_usedBreadth;
995 }
996
997 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox& child, const GridSizingData& sizingData)
998 {
999     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1000     ASSERT_UNUSED(sizingData, coordinate.columns.resolvedInitialPosition.toInt() < sizingData.columnTracks.size());
1001     ASSERT_UNUSED(sizingData, coordinate.rows.resolvedInitialPosition.toInt() < sizingData.rowTracks.size());
1002
1003     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1004     return LayoutPoint(m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()] + marginStartForChild(child), m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()] + marginBeforeForChild(child));
1005 }
1006
1007 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset, PaintInfo& forChild, bool usePrintRect)
1008 {
1009     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next())
1010         paintChild(*child, paintInfo, paintOffset, forChild, usePrintRect);
1011 }
1012
1013 const char* RenderGrid::renderName() const
1014 {
1015     if (isFloating())
1016         return "RenderGrid (floating)";
1017     if (isOutOfFlowPositioned())
1018         return "RenderGrid (positioned)";
1019     if (isAnonymous())
1020         return "RenderGrid (generated)";
1021     if (isRelPositioned())
1022         return "RenderGrid (relative positioned)";
1023     return "RenderGrid";
1024 }
1025
1026 } // namespace WebCore
1027
1028 #endif /* ENABLE(CSS_GRID_LAYOUT) */