radiance · commit

compiler: Index exact nominal region applications

b7d3a9567cda99a7374d7826d55e075e7f0da8f9a4a04d548f52f8502fe203db

Alexis Sellier committed 6 days ago 1 parent 5db493fa

lib/std/lang/resolver.rad +27 -4

/// Maximum number of diagnostics recorded.
export constant MAX_ERRORS: u32 = 64;

/// Power-of-two bucket count for interned type lookup chains.
constant TYPE_BUCKETS: u32 = 1024;
/// Odd multiplier that combines type cache key components.
/// Power-of-two bucket count for exact nominal application lookup chains.
constant APPLICATION_BUCKETS: u32 = 1024;
/// Odd multiplier that combines cache key components.
constant CACHE_HASH_PRIME: u32 = 16777619;

/// Synthetic function name used when wrapping a bare expression for analysis.
export constant ANALYZE_EXPR_FN_NAME: *[u8] = "__expr__";
/// Synthetic function name used when wrapping a block for analysis.

    arguments: *unsafe [*unsafe types::Region],
    /// Stable descriptor for the substituted field or variant view.
    view: *unsafe mut NominalType,
    /// Next application in the resolver cache.
    next: ?*unsafe NominalApplication,
    /// Next application in the same lookup bucket.
    bucketNext: ?*unsafe NominalApplication,
}

/// Global resolver state.
export record Resolver: 'arena {
    /// Number of symbol identities allocated by this resolver.

    regionScope: ?*RegionScope,
    /// Interned applications of nominal region parameters.
    applications: ?*unsafe NominalApplication,
    /// First entry in the fully resolved suffix of the application list.
    completedApplications: ?*unsafe NominalApplication,
    /// Exact application lookup chains, backed by the resolver arena.
    applicationBuckets: *unsafe mut [?*unsafe NominalApplication],
    /// Current scope.
    scope: *unsafe mut Scope,
    /// Package scope containing package roots and top-level symbols.
    pkgScope: *unsafe mut Scope,
    /// Stack of loop contexts for nested loops.


/// Intern an exact nominal application before resolving its recursive members.
unsafe fn internNominalApplication 'arena (
    self: &mut Resolver 'arena, base: *unsafe NominalType, map: &RegionSubstitution
) -> *unsafe mut NominalType {
    let mut cursor = self.applications;
    let mut hash = addressHash(base as u64);
    for argument in map.arguments {
        let region = argument else panic "internNominalApplication: incomplete map";
        set hash = (hash ^ region.id) * CACHE_HASH_PRIME;
    }
    let bucket = hash & (APPLICATION_BUCKETS - 1);
    let mut cursor = self.applicationBuckets[bucket];
    while let applied = cursor {
        if applied.base == base {
            let mut same = true;
            for argument, i in applied.arguments {
                let other = map.arguments[i] else panic "internNominalApplication: missing argument";

            }
            if same {
                return applied.view;
            }
        }
        set cursor = applied.next;
        set cursor = applied.bucketNext;
    }
    let arguments = try! alloc::allocRawSlice(
        self.arena, @sizeOf(*unsafe types::Region), @alignOf(*unsafe types::Region), map.arguments.len
    ) as *unsafe mut [*unsafe types::Region];
    for argument, i in map.arguments {

    }
    let entry = try! alloc::allocRaw(
        self.arena, @sizeOf(NominalApplication), @alignOf(NominalApplication)
    ) as *unsafe mut NominalApplication;
    let view = allocNominalType(self, NominalType::Application(entry));
    set *entry = NominalApplication { base, parameters: map.parameters, arguments, view, next: self.applications };
    set *entry = NominalApplication {
        base, parameters: map.parameters, arguments, view,
        next: self.applications, bucketNext: self.applicationBuckets[bucket],
    };
    set self.applications = entry;
    set self.applicationBuckets[bucket] = entry;
    return view;
}

/// Check explicit region arguments and intern the applied nominal type.
unsafe fn applyNominalRegions 'arena (

    arena: &'arena mut alloc::Arena,
    storage: ResolverStorage,
    config: Config
) -> Resolver 'arena {
    let case ResolverStorage { nodeData, pkgScope, errors } = storage else panic "expected resolver storage";
    let applicationBuckets = try! alloc::allocRawSlice(
        arena, @sizeOf(?*unsafe NominalApplication), @alignOf(?*unsafe NominalApplication), APPLICATION_BUCKETS
    ) as *unsafe mut [?*unsafe NominalApplication];
    for i in 0..applicationBuckets.len {
        set applicationBuckets[i] = nil;
    }
    let types = try! alloc::allocRawSlice(
        arena, @sizeOf(?*TypeNode), @alignOf(?*TypeNode), TYPE_BUCKETS
    ) as *unsafe mut [?*TypeNode];
    for i in 0..types.len {
        set types[i] = nil;

    return Resolver 'arena {
        symbolCount: 0,
        regionScope: nil,
        applications: nil,
        completedApplications: nil,
        applicationBuckets,
        scope: pkgScope,
        pkgScope: pkgScope,
        loopStack: undefined,
        loopDepth: 0,
        currentFn: nil,

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

            try super::expectNoErrors(&result);
        }
    }
}

