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        if reads_outer_name(op) {
320            self.references_outer_names = true;
321        }
322    }
323
324    /// Emit an instruction whose complete operand list consists of `u16`
325    /// values. The opcode schema remains the authority for arity and width.
326    pub fn emit_u16_operands(&mut self, op: Op, values: &[u16], line: u32) {
327        debug_assert_eq!(op.operands().len(), values.len());
328        debug_assert!(op.operands().iter().all(|operand| operand.width() == 2));
329        self.note_balance(op, values.first().copied().unwrap_or_default());
330        let mut bytes = Vec::with_capacity(op.instruction_len());
331        bytes.push(op as u8);
332        for value in values {
333            bytes.extend_from_slice(&value.to_be_bytes());
334        }
335        self.push_bytes(&bytes, line);
336        if reads_outer_name(op) {
337            self.references_outer_names = true;
338        }
339    }
340
341    pub fn emit_u8(&mut self, op: Op, value: u8, line: u32) {
342        self.note_balance(op, u16::from(value));
343        self.push_bytes(&[op as u8, value], line);
344        if reads_outer_name(op) {
345            self.references_outer_names = true;
346        }
347    }
348
349    pub fn emit_call_builtin(&mut self, id: BuiltinId, name: u16, argc: u8, line: u32) {
350        self.note_balance(Op::CallBuiltin, u16::from(argc));
351        let mut bytes = vec![Op::CallBuiltin as u8];
352        bytes.extend_from_slice(&id.raw().to_be_bytes());
353        bytes.extend_from_slice(&name.to_be_bytes());
354        bytes.push(argc);
355        self.push_bytes(&bytes, line);
356        self.references_outer_names = true;
357    }
358
359    pub fn emit_call_builtin_spread(&mut self, id: BuiltinId, name: u16, line: u32) {
360        let mut bytes = vec![Op::CallBuiltinSpread as u8];
361        bytes.extend_from_slice(&id.raw().to_be_bytes());
362        bytes.extend_from_slice(&name.to_be_bytes());
363        self.push_bytes(&bytes, line);
364        self.references_outer_names = true;
365    }
366
367    pub fn emit_method_call(&mut self, name: u16, argc: u8, line: u32) {
368        self.emit_method_call_inner(Op::MethodCall, name, argc, line);
369    }
370
371    pub fn emit_method_call_opt(&mut self, name: u16, argc: u8, line: u32) {
372        self.emit_method_call_inner(Op::MethodCallOpt, name, argc, line);
373    }
374
375    fn emit_method_call_inner(&mut self, op: Op, name: u16, argc: u8, line: u32) {
376        self.note_balance(op, u16::from(argc));
377        self.push_bytes(&[op as u8, (name >> 8) as u8, name as u8, argc], line);
378    }
379
380    pub fn emit_set_local_slot_property(&mut self, property: u16, slot: u16, line: u32) {
381        self.note_balance(Op::SetLocalSlotProperty, 0);
382        self.push_bytes(
383            &[
384                Op::SetLocalSlotProperty as u8,
385                (property >> 8) as u8,
386                property as u8,
387                (slot >> 8) as u8,
388                slot as u8,
389            ],
390            line,
391        );
392    }
393
394    fn push_bytes(&mut self, bytes: &[u8], line: u32) {
395        self.code.extend_from_slice(bytes);
396        self.lines.extend(std::iter::repeat_n(line, bytes.len()));
397        self.columns
398            .extend(std::iter::repeat_n(self.current_col, bytes.len()));
399    }
400
401    pub fn current_offset(&self) -> usize {
402        self.code.len()
403    }
404
405    pub fn emit_jump(&mut self, op: Op, line: u32) -> usize {
406        self.note_balance(op, 0);
407        let patch = self.code.len() + 1;
408        self.push_bytes(&[op as u8, 0xff, 0xff], line);
409        patch
410    }
411
412    pub fn patch_jump(&mut self, patch: usize) {
413        self.patch_jump_to(patch, self.code.len());
414    }
415
416    pub fn patch_jump_to(&mut self, patch: usize, target: usize) {
417        // The compiler's final addressability guard turns this provisional
418        // truncation into a structured compile error before the image escapes.
419        let target = target as u16;
420        self.code[patch..patch + 2].copy_from_slice(&target.to_be_bytes());
421    }
422
423    pub fn read_u16(&self, position: usize) -> u16 {
424        u16::from_be_bytes([self.code[position], self.code[position + 1]])
425    }
426
427    pub(crate) fn add_local_slot(
428        &mut self,
429        name: String,
430        mutable: bool,
431        scope_depth: usize,
432    ) -> u16 {
433        let slot = u16::try_from(self.local_slots.len()).expect("local slot count exceeded u16");
434        self.local_slots.push(LocalSlotInfo {
435            name,
436            mutable,
437            scope_depth,
438        });
439        slot
440    }
441
442    /// Intern a binding-type slot and return its `AssertBindingType` operand.
443    ///
444    /// Identical slots are shared: a loop body that rebinds the same annotated
445    /// name on every iteration, or a repeated `const path: string`, contributes
446    /// one table entry rather than one per occurrence.
447    pub(crate) fn add_binding_type(
448        &mut self,
449        name: &str,
450        type_expr: &TypeExpr,
451        nominal_type_names: &[String],
452    ) -> Option<u16> {
453        if let Some(index) = self.binding_types.iter().position(|slot| {
454            slot.name == name
455                && &slot.type_expr == type_expr
456                && slot.nominal_type_names == nominal_type_names
457        }) {
458            return u16::try_from(index).ok();
459        }
460        let index = u16::try_from(self.binding_types.len()).ok()?;
461        self.binding_types.push(BindingTypeSlot {
462            name: name.to_string(),
463            type_expr: type_expr.clone(),
464            nominal_type_names: nominal_type_names.to_vec(),
465        });
466        Some(index)
467    }
468
469    #[cfg(debug_assertions)]
470    pub(crate) fn balance_probe(&self) -> BalanceProbe {
471        BalanceProbe {
472            depth: self.balance_depth,
473            nonlinear: self.balance_nonlinear,
474        }
475    }
476
477    #[cfg(debug_assertions)]
478    pub(crate) fn balance_delta_since(&self, probe: BalanceProbe) -> Option<i32> {
479        (self.balance_nonlinear == probe.nonlinear).then_some(self.balance_depth - probe.depth)
480    }
481
482    #[cfg(debug_assertions)]
483    fn note_balance(&mut self, op: Op, count: u16) {
484        match stack_delta(op, count) {
485            Some(delta) => self.balance_depth += delta,
486            None => self.balance_nonlinear += 1,
487        }
488    }
489
490    #[cfg(not(debug_assertions))]
491    fn note_balance(&mut self, _op: Op, _count: u16) {}
492
493    pub fn disassemble(&self, name: &str) -> String {
494        let mut output = format!("== {name} ==\n");
495        let mut ip = 0;
496        while let Some(byte) = self.code.get(ip).copied() {
497            let offset = ip;
498            let line = self.lines.get(ip).copied().unwrap_or(0);
499            let Some(op) = Op::from_byte(byte) else { break };
500            ip += 1;
501            let rendered = self.disassemble_instruction(op, &mut ip);
502            debug_assert_eq!(
503                ip,
504                offset + op.instruction_len(),
505                "disassembler operand width drifted for {}",
506                op.name(),
507            );
508            output.push_str(&format!("{offset:04} [{line:>4}] {rendered}\n"));
509        }
510        output
511    }
512
513    fn disassemble_instruction(&self, op: Op, ip: &mut usize) -> String {
514        let label = opcode_label(op.name());
515        let read_u16 = |position: usize| {
516            self.code
517                .get(position..position + 2)
518                .map(|bytes| u16::from_be_bytes([bytes[0], bytes[1]]))
519        };
520        if matches!(
521            op,
522            Op::Constant
523                | Op::GetVar
524                | Op::DefLet
525                | Op::DefVar
526                | Op::DefCell
527                | Op::SetVar
528                | Op::GetProperty
529                | Op::GetPropertyOpt
530                | Op::Import
531        ) {
532            let Some(index) = read_u16(*ip) else {
533                return label;
534            };
535            *ip += 2;
536            return match self.constants.get(index as usize) {
537                Some(value) => format!("{label} {index:>4} ({value})"),
538                None => format!("{label} {index:>4}"),
539            };
540        }
541        if op == Op::SetProperty {
542            let Some(property) = read_u16(*ip) else {
543                return label;
544            };
545            let Some(binding) = read_u16(*ip + 2) else {
546                return label;
547            };
548            *ip += 4;
549            let render = |index: u16| {
550                self.constants
551                    .get(index as usize)
552                    .map(ToString::to_string)
553                    .unwrap_or_default()
554            };
555            return format!(
556                "{label} property {property:>4} ({}) binding {binding:>4} ({})",
557                render(property),
558                render(binding)
559            );
560        }
561        if matches!(
562            op,
563            Op::GetLocalSlot
564                | Op::DefLocalSlot
565                | Op::SetLocalSlot
566                | Op::SetLocalSlotSubscript
567                | Op::ConcatAssignLocal
568        ) {
569            let Some(slot) = read_u16(*ip) else {
570                return label;
571            };
572            *ip += 2;
573            return match self.local_slots.get(slot as usize) {
574                Some(info) => format!("{label} {slot:>4} ({})", info.name),
575                None => format!("{label} {slot:>4}"),
576            };
577        }
578        if op == Op::SetLocalSlotProperty {
579            let Some(property) = read_u16(*ip) else {
580                return label;
581            };
582            let Some(slot) = read_u16(*ip + 2) else {
583                return label;
584            };
585            *ip += 4;
586            let property = self
587                .constants
588                .get(property as usize)
589                .map(ToString::to_string)
590                .unwrap_or_default();
591            return format!("{label} {slot:>4} {property}");
592        }
593        if matches!(op, Op::MethodCall | Op::MethodCallOpt) {
594            let Some(name) = read_u16(*ip) else {
595                return label;
596            };
597            let Some(argc) = self.code.get(*ip + 2).copied() else {
598                return label;
599            };
600            *ip += 3;
601            let name = self
602                .constants
603                .get(name as usize)
604                .map(ToString::to_string)
605                .unwrap_or_default();
606            return format!("{label} {argc:>4} ({name})");
607        }
608        if matches!(op, Op::Call | Op::TailCall) {
609            let Some(argc) = self.code.get(*ip).copied() else {
610                return label;
611            };
612            *ip += 1;
613            return format!("{label} {argc:>4}");
614        }
615        let width = instruction_len(op, &self.code[(*ip).saturating_sub(1)..]).unwrap_or(1);
616        if width == 3 {
617            let Some(value) = read_u16(*ip) else {
618                return label;
619            };
620            *ip += 2;
621            return format!("{label} {value:>4}");
622        }
623        if width > 1 {
624            *ip = (*ip).saturating_add(width - 1).min(self.code.len());
625        }
626        label
627    }
628}
629
630fn opcode_label(name: &str) -> String {
631    let mut output = String::new();
632    for (index, ch) in name.chars().enumerate() {
633        if index > 0 && ch.is_ascii_uppercase() {
634            output.push('_');
635        }
636        output.push(ch.to_ascii_uppercase());
637    }
638    output
639}
640
641fn reads_outer_name(op: Op) -> bool {
642    matches!(
643        op,
644        Op::GetVar
645            | Op::SetVar
646            | Op::Call
647            | Op::TailCall
648            | Op::Pipe
649            | Op::CheckType
650            | Op::CallSpread
651            | Op::CallBuiltin
652            | Op::CallBuiltinSpread
653    )
654}
655
656pub fn instruction_len(op: Op, _remaining: &[u8]) -> Option<usize> {
657    Some(op.instruction_len())
658}
659
660#[cfg(debug_assertions)]
661fn stack_delta(op: Op, count: u16) -> Option<i32> {
662    use Op::*;
663    let count = i32::from(count);
664    Some(match op {
665        Constant | Nil | True | False | RootHarness | GetVar | GetArgc | GetLocalSlot | Closure
666        | Dup => 1,
667        DefLet | DefVar | DefCell | SetVar | DefLocalSlot | SetLocalSlot | SetProperty
668        | SetLocalSlotProperty | ConcatAssignLocal | Pop => -1,
669        Negate | Not | GetProperty | GetPropertyOpt | CheckType | TryUnwrap | TryWrapOk | Swap
670        | PushScope | PopScope | PopIterator | PopHandler | AssertBindingType => 0,
671        Add | Sub | Mul | Div | Mod | Pow | AddInt | SubInt | MulInt | DivInt | ModInt
672        | AddFloat | SubFloat | MulFloat | DivFloat | ModFloat | Equal | NotEqual | Less
673        | Greater | LessEqual | GreaterEqual | EqualInt | NotEqualInt | LessInt | GreaterInt
674        | LessEqualInt | GreaterEqualInt | EqualFloat | NotEqualFloat | LessFloat
675        | GreaterFloat | LessEqualFloat | GreaterEqualFloat | EqualBool | NotEqualBool
676        | EqualString | NotEqualString | Contains | Subscript | SubscriptOpt => -1,
677        IterInit => -1,
678        Slice | SetSubscript | SetLocalSlotSubscript => -2,
679        BuildList | Concat | CallBuiltin => 1 - count,
680        BuildDict => 1 - 2 * count,
681        Call | MethodCall | MethodCallOpt => -count,
682        Jump
683        | JumpIfFalse
684        | JumpIfTrue
685        | IterNext
686        | Return
687        | TailCall
688        | Throw
689        | TryCatchSetup
690        | Spawn
691        | Pipe
692        | Parallel
693        | ParallelMap
694        | ParallelMapStream
695        | ParallelSettle
696        | SyncMutexEnter
697        | SyncMutexEnterKeyed
698        | TaskScopeEnter
699        | TaskScopeExit
700        | Import
701        | SelectiveImport
702        | NamespaceImport
703        | NamespaceImportMembers
704        | DeadlineSetup
705        | DeadlineEnd
706        | BuildEnum
707        | MatchEnum
708        | Yield
709        | CallSpread
710        | CallBuiltinSpread
711        | MethodCallSpread => return None,
712    })
713}
harn_kernel/program.rs

harn_kernel/
program.rs
