Documentation
¶
Overview ¶
Package db provides a Salsa-style incremental computation database for efficient re-analysis when source files change.
The db package enables incremental type checking by tracking dependencies between computations and only recomputing what changed. This is essential for responsive IDE tooling where most edits affect only a small portion of the program.
Core Concepts ¶
Revision: A monotonically increasing version number bumped whenever inputs change. Used to track staleness of cached computations.
Input: A memoized query that caches values by key with VerifiedAt tracking. When an input is accessed, its VerifiedAt is compared to the current revision to determine if recomputation is needed.
Interning: Structural deduplication ensuring that types with identical structure share the same pointer. This enables cheap equality checks and stable memoization keys.
Manifest: Cross-module type information loaded from dependencies. Manifests are connected/disconnected from the database to enable module-level caching.
Thread Safety ¶
The database is thread-safe for concurrent access. Multiple goroutines can query and update the database simultaneously without external synchronization.
Index ¶
- func Attach[T any](ctx *QueryContext, key AttachmentKey[T], val T)
- func Attached[T any](ctx *QueryContext, key AttachmentKey[T]) (T, bool)
- type AttachmentKey
- type DB
- func (db *DB) Bump() Revision
- func (db *DB) Connect(path string, manifest *io.Manifest)
- func (db *DB) Disconnect(path string)
- func (db *DB) Imports() map[string]*io.Manifest
- func (db *DB) Intern(key uint64, factory func() any, equal func(existing, candidate any) bool) any
- func (db *DB) InternType(t typ.Type) typ.Type
- func (db *DB) Manifest(path string) *io.Manifest
- func (db *DB) Manifests(fn func(path string, manifest *io.Manifest) bool)
- func (db *DB) Revision() Revision
- type Input
- type Interner
- type MemoEntry
- type Query
- func (q *Query[K, V]) Clear()
- func (q *Query[K, V]) Get(ctx *QueryContext, key K) V
- func (q *Query[K, V]) SetAlwaysWiden(enabled bool)
- func (q *Query[K, V]) SetMaxIter(limit int)
- func (q *Query[K, V]) SetOnMaxIter(fn func(iter int, last V, key K) (V, bool))
- func (q *Query[K, V]) SetOnMaxIterReturnLast()
- type QueryContext
- type Revision
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Attach ¶
func Attach[T any](ctx *QueryContext, key AttachmentKey[T], val T)
Attach stores a value in the context using a typed key.
The value is stored in the context's attachment map, keyed by the AttachmentKey's name. Calling Attach with the same key replaces any previously attached value.
func Attached ¶
func Attached[T any](ctx *QueryContext, key AttachmentKey[T]) (T, bool)
Attached retrieves a value from the context using a typed key.
Returns the attached value and true if found, or the zero value and false if not found or if the value's type doesn't match T.
Types ¶
type AttachmentKey ¶
type AttachmentKey[T any] struct { // contains filtered or unexported fields }
AttachmentKey is a type-safe key for context attachments.
Attachments allow passing additional state through the query context without modifying the QueryContext type. Each AttachmentKey[T] creates a unique slot identified by its name string.
Usage pattern:
// Define a key at package level
var MyDataKey = db.NewAttachmentKey[*MyData]("mypackage.MyData")
// Attach data to context
db.Attach(ctx, MyDataKey, myData)
// Retrieve data from context
if data, ok := db.Attached(ctx, MyDataKey); ok {
// use data
}
The generic type T ensures type safety at compile time, while the name string enables runtime lookup in the attachments map.
func NewAttachmentKey ¶
func NewAttachmentKey[T any](name string) AttachmentKey[T]
NewAttachmentKey creates a new typed attachment key. The name is used for debugging and should be unique per attachment type.
func (AttachmentKey[T]) Name ¶
func (k AttachmentKey[T]) Name() string
Name returns the key's name for debugging.
type DB ¶
type DB struct {
// contains filtered or unexported fields
}
DB is the central database for incremental computation. Thread-safe for concurrent access.
func (*DB) Bump ¶
Bump increments the revision and returns the new value. Call this when inputs change.
func (*DB) Connect ¶
Connect adds a manifest to the database. Bumps revision to invalidate dependent queries.
func (*DB) Disconnect ¶
Disconnect removes a manifest from the database. Bumps revision to invalidate dependent queries.
func (*DB) Imports ¶
Imports implements io.ManifestQuerier. Returns a copy of the manifest map for read-only access.
func (*DB) Intern ¶
Intern returns the canonical instance of a value. Values with the same structural hash and equality share the same pointer.
func (*DB) InternType ¶
InternType returns a canonical instance of a type for stable memoization keys.
type Input ¶
type Input[K comparable, V any] struct { // contains filtered or unexported fields }
Input represents a tracked input value keyed by K.
Input is the fundamental source of truth in the incremental computation model. Unlike memoized queries that derive their values, inputs are set directly and form the leaves of the dependency graph.
Each key-value pair carries its own revision number for fine-grained dependency tracking. When an input value changes, only queries that depend on that specific key need recomputation.
Thread safety: All methods are safe for concurrent use via internal locking.
Example usage:
sourceInputs := db.NewInput[string, string](database)
sourceInputs.Set("main.lua", sourceCode)
// Queries that call sourceInputs.Get() will track dependency on that key
result := someQuery.Get(ctx, "main.lua")
func NewInput ¶
func NewInput[K comparable, V any](db *DB) *Input[K, V]
NewInput creates a new input table bound to a DB.
func (*Input[K, V]) Get ¶
func (i *Input[K, V]) Get(ctx *QueryContext, key K) (V, bool)
Get returns the input value for key.
When called within a query context (ctx is non-nil), this records a dependency on the input at the current revision. Future calls to the containing query will revalidate by checking if this input's revision has increased.
Returns the value and true if found, or zero value and false if not.
func (*Input[K, V]) Range ¶
Range iterates over all stored values in a deterministic order.
For ordered key types (string, numeric), iteration occurs in sorted order. For other key types, iteration order is unspecified but consistent within a single Range call.
The callback returns false to stop iteration early.
type Interner ¶
type Interner struct {
// contains filtered or unexported fields
}
Interner provides structural deduplication.
type Query ¶
type Query[K comparable, V any] struct { // contains filtered or unexported fields }
Query represents a memoized query with dependency tracking.
Query is the core abstraction for incremental computation. Each Query:
- Computes a value V from a key K using the provided compute function
- Caches results and tracks which inputs/queries were accessed
- Revalidates cached values when dependencies change
- Handles recursive/cyclic queries via fixpoint iteration
Memoization strategy:
- First call: compute and cache result with dependency list
- Subsequent calls at same revision: return cached value
- After revision bump: check if dependencies changed, recompute if needed
Cycle handling:
- Detects recursive calls to the same (query, key) pair
- Uses seed value for initial approximation
- Iterates to fixpoint using equal function for convergence check
- Applies widen function (if provided) to ensure termination
Thread safety: Query is safe for concurrent use via internal locking.
func NewQuery ¶
func NewQuery[K comparable, V any]( name string, compute func(*QueryContext, K) V, equal func(a, b V) bool, ) *Query[K, V]
NewQuery constructs a memoized query.
Parameters:
- name: identifier for debugging and cycle detection
- compute: function to compute V from K (may call other queries)
- equal: equality function for result comparison and convergence
If equal is nil, defaults to internal.Equaler interface check or pointer equality.
func NewQueryWithWiden ¶
func NewQueryWithWiden[K comparable, V any]( name string, compute func(*QueryContext, K) V, equal func(a, b V) bool, widen func(prev, next V) V, ) *Query[K, V]
NewQueryWithWiden constructs a query with a widening function for cycles.
The widen function is called during fixpoint iteration when a cycle is detected. It should return a value that is "wider" than both inputs, ensuring eventual convergence. Common widening strategies include unioning type sets or taking upper bounds in lattices.
Without widening, cycles may iterate indefinitely. With widening, the sequence prev, widen(prev, next), widen(..., next), ... is guaranteed to stabilize.
func (*Query[K, V]) Clear ¶
func (q *Query[K, V]) Clear()
Clear removes all entries from the query cache.
Use for batch operations where memoization between files isn't needed, or when the database is reset. Does not affect other queries in the database.
func (*Query[K, V]) Get ¶
func (q *Query[K, V]) Get(ctx *QueryContext, key K) V
Get returns the query result, recomputing if dependencies changed.
Algorithm:
- If cached and verified at current revision, return cached value
- If cached but not verified, check if dependencies changed
- If dependencies unchanged, mark verified and return cached value
- Otherwise, recompute, update cache, and return new value
Cycle handling: If this (query, key) is already being computed (recursive call), returns the current approximation (seed value on first iteration, previous result on subsequent iterations). After the outermost call completes, iterates to fixpoint if a cycle was detected.
If ctx is nil, computes directly without memoization or dependency tracking.
func (*Query[K, V]) SetAlwaysWiden ¶
SetAlwaysWiden enables widening on every update, not just during cycles. Use for monotone analyses where results should only grow.
func (*Query[K, V]) SetMaxIter ¶
SetMaxIter controls how many fixpoint iterations to attempt before triggering onMaxIter.
func (*Query[K, V]) SetOnMaxIter ¶
SetOnMaxIter registers a handler for non-converging cycles.
func (*Query[K, V]) SetOnMaxIterReturnLast ¶
func (q *Query[K, V]) SetOnMaxIterReturnLast()
SetOnMaxIterReturnLast avoids panics by returning the last value after max iterations.
type QueryContext ¶
type QueryContext struct {
// contains filtered or unexported fields
}
QueryContext carries query dependency tracking state.
A QueryContext tracks which inputs and queries are accessed during computation, enabling the incremental computation system to determine which cached values need revalidation when inputs change.
Lifecycle:
- Create a new QueryContext for each top-level analysis run
- Pass the same context through all query calls in that run
- Discard after the run completes
Thread safety: QueryContext is not safe for concurrent use. Use a single context per goroutine, or serialize access externally.
The context also carries attachments (via Attach/Attached) for passing additional state through the query graph without modifying function signatures.
func NewQueryContext ¶
func NewQueryContext(db *DB) *QueryContext
NewQueryContext creates a query context for a DB.
func (*QueryContext) DB ¶
func (c *QueryContext) DB() *DB
DB returns the backing database for this context.
Source Files