Expansion: resolving unresolved elements

The expand module resolves the unresolved Element kinds — Alias, Reference, MemberReference, GlobalReference, Conditional, Derived, Variable — into structural types the lattice can reason about.

use suffete::expand;

let resolved: TypeId = expand::expand(input, &world);

The contract is one direction: the analyser must call expand on a type before passing it to the lattice if the type might contain any unresolved Element. The lattice does not invoke expansion itself; the recursion would loop, and the analyser knows when expansion is safe in a way the lattice cannot.

Why expansion is the analyser's job

Resolving an Alias requires looking the alias name up in the analyser's alias table. Resolving a Conditional requires evaluating the subject vs target subtype check, which requires the world. Resolving a Derived requires walking into the target type and applying the transformation.

All of these are traversals the analyser may want to control: cache the result, abort on a cycle, expand only some kinds (e.g. expand aliases but leave conditionals lazy), produce diagnostics on unresolved names. The lattice would have one fixed strategy; the analyser benefits from having the choice.

What `expand` does

expand(ty, world) walks the type tree and replaces every unresolved Element with its structural form, recursing into nested types. The high-level rules:

Alias { name } ; resolve via world.alias_body(class, alias). If the alias is itself an alias chain, follow until structural.
Reference { name, type_args, intersections } ; resolve name to a class-like or a template parameter via the world's symbol table. Substitute type_args if applicable.
MemberReference { class, name } ; resolve the member name on the class via world.class_constant_type (or similar member-type query).
GlobalReference { name } ; resolve via world.global_constant_type(name).
Conditional { subject, target, then, otherwise } ; check subject <: target via the lattice. Return then if yes, otherwise if no.
Derived(...) ; apply the per-variant transformation.
Variable { id } ; look up id in the analyser's inference state.

The catch-all expand uses ExpansionContext::default(), which leaves conditionals untouched (eval_conditional defaults to false). To resolve conditionals, or to bind self/static/parent, or to substitute free template parameters with their constraints, call expand_with(ty, world, &ctx) and configure the ExpansionContext fields (see Expansion context). Free GenericParameter atoms are substituted only when ctx.substitute_template_constraints is on; otherwise they pass through opaque.

Worked example: `Alias`

/** @type UserId = positive-int */

function find(UserId $id): User { ... }

The parameter type is parsed as Alias { name: "UserId" }. Before the analyser checks find(7), it expands:

let alias_t = ...; // contains Alias { name: "UserId" }
let resolved = expand::expand(alias_t, &world);
// resolved == int<1, ∞>  (the underlying type of UserId)

The world's alias_body(class, "UserId") returns the underlying type; expansion substitutes it.

Worked example: `Conditional`

/**
 * @template T
 * @return ($T extends int ? string : bool)
 */
function classify(): mixed { ... }

The return type is Conditional { subject: T, target: int, then: string, otherwise: bool }. After the call site has bound T := int(7), the subject is already the concrete int(7). Conditional evaluation is opt-in, so use expand_with with eval_conditional enabled:

use suffete::expand::{self, ExpansionContext};

let cond_t = ...; // Conditional { subject: int(7), target: int, then: string, otherwise: bool }
let ctx = ExpansionContext { eval_conditional: true, ..ExpansionContext::default() };
let resolved = expand::expand_with(cond_t, &world, &ctx);
// Step 1: check int(7) <: int → true (decided via the lattice).
// Step 2: take the `then` branch.
// resolved == string

If the subject were bool instead, the target check would fail and the otherwise branch (bool) would be taken. With the default context (eval_conditional off), the conditional atom is left in place unchanged.

Worked example: `Derived` (KeyOf)

/** @type Shape = array{a: int, b: string} */
/** @type Keys = key-of<Shape> */

The type Keys is Derived(KeyOf(Alias("Shape"))). Expansion:

Resolve the inner Alias("Shape") → array{a: int, b: string}.
Apply KeyOf to the result: extract the keys → 'a' | 'b'.

