[CSS Grid Layout] Sort items by span when resolving content-based track sizing functions
authorsvillar@igalia.com <svillar@igalia.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Sep 2014 14:20:46 +0000 (14:20 +0000)
committersvillar@igalia.com <svillar@igalia.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Sep 2014 14:20:46 +0000 (14:20 +0000)
https://bugs.webkit.org/show_bug.cgi?id=135701

Reviewed by Darin Adler.

Source/WebCore:

Section 10.4 of the specs mentions that we should first treat non
spanning items and then incrementally proceed with items with
greater spans when resolving the track breaths in the Track Sizing
Algorithm.

As a nice side effect we're removing the multiple processing of
spanning grid items caused by GridIterator (it returns the same
item as many times as the number of cells it spans). This adds a
~4% performance penalty in auto-grid-lots-of-data.html mainly due
to the use of a hash to remove duplicates.

Test: fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution.html

* rendering/RenderGrid.cpp:
(WebCore::RenderGrid::gridItemSpan):
(WebCore::gridItemWithSpanSorter):
(WebCore::uniquePointerInPair):
(WebCore::RenderGrid::resolveContentBasedTrackSizingFunctions):
* rendering/RenderGrid.h:

LayoutTests:

Tests that check that items are sorted by span to resolve content
based track sizing functions instead of directly using DOM order.

* fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution-expected.txt: Added.
* fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173620 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution-expected.txt [new file with mode: 0644]
LayoutTests/fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/rendering/RenderGrid.cpp
Source/WebCore/rendering/RenderGrid.h

index bba8596..2c6f43a 100644 (file)
@@ -1,3 +1,16 @@
+2014-08-07  Sergio Villar Senin  <svillar@igalia.com>
+
+        [CSS Grid Layout] Sort items by span when resolving content-based track sizing functions
+        https://bugs.webkit.org/show_bug.cgi?id=135701
+
+        Reviewed by Darin Adler.
+
+        Tests that check that items are sorted by span to resolve content
+        based track sizing functions instead of directly using DOM order.
+
+        * fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution-expected.txt: Added.
+        * fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution.html: Added.
+
 2014-09-12  Sergio Villar Senin  <svillar@igalia.com>
 
         [CSS Grid Layout] Crash at CSSParser::parseGridTemplateRowsAndAreas
