cfg

package
v1.5.12 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 3, 2026 License: MIT Imports: 11 Imported by: 0

Documentation

Overview

Package cfg constructs control flow graphs from Lua AST nodes.

This package transforms parsed Lua code into a graph representation suitable for dataflow analysis. The CFG captures control flow through branches, loops, and function calls while preserving variable scope and SSA versioning.

Core Types

Graph is the primary type, holding:

  • The underlying CFG structure with entry/exit points
  • NodeInfo for each CFG point (assignments, calls, branches, returns)
  • SSA versioning for all variables
  • Scope visibility maps for lexical scoping
  • Nested function references for hierarchical analysis

Builder constructs graphs incrementally from AST traversal. It handles:

  • Creating CFG nodes and edges
  • Tracking scope entry/exit
  • Computing SSA versions via dominance frontiers
  • Extracting nested function definitions

ScopeTracker maintains lexical scope during construction:

  • Symbol registration at declaration points
  • Visibility snapshots at each CFG point
  • Global vs local symbol distinction

Node Information Types

Each CFG node carries semantic information via the NodeInfo interface:

  • AssignInfo: Local/global assignments with targets and sources
  • CallInfo: Function calls with callee, arguments, and receiver
  • ReturnInfo: Return statements with expressions
  • BranchInfo: Conditional branches with condition analysis
  • FuncDefInfo: Function definitions (global, field, method)
  • TypeDefInfo: Type alias definitions

SSA Versioning

The package computes SSA (Static Single Assignment) form using the Cytron et al. dominance-frontier algorithm:

  1. Collect all assigned symbols across the function
  2. Compute dominance frontiers via immediate dominators
  3. Place phi nodes at iterated dominance frontiers
  4. Rename variables during dominator-tree traversal

SSA versioning enables precise dataflow tracking through control flow joins. The Version type identifies a specific definition of a symbol, and PhiInfo represents join points where multiple definitions merge.

Symbol Resolution

Symbols are bound during a separate binder pass that runs before CFG construction. The Builder receives a pre-populated bind.BindingTable mapping AST identifiers to unique SymbolIDs. This ensures consistent symbol identity across the analysis.

Usage

Typical usage involves calling Build or BuildWithBindings: 

// Simple case: build with automatic binding
graph := cfg.Build(funcExpr, "print", "error")

// Module case: share bindings across functions
bindings := bind.Bind(moduleFunc, globalNames...)
graph := cfg.BuildWithBindings(funcExpr, bindings)

The resulting graph provides iteration methods for processing nodes: 

graph.EachAssign(func(p cfg.Point, info *cfg.AssignInfo) {
    // Process assignment at point p
})

graph.EachStmtCall(func(p cfg.Point, info *cfg.CallInfo) {
    // Process call statements at point p
})

graph.EachCallSite(func(p cfg.Point, info *cfg.CallInfo) {
    // Process all callsites, including assignment/return call expressions
})

Nested Functions

Nested function definitions are collected during CFG construction and accessible via Graph.NestedFunctions. Each NestedFunc contains the definition point, AST node, and assigned symbol. Callers typically build separate graphs for nested functions and link them via symbol IDs.

Package cfg provides CFG construction utilities.

Package cfg provides CFG construction utilities.

Index

Constants

View Source 
const (
	SymbolUnknown = basecfg.SymbolUnknown
	SymbolLocal   = basecfg.SymbolLocal
	SymbolGlobal  = basecfg.SymbolGlobal
	SymbolParam   = basecfg.SymbolParam
	SymbolUpvalue = basecfg.SymbolUpvalue
)

Symbol kind constants.

View Source 
const (
	NodeEntry      = basecfg.NodeEntry
	NodeExit       = basecfg.NodeExit
	NodeAssign     = basecfg.NodeAssign
	NodeCall       = basecfg.NodeCall
	NodeBranch     = basecfg.NodeBranch
	NodeJoin       = basecfg.NodeJoin
	NodeReturn     = basecfg.NodeReturn
	NodeScopeEnter = basecfg.NodeScopeEnter
	NodeScopeExit  = basecfg.NodeScopeExit
	NodeTypeDef    = basecfg.NodeTypeDef
)

Node kind constants.

View Source 
const (
	CheckNone      = basecfg.CheckNone
	CheckTruthy    = basecfg.CheckTruthy
	CheckFalsy     = basecfg.CheckFalsy
	CheckNil       = basecfg.CheckNil
	CheckNotNil    = basecfg.CheckNotNil
	CheckLimit     = basecfg.CheckLimit
	CheckTypeEqual = basecfg.CheckTypeEqual
	CheckTypeNot   = basecfg.CheckTypeNot
)

Condition check kind constants.

Variables

This section is empty.

Functions

func ExtractTypeCheckPattern 

func ExtractTypeCheckPattern(info *CallInfo)

ExtractTypeCheckPattern detects Type:is(x) or TypeName(x) patterns.

func SortedFieldNames 

func SortedFieldNames[T any](m map[string]T) []string

SortedFieldNames returns the field names from m in ascending order.

func SortedSymbolIDs 

func SortedSymbolIDs[T any](m map[basecfg.SymbolID]T) []basecfg.SymbolID

SortedSymbolIDs returns the SymbolIDs from m in ascending order.

Types

type AssignInfo 

