Help us shape the future of Go! Take the 2026 Go Developer Survey

incremental

package
v0.9.0 Latest Latest
Warning

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

 Go to latest Published: Oct 30, 2026 License: Apache-2.0 Imports: 19 Imported by: 0

Documentation

Overview

Package incremental is a generic incremental computation graph. Queries are opaque keys; a session records the exact inputs each evaluation read — including reads that found nothing — and commits transactionally against a generation, so a later session reruns exactly the queries whose recorded reads changed. It knows nothing about templating or Kubernetes.

See docs/adr/0023-incremental-render-graph.md.

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrCommitConflict means another session committed first.
	ErrCommitConflict = errors.New("incremental graph commit conflict")

	// ErrRevisionConflict means final input verification found a newer snapshot.
	ErrRevisionConflict = errors.New("incremental input revision conflict")
	// ErrVerifierRequired prevents publishing unverified speculative state.
	ErrVerifierRequired = errors.New("incremental input revision verifier is required")
	// ErrSessionClosed means a session is committing, committed, or aborted.
	ErrSessionClosed = errors.New("incremental graph session is closed")
	// ErrGenerationExhausted means no later commit generation can be represented.
	ErrGenerationExhausted = errors.New("incremental graph generation exhausted")
	// ErrResolverRequired prevents retiring inputs that cannot be loaded again.
	ErrResolverRequired = errors.New("incremental input resolver is required")
)

Functions

func DescribeTuple added in v0.7.0 

func DescribeTuple(value string) string

DescribeTuple renders an EncodeTuple value for people, as head(element, ...). Any other value comes back Go-quoted, so a description never carries a raw control character.

func EncodeTuple added in v0.7.0 

func EncodeTuple(head string, tail ...string) string

EncodeTuple encodes an ordered tuple of strings as one key. Each element is prefixed with its canonical uvarint length, so distinct tuples never share an encoding and every element may hold any byte.

Types

type BatchQuery 

type BatchQuery struct {
	Key    QueryKey
	Reader Reader
	// contains filtered or unexported fields
}

BatchQuery is one independently tracked query execution in a batch.

func (BatchQuery) NewExactValue 

func (q BatchQuery) NewExactValue(value string) (ExactValueRoot, error)

NewExactValue binds an immutable string to this live query execution.

type BatchQueryFunc 

type BatchQueryFunc func(context.Context, []BatchQuery) ([]BatchValue, error)

BatchQueryFunc executes sorted queries without merging their dependency readers.

type BatchValue 

type BatchValue struct {
	Value []byte
	Err   error
}

BatchValue is the value or error produced for one BatchQuery.

type ColdExactBatch 

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

ColdExactBatch exposes sorted query handles without allocating one reader per query.

func (ColdExactBatch) CompleteWave 

func (b ColdExactBatch) CompleteWave(values ...ColdExactBatchValue) ([]ExactResult, error)

CompleteWave initializes no value unless every member passes preflight.

func (ColdExactBatch) Len 

func (b ColdExactBatch) Len() int

Len returns the number of queries in the batch.

func (ColdExactBatch) Query 

func (b ColdExactBatch) Query(index int) ColdExactBatchQuery

Query returns the independently tracked query at index.

func (ColdExactBatch) SealWave 

func (b ColdExactBatch) SealWave(results ...ExactResult) error

SealWave authenticates and freezes one completed dependency wave atomically.

type ColdExactBatchFunc 

type ColdExactBatchFunc func(context.Context, ColdExactBatch) error

ColdExactBatchFunc computes every query in one cold columnar execution.

type ColdExactBatchQuery 

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

ColdExactBatchQuery is a query-bound dependency reader and value authority.

func (ColdExactBatchQuery) Complete 

func (q ColdExactBatchQuery) Complete(value string) (ExactValueRoot, error)

Complete records the query's only value and returns its authenticated root.

func (ColdExactBatchQuery) ExactInput 

func (q ColdExactBatchQuery) ExactInput(key InputKey) (Input, error)

func (ColdExactBatchQuery) ExactInputOwned 

