diff options
Diffstat (limited to 'reachability')
| -rw-r--r-- | reachability/reachability.go | 97 | ||||
| -rw-r--r-- | reachability/walk.go | 88 |
2 files changed, 185 insertions, 0 deletions
diff --git a/reachability/reachability.go b/reachability/reachability.go index 12f672e3..9126ee84 100644 --- a/reachability/reachability.go +++ b/reachability/reachability.go @@ -2,6 +2,9 @@ package reachability import ( + "errors" + + "codeberg.org/lindenii/furgit/format/commitgraph" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objectstore" ) @@ -11,6 +14,7 @@ import ( // It is not safe for concurrent use. type Reachability struct { store objectstore.Store + graph *commitgraph.Reader } // New builds a Reachability over one object store. @@ -18,6 +22,12 @@ func New(store objectstore.Store) *Reachability { return &Reachability{store: store} } +// NewWithCommitGraph builds a Reachability over one object store with an +// optional commit-graph reader for faster commit-domain traversal. +func NewWithCommitGraph(store objectstore.Store, graph *commitgraph.Reader) *Reachability { + return &Reachability{store: store, graph: graph} +} + // IsAncestor reports whether ancestor is reachable from descendant via commit // parent edges. // @@ -37,6 +47,15 @@ func (r *Reachability) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, return true, nil } + graphResult, graphUsed, err := r.isAncestorGraph(ancestorCommit, descendantCommit) + if err != nil { + return false, err + } + + if graphUsed { + return graphResult, nil + } + walk := r.Walk(DomainCommits, nil, map[objectid.ObjectID]struct{}{descendantCommit: {}}) for id := range walk.Seq() { if id == ancestorCommit { @@ -52,11 +71,86 @@ func (r *Reachability) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, return false, nil } +func (r *Reachability) isAncestorGraph(ancestor, descendant objectid.ObjectID) (bool, bool, error) { + if r.graph == nil { + return false, false, nil + } + + ancestorPos, err := r.graph.Lookup(ancestor) + if err != nil { + var notFound *commitgraph.ErrNotFound + if errors.As(err, ¬Found) { + return false, false, nil + } + + return false, true, err + } + + descendantPos, err := r.graph.Lookup(descendant) + if err != nil { + var notFound *commitgraph.ErrNotFound + if errors.As(err, ¬Found) { + return false, false, nil + } + + return false, true, err + } + + ancestorCommit, err := r.graph.CommitAt(ancestorPos) + if err != nil { + return false, true, err + } + + ancestorGeneration := ancestorCommit.GenerationV2 + stack := []commitgraph.Position{descendantPos} + visited := make(map[commitgraph.Position]struct{}, 64) + + for len(stack) > 0 { + pos := stack[len(stack)-1] + stack = stack[:len(stack)-1] + + if _, ok := visited[pos]; ok { + continue + } + + visited[pos] = struct{}{} + + if pos == ancestorPos { + return true, true, nil + } + + commit, err := r.graph.CommitAt(pos) + if err != nil { + return false, true, err + } + + if commit.GenerationV2 < ancestorGeneration { + continue + } + + if commit.Parent1.Valid { + stack = append(stack, commit.Parent1.Pos) + } + + if commit.Parent2.Valid { + stack = append(stack, commit.Parent2.Pos) + } + + stack = append(stack, commit.ExtraParents...) + } + + return false, true, nil +} + // CheckConnected verifies that all objects reachable from wants (under the // selected domain) can be fully traversed without missing-object/type/parse // errors, excluding subgraphs rooted at haves. +// +// Even with commit-graph acceleration available, each visited commit is +// still validated against the object store. func (r *Reachability) CheckConnected(domain Domain, haves, wants map[objectid.ObjectID]struct{}) error { walk := r.Walk(domain, haves, wants) + walk.strict = true for range walk.Seq() { } @@ -64,6 +158,9 @@ func (r *Reachability) CheckConnected(domain Domain, haves, wants map[objectid.O } // Walk creates one single-use traversal over the selected domain. +// +// In DomainCommits, when a commit-graph reader is attached, parent expansion +// may use commit-graph metadata for speed. func (r *Reachability) Walk(domain Domain, haves, wants map[objectid.ObjectID]struct{}) *Walk { walk := &Walk{ reachability: r, diff --git a/reachability/walk.go b/reachability/walk.go index 89de19e8..e96a8b44 100644 --- a/reachability/walk.go +++ b/reachability/walk.go @@ -5,6 +5,7 @@ import ( "fmt" "iter" + "codeberg.org/lindenii/furgit/format/commitgraph" "codeberg.org/lindenii/furgit/object" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objecttype" @@ -16,6 +17,7 @@ type Walk struct { domain Domain haves map[objectid.ObjectID]struct{} wants map[objectid.ObjectID]struct{} + strict bool seqUsed bool err error @@ -109,6 +111,24 @@ func (walk *Walk) expand(item walkItem) ([]walkItem, error) { } func (walk *Walk) expandCommits(item walkItem) ([]walkItem, error) { + if walk.reachability.graph != nil { + next, graphUsed, err := walk.expandCommitsFromGraph(item.id) + if err != nil { + return nil, err + } + + if graphUsed { + if walk.strict { + err := walk.validateCommitObject(item.id) + if err != nil { + return nil, err + } + } + + return next, nil + } + } + ty, err := walk.readHeaderType(item.id) if err != nil { return nil, err @@ -152,6 +172,74 @@ func (walk *Walk) expandCommits(item walkItem) ([]walkItem, error) { return nil, fmt.Errorf("reachability: unreachable object type %d", ty) } +func (walk *Walk) validateCommitObject(id objectid.ObjectID) error { + ty, err := walk.readHeaderType(id) + if err != nil { + return err + } + + if ty != objecttype.TypeCommit { + return &ErrObjectType{OID: id, Got: ty, Want: objecttype.TypeCommit} + } + + content, err := walk.readBytesContent(id) + if err != nil { + return err + } + + _, err = object.ParseCommit(content, id.Algorithm()) + + return err +} + +func (walk *Walk) expandCommitsFromGraph(id objectid.ObjectID) ([]walkItem, bool, error) { + pos, err := walk.reachability.graph.Lookup(id) + if err != nil { + var notFound *commitgraph.ErrNotFound + if errors.As(err, ¬Found) { + return nil, false, nil + } + + return nil, true, err + } + + commit, err := walk.reachability.graph.CommitAt(pos) + if err != nil { + return nil, true, err + } + + next := make([]walkItem, 0, 2+len(commit.ExtraParents)) + + if commit.Parent1.Valid { + parentOID, err := walk.reachability.graph.OIDAt(commit.Parent1.Pos) + if err != nil { + return nil, true, err + } + + next = append(next, walkItem{id: parentOID, want: objecttype.TypeInvalid}) + } + + if commit.Parent2.Valid { + parentOID, err := walk.reachability.graph.OIDAt(commit.Parent2.Pos) + if err != nil { + return nil, true, err + } + + next = append(next, walkItem{id: parentOID, want: objecttype.TypeInvalid}) + } + + for _, parentPos := range commit.ExtraParents { + parentOID, err := walk.reachability.graph.OIDAt(parentPos) + if err != nil { + return nil, true, err + } + + next = append(next, walkItem{id: parentOID, want: objecttype.TypeInvalid}) + } + + return next, true, nil +} + func (walk *Walk) expandObjects(item walkItem) ([]walkItem, error) { ty, err := walk.readHeaderType(item.id) if err != nil { |