1
/**
2
 * Copy drift: two copies of a function, how alike they are, where they differ, and, given each one's git history,
3
 * whether they have been changing together or drifting apart.
4
 *
5
 * Three things a reader cannot do by eye, each a place the usual rule of thumb ("three copies, then abstract") goes
6
 * wrong:
7
 *
8
 *  1. **How alike, once names are set aside.** `get(url)` and `head(link)` are the same code. Every identifier,
9
 *     string and number becomes a placeholder, and the two token streams are compared with the ratio Python's
10
 *     difflib computes, 2M/T: matched tokens, twice, over the total. The algorithm is difflib's own, ported, with
11
 *     autojunk off, so a Python figure and this one agree.
12
 *  2. **Where they differ, and whether only in names.** A line diff of the two, each differing line marked as a name
13
 *     change (the same shape) or a real one.
14
 *  3. **Whether they move together.** From two `git log` listings, the commits that changed both, only one, or only
15
 *     the other, counted only after both copies existed. That last rule is the one that matters: `git log -L`
16
 *     follows a range of lines back past the moment it became a copy, and a change made when there was one copy
17
 *     is not a one-sided change.
18
 *
19
 * What it deliberately cannot do: say whether a one-sided change was a missed update or a deliberate difference.
20
 * Only reading the diff can. It leads with how many there are and lists them, newest first, so you can, then shows
21
 * where the code differs today, above the history that produced it.
22
 *
23
 * Six inputs, down from nine in 1.x: the language is read from the code, the comparison is always of the bodies,
24
 * and the near-duplicate line is fixed at cochange.py's 85%. Each is stated in the result, so nothing is hidden.
25
 */
26
import type { Cell, Field, Output, Series, Tool } from "@toolbench/sdk";
27

28
type Input = {
29
  a: string;
30
  b: string;
31
  historya: string;
32
  historyb: string;
33
  since: string;
34
  ignore: string;
35
};
36

37
class InputError extends Error {
38
  readonly input: string;
39
  constructor(message: string, input: string) {
40
    super(message);
41
    this.input = input;
42
  }
43
}
44

45
// ---------------------------------------------------------------------------------------------------------------
46
// Tokens
47

48
export type Lang = "python" | "js" | "c";
49

50
/** Python 3.12's keyword.kwlist: soft keywords such as `match` and `type` are names, as tokenize treats them. */
51
const PY_KEYWORDS = new Set(
52
  "False None True and as assert async await break class continue def del elif else except finally for from global if import in is lambda nonlocal not or pass raise return try while with yield".split(
53
    " ",
54
  ),
55
);
56

57
const JS_KEYWORDS = new Set(
58
  "abstract as async await break case catch class const continue debugger declare default delete do else enum export extends false finally for from function get if implements import in instanceof interface keyof let new null of private protected public readonly return satisfies set static super switch this throw true try type typeof undefined var void while with yield".split(
59
    " ",
60
  ),
61
);
62

63
/** The union of C, C++, C#, Java, Go, Rust, Kotlin and Swift keywords: one list, so `map` is a keyword in C too. */
64
const C_KEYWORDS = new Set(
65
  "abstract as async auto await bool break case catch chan char class const continue default defer delete do double else enum extends extern false final finally float fn for fun func go goto if impl implements import in init int interface is let long loop map match mod mut namespace new nil null object operator override package private protected pub public range register return select self short signed sizeof static struct super switch template this throw trait true try type typedef typename union unsigned use using val var virtual void volatile when where while yield".split(
66
    " ",
67
  ),
68
);
69

70
const PY_OPS = [
71
  "**=",
72
  "//=",
73
  ">>=",
74
  "<<=",
75
  "...",
76
  "->",
77
  ":=",
78
  "**",
79
  "//",
80
  "<<",
81
  ">>",
82
  "<=",
83
  ">=",
84
  "==",
85
  "!=",
86
  "+=",
87
  "-=",
88
  "*=",
89
  "/=",
90
  "%=",
91
  "&=",
92
  "|=",
93
  "^=",
94
  "@=",
95
];
96
const C_OPS = [
97
  ">>>=",
98
  "<<=",
99
  ">>=",
100
  ">>>",
101
  "===",
102
  "!==",
103
  "**=",
104
  "&&=",
105
  "||=",
106
  "??=",
107
  "...",
108
  "->",
109
  "=>",
110
  "::",
111
  "?.",
112
  "??",
113
  "&&",
114
  "||",
115
  "++",
116
  "--",
117
  "<<",
118
  ">>",
119
  "<=",
120
  ">=",
121
  "==",
122
  "!=",
123
  "+=",
124
  "-=",
125
  "*=",
126
  "/=",
127
  "%=",
128
  "&=",
129
  "|=",
130
  "^=",
131
  ":=",
132
  "**",
133
  "<-",
134
];
135
const SINGLE = "+-*/%@&|^~<>()[]{},:;.=!?";
136

137
const NAME_START = /[A-Za-z_$\u0080-￿]/;
138
const NAME_PART = /[A-Za-z0-9_$\u0080-￿]/;
139
const NUMBER =
140
  /^(?:0[xX][0-9a-fA-F_]+|0[oO][0-7_]+|0[bB][01_]+|(?:\d[\d_]*\.?[\d_]*|\.\d[\d_]*)(?:[eE][+-]?\d[\d_]*)?[jJlLfFdDuU]*n?)/;
