radiance · commit

compiler: Index interned types by active fields

5db493faf3660904b5e1c56f08be422bdbcab4c32169ec63ca88b0f1e4991ffe

Alexis Sellier committed 7 days ago 1 parent 1de5c499

lib/std/lang/resolver.rad +66 -7

use std::lang::module;

/// 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.
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.
export constant ANALYZE_BLOCK_FN_NAME: *[u8] = "__block__";


    config: Config,
    /// Caller-owned arena, valid for this resolver and all emitted metadata.
    arena: &'arena mut alloc::Arena,
    /// Combined semantic metadata table indexed by node ID.
    nodeData: NodeDataTable,
    /// Linked list of interned types.
    types: ?*TypeNode,
    /// Lookup chains for interned types.
    types: *unsafe mut [?*TypeNode],
    /// Diagnostics recorded so far.
    errors: DiagnosticBuffer,
    /// Stable module identities indexed by module ID.
    moduleEntries: [?*module::ModuleEntry; module::MAX_MODULES],
    /// Cache of module scopes indexed by module ID.

/// Internal error sentinel thrown when analysis cannot proceed.
export union ResolveError: Copy {
    Failure,
}

/// Node in the type interning linked list.
/// Node in a type interning lookup chain.
record TypeNode: Copy {
    /// Exact interned type value.
    ty: Type,
    /// Next type in the same lookup bucket.
    next: ?*TypeNode,
}

/// Look up a region name in a lexical environment.
unsafe fn findRegion(scope: ?*RegionScope, name: *[u8]) -> ?*unsafe mut types::Region {

    }
    set self.nodeData.entries[owner.id].extra = NodeExtra::Regions(frozen);
    return frozen;
}

/// Mix aligned metadata addresses into a lookup key.
fn addressHash(address: u64) -> u32 {
    return ((address >> 3) as u32) ^ ((address >> 35) as u32);
}

/// Hash the active fields of a pointer class.
unsafe fn classHash(class: types::PointerClass) -> u32 {
    match class {
        case types::PointerClass::Owned => return 1,
        case types::PointerClass::Ref => return 2,
        case types::PointerClass::Unsafe => return 3,
        case types::PointerClass::Region(region) => return addressHash(region as u64),
    }
}

/// Hash active type fields so equal values select the same lookup chain.
unsafe fn typeHash(ty: Type) -> u32 {
    match ty {
        case Type::Cell { class, payload } =>
            return addressHash(payload as u64) ^ (classHash(class) * CACHE_HASH_PRIME),
        case Type::Pointer { class, target, mutable } =>
            return addressHash(target as u64) ^ (classHash(class) * CACHE_HASH_PRIME) ^ (1 if mutable else 0),
        case Type::Slice { class, item, mutable } =>
            return addressHash(item as u64) ^ (classHash(class) * CACHE_HASH_PRIME) ^ (1 if mutable else 0),
        case Type::TraitObject { class, traitInfo, mutable } =>
            return addressHash(traitInfo as u64) ^ (classHash(class) * CACHE_HASH_PRIME) ^ (1 if mutable else 0),
        case Type::Session(region) => return addressHash(region as u64),
        case Type::Optional(inner) => return addressHash(inner as u64),
        case Type::Fn(info) => return addressHash(info as u64),
        case Type::Nominal(info) => return addressHash(info as u64),
        case Type::Array(array) => return addressHash(array.item as u64) ^ (array.length * CACHE_HASH_PRIME),
        case Type::Range { start, end } => {
            let mut hash: u32 = 0;
            if let item = start {
                set hash = addressHash(item as u64);
            }
            if let item = end {
                set hash = hash ^ (addressHash(item as u64) * CACHE_HASH_PRIME);
            }
            return hash;
        }
        else => return 0,
    }
}