type AssignInfo struct {
	IsLocal bool     // local x = ... vs x = ...
	Stmt    ast.Stmt // original AST statement (for position info)

	Targets []AssignTarget

	Sources       []ast.Expr
	SourceNames   []string           // Pre-extracted: identifier name or "" if not ident
	SourceSymbols []basecfg.SymbolID // Symbol IDs for source expressions (0 if not ident or unresolved)

	// Pre-extracted CallInfo for each source that is a function call (nil otherwise)
	SourceCalls []*CallInfo

	// Type annotations (for local assignments)
	TypeAnnotations []ast.TypeExpr

	// For generic for: iterator expressions
	IterExprs []ast.Expr

	// For numeric for
	NumericFor *NumericForInfo

	// SSA versions assigned by this node (one per target, may be zero if not yet computed)
	TargetVersions []Version
	// contains filtered or unexported fields
}

AssignInfo captures pre-extracted data for assignment nodes.

func (*AssignInfo) CallForTarget added in v1.5.6 

func (info *AssignInfo) CallForTarget(i int) (*CallInfo, int)

CallForTarget resolves the source call producing target index i.

Lua assignment rule: when there are more targets than sources, the final source expression may expand to multiple values. If that final source is a call expression, it supplies trailing target values.

func (*AssignInfo) EachSource added in v1.5.6 

func (info *AssignInfo) EachSource(fn func(i int, src ast.Expr))

EachSource visits non-nil source expressions in source index order.

func (*AssignInfo) EachSourceCall added in v1.5.6 

func (info *AssignInfo) EachSourceCall(fn func(i int, call *CallInfo))

EachSourceCall visits non-nil source call infos in source index order.

func (*AssignInfo) EachTarget added in v1.5.6 

func (info *AssignInfo) EachTarget(fn func(i int, target AssignTarget))

EachTarget visits targets in target index order.

func (*AssignInfo) EachTargetSource added in v1.5.6 

func (info *AssignInfo) EachTargetSource(fn func(i int, target AssignTarget, src ast.Expr))

EachTargetSource visits targets in target index order with their aligned source expression. Source may be nil when no source exists at that index.

This preserves raw positional alignment only; it does not apply Lua multi-return expansion semantics for trailing targets.

func (*AssignInfo) ExpandingSourceCall added in v1.5.6 

func (info *AssignInfo) ExpandingSourceCall() (*CallInfo, int)

ExpandingSourceCall returns the trailing source call that expands across multiple targets, along with the first target index fed by that call.

Lua assignment semantics only allow multi-return expansion from the last source expression. This helper encodes that rule and requires at least two targets to be populated by the expanding call.

func (*AssignInfo) FirstTarget added in v1.5.6 

func (info *AssignInfo) FirstTarget() (AssignTarget, bool)

FirstTarget returns the first assignment target when present.

func (*AssignInfo) HasSiblingCallExpansion added in v1.5.6 

func (info *AssignInfo) HasSiblingCallExpansion() bool

HasSiblingCallExpansion reports whether assignment can produce sibling correlations from a single call expression expanded across multiple targets.

func (*AssignInfo) Kind 

func (*AssignInfo) Kind() basecfg.NodeKind

Kind returns the node kind for AssignInfo.

func (*AssignInfo) LastSource added in v1.5.6 

func (info *AssignInfo) LastSource() ast.Expr

LastSource returns the last source expression, or nil when no sources exist.

func (*AssignInfo) SingleSourceCall added in v1.5.6 

func (info *AssignInfo) SingleSourceCall() *CallInfo

SingleSourceCall returns the call info when this assignment has exactly one call expression source (directly at source index 0). Returns nil otherwise.

func (*AssignInfo) SourceAt added in v1.5.6 

func (info *AssignInfo) SourceAt(i int) ast.Expr

SourceAt returns the source expression aligned with source index i.

func (*AssignInfo) SourceCallAt added in v1.5.6 

func (info *AssignInfo) SourceCallAt(i int) *CallInfo

SourceCallAt returns the source call info aligned with source index i.

func (*AssignInfo) TargetAt added in v1.5.6 

func (info *AssignInfo) TargetAt(i int) (AssignTarget, bool)

TargetAt returns the assignment target aligned with target index i.

func (*AssignInfo) TypeAnnotationAt added in v1.5.6 

func (info *AssignInfo) TypeAnnotationAt(i int) ast.TypeExpr

TypeAnnotationAt returns the type annotation aligned with target index i.

type AssignTarget 

type AssignTarget struct {
	Kind TargetKind

	// For TargetIdent: the variable name and symbol
	Name   string           // Variable name
	Symbol basecfg.SymbolID // Unique symbol ID (0 if unresolved)

	// For TargetField: base object and field chain
	// For TargetIndex: base object if it is an identifier
	BaseName   string           // "x" in x.y or x[k]
	BaseSymbol basecfg.SymbolID // Symbol ID for base variable
	FieldPath  []string         // ["y", "z"] in x.y.z

	// For TargetIndex: the base expression and key
	Base ast.Expr // x in x[k]
	Key  ast.Expr // k in x[k]

	// Raw LHS expression for complex cases
	Expr ast.Expr
}

AssignTarget represents a single assignment target with pre-extracted info.

func ExtractAssignTarget 

func ExtractAssignTarget(expr ast.Expr) AssignTarget

ExtractAssignTarget extracts assignment target info from an expression.

type BranchInfo 

type BranchInfo struct {
	CondVar    string    // Variable being tested (path string)
	CondSymbol SymbolID  // Symbol ID of condition variable root (0 if unresolved)
	CondCheck  CondCheck // Condition check type
	Condition  ast.Expr  // Full condition expression
}

BranchInfo captures pre-extracted data for branch nodes.

