Duplicated Code

import type { ClassDecl, Expr, Stmt } from "./program";import type { Tracer } from "../trace";import type { SmellDetector } from "./detector";/** Which clones count: type-1 (`exact`, only ids differ) or type-2 (`renamed`, local names may differ consistently too). */export type CloneVariant = "exact" | "renamed";/** A run of top-level statements of one method, from `firstId` through `lastId` inclusive. */export interface RunRef {  readonly method: string;  readonly firstId: string;  readonly lastId: string;}/** Two runs of the same length that match statement by statement; `a` is the one found first in declaration order. */export interface CloneRun {  readonly a: RunRef;  readonly b: RunRef;  /** Top-level statements in each run. */  readonly length: number;}export interface CloneReport {  readonly className: string;  readonly minLength: number;  readonly variant: CloneVariant;  readonly clones: readonly CloneRun[];  /** Distinct top-level statements on the `b` side of a clone: the copies that a call could replace. */  readonly duplicated: number;  /** At least one clone. */  readonly smelly: boolean;}/** A top-level method body as a sequence of statements, with the method that owns it. */interface Sequence {  readonly method: string;  readonly body: readonly Stmt[];}/** * A clone detector over the top-level statement sequences of a class's * methods, in Roy and Cordy's taxonomy: a type-1 clone (`exact`) is a run * of statements equal in everything but whitespace and comments, which * here means everything but statement ids; a type-2 clone (`renamed`) * allows the local names (parameters, lets, loop variables) to differ, * as long as the renaming is consistent across the whole run, a * bijection between the two runs' names. Members, method names, literals * and operators never rename: `account.frozen` and `target.frozen` are * the same statement renamed, `this.log` and `this.audit` are not. * Type-3 (gapped) and type-4 (semantic) clones are out of scope. * * Only the top-level bodies of the methods are sequences: a statement * inside a block is compared as part of the statement that opens the * block, never as the start of a run of its own. Every pair of sequences * `p <= q` is tried at every pair of start positions not already inside * an earlier match, the match extends while the next statements are * equal (on a self pair, only while the two runs stay disjoint), and a * match at least `minLength` long is a clone. * * The statics `fingerprint`, `renaming`, and `sameRun` are shared with * `ReplaceRunWithCall`, which needs the same equality and the same * bijection to map a helper's parameters onto a copy. * * Time: O(s² · l) over s statements across the sequences and l the * longest match. Space: O(s) for the fingerprints and covered pairs. */export class CloneDetector implements SmellDetector<ClassDecl, CloneReport> {  constructor(    readonly minLength = 3,    readonly variant: CloneVariant = "exact",    private readonly tracer?: Tracer,  ) {}  /**   * A statement's shape as a string: the statement serialized with every   * id blanked (nested blocks included). In `renamed` every local name   * becomes `$k`, numbered by first appearance in the statement, so two   * statements that differ only in local names print the same.   */  static fingerprint(stmt: Stmt, variant: CloneVariant): string {    const names: string[] = [];    return JSON.stringify(CloneDetector.normalize(stmt, variant === "renamed" ? names : null));  }  /**   * The renaming that turns run `a` into run `b`: the local names of each   * statement, in first-appearance order, zipped across the whole run.   * Null when the runs differ in length, when a statement pair has a   * different number of names, or when the pairs are not one-to-one in   * both directions (`a` named twice for one `b` name, or the reverse).   */  static renaming(a: readonly Stmt[], b: readonly Stmt[]): ReadonlyMap<string, string> | null {    if (a.length !== b.length) return null;    const forward = new Map<string, string>();    const backward = new Map<string, string>();    for (const [i, stmt] of a.entries()) {      const left = CloneDetector.localNames(stmt);      const right = CloneDetector.localNames(b[i]!);      if (left.length !== right.length) return null;      for (const [k, name] of left.entries()) {        const other = right[k]!;        if ((forward.has(name) && forward.get(name) !== other) || (backward.has(other) && backward.get(other) !== name)) return null;        forward.set(name, other);        backward.set(other, name);      }    }    return forward;  }  /**   * Whether two runs are the same clone: equal in length, fingerprints   * equal statement by statement, and in `renamed` the zipped local   * names of the whole run form a bijection. The bijection is what tells   * `x = a; y = a` from `x = a; y = b`: the statements print alike one at   * a time, but `a` cannot stand for both `a` and `b`.   */  static sameRun(a: readonly Stmt[], b: readonly Stmt[], variant: CloneVariant): boolean {    if (a.length !== b.length) return false;    for (const [i, stmt] of a.entries()) {      if (CloneDetector.fingerprint(stmt, variant) !== CloneDetector.fingerprint(b[i]!, variant)) return false;    }    return variant === "exact" || CloneDetector.renaming(a, b) !== null;  }  analyze(cls: ClassDecl): CloneReport {    const sequences: Sequence[] = cls.methods.map((method) => ({ method: method.name, body: method.body }));    sequences.forEach((sequence, index) => {      // ▸ a method's body becomes a sequence of top-level statements      this.tracer?.emit("method", { name: sequence.method, index, count: sequences.length, statements: sequence.body.length });    });    const clones: CloneRun[] = [];    const covered = new Set<string>();    const bIds = new Set<string>();    for (let p = 0; p < sequences.length; p++) {      for (let q = p; q < sequences.length; q++) {        const a = sequences[p]!;        const b = sequences[q]!;        for (let i = 0; i < a.body.length; i++) {          for (let j = p === q ? i + 1 : 0; j < b.body.length; j++) {            if (covered.has(CloneDetector.key(p, i, q, j))) continue;            const length = this.extend(a, b, i, j, p === q);            for (let k = 0; k < length; k++) covered.add(CloneDetector.key(p, i + k, q, j + k));            if (length < this.minLength) continue;            const clone: CloneRun = {              a: { method: a.method, firstId: a.body[i]!.id, lastId: a.body[i + length - 1]!.id },              b: { method: b.method, firstId: b.body[j]!.id, lastId: b.body[j + length - 1]!.id },              length,            };            clones.push(clone);            for (let k = 0; k < length; k++) bIds.add(b.body[j + k]!.id);            // ▸ a run at least min long is a clone: the first copy and the duplicate            this.tracer?.emit("clone", { aMethod: clone.a.method, aFirst: clone.a.firstId, aLast: clone.a.lastId, bMethod: clone.b.method, bFirst: clone.b.firstId, bLast: clone.b.lastId, length, count: clones.length });          }        }      }    }    const duplicated = bIds.size;    const smelly = clones.length > 0;    // ▸ the clones found and the duplicated statements a call could replace    this.tracer?.emit("verdict", { className: cls.name, clones: clones.length, duplicated, minLength: this.minLength, variant: this.variant, smelly });    return { className: cls.name, minLength: this.minLength, variant: this.variant, clones, duplicated, smelly };  }  /** The longest match starting at `a[i]` and `b[j]`, one `match` per statement it grows by; on a self pair the runs must stay disjoint. */  private extend(a: Sequence, b: Sequence, i: number, j: number, self: boolean): number {    let length = 0;    while (i + length < a.body.length && j + length < b.body.length && (!self || i + length < j)) {      if (!CloneDetector.sameRun(a.body.slice(i, i + length + 1), b.body.slice(j, j + length + 1), this.variant)) break;      length++;      // ▸ the next statements of two runs are the same, so the run grows by one      this.tracer?.emit("match", { aMethod: a.method, aId: a.body[i + length - 1]!.id, bMethod: b.method, bId: b.body[j + length - 1]!.id, length });    }    return length;  }  /** One start pair: sequence `p` at `i` against sequence `q` at `j`. */  private static key(p: number, i: number, q: number, j: number): string {    return `${p}:${i}:${q}:${j}`;  }  /** The local names of a statement in first-appearance order: the order `fingerprint` numbers them in. */  private static localNames(stmt: Stmt): readonly string[] {    const names: string[] = [];    CloneDetector.normalize(stmt, names);    return names;  }  /** The statement with ids blanked and, when `names` is given, every local name replaced by its `$k` index in `names`. */  private static normalize(stmt: Stmt, names: string[] | null): unknown {    const local = (name: string): string => {      if (!names) return name;      let k = names.indexOf(name);      if (k < 0) {        k = names.length;        names.push(name);      }      return `$${k}`;    };    const expr = (e: Expr): unknown => CloneDetector.normalizeExpr(e, local);    const block = (body: readonly Stmt[]): unknown[] => body.map((s) => CloneDetector.normalize(s, names));    switch (stmt.kind) {      case "let":        return { kind: stmt.kind, name: local(stmt.name), type: stmt.type, init: stmt.init ? expr(stmt.init) : null };      case "assign":        return { kind: stmt.kind, target: expr(stmt.target), value: expr(stmt.value) };      case "expr":        return { kind: stmt.kind, expr: expr(stmt.expr) };      case "if":        return { kind: stmt.kind, test: expr(stmt.test), then: block(stmt.then), else: stmt.else ? block(stmt.else) : null };      case "for-each":        return { kind: stmt.kind, variable: local(stmt.variable), variableType: stmt.variableType, iterable: expr(stmt.iterable), body: block(stmt.body) };      case "while":        return { kind: stmt.kind, test: expr(stmt.test), body: block(stmt.body) };      case "return":        return { kind: stmt.kind, value: stmt.value ? expr(stmt.value) : null };      case "throw":        return { kind: stmt.kind, message: stmt.message };    }  }  private static normalizeExpr(e: Expr, local: (name: string) => string): unknown {    switch (e.kind) {      case "name":        return { kind: e.kind, name: local(e.name) };      case "field":        return { kind: e.kind, target: CloneDetector.normalizeExpr(e.target, local), name: e.name };      case "call":        return { kind: e.kind, target: CloneDetector.normalizeExpr(e.target, local), method: e.method, args: e.args.map((a) => CloneDetector.normalizeExpr(a, local)) };      case "new":        return { kind: e.kind, className: e.className, args: e.args.map((a) => CloneDetector.normalizeExpr(a, local)) };      case "unary":        return { kind: e.kind, op: e.op, operand: CloneDetector.normalizeExpr(e.operand, local) };      case "binary":        return { kind: e.kind, op: e.op, left: CloneDetector.normalizeExpr(e.left, local), right: CloneDetector.normalizeExpr(e.right, local) };      default:        return e;    }  }}