cf44df9db1413dd5389f585ebafa1f9a6761867f
[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 = -1;
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         ASSERT(m_rowIndex < m_grid.size());
82         ASSERT(m_columnIndex < m_grid[0].size());
83     }
84
85     RenderBox* nextGridItem()
86     {
87         if (!m_grid.size())
88             return 0;
89
90         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
91         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
92         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
93             const Vector<RenderBox*>& children = m_grid[m_rowIndex][m_columnIndex];
94             if (m_childIndex < children.size())
95                 return children[m_childIndex++];
96
97             m_childIndex = 0;
98         }
99         return 0;
100     }
101
102     PassOwnPtr<GridCoordinate> nextEmptyGridArea()
103     {
104         if (m_grid.isEmpty())
105             return nullptr;
106
107         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
108         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
109         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
110             const Vector<RenderBox*>& children = m_grid[m_rowIndex][m_columnIndex];
111             if (children.isEmpty()) {
112                 OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(GridSpan(m_rowIndex, m_rowIndex), GridSpan(m_columnIndex, m_columnIndex)));
113                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
114                 ++varyingTrackIndex;
115                 return result.release();
116             }
117         }
118         return nullptr;
119     }
120
121 private:
122     const Vector<Vector<Vector<RenderBox*, 1> > >& m_grid;
123     TrackSizingDirection m_direction;
124     size_t m_rowIndex;
125     size_t m_columnIndex;
126     size_t m_childIndex;
127 };
128
129 RenderGrid::RenderGrid(Element* element)
130     : RenderBlock(element)
131 {
132     // All of our children must be block level.
133     setChildrenInline(false);
134 }
135
136 RenderGrid::~RenderGrid()
137 {
138 }
139
140 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
141 {
142     ASSERT(needsLayout());
143
144     if (!relayoutChildren && simplifiedLayout())
145         return;
146
147     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
148     // It would be nice to refactor some of the duplicate code.
149     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
150     LayoutStateMaintainer statePusher(&view(), this, locationOffset(), hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
151
152     // Regions changing widths can force us to relayout our children.
153     RenderFlowThread* flowThread = flowThreadContainingBlock();
154     if (logicalWidthChangedInRegions(flowThread))
155         relayoutChildren = true;
156     if (updateShapesBeforeBlockLayout())
157         relayoutChildren = true;
158
159     LayoutSize previousSize = size();
160
161     setLogicalHeight(0);
162     updateLogicalWidth();
163
164     layoutGridItems();
165
166     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
167     updateLogicalHeight();
168
169     if (size() != previousSize)
170         relayoutChildren = true;
171
172     layoutPositionedObjects(relayoutChildren || isRoot());
173
174     updateShapesAfterBlockLayout();
175
176     computeOverflow(oldClientAfterEdge);
177     statePusher.pop();
178
179     updateLayerTransform();
180
181     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
182     // we overflow or not.
183     updateScrollInfoAfterLayout();
184
185     repainter.repaintAfterLayout();
186
187     setNeedsLayout(false);
188 }
189
190 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
191 {
192     const_cast<RenderGrid*>(this)->placeItemsOnGrid();
193
194     // FIXME: This is an inefficient way to fill our sizes as it will try every grid areas, when we would
195     // only want to account for fixed grid tracks and grid items. Also this will be incorrect if we have spanning
196     // grid items.
197     for (size_t i = 0; i < gridColumnCount(); ++i) {
198         const GridTrackSize& trackSize = gridTrackSize(ForColumns, i);
199         LayoutUnit minTrackBreadth = computePreferredTrackWidth(trackSize.minTrackBreadth(), i);
200         LayoutUnit maxTrackBreadth = computePreferredTrackWidth(trackSize.maxTrackBreadth(), i);
201         maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth);
202
203         minLogicalWidth += minTrackBreadth;
204         maxLogicalWidth += maxTrackBreadth;
205
206         // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
207     }
208
209     const_cast<RenderGrid*>(this)->clearGrid();
210 }
211
212 void RenderGrid::computePreferredLogicalWidths()
213 {
214     ASSERT(preferredLogicalWidthsDirty());
215
216     m_minPreferredLogicalWidth = 0;
217     m_maxPreferredLogicalWidth = 0;
218
219     // FIXME: We don't take our own logical width into account. Once we do, we need to make sure
220     // we apply (and test the interaction with) min-width / max-width.
221
222     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
223
224     LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
225     m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
226     m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
227
228     setPreferredLogicalWidthsDirty(false);
229 }
230
231 LayoutUnit RenderGrid::computePreferredTrackWidth(const Length& length, size_t trackIndex) const
232 {
233     if (length.isFixed()) {
234         // Grid areas don't have borders, margins or paddings so we don't need to account for them.
235         return length.intValue();
236     }
237
238     if (length.isMinContent()) {
239         LayoutUnit minContentSize = 0;
240         GridIterator iterator(m_grid, ForColumns, trackIndex);
241         while (RenderBox* gridItem = iterator.nextGridItem()) {
242             // FIXME: We should include the child's fixed margins like RenderFlexibleBox.
243             minContentSize = std::max(minContentSize, gridItem->minPreferredLogicalWidth());
244         }
245         return minContentSize;
246     }
247
248     if (length.isMaxContent()) {
249         LayoutUnit maxContentSize = 0;
250         GridIterator iterator(m_grid, ForColumns, trackIndex);
251         while (RenderBox* gridItem = iterator.nextGridItem()) {
252             // FIXME: We should include the child's fixed margins like RenderFlexibleBox.
253             maxContentSize = std::max(maxContentSize, gridItem->maxPreferredLogicalWidth());
254         }
255         return maxContentSize;
256     }
257
258     // FIXME: css3-sizing mentions that we should resolve "definite sizes"
259     // (including <percentage> and calc()) but we don't do it elsewhere.
260     return 0;
261 }
262
263 void RenderGrid::computedUsedBreadthOfGridTracks(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks)
264 {
265     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
266     Vector<GridTrack>& tracks = (direction == ForColumns) ? columnTracks : rowTracks;
267     for (size_t i = 0; i < tracks.size(); ++i) {
268         GridTrack& track = tracks[i];
269         const GridTrackSize& trackSize = gridTrackSize(direction, i);
270         const Length& minTrackBreadth = trackSize.minTrackBreadth();
271         const Length& maxTrackBreadth = trackSize.maxTrackBreadth();
272
273         track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth);
274         track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth);
275
276         track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth);
277     }
278
279     // FIXME: We shouldn't call resolveContentBasedTrackSizingFunctions if we have no min-content / max-content tracks.
280     resolveContentBasedTrackSizingFunctions(direction, columnTracks, rowTracks, availableLogicalSpace);
281
282     if (availableLogicalSpace <= 0)
283         return;
284
285     const size_t tracksSize = tracks.size();
286     Vector<GridTrack*> tracksForDistribution(tracksSize);
287     for (size_t i = 0; i < tracksSize; ++i)
288         tracksForDistribution[i] = tracks.data() + i;
289
290     distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, availableLogicalSpace);
291 }
292
293 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(TrackSizingDirection direction, const Length& trackLength) const
294 {
295     if (trackLength.isFixed() || trackLength.isPercent() || trackLength.isViewportPercentage())
296         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
297
298     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent() || trackLength.isAuto());
299     return 0;
300 }
301
302 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(TrackSizingDirection direction, const Length& trackLength) const
303 {
304     if (trackLength.isFixed() || trackLength.isPercent() || trackLength.isViewportPercentage()) {
305         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
306         ASSERT(computedBreadth != infinity);
307         return computedBreadth;
308     }
309
310     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent() || trackLength.isAuto());
311     return infinity;
312 }
313
314 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(TrackSizingDirection direction, const Length& trackLength) const
315 {
316     // FIXME: We still need to support calc() here (https://webkit.org/b/103761).
317     ASSERT(trackLength.isFixed() || trackLength.isPercent() || trackLength.isViewportPercentage());
318     return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style()->logicalHeight()), &view());
319 }
320
321 const GridTrackSize& RenderGrid::gridTrackSize(TrackSizingDirection direction, size_t i) const
322 {
323     const Vector<GridTrackSize>& trackStyles = (direction == ForColumns) ? style()->gridColumns() : style()->gridRows();
324     if (i >= trackStyles.size())
325         return (direction == ForColumns) ? style()->gridAutoColumns() : style()->gridAutoRows();
326
327     return trackStyles[i];
328 }
329
330 size_t RenderGrid::explicitGridColumnCount() const
331 {
332     return style()->gridColumns().size();
333 }
334
335 size_t RenderGrid::explicitGridRowCount() const
336 {
337     return style()->gridRows().size();
338 }
339
340 size_t RenderGrid::maximumIndexInDirection(TrackSizingDirection direction) const
341 {
342     size_t maximumIndex = std::max<size_t>(1, (direction == ForColumns) ? explicitGridColumnCount() : explicitGridRowCount());
343
344     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
345         OwnPtr<GridSpan> positions = resolveGridPositionsFromStyle(child, direction);
346
347         // |positions| is null if we need to run the auto-placement algorithm. Our estimation ignores
348         // this case as the auto-placement algorithm will grow the grid as needed.
349         if (!positions)
350             continue;
351
352         maximumIndex = std::max(maximumIndex, positions->finalPositionIndex + 1);
353     }
354
355     return maximumIndex;
356 }
357
358 LayoutUnit RenderGrid::logicalContentHeightForChild(RenderBox* child, Vector<GridTrack>& columnTracks)
359 {
360     // FIXME: We shouldn't force a layout every time this function is called but
361     // 1) Return computeLogicalHeight's value if it's available. Unfortunately computeLogicalHeight
362     // doesn't return if the logical height is available so would need to be changed.
363     // 2) Relayout if the column track's used breadth changed OR the logical height is unavailable.
364     if (!child->needsLayout())
365         child->setNeedsLayout(true, MarkOnlyThis);
366
367     child->setOverrideContainingBlockContentLogicalWidth(gridAreaBreadthForChild(child, ForColumns, columnTracks));
368     // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is
369     // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution).
370     child->setOverrideContainingBlockContentLogicalHeight(-1);
371     child->layout();
372     return child->logicalHeight();
373 }
374
375 LayoutUnit RenderGrid::minContentForChild(RenderBox* child, TrackSizingDirection direction, Vector<GridTrack>& columnTracks)
376 {
377     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
378     // FIXME: Properly support orthogonal writing mode.
379     if (hasOrthogonalWritingMode)
380         return 0;
381
382     if (direction == ForColumns) {
383         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
384         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
385         return child->minPreferredLogicalWidth();
386     }
387
388     return logicalContentHeightForChild(child, columnTracks);
389 }
390
391 LayoutUnit RenderGrid::maxContentForChild(RenderBox* child, TrackSizingDirection direction, Vector<GridTrack>& columnTracks)
392 {
393     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
394     // FIXME: Properly support orthogonal writing mode.
395     if (hasOrthogonalWritingMode)
396         return LayoutUnit();
397
398     if (direction == ForColumns) {
399         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
400         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
401         return child->maxPreferredLogicalWidth();
402     }
403
404     return logicalContentHeightForChild(child, columnTracks);
405 }
406
407 void RenderGrid::resolveContentBasedTrackSizingFunctions(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, LayoutUnit& availableLogicalSpace)
408 {
409     // FIXME: Split the grid tracks once we support fractions (step 1 of the algorithm).
410
411     Vector<GridTrack>& tracks = (direction == ForColumns) ? columnTracks : rowTracks;
412
413     // FIXME: Per step 2 of the specification, we should order the grid items by increasing span.
414     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
415         resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, child, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
416         resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, child, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
417         resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, child, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
418         resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, child, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
419     }
420
421     for (size_t i = 0; i < tracks.size(); ++i) {
422         GridTrack& track = tracks[i];
423         if (track.m_maxBreadth == infinity)
424             track.m_maxBreadth = track.m_usedBreadth;
425
426         availableLogicalSpace -= track.m_usedBreadth;
427     }
428 }
429
430 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, RenderBox* gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
431 {
432     const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
433     const size_t initialTrackIndex = (direction == ForColumns) ? coordinate.columns.initialPositionIndex : coordinate.rows.initialPositionIndex;
434     const size_t finalTrackIndex = (direction == ForColumns) ? coordinate.columns.finalPositionIndex : coordinate.rows.finalPositionIndex;
435
436     Vector<GridTrack*> tracks;
437     for (size_t trackIndex = initialTrackIndex; trackIndex <= finalTrackIndex; ++trackIndex) {
438         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
439         if (!(trackSize.*filterFunction)())
440             continue;
441
442         GridTrack& track = (direction == ForColumns) ? columnTracks[trackIndex] : rowTracks[trackIndex];
443         tracks.append(&track);
444     }
445
446     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, columnTracks);
447     for (size_t trackIndexForSpace = initialTrackIndex; trackIndexForSpace <= finalTrackIndex; ++trackIndexForSpace) {
448         GridTrack& track = (direction == ForColumns) ? columnTracks[trackIndexForSpace] : rowTracks[trackIndexForSpace];
449         additionalBreadthSpace -= (track.*trackGetter)();
450     }
451
452     // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
453     distributeSpaceToTracks(tracks, &tracks, trackGetter, trackGrowthFunction, additionalBreadthSpace);
454 }
455
456 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
457 {
458     return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
459 }
460
461 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, LayoutUnit& availableLogicalSpace)
462 {
463     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
464
465     size_t tracksSize = tracks.size();
466     Vector<LayoutUnit> updatedTrackBreadths(tracksSize);
467
468     for (size_t i = 0; i < tracksSize; ++i) {
469         GridTrack& track = *tracks[i];
470         LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
471         LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
472         LayoutUnit growthShare = std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth);
473         updatedTrackBreadths[i] = trackBreadth + growthShare;
474         availableLogicalSpace -= growthShare;
475     }
476
477     if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) {
478         tracksSize = tracksForGrowthAboveMaxBreadth->size();
479         for (size_t i = 0; i < tracksSize; ++i) {
480             LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
481             updatedTrackBreadths[i] += growthShare;
482             availableLogicalSpace -= growthShare;
483         }
484     }
485
486     for (size_t i = 0; i < tracksSize; ++i) {
487         LayoutUnit growth = updatedTrackBreadths[i] - (tracks[i]->*trackGetter)();
488         if (growth >= 0)
489             (tracks[i]->*trackGrowthFunction)(growth);
490     }
491 }
492
493 #ifndef NDEBUG
494 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(TrackSizingDirection direction, const Vector<GridTrack>& tracks)
495 {
496     for (size_t i = 0; i < tracks.size(); ++i) {
497         const GridTrackSize& trackSize = gridTrackSize(direction, i);
498         const Length& minTrackBreadth = trackSize.minTrackBreadth();
499         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth)
500             return false;
501     }
502     return true;
503 }
504 #endif
505
506 void RenderGrid::growGrid(TrackSizingDirection direction)
507 {
508     if (direction == ForColumns) {
509         const size_t oldColumnSize = m_grid[0].size();
510         for (size_t row = 0; row < m_grid.size(); ++row)
511             m_grid[row].grow(oldColumnSize + 1);
512     } else {
513         const size_t oldRowSize = m_grid.size();
514         m_grid.grow(oldRowSize + 1);
515         m_grid[oldRowSize].grow(m_grid[0].size());
516     }
517 }
518
519 void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridCoordinate& coordinate)
520 {
521     m_grid[coordinate.rows.initialPositionIndex][coordinate.columns.initialPositionIndex].append(child);
522     m_gridItemCoordinate.set(child, coordinate);
523 }
524
525 void RenderGrid::insertItemIntoGrid(RenderBox* child, size_t rowTrack, size_t columnTrack)
526 {
527     const GridSpan& rowSpan = resolveGridPositionsFromAutoPlacementPosition(child, ForRows, rowTrack);
528     const GridSpan& columnSpan = resolveGridPositionsFromAutoPlacementPosition(child, ForColumns, columnTrack);
529     insertItemIntoGrid(child, GridCoordinate(rowSpan, columnSpan));
530 }
531
532 void RenderGrid::placeItemsOnGrid()
533 {
534     ASSERT(!gridWasPopulated());
535     ASSERT(m_gridItemCoordinate.isEmpty());
536
537     m_grid.grow(maximumIndexInDirection(ForRows));
538     size_t maximumColumnIndex = maximumIndexInDirection(ForColumns);
539     for (size_t i = 0; i < m_grid.size(); ++i)
540         m_grid[i].grow(maximumColumnIndex);
541
542     Vector<RenderBox*> autoMajorAxisAutoGridItems;
543     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
544     GridAutoFlow autoFlow = style()->gridAutoFlow();
545     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
546         // FIXME: We never re-resolve positions if the grid is grown during auto-placement which may lead auto / <integer>
547         // positions to not match the author's intent. The specification is unclear on what should be done in this case.
548         OwnPtr<GridSpan> rowPositions = resolveGridPositionsFromStyle(child, ForRows);
549         OwnPtr<GridSpan> columnPositions = resolveGridPositionsFromStyle(child, ForColumns);
550         if (!rowPositions || !columnPositions) {
551             GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get();
552             if (!majorAxisPositions)
553                 autoMajorAxisAutoGridItems.append(child);
554             else
555                 specifiedMajorAxisAutoGridItems.append(child);
556             continue;
557         }
558         insertItemIntoGrid(child, GridCoordinate(*rowPositions, *columnPositions));
559     }
560
561     ASSERT(gridRowCount() >= style()->gridRows().size());
562     ASSERT(gridColumnCount() >= style()->gridColumns().size());
563
564     if (autoFlow == AutoFlowNone) {
565         // If we did collect some grid items, they won't be placed thus never laid out.
566         ASSERT(!autoMajorAxisAutoGridItems.size());
567         ASSERT(!specifiedMajorAxisAutoGridItems.size());
568         return;
569     }
570
571     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
572     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
573 }
574
575 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(Vector<RenderBox*> autoGridItems)
576 {
577     for (size_t i = 0; i < autoGridItems.size(); ++i) {
578         OwnPtr<GridSpan> majorAxisPositions = resolveGridPositionsFromStyle(autoGridItems[i], autoPlacementMajorAxisDirection());
579         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->initialPositionIndex);
580         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
581             insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
582             continue;
583         }
584
585         growGrid(autoPlacementMinorAxisDirection());
586         OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
587         ASSERT(emptyGridArea);
588         insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
589     }
590 }
591
592 void RenderGrid::placeAutoMajorAxisItemsOnGrid(Vector<RenderBox*> autoGridItems)
593 {
594     for (size_t i = 0; i < autoGridItems.size(); ++i)
595         placeAutoMajorAxisItemOnGrid(autoGridItems[i]);
596 }
597
598 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
599 {
600     OwnPtr<GridSpan> minorAxisPositions = resolveGridPositionsFromStyle(gridItem, autoPlacementMinorAxisDirection());
601     ASSERT(!resolveGridPositionsFromStyle(gridItem, autoPlacementMajorAxisDirection()));
602     size_t minorAxisIndex = 0;
603     if (minorAxisPositions) {
604         minorAxisIndex = minorAxisPositions->initialPositionIndex;
605         GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisIndex);
606         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
607             insertItemIntoGrid(gridItem, emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
608             return;
609         }
610     } else {
611         const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
612         for (size_t majorAxisIndex = 0; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
613             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex);
614             if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
615                 insertItemIntoGrid(gridItem, emptyGridArea->rows.initialPositionIndex, emptyGridArea->columns.initialPositionIndex);
616                 return;
617             }
618         }
619     }
620
621     // We didn't find an empty grid area so we need to create an extra major axis line and insert our gridItem in it.
622     const size_t columnIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? m_grid[0].size() : minorAxisIndex;
623     const size_t rowIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? minorAxisIndex : m_grid.size();
624     growGrid(autoPlacementMajorAxisDirection());
625     insertItemIntoGrid(gridItem, rowIndex, columnIndex);
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         // Because the grid area cannot be styled, we don't need to adjust
663         // the grid breadth to account for 'box-sizing'.
664         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
665         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
666
667         // FIXME: For children in a content sized track, we clear the overrideContainingBlockContentLogicalHeight
668         // in minContentForChild / maxContentForChild which means that we will always relayout the child.
669         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
670         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(child, ForRows, rowTracks);
671         if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight)
672             child->setNeedsLayout(true, MarkOnlyThis);
673
674         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
675         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
676
677         LayoutRect oldChildRect = child->frameRect();
678
679         // FIXME: Grid items should stretch to fill their cells. Once we
680         // implement grid-{column,row}-align, we can also shrink to fit. For
681         // now, just size as if we were a regular child.
682         child->layoutIfNeeded();
683
684         // FIXME: Handle border & padding on the grid element.
685         child->setLogicalLocation(childPosition);
686
687         // If the child moved, we have to repaint it as well as any floating/positioned
688         // descendants. An exception is if we need a layout. In this case, we know we're going to
689         // repaint ourselves (and the child) anyway.
690         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
691             child->repaintDuringLayoutIfMoved(oldChildRect);
692     }
693
694     for (size_t i = 0; i < rowTracks.size(); ++i)
695         setLogicalHeight(logicalHeight() + rowTracks[i].m_usedBreadth);
696
697     // FIXME: We should handle min / max logical height.
698
699     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
700     clearGrid();
701 }
702
703 RenderGrid::GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox* gridItem) const
704 {
705     ASSERT(m_gridItemCoordinate.contains(gridItem));
706     return m_gridItemCoordinate.get(gridItem);
707 }
708
709 RenderGrid::GridSpan RenderGrid::resolveGridPositionsFromAutoPlacementPosition(const RenderBox*, TrackSizingDirection, size_t initialPosition) const
710 {
711     // FIXME: We don't support spanning with auto positions yet. Once we do, this is wrong. Also we should make
712     // sure the grid can accomodate the new item as we only grow 1 position in a given direction.
713     return GridSpan(initialPosition, initialPosition);
714 }
715
716 PassOwnPtr<RenderGrid::GridSpan> RenderGrid::resolveGridPositionsFromStyle(const RenderBox* gridItem, TrackSizingDirection direction) const
717 {
718     const GridPosition& initialPosition = (direction == ForColumns) ? gridItem->style()->gridItemColumnStart() : gridItem->style()->gridItemRowStart();
719     const GridPositionSide initialPositionSide = (direction == ForColumns) ? ColumnStartSide : RowStartSide;
720     const GridPosition& finalPosition = (direction == ForColumns) ? gridItem->style()->gridItemColumnEnd() : gridItem->style()->gridItemRowEnd();
721     const GridPositionSide finalPositionSide = (direction == ForColumns) ? ColumnEndSide : RowEndSide;
722
723     // We should NEVER see both spans as they should have been handled during style resolve.
724     ASSERT(!initialPosition.isSpan() || !finalPosition.isSpan());
725
726     if (initialPosition.isAuto() && finalPosition.isAuto()) {
727         if (style()->gridAutoFlow() == AutoFlowNone)
728             return adoptPtr(new GridSpan(0, 0));
729
730         // We can't get our grid positions without running the auto placement algorithm.
731         return nullptr;
732     }
733
734     if (initialPosition.shouldBeResolvedAgainstOppositePosition()) {
735         // Infer the position from the final position ('auto / 1' or 'span 2 / 3' case).
736         const size_t finalResolvedPosition = resolveGridPositionFromStyle(finalPosition, finalPositionSide);
737         return resolveGridPositionAgainstOppositePosition(finalResolvedPosition, initialPosition, initialPositionSide);
738     }
739
740     if (finalPosition.shouldBeResolvedAgainstOppositePosition()) {
741         // Infer our position from the initial position ('1 / auto' or '3 / span 2' case).
742         const size_t initialResolvedPosition = resolveGridPositionFromStyle(initialPosition, initialPositionSide);
743         return resolveGridPositionAgainstOppositePosition(initialResolvedPosition, finalPosition, finalPositionSide);
744     }
745
746     size_t resolvedInitialPosition = resolveGridPositionFromStyle(initialPosition, initialPositionSide);
747     size_t resolvedFinalPosition = resolveGridPositionFromStyle(finalPosition, finalPositionSide);
748
749     // If 'grid-row-end' specifies a line at or before that specified by 'grid-row-start', it computes to 'span 1'.
750     if (resolvedFinalPosition < resolvedInitialPosition)
751         resolvedFinalPosition = resolvedInitialPosition;
752
753     return adoptPtr(new GridSpan(resolvedInitialPosition, resolvedFinalPosition));
754 }
755
756 static size_t adjustGridPositionForSide(size_t resolvedPosition, RenderGrid::GridPositionSide side)
757 {
758     // An item finishing on the N-th line belongs to the N-1-th cell.
759     if (side == RenderGrid::ColumnEndSide || side == RenderGrid::RowEndSide)
760         return resolvedPosition ? resolvedPosition - 1 : 0;
761
762     return resolvedPosition;
763 }
764
765 size_t RenderGrid::resolveGridPositionFromStyle(const GridPosition& position, GridPositionSide side) const
766 {
767     // FIXME: Handle other values for grid-{row,column} like ranges or line names.
768     switch (position.type()) {
769     case IntegerPosition: {
770         ASSERT(position.integerPosition());
771         if (position.isPositive())
772             return adjustGridPositionForSide(position.integerPosition() - 1, side);
773
774         size_t resolvedPosition = abs(position.integerPosition()) - 1;
775         const size_t endOfTrack = (side == ColumnStartSide || side == ColumnEndSide) ? explicitGridColumnCount() : explicitGridRowCount();
776
777         // Per http://lists.w3.org/Archives/Public/www-style/2013Mar/0589.html, we clamp negative value to the first line.
778         if (endOfTrack < resolvedPosition)
779             return 0;
780
781         return adjustGridPositionForSide(endOfTrack - resolvedPosition, side);
782     }
783     case AutoPosition:
784         // 'auto' depends on the opposite position for resolution (e.g. grid-row: auto / 1).
785         ASSERT_NOT_REACHED();
786         return 0;
787     case SpanPosition:
788         // FIXME: Handle span positions.
789         ASSERT_NOT_REACHED();
790         return 0;
791     }
792     ASSERT_NOT_REACHED();
793     return 0;
794 }
795
796 PassOwnPtr<RenderGrid::GridSpan> RenderGrid::resolveGridPositionAgainstOppositePosition(size_t resolvedOppositePosition, const GridPosition& position, GridPositionSide side) const
797 {
798     if (position.isAuto())
799         return GridSpan::create(resolvedOppositePosition, resolvedOppositePosition);
800
801     ASSERT(position.isSpan());
802     ASSERT(position.spanPosition() > 0);
803
804     // 'span 1' is contained inside a single grid track regardless of the direction.
805     // That's why the CSS span value is one more than the offset we apply.
806     size_t positionOffset = position.spanPosition() - 1;
807     if (side == ColumnStartSide || side == RowStartSide) {
808         size_t initialResolvedPosition = std::max<int>(0, resolvedOppositePosition - positionOffset);
809         return GridSpan::create(initialResolvedPosition, resolvedOppositePosition);
810     }
811
812     return GridSpan::create(resolvedOppositePosition, resolvedOppositePosition + positionOffset);
813 }
814
815 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox* child, TrackSizingDirection direction, const Vector<GridTrack>& tracks) const
816 {
817     const GridCoordinate& coordinate = cachedGridCoordinate(child);
818     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
819     LayoutUnit gridAreaBreadth = 0;
820     for (size_t trackIndex = span.initialPositionIndex; trackIndex <= span.finalPositionIndex; ++trackIndex)
821         gridAreaBreadth += tracks[trackIndex].m_usedBreadth;
822     return gridAreaBreadth;
823 }
824
825 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks)
826 {
827     const GridCoordinate& coordinate = cachedGridCoordinate(child);
828
829     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
830     LayoutPoint offset(borderAndPaddingStart(), borderAndPaddingBefore());
831     // FIXME: |columnTrack| and |rowTrack| should be smaller than our column / row count.
832     for (size_t i = 0; i < coordinate.columns.initialPositionIndex && i < columnTracks.size(); ++i)
833         offset.setX(offset.x() + columnTracks[i].m_usedBreadth);
834     for (size_t i = 0; i < coordinate.rows.initialPositionIndex && i < rowTracks.size(); ++i)
835         offset.setY(offset.y() + rowTracks[i].m_usedBreadth);
836
837     // FIXME: Handle margins on the grid item.
838     return offset;
839 }
840
841 const char* RenderGrid::renderName() const
842 {
843     if (isFloating())
844         return "RenderGrid (floating)";
845     if (isOutOfFlowPositioned())
846         return "RenderGrid (positioned)";
847     if (isAnonymous())
848         return "RenderGrid (generated)";
849     if (isRelPositioned())
850         return "RenderGrid (relative positioned)";
851     return "RenderGrid";
852 }
853
854 } // namespace WebCore