Doc named getter improvements

5 files changed, 284 insertions, 86 deletions

diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index 84a63d16238..1a45b0b82b7 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -146,6 +146,7 @@ use servo_media::{ClientContextId, ServoMedia};
 use servo_url::{ImmutableOrigin, MutableOrigin, ServoUrl};
 use std::borrow::Cow;
 use std::cell::Cell;
+use std::cmp::Ordering;
 use std::collections::hash_map::Entry::{Occupied, Vacant};
 use std::collections::{HashMap, HashSet, VecDeque};
 use std::default::Default;
@@ -243,6 +244,7 @@ pub struct Document {
     quirks_mode: Cell<QuirksMode>,
     /// Caches for the getElement methods
     id_map: DomRefCell<HashMap<Atom, Vec<Dom<Element>>>>,
+    name_map: DomRefCell<HashMap<Atom, Vec<Dom<Element>>>>,
     tag_map: DomRefCell<HashMap<LocalName, Dom<HTMLCollection>>>,
     tagns_map: DomRefCell<HashMap<QualName, Dom<HTMLCollection>>>,
     classes_map: DomRefCell<HashMap<Vec<Atom>, Dom<HTMLCollection>>>,
@@ -450,6 +452,12 @@ impl CollectionFilter for AnchorsFilter {
     }
 }
 
