radiance · commit

compiler: Retain explicit argument borrows through call evaluation

bcc4a622ad4d2e8c1d643ffdb138bafa273e948db85c8e3fafe315d19496b4ed

Alexis Sellier committed 7 days ago 1 parent 2c67cf47

lib/std/lang/resolver.rad +40 -3

    precise: bool,
}

/// A reference binding that protects its source for one lexical scope.
record LocalLoan: Copy {
    /// Local symbol through which the source can be accessed.
    binding: *unsafe mut Symbol,
    /// Local symbol that provides access, or nil for a pending call argument.
    binding: ?*unsafe mut Symbol,
    /// Storage retained by the reference.
    place: BorrowPlace,
    /// Whether other reads of the source are excluded.
    exclusive: bool,
}

            throw emitError(checker.resolver, node, ErrorKind::BorrowConflict(root.name));
        }
    }
    for i in 0..checker.localLen {
        let loan = checker.locals[i];
        let mut throughBinding = false;
        if let binding = loan.binding {
            set throughBinding = usesLocalLoan(checker.resolver, node, binding);
        }
        if (exclusive or loan.exclusive) and placesOverlap(&place, &loan.place)
            and not usesLocalLoan(checker.resolver, node, loan.binding)
            and not throughBinding
        {
            throw emitError(checker.resolver, node, ErrorKind::BorrowConflict(root.name));
        }
    }
}

    checker: &mut LinearChecker 'arena 'checking,
    env: &mut LinearEnv,
    node: *ast::Node,
    call: ast::Call,
) throws (ResolveError) where 'arena: 'checking {
    let localStart = checker.localLen;
    match checker.resolver.nodeData.entries[node.id].extra {
        case NodeExtra::SliceAppend { .. }, NodeExtra::SliceDelete { .. } => {
            let case ast::NodeValue::FieldAccess(access) = call.callee.value
                else panic "slice mutation without receiver";
            try checkPatternLoan(checker, access.parent);

                    set placesLen += 1;
                }
            }
            if types::isReference(receiverClass) {
                try checkLinearNode(checker, env, access.parent, LinearUse::Borrow);
                if createsExplicitBorrow(access.parent) {
                    try retainCallLoan(checker, access.parent, receiverMutable);
                }
            } else if receiverClass == types::PointerClass::Owned {
                try checkLinearNode(checker, env, access.parent, LinearUse::Consume);
            }
        }
    }

        if isBorrowedReferenceParameter(expected) {
            try checkLinearNode(checker, env, arg, LinearUse::Borrow);
        } else {
            try checkLinearNode(checker, env, arg, LinearUse::Consume);
        }
        if isRefType(expected) and createsExplicitBorrow(arg) {
            try retainCallLoan(checker, arg, argExclusive);
        }
    }
    set checker.localLen = localStart;
    if *info.returnType == Type::Never and info.throwList.len == 0 {
        set env.terminated = true;
    }
}

/// Return whether evaluating an argument creates an explicit address borrow.
fn createsExplicitBorrow(node: *ast::Node) -> bool {
    match node.value {
        case ast::NodeValue::AddressOf(_) => return true,
        case ast::NodeValue::As(cast) => return createsExplicitBorrow(cast.value),
        case ast::NodeValue::RegionApply { value, .. } => return createsExplicitBorrow(value),
        else => return false,
    }
}

/// Protect explicit address arguments until their call begins.
unsafe fn retainCallLoan 'arena 'checking (
    checker: &mut LinearChecker 'arena 'checking, node: *ast::Node, exclusive: bool
) throws (ResolveError) where 'arena: 'checking {
    let place = borrowPlace(checker.resolver, node);
    if place.root == nil {
        return;
    }
    if checker.localLen >= MAX_LINEAR_BINDINGS {
        throw emitError(checker.resolver, node, ErrorKind::Internal);
    }
    set checker.locals[checker.localLen] = LocalLoan { binding: nil, place, exclusive };
    set checker.localLen += 1;
}

