traversal

Documentation

Overview

Package traversal provides utilities that operate above the github.com/ipld/go-ipld-prime/traversal system to perform the kinds of traversals required by the IPFS Trustless Gateway protocol, which requires only limited subset of the full go-ipld-prime traversal system.

Utilities are also provided to verify CAR streams against expected traversals and the LinkSystems used throughout can also be used to produce IPFS Trustless Gateway CAR streams when coupled with the github.com/ipld/go-car/v2/storage package.

Index

• Variables
• func CheckPath(expectPath datamodel.Path, lastPath datamodel.Path) error
• type BlockStream
• type Config
  • func (cfg Config) Traverse(ctx context.Context, lsys linking.LinkSystem, preloader preload.Loader) (datamodel.Path, error)
  • func (cfg Config) VerifyBlockStream(ctx context.Context, bs BlockStream, lsys linking.LinkSystem) (TraversalResult, error)
  • func (cfg Config) VerifyCar(ctx context.Context, rdr io.Reader, lsys linking.LinkSystem) (TraversalResult, error)
• type ErrorCapturingReader
  • func NewErrorCapturingReader(lsys linking.LinkSystem) (linking.LinkSystem, *ErrorCapturingReader)
  • func (ecr *ErrorCapturingReader) StorageReadOpener(lc linking.LinkContext, l datamodel.Link) (io.Reader, error)
• type TraversalResult

Variables

var (
	ErrMalformedCar    = errors.New("malformed CAR")
	ErrBadVersion      = errors.New("bad CAR version")
	ErrBadRoots        = errors.New("CAR root CID mismatch")
	ErrUnexpectedBlock = errors.New("unexpected block in CAR")
	ErrExtraneousBlock = errors.New("extraneous block in CAR")
	ErrMissingBlock    = errors.New("missing block in CAR")
)

Functions

func CheckPath

func CheckPath(expectPath datamodel.Path, lastPath datamodel.Path) error

CheckPath will check the lastPath against the expectedPath, returning an error if the expected path is not fulfilled within the lastPath. A successful check will find that the expectedPath is subset of the lastPath for. If the expectedPath does not match the prefix of the lastPath, or lastPath is shorter than expectedPath, an error will be returned.

Types

type BlockStream

type BlockStream interface {
	Next(ctx context.Context) (blocks.Block, error)
}

type Config

type Config struct {
	Root               cid.Cid        // The single root we expect to appear in the CAR and that we use to run our traversal against
	AllowCARv2         bool           // If true, allow CARv2 files to be received, otherwise strictly only allow CARv1
	Selector           datamodel.Node // The selector to execute, starting at the provided Root, to verify the contents of the CAR
	CheckRootsMismatch bool           // Check if roots match expected behavior
	ExpectDuplicatesIn bool           // Handles whether the incoming stream has duplicates
	WriteDuplicatesOut bool           // Handles whether duplicates should be written a second time as blocks
	MaxBlocks          uint64         // set a budget for the traversal
	OnBlockIn          func(uint64)   // a callback whenever a block is read the incoming source, recording the number of bytes in the block data
}

func (Config) Traverse

func (cfg Config) Traverse(
	ctx context.Context,
	lsys linking.LinkSystem,
	preloader preload.Loader,
) (datamodel.Path, error)

Traverse performs a traversal using the Config's Selector, starting at the Config's Root, using the provided LinkSystem and optional Preloader.

The traversal will capture any errors that occur during traversal, including block load errors that may not otherwise be captured by a standard go-ipld-prime traversal (such as those encountered by ADLs that are not propagated).

Returns the last path visited during the traversal, or an error if the traversal failed.

func (Config) VerifyBlockStream

func (cfg Config) VerifyBlockStream(
	ctx context.Context,
	bs BlockStream,
	lsys linking.LinkSystem,
) (TraversalResult, error)

VerifyBlockStream reads blocks from a BlockStream and verifies the stream of blocks are strictly what is specified by this Config and writes the blocks to the provided LinkSystem. It returns the number of blocks and bytes written to the LinkSystem. The LinkSystem may be used to load duplicate blocks in the case that duplicates are not expected from the BlockStream being verified but need to be written back out to the LinkSystem.

Verification is performed according to the CAR construction rules contained within the Trustless, and Path Gateway specifications:

* https://specs.ipfs.tech/http-gateways/trustless-gateway/

* https://specs.ipfs.tech/http-gateways/path-gateway/

func (Config) VerifyCar

func (cfg Config) VerifyCar(
	ctx context.Context,
	rdr io.Reader,
	lsys linking.LinkSystem,
) (TraversalResult, error)

VerifyCar reads a CAR from the provided reader, verifies the contents are strictly what is specified by this Config and writes the blocks to the provided LinkSystem. It returns the number of blocks and bytes written to the LinkSystem. The LinkSystem may be used to load duplicate blocks in the case that duplicates are not expected from the CAR being verified but need to be written back out to the LinkSystem.

Verification is performed according to the CAR construction rules contained within the Trustless, and Path Gateway specifications:

* https://specs.ipfs.tech/http-gateways/trustless-gateway/

* https://specs.ipfs.tech/http-gateways/path-gateway/

type ErrorCapturingReader

type ErrorCapturingReader struct {
	Error error
	// contains filtered or unexported fields
}

ErrorCapturingReader captures any errors that occur during block loading and makes them available via the Error property.

This is useful for capturing errors that occur during traversal, which are not currently surfaced by the traversal package, see:

https://github.com/ipld/go-ipld-prime/pull/524

func NewErrorCapturingReader

func NewErrorCapturingReader(lsys linking.LinkSystem) (linking.LinkSystem, *ErrorCapturingReader)

func (*ErrorCapturingReader) StorageReadOpener

func (ecr *ErrorCapturingReader) StorageReadOpener(lc linking.LinkContext, l datamodel.Link) (io.Reader, error)

type TraversalResult

type TraversalResult struct {
	// LastPath is the final path visited in a traversal, it can be used to
	// compare against the expected path to determine whether the traversal was
	// "complete"
	LastPath  datamodel.Path
	BlocksIn  uint64
	BytesIn   uint64
	BlocksOut uint64
	BytesOut  uint64
}

TraversalResult provides the results of a successful traversal. Byte counting is performed on the raw block data, not any CAR container bytes.