/* 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/ScrollSnapTargetId.h"
#include "mozilla/ServoStyleConsts.h"
#include "mozilla/StaticPrefs_layout.h"
#include "mozilla/dom/Document.h"
#include "nsContentUtils.h"
#include "nsIFrame.h"
#include "nsLayoutUtils.h"
#include "nsPresContext.h"
#include "nsString.h"
#include "nsTArray.h"

mozilla::LazyLogModule sApzScrollSnapLog("apz.scrollsnap");
#define SCROLL_SNAP_LOG(...) \
  MOZ_LOG(sApzScrollSnapLog, LogLevel::Debug, (__VA_ARGS__))

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,
                 const StyleScrollSnapStrictness& aXStrictness,
                 const StyleScrollSnapStrictness& aYStrictness);
  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;
  nsPoint GetDefaultSnapPoint() 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
  StyleScrollSnapStrictness mStrictnessX;
  StyleScrollSnapStrictness mStrictnessY;
  CandidateTracker mTrackerOnX;
  CandidateTracker mTrackerOnY;
};

CalcSnapPoints::CalcSnapPoints(ScrollUnit aUnit, ScrollSnapFlags aSnapFlags,
                               const nsPoint& aDestination,
                               const nsPoint& aStartPos,
                               const StyleScrollSnapStrictness& aXStrictness,
                               const StyleScrollSnapStrictness& aYStrictness)
    : mUnit(aUnit),
      mSnapFlags(aSnapFlags),
      mDestination(aDestination),
      mStartPos(aStartPos),
      mStrictnessX(aXStrictness),
      mStrictnessY(aYStrictness) {
  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;
  }
}

nsPoint CalcSnapPoints::GetDefaultSnapPoint() const {
  MOZ_ASSERT(mSnapFlags != ScrollSnapFlags::Disabled);
  nsPoint defaultPoint = mDestination;
  if ((mSnapFlags & ScrollSnapFlags::IntendedDirection) ==
      ScrollSnapFlags::IntendedDirection) {
    if (mStrictnessX != StyleScrollSnapStrictness::Proximity) {
      defaultPoint.x = mStartPos.x;
    }
    if (mStrictnessY != StyleScrollSnapStrictness::Proximity) {
      defaultPoint.y = mStartPos.y;
    }
  }
  return defaultPoint;
}

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.
  }

  nsPoint defaultPoint = GetDefaultSnapPoint();
  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.
                  : defaultPoint.x,
              mTrackerOnY.EdgeFound()
                  ? mTrackerOnY.mBestEdges[0].mPosition
                  // Same as above X axis case, use the destination point if we
                  // didn't find any candidates.
                  : defaultPoint.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);
}

using SnapTarget = ScrollSnapInfo::SnapTarget;

static void ProcessSnapPositions(CalcSnapPoints& aCalcSnapPoints,
                                 const ScrollSnapInfo& aSnapInfo) {
  aSnapInfo.ForEachValidTargetFor(
      aCalcSnapPoints.Destination(), [&](const SnapTarget& 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;
      });
}

static void ProcessSnapOverflowForAxis(
    CalcSnapPoints& aCalcSnapPoints, layers::ScrollDirection aScrollDirection,
    nscoord aClampedDestination, nscoord aSnapportSize,
    const nsTArray<ScrollSnapInfo::ScrollSnapRange>& aRanges) {
  auto addEdge = [&](nscoord aSnapPoint, const nsRect& aSnapArea) {
    if (aScrollDirection == layers::ScrollDirection::eHorizontal) {
      aCalcSnapPoints.AddVerticalEdge(ScrollSnapInfo::SnapTarget{
          Some(aSnapPoint), Nothing(), aSnapArea, StyleScrollSnapStop::Normal,
          ScrollSnapTargetId::None});
    } else {
      aCalcSnapPoints.AddHorizontalEdge(ScrollSnapInfo::SnapTarget{
          Nothing(), Some(aSnapPoint), aSnapArea, StyleScrollSnapStop::Normal,
          ScrollSnapTargetId::None});
    }
  };

  for (const auto& range : aRanges) {
    if (range.IsValid(aClampedDestination, aSnapportSize)) {
      addEdge(range.FindNearestSnapPoint(aClampedDestination, aSnapportSize),
              range.mSnapArea);
      break;
    }
  }
}

static void ProcessSnapOverflow(CalcSnapPoints& aCalcSnapPoints,
                                const ScrollSnapInfo& aSnapInfo,
                                const nsRect& aScrollRange,
                                const nsPoint& aDestination) {
  // 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);
  if (aCalcSnapPoints.XDistanceBetweenBestAndSecondEdge() >
      aSnapInfo.mSnapportSize.width) {
    ProcessSnapOverflowForAxis(
        aCalcSnapPoints, layers::ScrollDirection::eHorizontal,
        clampedDestination.x, aSnapInfo.mSnapportSize.width,
        aSnapInfo.mXRangeWiderThanSnapport);
  }
  if (aCalcSnapPoints.YDistanceBetweenBestAndSecondEdge() >
      aSnapInfo.mSnapportSize.height) {
    ProcessSnapOverflowForAxis(
        aCalcSnapPoints, layers::ScrollDirection::eVertical,
        clampedDestination.y, aSnapInfo.mSnapportSize.height,
        aSnapInfo.mYRangeWiderThanSnapport);
  }
}

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,
                                aSnapInfo.mScrollSnapStrictnessX,
                                aSnapInfo.mScrollSnapStrictnessY);

  ProcessSnapPositions(calcSnapPoints, aSnapInfo);
  ProcessSnapOverflow(calcSnapPoints, aSnapInfo, aScrollRange, aDestination);

  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 const nsIContent* ResolveSnapTargetToContent(
    const ScrollSnapTargetId& aId) {
  if (aId == ScrollSnapTargetId::None) {
    return nullptr;
  }
  return reinterpret_cast<const nsIContent*>(aId);
}

static bool SnapTargetIsFlattenedTreeDescendantOf(
    const ScrollSnapTargetId& aPossibleDescendant,
    const ScrollSnapTargetId& aPossibleAncestor) {
  MOZ_ASSERT(aPossibleAncestor != ScrollSnapTargetId::None &&
             aPossibleDescendant != ScrollSnapTargetId::None);
  return nsContentUtils::ContentIsFlattenedTreeDescendantOf(
      ResolveSnapTargetToContent(aPossibleDescendant),
      ResolveSnapTargetToContent(aPossibleAncestor));
}

static std::pair<Maybe<nscoord>, Maybe<nscoord>> GetCandidateInLastTargets(
    const ScrollSnapInfo& aSnapInfo, const nsPoint& aCurrentPosition,
    const UniquePtr<ScrollSnapTargetIds>& aLastSnapTargetIds,
    const nsIContent* aFocusedContent, const nsIContent* aTargetContent,
    const WritingMode aWM) {
  auto GetTargetId = [](const nsIContent* aContent) -> ScrollSnapTargetId {
    if (aContent && aContent->GetPrimaryFrame()) {
      return ScrollSnapUtils::GetTargetIdFor(aContent->GetPrimaryFrame());
    }
    return ScrollSnapTargetId::None;
  };

  ScrollSnapTargetId targetIdForFocusedContent = GetTargetId(aFocusedContent);
  ScrollSnapTargetId targetIdForTargetContent = GetTargetId(aTargetContent);
  const bool isVertical = aWM.IsVertical();

  // 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

  // Build the inline and block candidate sets from the last snap targets, per
  // https://drafts.csswg.org/css-scroll-snap-1/#multiple-aligned-snap-areas
  AutoTArray<const ScrollSnapInfo::SnapTarget*, 2> inlineSet, blockSet;
  const ScrollSnapInfo::SnapTarget* focusedTarget = nullptr;
  const ScrollSnapInfo::SnapTarget* targetedTarget = nullptr;

  aSnapInfo.ForEachValidTargetFor(
      aCurrentPosition, [&](const SnapTarget& aTarget) -> bool {
        if (aTarget.mSnapPoint.I(aWM) &&
            aSnapInfo.StrictnessInline(aWM) !=
                StyleScrollSnapStrictness::None &&
            aLastSnapTargetIds->IdsOnInline(aWM).Contains(aTarget.mTargetId)) {
          inlineSet.AppendElement(&aTarget);
        }
        if (aTarget.mSnapPoint.B(aWM) &&
            aSnapInfo.StrictnessBlock(aWM) != StyleScrollSnapStrictness::None &&
            aLastSnapTargetIds->IdsOnBlock(aWM).Contains(aTarget.mTargetId)) {
          blockSet.AppendElement(&aTarget);
        }
        if (aLastSnapTargetIds->Contains(aTarget.mTargetId)) {
          if (aTarget.mTargetId == targetIdForFocusedContent ||
              (targetIdForFocusedContent != ScrollSnapTargetId::None &&
               SnapTargetIsFlattenedTreeDescendantOf(targetIdForFocusedContent,
                                                     aTarget.mTargetId))) {
            focusedTarget = &aTarget;
          }
          if (aTarget.mTargetId == targetIdForTargetContent) {
            targetedTarget = &aTarget;
          }
        }
        return true;
      });

  if (MOZ_LOG_TEST(sApzScrollSnapLog, LogLevel::Debug)) {
    SCROLL_SNAP_LOG("All snap targets: %s",
                    ToString(aSnapInfo.mSnapTargets).c_str());
    SCROLL_SNAP_LOG("Inline snap targets: %s", ToString(inlineSet).c_str());
    SCROLL_SNAP_LOG("Block snap targets: %s", ToString(blockSet).c_str());
  }

  // Step 4.1: If the focused element is in a set, it's the only candidate.
  if (focusedTarget) {
    if (focusedTarget->mSnapPoint.I(aWM) &&
        aSnapInfo.StrictnessInline(aWM) != StyleScrollSnapStrictness::None) {
      inlineSet = {focusedTarget};
    }
    if (focusedTarget->mSnapPoint.B(aWM) &&
        aSnapInfo.StrictnessBlock(aWM) != StyleScrollSnapStrictness::None) {
      blockSet = {focusedTarget};
    }
  }

  // Step 4.2: If no focused element was found but the :target element is
  // in a set, it's the only candidate.
  if (!focusedTarget && targetedTarget) {
    if (targetedTarget->mSnapPoint.I(aWM) &&
        aSnapInfo.StrictnessInline(aWM) != StyleScrollSnapStrictness::None) {
      inlineSet = {targetedTarget};
    }
    if (targetedTarget->mSnapPoint.B(aWM) &&
        aSnapInfo.StrictnessBlock(aWM) != StyleScrollSnapStrictness::None) {
      blockSet = {targetedTarget};
    }
  }

  // Step 4.3: For each box in a set, remove any box from the set that is an
  // ancestor of that box.
  auto removeAncestors =
      [](AutoTArray<const ScrollSnapInfo::SnapTarget*, 2>& aSet) {
        if (aSet.Length() <= 1) {
          return;
        }
        AutoTArray<const ScrollSnapInfo::SnapTarget*, 2> result;
        for (const auto* candidate : aSet) {
          bool isAncestorOfAnotherInSet = false;
          for (const auto* other : aSet) {
            if (other == candidate) {
              continue;
            }
            if (SnapTargetIsFlattenedTreeDescendantOf(other->mTargetId,
                                                      candidate->mTargetId)) {
              isAncestorOfAnotherInSet = true;
              break;
            }
          }
          if (!isAncestorOfAnotherInSet) {
            result.AppendElement(candidate);
          }
        }
        aSet = std::move(result);
      };
  removeAncestors(inlineSet);
  removeAncestors(blockSet);

  // Step 5: If the inline and block sets overlap (share at least one element),
  // replace both with their intersection. If they are disjoint, the block axis
  // set takes precedence and is used for both axes.
  AutoTArray<const ScrollSnapInfo::SnapTarget*, 2> intersection;
  for (const auto* inlineTarget : inlineSet) {
    for (const auto* blockTarget : blockSet) {
      if (inlineTarget->mTargetId == blockTarget->mTargetId) {
        intersection.AppendElement(inlineTarget);
        break;
      }
    }
  }
  const auto& effective = !intersection.IsEmpty() ? intersection
                          : !blockSet.IsEmpty()   ? blockSet
                                                  : inlineSet;

  // Select the first candidate from each set in tree order, using a
  // cross-axis visibility check to prefer targets whose snap area remains
  // visible at the combined snap position.
  Maybe<nscoord> x, y;

  const ScrollSnapInfo::SnapTarget* inlinePick{nullptr};
  const ScrollSnapInfo::SnapTarget* blockPick{nullptr};
  auto pickFromInline = [&]() {
    Maybe<nscoord>& inlineCoord = isVertical ? y : x;
    const Maybe<nscoord>& blockCoord = isVertical ? x : y;
    for (const auto* target : effective) {
      // When effective == blockSet, targets may not have an inline snap point.
      const auto& sp = target->mSnapPoint.I(aWM);
      if (!sp) {
        continue;
      }
      if (!blockCoord || target->mSnapArea.Intersects(
                             nsRect(isVertical ? nsPoint(*blockCoord, *sp)
                                               : nsPoint(*sp, *blockCoord),
                                    aSnapInfo.mSnapportSize))) {
        inlineCoord = sp;
        inlinePick = target;
        return;
      }
    }
  };

  auto pickFromBlock = [&]() {
    Maybe<nscoord>& blockCoord = isVertical ? x : y;
    const Maybe<nscoord>& inlineCoord = isVertical ? y : x;
    for (const auto* target : effective) {
      // When effective == inlineSet, targets may not have a block snap point.
      const auto& sp = target->mSnapPoint.B(aWM);
      if (!sp) {
        continue;
      }
      if (!inlineCoord || target->mSnapArea.Intersects(
                              nsRect(isVertical ? nsPoint(*sp, *inlineCoord)
                                                : nsPoint(*inlineCoord, *sp),
                                     aSnapInfo.mSnapportSize))) {
        blockCoord = sp;
        blockPick = target;
        return;
      }
    }
  };

  // Only pick snap positions for axes that have snapping enabled.
  if (aSnapInfo.StrictnessInline(aWM) != StyleScrollSnapStrictness::None) {
    pickFromInline();
    if (inlinePick && MOZ_LOG_TEST(sApzScrollSnapLog, LogLevel::Debug)) {
      SCROLL_SNAP_LOG("Inline snap target pick: %s",
                      ToString(*inlinePick).c_str());
    }
  }
  if (aSnapInfo.StrictnessBlock(aWM) != StyleScrollSnapStrictness::None) {
    pickFromBlock();
    if (blockPick && MOZ_LOG_TEST(sApzScrollSnapLog, LogLevel::Debug)) {
      SCROLL_SNAP_LOG("Block snap target pick: %s",
                      ToString(*blockPick).c_str());
    }
  }

  return {x, y};
}

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

  auto [x, y] =
      GetCandidateInLastTargets(aSnapInfo, aCurrentPosition, aLastSnapTargetIds,
                                aFocusedContent, aTargetContent, aWritingMode);
  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.mScrollSnapStrictnessX,
        aSnapInfo.mScrollSnapStrictnessY);
    aSnapInfo.ForEachValidTargetFor(
        newPosition, [&, &x = x, &y = y](const SnapTarget& 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 SnapTarget& aTarget) -> bool {
        if (aTarget.mSnapPoint.mX &&
            aSnapInfo.mScrollSnapStrictnessX !=
                StyleScrollSnapStrictness::None &&
            aTarget.mSnapPoint.mX == x &&
            // Ignore snap points outside of the snapport to optimize the next
            // re-snap iteration.
            aTarget.mSnapArea.Intersects(
                nsRect(nsPoint(*x, *y), aSnapInfo.mSnapportSize))) {
          snapTarget.mTargetIds.mIdsOnX.AppendElement(aTarget.mTargetId);
        }

        if (aTarget.mSnapPoint.mY &&
            aSnapInfo.mScrollSnapStrictnessY !=
                StyleScrollSnapStrictness::None &&
            aTarget.mSnapPoint.mY == y &&
            // Likewise for the Y axis.
            aTarget.mSnapArea.Intersects(
                nsRect(nsPoint(*x, *y), aSnapInfo.mSnapportSize))) {
          snapTarget.mTargetIds.mIdsOnY.AppendElement(aTarget.mTargetId);
        }
        return true;
      });
  return Some(snapTarget);
}

void ScrollSnapUtils::PostPendingResnapIfNeededFor(nsIFrame* aFrame) {
  MOZ_ASSERT(aFrame);

  ScrollSnapTargetId id = GetTargetIdFor(aFrame);
  if (id == ScrollSnapTargetId::None) {
    return;
  }

  ScrollContainerFrame* sf = nsLayoutUtils::GetNearestScrollContainerFrame(
      aFrame, nsLayoutUtils::SCROLLABLE_SAME_DOC |
                  nsLayoutUtils::SCROLLABLE_INCLUDE_HIDDEN);
  if (!sf) {
    return;
  }

  sf->PostPendingResnapIfNeeded(aFrame);

  nsIContent* focusedContent =
      aFrame->PresContext()->Document()->GetUnretargetedFocusedContent(
          dom::Document::IncludeChromeOnly::No);
  // If the focused content is a descendant of |aFrame|, ancestor scroll
  // containers may also need to re-snap since |sf| or other ancestors may be
  // registered as their snap target.
  if (!focusedContent || !nsContentUtils::ContentIsFlattenedTreeDescendantOf(
                             focusedContent, aFrame->GetContent())) {
    return;
  }

  AutoTArray<nsIFrame*, 2> targets = {sf};
  for (nsIFrame* f = sf->GetParent(); f; f = f->GetParent()) {
    if (ScrollContainerFrame* ancestorSf = do_QueryFrame(f)) {
      for (nsIFrame* target : targets) {
        ancestorSf->PostPendingResnapIfNeeded(target);
      }
      targets.ClearAndRetainStorage();
    }
    targets.AppendElement(f);
  }
}

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