/// Exact application keys include the base and the ordered region arguments.
@test unsafe fn testNominalApplicationKeys() throws (testing::TestError) {
    let mut arena = super::testArena();
    let storage: 'test = &mut arena in {
        let mut res = super::testResolver(storage);
        let result = try super::resolveProgramStr(&mut res,
            "record N: 'r + 's + Copy { value: u32 } record M: 'r + 's + Copy { value: u32 } fn f 'a 'b (x: N 'a 'b, y: N 'a 'b, z: N 'b 'a, w: N 'a 'a, v: M 'a 'b) {}"
        );
        try super::expectNoErrors(&result);
        let func = try super::getBlockStmt(result.root, 2);
        let ty = resolver::typeFor(&res, func) else throw testing::TestError::Failed;
        let case resolver::Type::Fn(info) = ty else throw testing::TestError::Failed;
        for param, i in info.paramTypes {
            for other, j in info.paramTypes {
                assert (param == other) == (i == j or (i < 2 and j < 2));
            }
        }
        let mut count: u32 = 0;
        let mut cursor = res.applications;
        while let entry = cursor {
            assert entry.arguments.len == 2;
            assert resolver::nominalApplication(entry.view) == entry;
            set count += 1;
            set cursor = entry.next;
        }
        assert count == 4;
    }
}

/// Exact arguments share one descriptor and all applications share the source layout.
@test unsafe fn testNominalRegionApplications() throws (testing::TestError) {
    let mut testArena19 = super::testArena();
    let testStorage19: 'test19 = &mut testArena19 in {
        let mut res = super::testResolver(testStorage19);

test/tests/regions.nominal.cache.rad added +97 -0

1	+	//! returns: 0
2	+
3	+	/// Adjacent swaps and rotation produce all 120 region argument permutations.
4	+	record Node: 'a + 'b + 'c + 'd + 'e + Copy {
5	+	/// Link with rotated region arguments.
6	+	rotated: ?*Node 'b 'c 'd 'e 'a,
7	+	/// Link with the first two region arguments exchanged.
8	+	swapped: ?*Node 'b 'a 'c 'd 'e,
9	+	/// Value retained across all applications.
10	+	value: u32,
11	+	}
12	+
13	+	/// Read through a distinct set of five region identities.
14	+	fn read0 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
15	+	assert node.rotated == nil;
16	+	assert node.swapped == nil;
17	+	return node.value;
18	+	}
19	+
20	+	/// Read through a distinct set of five region identities.
21	+	fn read1 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
22	+	assert node.rotated == nil;
23	+	assert node.swapped == nil;
24	+	return node.value;
25	+	}
26	+
27	+	/// Read through a distinct set of five region identities.
28	+	fn read2 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
29	+	assert node.rotated == nil;
30	+	assert node.swapped == nil;
31	+	return node.value;
32	+	}
33	+
34	+	/// Read through a distinct set of five region identities.
35	+	fn read3 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
36	+	assert node.rotated == nil;
37	+	assert node.swapped == nil;
38	+	return node.value;
39	+	}
40	+
41	+	/// Read through a distinct set of five region identities.
42	+	fn read4 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
43	+	assert node.rotated == nil;
44	+	assert node.swapped == nil;
45	+	return node.value;
46	+	}
47	+
48	+	/// Read through a distinct set of five region identities.
49	+	fn read5 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
50	+	assert node.rotated == nil;
51	+	assert node.swapped == nil;
52	+	return node.value;
53	+	}
54	+
55	+	/// Read through a distinct set of five region identities.
56	+	fn read6 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
57	+	assert node.rotated == nil;
58	+	assert node.swapped == nil;
59	+	return node.value;
60	+	}
61	+
62	+	/// Read through a distinct set of five region identities.
63	+	fn read7 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
64	+	assert node.rotated == nil;
65	+	assert node.swapped == nil;
66	+	return node.value;
67	+	}
68	+
69	+	/// Read through a distinct set of five region identities.
70	+	fn read8 'a 'b 'c 'd 'e (node: Node 'a 'b 'c 'd 'e) -> u32 {
71	+	assert node.rotated == nil;
72	+	assert node.swapped == nil;
73	+	return node.value;
74	+	}
75	+
76	+	/// Resolve more exact applications than the cache has buckets.
77	+	fn check 'a 'b 'c 'd 'e (a: &'a u32, b: &'b u32, c: &'c u32, d: &'d u32, e: &'e u32) {
78	+	let node = Node 'a 'b 'c 'd 'e { rotated: nil, swapped: nil, value: 42 };
79	+	assert read0(node) == 42;
80	+	assert read1(node) == 42;
81	+	assert read2(node) == 42;
82	+	assert read3(node) == 42;
83	+	assert read4(node) == 42;
84	+	assert read5(node) == 42;
85	+	assert read6(node) == 42;
86	+	assert read7(node) == 42;
87	+	assert read8(node) == 42;
88	+	}
89	+
90	+	/// Execute the cache collision workload with live region arguments.
91	+	@default fn main() -> u32 {
92	+	let value: u32 = 0;
93	+	let p: 'r = &value in {
94	+	check(p, p, p, p, p);
95	+	}
96	+	return 0;
97	+	}

