merkledag

package module
v0.0.3 Latest Latest
Warning

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

Go to latest
Published: Aug 30, 2021 License: MIT Imports: 14 Imported by: 33

README

go-merkledag

Coverage Status Travis CI

go-merkledag implements the 'DAGService' interface and adds two ipld node types, Protobuf and Raw

Lead Maintainer

Steven Allen

Table of Contents

TODO

  • Pull out dag-pb stuff into go-ipld-pb
  • Pull 'raw nodes' out into go-ipld-raw (maybe main one instead)
  • Move most other logic to go-ipld
  • Make dagservice constructor take a 'blockstore' to avoid the blockservice offline nonsense
  • deprecate this package

Contribute

PRs are welcome!

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

License

MIT © Juan Batiz-Benet

Documentation

Overview

Package merkledag implements the DMS3 Merkle DAG data structures.

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrNotProtobuf  = fmt.Errorf("expected protobuf dag node")
	ErrLinkNotFound = fmt.Errorf("no link by that name")
)

Common errors

View Source
var ErrReadOnly = fmt.Errorf("cannot write to readonly DAGService")

ErrReadOnly is used when a read-only datastructure is written to.

Functions

func DecodeProtobufBlock

func DecodeProtobufBlock(b blocks.Block) (ld.Node, error)

DecodeProtobufBlock is a block decoder for protobuf LD nodes conforming to node.DecodeBlockFunc

func DecodeRawBlock

func DecodeRawBlock(block blocks.Block) (ld.Node, error)

DecodeRawBlock is a block decoder for raw LD nodes conforming to `node.DecodeBlockFunc`.

func FetchGraph

func FetchGraph(ctx context.Context, root cid.Cid, serv ld.DAGService) error

FetchGraph fetches all nodes that are children of the given node

func FetchGraphWithDepthLimit

func FetchGraphWithDepthLimit(ctx context.Context, root cid.Cid, depthLim int, serv ld.DAGService) error

FetchGraphWithDepthLimit fetches all nodes that are children to the given node down to the given depth. maxDepth=0 means "only fetch root", maxDepth=1 means "fetch root and its direct children" and so on... maxDepth=-1 means unlimited.

func NewDAGService

func NewDAGService(bs bserv.BlockService) *dagService

NewDAGService constructs a new DAGService (using the default implementation). Note that the default implementation is also an ld.LinkGetter.

func NewReadOnlyDagService

func NewReadOnlyDagService(ng ld.NodeGetter) ld.DAGService

NewReadOnlyDagService takes a NodeGetter, and returns a full DAGService implementation that returns ErrReadOnly when its 'write' methods are invoked.

func NewSession

func NewSession(ctx context.Context, g ld.NodeGetter) ld.NodeGetter

NewSession returns a session backed NodeGetter if the given NodeGetter implements SessionMaker.

func PrefixForCidVersion

func PrefixForCidVersion(version int) (cid.Prefix, error)

PrefixForCidVersion returns the Protobuf prefix for a given CID version

func V0CidPrefix

func V0CidPrefix() cid.Prefix

V0CidPrefix returns a prefix for CIDv0

func V1CidPrefix

func V1CidPrefix() cid.Prefix

V1CidPrefix returns a prefix for CIDv1 with the default settings

func Walk

func Walk(ctx context.Context, getLinks GetLinks, c cid.Cid, visit func(cid.Cid) bool, options ...WalkOption) error

WalkGraph will walk the dag in order (depth first) starting at the given root.

func WalkDepth

func WalkDepth(ctx context.Context, getLinks GetLinks, c cid.Cid, visit func(cid.Cid, int) bool, options ...WalkOption) error

WalkDepth walks the dag starting at the given root and passes the current depth to a given visit function. The visit function can be used to limit DAG exploration.

Types

type ComboService

type ComboService struct {
	Read  ld.NodeGetter
	Write ld.DAGService
}

ComboService implements ld.DAGService, using 'Read' for all fetch methods, and 'Write' for all methods that add new objects.

func (*ComboService) Add

