/* 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 "mozilla/KeyframeUtils.h"

#include <algorithm>  // For std::stable_sort, std::min
#include <utility>

#include "PseudoStyleType.h"   // For PseudoStyleType
#include "js/ForOfIterator.h"  // For JS::ForOfIterator
#include "js/PropertyAndElement.h"  // JS_Enumerate, JS_GetProperty, JS_GetPropertyById
#include "jsapi.h"                  // For most JSAPI
#include "mozilla/CSSPropertyId.h"
#include "mozilla/ComputedStyle.h"
#include "mozilla/ErrorResult.h"
#include "mozilla/ServoBindingTypes.h"
#include "mozilla/ServoBindings.h"
#include "mozilla/ServoCSSParser.h"
#include "mozilla/ServoStyleSet.h"
#include "mozilla/StaticPrefs_dom.h"
#include "mozilla/StyleAnimationValue.h"
#include "mozilla/TimingParams.h"
#include "mozilla/dom/BaseKeyframeTypesBinding.h"  // For FastBaseKeyframe etc.
#include "mozilla/dom/BindingCallContext.h"
#include "mozilla/dom/CSSUnitValue.h"
#include "mozilla/dom/Element.h"
#include "mozilla/dom/KeyframeEffect.h"  // For PropertyValuesPair etc.
#include "mozilla/dom/KeyframeEffectBinding.h"
#include "mozilla/dom/Nullable.h"
#include "mozilla/dom/ViewTimeline.h"
#include "nsCSSPropertyIDSet.h"
#include "nsCSSProps.h"
#include "nsClassHashtable.h"
#include "nsContentUtils.h"  // For GetContextForContent
#include "nsIScriptError.h"
#include "nsPresContextInlines.h"
#include "nsString.h"
#include "nsTArray.h"

using mozilla::dom::Nullable;

namespace mozilla {

// ------------------------------------------------------------------
//
// Internal data types
//
// ------------------------------------------------------------------

// For the aAllowList parameter of AppendStringOrStringSequence and
// GetPropertyValuesPairs.
enum class ListAllowance { eDisallow, eAllow };

/**
 * A property-values pair obtained from the open-ended properties
 * discovered on a regular keyframe or property-indexed keyframe object.
 *
 * Single values (as required by a regular keyframe, and as also supported
 * on property-indexed keyframes) are stored as the only element in
 * mValues.
 */
struct PropertyValuesPair {
  PropertyValuesPair() : mProperty(eCSSProperty_UNKNOWN) {}

  CSSPropertyId mProperty;
  nsTArray<nsCString> mValues;
};

/**
 * An additional property (for a property-values pair) found on a
 * BaseKeyframe or BasePropertyIndexedKeyframe object.
 */
struct AdditionalProperty {
  CSSPropertyId mProperty;
  size_t mJsidIndex = 0;  // Index into |ids| in GetPropertyValuesPairs.

  struct PropertyComparator {
    bool Equals(const AdditionalProperty& aLhs,
                const AdditionalProperty& aRhs) const {
      return aLhs.mProperty == aRhs.mProperty;
    }
    bool LessThan(const AdditionalProperty& aLhs,
                  const AdditionalProperty& aRhs) const {
      bool customLhs = aLhs.mProperty.mId ==
                       NonCustomCSSPropertyId::eCSSPropertyExtra_variable;
      bool customRhs = aRhs.mProperty.mId ==
                       NonCustomCSSPropertyId::eCSSPropertyExtra_variable;
      if (!customLhs && !customRhs) {
        // Compare by IDL names.
        return nsCSSProps::PropertyIDLNameSortPosition(aLhs.mProperty.mId) <
               nsCSSProps::PropertyIDLNameSortPosition(aRhs.mProperty.mId);
      }
      if (customLhs && customRhs) {
        // Compare by custom property names.
        return nsDependentAtomString(aLhs.mProperty.mCustomName) <
               nsDependentAtomString(aRhs.mProperty.mCustomName);
      }
      // Custom properties should be ordered before normal CSS properties, as if
      // the custom property name starts with `--`.
      // <https://drafts.csswg.org/web-animations-1/#idl-attribute-name-to-animation-property-name>
      return !customLhs && customRhs;
    }
  };
};

/**
 * Data for a segment in a keyframe animation of a given property
 * whose value is a StyleAnimationValue.
 *
 * KeyframeValueEntry is used in GetAnimationPropertiesFromKeyframes
 * to gather data for each individual segment.
 */
struct KeyframeValueEntry {
  KeyframeValueEntry()
      : mProperty(eCSSProperty_UNKNOWN), mOffset(), mComposite() {}

  CSSPropertyId mProperty;
  AnimationValue mValue;

  float mOffset;
  Maybe<StyleComputedTimingFunction> mTimingFunction;
  dom::CompositeOperation mComposite;

  struct PropertyOffsetComparator {
    static bool Equals(const KeyframeValueEntry& aLhs,
                       const KeyframeValueEntry& aRhs) {
      return aLhs.mProperty == aRhs.mProperty && aLhs.mOffset == aRhs.mOffset;
    }
    static bool LessThan(const KeyframeValueEntry& aLhs,
                         const KeyframeValueEntry& aRhs) {
      // First, sort by property name.
      bool customLhs = aLhs.mProperty.mId ==
                       NonCustomCSSPropertyId::eCSSPropertyExtra_variable;
      bool customRhs = aRhs.mProperty.mId ==
                       NonCustomCSSPropertyId::eCSSPropertyExtra_variable;
      if (!customLhs && !customRhs) {
        // Compare by IDL names.
        int32_t order =
            nsCSSProps::PropertyIDLNameSortPosition(aLhs.mProperty.mId) -
            nsCSSProps::PropertyIDLNameSortPosition(aRhs.mProperty.mId);
        if (order != 0) {
          return order < 0;
        }
      } else if (customLhs && customRhs) {
        // Compare by custom property names.
        int order = Compare(nsDependentAtomString(aLhs.mProperty.mCustomName),
                            nsDependentAtomString(aRhs.mProperty.mCustomName));
        if (order != 0) {
          return order < 0;
        }
      } else {
        return !customLhs && customRhs;
      }

      // Then, by offset.
      return aLhs.mOffset < aRhs.mOffset;
    }
  };
};

class ComputedOffsetComparator {
 public:
  static bool Equals(const Keyframe& aLhs, const Keyframe& aRhs) {
    return aLhs.mComputedOffset == aRhs.mComputedOffset;
  }

  static bool LessThan(const Keyframe& aLhs, const Keyframe& aRhs) {
    return aLhs.mComputedOffset < aRhs.mComputedOffset;
  }
};

// ------------------------------------------------------------------
//
// Internal helper method declarations
//
// ------------------------------------------------------------------

static void GetKeyframeListFromKeyframeSequence(
    JSContext* aCx, dom::Document* aDocument, JS::ForOfIterator& aIterator,
    nsTArray<Keyframe>& aResult, const char* aContext, ErrorResult& aRv);

static bool ConvertKeyframeSequence(JSContext* aCx, dom::Document* aDocument,
                                    JS::ForOfIterator& aIterator,
                                    const char* aContext,
                                    nsTArray<Keyframe>& aResult);

static bool GetPropertyValuesPairs(JSContext* aCx,
                                   JS::Handle<JSObject*> aObject,
                                   ListAllowance aAllowLists,
                                   nsTArray<PropertyValuesPair>& aResult);

static bool AppendStringOrStringSequenceToArray(JSContext* aCx,
                                                JS::Handle<JS::Value> aValue,
                                                ListAllowance aAllowLists,
                                                nsTArray<nsCString>& aValues);

static bool AppendValueAsString(JSContext* aCx, nsTArray<nsCString>& aValues,
                                JS::Handle<JS::Value> aValue);

static Maybe<PropertyValuePair> MakePropertyValuePair(
    const CSSPropertyId& aProperty, const nsACString& aStringValue,
    dom::Document* aDocument);

