1/*
2 * Copyright (C) 2014-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 are
6 * met:
7 *
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 * * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include "config.h"
32#include "GridPositionsResolver.h"
33
34#include "GridArea.h"
35#include "RenderBox.h"
36#include <cstdlib>
37
38namespace WebCore {
39
40static inline bool isColumnSide(GridPositionSide side)
41{
42 return side == ColumnStartSide || side == ColumnEndSide;
43}
44
45static inline bool isStartSide(GridPositionSide side)
46{
47 return side == ColumnStartSide || side == RowStartSide;
48}
49
50static inline GridTrackSizingDirection directionFromSide(GridPositionSide side)
51{
52 return side == ColumnStartSide || side == ColumnEndSide ? ForColumns : ForRows;
53}
54
55static const String implicitNamedGridLineForSide(const String& lineName, GridPositionSide side)
56{
57 return lineName + (isStartSide(side) ? "-start" : "-end");
58}
59
60NamedLineCollection::NamedLineCollection(const RenderStyle& gridContainerStyle, const String& namedLine, GridTrackSizingDirection direction, unsigned lastLine, unsigned autoRepeatTracksCount)
61 : m_lastLine(lastLine)
62 , m_autoRepeatTotalTracks(autoRepeatTracksCount)
63{
64 bool isRowAxis = direction == ForColumns;
65 const NamedGridLinesMap& gridLineNames = isRowAxis ? gridContainerStyle.namedGridColumnLines() : gridContainerStyle.namedGridRowLines();
66 const NamedGridLinesMap& autoRepeatGridLineNames = isRowAxis ? gridContainerStyle.autoRepeatNamedGridColumnLines() : gridContainerStyle.autoRepeatNamedGridRowLines();
67
68 auto linesIterator = gridLineNames.find(namedLine);
69 m_namedLinesIndexes = linesIterator == gridLineNames.end() ? nullptr : &linesIterator->value;
70
71 auto autoRepeatLinesIterator = autoRepeatGridLineNames.find(namedLine);
72 m_autoRepeatNamedLinesIndexes = autoRepeatLinesIterator == autoRepeatGridLineNames.end() ? nullptr : &autoRepeatLinesIterator->value;
73
74 m_insertionPoint = isRowAxis ? gridContainerStyle.gridAutoRepeatColumnsInsertionPoint() : gridContainerStyle.gridAutoRepeatRowsInsertionPoint();
75
76 m_autoRepeatTrackListLength = isRowAxis ? gridContainerStyle.gridAutoRepeatColumns().size() : gridContainerStyle.gridAutoRepeatRows().size();
77}
78
79bool NamedLineCollection::hasNamedLines() const
80{
81 return m_namedLinesIndexes || m_autoRepeatNamedLinesIndexes;
82}
83
84size_t NamedLineCollection::find(unsigned line) const
85{
86 if (line > m_lastLine)
87 return notFound;
88
89 if (!m_autoRepeatNamedLinesIndexes || line < m_insertionPoint)
90 return m_namedLinesIndexes ? m_namedLinesIndexes->find(line) : notFound;
91
92 if (line <= (m_insertionPoint + m_autoRepeatTotalTracks)) {
93 size_t localIndex = line - m_insertionPoint;
94
95 size_t indexInFirstRepetition = localIndex % m_autoRepeatTrackListLength;
96 if (indexInFirstRepetition)
97 return m_autoRepeatNamedLinesIndexes->find(indexInFirstRepetition);
98
99 // The line names defined in the last line are also present in the first line of the next
100 // repetition (if any). Same for the line names defined in the first line.
101 if (localIndex == m_autoRepeatTotalTracks)
102 return m_autoRepeatNamedLinesIndexes->find(m_autoRepeatTrackListLength);
103 size_t position = m_autoRepeatNamedLinesIndexes->find(0u);
104 if (position != notFound)
105 return position;
106 return localIndex ? m_autoRepeatNamedLinesIndexes->find(m_autoRepeatTrackListLength) : notFound;
107 }
108
109 return m_namedLinesIndexes ? m_namedLinesIndexes->find(line - (m_autoRepeatTotalTracks - 1)) : notFound;
110}
111
112bool NamedLineCollection::contains(unsigned line) const
113{
114 ASSERT(hasNamedLines());
115 return find(line) != notFound;
116}
117
118unsigned NamedLineCollection::firstPosition() const
119{
120 ASSERT(hasNamedLines());
121 unsigned firstLine = 0;
122
123 if (!m_autoRepeatNamedLinesIndexes) {
124 if (!m_insertionPoint || m_insertionPoint < m_namedLinesIndexes->at(firstLine))
125 return m_namedLinesIndexes->at(firstLine) + (m_autoRepeatTotalTracks ? m_autoRepeatTotalTracks - 1 : 0);
126 return m_namedLinesIndexes->at(firstLine);
127 }
128
129 if (!m_namedLinesIndexes)
130 return m_autoRepeatNamedLinesIndexes->at(firstLine) + m_insertionPoint;
131
132 if (!m_insertionPoint)
133 return std::min(m_namedLinesIndexes->at(firstLine) + m_autoRepeatTotalTracks, m_autoRepeatNamedLinesIndexes->at(firstLine));
134
135 return std::min(m_namedLinesIndexes->at(firstLine), m_autoRepeatNamedLinesIndexes->at(firstLine) + m_insertionPoint);
136}
137
138static void adjustGridPositionsFromStyle(const RenderBox& gridItem, GridTrackSizingDirection direction, GridPosition& initialPosition, GridPosition& finalPosition)
139{
140 bool isForColumns = direction == ForColumns;
141 initialPosition = isForColumns ? gridItem.style().gridItemColumnStart() : gridItem.style().gridItemRowStart();
142 finalPosition = isForColumns ? gridItem.style().gridItemColumnEnd() : gridItem.style().gridItemRowEnd();
143
144 // We must handle the placement error handling code here instead of in the StyleAdjuster because we don't want to
145 // overwrite the specified values.
146 if (initialPosition.isSpan() && finalPosition.isSpan())
147 finalPosition.setAutoPosition();
148
149 // If the grid item has an automatic position and a grid span for a named line in a given dimension, instead treat the grid span as one.
150 if (initialPosition.isAuto() && finalPosition.isSpan() && !finalPosition.namedGridLine().isNull())
151 finalPosition.setSpanPosition(1, String());
152 if (finalPosition.isAuto() && initialPosition.isSpan() && !initialPosition.namedGridLine().isNull())
153 initialPosition.setSpanPosition(1, String());
154}
155
156unsigned GridPositionsResolver::explicitGridColumnCount(const RenderStyle& gridContainerStyle, unsigned autoRepeatTracksCount)
157{
158 return std::min<unsigned>(std::max(gridContainerStyle.gridColumns().size() + autoRepeatTracksCount, gridContainerStyle.namedGridAreaColumnCount()), GridPosition::max());
159}
160
161unsigned GridPositionsResolver::explicitGridRowCount(const RenderStyle& gridContainerStyle, unsigned autoRepeatTracksCount)
162{
163 return std::min<unsigned>(std::max(gridContainerStyle.gridRows().size() + autoRepeatTracksCount, gridContainerStyle.namedGridAreaRowCount()), GridPosition::max());
164}
165
166static unsigned explicitGridSizeForSide(const RenderStyle& gridContainerStyle, GridPositionSide side, unsigned autoRepeatTracksCount)
167{
168 return isColumnSide(side) ? GridPositionsResolver::explicitGridColumnCount(gridContainerStyle, autoRepeatTracksCount) : GridPositionsResolver::explicitGridRowCount(gridContainerStyle, autoRepeatTracksCount);
169}
170
171static unsigned lookAheadForNamedGridLine(int start, unsigned numberOfLines, unsigned gridLastLine, NamedLineCollection& linesCollection)
172{
173 ASSERT(numberOfLines);
174
175 // Only implicit lines on the search direction are assumed to have the given name, so we can start to look from first line.
176 // See: https://drafts.csswg.org/css-grid/#grid-placement-span-int
177 unsigned end = std::max(start, 0);
178
179 if (!linesCollection.hasNamedLines())
180 return std::max(end, gridLastLine + 1) + numberOfLines - 1;
181
182 for (; numberOfLines; ++end) {
183 if (end > gridLastLine || linesCollection.contains(end))
184 numberOfLines--;
185 }
186
187 ASSERT(end);
188 return end - 1;
189}
190
191static int lookBackForNamedGridLine(int end, unsigned numberOfLines, int gridLastLine, NamedLineCollection& linesCollection)
192{
193 ASSERT(numberOfLines);
194
195 // Only implicit lines on the search direction are assumed to have the given name, so we can start to look from last line.
196 // See: https://drafts.csswg.org/css-grid/#grid-placement-span-int
197 int start = std::min(end, gridLastLine);
198
199 if (!linesCollection.hasNamedLines())
200 return std::min(start, -1) - numberOfLines + 1;
201
202 for (; numberOfLines; --start) {
203 if (start < 0 || linesCollection.contains(start))
204 numberOfLines--;
205 }
206
207 return start + 1;
208}
209
210static int resolveNamedGridLinePositionFromStyle(const RenderStyle& gridContainerStyle, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
211{
212 ASSERT(!position.namedGridLine().isNull());
213
214 unsigned lastLine = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
215 NamedLineCollection linesCollection(gridContainerStyle, position.namedGridLine(), directionFromSide(side), lastLine, autoRepeatTracksCount);
216
217 if (position.isPositive())
218 return lookAheadForNamedGridLine(0, std::abs(position.integerPosition()), lastLine, linesCollection);
219 return lookBackForNamedGridLine(lastLine, std::abs(position.integerPosition()), lastLine, linesCollection);
220}
221
222static GridSpan definiteGridSpanWithNamedLineSpanAgainstOpposite(int oppositeLine, const GridPosition& position, GridPositionSide side, unsigned lastLine, NamedLineCollection& linesCollection)
223{
224 int start, end;
225 if (side == RowStartSide || side == ColumnStartSide) {
226 start = lookBackForNamedGridLine(oppositeLine - 1, position.spanPosition(), lastLine, linesCollection);
227 end = oppositeLine;
228 } else {
229 start = oppositeLine;
230 end = lookAheadForNamedGridLine(oppositeLine + 1, position.spanPosition(), lastLine, linesCollection);
231 }
232
233 return GridSpan::untranslatedDefiniteGridSpan(start, end);
234}
235
236static GridSpan resolveNamedGridLinePositionAgainstOppositePosition(const RenderStyle& gridContainerStyle, int oppositeLine, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
237{
238 ASSERT(position.isSpan());
239 ASSERT(!position.namedGridLine().isNull());
240 // Negative positions are not allowed per the specification and should have been handled during parsing.
241 ASSERT(position.spanPosition() > 0);
242
243 unsigned lastLine = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
244 NamedLineCollection linesCollection(gridContainerStyle, position.namedGridLine(), directionFromSide(side), lastLine, autoRepeatTracksCount);
245 return definiteGridSpanWithNamedLineSpanAgainstOpposite(oppositeLine, position, side, lastLine, linesCollection);
246}
247
248static GridSpan resolveGridPositionAgainstOppositePosition(const RenderStyle& gridContainerStyle, int oppositeLine, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
249{
250 if (position.isAuto()) {
251 if (isStartSide(side))
252 return GridSpan::untranslatedDefiniteGridSpan(oppositeLine - 1, oppositeLine);
253 return GridSpan::untranslatedDefiniteGridSpan(oppositeLine, oppositeLine + 1);
254 }
255
256 ASSERT(position.isSpan());
257 ASSERT(position.spanPosition() > 0);
258
259 if (!position.namedGridLine().isNull()) {
260 // span 2 'c' -> we need to find the appropriate grid line before / after our opposite position.
261 return resolveNamedGridLinePositionAgainstOppositePosition(gridContainerStyle, oppositeLine, position, side, autoRepeatTracksCount);
262 }
263
264 // 'span 1' is contained inside a single grid track regardless of the direction.
265 // That's why the CSS span value is one more than the offset we apply.
266 unsigned positionOffset = position.spanPosition();
267 if (isStartSide(side))
268 return GridSpan::untranslatedDefiniteGridSpan(oppositeLine - positionOffset, oppositeLine);
269
270 return GridSpan::untranslatedDefiniteGridSpan(oppositeLine, oppositeLine + positionOffset);
271}
272
273GridPositionSide GridPositionsResolver::initialPositionSide(GridTrackSizingDirection direction)
274{
275 return direction == ForColumns ? ColumnStartSide : RowStartSide;
276}
277
278GridPositionSide GridPositionsResolver::finalPositionSide(GridTrackSizingDirection direction)
279{
280 return direction == ForColumns ? ColumnEndSide : RowEndSide;
281}
282
283unsigned GridPositionsResolver::spanSizeForAutoPlacedItem(const RenderBox& gridItem, GridTrackSizingDirection direction)
284{
285 GridPosition initialPosition, finalPosition;
286 adjustGridPositionsFromStyle(gridItem, direction, initialPosition, finalPosition);
287
288 // This method will only be used when both positions need to be resolved against the opposite one.
289 ASSERT(initialPosition.shouldBeResolvedAgainstOppositePosition() && finalPosition.shouldBeResolvedAgainstOppositePosition());
290
291 if (initialPosition.isAuto() && finalPosition.isAuto())
292 return 1;
293
294 GridPosition position = initialPosition.isSpan() ? initialPosition : finalPosition;
295 ASSERT(position.isSpan());
296
297 ASSERT(position.spanPosition());
298 return position.spanPosition();
299}
300
301static int resolveGridPositionFromStyle(const RenderStyle& gridContainerStyle, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
302{
303 switch (position.type()) {
304 case ExplicitPosition: {
305 ASSERT(position.integerPosition());
306
307 if (!position.namedGridLine().isNull())
308 return resolveNamedGridLinePositionFromStyle(gridContainerStyle, position, side, autoRepeatTracksCount);
309
310 // Handle <integer> explicit position.
311 if (position.isPositive())
312 return position.integerPosition() - 1;
313
314 unsigned resolvedPosition = std::abs(position.integerPosition()) - 1;
315 const unsigned endOfTrack = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
316
317 return endOfTrack - resolvedPosition;
318 }
319 case NamedGridAreaPosition:
320 {
321 // First attempt to match the grid area's edge to a named grid area: if there is a named line with the name
322 // ''<custom-ident>-start (for grid-*-start) / <custom-ident>-end'' (for grid-*-end), contributes the first such
323 // line to the grid item's placement.
324 String namedGridLine = position.namedGridLine();
325 ASSERT(!position.namedGridLine().isNull());
326
327 unsigned lastLine = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
328 NamedLineCollection implicitLines(gridContainerStyle, implicitNamedGridLineForSide(namedGridLine, side), directionFromSide(side), lastLine, autoRepeatTracksCount);
329 if (implicitLines.hasNamedLines())
330 return implicitLines.firstPosition();
331
332 // Otherwise, if there is a named line with the specified name, contributes the first such line to the grid
333 // item's placement.
334 NamedLineCollection explicitLines(gridContainerStyle, namedGridLine, directionFromSide(side), lastLine, autoRepeatTracksCount);
335 if (explicitLines.hasNamedLines())
336 return explicitLines.firstPosition();
337
338 // If none of the above works specs mandate to assume that all the lines in the implicit grid have this name.
339 return lastLine + 1;
340 }
341 case AutoPosition:
342 case SpanPosition:
343 // 'auto' and span depend on the opposite position for resolution (e.g. grid-row: auto / 1 or grid-column: span 3 / "myHeader").
344 ASSERT_NOT_REACHED();
345 return 0;
346 }
347 ASSERT_NOT_REACHED();
348 return 0;
349}
350
351GridSpan GridPositionsResolver::resolveGridPositionsFromStyle(const RenderStyle& gridContainerStyle, const RenderBox& gridItem, GridTrackSizingDirection direction, unsigned autoRepeatTracksCount)
352{
353 GridPosition initialPosition, finalPosition;
354 adjustGridPositionsFromStyle(gridItem, direction, initialPosition, finalPosition);
355
356 GridPositionSide initialSide = initialPositionSide(direction);
357 GridPositionSide finalSide = finalPositionSide(direction);
358
359 // We can't get our grid positions without running the auto placement algorithm.
360 if (initialPosition.shouldBeResolvedAgainstOppositePosition() && finalPosition.shouldBeResolvedAgainstOppositePosition())
361 return GridSpan::indefiniteGridSpan();
362
363 if (initialPosition.shouldBeResolvedAgainstOppositePosition()) {
364 // Infer the position from the final position ('auto / 1' or 'span 2 / 3' case).
365 auto endLine = resolveGridPositionFromStyle(gridContainerStyle, finalPosition, finalSide, autoRepeatTracksCount);
366 return resolveGridPositionAgainstOppositePosition(gridContainerStyle, endLine, initialPosition, initialSide, autoRepeatTracksCount);
367 }
368
369 if (finalPosition.shouldBeResolvedAgainstOppositePosition()) {
370 // Infer our position from the initial position ('1 / auto' or '3 / span 2' case).
371 auto startLine = resolveGridPositionFromStyle(gridContainerStyle, initialPosition, initialSide, autoRepeatTracksCount);
372 return resolveGridPositionAgainstOppositePosition(gridContainerStyle, startLine, finalPosition, finalSide, autoRepeatTracksCount);
373 }
374
375 int startLine = resolveGridPositionFromStyle(gridContainerStyle, initialPosition, initialSide, autoRepeatTracksCount);
376 int endLine = resolveGridPositionFromStyle(gridContainerStyle, finalPosition, finalSide, autoRepeatTracksCount);
377
378 if (startLine > endLine)
379 std::swap(startLine, endLine);
380 else if (startLine == endLine)
381 endLine = startLine + 1;
382
383 return GridSpan::untranslatedDefiniteGridSpan(startLine, std::max(startLine, endLine));
384}
385
386} // namespace WebCore
387