scope

Documentation

Overview

Package scope provides lexical scope state for type checking.

This package maintains the scope state at each CFG point, tracking which variables are visible and their symbol IDs. Scope states are used by the type synthesizer to resolve identifiers.

Scope State

State represents the scope at a specific CFG point:

• Parent scope reference (for nested functions)
• Visible symbols and their types
• Global symbol access

Scope Construction

Scopes are built during CFG construction and refined during type checking. The scope at each point reflects:

• Function parameters
• Local variable declarations up to that point
• Captured variables from enclosing scopes

Symbol Resolution

The package provides methods to:

• Look up symbols by name
• Determine if a symbol is local or global
• Access parent scope for captured variables

Integration

Scope states are stored per CFG point and accessed by the type synthesizer when evaluating expressions.

Package scope provides immutable lexical scope state with HAMT-based symbol tables.

This package implements the lexical scoping model for the Lua type checker. Each State represents a snapshot of the type namespace and lexical metadata at a specific point in code. States are immutable and support efficient structural sharing through Hash Array Mapped Tries (HAMTs), enabling cheap copy-on-write semantics.

Architecture

The scope state tracks two categories of information:

Type Namespace: Type definitions and type parameters visible at this scope level. Type definitions are created by `type` annotations and propagate to child scopes. Type parameters are bound by generic function definitions.

Lexical Metadata: Local variable declarations and mutation tracking. Local names indicate which variables are declared in the current scope (vs inherited). Mutation tracking records which variables have been assigned after their initial declaration, enabling flow-sensitive analysis.

Value Type Separation

Value types (the types of variables at each program point) are NOT stored in scope. They are stored externally in flow.DeclaredTypes, which provides flow-sensitive type maps. This separation allows the scope state to remain stable across flow iterations while value types evolve during fixpoint computation.

Immutability and Structural Sharing

All State methods that modify state return a new State instance. The underlying HAMT data structures share unchanged nodes between old and new states, making modifications O(log n) in both time and space. This enables efficient snapshotting and backtracking during type analysis.

Scope Hierarchy

Scopes form a tree structure through parent links. Each function body, block, and control flow construct can introduce a new scope. Type definitions propagate down (children see parent types), while local declarations do not (each scope tracks only its own locals).

Index

• func BuildTypeDefScopes(graph *cfg.Graph, base *State, resolver TypeDefResolver) map[cfg.Point]*State
• func ToTypeParamExprs(params []cfg.TypeParamInfo) []ast.TypeParamExpr
• type State
  • func EnrichWithTypeDefs(graph *cfg.Graph, base *State, resolver TypeDefResolver) *State
  • func MergeScopeExit(parent *State, child *State) *State
  • func New() *State
  • func NewWithBuiltins() *State
  • func (s *State) AllLocals() map[string]bool
  • func (s *State) AllMutated() map[string]bool
  • func (s *State) AllTypes() map[string]typ.Type
  • func (s *State) Child() *State
  • func (s *State) Depth() int
  • func (s *State) GroupHash() uint64
  • func (s *State) Hash() uint64
  • func (s *State) ID() uint64
  • func (s *State) IsLocal(name string) bool
  • func (s *State) IsMutated(name string) bool
  • func (s *State) LookupType(name string) (typ.Type, bool)
  • func (s *State) LookupTypeParam(name string) (typ.Type, bool)
  • func (s *State) MetaForName(name string) *typ.Meta
  • func (s *State) Name() string
  • func (s *State) Parent() *State
  • func (s *State) RangeLocals(fn func(name string) bool)
  • func (s *State) RangeMutations(fn func(name string) bool)
  • func (s *State) RangeTypeParams(fn func(name string, t typ.Type) bool)
  • func (s *State) RangeTypes(fn func(name string, t typ.Type) bool)
  • func (s *State) ReturnTypes() []typ.Type
  • func (s *State) SelfType() typ.Type
  • func (s *State) Stamp() uint64
  • func (s *State) TypeParams() map[string]typ.Type
  • func (s *State) VariadicType() typ.Type
  • func (s *State) WithLocalName(name string) *State
  • func (s *State) WithLocalNames(names []string) *State
  • func (s *State) WithMutated(name string) *State
  • func (s *State) WithMutatedNames(names []string) *State
  • func (s *State) WithName(name string) *State
  • func (s *State) WithReturn(types []typ.Type) *State
  • func (s *State) WithSelf(self typ.Type) *State
  • func (s *State) WithType(name string, t typ.Type) *State
  • func (s *State) WithTypeParams(params map[string]typ.Type) *State
  • func (s *State) WithTypes(types map[string]typ.Type) *State
  • func (s *State) WithVariadic(t typ.Type) *State
