JavaScriptのSetを調べる

先日、JavaScript の Set について聞かれたのですが、「早く一意のリストを作成できる」ということしか答えられませんでした。
より深く知りたくなったので調べていきたいと思います。

そもそも Set とは

Set オブジェクトは値のコレクションです。 Set に重複する値は格納出来ません。 Set 内の値はコレクション内で一意になります。 Set はその要素について挿入順で反復処理を行うことができます。挿入順は、各要素が add メソッドによって正常に Set に挿入された順番に対応します。
引用元: Set 解説

イテレーター的役割もあったんですね！
Set 内の値はコレクション内で一意となるらしいのですが、どういった作りになっているんでしょうか。
EcmaScript でより詳しい Set の仕様をみていきたいと思います！

仕様を見てみよう

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.
Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structure used in this specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.
引用元: 24.2 Set Objects

異なる値かどうかは SameValueZero アルゴリズムで識別されるんですね！
Set オブジェクトはハッシュテーブルか他の(平均して要素にアクセスする時間が短い)メカニズムできているそうです。

SameValueZero とは
JavaScript における比較演算の一種です。
厳密等価との違いは NaN を等価として扱うことです。また、SameValue との違いは-0と+0が等価として扱うことです。
より詳しい違いは下記の MDN に載っているので確認してみてください
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness#comparing_equality_methods

なぜ Set に SameValueZero が使用されいているのか

-0s can sneak into your code fairly easily via arithmetic operations, but you almost always desire -0 to be treated the same as +0, so distinguishing them will just cause spurious failures.
引用元: https://github.com/tc39/proposal-Array.prototype.includes?tab=readme-ov-file#why-samevaluezero

たしかに、-0は算術演算を通じてコードに簡単に入り込む可能性があるので、-0と0を同値で扱うものの方が良さそうですね。

new Set の実装をみてみよう

それでは実際に new Set()をしたときはどのような挙動が起きるのでしょうか。
Set の constructor の仕様を確認してみます。

24.2.1.1 Set ( [ iterable ] )
This function performs the following steps when called:

1. If NewTarget is undefined, throw a TypeError exception.
2. Let set be ? OrdinaryCreateFromConstructor(NewTarget, "%Set.prototype%", « [[SetData]] »).
3. Set set.[[SetData]] to a new empty List.
4. If iterable is either undefined or null, return set.
5. Let adder be ? Get(set, "add").
6. If IsCallable(adder) is false, throw a TypeError exception.
7. Let iteratorRecord be ? GetIterator(iterable, SYNC).
8. Repeat

引用元: 24.2.1.1 Set ([ iterable ])

順に中身を見ていきます。

1. If NewTarget is undefined, throw a TypeError exception.

new Set の new の部分をなしで Set を呼び出したら、エラーを投げます。

2. Let set be ? OrdinaryCreateFromConstructor(NewTarget, "%Set.prototype%", « [[SetData]] »).

OrdinaryCreateFromConstructor を使用して、Set のオブジェクトを作ります。
このとき、Set の プロトタイプを継承させて、Set を完成させます。

3. Set set.[[SetData]] to a new empty List.

作成した Set のオブジェクトに[[SetData]]という内部スロットに空のリストを入れます。

4. If iterable is either undefined or null, return set.

new Set(iterable)の引数 (iterable) が undefined や null の場合、
何も追加せずに空の Set オブジェクトを返します。

5. Let adder be ? Get(set, "add").

Set オブジェクトから add のメソッドを取得し、adder という名前にします。

6. If IsCallable(adder) is false, throw a TypeError exception.

上で呼び出した add が関数でなかったら、エラーを投げます。

7. Let iteratorRecord be ? GetIterator(iterable, SYNC).

new Set(iterable)の引数から、イテレータを取得します。

8. Repeat

下記を繰り返します。

a. Let next be ? IteratorStep(iteratorRecord).

イテレーターから次の要素を取得します。

b. If next is false, return set.

次の要素がなかったら、Set オブジェクトを返します。

c. Let nextValue be ? IteratorValue(next).

a で取得した要素を nextValue という名前にします。

d. Let status be Completion(Call(adder, set, « nextValue »)).

adder を使用して a で取得した要素を Set に追加します。
このときの adder の返り値を status として持ちます。

e. IfAbruptCloseIterator(status, iteratorRecord).

エラーが発生した場合、イテレータを適切に閉じてリソースを解放します。

---

それといって難しいことはしていないですね。
値が一意かどうかは add の関数内に書かれているようですね。
こちらも EcmaScript の仕様を見てみましょう！

Set.prototype.add 周りをみてみよう

24.2.3.1 Set.prototype.add ( value )
This method performs the following steps when called:

1. Let S be the this value.
2. Perform ? RequireInternalSlot(S, [[SetData]]).
3. For each element e of S.[[SetData]], do
   a. If e is not EMPTY and SameValueZero(e, value) is true, then
   i. Return S.
4. If value is -0𝔽, set value to +0𝔽.
5. Append value to S.[[SetData]].
6. Return S.

引用元: 24.2.3.1 Set.prototype.add(value)

1 つ 1 つ見ていきましょう。

1. Let S be the this value.

S を this(Set)とする。

2. Perform ? RequireInternalSlot(S, [[SetData]]).

S が[[SetData]]という内部スロットを持っているか確認する。

3. For each element e of S.[[SetData]], do

• a. If e is not EMPTY and SameValueZero(e, value) is true, then
  • i. Return S.

S の内部スロット[[SetData]]の各要素を e に対してループを行います。
e が空でない且つ、SameValueZero(e, value)が true の場合 S を返します。

4. If value is -0𝔽, set value to +0𝔽.

value が-0だったら+0として入れます。

5. Append value to S.[[SetData]].

新しい値 value を[[SetData]]に追加します。

6. Return S.

S を返します。

感想

もっと EcmaScript を読みたいなと思いました。