traversal

package
v0.6.1 Latest Latest
Warning

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

Go to latest
Published: Aug 12, 2020 License: MIT Imports: 6 Imported by: 1

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

Constants

This section is empty.

Variables

This section is empty.

Functions

func Focus

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

Focus is a shortcut for kicking off traversal.Progress.Focus with an empty initial state (e.g. the Node given here is the "root" node of your operation).

func FocusedTransform

func FocusedTransform(n ipld.Node, p ipld.Path, fn TransformFn) (ipld.Node, error)

FocusedTransform is a shortcut for kicking off traversal.Progress.FocusedTransform with an empty initial state (e.g. the Node given here is the "root" node of your operation).

func WalkAdv

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

func WalkMatching

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

func WalkTransforming

func WalkTransforming(n ipld.Node, s selector.Selector, fn TransformFn) (ipld.Node, error)

Types

type AdvVisitFn

type AdvVisitFn func(Progress, ipld.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.
	LinkLoader             ipld.Loader        // Loader used for automatic link traversal.
	LinkNodeBuilderChooser NodeBuilderChooser // Chooser for Node implementations to produce during automatic link traversal.
	LinkStorer             ipld.Storer        // Storer used if any mutation features (e.g. traversal.Transform) are used.
}

type NodeBuilderChooser

type NodeBuilderChooser func(ipld.Link, ipld.LinkContext) ipld.NodeBuilder

NodeBuilderChooser is a function that returns a NodeBuilder based on the information in a Link its LinkContext.

A NodeBuilderChooser 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 an `ipldfree.NodeBuilder`. 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      ipld.Path // Path is how we reached the current point in the traversal.
	LastBlock struct {
		Path ipld.Path
		Link ipld.Link
	}
}

func (Progress) Focus

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

Focus traverses an ipld.Node graph, reaches a single Node, and applies a function to the reached node.

Focus is a read-only traversal. See FocusedTransform if looking for a way to do an "update" to a Node.

Focus can be used again again inside the applied 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 Focus will see a fully contextualized Path.

func (Progress) FocusedTransform

func (prog Progress) FocusedTransform(n ipld.Node, p ipld.Path, fn TransformFn) (ipld.Node, error)

FocusedTransform traverses an ipld.Node graph, reaches a single Node, and applies a function to the reached node which make return a new Node.

If the TransformFn returns a Node which is the same as the original reached node, 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.

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

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

func (Progress) WalkMatching

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

func (Progress) WalkTransforming

func (prog Progress) WalkTransforming(n ipld.Node, s selector.Selector, fn TransformFn) (ipld.Node, error)

type TransformFn

type TransformFn func(Progress, ipld.Node) (ipld.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, ipld.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.)
)

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL