From d0fcd7136a31f3f693cb63e6e2733435e4240258 Mon Sep 17 00:00:00 2001 From: Saeed Rasooli Date: Mon, 5 Mar 2018 16:42:58 +0800 Subject: add LogOrder, LogOptions.Order, implement Order=LogOrderCommitterTime and Order=LogOrderBSF Signed-off-by: Saeed Rasooli --- plumbing/object/commit_walker_bfs.go | 100 ++++++++++++++++++++++++++++++++ plumbing/object/commit_walker_ctime.go | 103 +++++++++++++++++++++++++++++++++ 2 files changed, 203 insertions(+) create mode 100644 plumbing/object/commit_walker_bfs.go create mode 100644 plumbing/object/commit_walker_ctime.go (limited to 'plumbing') diff --git a/plumbing/object/commit_walker_bfs.go b/plumbing/object/commit_walker_bfs.go new file mode 100644 index 0000000..aef1cf2 --- /dev/null +++ b/plumbing/object/commit_walker_bfs.go @@ -0,0 +1,100 @@ +package object + +import ( + "io" + + "gopkg.in/src-d/go-git.v4/plumbing" + "gopkg.in/src-d/go-git.v4/plumbing/storer" +) + +type bfsCommitIterator struct { + seenExternal map[plumbing.Hash]bool + seen map[plumbing.Hash]bool + queue []*Commit +} + +// NewCommitIterBSF returns a CommitIter that walks the commit history, +// starting at the given commit and visiting its parents in pre-order. +// The given callback will be called for each visited commit. Each commit will +// be visited only once. If the callback returns an error, walking will stop +// and will return the error. Other errors might be returned if the history +// cannot be traversed (e.g. missing objects). Ignore allows to skip some +// commits from being iterated. +func NewCommitIterBSF( + c *Commit, + seenExternal map[plumbing.Hash]bool, + ignore []plumbing.Hash, +) CommitIter { + seen := make(map[plumbing.Hash]bool) + for _, h := range ignore { + seen[h] = true + } + + return &bfsCommitIterator{ + seenExternal: seenExternal, + seen: seen, + queue: []*Commit{c}, + } +} + +func (w *bfsCommitIterator) appendHash(store storer.EncodedObjectStorer, h plumbing.Hash) error { + if w.seen[h] || w.seenExternal[h] { + return nil + } + c, err := GetCommit(store, h) + if err != nil { + return err + } + w.queue = append(w.queue, c) + return nil +} + +func (w *bfsCommitIterator) Next() (*Commit, error) { + var c *Commit + for { + if len(w.queue) == 0 { + return nil, io.EOF + } + c = w.queue[0] + w.queue = w.queue[1:] + + if w.seen[c.Hash] || w.seenExternal[c.Hash] { + continue + } + + w.seen[c.Hash] = true + + for _, h := range c.ParentHashes { + err := w.appendHash(c.s, h) + if err != nil { + return nil, nil + } + } + + return c, nil + } +} + +func (w *bfsCommitIterator) ForEach(cb func(*Commit) error) error { + for { + c, err := w.Next() + if err == io.EOF { + break + } + if err != nil { + return err + } + + err = cb(c) + if err == storer.ErrStop { + break + } + if err != nil { + return err + } + } + + return nil +} + +func (w *bfsCommitIterator) Close() {} diff --git a/plumbing/object/commit_walker_ctime.go b/plumbing/object/commit_walker_ctime.go new file mode 100644 index 0000000..0191614 --- /dev/null +++ b/plumbing/object/commit_walker_ctime.go @@ -0,0 +1,103 @@ +package object + +import ( + "io" + + "github.com/emirpasic/gods/trees/binaryheap" + + "gopkg.in/src-d/go-git.v4/plumbing" + "gopkg.in/src-d/go-git.v4/plumbing/storer" +) + +type commitIteratorByCTime struct { + seenExternal map[plumbing.Hash]bool + seen map[plumbing.Hash]bool + heap *binaryheap.Heap +} + +// NewCommitIterCTime returns a CommitIter that walks the commit history, +// starting at the given commit and visiting its parents while preserving Committer Time order. +// this appears to be the closest order to `git log` +// The given callback will be called for each visited commit. Each commit will +// be visited only once. If the callback returns an error, walking will stop +// and will return the error. Other errors might be returned if the history +// cannot be traversed (e.g. missing objects). Ignore allows to skip some +// commits from being iterated. +func NewCommitIterCTime( + c *Commit, + seenExternal map[plumbing.Hash]bool, + ignore []plumbing.Hash, +) CommitIter { + seen := make(map[plumbing.Hash]bool) + for _, h := range ignore { + seen[h] = true + } + + heap := binaryheap.NewWith(func(a, b interface{}) int { + if a.(*Commit).Committer.When.Before(b.(*Commit).Committer.When) { + return 1 + } + return -1 + }) + heap.Push(c) + + return &commitIteratorByCTime{ + seenExternal: seenExternal, + seen: seen, + heap: heap, + } +} + +func (w *commitIteratorByCTime) Next() (*Commit, error) { + var c *Commit + for { + cIn, ok := w.heap.Pop() + if !ok { + return nil, io.EOF + } + c = cIn.(*Commit) + + if w.seen[c.Hash] || w.seenExternal[c.Hash] { + continue + } + + w.seen[c.Hash] = true + + for _, h := range c.ParentHashes { + if w.seen[h] || w.seenExternal[h] { + continue + } + pc, err := GetCommit(c.s, h) + if err != nil { + return nil, err + } + w.heap.Push(pc) + } + + return c, nil + } +} + +func (w *commitIteratorByCTime) ForEach(cb func(*Commit) error) error { + for { + c, err := w.Next() + if err == io.EOF { + break + } + if err != nil { + return err + } + + err = cb(c) + if err == storer.ErrStop { + break + } + if err != nil { + return err + } + } + + return nil +} + +func (w *commitIteratorByCTime) Close() {} -- cgit