/// Allocate and intern a type in the arena, returning a pointer for deduplication.
export unsafe fn allocType 'arena (self: &mut Resolver 'arena, ty: Type) -> *Type {
    // Search existing types for a match.
    let mut cursor = self.types;
    let bucket = typeHash(ty) & (TYPE_BUCKETS - 1);
    let mut cursor = self.types[bucket];
    while let node = cursor {
        if node.ty == ty {
            return &node.ty;
        }
        set cursor = node.next;

    // Allocate a new type node from the arena.
    let node = try! alloc::alloc(
        &mut *self.arena, @sizeOf(TypeNode), @alignOf(TypeNode)
    ) as *mut TypeNode;

    set *node = TypeNode { ty, next: self.types };
    set *node = TypeNode { ty, next: self.types[bucket] };
    let frozen: *TypeNode = node;
    set self.types = frozen;
    set self.types[bucket] = frozen;

    return &frozen.ty;
}

/// Allocate a nominal type descriptor and return a pointer to it.

    arena: &'arena mut alloc::Arena,
    storage: ResolverStorage,
    config: Config
) -> Resolver 'arena {
    let case ResolverStorage { nodeData, pkgScope, errors } = storage else panic "expected resolver storage";
    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;
    }
    let symbols = try! alloc::allocRawSlice(
        arena, @sizeOf(*unsafe mut Symbol), @alignOf(*unsafe mut Symbol), MAX_MODULE_SYMBOLS
    ) as *unsafe mut [*unsafe mut Symbol];

    // Initialize the root scope.

        currentMod: 0,
        inUnsafeContext: false,
        config,
        arena,
        nodeData: NodeDataTable { entries: nodeData },
        types: nil,
        types,
        errors: DiagnosticBuffer { entries: errors, len: 0 },
        moduleEntries: [nil; module::MAX_MODULES],
        moduleScopes,
        instances: undefined,
        instancesLen: 0,

lib/std/lang/resolver/tests.rad +42 -0

use std::lang::parser;
use std::lang::scanner;
use std::lang::module;
use std::lang::strings;

/// Interning preserves exact identity across populated collision chains.
@test unsafe fn testTypeInterningIdentity() throws (testing::TestError) {
    let mut arena = testArena();
    let storage: 'test = &mut arena in {
        let mut res = testResolver(storage);
        let item = super::allocType(&mut res, super::Type::U32);
        let mut entries: [?*super::Type; 2048] = [nil; 2048];
        for i in 0..entries.len {
            let ty = super::Type::Array(super::ArrayType { item, length: i });
            set entries[i] = super::allocType(&mut res, ty);
        }
        for i in 0..entries.len {
            let ty = super::Type::Array(super::ArrayType { item, length: i });
            let entry = entries[i] else throw testing::TestError::Failed;
            assert super::allocType(&mut res, ty) == entry;
            assert *entry == ty;
        }
        let values = [
            super::Type::U32, super::Type::U64,
            super::Type::Optional(item),
            super::Type::Range { start: nil, end: nil },
            super::Type::Range { start: item, end: nil },
            super::Type::Range { start: nil, end: item },
            super::Type::Range { start: item, end: item },
            super::Type::Cell { class: types::PointerClass::Ref, payload: item },
            super::Type::Pointer { class: types::PointerClass::Ref, target: item, mutable: false },
            super::Type::Pointer { class: types::PointerClass::Ref, target: item, mutable: true },
            super::Type::Pointer { class: types::PointerClass::Owned, target: item, mutable: false },
            super::Type::Pointer { class: types::PointerClass::Unsafe, target: item, mutable: false },
            super::Type::Slice { class: types::PointerClass::Ref, item, mutable: false },
            super::Type::Slice { class: types::PointerClass::Ref, item, mutable: true },
        ];
        for ty, i in values {
            let entry = super::allocType(&mut res, ty);
            assert super::allocType(&mut res, ty) == entry;
            for other, j in values {
                assert (entry == super::allocType(&mut res, other)) == (i == j);
            }
        }
    }
}

