codehelion_artifact/
wasm.rs

1//! WebAssembly implementation of the codehelion artifact backend boundary.
2//!
3//! Parsing validates a core module before retaining any facts from it. The
4//! backend never instantiates the module: all output is derived from bytes.
5
6use std::collections::{BTreeMap, BTreeSet};
7
8use crate::symbols::demangle;
9use crate::{
10    ArtifactBackend, ArtifactCall, ArtifactCapabilities, ArtifactDataSegment, ArtifactError,
11    ArtifactFingerprint, ArtifactFormat, ArtifactImport, ArtifactImportKind, ArtifactIr,
12    ArtifactSection, ArtifactSourceMapping, ArtifactSymbol, NormalizedInstructions, UnresolvedCall,
13};
14use wasmparser::{
15    ElementItems, Encoding, ExternalKind, KnownCustom, Name, Operator, Parser, Payload, TypeRef,
16    Validator,
17};
18
19/// Version of the immediate-free WebAssembly opcode representation.
20pub const WASM_NORMALIZATION_VERSION: &str = "wasm-opcode-v1";
21
22/// Parser backend for a WebAssembly core module.
23#[derive(Debug, Default, Clone, Copy)]
24pub struct WasmBackend;
25
26impl ArtifactBackend for WasmBackend {
27    fn format(&self) -> ArtifactFormat {
28        ArtifactFormat::Wasm
29    }
30
31    fn detects(&self, bytes: &[u8]) -> bool {
32        bytes.starts_with(b"\0asm")
33    }
34
35    #[allow(clippy::too_many_lines)] // Parsing follows Wasm's section stream in one pass.
36    fn parse(&self, bytes: &[u8]) -> Result<ArtifactIr, ArtifactError> {
37        if !self.detects(bytes) {
38            return Err(ArtifactError::WrongFormat {
39                expected: ArtifactFormat::Wasm,
40            });
41        }
42        Validator::new()
43            .validate_all(bytes)
44            .map_err(|error| malformed(error.to_string()))?;
45
46        let mut state = ParseState::default();
47        let mut ir = ArtifactIr::empty(ArtifactFormat::Wasm, bytes);
48        for payload in Parser::new(0).parse_all(bytes) {
49            let payload = payload.map_err(|error| malformed(error.to_string()))?;
50            if let Some((id, range)) = payload.as_section() {
51                ir.sections.push(ArtifactSection {
52                    name: section_name(id).map(str::to_owned),
53                    offset: range.start as u64,
54                    size: range.len() as u64,
55                    executable: id == 10,
56                });
57            }
58            match payload {
59                Payload::Version { encoding, .. } if encoding != Encoding::Module => {
60                    return Err(ArtifactError::Unsupported {
61                        format: ArtifactFormat::Wasm,
62                    });
63                }
64                Payload::ImportSection(reader) => {
65                    for import in reader.into_imports() {
66                        let import = import.map_err(|error| malformed(error.to_string()))?;
67                        ir.imports.push(ArtifactImport {
68                            module: Some(import.module.to_owned()),
69                            name: Some(import.name.to_owned()),
70                            kind: import_kind(&import.ty),
71                        });
72                        if let TypeRef::Func(type_index) | TypeRef::FuncExact(type_index) =
73                            import.ty
74                        {
75                            state
76                                .function_types
77                                .insert(state.imported_functions, type_index);
78                            state.imported_functions += 1;
79                        }
80                    }
81                }
82                Payload::FunctionSection(reader) => {
83                    for type_index in reader {
84                        state
85                            .defined_function_types
86                            .push(type_index.map_err(|error| malformed(error.to_string()))?);
87                    }
88                }
89                Payload::ExportSection(reader) => {
90                    for export in reader {
91                        let export = export.map_err(|error| malformed(error.to_string()))?;
92                        if export.kind == ExternalKind::Func {
93                            state.names.insert(export.index, export.name.to_owned());
94                            state.exports.insert(export.index);
95                        }
96                    }
97                }
98                Payload::StartSection { func, .. } => {
99                    state.start = Some(func);
100                }
101                Payload::ElementSection(reader) => {
102                    for element in reader {
103                        let element = element.map_err(|error| malformed(error.to_string()))?;
104                        if let ElementItems::Functions(functions) = element.items {
105                            for function in functions {
106                                state.element_functions.insert(
107                                    function.map_err(|error| malformed(error.to_string()))?,
108                                );
109                            }
110                        } else if let ElementItems::Expressions(_, expressions) = element.items {
111                            for expression in expressions {
112                                let expression =
113                                    expression.map_err(|error| malformed(error.to_string()))?;
114                                let operators = expression.get_operators_reader();
115                                for operator in operators {
116                                    if let Operator::RefFunc { function_index } =
117                                        operator.map_err(|error| malformed(error.to_string()))?
118                                    {
119                                        state.element_functions.insert(function_index);
120                                    }
121                                }
122                            }
123                        }
124                    }
125                }
126                Payload::CustomSection(section) => {
127                    if section.name() == "sourceMappingURL" {
128                        let uri = std::str::from_utf8(section.data())
129                            .map_err(|_| malformed("sourceMappingURL is not UTF-8".to_owned()))?;
130                        ir.source_mappings.push(ArtifactSourceMapping {
131                            uri: uri.to_owned(),
132                        });
133                    }
134                    if let KnownCustom::Name(names) = section.as_known() {
135                        for name in names {
136                            if let Name::Function(functions) =
137                                name.map_err(|error| malformed(error.to_string()))?
138                            {
139                                for function in functions {
140                                    let function =
141                                        function.map_err(|error| malformed(error.to_string()))?;
142                                    state.names.insert(function.index, function.name.to_owned());
143                                }
144                            }
145                        }
146                    }
147                }
148                Payload::CodeSectionEntry(body) => {
149                    let defined = u32::try_from(state.functions.len())
150                        .map_err(|_| malformed("too many defined functions".to_owned()))?;
151                    let index = state
152                        .imported_functions
153                        .checked_add(defined)
154                        .ok_or_else(|| malformed("too many functions".to_owned()))?;
155                    let type_index = *state
156                        .defined_function_types
157                        .get(defined as usize)
158                        .ok_or_else(|| malformed("function type is missing".to_owned()))?;
159                    state.function_types.insert(index, type_index);
160                    state.functions.push(parse_function(index, &body, bytes)?);
161                }
162                Payload::DataSection(reader) => {
163                    for data in reader {
164                        let data = data.map_err(|error| malformed(error.to_string()))?;
165                        ir.data_segments.push(ArtifactDataSegment {
166                            fingerprint: ArtifactFingerprint::from_content("wasm-data", data.data),
167                            section: Some(11),
168                            offset: data.range.start as u64,
169                            bytes: data.data.to_vec(),
170                        });
171                    }
172                }
173                _ => {}
174            }
175        }
176
177        let mut by_index = BTreeMap::new();
178        for function in &mut state.functions {
179            let name = state.names.get(&function.index).map(|name| demangle(name));
180            let normalized = NormalizedInstructions {
181                version: std::mem::take(&mut function.normalized.version),
182                bytes: std::mem::take(&mut function.normalized.bytes),
183            };
184            let fingerprint = symbol_fingerprint(name.as_deref(), &normalized.bytes);
185            by_index.insert(function.index, fingerprint);
186            ir.symbols.push(ArtifactSymbol {
187                fingerprint,
188                name,
189                exported: state.exports.contains(&function.index),
190                section: Some(10),
191                offset: function.offset,
192                size: function.code.len() as u64,
193                size_inferred: false,
194                code: std::mem::take(&mut function.code),
195                normalized: Some(normalized),
196                inline_stack: Vec::new(),
197            });
198        }
199        if let Some(start) = state.start.and_then(|index| by_index.get(&index)) {
200            ir.entry_points.push(*start);
201        }
202        ir.indirect_references.extend(
203            state
204                .indirect_root_indices()
205                .iter()
206                .filter_map(|index| by_index.get(index))
207                .copied(),
208        );
209        for function in &state.functions {
210            let caller = by_index[&function.index];
211            for call in &function.calls {
212                let (target, unresolved) = match call {
213                    PendingCall::Direct(index) => match by_index.get(index) {
214                        Some(target) => (Some(*target), None),
215                        None if *index < state.imported_functions => {
216                            (None, Some(UnresolvedCall::ExternalImport))
217                        }
218                        None => (None, Some(UnresolvedCall::MissingRelocation)),
219                    },
220                    PendingCall::Indirect { .. } => (None, Some(UnresolvedCall::IndirectTable)),
221                };
222                ir.calls.push(ArtifactCall {
223                    caller,
224                    target,
225                    unresolved,
226                });
227            }
228        }
229        ir.capabilities = self.capabilities();
230        ir.capabilities.source_mapping = !ir.source_mappings.is_empty();
231        Ok(ir)
232    }
233
234    fn capabilities(&self) -> ArtifactCapabilities {
235        ArtifactCapabilities {
236            symbols: true,
237            call_graph: true,
238            source_mapping: false,
239            debug_info_unreadable: false,
240            normalized_duplicates: true,
241            independent_data_segments: true,
242            relocations: false,
243            data_segments: true,
244        }
245    }
246}
247
248const fn import_kind(import: &TypeRef) -> ArtifactImportKind {
249    match import {
250        TypeRef::Func(_) | TypeRef::FuncExact(_) => ArtifactImportKind::Function,
251        TypeRef::Table(_) => ArtifactImportKind::Table,
252        TypeRef::Memory(_) => ArtifactImportKind::Memory,
253        TypeRef::Global(_) => ArtifactImportKind::Global,
254        TypeRef::Tag(_) => ArtifactImportKind::Tag,
255    }
256}
257
258/// State gathered from sections whose ordering differs from the code section.
259#[derive(Default)]
260struct ParseState {
261    imported_functions: u32,
262    start: Option<u32>,
263    element_functions: BTreeSet<u32>,
264    function_types: BTreeMap<u32, u32>,
265    defined_function_types: Vec<u32>,
266    names: BTreeMap<u32, String>,
267    exports: BTreeSet<u32>,
268    functions: Vec<PendingFunction>,
269}
270
271impl ParseState {
272    /// Return table references narrowed by observed indirect-call types.
273    ///
274    /// If no indirect call was seen, or an index has no type evidence, every
275    /// table element remains a root. That avoids falsely claiming dead code
276    /// when an export or host call can dispatch through the table.
277    fn indirect_root_indices(&self) -> BTreeSet<u32> {
278        let types: BTreeSet<_> = self
279            .functions
280            .iter()
281            .flat_map(|function| function.calls.iter())
282            .filter_map(|call| match call {
283                PendingCall::Indirect { type_index } => Some(*type_index),
284                PendingCall::Direct(_) => None,
285            })
286            .collect();
287        if types.is_empty() {
288            return self.element_functions.clone();
289        }
290        let narrowed: BTreeSet<_> = self
291            .element_functions
292            .iter()
293            .filter(|index| {
294                self.function_types
295                    .get(index)
296                    .is_some_and(|ty| types.contains(ty))
297            })
298            .copied()
299            .collect();
300        if narrowed.is_empty() {
301            self.element_functions.clone()
302        } else {
303            narrowed
304        }
305    }
306}
307
308/// One body before its source-level function name has necessarily been seen.
309struct PendingFunction {
310    index: u32,
311    offset: u64,
312    code: Vec<u8>,
313    normalized: NormalizedInstructions,
314    calls: Vec<PendingCall>,
315}
316
317/// A call target represented by the temporary WebAssembly index space only.
318enum PendingCall {
319    Direct(u32),
320    Indirect { type_index: u32 },
321}
322
323fn parse_function(
324    index: u32,
325    body: &wasmparser::FunctionBody<'_>,
326    bytes: &[u8],
327) -> Result<PendingFunction, ArtifactError> {
328    let mut normalized = Vec::with_capacity(body.range().len());
329    let mut calls = Vec::new();
330    let operators = body
331        .get_operators_reader()
332        .map_err(|error| malformed(error.to_string()))?;
333    for operator in operators.into_iter_with_offsets() {
334        let (operator, offset) = operator.map_err(|error| malformed(error.to_string()))?;
335        append_opcode_key(&mut normalized, bytes, offset)?;
336        match operator {
337            Operator::Call { function_index } | Operator::ReturnCall { function_index } => {
338                calls.push(PendingCall::Direct(function_index));
339            }
340            Operator::CallIndirect { type_index, .. }
341            | Operator::ReturnCallIndirect { type_index, .. } => {
342                calls.push(PendingCall::Indirect { type_index });
343            }
344            _ => {}
345        }
346    }
347    Ok(PendingFunction {
348        index,
349        offset: body.range().start as u64,
350        code: body.as_bytes().to_vec(),
351        normalized: NormalizedInstructions {
352            version: WASM_NORMALIZATION_VERSION.to_owned(),
353            bytes: normalized,
354        },
355        calls,
356    })
357}
358
359/// Encode an opcode without any of its value, index, or branch immediates.
360///
361/// WebAssembly's extended opcodes start with an escape byte and a LEB128
362/// subopcode. Keeping that subopcode distinguishes operations while allowing
363/// local indices, call targets, labels, and constants to normalize away.
364fn append_opcode_key(
365    normalized: &mut Vec<u8>,
366    bytes: &[u8],
367    offset: usize,
368) -> Result<(), ArtifactError> {
369    let opcode = *bytes
370        .get(offset)
371        .ok_or_else(|| malformed("operator offset lies outside the input".to_owned()))?;
372    if !matches!(opcode, 0xfb..=0xfe) {
373        normalized.push(opcode);
374        return Ok(());
375    }
376    let (subopcode, _) = unsigned_leb(bytes, offset + 1)?;
377    normalized.push(opcode);
378    normalized.extend(subopcode.to_le_bytes());
379    Ok(())
380}
381
382/// Read one unsigned LEB128 value only to distinguish an extended opcode.
383fn unsigned_leb(bytes: &[u8], start: usize) -> Result<(u32, usize), ArtifactError> {
384    let mut value = 0_u32;
385    for shift in 0..5 {
386        let index = start + shift;
387        let byte = *bytes
388            .get(index)
389            .ok_or_else(|| malformed("truncated extended opcode".to_owned()))?;
390        value |= u32::from(byte & 0x7f) << (shift * 7);
391        if byte & 0x80 == 0 {
392            return Ok((value, index + 1));
393        }
394    }
395    Err(malformed("extended opcode LEB128 is too long".to_owned()))
396}
397
398fn symbol_fingerprint(name: Option<&str>, normalized: &[u8]) -> ArtifactFingerprint {
399    let mut bytes = Vec::new();
400    // The section and normalization recipe belong to identity. Function
401    // indices do not: they only route calls while this one parse is in memory.
402    bytes.push(10);
403    let name = name.unwrap_or("");
404    bytes.extend((name.len() as u64).to_le_bytes());
405    bytes.extend(name.as_bytes());
406    bytes.extend((WASM_NORMALIZATION_VERSION.len() as u64).to_le_bytes());
407    bytes.extend(WASM_NORMALIZATION_VERSION.as_bytes());
408    bytes.extend(normalized);
409    ArtifactFingerprint::from_content("wasm-symbol", &bytes)
410}
411
412const fn section_name(id: u8) -> Option<&'static str> {
413    match id {
414        0 => Some("custom"),
415        1 => Some("type"),
416        2 => Some("import"),
417        3 => Some("function"),
418        4 => Some("table"),
419        5 => Some("memory"),
420        6 => Some("global"),
421        7 => Some("export"),
422        8 => Some("start"),
423        9 => Some("element"),
424        10 => Some("code"),
425        11 => Some("data"),
426        _ => None,
427    }
428}
429
430const fn malformed(message: String) -> ArtifactError {
431    ArtifactError::Malformed {
432        format: ArtifactFormat::Wasm,
433        message,
434    }
435}
436
437#[cfg(test)]
438#[allow(clippy::expect_used, clippy::panic, clippy::unwrap_used)]
439mod tests {
440    use super::*;
441    use crate::metrics;
442    use proptest::prelude::*;
443    use std::panic::{AssertUnwindSafe, catch_unwind};
444
445    const MODULE: &[u8] = &[
446        0, 97, 115, 109, 1, 0, 0, 0, 1, 4, 1, 96, 0, 0, 3, 3, 2, 0, 0, 7, 7, 1, 3, b'f', b'o',
447        b'o', 0, 0, 10, 9, 2, 4, 0, 16, 1, 11, 2, 0, 11, 11, 6, 1, 1, 3, b'a', b'b', b'c', 0, 18,
448        4, b'n', b'a', b'm', b'e', 1, 11, 2, 0, 3, b'f', b'o', b'o', 1, 3, b'b', b'a', b'r',
449    ];
450
451    #[test]
452    fn parses_code_names_calls_and_data_without_executing_the_module() {
453        let artifact = WasmBackend.parse(MODULE).expect("fixture parses");
454        assert_eq!(artifact.format, ArtifactFormat::Wasm);
455        assert!(artifact.capabilities.symbols);
456        assert!(artifact.capabilities.call_graph);
457        assert!(artifact.capabilities.data_segments);
458        assert_eq!(artifact.symbols.len(), 2);
459        assert_eq!(artifact.symbols[0].name.as_deref(), Some("foo"));
460        assert_eq!(artifact.symbols[1].name.as_deref(), Some("bar"));
461        assert!(artifact.symbols[0].exported);
462        assert!(!artifact.symbols[1].exported);
463        assert_eq!(artifact.symbols[0].code, vec![0, 16, 1, 11]);
464        assert_eq!(
465            artifact.symbols[0].normalized.as_ref().unwrap().bytes,
466            vec![16, 11]
467        );
468        assert_eq!(artifact.calls.len(), 1);
469        assert_eq!(artifact.calls[0].caller, artifact.symbols[0].fingerprint);
470        assert_eq!(
471            artifact.calls[0].target,
472            Some(artifact.symbols[1].fingerprint)
473        );
474        assert_eq!(artifact.data_segments[0].bytes, b"abc");
475        assert!(
476            artifact
477                .sections
478                .iter()
479                .any(|section| section.name.as_deref() == Some("code") && section.executable)
480        );
481    }
482
483    #[test]
484    fn malformed_or_other_inputs_return_errors_instead_of_panicking() {
485        assert!(matches!(
486            WasmBackend.parse(b"not wasm"),
487            Err(ArtifactError::WrongFormat { .. })
488        ));
489        assert!(matches!(
490            WasmBackend.parse(b"\0asm\x01\0\0\0\x0a"),
491            Err(ArtifactError::Malformed { .. })
492        ));
493    }
494
495    proptest! {
496        #[test]
497        fn arbitrary_and_truncated_wasm_bytes_never_panic(
498            bytes in prop::collection::vec(any::<u8>(), 0..2048),
499        ) {
500            let mut truncated = b"\0asm\x01\0\0\0".to_vec();
501            truncated.extend(&bytes);
502            for input in [&bytes, &truncated] {
503                let result = catch_unwind(AssertUnwindSafe(|| WasmBackend.parse(input)));
504                prop_assert!(result.is_ok());
505            }
506        }
507    }
508
509    #[test]
510    fn parsing_the_same_module_twice_is_deterministic() {
511        assert_eq!(
512            WasmBackend.parse(MODULE).expect("first fixture parses"),
513            WasmBackend.parse(MODULE).expect("second fixture parses")
514        );
515    }
516
517    #[test]
518    fn normalization_keeps_extended_opcodes_and_drops_call_immediates() {
519        let mut normalized = Vec::new();
520        append_opcode_key(&mut normalized, &[0x10, 0x01], 0).unwrap();
521        append_opcode_key(&mut normalized, &[0x10, 0x7f], 0).unwrap();
522        assert_eq!(normalized, vec![0x10, 0x10]);
523
524        let mut extended = Vec::new();
525        append_opcode_key(&mut extended, &[0xfc, 0x83, 0x01], 0).unwrap();
526        assert_eq!(extended, vec![0xfc, 131, 0, 0, 0]);
527        assert!(
528            append_opcode_key(&mut extended, &[0xfc, 0x80, 0x80, 0x80, 0x80, 0x80], 0,).is_err()
529        );
530    }
531
532    #[test]
533    fn wasm_names_use_the_same_demangling_as_other_artifact_backends() {
534        assert_eq!(demangle("ordinary_name"), "ordinary_name");
535        assert!(demangle("_Z3fooi").contains("foo"));
536        assert!(demangle("_ZN4test3foo17h0123456789abcdefE").contains("test::foo"));
537    }
538
539    #[test]
540    fn fixture_ir_snapshot_is_current() {
541        let artifact = WasmBackend.parse(MODULE).expect("fixture parses");
542        let rendered = serde_json::to_string_pretty(&artifact).expect("IR serializes");
543        assert_eq!(
544            rendered,
545            include_str!("../tests/golden/module-ir-v1.json").trim_end()
546        );
547    }
548
549    #[test]
550    fn a_module_without_a_name_section_keeps_the_code_and_leaves_names_absent() {
551        // The custom name section starts after the passive data segment.
552        let artifact = WasmBackend
553            .parse(&MODULE[..47])
554            .expect("stripped fixture parses");
555        assert_eq!(artifact.symbols.len(), 2);
556        assert_eq!(artifact.symbols[0].name.as_deref(), Some("foo"));
557        assert_eq!(artifact.symbols[1].name, None);
558        assert_eq!(artifact.symbols[1].code, vec![0, 11]);
559    }
560
561    #[test]
562    fn imports_and_source_mapping_urls_are_retained_without_fetching_them() {
563        let imported_module = [
564            0, 97, 115, 109, 1, 0, 0, 0, 1, 4, 1, 96, 0, 0, 2, 7, 1, 1, b'm', 1, b'f', 0, 0,
565        ];
566        let imported = WasmBackend
567            .parse(&imported_module)
568            .expect("import fixture parses");
569        assert_eq!(imported.imports.len(), 1);
570        assert_eq!(imported.imports[0].module.as_deref(), Some("m"));
571        assert_eq!(imported.imports[0].name.as_deref(), Some("f"));
572        assert_eq!(imported.imports[0].kind, ArtifactImportKind::Function);
573
574        let mut source_mapped = MODULE.to_vec();
575        source_mapped.extend([0, 26, 16]);
576        source_mapped.extend(b"sourceMappingURL");
577        source_mapped.extend(b"maps.json");
578        let source_mapped = WasmBackend
579            .parse(&source_mapped)
580            .expect("source-map fixture parses");
581        assert!(source_mapped.capabilities.source_mapping);
582        assert_eq!(source_mapped.source_mappings[0].uri, "maps.json");
583    }
584
585    #[test]
586    fn a_start_function_is_an_entry_point_even_when_not_exported() {
587        let module = [
588            0, 97, 115, 109, 1, 0, 0, 0, 1, 4, 1, 96, 0, 0, 3, 2, 1, 0, 8, 1, 0, 10, 4, 1, 2, 0, 11,
589        ];
590        let artifact = WasmBackend.parse(&module).expect("start fixture parses");
591        assert_eq!(artifact.entry_points, vec![artifact.symbols[0].fingerprint]);
592        assert!(
593            metrics::dead_code_candidates(&artifact)
594                .expect("entry point establishes roots")
595                .symbols
596                .is_empty()
597        );
598    }
599
600    #[test]
601    fn element_table_references_are_conservative_reachability_roots() {
602        let module = [
603            0, 97, 115, 109, 1, 0, 0, 0, 1, 4, 1, 96, 0, 0, 3, 3, 2, 0, 0, 4, 4, 1, 112, 0, 1, 9,
604            9, 1, 4, 65, 0, 11, 1, 210, 1, 11, 10, 10, 2, 2, 0, 11, 5, 0, 65, 0, 26, 11,
605        ];
606        let artifact = WasmBackend.parse(&module).expect("element fixture parses");
607        assert_eq!(
608            artifact.indirect_references,
609            vec![artifact.symbols[1].fingerprint]
610        );
611        let dead = metrics::dead_code_candidates(&artifact).expect("table establishes roots");
612        assert_eq!(dead.symbols, vec![artifact.symbols[0].fingerprint]);
613        assert!(dead.definitive);
614    }
615
616    #[test]
617    fn indirect_call_types_narrow_table_roots_when_all_types_are_known() {
618        let state = ParseState {
619            element_functions: BTreeSet::from([0, 1, 2]),
620            function_types: BTreeMap::from([(0, 7), (1, 8), (2, 7)]),
621            functions: vec![PendingFunction {
622                index: 3,
623                offset: 0,
624                code: Vec::new(),
625                normalized: NormalizedInstructions {
626                    version: WASM_NORMALIZATION_VERSION.to_owned(),
627                    bytes: Vec::new(),
628                },
629                calls: vec![PendingCall::Indirect { type_index: 7 }],
630            }],
631            ..ParseState::default()
632        };
633
634        assert_eq!(state.indirect_root_indices(), BTreeSet::from([0, 2]));
635    }
636}
codehelion_artifact/wasm.rs

codehelion_artifact/
wasm.rs
