causal.go raw
1 // Package causal provides define-use analysis for Go source statements
2 // and a lattice constraint that enforces causal correctness.
3 //
4 // The CausalConstraint implements axiom.ContextualConstraint. It allows
5 // the lattice to learn causal ordering structurally — statements that
6 // reference identifiers defined by neighbors bond more readily than
7 // statements with no causal links.
8 //
9 // The constraint is intentionally lenient: it requires at least one
10 // causal link OR allows self-contained statements. Over multiple
11 // solve-et-coagula cycles, dissolution removes weakly-held elements
12 // and re-growth places them in better neighborhoods.
13 package causal
14
15 import (
16 "strings"
17 "unicode"
18
19 "git.mleku.dev/mleku/dendrite/pkg/axiom"
20 )
21
22 // CausalConstraint implements axiom.ContextualConstraint for body-level
23 // Go source elements. It checks that at least one identifier used by
24 // the element is defined by an occupied neighbor.
25 type CausalConstraint struct {
26 ConstraintTag string // the element type this constraint accepts
27 }
28
29 func (c CausalConstraint) Tag() string { return c.ConstraintTag }
30
31 func (c CausalConstraint) Admits(e axiom.Element) bool {
32 return e.Type() == c.ConstraintTag
33 }
34
35 func (c CausalConstraint) AdmitsInContext(e axiom.Element, neighbors []axiom.Element) bool {
36 if !c.Admits(e) {
37 return false
38 }
39 val, ok := e.Value().(string)
40 if !ok || val == "" {
41 return true
42 }
43 _, source := ParseParentSource(val)
44 uses := ExtractUses(source)
45 if len(uses) == 0 {
46 return true // no dependencies — bonds anywhere
47 }
48
49 // Collect all identifiers defined by occupied neighbors.
50 defined := make(map[string]bool)
51 for _, nb := range neighbors {
52 if nb == nil {
53 continue
54 }
55 nbVal, ok := nb.Value().(string)
56 if !ok {
57 continue
58 }
59 _, nbSrc := ParseParentSource(nbVal)
60 for id := range ExtractDefines(nbSrc) {
61 defined[id] = true
62 }
63 }
64
65 // At least one prerequisite must be satisfied by a neighbor.
66 for id := range uses {
67 if defined[id] {
68 return true
69 }
70 }
71
72 // No neighbor defines any used identifier. Allow bonding anyway —
73 // the element might depend on globals, function params, or package-level
74 // vars. The emitter's DAG sort handles the rest.
75 return true
76 }
77
78 // ParseParentSource splits "parent\x00source" from a body element's value.
79 func ParseParentSource(val string) (parent, source string) {
80 idx := strings.IndexByte(val, '\x00')
81 if idx < 0 {
82 return "", val
83 }
84 return val[:idx], val[idx+1:]
85 }
86
87 // ExtractDefines returns identifiers defined by a Go source statement.
88 // Looks for := left-hand sides and var declarations.
89 func ExtractDefines(src string) map[string]bool {
90 defs := make(map[string]bool)
91
92 // Short-assignment: "x := expr" or "x, y := expr"
93 if idx := strings.Index(src, ":="); idx >= 0 {
94 lhs := strings.TrimSpace(src[:idx])
95 for _, part := range strings.Split(lhs, ",") {
96 id := strings.TrimSpace(part)
97 if IsIdent(id) && id != "_" {
98 defs[id] = true
99 }
100 }
101 }
102
103 // var declarations: "var x int" or "var x = expr"
104 if strings.HasPrefix(src, "var ") {
105 rest := src[4:]
106 tokens := Tokenize(rest)
107 if len(tokens) > 0 && IsIdent(tokens[0]) {
108 defs[tokens[0]] = true
109 }
110 }
111
112 return defs
113 }
114
115 // ExtractUses returns identifiers used (but not defined) by a Go source statement.
116 func ExtractUses(src string) map[string]bool {
117 defs := ExtractDefines(src)
118 uses := make(map[string]bool)
119 for _, tok := range Tokenize(src) {
120 if IsIdent(tok) && !GoKeywords[tok] && !defs[tok] && !GoBuiltins[tok] {
121 uses[tok] = true
122 }
123 }
124 return uses
125 }
126
127 // Tokenize splits source text on non-identifier characters.
128 func Tokenize(src string) []string {
129 return strings.FieldsFunc(src, func(r rune) bool {
130 return !unicode.IsLetter(r) && !unicode.IsDigit(r) && r != '_'
131 })
132 }
133
134 // IsIdent returns true if s is a valid Go identifier.
135 func IsIdent(s string) bool {
136 if s == "" {
137 return false
138 }
139 for i, r := range s {
140 if i == 0 && !unicode.IsLetter(r) && r != '_' {
141 return false
142 }
143 if !unicode.IsLetter(r) && !unicode.IsDigit(r) && r != '_' {
144 return false
145 }
146 }
147 return true
148 }
149
150 // GoKeywords is the set of Go reserved keywords.
151 var GoKeywords = map[string]bool{
152 "break": true, "case": true, "chan": true, "const": true,
153 "continue": true, "default": true, "defer": true, "else": true,
154 "fallthrough": true, "for": true, "func": true, "go": true,
155 "goto": true, "if": true, "import": true, "interface": true,
156 "map": true, "package": true, "range": true, "return": true,
157 "select": true, "struct": true, "switch": true, "type": true,
158 "var": true,
159 }
160
161 // BodyStmtTags are element types that represent function body statements.
162 // Used by scope-aware constraints to identify elements that participate
163 // in define-use analysis.
164 var BodyStmtTags = map[string]bool{
165 "assign": true, "return": true, "if": true, "for": true,
166 "switch": true, "select": true, "go": true, "send": true,
167 "expr": true, "defer": true, "decl": true, "branch": true,
168 "case": true, "comm": true,
169 }
170
171 // ScopeConstraint enforces declaration-before-use within a function scope.
172 // Body elements that reference identifiers must have at least one neighbor
173 // in the same function scope that defines those identifiers. This creates
174 // lattice-level pressure toward correct variable scoping.
175 //
176 // Unlike CausalConstraint (which is lenient and allows unresolved uses),
177 // ScopeConstraint rejects elements whose uses are entirely unsatisfied
178 // when same-scope neighbors exist that could provide definitions.
179 //
180 // Self-contained statements (no uses, or uses only globals/builtins)
181 // always pass. Statements in scopes with no body-statement neighbors
182 // also pass (seed bonding).
183 type ScopeConstraint struct {
184 ConstraintTag string
185 }
186
187 func (c ScopeConstraint) Tag() string { return c.ConstraintTag }
188 func (c ScopeConstraint) Admits(e axiom.Element) bool { return e.Type() == c.ConstraintTag }
189
190 func (c ScopeConstraint) AdmitsInContext(e axiom.Element, neighbors []axiom.Element) bool {
191 if !c.Admits(e) {
192 return false
193 }
194 val, ok := e.Value().(string)
195 if !ok || val == "" {
196 return true
197 }
198 parent, source := ParseParentSource(val)
199 uses := ExtractUses(source)
200 if len(uses) == 0 {
201 return true // self-contained — no dependencies
202 }
203
204 // Collect definitions from same-scope neighbors (same parent function).
205 defined := make(map[string]bool)
206 hasScopeNeighbor := false
207 for _, nb := range neighbors {
208 if nb == nil {
209 continue
210 }
211 if !BodyStmtTags[nb.Type()] {
212 continue
213 }
214 nbVal, ok := nb.Value().(string)
215 if !ok {
216 continue
217 }
218 nbParent, nbSrc := ParseParentSource(nbVal)
219 if nbParent != parent {
220 continue // different function scope
221 }
222 hasScopeNeighbor = true
223 for id := range ExtractDefines(nbSrc) {
224 defined[id] = true
225 }
226 }
227
228 // No same-scope neighbors — allow seed bonding.
229 if !hasScopeNeighbor {
230 return true
231 }
232
233 // At least one used identifier must be defined by a scope neighbor.
234 for id := range uses {
235 if defined[id] {
236 return true
237 }
238 }
239
240 // None of the uses are satisfied by scope neighbors.
241 // Still allow if the statement defines something (it may be a
242 // root definition that others depend on).
243 defs := ExtractDefines(source)
244 if len(defs) > 0 {
245 return true
246 }
247
248 // Pure consumer with no scope-local definitions nearby — reject.
249 // This biases walkers toward neighborhoods that have the definitions
250 // the statement needs.
251 return false
252 }
253
254 // UniqueDefConstraint prevents duplicate variable declarations within a
255 // function scope. If a body element defines an identifier that is already
256 // defined by a same-parent neighbor, the bond is rejected.
257 //
258 // Go allows re-declaration with := when at least one variable is new,
259 // but duplicate definitions are a common source of bugs. This constraint
260 // creates evolutionary pressure against them — the lattice prefers
261 // arrangements where each identifier is defined once per scope.
262 type UniqueDefConstraint struct {
263 ConstraintTag string
264 }
265
266 func (c UniqueDefConstraint) Tag() string { return c.ConstraintTag }
267 func (c UniqueDefConstraint) Admits(e axiom.Element) bool { return e.Type() == c.ConstraintTag }
268
269 func (c UniqueDefConstraint) AdmitsInContext(e axiom.Element, neighbors []axiom.Element) bool {
270 if !c.Admits(e) {
271 return false
272 }
273 val, ok := e.Value().(string)
274 if !ok || val == "" {
275 return true
276 }
277 parent, source := ParseParentSource(val)
278 defs := ExtractDefines(source)
279 if len(defs) == 0 {
280 return true // no definitions — no conflict possible
281 }
282
283 // Check same-scope neighbors for conflicting definitions.
284 for _, nb := range neighbors {
285 if nb == nil {
286 continue
287 }
288 if !BodyStmtTags[nb.Type()] {
289 continue
290 }
291 nbVal, ok := nb.Value().(string)
292 if !ok {
293 continue
294 }
295 nbParent, nbSrc := ParseParentSource(nbVal)
296 if nbParent != parent {
297 continue // different function scope
298 }
299 nbDefs := ExtractDefines(nbSrc)
300 for id := range defs {
301 if nbDefs[id] {
302 return false // duplicate definition in same scope
303 }
304 }
305 }
306
307 return true
308 }
309
310 // GoBuiltins is the set of Go predeclared identifiers.
311 var GoBuiltins = map[string]bool{
312 "bool": true, "byte": true, "complex64": true, "complex128": true,
313 "error": true, "float32": true, "float64": true, "int": true,
314 "int8": true, "int16": true, "int32": true, "int64": true,
315 "rune": true, "string": true, "uint": true, "uint8": true,
316 "uint16": true, "uint32": true, "uint64": true, "uintptr": true,
317 "true": true, "false": true, "iota": true, "nil": true,
318 "append": true, "cap": true, "clear": true, "close": true,
319 "complex": true, "copy": true, "delete": true, "imag": true,
320 "len": true, "make": true, "max": true, "min": true,
321 "new": true, "panic": true, "print": true, "println": true,
322 "real": true, "recover": true, "any": true,
323 }
324