Labels are a live list in tree order

12 files changed, 161 insertions, 70 deletions

diff --git a/components/script/dom/htmlbuttonelement.rs b/components/script/dom/htmlbuttonelement.rs
index 6a60a88b25c..b7c7da1e9bf 100755
--- a/components/script/dom/htmlbuttonelement.rs
+++ b/components/script/dom/htmlbuttonelement.rs
@@ -41,6 +41,7 @@ pub struct HTMLButtonElement {
     htmlelement: HTMLElement,
     button_type: Cell<ButtonType>,
     form_owner: MutNullableDom<HTMLFormElement>,
+    labels_node_list: MutNullableDom<NodeList>,
 }
 
 impl HTMLButtonElement {
@@ -58,6 +59,7 @@ impl HTMLButtonElement {
             ),
             button_type: Cell::new(ButtonType::Submit),
             form_owner: Default::default(),
+            labels_node_list: Default::default(),
         }
     }
 
@@ -149,9 +151,7 @@ impl HTMLButtonElementMethods for HTMLButtonElement {
     make_setter!(SetValue, "value");
 
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    fn Labels(&self) -> DomRoot<NodeList> {
-        self.upcast::<HTMLElement>().labels()
-    }
+    make_labels_getter!(Labels, labels_node_list);
 }
 
 impl HTMLButtonElement {
diff --git a/components/script/dom/htmlelement.rs b/components/script/dom/htmlelement.rs
index 7bec738f382..c5b7e6d0251 100644
--- a/components/script/dom/htmlelement.rs
+++ b/components/script/dom/htmlelement.rs
@@ -4,10 +4,10 @@
 
 use crate::dom::activation::{synthetic_click_activation, ActivationSource};
 use crate::dom::attr::Attr;
-use crate::dom::bindings::codegen::Bindings::ElementBinding::ElementMethods;
 use crate::dom::bindings::codegen::Bindings::EventHandlerBinding::EventHandlerNonNull;
 use crate::dom::bindings::codegen::Bindings::HTMLElementBinding;
 use crate::dom::bindings::codegen::Bindings::HTMLElementBinding::HTMLElementMethods;
+use crate::dom::bindings::codegen::Bindings::HTMLLabelElementBinding::HTMLLabelElementMethods;
 use crate::dom::bindings::codegen::Bindings::NodeBinding::NodeBinding::NodeMethods;
 use crate::dom::bindings::codegen::Bindings::WindowBinding::WindowMethods;
 use crate::dom::bindings::error::{Error, ErrorResult};
@@ -29,7 +29,6 @@ use crate::dom::htmlinputelement::{HTMLInputElement, InputType};
 use crate::dom::htmllabelelement::HTMLLabelElement;
 use crate::dom::node::{document_from_node, window_from_node};
 use crate::dom::node::{BindContext, Node, NodeFlags, ShadowIncluding};
-use crate::dom::nodelist::NodeList;
 use crate::dom::text::Text;
 use crate::dom::virtualmethods::VirtualMethods;
 use dom_struct::dom_struct;
@@ -677,43 +676,48 @@ impl HTMLElement {
     }
 
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    pub fn labels(&self) -> DomRoot<NodeList> {
-        debug_assert!(self.is_labelable_element());
-
+    // This gets the nth label in tree order.
+    pub fn label_at(&self, index: u32) -> Option<DomRoot<Node>> {
         let element = self.upcast::<Element>();
-        let window = window_from_node(element);
-
-        // Traverse ancestors for implicitly associated <label> elements
-        // https://html.spec.whatwg.org/multipage/#the-label-element:attr-label-for-4
-        let ancestors = self
-            .upcast::<Node>()
-            .ancestors()
-            .filter_map(DomRoot::downcast::<HTMLElement>)
-            // If we reach a labelable element, we have a guarantee no ancestors above it
-            // will be a label for this HTMLElement
-            .take_while(|elem| !elem.is_labelable_element())
-            .filter_map(DomRoot::downcast::<HTMLLabelElement>)
-            .filter(|elem| !elem.upcast::<Element>().has_attribute(&local_name!("for")))
-            .filter(|elem| elem.first_labelable_descendant().as_deref() == Some(self))
-            .map(DomRoot::upcast::<Node>);
 
-        let id = element.Id();
-        let id = match &id as &str {
-            "" => return NodeList::new_simple_list(&window, ancestors),
-            id => id,
-        };
-
-        // Traverse entire tree for <label> elements with `for` attribute matching `id`
+        // Traverse entire tree for <label> elements that have
+        // this as their control.
+        // There is room for performance optimization, as we don't need
+        // the actual result of GetControl, only whether the result
+        // would match self.
+        // (Even more room for performance optimization: do what
+        // nodelist ChildrenList does and keep a mutation-aware cursor
+        // around; this may be hard since labels need to keep working
+        // even as they get detached into a subtree and reattached to
+        // a document.)
         let root_element = element.root_element();
         let root_node = root_element.upcast::<Node>();
-        let children = root_node
+        root_node
             .traverse_preorder(ShadowIncluding::No)
-            .filter_map(DomRoot::downcast::<Element>)
-            .filter(|elem| elem.is::<HTMLLabelElement>())
-            .filter(|elem| elem.get_string_attribute(&local_name!("for")) == id)
-            .map(DomRoot::upcast::<Node>);
+            .filter_map(DomRoot::downcast::<HTMLLabelElement>)
+            .filter(|elem| match elem.GetControl() {
+                Some(control) => &*control == self,
+                _ => false,
+            })
+            .nth(index as usize)
+            .map(|n| DomRoot::from_ref(n.upcast::<Node>()))
+    }
 
-        NodeList::new_simple_list(&window, children.chain(ancestors))
+    // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
+    // This counts the labels of the element, to support NodeList::Length
+    pub fn labels_count(&self) -> u32 {
+        // see label_at comments about performance
+        let element = self.upcast::<Element>();
+        let root_element = element.root_element();
+        let root_node = root_element.upcast::<Node>();
+        root_node
+            .traverse_preorder(ShadowIncluding::No)
+            .filter_map(DomRoot::downcast::<HTMLLabelElement>)
+            .filter(|elem| match elem.GetControl() {
+                Some(control) => &*control == self,
+                _ => false,
+            })
+            .count() as u32
     }
 }
 
diff --git a/components/script/dom/htmlinputelement.rs b/components/script/dom/htmlinputelement.rs
index 962ccc8161f..90058f303a9 100755
--- a/components/script/dom/htmlinputelement.rs
+++ b/components/script/dom/htmlinputelement.rs
@@ -234,6 +234,7 @@ pub struct HTMLInputElement {
 
     filelist: MutNullableDom<FileList>,
     form_owner: MutNullableDom<HTMLFormElement>,
+    labels_node_list: MutNullableDom<NodeList>,
 }
 
 #[derive(JSTraceable)]
@@ -303,6 +304,7 @@ impl HTMLInputElement {
             value_dirty: Cell::new(false),
             filelist: MutNullableDom::new(None),
             form_owner: Default::default(),
+            labels_node_list: MutNullableDom::new(None),
         }
     }
 
