1183461 - Sort animation events before dispatch

Status: RESOLVED FIXED

(Core :: DOM: Animation, defect)

Description

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Once we start sampling animations from their timeline, the order in which we visit them is potentially random (since they're stored in a hashmap there). If we queue events then and dispatch them in the same order, the order of event dispatch will also be random. We should probably be consistent about this order, however.

At a minimum, we should sort by the timeline time of an event. That is, if we:

 .a {
    animation: anim 3s;
 }
 .b {
    animation: anim 3.01s;
 }

When we come to dispatch the animationend events, we should dispatch the event for 'a' before 'b'. That seems pretty straightforward.

If multiple elements match 'a' at the same time we should sort by document order.

If, in between the time an animation was scheduled to finish and the event was dispatched, the corresponding element was reparented, or orphaned, then the animation will be cancelled so we should be ok.

For animations within an element, we should obviously use the animation-name / transition-property order.

That would suggest what we really want to do is hold on to the Animation that created the event and sort based on its priority (i.e. the same ordering used for returning animations from document.timeline.getAnimations()).

Note that this sorting should occur before we begin dispatch so we don't need to worry about animations disappearing or changing their priority after we start dispatch.

A further question is whether the dispatch of transitions and animations should be interleaved. That is, if an animation finished before a transition, should we dispatch the animation first?

I think it's probably ok for them to *not* be interleaved for the time being as long as we sort both lists at once.

Comment 1

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: WIP patch

WIP patch, still needs some work

Comment 2

[Brian Birtles (:birtles, Feb 26~ parental leave)]

A few things I need to work out:
* Need to add sorting based on animation-name / transition-property
* Need to work out if it's easier just to store the Animation on the event (probably is?)
* "I think it's probably ok for them to *not* be interleaved for the time being as long as we sort both lists at once." -- need to work out how to sort both lists at once before beginning dispatch

Comment 3

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: WIP patch v2

Addressed the following from comment 2:
* Need to add sorting based on animation-name / transition-property

Comment 4

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: WIP patch v3

Fix remaining issues

Comment 5

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Daniel, I hope you don't mind reviewing this? Otherwise, I think heycam or dbaron would be suitable reviewers if you're busy.

Comment 6

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 1 - Move InitialAdvance to CSSAnimation

Currently we define a helper method, InitialAdvance, on KeyframeEffectReadOnly.
However, this method is only used for filling out the elapsedTime member of
AnimationEvents (which are generated by CSS animations). This patch moves this
method to CSSAnimation since it is unneeded for other types of Animations.

Comment 7

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 2 - Reorder the parameters to EventInfo constructors

This patch lines up the parameters of AnimationEventInfo and
TransitionEventInfo constructors so that they are more logical and consistent.
Specifically, it groups the element and pseudo type together since they
form a logical pair denoting the event target. For AnimationEventInfo this
patch also places the type of event before the common event parameters since
the event type seems to be more significant.

This patch also performs some miscelleaneous housekeeping: removing some
unnecessary namespace prefixes, whitespace fixes, and making
TransitionEventInfo use the same concrete type to store the target element
as AnimationEventInfo (dom::Element instead of nsIContent).

Comment 8

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 3 - Add Animation::AnimationTimeToTimeStamp

This patch adds a utility method to Animation which takes a time in the
same time space as "current time", i.e. "animation time" and convert it to
a TimeStamp. Subsequent patches in this series will use this method to
take the time when an event was scheduled to occur and convert it to a
TimeStamp so it can be compared with other event times. This allows us to
dispatch events in the order they would have fired given an infinitely
frequent sample rate.

Comment 9

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 4 - Add CSSAnimation::ElapsedTimeToTimeStamp

The elapsedTime member reported on AnimationEvents measures the time from
the *end* of the delay phase (i.e. the beginning of the active interval) to
when the event occurred. However, the AnimationTimeToTimeStamp method
introduced in the previous patch expects a time relative to the animation's
start time (i.e. the *start* of the delay phase). This patch adds a method
that performs the necessary conversion from an elapsedTime to an animation
time before calling AnimationTimeToTimeStamp. It also provides extra handling
for cases such as when the animation's start time has not yet been resolved or
when animation effect has disappeared.

Comment 10

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 5 - Store event TimeStamp along with event info

Comment 11

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 6 - Store the generating animation on the event

In order to sort between events that have the same timestamp we use the
sort order of the corresponding animations so we need to store a pointer
to the animation along with the event.

Comment 12

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 7 - Add EventInfoComparator and sort events

Comment 13

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 8 - Add tests for event order dispatch

Comment 14

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 8 - Add tests for event order dispatch

Comment 15

[Cameron McCormack (:heycam)]

Comment on attachment 8655292 [details] [diff] [review]
part 1 - Move InitialAdvance to CSSAnimation

Review of attachment 8655292 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/style/nsAnimationManager.h
@@ +166,5 @@
>                                          "before a CSS animation is destroyed");
>    }
>    virtual CommonAnimationManager* GetAnimationManager() const override;
>  
> +  // Returns the duration from the start the animation's source effect's active

