blob: 4b5d90c0309f2890633580e37b93aa1918e7390e [file] [log] [blame]
// Copyright 2017 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "base/macros.h"
#include "third_party/blink/renderer/core/core_export.h"
#include "third_party/blink/renderer/core/layout/order_iterator.h"
#include "third_party/blink/renderer/core/style/grid_area.h"
#include "third_party/blink/renderer/core/style/grid_positions_resolver.h"
#include "third_party/blink/renderer/platform/wtf/assertions.h"
#include "third_party/blink/renderer/platform/wtf/doubly_linked_list.h"
#include "third_party/blink/renderer/platform/wtf/linked_hash_set.h"
#include "third_party/blink/renderer/platform/wtf/vector.h"
namespace blink {
// TODO(svillar): Perhaps we should use references here.
typedef Vector<LayoutBox*, 1> GridItemList;
typedef LinkedHashSet<size_t> OrderedTrackIndexSet;
class LayoutGrid;
class GridIterator;
// The Grid class represent a generic storage for grid items. This
// class is used by the LayoutGrid object to place the grid items on a
// grid like structure, so that they could be accessed by rows/columns
// instead of just traversing the DOM or Layout trees. The other user
// of this class is the GridTrackSizingAlgorithm class.
class CORE_EXPORT Grid {
static std::unique_ptr<Grid> Create(const LayoutGrid*);
virtual size_t NumTracks(GridTrackSizingDirection) const = 0;
virtual void EnsureGridSize(size_t maximum_row_size,
size_t maximum_column_size) = 0;
virtual void Insert(LayoutBox&, const GridArea&) = 0;
virtual const GridItemList& Cell(size_t row, size_t column) const = 0;
virtual ~Grid(){};
// Note that out of flow children are not grid items.
bool HasGridItems() const { return !grid_item_area_.IsEmpty(); }
GridArea GridItemArea(const LayoutBox&) const;
void SetGridItemArea(const LayoutBox&, GridArea);
GridSpan GridItemSpan(const LayoutBox&, GridTrackSizingDirection) const;
size_t GridItemPaintOrder(const LayoutBox&) const;
void SetGridItemPaintOrder(const LayoutBox&, size_t order);
int SmallestTrackStart(GridTrackSizingDirection) const;
void SetSmallestTracksStart(int row_start, int column_start);
size_t AutoRepeatTracks(GridTrackSizingDirection) const;
void SetAutoRepeatTracks(size_t auto_repeat_rows, size_t auto_repeat_columns);
typedef LinkedHashSet<size_t> OrderedTrackIndexSet;
void SetAutoRepeatEmptyColumns(std::unique_ptr<OrderedTrackIndexSet>);
void SetAutoRepeatEmptyRows(std::unique_ptr<OrderedTrackIndexSet>);
bool HasAutoRepeatEmptyTracks(GridTrackSizingDirection) const;
bool IsEmptyAutoRepeatTrack(GridTrackSizingDirection, size_t) const;
OrderedTrackIndexSet* AutoRepeatEmptyTracks(GridTrackSizingDirection) const;
OrderIterator& GetOrderIterator() { return order_iterator_; }
void SetNeedsItemsPlacement(bool);
bool NeedsItemsPlacement() const { return needs_items_placement_; };
bool HasAnyGridItemPaintOrder() const;
class GridIterator {
virtual LayoutBox* NextGridItem() = 0;
virtual std::unique_ptr<GridArea> NextEmptyGridArea(
size_t fixed_track_span,
size_t varying_track_span) = 0;
virtual ~GridIterator() = default;
// |direction| is the direction that is fixed to |fixed_track_index| so e.g
// GridIterator(grid_, kForColumns, 1) will walk over the rows of the 2nd
// column.
size_t fixed_track_index,
size_t varying_track_index);
GridTrackSizingDirection direction_;
size_t row_index_;
size_t column_index_;
size_t child_index_;
virtual std::unique_ptr<GridIterator> CreateIterator(
size_t fixed_track_index,
size_t varying_track_index = 0) const = 0;
Grid(const LayoutGrid*);
virtual void ClearGridDataStructure() = 0;
virtual void ConsolidateGridDataStructure() = 0;
friend class GridIterator;
OrderIterator order_iterator_;
int smallest_column_start_{0};
int smallest_row_start_{0};
size_t auto_repeat_columns_{0};
size_t auto_repeat_rows_{0};
bool needs_items_placement_{true};
HashMap<const LayoutBox*, GridArea> grid_item_area_;
HashMap<const LayoutBox*, size_t> grid_items_indexes_map_;
std::unique_ptr<OrderedTrackIndexSet> auto_repeat_empty_columns_{nullptr};
std::unique_ptr<OrderedTrackIndexSet> auto_repeat_empty_rows_{nullptr};
// This is a Grid specialization which uses doubly linked lists (DLL)
// for the grid data structure. Each axis will be represented by a DLL
// of GridTrack's. The grid will only have list nodes for those tracks
// which actually contain at least one item. Those DLL are ordered by
// the track index.
class CORE_EXPORT ListGrid final : public Grid {
explicit ListGrid(const LayoutGrid* grid) : Grid(grid) {}
size_t NumTracks(GridTrackSizingDirection direction) const override {
return direction == kForRows ? num_rows_ : num_columns_;
const GridItemList& Cell(size_t row, size_t column) const override;
void Insert(LayoutBox&, const GridArea&) override;
void EnsureGridSize(size_t maximum_row_size,
size_t maximum_column_size) override;
~ListGrid() final;
// This is the class representing a cell in the grid. GridCell's are
// only created for those cells which do have items inside. Each
// GridCell will be part of two different DLL, one representing the
// column and another one representing the row.
class GridCell final : public DoublyLinkedListNode<GridCell> {
friend class WTF::DoublyLinkedListNode<GridCell>;
GridCell(size_t row, size_t column) : row_(row), column_(column) {}
size_t Index(GridTrackSizingDirection direction) const {
return direction == kForRows ? row_ : column_;
void AppendItem(LayoutBox& item) { items_.push_back(&item); }
const GridItemList& Items() const { return items_; }
// DoublyLinkedListNode classes must provide a next_ and prev_
// pointers to the DoublyLinkedList class so that it could perform
// the list operations. In the case of GridCells we need them to
// be shared by two lists the row and the column. This means that
// we need to maintain 4 separate pointers. In order to accomodate
// this in the DoublyLinkedList model, we must set the proper
// traversal mode (navigation by rows or columns) before any
// operation with a GridCell involving the use of the next_/prev_
// pointers.
// TODO(svillar): we could probably use DoublyLinkedLists just for
// one axis, this will remove the need for this and some other
// clumsy things like different behaviours in ~GridTrack() for
// each axis.
void SetTraversalMode(GridTrackSizingDirection);
GridTrackSizingDirection TraversalMode() const { return direction_; }
// Use this ONLY for traversals. If your code performs any
// modification in the list of cells while traversing then this
// might not work as expected and you should use
// SetTraversalMode()+Next() instead.
GridCell* NextInDirection(GridTrackSizingDirection) const;
GridCell* prev_{nullptr};
GridCell* next_{nullptr};
GridCell* prev_ortho_{nullptr};
GridCell* next_ortho_{nullptr};
GridTrackSizingDirection direction_{kForColumns};
GridItemList items_;
size_t row_;
size_t column_;
// This class represents a track (column or row) of the grid. Each
// GridTrack will be part of a DLL stored in the ListGrid class,
// either rows_ or columns_. GridTrack's are never empty, i.e., they
// are only created whenever an item spans through them. Each
// GridTrack keeps a sorted list of the cells containing grid items
// in that particular track. The list of cells is ordered by the
// index of the cell in the orthogonal direction, i.e., the list of
// cells in a GridTrack representing a column will be sorted by
// their row index.
class CORE_EXPORT GridTrack final : public DoublyLinkedListNode<GridTrack> {
friend class WTF::DoublyLinkedListNode<GridTrack>;
GridTrack(size_t index, GridTrackSizingDirection direction)
: index_(index), direction_(direction) {}
size_t Index() const { return index_; }
DoublyLinkedList<GridCell>::AddResult Insert(GridCell*);
DoublyLinkedList<GridCell>::AddResult InsertAfter(
GridCell* cell,
GridCell* insertion_point);
DoublyLinkedList<GridCell>::AddResult Insert(LayoutBox&, const GridSpan&);
GridCell* Find(size_t cell_index) const;
const DoublyLinkedList<GridCell>& Cells() const { return cells_; }
DoublyLinkedList<GridCell> cells_;
size_t index_;
GridTrackSizingDirection direction_;
GridTrack* prev_;
GridTrack* next_;
friend class ListGridIterator;
// Returns a pointer to the first track.
GridTrack* InsertTracks(DoublyLinkedList<GridTrack>&,
const GridSpan&,
void ClearGridDataStructure() override;
void ConsolidateGridDataStructure() override {}
const DoublyLinkedList<GridTrack>& Tracks(
GridTrackSizingDirection direction) const {
return direction == kForRows ? rows_ : columns_;
std::unique_ptr<GridIterator> CreateIterator(
size_t fixed_track_index,
size_t varying_track_index = 0) const override;
size_t num_rows_{0};
size_t num_columns_{0};
DoublyLinkedList<GridTrack> columns_;
DoublyLinkedList<GridTrack> rows_;
class ListGridIterator final : public Grid::GridIterator {
ListGridIterator(const ListGrid& grid,
size_t fixed_track_index,
size_t varying_track_index = 0);
LayoutBox* NextGridItem() override;
std::unique_ptr<GridArea> NextEmptyGridArea(
size_t fixed_track_span,
size_t varying_track_span) override;
const ListGrid& grid_;
ListGrid::GridCell* cell_node_{nullptr};
} // namespace blink