Source/WebCore/rendering/RenderGrid.cpp

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  * Copyright (C) 2013, 2014 Igalia S.L.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "config.h"
  28 #include "RenderGrid.h"
  29
  30 #if ENABLE(CSS_GRID_LAYOUT)
  31
  32 #include "GridCoordinate.h"
  33 #include "GridResolvedPosition.h"
  34 #include "LayoutRepainter.h"
  35 #include "RenderLayer.h"
  36 #include "RenderView.h"
  37 #include <wtf/NeverDestroyed.h>
  38
  39 namespace WebCore {
  40
  41 static const int infinity = -1;
  42
  43 class GridTrack {
  44 public:
  45     GridTrack() {}
  46
  47     const LayoutUnit& baseSize() const
  48     {
  49         ASSERT(isGrowthLimitBiggerThanBaseSize());
  50         return m_baseSize;
  51     }
  52
  53     const LayoutUnit& growthLimit() const
  54     {
  55         ASSERT(isGrowthLimitBiggerThanBaseSize());
  56         return m_growthLimit;
  57     }
  58
  59     void setBaseSize(LayoutUnit baseSize)
  60     {
  61         m_baseSize = baseSize;
  62         ensureGrowthLimitIsBiggerThanBaseSize();
  63     }
  64
  65     void setGrowthLimit(LayoutUnit growthLimit)
  66     {
  67         m_growthLimit = growthLimit;
  68         ensureGrowthLimitIsBiggerThanBaseSize();
  69     }
  70
  71     void growBaseSize(LayoutUnit growth)
  72     {
  73         ASSERT(growth >= 0);
  74         m_baseSize += growth;
  75         ensureGrowthLimitIsBiggerThanBaseSize();
  76     }
  77
  78     void growGrowthLimit(LayoutUnit growth)
  79     {
  80         ASSERT(growth >= 0);
  81         if (m_growthLimit == infinity)
  82             m_growthLimit = m_baseSize + growth;
  83         else
  84             m_growthLimit += growth;
  85
  86         ASSERT(m_growthLimit >= m_baseSize);
  87     }
  88
  89     bool growthLimitIsInfinite() const
  90     {
  91         return m_growthLimit == infinity;
  92     }
  93
  94     const LayoutUnit& growthLimitIfNotInfinite() const
  95     {
  96         ASSERT(isGrowthLimitBiggerThanBaseSize());
  97         return (m_growthLimit == infinity) ? m_baseSize : m_growthLimit;
  98     }
  99
 100 private:
 101     bool isGrowthLimitBiggerThanBaseSize() const { return growthLimitIsInfinite() || m_growthLimit >= m_baseSize; }
 102
 103     void ensureGrowthLimitIsBiggerThanBaseSize()
 104     {
 105         if (m_growthLimit != infinity && m_growthLimit < m_baseSize)
 106             m_growthLimit = m_baseSize;
 107     }
 108
 109     LayoutUnit m_baseSize { 0 };
 110     LayoutUnit m_growthLimit { 0 };
 111 };
 112
 113 struct GridTrackForNormalization {
 114     GridTrackForNormalization(const GridTrack& track, double flex)
 115         : m_track(&track)
 116         , m_flex(flex)
 117         , m_normalizedFlexValue(track.baseSize() / flex)
 118     {
 119     }
 120
 121     const GridTrack* m_track;
 122     double m_flex;
 123     LayoutUnit m_normalizedFlexValue;
 124 };
 125
 126 class RenderGrid::GridIterator {
 127     WTF_MAKE_NONCOPYABLE(GridIterator);
 128 public:
 129     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
 130     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
 131     GridIterator(const Vector<Vector<Vector<RenderBox*, 1>>>& grid, GridTrackSizingDirection direction, unsigned fixedTrackIndex, unsigned varyingTrackIndex = 0)
 132         : m_grid(grid)
 133         , m_direction(direction)
 134         , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
 135         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
 136         , m_childIndex(0)
 137     {
 138         ASSERT(m_rowIndex < m_grid.size());
 139         ASSERT(m_columnIndex < m_grid[0].size());
 140     }
 141
 142     RenderBox* nextGridItem()
 143     {
 144         if (!m_grid.size())
 145             return 0;
 146
 147         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
 148         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
 149         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
 150             const Vector<RenderBox*>& children = m_grid[m_rowIndex][m_columnIndex];
 151             if (m_childIndex < children.size())
 152                 return children[m_childIndex++];
 153
 154             m_childIndex = 0;
 155         }
 156         return 0;
 157     }
 158
 159     bool isEmptyAreaEnough(unsigned rowSpan, unsigned columnSpan) const
 160     {
 161         // Ignore cells outside current grid as we will grow it later if needed.
 162         unsigned maxRows = std::min<unsigned>(m_rowIndex + rowSpan, m_grid.size());
 163         unsigned maxColumns = std::min<unsigned>(m_columnIndex + columnSpan, m_grid[0].size());
 164
 165         // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
 166         for (unsigned row = m_rowIndex; row < maxRows; ++row) {
 167             for (unsigned column = m_columnIndex; column < maxColumns; ++column) {
 168                 const Vector<RenderBox*>& children = m_grid[row][column];
 169                 if (!children.isEmpty())
 170                     return false;
 171             }
 172         }
 173
 174         return true;
 175     }
 176
 177     std::unique_ptr<GridCoordinate> nextEmptyGridArea(unsigned fixedTrackSpan, unsigned varyingTrackSpan)
 178     {
 179         ASSERT(fixedTrackSpan >= 1 && varyingTrackSpan >= 1);
 180
 181         if (m_grid.isEmpty())
 182             return nullptr;
 183
 184         unsigned rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
 185         unsigned columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
 186
 187         unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
 188         const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
 189         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
 190             if (isEmptyAreaEnough(rowSpan, columnSpan)) {
 191                 std::unique_ptr<GridCoordinate> result = std::make_unique<GridCoordinate>(GridSpan(m_rowIndex, m_rowIndex + rowSpan - 1), GridSpan(m_columnIndex, m_columnIndex + columnSpan - 1));
 192                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
 193                 ++varyingTrackIndex;
 194                 return result;
 195             }
 196         }
 197         return nullptr;
 198     }
 199
 200 private:
 201     const Vector<Vector<Vector<RenderBox*, 1>>>& m_grid;
 202     GridTrackSizingDirection m_direction;
 203     unsigned m_rowIndex;
 204     unsigned m_columnIndex;
 205     unsigned m_childIndex;
 206 };
 207
 208 class RenderGrid::GridSizingData {
 209     WTF_MAKE_NONCOPYABLE(GridSizingData);
 210 public:
 211     GridSizingData(unsigned gridColumnCount, unsigned gridRowCount)
 212         : columnTracks(gridColumnCount)
 213         , rowTracks(gridRowCount)
 214     {
 215     }
 216
 217     Vector<GridTrack> columnTracks;
 218     Vector<GridTrack> rowTracks;
 219     Vector<unsigned> contentSizedTracksIndex;
 220
 221     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
 222     Vector<LayoutUnit> distributeTrackVector;
 223     Vector<GridTrack*> filteredTracks;
 224     Vector<unsigned> growAboveMaxBreadthTrackIndexes;
 225     Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
 226 };
 227
 228 RenderGrid::RenderGrid(Element& element, Ref<RenderStyle>&& style)
 229     : RenderBlock(element, WTF::move(style), 0)
 230     , m_orderIterator(*this)
 231 {
 232     // All of our children must be block level.
 233     setChildrenInline(false);
 234 }
 235
 236 RenderGrid::~RenderGrid()
 237 {
 238 }
 239
 240 void RenderGrid::layoutBlock(bool relayoutChildren, LayoutUnit)
 241 {
 242     ASSERT(needsLayout());
 243
 244     if (!relayoutChildren && simplifiedLayout())
 245         return;
 246
 247     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
 248     // It would be nice to refactor some of the duplicate code.
 249     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
 250     LayoutStateMaintainer statePusher(view(), *this, locationOffset(), hasTransform() || hasReflection() || style().isFlippedBlocksWritingMode());
 251
 252     preparePaginationBeforeBlockLayout(relayoutChildren);
 253
 254     LayoutSize previousSize = size();
 255
 256     setLogicalHeight(0);
 257     updateLogicalWidth();
 258
 259     layoutGridItems();
 260
 261     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
 262     updateLogicalHeight();
 263
 264     if (size() != previousSize)
 265         relayoutChildren = true;
 266
 267     layoutPositionedObjects(relayoutChildren || isRoot());
 268
 269     computeOverflow(oldClientAfterEdge);
 270     statePusher.pop();
 271
 272     updateLayerTransform();
 273
 274     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
 275     // we overflow or not.
 276     updateScrollInfoAfterLayout();
 277
 278     repainter.repaintAfterLayout();
 279
 280     clearNeedsLayout();
 281 }
 282
 283 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
 284 {
 285     bool wasPopulated = gridWasPopulated();
 286     if (!wasPopulated)
 287         const_cast<RenderGrid*>(this)->placeItemsOnGrid();
 288
 289     GridSizingData sizingData(gridColumnCount(), gridRowCount());
 290     LayoutUnit availableLogicalSpace = 0;
 291     const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace);
 292
 293     for (auto& column : sizingData.columnTracks) {
 294         LayoutUnit minTrackBreadth = column.baseSize();
 295         LayoutUnit maxTrackBreadth = column.growthLimit();
 296
 297         minLogicalWidth += minTrackBreadth;
 298         maxLogicalWidth += maxTrackBreadth;
 299
 300         // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
 301     }
 302
 303     if (!wasPopulated)
 304         const_cast<RenderGrid*>(this)->clearGrid();
 305 }
 306
 307 void RenderGrid::computePreferredLogicalWidths()
 308 {
 309     ASSERT(preferredLogicalWidthsDirty());
 310
 311     m_minPreferredLogicalWidth = 0;
 312     m_maxPreferredLogicalWidth = 0;
 313
 314     // FIXME: We don't take our own logical width into account. Once we do, we need to make sure
 315     // we apply (and test the interaction with) min-width / max-width.
 316
 317     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
 318
 319     LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
 320     m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
 321     m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
 322
 323     setPreferredLogicalWidthsDirty(false);
 324 }
 325
 326 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData)
 327 {
 328     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
 329     computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace);
 330 }
 331
 332 bool RenderGrid::gridElementIsShrinkToFit()
 333 {
 334     return isFloatingOrOutOfFlowPositioned();
 335 }
 336
 337 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 338 {
 339     const LayoutUnit initialAvailableLogicalSpace = availableLogicalSpace;
 340     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
 341     Vector<unsigned> flexibleSizedTracksIndex;
 342     sizingData.contentSizedTracksIndex.shrink(0);
 343
 344     // 1. Initialize per Grid track variables.
 345     for (unsigned i = 0; i < tracks.size(); ++i) {
 346         GridTrack& track = tracks[i];
 347         const GridTrackSize& trackSize = gridTrackSize(direction, i);
 348         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
 349         const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
 350
 351         track.setBaseSize(computeUsedBreadthOfMinLength(direction, minTrackBreadth));
 352         track.setGrowthLimit(computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.baseSize()));
 353
 354         if (trackSize.isContentSized())
 355             sizingData.contentSizedTracksIndex.append(i);
 356         if (trackSize.maxTrackBreadth().isFlex())
 357             flexibleSizedTracksIndex.append(i);
 358     }
 359
 360     // 2. Resolve content-based TrackSizingFunctions.
 361     if (!sizingData.contentSizedTracksIndex.isEmpty())
 362         resolveContentBasedTrackSizingFunctions(direction, sizingData);
 363
 364     for (auto& track : tracks) {
 365         ASSERT(!track.growthLimitIsInfinite());
 366         availableLogicalSpace -= track.baseSize();
 367     }
 368
 369     const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style().logicalHeight().isAuto() : gridElementIsShrinkToFit();
 370
 371     if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0)
 372         return;
 373
 374     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until availableLogicalSpace is exhausted.
 375     if (!hasUndefinedRemainingSpace) {
 376         const unsigned tracksSize = tracks.size();
 377         Vector<GridTrack*> tracksForDistribution(tracksSize);
 378         for (unsigned i = 0; i < tracksSize; ++i)
 379             tracksForDistribution[i] = tracks.data() + i;
 380
 381         distributeSpaceToTracks(tracksForDistribution, nullptr, &GridTrack::baseSize, &GridTrack::growBaseSize, sizingData, availableLogicalSpace);
 382     } else {
 383         for (auto& track : tracks)
 384             track.setBaseSize(track.growthLimit());
 385     }
 386
 387     if (flexibleSizedTracksIndex.isEmpty())
 388         return;
 389
 390     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
 391     double normalizedFractionBreadth = 0;
 392     if (!hasUndefinedRemainingSpace)
 393         normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, initialAvailableLogicalSpace);
 394     else {
 395         for (auto trackIndex : flexibleSizedTracksIndex) {
 396             const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
 397             normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].baseSize() / trackSize.maxTrackBreadth().flex());
 398         }
 399
 400         for (unsigned i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
 401             GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
 402             while (RenderBox* gridItem = iterator.nextGridItem()) {
 403                 const GridCoordinate coordinate = cachedGridCoordinate(*gridItem);
 404                 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
 405
 406                 // Do not include already processed items.
 407                 if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1])
 408                     continue;
 409
 410                 double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData.columnTracks));
 411                 normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
 412             }
 413         }
 414     }
 415
 416     for (auto trackIndex : flexibleSizedTracksIndex) {
 417         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
 418         GridTrack& track = tracks[trackIndex];
 419         LayoutUnit baseSize = std::max<LayoutUnit>(track.baseSize(), normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
 420         track.setBaseSize(baseSize);
 421         availableLogicalSpace -= baseSize;
 422     }
 423 }
 424
 425 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
 426 {
 427     if (gridLength.isFlex())
 428         return 0;
 429
 430     const Length& trackLength = gridLength.length();
 431     ASSERT(!trackLength.isAuto());
 432     if (trackLength.isSpecified())
 433         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
 434
 435     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
 436     return 0;
 437 }
 438
 439 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const
 440 {
 441     if (gridLength.isFlex())
 442         return usedBreadth;
 443
 444     const Length& trackLength = gridLength.length();
 445     ASSERT(!trackLength.isAuto());
 446     if (trackLength.isSpecified()) {
 447         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
 448         ASSERT(computedBreadth != infinity);
 449         return computedBreadth;
 450     }
 451
 452     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
 453     return infinity;
 454 }
 455
 456 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
 457 {
 458     ASSERT(trackLength.isSpecified());
 459     return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style().logicalHeight()));
 460 }
 461
 462 double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit spaceToFill) const
 463 {
 464     LayoutUnit allocatedSpace;
 465     Vector<GridTrackForNormalization> tracksForNormalization;
 466     for (auto& position : tracksSpan) {
 467         GridTrack& track = tracks[position.toInt()];
 468         allocatedSpace += track.baseSize();
 469
 470         const GridTrackSize& trackSize = gridTrackSize(direction, position.toInt());
 471         if (!trackSize.maxTrackBreadth().isFlex())
 472             continue;
 473
 474         tracksForNormalization.append(GridTrackForNormalization(track, trackSize.maxTrackBreadth().flex()));
 475     }
 476
 477     // The function is not called if we don't have <flex> grid tracks
 478     ASSERT(!tracksForNormalization.isEmpty());
 479
 480     std::sort(tracksForNormalization.begin(), tracksForNormalization.end(),
 481               [](const GridTrackForNormalization& track1, const GridTrackForNormalization& track2) {
 482                   return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
 483               });
 484
 485     // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
 486     // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
 487     // fit into availableLogicalSpaceIgnoringFractionTracks.
 488     double accumulatedFractions = 0;
 489     LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
 490     LayoutUnit availableLogicalSpaceIgnoringFractionTracks = spaceToFill - allocatedSpace;
 491
 492     for (auto& track : tracksForNormalization) {
 493         if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
 494             // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
 495             // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
 496             if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
 497                 break;
 498
 499             fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
 500         }
 501
 502         accumulatedFractions += track.m_flex;
 503         // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
 504         availableLogicalSpaceIgnoringFractionTracks += track.m_track->baseSize();
 505     }
 506
 507     return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
 508 }
 509
 510 GridTrackSize RenderGrid::gridTrackSize(GridTrackSizingDirection direction, unsigned i) const
 511 {
 512     bool isForColumns = (direction == ForColumns);
 513     auto& trackStyles =  isForColumns ? style().gridColumns() : style().gridRows();
 514     auto& trackSize = (i >= trackStyles.size()) ? (isForColumns ? style().gridAutoColumns() : style().gridAutoRows()) : trackStyles[i];
 515
 516     // If the logical width/height of the grid container is indefinite, percentage values are treated as <auto> (or in
 517     // the case of minmax() as min-content for the first position and max-content for the second).
 518     Length logicalSize = isForColumns ? style().logicalWidth() : style().logicalHeight();
 519     if (logicalSize.isIntrinsicOrAuto()) {
 520         const GridLength& oldMinTrackBreadth = trackSize.minTrackBreadth();
 521         const GridLength& oldMaxTrackBreadth = trackSize.maxTrackBreadth();
 522         return GridTrackSize(oldMinTrackBreadth.isPercentage() ? Length(MinContent) : oldMinTrackBreadth, oldMaxTrackBreadth.isPercentage() ? Length(MaxContent) : oldMaxTrackBreadth);
 523     }
 524
 525     return trackSize;
 526 }
 527
 528 LayoutUnit RenderGrid::logicalContentHeightForChild(RenderBox& child, Vector<GridTrack>& columnTracks)
 529 {
 530     LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child.hasOverrideContainingBlockLogicalWidth() ? child.overrideContainingBlockContentLogicalWidth() : LayoutUnit();
 531     LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
 532     if (child.style().logicalHeight().isPercent() || oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth)
 533         child.setNeedsLayout(MarkOnlyThis);
 534
 535     child.setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
 536     // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is
 537     // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution).
 538     child.setOverrideContainingBlockContentLogicalHeight(-1);
 539     child.layoutIfNeeded();
 540     return child.logicalHeight() + child.marginLogicalHeight();
 541 }
 542
 543 LayoutUnit RenderGrid::minContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
 544 {
 545     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
 546     // FIXME: Properly support orthogonal writing mode.
 547     if (hasOrthogonalWritingMode)
 548         return 0;
 549
 550     if (direction == ForColumns) {
 551         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
 552         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
 553         return child.minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
 554     }
 555
 556     return logicalContentHeightForChild(child, columnTracks);
 557 }
 558
 559 LayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
 560 {
 561     bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
 562     // FIXME: Properly support orthogonal writing mode.
 563     if (hasOrthogonalWritingMode)
 564         return LayoutUnit();
 565
 566     if (direction == ForColumns) {
 567         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
 568         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
 569         return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
 570     }
 571
 572     return logicalContentHeightForChild(child, columnTracks);
 573 }
 574
 575 class GridItemWithSpan {
 576 public:
 577     GridItemWithSpan(RenderBox& gridItem, GridCoordinate coordinate, GridTrackSizingDirection direction)
 578         : m_gridItem(gridItem)
 579         , m_coordinate(coordinate)
 580     {
 581         const GridSpan& span = (direction == ForRows) ? coordinate.rows : coordinate.columns;
 582         m_span = span.resolvedFinalPosition.toInt() - span.resolvedInitialPosition.toInt() + 1;
 583     }
 584
 585     RenderBox& gridItem() const { return m_gridItem; }
 586     GridCoordinate coordinate() const { return m_coordinate; }
 587 #if !ASSERT_DISABLED
 588     size_t span() const { return m_span; }
 589 #endif
 590
 591     bool operator<(const GridItemWithSpan other) const
 592     {
 593         return m_span < other.m_span;
 594     }
 595
 596 private:
 597     std::reference_wrapper<RenderBox> m_gridItem;
 598     GridCoordinate m_coordinate;
 599     unsigned m_span;
 600 };
 601
 602 bool RenderGrid::spanningItemCrossesFlexibleSizedTracks(const GridCoordinate& coordinate, GridTrackSizingDirection direction) const
 603 {
 604     const GridSpan itemSpan = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
 605     for (auto trackPosition : itemSpan) {
 606         const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition.toInt());
 607         if (trackSize.minTrackBreadth().isFlex() || trackSize.maxTrackBreadth().isFlex())
 608             return true;
 609     }
 610
 611     return false;
 612 }
 613
 614 static inline unsigned integerSpanForDirection(const GridCoordinate& coordinate, GridTrackSizingDirection direction)
 615 {
 616     return (direction == ForRows) ? coordinate.rows.integerSpan() : coordinate.columns.integerSpan();
 617 }
 618
 619 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData)
 620 {
 621     sizingData.itemsSortedByIncreasingSpan.shrink(0);
 622     HashSet<RenderBox*> itemsSet;
 623     for (auto trackIndex : sizingData.contentSizedTracksIndex) {
 624         GridIterator iterator(m_grid, direction, trackIndex);
 625         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
 626
 627         while (RenderBox* gridItem = iterator.nextGridItem()) {
 628             if (itemsSet.add(gridItem).isNewEntry) {
 629                 const GridCoordinate& coordinate = cachedGridCoordinate(*gridItem);
 630                 if (integerSpanForDirection(coordinate, direction) == 1)
 631                     resolveContentBasedTrackSizingFunctionsForNonSpanningItems(direction, coordinate, *gridItem, track, sizingData.columnTracks);
 632                 else if (!spanningItemCrossesFlexibleSizedTracks(coordinate, direction))
 633                     sizingData.itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, coordinate, direction));
 634             }
 635         }
 636     }
 637     std::sort(sizingData.itemsSortedByIncreasingSpan.begin(), sizingData.itemsSortedByIncreasingSpan.end());
 638
 639     for (auto& itemWithSpan : sizingData.itemsSortedByIncreasingSpan) {
 640         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::baseSize, &GridTrack::growBaseSize, &GridTrackSize::hasMinContentMinTrackBreadthAndMinOrMaxContentMaxTrackBreadth);
 641         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::baseSize, &GridTrack::growBaseSize, &GridTrackSize::hasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth);
 642         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::growthLimitIfNotInfinite, &GridTrack::growGrowthLimit);
 643         resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::growthLimitIfNotInfinite, &GridTrack::growGrowthLimit);
 644     }
 645
 646     for (auto trackIndex : sizingData.contentSizedTracksIndex) {
 647         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
 648         if (track.growthLimitIsInfinite())
 649             track.setGrowthLimit(track.baseSize());
 650     }
 651 }
 652
 653 void RenderGrid::resolveContentBasedTrackSizingFunctionsForNonSpanningItems(GridTrackSizingDirection direction, const GridCoordinate& coordinate, RenderBox& gridItem, GridTrack& track, Vector<GridTrack>& columnTracks)
 654 {
 655     const GridResolvedPosition trackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
 656     GridTrackSize trackSize = gridTrackSize(direction, trackPosition.toInt());
 657
 658     if (trackSize.hasMinContentMinTrackBreadth())
 659         track.setBaseSize(std::max(track.baseSize(), minContentForChild(gridItem, direction, columnTracks)));
 660     else if (trackSize.hasMaxContentMinTrackBreadth())
 661         track.setBaseSize(std::max(track.baseSize(), maxContentForChild(gridItem, direction, columnTracks)));
 662
 663     if (trackSize.hasMinContentMaxTrackBreadth())
 664         track.setGrowthLimit(std::max(track.growthLimit(), minContentForChild(gridItem, direction, columnTracks)));
 665     else if (trackSize.hasMaxContentMaxTrackBreadth())
 666         track.setGrowthLimit(std::max(track.growthLimit(), maxContentForChild(gridItem, direction, columnTracks)));
 667 }
 668
 669 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, GridItemWithSpan& gridItemWithSpan, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, FilterFunction growAboveMaxBreadthFilterFunction)
 670 {
 671     ASSERT(gridItemWithSpan.span() > 1);
 672     const GridCoordinate& coordinate = gridItemWithSpan.coordinate();
 673     const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
 674     const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
 675
 676     sizingData.filteredTracks.shrink(0);
 677     sizingData.growAboveMaxBreadthTrackIndexes.shrink(0);
 678     for (GridResolvedPosition trackIndex = initialTrackPosition; trackIndex <= finalTrackPosition; ++trackIndex) {
 679         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex.toInt());
 680         if (!(trackSize.*filterFunction)())
 681             continue;
 682
 683         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex.toInt()] : sizingData.rowTracks[trackIndex.toInt()];
 684         sizingData.filteredTracks.append(&track);
 685
 686         if (growAboveMaxBreadthFilterFunction && (trackSize.*growAboveMaxBreadthFilterFunction)())
 687             sizingData.growAboveMaxBreadthTrackIndexes.append(sizingData.filteredTracks.size() - 1);
 688     }
 689
 690     if (sizingData.filteredTracks.isEmpty())
 691         return;
 692
 693     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItemWithSpan.gridItem(), direction, sizingData.columnTracks);
 694     for (GridResolvedPosition trackPositionForSpace = initialTrackPosition; trackPositionForSpace <= finalTrackPosition; ++trackPositionForSpace) {
 695         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPositionForSpace.toInt()] : sizingData.rowTracks[trackPositionForSpace.toInt()];
 696         additionalBreadthSpace -= (track.*trackGetter)();
 697     }
 698
 699     // Specs mandate to floor additionalBreadthSpace (extra-space in specs) to 0. Instead we directly avoid the function
 700     // call in those cases as it will be a noop in terms of track sizing.
 701     if (additionalBreadthSpace > 0)
 702         distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.growAboveMaxBreadthTrackIndexes, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
 703 }
 704
 705 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
 706 {
 707     // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
 708     // (forall x: NOT x < x).
 709     if (track1->growthLimitIsInfinite() && track2->growthLimitIsInfinite())
 710         return false;
 711
 712     if (track1->growthLimitIsInfinite() || track2->growthLimitIsInfinite())
 713         return track2->growthLimitIsInfinite();
 714
 715     return (track1->growthLimit() - track1->baseSize()) < (track2->growthLimit() - track2->baseSize());
 716 }
 717
 718 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<unsigned>* growAboveMaxBreadthTrackIndexes, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 719 {
 720     ASSERT(availableLogicalSpace > 0);
 721     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
 722
 723     unsigned tracksSize = tracks.size();
 724     sizingData.distributeTrackVector.resize(tracksSize);
 725
 726     for (unsigned i = 0; i < tracksSize; ++i) {
 727         GridTrack& track = *tracks[i];
 728         const LayoutUnit& trackBreadth = (tracks[i]->*trackGetter)();
 729         bool infiniteGrowthPotential = track.growthLimitIsInfinite();
 730         LayoutUnit trackGrowthPotential = infiniteGrowthPotential ? track.growthLimit() : track.growthLimit() - trackBreadth;
 731         sizingData.distributeTrackVector[i] = trackBreadth;
 732         // Let's avoid computing availableLogicalSpaceShare as much as possible as it's a hot spot in performance tests.
 733         if (trackGrowthPotential > 0 || infiniteGrowthPotential) {
 734             LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
 735             LayoutUnit growthShare = infiniteGrowthPotential ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, trackGrowthPotential);
 736             ASSERT_WITH_MESSAGE(growthShare >= 0, "We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function. We can still have 0 as growthShare if the amount of tracks greatly exceeds the availableLogicalSpace.");
 737             sizingData.distributeTrackVector[i] += growthShare;
 738             availableLogicalSpace -= growthShare;
 739         }
 740     }
 741
 742     if (availableLogicalSpace > 0 && growAboveMaxBreadthTrackIndexes) {
 743         unsigned indexesSize = growAboveMaxBreadthTrackIndexes->size();
 744         unsigned tracksGrowingAboveMaxBreadthSize = indexesSize ? indexesSize : tracksSize;
 745         // If we have a non-null empty vector of track indexes to grow above max breadth means that we should grow all
 746         // affected tracks.
 747         for (unsigned i = 0; i < tracksGrowingAboveMaxBreadthSize; ++i) {
 748             LayoutUnit growthShare = availableLogicalSpace / (tracksGrowingAboveMaxBreadthSize - i);
 749             unsigned distributeTrackIndex = indexesSize ? growAboveMaxBreadthTrackIndexes->at(i) : i;
 750             sizingData.distributeTrackVector[distributeTrackIndex] += growthShare;
 751             availableLogicalSpace -= growthShare;
 752         }
 753     }
 754
 755     for (unsigned i = 0; i < tracksSize; ++i) {
 756         LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
 757         if (growth >= 0)
 758             (tracks[i]->*trackGrowthFunction)(growth);
 759     }
 760 }
 761
 762 #ifndef NDEBUG
 763 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
 764 {
 765     for (unsigned i = 0; i < tracks.size(); ++i) {
 766         const GridTrackSize& trackSize = gridTrackSize(direction, i);
 767         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
 768         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].baseSize())
 769             return false;
 770     }
 771     return true;
 772 }
 773 #endif
 774
 775 void RenderGrid::ensureGridSize(unsigned maximumRowIndex, unsigned maximumColumnIndex)
 776 {
 777     const unsigned oldRowCount = gridRowCount();
 778     if (maximumRowIndex >= oldRowCount) {
 779         m_grid.grow(maximumRowIndex + 1);
 780         for (unsigned row = oldRowCount; row < gridRowCount(); ++row)
 781             m_grid[row].grow(gridColumnCount());
 782     }
 783
 784     if (maximumColumnIndex >= gridColumnCount()) {
 785         for (unsigned row = 0; row < gridRowCount(); ++row)
 786             m_grid[row].grow(maximumColumnIndex + 1);
 787     }
 788 }
 789
 790 void RenderGrid::insertItemIntoGrid(RenderBox& child, const GridCoordinate& coordinate)
 791 {
 792     ensureGridSize(coordinate.rows.resolvedFinalPosition.toInt(), coordinate.columns.resolvedFinalPosition.toInt());
 793
 794     for (auto& row : coordinate.rows) {
 795         for (auto& column : coordinate.columns)
 796             m_grid[row.toInt()][column.toInt()].append(&child);
 797     }
 798     m_gridItemCoordinate.set(&child, coordinate);
 799 }
 800
 801 void RenderGrid::placeItemsOnGrid()
 802 {
 803     ASSERT(!gridWasPopulated());
 804     ASSERT(m_gridItemCoordinate.isEmpty());
 805
 806     populateExplicitGridAndOrderIterator();
 807
 808     Vector<RenderBox*> autoMajorAxisAutoGridItems;
 809     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
 810     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
 811         std::unique_ptr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForRows);
 812         std::unique_ptr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForColumns);
 813         if (!rowPositions || !columnPositions) {
 814             GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get();
 815             if (!majorAxisPositions)
 816                 autoMajorAxisAutoGridItems.append(child);
 817             else
 818                 specifiedMajorAxisAutoGridItems.append(child);
 819             continue;
 820         }
 821         insertItemIntoGrid(*child, GridCoordinate(*rowPositions, *columnPositions));
 822     }
 823
 824     ASSERT(gridRowCount() >= GridResolvedPosition::explicitGridRowCount(style()));
 825     ASSERT(gridColumnCount() >= GridResolvedPosition::explicitGridColumnCount(style()));
 826
 827     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
 828     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
 829 }
 830
 831 void RenderGrid::populateExplicitGridAndOrderIterator()
 832 {
 833     OrderIteratorPopulator populator(m_orderIterator);
 834     unsigned maximumRowIndex = std::max<unsigned>(1, GridResolvedPosition::explicitGridRowCount(style()));
 835     unsigned maximumColumnIndex = std::max<unsigned>(1, GridResolvedPosition::explicitGridColumnCount(style()));
 836
 837     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
 838         populator.collectChild(*child);
 839
 840         // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
 841         std::unique_ptr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForRows);
 842         std::unique_ptr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *child, ForColumns);
 843
 844         // |positions| is 0 if we need to run the auto-placement algorithm.
 845         if (rowPositions)
 846             maximumRowIndex = std::max(maximumRowIndex, rowPositions->resolvedFinalPosition.next().toInt());
 847         else {
 848             // Grow the grid for items with a definite row span, getting the largest such span.
 849             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *child, ForRows, GridResolvedPosition(0));
 850             maximumRowIndex = std::max(maximumRowIndex, positions.resolvedFinalPosition.next().toInt());
 851         }
 852
 853         if (columnPositions)
 854             maximumColumnIndex = std::max(maximumColumnIndex, columnPositions->resolvedFinalPosition.next().toInt());
 855         else {
 856             // Grow the grid for items with a definite column span, getting the largest such span.
 857             GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *child, ForColumns, GridResolvedPosition(0));
 858             maximumColumnIndex = std::max(maximumColumnIndex, positions.resolvedFinalPosition.next().toInt());
 859         }
 860     }
 861
 862     m_grid.grow(maximumRowIndex);
 863     for (auto& column : m_grid)
 864         column.grow(maximumColumnIndex);
 865 }
 866
 867 std::unique_ptr<GridCoordinate> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox& gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
 868 {
 869     GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
 870     const unsigned endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount();
 871     GridSpan crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection));
 872     return std::make_unique<GridCoordinate>(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions);
 873 }
 874
 875 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 876 {
 877     bool isForColumns = autoPlacementMajorAxisDirection() == ForColumns;
 878     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
 879
 880     // Mapping between the major axis tracks (rows or columns) and the last auto-placed item's position inserted on
 881     // that track. This is needed to implement "sparse" packing for items locked to a given track.
 882     // See http://dev.w3.org/csswg/css-grid/#auto-placement-algo
 883     HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> minorAxisCursors;
 884
 885     for (auto& autoGridItem : autoGridItems) {
 886         std::unique_ptr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), *autoGridItem, autoPlacementMajorAxisDirection());
 887         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), *autoGridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
 888         unsigned majorAxisInitialPosition = majorAxisPositions->resolvedInitialPosition.toInt();
 889
 890         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt(), isGridAutoFlowDense ? 0 : minorAxisCursors.get(majorAxisInitialPosition));
 891         std::unique_ptr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->integerSpan(), minorAxisPositions.integerSpan());
 892         if (!emptyGridArea)
 893             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(*autoGridItem, autoPlacementMajorAxisDirection(), *majorAxisPositions);
 894         insertItemIntoGrid(*autoGridItem, *emptyGridArea);
 895
 896         if (!isGridAutoFlowDense)
 897             minorAxisCursors.set(majorAxisInitialPosition, isForColumns ? emptyGridArea->rows.resolvedInitialPosition.toInt() : emptyGridArea->columns.resolvedInitialPosition.toInt());
 898     }
 899 }
 900
 901 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 902 {
 903     AutoPlacementCursor autoPlacementCursor = {0, 0};
 904     bool isGridAutoFlowDense = style().isGridAutoFlowAlgorithmDense();
 905
 906     for (auto& autoGridItem : autoGridItems) {
 907         placeAutoMajorAxisItemOnGrid(*autoGridItem, autoPlacementCursor);
 908
 909         if (isGridAutoFlowDense) {
 910             autoPlacementCursor.first = 0;
 911             autoPlacementCursor.second = 0;
 912         }
 913     }
 914 }
 915
 916 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox& gridItem, AutoPlacementCursor& autoPlacementCursor)
 917 {
 918     std::unique_ptr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(style(), gridItem, autoPlacementMinorAxisDirection());
 919     ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(style(), gridItem, autoPlacementMajorAxisDirection()));
 920     GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(0));
 921
 922     const unsigned endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
 923     unsigned majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
 924     unsigned minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
 925
 926     std::unique_ptr<GridCoordinate> emptyGridArea;
 927     if (minorAxisPositions) {
 928         // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
 929         if (minorAxisPositions->resolvedInitialPosition.toInt() < minorAxisAutoPlacementCursor)
 930             majorAxisAutoPlacementCursor++;
 931
 932         if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
 933             GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions->resolvedInitialPosition.toInt(), majorAxisAutoPlacementCursor);
 934             emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->integerSpan(), majorAxisPositions.integerSpan());
 935         }
 936
 937         if (!emptyGridArea)
 938             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
 939     } else {
 940         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(style(), gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
 941
 942         for (unsigned majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
 943             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
 944             emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan());
 945
 946             if (emptyGridArea) {
 947                 // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
 948                 GridResolvedPosition minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.resolvedFinalPosition : emptyGridArea->rows.resolvedFinalPosition;
 949                 const unsigned endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount();
 950                 if (minorAxisFinalPositionIndex.toInt() < endOfMinorAxis)
 951                     break;
 952
 953                 // Discard empty grid area as it does not fit in the minor axis direction.
 954                 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
 955                 emptyGridArea = nullptr;
 956             }
 957
 958             // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
 959             minorAxisAutoPlacementCursor = 0;
 960         }
 961
 962         if (!emptyGridArea)
 963             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
 964     }
 965
 966     insertItemIntoGrid(gridItem, *emptyGridArea);
 967     autoPlacementCursor.first = emptyGridArea->rows.resolvedInitialPosition.toInt();
 968     autoPlacementCursor.second = emptyGridArea->columns.resolvedInitialPosition.toInt();
 969 }
 970
 971 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
 972 {
 973     return style().isGridAutoFlowDirectionColumn() ? ForColumns : ForRows;
 974 }
 975
 976 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
 977 {
 978     return style().isGridAutoFlowDirectionColumn() ? ForRows : ForColumns;
 979 }
 980
 981 void RenderGrid::clearGrid()
 982 {
 983     m_grid.clear();
 984     m_gridItemCoordinate.clear();
 985 }
 986
 987 void RenderGrid::layoutGridItems()
 988 {
 989     placeItemsOnGrid();
 990
 991     GridSizingData sizingData(gridColumnCount(), gridRowCount());
 992     computeUsedBreadthOfGridTracks(ForColumns, sizingData);
 993     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
 994     computeUsedBreadthOfGridTracks(ForRows, sizingData);
 995     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
 996
 997     populateGridPositions(sizingData);
 998
 999     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1000         // Because the grid area cannot be styled, we don't need to adjust
1001         // the grid breadth to account for 'box-sizing'.
1002         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
1003         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
1004
1005         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(*child, ForColumns, sizingData.columnTracks);
1006         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(*child, ForRows, sizingData.rowTracks);
1007         if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && child->hasRelativeLogicalHeight()))
1008             child->setNeedsLayout(MarkOnlyThis);
1009
1010         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
1011         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
1012
1013         LayoutRect oldChildRect = child->frameRect();
1014
1015         // FIXME: Grid items should stretch to fill their cells. Once we
1016         // implement grid-{column,row}-align, we can also shrink to fit. For
1017         // now, just size as if we were a regular child.
1018         child->layoutIfNeeded();
1019
1020         child->setLogicalLocation(findChildLogicalPosition(*child, sizingData));
1021
1022         // If the child moved, we have to repaint it as well as any floating/positioned
1023         // descendants. An exception is if we need a layout. In this case, we know we're going to
1024         // repaint ourselves (and the child) anyway.
1025         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
1026             child->repaintDuringLayoutIfMoved(oldChildRect);
1027     }
1028
1029     for (auto& row : sizingData.rowTracks)
1030         setLogicalHeight(logicalHeight() + row.baseSize());
1031
1032     // min / max logical height is handled in updateLogicalHeight().
1033     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
1034     if (hasLineIfEmpty()) {
1035         LayoutUnit minHeight = borderAndPaddingLogicalHeight()
1036             + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes)
1037             + scrollbarLogicalHeight();
1038         if (height() < minHeight)
1039             setLogicalHeight(minHeight);
1040     }
1041
1042     clearGrid();
1043 }
1044
1045 GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox& gridItem) const
1046 {
1047     ASSERT(m_gridItemCoordinate.contains(&gridItem));
1048     return m_gridItemCoordinate.get(&gridItem);
1049 }
1050
1051 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
1052 {
1053     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1054     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
1055     LayoutUnit gridAreaBreadth = 0;
1056     for (auto& trackPosition : span)
1057         gridAreaBreadth += tracks[trackPosition.toInt()].baseSize();
1058     return gridAreaBreadth;
1059 }
1060
1061 void RenderGrid::populateGridPositions(const GridSizingData& sizingData)
1062 {
1063     m_columnPositions.resizeToFit(sizingData.columnTracks.size() + 1);
1064     m_columnPositions[0] = borderAndPaddingStart();
1065     for (unsigned i = 0; i < m_columnPositions.size() - 1; ++i)
1066         m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].baseSize();
1067
1068     m_rowPositions.resizeToFit(sizingData.rowTracks.size() + 1);
1069     m_rowPositions[0] = borderAndPaddingBefore();
1070     for (unsigned i = 0; i < m_rowPositions.size() - 1; ++i)
1071         m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].baseSize();
1072 }
1073
1074 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox& child, const GridSizingData& sizingData)
1075 {
1076     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1077     ASSERT_UNUSED(sizingData, coordinate.columns.resolvedInitialPosition.toInt() < sizingData.columnTracks.size());
1078     ASSERT_UNUSED(sizingData, coordinate.rows.resolvedInitialPosition.toInt() < sizingData.rowTracks.size());
1079
1080     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1081     return LayoutPoint(m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()] + marginStartForChild(child), m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()] + marginBeforeForChild(child));
1082 }
1083
1084 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset, PaintInfo& forChild, bool usePrintRect)
1085 {
1086     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next())
1087         paintChild(*child, paintInfo, paintOffset, forChild, usePrintRect);
1088 }
1089
1090 const char* RenderGrid::renderName() const
1091 {
1092     if (isFloating())
1093         return "RenderGrid (floating)";
1094     if (isOutOfFlowPositioned())
1095         return "RenderGrid (positioned)";
1096     if (isAnonymous())
1097         return "RenderGrid (generated)";
1098     if (isRelPositioned())
1099         return "RenderGrid (relative positioned)";
1100     return "RenderGrid";
1101 }
1102
1103 } // namespace WebCore
1104
1105 #endif /* ENABLE(CSS_GRID_LAYOUT) */