fn absent(k: u64) -> u64 {
4_294_967_296 + k
}
fn idx_or(k: u64, v: Option<u32>) -> u64 {
v.map_or(absent(k), u64::from)
}
struct MCtx<'a> {
carrier: u64,
box_: u64,
add: u64,
sub: u64,
mul: u64,
neg: u64,
cmp: u64,
eq: u64,
mag: u64,
str_: u64,
str_vec: u64,
concat: u64,
streq: u64,
to_index: u64,
divmod: u64,
bitwise: u64,
to_i64_sat: u64,
bytes_arr: u64,
to_i64_chk: u64,
from_int: u64,
tt: &'a PlanTypeTable,
sigs: HashMap<u32, (Vec<PlanTy>, PlanTy)>,
}
impl<'a> MCtx<'a> {
fn new(
roles: Option<&HostRoles>,
strings: &StringHostRoles,
tt: &'a PlanTypeTable,
fns: &[(u32, &FnPlan)],
) -> Self {
let role = |pick: fn(&HostRoles) -> Option<u32>| roles.and_then(pick);
let string_role = |r: StringHostRole| strings.iter().find(|x| x.1 == r).map(|x| x.0);
let mut sigs = HashMap::new();
for (f, p) in fns {
sigs.entry(*f)
.or_insert_with(|| (p.params.clone(), p.ret.clone()));
}
MCtx {
carrier: idx_or(0, tt.carrier),
box_: idx_or(1, role(|r| r.box_idx)),
add: idx_or(2, role(|r| r.add_idx)),
sub: idx_or(3, role(|r| r.sub_idx)),
mul: idx_or(4, role(|r| r.mul_idx)),
neg: absent(5),
cmp: idx_or(6, role(|r| r.cmp_idx)),
eq: idx_or(7, role(|r| r.eq_idx)),
mag: idx_or(13, tt.mag),
str_: idx_or(14, tt.str_),
str_vec: idx_or(16, tt.str_vec),
concat: idx_or(17, string_role(StringHostRole::Concat)),
streq: idx_or(18, string_role(StringHostRole::Eq)),
to_index: idx_or(19, role(|r| r.to_index_idx)),
divmod: idx_or(23, role(|r| r.divmod_idx)),
bitwise: idx_or(28, role(|r| r.bitwise_idx)),
to_i64_sat: idx_or(24, tt.int_sat),
bytes_arr: idx_or(25, tt.bytes_arr),
to_i64_chk: idx_or(26, tt.int_chk),
from_int: idx_or(27, tt.str_from_int),
tt,
sigs,
}
}
fn record(&self, tid: u32) -> Option<&PlanRecordDecl> {
self.tt.records.iter().find(|r| r.tid == tid)
}
fn sum(&self, tid: u32) -> Option<&PlanSumDecl> {
self.tt.sums.iter().find(|s| s.tid == tid)
}
fn rec_fields(&self, tid: u32) -> Option<&[PlanTy]> {
self.record(tid).map(|r| r.fields.as_slice())
}
fn is_word(&self, tid: u32) -> bool {
self.tt.words.contains(&tid) && self.rec_fields(tid) == Some(&[PlanTy::Int][..])
}
fn struct_of(&self, tid: u32) -> u64 {
idx_or(8, self.record(tid).map(|r| r.struct_idx))
}
fn ctor_fields(&self, tid: u32, c: u32) -> Option<&[PlanTy]> {
self.sum(tid)?.ctors.get(c as usize).map(|x| x.1.as_slice())
}
fn ctor_struct(&self, tid: u32, c: u32) -> u64 {
idx_or(
9,
self.sum(tid)
.and_then(|s| s.ctors.get(c as usize))
.map(|x| x.0),
)
}
fn sum_root(&self, tid: u32) -> u64 {
idx_or(10, self.sum(tid).map(|s| s.root))
}
fn opt_struct(&self, t: &PlanTy) -> u64 {
idx_or(11, self.tt.options.iter().find(|o| &o.0 == t).map(|o| o.1))
}
fn res_struct(&self, t: &PlanTy, e: &PlanTy) -> u64 {
idx_or(
12,
self.tt
.results
.iter()
.find(|r| &r.0 == t && &r.1 == e)
.map(|r| r.2),
)
}
fn str_seg(&self, bytes: &[u8]) -> u64 {
idx_or(
15,
self.tt.str_segs.iter().find(|s| s.0 == bytes).map(|s| s.1),
)
}
fn vec_struct(&self, t: &PlanTy) -> u64 {
idx_or(20, self.tt.vecs.iter().find(|v| &v.0 == t).map(|v| v.1))
}
fn list_struct(&self, t: &PlanTy) -> u64 {
idx_or(21, self.tt.lists.iter().find(|l| &l.0 == t).map(|l| l.1))
}
fn list_cons(&self, t: &PlanTy) -> Option<u32> {
self.tt.list_cons.iter().find(|l| &l.0 == t).map(|l| l.1)
}
fn opaque_struct(&self, tid: u32) -> u64 {
idx_or(22, self.tt.opaques.iter().find(|o| o.0 == tid).map(|o| o.1))
}
fn sum_ok(&self, tid: u32) -> bool {
let Some(s) = self.sum(tid) else {
return false;
};
let cs = &s.ctors;
let newtype = cs.len() == 1 && cs[0].1.len() == 1;
if newtype {
return false;
}
(0..cs.len()).all(|a| {
(0..cs.len()).all(|b| {
a == b || self.ctor_struct(tid, a as u32) != self.ctor_struct(tid, b as u32)
})
})
}
fn ahead_w(&self, t: &PlanWTree) -> Vec<BI> {
let mut out = Vec::new();
for l in t.leaves() {
match l {
PlanWLeaf::Field {
tid,
field,
base,
slot,
} => out.extend(ops(vec![
WI::LocalGet(*base),
WI::StructGet(self.struct_of(*tid), *field),
WI::LocalSet(*slot),
])),
PlanWLeaf::Word { base, slot, .. } => {
out.extend(ops(vec![WI::LocalGet(*base), WI::LocalSet(*slot)]));
}
PlanWLeaf::Local(_) => {}
}
}
out
}
fn exact_b(&self, t: &PlanWTree) -> Vec<BI> {
match t {
PlanWTree::Leaf(PlanWLeaf::Word { slot, .. }) => {
ops(vec![WI::LocalGet(*slot), WI::Call(self.box_)])
}
PlanWTree::Leaf(l) => ops(vec![WI::LocalGet(l.loc())]),
PlanWTree::Op(op, a, b) => {
let mut out = self.exact_b(a);
out.extend(self.exact_b(b));
out.push(BI::Op(WI::Call(self.arith_idx(*op))));
out
}
PlanWTree::Lit(k) => ops(vec![WI::I64Const(*k), WI::Call(self.box_)]),
PlanWTree::MulLit(k, lit_first, a) => {
let lit = ops(vec![WI::I64Const(*k), WI::Call(self.box_)]);
let mut out = if *lit_first {
let mut o = lit;
o.extend(self.exact_b(a));
o
} else {
let mut o = self.exact_b(a);
o.extend(lit);
o
};
out.push(BI::Op(WI::Call(self.mul)));
out
}
PlanWTree::DivLit(k, a) | PlanWTree::ModLit(k, a) => {
let flag = i64::from(matches!(t, PlanWTree::ModLit(..)));
let mut out = self.exact_b(a);
out.extend(ops(vec![
WI::I64Const(*k),
WI::Call(self.box_),
WI::I32Const(flag),
WI::Call(self.divmod),
]));
out
}
PlanWTree::Pick(p, a, b) => {
let mut out = self.exact_b(a);
out.extend(self.exact_b(b));
out.extend(ops(self.int_cmp_tail(pick_op(*p))));
out.push(BI::If(Some(PlanTy::Int), self.exact_b(a), self.exact_b(b)));
out
}
}
}
fn arith_idx(&self, op: PlanBinOp) -> u64 {
match op {
PlanBinOp::Add => self.add,
PlanBinOp::Sub => self.sub,
_ => self.mul,
}
}
}
fn has_default(t: &PlanTy) -> bool {
matches!(
t,
PlanTy::Int
| PlanTy::Bool
| PlanTy::Record(_)
| PlanTy::Sum(_)
| PlanTy::Option(_)
| PlanTy::Result(_, _)
| PlanTy::Str
| PlanTy::Float
| PlanTy::List(_)
| PlanTy::Vec(_)
| PlanTy::Bytes
)
}
type Gamma = BTreeMap<u32, PlanTy>;
fn upd(g: &Gamma, b: u32, t: PlanTy) -> Gamma {
let mut g = g.clone();
g.insert(b, t);
g
}
fn bind_tys(n: u32, g: &Gamma, bs: &[u32], ts: &[PlanTy]) -> Option<Gamma> {
if bs.len() != ts.len() {
return None;
}
let mut g = g.clone();
for (b, t) in bs.iter().zip(ts) {
if *b == PLAN_NO_SLOT {
continue;
}
if *b < n && !g.contains_key(b) {
g.insert(*b, t.clone());
} else {
return None;
}
}
Some(g)
}
fn bind_one(n: u32, g: &Gamma, b: u32, t: &PlanTy) -> Option<Gamma> {
bind_tys(n, g, &[b], std::slice::from_ref(t))
}
fn opt_pick(p1: &PlanPat, p2: &PlanPat) -> Option<(bool, u32)> {
match (p1, p2) {
(PlanPat::Ctor(PlanCtor::Some, b), PlanPat::Ctor(PlanCtor::None, n))
if b.len() == 1 && n.is_empty() =>
{
Some((false, b[0]))
}
(PlanPat::Ctor(PlanCtor::Some, b), PlanPat::Wild) if b.len() == 1 => Some((false, b[0])),
(PlanPat::Ctor(PlanCtor::None, n), PlanPat::Ctor(PlanCtor::Some, b))
if b.len() == 1 && n.is_empty() =>
{
Some((true, b[0]))
}
(PlanPat::Ctor(PlanCtor::None, n), PlanPat::Wild) if n.is_empty() => {
Some((true, PLAN_NO_SLOT))
}
_ => None,
}
}
fn res_pick(p1: &PlanPat, p2: &PlanPat) -> Option<(bool, u32, u32)> {
match (p1, p2) {
(PlanPat::Ctor(PlanCtor::Ok, a), PlanPat::Ctor(PlanCtor::Err, b))
if a.len() == 1 && b.len() == 1 =>
{
Some((false, a[0], b[0]))
}
(PlanPat::Ctor(PlanCtor::Ok, a), PlanPat::Wild) if a.len() == 1 => {
Some((false, a[0], PLAN_NO_SLOT))
}
(PlanPat::Ctor(PlanCtor::Err, b), PlanPat::Ctor(PlanCtor::Ok, a))
if a.len() == 1 && b.len() == 1 =>
{
Some((true, a[0], b[0]))
}
(PlanPat::Ctor(PlanCtor::Err, b), PlanPat::Wild) if b.len() == 1 => {
Some((true, PLAN_NO_SLOT, b[0]))
}
_ => None,
}
}
fn list_pick(p1: &PlanPat, p2: &PlanPat) -> Option<(bool, u32, u32)> {
match (p1, p2) {
(PlanPat::EmptyList, PlanPat::Cons(h, t)) => Some((false, *h, *t)),
(PlanPat::EmptyList, PlanPat::Wild) => Some((false, PLAN_NO_SLOT, PLAN_NO_SLOT)),
(PlanPat::Cons(h, t), PlanPat::EmptyList | PlanPat::Wild) => Some((true, *h, *t)),
_ => None,
}
}
fn vec_get_or(lb: PlanLazy, o: &PlanExpr, d: &PlanExpr) -> Option<(u32, u32)> {
match (lb, o, d) {
(
PlanLazy::OptWithDefault,
PlanExpr::Call(PlanCallee::Builtin(PlanBuiltin::VecGet), args),
PlanExpr::Literal(_),
) => match args.as_slice() {
[PlanExpr::Local(v), PlanExpr::Local(i)] => Some((*v, *i)),
_ => None,
},
_ => None,
}
}
fn div_or<'e>(
lb: PlanLazy,
o: &'e PlanExpr,
d: &PlanExpr,
) -> Option<(bool, &'e PlanExpr, &'e PlanExpr)> {
match (lb, o, d) {
(
PlanLazy::ResWithDefault,
PlanExpr::Call(PlanCallee::Builtin(b @ (PlanBuiltin::IntDiv | PlanBuiltin::IntMod)), args),
PlanExpr::Literal(PlanLit::Int(_)),
) => match args.as_slice() {
[a, bb] => Some((*b == PlanBuiltin::IntMod, a, bb)),
_ => None,
},
_ => None,
}
}
fn all_str(ts: &[PlanTy]) -> bool {
!ts.is_empty() && ts.iter().all(|t| *t == PlanTy::Str)
}
fn contains_eq(t: &PlanTy) -> bool {
matches!(t, PlanTy::Int | PlanTy::Str | PlanTy::Bool)
}
impl MCtx<'_> {
fn builtin_ty(&self, b: PlanBuiltin, ts: &[PlanTy]) -> Option<PlanTy> {
use PlanListRole as R;
let has = |r: R, t: &PlanTy| self.list_helper(r, t).is_some();
let list = |t: &PlanTy| PlanTy::List(Box::new(t.clone()));
match (b, ts) {
(PlanBuiltin::BoolAnd | PlanBuiltin::BoolOr, [PlanTy::Bool, PlanTy::Bool]) => {
Some(PlanTy::Bool)
}
(PlanBuiltin::BoolNot, [PlanTy::Bool]) => Some(PlanTy::Bool),
(PlanBuiltin::ListPrepend, [t, PlanTy::List(t2)]) if t == t2.as_ref() => Some(list(t)),
(PlanBuiltin::ListLen, [PlanTy::List(t)]) => has(R::Len, t).then_some(PlanTy::Int),
(PlanBuiltin::ListReverse, [PlanTy::List(t)]) => has(R::Reverse, t).then(|| list(t)),
(PlanBuiltin::ListConcat, [PlanTy::List(t), PlanTy::List(t2)]) => {
(t == t2 && has(R::Concat, t)).then(|| list(t))
}
(PlanBuiltin::ListTake, [PlanTy::List(t), PlanTy::Int]) => {
has(R::Take, t).then(|| list(t))
}
(PlanBuiltin::ListDrop, [PlanTy::List(t), PlanTy::Int]) => {
has(R::Drop, t).then(|| list(t))
}
(PlanBuiltin::ListContains, [PlanTy::List(t), t2]) => {
(t.as_ref() == t2 && contains_eq(t) && has(R::Contains, t)).then_some(PlanTy::Bool)
}
(PlanBuiltin::BytesOfList, [PlanTy::List(t)]) if **t == PlanTy::Int => self
.bytes_helper(PlanBytesRole::Pack)
.map(|_| PlanTy::Bytes),
(PlanBuiltin::BytesValues, [PlanTy::Bytes]) => self
.bytes_helper(PlanBytesRole::Unpack)
.map(|_| list(&PlanTy::Int)),
(PlanBuiltin::BytesLen, [PlanTy::Bytes]) => Some(PlanTy::Int),
(PlanBuiltin::BytesConcat, [PlanTy::Bytes, PlanTy::Bytes]) => self
.bytes_helper(PlanBytesRole::Concat)
.map(|_| PlanTy::Bytes),
(PlanBuiltin::BytesTake, [PlanTy::Bytes, PlanTy::Int]) => self
.bytes_helper(PlanBytesRole::Take)
.map(|_| PlanTy::Bytes),
(PlanBuiltin::BytesDrop, [PlanTy::Bytes, PlanTy::Int]) => self
.bytes_helper(PlanBytesRole::Drop)
.map(|_| PlanTy::Bytes),
(PlanBuiltin::StrFromInt, [PlanTy::Int]) => Some(PlanTy::Str),
_ => None,
}
}
}
fn lazy_ty(lb: PlanLazy, to: &PlanTy, td: &PlanTy) -> Option<PlanTy> {
match (lb, to) {
(PlanLazy::OptWithDefault, PlanTy::Option(t))
| (PlanLazy::ResWithDefault, PlanTy::Result(t, _))
if t.as_ref() == td && has_default(t) =>
{
Some(td.clone())
}
_ => None,
}
}
fn is_arith(op: PlanBinOp) -> bool {
matches!(op, PlanBinOp::Add | PlanBinOp::Sub | PlanBinOp::Mul)
}
fn is_equality(op: PlanBinOp) -> bool {
matches!(op, PlanBinOp::Eq | PlanBinOp::Neq)
}
fn is_float_cmp(op: PlanBinOp) -> bool {
matches!(
op,
PlanBinOp::Eq | PlanBinOp::Lt | PlanBinOp::Gt | PlanBinOp::Lte | PlanBinOp::Gte
)
}
impl MCtx<'_> {
fn ctor_ty(&self, c: PlanCtor, ty: &PlanTy, ts: &[PlanTy]) -> Option<PlanTy> {
match (c, ty) {
(PlanCtor::User(tid, k), PlanTy::Sum(tid2)) => {
(tid == *tid2 && self.sum_ok(tid) && self.ctor_fields(tid, k) == Some(ts))
.then_some(PlanTy::Sum(tid))
}
(PlanCtor::Some, PlanTy::Option(t)) => {
(ts == [t.as_ref().clone()] && has_default(t)).then(|| ty.clone())
}
(PlanCtor::None, PlanTy::Option(t)) => {
(ts.is_empty() && has_default(t)).then(|| ty.clone())
}
(PlanCtor::Ok, PlanTy::Result(t, e)) => {
(ts == [t.as_ref().clone()] && has_default(t) && has_default(e)).then(|| ty.clone())
}
(PlanCtor::Err, PlanTy::Result(t, e)) => {
(ts == [e.as_ref().clone()] && has_default(t) && has_default(e)).then(|| ty.clone())
}
_ => None,
}
}
fn word_leaf_ok(&self, n: u32, g: &Gamma, l: &PlanWLeaf) -> bool {
match l {
PlanWLeaf::Local(i) => g.get(i) == Some(&PlanTy::Int),
PlanWLeaf::Field {
tid,
field,
base,
slot,
} => {
n <= *slot
&& match (g.get(base), self.rec_fields(*tid)) {
(Some(PlanTy::Record(t2)), Some(fts)) => {
t2 == tid
&& fts.len() >= 2
&& fts.get(*field as usize) == Some(&PlanTy::Int)
}
_ => false,
}
}
PlanWLeaf::Word { tid, base, slot } => {
n <= *slot && g.get(base) == Some(&PlanTy::Record(*tid)) && self.is_word(*tid)
}
}
}
fn word_tree_ok(&self, n: u32, g: &Gamma, t: &PlanWTree) -> bool {
match t {
PlanWTree::Leaf(l) => self.word_leaf_ok(n, g, l),
PlanWTree::Op(op, a, b) => {
is_arith(*op)
&& !(*op == PlanBinOp::Mul
&& (matches!(**a, PlanWTree::Lit(_))
|| matches!(**b, PlanWTree::Lit(_))))
&& self.word_tree_ok(n, g, a)
&& self.word_tree_ok(n, g, b)
}
PlanWTree::Lit(_) => true,
PlanWTree::Pick(_, a, b) => self.word_tree_ok(n, g, a) && self.word_tree_ok(n, g, b),
PlanWTree::MulLit(_, _, a) => self.word_tree_ok(n, g, a),
PlanWTree::DivLit(k, a) => div_lit_ok(*k) && self.word_tree_ok(n, g, a),
PlanWTree::ModLit(k, a) => mod_lit_ok(*k) && self.word_tree_ok(n, g, a),
}
}
fn word_ok(&self, n: u32, g: &Gamma, t: &PlanWTree, w: u32) -> bool {
let Some(w2) = w.checked_add(2) else {
return false;
};
let mut written = t.slots();
written.extend([w, w + 1, w2]);
self.word_tree_ok(n, g, t) && n <= w && distinct(&written)
}
fn tys_of(&self, n: u32, g: &Gamma, es: &[PlanExpr]) -> Option<Vec<PlanTy>> {
es.iter().map(|e| self.ty_of(n, g, false, e)).collect()
}
fn ty_of(&self, n: u32, g: &Gamma, tail: bool, e: &PlanExpr) -> Option<PlanTy> {
match e {
PlanExpr::Literal(PlanLit::Int(_)) => Some(PlanTy::Int),
PlanExpr::Literal(PlanLit::Bool(_)) => Some(PlanTy::Bool),
PlanExpr::Literal(PlanLit::Float(_)) => Some(PlanTy::Float),
PlanExpr::Literal(PlanLit::Str(_)) => Some(PlanTy::Str),
PlanExpr::Local(i) => g.get(i).cloned(),
PlanExpr::Let(b, v, body) => {
if *b < n && !g.contains_key(b) {
let t = self.ty_of(n, g, false, v)?;
self.ty_of(n, &upd(g, *b, t), tail, body)
} else {
None
}
}
PlanExpr::Call(PlanCallee::Fn(f), args) | PlanExpr::TailCall(f, args) => {
if matches!(e, PlanExpr::TailCall(..)) && !tail {
return None;
}
let (params, ret) = self.sigs.get(f)?;
let ts = self.tys_of(n, g, args)?;
(&ts == params).then(|| ret.clone())
}
PlanExpr::Call(PlanCallee::Builtin(b), args) => {
self.builtin_ty(*b, &self.tys_of(n, g, args)?)
}
PlanExpr::Call(PlanCallee::Lazy(lb), args) => match args.as_slice() {
[o, d] => match vec_get_or(*lb, o, d) {
Some((v, i)) => match (g.get(&v), g.get(&i), self.ty_of(n, g, false, d)) {
(Some(PlanTy::Vec(t)), Some(PlanTy::Int), Some(td)) if td == **t => {
Some(td)
}
_ => None,
},
None => match div_or(*lb, o, d) {
Some((_, a, b)) => (self.ty_of(n, g, false, a)? == PlanTy::Int
&& self.ty_of(n, g, false, b)? == PlanTy::Int
&& self.ty_of(n, g, false, d)? == PlanTy::Int)
.then_some(PlanTy::Int),
None => lazy_ty(
*lb,
&self.ty_of(n, g, false, o)?,
&self.ty_of(n, g, false, d)?,
),
},
},
_ => None,
},
PlanExpr::Call(PlanCallee::Intrinsic(_), args) => match args.as_slice() {
[a, PlanExpr::Literal(PlanLit::Int(k))] if *k != 0 => {
(self.ty_of(n, g, false, a)? == PlanTy::Int).then_some(PlanTy::Int)
}
_ => None,
},
PlanExpr::Call(PlanCallee::Pick(_) | PlanCallee::Bitwise(_), args) => match args
.as_slice()
{
[a, b] => (self.ty_of(n, g, false, a)? == PlanTy::Int
&& self.ty_of(n, g, false, b)? == PlanTy::Int)
.then_some(PlanTy::Int),
_ => None,
},
PlanExpr::BinOp(op, l, r) => {
match (self.ty_of(n, g, false, l)?, self.ty_of(n, g, false, r)?) {
(PlanTy::Int, PlanTy::Int) => Some(if is_arith(*op) {
PlanTy::Int
} else {
PlanTy::Bool
}),
(PlanTy::Bool, PlanTy::Bool) => is_equality(*op).then_some(PlanTy::Bool),
(PlanTy::Float, PlanTy::Float) => is_float_cmp(*op).then_some(PlanTy::Bool),
(PlanTy::Str, PlanTy::Str) => match op {
PlanBinOp::Add => Some(PlanTy::Str),
PlanBinOp::Eq | PlanBinOp::Neq => Some(PlanTy::Bool),
_ => None,
},
_ => None,
}
}
PlanExpr::Neg(x) => (self.ty_of(n, g, false, x)? == PlanTy::Int).then_some(PlanTy::Int),
PlanExpr::IntWord(t, w) => self.word_ok(n, g, t, *w).then_some(PlanTy::Int),
PlanExpr::IntCmp(op, a, b, w) => (!is_arith(*op)
&& self.word_ok(n, g, &PlanWTree::pair(a, b), *w))
.then_some(PlanTy::Bool),
PlanExpr::If(c, t, el) => {
match (
self.ty_of(n, g, false, c)?,
self.ty_of(n, g, tail, t)?,
self.ty_of(n, g, tail, el)?,
) {
(PlanTy::Bool, a, b) if a == b => Some(a),
_ => None,
}
}
PlanExpr::RecordCreate(tid, fs) => {
let fts = self.rec_fields(*tid)?;
let ts = self.tys_of(n, g, fs)?;
((fts.len() >= 2 || self.is_word(*tid)) && ts == fts)
.then_some(PlanTy::Record(*tid))
}
PlanExpr::Project(tid, i, base) => {
match (self.ty_of(n, g, false, base)?, self.rec_fields(*tid)) {
(PlanTy::Record(t2), Some(fts))
if t2 == *tid && (fts.len() >= 2 || self.is_word(*tid)) =>
{
fts.get(*i as usize).cloned()
}
_ => None,
}
}
PlanExpr::Construct(c, ty, args) => self.ctor_ty(*c, ty, &self.tys_of(n, g, args)?),
PlanExpr::Interp(parts) => all_str(&self.tys_of(n, g, parts)?).then_some(PlanTy::Str),
PlanExpr::List(t, items) => {
let lt = PlanTy::List(Box::new(t.clone()));
if items.is_empty() {
return Some(lt);
}
let f = self.list_cons(t)?;
let ts = self.tys_of(n, g, items)?;
let sig_ok = self.sigs.get(&f) == Some(&(vec![t.clone(), lt.clone()], lt.clone()));
(sig_ok && ts.iter().all(|x| x == t)).then_some(lt)
}
PlanExpr::Match(s, arms) => match self.ty_of(n, g, false, s)? {
PlanTy::Int => {
matches!(arms.first(), Some((PlanPat::LitInt(_), _))).then_some(())?;
self.ty_int_arms(n, g, tail, arms)
}
PlanTy::Bool => self.ty_bool_arms(n, g, tail, arms),
PlanTy::Option(t) => self.ty_opt_arms(n, g, tail, &t, arms),
PlanTy::Result(t, er) => self.ty_res_arms(n, g, tail, &t, &er, arms),
PlanTy::Sum(tid) => {
(self.sum_ok(tid) && self.var_exhaustive(tid, arms) && arms.len() >= 2)
.then_some(())?;
self.ty_var_arms(n, g, tail, tid, arms)
}
PlanTy::Str => self.ty_str_arms(n, g, tail, arms),
PlanTy::Record(tid) => self.ty_tup_arms(n, g, tail, tid, arms),
PlanTy::List(t) => self.ty_list_arms(n, g, tail, &t, arms),
_ => None,
},
PlanExpr::Try(x, ret) => match (self.ty_of(n, g, false, x)?, ret) {
(PlanTy::Result(t, er), PlanTy::Result(t2, er2))
if er == *er2 && has_default(t2) && has_default(&er) =>
{
Some(*t)
}
_ => None,
},
PlanExpr::Scope(x) => {
if !tail {
return None;
}
let t = self.ty_of(n, g, true, x)?;
let mut rets = Vec::new();
bare_tries(x, &mut rets);
rets.iter().all(|r| **r == t).then_some(t)
}
}
}
fn ty_int_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
let ((p, b), rest) = arms.split_first()?;
match p {
PlanPat::LitInt(_) => {
let t = self.ty_of(n, g, tail, b)?;
let t2 = self.ty_int_arms(n, g, tail, rest)?;
(t == t2).then_some(t)
}
PlanPat::Wild if rest.is_empty() => self.ty_of(n, g, tail, b),
PlanPat::Bind(s) if rest.is_empty() => {
(*s < n && !g.contains_key(s) && *s != PLAN_NO_SLOT).then_some(())?;
self.ty_of(n, &upd(g, *s, PlanTy::Int), tail, b)
}
_ => None,
}
}
fn ty_bool_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
match arms {
[(PlanPat::LitBool(v), t), (p, e)]
if *p == PlanPat::LitBool(!v) || *p == PlanPat::Wild =>
{
let a = self.ty_of(n, g, tail, t)?;
let b = self.ty_of(n, g, tail, e)?;
(a == b).then_some(a)
}
_ => None,
}
}
fn ty_opt_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
t: &PlanTy,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
let [(p1, b1), (p2, b2)] = arms else {
return None;
};
let (swap, sb) = opt_pick(p1, p2)?;
let gs = bind_one(n, g, sb, t)?;
let (a, b) = if swap {
(self.ty_of(n, &gs, tail, b2)?, self.ty_of(n, g, tail, b1)?)
} else {
(self.ty_of(n, &gs, tail, b1)?, self.ty_of(n, g, tail, b2)?)
};
(a == b).then_some(a)
}
fn ty_res_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
t: &PlanTy,
er: &PlanTy,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
let [(p1, b1), (p2, b2)] = arms else {
return None;
};
let (swap, ob, eb) = res_pick(p1, p2)?;
let go = bind_one(n, g, ob, t)?;
let ge = bind_one(n, g, eb, er)?;
let (a, b) = if swap {
(self.ty_of(n, &go, tail, b2)?, self.ty_of(n, &ge, tail, b1)?)
} else {
(self.ty_of(n, &go, tail, b1)?, self.ty_of(n, &ge, tail, b2)?)
};
(a == b).then_some(a)
}
fn covers(c: u32, arms: &[(PlanPat, PlanExpr)]) -> bool {
for (p, _) in arms {
match p {
PlanPat::Wild => return true,
PlanPat::Ctor(PlanCtor::User(_, c2), _) if *c2 == c => return true,
_ => {}
}
}
false
}
fn var_exhaustive(&self, tid: u32, arms: &[(PlanPat, PlanExpr)]) -> bool {
match self.sum(tid) {
Some(s) => (0..s.ctors.len() as u32).all(|c| Self::covers(c, arms)),
None => false,
}
}
fn var_arm_gamma(&self, n: u32, g: &Gamma, tid: u32, p: &PlanPat) -> Option<Gamma> {
match p {
PlanPat::Ctor(PlanCtor::User(t2, c), bs) if *t2 == tid => {
bind_tys(n, g, bs, self.ctor_fields(tid, *c)?)
}
PlanPat::Wild => Some(g.clone()),
_ => None,
}
}
fn ty_var_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
tid: u32,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
match arms {
[] => None,
[(p, b)] => self.ty_of(n, &self.var_arm_gamma(n, g, tid, p)?, tail, b),
[(p, b), rest @ ..] => {
if *p == PlanPat::Wild {
return None;
}
let g2 = self.var_arm_gamma(n, g, tid, p)?;
let a = self.ty_of(n, &g2, tail, b)?;
let c = self.ty_var_arms(n, g, tail, tid, rest)?;
(a == c).then_some(a)
}
}
}
fn ty_str_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
let ((p, b), rest) = arms.split_first()?;
match p {
PlanPat::LitStr(_) => {
let t = self.ty_of(n, g, tail, b)?;
let t2 = self.ty_str_arms(n, g, tail, rest)?;
(t == t2).then_some(t)
}
PlanPat::Wild if rest.is_empty() => self.ty_of(n, g, tail, b),
_ => None,
}
}
fn ty_list_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
t: &PlanTy,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
let [(p1, b1), (p2, b2)] = arms else {
return None;
};
let (swap, h, tl) = list_pick(p1, p2)?;
let gc = bind_tys(n, g, &[h, tl], &[t.clone(), PlanTy::List(Box::new(t.clone()))])?;
let (a, b) = if swap {
(self.ty_of(n, &gc, tail, b1)?, self.ty_of(n, g, tail, b2)?)
} else {
(self.ty_of(n, g, tail, b1)?, self.ty_of(n, &gc, tail, b2)?)
};
(a == b).then_some(a)
}
fn ty_tup_arms(
&self,
n: u32,
g: &Gamma,
tail: bool,
tid: u32,
arms: &[(PlanPat, PlanExpr)],
) -> Option<PlanTy> {
let [(PlanPat::Tuple(bs), b)] = arms else {
return None;
};
let fts = self.rec_fields(tid)?;
(fts.len() >= 2 && bs.iter().any(|x| *x != PLAN_NO_SLOT)).then_some(())?;
self.ty_of(n, &bind_tys(n, g, bs, fts)?, tail, b)
}
}
fn params_gamma(ps: &[PlanTy]) -> Gamma {
ps.iter()
.enumerate()
.map(|(i, t)| (i as u32, t.clone()))
.collect()
}
fn bare_tries<'e>(e: &'e PlanExpr, out: &mut Vec<&'e PlanTy>) {
match e {
PlanExpr::Literal(_) | PlanExpr::Local(_) | PlanExpr::Scope(_) | PlanExpr::IntWord(..) | PlanExpr::IntCmp(..) => {}
PlanExpr::Let(_, v, b) | PlanExpr::BinOp(_, v, b) => {
bare_tries(v, out);
bare_tries(b, out);
}
PlanExpr::Call(_, args)
| PlanExpr::TailCall(_, args)
| PlanExpr::RecordCreate(_, args)
| PlanExpr::Construct(_, _, args)
| PlanExpr::Interp(args)
| PlanExpr::List(_, args) => args.iter().for_each(|a| bare_tries(a, out)),
PlanExpr::Neg(x) | PlanExpr::Project(_, _, x) => bare_tries(x, out),
PlanExpr::If(c, t, el) => {
bare_tries(c, out);
bare_tries(t, out);
bare_tries(el, out);
}
PlanExpr::Match(s, arms) => {
bare_tries(s, out);
arms.iter().for_each(|(_, b)| bare_tries(b, out));
}
PlanExpr::Try(x, ret) => {
out.push(ret);
bare_tries(x, out);
}
}
}
fn plan_typed(m: &MCtx<'_>, p: &FnPlan) -> bool {
let np = p.params.len();
let mut bare = Vec::new();
bare_tries(&p.body, &mut bare);
np <= p.nslots as usize
&& (p.nslots as usize) <= np + p.locals.len()
&& m.ty_of(p.nslots, ¶ms_gamma(&p.params), true, &p.body) == Some(p.ret.clone())
&& bare.is_empty()
}
fn no_eqref(t: &PlanTy) -> bool {
match t {
PlanTy::Eqref => false,
PlanTy::Option(x) | PlanTy::Vec(x) | PlanTy::List(x) => no_eqref(x),
PlanTy::Result(x, e) => no_eqref(x) && no_eqref(e),
_ => true,
}
}
fn plan_eqref_ok(p: &FnPlan) -> bool {
let scratch = (p.nslots as usize).saturating_sub(p.params.len());
p.params.iter().all(no_eqref)
&& no_eqref(&p.ret)
&& p.locals
.iter()
.enumerate()
.all(|(i, t)| no_eqref(t) || (i == scratch && *t == PlanTy::Eqref))
}
fn inhab_ty(r: &BTreeSet<u32>, s: &BTreeSet<u32>, t: &PlanTy) -> bool {
match t {
PlanTy::Int
| PlanTy::Bool
| PlanTy::Float
| PlanTy::Str
| PlanTy::Opaque(_)
| PlanTy::Option(_)
| PlanTy::List(_)
| PlanTy::Vec(_)
| PlanTy::Bytes => true,
PlanTy::Result(x, e) => inhab_ty(r, s, x) || inhab_ty(r, s, e),
PlanTy::Record(tid) => r.contains(tid),
PlanTy::Sum(tid) => s.contains(tid),
PlanTy::Eqref | PlanTy::Word => false,
}
}
fn inhab_sets(tt: &PlanTypeTable) -> (BTreeSet<u32>, BTreeSet<u32>) {
let mut r: BTreeSet<u32> = BTreeSet::new();
let mut s: BTreeSet<u32> = BTreeSet::new();
for _ in 0..=(tt.records.len() + tt.sums.len()) {
let nr: BTreeSet<u32> = tt
.records
.iter()
.filter(|d| {
tt.records
.iter()
.find(|x| x.tid == d.tid)
.is_some_and(|x| x.fields.iter().all(|f| inhab_ty(&r, &s, f)))
})
.map(|d| d.tid)
.collect();
let ns: BTreeSet<u32> = tt
.sums
.iter()
.filter(|d| {
tt.sums.iter().find(|x| x.tid == d.tid).is_some_and(|x| {
x.ctors
.iter()
.any(|c| c.1.iter().all(|f| inhab_ty(&r, &s, f)))
})
})
.map(|d| d.tid)
.collect();
r = nr;
s = ns;
}
(r, s)
}
fn newtype_grounded(tt: &PlanTypeTable, tid: u32) -> bool {
let mut cur = PlanTy::Record(tid);
for _ in 0..=tt.records.len() {
let PlanTy::Record(t) = cur else {
return true;
};
match tt.records.iter().find(|r| r.tid == t) {
Some(r) if r.fields.len() == 1 => cur = r.fields[0].clone(),
_ => return true,
}
}
false
}
struct LCtx {
n: u32,
cmp: u32,
subj: u32,
}
fn lctx(p: &FnPlan) -> LCtx {
let at = (p.nslots as usize).checked_sub(p.params.len());
if at.and_then(|i| p.locals.get(i)) == Some(&PlanTy::Eqref) {
LCtx {
n: p.nslots,
cmp: p.nslots + 1,
subj: p.nslots,
}
} else {
LCtx {
n: p.nslots,
cmp: p.nslots,
subj: p.nslots,
}
}
}
#[derive(Clone, Debug, PartialEq)]
enum WI {
LocalGet(u32),
LocalSet(u32),
I64Const(i64),
I32Const(i64),
Call(u64),
ReturnCall(u64),
StructNew(u64),
StructGet(u64, u32),
RefIsNull,
I64Eqz,
I32Eqz,
I32Eq,
I32Ne,
I32LtS,
I32GtS,
I32LeS,
I32GeS,
I64Eq,
I64Ne,
I64LtS,
I64GtS,
I64LeS,
I64GeS,
I32And,
I32Or,
I32LtU,
I64ExtendI32U,
F64Const(u64),
F64Eq,
F64Lt,
F64Gt,
F64Le,
F64Ge,
ArrayLen,
ArrayGet(u64),
ArrayNewFixed(u64, u32),
RefTest(u64),
RefCast(u64),
Ret,
Br(u32),
BrIf(u32),
LocalTee(u32),
Select,
I64GtU,
I64Add,
I64Sub,
I64Mul,
I64DivS,
I64And,
I64Xor,
I64RemS,
I64ShrS,
}
#[derive(Clone, Debug, PartialEq)]
enum BI {
Op(WI),
If(Option<PlanTy>, Vec<BI>, Vec<BI>),
NullOf(u64),
NewData(u64, u64),
CastNull(u64),
Block(Option<PlanTy>, Vec<BI>),
}
fn small_read(c: u64, i: u32) -> Vec<WI> {
vec![
WI::LocalGet(i),
WI::StructGet(c, 1),
WI::RefIsNull,
WI::I32Eqz,
WI::BrIf(0),
WI::LocalGet(i),
WI::StructGet(c, 0),
]
}
fn tree_op(w: u32, op: PlanBinOp) -> Vec<WI> {
let (t0, t1, t2) = (w, w + 1, w + 2);
let general = [
WI::LocalGet(t0),
WI::I64Const(1),
WI::I64Add,
WI::I64Const(1),
WI::I64GtU,
];
let mut out = vec![
WI::LocalSet(t1),
WI::LocalSet(t0),
WI::LocalGet(t0),
WI::LocalGet(t1),
];
match op {
PlanBinOp::Add | PlanBinOp::Sub => {
let (sum, y) = if op == PlanBinOp::Add {
(WI::I64Add, WI::LocalGet(t2))
} else {
(WI::I64Sub, WI::LocalGet(t0))
};
out.extend([sum, WI::LocalTee(t2), WI::LocalGet(t0), WI::I64Xor, y]);
out.extend([WI::LocalGet(t1), WI::I64Xor, WI::I64And, WI::I64Const(0)]);
out.extend([WI::I64LtS, WI::BrIf(0), WI::LocalGet(t2)]);
}
_ => {
out.extend([WI::I64Mul, WI::LocalTee(t2), WI::LocalGet(t0), WI::I64Const(1)]);
out.extend(general.clone());
out.extend([WI::Select, WI::I64DivS, WI::LocalGet(t1), WI::I64Ne]);
out.extend([WI::LocalGet(t0), WI::I64Const(-1), WI::I64Eq, WI::LocalGet(t1)]);
out.extend([WI::I64Const(i64::MIN), WI::I64Eq, WI::I32And]);
out.extend(general);
out.extend([WI::Select, WI::BrIf(0), WI::LocalGet(t2)]);
}
}
out
}
pub(crate) fn div_lit_ok(k: i64) -> bool {
k != 0 && k != -1
}
pub(crate) fn mod_lit_ok(k: i64) -> bool {
k != 0
}
fn mul_range(k: i128) -> (i128, i128) {
let (min, max) = (i128::from(i64::MIN), i128::from(i64::MAX));
let (lo, hi) = if k < 0 { (max, min) } else { (min, max) };
let floor = |a: i128| (a * k.signum()).div_euclid(k.abs());
if k == 0 {
(min, max)
} else {
(-floor(-lo), floor(hi))
}
}
fn guard_w(lo: i128, hi: i128, t: u32) -> Vec<WI> {
let (lo, hi) = (lo.max(i64::MIN.into()), hi.min(i64::MAX.into()));
if hi < lo {
vec![WI::LocalSet(t), WI::Br(0)]
} else if hi - lo < i128::from(u64::MAX) {
vec![
WI::LocalSet(t),
WI::LocalGet(t),
WI::I64Const(lo as i64),
WI::I64Sub,
WI::I64Const((hi - lo) as i64),
WI::I64GtU,
WI::BrIf(0),
]
} else {
vec![WI::LocalSet(t)]
}
}
fn fast_w(c: u64, w: u32, t: &PlanWTree, out: &mut Vec<WI>) {
match t {
PlanWTree::Leaf(PlanWLeaf::Word { slot, .. }) => out.push(WI::LocalGet(*slot)),
PlanWTree::Leaf(l) => out.extend(small_read(c, l.loc())),
PlanWTree::Op(op, a, b) => {
fast_w(c, w, a, out);
fast_w(c, w, b, out);
out.extend(tree_op(w, *op));
}
PlanWTree::Lit(k) => out.push(WI::I64Const(*k)),
PlanWTree::DivLit(k, a) if *k > 0 && k.unsigned_abs().is_power_of_two() => {
fast_w(c, w, a, out);
out.extend([WI::I64Const(i64::from(k.trailing_zeros())), WI::I64ShrS]);
}
PlanWTree::DivLit(k, a) => {
fast_w(c, w, a, out);
out.extend([
WI::LocalTee(w),
WI::I64Const(*k),
WI::I64DivS,
WI::LocalGet(w),
WI::I64Const(*k),
WI::I64RemS,
WI::I64Const(63),
WI::I64ShrS,
if *k > 0 { WI::I64Add } else { WI::I64Sub },
]);
}
PlanWTree::ModLit(k, a) if k.unsigned_abs().is_power_of_two() => {
fast_w(c, w, a, out);
out.extend([
WI::I64Const((k.unsigned_abs() - 1) as i64),
WI::I64And,
]);
}
PlanWTree::ModLit(k, a) => {
fast_w(c, w, a, out);
out.extend([
WI::I64Const(*k),
WI::I64RemS,
WI::LocalTee(w),
WI::LocalGet(w),
WI::I64Const(63),
WI::I64ShrS,
WI::I64Const(k.unsigned_abs() as i64),
WI::I64And,
WI::I64Add,
]);
}
PlanWTree::MulLit(k, _, a) => {
fast_w(c, w, a, out);
let (lo, hi) = mul_range(i128::from(*k));
out.extend(guard_w(lo, hi, w));
out.extend([WI::LocalGet(w), WI::I64Const(*k), WI::I64Mul]);
}
PlanWTree::Pick(p, a, b) => {
fast_w(c, w, a, out);
fast_w(c, w, b, out);
out.extend([
WI::LocalSet(w + 1),
WI::LocalSet(w),
WI::LocalGet(w),
WI::LocalGet(w + 1),
WI::LocalGet(w),
WI::LocalGet(w + 1),
match p {
PlanPick::IntMin => WI::I64LeS,
PlanPick::IntMax => WI::I64GeS,
},
WI::Select,
]);
}
}
}
fn pick_op(p: PlanPick) -> PlanBinOp {
match p {
PlanPick::IntMin => PlanBinOp::Lte,
PlanPick::IntMax => PlanBinOp::Gte,
}
}
fn distinct(xs: &[u32]) -> bool {
xs.iter()
.enumerate()
.all(|(i, x)| !xs[i + 1..].contains(x))
}
fn flip(op: PlanBinOp) -> PlanBinOp {
match op {
PlanBinOp::Lt => PlanBinOp::Gt,
PlanBinOp::Gt => PlanBinOp::Lt,
PlanBinOp::Lte => PlanBinOp::Gte,
PlanBinOp::Gte => PlanBinOp::Lte,
other => other,
}
}
fn small_cmp(op: PlanBinOp) -> WI {
match op {
PlanBinOp::Eq => WI::I64Eq,
PlanBinOp::Neq => WI::I64Ne,
PlanBinOp::Lt => WI::I64LtS,
PlanBinOp::Gt => WI::I64GtS,
PlanBinOp::Lte => WI::I64LeS,
_ => WI::I64GeS,
}
}
fn big_cmp(c: u64, s: u32, op: PlanBinOp) -> Vec<WI> {
match op {
PlanBinOp::Lt | PlanBinOp::Lte => vec![
WI::LocalGet(s),
WI::StructGet(c, 2),
WI::I32Const(0),
WI::I32LtS,
],
PlanBinOp::Gt | PlanBinOp::Gte => vec![
WI::LocalGet(s),
WI::StructGet(c, 2),
WI::I32Const(0),
WI::I32GtS,
],
PlanBinOp::Eq => vec![WI::I32Const(0)],
PlanBinOp::Neq => vec![WI::I32Const(1)],
_ => vec![],
}
}
fn cmp_arm(c: u64, s: u32, op: PlanBinOp, k: i64) -> Vec<BI> {
vec![
BI::Op(WI::LocalGet(s)),
BI::Op(WI::StructGet(c, 1)),
BI::Op(WI::RefIsNull),
BI::If(
Some(PlanTy::Bool),
vec![
BI::Op(WI::LocalGet(s)),
BI::Op(WI::StructGet(c, 0)),
BI::Op(WI::I64Const(k)),
BI::Op(small_cmp(op)),
],
big_cmp(c, s, op).into_iter().map(BI::Op).collect(),
),
]
}
fn ops(is: Vec<WI>) -> Vec<BI> {
is.into_iter().map(BI::Op).collect()
}
impl MCtx<'_> {
fn int_cmp_tail(&self, op: PlanBinOp) -> Vec<WI> {
match op {
PlanBinOp::Eq => vec![WI::Call(self.eq)],
PlanBinOp::Neq => vec![WI::Call(self.eq), WI::I32Eqz],
PlanBinOp::Lt => vec![WI::Call(self.cmp), WI::I32Const(0), WI::I32LtS],
PlanBinOp::Gt => vec![WI::Call(self.cmp), WI::I32Const(0), WI::I32GtS],
PlanBinOp::Lte => vec![WI::Call(self.cmp), WI::I32Const(0), WI::I32LeS],
_ => vec![WI::Call(self.cmp), WI::I32Const(0), WI::I32GeS],
}
}
fn str_lit(&self, bytes: &[u8]) -> Vec<BI> {
vec![
BI::Op(WI::I32Const(0)),
BI::Op(WI::I32Const(bytes.len() as i64)),
BI::NewData(self.str_, self.str_seg(bytes)),
]
}
fn concat(&self, n: usize) -> Vec<BI> {
vec![
BI::Op(WI::ArrayNewFixed(self.str_vec, n as u32)),
BI::Op(WI::Call(self.concat)),
]
}
fn dflt(&self, t: &PlanTy) -> Vec<BI> {
match t {
PlanTy::Int => vec![
BI::Op(WI::I64Const(0)),
BI::NullOf(self.mag),
BI::Op(WI::I32Const(0)),
BI::Op(WI::StructNew(self.carrier)),
],
PlanTy::Bool => vec![BI::Op(WI::I32Const(0))],
PlanTy::Record(tid) if self.is_word(*tid) => vec![BI::Op(WI::I64Const(0))],
PlanTy::Record(tid) => vec![BI::NullOf(self.struct_of(*tid))],
PlanTy::Sum(tid) => vec![BI::NullOf(self.sum_root(*tid))],
PlanTy::Option(x) => vec![BI::NullOf(self.opt_struct(x))],
PlanTy::Result(x, e) => vec![BI::NullOf(self.res_struct(x, e))],
PlanTy::Str => vec![BI::NullOf(self.str_)],
PlanTy::Float => vec![BI::Op(WI::F64Const(0))],
PlanTy::List(x) => vec![BI::NullOf(self.list_struct(x))],
PlanTy::Vec(x) => vec![BI::NullOf(self.vec_struct(x))],
PlanTy::Bytes => vec![BI::NullOf(self.bytes_arr)],
_ => vec![],
}
}
fn lower_args(&self, x: &LCtx, g: &Gamma, es: &[PlanExpr]) -> Vec<BI> {
es.iter().flat_map(|e| self.lower(x, g, false, e)).collect()
}
fn lower(&self, x: &LCtx, g: &Gamma, tail: bool, e: &PlanExpr) -> Vec<BI> {
let n = x.n;
match e {
PlanExpr::Literal(PlanLit::Int(k)) => ops(vec![WI::I64Const(*k), WI::Call(self.box_)]),
PlanExpr::Literal(PlanLit::Bool(b)) => ops(vec![WI::I32Const(i64::from(*b))]),
PlanExpr::Literal(PlanLit::Float(bits)) => ops(vec![WI::F64Const(*bits)]),
PlanExpr::Literal(PlanLit::Str(bytes)) => self.str_lit(bytes),
PlanExpr::Local(i) => ops(vec![WI::LocalGet(*i)]),
PlanExpr::Let(b, v, body) => {
let mut out = self.lower(x, g, false, v);
out.push(BI::Op(WI::LocalSet(*b)));
let g2 = match self.ty_of(n, g, false, v) {
Some(t) => upd(g, *b, t),
None => g.clone(),
};
out.extend(self.lower(x, &g2, tail, body));
out
}
PlanExpr::Call(PlanCallee::Fn(f), args) => {
let mut out = self.lower_args(x, g, args);
out.push(BI::Op(WI::Call(u64::from(*f))));
out
}
PlanExpr::Call(PlanCallee::Builtin(b), args) => {
let mut out = self.lower_args(x, g, args);
match (b, self.tys_of(n, g, args).as_deref()) {
(PlanBuiltin::BoolAnd, _) => out.push(BI::Op(WI::I32And)),
(PlanBuiltin::BoolOr, _) => out.push(BI::Op(WI::I32Or)),
(PlanBuiltin::BoolNot, _) => out.push(BI::Op(WI::I32Eqz)),
(PlanBuiltin::ListPrepend, Some([_, PlanTy::List(t)])) => {
out.push(BI::Op(WI::StructNew(self.list_struct(t))))
}
(PlanBuiltin::ListLen, Some([PlanTy::List(t)])) => {
out.extend(self.helper_call(PlanListRole::Len, t));
out.push(BI::Op(WI::Call(self.box_)));
}
(PlanBuiltin::ListReverse, Some([PlanTy::List(t)])) => {
out.extend(self.helper_call(PlanListRole::Reverse, t))
}
(PlanBuiltin::ListConcat, Some([PlanTy::List(t), _])) => {
out.extend(self.helper_call(PlanListRole::Concat, t))
}
(PlanBuiltin::ListTake, Some([PlanTy::List(t), _])) => {
out.push(BI::Op(WI::Call(self.to_i64_sat)));
out.extend(self.helper_call(PlanListRole::Take, t));
}
(PlanBuiltin::ListDrop, Some([PlanTy::List(t), _])) => {
out.push(BI::Op(WI::Call(self.to_i64_sat)));
out.extend(self.helper_call(PlanListRole::Drop, t));
}
(PlanBuiltin::ListContains, Some([PlanTy::List(t), _])) => {
out.extend(self.helper_call(PlanListRole::Contains, t))
}
(PlanBuiltin::BytesOfList, _) => {
out.extend(self.bytes_call(PlanBytesRole::Pack))
}
(PlanBuiltin::BytesValues, _) => {
out.extend(self.bytes_call(PlanBytesRole::Unpack))
}
(PlanBuiltin::BytesLen, _) => out.extend(ops(vec![
WI::ArrayLen,
WI::I64ExtendI32U,
WI::Call(self.box_),
])),
(PlanBuiltin::BytesConcat, _) => {
out.extend(self.bytes_call(PlanBytesRole::Concat))
}
(PlanBuiltin::BytesTake, _) => {
out.push(BI::Op(WI::Call(self.to_i64_sat)));
out.extend(self.bytes_call(PlanBytesRole::Take));
}
(PlanBuiltin::BytesDrop, _) => {
out.push(BI::Op(WI::Call(self.to_i64_sat)));
out.extend(self.bytes_call(PlanBytesRole::Drop));
}
(PlanBuiltin::StrFromInt, _) => out.push(BI::Op(WI::Call(self.from_int))),
_ => {}
}
out
}
PlanExpr::Call(PlanCallee::Intrinsic(i), args) => {
let mut out = self.lower_args(x, g, args);
out.extend(ops(vec![
WI::I32Const(i64::from(*i == PlanIntrinsic::IntModEuclid)),
WI::Call(self.divmod),
]));
out
}
PlanExpr::Call(PlanCallee::Bitwise(b), args) => {
let mut out = self.lower_args(x, g, args);
out.extend(ops(vec![WI::I32Const(b.flag()), WI::Call(self.bitwise)]));
out
}
PlanExpr::Call(PlanCallee::Pick(p), args) => {
let [a, b] = args.as_slice() else {
return vec![];
};
let op = pick_op(*p);
let mut out = self.lower(x, g, false, a);
out.extend(self.lower(x, g, false, b));
out.extend(ops(self.int_cmp_tail(op)));
out.push(BI::If(
Some(PlanTy::Int),
self.lower(x, g, false, a),
self.lower(x, g, false, b),
));
out
}
PlanExpr::TailCall(f, args) => {
let mut out = self.lower_args(x, g, args);
out.push(BI::Op(WI::ReturnCall(u64::from(*f))));
out
}
PlanExpr::BinOp(op, l, r) => {
let lt = self.ty_of(n, g, false, l);
match lt {
Some(PlanTy::Bool) => {
let mut out = self.lower(x, g, false, l);
out.extend(self.lower(x, g, false, r));
out.push(BI::Op(if *op == PlanBinOp::Eq {
WI::I32Eq
} else {
WI::I32Ne
}));
out
}
Some(PlanTy::Float) => {
let mut out = self.lower(x, g, false, l);
out.extend(self.lower(x, g, false, r));
out.push(BI::Op(match op {
PlanBinOp::Eq => WI::F64Eq,
PlanBinOp::Lt => WI::F64Lt,
PlanBinOp::Gt => WI::F64Gt,
PlanBinOp::Lte => WI::F64Le,
_ => WI::F64Ge,
}));
out
}
Some(PlanTy::Str) => {
let mut out = self.lower(x, g, false, l);
out.extend(self.lower(x, g, false, r));
match op {
PlanBinOp::Add => out.extend(self.concat(2)),
PlanBinOp::Eq => out.push(BI::Op(WI::Call(self.streq))),
_ => out.extend(ops(vec![WI::Call(self.streq), WI::I32Eqz])),
}
out
}
_ => {
if is_arith(*op) {
let mut out = self.lower(x, g, false, l);
out.extend(self.lower(x, g, false, r));
out.push(BI::Op(WI::Call(self.arith_idx(*op))));
return out;
}
let lit = |ex: &PlanExpr| match ex {
PlanExpr::Literal(PlanLit::Int(k)) => Some(*k),
_ => None,
};
let slot = |ex: &PlanExpr| match ex {
PlanExpr::Local(i) => Some(*i),
_ => None,
};
match (lit(l), lit(r)) {
(Some(k), _) => match slot(r) {
Some(i) => cmp_arm(self.carrier, i, flip(*op), k),
None => {
let mut out = self.lower(x, g, false, r);
out.push(BI::Op(WI::LocalSet(x.cmp)));
out.extend(cmp_arm(self.carrier, x.cmp, flip(*op), k));
out
}
},
(None, Some(k)) => match slot(l) {
Some(i) => cmp_arm(self.carrier, i, *op, k),
None => {
let mut out = self.lower(x, g, false, l);
out.push(BI::Op(WI::LocalSet(x.cmp)));
out.extend(cmp_arm(self.carrier, x.cmp, *op, k));
out
}
},
(None, None) => {
let mut out = self.lower(x, g, false, l);
out.extend(self.lower(x, g, false, r));
out.extend(ops(self.int_cmp_tail(*op)));
out
}
}
}
}
}
PlanExpr::Neg(ex) => {
let mut out = self.lower(x, g, false, ex);
out.push(BI::Op(WI::Call(self.neg)));
out
}
PlanExpr::If(c, t, el) => {
let mut out = self.lower(x, g, false, c);
out.push(BI::If(
self.ty_of(n, g, tail, t),
self.lower(x, g, tail, t),
self.lower(x, g, tail, el),
));
out
}
PlanExpr::RecordCreate(tid, fs) => {
let mut out = self.lower_args(x, g, fs);
if self.is_word(*tid) {
out.push(BI::Op(WI::Call(self.to_i64_chk)));
} else {
out.push(BI::Op(WI::StructNew(self.struct_of(*tid))));
}
out
}
PlanExpr::Project(tid, i, base) => {
let mut out = self.lower(x, g, false, base);
if self.is_word(*tid) {
out.push(BI::Op(WI::Call(self.box_)));
} else {
out.push(BI::Op(WI::StructGet(self.struct_of(*tid), *i)));
}
out
}
PlanExpr::Call(PlanCallee::Lazy(lb), args) => {
let [o, d] = args.as_slice() else {
return vec![];
};
if let Some((v, i)) = vec_get_or(*lb, o, d) {
let Some(PlanTy::Vec(t)) = g.get(&v) else {
return vec![];
};
let ti = self.to_index;
let mut out = ops(vec![
WI::LocalGet(i),
WI::Call(ti),
WI::I32Const(0),
WI::I32GeS,
WI::LocalGet(i),
WI::Call(ti),
WI::LocalGet(v),
WI::ArrayLen,
WI::I32LtU,
WI::I32And,
]);
out.push(BI::If(
Some(t.as_ref().clone()),
ops(vec![
WI::LocalGet(v),
WI::LocalGet(i),
WI::Call(ti),
WI::ArrayGet(self.vec_struct(t)),
]),
self.lower(x, g, false, d),
));
return out;
}
if let Some((is_mod, _, _)) = div_or(*lb, o, d) {
let c = x.cmp;
let mut out = self.lower(x, g, false, o);
out.extend(self.lower(x, g, false, d));
out.extend(ops(vec![
WI::LocalSet(c + 3),
WI::LocalSet(c + 2),
WI::LocalSet(c + 1),
WI::LocalGet(c + 2),
WI::StructGet(self.carrier, 1),
WI::RefIsNull,
WI::LocalGet(c + 2),
WI::StructGet(self.carrier, 0),
WI::I64Eqz,
WI::I32And,
]));
out.push(BI::If(
Some(PlanTy::Int),
ops(vec![WI::LocalGet(c + 3)]),
ops(vec![
WI::LocalGet(c + 1),
WI::LocalGet(c + 2),
WI::I32Const(i64::from(is_mod)),
WI::Call(self.divmod),
]),
));
return out;
}
let (st, payload_ty) = match (lb, self.ty_of(n, g, false, o)) {
(PlanLazy::OptWithDefault, Some(PlanTy::Option(t))) => {
(self.opt_struct(&t), *t)
}
(PlanLazy::ResWithDefault, Some(PlanTy::Result(t, er))) => {
(self.res_struct(&t, &er), *t)
}
_ => return vec![],
};
let mut out = self.lower(x, g, false, o);
out.push(BI::Op(WI::LocalSet(x.subj)));
out.extend(tag_test(x.subj, st));
out.push(BI::If(
Some(payload_ty),
ops(vec![
WI::LocalGet(x.subj),
WI::RefCast(st),
WI::StructGet(st, 1),
]),
self.lower(x, g, false, d),
));
out
}
PlanExpr::Construct(c, ty, args) => match (c, ty) {
(PlanCtor::User(tid, k), _) => {
let mut out = self.lower_args(x, g, args);
out.push(BI::Op(WI::StructNew(self.ctor_struct(*tid, *k))));
out
}
(PlanCtor::Some, PlanTy::Option(t)) => {
let mut out = ops(vec![WI::I32Const(1)]);
out.extend(self.lower_args(x, g, args));
out.push(BI::Op(WI::StructNew(self.opt_struct(t))));
out
}
(PlanCtor::None, PlanTy::Option(t)) => {
let mut out = ops(vec![WI::I32Const(0)]);
out.extend(self.dflt(t));
out.extend(self.lower_args(x, g, args));
out.push(BI::Op(WI::StructNew(self.opt_struct(t))));
out
}
(PlanCtor::Ok, PlanTy::Result(t, er)) => {
let mut out = ops(vec![WI::I32Const(1)]);
out.extend(self.lower_args(x, g, args));
out.extend(self.dflt(er));
out.push(BI::Op(WI::StructNew(self.res_struct(t, er))));
out
}
(PlanCtor::Err, PlanTy::Result(t, er)) => {
let mut out = ops(vec![WI::I32Const(0)]);
out.extend(self.dflt(t));
out.extend(self.lower_args(x, g, args));
out.push(BI::Op(WI::StructNew(self.res_struct(t, er))));
out
}
_ => vec![],
},
PlanExpr::Match(s, arms) => {
let bt = self.ty_of(n, g, tail, e);
let sc = self.lower(x, g, false, s);
match self.ty_of(n, g, false, s) {
Some(PlanTy::Int) => self.lower_int_arms(x, g, tail, &sc, &bt, arms),
Some(PlanTy::Bool) => {
let mut out = sc;
if let [(PlanPat::LitBool(v), t), (_, el), ..] = arms.as_slice() {
let (a, b) = if *v { (t, el) } else { (el, t) };
out.push(BI::If(
bt,
self.lower(x, g, tail, a),
self.lower(x, g, tail, b),
));
}
out
}
Some(PlanTy::Option(t)) => {
let mut out = sc;
out.push(BI::Op(WI::LocalSet(x.subj)));
if let [(p1, b1), (p2, b2), ..] = arms.as_slice()
&& let Some((swap, sb)) = opt_pick(p1, p2)
{
let st = self.opt_struct(&t);
let (some_b, none_b) = if swap { (b2, b1) } else { (b1, b2) };
let gs = bind_one(n, g, sb, &t).unwrap_or_else(|| g.clone());
out.extend(tag_test(x.subj, st));
let mut then_b = bind_field(x.subj, st, 1, sb);
then_b.extend(self.lower(x, &gs, tail, some_b));
out.push(BI::If(bt, then_b, self.lower(x, g, tail, none_b)));
}
out
}
Some(PlanTy::Result(t, er)) => {
let mut out = sc;
out.push(BI::Op(WI::LocalSet(x.subj)));
if let [(p1, b1), (p2, b2), ..] = arms.as_slice()
&& let Some((swap, ob, eb)) = res_pick(p1, p2)
{
let st = self.res_struct(&t, &er);
let (ok_b, err_b) = if swap { (b2, b1) } else { (b1, b2) };
let go = bind_one(n, g, ob, &t).unwrap_or_else(|| g.clone());
let ge = bind_one(n, g, eb, &er).unwrap_or_else(|| g.clone());
out.extend(tag_test(x.subj, st));
let mut then_b = bind_field(x.subj, st, 1, ob);
then_b.extend(self.lower(x, &go, tail, ok_b));
let mut else_b = bind_field(x.subj, st, 2, eb);
else_b.extend(self.lower(x, &ge, tail, err_b));
out.push(BI::If(bt, then_b, else_b));
}
out
}
Some(PlanTy::Sum(tid)) => {
let mut out = sc;
out.push(BI::Op(WI::LocalSet(x.subj)));
out.extend(self.lower_var_arms(x, g, tail, &bt, tid, arms));
out
}
Some(PlanTy::Str) => {
let mut out = sc;
out.push(BI::Op(WI::LocalSet(x.subj)));
out.extend(self.lower_str_arms(x, g, tail, &bt, arms));
out
}
Some(PlanTy::Record(tid)) => {
let mut out = sc;
out.push(BI::Op(WI::LocalSet(x.subj)));
if let [(PlanPat::Tuple(bs), b), ..] = arms.as_slice() {
out.extend(extract(x.subj, self.struct_of(tid), bs));
let g2 = self
.rec_fields(tid)
.and_then(|fts| bind_tys(n, g, bs, fts))
.unwrap_or_else(|| g.clone());
out.extend(self.lower(x, &g2, tail, b));
}
out
}
Some(PlanTy::List(t)) => {
let mut out = sc;
out.push(BI::Op(WI::LocalSet(x.subj)));
if let [(p1, b1), (p2, b2), ..] = arms.as_slice()
&& let Some((swap, h, tl)) = list_pick(p1, p2)
{
let (empty_b, cons_b) = if swap { (b2, b1) } else { (b1, b2) };
let lt = PlanTy::List(t.clone());
let gc = bind_tys(n, g, &[h, tl], &[(*t).clone(), lt])
.unwrap_or_else(|| g.clone());
let mut else_b = extract(x.subj, self.list_struct(&t), &[h, tl]);
else_b.extend(self.lower(x, &gc, tail, cons_b));
out.extend(ops(vec![WI::LocalGet(x.subj), WI::RefIsNull]));
out.push(BI::If(bt, self.lower(x, g, tail, empty_b), else_b));
}
out
}
_ => vec![],
}
}
PlanExpr::Interp(parts) => {
let mut out = self.lower_args(x, g, parts);
out.extend(self.concat(parts.len()));
out
}
PlanExpr::List(t, items) => {
if items.is_empty() {
return vec![BI::NullOf(self.list_struct(t))];
}
let Some(f) = self.list_cons(t) else {
return vec![];
};
let mut out = self.lower_args(x, g, items);
out.push(BI::NullOf(self.list_struct(t)));
out.extend(items.iter().map(|_| BI::Op(WI::Call(u64::from(f)))));
out
}
PlanExpr::Try(inner, ret) => match (self.ty_of(n, g, false, inner), ret) {
(Some(PlanTy::Result(t, er)), PlanTy::Result(t2, er2)) => {
let mut out = self.lower(x, g, false, inner);
out.push(BI::Op(WI::LocalSet(x.subj)));
out.extend(self.try_tail(x, &t, &er, t2, er2));
out
}
_ => vec![],
},
PlanExpr::Scope(inner) => self.lower(x, g, tail, inner),
PlanExpr::IntWord(t, w) => {
let mut out = self.ahead_w(t);
let mut fast = Vec::new();
fast_w(self.carrier, *w, t, &mut fast);
fast.extend([WI::Call(self.box_), WI::Br(1)]);
let mut body = vec![BI::Block(None, ops(fast))];
body.extend(self.exact_b(t));
out.push(BI::Block(Some(PlanTy::Int), body));
out
}
PlanExpr::IntCmp(op, a, b, w) => {
let mut out = self.ahead_w(a);
out.extend(self.ahead_w(b));
let mut fast = Vec::new();
fast_w(self.carrier, *w, a, &mut fast);
fast_w(self.carrier, *w, b, &mut fast);
fast.extend([small_cmp(*op), WI::Br(1)]);
let mut body = vec![BI::Block(None, ops(fast))];
body.extend(self.exact_b(a));
body.extend(self.exact_b(b));
body.extend(ops(self.int_cmp_tail(*op)));
out.push(BI::Block(Some(PlanTy::Bool), body));
out
}
}
}
fn try_tail(&self, x: &LCtx, t: &PlanTy, er: &PlanTy, t2: &PlanTy, er2: &PlanTy) -> Vec<BI> {
let rs = self.res_struct(t, er);
let mut out = tag_test(x.subj, rs);
let then_b = ops(vec![
WI::LocalGet(x.subj),
WI::RefCast(rs),
WI::StructGet(rs, 1),
]);
let mut else_b = ops(vec![WI::I32Const(0)]);
else_b.extend(self.dflt(t2));
else_b.extend(ops(vec![
WI::LocalGet(x.subj),
WI::RefCast(rs),
WI::StructGet(rs, 2),
WI::StructNew(self.res_struct(t2, er2)),
WI::Ret,
]));
out.push(BI::If(Some(t.clone()), then_b, else_b));
out
}
fn lower_int_arms(
&self,
x: &LCtx,
g: &Gamma,
tail: bool,
sc: &[BI],
bt: &Option<PlanTy>,
arms: &[(PlanPat, PlanExpr)],
) -> Vec<BI> {
let Some(((p, b), rest)) = arms.split_first() else {
return vec![];
};
match p {
PlanPat::LitInt(k) => {
let mut out = sc.to_vec();
out.extend(ops(vec![
WI::I64Const(*k),
WI::Call(self.box_),
WI::Call(self.eq),
]));
out.push(BI::If(
bt.clone(),
self.lower(x, g, tail, b),
self.lower_int_arms(x, g, tail, sc, bt, rest),
));
out
}
PlanPat::Wild => self.lower(x, g, tail, b),
PlanPat::Bind(s) => {
let mut out = sc.to_vec();
out.push(BI::Op(WI::LocalSet(*s)));
out.extend(self.lower(x, &upd(g, *s, PlanTy::Int), tail, b));
out
}
_ => vec![],
}
}
fn lower_var_arms(
&self,
x: &LCtx,
g: &Gamma,
tail: bool,
bt: &Option<PlanTy>,
tid: u32,
arms: &[(PlanPat, PlanExpr)],
) -> Vec<BI> {
match arms {
[] => vec![],
[(p, b)] => match p {
PlanPat::Ctor(PlanCtor::User(t2, c), bs) => {
let mut out = extract(x.subj, self.ctor_struct(*t2, *c), bs);
let g2 = self
.var_arm_gamma(x.n, g, tid, p)
.unwrap_or_else(|| g.clone());
out.extend(self.lower(x, &g2, tail, b));
out
}
_ => self.lower(x, g, tail, b),
},
[(p, b), rest @ ..] => match p {
PlanPat::Ctor(PlanCtor::User(t2, c), bs) => {
let st = self.ctor_struct(*t2, *c);
let mut then_b = extract(x.subj, st, bs);
let g2 = self
.var_arm_gamma(x.n, g, tid, p)
.unwrap_or_else(|| g.clone());
then_b.extend(self.lower(x, &g2, tail, b));
vec![
BI::Op(WI::LocalGet(x.subj)),
BI::Op(WI::RefTest(st)),
BI::If(
bt.clone(),
then_b,
self.lower_var_arms(x, g, tail, bt, tid, rest),
),
]
}
PlanPat::Wild => self.lower(x, g, tail, b),
_ => vec![],
},
}
}
fn lower_str_arms(
&self,
x: &LCtx,
g: &Gamma,
tail: bool,
bt: &Option<PlanTy>,
arms: &[(PlanPat, PlanExpr)],
) -> Vec<BI> {
let Some(((p, b), rest)) = arms.split_first() else {
return vec![];
};
match p {
PlanPat::LitStr(k) => {
let mut out = vec![BI::Op(WI::LocalGet(x.subj)), BI::CastNull(self.str_)];
out.extend(self.str_lit(k));
out.push(BI::Op(WI::Call(self.streq)));
out.push(BI::If(
bt.clone(),
self.lower(x, g, tail, b),
self.lower_str_arms(x, g, tail, bt, rest),
));
out
}
_ => self.lower(x, g, tail, b),
}
}
}
fn tag_test(ss: u32, idx: u64) -> Vec<BI> {
ops(vec![
WI::LocalGet(ss),
WI::RefCast(idx),
WI::StructGet(idx, 0),
WI::I32Const(1),
WI::I32Eq,
])
}
fn bind_field(ss: u32, idx: u64, i: u32, b: u32) -> Vec<BI> {
if b == PLAN_NO_SLOT {
vec![]
} else {
ops(vec![
WI::LocalGet(ss),
WI::RefCast(idx),
WI::StructGet(idx, i),
WI::LocalSet(b),
])
}
}
fn extract(ss: u32, idx: u64, bs: &[u32]) -> Vec<BI> {
bs.iter()
.enumerate()
.flat_map(|(i, b)| bind_field(ss, idx, i as u32, *b))
.collect()
}
fn uleb(v: u64, out: &mut Vec<u8>) -> Option<()> {
if v >= 4_294_967_296 {
return None;
}
let mut v = v;
loop {
let byte = (v & 0x7f) as u8;
v >>= 7;
if v == 0 {
out.push(byte);
return Some(());
}
out.push(byte | 0x80);
}
}
fn sleb(v: i64, out: &mut Vec<u8>) {
let mut v = v;
loop {
let byte = (v & 0x7f) as u8;
v >>= 7;
let done = (v == 0 && byte & 0x40 == 0) || (v == -1 && byte & 0x40 != 0);
if done {
out.push(byte);
return;
}
out.push(byte | 0x80);
}
}
fn s33(idx: u64, out: &mut Vec<u8>) -> Option<()> {
if idx >= 4_294_967_296 {
return None;
}
sleb(idx as i64, out);
Some(())
}
impl MCtx<'_> {
fn val_ty(&self, t: &PlanTy, out: &mut Vec<u8>) -> Option<()> {
let heap = |i: u64, out: &mut Vec<u8>| {
out.push(0x63);
s33(i, out)
};
match t {
PlanTy::Int => heap(self.carrier, out),
PlanTy::Bool => {
out.push(0x7f);
Some(())
}
PlanTy::Record(tid) if self.is_word(*tid) => {
out.push(0x7e);
Some(())
}
PlanTy::Record(tid) => heap(self.struct_of(*tid), out),
PlanTy::Sum(tid) => heap(self.sum_root(*tid), out),
PlanTy::Option(x) => heap(self.opt_struct(x), out),
PlanTy::Result(x, e) => heap(self.res_struct(x, e), out),
PlanTy::Eqref => {
out.push(0x6d);
Some(())
}
PlanTy::Float => {
out.push(0x7c);
Some(())
}
PlanTy::Str => heap(self.str_, out),
PlanTy::Vec(x) => heap(self.vec_struct(x), out),
PlanTy::List(x) => heap(self.list_struct(x), out),
PlanTy::Opaque(tid) => heap(self.opaque_struct(*tid), out),
PlanTy::Bytes => heap(self.bytes_arr, out),
PlanTy::Word => {
out.push(0x7e);
Some(())
}
}
}
fn enc_w(&self, i: &WI, out: &mut Vec<u8>) -> Option<()> {
match i {
WI::LocalGet(x) => {
out.push(0x20);
uleb(u64::from(*x), out)?
}
WI::LocalSet(x) => {
out.push(0x21);
uleb(u64::from(*x), out)?
}
WI::I64Const(k) => {
out.push(0x42);
sleb(*k, out)
}
WI::I32Const(k) => {
if *k < i64::from(i32::MIN) || *k > i64::from(i32::MAX) {
return None;
}
out.push(0x41);
sleb(*k, out)
}
WI::Call(f) => {
out.push(0x10);
uleb(*f, out)?
}
WI::ReturnCall(f) => {
out.push(0x12);
uleb(*f, out)?
}
WI::StructNew(t) => {
out.extend([0xfb, 0x00]);
uleb(*t, out)?
}
WI::StructGet(t, fld) => {
out.extend([0xfb, 0x02]);
uleb(*t, out)?;
uleb(u64::from(*fld), out)?
}
WI::RefIsNull => out.push(0xd1),
WI::I64Eqz => out.push(0x50),
WI::I32Eqz => out.push(0x45),
WI::I32Eq => out.push(0x46),
WI::I32Ne => out.push(0x47),
WI::I32LtS => out.push(0x48),
WI::I32GtS => out.push(0x4a),
WI::I32LeS => out.push(0x4c),
WI::I32GeS => out.push(0x4e),
WI::I64Eq => out.push(0x51),
WI::I64Ne => out.push(0x52),
WI::I64LtS => out.push(0x53),
WI::I64GtS => out.push(0x55),
WI::I64LeS => out.push(0x57),
WI::I64GeS => out.push(0x59),
WI::I32And => out.push(0x71),
WI::I32Or => out.push(0x72),
WI::I32LtU => out.push(0x49),
WI::I64ExtendI32U => out.push(0xad),
WI::F64Const(bits) => {
out.push(0x44);
out.extend(bits.to_le_bytes())
}
WI::F64Eq => out.push(0x61),
WI::F64Lt => out.push(0x63),
WI::F64Gt => out.push(0x64),
WI::F64Le => out.push(0x65),
WI::F64Ge => out.push(0x66),
WI::ArrayLen => out.extend([0xfb, 0x0f]),
WI::ArrayGet(t) => {
out.extend([0xfb, 0x0b]);
uleb(*t, out)?
}
WI::ArrayNewFixed(t, n) => {
out.extend([0xfb, 0x08]);
uleb(*t, out)?;
uleb(u64::from(*n), out)?
}
WI::RefTest(t) => {
out.extend([0xfb, 0x14]);
s33(*t, out)?
}
WI::RefCast(t) => {
out.extend([0xfb, 0x16]);
s33(*t, out)?
}
WI::Ret => out.push(0x0f),
WI::Br(d) => {
out.push(0x0c);
uleb(u64::from(*d), out)?
}
WI::BrIf(d) => {
out.push(0x0d);
uleb(u64::from(*d), out)?
}
WI::LocalTee(x) => {
out.push(0x22);
uleb(u64::from(*x), out)?
}
WI::Select => out.push(0x1b),
WI::I64GtU => out.push(0x56),
WI::I64RemS => out.push(0x81),
WI::I64ShrS => out.push(0x87),
WI::I64Add => out.push(0x7c),
WI::I64Sub => out.push(0x7d),
WI::I64Mul => out.push(0x7e),
WI::I64DivS => out.push(0x7f),
WI::I64And => out.push(0x83),
WI::I64Xor => out.push(0x85),
}
Some(())
}
fn enc(&self, bs: &[BI], out: &mut Vec<u8>) -> Option<()> {
for b in bs {
match b {
BI::Op(i) => self.enc_w(i, out)?,
BI::Block(bt, body) => {
out.push(0x02);
match bt {
None => out.push(0x40),
Some(t) => self.val_ty(t, out)?,
}
self.enc(body, out)?;
out.push(0x0b);
}
BI::If(bt, t, e) => {
out.push(0x04);
self.val_ty(bt.as_ref()?, out)?;
self.enc(t, out)?;
out.push(0x05);
self.enc(e, out)?;
out.push(0x0b);
}
BI::NullOf(ht) => {
out.push(0xd0);
s33(*ht, out)?
}
BI::NewData(ty, seg) => {
out.extend([0xfb, 0x09]);
uleb(*ty, out)?;
uleb(*seg, out)?
}
BI::CastNull(ht) => {
out.extend([0xfb, 0x17]);
s33(*ht, out)?
}
}
}
Some(())
}
fn lower_plan(&self, p: &FnPlan) -> Vec<BI> {
self.lower(&lctx(p), ¶ms_gamma(&p.params), true, &p.body)
}
fn enc_zero(&self, t: &PlanTy, out: &mut Vec<u8>) -> Option<()> {
match t {
PlanTy::Bool => out.extend([0x41, 0x00]),
PlanTy::Float => {
out.push(0x44);
out.extend([0; 8]);
}
PlanTy::Eqref => out.extend([0xd0, 0x6d]),
PlanTy::Word => out.extend([0x42, 0x00]),
_ => {
let mut ty = Vec::new();
self.val_ty(t, &mut ty)?;
if ty.first() != Some(&0x63) {
return None;
}
out.push(0xd0);
out.extend(&ty[1..]);
}
}
Some(())
}
fn enc_loop_body(
&self,
bs: &[BI],
self_idx: u64,
params: u32,
depth: u32,
out: &mut Vec<u8>,
) -> Option<()> {
for b in bs {
match b {
BI::Op(WI::ReturnCall(g)) if *g == self_idx => {
for k in (0..params).rev() {
out.push(0x21);
uleb(u64::from(k), out)?;
}
out.push(0x0c);
uleb(u64::from(depth), out)?;
}
BI::If(bt, t, e) => {
out.push(0x04);
self.val_ty(bt.as_ref()?, out)?;
self.enc_loop_body(t, self_idx, params, depth + 1, out)?;
out.push(0x05);
self.enc_loop_body(e, self_idx, params, depth + 1, out)?;
out.push(0x0b);
}
other => self.enc(std::slice::from_ref(other), out)?,
}
}
Some(())
}
fn code_entry_bytes(&self, self_idx: u32, p: &FnPlan) -> Option<Vec<u8>> {
let mut entry = Vec::new();
uleb(p.locals.len() as u64, &mut entry)?;
for t in &p.locals {
entry.push(0x01);
self.val_ty(t, &mut entry)?;
}
let body = self.lower_plan(p);
if p.self_loop {
let params = u32::try_from(p.params.len()).ok()?;
entry.extend([0x03, 0x40]);
for (i, t) in p.locals.iter().enumerate() {
self.enc_zero(t, &mut entry)?;
entry.push(0x21);
uleb(u64::from(params) + i as u64, &mut entry)?;
}
self.enc_loop_body(&body, u64::from(self_idx), params, 0, &mut entry)?;
entry.extend([0x0f, 0x0b, 0x00]);
} else {
self.enc(&body, &mut entry)?;
}
entry.push(0x0b);
let mut out = Vec::new();
uleb(entry.len() as u64, &mut out)?;
out.extend(entry);
Some(out)
}
fn val_t(&self, t: &PlanTy) -> Option<ValT> {
let r = |i: u64| (i < 4_294_967_296).then_some(ValT::RefNull(i as u32));
match t {
PlanTy::Int => r(self.carrier),
PlanTy::Bool => Some(ValT::I32),
PlanTy::Float => Some(ValT::F64),
PlanTy::Eqref => Some(ValT::Eqref),
PlanTy::Word => Some(ValT::I64),
PlanTy::Record(tid) if self.is_word(*tid) => Some(ValT::I64),
PlanTy::Record(tid) => r(self.struct_of(*tid)),
PlanTy::Sum(tid) => r(self.sum_root(*tid)),
PlanTy::Option(x) => r(self.opt_struct(x)),
PlanTy::Result(x, e) => r(self.res_struct(x, e)),
PlanTy::Str => r(self.str_),
PlanTy::Vec(x) => r(self.vec_struct(x)),
PlanTy::List(x) => r(self.list_struct(x)),
PlanTy::Opaque(tid) => r(self.opaque_struct(*tid)),
PlanTy::Bytes => r(self.bytes_arr),
}
}
}
fn lowered_calls(bs: &[BI], out: &mut Vec<u64>) {
for b in bs {
match b {
BI::Op(WI::Call(f)) | BI::Op(WI::ReturnCall(f)) => out.push(*f),
BI::If(_, t, e) => {
lowered_calls(t, out);
lowered_calls(e, out);
}
BI::Block(_, body) => lowered_calls(body, out),
_ => {}
}
}
}
fn literal_list_types(e: &PlanExpr, out: &mut Vec<PlanTy>) {
match e {
PlanExpr::Literal(_) | PlanExpr::Local(_) => {}
PlanExpr::Let(_, v, b) | PlanExpr::BinOp(_, v, b) => {
literal_list_types(v, out);
literal_list_types(b, out);
}
PlanExpr::List(t, items) => {
if !items.is_empty() {
out.push(t.clone());
}
items.iter().for_each(|a| literal_list_types(a, out));
}
PlanExpr::Call(_, args)
| PlanExpr::TailCall(_, args)
| PlanExpr::RecordCreate(_, args)
| PlanExpr::Construct(_, _, args)
| PlanExpr::Interp(args) => args.iter().for_each(|a| literal_list_types(a, out)),
PlanExpr::Neg(x)
| PlanExpr::Project(_, _, x)
| PlanExpr::Try(x, _)
| PlanExpr::Scope(x) => literal_list_types(x, out),
PlanExpr::IntWord(..) | PlanExpr::IntCmp(..) => {}
PlanExpr::If(c, t, el) => {
literal_list_types(c, out);
literal_list_types(t, out);
literal_list_types(el, out);
}
PlanExpr::Match(s, arms) => {
literal_list_types(s, out);
arms.iter().for_each(|(_, b)| literal_list_types(b, out));
}
}
}
fn plan_targets(tt: &PlanTypeTable, p: &FnPlan) -> Vec<u32> {
let mut out = Vec::new();
call_targets(&p.body, &mut out);
let mut tys = Vec::new();
literal_list_types(&p.body, &mut tys);
for t in tys {
if let Some((_, f)) = tt.list_cons.iter().find(|l| l.0 == t) {
out.push(*f);
}
}
out
}
fn string_lits<'e>(e: &'e PlanExpr, out: &mut Vec<&'e [u8]>) {
match e {
PlanExpr::Literal(PlanLit::Str(b)) => out.push(b),
PlanExpr::Literal(_) | PlanExpr::Local(_) => {}
PlanExpr::Let(_, v, b) => {
string_lits(v, out);
string_lits(b, out);
}
PlanExpr::Call(_, args)
| PlanExpr::TailCall(_, args)
| PlanExpr::RecordCreate(_, args)
| PlanExpr::Construct(_, _, args)
| PlanExpr::Interp(args)
| PlanExpr::List(_, args) => args.iter().for_each(|a| string_lits(a, out)),
PlanExpr::BinOp(_, l, r) => {
string_lits(l, out);
string_lits(r, out);
}
PlanExpr::Neg(x)
| PlanExpr::Project(_, _, x)
| PlanExpr::Try(x, _)
| PlanExpr::Scope(x) => string_lits(x, out),
PlanExpr::IntWord(..) | PlanExpr::IntCmp(..) => {}
PlanExpr::If(c, t, el) => {
string_lits(c, out);
string_lits(t, out);
string_lits(el, out);
}
PlanExpr::Match(s, arms) => {
string_lits(s, out);
for (p, b) in arms {
if let PlanPat::LitStr(k) = p {
out.push(k);
}
string_lits(b, out);
}
}
}
}
fn is_descent(e: &PlanExpr) -> bool {
match e {
PlanExpr::BinOp(PlanBinOp::Sub, l, r) => {
**l == PlanExpr::Local(0) && **r == PlanExpr::Literal(PlanLit::Int(1))
}
PlanExpr::IntWord(PlanWTree::Op(PlanBinOp::Sub, l, r), _) => {
**l == PlanWTree::Leaf(PlanWLeaf::Local(0)) && **r == PlanWTree::Lit(1)
}
_ => false,
}
}
fn tot_w(mul_ok: bool, t: &PlanWTree) -> bool {
match t {
PlanWTree::Leaf(PlanWLeaf::Local(_)) | PlanWTree::Lit(_) => true,
PlanWTree::Op(op, a, b) => {
(matches!(op, PlanBinOp::Add | PlanBinOp::Sub) || (*op == PlanBinOp::Mul && mul_ok))
&& tot_w(mul_ok, a)
&& tot_w(mul_ok, b)
}
PlanWTree::MulLit(_, _, a) => mul_ok && tot_w(mul_ok, a),
PlanWTree::DivLit(..) | PlanWTree::ModLit(..) => false,
PlanWTree::Leaf(PlanWLeaf::Field { .. } | PlanWLeaf::Word { .. }) | PlanWTree::Pick(..) => {
false
}
}
}
fn uses_mul_w(t: &PlanWTree) -> bool {
match t {
PlanWTree::Op(op, a, b) => *op == PlanBinOp::Mul || uses_mul_w(a) || uses_mul_w(b),
PlanWTree::MulLit(..) => true,
_ => false,
}
}
fn tot_e(mem: &BTreeSet<u32>, mul_ok: bool, calls: bool, lim: u64, e: &PlanExpr) -> bool {
match e {
PlanExpr::Literal(PlanLit::Int(_) | PlanLit::Bool(_)) | PlanExpr::Local(_) => true,
PlanExpr::BinOp(op, l, r) => {
(matches!(op, PlanBinOp::Add | PlanBinOp::Sub) || (*op == PlanBinOp::Mul && mul_ok))
&& tot_e(mem, mul_ok, calls, lim, l)
&& tot_e(mem, mul_ok, calls, lim, r)
}
PlanExpr::Call(PlanCallee::Fn(g), args) | PlanExpr::TailCall(g, args) => {
calls
&& mem.contains(g)
&& args.first().is_some_and(is_descent)
&& args.iter().all(|a| tot_e(mem, mul_ok, calls, lim, a))
}
PlanExpr::IntWord(t, w) => tot_w(mul_ok, t) && u64::from(*w) + 2 < lim,
PlanExpr::IntCmp(..) => false,
PlanExpr::Let(_, v, body) => {
tot_e(mem, mul_ok, calls, lim, v) && tot_e(mem, mul_ok, calls, lim, body)
}
_ => false,
}
}
fn has_call(e: &PlanExpr) -> bool {
match e {
PlanExpr::BinOp(_, l, r) | PlanExpr::Let(_, l, r) => has_call(l) || has_call(r),
PlanExpr::Call(PlanCallee::Fn(_), _) | PlanExpr::TailCall(_, _) => true,
_ => false,
}
}
fn uses_mul(e: &PlanExpr) -> bool {
match e {
PlanExpr::BinOp(op, l, r) => *op == PlanBinOp::Mul || uses_mul(l) || uses_mul(r),
PlanExpr::Call(_, args) | PlanExpr::TailCall(_, args) => args.iter().any(uses_mul),
PlanExpr::If(c, t, el) => uses_mul(c) || uses_mul(t) || uses_mul(el),
PlanExpr::IntWord(t, _) => uses_mul_w(t),
PlanExpr::IntCmp(..) => false,
PlanExpr::Let(_, v, body) => uses_mul(v) || uses_mul(body),
_ => false,
}
}
fn tot_body(mem: &BTreeSet<u32>, mul_ok: bool, lim: u64, e: &PlanExpr) -> bool {
match e {
PlanExpr::If(c, base, step) => {
matches!(c.as_ref(), PlanExpr::BinOp(PlanBinOp::Lte, l, r)
if **l == PlanExpr::Local(0) && **r == PlanExpr::Literal(PlanLit::Int(0)))
&& tot_e(mem, mul_ok, false, lim, base)
&& tot_e(mem, mul_ok, true, lim, step)
&& has_call(step)
}
_ => false,
}
}
fn check_term_group(members: &[(u32, &FnPlan)]) -> Option<bool> {
let mem: BTreeSet<u32> = members.iter().map(|m| m.0).collect();
let mul = members.iter().any(|m| uses_mul(&m.1.body));
let ok = !members.is_empty()
&& members.iter().all(|(_, p)| {
let lim = (p.params.len() + p.locals.len()) as u64;
!p.params.is_empty()
&& p.params.iter().all(|t| *t == PlanTy::Int)
&& matches!(p.ret, PlanTy::Int | PlanTy::Bool)
&& tot_body(&mem, mul, lim, &p.body)
});
ok.then_some(mul)
}
fn facets_e(e: &PlanExpr, out: &mut BTreeSet<&'static str>) {
match e {
PlanExpr::Literal(PlanLit::Str(_)) => {
out.insert("strings");
}
PlanExpr::Literal(PlanLit::Float(_)) => {
out.insert("floats");
}
PlanExpr::Literal(_) | PlanExpr::Local(_) => {}
PlanExpr::Let(_, v, b) => {
facets_e(v, out);
facets_e(b, out);
}
PlanExpr::Call(PlanCallee::Fn(_), args) | PlanExpr::TailCall(_, args) => {
out.insert("calls");
args.iter().for_each(|a| facets_e(a, out));
}
PlanExpr::Call(_, args) | PlanExpr::List(_, args) => {
args.iter().for_each(|a| facets_e(a, out))
}
PlanExpr::BinOp(_, l, r) => {
facets_e(l, out);
facets_e(r, out);
}
PlanExpr::Neg(x) | PlanExpr::Try(x, _) | PlanExpr::Scope(x) => facets_e(x, out),
PlanExpr::IntWord(..) | PlanExpr::IntCmp(..) => {}
PlanExpr::If(c, t, el) => {
facets_e(c, out);
facets_e(t, out);
facets_e(el, out);
}
PlanExpr::RecordCreate(_, fs) => {
out.insert("records");
fs.iter().for_each(|a| facets_e(a, out));
}
PlanExpr::Project(_, _, b) => {
out.insert("records");
facets_e(b, out);
}
PlanExpr::Match(s, arms) => {
facets_e(s, out);
for (p, b) in arms {
match p {
PlanPat::Ctor(..) => {
out.insert("variants");
}
PlanPat::LitStr(_) => {
out.insert("strings");
}
PlanPat::Tuple(_) => {
out.insert("records");
}
_ => {}
}
facets_e(b, out);
}
}
PlanExpr::Construct(_, _, args) => {
out.insert("variants");
args.iter().for_each(|a| facets_e(a, out));
}
PlanExpr::Interp(parts) => {
out.insert("strings");
parts.iter().for_each(|a| facets_e(a, out));
}
}
}
#[derive(Clone, Debug, PartialEq)]
enum HI {
B(BI),
I64Add,
Block(Vec<HI>),
Loop(Vec<HI>),
Br(u32),
BrIf(u32),
IfThen(Vec<HI>),
IfElseI64(Vec<HI>, Vec<HI>),
Ret,
I32Add,
I32Sub,
WrapI64,
ExtU,
I64LtU,
Unreachable,
IfElseI32(Vec<HI>, Vec<HI>),
NewBytes(u64),
GetU(u64),
SetAt(u32, u64, Vec<HI>),
CopyTo(u32, u64, Vec<HI>),
IfElseRef(u64, Vec<HI>, Vec<HI>),
NewFill(u64),
I64Sub,
I64DivU,
I64RemU,
Dead(Vec<HI>),
RawOp(Vec<u8>),
}
enum HLocal {
I64,
I32,
Ref(u64),
Val(PlanTy),
}
struct HCode {
locals: Vec<HLocal>,
body: Vec<HI>,
}
fn h_op(i: WI) -> HI {
HI::B(BI::Op(i))
}
fn h_lg(i: u32) -> HI {
h_op(WI::LocalGet(i))
}
fn h_ls(i: u32) -> HI {
h_op(WI::LocalSet(i))
}
fn len_code(l: u64) -> HCode {
let body = vec![
h_lg(1),
h_op(WI::RefIsNull),
HI::BrIf(1),
h_lg(2),
h_op(WI::I64Const(1)),
HI::I64Add,
h_ls(2),
h_lg(1),
h_op(WI::StructGet(l, 1)),
h_ls(1),
HI::Br(0),
];
HCode {
locals: vec![HLocal::Ref(l), HLocal::I64],
body: vec![
h_lg(0),
h_ls(1),
h_op(WI::I64Const(0)),
h_ls(2),
HI::Block(vec![HI::Loop(body)]),
h_lg(2),
],
}
}
fn rev_code(l: u64, t: &PlanTy) -> HCode {
let body = vec![
h_lg(1),
h_op(WI::RefIsNull),
HI::BrIf(1),
h_lg(1),
h_op(WI::StructGet(l, 0)),
h_ls(3),
h_lg(3),
h_lg(2),
h_op(WI::StructNew(l)),
h_ls(2),
h_lg(1),
h_op(WI::StructGet(l, 1)),
h_ls(1),
HI::Br(0),
];
HCode {
locals: vec![HLocal::Ref(l), HLocal::Ref(l), HLocal::Val(t.clone())],
body: vec![
h_lg(0),
h_ls(1),
HI::B(BI::NullOf(l)),
h_ls(2),
HI::Block(vec![HI::Loop(body)]),
h_lg(2),
],
}
}
fn cat_code(l: u64, r: u64) -> HCode {
let body = vec![
h_lg(2),
h_op(WI::RefIsNull),
HI::BrIf(1),
h_lg(2),
h_op(WI::StructGet(l, 0)),
h_lg(3),
h_op(WI::StructNew(l)),
h_ls(3),
h_lg(2),
h_op(WI::StructGet(l, 1)),
h_ls(2),
HI::Br(0),
];
HCode {
locals: vec![HLocal::Ref(l), HLocal::Ref(l)],
body: vec![
h_lg(0),
h_op(WI::Call(r)),
h_ls(2),
h_lg(1),
h_ls(3),
HI::Block(vec![HI::Loop(body)]),
h_lg(3),
],
}
}
fn take_code(l: u64, r: u64) -> HCode {
let body = vec![
h_lg(4),
h_lg(1),
h_op(WI::I64GeS),
HI::BrIf(1),
h_lg(2),
h_op(WI::RefIsNull),
HI::BrIf(1),
h_lg(2),
h_op(WI::StructGet(l, 0)),
h_lg(3),
h_op(WI::StructNew(l)),
h_ls(3),
h_lg(4),
h_op(WI::I64Const(1)),
HI::I64Add,
h_ls(4),
h_lg(2),
h_op(WI::StructGet(l, 1)),
h_ls(2),
HI::Br(0),
];
HCode {
locals: vec![HLocal::Ref(l), HLocal::Ref(l), HLocal::I64],
body: vec![
h_lg(0),
h_ls(2),
HI::B(BI::NullOf(l)),
h_ls(3),
h_op(WI::I64Const(0)),
h_ls(4),
HI::Block(vec![HI::Loop(body)]),
h_lg(3),
h_op(WI::Call(r)),
],
}
}
fn drop_code(l: u64) -> HCode {
let body = vec![
h_lg(3),
h_lg(1),
h_op(WI::I64GeS),
HI::BrIf(1),
h_lg(2),
h_op(WI::RefIsNull),
HI::BrIf(1),
h_lg(2),
h_op(WI::StructGet(l, 1)),
h_ls(2),
h_lg(3),
h_op(WI::I64Const(1)),
HI::I64Add,
h_ls(3),
HI::Br(0),
];
HCode {
locals: vec![HLocal::Ref(l), HLocal::I64],
body: vec![
h_lg(0),
h_ls(2),
h_op(WI::I64Const(0)),
h_ls(3),
HI::Block(vec![HI::Loop(body)]),
h_lg(2),
],
}
}
fn has_code(l: u64, eq: WI) -> HCode {
let body = vec![
h_lg(2),
h_op(WI::RefIsNull),
HI::BrIf(1),
h_lg(2),
h_op(WI::StructGet(l, 0)),
h_lg(1),
h_op(eq),
HI::IfThen(vec![h_op(WI::I32Const(1)), HI::Ret]),
h_lg(2),
h_op(WI::StructGet(l, 1)),
h_ls(2),
HI::Br(0),
];
HCode {
locals: vec![HLocal::Ref(l)],
body: vec![
h_lg(0),
h_ls(2),
HI::Block(vec![HI::Loop(body)]),
h_op(WI::I32Const(0)),
],
}
}
fn sat_code(c: u64) -> HCode {
HCode {
locals: vec![],
body: vec![
h_lg(0),
h_op(WI::StructGet(c, 1)),
h_op(WI::RefIsNull),
HI::IfElseI64(
vec![h_lg(0), h_op(WI::StructGet(c, 0))],
vec![
h_lg(0),
h_op(WI::StructGet(c, 2)),
h_op(WI::I32Const(0)),
h_op(WI::I32GtS),
HI::IfElseI64(
vec![h_op(WI::I64Const(i64::MAX))],
vec![h_op(WI::I64Const(i64::MIN))],
),
],
),
],
}
}
impl MCtx<'_> {
fn list_helper(&self, r: PlanListRole, t: &PlanTy) -> Option<u32> {
self.tt
.list_helpers
.iter()
.find(|x| &x.0 == t && x.1 == r)
.map(|x| x.2)
}
fn has_eq(&self, t: &PlanTy) -> Option<WI> {
match t {
PlanTy::Int => Some(WI::Call(self.eq)),
PlanTy::Str => Some(WI::Call(self.streq)),
PlanTy::Bool => Some(WI::I32Eq),
_ => None,
}
}
fn helper_code(&self, r: PlanListRole, t: &PlanTy) -> Option<HCode> {
let l = self.list_struct(t);
let rev = || self.list_helper(PlanListRole::Reverse, t).map(u64::from);
Some(match r {
PlanListRole::Len => len_code(l),
PlanListRole::Reverse => rev_code(l, t),
PlanListRole::Concat => cat_code(l, rev()?),
PlanListRole::Take => take_code(l, rev()?),
PlanListRole::Drop => drop_code(l),
PlanListRole::Contains => has_code(l, self.has_eq(t)?),
})
}
fn helper_inner_calls(&self, r: PlanListRole, t: &PlanTy) -> Vec<u64> {
match (r, t) {
(PlanListRole::Contains, PlanTy::Int) => vec![self.eq],
(PlanListRole::Contains, PlanTy::Str) => vec![self.streq],
_ => vec![],
}
}
fn helper_sig(&self, r: PlanListRole, t: &PlanTy) -> Option<(Vec<ValT>, Vec<ValT>)> {
let rn = |i: u64| u32::try_from(i).ok().map(ValT::RefNull);
let l = rn(self.list_struct(t))?;
Some(match r {
PlanListRole::Len => (vec![l], vec![ValT::I64]),
PlanListRole::Reverse => (vec![l], vec![l]),
PlanListRole::Concat => (vec![l, l], vec![l]),
PlanListRole::Take | PlanListRole::Drop => (vec![l, ValT::I64], vec![l]),
PlanListRole::Contains => {
let e = match t {
PlanTy::Int => rn(self.carrier)?,
PlanTy::Str => rn(self.str_)?,
PlanTy::Bool => ValT::I32,
_ => return None,
};
(vec![l, e], vec![ValT::I32])
}
})
}
fn enc_h(&self, hs: &[HI], out: &mut Vec<u8>) -> Option<()> {
for h in hs {
match h {
HI::B(b) => self.enc(std::slice::from_ref(b), out)?,
HI::I64Add => out.push(0x7c),
HI::Block(b) => {
out.extend([0x02, 0x40]);
self.enc_h(b, out)?;
out.push(0x0b);
}
HI::Loop(b) => {
out.extend([0x03, 0x40]);
self.enc_h(b, out)?;
out.push(0x0b);
}
HI::Br(d) => {
out.push(0x0c);
uleb(u64::from(*d), out)?
}
HI::BrIf(d) => {
out.push(0x0d);
uleb(u64::from(*d), out)?
}
HI::IfThen(b) => {
out.extend([0x04, 0x40]);
self.enc_h(b, out)?;
out.push(0x0b);
}
HI::IfElseI64(t, e) => {
out.extend([0x04, 0x7e]);
self.enc_h(t, out)?;
out.push(0x05);
self.enc_h(e, out)?;
out.push(0x0b);
}
HI::Ret => out.push(0x0f),
HI::I32Add => out.push(0x6a),
HI::I32Sub => out.push(0x6b),
HI::WrapI64 => out.push(0xa7),
HI::ExtU => out.push(0xad),
HI::I64LtU => out.push(0x54),
HI::Unreachable => out.push(0x00),
HI::IfElseI32(t, e) => {
out.extend([0x04, 0x7f]);
self.enc_h(t, out)?;
out.push(0x05);
self.enc_h(e, out)?;
out.push(0x0b);
}
HI::NewBytes(ty) => {
out.extend([0xfb, 0x07]);
uleb(*ty, out)?
}
HI::GetU(ty) => {
out.extend([0xfb, 0x0d]);
uleb(*ty, out)?
}
HI::SetAt(k, ty, args) => {
out.push(0x20);
uleb(u64::from(*k), out)?;
self.enc_h(args, out)?;
out.extend([0xfb, 0x0e]);
uleb(*ty, out)?
}
HI::CopyTo(k, ty, args) => {
out.push(0x20);
uleb(u64::from(*k), out)?;
self.enc_h(args, out)?;
out.extend([0xfb, 0x11]);
uleb(*ty, out)?;
uleb(*ty, out)?
}
HI::IfElseRef(ht, t, e) => {
out.extend([0x04, 0x63]);
s33(*ht, out)?;
self.enc_h(t, out)?;
out.push(0x05);
self.enc_h(e, out)?;
out.push(0x0b);
}
HI::NewFill(ty) => {
out.extend([0xfb, 0x06]);
uleb(*ty, out)?
}
HI::I64Sub => out.push(0x7d),
HI::I64DivU => out.push(0x80),
HI::I64RemU => out.push(0x82),
HI::Dead(b) => self.enc_h(b, out)?,
HI::RawOp(b) => out.extend(b),
}
}
Some(())
}
fn h_local(&self, t: &HLocal, out: &mut Vec<u8>) -> Option<()> {
match t {
HLocal::I64 => out.push(0x7e),
HLocal::I32 => out.push(0x7f),
HLocal::Ref(ht) => {
out.push(0x63);
s33(*ht, out)?
}
HLocal::Val(t) => self.val_ty(t, out)?,
}
Some(())
}
fn h_entry_bytes(&self, c: &HCode) -> Option<Vec<u8>> {
let mut entry = Vec::new();
uleb(c.locals.len() as u64, &mut entry)?;
for t in &c.locals {
entry.push(0x01);
self.h_local(t, &mut entry)?;
}
self.enc_h(&c.body, &mut entry)?;
entry.push(0x0b);
let mut out = Vec::new();
uleb(entry.len() as u64, &mut out)?;
out.extend(entry);
Some(out)
}
fn helper_entry_bytes(&self, r: PlanListRole, t: &PlanTy) -> Option<Vec<u8>> {
self.h_entry_bytes(&self.helper_code(r, t)?)
}
fn sat_entry_bytes(&self) -> Option<Vec<u8>> {
self.h_entry_bytes(&sat_code(self.carrier))
}
fn helper_call(&self, r: PlanListRole, t: &PlanTy) -> Vec<BI> {
match self.list_helper(r, t) {
Some(f) => vec![BI::Op(WI::Call(u64::from(f)))],
None => vec![],
}
}
}
struct BCode {
groups: Vec<(u32, HLocal)>,
body: Vec<HI>,
}
fn h_i32c(k: i64) -> HI {
h_op(WI::I32Const(k))
}
fn pack_code(l: u64, b: u64, chk: u64) -> BCode {
let count = vec![
h_lg(1),
h_op(WI::RefIsNull),
HI::BrIf(1),
h_lg(2),
h_i32c(1),
HI::I32Add,
h_ls(2),
h_lg(1),
h_op(WI::StructGet(l, 1)),
h_ls(1),
HI::Br(0),
];
let fill = vec![
h_lg(1),
h_op(WI::RefIsNull),
HI::BrIf(1),
HI::SetAt(
3,
b,
vec![
h_lg(4),
h_lg(1),
h_op(WI::StructGet(l, 0)),
h_op(WI::Call(chk)),
HI::WrapI64,
],
),
h_lg(4),
h_i32c(1),
HI::I32Add,
h_ls(4),
h_lg(1),
h_op(WI::StructGet(l, 1)),
h_ls(1),
HI::Br(0),
];
BCode {
groups: vec![
(1, HLocal::Ref(l)),
(1, HLocal::I32),
(1, HLocal::Ref(b)),
(1, HLocal::I32),
],
body: vec![
h_lg(0),
h_ls(1),
h_i32c(0),
h_ls(2),
HI::Block(vec![HI::Loop(count)]),
h_lg(2),
HI::NewBytes(b),
h_ls(3),
h_lg(0),
h_ls(1),
h_i32c(0),
h_ls(4),
HI::Block(vec![HI::Loop(fill)]),
h_lg(3),
],
}
}
fn unpack_code(l: u64, b: u64, box_: u64) -> BCode {
let body = vec![
h_lg(2),
h_op(WI::I32Eqz),
HI::BrIf(1),
h_lg(2),
h_i32c(1),
HI::I32Sub,
h_ls(2),
h_lg(0),
h_lg(2),
HI::GetU(b),
HI::ExtU,
h_op(WI::Call(box_)),
h_lg(1),
h_op(WI::StructNew(l)),
h_ls(1),
HI::Br(0),
];
BCode {
groups: vec![(1, HLocal::Ref(l)), (1, HLocal::I32)],
body: vec![
HI::B(BI::NullOf(l)),
h_ls(1),
h_lg(0),
h_op(WI::ArrayLen),
h_ls(2),
HI::Block(vec![HI::Loop(body)]),
h_lg(1),
],
}
}
fn bytes_cat_code(b: u64) -> BCode {
BCode {
groups: vec![(2, HLocal::I32), (1, HLocal::Ref(b))],
body: vec![
h_lg(0),
h_op(WI::ArrayLen),
h_ls(2),
h_lg(1),
h_op(WI::ArrayLen),
h_ls(3),
h_lg(2),
h_lg(3),
HI::I32Add,
HI::NewBytes(b),
h_ls(4),
HI::CopyTo(4, b, vec![h_i32c(0), h_lg(0), h_i32c(0), h_lg(2)]),
HI::CopyTo(4, b, vec![h_lg(2), h_lg(1), h_i32c(0), h_lg(3)]),
h_lg(4),
],
}
}
fn bytes_clamp() -> Vec<HI> {
vec![
h_lg(1),
h_op(WI::I64Const(0)),
h_op(WI::I64GtS),
HI::IfThen(vec![
h_lg(1),
h_lg(2),
HI::ExtU,
HI::I64LtU,
HI::IfElseI32(vec![h_lg(1), HI::WrapI64], vec![h_lg(2)]),
h_ls(3),
]),
]
}
fn bytes_take_code(b: u64) -> BCode {
let mut body = vec![h_lg(0), h_op(WI::ArrayLen), h_ls(2), h_i32c(0), h_ls(3)];
body.extend(bytes_clamp());
body.extend([
h_lg(3),
HI::NewBytes(b),
h_ls(4),
HI::CopyTo(4, b, vec![h_i32c(0), h_lg(0), h_i32c(0), h_lg(3)]),
h_lg(4),
]);
BCode {
groups: vec![(2, HLocal::I32), (1, HLocal::Ref(b))],
body,
}
}
fn bytes_drop_code(b: u64) -> BCode {
let mut body = vec![h_lg(0), h_op(WI::ArrayLen), h_ls(2), h_i32c(0), h_ls(3)];
body.extend(bytes_clamp());
body.extend([
h_lg(2),
h_lg(3),
HI::I32Sub,
h_ls(4),
h_lg(4),
HI::NewBytes(b),
h_ls(5),
HI::CopyTo(5, b, vec![h_i32c(0), h_lg(0), h_lg(3), h_lg(4)]),
h_lg(5),
]);
BCode {
groups: vec![(3, HLocal::I32), (1, HLocal::Ref(b))],
body,
}
}
fn chk_code(c: u64) -> BCode {
BCode {
groups: vec![],
body: vec![
h_lg(0),
h_op(WI::StructGet(c, 1)),
h_op(WI::RefIsNull),
HI::IfElseI64(
vec![h_lg(0), h_op(WI::StructGet(c, 0))],
vec![HI::Unreachable],
),
],
}
}
fn from_int_count() -> Vec<HI> {
vec![
h_lg(3),
h_op(WI::I64Eqz),
HI::BrIf(1),
h_lg(4),
h_i32c(1),
HI::I32Add,
h_ls(4),
h_lg(3),
h_op(WI::I64Const(10)),
HI::I64DivU,
h_ls(3),
HI::Br(0),
]
}
fn from_int_fill(s: u64) -> Vec<HI> {
vec![
h_lg(6),
h_lg(7),
h_op(WI::I32LtS),
HI::BrIf(1),
HI::SetAt(
8,
s,
vec![
h_lg(6),
h_i32c(48),
h_lg(3),
h_op(WI::I64Const(10)),
HI::I64RemU,
HI::WrapI64,
HI::I32Add,
],
),
h_lg(3),
h_op(WI::I64Const(10)),
HI::I64DivU,
h_ls(3),
h_lg(6),
h_i32c(1),
HI::I32Sub,
h_ls(6),
HI::Br(0),
]
}
fn from_int_nonzero(s: u64) -> Vec<HI> {
vec![
h_lg(1),
h_op(WI::I64Const(0)),
h_op(WI::I64LtS),
HI::IfElseI32(vec![h_i32c(1)], vec![h_i32c(0)]),
h_ls(7),
h_lg(7),
HI::IfElseI64(
vec![h_op(WI::I64Const(0)), h_lg(1), HI::I64Sub],
vec![h_lg(1)],
),
h_ls(2),
h_lg(2),
h_ls(3),
h_i32c(0),
h_ls(4),
HI::Block(vec![HI::Loop(from_int_count())]),
h_lg(4),
h_lg(7),
HI::I32Add,
h_ls(5),
h_lg(5),
HI::NewBytes(s),
h_ls(8),
h_lg(5),
h_i32c(1),
HI::I32Sub,
h_ls(6),
h_lg(2),
h_ls(3),
HI::Block(vec![HI::Loop(from_int_fill(s))]),
h_lg(7),
HI::IfThen(vec![HI::SetAt(8, s, vec![h_i32c(0), h_i32c(45)])]),
h_lg(8),
]
}
fn from_int_big(c: u64, g: u64, s: u64) -> Vec<HI> {
let ge_u = || HI::RawOp(vec![0x4f]);
let aget = || h_op(WI::ArrayGet(g));
vec![
h_lg(0),
h_op(WI::StructGet(c, 2)),
h_i32c(0),
h_op(WI::I32LtS),
HI::IfElseI32(vec![h_i32c(1)], vec![h_i32c(0)]),
h_ls(7),
h_lg(0),
h_op(WI::StructGet(c, 1)),
h_op(WI::ArrayLen),
h_ls(10),
h_lg(10),
HI::NewBytes(g),
h_ls(9),
h_i32c(0),
h_ls(11),
HI::Block(vec![HI::Loop(vec![
h_lg(11),
h_lg(10),
ge_u(),
HI::BrIf(1),
HI::SetAt(
9,
g,
vec![h_lg(11), h_lg(0), h_op(WI::StructGet(c, 1)), h_lg(11), aget()],
),
h_lg(11),
h_i32c(1),
HI::I32Add,
h_ls(11),
HI::Br(0),
])]),
h_lg(10),
h_i32c(10),
HI::RawOp(vec![0x6c]),
HI::NewBytes(s),
h_ls(16),
h_i32c(0),
h_ls(17),
HI::Block(vec![HI::Loop(vec![
h_op(WI::I64Const(0)),
h_ls(13),
h_lg(10),
h_ls(11),
HI::Block(vec![HI::Loop(vec![
h_lg(11),
h_op(WI::I32Eqz),
HI::BrIf(1),
h_lg(11),
h_i32c(1),
HI::I32Sub,
h_ls(11),
h_lg(13),
h_op(WI::I64Const(32)),
HI::RawOp(vec![0x86]),
h_lg(9),
h_lg(11),
aget(),
h_op(WI::I64Const(4_294_967_295)),
HI::RawOp(vec![0x83]),
HI::RawOp(vec![0x84]),
h_ls(12),
h_lg(12),
h_op(WI::I64Const(10)),
HI::I64DivU,
h_ls(14),
h_lg(12),
h_op(WI::I64Const(10)),
HI::I64RemU,
h_ls(13),
HI::SetAt(9, g, vec![h_lg(11), h_lg(14)]),
HI::Br(0),
])]),
HI::SetAt(
16,
s,
vec![h_lg(17), h_i32c(48), h_lg(13), HI::WrapI64, HI::I32Add],
),
h_lg(17),
h_i32c(1),
HI::I32Add,
h_ls(17),
h_i32c(1),
h_ls(15),
h_i32c(0),
h_ls(11),
HI::Block(vec![HI::Loop(vec![
h_lg(11),
h_lg(10),
ge_u(),
HI::BrIf(1),
h_lg(9),
h_lg(11),
aget(),
h_op(WI::I64Const(0)),
h_op(WI::I64Ne),
HI::IfThen(vec![h_i32c(0), h_ls(15), HI::Br(2)]),
h_lg(11),
h_i32c(1),
HI::I32Add,
h_ls(11),
HI::Br(0),
])]),
h_lg(15),
HI::BrIf(1),
HI::Br(0),
])]),
h_lg(17),
h_lg(7),
HI::I32Add,
h_ls(5),
h_lg(5),
HI::NewBytes(s),
h_ls(8),
h_lg(7),
HI::IfThen(vec![HI::SetAt(8, s, vec![h_i32c(0), h_i32c(45)])]),
h_i32c(0),
h_ls(6),
HI::Block(vec![HI::Loop(vec![
h_lg(6),
h_lg(17),
ge_u(),
HI::BrIf(1),
HI::SetAt(
8,
s,
vec![
h_lg(7),
h_lg(6),
HI::I32Add,
h_lg(16),
h_lg(17),
h_i32c(1),
HI::I32Sub,
h_lg(6),
HI::I32Sub,
HI::GetU(s),
],
),
h_lg(6),
h_i32c(1),
HI::I32Add,
h_ls(6),
HI::Br(0),
])]),
h_lg(8),
]
}
fn from_int_code(c: u64, g: u64, s: u64) -> BCode {
let small = vec![
h_lg(0),
h_op(WI::StructGet(c, 0)),
h_ls(1),
h_lg(1),
h_op(WI::I64Eqz),
HI::IfElseRef(
s,
vec![h_i32c(48), h_i32c(1), HI::NewFill(s)],
from_int_nonzero(s),
),
];
BCode {
groups: vec![
(3, HLocal::I64),
(4, HLocal::I32),
(1, HLocal::Ref(s)),
(1, HLocal::Ref(g)),
(2, HLocal::I32),
(3, HLocal::I64),
(1, HLocal::I32),
(1, HLocal::Ref(s)),
(1, HLocal::I32),
],
body: vec![
h_lg(0),
h_op(WI::StructGet(c, 1)),
h_op(WI::RefIsNull),
HI::IfElseRef(s, small, vec![HI::Dead(from_int_big(c, g, s))]),
],
}
}
impl MCtx<'_> {
fn int_formatter_entry_bytes(&self) -> Option<Vec<u8>> {
self.b_entry_bytes(&from_int_code(self.carrier, self.mag, self.str_))
}
}
impl MCtx<'_> {
fn bytes_helper(&self, r: PlanBytesRole) -> Option<u32> {
self.tt
.bytes_helpers
.iter()
.find(|x| x.0 == r)
.map(|x| x.1)
}
fn bytes_call(&self, r: PlanBytesRole) -> Vec<BI> {
match self.bytes_helper(r) {
Some(f) => vec![BI::Op(WI::Call(u64::from(f)))],
None => vec![],
}
}
fn bytes_code(&self, r: PlanBytesRole) -> BCode {
let l = self.list_struct(&PlanTy::Int);
let b = self.bytes_arr;
match r {
PlanBytesRole::Pack => pack_code(l, b, self.to_i64_chk),
PlanBytesRole::Unpack => unpack_code(l, b, self.box_),
PlanBytesRole::Concat => bytes_cat_code(b),
PlanBytesRole::Take => bytes_take_code(b),
PlanBytesRole::Drop => bytes_drop_code(b),
}
}
fn bytes_inner_calls(&self, r: PlanBytesRole) -> Vec<u64> {
match r {
PlanBytesRole::Unpack => vec![self.box_],
_ => vec![],
}
}
fn bytes_sig(&self, r: PlanBytesRole) -> Option<(Vec<ValT>, Vec<ValT>)> {
let rn = |i: u64| u32::try_from(i).ok().map(ValT::RefNull);
let b = rn(self.bytes_arr)?;
let l = rn(self.list_struct(&PlanTy::Int))?;
Some(match r {
PlanBytesRole::Pack => (vec![l], vec![b]),
PlanBytesRole::Unpack => (vec![b], vec![l]),
PlanBytesRole::Concat => (vec![b, b], vec![b]),
PlanBytesRole::Take | PlanBytesRole::Drop => (vec![b, ValT::I64], vec![b]),
})
}
fn b_entry_bytes(&self, c: &BCode) -> Option<Vec<u8>> {
let mut entry = Vec::new();
uleb(c.groups.len() as u64, &mut entry)?;
for (n, t) in &c.groups {
uleb(u64::from(*n), &mut entry)?;
self.h_local(t, &mut entry)?;
}
self.enc_h(&c.body, &mut entry)?;
entry.push(0x0b);
let mut out = Vec::new();
uleb(entry.len() as u64, &mut out)?;
out.extend(entry);
Some(out)
}
fn bytes_entry_bytes(&self, r: PlanBytesRole) -> Option<Vec<u8>> {
self.b_entry_bytes(&self.bytes_code(r))
}
fn chk_entry_bytes(&self) -> Option<Vec<u8>> {
self.b_entry_bytes(&chk_code(self.carrier))
}
}