Bug 474743 Patch B: Implement milestone sampling behavior. r=dholbert sr=roc
authorBrian Birtles <birtles@gmail.com>
Tue, 12 Jan 2010 12:00:49 -0800
changeset 37113 6955702f91acfc6e107c54bf6a8ba60137b59b04
parent 37112 567a4da0a3fc7af7e894f5459f3540181735ad87
child 37114 192adf25beb32a246763995268fc65186ef02e2d
push idunknown
push userunknown
push dateunknown
reviewersdholbert, roc
bugs474743
milestone1.9.3a1pre
Bug 474743 Patch B: Implement milestone sampling behavior. r=dholbert sr=roc
content/smil/Makefile.in
content/smil/nsSMILAnimationController.cpp
content/smil/nsSMILAnimationController.h
content/smil/nsSMILAnimationFunction.cpp
content/smil/nsSMILMilestone.h
content/smil/nsSMILTimeContainer.cpp
content/smil/nsSMILTimeContainer.h
content/smil/nsSMILTimeValue.cpp
content/smil/nsSMILTimeValue.h
content/smil/nsSMILTimedElement.cpp
content/smil/nsSMILTimedElement.h
content/svg/content/src/nsSVGAnimationElement.cpp
content/svg/content/src/nsSVGSVGElement.cpp
content/svg/content/src/nsSVGSVGElement.h
--- a/content/smil/Makefile.in
+++ b/content/smil/Makefile.in
@@ -84,16 +84,17 @@ TOOL_DIRS		+= test
 endif # ENABLE_TESTS
 
 EXPORTS		+= \
 	  nsISMILAnimationElement.h \
 	  nsISMILAttr.h \
 	  nsSMILAnimationController.h \
 	  nsSMILCompositorTable.h \
 	  nsSMILKeySpline.h \
+	  nsSMILMilestone.h \
 	  nsSMILTimeContainer.h \
 	  nsSMILTypes.h \
 	  $(NULL)
 
 INCLUDES += 	\
 		-I$(srcdir)/../base/src \
 		-I$(srcdir)/../../layout/style \
 		$(NULL)
--- a/content/smil/nsSMILAnimationController.cpp
+++ b/content/smil/nsSMILAnimationController.cpp
@@ -161,25 +161,16 @@ nsSMILAnimationController::RegisterAnima
 void
 nsSMILAnimationController::UnregisterAnimationElement(
                                   nsISMILAnimationElement* aAnimationElement)
 {
   mAnimationElementTable.RemoveEntry(aAnimationElement);
 }
 
 //----------------------------------------------------------------------
-// Resampling methods
-
-void
-nsSMILAnimationController::Resample()
-{
-  DoSample(PR_FALSE);
-}
-
-//----------------------------------------------------------------------
 // Page show/hide
 
 void
 nsSMILAnimationController::OnPageShow()
 {
   Resume(nsSMILTimeContainer::PAUSE_PAGEHIDE);
 }
 
@@ -291,34 +282,36 @@ DoComposeAttribute(nsSMILCompositor* aCo
 }
 
 void
 nsSMILAnimationController::DoSample()
 {
   DoSample(PR_TRUE); // Skip unchanged time containers
 }
 
-
 void
 nsSMILAnimationController::DoSample(PRBool aSkipUnchangedContainers)
 {
   // Reset resample flag
   mResampleNeeded = PR_FALSE;
 
-  // STEP 1: Sample the child time containers
+  // STEP 1: Bring model up to date
+  DoMilestoneSamples();
+
+  // STEP 2: Sample the child time containers
   //
   // When we sample the child time containers they will simply record the sample
   // time in document time.
   TimeContainerHashtable activeContainers;
   activeContainers.Init(mChildContainerTable.Count());
   SampleTimeContainerParams tcParams = { &activeContainers,
                                          aSkipUnchangedContainers };
   mChildContainerTable.EnumerateEntries(SampleTimeContainer, &tcParams);
 
-  // STEP 2: (i)  Sample the timed elements AND
+  // STEP 3: (i)  Sample the timed elements AND
   //         (ii) Create a table of compositors
   //
   // (i) Here we sample the timed elements (fetched from the
   // nsISMILAnimationElements) which determine from the active time if the
   // element is active and what its simple time etc. is. This information is
   // then passed to its time client (nsSMILAnimationFunction).
   //
   // (ii) During the same loop we also build up a table that contains one
@@ -344,55 +337,181 @@ nsSMILAnimationController::DoSample(PRBo
                                      currentCompositorTable };
   nsresult rv = mAnimationElementTable.EnumerateEntries(SampleAnimation,
                                                         &saParams);
   if (NS_FAILED(rv)) {
     NS_WARNING("SampleAnimationParams failed");
   }
   activeContainers.Clear();
 
-  // STEP 3: Remove animation effects from any no-longer-animated elems/attrs
+  // STEP 4: Remove animation effects from any no-longer-animated elems/attrs
   if (mLastCompositorTable) {
     // * For each compositor in current sample's hash table, remove entry from
     // prev sample's hash table -- we don't need to clear animation
     // effects of those compositors, since they're still being animated.
     currentCompositorTable->EnumerateEntries(RemoveCompositorFromTable,
                                              mLastCompositorTable);
 
     // * For each entry that remains in prev sample's hash table (i.e. for
     // every target that's no longer animated), clear animation effects.
     mLastCompositorTable->EnumerateEntries(DoClearAnimationEffects, nsnull);
   }
 
-  // STEP 4: Compose currently-animated attributes.
+  // STEP 5: Compose currently-animated attributes.
   // XXXdholbert: This step traverses our animation targets in an effectively
   // random order. For animation from/to 'inherit' values to work correctly
   // when the inherited value is *also* being animated, we really should be
   // traversing our animated nodes in an ancestors-first order (bug 501183)
   currentCompositorTable->EnumerateEntries(DoComposeAttribute, nsnull);
 
   // Update last compositor table
   mLastCompositorTable = currentCompositorTable.forget();
 
   NS_ASSERTION(!mResampleNeeded, "Resample dirty flag set during sample!");
 }
 
+void
+nsSMILAnimationController::DoMilestoneSamples()
+{
+  // We need to sample the timing model but because SMIL operates independently
+  // of the frame-rate, we can get one sample at t=0s and the next at t=10min.
+  //
+  // In between those two sample times a whole string of significant events
+  // might be expected to take place: events firing, new interdependencies
+  // between animations resolved and dissolved, etc.
+  //
+  // Furthermore, at any given time, we want to sample all the intervals that
+  // end at that time BEFORE any that begin. This behaviour is implied by SMIL's
+  // endpoint-exclusive timing model.
+  //
+  // So we have the animations (specifically the timed elements) register the
+  // next significant moment (called a milestone) in their lifetime and then we
+  // step through the model at each of these moments and sample those animations
+  // registered for those times. This way events can fire in the correct order,
+  // dependencies can be resolved etc.
+
+  nsSMILTime sampleTime = LL_MININT;
+
+  while (PR_TRUE) {
+    // We want to find any milestones AT OR BEFORE the current sample time so we
+    // initialise the next milestone to the moment after (1ms after, to be
+    // precise) the current sample time and see if there are any milestones
+    // before that. Any other milestones will be dealt with in a subsequent
+    // sample.
+    nsSMILMilestone nextMilestone(GetCurrentTime() + 1, PR_TRUE);
+    mChildContainerTable.EnumerateEntries(GetNextMilestone, &nextMilestone);
+
+    if (nextMilestone.mTime > GetCurrentTime()) {
+      break;
+    }
+
+    GetMilestoneElementsParams params;
+    params.mMilestone = nextMilestone;
+    mChildContainerTable.EnumerateEntries(GetMilestoneElements, &params);
+    PRUint32 length = params.mElements.Length();
+
+    // During the course of a sampling we don't want to actually go backwards.
+    // Due to negative offsets, early ends and the like, a timed element might
+    // register a milestone that is actually in the past. That's fine, but it's
+    // still only going to get *sampled* with whatever time we're up to and no
+    // earlier.
+    //
+    // Because we're only performing this clamping at the last moment, the
+    // animations will still all get sampled in the correct order and
+    // dependencies will be appropriately resolved.
+    sampleTime = PR_MAX(nextMilestone.mTime, sampleTime);
+
+    for (PRUint32 i = 0; i < length; ++i) {
+      nsISMILAnimationElement* elem = params.mElements[i].get();
+      NS_ABORT_IF_FALSE(elem, "NULL animation element in list");
+      nsSMILTimeContainer* container = elem->GetTimeContainer();
+      if (!container)
+        // The container may be nsnull if the element has been detached from its
+        // parent since registering a milestone.
+        continue;
+
+      nsSMILTimeValue containerTimeValue =
+        container->ParentToContainerTime(sampleTime);
+      if (!containerTimeValue.IsResolved())
+        continue;
+
+      // Clamp the converted container time to non-negative values.
+      nsSMILTime containerTime = PR_MAX(0, containerTimeValue.GetMillis());
+
+      if (nextMilestone.mIsEnd) {
+        elem->TimedElement().SampleEndAt(containerTime);
+      } else {
+        elem->TimedElement().SampleAt(containerTime);
+      }
+    }
+  }
+}
+
+/*static*/ PR_CALLBACK PLDHashOperator
+nsSMILAnimationController::GetNextMilestone(TimeContainerPtrKey* aKey,
+                                            void* aData)
+{
+  NS_ABORT_IF_FALSE(aKey, "Null hash key for time container hash table");
+  NS_ABORT_IF_FALSE(aKey->GetKey(), "Null time container key in hash table");
+  NS_ABORT_IF_FALSE(aData,
+      "Null data pointer during time container enumeration");
+
+  nsSMILMilestone* nextMilestone = static_cast<nsSMILMilestone*>(aData);
+
+  nsSMILTimeContainer* container = aKey->GetKey();
+  if (container->IsPausedByType(nsSMILTimeContainer::PAUSE_BEGIN))
+    return PL_DHASH_NEXT;
+
+  nsSMILMilestone thisMilestone;
+  PRBool didGetMilestone =
+    container->GetNextMilestoneInParentTime(thisMilestone);
+  if (didGetMilestone && thisMilestone < *nextMilestone) {
+    *nextMilestone = thisMilestone;
+  }
+
+  return PL_DHASH_NEXT;
+}
+
+/*static*/ PR_CALLBACK PLDHashOperator
+nsSMILAnimationController::GetMilestoneElements(TimeContainerPtrKey* aKey,
+                                                void* aData)
+{
+  NS_ABORT_IF_FALSE(aKey, "Null hash key for time container hash table");
+  NS_ABORT_IF_FALSE(aKey->GetKey(), "Null time container key in hash table");
+  NS_ABORT_IF_FALSE(aData,
+      "Null data pointer during time container enumeration");
+
+  GetMilestoneElementsParams* params =
+    static_cast<GetMilestoneElementsParams*>(aData);
+
+  nsSMILTimeContainer* container = aKey->GetKey();
+  if (container->IsPausedByType(nsSMILTimeContainer::PAUSE_BEGIN))
+    return PL_DHASH_NEXT;
+
+  container->PopMilestoneElementsAtMilestone(params->mMilestone,
+                                             params->mElements);
+
+  return PL_DHASH_NEXT;
+}
+
 /*static*/ PR_CALLBACK PLDHashOperator
 nsSMILAnimationController::SampleTimeContainer(TimeContainerPtrKey* aKey,
                                                void* aData)
 {
   NS_ENSURE_TRUE(aKey, PL_DHASH_NEXT);
   NS_ENSURE_TRUE(aKey->GetKey(), PL_DHASH_NEXT);
   NS_ENSURE_TRUE(aData, PL_DHASH_NEXT);
 
   SampleTimeContainerParams* params =
     static_cast<SampleTimeContainerParams*>(aData);
 
   nsSMILTimeContainer* container = aKey->GetKey();
-  if (container->NeedsSample() || !params->mSkipUnchangedContainers) {
+  if (!container->IsPausedByType(nsSMILTimeContainer::PAUSE_BEGIN) &&
+      (container->NeedsSample() || !params->mSkipUnchangedContainers)) {
+    container->ClearMilestones();
     container->Sample();
     params->mActiveContainers->PutEntry(container);
   }
 
   return PL_DHASH_NEXT;
 }
 
 /*static*/ PR_CALLBACK PLDHashOperator
--- a/content/smil/nsSMILAnimationController.h
+++ b/content/smil/nsSMILAnimationController.h
@@ -42,16 +42,17 @@
 #include "nsAutoPtr.h"
 #include "nsCOMPtr.h"
 #include "nsTArray.h"
 #include "nsITimer.h"
 #include "nsTHashtable.h"
 #include "nsHashKeys.h"
 #include "nsSMILTimeContainer.h"
 #include "nsSMILCompositorTable.h"
+#include "nsSMILMilestone.h"
 
 class nsISMILAnimationElement;
 class nsIDocument;
 
 //----------------------------------------------------------------------
 // nsSMILAnimationController
 //
 // The animation controller maintains the animation timer and determines the
@@ -77,24 +78,24 @@ public:
 
   // Methods for registering and enumerating animation elements
   void RegisterAnimationElement(nsISMILAnimationElement* aAnimationElement);
   void UnregisterAnimationElement(nsISMILAnimationElement* aAnimationElement);
 
   // Methods for resampling all animations
   // (A resample performs the same operations as a sample but doesn't advance
   // the current time and doesn't check if the container is paused)
-  void Resample();
+  void Resample() { DoSample(PR_FALSE); }
   void SetResampleNeeded() { mResampleNeeded = PR_TRUE; }
   void FlushResampleRequests()
   {
     if (!mResampleNeeded)
       return;
 
-    DoSample(PR_FALSE); // Don't skip unchanged time containers--sample them all
+    Resample();
   }
 
   // Methods for handling page transitions
   void OnPageShow();
   void OnPageHide();
 
   // Methods for supporting cycle-collection
   void Traverse(nsCycleCollectionTraversalCallback* aCallback);
@@ -114,16 +115,22 @@ protected:
   };
 
   struct SampleAnimationParams
   {
     TimeContainerHashtable* mActiveContainers;
     nsSMILCompositorTable*  mCompositorTable;
   };
 