static bool HasValidOffsets(const nsTArray<Keyframe>& aKeyframes);

#ifdef DEBUG
static void MarkAsComputeValuesFailureKey(PropertyValuePair& aPair);

#endif

static nsTArray<ComputedKeyframeValues> GetComputedKeyframeValues(
    const nsTArray<Keyframe>& aKeyframes, dom::Element* aElement,
    const PseudoStyleRequest& aPseudoRequest,
    const ComputedStyle* aComputedValues);

static void BuildSegmentsFromValueEntries(
    nsTArray<KeyframeValueEntry>& aEntries,
    nsTArray<AnimationProperty>& aResult);

static void GetKeyframeListFromPropertyIndexedKeyframe(
    JSContext* aCx, dom::Document* aDocument, JS::Handle<JS::Value> aValue,
    nsTArray<Keyframe>& aResult, ErrorResult& aRv);

static void DistributeRange(const Range<Keyframe*>& aRange);

static void DoComputeMissingKeyframeOffsets(nsTArray<Keyframe*>& aKeyframes);

static Maybe<Keyframe::OffsetType> ValidateUTF8StringOffset(
    const nsCString& aOffset, ErrorResult& aRv);

static Maybe<Keyframe::OffsetType> ValidateCSSNumericValueOffset(
    const dom::CSSNumericValue& aOffset, ErrorResult& aRv);

static Maybe<Keyframe::OffsetType> ValidateTimelineRangeOffset(
    const dom::TimelineRangeOffset& aOffset, ErrorResult& aRv);

static Maybe<Keyframe::OffsetType> ValidateKeyframeOffset(
    const dom::OwningDoubleOrCSSNumericValueOrTimelineRangeOffsetOrUTF8String&
        aOffset,
    ErrorResult& aRv);

// ------------------------------------------------------------------
//
// Public API
//
// ------------------------------------------------------------------

/* static */
nsTArray<Keyframe> KeyframeUtils::GetKeyframesFromObject(
    JSContext* aCx, dom::Document* aDocument, JS::Handle<JSObject*> aFrames,
    const char* aContext, ErrorResult& aRv) {
  MOZ_ASSERT(!aRv.Failed());

  nsTArray<Keyframe> keyframes;

  if (!aFrames) {
    // The argument was explicitly null meaning no keyframes.
    return keyframes;
  }

  // At this point we know we have an object. We try to convert it to a
  // sequence of keyframes first, and if that fails due to not being iterable,
  // we try to convert it to a property-indexed keyframe.
  JS::Rooted<JS::Value> objectValue(aCx, JS::ObjectValue(*aFrames));
  JS::ForOfIterator iter(aCx);
  if (!iter.init(objectValue, JS::ForOfIterator::AllowNonIterable)) {
    aRv.Throw(NS_ERROR_FAILURE);
    return keyframes;
  }

  if (iter.valueIsIterable()) {
    GetKeyframeListFromKeyframeSequence(aCx, aDocument, iter, keyframes,
                                        aContext, aRv);
  } else {
    GetKeyframeListFromPropertyIndexedKeyframe(aCx, aDocument, objectValue,
                                               keyframes, aRv);
  }

  if (aRv.Failed()) {
    MOZ_ASSERT(keyframes.IsEmpty(),
               "Should not set any keyframes when there is an error");
    return keyframes;
  }

  return keyframes;
}

/* static */
KeyframesOffsetHasAny KeyframeUtils::ComputeMissingKeyframeOffsets(
    nsTArray<Keyframe>& aKeyframes, const dom::AnimationTimeline* aTimeline,
    const dom::AnimationRange* aRange) {
  if (aKeyframes.IsEmpty()) {
    return {false, false};
  }

  // We intentionally maintain a special array of keyframes with double offset
  // or null (i.e. the keyframes without TimelineRangeOffset). We would like to
  // use this array to distribute the keyframes with missing offsets.
  //
  // This part is not specced so we borrow the idea from other browsers, i.e.
  // the missing keyframe offsets are calculated only from double offset.
  nsTArray<Keyframe*> keyframesWithDoubleOrNullOffsets;

  bool hasTimelineRangeOffset = false;
  bool hasNullOrPercentageOffset = false;

  // 1. The 1st pass. We try to resolve the computed offset from offset if
  // provided.
  for (Keyframe& keyframe : aKeyframes) {
    const auto& offset = keyframe.mOffset;
    if (!offset) {
      hasNullOrPercentageOffset = true;
      keyframesWithDoubleOrNullOffsets.AppendElement(&keyframe);
      continue;
    }

    if (offset->IsPercentageOffset()) {
      if (!keyframe.mIsGenerated) {
        hasNullOrPercentageOffset = true;
      }
      keyframesWithDoubleOrNullOffsets.AppendElement(&keyframe);
      keyframe.mComputedOffset = offset->mPercentage;
      continue;
    }

    hasTimelineRangeOffset = true;
    keyframe.mComputedOffset =
        GetComputedOffset(offset.ref(), aTimeline, aRange);
  }

  // 2. The 2nd pass. Follow the spec to compute the missing offsets.
  DoComputeMissingKeyframeOffsets(keyframesWithDoubleOrNullOffsets);

  return {hasTimelineRangeOffset, hasNullOrPercentageOffset};
}

/* static */
double KeyframeUtils::GetComputedOffset(const Keyframe::OffsetType& aOffset,
                                        const dom::AnimationTimeline* aTimeline,
                                        const dom::AnimationRange* aRange) {
  MOZ_ASSERT(aOffset.mRangeName != StyleTimelineRangeName::None &&
                 aOffset.mRangeName != StyleTimelineRangeName::Normal,
             "This is only for keyframe selector with timeline range name");

  if (!aTimeline || !aTimeline->IsViewTimeline()) {
    return std::numeric_limits<double>::quiet_NaN();
  }

  const dom::ViewTimeline* vt = aTimeline->AsViewTimeline();
  const auto offset =
      vt->MapKeyframeOffsetToOffset(aOffset.mRangeName, aOffset.mPercentage);
  if (!offset) {
    return std::numeric_limits<double>::quiet_NaN();
  }

  if (!aRange) {
    return *offset;
  }

  // Attach this keyframe offset, |*offset|, which is calculated based on the
  // whole timeline range, i.e. [0.0, 1.0], to the animation attachment range,
  // i.e. [range.first, range.second], to get the final computed offset.
  //
  // Note: [range.first, range.second] is calculated based on the whole timeline
  // range as well.
  const auto& range = vt->IntervalForAttachmentRange(*aRange);
  return (*offset - range.first) / (range.second - range.first);
}

