Attachment #432244 for bug #227062

View Details Raw Unified Return to Bug 227062

| Differences between



2021-06-24  Martin Robinson  <mrobinson@webkit.org>

        [css-scroll-snap] Simplify snap point selection helpers
        https://bugs.webkit.org/show_bug.cgi?id=227062

        Reviewed by Frédéric Wang.

        Combine indicesOfNearestSnapOffsets and findFirstSnapStopOffsetBetweenOriginAndDestination
        and have the helper return the geometric previous and next snap points. This makes the
        code a bit easier to read, slightly more efficient, and prepares for looking at
        the geometric previous and next snap points for certain upcoming CSS Scroll Snap features.

        Previously, indicesOfNearestSnapOffsets used a binary search and findFirstSnapStopOffsetBetweenOriginAndDestination
        used a linear search. This change replaces these two functions with a single linear search.
        While findFirstSnapStopOffsetBetweenOriginAndDestination is only called for directional scrolling,
        directional scrolling is more common than non-directional scrolling (which is typically only called
        by scrollIntoView() and other JS scrolling APIs). I have tested this change with a large table of
        of snap points and performance does not seem to be changed. In addition, a future change should mean
        that this searchForPotentialSnapPoints should be called much less.

        No new tests. This should not change behavior in any way.

        * page/scrolling/ScrollSnapOffsetsInfo.cpp:
        (WebCore::searchForPotentialSnapPoints): Added this new helper which is the combination
        of indicesOfNearestSnapOffsets and findFirstSnapStopOffsetBetweenOriginAndDestination.
        (WebCore::closestSnapOffsetWithInfoAndAxis): Use the new helper.

2021-06-23  Jean-Yves Avenard  <jya@apple.com>

        Not all uses of AudioToolbox framework use soft linking




namespace WebCore {

template <typename UnitType>
struct PotentialSnapPointSearchResult {
    std::optional<std::pair<UnitType, unsigned>> previous;
    std::optional<std::pair<UnitType, unsigned>> next;
    std::optional<std::pair<UnitType, unsigned>> snapStop;
};
        int middleIndex = (lowerIndex + upperIndex) / 2;
        auto middleOffset = snapOffsets[middleIndex].offset;
        if (offset == middleOffset) {
            upperIndex = middleIndex;
            lowerIndex = middleIndex;
            break;
        }

        if (offset > middleOffset)
            lowerIndex = middleIndex;
        else
            upperIndex = middleIndex;
    }

    return std::make_pair(lowerIndex, upperIndex);
}

template <typename InfoType, typename UnitType>
static PotentialSnapPointSearchResult<UnitType> searchForPotentialSnapPoints(const InfoType& info, ScrollEventAxis axis, UnitType destinationOffset, std::optional<UnitType> originalOffset)
{
    const auto& snapOffsets = info.offsetsForAxis(axis);
    std::optional<std::pair<UnitType, unsigned>> previous, next, exact, snapStop;

    // A particular snap stop is better if it's between the original offset and destination offset and closer original
    // offset than the previously selected snap stop. We always want to stop at the snap stop closest to the original offset.
    auto isBetterSnapStop = [&](UnitType candidate) {
        if (!originalOffset)
            return false;
        auto original = *originalOffset;
        if (candidate <= std::min(destinationOffset, original) || candidate >= std::max(destinationOffset, original))
            return false;
        return !snapStop || std::abs(float { candidate - original }) < std::abs(float { (*snapStop).first - original });
        return (difference > 0 && candidate > mark) || (difference < 0 && candidate < mark);
    };

    for (unsigned i = 0; i < snapOffsets.size(); i++) {
        UnitType potentialSnapOffset = snapOffsets[i].offset;
        if (potentialSnapOffset == destinationOffset)
            exact = std::make_pair(potentialSnapOffset, i);
        else if (potentialSnapOffset < destinationOffset)
            previous = std::make_pair(potentialSnapOffset, i);
        else if (!next && potentialSnapOffset > destinationOffset)
            next = std::make_pair(potentialSnapOffset, i);

        if (snapOffsets[i].stop == ScrollSnapStop::Always && isBetterSnapStop(potentialSnapOffset))
            snapStop = std::make_pair(potentialSnapOffset, i);
    }

    if (exact)
        return { exact, exact, snapStop };
    return { previous, next, snapStop };
}

