Documentation
¶
Overview ¶
This package provides functional utilities for traversing and transforming LD nodes.
The traversal.Path type provides a description of how to perform several steps across a Node tree. These are dual purpose: Paths can be used as instructions to do some traversal, and Paths are accumulated during traversals as a log of progress.
"Focus" functions provide syntactic sugar for using ld.Path to jump to a Node deep in a tree of other Nodes.
"FocusedTransform" functions can do the same such deep jumps, and support mutation as well! (Of course, since ld.Node is an immutable interface, more precisely speaking, "transformations" are implemented rebuilding trees of nodes to emulate mutation in a copy-on-write way.)
"Walk" functions perform a walk of a Node graph, and apply visitor functions multiple Nodes. The more advanced Walk functions can be guided by Selectors, which provide a declarative mechanism for guiding the traversal and filtering which Nodes are of interest. (See the selector sub-package for more detail.)
"WalkTransforming" is similar to Traverse, but with support for mutations. Like "FocusTransform", "WalkTransforming" operates in a copy-on-write way.
All of these functions -- the "Focus*" and "Walk*" family alike -- work via callbacks: they do the traversal, and call a user-provided function with a handle to the reached Node. Further "Focus" and "Walk" can be used recursively within this callback.
All of these functions -- the "Focus*" and "Walk*" family alike -- include support for automatic resolution and loading of new Node trees whenever LD Links are encountered. This can be configured freely by providing LinkLoader interfaces to the traversal.Config.
Some notes on the limits of usage:
The "*Transform" family of methods is most appropriate for patterns of usage which resemble point mutations. More general transformations -- zygohylohistomorphisms, etc -- will be best implemented by composing the read-only systems (e.g. Focus, Traverse) and handling the accumulation in the visitor functions.
(Why? The "point mutation" use-case gets core library support because it's both high utility and highly clear how to implement it. More advanced transformations are nontrivial to provide generalized support for, for three reasons: efficiency is hard; not all existing research into categorical recursion schemes is necessarily applicable without modification (efficient behavior in a merkle-tree context is not the same as efficient behavior on uniform memory!); and we have the further compounding complexity of the range of choices available for underlying Node implementation. Therefore, attempts at generalization are not included here; handling these issues in concrete cases is easy, so we call it an application logic concern. However, exploring categorical recursion schemes as a library is encouraged!)
Index ¶
- func Focus(n ld.Node, p ld.Path, fn VisitFn) error
- func FocusedTransform(n ld.Node, p ld.Path, fn TransformFn, createParents bool) (ld.Node, error)
- func Get(n ld.Node, p ld.Path) (ld.Node, error)
- func SelectLinks(n ld.Node) ([]ld.Link, error)
- func WalkAdv(n ld.Node, s selector.Selector, fn AdvVisitFn) error
- func WalkMatching(n ld.Node, s selector.Selector, fn VisitFn) error
- func WalkTransforming(n ld.Node, s selector.Selector, fn TransformFn) (ld.Node, error)
- type AdvVisitFn
- type Config
- type LinkTargetNodePrototypeChooser
- type Progress
- func (prog Progress) Focus(n ld.Node, p ld.Path, fn VisitFn) error
- func (prog Progress) FocusedTransform(n ld.Node, p ld.Path, fn TransformFn, createParents bool) (ld.Node, error)
- func (prog Progress) Get(n ld.Node, p ld.Path) (ld.Node, error)
- func (prog Progress) WalkAdv(n ld.Node, s selector.Selector, fn AdvVisitFn) error
- func (prog Progress) WalkMatching(n ld.Node, s selector.Selector, fn VisitFn) error
- func (prog Progress) WalkTransforming(n ld.Node, s selector.Selector, fn TransformFn) (ld.Node, error)
- type SkipMe
- type TransformFn
- type VisitFn
- type VisitReason
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Focus ¶
Focus traverses a Node graph according to a path, reaches a single Node, and calls the given VisitFn on that reached node.
This function is a helper function which starts a new traversal with default configuration. It cannot cross links automatically (since this requires configuration). Use the equivalent Focus function on the Progress structure for more advanced and configurable walks.
func FocusedTransform ¶
FocusedTransform traverses an ld.Node graph, reaches a single Node, and calls the given TransformFn to decide what new node to replace the visited node with. A new Node tree will be returned (the original is unchanged).
This function is a helper function which starts a new traversal with default configuration. It cannot cross links automatically (since this requires configuration). Use the equivalent FocusedTransform function on the Progress structure for more advanced and configurable walks.
func Get ¶
Get is the equivalent of Focus, but returns the reached node (rather than invoking a callback at the target), and does not yield Progress information.
This function is a helper function which starts a new traversal with default configuration. It cannot cross links automatically (since this requires configuration). Use the equivalent Get function on the Progress structure for more advanced and configurable walks.
func SelectLinks ¶
func SelectLinks(n ld.Node) ([]ld.Link, error)
SelectLinks walks a Node tree and returns a slice of all Links encountered. SelectLinks will recurse down into any maps and lists, but does not attempt to load any of the links it encounters nor recurse further through them (in other words, it's confined to one "block").
SelectLinks only returns the list of links; it does not return any other information about them such as position in the tree, etc.
An error may be returned if any of the nodes returns errors during iteration; this is generally only possible if one of the Nodes is an ADL, and unable to be fully walked because of the inability to load or process some data inside the ADL. Nodes already fully in memory should not encounter such errors, and it should be safe to ignore errors from this method when used in that situation. In case of an error, a partial list will still be returned.
If an identical link is found several times during the walk, it is reported several times in the resulting list; no deduplication is performed by this method.
func WalkAdv ¶
WalkAdv is identical to WalkMatching, except it is called for *all* nodes visited (not just matching nodes), together with the reason for the visit. An AdvVisitFn is used instead of a VisitFn, so that the reason can be provided.
This function is a helper function which starts a new walk with default configuration. It cannot cross links automatically (since this requires configuration). Use the equivalent WalkAdv function on the Progress structure for more advanced and configurable walks.
func WalkMatching ¶
WalkMatching walks a graph of Nodes, deciding which to visit by applying a Selector, and calling the given VisitFn on those that the Selector deems a match.
This function is a helper function which starts a new walk with default configuration. It cannot cross links automatically (since this requires configuration). Use the equivalent WalkMatching function on the Progress structure for more advanced and configurable walks.
func WalkTransforming ¶
WalkTransforming walks a graph of Nodes, deciding which to alter by applying a Selector, and calls the given TransformFn to decide what new node to replace the visited node with. A new Node tree will be returned (the original is unchanged).
This function is a helper function which starts a new walk with default configuration. It cannot cross links automatically (since this requires configuration). Use the equivalent WalkTransforming function on the Progress structure for more advanced and configurable walks.
Types ¶
type AdvVisitFn ¶
type AdvVisitFn func(Progress, ld.Node, VisitReason) error
AdvVisitFn is like VisitFn, but for use with AdvTraversal: it gets additional arguments describing *why* this node is visited.
type Config ¶
type Config struct {
Ctx context.Context // Context carried through a traversal. Optional; use it if you need cancellation.
LinkSystem ld.LinkSystem // LinkSystem used for automatic link loading, and also any storing if mutation features (e.g. traversal.Transform) are used.
LinkTargetNodePrototypeChooser LinkTargetNodePrototypeChooser // Chooser for Node implementations to produce during automatic link traversal.
}
type LinkTargetNodePrototypeChooser ¶
type LinkTargetNodePrototypeChooser func(ld.Link, ld.LinkContext) (ld.NodePrototype, error)
LinkTargetNodePrototypeChooser is a function that returns a NodePrototype based on the information in a Link and/or its LinkContext.
A LinkTargetNodePrototypeChooser can be used in a traversal.Config to be clear about what kind of Node implementation to use when loading a Link. In a simple example, it could constantly return a `basicnode.Prototype__Any{}`. In a more complex example, a program using `bind` over native Go types could decide what kind of native type is expected, and return a `bind.NodeBuilder` for that specific concrete native type.
type Progress ¶
type Progress struct {
Cfg *Config
Path ld.Path // Path is how we reached the current point in the traversal.
LastBlock struct {
Path ld.Path
Link ld.Link
}
}
func (Progress) Focus ¶
Focus traverses a Node graph according to a path, reaches a single Node, and calls the given VisitFn on that reached node.
Focus is a read-only traversal. See FocusedTransform if looking for a way to do an "update" to a Node.
Provide configuration to this process using the Config field in the Progress object.
This walk will automatically cross links, but requires some configuration with link loading functions to do so.
Focus (and the other traversal functions) can be used again again inside the VisitFn! By using the traversal.Progress handed to the VisitFn, the Path recorded of the traversal so far will continue to be extended, and thus continued nested uses of Walk and Focus will see the fully contextualized Path.
func (Progress) FocusedTransform ¶
func (prog Progress) FocusedTransform(n ld.Node, p ld.Path, fn TransformFn, createParents bool) (ld.Node, error)
FocusedTransform traverses an ld.Node graph, reaches a single Node, and calls the given TransformFn to decide what new node to replace the visited node with. A new Node tree will be returned (the original is unchanged).
If the TransformFn returns the same Node which it was called with, then the transform is a no-op, and the Node returned from the FocusedTransform call as a whole will also be the same as its starting Node.
Otherwise, the reached node will be "replaced" with the new Node -- meaning that new intermediate nodes will be constructed to also replace each parent Node that was traversed to get here, thus propagating the changes in a copy-on-write fashion -- and the FocusedTransform function as a whole will return a new Node containing identical children except for those replaced.
FocusedTransform can be used again inside the applied function! This kind of composition can be useful for doing batches of updates. E.g. if have a large Node graph which contains a 100-element list, and you want to replace elements 12, 32, and 95 of that list: then you should FocusedTransform to the list first, and inside that TransformFn's body, you can replace the entire list with a new one that is composed of copies of everything but those elements -- including using more TransformFn calls as desired to produce the replacement elements if it so happens that those replacement elements are easiest to construct by regarding them as incremental updates to the previous values. (This approach can also be used when doing other modifications like insertion or reordering -- which would otherwise be tricky to define, since each operation could change the meaning of subsequently used indexes.)
As a special case, list appending is supported by using the path segment "-". (This is determined by the node it applies to -- if that path segment is applied to a map, it's just a regular map key of the string of dash.)
Note that anything you can do with the Transform function, you can also do with regular Node and NodeBuilder usage directly. Transform just does a large amount of the intermediate bookkeeping that's useful when creating new values which are partial updates to existing values.
func (Progress) Get ¶
Get is the equivalent of Focus, but returns the reached node (rather than invoking a callback at the target), and does not yield Progress information.
Provide configuration to this process using the Config field in the Progress object.
This walk will automatically cross links, but requires some configuration with link loading functions to do so.
If doing several traversals which are nested, consider using the Focus funcion in preference to Get; the Focus functions provide updated Progress objects which can be used to do nested traversals while keeping consistent track of progress, such that continued nested uses of Walk or Focus or Get will see the fully contextualized Path.
func (Progress) WalkAdv ¶
WalkAdv is identical to WalkMatching, except it is called for *all* nodes visited (not just matching nodes), together with the reason for the visit. An AdvVisitFn is used instead of a VisitFn, so that the reason can be provided.
func (Progress) WalkMatching ¶
WalkMatching walks a graph of Nodes, deciding which to visit by applying a Selector, and calling the given VisitFn on those that the Selector deems a match.
WalkMatching is a read-only traversal. See WalkTransforming if looking for a way to do "updates" to a tree of nodes.
Provide configuration to this process using the Config field in the Progress object.
This walk will automatically cross links, but requires some configuration with link loading functions to do so.
Traversals are defined as visiting a (node,path) tuple. This is important to note because when walking DAGs with Links, it means you may visit the same node multiple times due to having reached it via a different path. (You can prevent this by using a LinkLoader function which memoizes a set of already-visited Links, and returns a SkipMe when encountering them again.)
WalkMatching (and the other traversal functions) can be used again again inside the VisitFn! By using the traversal.Progress handed to the VisitFn, the Path recorded of the traversal so far will continue to be extended, and thus continued nested uses of Walk and Focus will see the fully contextualized Path.
func (Progress) WalkTransforming ¶
func (prog Progress) WalkTransforming(n ld.Node, s selector.Selector, fn TransformFn) (ld.Node, error)
WalkTransforming walks a graph of Nodes, deciding which to alter by applying a Selector, and calls the given TransformFn to decide what new node to replace the visited node with. A new Node tree will be returned (the original is unchanged).
If the TransformFn returns the same Node which it was called with, then the transform is a no-op; if every visited node is a no-op, then the root node returned from the walk as a whole will also be the same as its starting Node (no new memory will be used).
When a Node is replaced, no further recursion of this walk will occur on its contents. (You can certainly do a additional traversals, including transforms, from inside the TransformFn while building the replacement node.)
The prototype (that is, implementation) of Node returned will be the same as the prototype of the Nodes at the same positions in the existing tree (literally, builders used to construct any new needed intermediate nodes are chosen by asking the existing nodes about their prototype).
This feature is not yet implemented.
type SkipMe ¶
type SkipMe struct{}
SkipMe is a signalling "error" which can be used to tell traverse to skip some data.
SkipMe can be returned by the Config.LinkLoader to skip entire blocks without aborting the walk. (This can be useful if you know you don't have data on hand, but want to continue the walk in other areas anyway; or, if you're doing a way where you know that it's valid to memoize seen areas based on Link alone.)
type TransformFn ¶
TransformFn is like a visitor that can also return a new Node to replace the visited one.
type VisitReason ¶
type VisitReason byte
VisitReason provides additional information to traversals using AdvVisitFn.
const ( VisitReason_SelectionMatch VisitReason = 'm' // Tells AdvVisitFn that this node was explicitly selected. (This is the set of nodes that VisitFn is called for.) VisitReason_SelectionParent VisitReason = 'p' // Tells AdvVisitFn that this node is a parent of one that will be explicitly selected. (These calls only happen if the feature is enabled -- enabling parent detection requires a different algorithm and adds some overhead.) VisitReason_SelectionCandidate VisitReason = 'x' // Tells AdvVisitFn that this node was visited while searching for selection matches. It is not necessarily implied that any explicit match will be a child of this node; only that we had to consider it. (Merkle-proofs generally need to include any node in this group.) )
Source Files
Directories