address review: grid fallback stays on snap positions and bars; thumbnail positions in f64

* MIDI: index controller dedup by channel and kind

Remove Duplicate Notes rescanned every controller already kept at the
same tick for each incoming one. A session whose sequence holds one tick
with many distinct channel/controller pairs made that quadratic and
blocked editing. Track where each channel+kind sits at the current tick
in a map instead; the last event per key still wins.

* MIDI: tag dedup index entries with their tick instead of clearing per tick

Clearing the map on every tick change cost O(capacity) per tick after a
dense tick. Store the tick with each entry and treat entries from an
earlier tick as absent. Add an oracle test comparing against the
previous per-tick rescan on mixed-tick input.

crates/midi/src/sequence.rs

@@ -1,4 +1,6 @@
 use serde::{Deserialize, Serialize};
+use std::collections::HashMap;
+use std::collections::hash_map::Entry;
 
 /// A MIDI note. Times are in model ticks ([`crate::PPQ`] per quarter note).
 #[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
@@ -108,14 +110,28 @@ impl Sequence {
 
         self.ctrls.sort_by_key(|c| c.tick);
         let mut kept: Vec<CtrlEvent> = Vec::with_capacity(self.ctrls.len());
+        // The latest tick and `kept` index of each channel+kind, so a same-tick repeat is found
+        // without rescanning the tick's events (a tick can hold many thousands of distinct keys).
+        // An entry from an earlier tick counts as absent; keeping the tick instead of clearing the
+        // map per tick keeps the work per event constant after a dense tick.
+        let mut last_at: HashMap<(u8, (u8, u8)), (i64, usize)> = HashMap::new();
         for c in self.ctrls.drain(..) {
             // Within a tick, replace an earlier event of the same channel+kind.
-            // Only events at the same tick (the tail of `kept`) can match.
-            let slot =
-                kept.iter_mut().rev().take_while(|k| k.tick == c.tick).find(|k| k.channel == c.channel && kind_key(k.kind) == kind_key(c.kind));
-            match slot {
-                Some(slot) => *slot = c,
-                None => kept.push(c),
+            match last_at.entry((c.channel, kind_key(c.kind))) {
+                Entry::Occupied(mut e) => {
+                    let (tick, idx) = *e.get();
+                    match kept.get_mut(idx) {
+                        Some(slot) if tick == c.tick => *slot = c,
+                        _ => {
+                            e.insert((c.tick, kept.len()));
+                            kept.push(c);
+                        }
+                    }
+                }
+                Entry::Vacant(e) => {
+                    e.insert((c.tick, kept.len()));
+                    kept.push(c);
+                }
             }
         }
         self.ctrls = kept;

crates/midi/tests/it/ops.rs

@@ -222,3 +222,72 @@ fn sequence_serde_round_trip() {
     let json = serde_json::to_string(&seq).unwrap();
     assert_eq!(serde_json::from_str::<Sequence>(&json).unwrap(), seq);
 }
+
+#[test]
+fn remove_duplicates_handles_a_large_same_tick_controller_group() {
+    // Every channel x controller number at one tick, twice: the second copy of each wins. A
+    // rescan of the tick's kept events per incoming event would make this quadratic.
+    let keys: Vec<(u8, u8)> = (0..=255u8).flat_map(|ch| (0..=255u8).map(move |cc| (ch, cc))).collect();
+    let ctrls = [0, 1]
+        .iter()
+        .flat_map(|&pass| keys.iter().map(move |&(channel, cc)| CtrlEvent { tick: 7, channel, kind: CtrlKind::Cc(cc), value: pass }))
+        .collect();
+    let mut seq = Sequence { notes: Vec::new(), ctrls };
+    let start = std::time::Instant::now();
+    assert_eq!(seq.remove_duplicates(), keys.len());
+    assert!(start.elapsed() < std::time::Duration::from_secs(10), "{:?}", start.elapsed());
+    assert_eq!(seq.ctrls.len(), keys.len());
+    assert!(seq.ctrls.iter().all(|c| c.value == 1));
+}
+
+#[test]
+fn remove_duplicates_matches_a_per_tick_rescan_on_mixed_ticks() {
+    // The straightforward per-tick rescan the indexed version replaced, kept as an oracle.
+    fn reference(mut ctrls: Vec<CtrlEvent>) -> Vec<CtrlEvent> {
+        ctrls.sort_by_key(|c| c.tick);
+        let key = |k: CtrlKind| match k {
+            CtrlKind::Cc(n) => (0, n),
+            CtrlKind::PitchBend => (1, 0),
+            CtrlKind::ChannelPressure => (2, 0),
+            CtrlKind::PolyPressure(p) => (3, p),
+            CtrlKind::Program => (4, 0),
+        };
+        let mut kept: Vec<CtrlEvent> = Vec::new();
+        for c in ctrls {
+            match kept.iter_mut().rev().take_while(|k| k.tick == c.tick).find(|k| k.channel == c.channel && key(k.kind) == key(c.kind)) {
+                Some(slot) => *slot = c,
+                None => kept.push(c),
+            }
+        }
+        kept
+    }
+
+    // Few ticks, channels and kinds, so the same key recurs both within a tick (interleaved with
+    // other keys) and across ticks; unsorted input from a fixed xorshift stream.
+    let mut state = 0x9E37_79B9_7F4A_7C15u64;
+    let mut next = move || {
+        state ^= state << 13;
+        state ^= state >> 7;
+        state ^= state << 17;
+        state
+    };
+    let kinds = |r: u64| match r % 5 {
+        0 => CtrlKind::Cc((r >> 8) as u8 % 4),
+        1 => CtrlKind::PitchBend,
+        2 => CtrlKind::ChannelPressure,
+        3 => CtrlKind::PolyPressure((r >> 8) as u8 % 4),
+        _ => CtrlKind::Program,
+    };
+    for round in 0..200 {
+        let mut ctrls = Vec::new();
+        for i in 0..(next() % 64) {
+            let r = next();
+            ctrls.push(CtrlEvent { tick: (r % 6) as i64 - 2, channel: (r >> 16) as u8 % 3, kind: kinds(r >> 24), value: (round * 100 + i) as i32 });
+        }
+        let mut seq = Sequence { notes: Vec::new(), ctrls: ctrls.clone() };
+        let removed = seq.remove_duplicates();
+        let expected = reference(ctrls.clone());
+        assert_eq!(seq.ctrls, expected, "round {round}");
+        assert_eq!(removed, ctrls.len() - expected.len(), "round {round}");
+    }
+}

crates/ui-egui/src/panels/midi_editor.rs

@@ -265,20 +265,42 @@ fn draw_roll_background(painter: &egui::Painter, g: &Roll<'_>) {
         }
     }
     // Grid.
+    let step = grid_stride(grid_ticks, px_per_tick);
     let mut tick = 0;
     while tick <= len_ticks {
         let bar = tick % (TICKS_PER_QUARTER * 4) == 0;
         let x = g.x_of(tick);
-        if grid_ticks as f32 * px_per_tick > 4.0 || bar {
-            painter.line_segment(
-                [pos2(x, roll.min.y), pos2(x, roll.max.y)],
-                Stroke::new(1.0, if bar { Color32::from_rgb(80, 80, 86) } else { Color32::from_rgb(50, 50, 54) }),
-            );
-        }
-        tick += grid_ticks;
+        painter.line_segment(
+            [pos2(x, roll.min.y), pos2(x, roll.max.y)],
+            Stroke::new(1.0, if bar { Color32::from_rgb(80, 80, 86) } else { Color32::from_rgb(50, 50, 54) }),
+        );
+        tick = tick.saturating_add(step);
     }
 }
 