s/start/start of/ while you're moving and rewording.

Comment 16

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Looks like part 7 breaks these tests:
dom/animation/test/css-animations/test_animation-currenttime.html
dom/animation/test/css-animations/test_animation-starttime.html

https://treeherder.mozilla.org/#/jobs?repo=try&revision=09b4808845a6

Comment 17

[Cameron McCormack (:heycam)]

Comment on attachment 8655298 [details] [diff] [review]
part 7 - Add EventInfoComparator and sort events

Review of attachment 8655298 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/style/AnimationCommon.h
@@ +521,5 @@
>  public:
>    void QueueEvent(EventInfo&& aEventInfo)
>    {
> +    mPendingEvents.InsertElementSorted(Forward<EventInfo>(aEventInfo),
> +                                       EventInfoComparator());

Would it be better to sort the array in DispatchEvents instead?  Then we could avoid potentially O(N^2) time if we happen to queue events in reverse time order.  (Not sure how likely that is to happen, or whether mPendingEvents will get big enough for that to matter.)

@@ +559,5 @@
>    }
>    void Unlink() { mPendingEvents.Clear(); }
>  
>  protected:
> +  class EventInfoComparator {

The style guide doesn't talk about nested classes explicitly, but probably the same "brace on next line" rule applies.

@@ +572,5 @@
> +    {
> +      if (a.mTimeStamp != b.mTimeStamp) {
> +        // Null timestamps sort last
> +        if (a.mTimeStamp.IsNull() || b.mTimeStamp.IsNull()) {
> +          return b.mTimeStamp.IsNull();

Is this right?  Shouldn't we be returning false if both a and b's timestamp are null?

Comment 18

[Brian Birtles (:birtles, Feb 26~ parental leave)]

(In reply to Cameron McCormack (:heycam) from comment #17)
> >  public:
> >    void QueueEvent(EventInfo&& aEventInfo)
> >    {
> > +    mPendingEvents.InsertElementSorted(Forward<EventInfo>(aEventInfo),
> > +                                       EventInfoComparator());
> 
> Would it be better to sort the array in DispatchEvents instead?  Then we
> could avoid potentially O(N^2) time if we happen to queue events in reverse
> time order.  (Not sure how likely that is to happen, or whether
> mPendingEvents will get big enough for that to matter.)

Yes, I think so. I'll rework it to do that.

I did that initially but I was concerned that by the time we hit DispatchEvents, if the document structure has changed we'll end up with a different sort order. But thinking about it a bit more, it's probably equally as correct to use the document order at the time of dispatch.

The other concern was that we dispatch the set of transition events first, then the set of animation events. So if any of the transition event handlers rearrange the document structure we'd end up with a different order again.

I think we should probably add an explicit "sort events" step and do that for both transitions and animations at once, *then* dispatch both. That's going to require reworking the code in nsRefreshDriver a bit, however.

> @@ +572,5 @@
> > +    {
> > +      if (a.mTimeStamp != b.mTimeStamp) {
> > +        // Null timestamps sort last
> > +        if (a.mTimeStamp.IsNull() || b.mTimeStamp.IsNull()) {
> > +          return b.mTimeStamp.IsNull();
> 
> Is this right?  Shouldn't we be returning false if both a and b's timestamp
> are null?

I think it's right. If a and b both have null timestamps we should sort based on their animations (i.e. run the code for when the timestamps are not equal).

Comment 19

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Comment on attachment 8655298 [details] [diff] [review]
part 7 - Add EventInfoComparator and sort events

Cancelling review request while I rework this.

Comment 20

[Cameron McCormack (:heycam)]

(In reply to Brian Birtles (:birtles) from comment #18)
> I think it's right. If a and b both have null timestamps we should sort
> based on their animations (i.e. run the code for when the timestamps are not
> equal).

Ah, because we already checked for equality a few lines up.  (Was thinking that this condition here also captured when both were null.)

Comment 21

[Cameron McCormack (:heycam)]

Comment on attachment 8655300 [details] [diff] [review]
part 8 - Add tests for event order dispatch

Review of attachment 8655300 [details] [diff] [review]:
-----------------------------------------------------------------

Just a couple of nits/suggestions...

::: layout/style/test/test_animations_event_order.html
@@ +18,5 @@
> +    src="/tests/SimpleTest/SimpleTest.js"></script>
> +  <!-- We still need animation_utils.js for advance_clock -->
> +  <script type="application/javascript" src="animation_utils.js"></script>
> +  <link rel="stylesheet" type="text/css" href="/tests/SimpleTest/test.css"/>
> +  <style type="text/css">

FWIW type="text/css" is implicit on <style>.

@@ +45,5 @@
> +
> +[ 'animationstart',
> +  'animationiteration',
> +  'animationend',
> +  'transitionend']

Nit: space before the "]" to match the one after the "["?

@@ +55,5 @@
> +function checkEventOrder() {
> +  // Argument format:
> +  // Arguments     = ExpectedEvent*, desc
> +  // ExpectedEvent =
> +  //       [ target|animationName|transitionProperty, [pseudo,] message ]

I was confused for a second by the fact that the outer brackets indicate "array" but the inner brackets mean "optional"!

@@ +56,5 @@
> +  // Argument format:
> +  // Arguments     = ExpectedEvent*, desc
> +  // ExpectedEvent =
> +  //       [ target|animationName|transitionProperty, [pseudo,] message ]
> +  var expectedEvents  = [].slice.call(arguments, 0, -1);

In case you're not aware, you could avoid the "arguments isn't a real array" problem by doing:

  function checkEventOrder(...args) {
    var expectedEvents = args.slice(0, -1);
    var desc           = args[args.length - 1];

which is maybe ε clearer than doing [].slice.call. :-)

Comment 22

[Brian Birtles (:birtles, Feb 26~ parental leave)]

(In reply to Brian Birtles (:birtles) from comment #16)
> Looks like part 7 breaks these tests:
> dom/animation/test/css-animations/test_animation-currenttime.html
> dom/animation/test/css-animations/test_animation-starttime.html
> 
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=09b4808845a6

I'm pretty sure what was happening here is that in these tests we hit the case where we generate a start and end event simultaneously and we *also* have yet to resolve the start time, hence we end up using the refresh driver time as the timestamp for both events. When we go to sort the events, however, we use nsTArray::Sort which is not a stable sort so sometimes we would end up returning the end event first.

We can solve this by either adjusting the comparison function to sort start events before end events when the timestamps and animation objects match. Alternatively, we can just use a stable sort.

A stable sort seems preferable since it *may* be possible to generate an end event followed by a start event where the event timestamp ends up the same. I'm not sure, but it seems feasible. Also, I notice we're using stable_sort elsewhere in the codebase (nsGridContainerFrame.cpp, APZ etc.) so I've just gone ahead and used that for now with a comment pointing to the bug where we plan to implement a stable sort (bug 1147091).

Comment 23

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 7 - Add EventInfoComparator and sort events

This patch also reworks the dispatch of events in nsRefreshDriver. Previously
the refresh driver would dispatch the transition events for all subdocuments
then the animation events. This arrangement is complicated and not obviously
necessary. This patch simplifies this arrangement by dispatching transition
events and animation events for each document before proceeding to
subdocuments.

Comment 24

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Comment on attachment 8656400 [details] [diff] [review]
part 7 - Add EventInfoComparator and sort events

Cancelling review request. It still seems to fail on try but I can't reproduce the failure locally.

Comment 25

[Brian Birtles (:birtles, Feb 26~ parental leave)]

I'm still not sure why I'm getting intermittent failures on try only and only on Linux.

A few things I notice, however:
* the elapsedTime (used to sort CSS animation events) doesn't seem to be inverted when we enter or cross the active interval from the RHS
* if elapsedTime *were* to accurately reflect where we entered the interval from and we sorted on that we'd probably get the wrong result for when we seekbackwards (when the play backwards with a negative playbackRate I think it would be ok)
* perhaps seeking should behave differently?

Comment 26

[Brian Birtles (:birtles, Feb 26~ parental leave)]

(In reply to Brian Birtles (:birtles) from comment #25)
> I'm still not sure why I'm getting intermittent failures on try only and
> only on Linux.

It looks like we're hitting an overflow condition inside TimeStamp which causes us to end up with nonsense TimeStamps, hence the sorting doesn't work.

Comment 27

[Brian Birtles (:birtles, Feb 26~ parental leave)]

To be more specific, TimeStamp::operator+(TimeDuration&) and friends don't check for the case when the addition/subtraction wraps backwards by going backwards past the origin of the monotonic clock which, for Linux, is "some unspecified starting point".[1]

[1] http://linux.die.net/man/3/clock_gettime

Comment 28

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: part 7 - Add EventInfoComparator and sort events

This patch also reworks the dispatch of events in nsRefreshDriver. Previously
the refresh driver would dispatch the transition events for all subdocuments
then the animation events. This arrangement is complicated and not obviously
necessary. This patch simplifies this arrangement by dispatching transition
events and animation events for each document before proceeding to
subdocuments.

Comment 29

[Cameron McCormack (:heycam)]

Comment on attachment 8661065 [details] [diff] [review]
part 7 - Add EventInfoComparator and sort events

Review of attachment 8661065 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/base/nsRefreshDriver.cpp
@@ +1335,5 @@
>    }
>  
>    nsCOMPtr<nsIDocument> kungFuDeathGrip(aDocument);
>  
> +  context->TransitionManager()->SortEvents();

Since the Transition/AnimationManager will sort events anyway when you call DispatchEvents, is it necessary to sort them here?  Is there an observable difference?

::: layout/style/AnimationCommon.h
@@ +550,4 @@
>      for (EventInfo& info : events) {
>        EventDispatcher::Dispatch(info.mElement, aPresContext, &info.mEvent);
>  
>        if (!aPresContext) {

This function looks like it's written with the expectation that EventDispatcher::Dispatch can set its second argument to nullptr, but that doesn't look like the case (it's not a reference type, at least on mozilla-central).  Am I missing something?

@@ +592,5 @@
> +      return mAnimationComparator.LessThan(a.mAnimation, b.mAnimation);
> +    }
> +
> +  private:
> +    AnimationPtrComparator<nsRefPtr<dom::Animation>> mAnimationComparator;

(It might not make any difference, but since this doesn't have a constructor that does anything, I think it would be safe to declare locally within operator().)

Comment 30

[Brian Birtles (:birtles, Feb 26~ parental leave)]

(In reply to Cameron McCormack (:heycam) from comment #29)
> ::: layout/base/nsRefreshDriver.cpp
> @@ +1335,5 @@
> >    }
> >  
> >    nsCOMPtr<nsIDocument> kungFuDeathGrip(aDocument);
> >  
> > +  context->TransitionManager()->SortEvents();
> 
> Since the Transition/AnimationManager will sort events anyway when you call
> DispatchEvents, is it necessary to sort them here?  Is there an observable
> difference?

Yes. The sorting is based on document position. When we dispatch events we call out into script which could perform document surgery. As a result, we want to sort both lists with the same document state before we call into script.

> ::: layout/style/AnimationCommon.h
> @@ +550,4 @@
> >      for (EventInfo& info : events) {
> >        EventDispatcher::Dispatch(info.mElement, aPresContext, &info.mEvent);
> >  
> >        if (!aPresContext) {
> 
> This function looks like it's written with the expectation that
> EventDispatcher::Dispatch can set its second argument to nullptr, but that
> doesn't look like the case (it's not a reference type, at least on
> mozilla-central).  Am I missing something?

This method takes a reference to the pres context pointer on the corresponding manager. During event dispatch something could destroy that pres context so we need to check after each call to Dispatch that the pres context is still around.

> @@ +592,5 @@
> > +      return mAnimationComparator.LessThan(a.mAnimation, b.mAnimation);
> > +    }
> > +
> > +  private:
> > +    AnimationPtrComparator<nsRefPtr<dom::Animation>> mAnimationComparator;
> 
> (It might not make any difference, but since this doesn't have a constructor
> that does anything, I think it would be safe to declare locally within
> operator().)

Yes, agreed.

Comment 31

[Cameron McCormack (:heycam)]

(In reply to Brian Birtles (:birtles) from comment #30)
> This method takes a reference to the pres context pointer on the
> corresponding manager. During event dispatch something could destroy that
> pres context so we need to check after each call to Dispatch that the pres
> context is still around.

Thanks, I see now.

Comment 32

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/b070f90f3cde
https://hg.mozilla.org/integration/mozilla-inbound/rev/52305b561896
https://hg.mozilla.org/integration/mozilla-inbound/rev/2718828e8f44
https://hg.mozilla.org/integration/mozilla-inbound/rev/a6651565f1ce
https://hg.mozilla.org/integration/mozilla-inbound/rev/aa1792f2af78
https://hg.mozilla.org/integration/mozilla-inbound/rev/e3d6aa401ec0
https://hg.mozilla.org/integration/mozilla-inbound/rev/95e0fae6c3e2
https://hg.mozilla.org/integration/mozilla-inbound/rev/5d135736c0a1

Comment 33

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/b070f90f3cde
https://hg.mozilla.org/mozilla-central/rev/52305b561896
https://hg.mozilla.org/mozilla-central/rev/2718828e8f44
https://hg.mozilla.org/mozilla-central/rev/a6651565f1ce
https://hg.mozilla.org/mozilla-central/rev/aa1792f2af78
https://hg.mozilla.org/mozilla-central/rev/e3d6aa401ec0
https://hg.mozilla.org/mozilla-central/rev/95e0fae6c3e2
https://hg.mozilla.org/mozilla-central/rev/5d135736c0a1