1 // Copyright 2020 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 #ifndef THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_NG_GRID_NG_GRID_LAYOUT_ALGORITHM_H_
6 #define THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_NG_GRID_NG_GRID_LAYOUT_ALGORITHM_H_
7 
8 #include "third_party/blink/renderer/core/layout/ng/grid/ng_grid_track_collection.h"
9 #include "third_party/blink/renderer/core/layout/ng/ng_block_break_token.h"
10 #include "third_party/blink/renderer/core/layout/ng/ng_box_fragment_builder.h"
11 #include "third_party/blink/renderer/core/layout/ng/ng_constraint_space.h"
12 #include "third_party/blink/renderer/core/layout/ng/ng_layout_algorithm.h"
13 #include "third_party/blink/renderer/platform/wtf/vector.h"
14 
15 namespace blink {
16 
17 // This enum corresponds to each step used to accommodate grid items across
18 // intrinsic tracks according to their min and max track sizing functions, as
19 // defined in https://drafts.csswg.org/css-grid-1/#algo-spanning-items.
20 enum class NGGridItemContributionType {
21   kForIntrinsicMinimums,
22   kForContentBasedMinimums,
23   kForMaxContentMinimums,
24   kForIntrinsicMaximums,
25   kForMaxContentMaximums
26 };
27 
28 enum class AutoPlacementType { kNotNeeded, kMajor, kMinor, kBoth };
29 
30 class CORE_EXPORT NGGridLayoutAlgorithm
31     : public NGLayoutAlgorithm<NGBlockNode,
32                                NGBoxFragmentBuilder,
33                                NGBlockBreakToken> {
34  public:
35   enum class AxisEdge { kStart, kCenter, kEnd, kBaseline };
36 
37   struct GridItemData {
38     explicit GridItemData(const NGBlockNode node);
39 
40     AutoPlacementType AutoPlacement(
41         GridTrackSizingDirection flow_direction) const;
42     const GridSpan& Span(GridTrackSizingDirection track_direction) const;
43     void SetSpan(const GridSpan& span,
44                  GridTrackSizingDirection track_direction);
45 
46     wtf_size_t StartLine(GridTrackSizingDirection track_direction) const;
47     wtf_size_t EndLine(GridTrackSizingDirection track_direction) const;
48     wtf_size_t SpanSize(GridTrackSizingDirection track_direction) const;
49 
50     const NGBlockNode node;
51     GridArea resolved_position;
52 
53     NGBoxStrut margins;
54     LayoutUnit inline_size;
55     MinMaxSizes min_max_sizes;
56 
57     // These fields are used to determine the sets this item spans in the
58     // respective track collection; see |CacheItemSetIndices|.
59     wtf_size_t columns_begin_set_index;
60     wtf_size_t columns_end_set_index;
61     wtf_size_t rows_begin_set_index;
62     wtf_size_t rows_end_set_index;
63 
64     AxisEdge inline_axis_alignment;
65     AxisEdge block_axis_alignment;
66 
67     bool is_inline_axis_stretched;
68     bool is_block_axis_stretched;
69 
70     bool is_spanning_flex_track : 1;
71     bool is_spanning_intrinsic_track : 1;
72   };
73 
74   explicit NGGridLayoutAlgorithm(const NGLayoutAlgorithmParams& params);
75 
76   scoped_refptr<const NGLayoutResult> Layout() override;
77 
78   MinMaxSizesResult ComputeMinMaxSizes(const MinMaxSizesInput&) const override;
79 
80   const NGGridLayoutAlgorithmTrackCollection& ColumnTrackCollection() const;
81   const NGGridLayoutAlgorithmTrackCollection& RowTrackCollection() const;
82 
83  private:
84   using NGGridSetVector = Vector<NGGridSet*, 16>;
85 
86   friend class NGGridLayoutAlgorithmTest;
87 
88   enum class GridLayoutAlgorithmState {
89     kMeasuringItems,
90     kResolvingInlineSize,
91     kResolvingBlockSize,
92     kPlacingGridItems,
93     kCompletedLayout
94   };
95 
96   class ReorderedGridItems {
97    public:
98     class Iterator
99         : public std::iterator<std::input_iterator_tag, GridItemData> {
100      public:
101       Iterator(Vector<wtf_size_t>::const_iterator current_index,
102                Vector<GridItemData>* grid_items);
103 
104       bool operator!=(const Iterator& other) const;
105       GridItemData* operator->();
106       GridItemData& operator*();
107       Iterator& operator++();
108 
109      private:
110       Vector<wtf_size_t>::const_iterator current_index_;
111       Vector<GridItemData>* grid_items_;
112     };
113 
114     ReorderedGridItems(const Vector<wtf_size_t>& reordered_item_indices,
115                        Vector<GridItemData>& grid_items);
116     Iterator begin();
117     Iterator end();
118 
119    private:
120     const Vector<wtf_size_t>& reordered_item_indices_;
121     Vector<GridItemData>& grid_items_;
122   };
123 
124   ReorderedGridItems GetReorderedGridItems();
125   NGGridLayoutAlgorithmTrackCollection& TrackCollection(
126       GridTrackSizingDirection track_direction);
127 
128   // Returns an iterator for every |NGGridSet| contained within an item's span
129   // in the relevant track collection.
130   NGGridLayoutAlgorithmTrackCollection::SetIterator GetSetIteratorForItem(
131       const GridItemData& item,
132       GridTrackSizingDirection track_direction);
133 
134   // Returns the size that a grid item will distribute across the tracks with an
135   // intrinsic sizing function it spans in the relevant track direction.
136   LayoutUnit ContributionSizeForGridItem(
137       const GridItemData& grid_item,
138       GridTrackSizingDirection track_direction,
139       NGGridItemContributionType contribution_type) const;
140 
141   void ConstructAndAppendGridItems();
142   GridItemData MeasureGridItem(const NGBlockNode node);
143   NGConstraintSpace BuildSpaceForGridItem(const NGBlockNode node) const;
144 
145   // Sets the specified tracks for row and column track lists.
146   void SetSpecifiedTracks();
147   // Determines the explicit column and row track starts.
148   void DetermineExplicitTrackStarts();
149 
150   // For every item and track direction, computes and stores the pair of indices
151   // "begin" and "end" such that the item spans every set from the respective
152   // collection's |sets_| with an index in the range [begin, end).
153   void CacheItemSetIndices();
154   // For every grid item, determines if it spans a track with an intrinsic or
155   // flexible sizing function and caches the answer in its |GridItemData|.
156   void DetermineGridItemsSpanningIntrinsicOrFlexTracks(
157       GridTrackSizingDirection track_direction);
158 
159   // Calculates from the min and max track sizing functions the used track size.
160   void ComputeUsedTrackSizes(GridTrackSizingDirection track_direction);
161 
162   // These methods implement the steps of the algorithm for intrinsic track size
163   // resolution defined in https://drafts.csswg.org/css-grid-1/#algo-content.
164   void ResolveIntrinsicTrackSizes(GridTrackSizingDirection track_direction);
165   void IncreaseTrackSizesToAccommodateGridItems(
166       GridTrackSizingDirection track_direction,
167       ReorderedGridItems::Iterator group_begin,
168       ReorderedGridItems::Iterator group_end,
169       NGGridItemContributionType contribution_type);
170   void DistributeExtraSpaceToSets(LayoutUnit extra_space,
171                                   NGGridItemContributionType contribution_type,
172                                   NGGridSetVector* sets_to_grow,
173                                   NGGridSetVector* sets_to_grow_beyond_limit);
174 
175   // Allows a test to set the value for automatic track repetition.
176   void SetAutomaticTrackRepetitionsForTesting(wtf_size_t auto_column,
177                                               wtf_size_t auto_row);
178   wtf_size_t AutoRepeatCountForDirection(
179       GridTrackSizingDirection track_direction) const;
180 
181   // Lays out and computes inline and block offsets for grid items.
182   void PlaceGridItems();
183 
184   // Lays out |grid_item| based on the offsets and sizes provided.
185   void PlaceGridItem(const GridItemData& grid_item,
186                      LogicalOffset offset,
187                      LogicalSize size);
188 
189   // Gets the row or column gap of the grid.
190   LayoutUnit GridGap(GridTrackSizingDirection track_direction,
191                      LayoutUnit available_size = kIndefiniteSize);
192 
193   // Calculates inline and block offsets for all tracks.
194   Vector<LayoutUnit> ComputeSetOffsets(GridTrackSizingDirection track_direction,
195                                        LayoutUnit grid_gap);
196 
197   // Tests whether the row gap is unresolvable based on its type and the
198   // available size.
199   bool IsRowGridGapUnresolvable(LayoutUnit available_size);
200 
201   GridTrackSizingDirection AutoFlowDirection() const;
202 
203   GridLayoutAlgorithmState state_;
204   LogicalSize border_box_size_;
205   LogicalSize child_percentage_size_;
206   LayoutUnit intrinsic_block_size_;
207 
208   Vector<GridItemData> grid_items_;
209   Vector<GridItemData> out_of_flow_items_;
210   Vector<wtf_size_t> reordered_item_indices_;
211 
212   NGGridBlockTrackCollection block_column_track_collection_;
213   NGGridBlockTrackCollection block_row_track_collection_;
214 
215   NGGridLayoutAlgorithmTrackCollection algorithm_column_track_collection_;
216   NGGridLayoutAlgorithmTrackCollection algorithm_row_track_collection_;
217 
218   wtf_size_t explicit_column_start_ = 0;
219   wtf_size_t explicit_row_start_ = 0;
220   wtf_size_t column_count_ = 0;
221   wtf_size_t row_count_ = 0;
222 
223   wtf_size_t automatic_column_repetitions_ =
224       NGGridBlockTrackCollection::kInvalidRangeIndex;
225   wtf_size_t automatic_row_repetitions_ =
226       NGGridBlockTrackCollection::kInvalidRangeIndex;
227 };
228 
229 }  // namespace blink
230 
231 #endif  // THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_NG_GRID_NG_GRID_LAYOUT_ALGORITHM_H_
232