Unreviewed, rolling out r143941.
[WebKit-https.git] / Source / WebCore / rendering / RenderGrid.cpp
1 /*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "RenderGrid.h"
28
29 #include "LayoutRepainter.h"
30 #include "NotImplemented.h"
31 #include "RenderLayer.h"
32 #include "RenderView.h"
33
34 namespace WebCore {
35
36 static const int infinity = intMaxForLayoutUnit;
37
38 class GridTrack {
39 public:
40     GridTrack()
41         : m_usedBreadth(0)
42         , m_maxBreadth(0)
43     {
44     }
45
46     void growUsedBreadth(LayoutUnit growth)
47     {
48         ASSERT(growth >= 0);
49         m_usedBreadth += growth;
50     }
51     LayoutUnit usedBreadth() const { return m_usedBreadth; }
52
53     void growMaxBreadth(LayoutUnit growth)
54     {
55         if (m_maxBreadth == infinity)
56             m_maxBreadth = m_usedBreadth + growth;
57         else
58             m_maxBreadth += growth;
59     }
60     LayoutUnit maxBreadthIfNotInfinite() const
61     {
62         return (m_maxBreadth == infinity) ? m_usedBreadth : m_maxBreadth;
63     }
64
65     LayoutUnit m_usedBreadth;
66     LayoutUnit m_maxBreadth;
67 };
68
69 class RenderGrid::GridIterator {
70     WTF_MAKE_NONCOPYABLE(GridIterator);
71 public:
72     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
73     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
74     GridIterator(const Vector<Vector<Vector<RenderBox*, 1> > >& grid, TrackSizingDirection direction, size_t fixedTrackIndex)
75         : m_grid(grid)
76         , m_direction(direction)
77         , m_rowIndex((direction == ForColumns) ? 0 : fixedTrackIndex)
78         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : 0)
79         , m_childIndex(0)
80     {
81     }
82
83     RenderBox* nextGridItem()
84     {
85         if (!m_grid.size())
86             return 0;
87
88         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
89         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
90         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
91             const Vector<RenderBox*>& children = m_grid[m_rowIndex][m_columnIndex];
92             if (m_childIndex < children.size())
93                 return children[m_childIndex++];
94
95             m_childIndex = 0;
96         }
97         return 0;
98     }
99
100     PassOwnPtr<GridCoordinate> nextEmptyGridArea()
101     {
102         if (m_grid.isEmpty())
103             return nullptr;
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 (children.isEmpty()) {
110                 PassOwnPtr<GridCoordinate> result =  adoptPtr(new GridCoordinate(m_rowIndex, m_columnIndex));
111                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
112                 ++varyingTrackIndex;
113                 return result;
114             }
115         }
116         return nullptr;
117     }
118
119 private:
120     const Vector<Vector<Vector<RenderBox*, 1> > >& m_grid;
121     TrackSizingDirection m_direction;
122     size_t m_rowIndex;
123     size_t m_columnIndex;
124     size_t m_childIndex;
125 };
126
127 RenderGrid::RenderGrid(Element* element)
128     : RenderBlock(element)
129 {
130     // All of our children must be block level.
131     setChildrenInline(false);
132 }
133
134 RenderGrid::~RenderGrid()
135 {
136 }
137
138 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
139 {
140     ASSERT(needsLayout());
141
142     if (!relayoutChildren && simplifiedLayout())
143         return;
144
145     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
146     // It would be nice to refactor some of the duplicate code.
147     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
148     LayoutStateMaintainer statePusher(view(), this, locationOffset(), hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
149
150     if (inRenderFlowThread()) {
151         // Regions changing widths can force us to relayout our children.
152         if (logicalWidthChangedInRegions())
153             relayoutChildren = true;
154     }
155     updateRegionsAndExclusionsLogicalSize();
156
157     LayoutSize previousSize = size();
158
159     setLogicalHeight(0);
160     updateLogicalWidth();
161
162     layoutGridItems();
163
164     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
165     updateLogicalHeight();
166
167     if (size() != previousSize)
168         relayoutChildren = true;
169
170     layoutPositionedObjects(relayoutChildren || isRoot());
171
172     computeRegionRangeForBlock();
173
174     computeOverflow(oldClientAfterEdge);
175     statePusher.pop();
176
177     updateLayerTransform();
178
179     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
180     // we overflow or not.
181     if (hasOverflowClip())
182         layer()->updateScrollInfoAfterLayout();
183
184     repainter.repaintAfterLayout();
185
186     setNeedsLayout(false);
187 }
188
189 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
190 {
191     const_cast<RenderGrid*>(this)->placeItemsOnGrid();
192
193     const Vector<GridTrackSize>& trackStyles = style()->gridColumns();
194     for (size_t i = 0; i < trackStyles.size(); ++i) {
195         LayoutUnit minTrackBreadth = computePreferredTrackWidth(trackStyles[i].minTrackBreadth(), i);
196         LayoutUnit maxTrackBreadth = computePreferredTrackWidth(trackStyles[i].maxTrackBreadth(), i);
197         maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth);
198
199         minLogicalWidth += minTrackBreadth;
200         maxLogicalWidth += maxTrackBreadth;
201
202         // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
203     }
204
205     const_cast<RenderGrid*>(this)->clearGrid();
206 }
207
208 void RenderGrid::computePreferredLogicalWidths()
209 {
210     ASSERT(preferredLogicalWidthsDirty());
211
212     m_minPreferredLogicalWidth = 0;
213     m_maxPreferredLogicalWidth = 0;
214
215     // FIXME: We don't take our own logical width into account.
216     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
217     // FIXME: We should account for min / max logical width.
218
219     LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
220     m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
221     m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
222
223     setPreferredLogicalWidthsDirty(false);
224 }
225
226 LayoutUnit RenderGrid::computePreferredTrackWidth(const Length& length, size_t trackIndex) const
227 {
228     if (length.isFixed()) {
229         // Grid areas don't have borders, margins or paddings so we don't need to account for them.
230         return length.intValue();
231     }
232
233     if (length.isMinContent()) {
234         LayoutUnit minContentSize = 0;
235         GridIterator iterator(m_grid, ForColumns, trackIndex);
236         while (RenderBox* gridItem = iterator.nextGridItem()) {
237             // FIXME: We should include the child's fixed margins like RenderFlexibleBox.
238             minContentSize = std::max(minContentSize, gridItem->minPreferredLogicalWidth());
239         }
240         return minContentSize;
241     }
242
243     if (length.isMaxContent()) {
244         LayoutUnit maxContentSize = 0;
245         GridIterator iterator(m_grid, ForColumns, trackIndex);
246         while (RenderBox* gridItem = iterator.nextGridItem()) {
247             // FIXME: We should include the child's fixed margins like RenderFlexibleBox.
248             maxContentSize = std::max(maxContentSize, gridItem->maxPreferredLogicalWidth());
249         }
250         return maxContentSize;
251     }
252
253     // FIXME: css3-sizing mentions that we should resolve "definite sizes"
254     // (including <percentage> and calc()) but we don't do it elsewhere.
255     return 0;
256 }
257
258 void RenderGrid::computedUsedBreadthOfGridTracks(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks)
259 {
260     const Vector<GridTrackSize>& trackStyles = (direction == ForColumns) ? style()->gridColumns() : style()->gridRows();
261     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
262     Vector<GridTrack>& tracks = (direction == ForColumns) ? columnTracks : rowTracks;
263     for (size_t i = 0; i < trackStyles.size(); ++i) {
264         GridTrack& track = tracks[i];
265         const Length& minTrackBreadth = trackStyles[i].minTrackBreadth();
266         const Length& maxTrackBreadth = trackStyles[i].maxTrackBreadth();
267
268         track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth);
269         track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth);
270
271         track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth);
272
273         availableLogicalSpace -= track.m_usedBreadth;
274     }
275
276     // FIXME: We shouldn't call resolveContentBasedTrackSizingFunctions if we have no min-content / max-content tracks.
277     resolveContentBasedTrackSizingFunctions(direction, columnTracks, rowTracks, availableLogicalSpace);
278
279     if (availableLogicalSpace <= 0)
280         return;
281
282     const size_t tracksSize = tracks.size();
283     Vector<GridTrack*> tracksForDistribution(tracksSize);
284     for (size_t i = 0; i < tracksSize; ++i)
285         tracksForDistribution[i] = tracks.data() + i;
286
287     distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, availableLogicalSpace);
288 }
289
290 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(TrackSizingDirection direction, const Length& trackLength) const
291 {
292     if (trackLength.isFixed() || trackLength.isPercent() || trackLength.isViewportPercentage())
293         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
294
295     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent() || trackLength.isAuto());
296     return 0;
297 }
298
299 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(TrackSizingDirection direction, const Length& trackLength) const
300 {
301     if (trackLength.isFixed() || trackLength.isPercent() || trackLength.isViewportPercentage()) {
302         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
303         // FIXME: We should ASSERT that computedBreadth cannot return infinity but it's currently
304         // possible. See https://bugs.webkit.org/show_bug.cgi?id=107053
305         return computedBreadth;
306     }
307
308     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent() || trackLength.isAuto());
309     return infinity;
310 }
311
312 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(TrackSizingDirection direction, const Length& trackLength) const
313 {
314     // FIXME: We still need to support calc() here (https://webkit.org/b/103761).
315     ASSERT(trackLength.isFixed() || trackLength.isPercent() || trackLength.isViewportPercentage());
316     return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(MainOrPreferredSize, style()->logicalHeight()), view());
317 }
318
319 const GridTrackSize& RenderGrid::gridTrackSize(TrackSizingDirection direction, size_t i)
320 {
321     const Vector<GridTrackSize>& trackStyles = (direction == ForColumns) ? style()->gridColumns() : style()->gridRows();
322     if (i >= trackStyles.size()) {
323         // FIXME: This should match the default grid sizing (https://webkit.org/b/103333)
324         DEFINE_STATIC_LOCAL(GridTrackSize, defaultAutoSize, (Auto));
325         return defaultAutoSize;
326     }
327     return trackStyles[i];
328 }
329
330 size_t RenderGrid::maximumIndexInDirection(TrackSizingDirection direction) const
331 {
332     const Vector<GridTrackSize>& trackStyles = (direction == ForColumns) ? style()->gridColumns() : style()->gridRows();
333
334     size_t maximumIndex = std::max<size_t>(1, trackStyles.size());
335
336     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
337         const GridPosition& position = (direction == ForColumns) ? child->style()->gridItemColumn() : child->style()->gridItemRow();
338         // 'auto' items will need to be resolved in seperate phases anyway. Note that because maximumIndex is at least 1,
339         // the grid-auto-flow == none case is automatically handled.
340         if (position.isAuto())
341             continue;
342
343         // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
344         maximumIndex = std::max(maximumIndex, resolveGridPositionFromStyle(position) + 1);
345     }
346
347     return maximumIndex;
348 }
349
350 LayoutUnit RenderGrid::logicalContentHeightForChild(RenderBox* child, Vector<GridTrack>& columnTracks)
351 {
352     // FIXME: We shouldn't force a layout every time this function is called but
353     // 1) Return computeLogicalHeight's value if it's available. Unfortunately computeLogicalHeight
354     // doesn't return if the logical height is available so would need to be changed.
355     // 2) Relayout if the column track's used breadth changed OR the logical height is unavailable.
356     if (!child->needsLayout())
357         child->setNeedsLayout(true, MarkOnlyThis);
358
359     const GridCoordinate& coordinate = cachedGridCoordinate(child);
360     child->setOverrideContainingBlockContentLogicalWidth(columnTracks[coordinate.columnIndex].m_usedBreadth);
361     child->clearOverrideContainingBlockContentLogicalHeight();
362     child->layout();
363     return child->logicalHeight();
364 }
365
366 LayoutUnit RenderGrid::minContentForChild(RenderBox* child, TrackSizingDirection direction, Vector<GridTrack>& columnTracks)
367 {
368     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
369     // FIXME: Properly support orthogonal writing mode.
370     if (hasOrthogonalWritingMode)
371         return 0;
372
373     if (direction == ForColumns) {
374         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
375         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
376         return child->minPreferredLogicalWidth();
377     }
378
379     return logicalContentHeightForChild(child, columnTracks);
380 }
381
382 LayoutUnit RenderGrid::maxContentForChild(RenderBox* child, TrackSizingDirection direction, Vector<GridTrack>& columnTracks)
383 {
384     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
385     // FIXME: Properly support orthogonal writing mode.
386     if (hasOrthogonalWritingMode)
387         return LayoutUnit();
388
389     if (direction == ForColumns) {
390         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
391         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
392         return child->maxPreferredLogicalWidth();
393     }
394
395     return logicalContentHeightForChild(child, columnTracks);
396 }
397
398 void RenderGrid::resolveContentBasedTrackSizingFunctions(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, LayoutUnit& availableLogicalSpace)
399 {
400     // FIXME: Split the grid tracks once we support spanning or fractions (step 1 and 2 of the algorithm).
401
402     Vector<GridTrack>& tracks = (direction == ForColumns) ? columnTracks : rowTracks;
403
404     for (size_t i = 0; i < tracks.size(); ++i) {
405         const GridTrackSize& trackSize = gridTrackSize(direction, i);
406         GridTrack& track = tracks[i];
407         const Length& minTrackBreadth = trackSize.minTrackBreadth();
408         if (minTrackBreadth.isMinContent() || minTrackBreadth.isMaxContent()) {
409             LayoutUnit oldUsedBreadth = track.m_usedBreadth;
410             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, i, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
411             availableLogicalSpace -= (track.m_usedBreadth - oldUsedBreadth);
412         }
413
414         if (minTrackBreadth.isMaxContent()) {
415             LayoutUnit oldUsedBreadth = track.m_usedBreadth;
416             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, i, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
417             availableLogicalSpace -= (track.m_usedBreadth - oldUsedBreadth);
418         }
419
420         const Length& maxTrackBreadth = trackSize.maxTrackBreadth();
421         if (maxTrackBreadth.isMinContent() || maxTrackBreadth.isMaxContent())
422             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, i, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
423
424         if (maxTrackBreadth.isMaxContent())
425             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, i, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
426
427         if (track.m_maxBreadth == infinity)
428             track.m_maxBreadth = track.m_usedBreadth;
429     }
430 }
431
432 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, size_t trackIndex, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
433 {
434     GridTrack& track = (direction == ForColumns) ? columnTracks[trackIndex] : rowTracks[trackIndex];
435     GridIterator iterator(m_grid, direction, trackIndex);
436     while (RenderBox* gridItem = iterator.nextGridItem()) {
437         LayoutUnit contentSize = (this->*sizingFunction)(gridItem, direction, columnTracks);
438         LayoutUnit additionalBreadthSpace = contentSize - (track.*trackGetter)();
439         Vector<GridTrack*> tracks;
440         tracks.append(&track);
441         // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
442         distributeSpaceToTracks(tracks, &tracks, trackGetter, trackGrowthFunction, additionalBreadthSpace);
443     }
444 }
445
446 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
447 {
448     return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
449 }
450
451 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, LayoutUnit& availableLogicalSpace)
452 {
453     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
454
455     size_t tracksSize = tracks.size();
456     Vector<LayoutUnit> updatedTrackBreadths(tracksSize);
457
458     for (size_t i = 0; i < tracksSize; ++i) {
459         GridTrack& track = *tracks[i];
460         LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
461         LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
462         LayoutUnit growthShare = std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth);
463         updatedTrackBreadths[i] = trackBreadth + growthShare;
464         availableLogicalSpace -= growthShare;
465     }
466
467     if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) {
468         tracksSize = tracksForGrowthAboveMaxBreadth->size();
469         for (size_t i = 0; i < tracksSize; ++i) {
470             LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
471             updatedTrackBreadths[i] += growthShare;
472             availableLogicalSpace -= growthShare;
473         }
474     }
475
476     for (size_t i = 0; i < tracksSize; ++i) {
477         LayoutUnit growth = updatedTrackBreadths[i] - (tracks[i]->*trackGetter)();
478         if (growth >= 0)
479             (tracks[i]->*trackGrowthFunction)(growth);
480     }
481 }
482
483 #ifndef NDEBUG
484 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(TrackSizingDirection direction, const Vector<GridTrack>& tracks)
485 {
486     for (size_t i = 0; i < tracks.size(); ++i) {
487         const GridTrackSize& trackSize = gridTrackSize(direction, i);
488         const Length& minTrackBreadth = trackSize.minTrackBreadth();
489         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth)
490             return false;
491     }
492     return true;
493 }
494 #endif
495
496 void RenderGrid::growGrid(TrackSizingDirection direction)
497 {
498     if (direction == ForColumns) {
499         const size_t oldColumnSize = m_grid[0].size();
500         for (size_t row = 0; row < m_grid.size(); ++row)
501             m_grid[row].grow(oldColumnSize + 1);
502     } else {
503         const size_t oldRowSize = m_grid.size();
504         m_grid.grow(oldRowSize + 1);
505         m_grid[oldRowSize].grow(m_grid[0].size());
506     }
507 }
508
509 void RenderGrid::insertItemIntoGrid(RenderBox* child, size_t rowTrack, size_t columnTrack)
510 {
511     m_grid[rowTrack][columnTrack].append(child);
512     m_gridItemCoordinate.set(child, GridCoordinate(rowTrack, columnTrack));
513 }
514
515 void RenderGrid::placeItemsOnGrid()
516 {
517     ASSERT(!gridWasPopulated());
518     ASSERT(m_gridItemCoordinate.isEmpty());
519
520     m_grid.grow(maximumIndexInDirection(ForRows));
521     size_t maximumColumnIndex = maximumIndexInDirection(ForColumns);
522     for (size_t i = 0; i < m_grid.size(); ++i)
523         m_grid[i].grow(maximumColumnIndex);
524
525     Vector<RenderBox*> autoMajorAxisAutoGridItems;
526     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
527     GridAutoFlow autoFlow = style()->gridAutoFlow();
528     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
529         const GridPosition& columnPosition = child->style()->gridItemColumn();
530         const GridPosition& rowPosition = child->style()->gridItemRow();
531         if (autoFlow != AutoFlowNone && (columnPosition.isAuto() || rowPosition.isAuto())) {
532             const GridPosition& majorAxisPosition = autoPlacementMajorAxisPositionForChild(child);
533             if (majorAxisPosition.isAuto())
534                 autoMajorAxisAutoGridItems.append(child);
535             else
536                 specifiedMajorAxisAutoGridItems.append(child);
537             continue;
538         }
539         size_t columnTrack = resolveGridPositionFromStyle(columnPosition);
540         size_t rowTrack = resolveGridPositionFromStyle(rowPosition);
541         insertItemIntoGrid(child, rowTrack, columnTrack);
542     }
543
544     ASSERT(gridRowCount() >= style()->gridRows().size());
545     ASSERT(gridColumnCount() >= style()->gridColumns().size());
546
547     if (autoFlow == AutoFlowNone) {
548         // If we did collect some grid items, they won't be placed thus never laid out.
549         ASSERT(!autoMajorAxisAutoGridItems.size());
550         ASSERT(!specifiedMajorAxisAutoGridItems.size());
551         return;
552     }
553
554     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
555     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
556 }
557
558 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(Vector<RenderBox*> autoGridItems)
559 {
560     for (size_t i = 0; i < autoGridItems.size(); ++i) {
561         const GridPosition& majorAxisPosition = autoPlacementMajorAxisPositionForChild(autoGridItems[i]);
562         ASSERT(!majorAxisPosition.isAuto());
563         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), resolveGridPositionFromStyle(majorAxisPosition));
564         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
565             insertItemIntoGrid(autoGridItems[i], emptyGridArea->rowIndex, emptyGridArea->columnIndex);
566             continue;
567         }
568
569         growGrid(autoPlacementMinorAxisDirection());
570         OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
571         ASSERT(emptyGridArea);
572         insertItemIntoGrid(autoGridItems[i], emptyGridArea->rowIndex, emptyGridArea->columnIndex);
573     }
574 }
575
576 void RenderGrid::placeAutoMajorAxisItemsOnGrid(Vector<RenderBox*> autoGridItems)
577 {
578     for (size_t i = 0; i < autoGridItems.size(); ++i) {
579         ASSERT(autoPlacementMajorAxisPositionForChild(autoGridItems[i]).isAuto());
580         placeAutoMajorAxisItemOnGrid(autoGridItems[i]);
581     }
582 }
583
584 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
585 {
586     ASSERT(autoPlacementMajorAxisPositionForChild(gridItem).isAuto());
587     const GridPosition& minorAxisPosition = autoPlacementMinorAxisPositionForChild(gridItem);
588     size_t minorAxisIndex = 0;
589     if (!minorAxisPosition.isAuto()) {
590         minorAxisIndex = resolveGridPositionFromStyle(minorAxisPosition);
591         GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisIndex);
592         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
593             insertItemIntoGrid(gridItem, emptyGridArea->rowIndex, emptyGridArea->columnIndex);
594             return;
595         }
596     } else {
597         const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
598         for (size_t majorAxisIndex = 0; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
599             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex);
600             if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
601                 insertItemIntoGrid(gridItem, emptyGridArea->rowIndex, emptyGridArea->columnIndex);
602                 return;
603             }
604         }
605     }
606
607     // We didn't find an empty grid area so we need to create an extra major axis line and insert our gridItem in it.
608     const size_t columnIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? m_grid[0].size() : minorAxisIndex;
609     const size_t rowIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? minorAxisIndex : m_grid.size();
610     growGrid(autoPlacementMajorAxisDirection());
611     insertItemIntoGrid(gridItem, rowIndex, columnIndex);
612 }
613
614 const GridPosition& RenderGrid::autoPlacementMajorAxisPositionForChild(const RenderBox* gridItem) const
615 {
616     GridAutoFlow flow = style()->gridAutoFlow();
617     ASSERT(flow != AutoFlowNone);
618     return (flow == AutoFlowColumn) ? gridItem->style()->gridItemColumn() : gridItem->style()->gridItemRow();
619 }
620
621 const GridPosition& RenderGrid::autoPlacementMinorAxisPositionForChild(const RenderBox* gridItem) const
622 {
623     GridAutoFlow flow = style()->gridAutoFlow();
624     ASSERT(flow != AutoFlowNone);
625     return (flow == AutoFlowColumn) ? gridItem->style()->gridItemRow() : gridItem->style()->gridItemColumn();
626 }
627
628 RenderGrid::TrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
629 {
630     GridAutoFlow flow = style()->gridAutoFlow();
631     ASSERT(flow != AutoFlowNone);
632     return (flow == AutoFlowColumn) ? ForColumns : ForRows;
633 }
634
635 RenderGrid::TrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
636 {
637     GridAutoFlow flow = style()->gridAutoFlow();
638     ASSERT(flow != AutoFlowNone);
639     return (flow == AutoFlowColumn) ? ForRows : ForColumns;
640 }
641
642 void RenderGrid::clearGrid()
643 {
644     m_grid.clear();
645     m_gridItemCoordinate.clear();
646 }
647
648 void RenderGrid::layoutGridItems()
649 {
650     placeItemsOnGrid();
651
652     Vector<GridTrack> columnTracks(gridColumnCount());
653     Vector<GridTrack> rowTracks(gridRowCount());
654     computedUsedBreadthOfGridTracks(ForColumns, columnTracks, rowTracks);
655     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, columnTracks));
656     computedUsedBreadthOfGridTracks(ForRows, columnTracks, rowTracks);
657     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, rowTracks));
658
659     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
660         LayoutPoint childPosition = findChildLogicalPosition(child, columnTracks, rowTracks);
661
662         const GridCoordinate& childCoordinate = cachedGridCoordinate(child);
663
664         // Because the grid area cannot be styled, we don't need to adjust
665         // the grid breadth to account for 'box-sizing'.
666         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
667         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
668
669         // FIXME: For children in a content sized track, we clear the overrideContainingBlockContentLogicalHeight
670         // in minContentForChild / maxContentForChild which means that we will always relayout the child.
671         if (oldOverrideContainingBlockContentLogicalWidth != columnTracks[childCoordinate.columnIndex].m_usedBreadth || oldOverrideContainingBlockContentLogicalHeight != rowTracks[childCoordinate.rowIndex].m_usedBreadth)
672             child->setNeedsLayout(true, MarkOnlyThis);
673
674         child->setOverrideContainingBlockContentLogicalWidth(columnTracks[childCoordinate.columnIndex].m_usedBreadth);
675         child->setOverrideContainingBlockContentLogicalHeight(rowTracks[childCoordinate.rowIndex].m_usedBreadth);
676
677         // FIXME: Grid items should stretch to fill their cells. Once we
678         // implement grid-{column,row}-align, we can also shrink to fit. For
679         // now, just size as if we were a regular child.
680         child->layoutIfNeeded();
681
682         // FIXME: Handle border & padding on the grid element.
683         child->setLogicalLocation(childPosition);
684     }
685
686     for (size_t i = 0; i < rowTracks.size(); ++i)
687         setLogicalHeight(logicalHeight() + rowTracks[i].m_usedBreadth);
688
689     // FIXME: We should handle min / max logical height.
690
691     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
692     clearGrid();
693 }
694
695 RenderGrid::GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox* gridItem) const
696 {
697     ASSERT(m_gridItemCoordinate.contains(gridItem));
698     return m_gridItemCoordinate.get(gridItem);
699 }
700
701 size_t RenderGrid::resolveGridPositionFromStyle(const GridPosition& position) const
702 {
703     // FIXME: Handle other values for grid-{row,column} like ranges or line names.
704     switch (position.type()) {
705     case IntegerPosition:
706         // FIXME: What does a non-positive integer mean for a column/row?
707         if (!position.isPositive())
708             return 0;
709
710         return position.integerPosition() - 1;
711     case AutoPosition:
712         // We cannot resolve grid positions if grid-auto-flow != none as it requires several iterations.
713         ASSERT(style()->gridAutoFlow() == AutoFlowNone);
714         return 0;
715     }
716     ASSERT_NOT_REACHED();
717     return 0;
718 }
719
720 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks)
721 {
722     const GridCoordinate& coordinate = cachedGridCoordinate(child);
723
724     LayoutPoint offset;
725     // FIXME: |columnTrack| and |rowTrack| should be smaller than our column / row count.
726     for (size_t i = 0; i < coordinate.columnIndex && i < columnTracks.size(); ++i)
727         offset.setX(offset.x() + columnTracks[i].m_usedBreadth);
728     for (size_t i = 0; i < coordinate.rowIndex && i < rowTracks.size(); ++i)
729         offset.setY(offset.y() + rowTracks[i].m_usedBreadth);
730
731     // FIXME: Handle margins on the grid item.
732     return offset;
733 }
734
735 const char* RenderGrid::renderName() const
736 {
737     if (isFloating())
738         return "RenderGrid (floating)";
739     if (isOutOfFlowPositioned())
740         return "RenderGrid (positioned)";
741     if (isAnonymous())
742         return "RenderGrid (generated)";
743     if (isRelPositioned())
744         return "RenderGrid (relative positioned)";
745     return "RenderGrid";
746 }
747
748 } // namespace WebCore