/// Check a pattern conditional. Linear scrutinees require an exhaustive match.
unsafe fn checkLinearIfLet 'arena 'checking (
    checker: &mut LinearChecker 'arena 'checking,
    env: &mut LinearEnv,
    node: *ast::Node,

lib/std/lang/resolver/tests/regions.rad +34 -0

use std::mem;
use std::testing;
use std::lang::types;
use std::lang::resolver;

/// Earlier reference arguments protect their storage during later arguments.
@test unsafe fn testRegionalCallArgumentLoans() throws (testing::TestError) {
    for program in [
        "fn inner(p: &mut u32) -> u32 { set *p = 2; return 0; } fn outer(p: &mut u32, n: u32) {} fn f 'r (p: &'r mut u32) { outer(&mut *p, inner(p)); }",
        "fn inner(p: &mut u32) -> u32 { set *p = 2; return 0; } fn outer(p: &u32, n: u32) {} fn f 'r (p: &'r mut u32) { outer(&*p, inner(p)); }",
        "fn inner(p: &mut u32) -> u32 { set *p = 2; return 0; } fn outer(p: &mut u32, n: u32) {} unsafe fn f 'r (p: &'r mut u32) { outer(&mut *p, inner(p)); }",
        "record R { n: u32 } fn (r: &mut R) call(n: u32) {} fn inner(p: &mut u32) -> u32 { set *p = 2; return 0; } fn f 'r (r: &'r mut R) { (&mut *r).call(inner(&mut r.n)); }",
    ] {
        let mut arena = super::testArena();
        let storage: 'test = &mut arena in {
            let mut res = super::testResolver(storage);
            let result = try super::resolveProgramStr(&mut res, program);
            let error = try super::expectError(&result);
            let case resolver::ErrorKind::BorrowConflict(_) = error.kind
                else throw testing::TestError::Failed;
        }
    }
}

/// Call loans allow shared reads, separate fields, and access after the call.
@test unsafe fn testRegionalCallArgumentLoanScopes() throws (testing::TestError) {
    for program in [
        "fn read(p: &u32) -> u32 { return *p; } fn outer(p: &u32, n: u32) {} fn f 'r (p: &'r mut u32) { outer(&*p, read(p)); set *p = 3; }",
        "record R { a: u32, b: u32 } fn inner(p: &mut u32) -> u32 { set *p = 2; return 0; } fn outer(p: &mut u32, n: u32) {} fn f 'r (r: &'r mut R) { outer(&mut r.a, inner(&mut r.b)); set r.a = 3; }",
    ] {
        let mut arena = super::testArena();
        let storage: 'test = &mut arena in {
            let mut res = super::testResolver(storage);
            let result = try super::resolveProgramStr(&mut res, program);
            try super::expectNoErrors(&result);
        }
    }
}

