import { HashSet, Set } from 'zena:collections'; import { FlowNode } from '../analysis/flow.zena'; import { AsPattern, BindingPattern, BlockStatement, BooleanLiteral, ClassPattern, EnumDeclaration, Expression, ExpressionStatement, Identifier, IdentifierPattern, LogicalPattern, MatchExpression, MemberExpression, Node, NullLiteral, NumberLiteral, RecordPattern, StringLiteral } from '../ast.zena'; import { BoolLiteralType, BooleanType, ClassType, EnumType, InterfaceType, NeverType, NullType, NumLiteralType, RecordType as RecordT, StringLiteralType, Type, UnionType as UnionT, VoidType, baseType, isBooleanLike, typeToString, unwrapAliases } from '../types.zena'; import { DiagnosticCode } from '../diagnostics.zena'; import { adaptArmToContext, adaptJoinedArm, armValueNode } from './adaptation.zena'; import { CheckerContext } from './context.zena'; import { checkExpression } from './expressions.zena'; import { literalFits, recordUnionMembersOf } from './members.zena'; import { sameInterfaceDeclaration, sameTypeArguments } from './generics.zena'; import { prescanPendingFunctions } from './module.zena'; import { applyTrueNarrowingFromCondition, branchDefinitelyExits, getMemberPathKey, isImmutableMemberPath } from './narrowing.zena'; import { moveDestructured, registerPatternOwners } from './ownership.zena'; import { checkPattern, collectPatternInstantiations } from './patterns.zena'; import { isAssignableTo } from './relations.zena'; import { checkStatement } from './statements.zena'; import { combineArmTypes, narrowUnion, subtractNullFromType, subtractTypeFromUnion } from './unions.zena'; /** * Collect all concrete (non-sealed) leaf variants of a sealed class type, * recursing into sub-sealed variants (sum of sums). */ function collectLeafVariants(ct: ClassType): GrowableArray { let result = new Array(); if (ct.sealedVariants == null) { return result; } let variants = ct.sealedVariants as GrowableArray; for (let v in variants) { if (v.isSealed && v.sealedVariants != null) { // Recurse: this variant is itself sealed let leaves = collectLeafVariants(v); for (let leaf in leaves) { result.push(leaf); } } else { result.push(v); } } return result; } /** * Returns true if a type has a finite, enumerable set of values that can be * fully covered by match patterns (sealed classes, booleans, literal types). */ function isFiniteType(t: Type): boolean { return match (t) { case BooleanType: true case BoolLiteralType: true case StringLiteralType: true case NullType: true case ClassType as ct: ct.isSealed case EnumType: true case UnionT {types}: { // A union of records told apart by a literal field: its arms name // the members, so a missing one is an error (`recordMemberCovered`). if (isDiscriminatedRecordUnion(t)) { return true; } var allFinite = true; for (let member in types) { if (!isFiniteType(member)) { allFinite = false; } } allFinite } case _: false }; } /** * Whether `t` is a union of record types with a field every member has at * a literal type, as a discriminated union is. */ function isDiscriminatedRecordUnion(t: Type): boolean { if (!(t is UnionT)) { return false; } let members = recordUnionMembersOf(t); if (members == null) { return false; } for (let field in members[0].properties.keys()) { var literalInAll = true; for (let rec in members) { if (!rec.properties.has(field) || rec.isOptional(field) || !isLiteralFieldType(rec.properties[field])) { literalInAll = false; } } if (literalInAll) { return true; } } return false; } /** Whether a field of `rec` has a literal type, as a discriminant does. */ function hasLiteralField(rec: RecordT): boolean { for (let pair in rec.properties) { if (!rec.isOptional(pair.key) && isLiteralFieldType(pair.value)) { return true; } } return false; } function isLiteralFieldType(t: Type): boolean { return t is BoolLiteralType || t is NumLiteralType || t is StringLiteralType; } /** * Whether a record pattern matches every value of the record type `rec`: * each field it names is required there, and its pattern for the field * covers the field's type, a literal equal to the field's literal type * or a pattern that leaves nothing of the type. */ function recordMemberCovered(ctx: CheckerContext, rec: RecordT, pattern: RecordPattern): boolean { for (let prop in pattern.properties) { let name = prop.name.name; if (!rec.properties.has(name) || rec.isOptional(name)) { return false; } let fieldType = rec.properties[name]; if (literalFits(fieldType, prop.value) == 1) { continue; } if (!(subtractPatternFromType(ctx, fieldType, prop.value) is NeverType)) { return false; } } return true; } /** * One enum a match's scrutinee can hold, and the members its arms have named * so far. A scrutinee can reach more than one — `Color | Fruit` reaches two — * and a match covers the scrutinee only once it has named every member of * each of them. */ final class EnumCoverage { declaration: EnumDeclaration; covered: HashSet = new Set(); var complete: boolean = false; new(this.declaration); } /** * The enums a value of type `t` can hold. An enum's type is a distinct alias * over its backing primitive, so the declaration hanging off that alias is the * only place its member list survives. */ function enumsIn(t: Type) { let found = new Array(); match (t) { case EnumType as et: { found.push(new EnumCoverage(et.declaration)); } case UnionT {types}: { for (let member in types) { if (member is EnumType) { found.push(new EnumCoverage(member.declaration)); } } } case _: {} } return found; } /** * Drop everything `ed` can be from `t`, leaving what a scrutinee of that type * could still hold. Every member of an enum has the enum's own type, so this * is all-or-nothing: the caller runs it once the arms have named them all. */ function subtractEnumFromType(t: Type, ed: EnumDeclaration) { return narrowUnion(t, (member) => subtractEnumFromMember(member, ed)); } /** `subtractEnumFromType` for one member of the scrutinee's type. */ function subtractEnumFromMember(member: Type, ed: EnumDeclaration): Type { if (member is EnumType && member.declaration.id == ed.id) { return new NeverType(); } return member; } /** * Add the members of `ed` that `pattern` covers to `covered`. * * `case Color.Red` names one member. There is no per-member type to subtract * from the scrutinee — every member of `Color` has type `Color` — so coverage * is tracked by name instead, and the match is exhaustive once the set has * grown to the declared member count. Patterns that cover everything * (`case _`, a binding) name no member and are handled by * `subtractPatternFromType`, which takes the remaining type straight to Never. */ function collectCoveredEnumMembers( ctx: CheckerContext, pattern: Node, ed: EnumDeclaration, covered: HashSet ): void { match (pattern) { case MemberExpression as me: { if (me.isSymbolAccess) { return; } // Which enum the member belongs to is the namespace it was read // off: `Color`, the enum type itself. An enum imported under // another name still points here. let objectType = ctx.model.getNodeType(me.object); if (objectType == null) { return; } if (objectType is EnumType) { if (objectType.declaration.id == ed.id) { covered.add(me.property.name); } } } case LogicalPattern {operator, left, right}: { // A `|` pattern (spelled "||" here) covers what either side covers. // An `&` pattern covers only their overlap, which names no member. if (operator == "||") { collectCoveredEnumMembers(ctx, left, ed, covered); collectCoveredEnumMembers(ctx, right, ed, covered); } } case AsPattern as ap: { collectCoveredEnumMembers(ctx, ap.pattern, ed, covered); } case BindingPattern as bp: { collectCoveredEnumMembers(ctx, bp.pattern, ed, covered); } case _: {} } } /** * Subtract a pattern from a type, returning the remaining uncovered type. * Returns NeverType when the pattern fully covers the type. */ function subtractPatternFromType(ctx: CheckerContext, t: Type, pattern: Node): Type { // Wildcard or variable pattern covers everything. match (pattern) { case IdentifierPattern {name}: { if (name == "_") { return new NeverType(); } // Check if this identifier names a sealed variant (unit variant pattern). let resolved = ctx.resolveTypeName(name); if (resolved != null) { match (resolved) { case ClassType as patClass: { return subtractClassFromType(ctx, t, patClass); } case InterfaceType as patIface: { return subtractInterfaceFromType(ctx, t, patIface); } case _: {} } } // Regular variable binding — covers everything. return new NeverType(); } case Identifier {name}: { // Plain identifier in match pattern (e.g., case _, case Red). if (name == "_") { return new NeverType(); } // Check if this identifier names a sealed variant (unit variant pattern). let resolved = patternTestedType(ctx, pattern, name); if (resolved != null) { match (resolved) { case ClassType as patClass: { return subtractClassFromType(ctx, t, patClass); } case InterfaceType as patIface: { return subtractInterfaceFromType(ctx, t, patIface); } case _: {} } } // Regular variable binding — covers everything. return new NeverType(); } case ClassPattern as cp: { let resolved = patternTestedType(ctx, cp, cp.name.name); if (resolved != null) { match (resolved) { case ClassType as patClass: { return subtractClassFromType(ctx, t, patClass); } case InterfaceType as patIface: { return subtractInterfaceFromType(ctx, t, patIface); } case _: {} } } return t; } case AsPattern as ap: { return subtractPatternFromType(ctx, t, ap.pattern); } case BindingPattern as bp: { // `case let Leaf {size}: …` — the binding prefix doesn't change // what the inner pattern covers. return subtractPatternFromType(ctx, t, bp.pattern); } case RecordPattern as rp: { // The members of a discriminated record union the pattern matches // whole. A record with no literal field is left as it was: its arms // are not checked for coverage. return narrowUnion(t, (member) => { let rec = baseType(unwrapAliases(member)); return if (rec is RecordT && hasLiteralField(rec) && recordMemberCovered(ctx, rec, rp)) { new NeverType() as Type } else { member }; }); } case BooleanLiteral {value}: { // Subtract the specific boolean literal from the remaining type. let lit: Type = new BoolLiteralType(value); match (t) { case BooleanType: { // BooleanType = true | false. Subtracting one literal leaves the other. if (value) { return new BoolLiteralType(false); } else { return new BoolLiteralType(true); } } case _: { return subtractTypeFromUnion(t, lit); } } } case StringLiteral {value}: { // Subtract the specific string literal from the remaining type. let lit: Type = new StringLiteralType(value); return subtractTypeFromUnion(t, lit); } case NumberLiteral {}: { // Number literal patterns: no subtraction (no numeric literal types yet). return t; } case NullLiteral {}: { return subtractNullFromType(t); } case _: { // Literal patterns, etc. — don't subtract from sealed types for now. return t; } } } /** * Subtract a class type (from a pattern) from the scrutinee type. * Handles sealed class variant tracking and transitive hierarchies. */ function subtractClassFromType(ctx: CheckerContext, t: Type, patClass: ClassType): Type { return narrowUnion(t, (member) => subtractClassFromMember(ctx, member, patClass)); } /** `subtractClassFromType` for one member of the scrutinee's type. */ function subtractClassFromMember(ctx: CheckerContext, t: Type, patClass: ClassType): Type { let scrutClass = unwrapAliases(t); if (scrutClass is ClassType) { // If the pattern class IS the scrutinee class (or a supertype), covers it. if ((scrutClass.genericSource ?? scrutClass).id == (patClass.genericSource ?? patClass).id) { return if (patternCoversInstance(patClass, scrutClass)) new NeverType() else t; } // If the scrutinee is a sealed class, subtract the variant from its set. if (scrutClass.isSealed && scrutClass.sealedVariants != null) { let variants = scrutClass.sealedVariants as GrowableArray; let remaining = new Array(); for (let v in variants) { if (v.id == patClass.id) { if (!patternCoversInstance(patClass, variantInstantiation(v, scrutClass))) { remaining.push(v); } } else if (v.isSealed && v.sealedVariants != null) { // Variant is itself sealed — recurse into its sub-variants. let subResult = subtractClassFromType(ctx, variantInstantiation(v, scrutClass), patClass); match (subResult) { case NeverType: { // Fully covered — don't add to remaining. } case ClassType as remainingVariant: { remaining.push(remainingVariant); } case _: { remaining.push(v); } } } else { // Check if patClass is a subtype of this variant. var isSubtype = false; var current = patClass.superType; while (current != null) { let cur = current; if (cur.id == v.id) { isSubtype = true; break; } current = cur.superType; } if (!isSubtype) { remaining.push(v); } } } if (remaining.length == 0) { return new NeverType(); } // Return a synthetic sealed type with remaining variants. It keeps // the scrutinee's type arguments, which later arms infer theirs // from. let remainingType = new ClassType(scrutClass.id, scrutClass.symbolId, scrutClass.name); remainingType.isSealed = true; remainingType.isAbstract = true; remainingType.superType = scrutClass.superType; remainingType.sealedVariants = remaining; remainingType.typeParameters = scrutClass.typeParameters; remainingType.typeArguments = scrutClass.typeArguments; remainingType.genericSource = scrutClass.genericSource; remainingType.members = scrutClass.members; remainingType.staticMembers = scrutClass.staticMembers; return remainingType; } } return t; } /** * The class a pattern node tests for: the instantiation the checker * recorded on it (`Box`, or `Left` inferred from the * scrutinee), else whatever `name` resolves to. */ function patternTestedType(ctx: CheckerContext, pattern: Node, name: String): Type | null { let recorded = ctx.model.getNodeType(pattern); if (recorded is ClassType || recorded is InterfaceType) { return recorded; } return ctx.resolveTypeName(name); } /** * Whether a class pattern typed `pattern` matches every value typed * `member`, an instance type of the same class. An instantiation covers * only itself: `Box` leaves the `Box` of a `Box | * Box` to match. A pattern at the class's own type parameters * stands for an error already reported, and covers everything so the * error does not cascade. */ function patternCoversInstance(pattern: ClassType, member: ClassType): boolean { if (pattern.typeArguments == null) { return true; } return member.typeArguments != null && sameTypeArguments(pattern, member); } /** * The sealed variant `v` of `scrut` at the type arguments `scrut` gives * it: `Left` of an `Either` is `Left`. `v` * itself when it is not generic or `scrut` leaves one of its arguments * open. */ function variantInstantiation(v: ClassType, scrut: ClassType): ClassType { if (v.typeParameters == null || v.typeArguments != null) { return v; } let candidates = new Array(); collectPatternInstantiations(v, scrut, candidates); return if (candidates.length == 1) candidates[0] else v; } function subtractInterfaceFromType(ctx: CheckerContext, t: Type, patIface: InterfaceType): Type { return narrowUnion(t, (member) => subtractInterfaceFromMember(member, patIface)); } /** `subtractInterfaceFromType` for one member of the scrutinee's type. */ function subtractInterfaceFromMember(member: Type, patIface: InterfaceType): Type { let scrut = unwrapAliases(member); if (scrut is InterfaceType) { if (sameInterfaceDeclaration(scrut, patIface)) { return new NeverType(); } } return member; } function getNarrowedTypeFromPattern(ctx: CheckerContext, pattern: Node): Type | null { match (pattern) { case ClassPattern as cp: { return ctx.model.getNodeType(cp); } case AsPattern as ap: { return getNarrowedTypeFromPattern(ctx, ap.pattern); } case IdentifierPattern as id: { if (id.name == "_") { return null; } let nodeType = ctx.model.getNodeType(id); if (nodeType != null) { return nodeType; } return ctx.resolveTypeName(id.name); } case Identifier as id: { if (id.name == "_") { return null; } let nodeType = ctx.model.getNodeType(id); if (nodeType != null) { return nodeType; } return ctx.resolveTypeName(id.name); } case _: { return null; } } } /** * Check a match expression: discriminant against patterns, return union of case body types. * Also checks exhaustiveness for sealed class discriminants. */ export function checkMatchExpr( ctx: CheckerContext, matchExpr: MatchExpression, expectedType: Type | null ): Type { let {discriminant, cases, loc} = matchExpr; // Check the discriminant expression. let scrutineeType = checkExpression(ctx, discriminant, null); moveDestructured(ctx, discriminant, scrutineeType); // Each arm branches from the flow after the discriminant; the arms // join again after the match. Arm-end flow nodes are kept, aligned // with the cases by index, for the branch-join drop decision. let preArmFlow = ctx.currentFlow; let armJoin = ctx.newFlowJoin(); let armEnds = new Array(); // Track remaining type for exhaustiveness checking. var remainingType = scrutineeType; // An enum the scrutinee can hold is tracked by member name alongside the // remaining type, because its members all share the enum's own type and so // cannot be subtracted from it one at a time. let enumCoverages = enumsIn(scrutineeType); // Collect result types from each case. let resultTypes = new Array(); // Track matched pattern types for ambiguity detection. let matchedTypes = new Array(); for (let matchCase in cases) { // Check for unreachable case: if remaining type is Never, nothing can reach this case. if (remainingType is NeverType) { ctx.error( "Unreachable case.", DiagnosticCode.TypeMismatch, matchCase.loc ); } // Enter a new scope for pattern bindings. ctx.setFlow(preArmFlow); ctx.enterScope(); // Check the pattern and bind variables. Pass remainingType (not scrutineeType) so // catch-all identifier bindings get the type narrowed by the earlier arms. checkPattern(ctx, matchCase.pattern, remainingType); let discPath = getMemberPathKey(ctx, discriminant); let isImmutableDisc = discriminant is Identifier || (discriminant is MemberExpression && isImmutableMemberPath(ctx, discriminant)); if (discPath != null && isImmutableDisc) { let narrowedType = getNarrowedTypeFromPattern(ctx, matchCase.pattern); if (narrowedType != null) { ctx.pushFlowPathNarrowing(discPath, narrowedType); } } // Get pattern type for ambiguity detection. var patternType: Type | null = null; match (matchCase.pattern) { case ClassPattern as cp: { let clsName = cp.name.name; let classType = ctx.resolveTypeName(clsName); if (classType != null) { patternType = classType; } } case Identifier as ident: { let classType = ctx.resolveTypeName(ident.name); if (classType != null) { if (classType is ClassType) { patternType = classType; } else {} } } case _: {} } // Check for ambiguous extension types. if (patternType != null) { var pi = 0; while (pi < matchedTypes.length) { let prev = matchedTypes[pi]; var ext1: ClassType | null = null; var ext2: ClassType | null = null; if (patternType is ClassType) { if (patternType.isExtension && patternType.onType != null) { ext1 = patternType; } } if (prev is ClassType) { if (prev.isExtension && prev.onType != null) { ext2 = prev; } } if (ext1 != null) { if (ext2 != null) { let onType1 = ext1.onType; let onType2 = ext2.onType; if (onType1 != null && onType2 != null) { if (isAssignableTo(ctx, onType1, onType2) && isAssignableTo(ctx, onType2, onType1)) { ctx.error( "Ambiguous match case: '" + typeToString(patternType) + "' and '" + typeToString(prev) + "' extend the same underlying type and are indistinguishable at runtime.", DiagnosticCode.TypeMismatch, matchCase.loc ); } } } } pi = pi + 1; } matchedTypes.push(patternType); } // Update remaining type (only if no guard — guards prevent exhaustiveness). if (matchCase.guard == null) { remainingType = subtractPatternFromType(ctx, remainingType, matchCase.pattern); for (let coverage in enumCoverages) { if (coverage.complete) { continue; } let ed = coverage.declaration; collectCoveredEnumMembers(ctx, matchCase.pattern, ed, coverage.covered); if (coverage.covered.size == ed.members.length) { coverage.complete = true; remainingType = subtractEnumFromType(remainingType, ed); } } } // Check the guard if present. let {guard} = matchCase; if (guard != null) { let guardType = checkExpression(ctx, guard, null); if (!isBooleanLike(guardType)) { ctx.error( "Match guard must be a boolean expression.", DiagnosticCode.TypeMismatch, matchCase.loc ); } // The body runs only when the guard held, so it is checked under // the guard's narrowings, as an `if` consequent is (issue #128). applyTrueNarrowingFromCondition(ctx, guard); } // Check the body and collect its type. The owners the pattern bound // are released at the body's end unless it moves them (#495); the // guard has run by then, so a failed guard releases nothing. ctx.enterOwnScope(); registerPatternOwners(ctx, matchCase.pattern); let bodyType = checkMatchCaseBody(ctx, matchCase.body, expectedType); ctx.exitOwnScope(matchCase.body); resultTypes.push(bodyType); ctx.exitScope(); armEnds.push(ctx.currentFlow); armJoin.add(ctx.currentFlow); } ctx.recordPendingEdgeMatch(matchExpr as Node, preArmFlow, armEnds); if (armJoin.antecedents.length == 0) { ctx.markFlowUnreachable(); } else { ctx.setFlow(armJoin); } // Check exhaustiveness: if the scrutinee is a finite type (sealed class, // boolean, literal union, etc.) and remainingType is not Never, report error. if (isFiniteType(scrutineeType) && !(remainingType is NeverType)) { ctx.error( "Non-exhaustive match. Not all cases are covered.", DiagnosticCode.TypeMismatch, loc ); } // Result is union of all case body types. if (expectedType is VoidType) { return new VoidType(); } if (resultTypes.length == 0) { return new NeverType(); } if (resultTypes.length == 1) { return resultTypes[0]; } let joined = combineArmTypes(resultTypes, ctx, loc); // A class arm the join folded into an interface arm is packed on // its own value node. var ci = 0; for (let matchCase in cases) { if (ci < resultTypes.length) { let valueNode = armValueNode(matchCase.body); if (valueNode != null) { adaptJoinedArm(ctx, valueNode, resultTypes[ci], joined); } } ci += 1; } return joined; } /** * Check the body of a match case (expression or block) and return its type. */ export function checkMatchCaseBody(ctx: CheckerContext, body: Node, expectedType: Type | null): Type { match (body) { case BlockStatement as block: { // Execute statements; need to track return type. The block's owners // are its own, as in checkIfBranchNode: a `match` arm's body, and a // `try`, `catch`, `cancel` or `finally` block, all come here. let stmts = block.body; prescanPendingFunctions(ctx, stmts); ctx.enterOwnScope(); var lastType: Type = new VoidType(); var si = 0; while (si < stmts.length) { let isLast = si == stmts.length - 1; let et = if (isLast) { expectedType } else { new VoidType() as Type }; ctx.beginOwnStatement(); let stmt = stmts[si]; if (isLast && stmt is ExpressionStatement && !(et is VoidType)) { // The block's value. lastType = adaptArmToContext(ctx, stmt.expression, checkExpression(ctx, stmt.expression, et), et); } else { // Every other statement is one: checkStatement releases an // owner an expression statement discards, ends the path at a // call that never returns, and gives a `return` the full // treatment (return-type inference, async adoption, and // marking the flow unreachable — an arm that returns must not // feed the match join), and definitelyExits makes the arm // `never`, exactly like one ending in `throw`. checkStatement(ctx, stmt); lastType = if (branchDefinitelyExits(stmt)) { new NeverType() as Type } else { new VoidType() as Type }; } ctx.endOwnStatement(si, stmt); si = si + 1; } ctx.exitOwnScope(block as Node); return lastType; } case _: { // Expression body. let bodyExpr = body as Expression; return adaptArmToContext(ctx, bodyExpr, checkExpression(ctx, bodyExpr, expectedType), expectedType); } } }