From 54a32beb556ec6fb94d516e2949b80b14dd780a3 Mon Sep 17 00:00:00 2001
From: "rego@igalia.com" <rego@igalia.com@bbb929c8-8fbe-4397-9dbb-9b2b20218538>
Date: Wed, 16 Jul 2014 10:48:00 +0000
Subject: [CSS Grid Layout] Support sparse in auto-placement algorithm

Sparse mode for auto-placement algorithm was not implemented yet.

This patch implements sparse mode for auto-placement algorithm. It keeps
track of the auto-placement cursor in
RenderGrid::placeAutoMajorAxisItemsOnGrid() and updates it accordingly
when auto-positioned items are placed.
If we're in dense mode it resets the cursor after each item.

GridIterator has been adapted to look for empty areas from a given
position in both directions.

Test cases have been adapted accordingly, adding new cases to cover both
sparse and dense options.

TEST=fast/css-grid-layout/grid-auto-flow-sparse.html

BUG=384099

Review URL: https://codereview.chromium.org/362733002

git-svn-id: svn://svn.chromium.org/blink/trunk@178262 bbb929c8-8fbe-4397-9dbb-9b2b20218538
---
 .../css-grid-layout/grid-auto-flow-resolution.html |   4 +-
 .../grid-auto-flow-sparse-expected.txt             |  10 ++
 .../css-grid-layout/grid-auto-flow-sparse.html     | 109 +++++++++++++++++++++
 ...ainer-change-explicit-grid-recompute-child.html |   2 +-
 ...er-change-named-grid-lines-recompute-child.html |   2 +-
 .../grid-item-auto-placement-automatic-span.html   |  14 +--
 .../grid-item-auto-placement-definite-span.html    |   4 +-
 .../grid-item-removal-auto-placement-update.html   |   4 +-
 ...rid-lines-with-named-grid-areas-resolution.html |   4 +-
 .../fast/css-grid-layout/resources/grid.css        |  34 +++++++
 .../WebKit/Source/core/rendering/RenderGrid.cpp    |  49 ++++++---
 .../WebKit/Source/core/rendering/RenderGrid.h      |   2 +-
 12 files changed, 206 insertions(+), 32 deletions(-)
 create mode 100644 third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse-expected.txt
 create mode 100644 third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse.html

(limited to 'third_party')

diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-resolution.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-resolution.html
index 49c9988..4d27afd 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-resolution.html
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-resolution.html
@@ -76,7 +76,7 @@
 </div>
 
 <div class="unconstrainedContainer">
-    <div class="grid bigGrid gridAutoFlowColumn">
+    <div class="grid bigGrid gridAutoFlowColumnDense">
         <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea autoRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100">XXXXX XXXXX XXXXX</div>
@@ -86,7 +86,7 @@
 </div>
 
 <div class="unconstrainedContainer">
