noder

Documentation

Overview

Package noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors).

The hasher interface is easy to implement naively by elements that already have a hash, like git blobs and trees. More sophisticated implementations can implement the Equal function in exotic ways though: for instance, comparing the modification time of directories in a filesystem.

Index

• Variables
• type Comparators
• type Equal
• type Hasher
• type Matcher
  • func NewSparseTreeMatcher(dirs []string) Matcher
• type Noder
• type OriginHasher
• type Path
  • func (p Path) Children(ctx context.Context) ([]Noder, error)
  • func (p Path) Compare(other Path) int
  • func (p Path) Hash() []byte
  • func (p Path) IsDir() bool
  • func (p Path) Last() Noder
  • func (p Path) Name() string
  • func (p Path) NumChildren(ctx context.Context) (int, error)
  • func (p Path) Skip() bool
  • func (p Path) String() string
• type SparseMatcher
  • func NewSparseMatcher(dirs []string) SparseMatcher

Variables

var NoChildren = []Noder{}

NoChildren represents the children of a noder without children.

Types

type Comparators

type Comparators interface {
	Mode() filemode.FileMode
	ModifiedAt() time.Time
}

type Equal

type Equal func(a, b Hasher) bool

Equal functions take two hashers and return if they are equal.

These functions are expected to be faster than reflect.Equal or reflect.DeepEqual because they can compare just the hash of the objects, instead of their contents, so they are expected to be O(1).

type Hasher

type Hasher interface {
	Hash() []byte
}

Hasher interface is implemented by types that can tell you their hash.

type Matcher

type Matcher interface {
	Len() int
	Match(name string) (Matcher, bool)
}

func NewSparseTreeMatcher

func NewSparseTreeMatcher(dirs []string) Matcher

type Noder

type Noder interface {
	Hasher
	fmt.Stringer // for testing purposes
	// Name returns the name of an element (relative, not its full
	// path).
	Name() string
	// IsDir returns true if the element is a directory-like node or
	// false if it is a file-like node.
	IsDir() bool
	// Children returns the children of the element.  Note that empty
	// directory-like noders and file-like noders will both return
	// NoChildren.
	Children(ctx context.Context) ([]Noder, error)
	// NumChildren returns the number of children this element has.
	//
	// This method is an optimization: the number of children is easily
	// calculated as the length of the value returned by the Children
	// method (above); yet, some implementations will be able to
	// implement NumChildren in O(1) while Children is usually more
	// complex.
	NumChildren(ctx context.Context) (int, error)
	Skip() bool
}

The Noder interface is implemented by the elements of a Merkle Trie.

There are two types of elements in a Merkle Trie:

- file-like nodes: they cannot have children.

- directory-like nodes: they can have 0 or more children and their hash is calculated by combining their children hashes.

type OriginHasher

type OriginHasher interface {
	HashRaw() plumbing.Hash
}

type Path

type Path []Noder

Path values represent a noder and its ancestors. The root goes first and the actual final noder the path is referring to will be the last.

A path implements the Noder interface, redirecting all the interface calls to its final noder.

Paths build from an empty Noder slice are not valid paths and should not be used.

func (Path) Children

func (p Path) Children(ctx context.Context) ([]Noder, error)

Children returns the children of the final noder in the path.

func (Path) Compare

func (p Path) Compare(other Path) int

Compare returns -1, 0 or 1 if the path p is smaller, equal or bigger than other, in "directory order"; for example:

"a" < "b" "a/b/c/d/z" < "b" "a/b/a" > "a/b"

func (Path) Hash

func (p Path) Hash() []byte

Hash returns the hash of the final noder of the path.

func (Path) IsDir

func (p Path) IsDir() bool

IsDir returns if the final noder of the path is a directory-like noder.

func (Path) Last

func (p Path) Last() Noder

Last returns the final noder in the path.

func (Path) Name

func (p Path) Name() string

Name returns the name of the final noder of the path.

func (Path) NumChildren

func (p Path) NumChildren(ctx context.Context) (int, error)

NumChildren returns the number of children the final noder of the path has.

func (Path) Skip

func (p Path) Skip() bool

func (Path) String

func (p Path) String() string

String returns the full path of the final noder as a string, using "/" as the separator.

type SparseMatcher

type SparseMatcher interface {
	Match(string) bool
}

func NewSparseMatcher

func NewSparseMatcher(dirs []string) SparseMatcher