format

package
v0.0.0-...-8b9b725 Latest Latest
Warning

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

Go to latest
Published: Apr 7, 2019 License: MIT, MIT Imports: 7 Imported by: 150

README

go-ipld-format

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.

Table of Contents

Install

make install

Contribute

PRs are welcome!

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

License

MIT © Jeromy Johnson

Documentation

Index

Constants

This section is empty.

Variables

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.

View Source
var ErrNotFound = fmt.Errorf("merkledag: not found")
View Source
var ParallelBatchCommits = runtime.NumCPU() * 2

ParallelBatchCommits is the number of batch commits that can be in-flight before blocking. TODO(ipfs/go-ipfs#4299): Experiment with multiple datastores, storage devices, and CPUs to find the right value/formula.

Functions

func Copy

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

func Register

func Register(codec uint64, decoder DecodeBlockFunc)

Register registers block decoders with the default BlockDecoder.

Types

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: http://dave.cheney.net/2014/10/17/functional-options-for-friendly-apis

func MaxNodesBatchOption

func MaxNodesBatchOption(num int) BatchOption

MaxNodesBatchOption sets the maximum number of nodes in a Batch.

func MaxSizeBatchOption

func MaxSizeBatchOption(size int) BatchOption

MaxSizeBatchOption sets the maximum size of a Batch.

type BlockDecoder

type BlockDecoder interface {
	Register(codec uint64, decoder DecodeBlockFunc)
	Decode(blocks.Block) (Node, error)
}
var DefaultBlockDecoder BlockDecoder = &safeBlockDecoder{decoders: make(map[uint64]DecodeBlockFunc)}

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 {
	NodeGetter
	NodeAdder

	// 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 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 {
	NodeGetter

	// 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
}

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 {
	blocks.Block
	Resolver

	// 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) (Node, error)

Decode decodes the given block using the default BlockDecoder.

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 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 `github.com/ipfs/go-unixfs/io/dagreader.go` 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