-    <div class="grid bigGrid gridAutoFlowRow">
+    <div class="grid bigGrid gridAutoFlowRowDense">
         <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="150">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea firstRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100">XXXXX XXXXX XXXXX</div>
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse-expected.txt b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse-expected.txt
new file mode 100644
index 0000000..52a64ad
--- /dev/null
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse-expected.txt
@@ -0,0 +1,10 @@
+This test checks that the auto-placement algorithm is sparse by default.
+
+PASS
+PASS
+PASS
+PASS
+PASS
+PASS
+PASS
+PASS
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse.html
new file mode 100644
index 0000000..907b3ce
--- /dev/null
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-auto-flow-sparse.html
@@ -0,0 +1,109 @@
+<!DOCTYPE html>
+<html>
+<link href="resources/grid.css" rel="stylesheet">
+<style>
+.grid {
+    grid-template-columns: 50px 100px 150px 200px;
+    grid-template-rows: 50px 100px 150px 200px;
+}
+
+.unconstrainedContainer {
+    /* For accurate x / y offset. */
+    position: relative;
+}
+</style>
+<script src="../../resources/check-layout.js"></script>
+<body onload="checkLayout('.grid')">
+
+<p>This test checks that the auto-placement algorithm is sparse by default.</p>
+
+<div class="unconstrainedContainer">
+    <div class="grid">
+        <div class="sizedToGridArea firstRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowAutoColumnSpanning2" data-offset-x="150" data-offset-y="0" data-expected-width="350" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowAutoColumnSpanning2" data-offset-x="50" data-offset-y="50" data-expected-width="250" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowAutoColumnSpanning2" data-offset-x="0" data-offset-y="150" data-expected-width="150" data-expected-height="150"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="150" data-offset-y="150" data-expected-width="150" data-expected-height="150"></div>
+    </div>
+</div>
+
+<div class="unconstrainedContainer">
+    <div class="grid">
+        <div class="sizedToGridArea autoRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowAutoColumnSpanning2" data-offset-x="150" data-offset-y="0" data-expected-width="350" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowThirdColumn" data-offset-x="150" data-offset-y="50" data-expected-width="150" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="300" data-offset-y="50" data-expected-width="200" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="150"></div>
+        <div class="sizedToGridArea autoRowSpanning2AutoColumnSpanning3" data-offset-x="50" data-offset-y="150" data-expected-width="450" data-expected-height="350"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="0" data-offset-y="300" data-expected-width="50" data-expected-height="200"></div>
+    </div>
+</div>
+
+<div class="unconstrainedContainer">
+    <div class="grid">
+        <div class="sizedToGridArea firstRowAutoColumn" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50"></div>
+        <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="150"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="50" data-offset-y="150" data-expected-width="100" data-expected-height="150"></div>
+    </div>
+</div>
+
+<div class="unconstrainedContainer">
+    <div class="grid">
+        <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="150"></div>
+        <div class="sizedToGridArea firstRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea firstRowAutoColumn" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="50" data-offset-y="150" data-expected-width="100" data-expected-height="150"></div>
+    </div>
+</div>
+
+<div class="unconstrainedContainer">
+    <div class="grid gridAutoFlowColumn">
+        <div class="sizedToGridArea secondRowFirstColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowSpanning2AutoColumn" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="350"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowSpanning2AutoColumn" data-offset-x="50" data-offset-y="50" data-expected-width="100" data-expected-height="250"></div>
+        <div class="sizedToGridArea autoRowSpanning2AutoColumn" data-offset-x="150" data-offset-y="0" data-expected-width="150" data-expected-height="150"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="150" data-offset-y="150" data-expected-width="150" data-expected-height="150"></div>
+    </div>
+</div>
+
+<div class="unconstrainedContainer">
+    <div class="grid gridAutoFlowColumn">
+        <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowSpanning2AutoColumn" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="350"></div>
+        <div class="sizedToGridArea firstRowAutoColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea thirdRowAutoColumn" data-offset-x="50" data-offset-y="150" data-expected-width="100" data-expected-height="150"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="50" data-offset-y="300" data-expected-width="100" data-expected-height="200"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="150" data-offset-y="0" data-expected-width="150" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowSpanning3AutoColumnSpanning2" data-offset-x="150" data-offset-y="50" data-expected-width="350" data-expected-height="450"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="300" data-offset-y="0" data-expected-width="200" data-expected-height="50"></div>
+    </div>
+</div>
+
+<div class="unconstrainedContainer">
+    <div class="grid gridAutoFlowColumn">
+        <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea firstRowAutoColumn" data-offset-x="150" data-offset-y="0" data-expected-width="150" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="150" data-offset-y="50" data-expected-width="150" data-expected-height="100"></div>
+    </div>
+</div>
+
+<div class="unconstrainedContainer">
+    <div class="grid gridAutoFlowColumn">
+        <div class="sizedToGridArea firstRowAutoColumn" data-offset-x="150" data-offset-y="0" data-expected-width="150" data-expected-height="50"></div>
+        <div class="sizedToGridArea secondRowFirstColumn" data-offset-x="0" data-offset-y="50" data-expected-width="50" data-expected-height="100"></div>
+        <div class="sizedToGridArea autoRowSecondColumn" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50"></div>
+        <div class="sizedToGridArea autoRowAutoColumn" data-offset-x="150" data-offset-y="50" data-expected-width="150" data-expected-height="100"></div>
+    </div>
+</div>
+
+</body>
+</html>
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-explicit-grid-recompute-child.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-explicit-grid-recompute-child.html
index 95a67a3..a1305f5 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-explicit-grid-recompute-child.html
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-explicit-grid-recompute-child.html
@@ -4,7 +4,7 @@
 <script src="../../resources/check-layout.js"></script>
 <style>
 .grid {
-    grid-auto-flow: row;
+    grid-auto-flow: row dense;
 }
 #firstGridItem {
     grid-row: auto;
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-named-grid-lines-recompute-child.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-named-grid-lines-recompute-child.html
index 1e0a755..b9840f2 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-named-grid-lines-recompute-child.html
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-container-change-named-grid-lines-recompute-child.html
@@ -4,7 +4,7 @@
 <script src="../../resources/check-layout.js"></script>
 <style>
 .grid {
-    grid-auto-flow: row;
+    grid-auto-flow: row dense;
 }
 #firstGridItem {
     grid-row: auto;
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-automatic-span.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-automatic-span.html
index f8e96c3..930bbde 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-automatic-span.html
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-automatic-span.html
@@ -15,12 +15,6 @@
     grid-template-rows: 50px 100px (line) 200px (line);
 }
 
