auto merge of #1952 : brunoabinader/servo/htmlcollection-live, r=Ms2ger

Closes #1662.

PS: Cached collections will be next step.

8 files changed, 197 insertions, 81 deletions

diff --git a/src/components/script/dom/document.rs b/src/components/script/dom/document.rs
index 3172f2f93cb..24767aaec52 100644
--- a/src/components/script/dom/document.rs
+++ b/src/components/script/dom/document.rs
@@ -20,7 +20,7 @@ use dom::element::{HTMLHtmlElementTypeId, HTMLHeadElementTypeId, HTMLTitleElemen
 use dom::element::{HTMLBodyElementTypeId, HTMLFrameSetElementTypeId};
 use dom::event::Event;
 use dom::eventtarget::{EventTarget, NodeTargetTypeId};
-use dom::htmlcollection::HTMLCollection;
+use dom::htmlcollection::{HTMLCollection, CollectionFilter};
 use dom::nodelist::NodeList;
 use dom::htmlelement::HTMLElement;
 use dom::htmlheadelement::HTMLHeadElement;
@@ -475,12 +475,26 @@ impl Document {
 
     pub fn Images(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
         // FIXME: https://github.com/mozilla/servo/issues/1847
-        HTMLCollection::by_tag_name(&self.window, &NodeCast::from(abstract_self), ~"img")
+        struct ImagesFilter;
+        impl CollectionFilter for ImagesFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == ~"img"
+            }
+        }
+        let filter = ~ImagesFilter;
+        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), filter)
     }
 
     pub fn Embeds(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
         // FIXME: https://github.com/mozilla/servo/issues/1847
-        HTMLCollection::by_tag_name(&self.window, &NodeCast::from(abstract_self), ~"embed")
+        struct EmbedsFilter;
+        impl CollectionFilter for EmbedsFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == ~"embed"
+            }
+        }
+        let filter = ~EmbedsFilter;
+        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), filter)
     }
 
     pub fn Plugins(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
@@ -490,32 +504,63 @@ impl Document {
 
     pub fn Links(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
         // FIXME: https://github.com/mozilla/servo/issues/1847
-        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), |elem| {
-            ("a" == elem.get().tag_name || "area" == elem.get().tag_name) &&
-            elem.get_attribute(Null, "href").is_some()
-        })
+        struct LinksFilter;
+        impl CollectionFilter for LinksFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                (elem.get().tag_name == ~"a" || elem.get().tag_name == ~"area") &&
+                elem.get_attribute(Null, "href").is_some()
+            }
+        }
+        let filter = ~LinksFilter;
+        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), filter)
     }
 
     pub fn Forms(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
         // FIXME: https://github.com/mozilla/servo/issues/1847
-        HTMLCollection::by_tag_name(&self.window, &NodeCast::from(abstract_self), ~"form")
+        struct FormsFilter;
+        impl CollectionFilter for FormsFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == ~"form"
+            }
+        }
+        let filter = ~FormsFilter;
+        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), filter)
     }
 
     pub fn Scripts(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
         // FIXME: https://github.com/mozilla/servo/issues/1847
-        HTMLCollection::by_tag_name(&self.window, &NodeCast::from(abstract_self), ~"script")
+        struct ScriptsFilter;
+        impl CollectionFilter for ScriptsFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == ~"script"
+            }
+        }
+        let filter = ~ScriptsFilter;
+        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), filter)
     }
 
     pub fn Anchors(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
         // FIXME: https://github.com/mozilla/servo/issues/1847
-        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), |elem| {
-            "a" == elem.get().tag_name && elem.get_attribute(Null, "name").is_some()
-        })
+        struct AnchorsFilter;
+        impl CollectionFilter for AnchorsFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == ~"a" && elem.get_attribute(Null, "name").is_some()
+            }
+        }
+        let filter = ~AnchorsFilter;
+        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), filter)
     }
 
     pub fn Applets(&self, abstract_self: &JS<Document>) -> JS<HTMLCollection> {
         // FIXME: This should be return OBJECT elements containing applets.
-        HTMLCollection::by_tag_name(&self.window, &NodeCast::from(abstract_self), ~"applet")
+        struct AppletsFilter;
+        impl CollectionFilter for AppletsFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == ~"applet"
+            }
+        }
+        let filter = ~AppletsFilter;
+        HTMLCollection::create(&self.window, &NodeCast::from(abstract_self), filter)
     }
 
     pub fn create_collection<T>(&self, callback: |elem: &JS<Node>| -> Option<JS<T>>) -> ~[JS<T>] {
diff --git a/src/components/script/dom/htmlcollection.rs b/src/components/script/dom/htmlcollection.rs
index 77d36e07005..eb56ebac542 100644
--- a/src/components/script/dom/htmlcollection.rs
+++ b/src/components/script/dom/htmlcollection.rs
@@ -12,69 +12,123 @@ use dom::window::Window;
 use servo_util::namespace::Namespace;
 use servo_util::str::DOMString;
 
+use serialize::{Encoder, Encodable};
+
+pub trait CollectionFilter {
+    fn filter(&self, elem: &JS<Element>, root: &JS<Node>) -> bool;
+}
+
+impl<S: Encoder> Encodable<S> for ~CollectionFilter {
+    fn encode(&self, _s: &mut S) {}
+}
+
+#[deriving(Encodable)]
+pub enum CollectionTypeId {
+    Static(~[JS<Element>]),
+    Live(JS<Node>, ~CollectionFilter)
+}
+
 #[deriving(Encodable)]
 pub struct HTMLCollection {
-    elements: ~[JS<Element>],
+    collection: CollectionTypeId,
     reflector_: Reflector,
     window: JS<Window>,
 }
 
 impl HTMLCollection {
-    pub fn new_inherited(window: JS<Window>, elements: ~[JS<Element>]) -> HTMLCollection {
+    pub fn new_inherited(window: JS<Window>, collection: CollectionTypeId) -> HTMLCollection {
         HTMLCollection {
-            elements: elements,
+            collection: collection,
             reflector_: Reflector::new(),
             window: window,
         }
     }
 
-    pub fn new(window: &JS<Window>, elements: ~[JS<Element>]) -> JS<HTMLCollection> {
-        reflect_dom_object(~HTMLCollection::new_inherited(window.clone(), elements),
+    pub fn new(window: &JS<Window>, collection: CollectionTypeId) -> JS<HTMLCollection> {
+        reflect_dom_object(~HTMLCollection::new_inherited(window.clone(), collection),
                            window, HTMLCollectionBinding::Wrap)
     }
 }
 
 impl HTMLCollection {
-    pub fn create(window: &JS<Window>, root: &JS<Node>, predicate: |elem: &JS<Element>| -> bool) -> JS<HTMLCollection> {
-        let mut elements = ~[];
-        for child in root.traverse_preorder() {
-            if child.is_element() {
-                let elem: JS<Element> = ElementCast::to(&child).unwrap();
-                if predicate(&elem) {
-                    elements.push(elem);
-                }
-            }
-        }
-        HTMLCollection::new(window, elements)
+    pub fn create(window: &JS<Window>, root: &JS<Node>, filter: ~CollectionFilter) -> JS<HTMLCollection> {
+        HTMLCollection::new(window, Live(root.clone(), filter))
     }
 
-    pub fn by_tag_name(window: &JS<Window>, root: &JS<Node>, tag_name: DOMString) -> JS<HTMLCollection> {
-        HTMLCollection::create(window, root, |elem| elem.get().tag_name == tag_name)
+    pub fn by_tag_name(window: &JS<Window>, root: &JS<Node>, tag: DOMString)
+                       -> JS<HTMLCollection> {
+        struct TagNameFilter {
+            tag: DOMString
+        }
+        impl CollectionFilter for TagNameFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == self.tag
+            }
+        }
+        let filter = TagNameFilter {
+            tag: tag
+        };
+        HTMLCollection::create(window, root, ~filter)
     }
 
-    pub fn by_tag_name_ns(window: &JS<Window>, root: &JS<Node>, tag_name: DOMString, namespace: Namespace) -> JS<HTMLCollection> {
-        HTMLCollection::create(window, root, |elem| elem.get().namespace == namespace && elem.get().tag_name == tag_name)
+    pub fn by_tag_name_ns(window: &JS<Window>, root: &JS<Node>, tag: DOMString,
+                          namespace: Namespace) -> JS<HTMLCollection> {
+        struct TagNameNSFilter {
+            tag: DOMString,
+            namespace: Namespace
+        }
+        impl CollectionFilter for TagNameNSFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().namespace == self.namespace && elem.get().tag_name == self.tag
+            }
+        }
+        let filter = TagNameNSFilter {
+            tag: tag,
+            namespace: namespace
+        };
+        HTMLCollection::create(window, root, ~filter)
     }
 
-    pub fn by_class_name(window: &JS<Window>, root: &JS<Node>, classes: DOMString) -> JS<HTMLCollection> {
-        // FIXME: https://github.com/mozilla/servo/issues/1840
-        let classes: ~[&str] = classes.split(' ').collect();
-        HTMLCollection::create(window, root, |elem| classes.iter().all(|class| elem.has_class(*class)))
+    pub fn by_class_name(window: &JS<Window>, root: &JS<Node>, classes: DOMString)
+                         -> JS<HTMLCollection> {
+        struct ClassNameFilter {
+            classes: ~[DOMString]
+        }
+        impl CollectionFilter for ClassNameFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                self.classes.iter().all(|class| elem.has_class(*class))
+            }
+        }
+        let filter = ClassNameFilter {
+            classes: classes.split(' ').map(|class| class.into_owned()).to_owned_vec()
+        };
+        HTMLCollection::create(window, root, ~filter)
     }
 }
 
 impl HTMLCollection {
     // http://dom.spec.whatwg.org/#dom-htmlcollection-length
     pub fn Length(&self) -> u32 {
-        self.elements.len() as u32
+        match self.collection {
+            Static(ref elems) => elems.len() as u32,
+            Live(ref root, ref filter) => root.traverse_preorder()
+                .count(|child| {
+                    let elem: Option<JS<Element>> = ElementCast::to(&child);
+                    elem.map_or(false, |elem| filter.filter(&elem, root))
+                }) as u32
+        }
     }
 
     // http://dom.spec.whatwg.org/#dom-htmlcollection-item
     pub fn Item(&self, index: u32) -> Option<JS<Element>> {
-        if index < self.Length() {
-            Some(self.elements[index].clone())
-        } else {
-            None
+        match self.collection {
+            Static(ref elems) => elems
+                .get(index as uint)
+                .map(|elem| elem.clone()),
+            Live(ref root, ref filter) => root.traverse_preorder()
+                .filter_map(|node| ElementCast::to(&node))
+                .filter(|elem| filter.filter(elem, root))
+                .nth(index as uint).clone()
         }
     }
 
@@ -86,9 +140,20 @@ impl HTMLCollection {
         }
 
         // Step 2.
-        self.elements.iter().find(|elem| {
-            elem.get_string_attribute("name") == key || elem.get_string_attribute("id") == key
-        }).map(|maybe_elem| maybe_elem.clone())
+        match self.collection {
+            Static(ref elems) => elems.iter()
+                .find(|elem| {
+                    elem.get_string_attribute("name") == key ||
+                    elem.get_string_attribute("id") == key })
+                .map(|maybe_elem| maybe_elem.clone()),
+            Live(ref root, ref filter) => root.traverse_preorder()
+                .filter_map(|node| ElementCast::to(&node))
+                .filter(|elem| filter.filter(elem, root))
+                .find(|elem| {
+                    elem.get_string_attribute("name") == key ||
+                    elem.get_string_attribute("id") == key })
+                .map(|maybe_elem| maybe_elem.clone())
+        }
     }
 }
 
diff --git a/src/components/script/dom/htmldatalistelement.rs b/src/components/script/dom/htmldatalistelement.rs
index 2a81cce1994..7011a9fe721 100644
--- a/src/components/script/dom/htmldatalistelement.rs
+++ b/src/components/script/dom/htmldatalistelement.rs
@@ -6,11 +6,11 @@ use dom::bindings::codegen::HTMLDataListElementBinding;
 use dom::bindings::codegen::InheritTypes::{HTMLDataListElementDerived, NodeCast};
 use dom::bindings::js::JS;
 use dom::document::Document;
-use dom::element::HTMLDataListElementTypeId;
+use dom::element::{Element, HTMLDataListElementTypeId};
 use dom::eventtarget::{EventTarget, NodeTargetTypeId};
-use dom::htmlcollection::HTMLCollection;
+use dom::htmlcollection::{HTMLCollection, CollectionFilter};
 use dom::htmlelement::HTMLElement;
-use dom::node::{Node, ElementNodeTypeId};
+use dom::node::{Node, ElementNodeTypeId, window_from_node};
 use servo_util::str::DOMString;
 
 #[deriving(Encodable)]
@@ -42,9 +42,14 @@ impl HTMLDataListElement {
 
 impl HTMLDataListElement {
     pub fn Options(&self, abstract_self: &JS<HTMLDataListElement>) -> JS<HTMLCollection> {
+        struct HTMLDataListOptionsFilter;
+        impl CollectionFilter for HTMLDataListOptionsFilter {
+            fn filter(&self, elem: &JS<Element>, _root: &JS<Node>) -> bool {
+                elem.get().tag_name == ~"option"
+            }
+        }
         let node: JS<Node> = NodeCast::from(abstract_self);
-        let doc = &self.htmlelement.element.node.owner_doc();
-        let window = &doc.get().window;
-        HTMLCollection::by_tag_name(window, &node, ~"option")
+        let filter = ~HTMLDataListOptionsFilter;
+        HTMLCollection::create(&window_from_node(&node), &node, filter)
     }
 }
diff --git a/src/components/script/dom/htmlfieldsetelement.rs b/src/components/script/dom/htmlfieldsetelement.rs
index 5bbd13c2b79..9474481a6a9 100644
--- a/src/components/script/dom/htmlfieldsetelement.rs
+++ b/src/components/script/dom/htmlfieldsetelement.rs
@@ -10,11 +10,11 @@ use dom::document::Document;
 use dom::element::{Element, HTMLFieldSetElementTypeId};
 use dom::eventtarget::{EventTarget, NodeTargetTypeId};
 use dom::htmlformelement::HTMLFormElement;
-use dom::htmlcollection::HTMLCollection;
+use dom::htmlcollection::{HTMLCollection, CollectionFilter};
 use dom::htmlelement::HTMLElement;
 use dom::node::{Node, ElementNodeTypeId, window_from_node};
 use dom::validitystate::ValidityState;
-use servo_util::str::DOMString;
+use servo_util::str::{DOMString, StaticStringVec};
 
 #[deriving(Encodable)]
 pub struct HTMLFieldSetElement {
@@ -68,12 +68,20 @@ impl HTMLFieldSetElement {
         ~""
     }
 
+    // http://www.whatwg.org/html/#dom-fieldset-elements
     pub fn Elements(&self, abstract_self: &JS<HTMLFieldSetElement>) -> JS<HTMLCollection> {
+        struct ElementsFilter;
+        impl CollectionFilter for ElementsFilter {
+            fn filter(&self, elem: &JS<Element>, root: &JS<Node>) -> bool {
+                static tag_names: StaticStringVec = &["button", "fieldset", "input",
+                    "keygen", "object", "output", "select", "textarea"];
+                let root: &JS<Element> = &ElementCast::to(root).unwrap();
+                elem != root && tag_names.iter().any(|&tag_name| tag_name == elem.get().tag_name)
+            }
+        }
         let node: JS<Node> = NodeCast::from(abstract_self);
-        let element: JS<Element> = ElementCast::from(abstract_self);
-        let window = &window_from_node(&node);
-        let listed_elements = ["button", "fieldset", "input", "keygen", "object", "output", "select", "textarea"];
-        HTMLCollection::create(window, &node, |elem| *elem != element && listed_elements.iter().any(|&tag_name| tag_name == elem.get().tag_name))
+        let filter = ~ElementsFilter;
+        HTMLCollection::create(&window_from_node(&node), &node, filter)
     }
 
     pub fn WillValidate(&self) -> bool {
diff --git a/src/components/script/dom/htmlformelement.rs b/src/components/script/dom/htmlformelement.rs
index a1ca7d5dc2f..cabb71cc1ea 100644
--- a/src/components/script/dom/htmlformelement.rs
+++ b/src/components/script/dom/htmlformelement.rs
@@ -9,7 +9,7 @@ use dom::bindings::error::ErrorResult;
 use dom::document::Document;
 use dom::element::{Element, HTMLFormElementTypeId};
 use dom::eventtarget::{EventTarget, NodeTargetTypeId};
-use dom::htmlcollection::HTMLCollection;
+use dom::htmlcollection::{HTMLCollection, Static};
 use dom::htmlelement::HTMLElement;
 use dom::node::{Node, ElementNodeTypeId};
 use servo_util::str::DOMString;
@@ -118,7 +118,7 @@ impl HTMLFormElement {
         // FIXME: https://github.com/mozilla/servo/issues/1844
         let doc = self.htmlelement.element.node.owner_doc();
         let doc = doc.get();
-        HTMLCollection::new(&doc.window, ~[])
+        HTMLCollection::new(&doc.window, Static(~[]))
     }
 
     pub fn Length(&self) -> i32 {
diff --git a/src/components/script/dom/htmlmapelement.rs b/src/components/script/dom/htmlmapelement.rs
index d343073a278..c439225362c 100644
--- a/src/components/script/dom/htmlmapelement.rs
+++ b/src/components/script/dom/htmlmapelement.rs
@@ -9,7 +9,7 @@ use dom::bindings::error::ErrorResult;
 use dom::document::Document;
 use dom::element::HTMLMapElementTypeId;
 use dom::eventtarget::{EventTarget, NodeTargetTypeId};
-use dom::htmlcollection::HTMLCollection;
+use dom::htmlcollection::{HTMLCollection, Static};
 use dom::htmlelement::HTMLElement;
 use dom::node::{Node, ElementNodeTypeId};
 use servo_util::str::DOMString;
@@ -54,6 +54,6 @@ impl HTMLMapElement {
         // FIXME: https://github.com/mozilla/servo/issues/1845
         let doc = self.htmlelement.element.node.owner_doc();
         let doc = doc.get();
-        HTMLCollection::new(&doc.window, ~[])
+        HTMLCollection::new(&doc.window, Static(~[]))
     }
 }
diff --git a/src/components/util/str.rs b/src/components/util/str.rs
index bd89ad9ea6f..cdbf1bb9ea9 100644
--- a/src/components/util/str.rs
+++ b/src/components/util/str.rs
@@ -3,6 +3,7 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 pub type DOMString = ~str;
+pub type StaticStringVec = &'static [&'static str];
 
 pub fn null_str_as_empty(s: &Option<DOMString>) -> DOMString {
     // We don't use map_default because it would allocate ~"" even for Some.
diff --git a/src/test/content/test_htmlcollection.html b/src/test/content/test_htmlcollection.html
index e024a331e80..c620b54815f 100644
--- a/src/test/content/test_htmlcollection.html
+++ b/src/test/content/test_htmlcollection.html
@@ -40,33 +40,25 @@
                 is(htmlcollection.length, 1);
                 is(htmlcollection.item(0), live);
 
-                is(live.childNodes.length, 0)
-                is(htmlcollection.item(0).childNodes.length, 0);
-                is(document.getElementById("live").childNodes.length, 0);
-
-                live.appendChild(child);
+                let new_live = document.createElement("div");
+                new_live.className = "live";
+                document.body.appendChild(new_live);
+                is(htmlcollection.length, 2);
+                is(htmlcollection.item(1), new_live);
 
-                is(live.childNodes.length, 1);
-                is(htmlcollection.item(0).childNodes.length, 1);
-                is(document.getElementById("live").childNodes.length, 1);
+                document.body.removeChild(new_live);
+                is(htmlcollection.length, 1);
             }
 
             // test3: getElementsByTagName
             {
-                htmlcollection = document.getElementsByTagName("div");
-                is(htmlcollection.length, 5);
+                is(document.getElementsByTagName("DIV").length, 0);
 
-                let from_element = document.documentElement.getElementsByTagName("div");
-                is(htmlcollection.length, from_element.length);
+                is(document.getElementsByTagName("div").length,
+                   document.documentElement.getElementsByTagName("div").length);
 
-                htmlcollection = document.getElementsByTagName("DIV");
-                is(htmlcollection.length, 0);
-
-                htmlcollection = document.getElementsByTagName("p");
-                is(htmlcollection.length, 4);
-
-                from_element = document.getElementById("class-example").getElementsByTagName("p");
-                is(from_element.length, 3);
+                is(document.getElementsByTagName("p").length,
+                   document.getElementById("class-example").getElementsByTagName("p").length);
             }
 
             // test4: getElementsByTagNameNS