javascriptでJSONを比較する(方法を考えてみた)
コロナにかかったり、身内のコロナの病み上がりの面倒を見たり(料理スキルが上がった)、ネットゲームの大型アップデートに気を取られたりしつつも前進はしているゲームブックプロジェクトです。
現在、組んでいるのは2つのデータ(例えば保存したデータと読み込み済みのデータ、いずれもJSON)が同じ内容かをチェックするロジックです。
何故このような機能が必要かは割愛しますが、1例だけ上げるとWebブラウザの複数タブで同じデータをいじった場合、厄介な問題を起こしかねないという事があります。
さて、JSONの比較ですが安直にstringify()で文字列化して比較と言うのは(単純な配列の場合を除き)使えません。(各項目の順番が同じになるとは限らないので)
とりあえず楽をするならば、loadshと言う便利な関数をまとめて提供しているライブラリがあるそうなので、その中の今回の目的に合った.isEqualと言う関数を使えばよいと理解はしたのですが、今回は自作で何とかしようと思い、その設計を兼ねての記事投稿になります。
ですので当然誤りの出る可能性もありますので思考実験として読んでいただければと思います。
＊JSONについて
まずJSONについてですがmdnの記述によれば以下のようになります。
・JSON は、オブジェクト、配列、数値、文字列、論理値、そして null をシリアライズする構文。
・プロパティ名は二重引用符で括った文字列にしなければなりません。末尾のカンマを置いてはいけない。
・数値は先頭にゼロを置くことは禁止。また、小数点は 1 桁以上の数字の後ろに置かなければいけない。 NaN と Infinity には対応していない。
JSON javascript|MDN
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/JSON
nullはあり得ますが、undefinedは使用されません。
＊初期チェック
単純なデータであれば良いのですが、オブジェクトの中に配列やオブジェクトが複数階層にわたって存在する(しかも階層の深さが不明)ですと、比較は簡単には行きません。
再帰的なロジックになるでしょうから、まともに比較を行う前に明白な差異が有る場合について処理を省く事から始めます。
まずJSON.stringify()で文字列化した後に、{}と[]、そして,(カンマ)の数を比較します。
いずれかの数が異なる様であれば、それ以降のチェックは不要で異なる内容と判定できます。
全体の文字列長の比較も考えたのですが、まず問題は起きないとは思うものの、
１．予期せぬケースが無いと言う確信が持てない
ので、安全第一で採用しない事にします。
※コーディングミスした場合、問題が起こりえることを確証しました。
例えば"1.23"と1.23を等しいとみなすかのオプションをつけたいですね。
＊チェックの方針①
比較する２つのJSONの(各階層の)キーを調べ、値が数値、文字列、論理値、そして nullの場合のアクセスキー(適当な言葉が思いつかなかったので、ここではこう呼ぶ。詳細は後述)を配列として保存します。
アクセスキーは、JSONオブジェクトから目的のプロパティを指し示すキーの配列をここではこう呼ぶ事にしています。以下の例で判るでしょうか？
sampleJSON={"a":[{"b":"c"}, "xyz"]}
は、以下の２つのアクセスキーを持ちます。
[["a", 0, "b"], ["a", 1]]
つまり
sampleJSON["a"][0]["b"]="c"
sampleJSON["a"][1]="xyz
と言うように、プロパティが数値、文字列、論理値、そして nullの値にアクセスするためのキー情報を配列にしたものをすべて列挙し、その配列を比較し、さらにそれに差異が無いならば(順番は除く)、各アクセスキーでアクセスしたプロパティをすべて比較するという方針を考えてみました。
＊チェックの方針②
①のロジックを考え始めて気づいたのですが、アクセスキーと言う考え方はともかく、あんまり効率的じゃない気がしました。
と言うのも、初期チェックでカンマの数をカウントしているのでプロパティの数は２つのJSONで同じになるはずです。(プロパティを追加する時は必ずカンマが必要)
ですので、片方のJSONについてアクセスキー(プロパティが数値、文字列、論理値、そして nullの値にアクセスするためのキー情報)を探しつつ、見つかったら、比較するJSONにそのアクセスキーでアクセスできるプロパティがあるか、有れば、(同じアクセスキーでアクセスした)二つのプロパティは同じかを見ていき、片方にプロパティが無い、あるいはプロパティの値が異なるものが見つかれば二つのJSONは同じではなく、すべてのアクセスキーで同じプロパティを持つことが確認できれば二つのJSONは同じと判断できます。
＊アクセスキーを順に調べる
と言う感じで方針が決まってきました(変更があるかもですが)
ではアクセスキーを順次探していく方法を考えていきます。
まず、以下のような変数が必要でしょう。
・JSONオブジェクト自身を0とした現在の探索階層
また、各階層は一つあるいは複数の断片に分かれています。
(断片が配列かObjectかによって若干異なる処理になりますがおおむね一緒)
また各断片は一つあるいは複数のキー(そしてプロパティ)を持ちます。
これにより探索位置は[階層、断片番号、断片内index]で表せます。
なんとなく組むべきロジックが見えてきましたので、実装的思考実験をして見ます。
０．初期チェック
１．まず初期位置はJSONデータそれ自身で探索位置は[0, 0, 0]、そしてアクセスキーは[](つまり空)
２．現在の探索位置のデータタイプを調べる(オブジェクト、配列、数値、文字列、論理値、 nullのいずれか。それ以外は異なるJSONとみなすを返す。)
３．オブジェクト、配列ならば階層を一つ潜る。
３－１．探索位置の階層に＋１．断片番号と断片内indexをともに０にする
３－２．階層内の断片数を取得する。
３－３．断片番号０の断片内最大indexを取得する。２．に戻る
４．オブジェクト、配列以外ならば、
４－１．もう一つのJSONと比較(アクセスキーを使用）
４－２．アクセスできない、あるいはプロパティが異なる(タイプおよび値)ならば
異なるJSONとして処理終了
４－３．同じプロパティならば、探索位置の断片内indexと断片内最大indexを比較
断片内index＜断片内最大indexならば探索位置の断片内indexを＋１
２．に戻る
４－４．そうでなければ、この断片の探索は調べ終わったので
・探索位置の断片番号と階層内の断片数を比較する。
・探索していない断片が有れば探索位置の断片番号を＋１
断片内indexを０に、さらに断片内最大indexを取得する。２．に戻る
・探索していない断片が無ければ
と、ここまで書いて階層を上がる方の処理を考慮していない事に気づきました。
とは言え、大体のコードは見えてきたので実際に書いてみて出来たものを次の投稿でサンプルコードとして投稿したいと思います。
