diff options
Diffstat (limited to 'vendor/gopkg.in/src-d/go-git.v4/utils')
14 files changed, 1970 insertions, 0 deletions
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/binary/read.go b/vendor/gopkg.in/src-d/go-git.v4/utils/binary/read.go new file mode 100644 index 0000000000..50da1ff3e5 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/binary/read.go @@ -0,0 +1,165 @@ +// Package binary implements sintax-sugar functions on top of the standard +// library binary package +package binary + +import ( + "bufio" + "encoding/binary" + "io" + + "gopkg.in/src-d/go-git.v4/plumbing" +) + +// Read reads structured binary data from r into data. Bytes are read and +// decoded in BigEndian order +// https://golang.org/pkg/encoding/binary/#Read +func Read(r io.Reader, data ...interface{}) error { + for _, v := range data { + if err := binary.Read(r, binary.BigEndian, v); err != nil { + return err + } + } + + return nil +} + +// ReadUntil reads from r untin delim is found +func ReadUntil(r io.Reader, delim byte) ([]byte, error) { + var buf [1]byte + value := make([]byte, 0, 16) + for { + if _, err := io.ReadFull(r, buf[:]); err != nil { + if err == io.EOF { + return nil, err + } + + return nil, err + } + + if buf[0] == delim { + return value, nil + } + + value = append(value, buf[0]) + } +} + +// ReadVariableWidthInt reads and returns an int in Git VLQ special format: +// +// Ordinary VLQ has some redundancies, example: the number 358 can be +// encoded as the 2-octet VLQ 0x8166 or the 3-octet VLQ 0x808166 or the +// 4-octet VLQ 0x80808166 and so forth. +// +// To avoid these redundancies, the VLQ format used in Git removes this +// prepending redundancy and extends the representable range of shorter +// VLQs by adding an offset to VLQs of 2 or more octets in such a way +// that the lowest possible value for such an (N+1)-octet VLQ becomes +// exactly one more than the maximum possible value for an N-octet VLQ. +// In particular, since a 1-octet VLQ can store a maximum value of 127, +// the minimum 2-octet VLQ (0x8000) is assigned the value 128 instead of +// 0. Conversely, the maximum value of such a 2-octet VLQ (0xff7f) is +// 16511 instead of just 16383. Similarly, the minimum 3-octet VLQ +// (0x808000) has a value of 16512 instead of zero, which means +// that the maximum 3-octet VLQ (0xffff7f) is 2113663 instead of +// just 2097151. And so forth. +// +// This is how the offset is saved in C: +// +// dheader[pos] = ofs & 127; +// while (ofs >>= 7) +// dheader[--pos] = 128 | (--ofs & 127); +// +func ReadVariableWidthInt(r io.Reader) (int64, error) { + var c byte + if err := Read(r, &c); err != nil { + return 0, err + } + + var v = int64(c & maskLength) + for c&maskContinue > 0 { + v++ + if err := Read(r, &c); err != nil { + return 0, err + } + + v = (v << lengthBits) + int64(c&maskLength) + } + + return v, nil +} + +const ( + maskContinue = uint8(128) // 1000 000 + maskLength = uint8(127) // 0111 1111 + lengthBits = uint8(7) // subsequent bytes has 7 bits to store the length +) + +// ReadUint64 reads 8 bytes and returns them as a BigEndian uint32 +func ReadUint64(r io.Reader) (uint64, error) { + var v uint64 + if err := binary.Read(r, binary.BigEndian, &v); err != nil { + return 0, err + } + + return v, nil +} + +// ReadUint32 reads 4 bytes and returns them as a BigEndian uint32 +func ReadUint32(r io.Reader) (uint32, error) { + var v uint32 + if err := binary.Read(r, binary.BigEndian, &v); err != nil { + return 0, err + } + + return v, nil +} + +// ReadUint16 reads 2 bytes and returns them as a BigEndian uint16 +func ReadUint16(r io.Reader) (uint16, error) { + var v uint16 + if err := binary.Read(r, binary.BigEndian, &v); err != nil { + return 0, err + } + + return v, nil +} + +// ReadHash reads a plumbing.Hash from r +func ReadHash(r io.Reader) (plumbing.Hash, error) { + var h plumbing.Hash + if err := binary.Read(r, binary.BigEndian, h[:]); err != nil { + return plumbing.ZeroHash, err + } + + return h, nil +} + +const sniffLen = 8000 + +// IsBinary detects if data is a binary value based on: +// http://git.kernel.org/cgit/git/git.git/tree/xdiff-interface.c?id=HEAD#n198 +func IsBinary(r io.Reader) (bool, error) { + reader := bufio.NewReader(r) + c := 0 + for { + if c == sniffLen { + break + } + + b, err := reader.ReadByte() + if err == io.EOF { + break + } + if err != nil { + return false, err + } + + if b == byte(0) { + return true, nil + } + + c++ + } + + return false, nil +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/binary/write.go b/vendor/gopkg.in/src-d/go-git.v4/utils/binary/write.go new file mode 100644 index 0000000000..c08c73a06b --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/binary/write.go @@ -0,0 +1,50 @@ +package binary + +import ( + "encoding/binary" + "io" +) + +// Write writes the binary representation of data into w, using BigEndian order +// https://golang.org/pkg/encoding/binary/#Write +func Write(w io.Writer, data ...interface{}) error { + for _, v := range data { + if err := binary.Write(w, binary.BigEndian, v); err != nil { + return err + } + } + + return nil +} + +func WriteVariableWidthInt(w io.Writer, n int64) error { + buf := []byte{byte(n & 0x7f)} + n >>= 7 + for n != 0 { + n-- + buf = append([]byte{0x80 | (byte(n & 0x7f))}, buf...) + n >>= 7 + } + + _, err := w.Write(buf) + + return err +} + +// WriteUint64 writes the binary representation of a uint64 into w, in BigEndian +// order +func WriteUint64(w io.Writer, value uint64) error { + return binary.Write(w, binary.BigEndian, value) +} + +// WriteUint32 writes the binary representation of a uint32 into w, in BigEndian +// order +func WriteUint32(w io.Writer, value uint32) error { + return binary.Write(w, binary.BigEndian, value) +} + +// WriteUint16 writes the binary representation of a uint16 into w, in BigEndian +// order +func WriteUint16(w io.Writer, value uint16) error { + return binary.Write(w, binary.BigEndian, value) +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/diff/diff.go b/vendor/gopkg.in/src-d/go-git.v4/utils/diff/diff.go new file mode 100644 index 0000000000..f49ae55bae --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/diff/diff.go @@ -0,0 +1,45 @@ +// Package diff implements line oriented diffs, similar to the ancient +// Unix diff command. +// +// The current implementation is just a wrapper around Sergi's +// go-diff/diffmatchpatch library, which is a go port of Neil +// Fraser's google-diff-match-patch code +package diff + +import ( + "bytes" + + "github.com/sergi/go-diff/diffmatchpatch" +) + +// Do computes the (line oriented) modifications needed to turn the src +// string into the dst string. +func Do(src, dst string) (diffs []diffmatchpatch.Diff) { + dmp := diffmatchpatch.New() + wSrc, wDst, warray := dmp.DiffLinesToRunes(src, dst) + diffs = dmp.DiffMainRunes(wSrc, wDst, false) + diffs = dmp.DiffCharsToLines(diffs, warray) + return diffs +} + +// Dst computes and returns the destination text. +func Dst(diffs []diffmatchpatch.Diff) string { + var text bytes.Buffer + for _, d := range diffs { + if d.Type != diffmatchpatch.DiffDelete { + text.WriteString(d.Text) + } + } + return text.String() +} + +// Src computes and returns the source text +func Src(diffs []diffmatchpatch.Diff) string { + var text bytes.Buffer + for _, d := range diffs { + if d.Type != diffmatchpatch.DiffInsert { + text.WriteString(d.Text) + } + } + return text.String() +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/ioutil/common.go b/vendor/gopkg.in/src-d/go-git.v4/utils/ioutil/common.go new file mode 100644 index 0000000000..e9dcbfe49b --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/ioutil/common.go @@ -0,0 +1,170 @@ +// Package ioutil implements some I/O utility functions. +package ioutil + +import ( + "bufio" + "context" + "errors" + "io" + + "github.com/jbenet/go-context/io" +) + +type readPeeker interface { + io.Reader + Peek(int) ([]byte, error) +} + +var ( + ErrEmptyReader = errors.New("reader is empty") +) + +// NonEmptyReader takes a reader and returns it if it is not empty, or +// `ErrEmptyReader` if it is empty. If there is an error when reading the first +// byte of the given reader, it will be propagated. +func NonEmptyReader(r io.Reader) (io.Reader, error) { + pr, ok := r.(readPeeker) + if !ok { + pr = bufio.NewReader(r) + } + + _, err := pr.Peek(1) + if err == io.EOF { + return nil, ErrEmptyReader + } + + if err != nil { + return nil, err + } + + return pr, nil +} + +type readCloser struct { + io.Reader + closer io.Closer +} + +func (r *readCloser) Close() error { + return r.closer.Close() +} + +// NewReadCloser creates an `io.ReadCloser` with the given `io.Reader` and +// `io.Closer`. +func NewReadCloser(r io.Reader, c io.Closer) io.ReadCloser { + return &readCloser{Reader: r, closer: c} +} + +type writeCloser struct { + io.Writer + closer io.Closer +} + +func (r *writeCloser) Close() error { + return r.closer.Close() +} + +// NewWriteCloser creates an `io.WriteCloser` with the given `io.Writer` and +// `io.Closer`. +func NewWriteCloser(w io.Writer, c io.Closer) io.WriteCloser { + return &writeCloser{Writer: w, closer: c} +} + +type writeNopCloser struct { + io.Writer +} + +func (writeNopCloser) Close() error { return nil } + +// WriteNopCloser returns a WriteCloser with a no-op Close method wrapping +// the provided Writer w. +func WriteNopCloser(w io.Writer) io.WriteCloser { + return writeNopCloser{w} +} + +// CheckClose calls Close on the given io.Closer. If the given *error points to +// nil, it will be assigned the error returned by Close. Otherwise, any error +// returned by Close will be ignored. CheckClose is usually called with defer. +func CheckClose(c io.Closer, err *error) { + if cerr := c.Close(); cerr != nil && *err == nil { + *err = cerr + } +} + +// NewContextWriter wraps a writer to make it respect given Context. +// If there is a blocking write, the returned Writer will return whenever the +// context is cancelled (the return values are n=0 and err=ctx.Err()). +func NewContextWriter(ctx context.Context, w io.Writer) io.Writer { + return ctxio.NewWriter(ctx, w) +} + +// NewContextReader wraps a reader to make it respect given Context. +// If there is a blocking read, the returned Reader will return whenever the +// context is cancelled (the return values are n=0 and err=ctx.Err()). +func NewContextReader(ctx context.Context, r io.Reader) io.Reader { + return ctxio.NewReader(ctx, r) +} + +// NewContextWriteCloser as NewContextWriter but with io.Closer interface. +func NewContextWriteCloser(ctx context.Context, w io.WriteCloser) io.WriteCloser { + ctxw := ctxio.NewWriter(ctx, w) + return NewWriteCloser(ctxw, w) +} + +// NewContextReadCloser as NewContextReader but with io.Closer interface. +func NewContextReadCloser(ctx context.Context, r io.ReadCloser) io.ReadCloser { + ctxr := ctxio.NewReader(ctx, r) + return NewReadCloser(ctxr, r) +} + +type readerOnError struct { + io.Reader + notify func(error) +} + +// NewReaderOnError returns a io.Reader that call the notify function when an +// unexpected (!io.EOF) error happens, after call Read function. +func NewReaderOnError(r io.Reader, notify func(error)) io.Reader { + return &readerOnError{r, notify} +} + +// NewReadCloserOnError returns a io.ReadCloser that call the notify function +// when an unexpected (!io.EOF) error happens, after call Read function. +func NewReadCloserOnError(r io.ReadCloser, notify func(error)) io.ReadCloser { + return NewReadCloser(NewReaderOnError(r, notify), r) +} + +func (r *readerOnError) Read(buf []byte) (n int, err error) { + n, err = r.Reader.Read(buf) + if err != nil && err != io.EOF { + r.notify(err) + } + + return +} + +type writerOnError struct { + io.Writer + notify func(error) +} + +// NewWriterOnError returns a io.Writer that call the notify function when an +// unexpected (!io.EOF) error happens, after call Write function. +func NewWriterOnError(w io.Writer, notify func(error)) io.Writer { + return &writerOnError{w, notify} +} + +// NewWriteCloserOnError returns a io.WriteCloser that call the notify function +//when an unexpected (!io.EOF) error happens, after call Write function. +func NewWriteCloserOnError(w io.WriteCloser, notify func(error)) io.WriteCloser { + return NewWriteCloser(NewWriterOnError(w, notify), w) +} + +func (r *writerOnError) Write(p []byte) (n int, err error) { + n, err = r.Writer.Write(p) + if err != nil && err != io.EOF { + r.notify(err) + } + + return +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/change.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/change.go new file mode 100644 index 0000000000..0b50ca71d3 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/change.go @@ -0,0 +1,149 @@ +package merkletrie + +import ( + "fmt" + "io" + + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" +) + +// Action values represent the kind of things a Change can represent: +// insertion, deletions or modifications of files. +type Action int + +// The set of possible actions in a change. +const ( + _ Action = iota + Insert + Delete + Modify +) + +// String returns the action as a human readable text. +func (a Action) String() string { + switch a { + case Insert: + return "Insert" + case Delete: + return "Delete" + case Modify: + return "Modify" + default: + panic(fmt.Sprintf("unsupported action: %d", a)) + } +} + +// A Change value represent how a noder has change between to merkletries. +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 +} + +// Action is convenience method that returns what Action c represents. +func (c *Change) Action() (Action, error) { + if c.From == nil && c.To == nil { + return Action(0), fmt.Errorf("malformed change: nil from and to") + } + if c.From == nil { + return Insert, nil + } + if c.To == nil { + return Delete, nil + } + + return Modify, nil +} + +// NewInsert returns a new Change representing the insertion of n. +func NewInsert(n noder.Path) Change { return Change{To: n} } + +// NewDelete returns a new Change representing the deletion of n. +func NewDelete(n noder.Path) Change { return Change{From: n} } + +// NewModify returns a new Change representing that a has been modified and +// it is now b. +func NewModify(a, b noder.Path) Change { + return Change{ + From: a, + To: b, + } +} + +// 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>". +func (c Change) String() string { + action, err := c.Action() + if err != nil { + panic(err) + } + + var path string + if action == Delete { + path = c.From.String() + } else { + path = c.To.String() + } + + return fmt.Sprintf("<%s %s>", action, path) +} + +// Changes is a list of changes between to merkletries. +type Changes []Change + +// NewChanges returns an empty list of changes. +func NewChanges() Changes { + return Changes{} +} + +// Add adds the change c to the list of changes. +func (l *Changes) Add(c Change) { + *l = append(*l, c) +} + +// AddRecursiveInsert adds the required changes to insert all the +// file-like noders found in root, recursively. +func (l *Changes) AddRecursiveInsert(root noder.Path) error { + return l.addRecursive(root, NewInsert) +} + +// AddRecursiveDelete adds the required changes to delete all the +// file-like noders found in root, recursively. +func (l *Changes) AddRecursiveDelete(root noder.Path) error { + return l.addRecursive(root, NewDelete) +} + +type noderToChangeFn func(noder.Path) Change // NewInsert or NewDelete + +func (l *Changes) addRecursive(root noder.Path, ctor noderToChangeFn) error { + if !root.IsDir() { + l.Add(ctor(root)) + return nil + } + + i, err := NewIterFromPath(root) + if err != nil { + return err + } + + var current noder.Path + for { + if current, err = i.Step(); err != nil { + if err == io.EOF { + break + } + return err + } + if current.IsDir() { + continue + } + l.Add(ctor(current)) + } + + return nil +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/difftree.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/difftree.go new file mode 100644 index 0000000000..d57ed13332 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/difftree.go @@ -0,0 +1,424 @@ +package merkletrie + +// The focus of this difftree implementation is to save time by +// skipping whole directories if their hash is the same in both +// trees. +// +// The diff algorithm implemented here is based on the doubleiter +// type defined in this same package; we will iterate over both +// trees at the same time, while comparing the current noders in +// each iterator. Depending on how they differ we will output the +// corresponding chages and move the iterators further over both +// trees. +// +// The table bellow show all the possible comparison results, along +// with what changes should we produce and how to advance the +// iterators. +// +// The table is implemented by the switches in this function, +// diffTwoNodes, diffTwoNodesSameName and diffTwoDirs. +// +// Many Bothans died to bring us this information, make sure you +// understand the table before modifying this code. + +// # Cases +// +// When comparing noders in both trees you will found yourself in +// one of 169 possible cases, but if we ignore moves, we can +// simplify a lot the search space into the following table: +// +// - "-": nothing, no file or directory +// - a<>: an empty file named "a". +// - a<1>: a file named "a", with "1" as its contents. +// - a<2>: a file named "a", with "2" as its contents. +// - a(): an empty dir named "a". +// - a(...): a dir named "a", with some files and/or dirs inside (possibly +// empty). +// - a(;;;): a dir named "a", with some other files and/or dirs inside +// (possibly empty), which different from the ones in "a(...)". +// +// \ to - a<> a<1> a<2> a() a(...) a(;;;) +// from \ +// - 00 01 02 03 04 05 06 +// a<> 10 11 12 13 14 15 16 +// a<1> 20 21 22 23 24 25 26 +// a<2> 30 31 32 33 34 35 36 +// a() 40 41 42 43 44 45 46 +// a(...) 50 51 52 53 54 55 56 +// a(;;;) 60 61 62 63 64 65 66 +// +// Every (from, to) combination in the table is a special case, but +// some of them can be merged into some more general cases, for +// instance 11 and 22 can be merged into the general case: both +// noders are equal. +// +// Here is a full list of all the cases that are similar and how to +// merge them together into more general cases. Each general case +// is labeled with an uppercase letter for further reference, and it +// is followed by the pseudocode of the checks you have to perfrom +// on both noders to see if you are in such a case, the actions to +// perform (i.e. what changes to output) and how to advance the +// iterators of each tree to continue the comparison process. +// +// ## A. Impossible: 00 +// +// ## B. Same thing on both sides: 11, 22, 33, 44, 55, 66 +// - check: `SameName() && SameHash()` +// - action: do nothing. +// - advance: `FromNext(); ToNext()` +// +// ### C. To was created: 01, 02, 03, 04, 05, 06 +// - check: `DifferentName() && ToBeforeFrom()` +// - action: inserRecursively(to) +// - advance: `ToNext()` +// +// ### D. From was deleted: 10, 20, 30, 40, 50, 60 +// - check: `DifferentName() && FromBeforeTo()` +// - action: `DeleteRecursively(from)` +// - advance: `FromNext()` +// +// ### E. Empty file to file with contents: 12, 13 +// - check: `SameName() && DifferentHash() && FromIsFile() && +// ToIsFile() && FromIsEmpty()` +// - action: `modifyFile(from, to)` +// - advance: `FromNext()` or `FromStep()` +// +// ### E'. file with contents to empty file: 21, 31 +// - check: `SameName() && DifferentHash() && FromIsFile() && +// ToIsFile() && ToIsEmpty()` +// - action: `modifyFile(from, to)` +// - advance: `FromNext()` or `FromStep()` +// +// ### F. empty file to empty dir with the same name: 14 +// - check: `SameName() && FromIsFile() && FromIsEmpty() && +// ToIsDir() && ToIsEmpty()` +// - action: `DeleteFile(from); InsertEmptyDir(to)` +// - advance: `FromNext(); ToNext()` +// +// ### F'. empty dir to empty file of the same name: 41 +// - check: `SameName() && FromIsDir() && FromIsEmpty && +// ToIsFile() && ToIsEmpty()` +// - action: `DeleteEmptyDir(from); InsertFile(to)` +// - advance: `FromNext(); ToNext()` or step for any of them. +// +// ### G. empty file to non-empty dir of the same name: 15, 16 +// - check: `SameName() && FromIsFile() && ToIsDir() && +// FromIsEmpty() && ToIsNotEmpty()` +// - action: `DeleteFile(from); InsertDirRecursively(to)` +// - advance: `FromNext(); ToNext()` +// +// ### G'. non-empty dir to empty file of the same name: 51, 61 +// - check: `SameName() && FromIsDir() && FromIsNotEmpty() && +// ToIsFile() && FromIsEmpty()` +// - action: `DeleteDirRecursively(from); InsertFile(to)` +// - advance: `FromNext(); ToNext()` +// +// ### H. modify file contents: 23, 32 +// - check: `SameName() && FromIsFile() && ToIsFile() && +// FromIsNotEmpty() && ToIsNotEmpty()` +// - action: `ModifyFile(from, to)` +// - advance: `FromNext(); ToNext()` +// +// ### I. file with contents to empty dir: 24, 34 +// - check: `SameName() && DifferentHash() && FromIsFile() && +// FromIsNotEmpty() && ToIsDir() && ToIsEmpty()` +// - action: `DeleteFile(from); InsertEmptyDir(to)` +// - advance: `FromNext(); ToNext()` +// +// ### I'. empty dir to file with contents: 42, 43 +// - check: `SameName() && DifferentHash() && FromIsDir() && +// FromIsEmpty() && ToIsFile() && ToIsEmpty()` +// - action: `DeleteDir(from); InsertFile(to)` +// - advance: `FromNext(); ToNext()` +// +// ### J. file with contents to dir with contetns: 25, 26, 35, 36 +// - check: `SameName() && DifferentHash() && FromIsFile() && +// FromIsNotEmpty() && ToIsDir() && ToIsNotEmpty()` +// - action: `DeleteFile(from); InsertDirRecursively(to)` +// - advance: `FromNext(); ToNext()` +// +// ### J'. dir with contetns to file with contents: 52, 62, 53, 63 +// - check: `SameName() && DifferentHash() && FromIsDir() && +// FromIsNotEmpty() && ToIsFile() && ToIsNotEmpty()` +// - action: `DeleteDirRecursively(from); InsertFile(to)` +// - advance: `FromNext(); ToNext()` +// +// ### K. empty dir to dir with contents: 45, 46 +// - check: `SameName() && DifferentHash() && FromIsDir() && +// FromIsEmpty() && ToIsDir() && ToIsNotEmpty()` +// - action: `InsertChildrenRecursively(to)` +// - advance: `FromNext(); ToNext()` +// +// ### K'. dir with contents to empty dir: 54, 64 +// - check: `SameName() && DifferentHash() && FromIsDir() && +// FromIsEmpty() && ToIsDir() && ToIsNotEmpty()` +// - action: `DeleteChildrenRecursively(from)` +// - advance: `FromNext(); ToNext()` +// +// ### L. dir with contents to dir with different contents: 56, 65 +// - check: `SameName() && DifferentHash() && FromIsDir() && +// FromIsNotEmpty() && ToIsDir() && ToIsNotEmpty()` +// - action: nothing +// - advance: `FromStep(); ToStep()` +// +// + +// All these cases can be further simplified by a truth table +// reduction process, in which we gather similar checks together to +// make the final code easier to read and understand. +// +// The first 6 columns are the outputs of the checks to perform on +// both noders. I have labeled them 1 to 6, this is what they mean: +// +// 1: SameName() +// 2: SameHash() +// 3: FromIsDir() +// 4: ToIsDir() +// 5: FromIsEmpty() +// 6: ToIsEmpty() +// +// The from and to columns are a fsnoder example of the elements +// that you will find on each tree under the specified comparison +// results (columns 1 to 6). +// +// The type column identifies the case we are into, from the list above. +// +// The type' column identifies the new set of reduced cases, using +// lowercase letters, and they are explained after the table. +// +// The last column is the set of actions and advances for each case. +// +// "---" means impossible except in case of hash collision. +// +// advance meaning: +// - NN: from.Next(); to.Next() +// - SS: from.Step(); to.Step() +// +// 1 2 3 4 5 6 | from | to |type|type'|action ; advance +// ------------+--------+--------+----+------------------------------------ +// 0 0 0 0 0 0 | | | | | if !SameName() { +// . | | | | | if FromBeforeTo() { +// . | | | D | d | delete(from); from.Next() +// . | | | | | } else { +// . | | | C | c | insert(to); to.Next() +// . | | | | | } +// 0 1 1 1 1 1 | | | | | } +// 1 0 0 0 0 0 | a<1> | a<2> | H | e | modify(from, to); NN +// 1 0 0 0 0 1 | a<1> | a<> | E' | e | modify(from, to); NN +// 1 0 0 0 1 0 | a<> | a<1> | E | e | modify(from, to); NN +// 1 0 0 0 1 1 | ---- | ---- | | e | +// 1 0 0 1 0 0 | a<1> | a(...) | J | f | delete(from); insert(to); NN +// 1 0 0 1 0 1 | a<1> | a() | I | f | delete(from); insert(to); NN +// 1 0 0 1 1 0 | a<> | a(...) | G | f | delete(from); insert(to); NN +// 1 0 0 1 1 1 | a<> | a() | F | f | delete(from); insert(to); NN +// 1 0 1 0 0 0 | a(...) | a<1> | J' | f | delete(from); insert(to); NN +// 1 0 1 0 0 1 | a(...) | a<> | G' | f | delete(from); insert(to); NN +// 1 0 1 0 1 0 | a() | a<1> | I' | f | delete(from); insert(to); NN +// 1 0 1 0 1 1 | a() | a<> | F' | f | delete(from); insert(to); NN +// 1 0 1 1 0 0 | a(...) | a(;;;) | L | g | nothing; SS +// 1 0 1 1 0 1 | a(...) | a() | K' | h | deleteChidren(from); NN +// 1 0 1 1 1 0 | a() | a(...) | K | i | insertChildren(to); NN +// 1 0 1 1 1 1 | ---- | ---- | | | +// 1 1 0 0 0 0 | a<1> | a<1> | B | b | nothing; NN +// 1 1 0 0 0 1 | ---- | ---- | | b | +// 1 1 0 0 1 0 | ---- | ---- | | b | +// 1 1 0 0 1 1 | a<> | a<> | B | b | nothing; NN +// 1 1 0 1 0 0 | ---- | ---- | | b | +// 1 1 0 1 0 1 | ---- | ---- | | b | +// 1 1 0 1 1 0 | ---- | ---- | | b | +// 1 1 0 1 1 1 | ---- | ---- | | b | +// 1 1 1 0 0 0 | ---- | ---- | | b | +// 1 1 1 0 0 1 | ---- | ---- | | b | +// 1 1 1 0 1 0 | ---- | ---- | | b | +// 1 1 1 0 1 1 | ---- | ---- | | b | +// 1 1 1 1 0 0 | a(...) | a(...) | B | b | nothing; NN +// 1 1 1 1 0 1 | ---- | ---- | | b | +// 1 1 1 1 1 0 | ---- | ---- | | b | +// 1 1 1 1 1 1 | a() | a() | B | b | nothing; NN +// +// c and d: +// if !SameName() +// d if FromBeforeTo() +// c else +// b: SameName) && sameHash() +// e: SameName() && !sameHash() && BothAreFiles() +// f: SameName() && !sameHash() && FileAndDir() +// g: SameName() && !sameHash() && BothAreDirs() && NoneIsEmpty +// i: SameName() && !sameHash() && BothAreDirs() && FromIsEmpty +// h: else of i + +import ( + "context" + "errors" + "fmt" + + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" +) + +var ( + ErrCanceled = errors.New("operation canceled") +) + +// DiffTree calculates the list of changes between two merkletries. It +// uses the provided hashEqual callback to compare noders. +func DiffTree(fromTree, toTree noder.Noder, + hashEqual noder.Equal) (Changes, error) { + return DiffTreeContext(context.Background(), fromTree, toTree, hashEqual) +} + +// 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 DiffTreeContext(ctx context.Context, fromTree, toTree noder.Noder, + hashEqual noder.Equal) (Changes, error) { + ret := NewChanges() + + ii, err := newDoubleIter(fromTree, toTree, hashEqual) + if err != nil { + return nil, err + } + + for { + select { + case <-ctx.Done(): + return nil, ErrCanceled + default: + } + + from := ii.from.current + to := ii.to.current + + switch r := ii.remaining(); r { + case noMoreNoders: + return ret, nil + case onlyFromRemains: + if err = ret.AddRecursiveDelete(from); err != nil { + return nil, err + } + if err = ii.nextFrom(); err != nil { + return nil, err + } + case onlyToRemains: + if err = ret.AddRecursiveInsert(to); err != nil { + return nil, err + } + if err = ii.nextTo(); err != nil { + return nil, err + } + case bothHaveNodes: + if err = diffNodes(&ret, ii); err != nil { + return nil, err + } + default: + panic(fmt.Sprintf("unknown remaining value: %d", r)) + } + } +} + +func diffNodes(changes *Changes, ii *doubleIter) error { + from := ii.from.current + to := ii.to.current + var err error + + // compare their full paths as strings + switch from.Compare(to) { + case -1: + if err = changes.AddRecursiveDelete(from); err != nil { + return err + } + if err = ii.nextFrom(); err != nil { + return err + } + case 1: + if err = changes.AddRecursiveInsert(to); err != nil { + return err + } + if err = ii.nextTo(); err != nil { + return err + } + default: + if err := diffNodesSameName(changes, ii); err != nil { + return err + } + } + + return nil +} + +func diffNodesSameName(changes *Changes, ii *doubleIter) error { + from := ii.from.current + to := ii.to.current + + status, err := ii.compare() + if err != nil { + return err + } + + switch { + case status.sameHash: + // do nothing + if err = ii.nextBoth(); err != nil { + return err + } + case status.bothAreFiles: + changes.Add(NewModify(from, to)) + if err = ii.nextBoth(); err != nil { + return err + } + case status.fileAndDir: + if err = changes.AddRecursiveDelete(from); err != nil { + return err + } + if err = changes.AddRecursiveInsert(to); err != nil { + return err + } + if err = ii.nextBoth(); err != nil { + return err + } + case status.bothAreDirs: + if err = diffDirs(changes, ii); err != nil { + return err + } + default: + return fmt.Errorf("bad status from double iterator") + } + + return nil +} + +func diffDirs(changes *Changes, ii *doubleIter) error { + from := ii.from.current + to := ii.to.current + + status, err := ii.compare() + if err != nil { + return err + } + + switch { + case status.fromIsEmptyDir: + if err = changes.AddRecursiveInsert(to); err != nil { + return err + } + if err = ii.nextBoth(); err != nil { + return err + } + case status.toIsEmptyDir: + if err = changes.AddRecursiveDelete(from); err != nil { + return err + } + if err = ii.nextBoth(); err != nil { + return err + } + case !status.fromIsEmptyDir && !status.toIsEmptyDir: + // do nothing + if err = ii.stepBoth(); err != nil { + return err + } + default: + return fmt.Errorf("both dirs are empty but has different hash") + } + + return nil +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doc.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doc.go new file mode 100644 index 0000000000..5204024ad4 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doc.go @@ -0,0 +1,34 @@ +/* +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. +*/ +package merkletrie diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doubleiter.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doubleiter.go new file mode 100644 index 0000000000..e56dee701f --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doubleiter.go @@ -0,0 +1,187 @@ +package merkletrie + +import ( + "fmt" + "io" + + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" +) + +// A doubleIter is a convenience type to keep track of the current +// noders in two merkletries that are going to be iterated in parallel. +// It has methods for: +// +// - iterating over the merkletries, both at the same time or +// individually: nextFrom, nextTo, nextBoth, stepBoth +// +// - checking if there are noders left in one or both of them with the +// remaining method and its associated returned type. +// +// - comparing the current noders of both merkletries in several ways, +// with the compare method and its associated returned type. +type doubleIter struct { + from struct { + iter *Iter + current noder.Path // nil if no more nodes + } + to struct { + iter *Iter + current noder.Path // nil if no more nodes + } + hashEqual noder.Equal +} + +// NewdoubleIter returns a new doubleIter for the merkletries "from" and +// "to". The hashEqual callback function will be used by the doubleIter +// to compare the hash of the noders in the merkletries. The doubleIter +// will be initialized to the first elements in each merkletrie if any. +func newDoubleIter(from, to noder.Noder, hashEqual noder.Equal) ( + *doubleIter, error) { + var ii doubleIter + var err error + + if ii.from.iter, err = NewIter(from); err != nil { + return nil, fmt.Errorf("from: %s", err) + } + if ii.from.current, err = ii.from.iter.Next(); turnEOFIntoNil(err) != nil { + return nil, fmt.Errorf("from: %s", err) + } + + if ii.to.iter, err = NewIter(to); err != nil { + return nil, fmt.Errorf("to: %s", err) + } + if ii.to.current, err = ii.to.iter.Next(); turnEOFIntoNil(err) != nil { + return nil, fmt.Errorf("to: %s", err) + } + + ii.hashEqual = hashEqual + + return &ii, nil +} + +func turnEOFIntoNil(e error) error { + if e != nil && e != io.EOF { + return e + } + return nil +} + +// NextBoth makes d advance to the next noder in both merkletries. If +// any of them is a directory, it skips its contents. +func (d *doubleIter) nextBoth() error { + if err := d.nextFrom(); err != nil { + return err + } + if err := d.nextTo(); err != nil { + return err + } + + return nil +} + +// NextFrom makes d advance to the next noder in the "from" merkletrie, +// skipping its contents if it is a directory. +func (d *doubleIter) nextFrom() (err error) { + d.from.current, err = d.from.iter.Next() + return turnEOFIntoNil(err) +} + +// NextTo makes d advance to the next noder in the "to" merkletrie, +// skipping its contents if it is a directory. +func (d *doubleIter) nextTo() (err error) { + d.to.current, err = d.to.iter.Next() + return turnEOFIntoNil(err) +} + +// StepBoth makes d advance to the next noder in both merkletries, +// getting deeper into directories if that is the case. +func (d *doubleIter) stepBoth() (err error) { + if d.from.current, err = d.from.iter.Step(); turnEOFIntoNil(err) != nil { + return err + } + if d.to.current, err = d.to.iter.Step(); turnEOFIntoNil(err) != nil { + return err + } + return nil +} + +// Remaining returns if there are no more noders in the tree, if both +// have noders or if one of them doesn't. +func (d *doubleIter) remaining() remaining { + if d.from.current == nil && d.to.current == nil { + return noMoreNoders + } + + if d.from.current == nil && d.to.current != nil { + return onlyToRemains + } + + if d.from.current != nil && d.to.current == nil { + return onlyFromRemains + } + + return bothHaveNodes +} + +// Remaining values tells you whether both trees still have noders, or +// only one of them or none of them. +type remaining int + +const ( + noMoreNoders remaining = iota + onlyToRemains + onlyFromRemains + bothHaveNodes +) + +// Compare returns the comparison between the current elements in the +// merkletries. +func (d *doubleIter) compare() (s comparison, err error) { + s.sameHash = d.hashEqual(d.from.current, d.to.current) + + fromIsDir := d.from.current.IsDir() + toIsDir := d.to.current.IsDir() + + s.bothAreDirs = fromIsDir && toIsDir + s.bothAreFiles = !fromIsDir && !toIsDir + s.fileAndDir = !s.bothAreDirs && !s.bothAreFiles + + fromNumChildren, err := d.from.current.NumChildren() + if err != nil { + return comparison{}, fmt.Errorf("from: %s", err) + } + + toNumChildren, err := d.to.current.NumChildren() + if err != nil { + return comparison{}, fmt.Errorf("to: %s", err) + } + + s.fromIsEmptyDir = fromIsDir && fromNumChildren == 0 + s.toIsEmptyDir = toIsDir && toNumChildren == 0 + + return +} + +// Answers to a lot of questions you can ask about how to noders are +// equal or different. +type comparison struct { + // the following are only valid if both nodes have the same name + // (i.e. nameComparison == 0) + + // Do both nodes have the same hash? + sameHash bool + // Are both nodes files? + bothAreFiles bool + + // the following are only valid if any of the noders are dirs, + // this is, if !bothAreFiles + + // Is one a file and the other a dir? + fileAndDir bool + // Are both nodes dirs? + bothAreDirs bool + // Is the from node an empty dir? + fromIsEmptyDir bool + // Is the to Node an empty dir? + toIsEmptyDir bool +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/filesystem/node.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/filesystem/node.go new file mode 100644 index 0000000000..12d00189a3 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/filesystem/node.go @@ -0,0 +1,196 @@ +package filesystem + +import ( + "io" + "os" + "path" + + "gopkg.in/src-d/go-git.v4/plumbing" + "gopkg.in/src-d/go-git.v4/plumbing/filemode" + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" + + "gopkg.in/src-d/go-billy.v4" +) + +var ignore = map[string]bool{ + ".git": true, +} + +// The node represents a file or a directory in a billy.Filesystem. It +// implements the interface noder.Noder of merkletrie package. +// +// This implementation implements a "standard" hash method being able to be +// compared with any other noder.Noder implementation inside of go-git. +type node struct { + fs billy.Filesystem + submodules map[string]plumbing.Hash + + path string + hash []byte + children []noder.Noder + isDir bool +} + +// NewRootNode returns the root node based on a given billy.Filesystem. +// +// In order to provide the submodule hash status, a map[string]plumbing.Hash +// should be provided where the key is the path of the submodule and the commit +// of the submodule HEAD +func NewRootNode( + fs billy.Filesystem, + submodules map[string]plumbing.Hash, +) noder.Noder { + return &node{fs: fs, submodules: submodules, isDir: true} +} + +// Hash the hash of a filesystem is the result of concatenating the computed +// plumbing.Hash of the file as a Blob and its plumbing.FileMode; that way the +// difftree algorithm will detect changes in the contents of files and also in +// their mode. +// +// The hash of a directory is always a 24-bytes slice of zero values +func (n *node) Hash() []byte { + return n.hash +} + +func (n *node) Name() string { + return path.Base(n.path) +} + +func (n *node) IsDir() bool { + return n.isDir +} + +func (n *node) Children() ([]noder.Noder, error) { + if err := n.calculateChildren(); err != nil { + return nil, err + } + + return n.children, nil +} + +func (n *node) NumChildren() (int, error) { + if err := n.calculateChildren(); err != nil { + return -1, err + } + + return len(n.children), nil +} + +func (n *node) calculateChildren() error { + if !n.IsDir() { + return nil + } + + if len(n.children) != 0 { + return nil + } + + files, err := n.fs.ReadDir(n.path) + if err != nil { + if os.IsNotExist(err) { + return nil + } + + return nil + } + + for _, file := range files { + if _, ok := ignore[file.Name()]; ok { + continue + } + + c, err := n.newChildNode(file) + if err != nil { + return err + } + + n.children = append(n.children, c) + } + + return nil +} + +func (n *node) newChildNode(file os.FileInfo) (*node, error) { + path := path.Join(n.path, file.Name()) + + hash, err := n.calculateHash(path, file) + if err != nil { + return nil, err + } + + node := &node{ + fs: n.fs, + submodules: n.submodules, + + path: path, + hash: hash, + isDir: file.IsDir(), + } + + if hash, isSubmodule := n.submodules[path]; isSubmodule { + node.hash = append(hash[:], filemode.Submodule.Bytes()...) + node.isDir = false + } + + return node, nil +} + +func (n *node) calculateHash(path string, file os.FileInfo) ([]byte, error) { + if file.IsDir() { + return make([]byte, 24), nil + } + + var hash plumbing.Hash + var err error + if file.Mode()&os.ModeSymlink != 0 { + hash, err = n.doCalculateHashForSymlink(path, file) + } else { + hash, err = n.doCalculateHashForRegular(path, file) + } + + if err != nil { + return nil, err + } + + mode, err := filemode.NewFromOSFileMode(file.Mode()) + if err != nil { + return nil, err + } + + return append(hash[:], mode.Bytes()...), nil +} + +func (n *node) doCalculateHashForRegular(path string, file os.FileInfo) (plumbing.Hash, error) { + f, err := n.fs.Open(path) + if err != nil { + return plumbing.ZeroHash, err + } + + defer f.Close() + + h := plumbing.NewHasher(plumbing.BlobObject, file.Size()) + if _, err := io.Copy(h, f); err != nil { + return plumbing.ZeroHash, err + } + + return h.Sum(), nil +} + +func (n *node) doCalculateHashForSymlink(path string, file os.FileInfo) (plumbing.Hash, error) { + target, err := n.fs.Readlink(path) + if err != nil { + return plumbing.ZeroHash, err + } + + h := plumbing.NewHasher(plumbing.BlobObject, file.Size()) + if _, err := h.Write([]byte(target)); err != nil { + return plumbing.ZeroHash, err + } + + return h.Sum(), nil +} + +func (n *node) String() string { + return n.path +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/index/node.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/index/node.go new file mode 100644 index 0000000000..9622622483 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/index/node.go @@ -0,0 +1,90 @@ +package index + +import ( + "path" + "strings" + + "gopkg.in/src-d/go-git.v4/plumbing/format/index" + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" +) + +// The node represents a index.Entry or a directory inferred from the path +// of all entries. It implements the interface noder.Noder of merkletrie +// package. +// +// This implementation implements a "standard" hash method being able to be +// compared with any other noder.Noder implementation inside of go-git +type node struct { + path string + entry *index.Entry + children []noder.Noder + isDir bool +} + +// NewRootNode returns the root node of a computed tree from a index.Index, +func NewRootNode(idx *index.Index) noder.Noder { + const rootNode = "" + + m := map[string]*node{rootNode: {isDir: true}} + + for _, e := range idx.Entries { + parts := strings.Split(e.Name, string("/")) + + var fullpath string + for _, part := range parts { + parent := fullpath + fullpath = path.Join(fullpath, part) + + if _, ok := m[fullpath]; ok { + continue + } + + n := &node{path: fullpath} + if fullpath == e.Name { + n.entry = e + } else { + n.isDir = true + } + + m[n.path] = n + m[parent].children = append(m[parent].children, n) + } + } + + return m[rootNode] +} + +func (n *node) String() string { + return n.path +} + +// Hash the hash of a filesystem is a 24-byte slice, is the result of +// concatenating the computed plumbing.Hash of the file as a Blob and its +// plumbing.FileMode; that way the difftree algorithm will detect changes in the +// contents of files and also in their mode. +// +// If the node is computed and not based on a index.Entry the hash is equals +// to a 24-bytes slices of zero values. +func (n *node) Hash() []byte { + if n.entry == nil { + return make([]byte, 24) + } + + return append(n.entry.Hash[:], n.entry.Mode.Bytes()...) +} + +func (n *node) Name() string { + return path.Base(n.path) +} + +func (n *node) IsDir() bool { + return n.isDir +} + +func (n *node) Children() ([]noder.Noder, error) { + return n.children, nil +} + +func (n *node) NumChildren() (int, error) { + return len(n.children), nil +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame/frame.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame/frame.go new file mode 100644 index 0000000000..a0b042ee61 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame/frame.go @@ -0,0 +1,91 @@ +package frame + +import ( + "bytes" + "fmt" + "sort" + "strings" + + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" +) + +// A Frame is a collection of siblings in a trie, sorted alphabetically +// by name. +type Frame struct { + // siblings, sorted in reverse alphabetical order by name + stack []noder.Noder +} + +type byName []noder.Noder + +func (a byName) Len() int { return len(a) } +func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] } +func (a byName) Less(i, j int) bool { + return strings.Compare(a[i].Name(), a[j].Name()) < 0 +} + +// New returns a frame with the children of the provided node. +func New(n noder.Noder) (*Frame, error) { + children, err := n.Children() + if err != nil { + return nil, err + } + + sort.Sort(sort.Reverse(byName(children))) + return &Frame{ + stack: children, + }, nil +} + +// String returns the quoted names of the noders in the frame sorted in +// alphabeticall order by name, surrounded by square brackets and +// separated by comas. +// +// Examples: +// [] +// ["a", "b"] +func (f *Frame) String() string { + var buf bytes.Buffer + _ = buf.WriteByte('[') + + sep := "" + for i := f.Len() - 1; i >= 0; i-- { + _, _ = buf.WriteString(sep) + sep = ", " + _, _ = buf.WriteString(fmt.Sprintf("%q", f.stack[i].Name())) + } + + _ = buf.WriteByte(']') + + return buf.String() +} + +// First returns, but dont extract, the noder with the alphabetically +// smaller name in the frame and true if the frame was not empy. +// Otherwise it returns nil and false. +func (f *Frame) First() (noder.Noder, bool) { + if f.Len() == 0 { + return nil, false + } + + top := f.Len() - 1 + + return f.stack[top], true +} + +// Drop extracts the noder with the alphabetically smaller name in the +// frame or does nothing if the frame was empty. +func (f *Frame) Drop() { + if f.Len() == 0 { + return + } + + top := f.Len() - 1 + f.stack[top] = nil + f.stack = f.stack[:top] +} + +// Len returns the number of noders in the frame. +func (f *Frame) Len() int { + return len(f.stack) +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/iter.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/iter.go new file mode 100644 index 0000000000..b4d4c99a33 --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/iter.go @@ -0,0 +1,216 @@ +package merkletrie + +import ( + "fmt" + "io" + + "gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame" + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" +) + +// 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). +type Iter struct { + // Tells if the iteration has started. + hasStarted bool + // The top of this stack has the current node and its siblings. The + // rest of the stack keeps the ancestors of the current node and + // their corresponding siblings. The current element is always the + // top element of the top frame. + // + // When "step"ping into a node, its children are pushed as a new + // frame. + // + // When "next"ing pass a node, the current element is dropped by + // popping the top frame. + frameStack []*frame.Frame + // The base path used to turn the relative paths used internally by + // the iterator into absolute paths used by external applications. + // For relative iterator this will be nil. + base noder.Path +} + +// 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 NewIter(n noder.Noder) (*Iter, error) { + return newIter(n, nil) +} + +// 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 NewIterFromPath(p noder.Path) (*Iter, error) { + return newIter(p, p) // Path implements Noder +} + +func newIter(root noder.Noder, base noder.Path) (*Iter, error) { + ret := &Iter{ + base: base, + } + + if root == nil { + return ret, nil + } + + frame, err := frame.New(root) + if err != nil { + return nil, err + } + ret.push(frame) + + return ret, nil +} + +func (iter *Iter) top() (*frame.Frame, bool) { + if len(iter.frameStack) == 0 { + return nil, false + } + top := len(iter.frameStack) - 1 + + return iter.frameStack[top], true +} + +func (iter *Iter) push(f *frame.Frame) { + iter.frameStack = append(iter.frameStack, f) +} + +const ( + doDescend = true + dontDescend = false +) + +// 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 *Iter) Next() (noder.Path, error) { + return iter.advance(dontDescend) +} + +// 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 (iter *Iter) Step() (noder.Path, error) { + return iter.advance(doDescend) +} + +// Advances the iterator in the desired direction: descend or +// dontDescend. +// +// Returns the new current element and a nil error on success. If there +// are no more elements in the trie below the base, it returns nil, and +// io.EOF. Returns nil and an error in case of errors. +func (iter *Iter) advance(wantDescend bool) (noder.Path, error) { + current, err := iter.current() + if err != nil { + return nil, err + } + + // The first time we just return the current node. + if !iter.hasStarted { + iter.hasStarted = true + return current, nil + } + + // Advances means getting a next current node, either its first child or + // its next sibling, depending if we must descend or not. + numChildren, err := current.NumChildren() + if err != nil { + return nil, err + } + + mustDescend := numChildren != 0 && wantDescend + if mustDescend { + // descend: add a new frame with the current's children. + frame, err := frame.New(current) + if err != nil { + return nil, err + } + iter.push(frame) + } else { + // don't descend: just drop the current node + iter.drop() + } + + return iter.current() +} + +// Returns the path to the current node, adding the base if there was +// one, and a nil error. If there were no noders left, it returns nil +// and io.EOF. If an error occurred, it returns nil and the error. +func (iter *Iter) current() (noder.Path, error) { + if topFrame, ok := iter.top(); !ok { + return nil, io.EOF + } else if _, ok := topFrame.First(); !ok { + return nil, io.EOF + } + + ret := make(noder.Path, 0, len(iter.base)+len(iter.frameStack)) + + // concat the base... + ret = append(ret, iter.base...) + // ... and the current node and all its ancestors + for i, f := range iter.frameStack { + t, ok := f.First() + if !ok { + panic(fmt.Sprintf("frame %d is empty", i)) + } + ret = append(ret, t) + } + + return ret, nil +} + +// removes the current node if any, and all the frames that become empty as a +// consequence of this action. +func (iter *Iter) drop() { + frame, ok := iter.top() + if !ok { + return + } + + frame.Drop() + // if the frame is empty, remove it and its parent, recursively + if frame.Len() == 0 { + top := len(iter.frameStack) - 1 + iter.frameStack[top] = nil + iter.frameStack = iter.frameStack[:top] + iter.drop() + } +} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/noder.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/noder.go new file mode 100644 index 0000000000..d6b3de4ada --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/noder.go @@ -0,0 +1,59 @@ +// 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. +package noder + +import "fmt" + +// Hasher interface is implemented by types that can tell you +// their hash. +type Hasher interface { + Hash() []byte +} + +// 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 Equal func(a, b Hasher) 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 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() ([]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() (int, error) +} + +// NoChildren represents the children of a noder without children. +var NoChildren = []Noder{} diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/path.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/path.go new file mode 100644 index 0000000000..e9c905c96b --- /dev/null +++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/path.go @@ -0,0 +1,94 @@ +package noder + +import ( + "bytes" + "strings" + + "golang.org/x/text/unicode/norm" +) + +// 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. +type Path []Noder + +// String returns the full path of the final noder as a string, using +// "/" as the separator. +func (p Path) String() string { + var buf bytes.Buffer + sep := "" + for _, e := range p { + _, _ = buf.WriteString(sep) + sep = "/" + _, _ = buf.WriteString(e.Name()) + } + + return buf.String() +} + +// Last returns the final noder in the path. +func (p Path) Last() Noder { + return p[len(p)-1] +} + +// Hash returns the hash of the final noder of the path. +func (p Path) Hash() []byte { + return p.Last().Hash() +} + +// Name returns the name of the final noder of the path. +func (p Path) Name() string { + return p.Last().Name() +} + +// IsDir returns if the final noder of the path is a directory-like +// noder. +func (p Path) IsDir() bool { + return p.Last().IsDir() +} + +// Children returns the children of the final noder in the path. +func (p Path) Children() ([]Noder, error) { + return p.Last().Children() +} + +// NumChildren returns the number of children the final noder of the +// path has. +func (p Path) NumChildren() (int, error) { + return p.Last().NumChildren() +} + +// 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 (p Path) Compare(other Path) int { + i := 0 + for { + switch { + case len(other) == len(p) && i == len(p): + return 0 + case i == len(other): + return 1 + case i == len(p): + return -1 + default: + form := norm.Form(norm.NFC) + this := form.String(p[i].Name()) + that := form.String(other[i].Name()) + + cmp := strings.Compare(this, that) + if cmp != 0 { + return cmp + } + } + i++ + } +} |