radiance · commit

refactor(lang): Share generic type substitution

3225bfc0f4e8414a142c1c31c309d6172bf96408739626c07578605ac8253188

Keep resolver-owned semantic work and read-only lowering under one
recursive type traversal. Select allocation and error behavior through a
private context union, and write lowering results only to lowerer-owned
arenas.

Alexis Sellier committed 19 days ago 1 parent a0848143

lib/std/lang/lower.rad +9 -261

        }
    }
    return maxSize;
}

/// Allocate one persistent structural type component.
fn allocPersistentType(
    self: *mut Lowerer,
    ty: resolver::Type,
) -> *resolver::Type {
    let stored = try! alloc::alloc(
        self.arena,
        @sizeOf(resolver::Type),
        @alignOf(resolver::Type),
    ) as *mut resolver::Type;
    set *stored = ty;
    return stored;
}

/// Copy a concrete structural type into persistent lowering storage.
///
/// Nominal pointers retain their canonical identity; only structural
/// components that may live in the function arena are copied.
fn persistStructuralType(
    self: *mut Lowerer,
    ty: resolver::Type,
) -> resolver::Type {
    match ty {
        case resolver::Type::Pointer(pointer) => {
            let target = persistStructuralType(self, *pointer.target);
            return resolver::Type::Pointer(resolver::PointerType {
                class: pointer.class,
                target: allocPersistentType(self, target),
                mutable: pointer.mutable,
            });
        }
        case resolver::Type::Slice(slice) => {
            let item = persistStructuralType(self, *slice.item);
            return resolver::Type::Slice(resolver::SliceType {
                class: slice.class,
                item: allocPersistentType(self, item),
                mutable: slice.mutable,
            });
        }
        case resolver::Type::Array(array) => {
            let item = persistStructuralType(self, *array.item);
            return resolver::Type::Array(resolver::ArrayType {
                item: allocPersistentType(self, item),
                length: array.length,
            });
        }
        case resolver::Type::Optional(inner) => {
            let stored = persistStructuralType(self, *inner);
            return resolver::Type::Optional(allocPersistentType(self, stored));
        }
        case resolver::Type::Fn(info) => {
            let mut params: *mut [*resolver::Type] = &mut [];
            let mut throwList: *mut [*resolver::Type] = &mut [];
            for param in info.paramTypes {
                let stored = persistStructuralType(self, *param);
                params.append(allocPersistentType(self, stored), self.allocator);
            }
            for thrown in info.throwList {
                let stored = persistStructuralType(self, *thrown);
                throwList.append(
                    allocPersistentType(self, stored), self.allocator
                );
            }
            let returnType = persistStructuralType(self, *info.returnType);
            let storedInfo = try! alloc::alloc(
                self.arena,
                @sizeOf(resolver::FnType),
                @alignOf(resolver::FnType),
            ) as *mut resolver::FnType;
            set *storedInfo = resolver::FnType {
                paramTypes: &params[..],
                returnType: allocPersistentType(self, returnType),
                throwList: &throwList[..],
                isUnsafe: info.isUnsafe,
                localCount: info.localCount,
            };
            return resolver::Type::Fn(storedInfo);
        }
        case resolver::Type::Range { start, end } => {
            let mut storedStart: ?*resolver::Type = nil;
            let mut storedEnd: ?*resolver::Type = nil;
            if let value = start {
                let stored = persistStructuralType(self, *value);
                set storedStart = allocPersistentType(self, stored);
            }
            if let value = end {
                let stored = persistStructuralType(self, *value);
                set storedEnd = allocPersistentType(self, stored);
            }
            return resolver::Type::Range {
                start: storedStart,
                end: storedEnd,
            };
        }
        else => return ty,
    }
}

/// Get or assign a globally unique tag for a concrete error type.
fn getOrAssignErrorTag(
    self: *mut Lowerer,
    errType: resolver::Type,
) -> u32 {

        }
    }
    let tag = self.errTagCounter;
    set self.errTagCounter += 1;
    self.errTags.append(ErrTagEntry {
        ty: persistStructuralType(self, errType),
        ty: resolver::copyStructuralTypeToArena(errType, self.arena),
        tag,
    }, self.allocator);
    return tag;
}


    let reg = il::Reg { n: self.regCounter };
    set self.regCounter += 1;
    return reg;
}

/// Allocate a structural type component in the current function arena.
fn allocSpecializedType(
    self: *mut FnLowerer,
    ty: resolver::Type,
) -> *resolver::Type {
    let value = try! alloc::alloc(
        self.low.fnArena,
        @sizeOf(resolver::Type),
        @alignOf(resolver::Type),
    ) as *mut resolver::Type;
    set *value = ty;
    return value;
}

/// Apply the current generic function specialization without mutating resolver
/// metadata or allocating from resolver-owned arenas.
fn specializeType(
    self: *mut FnLowerer,
    ty: resolver::Type,
) -> resolver::Type throws (LowerError) {
    let sub = self.low.specialization else return ty;
    if not resolver::containsGenericParameter(ty) {
        return ty;
    }
    match ty {
        case resolver::Type::Parameter(param) =>
            return resolver::substitutionArg(sub, param),
        case resolver::Type::ConstParameter(param) =>
            return resolver::substitutionArg(sub, param),
        case resolver::Type::GenericConstExpr { type, expr } => {
            let value = resolver::constIntWithSubstitution(
                self.low.resolver, expr, *type, sub
            ) else throw LowerError::MissingMetadata;
            return resolver::Type::ConstArgument { type, value };
        }
        case resolver::Type::Pointer(pointer) => {
            let target = try specializeType(self, *pointer.target);
            return resolver::Type::Pointer(resolver::PointerType {
                class: pointer.class,
                target: allocSpecializedType(self, target),
                mutable: pointer.mutable,
            });
        }
        case resolver::Type::Slice(slice) => {
            let item = try specializeType(self, *slice.item);
            return resolver::Type::Slice(resolver::SliceType {
                class: slice.class,
                item: allocSpecializedType(self, item),
                mutable: slice.mutable,
            });
        }
        case resolver::Type::Array(array) => {
            let item = try specializeType(self, *array.item);
            return resolver::Type::Array(resolver::ArrayType {
                item: allocSpecializedType(self, item),
                length: array.length,
            });
        }
        case resolver::Type::GenericArray { item, length } => {
            let concreteItem = try specializeType(self, *item);
            let value = resolver::constIntWithSubstitution(
                self.low.resolver, length, resolver::Type::U32, sub
            ) else throw LowerError::MissingMetadata;
            return resolver::Type::Array(resolver::ArrayType {
                item: allocSpecializedType(self, concreteItem),
                length: value.magnitude as u32,
            });
        }
        case resolver::Type::Optional(inner) => {
            let value = try specializeType(self, *inner);
            return resolver::Type::Optional(allocSpecializedType(self, value));
        }
        case resolver::Type::GenericDataApply(app) => {
            let mut args: *mut [*resolver::Type] = &mut [];
            for arg in app.args {
                let concrete = try specializeType(self, *arg);
                if resolver::containsGenericParameter(concrete) {
                    throw LowerError::MissingMetadata;
                }
                args.append(allocSpecializedType(self, concrete), self.allocator);
            }
            let specialization = resolver::findGenericDataSpecialization(
                self.low.resolver, app.template, &args[..]
            ) else throw LowerError::MissingMetadata;
            return resolver::Type::Nominal(specialization.nominal);
        }
        case resolver::Type::GenericRecord(genericRecord) => {
            let mut fields: *mut [resolver::RecordField] = &mut [];
            let mut offset: u32 = 0;
            let mut alignment: u32 = 1;
            for field in genericRecord.fields {
                let fieldType = try specializeType(self, field.fieldType);
                if resolver::containsGenericParameter(fieldType) {
                    throw LowerError::MissingMetadata;
                }
                let fieldLayout = resolver::getTypeLayout(fieldType);
                set offset = mem::alignUp(offset, fieldLayout.alignment);
                fields.append(resolver::RecordField {
                    name: field.name,
                    fieldType: persistStructuralType(self.low, fieldType),
                    offset: offset as i32,
                }, self.low.allocator);
                set offset += fieldLayout.size;
                if fieldLayout.alignment > alignment {
                    set alignment = fieldLayout.alignment;
                }
            }
            let nominal = try! alloc::alloc(
                self.low.arena,
                @sizeOf(resolver::NominalType),
                @alignOf(resolver::NominalType),
            ) as *mut resolver::NominalType;
            set *nominal = resolver::NominalType::Record(resolver::RecordType {
                fields: &fields[..],
                labeled: genericRecord.labeled,
                layout: resolver::Layout {
                    size: mem::alignUp(offset, alignment),
                    alignment,
                },
                declaredLinear: false,
            });
            return resolver::Type::Nominal(nominal);
        }
        case resolver::Type::Fn(info) => {
            let mut params: *mut [*resolver::Type] = &mut [];
            let mut throwTypes: *mut [*resolver::Type] = &mut [];
            for param in info.paramTypes {
                let concrete = try specializeType(self, *param);
                params.append(allocSpecializedType(self, concrete), self.allocator);
            }
            for thrown in info.throwList {
                let concrete = try specializeType(self, *thrown);
                throwTypes.append(
                    allocSpecializedType(self, concrete), self.allocator
                );
            }
            let result = try specializeType(self, *info.returnType);
            let fnType = try! alloc::alloc(
                self.low.fnArena,
                @sizeOf(resolver::FnType),
                @alignOf(resolver::FnType),
            ) as *mut resolver::FnType;
            set *fnType = resolver::FnType {
                paramTypes: &params[..],
                returnType: allocSpecializedType(self, result),
                throwList: &throwTypes[..],
                isUnsafe: info.isUnsafe,
                localCount: info.localCount,
            };
            return resolver::Type::Fn(fnType);
        }
        case resolver::Type::Range { start, end } => {
            let mut concreteStart: ?*resolver::Type = nil;
            let mut concreteEnd: ?*resolver::Type = nil;
            if let value = start {
                let concrete = try specializeType(self, *value);
                set concreteStart = allocSpecializedType(self, concrete);
            }
            if let value = end {
                let concrete = try specializeType(self, *value);
                set concreteEnd = allocSpecializedType(self, concrete);
            }
            return resolver::Type::Range {
                start: concreteStart,
                end: concreteEnd,
            };
        }
        else => return ty,
    }
    let specialized = resolver::substituteTypeReadOnly(
        self.low.resolver,
        ty,
        sub,
        self.low.fnArena,
        self.low.arena,
    ) else throw LowerError::MissingMetadata;
    return specialized;
}

