harn_kernel/
program.rs

1use std::collections::HashMap;
2use std::fmt;
3use std::sync::Arc;
4
5use harn_parser::TypeExpr;
6use serde::{Deserialize, Serialize};
7
8use crate::{BuiltinId, Op};
9
10#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
11pub enum Constant {
12    Int(i64),
13    Float(f64),
14    String(String),
15    Bool(bool),
16    Nil,
17    Duration(i64),
18}
19
20impl fmt::Display for Constant {
21    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
22        match self {
23            Self::Int(value) => write!(formatter, "{value}"),
24            Self::Float(value) => write!(formatter, "{value}"),
25            Self::String(value) => write!(formatter, "\"{value}\""),
26            Self::Bool(value) => write!(formatter, "{value}"),
27            Self::Nil => formatter.write_str("nil"),
28            Self::Duration(value) => write!(formatter, "{value}ms"),
29        }
30    }
31}
32
33#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
34pub struct LocalSlotInfo {
35    pub name: String,
36    pub mutable: bool,
37    pub scope_depth: usize,
38}
39
40/// One annotated `let` / `const` binding site of a chunk.
41///
42/// The counterpart of [`ParamSlot`] for the other binding site a declared type
43/// can appear at. `Op::AssertBindingType` indexes this table and validates the
44/// initializer against `type_expr` through the same
45/// `type_contract::matches_type` matcher that validates arguments against a
46/// parameter's declared type, so an annotation means one thing everywhere.
47///
48/// `nominal_type_names` is narrowed at compile time to the struct and enum
49/// names actually mentioned by `type_expr`. The matcher treats every other
50/// named type as unconstrained, which is what keeps aliases, interfaces, and
51/// generic type parameters permissive here exactly as they are on parameters.
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct BindingTypeSlot {
54    pub name: String,
55    pub type_expr: TypeExpr,
56    pub nominal_type_names: Vec<String>,
57}
58
59#[derive(Debug, Clone, Serialize, Deserialize)]
60pub struct ParamSlot {
61    pub name: String,
62    pub type_expr: Option<TypeExpr>,
63    pub has_default: bool,
64}
65
66impl ParamSlot {
67    pub fn from_typed_param(param: &harn_parser::TypedParam) -> Self {
68        Self::from_typed_param_with_type(param, param.type_expr.clone())
69    }
70
71    pub(crate) fn from_typed_param_with_type(
72        param: &harn_parser::TypedParam,
73        type_expr: Option<TypeExpr>,
74    ) -> Self {
75        Self {
76            name: param.name.clone(),
77            type_expr,
78            has_default: param.default_value.is_some(),
79        }
80    }
81
82    pub fn vec_from_typed(params: &[harn_parser::TypedParam]) -> Vec<Self> {
83        params.iter().map(Self::from_typed_param).collect()
84    }
85}
86
87#[derive(Debug, Clone, Serialize, Deserialize)]
88pub struct CompiledFunction {
89    pub name: String,
90    pub type_params: Vec<String>,
91    pub nominal_type_names: Vec<String>,
92    pub params: Vec<ParamSlot>,
93    pub default_start: Option<usize>,
94    pub chunk: Arc<Chunk>,
95    pub is_generator: bool,
96    pub is_stream: bool,
97    pub has_rest_param: bool,
98    pub has_runtime_type_checks: bool,
99}
100
101impl CompiledFunction {
102    pub(crate) fn has_runtime_type_checks_for_params(params: &[ParamSlot]) -> bool {
103        params.iter().any(|param| {
104            param
105                .type_expr
106                .as_ref()
107                .is_some_and(crate::type_contract::requires_runtime_type_check)
108        })
109    }
110
111    pub fn param_names(&self) -> impl Iterator<Item = &str> {
112        self.params.iter().map(|param| param.name.as_str())
113    }
114
115    pub fn required_param_count(&self) -> usize {
116        self.default_start.unwrap_or(self.params.len())
117    }
118
119    pub fn declares_type_param(&self, name: &str) -> bool {
120        self.type_params.iter().any(|param| param == name)
121    }
122
123    pub fn has_nominal_type(&self, name: &str) -> bool {
124        self.nominal_type_names.iter().any(|ty| ty == name)
125    }
126}
127
128#[derive(Debug, Serialize, Deserialize)]
129pub struct Chunk {
130    pub code: Vec<u8>,
131    pub constants: Vec<Constant>,
132    #[serde(skip)]
133    constant_index: Option<HashMap<ConstantKey, u16>>,
134    pub lines: Vec<u32>,
135    pub columns: Vec<u32>,
136    pub source_file: Option<String>,
137    #[doc(hidden)]
138    pub current_col: u32,
139    pub functions: Vec<Arc<CompiledFunction>>,
140    #[doc(hidden)]
141    pub local_slots: Vec<LocalSlotInfo>,
142    #[doc(hidden)]
143    pub binding_types: Vec<BindingTypeSlot>,
144    #[doc(hidden)]
145    pub references_outer_names: bool,
146    #[cfg(debug_assertions)]
147    #[serde(skip)]
148    balance_depth: i32,
149    #[cfg(debug_assertions)]
150    #[serde(skip)]
151    balance_nonlinear: u32,
152}
153
154impl Clone for Chunk {
155    fn clone(&self) -> Self {
156        Self {
157            code: self.code.clone(),
158            constants: self.constants.clone(),
159            constant_index: self.constant_index.clone(),
160            lines: self.lines.clone(),
161            columns: self.columns.clone(),
162            source_file: self.source_file.clone(),
163            current_col: self.current_col,
164            functions: self.functions.clone(),
165            local_slots: self.local_slots.clone(),
166            binding_types: self.binding_types.clone(),
167            references_outer_names: self.references_outer_names,
168            #[cfg(debug_assertions)]
169            balance_depth: self.balance_depth,
170            #[cfg(debug_assertions)]
171            balance_nonlinear: self.balance_nonlinear,
172        }
173    }
174}
175
176#[derive(Debug, Clone, PartialEq, Eq, Hash)]
177enum ConstantKey {
178    Int(i64),
179    Float(u64),
180    String(String),
181    Bool(bool),
182    Nil,
183    Duration(i64),
184}
185
186impl From<&Constant> for ConstantKey {
187    fn from(value: &Constant) -> Self {
188        match value {
189            Constant::Int(value) => Self::Int(*value),
190            Constant::Float(value) => Self::Float(value.to_bits()),
191            Constant::String(value) => Self::String(value.clone()),
192            Constant::Bool(value) => Self::Bool(*value),
193            Constant::Nil => Self::Nil,
194            Constant::Duration(value) => Self::Duration(*value),
195        }
196    }
197}
198
199#[cfg(debug_assertions)]
200#[derive(Clone, Copy)]
201pub(crate) struct BalanceProbe {
202    depth: i32,
203    nonlinear: u32,
204}
205
206impl Default for Chunk {
207    fn default() -> Self {
208        Self::new()
209    }
210}
211
212/// The decoded contents of one artifact chunk.
213///
214/// A named struct rather than a positional argument list: the fields are mostly
215/// `Vec`s and `Option`s that would otherwise be easy to transpose silently at
216/// the one call site that builds a chunk back out of a verified artifact.
217pub(crate) struct ChunkParts {
218    pub(crate) code: Vec<u8>,
219    pub(crate) constants: Vec<Constant>,
220    pub(crate) lines: Vec<u32>,
221    pub(crate) columns: Vec<u32>,
222    pub(crate) source_file: Option<String>,
223    pub(crate) functions: Vec<Arc<CompiledFunction>>,
224    pub(crate) local_slots: Vec<LocalSlotInfo>,
225    pub(crate) binding_types: Vec<BindingTypeSlot>,
226    pub(crate) references_outer_names: bool,
227}
228
229impl Chunk {
230    pub(crate) fn from_artifact_parts(parts: ChunkParts) -> Self {
231        let ChunkParts {
232            code,
233            constants,
234            lines,
235            columns,
236            source_file,
237            functions,
238            local_slots,
239            binding_types,
240            references_outer_names,
241        } = parts;
242        Self {
243            code,
244            constants,
245            constant_index: None,
246            lines,
247            columns,
248            source_file,
249            current_col: 0,
250            functions,
251            local_slots,
252            binding_types,
253            references_outer_names,
254            #[cfg(debug_assertions)]
255            balance_depth: 0,
256            #[cfg(debug_assertions)]
257            balance_nonlinear: 0,
258        }
259    }
260
261    pub fn new() -> Self {
262        Self {
263            code: Vec::new(),
264            constants: Vec::new(),
265            constant_index: Some(HashMap::new()),
266            lines: Vec::new(),
267            columns: Vec::new(),
268            source_file: None,
269            current_col: 0,
270            functions: Vec::new(),
271            local_slots: Vec::new(),
272            binding_types: Vec::new(),
273            references_outer_names: false,
274            #[cfg(debug_assertions)]
275            balance_depth: 0,
276            #[cfg(debug_assertions)]
277            balance_nonlinear: 0,
278        }
279    }
280
281    pub fn set_column(&mut self, column: u32) {
282        self.current_col = column;
283    }
284
285    pub fn add_constant(&mut self, constant: Constant) -> u16 {
286        let index = self.constant_index.get_or_insert_with(|| {
287            self.constants
288                .iter()
289                .enumerate()
290                .filter_map(|(index, value)| {
291                    u16::try_from(index)
292                        .ok()
293                        .map(|index| (ConstantKey::from(value), index))
294                })
295                .collect()
296        });
297        let key = ConstantKey::from(&constant);
298        if let Some(existing) = index.get(&key) {
299            return *existing;
300        }
301        let slot =
302            u16::try_from(self.constants.len()).expect("constant pool exceeded u16 operand space");
303        self.constants.push(constant);
304        index.insert(key, slot);
305        slot
306    }
307
308    pub fn emit(&mut self, op: Op, line: u32) {
309        self.note_balance(op, 0);
310        self.push_bytes(&[op as u8], line);
311        if reads_outer_name(op) {
312            self.references_outer_names = true;
313        }
314    }
315
316    pub fn emit_u16(&mut self, op: Op, value: u16, line: u32) {
317        self.note_balance(op, value);
318        self.push_bytes(&[op as u8, (value >> 8) as u8, value as u8], line);
319        // A nested callback captures this function's environment, so its
320        // name reads need the same call-time bindings as direct reads.
321        if reads_outer_name(op)
322            || (op == Op::Closure
323                && self
324                    .functions
325                    .get(usize::from(value))
326                    .is_some_and(|function| function.chunk.references_outer_names))
327        {
328            self.references_outer_names = true;
329        }
330    }
331
332    /// Emit an instruction whose complete operand list consists of `u16`
333    /// values. The opcode schema remains the authority for arity and width.
334    pub fn emit_u16_operands(&mut self, op: Op, values: &[u16], line: u32) {
335        debug_assert_eq!(op.operands().len(), values.len());
336        debug_assert!(op.operands().iter().all(|operand| operand.width() == 2));
337        self.note_balance(op, values.first().copied().unwrap_or_default());
338        let mut bytes = Vec::with_capacity(op.instruction_len());
339        bytes.push(op as u8);
340        for value in values {
341            bytes.extend_from_slice(&value.to_be_bytes());
342        }
343        self.push_bytes(&bytes, line);
344        if reads_outer_name(op) {
345            self.references_outer_names = true;
346        }
347    }
348
349    pub fn emit_u8(&mut self, op: Op, value: u8, line: u32) {
350        self.note_balance(op, u16::from(value));
351        self.push_bytes(&[op as u8, value], line);
352        if reads_outer_name(op) {
353            self.references_outer_names = true;
354        }
355    }
356
357    pub fn emit_call_builtin(&mut self, id: BuiltinId, name: u16, argc: u8, line: u32) {
358        self.note_balance(Op::CallBuiltin, u16::from(argc));
359        let mut bytes = vec![Op::CallBuiltin as u8];
360        bytes.extend_from_slice(&id.raw().to_be_bytes());
361        bytes.extend_from_slice(&name.to_be_bytes());
362        bytes.push(argc);
363        self.push_bytes(&bytes, line);
364        self.references_outer_names = true;
365    }
366
367    pub fn emit_call_builtin_spread(&mut self, id: BuiltinId, name: u16, line: u32) {
368        let mut bytes = vec![Op::CallBuiltinSpread as u8];
369        bytes.extend_from_slice(&id.raw().to_be_bytes());
370        bytes.extend_from_slice(&name.to_be_bytes());
371        self.push_bytes(&bytes, line);
372        self.references_outer_names = true;
373    }
374
375    pub fn emit_method_call(&mut self, name: u16, argc: u8, line: u32) {
376        self.emit_method_call_inner(Op::MethodCall, name, argc, line);
377    }
378
379    pub fn emit_method_call_opt(&mut self, name: u16, argc: u8, line: u32) {
380        self.emit_method_call_inner(Op::MethodCallOpt, name, argc, line);
381    }
382
383    fn emit_method_call_inner(&mut self, op: Op, name: u16, argc: u8, line: u32) {
384        self.note_balance(op, u16::from(argc));
385        self.push_bytes(&[op as u8, (name >> 8) as u8, name as u8, argc], line);
386    }
387
388    pub fn emit_set_local_slot_property(&mut self, property: u16, slot: u16, line: u32) {
389        self.note_balance(Op::SetLocalSlotProperty, 0);
390        self.push_bytes(
391            &[
392                Op::SetLocalSlotProperty as u8,
393                (property >> 8) as u8,
394                property as u8,
395                (slot >> 8) as u8,
396                slot as u8,
397            ],
398            line,
399        );
400    }
401
402    fn push_bytes(&mut self, bytes: &[u8], line: u32) {
403        self.code.extend_from_slice(bytes);
404        self.lines.extend(std::iter::repeat_n(line, bytes.len()));
405        self.columns
406            .extend(std::iter::repeat_n(self.current_col, bytes.len()));
407    }
408
409    pub fn current_offset(&self) -> usize {
410        self.code.len()
411    }
412
413    pub fn emit_jump(&mut self, op: Op, line: u32) -> usize {
414        self.note_balance(op, 0);
415        let patch = self.code.len() + 1;
416        self.push_bytes(&[op as u8, 0xff, 0xff], line);
417        patch
418    }
419
420    pub fn patch_jump(&mut self, patch: usize) {
421        self.patch_jump_to(patch, self.code.len());
422    }
423
424    pub fn patch_jump_to(&mut self, patch: usize, target: usize) {
425        // The compiler's final addressability guard turns this provisional
426        // truncation into a structured compile error before the image escapes.
427        let target = target as u16;
428        self.code[patch..patch + 2].copy_from_slice(&target.to_be_bytes());
429    }
430
431    pub fn read_u16(&self, position: usize) -> u16 {
432        u16::from_be_bytes([self.code[position], self.code[position + 1]])
433    }
434
435    pub(crate) fn add_local_slot(
436        &mut self,
437        name: String,
438        mutable: bool,
439        scope_depth: usize,
440    ) -> u16 {
441        let slot = u16::try_from(self.local_slots.len()).expect("local slot count exceeded u16");
442        self.local_slots.push(LocalSlotInfo {
443            name,
444            mutable,
445            scope_depth,
446        });
447        slot
448    }
449
450    /// Intern a binding-type slot and return its `AssertBindingType` operand.
451    ///
452    /// Identical slots are shared: a loop body that rebinds the same annotated
453    /// name on every iteration, or a repeated `const path: string`, contributes
454    /// one table entry rather than one per occurrence.
455    pub(crate) fn add_binding_type(
456        &mut self,
457        name: &str,
458        type_expr: &TypeExpr,
459        nominal_type_names: &[String],
460    ) -> Option<u16> {
461        if let Some(index) = self.binding_types.iter().position(|slot| {
462            slot.name == name
463                && &slot.type_expr == type_expr
464                && slot.nominal_type_names == nominal_type_names
465        }) {
466            return u16::try_from(index).ok();
467        }
468        let index = u16::try_from(self.binding_types.len()).ok()?;
469        self.binding_types.push(BindingTypeSlot {
470            name: name.to_string(),
471            type_expr: type_expr.clone(),
472            nominal_type_names: nominal_type_names.to_vec(),
473        });
474        Some(index)
475    }
476
477    #[cfg(debug_assertions)]
478    pub(crate) fn balance_probe(&self) -> BalanceProbe {
479        BalanceProbe {
480            depth: self.balance_depth,
481            nonlinear: self.balance_nonlinear,
482        }
483    }
484
485    #[cfg(debug_assertions)]
486    pub(crate) fn balance_delta_since(&self, probe: BalanceProbe) -> Option<i32> {
487        (self.balance_nonlinear == probe.nonlinear).then_some(self.balance_depth - probe.depth)
488    }
489
490    #[cfg(debug_assertions)]
491    fn note_balance(&mut self, op: Op, count: u16) {
492        match stack_delta(op, count) {
493            Some(delta) => self.balance_depth += delta,
494            None => self.balance_nonlinear += 1,
495        }
496    }
497
498    #[cfg(not(debug_assertions))]
499    fn note_balance(&mut self, _op: Op, _count: u16) {}
500
501    pub fn disassemble(&self, name: &str) -> String {
502        let mut output = format!("== {name} ==\n");
503        let mut ip = 0;
504        while let Some(byte) = self.code.get(ip).copied() {
505            let offset = ip;
506            let line = self.lines.get(ip).copied().unwrap_or(0);
507            let Some(op) = Op::from_byte(byte) else { break };
508            ip += 1;
509            let rendered = self.disassemble_instruction(op, &mut ip);
510            debug_assert_eq!(
511                ip,
512                offset + op.instruction_len(),
513                "disassembler operand width drifted for {}",
514                op.name(),
515            );
516            output.push_str(&format!("{offset:04} [{line:>4}] {rendered}\n"));
517        }
518        output
519    }
520
521    fn disassemble_instruction(&self, op: Op, ip: &mut usize) -> String {
522        let label = opcode_label(op.name());
523        let read_u16 = |position: usize| {
524            self.code
525                .get(position..position + 2)
526                .map(|bytes| u16::from_be_bytes([bytes[0], bytes[1]]))
527        };
528        if matches!(
529            op,
530            Op::Constant
531                | Op::GetVar
532                | Op::DefLet
533                | Op::DefVar
534                | Op::DefCell
535                | Op::SetVar
536                | Op::GetProperty
537                | Op::GetPropertyOpt
538                | Op::Import
539        ) {
540            let Some(index) = read_u16(*ip) else {
541                return label;
542            };
543            *ip += 2;
544            return match self.constants.get(index as usize) {
545                Some(value) => format!("{label} {index:>4} ({value})"),
546                None => format!("{label} {index:>4}"),
547            };
548        }
549        if op == Op::SetProperty {
550            let Some(property) = read_u16(*ip) else {
551                return label;
552            };
553            let Some(binding) = read_u16(*ip + 2) else {
554                return label;
555            };
556            *ip += 4;
557            let render = |index: u16| {
558                self.constants
559                    .get(index as usize)
560                    .map(ToString::to_string)
561                    .unwrap_or_default()
562            };
563            return format!(
564                "{label} property {property:>4} ({}) binding {binding:>4} ({})",
565                render(property),
566                render(binding)
567            );
568        }
569        if matches!(
570            op,
571            Op::GetLocalSlot
572                | Op::DefLocalSlot
573                | Op::SetLocalSlot
574                | Op::SetLocalSlotSubscript
575                | Op::ConcatAssignLocal
576        ) {
577            let Some(slot) = read_u16(*ip) else {
578                return label;
579            };
580            *ip += 2;
581            return match self.local_slots.get(slot as usize) {
582                Some(info) => format!("{label} {slot:>4} ({})", info.name),
583                None => format!("{label} {slot:>4}"),
584            };
585        }
586        if op == Op::SetLocalSlotProperty {
587            let Some(property) = read_u16(*ip) else {
588                return label;
589            };
590            let Some(slot) = read_u16(*ip + 2) else {
591                return label;
592            };
593            *ip += 4;
594            let property = self
595                .constants
596                .get(property as usize)
597                .map(ToString::to_string)
598                .unwrap_or_default();
599            return format!("{label} {slot:>4} {property}");
600        }
601        if matches!(op, Op::MethodCall | Op::MethodCallOpt) {
602            let Some(name) = read_u16(*ip) else {
603                return label;
604            };
605            let Some(argc) = self.code.get(*ip + 2).copied() else {
606                return label;
607            };
608            *ip += 3;
609            let name = self
610                .constants
611                .get(name as usize)
612                .map(ToString::to_string)
613                .unwrap_or_default();
614            return format!("{label} {argc:>4} ({name})");
615        }
616        if matches!(op, Op::Call | Op::TailCall) {
617            let Some(argc) = self.code.get(*ip).copied() else {
618                return label;
619            };
620            *ip += 1;
621            return format!("{label} {argc:>4}");
622        }
623        let width = instruction_len(op, &self.code[(*ip).saturating_sub(1)..]).unwrap_or(1);
624        if width == 3 {
625            let Some(value) = read_u16(*ip) else {
626                return label;
627            };
628            *ip += 2;
629            return format!("{label} {value:>4}");
630        }
631        if width > 1 {
632            *ip = (*ip).saturating_add(width - 1).min(self.code.len());
633        }
634        label
635    }
636}
637
638fn opcode_label(name: &str) -> String {
639    let mut output = String::new();
640    for (index, ch) in name.chars().enumerate() {
641        if index > 0 && ch.is_ascii_uppercase() {
642            output.push('_');
643        }
644        output.push(ch.to_ascii_uppercase());
645    }
646    output
647}
648
649fn reads_outer_name(op: Op) -> bool {
650    matches!(
651        op,
652        Op::GetVar
653            | Op::SetVar
654            | Op::Call
655            | Op::TailCall
656            | Op::Pipe
657            | Op::CheckType
658            | Op::CallSpread
659            | Op::CallBuiltin
660            | Op::CallBuiltinSpread
661    )
662}
663
664pub fn instruction_len(op: Op, _remaining: &[u8]) -> Option<usize> {
665    Some(op.instruction_len())
666}
667
668#[cfg(debug_assertions)]
669fn stack_delta(op: Op, count: u16) -> Option<i32> {
670    use Op::*;
671    let count = i32::from(count);
672    Some(match op {
673        Constant | Nil | True | False | RootHarness | GetVar | GetArgc | GetLocalSlot | Closure
674        | Dup => 1,
675        DefLet | DefVar | DefCell | SetVar | DefLocalSlot | SetLocalSlot | SetProperty
676        | SetLocalSlotProperty | ConcatAssignLocal | Pop => -1,
677        Negate | Not | GetProperty | GetPropertyOpt | CheckType | TryUnwrap | TryWrapOk | Swap
678        | PushScope | PopScope | PopIterator | PopHandler | AssertBindingType => 0,
679        Add | Sub | Mul | Div | Mod | Pow | AddInt | SubInt | MulInt | DivInt | ModInt
680        | AddFloat | SubFloat | MulFloat | DivFloat | ModFloat | Equal | NotEqual | Less
681        | Greater | LessEqual | GreaterEqual | EqualInt | NotEqualInt | LessInt | GreaterInt
682        | LessEqualInt | GreaterEqualInt | EqualFloat | NotEqualFloat | LessFloat
683        | GreaterFloat | LessEqualFloat | GreaterEqualFloat | EqualBool | NotEqualBool
684        | EqualString | NotEqualString | Contains | Subscript | SubscriptOpt => -1,
685        IterInit => -1,
686        Slice | SetSubscript | SetLocalSlotSubscript => -2,
687        BuildList | Concat | CallBuiltin => 1 - count,
688        BuildDict => 1 - 2 * count,
689        Call | MethodCall | MethodCallOpt => -count,
690        Jump
691        | JumpIfFalse
692        | JumpIfTrue
693        | IterNext
694        | Return
695        | TailCall
696        | Throw
697        | ThrowDeclared
698        | Rethrow
699        | TryCatchSetup
700        | TryCatchPreserve
701        | Spawn
702        | Pipe
703        | Parallel
704        | ParallelMap
705        | ParallelMapStream
706        | ParallelSettle
707        | SyncMutexEnter
708        | SyncMutexEnterKeyed
709        | TaskScopeEnter
710        | TaskScopeExit
711        | Import
712        | SelectiveImport
713        | NamespaceImport
714        | NamespaceImportMembers
715        | DeadlineSetup
716        | DeadlineEnd
717        | BuildEnum
718        | MatchEnum
719        | Yield
720        | CallSpread
721        | CallBuiltinSpread
722        | MethodCallSpread => return None,
723    })
724}
harn_kernel/program.rs

harn_kernel/
program.rs