func (*BranchInfo) Kind 

func (*BranchInfo) Kind() basecfg.NodeKind

Kind returns the node kind for BranchInfo.

type Builder 

type Builder struct {
	Cfg         *basecfg.CFG
	Info        map[basecfg.Point]NodeInfo
	Nested      []NestedFunc
	Current     basecfg.Point
	CurrentLive bool
	Labels      map[string]basecfg.Point
	Pending     map[string][]basecfg.Point
	LoopExits   []basecfg.Point

	// SSA versioning state (keyed by basecfg.SymbolID for scope-aware versioning)
	NextVersionID         map[basecfg.SymbolID]int                       // symbol -> next version ID
	VisibleVersion        map[basecfg.Point]map[basecfg.SymbolID]Version // (point, symbol) -> visible version (legacy sparse)
	VisibleVersionByPoint []map[basecfg.SymbolID]Version                 // dense point-indexed view
	PhiNodes              []PhiInfo                                      // Collected phi nodes

	// Scope tracking (structural visibility)
	ScopeTracker *ScopeTracker

	// Binding table (AST ident -> symbol, populated by binder pass)
	Bindings *bind.BindingTable

	// Function parameters (collected during ParamDefs)
	ParamNames      []string
	ParamSymbols    []basecfg.SymbolID
	ParamDeclPoints []basecfg.Point
}

Builder constructs CFG Graphs from AST nodes through incremental traversal.

Builder maintains the state needed to transform an AST function body into a control flow graph. It tracks the current program point, pending gotos, loop exits, and scope visibility during traversal.

The build process involves:

  1. Traversing statements to create CFG nodes
  2. Connecting nodes with edges (including conditional edges)
  3. Tracking scope entry/exit for lexical scoping
  4. Computing SSA versions via dominance frontiers
  5. Collecting nested function definitions

Usage is internal to the package. External code should use Build or BuildWithBindings to construct graphs.

func NewBuilder 

func NewBuilder() *Builder

NewBuilder creates a new Builder with initialized fields.

func NewBuilderWithCapacity added in v1.5.11 

func NewBuilderWithCapacity(nodeCap, edgeCap int) *Builder

NewBuilderWithCapacity creates a new Builder with initial CFG size hints.

func (*Builder) AddCondBranch 

func (b *Builder) AddCondBranch(expr ast.Expr) basecfg.Point

AddCondBranch creates a branch node for a condition.

func (*Builder) AddConditionEdges 

func (b *Builder) AddConditionEdges(expr ast.Expr, thenTarget, elseTarget basecfg.Point) basecfg.Point

AddConditionEdges creates branch nodes for a condition expression.

func (*Builder) AddLinearEdge 

func (b *Builder) AddLinearEdge(next basecfg.Point)

AddLinearEdge adds an edge from the current point to next, then updates current.

func (*Builder) AddNodeWithSnapshot 

func (b *Builder) AddNodeWithSnapshot(kind basecfg.NodeKind, target basecfg.SymbolID, callee string) basecfg.Point

AddNodeWithSnapshot creates a CFG node and immediately takes a visibility snapshot.

func (*Builder) Assign 

func (b *Builder) Assign(s *ast.AssignStmt)

Assign processes a regular assignment statement.

func (*Builder) BreakStmt 

func (b *Builder) BreakStmt(_ *ast.BreakStmt)

BreakStmt processes a break statement.

func (*Builder) CallStmt 

func (b *Builder) CallStmt(s *ast.FuncCallStmt)

CallStmt processes a function call statement.

func (*Builder) ComputeSSAVersions 

func (b *Builder) ComputeSSAVersions()

ComputeSSAVersions computes SSA versions for all variables and inserts phi nodes. Uses Cytron et al. dominance-frontier phi placement + dominator-tree rename.

func (*Builder) FuncDef 

func (b *Builder) FuncDef(s *ast.FuncDefStmt)

FuncDef processes a function definition statement.

func (*Builder) GenericFor 

func (b *Builder) GenericFor(s *ast.GenericForStmt)

GenericFor processes a generic for statement.

func (*Builder) GotoStmt 

func (b *Builder) GotoStmt(s *ast.GotoStmt)

GotoStmt processes a goto statement.

func (*Builder) IfStmt 

func (b *Builder) IfStmt(s *ast.IfStmt)

IfStmt processes an if statement.

func (*Builder) LabelStmt 

func (b *Builder) LabelStmt(s *ast.LabelStmt)

LabelStmt processes a label statement.

func (*Builder) LocalAssign 

func (b *Builder) LocalAssign(s *ast.LocalAssignStmt)

LocalAssign processes a local assignment statement.

func (*Builder) NumberFor 

func (b *Builder) NumberFor(s *ast.NumberForStmt)

NumberFor processes a numeric for statement.

func (*Builder) ParamDefs 

func (b *Builder) ParamDefs(fn *ast.FunctionExpr)

ParamDefs processes function parameters.

func (*Builder) ProcessExprs 

func (b *Builder) ProcessExprs(p basecfg.Point, exprs []ast.Expr) []string

ProcessExprs extracts identifier names and collects nested functions in one pass.

func (*Builder) RepeatStmt 

func (b *Builder) RepeatStmt(s *ast.RepeatStmt)

RepeatStmt processes a repeat statement.

func (*Builder) ResolvePendingGotos 

func (b *Builder) ResolvePendingGotos()

ResolvePendingGotos resolves forward goto references.

func (*Builder) ReturnStmt 

func (b *Builder) ReturnStmt(s *ast.ReturnStmt)

