f56b58d81151d57b6898dd259b92e5857438a445
[WebKit-https.git] / Source / WebCore / rendering / Grid.cpp
1 /*
2  * Copyright (C) 2017 Igalia S.L.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "Grid.h"
28
29 #if ENABLE(CSS_GRID_LAYOUT)
30
31 #include "GridArea.h"
32 #include "RenderGrid.h"
33
34 namespace WebCore {
35
36 Grid::Grid(RenderGrid& grid)
37     : m_orderIterator(grid)
38 {
39 }
40
41 unsigned Grid::numTracks(GridTrackSizingDirection direction) const
42 {
43     if (direction == ForRows)
44         return m_grid.size();
45     return m_grid.size() ? m_grid[0].size() : 0;
46 }
47
48 void Grid::ensureGridSize(unsigned maximumRowSize, unsigned maximumColumnSize)
49 {
50     const size_t oldColumnSize = numTracks(ForColumns);
51     const size_t oldRowSize = numTracks(ForRows);
52     if (maximumRowSize > oldRowSize) {
53         m_grid.grow(maximumRowSize);
54         for (size_t row = oldRowSize; row < maximumRowSize; ++row)
55             m_grid[row].grow(oldColumnSize);
56     }
57
58     if (maximumColumnSize > oldColumnSize) {
59         for (size_t row = 0; row < numTracks(ForRows); ++row)
60             m_grid[row].grow(maximumColumnSize);
61     }
62 }
63
64 void Grid::insert(RenderBox& child, const GridArea& area)
65 {
66     ASSERT(area.rows.isTranslatedDefinite() && area.columns.isTranslatedDefinite());
67     ensureGridSize(area.rows.endLine(), area.columns.endLine());
68
69     for (const auto& row : area.rows) {
70         for (const auto& column : area.columns)
71             m_grid[row][column].append(&child);
72     }
73
74     setGridItemArea(child, area);
75 }
76
77 void Grid::setSmallestTracksStart(int rowStart, int columnStart)
78 {
79     m_smallestRowStart = rowStart;
80     m_smallestColumnStart = columnStart;
81 }
82
83 int Grid::smallestTrackStart(GridTrackSizingDirection direction) const
84 {
85     return direction == ForRows ? m_smallestRowStart : m_smallestColumnStart;
86 }
87
88 GridArea Grid::gridItemArea(const RenderBox& item) const
89 {
90     ASSERT(m_gridItemArea.contains(&item));
91     return m_gridItemArea.get(&item);
92 }
93
94 void Grid::setGridItemArea(const RenderBox& item, GridArea area)
95 {
96     m_gridItemArea.set(&item, area);
97 }
98
99 void Grid::setAutoRepeatTracks(unsigned autoRepeatRows, unsigned autoRepeatColumns)
100 {
101     m_autoRepeatRows = autoRepeatRows;
102     m_autoRepeatColumns =  autoRepeatColumns;
103 }
104
105 unsigned Grid::autoRepeatTracks(GridTrackSizingDirection direction) const
106 {
107     return direction == ForRows ? m_autoRepeatRows : m_autoRepeatColumns;
108 }
109
110 void Grid::setAutoRepeatEmptyColumns(std::unique_ptr<OrderedTrackIndexSet> autoRepeatEmptyColumns)
111 {
112     m_autoRepeatEmptyColumns = WTFMove(autoRepeatEmptyColumns);
113 }
114
115 void Grid::setAutoRepeatEmptyRows(std::unique_ptr<OrderedTrackIndexSet> autoRepeatEmptyRows)
116 {
117     m_autoRepeatEmptyRows = WTFMove(autoRepeatEmptyRows);
118 }
119
120 bool Grid::hasAutoRepeatEmptyTracks(GridTrackSizingDirection direction) const
121 {
122     return direction == ForColumns ? !!m_autoRepeatEmptyColumns : !!m_autoRepeatEmptyRows;
123 }
124
125 bool Grid::isEmptyAutoRepeatTrack(GridTrackSizingDirection direction, unsigned line) const
126 {
127     ASSERT(hasAutoRepeatEmptyTracks(direction));
128     return autoRepeatEmptyTracks(direction)->contains(line);
129 }
130
131 OrderedTrackIndexSet* Grid::autoRepeatEmptyTracks(GridTrackSizingDirection direction) const
132 {
133     ASSERT(hasAutoRepeatEmptyTracks(direction));
134     return direction == ForColumns ? m_autoRepeatEmptyColumns.get() : m_autoRepeatEmptyRows.get();
135 }
136
137 GridSpan Grid::gridItemSpan(const RenderBox& gridItem, GridTrackSizingDirection direction) const
138 {
139     GridArea area = gridItemArea(gridItem);
140     return direction == ForColumns ? area.columns : area.rows;
141 }
142
143 void Grid::setNeedsItemsPlacement(bool needsItemsPlacement)
144 {
145     m_needsItemsPlacement = needsItemsPlacement;
146
147     if (!needsItemsPlacement) {
148         m_grid.shrinkToFit();
149         return;
150     }
151
152     m_grid.resize(0);
153     m_gridItemArea.clear();
154     m_hasAnyOrthogonalGridItem = false;
155     m_smallestRowStart = 0;
156     m_smallestColumnStart = 0;
157     m_autoRepeatEmptyColumns = nullptr;
158     m_autoRepeatEmptyRows = nullptr;
159     m_autoRepeatColumns = 0;
160     m_autoRepeatRows = 0;
161 }
162
163 GridIterator::GridIterator(const Grid& grid, GridTrackSizingDirection direction, unsigned fixedTrackIndex, unsigned varyingTrackIndex)
164     : m_grid(grid.m_grid)
165     , m_direction(direction)
166     , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
167     , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
168     , m_childIndex(0)
169 {
170     ASSERT(!m_grid.isEmpty());
171     ASSERT(!m_grid[0].isEmpty());
172     ASSERT(m_rowIndex < m_grid.size());
173     ASSERT(m_columnIndex < m_grid[0].size());
174 }
175
176 RenderBox* GridIterator::nextGridItem()
177 {
178     ASSERT(!m_grid.isEmpty());
179     ASSERT(!m_grid[0].isEmpty());
180
181     unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
182     const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
183     for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
184         const auto& children = m_grid[m_rowIndex][m_columnIndex];
185         if (m_childIndex < children.size())
186             return children[m_childIndex++];
187
188         m_childIndex = 0;
189     }
190     return 0;
191 }
192
193 bool GridIterator::isEmptyAreaEnough(unsigned rowSpan, unsigned columnSpan) const
194 {
195     ASSERT(!m_grid.isEmpty());
196     ASSERT(!m_grid[0].isEmpty());
197
198     // Ignore cells outside current grid as we will grow it later if needed.
199     unsigned maxRows = std::min<unsigned>(m_rowIndex + rowSpan, m_grid.size());
200     unsigned maxColumns = std::min<unsigned>(m_columnIndex + columnSpan, m_grid[0].size());
201
202     // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
203     for (unsigned row = m_rowIndex; row < maxRows; ++row) {
204         for (unsigned column = m_columnIndex; column < maxColumns; ++column) {
205             auto& children = m_grid[row][column];
206             if (!children.isEmpty())
207                 return false;
208         }
209     }
210
211     return true;
212 }
213
214 std::unique_ptr<GridArea> GridIterator::nextEmptyGridArea(unsigned fixedTrackSpan, unsigned varyingTrackSpan)
215 {
216     ASSERT(!m_grid.isEmpty());
217     ASSERT(!m_grid[0].isEmpty());
218     ASSERT(fixedTrackSpan >= 1);
219     ASSERT(varyingTrackSpan >= 1);
220
221     if (m_grid.isEmpty())
222         return nullptr;
223
224     unsigned rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
225     unsigned columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
226
227     unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
228     const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
229     for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
230         if (isEmptyAreaEnough(rowSpan, columnSpan)) {
231             std::unique_ptr<GridArea> result = std::make_unique<GridArea>(GridSpan::translatedDefiniteGridSpan(m_rowIndex, m_rowIndex + rowSpan), GridSpan::translatedDefiniteGridSpan(m_columnIndex, m_columnIndex + columnSpan));
232             // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
233             ++varyingTrackIndex;
234             return result;
235         }
236     }
237     return nullptr;
238 }
239
240 } // namespace WebCore
241
242 #endif  /* ENABLE(CSS_GRID_LAYOUT) */