incr

package module
v1.2.0 Latest Latest
Warning

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

 Go to latest Published: Apr 17, 2024 License: MIT Imports: 15 Imported by: 8

README

go-incr

Continuous Integration Go Report Card

Graph

go-incr is an optimization tool to help implement partial computation of large graphs of operations.

It's useful in situations where you want to efficiently compute the outputs of computations where only a subset of the computation changes based on changes in inputs, but also specifically when the graph might be dynamic over the course of the computation's lifetime.

Think Excel spreadsheets and formulas, but in code, which can change over time.

Important caveat

Very often code is faster without incremental. Only reach for this library if you've hit a wall and need to add incrementality.

Inspiration & differences from the original

The inspiration for go-incr is Jane Street's incremental library.

The key difference from this library versus the Jane Street implementation is parallelism. You can stabilize multiple nodes with the same recompute height at once using ParallelStabilize. This is especially useful if you have nodes that make network calls or do other non-cpu bound work.

Basic concepts

A computation in go-incr is composed of three "meta" node types.

  • "Input" types that act as entry-points for data that we'll need in our computation (think, raw cell values in Excel)
  • "Mutator" types that take other nodes as inputs, and transform those input values into new values (think, formulas in Excel) or even new sub-graph components.
  • "Observe" type that indicates which values we care about, and ultimately want to display or return.

"Input" types for go-incr are Var and Return typically.

"Mutator" types for go-incr are nodes like Map and Bind.

The observer node is special in that there is only (1) type of observer, and it has a very specific role and cannot be passed as an input to other nodes.

Usage

A mini-worked example:

import "github.com/wcharczuk/go-incr"
...
g := incr.New()
v0 := incr.Var(g, "hello")
v1 := incr.Var(g, "world!")
m := incr.Map2(g, v0, v1, func(a, b string) string {
  return a+" "+b
})
om := incr.MustObserve(g, m)
_ = g.Stabilize(context.Background())
fmt.Println(om.Value()) // prints "hello world!"

This is not intended as a "real" use case for the library, simply as a worked example to show the syntax.

You can see more sample use cases in the examples/ directory in this repository.

API compatibility guarantees

As of v1.xxx you should assume that the functions and types exported by this library will maintain forward compatibility until some future v2 necessitates changing things meaningfully, at which point we'll integrate semantic import versioning to create a new /v2/ package. The goal will be to put off a v2 for as long as possible.

An exception to the preceeding are the incr.Expert... functions, for which there are no guarantees and the API may change between refs without notice.

A word on how to use this library effectively

It can be tempting to, when looking at what this library can do, make every operation in a slow piece of code incrementally computed.

This will typically make performance worse, as making a computation incrementally computed adds overhead for each operation.

A more ideal balance is to write your code as normal assuming nothing is incrementally computed, then do a coarsed-grain pass, specifically breaking up chunks that are mostly atomic, and making those chunks incrementally computed.

Error handling and context propagation

There are simplified versions of common node types (Map and Map2) as well as more advanced versions (MapContext and Map2Context) that are intended for real world use cases, and facilitating taking contexts and returning errors from operations.

Errors returned by these incremental operations will halt the computation for the stabilization pass, but the effect will be slightly different based on the stabilization method used.

When recomputing serially (using .Stabilize(...)) the stabilization pass will return immediately on error and no other nodes will be recomputed.

When recomputing in parallel (using .ParallelStabilize(...)), the current height block will finish stabilizing, and subsequent height blocks will not be recomputed.

Design Choices

There is some consideration with this library on the balance between hiding mutable implemenation details to protect against Hyrum's Law issues, and surfacing enough utility helpers to allow users to extend this library for their own use cases (specifically through incr.Expert... types.)

As a result, most of the features of this library can be leveraged externally, but little of the internal state and recomputation mechanism is exposed to the user.

Specific implications of this are, the INode interface includes a function that returns the Node metadata, but this Node struct has few exported fields on it, and users of this library should not really concern themselves with what's on it, just that it gets supplied to Incr through the interface implementation.

Implementation details

