Skip to main content

seqc/ast/
program.rs

1//! Program-level AST methods: word-call validation, auto-generated variant
2//! constructors (`Make-Variant`), and type fix-up for union types declared
3//! in stack effects.
4
5use crate::types::{Effect, StackType, Type};
6
7use super::{Program, SourceLocation, Statement, WordDef};
8
9/// Names of all runtime built-ins recognised by the validator.
10///
11/// IMPORTANT: Keep this in sync with codegen.rs WordCall matching.
12const BUILTINS: &[&str] = &[
13    // I/O operations
14    "io.write",
15    "io.write-line",
16    "io.read-line",
17    "io.read-n",
18    "int->string",
19    "symbol->string",
20    "string->symbol",
21    // Command-line arguments
22    "args.count",
23    "args.at",
24    // File operations
25    "file.slurp",
26    "file.exists?",
27    "file.for-each-line",
28    "file.spit",
29    "file.append",
30    "file.delete",
31    "file.size",
32    // Directory operations
33    "dir.exists?",
34    "dir.make",
35    "dir.delete",
36    "dir.list",
37    // String operations
38    "string.concat",
39    "string.length",
40    "string.byte-length",
41    "string.char-at",
42    "string.substring",
43    "char->string",
44    "string.find",
45    "string.split",
46    "string.contains",
47    "string.starts-with",
48    "string.empty?",
49    "string.trim",
50    "string.chomp",
51    "string.to-upper",
52    "string.to-lower",
53    "string.equal?",
54    "string.join",
55    "string.json-escape",
56    "string->int",
57    // Symbol operations
58    "symbol.=",
59    // Encoding operations
60    "encoding.base64-encode",
61    "encoding.base64-decode",
62    "encoding.base64url-encode",
63    "encoding.base64url-decode",
64    "encoding.hex-encode",
65    "encoding.hex-decode",
66    // Crypto operations
67    "crypto.sha256",
68    "crypto.hmac-sha256",
69    "crypto.constant-time-eq",
70    "crypto.random-bytes",
71    "crypto.random-int",
72    "crypto.uuid4",
73    "crypto.aes-gcm-encrypt",
74    "crypto.aes-gcm-decrypt",
75    "crypto.pbkdf2-sha256",
76    "crypto.ed25519-keypair",
77    "crypto.ed25519-sign",
78    "crypto.ed25519-verify",
79    // HTTP client operations
80    "net.http.get",
81    "net.http.post",
82    "net.http.put",
83    "net.http.delete",
84    // List operations
85    "list.make",
86    "list.push",
87    "list.get",
88    "list.set",
89    "list.map",
90    "list.filter",
91    "list.fold",
92    "list.each",
93    "list.length",
94    "list.empty?",
95    "list.reverse",
96    "list.first",
97    "list.last",
98    // Map operations
99    "map.make",
100    "map.get",
101    "map.set",
102    "map.has?",
103    "map.remove",
104    "map.keys",
105    "map.values",
106    "map.size",
107    "map.empty?",
108    "map.each",
109    "map.fold",
110    // Variant operations
111    "variant.field-count",
112    "variant.tag",
113    "variant.field-at",
114    "variant.append",
115    "variant.first",
116    "variant.last",
117    "variant.init",
118    "variant.make-0",
119    "variant.make-1",
120    "variant.make-2",
121    "variant.make-3",
122    "variant.make-4",
123    // SON wrap aliases
124    "wrap-0",
125    "wrap-1",
126    "wrap-2",
127    "wrap-3",
128    "wrap-4",
129    // Integer arithmetic operations
130    "i.add",
131    "i.subtract",
132    "i.multiply",
133    "i.divide",
134    "i.modulo",
135    "i.pow",
136    // Terse integer arithmetic
137    "i.+",
138    "i.-",
139    "i.*",
140    "i./",
141    "i.%",
142    // Integer comparison operations (return 0 or 1)
143    "i.=",
144    "i.<",
145    "i.>",
146    "i.<=",
147    "i.>=",
148    "i.<>",
149    // Integer comparison operations (verbose form)
150    "i.eq",
151    "i.lt",
152    "i.gt",
153    "i.lte",
154    "i.gte",
155    "i.neq",
156    // Stack operations (simple - no parameters)
157    "dup",
158    "drop",
159    "swap",
160    "over",
161    "rot",
162    "nip",
163    "tuck",
164    "2dup",
165    "3drop",
166    "pick",
167    "roll",
168    // Aux stack operations
169    ">aux",
170    "aux>",
171    // Boolean operations
172    "and",
173    "or",
174    "not",
175    // Bitwise operations
176    "band",
177    "bor",
178    "bxor",
179    "bnot",
180    "i.neg",
181    "negate",
182    // Arithmetic sugar (resolved to concrete ops by typechecker)
183    "+",
184    "-",
185    "*",
186    "/",
187    "%",
188    "=",
189    "<",
190    ">",
191    "<=",
192    ">=",
193    "<>",
194    "shl",
195    "shr",
196    "popcount",
197    "clz",
198    "ctz",
199    "int-bits",
200    // Channel operations
201    "chan.make",
202    "chan.send",
203    "chan.receive",
204    "chan.close",
205    "chan.yield",
206    // Quotation operations
207    "call",
208    // Dataflow combinators
209    "dip",
210    "keep",
211    "bi",
212    "if",
213    "strand.spawn",
214    "strand.weave",
215    "strand.resume",
216    "strand.weave-cancel",
217    "yield",
218    "cond",
219    // TCP operations
220    "net.tcp.listen",
221    "net.tcp.connect",
222    "net.tcp.accept",
223    "net.tcp.local-port",
224    "net.tcp.read",
225    "net.tcp.write",
226    "net.tcp.close",
227    // Socket <-> Int casts (FFI escape hatches)
228    "fd->socket",
229    "socket->fd",
230    // UDP operations
231    "net.udp.bind",
232    "net.udp.send-to",
233    "net.udp.receive-from",
234    "net.udp.close",
235    // DNS operations
236    "net.dns.resolve",
237    // TLS operations
238    "net.tls.client",
239    // OS operations
240    "os.getenv",
241    "os.home-dir",
242    "os.current-dir",
243    "os.path-exists",
244    "os.path-is-file",
245    "os.path-is-dir",
246    "os.path-join",
247    "os.path-parent",
248    "os.path-filename",
249    "os.exit",
250    "os.name",
251    "os.arch",
252    // Signal handling
253    "signal.trap",
254    "signal.received?",
255    "signal.pending?",
256    "signal.default",
257    "signal.ignore",
258    "signal.clear",
259    "signal.SIGINT",
260    "signal.SIGTERM",
261    "signal.SIGHUP",
262    "signal.SIGPIPE",
263    "signal.SIGUSR1",
264    "signal.SIGUSR2",
265    "signal.SIGCHLD",
266    "signal.SIGALRM",
267    "signal.SIGCONT",
268    // Terminal operations
269    "terminal.raw-mode",
270    "terminal.read-char",
271    "terminal.read-char?",
272    "terminal.width",
273    "terminal.height",
274    "terminal.flush",
275    // Float arithmetic operations (verbose form)
276    "f.add",
277    "f.subtract",
278    "f.multiply",
279    "f.divide",
280    // Float arithmetic operations (terse form)
281    "f.+",
282    "f.-",
283    "f.*",
284    "f./",
285    // Float comparison operations (symbol form)
286    "f.=",
287    "f.<",
288    "f.>",
289    "f.<=",
290    "f.>=",
291    "f.<>",
292    // Float comparison operations (verbose form)
293    "f.eq",
294    "f.lt",
295    "f.gt",
296    "f.lte",
297    "f.gte",
298    "f.neq",
299    // Float math — roots/powers
300    "f.sqrt",
301    "f.cbrt",
302    "f.pow",
303    // Float math — exp/log
304    "f.exp",
305    "f.ln",
306    "f.log10",
307    "f.log2",
308    // Float math — trig
309    "f.sin",
310    "f.cos",
311    "f.tan",
312    "f.asin",
313    "f.acos",
314    "f.atan",
315    "f.atan2",
316    // Float math — rounding
317    "f.floor",
318    "f.ceil",
319    "f.round",
320    "f.trunc",
321    // Float constants
322    "f.pi",
323    "f.e",
324    "f.tau",
325    // Type conversions
326    "int->float",
327    "float->int",
328    "float->string",
329    "string->float",
330    // Byte construction (binary protocol encoders)
331    "int.to-bytes-i32-be",
332    "float.to-bytes-f32-be",
333    // Test framework operations
334    "test.init",
335    "test.set-name",
336    "test.finish",
337    "test.has-failures",
338    "test.assert",
339    "test.assert-not",
340    "test.assert-eq",
341    "test.assert-eq-str",
342    "test.fail",
343    "test.pass-count",
344    "test.fail-count",
345    // Time operations
346    "time.now",
347    "time.nanos",
348    "time.sleep-ms",
349    // SON serialization
350    "son.dump",
351    "son.dump-pretty",
352    // Stack introspection (for REPL)
353    "stack.dump",
354    // Regex operations
355    "regex.match?",
356    "regex.find",
357    "regex.find-all",
358    "regex.replace",
359    "regex.replace-all",
360    "regex.captures",
361    "regex.split",
362    "regex.valid?",
363    // Compression operations
364    "compress.gzip",
365    "compress.gzip-level",
366    "compress.gunzip",
367    "compress.zstd",
368    "compress.zstd-level",
369    "compress.unzstd",
370];
371
372impl Program {
373    pub fn new() -> Self {
374        Program {
375            includes: Vec::new(),
376            unions: Vec::new(),
377            words: Vec::new(),
378        }
379    }
380
381    pub fn find_word(&self, name: &str) -> Option<&WordDef> {
382        self.words.iter().find(|w| w.name == name)
383    }
384
385    /// Validate that all word calls reference either a defined word or a built-in
386    pub fn validate_word_calls(&self) -> Result<(), String> {
387        self.validate_word_calls_with_externals(&[])
388    }
389
390    /// Validate that all word calls reference a defined word, built-in, or external word.
391    ///
392    /// The `external_words` parameter should contain names of words available from
393    /// external sources (e.g., included modules) that should be considered valid.
394    pub fn validate_word_calls_with_externals(
395        &self,
396        external_words: &[&str],
397    ) -> Result<(), String> {
398        for word in &self.words {
399            self.validate_statements(&word.body, &word.name, BUILTINS, external_words)?;
400        }
401
402        Ok(())
403    }
404
405    /// Helper to validate word calls in a list of statements (recursively)
406    fn validate_statements(
407        &self,
408        statements: &[Statement],
409        word_name: &str,
410        builtins: &[&str],
411        external_words: &[&str],
412    ) -> Result<(), String> {
413        for statement in statements {
414            match statement {
415                Statement::WordCall { name, .. } => {
416                    if builtins.contains(&name.as_str()) {
417                        continue;
418                    }
419                    if self.find_word(name).is_some() {
420                        continue;
421                    }
422                    if external_words.contains(&name.as_str()) {
423                        continue;
424                    }
425                    // v7.0 rename: pre-net.* networking names get a targeted
426                    // hint instead of the generic "did you misspell" message,
427                    // so the migration is obvious.
428                    if let Some(replacement) = v7_renamed_to(name) {
429                        return Err(format!(
430                            "'{}' was renamed to '{}' in v7.0 (called in word '{}'). \
431                             See docs/MIGRATION_7_0.md.",
432                            name, replacement, word_name
433                        ));
434                    }
435                    return Err(format!(
436                        "Undefined word '{}' called in word '{}'. \
437                         Did you forget to define it or misspell a built-in?",
438                        name, word_name
439                    ));
440                }
441                Statement::If {
442                    then_branch,
443                    else_branch,
444                    span: _,
445                } => {
446                    self.validate_statements(then_branch, word_name, builtins, external_words)?;
447                    if let Some(eb) = else_branch {
448                        self.validate_statements(eb, word_name, builtins, external_words)?;
449                    }
450                }
451                Statement::Quotation { body, .. } => {
452                    self.validate_statements(body, word_name, builtins, external_words)?;
453                }
454                Statement::Match { arms, span: _ } => {
455                    for arm in arms {
456                        self.validate_statements(&arm.body, word_name, builtins, external_words)?;
457                    }
458                }
459                _ => {} // Literals don't need validation
460            }
461        }
462        Ok(())
463    }
464
465    /// All word names called anywhere in the program — inside
466    /// quotations, if/match branches, and words not reachable from
467    /// `main` included. Conservative by design: drives runtime archive
468    /// selection (see docs/design/RUNTIME_CAPABILITY_LINKING.md), where
469    /// a missed capability word would produce a binary that panics at
470    /// runtime, so over-reporting is safe and under-reporting is not.
471    pub fn referenced_word_calls(&self) -> Vec<&str> {
472        let mut out = Vec::new();
473        for word in &self.words {
474            self.collect_word_calls(&word.body, &mut out);
475        }
476        out
477    }
478
479    fn collect_word_calls<'a>(&'a self, statements: &'a [Statement], out: &mut Vec<&'a str>) {
480        for statement in statements {
481            match statement {
482                Statement::WordCall { name, .. } => out.push(name.as_str()),
483                Statement::If {
484                    then_branch,
485                    else_branch,
486                    span: _,
487                } => {
488                    self.collect_word_calls(then_branch, out);
489                    if let Some(eb) = else_branch {
490                        self.collect_word_calls(eb, out);
491                    }
492                }
493                Statement::Quotation { body, .. } => {
494                    self.collect_word_calls(body, out);
495                }
496                Statement::Match { arms, span: _ } => {
497                    for arm in arms {
498                        self.collect_word_calls(&arm.body, out);
499                    }
500                }
501                _ => {}
502            }
503        }
504    }
505
506    /// Maximum number of fields a variant can have (limited by runtime support)
507    const MAX_VARIANT_FIELDS: usize = 12;
508
509    /// Generate helper words for union types:
510    /// 1. Constructors: `Make-VariantName` - creates variant instances
511    /// 2. Predicates: `is-VariantName?` - tests if value is a specific variant
512    /// 3. Accessors: `VariantName-fieldname` - extracts field values (RFC #345)
513    ///
514    /// Example: For `union Message { Get { chan: Int } }`
515    /// Generates:
516    ///   `: Make-Get ( Int -- Message ) :Get variant.make-1 ;`
517    ///   `: is-Get? ( Message -- Bool ) variant.tag :Get symbol.= ;`
518    ///   `: Get-chan ( Message -- Int ) 0 variant.field-at ;`
519    ///
520    /// Returns an error if any variant exceeds the maximum field count.
521    pub fn generate_constructors(&mut self) -> Result<(), String> {
522        let mut new_words = Vec::new();
523
524        for union_def in &self.unions {
525            for variant in &union_def.variants {
526                let field_count = variant.fields.len();
527
528                // Check field count limit before generating constructor
529                if field_count > Self::MAX_VARIANT_FIELDS {
530                    return Err(format!(
531                        "Variant '{}' in union '{}' has {} fields, but the maximum is {}. \
532                         Consider grouping fields into nested union types.",
533                        variant.name,
534                        union_def.name,
535                        field_count,
536                        Self::MAX_VARIANT_FIELDS
537                    ));
538                }
539
540                let union_ty = Type::Union(union_def.name.clone());
541                let source = variant.source.clone();
542                let field_types: Vec<Type> = variant
543                    .fields
544                    .iter()
545                    .map(|f| parse_type_name(&f.type_name))
546                    .collect();
547
548                // 1. Constructor: Make-VariantName ( field_types -- UnionType )
549                new_words.push(make_helper_word(
550                    format!("Make-{}", variant.name),
551                    &field_types,
552                    union_ty.clone(),
553                    vec![
554                        Statement::Symbol(variant.name.clone()),
555                        Statement::WordCall {
556                            name: format!("variant.make-{}", field_count),
557                            span: None,
558                        },
559                    ],
560                    source.clone(),
561                ));
562
563                // 2. Predicate: is-VariantName? ( UnionType -- Bool )
564                new_words.push(make_helper_word(
565                    format!("is-{}?", variant.name),
566                    std::slice::from_ref(&union_ty),
567                    Type::Bool,
568                    vec![
569                        Statement::WordCall {
570                            name: "variant.tag".to_string(),
571                            span: None,
572                        },
573                        Statement::Symbol(variant.name.clone()),
574                        Statement::WordCall {
575                            name: "symbol.=".to_string(),
576                            span: None,
577                        },
578                    ],
579                    source.clone(),
580                ));
581
582                // 3. Field accessors: VariantName-fieldname ( UnionType -- FieldType )
583                for (index, field) in variant.fields.iter().enumerate() {
584                    new_words.push(make_helper_word(
585                        format!("{}-{}", variant.name, field.name),
586                        std::slice::from_ref(&union_ty),
587                        field_types[index].clone(),
588                        vec![
589                            Statement::IntLiteral(index as i64),
590                            Statement::WordCall {
591                                name: "variant.field-at".to_string(),
592                                span: None,
593                            },
594                        ],
595                        source.clone(),
596                    ));
597                }
598            }
599        }
600
601        self.words.extend(new_words);
602        Ok(())
603    }
604
605    /// RFC #345: Fix up type variables in stack effects that should be union types
606    ///
607    /// When parsing files with includes, type variables like "Message" in
608    /// `( Message -- Int )` may be parsed as `Type::Var("Message")` if the
609    /// union definition is in an included file. After resolving includes,
610    /// we know all union names and can convert these to `Type::Union("Message")`.
611    ///
612    /// This ensures proper nominal type checking for union types across files.
613    pub fn fixup_union_types(&mut self) {
614        let union_names: std::collections::HashSet<String> =
615            self.unions.iter().map(|u| u.name.clone()).collect();
616
617        for word in &mut self.words {
618            if let Some(ref mut effect) = word.effect {
619                Self::fixup_stack_type(&mut effect.inputs, &union_names);
620                Self::fixup_stack_type(&mut effect.outputs, &union_names);
621            }
622        }
623    }
624
625    /// Recursively fix up types in a stack type
626    fn fixup_stack_type(stack: &mut StackType, union_names: &std::collections::HashSet<String>) {
627        match stack {
628            StackType::Empty | StackType::RowVar(_) => {}
629            StackType::Cons { rest, top } => {
630                Self::fixup_type(top, union_names);
631                Self::fixup_stack_type(rest, union_names);
632            }
633        }
634    }
635
636    /// Fix up a single type, converting Type::Var to Type::Union if it matches a union name
637    fn fixup_type(ty: &mut Type, union_names: &std::collections::HashSet<String>) {
638        match ty {
639            Type::Var(name) if union_names.contains(name) => {
640                *ty = Type::Union(name.clone());
641            }
642            Type::Quotation(effect) => {
643                Self::fixup_stack_type(&mut effect.inputs, union_names);
644                Self::fixup_stack_type(&mut effect.outputs, union_names);
645            }
646            Type::Closure { effect, captures } => {
647                Self::fixup_stack_type(&mut effect.inputs, union_names);
648                Self::fixup_stack_type(&mut effect.outputs, union_names);
649                for cap in captures {
650                    Self::fixup_type(cap, union_names);
651                }
652            }
653            _ => {}
654        }
655    }
656}
657
658impl Default for Program {
659    fn default() -> Self {
660        Self::new()
661    }
662}
663
664/// Build a generated helper `WordDef` whose effect is
665/// `( ..a inputs -- ..a output )`. Used to emit the constructor /
666/// predicate / accessor words for each union variant.
667fn make_helper_word(
668    name: String,
669    inputs: &[Type],
670    output: Type,
671    body: Vec<Statement>,
672    source: Option<SourceLocation>,
673) -> WordDef {
674    let mut input_stack = StackType::RowVar("a".to_string());
675    for ty in inputs {
676        input_stack = input_stack.push(ty.clone());
677    }
678    let output_stack = StackType::RowVar("a".to_string()).push(output);
679    WordDef {
680        name,
681        effect: Some(Effect::new(input_stack, output_stack)),
682        body,
683        source,
684        allowed_lints: vec![],
685    }
686}
687
688/// Parse a type name string into a Type
689/// Used by constructor generation to build stack effects
690fn parse_type_name(name: &str) -> Type {
691    match name {
692        "Int" => Type::Int,
693        "Float" => Type::Float,
694        "Bool" => Type::Bool,
695        "String" => Type::String,
696        "Channel" => Type::Channel,
697        "Socket" => Type::Socket,
698        other => Type::Union(other.to_string()),
699    }
700}
701
702/// Map a pre-v7.0 networking word to its current name, or None if unknown.
703/// Used to turn the generic "Undefined word" error into a targeted migration
704/// hint when a user calls one of the renamed builtins. Remove this table
705/// in v8.0.
706fn v7_renamed_to(name: &str) -> Option<&'static str> {
707    Some(match name {
708        "tcp.listen" => "net.tcp.listen",
709        "tcp.accept" => "net.tcp.accept",
710        "tcp.read" => "net.tcp.read",
711        "tcp.write" => "net.tcp.write",
712        "tcp.close" => "net.tcp.close",
713        "udp.bind" => "net.udp.bind",
714        "udp.send-to" => "net.udp.send-to",
715        "udp.receive-from" => "net.udp.receive-from",
716        "udp.close" => "net.udp.close",
717        "http.get" => "net.http.get",
718        "http.post" => "net.http.post",
719        "http.put" => "net.http.put",
720        "http.delete" => "net.http.delete",
721        // imath stdlib pass-through removed in v7.0; route to the underlying
722        // builtin so callers learn the right name.
723        "mod" => "i.modulo",
724        _ => return None,
725    })
726}