CodeEraser

The mathematics

Every verdict is integer or exact-rational arithmetic over measured facts, and every rule is cited to the line that implements it.

Each entry below gives the rule, what it decides, the guarantee behind it where one is written down and the constants in play, and links to its derivation on the how pages and to the methodology booklet that cites the implementing line.

Duplication

01Winnowing

Any common run of at least t normalized tokens yields at least one shared fingerprint: the Schleimer et al. SIGMOD'03 no-miss bound, held as a correctness contract.

t = window + kgram - 1 = 26 + 25 - 1 = 50 tokens

Any common substring of at least t normalized tokens contains t - k + 1 = w consecutive k-grams (one complete window) and window selection depends only on that window's contents, so both copies select the same minimum.

Derivation: how it works · 01 · Source: booklet 01

02Tree edit distance

Zhang-Shasha edit distance is always integral, so a near-miss clone at TSED ≥ 0.85 is decided by exact cross-multiplication.

TSED(a, b) = (max(n1, n2) - ted(a, b)) / max(n1, n2)
clone      ⇔ TSED >= 0.85
cloneDecidesWith (num, den) t n1 n2 = (mx - t) * den >= num * mx  where mx = max n1 n2

ted is Zhang-Shasha with unit costs (delete = insert = 1, relabel = 0 on matching kind codes, else 1) and is always integral, so the comparison is an exact cross-multiplication and the boundary is decidable in both directions: at max = 100, ted 15 is a clone and ted 16 is not.

Derivation: how it works · 02 · Source: booklet 02

03Jaccard over shingles

Two documentation blocks are duplicates at Jaccard ≥ 0.80 over five-word shingles, or on a verbatim run of 50 words; MinHash/LSH only proposes the pairs.

dupDecidesWith num den inter union  =  inter * den >= num * union

dupVerdictWith (num, den, vfloor) inter union run
  =  dupDecidesWith num den inter union  ||  run >= vfloor

MinHash/LSH is only a coarse filter and is RNG-free: the permutation index is the salt.

Derivation: how it works · 03 · Source: booklet 03

18Clone merge

Where the members of a clone group differ becomes a hole, and each distinct value vector a parameter: at most six, and only when a line is saved.

align  : T1/T2 isomorphic, holes = differing leaves; T3 the tree-edit mapping narrowed top-down, relabels and unequal gaps are holes
params : one per distinct value vector; feasible iff every hole is an expression or a name, params ≤ 6 and savings > 0

The operation is anti-unification: the least general skeleton every member is an instance of, each member recovered by filling the skeleton's holes with its own values.

Derivation: how it works · 18 · Source: booklet 18

Structure

04Tsallis-2 and χ²

Directory diversity and layout divergence in exact rationals: the log-free members of the entropy and KL families, so every boundary is decidable.

tsallis2 cs     = 1 - Σ (c/N)^2            -- and = 0 when N == 0
tsallis2Norm cs = tsallis2 cs / (1 - 1/n)  -- n = nonzero bins, n > 1
chi2 pairs      = Σ_{r > 0} (p - q)^2 / q  -- p = o/Σo, q = r/Σr
perMille r      = floor (r * 1000)

Shannon entropy and KL divergence need logarithms (irrational, therefore not exactly decidable), so the family publishes the rational-closed members of the same families instead: Tsallis-2 diversity and the χ² f-divergence, all over Data.Ratio.

A χ² with observed mass on a zero-reference bin returns Nothing, a refusal rather than a zero: the report names those directories.

Derivation: how it works · 04 · Source: booklet 04

04Newman modularity

Each directory's modularity contribution as a share of the most it could earn: 1000‰ when it never reaches out, 0 at the null model's expectation.

rho = q / qMax = (e*m − o*i) / (mu*(m − mu))

With e internal edges, out-mass o, in-mass i, incident mass mu = e + crossOut + crossIn and m edges in the tree, Newman's contribution of a directory is q = e/m − o*i/m^2, and the most a directory of mass mu could earn — every incident edge internal — is qMax = mu(m−mu)/m^2.

Derivation: how it works · 04 · Source: booklet 04

19Layers and cuts

Directories ordered into layers once the cheapest arcs are cut out of their cycles, with each directory's instability in integer per-mille.

cuts   : per SCC, a subset programme when it has ≤ 14 directories (exact 1), else Eades–Lin–Smyth + redundancy pass (exact 0)
layers : level(d) = 0 when nothing leaves d, else 1 + max level of what d points at, the cut arcs removed
metrics: fanIn, fanOut, instability = ⌊1000 · out ÷ (in + out)⌋, −1 when nothing touches the directory

The cheapest set of arcs whose removal leaves the graph acyclic is found one component at a time: an arc between two components lies on no cycle, so the minimum over the graph is the union of the components' minima.

Derivation: how it works · 19 · Source: booklet 19

Score and trend

05The score

The axes fold into one 0–1000 score under a convex size penalty; each file's ceiling only shrinks, and growth past max(+2 %, +10) fails the gate.

raw     = sum_i (w_i * p_i * violCost)
wTotal  = sum_i w_i                            -- derived, never a literal
score   = max 0 (scoreScale - raw `div` (violCostNeutral * wTotal))

