grammar.go raw
1 // Package grammar defines adjacency rules for lattice element types.
2 //
3 // A grammar is a directed adjacency set: it specifies which element types
4 // can be neighbors in a lattice. This shapes the lattice topology to
5 // reflect the structure of the domain (e.g., Go AST hierarchy) rather
6 // than using flat random-node connectivity.
7 //
8 // The grammar is the rigid backbone — like the spinal cord in the nervous
9 // system, its shape is determined by what it connects to. Different
10 // grammars produce different topologies, and different seeds within the
11 // same grammar produce different wiring realizations.
12 package grammar
13
14 import (
15 "sort"
16 "sync"
17
18 "git.mleku.dev/mleku/dendrite/pkg/ratio"
19 )
20
21 // Rule defines a single adjacency: elements with Tag can neighbor elements
22 // with any of the Neighbors tags.
23 type Rule struct {
24 Tag string
25 Neighbors []string
26 }
27
28 // Grammar is an ordered set of adjacency rules.
29 type Grammar struct {
30 Rules []Rule
31 index map[string]map[string]bool // lazily built: tag -> set of valid neighbors
32 buildOne sync.Once
33 }
34
35 // build populates the index from Rules if not already built.
36 // Safe for concurrent use — sync.Once ensures single initialization.
37 func (g *Grammar) build() {
38 g.buildOne.Do(func() {
39 g.index = make(map[string]map[string]bool)
40 for _, r := range g.Rules {
41 if g.index[r.Tag] == nil {
42 g.index[r.Tag] = make(map[string]bool)
43 }
44 for _, nb := range r.Neighbors {
45 g.index[r.Tag][nb] = true
46 }
47 }
48 })
49 }
50
51 // CanNeighbor reports whether an element of type a can be adjacent to
52 // an element of type b. The check is directional: a→b may be valid
53 // while b→a is not. Callers should check both directions for symmetric
54 // adjacency.
55 func (g *Grammar) CanNeighbor(a, b string) bool {
56 g.build()
57 return g.index[a][b]
58 }
59
60 // NeighborsOf returns the set of tags that can neighbor the given tag.
61 func (g *Grammar) NeighborsOf(tag string) []string {
62 g.build()
63 nbs := g.index[tag]
64 out := make([]string, 0, len(nbs))
65 for nb := range nbs {
66 out = append(out, nb)
67 }
68 sort.Strings(out)
69 return out
70 }
71
72 // Tags returns all tags that appear in the grammar (as sources of rules),
73 // sorted for deterministic ordering.
74 func (g *Grammar) Tags() []string {
75 seen := make(map[string]bool)
76 for _, r := range g.Rules {
77 seen[r.Tag] = true
78 for _, nb := range r.Neighbors {
79 seen[nb] = true
80 }
81 }
82 out := make([]string, 0, len(seen))
83 for tag := range seen {
84 out = append(out, tag)
85 }
86 sort.Strings(out)
87 return out
88 }
89
90 // DefaultCounts returns a tag count map suitable for BuildGrammarLattice.
91 // It distributes targetSize nodes across all grammar tags using fixed
92 // proportions derived from typical Go source statistics. The wordFrac
93 // parameter controls the word/punct ratio for text enzyme fallback tags.
94 func (g *Grammar) DefaultCounts(targetSize int, wordFrac ratio.Ratio) map[string]int {
95 // Proportional weights for Go AST element types.
96 // These reflect typical Go source: more identifiers and literals
97 // than switch/select statements. Body statements are weighted by
98 // frequency in real codebases.
99 weights := map[string]int{
100 // Declarations — the skeleton.
101 "package": 1, "import": 2, "func": 4, "method": 4, "type": 3,
102 "struct": 2, "interface": 2, "field": 3, "var": 2, "directive": 1,
103 // Body statements — the meat.
104 "assign": 4, "return": 3, "if": 3, "for": 2, "switch": 1,
105 "select": 1, "go": 1, "send": 1, "expr": 3, "defer": 1,
106 "decl": 1, "branch": 1, "case": 1, "comm": 1,
107 // Declaration-level ident subtypes.
108 "ident:func-name": 1, "ident:method-name": 1, "ident:type-name": 1,
109 "ident:field-name": 1, "ident:param": 1, "ident:result": 1,
110 "ident:receiver": 1, "ident:var-name": 1,
111 // Reference material.
112 "grammar-rule": 2,
113 // Other atoms.
114 "comment": 1, "file": 1,
115 // Text enzyme fallback — scaled by wordFrac.
116 "word": 0, "punct": 0,
117 }
118
119 // Text fallback: allocate ~15% of nodes to word/punct.
120 textNodes := max(2, targetSize*15/100)
121 wordNodes := int(wordFrac.ScaleInt(int64(textNodes)))
122 punctNodes := textNodes - wordNodes
123 if punctNodes < 1 {
124 punctNodes = 1
125 wordNodes = textNodes - 1
126 }
127 weights["word"] = wordNodes
128 weights["punct"] = punctNodes
129
130 // Sum weights.
131 totalWeight := 0
132 for _, w := range weights {
133 totalWeight += w
134 }
135
136 // Distribute remaining nodes proportionally.
137 remaining := targetSize - textNodes
138 if remaining < 1 {
139 remaining = 1
140 }
141
142 counts := make(map[string]int)
143 allocated := 0
144 // Sort keys for deterministic allocation.
145 keys := make([]string, 0, len(weights))
146 for k := range weights {
147 keys = append(keys, k)
148 }
149 sort.Strings(keys)
150
151 astWeight := totalWeight - weights["word"] - weights["punct"]
152 if astWeight < 1 {
153 astWeight = 1
154 }
155
156 for _, tag := range keys {
157 w := weights[tag]
158 if tag == "word" || tag == "punct" {
159 counts[tag] = w
160 allocated += w
161 continue
162 }
163 n := remaining * w / astWeight
164 if n < 1 && w > 0 {
165 n = 1
166 }
167 counts[tag] = n
168 allocated += n
169 }
170
171 // Distribute any rounding remainder to "ident:var-name" (most flexible).
172 if allocated < targetSize {
173 counts["ident:var-name"] += targetSize - allocated
174 }
175
176 return counts
177 }
178
179 // bodyStmtTags are the Go body statement element types.
180 var bodyStmtTags = []string{
181 "assign", "return", "if", "for", "switch", "select",
182 "go", "send", "expr", "defer", "decl", "branch", "case", "comm",
183 }
184
185 // IdentSubtypes lists the declaration-level ident subtypes emitted by the
186 // Go enzyme. Expression-level idents (ref, selector, call-target) and
187 // literals are carried inside rendered statement elements and not emitted
188 // as standalone elements.
189 var IdentSubtypes = []string{
190 "ident:field-name",
191 "ident:func-name",
192 "ident:method-name",
193 "ident:param",
194 "ident:receiver",
195 "ident:result",
196 "ident:type-name",
197 "ident:var-name",
198 }
199
200 // GoAST is the input grammar derived from Go AST structure.
201 // Functions contain body statements. Body statements reference identifiers.
202 // Types contain structs/interfaces/fields. Imports are adjacent to package.
203 var GoAST = &Grammar{Rules: func() []Rule {
204 // Body statements can neighbor each other and declaration-level idents.
205 bodyNeighbors := append(append([]string{}, IdentSubtypes...), bodyStmtTags...)
206
207 rules := []Rule{
208 // Package scope.
209 {Tag: "package", Neighbors: []string{"import", "func", "method", "type", "var", "directive", "comment", "file"}},
210 {Tag: "import", Neighbors: []string{"package", "func", "method", "type", "var"}},
211 {Tag: "file", Neighbors: []string{"package", "import", "func", "method", "type", "comment"}},
212 {Tag: "directive", Neighbors: []string{"func", "method", "type", "var", "package"}},
213 {Tag: "comment", Neighbors: []string{"package", "func", "method", "type", "struct", "interface", "field", "var", "file"}},
214
215 // Function declarations neighbor their body types and naming subtypes.
216 {Tag: "func", Neighbors: append([]string{
217 "type", "var", "comment",
218 "ident:func-name", "ident:param", "ident:result", "ident:var-name",
219 }, bodyStmtTags...)},
220 {Tag: "method", Neighbors: append([]string{
221 "type", "struct", "var", "comment",
222 "ident:method-name", "ident:receiver", "ident:param", "ident:result", "ident:var-name",
223 }, bodyStmtTags...)},
224
225 // Type declarations.
226 {Tag: "type", Neighbors: []string{
227 "struct", "interface", "field", "func", "method", "comment",
228 "ident:type-name",
229 }},
230 {Tag: "struct", Neighbors: []string{
231 "field", "type", "method", "comment",
232 "ident:field-name", "ident:type-name",
233 }},
234 {Tag: "interface", Neighbors: []string{
235 "method", "type", "comment",
236 "ident:method-name",
237 }},
238 {Tag: "field", Neighbors: []string{
239 "struct", "type", "comment",
240 "ident:field-name",
241 }},
242 {Tag: "var", Neighbors: []string{
243 "type", "assign", "expr", "func",
244 "ident:var-name",
245 }},
246
247 // Declaration-level ident subtypes.
248 {Tag: "ident:func-name", Neighbors: []string{"func", "expr"}},
249 {Tag: "ident:method-name", Neighbors: []string{"method", "interface", "expr"}},
250 {Tag: "ident:type-name", Neighbors: []string{"type", "struct", "interface", "field"}},
251 {Tag: "ident:field-name", Neighbors: []string{"struct", "field", "type"}},
252 {Tag: "ident:param", Neighbors: []string{"func", "method"}},
253 {Tag: "ident:result", Neighbors: []string{"func", "method"}},
254 {Tag: "ident:receiver", Neighbors: []string{"method", "struct"}},
255 {Tag: "ident:var-name", Neighbors: []string{"var", "assign", "func", "method"}},
256
257 // Grammar rules from the Go spec — EBNF productions that describe
258 // valid Go syntax. These neighbor all declaration and statement types
259 // so the lattice can structurally associate grammar rules with the
260 // code elements they describe.
261 {Tag: "grammar-rule", Neighbors: []string{
262 "func", "method", "type", "struct", "interface", "field",
263 "import", "var", "assign", "return", "if", "for",
264 "package", "expr", "switch", "select",
265 }},
266
267 // Text enzyme fallback.
268 {Tag: "word", Neighbors: []string{"punct", "word", "comment"}},
269 {Tag: "punct", Neighbors: []string{"word", "punct"}},
270 }
271
272 // Body statement types.
273 for _, tag := range bodyStmtTags {
274 rules = append(rules, Rule{Tag: tag, Neighbors: bodyNeighbors})
275 }
276
277 return rules
278 }()}
279
280 // GoEmit is the output grammar — tighter grouping for emission.
281 // Functions neighbor only their body types (no cross-function leakage).
282 // Types neighbor only their structural members.
283 var GoEmit = &Grammar{Rules: func() []Rule {
284 rules := []Rule{
285 {Tag: "package", Neighbors: []string{"import"}},
286 {Tag: "import", Neighbors: []string{"package"}},
287 {Tag: "file", Neighbors: []string{"package"}},
288 {Tag: "directive", Neighbors: []string{"func", "method"}},
289
290 // Functions are scoped to their bodies.
291 {Tag: "func", Neighbors: bodyStmtTags},
292 {Tag: "method", Neighbors: bodyStmtTags},
293
294 // Types are scoped to their members.
295 {Tag: "type", Neighbors: []string{"struct", "interface"}},
296 {Tag: "struct", Neighbors: []string{"field"}},
297 {Tag: "interface", Neighbors: []string{"method"}},
298 {Tag: "field", Neighbors: []string{"struct", "ident:field-name"}},
299 {Tag: "var", Neighbors: []string{"ident:var-name"}},
300
301 // Declaration-level ident subtypes — tighter emission grouping.
302 {Tag: "ident:func-name", Neighbors: []string{"func"}},
303 {Tag: "ident:method-name", Neighbors: []string{"method", "interface"}},
304 {Tag: "ident:type-name", Neighbors: []string{"type"}},
305 {Tag: "ident:field-name", Neighbors: []string{"field", "struct"}},
306 {Tag: "ident:param", Neighbors: []string{"func", "method"}},
307 {Tag: "ident:result", Neighbors: []string{"func", "method"}},
308 {Tag: "ident:receiver", Neighbors: []string{"method"}},
309 {Tag: "ident:var-name", Neighbors: []string{"var"}},
310
311 {Tag: "comment", Neighbors: []string{"func", "method", "type", "struct"}},
312
313 // Grammar rules — not emitted, but can neighbor declarations.
314 {Tag: "grammar-rule", Neighbors: []string{"func", "method", "type", "struct", "interface"}},
315
316 // Text.
317 {Tag: "word", Neighbors: []string{"punct", "word"}},
318 {Tag: "punct", Neighbors: []string{"word", "punct"}},
319 }
320
321 // Body statements neighbor only each other (same scope).
322 for _, tag := range bodyStmtTags {
323 rules = append(rules, Rule{Tag: tag, Neighbors: bodyStmtTags})
324 }
325
326 return rules
327 }()}
328