Skip to main content

vihaco_module/
lowering.rs

1// SPDX-FileCopyrightText: 2026 The vihaco Authors
2// SPDX-License-Identifier: MIT
3
4//! Symbol lookups and string interning for metadata-backed instruction
5//! lowering.
6
7use crate::module::{ProgramMetadata, Symbol};
8use std::collections::HashMap;
9
10/// A lowering context that interns string literals into the section's string
11/// table.
12///
13/// `vihaco_syntax::ParsedModule::lower_with_metadata` uses it to move the
14/// completed table into the module. Contexts that wrap
15/// [`MetadataLoweringContext`] implement it by delegating.
16pub trait InternedStrings {
17    /// Take the string table: the metadata's strings followed by every string
18    /// interned during lowering, in first-occurrence order.
19    fn take_strings(&mut self) -> Vec<String>;
20}
21
22/// Symbol lookups and string interning backed by program metadata and the
23/// section's symbol table.
24///
25/// Every `@name` operand resolves through one section-wide symbol table:
26/// [`label_address`](Self::label_address) accepts any symbol, while
27/// [`function_address`](Self::function_address) additionally requires a
28/// function declaration with that name. Function indices retain metadata table
29/// order, independently of executable addresses.
30///
31/// [`string_index`](Self::string_index) interns: a string already in the
32/// table keeps its index, and a new one is appended. Lowering a code stream
33/// in address order therefore appends its literals in address order, after
34/// the strings the header derived. Take the completed table with
35/// [`into_strings`](Self::into_strings) and store it in the metadata before
36/// assembling the module. The context is independent of any instruction set;
37/// dialect crates implement their lowering-capability traits for it.
38#[derive(Debug)]
39pub struct MetadataLoweringContext {
40    table: Vec<String>,
41    strings: HashMap<String, u32>,
42    functions: HashMap<String, u32>,
43    symbols: HashMap<String, u32>,
44}
45
46impl MetadataLoweringContext {
47    /// Prepare section-wide string, function, and symbol lookups.
48    ///
49    /// # Errors
50    /// Rejects invalid function-name indices, duplicate function names,
51    /// duplicate symbols, and tables whose indices cannot be represented by
52    /// `u32`. Full program validation remains the responsibility of the
53    /// metadata loading driver.
54    pub fn new<V, Ty, Info>(
55        metadata: &ProgramMetadata<V, Ty, Info>,
56        symbols: &[Symbol],
57    ) -> eyre::Result<Self> {
58        let mut strings = HashMap::new();
59        for (index, text) in metadata.strings.iter().enumerate() {
60            strings.entry(text.clone()).or_insert(u32::try_from(index)?);
61        }
62        let string_table = metadata.strings.clone();
63        let mut functions = HashMap::new();
64        for index in 0..metadata.functions.len() {
65            let name = metadata.function_name(index)?;
66            eyre::ensure!(
67                functions
68                    .insert(name.to_owned(), u32::try_from(index)?)
69                    .is_none(),
70                "function `@{name}` has duplicate metadata"
71            );
72        }
73        let mut table = HashMap::with_capacity(symbols.len());
74        for symbol in symbols {
75            eyre::ensure!(
76                table.insert(symbol.name.clone(), symbol.address).is_none(),
77                "duplicate symbol `@{}`",
78                symbol.name
79            );
80        }
81        Ok(Self {
82            table: string_table,
83            strings,
84            functions,
85            symbols: table,
86        })
87    }
88
89    /// Look up a function's executable start address: its symbol's address.
90    pub fn function_address(&self, name: &str) -> eyre::Result<u32> {
91        eyre::ensure!(
92            self.functions.contains_key(name),
93            "undefined function `@{name}`"
94        );
95        self.symbols
96            .get(name)
97            .copied()
98            .ok_or_else(|| eyre::eyre!("function `@{name}` has no `@{name}:` symbol definition"))
99    }
100
101    /// Look up a function's index in the supplied metadata table.
102    pub fn function_index(&self, name: &str) -> eyre::Result<u32> {
103        self.functions
104            .get(name)
105            .copied()
106            .ok_or_else(|| eyre::eyre!("undefined function `@{name}`"))
107    }
108
109    /// Look up any symbol's address in the section's symbol table.
110    pub fn label_address(&self, name: &str) -> eyre::Result<u32> {
111        self.symbols
112            .get(name)
113            .copied()
114            .ok_or_else(|| eyre::eyre!("undefined symbol `@{name}`"))
115    }
116
117    /// Intern decoded string contents: the index of the first equal entry, or
118    /// of a new entry appended to the table.
119    ///
120    /// # Errors
121    /// Fails only if the table cannot represent another `u32` index.
122    pub fn string_index(&mut self, text: &str) -> eyre::Result<u32> {
123        if let Some(&index) = self.strings.get(text) {
124            return Ok(index);
125        }
126        let index = u32::try_from(self.table.len())
127            .map_err(|_| eyre::eyre!("string table exceeds u32 index space"))?;
128        self.table.push(text.to_owned());
129        self.strings.insert(text.to_owned(), index);
130        Ok(index)
131    }
132
133    /// The string table so far: the metadata's strings, then every interned
134    /// string.
135    pub fn strings(&self) -> &[String] {
136        &self.table
137    }
138
139    /// The completed string table, for `metadata.strings` before
140    /// `metadata.into_module(...)`.
141    pub fn into_strings(self) -> Vec<String> {
142        self.table
143    }
144}
145
146impl InternedStrings for MetadataLoweringContext {
147    fn take_strings(&mut self) -> Vec<String> {
148        self.strings.clear();
149        std::mem::take(&mut self.table)
150    }
151}
152
153#[cfg(test)]
154mod tests {
155    use super::*;
156    use crate::module::{FunctionDecl, NoInfo, Signature};
157
158    fn metadata() -> ProgramMetadata {
159        let function = |name| FunctionDecl {
160            name,
161            signature: Signature {
162                params: vec![],
163                ret: vec![],
164            },
165            local_count: 0,
166            file: 0,
167        };
168        ProgramMetadata {
169            strings: vec![
170                "later".into(),
171                "first".into(),
172                "hello".into(),
173                "hello".into(),
174            ],
175            functions: vec![function(0), function(1)],
176            constants: vec![],
177            main_function: Some(0),
178            source_symbols: vec![],
179            extra: NoInfo,
180        }
181    }
182
183    fn symbols() -> Vec<Symbol> {
184        [("first", 0), ("done", 6), ("later", 7)]
185            .into_iter()
186            .map(|(name, address)| Symbol {
187                name: name.into(),
188                address,
189            })
190            .collect()
191    }
192
193    #[test]
194    fn lookups_preserve_table_indices_and_resolve_through_symbols() -> eyre::Result<()> {
195        let metadata = metadata();
196        let mut context = MetadataLoweringContext::new(&metadata, &symbols())?;
197        assert_eq!(context.function_index("later")?, 0);
198        assert_eq!(context.function_address("later")?, 7);
199        assert_eq!(context.function_index("first")?, 1);
200        assert_eq!(context.function_address("first")?, 0);
201        assert_eq!(context.label_address("done")?, 6);
202        // Function symbols are ordinary symbols too.
203        assert_eq!(context.label_address("later")?, 7);
204        assert_eq!(context.string_index("hello")?, 2);
205        // New strings are appended once, in first-occurrence order.
206        assert_eq!(context.string_index("new")?, 4);
207        assert_eq!(context.string_index("newer")?, 5);
208        assert_eq!(context.string_index("new")?, 4);
209        assert_eq!(metadata.strings.len(), 4);
210        assert_eq!(&context.strings()[4..], ["new", "newer"]);
211        assert_eq!(context.into_strings().len(), 6);
212        Ok(())
213    }
214
215    #[test]
216    fn invalid_symbols_return_errors() -> eyre::Result<()> {
217        let mut metadata = metadata();
218        let context = MetadataLoweringContext::new(&metadata, &symbols())?;
219        assert!(context.function_index("missing").is_err());
220        assert!(context.label_address("missing").is_err());
221        // `done` is a symbol but not a declared function.
222        assert!(context.function_address("done").is_err());
223
224        let mut duplicate = symbols();
225        duplicate.push(Symbol {
226            name: "done".into(),
227            address: 1,
228        });
229        assert!(MetadataLoweringContext::new(&metadata, &duplicate).is_err());
230
231        let context = MetadataLoweringContext::new(&metadata, &[])?;
232        let err = context.function_address("first").unwrap_err();
233        assert!(err.to_string().contains("no `@first:` symbol"), "{err}");
234
235        metadata.functions[0].name = 99;
236        assert!(MetadataLoweringContext::new(&metadata, &symbols()).is_err());
237        metadata.functions[0].name = 1;
238        assert!(MetadataLoweringContext::new(&metadata, &symbols()).is_err());
239        Ok(())
240    }
241
242    #[test]
243    fn resolve_functions_derives_ranges_from_symbols() -> eyre::Result<()> {
244        let metadata = metadata();
245        let functions = metadata.resolve_functions(&symbols(), 9)?;
246        // Table order is preserved; ranges follow address order.
247        assert_eq!(
248            functions
249                .iter()
250                .map(|f| (f.name, f.start_address, f.end_address))
251                .collect::<Vec<_>>(),
252            [(0, 7, 9), (1, 0, 7)]
253        );
254
255        let err = metadata.resolve_functions(&symbols(), 5).unwrap_err();
256        assert!(
257            err.to_string().contains("outside the instruction stream"),
258            "{err}"
259        );
260
261        let err = metadata.resolve_functions(&symbols()[..2], 9).unwrap_err();
262        assert!(
263            err.to_string()
264                .contains("function `@later` (metadata.functions[0]) has no `@later:` symbol"),
265            "{err}"
266        );
267        Ok(())
268    }
269
270    #[test]
271    fn map_extra_preserves_all_tables_without_requiring_clone() {
272        struct Extra(String);
273        let original = metadata();
274        let converted = metadata().map_extra(|_| Extra("device".into()));
275        let converted = converted.map_extra(|extra| extra.0.len());
276        assert_eq!(converted.extra, 6);
277        assert_eq!(converted.functions, original.functions);
278        assert_eq!(converted.strings, original.strings);
279        assert_eq!(converted.constants, original.constants);
280        assert_eq!(converted.source_symbols, original.source_symbols);
281        assert_eq!(converted.main_function, original.main_function);
282    }
283}