Documentation
¶
Overview ¶
Package incremental implements a query-oriented incremental compilation framework.
The primary type of this package is Executor, which executes Query values and caches their results. Queries can themselves depend on other queries, and can request that those dependencies be executed (in parallel) using Resolve.
Queries are intended to be relatively fine-grained. For example, there might be a query that represents "compile a module" that contains a list of file names as input. It would then depend on the AST queries for each of those files, from which it would compute lists of imports, and depend on queries based on those inputs.
Implementing a Query ¶
Each query must provide a key that uniquely identifies it, and a function for actually computing it. Queries can partially succeed: instead of a query returning (T, error), it only returns a T, and errors are flagged to the Task argument.
If a query cannot proceed, it can call [Task.Fail], which will mark the query as failed and exit the goroutine dedicated to running that query. No queries that depend on it will be executed. Non-fatal errors can be recorded with [Task.Error].
This means that generally queries do not need to worry about propagating errors correctly; this happens automatically in the framework. The entry-point for query execution, Run, will return all errors that partially-succeeding or failing queries return.
Why can queries partially succeed? Consider a parsing operation. This may generate diagnostics that we want to bubble up to the caller, but whether or not the presence of errors is actually fatal depends on what the caller wants to do with the query result. Thus, queries should generally not fail unless one of their dependencies produced an error they cannot handle.
Queries can inspect errors generated by their direct dependencies, but not by those dependencies' dependencies. (Run, however, returns all transitive errors).
Invalidating Queries ¶
Executor supports invalidating queries by key, which will cause all queries that depended on that query to be discarded and require recomputing. This can be used e.g. to mark a file as changed and require that everything that that file depended on is recomputed. See Executor.Evict.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type AnyQuery ¶
type AnyQuery struct {
// contains filtered or unexported fields
}
AnyQuery is a Query that has been type-erased.
func AsAny ¶
AsAny type-erases a Query.
This is intended to be combined with Resolve, for cases where queries of different types want to be run in parallel.
If q is nil, returns nil.
func (*AnyQuery) Format ¶
Format implements fmt.Formatter.
func (*AnyQuery) Underlying ¶
Underlying returns the original, non-AnyQuery query this query was constructed with.
type ErrPanic ¶
type ErrPanic struct {
Query *AnyQuery // The query that panicked.
Panic any // The actual value passed to panic().
Backtrace string // A backtrace for the panic.
}
ErrPanic is returned by Run if any of the queries it executes panic. This error is used to cancel the context.Context that governs the call to Run.
type Executor ¶
type Executor struct {
// contains filtered or unexported fields
}
Executor is a caching executor for incremental queries.
See New, Run, and [Invalidate].
func New ¶
func New(options ...ExecutorOption) *Executor
New constructs a new executor with the given maximum parallelism.
func (*Executor) Evict ¶
Evict marks query keys as invalid, requiring those queries, and their dependencies, to be recomputed. keys that are not cached are ignored.
This function cannot execute in parallel with calls to Run, and will take an exclusive lock (note that Run calls themselves can be run in parallel).
func (*Executor) EvictWithCleanup ¶
EvictWithCleanup is like Executor.Evict, but it executes the given cleanup function atomically with the eviction action.
This function can be used to clean up after a query, or modify the result of the evicted query by writing to a variable, without risking concurrent calls to Run seeing inconsistent or stale state across multiple queries.
type ExecutorOption ¶
type ExecutorOption func(*Executor)
ExecutorOption is an option func for New.
func WithDebugEvict ¶
func WithDebugEvict(wait time.Duration) ExecutorOption
WithDebugEvict takes a time.Duration and configures debug mode for evictions in the executor.
If set and the compiler is built with the debug tag, when Executor.EvictWithCleanup is called, all evicted keys will be tracked. Then after eviction, a goroutine will be kicked off to sleep for the configured duration, force a GC run, and then print out all pointers that should be evicted but have not been GC'd.
func WithParallelism ¶
func WithParallelism(n int64) ExecutorOption
WithParallelism sets the maximum number of queries that can execute in parallel. Defaults to GOMAXPROCS if not set explicitly.
func WithReportOptions ¶
func WithReportOptions(options report.Options) ExecutorOption
WithReportOptions sets the report options for reports generated by this executor.
type Query ¶
type Query[T any] interface { // Returns a unique key representing this query. // // This should be a comparable struct type unique to the query type. Failure // to do so may result in different queries with the same key, which may // result in incorrect results or panics. Key() any // Executes this query. This function will only be called if the result of // this query is not already in the [Executor]'s cache. // // The error return should only be used to signal if the query failed. For // non-fatal errors, you should record that information with [Task.NonFatal]. // // Implementations of this function MUST NOT call [Run] on the executor that // is executing them. This will defeat correctness detection, and lead to // resource starvation (and potentially deadlocks). // // Panicking in execute is not interpreted as a fatal error that should be // memoized; instead, it is treated as cancellation of the context that // was passed to [Run]. Execute(*Task) (value T, fatal error) }
Query represents an incremental compilation query.
Types which implement Query can be executed by an Executor, which automatically caches the results of a query.
type Result ¶
type Result[T any] struct { Value T // Value is unspecified if Fatal is non-nil. Fatal error // Set if this result has possibly changed since the last time [Run] call in // which this query was computed. // // This has important semantics wrt to calls to [Run]. If *any* call to // [Resolve] downstream of a particular call to [Run] returns a true value // for Changed for a particular query, all such calls to [Resolve] will. // This ensures that the value of Changed is deterministic regardless of // the order in which queries are actually scheduled. // // This flag can be used to implement partial caching of a query. If a query // calculates the result of merging several queries, it can use its own // cached result (provided by the caller of [Run] in some way) and the value // of [Changed] to only perform a partial mutation instead of a complete // merge of the queries. Changed bool }
Result is the Result of executing a query on an Executor, either via Run or Resolve.
func Resolve ¶
Resolve executes a set of queries in parallel. Each query is run on its own goroutine.
If the context passed Executor expires, this will return context.Cause. The caller must propagate this error to ensure the whole query graph exits quickly. Failure to propagate the error will result in incorrect query results.
If a cycle is detected for a given query, the query will automatically fail and produce an ErrCycle for its fatal error. If the call to Query.Execute returns an error, that will be placed into the fatal error value, instead.
Callers should make sure to check each result's fatal error before using its value.
Non-fatal errors for each result are only those that occurred as a direct result of query execution, and *does not* contain that query's transitive errors. This is unlike the behavior of Run, which only collects errors at the very end. This ensures that errors are not duplicated, something that is not possible to do mid-query.
Note: this function really wants to be a method of Task, but it isn't because it's generic.
func Run ¶
func Run[T any](ctx context.Context, e *Executor, queries ...Query[T]) ([]Result[T], *report.Report, error)
Run executes a set of queries on this executor in parallel.
This function only returns an error if ctx expires during execution, in which case it returns nil and context.Cause.
Errors that occur during each query are contained within the returned results. Unlike Resolve, these contain the *transitive* errors for each query!
Implementations of Query.Execute MUST NOT UNDER ANY CIRCUMSTANCES call Run. This will result in potential resource starvation or deadlocking, and defeats other correctness verification (such as cycle detection). Instead, use Resolve, which takes a Task instead of an Executor.
Note: this function really wants to be a method of Executor, but it isn't because it's generic.
type Task ¶
type Task struct {
// contains filtered or unexported fields
}
Task represents a query that is currently being executed.
Values of type Task are passed to Query. The main use of a Task is to be passed to Resolve to resolve dependencies.
type ZeroQuery ¶
type ZeroQuery[T any] struct{}
ZeroQuery is a Query that produces the zero value of T.
This query is useful for cases where you are building a slice of queries out of some input slice, but some of the elements of that slice are invalid. This can be used as a "placeholder" query so that indices of the input slice match the indices of the result slice returned by Resolve.
Source Files
Directories