script/
document_collection.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use std::collections::{HashMap, hash_map};
6
7use base::id::{BrowsingContextId, PipelineId};
8
9use crate::dom::bindings::inheritance::Castable;
10use crate::dom::bindings::root::{Dom, DomRoot};
11use crate::dom::bindings::trace::HashMapTracedValues;
12use crate::dom::document::Document;
13use crate::dom::globalscope::GlobalScope;
14use crate::dom::html::htmliframeelement::HTMLIFrameElement;
15use crate::dom::window::Window;
16
17/// The collection of all [`Document`]s managed by the [`crate::script_thread::ScriptThread`].
18/// This is stored as a mapping of [`PipelineId`] to [`Document`], but for updating the
19/// rendering, [`Document`]s should be processed in order via [`Self::documents_in_order`].
20#[derive(JSTraceable)]
21#[cfg_attr(crown, crown::unrooted_must_root_lint::must_root)]
22pub(crate) struct DocumentCollection {
23    map: HashMapTracedValues<PipelineId, Dom<Document>>,
24}
25
26impl DocumentCollection {
27    pub(crate) fn insert(&mut self, pipeline_id: PipelineId, doc: &Document) {
28        self.map.insert(pipeline_id, Dom::from_ref(doc));
29    }
30
31    pub(crate) fn remove(&mut self, pipeline_id: PipelineId) -> Option<DomRoot<Document>> {
32        self.map
33            .remove(&pipeline_id)
34            .map(|ref doc| DomRoot::from_ref(&**doc))
35    }
36
37    pub(crate) fn find_document(&self, pipeline_id: PipelineId) -> Option<DomRoot<Document>> {
38        self.map
39            .get(&pipeline_id)
40            .map(|doc| DomRoot::from_ref(&**doc))
41    }
42
43    pub(crate) fn find_window(&self, pipeline_id: PipelineId) -> Option<DomRoot<Window>> {
44        self.find_document(pipeline_id)
45            .map(|doc| DomRoot::from_ref(doc.window()))
46    }
47
48    pub(crate) fn find_global(&self, pipeline_id: PipelineId) -> Option<DomRoot<GlobalScope>> {
49        self.find_window(pipeline_id)
50            .map(|window| DomRoot::from_ref(window.upcast()))
51    }
52
53    pub(crate) fn find_iframe(
54        &self,
55        pipeline_id: PipelineId,
56        browsing_context_id: BrowsingContextId,
57    ) -> Option<DomRoot<HTMLIFrameElement>> {
58        self.find_document(pipeline_id).and_then(|document| {
59            document
60                .iframes()
61                .get(browsing_context_id)
62                .map(|iframe| iframe.element.as_rooted())
63        })
64    }
65
66    pub(crate) fn iter(&self) -> DocumentsIter<'_> {
67        DocumentsIter {
68            iter: self.map.iter(),
69        }
70    }
71
72    /// Return the documents managed by this [`crate::script_thread::ScriptThread`] in the
73    /// order specified by the *[update the rendering][update-the-rendering]* step of the
74    /// HTML specification:
75    ///
76    /// > Let docs be all fully active Document objects whose relevant agent's event loop is
77    /// > eventLoop, sorted arbitrarily except that the following conditions must be met:
78    /// >
79    /// > Any Document B whose container document is A must be listed after A in the list.
80    /// >
81    /// > If there are two documents A and B that both have the same non-null container
82    /// > document C, then the order of A and B in the list must match the shadow-including
83    /// > tree order of their respective navigable containers in C's node tree.
84    /// >
85    /// > In the steps below that iterate over docs, each Document must be processed in the
86    /// > order it is found in the list.
87    ///
88    /// [update-the-rendering]: https://html.spec.whatwg.org/multipage/#update-the-rendering
89    pub(crate) fn documents_in_order(&self) -> Vec<PipelineId> {
90        DocumentTree::new(self).documents_in_order()
91    }
92}
93
94impl Default for DocumentCollection {
95    #[cfg_attr(crown, allow(crown::unrooted_must_root))]
96    fn default() -> Self {
97        Self {
98            map: HashMapTracedValues::new(),
99        }
100    }
101}
102
103#[cfg_attr(crown, allow(crown::unrooted_must_root))]
104pub(crate) struct DocumentsIter<'a> {
105    iter: hash_map::Iter<'a, PipelineId, Dom<Document>>,
106}
107
108impl Iterator for DocumentsIter<'_> {
109    type Item = (PipelineId, DomRoot<Document>);
110
111    fn next(&mut self) -> Option<(PipelineId, DomRoot<Document>)> {
112        self.iter
113            .next()
114            .map(|(id, doc)| (*id, DomRoot::from_ref(&**doc)))
115    }
116}
117
118#[derive(Default)]
119struct DocumentTreeNode {
120    parent: Option<PipelineId>,
121    children: Vec<PipelineId>,
122}
123
124/// A tree representation of [`Document`]s managed by the [`ScriptThread`][st], which is used
125/// to generate an ordered set of [`Document`]s for the *update the rendering* step of the
126/// HTML5 specification.
127///
128/// FIXME: The [`ScriptThread`][st] only has a view of [`Document`]s managed by itself,
129/// so if there are interceding iframes managed by other `ScriptThread`s, then the
130/// order of the [`Document`]s may not be correct. Perhaps the Constellation could
131/// ensure that every [`ScriptThread`][st] has the full view of the frame tree.
132///
133/// [st]: crate::script_thread::ScriptThread
134#[derive(Default)]
135struct DocumentTree {
136    tree: HashMap<PipelineId, DocumentTreeNode>,
137}
138
139impl DocumentTree {
140    fn new(documents: &DocumentCollection) -> Self {
141        let mut tree = DocumentTree::default();
142        for (id, document) in documents.iter() {
143            let children: Vec<PipelineId> = document
144                .iframes()
145                .iter()
146                .filter_map(|iframe| iframe.pipeline_id())
147                .filter(|iframe_pipeline_id| documents.find_document(*iframe_pipeline_id).is_some())
148                .collect();
149            for child in &children {
150                tree.tree.entry(*child).or_default().parent = Some(id);
151            }
152            tree.tree.entry(id).or_default().children = children;
153        }
154        tree
155    }
156
157    fn documents_in_order(&self) -> Vec<PipelineId> {
158        let mut list = Vec::new();
159        for (id, node) in self.tree.iter() {
160            if node.parent.is_none() {
161                self.process_node_for_documents_in_order(*id, &mut list);
162            }
163        }
164        list
165    }
166
167    fn process_node_for_documents_in_order(&self, id: PipelineId, list: &mut Vec<PipelineId>) {
168        list.push(id);
169        for child in self
170            .tree
171            .get(&id)
172            .expect("Should have found child node")
173            .children
174            .iter()
175        {
176            self.process_node_for_documents_in_order(*child, list);
177        }
178    }
179}