blob: ad3415d196df6152e18c34888118d876391d0298 (
about) (
plain) (
blame)
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
|
package reachability
import (
"errors"
"iter"
"codeberg.org/lindenii/furgit/objectid"
)
// Seq returns the traversal sequence. It is single-use.
func (walk *Walk) Seq() iter.Seq[objectid.ObjectID] {
if walk.seqUsed {
return func(yield func(objectid.ObjectID) bool) {
_ = yield
if walk.err == nil {
walk.err = errors.New("reachability: walk sequence already consumed")
}
}
}
walk.seqUsed = true
return func(yield func(objectid.ObjectID) bool) {
if walk.err != nil {
return
}
stack := walk.initialStack()
var err error
visited := make(map[objectid.ObjectID]struct{}, len(stack))
for len(stack) > 0 {
item := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if containsOID(walk.haves, item.id) {
continue
}
if _, ok := visited[item.id]; ok {
continue
}
visited[item.id] = struct{}{}
var next []walkItem
next, err = walk.expand(item)
if err != nil {
walk.err = err
return
}
if !yield(item.id) {
return
}
stack = append(stack, next...)
}
}
}
// Err returns the terminal error, if any, once Seq has been consumed.
func (walk *Walk) Err() error {
return walk.err
}
|
