auto merge of #3809 : mrobinson/servo/display-list-optimization, r=pcwalton

Instead of creating a display list for the entire page, only create one
for an area that expands around the viewport. On my machine this makes
incremental layout of http://timecube.com 50% faster.

4 files changed, 87 insertions, 25 deletions

diff --git a/components/script/dom/bindings/trace.rs b/components/script/dom/bindings/trace.rs
index 94d05e4c477..1690cb5ddad 100644
--- a/components/script/dom/bindings/trace.rs
+++ b/components/script/dom/bindings/trace.rs
@@ -28,37 +28,37 @@
 //! a datatype.
 
 use dom::bindings::js::JS;
-use dom::bindings::utils::{Reflectable, Reflector};
+use dom::bindings::utils::{Reflectable, Reflector, WindowProxyHandler};
+use dom::node::{Node, TrustedNodeAddress};
+
+use collections::hash::{Hash, Hasher};
+use geom::rect::Rect;
+use html5ever::tree_builder::QuirksMode;
+use http::headers::request::HeaderCollection as RequestHeaderCollection;
+use http::headers::response::HeaderCollection as ResponseHeaderCollection;
+use http::method::Method;
 use js::jsapi::{JSObject, JSTracer, JS_CallTracer, JSTRACE_OBJECT};
 use js::jsval::JSVal;
-
+use js::rust::Cx;
+use layout_interface::{LayoutRPC, LayoutChan};
 use libc;
-use std::rc::Rc;
-use std::cell::{Cell, RefCell};
-
-use url::Url;
 use msg::constellation_msg::{PipelineId, SubpageId, WindowSizeData};
 use net::image_cache_task::ImageCacheTask;
 use script_traits::ScriptControlChan;
-use std::collections::hashmap::HashMap;
-use collections::hash::{Hash, Hasher};
-use style::PropertyDeclarationBlock;
-use std::comm::{Receiver, Sender};
-use string_cache::{Atom, Namespace};
-use js::rust::Cx;
-use http::headers::response::HeaderCollection as ResponseHeaderCollection;
-use http::headers::request::HeaderCollection as RequestHeaderCollection;
-use http::method::Method;
-use std::io::timer::Timer;
 use script_traits::UntrustedNodeAddress;
 use servo_msg::compositor_msg::ScriptListener;
 use servo_msg::constellation_msg::ConstellationChan;
 use servo_util::smallvec::{SmallVec1, SmallVec};
 use servo_util::str::LengthOrPercentageOrAuto;
