⎇ 53dbdf0f1deea10d6fc567ea2b43e1e75d6d60cd
crates/modules/semantic_dht/minga-core/src/alpha.rs
Ñawpa willay
Pi imata llamkarqan
ch'uya
chore: monorepo inicial con arje + minga + yahweh absorbidos
1//! Hash α-equivalente.
2//!
3//! Dos términos que difieren *solo* en los nombres de variables ligadas
4//! producen el mismo hash. Los nombres de funciones, los identificadores
5//! libres y los constructores (variantes, tipos) **sí** afectan al hash:
6//! forman parte de la interfaz pública o discriminan el término.
7//!
8//! Implementación: durante el recorrido se mantiene una pila de scopes.
9//! Al encontrar un binder reconocido, su nombre se empuja sobre la pila;
10//! al salir del scope, se descarta. Las referencias a identificadores se
11//! buscan desde la cima:
12//! - si están, se emite un índice estilo de Bruijn (offset desde la cima);
13//! - si no, se emite el nombre literal (variable libre).
14//!
15//! **Distinción binder vs. constructor:** dentro de un patrón, un
16//! `identifier` puede ser binder (`x`, `mi_var`) o constructor / variante
17//! (`None`, `Ok`, `MAX_VAL`). La gramática no los distingue; usamos la
18//! convención de Rust: minúscula inicial (o `_` seguido de letra) = binder,
19//! mayúscula inicial = constructor. Cuando el grammar marca explícitamente
20//! `field_name = "pattern"` (parámetros, lets), forzamos binder.
21//!
22//! **Cobertura del MVP:**
23//! - Parámetros de `function_item` y `closure_expression`.
24//! - Bindings de `let_declaration` dentro de `block`, con desestructura.
25//! - Variable de `for_expression`.
26//! - Brazos de `match` (`match_arm` con guarda; cada arm es un scope
27//! independiente).
28//! - Patrones: `tuple_pattern`, `tuple_struct_pattern`, `struct_pattern`,
29//! `field_pattern` (forma completa y shorthand), `captured_pattern`
30//! (`n @ pat`), `range_pattern`, `slice_pattern`, `ref_pattern`,
31//! `reference_pattern`, `mut_pattern`.
32//!
33//! **Pendiente:** `if let`, `while let`, `let-else`, let-chains, `or_pattern`
34//! con bindings (Rust requiere mismas variables en cada rama).
35
36use crate::ast::SemanticNode;
37use crate::cas::ContentHash;
38use blake3::Hasher;
39
40const TAG_NO_LEAF: u8 = 0;
41const TAG_LEAF: u8 = 1;
42const TAG_BINDER: u8 = 2;
43const TAG_REF_BOUND: u8 = 3;
44const TAG_REF_FREE: u8 = 4;
45
46pub fn hash_node_alpha(node: &SemanticNode) -> ContentHash {
47 let mut h = Hasher::new();
48 let mut scope: Vec<String> = Vec::new();
49 feed(&mut h, node, &mut scope);
50 ContentHash(*h.finalize().as_bytes())
51}
52
53fn feed(h: &mut Hasher, node: &SemanticNode, scope: &mut Vec<String>) {
54 write_kind_and_field(h, node);
55
56 match node.kind.as_str() {
57 "function_item" | "closure_expression" => feed_callable(h, node, scope),
58 "block" => feed_block(h, node, scope),
59 "for_expression" => feed_for(h, node, scope),
60 "match_arm" => feed_match_arm(h, node, scope),
61 "identifier" if node.field_name.as_deref() == Some("pattern") => emit_binder_body(h),
62 "identifier" => emit_identifier_ref(h, node, scope),
63 _ => feed_default(h, node, scope),
64 }
65}
66
67fn feed_default(h: &mut Hasher, node: &SemanticNode, scope: &mut Vec<String>) {
68 emit_leaf_marker(h, node);
69 h.update(&(node.children.len() as u64).to_le_bytes());
70 for c in &node.children {
71 feed(h, c, scope);
72 }
73}
74
75fn emit_identifier_ref(h: &mut Hasher, node: &SemanticNode, scope: &Vec<String>) {
76 h.update(&[TAG_NO_LEAF]);
77 if let Some(t) = &node.leaf_text {
78 if let Ok(name) = std::str::from_utf8(t) {
79 if let Some(i) = scope.iter().rposition(|n| n == name) {
80 let de_bruijn = (scope.len() - 1 - i) as u64;
81 h.update(&[TAG_REF_BOUND]);
82 h.update(&de_bruijn.to_le_bytes());
83 } else {
84 h.update(&[TAG_REF_FREE]);
85 h.update(&(t.len() as u64).to_le_bytes());
86 h.update(t);
87 }
88 } else {
89 h.update(&[TAG_REF_FREE]);
90 h.update(&(t.len() as u64).to_le_bytes());
91 h.update(t);
92 }
93 } else {
94 h.update(&[TAG_REF_FREE]);
95 h.update(&[0u8; 8]);
96 }
97 h.update(&[0u8; 8]);
98}
99
100fn emit_binder_body(h: &mut Hasher) {
101 h.update(&[TAG_NO_LEAF]);
102 h.update(&[TAG_BINDER]);
103 h.update(&[0u8; 8]);
104}
105
106fn emit_binder_node(h: &mut Hasher, node: &SemanticNode) {
107 write_kind_and_field(h, node);
108 emit_binder_body(h);
109}
110
111fn emit_leaf_marker(h: &mut Hasher, node: &SemanticNode) {
112 match &node.leaf_text {
113 Some(t) => {
114 h.update(&[TAG_LEAF]);
115 h.update(&(t.len() as u64).to_le_bytes());
116 h.update(t);
117 }
118 None => {
119 h.update(&[TAG_NO_LEAF]);
120 }
121 }
122}
123
124fn feed_callable(h: &mut Hasher, node: &SemanticNode, scope: &mut Vec<String>) {
125 h.update(&[TAG_NO_LEAF]);
126
127 let mut binders: Vec<String> = Vec::new();
128 for c in &node.children {
129 if c.field_name.as_deref() == Some("parameters") {
130 collect_callable_binders(c, &mut binders);
131 }
132 }
133
134 let scope_before = scope.len();
135 scope.extend(binders);
136
137 h.update(&(node.children.len() as u64).to_le_bytes());
138 for c in &node.children {
139 if c.field_name.as_deref() == Some("parameters") {
140 feed_callable_params(h, c);
141 } else {
142 feed(h, c, scope);
143 }
144 }
145
146 scope.truncate(scope_before);
147}
148
149fn feed_block(h: &mut Hasher, node: &SemanticNode, scope: &mut Vec<String>) {
150 h.update(&[TAG_NO_LEAF]);
151
152 let scope_before = scope.len();
153 h.update(&(node.children.len() as u64).to_le_bytes());
154 for c in &node.children {
155 if c.kind == "let_declaration" {
156 feed_let(h, c, scope);
157 for cc in &c.children {
158 if cc.field_name.as_deref() == Some("pattern") {
159 collect_pattern_binders(cc, scope);
160 }
161 }
162 } else {
163 feed(h, c, scope);
164 }
165 }
166 scope.truncate(scope_before);
167}
168
169fn feed_let(h: &mut Hasher, node: &SemanticNode, scope: &mut Vec<String>) {
170 write_kind_and_field(h, node);
171 h.update(&[TAG_NO_LEAF]);
172 h.update(&(node.children.len() as u64).to_le_bytes());
173 for c in &node.children {
174 if c.field_name.as_deref() == Some("pattern") {
175 feed_pattern(h, c);
176 } else {
177 feed(h, c, scope);
178 }
179 }
180}
181
182fn feed_for(h: &mut Hasher, node: &SemanticNode, scope: &mut Vec<String>) {
183 h.update(&[TAG_NO_LEAF]);
184
185 let mut binders: Vec<String> = Vec::new();
186 for c in &node.children {
187 if c.field_name.as_deref() == Some("pattern") {
188 collect_pattern_binders(c, &mut binders);
189 }
190 }
191
192 h.update(&(node.children.len() as u64).to_le_bytes());
193 for c in &node.children {
194 match c.field_name.as_deref() {
195 Some("pattern") => feed_pattern(h, c),
196 Some("body") => {
197 let scope_before = scope.len();
198 scope.extend(binders.iter().cloned());
199 feed(h, c, scope);
200 scope.truncate(scope_before);
201 }
202 _ => feed(h, c, scope),
203 }
204 }
205}
206
207fn feed_match_arm(h: &mut Hasher, node: &SemanticNode, scope: &mut Vec<String>) {
208 h.update(&[TAG_NO_LEAF]);
209
210 let mut binders: Vec<String> = Vec::new();
211 for c in &node.children {
212 if c.field_name.as_deref() == Some("pattern") {
213 collect_match_pattern_binders(c, &mut binders);
214 }
215 }
216
217 let scope_before = scope.len();
218 scope.extend(binders);
219
220 h.update(&(node.children.len() as u64).to_le_bytes());
221 for c in &node.children {
222 if c.field_name.as_deref() == Some("pattern") {
223 if c.kind == "match_pattern" {
224 feed_match_pattern_split(h, c, scope);
225 } else {
226 feed_pattern(h, c);
227 }
228 } else {
229 feed(h, c, scope);
230 }
231 }
232
233 scope.truncate(scope_before);
234}
235
236fn feed_match_pattern_split(h: &mut Hasher, mp: &SemanticNode, scope: &mut Vec<String>) {
237 write_kind_and_field(h, mp);
238 emit_leaf_marker(h, mp);
239 h.update(&(mp.children.len() as u64).to_le_bytes());
240 for c in &mp.children {
241 if c.field_name.as_deref() == Some("condition") {
242 feed(h, c, scope);
243 } else {
244 feed_pattern(h, c);
245 }
246 }
247}
248
249fn collect_match_pattern_binders(p: &SemanticNode, out: &mut Vec<String>) {
250 if p.kind == "match_pattern" {
251 for c in &p.children {
252 if c.field_name.as_deref() != Some("condition") {
253 collect_pattern_binders(c, out);
254 }
255 }
256 } else {
257 collect_pattern_binders(p, out);
258 }
259}
260
261fn feed_callable_params(h: &mut Hasher, params: &SemanticNode) {
262 write_kind_and_field(h, params);
263 h.update(&[TAG_NO_LEAF]);
264 h.update(&(params.children.len() as u64).to_le_bytes());
265 for c in ¶ms.children {
266 match c.kind.as_str() {
267 "parameter" => feed_parameter(h, c),
268 _ => feed_pattern(h, c),
269 }
270 }
271}
272
273fn feed_parameter(h: &mut Hasher, node: &SemanticNode) {
274 write_kind_and_field(h, node);
275 h.update(&[TAG_NO_LEAF]);
276 h.update(&(node.children.len() as u64).to_le_bytes());
277 for c in &node.children {
278 if c.field_name.as_deref() == Some("pattern") {
279 feed_pattern(h, c);
280 } else {
281 feed_as_literal(h, c);
282 }
283 }
284}
285
286/// Pattern-aware emitter. Within a pattern, identifiers split into two
287/// roles: binders (introduce a new local) and constructors (variant or
288/// path references). The disambiguation rule mirrors Rust's: a `pattern`
289/// field forces binder; otherwise lowercase initial = binder, uppercase =
290/// constructor.
291fn feed_pattern(h: &mut Hasher, node: &SemanticNode) {
292 write_kind_and_field(h, node);
293 match node.kind.as_str() {
294 "identifier" => {
295 if is_binder_identifier(node) {
296 emit_binder_body(h);
297 } else {
298 emit_leaf_marker(h, node);
299 h.update(&[0u8; 8]);
300 }
301 }
302 "tuple_pattern" | "ref_pattern" | "reference_pattern" | "mut_pattern" | "slice_pattern" => {
303 h.update(&[TAG_NO_LEAF]);
304 h.update(&(node.children.len() as u64).to_le_bytes());
305 for c in &node.children {
306 feed_pattern(h, c);
307 }
308 }
309 "tuple_struct_pattern" => {
310 h.update(&[TAG_NO_LEAF]);
311 h.update(&(node.children.len() as u64).to_le_bytes());
312 for c in &node.children {
313 if c.field_name.as_deref() == Some("type") {
314 feed_as_literal(h, c);
315 } else {
316 feed_pattern(h, c);
317 }
318 }
319 }
320 "struct_pattern" => {
321 h.update(&[TAG_NO_LEAF]);
322 h.update(&(node.children.len() as u64).to_le_bytes());
323 for c in &node.children {
324 if c.field_name.as_deref() == Some("type") {
325 feed_as_literal(h, c);
326 } else if c.kind == "field_pattern" {
327 feed_field_pattern(h, c);
328 } else {
329 feed_as_literal(h, c);
330 }
331 }
332 }
333 "captured_pattern" => {
334 h.update(&[TAG_NO_LEAF]);
335 h.update(&(node.children.len() as u64).to_le_bytes());
336 let mut named_binder = false;
337 for c in &node.children {
338 if !named_binder && c.kind == "identifier" {
339 emit_binder_node(h, c);
340 named_binder = true;
341 } else {
342 feed_pattern(h, c);
343 }
344 }
345 }
346 _ => feed_as_literal(h, node),
347 }
348}
349
350fn feed_field_pattern(h: &mut Hasher, fp: &SemanticNode) {
351 write_kind_and_field(h, fp);
352 let has_pattern = fp
353 .children
354 .iter()
355 .any(|c| c.field_name.as_deref() == Some("pattern"));
356 h.update(&[TAG_NO_LEAF]);
357 h.update(&(fp.children.len() as u64).to_le_bytes());
358 for c in &fp.children {
359 if has_pattern {
360 if c.field_name.as_deref() == Some("pattern") {
361 feed_pattern(h, c);
362 } else {
363 feed_as_literal(h, c);
364 }
365 } else if matches!(
366 c.kind.as_str(),
367 "identifier" | "shorthand_field_identifier" | "field_identifier"
368 ) {
369 emit_binder_node(h, c);
370 } else {
371 feed_as_literal(h, c);
372 }
373 }
374}
375
376fn feed_as_literal(h: &mut Hasher, node: &SemanticNode) {
377 write_kind_and_field(h, node);
378 emit_leaf_marker(h, node);
379 h.update(&(node.children.len() as u64).to_le_bytes());
380 for c in &node.children {
381 feed_as_literal(h, c);
382 }
383}
384
385fn collect_callable_binders(params: &SemanticNode, out: &mut Vec<String>) {
386 for c in ¶ms.children {
387 match c.kind.as_str() {
388 "parameter" => {
389 for cc in &c.children {
390 if cc.field_name.as_deref() == Some("pattern") {
391 collect_pattern_binders(cc, out);
392 }
393 }
394 }
395 _ => collect_pattern_binders(c, out),
396 }
397 }
398}
399
400fn collect_pattern_binders(p: &SemanticNode, out: &mut Vec<String>) {
401 match p.kind.as_str() {
402 "identifier" => {
403 if is_binder_identifier(p) {
404 push_identifier_name(p, out);
405 }
406 }
407 "tuple_pattern" | "ref_pattern" | "reference_pattern" | "mut_pattern" | "slice_pattern" => {
408 for c in &p.children {
409 collect_pattern_binders(c, out);
410 }
411 }
412 "tuple_struct_pattern" => {
413 for c in &p.children {
414 if c.field_name.as_deref() != Some("type") {
415 collect_pattern_binders(c, out);
416 }
417 }
418 }
419 "struct_pattern" => {
420 for c in &p.children {
421 if c.kind == "field_pattern" {
422 collect_field_pattern_binders(c, out);
423 }
424 }
425 }
426 "captured_pattern" => {
427 let mut named_binder = false;
428 for c in &p.children {
429 if !named_binder && c.kind == "identifier" {
430 push_identifier_name(c, out);
431 named_binder = true;
432 } else {
433 collect_pattern_binders(c, out);
434 }
435 }
436 }
437 _ => {}
438 }
439}
440
441fn collect_field_pattern_binders(fp: &SemanticNode, out: &mut Vec<String>) {
442 let has_pattern = fp
443 .children
444 .iter()
445 .any(|c| c.field_name.as_deref() == Some("pattern"));
446 if has_pattern {
447 for c in &fp.children {
448 if c.field_name.as_deref() == Some("pattern") {
449 collect_pattern_binders(c, out);
450 }
451 }
452 } else {
453 for c in &fp.children {
454 if matches!(
455 c.kind.as_str(),
456 "identifier" | "shorthand_field_identifier" | "field_identifier"
457 ) {
458 push_identifier_name(c, out);
459 }
460 }
461 }
462}
463
464fn push_identifier_name(node: &SemanticNode, out: &mut Vec<String>) {
465 if let Some(t) = &node.leaf_text {
466 if let Ok(s) = std::str::from_utf8(t) {
467 out.push(s.to_string());
468 }
469 }
470}
471
472/// Determina si un `identifier` en posición de patrón se interpreta como
473/// binder. Reglas:
474/// - Si tiene `field_name == "pattern"` (parámetros, lets), siempre es binder.
475/// - Si su nombre comienza con minúscula, es binder.
476/// - Si comienza con `_` seguido de letra/dígito, es binder (convención
477/// Rust para "intencionalmente sin usar").
478/// - Resto: constructor / variante / constante (literal).
479fn is_binder_identifier(node: &SemanticNode) -> bool {
480 if node.field_name.as_deref() == Some("pattern") {
481 return true;
482 }
483 let Some(t) = &node.leaf_text else { return false };
484 let Ok(s) = std::str::from_utf8(t) else { return false };
485 is_binder_name(s)
486}
487
488fn is_binder_name(s: &str) -> bool {
489 let mut chars = s.chars();
490 match chars.next() {
491 Some('_') => chars
492 .next()
493 .map_or(false, |c| c.is_lowercase() || c.is_ascii_digit() || c == '_'),
494 Some(c) => c.is_lowercase(),
495 None => false,
496 }
497}
498
499fn write_kind_and_field(h: &mut Hasher, node: &SemanticNode) {
500 write_str(h, &node.kind);
501 match &node.field_name {
502 Some(f) => {
503 h.update(&[1]);
504 write_str(h, f);
505 }
506 None => {
507 h.update(&[0]);
508 }
509 }
510}
511
512fn write_str(h: &mut Hasher, s: &str) {
513 h.update(&(s.len() as u64).to_le_bytes());
514 h.update(s.as_bytes());
515}