merkletrie

Documentation

Overview

Package merkletrie provides support for n-ary trees that are at the same time Merkle trees and Radix trees (tries).

Git trees are Radix n-ary trees in virtue of the names of their tree entries. At the same time, git trees are Merkle trees thanks to their hashes.

This package defines Merkle tries as nodes that should have:

- a hash: the Merkle part of the Merkle trie

- a key: the Radix part of the Merkle trie

The Merkle hash condition is not enforced by this package though. This means that the hash of a node doesn't have to take into account the hashes of their children, which is good for testing purposes.

Nodes in the Merkle trie are abstracted by the Noder interface. The intended use is that git trees implements this interface, either directly or using a simple wrapper.

This package provides an iterator for merkletries that can skip whole directory-like noders and an efficient merkletrie comparison algorithm.

When comparing git trees, the simple approach of alphabetically sorting their elements and comparing the resulting lists is too slow as it depends linearly on the number of files in the trees: When a directory has lots of files but none of them has been modified, this approach is very expensive. We can do better by prunning whole directories that have not change, just by looking at their hashes. This package provides the tools to do exactly that.

Index

• type Action
  • func (a Action) String() string
• type Change
  • func NewDelete(n noder.Path) Change
  • func NewInsert(n noder.Path) Change
  • func NewModify(a, b noder.Path) Change
  • func (c *Change) Action() (Action, error)
  • func (c Change) String() string
• type Changes
  • func DiffTree(fromTree, toTree noder.Noder, hashEqual noder.Equal) (Changes, error)
  • func NewChanges() Changes
  • func (l *Changes) Add(c Change)
  • func (l *Changes) AddRecursiveDelete(root noder.Path) error
  • func (l *Changes) AddRecursiveInsert(root noder.Path) error
• type Iter
  • func NewIter(n noder.Noder) (*Iter, error)
  • func NewIterFromPath(p noder.Path) (*Iter, error)
  • func (iter *Iter) Next() (noder.Path, error)
  • func (iter *Iter) Step() (noder.Path, error)

Types

type Action

type Action int

Action values represent the kind of things a Change can represent: insertion, deletions or modifications of files.

const (
	Insert Action
	Delete
	Modify
)

The set of possible actions in a change.

func (Action) String

func (a Action) String() string

String returns the action as a human readable text.

type Change

type Change struct {
	// The noder before the change or nil if it was inserted.
	From noder.Path
	// The noder after the change or nil if it was deleted.
	To noder.Path
}

A Change value represent how a noder has change between to merkletries.

func NewDelete

func NewDelete(n noder.Path) Change

NewDelete returns a new Change representing the deletion of n.

func NewInsert

func NewInsert(n noder.Path) Change

NewInsert returns a new Change representing the insertion of n.

func NewModify

func NewModify(a, b noder.Path) Change

NewModify returns a new Change representing that a has been modified and it is now b.

func (*Change) Action

func (c *Change) Action() (Action, error)

Action is convenience method that returns what Action c represents.

func (Change) String

func (c Change) String() string

String returns a single change in human readable form, using the format: '<' + action + space + path + '>'. The contents of the file before or after the change are not included in this format.

Example: inserting a file at the path a/b/c.txt will return "<Insert a/b/c.txt>".

type Changes

type Changes []Change

Changes is a list of changes between to merkletries.

func DiffTree

func DiffTree(fromTree, toTree noder.Noder,
	hashEqual noder.Equal) (Changes, error)

DiffTree calculates the list of changes between two merkletries. It uses the provided hashEqual callback to compare noders.

func NewChanges

func NewChanges() Changes

NewChanges returns an empty list of changes.

func (*Changes) Add

func (l *Changes) Add(c Change)

Add adds the change c to the list of changes.

func (*Changes) AddRecursiveDelete

func (l *Changes) AddRecursiveDelete(root noder.Path) error

AddRecursiveDelete adds the required changes to delete all the file-like noders found in root, recursively.

func (*Changes) AddRecursiveInsert

func (l *Changes) AddRecursiveInsert(root noder.Path) error

AddRecursiveInsert adds the required changes to insert all the file-like noders found in root, recursively.

type Iter

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

Iter is an iterator for merkletries (only the trie part of the merkletrie is relevant here, it does not use the Hasher interface).

The iteration is performed in depth-first pre-order. Entries at each depth are traversed in (case-sensitive) alphabetical order.

This is the kind of traversal you will expect when listing ordinary files and directories recursively, for example:

     Trie           Traversal order
     ----           ---------------
      .
    / | \           c
   /  |  \          d/
  d   c   z   ===>  d/a
 / \                d/b
b   a               z

This iterator is somewhat especial as you can chose to skip whole "directories" when iterating:

- The Step method will iterate normally.

- the Next method will not descend deeper into the tree.

For example, if the iterator is at `d/`, the Step method will return `d/a` while the Next would have returned `z` instead (skipping `d/` and its descendants). The name of the these two methods are based on the well known "next" and "step" operations, quite common in debuggers, like gdb.

The paths returned by the iterator will be relative, if the iterator was created from a single node, or absolute, if the iterator was created from the path to the node (the path will be prefixed to all returned paths).

func NewIter

func NewIter(n noder.Noder) (*Iter, error)

NewIter returns a new relative iterator using the provider noder as its unnamed root. When iterating, all returned paths will be relative to node.

func NewIterFromPath

func NewIterFromPath(p noder.Path) (*Iter, error)

NewIterFromPath returns a new absolute iterator from the noder at the end of the path p. When iterating, all returned paths will be absolute, using the root of the path p as their root.

func (*Iter) Next

func (iter *Iter) Next() (noder.Path, error)

Next returns the path of the next node without descending deeper into the trie and nil. If there are no more entries in the trie it returns nil and io.EOF. In case of error, it will return nil and the error.

func (*Iter) Step

func (iter *Iter) Step() (noder.Path, error)

Step returns the path to the next node in the trie, descending deeper into it if needed, and nil. If there are no more nodes in the trie, it returns nil and io.EOF. In case of error, it will return nil and the error.