radiance · commit

compiler: Initialize loan and loop checker scratch state

44c1050ddc2bbb7d4c41911ead751e9fa11a57bba518b9b96252e52bef5dd2c1

Alexis Sellier committed 6 days ago 1 parent ecf232b6

lib/std/lang/resolver.rad +51 -28

/// `enterLinearLoop` initializes each slot before it increases `loopDepth`.
record LinearChecker: 'arena + 'checking where 'arena: 'checking {
    /// Resolver that owns the symbols and diagnostics.
    resolver: &'checking mut Resolver 'arena,
    /// Regional projections discovered in this function.
    regional: [RegionalLoan; MAX_REGIONAL_LOANS],
    /// Number of initialized regional loan entries.
    regional: [?RegionalLoan; MAX_REGIONAL_LOANS],
    /// Number of active regional loan entries.
    regionalLen: u32,
    /// Named regions active at the current source location.
    regions: ?*RegionScope,
    /// Regional loans carried to each loop's next iteration.
    loopBackLoans: [u64; MAX_LINEAR_LOOP_DEPTH],

    loopExitLoans: [u64; MAX_LINEAR_LOOP_DEPTH],
    /// Regions active at each loop's entry and exit.
    loopRegions: [?*RegionScope; MAX_LINEAR_LOOP_DEPTH],
    /// Source places protected by active pattern references.
    loans: [BorrowPlace; MAX_LINEAR_BINDINGS],
    /// Number of initialized entries in `loans`.
    /// Number of active entries in `loans`.
    loanLen: u32,
    /// Reference locals in active lexical scopes.
    locals: [LocalLoan; MAX_LINEAR_BINDINGS],
    /// Number of initialized local loans.
    /// Number of active local loans.
    localLen: u32,
    /// Binding count at entry to each active loop.
    loopMarks: [u32; MAX_LINEAR_LOOP_DEPTH],
    /// Available bindings at entry to each active loop.
    loopAvailable: [u64; MAX_LINEAR_LOOP_DEPTH],

    for stmt in block.statements {
        try visitDecl(res, stmt);
    }
}

/// Create a place with no storage root or field projections.
fn emptyBorrowPlace() -> BorrowPlace {
    return BorrowPlace { root: nil, fields: [0; MAX_BORROW_FIELDS], len: 0, precise: true };
}

/// Create initialized loan and loop scratch state for one function.
fn linearChecker 'arena 'checking (
    resolver: &'checking mut Resolver 'arena, regions: ?*RegionScope
) -> LinearChecker 'arena 'checking where 'arena: 'checking {
    let place = emptyBorrowPlace();
    return LinearChecker 'arena 'checking {
        resolver,
        regional: [nil; MAX_REGIONAL_LOANS],
        regionalLen: 0,
        regions,
        loopBackLoans: [0; MAX_LINEAR_LOOP_DEPTH],
        loopExitLoans: [0; MAX_LINEAR_LOOP_DEPTH],
        loopRegions: [nil; MAX_LINEAR_LOOP_DEPTH],
        loans: [place; MAX_LINEAR_BINDINGS],
        loanLen: 0,
        locals: [LocalLoan { binding: nil, place, exclusive: false }; MAX_LINEAR_BINDINGS],
        localLen: 0,
        loopMarks: [0; MAX_LINEAR_LOOP_DEPTH],
        loopAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
        loopExitAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
        loopHasNaturalExit: [false; MAX_LINEAR_LOOP_DEPTH],
        loopBreakSeen: [false; MAX_LINEAR_LOOP_DEPTH],
        loopDepth: 0,
    };
}

