-
Notifications
You must be signed in to change notification settings - Fork 0
/
depgraph.go
171 lines (134 loc) · 4.63 KB
/
depgraph.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
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
package depgraph
import (
"fmt"
"sort"
"strings"
"sync"
mapset "github.com/deckarep/golang-set"
)
type DependencyGraph struct {
mutex sync.RWMutex
graph map[uint64]mapset.Set
}
// NewDependencyGraph generates and returns an empty DependencyGraph
func NewDependencyGraph() *DependencyGraph {
return &DependencyGraph{graph: make(map[uint64]mapset.Set)}
}
// Insert inserts an uint64 as a graph vertex to the DependencyGraph.
// It also accepts a variadic number of dependencies for the pointer and inserts them as edges.
//
// If the vertex (and subsequently its edges) already exists, it is overwritten.
func (dgraph *DependencyGraph) Insert(ptr uint64, deps ...uint64) {
// Create a new Set and insert the dependencies into it
set := mapset.NewSet()
for _, dep := range deps {
set.Add(dep)
}
// Push the vertex and its edges into the graph
dgraph.push(ptr, set)
}
// Remove removes an uint64 as a graph vertex from the DependencyGraph.
// If such a vertex does not exist, this is a no-op.
func (dgraph *DependencyGraph) Remove(ptr uint64) {
dgraph.pop(ptr)
}
// Size returns the number of vertices in the DependencyGraph
func (dgraph *DependencyGraph) Size() uint64 {
dgraph.mutex.RLock()
defer dgraph.mutex.RUnlock()
return uint64(len(dgraph.graph))
}
// Contains returns whether a given vertex exists in the DependencyGraph
func (dgraph *DependencyGraph) Contains(ptr uint64) bool {
_, ok := dgraph.peek(ptr)
return ok
}
// Copy creates a clone of the DependencyGraph and returns it
func (dgraph *DependencyGraph) Copy() *DependencyGraph {
dgraph.mutex.RLock()
defer dgraph.mutex.RUnlock()
// Create a DependencyGraph with a graph buffer large enough for all elements in the original
clone := &DependencyGraph{graph: make(map[uint64]mapset.Set, len(dgraph.graph))}
// For each vertex pointer, copy its edge dependencies and insert
for ptr, deps := range dgraph.graph {
clone.push(ptr, deps.Clone())
}
return clone
}
// String implements the Stringer interface for DependencyGraph.
func (dgraph *DependencyGraph) String() string {
dgraph.mutex.RLock()
defer dgraph.mutex.RUnlock()
elements := make([]string, 0)
// Iterate over the graph vertices
for ptr := range dgraph.Iter() {
// Get the edge dependencies
deps, _ := dgraph.peek(ptr)
// If no edges, just add the pointer value
if deps.Cardinality() == 0 {
elements = append(elements, fmt.Sprintf("%v", ptr))
continue
}
// Sort the deps and format element as ptr:[deps]
depSlice := deps.ToSlice()
sort.Slice(depSlice, func(i, j int) bool {
return depSlice[i].(uint64) < depSlice[j].(uint64) //nolint:forcetypeassert
})
elements = append(elements, fmt.Sprintf("%v:%v", ptr, depSlice))
}
return fmt.Sprintf("DependencyGraph{%v}", strings.Join(elements, ", "))
}
// Iter returns a channel iterator that iterates over the vertices of the DependencyGraph is sorted order.
// This iteration is thread-safe, the graph being immutable during the iteration.
func (dgraph *DependencyGraph) Iter() <-chan uint64 {
ch := make(chan uint64)
go func() {
dgraph.mutex.RLock()
defer dgraph.mutex.RUnlock()
for _, ptr := range dgraph.sorted() {
ch <- ptr
}
close(ch)
}()
return ch
}
// Edges returns the edges of going out of a given vertex pointer.
// The dependencies are returned as a mapset.Set (cardinality is zero if no dependencies for vertex)
func (dgraph *DependencyGraph) Edges(ptr uint64) []uint64 {
depSet, _ := dgraph.peek(ptr)
deps := make([]uint64, 0, depSet.Cardinality())
for dep := range depSet.Iter() {
deps = append(deps, dep.(uint64)) //nolint:forcetypeassert
}
return deps
}
// Dependencies returns all the edges (and edges of edges) for a given vertex pointer.
// It recursively collects all dependencies from each dependency layer and returns them (without duplicates).
// Note: This should only be used if the DependencyGraph can be resolved, otherwise, it will result in an infinite loop.
func (dgraph *DependencyGraph) Dependencies(ptr uint64) []uint64 {
depSet := mapset.NewSet()
// Collect all the direct deps of the pointer
for _, dep := range dgraph.Edges(ptr) {
// Add the direct dep to depSet
depSet.Add(dep)
// Recursively collect all sub dependencies
deeper := dgraph.Dependencies(dep)
if len(deeper) == 0 {
continue
}
// Add all sub dependencies to the set
for _, dep := range deeper {
depSet.Add(dep)
}
}
// Collect all dependencies (free from duplicates)
deps := make([]uint64, 0, depSet.Cardinality())
for dep := range depSet.Iter() {
deps = append(deps, dep.(uint64)) //nolint:forcetypeassert
}
// Sort the dependencies
sort.Slice(deps, func(i, j int) bool {
return deps[i] < deps[j]
})
return deps
}