diff options
Diffstat (limited to 'plumbing/object/commitgraph')
-rw-r--r-- | plumbing/object/commitgraph/commitnode.go | 200 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_graph.go | 271 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_object.go | 187 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_test.go | 301 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_walker_author_order.go | 61 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_walker_ctime.go | 211 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_walker_date_order.go | 41 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_walker_helper.go | 164 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_walker_test.go | 187 | ||||
-rw-r--r-- | plumbing/object/commitgraph/commitnode_walker_topo_order.go | 161 |
10 files changed, 1212 insertions, 572 deletions
diff --git a/plumbing/object/commitgraph/commitnode.go b/plumbing/object/commitgraph/commitnode.go index 7abc58b..47227d4 100644 --- a/plumbing/object/commitgraph/commitnode.go +++ b/plumbing/object/commitgraph/commitnode.go @@ -1,98 +1,102 @@ -package commitgraph
-
-import (
- "io"
- "time"
-
- "github.com/go-git/go-git/v5/plumbing"
- "github.com/go-git/go-git/v5/plumbing/object"
- "github.com/go-git/go-git/v5/plumbing/storer"
-)
-
-// CommitNode is generic interface encapsulating a lightweight commit object retrieved
-// from CommitNodeIndex
-type CommitNode interface {
- // ID returns the Commit object id referenced by the commit graph node.
- ID() plumbing.Hash
- // Tree returns the Tree referenced by the commit graph node.
- Tree() (*object.Tree, error)
- // CommitTime returns the Commiter.When time of the Commit referenced by the commit graph node.
- CommitTime() time.Time
- // NumParents returns the number of parents in a commit.
- NumParents() int
- // ParentNodes return a CommitNodeIter for parents of specified node.
- ParentNodes() CommitNodeIter
- // ParentNode returns the ith parent of a commit.
- ParentNode(i int) (CommitNode, error)
- // ParentHashes returns hashes of the parent commits for a specified node
- ParentHashes() []plumbing.Hash
- // Generation returns the generation of the commit for reachability analysis.
- // Objects with newer generation are not reachable from objects of older generation.
- Generation() uint64
- // Commit returns the full commit object from the node
- Commit() (*object.Commit, error)
-}
-
-// CommitNodeIndex is generic interface encapsulating an index of CommitNode objects
-type CommitNodeIndex interface {
- // Get returns a commit node from a commit hash
- Get(hash plumbing.Hash) (CommitNode, error)
-}
-
-// CommitNodeIter is a generic closable interface for iterating over commit nodes.
-type CommitNodeIter interface {
- Next() (CommitNode, error)
- ForEach(func(CommitNode) error) error
- Close()
-}
-
-// parentCommitNodeIter provides an iterator for parent commits from associated CommitNodeIndex.
-type parentCommitNodeIter struct {
- node CommitNode
- i int
-}
-
-func newParentgraphCommitNodeIter(node CommitNode) CommitNodeIter {
- return &parentCommitNodeIter{node, 0}
-}
-
-// Next moves the iterator to the next commit and returns a pointer to it. If
-// there are no more commits, it returns io.EOF.
-func (iter *parentCommitNodeIter) Next() (CommitNode, error) {
- obj, err := iter.node.ParentNode(iter.i)
- if err == object.ErrParentNotFound {
- return nil, io.EOF
- }
- if err == nil {
- iter.i++
- }
-
- return obj, err
-}
-
-// ForEach call the cb function for each commit contained on this iter until
-// an error appends or the end of the iter is reached. If ErrStop is sent
-// the iteration is stopped but no error is returned. The iterator is closed.
-func (iter *parentCommitNodeIter) ForEach(cb func(CommitNode) error) error {
- for {
- obj, err := iter.Next()
- if err != nil {
- if err == io.EOF {
- return nil
- }
-
- return err
- }
-
- if err := cb(obj); err != nil {
- if err == storer.ErrStop {
- return nil
- }
-
- return err
- }
- }
-}
-
-func (iter *parentCommitNodeIter) Close() {
-}
+package commitgraph + +import ( + "io" + "time" + + "github.com/go-git/go-git/v5/plumbing" + "github.com/go-git/go-git/v5/plumbing/object" + "github.com/go-git/go-git/v5/plumbing/storer" +) + +// CommitNode is generic interface encapsulating a lightweight commit object retrieved +// from CommitNodeIndex +type CommitNode interface { + // ID returns the Commit object id referenced by the commit graph node. + ID() plumbing.Hash + // Tree returns the Tree referenced by the commit graph node. + Tree() (*object.Tree, error) + // CommitTime returns the Committer.When time of the Commit referenced by the commit graph node. + CommitTime() time.Time + // NumParents returns the number of parents in a commit. + NumParents() int + // ParentNodes return a CommitNodeIter for parents of specified node. + ParentNodes() CommitNodeIter + // ParentNode returns the ith parent of a commit. + ParentNode(i int) (CommitNode, error) + // ParentHashes returns hashes of the parent commits for a specified node + ParentHashes() []plumbing.Hash + // Generation returns the generation of the commit for reachability analysis. + // Objects with newer generation are not reachable from objects of older generation. + Generation() uint64 + // GenerationV2 stores the corrected commit date for the commits + // It combines the contents of the GDA2 and GDO2 sections of the commit-graph + // with the commit time portion of the CDAT section. + GenerationV2() uint64 + // Commit returns the full commit object from the node + Commit() (*object.Commit, error) +} + +// CommitNodeIndex is generic interface encapsulating an index of CommitNode objects +type CommitNodeIndex interface { + // Get returns a commit node from a commit hash + Get(hash plumbing.Hash) (CommitNode, error) +} + +// CommitNodeIter is a generic closable interface for iterating over commit nodes. +type CommitNodeIter interface { + Next() (CommitNode, error) + ForEach(func(CommitNode) error) error + Close() +} + +// parentCommitNodeIter provides an iterator for parent commits from associated CommitNodeIndex. +type parentCommitNodeIter struct { + node CommitNode + i int +} + +func newParentgraphCommitNodeIter(node CommitNode) CommitNodeIter { + return &parentCommitNodeIter{node, 0} +} + +// Next moves the iterator to the next commit and returns a pointer to it. If +// there are no more commits, it returns io.EOF. +func (iter *parentCommitNodeIter) Next() (CommitNode, error) { + obj, err := iter.node.ParentNode(iter.i) + if err == object.ErrParentNotFound { + return nil, io.EOF + } + if err == nil { + iter.i++ + } + + return obj, err +} + +// ForEach call the cb function for each commit contained on this iter until +// an error appends or the end of the iter is reached. If ErrStop is sent +// the iteration is stopped but no error is returned. The iterator is closed. +func (iter *parentCommitNodeIter) ForEach(cb func(CommitNode) error) error { + for { + obj, err := iter.Next() + if err != nil { + if err == io.EOF { + return nil + } + + return err + } + + if err := cb(obj); err != nil { + if err == storer.ErrStop { + return nil + } + + return err + } + } +} + +func (iter *parentCommitNodeIter) Close() { +} diff --git a/plumbing/object/commitgraph/commitnode_graph.go b/plumbing/object/commitgraph/commitnode_graph.go index 8e5d4e3..0f51e3b 100644 --- a/plumbing/object/commitgraph/commitnode_graph.go +++ b/plumbing/object/commitgraph/commitnode_graph.go @@ -1,131 +1,140 @@ -package commitgraph
-
-import (
- "fmt"
- "time"
-
- "github.com/go-git/go-git/v5/plumbing"
- "github.com/go-git/go-git/v5/plumbing/format/commitgraph"
- "github.com/go-git/go-git/v5/plumbing/object"
- "github.com/go-git/go-git/v5/plumbing/storer"
-)
-
-// graphCommitNode is a reduced representation of Commit as presented in the commit
-// graph file (commitgraph.Node). It is merely useful as an optimization for walking
-// the commit graphs.
-//
-// graphCommitNode implements the CommitNode interface.
-type graphCommitNode struct {
- // Hash for the Commit object
- hash plumbing.Hash
- // Index of the node in the commit graph file
- index int
-
- commitData *commitgraph.CommitData
- gci *graphCommitNodeIndex
-}
-
-// graphCommitNodeIndex is an index that can load CommitNode objects from both the commit
-// graph files and the object store.
-//
-// graphCommitNodeIndex implements the CommitNodeIndex interface
-type graphCommitNodeIndex struct {
- commitGraph commitgraph.Index
- s storer.EncodedObjectStorer
-}
-
-// NewGraphCommitNodeIndex returns CommitNodeIndex implementation that uses commit-graph
-// files as backing storage and falls back to object storage when necessary
-func NewGraphCommitNodeIndex(commitGraph commitgraph.Index, s storer.EncodedObjectStorer) CommitNodeIndex {
- return &graphCommitNodeIndex{commitGraph, s}
-}
-
-func (gci *graphCommitNodeIndex) Get(hash plumbing.Hash) (CommitNode, error) {
- // Check the commit graph first
- parentIndex, err := gci.commitGraph.GetIndexByHash(hash)
- if err == nil {
- parent, err := gci.commitGraph.GetCommitDataByIndex(parentIndex)
- if err != nil {
- return nil, err
- }
-
- return &graphCommitNode{
- hash: hash,
- index: parentIndex,
- commitData: parent,
- gci: gci,
- }, nil
- }
-
- // Fallback to loading full commit object
- commit, err := object.GetCommit(gci.s, hash)
- if err != nil {
- return nil, err
- }
-
- return &objectCommitNode{
- nodeIndex: gci,
- commit: commit,
- }, nil
-}
-
-func (c *graphCommitNode) ID() plumbing.Hash {
- return c.hash
-}
-
-func (c *graphCommitNode) Tree() (*object.Tree, error) {
- return object.GetTree(c.gci.s, c.commitData.TreeHash)
-}
-
-func (c *graphCommitNode) CommitTime() time.Time {
- return c.commitData.When
-}
-
-func (c *graphCommitNode) NumParents() int {
- return len(c.commitData.ParentIndexes)
-}
-
-func (c *graphCommitNode) ParentNodes() CommitNodeIter {
- return newParentgraphCommitNodeIter(c)
-}
-
-func (c *graphCommitNode) ParentNode(i int) (CommitNode, error) {
- if i < 0 || i >= len(c.commitData.ParentIndexes) {
- return nil, object.ErrParentNotFound
- }
-
- parent, err := c.gci.commitGraph.GetCommitDataByIndex(c.commitData.ParentIndexes[i])
- if err != nil {
- return nil, err
- }
-
- return &graphCommitNode{
- hash: c.commitData.ParentHashes[i],
- index: c.commitData.ParentIndexes[i],
- commitData: parent,
- gci: c.gci,
- }, nil
-}
-
-func (c *graphCommitNode) ParentHashes() []plumbing.Hash {
- return c.commitData.ParentHashes
-}
-
-func (c *graphCommitNode) Generation() uint64 {
- // If the commit-graph file was generated with older Git version that
- // set the generation to zero for every commit the generation assumption
- // is still valid. It is just less useful.
- return uint64(c.commitData.Generation)
-}
-
-func (c *graphCommitNode) Commit() (*object.Commit, error) {
- return object.GetCommit(c.gci.s, c.hash)
-}
-
-func (c *graphCommitNode) String() string {
- return fmt.Sprintf(
- "%s %s\nDate: %s",
- plumbing.CommitObject, c.ID(),
- c.CommitTime().Format(object.DateFormat),
- )
-}
+package commitgraph + +import ( + "fmt" + "time" + + "github.com/go-git/go-git/v5/plumbing" + commitgraph "github.com/go-git/go-git/v5/plumbing/format/commitgraph/v2" + "github.com/go-git/go-git/v5/plumbing/object" + "github.com/go-git/go-git/v5/plumbing/storer" +) + +// graphCommitNode is a reduced representation of Commit as presented in the commit +// graph file (commitgraph.Node). It is merely useful as an optimization for walking +// the commit graphs. +// +// graphCommitNode implements the CommitNode interface. +type graphCommitNode struct { + // Hash for the Commit object + hash plumbing.Hash + // Index of the node in the commit graph file + index uint32 + + commitData *commitgraph.CommitData + gci *graphCommitNodeIndex +} + +// graphCommitNodeIndex is an index that can load CommitNode objects from both the commit +// graph files and the object store. +// +// graphCommitNodeIndex implements the CommitNodeIndex interface +type graphCommitNodeIndex struct { + commitGraph commitgraph.Index + s storer.EncodedObjectStorer +} + +// NewGraphCommitNodeIndex returns CommitNodeIndex implementation that uses commit-graph +// files as backing storage and falls back to object storage when necessary +func NewGraphCommitNodeIndex(commitGraph commitgraph.Index, s storer.EncodedObjectStorer) CommitNodeIndex { + return &graphCommitNodeIndex{commitGraph, s} +} + +func (gci *graphCommitNodeIndex) Get(hash plumbing.Hash) (CommitNode, error) { + if gci.commitGraph != nil { + // Check the commit graph first + parentIndex, err := gci.commitGraph.GetIndexByHash(hash) + if err == nil { + parent, err := gci.commitGraph.GetCommitDataByIndex(parentIndex) + if err != nil { + return nil, err + } + + return &graphCommitNode{ + hash: hash, + index: parentIndex, + commitData: parent, + gci: gci, + }, nil + } + } + + // Fallback to loading full commit object + commit, err := object.GetCommit(gci.s, hash) + if err != nil { + return nil, err + } + + return &objectCommitNode{ + nodeIndex: gci, + commit: commit, + }, nil +} + +func (c *graphCommitNode) ID() plumbing.Hash { + return c.hash +} + +func (c *graphCommitNode) Tree() (*object.Tree, error) { + return object.GetTree(c.gci.s, c.commitData.TreeHash) +} + +func (c *graphCommitNode) CommitTime() time.Time { + return c.commitData.When +} + +func (c *graphCommitNode) NumParents() int { + return len(c.commitData.ParentIndexes) +} + +func (c *graphCommitNode) ParentNodes() CommitNodeIter { + return newParentgraphCommitNodeIter(c) +} + +func (c *graphCommitNode) ParentNode(i int) (CommitNode, error) { + if i < 0 || i >= len(c.commitData.ParentIndexes) { + return nil, object.ErrParentNotFound + } + + parent, err := c.gci.commitGraph.GetCommitDataByIndex(c.commitData.ParentIndexes[i]) + if err != nil { + return nil, err + } + + return &graphCommitNode{ + hash: c.commitData.ParentHashes[i], + index: c.commitData.ParentIndexes[i], + commitData: parent, + gci: c.gci, + }, nil +} + +func (c *graphCommitNode) ParentHashes() []plumbing.Hash { + return c.commitData.ParentHashes +} + +func (c *graphCommitNode) Generation() uint64 { + // If the commit-graph file was generated with older Git version that + // set the generation to zero for every commit the generation assumption + // is still valid. It is just less useful. + return c.commitData.Generation +} + +func (c *graphCommitNode) GenerationV2() uint64 { + // If the commit-graph file was generated with older Git version that + // set the generation to zero for every commit the generation assumption + // is still valid. It is just less useful. + return c.commitData.GenerationV2 +} + +func (c *graphCommitNode) Commit() (*object.Commit, error) { + return object.GetCommit(c.gci.s, c.hash) +} + +func (c *graphCommitNode) String() string { + return fmt.Sprintf( + "%s %s\nDate: %s", + plumbing.CommitObject, c.ID(), + c.CommitTime().Format(object.DateFormat), + ) +} diff --git a/plumbing/object/commitgraph/commitnode_object.go b/plumbing/object/commitgraph/commitnode_object.go index bdf8cb7..7256bed 100644 --- a/plumbing/object/commitgraph/commitnode_object.go +++ b/plumbing/object/commitgraph/commitnode_object.go @@ -1,90 +1,97 @@ -package commitgraph
-
-import (
- "math"
- "time"
-
- "github.com/go-git/go-git/v5/plumbing"
- "github.com/go-git/go-git/v5/plumbing/object"
- "github.com/go-git/go-git/v5/plumbing/storer"
-)
-
-// objectCommitNode is a representation of Commit as presented in the GIT object format.
-//
-// objectCommitNode implements the CommitNode interface.
-type objectCommitNode struct {
- nodeIndex CommitNodeIndex
- commit *object.Commit
-}
-
-// NewObjectCommitNodeIndex returns CommitNodeIndex implementation that uses
-// only object storage to load the nodes
-func NewObjectCommitNodeIndex(s storer.EncodedObjectStorer) CommitNodeIndex {
- return &objectCommitNodeIndex{s}
-}
-
-func (oci *objectCommitNodeIndex) Get(hash plumbing.Hash) (CommitNode, error) {
- commit, err := object.GetCommit(oci.s, hash)
- if err != nil {
- return nil, err
- }
-
- return &objectCommitNode{
- nodeIndex: oci,
- commit: commit,
- }, nil
-}
-
-// objectCommitNodeIndex is an index that can load CommitNode objects only from the
-// object store.
-//
-// objectCommitNodeIndex implements the CommitNodeIndex interface
-type objectCommitNodeIndex struct {
- s storer.EncodedObjectStorer
-}
-
-func (c *objectCommitNode) CommitTime() time.Time {
- return c.commit.Committer.When
-}
-
-func (c *objectCommitNode) ID() plumbing.Hash {
- return c.commit.ID()
-}
-
-func (c *objectCommitNode) Tree() (*object.Tree, error) {
- return c.commit.Tree()
-}
-
-func (c *objectCommitNode) NumParents() int {
- return c.commit.NumParents()
-}
-
-func (c *objectCommitNode) ParentNodes() CommitNodeIter {
- return newParentgraphCommitNodeIter(c)
-}
-
-func (c *objectCommitNode) ParentNode(i int) (CommitNode, error) {
- if i < 0 || i >= len(c.commit.ParentHashes) {
- return nil, object.ErrParentNotFound
- }
-
- // Note: It's necessary to go through CommitNodeIndex here to ensure
- // that if the commit-graph file covers only part of the history we
- // start using it when that part is reached.
- return c.nodeIndex.Get(c.commit.ParentHashes[i])
-}
-
-func (c *objectCommitNode) ParentHashes() []plumbing.Hash {
- return c.commit.ParentHashes
-}
-
-func (c *objectCommitNode) Generation() uint64 {
- // Commit nodes representing objects outside of the commit graph can never
- // be reached by objects from the commit-graph thus we return the highest
- // possible value.
- return math.MaxUint64
-}
-
-func (c *objectCommitNode) Commit() (*object.Commit, error) {
- return c.commit, nil
-}
+package commitgraph + +import ( + "math" + "time" + + "github.com/go-git/go-git/v5/plumbing" + "github.com/go-git/go-git/v5/plumbing/object" + "github.com/go-git/go-git/v5/plumbing/storer" +) + +// objectCommitNode is a representation of Commit as presented in the GIT object format. +// +// objectCommitNode implements the CommitNode interface. +type objectCommitNode struct { + nodeIndex CommitNodeIndex + commit *object.Commit +} + +// NewObjectCommitNodeIndex returns CommitNodeIndex implementation that uses +// only object storage to load the nodes +func NewObjectCommitNodeIndex(s storer.EncodedObjectStorer) CommitNodeIndex { + return &objectCommitNodeIndex{s} +} + +func (oci *objectCommitNodeIndex) Get(hash plumbing.Hash) (CommitNode, error) { + commit, err := object.GetCommit(oci.s, hash) + if err != nil { + return nil, err + } + + return &objectCommitNode{ + nodeIndex: oci, + commit: commit, + }, nil +} + +// objectCommitNodeIndex is an index that can load CommitNode objects only from the +// object store. +// +// objectCommitNodeIndex implements the CommitNodeIndex interface +type objectCommitNodeIndex struct { + s storer.EncodedObjectStorer +} + +func (c *objectCommitNode) CommitTime() time.Time { + return c.commit.Committer.When +} + +func (c *objectCommitNode) ID() plumbing.Hash { + return c.commit.ID() +} + +func (c *objectCommitNode) Tree() (*object.Tree, error) { + return c.commit.Tree() +} + +func (c *objectCommitNode) NumParents() int { + return c.commit.NumParents() +} + +func (c *objectCommitNode) ParentNodes() CommitNodeIter { + return newParentgraphCommitNodeIter(c) +} + +func (c *objectCommitNode) ParentNode(i int) (CommitNode, error) { + if i < 0 || i >= len(c.commit.ParentHashes) { + return nil, object.ErrParentNotFound + } + + // Note: It's necessary to go through CommitNodeIndex here to ensure + // that if the commit-graph file covers only part of the history we + // start using it when that part is reached. + return c.nodeIndex.Get(c.commit.ParentHashes[i]) +} + +func (c *objectCommitNode) ParentHashes() []plumbing.Hash { + return c.commit.ParentHashes +} + +func (c *objectCommitNode) Generation() uint64 { + // Commit nodes representing objects outside of the commit graph can never + // be reached by objects from the commit-graph thus we return the highest + // possible value. + return math.MaxUint64 +} + +func (c *objectCommitNode) GenerationV2() uint64 { + // Commit nodes representing objects outside of the commit graph can never + // be reached by objects from the commit-graph thus we return the highest + // possible value. + return math.MaxUint64 +} + +func (c *objectCommitNode) Commit() (*object.Commit, error) { + return c.commit, nil +} diff --git a/plumbing/object/commitgraph/commitnode_test.go b/plumbing/object/commitgraph/commitnode_test.go index 6c9a643..441ff6f 100644 --- a/plumbing/object/commitgraph/commitnode_test.go +++ b/plumbing/object/commitgraph/commitnode_test.go @@ -1,148 +1,153 @@ -package commitgraph
-
-import (
- "path"
- "testing"
-
- "github.com/go-git/go-git/v5/plumbing"
- "github.com/go-git/go-git/v5/plumbing/cache"
- "github.com/go-git/go-git/v5/plumbing/format/commitgraph"
- "github.com/go-git/go-git/v5/plumbing/format/packfile"
- "github.com/go-git/go-git/v5/storage/filesystem"
-
- fixtures "github.com/go-git/go-git-fixtures/v4"
- . "gopkg.in/check.v1"
-)
-
-func Test(t *testing.T) { TestingT(t) }
-
-type CommitNodeSuite struct {
- fixtures.Suite
-}
-
-var _ = Suite(&CommitNodeSuite{})
-
-func unpackRepositry(f *fixtures.Fixture) *filesystem.Storage {
- storer := filesystem.NewStorage(f.DotGit(), cache.NewObjectLRUDefault())
- p := f.Packfile()
- defer p.Close()
- packfile.UpdateObjectStorage(storer, p)
- return storer
-}
-
-func testWalker(c *C, nodeIndex CommitNodeIndex) {
- head, err := nodeIndex.Get(plumbing.NewHash("b9d69064b190e7aedccf84731ca1d917871f8a1c"))
- c.Assert(err, IsNil)
-
- iter := NewCommitNodeIterCTime(
- head,
- nil,
- nil,
- )
-
- var commits []CommitNode
- iter.ForEach(func(c CommitNode) error {
- commits = append(commits, c)
- return nil
- })
-
- c.Assert(commits, HasLen, 9)
-
- expected := []string{
- "b9d69064b190e7aedccf84731ca1d917871f8a1c",
- "6f6c5d2be7852c782be1dd13e36496dd7ad39560",
- "a45273fe2d63300e1962a9e26a6b15c276cd7082",
- "c0edf780dd0da6a65a7a49a86032fcf8a0c2d467",
- "bb13916df33ed23004c3ce9ed3b8487528e655c1",
- "03d2c021ff68954cf3ef0a36825e194a4b98f981",
- "ce275064ad67d51e99f026084e20827901a8361c",
- "e713b52d7e13807e87a002e812041f248db3f643",
- "347c91919944a68e9413581a1bc15519550a3afe",
- }
- for i, commit := range commits {
- c.Assert(commit.ID().String(), Equals, expected[i])
- }
-}
-
-func testParents(c *C, nodeIndex CommitNodeIndex) {
- merge3, err := nodeIndex.Get(plumbing.NewHash("6f6c5d2be7852c782be1dd13e36496dd7ad39560"))
- c.Assert(err, IsNil)
-
- var parents []CommitNode
- merge3.ParentNodes().ForEach(func(c CommitNode) error {
- parents = append(parents, c)
- return nil
- })
-
- c.Assert(parents, HasLen, 3)
-
- expected := []string{
- "ce275064ad67d51e99f026084e20827901a8361c",
- "bb13916df33ed23004c3ce9ed3b8487528e655c1",
- "a45273fe2d63300e1962a9e26a6b15c276cd7082",
- }
- for i, parent := range parents {
- c.Assert(parent.ID().String(), Equals, expected[i])
- }
-}
-
-func testCommitAndTree(c *C, nodeIndex CommitNodeIndex) {
- merge3node, err := nodeIndex.Get(plumbing.NewHash("6f6c5d2be7852c782be1dd13e36496dd7ad39560"))
- c.Assert(err, IsNil)
- merge3commit, err := merge3node.Commit()
- c.Assert(err, IsNil)
- c.Assert(merge3node.ID().String(), Equals, merge3commit.ID().String())
- tree, err := merge3node.Tree()
- c.Assert(err, IsNil)
- c.Assert(tree.ID().String(), Equals, merge3commit.TreeHash.String())
-}
-
-func (s *CommitNodeSuite) TestObjectGraph(c *C) {
- f := fixtures.ByTag("commit-graph").One()
- storer := unpackRepositry(f)
-
- nodeIndex := NewObjectCommitNodeIndex(storer)
- testWalker(c, nodeIndex)
- testParents(c, nodeIndex)
- testCommitAndTree(c, nodeIndex)
-}
-
-func (s *CommitNodeSuite) TestCommitGraph(c *C) {
- f := fixtures.ByTag("commit-graph").One()
- storer := unpackRepositry(f)
- reader, err := storer.Filesystem().Open(path.Join("objects", "info", "commit-graph"))
- c.Assert(err, IsNil)
- defer reader.Close()
- index, err := commitgraph.OpenFileIndex(reader)
- c.Assert(err, IsNil)
-
- nodeIndex := NewGraphCommitNodeIndex(index, storer)
- testWalker(c, nodeIndex)
- testParents(c, nodeIndex)
- testCommitAndTree(c, nodeIndex)
-}
-
-func (s *CommitNodeSuite) TestMixedGraph(c *C) {
- f := fixtures.ByTag("commit-graph").One()
- storer := unpackRepositry(f)
-
- // Take the commit-graph file and copy it to memory index without the last commit
- reader, err := storer.Filesystem().Open(path.Join("objects", "info", "commit-graph"))
- c.Assert(err, IsNil)
- defer reader.Close()
- fileIndex, err := commitgraph.OpenFileIndex(reader)
- c.Assert(err, IsNil)
- memoryIndex := commitgraph.NewMemoryIndex()
- for i, hash := range fileIndex.Hashes() {
- if hash.String() != "b9d69064b190e7aedccf84731ca1d917871f8a1c" {
- node, err := fileIndex.GetCommitDataByIndex(i)
- c.Assert(err, IsNil)
- memoryIndex.Add(hash, node)
- }
- }
-
- nodeIndex := NewGraphCommitNodeIndex(memoryIndex, storer)
- testWalker(c, nodeIndex)
- testParents(c, nodeIndex)
- testCommitAndTree(c, nodeIndex)
-}
+package commitgraph + +import ( + "path" + "testing" + + "github.com/go-git/go-git/v5/plumbing" + "github.com/go-git/go-git/v5/plumbing/cache" + commitgraph "github.com/go-git/go-git/v5/plumbing/format/commitgraph/v2" + "github.com/go-git/go-git/v5/plumbing/format/packfile" + "github.com/go-git/go-git/v5/storage/filesystem" + + fixtures "github.com/go-git/go-git-fixtures/v4" + . "gopkg.in/check.v1" +) + +func Test(t *testing.T) { TestingT(t) } + +type CommitNodeSuite struct { + fixtures.Suite +} + +var _ = Suite(&CommitNodeSuite{}) + +func unpackRepository(f *fixtures.Fixture) *filesystem.Storage { + storer := filesystem.NewStorage(f.DotGit(), cache.NewObjectLRUDefault()) + p := f.Packfile() + defer p.Close() + packfile.UpdateObjectStorage(storer, p) + return storer +} + +func testWalker(c *C, nodeIndex CommitNodeIndex) { + head, err := nodeIndex.Get(plumbing.NewHash("b9d69064b190e7aedccf84731ca1d917871f8a1c")) + c.Assert(err, IsNil) + + iter := NewCommitNodeIterCTime( + head, + nil, + nil, + ) + + var commits []CommitNode + iter.ForEach(func(c CommitNode) error { + commits = append(commits, c) + return nil + }) + + c.Assert(commits, HasLen, 9) + + expected := []string{ + "b9d69064b190e7aedccf84731ca1d917871f8a1c", + "6f6c5d2be7852c782be1dd13e36496dd7ad39560", + "a45273fe2d63300e1962a9e26a6b15c276cd7082", + "c0edf780dd0da6a65a7a49a86032fcf8a0c2d467", + "bb13916df33ed23004c3ce9ed3b8487528e655c1", + "03d2c021ff68954cf3ef0a36825e194a4b98f981", + "ce275064ad67d51e99f026084e20827901a8361c", + "e713b52d7e13807e87a002e812041f248db3f643", + "347c91919944a68e9413581a1bc15519550a3afe", + } + for i, commit := range commits { + c.Assert(commit.ID().String(), Equals, expected[i]) + } +} + +func testParents(c *C, nodeIndex CommitNodeIndex) { + merge3, err := nodeIndex.Get(plumbing.NewHash("6f6c5d2be7852c782be1dd13e36496dd7ad39560")) + c.Assert(err, IsNil) + + var parents []CommitNode + merge3.ParentNodes().ForEach(func(c CommitNode) error { + parents = append(parents, c) + return nil + }) + + c.Assert(parents, HasLen, 3) + + expected := []string{ + "ce275064ad67d51e99f026084e20827901a8361c", + "bb13916df33ed23004c3ce9ed3b8487528e655c1", + "a45273fe2d63300e1962a9e26a6b15c276cd7082", + } + for i, parent := range parents { + c.Assert(parent.ID().String(), Equals, expected[i]) + } +} + +func testCommitAndTree(c *C, nodeIndex CommitNodeIndex) { + merge3node, err := nodeIndex.Get(plumbing.NewHash("6f6c5d2be7852c782be1dd13e36496dd7ad39560")) + c.Assert(err, IsNil) + merge3commit, err := merge3node.Commit() + c.Assert(err, IsNil) + c.Assert(merge3node.ID().String(), Equals, merge3commit.ID().String()) + tree, err := merge3node.Tree() + c.Assert(err, IsNil) + c.Assert(tree.ID().String(), Equals, merge3commit.TreeHash.String()) +} + +func (s *CommitNodeSuite) TestObjectGraph(c *C) { + f := fixtures.ByTag("commit-graph").One() + storer := unpackRepository(f) + + nodeIndex := NewObjectCommitNodeIndex(storer) + testWalker(c, nodeIndex) + testParents(c, nodeIndex) + testCommitAndTree(c, nodeIndex) +} + +func (s *CommitNodeSuite) TestCommitGraph(c *C) { + f := fixtures.ByTag("commit-graph").One() + storer := unpackRepository(f) + reader, err := storer.Filesystem().Open(path.Join("objects", "info", "commit-graph")) + c.Assert(err, IsNil) + defer reader.Close() + index, err := commitgraph.OpenFileIndex(reader) + c.Assert(err, IsNil) + defer index.Close() + + nodeIndex := NewGraphCommitNodeIndex(index, storer) + testWalker(c, nodeIndex) + testParents(c, nodeIndex) + testCommitAndTree(c, nodeIndex) +} + +func (s *CommitNodeSuite) TestMixedGraph(c *C) { + f := fixtures.ByTag("commit-graph").One() + storer := unpackRepository(f) + + // Take the commit-graph file and copy it to memory index without the last commit + reader, err := storer.Filesystem().Open(path.Join("objects", "info", "commit-graph")) + c.Assert(err, IsNil) + defer reader.Close() + fileIndex, err := commitgraph.OpenFileIndex(reader) + c.Assert(err, IsNil) + defer fileIndex.Close() + + memoryIndex := commitgraph.NewMemoryIndex() + defer memoryIndex.Close() + + for i, hash := range fileIndex.Hashes() { + if hash.String() != "b9d69064b190e7aedccf84731ca1d917871f8a1c" { + node, err := fileIndex.GetCommitDataByIndex(uint32(i)) + c.Assert(err, IsNil) + memoryIndex.Add(hash, node) + } + } + + nodeIndex := NewGraphCommitNodeIndex(memoryIndex, storer) + testWalker(c, nodeIndex) + testParents(c, nodeIndex) + testCommitAndTree(c, nodeIndex) +} diff --git a/plumbing/object/commitgraph/commitnode_walker_author_order.go b/plumbing/object/commitgraph/commitnode_walker_author_order.go new file mode 100644 index 0000000..f5b23cc --- /dev/null +++ b/plumbing/object/commitgraph/commitnode_walker_author_order.go @@ -0,0 +1,61 @@ +package commitgraph + +import ( + "github.com/go-git/go-git/v5/plumbing" + + "github.com/emirpasic/gods/trees/binaryheap" +) + +// NewCommitNodeIterAuthorDateOrder returns a CommitNodeIter that walks the commit history, +// starting at the given commit and visiting its parents in Author Time order but with the +// constraint that no parent is emitted before its children are emitted. +// +// This matches `git log --author-order` +// +// This ordering requires that commit objects need to be loaded into memory - thus this +// ordering is likely to be slower than other orderings. +func NewCommitNodeIterAuthorDateOrder(c CommitNode, + seenExternal map[plumbing.Hash]bool, + ignore []plumbing.Hash, +) CommitNodeIter { + seen := make(map[plumbing.Hash]struct{}) + for _, h := range ignore { + seen[h] = struct{}{} + } + for h, ext := range seenExternal { + if ext { + seen[h] = struct{}{} + } + } + inCounts := make(map[plumbing.Hash]int) + + exploreHeap := &commitNodeHeap{binaryheap.NewWith(generationAndDateOrderComparator)} + exploreHeap.Push(c) + + visitHeap := &commitNodeHeap{binaryheap.NewWith(func(left, right interface{}) int { + leftCommit, err := left.(CommitNode).Commit() + if err != nil { + return -1 + } + rightCommit, err := right.(CommitNode).Commit() + if err != nil { + return -1 + } + + switch { + case rightCommit.Author.When.Before(leftCommit.Author.When): + return -1 + case leftCommit.Author.When.Before(rightCommit.Author.When): + return 1 + } + return 0 + })} + visitHeap.Push(c) + + return &commitNodeIteratorTopological{ + exploreStack: exploreHeap, + visitStack: visitHeap, + inCounts: inCounts, + ignore: seen, + } +} diff --git a/plumbing/object/commitgraph/commitnode_walker_ctime.go b/plumbing/object/commitgraph/commitnode_walker_ctime.go index 281f10b..3ab9e6e 100644 --- a/plumbing/object/commitgraph/commitnode_walker_ctime.go +++ b/plumbing/object/commitgraph/commitnode_walker_ctime.go @@ -1,105 +1,106 @@ -package commitgraph
-
-import (
- "io"
-
- "github.com/go-git/go-git/v5/plumbing"
- "github.com/go-git/go-git/v5/plumbing/storer"
-
- "github.com/emirpasic/gods/trees/binaryheap"
-)
-
-type commitNodeIteratorByCTime struct {
- heap *binaryheap.Heap
- seenExternal map[plumbing.Hash]bool
- seen map[plumbing.Hash]bool
-}
-
-// NewCommitNodeIterCTime returns a CommitNodeIter 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 NewCommitNodeIterCTime(
- c CommitNode,
- seenExternal map[plumbing.Hash]bool,
- ignore []plumbing.Hash,
-) CommitNodeIter {
- seen := make(map[plumbing.Hash]bool)
- for _, h := range ignore {
- seen[h] = true
- }
-
- heap := binaryheap.NewWith(func(a, b interface{}) int {
- if a.(CommitNode).CommitTime().Before(b.(CommitNode).CommitTime()) {
- return 1
- }
- return -1
- })
-
- heap.Push(c)
-
- return &commitNodeIteratorByCTime{
- heap: heap,
- seenExternal: seenExternal,
- seen: seen,
- }
-}
-
-func (w *commitNodeIteratorByCTime) Next() (CommitNode, error) {
- var c CommitNode
- for {
- cIn, ok := w.heap.Pop()
- if !ok {
- return nil, io.EOF
- }
- c = cIn.(CommitNode)
- cID := c.ID()
-
- if w.seen[cID] || w.seenExternal[cID] {
- continue
- }
-
- w.seen[cID] = true
-
- for i, h := range c.ParentHashes() {
- if w.seen[h] || w.seenExternal[h] {
- continue
- }
- pc, err := c.ParentNode(i)
- if err != nil {
- return nil, err
- }
- w.heap.Push(pc)
- }
-
- return c, nil
- }
-}
-
-func (w *commitNodeIteratorByCTime) ForEach(cb func(CommitNode) 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 *commitNodeIteratorByCTime) Close() {}
+package commitgraph + +import ( + "io" + + "github.com/go-git/go-git/v5/plumbing" + "github.com/go-git/go-git/v5/plumbing/storer" + + "github.com/emirpasic/gods/trees/binaryheap" +) + +type commitNodeIteratorByCTime struct { + heap *binaryheap.Heap + seenExternal map[plumbing.Hash]bool + seen map[plumbing.Hash]bool +} + +// NewCommitNodeIterCTime returns a CommitNodeIter that walks the commit history, +// starting at the given commit and visiting its parents while preserving Committer Time order. +// this is close in order to `git log` but does not guarantee topological order and will +// order things incorrectly occasionally. +// 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 NewCommitNodeIterCTime( + c CommitNode, + seenExternal map[plumbing.Hash]bool, + ignore []plumbing.Hash, +) CommitNodeIter { + seen := make(map[plumbing.Hash]bool) + for _, h := range ignore { + seen[h] = true + } + + heap := binaryheap.NewWith(func(a, b interface{}) int { + if a.(CommitNode).CommitTime().Before(b.(CommitNode).CommitTime()) { + return 1 + } + return -1 + }) + + heap.Push(c) + + return &commitNodeIteratorByCTime{ + heap: heap, + seenExternal: seenExternal, + seen: seen, + } +} + +func (w *commitNodeIteratorByCTime) Next() (CommitNode, error) { + var c CommitNode + for { + cIn, ok := w.heap.Pop() + if !ok { + return nil, io.EOF + } + c = cIn.(CommitNode) + cID := c.ID() + + if w.seen[cID] || w.seenExternal[cID] { + continue + } + + w.seen[cID] = true + + for i, h := range c.ParentHashes() { + if w.seen[h] || w.seenExternal[h] { + continue + } + pc, err := c.ParentNode(i) + if err != nil { + return nil, err + } + w.heap.Push(pc) + } + + return c, nil + } +} + +func (w *commitNodeIteratorByCTime) ForEach(cb func(CommitNode) 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 *commitNodeIteratorByCTime) Close() {} diff --git a/plumbing/object/commitgraph/commitnode_walker_date_order.go b/plumbing/object/commitgraph/commitnode_walker_date_order.go new file mode 100644 index 0000000..659a4fa --- /dev/null +++ b/plumbing/object/commitgraph/commitnode_walker_date_order.go @@ -0,0 +1,41 @@ +package commitgraph + +import ( + "github.com/go-git/go-git/v5/plumbing" + + "github.com/emirpasic/gods/trees/binaryheap" +) + +// NewCommitNodeIterDateOrder returns a CommitNodeIter that walks the commit history, +// starting at the given commit and visiting its parents in Committer Time and Generation order, +// but with the constraint that no parent is emitted before its children are emitted. +// +// This matches `git log --date-order` +func NewCommitNodeIterDateOrder(c CommitNode, + seenExternal map[plumbing.Hash]bool, + ignore []plumbing.Hash, +) CommitNodeIter { + seen := make(map[plumbing.Hash]struct{}) + for _, h := range ignore { + seen[h] = struct{}{} + } + for h, ext := range seenExternal { + if ext { + seen[h] = struct{}{} + } + } + inCounts := make(map[plumbing.Hash]int) + + exploreHeap := &commitNodeHeap{binaryheap.NewWith(generationAndDateOrderComparator)} + exploreHeap.Push(c) + + visitHeap := &commitNodeHeap{binaryheap.NewWith(generationAndDateOrderComparator)} + visitHeap.Push(c) + + return &commitNodeIteratorTopological{ + exploreStack: exploreHeap, + visitStack: visitHeap, + inCounts: inCounts, + ignore: seen, + } +} diff --git a/plumbing/object/commitgraph/commitnode_walker_helper.go b/plumbing/object/commitgraph/commitnode_walker_helper.go new file mode 100644 index 0000000..c54f6ca --- /dev/null +++ b/plumbing/object/commitgraph/commitnode_walker_helper.go @@ -0,0 +1,164 @@ +package commitgraph + +import ( + "math" + + "github.com/go-git/go-git/v5/plumbing" + + "github.com/emirpasic/gods/trees/binaryheap" +) + +// commitNodeStackable represents a common interface between heaps and stacks +type commitNodeStackable interface { + Push(c CommitNode) + Pop() (CommitNode, bool) + Peek() (CommitNode, bool) + Size() int +} + +// commitNodeLifo is a stack implementation using an underlying slice +type commitNodeLifo struct { + l []CommitNode +} + +// Push pushes a new CommitNode to the stack +func (l *commitNodeLifo) Push(c CommitNode) { + l.l = append(l.l, c) +} + +// Pop pops the most recently added CommitNode from the stack +func (l *commitNodeLifo) Pop() (CommitNode, bool) { + if len(l.l) == 0 { + return nil, false + } + c := l.l[len(l.l)-1] + l.l = l.l[:len(l.l)-1] + return c, true +} + +// Peek returns the most recently added CommitNode from the stack without removing it +func (l *commitNodeLifo) Peek() (CommitNode, bool) { + if len(l.l) == 0 { + return nil, false + } + return l.l[len(l.l)-1], true +} + +// Size returns the number of CommitNodes in the stack +func (l *commitNodeLifo) Size() int { + return len(l.l) +} + +// commitNodeHeap is a stack implementation using an underlying binary heap +type commitNodeHeap struct { + *binaryheap.Heap +} + +// Push pushes a new CommitNode to the heap +func (h *commitNodeHeap) Push(c CommitNode) { + h.Heap.Push(c) +} + +// Pop removes top element on heap and returns it, or nil if heap is empty. +// Second return parameter is true, unless the heap was empty and there was nothing to pop. +func (h *commitNodeHeap) Pop() (CommitNode, bool) { + c, ok := h.Heap.Pop() + if !ok { + return nil, false + } + return c.(CommitNode), true +} + +// Peek returns top element on the heap without removing it, or nil if heap is empty. +// Second return parameter is true, unless the heap was empty and there was nothing to peek. +func (h *commitNodeHeap) Peek() (CommitNode, bool) { + c, ok := h.Heap.Peek() + if !ok { + return nil, false + } + return c.(CommitNode), true +} + +// Size returns number of elements within the heap. +func (h *commitNodeHeap) Size() int { + return h.Heap.Size() +} + +// generationAndDateOrderComparator compares two CommitNode objects based on their generation and commit time. +// If the left CommitNode object is in a higher generation or is newer than the right one, it returns a -1. +// If the left CommitNode object is in a lower generation or is older than the right one, it returns a 1. +// If the two CommitNode objects have the same commit time and generation, it returns 0. +func generationAndDateOrderComparator(left, right interface{}) int { + leftCommit := left.(CommitNode) + rightCommit := right.(CommitNode) + + // if GenerationV2 is MaxUint64, then the node is not in the graph + if leftCommit.GenerationV2() == math.MaxUint64 { + if rightCommit.GenerationV2() == math.MaxUint64 { + switch { + case rightCommit.CommitTime().Before(leftCommit.CommitTime()): + return -1 + case leftCommit.CommitTime().Before(rightCommit.CommitTime()): + return 1 + } + return 0 + } + // left is not in the graph, but right is, so it is newer than the right + return -1 + } + + if rightCommit.GenerationV2() == math.MaxInt64 { + // the right is not in the graph, therefore the left is before the right + return 1 + } + + if leftCommit.GenerationV2() == 0 || rightCommit.GenerationV2() == 0 { + // We need to assess generation and date + if leftCommit.Generation() < rightCommit.Generation() { + return 1 + } + if leftCommit.Generation() > rightCommit.Generation() { + return -1 + } + switch { + case rightCommit.CommitTime().Before(leftCommit.CommitTime()): + return -1 + case leftCommit.CommitTime().Before(rightCommit.CommitTime()): + return 1 + } + return 0 + } + + if leftCommit.GenerationV2() < rightCommit.GenerationV2() { + return 1 + } + if leftCommit.GenerationV2() > rightCommit.GenerationV2() { + return -1 + } + + return 0 +} + +// composeIgnores composes the ignore list with the provided seenExternal list +func composeIgnores(ignore []plumbing.Hash, seenExternal map[plumbing.Hash]bool) map[plumbing.Hash]struct{} { + if len(ignore) == 0 { + seen := make(map[plumbing.Hash]struct{}) + for h, ext := range seenExternal { + if ext { + seen[h] = struct{}{} + } + } + return seen + } + + seen := make(map[plumbing.Hash]struct{}) + for _, h := range ignore { + seen[h] = struct{}{} + } + for h, ext := range seenExternal { + if ext { + seen[h] = struct{}{} + } + } + return seen +} diff --git a/plumbing/object/commitgraph/commitnode_walker_test.go b/plumbing/object/commitgraph/commitnode_walker_test.go new file mode 100644 index 0000000..1e09c0b --- /dev/null +++ b/plumbing/object/commitgraph/commitnode_walker_test.go @@ -0,0 +1,187 @@ +package commitgraph + +import ( + "strings" + + "github.com/go-git/go-git/v5/plumbing" + commitgraph "github.com/go-git/go-git/v5/plumbing/format/commitgraph/v2" + + fixtures "github.com/go-git/go-git-fixtures/v4" + . "gopkg.in/check.v1" +) + +func (s *CommitNodeSuite) TestCommitNodeIter(c *C) { + f := fixtures.ByTag("commit-graph-chain-2").One() + + storer := unpackRepository(f) + + index, err := commitgraph.OpenChainOrFileIndex(storer.Filesystem()) + c.Assert(err, IsNil) + + nodeIndex := NewGraphCommitNodeIndex(index, storer) + + head, err := nodeIndex.Get(plumbing.NewHash("ec6f456c0e8c7058a29611429965aa05c190b54b")) + c.Assert(err, IsNil) + + testTopoOrder(c, head) + testDateOrder(c, head) + testAuthorDateOrder(c, head) +} + +func testTopoOrder(c *C, head CommitNode) { + iter := NewCommitNodeIterTopoOrder( + head, + nil, + nil, + ) + + var commits []string + iter.ForEach(func(c CommitNode) error { + commits = append(commits, c.ID().String()) + return nil + }) + c.Assert(commits, DeepEquals, strings.Split(`ec6f456c0e8c7058a29611429965aa05c190b54b +d82f291cde9987322c8a0c81a325e1ba6159684c +3048d280d2d5b258d9e582a226ff4bbed34fd5c9 +27aa8cdd2431068606741a589383c02c149ea625 +fa058d42fa3bc53f39108a56dad67157169b2191 +6c629843a1750a27c9af01ed2985f362f619c47a +d10a0e7c1f340a6cfc14540a5f8c508ce7e2eabf +d0a18ccd8eea3bdabc76d6dc5420af1ea30aae9f +cf2874632223220e0445abf0a7806dc772c0b37a +758ac33217f092bfcded4ad4774954ac054c9609 +214e1dca024fb6da5ed65564d2de734df5dc2127 +70923099e61fa33f0bc5256d2f938fa44c4df10e +bcaa1ac5644b16f1febb72f31e204720b7bb8934 +e1d8866ffa78fa16d2f39b0ba5344a7269ee5371 +2275fa7d0c75d20103f90b0e1616937d5a9fc5e6 +bdd9a92789d4a86b20a8d3df462df373f41acf23 +b359f11ea09e642695edcd114b463da4395b10c1 +6f43e8933ba3c04072d5d104acc6118aac3e52ee +ccafe8bd5f9dbfb8b98b0da03ced29608dcfdeec +939814f341fdd5d35e81a3845a33c4fedb19d2d2 +5f5ad88bf2babe506f927d64d2b7a1e1493dc2ae +a2014124ca3b3f9ff28fbab0a83ce3c71bf4622e +77906b653c3eb8a1cd5bd7254e161c00c6086d83 +465cba710284204f9851854587c2887c247222db +b9471b13256703d3f5eb88b280b4a16ce325ec1b +62925030859646daeeaf5a4d386a0c41e00dda8a +5f56aea0ca8b74215a5b982bca32236e1e28c76b +23148841baa5dbce48f6adcb7ddf83dcd97debb3 +c336d16298a017486c4164c40f8acb28afe64e84 +31eae7b619d166c366bf5df4991f04ba8cebea0a +d2a38b4a5965d529566566640519d03d2bd10f6c +b977a025ca21e3b5ca123d8093bd7917694f6da7 +35b585759cbf29f8ec428ef89da20705d59f99ec +c2bbf9fe8009b22d0f390f3c8c3f13937067590f +fc9f0643b21cfe571046e27e0c4565f3a1ee96c8 +c088fd6a7e1a38e9d5a9815265cb575bb08d08ff +5fddbeb678bd2c36c5e5c891ab8f2b143ced5baf +5d7303c49ac984a9fec60523f2d5297682e16646`, "\n")) +} + +func testDateOrder(c *C, head CommitNode) { + iter := NewCommitNodeIterDateOrder( + head, + nil, + nil, + ) + + var commits []string + iter.ForEach(func(c CommitNode) error { + commits = append(commits, c.ID().String()) + return nil + }) + + c.Assert(commits, DeepEquals, strings.Split(`ec6f456c0e8c7058a29611429965aa05c190b54b +3048d280d2d5b258d9e582a226ff4bbed34fd5c9 +d82f291cde9987322c8a0c81a325e1ba6159684c +27aa8cdd2431068606741a589383c02c149ea625 +fa058d42fa3bc53f39108a56dad67157169b2191 +d0a18ccd8eea3bdabc76d6dc5420af1ea30aae9f +6c629843a1750a27c9af01ed2985f362f619c47a +cf2874632223220e0445abf0a7806dc772c0b37a +d10a0e7c1f340a6cfc14540a5f8c508ce7e2eabf +758ac33217f092bfcded4ad4774954ac054c9609 +214e1dca024fb6da5ed65564d2de734df5dc2127 +70923099e61fa33f0bc5256d2f938fa44c4df10e +bcaa1ac5644b16f1febb72f31e204720b7bb8934 +e1d8866ffa78fa16d2f39b0ba5344a7269ee5371 +2275fa7d0c75d20103f90b0e1616937d5a9fc5e6 +bdd9a92789d4a86b20a8d3df462df373f41acf23 +b359f11ea09e642695edcd114b463da4395b10c1 +6f43e8933ba3c04072d5d104acc6118aac3e52ee +ccafe8bd5f9dbfb8b98b0da03ced29608dcfdeec +939814f341fdd5d35e81a3845a33c4fedb19d2d2 +5f5ad88bf2babe506f927d64d2b7a1e1493dc2ae +a2014124ca3b3f9ff28fbab0a83ce3c71bf4622e +77906b653c3eb8a1cd5bd7254e161c00c6086d83 +465cba710284204f9851854587c2887c247222db +b9471b13256703d3f5eb88b280b4a16ce325ec1b +62925030859646daeeaf5a4d386a0c41e00dda8a +5f56aea0ca8b74215a5b982bca32236e1e28c76b +23148841baa5dbce48f6adcb7ddf83dcd97debb3 +c336d16298a017486c4164c40f8acb28afe64e84 +31eae7b619d166c366bf5df4991f04ba8cebea0a +b977a025ca21e3b5ca123d8093bd7917694f6da7 +d2a38b4a5965d529566566640519d03d2bd10f6c +35b585759cbf29f8ec428ef89da20705d59f99ec +c2bbf9fe8009b22d0f390f3c8c3f13937067590f +fc9f0643b21cfe571046e27e0c4565f3a1ee96c8 +c088fd6a7e1a38e9d5a9815265cb575bb08d08ff +5fddbeb678bd2c36c5e5c891ab8f2b143ced5baf +5d7303c49ac984a9fec60523f2d5297682e16646`, "\n")) +} + +func testAuthorDateOrder(c *C, head CommitNode) { + iter := NewCommitNodeIterAuthorDateOrder( + head, + nil, + nil, + ) + + var commits []string + iter.ForEach(func(c CommitNode) error { + commits = append(commits, c.ID().String()) + return nil + }) + + c.Assert(commits, DeepEquals, strings.Split(`ec6f456c0e8c7058a29611429965aa05c190b54b +3048d280d2d5b258d9e582a226ff4bbed34fd5c9 +d82f291cde9987322c8a0c81a325e1ba6159684c +27aa8cdd2431068606741a589383c02c149ea625 +fa058d42fa3bc53f39108a56dad67157169b2191 +d0a18ccd8eea3bdabc76d6dc5420af1ea30aae9f +6c629843a1750a27c9af01ed2985f362f619c47a +cf2874632223220e0445abf0a7806dc772c0b37a +d10a0e7c1f340a6cfc14540a5f8c508ce7e2eabf +758ac33217f092bfcded4ad4774954ac054c9609 +214e1dca024fb6da5ed65564d2de734df5dc2127 +70923099e61fa33f0bc5256d2f938fa44c4df10e +bcaa1ac5644b16f1febb72f31e204720b7bb8934 +e1d8866ffa78fa16d2f39b0ba5344a7269ee5371 +2275fa7d0c75d20103f90b0e1616937d5a9fc5e6 +bdd9a92789d4a86b20a8d3df462df373f41acf23 +b359f11ea09e642695edcd114b463da4395b10c1 +6f43e8933ba3c04072d5d104acc6118aac3e52ee +ccafe8bd5f9dbfb8b98b0da03ced29608dcfdeec +939814f341fdd5d35e81a3845a33c4fedb19d2d2 +5f5ad88bf2babe506f927d64d2b7a1e1493dc2ae +a2014124ca3b3f9ff28fbab0a83ce3c71bf4622e +77906b653c3eb8a1cd5bd7254e161c00c6086d83 +465cba710284204f9851854587c2887c247222db +b9471b13256703d3f5eb88b280b4a16ce325ec1b +5f56aea0ca8b74215a5b982bca32236e1e28c76b +62925030859646daeeaf5a4d386a0c41e00dda8a +23148841baa5dbce48f6adcb7ddf83dcd97debb3 +c336d16298a017486c4164c40f8acb28afe64e84 +31eae7b619d166c366bf5df4991f04ba8cebea0a +b977a025ca21e3b5ca123d8093bd7917694f6da7 +d2a38b4a5965d529566566640519d03d2bd10f6c +35b585759cbf29f8ec428ef89da20705d59f99ec +c2bbf9fe8009b22d0f390f3c8c3f13937067590f +fc9f0643b21cfe571046e27e0c4565f3a1ee96c8 +c088fd6a7e1a38e9d5a9815265cb575bb08d08ff +5fddbeb678bd2c36c5e5c891ab8f2b143ced5baf +5d7303c49ac984a9fec60523f2d5297682e16646`, "\n")) +} diff --git a/plumbing/object/commitgraph/commitnode_walker_topo_order.go b/plumbing/object/commitgraph/commitnode_walker_topo_order.go new file mode 100644 index 0000000..29f4bb7 --- /dev/null +++ b/plumbing/object/commitgraph/commitnode_walker_topo_order.go @@ -0,0 +1,161 @@ +package commitgraph + +import ( + "io" + + "github.com/go-git/go-git/v5/plumbing" + "github.com/go-git/go-git/v5/plumbing/storer" + + "github.com/emirpasic/gods/trees/binaryheap" +) + +type commitNodeIteratorTopological struct { + exploreStack commitNodeStackable + visitStack commitNodeStackable + inCounts map[plumbing.Hash]int + + ignore map[plumbing.Hash]struct{} +} + +// NewCommitNodeIterTopoOrder returns a CommitNodeIter that walks the commit history, +// starting at the given commit and visiting its parents in a topological order but +// with the constraint that no parent is emitted before its children are emitted. +// +// This matches `git log --topo-order` +func NewCommitNodeIterTopoOrder(c CommitNode, + seenExternal map[plumbing.Hash]bool, + ignore []plumbing.Hash, +) CommitNodeIter { + seen := composeIgnores(ignore, seenExternal) + inCounts := make(map[plumbing.Hash]int) + + heap := &commitNodeHeap{binaryheap.NewWith(generationAndDateOrderComparator)} + heap.Push(c) + + lifo := &commitNodeLifo{make([]CommitNode, 0, 8)} + lifo.Push(c) + + return &commitNodeIteratorTopological{ + exploreStack: heap, + visitStack: lifo, + inCounts: inCounts, + ignore: seen, + } +} + +func (iter *commitNodeIteratorTopological) Next() (CommitNode, error) { + var next CommitNode + for { + var ok bool + next, ok = iter.visitStack.Pop() + if !ok { + return nil, io.EOF + } + + if iter.inCounts[next.ID()] == 0 { + break + } + } + + minimumLevel, generationV2 := next.GenerationV2(), true + if minimumLevel == 0 { + minimumLevel, generationV2 = next.Generation(), false + } + + parents := make([]CommitNode, 0, len(next.ParentHashes())) + for i := range next.ParentHashes() { + pc, err := next.ParentNode(i) + if err != nil { + return nil, err + } + + parents = append(parents, pc) + + if generationV2 { + if pc.GenerationV2() < minimumLevel { + minimumLevel = pc.GenerationV2() + } + continue + } + + if pc.Generation() < minimumLevel { + minimumLevel = pc.Generation() + } + } + + // EXPLORE + for { + toExplore, ok := iter.exploreStack.Peek() + if !ok { + break + } + + if toExplore.ID() != next.ID() && iter.exploreStack.Size() == 1 { + break + } + if generationV2 { + if toExplore.GenerationV2() < minimumLevel { + break + } + } else { + if toExplore.Generation() < minimumLevel { + break + } + } + + iter.exploreStack.Pop() + for i, h := range toExplore.ParentHashes() { + if _, has := iter.ignore[h]; has { + continue + } + iter.inCounts[h]++ + + if iter.inCounts[h] == 1 { + pc, err := toExplore.ParentNode(i) + if err != nil { + return nil, err + } + iter.exploreStack.Push(pc) + } + } + } + + // VISIT + for i, h := range next.ParentHashes() { + if _, has := iter.ignore[h]; has { + continue + } + iter.inCounts[h]-- + + if iter.inCounts[h] == 0 { + iter.visitStack.Push(parents[i]) + } + } + delete(iter.inCounts, next.ID()) + + return next, nil +} + +func (iter *commitNodeIteratorTopological) ForEach(cb func(CommitNode) error) error { + for { + obj, err := iter.Next() + if err != nil { + if err == io.EOF { + return nil + } + + return err + } + + if err := cb(obj); err != nil { + if err == storer.ErrStop { + return nil + } + + return err + } + } +} + +func (iter *commitNodeIteratorTopological) Close() { +} |