Documentation
¶
Overview ¶
Package subtype provides subtype checking with seen-map cycle detection.
Subtype checking determines whether a value of type A can be safely used where type B is expected. This is fundamental to type safety: assignments, function calls, and return statements all require subtype checks.
Subtype Rules ¶
Basic rules:
- T <: T (reflexivity)
- Never <: T (bottom is subtype of all)
- T <: Any (all are subtypes of top)
- T <: Unknown (unknown accepts all for gradual typing)
- Integer <: Number (numeric hierarchy)
Composite rules:
- Union: (A|B) <: C iff A <: C and B <: C
- Optional: T <: T? always; T? <: U iff T <: U and nil <: U
- Function: contravariant params, covariant returns
- Record: width subtyping (more fields OK), depth subtyping (field types)
Cycle Detection ¶
Recursive types can form infinite subtype derivations. The checker uses interface-identity seen pairs for coinductive cycle detection: if a pair (A, B) is encountered again, the check succeeds (coinductive assumption).
Type Normalization ¶
The package also provides union and intersection normalization:
- NormalizeUnion removes redundant members via subtype subsumption
- NormalizeIntersection distributes over unions and detects incompatible primitives
Type Widening ¶
Widening converts specific types to more general forms:
- Widen converts literal types to their base types (shallow)
- WidenForInference recursively widens nested types (deep)
Variance ¶
Variance utilities for generic type parameter analysis:
- Variance represents covariant, contravariant, invariant, or bivariant positions
- FlipVariance inverts variance when entering contravariant positions
- CombineVariance composes variances through nested type constructors
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func IsSubtype ¶
IsSubtype reports whether sub is a subtype of super according to structural subtyping rules. This is the primary entry point for subtype checking.
The check is pure (no side effects) and non-memoized. For repeated checks on the same types, consider caching results externally.
Returns false if either type is nil.
Examples:
IsSubtype(typ.Integer, typ.Number) // true: integer <: number IsSubtype(typ.Never, typ.String) // true: never <: any type IsSubtype(typ.String, typ.Any) // true: any type <: any IsSubtype(typ.String, typ.Number) // false: incompatible primitives
func NormalizeIntersection ¶
NormalizeIntersection creates a normalized intersection type with simplification.
Normalization rules:
- Flatten nested intersections: (A & B) & C becomes A & B & C
- Never absorbs all: A & never = never
- Remove any/unknown: A & any = A, A & unknown = A
- Detect incompatible primitives: string & number = never
- Distribute over unions: (A | B) & C = (A & C) | (B & C)
Distribution is bounded by internal.MaxDistributionProduct to prevent exponential blowup when intersecting large unions.
Returns Any for empty input, the single type for single input.
Examples:
NormalizeIntersection(string, any) // string NormalizeIntersection(string, number) // never (incompatible) NormalizeIntersection(string, never) // never (absorbs)
func NormalizeUnion ¶
NormalizeUnion creates a normalized union type with subtype-based simplification.
Normalization rules applied in order:
- Flatten nested unions: (A | B) | C becomes A | B | C
- Expand optionals: T? becomes T | nil
- Absorb by any: A | any = any
- Remove never: A | never = A
- Remove subsumed types: if A <: B, then A | B simplifies to B
The result is a minimal union where no member is a subtype of another. Returns Never for empty input, the single type for single input.
Examples:
NormalizeUnion(string, never) // string NormalizeUnion(integer, number) // number (integer subsumed) NormalizeUnion(string, any, number) // any (absorbs all)
func Widen ¶
Widen converts a type to a more general form by replacing literals with base types.
Widening is used when types flow to mutable locations or when we want to prevent overly-specific type inference.
Widening rules:
- Literal boolean -> boolean
- Literal integer -> integer
- Literal number -> number
- Literal string -> string
- Union: widen each member, then normalize
- Optional: widen the inner type
- All other types: unchanged
This is a shallow operation; nested types within records, arrays, maps, and functions are not widened. Use WidenForInference for deep widening.
Returns nil if t is nil.
func WidenForInference ¶
WidenForInference performs deep widening, recursively widening nested types.
Used during type inference to prevent overly specific inferred types. This is more aggressive than Widen and processes nested structures:
- Tuple elements: each element is recursively widened
- Array elements: the element type is recursively widened
- Map key/value: both are recursively widened
- Record fields: each field type is recursively widened
- Large records (> DefaultRecursionDepth fields): collapsed to Map<string, union>
The large record collapse prevents type explosion when inferring types for data structures with many fields.
Returns nil if t is nil.
Types ¶
type Variance ¶
type Variance int
Variance describes how a type parameter position relates to subtyping.
In generic type contexts, variance determines how type parameters relate when the containing type is subtyped:
Invariant: The type parameter must be exactly equal. Used for mutable references where both reading and writing occur.
Covariant: A subtype can be used where a supertype is expected. Used for read-only/producer positions like function return types.
Contravariant: A supertype can be used where a subtype is expected. Used for write-only/consumer positions like function parameters.
Bivariant: Either subtype or supertype is acceptable. Rarely used, typically indicates the type parameter is unused or phantom.
func CombineVariance ¶
CombineVariance combines two variances when composing type constructors.
For example, a covariant position inside a contravariant position becomes contravariant overall. Invariant absorbs all variances, and bivariant is absorbed by all.
func CombineVariancePositions ¶
CombineVariancePositions combines variances from different uses of a type parameter.
When a type parameter appears in multiple positions with different variances, this function determines the combined variance. Equal variances stay the same, bivariant is absorbed by the other, and different non-bivariant variances become invariant.
func FlipVariance ¶
FlipVariance inverts variance for contravariant positions.
When entering a contravariant position (like a function parameter type), the variance of nested positions flips: covariant becomes contravariant and vice versa.
Source Files