/// Array layouts retain element alignment for empty and populated arrays.
@test fn testArrayLayoutFromElementLayout() throws (testing::TestError) {
    for alignment in [1 as u32, 2, 4, 8, 16] {
        let item = super::Layout { size: alignment, alignment };
        for count in [0 as u32, 1, 3] {

1085	1090		config: Config,
1086	1091		/// Caller-owned arena, valid for this resolver and all emitted metadata.
1087	1092		arena: &'arena mut alloc::Arena,
1088	1093		/// Combined semantic metadata table indexed by node ID.
1089	1094		nodeData: NodeDataTable,
1090		-	/// Linked list of interned types.
1091		-	types: ?*TypeNode,
	1095	+	/// Lookup chains for interned types.
	1096	+	types: unsafe mut [?TypeNode],
1092	1097		/// Diagnostics recorded so far.
1093	1098		errors: DiagnosticBuffer,
1094	1099		/// Stable module identities indexed by module ID.
1095	1100		moduleEntries: [?*module::ModuleEntry; module::MAX_MODULES],
1096	1101		/// Cache of module scopes indexed by module ID.

1108	1113		/// Internal error sentinel thrown when analysis cannot proceed.
1109	1114		export union ResolveError: Copy {
1110	1115		Failure,
1111	1116		}
1112	1117
1113		-	/// Node in the type interning linked list.
	1118	+	/// Node in a type interning lookup chain.
1114	1119		record TypeNode: Copy {
	1120	+	/// Exact interned type value.
1115	1121		ty: Type,
	1122	+	/// Next type in the same lookup bucket.
1116	1123		next: ?*TypeNode,
1117	1124		}
1118	1125
1119	1126		/// Look up a region name in a lexical environment.
1120	1127		unsafe fn findRegion(scope: ?RegionScope, name: [u8]) -> ?*unsafe mut types::Region {

1194	1201		}
1195	1202		set self.nodeData.entries[owner.id].extra = NodeExtra::Regions(frozen);
1196	1203		return frozen;
1197	1204		}
1198	1205
	1206	+	/// Mix aligned metadata addresses into a lookup key.
	1207	+	fn addressHash(address: u64) -> u32 {
	1208	+	return ((address >> 3) as u32) ^ ((address >> 35) as u32);
	1209	+	}
	1210	+
	1211	+	/// Hash the active fields of a pointer class.
	1212	+	unsafe fn classHash(class: types::PointerClass) -> u32 {
	1213	+	match class {
	1214	+	case types::PointerClass::Owned => return 1,
	1215	+	case types::PointerClass::Ref => return 2,
	1216	+	case types::PointerClass::Unsafe => return 3,
	1217	+	case types::PointerClass::Region(region) => return addressHash(region as u64),
	1218	+	}
	1219	+	}
	1220	+
	1221	+	/// Hash active type fields so equal values select the same lookup chain.
	1222	+	unsafe fn typeHash(ty: Type) -> u32 {
	1223	+	match ty {
	1224	+	case Type::Cell { class, payload } =>
	1225	+	return addressHash(payload as u64) ^ (classHash(class) * CACHE_HASH_PRIME),
	1226	+	case Type::Pointer { class, target, mutable } =>
	1227	+	return addressHash(target as u64) ^ (classHash(class) * CACHE_HASH_PRIME) ^ (1 if mutable else 0),
	1228	+	case Type::Slice { class, item, mutable } =>
	1229	+	return addressHash(item as u64) ^ (classHash(class) * CACHE_HASH_PRIME) ^ (1 if mutable else 0),
	1230	+	case Type::TraitObject { class, traitInfo, mutable } =>
	1231	+	return addressHash(traitInfo as u64) ^ (classHash(class) * CACHE_HASH_PRIME) ^ (1 if mutable else 0),
	1232	+	case Type::Session(region) => return addressHash(region as u64),
	1233	+	case Type::Optional(inner) => return addressHash(inner as u64),
	1234	+	case Type::Fn(info) => return addressHash(info as u64),
	1235	+	case Type::Nominal(info) => return addressHash(info as u64),
	1236	+	case Type::Array(array) => return addressHash(array.item as u64) ^ (array.length * CACHE_HASH_PRIME),
	1237	+	case Type::Range { start, end } => {
	1238	+	let mut hash: u32 = 0;
	1239	+	if let item = start {
	1240	+	set hash = addressHash(item as u64);
	1241	+	}
	1242	+	if let item = end {
	1243	+	set hash = hash ^ (addressHash(item as u64) * CACHE_HASH_PRIME);
	1244	+	}
	1245	+	return hash;
	1246	+	}
	1247	+	else => return 0,
	1248	+	}
	1249	+	}
	1250	+
1199	1251		/// Allocate and intern a type in the arena, returning a pointer for deduplication.
1200	1252		export unsafe fn allocType 'arena (self: &mut Resolver 'arena, ty: Type) -> *Type {
1201	1253		// Search existing types for a match.
1202		-	let mut cursor = self.types;
	1254	+	let bucket = typeHash(ty) & (TYPE_BUCKETS - 1);
	1255	+	let mut cursor = self.types[bucket];
1203	1256		while let node = cursor {
1204	1257		if node.ty == ty {
1205	1258		return &node.ty;
1206	1259		}
1207	1260		set cursor = node.next;

1209	1262		// Allocate a new type node from the arena.
1210	1263		let node = try! alloc::alloc(
1211	1264		&mut *self.arena, @sizeOf(TypeNode), @alignOf(TypeNode)
1212	1265		) as *mut TypeNode;
1213	1266
1214		-	set *node = TypeNode { ty, next: self.types };
	1267	+	set *node = TypeNode { ty, next: self.types[bucket] };
1215	1268		let frozen: *TypeNode = node;
1216		-	set self.types = frozen;
	1269	+	set self.types[bucket] = frozen;
1217	1270
1218	1271		return &frozen.ty;
1219	1272		}
1220	1273
1221	1274		/// Allocate a nominal type descriptor and return a pointer to it.

1504	1557		arena: &'arena mut alloc::Arena,
1505	1558		storage: ResolverStorage,
1506	1559		config: Config
1507	1560		) -> Resolver 'arena {
1508	1561		let case ResolverStorage { nodeData, pkgScope, errors } = storage else panic "expected resolver storage";
	1562	+	let types = try! alloc::allocRawSlice(
	1563	+	arena, @sizeOf(?TypeNode), @alignOf(?TypeNode), TYPE_BUCKETS
	1564	+	) as unsafe mut [?TypeNode];
	1565	+	for i in 0..types.len {
	1566	+	set types[i] = nil;
	1567	+	}
1509	1568		let symbols = try! alloc::allocRawSlice(
1510	1569		arena, @sizeOf(unsafe mut Symbol), @alignOf(unsafe mut Symbol), MAX_MODULE_SYMBOLS
1511	1570		) as unsafe mut [unsafe mut Symbol];
1512	1571
1513	1572		// Initialize the root scope.

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

1553	1612		currentMod: 0,
1554	1613		inUnsafeContext: false,
1555	1614		config,
1556	1615		arena,
1557	1616		nodeData: NodeDataTable { entries: nodeData },
1558		-	types: nil,
	1617	+	types,
1559	1618		errors: DiagnosticBuffer { entries: errors, len: 0 },
1560	1619		moduleEntries: [nil; module::MAX_MODULES],
1561	1620		moduleScopes,
1562	1621		instances: undefined,
1563	1622		instancesLen: 0,

11	11		use std::lang::parser;
12	12		use std::lang::scanner;
13	13		use std::lang::module;
14	14		use std::lang::strings;
15	15
	16	+	/// Interning preserves exact identity across populated collision chains.
	17	+	@test unsafe fn testTypeInterningIdentity() throws (testing::TestError) {
	18	+	let mut arena = testArena();
	19	+	let storage: 'test = &mut arena in {
	20	+	let mut res = testResolver(storage);
	21	+	let item = super::allocType(&mut res, super::Type::U32);
	22	+	let mut entries: [?*super::Type; 2048] = [nil; 2048];
	23	+	for i in 0..entries.len {
	24	+	let ty = super::Type::Array(super::ArrayType { item, length: i });
	25	+	set entries[i] = super::allocType(&mut res, ty);
	26	+	}
	27	+	for i in 0..entries.len {
	28	+	let ty = super::Type::Array(super::ArrayType { item, length: i });
	29	+	let entry = entries[i] else throw testing::TestError::Failed;
	30	+	assert super::allocType(&mut res, ty) == entry;
	31	+	assert *entry == ty;
	32	+	}
	33	+	let values = [
	34	+	super::Type::U32, super::Type::U64,
	35	+	super::Type::Optional(item),
	36	+	super::Type::Range { start: nil, end: nil },
	37	+	super::Type::Range { start: item, end: nil },
	38	+	super::Type::Range { start: nil, end: item },
	39	+	super::Type::Range { start: item, end: item },
	40	+	super::Type::Cell { class: types::PointerClass::Ref, payload: item },
	41	+	super::Type::Pointer { class: types::PointerClass::Ref, target: item, mutable: false },
	42	+	super::Type::Pointer { class: types::PointerClass::Ref, target: item, mutable: true },
	43	+	super::Type::Pointer { class: types::PointerClass::Owned, target: item, mutable: false },
	44	+	super::Type::Pointer { class: types::PointerClass::Unsafe, target: item, mutable: false },
	45	+	super::Type::Slice { class: types::PointerClass::Ref, item, mutable: false },
	46	+	super::Type::Slice { class: types::PointerClass::Ref, item, mutable: true },
	47	+	];
	48	+	for ty, i in values {
	49	+	let entry = super::allocType(&mut res, ty);
	50	+	assert super::allocType(&mut res, ty) == entry;
	51	+	for other, j in values {
	52	+	assert (entry == super::allocType(&mut res, other)) == (i == j);
	53	+	}
	54	+	}
	55	+	}
	56	+	}
	57	+
16	58		/// Array layouts retain element alignment for empty and populated arrays.
17	59		@test fn testArrayLayoutFromElementLayout() throws (testing::TestError) {
18	60		for alignment in [1 as u32, 2, 4, 8, 16] {
19	61		let item = super::Layout { size: alignment, alignment };
20	62		for count in [0 as u32, 1, 3] {