use alloc::boxed::Box;
use alloc::vec::Vec;
use core::fmt;
use hir_lang::{CaptureMode, ExpnKind, Op, OpKind, Prim};
pub(crate) const NONE: u32 = u32::MAX;
pub const MAX_TEMPLATE_SIZE: u32 = 1 << 20;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct TemplateId(pub(crate) u32);
impl TemplateId {
#[must_use]
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum HoleKind {
Expr,
Pat,
Ty,
Stmts,
Args,
Label,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum TLit {
Int(i64),
Float(f64),
Bool(bool),
Null,
Char(char),
}
macro_rules! handle {
($(#[$m:meta])* $name:ident, $int:ty) => {
$(#[$m])*
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct $name(pub(crate) $int);
};
}
handle!(
TExpr,
u32
);
handle!(
TPat,
u32
);
handle!(
TTy,
u32
);
handle!(
TStmt,
u32
);
handle!(
TBinder,
u16
);
handle!(
TLabel,
u16
);
handle!(
ExprHole,
u16
);
handle!(
PatHole,
u16
);
handle!(
TyHole,
u16
);
handle!(
StmtsHole,
u16
);
handle!(
ArgsHole,
u16
);
handle!(
LabelHole,
u16
);
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum LabelRef {
Own(TLabel),
Hole(LabelHole),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum TArg {
Expr(TExpr),
Pat(TPat),
Ty(TTy),
Stmts(StmtsHole),
Args(ArgsHole),
Label(LabelRef),
Absent,
}
impl TArg {
pub(crate) const fn kind(self) -> Option<HoleKind> {
match self {
Self::Expr(_) => Some(HoleKind::Expr),
Self::Pat(_) => Some(HoleKind::Pat),
Self::Ty(_) => Some(HoleKind::Ty),
Self::Stmts(_) => Some(HoleKind::Stmts),
Self::Args(_) => Some(HoleKind::Args),
Self::Label(_) => Some(HoleKind::Label),
Self::Absent => None,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) enum LabelSlot {
None,
Own(u16),
Hole(u16),
}
impl LabelSlot {
fn of(label: Option<LabelRef>) -> Self {
match label {
None => Self::None,
Some(LabelRef::Own(l)) => Self::Own(l.0),
Some(LabelRef::Hole(h)) => Self::Hole(h.0),
}
}
}
pub(crate) type TList = (u32, u32);
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) enum TNode {
Hole(u16),
Splice(u16),
Lit(TLit),
Str(u32),
Var(u16),
Global(u32),
Extern(u32),
Call {
callee: u32,
args: TList,
},
Method {
recv: u32,
name: u32,
args: TList,
},
Field {
base: u32,
name: u32,
},
Index {
base: u32,
index: u32,
},
Op {
op: Op,
exact: bool,
args: TList,
},
Assign {
target: u32,
value: u32,
},
Block {
stmts: TList,
tail: u32,
label: LabelSlot,
},
If {
cond: u32,
then: u32,
else_: u32,
},
Match {
scrutinee: u32,
arms: TList,
},
Loop {
label: LabelSlot,
body: u32,
step: u32,
},
Break {
label: LabelSlot,
value: u32,
},
Continue {
label: LabelSlot,
},
Return(u32),
Throw(u32),
Await(u32),
Yield {
key: u32,
value: u32,
},
YieldFrom(u32),
Spawn(u32),
Tuple(TList),
Array(TList),
Closure {
params: TList,
body: u32,
implicit: Option<CaptureMode>,
},
Apply {
template: u32,
args: TList,
},
LetPlace {
binder: u16,
place: u32,
body: u32,
},
Let {
pat: u32,
ty: u32,
init: u32,
},
ExprStmt(u32),
Defer(u32),
Stmts(u16),
PHole(u16),
PWild,
PBind(u16),
PLit(TLit),
PTuple(TList),
PCtor {
path: u32,
elems: TList,
},
THole(u16),
TPrim(Prim),
TNamed(u32),
TInfer,
TAny,
TUnion(TList),
TInter(TList),
}
#[derive(Clone, Debug, PartialEq)]
pub(crate) struct HoleDecl {
pub(crate) name: Box<str>,
pub(crate) kind: HoleKind,
pub(crate) optional: bool,
pub(crate) default: Option<TLit>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct BinderDecl {
pub(crate) name: u32,
pub(crate) mutable: bool,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Template {
pub(crate) name: Box<str>,
pub(crate) kind: ExpnKind,
pub(crate) nodes: Vec<TNode>,
pub(crate) lists: Vec<u32>,
pub(crate) texts: Vec<Box<str>>,
pub(crate) holes: Vec<HoleDecl>,
pub(crate) binders: Vec<BinderDecl>,
pub(crate) labels: Vec<BinderDecl>,
pub(crate) args: Vec<TArg>,
pub(crate) applies: Vec<u32>,
pub(crate) root: u32,
pub(crate) text_base: u32,
}
impl Template {
#[must_use]
pub fn name(&self) -> &str {
&self.name
}
#[must_use]
pub const fn expansion_kind(&self) -> ExpnKind {
self.kind
}
#[must_use]
pub fn hole_count(&self) -> usize {
self.holes.len()
}
#[must_use]
pub fn hole(&self, index: usize) -> Option<(&str, HoleKind, bool)> {
self.holes
.get(index)
.map(|h| (&*h.name, h.kind, h.optional))
}
pub fn parse(name: &str, text: &str) -> Result<Self, TemplateError> {
crate::text::parse(name, text, None)
}
#[must_use]
pub fn desugar(mut self) -> Self {
self.kind = ExpnKind::Desugar;
self
}
#[must_use]
pub fn hole_index(&self, name: &str) -> Option<usize> {
self.holes.iter().position(|h| &*h.name == name)
}
pub(crate) fn node(&self, index: u32) -> Option<&TNode> {
self.nodes.get(index as usize)
}
pub(crate) fn list(&self, list: TList) -> &[u32] {
let (start, len) = (list.0 as usize, list.1 as usize);
self.lists
.get(start..start.saturating_add(len))
.unwrap_or(&[])
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum TemplateError {
HoleUnused {
hole: usize,
},
BinderUnbound {
binder: usize,
},
BinderBoundTwice {
binder: usize,
},
LabelUndefined {
label: usize,
},
LabelDefinedTwice {
label: usize,
},
SpliceOutOfList {
hole: usize,
},
ForeignHandle,
TooLarge,
Syntax {
at: hir_lang::Span,
error: crate::SyntaxError,
},
}
impl fmt::Display for TemplateError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::HoleUnused { hole } => write!(f, "hole {hole} is never used"),
Self::BinderUnbound { binder } => write!(f, "binder {binder} is used but never bound"),
Self::BinderBoundTwice { binder } => write!(f, "binder {binder} is bound twice"),
Self::LabelUndefined { label } => write!(f, "label {label} is used but never defined"),
Self::LabelDefinedTwice { label } => write!(f, "label {label} is defined twice"),
Self::SpliceOutOfList { hole } => {
write!(
f,
"argument hole {hole} is spliced outside an argument or element list"
)
}
Self::ForeignHandle => f.write_str("a handle from another template builder was used"),
Self::TooLarge => f.write_str("the template is too large"),
Self::Syntax { at, error } => write!(
f,
"template text, bytes {}..{}: {error}",
at.start().to_usize(),
at.end().to_usize()
),
}
}
}
impl core::error::Error for TemplateError {}
#[derive(Clone, Debug)]
pub struct TemplateBuilder {
pub(crate) t: Template,
overflow: bool,
}
impl TemplateBuilder {
#[must_use]
pub fn new(name: &str) -> Self {
Self {
t: Template {
name: name.into(),
kind: ExpnKind::Template,
nodes: Vec::new(),
lists: Vec::new(),
texts: Vec::new(),
holes: Vec::new(),
binders: Vec::new(),
labels: Vec::new(),
args: Vec::new(),
applies: Vec::new(),
root: NONE,
text_base: 0,
},
overflow: false,
}
}
#[must_use]
pub fn desugar(mut self) -> Self {
self.t.kind = ExpnKind::Desugar;
self
}
fn push(&mut self, node: TNode) -> u32 {
match u32::try_from(self.t.nodes.len()) {
Ok(i) if i < NONE => {
self.t.nodes.push(node);
i
}
_ => {
self.overflow = true;
NONE
}
}
}
fn list(&mut self, items: impl IntoIterator<Item = u32>) -> TList {
let start = self.t.lists.len();
self.t.lists.extend(items);
match (
u32::try_from(start),
u32::try_from(self.t.lists.len() - start),
) {
(Ok(s), Ok(l)) => (s, l),
_ => {
self.overflow = true;
(0, 0)
}
}
}
fn text(&mut self, text: &str) -> u32 {
let i = self.t.texts.len();
self.t.texts.push(text.into());
u32::try_from(i).unwrap_or_else(|_| {
self.overflow = true;
0
})
}
fn hole_decl(
&mut self,
name: &str,
kind: HoleKind,
optional: bool,
default: Option<TLit>,
) -> u16 {
let i = self.t.holes.len();
self.t.holes.push(HoleDecl {
name: name.into(),
kind,
optional,
default,
});
u16::try_from(i).unwrap_or_else(|_| {
self.overflow = true;
0
})
}
fn opt(e: Option<TExpr>) -> u32 {
e.map_or(NONE, |e| e.0)
}
pub fn expr_hole(&mut self, name: &str) -> ExprHole {
ExprHole(self.hole_decl(name, HoleKind::Expr, false, None))
}
pub fn optional_expr_hole(&mut self, name: &str, default: Option<TLit>) -> ExprHole {
ExprHole(self.hole_decl(name, HoleKind::Expr, true, default))
}
pub fn pat_hole(&mut self, name: &str, optional: bool) -> PatHole {
PatHole(self.hole_decl(name, HoleKind::Pat, optional, None))
}
pub fn ty_hole(&mut self, name: &str, optional: bool) -> TyHole {
TyHole(self.hole_decl(name, HoleKind::Ty, optional, None))
}
pub fn stmts_hole(&mut self, name: &str) -> StmtsHole {
StmtsHole(self.hole_decl(name, HoleKind::Stmts, true, None))
}
pub fn args_hole(&mut self, name: &str) -> ArgsHole {
ArgsHole(self.hole_decl(name, HoleKind::Args, true, None))
}
pub fn label_hole(&mut self, name: &str) -> LabelHole {
LabelHole(self.hole_decl(name, HoleKind::Label, true, None))
}
pub fn binder(&mut self, name: &str) -> TBinder {
self.binder_decl(name, false)
}
pub fn mutable_binder(&mut self, name: &str) -> TBinder {
self.binder_decl(name, true)
}
fn binder_decl(&mut self, name: &str, mutable: bool) -> TBinder {
let name = self.text(name);
let i = self.t.binders.len();
self.t.binders.push(BinderDecl { name, mutable });
TBinder(u16::try_from(i).unwrap_or_else(|_| {
self.overflow = true;
0
}))
}
pub fn label(&mut self, name: &str) -> TLabel {
let name = self.text(name);
let i = self.t.labels.len();
self.t.labels.push(BinderDecl {
name,
mutable: false,
});
TLabel(u16::try_from(i).unwrap_or_else(|_| {
self.overflow = true;
0
}))
}
pub fn hole(&mut self, hole: ExprHole) -> TExpr {
TExpr(self.push(TNode::Hole(hole.0)))
}
pub fn splice(&mut self, hole: ArgsHole) -> TExpr {
TExpr(self.push(TNode::Splice(hole.0)))
}
pub fn lit(&mut self, lit: TLit) -> TExpr {
TExpr(self.push(TNode::Lit(lit)))
}
pub fn str(&mut self, text: &str) -> TExpr {
let s = self.text(text);
TExpr(self.push(TNode::Str(s)))
}
pub fn var(&mut self, binder: TBinder) -> TExpr {
TExpr(self.push(TNode::Var(binder.0)))
}
pub fn global(&mut self, path: &str) -> TExpr {
let s = self.text(path);
TExpr(self.push(TNode::Global(s)))
}
pub fn extern_(&mut self, name: &str) -> TExpr {
let s = self.text(name);
TExpr(self.push(TNode::Extern(s)))
}
pub fn call(&mut self, callee: TExpr, args: &[TExpr]) -> TExpr {
let args = self.list(args.iter().map(|a| a.0));
TExpr(self.push(TNode::Call {
callee: callee.0,
args,
}))
}
pub fn method(&mut self, recv: TExpr, name: &str, args: &[TExpr]) -> TExpr {
let name = self.text(name);
let args = self.list(args.iter().map(|a| a.0));
TExpr(self.push(TNode::Method {
recv: recv.0,
name,
args,
}))
}
pub fn field(&mut self, base: TExpr, name: &str) -> TExpr {
let name = self.text(name);
TExpr(self.push(TNode::Field { base: base.0, name }))
}
pub fn index(&mut self, base: TExpr, index: TExpr) -> TExpr {
TExpr(self.push(TNode::Index {
base: base.0,
index: index.0,
}))
}
pub fn op(&mut self, kind: OpKind, args: &[TExpr]) -> TExpr {
let args = self.list(args.iter().map(|a| a.0));
TExpr(self.push(TNode::Op {
op: Op::new(kind),
exact: false,
args,
}))
}
pub fn op_with(&mut self, op: Op, args: &[TExpr]) -> TExpr {
let args = self.list(args.iter().map(|a| a.0));
TExpr(self.push(TNode::Op {
op,
exact: true,
args,
}))
}
pub fn assign(&mut self, target: TExpr, value: TExpr) -> TExpr {
TExpr(self.push(TNode::Assign {
target: target.0,
value: value.0,
}))
}
pub fn block(&mut self, stmts: &[TStmt], tail: Option<TExpr>) -> TExpr {
let stmts = self.list(stmts.iter().map(|s| s.0));
TExpr(self.push(TNode::Block {
stmts,
tail: Self::opt(tail),
label: LabelSlot::None,
}))
}
pub fn labeled_block(
&mut self,
label: LabelRef,
stmts: &[TStmt],
tail: Option<TExpr>,
) -> TExpr {
let stmts = self.list(stmts.iter().map(|s| s.0));
TExpr(self.push(TNode::Block {
stmts,
tail: Self::opt(tail),
label: LabelSlot::of(Some(label)),
}))
}
pub fn if_(&mut self, cond: TExpr, then: TExpr, else_: Option<TExpr>) -> TExpr {
TExpr(self.push(TNode::If {
cond: cond.0,
then: then.0,
else_: Self::opt(else_),
}))
}
pub fn match_(&mut self, scrutinee: TExpr, arms: &[(TPat, Option<TExpr>, TExpr)]) -> TExpr {
let arms = self.list(arms.iter().flat_map(|(p, g, b)| [p.0, Self::opt(*g), b.0]));
TExpr(self.push(TNode::Match {
scrutinee: scrutinee.0,
arms,
}))
}
pub fn loop_(&mut self, label: Option<LabelRef>, body: TExpr, step: Option<TExpr>) -> TExpr {
TExpr(self.push(TNode::Loop {
label: LabelSlot::of(label),
body: body.0,
step: Self::opt(step),
}))
}
pub fn break_(&mut self, label: Option<LabelRef>, value: Option<TExpr>) -> TExpr {
TExpr(self.push(TNode::Break {
label: LabelSlot::of(label),
value: Self::opt(value),
}))
}
pub fn continue_(&mut self, label: Option<LabelRef>) -> TExpr {
TExpr(self.push(TNode::Continue {
label: LabelSlot::of(label),
}))
}
pub fn return_(&mut self, value: Option<TExpr>) -> TExpr {
TExpr(self.push(TNode::Return(Self::opt(value))))
}
pub fn throw(&mut self, value: TExpr) -> TExpr {
TExpr(self.push(TNode::Throw(value.0)))
}
pub fn await_(&mut self, value: TExpr) -> TExpr {
TExpr(self.push(TNode::Await(value.0)))
}
pub fn yield_(&mut self, value: Option<TExpr>) -> TExpr {
TExpr(self.push(TNode::Yield {
key: NONE,
value: Self::opt(value),
}))
}
pub fn yield_kv(&mut self, key: TExpr, value: TExpr) -> TExpr {
TExpr(self.push(TNode::Yield {
key: key.0,
value: value.0,
}))
}
pub fn yield_from(&mut self, source: TExpr) -> TExpr {
TExpr(self.push(TNode::YieldFrom(source.0)))
}
pub fn spawn(&mut self, callable: TExpr) -> TExpr {
TExpr(self.push(TNode::Spawn(callable.0)))
}
pub fn tuple(&mut self, elems: &[TExpr]) -> TExpr {
let elems = self.list(elems.iter().map(|e| e.0));
TExpr(self.push(TNode::Tuple(elems)))
}
pub fn array(&mut self, elems: &[TExpr]) -> TExpr {
let elems = self.list(elems.iter().map(|e| e.0));
TExpr(self.push(TNode::Array(elems)))
}
pub fn closure(
&mut self,
params: &[TBinder],
body: TExpr,
implicit: Option<CaptureMode>,
) -> TExpr {
let params = self.list(params.iter().map(|p| u32::from(p.0)));
TExpr(self.push(TNode::Closure {
params,
body: body.0,
implicit,
}))
}
pub fn apply(&mut self, template: TemplateId, args: &[TArg]) -> TExpr {
let start = self.t.args.len();
self.t.args.extend_from_slice(args);
let list = match (u32::try_from(start), u32::try_from(args.len())) {
(Ok(s), Ok(l)) => (s, l),
_ => {
self.overflow = true;
(0, 0)
}
};
TExpr(self.push(TNode::Apply {
template: template.0,
args: list,
}))
}
pub fn let_place(&mut self, binder: TBinder, place: TExpr, body: TExpr) -> TExpr {
TExpr(self.push(TNode::LetPlace {
binder: binder.0,
place: place.0,
body: body.0,
}))
}
pub fn let_(&mut self, pat: TPat, ty: Option<TTy>, init: Option<TExpr>) -> TStmt {
TStmt(self.push(TNode::Let {
pat: pat.0,
ty: ty.map_or(NONE, |t| t.0),
init: Self::opt(init),
}))
}
pub fn expr_stmt(&mut self, expr: TExpr) -> TStmt {
TStmt(self.push(TNode::ExprStmt(expr.0)))
}
pub fn defer(&mut self, expr: TExpr) -> TStmt {
TStmt(self.push(TNode::Defer(expr.0)))
}
pub fn stmts(&mut self, hole: StmtsHole) -> TStmt {
TStmt(self.push(TNode::Stmts(hole.0)))
}
pub fn pat(&mut self, hole: PatHole) -> TPat {
TPat(self.push(TNode::PHole(hole.0)))
}
pub fn wild(&mut self) -> TPat {
TPat(self.push(TNode::PWild))
}
pub fn bind(&mut self, binder: TBinder) -> TPat {
TPat(self.push(TNode::PBind(binder.0)))
}
pub fn lit_pat(&mut self, lit: TLit) -> TPat {
TPat(self.push(TNode::PLit(lit)))
}
pub fn tuple_pat(&mut self, elems: &[TPat]) -> TPat {
let elems = self.list(elems.iter().map(|p| p.0));
TPat(self.push(TNode::PTuple(elems)))
}
pub fn ctor_pat(&mut self, path: &str, elems: &[TPat]) -> TPat {
let path = self.text(path);
let elems = self.list(elems.iter().map(|p| p.0));
TPat(self.push(TNode::PCtor { path, elems }))
}
pub fn ty(&mut self, hole: TyHole) -> TTy {
TTy(self.push(TNode::THole(hole.0)))
}
pub fn prim(&mut self, prim: Prim) -> TTy {
TTy(self.push(TNode::TPrim(prim)))
}
pub fn named_ty(&mut self, path: &str) -> TTy {
let path = self.text(path);
TTy(self.push(TNode::TNamed(path)))
}
pub fn infer_ty(&mut self) -> TTy {
TTy(self.push(TNode::TInfer))
}
pub fn any_ty(&mut self) -> TTy {
TTy(self.push(TNode::TAny))
}
pub fn union_ty(&mut self, members: &[TTy]) -> TTy {
let members = self.list(members.iter().map(|m| m.0));
TTy(self.push(TNode::TUnion(members)))
}
pub fn intersection_ty(&mut self, members: &[TTy]) -> TTy {
let members = self.list(members.iter().map(|m| m.0));
TTy(self.push(TNode::TInter(members)))
}
pub fn finish(mut self, root: TExpr) -> Result<Template, TemplateError> {
if self.overflow {
return Err(TemplateError::TooLarge);
}
self.t.root = root.0;
let applies = check(&self.t)?;
self.t.applies = applies;
Ok(self.t)
}
}
struct Counts {
hole_uses: Vec<u32>,
binder_sites: Vec<u32>,
binder_uses: Vec<u32>,
label_defs: Vec<u32>,
label_uses: Vec<u32>,
}
fn check(t: &Template) -> Result<Vec<u32>, TemplateError> {
let mut c = Counts {
hole_uses: alloc::vec![0; t.holes.len()],
binder_sites: alloc::vec![0; t.binders.len()],
binder_uses: alloc::vec![0; t.binders.len()],
label_defs: alloc::vec![0; t.labels.len()],
label_uses: alloc::vec![0; t.labels.len()],
};
let mut applies = Vec::new();
let mut stack: Vec<(u32, bool)> = alloc::vec![(t.root, false)];
let mut size: u32 = 0;
while let Some((n, in_list)) = stack.pop() {
if n == NONE {
continue;
}
size += 1;
if size > MAX_TEMPLATE_SIZE {
return Err(TemplateError::TooLarge);
}
let node = *t.node(n).ok_or(TemplateError::ForeignHandle)?;
let kids = |list: TList,
in_list: bool,
stack: &mut Vec<(u32, bool)>|
-> Result<(), TemplateError> {
let (start, len) = (list.0 as usize, list.1 as usize);
let slice = t
.lists
.get(start..start.saturating_add(len))
.ok_or(TemplateError::ForeignHandle)?;
stack.extend(slice.iter().map(|&k| (k, in_list)));
Ok(())
};
match node {
TNode::Hole(h) | TNode::PHole(h) | TNode::THole(h) | TNode::Stmts(h) => {
bump(&mut c.hole_uses, usize::from(h))?;
}
TNode::Splice(h) => {
if !in_list {
return Err(TemplateError::SpliceOutOfList {
hole: usize::from(h),
});
}
bump(&mut c.hole_uses, usize::from(h))?;
}
TNode::Var(b) => bump(&mut c.binder_uses, usize::from(b))?,
TNode::PBind(b) => bump(&mut c.binder_sites, usize::from(b))?,
TNode::Lit(_)
| TNode::Str(_)
| TNode::Global(_)
| TNode::Extern(_)
| TNode::PWild
| TNode::PLit(_)
| TNode::TPrim(_)
| TNode::TNamed(_)
| TNode::TInfer
| TNode::TAny => {}
TNode::Call { callee, args } => {
stack.push((callee, false));
kids(args, true, &mut stack)?;
}
TNode::Method { recv, args, .. } => {
stack.push((recv, false));
kids(args, true, &mut stack)?;
}
TNode::Field { base, .. } => stack.push((base, false)),
TNode::Index { base, index } => stack.extend([(base, false), (index, false)]),
TNode::Op { args, .. } => kids(args, false, &mut stack)?,
TNode::Assign { target, value } => stack.extend([(target, false), (value, false)]),
TNode::Block { stmts, tail, label } => {
define_label(&mut c, label)?;
kids(stmts, false, &mut stack)?;
stack.push((tail, false));
}
TNode::If { cond, then, else_ } => {
stack.extend([(cond, false), (then, false), (else_, false)]);
}
TNode::Match { scrutinee, arms } => {
stack.push((scrutinee, false));
kids(arms, false, &mut stack)?;
}
TNode::Loop { label, body, step } => {
define_label(&mut c, label)?;
stack.extend([(body, false), (step, false)]);
}
TNode::Break { label, value } => {
use_label(&mut c, label)?;
stack.push((value, false));
}
TNode::Continue { label } => use_label(&mut c, label)?,
TNode::Return(v)
| TNode::Throw(v)
| TNode::Await(v)
| TNode::YieldFrom(v)
| TNode::Spawn(v)
| TNode::ExprStmt(v)
| TNode::Defer(v) => stack.push((v, false)),
TNode::Yield { key, value } => stack.extend([(key, false), (value, false)]),
TNode::LetPlace {
binder,
place,
body,
} => {
bump(&mut c.binder_sites, usize::from(binder))?;
stack.extend([(place, false), (body, false)]);
}
TNode::TUnion(l) | TNode::TInter(l) => kids(l, false, &mut stack)?,
TNode::Tuple(l) | TNode::Array(l) => kids(l, true, &mut stack)?,
TNode::Closure { params, body, .. } => {
let (start, len) = (params.0 as usize, params.1 as usize);
let slice = t
.lists
.get(start..start.saturating_add(len))
.ok_or(TemplateError::ForeignHandle)?;
for &p in slice {
bump(&mut c.binder_sites, p as usize)?;
}
stack.push((body, false));
}
TNode::Apply { args, .. } => {
applies.push(n);
let (start, len) = (args.0 as usize, args.1 as usize);
let slice = t
.args
.get(start..start.saturating_add(len))
.ok_or(TemplateError::ForeignHandle)?;
for arg in slice {
match *arg {
TArg::Expr(e) => stack.push((e.0, false)),
TArg::Pat(p) => stack.push((p.0, false)),
TArg::Ty(ty) => stack.push((ty.0, false)),
TArg::Stmts(h) => bump(&mut c.hole_uses, usize::from(h.0))?,
TArg::Args(h) => bump(&mut c.hole_uses, usize::from(h.0))?,
TArg::Label(l) => use_label(&mut c, LabelSlot::of(Some(l)))?,
TArg::Absent => {}
}
}
}
TNode::Let { pat, ty, init } => {
stack.extend([(pat, false), (ty, false), (init, false)])
}
TNode::PTuple(l) => kids(l, false, &mut stack)?,
TNode::PCtor { elems, .. } => kids(elems, false, &mut stack)?,
}
}
for (i, &n) in c.hole_uses.iter().enumerate() {
if n == 0 {
return Err(TemplateError::HoleUnused { hole: i });
}
}
for (i, (&sites, &uses)) in c.binder_sites.iter().zip(&c.binder_uses).enumerate() {
if sites > 1 {
return Err(TemplateError::BinderBoundTwice { binder: i });
}
if sites == 0 && uses > 0 {
return Err(TemplateError::BinderUnbound { binder: i });
}
}
for (i, (&defs, &uses)) in c.label_defs.iter().zip(&c.label_uses).enumerate() {
if defs > 1 {
return Err(TemplateError::LabelDefinedTwice { label: i });
}
if defs == 0 && uses > 0 {
return Err(TemplateError::LabelUndefined { label: i });
}
}
Ok(applies)
}
fn bump(counts: &mut [u32], i: usize) -> Result<(), TemplateError> {
let slot = counts.get_mut(i).ok_or(TemplateError::ForeignHandle)?;
*slot = slot.saturating_add(1);
Ok(())
}
fn define_label(c: &mut Counts, label: LabelSlot) -> Result<(), TemplateError> {
match label {
LabelSlot::None => Ok(()),
LabelSlot::Own(l) => bump(&mut c.label_defs, usize::from(l)),
LabelSlot::Hole(h) => bump(&mut c.hole_uses, usize::from(h)),
}
}
fn use_label(c: &mut Counts, label: LabelSlot) -> Result<(), TemplateError> {
match label {
LabelSlot::None => Ok(()),
LabelSlot::Own(l) => bump(&mut c.label_uses, usize::from(l)),
LabelSlot::Hole(h) => bump(&mut c.hole_uses, usize::from(h)),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_shared_subtrees_count_at_every_use() {
let mut t = TemplateBuilder::new("blowup");
let mut e = t.lit(TLit::Int(1));
for _ in 0..40 {
e = t.tuple(&[e, e]);
}
assert_eq!(t.finish(e), Err(TemplateError::TooLarge));
}
#[test]
fn test_foreign_handles_are_refused() {
let mut t = TemplateBuilder::new("foreign");
let root = TExpr(99);
let _ = t.lit(TLit::Null);
assert_eq!(t.finish(root), Err(TemplateError::ForeignHandle));
}
#[test]
fn test_label_rules() {
let mut t = TemplateBuilder::new("labels");
let l = t.label("l");
let brk = t.break_(Some(LabelRef::Own(l)), None);
assert_eq!(
t.finish(brk),
Err(TemplateError::LabelUndefined { label: 0 })
);
let mut t = TemplateBuilder::new("labels");
let l = t.label("l");
let body = t.block(&[], None);
let a = t.loop_(Some(LabelRef::Own(l)), body, None);
let b = t.loop_(Some(LabelRef::Own(l)), body, None);
let root = t.tuple(&[a, b]);
assert_eq!(
t.finish(root),
Err(TemplateError::LabelDefinedTwice { label: 0 })
);
}
#[test]
fn test_splice_outside_a_list_is_refused() {
let mut t = TemplateBuilder::new("splice");
let args = t.args_hole("args");
let s = t.splice(args);
let root = t.op(OpKind::Not, &[s]);
assert_eq!(
t.finish(root),
Err(TemplateError::SpliceOutOfList { hole: 0 })
);
}
#[test]
fn test_binder_bound_twice() {
let mut t = TemplateBuilder::new("twice");
let x = t.binder("x");
let (p1, p2) = (t.bind(x), t.bind(x));
let pair = t.tuple_pat(&[p1, p2]);
let unit = t.tuple(&[]);
let s = t.let_(pair, None, Some(unit));
let root = t.block(&[s], None);
assert_eq!(
t.finish(root),
Err(TemplateError::BinderBoundTwice { binder: 0 })
);
}
}