1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 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);
}
}
}