-use layout_interface::{LayoutRPC, LayoutChan};
-use dom::node::{Node, TrustedNodeAddress};
-use dom::bindings::utils::WindowProxyHandler;
-use html5ever::tree_builder::QuirksMode;
+use std::cell::{Cell, RefCell};
+use std::collections::hashmap::HashMap;
+use std::comm::{Receiver, Sender};
+use std::io::timer::Timer;
+use std::rc::Rc;
+use string_cache::{Atom, Namespace};
+use style::PropertyDeclarationBlock;
+use url::Url;
+
 
 /// A trait to allow tracing (only) DOM objects.
 pub trait JSTraceable {
@@ -200,6 +200,7 @@ no_jsmanaged_fields!(uint, u8, u16, u32, u64)
 no_jsmanaged_fields!(int, i8, i16, i32, i64)
 no_jsmanaged_fields!(Sender<T>)
 no_jsmanaged_fields!(Receiver<T>)
+no_jsmanaged_fields!(Rect<T>)
 no_jsmanaged_fields!(ImageCacheTask, ScriptControlChan)
 no_jsmanaged_fields!(Atom, Namespace, Timer)
 no_jsmanaged_fields!(PropertyDeclarationBlock)
diff --git a/components/script/layout_interface.rs b/components/script/layout_interface.rs
index 2cf64f961fb..95b422e18eb 100644
--- a/components/script/layout_interface.rs
+++ b/components/script/layout_interface.rs
@@ -109,6 +109,8 @@ pub struct Reflow {
     pub id: uint,
     /// The type of query if any to perform during this reflow.
     pub query_type: ReflowQueryType,
+    ///  A clipping rectangle for the page, an enlarged rectangle containing the viewport.
+    pub page_clip_rect: Rect<Au>,
 }
 
 /// Encapsulates a channel to the layout task.
diff --git a/components/script/page.rs b/components/script/page.rs
index 4e87ebe9050..b150804b5d3 100644
--- a/components/script/page.rs
+++ b/components/script/page.rs
@@ -19,19 +19,21 @@ use layout_interface::{
 };
 use script_traits::{UntrustedNodeAddress, ScriptControlChan};
 
-use geom::{Point2D, Rect};
+use geom::{Point2D, Rect, Size2D};
 use js::rust::Cx;
 use servo_msg::compositor_msg::PerformingLayout;
 use servo_msg::compositor_msg::ScriptListener;
 use servo_msg::constellation_msg::{ConstellationChan, WindowSizeData};
 use servo_msg::constellation_msg::{PipelineId, SubpageId};
 use servo_net::resource_task::ResourceTask;
-use servo_util::geometry::Au;
+use servo_util::geometry::{Au, MAX_RECT};
+use servo_util::geometry;
 use servo_util::str::DOMString;
 use servo_util::smallvec::{SmallVec1, SmallVec};
 use std::cell::Cell;
 use std::comm::{channel, Receiver, Empty, Disconnected};
 use std::mem::replace;
+use std::num::abs;
 use std::rc::Rc;
 use url::Url;
 
@@ -98,6 +100,10 @@ pub struct Page {
 
     /// Number of unnecessary potential reflows that were skipped since the last reflow
     pub avoided_reflows: Cell<int>,
+
+    /// An enlarged rectangle around the page contents visible in the viewport, used
+    /// to prevent creating display list items for content that is far away from the viewport.
+    pub page_clip_rect: Cell<Rect<Au>>,
 }
 
 pub struct PageIterator {
@@ -164,6 +170,7 @@ impl Page {
             damaged: Cell::new(false),
             pending_reflows: Cell::new(0),
             avoided_reflows: Cell::new(0),
+            page_clip_rect: Cell::new(MAX_RECT),
         }
     }
 
@@ -236,6 +243,49 @@ impl Page {
         }
         None
     }