template <typename InfoType, typename SizeType, typename LayoutType>

    if (snapOffsets.isEmpty())
        return pairForNoSnapping;

    auto [previous, next, snapStop] = searchForPotentialSnapPoints(info, axis, scrollDestinationOffset, originalOffsetForDirectionalSnapping);
    if (snapStop)
        return *snapStop;
    }

    auto viewportLength = axis == ScrollEventAxis::Horizontal ? viewportSize.width() : viewportSize.height();
    auto isNearEnoughToOffsetForProximity = [&](LayoutType candidateSnapOffset) {

        return isNearEnoughToOffsetForProximity(snapOffsets.last().offset) ? std::make_pair(snapOffsets.last().offset, std::make_optional(lastIndex)) : pairForNoSnapping;
    }

    if (previous && !isNearEnoughToOffsetForProximity((*previous).first))
        previous.reset();
    if (next && !isNearEnoughToOffsetForProximity((*next).first))
        next.reset();
    LayoutType upperSnapPosition = snapOffsets[*upperIndex].offset;

    if (!isNearEnoughToOffsetForProximity(lowerSnapPosition)) {
        lowerSnapPosition = scrollDestinationOffset;
        lowerIndex.reset();
    }

    if (!isNearEnoughToOffsetForProximity(upperSnapPosition)) {
        upperSnapPosition = scrollDestinationOffset;
        upperIndex.reset();

    if (originalOffsetForDirectionalSnapping) {
        // From https://www.w3.org/TR/css-scroll-snap-1/#choosing
        // "User agents must ensure that a user can “escape” a snap position, regardless of the scroll
        // method. For example, if the snap type is mandatory and the next snap position is more than
        // two screen-widths away, a naïve “always snap to nearest” selection algorithm might “trap” the
        //
        // For a directional scroll, we never snap back to the original scroll position or before it,
        // always preferring the snap offset in the scroll direction.
        auto& originalOffset = *originalOffsetForDirectionalSnapping;
        if (originalOffset < scrollDestinationOffset && previous && (*previous).first <= originalOffset)
            previous.reset();
        if (originalOffset > scrollDestinationOffset && next && (*next).first >= originalOffset)
            next.reset();
    }

    if (!previous && !next)
        return pairForNoSnapping;
    if (!previous)
        return *next;
    if (!next)
        return *previous;

    // If this scroll isn't directional, then choose whatever snap point is closer, otherwise pick the offset in the scroll direction.
    if (!std::abs(velocity))
        return (scrollDestinationOffset - (*previous).first) <= ((*next).first - scrollDestinationOffset) ? *previous : *next;
    return velocity < 0 ? *previous : *next;
            return std::make_pair(upperSnapPosition, upperIndex);
        return std::make_pair(lowerSnapPosition, lowerIndex);
    }

    if (lowerIndex && (!originalOffsetForDirectionalSnapping || *originalOffsetForDirectionalSnapping < lowerSnapPosition))
        return std::make_pair(lowerSnapPosition, lowerIndex);
    return std::make_pair(upperSnapPosition, upperIndex);
}

