【JavaScript】Object.deepEquals(仮)

こんにちは。

今回はJavaScriptにおける未解決問題(?)のお話です。

オブジェクト比較

JavaScriptにおいて、オブジェクト同士の比較は非常に面倒なことのひとつです。

割と有名な話なので、いくつかのパターンをざっとおさらいすると...

Abstract-Equal

const o1 = {};
const o2 = {};

o1 == o2; // true

どちらも object 型なので、中身のプロパティが何であれ true と解釈されます。

Strict-Equal

const o1 = {};
const o2 = {};

o1 === o2; // false

それぞれ別インスタンスなので、中身のプロパティが何であれ false と解釈されます。

for-in

const o1 = {};
const o2 = {};

for(const key in o1){
    if(o1[key] !== o2[key]){
        throw "Not equal";
    }
}

含まれていることは証明されますが、一致の証明にはなりません。
また、ネストしたオブジェクトの場合は、再帰処理をしないと前例のとおり「別インスタンス」と見なされてしまいます。

JSON-Compare

const o1 = {};
const o2 = {};

JSON.stringify(o1) === JSON.stringify(o2); // ???

良さげな感じはしますが、オブジェクトがシリアライズされる時のプロパティの順番は㍉も保証されておらず、実行エンジンやタイミングによって都度変動するため、実は全くアテになりません。

恐ろしいことに、巷ではオブジェクト比較の場面において、この実装が使用されるケースはそこそこあると、風の噂で聞いたことがあります。

他にも、たくさんの諸先輩方がこの難題へ立ち向かおうと執筆された記事が、いくつも存在します。

deepEquals

そのうち、私が立ち向かい辿り着いた解をご紹介します。

deep-equals.ts

function deepEquals(d1:any, d2:any){
    function toKV(o:any){
        return Object.entries(o).sort(([k1], [k2])=>{
            let i = 0;

            while(k1.at(i) === k2.at(i)){
                if(k1.at(i) === undefined && k2.at(i) === undefined){
                    throw "Same property name.";
                }

                i++;
            }

            return (k1.codePointAt(i) ?? 0) - (k2.codePointAt(i) ?? 0);
        });
    }

    if(d1 === d2){
        return true;
    }

    if(typeof d1 !== "object" || typeof d2 !== "object" || d1 === null || d2 === null){
        return false;
    }

    const kv1 = toKV(d1);
    const kv2 = toKV(d2);

    if(kv1.length !== kv2.length){
        return false;
    }

    for(let i = 0; i < kv1.length; i++){
        const [k1, v1] = kv1.at(i);
        const [k2, v2] = kv2.at(i);

        if(k1 !== k2 || !deepEquals(v1, v2)){
            return false;
        }
    }

    return true;
}

順を追って見ていきましょう。

まずショートサーキットとして、同じインスタンスであれば一致、どちらかが object 型でなけれなば不一致となります。
そして必然的に、引数としてプリミティブが入力された際もここで捌くことができます。

次に、当メソッドの特徴である Object.entries() でオブジェクトを配列化し、ソーティングします。

ソーティング方法は、ざっくり言うと前後のプロパティ名をUnicodeの数値へ変換して比較するのですが、プロパティ名が途中まで同じ場合への対策として、同じ文字であれば1文字ずつ位置をずらしていき、異なる文字が現れたときに初めて比較します。
なお、同名プロパティは存在し得えませんが while を使用していることもあり、どちらも undefined になった場合は、無限ループ回避で念のため例外を出すようにしています。

ソートを終えたら、双方の配列長を比較し、異なれば則ちプロパティ数が違うことになるので不一致となります。

ここからは for ループで1要素ずつ中身を精査していきます。

まず、双方のプロパティ名が異なるか、再起処理でプロパティ値を入力し不一致が返されれば不一致となります。
上述の通り、再起処理は引数として渡すプロパティ値がオブジェクトでもプリミティブでも問題ありません。

そして for を抜け、最後まで到達したということは、則ち全て一致していたことになるので true を返します。

なお、配列を Object.entries() へ入力した場合、インデックスがそのままプロパティ名となるため、引数として配列を入力しても挙動には影響ありません。

Object.entries(["value", "value", ...]);
// [["0", "value"], ["1", "value"], ...]

欠点として、同クラスから生成された異なる this の値を持つインスタンスや、単純にメソッドなどは比較できません。

そこだけ注意すれば、割とマトモに動くのではないでしょうか。

さいごに

JavaScriptのオブジェクト比較は本当に厄介なので、ご指摘などありましたらご教示いただければ幸いです。