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