| // Copyright 2015 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "third_party/blink/renderer/core/animation/list_interpolation_functions.h" |
| |
| #include <memory> |
| #include "base/callback.h" |
| #include "third_party/blink/renderer/core/animation/underlying_value_owner.h" |
| #include "third_party/blink/renderer/core/css/css_value_list.h" |
| #include "third_party/blink/renderer/platform/wtf/math_extras.h" |
| |
| namespace blink { |
| |
| DEFINE_NON_INTERPOLABLE_VALUE_TYPE(NonInterpolableList); |
| |
| const wtf_size_t kRepeatableListMaxLength = 1000; |
| |
| // An UnderlyingValue used for compositing list items. |
| // |
| // When new NonInterpolableValues are set, the NonInterpolableList::AutoBuilder |
| // is modified at the corresponding index. The NonInterpolableValue of the |
| // underlying_list is updated when the AutoBuilder goes out of scope (if |
| // any calls to UnderlyingItemValue::SetNonInterpolableValue were made). |
| class UnderlyingItemValue : public UnderlyingValue { |
| STACK_ALLOCATED(); |
| |
| public: |
| UnderlyingItemValue(UnderlyingValue& underlying_list, |
| NonInterpolableList::AutoBuilder& builder, |
| wtf_size_t index) |
| : underlying_list_(underlying_list), builder_(builder), index_(index) {} |
| |
| InterpolableValue& MutableInterpolableValue() final { |
| return *To<InterpolableList>(underlying_list_.MutableInterpolableValue()) |
| .GetMutable(index_); |
| } |
| void SetInterpolableValue( |
| std::unique_ptr<InterpolableValue> interpolable_value) final { |
| To<InterpolableList>(underlying_list_.MutableInterpolableValue()) |
| .Set(index_, std::move(interpolable_value)); |
| } |
| const NonInterpolableValue* GetNonInterpolableValue() const final { |
| return ToNonInterpolableList(*underlying_list_.GetNonInterpolableValue()) |
| .Get(index_); |
| } |
| void SetNonInterpolableValue( |
| scoped_refptr<const NonInterpolableValue> non_interpolable_value) final { |
| builder_.Set(index_, std::move(non_interpolable_value)); |
| } |
| |
| private: |
| UnderlyingValue& underlying_list_; |
| NonInterpolableList::AutoBuilder& builder_; |
| wtf_size_t index_; |
| }; |
| |
| bool ListInterpolationFunctions::EqualValues( |
| const InterpolationValue& a, |
| const InterpolationValue& b, |
| EqualNonInterpolableValuesCallback equal_non_interpolable_values) { |
| if (!a && !b) |
| return true; |
| |
| if (!a || !b) |
| return false; |
| |
| const auto& interpolable_list_a = To<InterpolableList>(*a.interpolable_value); |
| const auto& interpolable_list_b = To<InterpolableList>(*b.interpolable_value); |
| |
| if (interpolable_list_a.length() != interpolable_list_b.length()) |
| return false; |
| |
| wtf_size_t length = interpolable_list_a.length(); |
| if (length == 0) |
| return true; |
| |
| const NonInterpolableList& non_interpolable_list_a = |
| ToNonInterpolableList(*a.non_interpolable_value); |
| const NonInterpolableList& non_interpolable_list_b = |
| ToNonInterpolableList(*b.non_interpolable_value); |
| |
| for (wtf_size_t i = 0; i < length; i++) { |
| if (!equal_non_interpolable_values(non_interpolable_list_a.Get(i), |
| non_interpolable_list_b.Get(i))) |
| return false; |
| } |
| return true; |
| } |
| |
| static wtf_size_t MatchLengths( |
| wtf_size_t start_length, |
| wtf_size_t end_length, |
| ListInterpolationFunctions::LengthMatchingStrategy |
| length_matching_strategy) { |
| if (length_matching_strategy == |
| ListInterpolationFunctions::LengthMatchingStrategy::kEqual) { |
| DCHECK_EQ(start_length, end_length); |
| return start_length; |
| } else if (length_matching_strategy == |
| ListInterpolationFunctions::LengthMatchingStrategy:: |
| kLowestCommonMultiple) { |
| // Combining the length expansion of lowestCommonMultiple with CSS |
| // transitions has the potential to create pathological cases where this |
| // algorithm compounds upon itself as the user starts transitions on already |
| // animating values multiple times. This maximum limit is to avoid locking |
| // up users' systems with memory consumption in the event that this occurs. |
| // See crbug.com/739197 for more context. |
| return std::min(kRepeatableListMaxLength, |
| static_cast<wtf_size_t>( |
| lowestCommonMultiple(start_length, end_length))); |
| } |
| DCHECK_EQ(length_matching_strategy, |
| ListInterpolationFunctions::LengthMatchingStrategy::kPadToLargest); |
| return std::max(start_length, end_length); |
| } |
| |
| PairwiseInterpolationValue ListInterpolationFunctions::MaybeMergeSingles( |
| InterpolationValue&& start, |
| InterpolationValue&& end, |
| LengthMatchingStrategy length_matching_strategy, |
| MergeSingleItemConversionsCallback merge_single_item_conversions) { |
| const wtf_size_t start_length = |
| To<InterpolableList>(*start.interpolable_value).length(); |
| const wtf_size_t end_length = |
| To<InterpolableList>(*end.interpolable_value).length(); |
| |
| if (length_matching_strategy == |
| ListInterpolationFunctions::LengthMatchingStrategy::kEqual && |
| (start_length != end_length)) { |
| return nullptr; |
| } |
| |
| if (start_length == 0 && end_length == 0) { |
| return PairwiseInterpolationValue(std::move(start.interpolable_value), |
| std::move(end.interpolable_value), |
| nullptr); |
| } |
| |
| if (start_length == 0) { |
| std::unique_ptr<InterpolableValue> start_interpolable_value = |
| end.interpolable_value->CloneAndZero(); |
| return PairwiseInterpolationValue(std::move(start_interpolable_value), |
| std::move(end.interpolable_value), |
| std::move(end.non_interpolable_value)); |
| } |
| |
| if (end_length == 0) { |
| std::unique_ptr<InterpolableValue> end_interpolable_value = |
| start.interpolable_value->CloneAndZero(); |
| return PairwiseInterpolationValue(std::move(start.interpolable_value), |
| std::move(end_interpolable_value), |
| std::move(start.non_interpolable_value)); |
| } |
| |
| const wtf_size_t final_length = |
| MatchLengths(start_length, end_length, length_matching_strategy); |
| auto result_start_interpolable_list = |
| std::make_unique<InterpolableList>(final_length); |
| auto result_end_interpolable_list = |
| std::make_unique<InterpolableList>(final_length); |
| Vector<scoped_refptr<const NonInterpolableValue>> |
| result_non_interpolable_values(final_length); |
| |
| auto& start_interpolable_list = |
| To<InterpolableList>(*start.interpolable_value); |
| auto& end_interpolable_list = To<InterpolableList>(*end.interpolable_value); |
| const NonInterpolableList& start_non_interpolable_list = |
| ToNonInterpolableList(*start.non_interpolable_value); |
| const NonInterpolableList& end_non_interpolable_list = |
| ToNonInterpolableList(*end.non_interpolable_value); |
| const wtf_size_t start_non_interpolable_length = |
| ToNonInterpolableList(*start.non_interpolable_value).length(); |
| const wtf_size_t end_non_interpolable_length = |
| ToNonInterpolableList(*end.non_interpolable_value).length(); |
| for (wtf_size_t i = 0; i < final_length; i++) { |
| if (length_matching_strategy == |
| LengthMatchingStrategy::kLowestCommonMultiple || |
| (i < start_length && i < end_length)) { |
| InterpolationValue start_merge( |
| start_interpolable_list.Get(i % start_length)->Clone(), |
| start_non_interpolable_list.Get(i % start_non_interpolable_length)); |
| InterpolationValue end_merge( |
| end_interpolable_list.Get(i % end_length)->Clone(), |
| end_non_interpolable_list.Get(i % end_non_interpolable_length)); |
| PairwiseInterpolationValue result = merge_single_item_conversions.Run( |
| std::move(start_merge), std::move(end_merge)); |
| if (!result) |
| return nullptr; |
| result_start_interpolable_list->Set( |
| i, std::move(result.start_interpolable_value)); |
| result_end_interpolable_list->Set( |
| i, std::move(result.end_interpolable_value)); |
| result_non_interpolable_values[i] = |
| std::move(result.non_interpolable_value); |
| } else { |
| DCHECK_EQ(length_matching_strategy, |
| LengthMatchingStrategy::kPadToLargest); |
| if (i < start_length) { |
| result_start_interpolable_list->Set( |
| i, start_interpolable_list.Get(i)->Clone()); |
| result_end_interpolable_list->Set( |
| i, start_interpolable_list.Get(i)->CloneAndZero()); |
| result_non_interpolable_values[i] = |
| (i < start_non_interpolable_length) |
| ? start_non_interpolable_list.Get(i) |
| : nullptr; |
| } else { |
| DCHECK_LT(i, end_length); |
| result_start_interpolable_list->Set( |
| i, end_interpolable_list.Get(i)->CloneAndZero()); |
| result_end_interpolable_list->Set( |
| i, end_interpolable_list.Get(i)->Clone()); |
| result_non_interpolable_values[i] = |
| (i < end_non_interpolable_length) ? end_non_interpolable_list.Get(i) |
| : nullptr; |
| } |
| } |
| } |
| return PairwiseInterpolationValue( |
| std::move(result_start_interpolable_list), |
| std::move(result_end_interpolable_list), |
| NonInterpolableList::Create(std::move(result_non_interpolable_values))); |
| } |
| |
| static void RepeatToLength(InterpolationValue& value, wtf_size_t length) { |
| auto& interpolable_list = To<InterpolableList>(*value.interpolable_value); |
| const NonInterpolableList& non_interpolable_list = |
| ToNonInterpolableList(*value.non_interpolable_value); |
| wtf_size_t current_length = interpolable_list.length(); |
| DCHECK_GT(current_length, 0U); |
| if (current_length == length) |
| return; |
| DCHECK_LT(current_length, length); |
| auto new_interpolable_list = std::make_unique<InterpolableList>(length); |
| Vector<scoped_refptr<const NonInterpolableValue>> new_non_interpolable_values( |
| length); |
| for (wtf_size_t i = length; i-- > 0;) { |
| new_interpolable_list->Set( |
| i, i < current_length |
| ? std::move(interpolable_list.GetMutable(i)) |
| : interpolable_list.Get(i % current_length)->Clone()); |
| new_non_interpolable_values[i] = |
| non_interpolable_list.Get(i % current_length); |
| } |
| value.interpolable_value = std::move(new_interpolable_list); |
| value.non_interpolable_value = |
| NonInterpolableList::Create(std::move(new_non_interpolable_values)); |
| } |
| |
| // This helper function makes value the same length as length_value by |
| // CloneAndZero-ing the additional items from length_value into value. |
| static void PadToSameLength(InterpolationValue& value, |
| const InterpolationValue& length_value) { |
| auto& interpolable_list = To<InterpolableList>(*value.interpolable_value); |
| const NonInterpolableList& non_interpolable_list = |
| ToNonInterpolableList(*value.non_interpolable_value); |
| const wtf_size_t current_length = interpolable_list.length(); |
| auto& target_interpolable_list = |
| To<InterpolableList>(*length_value.interpolable_value); |
| const NonInterpolableList& target_non_interpolable_list = |
| ToNonInterpolableList(*length_value.non_interpolable_value); |
| const wtf_size_t target_length = target_interpolable_list.length(); |
| DCHECK_LT(current_length, target_length); |
| auto new_interpolable_list = |
| std::make_unique<InterpolableList>(target_length); |
| Vector<scoped_refptr<const NonInterpolableValue>> new_non_interpolable_values( |
| target_length); |
| wtf_size_t index = 0; |
| for (; index < current_length; index++) { |
| new_interpolable_list->Set(index, |
| std::move(interpolable_list.GetMutable(index))); |
| new_non_interpolable_values[index] = non_interpolable_list.Get(index); |
| } |
| for (; index < target_length; index++) { |
| new_interpolable_list->Set( |
| index, target_interpolable_list.Get(index)->CloneAndZero()); |
| new_non_interpolable_values[index] = |
| target_non_interpolable_list.Get(index); |
| } |
| value.interpolable_value = std::move(new_interpolable_list); |
| value.non_interpolable_value = |
| NonInterpolableList::Create(std::move(new_non_interpolable_values)); |
| } |
| |
| static bool InterpolableListsAreCompatible( |
| const InterpolableList& a, |
| const InterpolableList& b, |
| wtf_size_t length, |
| ListInterpolationFunctions::LengthMatchingStrategy length_matching_strategy, |
| ListInterpolationFunctions::InterpolableValuesAreCompatibleCallback |
| interpolable_values_are_compatible) { |
| for (wtf_size_t i = 0; i < length; i++) { |
| if (length_matching_strategy == |
| ListInterpolationFunctions::LengthMatchingStrategy:: |
| kLowestCommonMultiple || |
| (i < a.length() && i < b.length())) { |
| if (!interpolable_values_are_compatible.Run(a.Get(i % a.length()), |
| b.Get(i % b.length()))) { |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| static bool NonInterpolableListsAreCompatible( |
| const NonInterpolableList& a, |
| const NonInterpolableList& b, |
| wtf_size_t length, |
| ListInterpolationFunctions::LengthMatchingStrategy length_matching_strategy, |
| ListInterpolationFunctions::NonInterpolableValuesAreCompatibleCallback |
| non_interpolable_values_are_compatible) { |
| for (wtf_size_t i = 0; i < length; i++) { |
| if (length_matching_strategy == |
| ListInterpolationFunctions::LengthMatchingStrategy:: |
| kLowestCommonMultiple || |
| (i < a.length() && i < b.length())) { |
| if (!non_interpolable_values_are_compatible.Run(a.Get(i % a.length()), |
| b.Get(i % b.length()))) { |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| bool ListInterpolationFunctions::VerifyNoNonInterpolableValues( |
| const NonInterpolableValue* a, |
| const NonInterpolableValue* b) { |
| DCHECK(!a && !b); |
| return true; |
| } |
| |
| void ListInterpolationFunctions::Composite( |
| UnderlyingValueOwner& underlying_value_owner, |
| double underlying_fraction, |
| const InterpolationType& type, |
| const InterpolationValue& value, |
| LengthMatchingStrategy length_matching_strategy, |
| InterpolableValuesAreCompatibleCallback interpolable_values_are_compatible, |
| NonInterpolableValuesAreCompatibleCallback |
| non_interpolable_values_are_compatible, |
| CompositeItemCallback composite_item) { |
| const wtf_size_t underlying_length = |
| To<InterpolableList>(*underlying_value_owner.Value().interpolable_value) |
| .length(); |
| |
| const auto& interpolable_list = |
| To<InterpolableList>(*value.interpolable_value); |
| const wtf_size_t value_length = interpolable_list.length(); |
| |
| if (length_matching_strategy == |
| ListInterpolationFunctions::LengthMatchingStrategy::kEqual && |
| (underlying_length != value_length)) { |
| underlying_value_owner.Set(type, value); |
| return; |
| } |
| |
| if (underlying_length == 0) { |
| DCHECK(!underlying_value_owner.Value().non_interpolable_value); |
| underlying_value_owner.Set(type, value); |
| return; |
| } |
| |
| if (value_length == 0) { |
| DCHECK(!value.non_interpolable_value); |
| underlying_value_owner.MutableValue().interpolable_value->Scale( |
| underlying_fraction); |
| return; |
| } |
| |
| const wtf_size_t final_length = |
| MatchLengths(underlying_length, value_length, length_matching_strategy); |
| |
| if (!InterpolableListsAreCompatible( |
| To<InterpolableList>( |
| *underlying_value_owner.Value().interpolable_value), |
| interpolable_list, final_length, length_matching_strategy, |
| interpolable_values_are_compatible)) { |
| underlying_value_owner.Set(type, value); |
| return; |
| } |
| |
| const NonInterpolableList& non_interpolable_list = |
| ToNonInterpolableList(*value.non_interpolable_value); |
| if (!NonInterpolableListsAreCompatible( |
| ToNonInterpolableList( |
| *underlying_value_owner.Value().non_interpolable_value), |
| non_interpolable_list, final_length, length_matching_strategy, |
| non_interpolable_values_are_compatible)) { |
| underlying_value_owner.Set(type, value); |
| return; |
| } |
| |
| InterpolationValue& underlying_value = underlying_value_owner.MutableValue(); |
| if (length_matching_strategy == |
| LengthMatchingStrategy::kLowestCommonMultiple) { |
| if (underlying_length < final_length) { |
| RepeatToLength(underlying_value, final_length); |
| } |
| NonInterpolableList::AutoBuilder builder(underlying_value_owner); |
| |
| for (wtf_size_t i = 0; i < final_length; i++) { |
| UnderlyingItemValue underlying_item(underlying_value_owner, builder, i); |
| composite_item.Run(underlying_item, underlying_fraction, |
| *interpolable_list.Get(i % value_length), |
| non_interpolable_list.Get(i % value_length)); |
| } |
| } else { |
| DCHECK(length_matching_strategy == LengthMatchingStrategy::kPadToLargest || |
| length_matching_strategy == LengthMatchingStrategy::kEqual); |
| if (underlying_length < final_length) { |
| DCHECK_EQ(length_matching_strategy, |
| LengthMatchingStrategy::kPadToLargest); |
| DCHECK_EQ(value_length, final_length); |
| PadToSameLength(underlying_value, value); |
| } |
| auto& underlying_interpolable_list = |
| To<InterpolableList>(*underlying_value.interpolable_value); |
| |
| NonInterpolableList::AutoBuilder builder(underlying_value_owner); |
| |
| for (wtf_size_t i = 0; i < value_length; i++) { |
| UnderlyingItemValue underlying_item(underlying_value_owner, builder, i); |
| composite_item.Run(underlying_item, underlying_fraction, |
| *interpolable_list.Get(i), |
| non_interpolable_list.Get(i)); |
| } |
| for (wtf_size_t i = value_length; i < final_length; i++) { |
| underlying_interpolable_list.GetMutable(i)->Scale(underlying_fraction); |
| } |
| } |
| } |
| |
| NonInterpolableList::AutoBuilder::AutoBuilder(UnderlyingValue& underlying_value) |
| : underlying_value_(underlying_value) { |
| DCHECK(underlying_value.GetNonInterpolableValue()); |
| DCHECK(IsNonInterpolableList(underlying_value_.GetNonInterpolableValue())); |
| } |
| |
| NonInterpolableList::AutoBuilder::~AutoBuilder() { |
| // If no call to Set ever happened, there is no need to modify |
| // underlying_value_. |
| if (!list_.size()) |
| return; |
| const auto& non_interpolable_list = |
| ToNonInterpolableList(*underlying_value_.GetNonInterpolableValue()); |
| DCHECK_EQ(non_interpolable_list.length(), list_.size()); |
| underlying_value_.SetNonInterpolableValue( |
| NonInterpolableList::Create(std::move(list_))); |
| } |
| |
| void NonInterpolableList::AutoBuilder::Set( |
| wtf_size_t index, |
| scoped_refptr<const NonInterpolableValue> non_interpolable_value) { |
| // Copy list on first call to Set. |
| if (!list_.size()) { |
| const auto& non_interpolable_list = |
| ToNonInterpolableList(*underlying_value_.GetNonInterpolableValue()); |
| wtf_size_t underlying_length = non_interpolable_list.length(); |
| for (wtf_size_t i = 0; i < underlying_length; ++i) |
| list_.push_back(non_interpolable_list.Get(i)); |
| } |
| |
| DCHECK_LT(index, list_.size()); |
| list_[index] = non_interpolable_value; |
| } |
| |
| } // namespace blink |