func (q ColdExactBatchQuery) ExactInputOwned(key InputKey) (Input, error)

func (ColdExactBatchQuery) Input 

func (q ColdExactBatchQuery) Input(key InputKey) (value []byte, found bool, err error)

func (ColdExactBatchQuery) Key 

func (q ColdExactBatchQuery) Key() QueryKey

Key returns the opaque query identity bound to this handle.

func (ColdExactBatchQuery) ObserveExactImmutableInput 

func (q ColdExactBatchQuery) ObserveExactImmutableInput(expected ImmutableInput) error

func (ColdExactBatchQuery) ObserveExactInput 

func (q ColdExactBatchQuery) ObserveExactInput(expected InputRevision) error

func (ColdExactBatchQuery) ObserveExactInputValue 

func (q ColdExactBatchQuery) ObserveExactInputValue(expected Input) error

func (ColdExactBatchQuery) ObserveExactQuery 

func (q ColdExactBatchQuery) ObserveExactQuery(observation ExactQueryObservation) error

ObserveExactQuery records an authenticated query dependency and its transitive inputs without reading or copying the query value.

func (ColdExactBatchQuery) Query 

func (q ColdExactBatchQuery) Query(ctx context.Context, key QueryKey) ([]byte, error)

func (ColdExactBatchQuery) QueryWithExactObservation 

func (q ColdExactBatchQuery) QueryWithExactObservation(
	ctx context.Context,
	key QueryKey,
) ([]byte, ExactQueryObservation, error)

QueryWithExactObservation reads one dependency value and returns an opaque observation that sibling queries can reuse without reading the value again.

type ColdExactBatchValue 

type ColdExactBatchValue struct {
	Index int
	Key   QueryKey
	Value string
}

ColdExactBatchValue binds one batch index to its exact query value.

type CommitPublication 

type CommitPublication struct {
	Publish  func()
	Complete func()
	Abort    func()
}

CommitPublication contains the infallible phases surrounding graph publication.

type CommitPublicationPreparer 

type CommitPublicationPreparer func([]InputKey) (CommitPublication, error)

CommitPublicationPreparer prepares all caller-owned state before publication starts.

type CycleError 

type CycleError struct {
	Path []QueryKey
}

CycleError identifies a dynamic dependency cycle.

func (*CycleError) Error 

func (e *CycleError) Error() string

type Definition 

type Definition struct {
	Key QueryKey
	Run QueryFunc
}

Definition binds one stable query identity to its implementation.

type DefinitionProvider 

type DefinitionProvider func(QueryKey) (QueryFunc, bool)

DefinitionProvider resolves graph-lifetime dynamic query identities.

type ExactBatchQueryFunc 

type ExactBatchQueryFunc func(context.Context, []BatchQuery) ([]ExactBatchValue, error)

ExactBatchQueryFunc executes sorted queries and returns query-bound immutable values.

type ExactBatchValue 

type ExactBatchValue struct {
	Value ExactValueRoot
	Err   error
}

ExactBatchValue is the immutable value or error produced for one BatchQuery.

type ExactImmutableInputObserver 

type ExactImmutableInputObserver interface {
	Reader
	ObserveExactImmutableInput(ImmutableInput) error
	// contains filtered or unexported methods
}

ExactImmutableInputObserver records an input without exposing mutable bytes.

type ExactInputObserver 

type ExactInputObserver interface {
	Reader
	ObserveExactInput(InputRevision) error
	// contains filtered or unexported methods
}

ExactInputObserver records an input dependency only when its exact identity still matches, without exposing or copying the input bytes.

type ExactInputValueObserver 

type ExactInputValueObserver interface {
	Reader
	ObserveExactInputValue(Input) error
	// contains filtered or unexported methods
}

ExactInputValueObserver records an input only when its complete immutable value still matches.

type ExactQueryObservation 

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

ExactQueryObservation is an opaque authenticated query-node observation. Copies retain the same authority and never contain the query value bytes.

func (*ExactQueryObservation) ValidateAuthentication 