ReturnStmt processes a return statement.

func (*Builder) ScopedBlock 

func (b *Builder) ScopedBlock(stmts []ast.Stmt)

ScopedBlock processes a do block.

func (*Builder) StealDeclPoints 

func (b *Builder) StealDeclPoints() map[basecfg.SymbolID]basecfg.Point

StealDeclPoints transfers ownership of the declaration points map. The Builder must not be used after this call.

func (*Builder) StealGlobals 

func (b *Builder) StealGlobals() map[string]basecfg.SymbolID

StealGlobals transfers ownership of the globals map from the ScopeTracker.

func (*Builder) StealScopeVisibility 

func (b *Builder) StealScopeVisibility() map[basecfg.Point]map[string]basecfg.SymbolID

StealScopeVisibility transfers ownership of the visibility map from the ScopeTracker to the caller. The Builder must not be used after this call.

func (*Builder) StealSymbolKinds 

func (b *Builder) StealSymbolKinds() map[basecfg.SymbolID]basecfg.SymbolKind

StealSymbolKinds transfers ownership of the symbol kinds map. The Builder must not be used after this call.

func (*Builder) StealSymbolNames 

func (b *Builder) StealSymbolNames() map[basecfg.SymbolID]string

StealSymbolNames transfers ownership of the symbol names map. The Builder must not be used after this call.

func (*Builder) Stmt 

func (b *Builder) Stmt(stmt ast.Stmt)

Stmt processes a single statement.

func (*Builder) Stmts 

func (b *Builder) Stmts(stmts []ast.Stmt)

Stmts processes a list of statements.

func (*Builder) TypeDef 

func (b *Builder) TypeDef(s *ast.TypeDefStmt)

TypeDef processes a type definition statement.

func (*Builder) WhileStmt 

func (b *Builder) WhileStmt(s *ast.WhileStmt)

WhileStmt processes a while statement.

type CFG 

type CFG = basecfg.CFG

CFG is an alias for basecfg.CFG.

type CallInfo 

type CallInfo struct {
	Call     *ast.FuncCallExpr // Full call expression (for span lookup)
	Callee   ast.Expr          // Function expression (for non-method calls)
	Args     []ast.Expr        // Call arguments
	Method   string            // "foo" if x:foo()
	Receiver ast.Expr          // x if x:foo()
	IsStmt   bool              // Statement vs expression

	// Pre-extracted for quick checks
	CalleeName     string             // "error", "assert", "setmetatable" etc
	CalleeSymbol   basecfg.SymbolID   // Symbol ID for callee (0 if unresolved or not ident)
	ArgNames       []string           // Pre-extracted: identifier name or "" if not ident
	ArgSymbols     []basecfg.SymbolID // Symbol IDs for arguments (0 if not ident or unresolved)
	ReceiverName   string             // Pre-extracted: identifier name or "" if not ident
	ReceiverSymbol basecfg.SymbolID   // Symbol ID for receiver (0 if unresolved)

	// Pre-extracted predicate pattern info (for Type:is(x) or TypeName(x))
	IsTypeCheck   bool            // True if this is Type:is(arg) or TypeName(arg) pattern
	TypeCheckName string          // Type name for type check (receiver name for :is, callee name otherwise)
	TypeCheckPath constraint.Path // Binding-based path for type check argument (identity + display)

	// Unified callee path for identity resolution.
	// For f() -> {Root: "f", Symbol: sym}
	// For obj.f() -> {Root: "obj", Symbol: objSym, Segments: [{Field, "f"}]}
	// For obj:f() -> receiver path only: {Root: "obj", Symbol: objSym}
	//   Method name is in CallInfo.Method field, not in CalleePath
	// For a.b.c() -> {Root: "a", Symbol: aSym, Segments: [{Field, "b"}, {Field, "c"}]}
	// For a.b:c() -> receiver path: {Root: "a", Symbol: aSym, Segments: [{Field, "b"}]}
	// Empty if callee cannot be statically resolved to a path.
	CalleePath constraint.Path
}

CallInfo captures pre-extracted data for call nodes.

func BuildCallInfo 

func BuildCallInfo(call *ast.FuncCallExpr, isStmt bool) *CallInfo

BuildCallInfo creates a CallInfo from a FuncCallExpr, extracting all needed info.

func ExtractSourceCalls 

func ExtractSourceCalls(exprs []ast.Expr) []*CallInfo

ExtractSourceCalls pre-extracts CallInfo for each source expression that is a call.

func (*CallInfo) Kind 

func (*CallInfo) Kind() basecfg.NodeKind

Kind returns the node kind for CallInfo.

type CondCheck 

type CondCheck = basecfg.CondCheck

CondCheck is an alias for basecfg.CondCheck.

type CondCheckKind 

type CondCheckKind = basecfg.CondCheckKind

CondCheckKind is an alias for basecfg.CondCheckKind.

type FuncDefInfo 

type FuncDefInfo struct {
	TargetKind     FuncDefTargetKind
	Name           string           // Function name
	Symbol         basecfg.SymbolID // Symbol ID for function (0 if unresolved)
	Receiver       ast.Expr         // T in T:bar() or T.baz()
	ReceiverName   string           // Receiver identifier name if available
	ReceiverSymbol basecfg.SymbolID // Symbol ID for receiver (0 if unresolved)
	IsMethod       bool             // Uses : syntax
	FuncExpr       *ast.FunctionExpr

	// Unified target path for where the function is stored.
	// For function foo() -> {Root: "foo", Symbol: sym}
	// For local function foo() -> {Root: "foo", Symbol: sym}
	// For function M.foo() -> {Root: "M", Symbol: MSym, Segments: [{Field, "foo"}]}
	// For function M:foo() -> same as M.foo (method semantics separate via IsMethod)
	TargetPath constraint.Path
}