+  struct GetMilestoneElementsParams
+  {
+    nsTArray<nsRefPtr<nsISMILAnimationElement> > mElements;
+    nsSMILMilestone                              mMilestone;
+  };
+
   // Factory methods
   friend nsSMILAnimationController*
   NS_NewSMILAnimationController(nsIDocument* aDoc);
   nsresult    Init(nsIDocument* aDoc);
 
   // Cycle-collection implementation helpers
   PR_STATIC_CALLBACK(PLDHashOperator) CompositorTableEntryTraverse(
       nsSMILCompositor* aCompositor, void* aArg);
@@ -131,22 +138,25 @@ protected:
   // Timer-related implementation helpers
   static void Notify(nsITimer* aTimer, void* aClosure);
   nsresult    StartTimer();
   nsresult    StopTimer();
 
   // Sample-related callbacks and implementation helpers
   virtual void DoSample();
   void DoSample(PRBool aSkipUnchangedContainers);
+  void DoMilestoneSamples();
+  PR_STATIC_CALLBACK(PLDHashOperator) GetNextMilestone(
+      TimeContainerPtrKey* aKey, void* aData);
+  PR_STATIC_CALLBACK(PLDHashOperator) GetMilestoneElements(
+      TimeContainerPtrKey* aKey, void* aData);
   PR_STATIC_CALLBACK(PLDHashOperator) SampleTimeContainer(
       TimeContainerPtrKey* aKey, void* aData);
   PR_STATIC_CALLBACK(PLDHashOperator) SampleAnimation(
       AnimationElementPtrKey* aKey, void* aData);
-  PR_STATIC_CALLBACK(PLDHashOperator) AddAnimationToCompositorTable(
-      AnimationElementPtrKey* aKey, void* aData);
   static void SampleTimedElement(nsISMILAnimationElement* aElement,
                                  TimeContainerHashtable* aActiveContainers);
   static void AddAnimationToCompositorTable(
     nsISMILAnimationElement* aElement, nsSMILCompositorTable* aCompositorTable);
   static PRBool GetCompositorKeyForAnimation(nsISMILAnimationElement* aAnimElem,
                                              nsSMILCompositorKey& aResult);
 
   // Methods for adding/removing time containers
--- a/content/smil/nsSMILAnimationFunction.cpp
+++ b/content/smil/nsSMILAnimationFunction.cpp
@@ -37,16 +37,17 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "nsSMILAnimationFunction.h"
 #include "nsISMILAttr.h"
 #include "nsSMILParserUtils.h"
 #include "nsSMILNullType.h"
 #include "nsISMILAnimationElement.h"
+#include "nsSMILTimedElement.h"
 #include "nsGkAtoms.h"
 #include "nsCOMPtr.h"
 #include "nsCOMArray.h"
 #include "nsIContent.h"
 #include "nsAutoPtr.h"
 #include "nsContentUtils.h"
 #include "nsReadableUtils.h"
 #include "nsString.h"