func (o *ExactQueryObservation) ValidateAuthentication() error

ValidateAuthentication verifies that the observation belongs to its live cold-batch transaction and carries a well-formed authenticated value root.

func (*ExactQueryObservation) ValidateFor 

func (o *ExactQueryObservation) ValidateFor(key QueryKey) error

ValidateFor verifies authentication and exact query identity.

type ExactQueryObserver 

type ExactQueryObserver interface {
	Reader
	QueryWithExactObservation(context.Context, QueryKey) ([]byte, ExactQueryObservation, error)
	ObserveExactQuery(ExactQueryObservation) error
	// contains filtered or unexported methods
}

ExactQueryObserver obtains one query value with an authenticated observation and lets sibling queries record that exact dependency without reading its bytes.

type ExactResult 

type ExactResult struct {
	Key   QueryKey
	Value ExactValueRoot
}

ExactResult is one deterministically ordered immutable query result.

type ExactValueRoot 

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

ExactValueRoot is an authenticated immutable query value handle.

func (ExactValueRoot) Bytes 

func (r ExactValueRoot) Bytes() ([]byte, error)

Bytes returns a detached mutable copy of the immutable value.

func (ExactValueRoot) ExactEqual 

func (r ExactValueRoot) ExactEqual(other ExactValueRoot) (bool, error)

ExactEqual compares immutable values exactly without trusting a digest.

func (ExactValueRoot) SameRoot 

func (r ExactValueRoot) SameRoot(other ExactValueRoot) (bool, error)

SameRoot reports authenticated root identity without comparing payload bytes.

func (ExactValueRoot) String 

func (r ExactValueRoot) String() (string, error)

String returns the immutable value without copying its payload.

func (ExactValueRoot) ValidateAuthentication 

func (r ExactValueRoot) ValidateAuthentication() error

ValidateAuthentication verifies the root's private ownership chain in O(1).

type Graph 

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

Graph stores committed incremental query state across sessions.

func New 

func New(definitions ...Definition) (*Graph, error)

New constructs a graph with immutable query definitions.

func NewWithProvider 

func NewWithProvider(provider DefinitionProvider, definitions ...Definition) (*Graph, error)

NewWithProvider adds a fixed graph-lifetime dynamic definition provider.

func NewWithProviderOptions 

func NewWithProviderOptions(
	provider DefinitionProvider,
	options Options,
	definitions ...Definition,
) (*Graph, error)

NewWithProviderOptions configures a graph with dynamic definitions and cache behavior.

func (*Graph) Begin 

func (g *Graph) Begin() (*Session, error)

Begin starts an isolated transaction from the current generation.

func (*Graph) BeginColdReset 

func (g *Graph) BeginColdReset(inputs ...Input) (*Session, error)

BeginColdReset starts a transaction that replaces all cache state after a journal gap.

func (*Graph) BeginColdResetWithConcurrentResolver 

func (g *Graph) BeginColdResetWithConcurrentResolver(
	resolver InputResolver,
	inputs ...Input,
) (*Session, error)

BeginColdResetWithConcurrentResolver starts a cold transaction whose resolver accepts concurrent calls.

func (*Graph) BeginColdResetWithResolver 

func (g *Graph) BeginColdResetWithResolver(
	resolver InputResolver,
	inputs ...Input,
) (*Session, error)

BeginColdResetWithResolver starts a cold transaction with lazy input discovery.

func (*Graph) BeginWithResolver 

func (g *Graph) BeginWithResolver(resolver InputResolver) (*Session, error)

BeginWithResolver starts a transaction with lazy exact input discovery.

func (*Graph) Counters 

func (g *Graph) Counters(key QueryKey) NodeCounters

Counters returns committed counters for one query.

func (*Graph) ExactValue 

func (g *Graph) ExactValue(key QueryKey) (ExactValueRoot, bool, error)

ExactValue returns the authenticated committed value root without copying its payload.

func (*Graph) Generation 

func (g *Graph) Generation() uint64

Generation returns the latest committed generation.

func (*Graph) HasDependents 

