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 #ifndef THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_GRID_TRACK_SIZING_ALGORITHM_H_ 6 #define THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_GRID_TRACK_SIZING_ALGORITHM_H_ 7 8 #include <memory> 9 #include "base/macros.h" 10 #include "base/optional.h" 11 #include "third_party/blink/renderer/core/layout/grid_baseline_alignment.h" 12 #include "third_party/blink/renderer/core/layout/layout_box.h" 13 #include "third_party/blink/renderer/core/style/grid_positions_resolver.h" 14 #include "third_party/blink/renderer/core/style/grid_track_size.h" 15 #include "third_party/blink/renderer/platform/geometry/layout_unit.h" 16 #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h" 17 #include "third_party/blink/renderer/platform/wtf/hash_set.h" 18 19 namespace blink { 20 21 static const int kInfinity = -1; 22 23 class Grid; 24 class GridTrackSizingAlgorithmStrategy; 25 class LayoutGrid; 26 27 enum TrackSizeComputationPhase { 28 kResolveIntrinsicMinimums, 29 kResolveContentBasedMinimums, 30 kResolveMaxContentMinimums, 31 kResolveIntrinsicMaximums, 32 kResolveMaxContentMaximums, 33 kMaximizeTracks, 34 }; 35 36 class GridTrack { 37 DISALLOW_NEW(); 38 39 public: GridTrack()40 GridTrack() : infinitely_growable_(false) {} 41 42 LayoutUnit BaseSize() const; 43 void SetBaseSize(LayoutUnit); 44 45 LayoutUnit GrowthLimit() const; GrowthLimitIsInfinite()46 bool GrowthLimitIsInfinite() const { return growth_limit_ == kInfinity; } 47 void SetGrowthLimit(LayoutUnit); 48 49 bool InfiniteGrowthPotential() const; 50 PlannedSize()51 LayoutUnit PlannedSize() const { return planned_size_; } 52 void SetPlannedSize(LayoutUnit); 53 SizeDuringDistribution()54 LayoutUnit SizeDuringDistribution() const { 55 return size_during_distribution_; 56 } 57 void SetSizeDuringDistribution(LayoutUnit); 58 59 void GrowSizeDuringDistribution(LayoutUnit); 60 InfinitelyGrowable()61 bool InfinitelyGrowable() const { return infinitely_growable_; } 62 void SetInfinitelyGrowable(bool); 63 GrowthLimitCap()64 base::Optional<LayoutUnit> GrowthLimitCap() const { 65 return growth_limit_cap_; 66 } 67 void SetGrowthLimitCap(base::Optional<LayoutUnit>); 68 CachedTrackSize()69 const GridTrackSize& CachedTrackSize() const { 70 DCHECK(cached_track_size_.has_value()); 71 return cached_track_size_.value(); 72 } 73 void SetCachedTrackSize(const GridTrackSize&); 74 75 private: 76 bool IsGrowthLimitBiggerThanBaseSize() const; 77 void EnsureGrowthLimitIsBiggerThanBaseSize(); 78 79 LayoutUnit base_size_; 80 LayoutUnit growth_limit_; 81 LayoutUnit planned_size_; 82 LayoutUnit size_during_distribution_; 83 base::Optional<LayoutUnit> growth_limit_cap_; 84 bool infinitely_growable_; 85 base::Optional<GridTrackSize> cached_track_size_; 86 }; 87 88 class GridTrackSizingAlgorithm final { 89 friend class GridTrackSizingAlgorithmStrategy; 90 91 public: GridTrackSizingAlgorithm(const LayoutGrid * layout_grid,Grid & grid)92 GridTrackSizingAlgorithm(const LayoutGrid* layout_grid, Grid& grid) 93 : grid_(grid), 94 layout_grid_(layout_grid), 95 sizing_state_(kColumnSizingFirstIteration) {} 96 97 // Setup() must be run before calling Run() as it configures the behaviour of 98 // the algorithm. 99 void Setup(GridTrackSizingDirection, 100 size_t num_tracks, 101 base::Optional<LayoutUnit> available_space); 102 void Run(); 103 void Reset(); 104 105 // Required by LayoutGrid. Try to minimize the exposed surface. GetGrid()106 const Grid& GetGrid() const { return grid_; } 107 // TODO (jfernandez): We should remove any public getter for this attribute 108 // and encapsulate any access in the algorithm class. GetMutableGrid()109 Grid& GetMutableGrid() const { return grid_; } MinContentSize()110 LayoutUnit MinContentSize() const { return min_content_size_; } MaxContentSize()111 LayoutUnit MaxContentSize() const { return max_content_size_; } 112 113 LayoutUnit BaselineOffsetForChild(const LayoutBox&, GridAxis) const; 114 115 void CacheBaselineAlignedItem(const LayoutBox&, GridAxis); 116 void CopyBaselineItemsCache(const GridTrackSizingAlgorithm&, GridAxis); 117 void ClearBaselineItemsCache(); 118 119 LayoutSize EstimatedGridAreaBreadthForChild(const LayoutBox& child) const; 120 121 Vector<GridTrack>& Tracks(GridTrackSizingDirection); 122 const Vector<GridTrack>& Tracks(GridTrackSizingDirection) const; 123 124 base::Optional<LayoutUnit> FreeSpace(GridTrackSizingDirection) const; 125 void SetFreeSpace(GridTrackSizingDirection, base::Optional<LayoutUnit>); 126 127 base::Optional<LayoutUnit> AvailableSpace(GridTrackSizingDirection) const; 128 void SetAvailableSpace(GridTrackSizingDirection, base::Optional<LayoutUnit>); 129 130 #if DCHECK_IS_ON() 131 bool TracksAreWiderThanMinTrackBreadth() const; 132 #endif 133 134 LayoutUnit ComputeTrackBasedSize() const; 135 HasAnyPercentSizedRowsIndefiniteHeight()136 bool HasAnyPercentSizedRowsIndefiniteHeight() const { 137 return has_percent_sized_rows_indefinite_height_; 138 } 139 140 private: 141 base::Optional<LayoutUnit> AvailableSpace() const; 142 bool IsRelativeGridLengthAsAuto(const GridLength&, 143 GridTrackSizingDirection) const; 144 bool IsRelativeSizedTrackAsAuto(const GridTrackSize&, 145 GridTrackSizingDirection) const; 146 GridTrackSize CalculateGridTrackSize(GridTrackSizingDirection, 147 size_t translated_index) const; 148 const GridTrackSize& RawGridTrackSize(GridTrackSizingDirection, 149 size_t translated_index) const; 150 151 // Helper methods for step 1. initializeTrackSizes(). 152 LayoutUnit InitialBaseSize(const GridTrackSize&) const; 153 LayoutUnit InitialGrowthLimit(const GridTrackSize&, 154 LayoutUnit base_size) const; 155 156 // Helper methods for step 2. resolveIntrinsicTrackSizes(). 157 void SizeTrackToFitNonSpanningItem(const GridSpan&, 158 LayoutBox& grid_item, 159 GridTrack&); 160 bool SpanningItemCrossesFlexibleSizedTracks(const GridSpan&) const; 161 typedef struct GridItemsSpanGroupRange GridItemsSpanGroupRange; 162 template <TrackSizeComputationPhase phase> 163 void IncreaseSizesToAccommodateSpanningItems( 164 const GridItemsSpanGroupRange& grid_items_with_span); 165 LayoutUnit ItemSizeForTrackSizeComputationPhase(TrackSizeComputationPhase, 166 LayoutBox&) const; 167 template <TrackSizeComputationPhase phase> 168 void DistributeSpaceToTracks( 169 Vector<GridTrack*>& tracks, 170 Vector<GridTrack*>* grow_beyond_growth_limits_tracks, 171 LayoutUnit& available_logical_space) const; 172 LayoutUnit EstimatedGridAreaBreadthForChild(const LayoutBox&, 173 GridTrackSizingDirection) const; 174 LayoutUnit GridAreaBreadthForChild(const LayoutBox&, 175 GridTrackSizingDirection) const; 176 177 void ComputeBaselineAlignmentContext(); 178 void UpdateBaselineAlignmentContext(const LayoutBox&, GridAxis); 179 bool CanParticipateInBaselineAlignment(const LayoutBox&, GridAxis) const; 180 bool ParticipateInBaselineAlignment(const LayoutBox&, GridAxis) const; 181 182 bool IsIntrinsicSizedGridArea(const LayoutBox&, GridAxis) const; 183 void ComputeGridContainerIntrinsicSizes(); 184 185 // Helper methods for step 4. Strech flexible tracks. 186 typedef HashSet<size_t, 187 DefaultHash<size_t>::Hash, 188 WTF::UnsignedWithZeroKeyHashTraits<size_t>> 189 TrackIndexSet; 190 double ComputeFlexFactorUnitSize( 191 const Vector<GridTrack>& tracks, 192 double flex_factor_sum, 193 LayoutUnit& left_over_space, 194 const Vector<size_t, 8>& flexible_tracks_indexes, 195 std::unique_ptr<TrackIndexSet> tracks_to_treat_as_inflexible = 196 nullptr) const; 197 void ComputeFlexSizedTracksGrowth(double flex_fraction, 198 Vector<LayoutUnit>& increments, 199 LayoutUnit& total_growth) const; 200 double FindFrUnitSize(const GridSpan& tracks_span, 201 LayoutUnit left_over_space) const; 202 203 // Track sizing algorithm steps. Note that the "Maximize Tracks" step is done 204 // entirely inside the strategies, that's why we don't need an additional 205 // method at thise level. 206 void InitializeTrackSizes(); 207 void ResolveIntrinsicTrackSizes(); 208 void StretchFlexibleTracks(base::Optional<LayoutUnit> free_space); 209 void StretchAutoTracks(); 210 211 // State machine. 212 void AdvanceNextState(); 213 bool IsValidTransition() const; 214 215 // Data. WasSetup()216 bool WasSetup() const { return !!strategy_; } 217 bool needs_setup_{true}; 218 bool has_percent_sized_rows_indefinite_height_{false}; 219 base::Optional<LayoutUnit> available_space_columns_; 220 base::Optional<LayoutUnit> available_space_rows_; 221 222 base::Optional<LayoutUnit> free_space_columns_; 223 base::Optional<LayoutUnit> free_space_rows_; 224 225 // We need to keep both alive in order to properly size grids with orthogonal 226 // writing modes. 227 Vector<GridTrack> columns_; 228 Vector<GridTrack> rows_; 229 Vector<size_t> content_sized_tracks_index_; 230 Vector<size_t> flexible_sized_tracks_index_; 231 Vector<size_t> auto_sized_tracks_for_stretch_index_; 232 233 GridTrackSizingDirection direction_; 234 235 Grid& grid_; 236 237 const LayoutGrid* layout_grid_; 238 std::unique_ptr<GridTrackSizingAlgorithmStrategy> strategy_; 239 240 // The track sizing algorithm is used for both layout and intrinsic size 241 // computation. We're normally just interested in intrinsic inline sizes 242 // (a.k.a widths in most of the cases) for the computeIntrinsicLogicalWidths() 243 // computations. That's why we don't need to keep around different values for 244 // rows/columns. 245 LayoutUnit min_content_size_; 246 LayoutUnit max_content_size_; 247 248 enum SizingState { 249 kColumnSizingFirstIteration, 250 kRowSizingFirstIteration, 251 kColumnSizingSecondIteration, 252 kRowSizingSecondIteration 253 }; 254 SizingState sizing_state_; 255 256 GridBaselineAlignment baseline_alignment_; 257 typedef HashMap<const LayoutBox*, bool> BaselineItemsCache; 258 BaselineItemsCache column_baseline_items_map_; 259 BaselineItemsCache row_baseline_items_map_; 260 261 // This is a RAII class used to ensure that the track sizing algorithm is 262 // executed as it is suppossed to be, i.e., first resolve columns and then 263 // rows. Only if required a second iteration is run following the same order, 264 // first columns and then rows. 265 class StateMachine { 266 public: 267 StateMachine(GridTrackSizingAlgorithm&); 268 ~StateMachine(); 269 270 private: 271 GridTrackSizingAlgorithm& algorithm_; 272 }; 273 }; 274 275 class GridTrackSizingAlgorithmStrategy { 276 USING_FAST_MALLOC(GridTrackSizingAlgorithmStrategy); 277 278 public: 279 virtual ~GridTrackSizingAlgorithmStrategy(); 280 281 virtual LayoutUnit MinContentForChild(LayoutBox&) const; 282 virtual LayoutUnit MaxContentForChild(LayoutBox&) const; 283 LayoutUnit MinSizeForChild(LayoutBox&) const; 284 285 virtual void MaximizeTracks(Vector<GridTrack>&, 286 base::Optional<LayoutUnit>& free_space) = 0; 287 virtual double FindUsedFlexFraction( 288 Vector<size_t>& flexible_sized_tracks_index, 289 GridTrackSizingDirection, 290 base::Optional<LayoutUnit> initial_free_space) const = 0; 291 virtual bool RecomputeUsedFlexFractionIfNeeded( 292 Vector<size_t>& flexible_sized_tracks_index, 293 double& flex_fraction, 294 Vector<LayoutUnit>& increments, 295 LayoutUnit& total_growth) const = 0; 296 virtual LayoutUnit FreeSpaceForStretchAutoTracksStep() const = 0; 297 virtual bool IsComputingSizeContainment() const = 0; 298 299 protected: GridTrackSizingAlgorithmStrategy(GridTrackSizingAlgorithm & algorithm)300 GridTrackSizingAlgorithmStrategy(GridTrackSizingAlgorithm& algorithm) 301 : algorithm_(algorithm) {} 302 303 virtual LayoutUnit MinLogicalSizeForChild(LayoutBox&, 304 const Length& child_min_size, 305 LayoutUnit available_size) const; 306 virtual void LayoutGridItemForMinSizeComputation( 307 LayoutBox&, 308 bool override_size_has_changed) const = 0; 309 310 LayoutUnit LogicalHeightForChild(LayoutBox&) const; 311 312 bool UpdateOverrideContainingBlockContentSizeForChild( 313 LayoutBox&, 314 GridTrackSizingDirection, 315 base::Optional<LayoutUnit> = base::nullopt) const; 316 LayoutUnit ComputeTrackBasedSize() const; 317 Direction()318 GridTrackSizingDirection Direction() const { return algorithm_.direction_; } 319 double FindFrUnitSize(const GridSpan& tracks_span, 320 LayoutUnit left_over_space) const; 321 void DistributeSpaceToTracks(Vector<GridTrack*>& tracks, 322 LayoutUnit& available_logical_space) const; GetLayoutGrid()323 const LayoutGrid* GetLayoutGrid() const { return algorithm_.layout_grid_; } AvailableSpace()324 base::Optional<LayoutUnit> AvailableSpace() const { 325 return algorithm_.AvailableSpace(); 326 } 327 328 // Helper functions 329 static bool HasRelativeMarginOrPaddingForChild(const LayoutGrid&, 330 const LayoutBox& child, 331 GridTrackSizingDirection); 332 static bool HasRelativeOrIntrinsicSizeForChild(const LayoutGrid&, 333 const LayoutBox& child, 334 GridTrackSizingDirection); 335 static bool ShouldClearOverrideContainingBlockContentSizeForChild( 336 const LayoutGrid&, 337 const LayoutBox& child, 338 GridTrackSizingDirection); 339 static void SetOverrideContainingBlockContentSizeForChild( 340 LayoutBox& child, 341 GridTrackSizingDirection, 342 LayoutUnit size); 343 344 GridTrackSizingAlgorithm& algorithm_; 345 346 private: 347 DISALLOW_COPY_AND_ASSIGN(GridTrackSizingAlgorithmStrategy); 348 }; 349 } 350 351 #endif // THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_GRID_TRACK_SIZING_ALGORITHM_H_ 352