diff --git a/LayoutTests/fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution-expected.txt b/LayoutTests/fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution-expected.txt
new file mode 100644 (file)
index 0000000..77753cc
--- /dev/null
@@ -0,0 +1,27 @@
+PASS grid-template-columns is 60px 20px after grid row swap.
+PASS grid-template-columns is 76px 50px after grid row swap.
+PASS grid-template-columns is 60px 16px after grid row swap.
+PASS grid-template-columns is 68px 16px after grid row swap.
+PASS grid-template-columns is 76px 8px after grid row swap.
+PASS grid-template-columns is 68px 16px after grid row swap.
+PASS grid-template-columns is 60px 16px after grid row swap.
+PASS grid-template-columns is 60px 16px after grid row swap.
+PASS successfullyParsed is true
+
+TEST COMPLETE
+XXXXX
+XXX XXX
+XXXXX
+XXX XXX
+XXXXX
+XXX XXX
+XXXXX
+XXX XXX
+XXXXX
+XXX XXX
+XXXXX
+XXX XXX
+XXXXX
+XXX XXX
+XXXXX
+XXX XXX
diff --git a/LayoutTests/fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution.html b/LayoutTests/fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution.html
new file mode 100644 (file)
index 0000000..db00091
--- /dev/null
@@ -0,0 +1,122 @@
+<!DOCTYPE html>
+<html>
+<head>
+<link href="resources/grid.css" rel="stylesheet"/>
+<style>
+.gridFixedMinContentAndFixedMaxContent {
+     -webkit-grid-template-columns: minmax(20px, -webkit-min-content) minmax(20px, -webkit-max-content);
+}
+.gridMaxContentFixedAndMinContentFixed {
+     -webkit-grid-template-columns: minmax(-webkit-max-content, 50px) minmax(-webkit-min-content, 50px);
+}
+.gridFixedMinContentAndAuto {
+     -webkit-grid-template-columns: minmax(20px, -webkit-min-content) auto;
+}
+.gridFixedMaxContentAndAuto {
+     -webkit-grid-template-columns: minmax(20px, -webkit-max-content) auto;
+}
+.gridMaxContentAndAuto {
+     -webkit-grid-template-columns: -webkit-max-content auto;
+}
+.gridAutoAndMaxContent {
+     -webkit-grid-template-columns: auto -webkit-max-content;
+}
+.gridMinContentAndAuto {
+     -webkit-grid-template-columns: -webkit-min-content auto;
+}
+.gridAutoAndMinContent {
+     -webkit-grid-template-columns: -webkit-min-content auto;
+}
+.spanTwo {
+     -webkit-grid-column: 1 / 3;
+}
+</style>
+<script src="../../resources/js-test.js"></script>
+</head>
+<body>
+<div style="position: relative">
+    <div id="gridFixedMinContentAndFixedMaxContent" class="grid gridFixedMinContentAndFixedMaxContent">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+<div style="position: relative">
+    <div id="gridMaxContentFixedAndMinContentFixed" class="grid gridMaxContentFixedAndMinContentFixed">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+<div style="position: relative">
+    <div id="gridFixedMinContentAndAuto" class="grid gridFixedMinContentAndAuto">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+<div style="position: relative">
+    <div id="gridFixedMaxContentAndAuto" class="grid gridFixedMaxContentAndAuto">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+<div style="position: relative">
+    <div id="gridMaxContentAndAuto" class="grid gridMaxContentAndAuto">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+<div style="position: relative">
+    <div id="gridAutoAndMaxContent" class="grid gridAutoAndMaxContent">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+<div style="position: relative">
+    <div id="gridMinContentAndAuto" class="grid gridMinContentAndAuto">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+<div style="position: relative">
+    <div id="gridAutoAndMinContent" class="grid gridAutoAndMinContent">
+       <div class="firstRowFirstColumn">XXXXX</div>
+       <div class="spanTwo secondRowFirstColumn">XXX XXX</div>
+    </div>
+</div>
+
+</body>
+<script src="resources/grid-definitions-parsing-utils.js"></script>
+<script>
+
+function checkTrackBreadthAfterItemRowSwap(gridId)
+{
+     window.gridElement = document.getElementById(gridId);
+     var oldValue = getComputedStyle(gridElement, '').getPropertyValue('-webkit-grid-template-columns');
+     var firstChildRow = getComputedStyle(gridElement.children[0],'').getPropertyValue('-webkit-grid-row');
+     gridElement.children[0].style.webkitGridRow = getComputedStyle(gridElement.children[1],'').getPropertyValue('-webkit-grid-row');
+     gridElement.children[1].style.webkitGridRow = firstChildRow;
+     var newValue = getComputedStyle(gridElement, '').getPropertyValue('-webkit-grid-template-columns');
+
+     if (newValue == oldValue)
+         testPassed("grid-template-columns is " + newValue + " after grid row swap.");
+     else
+         testFailed("grid-template-columns should be " + oldValue + ". Was " + newValue + ".");
+}
+
+checkTrackBreadthAfterItemRowSwap("gridFixedMinContentAndFixedMaxContent");
+checkTrackBreadthAfterItemRowSwap("gridMaxContentFixedAndMinContentFixed");
+checkTrackBreadthAfterItemRowSwap("gridFixedMinContentAndAuto");
+checkTrackBreadthAfterItemRowSwap("gridFixedMaxContentAndAuto");
+checkTrackBreadthAfterItemRowSwap("gridMaxContentAndAuto");
+checkTrackBreadthAfterItemRowSwap("gridAutoAndMaxContent");
+checkTrackBreadthAfterItemRowSwap("gridMinContentAndAuto");
+checkTrackBreadthAfterItemRowSwap("gridAutoAndMinContent");
+
+</script>
+</html>
index 66b7978..5de34ec 100644 (file)
@@ -1,3 +1,30 @@
+2014-08-07  Sergio Villar Senin  <svillar@igalia.com>
+
+        [CSS Grid Layout] Sort items by span when resolving content-based track sizing functions
+        https://bugs.webkit.org/show_bug.cgi?id=135701
+
+        Reviewed by Darin Adler.
+
+        Section 10.4 of the specs mentions that we should first treat non
+        spanning items and then incrementally proceed with items with
+        greater spans when resolving the track breaths in the Track Sizing
+        Algorithm.
+
+        As a nice side effect we're removing the multiple processing of
+        spanning grid items caused by GridIterator (it returns the same
+        item as many times as the number of cells it spans). This adds a
+        ~4% performance penalty in auto-grid-lots-of-data.html mainly due
+        to the use of a hash to remove duplicates.
+
+        Test: fast/css-grid-layout/grid-item-order-in-content-sized-columns-resolution.html
+
+        * rendering/RenderGrid.cpp:
+        (WebCore::RenderGrid::gridItemSpan):
+        (WebCore::gridItemWithSpanSorter):
+        (WebCore::uniquePointerInPair):
+        (WebCore::RenderGrid::resolveContentBasedTrackSizingFunctions):
+        * rendering/RenderGrid.h:
+
 2014-09-15  Zan Dobersek  <zdobersek@igalia.com>
 
         [GTK][CMake] Build WebCore with Wayland-specific include directories, libraries