FuncDefInfo captures pre-extracted data for function definition nodes.

func (*FuncDefInfo) Kind 

func (*FuncDefInfo) Kind() basecfg.NodeKind

Kind returns the node kind for FuncDefInfo.

type FuncDefTargetKind 

type FuncDefTargetKind uint8

FuncDefTargetKind identifies how the function is being assigned. 

const (
	FuncDefGlobal FuncDefTargetKind = iota // function foo()
	FuncDefField                           // function T.foo()
	FuncDefMethod                          // function T:foo()
)

Function definition target kind constants.

type Graph 

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

Graph holds CFG with pre-extracted node info. Immutable after Build().

func Build 

func Build(fn *ast.FunctionExpr, globals ...string) *Graph

Build creates an immutable Graph for a function body. If globals is provided, those names are seeded into the binder's root scope with stable SymbolIDs before traversal, enabling global symbol resolution.

func BuildBlock 

func BuildBlock(stmts []ast.Stmt, globals ...string) *Graph

BuildBlock creates an immutable Graph for a block of statements. If globals is provided, those names are seeded into the binder's root scope with stable SymbolIDs before traversal, enabling global symbol resolution.

func BuildWithBindings 

func BuildWithBindings(fn *ast.FunctionExpr, bindings *bind.BindingTable) *Graph

BuildWithBindings creates an immutable Graph using a pre-computed binding table. This allows sharing SymbolIDs across multiple function graphs within a module.

func (*Graph) AllSymbolIDs 

func (g *Graph) AllSymbolIDs() map[basecfg.SymbolID]bool

AllSymbolIDs returns a set of all symbols known to this graph. Useful when only symbol identity is needed (avoids AllSymbolsAt merges).

func (*Graph) AllSymbolsAt 

func (g *Graph) AllSymbolsAt(p Point) map[string]basecfg.SymbolID

AllSymbolsAt returns all visible symbols at a CFG point.

func (*Graph) AllVisibleVersions 

func (g *Graph) AllVisibleVersions(p Point) map[basecfg.SymbolID]Version

AllVisibleVersions returns all symbol versions visible at a point. The returned map should not be modified. Implements cfg.SSAVersioned.

func (*Graph) Assign 

func (g *Graph) Assign(p Point) *AssignInfo

Assign returns AssignInfo at p, or nil if not an assign node.

func (*Graph) AssignPoints 

func (g *Graph) AssignPoints() []Point

AssignPoints returns all assignment points.

func (*Graph) Bindings 

func (g *Graph) Bindings() *bind.BindingTable

Bindings returns the binding table populated during binder pass.

func (*Graph) Branch 

func (g *Graph) Branch(p Point) *BranchInfo

Branch returns BranchInfo at p, or nil if not a branch node.

func (*Graph) CFG 

func (g *Graph) CFG() *basecfg.CFG

CFG returns the underlying control flow graph.

func (*Graph) Call 

func (g *Graph) Call(p Point) *CallInfo

Call returns CallInfo at p, or nil if not a call node.

func (*Graph) CallSiteAt added in v1.5.6 

func (g *Graph) CallSiteAt(p Point, ex *ast.FuncCallExpr) *CallInfo

CallSiteAt returns the callsite at point p matching expression ex. Returns nil when no matching callsite exists at that point.

func (*Graph) CallSitesAt added in v1.5.6 

func (g *Graph) CallSitesAt(p Point) []*CallInfo

CallSitesAt returns all callsites represented at point p.

A single point may represent:

  • a direct call node
  • an assignment node with source call expressions
  • a return node with source call expressions

func (*Graph) CalleePathAt 

func (g *Graph) CalleePathAt(p Point) constraint.Path

CalleePathAt returns the callee path for a call at point p. Returns empty path if p is not a call node.

func (*Graph) DeclarationPoint 

func (g *Graph) DeclarationPoint(sym basecfg.SymbolID) (Point, bool)

DeclarationPoint returns the CFG point where a symbol was declared. Returns (0, false) if the symbol is unknown. Implements cfg.SSAVersioned.

func (*Graph) DirectAliasSymbol 

func (g *Graph) DirectAliasSymbol(targetSym basecfg.SymbolID) basecfg.SymbolID

DirectAliasSymbol returns the source symbol for a direct local alias assignment. Handles patterns like `local f = B` in the current graph. Returns 0 if the alias is ambiguous or not a direct ident assignment.

func (*Graph) EachAliasSymbol added in v1.5.6 

func (g *Graph) EachAliasSymbol(targetSym basecfg.SymbolID, fn func(basecfg.SymbolID) bool)

EachAliasSymbol visits targetSym followed by its direct-alias chain. Iteration stops on zero, self-loop, cycle, or when fn returns true.

func (*Graph) EachAssign 

func (g *Graph) EachAssign(fn func(Point, *AssignInfo))

EachAssign calls fn for each assignment node in point order.

func (*Graph) EachBranch 

func (g *Graph) EachBranch(fn func(Point, *BranchInfo))

EachBranch calls fn for each branch node in point order.

func (*Graph) EachCall deprecated 

func (g *Graph) EachCall(fn func(Point, *CallInfo))

EachCall calls fn for each call statement node in point order.