func (cs *ComboService) Add(ctx context.Context, nd ld.Node) error

Add writes a new node using the Write DAGService.

func (*ComboService) AddMany

func (cs *ComboService) AddMany(ctx context.Context, nds []ld.Node) error

AddMany adds nodes using the Write DAGService.

func (*ComboService) Get

func (cs *ComboService) Get(ctx context.Context, c cid.Cid) (ld.Node, error)

Get fetches a node using the Read DAGService.

func (*ComboService) GetMany

func (cs *ComboService) GetMany(ctx context.Context, cids []cid.Cid) <-chan *ld.NodeOption

GetMany fetches nodes using the Read DAGService.

func (*ComboService) Remove

func (cs *ComboService) Remove(ctx context.Context, c cid.Cid) error

Remove deletes a node using the Write DAGService.

func (*ComboService) RemoveMany

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

RemoveMany deletes nodes using the Write DAGService.

type ErrorService

type ErrorService struct {
	Err error
}

ErrorService implements ld.DAGService, returning 'Err' for every call.

func (*ErrorService) Add

func (cs *ErrorService) Add(ctx context.Context, nd ld.Node) error

Add returns the cs.Err.

func (*ErrorService) AddMany

func (cs *ErrorService) AddMany(ctx context.Context, nds []ld.Node) error

AddMany returns the cs.Err.

func (*ErrorService) Get

func (cs *ErrorService) Get(ctx context.Context, c cid.Cid) (ld.Node, error)

Get returns the cs.Err.

func (*ErrorService) GetMany

func (cs *ErrorService) GetMany(ctx context.Context, cids []cid.Cid) <-chan *ld.NodeOption

GetMany many returns the cs.Err.

func (*ErrorService) Remove

func (cs *ErrorService) Remove(ctx context.Context, c cid.Cid) error

Remove returns the cs.Err.

func (*ErrorService) RemoveMany

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

RemoveMany returns the cs.Err.

type GetLinks func(context.Context, cid.Cid) ([]*ld.Link, error)

GetLinks is the type of function passed to the EnumerateChildren function(s) for getting the children of an LD node.

func GetLinksDirect

func GetLinksDirect(serv ld.NodeGetter) GetLinks

GetLinksDirect creates a function to get the links for a node, from the node, bypassing the LinkService. If the node does not exist locally (and can not be retrieved) an error will be returned.

func GetLinksWithDAG

func GetLinksWithDAG(ng ld.NodeGetter) GetLinks

GetLinksWithDAG returns a GetLinks function that tries to use the given NodeGetter as a LinkGetter to get the children of a given LD node. This may allow us to traverse the DAG without actually loading and parsing the node in question (if we already have the links cached).

type LinkSlice

type LinkSlice []*ld.Link

LinkSlice is a slice of ld.Links

func (LinkSlice) Len

func (ls LinkSlice) Len() int

func (LinkSlice) Less

func (ls LinkSlice) Less(a, b int) bool

func (LinkSlice) Swap

func (ls LinkSlice) Swap(a, b int)

type ProgressTracker

type ProgressTracker struct {
	Total int
	// contains filtered or unexported fields
}

ProgressTracker is used to show progress when fetching nodes.

func (*ProgressTracker) DeriveContext

func (p *ProgressTracker) DeriveContext(ctx context.Context) context.Context

DeriveContext returns a new context with value "progress" derived from the given one.

func (*ProgressTracker) Increment

func (p *ProgressTracker) Increment()

Increment adds one to the total progress.

func (*ProgressTracker) Value

func (p *ProgressTracker) Value() int

Value returns the current progress.

type ProtoNode

type ProtoNode struct {
	// contains filtered or unexported fields
}

ProtoNode represents a node in the DMS3 Merkle DAG. nodes have opaque data and a set of navigable links.

func DecodeProtobuf

func DecodeProtobuf(encoded []byte) (*ProtoNode, error)

DecodeProtobuf decodes raw data and returns a new Node instance.

func NodeWithData

func NodeWithData(d []byte) *ProtoNode

NodeWithData builds a new Protonode with the given data.