+
+    fn should_move_clip_rect(&self, clip_rect: Rect<Au>, new_viewport: Rect<f32>) -> bool{
+        let clip_rect = Rect(Point2D(geometry::to_frac_px(clip_rect.origin.x) as f32,
+                                        geometry::to_frac_px(clip_rect.origin.y) as f32),
+                                Size2D(geometry::to_frac_px(clip_rect.size.width) as f32,
+                                       geometry::to_frac_px(clip_rect.size.height) as f32));
+
+        // We only need to move the clip rect if the viewport is getting near the edge of
+        // our preexisting clip rect. We use half of the size of the viewport as a heuristic
+        // for "close."
+        static VIEWPORT_SCROLL_MARGIN_SIZE: f32 = 0.5;
+        let viewport_scroll_margin = new_viewport.size * VIEWPORT_SCROLL_MARGIN_SIZE;
+
+        abs(clip_rect.origin.x - new_viewport.origin.x) <= viewport_scroll_margin.width ||
+        abs(clip_rect.max_x() - new_viewport.max_x()) <= viewport_scroll_margin.width ||
+        abs(clip_rect.origin.y - new_viewport.origin.y) <= viewport_scroll_margin.height ||
+        abs(clip_rect.max_y() - new_viewport.max_y()) <= viewport_scroll_margin.height
+    }
+
+    pub fn set_page_clip_rect_with_new_viewport(&self, viewport: Rect<f32>) -> bool {
+        // We use a clipping rectangle that is five times the size of the of the viewport,
+        // so that we don't collect display list items for areas too far outside the viewport,
+        // but also don't trigger reflows every time the viewport changes.
+        static VIEWPORT_EXPANSION: f32 = 2.0; // 2 lengths on each side plus original length is 5 total.
+        let proposed_clip_rect = geometry::f32_rect_to_au_rect(
+            viewport.inflate(viewport.size.width * VIEWPORT_EXPANSION,
+            viewport.size.height * VIEWPORT_EXPANSION));
+        let clip_rect = self.page_clip_rect.get();
+        if proposed_clip_rect == clip_rect {
+            return false;
+        }
+
+        let had_clip_rect = clip_rect != MAX_RECT;
+        if had_clip_rect && !self.should_move_clip_rect(clip_rect, viewport) {
+            return false;
+        }
+
+        self.page_clip_rect.set(proposed_clip_rect);
+
+        // If we didn't have a clip rect, the previous display doesn't need rebuilding
+        // because it was built for infinite clip (MAX_RECT).
+        had_clip_rect
+    }
 }
 
 impl Iterator<Rc<Page>> for PageIterator {
@@ -375,6 +425,7 @@ impl Page {
                     script_join_chan: join_chan,
                     id: last_reflow_id.get(),
                     query_type: query_type,
+                    page_clip_rect: self.page_clip_rect.get(),
                 };
 
                 let LayoutChan(ref chan) = self.layout_chan;
diff --git a/components/script/script_task.rs b/components/script/script_task.rs
index b234efef6c3..5630a9763b9 100644
--- a/components/script/script_task.rs
+++ b/components/script/script_task.rs
@@ -40,9 +40,9 @@ use devtools_traits::{DevtoolScriptControlMsg, EvaluateJS, EvaluateJSReply, GetD
 use devtools_traits::{GetChildren, GetLayout};
 use script_traits::{CompositorEvent, ResizeEvent, ReflowEvent, ClickEvent, MouseDownEvent};
 use script_traits::{MouseMoveEvent, MouseUpEvent, ConstellationControlMsg, ScriptTaskFactory};
-use script_traits::{ResizeMsg, AttachLayoutMsg, LoadMsg, SendEventMsg, ResizeInactiveMsg};
-use script_traits::{ExitPipelineMsg, NewLayoutInfo, OpaqueScriptLayoutChannel, ScriptControlChan};
-use script_traits::{ReflowCompleteMsg, UntrustedNodeAddress};
+use script_traits::{ResizeMsg, AttachLayoutMsg, LoadMsg, ViewportMsg, SendEventMsg};
+use script_traits::{ResizeInactiveMsg, ExitPipelineMsg, NewLayoutInfo, OpaqueScriptLayoutChannel};
+use script_traits::{ScriptControlChan, ReflowCompleteMsg, UntrustedNodeAddress};
 use servo_msg::compositor_msg::{FinishedLoading, LayerId, Loading};
 use servo_msg::compositor_msg::{ScriptListener};
 use servo_msg::constellation_msg::{ConstellationChan, LoadCompleteMsg, LoadUrlMsg, NavigationDirection};
@@ -495,6 +495,13 @@ impl ScriptTask {
                     pending.push_all_move(node_addresses);
                     needs_reflow.insert(id);
                 }
+                FromConstellation(ViewportMsg(id, rect)) => {
+                    let mut page = self.page.borrow_mut();
+                    let inner_page = page.find(id).expect("Page rect message sent to nonexistent pipeline");
+                    if inner_page.set_page_clip_rect_with_new_viewport(rect) {
+                        needs_reflow.insert(id);
+                    }
+                }
                 _ => {
                     sequential.push(event);
                 }
@@ -530,6 +537,7 @@ impl ScriptTask {
                 FromConstellation(ReflowCompleteMsg(id, reflow_id)) => self.handle_reflow_complete_msg(id, reflow_id),
                 FromConstellation(ResizeInactiveMsg(id, new_size)) => self.handle_resize_inactive_msg(id, new_size),
                 FromConstellation(ExitPipelineMsg(id)) => if self.handle_exit_pipeline_msg(id) { return false },
+                FromConstellation(ViewportMsg(..)) => fail!("should have handled ViewportMsg already"),
                 FromScript(ExitWindowMsg(id)) => self.handle_exit_window_msg(id),
                 FromConstellation(ResizeMsg(..)) => fail!("should have handled ResizeMsg already"),
                 FromScript(XHRProgressMsg(addr, progress)) => XMLHttpRequest::handle_progress(addr, progress),