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