func (n *ProtoNode) AddNodeLink(name string, that ld.Node) error

AddNodeLink adds a link to another node.

func (n *ProtoNode) AddRawLink(name string, l *ld.Link) error

AddRawLink adds a copy of a link to this node

func (*ProtoNode) Cid

func (n *ProtoNode) Cid() cid.Cid

Cid returns the node's Cid, calculated according to its prefix and raw data contents.

func (*ProtoNode) CidBuilder

func (n *ProtoNode) CidBuilder() cid.Builder

CidBuilder returns the CID Builder for this ProtoNode, it is never nil

func (*ProtoNode) Copy

func (n *ProtoNode) Copy() ld.Node

Copy returns a copy of the node. NOTE: Does not make copies of Node objects in the links.

func (*ProtoNode) Data

func (n *ProtoNode) Data() []byte

Data returns the data stored by this node.

func (*ProtoNode) EncodeProtobuf

func (n *ProtoNode) EncodeProtobuf(force bool) ([]byte, error)

EncodeProtobuf returns the encoded raw data version of a Node instance. It may use a cached encoded version, unless the force flag is given.

func (*ProtoNode) GetLinkedNode

func (n *ProtoNode) GetLinkedNode(ctx context.Context, ds ld.DAGService, name string) (ld.Node, error)

GetLinkedNode returns a copy of the LD Node with the given name.

func (*ProtoNode) GetLinkedProtoNode

func (n *ProtoNode) GetLinkedProtoNode(ctx context.Context, ds ld.DAGService, name string) (*ProtoNode, error)

GetLinkedProtoNode returns a copy of the ProtoNode with the given name.

func (n *ProtoNode) GetNodeLink(name string) (*ld.Link, error)

GetNodeLink returns a copy of the link with the given name.

func (*ProtoNode) GetPBNode

func (n *ProtoNode) GetPBNode() *pb.PBNode

GetPBNode converts *ProtoNode into it's protocol buffer variant. If you plan on mutating the data of the original node, it is recommended that you call ProtoNode.Copy() before calling ProtoNode.GetPBNode()

func (n *ProtoNode) Links() []*ld.Link

Links returns the node links.

func (*ProtoNode) Loggable

func (n *ProtoNode) Loggable() map[string]interface{}

Loggable implements the dms3/go-log.Loggable interface.

func (*ProtoNode) Marshal

func (n *ProtoNode) Marshal() ([]byte, error)

Marshal encodes a *Node instance into a new byte slice. The conversion uses an intermediate PBNode.

func (*ProtoNode) MarshalJSON

func (n *ProtoNode) MarshalJSON() ([]byte, error)

MarshalJSON returns a JSON representation of the node.

func (*ProtoNode) Multihash

func (n *ProtoNode) Multihash() mh.Multihash

Multihash hashes the encoded data of this node.

func (*ProtoNode) RawData

func (n *ProtoNode) RawData() []byte

RawData returns the protobuf-encoded version of the node.

func (n *ProtoNode) RemoveNodeLink(name string) error

RemoveNodeLink removes a link on this node by the given name.

func (*ProtoNode) Resolve

func (n *ProtoNode) Resolve(path []string) (interface{}, []string, error)

Resolve is an alias for ResolveLink.

func (n *ProtoNode) ResolveLink(path []string) (*ld.Link, []string, error)

ResolveLink consumes the first element of the path and obtains the link corresponding to it from the node. It returns the link and the path without the consumed element.

func (*ProtoNode) SetCidBuilder

func (n *ProtoNode) SetCidBuilder(builder cid.Builder)

SetCidBuilder sets the CID builder if it is non nil, if nil then it is reset to the default value

func (*ProtoNode) SetData

func (n *ProtoNode) SetData(d []byte)

SetData stores data in this nodes.

func (n *ProtoNode) SetLinks(links []*ld.Link)

SetLinks replaces the node links with the given ones.

func (*ProtoNode) Size

func (n *ProtoNode) Size() (uint64, error)

Size returns the total size of the data addressed by node, including the total sizes of references.

func (*ProtoNode) Stat

