go-git.v4: gopkg.in/src-d/go-git.v4/utils/merkletrie Index | Files | Directories

package merkletrie

import "gopkg.in/src-d/go-git.v4/utils/merkletrie"

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

Package Files

change.go difftree.go doc.go doubleiter.go iter.go

Variables

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

type Action Uses

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 Uses

func (a Action) String() string

String returns the action as a human readable text.

type Change Uses

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 Uses

func NewDelete(n noder.Path) Change

NewDelete returns a new Change representing the deletion of n.

func NewInsert Uses

func NewInsert(n noder.Path) Change

NewInsert returns a new Change representing the insertion of n.

func NewModify Uses

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 Uses

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

Action is convenience method that returns what Action c represents.

func (Change) String Uses

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 Uses

type Changes []Change

Changes is a list of changes between to merkletries.

func DiffTree Uses

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 Uses

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 Uses

func NewChanges() Changes

NewChanges returns an empty list of changes.

func (*Changes) Add Uses

func (l *Changes) Add(c Change)

Add adds the change c to the list of changes.

func (*Changes) AddRecursiveDelete Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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

PathSynopsis
filesystem
index
internal/frame
internal/fsnoderPackage fsnoder allows to create merkletrie noders that resemble file systems, from human readable string descriptions.
noderPackage noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors).

Package merkletrie imports 6 packages (graph) and is imported by 37 packages. Updated 2019-08-08. Refresh now. Tools for package owners.