src/third_party/WebKit/Source/core/animation/KeyframeEffectModel.cpp

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include "config.h"
  32 #include "core/animation/KeyframeEffectModel.h"
  33
  34 #include "core/animation/TimedItem.h"
  35 #include "wtf/text/StringHash.h"
  36
  37 namespace {
  38
  39 using namespace WebCore;
  40
  41 class ReplaceCompositableValue FINAL : public AnimationEffect::CompositableValue {
  42 public:
  43     static PassRefPtr<ReplaceCompositableValue> create(const AnimatableValue* value)
  44     {
  45         return adoptRef(new ReplaceCompositableValue(value));
  46     }
  47     virtual bool dependsOnUnderlyingValue() const OVERRIDE
  48     {
  49         return false;
  50     }
  51     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const OVERRIDE
  52     {
  53         return PassRefPtr<AnimatableValue>(m_value);
  54     }
  55 private:
  56     ReplaceCompositableValue(const AnimatableValue* value)
  57         : m_value(const_cast<AnimatableValue*>(value))
  58     {
  59     }
  60     RefPtr<AnimatableValue> m_value;
  61 };
  62
  63 class AddCompositableValue FINAL : public AnimationEffect::CompositableValue {
  64 public:
  65     static PassRefPtr<AddCompositableValue> create(const AnimatableValue* value)
  66     {
  67         return adoptRef(new AddCompositableValue(value));
  68     }
  69     virtual bool dependsOnUnderlyingValue() const OVERRIDE
  70     {
  71         return true;
  72     }
  73     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const OVERRIDE
  74     {
  75         return AnimatableValue::add(underlyingValue, m_value.get());
  76     }
  77 private:
  78     AddCompositableValue(const AnimatableValue* value)
  79         : m_value(const_cast<AnimatableValue*>(value))
  80     {
  81     }
  82     RefPtr<AnimatableValue> m_value;
  83 };
  84
  85 class BlendedCompositableValue FINAL : public AnimationEffect::CompositableValue {
  86 public:
  87     static PassRefPtr<BlendedCompositableValue> create(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
  88     {
  89         return adoptRef(new BlendedCompositableValue(before, after, fraction));
  90     }
  91     virtual bool dependsOnUnderlyingValue() const OVERRIDE
  92     {
  93         return m_dependsOnUnderlyingValue;
  94     }
  95     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const OVERRIDE
  96     {
  97         return AnimatableValue::interpolate(m_before->compositeOnto(underlyingValue).get(), m_after->compositeOnto(underlyingValue).get(), m_fraction);
  98     }
  99 private:
 100     BlendedCompositableValue(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
 101         : m_before(const_cast<AnimationEffect::CompositableValue*>(before))
 102         , m_after(const_cast<AnimationEffect::CompositableValue*>(after))
 103         , m_fraction(fraction)
 104         , m_dependsOnUnderlyingValue(before->dependsOnUnderlyingValue() || after->dependsOnUnderlyingValue())
 105     { }
 106     RefPtr<AnimationEffect::CompositableValue> m_before;
 107     RefPtr<AnimationEffect::CompositableValue> m_after;
 108     double m_fraction;
 109     bool m_dependsOnUnderlyingValue;
 110 };
 111
 112 } // namespace
 113
 114
 115 namespace WebCore {
 116
 117 Keyframe::Keyframe()
 118     : m_offset(nullValue())
 119     , m_composite(AnimationEffect::CompositeReplace)
 120 { }
 121
 122 Keyframe::Keyframe(const Keyframe& copyFrom)
 123     : m_offset(copyFrom.m_offset)
 124     , m_composite(copyFrom.m_composite)
 125 {
 126     for (PropertyValueMap::const_iterator iter = copyFrom.m_propertyValues.begin(); iter != copyFrom.m_propertyValues.end(); ++iter)
 127         setPropertyValue(iter->key, iter->value.get());
 128 }
 129
 130 void Keyframe::setPropertyValue(CSSPropertyID property, const AnimatableValue* value)
 131 {
 132     m_propertyValues.add(property, const_cast<AnimatableValue*>(value));
 133 }
 134
 135 void Keyframe::clearPropertyValue(CSSPropertyID property)
 136 {
 137     m_propertyValues.remove(property);
 138 }
 139
 140 const AnimatableValue* Keyframe::propertyValue(CSSPropertyID property) const
 141 {
 142     ASSERT(m_propertyValues.contains(property));
 143     return m_propertyValues.get(property);
 144 }
 145
 146 PropertySet Keyframe::properties() const
 147 {
 148     // This is not used in time-critical code, so we probably don't need to
 149     // worry about caching this result.
 150     PropertySet properties;
 151     for (PropertyValueMap::const_iterator iter = m_propertyValues.begin(); iter != m_propertyValues.end(); ++iter)
 152         properties.add(*iter.keys());
 153     return properties;
 154 }
 155
 156 PassRefPtr<Keyframe> Keyframe::cloneWithOffset(double offset) const
 157 {
 158     RefPtr<Keyframe> theClone = clone();
 159     theClone->setOffset(offset);
 160     return theClone.release();
 161 }
 162
 163 KeyframeEffectModel::KeyframeEffectModel(const KeyframeVector& keyframes)
 164     : m_keyframes(keyframes)
 165 {
 166 }
 167
 168 PropertySet KeyframeEffectModel::properties() const
 169 {
 170     PropertySet result;
 171     if (!m_keyframes.size()) {
 172         return result;
 173     }
 174     result = m_keyframes[0]->properties();
 175     for (size_t i = 1; i < m_keyframes.size(); i++) {
 176         PropertySet extras = m_keyframes[i]->properties();
 177         for (PropertySet::const_iterator it = extras.begin(); it != extras.end(); ++it) {
 178             result.add(*it);
 179         }
 180     }
 181     return result;
 182 }
 183
 184 PassOwnPtr<AnimationEffect::CompositableValueList> KeyframeEffectModel::sample(int iteration, double fraction) const
 185 {
 186     ASSERT(iteration >= 0);
 187     ASSERT(!isNull(fraction));
 188     const_cast<KeyframeEffectModel*>(this)->ensureKeyframeGroups();
 189     OwnPtr<CompositableValueList> map = adoptPtr(new CompositableValueList());
 190     for (KeyframeGroupMap::const_iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter)
 191         map->append(std::make_pair(iter->key, iter->value->sample(iteration, fraction)));
 192     return map.release();
 193 }
 194
 195 KeyframeEffectModel::KeyframeVector KeyframeEffectModel::normalizedKeyframes(const KeyframeVector& keyframes)
 196 {
 197     // keyframes [beginIndex, endIndex) will remain after removing all keyframes if they are not
 198     // loosely sorted by offset, and after removing keyframes with positional offset outide [0, 1].
 199     size_t beginIndex = 0;
 200     size_t endIndex = keyframes.size();
 201
 202     // Becomes the most recent keyframe with an explicit offset.
 203     size_t lastIndex = endIndex;
 204     double lastOffset = std::numeric_limits<double>::quiet_NaN();
 205
 206     for (size_t i = 0; i < keyframes.size(); ++i) {
 207         double offset = keyframes[i]->offset();
 208         if (!isNull(offset)) {
 209             if (lastIndex < i && offset < lastOffset) {
 210                 // The keyframes are not loosely sorted by offset. Exclude all.
 211                 endIndex = beginIndex;
 212                 break;
 213             }
 214
 215             if (offset < 0) {
 216                 // Remove all keyframes up to and including this keyframe.
 217                 beginIndex = i + 1;
 218             } else if (offset > 1) {
 219                 // Remove all keyframes from this keyframe onwards. Note we must complete our checking
 220                 // that the keyframes are loosely sorted by offset, so we can't exit the loop early.
 221                 endIndex = std::min(i, endIndex);
 222             }
 223
 224             lastIndex = i;
 225             lastOffset = offset;
 226         }
 227     }
 228
 229     KeyframeVector result;
 230     if (beginIndex != endIndex) {
 231         result.reserveCapacity(endIndex - beginIndex);
 232         for (size_t i = beginIndex; i < endIndex; ++i) {
 233             result.append(keyframes[i]->clone());
 234         }
 235
 236         if (isNull(result[result.size() - 1]->offset()))
 237             result[result.size() - 1]->setOffset(1);
 238
 239         if (result.size() > 1 && isNull(result[0]->offset()))
 240             result[0]->setOffset(0);
 241
 242         lastIndex = 0;
 243         lastOffset = result[0]->offset();
 244         for (size_t i = 1; i < result.size(); ++i) {
 245             double offset = result[i]->offset();
 246             if (!isNull(offset)) {
 247                 if (lastIndex + 1 < i) {
 248                     for (size_t j = 1; j < i - lastIndex; ++j)
 249                         result[lastIndex + j]->setOffset(lastOffset + (offset - lastOffset) * j / (i - lastIndex));
 250                 }
 251                 lastIndex = i;
 252                 lastOffset = offset;
 253             }
 254         }
 255     }
 256     return result;
 257 }
 258
 259 void KeyframeEffectModel::ensureKeyframeGroups() const
 260 {
 261     if (m_keyframeGroups)
 262         return;
 263
 264     m_keyframeGroups = adoptPtr(new KeyframeGroupMap);
 265     const KeyframeVector keyframes = normalizedKeyframes(getFrames());
 266     for (KeyframeVector::const_iterator keyframeIter = keyframes.begin(); keyframeIter != keyframes.end(); ++keyframeIter) {
 267         const Keyframe* keyframe = keyframeIter->get();
 268         PropertySet keyframeProperties = keyframe->properties();
 269         for (PropertySet::const_iterator propertyIter = keyframeProperties.begin(); propertyIter != keyframeProperties.end(); ++propertyIter) {
 270             CSSPropertyID property = *propertyIter;
 271             KeyframeGroupMap::iterator groupIter = m_keyframeGroups->find(property);
 272             if (groupIter == m_keyframeGroups->end()) {
 273                 KeyframeGroupMap::AddResult result = m_keyframeGroups->add(property, adoptPtr(new PropertySpecificKeyframeGroup));
 274                 ASSERT(result.isNewEntry);
 275                 groupIter = result.iterator;
 276             }
 277             groupIter->value->appendKeyframe(adoptPtr(
 278                 new PropertySpecificKeyframe(keyframe->offset(), keyframe->propertyValue(property), keyframe->composite())));
 279         }
 280     }
 281
 282     // Add synthetic keyframes.
 283     for (KeyframeGroupMap::iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter) {
 284         iter->value->addSyntheticKeyframeIfRequired();
 285         iter->value->removeRedundantKeyframes();
 286     }
 287 }
 288
 289
 290 KeyframeEffectModel::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, const AnimatableValue* value, CompositeOperation composite)
 291     : m_offset(offset)
 292     , m_value(composite == AnimationEffect::CompositeReplace ?
 293         static_cast<PassRefPtr<CompositableValue> >(ReplaceCompositableValue::create(value)) :
 294         static_cast<PassRefPtr<CompositableValue> >(AddCompositableValue::create(value)))
 295 {
 296 }
 297
 298 KeyframeEffectModel::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, PassRefPtr<CompositableValue> value)
 299     : m_offset(offset)
 300     , m_value(value)
 301 {
 302     ASSERT(!isNull(m_offset));
 303 }
 304
 305 PassOwnPtr<KeyframeEffectModel::PropertySpecificKeyframe> KeyframeEffectModel::PropertySpecificKeyframe::cloneWithOffset(double offset) const
 306 {
 307     return adoptPtr(new PropertySpecificKeyframe(offset, PassRefPtr<CompositableValue>(m_value)));
 308 }
 309
 310
 311 void KeyframeEffectModel::PropertySpecificKeyframeGroup::appendKeyframe(PassOwnPtr<PropertySpecificKeyframe> keyframe)
 312 {
 313     ASSERT(m_keyframes.isEmpty() || m_keyframes.last()->offset() <= keyframe->offset());
 314     m_keyframes.append(keyframe);
 315 }
 316
 317 void KeyframeEffectModel::PropertySpecificKeyframeGroup::removeRedundantKeyframes()
 318 {
 319     // As an optimization, removes keyframes in the following categories, as
 320     // they will never be used by sample().
 321     // - End keyframes with the same offset as their neighbor
 322     // - Interior keyframes with the same offset as both their neighbors
 323     // Note that synthetic keyframes must be added before this method is
 324     // called.
 325     ASSERT(m_keyframes.size() >= 2);
 326     for (int i = m_keyframes.size() - 1; i >= 0; --i) {
 327         double offset = m_keyframes[i]->offset();
 328         bool hasSameOffsetAsPreviousNeighbor = !i || m_keyframes[i - 1]->offset() == offset;
 329         bool hasSameOffsetAsNextNeighbor = i == static_cast<int>(m_keyframes.size() - 1) || m_keyframes[i + 1]->offset() == offset;
 330         if (hasSameOffsetAsPreviousNeighbor && hasSameOffsetAsNextNeighbor)
 331             m_keyframes.remove(i);
 332     }
 333     ASSERT(m_keyframes.size() >= 2);
 334 }
 335
 336 void KeyframeEffectModel::PropertySpecificKeyframeGroup::addSyntheticKeyframeIfRequired()
 337 {
 338     ASSERT(!m_keyframes.isEmpty());
 339     double offset = m_keyframes.first()->offset();
 340     bool allOffsetsEqual = true;
 341     for (PropertySpecificKeyframeVector::const_iterator iter = m_keyframes.begin() + 1; iter != m_keyframes.end(); ++iter) {
 342         if ((*iter)->offset() != offset) {
 343             allOffsetsEqual = false;
 344             break;
 345         }
 346     }
 347     if (!allOffsetsEqual)
 348         return;
 349
 350     if (!offset)
 351         appendKeyframe(m_keyframes.first()->cloneWithOffset(1.0));
 352     else
 353         m_keyframes.insert(0, adoptPtr(new PropertySpecificKeyframe(0.0, AnimatableValue::neutralValue(), CompositeAdd)));
 354 }
 355
 356 PassRefPtr<AnimationEffect::CompositableValue> KeyframeEffectModel::PropertySpecificKeyframeGroup::sample(int iteration, double offset) const
 357 {
 358     // FIXME: Implement accumulation.
 359     ASSERT_UNUSED(iteration, iteration >= 0);
 360     ASSERT(!isNull(offset));
 361
 362     // Bail if offset is null, as this can lead to buffer overflow below.
 363     if (isNull(offset))
 364         return const_cast<CompositableValue*>(m_keyframes.first()->value());
 365
 366     double minimumOffset = m_keyframes.first()->offset();
 367     double maximumOffset = m_keyframes.last()->offset();
 368     ASSERT(minimumOffset != maximumOffset);
 369
 370     PropertySpecificKeyframeVector::const_iterator before;
 371     PropertySpecificKeyframeVector::const_iterator after;
 372
 373     // Note that this algorithm is simpler than that in the spec because we
 374     // have removed keyframes with equal offsets in
 375     // removeRedundantKeyframes().
 376     if (offset < minimumOffset) {
 377         before = m_keyframes.begin();
 378         after = before + 1;
 379         ASSERT((*before)->offset() > offset);
 380         ASSERT((*after)->offset() > offset);
 381     } else if (offset >= maximumOffset) {
 382         after = m_keyframes.end() - 1;
 383         before = after - 1;
 384         ASSERT((*before)->offset() < offset);
 385         ASSERT((*after)->offset() <= offset);
 386     } else {
 387         // FIXME: This is inefficient for large numbers of keyframes. Consider
 388         // using binary search.
 389         after = m_keyframes.begin();
 390         while ((*after)->offset() <= offset)
 391             ++after;
 392         before = after - 1;
 393         ASSERT((*before)->offset() <= offset);
 394         ASSERT((*after)->offset() > offset);
 395     }
 396
 397     if ((*before)->offset() == offset)
 398         return const_cast<CompositableValue*>((*before)->value());
 399     if ((*after)->offset() == offset)
 400         return const_cast<CompositableValue*>((*after)->value());
 401     return BlendedCompositableValue::create((*before)->value(), (*after)->value(),
 402         (offset - (*before)->offset()) / ((*after)->offset() - (*before)->offset()));
 403 }
 404
 405 } // namespace