The Derived(KeyOf) variant has a per-kind transformation. For keyed arrays, it returns the union of literal-string keys (or array-key if the array is unsealed). For lists, it returns int (or a range of valid indices). For objects, it returns the property names.

Recursion and termination

Aliases can be chains: A = B, B = C, C = int. Expansion follows the chain. Suffete does not detect cycles directly ; the world's alias_body is expected to return None for unknown names, which terminates the chain naturally.

If the analyser needs cycle detection, it should detect cycles in its alias table during ingestion and report a diagnostic before suffete sees the type.

Expansion context

Sometimes the analyser wants to expand some kinds but not others ; expand aliases but defer conditionals until enough template bindings exist, for example. There are no per-kind expansion functions; instead, expand_with takes an ExpansionContext whose boolean fields gate each kind of resolution:

use suffete::expand::{self, ExpansionContext};

// Expand aliases only, leaving class/global constants and conditionals in place.
let alias_only = expand::expand_with(input, &world, &ExpansionContext {
    eval_aliases: true,
    eval_class_constants: false,
    eval_global_constants: false,
    eval_conditional: false,
    ..ExpansionContext::default()
});

The fields of ExpansionContext are:

self_class: Option<Word>, static_class: Option<Word>, parent_class: Option<Word> ; the contextual class names a self / static / parent reference resolves to.
eval_class_constants: bool ; gate Foo::CONST resolution (default true).
eval_global_constants: bool ; gate \GLOBAL_NAME resolution (default true).
eval_aliases: bool ; gate @type Foo = ... alias body resolution (default true).
eval_conditional: bool ; decide T is U ? A : B via the lattice when on (default false).
fill_template_defaults: bool ; fill omitted type-args on a generic class reference with the parameters' upper bounds (default false).
substitute_template_constraints: bool ; replace a free GenericParameter atom with its constraint (default false).
function_is_final: bool ; drop the static modality on named-object atoms even without a static_class (default false).

ExpansionContext::default() is the same context the catch-all expand uses. The catch-all is the most common entry point.

Cost

Expansion is O(tree size) for the type, plus the per-kind costs:

Alias and Reference resolution: one world query per kind.
Conditional resolution: one refines call (lattice cost) plus the substitution.
Derived resolution: variant-specific, but bounded by the input's tree size.

The most expensive cases are Conditional chains where each branch is itself a Conditional with a non-trivial subject ; the lattice is invoked recursively. Most analyser-level types resolve in microseconds.

Idempotence

expand is idempotent: expand(expand(t)) == expand(t) (assuming no world changes between calls). The analyser can call expand without worrying about double expansion.

Detecting whether expansion is needed

The predicates chapter exposes:

use suffete::predicates::is_fully_resolved;

if !is_fully_resolved(ty) {
    ty = expand::expand(ty, &world);
}

This is the recommended pattern for analyser code that consumes types from the type-source layer (the parser, the codebase model, the docblock interpreter) and feeds them to the lattice.

A worked example: full pipeline

use suffete::{TypeId, expand, lattice::{self, LatticeOptions, LatticeReport}};
use suffete::predicates::is_fully_resolved;

fn analyser_check<W: suffete::world::World>(
    input: TypeId,
    expected: TypeId,
    world: &W,
) -> bool {
    let input    = if is_fully_resolved(input)    { input    } else { expand::expand(input, world) };
    let expected = if is_fully_resolved(expected) { expected } else { expand::expand(expected, world) };

    let opts = LatticeOptions::default();
    let mut report = LatticeReport::new();

    lattice::refines(input, expected, world, opts, &mut report)
}

The pattern: expand each side if needed, then call the lattice. Trivial wrapper, but the right interface to enforce on every analyser-side query.

See also: Unresolved elements for the kinds expansion handles; Predicates for is_fully_resolved; World for the resolution methods used during expansion; Conditional and Derived for the per-variant rules.

The Suffete Book