To determine which nodes to recompute go-incr uses a partial-order pseudo-height adjacency list similar to the Jane Street implementation. This offers "good enough" approximation of a heap while also allowing for fast iteration (e.g. faster than a traditional heap's O(log(n)) performance).

The underlying assumption is that nodes with the same pseudo-height do not depend on each other, and as a result can be recomputed in parallel.

A word on Bind

The Bind incremental is by far the most powerful, and as a result complicated, node type in the ecosystem.

To explain its purpose; there are situations where you want to dynamically swap out parts of a graph rooted at a given node. A concrete example might be in a user interface swapping out the displayed controls, which may be made up of individual computations.

The effect of Bind is that "children" of a Bind node may have their heights change significantly depending on the changes made to the "bound" nodes, and this has implications for the recomputation heap as a result, specifically that it has to handle updating the reflected height of nodes that may already be in the heap.

Bind nodes may also return Bind nodes themselves, creating fun and interesting implications for how an inner right-hand-side incremental needs to be propagated through multiple layers of binds, and reflect both its and the original bind children's true height through recomputations. To do this, we adopt the trick from the main ocaml library of creating two new pieces of state; a bind-lhs-change node that links the original bind input, and the right-hand-side incremental of the bind, making sure that the rhs respects the height of the transitive dependency of the bind's input. We also maintain a "scope", or a list of all the nodes that were created in respect to the rhs, and when the outer bind stabilizes, we also propagate changes to inner binds, regardless of where they are in the rhs graph.

If this sounds complicated, it is!

A word on Scopes

Because Bind nodes rely on scopes to operate correctly, and specifically know which nodes it was responsible for creating, the function you must provide to the Bind node constructor is passed Scope argument. This scope argument should be passed to node constructors within the bind function.

An example of a use case for bind might be:

g := incr.New()
t1 := incr.Map(g, Return(g, "hello"), func(v string) string { return v + " world!" })
t2v := incr.Var(g, "a")
t2 := incr.Bind(g, t2v, func(scope incr.Scope, t2vv string) Incr[string] {
  return Map(scope, t1, func(v string) string { return v + " Ipsum" })
})

Here t1 is not created within a bind scope (it's created in the top level scope by passing in the Graph reference), but the map that adds " Ipsum" to the value is created within a bind scope. This is done transparently by passing the scope through the Map constructor within the bind.

Progress

Many of the original library types are implemented, including:

  • Always|Timer
  • Bind(2,3,4,If)
  • Cutoff(2)
  • Freeze
  • Map(2,3,4,If,N)
  • Observe
  • Return
  • Sentinel
  • Var
  • Watch

With these, you can create 90% of what this library is typically needed for, though some others would be relatively straightforward to implement given the primitives already implemented.

An example of likely extension to this to facilitate some more advanced use cases; adding the ability to set inputs after nodes have been created, as well as the ability to return un-typed values from nodes.

Documentation

Overview

Incr is a library that enables building incremental computation graphs.

These graphs are useful for partially recomputing a small subset of a very large number of computations if only a subset of the inputs change.

Index

Constants

View Source 
const (
	StatusNotStabilizing int32 = iota
	StatusStabilizing
	StatusRunningUpdateHandlers
)

Status constants for graph stabilization status.

View Source 
const (
	// DefaultMaxHeight is the default maximum height that can
	// be tracked in the recompute heap.
	DefaultMaxHeight = 256
)
View Source 
const HeightUnset = -1

HeightUnset is a constant that denotes that a height isn't strictly set (because heights can be 0, we have to use something other than the integer zero value).

Variables

View Source 
var (
	// ErrAlreadyStabilizing is returned if you're already stabilizing a graph.
	ErrAlreadyStabilizing = errors.New("stabilize; already stabilizing, cannot continue")
)

Functions

func DetectCycleIfLinked 

func DetectCycleIfLinked(child, parent INode) error

DetectCycleIfLinked determines if adding a given input to a given child would cause a graph cycle.

It is a low-level utility function that should be used in special cases; the vast majority of situations outside very esoteric Bind use cases cannot create cycles.

func Dot 

func Dot(wr io.Writer, g *Graph) (err error)

Dot formats a graph from a given node in the dot format so that you can export the graph as an image.

To do so, you'll want to make sure you have `graphviz` installed locally, and then you'll want to run: 

> go run ??? | dot -Tpng > /home/foo/graph.png

As an for an example of a program that renders a graph with `Dot`, look at `examples/benchmark/main.go`.

func FormatStabilizationNumber 

func FormatStabilizationNumber(ctx context.Context) (output string)

FormatStabilizationNumber formats the stabilization number from a context for tracing output.

func GetStabilizationNumber 

func GetStabilizationNumber(ctx context.Context) (stabilizationNumber uint64, ok bool)

GetStabilizationNumber gets the stabilization number from a context.

func OptGraphMaxHeight 

func OptGraphMaxHeight(maxHeight int) func(*GraphOptions)

OptGraphMaxHeight sets the graph max recompute height.

func OptGraphParallelism added in v1.1.8 

func OptGraphParallelism(parallelism int) func(*GraphOptions)

OptGraphParallelism sets the parallelism factor, or said another way the number of goroutines, to use when stabilizing using Graph.ParallelStabilize.

This will default to runtime.NumCPU if unset.

func OptGraphPreallocateNodesSize added in v1.1.8 

func OptGraphPreallocateNodesSize(size int) func(*GraphOptions)

OptGraphPreallocateNodesSize preallocates the node tracking map within the graph with a given size number of elements for items.

If not provided, no size for elements will be preallocated.

func OptGraphPreallocateObserversSize added in v1.1.8 

func OptGraphPreallocateObserversSize(size int) func(*GraphOptions)

OptGraphPreallocateObserversSize preallocates the observer tracking map within the graph with a given size number of elements for items.

If not provided, no size for elements will be preallocated.

func OptGraphPreallocateSentinelsSize added in v1.1.8 

func OptGraphPreallocateSentinelsSize(size int) func(*GraphOptions)

OptGraphPreallocateSentinelsSize preallocates the sentinel tracking map within the graph with a given size number of elements for items.

If not provided, no size for elements will be preallocated.

func SetIdentifierProvider added in v1.1.8 

func SetIdentifierProvider(ip func() Identifier)

SetIdentifierProvider sets the identifier provider to a custom provider separate from the default.

This is especially useful in performance critical use cases where the identifier doesn't need to be securely random, that is there are looser constraints on the randomness of the identifier because there will be few nodes over the lifetime of the program or graph.

func TraceErrorf 

func TraceErrorf(ctx context.Context, format string, args ...any)

TraceErrorf prints a line to the error output of a tracer on a given context with a given format and args.

func TraceErrorln 

func TraceErrorln(ctx context.Context, args ...any)

TraceErrorln prints a line to the error output of a tracer on a given context.

func TracePrintf 

func TracePrintf(ctx context.Context, format string, args ...any)

TracePrintf prints a line to the tracer on a given context with a given format and args.

func TracePrintln 

func TracePrintln(ctx context.Context, args ...any)

TracePrintln prints a line to the tracer on a given context.

func WithStabilizationNumber 

func WithStabilizationNumber(ctx context.Context, stabilizationNumber uint64) context.Context

WithStabilizationNumber adds a stabilization number to a context.

func WithTracer 

func WithTracer(ctx context.Context, tracer Tracer) context.Context

WithTracer adds a tracer to a given context.

func WithTracing 

func WithTracing(ctx context.Context) context.Context

WithTracing adds a default tracer to a given context.

Tracing writes text logs to a standard out and standard error around the stabilization process, though for performance reasons this is typically just the start and stop of stabilization, and the elapsed time.

func WithTracingOutputs 

func WithTracingOutputs(ctx context.Context, output, errOutput io.Writer) context.Context

WithTracingOutputs adds a tracer to a given context with given outputs.

func WithinScope 

func WithinScope[A INode](scope Scope, node A) A

WithinScope updates a node's createdIn scope to reflect a new inner-most bind scope applied by a bind.

The scope itself is created by a bind at its construction, and will hold a reference to both the bind node itself and the bind's left-hand-side or input node. All nodes created within the bind's function will be associated with its scope unless they were created outside that scope and are simply referenced by nodes created by the bind.

You shouldn't need to call WithinScope in practice typically, as it is sufficient to pass the Bind function's provided scope to node constructors to associate the scopes correctly. This method is exported for advanced use cases where you want to manage scopes manually.

Types

type BindContextFunc 

type BindContextFunc[A, B any] func(context.Context, Scope, A) (Incr[B], error)

BindContextFunc is the type of bind function.

type BindFunc 

type BindFunc[A, B any] func(Scope, A) Incr[B]

BindFunc is the type of bind function.

type BindIncr 

type BindIncr[A any] interface {
	Incr[A]
	IStabilize
	IShouldBeInvalidated
	IBindMain
	fmt.Stringer
}

BindIncr is a node that implements Bind, which can dynamically swap out subgraphs based on input incrementals changing.

BindIncr gives the graph dynamism, but as a result is somewhat expensive to compute and should be used tactically.

func Bind 

func Bind[A, B any](scope Scope, input Incr[A], fn BindFunc[A, B]) BindIncr[B]

Bind lets you swap out an entire subgraph of a computation based on a given function and a single input.

A way to think about this, as a sequence:

A given node `a` can be bound to `c` or `d` or more subnodes with the value of `a` as the input: 

a -> b.bind() -> c

We might want to, at some point in the future, swap out `c` for `d` based on some logic: 

a -> b.bind() -> d

As a result, (a) is a child of (b), and (c) or (d) are children of (b). When the bind changes from (c) to (d), (c) is unlinked, and is removed as a "child" of (b), preventing it from being considered part of the overall computation unless it's referenced by another node in the graph.

More information is available at in the [Janestreet docs].

func Bind2 

func Bind2[A, B, C any](scope Scope, a Incr[A], b Incr[B], fn func(Scope, A, B) Incr[C]) BindIncr[C]

Bind2 lets you swap out an entire subgraph of a computation based on a given set of 2 input incrementals.

func Bind2Context 

func Bind2Context[A, B, C any](scope Scope, a Incr[A], b Incr[B], fn func(context.Context, Scope, A, B) (Incr[C], error)) BindIncr[C]

Bind2Context lets you swap out an entire subgraph of a computation based on a given set of 2 input incrementals, taking a context and as well returning an error.

func Bind3 

func Bind3[A, B, C, D any](scope Scope, a Incr[A], b Incr[B], c Incr[C], fn func(Scope, A, B, C) Incr[D]) BindIncr[D]

Bind3 lets you swap out an entire subgraph of a computation based on a given set of 3 input incrementals.

func Bind3Context 

func Bind3Context[A, B, C, D any](scope Scope, a Incr[A], b Incr[B], c Incr[C], fn func(context.Context, Scope, A, B, C) (Incr[D], error)) BindIncr[D]

Bind3Context lets you swap out an entire subgraph of a computation based on a given set of 3 input incrementals, taking a context and as well returning an error.

func Bind4 

func Bind4[A, B, C, D, E any](scope Scope, a Incr[A], b Incr[B], c Incr[C], d Incr[D], fn func(Scope, A, B, C, D) Incr[E]) BindIncr[E]

Bind4 lets you swap out an entire subgraph of a computation based on a given set of 4 input incrementals.

func Bind4Context 

func Bind4Context[A, B, C, D, E any](scope Scope, a Incr[A], b Incr[B], c Incr[C], d Incr[D], fn func(context.Context, Scope, A, B, C, D) (Incr[E], error)) BindIncr[E]

Bind4Context lets you swap out an entire subgraph of a computation based on a given set of 4 input incrementals, taking a context and as well returning an error.

func BindContext 

func BindContext[A, B any](scope Scope, input Incr[A], fn BindContextFunc[A, B]) BindIncr[B]

BindContext is like Bind but allows the bind delegate to take a context and return an error.

If an error returned, the bind is aborted, the error listener(s) will fire for the node, and the computation will stop.

func BindIf 

func BindIf[A any](scope Scope, p Incr[bool], fn func(context.Context, Scope, bool) (Incr[A], error)) BindIncr[A]

BindIf lets you swap out an entire subgraph of a computation based on a given boolean incremental predicate.

It is largely "macro" for a Bind that takes an input bool incremental.

type Cutoff2ContextFunc 

type Cutoff2ContextFunc[A, B any] func(context.Context, A, B, B) (bool, error)

Cutoff2ContextFunc is a function that implements cutoff checking and takes a context.

type Cutoff2Func 

type Cutoff2Func[A, B any] func(A, B, B) bool

Cutoff2Func is a function that implements cutoff checking.

type CutoffContextFunc 

type CutoffContextFunc[A any] func(context.Context, A, A) (bool, error)

CutoffContextFunc is a function that implements cutoff checking and takes a context.

type CutoffFunc 

type CutoffFunc[A any] func(A, A) bool

CutoffFunc is a function that implements cutoff checking.

type Graph 

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

Graph is the state that is shared across nodes in a computation graph.

You should instantiate this type with the New function.

The graph holds information such as, how many stabilizations have happened, what node are currently observed, and what nodes need to be recomputed.

func GraphForNode 

func GraphForNode(node INode) *Graph

GraphForNode returns the graph for a given node as derrived through the scope it was created in, which must return a graph reference.

func GraphForScope added in v1.1.0 

func GraphForScope(s Scope) *Graph

GraphForScope returns the graph for a given scope.

It is used for advanced situations where you need to refer back to the underlying graph of a scope but may not have a reference available (e.g. in generalized bind functions).

func New 

func New(opts ...GraphOption) *Graph

New returns a new Graph, which is the type that represents the shared state of a computation graph.

You can pass configuration options as GraphOption to customize settings within the graph, such as what the maximum "height" a node can be.

This is the entrypoint for all stabilization and computation operations, and generally the Graph will be passed to node constructors.

Nodes you initialize the graph with will need to be be observed by an [Observer] before you can stabilize them.

func (*Graph) Has 

func (graph *Graph) Has(gn INode) (ok bool)

IsObserving returns if a graph is observing a given node.

func (*Graph) HasObserver 

func (graph *Graph) HasObserver(on IObserver) (ok bool)

HasObserver returns if a graph has a given observer.

func (*Graph) HasSentinel added in v1.1.0 

func (graph *Graph) HasSentinel(sn ISentinel) (ok bool)

HasSentinel returns if a graph has a given sentinel.

func (*Graph) ID 

func (graph *Graph) ID() Identifier

ID is the identifier for the graph.

func (*Graph) IsStabilizing 

func (graph *Graph) IsStabilizing() bool

IsStabilizing returns if the graph is currently stabilizing.

func (*Graph) Label 

func (graph *Graph) Label() string

Label returns the graph label.

func (*Graph) Metadata 

func (graph *Graph) Metadata() any

Metadata is extra data held on the graph instance.

func (*Graph) OnStabilizationEnd 

func (graph *Graph) OnStabilizationEnd(handler func(context.Context, time.Time, error))

OnStabilizationEnd adds a stabilization end handler.

func (*Graph) OnStabilizationStart 

func (graph *Graph) OnStabilizationStart(handler func(context.Context))

OnStabilizationStart adds a stabilization start handler.

func (*Graph) ParallelStabilize 

func (graph *Graph) ParallelStabilize(ctx context.Context) (err error)

ParallelStabilize stabilizes a graph in parallel.

This is done similarly to Graph.Stabilize, in that nodes are stabilized starting with the minimum height in the recompute heap working upwards, but unlike the serial processing that Graph.Stabilize does, Graph.ParallelStabilize will process a height "block" all at once concurrently.

Because of the concurrent nature of the block processing, Graph.ParallelStabilize is considerably slower to process nodes, specifically because locks have to be acquired and shared state managed carefully.

You should only reach for Graph.ParallelStabilize if you have very long running node recomputations that would benefit from processing in parallel, e.g. if you have nodes that are I/O bound or CPU intensive.

func (*Graph) SetLabel 

func (graph *Graph) SetLabel(label string)

SetLabel sets the graph label.

func (*Graph) SetMetadata 

func (graph *Graph) SetMetadata(metadata any)

SetMetadata sets the metadata for the graph instance.

func (*Graph) SetStale 

func (graph *Graph) SetStale(gn INode)

SetStale sets a node as stale.

func (*Graph) Stabilize 

func (graph *Graph) Stabilize(ctx context.Context) (err error)

Stabilize kicks off the stabilization for nodes that have been observed by the graph's scope.

The general process of stabilization is to scan the recompute heap up from the minimum height block, processing each node in the block until there are no more nodes.

Stabilizing a node can add more nodes to the recompute heap, creating more work as the stabilization progresses, until finally no more nodes are left to process.

The [Stabailize] stabilization process is serial, that is each node is recomputed in sequence one after the other.

This can be extremely fast in practice because it lets us makes some assumptions about what can change in during each node's stabilization, specifically we can assume that Bind nodes evaluate serially and we can adjust recompute heights accordingly, and as a result we don't need to worry about shared resource contention and can skip acquiring locks.

If during the stabilization pass a node's stabilize function returns an error, the recomputation pass is stopped and the error is returned.

func (*Graph) String 

func (graph *Graph) String() string

type GraphOption 

type GraphOption func(*GraphOptions)

GraphOption mutates GraphOptions.

type GraphOptions 

type GraphOptions struct {
	MaxHeight                int
	Parallelism              int
	PreallocateNodesSize     int
	PreallocateObserversSize int
	PreallocateSentinelsSize int
}

GraphOptions are options for graphs.

type IAlways 

type IAlways interface {
	Always()
}

IAlways is a type that is opted into for recomputation each pass of stabilization.

type IBindChange 

type IBindChange interface {
	RightScopeNodes() []INode
}

IBindChange holds the methods specific to the bind-lhs-change node.

type IBindMain 

type IBindMain interface {
	IParents
	Invalidate()
}

IBindMain holds the methods specific to the bind main node.

type ICutoff 

type ICutoff interface {
	Cutoff(context.Context) (bool, error)
}

ICutoff is a type that determines if changes should continue to propagate past this node or not.

type IExpertGraph 

type IExpertGraph interface {
	// SetID sets the identifier for the [Graph].
	SetID(Identifier)

	// NumNodes returns the number of nodes the [Graph] is tracking.
	NumNodes() uint64

	// NumNodesRecomputed returns the number of nodes the [Graph] has
	// recomputed in its lifetime.
	NumNodesRecomputed() uint64

	// NumNodesChanged returns the number of nodes the [Graph] has
	// updated the value of in its lifetime.
	NumNodesChanged() uint64

	// NumObservers returns the current count of observers the [Graph] is tracking.
	NumObservers() uint64

	// StabilizationNum returns the current stabilization number of the [Graph].
	StabilizationNum() uint64

	// SetStabilizationNumber sets the current stabilization number, specifically
	// in situations where you're restoring graph state.
	SetStabilizationNum(uint64)

	// RecomputeHeapAdd directly adds a varadic array of nodes to the recompute heap.
	RecomputeHeapAdd(...INode)

	// RecomputeHeapLen returns the current length of the recompute heap.
	RecomputeHeapLen() int

	// RecomputeHeapIDs returns the node identifiers that are held in the recompute heap.
	//
	// This is useful when saving the state of a [Graph] to an external store.
	RecomputeHeapIDs() []Identifier

	// AddChild associates a child node to a parent.
	AddChild(child INode, parent INode) error
	// RemoveParent removes the association between a child and a parent.
	RemoveParent(child INode, parent INode)

	// ObserveNode implements the observe steps usually handled by [Observe] for custom nodes.
	ObserveNode(IObserver, INode) error

	// UnobserveNode implements the unobserve steps usually handled by observers.
	UnobserveNode(IObserver, INode)
}

IExpertGraph is an interface to allow you to manage internal fields of a graph (this is useful if you're deserializing the graph from a durable store).

Note there are no compatibility guarantees on this interface and you should use this interface at your own risk.

func ExpertGraph 

func ExpertGraph(g *Graph) IExpertGraph

ExpertGraph returns an "expert" interface to modify internal fields of the graph type.

Note there are no compatibility guarantees on this interface and you should use this interface at your own risk.

type IExpertNode 

type IExpertNode interface {
	CreatedIn() Scope
	SetCreatedIn(Scope)
	SetID(Identifier)

	Valid() bool
	SetValid(bool)

	Height() int
	SetHeight(int)

	HeightInRecomputeHeap() int
	SetHeightInRecomputeHeap(int)

	HeightInAdjustHeightsHeap() int
	SetHeightInAdjustHeightsHeap(int)

	ChangedAt() uint64
	SetChangedAt(uint64)
	SetAt() uint64
	SetSetAt(uint64)
	RecomputedAt() uint64
	SetRecomputedAt(uint64)

	NumRecomputes() uint64
	SetNumRecomputes(uint64)
	NumChanges() uint64
	SetNumChanges(uint64)

	IsNecessary() bool
	IsStale() bool
	IsInRecomputeHeap() bool

	Always() bool
	SetAlways(bool)

	Observer() bool
	SetObserver(bool)

	Children() []INode
	AddChildren(...INode)
	Parents() []INode
	AddParents(...INode)
	Observers() []IObserver
	AddObservers(...IObserver)
	RemoveChild(Identifier)
	RemoveParent(Identifier)
	RemoveObserver(Identifier)

	// ComputePseudoHeight walks the node graph up from a given node
	// computing the height of the node in-respect to its full graph.
	//
	// This is in contrast to how the node's height is calculated during
	// computation, which is only when it is linked or bound, and only
	// in respect to its immediate parents.
	//
	// This method is useful in advanced scenarios where you may be
	// rebuilding a graph from scratch dynamically.
	ComputePseudoHeight() int

	// Value returns the underlying value of the node
	// as an untyped `interface{}` for use in debugging.
	Value() any
}

IExpertNode is an expert interface for nodes.

Note there are no compatibility guarantees on this interface and you should use this interface at your own risk.

func ExpertNode 

func ExpertNode(in INode) IExpertNode

ExpertNode returns an "expert" interface to interact with nodes.

Note there are no compatibility guarantees on this interface and you should use this interface at your own risk.

type IExpertVar 

type IExpertVar[A any] interface {
	// SetInternalValue allows you to set the underlying value of a var
	// without marking it as stale.
	//
	// This can be useful when deserializing graphs from some other state.
	SetInternalValue(A)
}

IExpertVar are methods implemented by ExpertVar.

Note there are no compatibility guarantees on this interface and you should use this interface at your own risk.

func ExpertVar 

func ExpertVar[A any](v VarIncr[A]) IExpertVar[A]

ExpertVar returns an "expert" version of a var node.

Note there are no compatibility guarantees on this interface and you should use this interface at your own risk.

type INode 

type INode interface {
	// INode returns the underlying node metadata
	// for a given incremental node.
	Node() *Node
}

INode is a node in the incremental graph.

type IObserver 

type IObserver interface {
	INode

	// Unobserve effectively removes a given node from the observed ref count for a graph.
	//
	// As well, it unlinks the observer from its parent nodes, and as a result
	// you should _not_ re-use the node.
	//
	// To observe parts of a graph again, use the `MustObserve(...)` helper.
	Unobserve(context.Context)
}

IObserver is an INode that can be unobserved.

type IParents 

type IParents interface {
	// Parents provides a list of nodes that this node takes as inputs
	// for propagation of changes and dependency tracking.
	Parents() []INode
}

IParents is a type that has parents or inputs.

This list is used to link the node into the graph but also to reconstruct the links if the node becomes unnecessary, and then necessary again after construction.

type ISentinel added in v1.1.0 

type ISentinel interface {
	INode
	Unwatch(context.Context)
}

ISentinel is a node that manages the staleness of a target node based on a predicate and can mark that target node for recomputation.

type IShouldBeInvalidated 

type IShouldBeInvalidated interface {
	ShouldBeInvalidated() bool
}

IShouldBeInvalidateds a type that determines if a node should be invalidated or not.

type IStabilize 

type IStabilize interface {
	Stabilize(context.Context) error
}

IStabilize is a type that can be stabilized.

type IStale 

type IStale interface {
	Stale() bool
}

IStale is a type that determines if it is stale or not.

type Identifier 

type Identifier [16]byte

Identifier is a unique id.

Create a new identifier with NewIdentifier.

func MustParseIdentifier 

func MustParseIdentifier(raw string) (output Identifier)

MustParseIdentifier is the reverse of `.String()` that will panic if an error is returned by `ParseIdentifier`.

func NewIdentifier 

func NewIdentifier() (output Identifier)

NewIdentifier returns a new identifier.

Currently the underlying data looks like a uuidv4 but that shouldn't be relied upon.

By default NewIdentifier uses crypto/rand to generate the random data for the identifier in a rotating buffer, which yields decent performance and uniqueness guarantees.

If performance is still bottlenecked on creating identifiers for nodes you can swap out the algorithm for generating ids with SetIdentifierProvider.

func ParseIdentifier 

func ParseIdentifier(raw string) (output Identifier, err error)

ParseIdentifier is the reverse of `.String()`.

func (Identifier) IsZero 

func (id Identifier) IsZero() bool

IsZero returns if the identifier is unset.

func (Identifier) MarshalJSON 

func (id Identifier) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

func (Identifier) Short 

func (id Identifier) Short() string

Short returns the short hex representation of the id.

In practice this is the last ~8 bytes of the identifier.

func (Identifier) String 

func (id Identifier) String() string

String returns the full hex representation of the id.

func (*Identifier) UnmarshalJSON 

func (id *Identifier) UnmarshalJSON(data []byte) error

UnmarshalJSON implements json.Unmarshaler.

type Incr 

type Incr[T any] interface {
	INode
	// Value returns the stabilized value of the node.
	//
	// In practice you do not want to access this value
	// directly, you almost always want to associate this
	// value with a node as an input, and use the value
	// as resolved through a map or bind function.
	Value() T
}

Incr is a type that can be an incremental node in a computation graph.

func Always 

func Always[A any](scope Scope, input Incr[A]) Incr[A]

Always returns an incremental that is always stale and whose children will always be marked for recomputation.

The Always node will pass through the input incremental value to the nodes that take the Always node as an input.

An example use case for Always might be something like: 

g := incr.New()
v := incr.Var(g, "hello")
mv := incr.Map(g, v, func(vv string) string { return "not-" + v })
a := incr.Always(g, mv)
var counter int
mva := incr.Map(g, a, func(vv string) string { counter++; return vv })
_ = g.Stabilize(context.TODO())

In the above example, each time we call Graph.Stabilize we'll increment the counter.

func Cutoff 

func Cutoff[A any](bs Scope, i Incr[A], fn CutoffFunc[A]) Incr[A]

Cutoff returns a new wrapping cutoff incremental.

The goal of the cutoff incremental is to stop recomputation at a given node if the difference between the previous and latest values are not significant enough to warrant a full recomputation of the children of this node.

func Cutoff2 

func Cutoff2[A, B any](bs Scope, epsilon Incr[A], input Incr[B], fn Cutoff2Func[A, B]) Incr[B]

Cutoff2 returns a new cutoff incremental that takes an epsilon input.

func Cutoff2Context 

func Cutoff2Context[A, B any](bs Scope, epsilon Incr[A], input Incr[B], fn Cutoff2ContextFunc[A, B]) Incr[B]

Cutoff2Context returns a new cutoff incremental that takes an epsilon input.

The goal of the cutoff incremental is to stop recomputation at a given node if the difference between the previous and latest values are not significant enough to warrant a full recomputation of the children of this node.

func CutoffContext 

func CutoffContext[A any](bs Scope, i Incr[A], fn CutoffContextFunc[A]) Incr[A]

CutoffContext returns a new wrapping cutoff incremental.

The goal of the cutoff incremental is to stop recomputation at a given node if the difference between the previous and latest values are not significant enough to warrant a full recomputation of the children of this node.

func Freeze 

func Freeze[A any](scope Scope, i Incr[A]) Incr[A]

Freeze yields an incremental that takes the value of an input incremental on the first stabilization and doesn't change thereafter.

Stabilization propagates through this node even after the first stabilization.

func Func 

func Func[T any](scope Scope, fn func(context.Context) (T, error)) Incr[T]

Func wraps a given function as an incremental.

The result of the function after the first stabilization will be re-used between stabilizations unless you mark the node stale with the `SetStale` function on the `Graph` type.

Because there is no tracking of input changes, this node type is generally discouraged in favor of `Map` or `Bind` incrementals but is included for "expert" use cases, typically as an input to other nodes.

func Map 

func Map[A, B any](scope Scope, a Incr[A], fn func(A) B) Incr[B]

Map applies a function to a given input incremental and returns a new incremental of the output type of that function.

func Map2 

func Map2[A, B, C any](scope Scope, a Incr[A], b Incr[B], fn func(A, B) C) Incr[C]

Map2 applies a function to a given input incremental and returns a new incremental of the output type of that function.

func Map2Context 

func Map2Context[A, B, C any](scope Scope, a Incr[A], b Incr[B], fn func(context.Context, A, B) (C, error)) Incr[C]

Map2Context applies a function that accepts a context and returns an error, to a given input incremental and returns a new incremental of the output type of that function.

func Map3 

func Map3[A, B, C, D any](scope Scope, a Incr[A], b Incr[B], c Incr[C], fn func(A, B, C) D) Incr[D]

Map3 applies a function to given input incrementals and returns a new incremental of the output type of that function.

func Map3Context 

func Map3Context[A, B, C, D any](scope Scope, a Incr[A], b Incr[B], c Incr[C], fn func(context.Context, A, B, C) (D, error)) Incr[D]

Map3Context applies a function that accepts a context and returns an error, to given input incrementals and returns a new incremental of the output type of that function.

func Map4 

func Map4[A, B, C, D, E any](scope Scope, a Incr[A], b Incr[B], c Incr[C], d Incr[D], fn func(A, B, C, D) E) Incr[E]

Map4 applies a function to given input incrementals and returns a new incremental of the output type of that function.

func Map4Context 

func Map4Context[A, B, C, D, E any](scope Scope, a Incr[A], b Incr[B], c Incr[C], d Incr[D], fn func(context.Context, A, B, C, D) (E, error)) Incr[E]

Map4Context applies a function that accepts a context and returns an error, to given input incrementals and returns a new incremental of the output type of that function.

func MapContext 

func MapContext[A, B any](scope Scope, a Incr[A], fn func(context.Context, A) (B, error)) Incr[B]

MapContext applies a function to a given input incremental and returns a new incremental of the output type of that function but is context aware and can also return an error, aborting stabilization.

func MapIf 

func MapIf[A any](scope Scope, a, b Incr[A], p Incr[bool]) Incr[A]

MapIf returns an incremental that yields one of two values based on the boolean condition returned from a third.

Specifically, we term this _Apply_If because the nodes are all linked in the graph, but the value changes during stabilization.

func Return 

func Return[A any](scope Scope, v A) Incr[A]

Return yields a constant incremental for a given value.

Note that it does not implement IStabilize and is effectively always the same value, and never causes recomputations.

func Timer 

func Timer[A any](scope Scope, input Incr[A], every time.Duration) Incr[A]

Timer returns a special node type that fires if a given duration has elapsed since it last stabilized.

When it stabilizes, it assumes the value of the input node, and causes any children (i.e. nodes that take the timer as input) to recompute if this is the first stabilization or if the timer has elapsed.

type MapNContextFunc 

type MapNContextFunc[A, B any] func(context.Context, ...A) (B, error)

MapNContextFunc is the function that the MapNContext incremental applies.

type MapNFunc 

type MapNFunc[A, B any] func(...A) B

MapNFunc is the function that the MapN incremental applies.

type MapNIncr 

type MapNIncr[A, B any] interface {
	Incr[B]
	AddInput(Incr[A]) error
}

MapNIncr is a type of incremental that can add inputs over time.

func MapN 

func MapN[A, B any](scope Scope, fn MapNFunc[A, B], inputs ...Incr[A]) MapNIncr[A, B]

MapN applies a function to given list of input incrementals and returns a new incremental of the output type of that function.

func MapNContext 

func MapNContext[A, B any](scope Scope, fn MapNContextFunc[A, B], inputs ...Incr[A]) MapNIncr[A, B]

MapNContext applies a function to given list of input incrementals and returns a new incremental of the output type of that function.

type Node 

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

Node is the common metadata for any node in the computation graph.

func NewNode 

func NewNode(kind string) *Node

NewNode returns a new node.

func (*Node) ID 

func (n *Node) ID() Identifier

ID returns a unique identifier for the node.

func (*Node) Kind 

func (n *Node) Kind() string

Kind returns the meta type of the node.

func (*Node) Label 

func (n *Node) Label() string

Label returns a descriptive label for the node or an empty string if one hasn't been provided.

func (*Node) Metadata 

func (n *Node) Metadata() any

Metadata returns user assignable metadata.

func (*Node) OnError 

func (n *Node) OnError(fn func(context.Context, error))

OnError registers an error handler.

An error handler is called when the stabilize or cutoff function for this node returns an error.

func (*Node) OnUpdate 

func (n *Node) OnUpdate(fn func(context.Context))

OnUpdate registers an update handler.

An update handler is called when this node is recomputed.

func (*Node) SetKind 

func (n *Node) SetKind(kind string)

SetMetadata sets the metadata on the node.

func (*Node) SetLabel 

func (n *Node) SetLabel(label string)

SetLabel sets the descriptive label on the node.

func (*Node) SetMetadata 

func (n *Node) SetMetadata(md any)

SetMetadata sets the metadata on the node.

func (*Node) String 

func (n *Node) String() string

String returns a string form of the node metadata.

type ObserveIncr 

type ObserveIncr[A any] interface {
	IObserver
	// OnUpdate lets you register an update handler for the observer node.
	//
	// This handler is called when the observed node is recomputed. It is
	// passed the value of the observed node post-stabilization.
	//
	// If the stabilization is "serial" all update handlers that are registered
	// will also be called serially, conversely if the stabilization is "paralllel"
	// all update handlers will be called in parallel using the graph worker pool.
	OnUpdate(func(context.Context, A))
	// Value returns the observed node value.
	Value() A
}

ObserveIncr is an incremental that observes a graph of incrementals starting a given input.

func MustObserve 

func MustObserve[A any](g *Graph, observed Incr[A]) ObserveIncr[A]

MustObserve observes a node, specifically including it for computation as well as all of its parents.

If this detects a cycle or any other issue a panic will be raised.

func Observe 

func Observe[A any](g *Graph, observed Incr[A]) (ObserveIncr[A], error)

Observe observes a node, specifically including it for computation as well as all of its parents.

type Scope 

type Scope interface {
	fmt.Stringer
	// contains filtered or unexported methods
}

Scope is a type that's used to track which nodes are created by which "areas" of the graph.

When in doubt, if you see a scope argument you should pass the Graph itself.

If you're within a bind, you should pass the scope that is passed to your bind function.

type SentinelIncr added in v1.1.0 

type SentinelIncr interface {
	IAlways
	ICutoff
	IStale
	ISentinel
}

SentinelIncr is a node that is recomputed always, but can cutoff the computation based on the result of a provided deligate.

func Sentinel added in v1.1.0 

func Sentinel(scope Scope, fn func() bool, watched INode) SentinelIncr

Sentinel returns a node that evaluates a staleness function for each stabilization.

The provided predicate should return true if we should recompute the watched node. Returning false will stop recomputation from propagating past this node, specifically skipping the watched node and its children. Conversely, if the predicate returns true the watched node will be recomputed.

You can attach sentinels to parts of a graph to automatically recompute nodes on the result of a function withouth having to mark those nodes explicitly stale. Sentinels are somewhat expensive as a result, and should only be used sparingly, and even then only in situations where the stalness function will return true infequently.

func SentinelContext added in v1.1.0 

func SentinelContext(scope Scope, fn func(context.Context) (bool, error), watched INode) SentinelIncr

SentinelContext returns a node that evaluates a staleness function for each stabilization, similar to Sentinel, except that the predicate is passed the stabilization context and can return an error.

type Tracer 

type Tracer interface {
	Print(...any)
	Error(...any)
}

Tracer is a type that can implement a tracer.

func GetTracer 

func GetTracer(ctx context.Context) Tracer

GetTracer returns the tracer from a given context, and nil if one is not present.

type VarIncr 

type VarIncr[T any] interface {
	Incr[T]

	// Set sets the var value.
	//
	// Calling [Set] will invalidate any nodes that reference this variable.
	Set(T)
}

VarIncr is a graph node type that implements an incremental variable.

func Var 

func Var[T any](scope Scope, t T) VarIncr[T]

Var returns a new var node.

Var nodes are special nodes in incremental as they let you input data into a computation, and specifically change data between stabilization passes.

Var nodes include a method [Var.Set] that let you update the value after the initial construction. Calling [Var.Set] will mark the Var node stale, as well any of the nodes that take the Var node as an input (i.e. the Var node's children).

type WatchIncr 

type WatchIncr[A any] interface {
	Incr[A]

	// Reset empties the tracked values.
	Reset()

	// Values returns the input incremental values the [Watch] node
	// has seen through stabilization passes. This array of values will
	// continue to grow until you call [Reset] on the node.
	Values() []A
}

WatchIncr is a type that implements the watch interface.

func Watch 

func Watch[A any](scope Scope, i Incr[A]) WatchIncr[A]

Watch returns a new watch incremental that tracks values for a given incremental each time it stabilizes.

Source Files

View all Source files

Directories

Path Synopsis
examples
basic
benchmark
blaze
custom_node
diagram
integration
naive
orders
streaming
Package incrutil provides helper types above what is already provided in incr.
 Package incrutil provides helper types above what is already provided in incr.
mapi
package mapi provides helper incrementals for working with maps.
 package mapi provides helper incrementals for working with maps.
naive
package naive provides basic implementations of incremental primitives to test what a "baseline" implementation of a DAG would perform like _before_ you add incremental.
 package naive provides basic implementations of incremental primitives to test what a "baseline" implementation of a DAG would perform like _before_ you add incremental.
slicei

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.