radiance · commit

Resolve instance blocks

9de503edfb98f06115572a7017dbb5bb92a014cd57c3480b24b6c1ead41ef39b

After this commit, `instance Trait for Type { ... }` is fully
validated. Missing methods, signature mismatches, and wrong receiver
types are caught and reported.

Alexis Sellier committed 1 month ago 1 parent ffdd11dd

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

/// Nb. This should not be raised above `255`,
/// as tags are stored using 8-bits only.
pub const MAX_UNION_VARIANTS: u32 = 128;
/// Maximum nesting of loops.
pub const MAX_LOOP_DEPTH: u32 = 16;
/// Maximum trait instances.
pub const MAX_INSTANCES: u32 = 128;

/// Trait definition stored in the resolver.
pub record TraitType {
    /// Trait name.
    name: *[u8],

    name: *[u8],
    /// Function type for the method, excluding the receiver.
    fnType: *FnType,
    /// Whether the receiver is mutable.
    mutable: bool,
    /// Vtable slot index.
    /// V-table slot index.
    index: u32,
}

/// An entry in the trait instance registry.
pub record InstanceEntry {
    /// Trait type descriptor.
    traitType: *TraitType,
    /// Concrete type that implements the trait.
    concreteType: Type,
    /// Name of the concrete type.
    concreteTypeName: *[u8],
    /// Module where this instance was declared.
    moduleId: u16,
    /// Method symbols for each trait method, in declaration order.
    methods: [*mut Symbol; ast::MAX_TRAIT_METHODS],
    /// Number of methods.
    methodsLen: u32,
}

/// Identifier for the synthetic `len` field.
pub const LEN_FIELD: *[u8] = "len";
/// Identifier for the synthetic `ptr` field.
pub const PTR_FIELD: *[u8] = "ptr";


    BuiltinArgCountMismatch(CountMismatch),
    /// Instance method receiver mutability does not match the trait declaration.
    ReceiverMutabilityMismatch,
    /// Duplicate instance declaration for the same (trait, type) pair.
    DuplicateInstance,
    /// Instance declaration is missing a required trait method.
    MissingTraitMethod(*[u8]),
    /// Trait name used as a value expression.
    UnexpectedTraitName,
    /// Trait method receiver does not point to the declaring trait.
    TraitReceiverMismatch,
    /// Function declaration has too many parameters.

    /// Module graph for the current package.
    moduleGraph: *module::ModuleGraph,
    /// Cache of module scopes indexed by module ID.
    // TODO: Why is this optional?
    moduleScopes: [?*mut Scope; module::MAX_MODULES],
    /// Trait instance registry.
    instances: [InstanceEntry; MAX_INSTANCES],
    /// Number of registered instances.
    instancesLen: u32,
}

/// Internal error sentinel thrown when analysis cannot proceed.
pub union ResolveError {
    Failure,

        types: nil,
        errors: errorList(storage.errors),
        // TODO: Shouldn't be undefined.
        moduleGraph: undefined,
        moduleScopes,
        instances: undefined,
        instancesLen: 0,
    };
}

/// Return `true` if there are no errors in the diagnostics.
pub fn success(diag: *Diagnostics) -> bool {

            // Handled in previous pass.
        }
        case ast::NodeValue::Use(_) => {
            // Handled in previous pass.
        }
        case ast::NodeValue::InstanceDecl { traitName, targetType, methods } => {
            try resolveInstanceDecl(self, node, traitName, targetType, &methods);
        }
        else => {
            // Ignore non-declaration nodes.
        }
    }
}

            // Skip: already analyzed in declaration phase.
        }
        case ast::NodeValue::Use(_) => {
            // Skip: already analyzed in declaration phase.
        }
        case ast::NodeValue::TraitDecl { .. } => {
            // Skip: already analyzed in declaration phase.
        }
        case ast::NodeValue::InstanceDecl { methods, .. } => {
            try resolveInstanceMethodBodies(self, &methods);
        }
        else => {
            // FIXME: This allows module-level statements that should
            // normally only be valid inside function bodies. We currently
            // need this because of how tests are written, but it should
            // be eventually removed.


        try setNodeType(self, methodNode, Type::Void);
    }
}

/// Resolve a name path node to a symbol.
/// Used for trait and type references in instance declarations and trait objects.
fn resolveNamePath(self: *mut Resolver, node: *ast::Node) -> *mut Symbol
    throws (ResolveError)
{
    match node.value {
        case ast::NodeValue::Ident(name) => {
            let sym = findAnySymbol(self.scope, name)
                else throw emitError(self, node, ErrorKind::UnresolvedSymbol(name));
            return sym;
        }
        case ast::NodeValue::ScopeAccess(access) => {
            return try resolveAccess(self, node, access, self.scope);
        }
        else => {
            throw emitError(self, node, ErrorKind::ExpectedIdentifier);
        }
    }
}

