src/third_party/WebKit/Source/core/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 "core/rendering/RenderGrid.h"
  28
  29 #include "core/paint/GridPainter.h"
  30 #include "core/rendering/RenderLayer.h"
  31 #include "core/rendering/RenderView.h"
  32 #include "core/rendering/TextAutosizer.h"
  33 #include "core/rendering/style/GridCoordinate.h"
  34 #include "platform/LengthFunctions.h"
  35
  36 namespace blink {
  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     // Required by std::sort.
  80     GridTrackForNormalization& operator=(const GridTrackForNormalization& o)
  81     {
  82         m_track = o.m_track;
  83         m_flex = o.m_flex;
  84         m_normalizedFlexValue = o.m_normalizedFlexValue;
  85         return *this;
  86     }
  87
  88     const GridTrack* m_track;
  89     double m_flex;
  90     LayoutUnit m_normalizedFlexValue;
  91 };
  92
  93 class RenderGrid::GridIterator {
  94     WTF_MAKE_NONCOPYABLE(GridIterator);
  95 public:
  96     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
  97     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
  98     GridIterator(const GridRepresentation& grid, GridTrackSizingDirection direction, size_t fixedTrackIndex, size_t varyingTrackIndex = 0)
  99         : m_grid(grid)
 100         , m_direction(direction)
 101         , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
 102         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
 103         , m_childIndex(0)
 104     {
 105         ASSERT(m_rowIndex < m_grid.size());
 106         ASSERT(m_columnIndex < m_grid[0].size());
 107     }
 108
 109     RenderBox* nextGridItem()
 110     {
 111         ASSERT(!m_grid.isEmpty());
 112
 113         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
 114         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
 115         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
 116             const GridCell& children = m_grid[m_rowIndex][m_columnIndex];
 117             if (m_childIndex < children.size())
 118                 return children[m_childIndex++];
 119
 120             m_childIndex = 0;
 121         }
 122         return 0;
 123     }
 124
 125     bool checkEmptyCells(size_t rowSpan, size_t columnSpan) const
 126     {
 127         // Ignore cells outside current grid as we will grow it later if needed.
 128         size_t maxRows = std::min(m_rowIndex + rowSpan, m_grid.size());
 129         size_t maxColumns = std::min(m_columnIndex + columnSpan, m_grid[0].size());
 130
 131         // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
 132         for (size_t row = m_rowIndex; row < maxRows; ++row) {
 133             for (size_t column = m_columnIndex; column < maxColumns; ++column) {
 134                 const GridCell& children = m_grid[row][column];
 135                 if (!children.isEmpty())
 136                     return false;
 137             }
 138         }
 139
 140         return true;
 141     }
 142
 143     PassOwnPtr<GridCoordinate> nextEmptyGridArea(size_t fixedTrackSpan, size_t varyingTrackSpan)
 144     {
 145         ASSERT(!m_grid.isEmpty());
 146         ASSERT(fixedTrackSpan >= 1 && varyingTrackSpan >= 1);
 147
 148         size_t rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
 149         size_t columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
 150
 151         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
 152         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
 153         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
 154             if (checkEmptyCells(rowSpan, columnSpan)) {
 155                 OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(GridSpan(m_rowIndex, m_rowIndex + rowSpan - 1), GridSpan(m_columnIndex, m_columnIndex + columnSpan - 1)));
 156                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
 157                 ++varyingTrackIndex;
 158                 return result.release();
 159             }
 160         }
 161         return nullptr;
 162     }
 163
 164 private:
 165     const GridRepresentation& m_grid;
 166     GridTrackSizingDirection m_direction;
 167     size_t m_rowIndex;
 168     size_t m_columnIndex;
 169     size_t m_childIndex;
 170 };
 171
 172 struct RenderGrid::GridSizingData {
 173     WTF_MAKE_NONCOPYABLE(GridSizingData);
 174 public:
 175     GridSizingData(size_t gridColumnCount, size_t gridRowCount)
 176         : columnTracks(gridColumnCount)
 177         , rowTracks(gridRowCount)
 178     {
 179     }
 180
 181     Vector<GridTrack> columnTracks;
 182     Vector<GridTrack> rowTracks;
 183     Vector<size_t> contentSizedTracksIndex;
 184
 185     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
 186     Vector<LayoutUnit> distributeTrackVector;
 187     Vector<GridTrack*> filteredTracks;
 188 };
 189
 190 RenderGrid::RenderGrid(Element* element)
 191     : RenderBlock(element)
 192     , m_gridIsDirty(true)
 193     , m_orderIterator(this)
 194 {
 195     ASSERT(!childrenInline());
 196 }
 197
 198 RenderGrid::~RenderGrid()
 199 {
 200 }
 201
 202 void RenderGrid::addChild(RenderObject* newChild, RenderObject* beforeChild)
 203 {
 204     // If the new requested beforeChild is not one of our children is because it's wrapped by an anonymous container. If
 205     // we do not special case this situation we could end up calling addChild() twice for the newChild, one with the
 206     // initial beforeChild and another one with its parent.
 207     if (beforeChild && beforeChild->parent() != this) {
 208         ASSERT(beforeChild->parent()->isAnonymous());
 209         beforeChild = splitAnonymousBoxesAroundChild(beforeChild);
 210         dirtyGrid();
 211     }
 212
 213     RenderBlock::addChild(newChild, beforeChild);
 214
 215     if (gridIsDirty())
 216         return;
 217
 218     if (!newChild->isBox()) {
 219         dirtyGrid();
 220         return;
 221     }
 222
 223     // If the new child has been inserted inside an existent anonymous block, we can simply ignore it as the anonymous
 224     // block is an already known grid item.
 225     if (newChild->parent() != this)
 226         return;
 227
 228     // FIXME: Implement properly "stack" value in auto-placement algorithm.
 229     if (!style()->isGridAutoFlowAlgorithmStack()) {
 230         // The grid needs to be recomputed as it might contain auto-placed items that will change their position.
 231         dirtyGrid();
 232         return;
 233     }
 234
 235     RenderBox* newChildBox = toRenderBox(newChild);
 236     OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForRows);
 237     OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForColumns);
 238     if (!rowPositions || !columnPositions) {
 239         // The new child requires the auto-placement algorithm to run so we need to recompute the grid fully.
 240         dirtyGrid();
 241         return;
 242     } else {
 243         insertItemIntoGrid(*newChildBox, GridCoordinate(*rowPositions, *columnPositions));
 244         addChildToIndexesMap(*newChildBox);
 245     }
 246 }
 247
 248 void RenderGrid::addChildToIndexesMap(RenderBox& child)
 249 {
 250     ASSERT(!m_gridItemsIndexesMap.contains(&child));
 251     RenderBox* sibling = child.nextSiblingBox();
 252     bool lastSibling = !sibling;
 253
 254     if (lastSibling)
 255         sibling = child.previousSiblingBox();
 256
 257     size_t index = 0;
 258     if (sibling)
 259         index = lastSibling ? m_gridItemsIndexesMap.get(sibling) + 1 : m_gridItemsIndexesMap.get(sibling);
 260
 261     if (sibling && !lastSibling) {
 262         for (; sibling; sibling = sibling->nextSiblingBox())
 263             m_gridItemsIndexesMap.set(sibling, m_gridItemsIndexesMap.get(sibling) + 1);
 264     }
 265
 266     m_gridItemsIndexesMap.set(&child, index);
 267 }
 268
 269 void RenderGrid::removeChild(RenderObject* child)
 270 {
 271     RenderBlock::removeChild(child);
 272
 273     if (gridIsDirty())
 274         return;
 275
 276     ASSERT(child->isBox());
 277
 278     // FIXME: Implement properly "stack" value in auto-placement algorithm.
 279     if (!style()->isGridAutoFlowAlgorithmStack()) {
 280         // The grid needs to be recomputed as it might contain auto-placed items that will change their position.
 281         dirtyGrid();
 282         return;
 283     }
 284
 285     const RenderBox* childBox = toRenderBox(child);
 286     GridCoordinate coordinate = m_gridItemCoordinate.take(childBox);
 287
 288     for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) {
 289         for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column) {
 290             GridCell& cell = m_grid[row.toInt()][column.toInt()];
 291             cell.remove(cell.find(childBox));
 292         }
 293     }
 294
 295     m_gridItemsIndexesMap.remove(childBox);
 296 }
 297
 298 void RenderGrid::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
 299 {
 300     RenderBlock::styleDidChange(diff, oldStyle);
 301     if (!oldStyle)
 302         return;
 303
 304     // FIXME: The following checks could be narrowed down if we kept track of which type of grid items we have:
 305     // - explicit grid size changes impact negative explicitely positioned and auto-placed grid items.
 306     // - named grid lines only impact grid items with named grid lines.
 307     // - auto-flow changes only impacts auto-placed children.
 308
 309     if (explicitGridDidResize(oldStyle)
 310         || namedGridLinesDefinitionDidChange(oldStyle)
 311         || oldStyle->gridAutoFlow() != style()->gridAutoFlow())
 312         dirtyGrid();
 313 }
 314
 315 bool RenderGrid::explicitGridDidResize(const RenderStyle* oldStyle) const
 316 {
 317     return oldStyle->gridTemplateColumns().size() != style()->gridTemplateColumns().size()
 318         || oldStyle->gridTemplateRows().size() != style()->gridTemplateRows().size();
 319 }
 320
 321 bool RenderGrid::namedGridLinesDefinitionDidChange(const RenderStyle* oldStyle) const
 322 {
 323     return oldStyle->namedGridRowLines() != style()->namedGridRowLines()
 324         || oldStyle->namedGridColumnLines() != style()->namedGridColumnLines();
 325 }
 326
 327 void RenderGrid::layoutBlock(bool relayoutChildren)
 328 {
 329     ASSERT(needsLayout());
 330
 331     if (!relayoutChildren && simplifiedLayout())
 332         return;
 333
 334     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
 335     // It would be nice to refactor some of the duplicate code.
 336     LayoutState state(*this, locationOffset());
 337
 338     LayoutSize previousSize = size();
 339
 340     setLogicalHeight(0);
 341     updateLogicalWidth();
 342
 343     TextAutosizer::LayoutScope textAutosizerLayoutScope(this);
 344
 345     layoutGridItems();
 346
 347     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
 348     updateLogicalHeight();
 349
 350     if (size() != previousSize)
 351         relayoutChildren = true;
 352
 353     layoutPositionedObjects(relayoutChildren || isDocumentElement());
 354
 355     computeOverflow(oldClientAfterEdge);
 356
 357     updateLayerTransformAfterLayout();
 358
 359     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
 360     // we overflow or not.
 361     if (hasOverflowClip())
 362         layer()->scrollableArea()->updateAfterLayout();
 363
 364     clearNeedsLayout();
 365 }
 366
 367 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
 368 {
 369     const_cast<RenderGrid*>(this)->placeItemsOnGrid();
 370
 371     GridSizingData sizingData(gridColumnCount(), gridRowCount());
 372     LayoutUnit availableLogicalSpace = 0;
 373     const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace);
 374
 375     for (size_t i = 0; i < sizingData.columnTracks.size(); ++i) {
 376         LayoutUnit minTrackBreadth = sizingData.columnTracks[i].m_usedBreadth;
 377         LayoutUnit maxTrackBreadth = sizingData.columnTracks[i].m_maxBreadth;
 378         maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth);
 379
 380         minLogicalWidth += minTrackBreadth;
 381         maxLogicalWidth += maxTrackBreadth;
 382
 383         // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
 384     }
 385 }
 386
 387 void RenderGrid::computePreferredLogicalWidths()
 388 {
 389     ASSERT(preferredLogicalWidthsDirty());
 390
 391     m_minPreferredLogicalWidth = 0;
 392     m_maxPreferredLogicalWidth = 0;
 393
 394     // FIXME: We don't take our own logical width into account. Once we do, we need to make sure
 395     // we apply (and test the interaction with) min-width / max-width.
 396
 397     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
 398
 399     LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
 400     m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
 401     m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
 402
 403     clearPreferredLogicalWidthsDirty();
 404 }
 405
 406 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData)
 407 {
 408     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
 409     computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace);
 410 }
 411
 412 bool RenderGrid::gridElementIsShrinkToFit()
 413 {
 414     return isFloatingOrOutOfFlowPositioned();
 415 }
 416
 417 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 418 {
 419     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
 420     Vector<size_t> flexibleSizedTracksIndex;
 421     sizingData.contentSizedTracksIndex.shrink(0);
 422
 423     // 1. Initialize per Grid track variables.
 424     for (size_t i = 0; i < tracks.size(); ++i) {
 425         GridTrack& track = tracks[i];
 426         GridTrackSize trackSize = gridTrackSize(direction, i);
 427         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
 428         const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
 429
 430         track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth);
 431         track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.m_usedBreadth);
 432
 433         if (track.m_maxBreadth != infinity)
 434             track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth);
 435
 436         if (trackSize.isContentSized())
 437             sizingData.contentSizedTracksIndex.append(i);
 438         if (trackSize.maxTrackBreadth().isFlex())
 439             flexibleSizedTracksIndex.append(i);
 440     }
 441
 442     // 2. Resolve content-based TrackSizingFunctions.
 443     if (!sizingData.contentSizedTracksIndex.isEmpty())
 444         resolveContentBasedTrackSizingFunctions(direction, sizingData, availableLogicalSpace);
 445
 446     for (size_t i = 0; i < tracks.size(); ++i) {
 447         ASSERT(tracks[i].m_maxBreadth != infinity);
 448         availableLogicalSpace -= tracks[i].m_usedBreadth;
 449     }
 450
 451     const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style()->logicalHeight().isAuto() : gridElementIsShrinkToFit();
 452
 453     if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0)
 454         return;
 455
 456     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until
 457     // availableLogicalSpace (RemainingSpace in the specs) is exhausted.
 458     const size_t tracksSize = tracks.size();
 459     if (!hasUndefinedRemainingSpace) {
 460         Vector<GridTrack*> tracksForDistribution(tracksSize);
 461         for (size_t i = 0; i < tracksSize; ++i)
 462             tracksForDistribution[i] = tracks.data() + i;
 463
 464         distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, sizingData, availableLogicalSpace);
 465     } else {
 466         for (size_t i = 0; i < tracksSize; ++i)
 467             tracks[i].m_usedBreadth = tracks[i].m_maxBreadth;
 468     }
 469
 470     if (flexibleSizedTracksIndex.isEmpty())
 471         return;
 472
 473     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
 474     double normalizedFractionBreadth = 0;
 475     if (!hasUndefinedRemainingSpace) {
 476         normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, availableLogicalSpace);
 477     } else {
 478         for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
 479             const size_t trackIndex = flexibleSizedTracksIndex[i];
 480             GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
 481             normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].m_usedBreadth / trackSize.maxTrackBreadth().flex());
 482         }
 483
 484         for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
 485             GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
 486             while (RenderBox* gridItem = iterator.nextGridItem()) {
 487                 const GridCoordinate coordinate = cachedGridCoordinate(*gridItem);
 488                 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
 489
 490                 // Do not include already processed items.
 491                 if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1])
 492                     continue;
 493
 494                 double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData.columnTracks));
 495                 normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
 496             }
 497         }
 498     }
 499
 500     for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
 501         const size_t trackIndex = flexibleSizedTracksIndex[i];
 502         GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
 503
 504         tracks[trackIndex].m_usedBreadth = std::max<LayoutUnit>(tracks[trackIndex].m_usedBreadth, normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
 505     }
 506 }
 507
 508 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
 509 {
 510     if (gridLength.isFlex())
 511         return 0;
 512
 513     const Length& trackLength = gridLength.length();
 514     ASSERT(!trackLength.isAuto());
 515     if (trackLength.isSpecified())
 516         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
 517
 518     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
 519     return 0;
 520 }
 521
 522 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const
 523 {
 524     if (gridLength.isFlex())
 525         return usedBreadth;
 526
 527     const Length& trackLength = gridLength.length();
 528     ASSERT(!trackLength.isAuto());
 529     if (trackLength.isSpecified()) {
 530         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
 531         ASSERT(computedBreadth != infinity);
 532         return computedBreadth;
 533     }
 534
 535     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
 536     return infinity;
 537 }
 538
 539 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
 540 {
 541     ASSERT(trackLength.isSpecified());
 542     // FIXME: The -1 here should be replaced by whatever the intrinsic height of the grid is.
 543     return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style()->logicalHeight(), -1));
 544 }
 545
 546 static bool sortByGridNormalizedFlexValue(const GridTrackForNormalization& track1, const GridTrackForNormalization& track2)
 547 {
 548     return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
 549 }
 550
 551 double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit availableLogicalSpace) const
 552 {
 553     // |availableLogicalSpace| already accounts for the used breadths so no need to remove it here.
 554
 555     Vector<GridTrackForNormalization> tracksForNormalization;
 556     for (GridSpan::iterator resolvedPosition = tracksSpan.begin(); resolvedPosition != tracksSpan.end(); ++resolvedPosition) {
 557         GridTrackSize trackSize = gridTrackSize(direction, resolvedPosition.toInt());
 558         if (!trackSize.maxTrackBreadth().isFlex())
 559             continue;
 560
 561         tracksForNormalization.append(GridTrackForNormalization(tracks[resolvedPosition.toInt()], trackSize.maxTrackBreadth().flex()));
 562     }
 563
 564     // The function is not called if we don't have <flex> grid tracks
 565     ASSERT(!tracksForNormalization.isEmpty());
 566
 567     std::sort(tracksForNormalization.begin(), tracksForNormalization.end(), sortByGridNormalizedFlexValue);
 568
 569     // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
 570     // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
 571     // fit into availableLogicalSpaceIgnoringFractionTracks.
 572     double accumulatedFractions = 0;
 573     LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
 574     LayoutUnit availableLogicalSpaceIgnoringFractionTracks = availableLogicalSpace;
 575
 576     for (size_t i = 0; i < tracksForNormalization.size(); ++i) {
 577         const GridTrackForNormalization& track = tracksForNormalization[i];
 578         if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
 579             // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
 580             // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
 581             if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
 582                 break;
 583
 584             fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
 585         }
 586
 587         accumulatedFractions += track.m_flex;
 588         // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
 589         availableLogicalSpaceIgnoringFractionTracks += track.m_track->m_usedBreadth;
 590     }
 591
 592     return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
 593 }
 594
 595 GridTrackSize RenderGrid::gridTrackSize(GridTrackSizingDirection direction, size_t i) const
 596 {
 597     bool isForColumns = direction == ForColumns;
 598     const Vector<GridTrackSize>& trackStyles = isForColumns ? style()->gridTemplateColumns() : style()->gridTemplateRows();
 599     const GridTrackSize& trackSize = (i >= trackStyles.size()) ? (isForColumns ? style()->gridAutoColumns() : style()->gridAutoRows()) : trackStyles[i];
 600
 601     // If the logical width/height of the grid container is indefinite, percentage values are treated as <auto> (or in
 602     // the case of minmax() as min-content for the first position and max-content for the second).
 603     Length logicalSize = isForColumns ? style()->logicalWidth() : style()->logicalHeight();
 604     // FIXME: isIntrinsicOrAuto() does not fulfil the 'indefinite size' description as it does not include <percentage>
 605     // of indefinite sizes. This is a broather issue as Length does not have the required context to support it.
 606     if (logicalSize.isIntrinsicOrAuto()) {
 607         const GridLength& oldMinTrackBreadth = trackSize.minTrackBreadth();
 608         const GridLength& oldMaxTrackBreadth = trackSize.maxTrackBreadth();
 609         return GridTrackSize(oldMinTrackBreadth.isPercentage() ? Length(MinContent) : oldMinTrackBreadth, oldMaxTrackBreadth.isPercentage() ? Length(MaxContent) : oldMaxTrackBreadth);
 610     }
 611
 612     return trackSize;
 613 }
 614
 615 LayoutUnit RenderGrid::logicalHeightForChild(RenderBox& child, Vector<GridTrack>& columnTracks)
 616 {
 617     SubtreeLayoutScope layoutScope(child);
 618     LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child.hasOverrideContainingBlockLogicalWidth() ? child.overrideContainingBlockContentLogicalWidth() : LayoutUnit();
 619     LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
 620     if (child.style()->logicalHeight().isPercent() || oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth)
 621         layoutScope.setNeedsLayout(&child);
 622
 623     child.setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
 624     // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is
 625     // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution).
 626     child.setOverrideContainingBlockContentLogicalHeight(-1);
 627     child.layoutIfNeeded();
 628     return child.logicalHeight() + child.marginLogicalHeight();
 629 }
 630
 631 LayoutUnit RenderGrid::minContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
 632 {
 633     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
 634     // FIXME: Properly support orthogonal writing mode.
 635     if (hasOrthogonalWritingMode)
 636         return 0;
 637
 638     if (direction == ForColumns) {
 639         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
 640         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
 641         return child.minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(&child);
 642     }
 643
 644     return logicalHeightForChild(child, columnTracks);
 645 }
 646
 647 LayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
 648 {
 649     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
 650     // FIXME: Properly support orthogonal writing mode.
 651     if (hasOrthogonalWritingMode)
 652         return LayoutUnit();
 653
 654     if (direction == ForColumns) {
 655         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
 656         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
 657         return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(&child);
 658     }
 659
 660     return logicalHeightForChild(child, columnTracks);
 661 }
 662
 663 size_t RenderGrid::gridItemSpan(const RenderBox& child, GridTrackSizingDirection direction)
 664 {
 665     GridCoordinate childCoordinate = cachedGridCoordinate(child);
 666     GridSpan childSpan = (direction == ForRows) ? childCoordinate.rows : childCoordinate.columns;
 667
 668     return childSpan.resolvedFinalPosition.toInt() - childSpan.resolvedInitialPosition.toInt() + 1;
 669 }
 670
 671 typedef std::pair<RenderBox*, size_t> GridItemWithSpan;
 672
 673 // This function sorts by span (.second in the pair) but also places pointers (.first in the pair) to the same object in
 674 // consecutive positions so duplicates could be easily removed with std::unique() for example.
 675 static bool gridItemWithSpanSorter(const GridItemWithSpan& item1, const GridItemWithSpan& item2)
 676 {
 677     if (item1.second != item2.second)
 678         return item1.second < item2.second;
 679
 680     return item1.first < item2.first;
 681 }
 682
 683 static bool uniquePointerInPair(const GridItemWithSpan& item1, const GridItemWithSpan& item2)
 684 {
 685     return item1.first == item2.first;
 686 }
 687
 688 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 689 {
 690     // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track (crbug.com/235258).
 691
 692     for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
 693         size_t trackIndex = sizingData.contentSizedTracksIndex[i];
 694         GridIterator iterator(m_grid, direction, trackIndex);
 695         Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
 696
 697         while (RenderBox* gridItem = iterator.nextGridItem())
 698             itemsSortedByIncreasingSpan.append(std::make_pair(gridItem, gridItemSpan(*gridItem, direction)));
 699         std::stable_sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), gridItemWithSpanSorter);
 700         Vector<GridItemWithSpan>::iterator end = std::unique(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), uniquePointerInPair);
 701
 702         for (Vector<GridItemWithSpan>::iterator it = itemsSortedByIncreasingSpan.begin(); it != end; ++it) {
 703             RenderBox* gridItem = it->first;
 704             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
 705             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
 706             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
 707             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
 708         }
 709
 710         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
 711         if (track.m_maxBreadth == infinity)
 712             track.m_maxBreadth = track.m_usedBreadth;
 713     }
 714 }
 715
 716 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, RenderBox& gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
 717 {
 718     const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
 719     const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
 720     const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
 721
 722     sizingData.filteredTracks.shrink(0);
 723     for (GridResolvedPosition trackPosition = initialTrackPosition; trackPosition <= finalTrackPosition; ++trackPosition) {
 724         GridTrackSize trackSize = gridTrackSize(direction, trackPosition.toInt());
 725         if (!(trackSize.*filterFunction)())
 726             continue;
 727
 728         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPosition.toInt()] : sizingData.rowTracks[trackPosition.toInt()];
 729         sizingData.filteredTracks.append(&track);
 730     }
 731
 732     if (sizingData.filteredTracks.isEmpty())
 733         return;
 734
 735     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks);
 736     for (GridResolvedPosition trackIndexForSpace = initialTrackPosition; trackIndexForSpace <= finalTrackPosition; ++trackIndexForSpace) {
 737         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndexForSpace.toInt()] : sizingData.rowTracks[trackIndexForSpace.toInt()];
 738         additionalBreadthSpace -= (track.*trackGetter)();
 739     }
 740
 741     // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
 742
 743     // Specs mandate to floor additionalBreadthSpace (extra-space in specs) to 0. Instead we directly avoid the function
 744     // call in those cases as it will be a noop in terms of track sizing.
 745     if (additionalBreadthSpace > 0)
 746         distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.filteredTracks, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
 747 }
 748
 749 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
 750 {
 751     // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
 752     // (forall x: NOT x < x).
 753     if (track1->m_maxBreadth == infinity && track2->m_maxBreadth == infinity)
 754         return false;
 755
 756     if (track1->m_maxBreadth == infinity || track2->m_maxBreadth == infinity)
 757         return track2->m_maxBreadth == infinity;
 758
 759     return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
 760 }
 761
 762 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 763 {
 764     ASSERT(availableLogicalSpace > 0);
 765     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
 766
 767     size_t tracksSize = tracks.size();
 768     sizingData.distributeTrackVector.resize(tracksSize);
 769
 770     for (size_t i = 0; i < tracksSize; ++i) {
 771         GridTrack& track = *tracks[i];
 772         LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
 773         LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
 774         LayoutUnit growthShare = track.m_maxBreadth == infinity ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth);
 775         ASSERT(growthShare != infinity);
 776         sizingData.distributeTrackVector[i] = trackBreadth;
 777         // We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function.
 778         if (growthShare > 0) {
 779             sizingData.distributeTrackVector[i] += growthShare;
 780             availableLogicalSpace -= growthShare;
 781         }
 782     }
 783
 784     if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) {
 785         tracksSize = tracksForGrowthAboveMaxBreadth->size();
 786         for (size_t i = 0; i < tracksSize; ++i) {
 787             LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
 788             sizingData.distributeTrackVector[i] += growthShare;
 789             availableLogicalSpace -= growthShare;
 790         }
 791     }
 792
 793     for (size_t i = 0; i < tracksSize; ++i) {
 794         LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
 795         if (growth >= 0)
 796             (tracks[i]->*trackGrowthFunction)(growth);
 797     }
 798 }
 799
 800 #if ENABLE(ASSERT)
 801 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
 802 {
 803     for (size_t i = 0; i < tracks.size(); ++i) {
 804         GridTrackSize trackSize = gridTrackSize(direction, i);
 805         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
 806         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth)
 807             return false;
 808     }
 809     return true;
 810 }
 811 #endif
 812
 813 void RenderGrid::ensureGridSize(size_t maximumRowIndex, size_t maximumColumnIndex)
 814 {
 815     const size_t oldRowSize = gridRowCount();
 816     if (maximumRowIndex >= oldRowSize) {
 817         m_grid.grow(maximumRowIndex + 1);
 818         for (size_t row = oldRowSize; row < gridRowCount(); ++row)
 819             m_grid[row].grow(gridColumnCount());
 820     }
 821
 822     if (maximumColumnIndex >= gridColumnCount()) {
 823         for (size_t row = 0; row < gridRowCount(); ++row)
 824             m_grid[row].grow(maximumColumnIndex + 1);
 825     }
 826 }
 827
 828 void RenderGrid::insertItemIntoGrid(RenderBox& child, const GridCoordinate& coordinate)
 829 {
 830     ensureGridSize(coordinate.rows.resolvedFinalPosition.toInt(), coordinate.columns.resolvedFinalPosition.toInt());
 831
 832     for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) {
 833         for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column)
 834             m_grid[row.toInt()][column.toInt()].append(&child);
 835     }
 836
 837     RELEASE_ASSERT(!m_gridItemCoordinate.contains(&child));
 838     m_gridItemCoordinate.set(&child, coordinate);
 839 }
 840
 841 void RenderGrid::placeItemsOnGrid()
 842 {
 843     if (!gridIsDirty())
 844         return;
 845
 846     ASSERT(m_gridItemCoordinate.isEmpty());
 847
 848     populateExplicitGridAndOrderIterator();
 849
 850     // We clear the dirty bit here as the grid sizes have been updated, this means
 851     // that we can safely call gridRowCount() / gridColumnCount().
 852     m_gridIsDirty = false;
 853
 854     Vector<RenderBox*> autoMajorAxisAutoGridItems;
 855     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
 856     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
 857         // FIXME: We never re-resolve positions if the grid is grown during auto-placement which may lead auto / <integer>
 858         // positions to not match the author's intent. The specification is unclear on what should be done in this case.
 859         OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows);
 860         OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns);
 861         if (!rowPositions || !columnPositions) {
 862             GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get();
 863             if (!majorAxisPositions)
 864                 autoMajorAxisAutoGridItems.append(child);
 865             else
 866                 specifiedMajorAxisAutoGridItems.append(child);
 867             continue;
 868         }
 869         insertItemIntoGrid(*child, GridCoordinate(*rowPositions, *columnPositions));
 870     }
 871
 872     ASSERT(gridRowCount() >= style()->gridTemplateRows().size());
 873     ASSERT(gridColumnCount() >= style()->gridTemplateColumns().size());
 874
 875     // FIXME: Implement properly "stack" value in auto-placement algorithm.
 876     if (style()->isGridAutoFlowAlgorithmStack()) {
 877         // If we did collect some grid items, they won't be placed thus never laid out.
 878         ASSERT(!autoMajorAxisAutoGridItems.size());
 879         ASSERT(!specifiedMajorAxisAutoGridItems.size());
 880         return;
 881     }
 882
 883     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
 884     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
 885
 886     m_grid.shrinkToFit();
 887 }
 888
 889 void RenderGrid::populateExplicitGridAndOrderIterator()
 890 {
 891     OrderIteratorPopulator populator(m_orderIterator);
 892
 893     size_t maximumRowIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridRowCount(*style()));
 894     size_t maximumColumnIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridColumnCount(*style()));
 895
 896     ASSERT(m_gridItemsIndexesMap.isEmpty());
 897     size_t childIndex = 0;
 898     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
 899         populator.collectChild(child);
 900         m_gridItemsIndexesMap.set(child, childIndex++);
 901
 902         // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
 903         OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows);
 904         OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns);
 905
 906         // |positions| is 0 if we need to run the auto-placement algorithm.
 907         if (rowPositions) {
 908             maximumRowIndex = std::max<size_t>(maximumRowIndex, rowPositions->resolvedFinalPosition.next().toInt());
 909         } else {
 910             // Grow the grid for items with a definite row span, getting the largest such span.
 911             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForRows, GridResolvedPosition(0));
 912             maximumRowIndex = std::max<size_t>(maximumRowIndex, positions.resolvedFinalPosition.next().toInt());
 913         }
 914
 915         if (columnPositions) {
 916             maximumColumnIndex = std::max<size_t>(maximumColumnIndex, columnPositions->resolvedFinalPosition.next().toInt());
 917         } else {
 918             // Grow the grid for items with a definite column span, getting the largest such span.
 919             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForColumns, GridResolvedPosition(0));
 920             maximumColumnIndex = std::max<size_t>(maximumColumnIndex, positions.resolvedFinalPosition.next().toInt());
 921         }
 922     }
 923
 924     m_grid.grow(maximumRowIndex);
 925     for (size_t i = 0; i < m_grid.size(); ++i)
 926         m_grid[i].grow(maximumColumnIndex);
 927 }
 928
 929 PassOwnPtr<GridCoordinate> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox& gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
 930 {
 931     GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
 932     const size_t endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount();
 933     GridSpan crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection));
 934     return adoptPtr(new GridCoordinate(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions));
 935 }
 936
 937 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 938 {
 939     for (size_t i = 0; i < autoGridItems.size(); ++i) {
 940         OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *autoGridItems[i], autoPlacementMajorAxisDirection());
 941         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *autoGridItems[i], autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
 942
 943         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt());
 944         OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->integerSpan(), minorAxisPositions.integerSpan());
 945         if (!emptyGridArea)
 946             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(*autoGridItems[i], autoPlacementMajorAxisDirection(), *majorAxisPositions);
 947         insertItemIntoGrid(*autoGridItems[i], *emptyGridArea);
 948     }
 949 }
 950
 951 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 952 {
 953     std::pair<size_t, size_t> autoPlacementCursor = std::make_pair(0, 0);
 954     bool isGridAutoFlowDense = style()->isGridAutoFlowAlgorithmDense();
 955
 956     for (size_t i = 0; i < autoGridItems.size(); ++i) {
 957         placeAutoMajorAxisItemOnGrid(*autoGridItems[i], autoPlacementCursor);
 958
 959         // If grid-auto-flow is dense, reset auto-placement cursor.
 960         if (isGridAutoFlowDense) {
 961             autoPlacementCursor.first = 0;
 962             autoPlacementCursor.second = 0;
 963         }
 964     }
 965 }
 966
 967 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox& gridItem, std::pair<size_t, size_t>& autoPlacementCursor)
 968 {
 969     OwnPtr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), gridItem, autoPlacementMinorAxisDirection());
 970     ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(*style(), gridItem, autoPlacementMajorAxisDirection()));
 971     GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(0));
 972
 973     const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
 974     size_t majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
 975     size_t minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
 976
 977     OwnPtr<GridCoordinate> emptyGridArea;
 978     if (minorAxisPositions) {
 979         // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
 980         if (minorAxisPositions->resolvedInitialPosition.toInt() < minorAxisAutoPlacementCursor)
 981             majorAxisAutoPlacementCursor++;
 982
 983         if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
 984             GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions->resolvedInitialPosition.toInt(), majorAxisAutoPlacementCursor);
 985             emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->integerSpan(), majorAxisPositions.integerSpan());
 986         }
 987
 988         if (!emptyGridArea)
 989             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
 990     } else {
 991         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
 992
 993         for (size_t majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
 994             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
 995             emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan());
 996
 997             if (emptyGridArea) {
 998                 // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
 999                 GridResolvedPosition minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.resolvedFinalPosition : emptyGridArea->rows.resolvedFinalPosition;
1000                 const size_t endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount();
1001                 if (minorAxisFinalPositionIndex.toInt() < endOfMinorAxis)
1002                     break;
1003
1004                 // Discard empty grid area as it does not fit in the minor axis direction.
1005                 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
1006                 emptyGridArea = nullptr;
1007             }
1008
1009             // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
1010             minorAxisAutoPlacementCursor = 0;
1011         }
1012
1013         if (!emptyGridArea)
1014             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
1015     }
1016
1017     insertItemIntoGrid(gridItem, *emptyGridArea);
1018     // Move auto-placement cursor to the new position.
1019     autoPlacementCursor.first = emptyGridArea->rows.resolvedInitialPosition.toInt();
1020     autoPlacementCursor.second = emptyGridArea->columns.resolvedInitialPosition.toInt();
1021 }
1022
1023 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
1024 {
1025     return style()->isGridAutoFlowDirectionColumn() ? ForColumns : ForRows;
1026 }
1027
1028 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
1029 {
1030     return style()->isGridAutoFlowDirectionColumn() ? ForRows : ForColumns;
1031 }
1032
1033 void RenderGrid::dirtyGrid()
1034 {
1035     m_grid.resize(0);
1036     m_gridItemCoordinate.clear();
1037     m_gridIsDirty = true;
1038     m_gridItemsOverflowingGridArea.resize(0);
1039     m_gridItemsIndexesMap.clear();
1040 }
1041
1042 void RenderGrid::layoutGridItems()
1043 {
1044     placeItemsOnGrid();
1045
1046     GridSizingData sizingData(gridColumnCount(), gridRowCount());
1047     computeUsedBreadthOfGridTracks(ForColumns, sizingData);
1048     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
1049     computeUsedBreadthOfGridTracks(ForRows, sizingData);
1050     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
1051
1052     populateGridPositions(sizingData);
1053     m_gridItemsOverflowingGridArea.resize(0);
1054
1055     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1056         // Because the grid area cannot be styled, we don't need to adjust
1057         // the grid breadth to account for 'box-sizing'.
1058         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
1059         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
1060
1061         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(*child, ForColumns, sizingData.columnTracks);
1062         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(*child, ForRows, sizingData.rowTracks);
1063
1064         SubtreeLayoutScope layoutScope(*child);
1065         if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && child->hasRelativeLogicalHeight()))
1066             layoutScope.setNeedsLayout(child);
1067
1068         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
1069         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
1070
1071         // FIXME: Grid items should stretch to fill their cells. Once we
1072         // implement grid-{column,row}-align, we can also shrink to fit. For
1073         // now, just size as if we were a regular child.
1074         child->layoutIfNeeded();
1075
1076 #if ENABLE(ASSERT)
1077         const GridCoordinate& coordinate = cachedGridCoordinate(*child);
1078         ASSERT(coordinate.columns.resolvedInitialPosition.toInt() < sizingData.columnTracks.size());
1079         ASSERT(coordinate.rows.resolvedInitialPosition.toInt() < sizingData.rowTracks.size());
1080 #endif
1081         child->setLogicalLocation(findChildLogicalPosition(*child));
1082
1083         // Keep track of children overflowing their grid area as we might need to paint them even if the grid-area is
1084         // not visible
1085         if (child->logicalHeight() > overrideContainingBlockContentLogicalHeight
1086             || child->logicalWidth() > overrideContainingBlockContentLogicalWidth)
1087             m_gridItemsOverflowingGridArea.append(child);
1088     }
1089
1090     for (size_t i = 0; i < sizingData.rowTracks.size(); ++i)
1091         setLogicalHeight(logicalHeight() + sizingData.rowTracks[i].m_usedBreadth);
1092
1093     // Min / max logical height is handled by the call to updateLogicalHeight in layoutBlock.
1094
1095     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
1096 }
1097
1098 GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox& gridItem) const
1099 {
1100     ASSERT(m_gridItemCoordinate.contains(&gridItem));
1101     return m_gridItemCoordinate.get(&gridItem);
1102 }
1103
1104 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
1105 {
1106     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1107     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
1108     LayoutUnit gridAreaBreadth = 0;
1109     for (GridSpan::iterator trackPosition = span.begin(); trackPosition != span.end(); ++trackPosition)
1110         gridAreaBreadth += tracks[trackPosition.toInt()].m_usedBreadth;
1111     return gridAreaBreadth;
1112 }
1113
1114 void RenderGrid::populateGridPositions(const GridSizingData& sizingData)
1115 {
1116     m_columnPositions.resize(sizingData.columnTracks.size() + 1);
1117     m_columnPositions[0] = borderAndPaddingStart();
1118     for (size_t i = 0; i < m_columnPositions.size() - 1; ++i)
1119         m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].m_usedBreadth;
1120
1121     m_rowPositions.resize(sizingData.rowTracks.size() + 1);
1122     m_rowPositions[0] = borderAndPaddingBefore();
1123     for (size_t i = 0; i < m_rowPositions.size() - 1; ++i)
1124         m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].m_usedBreadth;
1125 }
1126
1127 LayoutUnit RenderGrid::startOfColumnForChild(const RenderBox& child) const
1128 {
1129     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1130     LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
1131     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1132     // FIXME: This should account for the grid item's <overflow-position>.
1133     return startOfColumn + marginStartForChild(&child);
1134 }
1135
1136 LayoutUnit RenderGrid::endOfColumnForChild(const RenderBox& child) const
1137 {
1138     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1139     LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
1140     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1141     LayoutUnit columnPosition = startOfColumn + marginStartForChild(&child);
1142
1143     LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()];
1144     // FIXME: This should account for the grid item's <overflow-position>.
1145     return columnPosition + std::max<LayoutUnit>(0, endOfColumn - m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()] - child.logicalWidth());
1146 }
1147
1148 LayoutUnit RenderGrid::columnPositionAlignedWithGridContainerStart(const RenderBox& child) const
1149 {
1150     if (style()->isLeftToRightDirection())
1151         return startOfColumnForChild(child);
1152
1153     return endOfColumnForChild(child);
1154 }
1155
1156 LayoutUnit RenderGrid::columnPositionAlignedWithGridContainerEnd(const RenderBox& child) const
1157 {
1158     if (!style()->isLeftToRightDirection())
1159         return startOfColumnForChild(child);
1160
1161     return endOfColumnForChild(child);
1162 }
1163
1164 LayoutUnit RenderGrid::centeredColumnPositionForChild(const RenderBox& child) const
1165 {
1166     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1167     LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
1168     LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()];
1169     LayoutUnit columnPosition = startOfColumn + marginStartForChild(&child);
1170     // FIXME: This should account for the grid item's <overflow-position>.
1171     return columnPosition + std::max<LayoutUnit>(0, endOfColumn - startOfColumn - child.logicalWidth()) / 2;
1172 }
1173
1174 static ItemPosition resolveJustification(const RenderStyle* parentStyle, const RenderStyle* childStyle)
1175 {
1176     ItemPosition justify = childStyle->justifySelf();
1177     if (justify == ItemPositionAuto)
1178         justify = (parentStyle->justifyItems() == ItemPositionAuto) ? ItemPositionStretch : parentStyle->justifyItems();
1179
1180     return justify;
1181 }
1182
1183 LayoutUnit RenderGrid::columnPositionForChild(const RenderBox& child) const
1184 {
1185     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
1186
1187     switch (resolveJustification(style(), child.style())) {
1188     case ItemPositionSelfStart:
1189         // For orthogonal writing-modes, this computes to 'start'
1190         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1191         if (hasOrthogonalWritingMode)
1192             return columnPositionAlignedWithGridContainerStart(child);
1193
1194         // self-start is based on the child's direction. That's why we need to check against the grid container's direction.
1195         if (child.style()->direction() != style()->direction())
1196             return columnPositionAlignedWithGridContainerEnd(child);
1197
1198         return columnPositionAlignedWithGridContainerStart(child);
1199     case ItemPositionSelfEnd:
1200         // For orthogonal writing-modes, this computes to 'start'
1201         // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
1202         if (hasOrthogonalWritingMode)
1203             return columnPositionAlignedWithGridContainerEnd(child);
1204
1205         // self-end is based on the child's direction. That's why we need to check against the grid container's direction.
1206         if (child.style()->direction() != style()->direction())
1207             return columnPositionAlignedWithGridContainerStart(child);
1208
1209         return columnPositionAlignedWithGridContainerEnd(child);
1210
1211     case ItemPositionFlexStart:
1212         // Only used in flex layout, for other layout, it's equivalent to 'start'.
1213         return columnPositionAlignedWithGridContainerStart(child);
1214     case ItemPositionFlexEnd:
1215         // Only used in flex layout, for other layout, it's equivalent to 'start'.
1216         return columnPositionAlignedWithGridContainerEnd(child);
1217
1218     case ItemPositionLeft:
1219         // If the property's axis is not parallel with the inline axis, this is equivalent to ‘start’.
1220         if (!isHorizontalWritingMode())
1221             return columnPositionAlignedWithGridContainerStart(child);
1222
1223         if (style()->isLeftToRightDirection())
1224             return columnPositionAlignedWithGridContainerStart(child);
1225
1226         return columnPositionAlignedWithGridContainerEnd(child);
1227     case ItemPositionRight:
1228         // If the property's axis is not parallel with the inline axis, this is equivalent to ‘start’.
1229         if (!isHorizontalWritingMode())
1230             return columnPositionAlignedWithGridContainerStart(child);
1231
1232         if (style()->isLeftToRightDirection())
1233             return columnPositionAlignedWithGridContainerEnd(child);
1234
1235         return columnPositionAlignedWithGridContainerStart(child);
1236
1237     case ItemPositionCenter:
1238         return centeredColumnPositionForChild(child);
1239     case ItemPositionStart:
1240         return columnPositionAlignedWithGridContainerStart(child);
1241     case ItemPositionEnd:
1242         return columnPositionAlignedWithGridContainerEnd(child);
1243
1244     case ItemPositionAuto:
1245         break;
1246     case ItemPositionStretch:
1247     case ItemPositionBaseline:
1248     case ItemPositionLastBaseline:
1249         // FIXME: Implement the previous values. For now, we always start align the child.
1250         return startOfColumnForChild(child);
1251     }
1252
1253     ASSERT_NOT_REACHED();
1254     return 0;
1255 }
1256
1257 LayoutUnit RenderGrid::endOfRowForChild(const RenderBox& child) const
1258 {
1259     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1260
1261     LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()];
1262     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1263     LayoutUnit rowPosition = startOfRow + marginBeforeForChild(&child);
1264
1265     LayoutUnit endOfRow = m_rowPositions[coordinate.rows.resolvedFinalPosition.next().toInt()];
1266     // FIXME: This should account for the grid item's <overflow-position>.
1267     return rowPosition + std::max<LayoutUnit>(0, endOfRow - startOfRow - child.logicalHeight());
1268 }
1269
1270 LayoutUnit RenderGrid::startOfRowForChild(const RenderBox& child) const
1271 {
1272     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1273
1274     LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()];
1275     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1276     // FIXME: This should account for the grid item's <overflow-position>.
1277     LayoutUnit rowPosition = startOfRow + marginBeforeForChild(&child);
1278
1279     return rowPosition;
1280 }
1281
1282 LayoutUnit RenderGrid::centeredRowPositionForChild(const RenderBox& child) const
1283 {
1284     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1285
1286     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1287     LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()] + marginBeforeForChild(&child);
1288     LayoutUnit endOfRow = m_rowPositions[coordinate.rows.resolvedFinalPosition.next().toInt()];
1289
1290     // FIXME: This should account for the grid item's <overflow-position>.
1291     return startOfRow + std::max<LayoutUnit>(0, endOfRow - startOfRow - child.logicalHeight()) / 2;
1292 }
1293
1294 // FIXME: We should move this logic to the StyleAdjuster or the StyleBuilder.
1295 static ItemPosition resolveAlignment(const RenderStyle* parentStyle, const RenderStyle* childStyle)
1296 {
1297     ItemPosition align = childStyle->alignSelf();
1298     // The auto keyword computes to the parent's align-items computed value, or to "stretch", if not set or "auto".
1299     if (align == ItemPositionAuto)
1300         align = (parentStyle->alignItems() == ItemPositionAuto) ? ItemPositionStretch : parentStyle->alignItems();
1301     return align;
1302 }
1303
1304 LayoutUnit RenderGrid::rowPositionForChild(const RenderBox& child) const
1305 {
1306     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
1307     ItemPosition alignSelf = resolveAlignment(style(), child.style());
1308
1309     switch (alignSelf) {
1310     case ItemPositionSelfStart:
1311         // If orthogonal writing-modes, this computes to 'Start'.
1312         // FIXME: grid track sizing and positioning does not support orthogonal modes yet.
1313         if (hasOrthogonalWritingMode)
1314             return startOfRowForChild(child);
1315
1316         // self-start is based on the child's block axis direction. That's why we need to check against the grid container's block flow.
1317         if (child.style()->writingMode() != style()->writingMode())
1318             return endOfRowForChild(child);
1319
1320         return startOfRowForChild(child);
1321     case ItemPositionSelfEnd:
1322         // If orthogonal writing-modes, this computes to 'End'.
1323         // FIXME: grid track sizing and positioning does not support orthogonal modes yet.
1324         if (hasOrthogonalWritingMode)
1325             return endOfRowForChild(child);
1326
1327         // self-end is based on the child's block axis direction. That's why we need to check against the grid container's block flow.
1328         if (child.style()->writingMode() != style()->writingMode())
1329             return startOfRowForChild(child);
1330
1331         return endOfRowForChild(child);
1332
1333     case ItemPositionLeft:
1334         // orthogonal modes make property and inline axes to be parallel, but in any case
1335         // this is always equivalent to 'Start'.
1336         //
1337         // self-align's axis is never parallel to the inline axis, except in orthogonal
1338         // writing-mode, so this is equivalent to 'Start’.
1339         return startOfRowForChild(child);
1340
1341     case ItemPositionRight:
1342         // orthogonal modes make property and inline axes to be parallel.
1343         // FIXME: grid track sizing and positioning does not support orthogonal modes yet.
1344         if (hasOrthogonalWritingMode)
1345             return endOfRowForChild(child);
1346
1347         // self-align's axis is never parallel to the inline axis, except in orthogonal
1348         // writing-mode, so this is equivalent to 'Start'.
1349         return startOfRowForChild(child);
1350
1351     case ItemPositionCenter:
1352         return centeredRowPositionForChild(child);
1353         // Only used in flex layout, for other layout, it's equivalent to 'Start'.
1354     case ItemPositionFlexStart:
1355     case ItemPositionStart:
1356         return startOfRowForChild(child);
1357         // Only used in flex layout, for other layout, it's equivalent to 'End'.
1358     case ItemPositionFlexEnd:
1359     case ItemPositionEnd:
1360         return endOfRowForChild(child);
1361     case ItemPositionStretch:
1362         // FIXME: Implement the Stretch value. For now, we always start align the child.
1363         return startOfRowForChild(child);
1364     case ItemPositionBaseline:
1365     case ItemPositionLastBaseline:
1366         // FIXME: Implement the ItemPositionBaseline value. For now, we always start align the child.
1367         return startOfRowForChild(child);
1368     case ItemPositionAuto:
1369         break;
1370     }
1371
1372     ASSERT_NOT_REACHED();
1373     return 0;
1374 }
1375
1376 LayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox& child) const
1377 {
1378     return LayoutPoint(columnPositionForChild(child), rowPositionForChild(child));
1379 }
1380
1381 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
1382 {
1383     GridPainter(*this).paintChildren(paintInfo, paintOffset);
1384 }
1385
1386 const char* RenderGrid::renderName() const
1387 {
1388     if (isFloating())
1389         return "RenderGrid (floating)";
1390     if (isOutOfFlowPositioned())
1391         return "RenderGrid (positioned)";
1392     if (isAnonymous())
1393         return "RenderGrid (generated)";
1394     if (isRelPositioned())
1395         return "RenderGrid (relative positioned)";
1396     return "RenderGrid";
1397 }
1398
1399 } // namespace blink