aboutsummaryrefslogtreecommitdiffstats
path: root/components/script/dom
diff options
context:
space:
mode:
Diffstat (limited to 'components/script/dom')
-rw-r--r--components/script/dom/document.rs60
-rw-r--r--components/script/dom/htmlcollection.rs252
2 files changed, 235 insertions, 77 deletions
diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index b39adbc53fc..0d778e700c9 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -26,7 +26,7 @@ use dom::bindings::refcounted::Trusted;
use dom::bindings::reflector::{Reflectable, reflect_dom_object};
use dom::bindings::trace::RootedVec;
use dom::bindings::xmlname::XMLName::InvalidXMLName;
-use dom::bindings::xmlname::{validate_and_extract, xml_name_type};
+use dom::bindings::xmlname::{validate_and_extract, namespace_from_domstring, xml_name_type};
use dom::comment::Comment;
use dom::customevent::CustomEvent;
use dom::documentfragment::DocumentFragment;
@@ -119,7 +119,6 @@ enum ParserBlockedByScript {
pub struct Document {
node: Node,
window: JS<Window>,
- idmap: DOMRefCell<HashMap<Atom, Vec<JS<Element>>>>,
implementation: MutNullableHeap<JS<DOMImplementation>>,
location: MutNullableHeap<JS<Location>>,
content_type: DOMString,
@@ -128,6 +127,11 @@ pub struct Document {
is_html_document: bool,
url: Url,
quirks_mode: Cell<QuirksMode>,
+ /// Caches for the getElement methods
+ id_map: DOMRefCell<HashMap<Atom, Vec<JS<Element>>>>,
+ tag_map: DOMRefCell<HashMap<Atom, JS<HTMLCollection>>>,
+ tagns_map: DOMRefCell<HashMap<QualName, JS<HTMLCollection>>>,
+ classes_map: DOMRefCell<HashMap<Vec<Atom>, JS<HTMLCollection>>>,
images: MutNullableHeap<JS<HTMLCollection>>,
embeds: MutNullableHeap<JS<HTMLCollection>>,
links: MutNullableHeap<JS<HTMLCollection>>,
@@ -387,8 +391,8 @@ impl Document {
to_unregister: &Element,
id: Atom) {
debug!("Removing named element from document {:p}: {:p} id={}", self, to_unregister, id);
- let mut idmap = self.idmap.borrow_mut();
- let is_empty = match idmap.get_mut(&id) {
+ let mut id_map = self.id_map.borrow_mut();
+ let is_empty = match id_map.get_mut(&id) {
None => false,
Some(elements) => {
let position = elements.iter()
@@ -399,7 +403,7 @@ impl Document {
}
};
if is_empty {
- idmap.remove(&id);
+ id_map.remove(&id);
}
}
@@ -411,12 +415,12 @@ impl Document {
assert!(element.upcast::<Node>().is_in_doc());
assert!(!id.is_empty());
- let mut idmap = self.idmap.borrow_mut();
+ let mut id_map = self.id_map.borrow_mut();
let root = self.GetDocumentElement().expect(
"The element is in the document, so there must be a document element.");
- match idmap.entry(id) {
+ match id_map.entry(id) {
Vacant(entry) => {
entry.insert(vec![JS::from_ref(element)]);
}
@@ -1278,7 +1282,6 @@ impl Document {
Document {
node: Node::new_document_node(),
window: JS::from_ref(window),
- idmap: DOMRefCell::new(HashMap::new()),
implementation: Default::default(),
location: Default::default(),
content_type: match content_type {
@@ -1297,6 +1300,10 @@ impl Document {
// https://dom.spec.whatwg.org/#concept-document-encoding
encoding_name: DOMRefCell::new(DOMString("UTF-8".to_owned())),
is_html_document: is_html_document == IsHTMLDocument::HTMLDocument,
+ id_map: DOMRefCell::new(HashMap::new()),
+ tag_map: DOMRefCell::new(HashMap::new()),
+ tagns_map: DOMRefCell::new(HashMap::new()),
+ classes_map: DOMRefCell::new(HashMap::new()),
images: Default::default(),
embeds: Default::default(),
links: Default::default(),
@@ -1386,7 +1393,7 @@ impl Document {
}
pub fn get_element_by_id(&self, id: &Atom) -> Option<Root<Element>> {
- self.idmap.borrow().get(&id).map(|ref elements| Root::from_ref(&*(*elements)[0]))
+ self.id_map.borrow().get(&id).map(|ref elements| Root::from_ref(&*(*elements)[0]))
}
pub fn record_element_state_change(&self, el: &Element, which: ElementState) {
@@ -1504,18 +1511,47 @@ impl DocumentMethods for Document {
// https://dom.spec.whatwg.org/#dom-document-getelementsbytagname
fn GetElementsByTagName(&self, tag_name: DOMString) -> Root<HTMLCollection> {
- HTMLCollection::by_tag_name(&self.window, self.upcast(), tag_name)
+ let tag_atom = Atom::from_slice(&tag_name);
+ match self.tag_map.borrow_mut().entry(tag_atom.clone()) {
+ Occupied(entry) => Root::from_ref(entry.get()),
+ Vacant(entry) => {
+ let mut tag_copy = tag_name;
+ tag_copy.make_ascii_lowercase();
+ let ascii_lower_tag = Atom::from_slice(&tag_copy);
+ let result = HTMLCollection::by_atomic_tag_name(&self.window, self.upcast(), tag_atom, ascii_lower_tag);
+ entry.insert(JS::from_rooted(&result));
+ result
+ }
+ }
}
// https://dom.spec.whatwg.org/#dom-document-getelementsbytagnamens
fn GetElementsByTagNameNS(&self, maybe_ns: Option<DOMString>, tag_name: DOMString)
-> Root<HTMLCollection> {
- HTMLCollection::by_tag_name_ns(&self.window, self.upcast(), tag_name, maybe_ns)
+ let ns = namespace_from_domstring(maybe_ns);
+ let local = Atom::from_slice(&tag_name);
+ let qname = QualName::new(ns, local);
+ match self.tagns_map.borrow_mut().entry(qname.clone()) {
+ Occupied(entry) => Root::from_ref(entry.get()),
+ Vacant(entry) => {
+ let result = HTMLCollection::by_qual_tag_name(&self.window, self.upcast(), qname);
+ entry.insert(JS::from_rooted(&result));
+ result
+ }
+ }
}
// https://dom.spec.whatwg.org/#dom-document-getelementsbyclassname
fn GetElementsByClassName(&self, classes: DOMString) -> Root<HTMLCollection> {
- HTMLCollection::by_class_name(&self.window, self.upcast(), classes)
+ let class_atoms: Vec<Atom> = split_html_space_chars(&classes).map(Atom::from_slice).collect();
+ match self.classes_map.borrow_mut().entry(class_atoms.clone()) {
+ Occupied(entry) => Root::from_ref(entry.get()),
+ Vacant(entry) => {
+ let result = HTMLCollection::by_atomic_class_name(&self.window, self.upcast(), class_atoms);
+ entry.insert(JS::from_rooted(&result));
+ result
+ }
+ }
}
// https://dom.spec.whatwg.org/#dom-nonelementparentnode-getelementbyid
diff --git a/components/script/dom/htmlcollection.rs b/components/script/dom/htmlcollection.rs
index 18b495a6f00..b645449dcc1 100644
--- a/components/script/dom/htmlcollection.rs
+++ b/components/script/dom/htmlcollection.rs
@@ -6,76 +6,169 @@ use dom::bindings::codegen::Bindings::HTMLCollectionBinding;
use dom::bindings::codegen::Bindings::HTMLCollectionBinding::HTMLCollectionMethods;
use dom::bindings::global::GlobalRef;
use dom::bindings::inheritance::Castable;
-use dom::bindings::js::{JS, Root};
+use dom::bindings::js::{JS, Root, MutNullableHeap};
use dom::bindings::reflector::{Reflector, reflect_dom_object};
use dom::bindings::trace::JSTraceable;
use dom::bindings::xmlname::namespace_from_domstring;
use dom::element::Element;
-use dom::node::{Node, TreeIterator};
+use dom::node::{Node, FollowingNodeIterator, PrecedingNodeIterator};
use dom::window::Window;
use std::ascii::AsciiExt;
-use string_cache::{Atom, Namespace};
+use std::cell::Cell;
+use string_cache::{Atom, Namespace, QualName};
use util::str::{DOMString, split_html_space_chars};
pub trait CollectionFilter : JSTraceable {
fn filter<'a>(&self, elem: &'a Element, root: &'a Node) -> bool;
}
-#[derive(JSTraceable)]
-#[must_root]
-pub struct Collection(JS<Node>, Box<CollectionFilter + 'static>);
+// An optional u32, using maxint to represent None.
+// It would be nicer just to use Option<u32> for this, but that would produce word
+// alignment issues since Option<u32> uses 33 bits.
+#[derive(Clone, Copy, JSTraceable, HeapSizeOf)]
+struct OptionU32 {
+ bits: u32,
+}
+
+impl OptionU32 {
+ fn to_option(self) -> Option<u32> {
+ if self.bits == u32::max_value() {
+ None
+ } else {
+ Some(self.bits)
+ }
+ }
+
+ fn some(bits: u32) -> OptionU32 {
+ assert!(bits != u32::max_value());
+ OptionU32 { bits: bits }
+ }
+
+ fn none() -> OptionU32 {
+ OptionU32 { bits: u32::max_value() }
+ }
+}
#[dom_struct]
pub struct HTMLCollection {
reflector_: Reflector,
+ root: JS<Node>,
#[ignore_heap_size_of = "Contains a trait object; can't measure due to #6870"]
- collection: Collection,
+ filter: Box<CollectionFilter + 'static>,
+ // We cache the version of the root node and all its decendents,
+ // the length of the collection, and a cursor into the collection.
+ // FIXME: make the cached cursor element a weak pointer
+ cached_version: Cell<u64>,
+ cached_cursor_element: MutNullableHeap<JS<Element>>,
+ cached_cursor_index: Cell<OptionU32>,
+ cached_length: Cell<OptionU32>,
}
impl HTMLCollection {
#[allow(unrooted_must_root)]
- fn new_inherited(collection: Collection) -> HTMLCollection {
+ fn new_inherited(root: &Node, filter: Box<CollectionFilter + 'static>) -> HTMLCollection {
HTMLCollection {
reflector_: Reflector::new(),
- collection: collection,
+ root: JS::from_ref(root),
+ filter: filter,
+ // Default values for the cache
+ cached_version: Cell::new(root.get_inclusive_descendants_version()),
+ cached_cursor_element: MutNullableHeap::new(None),
+ cached_cursor_index: Cell::new(OptionU32::none()),
+ cached_length: Cell::new(OptionU32::none()),
}
}
#[allow(unrooted_must_root)]
- pub fn new(window: &Window, collection: Collection) -> Root<HTMLCollection> {
- reflect_dom_object(box HTMLCollection::new_inherited(collection),
+ pub fn new(window: &Window, root: &Node, filter: Box<CollectionFilter + 'static>) -> Root<HTMLCollection> {
+ reflect_dom_object(box HTMLCollection::new_inherited(root, filter),
GlobalRef::Window(window), HTMLCollectionBinding::Wrap)
}
pub fn create(window: &Window, root: &Node,
filter: Box<CollectionFilter + 'static>) -> Root<HTMLCollection> {
- HTMLCollection::new(window, Collection(JS::from_ref(root), filter))
+ HTMLCollection::new(window, root, filter)
}
- fn all_elements(window: &Window, root: &Node,
- namespace_filter: Option<Namespace>) -> Root<HTMLCollection> {
- #[derive(JSTraceable, HeapSizeOf)]
- struct AllElementFilter {
- namespace_filter: Option<Namespace>
+ fn validate_cache(&self) {
+ // Clear the cache if the root version is different from our cached version
+ let cached_version = self.cached_version.get();
+ let curr_version = self.root.get_inclusive_descendants_version();
+ if curr_version != cached_version {
+ // Default values for the cache
+ self.cached_version.set(curr_version);
+ self.cached_cursor_element.set(None);
+ self.cached_length.set(OptionU32::none());
+ self.cached_cursor_index.set(OptionU32::none());
}
- impl CollectionFilter for AllElementFilter {
- fn filter(&self, elem: &Element, _root: &Node) -> bool {
- match self.namespace_filter {
- None => true,
- Some(ref namespace) => *elem.namespace() == *namespace
+ }
+
+ fn get_length(&self) -> u32 {
+ // Call validate_cache before calling this method!
+ if let Some(cached_length) = self.cached_length.get().to_option() {
+ // Cache hit
+ cached_length
+ } else {
+ // Cache miss, calculate the length
+ let length = self.elements_iter().count() as u32;
+ self.cached_length.set(OptionU32::some(length));
+ length
+ }
+ }
+
+ fn set_cached_cursor(&self, index: u32, element: Option<Root<Element>>) -> Option<Root<Element>> {
+ if let Some(element) = element {
+ self.cached_cursor_index.set(OptionU32::some(index));
+ self.cached_cursor_element.set(Some(element.r()));
+ Some(element)
+ } else {
+ None
+ }
+ }
+
+ fn get_item(&self, index: u32) -> Option<Root<Element>> {
+ // Call validate_cache before calling this method!
+ if let Some(element) = self.cached_cursor_element.get() {
+ // Cache hit, the cursor element is set
+ if let Some(cached_index) = self.cached_cursor_index.get().to_option() {
+ if cached_index == index {
+ // The cursor is the element we're looking for
+ Some(element)
+ } else if cached_index < index {
+ // The cursor is before the element we're looking for
+ // Iterate forwards, starting at the cursor.
+ let offset = index - (cached_index + 1);
+ let node: Root<Node> = Root::upcast(element);
+ self.set_cached_cursor(index, self.elements_iter_after(node.r()).nth(offset as usize))
+ } else {
+ // The cursor is after the element we're looking for
+ // Iterate backwards, starting at the cursor.
+ let offset = cached_index - (index + 1);
+ let node: Root<Node> = Root::upcast(element);
+ self.set_cached_cursor(index, self.elements_iter_before(node.r()).nth(offset as usize))
}
+ } else {
+ // Cache miss
+ // Iterate forwards through all the nodes
+ self.set_cached_cursor(index, self.elements_iter().nth(index as usize))
}
+ } else {
+ // Cache miss
+ // Iterate forwards through all the nodes
+ self.set_cached_cursor(index, self.elements_iter().nth(index as usize))
}
- let filter = AllElementFilter { namespace_filter: namespace_filter };
- HTMLCollection::create(window, root, box filter)
}
pub fn by_tag_name(window: &Window, root: &Node, mut tag: DOMString)
-> Root<HTMLCollection> {
- if tag == "*" {
- return HTMLCollection::all_elements(window, root, None);
- }
+ let tag_atom = Atom::from_slice(&tag);
+ tag.make_ascii_lowercase();
+ let ascii_lower_tag = Atom::from_slice(&tag);
+ HTMLCollection::by_atomic_tag_name(window, root, tag_atom, ascii_lower_tag)
+ }
+ pub fn by_atomic_tag_name(window: &Window, root: &Node, tag_atom: Atom, ascii_lower_tag: Atom)
+ -> Root<HTMLCollection> {
#[derive(JSTraceable, HeapSizeOf)]
struct TagNameFilter {
tag: Atom,
@@ -83,16 +176,15 @@ impl HTMLCollection {
}
impl CollectionFilter for TagNameFilter {
fn filter(&self, elem: &Element, _root: &Node) -> bool {
- if elem.html_element_in_html_document() {
+ if self.tag == atom!("*") {
+ true
+ } else if elem.html_element_in_html_document() {
*elem.local_name() == self.ascii_lower_tag
} else {
*elem.local_name() == self.tag
}
}
}
- let tag_atom = Atom::from_slice(&tag);
- tag.make_ascii_lowercase();
- let ascii_lower_tag = Atom::from_slice(&tag);
let filter = TagNameFilter {
tag: tag_atom,
ascii_lower_tag: ascii_lower_tag,
@@ -102,39 +194,37 @@ impl HTMLCollection {
pub fn by_tag_name_ns(window: &Window, root: &Node, tag: DOMString,
maybe_ns: Option<DOMString>) -> Root<HTMLCollection> {
- let namespace_filter = match maybe_ns {
- Some(ref namespace) if namespace == &"*" => None,
- ns => Some(namespace_from_domstring(ns)),
- };
+ let local = Atom::from_slice(&tag);
+ let ns = namespace_from_domstring(maybe_ns);
+ let qname = QualName::new(ns, local);
+ HTMLCollection::by_qual_tag_name(window, root, qname)
+ }
- if tag == "*" {
- return HTMLCollection::all_elements(window, root, namespace_filter);
- }
+ pub fn by_qual_tag_name(window: &Window, root: &Node, qname: QualName) -> Root<HTMLCollection> {
#[derive(JSTraceable, HeapSizeOf)]
struct TagNameNSFilter {
- tag: Atom,
- namespace_filter: Option<Namespace>
+ qname: QualName
}
impl CollectionFilter for TagNameNSFilter {
fn filter(&self, elem: &Element, _root: &Node) -> bool {
- let ns_match = match self.namespace_filter {
- Some(ref namespace) => {
- *elem.namespace() == *namespace
- },
- None => true
- };
- ns_match && *elem.local_name() == self.tag
+ ((self.qname.ns == Namespace(atom!("*"))) || (self.qname.ns == *elem.namespace()))
+ && ((self.qname.local == atom!("*")) || (self.qname.local == *elem.local_name()))
}
}
let filter = TagNameNSFilter {
- tag: Atom::from_slice(&tag),
- namespace_filter: namespace_filter
+ qname: qname
};
HTMLCollection::create(window, root, box filter)
}
pub fn by_class_name(window: &Window, root: &Node, classes: DOMString)
-> Root<HTMLCollection> {
+ let class_atoms = split_html_space_chars(&classes).map(Atom::from_slice).collect();
+ HTMLCollection::by_atomic_class_name(window, root, class_atoms)
+ }
+
+ pub fn by_atomic_class_name(window: &Window, root: &Node, classes: Vec<Atom>)
+ -> Root<HTMLCollection> {
#[derive(JSTraceable, HeapSizeOf)]
struct ClassNameFilter {
classes: Vec<Atom>
@@ -145,9 +235,7 @@ impl HTMLCollection {
}
}
let filter = ClassNameFilter {
- classes: split_html_space_chars(&classes).map(|class| {
- Atom::from_slice(class)
- }).collect()
+ classes: classes
};
HTMLCollection::create(window, root, box filter)
}
@@ -163,21 +251,34 @@ impl HTMLCollection {
HTMLCollection::create(window, root, box ElementChildFilter)
}
- pub fn elements_iter(&self) -> HTMLCollectionElementsIter {
- let ref filter = self.collection.1;
- let root = Root::from_ref(&*self.collection.0);
- let mut node_iter = root.traverse_preorder();
- let _ = node_iter.next(); // skip the root node
+ pub fn elements_iter_after(&self, after: &Node) -> HTMLCollectionElementsIter {
+ // Iterate forwards from a node.
HTMLCollectionElementsIter {
- node_iter: node_iter,
- root: root,
- filter: filter,
+ node_iter: after.following_nodes(&self.root),
+ root: Root::from_ref(&self.root),
+ filter: &self.filter,
+ }
+ }
+
+ pub fn elements_iter(&self) -> HTMLCollectionElementsIter {
+ // Iterate forwards from the root.
+ self.elements_iter_after(&*self.root)
+ }
+
+ pub fn elements_iter_before(&self, before: &Node) -> HTMLCollectionElementsRevIter {
+ // Iterate backwards from a node.
+ HTMLCollectionElementsRevIter {
+ node_iter: before.preceding_nodes(&self.root),
+ root: Root::from_ref(&self.root),
+ filter: &self.filter,
}
}
+
}
+// TODO: Make this generic, and avoid code duplication
pub struct HTMLCollectionElementsIter<'a> {
- node_iter: TreeIterator,
+ node_iter: FollowingNodeIterator,
root: Root<Node>,
filter: &'a Box<CollectionFilter>,
}
@@ -186,24 +287,45 @@ impl<'a> Iterator for HTMLCollectionElementsIter<'a> {
type Item = Root<Element>;
fn next(&mut self) -> Option<Self::Item> {
- let filter = self.filter;
- let root = self.root.r();
+ let ref filter = self.filter;
+ let ref root = self.root;
self.node_iter.by_ref()
.filter_map(Root::downcast)
.filter(|element| filter.filter(&element, root))
.next()
+ }
+}
+
+pub struct HTMLCollectionElementsRevIter<'a> {
+ node_iter: PrecedingNodeIterator,
+ root: Root<Node>,
+ filter: &'a Box<CollectionFilter>,
+}
+
+impl<'a> Iterator for HTMLCollectionElementsRevIter<'a> {
+ type Item = Root<Element>;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ let ref filter = self.filter;
+ let ref root = self.root;
+ self.node_iter.by_ref()
+ .filter_map(Root::downcast)
+ .filter(|element| filter.filter(&element, root))
+ .next()
}
}
impl HTMLCollectionMethods for HTMLCollection {
// https://dom.spec.whatwg.org/#dom-htmlcollection-length
fn Length(&self) -> u32 {
- self.elements_iter().count() as u32
+ self.validate_cache();
+ self.get_length()
}
// https://dom.spec.whatwg.org/#dom-htmlcollection-item
fn Item(&self, index: u32) -> Option<Root<Element>> {
- self.elements_iter().nth(index as usize)
+ self.validate_cache();
+ self.get_item(index)
}
// https://dom.spec.whatwg.org/#dom-htmlcollection-nameditem
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-04 02:46:12 +0000