script: Update the rendering when receiving IPC messages instead of just reflowing (#34486)

This changes fixes two issues:

1. A reflow of all `Document`s currently done unconditionally after
   receving IPC messages in the `ScriptThread`. Reflowing without first
   updating the animation timeline can lead to transitions finshing as
   soon as they start (because it looks like time advancement is
   measaured between calls to `update-the-rendering`).
2. Fix an issue where not all `Pipeline`s were updated during *update
   the rendering*. The previous code only took into account top level
   frames and their children. It's not guaranteed that a particular
   `ScriptThread` is managing any top level frames, depending on the
   origens of those frames. We should update the rendering of those
   non-top-level iframes regardless.

   The new code attempts to order the frames according to the
   specification as much as possible without knowing the entire frame
   tree, without skipping any documents managed by the `ScriptThread` in
   question.

In addition, `Documents` is pulled out the `script_thread.rs` and
renamed to `DocumentCollection`.

Signed-off-by: Martin Robinson <mrobinson@igalia.com>

1 files changed, 177 insertions, 0 deletions

diff --git a/components/script/document_collection.rs b/components/script/document_collection.rs
new file mode 100644
index 00000000000..0dc4ce87bb4
--- /dev/null
+++ b/components/script/document_collection.rs
@@ -0,0 +1,177 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+use std::collections::{hash_map, HashMap};
+
+use base::id::{BrowsingContextId, PipelineId};
+
+use crate::dom::bindings::inheritance::Castable;
+use crate::dom::bindings::root::{Dom, DomRoot};
+use crate::dom::bindings::trace::HashMapTracedValues;
+use crate::dom::document::Document;
+use crate::dom::globalscope::GlobalScope;
+use crate::dom::htmliframeelement::HTMLIFrameElement;
+use crate::dom::window::Window;
+
+/// The collection of all [`Document`]s managed by the [`crate::script_thread::SriptThread`].
+/// This is stored as a mapping of [`PipelineId`] to [`Document`], but for updating the
+/// rendering, [`Document`]s should be processed in order via [`Self::documents_in_order`].
+#[derive(JSTraceable)]
+#[crown::unrooted_must_root_lint::must_root]
+pub(crate) struct DocumentCollection {
+    map: HashMapTracedValues<PipelineId, Dom<Document>>,
+}
+
+impl DocumentCollection {
+    pub fn insert(&mut self, pipeline_id: PipelineId, doc: &Document) {
+        self.map.insert(pipeline_id, Dom::from_ref(doc));
+    }
+
+    pub fn remove(&mut self, pipeline_id: PipelineId) -> Option<DomRoot<Document>> {
+        self.map
+            .remove(&pipeline_id)
+            .map(|ref doc| DomRoot::from_ref(&**doc))
+    }
+
+    pub fn find_document(&self, pipeline_id: PipelineId) -> Option<DomRoot<Document>> {
+        self.map
+            .get(&pipeline_id)
+            .map(|doc| DomRoot::from_ref(&**doc))
+    }
+
+    pub fn find_window(&self, pipeline_id: PipelineId) -> Option<DomRoot<Window>> {
+        self.find_document(pipeline_id)
+            .map(|doc| DomRoot::from_ref(doc.window()))
+    }
+
+    pub fn find_global(&self, pipeline_id: PipelineId) -> Option<DomRoot<GlobalScope>> {
+        self.find_window(pipeline_id)
+            .map(|window| DomRoot::from_ref(window.upcast()))
+    }
+
+    pub fn find_iframe(
+        &self,
+        pipeline_id: PipelineId,
+        browsing_context_id: BrowsingContextId,
+    ) -> Option<DomRoot<HTMLIFrameElement>> {
+        self.find_document(pipeline_id)
+            .and_then(|doc| doc.find_iframe(browsing_context_id))
+    }
+
+    pub fn iter(&self) -> DocumentsIter<'_> {
+        DocumentsIter {
+            iter: self.map.iter(),
+        }
+    }
+
+    /// Return the documents managed by this [`crate::script_thread::ScriptThread`] in the
+    /// order specified by the *[update the rendering][update-the-rendering]* step of the
+    /// HTML specification:
+    ///
+    /// > Let docs be all fully active Document objects whose relevant agent's event loop is
+    /// > eventLoop, sorted arbitrarily except that the following conditions must be met:
+    /// >
+    /// > Any Document B whose container document is A must be listed after A in the list.
+    /// >
+    /// > If there are two documents A and B that both have the same non-null container
+    /// > document C, then the order of A and B in the list must match the shadow-including
+    /// > tree order of their respective navigable containers in C's node tree.
+    /// >
+    /// > In the steps below that iterate over docs, each Document must be processed in the
+    /// > order it is found in the list.
+    ///
+    /// [update-the-rendering]: https://html.spec.whatwg.org/multipage/#update-the-rendering
+    pub(crate) fn documents_in_order(&self) -> Vec<PipelineId> {
+        // TODO: This is a fairly expensive operation, because iterating iframes requires walking
+        // the *entire* DOM for a document. Instead this should be cached and marked as dirty when
+        // the DOM of a document changes or documents are added or removed from our set.
+        DocumentTree::new(self).documents_in_order()
+    }
+}
+
+impl Default for DocumentCollection {
+    #[allow(crown::unrooted_must_root)]
+    fn default() -> Self {
+        Self {
+            map: HashMapTracedValues::new(),
+        }
+    }
+}
+
+#[allow(crown::unrooted_must_root)]
+pub struct DocumentsIter<'a> {
+    iter: hash_map::Iter<'a, PipelineId, Dom<Document>>,
+}
+
+impl<'a> Iterator for DocumentsIter<'a> {
+    type Item = (PipelineId, DomRoot<Document>);
+
+    fn next(&mut self) -> Option<(PipelineId, DomRoot<Document>)> {
+        self.iter
+            .next()
+            .map(|(id, doc)| (*id, DomRoot::from_ref(&**doc)))
+    }
+}
+
+#[derive(Default)]
+struct DocumentTreeNode {
+    parent: Option<PipelineId>,
+    children: Vec<PipelineId>,
+}
+
+/// A tree representation of [`Document`]s managed by the [`ScriptThread`][st], which is used
+/// to generate an ordered set of [`Document`]s for the *update the rendering* step of the
+/// HTML5 specification.
+///
+/// FIXME: The [`ScriptThread`][st] only has a view of [`Document`]s managed by itself,
+/// so if there are interceding iframes managed by other `ScriptThread`s, then the
+/// order of the [`Document`]s may not be correct. Perhaps the Constellation could
+/// ensure that every [`ScriptThread`][st] has the full view of the frame tree.
+///
+/// [st]: crate::script_thread::ScriptThread
+#[derive(Default)]
+struct DocumentTree {
+    tree: HashMap<PipelineId, DocumentTreeNode>,
+}
+
+impl DocumentTree {
+    fn new(documents: &DocumentCollection) -> Self {
+        let mut tree = DocumentTree::default();
+        for (id, document) in documents.iter() {
+            let children: Vec<PipelineId> = document
+                .iter_iframes()
+                .filter_map(|iframe| iframe.pipeline_id())
+                .filter(|iframe_pipeline_id| documents.find_document(*iframe_pipeline_id).is_some())
+                .collect();
+            for child in &children {
+                tree.tree.entry(*child).or_default().parent = Some(id);
+            }
+            tree.tree.entry(id).or_default().children = children;
+        }
+        tree
+    }
+
+    fn documents_in_order(&self) -> Vec<PipelineId> {
+        let mut list = Vec::new();
+        for (id, node) in self.tree.iter() {
+            if node.parent.is_none() {
+                self.process_node_for_documents_in_order(*id, &mut list);
+            }
+        }
+        list
+    }
+
+    fn process_node_for_documents_in_order(&self, id: PipelineId, list: &mut Vec<PipelineId>) {
+        list.push(id);
+        for child in self
+            .tree
+            .get(&id)
+            .expect("Should have found child node")
+            .children
+            .iter()
+        {
+            self.process_node_for_documents_in_order(*child, list);
+        }
+    }
+}