• type TypeDefResolver

Functions

func BuildTypeDefScopes

func BuildTypeDefScopes(
	graph *cfg.Graph,
	base *State,
	resolver TypeDefResolver,
) map[cfg.Point]*State

BuildTypeDefScopes walks TypeDef nodes in RPO order and returns a scope for each point that includes all type definitions visible at that point.

This function implements forward propagation of type definitions through the control flow graph. Each TypeDef node introduces a new type alias that becomes visible at all subsequent points (in RPO order).

Processing order uses Reverse Post Order (RPO) to ensure that definitions are processed before their uses in straight-line code. For generic types, the resolved type is stored directly; for non-generic types, an alias wrapper preserves the user-defined name.

The returned map provides O(1) lookup of the scope state at any CFG point, enabling efficient type resolution during expression synthesis.

func ToTypeParamExprs

func ToTypeParamExprs(params []cfg.TypeParamInfo) []ast.TypeParamExpr

ToTypeParamExprs converts cfg type params to ast type param expressions.

CFG stores type parameters in a simplified form (TypeParamInfo) that captures name and constraint. The AST representation (TypeParamExpr) is needed for type resolution, which operates on AST nodes. This function bridges the two representations.

Types

type State

type State struct {
	// contains filtered or unexported fields
}

State is immutable lexical scope state.

State contains the type namespace (type definitions, type parameters) and lexical metadata (local declarations, mutation markers). Value types are stored separately in flow.DeclaredTypes to support flow-sensitive analysis.

All modification methods return new State instances. The underlying HAMT structures provide O(log n) copy-on-write semantics with structural sharing.

Scope Metadata

Each State has a unique ID (for identity), a stamp (for content versioning), a depth (nesting level from root), an optional name, and a parent link. The ID never changes for a logical scope, while the stamp updates on any content modification.

Function Context

States also carry function-level context: self type (for method definitions), variadic type (for ... parameters), and expected return types. These propagate to child scopes via Child() and can be overridden with With* methods.

func EnrichWithTypeDefs

func EnrichWithTypeDefs(
	graph *cfg.Graph,
	base *State,
	resolver TypeDefResolver,
) *State

EnrichWithTypeDefs walks TypeDef nodes in RPO order and returns a scope that includes all type definitions from the graph.

This is a convenience wrapper around BuildTypeDefScopes that returns only the final accumulated scope. Use this when you need the complete type namespace after processing all definitions, but don't need per-point scope snapshots.

Common use case: Building the scope for a module's top-level, where all type definitions should be visible to subsequent analysis.

func MergeScopeExit

func MergeScopeExit(parent *State, child *State) *State

MergeScopeExit merges child scope metadata back into parent on scope exit.

When a block or function scope exits, mutations performed in the child scope to non-local variables must be reflected in the parent scope. This function propagates mutation markers for variables that were modified in the child but declared in an ancestor scope.

Only mutation metadata is propagated; value types are stored externally in flow.DeclaredTypes and merged separately. Local declarations in the child are not propagated since they go out of scope.

This is essential for accurate escape analysis and mutation tracking across nested function boundaries.

func New

func New() *State

New creates an empty root scope.

func NewWithBuiltins

func NewWithBuiltins() *State

NewWithBuiltins creates a root scope with builtin type definitions.

func (*State) AllLocals

func (s *State) AllLocals() map[string]bool

AllLocals returns locally declared names for this scope.

func (*State) AllMutated

func (s *State) AllMutated() map[string]bool

AllMutated returns all names marked as mutated in this scope chain.

func (*State) AllTypes

func (s *State) AllTypes() map[string]typ.Type

AllTypes returns all visible type definitions.

func (*State) Child

func (s *State) Child() *State

Child creates a child scope inheriting type namespace.

The child scope receives:

• All type definitions from the parent (inherited)
• All type parameters from the parent (inherited)
• Function context: self type, variadic type, return types (inherited)
• Mutation markers from the parent (mutations propagate up)

The child scope does NOT inherit:

• Local declarations (each scope tracks only its own locals)

Child scopes are used for function bodies, block statements, and control flow constructs. The parent link enables scope chain traversal for debugging and group hash computation.

func (*State) Depth

func (s *State) Depth() int

Depth returns scope nesting depth (0 for root).

func (*State) GroupHash

func (s *State) GroupHash() uint64

GroupHash returns the hash used to group sibling functions.

Functions defined in the same parent scope share a group hash, enabling the type checker to identify and process mutually recursive function groups together. The group hash is the parent scope's content hash, ensuring that functions see consistent types for their siblings.

For root-level scopes (no parent), the scope's own hash is used as the group hash. This maintains the invariant that all scopes have a valid group hash.