p(x) = 0                              if x <= S
     = pMax                           if H <= S          -- degenerate fallback
     = pMax * ((x - S) / (H - S))^2   if S < x <= H
     = pMax * (1 + 2*(x - H)/(H - S)) if x > H           -- C¹ linear arm

Axis 0 is the only axis that is not a count: a convex penalty on file size, exact Rational, monotone past the hard line.

Derivation: how it works · 05 · Source: booklet 05

05The ratchet

Folds seven axes into one 0–1000 score and gates it against a banked baseline that is only allowed to tighten.

tolerated(c) = max (c * tolNum `div` tolDen) (c + tolAbs)

added   = current \ baseline        -- non-empty => fail
removed = baseline \ current        -- informational; drives the shrink

The fail bit is a disjunction of six named conditions: ratchet_over, discrete_added, floor, dedup_budget, knobs_digest, rows_dropped.

Derivation: how it works · 05 · Source: booklet 05

05Cognitive complexity

SonarSource's cognitive complexity with the recursion increment of S3776 Appendix B1, which SonarSource's own analysers leave out: the core finds the call cycles and every member pays once.

+1 for each method in a recursion cycle, whether direct or indirect

Derivation: how it works · 05 · Source: booklet 05

08Split ROI

The penalty curve is convex with p(0) = 0, hence superadditive: a seam's benefit is never negative, and it is priced against what the cut costs.

benefitMilli(u) = max 0 (floor (1000 * (p(total) - p(end_u) - p(total - end_u))))

costMilli(u)    = crossRefs(u)      * roiRefMilli
                + cutClones(end_u)  * roiCloneMilli
                + crossChurn(u)     * roiChurnMilli
                + roiPhiMilli

viable          ⇔ b >= c            -- ROI >= 1, evaluated without division

Benefit is the graded-zone penalty a split gives back, computed on the same convex curve the verdict family judges with, imported rather than re-derived; because p is convex with p(0) = 0 it is superadditive, so the bracket is non-negative.

Derivation: how it works · 08 · Source: booklet 08

10Theil-Sen slope

The trend is the median of pairwise slopes: one wild commit cannot move it past its neighbours.

x_i   = ts_i % 86400                 -- seconds to days, exact ratio
y_i   = (score_i * 1000000) % scale_i

slope = median{ (y_j - y_i) / (x_j - x_i) : x_i ≠ x_j }   -- Theil-Sen

slope < -band  → 2  (degrading)
slope >  band  → 0  (improving)
otherwise      → 1  (flat)        where band = floorMicro

The slope is the median of pairwise slopes (trend/2): one wild point, a broken commit that still measured, drags a least-squares mean anywhere and cannot move the median past its neighbors.

Derivation: how it works · 10 · Source: booklet 10

Graph and logic

06Liveness

A file nothing live reaches is dead; cycles are found once, by Tarjan's strongly connected components, and reported, never judged.

arcs  = { (s,d) | [s,d,kind,rung] ∈ edges,  rung <= minRung,  kind ∉ inert }
reach = ⋃ { reachable(G, s) | s ∈ entries(entryMask, flags) }

public     = testBit flags 0
referenced = indeg >= 1 over kept arcs
judged     = i ∉ reach
code       = 1 + public + 2*referenced    -- the lookup table is the authority

Cycles are reported, never judged; a cyclic island with no entry seed is dead by reachability alone.

Derivation: how it works · 06 · Source: booklet 06

17Reachability and liveness

Reachability over each function's control-flow graph, and backward liveness over its variables.

kind 0 : unreachable  = no path from the entry, one finding per maximal run of seqs
kind 1 : dead_store   = a write no path reads before the next write or the exit (backward liveness)
kind 2 : unused_local = no read · kind 3 : unused_param = no read (advice, never judged)

Live-in is solved to a fixpoint of in = transfer(∪ in of successors) over the whole graph.

Derivation: how it works · 17 · Source: booklet 17

16Stratified Datalog

Datalog evaluated semi-naively, one stratum at a time, over the index's own facts; every answer carries the derivation that produced it.

dead(F) :- file(F), not reach(F).
strata : a head sits above every negated or aggregated body predicate; a negative edge inside an SCC is a program error
eval   : semi-naive per stratum over lazy bitmask indexes; the first derivation of a tuple is its provenance

Set semantics, least model.

Derivation: how it works · 16 · Source: booklet 16

15Integer BM25 and PPMI

Integer BM25 with k1 = 6/5 and b = 3/4 ranks the units most like one unit; in-repository PPMI may widen a query, as advice only.

score  = Σ w · idf · 22·tf·avg / (10·tf·avg + 3·avg + 9·len)   (k1 = 6/5, b = 3/4; integer fixed point)
widen  = top-m PPMI neighbours at ≤ ½ weight    (opt-in view; never evidence)
role   ⇔ (N ≥ 1 ∧ C ≥ 1) ∨ (N ≥ 2 ∧ shapeEqual)  (judged in Haskell over similar/1; advisory only)
PPMI(a, b) = max(0, log2(n_ab · N / (n_a · n_b)))

Rust sends the query bag and one nine-integer row per candidate; Haskell orders them as exact rationals and applies the role conjunction; names, words and paths never cross the wire.

Derivation: how it works · 15 · Source: booklet 15