enum class InsetOrOutset {

Return to Bug 227062

Lines 42-99 a/Source/WebCore/page/scrolling/ScrollSnapOffsetsInfo.cpp_sec1
- a/Source/WebCore/page/scrolling/ScrollSnapOffsetsInfo.cpp -82 / +65 lines
42		42
43	namespace WebCore {	43	namespace WebCore {
44		44
45	template <typename LayoutType>	45	template <typename UnitType>
46	static std::pair<std::optional<unsigned>, std::optional<unsigned>> indicesOfNearestSnapOffsets(LayoutType offset, const Vector<SnapOffset<LayoutType>>& snapOffsets)	46	struct PotentialSnapPointSearchResult {
47	{	47	std::optional<std::pair<UnitType, unsigned>> previous;
48	unsigned lowerIndex = 0;	48	std::optional<std::pair<UnitType, unsigned>> next;
49	unsigned upperIndex = snapOffsets.size() - 1;	49	std::optional<std::pair<UnitType, unsigned>> snapStop;
50	while (lowerIndex < upperIndex - 1) {	50	};
51	int middleIndex = (lowerIndex + upperIndex) / 2;
52	auto middleOffset = snapOffsets[middleIndex].offset;
53	if (offset == middleOffset) {
54	upperIndex = middleIndex;
55	lowerIndex = middleIndex;
56	break;
57	}
58
59	if (offset > middleOffset)
60	lowerIndex = middleIndex;
61	else
62	upperIndex = middleIndex;
63	}
64
65	return std::make_pair(lowerIndex, upperIndex);
66	}
67		51
68	template <typename LayoutType>	52	template <typename InfoType, typename UnitType>
69	static std::optional<unsigned> findFirstSnapStopOffsetBetweenOriginAndDestination(const Vector<SnapOffset<LayoutType>>& snapOffsets, LayoutType scrollOriginOffset, LayoutType scrollDestinationOffset)	53	static PotentialSnapPointSearchResult<UnitType> searchForPotentialSnapPoints(const InfoType& info, ScrollEventAxis axis, UnitType destinationOffset, std::optional<UnitType> originalOffset)
70	{	54	{
71	LayoutType difference = scrollDestinationOffset - scrollOriginOffset;	55	const auto& snapOffsets = info.offsetsForAxis(axis);
72	if (!difference)	56	std::optional<std::pair<UnitType, unsigned>> previous, next, exact, snapStop;
73	return std::nullopt;	57
74		58	// A particular snap stop is better if it's between the original offset and destination offset and closer original
75	unsigned searchStartOffset = 0;	59	// offset than the previously selected snap stop. We always want to stop at the snap stop closest to the original offset.
76	size_t iteration = 1;	60	auto isBetterSnapStop = [&](UnitType candidate) {
77	if (difference < 0) {	61	if (!originalOffset)
78	searchStartOffset = snapOffsets.size() - 1;	62	return false;
79	iteration = -1;	63	auto original = *originalOffset;
80	}	64	if (candidate <= std::min(destinationOffset, original) \|\| candidate >= std::max(destinationOffset, original))
81		65	return false;
82	auto isPast = [difference](LayoutType mark, LayoutType candidate) {	66	return !snapStop \|\| std::abs(float { candidate - original }) < std::abs(float { (*snapStop).first - original });
83	return (difference > 0 && candidate > mark) \|\| (difference < 0 && candidate < mark);
84	};	67	};
85		68
86	for (int i = searchStartOffset; i >= 0 && static_cast<size_t>(i) < snapOffsets.size(); i += iteration) {	69	for (unsigned i = 0; i < snapOffsets.size(); i++) {
87	auto offset = snapOffsets[i].offset;	70	UnitType potentialSnapOffset = snapOffsets[i].offset;
88	if (isPast(scrollDestinationOffset, offset))	71	if (potentialSnapOffset == destinationOffset)
89	break;	72	exact = std::make_pair(potentialSnapOffset, i);
90	if (snapOffsets[i].stop != ScrollSnapStop::Always)	73	else if (potentialSnapOffset < destinationOffset)
91	continue;	74	previous = std::make_pair(potentialSnapOffset, i);
92	if (isPast(scrollOriginOffset, offset))	75	else if (!next && potentialSnapOffset > destinationOffset)
93	return i;	76	next = std::make_pair(potentialSnapOffset, i);
		77
		78	if (snapOffsets[i].stop == ScrollSnapStop::Always && isBetterSnapStop(potentialSnapOffset))
		79	snapStop = std::make_pair(potentialSnapOffset, i);
94	}	80	}
95		81
96	return std::nullopt;	82	if (exact)
		83	return { exact, exact, snapStop };
		84	return { previous, next, snapStop };
97	}	85	}
98		86
99	template <typename InfoType, typename SizeType, typename LayoutType>	87	template <typename InfoType, typename SizeType, typename LayoutType>
Lines 104-113 static std::pair<LayoutType, std::optional<unsigned>> closestSnapOffsetWithInfoA a/Source/WebCore/page/scrolling/ScrollSnapOffsetsInfo.cpp_sec2
104	if (snapOffsets.isEmpty())	92	if (snapOffsets.isEmpty())
105	return pairForNoSnapping;	93	return pairForNoSnapping;
106		94
107	if (originalOffsetForDirectionalSnapping) {	95	auto [previous, next, snapStop] = searchForPotentialSnapPoints(info, axis, scrollDestinationOffset, originalOffsetForDirectionalSnapping);
108	if (auto firstSnapStopOffsetIndex = findFirstSnapStopOffsetBetweenOriginAndDestination(snapOffsets, *originalOffsetForDirectionalSnapping, scrollDestinationOffset))	96	if (snapStop)
109	return std::make_pair(snapOffsets[*firstSnapStopOffsetIndex].offset, firstSnapStopOffsetIndex);	97	return *snapStop;
110	}
111		98
112	auto viewportLength = axis == ScrollEventAxis::Horizontal ? viewportSize.width() : viewportSize.height();	99	auto viewportLength = axis == ScrollEventAxis::Horizontal ? viewportSize.width() : viewportSize.height();
113	auto isNearEnoughToOffsetForProximity = [&](LayoutType candidateSnapOffset) {	100	auto isNearEnoughToOffsetForProximity = [&](LayoutType candidateSnapOffset) {
Lines 128-168 static std::pair<LayoutType, std::optional<unsigned>> closestSnapOffsetWithInfoA a/Source/WebCore/page/scrolling/ScrollSnapOffsetsInfo.cpp_sec3
128	return isNearEnoughToOffsetForProximity(snapOffsets.last().offset) ? std::make_pair(snapOffsets.last().offset, std::make_optional(lastIndex)) : pairForNoSnapping;	115	return isNearEnoughToOffsetForProximity(snapOffsets.last().offset) ? std::make_pair(snapOffsets.last().offset, std::make_optional(lastIndex)) : pairForNoSnapping;
129	}	116	}
130		117
131	auto [lowerIndex, upperIndex] = indicesOfNearestSnapOffsets<LayoutType>(scrollDestinationOffset, snapOffsets);	118	if (previous && !isNearEnoughToOffsetForProximity((*previous).first))
132	ASSERT(lowerIndex);	119	previous.reset();
133	ASSERT(upperIndex);	120	if (next && !isNearEnoughToOffsetForProximity((*next).first))
134	LayoutType lowerSnapPosition = snapOffsets[*lowerIndex].offset;	121	next.reset();
135	LayoutType upperSnapPosition = snapOffsets[*upperIndex].offset;
136
137	if (!isNearEnoughToOffsetForProximity(lowerSnapPosition)) {
138	lowerSnapPosition = scrollDestinationOffset;
139	lowerIndex.reset();
140	}
141
142	if (!isNearEnoughToOffsetForProximity(upperSnapPosition)) {
143	upperSnapPosition = scrollDestinationOffset;
144	upperIndex.reset();
145		122
		123	if (originalOffsetForDirectionalSnapping) {
		124	// From https://www.w3.org/TR/css-scroll-snap-1/#choosing
		125	// "User agents must ensure that a user can “escape” a snap position, regardless of the scroll
		126	// method. For example, if the snap type is mandatory and the next snap position is more than
		127	// two screen-widths away, a naïve “always snap to nearest” selection algorithm might “trap” the
		128	//
		129	// For a directional scroll, we never snap back to the original scroll position or before it,
		130	// always preferring the snap offset in the scroll direction.
		131	auto& originalOffset = *originalOffsetForDirectionalSnapping;
		132	if (originalOffset < scrollDestinationOffset && previous && (*previous).first <= originalOffset)
		133	previous.reset();
		134	if (originalOffset > scrollDestinationOffset && next && (*next).first >= originalOffset)
		135	next.reset();
146	}	136	}
147		137
148	if (!std::abs(velocity)) {	138	if (!previous && !next)
149	bool isCloserToLowerSnapPosition = !upperIndex \|\| (lowerIndex && scrollDestinationOffset - lowerSnapPosition <= upperSnapPosition - scrollDestinationOffset);	139	return pairForNoSnapping;
150	return isCloserToLowerSnapPosition ? std::make_pair(lowerSnapPosition, lowerIndex) : std::make_pair(upperSnapPosition, upperIndex);	140	if (!previous)
151	}	141	return *next;
152		142	if (!next)
153	// 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	143	return *previous;
154	// as long as a scroll snap offset is close enough for proximity (or we aren't using proximity). If we are doing directional	144
155	// snapping, we should never snap to a point that was on the other side of the original position in the opposite direction of this scroll.	145	// If this scroll isn't directional, then choose whatever snap point is closer, otherwise pick the offset in the scroll direction.
156	// This allows directional scrolling to escape snap points.	146	if (!std::abs(velocity))
157	if (velocity < 0) {	147	return (scrollDestinationOffset - (previous).first) <= ((next).first - scrollDestinationOffset) ? previous : next;
158	if (upperIndex && (!originalOffsetForDirectionalSnapping \|\| *originalOffsetForDirectionalSnapping > upperSnapPosition))	148	return velocity < 0 ? previous : next;
159	return std::make_pair(upperSnapPosition, upperIndex);
160	return std::make_pair(lowerSnapPosition, lowerIndex);
161	}
162
163	if (lowerIndex && (!originalOffsetForDirectionalSnapping \|\| *originalOffsetForDirectionalSnapping < lowerSnapPosition))
164	return std::make_pair(lowerSnapPosition, lowerIndex);
165	return std::make_pair(upperSnapPosition, upperIndex);
166	}	149	}
167		150
168	enum class InsetOrOutset {	151	enum class InsetOrOutset {

Lines 1-3 a/Source/WebCore/ChangeLog_sec1
- a/Source/WebCore/ChangeLog +27 lines
		1	2021-06-24 Martin Robinson <mrobinson@webkit.org>
		2
		3	[css-scroll-snap] Simplify snap point selection helpers
		4	https://bugs.webkit.org/show_bug.cgi?id=227062
		5
		6	Reviewed by Frédéric Wang.
		7
		8	Combine indicesOfNearestSnapOffsets and findFirstSnapStopOffsetBetweenOriginAndDestination
		9	and have the helper return the geometric previous and next snap points. This makes the
		10	code a bit easier to read, slightly more efficient, and prepares for looking at
		11	the geometric previous and next snap points for certain upcoming CSS Scroll Snap features.
		12
		13	Previously, indicesOfNearestSnapOffsets used a binary search and findFirstSnapStopOffsetBetweenOriginAndDestination
		14	used a linear search. This change replaces these two functions with a single linear search.
		15	While findFirstSnapStopOffsetBetweenOriginAndDestination is only called for directional scrolling,
		16	directional scrolling is more common than non-directional scrolling (which is typically only called
		17	by scrollIntoView() and other JS scrolling APIs). I have tested this change with a large table of
		18	of snap points and performance does not seem to be changed. In addition, a future change should mean
		19	that this searchForPotentialSnapPoints should be called much less.
		20
		21	No new tests. This should not change behavior in any way.
		22
		23	* page/scrolling/ScrollSnapOffsetsInfo.cpp:
		24	(WebCore::searchForPotentialSnapPoints): Added this new helper which is the combination
		25	of indicesOfNearestSnapOffsets and findFirstSnapStopOffsetBetweenOriginAndDestination.
		26	(WebCore::closestSnapOffsetWithInfoAndAxis): Use the new helper.
		27
1	2021-06-23 Jean-Yves Avenard <jya@apple.com>	28	2021-06-23 Jean-Yves Avenard <jya@apple.com>
2		29
3	Not all uses of AudioToolbox framework use soft linking	30	Not all uses of AudioToolbox framework use soft linking