func (*State) Hash

func (s *State) Hash() uint64

Hash returns a stable content hash for this scope.

The hash incorporates parent hash, depth, name, function context (self type, variadic type, return types), and the contents of type/typeParam/local/mutated maps. Two scopes with identical content produce identical hashes.

The hash is computed lazily and cached. Since State is immutable after creation, the cached value remains valid for the lifetime of the State.

func (*State) ID

func (s *State) ID() uint64

ID returns the unique scope identifier.

func (*State) IsLocal

func (s *State) IsLocal(name string) bool

IsLocal reports whether the name is declared in the current scope.

func (*State) IsMutated

func (s *State) IsMutated(name string) bool

IsMutated reports whether the name was mutated in this scope chain.

func (*State) LookupType

func (s *State) LookupType(name string) (typ.Type, bool)

LookupType finds a type definition. O(log n).

func (*State) LookupTypeParam

func (s *State) LookupTypeParam(name string) (typ.Type, bool)

LookupTypeParam finds a type parameter. O(log n).

func (*State) MetaForName

func (s *State) MetaForName(name string) *typ.Meta

MetaForName looks up a type definition by name and wraps it in Meta.

func (*State) Name

func (s *State) Name() string

Name returns the scope name.

func (*State) Parent

func (s *State) Parent() *State

Parent returns the parent scope, if any.

func (*State) RangeLocals

func (s *State) RangeLocals(fn func(name string) bool)

RangeLocals iterates over local names without allocation.

func (*State) RangeMutations

func (s *State) RangeMutations(fn func(name string) bool)

RangeMutations iterates over mutated names without allocation.

func (*State) RangeTypeParams

func (s *State) RangeTypeParams(fn func(name string, t typ.Type) bool)

RangeTypeParams iterates over all type parameters without allocation.

func (*State) RangeTypes

func (s *State) RangeTypes(fn func(name string, t typ.Type) bool)

RangeTypes iterates over all visible type definitions without allocation.

func (*State) ReturnTypes

func (s *State) ReturnTypes() []typ.Type

ReturnTypes returns expected return types.

func (*State) SelfType

func (s *State) SelfType() typ.Type

SelfType returns the current self type.

func (*State) Stamp

func (s *State) Stamp() uint64

Stamp returns the stable content stamp for this state instance.

func (*State) TypeParams

func (s *State) TypeParams() map[string]typ.Type

TypeParams returns all type parameters.

func (*State) VariadicType

func (s *State) VariadicType() typ.Type

VariadicType returns the variadic parameter type.

func (*State) WithLocalName

func (s *State) WithLocalName(name string) *State

WithLocalName marks a name as locally declared.

func (*State) WithLocalNames

func (s *State) WithLocalNames(names []string) *State

WithLocalNames marks multiple names as locally declared.

func (*State) WithMutated

func (s *State) WithMutated(name string) *State

WithMutated marks a name as mutated.

func (*State) WithMutatedNames

func (s *State) WithMutatedNames(names []string) *State

WithMutatedNames marks multiple names as mutated.

func (*State) WithName

func (s *State) WithName(name string) *State

WithName returns new state with scope name set.

func (*State) WithReturn

func (s *State) WithReturn(types []typ.Type) *State

WithReturn returns new state with return types set.

func (*State) WithSelf

func (s *State) WithSelf(self typ.Type) *State

WithSelf returns new state with self type set.

func (*State) WithType

func (s *State) WithType(name string, t typ.Type) *State

WithType returns new state with type definition added.

func (*State) WithTypeParams

func (s *State) WithTypeParams(params map[string]typ.Type) *State

WithTypeParams returns new state with type parameters added.

func (*State) WithTypes

func (s *State) WithTypes(types map[string]typ.Type) *State

WithTypes returns new state with multiple type definitions added.

func (*State) WithVariadic

func (s *State) WithVariadic(t typ.Type) *State

WithVariadic returns new state with variadic type set.

type TypeDefResolver

type TypeDefResolver func(name string, typeExpr ast.TypeExpr, typeParams []ast.TypeParamExpr, sc *State) typ.Type

TypeDefResolver resolves a type definition to its concrete type.

This callback is invoked during scope construction when a TypeDef CFG node is encountered. The resolver translates the AST type expression into a concrete typ.Type, using the current scope state to resolve type references.

Parameters:

• name: The type alias name being defined
• typeExpr: The AST type expression (right-hand side of the definition)
• typeParams: Generic type parameters for the definition (may be empty)
• sc: Current scope state for resolving type references

The resolver should return a typ.Generic for parameterized types, or the resolved type directly for non-generic definitions.