Impl Setlike and Maplike (#30237)

* MallocSizeOf for Index{Set, Map}

* like as iterable in WebIDL

* Codegen magic for like interfaces

* TestBinding for like

* Test for Setlike and Maplike test bindings

* Some fixes

* Switch to any.js

* nit

* Keep order

9 files changed, 571 insertions, 4 deletions

diff --git a/components/script/dom/bindings/codegen/CodegenRust.py b/components/script/dom/bindings/codegen/CodegenRust.py
index bc7f2ceb9a8..f7280ffba22 100644
--- a/components/script/dom/bindings/codegen/CodegenRust.py
+++ b/components/script/dom/bindings/codegen/CodegenRust.py
@@ -3805,7 +3805,9 @@ class CGPerSignatureCall(CGThing):
         if idlNode.isMethod() and idlNode.isMaplikeOrSetlikeOrIterableMethod():
             if idlNode.maplikeOrSetlikeOrIterable.isMaplike() or \
                idlNode.maplikeOrSetlikeOrIterable.isSetlike():
-                raise TypeError('Maplike/Setlike methods are not supported yet')
+                cgThings.append(CGMaplikeOrSetlikeMethodGenerator(descriptor,
+                                                                  idlNode.maplikeOrSetlikeOrIterable,
+                                                                  idlNode.identifier.name))
             else:
                 cgThings.append(CGIterableMethodGenerator(descriptor,
                                                           idlNode.maplikeOrSetlikeOrIterable,
@@ -6490,6 +6492,8 @@ def generate_imports(config, cgthings, descriptors, callbacks=None, dictionaries
         'crate::dom::bindings::htmlconstructor::push_new_element_queue',
         'crate::dom::bindings::iterable::Iterable',
         'crate::dom::bindings::iterable::IteratorType',
+        'crate::dom::bindings::like::Setlike',
+        'crate::dom::bindings::like::Maplike',
         'crate::dom::bindings::namespace::NamespaceObjectClass',
         'crate::dom::bindings::namespace::create_namespace_object',
         'crate::dom::bindings::reflector::MutDomObject',
@@ -7862,6 +7866,77 @@ class CallbackOperation(CallbackOperationBase):
                                        descriptor, descriptor.interface.isSingleOperationInterface())
 
 
+class CGMaplikeOrSetlikeMethodGenerator(CGGeneric):
+    """
+    Creates methods for *like interfaces. Unwrapping/wrapping
+    will be taken care of by the usual method generation machinery in
+    CGMethodCall/CGPerSignatureCall. Functionality is filled in here instead of
+    using CGCallGenerator.
+    """
+    def __init__(self, descriptor, likeable, methodName):
+        trait: str
+        if likeable.isSetlike():
+            trait = "Setlike"
+        elif likeable.isMaplike():
+            trait = "Maplike"
+        else:
+            raise TypeError("CGMaplikeOrSetlikeMethodGenerator is only for Setlike/Maplike")
+        """
+        setlike:
+            fn size(&self) -> usize;
+            fn add(&self, key: Self::Key);
+            fn has(&self, key: &Self::Key) -> bool;
+            fn clear(&self);
+            fn delete(&self, key: &Self::Key) -> bool;
+        maplike:
+            fn get(&self, key: Self::Key) -> Self::Value;
+            fn size(&self) -> usize;
+            fn set(&self, key: Self::Key, value: Self::Value);
+            fn has(&self, key: &Self::Key) -> bool;
+            fn clear(&self);
+            fn delete(&self, key: &Self::Key) -> bool;
+        like iterable:
+            keys/values/entries/forEach
+        """
+        # like iterables are implemented seperatly as we are actually implementing them
+        if methodName in ["keys", "values", "entries", "forEach"]:
+            CGIterableMethodGenerator.__init__(self, descriptor, likeable, methodName)
+        elif methodName in ["size", "clear"]:  # zero arguments
+            CGGeneric.__init__(self, fill(
+                """
+                let result = ${trt}::${method}(&*this);
+                """,
+                trt=trait,
+                method=methodName.lower()))
+        elif methodName == "add":  # special case one argumet
+            CGGeneric.__init__(self, fill(
+                """
+                ${trt}::${method}(&*this, arg0);
+                // Returns itself per https://webidl.spec.whatwg.org/#es-set-add
+                let result = this;
+                """,
+                trt=trait,
+                method=methodName))
+        elif methodName in ["has", "delete", "get"]:  # one argument
+            CGGeneric.__init__(self, fill(
+                """
+                let result = ${trt}::${method}(&*this, arg0);
+                """,
+                trt=trait,
+                method=methodName))
+        elif methodName == "set":  # two arguments
+            CGGeneric.__init__(self, fill(
+                """
+                ${trt}::${method}(&*this, arg0, arg1);
+                // Returns itself per https://webidl.spec.whatwg.org/#es-map-set
+                let result = this;
+                """,
+                trt=trait,
+                method=methodName))
+        else:
+            raise TypeError(f"Do not know how to impl *like method: {methodName}")
+
+
 class CGIterableMethodGenerator(CGGeneric):
     """
     Creates methods for iterable interfaces. Unwrapping/wrapping
diff --git a/components/script/dom/bindings/codegen/Configuration.py b/components/script/dom/bindings/codegen/Configuration.py
index bd455f5288e..aa32093772f 100644
--- a/components/script/dom/bindings/codegen/Configuration.py
+++ b/components/script/dom/bindings/codegen/Configuration.py
@@ -516,7 +516,11 @@ def getUnwrappedType(type):
 
 
 def iteratorNativeType(descriptor, infer=False):
-    assert descriptor.interface.isIterable()
     iterableDecl = descriptor.interface.maplikeOrSetlikeOrIterable
-    assert iterableDecl.isPairIterator()
-    return "IterableIterator%s" % ("" if infer else '<%s>' % descriptor.interface.identifier.name)
+    assert (iterableDecl.isIterable() and iterableDecl.isPairIterator()) \
+        or iterableDecl.isSetlike() or iterableDecl.isMaplike()
+    res = "IterableIterator%s" % ("" if infer else '<%s>' % descriptor.interface.identifier.name)
+    # todo: this hack is telling us that something is still wrong in codegen
+    if iterableDecl.isSetlike() or iterableDecl.isMaplike():
+        res = f"crate::dom::bindings::iterable::{res}"
+    return res
diff --git a/components/script/dom/bindings/like.rs b/components/script/dom/bindings/like.rs
new file mode 100644
index 00000000000..ad14e453655
--- /dev/null
+++ b/components/script/dom/bindings/like.rs
@@ -0,0 +1,298 @@
+/* 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/. */
+
+#![allow(unsafe_code)]
+
+//! Implementation of `setlike<...>` and `maplike<..., ...>` WebIDL declarations.
+
+use crate::dom::bindings::cell::DomRefCell;
+use indexmap::{IndexMap, IndexSet};
+use js::conversions::ToJSValConvertible;
+use std::cmp::Eq;
+use std::hash::Hash;
+
+use super::iterable::Iterable;
+
+/// Every Setlike dom_struct must implement this to provide access to underlying storage
+/// so codegen can automatically generate all setlike methods
+///
+/// In case you use a type that implements Setlike as underlying storage it's recommended to use `setlike` macro.
+// In webidl: `setlike<Key>`
+pub trait Setlike {
+    /// The type of the key of the set.
+    type Key: ToJSValConvertible + Clone; // clone is for impl<T: Setlike> Maplike for T
+
+    fn get_index(&self, index: u32) -> Option<Self::Key>;
+
+    fn size(&self) -> u32;
+    fn add(&self, key: Self::Key);
+    fn has(&self, key: Self::Key) -> bool;
+    fn clear(&self);
+    fn delete(&self, key: Self::Key) -> bool;
+}
+
+// we can only have one iterable for T
+// so we have impl<T: Maplike> Iterable for T
+// and minimal:
+impl<T: Setlike> Maplike for T {
+    type Key = <T as Setlike>::Key;
+
+    type Value = <T as Setlike>::Key;
+
+    #[inline]
+    fn get_index(&self, index: u32) -> Option<(Self::Key, Self::Value)> {
+        self.get_index(index).map(|k| (k.clone(), k))
+    }
+
+    fn get(&self, _key: Self::Key) -> Option<Self::Value> {
+        unimplemented!()
+    }
+
+    #[inline]
+    fn size(&self) -> u32 {
+        self.size()
+    }
+
+    fn set(&self, _key: Self::Key, _value: Self::Value) {
+        unimplemented!()
+    }
+
+    fn has(&self, _key: Self::Key) -> bool {
+        unimplemented!()
+    }
+
+    fn clear(&self) {
+        unimplemented!()
+    }
+
+    fn delete(&self, _key: Self::Key) -> bool {
+        unimplemented!()
+    }
+}
+
+impl<K> Setlike for DomRefCell<IndexSet<K>>
+where
+    K: ToJSValConvertible + Eq + PartialEq + Hash + Clone,
+{
+    type Key = K;
+
+    #[inline(always)]
+    fn get_index(&self, index: u32) -> Option<Self::Key> {
+        self.borrow().get_index(index as usize).cloned()
+    }
+
+    #[inline(always)]
+    fn size(&self) -> u32 {
+        self.borrow().len() as u32
+    }
+
+    #[inline(always)]
+    fn add(&self, key: Self::Key) {
+        self.borrow_mut().insert(key);
+    }
+
+    #[inline(always)]
+    fn has(&self, key: Self::Key) -> bool {
+        self.borrow().contains(&key)
+    }
+
+    #[inline(always)]
+    fn clear(&self) {
+        self.borrow_mut().clear()
+    }
+
+    #[inline(always)]
+    fn delete(&self, key: Self::Key) -> bool {
+        self.borrow_mut().shift_remove(&key)
+    }
+}
+
+/// Usage:
+/// ```rust
+/// pub struct TestBindingSetlike {
+///     // setlike<DOMString>
+///     internal: DomRefCell<IndexSet<DOMString>>,
+/// }
+/// impl Setlike for TestBindingSetlike {
+///     type Key = DOMString;
+///     setlike!(self, internal);
+/// }
+/// ```
+#[macro_export]
+macro_rules! setlike {
+    ( $self:ident, $x:ident ) => {
+        #[inline(always)]
+        fn get_index(&$self, index: u32) -> Option<Self::Key> {
+            $self.$x.get_index(index)
+        }
+
+        #[inline(always)]
+        fn size(&$self) -> u32 {
+            $self.$x.size()
+        }
+
+        #[inline(always)]
+        fn add(&$self, key: Self::Key) {
+            $self.$x.add(key)
+        }
+
+        #[inline(always)]
+        fn has(&$self, key: Self::Key) -> bool {
+            $self.$x.has(key)
+        }
+
+        #[inline(always)]
+        fn clear(&$self) {
+            $self.$x.clear()
+        }
+
+        #[inline(always)]
+        fn delete(&$self, key: Self::Key) -> bool {
+            $self.$x.delete(key)
+        }
+    };
+}
+
+/// Every Maplike dom_struct must implement this
+/// to provide access to underlying storage
+/// so codegen can automatically generate all maplike methods
+///
+/// In case you use a type that implements Maplike as underlying storage it's recommended to use `maplike` macro.
+// In webidl: `maplike<Key, Value>`
+pub trait Maplike {
+    /// The type of the key of the map.
+    type Key: ToJSValConvertible;
+    /// The type of the value of the map.
+    type Value: ToJSValConvertible;
+
+    fn get_index(&self, index: u32) -> Option<(Self::Key, Self::Value)>;
+
+    fn get(&self, key: Self::Key) -> Option<Self::Value>;
+    fn size(&self) -> u32;
+    fn set(&self, key: Self::Key, value: Self::Value);
+    fn has(&self, key: Self::Key) -> bool;
+    fn clear(&self);
+    fn delete(&self, key: Self::Key) -> bool;
+}
+
+impl<T: Maplike> Iterable for T {
+    type Key = T::Key;
+
+    type Value = T::Value;
+
+    #[inline]
+    fn get_iterable_length(&self) -> u32 {
+        self.size()
+    }
+
+    #[inline]
+    fn get_value_at_index(&self, index: u32) -> Self::Value {
+        // SAFETY: we are checking bounds manually
+        self.get_index(index).unwrap().1
+    }
+
+    #[inline]
+    fn get_key_at_index(&self, index: u32) -> Self::Key {
+        // SAFETY: we are checking bounds manually
+        self.get_index(index).unwrap().0
+    }
+}
+
+impl<K, V> Maplike for DomRefCell<IndexMap<K, V>>
+where
+    K: ToJSValConvertible + Eq + PartialEq + Hash + Clone,
+    V: ToJSValConvertible + Clone,
+{
+    type Key = K;
+    type Value = V;
+
+    #[inline(always)]
+    fn get_index(&self, index: u32) -> Option<(Self::Key, Self::Value)> {
+        self.borrow()
+            .get_index(index as usize)
+            .map(|(k, v)| (k.to_owned(), v.to_owned()))
+    }
+
+    #[inline(always)]
+    fn get(&self, key: Self::Key) -> Option<Self::Value> {
+        self.borrow().get(&key).cloned()
+    }
+
+    #[inline(always)]
+    fn size(&self) -> u32 {
+        self.borrow().len() as u32
+    }
+
+    #[inline(always)]
+    fn set(&self, key: Self::Key, value: Self::Value) {
+        self.borrow_mut().insert(key, value);
+    }
+
+    #[inline(always)]
+    fn has(&self, key: Self::Key) -> bool {
+        self.borrow().contains_key(&key)
+    }
+
+    #[inline(always)]
+    fn clear(&self) {
+        self.borrow_mut().clear()
+    }
+
+    #[inline(always)]
+    fn delete(&self, key: Self::Key) -> bool {
+        self.borrow_mut().shift_remove(&key).is_some()
+    }
+}
+
+/// Usage:
+/// ```rust
+/// pub struct TestBindingMaplike {
+///     // maplike<DOMString, long>
+///     internal: DomRefCell<IndexMap<DOMString, i32>>,
+/// }
+/// impl Maplike for TestBindingSetlike {
+///     type Key = DOMString;
+///     type Value = i32;
+///     maplike!(self, internal);
+/// }
+/// ```
+#[macro_export]
+macro_rules! maplike {
+    ( $self:ident, $internal:ident ) => {
+        #[inline(always)]
+        fn get_index(&$self, index: u32) -> Option<(Self::Key, Self::Value)> {
+            $self.$internal.get_index(index)
+        }
+
+        #[inline(always)]
+        fn get(&$self, key: Self::Key) -> Option<Self::Value> {
+            $self.$internal.get(key)
+        }
+
+        #[inline(always)]
+        fn size(&$self) -> u32 {
+            $self.$internal.size()
+        }
+
+        #[inline(always)]
+        fn set(&$self, key: Self::Key, value: Self::Value) {
+            $self.$internal.set(key, value)
+        }
+
+        #[inline(always)]
+        fn has(&$self, key: Self::Key) -> bool {
+            $self.$internal.has(key)
+        }
+
+        #[inline(always)]
+        fn clear(&$self) {
+            $self.$internal.clear()
+        }
+
+        #[inline(always)]
+        fn delete(&$self, key: Self::Key) -> bool {
+            $self.$internal.delete(key)
+        }
+    };
+}
diff --git a/components/script/dom/bindings/mod.rs b/components/script/dom/bindings/mod.rs
index e446af3693f..9263fca2ba6 100644
--- a/components/script/dom/bindings/mod.rs
+++ b/components/script/dom/bindings/mod.rs
@@ -143,6 +143,7 @@ pub mod htmlconstructor;
 pub mod inheritance;
 pub mod interface;
 pub mod iterable;
+pub mod like;
 pub mod namespace;
 pub mod num;
 pub mod principals;
diff --git a/components/script/dom/mod.rs b/components/script/dom/mod.rs
index 95d1821b87a..ae92d11de8f 100644
--- a/components/script/dom/mod.rs
+++ b/components/script/dom/mod.rs
@@ -532,8 +532,10 @@ pub mod svggraphicselement;
 pub mod svgsvgelement;
 pub mod testbinding;
 pub mod testbindingiterable;
+pub mod testbindingmaplike;
 pub mod testbindingpairiterable;
 pub mod testbindingproxy;
+pub mod testbindingsetlike;
 pub mod testrunner;
 pub mod testworklet;
 pub mod testworkletglobalscope;
diff --git a/components/script/dom/testbindingmaplike.rs b/components/script/dom/testbindingmaplike.rs
new file mode 100644
index 00000000000..83ebcce4646
--- /dev/null
+++ b/components/script/dom/testbindingmaplike.rs
@@ -0,0 +1,90 @@
+/* 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/. */
+
+// check-tidy: no specs after this line
+
+use crate::dom::bindings::cell::DomRefCell;
+use crate::dom::bindings::codegen::Bindings::TestBindingMaplikeBinding::TestBindingMaplikeMethods;
+use crate::dom::bindings::error::Fallible;
+use crate::dom::bindings::like::Maplike;
+use crate::dom::bindings::reflector::{reflect_dom_object_with_proto, Reflector};
+use crate::dom::bindings::root::DomRoot;
+use crate::dom::bindings::str::DOMString;
+use crate::dom::globalscope::GlobalScope;
+use crate::maplike;
+use dom_struct::dom_struct;
+use indexmap::IndexMap;
+use js::rust::HandleObject;
+
+use super::bindings::error::Error;
+
+/// maplike<DOMString, long>
+#[dom_struct]
+pub struct TestBindingMaplike {
+    reflector: Reflector,
+    #[custom_trace]
+    internal: DomRefCell<IndexMap<DOMString, i32>>,
+}
+
+impl TestBindingMaplike {
+    fn new(global: &GlobalScope, proto: Option<HandleObject>) -> DomRoot<TestBindingMaplike> {
+        reflect_dom_object_with_proto(
+            Box::new(TestBindingMaplike {
+                reflector: Reflector::new(),
+                internal: DomRefCell::new(IndexMap::new()),
+            }),
+            global,
+            proto,
+        )
+    }
+
+    #[allow(non_snake_case)]
+    pub fn Constructor(
+        global: &GlobalScope,
+        proto: Option<HandleObject>,
+    ) -> Fallible<DomRoot<TestBindingMaplike>> {
+        Ok(TestBindingMaplike::new(global, proto))
+    }
+}
+
+impl TestBindingMaplikeMethods for TestBindingMaplike {
+    fn SetInternal(&self, key: DOMString, value: i32) {
+        self.internal.set(key, value)
+    }
+
+    fn ClearInternal(&self) {
+        self.internal.clear()
+    }
+
+    fn DeleteInternal(&self, key: DOMString) -> bool {
+        self.internal.delete(key)
+    }
+
+    fn HasInternal(&self, key: DOMString) -> bool {
+        self.internal.has(key)
+    }
+
+    fn GetInternal(&self, key: DOMString) -> Fallible<i32> {
+        // TODO: error type?
+        self.internal
+            .borrow()
+            .get(&key)
+            .ok_or_else(|| Error::Type(format!("No entry for key {key}")))
+            .copied()
+    }
+
+    fn Size(&self) -> u32 {
+        self.internal.size()
+    }
+}
+
+// this error is wrong because if we inline Self::Key and Self::Value all errors are gone
+// TODO: FIX THIS
+#[allow(unrooted_must_root)]
+impl Maplike for TestBindingMaplike {
+    type Key = DOMString;
+    type Value = i32;
+
+    maplike!(self, internal);
+}
diff --git a/components/script/dom/testbindingsetlike.rs b/components/script/dom/testbindingsetlike.rs
new file mode 100644
index 00000000000..9d62afaf653
--- /dev/null
+++ b/components/script/dom/testbindingsetlike.rs
@@ -0,0 +1,63 @@
+/* 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/. */
+
+// check-tidy: no specs after this line
+
+use crate::dom::bindings::cell::DomRefCell;
+use crate::dom::bindings::codegen::Bindings::TestBindingSetlikeBinding::TestBindingSetlikeMethods;
+use crate::dom::bindings::error::Fallible;
+use crate::dom::bindings::reflector::{reflect_dom_object_with_proto, Reflector};
+use crate::dom::bindings::root::DomRoot;
+use crate::dom::bindings::str::DOMString;
+use crate::dom::globalscope::GlobalScope;
+use crate::setlike;
+use dom_struct::dom_struct;
+use indexmap::IndexSet;
+use js::rust::HandleObject;
+
+use super::bindings::like::Setlike;
+
+// setlike<DOMString>
+#[dom_struct]
+pub struct TestBindingSetlike {
+    reflector: Reflector,
+    #[custom_trace]
+    internal: DomRefCell<IndexSet<DOMString>>,
+}
+
+impl TestBindingSetlike {
+    fn new(global: &GlobalScope, proto: Option<HandleObject>) -> DomRoot<TestBindingSetlike> {
+        reflect_dom_object_with_proto(
+            Box::new(TestBindingSetlike {
+                reflector: Reflector::new(),
+                internal: DomRefCell::new(IndexSet::new()),
+            }),
+            global,
+            proto,
+        )
+    }
+
+    #[allow(non_snake_case)]
+    pub fn Constructor(
+        global: &GlobalScope,
+        proto: Option<HandleObject>,
+    ) -> Fallible<DomRoot<TestBindingSetlike>> {
+        Ok(TestBindingSetlike::new(global, proto))
+    }
+}
+
+impl TestBindingSetlikeMethods for TestBindingSetlike {
+    fn Size(&self) -> u32 {
+        self.internal.size()
+    }
+}
+
+// this error is wrong because if we inline Self::Key and Self::Value all errors are gone
+// TODO: FIX THIS
+#[allow(unrooted_must_root)]
+impl Setlike for TestBindingSetlike {
+    type Key = DOMString;
+
+    setlike!(self, internal);
+}
diff --git a/components/script/dom/webidls/TestBindingMaplike.webidl b/components/script/dom/webidls/TestBindingMaplike.webidl
new file mode 100644
index 00000000000..f9712d63a8a
--- /dev/null
+++ b/components/script/dom/webidls/TestBindingMaplike.webidl
@@ -0,0 +1,20 @@
+/* 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/. */
+
+// This interface is entirely internal to Servo, and should not be accessible to
+// web pages.
+
+[Pref="dom.testbinding.enabled", Exposed=(Window,Worker)]
+interface TestBindingMaplike {
+  [Throws]
+  constructor();
+
+  maplike<DOMString, long>;
+  undefined setInternal(DOMString aKey, long aValue);
+  undefined clearInternal();
+  boolean deleteInternal(DOMString aKey);
+  boolean hasInternal(DOMString aKey);
+  [Throws]
+  long getInternal(DOMString aKey);
+};
diff --git a/components/script/dom/webidls/TestBindingSetlike.webidl b/components/script/dom/webidls/TestBindingSetlike.webidl
new file mode 100644
index 00000000000..c8cfcf73b86
--- /dev/null
+++ b/components/script/dom/webidls/TestBindingSetlike.webidl
@@ -0,0 +1,14 @@
+/* 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/. */
+
+// This interface is entirely internal to Servo, and should not be accessible to
+// web pages.
+
+[Pref="dom.testbinding.enabled", Exposed=(Window,Worker)]
+interface TestBindingSetlike {
+  [Throws]
+  constructor();
+
+  setlike<DOMString>;
+};