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