141
const PY_STRING_START = /^([rRbBuUfF]{0,2})('''|"""|'|")/;
142

143
/** A token as the comparison sees it, and the text it came from, which the "text" comparison uses instead. */
144
export interface Token {
145
  shape: string;
146
  text: string;
147
}
148

149
class Lexer {
150
  readonly out: Token[] = [];
151
  readonly src: string;
152
  readonly lang: Lang;
153
  pos = 0;
154
  constructor(src: string, lang: Lang) {
155
    this.src = src;
156
    this.lang = lang;
157
  }
158

159
  keyword(name: string): boolean {
160
    return (this.lang === "python" ? PY_KEYWORDS : this.lang === "js" ? JS_KEYWORDS : C_KEYWORDS).has(name);
161
  }
162

163
  push(shape: string, text: string) {
164
    this.out.push({ shape, text });
165
  }
166

167
  /** Read tokens until the end, or until `stop` says so at bracket depth zero. Returns the stopping character. */
168
  run(stop?: (ch: string, next: string) => boolean): string | null {
169
    const s = this.src;
170
    let depth = 0;
171
    while (this.pos < s.length) {
172
      const ch = s[this.pos]!;
173
      const next = s[this.pos + 1] ?? "";
174
      if (stop && depth === 0 && stop(ch, next)) return ch;
175
      if (ch === " " || ch === "\t" || ch === "\n" || ch === "\r" || ch === "\f" || ch === "\\") {
176
        this.pos++;
177
        continue;
178
      }
179
      if (this.lang === "python" ? ch === "#" : ch === "/" && next === "/") {
180
        while (this.pos < s.length && s[this.pos] !== "\n") this.pos++;
181
        continue;
182
      }
183
      if (this.lang !== "python" && ch === "/" && next === "*") {
184
        const end = s.indexOf("*/", this.pos + 2);
185
        this.pos = end < 0 ? s.length : end + 2;
186
        continue;
187
      }
188
      if (this.lang === "python") {
189
        const m = PY_STRING_START.exec(s.slice(this.pos, this.pos + 5));
190
        if (m && (m[1] === "" || /^(?:[rRuUbBfF]|[rR][bBfF]|[bBfF][rR])$/.test(m[1]!))) {
191
          this.pyString(m[1]!, m[2]!);
192
          continue;
193
        }
194
      } else if (ch === '"' || ch === "'" || ch === "`") {
195
        this.quoted(ch);
196
        continue;
197
      }
198
      if (NAME_START.test(ch)) {
199
        let end = this.pos + 1;
200
        while (end < s.length && NAME_PART.test(s[end]!)) end++;
201
        const name = s.slice(this.pos, end);
202
        this.push(this.keyword(name) ? name : "ID", name);
203
        this.pos = end;
204
        continue;
205
      }
206
      const num = /[0-9.]/.test(ch) ? NUMBER.exec(s.slice(this.pos)) : null;
207
      if (num && num[0] !== "" && num[0] !== ".") {
208
        this.push("NUM", num[0]);
209
        this.pos += num[0].length;
210
        continue;
211
      }
212
      const ops = this.lang === "python" ? PY_OPS : C_OPS;
213
      const op = ops.find((o) => s.startsWith(o, this.pos)) ?? (SINGLE.includes(ch) ? ch : null);
214
      if (op) {
215
        if ("([{".includes(op)) depth++;
216
        else if (")]}".includes(op)) depth = Math.max(0, depth - 1);
217
        this.push(op, op);
218
        this.pos += op.length;
219
        continue;
220
      }
221
      this.pos++; // a character no language here has a token for: skipped, as tokenize would report and move on
222
    }
223
    return null;
224
  }
225

226
  /** A string in a C-family language: one STR, whatever is inside, template literals included. */
227
  quoted(q: string) {
228
    const s = this.src;
229
    const start = this.pos;
230
    let i = this.pos + 1;
231
    while (i < s.length && s[i] !== q) {
232
      if (s[i] === "\\") i++;
233
      else if (s[i] === "\n" && q !== "`") break;
234
      i++;
235
    }
236
    this.pos = Math.min(i + 1, s.length);
237
    this.push("STR", s.slice(start, this.pos));
238
  }
239

240
  /**
241
   * A Python string. A plain one is one STR. An f-string is what Python 3.12's tokenize makes of it: the literal text
242
   * is dropped, and each replacement field yields `{`, its expression's tokens, a `!` conversion, a `:` and any
243
   * nested fields of its format spec, and `}`.
244
   */
245
  pyString(prefix: string, q: string) {
246
    const s = this.src;
247
    const start = this.pos;
248
    const raw = /[rR]/.test(prefix);
249
    this.pos += prefix.length + q.length;
250
    if (!/[fF]/.test(prefix)) {
251
      while (this.pos < s.length && !s.startsWith(q, this.pos)) {
252
        if (s[this.pos] === "\\") this.pos++;
253
        else if (q.length === 1 && s[this.pos] === "\n") break;
254
        this.pos++;
255
      }
256
      this.pos = Math.min(this.pos + q.length, s.length);
257
      this.push("STR", s.slice(start, this.pos));
258
      return;
259
    }
260
    this.fstringBody(q, raw, false);
261
  }
262

263
  /** The literal part of an f-string, or of a format spec (`inSpec`, which ends at the field's closing brace). */
264
  fstringBody(q: string, raw: boolean, inSpec: boolean) {
265
    const s = this.src;
266
    while (this.pos < s.length) {
267
      if (inSpec && s[this.pos] === "}") return;
268
      if (!inSpec && s.startsWith(q, this.pos)) {
269
        this.pos += q.length;
270
        return;
271
      }
272
      const ch = s[this.pos]!;
273
      if (ch === "\\" && !raw) {
274
        this.pos += 2;
275
        continue;
276
      }
277
      if (ch === "{" && s[this.pos + 1] === "{" && !inSpec) {
278
        this.pos += 2;
279
        continue;
280
      }
281
      if (ch === "}" && s[this.pos + 1] === "}" && !inSpec) {
282
        this.pos += 2;
283
        continue;
284
      }
285
      if (ch === "{") {
286
        this.field(q, raw);
287
        continue;
288
      }
289
      if (q.length === 1 && ch === "\n") return;
290
      this.pos++;
291
    }
292
  }
293

294
  /** One replacement field, from its `{` to its `}`. */
295
  field(q: string, raw: boolean) {
296
    this.push("{", "{");
297
    this.pos++;
298
    const stop = (ch: string, next: string) =>
299
      ch === "}" || ch === ":" || (ch === "!" && next !== "=") || this.src.startsWith(q, this.pos);
300
    let at = this.run(stop);
301
    if (at === "!") {
302
      this.push("!", "!");
303
      this.pos++;
304
      at = this.run(stop);
305
    }
306
    if (at === ":") {
307
      this.push(":", ":");
308
      this.pos++;
309
      this.fstringBody(q, raw, true);
310
    }
311
    if (this.src[this.pos] === "}") {
312
      this.push("}", "}");
313
      this.pos++;
314
    }
315
  }
316
}
317

318
/** Common leading whitespace removed, as textwrap.dedent does, so a method pasted from inside a class still lexes. */
319
export function dedent(src: string): string {
320
  const lines = src.replace(/\r\n?/g, "\n").split("\n");
321
  let common: string | null = null;
322
  for (const line of lines) {
323
    if (!line.trim()) continue;
324
    const lead = /^[ \t]*/.exec(line)![0];
325
    if (common === null) common = lead;
326
    else {
327
      let i = 0;
328
      while (i < common.length && i < lead.length && common[i] === lead[i]) i++;
329
      common = common.slice(0, i);
330
    }
331
  }
332
  const cut = common?.length ?? 0;
333
  return lines.map((l) => (l.trim() ? l.slice(cut) : "")).join("\n");
334
}
335

336
export function tokens(src: string, lang: Lang): Token[] {
337
  const lexer = new Lexer(dedent(src), lang);
338
  lexer.run();
339
  return lexer.out;
340
}
341

342
/**
343
 * The body alone: what follows the signature, and for Python the docstring, which is how cochange.py compares two
344
 * functions. Two copies with different parameter lists (a module-level wrapper and the method it wraps) can have
345
 * nearly identical bodies, and the signature would hide that.
346
 */
347
export function body(ts: Token[], lang: Lang): Token[] {
348
  let depth = 0;
349
  if (lang === "python") {
350
    const def = ts.findIndex((t) => t.text === "def");
351
    if (def < 0) return ts;
352
    for (let i = def + 1; i < ts.length; i++) {
353
      const t = ts[i]!.text;
354
      if (t === "(" || t === "[" || t === "{") depth++;
355
      else if (t === ")" || t === "]" || t === "}") depth--;
356
      else if (t === ":" && depth === 0) {
357
        const rest = ts.slice(i + 1);
358
        return rest.length > 1 && rest[0]!.shape === "STR" ? rest.slice(1) : rest;
359
      }
360
    }
361
    return ts;
362
  }
363
  for (let i = 0; i < ts.length; i++) {
364
    const t = ts[i]!.text;
365
    if (t === "(" || t === "[") depth++;
366
    else if (t === ")" || t === "]") depth--;
367
    else if (t === "{" && depth === 0) {
368
      const rest = ts.slice(i + 1);
369
      return rest.length && rest[rest.length - 1]!.text === "}" ? rest.slice(0, -1) : rest;
370
    }
371
  }
372
  return ts;
373
}
374

375
export function shape(src: string, lang: Lang): string[] {
376
  return tokens(src, lang).map((t) => t.shape);
377
}
378

379
// ---------------------------------------------------------------------------------------------------------------
380
// difflib.SequenceMatcher, without junk: the same matching blocks, so the same ratio, as Python's
381

382
type Block = [number, number, number];
383

384
export class Matcher<T> {
385
  private readonly b2j = new Map<T, number[]>();
386
  readonly a: readonly T[];
387
  readonly b: readonly T[];
388
  constructor(a: readonly T[], b: readonly T[]) {
389
    this.a = a;
390
    this.b = b;
391
    b.forEach((x, j) => {
392
      const at = this.b2j.get(x);
393
      if (at) at.push(j);
394
      else this.b2j.set(x, [j]);
395
    });
396
  }
397

398
  longest(alo: number, ahi: number, blo: number, bhi: number): Block {
399
    let besti = alo;
400
    let bestj = blo;
401
    let bestsize = 0;
402
    let j2len = new Map<number, number>();
403
    for (let i = alo; i < ahi; i++) {
404
      const next = new Map<number, number>();
405
      for (const j of this.b2j.get(this.a[i]!) ?? []) {
406
        if (j < blo) continue;
407
        if (j >= bhi) break;
408
        const k = (j2len.get(j - 1) ?? 0) + 1;
409
        next.set(j, k);
410
        if (k > bestsize) {
411
          besti = i - k + 1;
412
          bestj = j - k + 1;
413
          bestsize = k;
414
        }
415
      }
416
      j2len = next;
417
    }
418
    return [besti, bestj, bestsize];
419
  }
420

421
  blocks(): Block[] {
422
    const queue: [number, number, number, number][] = [[0, this.a.length, 0, this.b.length]];
423
    const found: Block[] = [];
424
    while (queue.length) {
425
      const [alo, ahi, blo, bhi] = queue.pop()!;
426
      const [i, j, k] = this.longest(alo, ahi, blo, bhi);
427
      if (k) {
428
        found.push([i, j, k]);
429
        if (alo < i && blo < j) queue.push([alo, i, blo, j]);
430
        if (i + k < ahi && j + k < bhi) queue.push([i + k, ahi, j + k, bhi]);
431
      }
432
    }
433
    found.sort((x, y) => x[0] - y[0] || x[1] - y[1]);
434
    const merged: Block[] = [];
435
    for (const blk of found) {
436
      const last = merged[merged.length - 1];
437
      if (last && last[0] + last[2] === blk[0] && last[1] + last[2] === blk[1]) last[2] += blk[2];
438
      else merged.push([...blk]);
439
    }
440
    merged.push([this.a.length, this.b.length, 0]);
441
    return merged;
442
  }
443

444
  ratio(): number {
445
    const total = this.a.length + this.b.length;
446
    if (!total) return 1;
447
    return (2 * this.blocks().reduce((n, blk) => n + blk[2], 0)) / total;
448
  }
449

450
  /** difflib's get_opcodes: how to turn a into b, as equal, replace, delete and insert ranges. */
451
  opcodes(): { tag: "equal" | "replace" | "delete" | "insert"; i1: number; i2: number; j1: number; j2: number }[] {
452
    let i = 0;
453
    let j = 0;
454
    const out: { tag: "equal" | "replace" | "delete" | "insert"; i1: number; i2: number; j1: number; j2: number }[] =
455
      [];
456
    for (const [ai, bj, size] of this.blocks()) {
457
      const tag = i < ai && j < bj ? "replace" : i < ai ? "delete" : j < bj ? "insert" : null;
458
      if (tag) out.push({ tag, i1: i, i2: ai, j1: j, j2: bj });
459
      i = ai + size;
460
      j = bj + size;
461
      if (size) out.push({ tag: "equal", i1: ai, i2: i, j1: bj, j2: j });
462
    }
463
    return out;
464
  }
465
}
466

467
export function similarity(a: readonly string[], b: readonly string[]): number {
468
  return new Matcher(a, b).ratio();
469
}
470

471
// ---------------------------------------------------------------------------------------------------------------
472
// History
473

474
export interface Commit {
475
  sha: string;
476
  /** Seconds since the epoch. */
477
  ts: number;
478
  date: string;
479
  subject: string;
480
}
481

482
const MONTHS: Record<string, number> = {
483
  Jan: 0,
484
  Feb: 1,
485
  Mar: 2,
486
  Apr: 3,
487
  May: 4,
488
  Jun: 5,
489
  Jul: 6,
490
  Aug: 7,
491
  Sep: 8,
492
  Oct: 9,
493
  Nov: 10,
494
  Dec: 11,
495
};
496
const ISO = /^(\d{4})-(\d{2})-(\d{2})(?:[T ](\d{2}):(\d{2})(?::(\d{2}))?\s?(Z|[+-]\d{2}:?\d{2})?)?$/;
497
const ONE_LINE =
498
  /^([0-9a-f]{7,40})\s+(\d{9,11}|\d{4}-\d{2}-\d{2}(?:[T ]\d{2}:\d{2}(?::\d{2})?(?:Z|[+-]\d{2}:?\d{2}| [+-]\d{4})?)?)\s+(?:\d{4}-\d{2}-\d{2}\s+)?(.*)$/;
499

500
function offsetSeconds(z: string | undefined): number {
501
  if (!z || z === "Z") return 0;
502
  const m = /^([+-])(\d{2}):?(\d{2})$/.exec(z.trim());
503
  if (!m) return 0;
504
  return (m[1] === "-" ? -1 : 1) * (Number(m[2]) * 3600 + Number(m[3]) * 60);
505
}
506

507
/** An ISO date, a date and time with or without an offset, or seconds since the epoch, as git prints them. */
508
export function parseDate(text: string): number | null {
509
  const t = text.trim();
510
  if (/^\d{9,11}$/.test(t)) return Number(t);
511
  const spaced = /^(\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}) ([+-]\d{4})$/.exec(t); // %ci
512
  const m = ISO.exec(spaced ? `${spaced[1]}${spaced[2]}` : t);
513
  if (!m) return null;
514
  const utc =
515
    Date.UTC(Number(m[1]), Number(m[2]) - 1, Number(m[3]), Number(m[4] ?? 0), Number(m[5] ?? 0), Number(m[6] ?? 0)) /
516
    1000;
517
  return utc - offsetSeconds(m[7]);
518
}
519

520
/** git's default date: "Wed Apr 12 16:53:12 2023 +0200". */
521
function parseDefaultDate(text: string): number | null {
522
  const m = /^\w{3} (\w{3}) +(\d{1,2}) (\d{2}):(\d{2}):(\d{2}) (\d{4}) ([+-]\d{4})$/.exec(text.trim());
523
  if (!m || MONTHS[m[1]!] === undefined) return null;
524
  return (
525
    Date.UTC(Number(m[6]), MONTHS[m[1]!]!, Number(m[2]), Number(m[3]), Number(m[4]), Number(m[5])) / 1000 -
526
    offsetSeconds(m[7])
527
  );
528
}
529

530
function isoDay(ts: number): string {
531
  return new Date(ts * 1000).toISOString().slice(0, 10);
532
}
533

534
/**
535
 * Commits from what `git log` prints, in either of two shapes: one line per commit, `<sha> <date> <subject>`, as
536
 * `--format='%h %cI %s'` gives; or git's default, a `commit <sha>` line, a `Date:` line and an indented subject.
537
 * Everything else, the patches `-L` prints by default included, is ignored.
538
 */
539
export function parseHistory(text: string, input: string): Commit[] {
540
  const lines = text.replace(/\r\n?/g, "\n").split("\n");
541
  const commits: Commit[] = [];
542
  for (let n = 0; n < lines.length; n++) {
543
    const line = lines[n]!;
544
    const block = /^commit ([0-9a-f]{7,40})\b/.exec(line);
545
    if (block) {
546
      let ts: number | null = null;
547
      let subject = "";
548
      let k = n + 1;
549
      for (; k < lines.length && !/^commit [0-9a-f]{7,40}\b/.test(lines[k]!); k++) {
550
        const l = lines[k]!;
551
        const d = /^(?:Commit)?Date:\s+(.*)$/.exec(l);
552
        if (d && ts === null) ts = parseDefaultDate(d[1]!) ?? parseDate(d[1]!);
553
        else if (ts !== null && !subject && /^ {4}\S/.test(l)) subject = l.trim();
554
        if (/^diff --git /.test(l)) break;
555
      }
556
      if (ts === null) throw new InputError(`Commit ${block[1]!.slice(0, 7)} has no Date: line.`, input);
557
      commits.push({ sha: block[1]!, ts, date: isoDay(ts), subject });
558
      continue;
559
    }
560
    const one = ONE_LINE.exec(line.trim());
561
    if (one) {
562
      const ts = parseDate(one[2]!);
563
      if (ts !== null) commits.push({ sha: one[1]!, ts, date: isoDay(ts), subject: one[3]!.trim() });
564
    }
565
  }
566
  const seen = new Set<string>();
567
  return commits.filter((c) => {
568
    const key = c.sha.slice(0, 7);
569
    if (seen.has(key)) return false;
570
    seen.add(key);
571
    return true;
572
  });
573
}
574

575
export interface CoChange {
576
  since: Commit;
577
  sinceFrom: "history" | "input";
578
  together: Commit[];
579
  onlyA: Commit[];
580
  onlyB: Commit[];
581
  ignored: Commit[];
582
  before: number;
583
}
584

585
/**
586
 * Together, only A, only B: counted strictly after `since`, which is the younger copy's first commit unless the
587
 * reader names a commit or a date. A commit in both listings, matched on its first seven hex digits, is together.
588
 */
589
export function countChanges(a: Commit[], b: Commit[], since: string, ignore: string[]): CoChange {
590
  const key = (c: Commit) => c.sha.slice(0, 7).toLowerCase();
591
  const first = (cs: Commit[]) => cs.reduce((x, y) => (y.ts < x.ts ? y : x));
592
  let start: Commit = [first(a), first(b)].reduce((x, y) => (y.ts > x.ts ? y : x));
593
  let sinceFrom: CoChange["sinceFrom"] = "history";
594
  const named = since.trim();
595
  if (named) {
596
    const bySha = [...a, ...b].find(
597
      (c) => /^[0-9a-f]{7,40}$/i.test(named) && c.sha.toLowerCase().startsWith(named.toLowerCase().slice(0, 7)),
598
    );
599
    const ts = bySha?.ts ?? parseDate(named);
600
    if (ts === null || ts === undefined)
601
      throw new InputError(`"${named}" is neither a commit in either history nor a date.`, "since");
602
    start = bySha ?? { sha: "", ts, date: isoDay(ts), subject: "the date you gave" };
603
    sinceFrom = "input";
604
  }
605
  const inA = new Map(a.map((c) => [key(c), c]));
606
  const inB = new Map(b.map((c) => [key(c), c]));
607
  const all = new Map<string, Commit>([...inB, ...inA]);
608
  const words = ignore.map((w) => w.trim().toLowerCase()).filter(Boolean);
609
  const ignored = (c: Commit) =>
610
    words.some(
611
      (w) =>
612
        c.subject.toLowerCase().includes(w) ||
613
        (/^[0-9a-f]{7,40}$/.test(w) && c.sha.toLowerCase().startsWith(w.slice(0, 7))),
614
    );
615
  const out: CoChange = { since: start, sinceFrom, together: [], onlyA: [], onlyB: [], ignored: [], before: 0 };
616
  for (const [k, c] of [...all].sort((x, y) => x[1].ts - y[1].ts)) {
617
    if (c.ts <= start.ts) {
618
      out.before++;
619
      continue;
620
    }
621
    if (ignored(c)) out.ignored.push(c);
622
    else if (inA.has(k) && inB.has(k)) out.together.push(c);
623
    else if (inA.has(k)) out.onlyA.push(c);
624
    else out.onlyB.push(c);
625
  }
626
  return out;
627
}
628

629
/**
630
 * The answer line: the one-sided count, because those are the commits to read. The tool's one rule, stated rather than
631
 * tuned, is that fewer than five changes since both existed is too few to read anything into. It no longer names the
632
 * pair "mostly together" or "drifting apart": the counts do not settle that, and reading the one-sided commits does.
633
 */
634
export function answer(together: number, oneSided: number): { value: string; note: string } {
635
  const total = together + oneSided;
636
  const commits = (n: number) => `${n} commit${n === 1 ? "" : "s"}`;
637
  if (total < 5) {
638
    return {
639
      value: `Too early to tell: ${oneSided} of ${commits(total)} changed only one copy.`,
640
      note: "Fewer than 5 changes since both copies existed. Keep both for now, and add a check that tells you when one changes without the other.",
641
    };
642
  }
643
  if (oneSided === 0)
644
    return {
645
      value: `None of the ${commits(total)} changed only one copy.`,
646
      note: "Every change touched both, so a shared function would have taken the same edits.",
647
    };
648
  return {
649
    value: `${oneSided} of ${commits(total)} changed only one copy. Read ${oneSided === 1 ? "that one" : "those"} first.`,
650
    note: "Each is either a change the other copy missed, or a reason the two differ.",
651
  };
652
}
653

654
// ---------------------------------------------------------------------------------------------------------------
655
// The line diff
656

657
interface DiffRow {
658
  aLine: number | null;
659
  a: string;
660
  bLine: number | null;
661
  b: string;
662
  kind: "names" | "shape" | "only A" | "only B";
663
}
664

665
const MAX_ROWS = 200;
666

667
export function lineDiff(srcA: string, srcB: string, lang: Lang): DiffRow[] {
668
  const linesOf = (src: string) =>
669
    dedent(src)
670
      .split("\n")
671
      .map((text, i) => ({ n: i + 1, text: text.trim() }))
672
      .filter((l) => l.text && !(lang === "python" ? l.text.startsWith("#") : l.text.startsWith("//")));
673
  const la = linesOf(srcA);
674
  const lb = linesOf(srcB);
675
  const m = new Matcher(
676
    la.map((l) => l.text),
677
    lb.map((l) => l.text),
678
  );
679
  const rows: DiffRow[] = [];
680
  const lineShape = (t: string) =>
681
    tokens(t, lang)
682
      .map((x) => x.shape)
683
      .join(" ");
684
  for (const op of m.opcodes()) {
685
    if (op.tag === "equal") continue;
686
    const n = Math.max(op.i2 - op.i1, op.j2 - op.j1);
687
    for (let k = 0; k < n; k++) {
688
      const x = op.i1 + k < op.i2 ? la[op.i1 + k]! : null;
689
      const y = op.j1 + k < op.j2 ? lb[op.j1 + k]! : null;
690
      const kind = x && y ? (lineShape(x.text) === lineShape(y.text) ? "names" : "shape") : x ? "only A" : "only B";
691
      rows.push({ aLine: x?.n ?? null, a: x?.text ?? "", bLine: y?.n ?? null, b: y?.text ?? "", kind });
692
    }
693
  }
694
  return rows;
695
}
696

697
// ---------------------------------------------------------------------------------------------------------------
698

699
/**
700
 * Near-duplicate at 85% alike, names set aside: the threshold cochange.py uses. It was an input; it is fixed now
701
 * because nobody has a better number for their own pair, and a slider invited tuning the answer.
702
 */
703
export const THRESHOLD = 0.85;
704

705
const LANG_NAME: Record<Lang, string> = {
706
  python: "Python",
707
  js: "JavaScript or TypeScript",
708
  c: "the C family (C, C++, C#, Java, Go, Rust, Kotlin, Swift)",
709
};
710

711
/**
712
 * Which lexer to use, read from the code itself. It was a select; the three lexers differ only in comments, strings
713
 * and the keyword list, so a wrong guess between JavaScript and the C family moves the figure by a token or two, and
714
 * Python, the one that differs a lot, is the easiest to recognise.
715
 */
716
export function detectLang(src: string): Lang {
717
  if (/^[ \t]*(?:async[ \t]+)?def[ \t]+\w+[ \t]*\(/m.test(src)) return "python";
718
  if (
719
    /\b(?:fn|func|fun)[ \t]+\w|#include\b|\b(?:public|private|protected)[ \t]+(?:static[ \t]+)?\w+[ \t]+\w+[ \t]*\(/.test(
720
      src,
721
    )
722
  )
723
    return "c";
724
  if (/\bfunction\b|=>|===|!==|\b(?:const|let)[ \t]+\w+[ \t]*=|\bexport[ \t]/.test(src)) return "js";
725
  if (/:[ \t]*(?:#.*)?$/m.test(src) && !/[{};]/.test(src)) return "python";
726
  return "c";
727
}
728

729
const pct = (r: number) => `${Math.floor(r * 1000) / 10}%`;
730
const decimalYear = (ts: number) => {
731
  const d = new Date(ts * 1000);
732
  const y = d.getUTCFullYear();
733
  const start = Date.UTC(y, 0, 1) / 1000;
734
  const end = Date.UTC(y + 1, 0, 1) / 1000;
735
  return Math.round((y + (ts - start) / (end - start)) * 1000) / 1000;
736
};
737
const line = (c: Commit) => `${c.sha.slice(0, 7)} ${c.date} ${c.subject}`.trim();
738

739
export default {
740
  run(input: Input) {
741
    try {
742
      const srcA = input.a ?? "";
743
      const srcB = input.b ?? "";
744
      if (!srcA.trim()) throw new InputError("Paste the first copy.", "a");
745
      if (!srcB.trim()) throw new InputError("Paste the second copy.", "b");
746
      const lang = detectLang(`${srcA}\n${srcB}`);
747
      const ta = body(tokens(srcA, lang), lang);
748
      const tb = body(tokens(srcB, lang), lang);
749
      if (!ta.length) throw new InputError("The first copy has no code in it, only comments or blank lines.", "a");
750
      if (!tb.length) throw new InputError("The second copy has no code in it, only comments or blank lines.", "b");
751
      const shapeR = similarity(
752
        ta.map((t) => t.shape),
753
        tb.map((t) => t.shape),
754
      );
755
      const textR = similarity(
756
        ta.map((t) => t.text),
757
        tb.map((t) => t.text),
758
      );
759
      const rows = lineDiff(srcA, srcB, lang);
760
      const count = (k: DiffRow["kind"]) => rows.filter((r) => r.kind === k).length;
761
      const near = shapeR >= THRESHOLD;
762

763
      const alike: Field = {
764
        label: "Alike, names set aside",
765
        value: pct(shapeR),
766
        note: `every identifier, string and number replaced; ${near ? "at or over" : "under"} the 85% near-duplicate line`,
767
      };
768
      const written: Field = {
769
        label: "Alike, as written",
770
        value: pct(textR),
771
        note: "every name kept",
772
      };
773
      const likeness: Output = {
774
        kind: "fields",
775
        role: "metrics",
776
        fields: [
777
          alike,
778
          written,
779
          ...(rows.length ? [] : [{ label: "Lines that differ", value: "none", note: "line for line the same" }]),
780
        ],
781
      };
782

783
      // The current code, above the history: it is what a merge has to reconcile.
784
      const diff: Output[] = [];
785
      if (rows.length) {
786
        const shown = rows.slice(0, MAX_ROWS);
787
        const does = count("shape") + count("only A") + count("only B");
788
        diff.push({
789
          kind: "table",
790
          caption: `Current differences: ${rows.length} line${rows.length === 1 ? "" : "s"}, ${does} in what the code does and ${count("names")} only in names, strings or numbers${rows.length > MAX_ROWS ? `. The first ${MAX_ROWS} are shown` : ""}`,
791
          columns: [
792
            { label: "A", align: "end", mono: true, wrap: "none" },
793
            { label: "Copy A", mono: true, wrap: "prose" },
794
            { label: "B", align: "end", mono: true, wrap: "none" },
795
            { label: "Copy B", mono: true, wrap: "prose" },
796
            { label: "Differs in", wrap: "none" },
797
          ],
798
          rows: shown.map((r): Cell[] => [
799
            r.aLine === null ? "" : String(r.aLine),
800
            { text: r.a, mono: true },
801
            r.bLine === null ? "" : String(r.bLine),
802
            { text: r.b, mono: true },
803
            r.kind === "names"
804
              ? { text: "names or literals", tone: "muted" }
805
              : r.kind === "shape"
806
                ? "what it does"
807
                : r.kind,
808
          ]),
809
        });
810
      }
811

812
      const how: Field[] = [
813
        {
814
          label: "Read as",
815
          value: LANG_NAME[lang],
816
          mono: false,
817
          note: "from the code itself: it decides what counts as a keyword, a comment and a string",
818
        },
819
        {
820
          label: "Compared",
821
          value: "The bodies only, leaving out each signature and, in Python, the docstring.",
822
          mono: false,
823
          note: "A wrapper and the method it wraps can share a body under different parameter lists. The line diff still shows the signatures.",
824
        },
825
        {
826
          label: "Near-duplicate at",
827
          value: "85% alike, names set aside",
828
          mono: false,
829
          note: "the threshold the companion cochange.py uses",
830
        },
831
      ];
832

833
      const hasA = (input.historya ?? "").trim();
834
      const hasB = (input.historyb ?? "").trim();
835
      const parts: Output[] = [];
836
      if (hasA || hasB) {
837
        if (!hasA) throw new InputError("Paste the first copy's history too: a pair needs both.", "historya");
838
        if (!hasB) throw new InputError("Paste the second copy's history too: a pair needs both.", "historyb");
839
        const ha = parseHistory(input.historya, "historya");
840
        const hb = parseHistory(input.historyb, "historyb");
841
        const expected =
842
          "Expected lines like \"f1157db 2023-03-20T11:30:11Z Use standard logging style\", from git log --no-patch --format='%h %cI %s' -L <start>,<end>:<file>.";
843
        const none = (text: string) =>
844
          /^[0-9a-f]{7,40} \S/m.test(text)
845
            ? `These commits have no dates, and counting from when both copies existed needs one. ${expected}`
846
            : `No commits found. ${expected}`;
847
        if (!ha.length) throw new InputError(none(input.historya), "historya");
848
        if (!hb.length) throw new InputError(none(input.historyb), "historyb");
849
        const c = countChanges(ha, hb, input.since ?? "", (input.ignore ?? "").split(","));
850
        const oneSided = c.onlyA.length + c.onlyB.length;
851
        const v = answer(c.together.length, oneSided);
852
        const since =
853
          c.sinceFrom === "input"
854
            ? `Since ${c.since.sha ? c.since.sha.slice(0, 7) : c.since.date}`
855
            : "Since both copies existed";
856
        parts.push({
857
          kind: "fields",
858
          role: "answer",
859
          fields: [{ label: since, value: v.value, note: v.note, mono: false }],
860
        });
861

862
        const counted = [
863
          ...c.together.map((x) => ["both", x] as const),
864
          ...c.onlyA.map((x) => ["only A", x] as const),
865
          ...c.onlyB.map((x) => ["only B", x] as const),
866
        ].sort((x, y) => x[1].ts - y[1].ts);
867
        const lonely = counted
868
          .filter(([side]) => side !== "both")
869
          .map(([side, x]): [string, Commit] => [side === "only A" ? "A" : "B", x])
870
          .reverse();
871
        if (counted.length) {
872
          // Bars rather than a two-set Venn: a one-commit region is a sliver nobody can read, and a bar labels exactly.
873
          parts.push({
874
            kind: "series",
875
            chart: {
876
              xLabel: "Changed",
877
              yLabel: "Commits",
878
              orientation: "horizontal",
879
              x: ["Both", "A only", "B only"],
880
              series: [
881
                {
882
                  label: "Commits",
883
                  shape: "bar",
884
                  unit: "commits",
885
                  points: [c.together.length, c.onlyA.length, c.onlyB.length],
886
                },
887
              ],
888
            },
889
          });
890
        }
891
        if (lonely.length) {
892
          parts.push({
893
            kind: "table",
894
            role: "actions",
895
            caption: "Changed only one copy, newest first",
896
            columns: [
897
              { label: "Copy", wrap: "none" },
898
              { label: "Commit", mono: true, wrap: "none", rowHeader: true },
899
              { label: "Date", wrap: "none" },
900
              { label: "Subject", wrap: "prose" },
901
            ],
902
            rows: lonely.map(([side, x]): Cell[] => [side, { text: x.sha.slice(0, 7), mono: true }, x.date, x.subject]),
903
          });
904
        }
905
        parts.push(...diff, likeness);
906
        if (counted.length) {
907
          const run = { both: 0, "only A": 0, "only B": 0 };
908
          const pts: Record<keyof typeof run, number[]> = { both: [], "only A": [], "only B": [] };
909
          for (const [side] of counted) {
910
            run[side]++;
911
            for (const k of Object.keys(run) as (keyof typeof run)[]) pts[k].push(run[k]);
912
          }
913
          const series: Series[] = [
914
            { label: "Changed both", points: pts.both, shape: "step", unit: "commits" },
915
            { label: "Changed only A", points: pts["only A"], shape: "step", unit: "commits" },
916
            { label: "Changed only B", points: pts["only B"], shape: "step", unit: "commits" },
917
          ];
918
          parts.push({
919
            kind: "series",
920
            chart: {
921
              id: "drift",
922
              xLabel: "Year",
923
              yLabel: "Commits so far",
924
              x: counted.map(([, x]) => decimalYear(x.ts)),
925
              series,
926
              readout: { titles: counted.map(([side, x]) => `${line(x)} (${side})`), highlightTable: true },
927
            },
928
          });
929
          parts.push({
930
            kind: "table",
931
            caption: "Every counted commit, oldest first",
932
            columns: [
933
              { label: "Commit", mono: true, wrap: "none", rowHeader: true },
934
              { label: "Date", wrap: "none" },
935
              { label: "Changed", wrap: "none" },
936
              { label: "Subject", wrap: "prose" },
937
            ],
938
            rows: counted.map(([side, x]): Cell[] => [
939
              { text: x.sha.slice(0, 7), mono: true },
940
              x.date,
941
              side === "both" ? { text: "both", tone: "muted" } : side,
942
              x.subject,
943
            ]),
944
            link: { chart: "drift", keys: counted.map(([, x]) => decimalYear(x.ts)) },
945
          });
946
        }
947
        parts.push({
948
          kind: "fields",
949
          role: "method",
950
          fields: [
951
            {
952
              label: "Counted from",
953
              value: line(c.since) || c.since.date,
954
              note:
955
                c.sinceFrom === "input"
956
                  ? "the commit or date you gave"
957
                  : "the younger copy's first commit in its history. If that is earlier than the copy itself, name the commit that made it in Count from.",
958
            },
959
            {
960
              label: "Left out",
961
              value: `${c.before} at or before the count starts, ${c.ignored.length} ignored`,
962
              mono: false,
963
              note: "At or before: in either history up to the commit counted from, when there was one copy or the traced lines were other code. Ignored: by the words or commits you listed.",
964
            },
965
            ...how,
966
          ],
967
        });
968
      } else {
969
        // With no history, the code is all there is, so the diff comes straight after the answer.
970
        parts.push({
971
          kind: "fields",
972
          role: "answer",
973
          fields: [
974
            {
975
              label: near ? "Near-duplicates" : "Two different functions",
976
              value: `${pct(shapeR)} alike once names, strings and numbers are set aside, ${near ? "at or over" : "under"} the 85% line.`,
977
              mono: false,
978
              note: near
979
                ? "Whether to merge them depends on whether they change together. Paste each copy's git log to find out."
980
                : "Different enough that a change to one is unlikely to belong in the other.",
981
            },
982
          ],
983
        });
984
        alike.note = "every identifier, string and number replaced";
985
        parts.push(...diff, likeness, { kind: "fields", role: "method", fields: how });
986
      }
987
      return { kind: "group", parts };
988
    } catch (error) {
989
      if (error instanceof InputError) return { kind: "error", message: error.message, input: error.input };
990
      throw error;
991
    }
992
  },
993
} satisfies Tool<Input>;