Skip to main content

vihaco_module/
program_header.rs

1// SPDX-FileCopyrightText: 2026 The vihaco Authors
2// SPDX-License-Identifier: MIT
3
4//! The standard SST header: flat, assembler-style directives that name things
5//! by symbol, assembled into [`ProgramMetadata`].
6//!
7//! ```text
8//! .header
9//!     .file "loadable.sst"
10//!     .func @helper() -> u64, locals 0
11//!     .func @main(x: u64) -> (u64, bool), locals 2
12//!     .entry @main
13//!     .const u64 42
14//!     .const str "hello"
15//!     .const fn @helper
16//!     .source_symbol 12 "user"
17//! ```
18//!
19//! [`ProgramHeader`] documents how the directives become tables.
20
21use std::collections::HashMap;
22use std::fmt;
23
24use chumsky::error::Simple;
25use chumsky::extra;
26use chumsky::prelude::*;
27use vihaco_abi::{Type, Value};
28use vihaco_parser::{Parse, Print, QuotedString, print_quoted, trivia};
29
30use crate::module::{FunctionDecl, Parameter, ProgramMetadata, Signature, SourceSymbolInfo};
31
32type E<'src> = extra::Err<Simple<'src, char>>;
33
34/// Characters allowed in a symbol or parameter name.
35fn name_char(c: char) -> bool {
36    !c.is_whitespace()
37        && !matches!(
38            c,
39            ':' | '@' | ',' | ';' | '(' | ')' | '{' | '}' | '[' | ']' | '"' | '\'' | '`'
40        )
41}
42
43fn name<'src>() -> impl Parser<'src, &'src str, String, E<'src>> + Clone {
44    any()
45        .filter(|c: &char| name_char(*c))
46        .repeated()
47        .at_least(1)
48        .collect::<String>()
49}
50
51fn print_name(text: &str, out: &mut dyn fmt::Write) -> fmt::Result {
52    // A name that starts like an arrow or a number is still a valid name;
53    // only the characters matter.
54    if text.is_empty() || !text.chars().all(name_char) {
55        return Err(fmt::Error);
56    }
57    out.write_str(text)
58}
59
60/// `( item, item, ... )` with trivia (and so line breaks) inside.
61fn parenthesized<'src, T>(
62    item: impl Parser<'src, &'src str, T, E<'src>>,
63) -> impl Parser<'src, &'src str, Vec<T>, E<'src>> {
64    item.separated_by(just(',').then(trivia()))
65        .allow_trailing()
66        .collect::<Vec<_>>()
67        .delimited_by(just('(').then(trivia()), just(')'))
68}
69
70/// A value that can live in the constant pool of a standard header.
71///
72/// `.const str "text"` and `.const fn @name` are assembled through
73/// [`string`](Self::string) and [`function`](Self::function); a value model
74/// without string or function constants returns `None` and such directives
75/// are rejected. [`string_index`](Self::string_index) and
76/// [`function_index`](Self::function_index) report the table references of
77/// a value, so that a hand-written index such as `.const str 3` is rejected
78/// and tools can explain constants.
79pub trait ConstantValue: Sized {
80    /// The constant for `strings[index]`.
81    fn string(index: u32) -> Option<Self> {
82        let _ = index;
83        None
84    }
85
86    /// The constant for `functions[index]`.
87    fn function(index: u32) -> Option<Self> {
88        let _ = index;
89        None
90    }
91
92    /// The `strings` index this constant refers to, if any.
93    fn string_index(&self) -> Option<u32> {
94        None
95    }
96
97    /// The `functions` index this constant refers to, if any.
98    fn function_index(&self) -> Option<u32> {
99        None
100    }
101}
102
103impl ConstantValue for Value {
104    fn string(index: u32) -> Option<Self> {
105        Some(Value::String(index))
106    }
107
108    fn function(index: u32) -> Option<Self> {
109        Some(Value::FunctionRef(index))
110    }
111
112    fn string_index(&self) -> Option<u32> {
113        match self {
114            Value::String(index) => Some(*index),
115            _ => None,
116        }
117    }
118
119    fn function_index(&self) -> Option<u32> {
120        match self {
121            Value::FunctionRef(index) => Some(*index),
122            _ => None,
123        }
124    }
125}
126
127/// `.func @name(param: type, ...) -> ret, locals N`.
128#[derive(Debug, Clone, PartialEq)]
129pub struct FunctionDirective<Ty = Type> {
130    /// The function's name, without `@`. It must match an `@name:` symbol in
131    /// `.text`.
132    pub name: String,
133    /// Parameter names and types, in order.
134    pub params: Vec<(String, Ty)>,
135    /// Return types: none (`-> ...` omitted), one (`-> u64`), or several
136    /// (`-> (u64, bool)`).
137    pub ret: Vec<Ty>,
138    /// Reserved local slots, including parameters.
139    pub locals: u32,
140}
141
142/// The value of a `.const` directive.
143#[derive(Debug, Clone, PartialEq)]
144pub enum ConstantDirective<V = Value> {
145    /// `.const str "text"`: a string constant, interned in the string table.
146    Str(String),
147    /// `.const fn @name`: a reference to the function declared by
148    /// `.func @name`.
149    Function(String),
150    /// `.const <value>` in the value type's own syntax, such as `u64 42`.
151    Value(V),
152}
153
154/// One standard header directive.
155#[derive(Debug, Clone, PartialEq)]
156pub enum ProgramDirective<V = Value, Ty = Type> {
157    /// `.file "path"`: the file of the `.func` directives that follow.
158    File(String),
159    /// `.func @name(...) -> ..., locals N`: a function declaration.
160    Function(FunctionDirective<Ty>),
161    /// `.entry @name`: the entry function.
162    Entry(String),
163    /// `.const <value>`: the next constant-pool entry.
164    Const(ConstantDirective<V>),
165    /// `.source_symbol <index> "<name>"`: a source-level symbol.
166    SourceSymbol(SourceSymbolInfo),
167}
168
169impl<'src, V, Ty> Parse<'src> for ProgramDirective<V, Ty>
170where
171    V: Parse<'src> + 'src,
172    Ty: Parse<'src> + 'src,
173{
174    fn parser() -> impl Parser<'src, &'src str, Self, E<'src>> {
175        let space = one_of(" \t").repeated().at_least(1);
176        let gap = one_of(" \t").repeated();
177        let symbol = just('@').ignore_then(name());
178        let keyword = |word: &'static str| just(word).then(space);
179
180        let file = keyword(".file")
181            .ignore_then(QuotedString::parser())
182            .map(|path| ProgramDirective::File(path.into_inner()));
183
184        let ty = || Ty::parser().padded_by(trivia());
185        let param = name().padded_by(trivia()).then_ignore(just(':')).then(ty());
186        let ret = gap
187            .ignore_then(just("->"))
188            .ignore_then(gap)
189            .ignore_then(choice((
190                parenthesized(ty()),
191                Ty::parser().map(|ty| vec![ty]),
192            )))
193            .or_not()
194            .map(Option::unwrap_or_default);
195        let function = keyword(".func")
196            .ignore_then(symbol.clone())
197            .then(parenthesized(param))
198            .then(ret)
199            .then_ignore(gap)
200            .then_ignore(just(','))
201            .then_ignore(gap)
202            .then_ignore(keyword("locals"))
203            .then(u32::parser())
204            .map(|(((name, params), ret), locals)| {
205                ProgramDirective::Function(FunctionDirective {
206                    name,
207                    params,
208                    ret,
209                    locals,
210                })
211            });
212
213        let entry = keyword(".entry")
214            .ignore_then(symbol.clone())
215            .map(ProgramDirective::Entry);
216
217        let constant = keyword(".const")
218            .ignore_then(choice((
219                keyword("str")
220                    .ignore_then(QuotedString::parser())
221                    .map(|text| ConstantDirective::Str(text.into_inner())),
222                keyword("fn")
223                    .ignore_then(symbol)
224                    .map(ConstantDirective::Function),
225                V::parser().map(ConstantDirective::Value),
226            )))
227            .map(ProgramDirective::Const);
228
229        let source_symbol = keyword(".source_symbol")
230            .ignore_then(u32::parser())
231            .then_ignore(space)
232            .then(QuotedString::parser())
233            .map(|(index, name)| {
234                ProgramDirective::SourceSymbol(SourceSymbolInfo {
235                    index,
236                    name: name.into_inner(),
237                })
238            });
239
240        choice((file, function, entry, constant, source_symbol))
241    }
242}
243
244impl<V: Print, Ty: Print> Print for ProgramDirective<V, Ty> {
245    fn print(&self, out: &mut dyn fmt::Write) -> fmt::Result {
246        match self {
247            ProgramDirective::File(path) => {
248                out.write_str(".file ")?;
249                print_quoted(path, out)
250            }
251            ProgramDirective::Function(function) => {
252                out.write_str(".func @")?;
253                print_name(&function.name, out)?;
254                out.write_char('(')?;
255                for (index, (name, ty)) in function.params.iter().enumerate() {
256                    if index > 0 {
257                        out.write_str(", ")?;
258                    }
259                    print_name(name, out)?;
260                    out.write_str(": ")?;
261                    ty.print(out)?;
262                }
263                out.write_char(')')?;
264                match function.ret.as_slice() {
265                    [] => {}
266                    [ty] => {
267                        out.write_str(" -> ")?;
268                        ty.print(out)?;
269                    }
270                    types => {
271                        out.write_str(" -> (")?;
272                        for (index, ty) in types.iter().enumerate() {
273                            if index > 0 {
274                                out.write_str(", ")?;
275                            }
276                            ty.print(out)?;
277                        }
278                        out.write_char(')')?;
279                    }
280                }
281                write!(out, ", locals {}", function.locals)
282            }
283            ProgramDirective::Entry(name) => {
284                out.write_str(".entry @")?;
285                print_name(name, out)
286            }
287            ProgramDirective::Const(constant) => {
288                out.write_str(".const ")?;
289                match constant {
290                    ConstantDirective::Str(text) => {
291                        out.write_str("str ")?;
292                        print_quoted(text, out)
293                    }
294                    ConstantDirective::Function(name) => {
295                        out.write_str("fn @")?;
296                        print_name(name, out)
297                    }
298                    ConstantDirective::Value(value) => {
299                        let mut text = String::new();
300                        value.print(&mut text)?;
301                        // A value spelled like the string or function forms
302                        // would be read back as them.
303                        if text.starts_with("str \"") || text.starts_with("fn @") {
304                            return Err(fmt::Error);
305                        }
306                        out.write_str(&text)
307                    }
308                }
309            }
310            ProgramDirective::SourceSymbol(symbol) => {
311                write!(out, ".source_symbol {} ", symbol.index)?;
312                print_quoted(&symbol.name, out)
313            }
314        }
315    }
316}
317
318/// A header declaration that may be a standard directive.
319///
320/// Implemented by [`ProgramDirective`] itself. An application declaration
321/// enum implements it by returning its standard variant, so that checkers,
322/// formatters, and loaders can find the standard directives among the
323/// application's own:
324///
325/// ```
326/// use vihaco_module::module::{ProgramDirective, StandardDirective};
327///
328/// enum Declaration {
329///     Standard(ProgramDirective),
330///     Description(String),
331/// }
332///
333/// impl StandardDirective for Declaration {
334///     type Value = vihaco_abi::Value;
335///     type Type = vihaco_abi::Type;
336///
337///     fn as_standard(&self) -> Option<&ProgramDirective> {
338///         match self {
339///             Self::Standard(directive) => Some(directive),
340///             Self::Description(_) => None,
341///         }
342///     }
343/// }
344/// ```
345pub trait StandardDirective {
346    type Value;
347    type Type;
348
349    fn as_standard(&self) -> Option<&ProgramDirective<Self::Value, Self::Type>>;
350}
351
352impl<V, Ty> StandardDirective for ProgramDirective<V, Ty> {
353    type Value = V;
354    type Type = Ty;
355
356    fn as_standard(&self) -> Option<&ProgramDirective<V, Ty>> {
357        Some(self)
358    }
359}
360
361/// Which part of a directive a [`HeaderError`] is about, so tools can point
362/// at it precisely.
363#[derive(Debug, Clone, Copy, PartialEq, Eq)]
364pub enum Focus {
365    /// The whole directive.
366    Directive,
367    /// The `@name` in the directive.
368    Symbol,
369    /// The `locals N` part of a `.func`.
370    Locals,
371    /// Everything after the directive keyword.
372    Argument,
373}
374
375/// A problem found while assembling a [`ProgramHeader`].
376#[derive(Debug, Clone, PartialEq, Eq)]
377pub struct HeaderError {
378    /// The position of the offending directive among the pushed directives.
379    pub directive: usize,
380    pub focus: Focus,
381    pub message: String,
382    /// A short annotation for the focused text.
383    pub label: String,
384    /// An earlier directive the problem relates to, such as the first
385    /// declaration of a duplicated function.
386    pub related: Option<(usize, Focus, String)>,
387}
388
389impl fmt::Display for HeaderError {
390    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
391        f.write_str(&self.message)
392    }
393}
394
395impl std::error::Error for HeaderError {}
396
397/// Standard header directives in header order, assembled into
398/// [`ProgramMetadata`].
399///
400/// No table index is written by hand. This collects directives
401/// in header order and derives every table:
402///
403/// - **functions**: one per `.func`, in `.func` order. A `.func` belongs to
404///   the file named by the closest `.file` before it, or to the empty file
405///   `""` if there is none.
406/// - **entry**: `.entry @name` selects the function declared by
407///   `.func @name`. It is optional and may appear at most once.
408/// - **constants**: one per `.const`, in `.const` order. `.const str "text"`
409///   is a string constant and `.const fn @name` a function reference; other
410///   values use the value type's own syntax, such as `u64 42`.
411/// - **source symbols**: one per `.source_symbol <index> "<name>"`; indices
412///   are unique.
413/// - **strings**: each distinct string once, at its first occurrence, in this
414///   order: function names in `.func` order, then parameter names (by
415///   function, then by position), then file names in `.func` order, then
416///   `.const str` literals in `.const` order. Lowering then appends the
417///   string literals of `.text` in address order
418///   (`MetadataLoweringContext` interns them), so the same file always
419///   produces the same table.
420///
421/// Application directives compose with these in one header: an application
422/// declaration enum has a variant holding a [`ProgramDirective`] (usually
423/// with `#[pattern = "$0"]`) and implements [`StandardDirective`]; a loader
424/// pushes the standard directives into a [`ProgramHeader`] and handles the
425/// others itself.
426///
427/// ```
428/// use vihaco_module::module::{NoInfo, ProgramHeader};
429/// use vihaco_parser::Parse;
430/// use chumsky::Parser;
431///
432/// let header: ProgramHeader = [".file \"a.sst\"", ".func @main() -> u64, locals 0", ".entry @main"]
433///     .into_iter()
434///     .map(|line| vihaco_module::module::ProgramDirective::parser().parse(line).into_result().unwrap())
435///     .collect();
436/// let metadata = header.finish(NoInfo).unwrap();
437/// assert_eq!(metadata.strings, ["main", "a.sst"]);
438/// assert_eq!(metadata.main_function, Some(0));
439/// ```
440#[derive(Debug, Clone, PartialEq)]
441pub struct ProgramHeader<V = Value, Ty = Type> {
442    directives: Vec<ProgramDirective<V, Ty>>,
443}
444
445impl<V, Ty> Default for ProgramHeader<V, Ty> {
446    fn default() -> Self {
447        Self {
448            directives: Vec::new(),
449        }
450    }
451}
452
453impl<V, Ty> FromIterator<ProgramDirective<V, Ty>> for ProgramHeader<V, Ty> {
454    fn from_iter<T: IntoIterator<Item = ProgramDirective<V, Ty>>>(iter: T) -> Self {
455        Self {
456            directives: iter.into_iter().collect(),
457        }
458    }
459}
460
461impl<V, Ty> Extend<ProgramDirective<V, Ty>> for ProgramHeader<V, Ty> {
462    fn extend<T: IntoIterator<Item = ProgramDirective<V, Ty>>>(&mut self, iter: T) {
463        self.directives.extend(iter);
464    }
465}
466
467/// Strings in first-occurrence order.
468#[derive(Default)]
469struct Interner {
470    strings: Vec<String>,
471    index: HashMap<String, u32>,
472}
473
474impl Interner {
475    fn intern(&mut self, text: &str) -> u32 {
476        if let Some(&index) = self.index.get(text) {
477            return index;
478        }
479        let index = self.strings.len() as u32;
480        self.strings.push(text.to_owned());
481        self.index.insert(text.to_owned(), index);
482        index
483    }
484}
485
486impl<V, Ty> ProgramHeader<V, Ty> {
487    pub fn new() -> Self {
488        Self::default()
489    }
490
491    /// Append the next directive.
492    pub fn push(&mut self, directive: ProgramDirective<V, Ty>) {
493        self.directives.push(directive);
494    }
495
496    /// The directives pushed so far, in order.
497    pub fn directives(&self) -> &[ProgramDirective<V, Ty>] {
498        &self.directives
499    }
500
501    /// Assemble the tables, reporting every problem.
502    ///
503    /// Problems are duplicate `.func` names, `locals` smaller than the
504    /// parameter count, more than one `.entry`, an `.entry` or `.const fn`
505    /// naming no `.func`, a constant written as a table index (`.const str 3`
506    /// or `.const fn 0`), string or function constants the value model cannot
507    /// represent, and duplicate `.source_symbol` indices. Whether each
508    /// function has an `@name:` symbol is checked when the metadata is bound
509    /// to `.text` ([`ProgramMetadata::validate`]).
510    pub fn assemble<Info>(
511        self,
512        extra: Info,
513    ) -> Result<ProgramMetadata<V, Ty, Info>, Vec<HeaderError>>
514    where
515        V: ConstantValue,
516    {
517        let mut errors = Vec::new();
518        let error = |directive, focus, message: String, label: &str| HeaderError {
519            directive,
520            focus,
521            message,
522            label: label.to_owned(),
523            related: None,
524        };
525
526        let mut file = None::<String>;
527        let mut functions = Vec::new();
528        let mut entries = Vec::new();
529        let mut constants = Vec::new();
530        let mut source_symbols = Vec::new();
531        for (position, directive) in self.directives.into_iter().enumerate() {
532            match directive {
533                ProgramDirective::File(path) => file = Some(path),
534                ProgramDirective::Function(function) => {
535                    functions.push((position, function, file.clone().unwrap_or_default()))
536                }
537                ProgramDirective::Entry(name) => entries.push((position, name)),
538                ProgramDirective::Const(constant) => constants.push((position, constant)),
539                ProgramDirective::SourceSymbol(symbol) => source_symbols.push((position, symbol)),
540            }
541        }
542
543        let mut by_name = HashMap::new();
544        let mut duplicates = Vec::new();
545        for (index, (position, function, _)) in functions.iter().enumerate() {
546            if let Some(&(first, _)) = by_name.get(function.name.as_str()) {
547                duplicates.push(HeaderError {
548                    directive: *position,
549                    focus: Focus::Symbol,
550                    message: format!("function `@{}` is declared more than once", function.name),
551                    label: "declared again here".to_owned(),
552                    related: Some((first, Focus::Symbol, "first declared here".to_owned())),
553                });
554            } else {
555                by_name.insert(function.name.as_str(), (*position, index as u32));
556            }
557            if (function.locals as usize) < function.params.len() {
558                errors.push(error(
559                    *position,
560                    Focus::Locals,
561                    format!(
562                        "`@{}` reserves {} local slots but has {} parameters",
563                        function.name,
564                        function.locals,
565                        function.params.len()
566                    ),
567                    &format!("must be at least {}", function.params.len()),
568                ));
569            }
570        }
571
572        let mut main_function = None;
573        for (count, (position, name)) in entries.iter().enumerate() {
574            if count > 0 {
575                errors.push(HeaderError {
576                    directive: *position,
577                    focus: Focus::Directive,
578                    message: "the entry function is selected more than once".to_owned(),
579                    label: "second `.entry`".to_owned(),
580                    related: Some((entries[0].0, Focus::Directive, "first `.entry`".to_owned())),
581                });
582                continue;
583            }
584            match by_name.get(name.as_str()) {
585                Some(&(_, index)) => main_function = Some(index),
586                None => errors.push(HeaderError {
587                    directive: *position,
588                    focus: Focus::Symbol,
589                    message: format!("`.entry @{name}` names no `.func` directive"),
590                    label: "no such function".to_owned(),
591                    related: None,
592                }),
593            }
594        }
595        errors.extend(duplicates);
596
597        // The string table: names, then parameters, then files, then string
598        // constants; each string once, at its first occurrence.
599        let mut strings = Interner::default();
600        let names: Vec<u32> = functions
601            .iter()
602            .map(|(_, function, _)| strings.intern(&function.name))
603            .collect();
604        let params: Vec<Vec<u32>> = functions
605            .iter()
606            .map(|(_, function, _)| {
607                function
608                    .params
609                    .iter()
610                    .map(|(name, _)| strings.intern(name))
611                    .collect()
612            })
613            .collect();
614        let files: Vec<u32> = functions
615            .iter()
616            .map(|(_, _, file)| strings.intern(file))
617            .collect();
618
619        let mut pool = Vec::with_capacity(constants.len());
620        for (position, constant) in constants {
621            let value = match constant {
622                ConstantDirective::Str(text) => {
623                    let index = strings.intern(&text);
624                    V::string(index).ok_or((
625                        Focus::Argument,
626                        "this value model has no string constants".to_owned(),
627                        "not representable",
628                    ))
629                }
630                ConstantDirective::Function(name) => match by_name.get(name.as_str()) {
631                    Some(&(_, index)) => V::function(index).ok_or((
632                        Focus::Argument,
633                        "this value model has no function constants".to_owned(),
634                        "not representable",
635                    )),
636                    None => Err((
637                        Focus::Symbol,
638                        format!("`.const fn @{name}` names no `.func` directive"),
639                        "no such function",
640                    )),
641                },
642                ConstantDirective::Value(value) => {
643                    if value.string_index().is_some() {
644                        Err((
645                            Focus::Argument,
646                            "string constants name their text: write `.const str \"...\"`"
647                                .to_owned(),
648                            "table index written by hand",
649                        ))
650                    } else if value.function_index().is_some() {
651                        Err((
652                            Focus::Argument,
653                            "function constants name their function: write `.const fn @name`"
654                                .to_owned(),
655                            "table index written by hand",
656                        ))
657                    } else {
658                        Ok(value)
659                    }
660                }
661            };
662            match value {
663                Ok(value) => pool.push(value),
664                Err((focus, message, label)) => errors.push(error(position, focus, message, label)),
665            }
666        }
667
668        let mut seen = HashMap::new();
669        let mut symbols = Vec::with_capacity(source_symbols.len());
670        for (position, symbol) in source_symbols {
671            if let Some(&first) = seen.get(&symbol.index) {
672                errors.push(HeaderError {
673                    directive: position,
674                    focus: Focus::Argument,
675                    message: format!("duplicate source symbol index {}", symbol.index),
676                    label: "used again here".to_owned(),
677                    related: Some((first, Focus::Argument, "first used here".to_owned())),
678                });
679            } else {
680                seen.insert(symbol.index, position);
681            }
682            symbols.push(symbol);
683        }
684
685        if !errors.is_empty() {
686            errors.sort_by_key(|error| error.directive);
687            return Err(errors);
688        }
689        let functions = functions
690            .into_iter()
691            .enumerate()
692            .map(|(index, (_, function, _))| FunctionDecl {
693                name: names[index],
694                signature: Signature {
695                    params: function
696                        .params
697                        .into_iter()
698                        .zip(&params[index])
699                        .map(|((_, ty), &name)| Parameter { name, ty })
700                        .collect(),
701                    ret: function.ret,
702                },
703                local_count: function.locals,
704                file: files[index],
705            })
706            .collect();
707        Ok(ProgramMetadata {
708            strings: strings.strings,
709            functions,
710            constants: pool,
711            main_function,
712            source_symbols: symbols,
713            extra,
714        })
715    }
716
717    /// [`assemble`](Self::assemble), failing with the first problem.
718    pub fn finish<Info>(self, extra: Info) -> eyre::Result<ProgramMetadata<V, Ty, Info>>
719    where
720        V: ConstantValue,
721    {
722        self.assemble(extra).map_err(|errors| {
723            let more = match errors.len() - 1 {
724                0 => String::new(),
725                1 => " (and 1 more problem)".to_owned(),
726                n => format!(" (and {n} more problems)"),
727            };
728            eyre::eyre!("invalid header: {}{more}", errors[0])
729        })
730    }
731}
732
733#[cfg(test)]
734mod tests;