tor-browser

ScrollSnap.cpp (35376B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "ScrollSnap.h"

#include "FrameMetrics.h"
#include "mozilla/ScrollContainerFrame.h"
#include "mozilla/ScrollSnapInfo.h"
#include "mozilla/ServoStyleConsts.h"
#include "mozilla/StaticPrefs_layout.h"
#include "nsIFrame.h"
#include "nsLayoutUtils.h"
#include "nsPresContext.h"
#include "nsTArray.h"

namespace mozilla {

/**
* Keeps track of the current best edge to snap to. The criteria for
* adding an edge depends on the scrolling unit.
*/
class CalcSnapPoints final {
 using SnapTarget = ScrollSnapInfo::SnapTarget;

public:
 CalcSnapPoints(ScrollUnit aUnit, ScrollSnapFlags aSnapFlags,
                const nsPoint& aDestination, const nsPoint& aStartPos);
 struct SnapPosition : public SnapTarget {
   SnapPosition(const SnapTarget& aSnapTarget, nscoord aPosition,
                nscoord aDistanceOnOtherAxis)
       : SnapTarget(aSnapTarget),
         mPosition(aPosition),
         mDistanceOnOtherAxis(aDistanceOnOtherAxis) {}

   nscoord mPosition;
   // The distance from the scroll destination to this snap position on the
   // other axis. This value is used if there are multiple SnapPositions on
   // this axis, but the positions on the other axis are different.
   nscoord mDistanceOnOtherAxis;
 };

 void AddHorizontalEdge(const SnapTarget& aTarget);
 void AddVerticalEdge(const SnapTarget& aTarget);

 struct CandidateTracker {
   // keeps track of the position of the current second best edge on the
   // opposite side of the best edge on this axis.
   // We use NSCoordSaturatingSubtract to calculate the distance between a
   // given position and this second best edge position so that it can be an
   // uninitialized value as the maximum possible value, because the first
   // distance calculation would always be nscoord_MAX.
   nscoord mSecondBestEdge = nscoord_MAX;

   // Assuming in most cases there's no multiple coincide snap points.
   AutoTArray<ScrollSnapTargetId, 1> mTargetIds;
   // keeps track of the positions of the current best edge on this axis.
   // NOTE: Each SnapPosition.mPosition points the same snap position on this
   // axis but other member variables of SnapPosition may have different
   // values.
   AutoTArray<SnapPosition, 1> mBestEdges;
   bool EdgeFound() const { return !mBestEdges.IsEmpty(); }
 };
 void AddEdge(const SnapPosition& aEdge, nscoord aDestination,
              nscoord aStartPos, nscoord aScrollingDirection,
              CandidateTracker* aCandidateTracker);
 SnapDestination GetBestEdge(const nsSize& aSnapportSize) const;
 nscoord XDistanceBetweenBestAndSecondEdge() const {
   return std::abs(NSCoordSaturatingSubtract(
       mTrackerOnX.mSecondBestEdge,
       mTrackerOnX.EdgeFound() ? mTrackerOnX.mBestEdges[0].mPosition
                               : mDestination.x,
       nscoord_MAX));
 }
 nscoord YDistanceBetweenBestAndSecondEdge() const {
   return std::abs(NSCoordSaturatingSubtract(
       mTrackerOnY.mSecondBestEdge,
       mTrackerOnY.EdgeFound() ? mTrackerOnY.mBestEdges[0].mPosition
                               : mDestination.y,
       nscoord_MAX));
 }
 const nsPoint& Destination() const { return mDestination; }

protected:
 ScrollUnit mUnit;
 ScrollSnapFlags mSnapFlags;
 nsPoint mDestination;  // gives the position after scrolling but before
                        // snapping
 nsPoint mStartPos;     // gives the position before scrolling
 nsIntPoint mScrollingDirection;  // always -1, 0, or 1
 CandidateTracker mTrackerOnX;
 CandidateTracker mTrackerOnY;
};

CalcSnapPoints::CalcSnapPoints(ScrollUnit aUnit, ScrollSnapFlags aSnapFlags,
                              const nsPoint& aDestination,
                              const nsPoint& aStartPos)
   : mUnit(aUnit),
     mSnapFlags(aSnapFlags),
     mDestination(aDestination),
     mStartPos(aStartPos) {
 MOZ_ASSERT(aSnapFlags != ScrollSnapFlags::Disabled);

 nsPoint direction = aDestination - aStartPos;
 mScrollingDirection = nsIntPoint(0, 0);
 if (direction.x < 0) {
   mScrollingDirection.x = -1;
 }
 if (direction.x > 0) {
   mScrollingDirection.x = 1;
 }
 if (direction.y < 0) {
   mScrollingDirection.y = -1;
 }
 if (direction.y > 0) {
   mScrollingDirection.y = 1;
 }
}

SnapDestination CalcSnapPoints::GetBestEdge(const nsSize& aSnapportSize) const {
 if (mTrackerOnX.EdgeFound() && mTrackerOnY.EdgeFound()) {
   nsPoint bestCandidate(mTrackerOnX.mBestEdges[0].mPosition,
                         mTrackerOnY.mBestEdges[0].mPosition);
   nsRect snappedPort = nsRect(bestCandidate, aSnapportSize);

   // If we've found the candidates on both axes, it's possible some of
   // candidates will be outside of the snapport if we snap to the point
   // (mTrackerOnX.mBestEdges[0].mPosition,
   // mTrackerOnY.mBestEdges[0].mPosition). So we need to get the intersection
   // of the snap area of each snap target element on each axis and the
   // snapport to tell whether it's outside of the snapport or not.
   //
   // Also if at least either one of the elements will be outside of the
   // snapport if we snap to (mTrackerOnX.mBestEdges[0].mPosition,
   // mTrackerOnY.mBestEdges[0].mPosition). We need to choose one of
   // combinations of the candidates which is closest to the destination.
   //
   // So here we iterate over mTrackerOnX and mTrackerOnY just once
   // respectively for both purposes to avoid iterating over them again and
   // again.
   //
   // NOTE: Ideally we have to iterate over every possible combinations of
   // (mTrackerOnX.mBestEdges[i].mSnapPoint.mY,
   //  mTrackerOnY.mBestEdges[j].mSnapPoint.mX) and tell whether the given
   // combination will be visible in the snapport or not (maybe we should
   // choose the one that the visible area, i.e., the intersection area of
   // the snap target elements and the snapport, is the largest one rather than
   // the closest one?). But it will be inefficient, so here we will not
   // iterate all the combinations, we just iterate all the snap target
   // elements in each axis respectively.

   AutoTArray<ScrollSnapTargetId, 1> visibleTargetIdsOnX;
   nscoord minimumDistanceOnY = nscoord_MAX;
   size_t minimumXIndex = 0;
   AutoTArray<ScrollSnapTargetId, 1> minimumDistanceTargetIdsOnX;
   for (size_t i = 0; i < mTrackerOnX.mBestEdges.Length(); i++) {
     const auto& targetX = mTrackerOnX.mBestEdges[i];
     if (targetX.mSnapArea.Intersects(snappedPort)) {
       visibleTargetIdsOnX.AppendElement(targetX.mTargetId);
     }

     if (targetX.mDistanceOnOtherAxis < minimumDistanceOnY) {
       minimumDistanceOnY = targetX.mDistanceOnOtherAxis;
       minimumXIndex = i;
       minimumDistanceTargetIdsOnX =
           AutoTArray<ScrollSnapTargetId, 1>{targetX.mTargetId};
     } else if (minimumDistanceOnY != nscoord_MAX &&
                targetX.mDistanceOnOtherAxis == minimumDistanceOnY) {
       minimumDistanceTargetIdsOnX.AppendElement(targetX.mTargetId);
     }
   }

   AutoTArray<ScrollSnapTargetId, 1> visibleTargetIdsOnY;
   nscoord minimumDistanceOnX = nscoord_MAX;
   size_t minimumYIndex = 0;
   AutoTArray<ScrollSnapTargetId, 1> minimumDistanceTargetIdsOnY;
   for (size_t i = 0; i < mTrackerOnY.mBestEdges.Length(); i++) {
     const auto& targetY = mTrackerOnY.mBestEdges[i];
     if (targetY.mSnapArea.Intersects(snappedPort)) {
       visibleTargetIdsOnY.AppendElement(targetY.mTargetId);
     }

     if (targetY.mDistanceOnOtherAxis < minimumDistanceOnX) {
       minimumDistanceOnX = targetY.mDistanceOnOtherAxis;
       minimumYIndex = i;
       minimumDistanceTargetIdsOnY =
           AutoTArray<ScrollSnapTargetId, 1>{targetY.mTargetId};
     } else if (minimumDistanceOnX != nscoord_MAX &&
                targetY.mDistanceOnOtherAxis == minimumDistanceOnX) {
       minimumDistanceTargetIdsOnY.AppendElement(targetY.mTargetId);
     }
   }

   // If we have the target ids on both axes, it means the target elements
   // (ids) specifying the best edge on X axis and the target elements
   // specifying the best edge on Y axis are visible if we snap to the best
   // edge. Thus they are valid snap positions.
   if (!visibleTargetIdsOnX.IsEmpty() && !visibleTargetIdsOnY.IsEmpty()) {
     return SnapDestination{
         bestCandidate,
         ScrollSnapTargetIds{visibleTargetIdsOnX, visibleTargetIdsOnY}};
   }

   // Now we've already known that snapping to
   // (mTrackerOnX.mBestEdges[0].mPosition,
   // mTrackerOnY.mBestEdges[0].mPosition) will make all candidates of
   // mTrackerX or mTrackerY (or both) outside of the snapport. We need to
   // choose another combination where candidates of both mTrackerX/Y are
   // inside the snapport.

   // There are three possibilities;
   // 1) There's no candidate on X axis in mTrackerOnY (that means
   //    each candidate's scroll-snap-align is `none` on X axis), but there's
   //    any candidate in mTrackerOnX, the closest candidates of mTrackerOnX
   //    should be used.
   // 2) There's no candidate on Y axis in mTrackerOnX (that means
   //    each candidate's scroll-snap-align is `none` on Y axis), but there's
   //    any candidate in mTrackerOnY, the closest candidates of mTrackerOnY
   //    should be used.
   // 3) There are candidates on both axes. Choosing a combination such as
   //    (mTrackerOnX.mBestEdges[i].mSnapPoint.mX,
   //     mTrackerOnY.mBestEdges[i].mSnapPoint.mY)
   //    would require us to iterate over the candidates again if the
   //    combination position is outside the snapport, which we don't want to
   //    do. Instead, we choose either one of the axis' candidates.
   if ((minimumDistanceOnX == nscoord_MAX) &&
       minimumDistanceOnY != nscoord_MAX) {
     bestCandidate.y = *mTrackerOnX.mBestEdges[minimumXIndex].mSnapPoint.mY;
     return SnapDestination{bestCandidate,
                            ScrollSnapTargetIds{minimumDistanceTargetIdsOnX,
                                                minimumDistanceTargetIdsOnX}};
   }

   if (minimumDistanceOnX != nscoord_MAX &&
       minimumDistanceOnY == nscoord_MAX) {
     bestCandidate.x = *mTrackerOnY.mBestEdges[minimumYIndex].mSnapPoint.mX;
     return SnapDestination{bestCandidate,
                            ScrollSnapTargetIds{minimumDistanceTargetIdsOnY,
                                                minimumDistanceTargetIdsOnY}};
   }

   if (minimumDistanceOnX != nscoord_MAX &&
       minimumDistanceOnY != nscoord_MAX) {
     // If we've found candidates on both axes, choose the closest point either
     // on X axis or Y axis from the scroll destination. I.e. choose
     // `minimumXIndex` one or `minimumYIndex` one to make at least one of
     // snap target elements visible inside the snapport.
     //
     // For example,
     // [bestCandidate.x, mTrackerOnX.mBestEdges[minimumXIndex].mSnapPoint.mY]
     // is a candidate generated from a single element, thus snapping to the
     // point would definitely make the element visible inside the snapport.
     if (hypotf(NSCoordToFloat(mDestination.x -
                               mTrackerOnX.mBestEdges[0].mPosition),
                NSCoordToFloat(minimumDistanceOnY)) <
         hypotf(NSCoordToFloat(minimumDistanceOnX),
                NSCoordToFloat(mDestination.y -
                               mTrackerOnY.mBestEdges[0].mPosition))) {
       bestCandidate.y = *mTrackerOnX.mBestEdges[minimumXIndex].mSnapPoint.mY;
     } else {
       bestCandidate.x = *mTrackerOnY.mBestEdges[minimumYIndex].mSnapPoint.mX;
     }
     return SnapDestination{bestCandidate,
                            ScrollSnapTargetIds{minimumDistanceTargetIdsOnX,
                                                minimumDistanceTargetIdsOnY}};
   }
   MOZ_ASSERT_UNREACHABLE("There's at least one candidate on either axis");
   // `minimumDistanceOnX == nscoord_MAX && minimumDistanceOnY == nscoord_MAX`
   // should not happen but we fall back for safety.
 }

 return SnapDestination{
     nsPoint(
         mTrackerOnX.EdgeFound() ? mTrackerOnX.mBestEdges[0].mPosition
         // In the case of IntendedEndPosition (i.e. the destination point is
         // explicitely specied, e.g. scrollTo) use the destination point if we
         // didn't find any candidates.
         : !(mSnapFlags & ScrollSnapFlags::IntendedDirection) ? mDestination.x
                                                              : mStartPos.x,
         mTrackerOnY.EdgeFound() ? mTrackerOnY.mBestEdges[0].mPosition
         // Same as above X axis case, use the destination point if we didn't
         // find any candidates.
         : !(mSnapFlags & ScrollSnapFlags::IntendedDirection) ? mDestination.y
                                                              : mStartPos.y),
     ScrollSnapTargetIds{mTrackerOnX.mTargetIds, mTrackerOnY.mTargetIds}};
}

void CalcSnapPoints::AddHorizontalEdge(const SnapTarget& aTarget) {
 MOZ_ASSERT(aTarget.mSnapPoint.mY);
 AddEdge(SnapPosition{aTarget, *aTarget.mSnapPoint.mY,
                      aTarget.mSnapPoint.mX
                          ? std::abs(mDestination.x - *aTarget.mSnapPoint.mX)
                          : nscoord_MAX},
         mDestination.y, mStartPos.y, mScrollingDirection.y, &mTrackerOnY);
}

void CalcSnapPoints::AddVerticalEdge(const SnapTarget& aTarget) {
 MOZ_ASSERT(aTarget.mSnapPoint.mX);
 AddEdge(SnapPosition{aTarget, *aTarget.mSnapPoint.mX,
                      aTarget.mSnapPoint.mY
                          ? std::abs(mDestination.y - *aTarget.mSnapPoint.mY)
                          : nscoord_MAX},
         mDestination.x, mStartPos.x, mScrollingDirection.x, &mTrackerOnX);
}

void CalcSnapPoints::AddEdge(const SnapPosition& aEdge, nscoord aDestination,
                            nscoord aStartPos, nscoord aScrollingDirection,
                            CandidateTracker* aCandidateTracker) {
 if (mSnapFlags & ScrollSnapFlags::IntendedDirection) {
   // In the case of intended direction, we only want to snap to points ahead
   // of the direction we are scrolling.
   if (aScrollingDirection == 0 ||
       (aEdge.mPosition - aStartPos) * aScrollingDirection <= 0) {
     // The scroll direction is neutral - will not hit a snap point, or the
     // edge is not in the direction we are scrolling, skip it.
     return;
   }
 }

 if (!aCandidateTracker->EdgeFound()) {
   aCandidateTracker->mBestEdges = AutoTArray<SnapPosition, 1>{aEdge};
   aCandidateTracker->mTargetIds =
       AutoTArray<ScrollSnapTargetId, 1>{aEdge.mTargetId};
   return;
 }

 auto isPreferredStopAlways = [&](const SnapPosition& aSnapPosition) -> bool {
   MOZ_ASSERT(mSnapFlags & ScrollSnapFlags::IntendedDirection);
   // In the case of intended direction scroll operations, `scroll-snap-stop:
   // always` snap points in between the start point and the scroll destination
   // are preferable preferable. In other words any `scroll-snap-stop: always`
   // snap points can be handled as if it's `scroll-snap-stop: normal`.
   return aSnapPosition.mScrollSnapStop == StyleScrollSnapStop::Always &&
          std::abs(aSnapPosition.mPosition - aStartPos) <
              std::abs(aDestination - aStartPos);
 };

 const bool isOnOppositeSide =
     ((aEdge.mPosition - aDestination) > 0) !=
     ((aCandidateTracker->mBestEdges[0].mPosition - aDestination) > 0);
 const nscoord distanceFromStart = aEdge.mPosition - aStartPos;
 // A utility function to update the best and the second best edges in the
 // given conditions.
 // |aIsCloserThanBest| True if the current candidate is closer than the best
 // edge.
 // |aIsCloserThanSecond| True if the current candidate is closer than
 // the second best edge.
 const nscoord distanceFromDestination = aEdge.mPosition - aDestination;
 auto updateBestEdges = [&](bool aIsCloserThanBest, bool aIsCloserThanSecond) {
   if (aIsCloserThanBest) {
     if (mSnapFlags & ScrollSnapFlags::IntendedDirection &&
         isPreferredStopAlways(aEdge)) {
       // In the case of intended direction scroll operations and the new best
       // candidate is `scroll-snap-stop: always` and if it's closer to the
       // start position than the destination, thus we won't use the second
       // best edge since even if the snap port of the best edge covers entire
       // snapport, the `scroll-snap-stop: always` snap point is preferred than
       // any points.
       // NOTE: We've already ignored snap points behind start points so that
       // we can use std::abs here in the comparison.
       //
       // For example, if there's a `scroll-snap-stop: always` in between the
       // start point and destination, no `snap-overflow` mechanism should
       // happen, if there's `scroll-snap-stop: always` further than the
       // destination, `snap-overflow` might happen something like below
       // diagram.
       // start        always    dest   other always
       //   |------------|---------|------|
       aCandidateTracker->mSecondBestEdge = aEdge.mPosition;
     } else if (isOnOppositeSide) {
       // Replace the second best edge with the current best edge only if the
       // new best edge (aEdge) is on the opposite side of the current best
       // edge.
       aCandidateTracker->mSecondBestEdge =
           aCandidateTracker->mBestEdges[0].mPosition;
     }
     aCandidateTracker->mBestEdges = AutoTArray<SnapPosition, 1>{aEdge};
     aCandidateTracker->mTargetIds =
         AutoTArray<ScrollSnapTargetId, 1>{aEdge.mTargetId};
   } else {
     if (aEdge.mPosition == aCandidateTracker->mBestEdges[0].mPosition) {
       aCandidateTracker->mTargetIds.AppendElement(aEdge.mTargetId);
       aCandidateTracker->mBestEdges.AppendElement(aEdge);
     }
     if (aIsCloserThanSecond && isOnOppositeSide) {
       aCandidateTracker->mSecondBestEdge = aEdge.mPosition;
     }
   }
 };

 bool isCandidateOfBest = false;
 bool isCandidateOfSecondBest = false;
 switch (mUnit) {
   case ScrollUnit::DEVICE_PIXELS:
   case ScrollUnit::LINES:
   case ScrollUnit::WHOLE: {
     isCandidateOfBest =
         std::abs(distanceFromDestination) <
         std::abs(aCandidateTracker->mBestEdges[0].mPosition - aDestination);
     isCandidateOfSecondBest =
         std::abs(distanceFromDestination) <
         std::abs(NSCoordSaturatingSubtract(aCandidateTracker->mSecondBestEdge,
                                            aDestination, nscoord_MAX));
     break;
   }
   case ScrollUnit::PAGES: {
     // distance to the edge from the scrolling destination in the direction of
     // scrolling
     nscoord overshoot = distanceFromDestination * aScrollingDirection;
     // distance to the current best edge from the scrolling destination in the
     // direction of scrolling
     nscoord curOvershoot =
         (aCandidateTracker->mBestEdges[0].mPosition - aDestination) *
         aScrollingDirection;

     nscoord secondOvershoot =
         NSCoordSaturatingSubtract(aCandidateTracker->mSecondBestEdge,
                                   aDestination, nscoord_MAX) *
         aScrollingDirection;

     // edges between the current position and the scrolling destination are
     // favoured to preserve context
     if (overshoot < 0) {
       isCandidateOfBest = overshoot > curOvershoot || curOvershoot >= 0;
       isCandidateOfSecondBest =
           overshoot > secondOvershoot || secondOvershoot >= 0;
     }
     // if there are no edges between the current position and the scrolling
     // destination the closest edge beyond the destination is used
     if (overshoot > 0) {
       isCandidateOfBest = overshoot < curOvershoot;
       isCandidateOfSecondBest = overshoot < secondOvershoot;
     }
   }
 }

 if (mSnapFlags & ScrollSnapFlags::IntendedDirection) {
   if (isPreferredStopAlways(aEdge)) {
     // If the given position is `scroll-snap-stop: always` and if the position
     // is in between the start and the destination positions, update the best
     // position based on the distance from the __start__ point.
     isCandidateOfBest =
         std::abs(distanceFromStart) <
         std::abs(aCandidateTracker->mBestEdges[0].mPosition - aStartPos);
   } else if (isPreferredStopAlways(aCandidateTracker->mBestEdges[0])) {
     // If we've found a preferable `scroll-snap-stop:always` position as the
     // best, do not update it unless the given position is also
     // `scroll-snap-stop: always`.
     isCandidateOfBest = false;
   }
 }

 updateBestEdges(isCandidateOfBest, isCandidateOfSecondBest);
}

static void ProcessSnapPositions(CalcSnapPoints& aCalcSnapPoints,
                                const ScrollSnapInfo& aSnapInfo) {
 aSnapInfo.ForEachValidTargetFor(
     aCalcSnapPoints.Destination(), [&](const auto& aTarget) -> bool {
       if (aTarget.mSnapPoint.mX && aSnapInfo.mScrollSnapStrictnessX !=
                                        StyleScrollSnapStrictness::None) {
         aCalcSnapPoints.AddVerticalEdge(aTarget);
       }
       if (aTarget.mSnapPoint.mY && aSnapInfo.mScrollSnapStrictnessY !=
                                        StyleScrollSnapStrictness::None) {
         aCalcSnapPoints.AddHorizontalEdge(aTarget);
       }
       return true;
     });
}

Maybe<SnapDestination> ScrollSnapUtils::GetSnapPointForDestination(
   const ScrollSnapInfo& aSnapInfo, ScrollUnit aUnit,
   ScrollSnapFlags aSnapFlags, const nsRect& aScrollRange,
   const nsPoint& aStartPos, const nsPoint& aDestination) {
 if (aSnapInfo.mScrollSnapStrictnessY == StyleScrollSnapStrictness::None &&
     aSnapInfo.mScrollSnapStrictnessX == StyleScrollSnapStrictness::None) {
   return Nothing();
 }

 if (!aSnapInfo.HasSnapPositions()) {
   return Nothing();
 }

 CalcSnapPoints calcSnapPoints(aUnit, aSnapFlags, aDestination, aStartPos);

 ProcessSnapPositions(calcSnapPoints, aSnapInfo);

 // If the distance between the first and the second candidate snap points
 // is larger than the snapport size and the snapport is covered by larger
 // elements, any points inside the covering area should be valid snap
 // points.
 // https://drafts.csswg.org/css-scroll-snap-1/#snap-overflow
 // NOTE: |aDestination| sometimes points outside of the scroll range, e.g.
 // by the APZC fling, so for the overflow checks we need to clamp it.
 nsPoint clampedDestination = aScrollRange.ClampPoint(aDestination);
 for (auto range : aSnapInfo.mXRangeWiderThanSnapport) {
   if (range.IsValid(clampedDestination.x, aSnapInfo.mSnapportSize.width) &&
       calcSnapPoints.XDistanceBetweenBestAndSecondEdge() >
           aSnapInfo.mSnapportSize.width) {
     calcSnapPoints.AddVerticalEdge(ScrollSnapInfo::SnapTarget{
         Some(clampedDestination.x), Nothing(), range.mSnapArea,
         StyleScrollSnapStop::Normal, ScrollSnapTargetId::None});
     break;
   }
 }
 for (auto range : aSnapInfo.mYRangeWiderThanSnapport) {
   if (range.IsValid(clampedDestination.y, aSnapInfo.mSnapportSize.height) &&
       calcSnapPoints.YDistanceBetweenBestAndSecondEdge() >
           aSnapInfo.mSnapportSize.height) {
     calcSnapPoints.AddHorizontalEdge(ScrollSnapInfo::SnapTarget{
         Nothing(), Some(clampedDestination.y), range.mSnapArea,
         StyleScrollSnapStop::Normal, ScrollSnapTargetId::None});
     break;
   }
 }

 bool snapped = false;
 auto finalPos = calcSnapPoints.GetBestEdge(aSnapInfo.mSnapportSize);

 // Check whether we will snap to the final position on the given axis or not,
 // and if we will not, reset the final position to the original position so
 // that even if we need to snap on an axis, but we don't need to on the other
 // axis, the returned final position can be used as a valid destination.
 auto checkSnapOnAxis = [&snapped](StyleScrollSnapStrictness aStrictness,
                                   nscoord aDestination, nscoord aSnapportSize,
                                   nscoord& aFinalPosition) {
   // We used 0.3 proximity threshold which is what WebKit uses.
   constexpr float proximityRatio = 0.3;
   if (aStrictness == StyleScrollSnapStrictness::None ||
       (aStrictness == StyleScrollSnapStrictness::Proximity &&
        std::abs(aDestination - aFinalPosition) >
            aSnapportSize * proximityRatio)) {
     aFinalPosition = aDestination;
     return;
   }
   snapped = true;
 };

 checkSnapOnAxis(aSnapInfo.mScrollSnapStrictnessY, aDestination.y,
                 aSnapInfo.mSnapportSize.height, finalPos.mPosition.y);
 checkSnapOnAxis(aSnapInfo.mScrollSnapStrictnessX, aDestination.x,
                 aSnapInfo.mSnapportSize.width, finalPos.mPosition.x);

 return snapped ? Some(finalPos) : Nothing();
}

ScrollSnapTargetId ScrollSnapUtils::GetTargetIdFor(const nsIFrame* aFrame) {
 MOZ_ASSERT(aFrame && aFrame->GetContent());
 return ScrollSnapTargetId{reinterpret_cast<uintptr_t>(aFrame->GetContent())};
}

static std::pair<Maybe<nscoord>, Maybe<nscoord>> GetCandidateInLastTargets(
   const ScrollSnapInfo& aSnapInfo, const nsPoint& aCurrentPosition,
   const UniquePtr<ScrollSnapTargetIds>& aLastSnapTargetIds,
   const nsIContent* aFocusedContent) {
 ScrollSnapTargetId targetIdForFocusedContent = ScrollSnapTargetId::None;
 if (aFocusedContent && aFocusedContent->GetPrimaryFrame()) {
   targetIdForFocusedContent =
       ScrollSnapUtils::GetTargetIdFor(aFocusedContent->GetPrimaryFrame());
 }

 // Note: Below algorithm doesn't care about cases where the last snap point
 // was on an element larger than the snapport since it's not clear to us
 // what we should do for now.
 // https://github.com/w3c/csswg-drafts/issues/7438
 const ScrollSnapInfo::SnapTarget* focusedTarget = nullptr;
 Maybe<nscoord> x, y;
 aSnapInfo.ForEachValidTargetFor(
     aCurrentPosition, [&](const auto& aTarget) -> bool {
       if (aTarget.mSnapPoint.mX && aSnapInfo.mScrollSnapStrictnessX !=
                                        StyleScrollSnapStrictness::None) {
         if (aLastSnapTargetIds->mIdsOnX.Contains(aTarget.mTargetId)) {
           if (targetIdForFocusedContent == aTarget.mTargetId) {
             // If we've already found the candidate on Y axis, but if snapping
             // to the point results this target is scrolled out, we can't use
             // it.
             if ((y && !aTarget.mSnapArea.Intersects(
                           nsRect(nsPoint(*aTarget.mSnapPoint.mX, *y),
                                  aSnapInfo.mSnapportSize)))) {
               y.reset();
             }

             focusedTarget = &aTarget;
             // If the focused one is valid, then it's the candidate.
             x = aTarget.mSnapPoint.mX;
           }

           if (!x) {
             // Update the candidate on X axis only if
             // 1) we haven't yet found the candidate on Y axis
             // 2) or if we've found the candiate on Y axis and if snapping to
             // the
             //    candidate position result the target element is visible
             //    inside the snapport.
             if (!y || (y && aTarget.mSnapArea.Intersects(
                                 nsRect(nsPoint(*aTarget.mSnapPoint.mX, *y),
                                        aSnapInfo.mSnapportSize)))) {
               x = aTarget.mSnapPoint.mX;
             }
           }
         }
       }
       if (aTarget.mSnapPoint.mY && aSnapInfo.mScrollSnapStrictnessY !=
                                        StyleScrollSnapStrictness::None) {
         if (aLastSnapTargetIds->mIdsOnY.Contains(aTarget.mTargetId)) {
           if (targetIdForFocusedContent == aTarget.mTargetId) {
             NS_ASSERTION(
                 !focusedTarget || focusedTarget == &aTarget,
                 "If the focused target has been found on X axis, the "
                 "target should be same");
             // If we've already found the candidate on X axis other than the
             // focused one, but if snapping to the point results this target
             // is scrolled out, we can't use it.
             if (!focusedTarget &&
                 (x && !aTarget.mSnapArea.Intersects(
                           nsRect(nsPoint(*x, *aTarget.mSnapPoint.mY),
                                  aSnapInfo.mSnapportSize)))) {
               x.reset();
             }

             focusedTarget = &aTarget;
             y = aTarget.mSnapPoint.mY;
           }

           if (!y) {
             if (!x || (x && aTarget.mSnapArea.Intersects(
                                 nsRect(nsPoint(*x, *aTarget.mSnapPoint.mY),
                                        aSnapInfo.mSnapportSize)))) {
               y = aTarget.mSnapPoint.mY;
             }
           }
         }
       }

       // If we found candidates on both axes, it's the one we need.
       if (x && y &&
           // If we haven't found the focused target, it's possible that we
           // haven't iterated it, don't break in such case.
           (targetIdForFocusedContent == ScrollSnapTargetId::None ||
            focusedTarget)) {
         return false;
       }
       return true;
     });

 return {x, y};
}

Maybe<SnapDestination> ScrollSnapUtils::GetSnapPointForResnap(
   const ScrollSnapInfo& aSnapInfo, const nsRect& aScrollRange,
   const nsPoint& aCurrentPosition,
   const UniquePtr<ScrollSnapTargetIds>& aLastSnapTargetIds,
   const nsIContent* aFocusedContent) {
 if (!aLastSnapTargetIds) {
   return GetSnapPointForDestination(aSnapInfo, ScrollUnit::DEVICE_PIXELS,
                                     ScrollSnapFlags::IntendedEndPosition,
                                     aScrollRange, aCurrentPosition,
                                     aCurrentPosition);
 }

 auto [x, y] = GetCandidateInLastTargets(aSnapInfo, aCurrentPosition,
                                         aLastSnapTargetIds, aFocusedContent);
 if (!x && !y) {
   // In the worst case there's no longer valid snap points previously snapped,
   // try to find new valid snap points.
   return GetSnapPointForDestination(aSnapInfo, ScrollUnit::DEVICE_PIXELS,
                                     ScrollSnapFlags::IntendedEndPosition,
                                     aScrollRange, aCurrentPosition,
                                     aCurrentPosition);
 }

 // If there's no candidate on one of the axes in the last snap points, try
 // to find a new candidate.
 if (!x || !y) {
   nsPoint newPosition =
       nsPoint(x ? *x : aCurrentPosition.x, y ? *y : aCurrentPosition.y);
   CalcSnapPoints calcSnapPoints(ScrollUnit::DEVICE_PIXELS,
                                 ScrollSnapFlags::IntendedEndPosition,
                                 newPosition, newPosition);

   aSnapInfo.ForEachValidTargetFor(
       newPosition, [&, &x = x, &y = y](const auto& aTarget) -> bool {
         if (!x && aTarget.mSnapPoint.mX &&
             aSnapInfo.mScrollSnapStrictnessX !=
                 StyleScrollSnapStrictness::None) {
           calcSnapPoints.AddVerticalEdge(aTarget);
         }
         if (!y && aTarget.mSnapPoint.mY &&
             aSnapInfo.mScrollSnapStrictnessY !=
                 StyleScrollSnapStrictness::None) {
           calcSnapPoints.AddHorizontalEdge(aTarget);
         }
         return true;
       });

   auto finalPos = calcSnapPoints.GetBestEdge(aSnapInfo.mSnapportSize);
   if (!x) {
     x = Some(finalPos.mPosition.x);
   }
   if (!y) {
     y = Some(finalPos.mPosition.y);
   }
 }

 SnapDestination snapTarget{nsPoint(*x, *y)};
 // Collect snap points where the position is still same as the new snap
 // position.
 aSnapInfo.ForEachValidTargetFor(
     snapTarget.mPosition, [&, &x = x, &y = y](const auto& aTarget) -> bool {
       if (aTarget.mSnapPoint.mX &&
           aSnapInfo.mScrollSnapStrictnessX !=
               StyleScrollSnapStrictness::None &&
           aTarget.mSnapPoint.mX == x) {
         snapTarget.mTargetIds.mIdsOnX.AppendElement(aTarget.mTargetId);
       }

       if (aTarget.mSnapPoint.mY &&
           aSnapInfo.mScrollSnapStrictnessY !=
               StyleScrollSnapStrictness::None &&
           aTarget.mSnapPoint.mY == y) {
         snapTarget.mTargetIds.mIdsOnY.AppendElement(aTarget.mTargetId);
       }
       return true;
     });
 return Some(snapTarget);
}

void ScrollSnapUtils::PostPendingResnapIfNeededFor(nsIFrame* aFrame) {
 ScrollSnapTargetId id = GetTargetIdFor(aFrame);
 if (id == ScrollSnapTargetId::None) {
   return;
 }

 if (ScrollContainerFrame* sf = nsLayoutUtils::GetNearestScrollContainerFrame(
         aFrame, nsLayoutUtils::SCROLLABLE_SAME_DOC |
                     nsLayoutUtils::SCROLLABLE_INCLUDE_HIDDEN)) {
   sf->PostPendingResnapIfNeeded(aFrame);
 }
}

void ScrollSnapUtils::PostPendingResnapFor(nsIFrame* aFrame) {
 if (ScrollContainerFrame* sf = nsLayoutUtils::GetNearestScrollContainerFrame(
         aFrame, nsLayoutUtils::SCROLLABLE_SAME_DOC |
                     nsLayoutUtils::SCROLLABLE_INCLUDE_HIDDEN)) {
   sf->PostPendingResnap();
 }
}

bool ScrollSnapUtils::NeedsToRespectTargetWritingMode(
   const nsSize& aSnapAreaSize, const nsSize& aSnapportSize) {
 // Use the writing-mode on the target element if the snap area is larger than
 // the snapport.
 // https://drafts.csswg.org/css-scroll-snap/#snap-scope
 //
 // It's unclear `larger` means that the size is larger than only on the target
 // axis. If it doesn't, it will pick the same axis in the case where only one
 // axis is larger. For example, if an element size is (200 x 10) and the
 // snapport size is (100 x 100) and if the element's writing mode is different
 // from the scroller's writing mode, then `scroll-snap-align: start start`
 // will be conflict.
 return aSnapAreaSize.width > aSnapportSize.width ||
        aSnapAreaSize.height > aSnapportSize.height;
}

static nsRect InflateByScrollMargin(const nsRect& aTargetRect,
                                   const nsMargin& aScrollMargin,
                                   const nsRect& aScrolledRect) {
 // Inflate the rect by scroll-margin.
 nsRect result = aTargetRect;
 result.Inflate(aScrollMargin);

 // But don't be beyond the limit boundary.
 return result.Intersect(aScrolledRect);
}

nsRect ScrollSnapUtils::GetSnapAreaFor(const nsIFrame* aFrame,
                                      const nsIFrame* aScrolledFrame,
                                      const nsRect& aScrolledRect) {
 nsRect targetRect = nsLayoutUtils::TransformFrameRectToAncestor(
     aFrame, aFrame->GetRectRelativeToSelf(), aScrolledFrame);

 // The snap area contains scroll-margin values.
 // https://drafts.csswg.org/css-scroll-snap-1/#scroll-snap-area
 nsMargin scrollMargin = aFrame->StyleMargin()->GetScrollMargin();
 return InflateByScrollMargin(targetRect, scrollMargin, aScrolledRect);
}

}  // namespace mozilla