-.autoRowAutoColumnSpanning2 {
-    background-color: maroon;
-    grid-column: span 2;
-    grid-row: auto;
-}
-
 .autoRowAutoColumnSpanning3 {
     background-color: teal;
     grid-column: span 3;
@@ -91,7 +85,7 @@
 </div>
 
 <div style="position: relative">
-    <div class="grid gridAutoFlowRow">
+    <div class="grid gridAutoFlowRowDense">
         <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
         <div class="sizedToGridArea autoRowSecondColumn" data-offset-x="100" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
         <div class="sizedToGridArea autoRowThirdColumn" data-offset-x="200" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
@@ -119,7 +113,7 @@
 </div>
 
 <div style="position: relative">
-    <div class="grid gridAutoFlowRow gridNamedGridLinesColumns">
+    <div class="grid gridAutoFlowRowDense gridNamedGridLinesColumns">
         <div class="sizedToGridArea autoRowFirstColumn" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50"></div>
         <div class="sizedToGridArea autoRowAutoColumnSpanning2Line" data-offset-x="50" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
         <div class="sizedToGridArea autoRowSecondColumn" data-offset-x="50" data-offset-y="50" data-expected-width="100" data-expected-height="50"></div>
@@ -152,7 +146,7 @@
 </div>
 
 <div style="position: relative">
-    <div class="grid gridAutoFlowColumn">
+    <div class="grid gridAutoFlowColumnDense">
         <div class="sizedToGridArea firstRowAutoColumn" data-offset-x="0" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
         <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="100" data-expected-height="50"></div>
         <div class="sizedToGridArea thirdRowAutoColumn" data-offset-x="0" data-offset-y="100" data-expected-width="100" data-expected-height="50"></div>
@@ -180,7 +174,7 @@
 </div>
 
 <div style="position: relative">
-    <div class="grid gridAutoFlowColumn gridNamedGridLinesRows">
+    <div class="grid gridAutoFlowColumnDense gridNamedGridLinesRows">
         <div class="sizedToGridArea firstRowAutoColumn" data-offset-x="0" data-offset-y="0" data-expected-width="100" data-expected-height="50"></div>
         <div class="sizedToGridArea autoRowSpanning2LineAutoColumn" data-offset-x="0" data-offset-y="50" data-expected-width="100" data-expected-height="100"></div>
         <div class="sizedToGridArea secondRowAutoColumn" data-offset-x="100" data-offset-y="50" data-expected-width="100" data-expected-height="100"></div>
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-definite-span.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-definite-span.html
index 35e2ae1..a12db68 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-definite-span.html
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-auto-placement-definite-span.html
@@ -52,7 +52,7 @@
 <p>Thist test checks that span is supported in auto-placement for definite positions.</p>
 
 <div style="position: relative">
-    <div class="grid gridAutoFlowRow">
+    <div class="grid gridAutoFlowRowDense">
         <div class="sizedToGridArea autoRowFirstColumnSpanning2" data-offset-x="0" data-offset-y="0" data-expected-width="200" data-expected-height="50"></div>
         <div class="sizedToGridArea autoRowSecondColumnSpanning2" data-offset-x="100" data-offset-y="50" data-expected-width="200" data-expected-height="50"></div>
         <div class="sizedToGridArea autoRowFirstColumnSpanning3" data-offset-x="0" data-offset-y="100" data-expected-width="300" data-expected-height="50"></div>
@@ -72,7 +72,7 @@
 </div>
 
 <div style="position: relative">
-    <div class="grid gridAutoFlowColumn">
+    <div class="grid gridAutoFlowColumnDense">
         <div class="sizedToGridArea firstRowSpanning2AutoColumn" data-offset-x="0" data-offset-y="0" data-expected-width="100" data-expected-height="100"></div>
         <div class="sizedToGridArea secondRowSpanning2AutoColumn" data-offset-x="100" data-offset-y="50" data-expected-width="100" data-expected-height="100"></div>
         <div class="sizedToGridArea firstRowSpanning3AutoColumn" data-offset-x="200" data-offset-y="0" data-expected-width="100" data-expected-height="150"></div>
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-removal-auto-placement-update.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-removal-auto-placement-update.html
index 5e7e4f2..4effae8 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-removal-auto-placement-update.html
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/grid-item-removal-auto-placement-update.html
@@ -77,7 +77,7 @@ window.addEventListener("load", testRemovals, false);
 </div>
 
 <div class="unconstrainedContainer">
-    <div class="grid gridAutoFlowColumn" id="gridAutoFlowColumnWithAutoItems">
+    <div class="grid gridAutoFlowColumnDense" id="gridAutoFlowColumnWithAutoItems">
         <div class="sizedToGridArea autoRowFirstColumn">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea autoRowSecondColumn">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea secondRowAutoColumn">XXXXX XXXXX XXXXX</div>
@@ -87,7 +87,7 @@ window.addEventListener("load", testRemovals, false);
 </div>
 
 <div class="unconstrainedContainer">
-    <div class="grid gridAutoFlowRow" id="gridAutoFlowRowWithAutoAndFixedItems">
+    <div class="grid gridAutoFlowRowDense" id="gridAutoFlowRowWithAutoAndFixedItems">
         <div class="sizedToGridArea autoRowFirstColumn">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea firstRowSecondColumn">XXXXX XXXXX XXXXX</div>
         <div class="sizedToGridArea secondRowAutoColumn">XXXXX XXXXX XXXXX</div>
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/named-grid-lines-with-named-grid-areas-resolution.html b/third_party/WebKit/LayoutTests/fast/css-grid-layout/named-grid-lines-with-named-grid-areas-resolution.html
index f36175d..aa2cd93 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/named-grid-lines-with-named-grid-areas-resolution.html
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/named-grid-lines-with-named-grid-areas-resolution.html
@@ -107,7 +107,7 @@
 
 <!-- Check positioning using grid areas -->
 <div style="position: relative">
-  <div class="grid gridAreas gridNoLineNames">
+  <div class="grid gridAreas gridNoLineNames gridAutoFlowRowDense">
     <div class="sizedToGridArea" style="grid-column: d;" data-offset-x="150" data-offset-y="0" data-expected-width="200" data-expected-height="50"></div>
     <div class="sizedToGridArea" style="grid-row: d;" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="200"></div>
     <div class="sizedToGridArea" style="grid-column: c;" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50"></div>
@@ -125,7 +125,7 @@
 
 <!-- Use grid area's implicit line names if defined before explicitly named grid lines -->
 <div style="position: relative">
-  <div class="grid gridAreas gridWithNamedLineAfterGridArea">
+  <div class="grid gridAreas gridWithNamedLineAfterGridArea gridAutoFlowRowDense">
     <div class="sizedToGridArea" style="grid-column: d;" data-offset-x="150" data-offset-y="0" data-expected-width="200" data-expected-height="50"></div>
     <div class="sizedToGridArea" style="grid-row: d;" data-offset-x="0" data-offset-y="150" data-expected-width="50" data-expected-height="200"></div>
     <div class="sizedToGridArea" style="grid-column: c;" data-offset-x="0" data-offset-y="0" data-expected-width="50" data-expected-height="50"></div>
diff --git a/third_party/WebKit/LayoutTests/fast/css-grid-layout/resources/grid.css b/third_party/WebKit/LayoutTests/fast/css-grid-layout/resources/grid.css
index e28c00e..ed2266e 100644
--- a/third_party/WebKit/LayoutTests/fast/css-grid-layout/resources/grid.css
+++ b/third_party/WebKit/LayoutTests/fast/css-grid-layout/resources/grid.css
@@ -122,19 +122,53 @@
     grid-row: auto;
 }
 
