/*
 * Copyright (C) 2013 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "third_party/blink/renderer/core/animation/effect_input.h"

#include "third_party/blink/renderer/bindings/core/v8/dictionary.h"
#include "third_party/blink/renderer/bindings/core/v8/idl_types.h"
#include "third_party/blink/renderer/bindings/core/v8/native_value_traits_impl.h"
#include "third_party/blink/renderer/bindings/core/v8/script_iterator.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_base_keyframe.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_base_property_indexed_keyframe.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_timeline_range.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_timeline_range_offset.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_union_compositeoperationorauto_compositeoperationorautosequence.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_union_double_doubleorstringortimelinerangeoffsetornullsequence_string_timelinerangeoffset_null.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_union_double_string_timelinerangeoffset.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_union_string_stringsequence.h"
#include "third_party/blink/renderer/core/animation/animation_input_helpers.h"
#include "third_party/blink/renderer/core/animation/compositor_animations.h"
#include "third_party/blink/renderer/core/animation/css/css_animations.h"
#include "third_party/blink/renderer/core/animation/keyframe_effect_model.h"
#include "third_party/blink/renderer/core/animation/string_keyframe.h"
#include "third_party/blink/renderer/core/css/css_identifier_value.h"
#include "third_party/blink/renderer/core/css/css_identifier_value_mappings.h"
#include "third_party/blink/renderer/core/css/css_style_sheet.h"
#include "third_party/blink/renderer/core/css/css_value_id_mappings_generated.h"
#include "third_party/blink/renderer/core/css/parser/css_parser.h"
#include "third_party/blink/renderer/core/css/properties/computed_style_utils.h"
#include "third_party/blink/renderer/core/css/properties/css_parsing_utils.h"
#include "third_party/blink/renderer/core/css/resolver/element_resolve_context.h"
#include "third_party/blink/renderer/core/css/style_sheet_contents.h"
#include "third_party/blink/renderer/core/dom/document.h"
#include "third_party/blink/renderer/core/dom/element.h"
#include "third_party/blink/renderer/core/execution_context/security_context.h"
#include "third_party/blink/renderer/core/frame/frame_console.h"
#include "third_party/blink/renderer/core/frame/local_dom_window.h"
#include "third_party/blink/renderer/core/frame/local_frame.h"
#include "third_party/blink/renderer/core/inspector/console_message.h"
#include "third_party/blink/renderer/platform/heap/collection_support/heap_hash_map.h"
#include "third_party/blink/renderer/platform/heap/garbage_collected.h"
#include "third_party/blink/renderer/platform/wtf/hash_map.h"
#include "third_party/blink/renderer/platform/wtf/text/ascii_ctype.h"
#include "third_party/blink/renderer/platform/wtf/text/wtf_string.h"
#include "v8/include/v8.h"

namespace blink {

namespace {

// Names of classes autogenerated from IDL get very long.
// Create shorter aliases.
using BaseKeyframeOffset = V8UnionDoubleOrStringOrTimelineRangeOffset;
using BasePropertyIndexedKeyframeOffset =
    V8UnionDoubleOrDoubleOrStringOrTimelineRangeOffsetOrNullSequenceOrStringOrTimelineRangeOffsetOrNull;

// Converts the composite property of a BasePropertyIndexedKeyframe into a
// vector of std::optional<EffectModel::CompositeOperation> enums.
Vector<std::optional<EffectModel::CompositeOperation>> ParseCompositeProperty(
    const BasePropertyIndexedKeyframe* keyframe) {
  const auto* composite = keyframe->composite();
  switch (composite->GetContentType()) {
    case V8UnionCompositeOperationOrAutoOrCompositeOperationOrAutoSequence::
        ContentType::kCompositeOperationOrAuto:
      return {EffectModel::EnumToCompositeOperation(
          composite->GetAsCompositeOperationOrAuto().AsEnum())};
    case V8UnionCompositeOperationOrAutoOrCompositeOperationOrAutoSequence::
        ContentType::kCompositeOperationOrAutoSequence: {
      Vector<std::optional<EffectModel::CompositeOperation>> result;
      for (const auto& composite_operation :
           composite->GetAsCompositeOperationOrAutoSequence()) {
        result.push_back(EffectModel::EnumToCompositeOperation(
            composite_operation.AsEnum()));
      }
      return result;
    }
  }
  NOTREACHED();
}

struct ParsedOffset {
  TimelineOffset::NamedRange range;
  double relative_offset;
};

std::optional<ParsedOffset> ParseOffsetFromTimelineRangeOffset(
    TimelineRangeOffset* timeline_range_offset,
    ExceptionState& exception_state) {
  ParsedOffset result;
  result.range = timeline_range_offset->hasRangeName()
                     ? timeline_range_offset->rangeName().AsEnum()
                     : TimelineOffset::NamedRange::kNone;
  if (timeline_range_offset->hasOffset()) {
    CSSNumericValue* numeric_value = timeline_range_offset->offset();
    const auto* css_value =
        DynamicTo<CSSPrimitiveValue>(numeric_value->ToCSSValue());

    std::optional<double> percentage;
    if (css_value && css_value->IsPercentage()) {
      percentage = css_value->GetValueIfKnown();
    }
    if (!percentage.has_value()) {
      exception_state.ThrowTypeError(
          "CSSNumericValue must be a percentage, resolvable at parse time, for "
          "a keyframe offset");
      return std::nullopt;
    }
    result.relative_offset = percentage.value() / 100;
  } else {
    exception_state.ThrowTypeError(
        "timeline offset must be a range offset pair.  Missing the offset.");
    return std::nullopt;
  }
  return result;
}

std::optional<ParsedOffset> ParseOffsetFromCssText(
    Document& document,
    String css_text,
    ExceptionState& exception_state) {
  const CSSParserContext* context =
      document.ElementSheet().Contents()->ParserContext();
  CSSParserTokenStream stream(css_text);
  stream.ConsumeWhitespace();

  // <number>
  {
    CSSParserTokenStream::State savepoint = stream.Save();
    const auto* number =
        DynamicTo<CSSPrimitiveValue>(css_parsing_utils::ConsumeNumber(
            stream, *context, CSSPrimitiveValue::ValueRange::kAll));

    if (number && stream.AtEnd()) {
      std::optional<double> offset = number->GetValueIfKnown();
      if (!offset.has_value()) {
        return std::nullopt;
      }
      return ParsedOffset({TimelineOffset::NamedRange::kNone, offset.value()});
    }
    stream.Restore(savepoint);
  }

  // <percent>
  {
    CSSParserTokenStream::State savepoint = stream.Save();
    const CSSPrimitiveValue* percent =
        DynamicTo<CSSPrimitiveValue>(css_parsing_utils::ConsumePercent(
            stream, *context, CSSPrimitiveValue::ValueRange::kAll));
    if (percent && stream.AtEnd()) {
      std::optional<double> percentage = percent->GetValueIfKnown();
      if (!percentage.has_value()) {
        return std::nullopt;
      }
      return ParsedOffset(
          {TimelineOffset::NamedRange::kNone, percentage.value() / 100});
    }
    stream.Restore(savepoint);
  }

  // <range-name> <percent>
  auto* range_name_percent = To<CSSValueList>(
      css_parsing_utils::ConsumeTimelineRangeNameAndPercent(stream, *context));
  if (range_name_percent && stream.AtEnd()) {
    TimelineOffset::NamedRange range =
        To<CSSIdentifierValue>(range_name_percent->Item(0))
            .ConvertTo<TimelineOffset::NamedRange>();
    std::optional<double> relative_offset =
        To<CSSPrimitiveValue>(range_name_percent->Item(1)).GetValueIfKnown();
    if (relative_offset.has_value()) {
      return ParsedOffset({range, relative_offset.value() / 100});
    }
  }

  exception_state.ThrowTypeError(
      "timeline offset must be of the form [timeline-range-name] "
      "<percentage>");
  return std::nullopt;
}

template <typename T>
std::optional<ParsedOffset> ParseOffset(Document& document,
                                        T* keyframe_offset,
                                        ExceptionState& exception_state) {
  if (!keyframe_offset) {
    return std::nullopt;
  }

  if (keyframe_offset->IsDouble()) {
    return ParsedOffset(
        {TimelineOffset::NamedRange::kNone, keyframe_offset->GetAsDouble()});
  }

  if (keyframe_offset->IsTimelineRangeOffset()) {
    return ParseOffsetFromTimelineRangeOffset(
        keyframe_offset->GetAsTimelineRangeOffset(), exception_state);
  }

  if (keyframe_offset->IsString()) {
    return ParseOffsetFromCssText(document, keyframe_offset->GetAsString(),
                                  exception_state);
  }

  // If calling using a PropertyIndexKeyframe, we must already have handled
  // sequences.
  NOTREACHED();
}

void SetKeyframeOffset(Keyframe& keyframe, ParsedOffset& offset) {
  if (offset.range == V8TimelineRange::Enum::kNone) {
    keyframe.SetOffset(offset.relative_offset);
  } else {
    TimelineOffset timeline_offset(
        offset.range, Length::Percent(100 * offset.relative_offset));
    keyframe.SetTimelineOffset(timeline_offset);
  }
}

Vector<std::optional<ParsedOffset>> ExtractPropertyIndexedKeyframeOffsets(
    Document& document,
    BasePropertyIndexedKeyframe& base_property_indexed_keyframe,
    ExceptionState& exception_state) {
  Vector<std::optional<ParsedOffset>> offsets;

  if (!base_property_indexed_keyframe.hasOffset()) {
    return offsets;
  }

  BasePropertyIndexedKeyframeOffset* keyframe_offset =
      base_property_indexed_keyframe.offset();

  if (keyframe_offset->IsNull()) {
    return offsets;
  }

  if (keyframe_offset->IsDoubleOrStringOrTimelineRangeOffsetOrNullSequence()) {
    // iterate through all offsets in the list.
    const HeapVector<Member<BaseKeyframeOffset>>& list =
        keyframe_offset
            ->GetAsDoubleOrStringOrTimelineRangeOffsetOrNullSequence();
    for (BaseKeyframeOffset* base_keyframe_offset : list) {
      std::optional<ParsedOffset> parsed_offset =
          ParseOffset(document, base_keyframe_offset, exception_state);
      offsets.push_back(parsed_offset);
    }
    return offsets;
  }

  std::optional<ParsedOffset> parsed_offset =
      ParseOffset(document, keyframe_offset, exception_state);
  offsets.push_back(parsed_offset);
  return offsets;
}

void SetKeyframeValue(Document& document,
                      StringKeyframe& keyframe,
                      const String& property,
                      const String& value,
                      ExecutionContext* execution_context) {
  StyleSheetContents* style_sheet_contents = document.ElementSheet().Contents();
  CSSPropertyID css_property =
      AnimationInputHelpers::KeyframeAttributeToCSSProperty(property, document);
  SecureContextMode secure_context_mode =
      document.GetExecutionContext()
          ? document.GetExecutionContext()->GetSecureContextMode()
          : SecureContextMode::kInsecureContext;
  if (css_property != CSSPropertyID::kInvalid) {
    MutableCSSPropertyValueSet::SetResult set_result =
        css_property == CSSPropertyID::kVariable
            ? keyframe.SetCSSPropertyValue(AtomicString(property), value,
                                           secure_context_mode,
                                           style_sheet_contents)
            : keyframe.SetCSSPropertyValue(css_property, value,
                                           secure_context_mode,
                                           style_sheet_contents);
    if (set_result == MutableCSSPropertyValueSet::kParseError &&
        execution_context) {
      if (document.GetFrame()) {
        document.GetFrame()->Console().AddMessage(
            MakeGarbageCollected<ConsoleMessage>(
                mojom::ConsoleMessageSource::kJavaScript,
                mojom::ConsoleMessageLevel::kWarning,
                "Invalid keyframe value for property " + property + ": " +
                    value));
      }
    }
  }
}

bool IsAnimatableKeyframeAttribute(const String& property,
                                   const Document& document) {
  CSSPropertyID css_property =
      AnimationInputHelpers::KeyframeAttributeToCSSProperty(property, document);
  if (css_property == CSSPropertyID::kInvalid) {
    return false;
  }

  return !CSSAnimations::IsAnimationAffectingProperty(
      CSSProperty::Get(css_property));
}

void AddPropertyValuePairsForKeyframe(
    v8::Isolate* isolate,
    v8::Local<v8::Object> keyframe_obj,
    const Document& document,
    Vector<std::pair<String, String>>& property_value_pairs,
    ExceptionState& exception_state) {
  Vector<String> keyframe_properties =
      GetOwnPropertyNames(isolate, keyframe_obj, exception_state);
  if (exception_state.HadException())
    return;

  // By spec, we must sort the properties in "ascending order by the Unicode
  // codepoints that define each property name."
  std::sort(keyframe_properties.begin(), keyframe_properties.end(),
            WTF::CodeUnitCompareLessThan);

  TryRethrowScope rethrow_scope(isolate, exception_state);
  for (const auto& property : keyframe_properties) {
    if (property == "offset" || property == "float" ||
        property == "composite" || property == "easing") {
      continue;
    }

    // By spec, we are not allowed to access any non-animatable property.
    if (!IsAnimatableKeyframeAttribute(property, document)) {
      continue;
    }

    // By spec, we are only allowed to access a given (property, value) pair
    // once. This is observable by the web client, so we take care to adhere
    // to that.
    v8::Local<v8::Value> v8_value;
    if (!keyframe_obj
             ->Get(isolate->GetCurrentContext(), V8String(isolate, property))
             .ToLocal(&v8_value)) {
      return;
    }

    if (v8_value->IsArray()) {
      // Since allow-lists is false, array values should be ignored.
      continue;
    }

    String string_value = NativeValueTraits<IDLString>::NativeValue(
        isolate, v8_value, exception_state);
    if (exception_state.HadException())
      return;
    property_value_pairs.push_back(std::make_pair(property, string_value));
  }
}

StringKeyframeVector ConvertArrayForm(Document& document,
                                      ScriptIterator iterator,
                                      ScriptState* script_state,
                                      ExceptionState& exception_state) {
  v8::Isolate* isolate = script_state->GetIsolate();

  // https://www.w3.org/TR/web-animations-1/#processing-a-keyframes-argument
  // This implementation relaxes steps 6 and 7, which require the keyframes to
  // be loosely sorted and bounded between 0 and 1.  The sorting and bounds
  // only apply to keyframes without timeline offsets.

  // This loop captures step 5 of the procedure to process a keyframes argument,
  // in the case where the argument is iterable.
  HeapVector<Member<const BaseKeyframe>> processed_base_keyframes;
  Vector<Vector<std::pair<String, String>>> processed_properties;
  ExecutionContext* execution_context = ExecutionContext::From(script_state);
  while (iterator.Next(execution_context, exception_state)) {
    CHECK(!exception_state.HadException());

    // The value should already be non-empty, as guaranteed by the call to Next
    // and the exception_state check above.
    v8::Local<v8::Value> keyframe = iterator.GetValue().ToLocalChecked();

    if (!keyframe->IsObject() && !keyframe->IsNullOrUndefined()) {
      exception_state.ThrowTypeError(
          "Keyframes must be objects, or null or undefined");
      return {};
    }

    BaseKeyframe* base_keyframe = NativeValueTraits<BaseKeyframe>::NativeValue(
        isolate, keyframe, exception_state);
    Vector<std::pair<String, String>> property_value_pairs;
    if (exception_state.HadException())
      return {};

    if (!keyframe->IsNullOrUndefined()) {
      AddPropertyValuePairsForKeyframe(
          isolate, v8::Local<v8::Object>::Cast(keyframe), document,
          property_value_pairs, exception_state);
      if (exception_state.HadException())
        return {};
    }

    processed_base_keyframes.push_back(base_keyframe);
    processed_properties.push_back(property_value_pairs);
  }
  // If the very first call to next() throws the above loop will never be
  // entered, so we have to catch that here.
  if (exception_state.HadException())
    return {};

  // 6. If processed keyframes is not loosely sorted by offset, throw a
  //    TypeError and abort these steps.
  double previous_offset = -std::numeric_limits<double>::infinity();
  Vector<std::optional<ParsedOffset>> offsets;
  const wtf_size_t num_processed_keyframes = processed_base_keyframes.size();
  for (wtf_size_t i = 0; i < num_processed_keyframes; ++i) {
    const BaseKeyframe* base_keyframe = processed_base_keyframes[i];
    std::optional<ParsedOffset> offset =
        ParseOffset(document, base_keyframe->offset(), exception_state);
    if (exception_state.HadException()) {
      return {};
    }
    offsets.push_back(offset);

    if (!offset || offset->range != TimelineOffset::NamedRange::kNone) {
      continue;
    }

    double numeric_offset = offset->relative_offset;
    if (numeric_offset < previous_offset) {
      exception_state.ThrowTypeError(
          "Offsets must be monotonically non-decreasing.");
      return {};
    }
    previous_offset = numeric_offset;
  }

  // 7. If there exist any keyframe in processed keyframes whose keyframe
  //    offset is non-null and less than zero or greater than one, throw a
  //    TypeError and abort these steps.
  for (wtf_size_t i = 0; i < num_processed_keyframes; ++i) {
    std::optional<ParsedOffset> offset = offsets[i];
    if (!offset || offset->range != TimelineOffset::NamedRange::kNone) {
      continue;
    }

    double numeric_offset = offset->relative_offset;
    if (numeric_offset < 0 || numeric_offset > 1) {
      exception_state.ThrowTypeError(
          "Offsets must be null or in the range [0,1].");
      return {};
    }
  }

  StringKeyframeVector keyframes;
  for (wtf_size_t i = 0; i < num_processed_keyframes; ++i) {
    // Now we create the actual Keyframe object. We start by assigning the
    // offset and composite values; conceptually these were actually added in
    // step 5 above but we didn't have a keyframe object then.
    auto* keyframe = MakeGarbageCollected<StringKeyframe>();
    if (offsets[i]) {
      SetKeyframeOffset(*keyframe, offsets[i].value());
    }

    // 8.1. For each property-value pair in frame, parse the property value
    // using the syntax specified for that property.
    const BaseKeyframe* base_keyframe = processed_base_keyframes[i];
    for (const auto& pair : processed_properties[i]) {
      // TODO(crbug.com/777971): Make parsing of property values spec-compliant.
      SetKeyframeValue(document, *keyframe, pair.first, pair.second,
                       execution_context);
    }

    std::optional<EffectModel::CompositeOperation> composite =
        EffectModel::EnumToCompositeOperation(
            base_keyframe->composite().AsEnum());
    if (composite) {
      keyframe->SetComposite(composite.value());
    }

    // 8.2. Let the timing function of frame be the result of parsing the
    // “easing” property on frame using the CSS syntax defined for the easing
    // property of the AnimationEffectTimingReadOnly interface.
    //
    // If parsing the “easing” property fails, throw a TypeError and abort this
    // procedure.
    scoped_refptr<TimingFunction> timing_function =
        AnimationInputHelpers::ParseTimingFunction(base_keyframe->easing(),
                                                   &document, exception_state);
    if (!timing_function)
      return {};
    keyframe->SetEasing(timing_function);

    keyframes.push_back(keyframe);
  }

  DCHECK(!exception_state.HadException());
  return keyframes;
}

// Extracts the values for a given property in the input keyframes. As per the
// spec property values for the object-notation form have type (DOMString or
// sequence<DOMString>).
bool GetPropertyIndexedKeyframeValues(const v8::Local<v8::Object>& keyframe,
                                      const String& property,
                                      ScriptState* script_state,
                                      ExceptionState& exception_state,
                                      Vector<String>& result) {
  DCHECK(result.empty());

  // By spec, we are only allowed to access a given (property, value) pair once.
  // This is observable by the web client, so we take care to adhere to that.
  v8::Local<v8::Value> v8_value;
  v8::Local<v8::Context> context = script_state->GetContext();
  v8::Isolate* isolate = script_state->GetIsolate();
  TryRethrowScope rethrow_scope(isolate, exception_state);
  if (!keyframe->Get(context, V8String(isolate, property)).ToLocal(&v8_value)) {
    return {};
  }

  auto* string_or_string_sequence =
      V8UnionStringOrStringSequence::Create(isolate, v8_value, exception_state);
  if (exception_state.HadException())
    return false;

  switch (string_or_string_sequence->GetContentType()) {
    case V8UnionStringOrStringSequence::ContentType::kString:
      result.push_back(string_or_string_sequence->GetAsString());
      break;
    case V8UnionStringOrStringSequence::ContentType::kStringSequence:
      result = string_or_string_sequence->GetAsStringSequence();
      break;
  }

  return true;
}

// Implements the procedure to "process a keyframes argument" from the
// web-animations spec for an object form keyframes argument.
//
// See https://w3.org/TR/web-animations-1/#processing-a-keyframes-argument
StringKeyframeVector ConvertObjectForm(Element* element,
                                       Document& document,
                                       const v8::Local<v8::Object>& v8_keyframe,
                                       ScriptState* script_state,
                                       ExceptionState& exception_state) {
  // We implement much of this procedure out of order from the way the spec is
  // written, to avoid repeatedly going over the list of keyframes.
  // The web-observable behavior should be the same as the spec.

  // Extract the offset, easing, and composite as per step 1 of the 'procedure
  // to process a keyframe-like object'.
  BasePropertyIndexedKeyframe* property_indexed_keyframe =
      NativeValueTraits<BasePropertyIndexedKeyframe>::NativeValue(
          script_state->GetIsolate(), v8_keyframe, exception_state);
  if (exception_state.HadException())
    return {};

  Vector<std::optional<ParsedOffset>> offsets =
      ExtractPropertyIndexedKeyframeOffsets(
          document, *property_indexed_keyframe, exception_state);
  if (exception_state.HadException()) {
    return {};
  }

  // The web-animations spec explicitly states that easings should be kept as
  // DOMStrings here and not parsed into timing functions until later.
  Vector<String> easings;
  if (property_indexed_keyframe->easing()->IsString())
    easings.push_back(property_indexed_keyframe->easing()->GetAsString());
  else
    easings = property_indexed_keyframe->easing()->GetAsStringSequence();

  Vector<std::optional<EffectModel::CompositeOperation>> composite_operations =
      ParseCompositeProperty(property_indexed_keyframe);

  // Next extract all animatable properties from the input argument and iterate
  // through them, processing each as a list of values for that property. This
  // implements both steps 2-7 of the 'procedure to process a keyframe-like
  // object' and step 5.2 of the 'procedure to process a keyframes argument'.

  Vector<String> keyframe_properties = GetOwnPropertyNames(
      script_state->GetIsolate(), v8_keyframe, exception_state);
  if (exception_state.HadException())
    return {};

  // Steps 5.2 - 5.4 state that the user agent is to:
  //
  //   * Create sets of 'property keyframes' with no offset.
  //   * Calculate computed offsets for each set of keyframes individually.
  //   * Join the sets together and merge those with identical computed offsets.
  //
  // This is equivalent to just keeping a hashmap from computed offset to a
  // single keyframe, which simplifies the parsing logic.
  HeapHashMap<double, Member<StringKeyframe>> keyframes;

  // By spec, we must sort the properties in "ascending order by the Unicode
  // codepoints that define each property name."
  std::sort(keyframe_properties.begin(), keyframe_properties.end(),
            WTF::CodeUnitCompareLessThan);

  for (const auto& property : keyframe_properties) {
    if (property == "offset" || property == "float" ||
        property == "composite" || property == "easing") {
      continue;
    }

    // By spec, we are not allowed to access any non-animatable property.
    if (!IsAnimatableKeyframeAttribute(property, document)) {
      continue;
    }

    Vector<String> values;
    if (!GetPropertyIndexedKeyframeValues(v8_keyframe, property, script_state,
                                          exception_state, values)) {
      return {};
    }

    // Now create a keyframe (or retrieve and augment an existing one) for each
    // value this property maps to. As explained above, this loop performs both
    // the initial creation and merging mentioned in the spec.
    wtf_size_t num_keyframes = values.size();
    ExecutionContext* execution_context = ExecutionContext::From(script_state);
    for (wtf_size_t i = 0; i < num_keyframes; ++i) {
      // As all offsets are null for these 'property keyframes', the computed
      // offset is just the fractional position of each keyframe in the array.
      //
      // The only special case is that when there is only one keyframe the sole
      // computed offset is defined as 1.
      double computed_offset =
          (num_keyframes == 1) ? 1 : i / double(num_keyframes - 1);

      auto result = keyframes.insert(computed_offset, nullptr);
      if (result.is_new_entry)
        result.stored_value->value = MakeGarbageCollected<StringKeyframe>();

      SetKeyframeValue(document, *result.stored_value->value, property,
                       values[i], execution_context);
    }
  }

  // 5.3 Sort processed keyframes by the computed keyframe offset of each
  // keyframe in increasing order.
  Vector<double> keys(keyframes.Keys());
  std::sort(keys.begin(), keys.end());

  // Steps 5.5 - 5.12 deal with assigning the user-specified offset, easing, and
  // composite properties to the keyframes.
  //
  // This loop also implements steps 6, 7, and 8 of the spec. Because nothing is
  // user-observable at this point, we can operate out of order. Note that this
  // may result in us throwing a different order of TypeErrors than other user
  // agents[1], but as all exceptions are TypeErrors this is not observable by
  // the web client.
  //
  // [1] E.g. if the offsets are [2, 0] we will throw due to the first offset
  //     being > 1 before we throw due to the offsets not being loosely ordered.
  StringKeyframeVector results;
  double previous_offset = 0.0;
  for (wtf_size_t i = 0; i < keys.size(); i++) {
    auto* keyframe = keyframes.at(keys[i]);

    if (i < offsets.size()) {
      std::optional<ParsedOffset> parsed_offset = offsets[i];
      std::optional<double> numeric_offset;
      if (parsed_offset.has_value() &&
          parsed_offset.value().range == TimelineOffset::NamedRange::kNone) {
        numeric_offset = parsed_offset.value().relative_offset;
      }

      // 6. If processed keyframes is not loosely sorted by offset, throw a
      // TypeError and abort these steps.
      if (numeric_offset.has_value()) {
        if (numeric_offset.value() < previous_offset) {
          exception_state.ThrowTypeError(
              "Offsets must be monotonically non-decreasing.");
          return {};
        }
        previous_offset = numeric_offset.value();
      }

      // 7. If there exist any keyframe in processed keyframes whose keyframe
      // offset is non-null and less than zero or greater than one, throw a
      // TypeError and abort these steps.
      if (numeric_offset.has_value() &&
          (numeric_offset.value() < 0 || numeric_offset.value() > 1)) {
        exception_state.ThrowTypeError(
            "Offsets must be null or in the range [0,1].");
        return {};
      }
      if (parsed_offset) {
        SetKeyframeOffset(*keyframe, parsed_offset.value());
      }
    }

    // At this point in the code we have read all the properties we will read
    // from the input object, so it is safe to parse the easing strings. See the
    // note on step 8.2.
    if (!easings.empty()) {
      // 5.9 If easings has fewer items than property keyframes, repeat the
      // elements in easings successively starting from the beginning of the
      // list until easings has as many items as property keyframes.
      const String& easing = easings[i % easings.size()];

      // 8.2 Let the timing function of frame be the result of parsing the
      // "easing" property on frame using the CSS syntax defined for the easing
      // property of the AnimationEffectTimingReadOnly interface.
      //
      // If parsing the “easing” property fails, throw a TypeError and abort
      // this procedure.
      scoped_refptr<TimingFunction> timing_function =
          AnimationInputHelpers::ParseTimingFunction(easing, &document,
                                                     exception_state);
      if (!timing_function)
        return {};

      keyframe->SetEasing(timing_function);
    }

    if (!composite_operations.empty()) {
      // 5.12.2 As with easings, if composite modes has fewer items than
      // property keyframes, repeat the elements in composite modes successively
      // starting from the beginning of the list until composite modes has as
      // many items as property keyframes.
      std::optional<EffectModel::CompositeOperation> composite =
          composite_operations[i % composite_operations.size()];
      if (composite) {
        keyframe->SetComposite(composite.value());
      }
    }

    results.push_back(keyframe);
  }

  // Step 8 of the spec is done above (or will be): parsing property values
  // according to syntax for the property (discarding with console warning on
  // fail) and parsing each easing property.
  // TODO(crbug.com/777971): Fix parsing of property values to adhere to spec.

  // 9. Parse each of the values in unused easings using the CSS syntax defined
  // for easing property of the AnimationEffectTimingReadOnly interface, and if
  // any of the values fail to parse, throw a TypeError and abort this
  // procedure.
  for (wtf_size_t i = results.size(); i < easings.size(); i++) {
    scoped_refptr<TimingFunction> timing_function =
        AnimationInputHelpers::ParseTimingFunction(easings[i], &document,
                                                   exception_state);
    if (!timing_function)
      return {};
  }

  DCHECK(!exception_state.HadException());
  return results;
}

}  // namespace

KeyframeEffectModelBase* EffectInput::Convert(
    Element* element,
    const ScriptValue& keyframes,
    EffectModel::CompositeOperation composite,
    ScriptState* script_state,
    ExceptionState& exception_state) {
  StringKeyframeVector parsed_keyframes =
      ParseKeyframesArgument(element, keyframes, script_state, exception_state);
  if (exception_state.HadException())
    return nullptr;

  return MakeGarbageCollected<StringKeyframeEffectModel>(
      parsed_keyframes, composite, LinearTimingFunction::Shared());
}

StringKeyframeVector EffectInput::ParseKeyframesArgument(
    Element* element,
    const ScriptValue& keyframes,
    ScriptState* script_state,
    ExceptionState& exception_state) {
  // Per the spec, a null keyframes object maps to a valid but empty sequence.
  v8::Local<v8::Value> keyframes_value = keyframes.V8Value();
  if (keyframes_value->IsNullOrUndefined())
    return {};
  v8::Local<v8::Object> keyframes_obj = keyframes_value.As<v8::Object>();

  // 3. Let method be the result of GetMethod(object, @@iterator).
  v8::Isolate* isolate = script_state->GetIsolate();
  auto script_iterator = ScriptIterator::FromIterable(
      isolate, keyframes_obj, exception_state, ScriptIterator::Kind::kSync);
  if (exception_state.HadException())
    return {};

  // TODO(crbug.com/816934): Get spec to specify what parsing context to use.
  Document& document = element
                           ? element->GetDocument()
                           : *LocalDOMWindow::From(script_state)->document();

  // Map logical to physical properties.
  const ComputedStyle* style = element ? element->GetComputedStyle() : nullptr;
  WritingDirectionMode writing_direction =
      style ? style->GetWritingDirection()
            : WritingDirectionMode(WritingMode::kHorizontalTb,
                                   TextDirection::kLtr);

  StringKeyframeVector parsed_keyframes;
  if (script_iterator.IsNull()) {
    parsed_keyframes = ConvertObjectForm(element, document, keyframes_obj,
                                         script_state, exception_state);
  } else {
    parsed_keyframes = ConvertArrayForm(document, std::move(script_iterator),
                                        script_state, exception_state);
  }

  for (wtf_size_t i = 0; i < parsed_keyframes.size(); i++) {
    StringKeyframe* keyframe = parsed_keyframes[i];
    keyframe->SetLogicalPropertyResolutionContext(writing_direction);
  }

  return parsed_keyframes;
}

}  // namespace blink