15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/*
25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2011 Apple Inc. All rights reserved.
35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *
45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without
55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions
65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met:
75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright
85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *    notice, this list of conditions and the following disclaimer.
95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright
105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *    notice, this list of conditions and the following disclaimer in the
115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *    documentation and/or other materials provided with the distribution.
125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *
135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */
255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h"
2753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include "core/rendering/RenderGrid.h"
285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
297242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#include "core/paint/GridPainter.h"
3053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include "core/rendering/RenderLayer.h"
3153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include "core/rendering/RenderView.h"
32c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)#include "core/rendering/TextAutosizer.h"
33591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "core/rendering/style/GridCoordinate.h"
3409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include "platform/LengthFunctions.h"
355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
36c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink {
375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3883750176c3ee2cea66c8a9751271026a5901be3aBen Murdochstatic const int infinity = -1;
39926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
40926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)class GridTrack {
415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public:
425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    GridTrack()
435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        : m_usedBreadth(0)
44926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        , m_maxBreadth(0)
45926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    {
46926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
47926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
48926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    void growUsedBreadth(LayoutUnit growth)
49926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    {
50926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        ASSERT(growth >= 0);
51926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        m_usedBreadth += growth;
52926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
53926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    LayoutUnit usedBreadth() const { return m_usedBreadth; }
54926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
55926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    void growMaxBreadth(LayoutUnit growth)
565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    {
57926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        if (m_maxBreadth == infinity)
58926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            m_maxBreadth = m_usedBreadth + growth;
59926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        else
60926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            m_maxBreadth += growth;
61926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
62926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    LayoutUnit maxBreadthIfNotInfinite() const
63926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    {
64926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return (m_maxBreadth == infinity) ? m_usedBreadth : m_maxBreadth;
655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    LayoutUnit m_usedBreadth;
68926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    LayoutUnit m_maxBreadth;
695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)};
705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
71e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)struct GridTrackForNormalization {
72e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    GridTrackForNormalization(const GridTrack& track, double flex)
73e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        : m_track(&track)
74e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        , m_flex(flex)
75e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        , m_normalizedFlexValue(track.m_usedBreadth / flex)
76e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    {
77e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    }
78e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
79e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    // Required by std::sort.
8009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    GridTrackForNormalization& operator=(const GridTrackForNormalization& o)
81e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    {
82e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        m_track = o.m_track;
83e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        m_flex = o.m_flex;
84e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        m_normalizedFlexValue = o.m_normalizedFlexValue;
85e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        return *this;
86e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    }
87e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
88e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    const GridTrack* m_track;
89e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    double m_flex;
90e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    LayoutUnit m_normalizedFlexValue;
91e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)};
92e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
93926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)class RenderGrid::GridIterator {
94926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    WTF_MAKE_NONCOPYABLE(GridIterator);
95926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)public:
96926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g
97926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column.
98197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    GridIterator(const GridRepresentation& grid, GridTrackSizingDirection direction, size_t fixedTrackIndex, size_t varyingTrackIndex = 0)
99926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        : m_grid(grid)
100926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        , m_direction(direction)
101197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
102197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
103926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        , m_childIndex(0)
104926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    {
105926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        ASSERT(m_rowIndex < m_grid.size());
106926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        ASSERT(m_columnIndex < m_grid[0].size());
107926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
108926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
109926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    RenderBox* nextGridItem()
110926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    {
111e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        ASSERT(!m_grid.isEmpty());
112926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
113926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
114926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
115926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
116e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)            const GridCell& children = m_grid[m_rowIndex][m_columnIndex];
117926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            if (m_childIndex < children.size())
118926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)                return children[m_childIndex++];
119926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
120926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            m_childIndex = 0;
121926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        }
122926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return 0;
123926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
124926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
1255d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    bool checkEmptyCells(size_t rowSpan, size_t columnSpan) const
1265d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    {
1275d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        // Ignore cells outside current grid as we will grow it later if needed.
1285d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        size_t maxRows = std::min(m_rowIndex + rowSpan, m_grid.size());
1295d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        size_t maxColumns = std::min(m_columnIndex + columnSpan, m_grid[0].size());
1305d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
1315d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
1325d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        for (size_t row = m_rowIndex; row < maxRows; ++row) {
1335d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            for (size_t column = m_columnIndex; column < maxColumns; ++column) {
1345d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)                const GridCell& children = m_grid[row][column];
1355d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)                if (!children.isEmpty())
1365d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)                    return false;
1375d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            }
1385d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        }
1395d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
1405d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        return true;
1415d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    }
1425d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
1435d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    PassOwnPtr<GridCoordinate> nextEmptyGridArea(size_t fixedTrackSpan, size_t varyingTrackSpan)
144926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    {
145e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        ASSERT(!m_grid.isEmpty());
1465d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        ASSERT(fixedTrackSpan >= 1 && varyingTrackSpan >= 1);
1475d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
1485d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        size_t rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
1495d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        size_t columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
150926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
151926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
152926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
153926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
1545d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            if (checkEmptyCells(rowSpan, columnSpan)) {
1555d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)                OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(GridSpan(m_rowIndex, m_rowIndex + rowSpan - 1), GridSpan(m_columnIndex, m_columnIndex + columnSpan - 1)));
156926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)                // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
157926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)                ++varyingTrackIndex;
158926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)                return result.release();
159926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            }
160926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        }
161926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return nullptr;
162926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
163926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
164926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)private:
165e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)    const GridRepresentation& m_grid;
16619cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)    GridTrackSizingDirection m_direction;
167926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    size_t m_rowIndex;
168926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    size_t m_columnIndex;
169926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    size_t m_childIndex;
170926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)};
171926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
17206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)struct RenderGrid::GridSizingData {
17306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    WTF_MAKE_NONCOPYABLE(GridSizingData);
17406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)public:
17506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    GridSizingData(size_t gridColumnCount, size_t gridRowCount)
17606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        : columnTracks(gridColumnCount)
17706f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        , rowTracks(gridRowCount)
17806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    {
17906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    }
18006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)
18106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    Vector<GridTrack> columnTracks;
18206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    Vector<GridTrack> rowTracks;
18306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    Vector<size_t> contentSizedTracksIndex;
18406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)
18506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
18606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    Vector<LayoutUnit> distributeTrackVector;
18706f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    Vector<GridTrack*> filteredTracks;
18806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)};
18906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)
190926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)RenderGrid::RenderGrid(Element* element)
191926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    : RenderBlock(element)
192f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    , m_gridIsDirty(true)
193e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    , m_orderIterator(this)
1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){
195197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ASSERT(!childrenInline());
1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}
1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)RenderGrid::~RenderGrid()
1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){
2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}
2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
202f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)void RenderGrid::addChild(RenderObject* newChild, RenderObject* beforeChild)
203f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles){
204197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // If the new requested beforeChild is not one of our children is because it's wrapped by an anonymous container. If
205197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // we do not special case this situation we could end up calling addChild() twice for the newChild, one with the
206197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // initial beforeChild and another one with its parent.
207197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (beforeChild && beforeChild->parent() != this) {
208197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT(beforeChild->parent()->isAnonymous());
209197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        beforeChild = splitAnonymousBoxesAroundChild(beforeChild);
2107242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        dirtyGrid();
211197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
212197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
213f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    RenderBlock::addChild(newChild, beforeChild);
214f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
215f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    if (gridIsDirty())
216f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        return;
217f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
218e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)    if (!newChild->isBox()) {
219e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        dirtyGrid();
220e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        return;
221e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)    }
222e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)
2237242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // If the new child has been inserted inside an existent anonymous block, we can simply ignore it as the anonymous
2247242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // block is an already known grid item.
2257242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (newChild->parent() != this)
2267242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return;
2277242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
228197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // FIXME: Implement properly "stack" value in auto-placement algorithm.
229197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (!style()->isGridAutoFlowAlgorithmStack()) {
23007a852d8c1953036774d8f3b65d18dcfea3bb4a2Ben Murdoch        // The grid needs to be recomputed as it might contain auto-placed items that will change their position.
23107a852d8c1953036774d8f3b65d18dcfea3bb4a2Ben Murdoch        dirtyGrid();
23207a852d8c1953036774d8f3b65d18dcfea3bb4a2Ben Murdoch        return;
23307a852d8c1953036774d8f3b65d18dcfea3bb4a2Ben Murdoch    }
23407a852d8c1953036774d8f3b65d18dcfea3bb4a2Ben Murdoch
235f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    RenderBox* newChildBox = toRenderBox(newChild);
236a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForRows);
237a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForColumns);
238f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    if (!rowPositions || !columnPositions) {
239f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        // The new child requires the auto-placement algorithm to run so we need to recompute the grid fully.
240f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        dirtyGrid();
24107a852d8c1953036774d8f3b65d18dcfea3bb4a2Ben Murdoch        return;
242f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    } else {
2437242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        insertItemIntoGrid(*newChildBox, GridCoordinate(*rowPositions, *columnPositions));
2447242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        addChildToIndexesMap(*newChildBox);
245f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    }
246f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)}
247f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
2487242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccivoid RenderGrid::addChildToIndexesMap(RenderBox& child)
249d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles){
2507242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(!m_gridItemsIndexesMap.contains(&child));
2517242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    RenderBox* sibling = child.nextSiblingBox();
252d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    bool lastSibling = !sibling;
253d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)
254d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    if (lastSibling)
2557242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        sibling = child.previousSiblingBox();
256d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)
257d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    size_t index = 0;
258d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    if (sibling)
259d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)        index = lastSibling ? m_gridItemsIndexesMap.get(sibling) + 1 : m_gridItemsIndexesMap.get(sibling);
260d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)
261d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    if (sibling && !lastSibling) {
262d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)        for (; sibling; sibling = sibling->nextSiblingBox())
263d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)            m_gridItemsIndexesMap.set(sibling, m_gridItemsIndexesMap.get(sibling) + 1);
264d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    }
265d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)
2667242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    m_gridItemsIndexesMap.set(&child, index);
267d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)}
268d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)
269f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)void RenderGrid::removeChild(RenderObject* child)
270f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles){
271f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    RenderBlock::removeChild(child);
272f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
273f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    if (gridIsDirty())
274f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        return;
275f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
276f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    ASSERT(child->isBox());
277aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch
278197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // FIXME: Implement properly "stack" value in auto-placement algorithm.
279197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (!style()->isGridAutoFlowAlgorithmStack()) {
280aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch        // The grid needs to be recomputed as it might contain auto-placed items that will change their position.
281aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch        dirtyGrid();
282aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch        return;
283aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch    }
284aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch
285aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch    const RenderBox* childBox = toRenderBox(child);
286aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch    GridCoordinate coordinate = m_gridItemCoordinate.take(childBox);
287aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch
288f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) {
289f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column) {
290a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch            GridCell& cell = m_grid[row.toInt()][column.toInt()];
291aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch            cell.remove(cell.find(childBox));
292aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch        }
293aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch    }
294d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)
295d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    m_gridItemsIndexesMap.remove(childBox);
296f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)}
297f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
298f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)void RenderGrid::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
299f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles){
300f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    RenderBlock::styleDidChange(diff, oldStyle);
301f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    if (!oldStyle)
302f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        return;
303f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
304f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    // FIXME: The following checks could be narrowed down if we kept track of which type of grid items we have:
305f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    // - explicit grid size changes impact negative explicitely positioned and auto-placed grid items.
306f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    // - named grid lines only impact grid items with named grid lines.
307f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    // - auto-flow changes only impacts auto-placed children.
308f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
309f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    if (explicitGridDidResize(oldStyle)
310f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        || namedGridLinesDefinitionDidChange(oldStyle)
311f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        || oldStyle->gridAutoFlow() != style()->gridAutoFlow())
312f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        dirtyGrid();
313f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)}
314f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
315f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)bool RenderGrid::explicitGridDidResize(const RenderStyle* oldStyle) const
316f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles){
31709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return oldStyle->gridTemplateColumns().size() != style()->gridTemplateColumns().size()
31809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        || oldStyle->gridTemplateRows().size() != style()->gridTemplateRows().size();
319f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)}
320f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
321f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)bool RenderGrid::namedGridLinesDefinitionDidChange(const RenderStyle* oldStyle) const
322f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles){
323f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    return oldStyle->namedGridRowLines() != style()->namedGridRowLines()
324f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        || oldStyle->namedGridColumnLines() != style()->namedGridColumnLines();
325f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)}
326f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
32709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void RenderGrid::layoutBlock(bool relayoutChildren)
3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){
3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    ASSERT(needsLayout());
3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    if (!relayoutChildren && simplifiedLayout())
3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return;
3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock.
3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    // It would be nice to refactor some of the duplicate code.
3365d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    LayoutState state(*this, locationOffset());
3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    LayoutSize previousSize = size();
3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    setLogicalHeight(0);
3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    updateLogicalWidth();
3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
343c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    TextAutosizer::LayoutScope textAutosizerLayoutScope(this);
3445d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    layoutGridItems();
3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    LayoutUnit oldClientAfterEdge = clientLogicalBottom();
3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    updateLogicalHeight();
3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    if (size() != previousSize)
3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        relayoutChildren = true;
3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch    layoutPositionedObjects(relayoutChildren || isDocumentElement());
3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    computeOverflow(oldClientAfterEdge);
3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
35776c265b59aa821ccbf8c75ab2bb0d036e97d2956Torne (Richard Coles)    updateLayerTransformAfterLayout();
3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    // we overflow or not.
3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    if (hasOverflowClip())
362f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)        layer()->scrollableArea()->updateAfterLayout();
3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3643c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch    clearNeedsLayout();
3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}
3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
367926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
368926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
369926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    const_cast<RenderGrid*>(this)->placeItemsOnGrid();
370926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
3711e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    GridSizingData sizingData(gridColumnCount(), gridRowCount());
3721e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    LayoutUnit availableLogicalSpace = 0;
37309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace);
3741e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)
3751e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    for (size_t i = 0; i < sizingData.columnTracks.size(); ++i) {
3761e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        LayoutUnit minTrackBreadth = sizingData.columnTracks[i].m_usedBreadth;
3771e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        LayoutUnit maxTrackBreadth = sizingData.columnTracks[i].m_maxBreadth;
378926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth);
379926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
380926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        minLogicalWidth += minTrackBreadth;
381926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        maxLogicalWidth += maxTrackBreadth;
382926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
383926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
384926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
385926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
386926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void RenderGrid::computePreferredLogicalWidths()
3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){
3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    ASSERT(preferredLogicalWidthsDirty());
3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    m_minPreferredLogicalWidth = 0;
3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    m_maxPreferredLogicalWidth = 0;
3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
394926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // FIXME: We don't take our own logical width into account. Once we do, we need to make sure
395926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // we apply (and test the interaction with) min-width / max-width.
3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
397926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
399926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth();
400926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection;
401926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection;
402926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
403c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)    clearPreferredLogicalWidthsDirty();
404926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
405926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
40609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData)
407926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
4081e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)    LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
40909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace);
41009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
41109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
412d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)bool RenderGrid::gridElementIsShrinkToFit()
41309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
414d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    return isFloatingOrOutOfFlowPositioned();
415926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
416926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
41709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
418926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
41906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
42009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Vector<size_t> flexibleSizedTracksIndex;
42106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    sizingData.contentSizedTracksIndex.shrink(0);
42209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
42309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // 1. Initialize per Grid track variables.
424926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    for (size_t i = 0; i < tracks.size(); ++i) {
425926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        GridTrack& track = tracks[i];
4267242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        GridTrackSize trackSize = gridTrackSize(direction, i);
42753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)        const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
42853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)        const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth();
429926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
430926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth);
431e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.m_usedBreadth);
432926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
433c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        if (track.m_maxBreadth != infinity)
434c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)            track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth);
435e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)
436e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        if (trackSize.isContentSized())
43706f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)            sizingData.contentSizedTracksIndex.append(i);
43809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (trackSize.maxTrackBreadth().isFlex())
43909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            flexibleSizedTracksIndex.append(i);
440926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
441926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
44209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // 2. Resolve content-based TrackSizingFunctions.
44306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    if (!sizingData.contentSizedTracksIndex.isEmpty())
44406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        resolveContentBasedTrackSizingFunctions(direction, sizingData, availableLogicalSpace);
445e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)
446e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)    for (size_t i = 0; i < tracks.size(); ++i) {
447e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        ASSERT(tracks[i].m_maxBreadth != infinity);
448e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        availableLogicalSpace -= tracks[i].m_usedBreadth;
449e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)    }
450926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
451d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style()->logicalHeight().isAuto() : gridElementIsShrinkToFit();
45209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
45309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0)
454926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return;
455926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
45609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until
45709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // availableLogicalSpace (RemainingSpace in the specs) is exhausted.
458926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    const size_t tracksSize = tracks.size();
45909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (!hasUndefinedRemainingSpace) {
46009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        Vector<GridTrack*> tracksForDistribution(tracksSize);
46109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        for (size_t i = 0; i < tracksSize; ++i)
46209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            tracksForDistribution[i] = tracks.data() + i;
463926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
46409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, sizingData, availableLogicalSpace);
46509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    } else {
46609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        for (size_t i = 0; i < tracksSize; ++i)
46709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            tracks[i].m_usedBreadth = tracks[i].m_maxBreadth;
46809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
46909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
47009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (flexibleSizedTracksIndex.isEmpty())
47109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return;
472e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
473e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
47409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    double normalizedFractionBreadth = 0;
47509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (!hasUndefinedRemainingSpace) {
47609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, availableLogicalSpace);
47709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    } else {
47809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
47909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            const size_t trackIndex = flexibleSizedTracksIndex[i];
4807242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
48109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].m_usedBreadth / trackSize.maxTrackBreadth().flex());
48209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
483e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
48409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
48509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]);
48609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            while (RenderBox* gridItem = iterator.nextGridItem()) {
4877242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                const GridCoordinate coordinate = cachedGridCoordinate(*gridItem);
48809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)                const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
48909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
49009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)                // Do not include already processed items.
491a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch                if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1])
49209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)                    continue;
49309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
4947242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(*gridItem, direction, sizingData.columnTracks));
49509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)                normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth);
49609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            }
49709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
49809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
499e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
50009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
50109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        const size_t trackIndex = flexibleSizedTracksIndex[i];
5027242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        GridTrackSize trackSize = gridTrackSize(direction, trackIndex);
50309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
50409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        tracks[trackIndex].m_usedBreadth = std::max<LayoutUnit>(tracks[trackIndex].m_usedBreadth, normalizedFractionBreadth * trackSize.maxTrackBreadth().flex());
505e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    }
506926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
507926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
50819cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const
509926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
51053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    if (gridLength.isFlex())
51153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)        return 0;
51253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)
51353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    const Length& trackLength = gridLength.length();
51453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    ASSERT(!trackLength.isAuto());
51551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)    if (trackLength.isSpecified())
516926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return computeUsedBreadthOfSpecifiedLength(direction, trackLength);
517926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
51853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
519926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    return 0;
520926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
521926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
52219cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const
523926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
524e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    if (gridLength.isFlex())
525e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        return usedBreadth;
52653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)
52753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    const Length& trackLength = gridLength.length();
52853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    ASSERT(!trackLength.isAuto());
52951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)    if (trackLength.isSpecified()) {
530926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength);
53183750176c3ee2cea66c8a9751271026a5901be3aBen Murdoch        ASSERT(computedBreadth != infinity);
532926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return computedBreadth;
533926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
534926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
53553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    ASSERT(trackLength.isMinContent() || trackLength.isMaxContent());
536926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    return infinity;
537926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
538926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
53919cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const
540926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
54151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)    ASSERT(trackLength.isSpecified());
54253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    // FIXME: The -1 here should be replaced by whatever the intrinsic height of the grid is.
54309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style()->logicalHeight(), -1));
544926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
545926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
546e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)static bool sortByGridNormalizedFlexValue(const GridTrackForNormalization& track1, const GridTrackForNormalization& track2)
547e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles){
548e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue;
549e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)}
550e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
55109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit availableLogicalSpace) const
552e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles){
553e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    // |availableLogicalSpace| already accounts for the used breadths so no need to remove it here.
554e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
555e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    Vector<GridTrackForNormalization> tracksForNormalization;
556f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    for (GridSpan::iterator resolvedPosition = tracksSpan.begin(); resolvedPosition != tracksSpan.end(); ++resolvedPosition) {
5577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        GridTrackSize trackSize = gridTrackSize(direction, resolvedPosition.toInt());
558e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        if (!trackSize.maxTrackBreadth().isFlex())
559e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)            continue;
560e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
561a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        tracksForNormalization.append(GridTrackForNormalization(tracks[resolvedPosition.toInt()], trackSize.maxTrackBreadth().flex()));
562e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    }
563e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
56409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // The function is not called if we don't have <flex> grid tracks
56509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(!tracksForNormalization.isEmpty());
566e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
567e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    std::sort(tracksForNormalization.begin(), tracksForNormalization.end(), sortByGridNormalizedFlexValue);
568e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
569e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio
570e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't
571e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    // fit into availableLogicalSpaceIgnoringFractionTracks.
572e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    double accumulatedFractions = 0;
573e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    LayoutUnit fractionValueBasedOnGridItemsRatio = 0;
574e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    LayoutUnit availableLogicalSpaceIgnoringFractionTracks = availableLogicalSpace;
575e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
576e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    for (size_t i = 0; i < tracksForNormalization.size(); ++i) {
577e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        const GridTrackForNormalization& track = tracksForNormalization[i];
578e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) {
579e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)            // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value)
580e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)            // will make us overflow our container, then stop. We have the previous step's ratio is the best fit.
581e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)            if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks)
582e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)                break;
583e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
584e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)            fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue;
585e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        }
586e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
587e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        accumulatedFractions += track.m_flex;
588e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space.
589e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        availableLogicalSpaceIgnoringFractionTracks += track.m_track->m_usedBreadth;
590e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    }
591e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
592e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions;
593e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)}
594e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)
5957242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciGridTrackSize RenderGrid::gridTrackSize(GridTrackSizingDirection direction, size_t i) const
596926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
5977242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    bool isForColumns = direction == ForColumns;
5987242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    const Vector<GridTrackSize>& trackStyles = isForColumns ? style()->gridTemplateColumns() : style()->gridTemplateRows();
5997242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    const GridTrackSize& trackSize = (i >= trackStyles.size()) ? (isForColumns ? style()->gridAutoColumns() : style()->gridAutoRows()) : trackStyles[i];
6007242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
6017242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // If the logical width/height of the grid container is indefinite, percentage values are treated as <auto> (or in
6027242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // the case of minmax() as min-content for the first position and max-content for the second).
6037242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    Length logicalSize = isForColumns ? style()->logicalWidth() : style()->logicalHeight();
6047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // FIXME: isIntrinsicOrAuto() does not fulfil the 'indefinite size' description as it does not include <percentage>
6057242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // of indefinite sizes. This is a broather issue as Length does not have the required context to support it.
6067242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (logicalSize.isIntrinsicOrAuto()) {
6077242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        const GridLength& oldMinTrackBreadth = trackSize.minTrackBreadth();
6087242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        const GridLength& oldMaxTrackBreadth = trackSize.maxTrackBreadth();
6097242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return GridTrackSize(oldMinTrackBreadth.isPercentage() ? Length(MinContent) : oldMinTrackBreadth, oldMaxTrackBreadth.isPercentage() ? Length(MaxContent) : oldMaxTrackBreadth);
61009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
61109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
61209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return trackSize;
613926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
614926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
6157242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::logicalHeightForChild(RenderBox& child, Vector<GridTrack>& columnTracks)
616926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
6177242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    SubtreeLayoutScope layoutScope(child);
6187242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child.hasOverrideContainingBlockLogicalWidth() ? child.overrideContainingBlockContentLogicalWidth() : LayoutUnit();
61909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
6207242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (child.style()->logicalHeight().isPercent() || oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth)
6217242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        layoutScope.setNeedsLayout(&child);
622926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
6237242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    child.setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
624926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is
625926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution).
6267242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    child.setOverrideContainingBlockContentLogicalHeight(-1);
6277242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    child.layoutIfNeeded();
6287242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return child.logicalHeight() + child.marginLogicalHeight();
629926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
630926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
6317242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::minContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
632926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
6337242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
634926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // FIXME: Properly support orthogonal writing mode.
635926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    if (hasOrthogonalWritingMode)
636926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return 0;
637926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
638926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    if (direction == ForColumns) {
639926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
640926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
6417242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return child.minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(&child);
642926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
643926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
64410f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch    return logicalHeightForChild(child, columnTracks);
645926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
646926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
6477242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::maxContentForChild(RenderBox& child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks)
648926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
6497242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
650926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // FIXME: Properly support orthogonal writing mode.
651926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    if (hasOrthogonalWritingMode)
652926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return LayoutUnit();
653926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
654926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    if (direction == ForColumns) {
655926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
656926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
6577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(&child);
658926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
659926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
66010f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch    return logicalHeightForChild(child, columnTracks);
661926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
662926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
6637242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccisize_t RenderGrid::gridItemSpan(const RenderBox& child, GridTrackSizingDirection direction)
664c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles){
665c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    GridCoordinate childCoordinate = cachedGridCoordinate(child);
666c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    GridSpan childSpan = (direction == ForRows) ? childCoordinate.rows : childCoordinate.columns;
667c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
668c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    return childSpan.resolvedFinalPosition.toInt() - childSpan.resolvedInitialPosition.toInt() + 1;
669c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)}
670c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
671c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)typedef std::pair<RenderBox*, size_t> GridItemWithSpan;
672c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
673c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)// This function sorts by span (.second in the pair) but also places pointers (.first in the pair) to the same object in
674c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)// consecutive positions so duplicates could be easily removed with std::unique() for example.
675c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)static bool gridItemWithSpanSorter(const GridItemWithSpan& item1, const GridItemWithSpan& item2)
676c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles){
677c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    if (item1.second != item2.second)
678c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        return item1.second < item2.second;
679c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
680c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    return item1.first < item2.first;
681c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)}
682c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
683c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)static bool uniquePointerInPair(const GridItemWithSpan& item1, const GridItemWithSpan& item2)
684c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles){
685c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    return item1.first == item2.first;
686c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)}
687c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
68819cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
689926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
690e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)    // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track (crbug.com/235258).
691926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
69206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
693c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        size_t trackIndex = sizingData.contentSizedTracksIndex[i];
694c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        GridIterator iterator(m_grid, direction, trackIndex);
695c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
696c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
697c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        while (RenderBox* gridItem = iterator.nextGridItem())
6987242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            itemsSortedByIncreasingSpan.append(std::make_pair(gridItem, gridItemSpan(*gridItem, direction)));
699c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        std::stable_sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), gridItemWithSpanSorter);
700c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        Vector<GridItemWithSpan>::iterator end = std::unique(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end(), uniquePointerInPair);
701c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
702c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        for (Vector<GridItemWithSpan>::iterator it = itemsSortedByIncreasingSpan.begin(); it != end; ++it) {
703c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)            RenderBox* gridItem = it->first;
7047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
7057242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
7067242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
7077242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, *gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
708e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        }
709e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)
710c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
711926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        if (track.m_maxBreadth == infinity)
712926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            track.m_maxBreadth = track.m_usedBreadth;
713926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
714926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
715926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
7167242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccivoid RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, RenderBox& gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
717926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
718926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
719a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition;
720a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition;
721926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
72206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    sizingData.filteredTracks.shrink(0);
723a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    for (GridResolvedPosition trackPosition = initialTrackPosition; trackPosition <= finalTrackPosition; ++trackPosition) {
7247242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        GridTrackSize trackSize = gridTrackSize(direction, trackPosition.toInt());
725926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        if (!(trackSize.*filterFunction)())
7265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)            continue;
727926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
728a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPosition.toInt()] : sizingData.rowTracks[trackPosition.toInt()];
72906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        sizingData.filteredTracks.append(&track);
730926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
731926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
73206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    if (sizingData.filteredTracks.isEmpty())
733e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)        return;
734e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)
73506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks);
736a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    for (GridResolvedPosition trackIndexForSpace = initialTrackPosition; trackIndexForSpace <= finalTrackPosition; ++trackIndexForSpace) {
737a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndexForSpace.toInt()] : sizingData.rowTracks[trackIndexForSpace.toInt()];
738926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        additionalBreadthSpace -= (track.*trackGetter)();
739926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
740926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
741926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
742c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
743c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    // Specs mandate to floor additionalBreadthSpace (extra-space in specs) to 0. Instead we directly avoid the function
744c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    // call in those cases as it will be a noop in terms of track sizing.
745c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    if (additionalBreadthSpace > 0)
746c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.filteredTracks, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
747926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
748926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
749926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
750926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
7517242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
7527242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // (forall x: NOT x < x).
7537242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (track1->m_maxBreadth == infinity && track2->m_maxBreadth == infinity)
7547242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return false;
755c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
7567242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (track1->m_maxBreadth == infinity || track2->m_maxBreadth == infinity)
7577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return track2->m_maxBreadth == infinity;
758c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)
759926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth);
760926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
761926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
76206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
763926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
764c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    ASSERT(availableLogicalSpace > 0);
765926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
766926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
767926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    size_t tracksSize = tracks.size();
76806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    sizingData.distributeTrackVector.resize(tracksSize);
769926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
770926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    for (size_t i = 0; i < tracksSize; ++i) {
771926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        GridTrack& track = *tracks[i];
772926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i);
773926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        LayoutUnit trackBreadth = (tracks[i]->*trackGetter)();
774c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        LayoutUnit growthShare = track.m_maxBreadth == infinity ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth);
775c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        ASSERT(growthShare != infinity);
77651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)        sizingData.distributeTrackVector[i] = trackBreadth;
777e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)        // We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function.
77851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)        if (growthShare > 0) {
77951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)            sizingData.distributeTrackVector[i] += growthShare;
78051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)            availableLogicalSpace -= growthShare;
78151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)        }
782926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
783926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
784926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) {
785926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        tracksSize = tracksForGrowthAboveMaxBreadth->size();
786926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        for (size_t i = 0; i < tracksSize; ++i) {
787926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
78806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)            sizingData.distributeTrackVector[i] += growthShare;
789926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            availableLogicalSpace -= growthShare;
7905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
791926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
7925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
793926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    for (size_t i = 0; i < tracksSize; ++i) {
79406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
795926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        if (growth >= 0)
796926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            (tracks[i]->*trackGrowthFunction)(growth);
7975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
798926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
7995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
800197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
80119cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks)
802926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
803926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    for (size_t i = 0; i < tracks.size(); ++i) {
8047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        GridTrackSize trackSize = gridTrackSize(direction, i);
80553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)        const GridLength& minTrackBreadth = trackSize.minTrackBreadth();
806926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth)
807926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            return false;
808926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
809926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    return true;
810926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
811926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)#endif
8125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
8135d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)void RenderGrid::ensureGridSize(size_t maximumRowIndex, size_t maximumColumnIndex)
814926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
8155d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    const size_t oldRowSize = gridRowCount();
8165d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    if (maximumRowIndex >= oldRowSize) {
8175d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        m_grid.grow(maximumRowIndex + 1);
818f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        for (size_t row = oldRowSize; row < gridRowCount(); ++row)
819f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            m_grid[row].grow(gridColumnCount());
820926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
8215d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
8225d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    if (maximumColumnIndex >= gridColumnCount()) {
8235d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        for (size_t row = 0; row < gridRowCount(); ++row)
8245d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            m_grid[row].grow(maximumColumnIndex + 1);
8255d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    }
826926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
8275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
8287242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccivoid RenderGrid::insertItemIntoGrid(RenderBox& child, const GridCoordinate& coordinate)
829926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
8305d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    ensureGridSize(coordinate.rows.resolvedFinalPosition.toInt(), coordinate.columns.resolvedFinalPosition.toInt());
831f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)
832f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) {
833f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column)
8347242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            m_grid[row.toInt()][column.toInt()].append(&child);
835e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)    }
836e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)
8377242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    RELEASE_ASSERT(!m_gridItemCoordinate.contains(&child));
8387242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    m_gridItemCoordinate.set(&child, coordinate);
8395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}
8405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
841926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)void RenderGrid::placeItemsOnGrid()
842926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
843f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    if (!gridIsDirty())
844f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)        return;
845f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
846926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    ASSERT(m_gridItemCoordinate.isEmpty());
847926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
848e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    populateExplicitGridAndOrderIterator();
849926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
850f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    // We clear the dirty bit here as the grid sizes have been updated, this means
851f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    // that we can safely call gridRowCount() / gridColumnCount().
852f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    m_gridIsDirty = false;
853f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
854926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    Vector<RenderBox*> autoMajorAxisAutoGridItems;
855926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    Vector<RenderBox*> specifiedMajorAxisAutoGridItems;
856e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) {
857926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // FIXME: We never re-resolve positions if the grid is grown during auto-placement which may lead auto / <integer>
858926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // positions to not match the author's intent. The specification is unclear on what should be done in this case.
859a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows);
860a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns);
861926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        if (!rowPositions || !columnPositions) {
862926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get();
863926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            if (!majorAxisPositions)
864926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)                autoMajorAxisAutoGridItems.append(child);
865926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            else
866926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)                specifiedMajorAxisAutoGridItems.append(child);
867926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            continue;
868926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        }
8697242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        insertItemIntoGrid(*child, GridCoordinate(*rowPositions, *columnPositions));
870926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
871926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
87209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gridRowCount() >= style()->gridTemplateRows().size());
87309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gridColumnCount() >= style()->gridTemplateColumns().size());
874926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
875197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // FIXME: Implement properly "stack" value in auto-placement algorithm.
876197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (style()->isGridAutoFlowAlgorithmStack()) {
877926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // If we did collect some grid items, they won't be placed thus never laid out.
878926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        ASSERT(!autoMajorAxisAutoGridItems.size());
879926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        ASSERT(!specifiedMajorAxisAutoGridItems.size());
880926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        return;
881926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
882926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
883926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems);
884926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems);
885f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)
886f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    m_grid.shrinkToFit();
887926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
888926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
889e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdochvoid RenderGrid::populateExplicitGridAndOrderIterator()
890e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch{
891e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    OrderIteratorPopulator populator(m_orderIterator);
892e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch
893a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    size_t maximumRowIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridRowCount(*style()));
894a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    size_t maximumColumnIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridColumnCount(*style()));
895e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch
896d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    ASSERT(m_gridItemsIndexesMap.isEmpty());
897d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    size_t childIndex = 0;
898e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
899e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch        populator.collectChild(child);
900d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)        m_gridItemsIndexesMap.set(child, childIndex++);
901e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch
902e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch        // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
903a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows);
904a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns);
905e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch
906f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        // |positions| is 0 if we need to run the auto-placement algorithm.
907f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        if (rowPositions) {
908f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            maximumRowIndex = std::max<size_t>(maximumRowIndex, rowPositions->resolvedFinalPosition.next().toInt());
909f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        } else {
910f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            // Grow the grid for items with a definite row span, getting the largest such span.
911f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForRows, GridResolvedPosition(0));
912f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            maximumRowIndex = std::max<size_t>(maximumRowIndex, positions.resolvedFinalPosition.next().toInt());
913f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        }
914f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)
915f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        if (columnPositions) {
916f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            maximumColumnIndex = std::max<size_t>(maximumColumnIndex, columnPositions->resolvedFinalPosition.next().toInt());
917f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        } else {
918f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            // Grow the grid for items with a definite column span, getting the largest such span.
919f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForColumns, GridResolvedPosition(0));
920f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            maximumColumnIndex = std::max<size_t>(maximumColumnIndex, positions.resolvedFinalPosition.next().toInt());
921f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        }
922e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    }
923e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch
924e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    m_grid.grow(maximumRowIndex);
925e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch    for (size_t i = 0; i < m_grid.size(); ++i)
926e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch        m_grid[i].grow(maximumColumnIndex);
927e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch}
928e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch
9297242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciPassOwnPtr<GridCoordinate> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox& gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const
930f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles){
931f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns;
932f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    const size_t endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount();
9337242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    GridSpan crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection));
934f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    return adoptPtr(new GridCoordinate(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions));
935f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)}
936f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)
93706f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
938926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
939926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    for (size_t i = 0; i < autoGridItems.size(); ++i) {
940a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *autoGridItems[i], autoPlacementMajorAxisDirection());
9415d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *autoGridItems[i], autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
9425d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
9435d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt());
9445d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->integerSpan(), minorAxisPositions.integerSpan());
945f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        if (!emptyGridArea)
9467242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(*autoGridItems[i], autoPlacementMajorAxisDirection(), *majorAxisPositions);
9477242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        insertItemIntoGrid(*autoGridItems[i], *emptyGridArea);
948926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    }
949926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
9505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
95106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
952926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
953197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    std::pair<size_t, size_t> autoPlacementCursor = std::make_pair(0, 0);
954197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    bool isGridAutoFlowDense = style()->isGridAutoFlowAlgorithmDense();
955197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
956197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (size_t i = 0; i < autoGridItems.size(); ++i) {
9577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        placeAutoMajorAxisItemOnGrid(*autoGridItems[i], autoPlacementCursor);
958197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
959197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // If grid-auto-flow is dense, reset auto-placement cursor.
960197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (isGridAutoFlowDense) {
961197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            autoPlacementCursor.first = 0;
962197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            autoPlacementCursor.second = 0;
963197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
964197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
965926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
966926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
9677242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccivoid RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox& gridItem, std::pair<size_t, size_t>& autoPlacementCursor)
968926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
9697242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    OwnPtr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), gridItem, autoPlacementMinorAxisDirection());
9707242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(*style(), gridItem, autoPlacementMajorAxisDirection()));
9717242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(0));
972197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
973197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount();
974197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    size_t majorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.second : autoPlacementCursor.first;
975197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    size_t minorAxisAutoPlacementCursor = autoPlacementMajorAxisDirection() == ForColumns ? autoPlacementCursor.first : autoPlacementCursor.second;
976197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
977f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    OwnPtr<GridCoordinate> emptyGridArea;
978926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    if (minorAxisPositions) {
979197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Move to the next track in major axis if initial position in minor axis is before auto-placement cursor.
980197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (minorAxisPositions->resolvedInitialPosition.toInt() < minorAxisAutoPlacementCursor)
981197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            majorAxisAutoPlacementCursor++;
982197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
983197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (majorAxisAutoPlacementCursor < endOfMajorAxis) {
984197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions->resolvedInitialPosition.toInt(), majorAxisAutoPlacementCursor);
985197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->integerSpan(), majorAxisPositions.integerSpan());
986197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
987197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
988f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        if (!emptyGridArea)
989f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions);
990926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    } else {
9917242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0));
9925d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
993197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        for (size_t majorAxisIndex = majorAxisAutoPlacementCursor; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) {
994197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex, minorAxisAutoPlacementCursor);
9955d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan());
996f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)
997f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            if (emptyGridArea) {
998f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)                // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()).
999f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)                GridResolvedPosition minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.resolvedFinalPosition : emptyGridArea->rows.resolvedFinalPosition;
1000f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)                const size_t endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount();
1001f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)                if (minorAxisFinalPositionIndex.toInt() < endOfMinorAxis)
1002f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)                    break;
10035d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
10045d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)                // Discard empty grid area as it does not fit in the minor axis direction.
10055d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)                // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration.
10065d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)                emptyGridArea = nullptr;
1007926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)            }
1008197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1009197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // As we're moving to the next track in the major axis we should reset the auto-placement cursor in the minor axis.
1010197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            minorAxisAutoPlacementCursor = 0;
1011926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        }
1012f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)
10135d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        if (!emptyGridArea)
1014f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions);
10155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
1016926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
1017f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    insertItemIntoGrid(gridItem, *emptyGridArea);
1018197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // Move auto-placement cursor to the new position.
1019197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    autoPlacementCursor.first = emptyGridArea->rows.resolvedInitialPosition.toInt();
1020197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    autoPlacementCursor.second = emptyGridArea->columns.resolvedInitialPosition.toInt();
1021926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
1022926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
102319cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const
1024926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
1025197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return style()->isGridAutoFlowDirectionColumn() ? ForColumns : ForRows;
1026926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
1027926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
102819cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const
1029926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
1030197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return style()->isGridAutoFlowDirectionColumn() ? ForRows : ForColumns;
1031926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
1032926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
1033f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)void RenderGrid::dirtyGrid()
1034926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
1035f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    m_grid.resize(0);
1036926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    m_gridItemCoordinate.clear();
1037f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)    m_gridIsDirty = true;
103809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_gridItemsOverflowingGridArea.resize(0);
1039d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)    m_gridItemsIndexesMap.clear();
10405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}
10415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
10425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void RenderGrid::layoutGridItems()
10435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){
1044926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    placeItemsOnGrid();
1045926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
104606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    GridSizingData sizingData(gridColumnCount(), gridRowCount());
104709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    computeUsedBreadthOfGridTracks(ForColumns, sizingData);
104806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
104909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    computeUsedBreadthOfGridTracks(ForRows, sizingData);
105006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
10515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
105206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    populateGridPositions(sizingData);
105309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_gridItemsOverflowingGridArea.resize(0);
1054926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
10559bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)    for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
1056926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // Because the grid area cannot be styled, we don't need to adjust
1057926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        // the grid breadth to account for 'box-sizing'.
1058926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit();
1059926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit();
1060926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
10617242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(*child, ForColumns, sizingData.columnTracks);
10627242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(*child, ForRows, sizingData.rowTracks);
1063e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)
106410f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch        SubtreeLayoutScope layoutScope(*child);
10651e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && child->hasRelativeLogicalHeight()))
1066e1f1df5f01594c0e62e751e4b46e779b85c2faa5Torne (Richard Coles)            layoutScope.setNeedsLayout(child);
1067926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
1068926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth);
1069926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)        child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight);
1070926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
10715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // FIXME: Grid items should stretch to fill their cells. Once we
10725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // implement grid-{column,row}-align, we can also shrink to fit. For
10735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        // now, just size as if we were a regular child.
10745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        child->layoutIfNeeded();
10755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1076197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
10777242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        const GridCoordinate& coordinate = cachedGridCoordinate(*child);
1078a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        ASSERT(coordinate.columns.resolvedInitialPosition.toInt() < sizingData.columnTracks.size());
1079a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        ASSERT(coordinate.rows.resolvedInitialPosition.toInt() < sizingData.rowTracks.size());
108009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
10817242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        child->setLogicalLocation(findChildLogicalPosition(*child));
1082926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
108309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // Keep track of children overflowing their grid area as we might need to paint them even if the grid-area is
108409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // not visible
108509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (child->logicalHeight() > overrideContainingBlockContentLogicalHeight
108609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            || child->logicalWidth() > overrideContainingBlockContentLogicalWidth)
108709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            m_gridItemsOverflowingGridArea.append(child);
10885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    }
10895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
109006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    for (size_t i = 0; i < sizingData.rowTracks.size(); ++i)
109106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        setLogicalHeight(logicalHeight() + sizingData.rowTracks[i].m_usedBreadth);
1092926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
109351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)    // Min / max logical height is handled by the call to updateLogicalHeight in layoutBlock.
1094926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
1095926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
10965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}
10975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
10987242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciGridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox& gridItem) const
10995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){
11007242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(m_gridItemCoordinate.contains(&gridItem));
11017242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return m_gridItemCoordinate.get(&gridItem);
1102926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
11035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
11047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const
1105926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
1106926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    const GridCoordinate& coordinate = cachedGridCoordinate(child);
1107926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows;
1108926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    LayoutUnit gridAreaBreadth = 0;
1109f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    for (GridSpan::iterator trackPosition = span.begin(); trackPosition != span.end(); ++trackPosition)
1110a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        gridAreaBreadth += tracks[trackPosition.toInt()].m_usedBreadth;
1111926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    return gridAreaBreadth;
1112926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)}
1113926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)
111406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)void RenderGrid::populateGridPositions(const GridSizingData& sizingData)
11159bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles){
111606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    m_columnPositions.resize(sizingData.columnTracks.size() + 1);
11179bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)    m_columnPositions[0] = borderAndPaddingStart();
11189bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)    for (size_t i = 0; i < m_columnPositions.size() - 1; ++i)
111906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].m_usedBreadth;
11209bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)
112106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)    m_rowPositions.resize(sizingData.rowTracks.size() + 1);
11229bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)    m_rowPositions[0] = borderAndPaddingBefore();
11239bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)    for (size_t i = 0; i < m_rowPositions.size() - 1; ++i)
112406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)        m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].m_usedBreadth;
11259bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)}
11269bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)
11277242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::startOfColumnForChild(const RenderBox& child) const
1128926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){
1129926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)    const GridCoordinate& coordinate = cachedGridCoordinate(child);
1130a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
113109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // The grid items should be inside the grid container's border box, that's why they need to be shifted.
113209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // FIXME: This should account for the grid item's <overflow-position>.
11337242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return startOfColumn + marginStartForChild(&child);
113409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
11355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
11367242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::endOfColumnForChild(const RenderBox& child) const
113709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
113809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    const GridCoordinate& coordinate = cachedGridCoordinate(child);
1139a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
114053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)    // The grid items should be inside the grid container's border box, that's why they need to be shifted.
11417242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    LayoutUnit columnPosition = startOfColumn + marginStartForChild(&child);
114209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1143f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()];
114409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // FIXME: This should account for the grid item's <overflow-position>.
11457242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return columnPosition + std::max<LayoutUnit>(0, endOfColumn - m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()] - child.logicalWidth());
114609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
114709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
11487242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::columnPositionAlignedWithGridContainerStart(const RenderBox& child) const
114909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
115009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (style()->isLeftToRightDirection())
115109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return startOfColumnForChild(child);
115209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
115309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return endOfColumnForChild(child);
115409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
115509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
11567242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::columnPositionAlignedWithGridContainerEnd(const RenderBox& child) const
115709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
115809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (!style()->isLeftToRightDirection())
115909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return startOfColumnForChild(child);
116009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
116109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return endOfColumnForChild(child);
116209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
116309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
11647242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::centeredColumnPositionForChild(const RenderBox& child) const
116509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
116609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    const GridCoordinate& coordinate = cachedGridCoordinate(child);
1167a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()];
1168f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()];
11697242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    LayoutUnit columnPosition = startOfColumn + marginStartForChild(&child);
1170197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // FIXME: This should account for the grid item's <overflow-position>.
11717242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return columnPosition + std::max<LayoutUnit>(0, endOfColumn - startOfColumn - child.logicalWidth()) / 2;
11727242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci}
11737242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
11747242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccistatic ItemPosition resolveJustification(const RenderStyle* parentStyle, const RenderStyle* childStyle)
11757242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci{
11767242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ItemPosition justify = childStyle->justifySelf();
11777242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (justify == ItemPositionAuto)
11787242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        justify = (parentStyle->justifyItems() == ItemPositionAuto) ? ItemPositionStretch : parentStyle->justifyItems();
11797242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
11807242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return justify;
118109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
118209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
11837242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::columnPositionForChild(const RenderBox& child) const
118409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
11857242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
11867242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
11877242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    switch (resolveJustification(style(), child.style())) {
118809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionSelfStart:
11897242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // For orthogonal writing-modes, this computes to 'start'
11907242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
11917242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (hasOrthogonalWritingMode)
11927242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            return columnPositionAlignedWithGridContainerStart(child);
11937242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
119409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // self-start is based on the child's direction. That's why we need to check against the grid container's direction.
11957242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (child.style()->direction() != style()->direction())
119609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return columnPositionAlignedWithGridContainerEnd(child);
119709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
119809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return columnPositionAlignedWithGridContainerStart(child);
119909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionSelfEnd:
12007242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // For orthogonal writing-modes, this computes to 'start'
12017242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // FIXME: grid track sizing and positioning do not support orthogonal modes yet.
12027242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (hasOrthogonalWritingMode)
12037242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            return columnPositionAlignedWithGridContainerEnd(child);
12047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
120509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // self-end is based on the child's direction. That's why we need to check against the grid container's direction.
12067242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (child.style()->direction() != style()->direction())
120709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return columnPositionAlignedWithGridContainerStart(child);
120809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
120909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return columnPositionAlignedWithGridContainerEnd(child);
121009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
121109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionFlexStart:
121209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // Only used in flex layout, for other layout, it's equivalent to 'start'.
121309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return columnPositionAlignedWithGridContainerStart(child);
12147242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    case ItemPositionFlexEnd:
12157242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // Only used in flex layout, for other layout, it's equivalent to 'start'.
12167242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return columnPositionAlignedWithGridContainerEnd(child);
121709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
121809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionLeft:
121909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // If the property's axis is not parallel with the inline axis, this is equivalent to ‘start’.
122009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!isHorizontalWritingMode())
122109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return columnPositionAlignedWithGridContainerStart(child);
122209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
122309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (style()->isLeftToRightDirection())
122409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return columnPositionAlignedWithGridContainerStart(child);
122509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
122609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return columnPositionAlignedWithGridContainerEnd(child);
122709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionRight:
122809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // If the property's axis is not parallel with the inline axis, this is equivalent to ‘start’.
122909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!isHorizontalWritingMode())
123009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return columnPositionAlignedWithGridContainerStart(child);
123109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
123209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (style()->isLeftToRightDirection())
123309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return columnPositionAlignedWithGridContainerEnd(child);
123409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
123509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return columnPositionAlignedWithGridContainerStart(child);
123609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
123709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionCenter:
123809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return centeredColumnPositionForChild(child);
123909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionStart:
124009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return columnPositionAlignedWithGridContainerStart(child);
124109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionEnd:
124209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return columnPositionAlignedWithGridContainerEnd(child);
124309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
124409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionAuto:
12457242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        break;
124609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionStretch:
124709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    case ItemPositionBaseline:
1248197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionLastBaseline:
124909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // FIXME: Implement the previous values. For now, we always start align the child.
125009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return startOfColumnForChild(child);
125109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
125209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
125309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT_NOT_REACHED();
125409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return 0;
125509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
125609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
12577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::endOfRowForChild(const RenderBox& child) const
125809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
125909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    const GridCoordinate& coordinate = cachedGridCoordinate(child);
126009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1261a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()];
1262197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // The grid items should be inside the grid container's border box, that's why they need to be shifted.
12637242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    LayoutUnit rowPosition = startOfRow + marginBeforeForChild(&child);
126409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1265197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    LayoutUnit endOfRow = m_rowPositions[coordinate.rows.resolvedFinalPosition.next().toInt()];
1266197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // FIXME: This should account for the grid item's <overflow-position>.
12677242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return rowPosition + std::max<LayoutUnit>(0, endOfRow - startOfRow - child.logicalHeight());
1268197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1269197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
12707242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::startOfRowForChild(const RenderBox& child) const
1271197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1272197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    const GridCoordinate& coordinate = cachedGridCoordinate(child);
1273197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1274197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()];
1275197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // The grid items should be inside the grid container's border box, that's why they need to be shifted.
1276197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // FIXME: This should account for the grid item's <overflow-position>.
12777242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    LayoutUnit rowPosition = startOfRow + marginBeforeForChild(&child);
127809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
127909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return rowPosition;
128009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
128109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
12827242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::centeredRowPositionForChild(const RenderBox& child) const
1283197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1284197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    const GridCoordinate& coordinate = cachedGridCoordinate(child);
1285197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1286197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // The grid items should be inside the grid container's border box, that's why they need to be shifted.
12877242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()] + marginBeforeForChild(&child);
1288197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    LayoutUnit endOfRow = m_rowPositions[coordinate.rows.resolvedFinalPosition.next().toInt()];
1289197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1290197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // FIXME: This should account for the grid item's <overflow-position>.
12917242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return startOfRow + std::max<LayoutUnit>(0, endOfRow - startOfRow - child.logicalHeight()) / 2;
1292197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1293197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1294197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// FIXME: We should move this logic to the StyleAdjuster or the StyleBuilder.
1295197021e6b966cfb06891637935ef33fff06433d1Ben Murdochstatic ItemPosition resolveAlignment(const RenderStyle* parentStyle, const RenderStyle* childStyle)
1296197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1297197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ItemPosition align = childStyle->alignSelf();
1298c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    // The auto keyword computes to the parent's align-items computed value, or to "stretch", if not set or "auto".
1299197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (align == ItemPositionAuto)
1300197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        align = (parentStyle->alignItems() == ItemPositionAuto) ? ItemPositionStretch : parentStyle->alignItems();
1301197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return align;
1302197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1303197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
13047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutUnit RenderGrid::rowPositionForChild(const RenderBox& child) const
1305197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
13067242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    bool hasOrthogonalWritingMode = child.isHorizontalWritingMode() != isHorizontalWritingMode();
13077242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ItemPosition alignSelf = resolveAlignment(style(), child.style());
1308197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1309197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    switch (alignSelf) {
1310197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionSelfStart:
1311197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // If orthogonal writing-modes, this computes to 'Start'.
1312197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // FIXME: grid track sizing and positioning does not support orthogonal modes yet.
1313197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (hasOrthogonalWritingMode)
1314197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return startOfRowForChild(child);
1315197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1316197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // self-start is based on the child's block axis direction. That's why we need to check against the grid container's block flow.
13177242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (child.style()->writingMode() != style()->writingMode())
1318197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return endOfRowForChild(child);
1319197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1320197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return startOfRowForChild(child);
1321197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionSelfEnd:
1322197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // If orthogonal writing-modes, this computes to 'End'.
1323197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // FIXME: grid track sizing and positioning does not support orthogonal modes yet.
1324197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (hasOrthogonalWritingMode)
1325197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return endOfRowForChild(child);
1326197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1327197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // self-end is based on the child's block axis direction. That's why we need to check against the grid container's block flow.
13287242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (child.style()->writingMode() != style()->writingMode())
1329197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return startOfRowForChild(child);
1330197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1331197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return endOfRowForChild(child);
1332197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1333197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionLeft:
1334197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // orthogonal modes make property and inline axes to be parallel, but in any case
1335197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // this is always equivalent to 'Start'.
1336197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        //
1337197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // self-align's axis is never parallel to the inline axis, except in orthogonal
1338197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // writing-mode, so this is equivalent to 'Start’.
1339197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return startOfRowForChild(child);
1340197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1341197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionRight:
1342197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // orthogonal modes make property and inline axes to be parallel.
1343197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // FIXME: grid track sizing and positioning does not support orthogonal modes yet.
1344197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (hasOrthogonalWritingMode)
1345197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return endOfRowForChild(child);
1346197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1347197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // self-align's axis is never parallel to the inline axis, except in orthogonal
1348197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // writing-mode, so this is equivalent to 'Start'.
1349197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return startOfRowForChild(child);
1350197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1351197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionCenter:
1352197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return centeredRowPositionForChild(child);
1353197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Only used in flex layout, for other layout, it's equivalent to 'Start'.
1354197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionFlexStart:
1355197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionStart:
1356197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return startOfRowForChild(child);
1357197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Only used in flex layout, for other layout, it's equivalent to 'End'.
1358197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionFlexEnd:
1359197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionEnd:
1360197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return endOfRowForChild(child);
1361197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionStretch:
1362197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // FIXME: Implement the Stretch value. For now, we always start align the child.
1363197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return startOfRowForChild(child);
1364197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionBaseline:
1365197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionLastBaseline:
1366197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // FIXME: Implement the ItemPositionBaseline value. For now, we always start align the child.
1367197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return startOfRowForChild(child);
1368197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    case ItemPositionAuto:
1369197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        break;
1370197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1371197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1372197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ASSERT_NOT_REACHED();
1373197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return 0;
1374197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1375197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
13767242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano TucciLayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox& child) const
137709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
137809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return LayoutPoint(columnPositionForChild(child), rowPositionForChild(child));
13799bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)}
13809bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)
1381e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdochvoid RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
1382e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch{
13837242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    GridPainter(*this).paintChildren(paintInfo, paintOffset);
1384e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch}
1385e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch
13865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)const char* RenderGrid::renderName() const
13875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){
13885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    if (isFloating())
13895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return "RenderGrid (floating)";
13905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    if (isOutOfFlowPositioned())
13915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return "RenderGrid (positioned)";
13925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    if (isAnonymous())
13935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return "RenderGrid (generated)";
13945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    if (isRelPositioned())
13955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        return "RenderGrid (relative positioned)";
13965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)    return "RenderGrid";
13975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}
13985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
1399c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink
1400