Documentation
¶
Overview ¶
Package internal provides pure data structures for the type system.
HAMT (Hash Array Mapped Trie):
- Get: O(log32 n) ≈ O(1) for practical sizes
- Set: O(log32 n) with path copying
- Delete: O(log32 n) with path copying
- Memory: Unchanged subtrees are shared between versions.
Index ¶
- Constants
- func ComputeSCCs(adj map[uint64][]uint64) [][]uint64
- func FnvString(s string) uint64
- func HashCombine(a, b uint64) uint64
- func MixHash(h, v uint64) uint64
- func SafeAdd(a, b int64) (int64, bool)
- func SafeMul(a, b int64) (int64, bool)
- func SafeNeg(a int64) (int64, bool)
- func SafeSub(a, b int64) (int64, bool)
- type Equaler
- type HAMT
- type Hashable
- type RecursionGuard
Constants ¶
const ( FnvOffset64 = 14695981039346656037 FnvPrime64 = 1099511628211 )
FNV-1a constants.
const ( // MaxShallowDepth for simple type checks (32). MaxShallowDepth = 32 // MaxMediumDepth for type operations (64). MaxMediumDepth = 64 // MaxDeepDepth for environment and control flow (256). MaxDeepDepth = 256 // MaxHashDepth for structural hashing. MaxHashDepth = 50 // MaxDistributionProduct caps the cartesian product size when distributing // intersection over unions to prevent exponential blowup. MaxDistributionProduct = 256 )
Depth limits for recursive type operations.
const ( MinInt64 = math.MinInt64 MaxInt64 = math.MaxInt64 )
Int64 bounds for overflow detection.
Variables ¶
This section is empty.
Functions ¶
func ComputeSCCs ¶
ComputeSCCs computes strongly connected components using Tarjan's algorithm. Returns SCCs in topological order (dependencies resolved first).
Types ¶
type Equaler ¶
Equaler is implemented by types that support typed equality comparison. Used by typ.Function to compare Effects, Spec, and Refinement fields without importing circular dependencies.
type HAMT ¶
type HAMT[K comparable, V any] struct { // contains filtered or unexported fields }
HAMT is an immutable hash array mapped trie. Zero value is an empty map.
func FromMap ¶
func FromMap[K comparable, V any](m map[K]V) *HAMT[K, V]
FromMap creates a HAMT from a Go map.
type Hashable ¶
type Hashable interface {
Hash() uint64
}
Hashable is a minimal interface for types that can be tracked by a hash. typ.Type satisfies this interface via Hash().
type RecursionGuard ¶
type RecursionGuard struct {
// contains filtered or unexported fields
}
RecursionGuard tracks recursion depth and optional cycle detection.
func NewRecursionGuard ¶
func NewRecursionGuard(maxDepth int) RecursionGuard
NewRecursionGuard creates a guard with the given max depth.
func (RecursionGuard) Depth ¶
func (g RecursionGuard) Depth() int
Depth returns the current recursion depth of the guard.
func (RecursionGuard) Enter ¶
func (g RecursionGuard) Enter(h Hashable) (RecursionGuard, bool)
Enter advances the guard for a recursive step. Returns (nextGuard, true) if recursion should continue.
func (RecursionGuard) WithSeen ¶
func (g RecursionGuard) WithSeen() RecursionGuard
WithSeen enables cycle detection using hashes.
Source Files