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.