import { HashMap, Set } from 'zena:collections'; import { growable } from 'zena:core'; import { walk } from '../visitor.zena'; import { AssignmentExpression, BinaryExpression, BlockStatement, BooleanLiteral, BreakStatement, CallExpression, ClassDeclaration, ContinueStatement, Expression, ExpressionStatement, ForInStatement, ForStatement, FunctionExpression, Identifier, IfExpression, IfStatement, IsExpression, MatchExpression, MemberExpression, Node, NullLiteral, NumberLiteral, ReturnStatement, StringLiteral, ShieldedStatement, Statement, ThisExpression, ThrowExpression, UnaryExpression, WhileStatement, getMemberPropertyName } from '../ast.zena'; import { ClassType, FieldInfo, InterfaceType, NeverType, NullType, RecordType as RecordT, Type, UnionType as UnionT, baseType } from '../types.zena'; import { SemanticModel } from '../semantic-model.zena'; import { Symbol, SymbolId, noSymbolId } from '../scope/symbol.zena'; import { resolveTypeAnnotation } from './annotations.zena'; import { CheckerContext } from './context.zena'; import { checkExpression } from './expressions.zena'; import { literalFits, recordUnionMembersOf } from './members.zena'; import { createUnionType, subtractNullFromType, subtractTypeFromUnion, unwrapNullableForMemberLookup } from './unions.zena'; // ============================================================================ // Control-Flow Narrowing Helpers // ============================================================================ /** * Check if a statement definitely exits (return, break, continue, throw). * Used to propagate narrowing past null-guard patterns like: * if (x == null) { return; } * // x is now non-null here * * `neverCompletingLoops` counts a loop that never completes * (`loopNeverCompletes`) as exiting. The unreachable-code reports pass * false until the bootstrap's checker knows the rule (#509). */ function exprDefinitelyExits(expr: Expression, model: SemanticModel | null = null, neverCompletingLoops: boolean = true): boolean { return match (expr) { case ThrowExpression {}: true case CallExpression as call: { // A call to a never-returning function ends the path like a // `throw`; the type is only known when a model is provided. if (model == null) { false } else { let t = model.getNodeType(call); t != null && t is NeverType } } case MatchExpression {cases}: { if (cases.length == 0) { return false; } var allExit = true; for (let c in cases) { let caseExits = if (c.body is Statement) { branchDefinitelyExits(c.body as Statement, model, neverCompletingLoops) } else { exprDefinitelyExits(c.body as Expression, model, neverCompletingLoops) }; if (!caseExits) { allExit = false; } } allExit } case IfExpression {consequent, alternate}: { let consExits = if (consequent is Statement) { branchDefinitelyExits(consequent, model, neverCompletingLoops) } else { exprDefinitelyExits(consequent as Expression, model, neverCompletingLoops) }; let altExits = if (alternate == null) { false } else if (alternate is Statement) { branchDefinitelyExits(alternate, model, neverCompletingLoops) } else { exprDefinitelyExits(alternate as Expression, model, neverCompletingLoops) }; consExits && altExits } case _: false }; } export function branchDefinitelyExits(stmt: Statement, model: SemanticModel | null = null, neverCompletingLoops: boolean = true): boolean { return match (stmt) { case ReturnStatement {}: true case BreakStatement {}: true case ContinueStatement {}: true case ExpressionStatement {expression}: exprDefinitelyExits(expression, model, neverCompletingLoops) case BlockStatement {body}: { if (body.length == 0) { false } else { branchDefinitelyExits(body[body.length - 1], model, neverCompletingLoops) } } // A shielded block always runs, and exits when its body does. case ShieldedStatement {body}: branchDefinitelyExits(body, model, neverCompletingLoops) case IfStatement {consequent, alternate}: { if (alternate == null) { false } else { branchDefinitelyExits(consequent, model, neverCompletingLoops) && branchDefinitelyExits(alternate, model, neverCompletingLoops) } } case WhileStatement {test, body}: neverCompletingLoops && loopNeverCompletes(test, body) case ForStatement {test, body}: neverCompletingLoops && loopNeverCompletes(test, body) case _: false }; } /** Whether `test` is the literal `true`. */ export function isTrueLiteral(test: Node): boolean { if (let BooleanLiteral {value} = test) { return value; } return false; } /** * Whether a loop never completes normally: its condition is the literal * `true`, or a `for` has none, and no `break` in its body leaves it. A * `return` or a `throw` is the only way out. */ function loopNeverCompletes(test: Node | null, body: Statement): boolean { if (test != null && !isTrueLiteral(test)) { return false; } return !breaksOutOf(body); } /** * Whether `node` holds a `break` for the loop around it: one outside * every loop body and function nested in `node`. A nested loop's * condition, initializer and update belong to the outer loop, so a * `break` in one of them counts. */ function breaksOutOf(node: Node): boolean { var found = false; walk(node, (n) => { if (found) { return false; } if (n is BreakStatement) { found = true; return false; } if (let WhileStatement {test} = n) { found = breaksOutOf(test); return false; } if (let ForStatement {init, test, update} = n) { found = (init != null && breaksOutOf(init)) || (test != null && breaksOutOf(test)) || (update != null && breaksOutOf(update)); return false; } if (let ForInStatement {iterable} = n) { found = breaksOutOf(iterable); return false; } // A function's breaks belong to its own loops, and a class holds // only functions. return !(n is FunctionExpression) && !(n is ClassDeclaration); }, (_) => {}); return found; } /** * The root binding of a member-path narrowing key: "s42.inner" roots at * symbol 42, "this.x" at nothing assignable. The inverse of the "s" * prefix getMemberPathKey builds. */ export function pathRootSymbolId(path: String): SymbolId { if (path.length < 2 || path.sliceBytes(0, 1) != "s") { return noSymbolId; } var end = 1; // 46 is '.'. while (end < path.length && path.getByteAt(end) != 46) { end += 1; } if (let (true, id) = parseI32(path.sliceBytes(1, end))) { return id as SymbolId; } return noSymbolId; } export function getMemberPathKey(ctx: CheckerContext, expr: Expression): String | null { match (expr) { case Identifier: { let info = ctx.model.resolve(expr); if (info == null) { return null; } return "s" + i32ToString(info.id as i32); } case ThisExpression: { return "this"; } case MemberExpression {object, property, isSymbolAccess}: { let base = getMemberPathKey(ctx, object); if (base == null) { return null; } let propStr = getMemberPropertyName(isSymbolAccess, property.name); return `${base}.${propStr}`; } case _: { return null; } } } export function getMemberPathKeyFromAccess( ctx: CheckerContext, object: Expression, property: Identifier, isSymbolAccess: boolean ): String | null { let base = getMemberPathKey(ctx, object); if (base == null) { return null; } let propStr = getMemberPropertyName(isSymbolAccess, property.name); return `${base}.${propStr}`; } function isImmutableFieldAccess(objectType: Type, propName: String): boolean { let base = unwrapNullableForMemberLookup(objectType); if (base == null) { return false; } match (base) { case ClassType as ct: { if (!ct.members.has(propName)) { return false; } let m = ct.members[propName]; match (m) { case FieldInfo as fi: { return !fi.isMutable; } case _: { return false; } } } case InterfaceType as it: { if (!it.members.has(propName)) { return false; } let m = it.members[propName]; match (m) { case FieldInfo as fi: { return !fi.isMutable; } case _: { return false; } } } case RecordT {properties}: { return properties.has(propName); } case _: { return false; } } } /** * Whether `expr` is a member path whose every step is an immutable * field read off a binding or `this`, so that a narrowing of it holds * for as long as the root does. The object types are the ones the * expression's own check recorded; a path no check has reached yet is * checked here once. */ export function isImmutableMemberPath(ctx: CheckerContext, expr: Expression): boolean { if (let MemberExpression {object, property, isSymbolAccess} = expr) { let objectType = ctx.model.getNodeType(object) ?? checkExpression(ctx, object, null); let propName = getMemberPropertyName(isSymbolAccess, property.name); if (!isImmutableFieldAccess(objectType, propName)) { return false; } match (object) { case Identifier: { return true; } case ThisExpression: { return true; } case MemberExpression: { return isImmutableMemberPath(ctx, object); } case _: { return false; } } } else { return false; } } /** * What a condition narrows: a binding, keyed by its symbol, or an * immutable member path, keyed by `getMemberPathKey`, with the type the * subject has where the condition is tested — the flow type a read * there sees, which is what the condition's own check recorded. */ final class NarrowingSubject { binding: SymbolId; path: String | null; type: Type; new(this.binding, this.path, this.type); } /** The subject `expr` names, or null when a condition on it narrows nothing. */ function narrowingSubject(ctx: CheckerContext, expr: Expression): NarrowingSubject | null { match (expr) { case Identifier: { let info = ctx.model.resolve(expr); if (info == null) { return null; } let t = ctx.model.getNodeType(expr) ?? ctx.resolveIdentifier(expr); if (t == null) { return null; } return new NarrowingSubject(info.id, null, t); } case MemberExpression: { if (!isImmutableMemberPath(ctx, expr)) { return null; } let key = getMemberPathKey(ctx, expr); if (key == null) { return null; } let t = ctx.model.getNodeType(expr) ?? checkExpression(ctx, expr, null); return new NarrowingSubject(noSymbolId, key, t); } case _: { return null; } } } export final class ConditionNarrowings { bindings: HashMap; paths: HashMap; new() : bindings = new Map(), paths = new Map(); /** Records that `subject` is a `t` on this branch. */ narrow(subject: NarrowingSubject, t: Type): void { let {path} = subject; if (path != null) { this.paths[path] = t; } else { this.bindings[subject.binding] = t; } } } /** * What a condition establishes on each of its branches: the narrowings * in force where it was true, and where it was false. */ export final class BranchNarrowings { whenTrue: ConditionNarrowings; whenFalse: ConditionNarrowings; new(this.whenTrue, this.whenFalse); } function mergeNarrowings(ctx: CheckerContext, dest: ConditionNarrowings, src: ConditionNarrowings) { for (let id in src.bindings.keys()) { if (let (true, t) = src.bindings.get(id)) { dest.bindings[id] = t; } } for (let path in src.paths.keys()) { if (let (true, t) = src.paths.get(path)) { dest.paths[path] = t; } } } function intersectNarrowings( ctx: CheckerContext, dest: ConditionNarrowings, left: ConditionNarrowings, right: ConditionNarrowings ) { for (let id in left.bindings.keys()) { if (let (true, leftType) = left.bindings.get(id)) { if (let (true, rightType) = right.bindings.get(id)) { let types = growable([leftType, rightType]); dest.bindings[id] = createUnionType(types, ctx, null); } } } for (let path in left.paths.keys()) { if (let (true, leftType) = left.paths.get(path)) { if (let (true, rightType) = right.paths.get(path)) { let types = growable([leftType, rightType]); dest.paths[path] = createUnionType(types, ctx, null); } } } } /** The one-sided conjunction: both held, so both narrowings hold. */ function both(ctx: CheckerContext, a: ConditionNarrowings, b: ConditionNarrowings) { let result = new ConditionNarrowings(); mergeNarrowings(ctx, result, a); mergeNarrowings(ctx, result, b); return result; } /** The one-sided disjunction: one of them held, so a subject is what * either says, and a subject only one speaks of is unnarrowed. */ function either(ctx: CheckerContext, a: ConditionNarrowings, b: ConditionNarrowings) { let result = new ConditionNarrowings(); intersectNarrowings(ctx, result, a, b); return result; } /** * The narrowings `condition` establishes on its true and false * branches, in one pass over it. Two rules, each on a binding or an * immutable member path: a null test (`s == null`, `s != null`, either * way round) narrows the subject to `null` on one branch and takes * `null` off it on the other; an `is` test narrows it to the tested * type on one branch and takes that type out of its union on the * other. `!` swaps the branches. `a && b` holds both when true, and * when false one of them failed, so a subject is what either side's * false branch says; `a || b` the other way around. The right operand * is read under the left's narrowings in force where it runs — the * left's true branch for `&&`, its false branch for `||`. */ export function conditionNarrowings(ctx: CheckerContext, condition: Expression): BranchNarrowings { match (condition) { case UnaryExpression {operator, argument}: { if (operator == "!") { let inner = conditionNarrowings(ctx, argument); return new BranchNarrowings(inner.whenFalse, inner.whenTrue); } } case BinaryExpression {operator, left, right}: { if (operator == "&&" || operator == "||") { let isAnd = operator == "&&"; let a = conditionNarrowings(ctx, left); // The right side is analyzed under the left's narrowings: a // temporary node on the flow, removed by restoring. let savedFlow = ctx.currentFlow; ctx.pushFlowNarrowings(if (isAnd) a.whenTrue else a.whenFalse); let b = conditionNarrowings(ctx, right); ctx.setFlow(savedFlow); return if (isAnd) { new BranchNarrowings(both(ctx, a.whenTrue, b.whenTrue), either(ctx, a.whenFalse, b.whenFalse)) } else { new BranchNarrowings(either(ctx, a.whenTrue, b.whenTrue), both(ctx, a.whenFalse, b.whenFalse)) }; } if (operator == "==" || operator == "!=" || operator == "===" || operator == "!==") { let tested: Expression | null = if (right is NullLiteral) { left } else if (left is NullLiteral) { right } else { null }; if (tested == null) { let discriminated = discriminantNarrowings(ctx, left, right) ?? discriminantNarrowings(ctx, right, left); if (discriminated == null) { return new BranchNarrowings(new ConditionNarrowings(), new ConditionNarrowings()); } let found = discriminated; return if (operator == "==" || operator == "===") { found } else { new BranchNarrowings(found.whenFalse, found.whenTrue) }; } let subject = narrowingSubject(ctx, tested); if (subject == null) { return new BranchNarrowings(new ConditionNarrowings(), new ConditionNarrowings()); } let isNull = new ConditionNarrowings(); isNull.narrow(subject, new NullType()); let isNotNull = new ConditionNarrowings(); isNotNull.narrow(subject, subtractNullFromType(subject.type)); return if (operator == "==" || operator == "===") { new BranchNarrowings(isNull, isNotNull) } else { new BranchNarrowings(isNotNull, isNull) }; } } case IsExpression {expression, typeAnnotation}: { let subject = narrowingSubject(ctx, expression); if (subject == null) { return new BranchNarrowings(new ConditionNarrowings(), new ConditionNarrowings()); } let target = resolveTypeAnnotation(ctx, typeAnnotation); let whenTrue = new ConditionNarrowings(); whenTrue.narrow(subject, target); let whenFalse = new ConditionNarrowings(); whenFalse.narrow(subject, subtractTypeFromUnion(subject.type, target)); return new BranchNarrowings(whenTrue, whenFalse); } case _: {} } return new BranchNarrowings(new ConditionNarrowings(), new ConditionNarrowings()); } /** * What `x.f == literal` establishes when `x` is a union of record types * told apart by `f`, as a discriminated union is: where it holds, `x` is * the members whose `f` can be that literal; where it does not, the * members whose `f` is not exactly it. A member whose `f` is wider than a * literal (`i32`) stays on both sides. Null when `access` is not such a * read or `literal` not a literal. */ function discriminantNarrowings(ctx: CheckerContext, access: Expression, literal: Expression): BranchNarrowings | null { if (!(access is MemberExpression) || !(literal is NumberLiteral || literal is BooleanLiteral || literal is StringLiteral)) { return null; } let member = access; let subject = narrowingSubject(ctx, member.object); if (subject == null) { return null; } let union = baseType(subject.type); if (!(union is UnionT)) { return null; } let members = recordUnionMembersOf(union); if (members == null) { return null; } let field = member.property.name; let equal = new Array(); let unequal = new Array(); for (let rec in members) { if (!rec.properties.has(field)) { return null; } let fits = literalFits(rec.properties[field], literal); if (fits != 0) { equal.push(rec); } if (fits != 1) { unequal.push(rec); } } if (equal.length == members.length && unequal.length == members.length) { return null; } let whenTrue = new ConditionNarrowings(); whenTrue.narrow(subject, narrowedMembers(ctx, equal)); let whenFalse = new ConditionNarrowings(); whenFalse.narrow(subject, narrowedMembers(ctx, unequal)); return new BranchNarrowings(whenTrue, whenFalse); } /** The union of the members a narrowing keeps: `never` for none. */ function narrowedMembers(ctx: CheckerContext, members: GrowableArray): Type { if (members.length == 0) { return new NeverType(); } return if (members.length == 1) members[0] else createUnionType(members, ctx, null); } /** Puts `condition`'s true-branch narrowings on the flow: for a * consumer that has only that branch, such as `&&`'s right operand or * a match guard's arm. A consumer with both branches calls * `conditionNarrowings` once. */ export function applyTrueNarrowingFromCondition(ctx: CheckerContext, condition: Expression): void { ctx.pushFlowNarrowings(conditionNarrowings(ctx, condition).whenTrue); } /** Puts `condition`'s false-branch narrowings on the flow: `||`'s * right operand. */ export function applyFalseNarrowingFromCondition(ctx: CheckerContext, condition: Expression): void { ctx.pushFlowNarrowings(conditionNarrowings(ctx, condition).whenFalse); } /** The symbols assigned under one loop, collected by the walk below. */ final class LoopAssignments { ids = new Array(); #seen = new Set(); add(id: SymbolId): void { if (!this.#seen.has(id as i32)) { this.#seen.add(id as i32); this.ids.push(id); } } } function isLoopStatement(n: Node) { return n is WhileStatement || n is ForStatement || n is ForInStatement; } /** * Every symbol assigned anywhere under `node`, deduplicated. Loops * record these at the loop header as unknown-type flow assignments: * a reference in the body is checked before the loop's back edge * exists, yet on every iteration after the first it observes the * previous iteration's stores, so the header must already carry them. * Descends into nested functions on purpose — a closure created in the * body can run on any iteration. * * One walk serves every loop under `node` as well: each loop open in * the walk collects the assignments beneath it, and the sets are kept * on the context by loop, so a nested loop's header finds its own * without walking its body again. Nested loops used to cost depth * times body size. */ function collectAssignedSymbolIds(ctx: CheckerContext, node: Node) { if (let (true, collected) = ctx.loopAssignments.get(node.id as i32)) { return collected; } // The loops open at the walk's position, `node`'s own set first. let open = growable([new LoopAssignments()]); walk(node, (n) => { if (n.id != node.id && isLoopStatement(n)) { open.push(new LoopAssignments()); } if (n is AssignmentExpression) { if (n.left is Identifier) { let info = ctx.model.resolve(n.left); if (info != null) { for (let loop in open) { loop.add(info.id); } } } } return true; }, (n) => { if (n.id != node.id && isLoopStatement(n)) { let closed = open.pop(); ctx.loopAssignments[n.id as i32] = closed.ids; } }); let own = open.pop(); ctx.loopAssignments[node.id as i32] = own.ids; return own.ids; } /** * Record `node`'s assignments at the current position (a loop header) * as unknown-type stores. See collectAssignedSymbolIds. */ export function recordLoopAssignments(ctx: CheckerContext, node: Node): void { for (let assignedId in collectAssignedSymbolIds(ctx, node)) { ctx.recordFlowAssignment(assignedId, null); } }