package module
v0.6.0 Latest Latest

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

Go to latest
Published: Aug 28, 2023 License: MIT Imports: 6 Imported by: 926



Coverage Status Travis CI

go-ipld-format is a set of interfaces that a type needs to implement in order to be a part of the ipld merkle-forest.

Lead Maintainer

Eric Myhre

Table of Contents


make install


PRs are welcome!

Small note: If editing the Readme, please conform to the standard-readme specification.


MIT © Jeromy Johnson




This section is empty.


View Source
var EndOfDag = errors.New("end of DAG")

EndOfDag wraps the `errUpOnRoot` and signals to the user that the entire DAG has been iterated.

View Source
var ErrClosed = errors.New("error: batch closed")

ErrClosed is returned when operating on a batch that has already been closed.

View Source
var ErrDownNoChild = errors.New("can't go down, the child does not exist")

ErrDownNoChild signals there is no child at `ActiveChildIndex` in the `ActiveNode` to go down to.

View Source
var ErrNextNoChild = errors.New("can't go to the next child, no more child nodes in this parent")

ErrNextNoChild signals the end of this parent child nodes.

View Source
var ErrNilVisitor = errors.New("no Visitor function specified")

ErrNilVisitor signals the lack of a `Visitor` function.

View Source
var ErrNotCommited = errors.New("error: batch not commited")

ErrNotCommited is returned when closing a batch that hasn't been successfully committed.


func Copy

func Copy(ctx context.Context, from, to DAGService, root cid.Cid) error

func IsNotFound added in v0.1.0

func IsNotFound(err error) bool

IsNotFound returns if the given error is or wraps an ErrNotFound (equivalent to errors.Is(err, ErrNotFound{}))


type Batch

