Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WebCore / page / scrolling / AxisScrollSnapOffsets.cpp
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
39 #if ENABLE(CSS_SCROLL_SNAP)
40
41 namespace WebCore {
42
43 enum class InsetOrOutset {
44     Inset,
45     Outset
46 };
47
48 static LayoutRect computeScrollSnapPortOrAreaRect(const LayoutRect& rect, const LengthBox& insetOrOutsetBox, InsetOrOutset insetOrOutset)
49 {
50     LayoutBoxExtent extents(valueForLength(insetOrOutsetBox.top(), rect.height()), valueForLength(insetOrOutsetBox.right(), rect.width()), valueForLength(insetOrOutsetBox.bottom(), rect.height()), valueForLength(insetOrOutsetBox.left(), rect.width()));
51     auto snapPortOrArea(rect);
52     if (insetOrOutset == InsetOrOutset::Inset)
53         snapPortOrArea.contract(extents);
54     else
55         snapPortOrArea.expand(extents);
56     return snapPortOrArea;
57 }
58
59 static LayoutUnit computeScrollSnapAlignOffset(const LayoutUnit& leftOrTop, const LayoutUnit& widthOrHeight, ScrollSnapAxisAlignType alignment)
60 {
61     switch (alignment) {
62     case ScrollSnapAxisAlignType::Start:
63         return leftOrTop;
64     case ScrollSnapAxisAlignType::Center:
65         return leftOrTop + widthOrHeight / 2;
66     case ScrollSnapAxisAlignType::End:
67         return leftOrTop + widthOrHeight;
68     default:
69         ASSERT_NOT_REACHED();
70         return 0;
71     }
72 }
73
74 #if !LOG_DISABLED
75
76 static String snapOffsetsToString(const Vector<LayoutUnit>& snapOffsets)
77 {
78     StringBuilder s;
79     s.append("[ ");
80     for (auto offset : snapOffsets)
81         s.append(String::format("%.1f ", offset.toFloat()));
82
83     s.append("]");
84     return s.toString();
85 }
86
87 static String snapOffsetRangesToString(const Vector<ScrollOffsetRange<LayoutUnit>>& ranges)
88 {
89     StringBuilder s;
90     s.append("[ ");
91     for (auto range : ranges)
92         s.append(String::format("(%.1f, %.1f) ", range.start.toFloat(), range.end.toFloat()));
93     s.append("]");
94     return s.toString();
95 }
96
97 static String snapPortOrAreaToString(const LayoutRect& rect)
98 {
99     return String::format("{{%.1f, %.1f} {%.1f, %.1f}}", rect.x().toFloat(), rect.y().toFloat(), rect.width().toFloat(), rect.height().toFloat());
100 }
101
102 #endif
103
104 template <typename LayoutType>
105 static void indicesOfNearestSnapOffsetRanges(LayoutType offset, const Vector<ScrollOffsetRange<LayoutType>>& snapOffsetRanges, unsigned& lowerIndex, unsigned& upperIndex)
106 {
107     if (snapOffsetRanges.isEmpty()) {
108         lowerIndex = invalidSnapOffsetIndex;
109         upperIndex = invalidSnapOffsetIndex;
110         return;
111     }
112
113     int lowerIndexAsInt = -1;
114     int upperIndexAsInt = snapOffsetRanges.size();
115     do {
116         int middleIndex = (lowerIndexAsInt + upperIndexAsInt) / 2;
117         auto& range = snapOffsetRanges[middleIndex];
118         if (range.start < offset && offset < range.end) {
119             lowerIndexAsInt = middleIndex;
120             upperIndexAsInt = middleIndex;
121             break;
122         }
123
124         if (offset > range.end)
125             lowerIndexAsInt = middleIndex;
126         else
127             upperIndexAsInt = middleIndex;
128     } while (lowerIndexAsInt < upperIndexAsInt - 1);
129
130     if (offset <= snapOffsetRanges.first().start)
131         lowerIndex = invalidSnapOffsetIndex;
132     else
133         lowerIndex = lowerIndexAsInt;
134
135     if (offset >= snapOffsetRanges.last().end)
136         upperIndex = invalidSnapOffsetIndex;
137     else
138         upperIndex = upperIndexAsInt;
139 }
140
141 template <typename LayoutType>
142 static void indicesOfNearestSnapOffsets(LayoutType offset, const Vector<LayoutType>& snapOffsets, unsigned& lowerIndex, unsigned& upperIndex)
143 {
144     lowerIndex = 0;
145     upperIndex = snapOffsets.size() - 1;
146     while (lowerIndex < upperIndex - 1) {
147         int middleIndex = (lowerIndex + upperIndex) / 2;
148         auto middleOffset = snapOffsets[middleIndex];
149         if (offset == middleOffset) {
150             upperIndex = middleIndex;
151             lowerIndex = middleIndex;
152             break;
153         }
154
155         if (offset > middleOffset)
156             lowerIndex = middleIndex;
157         else
158             upperIndex = middleIndex;
159     }
160 }
161
162 static void adjustAxisSnapOffsetsForScrollExtent(Vector<LayoutUnit>& snapOffsets, float maxScrollExtent)
163 {
164     if (snapOffsets.isEmpty())
165         return;
166
167     std::sort(snapOffsets.begin(), snapOffsets.end());
168     if (snapOffsets.last() != maxScrollExtent)
169         snapOffsets.append(maxScrollExtent);
170     if (snapOffsets.first())
171         snapOffsets.insert(0, 0);
172 }
173
174 static void computeAxisProximitySnapOffsetRanges(const Vector<LayoutUnit>& snapOffsets, Vector<ScrollOffsetRange<LayoutUnit>>& offsetRanges, LayoutUnit scrollPortAxisLength)
175 {
176     // This is an arbitrary choice for what it means to be "in proximity" of a snap offset. We should play around with
177     // this and see what feels best.
178     static const float ratioOfScrollPortAxisLengthToBeConsideredForProximity = 0.3;
179     if (snapOffsets.size() < 2)
180         return;
181
182     // The extra rule accounting for scroll offset ranges in between the scroll destination and a potential snap offset
183     // handles the corner case where the user scrolls with momentum very lightly away from a snap offset, such that the
184     // predicted scroll destination is still within proximity of the snap offset. In this case, the regular (mandatory
185     // scroll snapping) behavior would be to snap to the next offset in the direction of momentum scrolling, but
186     // instead, it is more intuitive to either return to the original snap position (which we arbitrarily choose here)
187     // or scroll just outside of the snap offset range. This is another minor behavior tweak that we should play around
188     // with to see what feels best.
189     LayoutUnit proximityDistance = ratioOfScrollPortAxisLengthToBeConsideredForProximity * scrollPortAxisLength;
190     for (size_t index = 1; index < snapOffsets.size(); ++index) {
191         auto startOffset = snapOffsets[index - 1] + proximityDistance;
192         auto endOffset = snapOffsets[index] - proximityDistance;
193         if (startOffset < endOffset)
194             offsetRanges.append({ startOffset, endOffset });
195     }
196 }
197
198 void updateSnapOffsetsForScrollableArea(ScrollableArea& scrollableArea, HTMLElement& scrollingElement, const RenderBox& scrollingElementBox, const RenderStyle& scrollingElementStyle)
199 {
200     auto* scrollContainer = scrollingElement.renderer();
201     auto scrollSnapType = scrollingElementStyle.scrollSnapType();
202     if (!scrollContainer || scrollSnapType.strictness == ScrollSnapStrictness::None || scrollContainer->view().boxesWithScrollSnapPositions().isEmpty()) {
203         scrollableArea.clearHorizontalSnapOffsets();
204         scrollableArea.clearVerticalSnapOffsets();
205         return;
206     }
207
208     Vector<LayoutUnit> verticalSnapOffsets;
209     Vector<LayoutUnit> horizontalSnapOffsets;
210     Vector<ScrollOffsetRange<LayoutUnit>> verticalSnapOffsetRanges;
211     Vector<ScrollOffsetRange<LayoutUnit>> horizontalSnapOffsetRanges;
212     HashSet<float> seenVerticalSnapOffsets;
213     HashSet<float> seenHorizontalSnapOffsets;
214     bool hasHorizontalSnapOffsets = scrollSnapType.axis == ScrollSnapAxis::Both || scrollSnapType.axis == ScrollSnapAxis::XAxis || scrollSnapType.axis == ScrollSnapAxis::Inline;
215     bool hasVerticalSnapOffsets = scrollSnapType.axis == ScrollSnapAxis::Both || scrollSnapType.axis == ScrollSnapAxis::YAxis || scrollSnapType.axis == ScrollSnapAxis::Block;
216     auto maxScrollLeft = scrollingElementBox.scrollWidth() - scrollingElementBox.contentWidth();
217     auto maxScrollTop = scrollingElementBox.scrollHeight() - scrollingElementBox.contentHeight();
218     LayoutPoint containerScrollOffset(scrollingElementBox.scrollLeft(), scrollingElementBox.scrollTop());
219
220     // The bounds of the scrolling container's snap port, where the top left of the scrolling container's border box is the origin.
221     auto scrollSnapPort = computeScrollSnapPortOrAreaRect(scrollingElementBox.paddingBoxRect(), scrollingElementStyle.scrollPadding(), InsetOrOutset::Inset);
222 #if !LOG_DISABLED
223     LOG(Scrolling, "Computing scroll snap offsets in snap port: %s", snapPortOrAreaToString(scrollSnapPort).utf8().data());
224 #endif
225     for (auto* child : scrollContainer->view().boxesWithScrollSnapPositions()) {
226         if (child->findEnclosingScrollableContainer() != scrollContainer)
227             continue;
228
229         // The bounds of the child element's snap area, where the top left of the scrolling container's border box is the origin.
230         // The snap area is the bounding box of the child element's border box, after applying transformations.
231         auto scrollSnapArea = LayoutRect(child->localToContainerQuad(FloatQuad(child->borderBoundingBox()), scrollingElement.renderBox()).boundingBox());
232         scrollSnapArea.moveBy(containerScrollOffset);
233         scrollSnapArea = computeScrollSnapPortOrAreaRect(scrollSnapArea, child->style().scrollSnapMargin(), InsetOrOutset::Outset);
234 #if !LOG_DISABLED
235         LOG(Scrolling, "    Considering scroll snap area: %s", snapPortOrAreaToString(scrollSnapArea).utf8().data());
236 #endif
237         auto alignment = child->style().scrollSnapAlign();
238         if (hasHorizontalSnapOffsets && alignment.x != ScrollSnapAxisAlignType::None) {
239             auto absoluteScrollOffset = clampTo<LayoutUnit>(computeScrollSnapAlignOffset(scrollSnapArea.x(), scrollSnapArea.width(), alignment.x) - computeScrollSnapAlignOffset(scrollSnapPort.x(), scrollSnapPort.width(), alignment.x), 0, maxScrollLeft);
240             if (!seenHorizontalSnapOffsets.contains(absoluteScrollOffset)) {
241                 seenHorizontalSnapOffsets.add(absoluteScrollOffset);
242                 horizontalSnapOffsets.append(absoluteScrollOffset);
243             }
244         }
245         if (hasVerticalSnapOffsets && alignment.y != ScrollSnapAxisAlignType::None) {
246             auto absoluteScrollOffset = clampTo<LayoutUnit>(computeScrollSnapAlignOffset(scrollSnapArea.y(), scrollSnapArea.height(), alignment.y) - computeScrollSnapAlignOffset(scrollSnapPort.y(), scrollSnapPort.height(), alignment.y), 0, maxScrollTop);
247             if (!seenVerticalSnapOffsets.contains(absoluteScrollOffset)) {
248                 seenVerticalSnapOffsets.add(absoluteScrollOffset);
249                 verticalSnapOffsets.append(absoluteScrollOffset);
250             }
251         }
252     }
253
254     if (!horizontalSnapOffsets.isEmpty()) {
255         adjustAxisSnapOffsetsForScrollExtent(horizontalSnapOffsets, maxScrollLeft);
256 #if !LOG_DISABLED
257         LOG(Scrolling, " => Computed horizontal scroll snap offsets: %s", snapOffsetsToString(horizontalSnapOffsets).utf8().data());
258         LOG(Scrolling, " => Computed horizontal scroll snap offset ranges: %s", snapOffsetRangesToString(horizontalSnapOffsetRanges).utf8().data());
259 #endif
260         if (scrollSnapType.strictness == ScrollSnapStrictness::Proximity)
261             computeAxisProximitySnapOffsetRanges(horizontalSnapOffsets, horizontalSnapOffsetRanges, scrollSnapPort.width());
262
263         scrollableArea.setHorizontalSnapOffsets(horizontalSnapOffsets);
264         scrollableArea.setHorizontalSnapOffsetRanges(horizontalSnapOffsetRanges);
265     } else
266         scrollableArea.clearHorizontalSnapOffsets();
267
268     if (!verticalSnapOffsets.isEmpty()) {
269         adjustAxisSnapOffsetsForScrollExtent(verticalSnapOffsets, maxScrollTop);
270 #if !LOG_DISABLED
271         LOG(Scrolling, " => Computed vertical scroll snap offsets: %s", snapOffsetsToString(verticalSnapOffsets).utf8().data());
272         LOG(Scrolling, " => Computed vertical scroll snap offset ranges: %s", snapOffsetRangesToString(verticalSnapOffsetRanges).utf8().data());
273 #endif
274         if (scrollSnapType.strictness == ScrollSnapStrictness::Proximity)
275             computeAxisProximitySnapOffsetRanges(verticalSnapOffsets, verticalSnapOffsetRanges, scrollSnapPort.height());
276
277         scrollableArea.setVerticalSnapOffsets(verticalSnapOffsets);
278         scrollableArea.setVerticalSnapOffsetRanges(verticalSnapOffsetRanges);
279     } else
280         scrollableArea.clearVerticalSnapOffsets();
281 }
282
283 template <typename LayoutType>
284 LayoutType closestSnapOffset(const Vector<LayoutType>& snapOffsets, const Vector<ScrollOffsetRange<LayoutType>>& snapOffsetRanges, LayoutType scrollDestination, float velocity, unsigned& activeSnapIndex)
285 {
286     ASSERT(snapOffsets.size());
287     activeSnapIndex = 0;
288
289     unsigned lowerSnapOffsetRangeIndex;
290     unsigned upperSnapOffsetRangeIndex;
291     indicesOfNearestSnapOffsetRanges<LayoutType>(scrollDestination, snapOffsetRanges, lowerSnapOffsetRangeIndex, upperSnapOffsetRangeIndex);
292     if (lowerSnapOffsetRangeIndex == upperSnapOffsetRangeIndex && upperSnapOffsetRangeIndex != invalidSnapOffsetIndex) {
293         activeSnapIndex = invalidSnapOffsetIndex;
294         return scrollDestination;
295     }
296
297     if (scrollDestination <= snapOffsets.first())
298         return snapOffsets.first();
299
300     activeSnapIndex = snapOffsets.size() - 1;
301     if (scrollDestination >= snapOffsets.last())
302         return snapOffsets.last();
303
304     unsigned lowerIndex;
305     unsigned upperIndex;
306     indicesOfNearestSnapOffsets<LayoutType>(scrollDestination, snapOffsets, lowerIndex, upperIndex);
307     LayoutType lowerSnapPosition = snapOffsets[lowerIndex];
308     LayoutType upperSnapPosition = snapOffsets[upperIndex];
309     if (!std::abs(velocity)) {
310         bool isCloserToLowerSnapPosition = scrollDestination - lowerSnapPosition <= upperSnapPosition - scrollDestination;
311         activeSnapIndex = isCloserToLowerSnapPosition ? lowerIndex : upperIndex;
312         return isCloserToLowerSnapPosition ? lowerSnapPosition : upperSnapPosition;
313     }
314
315     // 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
316     // as long as a scroll snap offset range does not lie between the scroll destination and the targeted snap offset.
317     if (velocity < 0) {
318         if (lowerSnapOffsetRangeIndex != invalidSnapOffsetIndex && lowerSnapPosition < snapOffsetRanges[lowerSnapOffsetRangeIndex].end) {
319             activeSnapIndex = upperIndex;
320             return upperSnapPosition;
321         }
322         activeSnapIndex = lowerIndex;
323         return lowerSnapPosition;
324     }
325
326     if (upperSnapOffsetRangeIndex != invalidSnapOffsetIndex && snapOffsetRanges[upperSnapOffsetRangeIndex].start < upperSnapPosition) {
327         activeSnapIndex = lowerIndex;
328         return lowerSnapPosition;
329     }
330     activeSnapIndex = upperIndex;
331     return upperSnapPosition;
332 }
333
334 LayoutUnit closestSnapOffset(const Vector<LayoutUnit>& snapOffsets, const Vector<ScrollOffsetRange<LayoutUnit>>& snapOffsetRanges, LayoutUnit scrollDestination, float velocity, unsigned& activeSnapIndex)
335 {
336     return closestSnapOffset<LayoutUnit>(snapOffsets, snapOffsetRanges, scrollDestination, velocity, activeSnapIndex);
337 }
338
339 float closestSnapOffset(const Vector<float>& snapOffsets, const Vector<ScrollOffsetRange<float>>& snapOffsetRanges, float scrollDestination, float velocity, unsigned& activeSnapIndex)
340 {
341     return closestSnapOffset<float>(snapOffsets, snapOffsetRanges, scrollDestination, velocity, activeSnapIndex);
342 }
343
344 } // namespace WebCore
345
346 #endif // CSS_SCROLL_SNAP