Boa: Implement Set()

[jasonwilliams]

ECMASCript feature
Set objects are collections of ECMAScript language values. A distinct value may only occur once as an element of a Set's collection. Distinct values are discriminated using the SameValueZero comparison algorithm.

I would like to see Set implemented. ECMAScript specification.

Example code

let mySet = new Set()

mySet.add(1)           // Set [ 1 ]
mySet.add(5)           // Set [ 1, 5 ]
mySet.add(5)           // Set [ 1, 5 ]
mySet.add('some text') // Set [ 1, 5, 'some text' ]
let o = {a: 1, b: 2}
mySet.add(o)

mySet.add({a: 1, b: 2})   // o is referencing a different object, so this is okay

mySet.has(1)              // true
mySet.has(3)              // false, since 3 has not been added to the set
mySet.has(5)              // true
mySet.has(Math.sqrt(25))  // true
mySet.has('Some Text'.toLowerCase()) // true
mySet.has(o)       // true

mySet.size         // 5

mySet.delete(5)    // removes 5 from the set
mySet.has(5)       // false, 5 has been removed

mySet.size         // 4, since we just removed one value

console.log(mySet)
// logs Set(4) [ 1, "some text", {…}, {…} ] in Firefox
// logs Set(4) { 1, "some text", {…}, {…} } in Chrome

Example to work from
Array is implemented here: https://github.com/jasonwilliams/boa/blob/master/boa/src/builtins/array/mod.rs

Contributing
https://github.com/jasonwilliams/boa/blob/master/CONTRIBUTING.md

[brian-gavin]

Hey all, I'm interested in picking this up.

[jasonwilliams]

Assigned

[brian-gavin]

Have a WIP local implementation, but relies on internal_slot, so will be waiting for #419 to be completed before raising a PR for this one.

[HalidOdat]

Have a WIP local implementation, but relies on internal_slot, so will be waiting for #419 to be completed before raising a PR for this one.

I was curious, how you implemented it! because internal_slots the key value is string, and Set stores Values, right? I'm guessing its very hacky
I'm working on implementing Hash trait for Value so it be easier to implement Set because HashSet requires Hash trait.

[brian-gavin]

I was curious, how you implemented it! because internal_slots the key value is string, and Set stores Values, right? I'm guessing its very hacky

Oops, sorry, I meant to say that I implemented it using internal_state!

What I did with that was create a wrapper struct for Vec<Value> (Did not want to bother with trying to implement Hash for Value because of floating points 😆 ) and derive the InternalState trait for that struct.

After that it was just a matter of translating some of the spec operations to my implementation, such as the validity check being that the internal_state field could be downcasted to what I expected, then doing Vec operations on it.

I'm working on implementing Hash trait for Value so it be easier to implement Set because HashSet requires Hash trait.

Good luck! What kind of approach are you doing? I am curious about this.

[HalidOdat]

Good luck! What kind of approach are you doing? I am curious about this.

Well I checked the standard and for Set and Map for key comparison they use the SameValueZero algorithm. In it NaN === NaN, unlike strict equality.
The Hash trait requires PartialEq and Eq traits, for PartialEq I implemented SameValueZero algorithm that was easy. But the reason Eq is not implemented for floating points is that in Rust std::f64::NAN == std::f64::NAN is false and the requirement key1 == key2 && hash(key1) == hash(key2) fails. But because NaN === NaN, I can implement Eq trait on a wrapper struct with f64.

For Hash trait I think I implemented correctly but I'm still testing. Basically I call hash on Every field on ValueData, like String, Integer, etc, for Rational(f64) I call .to_bits on the float which returns a u64 (this is not a cast, this is transmutation of memory) and call hash on it, for Object and Symbol I hash the pointers to that memory location.

[jasonwilliams]

unassigned @brian-gavin due to inactivity, feel free to mention here if you still wanted this.
Marking as Medium due to the fact you can copy a lot from Map() implementation

[winnayx]

I can take this issue

[RageKnify]

I'd sugest waiting for #722 since it changes a bit how builtins are implemented, maybe you could start your branch from that PR's branch so that you can implement it in the new way straight away. Good luck @winnayx

[Razican]

Hi @winnayx, do you have any update on this?

[RageKnify]

I've implemented about half of Set, I reached a problem when trying to implement Set.prototype.size, it's supposed to be an accessor property, but the current API assumes DataDescriptors https://github.com/boa-dev/boa/blob/04da7ff2225c2ff303740ff388f1b7ac9fccdb5f/boa/src/object/mod.rs#L942

My first idea was to make it usable for both cases, sadly this will add more boiler plate at the call-site for DataDescriptors since we'd need to create the DataDescriptor there, the new property metod will look like this:

    pub fn property<K, P>(&mut self, key: K, property: P) -> &mut Self
    where
        K: Into<PropertyKey>,
        P: Into<PropertyDescriptor>,
    {
        self.prototype.borrow_mut().insert(key, property.into());
        self
    }

It doesn't feel as punishing for AccessorDescriptors since they have more fields.
Another idea would be to have different methods for Accessor and Data properties, the first would have 3 arguments (get, set and attirbutes) the second would only have 2 (value and attributes).

@HalidOdat you implemented the ConstructorBuilder so I'd like to hear your ideas on this.
@tofpie hasn't been mentioned in this Issue and might want to give some input on this.

[HalidOdat]

@HalidOdat you implemented the ConstructorBuilder so I'd like to hear your ideas on this.

Another idea would be to have different methods for Accessor and Data properties, the first would have 3 arguments (get, set and attirbutes) the second would only have 2 (value and attributes).

This approach is much better. I don't think changing .property to take property descriptor is the right answer. Instead we would add a new method called .accessor(&mut self, get: Option<GcObject>, set: Option<GcObject>, attribute: Attribute) that would add an accessor property to the prototype.

If we want to add a property descriptor we should have a method that does that with a clear name, instead of property it should be:

    pub fn property_descriptor<K, P>(&mut self, key: K, property: P) -> &mut Self
    where
        K: Into<PropertyKey>,
        P: Into<PropertyDescriptor>,
    {
        self.prototype.borrow_mut().insert(key, property.into());
        self
    }

We should also add a method static_accessor that would add it to the constructor object itself, like .static_property.

[RageKnify]

Yes, any change would also include updates to the static variants of these functions.
Since they are all properties I'd say to have 6 different functions:

• data_property
• static_data_property
• accessor_property
• static_accessor_property
• property_descriptor
• static_property_descriptor

(I prefer to use more complete names to make them easier to understand)

I'm not sure we would have use for the last 2 immediately but it seems like a nice API to provide.
I'll probably work on implementing this tomorrow or wednesday, might do a separate PR so that it isn't attached to the Set PR.