index 493d1d0..659f664 100644 (file)
@@ -531,17 +531,50 @@ LayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirec
     return logicalContentHeightForChild(child, columnTracks);
 }
 
+class GridItemWithSpan {
+public:
+    GridItemWithSpan(RenderBox& gridItem, GridCoordinate coordinate, GridTrackSizingDirection direction)
+        : m_gridItem(gridItem)
+        , m_coordinate(coordinate)
+    {
+        const GridSpan& span = (direction == ForRows) ? coordinate.rows : coordinate.columns;
+        m_span = span.resolvedFinalPosition.toInt() - span.resolvedInitialPosition.toInt() + 1;
+    }
+
+    RenderBox& gridItem() const { return m_gridItem; }
+    GridCoordinate coordinate() const { return m_coordinate; }
+
+    bool operator<(const GridItemWithSpan other) const
+    {
+        return m_span < other.m_span;
+    }
+
+private:
+    std::reference_wrapper<RenderBox> m_gridItem;
+    GridCoordinate m_coordinate;
+    size_t m_span;
+};
+
 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData)
 {
     // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track.
 
     for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
         GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]);
+        HashSet<RenderBox*> itemsSet;
+        Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
+
         while (RenderBox* gridItem = iterator.nextGridItem()) {
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
-            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
+            if (itemsSet.add(gridItem).isNewEntry)
+                itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, cachedGridCoordinate(*gridItem), direction));
+        }
+        std::stable_sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end());
+
+        for (auto& itemWithSpan : itemsSortedByIncreasingSpan) {
+            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
+            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
+            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
+            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, itemWithSpan, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
         }
 
         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[i] : sizingData.rowTracks[i];
@@ -550,9 +583,9 @@ void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirectio
     }
 }
 
-void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, RenderBox& gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
+void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, GridItemWithSpan& gridItemWithSpan, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
 {
-    const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
+    const GridCoordinate& coordinate = gridItemWithSpan.coordinate();
     const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
     const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
 
@@ -569,7 +602,7 @@ void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizing
     if (sizingData.filteredTracks.isEmpty())
         return;
 
-    LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks);
+    LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItemWithSpan.gridItem(), direction, sizingData.columnTracks);
     for (GridResolvedPosition trackPositionForSpace = initialTrackPosition; trackPositionForSpace <= finalTrackPosition; ++trackPositionForSpace) {
         GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPositionForSpace.toInt()] : sizingData.rowTracks[trackPositionForSpace.toInt()];
         additionalBreadthSpace -= (track.*trackGetter)();
index 90f3d0f..97f474c 100644 (file)
@@ -38,6 +38,7 @@ namespace WebCore {
 class GridCoordinate;
 class GridSpan;
 class GridTrack;
+class GridItemWithSpan;
 
 class RenderGrid final : public RenderBlock {
 public:
@@ -90,7 +91,7 @@ private:
     typedef LayoutUnit (GridTrack::* AccumulatorGetter)() const;
     typedef void (GridTrack::* AccumulatorGrowFunction)(LayoutUnit);
     typedef bool (GridTrackSize::* FilterFunction)() const;
-    void resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection, GridSizingData&, RenderBox&, FilterFunction, SizingFunction, AccumulatorGetter, AccumulatorGrowFunction);
+    void resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection, GridSizingData&, GridItemWithSpan&, FilterFunction, SizingFunction, AccumulatorGetter, AccumulatorGrowFunction);
     void distributeSpaceToTracks(Vector<GridTrack*>&, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter, AccumulatorGrowFunction, GridSizingData&, LayoutUnit& availableLogicalSpace);
 
     double computeNormalizedFractionBreadth(Vector<GridTrack>&, const GridSpan& tracksSpan, GridTrackSizingDirection, LayoutUnit availableLogicalSpace) const;