package merkletrie

Import Path
	github.com/go-git/go-git/v5/utils/merkletrie (on go.dev)

Dependency Relation
	imports 6 packages, and imported by 2 packages


Involved Source Files

	      change.go
	      difftree.go
	
		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.

	      doubleiter.go
	      iter.go


Package-Level Type Names (total 8, in which 4 are exported)


	/* sort exporteds by:  |  */
	
		Action values represent the kind of things a Change can represent:
		insertion, deletions or modifications of files.

		
			
				String returns the action as a human readable text.

		
			 T : expvar.Var
			 T : fmt.Stringer
			
		
			func (*Change).Action() (Action, error)
			func github.com/go-git/go-git/v5/plumbing/object.(*Change).Action() (Action, error)
		
			
		
			const Delete
			const Insert
			const Modify


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

		
			
				The noder before the change or nil if it was inserted.

			
				The noder after the change or nil if it was deleted.

		
			
				Action is convenience method that returns what Action c represents.

			
				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>".

		
			 T : expvar.Var
			 T : fmt.Stringer
			
		
			func NewDelete(n noder.Path) Change
			func NewInsert(n noder.Path) Change
			func NewModify(a, b noder.Path) Change
		
			func (*Changes).Add(c Change)
			


	
		Changes is a list of changes between to merkletries.

		
			
				Add adds the change c to the list of changes.

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

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

			
		
			func DiffTree(fromTree, toTree noder.Noder, hashEqual noder.Equal) (Changes, error)
			func DiffTreeContext(ctx context.Context, fromTree, toTree noder.Noder, hashEqual noder.Equal) (Changes, error)
			func NewChanges() Changes
			
		
			


	
		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).

		
			
		
			
				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.

			
				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.

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


	


Package-Level Functions (total 14, in which 8 are exported)


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


	
		DiffTreeContext 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


	
		NewChanges returns an empty list of changes.


	
		NewDelete returns a new Change representing the deletion of n.


	
		NewInsert returns a new Change representing the insertion of n.


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


	
		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.


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


	


Package-Level Variables (only one, which is exported)


	
		ErrCanceled is returned whenever the operation is canceled.




Package-Level Constants (total 9, in which 3 are exported)


	
		The set of possible actions in a change.


	
		The set of possible actions in a change.


	
		The set of possible actions in a change.