Deprecated: use EachStmtCall for statement-only traversal or EachCallSite to include embedded call expressions in assignment/return nodes.

func (*Graph) EachCallSite 

func (g *Graph) EachCallSite(fn func(Point, *CallInfo))

EachCallSite calls fn for each call site in point order.

A call site includes:

  • Call statement nodes (foo())
  • Call expressions inside assignment sources (local x = foo())
  • Call expressions inside return statements (return foo())

Calls embedded in assignment/return sources are yielded in source order.

func (*Graph) EachFuncDef 

func (g *Graph) EachFuncDef(fn func(Point, *FuncDefInfo))

EachFuncDef calls fn for each function definition node in point order.

func (*Graph) EachNode 

func (g *Graph) EachNode(fn func(Point, NodeInfo))

EachNode calls fn for each node with info in point order.

func (*Graph) EachReturn 

func (g *Graph) EachReturn(fn func(Point, *ReturnInfo))

EachReturn calls fn for each return node in point order.

func (*Graph) EachStmtCall added in v1.5.6 

func (g *Graph) EachStmtCall(fn func(Point, *CallInfo))

EachStmtCall calls fn for each call statement node in point order.

This does not include call expressions embedded in assignment or return nodes.

func (*Graph) EachTypeDef 

func (g *Graph) EachTypeDef(fn func(Point, *TypeDefInfo))

EachTypeDef calls fn for each type definition node in point order.

func (*Graph) EdgeCond 

func (g *Graph) EdgeCond(from, to Point) (bool, bool)

EdgeCond returns the condition value for edge from->to.

func (*Graph) Edges 

func (g *Graph) Edges() []basecfg.Edge

Edges returns all edges.

func (*Graph) Entry 

func (g *Graph) Entry() Point

Entry returns the entry point.

func (*Graph) Exit 

func (g *Graph) Exit() Point

Exit returns the exit point.

func (*Graph) Func 

func (g *Graph) Func() *ast.FunctionExpr

Func returns the root function expression for this graph, if any.

func (*Graph) FuncDef 

func (g *Graph) FuncDef(p Point) *FuncDefInfo

FuncDef returns FuncDefInfo at p, or nil if not a funcdef node.

func (*Graph) FuncDefPathAt 

func (g *Graph) FuncDefPathAt(p Point) constraint.Path

FuncDefPathAt returns the target path for a function definition at point p. Returns empty path if p is not a function definition node.

func (*Graph) GlobalSymbol 

func (g *Graph) GlobalSymbol(name string) (basecfg.SymbolID, bool)

GlobalSymbol returns the symbol ID for a global name. Returns (0, false) if the name is not a known global.

func (*Graph) HasPhiAt 

func (g *Graph) HasPhiAt(_ Point, sym basecfg.SymbolID) bool

HasPhiAt returns true if there's a phi node at point p for the given symbol.

func (*Graph) HasScopeTracking 

func (g *Graph) HasScopeTracking() bool

HasScopeTracking returns true if scope visibility was computed during build.

func (*Graph) ID 

func (g *Graph) ID() uint64

ID returns the unique identifier.

func (*Graph) Info 

func (g *Graph) Info(p Point) NodeInfo

Info returns the node info at point p, or nil if none.

func (*Graph) IsBranch 

func (g *Graph) IsBranch(p Point) bool

IsBranch returns true if p has multiple successors.

func (*Graph) IsJoin 

func (g *Graph) IsJoin(p Point) bool

IsJoin returns true if p has multiple predecessors.

func (*Graph) LocalSymbolsAt added in v1.5.10 

func (g *Graph) LocalSymbolsAt(p Point) map[string]basecfg.SymbolID

LocalSymbolsAt returns the point-local symbol visibility map. The returned map should not be modified.

func (*Graph) NameOf 

func (g *Graph) NameOf(sym basecfg.SymbolID) string

NameOf returns the variable name for a symbol (for display purposes). Returns empty string if the symbol is unknown.

func (*Graph) NestedFunctions 

func (g *Graph) NestedFunctions() []NestedFunc

NestedFunctions returns all nested functions found during build.

func (*Graph) Node 

func (g *Graph) Node(p Point) *basecfg.Node

Node returns the base CFG node at point p.

func (*Graph) ParamDeclPoints 

func (g *Graph) ParamDeclPoints() []Point

ParamDeclPoints returns a copy of the CFG points where parameters are declared. Returns nil for block graphs or functions with no parameters.

func (*Graph) ParamNames 

func (g *Graph) ParamNames() []string

ParamNames returns a copy of the function parameter names. Returns nil for block graphs or functions with no parameters.

func (*Graph) ParamSlots added in v1.5.6 

func (g *Graph) ParamSlots() []ParamSlot

ParamSlots returns the canonical parameter layout for this graph.

All downstream phases should consume this API rather than re-deriving ParList-to-symbol mapping, which can drift for implicit method receivers.

func (*Graph) ParamSlotsReadOnly added in v1.5.11 

func (g *Graph) ParamSlotsReadOnly() []ParamSlot

ParamSlotsReadOnly returns the canonical parameter layout for this graph. The returned slice must be treated as immutable by callers.

func (*Graph) ParamSymbols 

func (g *Graph) ParamSymbols() []basecfg.SymbolID

ParamSymbols returns a copy of the function parameter symbol IDs. Returns nil for block graphs or functions with no parameters.

func (*Graph) PhiNodes 

func (g *Graph) PhiNodes() []basecfg.PhiNode

PhiNodes returns all phi nodes in the graph. Implements cfg.SymbolScope.

