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

    Constants

    This section is empty.

    Variables

    View Source
    var (
    	ErrCanceled = errors.New("operation canceled")
    )

    Functions

    This section is empty.

    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 DiffTreeContext

                          func DiffTreeContext(ctx context.Context, 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. Error will be returned if context expires Provided context must be non nil

                            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.

                                              Directories

                                              Path Synopsis
                                              internal
                                              fsnoder
                                              Package fsnoder allows to create merkletrie noders that resemble file systems, from human readable string descriptions.
                                              Package fsnoder allows to create merkletrie noders that resemble file systems, from human readable string descriptions.
                                              Package noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors).
                                              Package noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors).