/
traversalservice_dfs.go
90 lines (75 loc) · 1.77 KB
/
traversalservice_dfs.go
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
package v1beta
import (
"context"
"github.com/depscloud/api/v1beta"
"github.com/depscloud/depscloud/internal/logger"
"go.uber.org/zap"
)
// DepthFirstSearch currently returns an in-order traversal.
func (t *traversalService) DepthFirstSearch(server v1beta.TraversalService_DepthFirstSearchServer) error {
ctx, cancel := context.WithCancel(server.Context())
defer cancel()
log := logger.Extract(ctx)
stream := consumeStream(ctx, server)
start := <-stream
if start.Cancel {
return nil
}
key := ""
if start.DependenciesFor != nil {
key = moduleKey(start.DependenciesFor.Module)
} else if start.DependentsOf != nil {
key = moduleKey(start.DependentsOf.Module)
} else {
return ErrInvalidRequest
}
seen := map[string]bool{key: true}
stack := Stack([]*v1beta.SearchRequest{
start,
})
for length := len(stack); length > 0; length = len(stack) {
req := stack.Pop()
resp, err := t.handleSearchRequest(ctx, req)
if err != nil {
log.Error("failed to query", zap.Error(err))
return ErrQueryFailure
}
if req.DependenciesFor != nil {
for _, dependency := range resp.Dependencies {
key := moduleKey(dependency.Module)
if !seen[key] {
seen[key] = true
stack.Push(&v1beta.SearchRequest{
DependenciesFor: dependency,
})
}
}
} else if req.DependentsOf != nil {
for _, dependency := range resp.Dependents {
key := moduleKey(dependency.Module)
if !seen[key] {
seen[key] = true
stack.Push(&v1beta.SearchRequest{
DependentsOf: dependency,
})
}
}
}
err = server.Send(resp)
if err != nil {
return ErrCancelled
}
select {
case <-ctx.Done():
return nil
case req := <-stream:
if req.Cancel {
return nil
}
return ErrDFS
default:
continue
}
}
return nil
}