Heads up! This PR modifies the following files:

• @asajeffrey: components/webdriver_server/lib.rs, components/constellation/constellation.rs
• @jgraham: components/webdriver_server/lib.rs
• @KiChjang: components/script/dom/htmliframeelement.rs, components/script_traits/script_msg.rs, components/script_traits/script_msg.rs, components/script_traits/lib.rs, components/script_traits/lib.rs

Warning

• These commits modify script code, but no tests are modified. Please consider adding a test!

☔ The latest upstream changes (presumably #10826) made this pull request unmergeable. Please resolve the merge conflicts.

Rebased.

Does this try to implement the spec model? Based on input from Gecko and Blink engineers, it seems that extant implementations are different from the spec in ways that are likely to be difficult to reconcile without changing the spec model to match implementations. In particular the existing implementations store a representation of the frame tree for each position in history, and then diff that tree during navigations to work out which frame to navigate. IMO we should implement that model and change the spec to match.

@jgraham it's based off of https://github.com/ConnorGBrewster/ServoNavigation/blob/master/notes/notes.pdf. It tries to stay as close to the current spec as possible. That proposes some changes to the spec to match up with what other browsers do/making traversal homomorphic.

@jgraham we tried to make the minimum changes to the spec but be a) as close as possible to existing implementations, and b) vaguely sensible :) We are expecting that spec changes will be a result of this work.

OK, but "as few changes from the spec as possible" should not be a goal. From what I've heard so far it sounds like there is common agreement on how this stuff is implemented, and the spec should reflect that agreement (in this area particularly because other implementations are highly unlikely to change their code to reflect a different model in the spec). From Servo's point of view this doesn't seem like an area where being gratuitously different can buy much in terms of the higher level goals around quality and performance.

Agreed, the goals are (a) and (b) and if we can get something that meets this with as little disruption, so much the better.

This implementation is based on timestamps and lazily computing the joint session history. I think with the revised spec, we should be able to use an in-memory representation of the jsh, and not have to keep track of timestamps. Not sure which is better.

Reviewed 6 of 7 files at r7, 1 of 1 files at r8.
Review status: all files reviewed at latest revision, 4 unresolved discussions.

components/constellation/constellation.rs, line 220 [r8] (raw file):

}

struct FrameIterator<'a> {

Rather than keeping two iterators, wouldn't it be easier to have separate ForwardFrameIterator and BackwardFrameInterator types?