1056	1058		arguments: unsafe [unsafe types::Region],
1057	1059		/// Stable descriptor for the substituted field or variant view.
1058	1060		view: *unsafe mut NominalType,
1059	1061		/// Next application in the resolver cache.
1060	1062		next: ?*unsafe NominalApplication,
	1063	+	/// Next application in the same lookup bucket.
	1064	+	bucketNext: ?*unsafe NominalApplication,
1061	1065		}
1062	1066
1063	1067		/// Global resolver state.
1064	1068		export record Resolver: 'arena {
1065	1069		/// Number of symbol identities allocated by this resolver.

1068	1072		regionScope: ?*RegionScope,
1069	1073		/// Interned applications of nominal region parameters.
1070	1074		applications: ?*unsafe NominalApplication,
1071	1075		/// First entry in the fully resolved suffix of the application list.
1072	1076		completedApplications: ?*unsafe NominalApplication,
	1077	+	/// Exact application lookup chains, backed by the resolver arena.
	1078	+	applicationBuckets: unsafe mut [?unsafe NominalApplication],
1073	1079		/// Current scope.
1074	1080		scope: *unsafe mut Scope,
1075	1081		/// Package scope containing package roots and top-level symbols.
1076	1082		pkgScope: *unsafe mut Scope,
1077	1083		/// Stack of loop contexts for nested loops.

1359	1365
1360	1366		/// Intern an exact nominal application before resolving its recursive members.
1361	1367		unsafe fn internNominalApplication 'arena (
1362	1368		self: &mut Resolver 'arena, base: *unsafe NominalType, map: &RegionSubstitution
1363	1369		) -> *unsafe mut NominalType {
1364		-	let mut cursor = self.applications;
	1370	+	let mut hash = addressHash(base as u64);
	1371	+	for argument in map.arguments {
	1372	+	let region = argument else panic "internNominalApplication: incomplete map";
	1373	+	set hash = (hash ^ region.id) * CACHE_HASH_PRIME;
	1374	+	}
	1375	+	let bucket = hash & (APPLICATION_BUCKETS - 1);
	1376	+	let mut cursor = self.applicationBuckets[bucket];
1365	1377		while let applied = cursor {
1366	1378		if applied.base == base {
1367	1379		let mut same = true;
1368	1380		for argument, i in applied.arguments {
1369	1381		let other = map.arguments[i] else panic "internNominalApplication: missing argument";

1374	1386		}
1375	1387		if same {
1376	1388		return applied.view;
1377	1389		}
1378	1390		}
1379		-	set cursor = applied.next;
	1391	+	set cursor = applied.bucketNext;
1380	1392		}
1381	1393		let arguments = try! alloc::allocRawSlice(
1382	1394		self.arena, @sizeOf(unsafe types::Region), @alignOf(unsafe types::Region), map.arguments.len
1383	1395		) as unsafe mut [unsafe types::Region];
1384	1396		for argument, i in map.arguments {

1387	1399		}
1388	1400		let entry = try! alloc::allocRaw(
1389	1401		self.arena, @sizeOf(NominalApplication), @alignOf(NominalApplication)
1390	1402		) as *unsafe mut NominalApplication;
1391	1403		let view = allocNominalType(self, NominalType::Application(entry));
1392		-	set *entry = NominalApplication { base, parameters: map.parameters, arguments, view, next: self.applications };
	1404	+	set *entry = NominalApplication {
	1405	+	base, parameters: map.parameters, arguments, view,
	1406	+	next: self.applications, bucketNext: self.applicationBuckets[bucket],
	1407	+	};
1393	1408		set self.applications = entry;
	1409	+	set self.applicationBuckets[bucket] = entry;
1394	1410		return view;
1395	1411		}
1396	1412
1397	1413		/// Check explicit region arguments and intern the applied nominal type.
1398	1414		unsafe fn applyNominalRegions 'arena (

