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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
//! The audio graph topology and render algorithm
use std::cell::RefCell;
use crate::context::AudioNodeId;
use rustc_hash::FxHashMap;
use smallvec::{smallvec, SmallVec};
use super::{Alloc, AudioParamValues, AudioProcessor, AudioRenderQuantum};
use crate::node::ChannelConfig;
use crate::render::RenderScope;
/// Connection between two audio nodes
struct OutgoingEdge {
/// index of the current Nodes output port
self_index: usize,
/// reference to the other Node
other_id: AudioNodeId,
/// index of the other Nodes input port
other_index: usize,
}
/// Renderer Node in the Audio Graph
pub struct Node {
/// Renderer: converts inputs to outputs
processor: Box<dyn AudioProcessor>,
/// Reusable input buffers
inputs: Vec<AudioRenderQuantum>,
/// Reusable output buffers, consumed by subsequent Nodes in this graph
outputs: Vec<AudioRenderQuantum>,
/// Channel configuration: determines up/down-mixing of inputs
channel_config: ChannelConfig,
/// Outgoing edges: tuple of outcoming node reference, our output index and their input index
outgoing_edges: SmallVec<[OutgoingEdge; 2]>,
/// Indicates if the control thread has dropped this Node
free_when_finished: bool,
/// Indicates if the node has any incoming connections (for lifecycle management)
has_inputs_connected: bool,
/// Indicates if the node can act as a cycle breaker (only DelayNode for now)
cycle_breaker: bool,
}
impl Node {
/// Render an audio quantum
fn process(&mut self, params: AudioParamValues, scope: &RenderScope) -> bool {
self.processor
.process(&self.inputs[..], &mut self.outputs[..], params, scope)
}
/// Determine if this node is done playing and can be removed from the audio graph
fn can_free(&self, tail_time: bool) -> bool {
// Only drop when the Control thread has dropped its handle.
// Otherwise the node can be reconnected/restarted etc.
if !self.free_when_finished {
return false;
}
// Drop, when the node does not have any inputs connected,
// and if the processor reports it won't yield output.
if !self.has_inputs_connected && !tail_time {
return true;
}
// Otherwise, do not drop the node.
// (Even if it has no outputs connected, it may have side effects)
false
}
/// Get the current buffer for AudioParam values
pub fn get_buffer(&self) -> &AudioRenderQuantum {
self.outputs.get(0).unwrap()
}
}
/// The audio graph
pub(crate) struct Graph {
/// Processing Nodes
nodes: FxHashMap<AudioNodeId, RefCell<Node>>,
/// Allocator for audio buffers
alloc: Alloc,
/// Topological ordering of the nodes
ordered: Vec<AudioNodeId>,
/// Topological sorting helper
marked: Vec<AudioNodeId>,
/// Topological sorting helper
marked_temp: Vec<AudioNodeId>,
/// Topological sorting helper
in_cycle: Vec<AudioNodeId>,
/// Topological sorting helper
cycle_breakers: Vec<AudioNodeId>,
}
impl Graph {
pub fn new() -> Self {
Graph {
nodes: FxHashMap::default(),
ordered: vec![],
marked: vec![],
marked_temp: vec![],
in_cycle: vec![],
cycle_breakers: vec![],
alloc: Alloc::with_capacity(64),
}
}
pub fn add_node(
&mut self,
index: AudioNodeId,
processor: Box<dyn AudioProcessor>,
number_of_inputs: usize,
number_of_outputs: usize,
channel_config: ChannelConfig,
) {
// todo: pre-allocate the buffers on the control thread
// set input and output buffers to single channel of silence, will be upmixed when
// necessary
let inputs = vec![AudioRenderQuantum::from(self.alloc.silence()); number_of_inputs];
let outputs = vec![AudioRenderQuantum::from(self.alloc.silence()); number_of_outputs];
self.nodes.insert(
index,
RefCell::new(Node {
processor,
inputs,
outputs,
channel_config,
outgoing_edges: smallvec![],
free_when_finished: false,
has_inputs_connected: false,
cycle_breaker: false,
}),
);
}
pub fn add_edge(&mut self, source: (AudioNodeId, usize), dest: (AudioNodeId, usize)) {
self.nodes
.get_mut(&source.0)
.unwrap_or_else(|| panic!("cannot connect {:?} to {:?}", source, dest))
.get_mut()
.outgoing_edges
.push(OutgoingEdge {
self_index: source.1,
other_id: dest.0,
other_index: dest.1,
});
self.ordered.clear(); // void current ordering
}
pub fn remove_edge(&mut self, source: AudioNodeId, dest: AudioNodeId) {
self.nodes
.get_mut(&source)
.unwrap_or_else(|| panic!("cannot remove the edge from {:?} to {:?}", source, dest))
.get_mut()
.outgoing_edges
.retain(|edge| edge.other_id != dest);
self.ordered.clear(); // void current ordering
}
pub fn remove_edges_from(&mut self, source: AudioNodeId) {
self.nodes
.get_mut(&source)
.unwrap_or_else(|| panic!("cannot remove edges from {:?}", source))
.get_mut()
.outgoing_edges
.clear();
self.nodes.values_mut().for_each(|node| {
node.get_mut()
.outgoing_edges
.retain(|edge| edge.other_id != source);
});
self.ordered.clear(); // void current ordering
}
pub fn mark_free_when_finished(&mut self, index: AudioNodeId) {
// Issue #92, a race condition can occur for AudioParams. They may have already been
// removed from the audio graph if the node they feed into was dropped.
// Therefore, do not assume this node still exists:
if let Some(node) = self.nodes.get_mut(&index) {
node.get_mut().free_when_finished = true;
}
}
pub fn mark_cycle_breaker(&mut self, index: AudioNodeId) {
self.nodes.get_mut(&index).unwrap().get_mut().cycle_breaker = true;
}
/// Helper function for `order_nodes` - traverse node and outgoing edges
///
/// The return value indicates `cycle_breaker_applied`:
/// - true: a cycle was found and a cycle breaker was applied, current ordering is invalidated
/// - false: visiting this leg was successful and no topological changes were applied
fn visit(
&self,
node_id: AudioNodeId,
marked: &mut Vec<AudioNodeId>,
marked_temp: &mut Vec<AudioNodeId>,
ordered: &mut Vec<AudioNodeId>,
in_cycle: &mut Vec<AudioNodeId>,
cycle_breakers: &mut Vec<AudioNodeId>,
) -> bool {
// If this node is in the cycle detection list, it is part of a cycle!
if let Some(pos) = marked_temp.iter().position(|&m| m == node_id) {
// check if we can find some node that can break the cycle
let cycle_breaker_node = marked_temp
.iter()
.skip(pos)
.find(|node_id| self.nodes.get(node_id).unwrap().borrow().cycle_breaker);
match cycle_breaker_node {
Some(&node_id) => {
// store node id to clear the node outgoing edges
cycle_breakers.push(node_id);
return true;
}
None => {
// Mark all nodes in the cycle
in_cycle.extend_from_slice(&marked_temp[pos..]);
// Do not continue, as we already have visited all these nodes
return false;
}
}
}
// Do not visit nodes multiple times
if marked.contains(&node_id) {
return false;
}
// Add node to the visited list
marked.push(node_id);
// Add node to the current cycle detection list
marked_temp.push(node_id);
// Visit outgoing nodes, and call `visit` on them recursively
for edge in self
.nodes
.get(&node_id)
.unwrap()
.borrow()
.outgoing_edges
.iter()
{
let cycle_breaker_applied = self.visit(
edge.other_id,
marked,
marked_temp,
ordered,
in_cycle,
cycle_breakers,
);
if cycle_breaker_applied {
return true;
}
}
// Then add this node to the ordered list
ordered.push(node_id);
// Finished visiting all nodes in this leg, clear the current cycle detection list
marked_temp.retain(|marked| *marked != node_id);
false
}
/// Determine the order of the audio nodes for rendering
///
/// By inspecting the audio node connections, we can determine which nodes should render before
/// other nodes. For example, in a graph with an audio source, a gain node and the destination
/// node, at every render quantum the source should render first and after that the gain node.
///
/// Inspired by the spec recommendation at
/// <https://webaudio.github.io/web-audio-api/#rendering-loop>
///
/// The goals are:
/// - Perform a topological sort of the graph
/// - Break cycles when possible (if there is a DelayNode present)
/// - Mute nodes that are still in a cycle
/// - For performance: no new allocations (reuse Vecs)
fn order_nodes(&mut self) {
// For borrowck reasons, we need the `visit` call to be &self.
// So move out the bookkeeping Vecs, and pass them around as &mut.
let mut ordered = std::mem::take(&mut self.ordered);
let mut marked = std::mem::take(&mut self.marked);
let mut marked_temp = std::mem::take(&mut self.marked_temp);
let mut in_cycle = std::mem::take(&mut self.in_cycle);
let mut cycle_breakers = std::mem::take(&mut self.cycle_breakers);
// When a cycle breaker is applied, the graph topology changes and we need to run the
// ordering again
loop {
// Clear previous administration
ordered.clear();
marked.clear();
marked_temp.clear();
in_cycle.clear();
cycle_breakers.clear();
// Visit all registered nodes, and perform a depth first traversal.
//
// We cannot just start from the AudioDestinationNode and visit all nodes connecting to it,
// since the audio graph could contain legs detached from the destination and those should
// still be rendered.
let mut cycle_breaker_applied = false;
for &node_id in self.nodes.keys() {
cycle_breaker_applied = self.visit(
node_id,
&mut marked,
&mut marked_temp,
&mut ordered,
&mut in_cycle,
&mut cycle_breakers,
);
if cycle_breaker_applied {
break;
}
}
if cycle_breaker_applied {
// clear the outgoing edges of the nodes that have been recognized as cycle breaker
cycle_breakers.iter().for_each(|node_id| {
let node = self.nodes.get_mut(node_id).unwrap();
node.get_mut().outgoing_edges.clear();
});
continue;
}
break;
}
// Remove nodes from the ordering if they are part of a cycle. The spec mandates that their
// outputs should be silenced, but with our rendering algorithm that is not necessary.
// `retain` leaves the ordering in place
ordered.retain(|o| !in_cycle.contains(o));
// The `visit` function adds child nodes before their parent, so reverse the order
ordered.reverse();
// Re-instate Vecs
self.ordered = ordered;
self.marked = marked;
self.marked_temp = marked_temp;
self.in_cycle = in_cycle;
self.cycle_breakers = cycle_breakers;
}
/// Render a single audio quantum by traversing the node list
pub fn render(&mut self, scope: &RenderScope) -> AudioRenderQuantum {
// if the audio graph was changed, determine the new ordering
if self.ordered.is_empty() {
self.order_nodes();
}
// keep track of end-of-lifecyle nodes
let mut nodes_dropped = false;
// for borrow-checker reasons, move mutable borrow of nodes out of self
let nodes = &mut self.nodes;
// process every node, in topological sorted order
self.ordered.iter().for_each(|index| {
// acquire a mutable borrow of the current processing node
let mut node = nodes.get(index).unwrap().borrow_mut();
// make sure all input buffers have the correct number of channels, this might not be
// the case if the node has no inputs connected or the channel count has just changed
let interpretation = node.channel_config.interpretation();
let count = node.channel_config.count();
node.inputs
.iter_mut()
.for_each(|i| i.mix(count, interpretation));
// let the current node process
let params = AudioParamValues::from(&*nodes);
scope.node_id.set(*index);
let tail_time = node.process(params, scope);
// iterate all outgoing edges, lookup these nodes and add to their input
node.outgoing_edges
.iter()
// audio params are connected to the 'hidden' usize::MAX output, ignore them here
.filter(|edge| edge.other_index != usize::MAX)
.for_each(|edge| {
let mut output_node = nodes.get(&edge.other_id).unwrap().borrow_mut();
output_node.has_inputs_connected = true;
let signal = &node.outputs[edge.self_index];
let channel_config = &output_node.channel_config.clone();
output_node.inputs[edge.other_index].add(signal, channel_config);
});
let can_free = node.can_free(tail_time);
// Node is not dropped.
if !can_free {
// Reset input buffers as they will be summed up in the next render quantum.
node.inputs
.iter_mut()
.for_each(AudioRenderQuantum::make_silent);
// Reset input state
node.has_inputs_connected = false;
}
drop(node); // release borrow of self.nodes
// Check if we can decommission this node (end of life)
if can_free {
// Node is dropped, remove it from the node list
nodes.remove(index);
// And remove it from the ordering after we have processed all nodes
nodes_dropped = true;
// Nodes are only dropped when they do not have incoming connections.
// But they may have AudioParams feeding into them, these can de dropped too.
nodes.retain(|id, n| {
id.0 < 2 // never drop Listener and Destination node
|| !n
.borrow()
.outgoing_edges
.iter()
.any(|e| e.other_id == *index)
});
}
});
// If there were any nodes decomissioned, remove from graph order
if nodes_dropped {
let mut i = 0;
while i < self.ordered.len() {
if !nodes.contains_key(&self.ordered[i]) {
self.ordered.remove(i);
} else {
i += 1;
}
}
}
// Return the output buffer of destination node
self.nodes
.get_mut(&AudioNodeId(0))
.unwrap()
.get_mut()
.outputs[0]
.clone()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[derive(Debug, Clone)]
struct TestNode {}
impl AudioProcessor for TestNode {
fn process(
&mut self,
_inputs: &[AudioRenderQuantum],
_outputs: &mut [AudioRenderQuantum],
_params: AudioParamValues,
_scope: &RenderScope,
) -> bool {
false
}
}
fn config() -> ChannelConfig {
crate::node::ChannelConfigOptions {
count: 2,
count_mode: crate::node::ChannelCountMode::Explicit,
interpretation: crate::node::ChannelInterpretation::Speakers,
}
.into()
}
#[test]
fn test_add_remove() {
let mut graph = Graph::new();
let node = Box::new(TestNode {});
graph.add_node(AudioNodeId(0), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(1), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(2), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(3), node, 1, 1, config());
graph.add_edge((AudioNodeId(1), 0), (AudioNodeId(0), 0));
graph.add_edge((AudioNodeId(2), 0), (AudioNodeId(1), 0));
graph.add_edge((AudioNodeId(3), 0), (AudioNodeId(0), 0));
graph.order_nodes();
// sorting is not deterministic, but this should uphold:
assert_eq!(graph.ordered.len(), 4); // all nodes present
assert_eq!(graph.ordered[3], AudioNodeId(0)); // root node comes last
let pos1 = graph
.ordered
.iter()
.position(|&n| n == AudioNodeId(1))
.unwrap();
let pos2 = graph
.ordered
.iter()
.position(|&n| n == AudioNodeId(2))
.unwrap();
assert!(pos2 < pos1); // node 1 depends on node 2
// Detach node 1 (and thus node 2) from the root node
graph.remove_edge(AudioNodeId(1), AudioNodeId(0));
graph.order_nodes();
// sorting is not deterministic, but this should uphold:
assert_eq!(graph.ordered.len(), 4); // all nodes present
let pos1 = graph
.ordered
.iter()
.position(|&n| n == AudioNodeId(1))
.unwrap();
let pos2 = graph
.ordered
.iter()
.position(|&n| n == AudioNodeId(2))
.unwrap();
assert!(pos2 < pos1); // node 1 depends on node 2
}
#[test]
fn test_remove_all() {
let mut graph = Graph::new();
let node = Box::new(TestNode {});
graph.add_node(AudioNodeId(0), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(1), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(2), node, 1, 1, config());
// link 1->0, 1->2 and 2->0
graph.add_edge((AudioNodeId(1), 0), (AudioNodeId(0), 0));
graph.add_edge((AudioNodeId(1), 0), (AudioNodeId(2), 0));
graph.add_edge((AudioNodeId(2), 0), (AudioNodeId(0), 0));
graph.order_nodes();
assert_eq!(
graph.ordered,
vec![AudioNodeId(1), AudioNodeId(2), AudioNodeId(0)]
);
graph.remove_edges_from(AudioNodeId(1));
graph.order_nodes();
// sorting is not deterministic, but this should uphold:
assert_eq!(graph.ordered.len(), 3); // all nodes present
let pos0 = graph
.ordered
.iter()
.position(|&n| n == AudioNodeId(0))
.unwrap();
let pos2 = graph
.ordered
.iter()
.position(|&n| n == AudioNodeId(2))
.unwrap();
assert!(pos2 < pos0); // node 1 depends on node 0
}
#[test]
fn test_cycle() {
let mut graph = Graph::new();
let node = Box::new(TestNode {});
graph.add_node(AudioNodeId(0), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(1), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(2), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(3), node.clone(), 1, 1, config());
graph.add_node(AudioNodeId(4), node, 1, 1, config());
// link 4->2, 2->1, 1->0, 1->2, 3->0
graph.add_edge((AudioNodeId(4), 0), (AudioNodeId(2), 0));
graph.add_edge((AudioNodeId(2), 0), (AudioNodeId(1), 0));
graph.add_edge((AudioNodeId(1), 0), (AudioNodeId(0), 0));
graph.add_edge((AudioNodeId(1), 0), (AudioNodeId(2), 0));
graph.add_edge((AudioNodeId(3), 0), (AudioNodeId(0), 0));
graph.order_nodes();
let pos0 = graph.ordered.iter().position(|&n| n == AudioNodeId(0));
let pos1 = graph.ordered.iter().position(|&n| n == AudioNodeId(1));
let pos2 = graph.ordered.iter().position(|&n| n == AudioNodeId(2));
let pos3 = graph.ordered.iter().position(|&n| n == AudioNodeId(3));
let pos4 = graph.ordered.iter().position(|&n| n == AudioNodeId(4));
// cycle 1<>2 should be removed
assert_eq!(pos1, None);
assert_eq!(pos2, None);
// detached leg from cycle will still be renderd
assert!(pos4.is_some());
// a-cyclic part should be present
assert!(pos3.unwrap() < pos0.unwrap());
}
}