1/*
2 * Copyright (C) 2017 Igalia S.L.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25#pragma once
26
27#include "Grid.h"
28#include "GridBaselineAlignment.h"
29#include "GridTrackSize.h"
30#include "LayoutSize.h"
31
32namespace WebCore {
33
34static const int infinity = -1;
35
36enum SizingOperation { TrackSizing, IntrinsicSizeComputation };
37
38enum TrackSizeComputationPhase {
39 ResolveIntrinsicMinimums,
40 ResolveContentBasedMinimums,
41 ResolveMaxContentMinimums,
42 ResolveIntrinsicMaximums,
43 ResolveMaxContentMaximums,
44 MaximizeTracks,
45};
46
47class GridTrackSizingAlgorithmStrategy;
48
49class GridTrack {
50public:
51 GridTrack() = default;
52
53 const LayoutUnit& baseSize() const;
54 void setBaseSize(LayoutUnit);
55
56 const LayoutUnit& growthLimit() const;
57 bool growthLimitIsInfinite() const { return m_growthLimit == infinity; }
58 void setGrowthLimit(LayoutUnit);
59
60 bool infiniteGrowthPotential() const { return growthLimitIsInfinite() || m_infinitelyGrowable; }
61 const LayoutUnit& growthLimitIfNotInfinite() const;
62
63 const LayoutUnit& plannedSize() const { return m_plannedSize; }
64 void setPlannedSize(LayoutUnit plannedSize) { m_plannedSize = plannedSize; }
65
66 const LayoutUnit& tempSize() const { return m_tempSize; }
67 void setTempSize(const LayoutUnit&);
68 void growTempSize(const LayoutUnit&);
69
70 bool infinitelyGrowable() const { return m_infinitelyGrowable; }
71 void setInfinitelyGrowable(bool infinitelyGrowable) { m_infinitelyGrowable = infinitelyGrowable; }
72
73 void setGrowthLimitCap(Optional<LayoutUnit>);
74 Optional<LayoutUnit> growthLimitCap() const { return m_growthLimitCap; }
75
76private:
77 bool isGrowthLimitBiggerThanBaseSize() const { return growthLimitIsInfinite() || m_growthLimit >= m_baseSize; }
78
79 void ensureGrowthLimitIsBiggerThanBaseSize();
80
81 LayoutUnit m_baseSize { 0 };
82 LayoutUnit m_growthLimit { 0 };
83 LayoutUnit m_plannedSize { 0 };
84 LayoutUnit m_tempSize { 0 };
85 Optional<LayoutUnit> m_growthLimitCap;
86 bool m_infinitelyGrowable { false };
87};
88
89class GridTrackSizingAlgorithm final {
90 friend class GridTrackSizingAlgorithmStrategy;
91
92public:
93 GridTrackSizingAlgorithm(const RenderGrid* renderGrid, Grid& grid)
94 : m_grid(grid)
95 , m_renderGrid(renderGrid)
96 , m_sizingState(ColumnSizingFirstIteration)
97 {
98 }
99
100 void setup(GridTrackSizingDirection, unsigned numTracks, SizingOperation, Optional<LayoutUnit> availableSpace, Optional<LayoutUnit> freeSpace);
101 void run();
102 void reset();
103
104 // Required by RenderGrid. Try to minimize the exposed surface.
105 const Grid& grid() const { return m_grid; }
106 // FIXME (jfernandez): We should remove any public getter for this attribute
107 // and encapsulate any access in the algorithm class.
108 Grid& mutableGrid() const { return m_grid; }
109
110 LayoutUnit minContentSize() const { return m_minContentSize; };
111 LayoutUnit maxContentSize() const { return m_maxContentSize; };
112
113 LayoutSize estimatedGridAreaBreadthForChild(const RenderBox&) const;
114 LayoutUnit baselineOffsetForChild(const RenderBox&, GridAxis) const;
115
116 void cacheBaselineAlignedItem(const RenderBox&, GridAxis);
117 void copyBaselineItemsCache(const GridTrackSizingAlgorithm&, GridAxis);
118 void clearBaselineItemsCache();
119
120 Vector<GridTrack>& tracks(GridTrackSizingDirection direction) { return direction == ForColumns ? m_columns : m_rows; }
121 const Vector<GridTrack>& tracks(GridTrackSizingDirection direction) const { return direction == ForColumns ? m_columns : m_rows; }
122
123 Optional<LayoutUnit> freeSpace(GridTrackSizingDirection direction) const { return direction == ForColumns ? m_freeSpaceColumns : m_freeSpaceRows; }
124 void setFreeSpace(GridTrackSizingDirection, Optional<LayoutUnit>);
125
126 Optional<LayoutUnit> availableSpace(GridTrackSizingDirection direction) const { return direction == ForColumns ? m_availableSpaceColumns : m_availableSpaceRows; }
127 void setAvailableSpace(GridTrackSizingDirection, Optional<LayoutUnit>);
128
129 LayoutUnit computeTrackBasedSize() const;
130
131 bool hasAnyPercentSizedRowsIndefiniteHeight() const { return m_hasPercentSizedRowsIndefiniteHeight; }
132
133#ifndef NDEBUG
134 bool tracksAreWiderThanMinTrackBreadth() const;
135#endif
136
137private:
138 Optional<LayoutUnit> availableSpace() const;
139 bool isRelativeGridLengthAsAuto(const GridLength&, GridTrackSizingDirection) const;
140 GridTrackSize gridTrackSize(GridTrackSizingDirection, unsigned translatedIndex) const;
141 const GridTrackSize& rawGridTrackSize(GridTrackSizingDirection, unsigned translatedIndex) const;
142
143 // Helper methods for step 1. initializeTrackSizes().
144 LayoutUnit initialBaseSize(const GridTrackSize&) const;
145 LayoutUnit initialGrowthLimit(const GridTrackSize&, LayoutUnit baseSize) const;
146
147 // Helper methods for step 2. resolveIntrinsicTrackSizes().
148 void sizeTrackToFitNonSpanningItem(const GridSpan&, RenderBox& gridItem, GridTrack&);
149 bool spanningItemCrossesFlexibleSizedTracks(const GridSpan&) const;
150 typedef struct GridItemsSpanGroupRange GridItemsSpanGroupRange;
151 template <TrackSizeComputationPhase phase> void increaseSizesToAccommodateSpanningItems(const GridItemsSpanGroupRange& gridItemsWithSpan);
152 LayoutUnit itemSizeForTrackSizeComputationPhase(TrackSizeComputationPhase, RenderBox&) const;
153 template <TrackSizeComputationPhase phase> void distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* growBeyondGrowthLimitsTracks, LayoutUnit& availableLogicalSpace) const;
154 LayoutUnit estimatedGridAreaBreadthForChild(const RenderBox&, GridTrackSizingDirection) const;
155 LayoutUnit gridAreaBreadthForChild(const RenderBox&, GridTrackSizingDirection) const;
156
157 void computeBaselineAlignmentContext();
158 void updateBaselineAlignmentContext(const RenderBox&, GridAxis);
159 bool canParticipateInBaselineAlignment(const RenderBox&, GridAxis) const;
160 bool participateInBaselineAlignment(const RenderBox&, GridAxis) const;
161
162 bool isIntrinsicSizedGridArea(const RenderBox&, GridAxis) const;
163 void computeGridContainerIntrinsicSizes();
164
165 // Helper methods for step 4. Strech flexible tracks.
166 typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> TrackIndexSet;
167 double computeFlexFactorUnitSize(const Vector<GridTrack>& tracks, double flexFactorSum, LayoutUnit& leftOverSpace, const Vector<unsigned, 8>& flexibleTracksIndexes, std::unique_ptr<TrackIndexSet> tracksToTreatAsInflexible = nullptr) const;
168 void computeFlexSizedTracksGrowth(double flexFraction, Vector<LayoutUnit>& increments, LayoutUnit& totalGrowth) const;
169 double findFrUnitSize(const GridSpan& tracksSpan, LayoutUnit leftOverSpace) const;
170
171 // Track sizing algorithm steps. Note that the "Maximize Tracks" step is done
172 // entirely inside the strategies, that's why we don't need an additional
173 // method at thise level.
174 void initializeTrackSizes();
175 void resolveIntrinsicTrackSizes();
176 void stretchFlexibleTracks(Optional<LayoutUnit> freeSpace);
177 void stretchAutoTracks();
178
179 // State machine.
180 void advanceNextState();
181 bool isValidTransition() const;
182
183 // Data.
184 bool wasSetup() const { return !!m_strategy; }
185 bool m_needsSetup { true };
186 bool m_hasPercentSizedRowsIndefiniteHeight { false };
187 Optional<LayoutUnit> m_availableSpaceRows;
188 Optional<LayoutUnit> m_availableSpaceColumns;
189
190 Optional<LayoutUnit> m_freeSpaceColumns;
191 Optional<LayoutUnit> m_freeSpaceRows;
192
193 // We need to keep both alive in order to properly size grids with orthogonal
194 // writing modes.
195 Vector<GridTrack> m_columns;
196 Vector<GridTrack> m_rows;
197 Vector<unsigned> m_contentSizedTracksIndex;
198 Vector<unsigned> m_flexibleSizedTracksIndex;
199 Vector<unsigned> m_autoSizedTracksForStretchIndex;
200
201 GridTrackSizingDirection m_direction;
202 SizingOperation m_sizingOperation;
203
204 Grid& m_grid;
205
206 const RenderGrid* m_renderGrid;
207 std::unique_ptr<GridTrackSizingAlgorithmStrategy> m_strategy;
208
209 // The track sizing algorithm is used for both layout and intrinsic size
210 // computation. We're normally just interested in intrinsic inline sizes
211 // (a.k.a widths in most of the cases) for the computeIntrinsicLogicalWidths()
212 // computations. That's why we don't need to keep around different values for
213 // rows/columns.
214 LayoutUnit m_minContentSize;
215 LayoutUnit m_maxContentSize;
216
217 enum SizingState {
218 ColumnSizingFirstIteration,
219 RowSizingFirstIteration,
220 ColumnSizingSecondIteration,
221 RowSizingSecondIteration
222 };
223 SizingState m_sizingState;
224
225 GridBaselineAlignment m_baselineAlignment;
226 typedef HashMap<const RenderBox*, bool> BaselineItemsCache;
227 BaselineItemsCache m_columnBaselineItemsMap;
228 BaselineItemsCache m_rowBaselineItemsMap;
229
230 // This is a RAII class used to ensure that the track sizing algorithm is
231 // executed as it is suppossed to be, i.e., first resolve columns and then
232 // rows. Only if required a second iteration is run following the same order,
233 // first columns and then rows.
234 class StateMachine {
235 public:
236 StateMachine(GridTrackSizingAlgorithm&);
237 ~StateMachine();
238
239 private:
240 GridTrackSizingAlgorithm& m_algorithm;
241 };
242};
243
244class GridTrackSizingAlgorithmStrategy {
245 WTF_MAKE_FAST_ALLOCATED;
246public:
247 LayoutUnit minContentForChild(RenderBox&) const;
248 LayoutUnit maxContentForChild(RenderBox&) const;
249 LayoutUnit minSizeForChild(RenderBox&) const;
250
251 virtual ~GridTrackSizingAlgorithmStrategy() = default;
252
253 virtual void maximizeTracks(Vector<GridTrack>&, Optional<LayoutUnit>& freeSpace) = 0;
254 virtual double findUsedFlexFraction(Vector<unsigned>& flexibleSizedTracksIndex, GridTrackSizingDirection, Optional<LayoutUnit> initialFreeSpace) const = 0;
255 virtual bool recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const = 0;
256 virtual LayoutUnit freeSpaceForStretchAutoTracksStep() const = 0;
257
258protected:
259 GridTrackSizingAlgorithmStrategy(GridTrackSizingAlgorithm& algorithm)
260 : m_algorithm(algorithm) { }
261
262 virtual LayoutUnit minLogicalWidthForChild(RenderBox&, Length childMinSize, LayoutUnit availableSize) const = 0;
263 virtual void layoutGridItemForMinSizeComputation(RenderBox&, bool overrideSizeHasChanged) const = 0;
264
265 LayoutUnit logicalHeightForChild(RenderBox&) const;
266 bool updateOverrideContainingBlockContentSizeForChild(RenderBox&, GridTrackSizingDirection, Optional<LayoutUnit> = WTF::nullopt) const;
267
268 GridTrackSize gridTrackSize(GridTrackSizingDirection direction, size_t translatedIndex) const { return m_algorithm.gridTrackSize(direction, translatedIndex); }
269
270 // GridTrackSizingAlgorithm accessors for subclasses.
271 LayoutUnit computeTrackBasedSize() const { return m_algorithm.computeTrackBasedSize(); }
272 GridTrackSizingDirection direction() const { return m_algorithm.m_direction; }
273 double findFrUnitSize(const GridSpan& tracksSpan, LayoutUnit leftOverSpace) const { return m_algorithm.findFrUnitSize(tracksSpan, leftOverSpace); }
274 void distributeSpaceToTracks(Vector<GridTrack*>& tracks, LayoutUnit& availableLogicalSpace) const { m_algorithm.distributeSpaceToTracks<MaximizeTracks>(tracks, nullptr, availableLogicalSpace); }
275 const RenderGrid* renderGrid() const { return m_algorithm.m_renderGrid; }
276 Optional<LayoutUnit> availableSpace() const { return m_algorithm.availableSpace(); }
277
278 GridTrackSizingAlgorithm& m_algorithm;
279};
280
281} // namespace WebCore
282