-
Notifications
You must be signed in to change notification settings - Fork 24
/
compile.go
177 lines (160 loc) · 5.42 KB
/
compile.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
172
173
174
175
176
177
package runtime
import (
"errors"
"fmt"
"github.com/looplab/tarjan"
"github.com/fluxninja/aperture/v2/pkg/log"
)
// Compile compiles list of configured components into a circuit and validates it.
func Compile(
configuredComponents []*ConfiguredComponent,
logger *log.Logger,
) error {
// Map from signal name to a list of componentIndex(es) which accept the signal as input.
inSignals := make(map[SignalID][]int)
// Map from signal name to the componentIndex which emits the signal as output.
outSignals := make(map[SignalID]int)
for componentIndex, comp := range configuredComponents {
logger.Trace().Str("componentName", comp.Name()).Interface("ports", comp.PortMapping).Send()
updateSignalConsumers(comp.PortMapping.Ins, inSignals, componentIndex)
err := updateSignalProducers(comp.PortMapping.Outs, outSignals, componentIndex)
if err != nil {
return err
}
}
// Sanitization of inSignals i.e. all inSignals should be defined in outSignals
for signalID := range inSignals {
if _, ok := outSignals[signalID]; !ok {
return fmt.Errorf("undefined signal: %+v", signalID)
}
}
// Run loop detection and mark any looped signals
// Create a graph for Tarjan's algorithm
graph := make(map[interface{}][]interface{})
for componentIndex, comp := range configuredComponents {
destCompIndexes := make([]interface{}, 0)
for _, signals := range comp.PortMapping.Outs {
for _, signal := range signals {
// Lookup signal in inSignals
componentIndexes, ok := inSignals[signal.SignalID()]
// Convert componentIndexes to []interface{}
componentIndexesIfc := make([]interface{}, len(componentIndexes))
for i, componentIndex := range componentIndexes {
componentIndexesIfc[i] = componentIndex
}
if ok {
// Add componentIndexes to destCompIndexes
destCompIndexes = append(destCompIndexes, componentIndexesIfc...)
}
}
}
// Add componentIndex:destCompIndexes in graph
if len(destCompIndexes) > 0 {
graph[componentIndex] = destCompIndexes
}
}
// Run Tarjan's algorithm for detecting loops
loops := tarjan.Connections(graph)
// Log loops and graph
logger.Trace().Msgf("Tarjan Loops: %+v \nTarjan Graph: %+v", loops, graph)
// Iterate over loops
for _, loop := range loops {
// Need to break loop at smallest componentIndex. Find smallest componentIndex in loop
if len(loop) > 0 {
smallestCompIndex, ok := loop[0].(int)
if !ok {
return errors.New("loop contains non-int component id")
}
smallestCompIndexLoopIdx := 0
for loopIdx, compIndexIfc := range loop {
componentIndex, ok := compIndexIfc.(int)
if !ok {
return errors.New("loop contains non-int component id")
}
if componentIndex < smallestCompIndex {
smallestCompIndex = componentIndex
smallestCompIndexLoopIdx = loopIdx
}
}
// Break loop at smallest compId.
removeToCompIndex := smallestCompIndex
// Remove connections from the next component in the loop
removeFromCompIndexLoopIdx := (smallestCompIndexLoopIdx + 1) % len(loop)
removeFromCompIndex := loop[removeFromCompIndexLoopIdx].(int)
// Remove connections from components at removeFromCompIndex to removeToCompIndex
if removeToCompIndex >= len(configuredComponents) {
return errors.New("removeToCompId is out of range")
}
removeToComp := configuredComponents[removeToCompIndex]
if removeFromCompIndex >= len(configuredComponents) {
return errors.New("removeFromCompId is out of range")
}
removeFromComp := configuredComponents[removeFromCompIndex]
loopedSignals := make(map[string]bool)
// Mark looped signals in Ins
for _, signals := range removeToComp.PortMapping.Ins {
for idx, signal := range signals {
if signal.SignalType() == SignalTypeNamed {
outFromCompID, ok := outSignals[signal.SignalID()]
if !ok {
return fmt.Errorf("unexpected state: signal %s is not defined in outSignals", signal.SignalName)
}
if outFromCompID == removeFromCompIndex {
// Mark signal as looped
signals[idx].Looped = true
loopedSignals[signal.SignalName] = true
}
}
}
}
// Mark looped signals in Outs
for _, signals := range removeFromComp.PortMapping.Outs {
for idx, signal := range signals {
if _, ok := loopedSignals[signal.SignalName]; ok {
// Mark signal as looped
signals[idx].Looped = true
}
}
}
} else {
// Loop is empty
return errors.New("got an empty loop from tarjan.Connections")
}
}
// Log components
for compIndex, comp := range configuredComponents {
logger.Trace().Msgf("compIndex: %d, comp: %+v", compIndex, comp)
}
return nil
}
func updateSignalConsumers(
portMapping map[string][]Signal,
signalConsumers map[SignalID][]int,
componentIndex int,
) {
for _, signals := range portMapping {
for _, signal := range signals {
if signal.SignalType() == SignalTypeNamed {
signalConsumers[signal.SignalID()] = append(signalConsumers[signal.SignalID()], componentIndex)
}
}
}
}
func updateSignalProducers(
portMapping map[string][]Signal,
signalProducers map[SignalID]int,
componentIndex int,
) error {
for _, signals := range portMapping {
for _, signal := range signals {
if signal.SignalType() == SignalTypeNamed {
if _, ok := signalProducers[signal.SignalID()]; !ok {
signalProducers[signal.SignalID()] = componentIndex
} else {
return errors.New("duplicate signal definition for signal name: " + signal.SignalName)
}
}
}
}
return nil
}