@@ -184,17 +185,17 @@ nsSMILAnimationFunction::UnsetAttr(nsIAt
 }
 
 void
 nsSMILAnimationFunction::SampleAt(nsSMILTime aSampleTime,
                                   const nsSMILTimeValue& aSimpleDuration,
                                   PRUint32 aRepeatIteration)
 {
   if (mHasChanged || mLastValue || mSampleTime != aSampleTime ||
-      mSimpleDuration.CompareTo(aSimpleDuration) ||
+      mSimpleDuration != aSimpleDuration ||
       mRepeatIteration != aRepeatIteration) {
     mHasChanged = PR_TRUE;
   }
 
   mSampleTime       = aSampleTime;
   mSimpleDuration   = aSimpleDuration;
   mRepeatIteration  = aRepeatIteration;
   mLastValue        = PR_FALSE;
@@ -244,24 +245,22 @@ nsSMILAnimationFunction::ComposeResult(c
   nsresult rv = GetValues(aSMILAttr, values);
   if (NS_FAILED(rv))
     return;
 
   // GetValues may update the error state
   if (mErrorFlags != 0)
     return;
 
-  // If this interval is active, we must have a non-negative
-  // mSampleTime and a resolved or indefinite mSimpleDuration.
-  // (Otherwise, we're probably just frozen.)
-  if (mIsActive) {
-    NS_ENSURE_TRUE(mSampleTime >= 0,);
-    NS_ENSURE_TRUE(mSimpleDuration.IsResolved() ||
-                   mSimpleDuration.IsIndefinite(),);
-  }
+  // If this interval is active, we must have a non-negative mSampleTime
+  NS_ABORT_IF_FALSE(mSampleTime >= 0 || !mIsActive,
+      "Negative sample time for active animation");
+  NS_ABORT_IF_FALSE(mSimpleDuration.IsResolved() ||
+      mSimpleDuration.IsIndefinite() || mLastValue,
+      "Unresolved simple duration for active or frozen animation");
 
   nsSMILValue result(aResult.mType);
 
   if (mSimpleDuration.IsIndefinite() ||
       (HasAttr(nsGkAtoms::values) && values.Length() == 1)) {
 
     // Indefinite duration or only one value set: Always set the first value
     result = values[0];
new file mode 100644
--- /dev/null
+++ b/content/smil/nsSMILMilestone.h
@@ -0,0 +1,110 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (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.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is the Mozilla SMIL module.
+ *
+ * The Initial Developer of the Original Code is Brian Birtles.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Brian Birtles <birtles@gmail.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifndef NS_SMILMILESTONE_H_
+#define NS_SMILMILESTONE_H_
+
+/*
+ * A significant moment in an nsSMILTimedElement's lifetime where a sample is
+ * required.
+ *
+ * Animations register the next milestone in their lifetime with the time
+ * container that they belong to. When the animation controller goes to run
+ * a sample it first visits all the animations that have a registered milestone
+ * in order of their milestone times. This allows interdependencies between
+ * animations to be correctly resolved and events to fire in the proper order.
+ *
+ * A distinction is made between a milestone representing the end of an interval
+ * and any other milestone. This is because if animation A ends at time t, and
+ * animation B begins at the same time t (or has some other significant moment
+ * such as firing a repeat event), SMIL's endpoint-exclusive timing model
+ * implies that the interval end occurs first. In fact, interval ends can be
+ * thought of as ending an infinitesimally small time before t. Therefore,
+ * A should be sampled before B.
+ *
+ * Furthermore, this distinction between sampling the end of an interval and
+ * a regular sample is used within the timing model (specifically in
+ * nsSMILTimedElement) to ensure that all intervals ending at time t are sampled
+ * before any new intervals are entered so that we have a fully up-to-date set
+ * of instance times available before committing to a new interval. Once an
+ * interval is entered, the begin time is fixed.
+ */
+class nsSMILMilestone
+{
+public:
+  nsSMILMilestone(nsSMILTime aTime, PRBool aIsEnd)
+    : mTime(aTime), mIsEnd(aIsEnd)
+  { }
+
+  nsSMILMilestone()
+    : mTime(0), mIsEnd(PR_FALSE)
+  { }
+
+  PRBool operator==(const nsSMILMilestone& aOther) const
+  {
+    return mTime == aOther.mTime && mIsEnd == aOther.mIsEnd;
+  }
+
+  PRBool operator!=(const nsSMILMilestone& aOther) const
+  {
+    return !(*this == aOther);
+  }
+
+  PRBool operator<(const nsSMILMilestone& aOther) const
+  {
+    // Earlier times sort first, and for equal times end milestones sort first
+    return mTime < aOther.mTime ||
+          (mTime == aOther.mTime && mIsEnd && !aOther.mIsEnd);
+  }
+
+  PRBool operator<=(const nsSMILMilestone& aOther) const
+  {
+    return *this == aOther || *this < aOther;
+  }
+  
+  PRBool operator>=(const nsSMILMilestone& aOther) const
+  {
+    return !(*this < aOther);
+  }
+
+  nsSMILTime   mTime;  // The milestone time. This may be in container time or
+                       // parent container time depending on where it is used.
+  PRPackedBool mIsEnd; // PR_TRUE if this milestone corresponds to an interval
+                       // end, PR_FALSE otherwise.
+};
+
+#endif // NS_SMILMILESTONE_H_
--- a/content/smil/nsSMILTimeContainer.cpp
+++ b/content/smil/nsSMILTimeContainer.cpp
@@ -31,16 +31,18 @@
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "nsSMILTimeContainer.h"
+#include "nsSMILTimeValue.h"
+#include "nsSMILTimedElement.h"
 
 nsSMILTimeContainer::nsSMILTimeContainer()
 :
   mParent(nsnull),
   mCurrentTime(0L),
   mParentOffset(0L),
   mPauseStart(0L),
   mNeedsPauseSample(PR_FALSE),
@@ -50,16 +52,36 @@ nsSMILTimeContainer::nsSMILTimeContainer
 
 nsSMILTimeContainer::~nsSMILTimeContainer()
 {
   if (mParent) {
     mParent->RemoveChild(*this);
   }
 }
 
+nsSMILTimeValue
+nsSMILTimeContainer::ContainerToParentTime(nsSMILTime aContainerTime) const
+{
+  // If we're paused, then future times are indefinite
+  if (IsPaused() && aContainerTime > mCurrentTime)
+    return nsSMILTimeValue::Indefinite();
+
+  return nsSMILTimeValue(aContainerTime + mParentOffset);
+}
+
+nsSMILTimeValue
+nsSMILTimeContainer::ParentToContainerTime(nsSMILTime aParentTime) const
+{
+  // If we're paused, then any time after when we paused is indefinite
+  if (IsPaused() && aParentTime > mPauseStart)
+    return nsSMILTimeValue::Indefinite();
+
+  return nsSMILTimeValue(aParentTime - mParentOffset);
+}
+
 void
 nsSMILTimeContainer::Begin()
 {
   Resume(PAUSE_BEGIN);
   if (mPauseState) {
     mNeedsPauseSample = PR_TRUE;
   }
 
@@ -118,17 +140,17 @@ nsSMILTimeContainer::SetCurrentTime(nsSM
   // The following behaviour is consistent with:
   // http://www.w3.org/2003/01/REC-SVG11-20030114-errata
   //  #getCurrentTime_setCurrentTime_undefined_before_document_timeline_begin
   // which says that if SetCurrentTime is called before the document timeline
   // has begun we should still adjust the offset.
   nsSMILTime parentTime = GetParentTime();
   mParentOffset = parentTime - aSeekTo;
 
-  if (mPauseState) {
+  if (IsPaused()) {
     mNeedsPauseSample = PR_TRUE;
     mPauseStart = parentTime;
   }
 
   // Force an update to the current time in case we get a call to GetCurrentTime
   // before another call to Sample().
   UpdateCurrentTime();
 }
@@ -166,14 +188,97 @@ nsSMILTimeContainer::SetParent(nsSMILTim
   nsresult rv = NS_OK;
   if (mParent) {
     rv = mParent->AddChild(*this);
   }
 
   return rv;
 }
 
+PRBool
+nsSMILTimeContainer::AddMilestone(const nsSMILMilestone& aMilestone,
+                                  nsISMILAnimationElement& aElement)
+{
+  // We record the milestone time and store it along with the element but this
+  // time may change (e.g. if attributes are changed on the timed element in
+  // between samples). If this happens, then we may do an unecessary sample
+  // but that's pretty cheap.
+  return mMilestoneEntries.Push(MilestoneEntry(aMilestone, aElement));
+}
+
+void
+nsSMILTimeContainer::ClearMilestones()
+{
+  mMilestoneEntries.Clear();
+}
+
+PRBool
+nsSMILTimeContainer::GetNextMilestoneInParentTime(
+    nsSMILMilestone& aNextMilestone) const
+{
+  if (mMilestoneEntries.IsEmpty())
+    return PR_FALSE;
+
+  nsSMILTimeValue parentTime =
+    ContainerToParentTime(mMilestoneEntries.Top().mMilestone.mTime);
+  if (!parentTime.IsResolved())
+    return PR_FALSE;
+
+  aNextMilestone = nsSMILMilestone(parentTime.GetMillis(),
+                                   mMilestoneEntries.Top().mMilestone.mIsEnd);
+
+  return PR_TRUE;
+}
+
+PRBool
+nsSMILTimeContainer::PopMilestoneElementsAtMilestone(
+      const nsSMILMilestone& aMilestone,
+      AnimElemArray& aMatchedElements)
+{
+  if (mMilestoneEntries.IsEmpty())
+    return PR_FALSE;
+
+  nsSMILTimeValue containerTime = ParentToContainerTime(aMilestone.mTime);
+  if (!containerTime.IsResolved())
+    return PR_FALSE;
+
+  nsSMILMilestone containerMilestone(containerTime.GetMillis(),
+                                     aMilestone.mIsEnd);
+
+  NS_ABORT_IF_FALSE(mMilestoneEntries.Top().mMilestone >= containerMilestone,
+      "Trying to pop off earliest times but we have earlier ones that were "
+      "overlooked");
+
+  PRBool gotOne = PR_FALSE;
+  while (!mMilestoneEntries.IsEmpty() &&
+      mMilestoneEntries.Top().mMilestone == containerMilestone)
+  {
+    aMatchedElements.AppendElement(mMilestoneEntries.Pop().mTimebase);
+    gotOne = PR_TRUE;
+  }
+
+  return gotOne;
+}
+
+void
+nsSMILTimeContainer::Traverse(nsCycleCollectionTraversalCallback* aCallback)
+{
+  const MilestoneEntry* p = mMilestoneEntries.Elements();
+  const MilestoneEntry* const end = p + mMilestoneEntries.Length();
+  while (p != end) {
+    NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(*aCallback, "mTimebase");
+    aCallback->NoteXPCOMChild(p->mTimebase.get());
+    ++p;
+  }
+}
+
+void
+nsSMILTimeContainer::Unlink()
+{
+  mMilestoneEntries.Clear();
+}
+
 void
 nsSMILTimeContainer::UpdateCurrentTime()
 {
-  nsSMILTime now = mPauseState ? mPauseStart : GetParentTime();
+  nsSMILTime now = IsPaused() ? mPauseStart : GetParentTime();
   mCurrentTime = now - mParentOffset;
 }
--- a/content/smil/nsSMILTimeContainer.h
+++ b/content/smil/nsSMILTimeContainer.h
@@ -35,16 +35,22 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef NS_SMILTIMECONTAINER_H_
 #define NS_SMILTIMECONTAINER_H_
 
 #include "nscore.h"
 #include "nsSMILTypes.h"
+#include "nsTPriorityQueue.h"
+#include "nsAutoPtr.h"
+#include "nsISMILAnimationElement.h"
+#include "nsSMILMilestone.h"
+
+class nsSMILTimeValue;
 
 //----------------------------------------------------------------------
 // nsSMILTimeContainer
 //
 // Common base class for a time base that can be paused, resumed, and sampled.
 //
 class nsSMILTimeContainer
 {
@@ -91,16 +97,25 @@ public:
    * Note that the time container may also be paused by other types; this method
    * does not test if aType is the exclusive pause source.
    *
    * @param @aType The pause source to test for.
    * @return PR_TRUE if this container is paused by aType.
    */
   PRBool IsPausedByType(PRUint32 aType) const { return mPauseState & aType; }
 
+  /**
+   * Returns true if this time container is paused.
+   * Generally you should test for a specific type of pausing using
+   * IsPausedByType.
+   *
+   * @return PR_TRUE if this container is paused, PR_FALSE otherwise.
+   */
+  PRBool IsPaused() const { return mPauseState != 0; }
+
   /*
    * Return the time elapsed since this time container's begin time (expressed
    * in parent time) minus any accumulated offset from pausing.
    */
   nsSMILTime GetCurrentTime() const;
 
   /*
    * Seek the document timeline to the specified time.
@@ -111,16 +126,34 @@ public:
   void SetCurrentTime(nsSMILTime aSeekTo);
 
   /*
    * Return the current time for the parent time container if any.
    */
   virtual nsSMILTime GetParentTime() const;
 
   /*
+   * Convert container time to parent time.
+   *
+   * @param   aContainerTime The container time to convert.
+   * @return  The equivalent parent time or indefinite if the container is
+   *          paused and the time is in the future.
+   */
+  nsSMILTimeValue ContainerToParentTime(nsSMILTime aContainerTime) const;
+
+  /*
+   * Convert from parent time to container time.
+   *
+   * @param   aParentTime The parent time to convert.
+   * @return  The equivalent container time or indefinite if the container is
+   *          paused and aParentTime is after the time when the pause began.
+   */
+  nsSMILTimeValue ParentToContainerTime(nsSMILTime aParentTime) const;
+
+  /*
    * Updates the current time of this time container and calls DoSample to
    * perform any sample-operations.
    */
   void Sample();
 
   /*
    * Return if this time container should be sampled or can be skipped.
    *
@@ -131,16 +164,62 @@ public:
 
   /*
    * Sets the parent time container.
    *
    * The callee still retains ownership of the time container.
    */
   nsresult SetParent(nsSMILTimeContainer* aParent);
 
+  /*
+   * Registers an element for a sample at the given time.
+   *
+   * @param   aMilestone  The milestone to register in container time.
+   * @param   aElement    The timebase element that needs a sample at
+   *                      aMilestone.
+   * @return  PR_TRUE if the element was successfully added, PR_FALSE otherwise.
+   */
+  PRBool AddMilestone(const nsSMILMilestone& aMilestone,
+                      nsISMILAnimationElement& aElement);
+
+  /*
+   * Resets the list of milestones.
+   */
+  void ClearMilestones();
+
+  /*
+   * Returns the next significant transition from amongst the registered
+   * milestones.
+   *
+   * @param[out] aNextMilestone The next milestone with time in parent time.
+   *
+   * @return PR_TRUE if there exists another milestone, PR_FALSE otherwise in
+   * which case aNextMilestone will be unmodified.
+   */
+  PRBool GetNextMilestoneInParentTime(nsSMILMilestone& aNextMilestone) const;
+
+  typedef nsTArray<nsRefPtr<nsISMILAnimationElement> > AnimElemArray;
+
+  /*
+   * Removes and returns the timebase elements from the start of the list of
+   * timebase elements that match the given time.
+   *
+   * @param      aMilestone  The milestone time to match in parent time. This
+   *                         must be <= GetNextMilestoneInParentTime.
+   * @param[out] aMatchedElements The array to which matching elements will be
+   *                              appended.
+   * @return PR_TRUE if one or more elements match, PR_FALSE otherwise.
+   */
+  PRBool PopMilestoneElementsAtMilestone(const nsSMILMilestone& aMilestone,
+                                         AnimElemArray& aMatchedElements);
+
+  // Cycle-collection support
+  void Traverse(nsCycleCollectionTraversalCallback* aCallback);
+  void Unlink();
+
 protected:
   /*
    * Per-sample operations to be performed whenever Sample() is called and
    * NeedsSample() is true. Called after updating mCurrentTime;
    */
   virtual void DoSample() { }
 
   /*
@@ -175,20 +254,42 @@ protected:
   // The number of milliseconds for which the container has been paused
   // (excluding the current pause interval if the container is currently
   // paused).
   //
   //  Current time = parent time - mParentOffset
   //
   nsSMILTime mParentOffset;
 
-  // The timestamp in milliseconds since the epoch (i.e. wallclock time) when
-  // the document was paused
+  // The timestamp in parent time when the container was paused
   nsSMILTime mPauseStart;
 
   // Whether or not a pause sample is required
   PRPackedBool mNeedsPauseSample;
 
   // A bitfield of the pause state for all pause requests
   PRUint32 mPauseState;
+
+  struct MilestoneEntry
+  {
+    MilestoneEntry(nsSMILMilestone aMilestone,
+                   nsISMILAnimationElement& aElement)
+      : mMilestone(aMilestone), mTimebase(&aElement)
+    { }
+
+    PRBool operator<(const MilestoneEntry& aOther) const
+    {
+      return mMilestone < aOther.mMilestone;
+    }
+
+    nsSMILMilestone mMilestone; // In container time.
+    nsRefPtr<nsISMILAnimationElement> mTimebase;
+  };
+
+  // Queue of elements with registered milestones. Used to update the model with
+  // significant transitions that occur between two samples. Since timed element
+  // re-register their milestones when they're sampled this is reset once we've
+  // taken care of the milestones before the current sample time but before we
+  // actually do the full sample.
+  nsTPriorityQueue<MilestoneEntry> mMilestoneEntries;
 };
 
 #endif // NS_SMILTIMECONTAINER_H_
--- a/content/smil/nsSMILTimeValue.cpp
+++ b/content/smil/nsSMILTimeValue.cpp
@@ -31,72 +31,28 @@
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "nsSMILTimeValue.h"
-#include "nsDebug.h"
 
-nsSMILTime nsSMILTimeValue::kUnresolvedSeconds = LL_MAXINT;
-
-//----------------------------------------------------------------------
-// Implementation
-
-// Default constructor creates an unresolved time
-nsSMILTimeValue::nsSMILTimeValue()
-  : mMilliseconds(LL_MAXINT),
-    mState(STATE_UNRESOLVED)
-{
-}
+nsSMILTime nsSMILTimeValue::kUnresolvedMillis = LL_MAXINT;
 
 //----------------------------------------------------------------------
 // nsSMILTimeValue methods:
 
-inline PRInt8
-nsSMILTimeValue::Cmp(PRInt64 aA, PRInt64 aB) const
+static inline PRInt8
+Cmp(PRInt64 aA, PRInt64 aB)
 {
   return aA == aB ? 0 : (aA > aB ? 1 : -1);
 }
 
-void
-nsSMILTimeValue::SetIndefinite()
-{
-  mState = STATE_INDEFINITE;
-  mMilliseconds = LL_MAXINT;
-}
-
-void
-nsSMILTimeValue::SetUnresolved()
-{
-  mState = STATE_UNRESOLVED;
-  mMilliseconds = LL_MAXINT;
-}
-
-nsSMILTime
-nsSMILTimeValue::GetMillis() const
-{
-  NS_ASSERTION(mState == STATE_RESOLVED,
-               "GetMillis() called for unresolved time.");
-
-  if (mState != STATE_RESOLVED)
-      return kUnresolvedSeconds;
-
-  return mMilliseconds;
-}
-
-void
-nsSMILTimeValue::SetMillis(nsSMILTime aMillis)
-{
-  mState = STATE_RESOLVED;
-  mMilliseconds = aMillis;
-}
-
 PRInt8
 nsSMILTimeValue::CompareTo(const nsSMILTimeValue& aOther) const
 {
   PRInt8 result;
 
   if (mState == STATE_RESOLVED) {
     result = (aOther.mState == STATE_RESOLVED)
            ? Cmp(mMilliseconds, aOther.mMilliseconds)
--- a/content/smil/nsSMILTimeValue.h
+++ b/content/smil/nsSMILTimeValue.h
@@ -36,16 +36,17 @@
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef NS_SMILTIMEVALUE_H_
 #define NS_SMILTIMEVALUE_H_
 
 #include "prtypes.h"
 #include "prlong.h"
 #include "nsSMILTypes.h"
+#include "nsDebug.h"
 
 /*----------------------------------------------------------------------
  * nsSMILTimeValue class
  *
  * A tri-state time value.
  *
  * First a quick overview of the SMIL time data types:
  *
@@ -97,33 +98,85 @@
  * Unresolved    |  LL_MAXINT         |  PR_FALSE          |  PR_FALSE
  *
  */
 
 class nsSMILTimeValue
 {
 public:
   // Creates an unresolved time value
-  nsSMILTimeValue();
+  nsSMILTimeValue()
+  : mMilliseconds(kUnresolvedMillis),
+    mState(STATE_UNRESOLVED)
+  { }
+
+  // Creates a resolved time value
+  explicit nsSMILTimeValue(nsSMILTime aMillis)
+  : mMilliseconds(aMillis),
+    mState(STATE_RESOLVED)
+  { }
 
-  PRBool            IsIndefinite() const { return mState == STATE_INDEFINITE; }
-  void              SetIndefinite();
+  // Named constructor to create an indefinite time value
+  static nsSMILTimeValue Indefinite()
+  {
+    nsSMILTimeValue value;
+    value.SetIndefinite();
+    return value;
+  }
+
+  PRBool IsIndefinite() const { return mState == STATE_INDEFINITE; }
+  void SetIndefinite()
+  {
+    mState = STATE_INDEFINITE;
+    mMilliseconds = kUnresolvedMillis;
+  }
+
+  PRBool IsResolved() const { return mState == STATE_RESOLVED; }
+  void SetUnresolved()
+  {
+    mState = STATE_UNRESOLVED;
+    mMilliseconds = kUnresolvedMillis;
+  }
 
-  PRBool            IsResolved() const { return mState == STATE_RESOLVED; }
-  void              SetUnresolved();
+  nsSMILTime GetMillis() const
+  {
+    NS_ABORT_IF_FALSE(mState == STATE_RESOLVED,
+       "GetMillis() called for unresolved time");
+
+    return mState == STATE_RESOLVED ? mMilliseconds : kUnresolvedMillis;
+  }
+
+  void SetMillis(nsSMILTime aMillis)
+  {
+    mState = STATE_RESOLVED;
+    mMilliseconds = aMillis;
+  }
+
+  PRInt8 CompareTo(const nsSMILTimeValue& aOther) const;
 
-  nsSMILTime        GetMillis() const;
-  void              SetMillis(nsSMILTime aMillis);
+  PRBool operator==(const nsSMILTimeValue& aOther) const
+  { return CompareTo(aOther) == 0; }
+
+  PRBool operator!=(const nsSMILTimeValue& aOther) const
+  { return CompareTo(aOther) != 0; }
+
+  PRBool operator<(const nsSMILTimeValue& aOther) const
+  { return CompareTo(aOther) < 0; }
 
-  PRInt8            CompareTo(const nsSMILTimeValue& aOther) const;
+  PRBool operator>(const nsSMILTimeValue& aOther) const
+  { return CompareTo(aOther) > 0; }
+
+  PRBool operator<=(const nsSMILTimeValue& aOther) const
+  { return CompareTo(aOther) <= 0; }
+
+  PRBool operator>=(const nsSMILTimeValue& aOther) const
+  { return CompareTo(aOther) >= 0; }
 
 private:
-  PRInt8            Cmp(PRInt64 aA, PRInt64 aB) const;
-
-  static nsSMILTime kUnresolvedSeconds;
+  static nsSMILTime kUnresolvedMillis;
 
   nsSMILTime        mMilliseconds;
   enum {
     STATE_RESOLVED,
     STATE_INDEFINITE,
     STATE_UNRESOLVED
   } mState;
 };
--- a/content/smil/nsSMILTimedElement.cpp
+++ b/content/smil/nsSMILTimedElement.cpp
@@ -61,36 +61,51 @@ nsAttrValue::EnumTable nsSMILTimedElemen
 
 nsAttrValue::EnumTable nsSMILTimedElement::sRestartModeTable[] = {
       {"always", RESTART_ALWAYS},
       {"whenNotActive", RESTART_WHENNOTACTIVE},
       {"never", RESTART_NEVER},
       {nsnull, 0}
 };
 
+const nsSMILMilestone nsSMILTimedElement::sMaxMilestone(LL_MAXINT, PR_FALSE);
+
 //----------------------------------------------------------------------
 // Ctor, dtor
 
 nsSMILTimedElement::nsSMILTimedElement()
 :
-  mBeginSpecs(),
-  mEndSpecs(),
+  mAnimationElement(nsnull),
   mFillMode(FILL_REMOVE),
   mRestartMode(RESTART_ALWAYS),
   mBeginSpecSet(PR_FALSE),
   mEndHasEventConditions(PR_FALSE),
   mClient(nsnull),
-  mCurrentInterval(),
+  mPrevRegisteredMilestone(sMaxMilestone),
   mElementState(STATE_STARTUP)
 {
   mSimpleDur.SetIndefinite();
   mMin.SetMillis(0L);
   mMax.SetIndefinite();
 }
 
+void
+nsSMILTimedElement::SetAnimationElement(nsISMILAnimationElement* aElement)
+{
+  NS_ABORT_IF_FALSE(aElement, "NULL owner element");
+  NS_ABORT_IF_FALSE(!mAnimationElement, "Re-setting owner");
+  mAnimationElement = aElement;
+}
+
+nsSMILTimeContainer*
+nsSMILTimedElement::GetTimeContainer()
+{
+  return mAnimationElement ? mAnimationElement->GetTimeContainer() : nsnull;
+}
+
 //----------------------------------------------------------------------
 // nsIDOMElementTimeControl methods
 //
 // The definition of the ElementTimeControl interface differs between SMIL
 // Animation and SVG 1.1. In SMIL Animation all methods have a void return
 // type and the new instance time is simply added to the list and restart
 // semantics are applied as with any other instance time. In the SVG definition
 // the methods return a bool depending on the restart mode.
@@ -98,24 +113,23 @@ nsSMILTimedElement::nsSMILTimedElement()
 // This inconsistency has now been addressed by an erratum in SVG 1.1:
 //
 // http://www.w3.org/2003/01/REC-SVG11-20030114-errata#elementtimecontrol-interface
 //
 // which favours the definition in SMIL, i.e. instance times are just added
 // without first checking the restart mode.
 
 nsresult
-nsSMILTimedElement::BeginElementAt(double aOffsetSeconds,
-                                   const nsSMILTimeContainer* aContainer)
+nsSMILTimedElement::BeginElementAt(double aOffsetSeconds)
 {
-  if (!aContainer)
+  nsSMILTimeContainer* container = GetTimeContainer();
+  if (!container)
     return NS_ERROR_FAILURE;
 
-  nsSMILTime currentTime = aContainer->GetCurrentTime();
-
+  nsSMILTime currentTime = container->GetCurrentTime();
   AddInstanceTimeFromCurrentTime(currentTime, aOffsetSeconds, PR_TRUE);
 
   // After we've added the instance time we must do a local resample.
   //
   // The reason for this can be explained by considering the following sequence
   // of calls in a script block
   //
   //   BeginElementAt(0)
@@ -134,31 +148,38 @@ nsSMILTimedElement::BeginElementAt(doubl
   // When we get the second call to BeginElementAt the element should be in the
   // active state and hence the new begin instance time will be ignored because
   // it is before the beginning of the (new) current interval. SMIL says we do
   // not change the begin of a current interval once it is active.
   //
   // See also:
   // http://www.w3.org/TR/SMIL3/smil-timing.html#Timing-BeginEnd-Restart
 
-  SampleAt(currentTime);
+  // If we haven't started yet, then there's no point in trying to force the
+  // sample. A series of calls to BeginElementAt before the document starts
+  // should probably just add a series of instance times.
+  if (mElementState != STATE_STARTUP) {
+    DoSampleAt(currentTime, PR_FALSE); // Regular sample, not end sample
+  }
 
   return NS_OK;
 }
 
 nsresult
-nsSMILTimedElement::EndElementAt(double aOffsetSeconds,
-                                 const nsSMILTimeContainer* aContainer)
+nsSMILTimedElement::EndElementAt(double aOffsetSeconds)
 {
-  if (!aContainer)
+  nsSMILTimeContainer* container = GetTimeContainer();
+  if (!container)
     return NS_ERROR_FAILURE;
 
-  nsSMILTime currentTime = aContainer->GetCurrentTime();
+  nsSMILTime currentTime = container->GetCurrentTime();
   AddInstanceTimeFromCurrentTime(currentTime, aOffsetSeconds, PR_FALSE);
-  SampleAt(currentTime);
+  if (mElementState != STATE_STARTUP) {
+    DoSampleAt(currentTime, PR_FALSE); // Regular sample, not end sample
+  }
 
   return NS_OK;
 }
 
 //----------------------------------------------------------------------
 // nsSVGAnimationElement methods
 
 nsSMILTimeValue
@@ -192,25 +213,70 @@ nsSMILTimedElement::SetTimeClient(nsSMIL
   // No need to check for NULL. A NULL parameter simply means to remove the
   // previous client which we do by setting to NULL anyway.
   //
 
   mClient = aClient;
 }
 
 void
-nsSMILTimedElement::SampleAt(nsSMILTime aDocumentTime)
+nsSMILTimedElement::SampleAt(nsSMILTime aContainerTime)
+{
+  // Milestones are cleared before a sample
+  mPrevRegisteredMilestone = sMaxMilestone;
+
+  DoSampleAt(aContainerTime, PR_FALSE);
+}
+
+void
+nsSMILTimedElement::SampleEndAt(nsSMILTime aContainerTime)
 {
+  // Milestones are cleared before a sample
+  mPrevRegisteredMilestone = sMaxMilestone;
+
+  // If the current interval changes, we don't bother trying to remove any old
+  // milestones we'd registered. So it's possible to get a call here to end an
+  // interval at a time that no longer reflects the end of the current interval.
+  //
+  // For now we just check that we're actually in an interval but note that the
+  // initial sample we use to initialise the model is an end sample. This is
+  // because we want to resolve all the instance times before committing to an
+  // initial interval. Therefore an end sample from the startup state is also
+  // acceptable.
+  if (mElementState == STATE_ACTIVE || mElementState == STATE_STARTUP) {
+    DoSampleAt(aContainerTime, PR_TRUE); // End sample
+  } else {
+    // Even if this was an unnecessary milestone sample we want to be sure that
+    // our next real milestone is registered.
+    RegisterMilestone();
+  }
+}
+
+void
+nsSMILTimedElement::DoSampleAt(nsSMILTime aContainerTime, PRBool aEndOnly)
+{
+  NS_ABORT_IF_FALSE(mAnimationElement,
+      "Got sample before being registered with an animation element");
+  NS_ABORT_IF_FALSE(GetTimeContainer(),
+      "Got sample without being registered with a time container");
+
+  // This could probably happen if we later implement externalResourcesRequired
+  // (bug 277955) and whilst waiting for those resources (and the animation to
+  // start) we transfer a node from another document fragment that has already
+  // started. In such a case we might receive milestone samples registered with
+  // the already active container.
+  if (GetTimeContainer()->IsPausedByType(nsSMILTimeContainer::PAUSE_BEGIN))
+    return;
+
+  NS_ABORT_IF_FALSE(mElementState != STATE_STARTUP || aEndOnly,
+      "Got a regular sample during startup state, expected an end sample"
+      " instead");
+
   PRBool          stateChanged;
-  nsSMILTimeValue docTime;
-  docTime.SetMillis(aDocumentTime);
-
-  // XXX Need to cache previous sample time and if this time is less then
-  // perform backwards seeking behaviour (see SMILANIM 3.6.5 Hyperlinks and
-  // timing)
+  nsSMILTimeValue sampleTime(aContainerTime);
 
   do {
     stateChanged = PR_FALSE;
 
     switch (mElementState)
     {
     case STATE_STARTUP:
       {
@@ -219,55 +285,72 @@ nsSMILTimedElement::SampleAt(nsSMILTime 
          ? STATE_WAITING
          : STATE_POSTACTIVE;
         stateChanged = PR_TRUE;
       }
       break;
 
     case STATE_WAITING:
       {
-        if (mCurrentInterval.mBegin.CompareTo(docTime) <= 0) {
+        if (mCurrentInterval.mBegin <= sampleTime) {
           mElementState = STATE_ACTIVE;
           if (mClient) {
             mClient->Activate(mCurrentInterval.mBegin.GetMillis());
           }
           stateChanged = PR_TRUE;
         }
       }
       break;
 
     case STATE_ACTIVE:
       {
-        CheckForEarlyEnd(docTime);
-        if (mCurrentInterval.mEnd.CompareTo(docTime) <= 0) {
+        // Only apply an early end if we're not already ending.
+        if (mCurrentInterval.mEnd > sampleTime) {
+          nsSMILTimeValue earlyEnd = CheckForEarlyEnd(sampleTime);
+          if (earlyEnd.IsResolved()) {
+            mCurrentInterval.mEnd = earlyEnd;
+          }
+        }
+
+        if (mCurrentInterval.mEnd <= sampleTime) {
           nsSMILInterval newInterval;
           mElementState =
             (NS_SUCCEEDED(GetNextInterval(&mCurrentInterval, newInterval)))
             ? STATE_WAITING
             : STATE_POSTACTIVE;
           if (mClient) {
             mClient->Inactivate(mFillMode == FILL_FREEZE);
           }
           SampleFillValue();
           mOldIntervals.AppendElement(mCurrentInterval);
           mCurrentInterval = newInterval;
           Reset();
           stateChanged = PR_TRUE;
         } else {
           nsSMILTime beginTime = mCurrentInterval.mBegin.GetMillis();
-          nsSMILTime activeTime = aDocumentTime - beginTime;
+          nsSMILTime activeTime = aContainerTime - beginTime;
           SampleSimpleTime(activeTime);
         }
       }
       break;
 
     case STATE_POSTACTIVE:
       break;
     }
-  } while (stateChanged);
+
+  // Generally we continue driving the state machine so long as we have changed
+  // state. However, for end samples we only drive the state machine as far as
+  // the waiting or postactive state because we don't want to commit to any new
+  // interval (by transitioning to the active state) until all the end samples
+  // have finished and we then have complete information about the available
+  // instance times upon which to base our next interval.
+  } while (stateChanged && (!aEndOnly || (mElementState != STATE_WAITING &&
+                                          mElementState != STATE_POSTACTIVE)));
+
+  RegisterMilestone();
 }
 
 void
 nsSMILTimedElement::Reset()
 {
   PRInt32 count = mBeginInstances.Length();
 
   for (PRInt32 i = count - 1; i >= 0; --i) {
@@ -626,16 +709,22 @@ nsSMILTimedElement::UnsetFillMode()
   PRUint16 previousFillMode = mFillMode;
   mFillMode = FILL_REMOVE;
   if ((mElementState == STATE_WAITING || mElementState == STATE_POSTACTIVE) &&
       previousFillMode == FILL_FREEZE &&
       mClient)
     mClient->Inactivate(PR_FALSE);
 }
 
+void
+nsSMILTimedElement::BindToTree()
+{
+  RegisterMilestone();
+}
+
 //----------------------------------------------------------------------
 // Implementation helpers
 
 nsresult
 nsSMILTimedElement::SetBeginOrEndSpec(const nsAString& aSpec,
                                       PRBool aIsBegin)
 {
   nsRefPtr<nsSMILTimeValueSpec> spec;
@@ -679,42 +768,40 @@ nsSMILTimedElement::SetBeginOrEndSpec(co
 //
 // See:
 // http://www.w3.org/TR/2001/REC-smil-animation-20010904/#Timing-BeginEnd-LC-Start
 //
 nsresult
 nsSMILTimedElement::GetNextInterval(const nsSMILInterval* aPrevInterval,
                                     nsSMILInterval& aResult)
 {
-  static nsSMILTimeValue zeroTime;
-  zeroTime.SetMillis(0L);
+  static nsSMILTimeValue zeroTime(0L);
 
   if (mRestartMode == RESTART_NEVER && aPrevInterval)
     return NS_ERROR_FAILURE;
 
   // Calc starting point
   nsSMILTimeValue beginAfter;
   PRBool prevIntervalWasZeroDur = PR_FALSE;
   if (aPrevInterval) {
     beginAfter = aPrevInterval->mEnd;
-    prevIntervalWasZeroDur
-      = (aPrevInterval->mEnd.CompareTo(aPrevInterval->mBegin) == 0);
+    prevIntervalWasZeroDur = (aPrevInterval->mEnd == aPrevInterval->mBegin);
   } else {
     beginAfter.SetMillis(LL_MININT);
   }
 
   nsSMILTimeValue tempBegin;
   nsSMILTimeValue tempEnd;
 
   nsSMILInstanceTime::Comparator comparator;
   mBeginInstances.Sort(comparator);
   mEndInstances.Sort(comparator);
 
   while (PR_TRUE) {
-    if (!mBeginSpecSet && beginAfter.CompareTo(zeroTime) <= 0) {
+    if (!mBeginSpecSet && beginAfter <= zeroTime) {
       tempBegin.SetMillis(0);
     } else {
       PRInt32 beginPos = 0;
       PRBool beginFound = GetNextGreaterOrEqual(mBeginInstances, beginAfter,
                                                 beginPos, tempBegin);
       if (!beginFound)
         return NS_ERROR_FAILURE;
     }
@@ -726,17 +813,17 @@ nsSMILTimedElement::GetNextInterval(cons
       tempEnd = CalcActiveEnd(tempBegin, indefiniteEnd);
     } else {
       PRInt32 endPos = 0;
       PRBool endFound = GetNextGreaterOrEqual(mEndInstances, tempBegin,
                                               endPos, tempEnd);
 
       // If the last interval ended at the same point and was zero-duration and
       // this one is too, look for another end to use instead
-      if (tempEnd.CompareTo(tempBegin) == 0 && prevIntervalWasZeroDur) {
+      if (tempEnd == tempBegin && prevIntervalWasZeroDur) {
         endFound = GetNextGreater(mEndInstances, tempBegin, endPos, tempEnd);
       }
 
       if (!endFound) {
         if (mEndHasEventConditions || mEndInstances.Length() == 0) {
           tempEnd.SetUnresolved();
         } else {
           //
@@ -750,27 +837,27 @@ nsSMILTimedElement::GetNextInterval(cons
       }
 
       tempEnd = CalcActiveEnd(tempBegin, tempEnd);
     }
 
     // If we get two zero-length intervals in a row we will potentially have an
     // infinite loop so we break it here by searching for the next begin time
     // greater than tempEnd on the next time around.
-    if (tempEnd.IsResolved() && tempBegin.CompareTo(tempEnd) == 0) {
+    if (tempEnd.IsResolved() && tempBegin == tempEnd) {
       if (prevIntervalWasZeroDur) {
-        beginAfter.SetMillis(tempEnd.GetMillis()+1);
+        beginAfter.SetMillis(tempEnd.GetMillis() + 1);
         prevIntervalWasZeroDur = PR_FALSE;
         continue;
       }
       prevIntervalWasZeroDur = PR_TRUE;
     }
 
-    if (tempEnd.CompareTo(zeroTime) > 0 ||
-     (tempBegin.CompareTo(zeroTime) == 0 && tempEnd.CompareTo(zeroTime) == 0)) {
+    if (tempEnd > zeroTime ||
+       (tempBegin == zeroTime && tempEnd == zeroTime)) {
       aResult.mBegin = tempBegin;
       aResult.mEnd = tempEnd;
       return NS_OK;
     } else if (mRestartMode == RESTART_NEVER) {
       // tempEnd <= 0 so we're going to loop which effectively means restarting
       return NS_ERROR_FAILURE;
     } else {
       beginAfter = tempEnd;
@@ -780,52 +867,52 @@ nsSMILTimedElement::GetNextInterval(cons
 
   return NS_ERROR_FAILURE;
 }
 
 PRBool
 nsSMILTimedElement::GetNextGreater(
     const nsTArray<nsSMILInstanceTime>& aList,
     const nsSMILTimeValue& aBase,
-    PRInt32 &aPosition,
-    nsSMILTimeValue& aResult)
+    PRInt32& aPosition,
+    nsSMILTimeValue& aResult) const
 {
   PRBool found;
-  while ((found = GetNextGreaterOrEqual(aList, aBase, aPosition, aResult))
-         && aResult.CompareTo(aBase) == 0);
+  while ((found = GetNextGreaterOrEqual(aList, aBase, aPosition, aResult)) &&
+         aResult == aBase);
   return found;
 }
 
 PRBool
 nsSMILTimedElement::GetNextGreaterOrEqual(
     const nsTArray<nsSMILInstanceTime>& aList,
     const nsSMILTimeValue& aBase,
-    PRInt32 &aPosition,
-    nsSMILTimeValue& aResult)
+    PRInt32& aPosition,
+    nsSMILTimeValue& aResult) const
 {
   PRBool found = PR_FALSE;
   PRInt32 count = aList.Length();
 
   for (; aPosition < count && !found; ++aPosition) {
     const nsSMILInstanceTime &val = aList[aPosition];
-    if (val.Time().CompareTo(aBase) >= 0) {
+    if (val.Time() >= aBase) {
       aResult = val.Time();
       found = PR_TRUE;
     }
   }
 
   return found;
 }
 
 /**
  * @see SMILANIM 3.3.4
  */
 nsSMILTimeValue
 nsSMILTimedElement::CalcActiveEnd(const nsSMILTimeValue& aBegin,
-                                  const nsSMILTimeValue& aEnd)
+                                  const nsSMILTimeValue& aEnd) const
 {
   nsSMILTimeValue result;
 
   NS_ASSERTION(mSimpleDur.IsResolved() || mSimpleDur.IsIndefinite(),
     "Unresolved simple duration in CalcActiveEnd.");
 
   if (!aBegin.IsResolved() && !aBegin.IsIndefinite()) {
     NS_ERROR("Unresolved begin time passed to CalcActiveEnd.");
@@ -855,59 +942,61 @@ nsSMILTimedElement::CalcActiveEnd(const 
     nsSMILTime activeEnd = result.GetMillis() + aBegin.GetMillis();
     result.SetMillis(activeEnd);
   }
 
   return result;
 }
 
 nsSMILTimeValue
-nsSMILTimedElement::GetRepeatDuration()
+nsSMILTimedElement::GetRepeatDuration() const
 {
   nsSMILTimeValue result;
 
   if (mRepeatCount.IsDefinite() && mRepeatDur.IsResolved()) {
     if (mSimpleDur.IsResolved()) {
-      nsSMILTime activeDur = mRepeatCount * double(mSimpleDur.GetMillis());
+      nsSMILTime activeDur =
+        nsSMILTime(mRepeatCount * double(mSimpleDur.GetMillis()));
       result.SetMillis(NS_MIN(activeDur, mRepeatDur.GetMillis()));
     } else {
       result = mRepeatDur;
     }
   } else if (mRepeatCount.IsDefinite() && mSimpleDur.IsResolved()) {
-    nsSMILTime activeDur = mRepeatCount * double(mSimpleDur.GetMillis());
+    nsSMILTime activeDur =
+      nsSMILTime(mRepeatCount * double(mSimpleDur.GetMillis()));
     result.SetMillis(activeDur);
   } else if (mRepeatDur.IsResolved()) {
     result = mRepeatDur;
   } else if (mRepeatCount.IsIndefinite()) {
     result.SetIndefinite();
   } else {
     result = mSimpleDur;
   }
 
   return result;
 }
 
 nsSMILTimeValue
-nsSMILTimedElement::ApplyMinAndMax(const nsSMILTimeValue& aDuration)
+nsSMILTimedElement::ApplyMinAndMax(const nsSMILTimeValue& aDuration) const
 {
   if (!aDuration.IsResolved() && !aDuration.IsIndefinite()) {
     return aDuration;
   }
 
-  if (mMax.CompareTo(mMin) < 0) {
+  if (mMax < mMin) {
     return aDuration;
   }
 
   nsSMILTimeValue result;
 
-  if (aDuration.CompareTo(mMax) > 0) {
+  if (aDuration > mMax) {
     result = mMax;
-  } else if (aDuration.CompareTo(mMin) < 0) {
+  } else if (aDuration < mMin) {
     nsSMILTimeValue repeatDur = GetRepeatDuration();
-    result = (mMin.CompareTo(repeatDur) > 0) ? repeatDur : mMin;
+    result = mMin > repeatDur ? repeatDur : mMin;
   } else {
     result = aDuration;
   }
 
   return result;
 }
 
 nsSMILTime
@@ -937,55 +1026,72 @@ nsSMILTimedElement::ActiveTimeToSimpleTi
 // moment. In particular, this paragraph from section 3.6.8:
 //
 // 'If restart  is set to "always", then the current interval will end early if
 // there is an instance time in the begin list that is before (i.e. earlier
 // than) the defined end for the current interval. Ending in this manner will
 // also send a changed time notice to all time dependents for the current
 // interval end.'
 //
-void
-nsSMILTimedElement::CheckForEarlyEnd(const nsSMILTimeValue& aDocumentTime)
+nsSMILTimeValue
+nsSMILTimedElement::CheckForEarlyEnd(
+    const nsSMILTimeValue& aContainerTime) const
 {
   if (mRestartMode != RESTART_ALWAYS)
-    return;
+    return nsSMILTimeValue();
 
   nsSMILTimeValue nextBegin;
   PRInt32 position = 0;
 
   GetNextGreater(mBeginInstances, mCurrentInterval.mBegin, position, nextBegin);
 
   if (nextBegin.IsResolved() &&
-      nextBegin.CompareTo(mCurrentInterval.mBegin) > 0 &&
-      nextBegin.CompareTo(mCurrentInterval.mEnd) < 0 &&
-      nextBegin.CompareTo(aDocumentTime) <= 0) {
-    mCurrentInterval.mEnd = nextBegin;
+      nextBegin > mCurrentInterval.mBegin &&
+      nextBegin < mCurrentInterval.mEnd &&
+      nextBegin <= aContainerTime) {
+    return nextBegin;
   }
+
+  return nsSMILTimeValue();
 }
 
 void
 nsSMILTimedElement::UpdateCurrentInterval()
 {
+  // We adopt the convention of not resolving intervals until the first sample.
+  // Otherwise, every time each attribute is set we'll re-resolve the current
+  // interval and notify all our time dependents of the change.
+  //
+  // The disadvantage of deferring resolving the interval is that DOM calls to
+  // to getStartTime will throw an INVALID_STATE_ERR exception until the
+  // container timeline begins since the start time has not yet been resolved.
+  if (mElementState == STATE_STARTUP)
+    return;
+
   nsSMILInterval updatedInterval;
   nsSMILInterval* prevInterval = mOldIntervals.IsEmpty()
                                ? nsnull
                                : &mOldIntervals[mOldIntervals.Length() - 1];
   nsresult rv = GetNextInterval(prevInterval, updatedInterval);
 
   if (NS_SUCCEEDED(rv)) {
 
     if (mElementState != STATE_ACTIVE &&
-        updatedInterval.mBegin.CompareTo(mCurrentInterval.mBegin)) {
+        updatedInterval.mBegin != mCurrentInterval.mBegin) {
       mCurrentInterval.mBegin = updatedInterval.mBegin;
     }
 
-    if (updatedInterval.mEnd.CompareTo(mCurrentInterval.mEnd)) {
+    if (updatedInterval.mEnd != mCurrentInterval.mEnd) {
       mCurrentInterval.mEnd = updatedInterval.mEnd;
     }
 
+    // There's a chance our next milestone has now changed, so update the time
+    // container
+    RegisterMilestone();
+
     if (mElementState == STATE_POSTACTIVE) {
       // XXX notify dependents of new interval
       mElementState = STATE_WAITING;
     }
   } else {
 
     nsSMILTimeValue unresolvedTime;
     mCurrentInterval.mEnd = unresolvedTime;
@@ -1044,14 +1150,105 @@ nsSMILTimedElement::SampleFillValue()
 
 void
 nsSMILTimedElement::AddInstanceTimeFromCurrentTime(nsSMILTime aCurrentTime,
     double aOffsetSeconds, PRBool aIsBegin)
 {
   double offset = aOffsetSeconds * PR_MSEC_PER_SEC;
   nsSMILTime timeWithOffset = aCurrentTime + PRInt64(NS_round(offset));
 
-  nsSMILTimeValue timeVal;
-  timeVal.SetMillis(timeWithOffset);
+  nsSMILTimeValue timeVal(timeWithOffset);
 
   nsSMILInstanceTime instanceTime(timeVal, nsnull, PR_TRUE);
   AddInstanceTime(instanceTime, aIsBegin);
 }
+
+void
+nsSMILTimedElement::RegisterMilestone()
+{
+  nsSMILTimeContainer* container = GetTimeContainer();
+  if (!container)
+    return;
+  NS_ABORT_IF_FALSE(mAnimationElement,
+      "Got a time container without an owning animation element");
+
+  nsSMILMilestone nextMilestone;
+  if (!GetNextMilestone(nextMilestone))
+    return;
+
+  // This method is called every time we might possibly have updated our
+  // current interval, but since nsSMILTimeContainer makes no attempt to filter
+  // out redundant milestones we do some rudimentary filtering here. It's not
+  // perfect, but unnecessary samples are fairly cheap.
+  if (nextMilestone >= mPrevRegisteredMilestone)
+    return;
+
+  container->AddMilestone(nextMilestone, *mAnimationElement);
+  mPrevRegisteredMilestone = nextMilestone;
+}
+
+PRBool
+nsSMILTimedElement::GetNextMilestone(nsSMILMilestone& aNextMilestone) const
+{
+  // Return the next key moment in our lifetime.
+  //
+  // XXX Once we implement TimeEvents and event based timing we might need to
+  // include repeat times too, particularly if it's important to get them in
+  // order.
+  //
+  // XXX It may be possible in future to optimise this so that we only register
+  // for milestones if:
+  // a) We have time dependents, or
+  // b) We are dependent on events or syncbase relationships, or
+  // c) There are registered listeners for our events
+  //
+  // Then for the simple case where everything uses offset values we could
+  // ignore milestones altogether.
+  //
+  // We'd need to be careful, however, that if one of those conditions became
+  // true in between samples that we registered our next milestone at that
+  // point.
+
+  switch (mElementState)
+  {
+  case STATE_STARTUP:
+    // All elements register for an initial end sample at t=0 where we resolve
+    // our initial interval.
+    aNextMilestone.mIsEnd = PR_TRUE; // Initial sample should be an end sample
+    aNextMilestone.mTime = 0;
+    return PR_TRUE;
+
+  case STATE_WAITING:
+    aNextMilestone.mIsEnd = PR_FALSE;
+    aNextMilestone.mTime = mCurrentInterval.mBegin.GetMillis();
+    return PR_TRUE;
+
+  case STATE_ACTIVE:
+    {
+      // XXX When we implement TimeEvents, we may need to consider what comes
+      // next: the interval end or an interval repeat.
+
+      // Check for an early end
+      nsSMILTimeValue earlyEnd = CheckForEarlyEnd(mCurrentInterval.mEnd);
+      if (earlyEnd.IsResolved()) {
+        aNextMilestone.mIsEnd = PR_TRUE;
+        aNextMilestone.mTime = earlyEnd.GetMillis();
+        return PR_TRUE;
+      }
+
+      // Otherwise it's just the next interval end
+      if (mCurrentInterval.mEnd.IsResolved()) {
+        aNextMilestone.mIsEnd = PR_TRUE;
+        aNextMilestone.mTime = mCurrentInterval.mEnd.GetMillis();
+        return PR_TRUE;
+      }
+
+      return PR_FALSE;
+    }
+
+  case STATE_POSTACTIVE:
+    return PR_FALSE;
+
+  default:
+    NS_ABORT_IF_FALSE(PR_FALSE, "Invalid element state");
+    return PR_FALSE;
+  }
+}
--- a/content/smil/nsSMILTimedElement.h
+++ b/content/smil/nsSMILTimedElement.h
@@ -35,67 +35,73 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef NS_SMILTIMEDELEMENT_H_
 #define NS_SMILTIMEDELEMENT_H_
 
 #include "nsSMILInterval.h"
 #include "nsSMILInstanceTime.h"
+#include "nsSMILMilestone.h"
 #include "nsSMILTimeValueSpec.h"
 #include "nsSMILRepeatCount.h"
 #include "nsSMILTypes.h"
 #include "nsTArray.h"
 #include "nsAutoPtr.h"
 #include "nsAttrValue.h"
 
+class nsISMILAnimationElement;
 class nsSMILAnimationFunction;
 class nsSMILTimeContainer;
 class nsSMILTimeValue;
 class nsIAtom;
 
 //----------------------------------------------------------------------
 // nsSMILTimedElement
 
 class nsSMILTimedElement
 {
 public:
   nsSMILTimedElement();
 
+  /*
+   * Sets the owning animation element which this class uses to convert between
+   * container times and to register timebase elements.
+   */
+  void SetAnimationElement(nsISMILAnimationElement* aElement);
+
+  /*
+   * Returns the time container with which this timed element is associated or
+   * nsnull if it is not associated with a time container.
+   */
+  nsSMILTimeContainer* GetTimeContainer();
+
   /**
    * Methods for supporting the nsIDOMElementTimeControl interface.
    */
 
   /*
-   * Adds a new begin instance time at the current document time (as defined by
-   * aContainer) plus or minus the specified offset.
+   * Adds a new begin instance time at the current container time plus or minus
+   * the specified offset.
    *
    * @param aOffsetSeconds A real number specifying the number of seconds to add
    *                       to the current container time.
-   * @param aContainer The time container with which this timed element is
-   *                   associated and which should be used for determining the
-   *                   current time.
    * @return NS_OK if the operation succeeeded, or an error code otherwise.
    */
-  nsresult BeginElementAt(double aOffsetSeconds,
-                          const nsSMILTimeContainer* aContainer);
+  nsresult BeginElementAt(double aOffsetSeconds);
 
   /*
-   * Adds a new end instance time at the current document time (as defined by
-   * aContainer) plus or minus the specified offset.
+   * Adds a new end instance time at the current container time plus or minus
+   * the specified offset.
    *
    * @param aOffsetSeconds A real number specifying the number of seconds to add
    *                       to the current container time.
-   * @param aContainer The time container with which this timed element is
-   *                   associated and which should be used for determining the
-   *                   current time.
    * @return NS_OK if the operation succeeeded, or an error code otherwise.
    */
-  nsresult EndElementAt(double aOffsetSeconds,
-                        const nsSMILTimeContainer* aContainer);
+  nsresult EndElementAt(double aOffsetSeconds);
 
   /**
    * Methods for supporting the nsSVGAnimationElement interface.
    */
 
   /**
    * According to SVG 1.1 SE this returns
    *
@@ -122,20 +128,19 @@ public:
    */
 
   /**
    * Adds an instance time object this element's list of instance times.
    * These instance times are used when creating intervals.
    *
    * This method is typically called by an nsSMILTimeValueSpec.
    *
-   * @param aInstanceTime   The time to add, expressed in document time.
-   *
-   * @param aIsBegin        True if the time to be added represents a begin time
-   *                        or false if it represents an end time.
+   * @param aInstanceTime   The time to add, expressed in container time.
+   * @param aIsBegin        PR_TRUE if the time to be added represents a begin
+   *                        time or PR_FALSE if it represents an end time.
    */
   void AddInstanceTime(const nsSMILInstanceTime& aInstanceTime,
                        PRBool aIsBegin);
 
   /**
    * Sets the object that will be called by this timed element each time it is
    * sampled.
    *
@@ -145,23 +150,37 @@ public:
    * @param aClient   The time client to associate. Any previous time client
    *                  will be disassociated and no longer sampled. Setting this
    *                  to nsnull will simply disassociate the previous client, if
    *                  any.
    */
   void SetTimeClient(nsSMILAnimationFunction* aClient);
 
   /**
-   * Samples the object at the given document time. Timing intervals are updated
-   * and if this element is active at the given time the associated time client
-   * will be sampled with the appropriate simple time.
+   * Samples the object at the given container time. Timing intervals are
+   * updated and if this element is active at the given time the associated time
+   * client will be sampled with the appropriate simple time.
    *
-   * @param aDocumentTime The document time at which to sample.
+   * @param aContainerTime The container time at which to sample.
    */
-  void SampleAt(nsSMILTime aDocumentTime);
+  void SampleAt(nsSMILTime aContainerTime);
+
+  /**
+   * Performs a special sample for the end of an interval. Such a sample should
+   * only advance the timed element (and any dependent elements) to the waiting
+   * or postactive state. It should not cause a transition to the active state.
+   * Transition to the active state is only performed on a regular SampleAt.
+   *
+   * This allows all interval ends at a given time to be processed first and
+   * hence the new interval can be established based on full information of the
+   * available instance times.
+   *
+   * @param aContainerTime The container time at which to sample.
+   */
+  void SampleEndAt(nsSMILTime aContainerTime);
 
   /**
    * Reset the element's internal state. As described in SMILANIM 3.3.7, all
    * instance times associated with DOM calls, events, etc. are cleared.
    */
   void Reset();
 
   /**
@@ -201,16 +220,21 @@ public:
    *                    namespace of the attribute is not specified (see
    *                    SetAttr).
    *
    * @return PR_TRUE if the given attribute is a timing attribute, PR_FALSE
    * otherwise.
    */
   PRBool UnsetAttr(nsIAtom* aAttribute);
 
+  /**
+   * Called when the timed element has been bound to the document.
+   */
+  void BindToTree();
+
 protected:
   //
   // Implementation helpers
   //
 
   nsresult          SetBeginSpec(const nsAString& aBeginSpec);
   nsresult          SetEndSpec(const nsAString& aEndSpec);
   nsresult          SetSimpleDuration(const nsAString& aDurSpec);
@@ -227,52 +251,57 @@ protected:
   void              UnsetMin();
   void              UnsetMax();
   void              UnsetRestart();
   void              UnsetRepeatCount();
   void              UnsetRepeatDur();
   void              UnsetFillMode();
 
   nsresult          SetBeginOrEndSpec(const nsAString& aSpec, PRBool aIsBegin);
+  void              DoSampleAt(nsSMILTime aContainerTime, PRBool aEndOnly);
 
   /**
    * Calculates the first acceptable interval for this element.
    *
    * @see SMILANIM 3.6.8
    */
   nsresult          GetNextInterval(const nsSMILInterval* aPrevInterval,
                                     nsSMILInterval& aResult);
   PRBool            GetNextGreater(const nsTArray<nsSMILInstanceTime>& aList,
                                    const nsSMILTimeValue& aBase,
                                    PRInt32& aPosition,
-                                   nsSMILTimeValue& aResult);
+                                   nsSMILTimeValue& aResult) const;
   PRBool            GetNextGreaterOrEqual(
                                    const nsTArray<nsSMILInstanceTime>& aList,
                                    const nsSMILTimeValue& aBase,
                                    PRInt32& aPosition,
-                                   nsSMILTimeValue& aResult);
+                                   nsSMILTimeValue& aResult) const;
   nsSMILTimeValue   CalcActiveEnd(const nsSMILTimeValue& aBegin,
-                                  const nsSMILTimeValue& aEnd);
-  nsSMILTimeValue   GetRepeatDuration();
-  nsSMILTimeValue   ApplyMinAndMax(const nsSMILTimeValue& aDuration);
+                                  const nsSMILTimeValue& aEnd) const;
+  nsSMILTimeValue   GetRepeatDuration() const;
+  nsSMILTimeValue   ApplyMinAndMax(const nsSMILTimeValue& aDuration) const;
   nsSMILTime        ActiveTimeToSimpleTime(nsSMILTime aActiveTime,
                                            PRUint32& aRepeatIteration);
-  void              CheckForEarlyEnd(const nsSMILTimeValue& aDocumentTime);
+  nsSMILTimeValue   CheckForEarlyEnd(
+                        const nsSMILTimeValue& aContainerTime) const;
   void              UpdateCurrentInterval();
   void              SampleSimpleTime(nsSMILTime aActiveTime);
   void              SampleFillValue();
   void              AddInstanceTimeFromCurrentTime(nsSMILTime aCurrentTime,
                         double aOffsetSeconds, PRBool aIsBegin);
+  void              RegisterMilestone();
+  PRBool            GetNextMilestone(nsSMILMilestone& aNextMilestone) const;
 
   // Typedefs
   typedef nsTArray<nsRefPtr<nsSMILTimeValueSpec> >  SMILTimeValueSpecList;
 
   //
   // Members
   //
+  nsISMILAnimationElement* mAnimationElement; // [weak] won't outlive owner
   SMILTimeValueSpecList mBeginSpecs;
   SMILTimeValueSpecList mEndSpecs;
 
   nsSMILTimeValue                 mSimpleDur;
 
   nsSMILRepeatCount               mRepeatCount;
   nsSMILTimeValue                 mRepeatDur;
 
@@ -307,16 +336,18 @@ protected:
   PRPackedBool                    mEndHasEventConditions;
 
   nsTArray<nsSMILInstanceTime>    mBeginInstances;
   nsTArray<nsSMILInstanceTime>    mEndInstances;
 
   nsSMILAnimationFunction*        mClient;
   nsSMILInterval                  mCurrentInterval;
   nsTArray<nsSMILInterval>        mOldIntervals;
+  nsSMILMilestone                 mPrevRegisteredMilestone;
+  static const nsSMILMilestone    sMaxMilestone;
 
   /**
    * The state of the element in its life-cycle. These states are based on the
    * element life-cycle described in SMILANIM 3.6.8
    */
   enum nsSMILElementState
   {
     STATE_STARTUP,
--- a/content/svg/content/src/nsSVGAnimationElement.cpp
+++ b/content/svg/content/src/nsSVGAnimationElement.cpp
@@ -77,16 +77,17 @@ nsSVGAnimationElement::nsSVGAnimationEle
 }
 
 nsresult
 nsSVGAnimationElement::Init()
 {
   nsresult rv = nsSVGAnimationElementBase::Init();
   NS_ENSURE_SUCCESS(rv, rv);
 
+  mTimedElement.SetAnimationElement(this);
   AnimationFunction().SetAnimationElement(this);
   mTimedElement.SetTimeClient(&AnimationFunction());
 
   return NS_OK;
 }
 
 //----------------------------------------------------------------------
 // nsISMILAnimationElement methods
@@ -269,16 +270,18 @@ nsSVGAnimationElement::BindToTree(nsIDoc
       nsAutoString hrefStr;
       href->ToString(hrefStr);
 
       // Pass in |aParent| instead of |this| -- first argument is only used
       // for a call to GetCurrentDoc(), and |this| might not have a current
       // document yet.
       UpdateHrefTarget(aParent, hrefStr);
     }
+
+    mTimedElement.BindToTree();
   }
 
   AnimationNeedsResample();
 
   return NS_OK;
 }
 
 void
@@ -405,37 +408,45 @@ nsSVGAnimationElement::BeginElement(void
 {
   return BeginElementAt(0.f);
 }
 
 /* void beginElementAt (in float offset); */
 NS_IMETHODIMP
 nsSVGAnimationElement::BeginElementAt(float offset)
 {
-  nsresult rv = mTimedElement.BeginElementAt(offset, mTimedDocumentRoot);
+  // This will fail if we're not attached to a time container (SVG document
+  // fragment).
+  nsresult rv = mTimedElement.BeginElementAt(offset);
+  if (NS_FAILED(rv))
+    return rv;
+
   AnimationNeedsResample();
 
-  return rv;
+  return NS_OK;
 }
 
 /* void endElement (); */
 NS_IMETHODIMP
 nsSVGAnimationElement::EndElement(void)
 {
   return EndElementAt(0.f);
 }
 
 /* void endElementAt (in float offset); */
 NS_IMETHODIMP
 nsSVGAnimationElement::EndElementAt(float offset)
 {
-  nsresult rv = mTimedElement.EndElementAt(offset, mTimedDocumentRoot);
+  nsresult rv = mTimedElement.EndElementAt(offset);
+  if (NS_FAILED(rv))
+    return rv;
+
   AnimationNeedsResample();
-
-  return rv;
+ 
+  return NS_OK;
 }
 
 void
 nsSVGAnimationElement::UpdateHrefTarget(nsIContent* aNodeForContext,
                                         const nsAString& aHrefStr)
 {
   nsCOMPtr<nsIURI> targetURI;
   nsCOMPtr<nsIURI> baseURI = GetBaseURI();
--- a/content/svg/content/src/nsSVGSVGElement.cpp
+++ b/content/svg/content/src/nsSVGSVGElement.cpp
@@ -173,20 +173,40 @@ NS_NewSVGSVGElement(nsIContent **aResult
   *aResult = it;
 
   return rv;
 }
 
 //----------------------------------------------------------------------
 // nsISupports methods
 
+#ifdef MOZ_SMIL
+NS_IMPL_CYCLE_COLLECTION_CLASS(nsSVGSVGElement)
+NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN_INHERITED(nsSVGSVGElement,
+                                                nsSVGSVGElementBase)
+  if (tmp->mTimedDocumentRoot) {
+    tmp->mTimedDocumentRoot->Unlink();
+  }
+NS_IMPL_CYCLE_COLLECTION_UNLINK_END
+NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN_INHERITED(nsSVGSVGElement,
+                                                  nsSVGSVGElementBase)
+  if (tmp->mTimedDocumentRoot) {
+    tmp->mTimedDocumentRoot->Traverse(&cb);
+  }
+NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
+#endif // MOZ_SMIL
+
 NS_IMPL_ADDREF_INHERITED(nsSVGSVGElement,nsSVGSVGElementBase)
 NS_IMPL_RELEASE_INHERITED(nsSVGSVGElement,nsSVGSVGElementBase)
 
+#ifdef MOZ_SMIL
+NS_INTERFACE_TABLE_HEAD_CYCLE_COLLECTION_INHERITED(nsSVGSVGElement)
+#else
 NS_INTERFACE_TABLE_HEAD(nsSVGSVGElement)
+#endif
   NS_NODE_INTERFACE_TABLE7(nsSVGSVGElement, nsIDOMNode, nsIDOMElement,
                            nsIDOMSVGElement, nsIDOMSVGSVGElement,
                            nsIDOMSVGFitToViewBox, nsIDOMSVGLocatable,
                            nsIDOMSVGZoomAndPan)
   NS_INTERFACE_MAP_ENTRY_CONTENT_CLASSINFO(SVGSVGElement)
 NS_INTERFACE_MAP_END_INHERITING(nsSVGSVGElementBase)
 
 //----------------------------------------------------------------------
--- a/content/svg/content/src/nsSVGSVGElement.h
+++ b/content/svg/content/src/nsSVGSVGElement.h
@@ -135,16 +135,19 @@ protected:
                                       nsINodeInfo *aNodeInfo,
                                       PRBool aFromParser);
   nsSVGSVGElement(nsINodeInfo* aNodeInfo, PRBool aFromParser);
   
 public:
 
   // interfaces:
   NS_DECL_ISUPPORTS_INHERITED
+#ifdef MOZ_SMIL
+  NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsSVGSVGElement, nsSVGSVGElementBase)
+#endif // MOZ_SMIL
   NS_DECL_NSIDOMSVGSVGELEMENT
   NS_DECL_NSIDOMSVGFITTOVIEWBOX
   NS_DECL_NSIDOMSVGLOCATABLE
   NS_DECL_NSIDOMSVGZOOMANDPAN
   
   // xxx I wish we could use virtual inheritance
   NS_FORWARD_NSIDOMNODE(nsSVGSVGElementBase::)
   NS_FORWARD_NSIDOMELEMENT(nsSVGSVGElementBase::)