/* static */
nsTArray<AnimationProperty> KeyframeUtils::GetAnimationPropertiesFromKeyframes(
    const nsTArray<Keyframe>& aKeyframes, dom::Element* aElement,
    const PseudoStyleRequest& aPseudoRequest, const ComputedStyle* aStyle,
    dom::CompositeOperation aEffectComposite,
    const dom::AnimationTimeline* aTimeline,
    const KeyframesOffsetHasAny& aOffsetHasAny) {
  nsTArray<AnimationProperty> result;

  const nsTArray<ComputedKeyframeValues> computedValues =
      GetComputedKeyframeValues(aKeyframes, aElement, aPseudoRequest, aStyle);
  if (computedValues.IsEmpty()) {
    // In rare cases GetComputedKeyframeValues might fail and return an empty
    // array, in which case we likewise return an empty array from here.
    return result;
  }

  MOZ_ASSERT(aKeyframes.Length() == computedValues.Length(),
             "Array length mismatch");

  // If we don't have a timeline or the timeline is not a ViewTimeline, we
  // shouldn't generate the missing keyframes if all keyframes are using
  // TimelineRangeOffsets. Otherwise, we should generate the missing keyframes
  // only if needed.
  const auto& generatedKeyframesStatus =
      CheckSkippableGeneratedKeyframes(aKeyframes, aTimeline, aOffsetHasAny);

  nsTArray<KeyframeValueEntry> entries(aKeyframes.Length());

  const size_t len = aKeyframes.Length();
  for (size_t i = 0; i < len; ++i) {
    const Keyframe& frame = aKeyframes[i];
    // Skip the generated initial or final keyframe if it is not needed.
    if (generatedKeyframesStatus.ShouldSkip(frame)) {
      // FIXME: Bug 2037642. We may need a better way to handle this.
      // For now, we just skip the entire generated keyframes. This is fine for
      // building the propertie segments because we still fill the missing
      // values at 0% and 100% in BuildSegmentsFromValueEntries().
      continue;
    }

    if (frame.IsRangedKeyframe() && std::isnan(frame.mComputedOffset)) {
      // This may happen if the animation doesn't associate with a view
      // timeline, or the timeline is inactive. We just skip this keyframe.
      continue;
    }
    for (auto& value : computedValues[i]) {
      MOZ_ASSERT(!std::isnan(frame.mComputedOffset), "Invalid computed offset");
      KeyframeValueEntry* entry = entries.AppendElement();
      entry->mOffset = frame.mComputedOffset;
      entry->mProperty = value.mProperty;
      entry->mValue = value.mValue;
      entry->mTimingFunction = frame.mTimingFunction;
      // The following assumes that CompositeOperation is a strict subset of
      // CompositeOperationOrAuto.
      entry->mComposite =
          frame.mComposite == dom::CompositeOperationOrAuto::Auto
              ? aEffectComposite
              : static_cast<dom::CompositeOperation>(frame.mComposite);
    }
  }

  BuildSegmentsFromValueEntries(entries, result);
  return result;
}

/* static */
bool KeyframeUtils::IsAnimatableProperty(const CSSPropertyId& aProperty) {
  // Regardless of the backend type, treat the 'display' property as not
  // animatable. (Servo will report it as being animatable, since it is
  // in fact animatable by SMIL.)
  if (aProperty.mId == eCSSProperty_display) {
    return false;
  }
  return Servo_Property_IsAnimatable(&aProperty);
}

/* static */
KeyframeUtils::GeneratedKeyframesStatus
KeyframeUtils::CheckSkippableGeneratedKeyframes(
    const nsTArray<Keyframe>& aKeyframes,
    const dom::AnimationTimeline* aTimeline,
    const KeyframesOffsetHasAny& aOffsetHasAny) {
  if (!aTimeline || !aTimeline->IsViewTimeline()) {
    // The timeline range offsets are not supported for
    // null/doucment-timeline/scroll-timeline, so we shouldn't generate the
    // initial/final keyframes if there is no percentage/null offset.
    return {!aOffsetHasAny.mNonRangeOffset, !aOffsetHasAny.mNonRangeOffset};
  }

  // The quick check if we don't have timeline range offsets in |aKeyframes|.
  if (!aOffsetHasAny.mRangeOffset) {
    return {false, false};
  }

  bool skipInitial = false;
  bool skipFinal = false;
  for (const auto& keyframe : aKeyframes) {
    // Note: The generated keyframe is always percentage offset so this should
    // skip it as as well.
    if (!keyframe.IsRangedKeyframe() || std::isnan(keyframe.mComputedOffset)) {
      continue;
    }

    // It is possible that these attachment points are outside the active
    // interval of the animation; in these cases the automatic from (0%) and to
    // (100%) keyframes are only generated for properties that don’t have
    // keyframes at or earlier than 0% or at or after 100% (respectively).
    // https://drafts.csswg.org/scroll-animations-1/#named-range-keyframes
    if (keyframe.mComputedOffset <= 0.0) {
      skipInitial = true;
    } else if (keyframe.mComputedOffset >= 1.0) {
      skipFinal = true;
    }
  }
  return {skipInitial, skipFinal};
}

// ------------------------------------------------------------------
//
// Internal helpers
//
// ------------------------------------------------------------------

/**
 * Converts a JS object to an IDL sequence<Keyframe>.
 *
 * @param aCx The JSContext corresponding to |aIterator|.
 * @param aDocument The document to use when parsing CSS properties.
 * @param aIterator An already-initialized ForOfIterator for the JS
 *   object to iterate over as a sequence.
 * @param aResult The array into which the resulting Keyframe objects will be
 *   appended.
 * @param aContext The context string to prepend to thrown exceptions.
 * @param aRv Out param to store any errors thrown by this function.
 */
static void GetKeyframeListFromKeyframeSequence(
    JSContext* aCx, dom::Document* aDocument, JS::ForOfIterator& aIterator,
    nsTArray<Keyframe>& aResult, const char* aContext, ErrorResult& aRv) {
  MOZ_ASSERT(!aRv.Failed());
  MOZ_ASSERT(aResult.IsEmpty());

  // Convert the object in aIterator to a sequence of keyframes producing
  // an array of Keyframe objects.
  if (!ConvertKeyframeSequence(aCx, aDocument, aIterator, aContext, aResult)) {
    aResult.Clear();
    aRv.NoteJSContextException(aCx);
    return;
  }

  // If the sequence<> had zero elements, we won't generate any
  // keyframes.
  if (aResult.IsEmpty()) {
    return;
  }

  // Check that the keyframes are loosely sorted and with values all
  // between 0% and 100%.
  if (!HasValidOffsets(aResult)) {
    aResult.Clear();
    aRv.ThrowTypeError<dom::MSG_INVALID_KEYFRAME_OFFSETS>();
    return;
  }
}

/**
 * Converts a JS object wrapped by the given JS::ForIfIterator to an
 * IDL sequence<Keyframe> and stores the resulting Keyframe objects in
 * aResult.
 */
static bool ConvertKeyframeSequence(JSContext* aCx, dom::Document* aDocument,
                                    JS::ForOfIterator& aIterator,
                                    const char* aContext,
                                    nsTArray<Keyframe>& aResult) {
  JS::Rooted<JS::Value> value(aCx);
  // Parsing errors should only be reported after we have finished iterating
  // through all values. If we have any early returns while iterating, we should
  // ignore parsing errors.
  IgnoredErrorResult parseErrorResult;

  for (;;) {
    bool done;
    if (!aIterator.next(&value, &done)) {
      return false;
    }
    if (done) {
      break;
    }
    // Each value found when iterating the object must be an object
    // or null/undefined (which gets treated as a default {} dictionary
    // value).
    if (!value.isObject() && !value.isNullOrUndefined()) {
      dom::ThrowErrorMessage<dom::MSG_NOT_OBJECT>(
          aCx, aContext, "Element of sequence<Keyframe> argument");
      return false;
    }

    // Convert the JS value into a BaseKeyframe dictionary value.
    dom::binding_detail::FastBaseKeyframe keyframeDict;
    dom::BindingCallContext callCx(aCx, aContext);
    if (!keyframeDict.Init(callCx, value,
                           "Element of sequence<Keyframe> argument")) {
      // This may happen if the value type of the member of BaseKeyframe is
      // invalid. e.g. `offset` only accept a double value, so if we provide a
      // string, we enter this branch.
      // Besides, keyframeDict.Init() should throw a Type Error message already,
      // so we don't have to do it again.
      return false;
    }

    Keyframe* keyframe = aResult.AppendElement(fallible);
    if (!keyframe) {
      return false;
    }

    if (!parseErrorResult.Failed() && !keyframeDict.mOffset.IsNull()) {
      if (auto offset = ValidateKeyframeOffset(keyframeDict.mOffset.Value(),
                                               parseErrorResult)) {
        keyframe->mOffset = std::move(offset);
      }
    }

    keyframe->mComposite = keyframeDict.mComposite;

    // Look for additional property-values pairs on the object.
    nsTArray<PropertyValuesPair> propertyValuePairs;
    if (value.isObject()) {
      JS::Rooted<JSObject*> object(aCx, &value.toObject());
      if (!GetPropertyValuesPairs(aCx, object, ListAllowance::eDisallow,
                                  propertyValuePairs)) {
        return false;
      }
    }

    if (!parseErrorResult.Failed()) {
      keyframe->mTimingFunction =
          TimingParams::ParseEasing(keyframeDict.mEasing, parseErrorResult);
      // Even if the above fails, we still need to continue reading off all the
      // properties since checking the validity of easing/offset should be
      // treated as a separate step that happens *after* all the other
      // processing in this loop (since it is never likely to be handled by
      // WebIDL unlike the rest of this loop).
    }

    for (PropertyValuesPair& pair : propertyValuePairs) {
      MOZ_ASSERT(pair.mValues.Length() == 1);

      Maybe<PropertyValuePair> valuePair =
          MakePropertyValuePair(pair.mProperty, pair.mValues[0], aDocument);
      if (!valuePair) {
        continue;
      }
      keyframe->mPropertyValues.AppendElement(std::move(valuePair.ref()));

#ifdef DEBUG
      // When we go to convert keyframes into arrays of property values we
      // call StyleAnimation::ComputeValues. This should normally return true
      // but in order to test the case where it does not, BaseKeyframeDict
      // includes a chrome-only member that can be set to indicate that
      // ComputeValues should fail for shorthand property values on that
      // keyframe.
      if (nsCSSProps::IsShorthand(pair.mProperty.mId) &&
          keyframeDict.mSimulateComputeValuesFailure) {
        MarkAsComputeValuesFailureKey(keyframe->mPropertyValues.LastElement());
      }
#endif
    }
  }

  // Throw any errors we encountered while parsing 'offset' and 'easing'
  // properties.
  if (parseErrorResult.MaybeSetPendingException(aCx)) {
    return false;
  }

  return true;
}

