オブジェクトが循環参照を持つかどうか判定する

javascripter's
gist: 139376 — Gist
に載せた。

function isCircular(obj) {
  function isCircularWithAncestors(obj, ancestors) {
    var k;
    for (k in obj)
      if (ancestors.indexOf(obj) >= 0 ||
        obj[k] instanceof Object && isCircularWithAncestors(obj[k], ancestors.concat([obj])))
        return true;
    return false;
  }
  return obj instanceof Object && isCircularWithAncestors(obj, []);
}

ref.

cyclicなオブジェクトの判定について調べててv8のJSON.stringifyの実装見たら、stack作って通ったオブジェクトを記録してリニアサーチしてた。もっといい方法ないかなあ。

http://twitter.com/javascripter/status/2433939977

Error 404 (Not Found)!!1のStackContains、stack.pushのあたり。

@javascripter 訪れた全部のノードと比較してはだめで、現在のノードの直径の先祖だけで比べないといけないということ。そのコードで十分効率的だと思いますけど。JS の Array じゃなかったらもっと良い気が…

http://twitter.com/edvakf/status/2434308777