`nx_dupfunc.nx` source

↩ module page · 373 lines · 16319 B
1// nx_dupfunc.nx -- WHICH FUNCTION BODIES ARE WRITTEN MORE THAN ONCE?
2//
3// ===== WHY THIS EXISTS ============================================
4//
5// The tree already has nx_dup_source_check, and it is a good tool, but it
6// answers a different question: it detects the SAME FILE existing in two
7// source trees.  It is file-level and cross-tree by construction, so it
8// cannot see two files in the same directory that happen to contain the same
9// function written twice.
10//
11// That gap is not theoretical.  Building nx_gatescan and nx_gatequality I
12// duplicated NINE functions between them -- the tree walk, file read, path
13// join, the file-type predicates, the attribution rule -- while holding two
14// tools designed to find exactly this class of problem.  Nothing in the
15// ecosystem could have told me.  This organ closes that.
16//
17// ===== THE DESIGN DECISION THAT MAKES IT WORK =====================
18//
19// ★NAMES ARE IGNORED.  My nine duplicates were called gs_len and gq_len,
20// gs_walk and gq_walk -- identical bodies behind different prefixes, which is
21// what copying into a new file naturally produces.  A detector keyed on names
22// would have found none of them.  So a function is reduced to its BODY, and
23// the body alone decides identity.
24//
25// Normalisation before comparison, each for a reason:
26//   - comments stripped     : a copied function usually keeps the code and
27//                             rewrites the comment, or vice versa
28//   - whitespace collapsed  : re-indentation is not a difference
29//   - the signature line dropped: that is where the name lives
30//
31// ===== RANKED BY COST, NOT BY COUNT ===============================
32//
33// Two copies of a 60-line walk are a different problem from two copies of a
34// one-line helper.  Severity is therefore (copies - 1) x body size: what you
35// would actually save, and what is actually at risk of drifting apart.
36//
37// ⚠WHAT IT DOES NOT MEAN.  Identical bodies are not automatically a defect.
38// This tree deliberately keeps independent re-derivations of a rule inside
39// gates, because a test that calls the code under test can only confirm
40// self-consistency -- and that decision is what caught a dead primitive
41// earlier.  So this reports CANDIDATES, and gate-to-gate matches are counted
42// separately from product-code matches, because only the second kind is
43// unambiguously debt.
44//
45//   nx_dupfunc <root-dir> [min-body-bytes] [topk]
46//     default root runtime, min body 200 bytes, topk 25
47//
48// license_tier: ORIGINAL
49import "nx_syscalls.nx"
50import "nx_eco_graph.nx"
51import "nx_gatelib.nx"
52const DF_MAGIC_1469598103934665603: i64 = 1469598103934665603
53const DF_MAGIC_1099511628211: i64 = 1099511628211
54const DF_MAGIC_4096: i64 = 4096
55const DF_MAGIC_262144: i64 = 262144
56
57const DF_MAXNODE: i64 = 24000
58const DF_ARENA:   i64 = 4194304
59const DF_HASH:    i64 = 65536
60const DF_PATHARENA: i64 = 4194304
61const DF_MAXFUNCS: i64 = 64
62// Total functions tracked across the whole scan.  DECLARED, and reported.
63const DF_MAXTOTAL: i64 = 120000
64
65func dw(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
66func dn(v: i64) -> i64 { let b: *u8 = sys_mmap(24); var m: i64 = v; if m < 0 { sys_write(1, "-" as *u8, 1); m = 0 - m } let t: *u8 = sys_mmap(24); var k: i64 = 0; if m == 0 { t[0] = 48 as u8; k = 1 } while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } var i: i64 = 0; while i < k { b[i] = t[k - 1 - i]; i = i + 1 } sys_write(1, b, k); return 0 }
67
68
69// FNV-1a over the normalised body.  A 64-bit hash over bodies this size makes
70// an accidental collision vanishingly unlikely, and the report prints the
71// file names so a human confirms before acting -- the hash narrows the search,
72// it does not decide.
73func df_hash(buf: *u8, n: i64) -> i64 {
  var h: i64 = DF_MAGIC_1469598103934665603
  var i: i64 = 0
  while i < n {
      h = h ^ (buf[i] as i64)
      h = h * DF_MAGIC_1099511628211
      i = i + 1
  }
  return h
82}
83
84func main(argc: i64, argv: *i64) -> i64 {
  var root: *u8 = "runtime" as *u8
  var minbody: i64 = 200
  var topk: i64 = 25
  if argc >= 2 { root = argv[1] as *u8 }
  if argc >= 3 {
      let s: *u8 = argv[2] as *u8
      var v: i64 = 0
      var i: i64 = 0
      while s[i] != (0 as u8) { let d: i64 = s[i] as i64; if d >= 48 { if d <= 57 { v = v * 10 + (d - 48) } } i = i + 1 }
      minbody = v
  }
  if argc >= 4 {
      let s2: *u8 = argv[3] as *u8
      var v2: i64 = 0
      var i2: i64 = 0
      while s2[i2] != (0 as u8) { let d2: i64 = s2[i2] as i64; if d2 >= 48 { if d2 <= 57 { v2 = v2 * 10 + (d2 - 48) } } i2 = i2 + 1 }
      if v2 > 0 { topk = v2 }
  }
103
  let g: *EcoGraph = eg_new(DF_MAXNODE, 8, DF_ARENA, DF_HASH)
  let patharena: *u8 = sys_mmap(DF_PATHARENA)
  let pathoff: *i64 = sys_mmap(DF_MAXNODE * 8) as *i64
  let used: *i64 = sys_mmap(16)
  let st: *i64 = sys_mmap(16)
  used[0] = 0
  st[0] = 0
  var z: i64 = 0
  while z < DF_MAXNODE { pathoff[z] = 0; z = z + 1 }
  let path: *u8 = sys_mmap(DF_MAGIC_4096)
  var rn: i64 = 0
  while root[rn] != (0 as u8) { path[rn] = root[rn]; rn = rn + 1 }
  gl_walk(g, path, rn, 0 as *u8, 0 as *i64, 0 as *i64, st, 0, patharena, pathoff, used, DF_PATHARENA)
117
  dw("=== NISHI DUPFUNC -- function bodies written more than once ===\n" as *u8)
  dw("root=" as *u8); dw(root)
  dw("  files=" as *u8); dn(st[0])
  dw("  min body bytes=" as *u8); dn(minbody)
  dw("  caps: " as *u8); dn(DF_MAXFUNCS); dw("/organ " as *u8); dn(DF_MAXTOTAL)
  dw(" total (DECLARED)\n" as *u8)
124
  let hashes: *i64 = sys_mmap(DF_MAXTOTAL * 8) as *i64
  let sizes: *i64 = sys_mmap(DF_MAXTOTAL * 8) as *i64
  let owner: *i64 = sys_mmap(DF_MAXTOTAL * 8) as *i64
  var nf: i64 = 0
129
  let src: *u8 = sys_mmap(GL_FILECAP)
  let strip: *u8 = sys_mmap(GL_FILECAP)
  let norm: *u8 = sys_mmap(GL_FILECAP)
  let names: *u8 = sys_mmap(DF_MAXFUNCS * 96)
  let offs: *i64 = sys_mmap(DF_MAXFUNCS * 8) as *i64
  let lens: *i64 = sys_mmap(DF_MAXFUNCS * 8) as *i64
  let spans: *i64 = sys_mmap(DF_MAXFUNCS * 8) as *i64
137
  var v: i64 = 0
  while v < g.node_count {
      if pathoff[v] > 0 {
          if nf < DF_MAXTOTAL - DF_MAXFUNCS {
              let fp: *u8 = ((patharena as i64) + pathoff[v] - 1) as *u8
              let n: i64 = gl_read(fp, src, GL_FILECAP)
              if n > 0 {
                  let sn: i64 = gl_strip_comments(src, n, strip)
                  let fc: i64 = gl_extract_funcs(strip, sn, names, offs, lens, spans, DF_MAXFUNCS)
                  var f: i64 = 0
                  while f < fc {
                      var e: i64 = sn
                      if f + 1 < fc { e = spans[f + 1] }
                      let bs: i64 = spans[f]
                      if e > bs {
                          // normalise: skip the signature up to '{', then
                          // collapse whitespace runs to one space
                          // ⚠NishiLang has no break, and the first cut of
                          // this loop escaped by assigning the loop variable
                          // (p = e) -- which DESTROYED the position it had
                          // just found, so every body came out empty and the
                          // whole scan reported 0 functions and verdict=GREEN
                          // over 17000 files. A tool that reports nothing is
                          // indistinguishable from a clean tree, which is the
                          // worst failure a detector has. LATCH the position
                          // in its own variable and let the loop run out.
                          var p: i64 = bs
                          var bodystart: i64 = 0 - 1
                          while p < e {
                              if bodystart < 0 { if strip[p] == (123 as u8) { bodystart = p + 1 } }
                              p = p + 1
                          }
                          if bodystart < 0 { bodystart = e }
                          var w: i64 = 0
                          var q: i64 = bodystart
                          var ws: i64 = 0
                          while q < e {
                              let c: i64 = strip[q] as i64
                              var isws: i64 = 0
                              if c == 32 { isws = 1 }
                              if c == 9 { isws = 1 }
                              if c == 10 { isws = 1 }
                              if c == 13 { isws = 1 }
                              if isws == 1 {
                                  if ws == 0 { if w < GL_FILECAP { norm[w] = 32 as u8; w = w + 1 } ws = 1 }
                              } else {
                                  if w < GL_FILECAP { norm[w] = strip[q]; w = w + 1 }
                                  ws = 0
                              }
                              q = q + 1
                          }
                          if w >= minbody {
                              hashes[nf] = df_hash(norm, w)
                              sizes[nf] = w
                              owner[nf] = v
                              nf = nf + 1
                          }
                      }
                      f = f + 1
                  }
              }
          }
      }
      v = v + 1
  }
203
  dw("functions measured (body >= min): " as *u8); dn(nf); dw("\n" as *u8)
205
  // Group by hash.  O(n^2) would be 1e10 here, so sort indices by hash
  // first with a simple insertion pass over a bucketed table instead:
  // bucket by hash modulo a large prime, then compare within buckets.
  let BK: i64 = DF_MAGIC_262144
  let head: *i64 = sys_mmap(BK * 8) as *i64
  let next: *i64 = sys_mmap(DF_MAXTOTAL * 8) as *i64
  var b: i64 = 0
  while b < BK { head[b] = 0 - 1; b = b + 1 }
  var i2: i64 = 0
  while i2 < nf {
      var hh: i64 = hashes[i2]
      if hh < 0 { hh = 0 - hh }
      let slot: i64 = hh % BK
      next[i2] = head[slot]
      head[slot] = i2
      i2 = i2 + 1
  }
223
  let bk_sev: *i64 = sys_mmap((topk + 2) * 8) as *i64
  let bk_rep: *i64 = sys_mmap((topk + 2) * 8) as *i64
  let bk_cnt: *i64 = sys_mmap((topk + 2) * 8) as *i64
  let bk_sz: *i64 = sys_mmap((topk + 2) * 8) as *i64
  var bn: i64 = 0
  var groups: i64 = 0
  var dupfuncs: i64 = 0
  var wasted: i64 = 0
  var g_gate: i64 = 0
  var g_prod: i64 = 0
  var g_mixed: i64 = 0
  var c_prod: i64 = 0
  var b_prod: i64 = 0
237
  let done: *u8 = sys_mmap(DF_MAXTOTAL + 8)
  var d0: i64 = 0
  while d0 < nf { done[d0] = 0 as u8; d0 = d0 + 1 }
241
  var i3: i64 = 0
  while i3 < nf {
      if done[i3] == (0 as u8) {
          var hh2: i64 = hashes[i3]
          if hh2 < 0 { hh2 = 0 - hh2 }
          let slot2: i64 = hh2 % BK
          var cnt: i64 = 0
          var p2: i64 = head[slot2]
          while p2 >= 0 {
              if hashes[p2] == hashes[i3] {
                  if sizes[p2] == sizes[i3] {
                      done[p2] = 1 as u8
                      cnt = cnt + 1
                  }
              }
              p2 = next[p2]
          }
          if cnt > 1 {
              // ★CLASSIFY THE GROUP BEFORE COUNTING IT. A group whose copies
              // all live in gate files is usually a DELIBERATE independent
              // re-derivation -- this tree keeps those on purpose, because a
              // test that calls the code under test can only confirm
              // self-consistency. A group entirely inside product code has
              // no such defence and is unambiguous debt. Reporting one
              // number for both makes the headline an upper bound that
              // nobody can act on, which is what the first version did.
              var gatecopies: i64 = 0
              var p4: i64 = head[slot2]
              while p4 >= 0 {
                  if hashes[p4] == hashes[i3] {
                      if sizes[p4] == sizes[i3] {
                          let nmc: *u8 = ((g.arena as i64) + g.node_off[owner[p4]]) as *u8
                          if gl_is_gate_name(nmc, gl_len(nmc)) == 1 { gatecopies = gatecopies + 1 }
                      }
                  }
                  p4 = next[p4]
              }
              var cls: i64 = 2
              if gatecopies == cnt { cls = 0 }
              if gatecopies == 0 { cls = 1 }
              groups = groups + 1
              if cls == 0 { g_gate = g_gate + 1 }
              if cls == 1 { g_prod = g_prod + 1; c_prod = c_prod + (cnt - 1) }
              if cls == 2 { g_mixed = g_mixed + 1 }
              dupfuncs = dupfuncs + (cnt - 1)
              let sev0: i64 = (cnt - 1) * sizes[i3]
              wasted = wasted + sev0
              // Only PRODUCT-ONLY groups compete for the board.
              var sev: i64 = 0
              if cls == 1 { sev = sev0 }
              if cls == 1 { b_prod = b_prod + sev0 }
              var start: i64 = 0 - 1
              if sev > 0 {
              if bn < topk {
                  start = bn
                  bk_sev[bn] = sev; bk_rep[bn] = i3; bk_cnt[bn] = cnt; bk_sz[bn] = sizes[i3]
                  bn = bn + 1
              }
              if bn >= topk {
                  if start < 0 {
                      if sev > bk_sev[topk - 1] {
                          start = topk - 1
                          bk_sev[start] = sev; bk_rep[start] = i3; bk_cnt[start] = cnt; bk_sz[start] = sizes[i3]
                      }
                  }
              }
              }
              var q2: i64 = start
              while q2 > 0 {
                  if bk_sev[q2 - 1] < bk_sev[q2] {
                      let t1: i64 = bk_sev[q2-1]; bk_sev[q2-1] = bk_sev[q2]; bk_sev[q2] = t1
                      let t2: i64 = bk_rep[q2-1]; bk_rep[q2-1] = bk_rep[q2]; bk_rep[q2] = t2
                      let t3: i64 = bk_cnt[q2-1]; bk_cnt[q2-1] = bk_cnt[q2]; bk_cnt[q2] = t3
                      let t4: i64 = bk_sz[q2-1]; bk_sz[q2-1] = bk_sz[q2]; bk_sz[q2] = t4
                      q2 = q2 - 1
                  } else { q2 = 0 }
              }
          }
      }
      i3 = i3 + 1
  }
323
  dw("duplicate GROUPS=" as *u8); dn(groups)
  dw("  redundant copies=" as *u8); dn(dupfuncs)
  dw("  bytes duplicated=" as *u8); dn(wasted)
  dw("
split: gate-only=" as *u8); dn(g_gate)
  dw(" (deliberate re-derivations, kept on purpose)  mixed=" as *u8); dn(g_mixed)
  dw("
** PRODUCT-ONLY groups=" as *u8); dn(g_prod)
  dw("  copies=" as *u8); dn(c_prod)
  dw("  bytes=" as *u8); dn(b_prod)
  dw("  <== the actionable debt **
335" as *u8)
  dw("\n-- ranked by (copies-1) x body size; top " as *u8); dn(bn)
  dw(" (bound DECLARED) --\n" as *u8)
  var r: i64 = 0
  while r < bn {
      let rep: i64 = bk_rep[r]
      dw("  cost=" as *u8); dn(bk_sev[r])
      dw("  copies=" as *u8); dn(bk_cnt[r])
      dw("  body=" as *u8); dn(bk_sz[r])
      dw("B  in: " as *u8)
      // name every file holding this body
      var hh3: i64 = hashes[rep]
      if hh3 < 0 { hh3 = 0 - hh3 }
      var p3: i64 = head[hh3 % BK]
      var shown: i64 = 0
      while p3 >= 0 {
          if hashes[p3] == hashes[rep] {
              if sizes[p3] == sizes[rep] {
                  if shown < 6 {
                      let nm: *u8 = ((g.arena as i64) + g.node_off[owner[p3]]) as *u8
                      dw(nm); dw(" " as *u8)
                      shown = shown + 1
                  }
              }
          }
          p3 = next[p3]
      }
      dw("\n" as *u8)
      r = r + 1
  }
  dw("\nNOTE: identical bodies are CANDIDATES, not automatically defects.\n" as *u8)
  dw("      This tree deliberately keeps independent re-derivations inside\n" as *u8)
  dw("      gates -- a test that calls the code under test can only confirm\n" as *u8)
  dw("      self-consistency. Confirm by reading before removing anything.\n" as *u8)
  if groups == 0 { dw("verdict=GREEN\n" as *u8); sys_exit(0); return 0 }
  dw("verdict=CANDIDATES\n" as *u8)
  sys_exit(0)
  return 0
373}
nx_dupfunc.nx source

`nx_dupfunc.nx` source