/**
 * Reads the property-values pairs from the specified JS object.
 *
 * @param aObject The JS object to look at.
 * @param aAllowLists If eAllow, values will be converted to
 *   (DOMString or sequence<DOMString); if eDisallow, values
 *   will be converted to DOMString.
 * @param aResult The array into which the enumerated property-values
 *   pairs will be stored.
 * @return false on failure or JS exception thrown while interacting
 *   with aObject; true otherwise.
 */
static bool GetPropertyValuesPairs(JSContext* aCx,
                                   JS::Handle<JSObject*> aObject,
                                   ListAllowance aAllowLists,
                                   nsTArray<PropertyValuesPair>& aResult) {
  nsTArray<AdditionalProperty> properties;

  // Iterate over all the properties on aObject and append an
  // entry to properties for them.
  //
  // We don't compare the jsids that we encounter with those for
  // the explicit dictionary members, since we know that none
  // of the CSS property IDL names clash with them.
  JS::Rooted<JS::IdVector> ids(aCx, JS::IdVector(aCx));
  if (!JS_Enumerate(aCx, aObject, &ids)) {
    return false;
  }
  for (size_t i = 0, n = ids.length(); i < n; i++) {
    nsAutoJSCString propName;
    if (!propName.init(aCx, ids[i])) {
      return false;
    }

    // Basically, we have to handle "cssOffset" and "cssFloat" specially here:
    // "cssOffset" => eCSSProperty_offset
    // "cssFloat"  => eCSSProperty_float
    // This means if the attribute is the string "cssOffset"/"cssFloat", we use
    // CSS "offset"/"float" property.
    // https://drafts.csswg.org/web-animations/#property-name-conversion
    NonCustomCSSPropertyId propertyId =
        NonCustomCSSPropertyId::eCSSProperty_UNKNOWN;
    if (nsCSSProps::IsCustomPropertyName(propName)) {
      propertyId = eCSSPropertyExtra_variable;
    } else if (propName.EqualsLiteral("cssOffset")) {
      propertyId = NonCustomCSSPropertyId::eCSSProperty_offset;
    } else if (propName.EqualsLiteral("cssFloat")) {
      propertyId = NonCustomCSSPropertyId::eCSSProperty_float;
    } else if (!propName.EqualsLiteral("offset") &&
               !propName.EqualsLiteral("float")) {
      propertyId = nsCSSProps::LookupPropertyByIDLName(
          propName, CSSEnabledState::ForAllContent);
    }

    auto property = CSSPropertyId::FromIdOrCustomProperty(propertyId, propName);

    if (KeyframeUtils::IsAnimatableProperty(property)) {
      properties.AppendElement(AdditionalProperty{std::move(property), i});
    }
  }

  // Sort the entries by IDL name and then get each value and
  // convert it either to a DOMString or to a
  // (DOMString or sequence<DOMString>), depending on aAllowLists,
  // and build up aResult.
  properties.Sort(AdditionalProperty::PropertyComparator());

  for (AdditionalProperty& p : properties) {
    JS::Rooted<JS::Value> value(aCx);
    if (!JS_GetPropertyById(aCx, aObject, ids[p.mJsidIndex], &value)) {
      return false;
    }
    PropertyValuesPair* pair = aResult.AppendElement();
    pair->mProperty = p.mProperty;
    if (!AppendStringOrStringSequenceToArray(aCx, value, aAllowLists,
                                             pair->mValues)) {
      return false;
    }
  }

  return true;
}

/**
 * Converts aValue to DOMString, if aAllowLists is eDisallow, or
 * to (DOMString or sequence<DOMString>) if aAllowLists is aAllow.
 * The resulting strings are appended to aValues.
 */
static bool AppendStringOrStringSequenceToArray(JSContext* aCx,
                                                JS::Handle<JS::Value> aValue,
                                                ListAllowance aAllowLists,
                                                nsTArray<nsCString>& aValues) {
  if (aAllowLists == ListAllowance::eAllow && aValue.isObject()) {
    // The value is an object, and we want to allow lists; convert
    // aValue to (DOMString or sequence<DOMString>).
    JS::ForOfIterator iter(aCx);
    if (!iter.init(aValue, JS::ForOfIterator::AllowNonIterable)) {
      return false;
    }
    if (iter.valueIsIterable()) {
      // If the object is iterable, convert it to sequence<DOMString>.
      JS::Rooted<JS::Value> element(aCx);
      for (;;) {
        bool done;
        if (!iter.next(&element, &done)) {
          return false;
        }
        if (done) {
          break;
        }
        if (!AppendValueAsString(aCx, aValues, element)) {
          return false;
        }
      }
      return true;
    }
  }

  // Either the object is not iterable, or aAllowLists doesn't want
  // a list; convert it to DOMString.
  if (!AppendValueAsString(aCx, aValues, aValue)) {
    return false;
  }

  return true;
}

/**
 * Converts aValue to DOMString and appends it to aValues.
 */
static bool AppendValueAsString(JSContext* aCx, nsTArray<nsCString>& aValues,
                                JS::Handle<JS::Value> aValue) {
  return ConvertJSValueToString(aCx, aValue, dom::eStringify, dom::eStringify,
                                *aValues.AppendElement());
}

static void ReportInvalidPropertyValueToConsole(
    const CSSPropertyId& aProperty, const nsACString& aInvalidPropertyValue,
    dom::Document* aDoc) {
  AutoTArray<nsString, 2> params;
  params.AppendElement(NS_ConvertUTF8toUTF16(aInvalidPropertyValue));
  aProperty.ToString(*params.AppendElement());
  nsContentUtils::ReportToConsole(nsIScriptError::warningFlag, "Animation"_ns,
                                  aDoc, PropertiesFile::DOM_PROPERTIES,
                                  "InvalidKeyframePropertyValue", params);
}

/**
 * Construct a PropertyValuePair parsing the given string into a suitable
 * nsCSSValue object.
 *
 * @param aProperty The CSS property.
 * @param aStringValue The property value to parse.
 * @param aDocument The document to use when parsing.
 * @return The constructed PropertyValuePair, or Nothing() if |aStringValue| is
 *   an invalid property value.
 */
