[CSS Grid layout] Initial position in span not correctly computed sometimes
[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 COMPUTER, 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 "LayoutRepainter.h"
34 #include "NotImplemented.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, size_t fixedTrackIndex)
93         : m_grid(grid)
94         , m_direction(direction)
95         , m_rowIndex((direction == ForColumns) ? 0 : fixedTrackIndex)
96         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : 0)
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         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
109         const size_t 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     PassOwnPtr<GridCoordinate> nextEmptyGridArea()
121     {
122         if (m_grid.isEmpty())
123             return nullptr;
124
125         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
126         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
127         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
128             const Vector<RenderBox*>& children = m_grid[m_rowIndex][m_columnIndex];
129             if (children.isEmpty()) {
130                 OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(GridSpan(m_rowIndex, m_rowIndex), GridSpan(m_columnIndex, m_columnIndex)));
131                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
132                 ++varyingTrackIndex;
133                 return result.release();
134             }
135         }
136         return nullptr;
137     }
138
139 private:
140     const Vector<Vector<Vector<RenderBox*, 1>>>& m_grid;
141     GridTrackSizingDirection m_direction;
142     size_t m_rowIndex;
143     size_t m_columnIndex;
144     size_t m_childIndex;
145 };
146
147 class RenderGrid::GridSizingData {
148     WTF_MAKE_NONCOPYABLE(GridSizingData);
149 public:
150     GridSizingData(size_t gridColumnCount, size_t gridRowCount)
151         : columnTracks(gridColumnCount)
152         , rowTracks(gridRowCount)
153     {
154     }
155
156     Vector<GridTrack> columnTracks;
157     Vector<GridTrack> rowTracks;
158     Vector<size_t> contentSizedTracksIndex;
159
160     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
161     Vector<LayoutUnit> distributeTrackVector;
162     Vector<GridTrack*> filteredTracks;
163 };
164
165 RenderGrid::RenderGrid(Element& element, PassRef<RenderStyle> style)
166     : RenderBlock(element, std::move(style), 0)
167     , m_orderIterator(*this)
168 {
169     // All of our children must be block level.
170     setChildrenInline(false);
171 }
172
173 RenderGrid::~RenderGrid()
174 {
175 }
176
177 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
178 {
179     ASSERT(needsLayout());
180
181     if (!relayoutChildren && simplifiedLayout())
182         return;
183
184     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
185     // It would be nice to refactor some of the duplicate code.
186     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
187     LayoutStateMaintainer statePusher(view(), *this, locationOffset(), hasTransform() || hasReflection() || style().isFlippedBlocksWritingMode());
188
189     prepareShapesAndPaginationBeforeBlockLayout(relayoutChildren);
190
191     LayoutSize previousSize = size();
192
193     setLogicalHeight(0);
194     updateLogicalWidth();
195
196     layoutGridItems();
197
198     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
199     updateLogicalHeight();
200
201     if (size() != previousSize)
202         relayoutChildren = true;
203
204     layoutPositionedObjects(relayoutChildren || isRoot());
205
206     updateShapesAfterBlockLayout();
207
208     computeOverflow(oldClientAfterEdge);
209     statePusher.pop();
210
211     updateLayerTransform();
212
213     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
214     // we overflow or not.
215     updateScrollInfoAfterLayout();
216
217     repainter.repaintAfterLayout();
218
219     clearNeedsLayout();
220 }
221
222 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
223 {
224     const_cast<RenderGrid*>(this)->placeItemsOnGrid();
225
226     GridSizingData sizingData(gridColumnCount(), gridRowCount());
227     LayoutUnit availableLogicalSpace = 0;
228     const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace);
229
230     for (size_t i = 0; i < sizingData.columnTracks.size(); ++i) {
231         LayoutUnit minTrackBreadth = sizingData.columnTracks[i].m_usedBreadth;
232         LayoutUnit maxTrackBreadth = sizingData.columnTracks[i].m_maxBreadth;
233         maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth);
234
235         minLogicalWidth += minTrackBreadth;
236         maxLogicalWidth += maxTrackBreadth;
237
238         // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
239     }
240
241     const_cast<RenderGrid*>(this)->clearGrid();
242 }
243
244 void RenderGrid::computePreferredLogicalWidths()
245 {
246     ASSERT(preferredLogicalWidthsDirty());
247
248     m_minPreferredLogicalWidth = 0;
249     m_maxPreferredLogicalWidth = 0;
250
251     // FIXME: We don't take our own logical width into account. Once we do, we need to make sure
252     // we apply (and test the interaction with) min-width / max-width.
253
254     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
255
256     LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
257     m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
258     m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
259
260     setPreferredLogicalWidthsDirty(false);
261 }
262
263 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData)
264 {
265     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
266     computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace);
267 }
268
269 bool RenderGrid::gridElementIsShrinkToFit()
270 {
271     return isFloatingOrOutOfFlowPositioned();
272 }
273
274 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
275 {
276     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
277     Vector<size_t> flexibleSizedTracksIndex;
278     sizingData.contentSizedTracksIndex.shrink(0);
279
280     // 1. Initialize per Grid track variables.
281     for (size_t i = 0; i < tracks.size(); ++i) {
282         GridTrack& track = tracks[i];
283         const GridTrackSize& trackSize = gridTrackSize(direction, i);
284         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
285         const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
286
287         track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth);
288         track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.m_usedBreadth);
289
290         track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth);
291
292         if (trackSize.isContentSized())
293             sizingData.contentSizedTracksIndex.append(i);
294         if (trackSize.maxTrackBreadth().isFlex())
295             flexibleSizedTracksIndex.append(i);
296     }
297
298     // 2. Resolve content-based TrackSizingFunctions.
299     if (!sizingData.contentSizedTracksIndex.isEmpty())
300         resolveContentBasedTrackSizingFunctions(direction, sizingData);
301
302     for (size_t i = 0; i < tracks.size(); ++i) {
303         ASSERT(tracks[i].m_maxBreadth != infinity);
304         availableLogicalSpace -= tracks[i].m_usedBreadth;
305     }
306
307     const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style().logicalHeight().isAuto() : gridElementIsShrinkToFit();
308
309     if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0)
310         return;
311
312     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until
313     // availableLogicalSpace (RemainingSpace in the specs) is exhausted.
314     const size_t tracksSize = tracks.size();
315     if (!hasUndefinedRemainingSpace) {
316         Vector<GridTrack*> tracksForDistribution(tracksSize);
317         for (size_t i = 0; i < tracksSize; ++i)
318             tracksForDistribution[i] = tracks.data() + i;
319
320         distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, sizingData, availableLogicalSpace);
321     } else {
322         for (size_t i = 0; i < tracksSize; ++i)
323             tracks[i].m_usedBreadth = tracks[i].m_maxBreadth;
324     }
325
326     if (flexibleSizedTracksIndex.isEmpty())
327         return;
328
329     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
330     double normalizedFractionBreadth = 0;
331     if (!hasUndefinedRemainingSpace)
332         normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, availableLogicalSpace);
333     else {
334         for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
335             const size_t trackIndex = flexibleSizedTracksIndex[i];
336             const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
337             normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].m_usedBreadth / trackSize.maxTrackBreadth().flex());
338         }
339
340         for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
341             GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
342             while (RenderBox* gridItem = iterator.nextGridItem()) {
343                 const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
344                 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
345
346                 // Do not include already processed items.
347                 if (i > 0 && span.initialPositionIndex <= flexibleSizedTracksIndex[i - 1])
348                     continue;
349
350                 double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(gridItem, direction, sizingData.columnTracks));
351                 normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
352             }
353         }
354     }
355
356     for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
357         const size_t trackIndex = flexibleSizedTracksIndex[i];
358         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
359
360         tracks[trackIndex].m_usedBreadth = std::max<LayoutUnit>(tracks[trackIndex].m_usedBreadth, normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
361     }
362 }
363
364 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
365 {
366     if (gridLength.isFlex())
367         return 0;
368
369     const Length& trackLength = gridLength.length();
370     ASSERT(!trackLength.isAuto());
371     if (trackLength.isSpecified())
372         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
373
374     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
375     return 0;
376 }
377
378 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const
379 {
380     if (gridLength.isFlex())
381         return usedBreadth;
382
383     const Length& trackLength = gridLength.length();
384     ASSERT(!trackLength.isAuto());
385     if (trackLength.isSpecified()) {
386         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
387         ASSERT(computedBreadth != infinity);
388         return computedBreadth;
389     }
390
391     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
392     return infinity;
393 }
394
395 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
396 {
397     ASSERT(trackLength.isSpecified());
398     return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style().logicalHeight()));
399 }
400
401 double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit availableLogicalSpace) const
402 {
403     // |availableLogicalSpace| already accounts for the used breadths so no need to remove it here.
404
405     Vector<GridTrackForNormalization> tracksForNormalization;
406     for (size_t i = tracksSpan.initialPositionIndex; i <= tracksSpan.finalPositionIndex; ++i) {
407         const GridTrackSize& trackSize = gridTrackSize(direction, i);
408         if (!trackSize.maxTrackBreadth().isFlex())
409             continue;
410
411         tracksForNormalization.append(GridTrackForNormalization(tracks[i], trackSize.maxTrackBreadth().flex()));
412     }
413
414     // The function is not called if we don't have <flex> grid tracks
415     ASSERT(!tracksForNormalization.isEmpty());
416
417     std::sort(tracksForNormalization.begin(), tracksForNormalization.end(),
418               [](const GridTrackForNormalization& track1, const GridTrackForNormalization& track2) {
419                   return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
420               });
421
422     // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
423     // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
424     // fit into availableLogicalSpaceIgnoringFractionTracks.
425     double accumulatedFractions = 0;
426     LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
427     LayoutUnit availableLogicalSpaceIgnoringFractionTracks = availableLogicalSpace;
428
429     for (size_t i = 0; i < tracksForNormalization.size(); ++i) {
430         const GridTrackForNormalization& track = tracksForNormalization[i];
431         if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
432             // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
433             // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
434             if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
435                 break;
436
437             fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
438         }
439
440         accumulatedFractions += track.m_flex;
441         // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
442         availableLogicalSpaceIgnoringFractionTracks += track.m_track->m_usedBreadth;
443     }
444
445     return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
446 }
447
448 const GridTrackSize& RenderGrid::gridTrackSize(GridTrackSizingDirection direction, size_t i) const
449 {
450     const Vector<GridTrackSize>& trackStyles = (direction == ForColumns) ? style().gridColumns() : style().gridRows();
451     if (i >= trackStyles.size())
452         return (direction == ForColumns) ? style().gridAutoColumns() : style().gridAutoRows();
453
454     const GridTrackSize& trackSize = trackStyles[i];
455     // If the logical width/height of the grid container is indefinite, percentage values are treated as <auto>.
456     if (trackSize.isPercentage()) {
457         Length logicalSize = direction == ForColumns ? style().logicalWidth() : style().logicalHeight();
458         if (logicalSize.isIntrinsicOrAuto()) {
459             static NeverDestroyed<GridTrackSize> autoTrackSize(Auto);
460             return autoTrackSize.get();
461         }
462     }
463
464     return trackSize;
465 }
466
467 size_t RenderGrid::explicitGridColumnCount() const
468 {
469     return style().gridColumns().size();
470 }
471
472 size_t RenderGrid::explicitGridRowCount() const
473 {
474     return style().gridRows().size();
475 }
476
477 size_t RenderGrid::explicitGridSizeForSide(GridPositionSide side) const
478 {
479     return (side == ColumnStartSide || side == ColumnEndSide) ? explicitGridColumnCount() : explicitGridRowCount();
480 }
481
482 LayoutUnit RenderGrid::logicalContentHeightForChild(RenderBox* child, Vector<GridTrack>& columnTracks)
483 {
484     LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
485     LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
486     if (child->style().logicalHeight().isPercent() || oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth)
487         child->setNeedsLayout(MarkOnlyThis);
488
489     child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
490     // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is
491     // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution).
492     child->setOverrideContainingBlockContentLogicalHeight(-1);
493     child->layoutIfNeeded();
494     return child->logicalHeight();
495 }
496
497 LayoutUnit RenderGrid::minContentForChild(RenderBox* child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
498 {
499     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
500     // FIXME: Properly support orthogonal writing mode.
501     if (hasOrthogonalWritingMode)
502         return 0;
503
504     if (direction == ForColumns) {
505         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
506         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
507         return child->minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(*child);
508     }
509
510     return logicalContentHeightForChild(child, columnTracks);
511 }
512
513 LayoutUnit RenderGrid::maxContentForChild(RenderBox* child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
514 {
515     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
516     // FIXME: Properly support orthogonal writing mode.
517     if (hasOrthogonalWritingMode)
518         return LayoutUnit();
519
520     if (direction == ForColumns) {
521         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
522         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
523         return child->maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(*child);
524     }
525
526     return logicalContentHeightForChild(child, columnTracks);
527 }
528
529 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData)
530 {
531     // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track.
532
533     for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
534         GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]);
535         while (RenderBox* gridItem = iterator.nextGridItem()) {
536             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
537             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
538             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
539             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
540         }
541
542         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[i] : sizingData.rowTracks[i];
543         if (track.m_maxBreadth == infinity)
544             track.m_maxBreadth = track.m_usedBreadth;
545     }
546 }
547
548 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, RenderBox* gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
549 {
550     const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
551     const size_t initialTrackIndex = (direction == ForColumns) ? coordinate.columns.initialPositionIndex : coordinate.rows.initialPositionIndex;
552     const size_t finalTrackIndex = (direction == ForColumns) ? coordinate.columns.finalPositionIndex : coordinate.rows.finalPositionIndex;
553
554     sizingData.filteredTracks.shrink(0);
555     for (size_t trackIndex = initialTrackIndex; trackIndex <= finalTrackIndex; ++trackIndex) {
556         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
557         if (!(trackSize.*filterFunction)())
558             continue;
559
560         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
561         sizingData.filteredTracks.append(&track);
562     }
563
564     if (sizingData.filteredTracks.isEmpty())
565         return;
566
567     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks);
568     for (size_t trackIndexForSpace = initialTrackIndex; trackIndexForSpace <= finalTrackIndex; ++trackIndexForSpace) {
569         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndexForSpace] : sizingData.rowTracks[trackIndexForSpace];
570         additionalBreadthSpace -= (track.*trackGetter)();
571     }
572
573     // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
574     distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.filteredTracks, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
575 }
576
577 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
578 {
579     return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
580 }
581
582 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
583 {
584     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
585
586     size_t tracksSize = tracks.size();
587     sizingData.distributeTrackVector.resize(tracksSize);
588
589     for (size_t i = 0; i < tracksSize; ++i) {
590         GridTrack& track = *tracks[i];
591         LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
592         LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
593         LayoutUnit growthShare = std::max(LayoutUnit(), std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth));
594         // We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function.
595         sizingData.distributeTrackVector[i] = trackBreadth + growthShare;
596         availableLogicalSpace -= growthShare;
597     }
598
599     if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) {
600         tracksSize = tracksForGrowthAboveMaxBreadth->size();
601         for (size_t i = 0; i < tracksSize; ++i) {
602             LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
603             sizingData.distributeTrackVector[i] += growthShare;
604             availableLogicalSpace -= growthShare;
605         }
606     }
607
608     for (size_t i = 0; i < tracksSize; ++i) {
609         LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
610         if (growth >= 0)
611             (tracks[i]->*trackGrowthFunction)(growth);
612     }
613 }
614
615 #ifndef NDEBUG
616 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
617 {
618     for (size_t i = 0; i < tracks.size(); ++i) {
619         const GridTrackSize& trackSize = gridTrackSize(direction, i);
620         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
621         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth)
622             return false;
623     }
624     return true;
625 }
626 #endif
627
628 void RenderGrid::growGrid(GridTrackSizingDirection direction)
629 {
630     if (direction == ForColumns) {
631         const size_t oldColumnSize = m_grid[0].size();
632         for (size_t row = 0; row < m_grid.size(); ++row)
633             m_grid[row].grow(oldColumnSize + 1);
634     } else {
635         const size_t oldRowSize = m_grid.size();
636         m_grid.grow(oldRowSize + 1);
637         m_grid[oldRowSize].grow(m_grid[0].size());
638     }
639 }
640
641 void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridCoordinate& coordinate)
642 {
643     for (size_t row = coordinate.rows.initialPositionIndex; row <= coordinate.rows.finalPositionIndex; ++row) {
644         for (size_t column = coordinate.columns.initialPositionIndex; column <= coordinate.columns.finalPositionIndex; ++column)
645             m_grid[row][column].append(child);
646     }
647     m_gridItemCoordinate.set(child, coordinate);
648 }
649
650 void RenderGrid::insertItemIntoGrid(RenderBox* child, size_t rowTrack, size_t columnTrack)
651 {
652     const GridSpan& rowSpan = resolveGridPositionsFromAutoPlacementPosition(child, ForRows, rowTrack);
653     const GridSpan& columnSpan = resolveGridPositionsFromAutoPlacementPosition(child, ForColumns, columnTrack);
654     insertItemIntoGrid(child, GridCoordinate(rowSpan, columnSpan));
655 }
656
657 void RenderGrid::placeItemsOnGrid()
658 {
659     ASSERT(!gridWasPopulated());
660     ASSERT(m_gridItemCoordinate.isEmpty());
661
662     populateExplicitGridAndOrderIterator();
663
664     Vector<RenderBox*> autoMajorAxisAutoGridItems;
665     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
666     GridAutoFlow autoFlow = style().gridAutoFlow();
667     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
668         // FIXME: We never re-resolve positions if the grid is grown during auto-placement which may lead auto / <integer>
669         // positions to not match the author's intent. The specification is unclear on what should be done in this case.
670         OwnPtr<GridSpan> rowPositions = resolveGridPositionsFromStyle(child, ForRows);
671         OwnPtr<GridSpan> columnPositions = resolveGridPositionsFromStyle(child, ForColumns);
672         if (!rowPositions || !columnPositions) {
673             GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get();
674             if (!majorAxisPositions)
675                 autoMajorAxisAutoGridItems.append(child);
676             else
677                 specifiedMajorAxisAutoGridItems.append(child);
678             continue;
679         }
680         insertItemIntoGrid(child, GridCoordinate(*rowPositions, *columnPositions));
681     }
682
683     ASSERT(gridRowCount() >= style().gridRows().size());
684     ASSERT(gridColumnCount() >= style().gridColumns().size());
685
686     if (autoFlow == AutoFlowNone) {
687         // If we did collect some grid items, they won't be placed thus never laid out.
688         ASSERT(!autoMajorAxisAutoGridItems.size());
689         ASSERT(!specifiedMajorAxisAutoGridItems.size());
690         return;
691     }
692
693     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
694     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
695 }
696
697 void RenderGrid::populateExplicitGridAndOrderIterator()
698 {
699     // FIXME: We should find a way to share OrderValues's initialization code with RenderFlexibleBox.
700     OrderIterator::OrderValues orderValues;
701     size_t maximumRowIndex = std::max<size_t>(1, explicitGridRowCount());
702     size_t maximumColumnIndex = std::max<size_t>(1, explicitGridColumnCount());
703
704     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
705         // Avoid growing the vector for the common-case default value of 0. This optimizes the most common case which is
706         // one or a few values with the default order 0
707         int order = child->style().order();
708         if (orderValues.isEmpty() || orderValues.last() != order)
709             orderValues.append(order);
710
711         // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
712         OwnPtr<GridSpan> rowPositions = resolveGridPositionsFromStyle(child, ForRows);
713         OwnPtr<GridSpan> columnPositions = resolveGridPositionsFromStyle(child, ForColumns);
714
715         // |positions| is 0 if we need to run the auto-placement algorithm. Our estimation ignores
716         // this case as the auto-placement algorithm will grow the grid as needed.
717         if (rowPositions)
718             maximumRowIndex = std::max(maximumRowIndex, rowPositions->finalPositionIndex + 1);
719         if (columnPositions)
720             maximumColumnIndex = std::max(maximumColumnIndex, columnPositions->finalPositionIndex + 1);
721     }
722
723     m_grid.grow(maximumRowIndex);
724     for (size_t i = 0; i < m_grid.size(); ++i)
725         m_grid[i].grow(maximumColumnIndex);
726
727     m_orderIterator.setOrderValues(std::move(orderValues));
728 }
729
730 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(Vector<RenderBox*> autoGridItems)
731 {
732     for (size_t i = 0; i < autoGridItems.size(); ++i) {
733         OwnPtr<GridSpan> majorAxisPositions = resolveGridPositionsFromStyle(autoGridItems[i], autoPlacementMajorAxisDirection());
734         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->initialPositionIndex);
735         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
736             insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
737             continue;
738         }
739
740         growGrid(autoPlacementMinorAxisDirection());
741         OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
742         ASSERT(emptyGridArea);
743         insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
744     }
745 }
746
747 void RenderGrid::placeAutoMajorAxisItemsOnGrid(Vector<RenderBox*> autoGridItems)
748 {
749     for (size_t i = 0; i < autoGridItems.size(); ++i)
750         placeAutoMajorAxisItemOnGrid(autoGridItems[i]);
751 }
752
753 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
754 {
755     OwnPtr<GridSpan> minorAxisPositions = resolveGridPositionsFromStyle(gridItem, autoPlacementMinorAxisDirection());
756     ASSERT(!resolveGridPositionsFromStyle(gridItem, autoPlacementMajorAxisDirection()));
757     size_t minorAxisIndex = 0;
758     if (minorAxisPositions) {
759         minorAxisIndex = minorAxisPositions->initialPositionIndex;
760         GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisIndex);
761         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
762             insertItemIntoGrid(gridItem, emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
763             return;
764         }
765     } else {
766         const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
767         for (size_t majorAxisIndex = 0; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
768             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex);
769             if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
770                 insertItemIntoGrid(gridItem, emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
771                 return;
772             }
773         }
774     }
775
776     // We didn't find an empty grid area so we need to create an extra major axis line and insert our gridItem in it.
777     const size_t columnIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? m_grid[0].size() : minorAxisIndex;
778     const size_t rowIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? minorAxisIndex : m_grid.size();
779     growGrid(autoPlacementMajorAxisDirection());
780     insertItemIntoGrid(gridItem, rowIndex, columnIndex);
781 }
782
783 RenderGrid::GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
784 {
785     GridAutoFlow flow = style().gridAutoFlow();
786     ASSERT(flow != AutoFlowNone);
787     return (flow == AutoFlowColumn) ? ForColumns : ForRows;
788 }
789
790 RenderGrid::GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
791 {
792     GridAutoFlow flow = style().gridAutoFlow();
793     ASSERT(flow != AutoFlowNone);
794     return (flow == AutoFlowColumn) ? ForRows : ForColumns;
795 }
796
797 void RenderGrid::clearGrid()
798 {
799     m_grid.clear();
800     m_gridItemCoordinate.clear();
801 }
802
803 void RenderGrid::layoutGridItems()
804 {
805     placeItemsOnGrid();
806
807     GridSizingData sizingData(gridColumnCount(), gridRowCount());
808     computeUsedBreadthOfGridTracks(ForColumns, sizingData);
809     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
810     computeUsedBreadthOfGridTracks(ForRows, sizingData);
811     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
812
813     populateGridPositions(sizingData);
814
815     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
816         // Because the grid area cannot be styled, we don't need to adjust
817         // the grid breadth to account for 'box-sizing'.
818         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
819         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
820
821         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, sizingData.columnTracks);
822         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(child, ForRows, sizingData.rowTracks);
823         if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && (child->hasRelativeLogicalHeight() || child->hasViewportPercentageLogicalHeight())))
824             child->setNeedsLayout(MarkOnlyThis);
825
826         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
827         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
828
829         LayoutRect oldChildRect = child->frameRect();
830
831         // FIXME: Grid items should stretch to fill their cells. Once we
832         // implement grid-{column,row}-align, we can also shrink to fit. For
833         // now, just size as if we were a regular child.
834         child->layoutIfNeeded();
835
836         child->setLogicalLocation(findChildLogicalPosition(child, sizingData));
837
838         // If the child moved, we have to repaint it as well as any floating/positioned
839         // descendants. An exception is if we need a layout. In this case, we know we're going to
840         // repaint ourselves (and the child) anyway.
841         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
842             child->repaintDuringLayoutIfMoved(oldChildRect);
843     }
844
845     for (size_t i = 0; i < sizingData.rowTracks.size(); ++i)
846         setLogicalHeight(logicalHeight() + sizingData.rowTracks[i].m_usedBreadth);
847
848     // FIXME: We should handle min / max logical height.
849
850     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
851     clearGrid();
852 }
853
854 GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox* gridItem) const
855 {
856     ASSERT(m_gridItemCoordinate.contains(gridItem));
857     return m_gridItemCoordinate.get(gridItem);
858 }
859
860 GridSpan RenderGrid::resolveGridPositionsFromAutoPlacementPosition(const RenderBox*, GridTrackSizingDirection, size_t initialPosition) const
861 {
862     // FIXME: We don't support spanning with auto positions yet. Once we do, this is wrong. Also we should make
863     // sure the grid can accomodate the new item as we only grow 1 position in a given direction.
864     return GridSpan(initialPosition, initialPosition);
865 }
866
867 PassOwnPtr<GridSpan> RenderGrid::resolveGridPositionsFromStyle(const RenderBox* gridItem, GridTrackSizingDirection direction) const
868 {
869     const GridPosition& initialPosition = (direction == ForColumns) ? gridItem->style().gridItemColumnStart() : gridItem->style().gridItemRowStart();
870     const GridPositionSide initialPositionSide = (direction == ForColumns) ? ColumnStartSide : RowStartSide;
871     const GridPosition& finalPosition = (direction == ForColumns) ? gridItem->style().gridItemColumnEnd() : gridItem->style().gridItemRowEnd();
872     const GridPositionSide finalPositionSide = (direction == ForColumns) ? ColumnEndSide : RowEndSide;
873
874     // We should NEVER see both spans as they should have been handled during style resolve.
875     ASSERT(!initialPosition.isSpan() || !finalPosition.isSpan());
876
877     if (initialPosition.shouldBeResolvedAgainstOppositePosition() && finalPosition.shouldBeResolvedAgainstOppositePosition()) {
878         if (style().gridAutoFlow() == AutoFlowNone)
879             return adoptPtr(new GridSpan(0, 0));
880
881         // We can't get our grid positions without running the auto placement algorithm.
882         return nullptr;
883     }
884
885     if (initialPosition.shouldBeResolvedAgainstOppositePosition()) {
886         // Infer the position from the final position ('auto / 1' or 'span 2 / 3' case).
887         const size_t finalResolvedPosition = resolveGridPositionFromStyle(finalPosition, finalPositionSide);
888         return resolveGridPositionAgainstOppositePosition(finalResolvedPosition, initialPosition, initialPositionSide);
889     }
890
891     if (finalPosition.shouldBeResolvedAgainstOppositePosition()) {
892         // Infer our position from the initial position ('1 / auto' or '3 / span 2' case).
893         const size_t initialResolvedPosition = resolveGridPositionFromStyle(initialPosition, initialPositionSide);
894         return resolveGridPositionAgainstOppositePosition(initialResolvedPosition, finalPosition, finalPositionSide);
895     }
896
897     size_t resolvedInitialPosition = resolveGridPositionFromStyle(initialPosition, initialPositionSide);
898     size_t resolvedFinalPosition = resolveGridPositionFromStyle(finalPosition, finalPositionSide);
899
900     // If 'grid-row-end' specifies a line at or before that specified by 'grid-row-start', it computes to 'span 1'.
901     if (resolvedFinalPosition < resolvedInitialPosition)
902         resolvedFinalPosition = resolvedInitialPosition;
903
904     return adoptPtr(new GridSpan(resolvedInitialPosition, resolvedFinalPosition));
905 }
906
907 size_t RenderGrid::resolveNamedGridLinePositionFromStyle(const GridPosition& position, GridPositionSide side) const
908 {
909     ASSERT(!position.namedGridLine().isNull());
910
911     const NamedGridLinesMap& gridLinesNames = (side == ColumnStartSide || side == ColumnEndSide) ? style().namedGridColumnLines() : style().namedGridRowLines();
912     NamedGridLinesMap::const_iterator it = gridLinesNames.find(position.namedGridLine());
913     if (it == gridLinesNames.end()) {
914         if (position.isPositive())
915             return 0;
916         const size_t lastLine = explicitGridSizeForSide(side);
917         return GridPosition::adjustGridPositionForSide(lastLine, side);
918     }
919
920     size_t namedGridLineIndex;
921     if (position.isPositive())
922         namedGridLineIndex = std::min<size_t>(position.integerPosition(), it->value.size()) - 1;
923     else
924         namedGridLineIndex = std::max<int>(it->value.size() - abs(position.integerPosition()), 0);
925     return GridPosition::adjustGridPositionForSide(it->value[namedGridLineIndex], side);
926 }
927
928 size_t RenderGrid::resolveGridPositionFromStyle(const GridPosition& position, GridPositionSide side) const
929 {
930     switch (position.type()) {
931     case ExplicitPosition: {
932         ASSERT(position.integerPosition());
933
934         if (!position.namedGridLine().isNull())
935             return resolveNamedGridLinePositionFromStyle(position, side);
936
937         // Handle <integer> explicit position.
938         if (position.isPositive())
939             return GridPosition::adjustGridPositionForSide(position.integerPosition() - 1, side);
940
941         size_t resolvedPosition = abs(position.integerPosition()) - 1;
942         const size_t endOfTrack = explicitGridSizeForSide(side);
943
944         // Per http://lists.w3.org/Archives/Public/www-style/2013Mar/0589.html, we clamp negative value to the first line.
945         if (endOfTrack < resolvedPosition)
946             return 0;
947
948         return GridPosition::adjustGridPositionForSide(endOfTrack - resolvedPosition, side);
949     }
950     case NamedGridAreaPosition:
951     {
952         NamedGridAreaMap::const_iterator it = style().namedGridArea().find(position.namedGridLine());
953         // Unknown grid area should have been computed to 'auto' by now.
954         ASSERT(it != style().namedGridArea().end());
955         const GridCoordinate& gridAreaCoordinate = it->value;
956         switch (side) {
957         case ColumnStartSide:
958             return gridAreaCoordinate.columns.initialPositionIndex;
959         case ColumnEndSide:
960             return gridAreaCoordinate.columns.finalPositionIndex;
961         case RowStartSide:
962             return gridAreaCoordinate.rows.initialPositionIndex;
963         case RowEndSide:
964             return gridAreaCoordinate.rows.finalPositionIndex;
965         }
966         ASSERT_NOT_REACHED();
967         return 0;
968     }
969     case AutoPosition:
970     case SpanPosition:
971         // 'auto' and span depend on the opposite position for resolution (e.g. grid-row: auto / 1 or grid-column: span 3 / "myHeader").
972         ASSERT_NOT_REACHED();
973         return 0;
974     }
975     ASSERT_NOT_REACHED();
976     return 0;
977 }
978
979 PassOwnPtr<GridSpan> RenderGrid::resolveGridPositionAgainstOppositePosition(size_t resolvedOppositePosition, const GridPosition& position, GridPositionSide side) const
980 {
981     if (position.isAuto())
982         return GridSpan::create(resolvedOppositePosition, resolvedOppositePosition);
983
984     ASSERT(position.isSpan());
985     ASSERT(position.spanPosition() > 0);
986
987     if (!position.namedGridLine().isNull()) {
988         // span 2 'c' -> we need to find the appropriate grid line before / after our opposite position.
989         return resolveNamedGridLinePositionAgainstOppositePosition(resolvedOppositePosition, position, side);
990     }
991
992     // 'span 1' is contained inside a single grid track regardless of the direction.
993     // That's why the CSS span value is one more than the offset we apply.
994     size_t positionOffset = position.spanPosition() - 1;
995     if (side == ColumnStartSide || side == RowStartSide) {
996         size_t initialResolvedPosition = std::max<int>(0, resolvedOppositePosition - positionOffset);
997         return GridSpan::create(initialResolvedPosition, resolvedOppositePosition);
998     }
999
1000     return GridSpan::create(resolvedOppositePosition, resolvedOppositePosition + positionOffset);
1001 }
1002
1003 PassOwnPtr<GridSpan> RenderGrid::resolveNamedGridLinePositionAgainstOppositePosition(size_t resolvedOppositePosition, const GridPosition& position, GridPositionSide side) const
1004 {
1005     ASSERT(position.isSpan());
1006     ASSERT(!position.namedGridLine().isNull());
1007     // Negative positions are not allowed per the specification and should have been handled during parsing.
1008     ASSERT(position.spanPosition() > 0);
1009
1010     const NamedGridLinesMap& gridLinesNames = (side == ColumnStartSide || side == ColumnEndSide) ? style().namedGridColumnLines() : style().namedGridRowLines();
1011     NamedGridLinesMap::const_iterator it = gridLinesNames.find(position.namedGridLine());
1012
1013     // If there is no named grid line of that name, we resolve the position to 'auto' (which is equivalent to 'span 1' in this case).
1014     // See http://lists.w3.org/Archives/Public/www-style/2013Jun/0394.html.
1015     if (it == gridLinesNames.end())
1016         return GridSpan::create(resolvedOppositePosition, resolvedOppositePosition);
1017
1018     if (side == RowStartSide || side == ColumnStartSide)
1019         return resolveRowStartColumnStartNamedGridLinePositionAgainstOppositePosition(resolvedOppositePosition, position, it->value);
1020
1021     return resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition(resolvedOppositePosition, position, it->value);
1022 }
1023
1024 static inline size_t firstNamedGridLineBeforePosition(size_t position, const Vector<size_t>& gridLines)
1025 {
1026     // The grid line inequality needs to be strict (which doesn't match the after / end case) because |position| is
1027     // already converted to an index in our grid representation (ie one was removed from the grid line to account for
1028     // the side).
1029     size_t firstLineBeforePositionIndex = 0;
1030     const size_t* firstLineBeforePosition = std::lower_bound(gridLines.begin(), gridLines.end(), position);
1031     if (firstLineBeforePosition != gridLines.end()) {
1032         if (*firstLineBeforePosition > position && firstLineBeforePosition != gridLines.begin())
1033             --firstLineBeforePosition;
1034
1035         firstLineBeforePositionIndex = firstLineBeforePosition - gridLines.begin();
1036     }
1037     return firstLineBeforePositionIndex;
1038 }
1039
1040 PassOwnPtr<GridSpan> RenderGrid::resolveRowStartColumnStartNamedGridLinePositionAgainstOppositePosition(size_t resolvedOppositePosition, const GridPosition& position, const Vector<size_t>& gridLines) const
1041 {
1042     size_t gridLineIndex = std::max<int>(0, firstNamedGridLineBeforePosition(resolvedOppositePosition, gridLines) - position.spanPosition() + 1);
1043     size_t resolvedGridLinePosition = gridLines[gridLineIndex];
1044     if (resolvedGridLinePosition > resolvedOppositePosition)
1045         resolvedGridLinePosition = resolvedOppositePosition;
1046     return GridSpan::create(resolvedGridLinePosition, resolvedOppositePosition);
1047 }
1048
1049 PassOwnPtr<GridSpan> RenderGrid::resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition(size_t resolvedOppositePosition, const GridPosition& position, const Vector<size_t>& gridLines) const
1050 {
1051     size_t firstLineAfterOppositePositionIndex = gridLines.size() - 1;
1052     const size_t* firstLineAfterOppositePosition = std::upper_bound(gridLines.begin(), gridLines.end(), resolvedOppositePosition);
1053     if (firstLineAfterOppositePosition != gridLines.end())
1054         firstLineAfterOppositePositionIndex = firstLineAfterOppositePosition - gridLines.begin();
1055
1056     size_t gridLineIndex = std::min(gridLines.size() - 1, firstLineAfterOppositePositionIndex + position.spanPosition() - 1);
1057     size_t resolvedGridLinePosition = GridPosition::adjustGridPositionForRowEndColumnEndSide(gridLines[gridLineIndex]);
1058     if (resolvedGridLinePosition < resolvedOppositePosition)
1059         resolvedGridLinePosition = resolvedOppositePosition;
1060     return GridSpan::create(resolvedOppositePosition, resolvedGridLinePosition);
1061 }
1062
1063 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox* child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
1064 {
1065     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1066     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
1067     LayoutUnit gridAreaBreadth = 0;
1068     for (size_t trackIndex = span.initialPositionIndex; trackIndex <= span.finalPositionIndex; ++trackIndex)
1069         gridAreaBreadth += tracks[trackIndex].m_usedBreadth;
1070     return gridAreaBreadth;
1071 }
1072
1073 void RenderGrid::populateGridPositions(const GridSizingData& sizingData)
1074 {
1075     m_columnPositions.resizeToFit(sizingData.columnTracks.size() + 1);
1076     m_columnPositions[0] = borderAndPaddingStart();
1077     for (size_t i = 0; i < m_columnPositions.size() - 1; ++i)
1078         m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].m_usedBreadth;
1079
1080     m_rowPositions.resizeToFit(sizingData.rowTracks.size() + 1);
1081     m_rowPositions[0] = borderAndPaddingBefore();
1082     for (size_t i = 0; i < m_rowPositions.size() - 1; ++i)
1083         m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].m_usedBreadth;
1084 }
1085
1086 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const GridSizingData& sizingData)
1087 {
1088     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1089     ASSERT_UNUSED(sizingData, coordinate.columns.initialPositionIndex < sizingData.columnTracks.size());
1090     ASSERT_UNUSED(sizingData, coordinate.rows.initialPositionIndex < sizingData.rowTracks.size());
1091
1092     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1093     return LayoutPoint(m_columnPositions[coordinate.columns.initialPositionIndex] + marginStartForChild(*child), m_rowPositions[coordinate.rows.initialPositionIndex] + marginBeforeForChild(*child));
1094 }
1095
1096 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset, PaintInfo& forChild, bool usePrintRect)
1097 {
1098     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next())
1099         paintChild(*child, paintInfo, paintOffset, forChild, usePrintRect);
1100 }
1101
1102 const char* RenderGrid::renderName() const
1103 {
1104     if (isFloating())
1105         return "RenderGrid (floating)";
1106     if (isOutOfFlowPositioned())
1107         return "RenderGrid (positioned)";
1108     if (isAnonymous())
1109         return "RenderGrid (generated)";
1110     if (isRelPositioned())
1111         return "RenderGrid (relative positioned)";
1112     return "RenderGrid";
1113 }
1114
1115 } // namespace WebCore
1116
1117 #endif /* ENABLE(CSS_GRID_LAYOUT) */