func (*Graph) PopulateSymbols 

func (g *Graph) PopulateSymbols(resolve SymbolResolver)

PopulateSymbols fills in basecfg.SymbolID fields for all node infos using the resolver.

func (*Graph) Predecessor 

func (g *Graph) Predecessor(p Point) Point

Predecessor returns single predecessor (for non-join nodes).

func (*Graph) Predecessors 

func (g *Graph) Predecessors(p Point) []Point

Predecessors returns all predecessors of p.

func (*Graph) PredecessorsReadOnly added in v1.5.11 

func (g *Graph) PredecessorsReadOnly(p Point) []Point

PredecessorsReadOnly returns predecessors without copying.

The returned slice must be treated as read-only by callers.

func (*Graph) RPO 

func (g *Graph) RPO() []Point

RPO returns nodes in reverse post-order.

func (*Graph) Return 

func (g *Graph) Return(p Point) *ReturnInfo

Return returns ReturnInfo at p, or nil if not a return node.

func (*Graph) Size 

func (g *Graph) Size() int

Size returns the number of nodes.

func (*Graph) Successor 

func (g *Graph) Successor(p Point) Point

Successor returns single successor (for non-branch nodes).

func (*Graph) Successors 

func (g *Graph) Successors(p Point) []Point

Successors returns all successors of p.

func (*Graph) SuccessorsReadOnly added in v1.5.11 

func (g *Graph) SuccessorsReadOnly(p Point) []Point

SuccessorsReadOnly returns successors without copying.

The returned slice must be treated as read-only by callers.

func (*Graph) SymbolAt 

func (g *Graph) SymbolAt(p Point, name string) (basecfg.SymbolID, bool)

SymbolAt returns the basecfg.SymbolID for a variable name at a specific CFG point. This reflects lexical scoping - the same name may resolve to different symbols at different points due to shadowing. Returns (0, false) if the name is not visible at that point. Implements cfg.SSAVersioned.

func (*Graph) SymbolKind 

func (g *Graph) SymbolKind(sym basecfg.SymbolID) (basecfg.SymbolKind, bool)

SymbolKind returns the kind of a symbol (Param, Local, or Global). Returns (SymbolUnknown, false) if the symbol is not known.

func (*Graph) TypeDef 

func (g *Graph) TypeDef(p Point) *TypeDefInfo

TypeDef returns TypeDefInfo at p, or nil if not a typedef node.

func (*Graph) VisibleVersion 

func (g *Graph) VisibleVersion(p Point, sym basecfg.SymbolID) Version

VisibleVersion returns the SSA version of a symbol visible at a point. Returns a zero Version if the symbol is not defined on all paths to this point. Implements cfg.SymbolScope.

type NestedFunc 

type NestedFunc struct {
	Point  Point
	Func   *ast.FunctionExpr
	Symbol basecfg.SymbolID // Symbol for the function literal (0 if not yet assigned)
}

NestedFunc records a nested function found during CFG build.

type Node 

type Node = basecfg.Node

Node is an alias for basecfg.Node.

type NodeInfo 

type NodeInfo interface {
	Kind() basecfg.NodeKind
	// contains filtered or unexported methods
}

NodeInfo is the interface implemented by all node info types.

type NodeKind 

type NodeKind = basecfg.NodeKind

NodeKind is an alias for basecfg.NodeKind.

type NumericForInfo 

type NumericForInfo struct {
	VarName string
	Init    ast.Expr
	Limit   ast.Expr
	Step    ast.Expr
}

NumericForInfo captures numeric for loop details.

type ParamSlot added in v1.5.6 

type ParamSlot struct {
	Name           string
	Symbol         SymbolID
	DeclPoint      Point
	TypeAnnotation ast.TypeExpr
	SourceIndex    int
	IsImplicitSelf bool
}

ParamSlot is the canonical parameter layout entry for a function graph.

SourceIndex maps this slot back to fn.ParList. A value of -1 means this is an implicit parameter introduced by binder/CFG (for example implicit method receiver `self` on `function T:m(...)`).

func (ParamSlot) HasSourceParam added in v1.5.6 

func (s ParamSlot) HasSourceParam() bool

HasSourceParam reports whether this slot maps to a source parameter in fn.ParList.

func (ParamSlot) SourceParamIndex added in v1.5.6 

func (s ParamSlot) SourceParamIndex() (int, bool)

SourceParamIndex returns the source parameter index when present.

type PhiInfo 

type PhiInfo = basecfg.PhiNode

PhiInfo is an alias for basecfg.PhiNode.

type PhiOperand 

type PhiOperand = basecfg.PhiOperand

PhiOperand is an alias for basecfg.PhiOperand.

type Point 

type Point = basecfg.Point

Point is an alias for basecfg.Point.

type ReturnInfo 

type ReturnInfo struct {
	Stmt        *ast.ReturnStmt
	Exprs       []ast.Expr
	Names       []string           // Pre-extracted: identifier name or "" if not ident
	Symbols     []basecfg.SymbolID // Symbol IDs for returned identifiers (0 if not ident or unresolved)
	SourceCalls []*CallInfo        // Call info for returned call expressions (parallel to Exprs; nil if not a call)
}

ReturnInfo captures pre-extracted data for return nodes.

func (*ReturnInfo) EachSourceCall added in v1.5.6 

func (info *ReturnInfo) EachSourceCall(fn func(i int, call *CallInfo))

EachSourceCall visits non-nil return-expression call infos in expression order.

func (*ReturnInfo) Kind 

func (*ReturnInfo) Kind() basecfg.NodeKind

