Auto merge of #14312 - asajeffrey:script-discard-documents, r=cbrewster

Implement discarding Document objects to reclaim space.

<!-- Please describe your changes on the following line: -->

This PR implements document discarding. Active documents are kept alive strongly, but inactive documents are only kept alive weakly. When a document is GCd, it is marked as discarded, and if it is every reactivated, a reload of the URL is triggered.

Note that this PR is pretty aggressive about discarding, and can any inactive document (other than those being kept alive by other same-origin pipelines). We might want to damp it down a bit.

Also note that this interacts with browser.html in that the reloading triggered by reactivating a document triggers mozbrowser events.

To test this, I added a `-Zdiscard-inactive-documents` debug flag, which discards all inactive documents, even ones which are reachable through other same-origin pipelines.

---
<!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `__` with appropriate data: -->
- [X] `./mach build -d` does not report any errors
- [X] `./mach test-tidy` does not report any errors
- [X] These changes fix #14262.
- [X] These changes do not require tests because we should be able to use the existing tests with `-Zdiscard-inactive-documents`.

<!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. -->

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/14312)
<!-- Reviewable:end -->

8 files changed, 307 insertions, 219 deletions

diff --git a/components/config/opts.rs b/components/config/opts.rs
index a59cd56f0d7..ea1173c6443 100644
--- a/components/config/opts.rs
+++ b/components/config/opts.rs
@@ -68,6 +68,9 @@ pub struct Opts {
 
     pub output_file: Option<String>,
 
+    /// How much session history to keep in each tab.
+    pub max_session_history: usize,
+
     /// Replace unpaires surrogates in DOM strings with U+FFFD.
     /// See https://github.com/servo/servo/issues/6564
     pub replace_surrogates: bool,
@@ -518,6 +521,7 @@ pub fn default_opts() -> Opts {
         userscripts: None,
         user_stylesheets: Vec::new(),
         output_file: None,
+        max_session_history: 16,
         replace_surrogates: false,
         gc_profile: false,
         load_webfonts_synchronously: false,
@@ -611,6 +615,7 @@ pub fn from_cmdline_args(args: &[String]) -> ArgumentParsingResult {
                 "Probability of randomly closing a pipeline (for testing constellation hardening).",
                 "0.0");
     opts.optopt("", "random-pipeline-closure-seed", "A fixed seed for repeatbility of random pipeline closure.", "");
+    opts.optopt("", "max-session-history", "Maximum amount of session history to store in each tab.", "16");
     opts.optmulti("Z", "debug",
                   "A comma-separated string of debug options. Pass help to show available options.", "");
     opts.optflag("h", "help", "Print this message");
@@ -779,6 +784,10 @@ pub fn from_cmdline_args(args: &[String]) -> ArgumentParsingResult {
         }
     };
 
+    let max_session_history = opt_match.opt_str("max-session-history").map(|max| {
+        max.parse().unwrap_or_else(|err| args_fail(&format!("Error parsing option: --max-session-history ({})", err)))
+    }).unwrap_or(16);
+
     if opt_match.opt_present("M") {
         MULTIPROCESS.store(true, Ordering::SeqCst)
     }
@@ -820,6 +829,7 @@ pub fn from_cmdline_args(args: &[String]) -> ArgumentParsingResult {
         userscripts: opt_match.opt_default("userscripts", ""),
         user_stylesheets: user_stylesheets,
         output_file: opt_match.opt_str("o"),
+        max_session_history: max_session_history,
         replace_surrogates: debug_options.replace_surrogates,
         gc_profile: debug_options.gc_profile,
         load_webfonts_synchronously: debug_options.load_webfonts_synchronously,
diff --git a/components/constellation/constellation.rs b/components/constellation/constellation.rs
index 87c555ac9aa..f5a5983fa9b 100644
--- a/components/constellation/constellation.rs
+++ b/components/constellation/constellation.rs
@@ -75,7 +75,7 @@ use devtools_traits::{ChromeToDevtoolsControlMsg, DevtoolsControlMsg};
 use euclid::scale_factor::ScaleFactor;
 use euclid::size::{Size2D, TypedSize2D};
 use event_loop::EventLoop;
-use frame::{Frame, FrameChange, FrameTreeIterator, FullFrameTreeIterator};
+use frame::{Frame, FrameChange, FrameState, FrameTreeIterator, FullFrameTreeIterator};
 use gfx::font_cache_thread::FontCacheThread;
 use gfx_traits::Epoch;
 use ipc_channel::ipc::{self, IpcSender};
@@ -608,7 +608,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             .map(|pipeline| pipeline.visible);
 
         let prev_visibility = self.frames.get(&frame_id)
-            .and_then(|frame| self.pipelines.get(&frame.current.pipeline_id))
+            .and_then(|frame| self.pipelines.get(&frame.pipeline_id))
             .map(|pipeline| pipeline.visible)
             .or(parent_visibility);
 
@@ -685,16 +685,16 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
     }
 
     /// The joint session future is the merge of the session future of every
-    /// frame in the frame tree, sorted reverse chronologically.
-    fn joint_session_future(&self, frame_id_root: FrameId) -> Vec<(Instant, FrameId, PipelineId)> {
-        let mut future = vec!();
-        for frame in self.full_frame_tree_iter(frame_id_root) {
-            future.extend(frame.next.iter().map(|entry| (entry.instant, entry.frame_id, entry.pipeline_id)));
-        }
+    /// frame in the frame tree, sorted chronologically.
+    fn joint_session_future<'a>(&'a self, frame_id_root: FrameId) -> impl Iterator<Item=FrameState> {
+        let mut future: Vec<FrameState> = self.full_frame_tree_iter(frame_id_root)
+            .flat_map(|frame| frame.next.iter().cloned())
+            .collect();
 
-        // reverse sorting
-        future.sort_by(|a, b| b.cmp(a));
-        future
+        // Sort the joint session future by the timestamp that the pipeline was navigated to
+        // in chronological order
+        future.sort_by(|a, b| a.instant.cmp(&b.instant));
+        future.into_iter()
     }
 
     /// Is the joint session future empty?
@@ -704,19 +704,20 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
     }
 
     /// The joint session past is the merge of the session past of every
-    /// frame in the frame tree, sorted chronologically.
-    fn joint_session_past(&self, frame_id_root: FrameId) -> Vec<(Instant, FrameId, PipelineId)> {
-        let mut past = vec!();
-        for frame in self.full_frame_tree_iter(frame_id_root) {
-            let mut prev_instant = frame.current.instant;
-            for entry in frame.prev.iter().rev() {
-                past.push((prev_instant, entry.frame_id, entry.pipeline_id));
-                prev_instant = entry.instant;
-            }
-        }
+    /// frame in the frame tree, sorted reverse chronologically.
+    fn joint_session_past<'a>(&self, frame_id_root: FrameId) -> impl Iterator<Item=FrameState> {
+        let mut past: Vec<(Instant, FrameState)> = self.full_frame_tree_iter(frame_id_root)
+            .flat_map(|frame| frame.prev.iter().rev().scan(frame.instant, |prev_instant, entry| {
+                let instant = *prev_instant;
+                *prev_instant = entry.instant;
+                Some((instant, entry.clone()))
+            }))
+            .collect();
 
-        past.sort();
-        past
+        // Sort the joint session past by the timestamp that the pipeline was navigated from
+        // in reverse chronological order
+        past.sort_by(|a, b| b.0.cmp(&a.0));
+        past.into_iter().map(|(_, entry)| entry)
     }
 
     /// Is the joint session past empty?
@@ -726,8 +727,8 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
     }
 
     /// Create a new frame and update the internal bookkeeping.
-    fn new_frame(&mut self, frame_id: FrameId, pipeline_id: PipelineId) {
-        let frame = Frame::new(frame_id, pipeline_id);
+    fn new_frame(&mut self, frame_id: FrameId, pipeline_id: PipelineId, url: ServoUrl) {
+        let frame = Frame::new(frame_id, pipeline_id, url);
         self.frames.insert(frame_id, frame);
 
         // If a child frame, add it to the parent pipeline.
@@ -1228,7 +1229,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
         // Notify the browser chrome that the pipeline has failed
         self.trigger_mozbrowsererror(top_level_frame_id, reason, backtrace);
 
-        let pipeline_id = self.frames.get(&top_level_frame_id).map(|frame| frame.current.pipeline_id);
+        let pipeline_id = self.frames.get(&top_level_frame_id).map(|frame| frame.pipeline_id);
         let pipeline_url = pipeline_id.and_then(|id| self.pipelines.get(&id).map(|pipeline| pipeline.url.clone()));
         let parent_info = pipeline_id.and_then(|id| self.pipelines.get(&id).and_then(|pipeline| pipeline.parent_info));
         let window_size = pipeline_id.and_then(|id| self.pipelines.get(&id).and_then(|pipeline| pipeline.size));
@@ -1246,14 +1247,15 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
         warn!("creating replacement pipeline for about:failure");
 
         let new_pipeline_id = PipelineId::new();
-        let load_data = LoadData::new(failure_url, None, None);
+        let load_data = LoadData::new(failure_url.clone(), None, None);
         let sandbox = IFrameSandboxState::IFrameSandboxed;
         self.new_pipeline(new_pipeline_id, top_level_frame_id, parent_info, window_size, load_data, sandbox, false);
         self.pending_frames.push(FrameChange {
             frame_id: top_level_frame_id,
             old_pipeline_id: pipeline_id,
             new_pipeline_id: new_pipeline_id,
-            replace: false,
+            url: failure_url,
+            replace: None,
         });
     }
 
@@ -1286,7 +1288,8 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             frame_id: self.root_frame_id,
             old_pipeline_id: None,
             new_pipeline_id: root_pipeline_id,
-            replace: false,
+            url: url.clone(),
+            replace: None,
         });
         self.compositor_proxy.send(ToCompositorMsg::ChangePageUrl(root_pipeline_id, url));
     }
@@ -1377,7 +1380,21 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             (load_data, window_size, is_private)
         };
 
+        let replace = if load_info.info.replace {
+            self.frames.get(&load_info.info.frame_id).map(|frame| frame.current())
+        } else {
+            None
+        };
+
         // Create the new pipeline, attached to the parent and push to pending frames
+        self.pending_frames.push(FrameChange {
+            frame_id: load_info.info.frame_id,
+            old_pipeline_id: load_info.old_pipeline_id,
+            new_pipeline_id: load_info.info.new_pipeline_id,
+            url: load_data.url.clone(),
+            replace: replace,
+        });
+
         self.new_pipeline(load_info.info.new_pipeline_id,
                           load_info.info.frame_id,
                           Some((load_info.info.parent_pipeline_id, load_info.info.frame_type)),
@@ -1385,13 +1402,6 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
                           load_data,
                           load_info.sandbox,
                           is_private);
-
-        self.pending_frames.push(FrameChange {
-            frame_id: load_info.info.frame_id,
-            old_pipeline_id: load_info.old_pipeline_id,
-            new_pipeline_id: load_info.info.new_pipeline_id,
-            replace: load_info.info.replace,
-        });
     }
 
     fn handle_script_loaded_about_blank_in_iframe_msg(&mut self,
@@ -1406,6 +1416,8 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             is_private,
         } = load_info;
 
