CodeEraser
Method

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: the rule, what it decides, its guarantee where one is written down, the constants in play, and links to its derivation and to the booklet citing the implementing line.

Duplication

01Winnowing

Decides which normalized-token runs two files share, as fingerprints chosen by each window's minimum.

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

No-miss bound (Schleimer et al., SIGMOD'03, held as a contract): a common run of at least t tokens holds t - k + 1 = w consecutive k-grams, one whole window, whose minimum both copies select.

Derivation · booklet 01

02Tree edit distance

Decides near-miss clones: two trees are clones at TSED ≥ 0.85.

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

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

Derivation · 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.

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 only proposes the pairs and is RNG-free (the permutation index is the salt); the verdict is the exact integer test.

Derivation · booklet 03

18Clone merge

Where a clone group's members differ becomes a hole, 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

Anti-unification: the least general skeleton every member instantiates, each member recovered by filling the holes with its own values.

Derivation · booklet 18

Structure

04Tsallis-2 and χ²

Directory diversity and layout divergence, in exact rationals.

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 need logarithms (irrational, not exactly decidable), so the family uses their log-free members, Tsallis-2 and the χ² f-divergence, over Data.Ratio; a χ² with mass on a zero-reference bin returns Nothing, a refusal naming the directories, not a zero.

Derivation · booklet 04

04Newman modularity

Each directory's modularity as a share of its maximum: 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, Newman's contribution is q = e/m − o*i/m^2 and its maximum, every incident edge internal, qMax = mu(m−mu)/m^2.

Derivation · booklet 04

19Layers and cuts

Orders directories into layers once the cheapest arcs are cut from their cycles, with 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

Cuts are found per strongly connected component: an arc between components lies on no cycle, so the graph's minimum is the union of the components' minima.

Derivation · booklet 19

Score and trend

05The score

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

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          -- S read as min S H
     = 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 alone is not a count: a convex size penalty in exact Rational, monotone past the hard line.

Derivation · booklet 05

05The ratchet

Gates the score of seven axes against a banked baseline that may only tighten.

tolerated(c) = max (c * tolNum `div` tolDen) (c + tolAbs)   -- tolAbsCoc on a complexity row

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 · booklet 05

05Cognitive complexity

Cognitive complexity with the recursion increment of S3776 Appendix B1, which SonarSource's own analysers omit: the core finds call cycles and each member pays once.

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

Derivation · booklet 05

08Split ROI

Prices a split seam: the size penalty it gives back 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

p is convex with p(0) = 0, hence superadditive, so the benefit, computed on the verdict family's same curve (imported, not re-derived), is never negative.

Derivation · booklet 08

10Theil-Sen slope

The trend is the median of pairwise slopes (trend/2).

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

One wild point, a broken commit that still measured, drags a least-squares mean anywhere but cannot move the median past its neighbours.

Derivation · booklet 10

Graph and logic

06Liveness

A file nothing live reaches is dead; cycles come from Kosaraju's strongly connected components, found once.

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 · booklet 06

17Reachability and liveness

Reachability over each function's control-flow graph, 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 · booklet 17

16Stratified Datalog

Semi-naive, stratum-by-stratum Datalog over the index's own facts; every answer carries its derivation.

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 · booklet 16

15Integer BM25 and PPMI

Integer BM25 (k1 = 6/5, 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)))

Haskell orders each candidate's nine-integer row as exact rationals and applies the role conjunction; on similar/1 and rank/1 only hashes and counts cross — the unit texts the bags are built from go to the core once, over the local pipe, in bags/1.

Derivation · booklet 15