循環構造をサポートするdeep-equal関数 by marihachi · Pull Request #460

循環構造をサポートするdeep-equal関数 by marihachi · Pull Request #460 · aiscript-dev/aiscript

What

循環構造をサポートするdeep-equalを実装。
連想配列で必要になりそうなのでひとまず追加。
標準ライブラリ等でも使えそう。

~~少し怪しい部分があるので考えたい~~

Why

Additional info (optional)

constructorとか怪しいかも
あと特殊なやつってあったっけ

(Mapなどではない)通常のオブジェクトに任意のキーでユーザーがアクセスすることがなければ大丈夫そうかも

equal({ a: 1 }, { a: 1, b: 2 })

のように、オブジェクト同士の比較で後者が前者の要素全部+αを持っている時に偽陽になってしまうようです

怪しいのというと

let a, b, c;
a = { b };
b = { c };
c = { a };
let x = { a };
let y = { a: { b } };
equal(x, y); // false

が微妙ですね

怪しいのというと

let a, b, c;
a = { b };
b = { c };
c = { a };
let x = { a };
let y = { a: { b } };
equal(x, y); // false

が微妙ですね

これ修正されてませんか？

This comment was marked as outdated.

あ、テストケースが間違ってますね

の時点ではbはundefinedです
多分

これだと動きました

let a: any, b: any, c: any;
a = { b };
b = { c };
a.b = b;
c = { a };
b.c = c;
let x = { a };
let y = { a: { b } };
console.log(deepEqual(x, y)); // true

これだと動きました

let a: any, b: any, c: any;
a = { b };
b = { c };
a.b = b;
c = { a };
b.c = c;
let x = { a };
let y = { a: { b } };
console.log(deepEqual(x, y)); // true

確認できました

let a=[{a:[]}]
let b=[{a:[]}]
a[0].a[0]=a
b[0].a[0]=b[0]

deepEqual(a,b) // true

になるみたいです

循環の判定方法にバグがあるかも
両方が循環した位置だけでは一致を判断できないかも？

Comment on lines +12 to +18

		// 参照の循環をチェック
		// 両方の循環が確認された時点で、その先も一致すると保証できるためtrueで返す
		const indexA = refsA.findIndex(x => x === a);
		const indexB = refsB.findIndex(x => x === b);
		if (indexA !== -1 && indexB !== -1) {
		return true;
		}

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

愚直にやるなら、indexAとindexBが同時に見つかるのが二回確認できればその先の一致が保証できると思います（一回だとループの開始位置にズレがある場合があるが、二回なら一回目のループ終了地点で開始を固定できる）

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

aとbで同じ位置で循環が検出される場合は良いと思っています。
aとbでそれぞれ別の位置を起点として循環が現れるが、パターンとしては一致しているor一致してないというのを判定する処理が必要な気がしています。
具体的な処理は思いついていません。

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ん、2回まわすってことですか？

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

はい。同位置で循環があった地点からもう一度回せば、「aとbで同じ位置で循環が検出される場合」に持ち込めるのでうまくいくはずです。（だいぶ効率が悪いとは思いますが）

let x: any = { a: { b: null } };
let y: any = { a: { b: null } };
x.a.b = x;
y.a.b = y.a;
deepEqual(x, y); // true

になってしまう

let a=[{a:[]}]
let b=[{a:[]}]
a[0].a[0]=a
b[0].a[0]=b[0]

deepEqual(a,b) // true

になるみたいです

これと同じことか