walk.go raw
1 // Package walk implements an ergodic PRNG-driven repository walker.
2 //
3 // The walker builds a manifest of all files in a repository,
4 // shuffles them via Fisher-Yates with a deterministic PRNG seed,
5 // and iterates one file at a time. This ensures every file is visited
6 // exactly once in a deterministic (but non-sequential) order.
7 // Code, prose, config, binary data — everything gets walked.
8 package walk
9
10 import (
11 "io"
12 "math"
13 "math/rand/v2"
14 "os"
15 "path/filepath"
16 "slices"
17 "strings"
18
19 "git.mleku.dev/mleku/dendrite/pkg/axiom"
20 "git.mleku.dev/mleku/dendrite/pkg/enzyme"
21 "git.mleku.dev/mleku/dendrite/pkg/ratio"
22 )
23
24 // Default directories to exclude from the walk.
25 var DefaultExclude = []string{
26 ".git", "node_modules", "vendor",
27 "dist", "build", "coverage", ".svelte-kit", ".next",
28 "memory", // live Badger database — exclude while open
29 }
30
31 // Manifest is all source files in a repository, in PRNG-permuted order.
32 type Manifest struct {
33 Files []string `json:"files"` // relative paths in permuted order
34 Root string `json:"root"`
35 Seed uint64 `json:"seed"`
36 }
37
38 // Build scans root for all files, excludes directories matching
39 // the exclude list, and returns a manifest with files in PRNG-permuted order.
40 func Build(root string, seed uint64, exclude []string) (*Manifest, error) {
41 root, files, err := scanFiles(root, exclude)
42 if err != nil {
43 return nil, err
44 }
45
46 // Fisher-Yates shuffle with deterministic PRNG.
47 rng := rand.New(rand.NewPCG(seed, seed^0xdeadbeef))
48 for i := len(files) - 1; i > 0; i-- {
49 j := rng.IntN(i + 1)
50 files[i], files[j] = files[j], files[i]
51 }
52
53 return &Manifest{
54 Files: files,
55 Root: root,
56 Seed: seed,
57 }, nil
58 }
59
60 // BuildWeighted scans root for all files and orders them via
61 // Efraimidis-Spirakis weighted random permutation. Files with higher
62 // weight appear statistically earlier. weights maps relative file path
63 // to weight; files not in the map get defaultWeight.
64 func BuildWeighted(root string, seed uint64, exclude []string,
65 weights map[string]float64, defaultWeight float64) (*Manifest, error) {
66
67 root, files, err := scanFiles(root, exclude)
68 if err != nil {
69 return nil, err
70 }
71
72 // Efraimidis-Spirakis: for each file compute key = u^(1/w).
73 // Sort descending by key. Higher weight → statistically higher key.
74 rng := rand.New(rand.NewPCG(seed, seed^0xdeadbeef))
75
76 type keyed struct {
77 path string
78 key float64
79 }
80 items := make([]keyed, len(files))
81 for i, f := range files {
82 w := defaultWeight
83 if ww, ok := weights[f]; ok {
84 w = ww
85 }
86 if w < 1.0 {
87 w = 1.0
88 }
89 u := rng.Float64()
90 for u == 0 {
91 u = rng.Float64()
92 }
93 items[i] = keyed{path: f, key: math.Pow(u, 1.0/w)}
94 }
95
96 slices.SortFunc(items, func(a, b keyed) int {
97 if a.key > b.key {
98 return -1
99 }
100 if a.key < b.key {
101 return 1
102 }
103 return 0
104 })
105
106 sorted := make([]string, len(items))
107 for i, item := range items {
108 sorted[i] = item.path
109 }
110
111 return &Manifest{
112 Files: sorted,
113 Root: root,
114 Seed: seed,
115 }, nil
116 }
117
118 // DeriveNextSeed produces a new seed from the previous one using SplitMix64.
119 // Each epoch gets a different but deterministic seed.
120 func DeriveNextSeed(prev uint64) uint64 {
121 s := prev + 0x9e3779b97f4a7c15
122 s = (s ^ (s >> 30)) * 0xbf58476d1ce4e5b9
123 s = (s ^ (s >> 27)) * 0x94d049bb133111eb
124 return s ^ (s >> 31)
125 }
126
127 // scanFiles walks the directory tree and returns all file relative paths.
128 // Shared by Build and BuildWeighted.
129 func scanFiles(root string, exclude []string) (string, []string, error) {
130 excludeSet := make(map[string]bool, len(exclude))
131 for _, e := range exclude {
132 excludeSet[e] = true
133 }
134
135 var files []string
136 root = filepath.Clean(root)
137
138 err := filepath.WalkDir(root, func(path string, d os.DirEntry, err error) error {
139 if err != nil {
140 return nil // skip unreadable entries
141 }
142 if d.IsDir() {
143 if excludeSet[d.Name()] {
144 return filepath.SkipDir
145 }
146 return nil
147 }
148 rel, err := filepath.Rel(root, path)
149 if err != nil {
150 return nil
151 }
152 files = append(files, rel)
153 return nil
154 })
155 return root, files, err
156 }
157
158 // Walker iterates through the manifest one file at a time.
159 type Walker struct {
160 Manifest *Manifest `json:"manifest"`
161 Position int `json:"position"`
162 }
163
164 // NewWalker creates a walker starting at the beginning of the manifest.
165 func NewWalker(m *Manifest) *Walker {
166 return &Walker{Manifest: m}
167 }
168
169 // Resume creates a walker starting at the given position.
170 func Resume(m *Manifest, position int) *Walker {
171 return &Walker{Manifest: m, Position: position}
172 }
173
174 // Next returns the next file path (relative) and true, or ("", false)
175 // when the walk is complete.
176 func (w *Walker) Next() (string, bool) {
177 if w.Position >= len(w.Manifest.Files) {
178 return "", false
179 }
180 path := w.Manifest.Files[w.Position]
181 w.Position++
182 return path, true
183 }
184
185 // Done reports whether all files have been visited.
186 func (w *Walker) Done() bool {
187 return w.Position >= len(w.Manifest.Files)
188 }
189
190 // Remaining returns the number of unvisited files.
191 func (w *Walker) Remaining() int {
192 r := len(w.Manifest.Files) - w.Position
193 if r < 0 {
194 return 0
195 }
196 return r
197 }
198
199 // Progress returns the fraction of files visited as a Ratio.
200 func (w *Walker) Progress() ratio.Ratio {
201 total := len(w.Manifest.Files)
202 if total == 0 {
203 return ratio.One
204 }
205 return ratio.New(int64(w.Position), int64(total))
206 }
207
208 // DigestNext opens the next file, routes it through the correct enzyme,
209 // and returns a channel of elements. Returns nil, false when the walk
210 // is complete.
211 func (w *Walker) DigestNext() (<-chan axiom.Element, bool) {
212 relPath, ok := w.Next()
213 if !ok {
214 return nil, false
215 }
216
217 absPath := filepath.Join(w.Manifest.Root, relPath)
218 f, err := os.Open(absPath)
219 if err != nil {
220 // Skip unreadable files — return empty channel.
221 ch := make(chan axiom.Element)
222 close(ch)
223 return ch, true
224 }
225
226 ch := make(chan axiom.Element, 64)
227 go func() {
228 defer close(ch)
229 defer f.Close()
230
231 // Emit file marker.
232 ch <- enzyme.Elem("file", relPath)
233
234 // Route to enzyme based on extension.
235 enzCh := digestReader(absPath, f)
236 for elem := range enzCh {
237 ch <- elem
238 }
239 }()
240
241 return ch, true
242 }
243
244 // digestReader selects the appropriate enzyme and digests the file.
245 func digestReader(path string, r io.ReadSeeker) <-chan axiom.Element {
246 ext := strings.ToLower(filepath.Ext(path))
247
248 // Read sample for enzyme detection.
249 sample := make([]byte, 512)
250 n, _ := r.Read(sample)
251 sample = sample[:n]
252 r.Seek(0, io.SeekStart)
253
254 switch ext {
255 case ".go":
256 enz := enzyme.GoSource{}
257 if enz.CanDigest(sample) {
258 return enz.Digest(r)
259 }
260 case ".ts", ".js", ".tsx", ".jsx", ".svelte":
261 enz := enzyme.JSSource{}
262 if enz.CanDigest(sample) {
263 return enz.Digest(r)
264 }
265 }
266
267 // Fallback: text enzyme.
268 r.Seek(0, io.SeekStart)
269 return enzyme.Text{}.Digest(r)
270 }
271