【JavaScript】再帰処理でJSONの階層を掘り進めて末端の値を変更したい

#あらすじ
むかしむかし（先週）あるところに、若いプログラマーがおったそうな。
彼のいるプロジェクトには、大事な情報が詰まった「**おしながき**」という膨大なJSONファイルがあったそうな。

ある日、プログラマは上司にこう言われた。

>「OO.XX.OO.XX.OO.XX」という文字列で階層が与えられるから、「おしながき」のその階層の値を、これまた与えられた値に変更して、新しい別のJSONファイルとして出力してほしい。

はてさて、プログラマはこの先、どうなりますことやら。

（この物語は、2割くらいフィクションです）

#指令の詳細
**おしながき**には、サービスで用いる基準値や名前など、大量のデータが入っています。また、そのデータ量もさることながら、階層も深く、多少浅いものから、かなり深いものまでマチマチです。

今回は、そんなおしながきをベースにしたテストデータを作って欲しいという指示を受けました。おしながきの中の、指定された階層の値のみを、テスト値に変更し、別ファイルとして出力しろというものです。

指定に用いられる情報は、以下の条件を満たします。

- 指定で与えられるデータの形式は`(ID): { {"layer": (string), "value":(any)} }`の連想配列
- 指定で与えられるデータは**複数**
- 階層情報はドット区切り
- 階層情報は**必ず末端**
- 階層が「\*」の場合は、その階層は**配列**

###おしながきの例

```json:oshinagaki.json
{
 "おしながき": {
  "メイン": {
   "焼き鳥": {
    [
     {"品名": "カワ", "味付け": ["タレ", "塩"]},
     {"品名": "モモ", "味付け": ["タレ", "塩"]},
     ...
    ]
   }
  },
  "サブ": {...},
  "ドリンク" {...},
  ...
 }
}
```

###テスト値情報の例

```js:testValueInfo.js
var testValueInfo = {
 "0001": {
  "layer": "おしながき.メイン.焼き鳥.*.味付け.*", "value": ["無", "無"]
 },
 "0002": {
  ...
 },
 ...
}
```

例を見て分かる通り、配列とオブジェクトが複雑に入り混じったJSONを掘り進めるのは簡単ではありませんでした。

#軽く計画
この指示を受け、頭の中に軽く浮かんだ流れは以下の通りです。

>テスト値情報1つのIDの、階層を示すドット区切りの文字列を配列に変換する。
↓
配列に基づいて再帰的におしながきを探索していき、最深部まで進める
現時点の階層が配列の場合はfor処理を使い、配列要素ごとに掘り進める
↓
末端の値をテスト値に変更し、末端ではテスト値を、それ以外では**JSONオブジェクト**を再帰的に返していく。
↓
再帰処理が終わった後は、元のおしながきに返り値を代入する。
↓
次のIDへ

詳細に関しては後述で説明するとします。
上記より計算量が少ない、スマートなアルゴリズムもあるとは思います。例えば、次のテスト値情報を見た時、共通しているディレクトリ戻って次の探索を行う...などが考えられますが、今回はシンプルで分かりやすい方法にします。

#実装
##階層情報文字列を配列に変換する
JavaScriptには、**split()**という便利なメソッドがあります。これは、引数で与えられた文字（複数文字可）を区切りとし、文字列を分割して配列にしてくれるスグレモノです。

```js:sample.js
var str = "これ・それ・あれ・どれ";

var array = str.split("・");

array.forEach(function(item, index) {
    console.log(index + ":" + item + "\n");
})
```

```出力
0:これ
1:それ
2:あれ
3:どれ

```

今回はこれに加えて、配列の末尾に**テスト値**を付け足します。
さらに、指定情報をforEachでループしながら、1回1回頭から探索することにします。

```js:sample.js
//どこからかJSONを取得する
var json = getJson();

// testValueInfo:全ての指定情報が記された連想配列
// {
//    (id): {
//        layer: (階層情報),
//        value: (テスト値)
//    }
// }
testValueInfo.forEach(info, index){
    // 階層情報＆テスト値を入れる配列
    var layerArray;

    // layerArrayに階層情報を格納
    layerArray = info.layer.split(".");

    // layerArrayの末尾にtestValueを追加
    layerArray.push(info.value);

    // JSONを探索して値を更新する関数（これから定義）
    json = digJson(json, layerArray);
}
```

階層情報にテスト値を加えた理由は、再帰処理中はずっとテスト値が不変なので、いちいち引数に与える必要はないと考えたからです。

##再帰的におしながきを探索する
処理のおおまかな流れは以下のようになります。