Kind returns the node kind for ReturnInfo.

func (*ReturnInfo) SourceCallAt added in v1.5.6 

func (info *ReturnInfo) SourceCallAt(i int) *CallInfo

SourceCallAt returns the return-expression call info aligned with expression index i.

type ScopeTracker 

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

ScopeTracker tracks symbol visibility during CFG construction. It does NOT create symbols - it only registers symbols created by the binder. Uses copy-on-write: maps are shared until modification.

func NewScopeTracker 

func NewScopeTracker() *ScopeTracker

NewScopeTracker creates a new scope tracker.

func NewScopeTrackerWithCapacity added in v1.5.11 

func NewScopeTrackerWithCapacity(pointCap int) *ScopeTracker

NewScopeTrackerWithCapacity creates a new scope tracker with visibility capacity hint.

func (*ScopeTracker) CurrentDepth 

func (t *ScopeTracker) CurrentDepth() int

CurrentDepth returns the current scope nesting depth.

func (*ScopeTracker) DeclarationPoint 

func (t *ScopeTracker) DeclarationPoint(sym basecfg.SymbolID) (basecfg.Point, bool)

DeclarationPoint returns the CFG point where a symbol was declared.

func (*ScopeTracker) EnterScope 

func (t *ScopeTracker) EnterScope()

EnterScope pushes a new scope frame onto the stack. Uses copy-on-write: shares parent's map until modification.

func (*ScopeTracker) ExitScope 

func (t *ScopeTracker) ExitScope()

ExitScope pops the current scope frame from the stack.

func (*ScopeTracker) Lookup 

func (t *ScopeTracker) Lookup(name string) (basecfg.SymbolID, bool)

Lookup returns the symbol for a name in the current scope.

func (*ScopeTracker) RegisterGlobal 

func (t *ScopeTracker) RegisterGlobal(sym basecfg.SymbolID, name string, declPoint basecfg.Point)

RegisterGlobal registers a symbol as a global. Uses lazy overlay - globals are stored separately and merged on lookup.

func (*ScopeTracker) RegisterSymbol 

func (t *ScopeTracker) RegisterSymbol(
	sym basecfg.SymbolID, name string, kind basecfg.SymbolKind, declPoint basecfg.Point,
)

RegisterSymbol registers an externally-created symbol in the current scope.

func (*ScopeTracker) SnapshotVisibility 

func (t *ScopeTracker) SnapshotVisibility(point basecfg.Point)

SnapshotVisibility records the current visibility state at a CFG point. Uses copy-on-write: the next modification will copy the map.

func (*ScopeTracker) SymbolAt 

func (t *ScopeTracker) SymbolAt(point basecfg.Point, name string) (basecfg.SymbolID, bool)

SymbolAt returns the symbol for a name at a specific CFG point.

func (*ScopeTracker) SymbolKind 

func (t *ScopeTracker) SymbolKind(sym basecfg.SymbolID) (basecfg.SymbolKind, bool)

SymbolKind returns the kind of a symbol.

func (*ScopeTracker) VisibleAt 

func (t *ScopeTracker) VisibleAt(point basecfg.Point) *SymbolMap

VisibleAt returns the visibility snapshot at a CFG point.

type SymbolID 

type SymbolID = basecfg.SymbolID

SymbolID is an alias for basecfg.SymbolID.

type SymbolKind 

type SymbolKind = basecfg.SymbolKind

SymbolKind is an alias for basecfg.SymbolKind.

type SymbolMap 

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

SymbolMap wraps a map for compatibility with existing code.

func (*SymbolMap) Get 

func (s *SymbolMap) Get(name string) (basecfg.SymbolID, bool)

Get returns the symbol for a name.

func (*SymbolMap) Range 

func (s *SymbolMap) Range(fn func(name string, sym basecfg.SymbolID) bool)

Range iterates over all symbols.

func (*SymbolMap) Size 

func (s *SymbolMap) Size() int

Size returns the number of symbols in the map.

func (*SymbolMap) ToMap 

func (s *SymbolMap) ToMap() map[string]basecfg.SymbolID

ToMap returns the underlying map (without globals for pointer identity).

type SymbolResolver 

type SymbolResolver func(p Point, name string) basecfg.SymbolID

SymbolResolver resolves variable names to SymbolIDs at CFG points.

type TargetKind 

type TargetKind uint8

TargetKind identifies the kind of assignment target. 

const (
	TargetIdent TargetKind = iota // Simple identifier: x
	TargetField                   // Field access: x.y
	TargetIndex                   // Index access: x[k]
)

Target kind constants.

type TypeDefInfo 

type TypeDefInfo struct {
	Name       string
	TypeParams []TypeParamInfo
	TypeExpr   ast.TypeExpr
}

TypeDefInfo captures pre-extracted data for type definition nodes.

func (*TypeDefInfo) Kind 

func (*TypeDefInfo) Kind() basecfg.NodeKind

Kind returns the node kind for TypeDefInfo.

type TypeParamInfo 

type TypeParamInfo struct {
	Name       string
	Constraint ast.TypeExpr
}

TypeParamInfo captures a type parameter definition.

type Version 

type Version = basecfg.Version

Version is an alias for basecfg.Version.

Source Files

View all Source files

Directories

Path Synopsis
Package analysis provides pure graph analysis algorithms for CFGs.
 Package analysis provides pure graph analysis algorithms for CFGs.
Package extraction provides pure AST extraction functions for CFG construction.
 Package extraction provides pure AST extraction functions for CFG construction.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.