layout: Tie transitions to the DOM node and finish them instantly when

new styles are set.

Tying transitions to the DOM node avoids quadratic complexity when
updating them.

Finishing transitions instantly when styles are updated makes our
behavior more correct.

5 files changed, 91 insertions, 50 deletions

diff --git a/components/gfx/display_list/mod.rs b/components/gfx/display_list/mod.rs
index e87a5888ea9..621068824c4 100644
--- a/components/gfx/display_list/mod.rs
+++ b/components/gfx/display_list/mod.rs
@@ -65,11 +65,12 @@ const MIN_INDENTATION_LENGTH: usize = 4;
 /// Because the script task's GC does not trace layout, node data cannot be safely stored in layout
 /// data structures. Also, layout code tends to be faster when the DOM is not being accessed, for
 /// locality reasons. Using `OpaqueNode` enforces this invariant.
-#[derive(Clone, PartialEq, Copy, Debug, HeapSizeOf, Deserialize, Serialize)]
+#[derive(Clone, PartialEq, Copy, Debug, HeapSizeOf, Hash, Eq, Deserialize, Serialize)]
 pub struct OpaqueNode(pub uintptr_t);
 
 impl OpaqueNode {
     /// Returns the address of this node, for debugging purposes.
+    #[inline]
     pub fn id(&self) -> uintptr_t {
         let OpaqueNode(pointer) = *self;
         pointer
diff --git a/components/layout/animation.rs b/components/layout/animation.rs
index b0737538a70..e8acb3b3229 100644
--- a/components/layout/animation.rs
+++ b/components/layout/animation.rs
@@ -13,7 +13,8 @@ use layout_task::{LayoutTask, LayoutTaskData};
 use msg::constellation_msg::{AnimationState, Msg, PipelineId};
 use script::layout_interface::Animation;
 use script_traits::{ConstellationControlMsg, ScriptControlChan};
-use std::mem;
+use std::collections::HashMap;
+use std::collections::hash_map::Entry;
 use std::sync::Arc;
 use std::sync::mpsc::Sender;
 use style::animation::{GetMod, PropertyAnimation};
@@ -50,8 +51,30 @@ pub fn start_transitions_if_applicable(new_animations_sender: &Sender<Animation>
 
 /// Processes any new animations that were discovered after style recalculation.
 pub fn process_new_animations(rw_data: &mut LayoutTaskData, pipeline_id: PipelineId) {
+    let mut new_running_animations = Vec::new();
     while let Ok(animation) = rw_data.new_animations_receiver.try_recv() {
-        rw_data.running_animations.push(animation)
+        new_running_animations.push(animation)
+    }
+    if !new_running_animations.is_empty() {
+        let mut running_animations = (*rw_data.running_animations).clone();
+
+        // Expire old running animations.
+        let now = clock_ticks::precise_time_s();
+        for (_, running_animations) in running_animations.iter_mut() {
+            running_animations.retain(|running_animation| now < running_animation.end_time);
+        }
+
+        // Add new running animations.
+        for new_running_animation in new_running_animations.into_iter() {
+            match running_animations.entry(OpaqueNode(new_running_animation.node)) {
+                Entry::Vacant(entry) => {
+                    entry.insert(vec![new_running_animation]);
+                }
+                Entry::Occupied(mut entry) => entry.get_mut().push(new_running_animation),
+            }
+        }
+
+        rw_data.running_animations = Arc::new(running_animations);
     }
 
     let animation_state;
@@ -68,48 +91,42 @@ pub fn process_new_animations(rw_data: &mut LayoutTaskData, pipeline_id: Pipelin
 
 }
 
-/// Recalculates style for an animation. This does *not* run with the DOM lock held.
-pub fn recalc_style_for_animation(flow: &mut Flow, animation: &Animation) {
+/// Recalculates style for a set of animations. This does *not* run with the DOM lock held.
+pub fn recalc_style_for_animations(flow: &mut Flow,
+                                   animations: &HashMap<OpaqueNode,Vec<Animation>>) {
     let mut damage = RestyleDamage::empty();
     flow.mutate_fragments(&mut |fragment| {
-        if fragment.node.id() != animation.node {
-            return
+        if let Some(ref animations) = animations.get(&OpaqueNode(fragment.node.id())) {
+            for animation in animations.iter() {
+                let now = clock_ticks::precise_time_s();
+                let mut progress = (now - animation.start_time) / animation.duration();
+                if progress > 1.0 {
+                    progress = 1.0
+                }
+                if progress <= 0.0 {
+                    continue
+                }
+
+                let mut new_style = fragment.style.clone();
+                animation.property_animation.update(&mut *Arc::make_unique(&mut new_style),
+                                                    progress);
+                damage.insert(incremental::compute_damage(&Some(fragment.style.clone()),
+                                                          &new_style));
+                fragment.style = new_style
+            }
         }
-
-        let now = clock_ticks::precise_time_s() as f64;
-        let mut progress = (now - animation.start_time) / animation.duration();
-        if progress > 1.0 {
-            progress = 1.0
-        }
-        if progress <= 0.0 {
-            return
-        }
-
-        let mut new_style = fragment.style.clone();
-        animation.property_animation.update(&mut *Arc::make_unique(&mut new_style), progress);
-        damage.insert(incremental::compute_damage(&Some(fragment.style.clone()), &new_style));
-        fragment.style = new_style
     });
 
     let base = flow::mut_base(flow);
     base.restyle_damage.insert(damage);
     for kid in base.children.iter_mut() {
-        recalc_style_for_animation(kid, animation)
+        recalc_style_for_animations(kid, animations)
     }
 }
 
 /// Handles animation updates.
 pub fn tick_all_animations(layout_task: &LayoutTask, rw_data: &mut LayoutTaskData) {
-    let running_animations = mem::replace(&mut rw_data.running_animations, Vec::new());
-    let now = clock_ticks::precise_time_s() as f64;
-    for running_animation in running_animations.into_iter() {
-        layout_task.tick_animation(&running_animation, rw_data);
-
-        if now < running_animation.end_time {
-            // Keep running the animation if it hasn't expired.
-            rw_data.running_animations.push(running_animation)
-        }
-    }
+    layout_task.tick_animations(rw_data);
 
     let ScriptControlChan(ref chan) = layout_task.script_chan;
     chan.send(ConstellationControlMsg::TickAllAnimations(layout_task.id)).unwrap();
diff --git a/components/layout/context.rs b/components/layout/context.rs
index 601e8118cb4..b2d80110f87 100644
--- a/components/layout/context.rs
+++ b/components/layout/context.rs
@@ -126,6 +126,9 @@ pub struct SharedLayoutContext {
     /// The visible rects for each layer, as reported to us by the compositor.
     pub visible_rects: Arc<HashMap<LayerId, Rect<Au>, DefaultState<FnvHasher>>>,
 
+    /// The animations that are currently running.
+    pub running_animations: Arc<HashMap<OpaqueNode,Vec<Animation>>>,
+
     /// Why is this reflow occurring
     pub goal: ReflowGoal,
 }
diff --git a/components/layout/css/matching.rs b/components/layout/css/matching.rs
index 1d147dcdbdd..1a372a82905 100644
--- a/components/layout/css/matching.rs
+++ b/components/layout/css/matching.rs
@@ -420,7 +420,8 @@ trait PrivateMatchMethods {
                                    applicable_declarations_cache:
                                     &mut ApplicableDeclarationsCache,
                                    new_animations_sender: &Sender<Animation>,
-                                   shareable: bool)
+                                   shareable: bool,
+                                   animate_properties: bool)
                                    -> RestyleDamage;
 
     fn share_style_with_candidate_if_possible(&self,
@@ -438,8 +439,21 @@ impl<'ln> PrivateMatchMethods for LayoutNode<'ln> {
                                    applicable_declarations_cache:
                                     &mut ApplicableDeclarationsCache,
                                    new_animations_sender: &Sender<Animation>,
-                                   shareable: bool)
+                                   shareable: bool,
+                                   animate_properties: bool)
                                    -> RestyleDamage {
+        // Finish any transitions.
+        if animate_properties {
+            if let Some(ref mut style) = *style {
+                let this_opaque = self.opaque();
+                if let Some(ref animations) = layout_context.running_animations.get(&this_opaque) {
+                    for animation in animations.iter() {
+                        animation.property_animation.update(&mut *Arc::make_unique(style), 1.0);
+                    }
+                }
+            }
+        }
+
         let mut this_style;
         let cacheable;
         match parent_style {
@@ -470,11 +484,8 @@ impl<'ln> PrivateMatchMethods for LayoutNode<'ln> {
 
         // Trigger transitions if necessary. This will reset `this_style` back to its old value if
         // it did trigger a transition.
-        match *style {
-            None => {
-                // This is a newly-created node; we've nothing to transition from!
-            }
-            Some(ref style) => {
+        if animate_properties {
+            if let Some(ref style) = *style {
                 animation::start_transitions_if_applicable(new_animations_sender,
                                                            self.opaque(),
                                                            &**style,
@@ -488,7 +499,8 @@ impl<'ln> PrivateMatchMethods for LayoutNode<'ln> {
 
         // Cache the resolved style if it was cacheable.
         if cacheable {
-            applicable_declarations_cache.insert(applicable_declarations.to_vec(), this_style.clone());
+            applicable_declarations_cache.insert(applicable_declarations.to_vec(),
+                                                 this_style.clone());
         }
 
         // Write in the final style and return the damage done to our caller.
@@ -686,7 +698,8 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
                             &mut layout_data.shared_data.style,
                             applicable_declarations_cache,
                             new_animations_sender,
-                            applicable_declarations.normal_shareable);
+                            applicable_declarations.normal_shareable,
+                            true);
                         if applicable_declarations.before.len() > 0 {
                             damage = damage | self.cascade_node_pseudo_element(
                                 layout_context,
@@ -695,6 +708,7 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
                                 &mut layout_data.data.before_style,
                                 applicable_declarations_cache,
                                 new_animations_sender,
+                                false,
                                 false);
                         }
                         if applicable_declarations.after.len() > 0 {
@@ -705,6 +719,7 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
                                 &mut layout_data.data.after_style,
                                 applicable_declarations_cache,
                                 new_animations_sender,
+                                false,
                                 false);
                         }
                         layout_data.data.restyle_damage = damage;
diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs
index 001f8f42d2a..c7eab0fdb50 100644
--- a/components/layout/layout_task.rs
+++ b/components/layout/layout_task.rs
@@ -138,7 +138,7 @@ pub struct LayoutTaskData {
     pub resolved_style_response: Option<String>,
 
     /// The list of currently-running animations.
-    pub running_animations: Vec<Animation>,
+    pub running_animations: Arc<HashMap<OpaqueNode,Vec<Animation>>>,
 
     /// Receives newly-discovered animations.
     pub new_animations_receiver: Receiver<Animation>,
@@ -381,7 +381,7 @@ impl LayoutTask {
                     content_boxes_response: Vec::new(),
                     client_rect_response: Rect::zero(),
                     resolved_style_response: None,
-                    running_animations: Vec::new(),
+                    running_animations: Arc::new(HashMap::new()),
                     visible_rects: Arc::new(HashMap::with_hash_state(Default::default())),
                     new_animations_receiver: new_animations_receiver,
                     new_animations_sender: new_animations_sender,
@@ -423,6 +423,7 @@ impl LayoutTask {
             generation: rw_data.generation,
             new_animations_sender: rw_data.new_animations_sender.clone(),
             goal: goal,
+            running_animations: rw_data.running_animations.clone(),
         }
     }
 
@@ -1275,23 +1276,27 @@ impl LayoutTask {
         animation::tick_all_animations(self, &mut rw_data)
     }
 
-    pub fn tick_animation<'a>(&'a self, animation: &Animation, rw_data: &mut LayoutTaskData) {
+    pub fn tick_animations<'a>(&'a self, rw_data: &mut LayoutTaskData) {
         let reflow_info = Reflow {
             goal: ReflowGoal::ForDisplay,
             page_clip_rect: MAX_RECT,
         };
 
-        // Perform an abbreviated style recalc that operates without access to the DOM.
         let mut layout_context = self.build_shared_layout_context(&*rw_data,
                                                                   false,
                                                                   None,
                                                                   &self.url,
                                                                   reflow_info.goal);
-        let mut root_flow = (*rw_data.root_flow.as_ref().unwrap()).clone();
-        profile(time::ProfilerCategory::LayoutStyleRecalc,
-                self.profiler_metadata(),
-                self.time_profiler_chan.clone(),
-                || animation::recalc_style_for_animation(root_flow.deref_mut(), &animation));
+
+        {
+            // Perform an abbreviated style recalc that operates without access to the DOM.
+            let mut root_flow = (*rw_data.root_flow.as_ref().unwrap()).clone();
+            let animations = &*rw_data.running_animations;
+            profile(time::ProfilerCategory::LayoutStyleRecalc,
+                    self.profiler_metadata(),
+                    self.time_profiler_chan.clone(),
+                    || animation::recalc_style_for_animations(root_flow.deref_mut(), animations));
+        }
 
         self.perform_post_style_recalc_layout_passes(&reflow_info,
                                                      &mut *rw_data,