+enum ElementLookupResult {
+    None,
+    One(DomRoot<Element>),
+    Many,
+}
+
 #[allow(non_snake_case)]
 impl Document {
     #[inline]
@@ -709,14 +717,14 @@ impl Document {
     }
 
     /// Remove any existing association between the provided id and any elements in this document.
-    pub fn unregister_named_element(&self, to_unregister: &Element, id: Atom) {
+    pub fn unregister_element_id(&self, to_unregister: &Element, id: Atom) {
         self.document_or_shadow_root
             .unregister_named_element(&self.id_map, to_unregister, &id);
         self.reset_form_owner_for_listeners(&id);
     }
 
     /// Associate an element present in this document with the provided id.
-    pub fn register_named_element(&self, element: &Element, id: Atom) {
+    pub fn register_element_id(&self, element: &Element, id: Atom) {
         let root = self.GetDocumentElement().expect(
             "The element is in the document, so there must be a document \
              element.",
@@ -730,6 +738,26 @@ impl Document {
         self.reset_form_owner_for_listeners(&id);
     }
 
+    /// Remove any existing association between the provided name and any elements in this document.
+    pub fn unregister_element_name(&self, to_unregister: &Element, name: Atom) {
+        self.document_or_shadow_root
+            .unregister_named_element(&self.name_map, to_unregister, &name);
+    }
+
+    /// Associate an element present in this document with the provided name.
+    pub fn register_element_name(&self, element: &Element, name: Atom) {
+        let root = self.GetDocumentElement().expect(
+            "The element is in the document, so there must be a document \
+             element.",
+        );
+        self.document_or_shadow_root.register_named_element(
+            &self.name_map,
+            element,
+            &name,
+            DomRoot::from_ref(root.upcast::<Node>()),
+        );
+    }
+
     pub fn register_form_id_listener<T: ?Sized + FormControl>(&self, id: DOMString, listener: &T) {
         let mut map = self.form_id_listener_map.borrow_mut();
         let listener = listener.to_element();
@@ -823,18 +851,13 @@ impl Document {
     }
 
     fn get_anchor_by_name(&self, name: &str) -> Option<DomRoot<Element>> {
-        // TODO faster name lookups (see #25548)
-        let check_anchor = |node: &HTMLAnchorElement| {
-            let elem = node.upcast::<Element>();
-            elem.get_attribute(&ns!(), &local_name!("name"))
-                .map_or(false, |attr| &**attr.value() == name)
-        };
-        let doc_node = self.upcast::<Node>();
-        doc_node
-            .traverse_preorder(ShadowIncluding::No)
-            .filter_map(DomRoot::downcast)
-            .find(|node| check_anchor(&node))
-            .map(DomRoot::upcast)
+        let name = Atom::from(name);
+        self.name_map.borrow().get(&name).and_then(|elements| {
+            elements
+                .iter()
+                .find(|e| e.is::<HTMLAnchorElement>())
+                .map(|e| DomRoot::from_ref(&**e))
+        })
     }
 
     // https://html.spec.whatwg.org/multipage/#current-document-readiness
@@ -2524,6 +2547,75 @@ impl Document {
             .unwrap();
         receiver.recv().unwrap();
     }
+
+    // https://html.spec.whatwg.org/multipage/#dom-tree-accessors:supported-property-names
+    // (This takes the filter as a method so the window named getter can use it too)
+    pub fn supported_property_names_impl(
+        &self,
+        nameditem_filter: fn(&Node, &Atom) -> bool,
+    ) -> Vec<DOMString> {
+        // The tricky part here is making sure we return the names in
+        // tree order, without just resorting to a full tree walkthrough.
+
+        let mut first_elements_with_name: HashMap<&Atom, &Dom<Element>> = HashMap::new();
+
+        // Get the first-in-tree-order element for each name in the name_map
+        let name_map = self.name_map.borrow();
+        name_map.iter().for_each(|(name, value)| {
+            if let Some(first) = value
+                .iter()
+                .find(|n| nameditem_filter((***n).upcast::<Node>(), &name))
+            {
+                first_elements_with_name.insert(name, first);
+            }
+        });
+
+        // Get the first-in-tree-order element for each name in the id_map;
+        // if we already had one from the name_map, figure out which of
+        // the two is first.
+        let id_map = self.id_map.borrow();
+        id_map.iter().for_each(|(name, value)| {
+            if let Some(first) = value
+                .iter()
+                .find(|n| nameditem_filter((***n).upcast::<Node>(), &name))
+            {
+                match first_elements_with_name.get(&name) {
+                    None => {
+                        first_elements_with_name.insert(name, first);
+                    },
+                    Some(el) => {
+                        if *el != first && first.upcast::<Node>().is_before(el.upcast::<Node>()) {
+                            first_elements_with_name.insert(name, first);
+                        }
+                    },
+                }
+            }
+        });
+
+        // first_elements_with_name now has our supported property names
+        // as keys, and the elements to order on as values.
+        let mut sortable_vec: Vec<(&Atom, &Dom<Element>)> = first_elements_with_name
+            .iter()
+            .map(|(k, v)| (*k, *v))
+            .collect();
+        sortable_vec.sort_unstable_by(|a, b| {
+            if a.1 == b.1 {
+                // This can happen if an img has an id different from its name,
+                // spec does not say which string to put first.
+                a.0.cmp(&b.0)
+            } else if a.1.upcast::<Node>().is_before(b.1.upcast::<Node>()) {
+                Ordering::Less
+            } else {
+                Ordering::Greater
+            }
+        });
+
+        // And now that they're sorted, we can return the keys
+        sortable_vec
+            .iter()
+            .map(|(k, _v)| DOMString::from(&***k))
+            .collect()
+    }
 }
 
 fn is_character_value_key(key: &Key) -> bool {
@@ -2735,6 +2827,7 @@ impl Document {
             // https://dom.spec.whatwg.org/#concept-document-quirks
             quirks_mode: Cell::new(QuirksMode::NoQuirks),
             id_map: DomRefCell::new(HashMap::new()),
+            name_map: DomRefCell::new(HashMap::new()),
             // https://dom.spec.whatwg.org/#concept-document-encoding
             encoding: Cell::new(encoding),
             is_html_document: is_html_document == IsHTMLDocument::HTMLDocument,
@@ -3397,6 +3490,81 @@ impl Document {
             StylesheetSetRef::Document(&mut *self.stylesheets.borrow_mut()),
         )
     }
+
+    // https://html.spec.whatwg.org/multipage/#dom-tree-accessors:determine-the-value-of-a-named-property
+    // Support method for steps 1-3:
+    // Count if there are 0, 1, or >1 elements that match the name.
+    // (This takes the filter as a method so the window named getter can use it too)
+    fn look_up_named_elements(
+        &self,
+        name: &Atom,
+        nameditem_filter: fn(&Node, &Atom) -> bool,
+    ) -> ElementLookupResult {
+        // We might match because of either id==name or name==name, so there
+        // are two sets of nodes to look through, but we don't need a
+        // full tree traversal.
+        let id_map = self.id_map.borrow();
+        let name_map = self.name_map.borrow();
+        let id_vec = id_map.get(&name);
+        let name_vec = name_map.get(&name);
+
+        // If nothing can possibly have the name, exit fast
+        if id_vec.is_none() && name_vec.is_none() {
+            return ElementLookupResult::None;
+        }
+
+        let one_from_id_map = if let Some(id_vec) = id_vec {
+            let mut elements = id_vec
+                .iter()
+                .filter(|n| nameditem_filter((***n).upcast::<Node>(), &name))
+                .peekable();
+            if let Some(first) = elements.next() {
+                if elements.peek().is_none() {
+                    Some(first)
+                } else {
+                    return ElementLookupResult::Many;
+                }
+            } else {
+                None
+            }
+        } else {
+            None
+        };
+
+        let one_from_name_map = if let Some(name_vec) = name_vec {
+            let mut elements = name_vec
+                .iter()
+                .filter(|n| nameditem_filter((***n).upcast::<Node>(), &name))
+                .peekable();
+            if let Some(first) = elements.next() {
+                if elements.peek().is_none() {
+                    Some(first)
+                } else {
+                    return ElementLookupResult::Many;
+                }
+            } else {
+                None
+            }
+        } else {
+            None
+        };
+
+        // We now have two elements, or one element, or the same
+        // element twice, or no elements.
+        match (one_from_id_map, one_from_name_map) {
+            (Some(one), None) | (None, Some(one)) => {
+                ElementLookupResult::One(DomRoot::from_ref(&one))
+            },
+            (Some(one), Some(other)) => {
+                if one == other {
+                    ElementLookupResult::One(DomRoot::from_ref(&one))
+                } else {
+                    ElementLookupResult::Many
+                }
+            },
+            (None, None) => ElementLookupResult::None,
+        }
+    }
 }
 
 impl Element {
@@ -4297,69 +4465,39 @@ impl DocumentMethods for Document {
         }
         impl CollectionFilter for NamedElementFilter {
             fn filter(&self, elem: &Element, _root: &Node) -> bool {
-                filter_by_name(&self.name, elem.upcast())
-            }
-        }
-        // https://html.spec.whatwg.org/multipage/#dom-document-nameditem-filter
-        fn filter_by_name(name: &Atom, node: &Node) -> bool {
-            // TODO faster name lookups (see #25548)
-            let html_elem_type = match node.type_id() {
-                NodeTypeId::Element(ElementTypeId::HTMLElement(type_)) => type_,
-                _ => return false,
-            };
-            let elem = match node.downcast::<Element>() {
-                Some(elem) => elem,
-                None => return false,
-            };
-            match html_elem_type {
-                HTMLElementTypeId::HTMLFormElement => {
-                    match elem.get_attribute(&ns!(), &local_name!("name")) {
-                        Some(ref attr) => attr.value().as_atom() == name,
-                        None => false,
-                    }
-                },
-                HTMLElementTypeId::HTMLImageElement => {
-                    match elem.get_attribute(&ns!(), &local_name!("name")) {
-                        Some(ref attr) => {
-                            if attr.value().as_atom() == name {
-                                true
-                            } else {
-                                match elem.get_attribute(&ns!(), &local_name!("id")) {
-                                    Some(ref attr) => attr.value().as_atom() == name,
-                                    None => false,
-                                }
-                            }
-                        },
-                        None => false,
-                    }
-                },
-                // TODO: Handle <embed>, <iframe> and <object>.
-                _ => false,
+                elem.upcast::<Node>().is_document_named_item(&self.name)
             }
         }
+
         let name = Atom::from(name);
-        let root = self.upcast::<Node>();
-        unsafe {
-            // Step 1.
-            let mut elements = root
-                .traverse_preorder(ShadowIncluding::No)
-                .filter(|node| filter_by_name(&name, &node))
-                .peekable();
-            if let Some(first) = elements.next() {
-                if elements.peek().is_none() {
-                    // TODO: Step 2.
-                    // Step 3.
+
+        match self.look_up_named_elements(&name, Node::is_document_named_item) {
+            ElementLookupResult::None => {
+                return None;
+            },
+            ElementLookupResult::One(element) => {
+                if let Some(nested_proxy) = element
+                    .downcast::<HTMLIFrameElement>()
+                    .and_then(|iframe| iframe.GetContentWindow())
+                {
+                    unsafe {
+                        return Some(NonNull::new_unchecked(
+                            nested_proxy.reflector().get_jsobject().get(),
+                        ));
+                    }
+                }
+                unsafe {
                     return Some(NonNull::new_unchecked(
-                        first.reflector().get_jsobject().get(),
+                        element.reflector().get_jsobject().get(),
                     ));
                 }
-            } else {
-                return None;
-            }
-        }
+            },
+            ElementLookupResult::Many => {},
+        };
+
         // Step 4.
         let filter = NamedElementFilter { name: name };
-        let collection = HTMLCollection::create(self.window(), root, Box::new(filter));
+        let collection = HTMLCollection::create(self.window(), self.upcast(), Box::new(filter));
         unsafe {
             Some(NonNull::new_unchecked(
                 collection.reflector().get_jsobject().get(),
@@ -4369,8 +4507,7 @@ impl DocumentMethods for Document {
 
     // https://html.spec.whatwg.org/multipage/#dom-tree-accessors:supported-property-names
     fn SupportedPropertyNames(&self) -> Vec<DOMString> {
-        // FIXME: unimplemented (https://github.com/servo/servo/issues/7273)
-        vec![]
+        self.supported_property_names_impl(Node::is_document_named_item)
     }
 
     // https://html.spec.whatwg.org/multipage/#dom-document-clear
diff --git a/components/script/dom/documentorshadowroot.rs b/components/script/dom/documentorshadowroot.rs
index 724ea11da8c..5469287d87c 100644
--- a/components/script/dom/documentorshadowroot.rs
+++ b/components/script/dom/documentorshadowroot.rs
@@ -266,7 +266,7 @@ impl DocumentOrShadowRoot {
         }
     }
 
-    /// Remove any existing association between the provided id and any elements in this document.
+    /// Remove any existing association between the provided id/name and any elements in this document.
     pub fn unregister_named_element(
         &self,
         id_map: &DomRefCell<HashMap<Atom, Vec<Dom<Element>>>>,
@@ -294,7 +294,7 @@ impl DocumentOrShadowRoot {
         }
     }
 
-    /// Associate an element present in this document with the provided id.
+    /// Associate an element present in this document with the provided id/name.
     pub fn register_named_element(
         &self,
         id_map: &DomRefCell<HashMap<Atom, Vec<Dom<Element>>>>,
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 524502e36d6..4eb2f2a2609 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -1177,6 +1177,10 @@ impl Element {
         ns!()
     }
 
+    pub fn name_attribute(&self) -> Option<Atom> {
+        self.rare_data().as_ref()?.name_attribute.clone()
+    }
+
     pub fn style_attribute(&self) -> &DomRefCell<Option<Arc<Locked<PropertyDeclarationBlock>>>> {
         &self.style_attribute
     }
@@ -2803,25 +2807,25 @@ impl VirtualMethods for Element {
                             if let Some(old_value) = old_value {
                                 let old_value = old_value.as_atom().clone();
                                 if let Some(ref shadow_root) = containing_shadow_root {
-                                    shadow_root.unregister_named_element(self, old_value);
+                                    shadow_root.unregister_element_id(self, old_value);
                                 } else {
-                                    doc.unregister_named_element(self, old_value);
+                                    doc.unregister_element_id(self, old_value);
                                 }
                             }
                             if value != atom!("") {
                                 if let Some(ref shadow_root) = containing_shadow_root {
-                                    shadow_root.register_named_element(self, value);
+                                    shadow_root.register_element_id(self, value);
                                 } else {
-                                    doc.register_named_element(self, value);
+                                    doc.register_element_id(self, value);
                                 }
                             }
                         },
                         AttributeMutation::Removed => {
                             if value != atom!("") {
                                 if let Some(ref shadow_root) = containing_shadow_root {
-                                    shadow_root.unregister_named_element(self, value);
+                                    shadow_root.unregister_element_id(self, value);
                                 } else {
-                                    doc.unregister_named_element(self, value);
+                                    doc.unregister_element_id(self, value);
                                 }
                             }
                         },
@@ -2839,8 +2843,27 @@ impl VirtualMethods for Element {
                             None
                         }
                     });
-                // TODO: notify the document about the name change
-                // once it has a name_map (#25548)
+                // Keep the document name_map up to date
+                // (if we're not in shadow DOM)
+                if node.is_connected() && node.containing_shadow_root().is_none() {
+                    let value = attr.value().as_atom().clone();
+                    match mutation {
+                        AttributeMutation::Set(old_value) => {
+                            if let Some(old_value) = old_value {
+                                let old_value = old_value.as_atom().clone();
+                                doc.unregister_element_name(self, old_value);
+                            }
+                            if value != atom!("") {
+                                doc.register_element_name(self, value);
+                            }
+                        },
+                        AttributeMutation::Removed => {
+                            if value != atom!("") {
+                                doc.unregister_element_name(self, value);
+                            }
+                        },
+                    }
+                }
             },
             _ => {
                 // FIXME(emilio): This is pretty dubious, and should be done in
@@ -2896,11 +2919,17 @@ impl VirtualMethods for Element {
 
         if let Some(ref value) = *self.id_attribute.borrow() {
             if let Some(shadow_root) = self.upcast::<Node>().containing_shadow_root() {
-                shadow_root.register_named_element(self, value.clone());
+                shadow_root.register_element_id(self, value.clone());
             } else {
-                doc.register_named_element(self, value.clone());
+                doc.register_element_id(self, value.clone());
+            }
+        }
+        if let Some(ref value) = self.name_attribute() {
+            if self.upcast::<Node>().containing_shadow_root().is_none() {
+                doc.register_element_name(self, value.clone());
             }
         }
+
         // This is used for layout optimization.
         doc.increment_dom_count();
     }
@@ -2933,7 +2962,10 @@ impl VirtualMethods for Element {
             doc.exit_fullscreen();
         }
         if let Some(ref value) = *self.id_attribute.borrow() {
-            doc.unregister_named_element(self, value.clone());
+            doc.unregister_element_id(self, value.clone());
+        }
+        if let Some(ref value) = self.name_attribute() {
+            doc.unregister_element_name(self, value.clone());
         }
         // This is used for layout optimization.
         doc.decrement_dom_count();
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index b6d4389d441..1cbba04ad16 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -83,6 +83,7 @@ use script_traits::UntrustedNodeAddress;
 use selectors::matching::{matches_selector_list, MatchingContext, MatchingMode};
 use selectors::parser::SelectorList;
 use servo_arc::Arc;
+use servo_atoms::Atom;
 use servo_url::ServoUrl;
 use smallvec::SmallVec;
 use std::borrow::ToOwned;
@@ -1170,6 +1171,34 @@ impl Node {
             );
         }
     }
+
+    // https://html.spec.whatwg.org/multipage/#dom-document-nameditem-filter
+    pub fn is_document_named_item(&self, name: &Atom) -> bool {
+        let html_elem_type = match self.type_id() {
+            NodeTypeId::Element(ElementTypeId::HTMLElement(type_)) => type_,
+            _ => return false,
+        };
+        let elem = self
+            .downcast::<Element>()
+            .expect("Node with an Element::HTMLElement NodeTypeID must be an Element");
+        match html_elem_type {
+            HTMLElementTypeId::HTMLFormElement | HTMLElementTypeId::HTMLIFrameElement => {
+                elem.get_name().map_or(false, |n| n == *name)
+            },
+            HTMLElementTypeId::HTMLImageElement =>
+            // Images can match by id, but only when their name is non-empty.
+            {
+                elem.get_name().map_or(false, |n| {
+                    n == *name || elem.get_id().map_or(false, |i| i == *name)
+                })
+            },
+            // TODO: Handle <embed> and <object>; these depend on
+            // whether the element is "exposed", a concept which
+            // doesn't fully make sense until embed/object behaviors
+            // are actually implemented.
+            _ => false,
+        }
+    }
 }
 
 /// Iterate through `nodes` until we find a `Node` that is not in `not_in`
diff --git a/components/script/dom/shadowroot.rs b/components/script/dom/shadowroot.rs
index d6df87bded8..0b791476f7c 100644
--- a/components/script/dom/shadowroot.rs
+++ b/components/script/dom/shadowroot.rs
@@ -145,7 +145,7 @@ impl ShadowRoot {
 
     /// Remove any existing association between the provided id and any elements
     /// in this shadow tree.
-    pub fn unregister_named_element(&self, to_unregister: &Element, id: Atom) {
+    pub fn unregister_element_id(&self, to_unregister: &Element, id: Atom) {
         self.document_or_shadow_root.unregister_named_element(
             self.document_fragment.id_map(),
             to_unregister,
@@ -154,7 +154,7 @@ impl ShadowRoot {
     }
 
     /// Associate an element present in this shadow tree with the provided id.
-    pub fn register_named_element(&self, element: &Element, id: Atom) {
+    pub fn register_element_id(&self, element: &Element, id: Atom) {
         let root = self
             .upcast::<Node>()
             .inclusive_ancestors(ShadowIncluding::No)