@@ -791,12 +793,18 @@ impl HTMLInputElementMethods for HTMLInputElement {
     }
 
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    fn Labels(&self) -> DomRoot<NodeList> {
+    // Different from make_labels_getter because this one
+    // conditionally returns null.
+    fn GetLabels(&self) -> Option<DomRoot<NodeList>> {
         if self.input_type() == InputType::Hidden {
-            let window = window_from_node(self);
-            NodeList::empty(&window)
+            None
         } else {
-            self.upcast::<HTMLElement>().labels()
+            Some(self.labels_node_list.or_init(|| {
+                NodeList::new_labels_list(
+                    self.upcast::<Node>().owner_doc().window(),
+                    self.upcast::<HTMLElement>(),
+                )
+            }))
         }
     }
 
diff --git a/components/script/dom/htmllabelelement.rs b/components/script/dom/htmllabelelement.rs
index 0a1401d6283..cca8e0f03c9 100644
--- a/components/script/dom/htmllabelelement.rs
+++ b/components/script/dom/htmllabelelement.rs
@@ -4,8 +4,11 @@
 
 use crate::dom::activation::{synthetic_click_activation, Activatable, ActivationSource};
 use crate::dom::attr::Attr;
+use crate::dom::bindings::codegen::Bindings::AttrBinding::AttrMethods;
+use crate::dom::bindings::codegen::Bindings::ElementBinding::ElementMethods;
 use crate::dom::bindings::codegen::Bindings::HTMLLabelElementBinding;
 use crate::dom::bindings::codegen::Bindings::HTMLLabelElementBinding::HTMLLabelElementMethods;
+use crate::dom::bindings::codegen::Bindings::NodeBinding::{GetRootNodeOptions, NodeMethods};
 use crate::dom::bindings::inheritance::Castable;
 use crate::dom::bindings::root::DomRoot;
 use crate::dom::bindings::str::DOMString;
@@ -15,7 +18,7 @@ use crate::dom::event::Event;
 use crate::dom::eventtarget::EventTarget;
 use crate::dom::htmlelement::HTMLElement;
 use crate::dom::htmlformelement::{FormControl, FormControlElementHelpers, HTMLFormElement};
-use crate::dom::node::{document_from_node, Node, ShadowIncluding};
+use crate::dom::node::{Node, ShadowIncluding};
 use crate::dom::virtualmethods::VirtualMethods;
 use dom_struct::dom_struct;
 use html5ever::{LocalName, Prefix};
@@ -99,10 +102,6 @@ impl HTMLLabelElementMethods for HTMLLabelElement {
 
     // https://html.spec.whatwg.org/multipage/#dom-label-control
     fn GetControl(&self) -> Option<DomRoot<HTMLElement>> {
-        if !self.upcast::<Node>().is_in_doc() {
-            return None;
-        }
-
         let for_attr = match self
             .upcast::<Element>()
             .get_attribute(&ns!(), &local_name!("for"))
@@ -111,13 +110,40 @@ impl HTMLLabelElementMethods for HTMLLabelElement {
             None => return self.first_labelable_descendant(),
         };
 
-        let for_value = for_attr.value();
-        document_from_node(self)
-            .get_element_by_id(for_value.as_atom())
-            .and_then(DomRoot::downcast::<HTMLElement>)
-            .into_iter()
-            .filter(|e| e.is_labelable_element())
-            .next()
+        let for_value = for_attr.Value();
+
+        // "If the attribute is specified and there is an element in the tree
+        // whose ID is equal to the value of the for attribute, and the first
+        // such element in tree order is a labelable element, then that
+        // element is the label element's labeled control."
+        // Two subtle points here: we need to search the _tree_, which is
+        // not necessarily the document if we're detached from the document,
+        // and we only consider one element even if a later element with
+        // the same ID is labelable.
+
+        let maybe_found = self
+            .upcast::<Node>()
+            .GetRootNode(&GetRootNodeOptions::empty())
+            .traverse_preorder(ShadowIncluding::No)
+            .find_map(|e| {
+                if let Some(htmle) = e.downcast::<HTMLElement>() {
+                    if htmle.upcast::<Element>().Id() == for_value {
+                        Some(DomRoot::from_ref(htmle))
+                    } else {
+                        None
+                    }
+                } else {
+                    None
+                }
+            });
+        // We now have the element that we would return, but only return it
+        // if it's labelable.
+        if let Some(ref maybe_labelable) = maybe_found {
+            if maybe_labelable.is_labelable_element() {
+                return maybe_found;
+            }
+        }
+        None
     }
 }
 
diff --git a/components/script/dom/htmlmeterelement.rs b/components/script/dom/htmlmeterelement.rs
index a627d9aee93..780080a6a65 100644
--- a/components/script/dom/htmlmeterelement.rs
+++ b/components/script/dom/htmlmeterelement.rs
@@ -6,7 +6,7 @@ use crate::dom::bindings::codegen::Bindings::HTMLMeterElementBinding::{
     self, HTMLMeterElementMethods,
 };
 use crate::dom::bindings::inheritance::Castable;
-use crate::dom::bindings::root::DomRoot;
+use crate::dom::bindings::root::{DomRoot, MutNullableDom};
 use crate::dom::document::Document;
 use crate::dom::htmlelement::HTMLElement;
 use crate::dom::node::Node;
@@ -17,6 +17,7 @@ use html5ever::{LocalName, Prefix};
 #[dom_struct]
 pub struct HTMLMeterElement {
     htmlelement: HTMLElement,
+    labels_node_list: MutNullableDom<NodeList>,
 }
 
 impl HTMLMeterElement {
@@ -27,6 +28,7 @@ impl HTMLMeterElement {
     ) -> HTMLMeterElement {
         HTMLMeterElement {
             htmlelement: HTMLElement::new_inherited(local_name, prefix, document),
+            labels_node_list: MutNullableDom::new(None),
         }
     }
 
@@ -48,7 +50,5 @@ impl HTMLMeterElement {
 
 impl HTMLMeterElementMethods for HTMLMeterElement {
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    fn Labels(&self) -> DomRoot<NodeList> {
-        self.upcast::<HTMLElement>().labels()
-    }
+    make_labels_getter!(Labels, labels_node_list);
 }
diff --git a/components/script/dom/htmloutputelement.rs b/components/script/dom/htmloutputelement.rs
index 65b9ae554c8..9314672d3d0 100644
--- a/components/script/dom/htmloutputelement.rs
+++ b/components/script/dom/htmloutputelement.rs
@@ -22,6 +22,7 @@ use html5ever::{LocalName, Prefix};
 pub struct HTMLOutputElement {
     htmlelement: HTMLElement,
     form_owner: MutNullableDom<HTMLFormElement>,
+    labels_node_list: MutNullableDom<NodeList>,
 }
 
 impl HTMLOutputElement {
@@ -33,6 +34,7 @@ impl HTMLOutputElement {
         HTMLOutputElement {
             htmlelement: HTMLElement::new_inherited(local_name, prefix, document),
             form_owner: Default::default(),
+            labels_node_list: Default::default(),
         }
     }
 
@@ -65,9 +67,7 @@ impl HTMLOutputElementMethods for HTMLOutputElement {
     }
 
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    fn Labels(&self) -> DomRoot<NodeList> {
-        self.upcast::<HTMLElement>().labels()
-    }
+    make_labels_getter!(Labels, labels_node_list);
 }
 
 impl VirtualMethods for HTMLOutputElement {
diff --git a/components/script/dom/htmlprogresselement.rs b/components/script/dom/htmlprogresselement.rs
index 26ee952b2c9..0c4789fdc14 100644
--- a/components/script/dom/htmlprogresselement.rs
+++ b/components/script/dom/htmlprogresselement.rs
@@ -6,7 +6,7 @@ use crate::dom::bindings::codegen::Bindings::HTMLProgressElementBinding::{
     self, HTMLProgressElementMethods,
 };
 use crate::dom::bindings::inheritance::Castable;
-use crate::dom::bindings::root::DomRoot;
+use crate::dom::bindings::root::{DomRoot, MutNullableDom};
 use crate::dom::document::Document;
 use crate::dom::htmlelement::HTMLElement;
 use crate::dom::node::Node;
@@ -17,6 +17,7 @@ use html5ever::{LocalName, Prefix};
 #[dom_struct]
 pub struct HTMLProgressElement {
     htmlelement: HTMLElement,
+    labels_node_list: MutNullableDom<NodeList>,
 }
 
 impl HTMLProgressElement {
@@ -27,6 +28,7 @@ impl HTMLProgressElement {
     ) -> HTMLProgressElement {
         HTMLProgressElement {
             htmlelement: HTMLElement::new_inherited(local_name, prefix, document),
+            labels_node_list: MutNullableDom::new(None),
         }
     }
 
@@ -48,7 +50,5 @@ impl HTMLProgressElement {
 
 impl HTMLProgressElementMethods for HTMLProgressElement {
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    fn Labels(&self) -> DomRoot<NodeList> {
-        self.upcast::<HTMLElement>().labels()
-    }
+    make_labels_getter!(Labels, labels_node_list);
 }
diff --git a/components/script/dom/htmlselectelement.rs b/components/script/dom/htmlselectelement.rs
index c71a5442e73..0ef500ccb1a 100755
--- a/components/script/dom/htmlselectelement.rs
+++ b/components/script/dom/htmlselectelement.rs
@@ -61,6 +61,7 @@ pub struct HTMLSelectElement {
     htmlelement: HTMLElement,
     options: MutNullableDom<HTMLOptionsCollection>,
     form_owner: MutNullableDom<HTMLFormElement>,
+    labels_node_list: MutNullableDom<NodeList>,
 }
 
 static DEFAULT_SELECT_SIZE: u32 = 0;
@@ -80,6 +81,7 @@ impl HTMLSelectElement {
             ),
             options: Default::default(),
             form_owner: Default::default(),
+            labels_node_list: Default::default(),
         }
     }
 
@@ -249,9 +251,7 @@ impl HTMLSelectElementMethods for HTMLSelectElement {
     }
 
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    fn Labels(&self) -> DomRoot<NodeList> {
-        self.upcast::<HTMLElement>().labels()
-    }
+    make_labels_getter!(Labels, labels_node_list);
 
     // https://html.spec.whatwg.org/multipage/#dom-select-options
     fn Options(&self) -> DomRoot<HTMLOptionsCollection> {
diff --git a/components/script/dom/htmltextareaelement.rs b/components/script/dom/htmltextareaelement.rs
index ed2372fb247..eb8fcab3873 100755
--- a/components/script/dom/htmltextareaelement.rs
+++ b/components/script/dom/htmltextareaelement.rs
@@ -52,6 +52,7 @@ pub struct HTMLTextAreaElement {
     // https://html.spec.whatwg.org/multipage/#concept-textarea-dirty
     value_dirty: Cell<bool>,
     form_owner: MutNullableDom<HTMLFormElement>,
+    labels_node_list: MutNullableDom<NodeList>,
 }
 
 pub trait LayoutHTMLTextAreaElementHelpers {
@@ -153,6 +154,7 @@ impl HTMLTextAreaElement {
             )),
             value_dirty: Cell::new(false),
             form_owner: Default::default(),
+            labels_node_list: Default::default(),
         }
     }
 
@@ -316,9 +318,7 @@ impl HTMLTextAreaElementMethods for HTMLTextAreaElement {
     }
 
     // https://html.spec.whatwg.org/multipage/#dom-lfe-labels
-    fn Labels(&self) -> DomRoot<NodeList> {
-        self.upcast::<HTMLElement>().labels()
-    }
+    make_labels_getter!(Labels, labels_node_list);
 
     // https://html.spec.whatwg.org/multipage/#dom-textarea/input-select
     fn Select(&self) {
diff --git a/components/script/dom/macros.rs b/components/script/dom/macros.rs
index a1941662963..fe578f6f675 100644
--- a/components/script/dom/macros.rs
+++ b/components/script/dom/macros.rs
@@ -141,6 +141,21 @@ macro_rules! make_form_action_getter(
 );
 
 #[macro_export]
+macro_rules! make_labels_getter(
+    ( $attr:ident, $memo:ident ) => (
+        fn $attr(&self) -> DomRoot<NodeList> {
+            use crate::dom::htmlelement::HTMLElement;
+            use crate::dom::nodelist::NodeList;
+            self.$memo.or_init(|| NodeList::new_labels_list(
+                self.upcast::<Node>().owner_doc().window(),
+                self.upcast::<HTMLElement>()
+                )
+            )
+        }
+    );
+);
+
+#[macro_export]
 macro_rules! make_enumerated_getter(
     ( $attr:ident, $htmlname:tt, $default:expr, $($choices: pat)|+) => (
         fn $attr(&self) -> DOMString {
diff --git a/components/script/dom/nodelist.rs b/components/script/dom/nodelist.rs
index 930fedbbec4..88fdd4cb70c 100644
--- a/components/script/dom/nodelist.rs
+++ b/components/script/dom/nodelist.rs
@@ -7,6 +7,7 @@ use crate::dom::bindings::codegen::Bindings::NodeListBinding;
 use crate::dom::bindings::codegen::Bindings::NodeListBinding::NodeListMethods;
 use crate::dom::bindings::reflector::{reflect_dom_object, Reflector};
 use crate::dom::bindings::root::{Dom, DomRoot, MutNullableDom};
+use crate::dom::htmlelement::HTMLElement;
 use crate::dom::node::{ChildrenMutation, Node};
 use crate::dom::window::Window;
 use dom_struct::dom_struct;
@@ -17,6 +18,7 @@ use std::cell::Cell;
 pub enum NodeListType {
     Simple(Vec<Dom<Node>>),
     Children(ChildrenList),
+    Labels(LabelsList),
 }
 
 // https://dom.spec.whatwg.org/#interface-nodelist
@@ -65,6 +67,10 @@ impl NodeList {
         NodeList::new(window, NodeListType::Children(ChildrenList::new(node)))
     }
 
+    pub fn new_labels_list(window: &Window, element: &HTMLElement) -> DomRoot<NodeList> {
+        NodeList::new(window, NodeListType::Labels(LabelsList::new(element)))
+    }
+
     pub fn empty(window: &Window) -> DomRoot<NodeList> {
         NodeList::new(window, NodeListType::Simple(vec![]))
     }
@@ -76,6 +82,7 @@ impl NodeListMethods for NodeList {
         match self.list_type {
             NodeListType::Simple(ref elems) => elems.len() as u32,
             NodeListType::Children(ref list) => list.len(),
+            NodeListType::Labels(ref list) => list.len(),
         }
     }
 
@@ -86,6 +93,7 @@ impl NodeListMethods for NodeList {
                 .get(index as usize)
                 .map(|node| DomRoot::from_ref(&**node)),
             NodeListType::Children(ref list) => list.item(index),
+            NodeListType::Labels(ref list) => list.item(index),
         }
     }
 
@@ -319,3 +327,33 @@ impl ChildrenList {
         self.last_index.set(0u32);
     }
 }
+
+// Labels lists: There might room for performance optimization
+// analogous to the ChildrenMutation case of a children list,
+// in which we can keep information from an older access live
+// if we know nothing has happened that would change it.
+// However, label relationships can happen from further away
+// in the DOM than parent-child relationships, so it's not as simple,
+// and it's possible that tracking label moves would end up no faster
+// than recalculating labels.
+#[derive(JSTraceable, MallocSizeOf)]
+#[unrooted_must_root_lint::must_root]
+pub struct LabelsList {
+    element: Dom<HTMLElement>,
+}
+
+impl LabelsList {
+    pub fn new(element: &HTMLElement) -> LabelsList {
+        LabelsList {
+            element: Dom::from_ref(element),
+        }
+    }
+
+    pub fn len(&self) -> u32 {
+        self.element.labels_count()
+    }
+
+    pub fn item(&self, index: u32) -> Option<DomRoot<Node>> {
+        self.element.label_at(index)
+    }
+}
diff --git a/components/script/dom/webidls/HTMLInputElement.webidl b/components/script/dom/webidls/HTMLInputElement.webidl
index 48001bc555c..64ee9aa7c2f 100644
--- a/components/script/dom/webidls/HTMLInputElement.webidl
+++ b/components/script/dom/webidls/HTMLInputElement.webidl
@@ -89,7 +89,7 @@ interface HTMLInputElement : HTMLElement {
   //boolean reportValidity();
   //void setCustomValidity(DOMString error);
 
-  readonly attribute NodeList labels;
+  readonly attribute NodeList? labels;
 
   void select();
   [SetterThrows]