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);
        }
    }
}