Javascript で diff (内部仕様についての補足４)

10/14 に投稿したJavascript で diff (通信なし、ローカルで完結)の内部仕様についての補足、その４です。
Javascript で diff (内部仕様についての補足)
Javascript で diff (内部仕様についての補足２)
Javascript で diff (内部仕様についての補足３)

移動ブロックの検出

前回までで、ファイルの差分が生成されたので、今回は移動ブロックを検出することにします。

Javascript で diff (内部仕様についての補足) で述べた内容の繰り返しとなりますが、移動ブロックを検出する手前までの手順は、

• ファイル１とファイル２から、内容が合致する行を探してペアを生成する。
• ペアが作れない行があったら、それは差分である。

比較開始前に、ファイル内の各行に対して、同一内容の行が複数存在するかどうかを調べておきます。
ファイル内に同じ内容の行が複数ある場合は、その時点では、比較対象ファイルのどの行とペアになるか確定しません。
しかし、「ファイル１で一意な内容の行」と「ファイル２で一意な内容の行」でペアが生成された場合、そこでペアが確定するので、決定した組み合わせを記録しておきます。
実際の実装は、InitInfo() 関数を参照して下さい。

InitInfo(len1, len2) {
	const bIgnoreCase = this.bIgnoreCase, isBlank_ = DIFF_ORZ.isBlank;
	const hash = (s_org, bIgnoreCase) => {
		let s = s_org.trim().replace(this.BLANK_PATTERN, ""), len = s.length;
		if (len == 0) { return 0; }
		if (bIgnoreCase) { s = s.toLowerCase(); }
		return [...s].reduce((v, c) => { return (c.codePointAt(0) ^ (v << 2)); }, len);
	}
	this.vInfo_L = this.vLeft.map(s => { return {status:"+", pair:-1, isBlank:s[isBlank_](), hash:hash(s, bIgnoreCase), UniquePair:-1}; });
	this.vInfo_R = this.vRight.map(s => { return {status:"+", pair:-1, isBlank:s[isBlank_](), hash:hash(s, bIgnoreCase), UniquePair:-1}; });
	if (!this.bDetectSimilarLine && !this.bDetectMovedBlock) { return; }
	let [vIsUnique_L, vIsUnique_R] = [this.vInfo_L.map(o => !o.isBlank), this.vInfo_R.map(o => !o.isBlank)];
	for (let i = 0; i < len1; i++) {
		if (!(vIsUnique_L[i])) { continue; }
		for (let j = len1 - 1; j > i; j--) {
			if (!(this.vInfo_L[j].isBlank) && this.IsDuplicated(this.vLeft, this.vInfo_L, i, j, bIgnoreCase, 2)) {
				vIsUnique_L[i] = vIsUnique_L[j] = false;
				break;
			}
		}
	}
	for (let i = 0; i < len2; i++) {
		if (!(vIsUnique_R[i])) { continue; }
		for (let j = len2 - 1; j > i; j--) {
			if (!(this.vInfo_R[j].isBlank) && this.IsDuplicated(this.vRight, this.vInfo_R, i, j, bIgnoreCase, 2)) {
				vIsUnique_R[i] = vIsUnique_R[j] = false;
				break;
			}
		}
		if (!(vIsUnique_R[i])) { continue; }
		for (let j = 0; j < len1; j++) {
			if (vIsUnique_L[j] && (this.vInfo_L[j].UniquePair < 0) && (this.CompareStr(j, i, true) > 1)) {
				[this.vInfo_R[i].UniquePair, this.vInfo_L[j].UniquePair] = [j, i];
				break;
			}
		}
	}
}

差分検出後、上記の例ですと、「ファイル１で一意な内容の行」と「ファイル２で一意な内容の行」の組み合わせがまだ残っている状態です。
そこで、差分とされている hunk (不一致行のかたまり) から、

• InitInfo() 関数で [UniquePair] として記録しておいた行の組み合わせを検出する。
• 起点となる行の直前の行どうしも一致していたら、さかのぼれるところまでさかのぼって行どうしのペアを生成する。
• 起点となる行の直後の行どうしも一致していたら、下向きに進めるところまで進んで行どうしのペアを生成する。
• 決定した組み合わせを移動ブロックとする。

実際の実装は DetectMovedBlock() 関数となります。
[UniquePair]の組み合わせと前後の行を探しつくした後、付近のhunkどうしで、さらに余っている行どうしのペアが生成できる場合は、移動ブロックとして記録します。
diff_orz では、[UniquePair]でない組み合わせは今のところ前後2ブロックしか検出対象としていないので、探索範囲を広げたい場合は、searchNeighborHunk() 関数の該当部分を書き換えてください。
長いファイルで、先頭付近の「}」と終端近くの「}」が移動ブロック扱いになると見づらかったため、このような仕様になっています。

searchNeighborHunk(o_L) {
	//前後2ブロックが検出対象
	return {start:(this.vList[Math.max(0, o_L.current - 2)].start + 1), 
			end:(this.vList[Math.min(this.vList.length - 1, o_L.current + 2)].end - 1)};
}

　　　↓↓↓↓↓

searchNeighborHunk(o_L) {
	//前後4ブロックが検出対象
	return {start:(this.vList[Math.max(0, o_L.current - 4)].start + 1), 
			end:(this.vList[Math.min(this.vList.length - 1, o_L.current + 4)].end - 1)};
}

なお、半角スペースと半角タブしか含まれていない hunk は、移動ブロックの検出対象から外しています。
半角スペースと半角タブしか含まれていない行は、内容のある行どうしで移動ブロックを検出した後、前後に探索範囲を広げたときに移動ブロックに含めるようにしています。