/// Equal region spellings in separate functions have distinct identities.
@test unsafe fn testRegionIdentities() throws (testing::TestError) {
    let mut testArena1 = super::testArena();
    let testStorage1: 'test1 = &mut testArena1 in {
        let mut res = super::testResolver(testStorage1);

lib/std/vec.rad +6 -4

/// Returns false if the vector is at capacity.
export unsafe fn push(vec: &mut RawVec, elem: &opaque) -> bool {
    if vec.len >= capacity(vec) {
        return false;
    }
    let off: u32 = vec.len * vec.stride;
    copyBytes(&mut vec.data[off..off + vec.stride], @sliceOf(elem as &u8, vec.stride));
    let stride = vec.stride;
    let off: u32 = vec.len * stride;
    copyBytes(&mut vec.data[off..off + stride], @sliceOf(elem as &u8, stride));
    set vec.len += 1;

    return true;
}


/// Returns false if index is out of bounds.
export unsafe fn put(vec: &mut RawVec, index: u32, elem: &opaque) -> bool {
    if index >= vec.len {
        return false;
    }
    let off: u32 = index * vec.stride;
    copyBytes(&mut vec.data[off..off + vec.stride], @sliceOf(elem as &u8, vec.stride));
    let stride = vec.stride;
    let off: u32 = index * stride;
    copyBytes(&mut vec.data[off..off + stride], @sliceOf(elem as &u8, stride));

    return true;
}

/// Copy bytes from source to destination.

test/tests/mutref.loop.bug.rad +8 -4

/// merge tries to `load` through it as if it were a pointer.
fn testZeroIter(n: u32) -> u32 {
    let mut val: u32 = 42;
    let mut i: u32 = 0;
    while i < n {
        store(&mut val, val + 1);
        let next = val + 1;
        store(&mut val, next);
        set i += 1;
    }
    return val;
}

/// Multiple iterations: accumulate via &mut pointer in a loop.
fn testMultiIter() -> u32 {
    let mut acc: u32 = 0;
    let mut i: u32 = 0;
    while i < 5 {
        store(&mut acc, acc + i);
        let next = acc + i;
        store(&mut acc, next);
        set i += 1;
    }
    return acc;
}


fn testMultipleVars() -> u32 {
    let mut a: u32 = 0;
    let mut b: u32 = 100;
    let mut i: u32 = 0;
    while i < 3 {
        store(&mut a, a + 1);
        store(&mut b, b - 1);
        let nextA = a + 1;
        store(&mut a, nextA);
        let nextB = b - 1;
        store(&mut b, nextB);
        set i += 1;
    }
    return a + b;
}


924	924		precise: bool,
925	925		}
926	926
927	927		/// A reference binding that protects its source for one lexical scope.
928	928		record LocalLoan: Copy {
929		-	/// Local symbol through which the source can be accessed.
930		-	binding: *unsafe mut Symbol,
	929	+	/// Local symbol that provides access, or nil for a pending call argument.
	930	+	binding: ?*unsafe mut Symbol,
931	931		/// Storage retained by the reference.
932	932		place: BorrowPlace,
933	933		/// Whether other reads of the source are excluded.
934	934		exclusive: bool,
935	935		}

10272	10272		throw emitError(checker.resolver, node, ErrorKind::BorrowConflict(root.name));
10273	10273		}
10274	10274		}
10275	10275		for i in 0..checker.localLen {
10276	10276		let loan = checker.locals[i];
	10277	+	let mut throughBinding = false;
	10278	+	if let binding = loan.binding {
	10279	+	set throughBinding = usesLocalLoan(checker.resolver, node, binding);
	10280	+	}
10277	10281		if (exclusive or loan.exclusive) and placesOverlap(&place, &loan.place)
10278		-	and not usesLocalLoan(checker.resolver, node, loan.binding)
	10282	+	and not throughBinding
10279	10283		{
10280	10284		throw emitError(checker.resolver, node, ErrorKind::BorrowConflict(root.name));
10281	10285		}
10282	10286		}
10283	10287		}

10639	10643		checker: &mut LinearChecker 'arena 'checking,
10640	10644		env: &mut LinearEnv,
10641	10645		node: *ast::Node,
10642	10646		call: ast::Call,
10643	10647		) throws (ResolveError) where 'arena: 'checking {
	10648	+	let localStart = checker.localLen;
10644	10649		match checker.resolver.nodeData.entries[node.id].extra {
10645	10650		case NodeExtra::SliceAppend { .. }, NodeExtra::SliceDelete { .. } => {
10646	10651		let case ast::NodeValue::FieldAccess(access) = call.callee.value
10647	10652		else panic "slice mutation without receiver";
10648	10653		try checkPatternLoan(checker, access.parent);

10710	10715		set placesLen += 1;
10711	10716		}
10712	10717		}
10713	10718		if types::isReference(receiverClass) {
10714	10719		try checkLinearNode(checker, env, access.parent, LinearUse::Borrow);
	10720	+	if createsExplicitBorrow(access.parent) {
	10721	+	try retainCallLoan(checker, access.parent, receiverMutable);
	10722	+	}
10715	10723		} else if receiverClass == types::PointerClass::Owned {
10716	10724		try checkLinearNode(checker, env, access.parent, LinearUse::Consume);
10717	10725		}
10718	10726		}
10719	10727		}

10741	10749		if isBorrowedReferenceParameter(expected) {
10742	10750		try checkLinearNode(checker, env, arg, LinearUse::Borrow);
10743	10751		} else {
10744	10752		try checkLinearNode(checker, env, arg, LinearUse::Consume);
10745	10753		}
	10754	+	if isRefType(expected) and createsExplicitBorrow(arg) {
	10755	+	try retainCallLoan(checker, arg, argExclusive);
	10756	+	}