```js:digJson()
// JSONを掘り進める関数
// 引数1:JSON。再帰が進むごとに深くなり、小さくなる
// 引数2:階層情報＆テスト値の配列
function digJson(json, layerArray){
    // 現在いる階層
    var currentLayer = layerArray[0];
    // それより深い階層（配列）
    // slice()で先頭要素を除外
    var deeperLayers = layerArray.slice(1);

    // 末端だったらホゲホゲ
    // 配列だったらフゴフゴ

    // 自分より深い階層で更新されたJSONを代入（再帰）
    json[currentLayer] = digJson(json[currentLayer], deeperLayers);

    // 自分自身を返却。１つ上の階層に代入される
    return json;
}
```

再帰処理はマトリョーシカ人形に例えられることがよくありますが、今回はJSONということで、まさにマトリョーシカです。

親子のように例えるならば、子のJSONに伝言を頼み、結果が返ってくるのを待ちます。末端の子は値を変更して親に返事をし、今度は子が親に伝言を頼み、子の役目は終了していきます。最も大きな親まで伝言が届いたとき、その親が持っているJSONはテスト値が埋め込まれた**おしながき全体**になっているのです。

「配列をスライスしてJSONを深くするだけなら、再帰じゃなくてforEachで良くない？」とも思いましたが、JSONの中に配列もあり、それがどこにあって何個出てくるのかが非固定なので、このような方法にしました。
また、「配列の場合は"\*"を入れる」という独自のフォーマットを採用していることもあり、ライブラリなども使えなく、自前で処理を組むしかなかったように思います。

##currentLayerが"\*"（配列）のとき
このときはforEachを使って、**要素ごとに返却を待ちます**。

先ほどのように親子で例えるならば、子が三つ子や四つ子などの場合、まず長男に伝言を頼み、長男の返事を待ってから次男に伝言を頼み、次男の返事を待ってから...といった具合です。

```js:
// 現階層が配列の場合
if(currentLayer === "*"){
    // 要素ごとにdigJson()を実行
    json[currentLayer].forEach(data, index){
        json[currentLayer] = digJson(data, deeperLayer);
    }
}
// 配列ではない時
else{
    json[currentLayer] = digJson(json[currentLayer], deeperLayers);
}
```

##階層の末端に到達したとき
階層の末端では、引数の「json」にはJSONオブジェクトではなく、単体の値もしくは配列が入っています。（少々ややこしいですが）
末端の子には、jsonにテスト値を代入してもらい、それを親に渡します。親はそれを使って自分の持っているJSONオブジェクトを更新し、そのまた親へ渡す...というのをリレーしていきます。

```js:
if(layerArray.length > 2){
    // 末端ではない時の処理
}
// 末端の時
else{
    var testValue = layerArray[1];

    // 末端の値が配列の時
    if(currentLayer === "*"){
        // 配列の要素を全てテスト値に更新
        json.forEach(function(data, index) {
            json[index] = testValue;
        })
    }
    // 配列ではない時
    else {
        json = testValue;
    }
}
```

##digJson()の全容
これらの処理をひとつにまとめ、digJson関数の完成です。

```js:digJson()
// JSONを掘り進める関数
// 引数1:JSON。再帰が進むごとに深くなり、小さくなる
// 引数2:階層情報＆テスト値の配列
function digJson(json, layerArray){
    // 現在いる階層
    var currentLayer = layerArray[0];
    // それより深い階層（配列）
    // slice()で先頭要素を除外
    var deeperLayers = layerArray.slice(1);

    // 末端ではない時
    if(layerArray.length > 2){
        // 現階層が配列の場合
        if(currentLayer === "*"){
            // 要素ごとにdigJson()を実行
            json[currentLayer].forEach(data, index){
                json[currentLayer] = digJson(data, deeperLayer);
            }
        }
        // 配列ではない時
        else{
            json[currentLayer] = digJson(json[currentLayer], deeperLayers);
        }
    }
    // 末端の時
    else{
        var testValue = layerArray[1];

        // 末端の値が配列の時
        if(currentLayer === "*"){
            // 配列の要素を全てテスト値に更新
            json.forEach(function(data, index) {
                json[index] = testValue;
            })
        }
        // 配列ではない時
        else {
            json = testValue;
        }
    }

    // 自分自身を返却。１つ上の階層に代入される
    return json;
}
```

`if(currentLayer === "*")`が2回出てくることに少し違和感がありますが、仕方ない...と思います。もうちょっとスマートなやり方がある気がしないでもないでもないですが...気にしないことにします。

#感想
**再帰は難しい！！**

理由としては、forやwhileなどのループと違ってメソッドなので、引数・ローカル変数・返り値を適切にしなければならない点が原因だと思います。コードだけ見れば簡素ですが、自分のような若造にとってはなかなか骨のあるミッションでした。再帰を利用するというのを比較的早く思い浮かんだのが幸いでした。

実際の業務ではもう少し複雑な条件で作っていますが、それはまた別のお話...。

#おまけ
実際の業務ではバグ対策として、指定された階層が見つからない場合は何もしない（自分自身をreturnする）という処理を入れているのですが、その際に得た知識です。

```js
var value = null;

value === undefined; // false
value ==  undefined; // true
```

このおかげでちょっと困りました。おそまつ。