forked from siderolabs/kres
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dag.go
79 lines (59 loc) · 1.75 KB
/
dag.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
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
// Package dag represents abstract directed acyclic graph.
package dag
// Graph represents the targets of the build process.
type Graph interface {
Targets() []Node
}
// WalkFunc is a callback function called by Walk.
type WalkFunc func(node Node) error
// Walk the graph calling function for every node just once.
func Walk(graph Graph, walkFn WalkFunc, visited map[Node]struct{}, depth int) error {
if visited == nil {
visited = make(map[Node]struct{})
}
targets := graph.Targets()
return walk(targets, walkFn, visited, depth)
}
// WalkNode walks the graph starting from the node just once.
func WalkNode(node Node, walkFn WalkFunc, visited map[Node]struct{}, depth int) error {
if visited == nil {
visited = make(map[Node]struct{})
}
targets := node.Inputs()
return walk(targets, walkFn, visited, depth)
}
func walk(targets []Node, walkFn WalkFunc, visited map[Node]struct{}, depth int) error {
if depth == 0 {
return nil
}
depth--
for _, target := range targets {
if _, ok := visited[target]; ok {
continue
}
visited[target] = struct{}{}
if err := walk(target.Inputs(), walkFn, visited, depth); err != nil {
return err
}
if err := walkFn(target); err != nil {
return err
}
}
return nil
}
// FindByName walks the nodes to find the node with matching name.
//
//nolint:nonamedreturns
func FindByName(name string, targets ...Node) (result Node) {
visited := make(map[Node]struct{})
walk(targets, func(node Node) error { //nolint:errcheck
if node.Name() == name {
result = node
}
return nil
}, visited, -1)
return
}