/// Look up the resolved type of an AST node, or throw `MissingType`.
fn typeOf(self: *mut FnLowerer, node: *ast::Node) -> resolver::Type throws (LowerError) {
    let ty = resolver::typeFor(self.low.resolver, node)

lib/std/lang/resolver.rad +309 -77

        return Type::ConstParameter(param);
    }
    return Type::Parameter(param);
}

/// Recursively replace rigid parameters in a resolved type.
export fn substituteType(
    self: *mut Resolver,
/// Ownership and error policy for type substitution.
union TypeSubstitutionContext {
    /// Resolver-owned substitution that may emit diagnostics.
    Resolution {
        /// Mutable resolver that owns the result.
        resolver: *mut Resolver,
        /// Source site for structural type diagnostics.
        site: *ast::Node,
    },
    /// Read-only substitution into caller-owned arenas.
    ReadOnly {
        /// Immutable resolver metadata.
        resolver: *Resolver,
        /// Arena for function-local structural types.
        structuralArena: *mut alloc::Arena,
        /// Arena for structural types that outlive the function.
        persistentArena: *mut alloc::Arena,
    },
}

/// Return the arena for temporary structural substitution results.
fn substitutionArena(context: *mut TypeSubstitutionContext) -> *mut alloc::Arena {
    match *context {
        case TypeSubstitutionContext::Resolution { resolver, .. } =>
            return &mut resolver.arena,
        case TypeSubstitutionContext::ReadOnly { structuralArena, .. } =>
            return structuralArena,
    }
}

/// Allocate a nested substituted type with the selected ownership policy.
fn allocSubstitutedType(
    context: *mut TypeSubstitutionContext,
    ty: Type,
) -> *Type {
    if let case TypeSubstitutionContext::Resolution { resolver, .. } = *context {
        return allocType(resolver, ty);
    }
    let stored = try! alloc::alloc(
        substitutionArena(context), @sizeOf(Type), @alignOf(Type)
    ) as *mut Type;
    set *stored = ty;
    return stored;
}

/// Allocate one type component in an explicit arena.
fn allocArenaType(arena: *mut alloc::Arena, ty: Type) -> *Type {
    let stored = try! alloc::alloc(
        arena, @sizeOf(Type), @alignOf(Type)
    ) as *mut Type;
    set *stored = ty;
    return stored;
}

/// Copy a concrete structural type into the given arena.
///
/// Nominal pointers retain their canonical identity.
export fn copyStructuralTypeToArena(
    ty: Type,
    arena: *mut alloc::Arena,
) -> Type {
    match ty {
        case Type::Pointer(pointer) => {
            let target = copyStructuralTypeToArena(*pointer.target, arena);
            return Type::Pointer(PointerType {
                class: pointer.class,
                target: allocArenaType(arena, target),
                mutable: pointer.mutable,
            });
        }
        case Type::Slice(slice) => {
            let item = copyStructuralTypeToArena(*slice.item, arena);
            return Type::Slice(SliceType {
                class: slice.class,
                item: allocArenaType(arena, item),
                mutable: slice.mutable,
            });
        }
        case Type::Array(array) => {
            let item = copyStructuralTypeToArena(*array.item, arena);
            return Type::Array(ArrayType {
                item: allocArenaType(arena, item),
                length: array.length,
            });
        }
        case Type::Optional(inner) => {
            let stored = copyStructuralTypeToArena(*inner, arena);
            return Type::Optional(allocArenaType(arena, stored));
        }
        case Type::Fn(info) => {
            let a = alloc::arenaAllocator(arena);
            let mut params: *mut [*Type] = &mut [];
            let mut throwList: *mut [*Type] = &mut [];
            for param in info.paramTypes {
                let stored = copyStructuralTypeToArena(*param, arena);
                params.append(allocArenaType(arena, stored), a);
            }
            for thrown in info.throwList {
                let stored = copyStructuralTypeToArena(*thrown, arena);
                throwList.append(allocArenaType(arena, stored), a);
            }
            let returnType = copyStructuralTypeToArena(*info.returnType, arena);
            let storedInfo = try! alloc::alloc(
                arena, @sizeOf(FnType), @alignOf(FnType)
            ) as *mut FnType;
            set *storedInfo = FnType {
                paramTypes: &params[..],
                returnType: allocArenaType(arena, returnType),
                throwList: &throwList[..],
                isUnsafe: info.isUnsafe,
                localCount: info.localCount,
            };
            return Type::Fn(storedInfo);
        }
        case Type::Range { start, end } => {
            let mut storedStart: ?*Type = nil;
            let mut storedEnd: ?*Type = nil;
            if let value = start {
                let stored = copyStructuralTypeToArena(*value, arena);
                set storedStart = allocArenaType(arena, stored);
            }
            if let value = end {
                let stored = copyStructuralTypeToArena(*value, arena);
                set storedEnd = allocArenaType(arena, stored);
            }
            return Type::Range { start: storedStart, end: storedEnd };
        }
        else => return ty,
    }
}

/// Recursively replace rigid parameters under the selected policy.
fn substituteTypeWithContext(
    context: *mut TypeSubstitutionContext,
    ty: Type,
    sub: *Substitution,
    site: *ast::Node,
) -> Type throws (ResolveError) {
    if not containsGenericParameter(ty) {
        return ty;
    }
    match ty {
        case Type::Parameter(param) => return substitutionArg(sub, param),
        case Type::ConstParameter(param) => return substitutionArg(sub, param),
        case Type::GenericConstExpr { type, expr } => {
            let value = constValueWithSubstitution(self, expr, sub)
                else throw emitError(self, expr, ErrorKind::ConstExprRequired);
            let case ConstValue::Int(int) = value
                else throw emitError(self, expr, ErrorKind::ConstExprRequired);
            if not validateConstIntRange(value, *type) {
                throw emitError(self, expr, ErrorKind::NumericLiteralOverflow);
            match *context {
                case TypeSubstitutionContext::Resolution { resolver, .. } => {
                    let value = constValueWithSubstitution(resolver, expr, sub)
                        else throw emitError(resolver, expr, ErrorKind::ConstExprRequired);
                    let case ConstValue::Int(int) = value
                        else throw emitError(resolver, expr, ErrorKind::ConstExprRequired);
                    if not validateConstIntRange(value, *type) {
                        throw emitError(resolver, expr, ErrorKind::NumericLiteralOverflow);
                    }
                    let case ConstValue::Int(canonical) = castConstInt(int, *type)
                        else throw emitError(resolver, expr, ErrorKind::Internal);
                    return Type::ConstArgument { type, value: canonical };
                }
                case TypeSubstitutionContext::ReadOnly { resolver, .. } => {
                    let value = constIntWithSubstitution(resolver, expr, *type, sub)
                        else throw ResolveError::Failure;
                    return Type::ConstArgument { type, value };
                }
            }
            let case ConstValue::Int(canonical) = castConstInt(int, *type)
                else throw emitError(self, expr, ErrorKind::Internal);
            return Type::ConstArgument { type, value: canonical };
        }
        case Type::Pointer(pointer) => {
            let inner = try substituteType(self, *pointer.target, sub, site);
            let inner = try substituteTypeWithContext(context, *pointer.target, sub);
            return Type::Pointer(PointerType {
                class: pointer.class,
                target: allocType(self, inner),
                target: allocSubstitutedType(context, inner),
                mutable: pointer.mutable,
            });
        }
        case Type::Slice(slice) => {
            let inner = try substituteType(self, *slice.item, sub, site);
            let inner = try substituteTypeWithContext(context, *slice.item, sub);
            return Type::Slice(SliceType {
                class: slice.class,
                item: allocType(self, inner),
                item: allocSubstitutedType(context, inner),
                mutable: slice.mutable,
            });
        }
        case Type::Array(array) => {
            let item = try substituteType(self, *array.item, sub, site);
            let item = try substituteTypeWithContext(context, *array.item, sub);
            return Type::Array(ArrayType {
                item: allocType(self, item),
                item: allocSubstitutedType(context, item),
                length: array.length,
            });
        }
        case Type::GenericArray { item, length } => {
            let concreteItem = try substituteType(self, *item, sub, site);
            let value = constValueWithSubstitution(self, length, sub)
                else throw emitError(self, length, ErrorKind::ConstExprRequired);
            if not validateConstIntRange(value, Type::U32) {
                throw emitError(self, length, ErrorKind::NumericLiteralOverflow);
            let concreteItem = try substituteTypeWithContext(context, *item, sub);
            let mut arrayLength: u32 = 0;
            match *context {
                case TypeSubstitutionContext::Resolution { resolver, .. } => {
                    let value = constValueWithSubstitution(resolver, length, sub)
                        else throw emitError(resolver, length, ErrorKind::ConstExprRequired);
                    if not validateConstIntRange(value, Type::U32) {
                        throw emitError(resolver, length, ErrorKind::NumericLiteralOverflow);
                    }
                    let case ConstValue::Int(int) = value
                        else throw emitError(resolver, length, ErrorKind::ConstExprRequired);
                    set arrayLength = int.magnitude as u32;
                }
                case TypeSubstitutionContext::ReadOnly { resolver, .. } => {
                    let value = constIntWithSubstitution(
                        resolver, length, Type::U32, sub
                    ) else throw ResolveError::Failure;
                    set arrayLength = value.magnitude as u32;
                }
            }
            let case ConstValue::Int(int) = value
                else throw emitError(self, length, ErrorKind::ConstExprRequired);
            return Type::Array(ArrayType {
                item: allocType(self, concreteItem),
                length: int.magnitude as u32,
                item: allocSubstitutedType(context, concreteItem),
                length: arrayLength,
            });
        }
        case Type::Optional(inner) => {
            let value = try substituteType(self, *inner, sub, site);
            return Type::Optional(allocType(self, value));
            let value = try substituteTypeWithContext(context, *inner, sub);
            return Type::Optional(allocSubstitutedType(context, value));
        }
        case Type::GenericDataApply(app) => {
            let a = alloc::arenaAllocator(&mut self.arena);
            let a = alloc::arenaAllocator(substitutionArena(context));
            let mut args: *mut [*Type] = &mut [];
            let mut symbolic = false;
            for arg in app.args {
                let replacement = try substituteType(self, *arg, sub, site);
                let replacement = try substituteTypeWithContext(context, *arg, sub);
                set symbolic = symbolic or containsGenericParameter(replacement);
                args.append(allocType(self, replacement), a);
            }
            if symbolic {
                let application = try! alloc::alloc(
                    &mut self.arena,
                    @sizeOf(GenericDataApplyType),
                    @alignOf(GenericDataApplyType),
                ) as *mut GenericDataApplyType;
                set *application = GenericDataApplyType {
                    template: app.template,
                    args: &args[..],
                    site: app.site,
                };
                return Type::GenericDataApply(application);
                args.append(allocSubstitutedType(context, replacement), a);
            }
            match *context {
                case TypeSubstitutionContext::Resolution { resolver, .. } => {
                    if symbolic {
                        let application = try! alloc::alloc(
                            &mut resolver.arena,
                            @sizeOf(GenericDataApplyType),
                            @alignOf(GenericDataApplyType),
                        ) as *mut GenericDataApplyType;
                        set *application = GenericDataApplyType {
                            template: app.template,
                            args: &args[..],
                            site: app.site,
                        };
                        return Type::GenericDataApply(application);
                    }
                    let nominal = try specializeGenericData(
                        resolver, app.site, app.template, &args[..], false
                    );
                    return Type::Nominal(nominal);
                }
                case TypeSubstitutionContext::ReadOnly { resolver, .. } => {
                    if symbolic {
                        throw ResolveError::Failure;
                    }
                    let specialization = findGenericDataSpecialization(
                        resolver, app.template, &args[..]
                    ) else throw ResolveError::Failure;
                    return Type::Nominal(specialization.nominal);
                }
            }
            let nominal = try specializeGenericData(
                self, app.site, app.template, &args[..], false
            );
            return Type::Nominal(nominal);
        }
        case Type::GenericRecord(rec) => {
            let a = alloc::arenaAllocator(&mut self.arena);
            let mut persistentArena = substitutionArena(context);
            if let case TypeSubstitutionContext::ReadOnly {
                persistentArena: arena,
                ..
            } = *context {
                set persistentArena = arena;
            }
            let a = alloc::arenaAllocator(persistentArena);
            let mut fields: *mut [RecordField] = &mut [];
            let mut offset: u32 = 0;
            let mut alignment: u32 = 1;
            for field in rec.fields {
                let fieldType = try substituteType(self, field.fieldType, sub, site);
                if hasUnresolvedNominalLayout(fieldType) {
                    throw emitError(self, site, ErrorKind::GenericRecursiveLayout);
                let fieldType = try substituteTypeWithContext(
                    context, field.fieldType, sub
                );
                let mut storedFieldType = fieldType;
                match *context {
                    case TypeSubstitutionContext::Resolution { resolver, site } => {
                        if hasUnresolvedNominalLayout(fieldType) {
                            throw emitError(
                                resolver, site, ErrorKind::GenericRecursiveLayout
                            );
                        }
                        try ensureStorableType(resolver, site, fieldType);
                        try ensureTypeResolved(resolver, fieldType, site);
                    }
                    case TypeSubstitutionContext::ReadOnly { .. } => {
                        if containsGenericParameter(fieldType) {
                            throw ResolveError::Failure;
                        }
                        set storedFieldType = copyStructuralTypeToArena(
                            fieldType, persistentArena
                        );
                    }
                }
                try ensureStorableType(self, site, fieldType);
                try ensureTypeResolved(self, fieldType, site);
                let fieldLayout = getTypeLayout(fieldType);
                set offset = mem::alignUp(offset, fieldLayout.alignment);
                fields.append(RecordField {
                    name: field.name,
                    fieldType,
                    fieldType: storedFieldType,
                    offset: offset as i32,
                }, a);
                set offset += fieldLayout.size;
                set alignment = max(alignment, fieldLayout.alignment);
            }
            let layout = Layout {
                size: mem::alignUp(offset, alignment),
                alignment,
            };
            return Type::Nominal(allocNominalType(self, NominalType::Record(RecordType {
            let nominal = try! alloc::alloc(
                persistentArena, @sizeOf(NominalType), @alignOf(NominalType)
            ) as *mut NominalType;
            set *nominal = NominalType::Record(RecordType {
                fields: &fields[..],
                labeled: rec.labeled,
                layout,
                layout: Layout {
                    size: mem::alignUp(offset, alignment),
                    alignment,
                },
                declaredLinear: false,
            })));
            });
            return Type::Nominal(nominal);
        }
        case Type::Fn(info) => {
            let a = alloc::arenaAllocator(&mut self.arena);
            let arena = substitutionArena(context);
            let a = alloc::arenaAllocator(arena);
            let mut params: *mut [*Type] = &mut [];
            let mut throwTypes: *mut [*Type] = &mut [];
            for param in info.paramTypes {
                let concrete = try substituteType(self, *param, sub, site);
                params.append(allocType(self, concrete), a);
                let concrete = try substituteTypeWithContext(context, *param, sub);
                params.append(allocSubstitutedType(context, concrete), a);
            }
            for thrown in info.throwList {
                let concrete = try substituteType(self, *thrown, sub, site);
                throwTypes.append(allocType(self, concrete), a);
                let concrete = try substituteTypeWithContext(context, *thrown, sub);
                throwTypes.append(allocSubstitutedType(context, concrete), a);
            }
            let result = try substituteType(self, *info.returnType, sub, site);
            return Type::Fn(allocFnType(self, FnType {
            let result = try substituteTypeWithContext(
                context, *info.returnType, sub
            );
            let fnType = try! alloc::alloc(
                arena, @sizeOf(FnType), @alignOf(FnType)
            ) as *mut FnType;
            set *fnType = FnType {
                paramTypes: &params[..],
                returnType: allocType(self, result),
                returnType: allocSubstitutedType(context, result),
                throwList: &throwTypes[..],
                isUnsafe: info.isUnsafe,
                localCount: info.localCount,
            }));
            };
            return Type::Fn(fnType);
        }
        case Type::Range { start, end } => {
            let mut newStart: ?*Type = nil;
            let mut newEnd: ?*Type = nil;
            if let value = start {
                let concrete = try substituteType(self, *value, sub, site);
                set newStart = allocType(self, concrete);
                let concrete = try substituteTypeWithContext(context, *value, sub);
                set newStart = allocSubstitutedType(context, concrete);
            }
            if let value = end {
                let concrete = try substituteType(self, *value, sub, site);
                set newEnd = allocType(self, concrete);
                let concrete = try substituteTypeWithContext(context, *value, sub);
                set newEnd = allocSubstitutedType(context, concrete);
            }
            return Type::Range { start: newStart, end: newEnd };
        }
        else => return ty,
    }
}

/// Recursively replace rigid parameters in a resolved type.
export fn substituteType(
    self: *mut Resolver,
    ty: Type,
    sub: *Substitution,
    site: *ast::Node,
) -> Type throws (ResolveError) {
    let mut context = TypeSubstitutionContext::Resolution {
        resolver: self,
        site,
    };
    return try substituteTypeWithContext(&mut context, ty, sub);
}

/// Substitute a type using immutable metadata and caller-owned arenas.
///
/// Return `nil` when required specialization metadata is missing.
export fn substituteTypeReadOnly(
    self: *Resolver,
    ty: Type,
    sub: *Substitution,
    structuralArena: *mut alloc::Arena,
    persistentArena: *mut alloc::Arena,
) -> ?Type {
    let mut context = TypeSubstitutionContext::ReadOnly {
        resolver: self,
        structuralArena,
        persistentArena,
    };
    return try substituteTypeWithContext(&mut context, ty, sub) catch {
        return nil;
    };
}

/// Allocate a nominal type descriptor and return a pointer to it.
fn allocNominalType(self: *mut Resolver, info: NominalType) -> *mut NominalType {
    // Nb. We don't attempt to de-duplicate nominal type entries,
    // since they don't carry node information and we create
    // placeholder entries when binding symbols.

361	361		}
362	362		}
363	363		return maxSize;
364	364		}
365	365
366		-	/// Allocate one persistent structural type component.
367		-	fn allocPersistentType(
368		-	self: *mut Lowerer,
369		-	ty: resolver::Type,
370		-	) -> *resolver::Type {
371		-	let stored = try! alloc::alloc(
372		-	self.arena,
373		-	@sizeOf(resolver::Type),
374		-	@alignOf(resolver::Type),
375		-	) as *mut resolver::Type;
376		-	set *stored = ty;
377		-	return stored;
378		-	}
379		-
380		-	/// Copy a concrete structural type into persistent lowering storage.
381		-	///
382		-	/// Nominal pointers retain their canonical identity; only structural
383		-	/// components that may live in the function arena are copied.
384		-	fn persistStructuralType(
385		-	self: *mut Lowerer,
386		-	ty: resolver::Type,
387		-	) -> resolver::Type {
388		-	match ty {
389		-	case resolver::Type::Pointer(pointer) => {
390		-	let target = persistStructuralType(self, *pointer.target);
391		-	return resolver::Type::Pointer(resolver::PointerType {
392		-	class: pointer.class,
393		-	target: allocPersistentType(self, target),
394		-	mutable: pointer.mutable,
395		-	});
396		-	}
397		-	case resolver::Type::Slice(slice) => {
398		-	let item = persistStructuralType(self, *slice.item);
399		-	return resolver::Type::Slice(resolver::SliceType {
400		-	class: slice.class,
401		-	item: allocPersistentType(self, item),
402		-	mutable: slice.mutable,
403		-	});
404		-	}
405		-	case resolver::Type::Array(array) => {
406		-	let item = persistStructuralType(self, *array.item);
407		-	return resolver::Type::Array(resolver::ArrayType {
408		-	item: allocPersistentType(self, item),
409		-	length: array.length,
410		-	});
411		-	}
412		-	case resolver::Type::Optional(inner) => {
413		-	let stored = persistStructuralType(self, *inner);
414		-	return resolver::Type::Optional(allocPersistentType(self, stored));
415		-	}
416		-	case resolver::Type::Fn(info) => {
417		-	let mut params: mut [resolver::Type] = &mut [];
418		-	let mut throwList: mut [resolver::Type] = &mut [];
419		-	for param in info.paramTypes {
420		-	let stored = persistStructuralType(self, *param);
421		-	params.append(allocPersistentType(self, stored), self.allocator);
422		-	}
423		-	for thrown in info.throwList {
424		-	let stored = persistStructuralType(self, *thrown);
425		-	throwList.append(
426		-	allocPersistentType(self, stored), self.allocator
427		-	);
428		-	}
429		-	let returnType = persistStructuralType(self, *info.returnType);
430		-	let storedInfo = try! alloc::alloc(
431		-	self.arena,
432		-	@sizeOf(resolver::FnType),
433		-	@alignOf(resolver::FnType),
434		-	) as *mut resolver::FnType;
435		-	set *storedInfo = resolver::FnType {
436		-	paramTypes: &params[..],
437		-	returnType: allocPersistentType(self, returnType),
438		-	throwList: &throwList[..],
439		-	isUnsafe: info.isUnsafe,
440		-	localCount: info.localCount,
441		-	};
442		-	return resolver::Type::Fn(storedInfo);
443		-	}
444		-	case resolver::Type::Range { start, end } => {
445		-	let mut storedStart: ?*resolver::Type = nil;
446		-	let mut storedEnd: ?*resolver::Type = nil;
447		-	if let value = start {
448		-	let stored = persistStructuralType(self, *value);
449		-	set storedStart = allocPersistentType(self, stored);
450		-	}
451		-	if let value = end {
452		-	let stored = persistStructuralType(self, *value);
453		-	set storedEnd = allocPersistentType(self, stored);
454		-	}
455		-	return resolver::Type::Range {
456		-	start: storedStart,
457		-	end: storedEnd,
458		-	};
459		-	}
460		-	else => return ty,
461		-	}
462		-	}
463		-
464	366		/// Get or assign a globally unique tag for a concrete error type.
465	367		fn getOrAssignErrorTag(
466	368		self: *mut Lowerer,
467	369		errType: resolver::Type,
468	370		) -> u32 {

473	375		}
474	376		}
475	377		let tag = self.errTagCounter;
476	378		set self.errTagCounter += 1;
477	379		self.errTags.append(ErrTagEntry {
478		-	ty: persistStructuralType(self, errType),
	380	+	ty: resolver::copyStructuralTypeToArena(errType, self.arena),
479	381		tag,
480	382		}, self.allocator);
481	383		return tag;
482	384		}
483	385

