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#include "GridArea.h"
30#include "RenderGrid.h"
31
32namespace WebCore {
33
34Grid::Grid(RenderGrid& grid)
35 : m_orderIterator(grid)
36{
37}
38
39unsigned Grid::numTracks(GridTrackSizingDirection direction) const
40{
41 if (direction == ForRows)
42 return m_grid.size();
43 return m_grid.size() ? m_grid[0].size() : 0;
44}
45
46void Grid::ensureGridSize(unsigned maximumRowSize, unsigned maximumColumnSize)
47{
48 ASSERT(static_cast<int>(maximumRowSize) < GridPosition::max() * 2);
49 ASSERT(static_cast<int>(maximumColumnSize) < GridPosition::max() * 2);
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
64void 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 (auto row : area.rows) {
70 for (auto column : area.columns)
71 m_grid[row][column].append(makeWeakPtr(child));
72 }
73
74 setGridItemArea(child, area);
75}
76
77void Grid::setSmallestTracksStart(int rowStart, int columnStart)
78{
79 ASSERT(rowStart > GridPosition::min() && rowStart < GridPosition::max() - 1);
80 ASSERT(columnStart > GridPosition::min() && columnStart < GridPosition::max() - 1);
81 m_smallestRowStart = rowStart;
82 m_smallestColumnStart = columnStart;
83}
84
85int Grid::smallestTrackStart(GridTrackSizingDirection direction) const
86{
87 return direction == ForRows ? m_smallestRowStart : m_smallestColumnStart;
88}
89
90GridArea Grid::gridItemArea(const RenderBox& item) const
91{
92 ASSERT(m_gridItemArea.contains(&item));
93 return m_gridItemArea.get(&item);
94}
95
96void Grid::setGridItemArea(const RenderBox& item, GridArea area)
97{
98 m_gridItemArea.set(&item, area);
99}
100
101void Grid::setAutoRepeatTracks(unsigned autoRepeatRows, unsigned autoRepeatColumns)
102{
103 ASSERT(static_cast<unsigned>(GridPosition::max()) >= numTracks(ForRows) + autoRepeatRows);
104 ASSERT(static_cast<unsigned>(GridPosition::max()) >= numTracks(ForColumns) + autoRepeatColumns);
105 m_autoRepeatRows = autoRepeatRows;
106 m_autoRepeatColumns = autoRepeatColumns;
107}
108
109unsigned Grid::autoRepeatTracks(GridTrackSizingDirection direction) const
110{
111 return direction == ForRows ? m_autoRepeatRows : m_autoRepeatColumns;
112}
113
114void Grid::setAutoRepeatEmptyColumns(std::unique_ptr<OrderedTrackIndexSet> autoRepeatEmptyColumns)
115{
116 ASSERT(!autoRepeatEmptyColumns || (autoRepeatEmptyColumns->size() <= m_autoRepeatColumns));
117 m_autoRepeatEmptyColumns = WTFMove(autoRepeatEmptyColumns);
118}
119
120void Grid::setAutoRepeatEmptyRows(std::unique_ptr<OrderedTrackIndexSet> autoRepeatEmptyRows)
121{
122 ASSERT(!autoRepeatEmptyRows || (autoRepeatEmptyRows->size() <= m_autoRepeatRows));
123 m_autoRepeatEmptyRows = WTFMove(autoRepeatEmptyRows);
124}
125
126bool Grid::hasAutoRepeatEmptyTracks(GridTrackSizingDirection direction) const
127{
128 return direction == ForColumns ? !!m_autoRepeatEmptyColumns : !!m_autoRepeatEmptyRows;
129}
130
131bool Grid::isEmptyAutoRepeatTrack(GridTrackSizingDirection direction, unsigned line) const
132{
133 ASSERT(hasAutoRepeatEmptyTracks(direction));
134 return autoRepeatEmptyTracks(direction)->contains(line);
135}
136
137OrderedTrackIndexSet* Grid::autoRepeatEmptyTracks(GridTrackSizingDirection direction) const
138{
139 ASSERT(hasAutoRepeatEmptyTracks(direction));
140 return direction == ForColumns ? m_autoRepeatEmptyColumns.get() : m_autoRepeatEmptyRows.get();
141}
142
143GridSpan Grid::gridItemSpan(const RenderBox& gridItem, GridTrackSizingDirection direction) const
144{
145 GridArea area = gridItemArea(gridItem);
146 return direction == ForColumns ? area.columns : area.rows;
147}
148
149void Grid::setNeedsItemsPlacement(bool needsItemsPlacement)
150{
151 m_needsItemsPlacement = needsItemsPlacement;
152
153 if (!needsItemsPlacement) {
154 m_grid.shrinkToFit();
155 return;
156 }
157
158 m_grid.shrink(0);
159 m_gridItemArea.clear();
160 m_smallestRowStart = 0;
161 m_smallestColumnStart = 0;
162 m_autoRepeatEmptyColumns = nullptr;
163 m_autoRepeatEmptyRows = nullptr;
164 m_autoRepeatColumns = 0;
165 m_autoRepeatRows = 0;
166}
167
168GridIterator::GridIterator(const Grid& grid, GridTrackSizingDirection direction, unsigned fixedTrackIndex, unsigned varyingTrackIndex)
169 : m_grid(grid.m_grid)
170 , m_direction(direction)
171 , m_rowIndex((direction == ForColumns) ? varyingTrackIndex : fixedTrackIndex)
172 , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : varyingTrackIndex)
173 , m_childIndex(0)
174{
175 ASSERT(!m_grid.isEmpty());
176 ASSERT(!m_grid[0].isEmpty());
177 ASSERT(m_rowIndex < m_grid.size());
178 ASSERT(m_columnIndex < m_grid[0].size());
179}
180
181RenderBox* GridIterator::nextGridItem()
182{
183 ASSERT(!m_grid.isEmpty());
184 ASSERT(!m_grid[0].isEmpty());
185
186 unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
187 const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
188 for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
189 const auto& children = m_grid[m_rowIndex][m_columnIndex];
190 if (m_childIndex < children.size())
191 return children[m_childIndex++].get();
192
193 m_childIndex = 0;
194 }
195 return 0;
196}
197
198bool GridIterator::isEmptyAreaEnough(unsigned rowSpan, unsigned columnSpan) const
199{
200 ASSERT(!m_grid.isEmpty());
201 ASSERT(!m_grid[0].isEmpty());
202
203 // Ignore cells outside current grid as we will grow it later if needed.
204 unsigned maxRows = std::min<unsigned>(m_rowIndex + rowSpan, m_grid.size());
205 unsigned maxColumns = std::min<unsigned>(m_columnIndex + columnSpan, m_grid[0].size());
206
207 // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small.
208 for (unsigned row = m_rowIndex; row < maxRows; ++row) {
209 for (unsigned column = m_columnIndex; column < maxColumns; ++column) {
210 auto& children = m_grid[row][column];
211 if (!children.isEmpty())
212 return false;
213 }
214 }
215
216 return true;
217}
218
219std::unique_ptr<GridArea> GridIterator::nextEmptyGridArea(unsigned fixedTrackSpan, unsigned varyingTrackSpan)
220{
221 ASSERT(!m_grid.isEmpty());
222 ASSERT(!m_grid[0].isEmpty());
223 ASSERT(fixedTrackSpan >= 1);
224 ASSERT(varyingTrackSpan >= 1);
225
226 if (m_grid.isEmpty())
227 return nullptr;
228
229 unsigned rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan;
230 unsigned columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan;
231
232 unsigned& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex;
233 const unsigned endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size();
234 for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) {
235 if (isEmptyAreaEnough(rowSpan, columnSpan)) {
236 std::unique_ptr<GridArea> result = std::make_unique<GridArea>(GridSpan::translatedDefiniteGridSpan(m_rowIndex, m_rowIndex + rowSpan), GridSpan::translatedDefiniteGridSpan(m_columnIndex, m_columnIndex + columnSpan));
237 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over.
238 ++varyingTrackIndex;
239 return result;
240 }
241 }
242 return nullptr;
243}
244
245} // namespace WebCore
246