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