static Maybe<PropertyValuePair> MakePropertyValuePair(
    const CSSPropertyId& aProperty, const nsACString& aStringValue,
    dom::Document* aDocument) {
  MOZ_ASSERT(aDocument);
  Maybe<PropertyValuePair> result;

  ServoCSSParser::ParsingEnvironment env =
      ServoCSSParser::GetParsingEnvironment(aDocument);
  RefPtr<StyleLockedDeclarationBlock> servoDeclarationBlock =
      ServoCSSParser::ParseProperty(aProperty, aStringValue, env,
                                    StyleParsingMode::DEFAULT);

  if (servoDeclarationBlock) {
    result.emplace(aProperty, std::move(servoDeclarationBlock));
  } else {
    ReportInvalidPropertyValueToConsole(aProperty, aStringValue, aDocument);
  }
  return result;
}

/**
 * Checks that the given keyframes are loosely ordered (each keyframe's
 * offset that is not null is greater than or equal to the previous
 * non-null offset) and that all values are within the range [0.0, 1.0].
 * Note that the loose ordering and bounds checks have been relaxed to
 * only apply to explicit keyframe offsets (i.e. double offset).
 *
 * @return true if the keyframes' offsets are correctly ordered and
 *   within range; false otherwise.
 */
static bool HasValidOffsets(const nsTArray<Keyframe>& aKeyframes) {
  double offset = 0.0;
  for (const Keyframe& keyframe : aKeyframes) {
    if (keyframe.mOffset) {
      if (!keyframe.mOffset->IsPercentageOffset()) {
        continue;
      }
      double thisOffset = keyframe.mOffset->mPercentage;
      if (thisOffset < offset || thisOffset > 1.0f) {
        return false;
      }
      offset = thisOffset;
    }
  }
  return true;
}

#ifdef DEBUG
/**
 * Takes a property-value pair for a shorthand property and modifies the
 * value to indicate that when we call StyleAnimationValue::ComputeValues on
 * that value we should behave as if that function had failed.
 *
 * @param aPair The PropertyValuePair to modify. |aPair.mProperty| must be
 *              a shorthand property.
 */
static void MarkAsComputeValuesFailureKey(PropertyValuePair& aPair) {
  MOZ_ASSERT(nsCSSProps::IsShorthand(aPair.mProperty.mId),
             "Only shorthand property values can be marked as failure values");

  aPair.mSimulateComputeValuesFailure = true;
}

#endif

/**
 * The variation of the above function. This is for Servo backend.
 */
static nsTArray<ComputedKeyframeValues> GetComputedKeyframeValues(
    const nsTArray<Keyframe>& aKeyframes, dom::Element* aElement,
    const PseudoStyleRequest& aPseudoRequest,
    const ComputedStyle* aComputedStyle) {
  MOZ_ASSERT(aElement);

  nsTArray<ComputedKeyframeValues> result;

  nsPresContext* presContext = nsContentUtils::GetContextForContent(aElement);
  if (!presContext) {
    // This has been reported to happen with some combinations of content
    // (particularly involving resize events and layout flushes? See bug 1407898
    // and bug 1408420) but no reproducible steps have been found.
    // For now we just return an empty array.
    return result;
  }

  result = presContext->StyleSet()->GetComputedKeyframeValuesFor(
      aKeyframes, aElement, aPseudoRequest, aComputedStyle);
  return result;
}

static void AppendInitialSegment(AnimationProperty* aAnimationProperty,
                                 const KeyframeValueEntry& aFirstEntry) {
  AnimationPropertySegment* segment =
      aAnimationProperty->mSegments.AppendElement();
  segment->mFromKey = 0.0f;
  segment->mToKey = aFirstEntry.mOffset;
  segment->mToValue = aFirstEntry.mValue;
  segment->mToComposite = aFirstEntry.mComposite;
}

static void AppendFinalSegment(AnimationProperty* aAnimationProperty,
                               const KeyframeValueEntry& aLastEntry) {
  AnimationPropertySegment* segment =
      aAnimationProperty->mSegments.AppendElement();
  segment->mFromKey = aLastEntry.mOffset;
  segment->mFromValue = aLastEntry.mValue;
  segment->mFromComposite = aLastEntry.mComposite;
  segment->mToKey = 1.0f;
  segment->mTimingFunction = aLastEntry.mTimingFunction;
}

// Returns a newly created AnimationProperty if one was created to fill-in the
// missing keyframe, nullptr otherwise (if we decided not to fill the keyframe
// becase we don't support implicit keyframes).
static AnimationProperty* HandleMissingInitialKeyframe(
    nsTArray<AnimationProperty>& aResult, const KeyframeValueEntry& aEntry) {
  MOZ_ASSERT(aEntry.mOffset > 0.0f,
             "The offset of the entry should be larger than 0.0");

  AnimationProperty* result = aResult.AppendElement();
  result->mProperty = aEntry.mProperty;

  AppendInitialSegment(result, aEntry);

  return result;
}

static void HandleMissingFinalKeyframe(
    nsTArray<AnimationProperty>& aResult, const KeyframeValueEntry& aEntry,
    AnimationProperty* aCurrentAnimationProperty) {
  MOZ_ASSERT(aEntry.mOffset < 1.0f,
             "The offset of the entry should be smaller than 1.0");

  // If |aCurrentAnimationProperty| is nullptr, that means this is the first
  // entry for the property, we have to append a new AnimationProperty for this
  // property.
  if (!aCurrentAnimationProperty) {
    aCurrentAnimationProperty = aResult.AppendElement();
    aCurrentAnimationProperty->mProperty = aEntry.mProperty;

    // If we have only one entry whose offset is neither >= 1 nor <= 0 for this
    // property, we need to append the initial segment as well.
    if (aEntry.mOffset > 0.0f) {
      AppendInitialSegment(aCurrentAnimationProperty, aEntry);
    }
  }
  AppendFinalSegment(aCurrentAnimationProperty, aEntry);
}

/**
 * Builds an array of AnimationProperty objects to represent the keyframe
 * animation segments in aEntries.
 */