/// Resolve an instance declaration.
/// Validates that the trait exists, the target type exists, and all methods
/// match the trait's signatures.
fn resolveInstanceDecl(
    self: *mut Resolver,
    node: *ast::Node,
    traitName: *ast::Node,
    targetType: *ast::Node,
    methods: *ast::NodeList
) throws (ResolveError) {
    // Look up the trait.
    let traitSym = try resolveNamePath(self, traitName);
    let case SymbolData::Trait(traitInfo) = traitSym.data
        else throw emitError(self, traitName, ErrorKind::Internal);

    try setNodeSymbol(self, traitName, traitSym);

    // Look up the target type.
    let typeSym = try resolveNamePath(self, targetType);
    let case SymbolData::Type(nominalTy) = typeSym.data
        else throw emitError(self, targetType, ErrorKind::Internal);
    try setNodeSymbol(self, targetType, typeSym);
    // Ensure the concrete type body is resolved.
    try ensureNominalResolved(self, nominalTy, targetType);

    // Reject duplicate instance for the same (trait, type) pair.
    let concreteType = Type::Nominal(nominalTy);
    if let _ = findInstance(self, traitInfo, concreteType) {
        throw emitError(self, node, ErrorKind::DuplicateInstance);
    }

    // Build the instance entry.
    if self.instancesLen >= MAX_INSTANCES {
        throw emitError(self, node, ErrorKind::Internal);
    }
    let mut entry = InstanceEntry {
        traitType: traitInfo,
        concreteType,
        concreteTypeName: typeSym.name,
        moduleId: self.currentMod,
        methods: undefined,
        methodsLen: 0,
    };
    // Track which trait methods are covered by the instance.
    let mut covered: [bool; ast::MAX_TRAIT_METHODS] = [false; ast::MAX_TRAIT_METHODS];

    // Match each instance method to a trait method.
    for i in 0..methods.len {
        let methodNode = methods.list[i];
        let case ast::NodeValue::InstanceMethodDecl {
            name, receiverName, receiverType, sig, body
        } = methodNode.value else continue;

        let methodName = try nodeName(self, name);

        // Find the matching trait method.
        let mut traitMethod: ?*TraitMethod = nil;
        for j in 0..traitInfo.methodsLen {
            if traitInfo.methods[j].name == methodName {
                traitMethod = &traitInfo.methods[j];
                break;
            }
        }
        let tm = traitMethod
            else throw emitError(self, name, ErrorKind::UnresolvedSymbol(methodName));

        // Determine receiver mutability and validate receiver type.
        let mut receiverMut = false;
        if let case ast::NodeValue::TypeSig(typeSig) = receiverType.value {
            if let case ast::TypeSig::Pointer { mutable, valueType } = typeSig {
                receiverMut = mutable;
                // Validate that the receiver type annotation matches the
                // concrete type from the instance declaration.
                let annotatedTy = try infer(self, valueType);
                if not typesEqual(annotatedTy, concreteType) {
                    throw emitTypeMismatch(self, receiverType, TypeMismatch {
                        expected: concreteType,
                        actual: annotatedTy,
                    });
                }
            }
        }

        // Check receiver mutability matches in both directions.
        if tm.mutable and not receiverMut {
            throw emitError(self, receiverType, ErrorKind::ImmutableBinding);
        }
        if receiverMut and not tm.mutable {
            throw emitError(self, receiverType, ErrorKind::ReceiverMutabilityMismatch);
        }

        // Build the function type for the instance method.
        // The receiver becomes the first parameter.
        let mut fnType = FnType {
            paramTypes: undefined,
            paramTypesLen: 0,
            returnType: allocType(self, Type::Void),
            throwList: undefined,
            throwListLen: 0,
            localCount: 0,
        };
        // First param is the receiver.
        let receiverPtrType = Type::Pointer {
            target: allocType(self, concreteType),
            mutable: receiverMut,
        };
        fnType.paramTypes[0] = allocType(self, receiverPtrType);
        fnType.paramTypesLen = 1;

        // Add the other params from the trait method and validate that
        // the instance method's declared parameter types match.
        if sig.params.len != tm.fnType.paramTypesLen {
            throw emitError(self, methodNode, ErrorKind::FnArgCountMismatch(CountMismatch {
                expected: tm.fnType.paramTypesLen,
                actual: sig.params.len,
            }));
        }
        for j in 0..tm.fnType.paramTypesLen {
            // Resolve the instance method's declared parameter type.
            let paramNode = sig.params.list[j];
            let case ast::NodeValue::FnParam(param) = paramNode.value
                else throw emitError(self, paramNode, ErrorKind::ExpectedIdentifier);
            let instanceParamTy = try resolveValueType(self, param.type);
            let traitParamTy = *tm.fnType.paramTypes[j];

            if not typesEqual(instanceParamTy, traitParamTy) {
                throw emitTypeMismatch(self, paramNode, TypeMismatch {
                    expected: traitParamTy,
                    actual: instanceParamTy,
                });
            }
            fnType.paramTypes[fnType.paramTypesLen] = tm.fnType.paramTypes[j];
            fnType.paramTypesLen += 1;
        }
        fnType.returnType = tm.fnType.returnType;

        // Copy throws list from the trait method.
        for j in 0..tm.fnType.throwListLen {
            fnType.throwList[fnType.throwListLen] = tm.fnType.throwList[j];
            fnType.throwListLen += 1;
        }

        // Create a symbol for the instance method without binding it into the
        // module scope. Instance methods are dispatched via v-table, so they
        // must not pollute the enclosing scope.
        let fnTy = Type::Fn(allocFnType(self, fnType));
        let mName = try nodeName(self, name);
        let sym = allocSymbol(self, SymbolData::Value {
            mutable: false, alignment: 0, type: fnTy, addressTaken: false,
        }, mName, methodNode, 0);

        try setNodeSymbol(self, methodNode, sym);
        try setNodeType(self, methodNode, fnTy);
        try setNodeType(self, name, fnTy);

        // Store in instance entry at the matching v-table slot.
        entry.methods[tm.index] = sym;
        entry.methodsLen += 1;

        covered[tm.index] = true;
    }

    // Check that all trait methods are implemented.
    for i in 0..traitInfo.methodsLen {
        if not covered[i] {
            throw emitError(self, node, ErrorKind::MissingTraitMethod(traitInfo.methods[i].name));
        }
    }
    self.instances[self.instancesLen] = entry;
    self.instancesLen += 1;

    try setNodeType(self, node, Type::Void);
}

