[CSS Grid Layout] Speed up painting on large grids

Source/core/rendering/RenderGrid.cpp

 /*
  * Copyright (C) 2011 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 838 matching lines @@
 {
     placeItemsOnGrid();
 
     Vector<GridTrack> columnTracks(gridColumnCount());
     Vector<GridTrack> rowTracks(gridRowCount());
     computedUsedBreadthOfGridTracks(ForColumns, columnTracks, rowTracks);
     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, columnTracks));
     computedUsedBreadthOfGridTracks(ForRows, columnTracks, rowTracks);
     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, rowTracks));
 
+    populateGridPositions(columnTracks, rowTracks);
+
     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
         // Because the grid area cannot be styled, we don't need to adjust
         // the grid breadth to account for 'box-sizing'.
         LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
         LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
 
         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(child, ForRows, rowTracks);
 
         SubtreeLayoutScope layoutScope(child);
@@ skipping 242 matching lines @@
 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox* child, TrackSizingDirection direction, const Vector<GridTrack>& tracks) const
 {
     const GridCoordinate& coordinate = cachedGridCoordinate(child);
     const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
     LayoutUnit gridAreaBreadth = 0;
     for (size_t trackIndex = span.initialPositionIndex; trackIndex <= span.finalPositionIndex; ++trackIndex)
         gridAreaBreadth += tracks[trackIndex].m_usedBreadth;
     return gridAreaBreadth;
 }
 
+void RenderGrid::populateGridPositions(const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks)
+{
+    m_columnPositions.resize(columnTracks.size() + 1);
+    m_columnPositions[0] = borderAndPaddingStart();
+    for (size_t i = 0; i < m_columnPositions.size() - 1; ++i)
+        m_columnPositions[i + 1] = m_columnPositions[i] + columnTracks[i].m_usedBreadth;
+
+    m_rowPositions.resize(rowTracks.size() + 1);
+    m_rowPositions[0] = borderAndPaddingBefore();
+    for (size_t i = 0; i < m_rowPositions.size() - 1; ++i)
+        m_rowPositions[i + 1] = m_rowPositions[i] + rowTracks[i].m_usedBreadth;
+}
+
 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks)
 {
     const GridCoordinate& coordinate = cachedGridCoordinate(child);
+    ASSERT(coordinate.columns.initialPositionIndex < columnTracks.size());
+    ASSERT(coordinate.rows.initialPositionIndex < rowTracks.size());
 
     // The grid items should be inside the grid container's border box, that's why they need to be shifted.
-    LayoutPoint offset(borderAndPaddingStart() + marginStartForChild(child), borderAndPaddingBefore() + marginBeforeForChild(child));
-    // FIXME: |columnTrack| and |rowTrack| should be smaller than our column / row count.
-    for (size_t i = 0; i < coordinate.columns.initialPositionIndex && i < columnTracks.size(); ++i)
-        offset.setX(offset.x() + columnTracks[i].m_usedBreadth);
-    for (size_t i = 0; i < coordinate.rows.initialPositionIndex && i < rowTracks.size(); ++i)
-        offset.setY(offset.y() + rowTracks[i].m_usedBreadth);
+    return LayoutPoint(m_columnPositions[coordinate.columns.initialPositionIndex] + marginStartForChild(child), m_rowPositions[coordinate.rows.initialPositionIndex] + marginBeforeForChild(child));
+}
 
-    return offset;
+static GridSpan dirtiedGridAreas(const Vector<LayoutUnit>& coordinates, LayoutUnit start, LayoutUnit end)
+{
+    // This function does a binary search over the coordinates.
+    // FIXME: This doesn't work with grid items overflowing their grid areas and should be tested & fixed.
+
+    size_t startGridAreaIndex = std::upper_bound(coordinates.begin(), coordinates.end() - 1, start) - coordinates.begin();
+    if (startGridAreaIndex > 0)
+        --startGridAreaIndex;
+
+    size_t endGridAreaIndex = std::upper_bound(coordinates.begin() + startGridAreaIndex, coordinates.end() - 1, end) - coordinates.begin();
+    return GridSpan(startGridAreaIndex, endGridAreaIndex);
 }
 
 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
 {
-    for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next())
+    ASSERT_WITH_SECURITY_IMPLICATION(!gridIsDirty());
+
+    LayoutRect localRepaintRect = paintInfo.rect;
+    localRepaintRect.moveBy(-paintOffset);
+
+    GridSpan dirtiedColumns = dirtiedGridAreas(m_columnPositions, localRepaintRect.x(), localRepaintRect.maxX());
+    GridSpan dirtiedRows = dirtiedGridAreas(m_rowPositions, localRepaintRect.y(), localRepaintRect.maxY());
+
+    OrderIterator paintIterator(this);
+    {
+        OrderIteratorPopulator populator(paintIterator);
+
+        for (size_t row = dirtiedRows.initialPositionIndex; row < dirtiedRows.finalPositionIndex; ++row) {
+            for (size_t column = dirtiedColumns.initialPositionIndex; column < dirtiedColumns.finalPositionIndex; ++column) {
+                const Vector<RenderBox*, 1> children = m_grid[row][column];
+                // FIXME: If we start adding spanning children in all grid areas they span, this
+                // would make us paint them several times, which is wrong!
+                for (size_t j = 0; j < children.size(); ++j)
+                    populator.storeChild(children[j]);
+            }
+        }
+    }
+
+    for (RenderBox* child = paintIterator.first(); child; child = paintIterator.next())
         paintChild(child, paintInfo, paintOffset);
 }
 
 const char* RenderGrid::renderName() const
 {
     if (isFloating())
         return "RenderGrid (floating)";
     if (isOutOfFlowPositioned())
         return "RenderGrid (positioned)";
     if (isAnonymous())
         return "RenderGrid (generated)";
     if (isRelPositioned())
         return "RenderGrid (relative positioned)";
     return "RenderGrid";
 }
 
 } // namespace WebCore