[css-grid] Percentage columns shouldn't include border and padding
[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
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 GridTrackForNormalization {
120     GridTrackForNormalization(const GridTrack& track, double flex)
121         : m_track(&track)
122         , m_flex(flex)
123         , m_normalizedFlexValue(track.baseSize() / flex)
124     {
125     }
126
127     const GridTrack* m_track;
128     double m_flex;
129     LayoutUnit m_normalizedFlexValue;
130 };
131
132 class RenderGrid::GridIterator {
133     WTF_MAKE_NONCOPYABLE(GridIterator);
134 public:
135     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
136     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
137     GridIterator(const Vector<Vector<Vector<RenderBox*, 1>>>& grid, GridTrackSizingDirection direction, unsigned fixedTrackIndex, unsigned varyingTrackIndex = 0)
138         : m_grid(grid)
139         , m_direction(direction)
140         , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
141         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
142         , m_childIndex(0)
143     {
144         ASSERT(m_rowIndex < m_grid.size());
145         ASSERT(m_columnIndex < m_grid[0].size());
146     }
147
148     RenderBox* nextGridItem()
149     {
150         if (!m_grid.size())
151             return 0;
152
153         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
154         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
155         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
156             const auto& children = m_grid[m_rowIndex][m_columnIndex];
157             if (m_childIndex < children.size())
158                 return children[m_childIndex++];
159
160             m_childIndex = 0;
161         }
162         return 0;
163     }
164
165     bool isEmptyAreaEnough(unsigned rowSpan, unsigned columnSpan) const
166     {
167         // Ignore cells outside current grid as we will grow it later if needed.
168         unsigned maxRows = std::min<unsigned>(m_rowIndex + rowSpan, m_grid.size());
169         unsigned maxColumns = std::min<unsigned>(m_columnIndex + columnSpan, m_grid[0].size());
170
171         // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
172         for (unsigned row = m_rowIndex; row < maxRows; ++row) {
173             for (unsigned column = m_columnIndex; column < maxColumns; ++column) {
174                 auto& children = m_grid[row][column];
175                 if (!children.isEmpty())
176                     return false;
177             }
178         }
179
180         return true;
181     }
182
183     std::unique_ptr<GridCoordinate> nextEmptyGridArea(unsigned fixedTrackSpan, unsigned varyingTrackSpan)
184     {
185         ASSERT(fixedTrackSpan >= 1 && varyingTrackSpan >= 1);
186
187         if (m_grid.isEmpty())
188             return nullptr;
189
190         unsigned rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
191         unsigned columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
192
193         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
194         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
195         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
196             if (isEmptyAreaEnough(rowSpan, columnSpan)) {
197                 std::unique_ptr<GridCoordinate> result = std::make_unique<GridCoordinate>(GridSpan(m_rowIndex, m_rowIndex + rowSpan - 1), GridSpan(m_columnIndex, m_columnIndex + columnSpan - 1));
198                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
199                 ++varyingTrackIndex;
200                 return result;
201             }
202         }
203         return nullptr;
204     }
205
206 private:
207     const Vector<Vector<Vector<RenderBox*, 1>>>& m_grid;
208     GridTrackSizingDirection m_direction;
209     unsigned m_rowIndex;
210     unsigned m_columnIndex;
211     unsigned m_childIndex;
212 };
213
214 class RenderGrid::GridSizingData {
215     WTF_MAKE_NONCOPYABLE(GridSizingData);
216 public:
217     GridSizingData(unsigned gridColumnCount, unsigned gridRowCount)
218         : columnTracks(gridColumnCount)
219         , rowTracks(gridRowCount)
220     {
221     }
222
223     Vector<GridTrack> columnTracks;
224     Vector<GridTrack> rowTracks;
225     Vector<unsigned> contentSizedTracksIndex;
226
227     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
228     Vector<GridTrack*> filteredTracks;
229     Vector<GridTrack*> growBeyondGrowthLimitsTracks;
230     Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
231 };
232
233 RenderGrid::RenderGrid(Element& element, Ref<RenderStyle>&& style)
234     : RenderBlock(element, WTF::move(style), 0)
235     , m_orderIterator(*this)
236 {
237     // All of our children must be block level.
238     setChildrenInline(false);
239 }
240
241 RenderGrid::~RenderGrid()
242 {
243 }
244
245 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
246 {
247     ASSERT(needsLayout());
248
249     if (!relayoutChildren && simplifiedLayout())
250         return;
251
252     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
253     // It would be nice to refactor some of the duplicate code.
254     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
255     LayoutStateMaintainer statePusher(view(), *this, locationOffset(), hasTransform() || hasReflection() || style().isFlippedBlocksWritingMode());
256
257     preparePaginationBeforeBlockLayout(relayoutChildren);
258
259     LayoutSize previousSize = size();
260
261     setLogicalHeight(0);
262     updateLogicalWidth();
263
264     layoutGridItems();
265
266     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
267     updateLogicalHeight();
268
269     if (size() != previousSize)
270         relayoutChildren = true;
271
272     layoutPositionedObjects(relayoutChildren || isRoot());
273
274     computeOverflow(oldClientAfterEdge);
275     statePusher.pop();
276
277     updateLayerTransform();
278
279     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
280     // we overflow or not.
281     updateScrollInfoAfterLayout();
282
283     repainter.repaintAfterLayout();
284
285     clearNeedsLayout();
286 }
287
288 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
289 {
290     bool wasPopulated = gridWasPopulated();
291     if (!wasPopulated)
292         const_cast<RenderGrid*>(this)->placeItemsOnGrid();
293
294     GridSizingData sizingData(gridColumnCount(), gridRowCount());
295     LayoutUnit availableLogicalSpace = 0;
296     const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace);
297
298     for (auto& column : sizingData.columnTracks) {
299         LayoutUnit minTrackBreadth = column.baseSize();
300         LayoutUnit maxTrackBreadth = column.growthLimit();
301
302         minLogicalWidth += minTrackBreadth;
303         maxLogicalWidth += maxTrackBreadth;
304     }
305
306     LayoutUnit scrollbarWidth = intrinsicScrollbarLogicalWidth();
307     minLogicalWidth += scrollbarWidth;
308     maxLogicalWidth += scrollbarWidth;
309
310     if (!wasPopulated)
311         const_cast<RenderGrid*>(this)->clearGrid();
312 }
313
314 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData)
315 {
316     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
317     computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace);
318 }
319
320 bool RenderGrid::gridElementIsShrinkToFit()
321 {
322     return isFloatingOrOutOfFlowPositioned();
323 }
324
325 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
326 {
327     const LayoutUnit initialAvailableLogicalSpace = availableLogicalSpace;
328     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
329     Vector<unsigned> flexibleSizedTracksIndex;
330     sizingData.contentSizedTracksIndex.shrink(0);
331
332     // 1. Initialize per Grid track variables.
333     for (unsigned i = 0; i < tracks.size(); ++i) {
334         GridTrack& track = tracks[i];
335         const GridTrackSize& trackSize = gridTrackSize(direction, i);
336         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
337         const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
338
339         track.setBaseSize(computeUsedBreadthOfMinLength(direction, minTrackBreadth));
340         track.setGrowthLimit(computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.baseSize()));
341         track.setInfinitelyGrowable(false);
342
343         if (trackSize.isContentSized())
344             sizingData.contentSizedTracksIndex.append(i);
345         if (trackSize.maxTrackBreadth().isFlex())
346             flexibleSizedTracksIndex.append(i);
347     }
348
349     // 2. Resolve content-based TrackSizingFunctions.
350     if (!sizingData.contentSizedTracksIndex.isEmpty())
351         resolveContentBasedTrackSizingFunctions(direction, sizingData);
352
353     for (auto& track : tracks) {
354         ASSERT(!track.growthLimitIsInfinite());
355         availableLogicalSpace -= track.baseSize();
356     }
357
358     const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style().logicalHeight().isAuto() : gridElementIsShrinkToFit();
359
360     if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0)
361         return;
362
363     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until availableLogicalSpace is exhausted.
364     if (!hasUndefinedRemainingSpace) {
365         const unsigned tracksSize = tracks.size();
366         Vector<GridTrack*> tracksForDistribution(tracksSize);
367         for (unsigned i = 0; i < tracksSize; ++i) {
368             tracksForDistribution[i] = tracks.data() + i;
369             tracksForDistribution[i]->setPlannedSize(tracksForDistribution[i]->baseSize());
370         }
371
372         distributeSpaceToTracks<MaximizeTracks>(tracksForDistribution, nullptr, availableLogicalSpace);
373
374         for (auto* track : tracksForDistribution)
375             track->setBaseSize(track->plannedSize());
376     } else {
377         for (auto& track : tracks)
378             track.setBaseSize(track.growthLimit());
379     }
380
381     if (flexibleSizedTracksIndex.isEmpty())
382         return;
383
384     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
385     double normalizedFractionBreadth = 0;
386     if (!hasUndefinedRemainingSpace)
387         normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, initialAvailableLogicalSpace);
388     else {
389         for (auto trackIndex : flexibleSizedTracksIndex) {
390             const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
391             normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].baseSize() / trackSize.maxTrackBreadth().flex());
392         }
393
394         for (unsigned i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
395             GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
396             while (RenderBox* gridItem = iterator.nextGridItem()) {
397                 const GridCoordinate coordinate = cachedGridCoordinate(*gridItem);
398                 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
399
400                 // Do not include already processed items.
401                 if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1])
402                     continue;
403
404                 double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData.columnTracks));
405                 normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
406             }
407         }
408     }
409
410     for (auto trackIndex : flexibleSizedTracksIndex) {
411         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
412         GridTrack& track = tracks[trackIndex];
413         LayoutUnit baseSize = std::max<LayoutUnit>(track.baseSize(), normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
414         track.setBaseSize(baseSize);
415         availableLogicalSpace -= baseSize;
416     }
417 }
418
419 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
420 {
421     if (gridLength.isFlex())
422         return 0;
423
424     const Length& trackLength = gridLength.length();
425     ASSERT(!trackLength.isAuto());
426     if (trackLength.isSpecified())
427         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
428
429     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
430     return 0;
431 }
432
433 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const
434 {
435     if (gridLength.isFlex())
436         return usedBreadth;
437
438     const Length& trackLength = gridLength.length();
439     ASSERT(!trackLength.isAuto());
440     if (trackLength.isSpecified()) {
441         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
442         ASSERT(computedBreadth != infinity);
443         return computedBreadth;
444     }
445
446     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
447     return infinity;
448 }
449
450 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
451 {
452     ASSERT(trackLength.isSpecified());
453     if (direction == ForColumns)
454         return valueForLength(trackLength, logicalWidth() - borderAndPaddingLogicalWidth());
455     return valueForLength(trackLength, computeContentLogicalHeight(style().logicalHeight(), Nullopt).valueOr(0));
456 }
457
458 double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit spaceToFill) const
459 {
460     LayoutUnit allocatedSpace;
461     Vector<GridTrackForNormalization> tracksForNormalization;
462     for (auto& position : tracksSpan) {
463         GridTrack& track = tracks[position.toInt()];
464         allocatedSpace += track.baseSize();
465
466         const GridTrackSize& trackSize = gridTrackSize(direction, position.toInt());
467         if (!trackSize.maxTrackBreadth().isFlex())
468             continue;
469
470         tracksForNormalization.append(GridTrackForNormalization(track, trackSize.maxTrackBreadth().flex()));
471     }
472
473     // The function is not called if we don't have <flex> grid tracks
474     ASSERT(!tracksForNormalization.isEmpty());
475
476     std::sort(tracksForNormalization.begin(), tracksForNormalization.end(),
477               [](const GridTrackForNormalization& track1, const GridTrackForNormalization& track2) {
478                   return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
479               });
480
481     // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
482     // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
483     // fit into availableLogicalSpaceIgnoringFractionTracks.
484     double accumulatedFractions = 0;
485     LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
486     LayoutUnit availableLogicalSpaceIgnoringFractionTracks = spaceToFill - allocatedSpace;
487
488     for (auto& track : tracksForNormalization) {
489         if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
490             // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
491             // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
492             if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
493                 break;
494
495             fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
496         }
497
498         accumulatedFractions += track.m_flex;
499         // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
500         availableLogicalSpaceIgnoringFractionTracks += track.m_track->baseSize();
501     }
502
503     // Let flex factor sum be the sum of the flex factors of the flexible tracks. If this value
504     // is less than 1, set it to 1 instead.
505     if (accumulatedFractions < 1)
506         return availableLogicalSpaceIgnoringFractionTracks;
507
508     return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
509 }
510
511 bool RenderGrid::hasDefiniteLogicalSize(GridTrackSizingDirection direction) const
512 {
513     return (direction == ForRows) ? hasDefiniteLogicalHeight() : hasDefiniteLogicalWidth();
514 }
515
516 GridTrackSize RenderGrid::gridTrackSize(GridTrackSizingDirection direction, unsigned i) const
517 {
518     bool isForColumns = (direction == ForColumns);
519     auto& trackStyles =  isForColumns ? style().gridColumns() : style().gridRows();
520     auto& trackSize = (i >= trackStyles.size()) ? (isForColumns ? style().gridAutoColumns() : style().gridAutoRows()) : trackStyles[i];
521
522     GridLength minTrackBreadth = trackSize.minTrackBreadth();
523     GridLength maxTrackBreadth = trackSize.maxTrackBreadth();
524
525     if (minTrackBreadth.isPercentage() || maxTrackBreadth.isPercentage()) {
526         if (!hasDefiniteLogicalSize(direction)) {
527             if (minTrackBreadth.isPercentage())
528                 minTrackBreadth = Length(MinContent);
529             if (maxTrackBreadth.isPercentage())
530                 maxTrackBreadth = Length(MaxContent);
531         }
532     }
533
534     return GridTrackSize(minTrackBreadth, maxTrackBreadth);
535 }
536
537 LayoutUnit RenderGrid::logicalContentHeightForChild(RenderBox& child, Vector<GridTrack>& columnTracks)
538 {
539     Optional<LayoutUnit> oldOverrideContainingBlockContentLogicalWidth = child.hasOverrideContainingBlockLogicalWidth() ? child.overrideContainingBlockContentLogicalWidth() : LayoutUnit();
540     LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
541     if (child.hasRelativeLogicalHeight() || !oldOverrideContainingBlockContentLogicalWidth || oldOverrideContainingBlockContentLogicalWidth.value() != overrideContainingBlockContentLogicalWidth) {
542         child.setNeedsLayout(MarkOnlyThis);
543         // We need to clear the stretched height to properly compute logical height during layout.
544         child.clearOverrideLogicalContentHeight();
545     }
546
547     child.setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
548     // If |child| has a relative logical height, we shouldn't let it override its intrinsic height, which is
549     // what we are interested in here. Thus we need to set the override logical height to Nullopt (no possible resolution).
550     if (child.hasRelativeLogicalHeight())
551         child.setOverrideContainingBlockContentLogicalHeight(Nullopt);
552     child.layoutIfNeeded();
553     return child.logicalHeight() + child.marginLogicalHeight();
554 }
555
556 LayoutUnit RenderGrid::minContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
557 {
558     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
559     // FIXME: Properly support orthogonal writing mode.
560     if (hasOrthogonalWritingMode)
561         return 0;
562
563     if (direction == ForColumns) {
564         // If |child| has a relative logical width, we shouldn't let it override its intrinsic width, which is
565         // what we are interested in here. Thus we need to set the override logical width to Nullopt (no possible resolution).
566         if (child.hasRelativeLogicalWidth())
567             child.setOverrideContainingBlockContentLogicalWidth(Nullopt);
568
569         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
570         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
571         return child.minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
572     }
573
574     return logicalContentHeightForChild(child, columnTracks);
575 }
576
577 LayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
578 {
579     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
580     // FIXME: Properly support orthogonal writing mode.
581     if (hasOrthogonalWritingMode)
582         return LayoutUnit();
583
584     if (direction == ForColumns) {
585         // If |child| has a relative logical width, we shouldn't let it override its intrinsic width, which is
586         // what we are interested in here. Thus we need to set the override logical width to Nullopt (no possible resolution).
587         if (child.hasRelativeLogicalWidth())
588             child.setOverrideContainingBlockContentLogicalWidth(Nullopt);
589
590         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
591         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
592         return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
593     }
594
595     return logicalContentHeightForChild(child, columnTracks);
596 }
597
598 class GridItemWithSpan {
599 public:
600     GridItemWithSpan(RenderBox& gridItem, GridCoordinate coordinate, GridTrackSizingDirection direction)
601         : m_gridItem(gridItem)
602         , m_coordinate(coordinate)
603     {
604         const GridSpan& span = (direction == ForRows) ? coordinate.rows : coordinate.columns;
605         m_span = span.resolvedFinalPosition.toInt() - span.resolvedInitialPosition.toInt() + 1;
606     }
607
608     RenderBox& gridItem() const { return m_gridItem; }
609     GridCoordinate coordinate() const { return m_coordinate; }
610 #if !ASSERT_DISABLED
611     size_t span() const { return m_span; }
612 #endif
613
614     bool operator<(const GridItemWithSpan other) const
615     {
616         return m_span < other.m_span;
617     }
618
619 private:
620     std::reference_wrapper<RenderBox> m_gridItem;
621     GridCoordinate m_coordinate;
622     unsigned m_span;
623 };
624
625 bool RenderGrid::spanningItemCrossesFlexibleSizedTracks(const GridCoordinate& coordinate, GridTrackSizingDirection direction) const
626 {
627     const GridSpan itemSpan = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
628     for (auto trackPosition : itemSpan) {
629         const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition.toInt());
630         if (trackSize.minTrackBreadth().isFlex() || trackSize.maxTrackBreadth().isFlex())
631             return true;
632     }
633
634     return false;
635 }
636
637 static inline unsigned integerSpanForDirection(const GridCoordinate& coordinate, GridTrackSizingDirection direction)
638 {
639     return (direction == ForRows) ? coordinate.rows.integerSpan() : coordinate.columns.integerSpan();
640 }
641
642 struct GridItemsSpanGroupRange {
643     Vector<GridItemWithSpan>::iterator rangeStart;
644     Vector<GridItemWithSpan>::iterator rangeEnd;
645 };
646
647 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData)
648 {
649     sizingData.itemsSortedByIncreasingSpan.shrink(0);
650     HashSet<RenderBox*> itemsSet;
651     for (auto trackIndex : sizingData.contentSizedTracksIndex) {
652         GridIterator iterator(m_grid, direction, trackIndex);
653         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
654
655         while (RenderBox* gridItem = iterator.nextGridItem()) {
656             if (itemsSet.add(gridItem).isNewEntry) {
657                 const GridCoordinate& coordinate = cachedGridCoordinate(*gridItem);
658                 if (integerSpanForDirection(coordinate, direction) == 1)
659                     resolveContentBasedTrackSizingFunctionsForNonSpanningItems(direction, coordinate, *gridItem, track, sizingData.columnTracks);
660                 else if (!spanningItemCrossesFlexibleSizedTracks(coordinate, direction))
661                     sizingData.itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, coordinate, direction));
662             }
663         }
664     }
665     std::sort(sizingData.itemsSortedByIncreasingSpan.begin(), sizingData.itemsSortedByIncreasingSpan.end());
666
667     auto it = sizingData.itemsSortedByIncreasingSpan.begin();
668     auto end = sizingData.itemsSortedByIncreasingSpan.end();
669     while (it != end) {
670         GridItemsSpanGroupRange spanGroupRange = { it, std::upper_bound(it, end, *it) };
671         resolveContentBasedTrackSizingFunctionsForItems<ResolveIntrinsicMinimums>(direction, sizingData, spanGroupRange);
672         resolveContentBasedTrackSizingFunctionsForItems<ResolveMaxContentMinimums>(direction, sizingData, spanGroupRange);
673         resolveContentBasedTrackSizingFunctionsForItems<ResolveIntrinsicMaximums>(direction, sizingData, spanGroupRange);
674         resolveContentBasedTrackSizingFunctionsForItems<ResolveMaxContentMaximums>(direction, sizingData, spanGroupRange);
675         it = spanGroupRange.rangeEnd;
676     }
677
678     for (auto trackIndex : sizingData.contentSizedTracksIndex) {
679         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
680         if (track.growthLimitIsInfinite())
681             track.setGrowthLimit(track.baseSize());
682     }
683 }
684
685 void RenderGrid::resolveContentBasedTrackSizingFunctionsForNonSpanningItems(GridTrackSizingDirection direction, const GridCoordinate& coordinate, RenderBox& gridItem, GridTrack& track, Vector<GridTrack>& columnTracks)
686 {
687     const GridResolvedPosition trackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
688     GridTrackSize trackSize = gridTrackSize(direction, trackPosition.toInt());
689
690     if (trackSize.hasMinContentMinTrackBreadth())
691         track.setBaseSize(std::max(track.baseSize(), minContentForChild(gridItem, direction, columnTracks)));
692     else if (trackSize.hasMaxContentMinTrackBreadth())
693         track.setBaseSize(std::max(track.baseSize(), maxContentForChild(gridItem, direction, columnTracks)));
694
695     if (trackSize.hasMinContentMaxTrackBreadth())
696         track.setGrowthLimit(std::max(track.growthLimit(), minContentForChild(gridItem, direction, columnTracks)));
697     else if (trackSize.hasMaxContentMaxTrackBreadth())
698         track.setGrowthLimit(std::max(track.growthLimit(), maxContentForChild(gridItem, direction, columnTracks)));
699 }
700
701 const LayoutUnit& RenderGrid::trackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track, TrackSizeRestriction restriction)
702 {
703     switch (phase) {
704     case ResolveIntrinsicMinimums:
705     case ResolveMaxContentMinimums:
706     case MaximizeTracks:
707         return track.baseSize();
708     case ResolveIntrinsicMaximums:
709     case ResolveMaxContentMaximums:
710         return restriction == AllowInfinity ? track.growthLimit() : track.growthLimitIfNotInfinite();
711     }
712
713     ASSERT_NOT_REACHED();
714     return track.baseSize();
715 }
716
717 bool RenderGrid::shouldProcessTrackForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
718 {
719     switch (phase) {
720     case ResolveIntrinsicMinimums:
721         return trackSize.hasMinOrMaxContentMinTrackBreadth();
722     case ResolveMaxContentMinimums:
723         return trackSize.hasMaxContentMinTrackBreadth();
724     case ResolveIntrinsicMaximums:
725         return trackSize.hasMinOrMaxContentMaxTrackBreadth();
726     case ResolveMaxContentMaximums:
727         return trackSize.hasMaxContentMaxTrackBreadth();
728     case MaximizeTracks:
729         ASSERT_NOT_REACHED();
730         return false;
731     }
732
733     ASSERT_NOT_REACHED();
734     return false;
735 }
736
737 bool RenderGrid::trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
738 {
739     switch (phase) {
740     case ResolveIntrinsicMinimums:
741         return trackSize.hasMinContentMinTrackBreadthAndMinOrMaxContentMaxTrackBreadth();
742     case ResolveMaxContentMinimums:
743         return trackSize.hasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth();
744     case ResolveIntrinsicMaximums:
745     case ResolveMaxContentMaximums:
746         return true;
747     case MaximizeTracks:
748         ASSERT_NOT_REACHED();
749         return false;
750     }
751
752     ASSERT_NOT_REACHED();
753     return false;
754 }
755
756 void RenderGrid::markAsInfinitelyGrowableForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
757 {
758     switch (phase) {
759     case ResolveIntrinsicMinimums:
760     case ResolveMaxContentMinimums:
761         return;
762     case ResolveIntrinsicMaximums:
763         if (trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity) == infinity  && track.plannedSize() != infinity)
764             track.setInfinitelyGrowable(true);
765         return;
766     case ResolveMaxContentMaximums:
767         if (track.infinitelyGrowable())
768             track.setInfinitelyGrowable(false);
769         return;
770     case MaximizeTracks:
771         ASSERT_NOT_REACHED();
772         return;
773     }
774
775     ASSERT_NOT_REACHED();
776 }
777
778 void RenderGrid::updateTrackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
779 {
780     switch (phase) {
781     case ResolveIntrinsicMinimums:
782     case ResolveMaxContentMinimums:
783         track.setBaseSize(track.plannedSize());
784         return;
785     case ResolveIntrinsicMaximums:
786     case ResolveMaxContentMaximums:
787         track.setGrowthLimit(track.plannedSize());
788         return;
789     case MaximizeTracks:
790         ASSERT_NOT_REACHED();
791         return;
792     }
793
794     ASSERT_NOT_REACHED();
795 }
796
797 LayoutUnit RenderGrid::currentItemSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, RenderBox& gridItem, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
798 {
799     switch (phase) {
800     case ResolveIntrinsicMinimums:
801     case ResolveIntrinsicMaximums:
802         return minContentForChild(gridItem, direction, columnTracks);
803     case ResolveMaxContentMinimums:
804     case ResolveMaxContentMaximums:
805         return maxContentForChild(gridItem, direction, columnTracks);
806     case MaximizeTracks:
807         ASSERT_NOT_REACHED();
808         return 0;
809     }
810
811     ASSERT_NOT_REACHED();
812     return 0;
813 }
814
815 template <RenderGrid::TrackSizeComputationPhase phase>
816 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, const GridItemsSpanGroupRange& gridItemsWithSpan)
817 {
818     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
819     for (const auto& trackIndex : sizingData.contentSizedTracksIndex) {
820         GridTrack& track = tracks[trackIndex];
821         track.setPlannedSize(trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity));
822     }
823
824     for (auto it = gridItemsWithSpan.rangeStart; it != gridItemsWithSpan.rangeEnd; ++it) {
825         GridItemWithSpan& gridItemWithSpan = *it;
826         ASSERT(gridItemWithSpan.span() > 1);
827         const GridCoordinate& coordinate = gridItemWithSpan.coordinate();
828         const GridSpan& itemSpan = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
829
830         sizingData.filteredTracks.shrink(0);
831         sizingData.growBeyondGrowthLimitsTracks.shrink(0);
832         LayoutUnit spanningTracksSize;
833         for (auto& trackPosition : itemSpan) {
834             const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition.toInt());
835             GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPosition.toInt()] : sizingData.rowTracks[trackPosition.toInt()];
836             spanningTracksSize += trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
837             if (!shouldProcessTrackForTrackSizeComputationPhase(phase, trackSize))
838                 continue;
839
840             sizingData.filteredTracks.append(&track);
841
842             if (trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(phase, trackSize))
843                 sizingData.growBeyondGrowthLimitsTracks.append(&track);
844         }
845
846         if (sizingData.filteredTracks.isEmpty())
847             continue;
848
849         LayoutUnit extraSpace = currentItemSizeForTrackSizeComputationPhase(phase, gridItemWithSpan.gridItem(), direction, sizingData.columnTracks) - spanningTracksSize;
850         extraSpace = std::max<LayoutUnit>(extraSpace, 0);
851         auto& tracksToGrowBeyondGrowthLimits = sizingData.growBeyondGrowthLimitsTracks.isEmpty() ? sizingData.filteredTracks : sizingData.growBeyondGrowthLimitsTracks;
852         distributeSpaceToTracks<phase>(sizingData.filteredTracks, &tracksToGrowBeyondGrowthLimits, extraSpace);
853     }
854
855     for (const auto& trackIndex : sizingData.contentSizedTracksIndex) {
856         GridTrack& track = tracks[trackIndex];
857         markAsInfinitelyGrowableForTrackSizeComputationPhase(phase, track);
858         updateTrackSizeForTrackSizeComputationPhase(phase, track);
859     }
860 }
861
862 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
863 {
864     // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
865     // (forall x: NOT x < x).
866     if (track1->infiniteGrowthPotential() && track2->infiniteGrowthPotential())
867         return false;
868
869     if (track1->infiniteGrowthPotential() || track2->infiniteGrowthPotential())
870         return track2->infiniteGrowthPotential();
871
872     return (track1->growthLimit() - track1->baseSize()) < (track2->growthLimit() - track2->baseSize());
873 }
874
875 template <RenderGrid::TrackSizeComputationPhase phase>
876 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, const Vector<GridTrack*>* growBeyondGrowthLimitsTracks, LayoutUnit& availableLogicalSpace)
877 {
878     ASSERT(availableLogicalSpace >= 0);
879
880     for (auto* track : tracks)
881         track->tempSize() = trackSizeForTrackSizeComputationPhase(phase, *track, ForbidInfinity);
882
883     if (availableLogicalSpace > 0) {
884         std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
885
886         unsigned tracksSize = tracks.size();
887         for (unsigned i = 0; i < tracksSize; ++i) {
888             GridTrack& track = *tracks[i];
889             const LayoutUnit& trackBreadth = trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
890             bool infiniteGrowthPotential = track.infiniteGrowthPotential();
891             LayoutUnit trackGrowthPotential = infiniteGrowthPotential ? track.growthLimit() : track.growthLimit() - trackBreadth;
892             // Let's avoid computing availableLogicalSpaceShare as much as possible as it's a hot spot in performance tests.
893             if (trackGrowthPotential > 0 || infiniteGrowthPotential) {
894                 LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
895                 LayoutUnit growthShare = infiniteGrowthPotential ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, trackGrowthPotential);
896                 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.");
897                 track.tempSize() += growthShare;
898                 availableLogicalSpace -= growthShare;
899             }
900         }
901     }
902
903     if (availableLogicalSpace > 0 && growBeyondGrowthLimitsTracks) {
904         unsigned tracksGrowingBeyondGrowthLimitsSize = growBeyondGrowthLimitsTracks->size();
905         for (unsigned i = 0; i < tracksGrowingBeyondGrowthLimitsSize; ++i) {
906             GridTrack* track = growBeyondGrowthLimitsTracks->at(i);
907             LayoutUnit growthShare = availableLogicalSpace / (tracksGrowingBeyondGrowthLimitsSize - i);
908             track->tempSize() += growthShare;
909             availableLogicalSpace -= growthShare;
910         }
911     }
912
913     for (auto* track : tracks)
914         track->setPlannedSize(track->plannedSize() == infinity ? track->tempSize() : std::max(track->plannedSize(), track->tempSize()));
915 }
916
917 #ifndef NDEBUG
918 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
919 {
920     for (unsigned i = 0; i < tracks.size(); ++i) {
921         const GridTrackSize& trackSize = gridTrackSize(direction, i);
922         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
923         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].baseSize())
924             return false;
925     }
926     return true;
927 }
928 #endif
929
930 void RenderGrid::ensureGridSize(unsigned maximumRowIndex, unsigned maximumColumnIndex)
931 {
932     const unsigned oldRowCount = gridRowCount();
933     if (maximumRowIndex >= oldRowCount) {
934         m_grid.grow(maximumRowIndex + 1);
935         for (unsigned row = oldRowCount; row < gridRowCount(); ++row)
936             m_grid[row].grow(gridColumnCount());
937     }
938
939     if (maximumColumnIndex >= gridColumnCount()) {
940         for (unsigned row = 0; row < gridRowCount(); ++row)
941             m_grid[row].grow(maximumColumnIndex + 1);
942     }
943 }
944
945 void RenderGrid::insertItemIntoGrid(RenderBox& child, const GridCoordinate& coordinate)
946 {
947     ensureGridSize(coordinate.rows.resolvedFinalPosition.toInt(), coordinate.columns.resolvedFinalPosition.toInt());
948
949     for (auto& row : coordinate.rows) {
950         for (auto& column : coordinate.columns)
951             m_grid[row.toInt()][column.toInt()].append(&child);
952     }
953     m_gridItemCoordinate.set(&child, coordinate);
954 }
955
956 void RenderGrid::placeItemsOnGrid()
957 {
958     ASSERT(!gridWasPopulated());
959     ASSERT(m_gridItemCoordinate.isEmpty());
960
961     populateExplicitGridAndOrderIterator();
962
963     Vector<RenderBox*> autoMajorAxisAutoGridItems;
964     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
965     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
966         auto unresolvedRowPositions = GridResolvedPosition::unresolvedSpanFromStyle(style(), *child, ForRows);
967         auto unresolvedColumnPositions = GridResolvedPosition::unresolvedSpanFromStyle(style(), *child, ForColumns);
968
969         if (unresolvedRowPositions.requiresAutoPlacement() || unresolvedColumnPositions.requiresAutoPlacement()) {
970
971             bool majorAxisDirectionIsForColumns = autoPlacementMajorAxisDirection() == ForColumns;
972             if ((majorAxisDirectionIsForColumns && unresolvedColumnPositions.requiresAutoPlacement())
973                 || (!majorAxisDirectionIsForColumns && unresolvedRowPositions.requiresAutoPlacement()))
974                 autoMajorAxisAutoGridItems.append(child);
975             else
976                 specifiedMajorAxisAutoGridItems.append(child);
977             continue;
978         }
979         GridSpan rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(unresolvedRowPositions, style());
980         GridSpan columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(unresolvedColumnPositions, style());
981         insertItemIntoGrid(*child, GridCoordinate(rowPositions, columnPositions));
982     }
983
984     ASSERT(gridRowCount() >= GridResolvedPosition::explicitGridRowCount(style()));
985     ASSERT(gridColumnCount() >= GridResolvedPosition::explicitGridColumnCount(style()));
986
987     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
988     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
989 }
990
991 void RenderGrid::populateExplicitGridAndOrderIterator()
992 {
993     OrderIteratorPopulator populator(m_orderIterator);
994     unsigned maximumRowIndex = std::max<unsigned>(1, GridResolvedPosition::explicitGridRowCount(style()));
995     unsigned maximumColumnIndex = std::max<unsigned>(1, GridResolvedPosition::explicitGridColumnCount(style()));
996
997     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
998         populator.collectChild(*child);
999
1000         auto unresolvedRowPositions = GridResolvedPosition::unresolvedSpanFromStyle(style(), *child, ForRows);
1001         if (!unresolvedRowPositions.requiresAutoPlacement()) {
1002             GridSpan rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(unresolvedRowPositions, style());
1003             maximumRowIndex = std::max(maximumRowIndex, rowPositions.resolvedFinalPosition.next().toInt());
1004         } else {
1005             // Grow the grid for items with a definite row span, getting the largest such span.
1006             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *child, ForRows, GridResolvedPosition(0));
1007             maximumRowIndex = std::max(maximumRowIndex, positions.resolvedFinalPosition.next().toInt());
1008         }
1009
1010         auto unresolvedColumnPositions = GridResolvedPosition::unresolvedSpanFromStyle(style(), *child, ForColumns);
1011         if (!unresolvedColumnPositions.requiresAutoPlacement()) {
1012             GridSpan columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(unresolvedColumnPositions, style());
1013             maximumColumnIndex = std::max(maximumColumnIndex, columnPositions.resolvedFinalPosition.next().toInt());
1014         } else {
1015             // Grow the grid for items with a definite column span, getting the largest such span.
1016             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *child, ForColumns, GridResolvedPosition(0));
1017             maximumColumnIndex = std::max(maximumColumnIndex, positions.resolvedFinalPosition.next().toInt());
1018         }
1019     }
1020
1021     m_grid.grow(maximumRowIndex);
1022     for (auto& column : m_grid)
1023         column.grow(maximumColumnIndex);
1024 }
1025
1026 std::unique_ptr<GridCoordinate> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox& gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
1027 {
1028     GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
1029     const unsigned endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount();
1030     GridSpan crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection));
1031     return std::make_unique<GridCoordinate>(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions);
1032 }
1033
1034 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
1035 {
1036     bool isForColumns = autoPlacementMajorAxisDirection() == ForColumns;
1037     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
1038
1039     // Mapping between the major axis tracks (rows or columns) and the last auto-placed item's position inserted on
1040     // that track. This is needed to implement "sparse" packing for items locked to a given track.
1041     // See http://dev.w3.org/csswg/css-grid/#auto-placement-algo
1042     HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> minorAxisCursors;
1043
1044     for (auto& autoGridItem : autoGridItems) {
1045         auto unresolvedMajorAxisPositions = GridResolvedPosition::unresolvedSpanFromStyle(style(), *autoGridItem, autoPlacementMajorAxisDirection());
1046         ASSERT(!unresolvedMajorAxisPositions.requiresAutoPlacement());
1047         GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(unresolvedMajorAxisPositions, style());
1048         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *autoGridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
1049         unsigned majorAxisInitialPosition = majorAxisPositions.resolvedInitialPosition.toInt();
1050
1051         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions.resolvedInitialPosition.toInt(), isGridAutoFlowDense ? 0 : minorAxisCursors.get(majorAxisInitialPosition));
1052         std::unique_ptr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan());
1053         if (!emptyGridArea)
1054             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(*autoGridItem, autoPlacementMajorAxisDirection(), majorAxisPositions);
1055         insertItemIntoGrid(*autoGridItem, *emptyGridArea);
1056
1057         if (!isGridAutoFlowDense)
1058             minorAxisCursors.set(majorAxisInitialPosition, isForColumns ? emptyGridArea->rows.resolvedInitialPosition.toInt() : emptyGridArea->columns.resolvedInitialPosition.toInt());
1059     }
1060 }
1061
1062 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
1063 {
1064     AutoPlacementCursor autoPlacementCursor = {0, 0};
1065     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
1066
1067     for (auto& autoGridItem : autoGridItems) {
1068         placeAutoMajorAxisItemOnGrid(*autoGridItem, autoPlacementCursor);
1069
1070         if (isGridAutoFlowDense) {
1071             autoPlacementCursor.first = 0;
1072             autoPlacementCursor.second = 0;
1073         }
1074     }
1075 }
1076
1077 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox& gridItem, AutoPlacementCursor& autoPlacementCursor)
1078 {
1079     ASSERT(GridResolvedPosition::unresolvedSpanFromStyle(style(), gridItem, autoPlacementMajorAxisDirection()).requiresAutoPlacement());
1080     GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(0));
1081
1082     const unsigned endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
1083     unsigned majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
1084     unsigned minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
1085
1086     std::unique_ptr<GridCoordinate> emptyGridArea;
1087     auto unresolvedMinorAxisPositions = GridResolvedPosition::unresolvedSpanFromStyle(style(), gridItem, autoPlacementMinorAxisDirection());
1088     if (!unresolvedMinorAxisPositions.requiresAutoPlacement()) {
1089         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(unresolvedMinorAxisPositions, style());
1090
1091         // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
1092         if (minorAxisPositions.resolvedInitialPosition.toInt() < minorAxisAutoPlacementCursor)
1093             majorAxisAutoPlacementCursor++;
1094
1095         if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
1096             GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions.resolvedInitialPosition.toInt(), majorAxisAutoPlacementCursor);
1097             emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions.integerSpan(), majorAxisPositions.integerSpan());
1098         }
1099
1100         if (!emptyGridArea)
1101             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
1102     } else {
1103         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
1104
1105         for (unsigned majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
1106             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
1107             emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan());
1108
1109             if (emptyGridArea) {
1110                 // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
1111                 GridResolvedPosition minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.resolvedFinalPosition : emptyGridArea->rows.resolvedFinalPosition;
1112                 const unsigned endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount();
1113                 if (minorAxisFinalPositionIndex.toInt() < endOfMinorAxis)
1114                     break;
1115
1116                 // Discard empty grid area as it does not fit in the minor axis direction.
1117                 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
1118                 emptyGridArea = nullptr;
1119             }
1120
1121             // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
1122             minorAxisAutoPlacementCursor = 0;
1123         }
1124
1125         if (!emptyGridArea)
1126             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
1127     }
1128
1129     insertItemIntoGrid(gridItem, *emptyGridArea);
1130     autoPlacementCursor.first = emptyGridArea->rows.resolvedInitialPosition.toInt();
1131     autoPlacementCursor.second = emptyGridArea->columns.resolvedInitialPosition.toInt();
1132 }
1133
1134 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
1135 {
1136     return style().isGridAutoFlowDirectionColumn() ? ForColumns : ForRows;
1137 }
1138
1139 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
1140 {
1141     return style().isGridAutoFlowDirectionColumn() ? ForRows : ForColumns;
1142 }
1143
1144 void RenderGrid::clearGrid()
1145 {
1146     m_grid.clear();
1147     m_gridItemCoordinate.clear();
1148 }
1149
1150 void RenderGrid::layoutGridItems()
1151 {
1152     placeItemsOnGrid();
1153
1154     GridSizingData sizingData(gridColumnCount(), gridRowCount());
1155     computeUsedBreadthOfGridTracks(ForColumns, sizingData);
1156     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
1157     computeUsedBreadthOfGridTracks(ForRows, sizingData);
1158     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
1159
1160     populateGridPositions(sizingData);
1161
1162     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1163         // Because the grid area cannot be styled, we don't need to adjust
1164         // the grid breadth to account for 'box-sizing'.
1165         Optional<LayoutUnit> oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
1166         Optional<LayoutUnit> oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
1167
1168         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(*child, ForColumns, sizingData.columnTracks);
1169         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(*child, ForRows, sizingData.rowTracks);
1170         if (!oldOverrideContainingBlockContentLogicalWidth || oldOverrideContainingBlockContentLogicalWidth.value() != overrideContainingBlockContentLogicalWidth
1171             || ((!oldOverrideContainingBlockContentLogicalHeight || oldOverrideContainingBlockContentLogicalHeight.value() != overrideContainingBlockContentLogicalHeight)
1172                 && child->hasRelativeLogicalHeight()))
1173             child->setNeedsLayout(MarkOnlyThis);
1174         else
1175             resetAutoMarginsAndLogicalTopInColumnAxis(*child);
1176
1177         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
1178         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
1179
1180         LayoutRect oldChildRect = child->frameRect();
1181
1182         // Stretching logic might force a child layout, so we need to run it before the layoutIfNeeded
1183         // call to avoid unnecessary relayouts. This might imply that child margins, needed to correctly
1184         // determine the available space before stretching, are not set yet.
1185         applyStretchAlignmentToChildIfNeeded(*child);
1186
1187         child->layoutIfNeeded();
1188
1189         // We need pending layouts to be done in order to compute auto-margins properly.
1190         updateAutoMarginsInColumnAxisIfNeeded(*child);
1191         updateAutoMarginsInRowAxisIfNeeded(*child);
1192
1193         child->setLogicalLocation(findChildLogicalPosition(*child));
1194
1195         // If the child moved, we have to repaint it as well as any floating/positioned
1196         // descendants. An exception is if we need a layout. In this case, we know we're going to
1197         // repaint ourselves (and the child) anyway.
1198         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
1199             child->repaintDuringLayoutIfMoved(oldChildRect);
1200     }
1201
1202     for (auto& row : sizingData.rowTracks)
1203         setLogicalHeight(logicalHeight() + row.baseSize());
1204
1205     // min / max logical height is handled in updateLogicalHeight().
1206     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
1207     if (hasLineIfEmpty()) {
1208         LayoutUnit minHeight = borderAndPaddingLogicalHeight()
1209             + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes)
1210             + scrollbarLogicalHeight();
1211         if (height() < minHeight)
1212             setLogicalHeight(minHeight);
1213     }
1214
1215     clearGrid();
1216 }
1217
1218 GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox& gridItem) const
1219 {
1220     ASSERT(m_gridItemCoordinate.contains(&gridItem));
1221     return m_gridItemCoordinate.get(&gridItem);
1222 }
1223
1224 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
1225 {
1226     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1227     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
1228     LayoutUnit gridAreaBreadth = 0;
1229     for (auto& trackPosition : span)
1230         gridAreaBreadth += tracks[trackPosition.toInt()].baseSize();
1231     return gridAreaBreadth;
1232 }
1233
1234 void RenderGrid::populateGridPositions(const GridSizingData& sizingData)
1235 {
1236     m_columnPositions.resizeToFit(sizingData.columnTracks.size() + 1);
1237     m_columnPositions[0] = borderAndPaddingStart();
1238     for (unsigned i = 0; i < m_columnPositions.size() - 1; ++i)
1239         m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].baseSize();
1240
1241     m_rowPositions.resizeToFit(sizingData.rowTracks.size() + 1);
1242     m_rowPositions[0] = borderAndPaddingBefore();
1243     for (unsigned i = 0; i < m_rowPositions.size() - 1; ++i)
1244         m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].baseSize();
1245 }
1246
1247 static inline LayoutUnit computeOverflowAlignmentOffset(OverflowAlignment overflow, LayoutUnit trackBreadth, LayoutUnit childBreadth)
1248 {
1249     LayoutUnit offset = trackBreadth - childBreadth;
1250     switch (overflow) {
1251     case OverflowAlignmentSafe:
1252         // If overflow is 'safe', we have to make sure we don't overflow the 'start'
1253         // edge (potentially cause some data loss as the overflow is unreachable).
1254         return std::max<LayoutUnit>(0, offset);
1255     case OverflowAlignmentTrue:
1256     case OverflowAlignmentDefault:
1257         // If we overflow our alignment container and overflow is 'true' (default), we
1258         // ignore the overflow and just return the value regardless (which may cause data
1259         // loss as we overflow the 'start' edge).
1260         return offset;
1261     }
1262
1263     ASSERT_NOT_REACHED();
1264     return 0;
1265 }
1266
1267 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1268 bool RenderGrid::needToStretchChildLogicalHeight(const RenderBox& child) const
1269 {
1270     if (RenderStyle::resolveAlignment(style(), child.style(), ItemPositionStretch) != ItemPositionStretch)
1271         return false;
1272
1273     return isHorizontalWritingMode() && child.style().height().isAuto();
1274 }
1275
1276 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1277 LayoutUnit RenderGrid::marginLogicalHeightForChild(const RenderBox& child) const
1278 {
1279     return isHorizontalWritingMode() ? child.verticalMarginExtent() : child.horizontalMarginExtent();
1280 }
1281
1282 LayoutUnit RenderGrid::availableAlignmentSpaceForChildBeforeStretching(LayoutUnit gridAreaBreadthForChild, const RenderBox& child) const
1283 {
1284     return gridAreaBreadthForChild - marginLogicalHeightForChild(child);
1285 }
1286
1287 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1288 void RenderGrid::applyStretchAlignmentToChildIfNeeded(RenderBox& child)
1289 {
1290     ASSERT(child.overrideContainingBlockContentLogicalWidth() && child.overrideContainingBlockContentLogicalHeight());
1291
1292     // We clear both width and height override values because we will decide now whether they
1293     // are allowed or not, evaluating the conditions which might have changed since the old
1294     // values were set.
1295     child.clearOverrideSize();
1296
1297     auto& gridStyle = style();
1298     auto& childStyle = child.style();
1299     bool isHorizontalMode = isHorizontalWritingMode();
1300     bool hasAutoSizeInRowAxis = isHorizontalMode ? childStyle.width().isAuto() : childStyle.height().isAuto();
1301     bool allowedToStretchChildAlongRowAxis = hasAutoSizeInRowAxis && !childStyle.marginStartUsing(&gridStyle).isAuto() && !childStyle.marginEndUsing(&gridStyle).isAuto();
1302     if (!allowedToStretchChildAlongRowAxis || RenderStyle::resolveJustification(gridStyle, childStyle, ItemPositionStretch) != ItemPositionStretch) {
1303         bool hasAutoMinSizeInRowAxis = isHorizontalMode ? childStyle.minWidth().isAuto() : childStyle.minHeight().isAuto();
1304         bool canShrinkToFitInRowAxisForChild = !hasAutoMinSizeInRowAxis || child.minPreferredLogicalWidth() <= child.overrideContainingBlockContentLogicalWidth().value();
1305         // TODO(lajava): how to handle orthogonality in this case ?.
1306         // TODO(lajava): grid track sizing and positioning do not support orthogonal modes yet.
1307         if (hasAutoSizeInRowAxis && canShrinkToFitInRowAxisForChild) {
1308             LayoutUnit childWidthToFitContent = std::max(std::min(child.maxPreferredLogicalWidth(), child.overrideContainingBlockContentLogicalWidth().value() - child.marginLogicalWidth()), child.minPreferredLogicalWidth());
1309             LayoutUnit desiredLogicalWidth = child.constrainLogicalHeightByMinMax(childWidthToFitContent, Nullopt);
1310             child.setOverrideLogicalContentWidth(desiredLogicalWidth - child.borderAndPaddingLogicalWidth());
1311             if (desiredLogicalWidth != child.logicalWidth())
1312                 child.setNeedsLayout();
1313         }
1314     }
1315
1316     bool hasAutoSizeInColumnAxis = isHorizontalMode ? childStyle.height().isAuto() : childStyle.width().isAuto();
1317     bool allowedToStretchChildAlongColumnAxis = hasAutoSizeInColumnAxis && !childStyle.marginBeforeUsing(&gridStyle).isAuto() && !childStyle.marginAfterUsing(&gridStyle).isAuto();
1318     if (allowedToStretchChildAlongColumnAxis && RenderStyle::resolveAlignment(gridStyle, childStyle, ItemPositionStretch) == ItemPositionStretch) {
1319         // TODO (lajava): If the child has orthogonal flow, then it already has an override height set, so use it.
1320         // TODO (lajava): grid track sizing and positioning do not support orthogonal modes yet.
1321         if (child.isHorizontalWritingMode() == isHorizontalMode) {
1322             LayoutUnit stretchedLogicalHeight = availableAlignmentSpaceForChildBeforeStretching(child.overrideContainingBlockContentLogicalHeight().value(), child);
1323             LayoutUnit desiredLogicalHeight = child.constrainLogicalHeightByMinMax(stretchedLogicalHeight, Nullopt);
1324             child.setOverrideLogicalContentHeight(desiredLogicalHeight - child.borderAndPaddingLogicalHeight());
1325             if (desiredLogicalHeight != child.logicalHeight()) {
1326                 // TODO (lajava): Can avoid laying out here in some cases. See https://webkit.org/b/87905.
1327                 child.setLogicalHeight(0);
1328                 child.setNeedsLayout();
1329             }
1330         }
1331     }
1332 }
1333
1334 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1335 bool RenderGrid::hasAutoMarginsInColumnAxis(const RenderBox& child) const
1336 {
1337     if (isHorizontalWritingMode())
1338         return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1339     return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1340 }
1341
1342 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1343 bool RenderGrid::hasAutoMarginsInRowAxis(const RenderBox& child) const
1344 {
1345     if (isHorizontalWritingMode())
1346         return child.style().marginLeft().isAuto() || child.style().marginRight().isAuto();
1347     return child.style().marginTop().isAuto() || child.style().marginBottom().isAuto();
1348 }
1349
1350 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1351 void RenderGrid::resetAutoMarginsAndLogicalTopInColumnAxis(RenderBox& child)
1352 {
1353     if (hasAutoMarginsInColumnAxis(child) || child.needsLayout()) {
1354         child.clearOverrideLogicalContentHeight();
1355         child.updateLogicalHeight();
1356         if (isHorizontalWritingMode()) {
1357             if (child.style().marginTop().isAuto())
1358                 child.setMarginTop(0);
1359             if (child.style().marginBottom().isAuto())
1360                 child.setMarginBottom(0);
1361         } else {
1362             if (child.style().marginLeft().isAuto())
1363                 child.setMarginLeft(0);
1364             if (child.style().marginRight().isAuto())
1365                 child.setMarginRight(0);
1366         }
1367
1368     }
1369 }
1370
1371 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1372 void RenderGrid::updateAutoMarginsInRowAxisIfNeeded(RenderBox& child)
1373 {
1374     ASSERT(!child.isOutOfFlowPositioned());
1375     ASSERT(child.overrideContainingBlockContentLogicalWidth());
1376
1377     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalWidth().value() - child.logicalWidth();
1378     if (availableAlignmentSpace <= 0)
1379         return;
1380
1381     bool isHorizontal = isHorizontalWritingMode();
1382     Length topOrLeft = isHorizontal ? child.style().marginLeft() : child.style().marginTop();
1383     Length bottomOrRight = isHorizontal ? child.style().marginRight() : child.style().marginBottom();
1384     if (topOrLeft.isAuto() && bottomOrRight.isAuto()) {
1385         if (isHorizontal) {
1386             child.setMarginLeft(availableAlignmentSpace / 2);
1387             child.setMarginRight(availableAlignmentSpace / 2);
1388         } else {
1389             child.setMarginTop(availableAlignmentSpace / 2);
1390             child.setMarginBottom(availableAlignmentSpace / 2);
1391         }
1392     } else if (topOrLeft.isAuto()) {
1393         if (isHorizontal)
1394             child.setMarginLeft(availableAlignmentSpace);
1395         else
1396             child.setMarginTop(availableAlignmentSpace);
1397     } else if (bottomOrRight.isAuto()) {
1398         if (isHorizontal)
1399             child.setMarginRight(availableAlignmentSpace);
1400         else
1401             child.setMarginBottom(availableAlignmentSpace);
1402     }
1403 }
1404
1405 // FIXME: This logic is shared by RenderFlexibleBox, so it should be moved to RenderBox.
1406 void RenderGrid::updateAutoMarginsInColumnAxisIfNeeded(RenderBox& child)
1407 {
1408     ASSERT(!child.isOutOfFlowPositioned());
1409     ASSERT(child.overrideContainingBlockContentLogicalHeight());
1410
1411     LayoutUnit availableAlignmentSpace = child.overrideContainingBlockContentLogicalHeight().value() - child.logicalHeight();
1412     if (availableAlignmentSpace <= 0)
1413         return;
1414
1415     bool isHorizontal = isHorizontalWritingMode();
1416     Length topOrLeft = isHorizontal ? child.style().marginTop() : child.style().marginLeft();
1417     Length bottomOrRight = isHorizontal ? child.style().marginBottom() : child.style().marginRight();
1418     if (topOrLeft.isAuto() && bottomOrRight.isAuto()) {
1419         if (isHorizontal) {
1420             child.setMarginTop(availableAlignmentSpace / 2);
1421             child.setMarginBottom(availableAlignmentSpace / 2);
1422         } else {
1423             child.setMarginLeft(availableAlignmentSpace / 2);
1424             child.setMarginRight(availableAlignmentSpace / 2);
1425         }
1426     } else if (topOrLeft.isAuto()) {
1427         if (isHorizontal)
1428             child.setMarginTop(availableAlignmentSpace);
1429         else
1430             child.setMarginLeft(availableAlignmentSpace);
1431     } else if (bottomOrRight.isAuto()) {
1432         if (isHorizontal)
1433             child.setMarginBottom(availableAlignmentSpace);
1434         else
1435             child.setMarginRight(availableAlignmentSpace);
1436     }
1437 }
1438
1439 GridAxisPosition RenderGrid::columnAxisPositionForChild(const RenderBox& child) const
1440 {
1441     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
1442     bool hasSameWritingMode = child.style().writingMode() == style().writingMode();
1443
1444     switch (RenderStyle::resolveAlignment(style(), child.style(), ItemPositionStretch)) {
1445     case ItemPositionSelfStart:
1446         // If orthogonal writing-modes, this computes to 'start'.
1447         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1448         // 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.
1449         return (hasOrthogonalWritingMode || hasSameWritingMode) ? GridAxisStart : GridAxisEnd;
1450     case ItemPositionSelfEnd:
1451         // If orthogonal writing-modes, this computes to 'end'.
1452         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1453         // 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.
1454         return (hasOrthogonalWritingMode || hasSameWritingMode) ? GridAxisEnd : GridAxisStart;
1455     case ItemPositionLeft:
1456         // The alignment axis (column axis) and the inline axis are parallell in
1457         // orthogonal writing mode. Otherwise this this is equivalent to 'start'.
1458         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1459         return GridAxisStart;
1460     case ItemPositionRight:
1461         // The alignment axis (column axis) and the inline axis are parallell in
1462         // orthogonal writing mode. Otherwise this this is equivalent to 'start'.
1463         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1464         return hasOrthogonalWritingMode ? GridAxisEnd : GridAxisStart;
1465     case ItemPositionCenter:
1466         return GridAxisCenter;
1467     case ItemPositionFlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
1468     case ItemPositionStart:
1469         return GridAxisStart;
1470     case ItemPositionFlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
1471     case ItemPositionEnd:
1472         return GridAxisEnd;
1473     case ItemPositionStretch:
1474         return GridAxisStart;
1475     case ItemPositionBaseline:
1476     case ItemPositionLastBaseline:
1477         // FIXME: Implement the previous values. For now, we always 'start' align the child.
1478         return GridAxisStart;
1479     case ItemPositionAuto:
1480         break;
1481     }
1482
1483     ASSERT_NOT_REACHED();
1484     return GridAxisStart;
1485 }
1486
1487 GridAxisPosition RenderGrid::rowAxisPositionForChild(const RenderBox& child) const
1488 {
1489     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
1490     bool hasSameDirection = child.style().direction() == style().direction();
1491     bool isLTR = style().isLeftToRightDirection();
1492
1493     switch (RenderStyle::resolveJustification(style(), child.style(), ItemPositionStretch)) {
1494     case ItemPositionSelfStart:
1495         // For orthogonal writing-modes, this computes to 'start'
1496         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1497         // self-start is based on the child's direction. That's why we need to check against the grid container's direction.
1498         return (hasOrthogonalWritingMode || hasSameDirection) ? GridAxisStart : GridAxisEnd;
1499     case ItemPositionSelfEnd:
1500         // For orthogonal writing-modes, this computes to 'start'
1501         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1502         return (hasOrthogonalWritingMode || hasSameDirection) ? GridAxisEnd : GridAxisStart;
1503     case ItemPositionLeft:
1504         return isLTR ? GridAxisStart : GridAxisEnd;
1505     case ItemPositionRight:
1506         return isLTR ? GridAxisEnd : GridAxisStart;
1507     case ItemPositionCenter:
1508         return GridAxisCenter;
1509     case ItemPositionFlexStart: // Only used in flex layout, otherwise equivalent to 'start'.
1510     case ItemPositionStart:
1511         return GridAxisStart;
1512     case ItemPositionFlexEnd: // Only used in flex layout, otherwise equivalent to 'end'.
1513     case ItemPositionEnd:
1514         return GridAxisEnd;
1515     case ItemPositionStretch:
1516         return GridAxisStart;
1517     case ItemPositionBaseline:
1518     case ItemPositionLastBaseline:
1519         // FIXME: Implement the previous values. For now, we always 'start' align the child.
1520         return GridAxisStart;
1521     case ItemPositionAuto:
1522         break;
1523     }
1524
1525     ASSERT_NOT_REACHED();
1526     return GridAxisStart;
1527 }
1528
1529 LayoutUnit RenderGrid::rowPositionForChild(const RenderBox& child) const
1530 {
1531     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1532     LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()];
1533     LayoutUnit startPosition = startOfRow + marginBeforeForChild(child);
1534     if (hasAutoMarginsInColumnAxis(child))
1535         return startPosition;
1536     GridAxisPosition axisPosition = columnAxisPositionForChild(child);
1537     switch (axisPosition) {
1538     case GridAxisStart:
1539         return startPosition;
1540     case GridAxisEnd:
1541     case GridAxisCenter: {
1542         LayoutUnit endOfRow = m_rowPositions[coordinate.rows.resolvedFinalPosition.next().toInt()];
1543         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(RenderStyle::resolveAlignmentOverflow(style(), child.style()), endOfRow - startOfRow, child.logicalHeight() + child.marginLogicalHeight());
1544         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
1545     }
1546     }
1547
1548     ASSERT_NOT_REACHED();
1549     return 0;
1550 }
1551
1552
1553 LayoutUnit RenderGrid::columnPositionForChild(const RenderBox& child) const
1554 {
1555     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1556     LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
1557     LayoutUnit startPosition = startOfColumn + marginStartForChild(child);
1558     if (hasAutoMarginsInRowAxis(child))
1559         return startPosition;
1560     GridAxisPosition axisPosition = rowAxisPositionForChild(child);
1561     switch (axisPosition) {
1562     case GridAxisStart:
1563         return startPosition;
1564     case GridAxisEnd:
1565     case GridAxisCenter: {
1566         LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()];
1567         LayoutUnit offsetFromStartPosition = computeOverflowAlignmentOffset(RenderStyle::resolveJustificationOverflow(style(), child.style()), endOfColumn - startOfColumn, child.logicalWidth() + child.marginLogicalWidth());
1568         return startPosition + (axisPosition == GridAxisEnd ? offsetFromStartPosition : offsetFromStartPosition / 2);
1569     }
1570     }
1571
1572     ASSERT_NOT_REACHED();
1573     return 0;
1574 }
1575
1576 LayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox& child) const
1577 {
1578     LayoutUnit columnPosition = columnPositionForChild(child);
1579     // We stored m_columnPositions's data ignoring the direction, hence we might need now
1580     // to translate positions from RTL to LTR, as it's more convenient for painting.
1581     if (!style().isLeftToRightDirection())
1582         columnPosition = (m_columnPositions[m_columnPositions.size() - 1] + borderAndPaddingLogicalLeft()) - columnPosition  - child.logicalWidth();
1583
1584     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1585     return LayoutPoint(columnPosition, rowPositionForChild(child));
1586 }
1587
1588 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset, PaintInfo& forChild, bool usePrintRect)
1589 {
1590     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next())
1591         paintChild(*child, paintInfo, paintOffset, forChild, usePrintRect, PaintAsInlineBlock);
1592 }
1593
1594 const char* RenderGrid::renderName() const
1595 {
1596     if (isFloating())
1597         return "RenderGrid (floating)";
1598     if (isOutOfFlowPositioned())
1599         return "RenderGrid (positioned)";
1600     if (isAnonymous())
1601         return "RenderGrid (generated)";
1602     if (isRelPositioned())
1603         return "RenderGrid (relative positioned)";
1604     return "RenderGrid";
1605 }
1606
1607 } // namespace WebCore
1608
1609 #endif /* ENABLE(CSS_GRID_LAYOUT) */