/// Resolve instance method bodies.
fn resolveInstanceMethodBodies(self: *mut Resolver, methods: *ast::NodeList)
    throws (ResolveError)
{
    for i in 0..methods.len {
        let methodNode = methods.list[i];
        let case ast::NodeValue::InstanceMethodDecl {
            name, receiverName, receiverType, sig, body
        } = methodNode.value else continue;

        // Symbol may be absent if [`resolveInstanceDecl`] reported an error
        // for this method (eg. unknown method name). Skip gracefully.
        let sym = symbolFor(self, methodNode)
            else continue;
        let case SymbolData::Value { type, .. } = sym.data
            else panic "resolveInstanceMethodBodies: expected value symbol";
        let case Type::Fn(fnType) = type
            else panic "resolveInstanceMethodBodies: expected function type";

        // Enter function scope.
        enterFn(self, methodNode, fnType);

        // Bind the receiver parameter.
        let receiverTy = *fnType.paramTypes[0];
        try bindValueIdent(self, receiverName, receiverName, receiverTy, false, 0, 0) catch {
            exitFn(self);
            throw ResolveError::Failure;
        };
        // Bind the remaining parameters from the signature.
        for j in 0..sig.params.len {
            let paramNode = sig.params.list[j];
            let paramTy = try infer(self, paramNode) catch {
                exitFn(self);
                throw ResolveError::Failure;
            };
        }

        // Resolve the body.
        let retTy = *fnType.returnType;
        let bodyTy = try checkAssignable(self, body, Type::Void) catch {
            exitFn(self);
            throw ResolveError::Failure;
        };
        if retTy != Type::Void and bodyTy != Type::Never {
            exitFn(self);
            throw emitError(self, body, ErrorKind::FnMissingReturn);
        }
        exitFn(self);
    }
}

/// Look up an instance entry by trait and concrete type.
fn findInstance(self: *Resolver, traitInfo: *TraitType, concreteType: Type) -> ?*InstanceEntry {
    for i in 0..self.instancesLen {
        let entry = &self.instances[i];
        if entry.traitType == traitInfo and typesEqual(entry.concreteType, concreteType) {
            return entry;
        }
    }
    return nil;
}

