[css-grid] Remove compilation flag ENABLE_CSS_GRID_LAYOUT
[WebKit-https.git] / Source / WebCore / rendering / style / GridPositionsResolver.cpp
1 /*
2  * Copyright (C) 2014-2016 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
38 namespace WebCore {
39
40 static inline bool isColumnSide(GridPositionSide side)
41 {
42     return side == ColumnStartSide || side == ColumnEndSide;
43 }
44
45 static inline bool isStartSide(GridPositionSide side)
46 {
47     return side == ColumnStartSide || side == RowStartSide;
48 }
49
50 static inline GridPositionSide initialPositionSide(GridTrackSizingDirection direction)
51 {
52     return direction == ForColumns ? ColumnStartSide : RowStartSide;
53 }
54
55 static inline GridPositionSide finalPositionSide(GridTrackSizingDirection direction)
56 {
57     return direction == ForColumns ? ColumnEndSide : RowEndSide;
58 }
59
60 static inline GridTrackSizingDirection directionFromSide(GridPositionSide side)
61 {
62     return side == ColumnStartSide || side == ColumnEndSide ? ForColumns : ForRows;
63 }
64
65 static const String implicitNamedGridLineForSide(const String& lineName, GridPositionSide side)
66 {
67     return lineName + (isStartSide(side) ? "-start" : "-end");
68 }
69
70 NamedLineCollection::NamedLineCollection(const RenderStyle& gridContainerStyle, const String& namedLine, GridTrackSizingDirection direction, unsigned lastLine, unsigned autoRepeatTracksCount)
71     : m_lastLine(lastLine)
72     , m_autoRepeatTotalTracks(autoRepeatTracksCount)
73 {
74     bool isRowAxis = direction == ForColumns;
75     const NamedGridLinesMap& gridLineNames = isRowAxis ? gridContainerStyle.namedGridColumnLines() : gridContainerStyle.namedGridRowLines();
76     const NamedGridLinesMap& autoRepeatGridLineNames = isRowAxis ? gridContainerStyle.autoRepeatNamedGridColumnLines() : gridContainerStyle.autoRepeatNamedGridRowLines();
77
78     auto linesIterator = gridLineNames.find(namedLine);
79     m_namedLinesIndexes = linesIterator == gridLineNames.end() ? nullptr : &linesIterator->value;
80
81     auto autoRepeatLinesIterator = autoRepeatGridLineNames.find(namedLine);
82     m_autoRepeatNamedLinesIndexes = autoRepeatLinesIterator == autoRepeatGridLineNames.end() ? nullptr : &autoRepeatLinesIterator->value;
83
84     m_insertionPoint = isRowAxis ? gridContainerStyle.gridAutoRepeatColumnsInsertionPoint() : gridContainerStyle.gridAutoRepeatRowsInsertionPoint();
85
86     m_autoRepeatTrackListLength = isRowAxis ? gridContainerStyle.gridAutoRepeatColumns().size() : gridContainerStyle.gridAutoRepeatRows().size();
87 }
88
89 bool NamedLineCollection::isValidNamedLineOrArea(const String& namedLine, const RenderStyle& gridContainerStyle, GridPositionSide side)
90 {
91     bool isRowAxis = directionFromSide(side) == ForColumns;
92     auto& gridLineNames = isRowAxis ? gridContainerStyle.namedGridColumnLines() : gridContainerStyle.namedGridRowLines();
93     auto& autoRepeatGridLineNames = isRowAxis ? gridContainerStyle.autoRepeatNamedGridColumnLines() : gridContainerStyle.autoRepeatNamedGridRowLines();
94
95     if (gridLineNames.contains(namedLine) || autoRepeatGridLineNames.contains(namedLine))
96         return true;
97
98     String implicitName = implicitNamedGridLineForSide(namedLine, side);
99     return gridLineNames.contains(implicitName) || autoRepeatGridLineNames.contains(implicitName);
100 }
101
102 bool NamedLineCollection::hasNamedLines() const
103 {
104     return m_namedLinesIndexes || m_autoRepeatNamedLinesIndexes;
105 }
106
107 size_t NamedLineCollection::find(unsigned line) const
108 {
109     if (line > m_lastLine)
110         return notFound;
111
112     if (!m_autoRepeatNamedLinesIndexes || line < m_insertionPoint)
113         return m_namedLinesIndexes ? m_namedLinesIndexes->find(line) : notFound;
114
115     if (line <= (m_insertionPoint + m_autoRepeatTotalTracks)) {
116         size_t localIndex = line - m_insertionPoint;
117
118         size_t indexInFirstRepetition = localIndex % m_autoRepeatTrackListLength;
119         if (indexInFirstRepetition)
120             return m_autoRepeatNamedLinesIndexes->find(indexInFirstRepetition);
121
122         // The line names defined in the last line are also present in the first line of the next
123         // repetition (if any). Same for the line names defined in the first line.
124         if (localIndex == m_autoRepeatTotalTracks)
125             return m_autoRepeatNamedLinesIndexes->find(m_autoRepeatTrackListLength);
126         size_t position = m_autoRepeatNamedLinesIndexes->find(0u);
127         if (position != notFound)
128             return position;
129         return localIndex ? m_autoRepeatNamedLinesIndexes->find(m_autoRepeatTrackListLength) : notFound;
130     }
131
132     return m_namedLinesIndexes ? m_namedLinesIndexes->find(line - (m_autoRepeatTotalTracks - 1)) : notFound;
133 }
134
135 bool NamedLineCollection::contains(unsigned line) const
136 {
137     ASSERT(hasNamedLines());
138     return find(line) != notFound;
139 }
140
141 unsigned NamedLineCollection::firstPosition() const
142 {
143     ASSERT(hasNamedLines());
144     unsigned firstLine = 0;
145
146     if (!m_autoRepeatNamedLinesIndexes) {
147         if (!m_insertionPoint || m_insertionPoint < m_namedLinesIndexes->at(firstLine))
148             return m_namedLinesIndexes->at(firstLine) + (m_autoRepeatTotalTracks ? m_autoRepeatTotalTracks - 1 : 0);
149         return m_namedLinesIndexes->at(firstLine);
150     }
151
152     if (!m_namedLinesIndexes)
153         return m_autoRepeatNamedLinesIndexes->at(firstLine) + m_insertionPoint;
154
155     if (!m_insertionPoint)
156         return std::min(m_namedLinesIndexes->at(firstLine) + m_autoRepeatTotalTracks, m_autoRepeatNamedLinesIndexes->at(firstLine));
157
158     return std::min(m_namedLinesIndexes->at(firstLine), m_autoRepeatNamedLinesIndexes->at(firstLine) + m_insertionPoint);
159 }
160
161 static void adjustGridPositionsFromStyle(const RenderStyle& gridContainerStyle, const RenderBox& gridItem, GridTrackSizingDirection direction, GridPosition& initialPosition, GridPosition& finalPosition)
162 {
163     bool isForColumns = direction == ForColumns;
164     initialPosition = isForColumns ? gridItem.style().gridItemColumnStart() : gridItem.style().gridItemRowStart();
165     finalPosition = isForColumns ? gridItem.style().gridItemColumnEnd() : gridItem.style().gridItemRowEnd();
166
167     // We must handle the placement error handling code here instead of in the StyleAdjuster because we don't want to
168     // overwrite the specified values.
169     if (initialPosition.isSpan() && finalPosition.isSpan())
170         finalPosition.setAutoPosition();
171
172     if (gridItem.isOutOfFlowPositioned()) {
173         // Early detect the case of non existing named grid lines for positioned items.
174         if (initialPosition.isNamedGridArea() && !NamedLineCollection::isValidNamedLineOrArea(initialPosition.namedGridLine(), gridContainerStyle, initialPositionSide(direction)))
175             initialPosition.setAutoPosition();
176
177         if (finalPosition.isNamedGridArea() && !NamedLineCollection::isValidNamedLineOrArea(finalPosition.namedGridLine(), gridContainerStyle, finalPositionSide(direction)))
178             finalPosition.setAutoPosition();
179     }
180
181     // 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.
182     if (initialPosition.isAuto() && finalPosition.isSpan() && !finalPosition.namedGridLine().isNull())
183         finalPosition.setSpanPosition(1, String());
184     if (finalPosition.isAuto() && initialPosition.isSpan() && !initialPosition.namedGridLine().isNull())
185         initialPosition.setSpanPosition(1, String());
186 }
187
188 unsigned GridPositionsResolver::explicitGridColumnCount(const RenderStyle& gridContainerStyle, unsigned autoRepeatTracksCount)
189 {
190     return std::min<unsigned>(std::max(gridContainerStyle.gridColumns().size() + autoRepeatTracksCount, gridContainerStyle.namedGridAreaColumnCount()), kGridMaxTracks);
191 }
192
193 unsigned GridPositionsResolver::explicitGridRowCount(const RenderStyle& gridContainerStyle, unsigned autoRepeatTracksCount)
194 {
195     return std::min<unsigned>(std::max(gridContainerStyle.gridRows().size() + autoRepeatTracksCount, gridContainerStyle.namedGridAreaRowCount()), kGridMaxTracks);
196 }
197
198 static unsigned explicitGridSizeForSide(const RenderStyle& gridContainerStyle, GridPositionSide side, unsigned autoRepeatTracksCount)
199 {
200     return isColumnSide(side) ? GridPositionsResolver::explicitGridColumnCount(gridContainerStyle, autoRepeatTracksCount) : GridPositionsResolver::explicitGridRowCount(gridContainerStyle, autoRepeatTracksCount);
201 }
202
203 static unsigned lookAheadForNamedGridLine(int start, unsigned numberOfLines, unsigned gridLastLine, NamedLineCollection& linesCollection)
204 {
205     ASSERT(numberOfLines);
206
207     // Only implicit lines on the search direction are assumed to have the given name, so we can start to look from first line.
208     // See: https://drafts.csswg.org/css-grid/#grid-placement-span-int
209     unsigned end = std::max(start, 0);
210
211     if (!linesCollection.hasNamedLines())
212         return std::max(end, gridLastLine + 1) + numberOfLines - 1;
213
214     for (; numberOfLines; ++end) {
215         if (end > gridLastLine || linesCollection.contains(end))
216             numberOfLines--;
217     }
218
219     ASSERT(end);
220     return end - 1;
221 }
222
223 static int lookBackForNamedGridLine(int end, unsigned numberOfLines, int gridLastLine, NamedLineCollection& linesCollection)
224 {
225     ASSERT(numberOfLines);
226
227     // Only implicit lines on the search direction are assumed to have the given name, so we can start to look from last line.
228     // See: https://drafts.csswg.org/css-grid/#grid-placement-span-int
229     int start = std::min(end, gridLastLine);
230
231     if (!linesCollection.hasNamedLines())
232         return std::min(start, -1) - numberOfLines + 1;
233
234     for (; numberOfLines; --start) {
235         if (start < 0 || linesCollection.contains(start))
236             numberOfLines--;
237     }
238
239     return start + 1;
240 }
241
242 static int resolveNamedGridLinePositionFromStyle(const RenderStyle& gridContainerStyle, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
243 {
244     ASSERT(!position.namedGridLine().isNull());
245
246     unsigned lastLine = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
247     NamedLineCollection linesCollection(gridContainerStyle, position.namedGridLine(), directionFromSide(side), lastLine, autoRepeatTracksCount);
248
249     if (position.isPositive())
250         return lookAheadForNamedGridLine(0, std::abs(position.integerPosition()), lastLine, linesCollection);
251     return lookBackForNamedGridLine(lastLine, std::abs(position.integerPosition()), lastLine, linesCollection);
252 }
253
254 static GridSpan definiteGridSpanWithNamedLineSpanAgainstOpposite(int oppositeLine, const GridPosition& position, GridPositionSide side, unsigned lastLine, NamedLineCollection& linesCollection)
255 {
256     int start, end;
257     if (side == RowStartSide || side == ColumnStartSide) {
258         start = lookBackForNamedGridLine(oppositeLine - 1, position.spanPosition(), lastLine, linesCollection);
259         end = oppositeLine;
260     } else {
261         start = oppositeLine;
262         end = lookAheadForNamedGridLine(oppositeLine + 1, position.spanPosition(), lastLine, linesCollection);
263     }
264
265     return GridSpan::untranslatedDefiniteGridSpan(start, end);
266 }
267
268 static GridSpan resolveNamedGridLinePositionAgainstOppositePosition(const RenderStyle& gridContainerStyle, int oppositeLine, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
269 {
270     ASSERT(position.isSpan());
271     ASSERT(!position.namedGridLine().isNull());
272     // Negative positions are not allowed per the specification and should have been handled during parsing.
273     ASSERT(position.spanPosition() > 0);
274
275     unsigned lastLine = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
276     NamedLineCollection linesCollection(gridContainerStyle, position.namedGridLine(), directionFromSide(side), lastLine, autoRepeatTracksCount);
277     return definiteGridSpanWithNamedLineSpanAgainstOpposite(oppositeLine, position, side, lastLine, linesCollection);
278 }
279
280 static GridSpan resolveGridPositionAgainstOppositePosition(const RenderStyle& gridContainerStyle, int oppositeLine, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
281 {
282     if (position.isAuto()) {
283         if (isStartSide(side))
284             return GridSpan::untranslatedDefiniteGridSpan(oppositeLine - 1, oppositeLine);
285         return GridSpan::untranslatedDefiniteGridSpan(oppositeLine, oppositeLine + 1);
286     }
287
288     ASSERT(position.isSpan());
289     ASSERT(position.spanPosition() > 0);
290
291     if (!position.namedGridLine().isNull()) {
292         // span 2 'c' -> we need to find the appropriate grid line before / after our opposite position.
293         return resolveNamedGridLinePositionAgainstOppositePosition(gridContainerStyle, oppositeLine, position, side, autoRepeatTracksCount);
294     }
295
296     // 'span 1' is contained inside a single grid track regardless of the direction.
297     // That's why the CSS span value is one more than the offset we apply.
298     unsigned positionOffset = position.spanPosition();
299     if (isStartSide(side))
300         return GridSpan::untranslatedDefiniteGridSpan(oppositeLine - positionOffset, oppositeLine);
301
302     return GridSpan::untranslatedDefiniteGridSpan(oppositeLine, oppositeLine + positionOffset);
303 }
304
305 unsigned GridPositionsResolver::spanSizeForAutoPlacedItem(const RenderStyle& gridContainerStyle, const RenderBox& gridItem, GridTrackSizingDirection direction)
306 {
307     GridPosition initialPosition, finalPosition;
308     adjustGridPositionsFromStyle(gridContainerStyle, gridItem, direction, initialPosition, finalPosition);
309
310     // This method will only be used when both positions need to be resolved against the opposite one.
311     ASSERT(initialPosition.shouldBeResolvedAgainstOppositePosition() && finalPosition.shouldBeResolvedAgainstOppositePosition());
312
313     if (initialPosition.isAuto() && finalPosition.isAuto())
314         return 1;
315
316     GridPosition position = initialPosition.isSpan() ? initialPosition : finalPosition;
317     ASSERT(position.isSpan());
318
319     ASSERT(position.spanPosition());
320     return position.spanPosition();
321 }
322
323 static int resolveGridPositionFromStyle(const RenderStyle& gridContainerStyle, const GridPosition& position, GridPositionSide side, unsigned autoRepeatTracksCount)
324 {
325     switch (position.type()) {
326     case ExplicitPosition: {
327         ASSERT(position.integerPosition());
328
329         if (!position.namedGridLine().isNull())
330             return resolveNamedGridLinePositionFromStyle(gridContainerStyle, position, side, autoRepeatTracksCount);
331
332         // Handle <integer> explicit position.
333         if (position.isPositive())
334             return position.integerPosition() - 1;
335
336         unsigned resolvedPosition = std::abs(position.integerPosition()) - 1;
337         const unsigned endOfTrack = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
338
339         return endOfTrack - resolvedPosition;
340     }
341     case NamedGridAreaPosition:
342     {
343         // First attempt to match the grid area's edge to a named grid area: if there is a named line with the name
344         // ''<custom-ident>-start (for grid-*-start) / <custom-ident>-end'' (for grid-*-end), contributes the first such
345         // line to the grid item's placement.
346         String namedGridLine = position.namedGridLine();
347         ASSERT(!position.namedGridLine().isNull());
348
349         unsigned lastLine = explicitGridSizeForSide(gridContainerStyle, side, autoRepeatTracksCount);
350         NamedLineCollection implicitLines(gridContainerStyle, implicitNamedGridLineForSide(namedGridLine, side), directionFromSide(side), lastLine, autoRepeatTracksCount);
351         if (implicitLines.hasNamedLines())
352             return implicitLines.firstPosition();
353
354         // Otherwise, if there is a named line with the specified name, contributes the first such line to the grid
355         // item's placement.
356         NamedLineCollection explicitLines(gridContainerStyle, namedGridLine, directionFromSide(side), lastLine, autoRepeatTracksCount);
357         if (explicitLines.hasNamedLines())
358             return explicitLines.firstPosition();
359
360         ASSERT(!NamedLineCollection::isValidNamedLineOrArea(namedGridLine, gridContainerStyle, side));
361         // If none of the above works specs mandate to assume that all the lines in the implicit grid have this name.
362         return lastLine + 1;
363     }
364     case AutoPosition:
365     case SpanPosition:
366         // 'auto' and span depend on the opposite position for resolution (e.g. grid-row: auto / 1 or grid-column: span 3 / "myHeader").
367         ASSERT_NOT_REACHED();
368         return 0;
369     }
370     ASSERT_NOT_REACHED();
371     return 0;
372 }
373
374 GridSpan GridPositionsResolver::resolveGridPositionsFromStyle(const RenderStyle& gridContainerStyle, const RenderBox& gridItem, GridTrackSizingDirection direction, unsigned autoRepeatTracksCount)
375 {
376     GridPosition initialPosition, finalPosition;
377     adjustGridPositionsFromStyle(gridContainerStyle, gridItem, direction, initialPosition, finalPosition);
378
379     GridPositionSide initialSide = initialPositionSide(direction);
380     GridPositionSide finalSide = finalPositionSide(direction);
381
382     // We can't get our grid positions without running the auto placement algorithm.
383     if (initialPosition.shouldBeResolvedAgainstOppositePosition() && finalPosition.shouldBeResolvedAgainstOppositePosition())
384         return GridSpan::indefiniteGridSpan();
385
386     if (initialPosition.shouldBeResolvedAgainstOppositePosition()) {
387         // Infer the position from the final position ('auto / 1' or 'span 2 / 3' case).
388         auto endLine = resolveGridPositionFromStyle(gridContainerStyle, finalPosition, finalSide, autoRepeatTracksCount);
389         return resolveGridPositionAgainstOppositePosition(gridContainerStyle, endLine, initialPosition, initialSide, autoRepeatTracksCount);
390     }
391
392     if (finalPosition.shouldBeResolvedAgainstOppositePosition()) {
393         // Infer our position from the initial position ('1 / auto' or '3 / span 2' case).
394         auto startLine = resolveGridPositionFromStyle(gridContainerStyle, initialPosition, initialSide, autoRepeatTracksCount);
395         return resolveGridPositionAgainstOppositePosition(gridContainerStyle, startLine, finalPosition, finalSide, autoRepeatTracksCount);
396     }
397
398     int startLine = resolveGridPositionFromStyle(gridContainerStyle, initialPosition, initialSide, autoRepeatTracksCount);
399     int endLine = resolveGridPositionFromStyle(gridContainerStyle, finalPosition, finalSide, autoRepeatTracksCount);
400
401     if (startLine > endLine)
402         std::swap(startLine, endLine);
403     else if (startLine == endLine)
404         endLine = startLine + 1;
405
406     return GridSpan::untranslatedDefiniteGridSpan(startLine, std::max(startLine, endLine));
407 }
408
409 } // namespace WebCore