func (g *Graph) HasDependents(key QueryKey) bool

HasDependents reports whether at least one committed query directly depends on key.

func (*Graph) HasInputDependents 

func (g *Graph) HasInputDependents(key InputKey) bool

HasInputDependents reports whether at least one committed query directly depends on key.

func (*Graph) ValidateCommittedExactValue 

func (g *Graph) ValidateCommittedExactValue(key QueryKey, root ExactValueRoot) error

ValidateCommittedExactValue verifies exact identity with the graph's committed node root.

func (*Graph) ValidateExactValue 

func (g *Graph) ValidateExactValue(key QueryKey, root ExactValueRoot) error

ValidateExactValue verifies that root belongs to this graph and query in O(1).

func (*Graph) Value 

func (g *Graph) Value(key QueryKey) ([]byte, bool)

Value returns a cloned committed query value.

type ImmutableInput 

type ImmutableInput struct {
	Key      InputKey
	Revision Revision
	Found    bool
	Value    string
}

ImmutableInput binds arbitrary input bytes as an immutable string.

type Input 

type Input struct {
	Key      InputKey
	Revision Revision
	Found    bool
	Value    []byte
}

Input binds immutable bytes, including an exact negative read, to a revision.

type InputKey 

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

InputKey is an opaque, comparable input identity.