/// Resolve union variant types after all type names are bound (Phase 2 of type resolution).
fn resolveUnionBody(self: *mut Resolver, node: *ast::Node, decl: ast::UnionDecl)
    throws (ResolveError)
{
    // Get the type symbol that was bound to this declaration node.

                fnType.returnType = allocType(self, Type::Void);
            }
            return Type::Fn(allocFnType(self, fnType));
        }
        case ast::TypeSig::TraitObject { traitName, mutable } => {
            let name = try nodeName(self, traitName);
            let sym = findAnySymbol(self.scope, name)
                else throw emitError(self, traitName, ErrorKind::UnresolvedSymbol(name));
            let sym = try resolveNamePath(self, traitName);
            let case SymbolData::Trait(traitInfo) = sym.data
                else throw emitError(self, traitName, ErrorKind::Internal);
            try setNodeSymbol(self, traitName, sym);

            return Type::TraitObject { traitInfo, mutable };

lib/std/lang/resolver/printer.rad +5 -0

            io::print("instance receiver mutability does not match trait declaration");
        }
        case super::ErrorKind::DuplicateInstance => {
            io::print("duplicate instance declaration for the same trait and type");
        }
        case super::ErrorKind::MissingTraitMethod(name) => {
            io::print("missing trait method '");
            io::print(name);
            io::print("'");
        }
        case super::ErrorKind::UnexpectedTraitName => {
            io::print("trait name cannot be used as a value");
        }
        case super::ErrorKind::TraitReceiverMismatch => {
            io::print("trait method receiver must be a pointer to the declaring trait");

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

        if let case super::ErrorKind::UnionMatchNonExhaustive(actualName) = *actual {
            return mem::eq(actualName, expectedName);
        }
        return false;
    }
    if let case super::ErrorKind::MissingTraitMethod(expectedName) = expected {
        if let case super::ErrorKind::MissingTraitMethod(actualName) = *actual {
            return mem::eq(actualName, expectedName);
        }
        return false;
    }
    return *actual == expected;
}

/// Extract the first error and ensure it has the expected kind.
fn expectErrorKind(result: *TestResult, kind: super::ErrorKind) -> *super::Error

    let mut a = testResolver();
    let program = "union ErrA { A } union ErrB { B } fn f() -> i32 throws (ErrA, ErrB) { throw ErrA::A(); return 0; } fn g() -> i32 { return try f() catch e { return 0; }; }";
    let result = try resolveProgramStr(&mut a, program);
    try expectErrorKind(&result, super::ErrorKind::TryCatchMultiError);
}

@test fn testInstanceMissingMethod() throws (testing::TestError) {
    let mut a = testResolver();
    let program = "trait S { fn (*S) f() -> i32; } record R { x: i32 } instance S for R {}";
    let result = try resolveProgramStr(&mut a, program);
    try expectErrorKind(&result, super::ErrorKind::MissingTraitMethod("f"));
}

@test fn testInstanceUnknownMethod() throws (testing::TestError) {
    let mut a = testResolver();
    let program = "trait S { fn (*S) f() -> i32; } record R { x: i32 } instance S for R { fn (self: *R) x() -> i32 { return 0; } }";
    let result = try resolveProgramStr(&mut a, program);
    try expectErrorKind(&result, super::ErrorKind::UnresolvedSymbol("x"));
}

60	62		name: *[u8],
61	63		/// Function type for the method, excluding the receiver.
62	64		fnType: *FnType,
63	65		/// Whether the receiver is mutable.
64	66		mutable: bool,
65		-	/// Vtable slot index.
	67	+	/// V-table slot index.
66	68		index: u32,
67	69		}
68	70
	71	+	/// An entry in the trait instance registry.
	72	+	pub record InstanceEntry {
	73	+	/// Trait type descriptor.
	74	+	traitType: *TraitType,
	75	+	/// Concrete type that implements the trait.
	76	+	concreteType: Type,
	77	+	/// Name of the concrete type.
	78	+	concreteTypeName: *[u8],
	79	+	/// Module where this instance was declared.
	80	+	moduleId: u16,
	81	+	/// Method symbols for each trait method, in declaration order.
	82	+	methods: [*mut Symbol; ast::MAX_TRAIT_METHODS],
	83	+	/// Number of methods.
	84	+	methodsLen: u32,
	85	+	}
	86	+
69	87		/// Identifier for the synthetic `len` field.
70	88		pub const LEN_FIELD: *[u8] = "len";
71	89		/// Identifier for the synthetic `ptr` field.
72	90		pub const PTR_FIELD: *[u8] = "ptr";
73	91

528	546		BuiltinArgCountMismatch(CountMismatch),
529	547		/// Instance method receiver mutability does not match the trait declaration.
530	548		ReceiverMutabilityMismatch,
531	549		/// Duplicate instance declaration for the same (trait, type) pair.
532	550		DuplicateInstance,
	551	+	/// Instance declaration is missing a required trait method.
	552	+	MissingTraitMethod(*[u8]),
533	553		/// Trait name used as a value expression.
534	554		UnexpectedTraitName,
535	555		/// Trait method receiver does not point to the declaring trait.
536	556		TraitReceiverMismatch,
537	557		/// Function declaration has too many parameters.

720	740		/// Module graph for the current package.
721	741		moduleGraph: *module::ModuleGraph,
722	742		/// Cache of module scopes indexed by module ID.
723	743		// TODO: Why is this optional?
724	744		moduleScopes: [?*mut Scope; module::MAX_MODULES],
	745	+	/// Trait instance registry.
	746	+	instances: [InstanceEntry; MAX_INSTANCES],
	747	+	/// Number of registered instances.
	748	+	instancesLen: u32,
