1/*
2 * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
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. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "AxisScrollSnapOffsets.h"
28
29#include "ElementChildIterator.h"
30#include "HTMLCollection.h"
31#include "HTMLElement.h"
32#include "Length.h"
33#include "Logging.h"
34#include "RenderBox.h"
35#include "RenderView.h"
36#include "ScrollableArea.h"
37#include "StyleScrollSnapPoints.h"
38#include <wtf/text/StringConcatenateNumbers.h>
39
40#if ENABLE(CSS_SCROLL_SNAP)
41
42namespace WebCore {
43
44enum class InsetOrOutset {
45 Inset,
46 Outset
47};
48
49static LayoutRect computeScrollSnapPortOrAreaRect(const LayoutRect& rect, const LengthBox& insetOrOutsetBox, InsetOrOutset insetOrOutset)
50{
51 LayoutBoxExtent extents(valueForLength(insetOrOutsetBox.top(), rect.height()), valueForLength(insetOrOutsetBox.right(), rect.width()), valueForLength(insetOrOutsetBox.bottom(), rect.height()), valueForLength(insetOrOutsetBox.left(), rect.width()));
52 auto snapPortOrArea(rect);
53 if (insetOrOutset == InsetOrOutset::Inset)
54 snapPortOrArea.contract(extents);
55 else
56 snapPortOrArea.expand(extents);
57 return snapPortOrArea;
58}
59
60static LayoutUnit computeScrollSnapAlignOffset(const LayoutUnit& leftOrTop, const LayoutUnit& widthOrHeight, ScrollSnapAxisAlignType alignment)
61{
62 switch (alignment) {
63 case ScrollSnapAxisAlignType::Start:
64 return leftOrTop;
65 case ScrollSnapAxisAlignType::Center:
66 return leftOrTop + widthOrHeight / 2;
67 case ScrollSnapAxisAlignType::End:
68 return leftOrTop + widthOrHeight;
69 default:
70 ASSERT_NOT_REACHED();
71 return 0;
72 }
73}
74
75#if !LOG_DISABLED
76
77static String snapOffsetsToString(const Vector<LayoutUnit>& snapOffsets)
78{
79 StringBuilder builder;
80 builder.appendLiteral("[ ");
81 for (auto& offset : snapOffsets) {
82 builder.appendFixedWidthNumber(offset.toFloat(), 1);
83 builder.append(' ');
84 }
85 builder.append(']');
86 return builder.toString();
87}
88
89static String snapOffsetRangesToString(const Vector<ScrollOffsetRange<LayoutUnit>>& ranges)
90{
91 StringBuilder builder;
92 builder.appendLiteral("[ ");
93 for (auto& range : ranges) {
94 builder.append('(');
95 builder.appendFixedWidthNumber(range.start.toFloat(), 1);
96 builder.appendLiteral(", ");
97 builder.appendFixedWidthNumber(range.end.toFloat(), 1);
98 builder.appendLiteral(") ");
99 }
100 builder.append(']');
101 return builder.toString();
102}
103
104static String snapPortOrAreaToString(const LayoutRect& rect)
105{
106 return makeString("{{",
107 FormattedNumber::fixedWidth(rect.x(), 1), ", ",
108 FormattedNumber::fixedWidth(rect.y(), 1), "} {",
109 FormattedNumber::fixedWidth(rect.width(), 1), ", ",
110 FormattedNumber::fixedWidth(rect.height(), 1), "}}");
111}
112
113#endif
114
115template <typename LayoutType>
116static void indicesOfNearestSnapOffsetRanges(LayoutType offset, const Vector<ScrollOffsetRange<LayoutType>>& snapOffsetRanges, unsigned& lowerIndex, unsigned& upperIndex)
117{
118 if (snapOffsetRanges.isEmpty()) {
119 lowerIndex = invalidSnapOffsetIndex;
120 upperIndex = invalidSnapOffsetIndex;
121 return;
122 }
123
124 int lowerIndexAsInt = -1;
125 int upperIndexAsInt = snapOffsetRanges.size();
126 do {
127 int middleIndex = (lowerIndexAsInt + upperIndexAsInt) / 2;
128 auto& range = snapOffsetRanges[middleIndex];
129 if (range.start < offset && offset < range.end) {
130 lowerIndexAsInt = middleIndex;
131 upperIndexAsInt = middleIndex;
132 break;
133 }
134
135 if (offset > range.end)
136 lowerIndexAsInt = middleIndex;
137 else
138 upperIndexAsInt = middleIndex;
139 } while (lowerIndexAsInt < upperIndexAsInt - 1);
140
141 if (offset <= snapOffsetRanges.first().start)
142 lowerIndex = invalidSnapOffsetIndex;
143 else
144 lowerIndex = lowerIndexAsInt;
145
146 if (offset >= snapOffsetRanges.last().end)
147 upperIndex = invalidSnapOffsetIndex;
148 else
149 upperIndex = upperIndexAsInt;
150}
151
152template <typename LayoutType>
153static void indicesOfNearestSnapOffsets(LayoutType offset, const Vector<LayoutType>& snapOffsets, unsigned& lowerIndex, unsigned& upperIndex)
154{
155 lowerIndex = 0;
156 upperIndex = snapOffsets.size() - 1;
157 while (lowerIndex < upperIndex - 1) {
158 int middleIndex = (lowerIndex + upperIndex) / 2;
159 auto middleOffset = snapOffsets[middleIndex];
160 if (offset == middleOffset) {
161 upperIndex = middleIndex;
162 lowerIndex = middleIndex;
163 break;
164 }
165
166 if (offset > middleOffset)
167 lowerIndex = middleIndex;
168 else
169 upperIndex = middleIndex;
170 }
171}
172
173static void adjustAxisSnapOffsetsForScrollExtent(Vector<LayoutUnit>& snapOffsets, float maxScrollExtent)
174{
175 if (snapOffsets.isEmpty())
176 return;
177
178 std::sort(snapOffsets.begin(), snapOffsets.end());
179 if (snapOffsets.last() != maxScrollExtent)
180 snapOffsets.append(maxScrollExtent);
181 if (snapOffsets.first())
182 snapOffsets.insert(0, 0);
183}
184
185static void computeAxisProximitySnapOffsetRanges(const Vector<LayoutUnit>& snapOffsets, Vector<ScrollOffsetRange<LayoutUnit>>& offsetRanges, LayoutUnit scrollPortAxisLength)
186{
187 // This is an arbitrary choice for what it means to be "in proximity" of a snap offset. We should play around with
188 // this and see what feels best.
189 static const float ratioOfScrollPortAxisLengthToBeConsideredForProximity = 0.3;
190 if (snapOffsets.size() < 2)
191 return;
192
193 // The extra rule accounting for scroll offset ranges in between the scroll destination and a potential snap offset
194 // handles the corner case where the user scrolls with momentum very lightly away from a snap offset, such that the
195 // predicted scroll destination is still within proximity of the snap offset. In this case, the regular (mandatory
196 // scroll snapping) behavior would be to snap to the next offset in the direction of momentum scrolling, but
197 // instead, it is more intuitive to either return to the original snap position (which we arbitrarily choose here)
198 // or scroll just outside of the snap offset range. This is another minor behavior tweak that we should play around
199 // with to see what feels best.
200 LayoutUnit proximityDistance { ratioOfScrollPortAxisLengthToBeConsideredForProximity * scrollPortAxisLength };
201 for (size_t index = 1; index < snapOffsets.size(); ++index) {
202 auto startOffset = snapOffsets[index - 1] + proximityDistance;
203 auto endOffset = snapOffsets[index] - proximityDistance;
204 if (startOffset < endOffset)
205 offsetRanges.append({ startOffset, endOffset });
206 }
207}
208
209void updateSnapOffsetsForScrollableArea(ScrollableArea& scrollableArea, HTMLElement& scrollingElement, const RenderBox& scrollingElementBox, const RenderStyle& scrollingElementStyle)
210{
211 auto* scrollContainer = scrollingElement.renderer();
212 auto scrollSnapType = scrollingElementStyle.scrollSnapType();
213 if (!scrollContainer || scrollSnapType.strictness == ScrollSnapStrictness::None || scrollContainer->view().boxesWithScrollSnapPositions().isEmpty()) {
214 scrollableArea.clearHorizontalSnapOffsets();
215 scrollableArea.clearVerticalSnapOffsets();
216 return;
217 }
218
219 Vector<LayoutUnit> verticalSnapOffsets;
220 Vector<LayoutUnit> horizontalSnapOffsets;
221 Vector<ScrollOffsetRange<LayoutUnit>> verticalSnapOffsetRanges;
222 Vector<ScrollOffsetRange<LayoutUnit>> horizontalSnapOffsetRanges;
223 HashSet<float> seenVerticalSnapOffsets;
224 HashSet<float> seenHorizontalSnapOffsets;
225 bool hasHorizontalSnapOffsets = scrollSnapType.axis == ScrollSnapAxis::Both || scrollSnapType.axis == ScrollSnapAxis::XAxis || scrollSnapType.axis == ScrollSnapAxis::Inline;
226 bool hasVerticalSnapOffsets = scrollSnapType.axis == ScrollSnapAxis::Both || scrollSnapType.axis == ScrollSnapAxis::YAxis || scrollSnapType.axis == ScrollSnapAxis::Block;
227 auto maxScrollLeft = scrollingElementBox.scrollWidth() - scrollingElementBox.contentWidth();
228 auto maxScrollTop = scrollingElementBox.scrollHeight() - scrollingElementBox.contentHeight();
229 LayoutPoint containerScrollOffset(scrollingElementBox.scrollLeft(), scrollingElementBox.scrollTop());
230
231 // The bounds of the scrolling container's snap port, where the top left of the scrolling container's border box is the origin.
232 auto scrollSnapPort = computeScrollSnapPortOrAreaRect(scrollingElementBox.paddingBoxRect(), scrollingElementStyle.scrollPadding(), InsetOrOutset::Inset);
233#if !LOG_DISABLED
234 LOG(Scrolling, "Computing scroll snap offsets in snap port: %s", snapPortOrAreaToString(scrollSnapPort).utf8().data());
235#endif
236 for (auto* child : scrollContainer->view().boxesWithScrollSnapPositions()) {
237 if (child->enclosingScrollableContainerForSnapping() != scrollContainer)
238 continue;
239
240 // The bounds of the child element's snap area, where the top left of the scrolling container's border box is the origin.
241 // The snap area is the bounding box of the child element's border box, after applying transformations.
242 auto scrollSnapArea = LayoutRect(child->localToContainerQuad(FloatQuad(child->borderBoundingBox()), scrollingElement.renderBox()).boundingBox());
243 scrollSnapArea.moveBy(containerScrollOffset);
244 scrollSnapArea = computeScrollSnapPortOrAreaRect(scrollSnapArea, child->style().scrollSnapMargin(), InsetOrOutset::Outset);
245#if !LOG_DISABLED
246 LOG(Scrolling, " Considering scroll snap area: %s", snapPortOrAreaToString(scrollSnapArea).utf8().data());
247#endif
248 auto alignment = child->style().scrollSnapAlign();
249 if (hasHorizontalSnapOffsets && alignment.x != ScrollSnapAxisAlignType::None) {
250 auto absoluteScrollOffset = clampTo<LayoutUnit>(computeScrollSnapAlignOffset(scrollSnapArea.x(), scrollSnapArea.width(), alignment.x) - computeScrollSnapAlignOffset(scrollSnapPort.x(), scrollSnapPort.width(), alignment.x), 0, maxScrollLeft);
251 if (!seenHorizontalSnapOffsets.contains(absoluteScrollOffset)) {
252 seenHorizontalSnapOffsets.add(absoluteScrollOffset);
253 horizontalSnapOffsets.append(absoluteScrollOffset);
254 }
255 }
256 if (hasVerticalSnapOffsets && alignment.y != ScrollSnapAxisAlignType::None) {
257 auto absoluteScrollOffset = clampTo<LayoutUnit>(computeScrollSnapAlignOffset(scrollSnapArea.y(), scrollSnapArea.height(), alignment.y) - computeScrollSnapAlignOffset(scrollSnapPort.y(), scrollSnapPort.height(), alignment.y), 0, maxScrollTop);
258 if (!seenVerticalSnapOffsets.contains(absoluteScrollOffset)) {
259 seenVerticalSnapOffsets.add(absoluteScrollOffset);
260 verticalSnapOffsets.append(absoluteScrollOffset);
261 }
262 }
263 }
264
265 if (!horizontalSnapOffsets.isEmpty()) {
266 adjustAxisSnapOffsetsForScrollExtent(horizontalSnapOffsets, maxScrollLeft);
267#if !LOG_DISABLED
268 LOG(Scrolling, " => Computed horizontal scroll snap offsets: %s", snapOffsetsToString(horizontalSnapOffsets).utf8().data());
269 LOG(Scrolling, " => Computed horizontal scroll snap offset ranges: %s", snapOffsetRangesToString(horizontalSnapOffsetRanges).utf8().data());
270#endif
271 if (scrollSnapType.strictness == ScrollSnapStrictness::Proximity)
272 computeAxisProximitySnapOffsetRanges(horizontalSnapOffsets, horizontalSnapOffsetRanges, scrollSnapPort.width());
273
274 scrollableArea.setHorizontalSnapOffsets(horizontalSnapOffsets);
275 scrollableArea.setHorizontalSnapOffsetRanges(horizontalSnapOffsetRanges);
276 } else
277 scrollableArea.clearHorizontalSnapOffsets();
278
279 if (!verticalSnapOffsets.isEmpty()) {
280 adjustAxisSnapOffsetsForScrollExtent(verticalSnapOffsets, maxScrollTop);
281#if !LOG_DISABLED
282 LOG(Scrolling, " => Computed vertical scroll snap offsets: %s", snapOffsetsToString(verticalSnapOffsets).utf8().data());
283 LOG(Scrolling, " => Computed vertical scroll snap offset ranges: %s", snapOffsetRangesToString(verticalSnapOffsetRanges).utf8().data());
284#endif
285 if (scrollSnapType.strictness == ScrollSnapStrictness::Proximity)
286 computeAxisProximitySnapOffsetRanges(verticalSnapOffsets, verticalSnapOffsetRanges, scrollSnapPort.height());
287
288 scrollableArea.setVerticalSnapOffsets(verticalSnapOffsets);
289 scrollableArea.setVerticalSnapOffsetRanges(verticalSnapOffsetRanges);
290 } else
291 scrollableArea.clearVerticalSnapOffsets();
292}
293
294template <typename LayoutType>
295LayoutType closestSnapOffset(const Vector<LayoutType>& snapOffsets, const Vector<ScrollOffsetRange<LayoutType>>& snapOffsetRanges, LayoutType scrollDestination, float velocity, unsigned& activeSnapIndex)
296{
297 ASSERT(snapOffsets.size());
298 activeSnapIndex = 0;
299
300 unsigned lowerSnapOffsetRangeIndex;
301 unsigned upperSnapOffsetRangeIndex;
302 indicesOfNearestSnapOffsetRanges<LayoutType>(scrollDestination, snapOffsetRanges, lowerSnapOffsetRangeIndex, upperSnapOffsetRangeIndex);
303 if (lowerSnapOffsetRangeIndex == upperSnapOffsetRangeIndex && upperSnapOffsetRangeIndex != invalidSnapOffsetIndex) {
304 activeSnapIndex = invalidSnapOffsetIndex;
305 return scrollDestination;
306 }
307
308 if (scrollDestination <= snapOffsets.first())
309 return snapOffsets.first();
310
311 activeSnapIndex = snapOffsets.size() - 1;
312 if (scrollDestination >= snapOffsets.last())
313 return snapOffsets.last();
314
315 unsigned lowerIndex;
316 unsigned upperIndex;
317 indicesOfNearestSnapOffsets<LayoutType>(scrollDestination, snapOffsets, lowerIndex, upperIndex);
318 LayoutType lowerSnapPosition = snapOffsets[lowerIndex];
319 LayoutType upperSnapPosition = snapOffsets[upperIndex];
320 if (!std::abs(velocity)) {
321 bool isCloserToLowerSnapPosition = scrollDestination - lowerSnapPosition <= upperSnapPosition - scrollDestination;
322 activeSnapIndex = isCloserToLowerSnapPosition ? lowerIndex : upperIndex;
323 return isCloserToLowerSnapPosition ? lowerSnapPosition : upperSnapPosition;
324 }
325
326 // Non-zero velocity indicates a flick gesture. Even if another snap point is closer, we should choose the one in the direction of the flick gesture
327 // as long as a scroll snap offset range does not lie between the scroll destination and the targeted snap offset.
328 if (velocity < 0) {
329 if (lowerSnapOffsetRangeIndex != invalidSnapOffsetIndex && lowerSnapPosition < snapOffsetRanges[lowerSnapOffsetRangeIndex].end) {
330 activeSnapIndex = upperIndex;
331 return upperSnapPosition;
332 }
333 activeSnapIndex = lowerIndex;
334 return lowerSnapPosition;
335 }
336
337 if (upperSnapOffsetRangeIndex != invalidSnapOffsetIndex && snapOffsetRanges[upperSnapOffsetRangeIndex].start < upperSnapPosition) {
338 activeSnapIndex = lowerIndex;
339 return lowerSnapPosition;
340 }
341 activeSnapIndex = upperIndex;
342 return upperSnapPosition;
343}
344
345LayoutUnit closestSnapOffset(const Vector<LayoutUnit>& snapOffsets, const Vector<ScrollOffsetRange<LayoutUnit>>& snapOffsetRanges, LayoutUnit scrollDestination, float velocity, unsigned& activeSnapIndex)
346{
347 return closestSnapOffset<LayoutUnit>(snapOffsets, snapOffsetRanges, scrollDestination, velocity, activeSnapIndex);
348}
349
350float closestSnapOffset(const Vector<float>& snapOffsets, const Vector<ScrollOffsetRange<float>>& snapOffsetRanges, float scrollDestination, float velocity, unsigned& activeSnapIndex)
351{
352 return closestSnapOffset<float>(snapOffsets, snapOffsetRanges, scrollDestination, velocity, activeSnapIndex);
353}
354
355} // namespace WebCore
356
357#endif // CSS_SCROLL_SNAP
358