Module: Moult::Cycles

Defined in:
lib/moult/cycles.rb

Overview

File-level circular dependencies over the Index#file_edges graph. Every edge is a resolved constant reference — the only dependency signal that survives Zeitwerk autoloading, where require lines are absent — so each cycle is backed by concrete reference sites, never name matching.

Constant Summary collapse

CONFIDENCE =

High because every edge is a resolved constant reference, but not 1.0: a constant reopened in several files fans its edges out to every definition file, which can widen a cycle beyond the code that actually participates.

0.9
CATEGORY = 
"cycle"

Class Method Summary collapse

Class Method Details

.adjacency(edges) ⇒ Object

Sorted node => sorted children over every file named by an edge, so the SCC walk (and therefore the report) is deterministic regardless of the order edges arrive in.



38
39
40
41
42
43
44
45
 
# File 'lib/moult/cycles.rb', line 38

def adjacency(edges)
  adj = {}
  edges.each do |edge|
    (adj[edge.src] ||= []) << edge.dst
    adj[edge.dst] ||= []
  end
  adj.keys.sort.to_h { |node| [node, adj[node].uniq.sort] }
end

.build_report(root:, edges:, git_ref: nil, generated_at: nil, backend_version: nil, resolved: true, diagnostics: []) ⇒ CyclesReport

Returns findings ranked largest cycle first.

Parameters:

  • root (String) —

    absolute analysis root

  • edges (Array<Index::Edge>) —

    file dependency edges

Returns:



23
24
25
26
27
28
29
30
31
32
33
 
# File 'lib/moult/cycles.rb', line 23

def build_report(root:, edges:, git_ref: nil, generated_at: nil,
  backend_version: nil, resolved: true, diagnostics: [])
  components = strongly_connected(adjacency(edges))
  findings = components.select { |c| c.size >= 2 }.map { |c| finding_for(c, edges) }
  findings.sort_by! { |f| [-f.size, f.files.first] }
  CyclesReport.new(
    root: root, findings: findings, git_ref: git_ref, generated_at: generated_at,
    backend: "rubydex", backend_version: backend_version,
    resolved: resolved, diagnostics: diagnostics
  )
end

.finding_for(component, edges) ⇒ Object 



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/moult/cycles.rb', line 105

def finding_for(component, edges)
  files = component.sort
  member = component.to_h { |f| [f, true] }
  evidence = edges.select { |e| member[e.src] && member[e.dst] && e.src != e.dst }
    .sort_by { |e| [e.src, e.dst] }
  CyclesReport::Finding.new(
    cycle_group: fingerprint(files),
    confidence: CONFIDENCE,
    category: CATEGORY,
    size: files.size,
    files: files,
    reasons: [Confidence::Reason.new(
      rule: :resolved_constant_edges,
      delta: CONFIDENCE,
      detail: "every edge is a resolved constant reference; reopened constants can widen a cycle"
    )],
    edges: evidence
  )
end

.fingerprint(files) ⇒ Object

Membership-stable across runs and machines (unlike a detector-backend hash): the same set of files is the same cycle, however its edges shift.



127
128
129
 
# File 'lib/moult/cycles.rb', line 127

def fingerprint(files)
  "scc:#{Digest::SHA256.hexdigest(files.join("\n"))[0, 12]}"
end

.strongly_connected(adj) ⇒ Object

Tarjan's strongly-connected components with an explicit work stack. ponytail: hand-rolled because stdlib TSort's SCC walk is recursive and SystemStackErrors on cycles a few thousand files deep (measured at ~5k); swap back to TSort if it ever gains an iterative walker.



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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
97
98
99
100
101
102
103
 
# File 'lib/moult/cycles.rb', line 51

def strongly_connected(adj)
  index = {}
  lowlink = {}
  on_stack = {}
  stack = []
  components = []
  counter = 0

  adj.each_key do |start|
    next if index.key?(start)
    work = [[start, 0]]
    until work.empty?
      frame = work.last
      node = frame[0]
      if frame[1].zero? # first visit
        index[node] = lowlink[node] = counter
        counter += 1
        stack << node
        on_stack[node] = true
      end

      children = adj[node]
      pushed = false
      while frame[1] < children.size
        child = children[frame[1]]
        frame[1] += 1
        if !index.key?(child)
          work << [child, 0]
          pushed = true
          break
        elsif on_stack[child]
          lowlink[node] = [lowlink[node], index[child]].min
        end
      end
      next if pushed

      work.pop
      if lowlink[node] == index[node]
        component = []
        loop do
          member = stack.pop
          on_stack.delete(member)
          component << member
          break if member == node
        end
        components << component
      end
      parent = work.last&.first
      lowlink[parent] = [lowlink[parent], lowlink[node]].min if parent
    end
  end
  components
end