use std::collections::{HashMap, HashSet};
use std::sync::Arc;
use crate::codegen::ir::{
LocalId, MirBlock, MirFunction, MirPlace, MirRValue, MirStmtKind, MirTerminator, MirValue,
PlaceProjection,
};
use crate::lexer::Span;
use crate::types::{TypeError, TypeErrorWithSpan};
use super::cfg::{block_id_index, reachable_blocks, terminator_successors};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum MoveState {
Init,
Moved,
}
type BlockState = HashMap<LocalId, MoveState>;
#[derive(Debug, Default, Clone)]
struct LinearContext {
borrow_escaping_params: HashMap<Arc<str>, HashSet<usize>>,
}
fn is_linear_local(func: &MirFunction, id: LocalId) -> bool {
func.locals
.iter()
.find(|l| l.id == id)
.is_some_and(|l| l.annotations.iter().any(|a| a.as_ref() == "linear"))
}
fn local_name(func: &MirFunction, id: LocalId) -> String {
func.locals
.iter()
.find(|l| l.id == id)
.and_then(|l| l.name.as_ref())
.map(|n| n.to_string())
.unwrap_or_else(|| format!("_{}", id.0))
}
fn shared_linear_ref_set(func: &MirFunction) -> HashSet<LocalId> {
let mut set = HashSet::new();
let Some(blocks) = &func.blocks else {
return set;
};
for block in blocks {
for stmt in &block.stmts {
if let MirStmtKind::Assign { dest, value } = &stmt.kind {
let place = match value {
MirRValue::Ref {
is_mut: false,
place,
}
| MirRValue::AddressOf {
is_mut: false,
place,
} => place,
_ => continue,
};
if place.projections.is_empty() && is_linear_local(func, place.local) {
set.insert(*dest);
}
}
}
}
let mut changed = true;
while changed {
changed = false;
for block in blocks {
for stmt in &block.stmts {
if let MirStmtKind::Assign { dest, value } = &stmt.kind {
let src = match value {
MirRValue::Use(MirValue::Local(s))
| MirRValue::Cast {
value: MirValue::Local(s),
..
} => *s,
_ => continue,
};
if set.contains(&src) && set.insert(*dest) {
changed = true;
}
}
}
}
}
set
}
fn call_target_name(func_val: &MirValue) -> Option<&Arc<str>> {
match func_val {
MirValue::Global(n) | MirValue::Function(n) => Some(n),
_ => None,
}
}
fn ref_param_index_of(func: &MirFunction) -> HashMap<LocalId, usize> {
func.locals
.iter()
.enumerate()
.filter(|(_, l)| l.is_param && matches!(l.ty, crate::codegen::ir::MirType::Ptr(_)))
.map(|(idx, l)| (l.id, idx))
.collect()
}
fn borrow_escaping_params_of(func: &MirFunction) -> HashSet<usize> {
let mut escaping = HashSet::new();
let Some(blocks) = &func.blocks else {
return escaping;
};
let ref_param_index = ref_param_index_of(func);
if ref_param_index.is_empty() {
return escaping;
}
let mut tainted: HashMap<LocalId, usize> = HashMap::new();
let taint_of = |tainted: &HashMap<LocalId, usize>, v: &MirValue| -> Option<usize> {
match v {
MirValue::Local(l) => tainted.get(l).copied(),
_ => None,
}
};
let mut changed = true;
while changed {
changed = false;
for block in blocks {
for stmt in &block.stmts {
if let MirStmtKind::Assign { dest, value } = &stmt.kind {
let origin = match value {
MirRValue::Deref {
ptr: MirValue::Local(p),
..
} => ref_param_index.get(p).copied(),
MirRValue::Use(MirValue::Local(s))
| MirRValue::Cast {
value: MirValue::Local(s),
..
} => tainted.get(s).copied(),
MirRValue::Aggregate { operands, .. } => {
operands.iter().find_map(|op| taint_of(&tainted, op))
}
MirRValue::FieldAccess { base, .. }
| MirRValue::VariantField { base, .. }
| MirRValue::IndexAccess { base, .. } => taint_of(&tainted, base),
_ => None,
};
if let Some(idx) = origin {
if tainted.insert(*dest, idx) != Some(idx) {
changed = true;
}
}
}
}
}
}
for block in blocks {
if let Some(MirTerminator::Return(Some(MirValue::Local(l)))) = &block.terminator {
if let Some(&idx) = tainted.get(l) {
escaping.insert(idx);
}
}
}
escaping
}
fn escaping_params_fixpoint(functions: &[MirFunction]) -> HashMap<Arc<str>, HashSet<usize>> {
let mut escaping: HashMap<Arc<str>, HashSet<usize>> = functions
.iter()
.map(|f| (f.name.clone(), borrow_escaping_params_of(f)))
.collect();
let ref_params: HashMap<Arc<str>, HashMap<LocalId, usize>> = functions
.iter()
.map(|f| (f.name.clone(), ref_param_index_of(f)))
.collect();
let mut changed = true;
while changed {
changed = false;
for f in functions {
let Some(my_ref_params) = ref_params.get(&f.name) else {
continue;
};
if my_ref_params.is_empty() {
continue;
}
let Some(blocks) = &f.blocks else {
continue;
};
let mut newly_escaping: Vec<usize> = Vec::new();
for block in blocks {
let Some(MirTerminator::Call {
func: callee, args, ..
}) = &block.terminator
else {
continue;
};
match call_target_name(callee) {
Some(callee_name) => {
let Some(callee_escaping) = escaping.get(callee_name) else {
continue;
};
for (i, a) in args.iter().enumerate() {
if let MirValue::Local(p) = a {
if let Some(&my_idx) = my_ref_params.get(p) {
if callee_escaping.contains(&i) {
newly_escaping.push(my_idx);
}
}
}
}
}
None => {
for a in args {
if let MirValue::Local(p) = a {
if let Some(&my_idx) = my_ref_params.get(p) {
newly_escaping.push(my_idx);
}
}
}
}
}
}
if !newly_escaping.is_empty() {
let my_set = escaping.entry(f.name.clone()).or_default();
for idx in newly_escaping {
if my_set.insert(idx) {
changed = true;
}
}
}
}
}
escaping.retain(|_, set| !set.is_empty());
escaping
}
fn move_out_of_shared_borrow(value: &MirRValue, shared_refs: &HashSet<LocalId>) -> Option<LocalId> {
match value {
MirRValue::Deref {
ptr: MirValue::Local(p),
..
} if shared_refs.contains(p) => Some(*p),
MirRValue::Discriminant(place) | MirRValue::Len(place) => {
if matches!(place.projections.first(), Some(PlaceProjection::Deref))
&& shared_refs.contains(&place.local)
{
Some(place.local)
} else {
None
}
}
_ => None,
}
}
fn field_extract_of_linear_out_of_borrow(
func: &MirFunction,
dest: &LocalId,
value: &MirRValue,
shared_refs: &HashSet<LocalId>,
) -> Option<LocalId> {
if !is_linear_local(func, *dest) {
return None;
}
let base = match value {
MirRValue::FieldAccess { base, .. }
| MirRValue::VariantField { base, .. }
| MirRValue::IndexAccess { base, .. } => base,
_ => return None,
};
match base {
MirValue::Local(p) if shared_refs.contains(p) => Some(*p),
_ => None,
}
}
fn moved_by_rvalue(func: &MirFunction, value: &MirRValue, out: &mut Vec<LocalId>) {
let mut push_if_linear = |v: &MirValue| {
if let MirValue::Local(l) = v {
if is_linear_local(func, *l) {
out.push(*l);
}
}
};
match value {
MirRValue::Use(v) => push_if_linear(v),
MirRValue::Aggregate { operands, .. } => operands.iter().for_each(&mut push_if_linear),
MirRValue::Repeat { value: v, .. } => push_if_linear(v),
MirRValue::Cast { value: v, .. } => push_if_linear(v),
MirRValue::VariantField { base, .. } => push_if_linear(base),
MirRValue::Ref { .. }
| MirRValue::AddressOf { .. }
| MirRValue::AddressOfGlobal { .. }
| MirRValue::FieldAccess { .. }
| MirRValue::IndexAccess { .. }
| MirRValue::Deref { .. }
| MirRValue::Discriminant(_)
| MirRValue::Len(_)
| MirRValue::BinaryOp { .. }
| MirRValue::UnaryOp { .. }
| MirRValue::NullaryOp(..)
| MirRValue::TextureSample { .. } => {}
}
}
fn read_by_rvalue(func: &MirFunction, value: &MirRValue, out: &mut Vec<LocalId>) {
fn push_place(func: &MirFunction, place: &MirPlace, out: &mut Vec<LocalId>) {
if is_linear_local(func, place.local) {
out.push(place.local);
}
}
fn push_val(func: &MirFunction, v: &MirValue, out: &mut Vec<LocalId>) {
if let MirValue::Local(l) = v {
if is_linear_local(func, *l) {
out.push(*l);
}
}
}
match value {
MirRValue::Ref { place, .. } | MirRValue::AddressOf { place, .. } => {
push_place(func, place, out)
}
MirRValue::Discriminant(place) | MirRValue::Len(place) => push_place(func, place, out),
MirRValue::FieldAccess { base, .. } => push_val(func, base, out),
MirRValue::IndexAccess { base, index, .. } => {
push_val(func, base, out);
push_val(func, index, out);
}
MirRValue::Deref { ptr, .. } => push_val(func, ptr, out),
MirRValue::BinaryOp { left, right, .. } => {
push_val(func, left, out);
push_val(func, right, out);
}
MirRValue::UnaryOp { operand, .. } => push_val(func, operand, out),
MirRValue::Use(_)
| MirRValue::Aggregate { .. }
| MirRValue::Repeat { .. }
| MirRValue::Cast { .. }
| MirRValue::VariantField { .. }
| MirRValue::NullaryOp(..)
| MirRValue::AddressOfGlobal { .. }
| MirRValue::TextureSample { .. } => {}
}
}
fn stmt_span(func: &MirFunction, block_id: u32, stmt_idx: usize) -> Span {
func.spans
.stmt
.get(&(block_id, stmt_idx))
.copied()
.unwrap_or_else(Span::dummy)
}
fn term_span(func: &MirFunction, block_id: u32) -> Span {
func.spans
.terminator
.get(&block_id)
.copied()
.unwrap_or_else(Span::dummy)
}
pub(crate) fn check_module(functions: &[MirFunction]) -> Vec<TypeErrorWithSpan> {
let ctx = LinearContext {
borrow_escaping_params: escaping_params_fixpoint(functions),
};
functions
.iter()
.flat_map(|f| check_with_context(f, &ctx))
.collect()
}
pub(crate) fn check(func: &MirFunction) -> Vec<TypeErrorWithSpan> {
check_with_context(func, &LinearContext::default())
}
fn check_with_context(func: &MirFunction, ctx: &LinearContext) -> Vec<TypeErrorWithSpan> {
let blocks = match &func.blocks {
Some(b) if !b.is_empty() => b.as_slice(),
_ => return Vec::new(),
};
if !func.locals.iter().any(|l| is_linear_local(func, l.id)) {
return Vec::new();
}
let n = blocks.len();
let id_to_index = block_id_index(blocks);
let reachable = reachable_blocks(blocks);
let shared_refs = shared_linear_ref_set(func);
let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
for (i, b) in blocks.iter().enumerate() {
if !reachable[i] {
continue;
}
for s in terminator_successors(&b.terminator, &id_to_index) {
if s < n {
preds[s].push(i);
}
}
}
let mut entry: Vec<BlockState> = vec![BlockState::new(); n];
let mut exit: Vec<BlockState> = vec![BlockState::new(); n];
let mut changed = true;
while changed {
changed = false;
for i in 0..n {
if !reachable[i] {
continue;
}
let mut new_entry = BlockState::new();
for &p in &preds[i] {
for (&local, &st) in &exit[p] {
let slot = new_entry.entry(local).or_insert(MoveState::Init);
if st == MoveState::Moved {
*slot = MoveState::Moved;
}
}
}
if new_entry != entry[i] {
entry[i] = new_entry;
changed = true;
}
let mut state = entry[i].clone();
transfer_block(func, ctx, &blocks[i], &shared_refs, &mut state, None);
if state != exit[i] {
exit[i] = state;
changed = true;
}
}
}
let mut errors = Vec::new();
for i in 0..n {
if !reachable[i] {
continue;
}
let mut state = entry[i].clone();
transfer_block(
func,
ctx,
&blocks[i],
&shared_refs,
&mut state,
Some(&mut errors),
);
}
errors
}
fn transfer_block(
func: &MirFunction,
ctx: &LinearContext,
block: &MirBlock,
shared_refs: &HashSet<LocalId>,
state: &mut BlockState,
mut errors: Option<&mut Vec<TypeErrorWithSpan>>,
) {
let block_id = block.id.0;
for (idx, stmt) in block.stmts.iter().enumerate() {
let span = stmt_span(func, block_id, idx);
apply_stmt(
func,
&stmt.kind,
shared_refs,
state,
span,
errors.as_deref_mut(),
);
}
let span = term_span(func, block_id);
apply_terminator(
func,
ctx,
&block.terminator,
shared_refs,
state,
span,
errors.as_deref_mut(),
);
}
fn apply_stmt(
func: &MirFunction,
kind: &MirStmtKind,
shared_refs: &HashSet<LocalId>,
state: &mut BlockState,
span: Span,
mut errors: Option<&mut Vec<TypeErrorWithSpan>>,
) {
if let MirStmtKind::Assign { dest, value } = kind {
if let Some(ptr) = move_out_of_shared_borrow(value, shared_refs) {
if let Some(errs) = errors.as_deref_mut() {
errs.push(TypeErrorWithSpan::new(
TypeError::LinearMoveOutOfBorrow {
name: local_name(func, ptr),
},
span,
));
}
}
if let Some(ptr) = field_extract_of_linear_out_of_borrow(func, dest, value, shared_refs) {
if let Some(errs) = errors.as_deref_mut() {
errs.push(TypeErrorWithSpan::new(
TypeError::LinearMoveOutOfBorrow {
name: local_name(func, ptr),
},
span,
));
}
}
let mut reads = Vec::new();
read_by_rvalue(func, value, &mut reads);
for l in reads {
if state.get(&l) == Some(&MoveState::Moved) {
if let Some(errs) = errors.as_deref_mut() {
errs.push(TypeErrorWithSpan::new(
TypeError::LinearBorrowAfterMove {
name: local_name(func, l),
},
span,
));
}
}
}
let mut moves = Vec::new();
moved_by_rvalue(func, value, &mut moves);
for l in moves {
apply_move(func, l, state, span, errors.as_deref_mut());
}
if is_linear_local(func, *dest) {
state.insert(*dest, MoveState::Init);
}
return;
}
let mut reads = Vec::new();
let mut moves = Vec::new();
match kind {
MirStmtKind::DerefAssign { ptr, value } => {
if is_linear_local(func, *ptr) {
reads.push(*ptr);
}
read_by_rvalue(func, value, &mut reads);
moved_by_rvalue(func, value, &mut moves);
}
MirStmtKind::FieldDerefAssign { ptr, value, .. } => {
if is_linear_local(func, *ptr) {
reads.push(*ptr);
}
read_by_rvalue(func, value, &mut reads);
moved_by_rvalue(func, value, &mut moves);
}
MirStmtKind::FieldAssign { base, value, .. } => {
if is_linear_local(func, *base) {
reads.push(*base);
}
read_by_rvalue(func, value, &mut reads);
moved_by_rvalue(func, value, &mut moves);
}
MirStmtKind::GlobalStore { value, .. } => {
read_by_rvalue(func, value, &mut reads);
moved_by_rvalue(func, value, &mut moves);
}
MirStmtKind::IndexStore {
base, index, value, ..
} => {
for v in [base, index] {
if let MirValue::Local(l) = v {
if is_linear_local(func, *l) {
reads.push(*l);
}
}
}
read_by_rvalue(func, value, &mut reads);
moved_by_rvalue(func, value, &mut moves);
}
MirStmtKind::Assign { .. }
| MirStmtKind::StorageLive(_)
| MirStmtKind::StorageDead(_)
| MirStmtKind::Nop
| MirStmtKind::WorkgroupBarrier => {}
}
for l in reads {
if state.get(&l) == Some(&MoveState::Moved) {
if let Some(errs) = errors.as_deref_mut() {
errs.push(TypeErrorWithSpan::new(
TypeError::LinearBorrowAfterMove {
name: local_name(func, l),
},
span,
));
}
}
}
for l in moves {
apply_move(func, l, state, span, errors.as_deref_mut());
}
}
fn apply_terminator(
func: &MirFunction,
ctx: &LinearContext,
term: &Option<MirTerminator>,
shared_refs: &HashSet<LocalId>,
state: &mut BlockState,
span: Span,
mut errors: Option<&mut Vec<TypeErrorWithSpan>>,
) {
match term {
Some(MirTerminator::Call {
args,
dest,
func: callee,
..
}) => {
if let Some(name) = call_target_name(callee) {
if let Some(escaping) = ctx.borrow_escaping_params.get(name) {
for (i, a) in args.iter().enumerate() {
if let MirValue::Local(p) = a {
if escaping.contains(&i) && shared_refs.contains(p) {
if let Some(errs) = errors.as_deref_mut() {
errs.push(TypeErrorWithSpan::new(
TypeError::LinearMoveOutOfBorrow {
name: local_name(func, *p),
},
span,
));
}
}
}
}
}
}
if let MirValue::Local(l) = callee {
if is_linear_local(func, *l) {
apply_move(func, *l, state, span, errors.as_deref_mut());
}
}
for a in args {
if let MirValue::Local(l) = a {
if is_linear_local(func, *l) {
apply_move(func, *l, state, span, errors.as_deref_mut());
}
}
}
if let Some(d) = dest {
if is_linear_local(func, *d) {
state.insert(*d, MoveState::Init);
}
}
}
Some(MirTerminator::Return(Some(MirValue::Local(l)))) => {
if is_linear_local(func, *l) {
apply_move(func, *l, state, span, errors.as_deref_mut());
}
}
Some(MirTerminator::If {
cond: MirValue::Local(l),
..
})
| Some(MirTerminator::Switch {
value: MirValue::Local(l),
..
})
| Some(MirTerminator::Assert {
cond: MirValue::Local(l),
..
}) => {
if is_linear_local(func, *l) && state.get(l) == Some(&MoveState::Moved) {
if let Some(errs) = errors.as_deref_mut() {
errs.push(TypeErrorWithSpan::new(
TypeError::LinearBorrowAfterMove {
name: local_name(func, *l),
},
span,
));
}
}
}
_ => {}
}
}
fn apply_move(
func: &MirFunction,
l: LocalId,
state: &mut BlockState,
span: Span,
errors: Option<&mut Vec<TypeErrorWithSpan>>,
) {
if state.get(&l) == Some(&MoveState::Moved) {
if let Some(errs) = errors {
errs.push(TypeErrorWithSpan::new(
TypeError::LinearUseAfterMove {
name: local_name(func, l),
},
span,
));
}
}
state.insert(l, MoveState::Moved);
}
#[cfg(test)]
mod tests {
use super::*;
use crate::codegen::ir::{
BlockId, LocalId, MirBlock, MirConst, MirFnSig, MirFunction, MirLocal, MirRValue, MirStmt,
MirTerminator, MirType, MirValue,
};
use std::sync::Arc;
fn linear_local(id: u32, name: &str) -> MirLocal {
MirLocal {
id: LocalId(id),
name: Some(Arc::from(name)),
ty: MirType::Struct(Arc::from("Qubit")),
is_mut: false,
is_param: false,
annotations: vec![Arc::from("linear")],
}
}
fn i64_local(id: u32, name: &str) -> MirLocal {
MirLocal {
id: LocalId(id),
name: Some(Arc::from(name)),
ty: MirType::i64(),
is_mut: false,
is_param: false,
annotations: Vec::new(),
}
}
fn untagged_ptr_local(id: u32, name: &str) -> MirLocal {
MirLocal {
id: LocalId(id),
name: Some(Arc::from(name)),
ty: MirType::Ptr(Box::new(MirType::Struct(Arc::from("Qubit")))),
is_mut: false,
is_param: false,
annotations: Vec::new(),
}
}
fn count(errors: &[TypeErrorWithSpan], pred: impl Fn(&TypeError) -> bool) -> usize {
errors.iter().filter(|e| pred(&e.error)).count()
}
fn linear_anon(id: u32) -> MirLocal {
MirLocal {
id: LocalId(id),
name: None,
ty: MirType::Struct(Arc::from("Qubit")),
is_mut: false,
is_param: false,
annotations: vec![Arc::from("linear")],
}
}
fn ref_param_local(id: u32, name: &str) -> MirLocal {
MirLocal {
id: LocalId(id),
name: Some(Arc::from(name)),
ty: MirType::Ptr(Box::new(MirType::Struct(Arc::from("Qubit")))),
is_mut: false,
is_param: true,
annotations: Vec::new(),
}
}
fn variant_field(base: LocalId) -> MirRValue {
MirRValue::VariantField {
base: MirValue::Local(base),
variant_name: Arc::from("Full"),
field_index: 0,
field_ty: MirType::Struct(Arc::from("Coin")),
}
}
#[test]
fn double_move_reports_use_after_move() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "q"));
func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(2, "_2"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearUseAfterMove { .. }
)),
1,
"exactly one use-after-move (the second consume of `q`): {errors:?}"
);
assert_eq!(errors.len(), 1, "no other diagnostics: {errors:?}");
}
#[test]
fn move_then_borrow_reports_borrow_after_move() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "q"));
func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(2, "_2"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearBorrowAfterMove { .. }
)),
1,
"the post-move borrow must be flagged: {errors:?}"
);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearUseAfterMove { .. }
)),
0,
"the borrow is not a second move: {errors:?}"
);
}
#[test]
fn move_out_of_shared_borrow_reports() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "coin"));
func.locals.push(untagged_ptr_local(1, "r"));
func.locals.push(i64_local(2, "_2"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(1)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"moving `*r` out of a real shared borrow must be flagged: {errors:?}"
);
}
#[test]
fn single_move_is_clean() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "q"));
func.locals.push(i64_local(1, "_1"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert!(errors.is_empty(), "a single move is legal: {errors:?}");
}
#[test]
fn move_then_rebind_then_use_is_clean() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "q"));
func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(2, "_2"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("make_qubit")),
args: Vec::new(),
dest: Some(LocalId(0)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b1.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1]);
let errors = check(&func);
assert!(
errors.is_empty(),
"re-binding resets move state; the later use is legal: {errors:?}"
);
}
#[test]
fn maybe_moved_join_reports_use_after_move() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "q"));
func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(2, "_2"));
func.locals.push(i64_local(9, "cond"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(1),
else_block: BlockId(2),
});
let mut b1 = MirBlock::new(BlockId(1));
b1.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b1.terminator = Some(MirTerminator::Goto(BlockId(3)));
let mut b2 = MirBlock::new(BlockId(2));
b2.terminator = Some(MirTerminator::Goto(BlockId(3)));
let mut b3 = MirBlock::new(BlockId(3));
b3.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b3.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1, b2, b3]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearUseAfterMove { .. }
)),
1,
"a value maybe-moved on one arm is moved after the join: {errors:?}"
);
}
#[test]
fn loop_rebind_and_move_each_iteration_is_clean() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "q"));
func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(9, "cond"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("make_qubit")),
args: Vec::new(),
dest: Some(LocalId(0)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(2),
else_block: BlockId(3),
});
let mut b2 = MirBlock::new(BlockId(2));
b2.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b2.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("make_qubit")),
args: Vec::new(),
dest: Some(LocalId(0)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b3 = MirBlock::new(BlockId(3));
b3.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1, b2, b3]);
let errors = check(&func);
assert!(
errors.is_empty(),
"each iteration rebinds then moves once; no double-consume: {errors:?}"
);
}
#[test]
fn non_linear_double_move_is_ignored() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(i64_local(0, "x")); func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(2, "_2"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert!(
errors.is_empty(),
"non-linear locals are not move-checked: {errors:?}"
);
}
#[test]
fn store_by_value_move_is_consumed() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "coin"));
func.locals.push(i64_local(1, "obj"));
func.locals.push(i64_local(2, "_2"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::new(MirStmtKind::FieldAssign {
base: LocalId(1),
field_name: Arc::from("field"),
value: MirRValue::Use(MirValue::Local(LocalId(0))),
}));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearUseAfterMove { .. }
)),
1,
"the store consumes `coin`; the later use is a use-after-move: {errors:?}"
);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearBorrowAfterMove { .. }
)),
0,
"the store is a by-value move, not a borrow-after-move: {errors:?}"
);
assert_eq!(errors.len(), 1, "no other diagnostics: {errors:?}");
}
#[test]
fn move_out_of_mut_borrow_is_not_flagged() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "coin"));
func.locals.push(untagged_ptr_local(1, "r"));
func.locals.push(i64_local(2, "a"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: true,
place: MirPlace::local(LocalId(0)),
},
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(1)),
pointee_ty: MirType::Struct(Arc::from("Coin")),
},
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
0,
"a `&mut` deref-move is not a shared move-out-of-borrow: {errors:?}"
);
}
#[test]
fn owned_variant_field_bind_moves_scrutinee() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "w")); func.locals.push(linear_anon(1)); func.locals.push(i64_local(2, "c1"));
func.locals.push(i64_local(3, "c2"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.stmts
.push(MirStmt::assign(LocalId(2), variant_field(LocalId(1))));
b0.stmts
.push(MirStmt::assign(LocalId(3), variant_field(LocalId(1))));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearUseAfterMove { .. }
)),
1,
"the second VariantField bind double-consumes the scrutinee: {errors:?}"
);
}
#[test]
fn owned_variant_field_bind_once_is_clean() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "w"));
func.locals.push(linear_anon(1));
func.locals.push(i64_local(2, "c"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Use(MirValue::Local(LocalId(0))),
));
b0.stmts
.push(MirStmt::assign(LocalId(2), variant_field(LocalId(1))));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert!(
errors.is_empty(),
"a single payload bind is a legal move of the scrutinee: {errors:?}"
);
}
#[test]
fn match_through_shared_borrow_reports_move_out_of_borrow() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "w")); func.locals.push(untagged_ptr_local(1, "r")); func.locals.push(linear_anon(2)); func.locals.push(i64_local(3, "c"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(1)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.stmts
.push(MirStmt::assign(LocalId(3), variant_field(LocalId(2))));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"matching a linear through a shared borrow moves it out of the borrow: {errors:?}"
);
}
#[test]
fn class3_pass_shared_borrow_into_borrow_escaping_param_reports() {
let mut callee = MirFunction::new("deref_any", MirFnSig::new(vec![], MirType::Void));
callee.locals.push(ref_param_local(0, "r")); callee.locals.push(linear_anon(1)); let mut cb0 = MirBlock::new(BlockId(0));
cb0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(0)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
cb0.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(1)))));
callee.blocks = Some(vec![cb0]);
let mut caller = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
caller.locals.push(linear_local(0, "coin"));
caller.locals.push(untagged_ptr_local(1, "r")); caller.locals.push(linear_anon(2)); let mut mb0 = MirBlock::new(BlockId(0));
mb0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
mb0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("deref_any")),
args: vec![MirValue::Local(LocalId(1))],
dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut mb1 = MirBlock::new(BlockId(1));
mb1.terminator = Some(MirTerminator::Return(None));
caller.blocks = Some(vec![mb0, mb1]);
let errors = check_module(&[callee, caller]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into a deref-and-return param moves it out of the borrow: {errors:?}"
);
}
#[test]
fn class3_read_only_borrow_param_is_clean() {
let mut callee = MirFunction::new("peek", MirFnSig::new(vec![], MirType::Void));
callee.locals.push(ref_param_local(0, "r"));
let mut cb0 = MirBlock::new(BlockId(0));
cb0.terminator = Some(MirTerminator::Return(Some(MirValue::Const(MirConst::Int(
0,
MirType::i64(),
)))));
callee.blocks = Some(vec![cb0]);
let mut caller = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
caller.locals.push(linear_local(0, "coin"));
caller.locals.push(untagged_ptr_local(1, "r"));
caller.locals.push(i64_local(2, "res"));
let mut mb0 = MirBlock::new(BlockId(0));
mb0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
mb0.terminator = Some(MirTerminator::Call {
func: MirValue::Global(Arc::from("peek")),
args: vec![MirValue::Local(LocalId(1))],
dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut mb1 = MirBlock::new(BlockId(1));
mb1.terminator = Some(MirTerminator::Return(None));
caller.blocks = Some(vec![mb0, mb1]);
let errors = check_module(&[callee, caller]);
assert!(
errors.is_empty(),
"a read-only borrow parameter is the legal borrow case; not flagged: {errors:?}"
);
}
#[test]
fn precision_linear_in_tuple_used_once_is_clean() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "coin"));
func.locals.push(i64_local(1, "seven"));
func.locals.push(i64_local(2, "tuple")); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Aggregate {
kind: crate::codegen::ir::AggregateKind::Tuple,
operands: vec![MirValue::Local(LocalId(0)), MirValue::Local(LocalId(1))],
},
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert!(
errors.is_empty(),
"a linear moved into a tuple exactly once is safe: {errors:?}"
);
}
#[test]
fn precision_option_of_linear_once_is_clean() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "coin"));
func.locals.push(linear_anon(1)); func.locals.push(i64_local(2, "res"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Aggregate {
kind: crate::codegen::ir::AggregateKind::Variant(
Arc::from("Option"),
0,
Arc::from("Some"),
),
operands: vec![MirValue::Local(LocalId(0))],
},
));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Global(Arc::from("consume")),
args: vec![MirValue::Local(LocalId(1))],
dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1]);
let errors = check(&func);
assert!(
errors.is_empty(),
"constructing Some(coin) and consuming it once is safe: {errors:?}"
);
}
#[test]
fn precision_generic_identity_over_linear_is_clean() {
let mut callee = MirFunction::new("id", MirFnSig::new(vec![], MirType::Void));
callee.locals.push(linear_local(0, "x")); let mut cb0 = MirBlock::new(BlockId(0));
cb0.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(0)))));
callee.blocks = Some(vec![cb0]);
let mut caller = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
caller.locals.push(linear_local(0, "coin"));
caller.locals.push(linear_anon(1)); caller.locals.push(i64_local(2, "r"));
let mut mb0 = MirBlock::new(BlockId(0));
mb0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("id")),
args: vec![MirValue::Local(LocalId(0))],
dest: Some(LocalId(1)),
target: Some(BlockId(1)),
unwind: None,
});
let mut mb1 = MirBlock::new(BlockId(1));
mb1.terminator = Some(MirTerminator::Call {
func: MirValue::Global(Arc::from("spend")),
args: vec![MirValue::Local(LocalId(1))],
dest: Some(LocalId(2)),
target: Some(BlockId(2)),
unwind: None,
});
let mut mb2 = MirBlock::new(BlockId(2));
mb2.terminator = Some(MirTerminator::Return(None));
caller.blocks = Some(vec![mb0, mb1, mb2]);
let errors = check_module(&[callee, caller]);
assert!(
errors.is_empty(),
"generic identity over a linear, consumed once, is safe: {errors:?}"
);
}
#[test]
fn precision_closure_moving_linear_once_is_clean() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "coin"));
func.locals.push(i64_local(1, "clos")); func.locals.push(i64_local(2, "res"));
let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Aggregate {
kind: crate::codegen::ir::AggregateKind::Closure(Arc::from("closure_0")),
operands: vec![MirValue::Local(LocalId(0))],
},
));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Local(LocalId(1)),
args: vec![],
dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1]);
let errors = check(&func);
assert!(
errors.is_empty(),
"a closure capturing a linear by value once is safe: {errors:?}"
);
}
fn deref_and_return_callee(name: &str) -> MirFunction {
let mut f = MirFunction::new(name, MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(0, "r")); f.locals.push(linear_anon(1)); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(0)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(1)))));
f.blocks = Some(vec![b0]);
f
}
fn read_only_callee(name: &str) -> MirFunction {
let mut f = MirFunction::new(name, MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(0, "r"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Return(Some(MirValue::Const(MirConst::Int(
0,
MirType::i64(),
)))));
f.blocks = Some(vec![b0]);
f
}
fn forwarding_wrapper(name: &str, callee: &str) -> MirFunction {
let mut f = MirFunction::new(name, MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(0, "r")); f.locals.push(linear_anon(1)); let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from(callee)),
args: vec![MirValue::Local(LocalId(0))],
dest: Some(LocalId(1)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(1)))));
f.blocks = Some(vec![b0, b1]);
f
}
fn caller_passing_shared_borrow(callee: &str) -> MirFunction {
let mut caller = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
caller.locals.push(linear_local(0, "coin"));
caller.locals.push(untagged_ptr_local(1, "r")); caller.locals.push(linear_anon(2)); let mut mb0 = MirBlock::new(BlockId(0));
mb0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
mb0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from(callee)),
args: vec![MirValue::Local(LocalId(1))],
dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut mb1 = MirBlock::new(BlockId(1));
mb1.terminator = Some(MirTerminator::Return(None));
caller.blocks = Some(vec![mb0, mb1]);
caller
}
#[test]
fn fixpoint_forwarding_wrapper_param_is_borrow_escaping() {
let deref_any = deref_and_return_callee("deref_any");
let wrap = forwarding_wrapper("wrap", "deref_any");
let escaping = escaping_params_fixpoint(&[deref_any, wrap]);
assert_eq!(
escaping.get("deref_any"),
Some(&HashSet::from([0])),
"the direct deref-and-return param is the base case: {escaping:?}"
);
assert_eq!(
escaping.get("wrap"),
Some(&HashSet::from([0])),
"the wrapper forwarding into an escaping callee must be escaping too: {escaping:?}"
);
}
#[test]
fn fixpoint_pass_shared_borrow_into_wrapper_reports() {
let deref_any = deref_and_return_callee("deref_any");
let wrap = forwarding_wrapper("wrap", "deref_any");
let main = caller_passing_shared_borrow("wrap");
let errors = check_module(&[deref_any, wrap, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into a transitive wrapper moves it out of the borrow: {errors:?}"
);
}
#[test]
fn fixpoint_wrapper_over_non_escaping_callee_stays_clean() {
let peek = read_only_callee("peek");
let w2 = forwarding_wrapper("w2", "peek");
let main = caller_passing_shared_borrow("w2");
let escaping = escaping_params_fixpoint(&[peek.clone(), w2.clone()]);
assert!(
escaping.get("peek").is_none(),
"a read-only borrow param is not escaping: {escaping:?}"
);
assert!(
escaping.get("w2").is_none(),
"a wrapper over a non-escaping callee is not escaping: {escaping:?}"
);
let errors = check_module(&[peek, w2, main]);
assert!(
errors.is_empty(),
"passing `&coin` into a non-escaping wrapper is the legal borrow case: {errors:?}"
);
}
#[test]
fn fixpoint_two_level_wrapper_reports() {
let deref_any = deref_and_return_callee("deref_any");
let wrap = forwarding_wrapper("wrap", "deref_any");
let wrap2 = forwarding_wrapper("wrap2", "wrap");
let escaping = escaping_params_fixpoint(&[deref_any.clone(), wrap.clone(), wrap2.clone()]);
assert_eq!(
escaping.get("wrap2"),
Some(&HashSet::from([0])),
"escaping must propagate two hops up the wrapper chain: {escaping:?}"
);
let main = caller_passing_shared_borrow("wrap2");
let errors = check_module(&[deref_any, wrap, wrap2, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into a two-level wrapper moves it out of the borrow: {errors:?}"
);
}
#[test]
fn fixpoint_recursive_wrapper_terminates_and_reports() {
let deref_any = deref_and_return_callee("deref_any");
let mut rec = MirFunction::new("rec", MirFnSig::new(vec![], MirType::Void));
rec.locals.push(ref_param_local(0, "r")); rec.locals.push(i64_local(9, "cond"));
rec.locals.push(linear_anon(1)); rec.locals.push(linear_anon(2)); let mut rb0 = MirBlock::new(BlockId(0));
rb0.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(1),
else_block: BlockId(2),
});
let mut rb1 = MirBlock::new(BlockId(1));
rb1.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("rec")),
args: vec![MirValue::Local(LocalId(0))],
dest: Some(LocalId(1)),
target: Some(BlockId(3)),
unwind: None,
});
let mut rb2 = MirBlock::new(BlockId(2));
rb2.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("deref_any")),
args: vec![MirValue::Local(LocalId(0))],
dest: Some(LocalId(2)),
target: Some(BlockId(3)),
unwind: None,
});
let mut rb3 = MirBlock::new(BlockId(3));
rb3.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(1)))));
rec.blocks = Some(vec![rb0, rb1, rb2, rb3]);
let escaping = escaping_params_fixpoint(&[deref_any.clone(), rec.clone()]);
assert_eq!(
escaping.get("rec"),
Some(&HashSet::from([0])),
"a recursive wrapper forwarding to an escaping callee is escaping: {escaping:?}"
);
let main = caller_passing_shared_borrow("rec");
let errors = check_module(&[deref_any, rec, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into the recursive wrapper is rejected: {errors:?}"
);
}
fn box_aggregate(operand: LocalId) -> MirRValue {
MirRValue::Aggregate {
kind: crate::codegen::ir::AggregateKind::Struct(Arc::from("Box_i32")),
operands: vec![MirValue::Local(operand)],
}
}
fn deref_boxed_struct_callee(name: &str) -> MirFunction {
let mut f = MirFunction::new(name, MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(0, "r")); f.locals.push(linear_anon(2)); f.locals.push(i64_local(3, "box")); f.locals.push(i64_local(4, "b")); f.locals.push(linear_anon(5)); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(0)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.stmts
.push(MirStmt::assign(LocalId(3), box_aggregate(LocalId(2))));
b0.stmts.push(MirStmt::assign(
LocalId(4),
MirRValue::Use(MirValue::Local(LocalId(3))),
));
b0.stmts.push(MirStmt::assign(
LocalId(5),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(4)),
field_name: Arc::from("item"),
field_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(5)))));
f.blocks = Some(vec![b0]);
f
}
#[test]
fn fixa_deref_boxed_struct_is_borrow_escaping() {
let f = deref_boxed_struct_callee("deref_boxed");
let escaping = escaping_params_fixpoint(&[f]);
assert_eq!(
escaping.get("deref_boxed"),
Some(&HashSet::from([0])),
"taint must follow *r through the struct aggregate and field-access: {escaping:?}"
);
}
#[test]
fn fixa_pass_shared_borrow_into_struct_launder_reports() {
let f = deref_boxed_struct_callee("deref_boxed");
let main = caller_passing_shared_borrow("deref_boxed");
let errors = check_module(&[f, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into a struct-laundering deref-return clones the linear: {errors:?}"
);
}
#[test]
fn fixa_deref_tuple_is_borrow_escaping_and_reports() {
let mut f = MirFunction::new("deref_tup", MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(0, "r"));
f.locals.push(linear_anon(1)); f.locals.push(i64_local(2, "tup")); f.locals.push(linear_anon(3)); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(0)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Aggregate {
kind: crate::codegen::ir::AggregateKind::Tuple,
operands: vec![MirValue::Local(LocalId(1))],
},
));
b0.stmts.push(MirStmt::assign(
LocalId(3),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(2)),
field_name: Arc::from("0"),
field_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(3)))));
f.blocks = Some(vec![b0]);
let escaping = escaping_params_fixpoint(std::slice::from_ref(&f));
assert_eq!(
escaping.get("deref_tup"),
Some(&HashSet::from([0])),
"taint must follow *r through a tuple aggregate and projection: {escaping:?}"
);
let main = caller_passing_shared_borrow("deref_tup");
let errors = check_module(&[f, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"the tuple launder clones the linear: {errors:?}"
);
}
#[test]
fn fixa_deref_enum_is_borrow_escaping_and_reports() {
let mut f = MirFunction::new("deref_enum", MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(0, "r"));
f.locals.push(linear_anon(1)); f.locals.push(linear_anon(2)); f.locals.push(linear_anon(3)); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(0)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Aggregate {
kind: crate::codegen::ir::AggregateKind::Variant(
Arc::from("Option"),
0,
Arc::from("Some"),
),
operands: vec![MirValue::Local(LocalId(1))],
},
));
b0.stmts
.push(MirStmt::assign(LocalId(3), variant_field(LocalId(2))));
b0.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(3)))));
f.blocks = Some(vec![b0]);
let escaping = escaping_params_fixpoint(std::slice::from_ref(&f));
assert_eq!(
escaping.get("deref_enum"),
Some(&HashSet::from([0])),
"taint must follow *r through an enum-variant aggregate and VariantField: {escaping:?}"
);
let main = caller_passing_shared_borrow("deref_enum");
let errors = check_module(&[f, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"the enum launder clones the linear: {errors:?}"
);
}
#[test]
fn fixa_three_level_wrapper_over_launder_reports() {
let launder = deref_boxed_struct_callee("launder");
let w1 = forwarding_wrapper("w1", "launder");
let w2 = forwarding_wrapper("w2", "w1");
let escaping = escaping_params_fixpoint(&[launder.clone(), w1.clone(), w2.clone()]);
assert_eq!(
escaping.get("launder"),
Some(&HashSet::from([0])),
"the aggregate-launder base case is escaping: {escaping:?}"
);
assert_eq!(
escaping.get("w2"),
Some(&HashSet::from([0])),
"escaping must propagate two hops up over an aggregate-launder base: {escaping:?}"
);
let main = caller_passing_shared_borrow("w2");
let errors = check_module(&[launder, w1, w2, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into a 3-level wrapper over a launder clones the linear: {errors:?}"
);
}
#[test]
fn fixa_deref_into_local_aggregate_returning_scalar_stays_clean() {
let mut f = MirFunction::new("inspect", MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(0, "r"));
f.locals.push(linear_anon(1)); f.locals.push(i64_local(2, "box")); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Deref {
ptr: MirValue::Local(LocalId(0)),
pointee_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.stmts
.push(MirStmt::assign(LocalId(2), box_aggregate(LocalId(1))));
b0.terminator = Some(MirTerminator::Return(Some(MirValue::Const(MirConst::Int(
0,
MirType::i64(),
)))));
f.blocks = Some(vec![b0]);
let escaping = escaping_params_fixpoint(std::slice::from_ref(&f));
assert!(
escaping.get("inspect").is_none(),
"boxing *r locally but returning a scalar is not borrow-escaping: {escaping:?}"
);
let main = caller_passing_shared_borrow("inspect");
let errors = check_module(&[f, main]);
assert!(
errors.is_empty(),
"a fn that boxes *r locally and returns a scalar is clean: {errors:?}"
);
}
#[test]
fn fixb_record_pattern_field_extract_through_borrow_reports() {
let mut func = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "w")); func.locals.push(untagged_ptr_local(1, "_4")); func.locals.push(untagged_ptr_local(2, "_5")); func.locals.push(linear_anon(3)); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Use(MirValue::Local(LocalId(1))),
));
b0.stmts.push(MirStmt::assign(
LocalId(3),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(2)),
field_name: Arc::from("coin"),
field_ty: MirType::Struct(Arc::from("Qubit")),
},
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"extracting a linear field out of a shared borrow (record pattern) is a move-out: {errors:?}"
);
}
#[test]
fn fixb_nonlinear_field_extract_through_borrow_is_clean() {
let mut func = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
func.locals.push(linear_local(0, "p")); func.locals.push(untagged_ptr_local(1, "r")); func.locals.push(untagged_ptr_local(2, "s")); func.locals.push(i64_local(3, "v")); let mut b0 = MirBlock::new(BlockId(0));
b0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
b0.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::Use(MirValue::Local(LocalId(1))),
));
b0.stmts.push(MirStmt::assign(
LocalId(3),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(2)),
field_name: Arc::from("x"),
field_ty: MirType::i64(),
},
));
b0.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0]);
let errors = check(&func);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
0,
"reading a non-linear field through a shared borrow is the legal case: {errors:?}"
);
}
fn apply_indirect_call(name: &str, fn_ptr_param: u32, ref_param: u32) -> MirFunction {
let mut f = MirFunction::new(name, MirFnSig::new(vec![], MirType::Void));
f.locals.push(ref_param_local(fn_ptr_param, "f"));
f.locals.push(ref_param_local(ref_param, "r"));
f.locals.push(linear_anon(2)); let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Local(LocalId(fn_ptr_param)), args: vec![MirValue::Local(LocalId(ref_param))],
dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(2)))));
f.blocks = Some(vec![b0, b1]);
f
}
#[test]
fn fix2_apply_ref_param_forwarded_into_fn_pointer_is_escaping() {
let apply = apply_indirect_call("apply", 0, 1);
let escaping = escaping_params_fixpoint(std::slice::from_ref(&apply));
assert_eq!(
escaping.get("apply"),
Some(&HashSet::from([1])),
"a &-param forwarded into an indirect fn-pointer call is escaping: {escaping:?}"
);
}
#[test]
fn fix2_pass_shared_borrow_into_apply_reports() {
let apply = apply_indirect_call("apply", 0, 1);
let mut caller = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
caller.locals.push(linear_local(0, "coin"));
caller.locals.push(untagged_ptr_local(1, "r")); caller.locals.push(untagged_ptr_local(2, "fptr")); caller.locals.push(linear_anon(3)); let mut mb0 = MirBlock::new(BlockId(0));
mb0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
mb0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("apply")),
args: vec![MirValue::Local(LocalId(2)), MirValue::Local(LocalId(1))],
dest: Some(LocalId(3)),
target: Some(BlockId(1)),
unwind: None,
});
let mut mb1 = MirBlock::new(BlockId(1));
mb1.terminator = Some(MirTerminator::Return(None));
caller.blocks = Some(vec![mb0, mb1]);
let errors = check_module(&[apply, caller]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into apply's fn-pointer-forwarded &-param is a move-out: {errors:?}"
);
}
#[test]
fn fix2_two_level_apply_over_fn_pointer_reports() {
let apply = apply_indirect_call("apply", 0, 1);
let mut apply2 = MirFunction::new("apply2", MirFnSig::new(vec![], MirType::Void));
apply2.locals.push(ref_param_local(0, "f"));
apply2.locals.push(ref_param_local(1, "r"));
apply2.locals.push(linear_anon(2)); let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("apply")),
args: vec![MirValue::Local(LocalId(0)), MirValue::Local(LocalId(1))],
dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(2)))));
apply2.blocks = Some(vec![b0, b1]);
let escaping = escaping_params_fixpoint(&[apply.clone(), apply2.clone()]);
assert_eq!(
escaping.get("apply2"),
Some(&HashSet::from([1])),
"escaping must propagate up from the fn-pointer base to apply2: {escaping:?}"
);
let mut caller = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
caller.locals.push(linear_local(0, "coin"));
caller.locals.push(untagged_ptr_local(1, "r"));
caller.locals.push(untagged_ptr_local(2, "fptr"));
caller.locals.push(linear_anon(3));
let mut mb0 = MirBlock::new(BlockId(0));
mb0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
mb0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("apply2")),
args: vec![MirValue::Local(LocalId(2)), MirValue::Local(LocalId(1))],
dest: Some(LocalId(3)),
target: Some(BlockId(1)),
unwind: None,
});
let mut mb1 = MirBlock::new(BlockId(1));
mb1.terminator = Some(MirTerminator::Return(None));
caller.blocks = Some(vec![mb0, mb1]);
let errors = check_module(&[apply, apply2, caller]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into a 2-level fn-pointer wrapper is a move-out: {errors:?}"
);
}
#[test]
fn fix2_struct_field_fn_pointer_is_escaping_and_reports() {
let run = apply_indirect_call("run", 0, 1);
let escaping = escaping_params_fixpoint(std::slice::from_ref(&run));
assert_eq!(
escaping.get("run"),
Some(&HashSet::from([1])),
"a &-param forwarded into a struct-field fn-pointer call is escaping: {escaping:?}"
);
let main = {
let mut caller = MirFunction::new("main", MirFnSig::new(vec![], MirType::Void));
caller.locals.push(linear_local(0, "coin"));
caller.locals.push(untagged_ptr_local(1, "r"));
caller.locals.push(untagged_ptr_local(2, "fptr"));
caller.locals.push(linear_anon(3));
let mut mb0 = MirBlock::new(BlockId(0));
mb0.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::Ref {
is_mut: false,
place: MirPlace::local(LocalId(0)),
},
));
mb0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("run")),
args: vec![MirValue::Local(LocalId(2)), MirValue::Local(LocalId(1))],
dest: Some(LocalId(3)),
target: Some(BlockId(1)),
unwind: None,
});
let mut mb1 = MirBlock::new(BlockId(1));
mb1.terminator = Some(MirTerminator::Return(None));
caller.blocks = Some(vec![mb0, mb1]);
caller
};
let errors = check_module(&[run, main]);
assert_eq!(
count(&errors, |e| matches!(
e,
TypeError::LinearMoveOutOfBorrow { .. }
)),
1,
"passing `&coin` into a struct-field fn-pointer consumer is a move-out: {errors:?}"
);
}
#[test]
fn fix2_indirect_call_not_forwarding_ref_param_stays_clean() {
let mut g = MirFunction::new("g", MirFnSig::new(vec![], MirType::Void));
g.locals.push(ref_param_local(0, "f")); g.locals.push(ref_param_local(1, "r")); g.locals.push(i64_local(2, "res"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Local(LocalId(0)), args: vec![], dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::Return(None));
g.blocks = Some(vec![b0, b1]);
let escaping = escaping_params_fixpoint(std::slice::from_ref(&g));
assert!(
escaping.get("g").is_none(),
"an indirect call not forwarding a &-param is not escaping: {escaping:?}"
);
let main = caller_passing_shared_borrow("g");
let errors = check_module(&[g, main]);
assert!(
errors.is_empty(),
"passing `&coin` into a fn that does not forward it is the legal case: {errors:?}"
);
}
}