static void BuildSegmentsFromValueEntries(
    nsTArray<KeyframeValueEntry>& aEntries,
    nsTArray<AnimationProperty>& aResult) {
  if (aEntries.IsEmpty()) {
    return;
  }

  // Sort the KeyframeValueEntry objects so that all entries for a given
  // property are together, and the entries are sorted by offset otherwise.
  std::stable_sort(aEntries.begin(), aEntries.end(),
                   &KeyframeValueEntry::PropertyOffsetComparator::LessThan);

  // For a given index i, we want to generate a segment from aEntries[i]
  // to aEntries[j], if:
  //
  //   * j > i,
  //   * aEntries[i + 1]'s offset/property is different from aEntries[i]'s, and
  //   * aEntries[j - 1]'s offset/property is different from aEntries[j]'s.
  //
  // That will eliminate runs of same offset/property values where there's no
  // point generating zero length segments in the middle of the animation.
  //
  // Additionally we need to generate a zero length segment at offset 0 and at
  // offset 1, if we have multiple values for a given property at that offset,
  // since we need to retain the very first and very last value so they can
  // be used for reverse and forward filling.
  //
  // Typically, for each property in |aEntries|, we expect there to be at least
  // one KeyframeValueEntry with offset <= 0.0, and at least one with offset
  // >= 1.0. However, since it is possible that when building |aEntries|, the
  // call to StyleAnimationValue::ComputeValues might fail, this can't be
  // guaranteed. Furthermore, if additive animation is disabled, the following
  // loop takes care to identify properties that lack a value at offset 0.0/1.0
  // and drops those properties from |aResult|.

  CSSPropertyId lastProperty(eCSSProperty_UNKNOWN);
  AnimationProperty* animationProperty = nullptr;

  size_t i = 0, n = aEntries.Length();

  while (i < n) {
    // If we've reached the end of the array of entries, synthesize a final (and
    // initial) segment if necessary.
    if (i + 1 == n) {
      if (aEntries[i].mOffset < 1.0f) {
        HandleMissingFinalKeyframe(aResult, aEntries[i], animationProperty);
      } else if (aEntries[i].mOffset >= 1.0f && !animationProperty) {
        // If the last entry with offset >= 1 and no animation property, that
        // means it is the only entry for this property so append a single
        // segment from 0 offset to |aEntry[i].offset|.
        (void)HandleMissingInitialKeyframe(aResult, aEntries[i]);
      }
      animationProperty = nullptr;
      break;
    }

    MOZ_ASSERT(
        aEntries[i].mProperty.IsValid() && aEntries[i + 1].mProperty.IsValid(),
        "Each entry should specify a valid property");

    // No keyframe for this property at offset 0.
    if (aEntries[i].mProperty != lastProperty && aEntries[i].mOffset > 0.0f) {
      // If we don't support additive animation we can't fill in the missing
      // keyframes and we should just skip this property altogether. Since the
      // entries are sorted by offset for a given property, and since we don't
      // update |lastProperty|, we will keep hitting this condition until we
      // change property.
      animationProperty = HandleMissingInitialKeyframe(aResult, aEntries[i]);
      if (animationProperty) {
        lastProperty = aEntries[i].mProperty;
      } else {
        // Skip this entry if we did not handle the missing entry.
        ++i;
        continue;
      }
    }

    // Skip this entry if the next entry has the same offset except for initial
    // and final ones. (This includes offset less than 0.0 or larger than 1.0).
    // We will handle missing keyframe in the next loop if the property is
    // changed on the next entry.
    if (aEntries[i].mProperty == aEntries[i + 1].mProperty &&
        aEntries[i].mOffset == aEntries[i + 1].mOffset &&
        aEntries[i].mOffset != 1.0f && aEntries[i].mOffset != 0.0f) {
      ++i;
      continue;
    }

    // No keyframe for this property at offset 1.
    if (aEntries[i].mProperty != aEntries[i + 1].mProperty &&
        aEntries[i].mOffset < 1.0f) {
      HandleMissingFinalKeyframe(aResult, aEntries[i], animationProperty);
      // Move on to new property.
      animationProperty = nullptr;
      ++i;
      continue;
    }

    // Starting from i + 1, determine the next [i, j] interval from which to
    // generate a segment. Basically, j is i + 1, but there are some special
    // cases for offset == |minCurrentPropertyOffset| and
    // |maxCurrentPropertyOffset|, so we need to handle them specifically.
    // Note: From this moment, we make sure [i + 1] is valid and
    //       there must be an initial entry (i.e. mOffset <= 0.0) and
    //       a final entry (i.e. mOffset >= 1.0). Besides, all the entries
    //       with the same offsets except for initial/final ones are filtered
    //       out already.
    size_t j = i + 1;
    if (aEntries[i].mOffset == 0.0f && aEntries[i + 1].mOffset == 0.0f) {
      // We need to generate an initial zero-length segment.
      MOZ_ASSERT(aEntries[i].mProperty == aEntries[i + 1].mProperty);
      while (j + 1 < n && aEntries[j + 1].mOffset == 0.0f &&
             aEntries[j + 1].mProperty == aEntries[j].mProperty) {
        ++j;
      }
    } else if (aEntries[i].mOffset >= 1.0f) {
      if (aEntries[i].mOffset == 1.0f && aEntries[i + 1].mOffset == 1.0f &&
          aEntries[i + 1].mProperty == aEntries[i].mProperty) {
        // We need to generate a final zero-length segment.
        while (j + 1 < n && aEntries[j + 1].mOffset == 1.0f &&
               aEntries[j + 1].mProperty == aEntries[j].mProperty) {
          ++j;
        }
      } else if (aEntries[i].mProperty != aEntries[i + 1].mProperty) {
        // New property.
        animationProperty = nullptr;
        ++i;
        continue;
      }
    }

    // If we've moved on to a new property, create a new AnimationProperty
    // to insert segments into.
    if (aEntries[i].mProperty != lastProperty) {
      MOZ_ASSERT(aEntries[i].mOffset <= 0.0f);
      MOZ_ASSERT(!animationProperty);
      animationProperty = aResult.AppendElement();
      animationProperty->mProperty = aEntries[i].mProperty;
      lastProperty = aEntries[i].mProperty;
    }

    MOZ_ASSERT(animationProperty, "animationProperty should be valid pointer.");

    // Now generate the segment.
    AnimationPropertySegment* segment =
        animationProperty->mSegments.AppendElement();
    segment->mFromKey = aEntries[i].mOffset;
    segment->mToKey = aEntries[j].mOffset;
    segment->mFromValue = aEntries[i].mValue;
    segment->mToValue = aEntries[j].mValue;
    segment->mTimingFunction = aEntries[i].mTimingFunction;
    segment->mFromComposite = aEntries[i].mComposite;
    segment->mToComposite = aEntries[j].mComposite;

    i = j;
  }
}

/**
 * Converts a JS object representing a property-indexed keyframe into
 * an array of Keyframe objects.
 *
 * @param aCx The JSContext for |aValue|.
 * @param aDocument The document to use when parsing CSS properties.
 * @param aValue The JS object.
 * @param aResult The array into which the resulting AnimationProperty
 *   objects will be appended.
 * @param aRv Out param to store any errors thrown by this function.
 */