725	749		}
726	750
727	751		/// Internal error sentinel thrown when analysis cannot proceed.
728	752		pub union ResolveError {
729	753		Failure,

861	885		types: nil,
862	886		errors: errorList(storage.errors),
863	887		// TODO: Shouldn't be undefined.
864	888		moduleGraph: undefined,
865	889		moduleScopes,
	890	+	instances: undefined,
	891	+	instancesLen: 0,
866	892		};
867	893		}
868	894
869	895		/// Return `true` if there are no errors in the diagnostics.
870	896		pub fn success(diag: *Diagnostics) -> bool {

2436	2462		// Handled in previous pass.
2437	2463		}
2438	2464		case ast::NodeValue::Use(_) => {
2439	2465		// Handled in previous pass.
2440	2466		}
	2467	+	case ast::NodeValue::InstanceDecl { traitName, targetType, methods } => {
	2468	+	try resolveInstanceDecl(self, node, traitName, targetType, &methods);
	2469	+	}
2441	2470		else => {
2442	2471		// Ignore non-declaration nodes.
2443	2472		}
2444	2473		}
2445	2474		}

41	41		/// Nb. This should not be raised above `255`,
42	42		/// as tags are stored using 8-bits only.
43	43		pub const MAX_UNION_VARIANTS: u32 = 128;
44	44		/// Maximum nesting of loops.
45	45		pub const MAX_LOOP_DEPTH: u32 = 16;
	46	+	/// Maximum trait instances.
	47	+	pub const MAX_INSTANCES: u32 = 128;
46	48
47	49		/// Trait definition stored in the resolver.
48	50		pub record TraitType {
49	51		/// Trait name.
50	52		name: *[u8],

2470	2499		// Skip: already analyzed in declaration phase.
2471	2500		}
2472	2501		case ast::NodeValue::Use(_) => {
2473	2502		// Skip: already analyzed in declaration phase.
2474	2503		}
	2504	+	case ast::NodeValue::TraitDecl { .. } => {
	2505	+	// Skip: already analyzed in declaration phase.
	2506	+	}
	2507	+	case ast::NodeValue::InstanceDecl { methods, .. } => {
	2508	+	try resolveInstanceMethodBodies(self, &methods);
	2509	+	}
