Documentation
¶
Overview ¶
Package traverse provides safe type traversal with automatic cycle detection. This prevents infinite loops when traversing cyclic type graphs (e.g., recursive ADTs).
API Design Rule (from M-PERF2 post-mortem): Every function of shape `func(Type) T` MUST document cycle-safety. Either use traverse.Visit or add a `visited` parameter.
Index ¶
- Constants
- func AllTypes(t types.Type) []types.Type
- func CollectFreeVars(t types.Type) map[string]bool
- func CollectTypesByKind(t types.Type, predicate func(types.Type) bool) []types.Type
- func ContainsType(t, target types.Type) bool
- func ContainsTypeByName(t types.Type, name string) bool
- func CountTypes(t types.Type) int
- func Depth(t types.Type) int
- func HasCycles(t types.Type) bool
- func HasTypeVars(t types.Type) bool
- func IsMonomorphic(t types.Type) bool
- func Walk(t types.Type, fn func(types.Type))
- func WalkWithCycleCallback(t types.Type, fn func(types.Type), onCycle func(types.Type))
- type TypeVisitor
Constants ¶
const DefaultMaxDepth = 1000
DefaultMaxDepth is the maximum traversal depth before panic. This prevents hangs on pathological cases even if cycle detection fails.
Variables ¶
This section is empty.
Functions ¶
func AllTypes ¶
AllTypes returns all types in a type graph in pre-order traversal. Safe for cyclic types - cycles are visited once.
func CollectFreeVars ¶
CollectFreeVars returns all free type variable names in a type. Safe for cyclic types - will not hang on self-referential type graphs.
Example:
vars := traverse.CollectFreeVars(funcType)
// vars might be: {"a": true, "b": true}
func CollectTypesByKind ¶
CollectTypesByKind returns all types of a specific kind in a type graph. The predicate function determines which types to collect. Safe for cyclic types.
Example:
funcs := traverse.CollectTypesByKind(t, func(typ types.Type) bool {
_, ok := typ.(*types.TFunc2)
return ok
})
func ContainsType ¶
ContainsType checks if a type graph contains a specific target type. Uses pointer equality for comparison. Safe for cyclic types.
Example:
if traverse.ContainsType(funcType, targetVar) {
// targetVar appears somewhere in funcType
}
func ContainsTypeByName ¶
ContainsTypeByName checks if a type graph contains a type variable with the given name. Safe for cyclic types.
Example:
if traverse.ContainsTypeByName(funcType, "a") {
// Type variable "a" appears somewhere in funcType
}
func CountTypes ¶
CountTypes returns the total number of type nodes in a type graph. Safe for cyclic types - cycles are counted once.
Useful for complexity estimation and debugging.
func Depth ¶
Depth returns the maximum nesting depth of a type graph. Safe for cyclic types - cycles are detected and counted once.
Useful for complexity analysis and debugging.
func HasCycles ¶
HasCycles checks if a type graph contains any cycles. Returns true if the type references itself directly or indirectly.
Example:
if traverse.HasCycles(adtType) {
// This is a recursive type like List[T] or Tree[T]
}
func HasTypeVars ¶
HasTypeVars checks if a type contains any type variables (TVar, TVar2, RowVar). Safe for cyclic types - will not hang on recursive ADTs.
This is the cycle-safe replacement for isPolymorphic checks. Use this in monomorphization and specialization passes.
Example:
if traverse.HasTypeVars(funcType) {
// Type is polymorphic, needs specialization
}
func IsMonomorphic ¶
IsMonomorphic checks if a type is fully concrete (no type variables). This is the inverse of HasTypeVars. Safe for cyclic types.
Example:
if traverse.IsMonomorphic(funcType) {
// Type can be used directly without specialization
}
Types ¶
type TypeVisitor ¶
type TypeVisitor struct {
// OnCycle is called when a cycle is detected.
// If nil, cycles are silently skipped.
OnCycle func(typ types.Type)
// contains filtered or unexported fields
}
TypeVisitor traverses type graphs with automatic cycle detection. Use NewVisitor() to create instances.
func NewVisitor ¶
func NewVisitor() *TypeVisitor
NewVisitor creates a TypeVisitor with default settings.
func (*TypeVisitor) Visit ¶
func (v *TypeVisitor) Visit(t types.Type, fn func(types.Type))
Visit traverses a type graph, calling fn for each type node. Automatically detects cycles and enforces depth limits.
The visitor uses pre-order traversal: fn is called before children. Cycles are detected and skipped (or OnCycle is called if set).
func (*TypeVisitor) WithMaxDepth ¶
func (v *TypeVisitor) WithMaxDepth(depth int) *TypeVisitor
WithMaxDepth sets a custom maximum depth (for testing).
func (*TypeVisitor) WithOnCycle ¶
func (v *TypeVisitor) WithOnCycle(fn func(types.Type)) *TypeVisitor
WithOnCycle sets a callback for cycle detection.
Source Files