static void GetKeyframeListFromPropertyIndexedKeyframe(
    JSContext* aCx, dom::Document* aDocument, JS::Handle<JS::Value> aValue,
    nsTArray<Keyframe>& aResult, ErrorResult& aRv) {
  MOZ_ASSERT(aValue.isObject());
  MOZ_ASSERT(aResult.IsEmpty());
  MOZ_ASSERT(!aRv.Failed());

  // Convert the object to a property-indexed keyframe dictionary to
  // get its explicit dictionary members.
  dom::binding_detail::FastBasePropertyIndexedKeyframe keyframeDict;
  // XXXbz Pass in the method name from callers and set up a BindingCallContext?
  if (!keyframeDict.Init(aCx, aValue, "BasePropertyIndexedKeyframe argument")) {
    aRv.Throw(NS_ERROR_FAILURE);
    return;
  }

  // Get all the property--value-list pairs off the object.
  JS::Rooted<JSObject*> object(aCx, &aValue.toObject());
  nsTArray<PropertyValuesPair> propertyValuesPairs;
  if (!GetPropertyValuesPairs(aCx, object, ListAllowance::eAllow,
                              propertyValuesPairs)) {
    aRv.Throw(NS_ERROR_FAILURE);
    return;
  }

  // Create a set of keyframes for each property.
  nsTHashMap<nsFloatHashKey, Keyframe> processedKeyframes;
  for (const PropertyValuesPair& pair : propertyValuesPairs) {
    size_t count = pair.mValues.Length();
    if (count == 0) {
      // No animation values for this property.
      continue;
    }

    size_t n = pair.mValues.Length() - 1;
    size_t i = 0;

    for (const nsCString& stringValue : pair.mValues) {
      // For single-valued lists, the single value should be added to a
      // keyframe with offset 1.
      double offset = n ? i++ / double(n) : 1;
      Keyframe& keyframe = processedKeyframes.LookupOrInsert(offset);
      if (keyframe.mPropertyValues.IsEmpty()) {
        keyframe.mComputedOffset = offset;
      }

      Maybe<PropertyValuePair> valuePair =
          MakePropertyValuePair(pair.mProperty, stringValue, aDocument);
      if (!valuePair) {
        continue;
      }
      keyframe.mPropertyValues.AppendElement(std::move(valuePair.ref()));
    }
  }

  aResult.SetCapacity(processedKeyframes.Count());
  std::transform(processedKeyframes.begin(), processedKeyframes.end(),
                 MakeBackInserter(aResult), [](auto& entry) {
                   return std::move(*entry.GetModifiableData());
                 });

  aResult.Sort(ComputedOffsetComparator());

  // Fill in any specified offsets
  //
  // This corresponds to step 5, "Otherwise," branch, substeps 5-6 of
  // https://drafts.csswg.org/web-animations/#processing-a-keyframes-argument
  //
  // 5. Let offsets be a sequence of nullable double values assigned based on
  // the type of the offset member of the property-indexed keyframe as follows:
  // Note: Since we replace "double?" with
  // "(CSSNumberish or TimelineRangeOffset or UTF8String)", so we tweak this
  // step to use Nullable<Keyframe::OffsetType>.
  nsTArray<Maybe<Keyframe::OffsetType>> offsets(1);
  if (!keyframeDict.mOffset.IsNull()) {
    const auto& offset = keyframeDict.mOffset.Value();
    if (offset.IsDouble()) {
      offsets.AppendElement(
          Some(Keyframe::OffsetType::PercentageOffset(offset.GetAsDouble())));
    } else if (offset.IsCSSNumericValue()) {
      if (auto result = ValidateCSSNumericValueOffset(
              offset.GetAsCSSNumericValue(), aRv)) {
        offsets.AppendElement(std::move(result));
      }
    } else if (offset.IsTimelineRangeOffset()) {
      if (auto result = ValidateTimelineRangeOffset(
              offset.GetAsTimelineRangeOffset(), aRv)) {
        offsets.AppendElement(std::move(result));
      }
    } else if (offset.IsUTF8String()) {
      if (auto result =
              ValidateUTF8StringOffset(offset.GetAsUTF8String(), aRv)) {
        offsets.AppendElement(std::move(result));
      }
    } else if (
        // Should be a sequence of nullable KeyframeOffset.
        // i.e. sequence<(CSSNumberish or TimelineRangeOffset or UTF8String)?>
        offset
            .IsDoubleOrCSSNumericValueOrTimelineRangeOffsetOrUTF8StringOrNullSequence()) {
      const auto& sequence =
          offset
              .GetAsDoubleOrCSSNumericValueOrTimelineRangeOffsetOrUTF8StringOrNullSequence();
      offsets.SetCapacity(sequence.Length());
      for (const auto& value : sequence) {
        if (value.IsNull()) {
          offsets.AppendElement(Nothing());
          continue;
        }
        auto result = ValidateKeyframeOffset(value.Value(), aRv);
        if (aRv.Failed()) {
          // We got the parse error and so don't have result.
          break;
        }
        MOZ_ASSERT(result);
        offsets.AppendElement(std::move(result));
      }
    }
  }

  // In the spec, TypeErrors arising from invalid offsets are thrown at the end
  // of the procedure. However, it only mentions the loosely sorted check and
  // the range check of the double offset (which will be done below). Therefore,
  // we clear the result and return for parsing errors here tentatively before
  // the check of the valid offset to avoid the redundant operations.
  if (aRv.Failed()) {
    // Note: We throw TypeErrors above already and come here directly so we can
    // just clear the result (just like other places to handle TypeErrors) and
    // return.
    aResult.Clear();
    return;
  }

  // 6. Assign each value in offsets to the keyframe offset of the keyframe with
  // the corresponding position in processed keyframes until the end of either
  // sequence is reached.
  //
  // If keyframeDict.mOffset.IsNull() is true, then we want to leave the mOffset
  // member of each keyframe with its initialized value of null. By leaving
  // |offsets| as nullptr here, we skip updating mOffset below.
  size_t offsetsToFill =
      offsets.IsEmpty() ? 0 : std::min(offsets.Length(), aResult.Length());
  for (size_t i = 0; i < offsetsToFill; i++) {
    if (offsets.ElementAt(i)) {
      std::swap(aResult[i].mOffset, offsets.ElementAt(i));
    }
  }

  // Check that the keyframes are loosely sorted and that any specified offsets
  // are between 0.0 and 1.0 inclusive.
  //
  // This corresponds to steps 6-7 of
  // https://drafts.csswg.org/web-animations/#processing-a-keyframes-argument
  //
  // In the spec, TypeErrors arising from invalid offsets and easings are thrown
  // at the end of the procedure since it assumes we initially store easing
  // values as strings and then later parse them.
  //
  // However, we will parse easing members immediately when we process them
  // below. In order to maintain the relative order in which TypeErrors are
  // thrown according to the spec, namely exceptions arising from invalid
  // offsets are thrown before exceptions arising from invalid easings, we check
  // the offsets here.
  if (!HasValidOffsets(aResult)) {
    aResult.Clear();
    aRv.ThrowTypeError<dom::MSG_INVALID_KEYFRAME_OFFSETS>();
    return;
  }

  // Fill in any easings.
  //
  // This corresponds to step 5, "Otherwise," branch, substeps 7-11 of
  // https://drafts.csswg.org/web-animations/#processing-a-keyframes-argument
  FallibleTArray<Maybe<StyleComputedTimingFunction>> easings;
  auto parseAndAppendEasing = [&](const nsACString& easingString,
                                  ErrorResult& aRv) {
    auto easing = TimingParams::ParseEasing(easingString, aRv);
    if (!aRv.Failed() && !easings.AppendElement(std::move(easing), fallible)) {
      aRv.Throw(NS_ERROR_OUT_OF_MEMORY);
    }
  };

  auto& easing = keyframeDict.mEasing;
  if (easing.IsUTF8String()) {
    parseAndAppendEasing(easing.GetAsUTF8String(), aRv);
    if (aRv.Failed()) {
      aResult.Clear();
      return;
    }
  } else {
    for (const auto& easingString : easing.GetAsUTF8StringSequence()) {
      parseAndAppendEasing(easingString, aRv);
      if (aRv.Failed()) {
        aResult.Clear();
        return;
      }
    }
  }

  // If |easings| is empty, then we are supposed to fill it in with the value
  // "linear" and then repeat the list as necessary.
  //
  // However, for Keyframe.mTimingFunction we represent "linear" as a None
  // value. Since we have not assigned 'mTimingFunction' for any of the
  // keyframes in |aResult| they will already have their initial None value
  // (i.e. linear). As a result, if |easings| is empty, we don't need to do
  // anything.
  if (!easings.IsEmpty()) {
    for (size_t i = 0; i < aResult.Length(); i++) {
      aResult[i].mTimingFunction = easings[i % easings.Length()];
    }
  }

  // Fill in any composite operations.
  //
  // This corresponds to step 5, "Otherwise," branch, substep 12 of
  // https://drafts.csswg.org/web-animations/#processing-a-keyframes-argument
  const FallibleTArray<dom::CompositeOperationOrAuto>* compositeOps = nullptr;
  AutoTArray<dom::CompositeOperationOrAuto, 1> singleCompositeOp;
  auto& composite = keyframeDict.mComposite;
  if (composite.IsCompositeOperationOrAuto()) {
    singleCompositeOp.AppendElement(composite.GetAsCompositeOperationOrAuto());
    const FallibleTArray<dom::CompositeOperationOrAuto>& asFallibleArray =
        singleCompositeOp;
    compositeOps = &asFallibleArray;
  } else if (composite.IsCompositeOperationOrAutoSequence()) {
    compositeOps = &composite.GetAsCompositeOperationOrAutoSequence();
  }

  // Fill in and repeat as needed.
  if (compositeOps && !compositeOps->IsEmpty()) {
    size_t length = compositeOps->Length();
    for (size_t i = 0; i < aResult.Length(); i++) {
      aResult[i].mComposite = compositeOps->ElementAt(i % length);
    }
  }
}

/**
 * Distribute the offsets of all keyframes in between the endpoints of the
 * given range.
 *
 * @param aRange The sequence of keyframes between whose endpoints we should
 * distribute offsets.
 */
