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/rendering/LayoutRepainter.h"
  30 #include "core/rendering/RenderLayer.h"
  31 #include "core/rendering/RenderView.h"
  32 #include "core/rendering/style/GridCoordinate.h"
  33 #include "platform/LengthFunctions.h"
  34
  35 namespace WebCore {
  36
  37 static const int infinity = -1;
  38
  39 class GridTrack {
  40 public:
  41     GridTrack()
  42         : m_usedBreadth(0)
  43         , m_maxBreadth(0)
  44     {
  45     }
  46
  47     void growUsedBreadth(LayoutUnit growth)
  48     {
  49         ASSERT(growth >= 0);
  50         m_usedBreadth += growth;
  51     }
  52     LayoutUnit usedBreadth() const { return m_usedBreadth; }
  53
  54     void growMaxBreadth(LayoutUnit growth)
  55     {
  56         if (m_maxBreadth == infinity)
  57             m_maxBreadth = m_usedBreadth + growth;
  58         else
  59             m_maxBreadth += growth;
  60     }
  61     LayoutUnit maxBreadthIfNotInfinite() const
  62     {
  63         return (m_maxBreadth == infinity) ? m_usedBreadth : m_maxBreadth;
  64     }
  65
  66     LayoutUnit m_usedBreadth;
  67     LayoutUnit m_maxBreadth;
  68 };
  69
  70 struct GridTrackForNormalization {
  71     GridTrackForNormalization(const GridTrack& track, double flex)
  72         : m_track(&track)
  73         , m_flex(flex)
  74         , m_normalizedFlexValue(track.m_usedBreadth / flex)
  75     {
  76     }
  77
  78     // Required by std::sort.
  79     GridTrackForNormalization& operator=(const GridTrackForNormalization& o)
  80     {
  81         m_track = o.m_track;
  82         m_flex = o.m_flex;
  83         m_normalizedFlexValue = o.m_normalizedFlexValue;
  84         return *this;
  85     }
  86
  87     const GridTrack* m_track;
  88     double m_flex;
  89     LayoutUnit m_normalizedFlexValue;
  90 };
  91
  92 class RenderGrid::GridIterator {
  93     WTF_MAKE_NONCOPYABLE(GridIterator);
  94 public:
  95     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
  96     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
  97     GridIterator(const GridRepresentation& grid, GridTrackSizingDirection direction, size_t fixedTrackIndex)
  98         : m_grid(grid)
  99         , m_direction(direction)
 100         , m_rowIndex((direction == ForColumns) ? 0 : fixedTrackIndex)
 101         , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : 0)
 102         , m_childIndex(0)
 103     {
 104         ASSERT(m_rowIndex < m_grid.size());
 105         ASSERT(m_columnIndex < m_grid[0].size());
 106     }
 107
 108     RenderBox* nextGridItem()
 109     {
 110         ASSERT(!m_grid.isEmpty());
 111
 112         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
 113         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
 114         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
 115             const GridCell& children = m_grid[m_rowIndex][m_columnIndex];
 116             if (m_childIndex < children.size())
 117                 return children[m_childIndex++];
 118
 119             m_childIndex = 0;
 120         }
 121         return 0;
 122     }
 123
 124     PassOwnPtr<GridCoordinate> nextEmptyGridArea()
 125     {
 126         ASSERT(!m_grid.isEmpty());
 127
 128         size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
 129         const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
 130         for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
 131             const GridCell& children = m_grid[m_rowIndex][m_columnIndex];
 132             if (children.isEmpty()) {
 133                 OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(GridSpan(m_rowIndex, m_rowIndex), GridSpan(m_columnIndex, m_columnIndex)));
 134                 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
 135                 ++varyingTrackIndex;
 136                 return result.release();
 137             }
 138         }
 139         return nullptr;
 140     }
 141
 142 private:
 143     const GridRepresentation& m_grid;
 144     GridTrackSizingDirection m_direction;
 145     size_t m_rowIndex;
 146     size_t m_columnIndex;
 147     size_t m_childIndex;
 148 };
 149
 150 struct RenderGrid::GridSizingData {
 151     WTF_MAKE_NONCOPYABLE(GridSizingData);
 152 public:
 153     GridSizingData(size_t gridColumnCount, size_t gridRowCount)
 154         : columnTracks(gridColumnCount)
 155         , rowTracks(gridRowCount)
 156     {
 157     }
 158
 159     Vector<GridTrack> columnTracks;
 160     Vector<GridTrack> rowTracks;
 161     Vector<size_t> contentSizedTracksIndex;
 162
 163     // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
 164     Vector<LayoutUnit> distributeTrackVector;
 165     Vector<GridTrack*> filteredTracks;
 166 };
 167
 168 RenderGrid::RenderGrid(Element* element)
 169     : RenderBlock(element)
 170     , m_gridIsDirty(true)
 171     , m_orderIterator(this)
 172 {
 173     // All of our children must be block level.
 174     setChildrenInline(false);
 175 }
 176
 177 RenderGrid::~RenderGrid()
 178 {
 179 }
 180
 181 void RenderGrid::addChild(RenderObject* newChild, RenderObject* beforeChild)
 182 {
 183     RenderBlock::addChild(newChild, beforeChild);
 184
 185     if (gridIsDirty())
 186         return;
 187
 188     if (!newChild->isBox()) {
 189         dirtyGrid();
 190         return;
 191     }
 192
 193     if (style()->gridAutoFlow() != AutoFlowNone) {
 194         // The grid needs to be recomputed as it might contain auto-placed items that will change their position.
 195         dirtyGrid();
 196         return;
 197     }
 198
 199     RenderBox* newChildBox = toRenderBox(newChild);
 200     OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForRows);
 201     OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForColumns);
 202     if (!rowPositions || !columnPositions) {
 203         // The new child requires the auto-placement algorithm to run so we need to recompute the grid fully.
 204         dirtyGrid();
 205         return;
 206     } else {
 207         // Ensure that the grid is big enough to contain new grid item.
 208         if (gridRowCount() <= rowPositions->resolvedFinalPosition.toInt())
 209             growGrid(ForRows, rowPositions->resolvedFinalPosition.toInt());
 210         if (gridColumnCount() <= columnPositions->resolvedFinalPosition.toInt())
 211             growGrid(ForColumns, columnPositions->resolvedFinalPosition.toInt());
 212
 213         insertItemIntoGrid(newChildBox, GridCoordinate(*rowPositions, *columnPositions));
 214     }
 215 }
 216
 217 void RenderGrid::removeChild(RenderObject* child)
 218 {
 219     RenderBlock::removeChild(child);
 220
 221     if (gridIsDirty())
 222         return;
 223
 224     ASSERT(child->isBox());
 225
 226     if (style()->gridAutoFlow() != AutoFlowNone) {
 227         // The grid needs to be recomputed as it might contain auto-placed items that will change their position.
 228         dirtyGrid();
 229         return;
 230     }
 231
 232     const RenderBox* childBox = toRenderBox(child);
 233     GridCoordinate coordinate = m_gridItemCoordinate.take(childBox);
 234
 235     for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) {
 236         for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column) {
 237             GridCell& cell = m_grid[row.toInt()][column.toInt()];
 238             cell.remove(cell.find(childBox));
 239         }
 240     }
 241 }
 242
 243 void RenderGrid::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
 244 {
 245     RenderBlock::styleDidChange(diff, oldStyle);
 246     if (!oldStyle)
 247         return;
 248
 249     // FIXME: The following checks could be narrowed down if we kept track of which type of grid items we have:
 250     // - explicit grid size changes impact negative explicitely positioned and auto-placed grid items.
 251     // - named grid lines only impact grid items with named grid lines.
 252     // - auto-flow changes only impacts auto-placed children.
 253
 254     if (explicitGridDidResize(oldStyle)
 255         || namedGridLinesDefinitionDidChange(oldStyle)
 256         || oldStyle->gridAutoFlow() != style()->gridAutoFlow())
 257         dirtyGrid();
 258 }
 259
 260 bool RenderGrid::explicitGridDidResize(const RenderStyle* oldStyle) const
 261 {
 262     return oldStyle->gridTemplateColumns().size() != style()->gridTemplateColumns().size()
 263         || oldStyle->gridTemplateRows().size() != style()->gridTemplateRows().size();
 264 }
 265
 266 bool RenderGrid::namedGridLinesDefinitionDidChange(const RenderStyle* oldStyle) const
 267 {
 268     return oldStyle->namedGridRowLines() != style()->namedGridRowLines()
 269         || oldStyle->namedGridColumnLines() != style()->namedGridColumnLines();
 270 }
 271
 272 void RenderGrid::layoutBlock(bool relayoutChildren)
 273 {
 274     ASSERT(needsLayout());
 275
 276     if (!relayoutChildren && simplifiedLayout())
 277         return;
 278
 279     // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
 280     // It would be nice to refactor some of the duplicate code.
 281     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
 282     LayoutStateMaintainer statePusher(*this, locationOffset());
 283
 284     LayoutSize previousSize = size();
 285
 286     setLogicalHeight(0);
 287     updateLogicalWidth();
 288
 289     layoutGridItems();
 290
 291     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
 292     updateLogicalHeight();
 293
 294     if (size() != previousSize)
 295         relayoutChildren = true;
 296
 297     layoutPositionedObjects(relayoutChildren || isDocumentElement());
 298
 299     computeRegionRangeForBlock(flowThreadContainingBlock());
 300
 301     computeOverflow(oldClientAfterEdge);
 302
 303     updateLayerTransform();
 304
 305     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
 306     // we overflow or not.
 307     if (hasOverflowClip())
 308         layer()->scrollableArea()->updateAfterLayout();
 309
 310     repainter.repaintAfterLayout();
 311
 312     clearNeedsLayout();
 313 }
 314
 315 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
 316 {
 317     const_cast<RenderGrid*>(this)->placeItemsOnGrid();
 318
 319     GridSizingData sizingData(gridColumnCount(), gridRowCount());
 320     LayoutUnit availableLogicalSpace = 0;
 321     const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace);
 322
 323     for (size_t i = 0; i < sizingData.columnTracks.size(); ++i) {
 324         LayoutUnit minTrackBreadth = sizingData.columnTracks[i].m_usedBreadth;
 325         LayoutUnit maxTrackBreadth = sizingData.columnTracks[i].m_maxBreadth;
 326         maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth);
 327
 328         minLogicalWidth += minTrackBreadth;
 329         maxLogicalWidth += maxTrackBreadth;
 330
 331         // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
 332     }
 333 }
 334
 335 void RenderGrid::computePreferredLogicalWidths()
 336 {
 337     ASSERT(preferredLogicalWidthsDirty());
 338
 339     m_minPreferredLogicalWidth = 0;
 340     m_maxPreferredLogicalWidth = 0;
 341
 342     // FIXME: We don't take our own logical width into account. Once we do, we need to make sure
 343     // we apply (and test the interaction with) min-width / max-width.
 344
 345     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
 346
 347     LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
 348     m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
 349     m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
 350
 351     clearPreferredLogicalWidthsDirty();
 352 }
 353
 354 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData)
 355 {
 356     LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
 357     computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace);
 358 }
 359
 360 bool RenderGrid::gridElementIsShrinkToFit()
 361 {
 362     return isFloatingOrOutOfFlowPositioned();
 363 }
 364
 365 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 366 {
 367     Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
 368     Vector<size_t> flexibleSizedTracksIndex;
 369     sizingData.contentSizedTracksIndex.shrink(0);
 370
 371     // 1. Initialize per Grid track variables.
 372     for (size_t i = 0; i < tracks.size(); ++i) {
 373         GridTrack& track = tracks[i];
 374         const GridTrackSize& trackSize = gridTrackSize(direction, i);
 375         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
 376         const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
 377
 378         track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth);
 379         track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.m_usedBreadth);
 380
 381         track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth);
 382
 383         if (trackSize.isContentSized())
 384             sizingData.contentSizedTracksIndex.append(i);
 385         if (trackSize.maxTrackBreadth().isFlex())
 386             flexibleSizedTracksIndex.append(i);
 387     }
 388
 389     // 2. Resolve content-based TrackSizingFunctions.
 390     if (!sizingData.contentSizedTracksIndex.isEmpty())
 391         resolveContentBasedTrackSizingFunctions(direction, sizingData, availableLogicalSpace);
 392
 393     for (size_t i = 0; i < tracks.size(); ++i) {
 394         ASSERT(tracks[i].m_maxBreadth != infinity);
 395         availableLogicalSpace -= tracks[i].m_usedBreadth;
 396     }
 397
 398     const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style()->logicalHeight().isAuto() : gridElementIsShrinkToFit();
 399
 400     if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0)
 401         return;
 402
 403     // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until
 404     // availableLogicalSpace (RemainingSpace in the specs) is exhausted.
 405     const size_t tracksSize = tracks.size();
 406     if (!hasUndefinedRemainingSpace) {
 407         Vector<GridTrack*> tracksForDistribution(tracksSize);
 408         for (size_t i = 0; i < tracksSize; ++i)
 409             tracksForDistribution[i] = tracks.data() + i;
 410
 411         distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, sizingData, availableLogicalSpace);
 412     } else {
 413         for (size_t i = 0; i < tracksSize; ++i)
 414             tracks[i].m_usedBreadth = tracks[i].m_maxBreadth;
 415     }
 416
 417     if (flexibleSizedTracksIndex.isEmpty())
 418         return;
 419
 420     // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
 421     double normalizedFractionBreadth = 0;
 422     if (!hasUndefinedRemainingSpace) {
 423         normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, availableLogicalSpace);
 424     } else {
 425         for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
 426             const size_t trackIndex = flexibleSizedTracksIndex[i];
 427             const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
 428             normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].m_usedBreadth / trackSize.maxTrackBreadth().flex());
 429         }
 430
 431         for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
 432             GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
 433             while (RenderBox* gridItem = iterator.nextGridItem()) {
 434                 const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
 435                 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
 436
 437                 // Do not include already processed items.
 438                 if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1])
 439                     continue;
 440
 441                 double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(gridItem, direction, sizingData.columnTracks));
 442                 normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
 443             }
 444         }
 445     }
 446
 447     for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
 448         const size_t trackIndex = flexibleSizedTracksIndex[i];
 449         const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
 450
 451         tracks[trackIndex].m_usedBreadth = std::max<LayoutUnit>(tracks[trackIndex].m_usedBreadth, normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
 452     }
 453 }
 454
 455 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
 456 {
 457     if (gridLength.isFlex())
 458         return 0;
 459
 460     const Length& trackLength = gridLength.length();
 461     ASSERT(!trackLength.isAuto());
 462     if (trackLength.isSpecified())
 463         return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
 464
 465     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
 466     return 0;
 467 }
 468
 469 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const
 470 {
 471     if (gridLength.isFlex())
 472         return usedBreadth;
 473
 474     const Length& trackLength = gridLength.length();
 475     ASSERT(!trackLength.isAuto());
 476     if (trackLength.isSpecified()) {
 477         LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
 478         ASSERT(computedBreadth != infinity);
 479         return computedBreadth;
 480     }
 481
 482     ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
 483     return infinity;
 484 }
 485
 486 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
 487 {
 488     ASSERT(trackLength.isSpecified());
 489     // FIXME: The -1 here should be replaced by whatever the intrinsic height of the grid is.
 490     return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style()->logicalHeight(), -1));
 491 }
 492
 493 static bool sortByGridNormalizedFlexValue(const GridTrackForNormalization& track1, const GridTrackForNormalization& track2)
 494 {
 495     return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
 496 }
 497
 498 double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit availableLogicalSpace) const
 499 {
 500     // |availableLogicalSpace| already accounts for the used breadths so no need to remove it here.
 501
 502     Vector<GridTrackForNormalization> tracksForNormalization;
 503     for (GridSpan::iterator resolvedPosition = tracksSpan.begin(); resolvedPosition != tracksSpan.end(); ++resolvedPosition) {
 504         const GridTrackSize& trackSize = gridTrackSize(direction, resolvedPosition.toInt());
 505         if (!trackSize.maxTrackBreadth().isFlex())
 506             continue;
 507
 508         tracksForNormalization.append(GridTrackForNormalization(tracks[resolvedPosition.toInt()], trackSize.maxTrackBreadth().flex()));
 509     }
 510
 511     // The function is not called if we don't have <flex> grid tracks
 512     ASSERT(!tracksForNormalization.isEmpty());
 513
 514     std::sort(tracksForNormalization.begin(), tracksForNormalization.end(), sortByGridNormalizedFlexValue);
 515
 516     // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
 517     // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
 518     // fit into availableLogicalSpaceIgnoringFractionTracks.
 519     double accumulatedFractions = 0;
 520     LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
 521     LayoutUnit availableLogicalSpaceIgnoringFractionTracks = availableLogicalSpace;
 522
 523     for (size_t i = 0; i < tracksForNormalization.size(); ++i) {
 524         const GridTrackForNormalization& track = tracksForNormalization[i];
 525         if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
 526             // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
 527             // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
 528             if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
 529                 break;
 530
 531             fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
 532         }
 533
 534         accumulatedFractions += track.m_flex;
 535         // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
 536         availableLogicalSpaceIgnoringFractionTracks += track.m_track->m_usedBreadth;
 537     }
 538
 539     return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
 540 }
 541
 542 const GridTrackSize& RenderGrid::gridTrackSize(GridTrackSizingDirection direction, size_t i) const
 543 {
 544     const Vector<GridTrackSize>& trackStyles = (direction == ForColumns) ? style()->gridTemplateColumns() : style()->gridTemplateRows();
 545     if (i >= trackStyles.size())
 546         return (direction == ForColumns) ? style()->gridAutoColumns() : style()->gridAutoRows();
 547
 548     const GridTrackSize& trackSize = trackStyles[i];
 549     // If the logical width/height of the grid container is indefinite, percentage values are treated as <auto>.
 550     if (trackSize.isPercentage()) {
 551         Length logicalSize = direction == ForColumns ? style()->logicalWidth() : style()->logicalHeight();
 552         if (logicalSize.isIntrinsicOrAuto()) {
 553             DEFINE_STATIC_LOCAL(GridTrackSize, autoTrackSize, (Length(Auto)));
 554             return autoTrackSize;
 555         }
 556     }
 557
 558     return trackSize;
 559 }
 560
 561 LayoutUnit RenderGrid::logicalHeightForChild(RenderBox* child, Vector<GridTrack>& columnTracks)
 562 {
 563     SubtreeLayoutScope layoutScope(*child);
 564     LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
 565     LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
 566     if (child->style()->logicalHeight().isPercent() || oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth)
 567         layoutScope.setNeedsLayout(child);
 568
 569     child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
 570     // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is
 571     // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution).
 572     child->setOverrideContainingBlockContentLogicalHeight(-1);
 573     child->layoutIfNeeded();
 574     return child->logicalHeight() + child->marginLogicalHeight();
 575 }
 576
 577 LayoutUnit RenderGrid::minContentForChild(RenderBox* child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
 578 {
 579     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
 580     // FIXME: Properly support orthogonal writing mode.
 581     if (hasOrthogonalWritingMode)
 582         return 0;
 583
 584     if (direction == ForColumns) {
 585         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
 586         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
 587         return child->minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
 588     }
 589
 590     return logicalHeightForChild(child, columnTracks);
 591 }
 592
 593 LayoutUnit RenderGrid::maxContentForChild(RenderBox* child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
 594 {
 595     bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
 596     // FIXME: Properly support orthogonal writing mode.
 597     if (hasOrthogonalWritingMode)
 598         return LayoutUnit();
 599
 600     if (direction == ForColumns) {
 601         // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
 602         // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
 603         return child->maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child);
 604     }
 605
 606     return logicalHeightForChild(child, columnTracks);
 607 }
 608
 609 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 610 {
 611     // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track (crbug.com/235258).
 612
 613     // FIXME: Per step 2 of the specification, we should order the grid items by increasing span.
 614
 615     for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
 616         GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]);
 617         while (RenderBox* gridItem = iterator.nextGridItem()) {
 618             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
 619             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
 620             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
 621             resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
 622         }
 623
 624         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[i] : sizingData.rowTracks[i];
 625         if (track.m_maxBreadth == infinity)
 626             track.m_maxBreadth = track.m_usedBreadth;
 627     }
 628 }
 629
 630 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, RenderBox* gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
 631 {
 632     const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
 633     const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
 634     const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
 635
 636     sizingData.filteredTracks.shrink(0);
 637     for (GridResolvedPosition trackPosition = initialTrackPosition; trackPosition <= finalTrackPosition; ++trackPosition) {
 638         const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition.toInt());
 639         if (!(trackSize.*filterFunction)())
 640             continue;
 641
 642         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPosition.toInt()] : sizingData.rowTracks[trackPosition.toInt()];
 643         sizingData.filteredTracks.append(&track);
 644     }
 645
 646     if (sizingData.filteredTracks.isEmpty())
 647         return;
 648
 649     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks);
 650     for (GridResolvedPosition trackIndexForSpace = initialTrackPosition; trackIndexForSpace <= finalTrackPosition; ++trackIndexForSpace) {
 651         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndexForSpace.toInt()] : sizingData.rowTracks[trackIndexForSpace.toInt()];
 652         additionalBreadthSpace -= (track.*trackGetter)();
 653     }
 654
 655     // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
 656     distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.filteredTracks, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
 657 }
 658
 659 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
 660 {
 661     return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
 662 }
 663
 664 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
 665 {
 666     std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
 667
 668     size_t tracksSize = tracks.size();
 669     sizingData.distributeTrackVector.resize(tracksSize);
 670
 671     for (size_t i = 0; i < tracksSize; ++i) {
 672         GridTrack& track = *tracks[i];
 673         LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
 674         LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
 675         LayoutUnit growthShare = std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth);
 676         sizingData.distributeTrackVector[i] = trackBreadth;
 677         // We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function.
 678         if (growthShare > 0) {
 679             sizingData.distributeTrackVector[i] += growthShare;
 680             availableLogicalSpace -= growthShare;
 681         }
 682     }
 683
 684     if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) {
 685         tracksSize = tracksForGrowthAboveMaxBreadth->size();
 686         for (size_t i = 0; i < tracksSize; ++i) {
 687             LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
 688             sizingData.distributeTrackVector[i] += growthShare;
 689             availableLogicalSpace -= growthShare;
 690         }
 691     }
 692
 693     for (size_t i = 0; i < tracksSize; ++i) {
 694         LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
 695         if (growth >= 0)
 696             (tracks[i]->*trackGrowthFunction)(growth);
 697     }
 698 }
 699
 700 #ifndef NDEBUG
 701 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
 702 {
 703     for (size_t i = 0; i < tracks.size(); ++i) {
 704         const GridTrackSize& trackSize = gridTrackSize(direction, i);
 705         const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
 706         if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth)
 707             return false;
 708     }
 709     return true;
 710 }
 711 #endif
 712
 713 void RenderGrid::growGrid(GridTrackSizingDirection direction, size_t maximumPositionIndex)
 714 {
 715     if (direction == ForColumns) {
 716         ASSERT(maximumPositionIndex >= gridColumnCount());
 717         for (size_t row = 0; row < gridRowCount(); ++row)
 718             m_grid[row].grow(maximumPositionIndex + 1);
 719     } else {
 720         ASSERT(maximumPositionIndex >= gridRowCount());
 721         const size_t oldRowSize = gridRowCount();
 722         m_grid.grow(maximumPositionIndex + 1);
 723         for (size_t row = oldRowSize; row < gridRowCount(); ++row)
 724             m_grid[row].grow(gridColumnCount());
 725     }
 726 }
 727
 728 void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridCoordinate& coordinate)
 729 {
 730     for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) {
 731         for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column)
 732             m_grid[row.toInt()][column.toInt()].append(child);
 733     }
 734
 735     m_gridItemCoordinate.set(child, coordinate);
 736 }
 737
 738 void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridResolvedPosition& rowTrack, const GridResolvedPosition& columnTrack)
 739 {
 740     const GridSpan& rowSpan = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*child, ForRows, rowTrack);
 741     const GridSpan& columnSpan = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*child, ForColumns, columnTrack);
 742     insertItemIntoGrid(child, GridCoordinate(rowSpan, columnSpan));
 743 }
 744
 745 void RenderGrid::placeItemsOnGrid()
 746 {
 747     if (!gridIsDirty())
 748         return;
 749
 750     ASSERT(m_gridItemCoordinate.isEmpty());
 751
 752     populateExplicitGridAndOrderIterator();
 753
 754     // We clear the dirty bit here as the grid sizes have been updated, this means
 755     // that we can safely call gridRowCount() / gridColumnCount().
 756     m_gridIsDirty = false;
 757
 758     Vector<RenderBox*> autoMajorAxisAutoGridItems;
 759     Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
 760     GridAutoFlow autoFlow = style()->gridAutoFlow();
 761     for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
 762         // FIXME: We never re-resolve positions if the grid is grown during auto-placement which may lead auto / <integer>
 763         // positions to not match the author's intent. The specification is unclear on what should be done in this case.
 764         OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows);
 765         OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns);
 766         if (!rowPositions || !columnPositions) {
 767             GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get();
 768             if (!majorAxisPositions)
 769                 autoMajorAxisAutoGridItems.append(child);
 770             else
 771                 specifiedMajorAxisAutoGridItems.append(child);
 772             continue;
 773         }
 774         insertItemIntoGrid(child, GridCoordinate(*rowPositions, *columnPositions));
 775     }
 776
 777     ASSERT(gridRowCount() >= style()->gridTemplateRows().size());
 778     ASSERT(gridColumnCount() >= style()->gridTemplateColumns().size());
 779
 780     if (autoFlow == AutoFlowNone) {
 781         // If we did collect some grid items, they won't be placed thus never laid out.
 782         ASSERT(!autoMajorAxisAutoGridItems.size());
 783         ASSERT(!specifiedMajorAxisAutoGridItems.size());
 784         return;
 785     }
 786
 787     placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
 788     placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
 789
 790     m_grid.shrinkToFit();
 791 }
 792
 793 void RenderGrid::populateExplicitGridAndOrderIterator()
 794 {
 795     OrderIteratorPopulator populator(m_orderIterator);
 796
 797     size_t maximumRowIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridRowCount(*style()));
 798     size_t maximumColumnIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridColumnCount(*style()));
 799
 800     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
 801         populator.collectChild(child);
 802
 803         // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
 804         OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows);
 805         OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns);
 806
 807         // |positions| is 0 if we need to run the auto-placement algorithm. Our estimation ignores
 808         // this case as the auto-placement algorithm will grow the grid as needed.
 809         if (rowPositions)
 810             maximumRowIndex = std::max<size_t>(maximumRowIndex, rowPositions->resolvedFinalPosition.next().toInt());
 811         if (columnPositions)
 812             maximumColumnIndex = std::max<size_t>(maximumColumnIndex, columnPositions->resolvedFinalPosition.next().toInt());
 813     }
 814
 815     m_grid.grow(maximumRowIndex);
 816     for (size_t i = 0; i < m_grid.size(); ++i)
 817         m_grid[i].grow(maximumColumnIndex);
 818 }
 819
 820 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 821 {
 822     for (size_t i = 0; i < autoGridItems.size(); ++i) {
 823         OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *autoGridItems[i], autoPlacementMajorAxisDirection());
 824         GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt());
 825         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
 826             insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
 827             continue;
 828         }
 829
 830         growGrid(autoPlacementMinorAxisDirection(), autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount());
 831         OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea();
 832         ASSERT(emptyGridArea);
 833         insertItemIntoGrid(autoGridItems[i], emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
 834     }
 835 }
 836
 837 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 838 {
 839     for (size_t i = 0; i < autoGridItems.size(); ++i)
 840         placeAutoMajorAxisItemOnGrid(autoGridItems[i]);
 841 }
 842
 843 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
 844 {
 845     OwnPtr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMinorAxisDirection());
 846     ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMajorAxisDirection()));
 847     size_t minorAxisIndex = 0;
 848     if (minorAxisPositions) {
 849         minorAxisIndex = minorAxisPositions->resolvedInitialPosition.toInt();
 850         GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisIndex);
 851         if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
 852             insertItemIntoGrid(gridItem, emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
 853             return;
 854         }
 855     } else {
 856         const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
 857         for (size_t majorAxisIndex = 0; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
 858             GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex);
 859             if (OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea()) {
 860                 insertItemIntoGrid(gridItem, emptyGridArea->rows.resolvedInitialPosition, emptyGridArea->columns.resolvedInitialPosition);
 861                 return;
 862             }
 863         }
 864     }
 865
 866     // We didn't find an empty grid area so we need to create an extra major axis line and insert our gridItem in it.
 867     const size_t columnIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : minorAxisIndex;
 868     const size_t rowIndex = (autoPlacementMajorAxisDirection() == ForColumns) ? minorAxisIndex : gridRowCount();
 869     growGrid(autoPlacementMajorAxisDirection(), autoPlacementMajorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount());
 870     insertItemIntoGrid(gridItem, rowIndex, columnIndex);
 871 }
 872
 873 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
 874 {
 875     GridAutoFlow flow = style()->gridAutoFlow();
 876     ASSERT(flow != AutoFlowNone);
 877     return (flow == AutoFlowColumn) ? ForColumns : ForRows;
 878 }
 879
 880 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
 881 {
 882     GridAutoFlow flow = style()->gridAutoFlow();
 883     ASSERT(flow != AutoFlowNone);
 884     return (flow == AutoFlowColumn) ? ForRows : ForColumns;
 885 }
 886
 887 void RenderGrid::dirtyGrid()
 888 {
 889     m_grid.resize(0);
 890     m_gridItemCoordinate.clear();
 891     m_gridIsDirty = true;
 892     m_gridItemsOverflowingGridArea.resize(0);
 893 }
 894
 895 void RenderGrid::layoutGridItems()
 896 {
 897     placeItemsOnGrid();
 898
 899     GridSizingData sizingData(gridColumnCount(), gridRowCount());
 900     computeUsedBreadthOfGridTracks(ForColumns, sizingData);
 901     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
 902     computeUsedBreadthOfGridTracks(ForRows, sizingData);
 903     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
 904
 905     populateGridPositions(sizingData);
 906     m_gridItemsOverflowingGridArea.resize(0);
 907
 908     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
 909         // Because the grid area cannot be styled, we don't need to adjust
 910         // the grid breadth to account for 'box-sizing'.
 911         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
 912         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
 913
 914         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, sizingData.columnTracks);
 915         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(child, ForRows, sizingData.rowTracks);
 916
 917         SubtreeLayoutScope layoutScope(*child);
 918         if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && child->hasRelativeLogicalHeight()))
 919             layoutScope.setNeedsLayout(child);
 920
 921         child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
 922         child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
 923
 924         LayoutRect oldChildRect = child->frameRect();
 925
 926         // FIXME: Grid items should stretch to fill their cells. Once we
 927         // implement grid-{column,row}-align, we can also shrink to fit. For
 928         // now, just size as if we were a regular child.
 929         child->layoutIfNeeded();
 930
 931 #ifndef NDEBUG
 932         const GridCoordinate& coordinate = cachedGridCoordinate(child);
 933         ASSERT(coordinate.columns.resolvedInitialPosition.toInt() < sizingData.columnTracks.size());
 934         ASSERT(coordinate.rows.resolvedInitialPosition.toInt() < sizingData.rowTracks.size());
 935 #endif
 936         child->setLogicalLocation(findChildLogicalPosition(child));
 937
 938         // Keep track of children overflowing their grid area as we might need to paint them even if the grid-area is
 939         // not visible
 940         if (child->logicalHeight() > overrideContainingBlockContentLogicalHeight
 941             || child->logicalWidth() > overrideContainingBlockContentLogicalWidth)
 942             m_gridItemsOverflowingGridArea.append(child);
 943
 944         // If the child moved, we have to repaint it as well as any floating/positioned
 945         // descendants. An exception is if we need a layout. In this case, we know we're going to
 946         // repaint ourselves (and the child) anyway.
 947         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
 948             child->repaintDuringLayoutIfMoved(oldChildRect);
 949     }
 950
 951     for (size_t i = 0; i < sizingData.rowTracks.size(); ++i)
 952         setLogicalHeight(logicalHeight() + sizingData.rowTracks[i].m_usedBreadth);
 953
 954     // Min / max logical height is handled by the call to updateLogicalHeight in layoutBlock.
 955
 956     setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
 957 }
 958
 959 GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox* gridItem) const
 960 {
 961     ASSERT(m_gridItemCoordinate.contains(gridItem));
 962     return m_gridItemCoordinate.get(gridItem);
 963 }
 964
 965 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox* child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
 966 {
 967     const GridCoordinate& coordinate = cachedGridCoordinate(child);
 968     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
 969     LayoutUnit gridAreaBreadth = 0;
 970     for (GridSpan::iterator trackPosition = span.begin(); trackPosition != span.end(); ++trackPosition)
 971         gridAreaBreadth += tracks[trackPosition.toInt()].m_usedBreadth;
 972     return gridAreaBreadth;
 973 }
 974
 975 void RenderGrid::populateGridPositions(const GridSizingData& sizingData)
 976 {
 977     m_columnPositions.resize(sizingData.columnTracks.size() + 1);
 978     m_columnPositions[0] = borderAndPaddingStart();
 979     for (size_t i = 0; i < m_columnPositions.size() - 1; ++i)
 980         m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].m_usedBreadth;
 981
 982     m_rowPositions.resize(sizingData.rowTracks.size() + 1);
 983     m_rowPositions[0] = borderAndPaddingBefore();
 984     for (size_t i = 0; i < m_rowPositions.size() - 1; ++i)
 985         m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].m_usedBreadth;
 986 }
 987
 988 LayoutUnit RenderGrid::startOfColumnForChild(const RenderBox* child) const
 989 {
 990     const GridCoordinate& coordinate = cachedGridCoordinate(child);
 991     LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
 992     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
 993     // FIXME: This should account for the grid item's <overflow-position>.
 994     return startOfColumn + marginStartForChild(child);
 995 }
 996
 997 LayoutUnit RenderGrid::endOfColumnForChild(const RenderBox* child) const
 998 {
 999     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1000     LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
1001     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1002     LayoutUnit columnPosition = startOfColumn + marginStartForChild(child);
1003
1004     LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()];
1005     // FIXME: This should account for the grid item's <overflow-position>.
1006     return columnPosition + std::max<LayoutUnit>(0, endOfColumn - m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()] - child->logicalWidth());
1007 }
1008
1009 LayoutUnit RenderGrid::columnPositionAlignedWithGridContainerStart(const RenderBox* child) const
1010 {
1011     if (style()->isLeftToRightDirection())
1012         return startOfColumnForChild(child);
1013
1014     return endOfColumnForChild(child);
1015 }
1016
1017 LayoutUnit RenderGrid::columnPositionAlignedWithGridContainerEnd(const RenderBox* child) const
1018 {
1019     if (!style()->isLeftToRightDirection())
1020         return startOfColumnForChild(child);
1021
1022     return endOfColumnForChild(child);
1023 }
1024
1025 LayoutUnit RenderGrid::centeredColumnPositionForChild(const RenderBox* child) const
1026 {
1027     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1028     LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
1029     LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()];
1030     LayoutUnit columnPosition = startOfColumn + marginStartForChild(child);
1031     return columnPosition + std::max<LayoutUnit>(0, endOfColumn - startOfColumn - child->logicalWidth()) / 2;
1032 }
1033
1034 LayoutUnit RenderGrid::columnPositionForChild(const RenderBox* child) const
1035 {
1036     ItemPosition childJustifySelf = child->style()->justifySelf();
1037     switch (childJustifySelf) {
1038     case ItemPositionSelfStart:
1039         // self-start is based on the child's direction. That's why we need to check against the grid container's direction.
1040         if (child->style()->direction() != style()->direction())
1041             return columnPositionAlignedWithGridContainerEnd(child);
1042
1043         return columnPositionAlignedWithGridContainerStart(child);
1044     case ItemPositionSelfEnd:
1045         // self-end is based on the child's direction. That's why we need to check against the grid container's direction.
1046         if (child->style()->direction() != style()->direction())
1047             return columnPositionAlignedWithGridContainerStart(child);
1048
1049         return columnPositionAlignedWithGridContainerEnd(child);
1050
1051     case ItemPositionFlexStart:
1052     case ItemPositionFlexEnd:
1053         // Only used in flex layout, for other layout, it's equivalent to 'start'.
1054         return columnPositionAlignedWithGridContainerStart(child);
1055
1056     case ItemPositionLeft:
1057         // If the property's axis is not parallel with the inline axis, this is equivalent to ‘start’.
1058         if (!isHorizontalWritingMode())
1059             return columnPositionAlignedWithGridContainerStart(child);
1060
1061         if (style()->isLeftToRightDirection())
1062             return columnPositionAlignedWithGridContainerStart(child);
1063
1064         return columnPositionAlignedWithGridContainerEnd(child);
1065     case ItemPositionRight:
1066         // If the property's axis is not parallel with the inline axis, this is equivalent to ‘start’.
1067         if (!isHorizontalWritingMode())
1068             return columnPositionAlignedWithGridContainerStart(child);
1069
1070         if (style()->isLeftToRightDirection())
1071             return columnPositionAlignedWithGridContainerEnd(child);
1072
1073         return columnPositionAlignedWithGridContainerStart(child);
1074
1075     case ItemPositionCenter:
1076         return centeredColumnPositionForChild(child);
1077     case ItemPositionStart:
1078         return columnPositionAlignedWithGridContainerStart(child);
1079     case ItemPositionEnd:
1080         return columnPositionAlignedWithGridContainerEnd(child);
1081
1082     case ItemPositionAuto:
1083     case ItemPositionStretch:
1084     case ItemPositionBaseline:
1085         // FIXME: Implement the previous values. For now, we always start align the child.
1086         return startOfColumnForChild(child);
1087     }
1088
1089     ASSERT_NOT_REACHED();
1090     return 0;
1091 }
1092
1093 LayoutUnit RenderGrid::rowPositionForChild(const RenderBox* child) const
1094 {
1095     const GridCoordinate& coordinate = cachedGridCoordinate(child);
1096
1097     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1098     LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()];
1099     LayoutUnit rowPosition = startOfRow + marginBeforeForChild(child);
1100
1101     // FIXME: This function should account for 'align-self'.
1102
1103     return rowPosition;
1104 }
1105
1106 LayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox* child) const
1107 {
1108     return LayoutPoint(columnPositionForChild(child), rowPositionForChild(child));
1109 }
1110
1111 static GridSpan dirtiedGridAreas(const Vector<LayoutUnit>& coordinates, LayoutUnit start, LayoutUnit end)
1112 {
1113     // This function does a binary search over the coordinates.
1114     // FIXME: This doesn't work with grid items overflowing their grid areas and should be tested & fixed.
1115
1116     size_t startGridAreaIndex = std::upper_bound(coordinates.begin(), coordinates.end() - 1, start) - coordinates.begin();
1117     if (startGridAreaIndex > 0)
1118         --startGridAreaIndex;
1119
1120     size_t endGridAreaIndex = std::upper_bound(coordinates.begin() + startGridAreaIndex, coordinates.end() - 1, end) - coordinates.begin();
1121     if (endGridAreaIndex > 0)
1122         --endGridAreaIndex;
1123
1124     return GridSpan(startGridAreaIndex, endGridAreaIndex);
1125 }
1126
1127 class GridCoordinateSorter {
1128 public:
1129     GridCoordinateSorter(RenderGrid* renderer) : m_renderer(renderer) { }
1130
1131     bool operator()(const RenderBox* firstItem, const RenderBox* secondItem) const
1132     {
1133         GridCoordinate first = m_renderer->cachedGridCoordinate(firstItem);
1134         GridCoordinate second = m_renderer->cachedGridCoordinate(secondItem);
1135
1136         if (first.rows.resolvedInitialPosition < second.rows.resolvedInitialPosition)
1137             return true;
1138         if (first.rows.resolvedInitialPosition > second.rows.resolvedInitialPosition)
1139             return false;
1140         return first.columns.resolvedFinalPosition < second.columns.resolvedFinalPosition;
1141     }
1142 private:
1143     RenderGrid* m_renderer;
1144 };
1145
1146 static inline bool isInSameRowBeforeDirtyArea(const GridCoordinate& coordinate, const GridResolvedPosition& row, const GridSpan& dirtiedColumns)
1147 {
1148     return coordinate.rows.resolvedInitialPosition == row && coordinate.columns.resolvedInitialPosition < dirtiedColumns.resolvedInitialPosition;
1149 }
1150
1151 static inline bool isInSameRowAfterDirtyArea(const GridCoordinate& coordinate, const GridResolvedPosition& row, const GridSpan& dirtiedColumns)
1152 {
1153     return coordinate.rows.resolvedInitialPosition == row && coordinate.columns.resolvedInitialPosition >= dirtiedColumns.resolvedFinalPosition;
1154 }
1155
1156 static inline bool rowIsBeforeDirtyArea(const GridCoordinate& coordinate, const GridSpan& dirtiedRows)
1157 {
1158     return coordinate.rows.resolvedInitialPosition < dirtiedRows.resolvedInitialPosition;
1159 }
1160
1161 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
1162 {
1163     ASSERT_WITH_SECURITY_IMPLICATION(!gridIsDirty());
1164
1165     LayoutRect localRepaintRect = paintInfo.rect;
1166     localRepaintRect.moveBy(-paintOffset);
1167
1168     GridSpan dirtiedColumns = dirtiedGridAreas(m_columnPositions, localRepaintRect.x(), localRepaintRect.maxX());
1169     GridSpan dirtiedRows = dirtiedGridAreas(m_rowPositions, localRepaintRect.y(), localRepaintRect.maxY());
1170
1171     // Sort the overflowing grid items according to their positions in the grid. We collect items during the layout
1172     // process following DOM's order but we have to paint following grid's.
1173     std::stable_sort(m_gridItemsOverflowingGridArea.begin(), m_gridItemsOverflowingGridArea.end(), GridCoordinateSorter(this));
1174
1175     OrderIterator paintIterator(this);
1176     {
1177         OrderIteratorPopulator populator(paintIterator);
1178         Vector<RenderBox*>::const_iterator overflowIterator = m_gridItemsOverflowingGridArea.begin();
1179         Vector<RenderBox*>::const_iterator end = m_gridItemsOverflowingGridArea.end();
1180
1181         for (; overflowIterator != end && rowIsBeforeDirtyArea(cachedGridCoordinate(*overflowIterator), dirtiedRows); ++overflowIterator) {
1182             if ((*overflowIterator)->frameRect().intersects(localRepaintRect))
1183                 populator.storeChild(*overflowIterator);
1184         }
1185
1186         for (GridSpan::iterator row = dirtiedRows.begin(); row != dirtiedRows.end(); ++row) {
1187
1188             for (; overflowIterator != end && isInSameRowBeforeDirtyArea(cachedGridCoordinate(*overflowIterator), row, dirtiedColumns); ++overflowIterator) {
1189                 if ((*overflowIterator)->frameRect().intersects(localRepaintRect))
1190                     populator.storeChild(*overflowIterator);
1191             }
1192
1193             for (GridSpan::iterator column = dirtiedColumns.begin(); column != dirtiedColumns.end(); ++column) {
1194                 const Vector<RenderBox*, 1>& children = m_grid[row.toInt()][column.toInt()];
1195                 // FIXME: If we start adding spanning children in all grid areas they span, this
1196                 // would make us paint them several times, which is wrong!
1197                 for (size_t j = 0; j < children.size(); ++j) {
1198                     populator.storeChild(children[j]);
1199                     // Do not paint overflowing grid items twice.
1200                     if (overflowIterator != end && *overflowIterator == children[j])
1201                         ++overflowIterator;
1202                 }
1203             }
1204
1205             for (; overflowIterator != end && isInSameRowAfterDirtyArea(cachedGridCoordinate(*overflowIterator), row, dirtiedColumns); ++overflowIterator) {
1206                 if ((*overflowIterator)->frameRect().intersects(localRepaintRect))
1207                     populator.storeChild(*overflowIterator);
1208             }
1209         }
1210
1211         for (; overflowIterator != end; ++overflowIterator) {
1212             if ((*overflowIterator)->frameRect().intersects(localRepaintRect))
1213                 populator.storeChild(*overflowIterator);
1214         }
1215     }
1216
1217     for (RenderBox* child = paintIterator.first(); child; child = paintIterator.next())
1218         paintChild(child, paintInfo, paintOffset);
1219 }
1220
1221 const char* RenderGrid::renderName() const
1222 {
1223     if (isFloating())
1224         return "RenderGrid (floating)";
1225     if (isOutOfFlowPositioned())
1226         return "RenderGrid (positioned)";
1227     if (isAnonymous())
1228         return "RenderGrid (generated)";
1229     if (isRelPositioned())
1230         return "RenderGrid (relative positioned)";
1231     return "RenderGrid";
1232 }
1233
1234 } // namespace WebCore