cove_ir/bytecode/
encode.rs

1//! `Inst` to sixteen bytes.
2//!
3//! The encoder is **total**: ADR 0041's audit covers all forty-nine variants,
4//! so there is no instruction it can refuse and no fallback to enum execution
5//! to design around. The one thing it can answer `Err` about is an operand
6//! that does not fit — a slot past 65,535, which the compiler's own frame
7//! limit already refuses at the declaration, and a branch displacement that
8//! overflows, which no pair of `u32` program counters can produce. Both are
9//! checked anyway, because *"the encoder rejects overflow"* should be a line
10//! of code rather than an argument.
11//!
12//! It is **deterministic**: encoding is a pure function of the instruction and
13//! its program counter, every field an opcode does not use is written zero,
14//! and two encodings of one program are byte-identical.
15
16use crate::inst::{Inst, Len, Pc, Slot};
17use crate::program::{Function, Program};
18
19use super::op::Op;
20use super::EncodedInst;
21
22/// An operand that does not fit the field ADR 0041 gives it.
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
24pub enum TooWide {
25    /// A slot a sixteen-bit operand cannot name.
26    ///
27    /// `crate::lower` refuses a frame of more than
28    /// [`MAX_FRAME_WORDS`](super::MAX_FRAME_WORDS) with a diagnostic at the
29    /// declaration, so a program that reached the encoder cannot hold one.
30    /// This is the assertion that says so.
31    Slot { slot: Slot },
32    /// A branch whose displacement is not an `i64`.
33    ///
34    /// Unreachable while [`Pc`] is a `u32`: every representable pair of
35    /// program counters has a representable difference. It is checked so that
36    /// a wider `Pc` is a refusal here rather than a wrong jump somewhere else.
37    Displacement { from: Pc, to: Pc },
38}
39
40impl std::fmt::Display for TooWide {
41    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
42        match self {
43            TooWide::Slot { slot } => write!(
44                f,
45                "slot {slot} cannot be encoded: a slot operand is sixteen bits, so the largest \
46                 is {}",
47                u16::MAX
48            ),
49            TooWide::Displacement { from, to } => {
50                write!(f, "a branch from {from} to {to} has no displacement")
51            }
52        }
53    }
54}
55
56/// A whole program's instructions, encoded, one run per function.
57///
58/// Parallel to [`Program::functions`], because a 1:1 encoding keeps a
59/// function's program counters exactly as they were: `code[id][pc]` is the
60/// encoding of `program.functions[id].code[pc]`, and everything indexed by pc
61/// — spans, local ranges, switch targets — goes on meaning what it meant.
62#[derive(Clone, Debug, Default, PartialEq, Eq)]
63pub struct Encoded {
64    pub functions: Vec<Vec<EncodedInst>>,
65}
66
67impl Encoded {
68    /// One function's instructions.
69    pub fn function(&self, id: crate::FunctionId) -> &[EncodedInst] {
70        &self.functions[id.index()]
71    }
72
73    /// How many bytes the whole program's code occupies.
74    pub fn bytes(&self) -> usize {
75        self.functions
76            .iter()
77            .map(|code| code.len() * EncodedInst::BYTES)
78            .sum()
79    }
80}
81
82/// Encodes every function of a program.
83pub fn encode_program(program: &Program) -> Result<Encoded, TooWide> {
84    let mut functions = Vec::with_capacity(program.functions.len());
85    for function in &program.functions {
86        functions.push(encode_function(function)?);
87    }
88    Ok(Encoded { functions })
89}
90
91/// Encodes one function's code.
92pub fn encode_function(function: &Function) -> Result<Vec<EncodedInst>, TooWide> {
93    function
94        .code
95        .iter()
96        .enumerate()
97        .map(|(pc, inst)| encode(inst, pc as Pc))
98        .collect()
99}
100
101/// Encodes one instruction.
102///
103/// `pc` is where the instruction sits, and only a branch reads it: ADR 0041
104/// makes [`Inst::Jump`] and [`Inst::BranchFalse`] carry `to - (pc + 1)`, so
105/// that a target is a displacement rather than an absolute address.
106pub fn encode(inst: &Inst, pc: Pc) -> Result<EncodedInst, TooWide> {
107    let build = |op: Op, a: u16, b: u16, c: u16, payload: u64| {
108        EncodedInst::new(op.number(), a, b, c, payload)
109    };
110    Ok(match *inst {
111        // ---- constants and moves ------------------------------------------
112        Inst::Unit { dst } => build(Op::ConstUnit, slot(dst)?, 0, 0, 0),
113        Inst::Bool { dst, value } => build(Op::ConstBool, slot(dst)?, 0, 0, u64::from(value)),
114        Inst::Int { dst, value } => build(Op::ConstInt, slot(dst)?, 0, 0, value as u64),
115        Inst::Tag { dst, layout, case } => {
116            build(Op::ConstTag, slot(dst)?, 0, 0, halves(case.0, layout.0))
117        }
118        Inst::FuncRef { dst, callee } => build(Op::FuncRef, slot(dst)?, 0, 0, halves(callee.0, 0)),
119        Inst::Float { dst, bits } => build(Op::ConstFloat, slot(dst)?, 0, 0, bits),
120        Inst::Str { dst, text } => build(Op::Str, slot(dst)?, 0, 0, halves(text.0, 0)),
121        Inst::Copy { dst, src, layout } => {
122            build(Op::Copy, slot(dst)?, slot(src)?, 0, halves(layout.0, 0))
123        }
124        Inst::Clear { slot: at, layout } => build(Op::Clear, slot(at)?, 0, 0, halves(layout.0, 0)),
125
126        // ---- scalar operations --------------------------------------------
127        Inst::Neg { num, dst, a } => build(Op::Neg(num), slot(dst)?, slot(a)?, 0, 0),
128        Inst::Arith { num, op, dst, a, b } => {
129            build(Op::Arith(num, op), slot(dst)?, slot(a)?, slot(b)?, 0)
130        }
131        Inst::Cmp { on, op, dst, a, b } => {
132            build(Op::Cmp(on, op), slot(dst)?, slot(a)?, slot(b)?, 0)
133        }
134        Inst::ArithImm { op, dst, a, value } => {
135            build(Op::ArithImm(op), slot(dst)?, slot(a)?, 0, value as u64)
136        }
137        Inst::CmpImm { op, dst, a, value } => {
138            build(Op::CmpImm(op), slot(dst)?, slot(a)?, 0, value as u64)
139        }
140        Inst::Not { dst, a } => build(Op::Not, slot(dst)?, slot(a)?, 0, 0),
141        Inst::Convert { to, dst, a } => build(Op::Convert(to), slot(dst)?, slot(a)?, 0, 0),
142
143        // ---- control flow --------------------------------------------------
144        Inst::Jump { to } => build(Op::Jump, 0, 0, 0, displacement(pc, to)? as u64),
145        Inst::BranchFalse { cond, to } => build(
146            Op::BranchFalse,
147            slot(cond)?,
148            0,
149            0,
150            displacement(pc, to)? as u64,
151        ),
152        Inst::Switch { on, table } => build(Op::Switch, slot(on)?, 0, 0, halves(table.0, 0)),
153        Inst::Return { src } => build(Op::Return, slot(src)?, 0, 0, 0),
154
155        // ---- calls ----------------------------------------------------------
156        Inst::Call { dst, callee, args } => {
157            build(Op::Call, slot(dst)?, 0, 0, halves(callee.0, args.0))
158        }
159        Inst::CallClosure {
160            dst,
161            closure,
162            args,
163            result,
164        } => build(
165            Op::CallClosure,
166            slot(dst)?,
167            slot(closure)?,
168            0,
169            halves(args.0, result.0),
170        ),
171        Inst::CallHost { dst, op, args } => {
172            build(Op::CallHost, slot(dst)?, 0, 0, halves(op.0, args.0))
173        }
174        Inst::CallResource {
175            dst,
176            receiver,
177            op,
178            args,
179        } => build(
180            Op::CallResource,
181            slot(dst)?,
182            slot(receiver)?,
183            0,
184            halves(op.0, args.0),
185        ),
186        Inst::CallBuiltin { dst, builtin, args } => {
187            build(Op::CallBuiltin, slot(dst)?, 0, 0, halves(builtin.0, args.0))
188        }
189
190        // ---- the heap --------------------------------------------------------
191        // Three opcodes rather than a discriminant in a field: `Len`'s three
192        // forms are three encodings, and nothing stores which one it is.
193        Inst::Alloc { dst, layout, len } => match len {
194            Len::Fixed => build(Op::AllocFixed, slot(dst)?, 0, 0, halves(layout.0, 0)),
195            Len::Count(n) => build(Op::AllocImm, slot(dst)?, 0, 0, halves(layout.0, n)),
196            Len::Slot(at) => build(Op::AllocSlot, slot(dst)?, slot(at)?, 0, halves(layout.0, 0)),
197        },
198        Inst::LoadField {
199            dst,
200            obj,
201            at,
202            layout,
203        } => build(
204            Op::LoadField,
205            slot(dst)?,
206            slot(obj)?,
207            0,
208            halves(at, layout.0),
209        ),
210        Inst::StoreField {
211            obj,
212            at,
213            src,
214            layout,
215        } => build(
216            Op::StoreField,
217            slot(obj)?,
218            slot(src)?,
219            0,
220            halves(at, layout.0),
221        ),
222        Inst::LoadElem {
223            dst,
224            obj,
225            index,
226            layout,
227        } => build(
228            Op::LoadElem,
229            slot(dst)?,
230            slot(obj)?,
231            slot(index)?,
232            halves(layout.0, 0),
233        ),
234        Inst::StoreElem {
235            obj,
236            index,
237            src,
238            layout,
239        } => build(
240            Op::StoreElem,
241            slot(obj)?,
242            slot(index)?,
243            slot(src)?,
244            halves(layout.0, 0),
245        ),
246        Inst::ByteAt { dst, obj, at } => build(Op::ByteAt, slot(dst)?, slot(obj)?, slot(at)?, 0),
247        Inst::AllocBytes { dst, len } => build(Op::AllocBytes, slot(dst)?, slot(len)?, 0, 0),
248        Inst::WriteByte { bytes, at, value } => {
249            build(Op::WriteByte, slot(bytes)?, slot(at)?, slot(value)?, 0)
250        }
251        Inst::CopyBytes { args } => build(Op::CopyBytes, 0, 0, 0, halves(args.0, 0)),
252        Inst::FinishString { dst, bytes } => {
253            build(Op::FinishString, slot(dst)?, slot(bytes)?, 0, 0)
254        }
255        Inst::AllocBuffer { dst, capacity } => {
256            build(Op::AllocBuffer, slot(dst)?, slot(capacity)?, 0, 0)
257        }
258        Inst::AppendByte { buffer, value } => {
259            build(Op::AppendByte, slot(buffer)?, slot(value)?, 0, 0)
260        }
261        Inst::AppendBytes { args } => build(Op::AppendBytes, 0, 0, 0, halves(args.0, 0)),
262        Inst::FinishBuffer { dst, buffer } => {
263            build(Op::FinishBuffer, slot(dst)?, slot(buffer)?, 0, 0)
264        }
265        Inst::Len { dst, obj } => build(Op::Len, slot(dst)?, slot(obj)?, 0, 0),
266        Inst::LayoutOf { dst, obj } => build(Op::LayoutOf, slot(dst)?, slot(obj)?, 0, 0),
267
268        // ---- places ----------------------------------------------------------
269        Inst::AddrOfSlot { dst, slot: at } => build(Op::AddrOfSlot, slot(dst)?, slot(at)?, 0, 0),
270        Inst::AddrOfField { dst, obj, at } => {
271            build(Op::AddrOfField, slot(dst)?, slot(obj)?, 0, halves(at, 0))
272        }
273        Inst::AddrOfElem {
274            dst,
275            obj,
276            index,
277            layout,
278        } => build(
279            Op::AddrOfElem,
280            slot(dst)?,
281            slot(obj)?,
282            slot(index)?,
283            halves(layout.0, 0),
284        ),
285        Inst::AddrOfPart { dst, addr, at } => {
286            build(Op::AddrOfPart, slot(dst)?, slot(addr)?, 0, halves(at, 0))
287        }
288        Inst::Load { dst, addr, layout } => {
289            build(Op::Load, slot(dst)?, slot(addr)?, 0, halves(layout.0, 0))
290        }
291        Inst::Store { addr, src, layout } => {
292            build(Op::Store, slot(addr)?, slot(src)?, 0, halves(layout.0, 0))
293        }
294
295        // ---- erasure ----------------------------------------------------------
296        Inst::Box { dst, src, layout } => {
297            build(Op::Box, slot(dst)?, slot(src)?, 0, halves(layout.0, 0))
298        }
299        Inst::Unbox { dst, src, layout } => {
300            build(Op::Unbox, slot(dst)?, slot(src)?, 0, halves(layout.0, 0))
301        }
302
303        // ---- tasks -------------------------------------------------------------
304        Inst::ScopeEnter { dst, name } => {
305            build(Op::ScopeEnter, slot(dst)?, 0, 0, halves(name.0, 0))
306        }
307        Inst::ScopeLeave {
308            scope,
309            failed,
310            error,
311            layout,
312        } => build(
313            Op::ScopeLeave,
314            slot(scope)?,
315            slot(failed)?,
316            slot(error)?,
317            halves(layout.0, 0),
318        ),
319        Inst::ScopeCancel { scope } => build(Op::ScopeCancel, slot(scope)?, 0, 0, 0),
320        Inst::Spawn {
321            dst,
322            scope,
323            closure,
324            answer,
325        } => build(
326            Op::Spawn,
327            slot(dst)?,
328            slot(scope)?,
329            slot(closure)?,
330            halves(answer.0, 0),
331        ),
332        Inst::Await { dst, task, answer } => {
333            build(Op::Await, slot(dst)?, slot(task)?, 0, halves(answer.0, 0))
334        }
335        Inst::Cancel { task } => build(Op::Cancel, slot(task)?, 0, 0, 0),
336        Inst::Settled { dst, src, answer } => {
337            build(Op::Settled, slot(dst)?, slot(src)?, 0, halves(answer.0, 0))
338        }
339
340        // ---- cells ---------------------------------------------------------------
341        Inst::SharedLock { cell } => build(Op::SharedLock, slot(cell)?, 0, 0, 0),
342        Inst::SharedUnlock { cell } => build(Op::SharedUnlock, slot(cell)?, 0, 0, 0),
343
344        // ---- failure ----------------------------------------------------------
345        Inst::Trap { message } => build(Op::Trap, 0, 0, 0, halves(message.0, 0)),
346        Inst::AssertFailed { message } => build(Op::AssertFailed, slot(message)?, 0, 0, 0),
347    })
348}
349
350/// A slot as the sixteen bits the format gives it.
351fn slot(slot: Slot) -> Result<u16, TooWide> {
352    u16::try_from(slot).map_err(|_| TooWide::Slot { slot })
353}
354
355/// Two 32-bit halves as one payload, low first.
356fn halves(lo: u32, hi: u32) -> u64 {
357    u64::from(lo) | (u64::from(hi) << 32)
358}
359
360/// `to - (pc + 1)`, which is what a relative branch carries.
361fn displacement(from: Pc, to: Pc) -> Result<i64, TooWide> {
362    i64::from(to)
363        .checked_sub(i64::from(from) + 1)
364        .ok_or(TooWide::Displacement { from, to })
365}
366
367#[cfg(test)]
368mod tests {
369    use std::collections::BTreeSet;
370
371    use super::*;
372    use crate::bytecode::decode::decode;
373    use crate::bytecode::op::Op;
374    use crate::inst::{ArithOp, CmpOp, Compare, Convert, Num};
375    use crate::layout::LayoutId;
376    use crate::{ArgsId, BuiltinId, FunctionId, HostOpId, StrId, TableId};
377
378    const L: LayoutId = LayoutId(3);
379
380    /// One instruction per opcode, built the way the opcode table is: the
381    /// families that are cross products are iterated, not listed.
382    ///
383    /// This is what makes the round trip structural. A new `Inst` variant is
384    /// a compile error in [`encode`], which forces a new [`Op`], which grows
385    /// [`Op::all`] — and then
386    /// [`every_opcode_is_reached_by_a_sample`](tests::every_opcode_is_reached_by_a_sample)
387    /// fails until an instruction that produces it is written here. A list
388    /// somebody remembered to extend would catch none of that.
389    fn samples() -> Vec<(Pc, Inst)> {
390        let mut held = vec![
391            (0, Inst::Unit { dst: 1 }),
392            (
393                0,
394                Inst::Bool {
395                    dst: 1,
396                    value: true,
397                },
398            ),
399            (0, Inst::Int { dst: 1, value: 7 }),
400            (
401                0,
402                Inst::Tag {
403                    dst: 1,
404                    layout: LayoutId(3),
405                    case: crate::CaseId(1),
406                },
407            ),
408            (
409                0,
410                Inst::FuncRef {
411                    dst: 1,
412                    callee: FunctionId(2),
413                },
414            ),
415            (
416                0,
417                Inst::Float {
418                    dst: 1,
419                    bits: 1.5f64.to_bits(),
420                },
421            ),
422            (
423                0,
424                Inst::Str {
425                    dst: 1,
426                    text: StrId(4),
427                },
428            ),
429            (
430                0,
431                Inst::Copy {
432                    dst: 1,
433                    src: 2,
434                    layout: L,
435                },
436            ),
437            (0, Inst::Clear { slot: 1, layout: L }),
438        ];
439        for num in [Num::Int, Num::Float] {
440            held.push((0, Inst::Neg { num, dst: 1, a: 2 }));
441            for op in [
442                ArithOp::Add,
443                ArithOp::Sub,
444                ArithOp::Mul,
445                ArithOp::Div,
446                ArithOp::Rem,
447            ] {
448                held.push((
449                    0,
450                    Inst::Arith {
451                        num,
452                        op,
453                        dst: 1,
454                        a: 2,
455                        b: 3,
456                    },
457                ));
458            }
459        }
460        for on in [
461            Compare::Int,
462            Compare::Float,
463            Compare::Bool,
464            Compare::Str,
465            Compare::Identity,
466            Compare::Tag,
467        ] {
468            for op in [
469                CmpOp::Eq,
470                CmpOp::Ne,
471                CmpOp::Lt,
472                CmpOp::Le,
473                CmpOp::Gt,
474                CmpOp::Ge,
475            ] {
476                held.push((
477                    0,
478                    Inst::Cmp {
479                        on,
480                        op,
481                        dst: 1,
482                        a: 2,
483                        b: 3,
484                    },
485                ));
486            }
487        }
488        for op in [
489            ArithOp::Add,
490            ArithOp::Sub,
491            ArithOp::Mul,
492            ArithOp::Div,
493            ArithOp::Rem,
494        ] {
495            held.push((
496                0,
497                Inst::ArithImm {
498                    op,
499                    dst: 1,
500                    a: 2,
501                    value: -9,
502                },
503            ));
504        }
505        for op in [
506            CmpOp::Eq,
507            CmpOp::Ne,
508            CmpOp::Lt,
509            CmpOp::Le,
510            CmpOp::Gt,
511            CmpOp::Ge,
512        ] {
513            held.push((
514                0,
515                Inst::CmpImm {
516                    op,
517                    dst: 1,
518                    a: 2,
519                    value: 11,
520                },
521            ));
522        }
523        held.push((0, Inst::Not { dst: 1, a: 2 }));
524        for to in [Convert::IntToFloat, Convert::FloatToInt] {
525            held.push((0, Inst::Convert { to, dst: 1, a: 2 }));
526        }
527        held.extend([
528            // A forward jump, a backward one, and one to the instruction
529            // after this — the displacement zero a fall-through would have.
530            (5, Inst::Jump { to: 9 }),
531            (9, Inst::Jump { to: 5 }),
532            (4, Inst::Jump { to: 5 }),
533            (5, Inst::BranchFalse { cond: 1, to: 2 }),
534            (
535                0,
536                Inst::Switch {
537                    on: 1,
538                    table: TableId(2),
539                },
540            ),
541            (0, Inst::Return { src: 1 }),
542            (
543                0,
544                Inst::Call {
545                    dst: 1,
546                    callee: FunctionId(2),
547                    args: ArgsId(3),
548                },
549            ),
550            (
551                0,
552                Inst::CallClosure {
553                    dst: 1,
554                    closure: 2,
555                    args: ArgsId(3),
556                    result: LayoutId(4),
557                },
558            ),
559            (
560                0,
561                Inst::CallHost {
562                    dst: 1,
563                    op: HostOpId(2),
564                    args: ArgsId(3),
565                },
566            ),
567            (
568                0,
569                Inst::CallResource {
570                    dst: 1,
571                    receiver: 2,
572                    op: HostOpId(3),
573                    args: ArgsId(4),
574                },
575            ),
576            (
577                0,
578                Inst::CallBuiltin {
579                    dst: 1,
580                    builtin: BuiltinId(2),
581                    args: ArgsId(3),
582                },
583            ),
584            (
585                0,
586                Inst::Alloc {
587                    dst: 1,
588                    layout: L,
589                    len: Len::Fixed,
590                },
591            ),
592            (
593                0,
594                Inst::Alloc {
595                    dst: 1,
596                    layout: L,
597                    len: Len::Count(12),
598                },
599            ),
600            (
601                0,
602                Inst::Alloc {
603                    dst: 1,
604                    layout: L,
605                    len: Len::Slot(2),
606                },
607            ),
608            (
609                0,
610                Inst::LoadField {
611                    dst: 1,
612                    obj: 2,
613                    at: 3,
614                    layout: L,
615                },
616            ),
617            (
618                0,
619                Inst::StoreField {
620                    obj: 1,
621                    at: 2,
622                    src: 3,
623                    layout: L,
624                },
625            ),
626            (
627                0,
628                Inst::LoadElem {
629                    dst: 1,
630                    obj: 2,
631                    index: 3,
632                    layout: L,
633                },
634            ),
635            (
636                0,
637                Inst::StoreElem {
638                    obj: 1,
639                    index: 2,
640                    src: 3,
641                    layout: L,
642                },
643            ),
644            (
645                0,
646                Inst::ByteAt {
647                    dst: 1,
648                    obj: 2,
649                    at: 3,
650                },
651            ),
652            (0, Inst::AllocBytes { dst: 1, len: 2 }),
653            (
654                0,
655                Inst::WriteByte {
656                    bytes: 1,
657                    at: 2,
658                    value: 3,
659                },
660            ),
661            (0, Inst::CopyBytes { args: ArgsId(1) }),
662            (0, Inst::FinishString { dst: 1, bytes: 2 }),
663            (
664                0,
665                Inst::AllocBuffer {
666                    dst: 1,
667                    capacity: 2,
668                },
669            ),
670            (
671                0,
672                Inst::AppendByte {
673                    buffer: 1,
674                    value: 2,
675                },
676            ),
677            (0, Inst::AppendBytes { args: ArgsId(1) }),
678            (0, Inst::FinishBuffer { dst: 1, buffer: 2 }),
679            (0, Inst::Len { dst: 1, obj: 2 }),
680            (0, Inst::LayoutOf { dst: 1, obj: 2 }),
681            (0, Inst::AddrOfSlot { dst: 1, slot: 2 }),
682            (
683                0,
684                Inst::AddrOfField {
685                    dst: 1,
686                    obj: 2,
687                    at: 3,
688                },
689            ),
690            (
691                0,
692                Inst::AddrOfElem {
693                    dst: 1,
694                    obj: 2,
695                    index: 3,
696                    layout: L,
697                },
698            ),
699            (
700                0,
701                Inst::AddrOfPart {
702                    dst: 1,
703                    addr: 2,
704                    at: 3,
705                },
706            ),
707            (
708                0,
709                Inst::Load {
710                    dst: 1,
711                    addr: 2,
712                    layout: L,
713                },
714            ),
715            (
716                0,
717                Inst::Store {
718                    addr: 1,
719                    src: 2,
720                    layout: L,
721                },
722            ),
723            (
724                0,
725                Inst::Box {
726                    dst: 1,
727                    src: 2,
728                    layout: L,
729                },
730            ),
731            (
732                0,
733                Inst::Unbox {
734                    dst: 1,
735                    src: 2,
736                    layout: L,
737                },
738            ),
739            (
740                0,
741                Inst::ScopeEnter {
742                    dst: 1,
743                    name: StrId(2),
744                },
745            ),
746            (
747                0,
748                Inst::ScopeLeave {
749                    scope: 1,
750                    failed: 2,
751                    error: 3,
752                    layout: L,
753                },
754            ),
755            (0, Inst::ScopeCancel { scope: 1 }),
756            (
757                0,
758                Inst::Spawn {
759                    dst: 1,
760                    scope: 2,
761                    closure: 3,
762                    answer: L,
763                },
764            ),
765            (
766                0,
767                Inst::Await {
768                    dst: 1,
769                    task: 2,
770                    answer: L,
771                },
772            ),
773            (0, Inst::Cancel { task: 1 }),
774            (
775                0,
776                Inst::Settled {
777                    dst: 1,
778                    src: 2,
779                    answer: L,
780                },
781            ),
782            (0, Inst::SharedLock { cell: 1 }),
783            (0, Inst::SharedUnlock { cell: 1 }),
784            (0, Inst::Trap { message: StrId(2) }),
785            (0, Inst::AssertFailed { message: 1 }),
786        ]);
787        held
788    }
789
790    /// Every value an operand can take that is one step from not fitting.
791    ///
792    /// Slot 0 and slot 65,535; the extreme immediates; the widest branch
793    /// either way; an id at `u32::MAX`. These are the encodings that would
794    /// have been silently wrong under a narrower field, so each of them is
795    /// round-tripped rather than merely built.
796    fn boundaries() -> Vec<(Pc, Inst)> {
797        let top = u16::MAX as Slot;
798        vec![
799            (0, Inst::Unit { dst: 0 }),
800            (0, Inst::Unit { dst: top }),
801            (
802                0,
803                Inst::Arith {
804                    num: Num::Int,
805                    op: ArithOp::Add,
806                    dst: top,
807                    a: top,
808                    b: top,
809                },
810            ),
811            (
812                0,
813                Inst::Int {
814                    dst: 0,
815                    value: i64::MIN,
816                },
817            ),
818            (
819                0,
820                Inst::Int {
821                    dst: top,
822                    value: i64::MAX,
823                },
824            ),
825            (0, Inst::Int { dst: 0, value: -1 }),
826            (
827                0,
828                Inst::Float {
829                    dst: 0,
830                    bits: u64::MAX,
831                },
832            ),
833            (0, Inst::Float { dst: 0, bits: 0 }),
834            (
835                0,
836                Inst::ArithImm {
837                    op: ArithOp::Sub,
838                    dst: 0,
839                    a: top,
840                    value: i64::MIN,
841                },
842            ),
843            (
844                0,
845                Inst::CmpImm {
846                    op: CmpOp::Lt,
847                    dst: top,
848                    a: 0,
849                    value: i64::MAX,
850                },
851            ),
852            // The widest displacement in each direction that two `u32`
853            // program counters can name.
854            (0, Inst::Jump { to: Pc::MAX }),
855            (Pc::MAX, Inst::Jump { to: 0 }),
856            (
857                0,
858                Inst::BranchFalse {
859                    cond: 0,
860                    to: Pc::MAX,
861                },
862            ),
863            (Pc::MAX, Inst::BranchFalse { cond: top, to: 0 }),
864            (
865                0,
866                Inst::Str {
867                    dst: 0,
868                    text: StrId(u32::MAX),
869                },
870            ),
871            (
872                0,
873                Inst::Call {
874                    dst: 0,
875                    callee: FunctionId(u32::MAX),
876                    args: ArgsId(u32::MAX),
877                },
878            ),
879            (
880                0,
881                Inst::FuncRef {
882                    dst: 0,
883                    callee: FunctionId(u32::MAX),
884                },
885            ),
886            (
887                0,
888                Inst::Tag {
889                    dst: 0,
890                    layout: LayoutId(u32::MAX),
891                    case: crate::CaseId(u32::MAX),
892                },
893            ),
894            (
895                0,
896                Inst::LoadField {
897                    dst: 0,
898                    obj: 1,
899                    at: u32::MAX,
900                    layout: LayoutId(u32::MAX),
901                },
902            ),
903            (
904                0,
905                Inst::Alloc {
906                    dst: 0,
907                    layout: LayoutId(u32::MAX),
908                    len: Len::Count(u32::MAX),
909                },
910            ),
911        ]
912    }
913
914    /// Every one of the hundred and two opcodes is produced by some sample.
915    ///
916    /// The structural half of the round trip: a variant added to `Inst`
917    /// cannot pass this without an instruction here that encodes to it.
918    #[test]
919    fn every_opcode_is_reached_by_a_sample() {
920        let reached: BTreeSet<u8> = samples()
921            .into_iter()
922            .map(|(pc, inst)| encode(&inst, pc).expect("the sample encodes").opcode())
923            .collect();
924        let defined: BTreeSet<u8> = Op::all().into_iter().map(Op::number).collect();
925        let missing: Vec<Op> = defined
926            .difference(&reached)
927            .map(|number| Op::from_number(*number).expect("a defined opcode"))
928            .collect();
929        assert!(missing.is_empty(), "no sample encodes to {missing:?}");
930        assert_eq!(reached, defined);
931    }
932
933    /// The encoding is 1:1, so decoding is a genuine inverse for every
934    /// instruction and every boundary value.
935    #[test]
936    fn decoding_an_encoded_instruction_gives_the_instruction_back() {
937        for (pc, inst) in samples().into_iter().chain(boundaries()) {
938            let bytes = encode(&inst, pc).expect("the sample encodes");
939            assert_eq!(decode(bytes, pc), Ok(inst.clone()), "{inst:?} at {pc}");
940        }
941    }
942
943    /// The other half, which is what "canonical" means: an encoding is the
944    /// *only* encoding of what it says, so re-encoding what was decoded gives
945    /// the same sixteen bytes back.
946    #[test]
947    fn encoding_a_decoded_instruction_gives_the_bytes_back() {
948        for (pc, inst) in samples().into_iter().chain(boundaries()) {
949            let bytes = encode(&inst, pc).expect("the sample encodes");
950            let read = decode(bytes, pc).expect("the encoding decodes");
951            assert_eq!(encode(&read, pc), Ok(bytes), "{inst:?} at {pc}");
952        }
953    }
954
955    /// Encoding is a function of the instruction and its pc and of nothing
956    /// else, so two encodings of one program are byte-identical.
957    #[test]
958    fn encoding_the_same_instruction_twice_gives_the_same_bytes() {
959        for (pc, inst) in samples().into_iter().chain(boundaries()) {
960            assert_eq!(encode(&inst, pc), encode(&inst, pc));
961        }
962    }
963
964    /// `flags` carries nothing and there is no way to set it, which is what
965    /// lets the verifier reject a nonzero one outright.
966    #[test]
967    fn nothing_the_encoder_produces_sets_flags() {
968        for (pc, inst) in samples().into_iter().chain(boundaries()) {
969            assert_eq!(encode(&inst, pc).expect("encodes").flags(), 0, "{inst:?}");
970        }
971    }
972
973    /// A slot a sixteen-bit operand cannot name is refused rather than
974    /// truncated or wrapped. `crate::lower` refuses the frame that would
975    /// contain one, so this is the assertion behind that promise.
976    #[test]
977    fn a_slot_past_sixty_five_thousand_five_hundred_and_thirty_five_is_refused() {
978        let top = u16::MAX as Slot;
979        assert!(encode(&Inst::Unit { dst: top }, 0).is_ok());
980        assert_eq!(
981            encode(&Inst::Unit { dst: top + 1 }, 0),
982            Err(TooWide::Slot { slot: 65_536 })
983        );
984        assert_eq!(
985            encode(
986                &Inst::Arith {
987                    num: Num::Int,
988                    op: ArithOp::Add,
989                    dst: 0,
990                    a: 0,
991                    b: 70_000,
992                },
993                0
994            ),
995            Err(TooWide::Slot { slot: 70_000 })
996        );
997        assert!(
998            format!("{}", TooWide::Slot { slot: 65_536 }).contains("sixteen bits"),
999            "the refusal says which limit it is"
1000        );
1001    }
1002
1003    /// A branch is relative, and the displacement is `to - (pc + 1)` — so a
1004    /// fall-through is zero and the sign says which way it goes.
1005    #[test]
1006    fn a_branch_carries_the_distance_to_its_target_and_not_the_target() {
1007        let forward = encode(&Inst::Jump { to: 9 }, 5).expect("encodes");
1008        assert_eq!(forward.payload() as i64, 3);
1009        let back = encode(&Inst::Jump { to: 5 }, 9).expect("encodes");
1010        assert_eq!(back.payload() as i64, -5);
1011        let next = encode(&Inst::Jump { to: 5 }, 4).expect("encodes");
1012        assert_eq!(next.payload() as i64, 0);
1013        // Every pc a `u32` can name has a displacement an `i64` can hold, so
1014        // the encoder's overflow arm is unreachable — which is why it is an
1015        // arm rather than a paragraph.
1016        assert_eq!(
1017            encode(&Inst::Jump { to: Pc::MAX }, 0)
1018                .expect("encodes")
1019                .payload() as i64,
1020            i64::from(Pc::MAX) - 1
1021        );
1022        assert_eq!(
1023            encode(&Inst::Jump { to: 0 }, Pc::MAX)
1024                .expect("encodes")
1025                .payload() as i64,
1026            -(i64::from(Pc::MAX) + 1)
1027        );
1028    }
1029
1030    /// ADR 0041's own example rows, byte for byte, so that the audit table
1031    /// and the encoder are pinned to each other rather than to a reading of
1032    /// each other.
1033    #[test]
1034    fn the_audits_own_rows_encode_where_the_audit_says_they_do() {
1035        let int = encode(&Inst::Int { dst: 5, value: -2 }, 0).expect("encodes");
1036        assert_eq!(int.a(), 5);
1037        assert_eq!(int.payload(), (-2i64) as u64);
1038
1039        let add = encode(
1040            &Inst::Arith {
1041                num: Num::Int,
1042                op: ArithOp::Add,
1043                dst: 1,
1044                a: 2,
1045                b: 3,
1046            },
1047            0,
1048        )
1049        .expect("encodes");
1050        assert_eq!((add.a(), add.b(), add.c(), add.payload()), (1, 2, 3, 0));
1051
1052        // `load.field` packs the word offset and the layout into the two
1053        // halves, and both keep their full thirty-two bits.
1054        let field = encode(
1055            &Inst::LoadField {
1056                dst: 1,
1057                obj: 2,
1058                at: 7,
1059                layout: LayoutId(9),
1060            },
1061            0,
1062        )
1063        .expect("encodes");
1064        assert_eq!((field.a(), field.b(), field.lo(), field.hi()), (1, 2, 7, 9));
1065
1066        // `call.resource` is the densest call: two slots and both halves,
1067        // with `c` still empty.
1068        let resource = encode(
1069            &Inst::CallResource {
1070                dst: 1,
1071                receiver: 2,
1072                op: HostOpId(3),
1073                args: ArgsId(4),
1074            },
1075            0,
1076        )
1077        .expect("encodes");
1078        assert_eq!(
1079            (
1080                resource.a(),
1081                resource.b(),
1082                resource.c(),
1083                resource.lo(),
1084                resource.hi()
1085            ),
1086            (1, 2, 0, 3, 4)
1087        );
1088
1089        // `scope.leave` is the three-slot case the issue predicted would be
1090        // tight, and it fits with the payload half empty.
1091        let leave = encode(
1092            &Inst::ScopeLeave {
1093                scope: 1,
1094                failed: 2,
1095                error: 3,
1096                layout: LayoutId(4),
1097            },
1098            0,
1099        )
1100        .expect("encodes");
1101        assert_eq!(
1102            (leave.a(), leave.b(), leave.c(), leave.lo(), leave.hi()),
1103            (1, 2, 3, 4, 0)
1104        );
1105    }
1106
1107    /// `Len`'s three forms are three opcodes, so nothing stores a
1108    /// discriminant and `alloc.imm x0` is not `alloc.fixed`.
1109    #[test]
1110    fn the_three_alloc_forms_are_three_opcodes_and_not_a_tagged_field() {
1111        let at = |len| {
1112            encode(
1113                &Inst::Alloc {
1114                    dst: 1,
1115                    layout: L,
1116                    len,
1117                },
1118                0,
1119            )
1120            .expect("encodes")
1121            .opcode()
1122        };
1123        assert_eq!(at(Len::Fixed), Op::AllocFixed.number());
1124        assert_eq!(at(Len::Count(0)), Op::AllocImm.number());
1125        assert_eq!(at(Len::Slot(2)), Op::AllocSlot.number());
1126        assert_ne!(at(Len::Fixed), at(Len::Count(0)));
1127    }
1128}
cove_ir/bytecode/encode.rs

cove_ir/bytecode/
encode.rs
