1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
// Package reachability traverses the object graph to test relationships and emit object lists.
package reachability
import (
"errors"
"codeberg.org/lindenii/furgit/format/commitgraph"
"codeberg.org/lindenii/furgit/objectid"
"codeberg.org/lindenii/furgit/objectstore"
)
// Reachability provides graph traversal over objects in one object store.
//
// It is not safe for concurrent use.
type Reachability struct {
store objectstore.Store
graph *commitgraph.Reader
}
// New builds a Reachability over one object store.
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.
//
// 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
}
|
