オブジェクトが循環参照しているかを検証する方法(ガチめ) #TypeScript

循環参照ってなんですか

循環参照(Circular reference)は、オブジェクトが子要素として持つオブジェクトが自分自身を持つような状態を指します。(孫でもひ孫でもいいたいことは同じです)

TypeScriptであれば最も簡単な例はこのようなものです。

const obj1: any = {};
const obj2: any = {
  obj1
};

obj1.obj2 = obj2;

obj1の子供にobj2というオブジェクトが、そしてobj2の子供にobj1というオブジェクトがあることがわかります。

JavaScript, TypeScriptで昔からある鉄板の方法

JavaScriptでは組み込みで存在するメソッドを使うことによって一発でそのオブジェクトが循環参照しているかどうかを検証することができます。すでにご存じのかたも多いとは思いますが、そのメソッドとはJSON.stringify()です。

JSON.stringify()は文字列という直列化可能なモノへ変換するために、元のオブジェクトも直列化可能である必要があります。そのため循環参照しているオブジェクトを検出するとTypeErrorを投げて処理を終了します。この例外をcatchすればそのオブジェクトは循環参照しているといえます。

const isCircular = (obj: object): boolean => {
  try {
    JSON.stringify(obj);

    return true;
  }
  catch (err) {
    if (err instanceof TypeError) {
      return false;
    }

    throw err;
  }
};

当然ながら、この手法はJavaScript, TypeScriptで可能な方法です。他の言語でも使えるような普遍的な知識としてそのオブジェクトが循環参照しているかどうかを検証できる方法を今回は紹介します。

どうやって循環参照を検出するんですか

循環参照を検出するためには、やや煙たがられているオブジェクトの性質を使います。その性質とはオブジェクトが等しいかどうかを判定することです。

一般的にオブジェクトを代表するリファレンス型は等値比較ができません。

{} === {}
// false

これは、リファレンス型のときの等値比較はプリミティブ型のそれとは異なり、指しているオブジェクト(のインスタンス)自身が等しいかどうかを指しているからです。同じキー、プロパティを持っているかどうかの検査ではないというプログラムの初心者が陥りやすい罠でもあります。

オブジェクトが同一かどうかを検出につかうとどうなるんですか

オブジェクトを再帰的に走査していくときに、コールスタックのようなモノを保持して、その中に同じオブジェクトが現れるかどうかを判定すればよいということになります。

成果物

以下が成果物です。

export const isCircular = (value: unknown): boolean => {
  return isCircularInternal(value, new WeakSet<object>());
};

const isCircularInternal = (value: unknown, objs: WeakSet<object>): boolean => {
  if (!isObject(value)) {
    return false;
  }
  if (objs.has(value)) {
    return true;
  }

  objs.add(value);

  return Object.keys(value).some((key: string) => {
    return isCircularInternal(value[key], objs);
  });
};

const isObject = (value: unknown): value is {[key: string]: unknown} => {
  if (typeof value === 'object') {
    if (value === null) {
      return false;
    }

    return true;
  }

  return false;
};

コツは以下です。

isCircularは直接処理をせず、オブジェクトの走査をするときの訪問済みオブジェクトを溜めるWeakSetを確保します
オブジェクトに対し再帰的にすでに訪問したオブジェクトがあるかを検証します
訪問していない場合はWeakSetに溜めます

最後に

この手法はオブジェクトリテラルに限らず、プロトタイプベースのオブジェクト(要するにクラスなど)でも可能です。木を作ったときやグラフを走査するときに同じオブジェクトを参照していないかを検証するときにも使えます。