traversal

Documentation

Overview

This package provides functional utilities for traversing and transforming IPLD 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 ipld.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 ipld.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 IPLD 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 datamodel.Node, p datamodel.Path, fn VisitFn) error
• func FocusedTransform(n datamodel.Node, p datamodel.Path, fn TransformFn, createParents bool) (datamodel.Node, error)
• func Get(n datamodel.Node, p datamodel.Path) (datamodel.Node, error)
• func SelectLinks(n datamodel.Node) ([]datamodel.Link, error)
• func WalkAdv(n datamodel.Node, s selector.Selector, fn AdvVisitFn) error
• func WalkLocal(n datamodel.Node, fn VisitFn) error
• func WalkMatching(n datamodel.Node, s selector.Selector, fn VisitFn) error
• func WalkTransforming(n datamodel.Node, s selector.Selector, fn TransformFn) (datamodel.Node, error)
• type AdvVisitFn
• type Budget
• type Config
• type ErrBudgetExceeded
  • func (e *ErrBudgetExceeded) Error() string
• type LinkTargetNodePrototypeChooser
• type Progress
  • func (prog Progress) Focus(n datamodel.Node, p datamodel.Path, fn VisitFn) error
  • func (prog Progress) FocusedTransform(n datamodel.Node, p datamodel.Path, fn TransformFn, createParents bool) (datamodel.Node, error)
  • func (prog Progress) Get(n datamodel.Node, p datamodel.Path) (datamodel.Node, error)
  • func (prog Progress) WalkAdv(n datamodel.Node, s selector.Selector, fn AdvVisitFn) error
  • func (prog Progress) WalkLocal(n datamodel.Node, fn VisitFn) error
  • func (prog Progress) WalkMatching(n datamodel.Node, s selector.Selector, fn VisitFn) error
  • func (prog Progress) WalkTransforming(n datamodel.Node, s selector.Selector, fn TransformFn) (datamodel.Node, error)
• type SkipMe
  • func (SkipMe) Error() string
• type TransformFn
• type VisitFn
• type VisitReason

Functions

func Focus

func Focus(n datamodel.Node, p datamodel.Path, fn VisitFn) error

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

func FocusedTransform(n datamodel.Node, p datamodel.Path, fn TransformFn, createParents bool) (datamodel.Node, error)

FocusedTransform traverses a datamodel.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

func Get(n datamodel.Node, p datamodel.Path) (datamodel.Node, error)

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 datamodel.Node) ([]datamodel.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

func WalkAdv(n datamodel.Node, s selector.Selector, fn AdvVisitFn) error

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 WalkLocal

func WalkLocal(n datamodel.Node, fn VisitFn) error

WalkLocal walks a tree of Nodes, visiting each of them, and calling the given VisitFn on all of them; it does not traverse any links.

WalkLocal can skip subtrees if the VisitFn returns SkipMe, but lacks any other options for controlling or directing the visit; consider using some of the various Walk functions with Selector parameters if you want more control.

func WalkMatching

func WalkMatching(n datamodel.Node, s selector.Selector, fn VisitFn) error

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

func WalkTransforming(n datamodel.Node, s selector.Selector, fn TransformFn) (datamodel.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).

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, datamodel.Node, VisitReason) error

AdvVisitFn is like VisitFn, but for use with AdvTraversal: it gets additional arguments describing *why* this node is visited.

type Budget

type Budget struct {
	NodeBudget int64 // A monotonically-decrementing "budget" for how many more nodes we're willing to visit before halting.
	LinkBudget int64 // A monotonically-decrementing "budget" for how many more links we're willing to load before halting.  (This is not aware of any caching; it's purely in terms of links encountered and traversed.)
}

type Config

type Config struct {
	Ctx                            context.Context                // Context carried through a traversal.  Optional; use it if you need cancellation.
	LinkSystem                     linking.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.
	LinkVisitOnlyOnce              bool                           // By default, we visit across links wherever we see them again, even if we've visited them before, because the reason for visiting might be different than it was before since we got to it via a different path.  If set to true, track links we've seen before in Progress.SeenLinks and do not visit them again.  Note that sufficiently complex selectors may require valid revisiting of some links, so setting this to true can change behavior noticably and should be done with care.
	StartAtPath                    datamodel.Path                 // If set, causes a traversal to skip forward until passing this path, and only then begins calling visit functions.  Block loads will also be skipped wherever possible.
}

type ErrBudgetExceeded

type ErrBudgetExceeded struct {
	BudgetKind string // "node"|"link"
	Path       datamodel.Path
	Link       datamodel.Link // only present if BudgetKind=="link"
}

func (*ErrBudgetExceeded) Error

func (e *ErrBudgetExceeded) Error() string

type LinkTargetNodePrototypeChooser

type LinkTargetNodePrototypeChooser func(datamodel.Link, linking.LinkContext) (datamodel.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      datamodel.Path // Path is how we reached the current point in the traversal.
	LastBlock struct {
		Path datamodel.Path
		Link datamodel.Link
	}
	PastStartAtPath bool                        // Indicates whether the traversal has progressed passed the StartAtPath in the config -- use to avoid path checks when inside a sub portion of a DAG that is entirely inside the "not-skipped" portion of a traversal
	Budget          *Budget                     // If present, tracks "budgets" for how many more steps we're willing to take before we should halt.
	SeenLinks       map[datamodel.Link]struct{} // Set used to remember which links have been visited before, if Cfg.LinkVisitOnlyOnce is true.
}

func (Progress) Focus

func (prog Progress) Focus(n datamodel.Node, p datamodel.Path, fn VisitFn) error

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 datamodel.Node, p datamodel.Path, fn TransformFn, createParents bool) (datamodel.Node, error)

FocusedTransform traverses a datamodel.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.

Returning nil from the TransformFn as the replacement node means "remove this".

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

func (prog Progress) Get(n datamodel.Node, p datamodel.Path) (datamodel.Node, error)

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

func (prog Progress) WalkAdv(n datamodel.Node, s selector.Selector, fn AdvVisitFn) error

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) WalkLocal

func (prog Progress) WalkLocal(n datamodel.Node, fn VisitFn) error

WalkLocal is the same as the package-scope function of the same name, but considers an existing Progress state (and any config it might reference).

func (Progress) WalkMatching

func (prog Progress) WalkMatching(n datamodel.Node, s selector.Selector, fn VisitFn) error

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 datamodel.Node, s selector.Selector, fn TransformFn) (datamodel.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).

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.)

func (SkipMe) Error

func (SkipMe) Error() string

type TransformFn

type TransformFn func(Progress, datamodel.Node) (datamodel.Node, error)

TransformFn is like a visitor that can also return a new Node to replace the visited one.

type VisitFn

type VisitFn func(Progress, datamodel.Node) error

VisitFn is a read-only visitor.

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.)
)