Keys are interned because a graph stores one per dependency edge, and edges outnumber distinct keys by orders of magnitude (#284).

func NewInputKey 

func NewInputKey(value string) InputKey

NewInputKey creates an input identity from caller-owned opaque data.

func (InputKey) Opaque 

func (k InputKey) Opaque() string

Opaque returns the input identity without interpreting it.

func (InputKey) String added in v0.7.0 

func (k InputKey) String() string

String describes the key for messages; see DescribeTuple.

type InputResolver 

type InputResolver func(context.Context, InputKey) (Input, error)

InputResolver atomically loads an exact snapshot for a previously unseen key.

type InputRevision 

type InputRevision struct {
	Key      InputKey
	Revision Revision
	Found    bool
}

InputRevision is an exact input observation passed to the commit verifier.

type NodeCounters 

type NodeCounters struct {
	Executions    uint64
	CacheHits     uint64
	Backdates     uint64
	Changes       uint64
	Invalidations uint64
}

NodeCounters describe committed work for one query.

type Options 

type Options struct {
	RetireUnreferencedInputs bool
}

Options controls graph-lifetime cache behavior.

type OwnedInputReader 

type OwnedInputReader interface {
	Reader
	ExactInputOwned(InputKey) (Input, error)
}

OwnedInputReader transfers one detached input snapshot while recording its dependency.

type PreparedGraphCommit 

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

PreparedGraphCommit is an opaque authenticated replacement-generation draft.

func (PreparedGraphCommit) Abort 

func (p PreparedGraphCommit) Abort() error

Abort revokes the draft and discards its speculative session.

func (PreparedGraphCommit) Publish 

func (p PreparedGraphCommit) Publish(ctx context.Context, verifier RevisionVerifier) error

Publish verifies exact inputs and atomically installs the prepared generation.

func (PreparedGraphCommit) PublishWithPreparedPublisher 

func (p PreparedGraphCommit) PublishWithPreparedPublisher(
	ctx context.Context,
	verifier RevisionVerifier,
	prepare CommitPublicationPreparer,
) (err error)

PublishWithPreparedPublisher publishes a fully prepared draft with an exact base CAS.

func (PreparedGraphCommit) PublishWithPublisher 

func (p PreparedGraphCommit) PublishWithPublisher(
	ctx context.Context,
	verifier RevisionVerifier,
	publish func(),
) error

PublishWithPublisher installs caller state immediately before graph visibility.

func (PreparedGraphCommit) RetiredInputs 

func (p PreparedGraphCommit) RetiredInputs() ([]InputKey, error)

RetiredInputs returns the immutable retirement set prepared with the draft.

func (PreparedGraphCommit) ValidateAuthentication 

func (p PreparedGraphCommit) ValidateAuthentication() error

ValidateAuthentication verifies that the draft is live and still targets its exact base.

func (PreparedGraphCommit) ValidateFor 

func (p PreparedGraphCommit) ValidateFor(session *Session) error

ValidateFor verifies authentication and exact session identity.

type QueryFunc 

type QueryFunc func(context.Context, Reader) ([]byte, error)

QueryFunc computes one immutable value. Its error is returned unwrapped, so it names the failing query in its own terms.

type QueryKey 

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

QueryKey is an opaque, comparable query identity, interned like InputKey.

func NewQueryKey 

func NewQueryKey(value string) QueryKey

NewQueryKey creates a query identity from caller-owned opaque data.

func (QueryKey) Opaque 

func (k QueryKey) Opaque() string

Opaque returns the query identity without interpreting it.

func (QueryKey) String added in v0.7.0 

func (k QueryKey) String() string

String describes the key for messages; see DescribeTuple.

type Reader 

type Reader interface {
	Input(InputKey) ([]byte, bool, error)
	ExactInput(InputKey) (Input, error)
	Query(context.Context, QueryKey) ([]byte, error)
}

Reader records dynamic query dependencies while a definition runs.

type Result 

type Result struct {
	Key   QueryKey
	Value []byte
}

Result is one deterministically ordered query result.

type Revision 

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

Revision is an exact, comparable input revision token.

func NewRevision 

func NewRevision(value string) Revision

NewRevision creates a revision from caller-owned opaque data.

func (Revision) Opaque 

func (r Revision) Opaque() string

Opaque returns the exact caller-owned revision token.

type RevisionVerifier 

type RevisionVerifier func(context.Context, []InputRevision) (bool, error)

RevisionVerifier confirms that every observation is still exact at commit.

type Session 

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

Session isolates speculative input and query state until commit.

func (*Session) Abort 

func (s *Session) Abort()

Abort discards all speculative state.

func (*Session) ApplyInputs 

func (s *Session) ApplyInputs(inputs ...Input) error

ApplyInputs stages an atomic invalidation batch before query evaluation starts.

func (*Session) ApplyInputsWhileIdle 

func (s *Session) ApplyInputsWhileIdle(inputs ...Input) ([]QueryKey, error)

ApplyInputsWhileIdle stages inputs between query evaluations and returns newly dirty queries.

func (*Session) BaseGeneration 

func (s *Session) BaseGeneration() uint64

BaseGeneration returns the generation on which this transaction is based.

func (*Session) BaseHasDependents 

func (s *Session) BaseHasDependents(key QueryKey) bool

BaseHasDependents reports whether a committed query in the generation this session began on depends on key.

func (*Session) BaseHasInputDependents 

func (s *Session) BaseHasInputDependents(key InputKey) bool

BaseHasInputDependents reports whether a committed query in the generation this session began on depends on the input key.

func (*Session) BaseValue 

func (s *Session) BaseValue(key QueryKey) ([]byte, bool)

BaseValue returns a query's committed value in the generation this session began on, or false when the base has no clean value for it. It is the session-consistent counterpart of Graph.Value, which reads the graph's current generation and so can be ahead of a session another commit passed.

func (*Session) Commit 

func (s *Session) Commit(ctx context.Context, verifier RevisionVerifier) error

Commit verifies exact inputs and publishes the transaction with generation CAS.

func (*Session) CommitWithPreparedPublisher 

func (s *Session) CommitWithPreparedPublisher(
	ctx context.Context,
	verifier RevisionVerifier,
	prepare CommitPublicationPreparer,
) error

CommitWithPreparedPublisher prepares graph and caller state before either becomes visible.

func (*Session) CommitWithPublisher 

func (s *Session) CommitWithPublisher(
	ctx context.Context,
	verifier RevisionVerifier,
	publish func(),
) error

CommitWithPublisher runs an infallible publication after verification and before graph visibility.

func (*Session) DirtyQueries 

func (s *Session) DirtyQueries() ([]QueryKey, error)

DirtyQueries returns the sorted cached queries requiring evaluation.

func (*Session) Evaluate 

func (s *Session) Evaluate(ctx context.Context, key QueryKey) ([]byte, error)

Evaluate returns a cloned value for one query.

func (*Session) EvaluateAll 

func (s *Session) EvaluateAll(ctx context.Context, keys ...QueryKey) ([]Result, error)

EvaluateAll evaluates unique query keys in deterministic order.

func (*Session) EvaluateAllBatch 

func (s *Session) EvaluateAllBatch(
	ctx context.Context,
	batch BatchQueryFunc,
	keys ...QueryKey,
) ([]Result, error)

EvaluateAllBatch evaluates cache misses through one batch call while keeping one dependency frame, value, and cache node per query. A batched query may read inputs and already-evaluable queries, but it cannot depend on another member of the same batch.

func (*Session) EvaluateAllColdExactBatch 

func (s *Session) EvaluateAllColdExactBatch(
	ctx context.Context,
	batch ColdExactBatchFunc,
	keys ...QueryKey,
) ([]ExactResult, error)

EvaluateAllColdExactBatch evaluates fresh queries in a cold-reset session.

func (*Session) EvaluateAllExactBatch 

func (s *Session) EvaluateAllExactBatch(
	ctx context.Context,
	batch ExactBatchQueryFunc,
	keys ...QueryKey,
) ([]ExactResult, error)

EvaluateAllExactBatch evaluates cache misses and returns authenticated immutable roots.

func (*Session) ExactInput 

func (s *Session) ExactInput(key InputKey) (Input, bool, error)

ExactInput returns the transaction's current immutable value for key.

func (*Session) HasInputDependents 

func (s *Session) HasInputDependents(key InputKey) (bool, error)

HasInputDependents reports whether the transaction retains a direct dependent of key.

func (*Session) MatchesExactInput 

func (s *Session) MatchesExactInput(expected Input) (bool, error)

MatchesExactInput compares a caller-owned snapshot without copying the graph's immutable bytes.

func (*Session) PrepareGraphCommit 

func (s *Session) PrepareGraphCommit(ctx context.Context) (PreparedGraphCommit, error)

PrepareGraphCommit builds and authenticates an immutable replacement draft.

func (*Session) RemoveQueries 

func (s *Session) RemoveQueries(keys ...QueryKey) error

RemoveQueries transactionally evicts queries and their cached dependents.

func (*Session) RemoveQueriesWhileIdle 

func (s *Session) RemoveQueriesWhileIdle(keys ...QueryKey) error

RemoveQueriesWhileIdle transactionally evicts queries between evaluations.

func (*Session) RetiredInputs 

func (s *Session) RetiredInputs() []InputKey

RetiredInputs returns inputs removed by a successful commit.

func (*Session) ValidateBaseExactValue 

func (s *Session) ValidateBaseExactValue(key QueryKey, root ExactValueRoot) error

ValidateBaseExactValue verifies identity with the query root captured by this transaction.

func (*Session) ValidateCurrentExactValue 

func (s *Session) ValidateCurrentExactValue(key QueryKey, root ExactValueRoot) error

ValidateCurrentExactValue verifies identity with the query root currently staged by this transaction.

type TupleDecoder added in v0.7.0 

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

TupleDecoder reads the elements of an EncodeTuple value in order.

func NewTupleDecoder added in v0.7.0 

func NewTupleDecoder(value string) TupleDecoder

NewTupleDecoder starts reading value at its first element.

func (*TupleDecoder) Done added in v0.7.0 

func (d *TupleDecoder) Done() bool

Done reports whether every byte of the value has been read.

func (*TupleDecoder) Next added in v0.7.0 

func (d *TupleDecoder) Next() (string, bool)

Next returns the next element. It reports false when no element is left or the remaining bytes are not a canonical element.

Source Files

View all Source files

Directories

Path Synopsis
internal
immutablevector
Package immutablevector owns compact immutable slices behind authenticated roots.
 Package immutablevector owns compact immutable slices behind authenticated roots.
orderedset

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.