type Batch struct {
	// contains filtered or unexported fields

Batch is a buffer for batching adds to a dag.

func NewBatch

func NewBatch(ctx context.Context, na NodeAdder, opts ...BatchOption) *Batch

NewBatch returns a node buffer (Batch) that buffers nodes internally and commits them to the underlying DAGService in batches. Use this if you intend to add or remove a lot of nodes all at once.

If the passed context is canceled, any in-progress commits are aborted.

func (*Batch) Add

func (t *Batch) Add(ctx context.Context, nd Node) error

Add adds a node to the batch and commits the batch if necessary.

func (*Batch) AddMany

func (t *Batch) AddMany(ctx context.Context, nodes []Node) error

AddMany many calls Add for every given Node, thus batching and commiting them as needed.

func (*Batch) Commit

func (t *Batch) Commit() error

Commit commits batched nodes.

type BatchOption

type BatchOption func(o *batchOptions)

BatchOption provides a way of setting internal options of a Batch.

See this post about the "functional options" pattern:

func MaxNodesBatchOption

func MaxNodesBatchOption(num int) BatchOption

MaxNodesBatchOption sets the maximum number of buffered nodes before writing blocks.

func MaxSizeBatchOption

func MaxSizeBatchOption(size int) BatchOption

MaxSizeBatchOption sets the maximum amount of buffered data before writing blocks.

type BufferedDAG

type BufferedDAG struct {
	// contains filtered or unexported fields

BufferedDAG implements DAGService using a Batch NodeAdder to wrap add operations in the given DAGService. It will trigger Commit() before any non-Add operations, but otherwise calling Commit() is left to the user.

func NewBufferedDAG

func NewBufferedDAG(ctx context.Context, ds DAGService, opts ...BatchOption) *BufferedDAG

NewBufferedDAG creates a BufferedDAG using the given DAGService and the given options for the Batch NodeAdder.

func (*BufferedDAG) Add

func (bd *BufferedDAG) Add(ctx context.Context, n Node) error

Add adds a new node using Batch.

func (*BufferedDAG) AddMany

func (bd *BufferedDAG) AddMany(ctx context.Context, nds []Node) error

AddMany adds many nodes using Batch.

func (*BufferedDAG) Commit

func (bd *BufferedDAG) Commit() error

Commit calls commit on the Batch.

func (*BufferedDAG) Get

func (bd *BufferedDAG) Get(ctx context.Context, c cid.Cid) (Node, error)

Get commits and gets a node from the DAGService.

func (*BufferedDAG) GetMany

func (bd *BufferedDAG) GetMany(ctx context.Context, cs []cid.Cid) <-chan *NodeOption

GetMany commits and gets nodes from the DAGService.

func (*BufferedDAG) Remove

func (bd *BufferedDAG) Remove(ctx context.Context, c cid.Cid) error

Remove commits and removes a node from the DAGService.

func (*BufferedDAG) RemoveMany

func (bd *BufferedDAG) RemoveMany(ctx context.Context, cs []cid.Cid) error

RemoveMany commits and removes nodes from the DAGService.

type DAGService

type DAGService interface {

	// Remove removes a node from this DAG.
	// Remove returns no error if the requested node is not present in this DAG.
	Remove(context.Context, cid.Cid) error

	// RemoveMany removes many nodes from this DAG.
	// It returns success even if the nodes were not present in the DAG.
	RemoveMany(context.Context, []cid.Cid) error

DAGService is an IPFS Merkle DAG service.

type DecodeBlockFunc

type DecodeBlockFunc func(block blocks.Block) (Node, error)

DecodeBlockFunc functions decode blocks into nodes.

type ErrNotFound

type ErrNotFound struct {
	Cid cid.Cid

ErrNotFound is used to signal when a Node could not be found. The specific meaning will depend on the DAGService implementation, which may be trying to read nodes locally but also, trying to find them remotely.

The Cid field can be filled in to provide additional context.

func (ErrNotFound) Error added in v0.1.0

func (e ErrNotFound) Error() string

Error implements the error interface and returns a human-readable message for this error.

func (ErrNotFound) Is added in v0.1.0

func (e ErrNotFound) Is(err error) bool

Is allows to check whether any error is of this ErrNotFound type. Do not use this directly, but rather errors.Is(yourError, ErrNotFound).

func (ErrNotFound) NotFound added in v0.1.0

func (e ErrNotFound) NotFound() bool

NotFound returns true.

type Link struct {
	// utf string name. should be unique per object
	Name string // utf8

	// cumulative size of target object
	Size uint64

	// multihash of the target object
	Cid cid.Cid

Link represents an IPFS Merkle DAG Link between Nodes.

func GetLinks(ctx context.Context, ng NodeGetter, c cid.Cid) ([]*Link, error)

GetLinks returns the CIDs of the children of the given node. Prefer this method over looking up the node itself and calling `Links()` on it as this method may be able to use a link cache.

func MakeLink(n Node) (*Link, error)

MakeLink creates a link to the given node

func (*Link) GetNode

func (l *Link) GetNode(ctx context.Context, serv NodeGetter) (Node, error)

GetNode returns the MDAG Node that this link points to

type LinkGetter

type LinkGetter interface {

	// GetLinks returns the children of the node refered to by the given
	// CID.
	GetLinks(ctx context.Context, nd cid.Cid) ([]*Link, error)

NodeGetters can optionally implement this interface to make finding linked objects faster.

type NavigableIPLDNode struct {
	// contains filtered or unexported fields

NavigableIPLDNode implements the `NavigableNode` interface wrapping an IPLD `Node` and providing support for node promises.

func NewNavigableIPLDNode

func NewNavigableIPLDNode(node Node, nodeGetter NodeGetter) *NavigableIPLDNode

NewNavigableIPLDNode returns a `NavigableIPLDNode` wrapping the provided `node`.

func (nn *NavigableIPLDNode) ChildTotal() uint

ChildTotal implements the `NavigableNode` returning the number of links (of child nodes) in this node.

func (nn *NavigableIPLDNode) FetchChild(ctx context.Context, childIndex uint) (NavigableNode, error)

FetchChild implements the `NavigableNode` interface using node promises to preload the following child nodes to `childIndex` leaving them ready for subsequent `FetchChild` calls.

func (nn *NavigableIPLDNode) GetIPLDNode() Node

GetIPLDNode returns the IPLD `Node` wrapped into this structure.

type NavigableNode interface {

	// FetchChild returns the child of this node pointed to by `childIndex`.
	// A `Context` stored in the `Walker` is passed (`ctx`) that may contain
	// configuration attributes stored by the user before initiating the
	// walk operation.
	FetchChild(ctx context.Context, childIndex uint) (NavigableNode, error)

	// ChildTotal returns the number of children of the `ActiveNode`.
	ChildTotal() uint

	// GetIPLDNode returns actual IPLD Node
	GetIPLDNode() Node

NavigableNode is the interface the nodes of a DAG need to implement in order to be traversed by the `Walker`.

type Node

type Node interface {

	// ResolveLink is a helper function that calls resolve and asserts the
	// output is a link
	ResolveLink(path []string) (*Link, []string, error)

	// Copy returns a deep copy of this node
	Copy() Node

	// Links is a helper function that returns all links within this object
	Links() []*Link

	// TODO: not sure if stat deserves to stay
	Stat() (*NodeStat, error)

	// Size returns the size in bytes of the serialized object
	Size() (uint64, error)

Node is the base interface all IPLD nodes must implement.

Nodes are **Immutable** and all methods defined on the interface are **Thread Safe**.

func Decode

func Decode(block blocks.Block, decoder DecodeBlockFunc) (Node, error)

Decode decodes the given block using passed DecodeBlockFunc. Note: this is just a helper function, consider using the DecodeBlockFunc itself rather than this helper

func ExtractIPLDNode

func ExtractIPLDNode(node NavigableNode) Node

ExtractIPLDNode is a helper function that takes a `NavigableNode` and returns the IPLD `Node` wrapped inside. Used in the `Visitor` function. TODO: Check for errors to avoid a panic?

type NodeAdder

type NodeAdder interface {
	// Add adds a node to this DAG.
	Add(context.Context, Node) error

	// AddMany adds many nodes to this DAG.
	// Consider using the Batch NodeAdder (`NewBatch`) if you make
	// extensive use of this function.
	AddMany(context.Context, []Node) error

NodeAdder adds nodes to a DAG.

type NodeGetter

type NodeGetter interface {
	// Get retrieves nodes by CID. Depending on the NodeGetter
	// implementation, this may involve fetching the Node from a remote
	// machine; consider setting a deadline in the context.
	Get(context.Context, cid.Cid) (Node, error)

	// GetMany returns a channel of NodeOptions given a set of CIDs.
	GetMany(context.Context, []cid.Cid) <-chan *NodeOption

The basic Node resolution service.

type NodeOption

type NodeOption struct {
	Node Node
	Err  error

Either a node or an error.

type NodePromise

type NodePromise struct {
	// contains filtered or unexported fields

func GetDAG

func GetDAG(ctx context.Context, ds NodeGetter, root Node) []*NodePromise

GetDAG will fill out all of the links of the given Node. It returns an array of NodePromise with the linked nodes all in the proper order.

func GetNodes

func GetNodes(ctx context.Context, ds NodeGetter, keys []cid.Cid) []*NodePromise

GetNodes returns an array of 'FutureNode' promises, with each corresponding to the key with the same index as the passed in keys

func NewNodePromise

func NewNodePromise(ctx context.Context) *NodePromise

NodePromise provides a promise like interface for a dag Node the first call to Get will block until the Node is received from its internal channels, subsequent calls will return the cached node.

Thread Safety: This is multiple-consumer/single-producer safe.

func (*NodePromise) Fail

func (np *NodePromise) Fail(err error)

Call this function to fail a promise.

Once a promise has been failed or fulfilled, further attempts to fail it will be silently dropped.

func (*NodePromise) Get

func (np *NodePromise) Get(ctx context.Context) (Node, error)

Get the value of this promise.

This function is safe to call concurrently from any number of goroutines.

func (*NodePromise) Send

func (np *NodePromise) Send(nd Node)

Fulfill this promise.

Once a promise has been fulfilled or failed, calling this function will panic.

type NodeStat

type NodeStat struct {
	Hash           string
	NumLinks       int // number of links in link table
	BlockSize      int // size of the raw, encoded data
	LinksSize      int // size of the links segment
	DataSize       int // size of the data segment
	CumulativeSize int // cumulative size of object and its references

NodeStat is a statistics object for a Node. Mostly sizes.

func (NodeStat) String

func (ns NodeStat) String() string

type Registry added in v0.5.0

type Registry struct {
	// contains filtered or unexported fields

Registry is a structure for storing mappings of multicodec IPLD codec numbers to DecodeBlockFunc functions.

Registry includes no mutexing. If using Registry in a concurrent context, you must handle synchronization yourself. (Typically, it is recommended to do initialization earlier in a program, before fanning out goroutines; this avoids the need for mutexing overhead.)

Multicodec indicator numbers are specified in . You should not use indicator numbers which are not specified in that table (however, there is nothing in this implementation that will attempt to stop you, either).

func (*Registry) Decode added in v0.5.0

func (r *Registry) Decode(block blocks.Block) (Node, error)

func (*Registry) Register added in v0.5.0

func (r *Registry) Register(codec uint64, decoder DecodeBlockFunc)

Register registers decoder for all blocks with the passed codec.

This will silently replace any existing registered block decoders.

type Resolver

type Resolver interface {
	// Resolve resolves a path through this node, stopping at any link boundary
	// and returning the object found as well as the remaining path to traverse
	Resolve(path []string) (interface{}, []string, error)

	// Tree lists all paths within the object under 'path', and up to the given depth.
	// To list the entire object (similar to `find .`) pass "" and -1
	Tree(path string, depth int) []string

type Visitor

type Visitor func(node NavigableNode) error

Function called each time a node is arrived upon in a walk operation through the `down` method (not when going back `up`). It is the main API to implement DAG functionality (e.g., read and seek a file DAG) on top of the `Walker` structure.

Its argument is the current `node` being visited (the `ActiveNode`). Any error it returns (apart from the internal `errPauseWalkOperation`) will be forwarded to the caller of the walk operation (pausing it).

Any of the exported methods of this API should be allowed to be called from within this method, e.g., `NextChild`. TODO: Check that. Can `ResetPosition` be called without breaking the `Walker` integrity?

type Walker

type Walker struct {
	// contains filtered or unexported fields

Walker provides methods to move through a DAG of nodes that implement the `NavigableNode` interface. It uses iterative algorithms (instead of recursive ones) that expose the `path` of nodes from the root to the `ActiveNode` it currently points to.

It provides multiple ways to walk through the DAG (e.g. `Iterate` and `Seek`). When using them, you provide a Visitor function that will be called for each node the Walker traverses. The Visitor can read data from those nodes and, optionally, direct the movement of the Walker by calling `Pause` (to stop traversing and return) or `NextChild` (to skip a child and its descendants). See the DAG reader in `` for a usage example. TODO: This example isn't merged yet.

func NewWalker

func NewWalker(ctx context.Context, root NavigableNode) *Walker

NewWalker creates a new `Walker` structure from a `root` NavigableNode.

func (*Walker) ActiveChildIndex

func (w *Walker) ActiveChildIndex() uint

ActiveChildIndex returns the index of the child the `ActiveNode()` is pointing to.

func (*Walker) ActiveNode

func (w *Walker) ActiveNode() NavigableNode

ActiveNode returns the `NavigableNode` that `Walker` is pointing to at the moment. It changes when `up` or `down` is called.

func (*Walker) Iterate

func (w *Walker) Iterate(visitor Visitor) error

Iterate the DAG through the DFS pre-order walk algorithm, going down as much as possible, then `NextChild` to the other siblings, and then up (to go down again). The position is saved throughout iterations (and can be previously set in `Seek`) allowing `Iterate` to be called repeatedly (after a `Pause`) to continue the iteration.

This function returns the errors received from `down` (generated either inside the `Visitor` call or any other errors while fetching the child nodes), the rest of the move errors are handled within the function and are not returned.

func (*Walker) NextChild

func (w *Walker) NextChild() error

NextChild increases the child index of the `ActiveNode` to point to the next child (which may exist or may be the end of the available child nodes).

This method doesn't change the `ActiveNode`, it just changes where is it pointing to next, it could be interpreted as "turn to the next child".

func (*Walker) Pause

func (w *Walker) Pause()

Pause the current walk operation. This function must be called from within the `Visitor` function.

func (*Walker) Seek

func (w *Walker) Seek(visitor Visitor) error

Seek a specific node in a downwards manner. The `Visitor` should be used to steer the seek selecting at each node which child will the seek continue to (extending the `path` in that direction) or pause it (if the desired node has been found). The seek always starts from the root. It modifies the position so it shouldn't be used in-between `Iterate` calls (it can be used to set the position *before* iterating). If the visitor returns any non-`nil` errors the seek will stop.

TODO: The seek could be extended to seek from the current position. (Is there something in the logic that would prevent it at the moment?)

func (*Walker) SetContext

func (w *Walker) SetContext(ctx context.Context)

SetContext changes the internal `Walker` (that is provided to the `NavigableNode`s when calling `FetchChild`) with the one passed as argument.

Jump to

Keyboard shortcuts

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