components/constellation/constellation.rs, line 232 [r8] (raw file):

        match self.direction {
            TraversalDirection::Back(_) => {
                if let Some(entry) = self.current {

I think this is doing by hand what once(current).chain(prev) does.

components/constellation/constellation.rs, line 266 [r8] (raw file):

    }

    fn iter(&self, direction: TraversalDirection) -> FrameIterator {

I think this would be simpler with two different iterators, since they're different logic.

components/constellation/constellation.rs, line 364 [r8] (raw file):

                self.stack.iter_mut()
                          .filter_map(|&mut (frame_id, ref mut iter)| {
                              iter.peek().cloned().map(|(_, instant)| (frame_id, iter, instant))

Yay combinators!

Comments from Reviewable

IRC chat: http://logs.glob.uno/?c=mozilla%23servo&s=27+Jun+2016&e=27+Jun+2016#c463962

TL;DR in-memory vs lazy computation of joint session history?

Cleaned up a bit, still a few things I would like to get cleaner, like reducing the number of Vec allocations. But this should clean up the Iterator stuff a bit.

Review status: 0 of 7 files reviewed at latest revision, 4 unresolved discussions.

components/constellation/constellation.rs, line 220 [r8] (raw file):

components/constellation/constellation.rs, line 232 [r8] (raw file):

components/constellation/constellation.rs, line 266 [r8] (raw file):

components/constellation/constellation.rs, line 364 [r8] (raw file):

Comments from Reviewable

I just cleaned up the HistoryIterator quite a bit. Just added a new enum for HistoryDirection that holds the corresponding stack type. This gets rid of having an unused empty Vec.

components/constellation/constellation.rs, line 232 [r8] (raw file):

Comments from Reviewable

I did as much as I could think of to reduce the amount of vec allocations, now there are only 2 vec allocations for full_frame_tree(). The pipelines vec can't be switched to a iter because you can't chain while in a for/while loop 😢.

This is ready for another review pass.

Reviewed everything apart from the constellation, i.e. all the easy bits! I'm trying to work out how we can simplify the constellation code.

Reviewed 6 of 7 files at r11.
Review status: 6 of 7 files reviewed at latest revision, 3 unresolved discussions.

components/msg/constellation_msg.rs, line 246 [r17] (raw file):

#[derive(Clone, PartialEq, Eq, Copy, Hash, Debug, Deserialize, Serialize)]
pub enum TraversalDirection {

Yay for spec-compliant naming!

components/script_traits/lib.rs, line 551 [r17] (raw file):

    LoadUrl(PipelineId, LoadData),
    /// Request to traverse the joint session history.
    TraverseHistory(Option<(PipelineId)>, TraversalDirection),

Don't need parentheses around PipelineId.

components/script_traits/script_msg.rs, line 77 [r17] (raw file):

    MozBrowserEvent(PipelineId, SubpageId, MozBrowserEvent),
    /// HTMLIFrameElement Forward or Back traversal.
    TraverseHistory(Option<(PipelineId)>, TraversalDirection),

Don't need parentheses around PipelineId.

Comments from Reviewable

Finally got back around to this one. I would like to simplify the extra constellation code aswell, it seems like the constellation could grow a lot after this, old pipeline purging, and History API state stuff if we aren't careful.

Review status: 0 of 7 files reviewed at latest revision, 3 unresolved discussions.

components/msg/constellation_msg.rs, line 246 [r17] (raw file):

components/script_traits/lib.rs, line 551 [r17] (raw file):

components/script_traits/script_msg.rs, line 77 [r17] (raw file):

Comments from Reviewable

☔ The latest upstream changes (presumably #12178) made this pull request unmergeable. Please resolve the merge conflicts.

Reviewed 3 of 7 files at r56, 2 of 2 files at r62, 2 of 2 files at r63.
Review status: 6 of 7 files reviewed at latest revision, 6 unresolved discussions.

components/constellation/constellation.rs, line 1572 [r53] (raw file):

components/constellation/constellation.rs, line 583 [r63] (raw file):

    }

    fn joint_session_future(&self, frame_id_root: FrameId) -> Vec<(Instant, FrameId, PipelineId)> {

Yay, this looks a lot nicer!

components/constellation/constellation.rs, line 603 [r63] (raw file):

            };
            for &frame_id in &pipeline.children {
                future.extend_from_slice(&self.joint_session_future(frame_id));

Are we creating vectors each time we do a recursive call? Wouldn't it be more efficient to pass in the vector as an argument?

components/constellation/constellation.rs, line 608 [r63] (raw file):

        // reverse sorting
        future.sort_by(|a, b| b.cmp(a));

Similarly, wouldn't it be more efficient to sort just the once, rather than every recursive call?

components/constellation/constellation.rs, line 646 [r63] (raw file):

    // Get a `Vec` of all the frames that are descendants of a root frame. This includes all
    // active and inactive frames.
    fn full_frame_tree(&self, frame_id_root: FrameId) -> Vec<FrameId> {

Can we get rid of this function? it's only used to remove the joint session future, which we should be able to do without slurping the whole frame tree into a vector.

components/constellation/constellation.rs, line 2208 [r63] (raw file):

    }

    fn remove_forward_history_in_frame_tree(&mut self, frame_id: FrameId) {

Bikeshed: clear_joint_session_future?

Comments from Reviewable

Review status: 6 of 7 files reviewed at latest revision, 6 unresolved discussions.

components/constellation/constellation.rs, line 1572 [r53] (raw file):

components/constellation/constellation.rs, line 603 [r63] (raw file):

components/constellation/constellation.rs, line 608 [r63] (raw file):

components/constellation/constellation.rs, line 646 [r63] (raw file):

components/constellation/constellation.rs, line 2208 [r63] (raw file):

Comments from Reviewable

Yay, nearly there, just one more nit.

Reviewed 1 of 1 files at r65.
Review status: all files reviewed at latest revision, 2 unresolved discussions.

components/constellation/constellation.rs, line 592 [r65] (raw file):

    }

    fn get_future_entries(&self, frame_id_root: FrameId, mut future: &mut Vec<(Instant, FrameId, PipelineId)>) {

Can just make this a Vec rather than a &mut Vec?

Comments from Reviewable

My goodness that was a bit epic!

@bors-servo r+

📌 Commit e72d1a5 has been approved by asajeffrey

⌛ Testing commit e72d1a5 with merge 0559e4f...

💔 Test failed - linux-rel

@bors-servo r=asajeffrey
I was checking the jsh future/past of the root pipeline instead of the mozbrowser iframe pipeline.

📌 Commit f131818 has been approved by asajeffrey

⌛ Testing commit f131818 with merge 05cc763...

☀️ Test successful - android, arm32, arm64, linux-dev, linux-rel, mac-dev-unit, mac-rel-css, mac-rel-wpt, windows-dev