+/// Closest lines the grid draws, in points.
+const MIN_GRID_PX: f32 = 4.0;
+
+/// Ticks between grid lines: the grid when its lines are more than [`MIN_GRID_PX`] apart, else
+/// as few common multiples of the grid and a bar as keep that spacing (so every line is a snap
+/// position and falls on a bar). The lines drawn are then bounded by the roll's width, however long
+/// the clip, instead of by its length.
+fn grid_stride(grid_ticks: i64, px_per_tick: f32) -> i64 {
+    let bar_ticks = TICKS_PER_QUARTER * 4;
+    if grid_ticks as f32 * px_per_tick > MIN_GRID_PX {
+        return grid_ticks.max(1);
+    }
+    let grid = grid_ticks.max(1);
+    let (mut a, mut b) = (grid, bar_ticks);
+    while b != 0 {
+        (a, b) = (b, a % b);
+    }
+    let common = (grid / a).saturating_mul(bar_ticks);
+    // `as` saturates a huge or NaN quotient; a zero `px_per_tick` gives one common multiple.
+    let n = (MIN_GRID_PX / (common as f32 * px_per_tick)).ceil().max(1.0) as i64;
+    common.saturating_mul(n)
+}
+
 /// The notes, with a drag in progress applied.
 fn draw_notes(app: &SoundApp, painter: &egui::Painter, g: &Roll<'_>, base: Color32) {
     let Roll { sequence, grid_ticks, .. } = *g;
@@ -478,6 +500,24 @@ fn velocity_lane(app: &mut SoundApp, ui: &mut Ui, g: &Roll<'_>, cid: ClipId, bas
 mod tests {
     use super::*;
 
+    #[test]
+    fn grid_lines_are_bounded_by_the_roll_width_not_the_clip_length() {
+        let sixteenth = TICKS_PER_QUARTER / 4;
+        // A 1000 pt roll showing a 4-bar clip: every sixteenth is 16 pt apart and drawn.
+        assert_eq!(grid_stride(sixteenth, 1000.0 / (16.0 * TICKS_PER_QUARTER as f32)), sixteenth);
+        // The same roll over a clip a billion ticks long: at most a line every 4 pt.
+        let (len, px_per_tick) = (1_000_000_000i64, 1000.0 / 1_000_000_000.0f32);
+        let step = grid_stride(sixteenth, px_per_tick);
+        assert_eq!(step % (TICKS_PER_QUARTER * 4), 0, "lines fall on bars");
+        assert!((len / step) <= 251, "{} lines", len / step);
+        // a dotted quarter grid (1440 ticks): every line is also a grid position
+        let dotted = TICKS_PER_QUARTER * 3 / 2;
+        let step = grid_stride(dotted, px_per_tick);
+        assert_eq!((step % dotted, step % (TICKS_PER_QUARTER * 4)), (0, 0), "lines are snap positions on bars: {step}");
+        assert!((len / step) <= 251, "{} lines", len / step);
+        assert!(grid_stride(0, 0.0) >= TICKS_PER_QUARTER * 4, "a zero grid or width still advances");
+    }
+
     #[test]
     fn switching_clip_drops_selection_and_gestures() {
         let mut st = MidiEditorState { selected: vec![0, 2], clip: Some(ClipId(1)), band: Some(pos2(1.0, 2.0)), ..Default::default() };

crates/ui-egui/src/panels/video_window.rs

@@ -115,6 +115,20 @@ fn first_movie_aspect(s: &soundcraft_model::Session) -> Option<f32> {
     s.videos.first().map(|v| v.aspect() as f32)
 }
 
+/// Most thumbnails one clip draws in the Video Universe strip: 8 pt each, so more than the
+/// widest strip holds.
+const MAX_UNIVERSE_THUMBS: usize = 1 << 12;
+
+/// Left edges of the thumbnails of a clip starting at `clip_x` (each `tw` wide) that lie in
+/// `shown_min..shown_max`. The index and position are worked out in `f64`: an `f32` this far from
+/// the origin (a clip starting a billion points left) cannot step by a thumbnail's width.
+fn thumb_xs(clip_x: f32, shown_min: f32, shown_max: f32, tw: f32) -> impl Iterator<Item = f32> {
+    let (origin, tw) = (f64::from(clip_x), f64::from(tw));
+    let first = ((f64::from(shown_min) - origin) / tw).floor().max(0.0);
+    let count = ((f64::from(shown_max) - origin) / tw - first).ceil().max(0.0) as usize;
+    (0..count.min(MAX_UNIVERSE_THUMBS)).map(move |i| (origin + (first + i as f64) * tw) as f32)
+}
+
 fn universe(app: &mut SoundApp, ctx: &egui::Context) {
     app.video.poll(ctx);
     let s = app.engine.session_arc();
@@ -145,8 +159,10 @@ fn universe(app: &mut SoundApp, ctx: &egui::Context) {
             }
             let tw = (cr.height() * v.aspect() as f32).max(8.0);
             let hpx = ((cr.height() * ppp / 16.0).ceil() * 16.0).clamp(16.0, 256.0) as u32;
-            let mut x = cr.min.x;
-            while x < cr.max.x {
+            // Only the thumbnails inside the strip, counted rather than stepped: a clip starting
+            // far left of it has an edge so large that adding a thumbnail's width wouldn't move it.
+            let shown = cr.intersect(r);
+            for x in thumb_xs(cr.min.x, shown.min.x, shown.max.x, tw) {
                 let secs = movie_secs(&s, c.start, offset, strip_position(x, r.min.x, r.width(), end, c.start)).max(0.0);
                 if let Some(tex) = app.video.thumb(ctx, key, &v.path, secs, hpx) {
                     let tr = Rect::from_min_size(pos2(x, cr.min.y), vec2(tw, cr.height()));
@@ -154,7 +170,6 @@ fn universe(app: &mut SoundApp, ctx: &egui::Context) {
                     let uv = Rect::from_min_max(pos2(0.0, 0.0), pos2((vis.width() / tw).clamp(0.0, 1.0), 1.0));
                     painter.image(tex.id(), vis, uv, Color32::WHITE);
                 }
-                x += tw;
             }
         }
         // The Edit window's visible range and the playhead.
@@ -182,7 +197,18 @@ fn universe(app: &mut SoundApp, ctx: &egui::Context) {
 
 #[cfg(test)]
 mod tests {
-    use super::strip_position;
+    use super::{strip_position, thumb_xs};
+
+    #[test]
+    fn thumbnails_of_a_clip_far_left_of_the_strip_are_evenly_spaced() {
+        // 2^30 points left of the strip with 8 pt thumbnails: f32 steps of `first + i` here are 16 apart
+        let xs: Vec<f32> = thumb_xs(-1_073_741_824.0, 0.0, 80.0, 8.0).collect();
+        assert_eq!(xs.len(), 10);
+        assert!(xs.windows(2).all(|w| w[1] - w[0] == 8.0), "{xs:?}");
+        assert_eq!(xs[0], 0.0);
+        // a clip inside the strip starts at its own edge
+        assert_eq!(thumb_xs(10.0, 10.0, 34.0, 8.0).collect::<Vec<_>>(), vec![10.0, 18.0, 26.0]);
+    }
 
     // A 1024 px strip over 1_024_000 samples: 1000 samples per point, exact in f32.
     const LEFT: f32 = 100.0;