blob: f13b13fa15793055bf96b8298d7ce32f3f6a277e [file] [log] [blame]
package gitstore
import (
"time"
)
const (
// initialGraphSize is the assumed starting number of commits in a repository. Just so we
// don't start with an empty data structure when we building or traversing the graph.
initialGraphSize = 100000
)
// BuildGraph takes a rawGraph (a slice where each element contains a commit hash followed by its
// parents) and returns an instance of CommitGraph.
// TODO(kjlubick,borenet): can this be replaced by go/git/repograph.Graph ?
func BuildGraph(rawGraph [][]string, timeStamps []time.Time) *CommitGraph {
nodeMap := make(map[string]*Node, len(rawGraph))
for idx, rawNode := range rawGraph {
hash := rawNode[0]
nodeMap[hash] = &Node{
Hash: hash,
Parents: make([]*Node, len(rawNode)-1),
Timestamp: timeStamps[idx],
}
}
for _, rawNode := range rawGraph {
for idx, p := range rawNode[1:] {
nodeMap[rawNode[0]].Parents[idx] = nodeMap[p]
}
}
return &CommitGraph{
Nodes: nodeMap,
}
}
// CommitGraph contains commits as Nodes that are connected and thus can be traversed.
// Given a graph a client can retrieve a specific node and traverse the graph like this:
// // First-parent traversal
// node := graph.GetNode(someHash)
// for node != nil {
// // so something with the commit
// node = node.Parents[0]
// }
//
type CommitGraph struct {
Nodes map[string]*Node
}
// GetNode returns the node in the graph that corresponds to the given hash or nil
func (c *CommitGraph) GetNode(hash string) *Node {
return c.Nodes[hash]
}
// Node is a node in the commit graph that contains the commit hash, a timestamp and pointers to
// its parent nodes. The first parent is the immediate parent in the same branch (like in Git).
type Node struct {
Hash string
Timestamp time.Time
Parents []*Node
}
// DescendantChain returns all nodes in the commit graph in the range of
// (firstAncestor, lastDescendant) where the parameters are both commit hashes.
// 'firstAncestor' can be "" in which case it will return all ancestors of 'lastDescendant'.
// 'lastDescendant' must not be empty and must exist in graph or this will panic.
func (g *CommitGraph) DecendantChain(firstAncestor, lastDescendant string) []*Node {
curr := g.Nodes[lastDescendant]
ret := make([]*Node, 0, len(g.Nodes))
for curr != nil {
ret = append(ret, curr)
if (len(curr.Parents) == 0) || (curr.Hash == firstAncestor) {
break
}
curr = curr.Parents[0]
}
// Reverse the result
for idx := 0; idx < len(ret)/2; idx++ {
rightIdx := len(ret) - 1 - idx
ret[idx], ret[rightIdx] = ret[rightIdx], ret[idx]
}
return ret
}