+.autoRowAutoColumnSpanning2 {
+    background-color: maroon;
+    grid-column: span 2;
+    grid-row: auto;
+}
+
+.autoRowSpanning2AutoColumn {
+    background-color: aqua;
+    grid-column: auto;
+    grid-row: span 2;
+}
+
+.autoRowSpanning2AutoColumnSpanning3 {
+    background-color: olive;
+    grid-column: span 3;
+    grid-row: span 2;
+}
+
+.autoRowSpanning3AutoColumnSpanning2 {
+    background-color: indigo;
+    grid-column: span 2;
+    grid-row: span 3;
+}
+
 /* Grid element flow. */
 .gridAutoFlowStack {
     grid-auto-flow: stack;
 }
 
+/* FIXME: Rename to gridAutoFlowColumnSparse to be more explicit about the algorithm mode by default. */
 .gridAutoFlowColumn {
     grid-auto-flow: column;
 }
 
+.gridAutoFlowColumnDense {
+    grid-auto-flow: column dense;
+}
+
+/* FIXME: Rename to gridAutoFlowRowSparse to be more explicit about the algorithm mode by default. */
 .gridAutoFlowRow {
     grid-auto-flow: row;
 }
 
+.gridAutoFlowRowDense {
+    grid-auto-flow: row dense;
+}
+
 /* This rule makes sure the container is smaller than any grid items to avoid distributing any extra logical space to them. */
 .constrainedContainer {
     width: 10px;
diff --git a/third_party/WebKit/Source/core/rendering/RenderGrid.cpp b/third_party/WebKit/Source/core/rendering/RenderGrid.cpp
index 00f5775..3b1df25 100644
--- a/third_party/WebKit/Source/core/rendering/RenderGrid.cpp
+++ b/third_party/WebKit/Source/core/rendering/RenderGrid.cpp
@@ -94,11 +94,11 @@ class RenderGrid::GridIterator {
 public:
     // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
     // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
-    GridIterator(const GridRepresentation& grid, GridTrackSizingDirection direction, size_t fixedTrackIndex)
+    GridIterator(const GridRepresentation& grid, GridTrackSizingDirection direction, size_t fixedTrackIndex, size_t varyingTrackIndex = 0)
         : m_grid(grid)
         , m_direction(direction)
-        , m_rowIndex((direction == ForColumns) ? 0 : fixedTrackIndex)
-        , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : 0)
+        , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
+        , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
         , m_childIndex(0)
     {
         ASSERT(m_rowIndex < m_grid.size());
@@ -898,27 +898,48 @@ void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& au
 
 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
 {
-    for (size_t i = 0; i < autoGridItems.size(); ++i)
-        placeAutoMajorAxisItemOnGrid(autoGridItems[i]);
+    std::pair<size_t, size_t> autoPlacementCursor = std::make_pair(0, 0);
+    bool isGridAutoFlowDense = style()->isGridAutoFlowAlgorithmDense();
+
+    for (size_t i = 0; i < autoGridItems.size(); ++i) {
+        placeAutoMajorAxisItemOnGrid(autoGridItems[i], autoPlacementCursor);
+
+        // If grid-auto-flow is dense, reset auto-placement cursor.
+        if (isGridAutoFlowDense) {
+            autoPlacementCursor.first = 0;
+            autoPlacementCursor.second = 0;
+        }
+    }
 }
 
-void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
+void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem, std::pair<size_t, size_t>& autoPlacementCursor)
 {
     OwnPtr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMinorAxisDirection());
     ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMajorAxisDirection()));
     GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(0));
