aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing
diff options
context:
space:
mode:
Diffstat (limited to 'plumbing')
-rw-r--r--plumbing/object/commit_walker_bfs.go100
-rw-r--r--plumbing/object/commit_walker_ctime.go103
-rw-r--r--plumbing/object/commit_walker_test.go96
3 files changed, 299 insertions, 0 deletions
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() {}
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])
+ }
+}
generated by cgit (git 2.34.1) at 2024-11-11 20:36:39 +0000