static void DistributeRange(const Range<Keyframe*>& aRange) {
  const Range<Keyframe*> rangeToAdjust =
      Range<Keyframe*>(aRange.begin() + 1, aRange.end() - 1);
  const size_t n = aRange.length() - 1;
  const double startOffset = aRange[0]->mComputedOffset;
  const double diffOffset = aRange[n]->mComputedOffset - startOffset;
  for (auto iter = rangeToAdjust.begin(); iter != rangeToAdjust.end(); ++iter) {
    size_t index = iter - aRange.begin();
    (*iter)->mComputedOffset = startOffset + double(index) / n * diffOffset;
  }
}

/**
 * Compute the missing offsets of all keyframes. This follows the spec steps in
 * https://drafts.csswg.org/web-animations-1/#compute-missing-keyframe-offsets.
 * Note that we compute the missing keyframe offsets from the existing keyframes
 * with a double offset (i.e. excluding the keyframes with timeline range
 * names).
 *
 * @param aKeyframes The sequence of keyframes. Note that all of the offsets in
 * this sequence should only be null or double.
 */
static void DoComputeMissingKeyframeOffsets(nsTArray<Keyframe*>& aKeyframes) {
  if (aKeyframes.IsEmpty()) {
    return;
  }

  // If the first keyframe has an unspecified offset, fill it in with 0%.
  // If there is only a single keyframe, then it gets 100%.
  if (aKeyframes.Length() > 1) {
    Keyframe& firstElement = *aKeyframes[0];
    MOZ_ASSERT(!firstElement.mOffset ||
               firstElement.mOffset->IsPercentageOffset());
    firstElement.mComputedOffset =
        firstElement.mOffset ? firstElement.mOffset->mPercentage : 0.0;
    // We will fill in the last keyframe's offset below
  } else {
    Keyframe& lastElement = *aKeyframes.LastElement();
    MOZ_ASSERT(!lastElement.mOffset ||
               lastElement.mOffset->IsPercentageOffset());
    lastElement.mComputedOffset =
        lastElement.mOffset ? lastElement.mOffset->mPercentage : 1.0;
  }

  // Fill in remaining missing offsets.
  const Keyframe* const last = aKeyframes.LastElement();
  const RangedPtr<Keyframe*> begin(aKeyframes.Elements(), aKeyframes.Length());
  RangedPtr<Keyframe*> keyframeA = begin;
  while (*keyframeA != last) {
    // Find keyframe A and keyframe B *between* which we will apply spacing.
    RangedPtr<Keyframe*> keyframeB = keyframeA + 1;
    while ((*keyframeB)->mOffset.isNothing() && *keyframeB != last) {
      ++keyframeB;
    }

    MOZ_ASSERT(!(*keyframeB)->mOffset ||
               (*keyframeB)->mOffset->IsPercentageOffset());
    (*keyframeB)->mComputedOffset =
        (*keyframeB)->mOffset ? (*keyframeB)->mOffset->mPercentage : 1.0;

    // Fill computed offsets in (keyframe A, keyframe B).
    DistributeRange(Range<Keyframe*>(keyframeA, keyframeB + 1));
    keyframeA = keyframeB;
  }
}

/**
 * Validate the keyframe offset as a UTF8String.
 *
 * @param aOffset The UTF8String from JS.
 * @return The validated offset, or null if the offset is invalid.
 */
static Maybe<Keyframe::OffsetType> ValidateUTF8StringOffset(
    const nsCString& aOffset, ErrorResult& aRv) {
  // Parse as <keyframe-selector>:
  //   from | to | <percentage [0,100]> | <timeline-range-name> <percentage>
  // https://drafts.csswg.org/web-animations-2/#keyframe-offset-type
  StyleTimelineRangeName name = StyleTimelineRangeName::None;
  double percentage = 0.0;
  if (!Servo_ParseKeyframeSelector(&aOffset, &name, &percentage)) {
    aRv.ThrowTypeError("Invalid string of the keyframe offset.");
    return Nothing();
  }
  return Some(Keyframe::OffsetType{name, percentage});
}

/**
 * Validate the keyframe offset as a CSSNumericValue. Only percentage is
 * acceptable for now.
 *
 * @param aOffset The CSSNumericValue object from JS.
 * @return The validated offset, or null if the offset is invalid.
 */
static Maybe<Keyframe::OffsetType> ValidateCSSNumericValueOffset(
    const dom::CSSNumericValue& aOffset, ErrorResult& aRv) {
  if (!StaticPrefs::layout_css_typed_om_enabled() ||
      !StaticPrefs::layout_css_scroll_driven_animations_enabled()) {
    aRv.ThrowTypeError(
        "CSSNumericValue is not supported for keyframe offsets.");
    return Nothing();
  }

  RefPtr<dom::CSSUnitValue> asPercent =
      aOffset.GetAsCSSNumericValue().To("percent"_ns, aRv);
  return asPercent ? Some(Keyframe::OffsetType::PercentageOffset(
                         asPercent->Value() / 100.0))
                   : Nothing();
}

/**
 * Validate the TimelineRangeOffset of a keyframe. The syntax of the timeline
 * range should be the same as:
 * "<timeline-range-name> <percentage>", defined in <keyframe-selector>.
 * https://drafts.csswg.org/scroll-animations-1/#named-range-keyframes
 *
 * @param aOffset The TimelineRangeOffset object from JS.
 * @return The validated offset, or null if the offset is invalid.
 */
static Maybe<Keyframe::OffsetType> ValidateTimelineRangeOffset(
    const dom::TimelineRangeOffset& aOffset, ErrorResult& aRv) {
  if (!StaticPrefs::layout_css_typed_om_enabled() ||
      !StaticPrefs::layout_css_scroll_driven_animations_enabled()) {
    aRv.ThrowTypeError(
        "TimelineRagneOffset is not supported for keyframe offsets.");
    return Nothing();
  }

  const auto& rangeName = aOffset.mRangeName;
  const auto& offset = aOffset.mOffset;
  if (!offset.WasPassed()) {
    if (rangeName.WasPassed()) {
      // If the <timeline-range-name> is provided, there must be a
      // <percentage>, otherwse it's an error.
      aRv.ThrowTypeError("Invalid syntax of the timeline range offset.");
    }
    // The same as null offset.
    return Nothing();
  }

  // So now, it is an offset or a pair of range name and offset.
  StyleTimelineRangeName name = StyleTimelineRangeName::None;
  if (rangeName.WasPassed() &&
      !Servo_ParseTimelineRangeName(&rangeName.Value(), &name)) {
    aRv.ThrowTypeError("Invalid string of the timeline range name.");
    return Nothing();
  }
  RefPtr<dom::CSSUnitValue> asPercent = offset.Value().To("percent"_ns, aRv);
  return asPercent
             ? Some(Keyframe::OffsetType{name, asPercent->Value() / 100.0})
             : Nothing();
}

/**
 * Validate the offset of a keyframe.
 * https://drafts.csswg.org/web-animations-2/#keyframe-offset-type
 *
 * @param aOffset The sequence of keyframe offsets from JS.
 * @return The validated offset, or null if the offset is invalid.
 */
static Maybe<Keyframe::OffsetType> ValidateKeyframeOffset(
    const dom::OwningDoubleOrCSSNumericValueOrTimelineRangeOffsetOrUTF8String&
        aOffset,
    ErrorResult& aRv) {
  if (aOffset.IsDouble()) {
    return Some(Keyframe::OffsetType::PercentageOffset(aOffset.GetAsDouble()));
  }

  if (aOffset.IsUTF8String()) {
    return ValidateUTF8StringOffset(aOffset.GetAsUTF8String(), aRv);
  }

  if (aOffset.IsCSSNumericValue()) {
    return ValidateCSSNumericValueOffset(aOffset.GetAsCSSNumericValue(), aRv);
  }

  MOZ_ASSERT(aOffset.IsTimelineRangeOffset());
  return ValidateTimelineRangeOffset(aOffset.GetAsTimelineRangeOffset(), aRv);
}

}  // namespace mozilla