Help us understand the problem. What is going on with this article?

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

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

移動ブロックの検出

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

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

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

移動ブロック_検出前.png

比較開始前に、ファイル内の各行に対して、同一内容の行が複数存在するかどうかを調べておきます。
ファイル内に同じ内容の行が複数ある場合は、その時点では、比較対象ファイルのどの行とペアになるか確定しません。
しかし、「ファイル1で一意な内容の行」と「ファイル2で一意な内容の行」でペアが生成された場合、そこでペアが確定するので、決定した組み合わせを記録しておきます。
実際の実装は、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;
            }
        }
    }
}

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

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

移動ブロック_検出後.png

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした