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/object') 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 From 3b75e0c904a81069d623a3361954242c668f496d Mon Sep 17 00:00:00 2001 From: Saeed Rasooli Date: Tue, 6 Mar 2018 12:11:13 +0800 Subject: add tests for NewCommitIterCTime and NewCommitIterBSF Signed-off-by: Saeed Rasooli --- plumbing/object/commit_walker_test.go | 96 +++++++++++++++++++++++++++++++++++ 1 file changed, 96 insertions(+) (limited to 'plumbing/object') diff --git a/plumbing/object/commit_walker_test.go b/plumbing/object/commit_walker_test.go index a27104e..9b0a260 100644 --- a/plumbing/object/commit_walker_test.go +++ b/plumbing/object/commit_walker_test.go @@ -132,3 +132,99 @@ func (s *CommitWalkerSuite) TestCommitPostIteratorWithIgnore(c *C) { c.Assert(commit.Hash.String(), Equals, expected[i]) } } + +func (s *CommitWalkerSuite) TestCommitCTimeIterator(c *C) { + commit := s.commit(c, s.Fixture.Head) + + var commits []*Commit + NewCommitIterCTime(commit, nil, nil).ForEach(func(c *Commit) error { + commits = append(commits, c) + return nil + }) + + c.Assert(commits, HasLen, 8) + + expected := []string{ + "6ecf0ef2c2dffb796033e5a02219af86ec6584e5", // 2015-04-05T23:30:47+02:00 + "918c48b83bd081e863dbe1b80f8998f058cd8294", // 2015-03-31T13:56:18+02:00 + "af2d6a6954d532f8ffb47615169c8fdf9d383a1a", // 2015-03-31T13:51:51+02:00 + "1669dce138d9b841a518c64b10914d88f5e488ea", // 2015-03-31T13:48:14+02:00 + "a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69", // 2015-03-31T13:47:14+02:00 + "35e85108805c84807bc66a02d91535e1e24b38b9", // 2015-03-31T13:46:24+02:00 + "b8e471f58bcbca63b07bda20e428190409c2db47", // 2015-03-31T13:44:52+02:00 + "b029517f6300c2da0f4b651b8642506cd6aaf45d", // 2015-03-31T13:42:21+02:00 + } + for i, commit := range commits { + c.Assert(commit.Hash.String(), Equals, expected[i]) + } +} + +func (s *CommitWalkerSuite) TestCommitCTimeIteratorWithIgnore(c *C) { + commit := s.commit(c, s.Fixture.Head) + + var commits []*Commit + NewCommitIterCTime(commit, nil, []plumbing.Hash{ + plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"), + }).ForEach(func(c *Commit) error { + commits = append(commits, c) + return nil + }) + + c.Assert(commits, HasLen, 2) + + expected := []string{ + "6ecf0ef2c2dffb796033e5a02219af86ec6584e5", + "918c48b83bd081e863dbe1b80f8998f058cd8294", + } + for i, commit := range commits { + c.Assert(commit.Hash.String(), Equals, expected[i]) + } +} + +func (s *CommitWalkerSuite) TestCommitBSFIterator(c *C) { + commit := s.commit(c, s.Fixture.Head) + + var commits []*Commit + NewCommitIterBSF(commit, nil, nil).ForEach(func(c *Commit) error { + commits = append(commits, c) + return nil + }) + + c.Assert(commits, HasLen, 8) + + expected := []string{ + "6ecf0ef2c2dffb796033e5a02219af86ec6584e5", + "918c48b83bd081e863dbe1b80f8998f058cd8294", + "af2d6a6954d532f8ffb47615169c8fdf9d383a1a", + "1669dce138d9b841a518c64b10914d88f5e488ea", + "35e85108805c84807bc66a02d91535e1e24b38b9", + "a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69", + "b029517f6300c2da0f4b651b8642506cd6aaf45d", + "b8e471f58bcbca63b07bda20e428190409c2db47", + } + for i, commit := range commits { + c.Assert(commit.Hash.String(), Equals, expected[i]) + } +} + +func (s *CommitWalkerSuite) TestCommitBSFIteratorWithIgnore(c *C) { + commit := s.commit(c, s.Fixture.Head) + + var commits []*Commit + NewCommitIterBSF(commit, nil, []plumbing.Hash{ + plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"), + }).ForEach(func(c *Commit) error { + commits = append(commits, c) + return nil + }) + + c.Assert(commits, HasLen, 2) + + expected := []string{ + "6ecf0ef2c2dffb796033e5a02219af86ec6584e5", + "918c48b83bd081e863dbe1b80f8998f058cd8294", + } + for i, commit := range commits { + c.Assert(commit.Hash.String(), Equals, expected[i]) + } +} -- cgit