+        let url = ServoUrl::parse("about:blank").expect("infallible");
+
         let pipeline = {
             let parent_pipeline = match self.pipelines.get(&parent_pipeline_id) {
                 Some(parent_pipeline) => parent_pipeline,
@@ -1414,7 +1426,6 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
 
             let script_sender = parent_pipeline.event_loop.clone();
 
-            let url = ServoUrl::parse("about:blank").expect("infallible");
             Pipeline::new(new_pipeline_id,
                           frame_id,
                           Some((parent_pipeline_id, frame_type)),
@@ -1422,11 +1433,17 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
                           layout_sender,
                           self.compositor_proxy.clone_compositor_proxy(),
                           is_private || parent_pipeline.is_private,
-                          url,
+                          url.clone(),
                           None,
                           parent_pipeline.visible)
         };
 
+        let replace = if replace {
+            self.frames.get(&frame_id).map(|frame| frame.current())
+        } else {
+            None
+        };
+
         assert!(!self.pipelines.contains_key(&new_pipeline_id));
         self.pipelines.insert(new_pipeline_id, pipeline);
 
@@ -1434,6 +1451,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             frame_id: frame_id,
             old_pipeline_id: None,
             new_pipeline_id: new_pipeline_id,
+            url: url,
             replace: replace,
         });
     }
