mergeLines

tcmts.cli.merge.mergeLines · #xs4ngyiy · term · runs anywhere

Three-way merge of lines, as git merge-file --diff3 does: where only one side changed a stretch of the base, that side's lines; where both changed it alike, those. The lines both sides left in place divide it into stretches; one both changed differently (or both added to at the same place) is a conflict, written as git writes one: ours, the base's and theirs, between markers labelled with labels. conflicts: how many there are; stretches: where what either side changed is in what's merged; changed: how many lines each side added and removed.

import { lineDiff } from "#codebase/tcmts/cli/diff";
import type { MarkerLabels, Merged, Stretch } from "#codebase/tcmts/cli/merge";

export function mergeLines(
  base: string[],
  ours: string[],
  theirs: string[],
  labels: MarkerLabels = { ours: "ours", base: "base", theirs: "theirs" },
): Omit<Merged, "text" | "body"> & { lines: string[] } {
  // which line of a side each base line is, where the side kept it, and how many lines it added and removed
  const kept = (side: string[]) => {
    const at = new Map<number, number>();
    const changed = { added: 0, removed: 0 };
    let i = 0;
    let j = 0;
    for (const [op] of lineDiff(base, side)) {
      if (op === " ") at.set(i++, j++);
      else if (op === "-") {
        i++;
        changed.removed++;
      } else {
        j++;
        changed.added++;
      }
    }
    return { at, changed };
  };
  const [{ at: inOurs, changed: oursChanged }, { at: inTheirs, changed: theirsChanged }] = [
    kept(ours),
    kept(theirs),
  ];
  const changed = { ours: oursChanged, theirs: theirsChanged };
  const stretches: Stretch[] = [];
  const same = (a: string[], b: string[]) => a.length === b.length && a.every((l, i) => l === b[i]);
  const out: string[] = [];
  let conflicts = 0;
  let [b, o, t] = [0, 0, 0];
  for (;;) {
    // the next base line both sides kept, and the stretch before it
    let k = b;
    while (k < base.length && !(inOurs.has(k) && inTheirs.has(k))) k++;
    const [oEnd, tEnd] =
      k < base.length ? [inOurs.get(k)!, inTheirs.get(k)!] : [ours.length, theirs.length];
    const was = base.slice(b, k);
    const [os, ts] = [ours.slice(o, oEnd), theirs.slice(t, tEnd)];
    const [byOurs, byTheirs] = [!same(os, was), !same(ts, was)];
    const from = out.length;
    if (!byOurs || same(os, ts)) out.push(...ts);
    else if (!byTheirs) out.push(...os);
    else {
      conflicts++;
      out.push(
        `<<<<<<< ${labels.ours}`,
        ...os,
        `||||||| ${labels.base}`,
        ...was,
        "=======",
        ...ts,
        `>>>>>>> ${labels.theirs}`,
      );
    }
    if (byOurs || byTheirs)
      stretches.push({
        by: byOurs && byTheirs ? "both" : byOurs ? "ours" : "theirs",
        at: from,
        lines: out.length - from,
        ...(byOurs && byTheirs && !same(os, ts) ? { conflict: true } : {}),
      });
    if (k >= base.length) return { lines: out, conflicts, stretches, changed };
    out.push(base[k]!);
    [b, o, t] = [k + 1, oEnd + 1, tEnd + 1];
  }
}

uses

used by