web-animation.js

/**
 * Copyright 2012 Google Inc. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

(function () {
  'use strict';

  var ASSERT_ENABLED = false;

  function assert (check, message) {
    console.assert(ASSERT_ENABLED,
      'assert should not be called when ASSERT_ENABLED is false');
    console.assert(check, message);
    // Some implementations of console.assert don't actually throw
    if (!check) { throw message; }
  }

  function detectFeatures () {
    var style = document.createElement('style');
    style.textContent = '' +
      'dummyRuleForTesting {' +
      'width: calc(0px);' +
      'width: -webkit-calc(0px); }';
    document.head.appendChild(style);
    var transformCandidates = [
      'transform',
      'webkitTransform',
      'msTransform'
    ];
    var transformProperty = transformCandidates.filter(function (property) {
      return property in style.sheet.cssRules[0].style;
    })[0];
    var calcFunction = style.sheet.cssRules[0].style.width.split('(')[0];
    document.head.removeChild(style);
    return {
      transformProperty: transformProperty,
      calcFunction: calcFunction
    };
  }

  var features = detectFeatures();
  var constructorToken = {};

  var createObject = function (proto, obj) {
    var newObject = Object.create(proto);
    Object.getOwnPropertyNames(obj).forEach(function (name) {
      Object.defineProperty(
        newObject, name, Object.getOwnPropertyDescriptor(obj, name));
    });
    return newObject;
  };

  var abstractMethod = function () {
    throw 'Abstract method not implemented.';
  };

  var IndexSizeError = function (message) {
    Error.call(this);
    this.name = 'IndexSizeError';
    this.message = message;
  };

  IndexSizeError.prototype = Object.create(Error.prototype);



  /** @constructor */
  var TimingDict = function (timingInput) {
    if (typeof timingInput === 'object') {
      for (var k in timingInput) {
        if (k in TimingDict.prototype) {
          this[k] = timingInput[k];
        }
      }
    } else if (isDefinedAndNotNull(timingInput)) {
      this.duration = Number(timingInput);
    }
  };

  TimingDict.prototype = {
    delay: 0,
    fill: 'forwards',
    iterationStart: 0,
    iterations: 1,
    duration: 'auto',
    activeDuration: 'auto',
    playbackRate: 1,
    direction: 'normal',
    easing: 'linear',
    _easingTimes: 'distribute'
  };



  /** @constructor */
  var Timing = function (token, timingInput, changeHandler) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    this._dict = new TimingDict(timingInput);
    this._changeHandler = changeHandler;
  };

  Timing.prototype = {
    _timingFunction: function (timedItem) {
      var timingFunction = TimingFunction.createFromString(
        this.easing, this._easingTimes, timedItem);
      this._timingFunction = function () {
        return timingFunction;
      };
      return timingFunction;
    },
    _invalidateTimingFunction: function () {
      delete this._timingFunction;
    },
    _iterations: function () {
      var value = this._dict.iterations;
      return value < 0 ? 1 : value;
    },
    _duration: function () {
      var value = this._dict.duration;
      return typeof value === 'number' ? value : 'auto';
    },
    _activeDuration: function () {
      var value = this._dict.activeDuration;
      return typeof value === 'number' ? value : 'auto';
    },
    getEasingTimes: function () {
      return this._easingTimes;
    },
    setEasingTimes: function (times) {
      this._easingTimes = times;
      this._invalidateTimingFunction();
    },
    _clone: function () {
      return new Timing(
        constructorToken, this._dict, this._updateInternalState.bind(this));
    }
  };

  // Configures an accessor descriptor for use with Object.defineProperty() to
  // allow the property to be changed and enumerated, to match __defineGetter__()
  // and __defineSetter__().
  var configureDescriptor = function (descriptor) {
    descriptor.configurable = true;
    descriptor.enumerable = true;
    return descriptor;
  };

  Timing._defineProperty = function (prop) {
    Object.defineProperty(Timing.prototype, prop, configureDescriptor({
      get: function () {
        return this._dict[prop];
      },
      set: function (value) {
        if (isDefinedAndNotNull(value)) {
          this._dict[prop] = value;
        } else {
          delete this._dict[prop];
        }
        // FIXME: probably need to implement specialized handling parsing
        // for each property
        if (prop === 'easing') {
          // Cached timing function may be invalid now.
          this._invalidateTimingFunction();
        }
        this._changeHandler();
      }
    }));
  };

  for (var prop in TimingDict.prototype) {
    Timing._defineProperty(prop);
  }

  var isDefined = function (val) {
    return typeof val !== 'undefined';
  };

  var isDefinedAndNotNull = function (val) {
    return isDefined(val) && (val !== null);
  };



  /** @constructor */
  var Timeline = function (token) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    // TODO: This will probably need to change.
    this._startTime = documentTimeZeroAsClockTime;
    if (this._startTime !== undefined) {
      this._startTime /= 1000;
    }
  };

  Timeline.prototype = {
    get currentTime () {
      if (this._startTime === undefined) {
        this._startTime = documentTimeZeroAsClockTime;
        if (this._startTime === undefined) {
          return null;
        } else {
          this._startTime /= 1000;
        }
      }
      return relativeTime(cachedClockTime(), this._startTime);
    },
    play: function (source) {
      return new Player(constructorToken, source, this);
    },
    getCurrentPlayers: function () {
      return PLAYERS.filter(function (player) {
        return !player._isPastEndOfActiveInterval();
      });
    },
    toTimelineTime: function (otherTime, other) {
      if ((this.currentTime === null) || (other.currentTime === null)) {
        return null;
      } else {
        return otherTime + other._startTime - this._startTime;
      }
    },
    _pauseAnimationsForTesting: function (pauseAt) {
      PLAYERS.forEach(function (player) {
        player.paused = true;
        player.currentTime = pauseAt;
      });
    }
  };

  // TODO: Remove dead Players from here?
  var PLAYERS = [];
  var playersAreSorted = false;
  var playerSequenceNumber = 0;



  /** @constructor */
  var Player = function (token, source, timeline) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    this._registeredOnTimeline = false;
    this._sequenceNumber = playerSequenceNumber++;
    this._timeline = timeline;
    this._startTime =
      this.timeline.currentTime === null ? 0 : this.timeline.currentTime;
    this._timeDrift = 0.0;
    this._pauseTime = undefined;
    this._playbackRate = 1.0;
    this._hasTicked = false;

    this.source = source;
    this._checkForHandlers();
    this._lastCurrentTime = undefined;

    playersAreSorted = false;
    maybeRestartAnimation();
  };

  Player.prototype = {
    set source (source) {
      enterModifyCurrentAnimationState();
      try {
        if (isDefinedAndNotNull(this.source)) {
          // To prevent infinite recursion.
          var oldTimedItem = this.source;
          this._source = null;
          oldTimedItem._attach(null);
        }
        this._source = source;
        if (isDefinedAndNotNull(this.source)) {
          this.source._attach(this);
          this._update();
          maybeRestartAnimation();
        }
        this._checkForHandlers();
      } finally {
        exitModifyCurrentAnimationState(this._hasTicked);
      }
    },
    get source () {
      return this._source;
    },
    // This is the effective current time.
    set currentTime (currentTime) {
      enterModifyCurrentAnimationState();
      try {
        this._currentTime = currentTime;
      } finally {
        exitModifyCurrentAnimationState(
          this._hasTicked || this.startTime + this._timeDrift <= lastTickTime);
      }
    },
    get currentTime () {
      return this._currentTime === null ? 0 : this._currentTime;
    },
    // This is the current time.
    set _currentTime (currentTime) {
      // This seeks by updating _drift. It does not affect the startTime.
      if (isDefined(this._pauseTime)) {
        this._pauseTime = currentTime;
      } else {
        this._timeDrift = (this.timeline.currentTime - this.startTime) *
          this.playbackRate - currentTime;
      }
      this._update();
      maybeRestartAnimation();
    },
    get _currentTime () {
      if (this.timeline.currentTime === null) {
        return null;
      }
      return isDefined(this._pauseTime) ? this._pauseTime :
        (this.timeline.currentTime - this.startTime) * this.playbackRate -
        this._timeDrift;
    },
    set startTime (startTime) {
      enterModifyCurrentAnimationState();
      try {
        // This seeks by updating _startTime and hence the currentTime. It does
        // not affect _drift.
        this._startTime = startTime;
        playersAreSorted = false;
        this._update();
        maybeRestartAnimation();
      } finally {
        exitModifyCurrentAnimationState(
          this._hasTicked || this.startTime + this._timeDrift <= lastTickTime);
      }
    },
    get startTime () {
      return this._startTime;
    },
    set paused (isPaused) {
      if (isPaused) {
        this._pauseTime = this.currentTime;
      } else if (isDefined(this._pauseTime)) {
        this._timeDrift = (this.timeline.currentTime - this.startTime) *
          this.playbackRate - this._pauseTime;
        this._pauseTime = undefined;
        maybeRestartAnimation();
      }
    },
    get paused () {
      return isDefined(this._pauseTime);
    },
    get timeline () {
      return this._timeline;
    },
    set playbackRate (playbackRate) {
      enterModifyCurrentAnimationState();
      try {
        var cachedCurrentTime = this.currentTime;
        // This will impact currentTime, so perform a compensatory seek.
        this._playbackRate = playbackRate;
        this.currentTime = cachedCurrentTime;
      } finally {
        exitModifyCurrentAnimationState(this._hasTicked);
      }
    },
    get playbackRate () {
      return this._playbackRate;
    },
    _update: function () {
      if (this.source !== null) {
        this.source._updateInheritedTime(this._currentTime);
        this._registerOnTimeline();
      }
    },
    _isPastEndOfActiveInterval: function () {
      return this.source === null ||
        this.source._isPastEndOfActiveInterval();
    },
    _isCurrent: function () {
      return this.source && this.source._isCurrent();
    },
    _hasFutureEffect: function () {
      return this.source && this.source._hasFutureEffect();
    },
    _getLeafItemsInEffect: function (items) {
      if (this.source) {
        this.source._getLeafItemsInEffect(items);
      }
    },
    _isTargetingElement: function (element) {
      return this.source && this.source._isTargetingElement(element);
    },
    _getAnimationsTargetingElement: function (element, animations) {
      if (this.source) {
        this.source._getAnimationsTargetingElement(element, animations);
      }
    },
    _handlerAdded: function () {
      this._needsHandlerPass = true;
    },
    _checkForHandlers: function () {
      this._needsHandlerPass = this.source !== null && this.source._hasHandlers();
    },
    _generateEvents: function () {
      if (!isDefinedAndNotNull(this._lastCurrentTime)) {
        this._lastCurrentTime = this._startTime;
      }

      if (this._needsHandlerPass) {
        var timeDelta = this._currentTime - this._lastCurrentTime;
        if (timeDelta > 0) {
          this.source._generateEvents(
            this._lastCurrentTime, this._currentTime,
            this.timeline.currentTime, 1);
        }
      }

      this._lastCurrentTime = this._currentTime;
    },
    _registerOnTimeline: function () {
      if (!this._registeredOnTimeline) {
        PLAYERS.push(this);
        this._registeredOnTimeline = true;
      }
    },
    _deregisterFromTimeline: function () {
      PLAYERS.splice(PLAYERS.indexOf(this), 1);
      this._registeredOnTimeline = false;
    }
  };



  /** @constructor */
  var TimedItem = function (token, timingInput) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    this.specified = new Timing(
      constructorToken, timingInput,
      this._specifiedTimingModified.bind(this));
    this._inheritedTime = null;
    this.currentIteration = null;
    this._iterationTime = null;
    this._animationTime = null;
    this._startTime = 0.0;
    this._player = null;
    this._parent = null;
    this._updateInternalState();
    this._handlers = {};
    this._onHandlers = {};
  };

  TimedItem.prototype = {
    // TODO: It would be good to avoid the need for this. We would need to modify
    // call sites to instead rely on a call from the parent.
    get _effectiveParentTime () {
      return this.parent !== null && this.parent._iterationTime !== null ?
        this.parent._iterationTime : 0;
    },
    get localTime () {
      return this._inheritedTime === null ?
        null : this._inheritedTime - this._startTime;
    },
    get startTime () {
      return this._startTime;
    },
    get duration () {
      var result = this.specified._duration();
      if (result === 'auto') {
        result = this._intrinsicDuration();
      }
      return result;
    },
    get activeDuration () {
      var result = this.specified._activeDuration();
      if (result === 'auto') {
        var repeatedDuration = this.duration * this.specified._iterations();
        result = repeatedDuration / Math.abs(this.specified.playbackRate);
      }
      return result;
    },
    get endTime () {
      return this._startTime + this.activeDuration + this.specified.delay;
    },
    get parent () {
      return this._parent;
    },
    _attach: function (player) {
      // Remove ourselves from our parent, if we have one. This also removes any
      // exsisting player.
      this._reparent(null);
      this._player = player;
    },
    // Takes care of updating the outgoing parent. This is called with a non-null
    // parent only from TimingGroup.splice(), which takes care of calling
    // TimingGroup._childrenStateModified() for the new parent.
    _reparent: function (parent) {
      if (parent === this) {
        throw new Error('parent can not be set to self!');
      }
      enterModifyCurrentAnimationState();
      try {
        if (this._player !== null) {
          this._player.source = null;
          this._player = null;
        }
        if (this.parent !== null) {
          this.remove();
        }
        this._parent = parent;
        // In the case of a SeqGroup parent, _startTime will be updated by
        // TimingGroup.splice().
        if (this.parent === null || this.parent.type !== 'seq') {
          this._startTime =
            this._stashedStartTime === undefined ? 0.0 : this._stashedStartTime;
          this._stashedStartTime = undefined;
        }
        // In the case of the parent being non-null, _childrenStateModified() will
        // call this via _updateChildInheritedTimes().
        // TODO: Consider optimising this case by skipping this call.
        this._updateTimeMarkers();
      } finally {
        exitModifyCurrentAnimationState(
          Boolean(this.player) && this.player._hasTicked);
      }
    },
    _intrinsicDuration: function () {
      return 0.0;
    },
    _updateInternalState: function () {
      if (this.parent) {
        this.parent._childrenStateModified();
      } else if (this._player) {
        this._player._registerOnTimeline();
      }
      this._updateTimeMarkers();
    },
    _specifiedTimingModified: function () {
      enterModifyCurrentAnimationState();
      try {
        this._updateInternalState();
      } finally {
        exitModifyCurrentAnimationState(
          Boolean(this.player) && this.player._hasTicked);
      }
    },
    // We push time down to children. We could instead have children pull from
    // above, but this is tricky because a TimedItem may use either a parent
    // TimedItem or an Player. This requires either logic in
    // TimedItem, or for TimedItem and Player to implement Timeline
    // (or an equivalent), both of which are ugly.
    _updateInheritedTime: function (inheritedTime) {
      this._inheritedTime = inheritedTime;
      this._updateTimeMarkers();
    },
    _updateAnimationTime: function () {
      if (this.localTime < this.specified.delay) {
        if (this.specified.fill === 'backwards' ||
          this.specified.fill === 'both') {
          this._animationTime = 0;
        } else {
          this._animationTime = null;
        }
      } else if (this.localTime <
        this.specified.delay + this.activeDuration) {
        this._animationTime = this.localTime - this.specified.delay;
      } else {
        if (this.specified.fill === 'forwards' ||
          this.specified.fill === 'both') {
          this._animationTime = this.activeDuration;
        } else {
          this._animationTime = null;
        }
      }
    },
    _updateIterationParamsZeroDuration: function () {
      this._iterationTime = 0;
      var isAtEndOfIterations = this.specified._iterations() !== 0 &&
        this.localTime >= this.specified.delay;
      this.currentIteration = (
        isAtEndOfIterations ?
          this._floorWithOpenClosedRange(
            this.specified.iterationStart + this.specified._iterations(),
            1.0) :
          this._floorWithClosedOpenRange(this.specified.iterationStart, 1.0));
      // Equivalent to unscaledIterationTime below.
      var unscaledFraction = (
        isAtEndOfIterations ?
          this._modulusWithOpenClosedRange(
            this.specified.iterationStart + this.specified._iterations(),
            1.0) :
          this._modulusWithClosedOpenRange(this.specified.iterationStart, 1.0));
      this._timeFraction = (
        this._isCurrentDirectionForwards() ?
          unscaledFraction :
          1.0 - unscaledFraction);
      ASSERT_ENABLED && assert(
        this._timeFraction >= 0.0 && this._timeFraction <= 1.0,
        'Time fraction should be in the range [0, 1]');
      this._timeFraction =
        this.specified._timingFunction(this).scaleTime(this._timeFraction);
    },
    _getAdjustedAnimationTime: function (animationTime) {
      var startOffset =
        multiplyZeroGivesZero(this.specified.iterationStart, this.duration);
      return (this.specified.playbackRate < 0 ?
        (animationTime - this.activeDuration) : animationTime) *
        this.specified.playbackRate + startOffset;
    },
    _scaleIterationTime: function (unscaledIterationTime) {
      return this._isCurrentDirectionForwards() ?
        unscaledIterationTime :
        this.duration - unscaledIterationTime;
    },
    _updateIterationParams: function () {
      var adjustedAnimationTime =
        this._getAdjustedAnimationTime(this._animationTime);
      var repeatedDuration = this.duration * this.specified._iterations();
      var startOffset = this.specified.iterationStart * this.duration;
      var isAtEndOfIterations = (this.specified._iterations() !== 0) &&
        (adjustedAnimationTime - startOffset === repeatedDuration);
      this.currentIteration = isAtEndOfIterations ?
        this._floorWithOpenClosedRange(
          adjustedAnimationTime, this.duration) :
        this._floorWithClosedOpenRange(
          adjustedAnimationTime, this.duration);
      var unscaledIterationTime = isAtEndOfIterations ?
        this._modulusWithOpenClosedRange(
          adjustedAnimationTime, this.duration) :
        this._modulusWithClosedOpenRange(
          adjustedAnimationTime, this.duration);
      this._iterationTime = this._scaleIterationTime(unscaledIterationTime);
      this._timeFraction = this._iterationTime / this.duration;
      ASSERT_ENABLED && assert(
        this._timeFraction >= 0.0 && this._timeFraction <= 1.0,
        'Time fraction should be in the range [0, 1], got ' +
        this._timeFraction + ' ' + this._iterationTime + ' ' +
        this.duration + ' ' + isAtEndOfIterations + ' ' +
        unscaledIterationTime);
      this._timeFraction =
        this.specified._timingFunction(this).scaleTime(this._timeFraction);
      this._iterationTime = this._timeFraction * this.duration;
    },
    _updateTimeMarkers: function () {
      if (this.localTime === null) {
        this._animationTime = null;
        this._iterationTime = null;
        this.currentIteration = null;
        this._timeFraction = null;
        return false;
      }
      this._updateAnimationTime();
      if (this._animationTime === null) {
        this._iterationTime = null;
        this.currentIteration = null;
        this._timeFraction = null;
      } else if (this.duration === 0) {
        this._updateIterationParamsZeroDuration();
      } else {
        this._updateIterationParams();
      }
      maybeRestartAnimation();
    },
    _floorWithClosedOpenRange: function (x, range) {
      return Math.floor(x / range);
    },
    _floorWithOpenClosedRange: function (x, range) {
      return Math.ceil(x / range) - 1;
    },
    _modulusWithClosedOpenRange: function (x, range) {
      ASSERT_ENABLED && assert(
        range > 0, 'Range must be strictly positive');
      var modulus = x % range;
      var result = modulus < 0 ? modulus + range : modulus;
      ASSERT_ENABLED && assert(
        result >= 0.0 && result < range,
        'Result should be in the range [0, range)');
      return result;
    },
    _modulusWithOpenClosedRange: function (x, range) {
      var modulus = this._modulusWithClosedOpenRange(x, range);
      var result = modulus === 0 ? range : modulus;
      ASSERT_ENABLED && assert(
        result > 0.0 && result <= range,
        'Result should be in the range (0, range]');
      return result;
    },
    _isCurrentDirectionForwards: function () {
      if (this.specified.direction === 'normal') {
        return true;
      }
      if (this.specified.direction === 'reverse') {
        return false;
      }
      var d = this.currentIteration;
      if (this.specified.direction === 'alternate-reverse') {
        d += 1;
      }
      // TODO: 6.13.3 step 3. wtf?
      return d % 2 === 0;
    },
    clone: abstractMethod,
    before: function () {
      var newItems = [];
      for (var i = 0; i < arguments.length; i++) {
        newItems.push(arguments[i]);
      }
      this.parent._splice(this.parent.indexOf(this), 0, newItems);
    },
    after: function () {
      var newItems = [];
      for (var i = 0; i < arguments.length; i++) {
        newItems.push(arguments[i]);
      }
      this.parent._splice(this.parent.indexOf(this) + 1, 0, newItems);
    },
    replace: function () {
      var newItems = [];
      for (var i = 0; i < arguments.length; i++) {
        newItems.push(arguments[i]);
      }
      this.parent._splice(this.parent.indexOf(this), 1, newItems);
    },
    remove: function () {
      this.parent._splice(this.parent.indexOf(this), 1);
    },
    // Gets the leaf TimedItems currently in effect. Note that this is a superset
    // of the leaf TimedItems in their active interval, as a TimedItem can have an
    // effect outside its active interval due to fill.
    _getLeafItemsInEffect: function (items) {
      if (this._timeFraction !== null) {
        this._getLeafItemsInEffectImpl(items);
      }
    },
    _getLeafItemsInEffectImpl: abstractMethod,
    _isPastEndOfActiveInterval: function () {
      return this._inheritedTime > this.endTime;
    },
    get player () {
      return this.parent === null ?
        this._player : this.parent.player;
    },
    _isCurrent: function () {
      return !this._isPastEndOfActiveInterval() ||
        (this.parent !== null && this.parent._isCurrent());
    },
    _isTargetingElement: abstractMethod,
    _getAnimationsTargetingElement: abstractMethod,
    _netEffectivePlaybackRate: function () {
      var effectivePlaybackRate = this._isCurrentDirectionForwards() ?
        this.specified.playbackRate : -this.specified.playbackRate;
      return this.parent === null ? effectivePlaybackRate :
        effectivePlaybackRate * this.parent._netEffectivePlaybackRate();
    },
    // Note that this restriction is currently incomplete - for example,
    // Animations which are playing forwards and have a fill of backwards
    // are not in effect unless current.
    // TODO: Complete this restriction.
    _hasFutureEffect: function () {
      return this._isCurrent() || this.specified.fill !== 'none';
    },
    set onstart (func) {
      this._setOnHandler('start', func);
    },
    get onstart () {
      return this._getOnHandler('start');
    },
    set oniteration (func) {
      this._setOnHandler('iteration', func);
    },
    get oniteration () {
      return this._getOnHandler('iteration');
    },
    set onend (func) {
      this._setOnHandler('end', func);
    },
    get onend () {
      return this._getOnHandler('end');
    },
    set oncancel (func) {
      this._setOnHandler('cancel', func);
    },
    get oncancel () {
      return this._getOnHandler('cancel');
    },
    _setOnHandler: function (type, func) {
      if (typeof func === 'function') {
        this._onHandlers[type] = {
          callback: func,
          index: (this._handlers[type] || []).length
        };
        if (this.player) {
          this.player._handlerAdded();
        }
      } else {
        this._onHandlers[type] = null;
        if (this.player) {
          this.player._checkForHandlers();
        }
      }
    },
    _getOnHandler: function (type) {
      if (isDefinedAndNotNull(this._onHandlers[type])) {
        return this._onHandlers[type].func;
      }
      return null;
    },
    addEventListener: function (type, func) {
      if (typeof func !== 'function' || !(type === 'start' ||
        type === 'iteration' || type === 'end' || type === 'cancel')) {
        return;
      }
      if (!isDefinedAndNotNull(this._handlers[type])) {
        this._handlers[type] = [];
      } else if (this._handlers[type].indexOf(func) !== -1) {
        return;
      }
      this._handlers[type].push(func);
      if (this.player) {
        this.player._handlerAdded();
      }
    },
    removeEventListener: function (type, func) {
      if (!this._handlers[type]) {
        return;
      }
      var index = this._handlers[type].indexOf(func);
      if (index === -1) {
        return;
      }
      this._handlers[type].splice(index, 1);
      if (isDefinedAndNotNull(this._onHandlers[type]) &&
        (index < this._onHandlers[type].index)) {
        this._onHandlers[type].index -= 1;
      }
      if (this.player) {
        this.player._checkForHandlers();
      }
    },
    _hasHandlers: function () {
      return this._hasHandlersForEvent('start') ||
        this._hasHandlersForEvent('iteration') ||
        this._hasHandlersForEvent('end') || this._hasHandlersForEvent('cancel');
    },
    _hasHandlersForEvent: function (type) {
      return (isDefinedAndNotNull(this._handlers[type]) &&
        this._handlers[type].length > 0) ||
        isDefinedAndNotNull(this._onHandlers[type]);
    },
    _callHandlers: function (type, event) {
      var callbackList;
      if (isDefinedAndNotNull(this._handlers[type])) {
        callbackList = this._handlers[type].slice();
      } else {
        callbackList = [];
      }
      if (isDefinedAndNotNull(this._onHandlers[type])) {
        callbackList.splice(this._onHandlers[type].index, 0,
          this._onHandlers[type].callback);
      }
      setTimeout(function () {
        for (var i = 0; i < callbackList.length; i++) {
          callbackList[i].call(this, event);
        }
      }, 0);
    },
    _generateChildEventsForRange: function () { },
    _toSubRanges: function (fromTime, toTime, iterationTimes) {
      if (fromTime > toTime) {
        var revRanges = this._toSubRanges(toTime, fromTime, iterationTimes);
        revRanges.ranges.forEach(function (a) { a.reverse(); });
        revRanges.ranges.reverse();
        revRanges.start = iterationTimes.length - revRanges.start - 1;
        revRanges.delta = -1;
        return revRanges;
      }
      var skipped = 0;
      // TODO: this should be calculatable. This would be more efficient
      // than searching through the list.
      while (iterationTimes[skipped] < fromTime) {
        skipped++;
      }
      var currentStart = fromTime;
      var ranges = [];
      for (var i = skipped; i < iterationTimes.length; i++) {
        if (iterationTimes[i] < toTime) {
          ranges.push([currentStart, iterationTimes[i]]);
          currentStart = iterationTimes[i];
        } else {
          ranges.push([currentStart, toTime]);
          return { start: skipped, delta: 1, ranges: ranges };
        }
      }
      ranges.push([currentStart, toTime]);
      return { start: skipped, delta: 1, ranges: ranges };
    },
    _generateEvents: function (fromTime, toTime, globalTime, deltaScale) {
      function toGlobal (time) {
        return (globalTime - (toTime - (time / deltaScale)));
      }
      var firstIteration = Math.floor(this.specified.iterationStart);
      var lastIteration = Math.floor(this.specified.iterationStart +
        this.specified.iterations);
      if (lastIteration === this.specified.iterationStart +
        this.specified.iterations) {
        lastIteration -= 1;
      }
      var startTime = this.startTime + this.specified.delay;

      if (this._hasHandlersForEvent('start')) {
        // Did we pass the start of this animation in the forward direction?
        if (fromTime <= startTime && toTime > startTime) {
          this._callHandlers('start', new TimingEvent(constructorToken, this,
            'start', this.specified.delay, toGlobal(startTime),
            firstIteration));
          // Did we pass the end of this animation in the reverse direction?
        } else if (fromTime > this.endTime && toTime <= this.endTime) {
          this._callHandlers(
            'start',
            new TimingEvent(
              constructorToken, this, 'start', this.endTime - this.startTime,
              toGlobal(this.endTime), lastIteration));
        }
      }

      // Calculate a list of uneased iteration times.
      var iterationTimes = [];
      for (var i = firstIteration + 1; i <= lastIteration; i++) {
        iterationTimes.push(i - this.specified.iterationStart);
      }
      iterationTimes = iterationTimes.map(function (i) {
        return i * this.duration / this.specified.playbackRate + startTime;
      }.bind(this));

      // Determine the impacted subranges.
      var clippedFromTime;
      var clippedToTime;
      if (fromTime < toTime) {
        clippedFromTime = Math.max(fromTime, startTime);
        clippedToTime = Math.min(toTime, this.endTime);
      } else {
        clippedFromTime = Math.min(fromTime, this.endTime);
        clippedToTime = Math.max(toTime, startTime);
      }
      var subranges = this._toSubRanges(
        clippedFromTime, clippedToTime, iterationTimes);

      for (var i = 0; i < subranges.ranges.length; i++) {
        var currentIter = subranges.start + i * subranges.delta;
        if (i > 0 && this._hasHandlersForEvent('iteration')) {
          var iterTime = subranges.ranges[i][0];
          this._callHandlers(
            'iteration',
            new TimingEvent(
              constructorToken, this, 'iteration', iterTime - this.startTime,
              toGlobal(iterTime), currentIter));
        }

        var iterFraction;
        if (subranges.delta > 0) {
          iterFraction = this.specified.iterationStart % 1;
        } else {
          iterFraction = 1 -
            (this.specified.iterationStart + this.specified.iterations) % 1;
        }
        this._generateChildEventsForRange(
          subranges.ranges[i][0], subranges.ranges[i][1],
          fromTime, toTime, currentIter - iterFraction,
          globalTime, deltaScale * this.specified.playbackRate);
      }

      if (this._hasHandlersForEvent('end')) {
        // Did we pass the end of this animation in the forward direction?
        if (fromTime < this.endTime && toTime >= this.endTime) {
          this._callHandlers(
            'end',
            new TimingEvent(
              constructorToken, this, 'end', this.endTime - this.startTime,
              toGlobal(this.endTime), lastIteration));
          // Did we pass the start of this animation in the reverse direction?
        } else if (fromTime >= startTime && toTime < startTime) {
          this._callHandlers(
            'end',
            new TimingEvent(
              constructorToken, this, 'end', this.specified.delay,
              toGlobal(startTime), firstIteration));
        }
      }
    }
  };

  var TimingEvent = function (
    token, target, type, localTime, timelineTime, iterationIndex, seeked) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    this._target = target;
    this._type = type;
    this.localTime = localTime;
    this.timelineTime = timelineTime;
    this.iterationIndex = iterationIndex;
    this.seeked = seeked ? true : false;
  };

  TimingEvent.prototype = Object.create(window.Event.prototype, {
    target: {
      get: function () {
        return this._target;
      }
    },
    cancelable: {
      get: function () {
        return false;
      }
    },
    cancelBubble: {
      get: function () {
        return false;
      }
    },
    defaultPrevented: {
      get: function () {
        return false;
      }
    },
    eventPhase: {
      get: function () {
        return 0;
      }
    },
    type: {
      get: function () {
        return this._type;
      }
    }
  });

  var isCustomAnimationEffect = function (animationEffect) {
    // TODO: How does WebIDL actually differentiate different callback interfaces?
    return isDefinedAndNotNull(animationEffect) &&
      typeof animationEffect === 'object' &&
      typeof animationEffect.sample === 'function';
  };

  var interpretAnimationEffect = function (animationEffect) {
    if (animationEffect instanceof AnimationEffect ||
      isCustomAnimationEffect(animationEffect)) {
      return animationEffect;
    } else if (isDefinedAndNotNull(animationEffect) &&
      typeof animationEffect === 'object') {
      // The spec requires animationEffect to be an instance of
      // OneOrMoreKeyframes, but this type is just a dictionary or a list of
      // dictionaries, so the best we can do is test for an object.
      return new KeyframeAnimationEffect(animationEffect);
    }
    return null;
  };

  var cloneAnimationEffect = function (animationEffect) {
    if (animationEffect instanceof AnimationEffect) {
      return animationEffect.clone();
    } else if (isCustomAnimationEffect(animationEffect)) {
      if (typeof animationEffect.clone === 'function') {
        return animationEffect.clone();
      } else {
        return animationEffect;
      }
    } else {
      return null;
    }
  };



  /** @constructor */
  var Animation = function (target, animationEffect, timingInput) {
    enterModifyCurrentAnimationState();
    try {
      TimedItem.call(this, constructorToken, timingInput);
      this.effect = interpretAnimationEffect(animationEffect);
      this._target = target;
    } finally {
      exitModifyCurrentAnimationState(false);
    }
  };

  Animation.prototype = createObject(TimedItem.prototype, {
    _sample: function () {
      if (isDefinedAndNotNull(this.effect) &&
        !(this.target instanceof PseudoElementReference)) {
        var sampleMethod = isCustomAnimationEffect(this.effect) ?
          this.effect.sample : this.effect._sample;
        sampleMethod.apply(
          this.effect, [
          this._timeFraction,
          this.currentIteration,
          this.target,
          this.underlyingValue
        ]
        );
      }
    },
    _getLeafItemsInEffectImpl: function (items) {
      items.push(this);
    },
    _isTargetingElement: function (element) {
      return element === this.target;
    },
    _getAnimationsTargetingElement: function (element, animations) {
      if (this._isTargetingElement(element)) {
        animations.push(this);
      }
    },
    get target () {
      return this._target;
    },
    set effect (effect) {
      enterModifyCurrentAnimationState();
      try {
        this._effect = effect;
        this.specified._invalidateTimingFunction();
      } finally {
        exitModifyCurrentAnimationState(
          Boolean(this.player) && this.player._hasTicked);
      }
    },
    get effect () {
      return this._effect;
    },
    clone: function () {
      return new Animation(this.target,
        cloneAnimationEffect(this.effect), this.specified._dict);
    },
    toString: function () {
      var effectString = '<none>';
      if (this.effect instanceof AnimationEffect) {
        effectString = this.effect.toString();
      } else if (isCustomAnimationEffect(this.effect)) {
        effectString = 'Custom effect';
      }
      return 'Animation ' + this.startTime + '-' + this.endTime + ' (' +
        this.localTime + ') ' + effectString;
    }
  });

  function throwNewHierarchyRequestError () {
    var element = document.createElement('span');
    element.appendChild(element);
  }



  /** @constructor */
  var TimedItemList = function (token, children) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    this._children = children;
    this._getters = 0;
    this._ensureGetters();
  };

  TimedItemList.prototype = {
    get length () {
      return this._children.length;
    },
    _ensureGetters: function () {
      while (this._getters < this._children.length) {
        this._ensureGetter(this._getters++);
      }
    },
    _ensureGetter: function (i) {
      Object.defineProperty(this, i, {
        get: function () {
          return this._children[i];
        }
      });
    }
  };



  /** @constructor */
  var TimingGroup = function (token, type, children, timing) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    // Take a copy of the children array, as it could be modified as a side-effect
    // of creating this object. See
    // https://github.com/web-animations/web-animations-js/issues/65 for details.
    var childrenCopy = (children && Array.isArray(children)) ?
      children.slice() : [];
    // used by TimedItem via _intrinsicDuration(), so needs to be set before
    // initializing super.
    this.type = type || 'par';
    this._children = [];
    this._cachedTimedItemList = null;
    this._cachedIntrinsicDuration = null;
    TimedItem.call(this, constructorToken, timing);
    // We add children after setting the parent. This means that if an ancestor
    // (including the parent) is specified as a child, it will be removed from our
    // ancestors and used as a child,
    this.append.apply(this, childrenCopy);
  };

  TimingGroup.prototype = createObject(TimedItem.prototype, {
    _childrenStateModified: function () {
      // See _updateChildStartTimes().
      this._isInChildrenStateModified = true;
      if (this._cachedTimedItemList) {
        this._cachedTimedItemList._ensureGetters();
      }
      this._cachedIntrinsicDuration = null;

      // We need to walk up and down the tree to re-layout. endTime and the
      // various durations (which are all calculated lazily) are the only
      // properties of a TimedItem which can affect the layout of its ancestors.
      // So it should be sufficient to simply update start times and time markers
      // on the way down.

      // This calls up to our parent, then calls _updateTimeMarkers().
      this._updateInternalState();
      this._updateChildInheritedTimes();

      // Update child start times before walking down.
      this._updateChildStartTimes();

      if (this.player) {
        this.player._checkForHandlers();
      }

      this._isInChildrenStateModified = false;
    },
    _updateInheritedTime: function (inheritedTime) {
      this._inheritedTime = inheritedTime;
      this._updateTimeMarkers();
      this._updateChildInheritedTimes();
    },
    _updateChildInheritedTimes: function () {
      for (var i = 0; i < this._children.length; i++) {
        var child = this._children[i];
        child._updateInheritedTime(this._iterationTime);
      }
    },
    _updateChildStartTimes: function () {
      if (this.type === 'seq') {
        var cumulativeStartTime = 0;
        for (var i = 0; i < this._children.length; i++) {
          var child = this._children[i];
          if (child._stashedStartTime === undefined) {
            child._stashedStartTime = child._startTime;
          }
          child._startTime = cumulativeStartTime;
          // Avoid updating the child's inherited time and time markers if this is
          // about to be done in the down phase of _childrenStateModified().
          if (!child._isInChildrenStateModified) {
            // This calls _updateTimeMarkers() on the child.
            child._updateInheritedTime(this._iterationTime);
          }
          cumulativeStartTime += Math.max(0, child.specified.delay +
            child.activeDuration);
        }
      }
    },
    get children () {
      if (!this._cachedTimedItemList) {
        this._cachedTimedItemList = new TimedItemList(
          constructorToken, this._children);
      }
      return this._cachedTimedItemList;
    },
    get firstChild () {
      return this._children[0];
    },
    get lastChild () {
      return this._children[this.children.length - 1];
    },
    _intrinsicDuration: function () {
      if (!isDefinedAndNotNull(this._cachedIntrinsicDuration)) {
        if (this.type === 'par') {
          var dur = Math.max.apply(undefined, this._children.map(function (a) {
            return a.endTime;
          }));
          this._cachedIntrinsicDuration = Math.max(0, dur);
        } else if (this.type === 'seq') {
          var result = 0;
          this._children.forEach(function (a) {
            result += a.activeDuration + a.specified.delay;
          });
          this._cachedIntrinsicDuration = result;
        } else {
          throw 'Unsupported type ' + this.type;
        }
      }
      return this._cachedIntrinsicDuration;
    },
    _getLeafItemsInEffectImpl: function (items) {
      for (var i = 0; i < this._children.length; i++) {
        this._children[i]._getLeafItemsInEffect(items);
      }
    },
    clone: function () {
      var children = [];
      this._children.forEach(function (child) {
        children.push(child.clone());
      });
      return this.type === 'par' ?
        new ParGroup(children, this.specified._dict) :
        new SeqGroup(children, this.specified._dict);
    },
    clear: function () {
      this._splice(0, this._children.length);
    },
    append: function () {
      var newItems = [];
      for (var i = 0; i < arguments.length; i++) {
        newItems.push(arguments[i]);
      }
      this._splice(this._children.length, 0, newItems);
    },
    prepend: function () {
      var newItems = [];
      for (var i = 0; i < arguments.length; i++) {
        newItems.push(arguments[i]);
      }
      this._splice(0, 0, newItems);
    },
    _addInternal: function (child) {
      this._children.push(child);
      this._childrenStateModified();
    },
    indexOf: function (item) {
      return this._children.indexOf(item);
    },
    _splice: function (start, deleteCount, newItems) {
      enterModifyCurrentAnimationState();
      try {
        var args = arguments;
        if (args.length === 3) {
          args = [start, deleteCount].concat(newItems);
        }
        for (var i = 2; i < args.length; i++) {
          var newChild = args[i];
          if (this._isInclusiveAncestor(newChild)) {
            throwNewHierarchyRequestError();
          }
          newChild._reparent(this);
        }
        var result = Array.prototype.splice.apply(this._children, args);
        for (var i = 0; i < result.length; i++) {
          result[i]._parent = null;
        }
        this._childrenStateModified();
        return result;
      } finally {
        exitModifyCurrentAnimationState(
          Boolean(this.player) && this.player._hasTicked);
      }
    },
    _isInclusiveAncestor: function (item) {
      for (var ancestor = this; ancestor !== null; ancestor = ancestor.parent) {
        if (ancestor === item) {
          return true;
        }
      }
      return false;
    },
    _isTargetingElement: function (element) {
      return this._children.some(function (child) {
        return child._isTargetingElement(element);
      });
    },
    _getAnimationsTargetingElement: function (element, animations) {
      this._children.map(function (child) {
        return child._getAnimationsTargetingElement(element, animations);
      });
    },
    toString: function () {
      return this.type + ' ' + this.startTime + '-' + this.endTime + ' (' +
        this.localTime + ') ' + ' [' +
        this._children.map(function (a) { return a.toString(); }) + ']';
    },
    _hasHandlers: function () {
      return TimedItem.prototype._hasHandlers.call(this) || (
        this._children.length > 0 &&
        this._children.reduce(
          function (a, b) { return a || b._hasHandlers(); },
          false));
    },
    _generateChildEventsForRange: function (localStart, localEnd, rangeStart,
      rangeEnd, iteration, globalTime, deltaScale) {
      var start;
      var end;

      if (localEnd - localStart > 0) {
        start = Math.max(rangeStart, localStart);
        end = Math.min(rangeEnd, localEnd);
        if (start >= end) {
          return;
        }
      } else {
        start = Math.min(rangeStart, localStart);
        end = Math.max(rangeEnd, localEnd);
        if (start <= end) {
          return;
        }
      }

      var endDelta = rangeEnd - end;
      start -= iteration * this.duration / deltaScale;
      end -= iteration * this.duration / deltaScale;

      for (var i = 0; i < this._children.length; i++) {
        this._children[i]._generateEvents(
          start, end, globalTime - endDelta, deltaScale);
      }
    }
  });



  /** @constructor */
  var ParGroup = function (children, timing, parent) {
    TimingGroup.call(this, constructorToken, 'par', children, timing, parent);
  };

  ParGroup.prototype = Object.create(TimingGroup.prototype);



  /** @constructor */
  var SeqGroup = function (children, timing, parent) {
    TimingGroup.call(this, constructorToken, 'seq', children, timing, parent);
  };

  SeqGroup.prototype = Object.create(TimingGroup.prototype);



  /** @constructor */
  var PseudoElementReference = function (element, pseudoElement) {
    this.element = element;
    this.pseudoElement = pseudoElement;
    console.warn('PseudoElementReference is not supported.');
  };



  /** @constructor */
  var MediaReference = function (mediaElement, timing, parent, delta) {
    TimedItem.call(this, constructorToken, timing, parent);
    this._media = mediaElement;

    // We can never be sure when _updateInheritedTime() is going to be called
    // next, due to skipped frames or the player being seeked. Plus the media
    // element's currentTime may drift from our iterationTime. So if a media
    // element has loop set, we can't be sure that we'll stop it before it wraps.
    // For this reason, we simply disable looping.
    // TODO: Maybe we should let it loop if our duration exceeds it's
    // length?
    this._media.loop = false;

    // If the media element has a media controller, we detach it. This mirrors the
    // behaviour when re-parenting a TimedItem, or attaching one to a Player.
    // TODO: It would be neater to assign to MediaElement.controller, but this was
    // broken in Chrome until recently. See crbug.com/226270.
    this._media.mediaGroup = '';

    this._delta = delta;
  };

  MediaReference.prototype = createObject(TimedItem.prototype, {
    _intrinsicDuration: function () {
      // TODO: This should probably default to zero. But doing so means that as
      // soon as our inheritedTime is zero, the polyfill deems the animation to be
      // done and stops ticking, so we don't get any further calls to
      // _updateInheritedTime(). One way around this would be to modify
      // TimedItem._isPastEndOfActiveInterval() to recurse down the tree, then we
      // could override it here.
      return isNaN(this._media.duration) ?
        Infinity : this._media.duration / this._media.defaultPlaybackRate;
    },
    _unscaledMediaCurrentTime: function () {
      return this._media.currentTime / this._media.defaultPlaybackRate;
    },
    _getLeafItemsInEffectImpl: function (items) {
      items.push(this);
    },
    _ensurePlaying: function () {
      // The media element is paused when created.
      if (this._media.paused) {
        this._media.play();
      }
    },
    _ensurePaused: function () {
      if (!this._media.paused) {
        this._media.pause();
      }
    },
    _isSeekableUnscaledTime: function (time) {
      var seekTime = time * this._media.defaultPlaybackRate;
      var ranges = this._media.seekable;
      for (var i = 0; i < ranges.length; i++) {
        if (seekTime >= ranges.start(i) && seekTime <= ranges.end(i)) {
          return true;
        }
      }
      return false;
    },
    // Note that a media element's timeline may not start at zero, although its
    // duration is always the timeline time at the end point. This means that an
    // element's duration isn't always it's length and not all values of the
    // timline are seekable. Furthermore, some types of media further limit the
    // range of seekable timeline times. For this reason, we always map an
    // iteration to the range [0, duration] and simply seek to the nearest
    // seekable time.
    _ensureIsAtUnscaledTime: function (time) {
      if (this._unscaledMediaCurrentTime() !== time) {
        this._media.currentTime = time * this._media.defaultPlaybackRate;
      }
    },
    // This is called by the polyfill on each tick when our Player's tree is
    // active.
    _updateInheritedTime: function (inheritedTime) {
      this._inheritedTime = inheritedTime;
      this._updateTimeMarkers();

      // The polyfill uses a sampling model whereby time values are propagated
      // down the tree at each sample. However, for the media item, we need to use
      // play() and pause().

      // Handle the case of being outside our effect interval.
      if (this._iterationTime === null) {
        this._ensureIsAtUnscaledTime(0);
        this._ensurePaused();
        return;
      }

      if (this._iterationTime >= this._intrinsicDuration()) {
        // Our iteration time exceeds the media element's duration, so just make
        // sure the media element is at the end. It will stop automatically, but
        // that could take some time if the seek below is significant, so force
        // it.
        this._ensureIsAtUnscaledTime(this._intrinsicDuration());
        this._ensurePaused();
        return;
      }

      var finalIteration = this._floorWithOpenClosedRange(
        this.specified.iterationStart + this.specified._iterations(), 1.0);
      var endTimeFraction = this._modulusWithOpenClosedRange(
        this.specified.iterationStart + this.specified._iterations(), 1.0);
      if (this.currentIteration === finalIteration &&
        this._timeFraction === endTimeFraction &&
        this._intrinsicDuration() >= this.duration) {
        // We have reached the end of our final iteration, but the media element
        // is not done.
        this._ensureIsAtUnscaledTime(this.duration * endTimeFraction);
        this._ensurePaused();
        return;
      }

      // Set the appropriate playback rate.
      var playbackRate =
        this._media.defaultPlaybackRate * this._netEffectivePlaybackRate();
      if (this._media.playbackRate !== playbackRate) {
        this._media.playbackRate = playbackRate;
      }

      // Set the appropriate play/pause state. Note that we may not be able to
      // seek to the desired time. In this case, the media element's seek
      // algorithm repositions the seek to the nearest seekable time. This is OK,
      // but in this case, we don't want to play the media element, as it prevents
      // us from synchronising properly.
      if (this.player.paused ||
        !this._isSeekableUnscaledTime(this._iterationTime)) {
        this._ensurePaused();
      } else {
        this._ensurePlaying();
      }

      // Seek if required. This could be due to our Player being seeked, or video
      // slippage. We need to handle the fact that the video may not play at
      // exactly the right speed. There's also a variable delay when the video is
      // first played.
      // TODO: What's the right value for this delta?
      var delta = isDefinedAndNotNull(this._delta) ? this._delta :
        0.2 * Math.abs(this._media.playbackRate);
      if (Math.abs(this._iterationTime - this._unscaledMediaCurrentTime()) >
        delta) {
        this._ensureIsAtUnscaledTime(this._iterationTime);
      }
    },
    _isTargetingElement: function (element) {
      return this._media === element;
    },
    _getAnimationsTargetingElement: function () { },
    _attach: function (player) {
      this._ensurePaused();
      TimedItem.prototype._attach.call(this, player);
    }
  });



  /** @constructor */
  var AnimationEffect = function (token, accumulate) {
    if (token !== constructorToken) {
      throw new TypeError('Illegal constructor');
    }
    enterModifyCurrentAnimationState();
    try {
      this.accumulate = accumulate;
    } finally {
      exitModifyCurrentAnimationState(false);
    }
  };

  AnimationEffect.prototype = {
    get accumulate () {
      return this._accumulate;
    },
    set accumulate (value) {
      enterModifyCurrentAnimationState();
      try {
        // Use the default value if an invalid string is specified.
        this._accumulate = value === 'sum' ? 'sum' : 'none';
      } finally {
        exitModifyCurrentAnimationState(true);
      }
    },
    _sample: abstractMethod,
    clone: abstractMethod,
    toString: abstractMethod
  };

  var clamp = function (x, min, max) {
    return Math.max(Math.min(x, max), min);
  };



  /** @constructor */
  var PathAnimationEffect = function (path, autoRotate, angle, composite,
    accumulate) {
    enterModifyCurrentAnimationState();
    try {
      AnimationEffect.call(this, constructorToken, accumulate);

      // Use the default value if an invalid string is specified.
      this.composite = composite;

      // TODO: path argument is not in the spec -- seems useful since
      // SVGPathSegList doesn't have a constructor.
      this.autoRotate = isDefined(autoRotate) ? autoRotate : 'none';
      this.angle = isDefined(angle) ? angle : 0;
      this._path = document.createElementNS('http://www.w3.org/2000/svg', 'path');
      if (path instanceof SVGPathSegList) {
        this.segments = path;
      } else {
        var tempPath = document.createElementNS(
          'http://www.w3.org/2000/svg', 'path');
        tempPath.setAttribute('d', String(path));
        this.segments = tempPath.pathSegList;
      }
    } finally {
      exitModifyCurrentAnimationState(false);
    }
  };

  PathAnimationEffect.prototype = createObject(AnimationEffect.prototype, {
    get composite () {
      return this._composite;
    },
    set composite (value) {
      enterModifyCurrentAnimationState();
      try {
        // Use the default value if an invalid string is specified.
        this._composite = value === 'add' ? 'add' : 'replace';
      } finally {
        exitModifyCurrentAnimationState(true);
      }
    },
    _sample: function (timeFraction, currentIteration, target) {
      // TODO: Handle accumulation.
      var lengthAtTimeFraction = this._lengthAtTimeFraction(timeFraction);
      var point = this._path.getPointAtLength(lengthAtTimeFraction);
      var x = point.x - target.offsetWidth / 2;
      var y = point.y - target.offsetHeight / 2;
      // TODO: calc(point.x - 50%) doesn't work?
      var value = [{ t: 'translate', d: [{ px: x }, { px: y }] }];
      var angle = this.angle;
      if (this._autoRotate === 'auto-rotate') {
        // Super hacks
        var lastPoint = this._path.getPointAtLength(lengthAtTimeFraction - 0.01);
        var dx = point.x - lastPoint.x;
        var dy = point.y - lastPoint.y;
        var rotation = Math.atan2(dy, dx);
        angle += rotation / 2 / Math.PI * 360;
      }
      value.push({ t: 'rotate', d: [angle] });
      compositor.setAnimatedValue(target, 'transform',
        new AddReplaceCompositableValue(value, this.composite));
    },
    _lengthAtTimeFraction: function (timeFraction) {
      var segmentCount = this._cumulativeLengths.length - 1;
      if (!segmentCount) {
        return 0;
      }
      var scaledFraction = timeFraction * segmentCount;
      var index = clamp(Math.floor(scaledFraction), 0, segmentCount);
      return this._cumulativeLengths[index] + ((scaledFraction % 1) * (
        this._cumulativeLengths[index + 1] - this._cumulativeLengths[index]));
    },
    clone: function () {
      return new PathAnimationEffect(this._path.getAttribute('d'));
    },
    _positionListForTiming: function () {
      // TODO: Handle aligning chained function segments with PathAnimationEffect.
      console.warn('Alignment of chained timing functions with path animation ' +
        'effects is not yet implemented');
      return [0, 1];
    },
    toString: function () {
      return '<PathAnimationEffect>';
    },
    set autoRotate (autoRotate) {
      enterModifyCurrentAnimationState();
      try {
        this._autoRotate = String(autoRotate);
      } finally {
        exitModifyCurrentAnimationState(true);
      }
    },
    get autoRotate () {
      return this._autoRotate;
    },
    set angle (angle) {
      enterModifyCurrentAnimationState();
      try {
        // TODO: This should probably be a string with a unit, but the spec
        //       says it's a double.
        this._angle = Number(angle);
      } finally {
        exitModifyCurrentAnimationState(true);
      }
    },
    get angle () {
      return this._angle;
    },
    set segments (segments) {
      enterModifyCurrentAnimationState();
      try {
        var targetSegments = this.segments;
        targetSegments.clear();
        var cumulativeLengths = [0];
        // TODO: *moving* the path segments is not correct, but pathSegList
        //       is read only
        var items = segments.numberOfItems;
        while (targetSegments.numberOfItems < items) {
          var segment = segments.removeItem(0);
          targetSegments.appendItem(segment);
          if (segment.pathSegType !== SVGPathSeg.PATHSEG_MOVETO_REL &&
            segment.pathSegType !== SVGPathSeg.PATHSEG_MOVETO_ABS) {
            cumulativeLengths.push(this._path.getTotalLength());
          }
        }
        this._cumulativeLengths = cumulativeLengths;
      } finally {
        exitModifyCurrentAnimationState(true);
      }
    },
    get segments () {
      return this._path.pathSegList;
    }
  });

  var shorthandToLonghand = {
    background: [
      'backgroundImage',
      'backgroundPosition',
      'backgroundSize',
      'backgroundRepeat',
      'backgroundAttachment',
      'backgroundOrigin',
      'backgroundClip',
      'backgroundColor'
    ],
    border: [
      'borderTopColor',
      'borderTopStyle',
      'borderTopWidth',
      'borderRightColor',
      'borderRightStyle',
      'borderRightWidth',
      'borderBottomColor',
      'borderBottomStyle',
      'borderBottomWidth',
      'borderLeftColor',
      'borderLeftStyle',
      'borderLeftWidth'
    ],
    borderBottom: [
      'borderBottomWidth',
      'borderBottomStyle',
      'borderBottomColor'
    ],
    borderColor: [
      'borderTopColor',
      'borderRightColor',
      'borderBottomColor',
      'borderLeftColor'
    ],
    borderLeft: [
      'borderLeftWidth',
      'borderLeftStyle',
      'borderLeftColor'
    ],
    borderRadius: [
      'borderTopLeftRadius',
      'borderTopRightRadius',
      'borderBottomRightRadius',
      'borderBottomLeftRadius'
    ],
    borderRight: [
      'borderRightWidth',
      'borderRightStyle',
      'borderRightColor'
    ],
    borderTop: [
      'borderTopWidth',
      'borderTopStyle',
      'borderTopColor'
    ],
    borderWidth: [
      'borderTopWidth',
      'borderRightWidth',
      'borderBottomWidth',
      'borderLeftWidth'
    ],
    font: [
      'fontFamily',
      'fontSize',
      'fontStyle',
      'fontVariant',
      'fontWeight',
      'lineHeight'
    ],
    margin: [
      'marginTop',
      'marginRight',
      'marginBottom',
      'marginLeft'
    ],
    outline: [
      'outlineColor',
      'outlineStyle',
      'outlineWidth'
    ],
    padding: [
      'paddingTop',
      'paddingRight',
      'paddingBottom',
      'paddingLeft'
    ]
  };

  // This delegates parsing shorthand value syntax to the browser.
  var shorthandExpanderDiv = document.createElement('div');
  var expandShorthand = function (property, value, result) {
    shorthandExpanderDiv.style[property] = value;
    var longProperties = shorthandToLonghand[property];
    for (var i in longProperties) {
      var longProperty = longProperties[i];
      var longhandValue = shorthandExpanderDiv.style[longProperty];
      result[longProperty] = longhandValue;
    }
  };

  var normalizeKeyframeDictionary = function (properties) {
    var result = {
      offset: null,
      composite: null
    };
    var animationProperties = [];
    for (var property in properties) {
      // TODO: Apply the CSS property to IDL attribute algorithm.
      if (property === 'offset') {
        if (typeof properties.offset === 'number') {
          result.offset = properties.offset;
        }
      } else if (property === 'composite') {
        if (properties.composite === 'add' ||
          properties.composite === 'replace') {
          result.composite = properties.composite;
        }
      } else {
        // TODO: Check whether this is a supported property.
        animationProperties.push(property);
      }
    }
    // TODO: Remove prefixed properties if the unprefixed version is also
    // supported and present.
    animationProperties = animationProperties.sort(playerSortFunction);
    for (var i = 0; i < animationProperties.length; i++) {
      // TODO: Apply the IDL attribute to CSS property algorithm.
      var property = animationProperties[i];
      // TODO: The spec does not specify how to handle null values.
      // See https://www.w3.org/Bugs/Public/show_bug.cgi?id=22572
      var value = isDefinedAndNotNull(properties[property]) ?
        properties[property].toString() : '';
      if (property in shorthandToLonghand) {
        expandShorthand(property, value, result);
      } else {
        result[property] = value;
      }
    }
    return result;
  };



  /** @constructor */
  var KeyframeAnimationEffect = function (oneOrMoreKeyframeDictionaries,
    composite, accumulate) {
    enterModifyCurrentAnimationState();
    try {
      AnimationEffect.call(this, constructorToken, accumulate);

      this.composite = composite;

      this.setFrames(oneOrMoreKeyframeDictionaries);
    } finally {
      exitModifyCurrentAnimationState(false);
    }
  };

  KeyframeAnimationEffect.prototype = createObject(AnimationEffect.prototype, {
    get composite () {
      return this._composite;
    },
    set composite (value) {
      enterModifyCurrentAnimationState();
      try {
        // Use the default value if an invalid string is specified.
        this._composite = value === 'add' ? 'add' : 'replace';
      } finally {
        exitModifyCurrentAnimationState(true);
      }
    },
    getFrames: function () {
      return this._keyframeDictionaries.slice(0);
    },
    setFrames: function (oneOrMoreKeyframeDictionaries) {
      enterModifyCurrentAnimationState();
      try {
        if (!Array.isArray(oneOrMoreKeyframeDictionaries)) {
          oneOrMoreKeyframeDictionaries = [oneOrMoreKeyframeDictionaries];
        }
        this._keyframeDictionaries =
          oneOrMoreKeyframeDictionaries.map(normalizeKeyframeDictionary);
        // Set lazily
        this._cachedPropertySpecificKeyframes = null;
      } finally {
        exitModifyCurrentAnimationState(true);
      }
    },
    _sample: function (timeFraction, currentIteration, target) {
      var frames = this._propertySpecificKeyframes();
      for (var property in frames) {
        compositor.setAnimatedValue(target, property,
          this._sampleForProperty(
            frames[property], timeFraction, currentIteration));
      }
    },
    _sampleForProperty: function (frames, timeFraction, currentIteration) {
      var unaccumulatedValue = this._getUnaccumulatedValue(frames, timeFraction);

      // We can only accumulate if this iteration is strictly positive and if all
      // keyframes use the same composite operation.
      if (this.accumulate === 'sum' &&
        currentIteration > 0 &&
        this._allKeyframesUseSameCompositeOperation(frames)) {
        // TODO: The spec is vague about the order of addition here when using add
        // composition.
        return new AccumulatedCompositableValue(unaccumulatedValue,
          this._getAccumulatingValue(frames), currentIteration);
      }

      return unaccumulatedValue;
    },
    _getAccumulatingValue: function (frames) {
      ASSERT_ENABLED && assert(
        this._allKeyframesUseSameCompositeOperation(frames),
        'Accumulation only valid if all frames use same composite operation');

      // This is a BlendedCompositableValue, though because the offset is 1.0, we
      // could simplify it to an AddReplaceCompositableValue representing the
      // keyframe at offset 1.0. We don't do this because the spec is likely to
      // change such that there is no guarantee that a keyframe with offset 1.0 is
      // present.
      // TODO: Consider caching this.
      var unaccumulatedValueAtOffsetOne = this._getUnaccumulatedValue(
        frames, 1.0);

      if (this._compositeForKeyframe(frames[0]) === 'add') {
        return unaccumulatedValueAtOffsetOne;
      }

      // For replace composition, we must evaluate the BlendedCompositableValue
      // to get a concrete value (note that the choice of underlying value is
      // irrelevant since it uses replace composition). We then form a new
      // AddReplaceCompositable value to add-composite this concrete value.
      ASSERT_ENABLED && assert(
        !unaccumulatedValueAtOffsetOne.dependsOnUnderlyingValue());
      return new AddReplaceCompositableValue(
        unaccumulatedValueAtOffsetOne.compositeOnto(null, null), 'add');
    },
    _getUnaccumulatedValue: function (frames, timeFraction) {
      ASSERT_ENABLED && assert(
        frames.length >= 2,
        'Interpolation requires at least two keyframes');

      var startKeyframeIndex;
      var length = frames.length;
      // We extrapolate differently depending on whether or not there are multiple
      // keyframes at offsets of 0 and 1.
      if (timeFraction < 0.0) {
        if (frames[1].offset === 0.0) {
          return new AddReplaceCompositableValue(frames[0].rawValue(),
            this._compositeForKeyframe(frames[0]));
        } else {
          startKeyframeIndex = 0;
        }
      } else if (timeFraction >= 1.0) {
        if (frames[length - 2].offset === 1.0) {
          return new AddReplaceCompositableValue(frames[length - 1].rawValue(),
            this._compositeForKeyframe(frames[length - 1]));
        } else {
          startKeyframeIndex = length - 2;
        }
      } else {
        for (var i = length - 1; i >= 0; i--) {
          if (frames[i].offset <= timeFraction) {
            ASSERT_ENABLED && assert(frames[i].offset !== 1.0);
            startKeyframeIndex = i;
            break;
          }
        }
      }
      var startKeyframe = frames[startKeyframeIndex];
      var endKeyframe = frames[startKeyframeIndex + 1];
      if (startKeyframe.offset === timeFraction) {
        return new AddReplaceCompositableValue(startKeyframe.rawValue(),
          this._compositeForKeyframe(startKeyframe));
      }
      if (endKeyframe.offset === timeFraction) {
        return new AddReplaceCompositableValue(endKeyframe.rawValue(),
          this._compositeForKeyframe(endKeyframe));
      }
      var intervalDistance = (timeFraction - startKeyframe.offset) /
        (endKeyframe.offset - startKeyframe.offset);
      return new BlendedCompositableValue(
        new AddReplaceCompositableValue(startKeyframe.rawValue(),
          this._compositeForKeyframe(startKeyframe)),
        new AddReplaceCompositableValue(endKeyframe.rawValue(),
          this._compositeForKeyframe(endKeyframe)),
        intervalDistance);
    },
    _propertySpecificKeyframes: function () {
      if (isDefinedAndNotNull(this._cachedPropertySpecificKeyframes)) {
        return this._cachedPropertySpecificKeyframes;
      }

      this._cachedPropertySpecificKeyframes = {};
      var distributedFrames = this._getDistributedKeyframes();
      for (var i = 0; i < distributedFrames.length; i++) {
        for (var property in distributedFrames[i].cssValues) {
          if (!(property in this._cachedPropertySpecificKeyframes)) {
            this._cachedPropertySpecificKeyframes[property] = [];
          }
          var frame = distributedFrames[i];
          this._cachedPropertySpecificKeyframes[property].push(
            new PropertySpecificKeyframe(frame.offset,
              frame.composite, property, frame.cssValues[property]));
        }
      }

      for (var property in this._cachedPropertySpecificKeyframes) {
        var frames = this._cachedPropertySpecificKeyframes[property];
        ASSERT_ENABLED && assert(
          frames.length > 0,
          'There should always be keyframes for each property');

        // Add synthetic keyframes at offsets of 0 and 1 if required.
        if (frames[0].offset !== 0.0) {
          var keyframe = new PropertySpecificKeyframe(0.0, 'add',
            property, cssNeutralValue);
          frames.unshift(keyframe);
        }
        if (frames[frames.length - 1].offset !== 1.0) {
          var keyframe = new PropertySpecificKeyframe(1.0, 'add',
            property, cssNeutralValue);
          frames.push(keyframe);
        }
        ASSERT_ENABLED && assert(
          frames.length >= 2,
          'There should be at least two keyframes including' +
          ' synthetic keyframes');
      }

      return this._cachedPropertySpecificKeyframes;
    },
    clone: function () {
      var result = new KeyframeAnimationEffect([], this.composite,
        this.accumulate);
      result._keyframeDictionaries = this._keyframeDictionaries.slice(0);
      return result;
    },
    toString: function () {
      return '<KeyframeAnimationEffect>';
    },
    _compositeForKeyframe: function (keyframe) {
      return isDefinedAndNotNull(keyframe.composite) ?
        keyframe.composite : this.composite;
    },
    _allKeyframesUseSameCompositeOperation: function (keyframes) {
      ASSERT_ENABLED && assert(
        keyframes.length >= 1, 'This requires at least one keyframe');
      var composite = this._compositeForKeyframe(keyframes[0]);
      for (var i = 1; i < keyframes.length; i++) {
        if (this._compositeForKeyframe(keyframes[i]) !== composite) {
          return false;
        }
      }
      return true;
    },
    _areKeyframeDictionariesLooselySorted: function () {
      var previousOffset = -Infinity;
      for (var i = 0; i < this._keyframeDictionaries.length; i++) {
        if (isDefinedAndNotNull(this._keyframeDictionaries[i].offset)) {
          if (this._keyframeDictionaries[i].offset < previousOffset) {
            return false;
          }
          previousOffset = this._keyframeDictionaries[i].offset;
        }
      }
      return true;
    },
    // The spec describes both this process and the process for interpretting the
    // properties of a keyframe dictionary as 'normalizing'. Here we use the term
    // 'distributing' to avoid confusion with normalizeKeyframeDictionary().
    _getDistributedKeyframes: function () {
      if (!this._areKeyframeDictionariesLooselySorted()) {
        return [];
      }

      var distributedKeyframes = this._keyframeDictionaries.map(
        KeyframeInternal.createFromNormalizedProperties);

      // Remove keyframes with offsets out of bounds.
      var length = distributedKeyframes.length;
      var count = 0;
      for (var i = 0; i < length; i++) {
        var offset = distributedKeyframes[i].offset;
        if (isDefinedAndNotNull(offset)) {
          if (offset >= 0) {
            break;
          } else {
            count = i;
          }
        }
      }
      distributedKeyframes.splice(0, count);

      length = distributedKeyframes.length;
      count = 0;
      for (var i = length - 1; i >= 0; i--) {
        var offset = distributedKeyframes[i].offset;
        if (isDefinedAndNotNull(offset)) {
          if (offset <= 1) {
            break;
          } else {
            count = length - i;
          }
        }
      }
      distributedKeyframes.splice(length - count, count);

      // Distribute offsets.
      length = distributedKeyframes.length;
      if (length > 1 && !isDefinedAndNotNull(distributedKeyframes[0].offset)) {
        distributedKeyframes[0].offset = 0;
      }
      if (!isDefinedAndNotNull(distributedKeyframes[length - 1].offset)) {
        distributedKeyframes[length - 1].offset = 1;
      }
      var lastOffsetIndex = 0;
      var nextOffsetIndex = 0;
      for (var i = 1; i < distributedKeyframes.length - 1; i++) {
        var keyframe = distributedKeyframes[i];
        if (isDefinedAndNotNull(keyframe.offset)) {
          lastOffsetIndex = i;
          continue;
        }
        if (i > nextOffsetIndex) {
          nextOffsetIndex = i;
          while (!isDefinedAndNotNull(
            distributedKeyframes[nextOffsetIndex].offset)) {
            nextOffsetIndex++;
          }
        }
        var lastOffset = distributedKeyframes[lastOffsetIndex].offset;
        var nextOffset = distributedKeyframes[nextOffsetIndex].offset;
        var unspecifiedKeyframes = nextOffsetIndex - lastOffsetIndex - 1;
        ASSERT_ENABLED && assert(unspecifiedKeyframes > 0);
        var localIndex = i - lastOffsetIndex;
        ASSERT_ENABLED && assert(localIndex > 0);
        distributedKeyframes[i].offset = lastOffset +
          (nextOffset - lastOffset) * localIndex / (unspecifiedKeyframes + 1);
      }

      // Remove invalid property values.
      for (var i = distributedKeyframes.length - 1; i >= 0; i--) {
        var keyframe = distributedKeyframes[i];
        for (var property in keyframe.cssValues) {
          if (!KeyframeInternal.isSupportedPropertyValue(
            keyframe.cssValues[property])) {
            delete (keyframe.cssValues[property]);
          }
        }
        if (Object.keys(keyframe).length === 0) {
          distributedKeyframes.splice(i, 1);
        }
      }

      return distributedKeyframes;
    },
    _positionListForTiming: function () {
      var positionList =
        this._getDistributedKeyframes().map(function (x) { return x.offset; });
      if (positionList[0] !== 0) {
        positionList.unshift(0);
      }
      if (positionList[positionList.length - 1] !== 1) {
        positionList.push(1);
      }
      return positionList;
    }
  });



  /**
   * An internal representation of a keyframe. The Keyframe type from the spec is
   * just a dictionary and is not exposed.
   *
   * @constructor
   */
  var KeyframeInternal = function (offset, composite) {
    ASSERT_ENABLED && assert(
      typeof offset === 'number' || offset === null,
      'Invalid offset value');
    ASSERT_ENABLED && assert(
      composite === 'add' || composite === 'replace' || composite === null,
      'Invalid composite value');
    this.offset = offset;
    this.composite = composite;
    this.cssValues = {};
  };

  KeyframeInternal.prototype = {
    addPropertyValuePair: function (property, value) {
      ASSERT_ENABLED && assert(!this.cssValues.hasOwnProperty(property));
      this.cssValues[property] = value;
    },
    hasValueForProperty: function (property) {
      return property in this.cssValues;
    }
  };

  KeyframeInternal.isSupportedPropertyValue = function (value) {
    ASSERT_ENABLED && assert(
      typeof value === 'string' || value === cssNeutralValue);
    // TODO: Check this properly!
    return value !== '';
  };

  KeyframeInternal.createFromNormalizedProperties = function (properties) {
    ASSERT_ENABLED && assert(
      isDefinedAndNotNull(properties) && typeof properties === 'object',
      'Properties must be an object');
    var keyframe = new KeyframeInternal(properties.offset, properties.composite);
    for (var candidate in properties) {
      if (candidate !== 'offset' && candidate !== 'composite') {
        keyframe.addPropertyValuePair(candidate, properties[candidate]);
      }
    }
    return keyframe;
  };



  /** @constructor */
  var PropertySpecificKeyframe = function (offset, composite, property, cssValue) {
    this.offset = offset;
    this.composite = composite;
    this.property = property;
    this.cssValue = cssValue;
    // Calculated lazily
    this.cachedRawValue = null;
  };

  PropertySpecificKeyframe.prototype = {
    rawValue: function () {
      if (!isDefinedAndNotNull(this.cachedRawValue)) {
        this.cachedRawValue = fromCssValue(this.property, this.cssValue);
      }
      return this.cachedRawValue;
    }
  };



  /** @constructor */
  var TimingFunction = function () {
    throw new TypeError('Illegal constructor');
  };

  TimingFunction.prototype.scaleTime = abstractMethod;
  TimingFunction.prototype.clone = abstractMethod;

  TimingFunction.createFromString = function (easing, easingPoints, timedItem) {
    var normalizedChain = TimingFunction.createNormalizedChain(easing,
      easingPoints, timedItem);
    ASSERT_ENABLED && assert(normalizedChain.length > 0);
    if (normalizedChain.length === 1) {
      ASSERT_ENABLED && assert(normalizedChain[0].range.min === 0);
      ASSERT_ENABLED && assert(normalizedChain[0].range.max === 1);
      return normalizedChain[0].timingFunction;
    }
    return new ChainedTimingFunction(normalizedChain);
  };

  // Returns an array of objects, where each object contains a timing function and
  // the range over which it applies.
  TimingFunction.createNormalizedChain = function (easing, easingPoints,
    timedItem) {
    var chain = TimingFunction.createChain(easing, timedItem);
    ASSERT_ENABLED && assert(chain.length > 0);

    var normalizedPositionList = TimingFunction.createNormalizedPositionList(
      easingPoints, chain.length, timedItem);
    ASSERT_ENABLED && assert(TimingFunction.isValidPositionList(
      normalizedPositionList));

    var normalizedChain = [];
    var lastTimingFunction = chain[chain.length - 1];
    for (var i = 1; i < normalizedPositionList.length; i++) {
      var range = {
        min: normalizedPositionList[i - 1],
        max: normalizedPositionList[i]
      };
      var timingFunction = i - 1 < chain.length ?
        chain[i - 1] : lastTimingFunction.clone();
      if (timingFunction instanceof PacedTimingFunction) {
        timingFunction.setRange(range);
      }
      normalizedChain.push({ timingFunction: timingFunction, range: range });
    }
    return normalizedChain;
  };

  TimingFunction.createChain = function (easing, timedItem) {
    var chain = [];
    if (typeof easing === 'string') {
      easing = easing.trim();
      while (easing.length > 0) {
        var result = TimingFunction.createComponentFromString(easing, timedItem);
        if (result === null) {
          chain = [];
          break;
        }
        chain.push(result.component);
        easing = result.remainingString.trim();
      }
    }
    if (chain.length === 0) {
      return [presetTimingFunctions.linear];
    }
    return chain;
  };

  TimingFunction.createNormalizedPositionList = function (easingPoints,
    numTimingFunctions, timedItem) {
    if (easingPoints === 'distribute') {
      return TimingFunction.generateDistributedPositionList(numTimingFunctions);
    } else if (easingPoints === 'align') {
      if (timedItem instanceof Animation &&
        // We have to test for keyframe or path effects because custom effects
        // may inherit from AnimationEffect.
        (timedItem.effect instanceof KeyframeAnimationEffect ||
          timedItem.effect instanceof PathAnimationEffect)) {
        return timedItem.effect._positionListForTiming();
      }
      return TimingFunction.generateDistributedPositionList(numTimingFunctions);
    }
    return TimingFunction.isValidPositionList(easingPoints) ? easingPoints :
      TimingFunction.generateDistributedPositionList(numTimingFunctions);
  };

  TimingFunction.generateDistributedPositionList = function (numTimingFunctions) {
    var positionList = [0];
    for (var i = 1; i <= numTimingFunctions; i++) {
      positionList.push(i / numTimingFunctions);
    }
    return positionList;
  };

  TimingFunction.isValidPositionList = function (positionList) {
    if (!Array.isArray(positionList) || positionList[0] !== 0 ||
      positionList[positionList.length - 1] !== 1) {
      return false;
    }
    for (var i = 1; i < positionList.length; i++) {
      // Test for a negative condition to correctly handle non-numeric values.
      if (!(positionList[i] > positionList[i - 1])) {
        return false;
      }
    }
    return true;
  };

  // Creates a timing function from the first valid portion of the supplied
  // string. Returns an object containg the created timing function and the
  // remaining string, or null on failure.
  TimingFunction.createComponentFromString = function (spec, timedItem) {
    var toFirstSpace = spec.split(' ')[0];
    var preset = presetTimingFunctions[toFirstSpace];
    if (preset) {
      return {
        component: preset,
        remainingString: spec.substring(toFirstSpace.length)
      };
    }
    if (spec.indexOf('paced') === 0) {
      var remainingString = spec.substring(5);
      if (timedItem instanceof Animation &&
        timedItem.effect instanceof PathAnimationEffect) {
        return {
          component: new PacedTimingFunction(timedItem.effect),
          remainingString: remainingString
        };
      }
      return {
        component: presetTimingFunctions.linear,
        remainingString: remainingString
      };
    }
    var stepMatch = /^steps\(\s*(\d+)\s*,\s*(start|end|middle)\s*\)/.exec(spec);
    if (stepMatch) {
      return {
        component: new StepTimingFunction(Number(stepMatch[1]), stepMatch[2]),
        remainingString: spec.substring(stepMatch[0].length)
      };
    }
    var bezierMatch =
      /^cubic-bezier\(([^,]*),([^,]*),([^,]*),([^)]*)\)/.exec(spec);
    if (bezierMatch) {
      return {
        component: new CubicBezierTimingFunction([
          Number(bezierMatch[1]),
          Number(bezierMatch[2]),
          Number(bezierMatch[3]),
          Number(bezierMatch[4])
        ]),
        remainingString: spec.substring(bezierMatch[0].length)
      };
    }
    return null;
  };



  /** @constructor */
  var ChainedTimingFunction = function (chain) {
    this._chain = chain;
  };

  ChainedTimingFunction.prototype = createObject(TimingFunction.prototype, {
    scaleTime: function (fraction) {
      for (var i = 0; i < this._chain.length; i++) {
        var component = this._chain[i];
        if (fraction < component.range.max || i === this._chain.length - 1) {
          return interp(
            component.range.min,
            component.range.max,
            component.timingFunction.scaleTime(
              this._relativeRange(component.range, fraction)));
        }
      }
      ASSERT_ENABLED && assert(false, 'Logic error in ChainedTimingFunction');
    },
    _relativeRange: function (range, x) {
      return (x - range.min) / (range.max - range.min);
    }
  });



  /** @constructor */
  var LinearTimingFunction = function () {
  };

  LinearTimingFunction.prototype = createObject(TimingFunction.prototype, {
    scaleTime: function (fraction) {
      return fraction;
    },
    clone: function () {
      return this;
    }
  });



  /** @constructor */
  var CubicBezierTimingFunction = function (spec) {
    this.params = spec;
    this.map = [];
    for (var ii = 0; ii <= 100; ii += 1) {
      var i = ii / 100;
      this.map.push([
        3 * i * (1 - i) * (1 - i) * this.params[0] +
        3 * i * i * (1 - i) * this.params[2] + i * i * i,
        3 * i * (1 - i) * (1 - i) * this.params[1] +
        3 * i * i * (1 - i) * this.params[3] + i * i * i
      ]);
    }
  };

  CubicBezierTimingFunction.prototype = createObject(TimingFunction.prototype, {
    scaleTime: function (fraction) {
      var fst = 0;
      while (fst !== 100 && fraction > this.map[fst][0]) {
        fst += 1;
      }
      if (fraction === this.map[fst][0] || fst === 0) {
        return this.map[fst][1];
      }
      var yDiff = this.map[fst][1] - this.map[fst - 1][1];
      var xDiff = this.map[fst][0] - this.map[fst - 1][0];
      var p = (fraction - this.map[fst - 1][0]) / xDiff;
      return this.map[fst - 1][1] + p * yDiff;
    },
    clone: function () {
      return this;
    }
  });



  /** @constructor */
  var StepTimingFunction = function (numSteps, position) {
    this.numSteps = numSteps;
    this.position = position || 'end';
  };

  StepTimingFunction.prototype = createObject(TimingFunction.prototype, {
    scaleTime: function (fraction) {
      if (fraction >= 1) {
        return 1;
      }
      var stepSize = 1 / this.numSteps;
      if (this.position === 'start') {
        fraction += stepSize;
      } else if (this.position === 'middle') {
        fraction += stepSize / 2;
      }
      return fraction - fraction % stepSize;
    },
    clone: function () {
      return this;
    }
  });

  var presetTimingFunctions = {
    'linear': new LinearTimingFunction(),
    'ease': new CubicBezierTimingFunction([0.25, 0.1, 0.25, 1.0]),
    'ease-in': new CubicBezierTimingFunction([0.42, 0, 1.0, 1.0]),
    'ease-out': new CubicBezierTimingFunction([0, 0, 0.58, 1.0]),
    'ease-in-out': new CubicBezierTimingFunction([0.42, 0, 0.58, 1.0]),
    'step-start': new StepTimingFunction(1, 'start'),
    'step-middle': new StepTimingFunction(1, 'middle'),
    'step-end': new StepTimingFunction(1, 'end')
  };



  /** @constructor */
  var PacedTimingFunction = function (pathEffect) {
    ASSERT_ENABLED && assert(pathEffect instanceof PathAnimationEffect);
    this._pathEffect = pathEffect;
    // Range is the portion of the effect over which we pace, normalized to
    // [0, 1].
    this._range = { min: 0, max: 1 };
  };

  PacedTimingFunction.prototype = createObject(TimingFunction.prototype, {
    setRange: function (range) {
      ASSERT_ENABLED && assert(range.min >= 0 && range.min <= 1);
      ASSERT_ENABLED && assert(range.max >= 0 && range.max <= 1);
      ASSERT_ENABLED && assert(range.min < range.max);
      this._range = range;
    },
    scaleTime: function (fraction) {
      var cumulativeLengths = this._pathEffect._cumulativeLengths;
      var numSegments = cumulativeLengths.length - 1;
      if (!cumulativeLengths[numSegments] || fraction <= 0) {
        return this._range.min;
      }
      if (fraction >= 1) {
        return this._range.max;
      }
      var minLength = this.lengthAtIndex(this._range.min * numSegments);
      var maxLength = this.lengthAtIndex(this._range.max * numSegments);
      var length = interp(minLength, maxLength, fraction);
      var leftIndex = this.findLeftIndex(cumulativeLengths, length);
      var leftLength = cumulativeLengths[leftIndex];
      var segmentLength = cumulativeLengths[leftIndex + 1] - leftLength;
      if (segmentLength > 0) {
        return (leftIndex + (length - leftLength) / segmentLength) / numSegments;
      }
      return leftLength / cumulativeLengths.length;
    },
    findLeftIndex: function (array, value) {
      var leftIndex = 0;
      var rightIndex = array.length;
      while (rightIndex - leftIndex > 1) {
        var midIndex = (leftIndex + rightIndex) >> 1;
        if (array[midIndex] <= value) {
          leftIndex = midIndex;
        } else {
          rightIndex = midIndex;
        }
      }
      return leftIndex;
    },
    lengthAtIndex: function (i) {
      var cumulativeLengths = this._pathEffect._cumulativeLengths;
      ASSERT_ENABLED && assert(i >= 0 && i <= cumulativeLengths.length - 1);
      var leftIndex = Math.floor(i);
      var startLength = cumulativeLengths[leftIndex];
      var endLength = cumulativeLengths[leftIndex + 1];
      var indexFraction = i % 1;
      return interp(startLength, endLength, indexFraction);
    },
    clone: function () {
      return new PacedTimingFunction(this._pathEffect);
    }
  });

  var interp = function (from, to, f, type) {
    if (Array.isArray(from) || Array.isArray(to)) {
      return interpArray(from, to, f, type);
    }
    var zero = type === 'scale' ? 1.0 : 0.0;
    to = isDefinedAndNotNull(to) ? to : zero;
    from = isDefinedAndNotNull(from) ? from : zero;

    return to * f + from * (1 - f);
  };

  var interpArray = function (from, to, f, type) {
    ASSERT_ENABLED && assert(
      Array.isArray(from) || from === null,
      'From is not an array or null');
    ASSERT_ENABLED && assert(
      Array.isArray(to) || to === null,
      'To is not an array or null');
    ASSERT_ENABLED && assert(
      from === null || to === null || from.length === to.length,
      'Arrays differ in length ' + from + ' : ' + to);
    var length = from ? from.length : to.length;

    var result = [];
    for (var i = 0; i < length; i++) {
      result[i] = interp(from ? from[i] : null, to ? to[i] : null, f, type);
    }
    return result;
  };

  var typeWithKeywords = function (keywords, type) {
    var isKeyword;
    if (keywords.length === 1) {
      var keyword = keywords[0];
      isKeyword = function (value) {
        return value === keyword;
      };
    } else {
      isKeyword = function (value) {
        return keywords.indexOf(value) >= 0;
      };
    }
    return createObject(type, {
      add: function (base, delta) {
        if (isKeyword(base) || isKeyword(delta)) {
          return delta;
        }
        return type.add(base, delta);
      },
      interpolate: function (from, to, f) {
        if (isKeyword(from) || isKeyword(to)) {
          return nonNumericType.interpolate(from, to, f);
        }
        return type.interpolate(from, to, f);
      },
      toCssValue: function (value, svgMode) {
        return isKeyword(value) ? value : type.toCssValue(value, svgMode);
      },
      fromCssValue: function (value) {
        return isKeyword(value) ? value : type.fromCssValue(value);
      }
    });
  };

  var numberType = {
    add: function (base, delta) {
      // If base or delta are 'auto', we fall back to replacement.
      if (base === 'auto' || delta === 'auto') {
        return nonNumericType.add(base, delta);
      }
      return base + delta;
    },
    interpolate: function (from, to, f) {
      // If from or to are 'auto', we fall back to step interpolation.
      if (from === 'auto' || to === 'auto') {
        return nonNumericType.interpolate(from, to);
      }
      return interp(from, to, f);
    },
    toCssValue: function (value) { return value + ''; },
    fromCssValue: function (value) {
      if (value === 'auto') {
        return 'auto';
      }
      var result = Number(value);
      return isNaN(result) ? undefined : result;
    }
  };

  var integerType = createObject(numberType, {
    interpolate: function (from, to, f) {
      // If from or to are 'auto', we fall back to step interpolation.
      if (from === 'auto' || to === 'auto') {
        return nonNumericType.interpolate(from, to);
      }
      return Math.floor(interp(from, to, f));
    }
  });

  var fontWeightType = {
    add: function (base, delta) { return base + delta; },
    interpolate: function (from, to, f) {
      return interp(from, to, f);
    },
    toCssValue: function (value) {
      value = Math.round(value / 100) * 100;
      value = clamp(value, 100, 900);
      if (value === 400) {
        return 'normal';
      }
      if (value === 700) {
        return 'bold';
      }
      return String(value);
    },
    fromCssValue: function (value) {
      // TODO: support lighter / darker ?
      var out = Number(value);
      if (isNaN(out) || out < 100 || out > 900 || out % 100 !== 0) {
        return undefined;
      }
      return out;
    }
  };

  // This regular expression is intentionally permissive, so that
  // platform-prefixed versions of calc will still be accepted as
  // input. While we are restrictive with the transform property
  // name, we need to be able to read underlying calc values from
  // computedStyle so can't easily restrict the input here.
  var outerCalcRE = /^\s*(-webkit-)?calc\s*\(\s*([^)]*)\)/;
  var valueRE = /^\s*(-?[0-9]+(\.[0-9])?[0-9]*)([a-zA-Z%]*)/;
  var operatorRE = /^\s*([+-])/;
  var autoRE = /^\s*auto/i;
  var percentLengthType = {
    zero: function () { return {}; },
    add: function (base, delta) {
      var out = {};
      for (var value in base) {
        out[value] = base[value] + (delta[value] || 0);
      }
      for (value in delta) {
        if (value in base) {
          continue;
        }
        out[value] = delta[value];
      }
      return out;
    },
    interpolate: function (from, to, f) {
      var out = {};
      for (var value in from) {
        out[value] = interp(from[value], to[value], f);
      }
      for (var value in to) {
        if (value in out) {
          continue;
        }
        out[value] = interp(0, to[value], f);
      }
      return out;
    },
    toCssValue: function (value) {
      var s = '';
      var singleValue = true;
      for (var item in value) {
        if (s === '') {
          s = value[item] + item;
        } else if (singleValue) {
          if (value[item] !== 0) {
            s = features.calcFunction +
              '(' + s + ' + ' + value[item] + item + ')';
            singleValue = false;
          }
        } else if (value[item] !== 0) {
          s = s.substring(0, s.length - 1) + ' + ' + value[item] + item + ')';
        }
      }
      return s;
    },
    fromCssValue: function (value) {
      var result = percentLengthType.consumeValueFromString(value);
      if (result) {
        return result.value;
      }
      return undefined;
    },
    consumeValueFromString: function (value) {
      if (!isDefinedAndNotNull(value)) {
        return undefined;
      }
      var autoMatch = autoRE.exec(value);
      if (autoMatch) {
        return {
          value: { auto: true },
          remaining: value.substring(autoMatch[0].length)
        };
      }
      var out = {};
      var calcMatch = outerCalcRE.exec(value);
      if (!calcMatch) {
        var singleValue = valueRE.exec(value);
        if (singleValue && (singleValue.length === 4)) {
          out[singleValue[3]] = Number(singleValue[1]);
          return {
            value: out,
            remaining: value.substring(singleValue[0].length)
          };
        }
        return undefined;
      }
      var remaining = value.substring(calcMatch[0].length);
      var calcInnards = calcMatch[2];
      var firstTime = true;
      while (true) {
        var reversed = false;
        if (firstTime) {
          firstTime = false;
        } else {
          var op = operatorRE.exec(calcInnards);
          if (!op) {
            return undefined;
          }
          if (op[1] === '-') {
            reversed = true;
          }
          calcInnards = calcInnards.substring(op[0].length);
        }
        value = valueRE.exec(calcInnards);
        if (!value) {
          return undefined;
        }
        var valueUnit = value[3];
        var valueNumber = Number(value[1]);
        if (!isDefinedAndNotNull(out[valueUnit])) {
          out[valueUnit] = 0;
        }
        if (reversed) {
          out[valueUnit] -= valueNumber;
        } else {
          out[valueUnit] += valueNumber;
        }
        calcInnards = calcInnards.substring(value[0].length);
        if (/\s*/.exec(calcInnards)[0].length === calcInnards.length) {
          return {
            value: out,
            remaining: remaining
          };
        }
      }
    },
    negate: function (value) {
      var out = {};
      for (var unit in value) {
        out[unit] = -value[unit];
      }
      return out;
    }
  };

  var percentLengthAutoType = typeWithKeywords(['auto'], percentLengthType);

  var positionKeywordRE = /^\s*left|^\s*center|^\s*right|^\s*top|^\s*bottom/i;
  var positionType = {
    zero: function () { return [{ px: 0 }, { px: 0 }]; },
    add: function (base, delta) {
      return [
        percentLengthType.add(base[0], delta[0]),
        percentLengthType.add(base[1], delta[1])
      ];
    },
    interpolate: function (from, to, f) {
      return [
        percentLengthType.interpolate(from[0], to[0], f),
        percentLengthType.interpolate(from[1], to[1], f)
      ];
    },
    toCssValue: function (value) {
      return value.map(percentLengthType.toCssValue).join(' ');
    },
    fromCssValue: function (value) {
      var tokens = [];
      var remaining = value;
      while (true) {
        var result = positionType.consumeTokenFromString(remaining);
        if (!result) {
          return undefined;
        }
        tokens.push(result.value);
        remaining = result.remaining;
        if (!result.remaining.trim()) {
          break;
        }
        if (tokens.length >= 4) {
          return undefined;
        }
      }

      if (tokens.length === 1) {
        var token = tokens[0];
        return (positionType.isHorizontalToken(token) ?
          [token, 'center'] : ['center', token]).map(positionType.resolveToken);
      }

      if (tokens.length === 2 &&
        positionType.isHorizontalToken(tokens[0]) &&
        positionType.isVerticalToken(tokens[1])) {
        return tokens.map(positionType.resolveToken);
      }

      if (tokens.filter(positionType.isKeyword).length !== 2) {
        return undefined;
      }

      var out = [undefined, undefined];
      var center = false;
      for (var i = 0; i < tokens.length; i++) {
        var token = tokens[i];
        if (!positionType.isKeyword(token)) {
          return undefined;
        }
        if (token === 'center') {
          if (center) {
            return undefined;
          }
          center = true;
          continue;
        }
        var axis = Number(positionType.isVerticalToken(token));
        if (out[axis]) {
          return undefined;
        }
        if (i === tokens.length - 1 || positionType.isKeyword(tokens[i + 1])) {
          out[axis] = positionType.resolveToken(token);
          continue;
        }
        var percentLength = tokens[++i];
        if (token === 'bottom' || token === 'right') {
          percentLength = percentLengthType.negate(percentLength);
          percentLength['%'] = (percentLength['%'] || 0) + 100;
        }
        out[axis] = percentLength;
      }
      if (center) {
        if (!out[0]) {
          out[0] = positionType.resolveToken('center');
        } else if (!out[1]) {
          out[1] = positionType.resolveToken('center');
        } else {
          return undefined;
        }
      }
      return out.every(isDefinedAndNotNull) ? out : undefined;
    },
    consumeTokenFromString: function (value) {
      var keywordMatch = positionKeywordRE.exec(value);
      if (keywordMatch) {
        return {
          value: keywordMatch[0].trim().toLowerCase(),
          remaining: value.substring(keywordMatch[0].length)
        };
      }
      return percentLengthType.consumeValueFromString(value);
    },
    resolveToken: function (token) {
      if (typeof token === 'string') {
        return percentLengthType.fromCssValue({
          left: '0%',
          center: '50%',
          right: '100%',
          top: '0%',
          bottom: '100%'
        }[token]);
      }
      return token;
    },
    isHorizontalToken: function (token) {
      if (typeof token === 'string') {
        return token in { left: true, center: true, right: true };
      }
      return true;
    },
    isVerticalToken: function (token) {
      if (typeof token === 'string') {
        return token in { top: true, center: true, bottom: true };
      }
      return true;
    },
    isKeyword: function (token) {
      return typeof token === 'string';
    }
  };

  // Spec: http://dev.w3.org/csswg/css-backgrounds/#background-position
  var positionListType = {
    zero: function () { return [positionType.zero()]; },
    add: function (base, delta) {
      var out = [];
      var maxLength = Math.max(base.length, delta.length);
      for (var i = 0; i < maxLength; i++) {
        var basePosition = base[i] ? base[i] : positionType.zero();
        var deltaPosition = delta[i] ? delta[i] : positionType.zero();
        out.push(positionType.add(basePosition, deltaPosition));
      }
      return out;
    },
    interpolate: function (from, to, f) {
      var out = [];
      var maxLength = Math.max(from.length, to.length);
      for (var i = 0; i < maxLength; i++) {
        var fromPosition = from[i] ? from[i] : positionType.zero();
        var toPosition = to[i] ? to[i] : positionType.zero();
        out.push(positionType.interpolate(fromPosition, toPosition, f));
      }
      return out;
    },
    toCssValue: function (value) {
      return value.map(positionType.toCssValue).join(', ');
    },
    fromCssValue: function (value) {
      if (!isDefinedAndNotNull(value)) {
        return undefined;
      }
      if (!value.trim()) {
        return [positionType.fromCssValue('0% 0%')];
      }
      var positionValues = value.split(',');
      var out = positionValues.map(positionType.fromCssValue);
      return out.every(isDefinedAndNotNull) ? out : undefined;
    }
  };

  var rectangleRE = /rect\(([^,]+),([^,]+),([^,]+),([^)]+)\)/;
  var rectangleType = {
    add: function (base, delta) {
      return {
        top: percentLengthType.add(base.top, delta.top),
        right: percentLengthType.add(base.right, delta.right),
        bottom: percentLengthType.add(base.bottom, delta.bottom),
        left: percentLengthType.add(base.left, delta.left)
      };
    },
    interpolate: function (from, to, f) {
      return {
        top: percentLengthType.interpolate(from.top, to.top, f),
        right: percentLengthType.interpolate(from.right, to.right, f),
        bottom: percentLengthType.interpolate(from.bottom, to.bottom, f),
        left: percentLengthType.interpolate(from.left, to.left, f)
      };
    },
    toCssValue: function (value) {
      return 'rect(' +
        percentLengthType.toCssValue(value.top) + ',' +
        percentLengthType.toCssValue(value.right) + ',' +
        percentLengthType.toCssValue(value.bottom) + ',' +
        percentLengthType.toCssValue(value.left) + ')';
    },
    fromCssValue: function (value) {
      var match = rectangleRE.exec(value);
      if (!match) {
        return undefined;
      }
      var out = {
        top: percentLengthType.fromCssValue(match[1]),
        right: percentLengthType.fromCssValue(match[2]),
        bottom: percentLengthType.fromCssValue(match[3]),
        left: percentLengthType.fromCssValue(match[4])
      };
      if (out.top && out.right && out.bottom && out.left) {
        return out;
      }
      return undefined;
    }
  };

  var shadowType = {
    zero: function () {
      return {
        hOffset: lengthType.zero(),
        vOffset: lengthType.zero()
      };
    },
    _addSingle: function (base, delta) {
      if (base && delta && base.inset !== delta.inset) {
        return delta;
      }
      var result = {
        inset: base ? base.inset : delta.inset,
        hOffset: lengthType.add(
          base ? base.hOffset : lengthType.zero(),
          delta ? delta.hOffset : lengthType.zero()),
        vOffset: lengthType.add(
          base ? base.vOffset : lengthType.zero(),
          delta ? delta.vOffset : lengthType.zero()),
        blur: lengthType.add(
          base && base.blur || lengthType.zero(),
          delta && delta.blur || lengthType.zero())
      };
      if (base && base.spread || delta && delta.spread) {
        result.spread = lengthType.add(
          base && base.spread || lengthType.zero(),
          delta && delta.spread || lengthType.zero());
      }
      if (base && base.color || delta && delta.color) {
        result.color = colorType.add(
          base && base.color || colorType.zero(),
          delta && delta.color || colorType.zero());
      }
      return result;
    },
    add: function (base, delta) {
      var result = [];
      for (var i = 0; i < base.length || i < delta.length; i++) {
        result.push(this._addSingle(base[i], delta[i]));
      }
      return result;
    },
    _interpolateSingle: function (from, to, f) {
      if (from && to && from.inset !== to.inset) {
        return f < 0.5 ? from : to;
      }
      var result = {
        inset: from ? from.inset : to.inset,
        hOffset: lengthType.interpolate(
          from ? from.hOffset : lengthType.zero(),
          to ? to.hOffset : lengthType.zero(), f),
        vOffset: lengthType.interpolate(
          from ? from.vOffset : lengthType.zero(),
          to ? to.vOffset : lengthType.zero(), f),
        blur: lengthType.interpolate(
          from && from.blur || lengthType.zero(),
          to && to.blur || lengthType.zero(), f)
      };
      if (from && from.spread || to && to.spread) {
        result.spread = lengthType.interpolate(
          from && from.spread || lengthType.zero(),
          to && to.spread || lengthType.zero(), f);
      }
      if (from && from.color || to && to.color) {
        result.color = colorType.interpolate(
          from && from.color || colorType.zero(),
          to && to.color || colorType.zero(), f);
      }
      return result;
    },
    interpolate: function (from, to, f) {
      var result = [];
      for (var i = 0; i < from.length || i < to.length; i++) {
        result.push(this._interpolateSingle(from[i], to[i], f));
      }
      return result;
    },
    _toCssValueSingle: function (value) {
      return (value.inset ? 'inset ' : '') +
        lengthType.toCssValue(value.hOffset) + ' ' +
        lengthType.toCssValue(value.vOffset) + ' ' +
        lengthType.toCssValue(value.blur) +
        (value.spread ? ' ' + lengthType.toCssValue(value.spread) : '') +
        (value.color ? ' ' + colorType.toCssValue(value.color) : '');
    },
    toCssValue: function (value) {
      return value.map(this._toCssValueSingle).join(', ');
    },
    fromCssValue: function (value) {
      var shadowRE = /(([^(,]+(\([^)]*\))?)+)/g;
      var match;
      var shadows = [];
      while ((match = shadowRE.exec(value)) !== null) {
        shadows.push(match[0]);
      }

      var result = shadows.map(function (value) {
        if (value === 'none') {
          return shadowType.zero();
        }
        value = value.replace(/^\s+|\s+$/g, '');

        var partsRE = /([^ (]+(\([^)]*\))?)/g;
        var parts = [];
        while ((match = partsRE.exec(value)) !== null) {
          parts.push(match[0]);
        }

        if (parts.length < 2 || parts.length > 7) {
          return undefined;
        }
        var result = {
          inset: false
        };

        var lengths = [];
        while (parts.length) {
          var part = parts.shift();

          var length = lengthType.fromCssValue(part);
          if (length) {
            lengths.push(length);
            continue;
          }

          var color = colorType.fromCssValue(part);
          if (color) {
            result.color = color;
          }

          if (part === 'inset') {
            result.inset = true;
          }
        }

        if (lengths.length < 2 || lengths.length > 4) {
          return undefined;
        }
        result.hOffset = lengths[0];
        result.vOffset = lengths[1];
        if (lengths.length > 2) {
          result.blur = lengths[2];
        }
        if (lengths.length > 3) {
          result.spread = lengths[3];
        }
        return result;
      });

      return result.every(isDefined) ? result : undefined;
    }
  };

  var nonNumericType = {
    add: function (base, delta) {
      return isDefined(delta) ? delta : base;
    },
    interpolate: function (from, to, f) {
      return f < 0.5 ? from : to;
    },
    toCssValue: function (value) {
      return value;
    },
    fromCssValue: function (value) {
      return value;
    }
  };

  var visibilityType = createObject(nonNumericType, {
    interpolate: function (from, to, f) {
      if (from !== 'visible' && to !== 'visible') {
        return nonNumericType.interpolate(from, to, f);
      }
      if (f <= 0) {
        return from;
      }
      if (f >= 1) {
        return to;
      }
      return 'visible';
    },
    fromCssValue: function (value) {
      if (['visible', 'hidden', 'collapse'].indexOf(value) !== -1) {
        return value;
      }
      return undefined;
    }
  });

  var lengthType = percentLengthType;
  var lengthAutoType = typeWithKeywords(['auto'], lengthType);

  var colorRE = new RegExp(
    '(hsla?|rgba?)\\(' +
    '([\\-0-9]+%?),?\\s*' +
    '([\\-0-9]+%?),?\\s*' +
    '([\\-0-9]+%?)(?:,?\\s*([\\-0-9\\.]+%?))?' +
    '\\)');
  var colorHashRE = new RegExp(
    '#([0-9A-Fa-f][0-9A-Fa-f]?)' +
    '([0-9A-Fa-f][0-9A-Fa-f]?)' +
    '([0-9A-Fa-f][0-9A-Fa-f]?)');

  function hsl2rgb (h, s, l) {
    // Cribbed from http://dev.w3.org/csswg/css-color/#hsl-color
    // Wrap to 0->360 degrees (IE -10 === 350) then normalize
    h = (((h % 360) + 360) % 360) / 360;
    s = s / 100;
    l = l / 100;
    function hue2rgb (m1, m2, h) {
      if (h < 0) {
        h += 1;
      }
      if (h > 1) {
        h -= 1;
      }
      if (h * 6 < 1) {
        return m1 + (m2 - m1) * h * 6;
      }
      if (h * 2 < 1) {
        return m2;
      }
      if (h * 3 < 2) {
        return m1 + (m2 - m1) * (2 / 3 - h) * 6;
      }
      return m1;
    }
    var m2;
    if (l <= 0.5) {
      m2 = l * (s + 1);
    } else {
      m2 = l + s - l * s;
    }

    var m1 = l * 2 - m2;
    var r = Math.ceil(hue2rgb(m1, m2, h + 1 / 3) * 255);
    var g = Math.ceil(hue2rgb(m1, m2, h) * 255);
    var b = Math.ceil(hue2rgb(m1, m2, h - 1 / 3) * 255);
    return [r, g, b];
  }

  var namedColors = {
    aliceblue: [240, 248, 255, 1],
    antiquewhite: [250, 235, 215, 1],
    aqua: [0, 255, 255, 1],
    aquamarine: [127, 255, 212, 1],
    azure: [240, 255, 255, 1],
    beige: [245, 245, 220, 1],
    bisque: [255, 228, 196, 1],
    black: [0, 0, 0, 1],
    blanchedalmond: [255, 235, 205, 1],
    blue: [0, 0, 255, 1],
    blueviolet: [138, 43, 226, 1],
    brown: [165, 42, 42, 1],
    burlywood: [222, 184, 135, 1],
    cadetblue: [95, 158, 160, 1],
    chartreuse: [127, 255, 0, 1],
    chocolate: [210, 105, 30, 1],
    coral: [255, 127, 80, 1],
    cornflowerblue: [100, 149, 237, 1],
    cornsilk: [255, 248, 220, 1],
    crimson: [220, 20, 60, 1],
    cyan: [0, 255, 255, 1],
    darkblue: [0, 0, 139, 1],
    darkcyan: [0, 139, 139, 1],
    darkgoldenrod: [184, 134, 11, 1],
    darkgray: [169, 169, 169, 1],
    darkgreen: [0, 100, 0, 1],
    darkgrey: [169, 169, 169, 1],
    darkkhaki: [189, 183, 107, 1],
    darkmagenta: [139, 0, 139, 1],
    darkolivegreen: [85, 107, 47, 1],
    darkorange: [255, 140, 0, 1],
    darkorchid: [153, 50, 204, 1],
    darkred: [139, 0, 0, 1],
    darksalmon: [233, 150, 122, 1],
    darkseagreen: [143, 188, 143, 1],
    darkslateblue: [72, 61, 139, 1],
    darkslategray: [47, 79, 79, 1],
    darkslategrey: [47, 79, 79, 1],
    darkturquoise: [0, 206, 209, 1],
    darkviolet: [148, 0, 211, 1],
    deeppink: [255, 20, 147, 1],
    deepskyblue: [0, 191, 255, 1],
    dimgray: [105, 105, 105, 1],
    dimgrey: [105, 105, 105, 1],
    dodgerblue: [30, 144, 255, 1],
    firebrick: [178, 34, 34, 1],
    floralwhite: [255, 250, 240, 1],
    forestgreen: [34, 139, 34, 1],
    fuchsia: [255, 0, 255, 1],
    gainsboro: [220, 220, 220, 1],
    ghostwhite: [248, 248, 255, 1],
    gold: [255, 215, 0, 1],
    goldenrod: [218, 165, 32, 1],
    gray: [128, 128, 128, 1],
    green: [0, 128, 0, 1],
    greenyellow: [173, 255, 47, 1],
    grey: [128, 128, 128, 1],
    honeydew: [240, 255, 240, 1],
    hotpink: [255, 105, 180, 1],
    indianred: [205, 92, 92, 1],
    indigo: [75, 0, 130, 1],
    ivory: [255, 255, 240, 1],
    khaki: [240, 230, 140, 1],
    lavender: [230, 230, 250, 1],
    lavenderblush: [255, 240, 245, 1],
    lawngreen: [124, 252, 0, 1],
    lemonchiffon: [255, 250, 205, 1],
    lightblue: [173, 216, 230, 1],
    lightcoral: [240, 128, 128, 1],
    lightcyan: [224, 255, 255, 1],
    lightgoldenrodyellow: [250, 250, 210, 1],
    lightgray: [211, 211, 211, 1],
    lightgreen: [144, 238, 144, 1],
    lightgrey: [211, 211, 211, 1],
    lightpink: [255, 182, 193, 1],
    lightsalmon: [255, 160, 122, 1],
    lightseagreen: [32, 178, 170, 1],
    lightskyblue: [135, 206, 250, 1],
    lightslategray: [119, 136, 153, 1],
    lightslategrey: [119, 136, 153, 1],
    lightsteelblue: [176, 196, 222, 1],
    lightyellow: [255, 255, 224, 1],
    lime: [0, 255, 0, 1],
    limegreen: [50, 205, 50, 1],
    linen: [250, 240, 230, 1],
    magenta: [255, 0, 255, 1],
    maroon: [128, 0, 0, 1],
    mediumaquamarine: [102, 205, 170, 1],
    mediumblue: [0, 0, 205, 1],
    mediumorchid: [186, 85, 211, 1],
    mediumpurple: [147, 112, 219, 1],
    mediumseagreen: [60, 179, 113, 1],
    mediumslateblue: [123, 104, 238, 1],
    mediumspringgreen: [0, 250, 154, 1],
    mediumturquoise: [72, 209, 204, 1],
    mediumvioletred: [199, 21, 133, 1],
    midnightblue: [25, 25, 112, 1],
    mintcream: [245, 255, 250, 1],
    mistyrose: [255, 228, 225, 1],
    moccasin: [255, 228, 181, 1],
    navajowhite: [255, 222, 173, 1],
    navy: [0, 0, 128, 1],
    oldlace: [253, 245, 230, 1],
    olive: [128, 128, 0, 1],
    olivedrab: [107, 142, 35, 1],
    orange: [255, 165, 0, 1],
    orangered: [255, 69, 0, 1],
    orchid: [218, 112, 214, 1],
    palegoldenrod: [238, 232, 170, 1],
    palegreen: [152, 251, 152, 1],
    paleturquoise: [175, 238, 238, 1],
    palevioletred: [219, 112, 147, 1],
    papayawhip: [255, 239, 213, 1],
    peachpuff: [255, 218, 185, 1],
    peru: [205, 133, 63, 1],
    pink: [255, 192, 203, 1],
    plum: [221, 160, 221, 1],
    powderblue: [176, 224, 230, 1],
    purple: [128, 0, 128, 1],
    red: [255, 0, 0, 1],
    rosybrown: [188, 143, 143, 1],
    royalblue: [65, 105, 225, 1],
    saddlebrown: [139, 69, 19, 1],
    salmon: [250, 128, 114, 1],
    sandybrown: [244, 164, 96, 1],
    seagreen: [46, 139, 87, 1],
    seashell: [255, 245, 238, 1],
    sienna: [160, 82, 45, 1],
    silver: [192, 192, 192, 1],
    skyblue: [135, 206, 235, 1],
    slateblue: [106, 90, 205, 1],
    slategray: [112, 128, 144, 1],
    slategrey: [112, 128, 144, 1],
    snow: [255, 250, 250, 1],
    springgreen: [0, 255, 127, 1],
    steelblue: [70, 130, 180, 1],
    tan: [210, 180, 140, 1],
    teal: [0, 128, 128, 1],
    thistle: [216, 191, 216, 1],
    tomato: [255, 99, 71, 1],
    transparent: [0, 0, 0, 0],
    turquoise: [64, 224, 208, 1],
    violet: [238, 130, 238, 1],
    wheat: [245, 222, 179, 1],
    white: [255, 255, 255, 1],
    whitesmoke: [245, 245, 245, 1],
    yellow: [255, 255, 0, 1],
    yellowgreen: [154, 205, 50, 1]
  };

  var colorType = typeWithKeywords(['currentColor'], {
    zero: function () { return [0, 0, 0, 0]; },
    _premultiply: function (value) {
      var alpha = value[3];
      return [value[0] * alpha, value[1] * alpha, value[2] * alpha];
    },
    add: function (base, delta) {
      var alpha = Math.min(base[3] + delta[3], 1);
      if (alpha === 0) {
        return [0, 0, 0, 0];
      }
      base = this._premultiply(base);
      delta = this._premultiply(delta);
      return [(base[0] + delta[0]) / alpha, (base[1] + delta[1]) / alpha,
      (base[2] + delta[2]) / alpha, alpha];
    },
    interpolate: function (from, to, f) {
      var alpha = clamp(interp(from[3], to[3], f), 0, 1);
      if (alpha === 0) {
        return [0, 0, 0, 0];
      }
      from = this._premultiply(from);
      to = this._premultiply(to);
      return [interp(from[0], to[0], f) / alpha,
      interp(from[1], to[1], f) / alpha,
      interp(from[2], to[2], f) / alpha, alpha];
    },
    toCssValue: function (value) {
      return 'rgba(' + Math.round(value[0]) + ', ' + Math.round(value[1]) +
        ', ' + Math.round(value[2]) + ', ' + value[3] + ')';
    },
    fromCssValue: function (value) {
      // http://dev.w3.org/csswg/css-color/#color
      var out = [];

      var regexResult = colorHashRE.exec(value);
      if (regexResult) {
        if (value.length !== 4 && value.length !== 7) {
          return undefined;
        }

        var out = [];
        regexResult.shift();
        for (var i = 0; i < 3; i++) {
          if (regexResult[i].length === 1) {
            regexResult[i] = regexResult[i] + regexResult[i];
          }
          var v = Math.max(Math.min(parseInt(regexResult[i], 16), 255), 0);
          out[i] = v;
        }
        out.push(1.0);
      }

      var regexResult = colorRE.exec(value);
      if (regexResult) {
        regexResult.shift();
        var type = regexResult.shift().substr(0, 3);
        for (var i = 0; i < 3; i++) {
          var m = 1;
          if (regexResult[i][regexResult[i].length - 1] === '%') {
            regexResult[i] = regexResult[i].substr(0, regexResult[i].length - 1);
            m = 255.0 / 100.0;
          }
          if (type === 'rgb') {
            out[i] = clamp(Math.round(parseInt(regexResult[i], 10) * m), 0, 255);
          } else {
            out[i] = parseInt(regexResult[i], 10);
          }
        }

        // Convert hsl values to rgb value
        if (type === 'hsl') {
          out = hsl2rgb.apply(null, out);
        }

        if (typeof regexResult[3] !== 'undefined') {
          out[3] = Math.max(Math.min(parseFloat(regexResult[3]), 1.0), 0.0);
        } else {
          out.push(1.0);
        }
      }

      if (out.some(isNaN)) {
        return undefined;
      }
      if (out.length > 0) {
        return out;
      }
      return namedColors[value];
    }
  });

  var convertToDeg = function (num, type) {
    switch (type) {
      case 'grad':
        return num / 400 * 360;
      case 'rad':
        return num / 2 / Math.PI * 360;
      case 'turn':
        return num * 360;
      default:
        return num;
    }
  };

  var extractValue = function (values, pos, hasUnits) {
    var value = Number(values[pos]);
    if (!hasUnits) {
      return value;
    }
    var type = values[pos + 1];
    if (type === '') { type = 'px'; }
    var result = {};
    result[type] = value;
    return result;
  };

  var extractValues = function (values, numValues, hasOptionalValue,
    hasUnits) {
    var result = [];
    for (var i = 0; i < numValues; i++) {
      result.push(extractValue(values, 1 + 2 * i, hasUnits));
    }
    if (hasOptionalValue && values[1 + 2 * numValues]) {
      result.push(extractValue(values, 1 + 2 * numValues, hasUnits));
    }
    return result;
  };

  var SPACES = '\\s*';
  var NUMBER = '[+-]?(?:\\d+|\\d*\\.\\d+)';
  var RAW_OPEN_BRACKET = '\\(';
  var RAW_CLOSE_BRACKET = '\\)';
  var RAW_COMMA = ',';
  var UNIT = '[a-zA-Z%]*';
  var START = '^';

  function capture (x) { return '(' + x + ')'; }
  function optional (x) { return '(?:' + x + ')?'; }

  var OPEN_BRACKET = [SPACES, RAW_OPEN_BRACKET, SPACES].join('');
  var CLOSE_BRACKET = [SPACES, RAW_CLOSE_BRACKET, SPACES].join('');
  var COMMA = [SPACES, RAW_COMMA, SPACES].join('');
  var UNIT_NUMBER = [capture(NUMBER), capture(UNIT)].join('');

  function transformRE (name, numParms, hasOptionalParm) {
    var tokenList = [START, SPACES, name, OPEN_BRACKET];
    for (var i = 0; i < numParms - 1; i++) {
      tokenList.push(UNIT_NUMBER);
      tokenList.push(COMMA);
    }
    tokenList.push(UNIT_NUMBER);
    if (hasOptionalParm) {
      tokenList.push(optional([COMMA, UNIT_NUMBER].join('')));
    }
    tokenList.push(CLOSE_BRACKET);
    return new RegExp(tokenList.join(''));
  }

  function buildMatcher (name, numValues, hasOptionalValue, hasUnits,
    baseValue) {
    var baseName = name;
    if (baseValue) {
      if (name[name.length - 1] === 'X' || name[name.length - 1] === 'Y') {
        baseName = name.substring(0, name.length - 1);
      } else if (name[name.length - 1] === 'Z') {
        baseName = name.substring(0, name.length - 1) + '3d';
      }
    }

    var f = function (x) {
      var r = extractValues(x, numValues, hasOptionalValue, hasUnits);
      if (baseValue !== undefined) {
        if (name[name.length - 1] === 'X') {
          r.push(baseValue);
        } else if (name[name.length - 1] === 'Y') {
          r = [baseValue].concat(r);
        } else if (name[name.length - 1] === 'Z') {
          r = [baseValue, baseValue].concat(r);
        } else if (hasOptionalValue) {
          while (r.length < 2) {
            if (baseValue === 'copy') {
              r.push(r[0]);
            } else {
              r.push(baseValue);
            }
          }
        }
      }
      return r;
    };
    return [transformRE(name, numValues, hasOptionalValue), f, baseName];
  }

  function buildRotationMatcher (name, numValues, hasOptionalValue,
    baseValue) {
    var m = buildMatcher(name, numValues, hasOptionalValue, true, baseValue);

    var f = function (x) {
      var r = m[1](x);
      return r.map(function (v) {
        var result = 0;
        for (var type in v) {
          result += convertToDeg(v[type], type);
        }
        return result;
      });
    };
    return [m[0], f, m[2]];
  }

  function build3DRotationMatcher () {
    var m = buildMatcher('rotate3d', 4, false, true);
    var f = function (x) {
      var r = m[1](x);
      var out = [];
      for (var i = 0; i < 3; i++) {
        out.push(r[i].px);
      }
      out.push(r[3]);
      return out;
    };
    return [m[0], f, m[2]];
  }

  var transformREs = [
    buildRotationMatcher('rotate', 1, false),
    buildRotationMatcher('rotateX', 1, false),
    buildRotationMatcher('rotateY', 1, false),
    buildRotationMatcher('rotateZ', 1, false),
    build3DRotationMatcher(),
    buildRotationMatcher('skew', 1, true, 0),
    buildRotationMatcher('skewX', 1, false),
    buildRotationMatcher('skewY', 1, false),
    buildMatcher('translateX', 1, false, true, { px: 0 }),
    buildMatcher('translateY', 1, false, true, { px: 0 }),
    buildMatcher('translateZ', 1, false, true, { px: 0 }),
    buildMatcher('translate', 1, true, true, { px: 0 }),
    buildMatcher('translate3d', 3, false, true),
    buildMatcher('scale', 1, true, false, 'copy'),
    buildMatcher('scaleX', 1, false, false, 1),
    buildMatcher('scaleY', 1, false, false, 1),
    buildMatcher('scaleZ', 1, false, false, 1),
    buildMatcher('scale3d', 3, false, false),
    buildMatcher('perspective', 1, false, true),
    buildMatcher('matrix', 6, false, false)
  ];

  var decomposeMatrix = (function () {
    // this is only ever used on the perspective matrix, which has 0, 0, 0, 1 as
    // last column
    function determinant (m) {
      return m[0][0] * m[1][1] * m[2][2] +
        m[1][0] * m[2][1] * m[0][2] +
        m[2][0] * m[0][1] * m[1][2] -
        m[0][2] * m[1][1] * m[2][0] -
        m[1][2] * m[2][1] * m[0][0] -
        m[2][2] * m[0][1] * m[1][0];
    }

    // this is only ever used on the perspective matrix, which has 0, 0, 0, 1 as
    // last column
    //
    // from Wikipedia:
    //
    // [A B]^-1 = [A^-1 + A^-1B(D - CA^-1B)^-1CA^-1     -A^-1B(D - CA^-1B)^-1]
    // [C D]      [-(D - CA^-1B)^-1CA^-1                (D - CA^-1B)^-1      ]
    //
    // Therefore
    //
    // [A [0]]^-1 = [A^-1       [0]]
    // [C  1 ]      [ -CA^-1     1 ]
    function inverse (m) {
      var iDet = 1 / determinant(m);
      var a = m[0][0], b = m[0][1], c = m[0][2];
      var d = m[1][0], e = m[1][1], f = m[1][2];
      var g = m[2][0], h = m[2][1], k = m[2][2];
      var Ainv = [
        [(e * k - f * h) * iDet, (c * h - b * k) * iDet,
        (b * f - c * e) * iDet, 0],
        [(f * g - d * k) * iDet, (a * k - c * g) * iDet,
        (c * d - a * f) * iDet, 0],
        [(d * h - e * g) * iDet, (g * b - a * h) * iDet,
        (a * e - b * d) * iDet, 0]
      ];
      var lastRow = [];
      for (var i = 0; i < 3; i++) {
        var val = 0;
        for (var j = 0; j < 3; j++) {
          val += m[3][j] * Ainv[j][i];
        }
        lastRow.push(val);
      }
      lastRow.push(1);
      Ainv.push(lastRow);
      return Ainv;
    }

    function transposeMatrix4 (m) {
      return [[m[0][0], m[1][0], m[2][0], m[3][0]],
      [m[0][1], m[1][1], m[2][1], m[3][1]],
      [m[0][2], m[1][2], m[2][2], m[3][2]],
      [m[0][3], m[1][3], m[2][3], m[3][3]]];
    }

    function multVecMatrix (v, m) {
      var result = [];
      for (var i = 0; i < 4; i++) {
        var val = 0;
        for (var j = 0; j < 4; j++) {
          val += v[j] * m[j][i];
        }
        result.push(val);
      }
      return result;
    }

    function normalize (v) {
      var len = length(v);
      return [v[0] / len, v[1] / len, v[2] / len];
    }

    function length (v) {
      return Math.sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
    }

    function combine (v1, v2, v1s, v2s) {
      return [v1s * v1[0] + v2s * v2[0], v1s * v1[1] + v2s * v2[1],
      v1s * v1[2] + v2s * v2[2]];
    }

    function cross (v1, v2) {
      return [v1[1] * v2[2] - v1[2] * v2[1],
      v1[2] * v2[0] - v1[0] * v2[2],
      v1[0] * v2[1] - v1[1] * v2[0]];
    }

    function decomposeMatrix (matrix) {
      var m3d = [[matrix[0], matrix[1], 0, 0],
      [matrix[2], matrix[3], 0, 0],
      [0, 0, 1, 0],
      [matrix[4], matrix[5], 0, 1]];

      // skip normalization step as m3d[3][3] should always be 1
      if (m3d[3][3] !== 1) {
        throw 'attempt to decompose non-normalized matrix';
      }

      var perspectiveMatrix = m3d.concat(); // copy m3d
      for (var i = 0; i < 3; i++) {
        perspectiveMatrix[i][3] = 0;
      }

      if (determinant(perspectiveMatrix) === 0) {
        return false;
      }

      var rhs = [];

      var perspective;
      if (m3d[0][3] !== 0 || m3d[1][3] !== 0 || m3d[2][3] !== 0) {
        rhs.push(m3d[0][3]);
        rhs.push(m3d[1][3]);
        rhs.push(m3d[2][3]);
        rhs.push(m3d[3][3]);

        var inversePerspectiveMatrix = inverse(perspectiveMatrix);
        var transposedInversePerspectiveMatrix =
          transposeMatrix4(inversePerspectiveMatrix);
        perspective = multVecMatrix(rhs, transposedInversePerspectiveMatrix);
      } else {
        perspective = [0, 0, 0, 1];
      }

      var translate = m3d[3].slice(0, 3);

      var row = [];
      row.push(m3d[0].slice(0, 3));
      var scale = [];
      scale.push(length(row[0]));
      row[0] = normalize(row[0]);

      var skew = [];
      row.push(m3d[1].slice(0, 3));
      skew.push(dot(row[0], row[1]));
      row[1] = combine(row[1], row[0], 1.0, -skew[0]);

      scale.push(length(row[1]));
      row[1] = normalize(row[1]);
      skew[0] /= scale[1];

      row.push(m3d[2].slice(0, 3));
      skew.push(dot(row[0], row[2]));
      row[2] = combine(row[2], row[0], 1.0, -skew[1]);
      skew.push(dot(row[1], row[2]));
      row[2] = combine(row[2], row[1], 1.0, -skew[2]);

      scale.push(length(row[2]));
      row[2] = normalize(row[2]);
      skew[1] /= scale[2];
      skew[2] /= scale[2];

      var pdum3 = cross(row[1], row[2]);
      if (dot(row[0], pdum3) < 0) {
        for (var i = 0; i < 3; i++) {
          scale[i] *= -1;
          row[i][0] *= -1;
          row[i][1] *= -1;
          row[i][2] *= -1;
        }
      }

      var t = row[0][0] + row[1][1] + row[2][2] + 1;
      var s;
      var quaternion;

      if (t > 1e-4) {
        s = 0.5 / Math.sqrt(t);
        quaternion = [
          (row[2][1] - row[1][2]) * s,
          (row[0][2] - row[2][0]) * s,
          (row[1][0] - row[0][1]) * s,
          0.25 / s
        ];
      } else if (row[0][0] > row[1][1] && row[0][0] > row[2][2]) {
        s = Math.sqrt(1 + row[0][0] - row[1][1] - row[2][2]) * 2.0;
        quaternion = [
          0.25 * s,
          (row[0][1] + row[1][0]) / s,
          (row[0][2] + row[2][0]) / s,
          (row[2][1] - row[1][2]) / s
        ];
      } else if (row[1][1] > row[2][2]) {
        s = Math.sqrt(1.0 + row[1][1] - row[0][0] - row[2][2]) * 2.0;
        quaternion = [
          (row[0][1] + row[1][0]) / s,
          0.25 * s,
          (row[1][2] + row[2][1]) / s,
          (row[0][2] - row[2][0]) / s
        ];
      } else {
        s = Math.sqrt(1.0 + row[2][2] - row[0][0] - row[1][1]) * 2.0;
        quaternion = [
          (row[0][2] + row[2][0]) / s,
          (row[1][2] + row[2][1]) / s,
          0.25 * s,
          (row[1][0] - row[0][1]) / s
        ];
      }

      return {
        translate: translate, scale: scale, skew: skew,
        quaternion: quaternion, perspective: perspective
      };
    }
    return decomposeMatrix;
  })();

  function dot (v1, v2) {
    var result = 0;
    for (var i = 0; i < v1.length; i++) {
      result += v1[i] * v2[i];
    }
    return result;
  }

  function multiplyMatrices (a, b) {
    return [a[0] * b[0] + a[2] * b[1], a[1] * b[0] + a[3] * b[1],
    a[0] * b[2] + a[2] * b[3], a[1] * b[2] + a[3] * b[3],
    a[0] * b[4] + a[2] * b[5] + a[4], a[1] * b[4] + a[3] * b[5] + a[5]];
  }

  function convertItemToMatrix (item) {
    switch (item.t) {
      case 'rotate':
        var amount = item.d * Math.PI / 180;
        return [Math.cos(amount), Math.sin(amount),
        -Math.sin(amount), Math.cos(amount), 0, 0];
      case 'scale':
        return [item.d[0], 0, 0, item.d[1], 0, 0];
      // TODO: Work out what to do with non-px values.
      case 'translate':
        return [1, 0, 0, 1, item.d[0].px, item.d[1].px];
      case 'matrix':
        return item.d;
    }
  }

  function convertToMatrix (transformList) {
    return transformList.map(convertItemToMatrix).reduce(multiplyMatrices);
  }

  var composeMatrix = (function () {
    function multiply (a, b) {
      var result = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]];
      for (var i = 0; i < 4; i++) {
        for (var j = 0; j < 4; j++) {
          for (var k = 0; k < 4; k++) {
            result[i][j] += b[i][k] * a[k][j];
          }
        }
      }
      return result;
    }

    function composeMatrix (translate, scale, skew, quat, perspective) {
      var matrix = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]];

      for (var i = 0; i < 4; i++) {
        matrix[i][3] = perspective[i];
      }

      for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
          matrix[3][i] += translate[j] * matrix[j][i];
        }
      }

      var x = quat[0], y = quat[1], z = quat[2], w = quat[3];

      var rotMatrix = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]];

      rotMatrix[0][0] = 1 - 2 * (y * y + z * z);
      rotMatrix[0][1] = 2 * (x * y - z * w);
      rotMatrix[0][2] = 2 * (x * z + y * w);
      rotMatrix[1][0] = 2 * (x * y + z * w);
      rotMatrix[1][1] = 1 - 2 * (x * x + z * z);
      rotMatrix[1][2] = 2 * (y * z - x * w);
      rotMatrix[2][0] = 2 * (x * z - y * w);
      rotMatrix[2][1] = 2 * (y * z + x * w);
      rotMatrix[2][2] = 1 - 2 * (x * x + y * y);

      matrix = multiply(matrix, rotMatrix);

      var temp = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]];
      if (skew[2]) {
        temp[2][1] = skew[2];
        matrix = multiply(matrix, temp);
      }

      if (skew[1]) {
        temp[2][1] = 0;
        temp[2][0] = skew[0];
        matrix = multiply(matrix, temp);
      }

      for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
          matrix[i][j] *= scale[i];
        }
      }

      return {
        t: 'matrix', d: [matrix[0][0], matrix[0][1],
        matrix[1][0], matrix[1][1],
        matrix[3][0], matrix[3][1]]
      };
    }
    return composeMatrix;
  })();

  function interpolateTransformsWithMatrices (from, to, f) {
    var fromM = decomposeMatrix(convertToMatrix(from));
    var toM = decomposeMatrix(convertToMatrix(to));

    var product = dot(fromM.quaternion, toM.quaternion);
    product = clamp(product, -1.0, 1.0);

    var quat = [];
    if (product === 1.0) {
      quat = fromM.quaternion;
    } else {
      var theta = Math.acos(product);
      var w = Math.sin(f * theta) * 1 / Math.sqrt(1 - product * product);

      for (var i = 0; i < 4; i++) {
        quat.push(fromM.quaternion[i] * (Math.cos(f * theta) - product * w) +
          toM.quaternion[i] * w);
      }
    }

    var translate = interp(fromM.translate, toM.translate, f);
    var scale = interp(fromM.scale, toM.scale, f);
    var skew = interp(fromM.skew, toM.skew, f);
    var perspective = interp(fromM.perspective, toM.perspective, f);

    return composeMatrix(translate, scale, skew, quat, perspective);
  }

  function interpTransformValue (from, to, f) {
    var type = from.t ? from.t : to.t;
    switch (type) {
      // Transforms with unitless parameters.
      case 'rotate':
      case 'rotateX':
      case 'rotateY':
      case 'rotateZ':
      case 'scale':
      case 'scaleX':
      case 'scaleY':
      case 'scaleZ':
      case 'scale3d':
      case 'skew':
      case 'skewX':
      case 'skewY':
      case 'matrix':
        return { t: type, d: interp(from.d, to.d, f, type) };
      default:
        // Transforms with lengthType parameters.
        var result = [];
        var maxVal;
        if (from.d && to.d) {
          maxVal = Math.max(from.d.length, to.d.length);
        } else if (from.d) {
          maxVal = from.d.length;
        } else {
          maxVal = to.d.length;
        }
        for (var j = 0; j < maxVal; j++) {
          var fromVal = from.d ? from.d[j] : {};
          var toVal = to.d ? to.d[j] : {};
          result.push(lengthType.interpolate(fromVal, toVal, f));
        }
        return { t: type, d: result };
    }
  }

  // The CSSWG decided to disallow scientific notation in CSS property strings
  // (see http://lists.w3.org/Archives/Public/www-style/2010Feb/0050.html).
  // We need this function to hakonitize all numbers before adding them to
  // property strings.
  // TODO: Apply this function to all property strings
  function n (num) {
    return Number(num).toFixed(4);
  }

  var transformType = {
    add: function (base, delta) { return base.concat(delta); },
    interpolate: function (from, to, f) {
      var out = [];
      for (var i = 0; i < Math.min(from.length, to.length); i++) {
        if (from[i].t !== to[i].t) {
          break;
        }
        out.push(interpTransformValue(from[i], to[i], f));
      }

      if (i < Math.min(from.length, to.length)) {
        out.push(interpolateTransformsWithMatrices(from.slice(i), to.slice(i),
          f));
        return out;
      }

      for (; i < from.length; i++) {
        out.push(interpTransformValue(from[i], { t: null, d: null }, f));
      }
      for (; i < to.length; i++) {
        out.push(interpTransformValue({ t: null, d: null }, to[i], f));
      }
      return out;
    },
    toCssValue: function (value, svgMode) {
      // TODO: fix this :)
      var out = '';
      for (var i = 0; i < value.length; i++) {
        ASSERT_ENABLED && assert(
          value[i].t, 'transform type should be resolved by now');
        switch (value[i].t) {
          case 'rotate':
          case 'rotateX':
          case 'rotateY':
          case 'rotateZ':
          case 'skewX':
          case 'skewY':
            var unit = svgMode ? '' : 'deg';
            out += value[i].t + '(' + value[i].d + unit + ') ';
            break;
          case 'skew':
            var unit = svgMode ? '' : 'deg';
            out += value[i].t + '(' + value[i].d[0] + unit;
            if (value[i].d[1] === 0) {
              out += ') ';
            } else {
              out += ', ' + value[i].d[1] + unit + ') ';
            }
            break;
          case 'translateX':
          case 'translateY':
          case 'translateZ':
          case 'perspective':
            out += value[i].t + '(' + lengthType.toCssValue(value[i].d[0]) +
              ') ';
            break;
          case 'translate':
            if (svgMode) {
              if (value[i].d[1] === undefined) {
                out += value[i].t + '(' + value[i].d[0].px + ') ';
              } else {
                out += (
                  value[i].t + '(' + value[i].d[0].px + ', ' +
                  value[i].d[1].px + ') ');
              }
              break;
            }
            if (value[i].d[1] === undefined) {
              out += value[i].t + '(' + lengthType.toCssValue(value[i].d[0]) +
                ') ';
            } else {
              out += value[i].t + '(' + lengthType.toCssValue(value[i].d[0]) +
                ', ' + lengthType.toCssValue(value[i].d[1]) + ') ';
            }
            break;
          case 'translate3d':
            var values = value[i].d.map(lengthType.toCssValue);
            out += value[i].t + '(' + values[0] + ', ' + values[1] +
              ', ' + values[2] + ') ';
            break;
          case 'scale':
            if (value[i].d[0] === value[i].d[1]) {
              out += value[i].t + '(' + value[i].d[0] + ') ';
            } else {
              out += value[i].t + '(' + value[i].d[0] + ', ' + value[i].d[1] +
                ') ';
            }
            break;
          case 'scaleX':
          case 'scaleY':
          case 'scaleZ':
            out += value[i].t + '(' + value[i].d[0] + ') ';
            break;
          case 'scale3d':
            out += value[i].t + '(' + value[i].d[0] + ', ' +
              value[i].d[1] + ', ' + value[i].d[2] + ') ';
            break;
          case 'matrix':
            out += value[i].t + '(' +
              n(value[i].d[0]) + ', ' + n(value[i].d[1]) + ', ' +
              n(value[i].d[2]) + ', ' + n(value[i].d[3]) + ', ' +
              n(value[i].d[4]) + ', ' + n(value[i].d[5]) + ') ';
            break;
        }
      }
      return out.substring(0, out.length - 1);
    },
    fromCssValue: function (value) {
      // TODO: fix this :)
      if (value === undefined) {
        return undefined;
      }
      var result = [];
      while (value.length > 0) {
        var r;
        for (var i = 0; i < transformREs.length; i++) {
          var reSpec = transformREs[i];
          r = reSpec[0].exec(value);
          if (r) {
            result.push({ t: reSpec[2], d: reSpec[1](r) });
            value = value.substring(r[0].length);
            break;
          }
        }
        if (!isDefinedAndNotNull(r)) {
          return result;
        }
      }
      return result;
    }
  };

  var pathType = {
    // Properties ...
    // - path: The target path element
    // - points: The absolute points to set on the path
    // - cachedCumulativeLengths: The lengths at the end of each segment
    add: function () { throw 'Addition not supported for path attribute' },
    cumulativeLengths: function (value) {
      if (isDefinedAndNotNull(value.cachedCumulativeLengths))
        return value.cachedCumulativeLengths;
      var path = value.path.cloneNode(true);
      var cumulativeLengths = [];
      while (path.pathSegList.numberOfItems > 0) {
        // TODO: It would be good to skip moves here and when generating points.
        cumulativeLengths.unshift(path.getTotalLength());
        path.pathSegList.removeItem(path.pathSegList.numberOfItems - 1);
      }
      value.cachedCumulativeLengths = cumulativeLengths;
      return value.cachedCumulativeLengths;
    },
    appendFractions: function (fractions, cumulativeLengths) {
      console.assert(cumulativeLengths[0] === 0);
      var totalLength = cumulativeLengths[cumulativeLengths.length - 1];
      for (var i = 1; i < cumulativeLengths.length - 1; ++i)
        fractions.push(cumulativeLengths[i] / totalLength);
    },
    interpolate: function (from, to, f) {
      // TODO: Handle non-linear path segments.
      // Get the fractions at which we need to sample.
      var sampleFractions = [0, 1];
      pathType.appendFractions(sampleFractions, pathType.cumulativeLengths(from));
      pathType.appendFractions(sampleFractions, pathType.cumulativeLengths(to));
      sampleFractions.sort();
      console.assert(sampleFractions[0] === 0);
      console.assert(sampleFractions[sampleFractions.length - 1] === 1);

      // FIXME: Cache the 'from' and 'to' points.
      var fromTotalLength = from.path.getTotalLength();
      var toTotalLength = to.path.getTotalLength();
      var points = [];
      for (var i = 0; i < sampleFractions.length; ++i) {
        var fromPoint = from.path.getPointAtLength(fromTotalLength * sampleFractions[i]);
        var toPoint = to.path.getPointAtLength(toTotalLength * sampleFractions[i]);
        points.push({ x: interp(fromPoint.x, toPoint.x, f), y: interp(fromPoint.y, toPoint.y, f) });
      }
      return { points: points };
    },
    pointToString: function (point) {
      return point.x + ',' + point.y;
    },
    toCssValue: function (value, svgMode) {
      // TODO: It would be good to use PathSegList API on the target directly,
      // rather than generating this string, but that would require a hack to
      // setValue().
      console.assert(svgMode, 'Path type should only be used with SVG \'d\' attribute');
      var ret = 'M' + pathType.pointToString(value.points[0]);
      for (var i = 1; i < value.points.length; ++i)
        ret += 'L' + pathType.pointToString(value.points[i]);
      return ret;
    },
    fromCssValue: function (value) {
      var path = document.createElementNS('http://www.w3.org/2000/svg', 'path');
      path.setAttribute('d', value);
      return { path: path };
    }
  };

  var propertyTypes = {
    backgroundColor: colorType,
    backgroundPosition: positionListType,
    borderBottomColor: colorType,
    borderBottomLeftRadius: percentLengthType,
    borderBottomRightRadius: percentLengthType,
    borderBottomWidth: lengthType,
    borderLeftColor: colorType,
    borderLeftWidth: lengthType,
    borderRightColor: colorType,
    borderRightWidth: lengthType,
    borderSpacing: lengthType,
    borderTopColor: colorType,
    borderTopLeftRadius: percentLengthType,
    borderTopRightRadius: percentLengthType,
    borderTopWidth: lengthType,
    bottom: percentLengthAutoType,
    clip: typeWithKeywords(['auto'], rectangleType),
    color: colorType,
    cx: lengthType,
    d: pathType,

    // TODO: Handle these keywords properly.
    fontSize: typeWithKeywords(['smaller', 'larger'], percentLengthType),
    fontWeight: typeWithKeywords(['lighter', 'bolder'], fontWeightType),

    height: percentLengthAutoType,
    left: percentLengthAutoType,
    letterSpacing: typeWithKeywords(['normal'], lengthType),
    lineHeight: percentLengthType, // TODO: Should support numberType as well.
    marginBottom: lengthAutoType,
    marginLeft: lengthAutoType,
    marginRight: lengthAutoType,
    marginTop: lengthAutoType,
    maxHeight: typeWithKeywords(
      ['none', 'max-content', 'min-content', 'fill-available', 'fit-content'],
      percentLengthType),
    maxWidth: typeWithKeywords(
      ['none', 'max-content', 'min-content', 'fill-available', 'fit-content'],
      percentLengthType),
    minHeight: typeWithKeywords(
      ['max-content', 'min-content', 'fill-available', 'fit-content'],
      percentLengthType),
    minWidth: typeWithKeywords(
      ['max-content', 'min-content', 'fill-available', 'fit-content'],
      percentLengthType),
    opacity: numberType,
    outlineColor: typeWithKeywords(['invert'], colorType),
    outlineOffset: lengthType,
    outlineWidth: lengthType,
    paddingBottom: lengthType,
    paddingLeft: lengthType,
    paddingRight: lengthType,
    paddingTop: lengthType,
    right: percentLengthAutoType,
    textIndent: typeWithKeywords(['each-line', 'hanging'], percentLengthType),
    textShadow: shadowType,
    top: percentLengthAutoType,
    transform: transformType,
    verticalAlign: typeWithKeywords([
      'baseline',
      'sub',
      'super',
      'text-top',
      'text-bottom',
      'middle',
      'top',
      'bottom'
    ], percentLengthType),
    visibility: visibilityType,
    width: typeWithKeywords([
      'border-box',
      'content-box',
      'auto',
      'max-content',
      'min-content',
      'available',
      'fit-content'
    ], percentLengthType),
    wordSpacing: typeWithKeywords(['normal'], percentLengthType),
    x: lengthType,
    y: lengthType,
    zIndex: typeWithKeywords(['auto'], integerType)
  };

  var svgProperties = {
    'cx': 1,
    'd': 1,
    'width': 1,
    'x': 1,
    'y': 1
  };

  var borderWidthAliases = {
    initial: '3px',
    thin: '1px',
    medium: '3px',
    thick: '5px'
  };

  var propertyValueAliases = {
    backgroundColor: { initial: 'transparent' },
    backgroundPosition: { initial: '0% 0%' },
    borderBottomColor: { initial: 'currentColor' },
    borderBottomLeftRadius: { initial: '0px' },
    borderBottomRightRadius: { initial: '0px' },
    borderBottomWidth: borderWidthAliases,
    borderLeftColor: { initial: 'currentColor' },
    borderLeftWidth: borderWidthAliases,
    borderRightColor: { initial: 'currentColor' },
    borderRightWidth: borderWidthAliases,
    // Spec says this should be 0 but in practise it is 2px.
    borderSpacing: { initial: '2px' },
    borderTopColor: { initial: 'currentColor' },
    borderTopLeftRadius: { initial: '0px' },
    borderTopRightRadius: { initial: '0px' },
    borderTopWidth: borderWidthAliases,
    bottom: { initial: 'auto' },
    clip: { initial: 'rect(0px, 0px, 0px, 0px)' },
    color: { initial: 'black' }, // Depends on user agent.
    fontSize: {
      initial: '100%',
      'xx-small': '60%',
      'x-small': '75%',
      'small': '89%',
      'medium': '100%',
      'large': '120%',
      'x-large': '150%',
      'xx-large': '200%'
    },
    fontWeight: {
      initial: '400',
      normal: '400',
      bold: '700'
    },
    height: { initial: 'auto' },
    left: { initial: 'auto' },
    letterSpacing: { initial: 'normal' },
    lineHeight: {
      initial: '120%',
      normal: '120%'
    },
    marginBottom: { initial: '0px' },
    marginLeft: { initial: '0px' },
    marginRight: { initial: '0px' },
    marginTop: { initial: '0px' },
    maxHeight: { initial: 'none' },
    maxWidth: { initial: 'none' },
    minHeight: { initial: '0px' },
    minWidth: { initial: '0px' },
    opacity: { initial: '1.0' },
    outlineColor: { initial: 'invert' },
    outlineOffset: { initial: '0px' },
    outlineWidth: borderWidthAliases,
    paddingBottom: { initial: '0px' },
    paddingLeft: { initial: '0px' },
    paddingRight: { initial: '0px' },
    paddingTop: { initial: '0px' },
    right: { initial: 'auto' },
    textIndent: { initial: '0px' },
    textShadow: {
      initial: '0px 0px 0px transparent',
      none: '0px 0px 0px transparent'
    },
    top: { initial: 'auto' },
    transform: {
      initial: '',
      none: ''
    },
    verticalAlign: { initial: '0px' },
    visibility: { initial: 'visible' },
    width: { initial: 'auto' },
    wordSpacing: { initial: 'normal' },
    zIndex: { initial: 'auto' }
  };

  var propertyIsSVGAttrib = function (property, target) {
    return target.namespaceURI === 'http://www.w3.org/2000/svg' &&
      property in svgProperties;
  };

  var getType = function (property) {
    return propertyTypes[property] || nonNumericType;
  };

  var add = function (property, base, delta) {
    if (delta === rawNeutralValue) {
      return base;
    }
    if (base === 'inherit' || delta === 'inherit') {
      return nonNumericType.add(base, delta);
    }
    return getType(property).add(base, delta);
  };


  /**
   * Interpolate the given property name (f*100)% of the way from 'from' to 'to'.
   * 'from' and 'to' are both raw values already converted from CSS value
   * strings. Requires the target element to be able to determine whether the
   * given property is an SVG attribute or not, as this impacts the conversion of
   * the interpolated value back into a CSS value string for transform
   * translations.
   *
   * e.g. interpolate('transform', elem, 'rotate(40deg)', 'rotate(50deg)', 0.3);
   *   will return 'rotate(43deg)'.
   */
  var interpolate = function (property, from, to, f) {
    ASSERT_ENABLED && assert(
      isDefinedAndNotNull(from) && isDefinedAndNotNull(to),
      'Both to and from values should be specified for interpolation');
    if (from === 'inherit' || to === 'inherit') {
      return nonNumericType.interpolate(from, to, f);
    }
    if (f === 0) {
      return from;
    }
    if (f === 1) {
      return to;
    }
    return getType(property).interpolate(from, to, f);
  };


  /**
   * Convert the provided interpolable value for the provided property to a CSS
   * value string. Note that SVG transforms do not require units for translate
   * or rotate values while CSS properties require 'px' or 'deg' units.
   */
  var toCssValue = function (property, value, svgMode) {
    if (value === 'inherit') {
      return value;
    }
    return getType(property).toCssValue(value, svgMode);
  };

  var fromCssValue = function (property, value) {
    if (value === cssNeutralValue) {
      return rawNeutralValue;
    }
    if (value === 'inherit') {
      return value;
    }
    if (property in propertyValueAliases &&
      value in propertyValueAliases[property]) {
      value = propertyValueAliases[property][value];
    }
    var result = getType(property).fromCssValue(value);
    // Currently we'll hit this assert if input to the API is bad. To avoid this,
    // we should eliminate invalid values when normalizing the list of keyframes.
    // See the TODO in isSupportedPropertyValue().
    ASSERT_ENABLED && assert(isDefinedAndNotNull(result),
      'Invalid property value "' + value + '" for property "' + property + '"');
    return result;
  };

  // Sentinel values
  var cssNeutralValue = {};
  var rawNeutralValue = {};



  /** @constructor */
  var CompositableValue = function () {
  };

  CompositableValue.prototype = {
    compositeOnto: abstractMethod,
    // This is purely an optimization.
    dependsOnUnderlyingValue: function () {
      return true;
    }
  };



  /** @constructor */
  var AddReplaceCompositableValue = function (value, composite) {
    this.value = value;
    this.composite = composite;
    ASSERT_ENABLED && assert(
      !(this.value === cssNeutralValue && this.composite === 'replace'),
      'Should never replace-composite the neutral value');
  };

  AddReplaceCompositableValue.prototype = createObject(
    CompositableValue.prototype, {
    compositeOnto: function (property, underlyingValue) {
      switch (this.composite) {
        case 'replace':
          return this.value;
        case 'add':
          return add(property, underlyingValue, this.value);
        default:
          ASSERT_ENABLED && assert(
            false, 'Invalid composite operation ' + this.composite);
      }
    },
    dependsOnUnderlyingValue: function () {
      return this.composite === 'add';
    }
  });



  /** @constructor */
  var BlendedCompositableValue = function (startValue, endValue, fraction) {
    this.startValue = startValue;
    this.endValue = endValue;
    this.fraction = fraction;
  };

  BlendedCompositableValue.prototype = createObject(
    CompositableValue.prototype, {
    compositeOnto: function (property, underlyingValue) {
      return interpolate(property,
        this.startValue.compositeOnto(property, underlyingValue),
        this.endValue.compositeOnto(property, underlyingValue),
        this.fraction);
    },
    dependsOnUnderlyingValue: function () {
      // Travis crashes here randomly in Chrome beta and unstable,
      // this try catch is to help debug the problem.
      try {
        return this.startValue.dependsOnUnderlyingValue() ||
          this.endValue.dependsOnUnderlyingValue();
      }
      catch (error) {
        throw new Error(
          error + '\n JSON.stringify(this) = ' + JSON.stringify(this));
      }
    }
  });



  /** @constructor */
  var AccumulatedCompositableValue = function (
    bottomValue, accumulatingValue, accumulationCount) {
    this.bottomValue = bottomValue;
    this.accumulatingValue = accumulatingValue;
    this.accumulationCount = accumulationCount;
    ASSERT_ENABLED && assert(this.accumulationCount > 0,
      'Accumumlation count should be strictly positive');
  };

  AccumulatedCompositableValue.prototype = createObject(
    CompositableValue.prototype, {
    compositeOnto: function (property, underlyingValue) {
      // The spec defines accumulation recursively, but we do it iteratively
      // to better handle large numbers of iterations.
      var result = this.bottomValue.compositeOnto(property, underlyingValue);
      for (var i = 0; i < this.accumulationCount; i++) {
        result = this.accumulatingValue.compositeOnto(property, result);
      }
      return result;
    },
    dependsOnUnderlyingValue: function () {
      return this.bottomValue.dependsOnUnderlyingValue() &&
        this.accumulatingValue.dependsOnUnderlyingValue();
    }
  });



  /** @constructor */
  var CompositedPropertyMap = function (target) {
    this.properties = {};
    this.baseValues = {};
    this.target = target;
  };

  CompositedPropertyMap.prototype = {
    addValue: function (property, animValue) {
      if (!(property in this.properties)) {
        this.properties[property] = [];
      }
      if (!(animValue instanceof CompositableValue)) {
        throw new TypeError('expected CompositableValue');
      }
      this.properties[property].push(animValue);
    },
    stackDependsOnUnderlyingValue: function (stack) {
      for (var i = 0; i < stack.length; i++) {
        if (!stack[i].dependsOnUnderlyingValue()) {
          return false;
        }
      }
      return true;
    },
    clear: function () {
      for (var property in this.properties) {
        if (this.stackDependsOnUnderlyingValue(this.properties[property])) {
          clearValue(this.target, property);
        }
      }
    },
    captureBaseValues: function () {
      for (var property in this.properties) {
        if (this.stackDependsOnUnderlyingValue(this.properties[property])) {
          var baseValue = fromCssValue(property, getValue(this.target, property));
          // TODO: Decide what to do with elements not in the DOM.
          ASSERT_ENABLED && assert(
            isDefinedAndNotNull(baseValue) && baseValue !== '',
            'Base value should always be set. ' +
            'Is the target element in the DOM?');
          this.baseValues[property] = baseValue;
        } else {
          this.baseValues[property] = undefined;
        }
      }
    },
    applyAnimatedValues: function () {
      for (var property in this.properties) {
        var valuesToComposite = this.properties[property];
        if (valuesToComposite.length === 0) {
          continue;
        }
        var baseValue = this.baseValues[property];
        var i = valuesToComposite.length - 1;
        while (i > 0 && valuesToComposite[i].dependsOnUnderlyingValue()) {
          i--;
        }
        for (; i < valuesToComposite.length; i++) {
          baseValue = valuesToComposite[i].compositeOnto(property, baseValue);
        }
        ASSERT_ENABLED && assert(
          isDefinedAndNotNull(baseValue) && baseValue !== '',
          'Value should always be set after compositing');
        var isSvgMode = propertyIsSVGAttrib(property, this.target);
        setValue(this.target, property, toCssValue(property, baseValue,
          isSvgMode));
        this.properties[property] = [];
      }
    }
  };

  var cssStyleDeclarationAttribute = {
    cssText: true,
    length: true,
    parentRule: true,
    'var': true
  };

  var cssStyleDeclarationMethod = {
    getPropertyValue: true,
    getPropertyCSSValue: true,
    removeProperty: true,
    getPropertyPriority: true,
    setProperty: true,
    item: true
  };



  /** @constructor */
  var AnimatedCSSStyleDeclaration = function (element) {
    ASSERT_ENABLED && assert(
      !(element.style instanceof AnimatedCSSStyleDeclaration),
      'Element must not already have an animated style attached.');

    // Stores the inline style of the element on its behalf while the
    // polyfill uses the element's inline style to simulate web animations.
    // This is needed to fake regular inline style CSSOM access on the element.
    this._surrogateElement = document.createElement('div');
    this._style = element.style;
    this._length = 0;
    this._isAnimatedProperty = {};

    // Populate the surrogate element's inline style.
    for (var i = 0; i < this._style.length; i++) {
      var property = this._style[i];
      this._surrogateElement.style[property] = this._style[property];
    }
    this._updateIndices();
  };

  AnimatedCSSStyleDeclaration.prototype = {
    get cssText () {
      return this._surrogateElement.style.cssText;
    },
    set cssText (text) {
      var isAffectedProperty = {};
      for (var i = 0; i < this._surrogateElement.style.length; i++) {
        isAffectedProperty[this._surrogateElement.style[i]] = true;
      }
      this._surrogateElement.style.cssText = text;
      this._updateIndices();
      for (var i = 0; i < this._surrogateElement.style.length; i++) {
        isAffectedProperty[this._surrogateElement.style[i]] = true;
      }
      for (var property in isAffectedProperty) {
        if (!this._isAnimatedProperty[property]) {
          this._style.setProperty(property,
            this._surrogateElement.style.getPropertyValue(property));
        }
      }
      this._inlineStyleChanged();
    },
    get length () {
      return this._surrogateElement.style.length;
    },
    get parentRule () {
      return this._style.parentRule;
    },
    get 'var' () {
      return this._style.var;
    },
    _updateIndices: function () {
      while (this._length < this._surrogateElement.style.length) {
        Object.defineProperty(this, this._length, {
          configurable: true,
          enumerable: false,
          get: (function (index) {
            return function () {
              return this._surrogateElement.style[index];
            };
          })(this._length)
        });
        this._length++;
      }
      while (this._length > this._surrogateElement.style.length) {
        this._length--;
        Object.defineProperty(this, this._length, {
          configurable: true,
          enumerable: false,
          value: undefined
        });
      }
    },
    _clearAnimatedProperty: function (property) {
      this._style[property] = this._surrogateElement.style[property];
      this._isAnimatedProperty[property] = false;
    },
    _setAnimatedProperty: function (property, value) {
      this._style[property] = value;
      this._isAnimatedProperty[property] = true;
    },
    _inlineStyleChanged: function () {
      maybeRestartAnimation();
      // Changing the inline style of an element under animation may require the
      // animation to be recomputed ontop of the new inline style if
      // getComputedStyle() is called inbetween setting the style and the next
      // animation frame.
      // We modify getComputedStyle() to re-evaluate the animations only if it is
      // called instead of re-evaluating them here potentially unnecessarily.
      ensureRetickBeforeGetComputedStyle();
    }
  };

  for (var method in cssStyleDeclarationMethod) {
    AnimatedCSSStyleDeclaration.prototype[method] = (function (method) {
      return function () {
        return this._surrogateElement.style[method].apply(
          this._surrogateElement.style, arguments);
      }
    })(method);
  }

  for (var property in document.documentElement.style) {
    if (cssStyleDeclarationAttribute[property] ||
      cssStyleDeclarationMethod[property]) {
      continue;
    }
    (function (property) {
      Object.defineProperty(AnimatedCSSStyleDeclaration.prototype, property,
        configureDescriptor({
          get: function () {
            return this._surrogateElement.style[property];
          },
          set: function (value) {
            this._surrogateElement.style[property] = value;
            this._updateIndices();
            if (!this._isAnimatedProperty[property]) {
              this._style[property] = value;
            }
            this._inlineStyleChanged();
          }
        }));
    })(property);
  }

  var retickThenGetComputedStyle = function () {
    repeatLastTick();
    // ticker() will restore getComputedStyle() back to normal.
    return window.getComputedStyle.apply(this, arguments);
  };

  var originalGetComputedStyle = window.getComputedStyle;

  var ensureRetickBeforeGetComputedStyle = function () {
    if (window.getComputedStyle !== retickThenGetComputedStyle) {
      Object.defineProperty(window, 'getComputedStyle', configureDescriptor({
        value: retickThenGetComputedStyle
      }));
    }
  };

  var ensureOriginalGetComputedStyle = function () {
    if (window.getComputedStyle === retickThenGetComputedStyle) {
      Object.defineProperty(window, 'getComputedStyle', configureDescriptor({
        value: originalGetComputedStyle
      }));
    }
  };



  /** @constructor */
  var Compositor = function () {
    this.targets = [];
  };

  Compositor.prototype = {
    setAnimatedValue: function (target, property, animValue) {
      if (target !== null) {
        if (target._animProperties === undefined) {
          target._animProperties = new CompositedPropertyMap(target);
          this.targets.push(target);
        }
        target._animProperties.addValue(property, animValue);
      }
    },
    applyAnimatedValues: function () {
      for (var i = 0; i < this.targets.length; i++) {
        this.targets[i]._animProperties.clear();
      }
      for (var i = 0; i < this.targets.length; i++) {
        this.targets[i]._animProperties.captureBaseValues();
      }
      for (var i = 0; i < this.targets.length; i++) {
        this.targets[i]._animProperties.applyAnimatedValues();
      }
    }
  };

  var ensureTargetInitialised = function (property, target) {
    if (propertyIsSVGAttrib(property, target)) {
      if (!isDefinedAndNotNull(target._actuals)) {
        target._actuals = {};
        target._bases = {};
        target.actuals = {};
        target._getAttribute = target.getAttribute;
        target._setAttribute = target.setAttribute;
        target.getAttribute = function (name) {
          if (isDefinedAndNotNull(target._bases[name])) {
            return target._bases[name];
          }
          return target._getAttribute(name);
        };
        target.setAttribute = function (name, value) {
          if (isDefinedAndNotNull(target._actuals[name])) {
            target._bases[name] = value;
          } else {
            target._setAttribute(name, value);
          }
        };
      }
      if (!isDefinedAndNotNull(target._actuals[property])) {
        var baseVal = target.getAttribute(property);
        target._actuals[property] = 0;
        target._bases[property] = baseVal;

        Object.defineProperty(target.actuals, property, configureDescriptor({
          set: function (value) {
            if (value === null) {
              target._actuals[property] = target._bases[property];
              target._setAttribute(property, target._bases[property]);
            } else {
              target._actuals[property] = value;
              target._setAttribute(property, value);
            }
          },
          get: function () {
            return target._actuals[property];
          }
        }));
      }
    } else {
      if (target.style instanceof AnimatedCSSStyleDeclaration) {
        return;
      }
      var animatedStyle = new AnimatedCSSStyleDeclaration(target);
      Object.defineProperty(target, 'style', configureDescriptor({
        get: function () { return animatedStyle; }
      }));
    }
  };

  var setValue = function (target, property, value) {
    ensureTargetInitialised(property, target);
    if (property === 'transform') {
      property = features.transformProperty;
    }
    if (propertyIsSVGAttrib(property, target)) {
      /*
          if (property === 'd') {
            console.log('Setting \'d\': points=', value.points);
            target.pathSegList.clear();
            target.pathSegList.appendItem(target.createSVGPathSegMovetoAbs(
                value.points[0].x,
                value.points[0].y));
            for (var i = 1; i < startKeyframe.points.length; ++i)
              target.pathSegList.appendItem(target.createSVGPathSegLinetoAbs(
                  value.points[i].x,
                  value.points[i].y));
          } else
      */
      target.actuals[property] = value;
    } else {
      target.style._setAnimatedProperty(property, value);
    }
  };

  var clearValue = function (target, property) {
    ensureTargetInitialised(property, target);
    if (property === 'transform') {
      property = features.transformProperty;
    }
    if (propertyIsSVGAttrib(property, target)) {
      target.actuals[property] = null;
    } else {
      target.style._clearAnimatedProperty(property);
    }
  };

  var getValue = function (target, property) {
    ensureTargetInitialised(property, target);
    if (property === 'transform') {
      property = features.transformProperty;
    }
    if (propertyIsSVGAttrib(property, target)) {
      return target.actuals[property];
    } else {
      return getComputedStyle(target)[property];
    }
  };

  var rafScheduled = false;

  var compositor = new Compositor();

  var usePerformanceTiming =
    typeof window.performance === 'object' &&
    typeof window.performance.timing === 'object' &&
    typeof window.performance.now === 'function';

  // Don't use a local named requestAnimationFrame, to avoid potential problems
  // with hoisting.
  var raf = window.requestAnimationFrame;
  if (!raf) {
    var nativeRaf = window.webkitRequestAnimationFrame ||
      window.mozRequestAnimationFrame;
    if (!nativeRaf) {
      // requestAnimationFrame is not available, simulate it.
      raf = function (callback) {
        setTimeout(function () {
          callback(clockMillis());
        }, 1000 / 60);
      };
    } else if (usePerformanceTiming) {
      // platform requestAnimationFrame provides only millisecond accuracy, wrap
      // it and use performance.now()
      raf = function (callback) {
        nativeRaf(function () {
          callback(window.performance.now());
        });
      };
    } else {
      // platform requestAnimationFrame provides only millisecond accuracy, and
      // we can't do any better
      raf = nativeRaf;
    }
  }

  var clockMillis = function () {
    return usePerformanceTiming ? window.performance.now() : Date.now();
  };
  // Set up the zero times for document time. Document time is relative to the
  // document load event.
  var documentTimeZeroAsRafTime;
  var documentTimeZeroAsClockTime;
  var load;
  if (usePerformanceTiming) {
    load = function () {
      // RAF time is relative to the navigationStart event.
      documentTimeZeroAsRafTime =
        window.performance.timing.loadEventStart -
        window.performance.timing.navigationStart;
      // performance.now() uses the same origin as RAF time.
      documentTimeZeroAsClockTime = documentTimeZeroAsRafTime;
    };
  } else {
    // The best approximation we have for the relevant clock and RAF times is to
    // listen to the load event.
    load = function () {
      raf(function (rafTime) {
        documentTimeZeroAsRafTime = rafTime;
      });
      documentTimeZeroAsClockTime = Date.now();
    };
  }
  // Start timing when load event fires or if this script is processed when
  // document loading is already complete.
  if (document.readyState === 'complete') {
    // When performance timing is unavailable and this script is loaded
    // dynamically, document zero time is incorrect.
    // Warn the user in this case.
    if (!usePerformanceTiming) {
      console.warn(
        'Web animations can\'t discover document zero time when ' +
        'asynchronously loaded in the absence of performance timing.');
    }
    load();
  } else {
    addEventListener('load', function () {
      load();
      if (usePerformanceTiming) {
        // We use setTimeout() to clear cachedClockTimeMillis at the end of a
        // frame, but this will not run until after other load handlers. We need
        // those handlers to pick up the new value of clockMillis(), so we must
        // clear the cached value.
        cachedClockTimeMillis = undefined;
      }
    });
  }

  // A cached document time for use during the current callstack.
  var cachedClockTimeMillis;
  // Calculates one time relative to another, returning null if the zero time is
  // undefined.
  var relativeTime = function (time, zeroTime) {
    return isDefined(zeroTime) ? time - zeroTime : null;
  };

  var lastClockTimeMillis;

  var cachedClockTime = function () {
    // Cache a document time for the remainder of this callstack.
    if (!isDefined(cachedClockTimeMillis)) {
      cachedClockTimeMillis = clockMillis();
      lastClockTimeMillis = cachedClockTimeMillis;
      setTimeout(function () { cachedClockTimeMillis = undefined; }, 0);
    }
    return cachedClockTimeMillis / 1000;
  };


  // These functions should be called in every stack that could possibly modify
  // the effect results that have already been calculated for the current tick.
  var modifyCurrentAnimationStateDepth = 0;
  var enterModifyCurrentAnimationState = function () {
    modifyCurrentAnimationStateDepth++;
  };
  var exitModifyCurrentAnimationState = function (shouldRepeat) {
    modifyCurrentAnimationStateDepth--;
    // shouldRepeat is set false when we know we can't possibly affect the current
    // state (eg. a TimedItem which is not attached to a player). We track the
    // depth of recursive calls trigger just one repeat per entry. Only the value
    // of shouldRepeat from the outermost call is considered, this allows certain
    // locatations (eg. constructors) to override nested calls that would
    // otherwise set shouldRepeat unconditionally.
    if (modifyCurrentAnimationStateDepth === 0 && shouldRepeat) {
      repeatLastTick();
    }
  };

  var repeatLastTick = function () {
    if (isDefined(lastTickTime)) {
      ticker(lastTickTime, true);
    }
  };

  var playerSortFunction = function (a, b) {
    var result = a.startTime - b.startTime;
    return result !== 0 ? result : a._sequenceNumber - b.sequenceNumber;
  };

  var lastTickTime;
  var ticker = function (rafTime, isRepeat) {
    // Don't tick till the page is loaded....
    if (!isDefined(documentTimeZeroAsRafTime)) {
      raf(ticker);
      return;
    }

    if (!isRepeat) {
      if (rafTime < lastClockTimeMillis) {
        rafTime = lastClockTimeMillis;
      }
      lastTickTime = rafTime;
      cachedClockTimeMillis = rafTime;
    }

    // Clear any modifications to getComputedStyle.
    ensureOriginalGetComputedStyle();

    // Get animations for this sample. We order by Player then by DFS order within
    // each Player's tree.
    if (!playersAreSorted) {
      PLAYERS.sort(playerSortFunction);
      playersAreSorted = true;
    }
    var finished = true;
    var paused = true;
    var animations = [];
    var finishedPlayers = [];
    PLAYERS.forEach(function (player) {
      player._hasTicked = true;
      player._update();
      finished = finished && player._isPastEndOfActiveInterval();
      if (!player._hasFutureEffect()) {
        finishedPlayers.push(player);
      }
      paused = paused && player.paused;
      player._getLeafItemsInEffect(animations);
    });

    // Apply animations in order
    for (var i = 0; i < animations.length; i++) {
      if (animations[i] instanceof Animation) {
        animations[i]._sample();
      }
    }

    // Generate events
    PLAYERS.forEach(function (player) {
      player._generateEvents();
    });

    // Remove finished players. Warning: _deregisterFromTimeline modifies
    // the PLAYER list. It should not be called from within a PLAYERS.forEach
    // loop directly.
    finishedPlayers.forEach(function (player) {
      player._deregisterFromTimeline();
      playersAreSorted = false;
    });

    // Composite animated values into element styles
    compositor.applyAnimatedValues();

    if (!isRepeat) {
      if (finished || paused) {
        rafScheduled = false;
      } else {
        raf(ticker);
      }
      cachedClockTimeMillis = undefined;
    }
  };

  // Multiplication where zero multiplied by any value (including infinity)
  // gives zero.
  var multiplyZeroGivesZero = function (a, b) {
    return (a === 0 || b === 0) ? 0 : a * b;
  };

  var maybeRestartAnimation = function () {
    if (rafScheduled) {
      return;
    }
    raf(ticker);
    rafScheduled = true;
  };

  var DOCUMENT_TIMELINE = new Timeline(constructorToken);
  document.timeline = DOCUMENT_TIMELINE;

  window.Element.prototype.animate = function (effect, timing) {
    var anim = new Animation(this, effect, timing);
    DOCUMENT_TIMELINE.play(anim);
    return anim;
  };
  window.Element.prototype.getCurrentPlayers = function () {
    return PLAYERS.filter((function (player) {
      return player._isCurrent() && player._isTargetingElement(this);
    }).bind(this));
  };
  window.Element.prototype.getCurrentAnimations = function () {
    var animations = [];
    PLAYERS.forEach((function (player) {
      if (player._isCurrent()) {
        player._getAnimationsTargetingElement(this, animations);
      }
    }).bind(this));
    return animations;
  };

  window.Animation = Animation;
  window.AnimationEffect = AnimationEffect;
  window.KeyframeAnimationEffect = KeyframeAnimationEffect;
  window.MediaReference = MediaReference;
  window.ParGroup = ParGroup;
  window.PathAnimationEffect = PathAnimationEffect;
  window.Player = Player;
  window.PseudoElementReference = PseudoElementReference;
  window.SeqGroup = SeqGroup;
  window.TimedItem = TimedItem;
  window.TimedItemList = TimedItemList;
  window.Timing = Timing;
  window.Timeline = Timeline;
  window.TimingEvent = TimingEvent;
  window.TimingGroup = TimingGroup;

  window._WebAnimationsTestingUtilities = {
    _constructorToken: constructorToken,
    _positionListType: positionListType,
    _hsl2rgb: hsl2rgb,
    _types: propertyTypes,
    _knownPlayers: PLAYERS,
    _createNormalizedChain: TimingFunction.createNormalizedChain,
    _cubicBezierTimingFunction: CubicBezierTimingFunction,
    _linearTimingFunction: LinearTimingFunction,
    _pacedTimingFunction: PacedTimingFunction,
    _enableAsserts: function () { ASSERT_ENABLED = true; }
  };

})();