diff options
| -rw-r--r-- | reachability/ancestor.go | 122 | ||||
| -rw-r--r-- | reachability/connected.go | 19 | ||||
| -rw-r--r-- | reachability/reachability.go | 153 | ||||
| -rw-r--r-- | reachability/walk.go | 20 |
4 files changed, 161 insertions, 153 deletions
diff --git a/reachability/ancestor.go b/reachability/ancestor.go new file mode 100644 index 00000000..5c978bf4 --- /dev/null +++ b/reachability/ancestor.go @@ -0,0 +1,122 @@ +package reachability + +import ( + "errors" + + "codeberg.org/lindenii/furgit/format/commitgraph" + "codeberg.org/lindenii/furgit/objectid" +) + +// IsAncestor reports whether ancestor is reachable from descendant via commit +// parent edges. +// +// Both inputs are peeled through annotated tags before commit traversal. +func (r *Reachability) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) { + ancestorCommit, err := r.peelRootToDomain(ancestor, DomainCommits) + if err != nil { + return false, err + } + + descendantCommit, err := r.peelRootToDomain(descendant, DomainCommits) + if err != nil { + return false, err + } + + if ancestorCommit == descendantCommit { + 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 { + return true, nil + } + } + + err = walk.Err() + if err != nil { + return false, err + } + + 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 +} diff --git a/reachability/connected.go b/reachability/connected.go new file mode 100644 index 00000000..6496287d --- /dev/null +++ b/reachability/connected.go @@ -0,0 +1,19 @@ +package reachability + +import "codeberg.org/lindenii/furgit/objectid" + +// 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() { + } + + return walk.Err() +} diff --git a/reachability/reachability.go b/reachability/reachability.go index 29ac2a93..1180e32a 100644 --- a/reachability/reachability.go +++ b/reachability/reachability.go @@ -2,10 +2,7 @@ package reachability import ( - "errors" - "codeberg.org/lindenii/furgit/format/commitgraph" - "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objectstore" ) @@ -27,153 +24,3 @@ func New(store objectstore.Store) *Reachability { 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. -// -// Both inputs are peeled through annotated tags before commit traversal. -func (r *Reachability) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) { - ancestorCommit, err := r.peelRootToDomain(ancestor, DomainCommits) - if err != nil { - return false, err - } - - descendantCommit, err := r.peelRootToDomain(descendant, DomainCommits) - if err != nil { - return false, err - } - - if ancestorCommit == descendantCommit { - 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 { - return true, nil - } - } - - err = walk.Err() - if err != nil { - return false, err - } - - return false, 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() { - } - - return walk.Err() -} - -// 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, - domain: domain, - haves: haves, - wants: wants, - } - - err := validateDomain(domain) - if err != nil { - walk.err = err - } - - return walk -} - -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 -} diff --git a/reachability/walk.go b/reachability/walk.go index 13400e89..e6de8684 100644 --- a/reachability/walk.go +++ b/reachability/walk.go @@ -15,3 +15,23 @@ type Walk struct { seqUsed bool err error } + +// 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, + domain: domain, + haves: haves, + wants: wants, + } + + err := validateDomain(domain) + if err != nil { + walk.err = err + } + + return walk +} |