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