@@ -1488,7 +1506,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
 
             match self.frames.get(&self.root_frame_id) {
                 None => warn!("Alert sent after root frame closure."),
-                Some(root_frame) => match self.pipelines.get(&root_frame.current.pipeline_id) {
+                Some(root_frame) => match self.pipelines.get(&root_frame.pipeline_id) {
                     None => warn!("Alert sent after root pipeline closure."),
                     Some(root_pipeline) => root_pipeline.trigger_mozbrowser_event(Some(top_level_frame_id), event),
                 }
@@ -1564,13 +1582,19 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
                 let new_pipeline_id = PipelineId::new();
                 let root_frame_id = self.root_frame_id;
                 let sandbox = IFrameSandboxState::IFrameUnsandboxed;
-                self.new_pipeline(new_pipeline_id, root_frame_id, None, window_size, load_data, sandbox, false);
+                let replace = if replace {
+                    self.frames.get(&frame_id).map(|frame| frame.current())
+                } else {
+                    None
+                };
                 self.pending_frames.push(FrameChange {
                     frame_id: root_frame_id,
                     old_pipeline_id: Some(source_id),
                     new_pipeline_id: new_pipeline_id,
+                    url: load_data.url.clone(),
                     replace: replace,
                 });
+                self.new_pipeline(new_pipeline_id, root_frame_id, None, window_size, load_data, sandbox, false);
 
                 // Send message to ScriptThread that will suspend all timers
                 match self.pipelines.get(&source_id) {
@@ -1616,34 +1640,32 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             .map(|pipeline_id| self.get_top_level_frame_for_pipeline(pipeline_id))
             .unwrap_or(self.root_frame_id);
 
-        let mut traversal_info = HashMap::new();
+        let mut size = 0;
+        let mut table = HashMap::new();
 
         match direction {
             TraversalDirection::Forward(delta) => {
-                let mut future = self.joint_session_future(top_level_frame_id);
-                for _ in 0..delta {
-                    match future.pop() {
-                        Some((_, frame_id, pipeline_id)) => {
-                            traversal_info.insert(frame_id, pipeline_id);
-                        },
-                        None => return warn!("invalid traversal delta"),
-                    }
+                for entry in self.joint_session_future(top_level_frame_id).take(delta) {
+                    size = size + 1;
+                    table.insert(entry.frame_id, entry);
+                }
+                if size < delta {
+                    return debug!("Traversing forward too much.");
                 }
             },
             TraversalDirection::Back(delta) => {
-                let mut past = self.joint_session_past(top_level_frame_id);
-                for _ in 0..delta {
-                    match past.pop() {
-                        Some((_, frame_id, pipeline_id)) => {
-                            traversal_info.insert(frame_id, pipeline_id);
-                        },
-                        None => return warn!("invalid traversal delta"),
-                    }
+                for entry in self.joint_session_past(top_level_frame_id).take(delta) {
+                    size = size + 1;
+                    table.insert(entry.frame_id, entry);
+                }
+                if size < delta {
+                    return debug!("Traversing back too much.");
                 }
             },
-        };
-        for (frame_id, pipeline_id) in traversal_info {
-            self.traverse_frame_to_pipeline(frame_id, pipeline_id);
+        }
+
+        for (_, entry) in table {
+            self.traverse_to_entry(entry);
         }
     }
 
@@ -1664,7 +1686,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
         // frame's current pipeline. If neither exist, fall back to sending to
         // the compositor below.
         let root_pipeline_id = self.frames.get(&self.root_frame_id)
-            .map(|root_frame| root_frame.current.pipeline_id);
+            .map(|root_frame| root_frame.pipeline_id);
         let pipeline_id = self.focus_pipeline_id.or(root_pipeline_id);
 
         match pipeline_id {
@@ -1689,7 +1711,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
     fn handle_reload_msg(&mut self) {
         // Send Reload constellation msg to root script channel.
         let root_pipeline_id = self.frames.get(&self.root_frame_id)
-            .map(|root_frame| root_frame.current.pipeline_id);
+            .map(|root_frame| root_frame.pipeline_id);
 
         if let Some(pipeline_id) = root_pipeline_id {
             let msg = ConstellationControlMsg::Reload(pipeline_id);
@@ -1734,7 +1756,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
                            resp_chan: IpcSender<Option<PipelineId>>) {
         let frame_id = frame_id.unwrap_or(self.root_frame_id);
         let current_pipeline_id = self.frames.get(&frame_id)
-            .map(|frame| frame.current.pipeline_id);
+            .map(|frame| frame.pipeline_id);
         let pipeline_id_loaded = self.pending_frames.iter().rev()
             .find(|x| x.old_pipeline_id == current_pipeline_id)
             .map(|x| x.new_pipeline_id)
@@ -1806,11 +1828,11 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
         };
 
         let child_pipeline_ids: Vec<PipelineId> = self.full_frame_tree_iter(frame_id)
-                                                      .flat_map(|frame| frame.next.iter()
-                                                                .chain(frame.prev.iter())
-                                                                .chain(once(&frame.current)))
-                                                      .map(|state| state.pipeline_id)
-                                                      .collect();
+            .flat_map(|frame| frame.prev.iter().chain(frame.next.iter())
+                      .filter_map(|entry| entry.pipeline_id)
+                      .chain(once(frame.pipeline_id)))
+            .collect();
+
         for id in child_pipeline_ids {
             if let Some(pipeline) = self.pipelines.get_mut(&id) {
                 pipeline.change_visibility(visible);
@@ -1909,7 +1931,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             },
             WebDriverCommandMsg::TakeScreenshot(pipeline_id, reply) => {
                 let current_pipeline_id = self.frames.get(&self.root_frame_id)
-                    .map(|root_frame| root_frame.current.pipeline_id);
+                    .map(|root_frame| root_frame.pipeline_id);
                 if Some(pipeline_id) == current_pipeline_id {
                     self.compositor_proxy.send(ToCompositorMsg::CreatePng(reply));
                 } else {
@@ -1921,63 +1943,95 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
         }
     }
 
-    fn traverse_frame_to_pipeline(&mut self, frame_id: FrameId, next_pipeline_id: PipelineId) {
+    // https://html.spec.whatwg.org/multipage/#traverse-the-history
+    fn traverse_to_entry(&mut self, entry: FrameState) {
+        // Step 1.
+        let frame_id = entry.frame_id;
+        let pipeline_id = match entry.pipeline_id {
+            Some(pipeline_id) => pipeline_id,
+            None => {
+                // If there is no pipeline, then the document for this
+                // entry has been discarded, so we navigate to the entry
+                // URL instead. When the document has activated, it will
+                // traverse to the entry, but with the new pipeline id.
+                debug!("Reloading document {} for frame {}.", entry.url, frame_id);
+                // TODO: referrer?
+                let load_data = LoadData::new(entry.url.clone(), None, None);
+                // TODO: save the sandbox state so it can be restored here.
+                let sandbox = IFrameSandboxState::IFrameUnsandboxed;
+                let new_pipeline_id = PipelineId::new();
+                let (old_pipeline_id, parent_info, window_size, is_private) = match self.frames.get(&frame_id) {
+                    Some(frame) => match self.pipelines.get(&frame.pipeline_id) {
+                        Some(pipeline) => (frame.pipeline_id, pipeline.parent_info, pipeline.size, pipeline.is_private),
+                        None => (frame.pipeline_id, None, None, false),
+                    },
+                    None => return warn!("no frame to traverse"),
+                };
+                self.new_pipeline(new_pipeline_id, frame_id, parent_info, window_size, load_data, sandbox, is_private);
+                self.pending_frames.push(FrameChange {
+                    frame_id: frame_id,
+                    old_pipeline_id: Some(old_pipeline_id),
+                    new_pipeline_id: new_pipeline_id,
+                    url: entry.url.clone(),
+                    replace: Some(entry),
+                });
+                return;
+            }
+        };
+
         // Check if the currently focused pipeline is the pipeline being replaced
         // (or a child of it). This has to be done here, before the current
         // frame tree is modified below.
-        let update_focus_pipeline = self.focused_pipeline_in_tree(frame_id);
+        let update_focus_pipeline = self.focused_pipeline_in_tree(entry.frame_id);
 
-        let prev_pipeline_id = match self.frames.get_mut(&frame_id) {
+        let old_pipeline_id = match self.frames.get_mut(&frame_id) {
             Some(frame) => {
-                let prev = frame.current.pipeline_id;
-
-                // Check that this frame contains the pipeline passed in, so that this does not
-                // change Frame's state before realizing `next_pipeline_id` is invalid.
-                if frame.next.iter().find(|entry| next_pipeline_id == entry.pipeline_id).is_some() {
-                    frame.prev.push(frame.current.clone());
-                    while let Some(entry) = frame.next.pop() {
-                        if entry.pipeline_id == next_pipeline_id {
-                            frame.current = entry;
-                            break;
-                        } else {
-                            frame.prev.push(entry);
-                        }
+                let old_pipeline_id = frame.pipeline_id;
+                let mut curr_entry = frame.current();
+
+                if entry.instant > frame.instant {
+                    // We are traversing to the future.
+                    while let Some(next) = frame.next.pop() {
+                        frame.prev.push(curr_entry);
+                        curr_entry = next;
+                        if entry.instant <= curr_entry.instant { break; }
                     }
-                } else if frame.prev.iter().find(|entry| next_pipeline_id == entry.pipeline_id).is_some() {
-                    frame.next.push(frame.current.clone());
-                    while let Some(entry) = frame.prev.pop() {
-                        if entry.pipeline_id == next_pipeline_id {
-                            frame.current = entry;
-                            break;
-                        } else {
-                            frame.next.push(entry);
-                        }
+                } else if entry.instant < frame.instant {
+                    // We are traversing to the past.
+                    while let Some(prev) = frame.prev.pop() {
+                        frame.next.push(curr_entry);
+                        curr_entry = prev;
+                        if entry.instant >= curr_entry.instant { break; }
                     }
-                } else if prev != next_pipeline_id {
-                    return warn!("Tried to traverse frame {:?} to pipeline {:?} it does not contain.",
-                        frame_id, next_pipeline_id);
                 }
 
-                prev
+                debug_assert_eq!(entry.instant, curr_entry.instant);
+
+                frame.pipeline_id = pipeline_id;
+                frame.instant = entry.instant;
+                frame.url = entry.url.clone();
+
+                old_pipeline_id
             },
             None => return warn!("no frame to traverse"),
         };
 
-        let pipeline_info = self.pipelines.get(&prev_pipeline_id).and_then(|p| p.parent_info);
+        let parent_info = self.pipelines.get(&old_pipeline_id)
+            .and_then(|pipeline| pipeline.parent_info);
 
         // If the currently focused pipeline is the one being changed (or a child
         // of the pipeline being changed) then update the focus pipeline to be
         // the replacement.
         if update_focus_pipeline {
-            self.focus_pipeline_id = Some(next_pipeline_id);
+            self.focus_pipeline_id = Some(pipeline_id);
         }
 
         // Suspend the old pipeline, and resume the new one.
-        if let Some(prev_pipeline) = self.pipelines.get(&prev_pipeline_id) {
-            prev_pipeline.freeze();
+        if let Some(pipeline) = self.pipelines.get(&old_pipeline_id) {
+            pipeline.freeze();
         }
-        if let Some(next_pipeline) = self.pipelines.get(&next_pipeline_id) {
-            next_pipeline.thaw();
+        if let Some(pipeline) = self.pipelines.get(&pipeline_id) {
+            pipeline.thaw();
         }
 
         // Set paint permissions correctly for the compositor layers.
@@ -1985,10 +2039,8 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
 
         // Update the owning iframe to point to the new pipeline id.
         // This makes things like contentDocument work correctly.
-        if let Some((parent_pipeline_id, _)) = pipeline_info {
-            let msg = ConstellationControlMsg::UpdatePipelineId(parent_pipeline_id,
-                                                                frame_id,
-                                                                next_pipeline_id);
+        if let Some((parent_pipeline_id, _)) = parent_info {
+            let msg = ConstellationControlMsg::UpdatePipelineId(parent_pipeline_id, frame_id, pipeline_id);
             let result = match self.pipelines.get(&parent_pipeline_id) {
                 None => return warn!("Pipeline {:?} child traversed after closure.", parent_pipeline_id),
                 Some(pipeline) => pipeline.event_loop.send(msg),
@@ -1999,7 +2051,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
 
             // If this is an iframe, send a mozbrowser location change event.
             // This is the result of a back/forward traversal.
-            self.trigger_mozbrowserlocationchange(next_pipeline_id);
+            self.trigger_mozbrowserlocationchange(pipeline_id);
         }
     }
 
@@ -2049,33 +2101,39 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             }
         }
 
-        if self.frames.contains_key(&frame_change.frame_id) {
-            if frame_change.replace {
-                let evicted = self.frames.get_mut(&frame_change.frame_id).map(|frame| {
-                    frame.replace_current(frame_change.new_pipeline_id)
-                });
-                if let Some(evicted) = evicted {
-                    self.close_pipeline(evicted.pipeline_id, ExitPipelineMode::Normal);
-                }
-            } else {
-                if let Some(ref mut frame) = self.frames.get_mut(&frame_change.frame_id) {
-                    frame.load(frame_change.new_pipeline_id);
-                }
-            }
+        let (evicted_id, new_frame, clear_future, location_changed) = if let Some(mut entry) = frame_change.replace {
+            debug!("Replacing pipeline in existing frame.");
+            let evicted_id = entry.pipeline_id;
+            entry.pipeline_id = Some(frame_change.new_pipeline_id);
+            self.traverse_to_entry(entry);
+            (evicted_id, false, false, false)
+        } else if let Some(frame) = self.frames.get_mut(&frame_change.frame_id) {
+            debug!("Adding pipeline to existing frame.");
+            frame.load(frame_change.new_pipeline_id, frame_change.url.clone());
+            let evicted_id = frame.prev.get_mut(opts::get().max_session_history)
+                .and_then(|entry| entry.pipeline_id.take());
+            (evicted_id, false, true, true)
         } else {
-            // The new pipeline is in a new frame with no history
-            self.new_frame(frame_change.frame_id, frame_change.new_pipeline_id);
+            (None, true, false, true)
+        };
+
+        if let Some(evicted_id) = evicted_id {
+            self.close_pipeline(evicted_id, ExitPipelineMode::Normal);
         }
 
-        if !frame_change.replace {
-            // If this is an iframe, send a mozbrowser location change event.
-            // This is the result of a link being clicked and a navigation completing.
-            self.trigger_mozbrowserlocationchange(frame_change.new_pipeline_id);
+        if new_frame {
+            self.new_frame(frame_change.frame_id, frame_change.new_pipeline_id, frame_change.url);
+        };
 
+        if clear_future {
             let top_level_frame_id = self.get_top_level_frame_for_pipeline(frame_change.new_pipeline_id);
             self.clear_joint_session_future(top_level_frame_id);
         }
 
+        if location_changed {
+            self.trigger_mozbrowserlocationchange(frame_change.new_pipeline_id);
+        }
+
         // Build frame tree
         self.send_frame_tree();
     }
@@ -2114,7 +2172,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
         if let Some(frame) = self.frames.get(&self.root_frame_id) {
             // Send Resize (or ResizeInactive) messages to each
             // pipeline in the frame tree.
-            let pipeline_id = frame.current.pipeline_id;
+            let pipeline_id = frame.pipeline_id;
             let pipeline = match self.pipelines.get(&pipeline_id) {
                 None => return warn!("Pipeline {:?} resized after closing.", pipeline_id),
                 Some(pipeline) => pipeline,
@@ -2124,14 +2182,10 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
                 new_size,
                 size_type
             ));
-            for entry in frame.prev.iter().chain(&frame.next) {
-                let pipeline = match self.pipelines.get(&entry.pipeline_id) {
-                    None => {
-                        warn!("Inactive pipeline {:?} resized after closing.", pipeline_id);
-                        continue;
-                    },
-                    Some(pipeline) => pipeline,
-                };
+            let pipelines = frame.prev.iter().chain(frame.next.iter())
+                .filter_map(|entry| entry.pipeline_id)
+                .filter_map(|pipeline_id| self.pipelines.get(&pipeline_id));
+            for pipeline in pipelines {
                 let _ = pipeline.event_loop.send(ConstellationControlMsg::ResizeInactive(
                     pipeline.id,
                     new_size
@@ -2200,7 +2254,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
         // are met, then the output image should not change and a reftest
         // screenshot can safely be written.
         for frame in self.current_frame_tree_iter(self.root_frame_id) {
-            let pipeline_id = frame.current.pipeline_id;
+            let pipeline_id = frame.pipeline_id;
             debug!("Checking readiness of frame {}, pipeline {}.", frame.id, pipeline_id);
 
             let pipeline = match self.pipelines.get(&pipeline_id) {
@@ -2228,7 +2282,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             }
 
             // See if this pipeline has reached idle script state yet.
-            match self.document_states.get(&frame.current.pipeline_id) {
+            match self.document_states.get(&frame.pipeline_id) {
                 Some(&DocumentState::Idle) => {}
                 Some(&DocumentState::Pending) | None => {
                     return ReadyToSave::DocumentLoading;
@@ -2248,7 +2302,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
                 }
 
                 // Get the epoch that the compositor has drawn for this pipeline.
-                let compositor_epoch = pipeline_states.get(&frame.current.pipeline_id);
+                let compositor_epoch = pipeline_states.get(&frame.pipeline_id);
                 match compositor_epoch {
                     Some(compositor_epoch) => {
                         // Synchronously query the layout thread to see if the current
@@ -2280,38 +2334,27 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
     }
 
     fn clear_joint_session_future(&mut self, frame_id: FrameId) {
-        let mut evicted_pipelines = vec!();
-        let mut frames_to_clear = vec!(frame_id);
-        while let Some(frame_id) = frames_to_clear.pop() {
-            let frame = match self.frames.get_mut(&frame_id) {
-                Some(frame) => frame,
-                None => {
-                    warn!("Removed forward history after frame {:?} closure.", frame_id);
-                    continue;
-                }
+        let frame_ids: Vec<FrameId> = self.full_frame_tree_iter(frame_id)
+            .map(|frame| frame.id)
+            .collect();
+        for frame_id in frame_ids {
+            let evicted = match self.frames.get_mut(&frame_id) {
+                Some(frame) => frame.remove_forward_entries(),
+                None => continue,
             };
-            evicted_pipelines.extend(frame.remove_forward_entries());
-            for entry in frame.next.iter().chain(frame.prev.iter()).chain(once(&frame.current)) {
-                let pipeline = match self.pipelines.get(&entry.pipeline_id) {
-                    Some(pipeline) => pipeline,
-                    None => {
-                        warn!("Removed forward history after pipeline {:?} closure.", entry.pipeline_id);
-                        continue;
-                    }
-                };
-                frames_to_clear.extend_from_slice(&pipeline.children);
+            for entry in evicted {
+                if let Some(pipeline_id) = entry.pipeline_id {
+                    self.close_pipeline(pipeline_id, ExitPipelineMode::Normal);
+                }
             }
         }
-        for entry in evicted_pipelines {
-            self.close_pipeline(entry.pipeline_id, ExitPipelineMode::Normal);
-        }
     }
 
     // Close a frame (and all children)
     fn close_frame(&mut self, frame_id: FrameId, exit_mode: ExitPipelineMode) {
         debug!("Closing frame {}.", frame_id);
         let parent_info = self.frames.get(&frame_id)
-            .and_then(|frame| self.pipelines.get(&frame.current.pipeline_id))
+            .and_then(|frame| self.pipelines.get(&frame.pipeline_id))
             .and_then(|pipeline| pipeline.parent_info);
 
         self.close_frame_children(frame_id, exit_mode);
@@ -2344,9 +2387,9 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
             .collect();
 
         if let Some(frame) = self.frames.get(&frame_id) {
-            pipelines_to_close.extend(frame.next.iter().map(|state| state.pipeline_id));
-            pipelines_to_close.push(frame.current.pipeline_id);
-            pipelines_to_close.extend(frame.prev.iter().map(|state| state.pipeline_id));
+            pipelines_to_close.extend(frame.next.iter().filter_map(|state| state.pipeline_id));
+            pipelines_to_close.push(frame.pipeline_id);
+            pipelines_to_close.extend(frame.prev.iter().filter_map(|state| state.pipeline_id));
         }
 
         for pipeline_id in pipelines_to_close {
@@ -2430,7 +2473,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
     // Convert a frame to a sendable form to pass to the compositor
     fn frame_to_sendable(&self, frame_id: FrameId) -> Option<SendableFrameTree> {
         self.frames.get(&frame_id).and_then(|frame: &Frame| {
-            self.pipelines.get(&frame.current.pipeline_id).map(|pipeline: &Pipeline| {
+            self.pipelines.get(&frame.pipeline_id).map(|pipeline: &Pipeline| {
                 let mut frame_tree = SendableFrameTree {
                     pipeline: pipeline.to_sendable(),
                     size: pipeline.size,
@@ -2511,7 +2554,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
 
         match self.frames.get(&top_level_frame_id) {
             None => warn!("Mozbrowser error after top-level frame closed."),
-            Some(frame) => match self.pipelines.get(&frame.current.pipeline_id) {
+            Some(frame) => match self.pipelines.get(&frame.pipeline_id) {
                 None => warn!("Mozbrowser error after top-level pipeline closed."),
                 Some(pipeline) => match pipeline.parent_info {
                     None => pipeline.trigger_mozbrowser_event(None, event),
@@ -2538,7 +2581,7 @@ impl<Message, LTF, STF> Constellation<Message, LTF, STF>
                                pipeline_id: PipelineId,
                                root_frame_id: FrameId) -> bool {
         self.current_frame_tree_iter(root_frame_id)
-            .any(|current_frame| current_frame.current.pipeline_id == pipeline_id)
+            .any(|current_frame| current_frame.pipeline_id == pipeline_id)
     }
 
 }
diff --git a/components/constellation/frame.rs b/components/constellation/frame.rs
index b061e0920ee..d137e504f67 100644
--- a/components/constellation/frame.rs
+++ b/components/constellation/frame.rs
@@ -4,6 +4,7 @@
 
 use msg::constellation_msg::{FrameId, PipelineId};
 use pipeline::Pipeline;
+use servo_url::ServoUrl;
 use std::collections::HashMap;
 use std::iter::once;
 use std::mem::replace;
@@ -22,12 +23,18 @@ pub struct Frame {
     /// The frame id.
     pub id: FrameId,
 
+    /// The timestamp for the current session history entry
+    pub instant: Instant,
+
+    /// The pipeline for the current session history entry
+    pub pipeline_id: PipelineId,
+
+    /// The URL for the current session history entry
+    pub url: ServoUrl,
+
     /// The past session history, ordered chronologically.
     pub prev: Vec<FrameState>,
 
-    /// The currently active session history entry.
-    pub current: FrameState,
-
     /// The future session history, ordered reverse chronologically.
     pub next: Vec<FrameState>,
 }
@@ -35,30 +42,40 @@ pub struct Frame {
 impl Frame {
     /// Create a new frame.
     /// Note this just creates the frame, it doesn't add it to the frame tree.
-    pub fn new(id: FrameId, pipeline_id: PipelineId) -> Frame {
+    pub fn new(id: FrameId, pipeline_id: PipelineId, url: ServoUrl) -> Frame {
         Frame {
             id: id,
+            pipeline_id: pipeline_id,
+            instant: Instant::now(),
+            url: url,
             prev: vec!(),
-            current: FrameState::new(pipeline_id, id),
             next: vec!(),
         }
     }
 
+    /// Get the current frame state.
+    pub fn current(&self) -> FrameState {
+        FrameState {
+            instant: self.instant,
+            frame_id: self.id,
+            pipeline_id: Some(self.pipeline_id),
+            url: self.url.clone(),
+        }
+    }
+
     /// Set the current frame entry, and push the current frame entry into the past.
-    pub fn load(&mut self, pipeline_id: PipelineId) {
-        self.prev.push(self.current.clone());
-        self.current = FrameState::new(pipeline_id, self.id);
+    pub fn load(&mut self, pipeline_id: PipelineId, url: ServoUrl) {
+        let current = self.current();
+        self.prev.push(current);
+        self.instant = Instant::now();
+        self.pipeline_id = pipeline_id;
+        self.url = url;
     }
 
     /// Set the future to be empty.
     pub fn remove_forward_entries(&mut self) -> Vec<FrameState> {
         replace(&mut self.next, vec!())
     }
-
-    /// Set the current frame entry, and drop the current frame entry.
-    pub fn replace_current(&mut self, pipeline_id: PipelineId) -> FrameState {
-        replace(&mut self.current, FrameState::new(pipeline_id, self.id))
-    }
 }
 
 /// An entry in a frame's session history.
@@ -70,23 +87,18 @@ impl Frame {
 pub struct FrameState {
     /// The timestamp for when the session history entry was created
     pub instant: Instant,
-    /// The pipeline for the document in the session history
-    pub pipeline_id: PipelineId,
+
+    /// The pipeline for the document in the session history,
+    /// None if the entry has been discarded
+    pub pipeline_id: Option<PipelineId>,
+
+    /// The URL for this entry, used to reload the pipeline if it has been discarded
+    pub url: ServoUrl,
+
     /// The frame that this session history entry is part of
     pub frame_id: FrameId,
 }
 
-impl FrameState {
-    /// Create a new session history entry.
-    fn new(pipeline_id: PipelineId, frame_id: FrameId) -> FrameState {
-        FrameState {
-            instant: Instant::now(),
-            pipeline_id: pipeline_id,
-            frame_id: frame_id,
-        }
-    }
-}
-
 /// Represents a pending change in the frame tree, that will be applied
 /// once the new pipeline has loaded and completed initial layout / paint.
 pub struct FrameChange {
@@ -100,9 +112,12 @@ pub struct FrameChange {
     /// The pipeline for the document being loaded.
     pub new_pipeline_id: PipelineId,
 
+    /// The URL for the document being loaded.
+    pub url: ServoUrl,
+
     /// Is the new document replacing the current document (e.g. a reload)
     /// or pushing it into the session history (e.g. a navigation)?
-    pub replace: bool,
+    pub replace: Option<FrameState>,
 }
 
 /// An iterator over a frame tree, returning the fully active frames in
@@ -137,14 +152,14 @@ impl<'a> Iterator for FrameTreeIterator<'a> {
                     continue;
                 },
             };
-            let pipeline = match self.pipelines.get(&frame.current.pipeline_id) {
+            let pipeline = match self.pipelines.get(&frame.pipeline_id) {
                 Some(pipeline) => pipeline,
                 None => {
-                    warn!("Pipeline {:?} iterated after closure.", frame.current.pipeline_id);
+                    warn!("Pipeline {:?} iterated after closure.", frame.pipeline_id);
                     continue;
                 },
             };
-            self.stack.extend(pipeline.children.iter().map(|&c| c));
+            self.stack.extend(pipeline.children.iter());
             return Some(frame)
         }
     }
@@ -169,6 +184,7 @@ pub struct FullFrameTreeIterator<'a> {
 impl<'a> Iterator for FullFrameTreeIterator<'a> {
     type Item = &'a Frame;
     fn next(&mut self) -> Option<&'a Frame> {
+        let pipelines = self.pipelines;
         loop {
             let frame_id = match self.stack.pop() {
                 Some(frame_id) => frame_id,
@@ -181,11 +197,12 @@ impl<'a> Iterator for FullFrameTreeIterator<'a> {
                     continue;
                 },
             };
-            for entry in frame.prev.iter().chain(frame.next.iter()).chain(once(&frame.current)) {
-                if let Some(pipeline) = self.pipelines.get(&entry.pipeline_id) {
-                    self.stack.extend(pipeline.children.iter().map(|&c| c));
-                }
-            }
+            let child_frame_ids = frame.prev.iter().chain(frame.next.iter())
+                .filter_map(|entry| entry.pipeline_id)
+                .chain(once(frame.pipeline_id))
+                .filter_map(|pipeline_id| pipelines.get(&pipeline_id))
+                .flat_map(|pipeline| pipeline.children.iter());
+            self.stack.extend(child_frame_ids);
             return Some(frame)
         }
     }
diff --git a/components/constellation/lib.rs b/components/constellation/lib.rs
index adb9e768425..ecfa1c80dd8 100644
--- a/components/constellation/lib.rs
+++ b/components/constellation/lib.rs
@@ -3,6 +3,7 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #![feature(box_syntax)]
+#![feature(conservative_impl_trait)]
 #![feature(mpsc_select)]
 #![feature(plugin)]
 #![feature(proc_macro)]
diff --git a/components/script/dom/window.rs b/components/script/dom/window.rs
index 7dd8d71e9c8..37bf817ed7a 100644
--- a/components/script/dom/window.rs
+++ b/components/script/dom/window.rs
@@ -901,18 +901,24 @@ impl Window {
     }
 
     pub fn clear_js_runtime(&self) {
+        // We tear down the active document, which causes all the attached
+        // nodes to dispose of their layout data. This messages the layout
+        // thread, informing it that it can safely free the memory.
         self.Document().upcast::<Node>().teardown();
 
-        // The above code may not catch all DOM objects
-        // (e.g. DOM objects removed from the tree that haven't
-        // been collected yet). Forcing a GC here means that
-        // those DOM objects will be able to call dispose()
-        // to free their layout data before the layout thread
-        // exits. Without this, those remaining objects try to
-        // send a message to free their layout data to the
-        // layout thread when the script thread is dropped,
-        // which causes a panic!
+        // The above code may not catch all DOM objects (e.g. DOM
+        // objects removed from the tree that haven't been collected
+        // yet). There should not be any such DOM nodes with layout
+        // data, but if there are, then when they are dropped, they
+        // will attempt to send a message to the closed layout thread.
+        // This causes memory safety issues, because the DOM node uses
+        // the layout channel from its window, and the window has
+        // already been GC'd.  For nodes which do not have a live
+        // pointer, we can avoid this by GCing now:
         self.Gc();
+        // but there may still be nodes being kept alive by user
+        // script.
+        // TODO: ensure that this doesn't happen!
 
         self.current_state.set(WindowState::Zombie);
         *self.js_runtime.borrow_mut() = None;
@@ -1445,6 +1451,15 @@ impl Window {
         None
     }
 
+    pub fn freeze(&self) {
+        self.upcast::<GlobalScope>().suspend();
+        // A hint to the JS runtime that now would be a good time to
+        // GC any unreachable objects generated by user script,
+        // or unattached DOM nodes. Attached DOM nodes can't be GCd yet,
+        // as the document might be thawed later.
+        self.Gc();
+    }
+
     pub fn thaw(&self) {
         self.upcast::<GlobalScope>().resume();
 
diff --git a/components/script/script_thread.rs b/components/script/script_thread.rs
index 065d214a323..563e4c52529 100644
--- a/components/script/script_thread.rs
+++ b/components/script/script_thread.rs
@@ -1346,7 +1346,7 @@ impl ScriptThread {
     fn handle_freeze_msg(&self, id: PipelineId) {
         let window = self.documents.borrow().find_window(id);
         if let Some(window) = window {
-            window.upcast::<GlobalScope>().suspend();
+            window.freeze();
             return;
         }
         let mut loads = self.incomplete_loads.borrow_mut();
diff --git a/components/script/timers.rs b/components/script/timers.rs
index 14c4eb89c13..b86bdc17aae 100644
--- a/components/script/timers.rs
+++ b/components/script/timers.rs
@@ -228,18 +228,20 @@ impl OneshotTimers {
     }
 
     pub fn suspend(&self) {
-        assert!(self.suspended_since.get().is_none());
+        // Suspend is idempotent: do nothing if the timers are already suspended.
+        if self.suspended_since.get().is_some() {
+            return warn!("Suspending an already suspended timer.");
+        }
 
         self.suspended_since.set(Some(precise_time_ms()));
         self.invalidate_expected_event_id();
     }
 
     pub fn resume(&self) {
-        assert!(self.suspended_since.get().is_some());
-
+        // Suspend is idempotent: do nothing if the timers are already suspended.
         let additional_offset = match self.suspended_since.get() {
             Some(suspended_since) => precise_time_ms() - suspended_since,
-            None => panic!("Timers are not suspended.")
+            None => return warn!("Resuming an already resumed timer."),
         };
 
         self.suspension_offset.set(self.suspension_offset.get() + additional_offset);
diff --git a/components/url/lib.rs b/components/url/lib.rs
index 43498444a54..49db7d4d951 100644
--- a/components/url/lib.rs
+++ b/components/url/lib.rs
@@ -24,7 +24,7 @@ use std::path::Path;
 use std::sync::Arc;
 use url::{Url, Origin, Position};
 
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 #[cfg_attr(feature = "servo", derive(HeapSizeOf, Serialize, Deserialize))]
 pub struct ServoUrl(Arc<Url>);