/// Create an empty ownership environment with initialized binding slots.
fn linearEnv() -> LinearEnv {
    return LinearEnv {
        regionalLoans: 0,
        symbols: [nil; MAX_LINEAR_BINDINGS],

    place: BorrowPlace,
    /// Whether accesses through other references are excluded.
    exclusive: bool,
}

/// Read an initialized regional loan from the active prefix.
fn regionalLoan 'arena 'checking (
    checker: &LinearChecker 'arena 'checking, index: u32
) -> RegionalLoan where 'arena: 'checking {
    assert index < checker.regionalLen, "regionalLoan: index outside active prefix";
    let loan = checker.regional[index] else panic "regionalLoan: missing active loan";
    return loan;
}

/// Return whether a region identity is visible in a lexical environment.
fn regionInScope(scope: ?*RegionScope, regionId: u32) -> bool {
    let mut cursor = scope;
    while let current = cursor {
        if regionIndex(current, regionId) <> nil {

/// Retain only loans whose regions remain active at a control-flow destination.
fn regionalLoansInScope 'arena 'checking (checker: &LinearChecker 'arena 'checking, mask: u64, scope: ?*RegionScope) -> u64 where 'arena: 'checking {
    let mut result: u64 = 0;
    for i in 0..checker.regionalLen {
        let bit = (1 as u64) << (i as u64);
        if (mask & bit) <> 0 and regionInScope(scope, checker.regional[i].regionId) {
        if (mask & bit) <> 0 and regionInScope(scope, regionalLoan(checker, i).regionId) {
            set result |= bit;
        }
    }
    return result;
}

) where 'arena: 'checking {
    let oldLen = checker.regionalLen;
    let mut mapping: [u64; MAX_REGIONAL_LOANS] = [0; MAX_REGIONAL_LOANS];
    let mut next: u32 = 0;
    for i in 0..oldLen {
        let loan = checker.regional[i];
        let loan = regionalLoan(checker, i);
        if regionInScope(scope, loan.regionId) {
            set checker.regional[next] = loan;
            set mapping[i] = (1 as u64) << (next as u64);
            set next += 1;
        }

    }
    let place = borrowPlace(checker.resolver, address.target);
    if place.root == nil {
        return;
    }
    for loan, i in &checker.regional[..checker.regionalLen] {
    for i in 0..checker.regionalLen {
        let loan = regionalLoan(checker, i);
        if loan.source.id == node.id {
            set env.regionalLoans |= (1 as u64) << (i as u64);
            return;
        }
    }

    return nil;
}

/// Resolve a place through reference locals without extending its storage lifetime.
unsafe fn borrowPlace 'arena (self: &mut Resolver 'arena, node: *ast::Node) -> BorrowPlace {
    let mut place = BorrowPlace { root: nil, fields: undefined, len: 0, precise: true };
    let mut place = emptyBorrowPlace();
    match node.value {
        case ast::NodeValue::Ident(_), ast::NodeValue::ScopeAccess(_) => {
            let sym = symbolFor(self, node) else return place;
            if let source = localReferenceSource(sym) {
                let origin = borrowPlace(self, source);

    let root = place.root else return;
    for i in 0..checker.regionalLen {
        if (env.regionalLoans & ((1 as u64) << (i as u64))) == 0 {
            continue;
        }
        let loan = checker.regional[i];
        let loan = regionalLoan(checker, i);
        if (exclusive or loan.exclusive) and placesOverlap(&place, &loan.place)
            and not usesRegionalLoan(checker.resolver, node, loan.source)
        {
            throw emitError(checker.resolver, node, ErrorKind::BorrowConflict(root.name));
        }

    body: *ast::Node,
) throws (ResolveError) {
    try resolveNominalApplications(self, body);
    let regions = self.regionScope;
    let resolved: 'checking = &mut *self where 'arena: 'checking in {
        let mut checker = LinearChecker 'arena 'checking {
            resolver: resolved,
            regional: undefined,
            regionalLen: 0,
            regions,
            loopBackLoans: undefined,
            loopExitLoans: undefined,
            loopRegions: undefined,
            loans: undefined,
            loanLen: 0,
            locals: undefined,
            localLen: 0,
            loopMarks: undefined,
            loopAvailable: undefined,
            loopExitAvailable: undefined,
            loopHasNaturalExit: undefined,
            loopBreakSeen: undefined,
            loopDepth: 0,
        };
        let mut checker = linearChecker(resolved, regions);
        let mut env = linearEnv();
        if let receiverNode = receiver {
            try addLinearBinding(&mut checker, &mut env, receiverNode);
        }
        for paramNode in params {

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

            try super::expectErrorKind(&result, resolver::ErrorKind::InvalidRefPosition);
        }
    }
}

/// Loan compaction preserves outer-region conflicts after child slots expire.
@test unsafe fn testRegionalLoanCompactionConflict() throws (testing::TestError) {
    for program in [
        "fn f 'r (p: &'r mut u32) { let value: u32 = 0; let child: 'child = &value where 'r: 'child in { let local = &*child; let retained = &*p; } set *p = 1; }",
        "fn f 'r (p: &'r mut u32) { let value: u32 = 0; loop { let child: 'child = &value where 'r: 'child in { let local = &*child; let retained = &*p; } break; } set *p = 1; }",
    ] {
        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;
        }
    }
}

/// Regional projection tracking limits simultaneous live projections.
@test unsafe fn testRegionalLoanCapacity() throws (testing::TestError) {
    let mut reuseArena = super::testArena();
    let reuseStorage: 'reuse = &mut reuseArena in {
        let mut res = super::testResolver(reuseStorage);

test/tests/regions.loan.scratch.rad added +103 -0

1	+	//! returns: 0
2	+
3	+	/// Retain every supported regional projection slot at once.
4	+	fn full 'r (p: &'r u32) -> u32 {
5	+	let refs: [&'r u32; 32] = [&p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p, &p];
6	+	let mut sum: u32 = 0;
7	+	for item in refs {
8	+	set sum += *item;
9	+	}
10	+	return sum;
11	+	}
12	+
13	+	/// Reuse child-region loans across loop exits and later iterations.
14	+	fn recycle() -> u32 {
15	+	let mut value: u32 = 0;
16	+	let outer: 'outer = &mut value in {
17	+	for i in 0..3 {
18	+	let inner: 'inner = &mut *outer in {
19	+	set *inner += 1;
20	+	}
21	+	if i == 1 { continue; }
22	+	let read: 'read = &*outer in {
23	+	assert *read == i + 1;
24	+	}
25	+	}
26	+	loop {
27	+	let inner: 'last = &mut *outer in {
28	+	set *inner += 1;
29	+	}
30	+	break;
31	+	}
32	+	set *outer += 1;
33	+	}
34	+	return value;
35	+	}
36	+
37	+	/// Initialize and unwind every supported nested loop slot.
38	+	fn nested() -> u32 {
39	+	let mut value: u32 = 0;
40	+	loop {
41	+	loop {
42	+	loop {
43	+	loop {
44	+	loop {
45	+	loop {
46	+	loop {
47	+	loop {
48	+	loop {
49	+	loop {
50	+	loop {
51	+	loop {
52	+	loop {
53	+	loop {
54	+	loop {
55	+	loop {
56	+	let p: 'value = &mut value in {
57	+	set *p = 9;
58	+	}
59	+	break;
60	+	}
61	+	break;
62	+	}
63	+	break;
64	+	}
65	+	break;
66	+	}
67	+	break;
68	+	}
69	+	break;
70	+	}
71	+	break;
72	+	}
73	+	break;
74	+	}
75	+	break;
76	+	}
77	+	break;
78	+	}
79	+	break;
80	+	}
81	+	break;
82	+	}
83	+	break;
84	+	}
85	+	break;
86	+	}
87	+	break;
88	+	}
89	+	break;
90	+	}
91	+	return value;
92	+	}
93	+
94	+	/// Execute full and reused loan tables with fresh checker state per function.
95	+	@default fn main() -> u32 {
96	+	let value: u32 = 2;
97	+	let p: 'value = &value in {
98	+	assert full(p) == 64;
99	+	}
100	+	assert recycle() == 5;
101	+	assert nested() == 9;
102	+	return 0;
103	+	}

978	978		/// `enterLinearLoop` initializes each slot before it increases `loopDepth`.
979	979		record LinearChecker: 'arena + 'checking where 'arena: 'checking {
980	980		/// Resolver that owns the symbols and diagnostics.
981	981		resolver: &'checking mut Resolver 'arena,
982	982		/// Regional projections discovered in this function.
983		-	regional: [RegionalLoan; MAX_REGIONAL_LOANS],
984		-	/// Number of initialized regional loan entries.
	983	+	regional: [?RegionalLoan; MAX_REGIONAL_LOANS],
	984	+	/// Number of active regional loan entries.
985	985		regionalLen: u32,
986	986		/// Named regions active at the current source location.
987	987		regions: ?*RegionScope,
988	988		/// Regional loans carried to each loop's next iteration.
989	989		loopBackLoans: [u64; MAX_LINEAR_LOOP_DEPTH],

991	991		loopExitLoans: [u64; MAX_LINEAR_LOOP_DEPTH],
992	992		/// Regions active at each loop's entry and exit.
993	993		loopRegions: [?*RegionScope; MAX_LINEAR_LOOP_DEPTH],
994	994		/// Source places protected by active pattern references.
995	995		loans: [BorrowPlace; MAX_LINEAR_BINDINGS],
996		-	/// Number of initialized entries in `loans`.
	996	+	/// Number of active entries in `loans`.
997	997		loanLen: u32,
998	998		/// Reference locals in active lexical scopes.
999	999		locals: [LocalLoan; MAX_LINEAR_BINDINGS],
1000		-	/// Number of initialized local loans.
	1000	+	/// Number of active local loans.
1001	1001		localLen: u32,
1002	1002		/// Binding count at entry to each active loop.
1003	1003		loopMarks: [u32; MAX_LINEAR_LOOP_DEPTH],
1004	1004		/// Available bindings at entry to each active loop.
1005	1005		loopAvailable: [u64; MAX_LINEAR_LOOP_DEPTH],

10006	10006		for stmt in block.statements {
10007	10007		try visitDecl(res, stmt);
10008	10008		}
10009	10009		}
10010	10010
	10011	+	/// Create a place with no storage root or field projections.
	10012	+	fn emptyBorrowPlace() -> BorrowPlace {
	10013	+	return BorrowPlace { root: nil, fields: [0; MAX_BORROW_FIELDS], len: 0, precise: true };
	10014	+	}
	10015	+
	10016	+	/// Create initialized loan and loop scratch state for one function.
	10017	+	fn linearChecker 'arena 'checking (
	10018	+	resolver: &'checking mut Resolver 'arena, regions: ?*RegionScope
	10019	+	) -> LinearChecker 'arena 'checking where 'arena: 'checking {
	10020	+	let place = emptyBorrowPlace();
	10021	+	return LinearChecker 'arena 'checking {
	10022	+	resolver,
	10023	+	regional: [nil; MAX_REGIONAL_LOANS],
	10024	+	regionalLen: 0,
	10025	+	regions,
	10026	+	loopBackLoans: [0; MAX_LINEAR_LOOP_DEPTH],
	10027	+	loopExitLoans: [0; MAX_LINEAR_LOOP_DEPTH],
	10028	+	loopRegions: [nil; MAX_LINEAR_LOOP_DEPTH],
	10029	+	loans: [place; MAX_LINEAR_BINDINGS],
	10030	+	loanLen: 0,
	10031	+	locals: [LocalLoan { binding: nil, place, exclusive: false }; MAX_LINEAR_BINDINGS],
	10032	+	localLen: 0,
	10033	+	loopMarks: [0; MAX_LINEAR_LOOP_DEPTH],
	10034	+	loopAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
	10035	+	loopExitAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
	10036	+	loopHasNaturalExit: [false; MAX_LINEAR_LOOP_DEPTH],
	10037	+	loopBreakSeen: [false; MAX_LINEAR_LOOP_DEPTH],
	10038	+	loopDepth: 0,
	10039	+	};
	10040	+	}
	10041	+
10011	10042		/// Create an empty ownership environment with initialized binding slots.
10012	10043		fn linearEnv() -> LinearEnv {
10013	10044		return LinearEnv {
10014	10045		regionalLoans: 0,
10015	10046		symbols: [nil; MAX_LINEAR_BINDINGS],

10209	10240		place: BorrowPlace,
10210	10241		/// Whether accesses through other references are excluded.
10211	10242		exclusive: bool,
10212	10243		}
10213	10244
	10245	+	/// Read an initialized regional loan from the active prefix.
	10246	+	fn regionalLoan 'arena 'checking (
	10247	+	checker: &LinearChecker 'arena 'checking, index: u32
	10248	+	) -> RegionalLoan where 'arena: 'checking {
	10249	+	assert index < checker.regionalLen, "regionalLoan: index outside active prefix";
	10250	+	let loan = checker.regional[index] else panic "regionalLoan: missing active loan";
	10251	+	return loan;
	10252	+	}
	10253	+
10214	10254		/// Return whether a region identity is visible in a lexical environment.
10215	10255		fn regionInScope(scope: ?*RegionScope, regionId: u32) -> bool {
10216	10256		let mut cursor = scope;
10217	10257		while let current = cursor {
10218	10258		if regionIndex(current, regionId) <> nil {

10226	10266		/// Retain only loans whose regions remain active at a control-flow destination.
10227	10267		fn regionalLoansInScope 'arena 'checking (checker: &LinearChecker 'arena 'checking, mask: u64, scope: ?*RegionScope) -> u64 where 'arena: 'checking {
10228	10268		let mut result: u64 = 0;
10229	10269		for i in 0..checker.regionalLen {
10230	10270		let bit = (1 as u64) << (i as u64);
10231		-	if (mask & bit) <> 0 and regionInScope(scope, checker.regional[i].regionId) {
	10271	+	if (mask & bit) <> 0 and regionInScope(scope, regionalLoan(checker, i).regionId) {
10232	10272		set result \|= bit;
10233	10273		}
10234	10274		}
10235	10275		return result;
10236	10276		}

10253	10293		) where 'arena: 'checking {
10254	10294		let oldLen = checker.regionalLen;
10255	10295		let mut mapping: [u64; MAX_REGIONAL_LOANS] = [0; MAX_REGIONAL_LOANS];
10256	10296		let mut next: u32 = 0;
10257	10297		for i in 0..oldLen {
10258		-	let loan = checker.regional[i];
	10298	+	let loan = regionalLoan(checker, i);
10259	10299		if regionInScope(scope, loan.regionId) {
10260	10300		set checker.regional[next] = loan;
10261	10301		set mapping[i] = (1 as u64) << (next as u64);
10262	10302		set next += 1;
10263	10303		}

10300	10340		}
10301	10341		let place = borrowPlace(checker.resolver, address.target);
10302	10342		if place.root == nil {
10303	10343		return;
10304	10344		}
10305		-	for loan, i in &checker.regional[..checker.regionalLen] {
	10345	+	for i in 0..checker.regionalLen {
	10346	+	let loan = regionalLoan(checker, i);
10306	10347		if loan.source.id == node.id {
10307	10348		set env.regionalLoans \|= (1 as u64) << (i as u64);
10308	10349		return;
10309	10350		}
10310	10351		}

10351	10392		return nil;
10352	10393		}
10353	10394
10354	10395		/// Resolve a place through reference locals without extending its storage lifetime.
10355	10396		unsafe fn borrowPlace 'arena (self: &mut Resolver 'arena, node: *ast::Node) -> BorrowPlace {
10356		-	let mut place = BorrowPlace { root: nil, fields: undefined, len: 0, precise: true };
	10397	+	let mut place = emptyBorrowPlace();
10357	10398		match node.value {
10358	10399		case ast::NodeValue::Ident(_), ast::NodeValue::ScopeAccess(_) => {
10359	10400		let sym = symbolFor(self, node) else return place;
10360	10401		if let source = localReferenceSource(sym) {
10361	10402		let origin = borrowPlace(self, source);

10439	10480		let root = place.root else return;
10440	10481		for i in 0..checker.regionalLen {
10441	10482		if (env.regionalLoans & ((1 as u64) << (i as u64))) == 0 {
10442	10483		continue;
10443	10484		}
10444		-	let loan = checker.regional[i];
	10485	+	let loan = regionalLoan(checker, i);
10445	10486		if (exclusive or loan.exclusive) and placesOverlap(&place, &loan.place)
10446	10487		and not usesRegionalLoan(checker.resolver, node, loan.source)
10447	10488		{
10448	10489		throw emitError(checker.resolver, node, ErrorKind::BorrowConflict(root.name));
10449	10490		}

11643	11684		body: *ast::Node,
11644	11685		) throws (ResolveError) {
11645	11686		try resolveNominalApplications(self, body);
11646	11687		let regions = self.regionScope;
11647	11688		let resolved: 'checking = &mut *self where 'arena: 'checking in {
11648		-	let mut checker = LinearChecker 'arena 'checking {
11649		-	resolver: resolved,
11650		-	regional: undefined,
11651		-	regionalLen: 0,
11652		-	regions,
11653		-	loopBackLoans: undefined,
11654		-	loopExitLoans: undefined,
11655		-	loopRegions: undefined,
11656		-	loans: undefined,
11657		-	loanLen: 0,
11658		-	locals: undefined,
11659		-	localLen: 0,
11660		-	loopMarks: undefined,
11661		-	loopAvailable: undefined,
11662		-	loopExitAvailable: undefined,
11663		-	loopHasNaturalExit: undefined,
11664		-	loopBreakSeen: undefined,
11665		-	loopDepth: 0,
11666		-	};
	11689	+	let mut checker = linearChecker(resolved, regions);
11667	11690		let mut env = linearEnv();
11668	11691		if let receiverNode = receiver {
11669	11692		try addLinearBinding(&mut checker, &mut env, receiverNode);
11670	11693		}
11671	11694		for paramNode in params {

1066	1066		try super::expectErrorKind(&result, resolver::ErrorKind::InvalidRefPosition);
1067	1067		}
1068	1068		}
1069	1069		}
1070	1070
	1071	+	/// Loan compaction preserves outer-region conflicts after child slots expire.
	1072	+	@test unsafe fn testRegionalLoanCompactionConflict() throws (testing::TestError) {
	1073	+	for program in [
	1074	+	"fn f 'r (p: &'r mut u32) { let value: u32 = 0; let child: 'child = &value where 'r: 'child in { let local = &child; let retained = &p; } set *p = 1; }",
	1075	+	"fn f 'r (p: &'r mut u32) { let value: u32 = 0; loop { let child: 'child = &value where 'r: 'child in { let local = &child; let retained = &p; } break; } set *p = 1; }",
	1076	+	] {
	1077	+	let mut arena = super::testArena();
	1078	+	let storage: 'test = &mut arena in {
	1079	+	let mut res = super::testResolver(storage);
	1080	+	let result = try super::resolveProgramStr(&mut res, program);
	1081	+	let error = try super::expectError(&result);
	1082	+	let case resolver::ErrorKind::BorrowConflict(_) = error.kind else throw testing::TestError::Failed;
	1083	+	}
	1084	+	}
	1085	+	}
	1086	+
1071	1087		/// Regional projection tracking limits simultaneous live projections.
1072	1088		@test unsafe fn testRegionalLoanCapacity() throws (testing::TestError) {
1073	1089		let mut reuseArena = super::testArena();
1074	1090		let reuseStorage: 'reuse = &mut reuseArena in {
1075	1091		let mut res = super::testResolver(reuseStorage);