10746	10757		}
	10758	+	set checker.localLen = localStart;
10747	10759		if *info.returnType == Type::Never and info.throwList.len == 0 {
10748	10760		set env.terminated = true;
10749	10761		}
10750	10762		}
10751	10763
	10764	+	/// Return whether evaluating an argument creates an explicit address borrow.
	10765	+	fn createsExplicitBorrow(node: *ast::Node) -> bool {
	10766	+	match node.value {
	10767	+	case ast::NodeValue::AddressOf(_) => return true,
	10768	+	case ast::NodeValue::As(cast) => return createsExplicitBorrow(cast.value),
	10769	+	case ast::NodeValue::RegionApply { value, .. } => return createsExplicitBorrow(value),
	10770	+	else => return false,
	10771	+	}
	10772	+	}
	10773	+
	10774	+	/// Protect explicit address arguments until their call begins.
	10775	+	unsafe fn retainCallLoan 'arena 'checking (
	10776	+	checker: &mut LinearChecker 'arena 'checking, node: *ast::Node, exclusive: bool
	10777	+	) throws (ResolveError) where 'arena: 'checking {
	10778	+	let place = borrowPlace(checker.resolver, node);
	10779	+	if place.root == nil {
	10780	+	return;
	10781	+	}
	10782	+	if checker.localLen >= MAX_LINEAR_BINDINGS {
	10783	+	throw emitError(checker.resolver, node, ErrorKind::Internal);
	10784	+	}
	10785	+	set checker.locals[checker.localLen] = LocalLoan { binding: nil, place, exclusive };
	10786	+	set checker.localLen += 1;
	10787	+	}
	10788	+
10752	10789		/// Check a pattern conditional. Linear scrutinees require an exhaustive match.
10753	10790		unsafe fn checkLinearIfLet 'arena 'checking (
10754	10791		checker: &mut LinearChecker 'arena 'checking,
10755	10792		env: &mut LinearEnv,
10756	10793		node: *ast::Node,

3	3		use std::mem;
4	4		use std::testing;
5	5		use std::lang::types;
6	6		use std::lang::resolver;
7	7
	8	+	/// Earlier reference arguments protect their storage during later arguments.
	9	+	@test unsafe fn testRegionalCallArgumentLoans() throws (testing::TestError) {
	10	+	for program in [
	11	+	"fn inner(p: &mut u32) -> u32 { set p = 2; return 0; } fn outer(p: &mut u32, n: u32) {} fn f 'r (p: &'r mut u32) { outer(&mut p, inner(p)); }",
	12	+	"fn inner(p: &mut u32) -> u32 { set p = 2; return 0; } fn outer(p: &u32, n: u32) {} fn f 'r (p: &'r mut u32) { outer(&p, inner(p)); }",
	13	+	"fn inner(p: &mut u32) -> u32 { set p = 2; return 0; } fn outer(p: &mut u32, n: u32) {} unsafe fn f 'r (p: &'r mut u32) { outer(&mut p, inner(p)); }",
	14	+	"record R { n: u32 } fn (r: &mut R) call(n: u32) {} fn inner(p: &mut u32) -> u32 { set p = 2; return 0; } fn f 'r (r: &'r mut R) { (&mut r).call(inner(&mut r.n)); }",
	15	+	] {
	16	+	let mut arena = super::testArena();
	17	+	let storage: 'test = &mut arena in {
	18	+	let mut res = super::testResolver(storage);
	19	+	let result = try super::resolveProgramStr(&mut res, program);
	20	+	let error = try super::expectError(&result);
	21	+	let case resolver::ErrorKind::BorrowConflict(_) = error.kind
	22	+	else throw testing::TestError::Failed;
	23	+	}
	24	+	}
	25	+	}
	26	+
	27	+	/// Call loans allow shared reads, separate fields, and access after the call.
	28	+	@test unsafe fn testRegionalCallArgumentLoanScopes() throws (testing::TestError) {
	29	+	for program in [
	30	+	"fn read(p: &u32) -> u32 { return p; } fn outer(p: &u32, n: u32) {} fn f 'r (p: &'r mut u32) { outer(&p, read(p)); set *p = 3; }",
	31	+	"record R { a: u32, b: u32 } fn inner(p: &mut u32) -> u32 { set *p = 2; return 0; } fn outer(p: &mut u32, n: u32) {} fn f 'r (r: &'r mut R) { outer(&mut r.a, inner(&mut r.b)); set r.a = 3; }",
	32	+	] {
	33	+	let mut arena = super::testArena();
	34	+	let storage: 'test = &mut arena in {
	35	+	let mut res = super::testResolver(storage);
	36	+	let result = try super::resolveProgramStr(&mut res, program);
	37	+	try super::expectNoErrors(&result);
	38	+	}
	39	+	}
	40	+	}
	41	+
