1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "third_party/blink/renderer/core/layout/grid.h"
6
7 #include <algorithm>
8 #include <memory>
9 #include <utility>
10
11 #include "base/memory/ptr_util.h"
12 #include "third_party/blink/renderer/core/layout/layout_grid.h"
13
14 namespace blink {
15
16 namespace {
17
OrthogonalDirection(GridTrackSizingDirection direction)18 static inline GridTrackSizingDirection OrthogonalDirection(
19 GridTrackSizingDirection direction) {
20 return direction == kForRows ? kForColumns : kForRows;
21 }
22
23 } // namespace
24
Create(const LayoutGrid * layout_grid)25 std::unique_ptr<Grid> Grid::Create(const LayoutGrid* layout_grid) {
26 return base::WrapUnique(new ListGrid(layout_grid));
27 }
28
Grid(const LayoutGrid * grid)29 Grid::Grid(const LayoutGrid* grid) : order_iterator_(grid) {}
30
SetSmallestTracksStart(int row_start,int column_start)31 void Grid::SetSmallestTracksStart(int row_start, int column_start) {
32 smallest_row_start_ = row_start;
33 smallest_column_start_ = column_start;
34 }
35
SmallestTrackStart(GridTrackSizingDirection direction) const36 int Grid::SmallestTrackStart(GridTrackSizingDirection direction) const {
37 return direction == kForRows ? smallest_row_start_ : smallest_column_start_;
38 }
39
GridItemArea(const LayoutBox & item) const40 GridArea Grid::GridItemArea(const LayoutBox& item) const {
41 DCHECK(grid_item_area_.Contains(&item));
42 return grid_item_area_.at(&item);
43 }
44
SetGridItemArea(const LayoutBox & item,GridArea area)45 void Grid::SetGridItemArea(const LayoutBox& item, GridArea area) {
46 grid_item_area_.Set(&item, area);
47 }
48
GridItemPaintOrder(const LayoutBox & item) const49 size_t Grid::GridItemPaintOrder(const LayoutBox& item) const {
50 return grid_items_indexes_map_.at(&item);
51 }
52
SetGridItemPaintOrder(const LayoutBox & item,size_t order)53 void Grid::SetGridItemPaintOrder(const LayoutBox& item, size_t order) {
54 grid_items_indexes_map_.Set(&item, order);
55 }
56
57 #if DCHECK_IS_ON()
HasAnyGridItemPaintOrder() const58 bool Grid::HasAnyGridItemPaintOrder() const {
59 return !grid_items_indexes_map_.IsEmpty();
60 }
61 #endif
62
SetAutoRepeatTracks(size_t auto_repeat_rows,size_t auto_repeat_columns)63 void Grid::SetAutoRepeatTracks(size_t auto_repeat_rows,
64 size_t auto_repeat_columns) {
65 DCHECK_GE(static_cast<unsigned>(kGridMaxTracks),
66 NumTracks(kForRows) + auto_repeat_rows);
67 DCHECK_GE(static_cast<unsigned>(kGridMaxTracks),
68 NumTracks(kForColumns) + auto_repeat_columns);
69 auto_repeat_rows_ = auto_repeat_rows;
70 auto_repeat_columns_ = auto_repeat_columns;
71 }
72
AutoRepeatTracks(GridTrackSizingDirection direction) const73 size_t Grid::AutoRepeatTracks(GridTrackSizingDirection direction) const {
74 return direction == kForRows ? auto_repeat_rows_ : auto_repeat_columns_;
75 }
76
SetAutoRepeatEmptyColumns(std::unique_ptr<OrderedTrackIndexSet> auto_repeat_empty_columns)77 void Grid::SetAutoRepeatEmptyColumns(
78 std::unique_ptr<OrderedTrackIndexSet> auto_repeat_empty_columns) {
79 auto_repeat_empty_columns_ = std::move(auto_repeat_empty_columns);
80 }
81
SetAutoRepeatEmptyRows(std::unique_ptr<OrderedTrackIndexSet> auto_repeat_empty_rows)82 void Grid::SetAutoRepeatEmptyRows(
83 std::unique_ptr<OrderedTrackIndexSet> auto_repeat_empty_rows) {
84 auto_repeat_empty_rows_ = std::move(auto_repeat_empty_rows);
85 }
86
HasAutoRepeatEmptyTracks(GridTrackSizingDirection direction) const87 bool Grid::HasAutoRepeatEmptyTracks(GridTrackSizingDirection direction) const {
88 return direction == kForColumns ? !!auto_repeat_empty_columns_
89 : !!auto_repeat_empty_rows_;
90 }
91
IsEmptyAutoRepeatTrack(GridTrackSizingDirection direction,size_t line) const92 bool Grid::IsEmptyAutoRepeatTrack(GridTrackSizingDirection direction,
93 size_t line) const {
94 DCHECK(HasAutoRepeatEmptyTracks(direction));
95 return AutoRepeatEmptyTracks(direction)->Contains(line);
96 }
97
AutoRepeatEmptyTracks(GridTrackSizingDirection direction) const98 OrderedTrackIndexSet* Grid::AutoRepeatEmptyTracks(
99 GridTrackSizingDirection direction) const {
100 DCHECK(HasAutoRepeatEmptyTracks(direction));
101 return direction == kForColumns ? auto_repeat_empty_columns_.get()
102 : auto_repeat_empty_rows_.get();
103 }
104
GridItemSpan(const LayoutBox & grid_item,GridTrackSizingDirection direction) const105 GridSpan Grid::GridItemSpan(const LayoutBox& grid_item,
106 GridTrackSizingDirection direction) const {
107 GridArea area = GridItemArea(grid_item);
108 return direction == kForColumns ? area.columns : area.rows;
109 }
110
SetNeedsItemsPlacement(bool needs_items_placement)111 void Grid::SetNeedsItemsPlacement(bool needs_items_placement) {
112 needs_items_placement_ = needs_items_placement;
113
114 if (!needs_items_placement) {
115 ConsolidateGridDataStructure();
116 return;
117 }
118
119 ClearGridDataStructure();
120 grid_item_area_.clear();
121 grid_items_indexes_map_.clear();
122 smallest_row_start_ = 0;
123 smallest_column_start_ = 0;
124 auto_repeat_columns_ = 0;
125 auto_repeat_rows_ = 0;
126 auto_repeat_empty_columns_ = nullptr;
127 auto_repeat_empty_rows_ = nullptr;
128 }
129
GridIterator(GridTrackSizingDirection direction,size_t fixed_track_index,size_t varying_track_index)130 Grid::GridIterator::GridIterator(GridTrackSizingDirection direction,
131 size_t fixed_track_index,
132 size_t varying_track_index)
133 : direction_(direction),
134 row_index_((direction == kForColumns) ? varying_track_index
135 : fixed_track_index),
136 column_index_((direction == kForColumns) ? fixed_track_index
137 : varying_track_index),
138 child_index_(0) {}
139
Find(size_t index) const140 ListGrid::GridCell* ListGrid::GridTrack::Find(size_t index) const {
141 auto orthogonal_axis = OrthogonalDirection(direction_);
142 for (auto* cell = cells_.Head(); cell;
143 cell = cell->NextInDirection(direction_)) {
144 size_t cell_index = cell->Index(orthogonal_axis);
145 if (cell_index == index)
146 return cell;
147 if (cell_index > index)
148 return nullptr;
149 }
150 return nullptr;
151 }
152
ComparePositions(size_t first,size_t second)153 static int ComparePositions(size_t first, size_t second) {
154 return first < second ? -1 : (first != second);
155 }
156
Insert(GridCell * cell)157 DoublyLinkedList<ListGrid::GridCell>::AddResult ListGrid::GridTrack::Insert(
158 GridCell* cell) {
159 cell->SetTraversalMode(direction_);
160
161 return cells_.Insert(
162 cell, [this](ListGrid::GridCell* first, ListGrid::GridCell* second) {
163 // This is ugly but we need to do this in order the
164 // DoublyLinkedList::Insert() algorithm to work at that code
165 // only uses next_ and prev_.
166 first->SetTraversalMode(direction_);
167 second->SetTraversalMode(direction_);
168 auto ortho_direction = OrthogonalDirection(direction_);
169 return ComparePositions(first->Index(ortho_direction),
170 second->Index(ortho_direction));
171 });
172 }
173
Insert(LayoutBox & item,const GridSpan & span)174 DoublyLinkedList<ListGrid::GridCell>::AddResult ListGrid::GridTrack::Insert(
175 LayoutBox& item,
176 const GridSpan& span) {
177 auto compare_cells = [this](ListGrid::GridCell* first,
178 ListGrid::GridCell* second) {
179 first->SetTraversalMode(direction_);
180 second->SetTraversalMode(direction_);
181 auto ortho_direction = OrthogonalDirection(direction_);
182 return ComparePositions(first->Index(ortho_direction),
183 second->Index(ortho_direction));
184 };
185
186 size_t col_index = direction_ == kForColumns ? Index() : span.StartLine();
187 size_t row_index = direction_ == kForColumns ? span.StartLine() : Index();
188
189 auto result = cells_.Insert(
190 base::WrapUnique(new GridCell(row_index, col_index)), compare_cells);
191 auto* cell = result.node;
192 for (auto index : span) {
193 cell->AppendItem(item);
194
195 if (index == span.EndLine() - 1)
196 break;
197
198 cell->SetTraversalMode(direction_);
199 auto ortho_direction = OrthogonalDirection(direction_);
200 if (!cell->Next() ||
201 (cell->Next()->Index(ortho_direction) != (index + 1))) {
202 size_t next_col_index = direction_ == kForColumns ? Index() : index + 1;
203 size_t next_row_index = direction_ == kForColumns ? index + 1 : Index();
204 auto next_cell =
205 base::WrapUnique(new GridCell(next_row_index, next_col_index));
206 auto result = InsertAfter(next_cell.get(), cell);
207 if (result.is_new_entry)
208 next_cell.release();
209 }
210 cell = cell->Next();
211 }
212 return result;
213 }
214
215 DoublyLinkedList<ListGrid::GridCell>::AddResult
InsertAfter(GridCell * cell,GridCell * insertion_point)216 ListGrid::GridTrack::InsertAfter(GridCell* cell, GridCell* insertion_point) {
217 insertion_point->SetTraversalMode(direction_);
218 cell->SetTraversalMode(direction_);
219 if (auto* next = insertion_point->Next()) {
220 if (next == cell)
221 return {cell, false};
222 // We need to set the traversal mode for the next cell as we're
223 // going to insert in between and we need to properly update next_
224 // and prev_ pointers.
225 next->SetTraversalMode(direction_);
226 }
227 return cells_.InsertAfter(cell, insertion_point);
228 }
229
~GridTrack()230 ListGrid::GridTrack::~GridTrack() {
231 // We destroy cells just when disposing columns as we don't want to
232 // double free them.
233 // TODO(svillar): we need to eventually get rid of this different
234 // destructors depending on the axis.
235 if (direction_ == kForRows) {
236 cells_.Clear();
237 return;
238 }
239
240 while (!cells_.IsEmpty()) {
241 cells_.Head()->SetTraversalMode(kForColumns);
242 if (cells_.Head()->Next())
243 cells_.Head()->Next()->SetTraversalMode(kForColumns);
244 delete cells_.RemoveHead();
245 }
246 }
247
Cell(size_t row_index,size_t column_index) const248 const GridItemList& ListGrid::Cell(size_t row_index,
249 size_t column_index) const {
250 DEFINE_STATIC_LOCAL(const GridItemList, empty_vector, ());
251 for (auto* row = rows_.Head(); row; row = row->Next()) {
252 if (row->Index() == row_index) {
253 auto* cell = row->Find(column_index);
254 return cell ? cell->Items() : empty_vector;
255 }
256 if (row->Index() > row_index)
257 return empty_vector;
258 }
259 return empty_vector;
260 }
261
InsertTracks(DoublyLinkedList<GridTrack> & tracks,const GridSpan & span,GridTrackSizingDirection direction)262 ListGrid::GridTrack* ListGrid::InsertTracks(
263 DoublyLinkedList<GridTrack>& tracks,
264 const GridSpan& span,
265 GridTrackSizingDirection direction) {
266 auto compare_tracks = [](ListGrid::GridTrack* first,
267 ListGrid::GridTrack* second) {
268 return ComparePositions(first->Index(), second->Index());
269 };
270
271 size_t start_line = span.StartLine();
272 size_t end_line = span.EndLine();
273
274 DoublyLinkedList<ListGrid::GridTrack>::AddResult result = tracks.Insert(
275 base::WrapUnique(new GridTrack(start_line, direction)), compare_tracks);
276 auto* track = result.node;
277 DCHECK(track);
278
279 auto* iter = track;
280 for (size_t track_index = start_line + 1; iter && track_index < end_line;
281 ++track_index) {
282 if (!iter->Next() || track_index < iter->Next()->Index()) {
283 tracks.InsertAfter(
284 base::WrapUnique(new GridTrack(track_index, direction)), iter);
285 }
286 iter = iter->Next();
287 }
288
289 return track;
290 }
291
Insert(LayoutBox & item,const GridArea & area)292 void ListGrid::Insert(LayoutBox& item, const GridArea& area) {
293 DCHECK(area.rows.IsTranslatedDefinite() &&
294 area.columns.IsTranslatedDefinite());
295 EnsureGridSize(area.rows.EndLine(), area.columns.EndLine());
296
297 GridTrack* first_row = InsertTracks(rows_, area.rows, kForRows);
298 DCHECK(first_row);
299 GridTrack* first_column = InsertTracks(columns_, area.columns, kForColumns);
300 DCHECK(first_column);
301
302 GridCell* above_cell = nullptr;
303 GridTrack* row = first_row;
304 for (auto row_index : area.rows) {
305 auto result = row->Insert(item, area.columns);
306 // We need to call Insert() for the first row of cells to get the
307 // column pointers right. For the following rows we can use
308 // InsertAfter() as it's cheaper (it doesn't traverse the
309 // list). We need to keep track of the cell in the row above
310 // (above_cell) in order to properly update the column next_ &
311 // prev_ pointers.
312 auto* cell_iter = result.node;
313 auto* col_iter = first_column;
314 while (col_iter && col_iter->Index() < area.columns.EndLine()) {
315 if (row_index == area.rows.StartLine()) {
316 col_iter->Insert(cell_iter);
317 } else {
318 col_iter->InsertAfter(cell_iter, above_cell);
319 above_cell = above_cell->NextInDirection(kForRows);
320 }
321 cell_iter = cell_iter->NextInDirection(kForRows);
322 col_iter = col_iter->Next();
323 }
324 above_cell = result.node;
325 row = row->Next();
326 }
327
328 SetGridItemArea(item, area);
329 }
330
EnsureGridSize(size_t maximum_row_size,size_t maximum_column_size)331 void ListGrid::EnsureGridSize(size_t maximum_row_size,
332 size_t maximum_column_size) {
333 num_rows_ = std::max(num_rows_, maximum_row_size);
334 num_columns_ = std::max(num_columns_, maximum_column_size);
335 }
336
ClearGridDataStructure()337 void ListGrid::ClearGridDataStructure() {
338 num_rows_ = num_columns_ = 0;
339 while (!rows_.IsEmpty())
340 delete rows_.RemoveHead();
341 DCHECK(rows_.IsEmpty());
342 while (!columns_.IsEmpty())
343 delete columns_.RemoveHead();
344 DCHECK(columns_.IsEmpty());
345 }
346
~ListGrid()347 ListGrid::~ListGrid() {
348 ClearGridDataStructure();
349 }
350
SetTraversalMode(GridTrackSizingDirection direction)351 void ListGrid::GridCell::SetTraversalMode(GridTrackSizingDirection direction) {
352 if (direction == direction_)
353 return;
354 direction_ = direction;
355 std::swap(next_, next_ortho_);
356 std::swap(prev_, prev_ortho_);
357 }
358
NextInDirection(GridTrackSizingDirection direction) const359 ListGrid::GridCell* ListGrid::GridCell::NextInDirection(
360 GridTrackSizingDirection direction) const {
361 return direction_ == direction ? next_ : next_ortho_;
362 }
363
CreateIterator(GridTrackSizingDirection direction,size_t fixed_track_index,size_t varying_track_index) const364 std::unique_ptr<Grid::GridIterator> ListGrid::CreateIterator(
365 GridTrackSizingDirection direction,
366 size_t fixed_track_index,
367 size_t varying_track_index) const {
368 return base::WrapUnique(new ListGridIterator(
369 *this, direction, fixed_track_index, varying_track_index));
370 }
371
ListGridIterator(const ListGrid & grid,GridTrackSizingDirection direction,size_t fixed_track_index,size_t varying_track_index)372 ListGridIterator::ListGridIterator(const ListGrid& grid,
373 GridTrackSizingDirection direction,
374 size_t fixed_track_index,
375 size_t varying_track_index)
376 : GridIterator(direction, fixed_track_index, varying_track_index),
377 grid_(grid) {}
378
NextGridItem()379 LayoutBox* ListGridIterator::NextGridItem() {
380 DCHECK(grid_.NumTracks(kForRows));
381 DCHECK(grid_.NumTracks(kForColumns));
382
383 bool is_row_axis = direction_ == kForColumns;
384 if (!cell_node_) {
385 auto* track = is_row_axis ? grid_.columns_.Head() : grid_.rows_.Head();
386 DCHECK(track);
387 const size_t fixed_index = is_row_axis ? column_index_ : row_index_;
388 while (track && track->Index() != fixed_index)
389 track = track->Next();
390
391 if (!track)
392 return nullptr;
393
394 child_index_ = 0;
395 cell_node_ = track->Cells().Head();
396 DCHECK(cell_node_);
397 DCHECK(!cell_node_->Items().IsEmpty());
398 return cell_node_->Items()[child_index_++];
399 }
400
401 if (child_index_ < cell_node_->Items().size())
402 return cell_node_->Items()[child_index_++];
403
404 child_index_ = 0;
405 cell_node_ = cell_node_->NextInDirection(direction_);
406 if (!cell_node_)
407 return nullptr;
408
409 DCHECK(!cell_node_->Items().IsEmpty());
410 return cell_node_->Items()[child_index_++];
411 }
412
NextEmptyGridArea(size_t fixed_track_span,size_t varying_track_span)413 std::unique_ptr<GridArea> ListGridIterator::NextEmptyGridArea(
414 size_t fixed_track_span,
415 size_t varying_track_span) {
416 auto FindCellOrClosest = [](ListGrid::GridCell* cell_node,
417 GridTrackSizingDirection direction,
418 size_t index) {
419 auto ortho_direction = OrthogonalDirection(direction);
420 while (cell_node && cell_node->Index(direction) < index)
421 cell_node = cell_node->NextInDirection(ortho_direction);
422
423 return cell_node;
424 };
425
426 auto CreateUniqueGridArea = [this, fixed_track_span, varying_track_span]() {
427 bool is_row_axis = direction_ == kForColumns;
428 size_t row_span = is_row_axis ? varying_track_span : fixed_track_span;
429 size_t column_span = is_row_axis ? fixed_track_span : varying_track_span;
430 return std::make_unique<GridArea>(
431 GridSpan::TranslatedDefiniteGridSpan(row_index_, row_index_ + row_span),
432 GridSpan::TranslatedDefiniteGridSpan(column_index_,
433 column_index_ + column_span));
434 };
435
436 auto CellIsInsideSpan = [](ListGrid::GridCell* cell_node,
437 GridTrackSizingDirection direction, size_t start,
438 size_t end) {
439 DCHECK(cell_node);
440 size_t cell_index = cell_node->Index(direction);
441 return cell_index >= start && cell_index <= end;
442 };
443
444 auto orthogonal_axis = OrthogonalDirection(direction_);
445 auto& tracks = grid_.Tracks(orthogonal_axis);
446
447 bool is_row_axis = direction_ == kForColumns;
448 auto& varying_index = is_row_axis ? row_index_ : column_index_;
449 const size_t fixed_index = is_row_axis ? column_index_ : row_index_;
450 const size_t end_fixed_span = fixed_index + fixed_track_span - 1;
451 auto* track_node = tracks.Head();
452 while (track_node && track_node->Index() < varying_index)
453 track_node = track_node->Next();
454
455 for (; track_node; track_node = track_node->Next()) {
456 if (!track_node)
457 return CreateUniqueGridArea();
458
459 if (track_node->Index() - varying_index >= varying_track_span)
460 return CreateUniqueGridArea();
461
462 auto* cell_node =
463 FindCellOrClosest(track_node->Cells().Head(), direction_, fixed_index);
464 if (cell_node &&
465 CellIsInsideSpan(cell_node, direction_, fixed_index, end_fixed_span))
466 varying_index = track_node->Index() + 1;
467 else if (track_node->Index() - varying_index >= varying_track_span)
468 return CreateUniqueGridArea();
469 }
470
471 return CreateUniqueGridArea();
472 }
473
474 } // namespace blink
475