24	24		/// Maximum number of diagnostics recorded.
25	25		export constant MAX_ERRORS: u32 = 64;
26	26
27	27		/// Power-of-two bucket count for interned type lookup chains.
28	28		constant TYPE_BUCKETS: u32 = 1024;
29		-	/// Odd multiplier that combines type cache key components.
	29	+	/// Power-of-two bucket count for exact nominal application lookup chains.
	30	+	constant APPLICATION_BUCKETS: u32 = 1024;
	31	+	/// Odd multiplier that combines cache key components.
30	32		constant CACHE_HASH_PRIME: u32 = 16777619;
31	33
32	34		/// Synthetic function name used when wrapping a bare expression for analysis.
33	35		export constant ANALYZE_EXPR_FN_NAME: *[u8] = "__expr__";
34	36		/// Synthetic function name used when wrapping a block for analysis.

1557	1573		arena: &'arena mut alloc::Arena,
1558	1574		storage: ResolverStorage,
1559	1575		config: Config
1560	1576		) -> Resolver 'arena {
1561	1577		let case ResolverStorage { nodeData, pkgScope, errors } = storage else panic "expected resolver storage";
	1578	+	let applicationBuckets = try! alloc::allocRawSlice(
	1579	+	arena, @sizeOf(?unsafe NominalApplication), @alignOf(?unsafe NominalApplication), APPLICATION_BUCKETS
	1580	+	) as unsafe mut [?unsafe NominalApplication];
	1581	+	for i in 0..applicationBuckets.len {
	1582	+	set applicationBuckets[i] = nil;
	1583	+	}
1562	1584		let types = try! alloc::allocRawSlice(
1563	1585		arena, @sizeOf(?TypeNode), @alignOf(?TypeNode), TYPE_BUCKETS
1564	1586		) as unsafe mut [?TypeNode];
1565	1587		for i in 0..types.len {
1566	1588		set types[i] = nil;

1601	1623		return Resolver 'arena {
1602	1624		symbolCount: 0,
1603	1625		regionScope: nil,
1604	1626		applications: nil,
1605	1627		completedApplications: nil,
	1628	+	applicationBuckets,
1606	1629		scope: pkgScope,
1607	1630		pkgScope: pkgScope,
1608	1631		loopStack: undefined,
1609	1632		loopDepth: 0,
1610	1633		currentFn: nil,

609	609		try super::expectNoErrors(&result);
610	610		}
611	611		}
612	612		}
613	613
	614	+	/// Exact application keys include the base and the ordered region arguments.
	615	+	@test unsafe fn testNominalApplicationKeys() throws (testing::TestError) {
	616	+	let mut arena = super::testArena();
	617	+	let storage: 'test = &mut arena in {
	618	+	let mut res = super::testResolver(storage);
	619	+	let result = try super::resolveProgramStr(&mut res,
	620	+	"record N: 'r + 's + Copy { value: u32 } record M: 'r + 's + Copy { value: u32 } fn f 'a 'b (x: N 'a 'b, y: N 'a 'b, z: N 'b 'a, w: N 'a 'a, v: M 'a 'b) {}"
	621	+	);
	622	+	try super::expectNoErrors(&result);
	623	+	let func = try super::getBlockStmt(result.root, 2);
	624	+	let ty = resolver::typeFor(&res, func) else throw testing::TestError::Failed;
	625	+	let case resolver::Type::Fn(info) = ty else throw testing::TestError::Failed;
	626	+	for param, i in info.paramTypes {
	627	+	for other, j in info.paramTypes {
	628	+	assert (param == other) == (i == j or (i < 2 and j < 2));
	629	+	}
	630	+	}
	631	+	let mut count: u32 = 0;
	632	+	let mut cursor = res.applications;
	633	+	while let entry = cursor {
	634	+	assert entry.arguments.len == 2;
	635	+	assert resolver::nominalApplication(entry.view) == entry;
	636	+	set count += 1;
	637	+	set cursor = entry.next;
	638	+	}
	639	+	assert count == 4;
	640	+	}
	641	+	}
	642	+
614	643		/// Exact arguments share one descriptor and all applications share the source layout.
615	644		@test unsafe fn testNominalRegionApplications() throws (testing::TestError) {
616	645		let mut testArena19 = super::testArena();
617	646		let testStorage19: 'test19 = &mut testArena19 in {
618	647		let mut res = super::testResolver(testStorage19);