+
+    const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
+    size_t majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
+    size_t minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
+
     OwnPtr<GridCoordinate> emptyGridArea;
     if (minorAxisPositions) {
-        GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions->resolvedInitialPosition.toInt());
-        emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->integerSpan(), majorAxisPositions.integerSpan());
+        // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
+        if (minorAxisPositions->resolvedInitialPosition.toInt() < minorAxisAutoPlacementCursor)
+            majorAxisAutoPlacementCursor++;
+
+        if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
+            GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions->resolvedInitialPosition.toInt(), majorAxisAutoPlacementCursor);
+            emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->integerSpan(), majorAxisPositions.integerSpan());
+        }
+
         if (!emptyGridArea)
             emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
     } else {
         GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
 
-        const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
-        for (size_t majorAxisIndex = 0; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
-            GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex);
+        for (size_t majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
+            GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
             emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan());
 
             if (emptyGridArea) {
@@ -932,6 +953,9 @@ void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
                 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
                 emptyGridArea = nullptr;
             }
+
+            // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
+            minorAxisAutoPlacementCursor = 0;
         }
 
         if (!emptyGridArea)
@@ -939,6 +963,9 @@ void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem)
     }
 
     insertItemIntoGrid(gridItem, *emptyGridArea);
+    // Move auto-placement cursor to the new position.
+    autoPlacementCursor.first = emptyGridArea->rows.resolvedInitialPosition.toInt();
+    autoPlacementCursor.second = emptyGridArea->columns.resolvedInitialPosition.toInt();
 }
 
 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
diff --git a/third_party/WebKit/Source/core/rendering/RenderGrid.h b/third_party/WebKit/Source/core/rendering/RenderGrid.h
index 5dbeded..c559e28 100644
--- a/third_party/WebKit/Source/core/rendering/RenderGrid.h
+++ b/third_party/WebKit/Source/core/rendering/RenderGrid.h
@@ -84,7 +84,7 @@ private:
     PassOwnPtr<GridCoordinate> createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox*, GridTrackSizingDirection, const GridSpan& specifiedPositions) const;
     void placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>&);
     void placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>&);
-    void placeAutoMajorAxisItemOnGrid(RenderBox*);
+    void placeAutoMajorAxisItemOnGrid(RenderBox*, std::pair<size_t, size_t>& autoPlacementCursor);
     GridTrackSizingDirection autoPlacementMajorAxisDirection() const;
     GridTrackSizingDirection autoPlacementMinorAxisDirection() const;
 
-- 
cgit v1.1