2345	2247		let reg = il::Reg { n: self.regCounter };
2346	2248		set self.regCounter += 1;
2347	2249		return reg;
2348	2250		}
2349	2251
2350		-	/// Allocate a structural type component in the current function arena.
2351		-	fn allocSpecializedType(
2352		-	self: *mut FnLowerer,
2353		-	ty: resolver::Type,
2354		-	) -> *resolver::Type {
2355		-	let value = try! alloc::alloc(
2356		-	self.low.fnArena,
2357		-	@sizeOf(resolver::Type),
2358		-	@alignOf(resolver::Type),
2359		-	) as *mut resolver::Type;
2360		-	set *value = ty;
2361		-	return value;
2362		-	}
2363		-
2364	2252		/// Apply the current generic function specialization without mutating resolver
2365	2253		/// metadata or allocating from resolver-owned arenas.
2366	2254		fn specializeType(
2367	2255		self: *mut FnLowerer,
2368	2256		ty: resolver::Type,
2369	2257		) -> resolver::Type throws (LowerError) {
2370	2258		let sub = self.low.specialization else return ty;
2371		-	if not resolver::containsGenericParameter(ty) {
2372		-	return ty;
2373		-	}
2374		-	match ty {
2375		-	case resolver::Type::Parameter(param) =>
2376		-	return resolver::substitutionArg(sub, param),
2377		-	case resolver::Type::ConstParameter(param) =>
2378		-	return resolver::substitutionArg(sub, param),
2379		-	case resolver::Type::GenericConstExpr { type, expr } => {
2380		-	let value = resolver::constIntWithSubstitution(
2381		-	self.low.resolver, expr, *type, sub
2382		-	) else throw LowerError::MissingMetadata;
2383		-	return resolver::Type::ConstArgument { type, value };
2384		-	}
2385		-	case resolver::Type::Pointer(pointer) => {
2386		-	let target = try specializeType(self, *pointer.target);
2387		-	return resolver::Type::Pointer(resolver::PointerType {
2388		-	class: pointer.class,
2389		-	target: allocSpecializedType(self, target),
2390		-	mutable: pointer.mutable,
2391		-	});
2392		-	}
2393		-	case resolver::Type::Slice(slice) => {
2394		-	let item = try specializeType(self, *slice.item);
2395		-	return resolver::Type::Slice(resolver::SliceType {
2396		-	class: slice.class,
2397		-	item: allocSpecializedType(self, item),
2398		-	mutable: slice.mutable,
2399		-	});
2400		-	}
2401		-	case resolver::Type::Array(array) => {
2402		-	let item = try specializeType(self, *array.item);
2403		-	return resolver::Type::Array(resolver::ArrayType {
2404		-	item: allocSpecializedType(self, item),
2405		-	length: array.length,
2406		-	});
2407		-	}
2408		-	case resolver::Type::GenericArray { item, length } => {
2409		-	let concreteItem = try specializeType(self, *item);
2410		-	let value = resolver::constIntWithSubstitution(
2411		-	self.low.resolver, length, resolver::Type::U32, sub
2412		-	) else throw LowerError::MissingMetadata;
2413		-	return resolver::Type::Array(resolver::ArrayType {
2414		-	item: allocSpecializedType(self, concreteItem),
2415		-	length: value.magnitude as u32,
2416		-	});
2417		-	}
2418		-	case resolver::Type::Optional(inner) => {
2419		-	let value = try specializeType(self, *inner);
2420		-	return resolver::Type::Optional(allocSpecializedType(self, value));
2421		-	}
2422		-	case resolver::Type::GenericDataApply(app) => {
2423		-	let mut args: mut [resolver::Type] = &mut [];
2424		-	for arg in app.args {
2425		-	let concrete = try specializeType(self, *arg);
2426		-	if resolver::containsGenericParameter(concrete) {
2427		-	throw LowerError::MissingMetadata;
2428		-	}
2429		-	args.append(allocSpecializedType(self, concrete), self.allocator);
2430		-	}
2431		-	let specialization = resolver::findGenericDataSpecialization(
2432		-	self.low.resolver, app.template, &args[..]
2433		-	) else throw LowerError::MissingMetadata;
2434		-	return resolver::Type::Nominal(specialization.nominal);
2435		-	}
2436		-	case resolver::Type::GenericRecord(genericRecord) => {
2437		-	let mut fields: *mut [resolver::RecordField] = &mut [];
2438		-	let mut offset: u32 = 0;
2439		-	let mut alignment: u32 = 1;
2440		-	for field in genericRecord.fields {
2441		-	let fieldType = try specializeType(self, field.fieldType);
2442		-	if resolver::containsGenericParameter(fieldType) {
2443		-	throw LowerError::MissingMetadata;
2444		-	}
2445		-	let fieldLayout = resolver::getTypeLayout(fieldType);
2446		-	set offset = mem::alignUp(offset, fieldLayout.alignment);
2447		-	fields.append(resolver::RecordField {
2448		-	name: field.name,
2449		-	fieldType: persistStructuralType(self.low, fieldType),
2450		-	offset: offset as i32,
2451		-	}, self.low.allocator);
2452		-	set offset += fieldLayout.size;
2453		-	if fieldLayout.alignment > alignment {
2454		-	set alignment = fieldLayout.alignment;
2455		-	}
2456		-	}
2457		-	let nominal = try! alloc::alloc(
2458		-	self.low.arena,
2459		-	@sizeOf(resolver::NominalType),
2460		-	@alignOf(resolver::NominalType),
2461		-	) as *mut resolver::NominalType;
2462		-	set *nominal = resolver::NominalType::Record(resolver::RecordType {
2463		-	fields: &fields[..],
2464		-	labeled: genericRecord.labeled,
2465		-	layout: resolver::Layout {
2466		-	size: mem::alignUp(offset, alignment),
2467		-	alignment,
2468		-	},
2469		-	declaredLinear: false,
2470		-	});
2471		-	return resolver::Type::Nominal(nominal);
2472		-	}
2473		-	case resolver::Type::Fn(info) => {
2474		-	let mut params: mut [resolver::Type] = &mut [];
2475		-	let mut throwTypes: mut [resolver::Type] = &mut [];
2476		-	for param in info.paramTypes {
2477		-	let concrete = try specializeType(self, *param);
2478		-	params.append(allocSpecializedType(self, concrete), self.allocator);
2479		-	}
2480		-	for thrown in info.throwList {
2481		-	let concrete = try specializeType(self, *thrown);
2482		-	throwTypes.append(
2483		-	allocSpecializedType(self, concrete), self.allocator
2484		-	);
2485		-	}
2486		-	let result = try specializeType(self, *info.returnType);
2487		-	let fnType = try! alloc::alloc(
2488		-	self.low.fnArena,
2489		-	@sizeOf(resolver::FnType),
2490		-	@alignOf(resolver::FnType),
2491		-	) as *mut resolver::FnType;
2492		-	set *fnType = resolver::FnType {
2493		-	paramTypes: &params[..],
2494		-	returnType: allocSpecializedType(self, result),
2495		-	throwList: &throwTypes[..],
2496		-	isUnsafe: info.isUnsafe,
2497		-	localCount: info.localCount,
2498		-	};
2499		-	return resolver::Type::Fn(fnType);
2500		-	}
2501		-	case resolver::Type::Range { start, end } => {
2502		-	let mut concreteStart: ?*resolver::Type = nil;
2503		-	let mut concreteEnd: ?*resolver::Type = nil;
2504		-	if let value = start {
2505		-	let concrete = try specializeType(self, *value);
2506		-	set concreteStart = allocSpecializedType(self, concrete);
2507		-	}
2508		-	if let value = end {
2509		-	let concrete = try specializeType(self, *value);
2510		-	set concreteEnd = allocSpecializedType(self, concrete);
2511		-	}
2512		-	return resolver::Type::Range {
2513		-	start: concreteStart,
2514		-	end: concreteEnd,
2515		-	};
2516		-	}
2517		-	else => return ty,
2518		-	}
	2259	+	let specialized = resolver::substituteTypeReadOnly(
	2260	+	self.low.resolver,
	2261	+	ty,
	2262	+	sub,
	2263	+	self.low.fnArena,
	2264	+	self.low.arena,
	2265	+	) else throw LowerError::MissingMetadata;
	2266	+	return specialized;
2519	2267		}
2520	2268
2521	2269		/// Look up the resolved type of an AST node, or throw `MissingType`.
2522	2270		fn typeOf(self: mut FnLowerer, node: ast::Node) -> resolver::Type throws (LowerError) {
2523	2271		let ty = resolver::typeFor(self.low.resolver, node)

1437	1437		return Type::ConstParameter(param);
1438	1438		}
1439	1439		return Type::Parameter(param);
1440	1440		}
1441	1441
1442		-	/// Recursively replace rigid parameters in a resolved type.
1443		-	export fn substituteType(
1444		-	self: *mut Resolver,
	1442	+	/// Ownership and error policy for type substitution.
	1443	+	union TypeSubstitutionContext {
	1444	+	/// Resolver-owned substitution that may emit diagnostics.
	1445	+	Resolution {
	1446	+	/// Mutable resolver that owns the result.
	1447	+	resolver: *mut Resolver,
	1448	+	/// Source site for structural type diagnostics.
	1449	+	site: *ast::Node,
	1450	+	},
	1451	+	/// Read-only substitution into caller-owned arenas.
	1452	+	ReadOnly {
	1453	+	/// Immutable resolver metadata.
	1454	+	resolver: *Resolver,
	1455	+	/// Arena for function-local structural types.
	1456	+	structuralArena: *mut alloc::Arena,
	1457	+	/// Arena for structural types that outlive the function.
	1458	+	persistentArena: *mut alloc::Arena,
	1459	+	},
	1460	+	}
	1461	+
	1462	+	/// Return the arena for temporary structural substitution results.
	1463	+	fn substitutionArena(context: mut TypeSubstitutionContext) -> mut alloc::Arena {
	1464	+	match *context {
	1465	+	case TypeSubstitutionContext::Resolution { resolver, .. } =>
	1466	+	return &mut resolver.arena,
	1467	+	case TypeSubstitutionContext::ReadOnly { structuralArena, .. } =>
	1468	+	return structuralArena,
	1469	+	}
	1470	+	}
	1471	+
	1472	+	/// Allocate a nested substituted type with the selected ownership policy.
	1473	+	fn allocSubstitutedType(
	1474	+	context: *mut TypeSubstitutionContext,
	1475	+	ty: Type,
	1476	+	) -> *Type {
	1477	+	if let case TypeSubstitutionContext::Resolution { resolver, .. } = *context {
	1478	+	return allocType(resolver, ty);
	1479	+	}
	1480	+	let stored = try! alloc::alloc(
	1481	+	substitutionArena(context), @sizeOf(Type), @alignOf(Type)
	1482	+	) as *mut Type;
	1483	+	set *stored = ty;
	1484	+	return stored;
	1485	+	}
	1486	+
	1487	+	/// Allocate one type component in an explicit arena.
	1488	+	fn allocArenaType(arena: mut alloc::Arena, ty: Type) -> Type {
	1489	+	let stored = try! alloc::alloc(
	1490	+	arena, @sizeOf(Type), @alignOf(Type)
	1491	+	) as *mut Type;
	1492	+	set *stored = ty;
	1493	+	return stored;
	1494	+	}
	1495	+
	1496	+	/// Copy a concrete structural type into the given arena.
	1497	+	///
	1498	+	/// Nominal pointers retain their canonical identity.
	1499	+	export fn copyStructuralTypeToArena(
	1500	+	ty: Type,
	1501	+	arena: *mut alloc::Arena,
	1502	+	) -> Type {
	1503	+	match ty {
	1504	+	case Type::Pointer(pointer) => {
	1505	+	let target = copyStructuralTypeToArena(*pointer.target, arena);
	1506	+	return Type::Pointer(PointerType {
	1507	+	class: pointer.class,
	1508	+	target: allocArenaType(arena, target),
	1509	+	mutable: pointer.mutable,
	1510	+	});
	1511	+	}
	1512	+	case Type::Slice(slice) => {
	1513	+	let item = copyStructuralTypeToArena(*slice.item, arena);
	1514	+	return Type::Slice(SliceType {
	1515	+	class: slice.class,
	1516	+	item: allocArenaType(arena, item),
	1517	+	mutable: slice.mutable,
	1518	+	});
	1519	+	}
	1520	+	case Type::Array(array) => {
	1521	+	let item = copyStructuralTypeToArena(*array.item, arena);
	1522	+	return Type::Array(ArrayType {
	1523	+	item: allocArenaType(arena, item),
	1524	+	length: array.length,
	1525	+	});
	1526	+	}
	1527	+	case Type::Optional(inner) => {
	1528	+	let stored = copyStructuralTypeToArena(*inner, arena);
	1529	+	return Type::Optional(allocArenaType(arena, stored));
	1530	+	}
	1531	+	case Type::Fn(info) => {
	1532	+	let a = alloc::arenaAllocator(arena);
	1533	+	let mut params: mut [Type] = &mut [];
	1534	+	let mut throwList: mut [Type] = &mut [];
	1535	+	for param in info.paramTypes {
	1536	+	let stored = copyStructuralTypeToArena(*param, arena);
	1537	+	params.append(allocArenaType(arena, stored), a);
	1538	+	}
	1539	+	for thrown in info.throwList {
	1540	+	let stored = copyStructuralTypeToArena(*thrown, arena);
	1541	+	throwList.append(allocArenaType(arena, stored), a);
	1542	+	}
	1543	+	let returnType = copyStructuralTypeToArena(*info.returnType, arena);
	1544	+	let storedInfo = try! alloc::alloc(
	1545	+	arena, @sizeOf(FnType), @alignOf(FnType)
	1546	+	) as *mut FnType;
	1547	+	set *storedInfo = FnType {
	1548	+	paramTypes: &params[..],
	1549	+	returnType: allocArenaType(arena, returnType),
	1550	+	throwList: &throwList[..],
	1551	+	isUnsafe: info.isUnsafe,
	1552	+	localCount: info.localCount,
	1553	+	};
	1554	+	return Type::Fn(storedInfo);
	1555	+	}
	1556	+	case Type::Range { start, end } => {
	1557	+	let mut storedStart: ?*Type = nil;
	1558	+	let mut storedEnd: ?*Type = nil;
	1559	+	if let value = start {
	1560	+	let stored = copyStructuralTypeToArena(*value, arena);
	1561	+	set storedStart = allocArenaType(arena, stored);
	1562	+	}
	1563	+	if let value = end {
	1564	+	let stored = copyStructuralTypeToArena(*value, arena);
	1565	+	set storedEnd = allocArenaType(arena, stored);
	1566	+	}
	1567	+	return Type::Range { start: storedStart, end: storedEnd };
	1568	+	}
	1569	+	else => return ty,
	1570	+	}
	1571	+	}
	1572	+
	1573	+	/// Recursively replace rigid parameters under the selected policy.
	1574	+	fn substituteTypeWithContext(
	1575	+	context: *mut TypeSubstitutionContext,
1445	1576		ty: Type,
1446	1577		sub: *Substitution,
1447		-	site: *ast::Node,
1448	1578		) -> Type throws (ResolveError) {
1449	1579		if not containsGenericParameter(ty) {
1450	1580		return ty;
1451	1581		}
1452	1582		match ty {
1453	1583		case Type::Parameter(param) => return substitutionArg(sub, param),
1454	1584		case Type::ConstParameter(param) => return substitutionArg(sub, param),
1455	1585		case Type::GenericConstExpr { type, expr } => {
1456		-	let value = constValueWithSubstitution(self, expr, sub)
1457		-	else throw emitError(self, expr, ErrorKind::ConstExprRequired);
1458		-	let case ConstValue::Int(int) = value
1459		-	else throw emitError(self, expr, ErrorKind::ConstExprRequired);
1460		-	if not validateConstIntRange(value, *type) {
1461		-	throw emitError(self, expr, ErrorKind::NumericLiteralOverflow);
	1586	+	match *context {
	1587	+	case TypeSubstitutionContext::Resolution { resolver, .. } => {
	1588	+	let value = constValueWithSubstitution(resolver, expr, sub)
	1589	+	else throw emitError(resolver, expr, ErrorKind::ConstExprRequired);
	1590	+	let case ConstValue::Int(int) = value
	1591	+	else throw emitError(resolver, expr, ErrorKind::ConstExprRequired);
	1592	+	if not validateConstIntRange(value, *type) {
	1593	+	throw emitError(resolver, expr, ErrorKind::NumericLiteralOverflow);
	1594	+	}
	1595	+	let case ConstValue::Int(canonical) = castConstInt(int, *type)
	1596	+	else throw emitError(resolver, expr, ErrorKind::Internal);
	1597	+	return Type::ConstArgument { type, value: canonical };
	1598	+	}
	1599	+	case TypeSubstitutionContext::ReadOnly { resolver, .. } => {
	1600	+	let value = constIntWithSubstitution(resolver, expr, *type, sub)
	1601	+	else throw ResolveError::Failure;
	1602	+	return Type::ConstArgument { type, value };
	1603	+	}
1462	1604		}
1463		-	let case ConstValue::Int(canonical) = castConstInt(int, *type)
1464		-	else throw emitError(self, expr, ErrorKind::Internal);
1465		-	return Type::ConstArgument { type, value: canonical };
1466	1605		}
1467	1606		case Type::Pointer(pointer) => {
1468		-	let inner = try substituteType(self, *pointer.target, sub, site);
	1607	+	let inner = try substituteTypeWithContext(context, *pointer.target, sub);
1469	1608		return Type::Pointer(PointerType {
1470	1609		class: pointer.class,
1471		-	target: allocType(self, inner),
	1610	+	target: allocSubstitutedType(context, inner),
1472	1611		mutable: pointer.mutable,
1473	1612		});
1474	1613		}
1475	1614		case Type::Slice(slice) => {
1476		-	let inner = try substituteType(self, *slice.item, sub, site);
	1615	+	let inner = try substituteTypeWithContext(context, *slice.item, sub);
1477	1616		return Type::Slice(SliceType {
1478	1617		class: slice.class,
1479		-	item: allocType(self, inner),
	1618	+	item: allocSubstitutedType(context, inner),
1480	1619		mutable: slice.mutable,
1481	1620		});
1482	1621		}
1483	1622		case Type::Array(array) => {
1484		-	let item = try substituteType(self, *array.item, sub, site);
	1623	+	let item = try substituteTypeWithContext(context, *array.item, sub);
1485	1624		return Type::Array(ArrayType {
1486		-	item: allocType(self, item),
	1625	+	item: allocSubstitutedType(context, item),
1487	1626		length: array.length,
1488	1627		});
1489	1628		}
1490	1629		case Type::GenericArray { item, length } => {
1491		-	let concreteItem = try substituteType(self, *item, sub, site);
1492		-	let value = constValueWithSubstitution(self, length, sub)
1493		-	else throw emitError(self, length, ErrorKind::ConstExprRequired);
1494		-	if not validateConstIntRange(value, Type::U32) {
1495		-	throw emitError(self, length, ErrorKind::NumericLiteralOverflow);
	1630	+	let concreteItem = try substituteTypeWithContext(context, *item, sub);
	1631	+	let mut arrayLength: u32 = 0;
	1632	+	match *context {
	1633	+	case TypeSubstitutionContext::Resolution { resolver, .. } => {
	1634	+	let value = constValueWithSubstitution(resolver, length, sub)
	1635	+	else throw emitError(resolver, length, ErrorKind::ConstExprRequired);
	1636	+	if not validateConstIntRange(value, Type::U32) {
	1637	+	throw emitError(resolver, length, ErrorKind::NumericLiteralOverflow);
	1638	+	}
	1639	+	let case ConstValue::Int(int) = value
	1640	+	else throw emitError(resolver, length, ErrorKind::ConstExprRequired);
	1641	+	set arrayLength = int.magnitude as u32;
	1642	+	}
	1643	+	case TypeSubstitutionContext::ReadOnly { resolver, .. } => {
	1644	+	let value = constIntWithSubstitution(
	1645	+	resolver, length, Type::U32, sub
	1646	+	) else throw ResolveError::Failure;
	1647	+	set arrayLength = value.magnitude as u32;
	1648	+	}
1496	1649		}
1497		-	let case ConstValue::Int(int) = value
1498		-	else throw emitError(self, length, ErrorKind::ConstExprRequired);
1499	1650		return Type::Array(ArrayType {
1500		-	item: allocType(self, concreteItem),
1501		-	length: int.magnitude as u32,
	1651	+	item: allocSubstitutedType(context, concreteItem),
	1652	+	length: arrayLength,
1502	1653		});
1503	1654		}
1504	1655		case Type::Optional(inner) => {
1505		-	let value = try substituteType(self, *inner, sub, site);
1506		-	return Type::Optional(allocType(self, value));
	1656	+	let value = try substituteTypeWithContext(context, *inner, sub);
	1657	+	return Type::Optional(allocSubstitutedType(context, value));
1507	1658		}
1508	1659		case Type::GenericDataApply(app) => {
1509		-	let a = alloc::arenaAllocator(&mut self.arena);
	1660	+	let a = alloc::arenaAllocator(substitutionArena(context));
1510	1661		let mut args: mut [Type] = &mut [];
1511	1662		let mut symbolic = false;
1512	1663		for arg in app.args {
1513		-	let replacement = try substituteType(self, *arg, sub, site);
	1664	+	let replacement = try substituteTypeWithContext(context, *arg, sub);
1514	1665		set symbolic = symbolic or containsGenericParameter(replacement);
1515		-	args.append(allocType(self, replacement), a);
1516		-	}
1517		-	if symbolic {
1518		-	let application = try! alloc::alloc(
1519		-	&mut self.arena,
1520		-	@sizeOf(GenericDataApplyType),
1521		-	@alignOf(GenericDataApplyType),
1522		-	) as *mut GenericDataApplyType;
1523		-	set *application = GenericDataApplyType {
1524		-	template: app.template,
1525		-	args: &args[..],
1526		-	site: app.site,
1527		-	};
1528		-	return Type::GenericDataApply(application);
	1666	+	args.append(allocSubstitutedType(context, replacement), a);
	1667	+	}
	1668	+	match *context {
	1669	+	case TypeSubstitutionContext::Resolution { resolver, .. } => {
	1670	+	if symbolic {
	1671	+	let application = try! alloc::alloc(
	1672	+	&mut resolver.arena,
	1673	+	@sizeOf(GenericDataApplyType),
	1674	+	@alignOf(GenericDataApplyType),
	1675	+	) as *mut GenericDataApplyType;
	1676	+	set *application = GenericDataApplyType {
	1677	+	template: app.template,
	1678	+	args: &args[..],
	1679	+	site: app.site,
	1680	+	};
	1681	+	return Type::GenericDataApply(application);
	1682	+	}
	1683	+	let nominal = try specializeGenericData(
	1684	+	resolver, app.site, app.template, &args[..], false
	1685	+	);
	1686	+	return Type::Nominal(nominal);
	1687	+	}
	1688	+	case TypeSubstitutionContext::ReadOnly { resolver, .. } => {
	1689	+	if symbolic {
	1690	+	throw ResolveError::Failure;
	1691	+	}
	1692	+	let specialization = findGenericDataSpecialization(
	1693	+	resolver, app.template, &args[..]
	1694	+	) else throw ResolveError::Failure;
	1695	+	return Type::Nominal(specialization.nominal);
	1696	+	}
1529	1697		}
1530		-	let nominal = try specializeGenericData(
1531		-	self, app.site, app.template, &args[..], false
1532		-	);
1533		-	return Type::Nominal(nominal);
1534	1698		}
1535	1699		case Type::GenericRecord(rec) => {
1536		-	let a = alloc::arenaAllocator(&mut self.arena);
	1700	+	let mut persistentArena = substitutionArena(context);
	1701	+	if let case TypeSubstitutionContext::ReadOnly {
	1702	+	persistentArena: arena,
	1703	+	..
	1704	+	} = *context {
	1705	+	set persistentArena = arena;
	1706	+	}
	1707	+	let a = alloc::arenaAllocator(persistentArena);
1537	1708		let mut fields: *mut [RecordField] = &mut [];
1538	1709		let mut offset: u32 = 0;
1539	1710		let mut alignment: u32 = 1;
1540	1711		for field in rec.fields {
1541		-	let fieldType = try substituteType(self, field.fieldType, sub, site);
1542		-	if hasUnresolvedNominalLayout(fieldType) {
1543		-	throw emitError(self, site, ErrorKind::GenericRecursiveLayout);
	1712	+	let fieldType = try substituteTypeWithContext(
	1713	+	context, field.fieldType, sub
	1714	+	);
	1715	+	let mut storedFieldType = fieldType;
	1716	+	match *context {
	1717	+	case TypeSubstitutionContext::Resolution { resolver, site } => {
	1718	+	if hasUnresolvedNominalLayout(fieldType) {
	1719	+	throw emitError(
	1720	+	resolver, site, ErrorKind::GenericRecursiveLayout
	1721	+	);
	1722	+	}
	1723	+	try ensureStorableType(resolver, site, fieldType);
	1724	+	try ensureTypeResolved(resolver, fieldType, site);
	1725	+	}
	1726	+	case TypeSubstitutionContext::ReadOnly { .. } => {
	1727	+	if containsGenericParameter(fieldType) {
	1728	+	throw ResolveError::Failure;
	1729	+	}
	1730	+	set storedFieldType = copyStructuralTypeToArena(
	1731	+	fieldType, persistentArena
	1732	+	);
	1733	+	}
1544	1734		}
1545		-	try ensureStorableType(self, site, fieldType);
1546		-	try ensureTypeResolved(self, fieldType, site);
1547	1735		let fieldLayout = getTypeLayout(fieldType);
1548	1736		set offset = mem::alignUp(offset, fieldLayout.alignment);
1549	1737		fields.append(RecordField {
1550	1738		name: field.name,
1551		-	fieldType,
	1739	+	fieldType: storedFieldType,
1552	1740		offset: offset as i32,
1553	1741		}, a);
1554	1742		set offset += fieldLayout.size;
1555	1743		set alignment = max(alignment, fieldLayout.alignment);
1556	1744		}
1557		-	let layout = Layout {
1558		-	size: mem::alignUp(offset, alignment),
1559		-	alignment,
1560		-	};
1561		-	return Type::Nominal(allocNominalType(self, NominalType::Record(RecordType {
	1745	+	let nominal = try! alloc::alloc(
	1746	+	persistentArena, @sizeOf(NominalType), @alignOf(NominalType)
	1747	+	) as *mut NominalType;
	1748	+	set *nominal = NominalType::Record(RecordType {
1562	1749		fields: &fields[..],
1563	1750		labeled: rec.labeled,
1564		-	layout,
	1751	+	layout: Layout {
	1752	+	size: mem::alignUp(offset, alignment),
	1753	+	alignment,
	1754	+	},
1565	1755		declaredLinear: false,
1566		-	})));
	1756	+	});
	1757	+	return Type::Nominal(nominal);
1567	1758		}
1568	1759		case Type::Fn(info) => {
1569		-	let a = alloc::arenaAllocator(&mut self.arena);
	1760	+	let arena = substitutionArena(context);
	1761	+	let a = alloc::arenaAllocator(arena);
1570	1762		let mut params: mut [Type] = &mut [];
1571	1763		let mut throwTypes: mut [Type] = &mut [];
1572	1764		for param in info.paramTypes {
1573		-	let concrete = try substituteType(self, *param, sub, site);
1574		-	params.append(allocType(self, concrete), a);
	1765	+	let concrete = try substituteTypeWithContext(context, *param, sub);
	1766	+	params.append(allocSubstitutedType(context, concrete), a);
1575	1767		}
1576	1768		for thrown in info.throwList {
1577		-	let concrete = try substituteType(self, *thrown, sub, site);
1578		-	throwTypes.append(allocType(self, concrete), a);
	1769	+	let concrete = try substituteTypeWithContext(context, *thrown, sub);
	1770	+	throwTypes.append(allocSubstitutedType(context, concrete), a);
1579	1771		}
1580		-	let result = try substituteType(self, *info.returnType, sub, site);
1581		-	return Type::Fn(allocFnType(self, FnType {
	1772	+	let result = try substituteTypeWithContext(
	1773	+	context, *info.returnType, sub
	1774	+	);
	1775	+	let fnType = try! alloc::alloc(
	1776	+	arena, @sizeOf(FnType), @alignOf(FnType)
	1777	+	) as *mut FnType;
	1778	+	set *fnType = FnType {
1582	1779		paramTypes: &params[..],
1583		-	returnType: allocType(self, result),
	1780	+	returnType: allocSubstitutedType(context, result),
1584	1781		throwList: &throwTypes[..],
1585	1782		isUnsafe: info.isUnsafe,
1586	1783		localCount: info.localCount,
1587		-	}));
	1784	+	};
	1785	+	return Type::Fn(fnType);
1588	1786		}
1589	1787		case Type::Range { start, end } => {
1590	1788		let mut newStart: ?*Type = nil;
1591	1789		let mut newEnd: ?*Type = nil;
1592	1790		if let value = start {
1593		-	let concrete = try substituteType(self, *value, sub, site);
1594		-	set newStart = allocType(self, concrete);
	1791	+	let concrete = try substituteTypeWithContext(context, *value, sub);
	1792	+	set newStart = allocSubstitutedType(context, concrete);
1595	1793		}
1596	1794		if let value = end {
1597		-	let concrete = try substituteType(self, *value, sub, site);
1598		-	set newEnd = allocType(self, concrete);
	1795	+	let concrete = try substituteTypeWithContext(context, *value, sub);
	1796	+	set newEnd = allocSubstitutedType(context, concrete);
1599	1797		}
1600	1798		return Type::Range { start: newStart, end: newEnd };
1601	1799		}
1602	1800		else => return ty,
1603	1801		}
1604	1802		}
1605	1803
	1804	+	/// Recursively replace rigid parameters in a resolved type.
	1805	+	export fn substituteType(
	1806	+	self: *mut Resolver,
	1807	+	ty: Type,
	1808	+	sub: *Substitution,
	1809	+	site: *ast::Node,
	1810	+	) -> Type throws (ResolveError) {
	1811	+	let mut context = TypeSubstitutionContext::Resolution {
	1812	+	resolver: self,
	1813	+	site,
	1814	+	};
	1815	+	return try substituteTypeWithContext(&mut context, ty, sub);
	1816	+	}
	1817	+
	1818	+	/// Substitute a type using immutable metadata and caller-owned arenas.
	1819	+	///
	1820	+	/// Return `nil` when required specialization metadata is missing.
	1821	+	export fn substituteTypeReadOnly(
	1822	+	self: *Resolver,
	1823	+	ty: Type,
	1824	+	sub: *Substitution,
	1825	+	structuralArena: *mut alloc::Arena,
	1826	+	persistentArena: *mut alloc::Arena,
	1827	+	) -> ?Type {
	1828	+	let mut context = TypeSubstitutionContext::ReadOnly {
	1829	+	resolver: self,
	1830	+	structuralArena,
	1831	+	persistentArena,
	1832	+	};
	1833	+	return try substituteTypeWithContext(&mut context, ty, sub) catch {
	1834	+	return nil;
	1835	+	};
	1836	+	}
	1837	+
1606	1838		/// Allocate a nominal type descriptor and return a pointer to it.
1607	1839		fn allocNominalType(self: mut Resolver, info: NominalType) -> mut NominalType {
1608	1840		// Nb. We don't attempt to de-duplicate nominal type entries,
1609	1841		// since they don't carry node information and we create
1610	1842		// placeholder entries when binding symbols.