Function recurseLCS

packages/2d/src/lib/code/diff.ts:256–293

* Finds the longest common subsequence between the arrays * aLines[aStart...aEnd] and bLines[bStart...bEnd], inclusive. Then for each * subsequence, recursively performs another LCS search (via addSubMatch), * until there are none found, at which point the subsequence is dumped to * the

(
    aStart: number,
    aEnd: number,
    bStart: number,
    bEnd: number,
    uniqueCommonMap: Map<string, Subsequence> = uniqueCommon(
      aLines,
      aStart,
      aEnd,
      bLines,
      bStart,
      bEnd,
    ),
  )

   * aLines[aStart...aEnd] and bLines[bStart...bEnd], inclusive.
   */
  function recurseLCS(
    aStart: number,
    aEnd: number,
    bStart: number,
    bEnd: number,
    uniqueCommonMap: Map<string, Subsequence> = uniqueCommon(
      aLines,
      aStart,
      aEnd,
      bLines,
      bStart,
      bEnd,
    ),
  ) {
    const lcs = longestCommonSubsequence(uniqueCommonMap);

    if (lcs.length === 0) {
      addSubMatch(aStart, aEnd, bStart, bEnd);
    } else {
      if (aStart < lcs[0].aIndex || bStart < lcs[0].bIndex) {
        addSubMatch(aStart, lcs[0].aIndex - 1, bStart, lcs[0].bIndex - 1);
      }

      let i;
      for (i = 0; i < lcs.length - 1; i++) {
        addSubMatch(
          lcs[i].aIndex,
          lcs[i + 1].aIndex - 1,
          lcs[i].bIndex,
          lcs[i + 1].bIndex - 1,
        );
      }

      if (lcs[i].aIndex <= aEnd || lcs[i].bIndex <= bEnd) {
        addSubMatch(lcs[i].aIndex, aEnd, lcs[i].bIndex, bEnd);
      }
    }
  }

  recurseLCS(0, aLines.length - 1, 0, bLines.length - 1);