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

harn_kernel/
program.rs