2475	2510		else => {
2476	2511		// FIXME: This allows module-level statements that should
2477	2512		// normally only be valid inside function bodies. We currently
2478	2513		// need this because of how tests are written, but it should
2479	2514		// be eventually removed.

3323	3358
3324	3359		try setNodeType(self, methodNode, Type::Void);
3325	3360		}
3326	3361		}
3327	3362
	3363	+	/// Resolve a name path node to a symbol.
	3364	+	/// Used for trait and type references in instance declarations and trait objects.
	3365	+	fn resolveNamePath(self: mut Resolver, node: ast::Node) -> *mut Symbol
	3366	+	throws (ResolveError)
	3367	+	{
	3368	+	match node.value {
	3369	+	case ast::NodeValue::Ident(name) => {
	3370	+	let sym = findAnySymbol(self.scope, name)
	3371	+	else throw emitError(self, node, ErrorKind::UnresolvedSymbol(name));
	3372	+	return sym;
	3373	+	}
	3374	+	case ast::NodeValue::ScopeAccess(access) => {
	3375	+	return try resolveAccess(self, node, access, self.scope);
	3376	+	}
	3377	+	else => {
	3378	+	throw emitError(self, node, ErrorKind::ExpectedIdentifier);
	3379	+	}
	3380	+	}
	3381	+	}
	3382	+
	3383	+	/// Resolve an instance declaration.
	3384	+	/// Validates that the trait exists, the target type exists, and all methods
	3385	+	/// match the trait's signatures.
	3386	+	fn resolveInstanceDecl(
	3387	+	self: *mut Resolver,
	3388	+	node: *ast::Node,
	3389	+	traitName: *ast::Node,
	3390	+	targetType: *ast::Node,
	3391	+	methods: *ast::NodeList
	3392	+	) throws (ResolveError) {
	3393	+	// Look up the trait.
	3394	+	let traitSym = try resolveNamePath(self, traitName);
	3395	+	let case SymbolData::Trait(traitInfo) = traitSym.data
	3396	+	else throw emitError(self, traitName, ErrorKind::Internal);
	3397	+
	3398	+	try setNodeSymbol(self, traitName, traitSym);
	3399	+
	3400	+	// Look up the target type.
	3401	+	let typeSym = try resolveNamePath(self, targetType);
	3402	+	let case SymbolData::Type(nominalTy) = typeSym.data
	3403	+	else throw emitError(self, targetType, ErrorKind::Internal);
	3404	+	try setNodeSymbol(self, targetType, typeSym);
	3405	+	// Ensure the concrete type body is resolved.
	3406	+	try ensureNominalResolved(self, nominalTy, targetType);
	3407	+
	3408	+	// Reject duplicate instance for the same (trait, type) pair.
	3409	+	let concreteType = Type::Nominal(nominalTy);
	3410	+	if let _ = findInstance(self, traitInfo, concreteType) {
	3411	+	throw emitError(self, node, ErrorKind::DuplicateInstance);
	3412	+	}
	3413	+
	3414	+	// Build the instance entry.
	3415	+	if self.instancesLen >= MAX_INSTANCES {
	3416	+	throw emitError(self, node, ErrorKind::Internal);
	3417	+	}
	3418	+	let mut entry = InstanceEntry {
	3419	+	traitType: traitInfo,
	3420	+	concreteType,
	3421	+	concreteTypeName: typeSym.name,
	3422	+	moduleId: self.currentMod,
	3423	+	methods: undefined,
	3424	+	methodsLen: 0,
	3425	+	};
	3426	+	// Track which trait methods are covered by the instance.
	3427	+	let mut covered: [bool; ast::MAX_TRAIT_METHODS] = [false; ast::MAX_TRAIT_METHODS];
	3428	+
	3429	+	// Match each instance method to a trait method.
	3430	+	for i in 0..methods.len {
	3431	+	let methodNode = methods.list[i];
	3432	+	let case ast::NodeValue::InstanceMethodDecl {
	3433	+	name, receiverName, receiverType, sig, body
	3434	+	} = methodNode.value else continue;
	3435	+
	3436	+	let methodName = try nodeName(self, name);
	3437	+
	3438	+	// Find the matching trait method.
	3439	+	let mut traitMethod: ?*TraitMethod = nil;
	3440	+	for j in 0..traitInfo.methodsLen {
	3441	+	if traitInfo.methods[j].name == methodName {
	3442	+	traitMethod = &traitInfo.methods[j];
	3443	+	break;
	3444	+	}
	3445	+	}
	3446	+	let tm = traitMethod
	3447	+	else throw emitError(self, name, ErrorKind::UnresolvedSymbol(methodName));
	3448	+
	3449	+	// Determine receiver mutability and validate receiver type.
	3450	+	let mut receiverMut = false;
	3451	+	if let case ast::NodeValue::TypeSig(typeSig) = receiverType.value {
	3452	+	if let case ast::TypeSig::Pointer { mutable, valueType } = typeSig {
	3453	+	receiverMut = mutable;
	3454	+	// Validate that the receiver type annotation matches the
	3455	+	// concrete type from the instance declaration.
	3456	+	let annotatedTy = try infer(self, valueType);
	3457	+	if not typesEqual(annotatedTy, concreteType) {
	3458	+	throw emitTypeMismatch(self, receiverType, TypeMismatch {
	3459	+	expected: concreteType,
	3460	+	actual: annotatedTy,
	3461	+	});
	3462	+	}
	3463	+	}
	3464	+	}
	3465	+
	3466	+	// Check receiver mutability matches in both directions.
	3467	+	if tm.mutable and not receiverMut {
	3468	+	throw emitError(self, receiverType, ErrorKind::ImmutableBinding);
	3469	+	}
	3470	+	if receiverMut and not tm.mutable {
	3471	+	throw emitError(self, receiverType, ErrorKind::ReceiverMutabilityMismatch);
	3472	+	}
	3473	+
	3474	+	// Build the function type for the instance method.
	3475	+	// The receiver becomes the first parameter.
	3476	+	let mut fnType = FnType {
	3477	+	paramTypes: undefined,
	3478	+	paramTypesLen: 0,
	3479	+	returnType: allocType(self, Type::Void),
	3480	+	throwList: undefined,
	3481	+	throwListLen: 0,
	3482	+	localCount: 0,
	3483	+	};
	3484	+	// First param is the receiver.
	3485	+	let receiverPtrType = Type::Pointer {
	3486	+	target: allocType(self, concreteType),
	3487	+	mutable: receiverMut,
	3488	+	};
	3489	+	fnType.paramTypes[0] = allocType(self, receiverPtrType);
	3490	+	fnType.paramTypesLen = 1;
	3491	+
	3492	+	// Add the other params from the trait method and validate that
	3493	+	// the instance method's declared parameter types match.
	3494	+	if sig.params.len != tm.fnType.paramTypesLen {
	3495	+	throw emitError(self, methodNode, ErrorKind::FnArgCountMismatch(CountMismatch {
	3496	+	expected: tm.fnType.paramTypesLen,
	3497	+	actual: sig.params.len,
	3498	+	}));
	3499	+	}
	3500	+	for j in 0..tm.fnType.paramTypesLen {
	3501	+	// Resolve the instance method's declared parameter type.
	3502	+	let paramNode = sig.params.list[j];
	3503	+	let case ast::NodeValue::FnParam(param) = paramNode.value
	3504	+	else throw emitError(self, paramNode, ErrorKind::ExpectedIdentifier);
	3505	+	let instanceParamTy = try resolveValueType(self, param.type);
	3506	+	let traitParamTy = *tm.fnType.paramTypes[j];
	3507	+
	3508	+	if not typesEqual(instanceParamTy, traitParamTy) {
	3509	+	throw emitTypeMismatch(self, paramNode, TypeMismatch {
	3510	+	expected: traitParamTy,
	3511	+	actual: instanceParamTy,
	3512	+	});
	3513	+	}
	3514	+	fnType.paramTypes[fnType.paramTypesLen] = tm.fnType.paramTypes[j];
	3515	+	fnType.paramTypesLen += 1;
	3516	+	}
	3517	+	fnType.returnType = tm.fnType.returnType;
	3518	+
	3519	+	// Copy throws list from the trait method.
	3520	+	for j in 0..tm.fnType.throwListLen {
	3521	+	fnType.throwList[fnType.throwListLen] = tm.fnType.throwList[j];
	3522	+	fnType.throwListLen += 1;
	3523	+	}
	3524	+
	3525	+	// Create a symbol for the instance method without binding it into the
	3526	+	// module scope. Instance methods are dispatched via v-table, so they
	3527	+	// must not pollute the enclosing scope.
	3528	+	let fnTy = Type::Fn(allocFnType(self, fnType));
	3529	+	let mName = try nodeName(self, name);
	3530	+	let sym = allocSymbol(self, SymbolData::Value {
	3531	+	mutable: false, alignment: 0, type: fnTy, addressTaken: false,
	3532	+	}, mName, methodNode, 0);
	3533	+
	3534	+	try setNodeSymbol(self, methodNode, sym);
	3535	+	try setNodeType(self, methodNode, fnTy);
	3536	+	try setNodeType(self, name, fnTy);
	3537	+
	3538	+	// Store in instance entry at the matching v-table slot.
	3539	+	entry.methods[tm.index] = sym;
	3540	+	entry.methodsLen += 1;
	3541	+
	3542	+	covered[tm.index] = true;
	3543	+	}
	3544	+
	3545	+	// Check that all trait methods are implemented.
	3546	+	for i in 0..traitInfo.methodsLen {
	3547	+	if not covered[i] {
	3548	+	throw emitError(self, node, ErrorKind::MissingTraitMethod(traitInfo.methods[i].name));
	3549	+	}
	3550	+	}
	3551	+	self.instances[self.instancesLen] = entry;
	3552	+	self.instancesLen += 1;
	3553	+
	3554	+	try setNodeType(self, node, Type::Void);
	3555	+	}
	3556	+
	3557	+	/// Resolve instance method bodies.
	3558	+	fn resolveInstanceMethodBodies(self: mut Resolver, methods: ast::NodeList)
	3559	+	throws (ResolveError)
	3560	+	{
	3561	+	for i in 0..methods.len {
	3562	+	let methodNode = methods.list[i];
	3563	+	let case ast::NodeValue::InstanceMethodDecl {
	3564	+	name, receiverName, receiverType, sig, body
	3565	+	} = methodNode.value else continue;
	3566	+
	3567	+	// Symbol may be absent if [`resolveInstanceDecl`] reported an error
	3568	+	// for this method (eg. unknown method name). Skip gracefully.
	3569	+	let sym = symbolFor(self, methodNode)
	3570	+	else continue;
	3571	+	let case SymbolData::Value { type, .. } = sym.data
	3572	+	else panic "resolveInstanceMethodBodies: expected value symbol";
	3573	+	let case Type::Fn(fnType) = type
	3574	+	else panic "resolveInstanceMethodBodies: expected function type";
	3575	+
	3576	+	// Enter function scope.
	3577	+	enterFn(self, methodNode, fnType);
	3578	+
	3579	+	// Bind the receiver parameter.
	3580	+	let receiverTy = *fnType.paramTypes[0];
	3581	+	try bindValueIdent(self, receiverName, receiverName, receiverTy, false, 0, 0) catch {
	3582	+	exitFn(self);
	3583	+	throw ResolveError::Failure;
	3584	+	};
	3585	+	// Bind the remaining parameters from the signature.
	3586	+	for j in 0..sig.params.len {
	3587	+	let paramNode = sig.params.list[j];
	3588	+	let paramTy = try infer(self, paramNode) catch {
	3589	+	exitFn(self);
	3590	+	throw ResolveError::Failure;
	3591	+	};
	3592	+	}
	3593	+
	3594	+	// Resolve the body.
	3595	+	let retTy = *fnType.returnType;
	3596	+	let bodyTy = try checkAssignable(self, body, Type::Void) catch {
	3597	+	exitFn(self);
	3598	+	throw ResolveError::Failure;
	3599	+	};
	3600	+	if retTy != Type::Void and bodyTy != Type::Never {
	3601	+	exitFn(self);
	3602	+	throw emitError(self, body, ErrorKind::FnMissingReturn);
	3603	+	}
	3604	+	exitFn(self);
	3605	+	}
	3606	+	}
	3607	+
	3608	+	/// Look up an instance entry by trait and concrete type.
	3609	+	fn findInstance(self: Resolver, traitInfo: TraitType, concreteType: Type) -> ?*InstanceEntry {
	3610	+	for i in 0..self.instancesLen {
	3611	+	let entry = &self.instances[i];
	3612	+	if entry.traitType == traitInfo and typesEqual(entry.concreteType, concreteType) {
	3613	+	return entry;
	3614	+	}
	3615	+	}
	3616	+	return nil;
	3617	+	}
	3618	+