8	42		/// Equal region spellings in separate functions have distinct identities.
9	43		@test unsafe fn testRegionIdentities() throws (testing::TestError) {
10	44		let mut testArena1 = super::testArena();
11	45		let testStorage1: 'test1 = &mut testArena1 in {
12	46		let mut res = super::testResolver(testStorage1);

65	65		/// Returns false if the vector is at capacity.
66	66		export unsafe fn push(vec: &mut RawVec, elem: &opaque) -> bool {
67	67		if vec.len >= capacity(vec) {
68	68		return false;
69	69		}
70		-	let off: u32 = vec.len * vec.stride;
71		-	copyBytes(&mut vec.data[off..off + vec.stride], @sliceOf(elem as &u8, vec.stride));
	70	+	let stride = vec.stride;
	71	+	let off: u32 = vec.len * stride;
	72	+	copyBytes(&mut vec.data[off..off + stride], @sliceOf(elem as &u8, stride));
72	73		set vec.len += 1;
73	74
74	75		return true;
75	76		}
76	77

95	96		/// Returns false if index is out of bounds.
96	97		export unsafe fn put(vec: &mut RawVec, index: u32, elem: &opaque) -> bool {
97	98		if index >= vec.len {
98	99		return false;
99	100		}
100		-	let off: u32 = index * vec.stride;
101		-	copyBytes(&mut vec.data[off..off + vec.stride], @sliceOf(elem as &u8, vec.stride));
	101	+	let stride = vec.stride;
	102	+	let off: u32 = index * stride;
	103	+	copyBytes(&mut vec.data[off..off + stride], @sliceOf(elem as &u8, stride));
102	104
103	105		return true;
104	106		}
105	107
106	108		/// Copy bytes from source to destination.

19	19		/// merge tries to `load` through it as if it were a pointer.
20	20		fn testZeroIter(n: u32) -> u32 {
21	21		let mut val: u32 = 42;
22	22		let mut i: u32 = 0;
23	23		while i < n {
24		-	store(&mut val, val + 1);
	24	+	let next = val + 1;
	25	+	store(&mut val, next);
25	26		set i += 1;
26	27		}
27	28		return val;
28	29		}
29	30
30	31		/// Multiple iterations: accumulate via &mut pointer in a loop.
31	32		fn testMultiIter() -> u32 {
32	33		let mut acc: u32 = 0;
33	34		let mut i: u32 = 0;
34	35		while i < 5 {
35		-	store(&mut acc, acc + i);
	36	+	let next = acc + i;
	37	+	store(&mut acc, next);
36	38		set i += 1;
37	39		}
38	40		return acc;
39	41		}
40	42

42	44		fn testMultipleVars() -> u32 {
43	45		let mut a: u32 = 0;
44	46		let mut b: u32 = 100;
45	47		let mut i: u32 = 0;
46	48		while i < 3 {
47		-	store(&mut a, a + 1);
48		-	store(&mut b, b - 1);
	49	+	let nextA = a + 1;
	50	+	store(&mut a, nextA);
	51	+	let nextB = b - 1;
	52	+	store(&mut b, nextB);
49	53		set i += 1;
50	54		}
51	55		return a + b;
52	56		}
53	57