func (n *ProtoNode) Stat() (*ld.NodeStat, error)

Stat returns statistics on the node.

func (*ProtoNode) String

func (n *ProtoNode) String() string

String prints the node's Cid.

func (*ProtoNode) Tree

func (n *ProtoNode) Tree(p string, depth int) []string

Tree returns the link names of the ProtoNode. ProtoNodes are only ever one path deep, so anything different than an empty string for p results in nothing. The depth parameter is ignored.

func (*ProtoNode) UnmarshalJSON

func (n *ProtoNode) UnmarshalJSON(b []byte) error

UnmarshalJSON reads the node fields from a JSON-encoded byte slice.

func (n *ProtoNode) UpdateNodeLink(name string, that *ProtoNode) (*ProtoNode, error)

UpdateNodeLink return a copy of the node with the link name set to point to that. If a link of the same name existed, it is removed.

type RawNode

type RawNode struct {
	blocks.Block
}

RawNode represents a node which only contains data.

func NewRawNode

func NewRawNode(data []byte) *RawNode

NewRawNode creates a RawNode using the default sha2-256 hash function.

func NewRawNodeWPrefix

func NewRawNodeWPrefix(data []byte, builder cid.Builder) (*RawNode, error)

NewRawNodeWPrefix creates a RawNode using the provided cid builder

func (*RawNode) Copy

func (rn *RawNode) Copy() ld.Node

Copy performs a deep copy of this node and returns it as an ld.Node

func (rn *RawNode) Links() []*ld.Link

Links returns nil.

func (*RawNode) MarshalJSON

func (rn *RawNode) MarshalJSON() ([]byte, error)

MarshalJSON is required for our "dms3 dag" commands.

func (*RawNode) Resolve

func (rn *RawNode) Resolve(path []string) (interface{}, []string, error)

Resolve returns an error.

func (rn *RawNode) ResolveLink(path []string) (*ld.Link, []string, error)

ResolveLink returns an error.

func (*RawNode) Size

func (rn *RawNode) Size() (uint64, error)

Size returns the size of this node

func (*RawNode) Stat

func (rn *RawNode) Stat() (*ld.NodeStat, error)

Stat returns some Stats about this node.

func (*RawNode) Tree

func (rn *RawNode) Tree(p string, depth int) []string

Tree returns nil.

type SessionMaker

type SessionMaker interface {
	Session(context.Context) ld.NodeGetter
}

SessionMaker is an object that can generate a new fetching session.

type WalkOption

type WalkOption func(*walkOptions)

WalkOption is a setter for walkOptions

func Concurrency

func Concurrency(worker int) WalkOption

Concurrency is a WalkOption indicating that node fetching should be done in parallel, with a specific concurrency factor. NOTE: When using that option, the walk order is *not* guarantee. NOTE: It *does not* make multiple concurrent calls to the passed `visit` function.

func Concurrent

func Concurrent() WalkOption

Concurrent is a WalkOption indicating that node fetching should be done in parallel, with the default concurrency factor. NOTE: When using that option, the walk order is *not* guarantee. NOTE: It *does not* make multiple concurrent calls to the passed `visit` function.

func IgnoreErrors

func IgnoreErrors() WalkOption

IgnoreErrors is a WalkOption indicating that the walk should attempt to continue even when an error occur.

func IgnoreMissing

func IgnoreMissing() WalkOption

IgnoreMissing is a WalkOption indicating that the walk should continue when a node is missing.

func OnError

func OnError(handler func(c cid.Cid, err error) error) WalkOption

OnError is a WalkOption adding a custom error handler. If this handler return a nil error, the walk will continue.

func OnMissing

func OnMissing(callback func(c cid.Cid)) WalkOption

OnMissing is a WalkOption adding a callback that will be triggered on a missing node.

func SkipRoot

func SkipRoot() WalkOption

SkipRoot is a WalkOption indicating that the root node should skipped

Directories

Path Synopsis
Package traverse provides merkledag traversal functions
Package traverse provides merkledag traversal functions

Jump to

Keyboard shortcuts

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