3328	3619		/// Resolve union variant types after all type names are bound (Phase 2 of type resolution).
3329	3620		fn resolveUnionBody(self: mut Resolver, node: ast::Node, decl: ast::UnionDecl)
3330	3621		throws (ResolveError)
3331	3622		{
3332	3623		// Get the type symbol that was bound to this declaration node.

5591	5882		fnType.returnType = allocType(self, Type::Void);
5592	5883		}
5593	5884		return Type::Fn(allocFnType(self, fnType));
5594	5885		}
5595	5886		case ast::TypeSig::TraitObject { traitName, mutable } => {
5596		-	let name = try nodeName(self, traitName);
5597		-	let sym = findAnySymbol(self.scope, name)
5598		-	else throw emitError(self, traitName, ErrorKind::UnresolvedSymbol(name));
	5887	+	let sym = try resolveNamePath(self, traitName);
5599	5888		let case SymbolData::Trait(traitInfo) = sym.data
5600	5889		else throw emitError(self, traitName, ErrorKind::Internal);
5601	5890		try setNodeSymbol(self, traitName, sym);
5602	5891
5603	5892		return Type::TraitObject { traitInfo, mutable };

556	556		io::print("instance receiver mutability does not match trait declaration");
557	557		}
558	558		case super::ErrorKind::DuplicateInstance => {
559	559		io::print("duplicate instance declaration for the same trait and type");
560	560		}
	561	+	case super::ErrorKind::MissingTraitMethod(name) => {
	562	+	io::print("missing trait method '");
	563	+	io::print(name);
	564	+	io::print("'");
	565	+	}
