hara_native/vm/
validate.rs

1//! Program validation: one abstract-interpretation pass over the code
2//! vector before any execution. After validation the machine indexes
3//! without re-checking, and malformed programs never reach a panic.
4
5
6use super::error::ValidationError;
7use super::opcode::Instruction;
8use super::program::{
9    FunctionPrototype, Program, MAX_CONSTANTS, MAX_INSTRUCTIONS, MAX_LOCALS, MAX_OPERAND_STACK,
10};
11use crate::core::Value;
12
13/// Validates a whole program. See `notes/rust-bytecode-vm.md` §9 for the
14/// rule list.
15pub fn validate(program: &Program) -> Result<(), ValidationError> {
16    if program.constants.len() > MAX_CONSTANTS {
17        return Err(ValidationError::new(
18            format!("constant pool exceeds limit of {MAX_CONSTANTS}"),
19            None,
20        ));
21    }
22    if program.functions.is_empty() {
23        return Err(ValidationError::new("program has no functions", None));
24    }
25    if program.entry as usize >= program.functions.len() {
26        return Err(ValidationError::new(
27            "entry function index out of range",
28            None,
29        ));
30    }
31    let multiple = program.functions.len() > 1;
32    for (index, function) in program.functions.iter().enumerate() {
33        validate_declared_arity(program, index)
34            .and_then(|_| validate_function(program, function))
35            .map_err(|mut error| {
36                if multiple {
37                    error.message = format!("function {index}: {}", error.message);
38                }
39                error
40            })?;
41    }
42    Ok(())
43}
44
45fn validate_declared_arity(program: &Program, index: usize) -> Result<(), ValidationError> {
46    let function = &program.functions[index];
47    let Some(crate::kernel::SchemaType::Function(arities)) = program.function_schema(index as u16)
48    else {
49        return Ok(());
50    };
51    if arities.iter().any(|schema| {
52        schema.fixed.len() == function.arity as usize && schema.rest.is_some() == function.variadic
53    }) {
54        return Ok(());
55    }
56    Err(ValidationError::new(
57        format!(
58            "function schema for {} has no {}-argument arity{}",
59            function.name.as_deref().unwrap_or("<anonymous>"),
60            function.arity,
61            if function.variadic {
62                " with rest arguments"
63            } else {
64                ""
65            }
66        ),
67        None,
68    ))
69}
70
71fn validate_function(
72    program: &Program,
73    function: &FunctionPrototype,
74) -> Result<(), ValidationError> {
75    if function.source_map.len() != function.code.len() {
76        return Err(ValidationError::new(
77            "source map length does not match code length",
78            None,
79        ));
80    }
81    let heights = stack_heights(program, function)?;
82    let computed = heights.iter().copied().max().unwrap_or(0);
83    if computed != function.max_stack {
84        return Err(ValidationError::new(
85            format!(
86                "declared max_stack {} disagrees with computed {computed}",
87                function.max_stack
88            ),
89            None,
90        ));
91    }
92    validate_handlers(function, &heights)?;
93    Ok(())
94}
95
96/// Checks the static handler table: ranges, targets, slots, depth
97/// declarations, pending-slot presence, and clean nesting. Stack heights
98/// at handler targets are already covered by the analysis, which seeds
99/// them with the height computed at each entry's `start`.
100fn validate_handlers(function: &FunctionPrototype, heights: &[u16]) -> Result<(), ValidationError> {
101    let code_len = function.code.len();
102    for (index, entry) in function.handlers.iter().enumerate() {
103        let (start, end) = (entry.start as usize, entry.end as usize);
104        if start >= end || end > code_len {
105            return Err(ValidationError::new(
106                format!("try range [{start}, {end}) out of bounds or empty"),
107                Some(entry.start),
108            ));
109        }
110        if heights[start] != entry.depth {
111            return Err(ValidationError::new(
112                format!(
113                    "handler depth {} disagrees with computed {}",
114                    entry.depth, heights[start]
115                ),
116                Some(entry.start),
117            ));
118        }
119        for catch in &entry.catches {
120            if catch.target as usize >= code_len {
121                return Err(ValidationError::new(
122                    format!("catch target {} out of range", catch.target),
123                    Some(entry.start),
124                ));
125            }
126            if catch.binding >= function.local_count {
127                return Err(ValidationError::new(
128                    format!("catch binding slot {} out of range", catch.binding),
129                    Some(entry.start),
130                ));
131            }
132        }
133        match (entry.finally, entry.pending_value, entry.pending_error) {
134            (Some(finally), Some(value), Some(flag)) => {
135                if finally as usize >= code_len {
136                    return Err(ValidationError::new(
137                        format!("finally target {finally} out of range"),
138                        Some(entry.start),
139                    ));
140                }
141                if value >= function.local_count || flag >= function.local_count {
142                    return Err(ValidationError::new(
143                        "pending slot out of range",
144                        Some(entry.start),
145                    ));
146                }
147            }
148            (None, None, None) => {}
149            _ => {
150                return Err(ValidationError::new(
151                    "pending slots must be present exactly when finally is present",
152                    Some(entry.start),
153                ))
154            }
155        }
156        for other in &function.handlers[index + 1..] {
157            let (s1, e1) = (entry.start, entry.end);
158            let (s2, e2) = (other.start, other.end);
159            let disjoint = e1 <= s2 || e2 <= s1;
160            let nested = (s1 <= s2 && e2 <= e1) || (s2 <= s1 && e1 <= e2);
161            if !disjoint && !nested {
162                return Err(ValidationError::new(
163                    "try ranges must not partially overlap",
164                    Some(entry.start),
165                ));
166            }
167        }
168    }
169    Ok(())
170}
171
172/// Computes the unique operand-stack height at every instruction while
173/// checking indexes, slots, jump targets, reachability, and termination.
174/// Shared by the validator and by the compiler, which uses it to fill in
175/// `max_stack` for code it just emitted.
176pub(crate) fn stack_heights(
177    program: &Program,
178    function: &FunctionPrototype,
179) -> Result<Vec<u16>, ValidationError> {
180    let code = &function.code;
181    if code.is_empty() {
182        return Err(ValidationError::new("function has no code", None));
183    }
184    if code.len() > MAX_INSTRUCTIONS {
185        return Err(ValidationError::new(
186            format!("code exceeds limit of {MAX_INSTRUCTIONS} instructions"),
187            None,
188        ));
189    }
190    if usize::from(function.local_count) > MAX_LOCALS {
191        return Err(ValidationError::new("local count exceeds slot limit", None));
192    }
193    let mut heights: Vec<Option<u16>> = vec![None; code.len()];
194    let mut worklist: Vec<(usize, u16)> = vec![(0, 0)];
195    // Handler regions are reached by unwinding, not by ordinary control
196    // flow; each is seeded with the height computed at its entry's start.
197    let mut handler_starts: std::collections::HashMap<usize, Vec<usize>> =
198        std::collections::HashMap::new();
199    for (index, entry) in function.handlers.iter().enumerate() {
200        handler_starts
201            .entry(entry.start as usize)
202            .or_default()
203            .push(index);
204    }
205    while let Some((ip, height)) = worklist.pop() {
206        if let Some(existing) = heights[ip] {
207            if existing != height {
208                return Err(ValidationError::new(
209                    format!("inconsistent stack heights {existing} and {height} at join"),
210                    Some(ip as u32),
211                ));
212            }
213            continue;
214        }
215        heights[ip] = Some(height);
216        if let Some(entries) = handler_starts.get(&ip) {
217            for &index in entries {
218                let entry = &function.handlers[index];
219                for catch in &entry.catches {
220                    if catch.target as usize >= code.len() {
221                        return Err(ValidationError::new(
222                            format!("catch target {} out of range", catch.target),
223                            Some(entry.start),
224                        ));
225                    }
226                    worklist.push((catch.target as usize, height));
227                }
228                if let Some(finally) = entry.finally {
229                    if finally as usize >= code.len() {
230                        return Err(ValidationError::new(
231                            format!("finally target {finally} out of range"),
232                            Some(entry.start),
233                        ));
234                    }
235                    worklist.push((finally as usize, height));
236                }
237            }
238        }
239        let instruction = &code[ip];
240        let at = Some(ip as u32);
241        // Operand checks independent of control flow.
242        match instruction {
243            Instruction::Constant(index) if *index as usize >= program.constants.len() => {
244                return Err(ValidationError::new(
245                    format!("constant index {index} out of range"),
246                    at,
247                ));
248            }
249            Instruction::LoadLocal(slot) | Instruction::StoreLocal(slot)
250                if *slot >= function.local_count =>
251            {
252                return Err(ValidationError::new(
253                    format!("local slot {slot} out of range"),
254                    at,
255                ));
256            }
257            Instruction::IntrinsicCall { target, .. }
258            | Instruction::ProtocolCall { target, .. }
259            | Instruction::IntrinsicValue(target) => {
260                string_constant(program, *target, at)?;
261            }
262            Instruction::BuiltinValue(constant)
263                if !matches!(
264                    program.constants.get(*constant as usize),
265                    Some(Value::String(_))
266                ) =>
267            {
268                return Err(ValidationError::new(
269                    format!("builtin name constant {constant} is invalid"),
270                    at,
271                ));
272            }
273            Instruction::NamespaceValue(constant)
274                if !matches!(
275                    program.constants.get(*constant as usize),
276                    Some(Value::String(_))
277                ) =>
278            {
279                return Err(ValidationError::new(
280                    format!("namespace name constant {constant} is invalid"),
281                    at,
282                ));
283            }
284            Instruction::NamespaceOperation(constant) => {
285                let Some(value) = program.constants.get(*constant as usize) else {
286                    return Err(ValidationError::new(
287                        format!("constant index {constant} out of range"),
288                        at,
289                    ));
290                };
291                let valid = crate::core::value_to_form(value).is_ok_and(|form| {
292                    matches!(
293                        crate::core::form_without_metadata(&form),
294                        crate::kernel::Form::List(items)
295                            if matches!(
296                                items.first(),
297                                Some(crate::kernel::Form::Symbol(operator))
298                                    if matches!(operator.as_str(), "ns" | "ns+" | "require")
299                            )
300                    )
301                });
302                if !valid {
303                    return Err(ValidationError::new(
304                        format!("namespace-management constant {constant} is invalid"),
305                        at,
306                    ));
307                }
308            }
309            Instruction::DynamicBind(constant) | Instruction::DynamicUnbind(constant)
310                if !matches!(
311                    program.constants.get(*constant as usize),
312                    Some(Value::String(_))
313                ) =>
314            {
315                return Err(ValidationError::new(
316                    format!("binding name constant {constant} is invalid"),
317                    at,
318                ));
319            }
320            Instruction::Jump(target) | Instruction::JumpIfFalse(target)
321                if *target as usize >= code.len() =>
322            {
323                return Err(ValidationError::new(
324                    format!("jump target {target} out of range"),
325                    at,
326                ));
327            }
328            Instruction::Closure {
329                prototype,
330                captures,
331            } => {
332                let Some(target) = program.functions.get(usize::from(*prototype)) else {
333                    return Err(ValidationError::new(
334                        format!("closure prototype {prototype} out of range"),
335                        at,
336                    ));
337                };
338                if usize::from(*captures) != usize::from(target.capture_count) {
339                    return Err(ValidationError::new(
340                        format!(
341                            "closure captures {captures} but prototype expects {}",
342                            target.capture_count
343                        ),
344                        at,
345                    ));
346                }
347            }
348            Instruction::CallStatic { prototype, argc } => {
349                let Some(target) = program.functions.get(usize::from(*prototype)) else {
350                    return Err(ValidationError::new(
351                        format!("callstatic target {prototype} out of range"),
352                        at,
353                    ));
354                };
355                let arity = usize::from(target.arity);
356                let arity_ok = if target.variadic {
357                    usize::from(*argc) >= arity
358                } else {
359                    usize::from(*argc) == arity
360                };
361                if !arity_ok {
362                    return Err(ValidationError::new(
363                        format!("callstatic argc {argc} but prototype expects {arity}"),
364                        at,
365                    ));
366                }
367                if target.capture_count != function.capture_count {
368                    return Err(ValidationError::new(
369                        "callstatic capture count differs from current function",
370                        at,
371                    ));
372                }
373            }
374            Instruction::GetGlobal(index)
375            | Instruction::SetGlobal(index)
376            | Instruction::VarGlobal(index)
377            | Instruction::MutableFieldGet(index)
378            | Instruction::MutableFieldSet(index)
379            | Instruction::DeclareGlobal(index) => {
380                string_constant(program, *index, at)?;
381            }
382            Instruction::DefGlobal { name, metadata }
383            | Instruction::DefMacro { name, metadata } => {
384                string_constant(program, *name, at)?;
385                if let Some(metadata) = metadata {
386                    if usize::from(*metadata) >= program.var_metadata.len() {
387                        return Err(ValidationError::new(
388                            format!("var metadata index {metadata} out of range"),
389                            at,
390                        ));
391                    }
392                }
393            }
394            Instruction::MakeMultiArity { name, .. } => {
395                string_constant(program, *name, at)?;
396            }
397            _ => {}
398        }
399        // Stack effects and successors.
400        if let Instruction::Return = instruction {
401            if height != 1 {
402                return Err(ValidationError::new(
403                    format!("return with stack height {height}, expected 1"),
404                    at,
405                ));
406            }
407            continue;
408        }
409        if matches!(instruction, Instruction::Throw | Instruction::Rethrow) {
410            if height < 1 {
411                return Err(ValidationError::new("stack underflow", at));
412            }
413            continue;
414        }
415        let effect = instruction
416            .stack_effect()
417            .expect("non-terminal instruction");
418        let next = height as i32 + effect;
419        if next < 0 {
420            return Err(ValidationError::new("stack underflow", at));
421        }
422        if next as usize > MAX_OPERAND_STACK {
423            return Err(ValidationError::new(
424                format!("operand stack exceeds limit of {MAX_OPERAND_STACK}"),
425                at,
426            ));
427        }
428        let next = next as u16;
429        match instruction {
430            Instruction::Jump(target) => worklist.push((*target as usize, next)),
431            Instruction::JumpIfFalse(target) => {
432                worklist.push((*target as usize, next));
433                push_fallthrough(code, ip, next, &mut worklist)?;
434            }
435            _ => push_fallthrough(code, ip, next, &mut worklist)?,
436        }
437    }
438    let mut result = Vec::with_capacity(code.len());
439    for (ip, height) in heights.into_iter().enumerate() {
440        match height {
441            Some(height) => result.push(height),
442            None => {
443                return Err(ValidationError::new(
444                    "unreachable instruction",
445                    Some(ip as u32),
446                ))
447            }
448        }
449    }
450    Ok(result)
451}
452
453fn push_fallthrough(
454    code: &[Instruction],
455    ip: usize,
456    height: u16,
457    worklist: &mut Vec<(usize, u16)>,
458) -> Result<(), ValidationError> {
459    if ip + 1 == code.len() {
460        return Err(ValidationError::new(
461            "missing return: control falls off the end of the function",
462            Some(ip as u32),
463        ));
464    }
465    debug_assert!(code[ip].falls_through());
466    worklist.push((ip + 1, height));
467    Ok(())
468}
469
470/// Global-instruction name operands must index a string constant.
471fn string_constant(program: &Program, index: u32, at: Option<u32>) -> Result<(), ValidationError> {
472    match program.constants.get(index as usize) {
473        Some(Value::String(_)) => Ok(()),
474        Some(_) => Err(ValidationError::new(
475            format!("global name constant {index} is not a string"),
476            at,
477        )),
478        None => Err(ValidationError::new(
479            format!("constant index {index} out of range"),
480            at,
481        )),
482    }
483}
hara_native/vm/validate.rs

hara_native/vm/
validate.rs