561	566		case super::ErrorKind::UnexpectedTraitName => {
562	567		io::print("trait name cannot be used as a value");
563	568		}
564	569		case super::ErrorKind::TraitReceiverMismatch => {
565	570		io::print("trait method receiver must be a pointer to the declaring trait");

247	247		if let case super::ErrorKind::UnionMatchNonExhaustive(actualName) = *actual {
248	248		return mem::eq(actualName, expectedName);
249	249		}
250	250		return false;
251	251		}
	252	+	if let case super::ErrorKind::MissingTraitMethod(expectedName) = expected {
	253	+	if let case super::ErrorKind::MissingTraitMethod(actualName) = *actual {
	254	+	return mem::eq(actualName, expectedName);
	255	+	}
	256	+	return false;
	257	+	}
252	258		return *actual == expected;
253	259		}
254	260
255	261		/// Extract the first error and ensure it has the expected kind.
256	262		fn expectErrorKind(result: TestResult, kind: super::ErrorKind) -> super::Error

4495	4501		let mut a = testResolver();
4496	4502		let program = "union ErrA { A } union ErrB { B } fn f() -> i32 throws (ErrA, ErrB) { throw ErrA::A(); return 0; } fn g() -> i32 { return try f() catch e { return 0; }; }";
4497	4503		let result = try resolveProgramStr(&mut a, program);
4498	4504		try expectErrorKind(&result, super::ErrorKind::TryCatchMultiError);
4499	4505		}
	4506	+
	4507	+	@test fn testInstanceMissingMethod() throws (testing::TestError) {
	4508	+	let mut a = testResolver();
	4509	+	let program = "trait S { fn (*S) f() -> i32; } record R { x: i32 } instance S for R {}";
	4510	+	let result = try resolveProgramStr(&mut a, program);
	4511	+	try expectErrorKind(&result, super::ErrorKind::MissingTraitMethod("f"));
	4512	+	}
	4513	+
	4514	+	@test fn testInstanceUnknownMethod() throws (testing::TestError) {
	4515	+	let mut a = testResolver();
	4516	+	let program = "trait S { fn (S) f() -> i32; } record R { x: i32 } instance S for R { fn (self: R) x() -> i32 { return 0; } }";
	4517	+	let result = try resolveProgramStr(&mut a, program);
	4518	+	try expectErrorKind(&result, super::ErrorKind::UnresolvedSymbol("x"));
	4519	+	}