Skip to main content

cellix_term/
pixels.rs

1use std::collections::btree_map::Entry;
2use std::collections::hash_map::DefaultHasher;
3use std::collections::{BTreeMap, HashMap, HashSet};
4use std::hash::{Hash, Hasher};
5use std::io::{self, Write};
6use std::time::{Duration, Instant};
7
8use base64::Engine;
9use cellix_render::{Grid, Image, Paint, Rasterizer, Rect, Rgb, UNIT};
10use flate2::{Compression, write::ZlibEncoder};
11
12use crate::Backend;
13
14/// Decoded image memory Cellix keeps in the terminal. Kitty's default limit is 320 MB and
15/// other terminals' are lower, so this stays well inside them.
16pub const DEFAULT_QUOTA: usize = 64 * 1024 * 1024;
17
18const CHUNK: usize = 4096;
19const PLACEHOLDER: char = '\u{10EEEE}';
20/// Row and column zero in the placeholder encoding.
21const DIACRITIC_ZERO: char = '\u{305}';
22
23/// Above the row tiles, so a scrolling region covers them and nothing else has to change.
24const SCROLL_LAYER: u32 = 1;
25/// Placement ids for a scrolling region, clear of the row placements.
26const FIRST_STRIP: usize = 100_000;
27/// Placement numbers a band adds, so each band of a row has its own.
28const BAND_PLACEMENTS: usize = 10_000;
29/// Rows of the page a glide can tell apart, which wrap round far out of sight.
30const STRIP_ROWS: i32 = 1 << 20;
31/// Pixels from the end at which a glide counts as there.
32const ARRIVED: f32 = 0.5;
33/// Screens of rows kept around the view, so turning round needs nothing sent.
34const KEPT_SCREENS: i32 = 3;
35
36/// How a region animates. Direct placement only, since only that can sit between cells.
37#[derive(Clone, Copy, Debug, PartialEq, Eq)]
38pub struct Smooth {
39    /// How often it moves.
40    pub frame: Duration,
41    /// How quickly it closes on where it's going: about two thirds of the way in this time.
42    pub ease: Duration,
43}
44
45/// How far tiles reach past the text area. Ghostty doesn't clip images, so a tile can cover
46/// its right and bottom padding, which no cell can. Left and top stay out of reach, and the
47/// frame there is the terminal's own colour.
48#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
49pub struct Bleed {
50    /// Columns past the right edge.
51    pub cols: u16,
52    /// Rows past the bottom edge.
53    pub rows: u16,
54    /// Pixels the last row's content moves down, to centre it in the band it now fills.
55    pub drop: usize,
56}
57
58struct Tile {
59    id: u32,
60    bytes: usize,
61    last_used: u64,
62}
63
64/// A scroll under way. Its rows are tiles the terminal already has, shown through a crop and
65/// a pixel offset, so moving costs a line of text per row and nothing has to be drawn. The
66/// screen underneath is already at the end, and this stands over it until it gets there.
67struct Glide {
68    area: Rect,
69    /// The rows of the page it's seen, counted from the top of the view when it started.
70    rows: BTreeMap<i32, u32>,
71    /// Where the view's heading, in rows from the start.
72    target: i32,
73    /// Where it is, in pixels from the start.
74    at: f32,
75    last: Instant,
76    /// The rows with a placement to take away.
77    placed: HashSet<i32>,
78}
79
80/// How tiles reach the screen. See the tier table in `docs/DESIGN.md`.
81#[derive(Clone, Copy, Debug, PartialEq, Eq)]
82pub enum Placement {
83    /// `a=p` at the cursor. Fails under tmux, which can't track it.
84    Direct,
85    /// Unicode placeholder cells, which tmux stores like text. Every graphics command
86    /// goes through tmux's DCS passthrough.
87    Placeholder,
88}
89
90/// Renders each row once as a tile, keeps it in the terminal's image store, and moves it
91/// by reference, so only new content crosses the wire.
92pub struct PixelBackend<R> {
93    rasterizer: R,
94    placement: Placement,
95    tiles: HashMap<u64, Tile>,
96    /// What's showing in each row, band by band.
97    shown: Vec<Vec<Option<u32>>>,
98    /// The bands those are.
99    bands: Vec<u16>,
100    size: (u16, u16),
101    next_id: u32,
102    used: usize,
103    quota: usize,
104    frame: u64,
105    smooth: Option<Smooth>,
106    /// Whether region placements are waiting to be removed by the next present.
107    scrolling: bool,
108    bleed: Bleed,
109    glide: Option<Glide>,
110    /// A cell's size in pixels, from the tiles.
111    cell: Option<(i32, i32)>,
112}
113
114/// What a row looks like, as a key: rows with the same key draw the same pixels.
115pub fn row_key(grid: &Grid, y: u16) -> u64 {
116    band_key(grid, y, (0, grid.width()))
117}
118
119/// What one band of a row looks like, as a key. It says nothing of where the row stands, so
120/// a row keeps its tile as it scrolls.
121fn band_key(grid: &Grid, y: u16, (from, to): (u16, u16)) -> u64 {
122    let mut hasher = DefaultHasher::new();
123    (from, to).hash(&mut hasher);
124    grid.row(y)[from as usize..to as usize].hash(&mut hasher);
125    let inside = |x: u16| x >= from && x < to;
126    let cursor = grid.cursor.filter(|c| c.1 == y && inside(c.0));
127    cursor.map(|c| c.0).hash(&mut hasher);
128    // Only on its own row: hashed everywhere, moving the caret resent the whole screen.
129    let (top, bottom) = (y as i32 * UNIT, (y as i32 + 1) * UNIT);
130    let (left, right) = (from as i32 * UNIT, to as i32 * UNIT);
131    let caret = grid
132        .caret
133        .filter(|c| c.y < bottom && c.y + c.h > top && c.x >= left && c.x < right);
134    caret.map(|c| (c.x, c.y - top, c.w, c.h)).hash(&mut hasher);
135    let meets = |paint: &&Paint| {
136        let (start, end) = paint.reach();
137        start < right && end > left
138    };
139    // Paint can stand in several rows, and each shows its own slice, which `on_row` keeps
140    // apart: the rows above and below a tall heading aren't the same tile.
141    for paint in grid.paint_on_row(y).filter(meets) {
142        paint.on_row(top).hash(&mut hasher);
143    }
144    hasher.finish()
145}
146
147/// Part of a row's image, between two pixel columns.
148fn crop(image: &Image, left: usize, right: usize) -> Image {
149    let mut rgb = Vec::with_capacity((right - left) * image.height * 3);
150    for line in image.rgb.chunks_exact(image.width * 3) {
151        rgb.extend_from_slice(&line[left * 3..right * 3]);
152    }
153    Image {
154        width: right - left,
155        height: image.height,
156        rgb,
157    }
158}
159
160fn place_number(y: u16, band: usize) -> usize {
161    y as usize + 1 + band * BAND_PLACEMENTS
162}
163
164fn zlib(data: &[u8]) -> Vec<u8> {
165    let mut z = ZlibEncoder::new(Vec::with_capacity(data.len() / 8), Compression::fast());
166    z.write_all(data).expect("writing to a Vec");
167    z.finish().expect("writing to a Vec")
168}
169
170impl<R: Rasterizer> PixelBackend<R> {
171    pub fn new(rasterizer: R, placement: Placement, quota: usize) -> Self {
172        Self {
173            rasterizer,
174            placement,
175            tiles: HashMap::new(),
176            shown: Vec::new(),
177            bands: Vec::new(),
178            size: (0, 0),
179            next_id: 1,
180            used: 0,
181            quota,
182            frame: 0,
183            smooth: None,
184            scrolling: false,
185            bleed: Bleed::default(),
186            glide: None,
187            cell: None,
188        }
189    }
190
191    /// Only direct placement can leave the text area: placeholders are cells.
192    pub fn with_bleed(mut self, bleed: Bleed) -> Self {
193        if self.placement == Placement::Direct {
194            self.bleed = bleed;
195        }
196        self
197    }
198
199    pub fn with_smooth(mut self, smooth: Smooth) -> Self {
200        self.smooth = (self.placement == Placement::Direct).then_some(smooth);
201        self
202    }
203
204    /// Writes one graphics command, wrapped for tmux in placeholder mode.
205    fn apc(&self, out: &mut Vec<u8>, control: &str, payload: &[u8]) {
206        let wrap = self.placement == Placement::Placeholder;
207        out.extend_from_slice(if wrap {
208            b"\x1bPtmux;\x1b\x1b_G"
209        } else {
210            b"\x1b_G"
211        });
212        out.extend_from_slice(control.as_bytes());
213        if !payload.is_empty() {
214            out.push(b';');
215            out.extend_from_slice(payload);
216        }
217        out.extend_from_slice(if wrap { b"\x1b\x1b\\\x1b\\" } else { b"\x1b\\" });
218    }
219
220    fn transmit(&self, out: &mut Vec<u8>, id: u32, image: &Image) {
221        let b64 = base64::engine::general_purpose::STANDARD.encode(zlib(&image.rgb));
222        let chunks: Vec<&[u8]> = b64.as_bytes().chunks(CHUNK).collect();
223        for (i, chunk) in chunks.iter().enumerate() {
224            let more = u8::from(i + 1 < chunks.len());
225            let control = if i == 0 {
226                format!(
227                    "a=t,f=24,o=z,t=d,q=2,i={id},s={},v={},m={more}",
228                    image.width, image.height
229                )
230            } else {
231                format!("m={more},q=2")
232            };
233            self.apc(out, &control, chunk);
234        }
235    }
236
237    /// Where a band of a row goes, and how many rows high.
238    fn place(
239        &self,
240        out: &mut Vec<u8>,
241        id: u32,
242        (y, band): (u16, usize),
243        (from, to): (u16, u16),
244        rows: u16,
245        last: bool,
246    ) {
247        let cols = to - from;
248        let _ = write!(out, "\x1b[{};{}H", y + 1, from + 1);
249        match self.placement {
250            Placement::Direct => {
251                let cols = cols + if last { self.bleed.cols } else { 0 };
252                let number = place_number(y, band);
253                let control = format!("a=p,i={id},p={number},c={cols},r={rows},C=1,q=2");
254                self.apc(out, &control, b"");
255            }
256            Placement::Placeholder => {
257                // The foreground colour carries the image id.
258                let (r, g, b) = ((id >> 16) & 255, (id >> 8) & 255, id & 255);
259                let _ = write!(out, "\x1b[38;2;{r};{g};{b}m");
260                let _ = write!(out, "{PLACEHOLDER}{DIACRITIC_ZERO}{DIACRITIC_ZERO}");
261                for _ in 1..cols {
262                    let _ = write!(out, "{PLACEHOLDER}");
263                }
264                out.extend_from_slice(b"\x1b[39m");
265            }
266        }
267    }
268
269    /// A row's image, grown to cover the padding beyond it in the colours at the edge.
270    fn bled(&self, image: Image, grid: &Grid, y: u16) -> Image {
271        let Bleed { cols, rows, drop } = self.bleed;
272        let cells = grid.row(y);
273        let (Some(last), true) = (cells.last(), cols > 0 || rows > 0) else {
274            return image;
275        };
276        let cell = image.width / cells.len();
277        let width = image.width + cols as usize * cell;
278        let paint = |line: &mut Vec<u8>, from: usize, to: usize, color: Rgb| {
279            for _ in from..to {
280                line.extend_from_slice(&[color.0, color.1, color.2]);
281            }
282        };
283        let mut rgb = Vec::new();
284        if y + 1 != grid.height() {
285            for line in image.rgb.chunks_exact(image.width * 3) {
286                rgb.extend_from_slice(line);
287                paint(&mut rgb, image.width, width, last.style.bg);
288            }
289            return Image {
290                width,
291                rgb,
292                ..image
293            };
294        }
295        // The bar's own colours run on below it, column by column.
296        let height = image.height * (1 + rows as usize);
297        let drop = drop.min(height - image.height);
298        let mut plain = Vec::with_capacity(width * 3);
299        for c in cells {
300            paint(&mut plain, 0, cell, c.style.bg);
301        }
302        paint(&mut plain, image.width, width, last.style.bg);
303        for _ in 0..drop {
304            rgb.extend_from_slice(&plain);
305        }
306        for line in image.rgb.chunks_exact(image.width * 3) {
307            rgb.extend_from_slice(line);
308            paint(&mut rgb, image.width, width, last.style.bg);
309        }
310        for _ in drop + image.height..height {
311            rgb.extend_from_slice(&plain);
312        }
313        Image { width, height, rgb }
314    }
315
316    /// The bands of a row, as (first column, column past the last). The last row is the
317    /// status bar, which nothing scrolls in, and its tile can reach below the text area.
318    fn spans(&self, grid: &Grid, y: u16) -> Vec<(u16, u16)> {
319        let width = grid.width();
320        if y + 1 == grid.height() {
321            return vec![(0, width)];
322        }
323        let inside = grid.bands.iter().copied().filter(|x| *x > 0 && *x < width);
324        let edges: Vec<u16> = [0].into_iter().chain(inside).chain([width]).collect();
325        edges.windows(2).map(|edge| (edge[0], edge[1])).collect()
326    }
327
328    /// The tile for each band of a row, rasterizing the row once if any of them is new.
329    fn band_tiles(&mut self, out: &mut Vec<u8>, grid: &Grid, y: u16) -> Vec<u32> {
330        let spans = self.spans(grid, y);
331        // The last row's tile is taller than the same row anywhere else.
332        let bottom = y + 1 == grid.height() && self.bleed.rows > 0;
333        let keys: Vec<u64> = spans
334            .iter()
335            .map(|span| band_key(grid, y, *span).rotate_left(u32::from(bottom)))
336            .collect();
337        if keys.iter().any(|key| !self.tiles.contains_key(key)) {
338            let image = self.rasterizer.row(grid, y);
339            let cols = grid.width();
340            let cell = image.width / cols.max(1) as usize;
341            self.cell = Some((cell as i32, image.height as i32));
342            let image = self.bled(image, grid, y);
343            for (&(from, to), key) in spans.iter().zip(&keys) {
344                if self.tiles.contains_key(key) {
345                    continue;
346                }
347                let right = if to == cols {
348                    image.width
349                } else {
350                    to as usize * cell
351                };
352                let part = crop(&image, from as usize * cell, right);
353                let id = self.new_id();
354                self.transmit(out, id, &part);
355                if self.placement == Placement::Placeholder {
356                    let wide = to - from;
357                    self.apc(out, &format!("a=p,U=1,i={id},c={wide},r=1,q=2"), b"");
358                }
359                self.used += part.rgb.len();
360                let tile = Tile {
361                    id,
362                    bytes: part.rgb.len(),
363                    last_used: self.frame,
364                };
365                self.tiles.insert(*key, tile);
366            }
367        }
368        let frame = self.frame;
369        let mut use_tile = |key: &u64| {
370            let tile = self.tiles.get_mut(key).expect("made above");
371            tile.last_used = frame;
372            tile.id
373        };
374        keys.iter().map(&mut use_tile).collect()
375    }
376
377    /// A glide from what's on screen now, whose rows are in the terminal already.
378    fn start_glide(&self, area: Rect, band: usize) -> Option<Glide> {
379        let shown = (area.y..area.bottom()).enumerate().map(|(index, y)| {
380            let id = (*self.shown.get(y as usize)?.get(band)?)?;
381            Some((index as i32, id))
382        });
383        Some(Glide {
384            area,
385            rows: shown.collect::<Option<_>>()?,
386            target: 0,
387            at: 0.0,
388            last: Instant::now(),
389            placed: HashSet::new(),
390        })
391    }
392
393    fn new_id(&mut self) -> u32 {
394        let id = self.next_id;
395        self.next_id = (self.next_id + 1) & 0xff_ffff;
396        if self.next_id == 0 {
397            self.next_id = 1;
398        }
399        id
400    }
401
402    /// Frees the least recently used tiles that aren't on screen.
403    fn evict(&mut self, out: &mut Vec<u8>, on_screen: &HashSet<u32>) {
404        while self.used > self.quota {
405            let oldest = self
406                .tiles
407                .iter()
408                .filter(|(_, t)| !on_screen.contains(&t.id))
409                .min_by_key(|(_, t)| t.last_used)
410                .map(|(key, _)| *key);
411            let Some(key) = oldest else { return };
412            let tile = self.tiles.remove(&key).expect("key came from the map");
413            self.used -= tile.bytes;
414            self.apc(out, &format!("a=d,d=I,i={},q=2", tile.id), b"");
415        }
416    }
417
418    pub fn tile_count(&self) -> usize {
419        self.tiles.len()
420    }
421
422    pub fn used_bytes(&self) -> usize {
423        self.used
424    }
425}
426
427impl<R: Rasterizer> Backend for PixelBackend<R> {
428    fn present(&mut self, grid: &Grid, out: &mut dyn Write) -> io::Result<()> {
429        let mut bytes = Vec::new();
430        bytes.extend_from_slice(b"\x1b[?2026h\x1b[?25l");
431        let size = (grid.width(), grid.height());
432        if size != self.size {
433            // Tiles are as wide as the grid, so a new width makes all of them useless.
434            self.apc(&mut bytes, "a=d,d=A,q=2", b"");
435            bytes.extend_from_slice(b"\x1b[2J");
436            self.tiles.clear();
437            self.glide = None;
438            self.used = 0;
439            self.shown = vec![Vec::new(); grid.height() as usize];
440            self.size = size;
441        }
442        if grid.bands != self.bands {
443            // The panels moved, so what's shown is cut in the wrong places. Tiles stay.
444            if self.placement == Placement::Direct {
445                self.apc(&mut bytes, "a=d,d=a,q=2", b"");
446            }
447            self.shown = vec![Vec::new(); grid.height() as usize];
448            self.bands.clone_from(&grid.bands);
449            self.glide = None;
450            self.scrolling = false;
451        }
452        self.frame += 1;
453        let mut on_screen = HashSet::new();
454        for y in 0..grid.height() {
455            let bottom = y + 1 == grid.height() && self.bleed.rows > 0;
456            let spans = self.spans(grid, y);
457            let ids = self.band_tiles(&mut bytes, grid, y);
458            self.shown[y as usize].resize(ids.len(), None);
459            for (band, (id, span)) in ids.into_iter().zip(spans).enumerate() {
460                on_screen.insert(id);
461                let old = self.shown[y as usize][band];
462                if old == Some(id) {
463                    continue;
464                }
465                // A placement belongs to its image, so a new image at this row doesn't
466                // replace the old one. Left alone, stale rows pile up as you scroll.
467                if let (Placement::Direct, Some(old)) = (self.placement, old) {
468                    let number = place_number(y, band);
469                    self.apc(&mut bytes, &format!("a=d,d=i,i={old},p={number},q=2"), b"");
470                }
471                let rows = 1 + if bottom { self.bleed.rows } else { 0 };
472                let last = span.1 == grid.width();
473                self.place(&mut bytes, id, (y, band), span, rows, last);
474                self.shown[y as usize][band] = Some(id);
475            }
476        }
477        if std::mem::take(&mut self.scrolling) {
478            self.apc(&mut bytes, &format!("a=d,d=z,z={SCROLL_LAYER},q=2"), b"");
479        }
480        on_screen.extend(self.glide.iter().flat_map(|g| g.rows.values().copied()));
481        self.evict(&mut bytes, &on_screen);
482        bytes.extend_from_slice(b"\x1b[?2026l");
483        out.write_all(&bytes)?;
484        out.flush()
485    }
486
487    fn scroll(
488        &mut self,
489        from: &Grid,
490        to: &Grid,
491        area: Rect,
492        rows: i32,
493        out: &mut dyn Write,
494    ) -> io::Result<()> {
495        let same_size = (from.width(), from.height()) == (to.width(), to.height());
496        let can_glide = self.smooth.is_some()
497            && self.cell.is_some()
498            && same_size
499            && self.size == (to.width(), to.height())
500            && rows != 0
501            && rows.abs() < area.h as i32;
502        let spans = self.spans(to, area.y);
503        let band = spans
504            .iter()
505            .position(|span| *span == (area.x, area.right()));
506        let same_area = self.glide.as_ref().is_none_or(|g| g.area == area);
507        let (true, true, Some(band)) = (can_glide, same_area, band) else {
508            self.settle();
509            return Ok(());
510        };
511        let Some(mut glide) = self.glide.take().or_else(|| self.start_glide(area, band)) else {
512            return Ok(());
513        };
514        let mut bytes = Vec::new();
515        glide.target += rows;
516        for (index, y) in (area.y..area.bottom()).enumerate() {
517            let row = glide.target + index as i32;
518            if let Entry::Vacant(place) = glide.rows.entry(row) {
519                place.insert(self.band_tiles(&mut bytes, to, y)[band]);
520            }
521        }
522        self.glide = Some(glide);
523        out.write_all(&bytes)?;
524        out.flush()
525    }
526
527    fn gliding(&self) -> Option<Duration> {
528        self.glide.as_ref()?;
529        self.smooth.map(|smooth| smooth.frame)
530    }
531
532    fn glide(&mut self, now: Instant, out: &mut dyn Write) -> io::Result<()> {
533        let (Some(mut glide), Some(smooth), Some((cell_w, cell_h))) =
534            (self.glide.take(), self.smooth, self.cell)
535        else {
536            return Ok(());
537        };
538        let target = (glide.target * cell_h) as f32;
539        let window = glide.area.h as i32 * cell_h;
540        // A long way behind, as after a hard flick, it would only look like lag.
541        glide.at = glide
542            .at
543            .clamp(target - window as f32, target + window as f32);
544        let passed = now.duration_since(glide.last).as_secs_f32();
545        glide.last = now;
546        let left = (-passed / smooth.ease.as_secs_f32()).exp();
547        glide.at = target + (glide.at - target) * left;
548        if (glide.at - target).abs() < ARRIVED {
549            glide.at = target;
550        }
551        let at = glide.at.round() as i32;
552        let wide = i32::from(glide.area.w) * cell_w;
553        let mut bytes = b"\x1b[?2026h".to_vec();
554        for (&row, &id) in &glide.rows {
555            let top = row * cell_h - at;
556            let (clip_top, clip_end) = ((-top).max(0), cell_h.min(window - top));
557            let number = FIRST_STRIP + row.rem_euclid(STRIP_ROWS) as usize;
558            if clip_top >= clip_end {
559                if glide.placed.remove(&row) {
560                    self.apc(&mut bytes, &format!("a=d,d=i,i={id},p={number},q=2"), b"");
561                }
562                continue;
563            }
564            let pixel = top.max(0);
565            let y = i32::from(glide.area.y) + pixel / cell_h;
566            let _ = write!(bytes, "\x1b[{};{}H", y + 1, glide.area.x + 1);
567            let control = format!(
568                "a=p,i={id},p={number},x=0,y={clip_top},w={wide},h={},Y={},z={SCROLL_LAYER},C=1,q=2",
569                clip_end - clip_top,
570                pixel % cell_h,
571            );
572            self.apc(&mut bytes, &control, b"");
573            glide.placed.insert(row);
574        }
575        bytes.extend_from_slice(b"\x1b[?2026l");
576        out.write_all(&bytes)?;
577        out.flush()?;
578        // What's far behind has no way back into view before it's drawn again.
579        let reach = glide.area.h as i32 * KEPT_SCREENS;
580        let view = at / cell_h;
581        glide
582            .rows
583            .retain(|row, _| (row - view).abs() <= reach || glide.placed.contains(row));
584        if glide.at == target {
585            self.scrolling = true;
586        } else {
587            self.glide = Some(glide);
588        }
589        Ok(())
590    }
591
592    fn settle(&mut self) {
593        self.scrolling |= self.glide.take().is_some();
594    }
595
596    fn invalidate(&mut self) {
597        self.size = (0, 0);
598        self.glide = None;
599    }
600}
601
602#[cfg(test)]
603mod tests {
604    use super::*;
605    use cellix_render::Style;
606
607    /// A row under a tall shape, like a page's sheet, is the same row wherever it stands, so it
608    /// keeps its picture as the page scrolls. Near the shape's rounded ends it isn't.
609    #[test]
610    fn a_row_under_a_tall_shape_is_known_wherever_it_stands() {
611        let mut grid = Grid::new(10, 30, Style::default());
612        let sheet = cellix_render::Bounds::cells(1.0, 0.0, 8.0, 30.0);
613        grid.panel(sheet, 40, Some(cellix_render::Rgb(250, 250, 250)), None);
614        assert_eq!(row_key(&grid, 10), row_key(&grid, 15));
615        assert_ne!(
616            row_key(&grid, 0),
617            row_key(&grid, 15),
618            "the rounded top shows in row 0"
619        );
620    }
621
622    /// Solid tiles, so these tests measure the protocol and not fonts.
623    struct Flat;
624
625    impl Rasterizer for Flat {
626        fn row(&mut self, grid: &Grid, _y: u16) -> Image {
627            Image {
628                width: grid.width() as usize,
629                height: 1,
630                rgb: vec![9; grid.width() as usize * 3],
631            }
632        }
633    }
634
635    /// Eight by sixteen, with a colour taken from the row's first letter.
636    struct Sized;
637
638    impl Rasterizer for Sized {
639        fn row(&mut self, grid: &Grid, y: u16) -> Image {
640            let tone = grid.row(y)[9].symbol.bytes().next().unwrap_or(0);
641            let (width, height) = (grid.width() as usize * 8, 16);
642            Image {
643                width,
644                height,
645                rgb: vec![tone; width * height * 3],
646            }
647        }
648    }
649
650    /// A sidebar in the first eight columns that stays still, and a pane that moves.
651    fn pane(top: usize) -> Grid {
652        let mut grid = Grid::new(20, 8, Style::default());
653        grid.bands = vec![PANE.x];
654        for y in 0..8 {
655            grid.put_str(0, y, &format!("side{y}"), Style::default(), 8);
656            let letter = char::from(b'a' + (top + y as usize) as u8);
657            grid.put_str(9, y, &letter.to_string(), Style::default(), 20);
658        }
659        grid
660    }
661
662    const PANE: Rect = Rect {
663        x: 8,
664        y: 1,
665        w: 12,
666        h: 6,
667    };
668
669    const STEP: Duration = Duration::from_millis(8);
670    const SMOOTH: Smooth = Smooth {
671        frame: STEP,
672        ease: Duration::from_millis(40),
673    };
674
675    fn smooth() -> PixelBackend<Sized> {
676        PixelBackend::new(Sized, Placement::Direct, DEFAULT_QUOTA).with_smooth(SMOOTH)
677    }
678
679    fn scroll(b: &mut PixelBackend<Sized>, from: &Grid, to: &Grid, rows: i32) -> String {
680        let mut out = Vec::new();
681        b.scroll(from, to, PANE, rows, &mut out).unwrap();
682        String::from_utf8(out).unwrap()
683    }
684
685    fn present_sized(b: &mut PixelBackend<Sized>, grid: &Grid) -> String {
686        let mut out = Vec::new();
687        b.present(grid, &mut out).unwrap();
688        String::from_utf8(out).unwrap()
689    }
690
691    #[test]
692    fn the_window_fills_to_its_edges() {
693        let mut b = PixelBackend::new(Sized, Placement::Direct, DEFAULT_QUOTA).with_bleed(Bleed {
694            cols: 2,
695            rows: 1,
696            drop: 3,
697        });
698        let grid = Grid::new(12, 2, Style::default());
699        let output = present_sized(&mut b, &grid);
700        let widths: Vec<String> = output
701            .split("\x1b_G")
702            .filter_map(|c| field(c, "s"))
703            .collect();
704        let tall: Vec<String> = output
705            .split("\x1b_G")
706            .filter_map(|c| field(c, "v"))
707            .collect();
708        assert!(
709            widths.iter().all(|w| w == "112"),
710            "two more cells: {widths:?}"
711        );
712        assert!(
713            tall.contains(&"32".to_string()),
714            "the last row takes two: {tall:?}"
715        );
716        assert!(tall.contains(&"16".to_string()));
717        let placed: Vec<&str> = output
718            .split("\x1b_G")
719            .filter(|c| c.starts_with("a=p"))
720            .collect();
721        assert!(placed.iter().all(|c| c.contains(",c=14,")), "{placed:?}");
722        assert!(placed[1].contains(",r=2,"), "{placed:?}");
723        let mut placeholders = PixelBackend::new(Sized, Placement::Placeholder, DEFAULT_QUOTA)
724            .with_bleed(Bleed {
725                cols: 2,
726                rows: 1,
727                drop: 3,
728            });
729        assert_eq!(
730            placeholders.bleed,
731            Bleed::default(),
732            "placeholders are cells"
733        );
734        let _ = present_sized(&mut placeholders, &grid);
735    }
736
737    #[test]
738    fn a_tall_heading_keeps_its_lower_half() {
739        let mut grid = Grid::new(20, 8, Style::default());
740        let big = cellix_render::Font {
741            size: 150,
742            ..cellix_render::Font::default()
743        };
744        grid.text_run((1.0, 3.5), 20.0, "Workflow", (Rgb(9, 9, 9), false), big);
745        assert_ne!(
746            row_key(&grid, 2),
747            row_key(&grid, 4),
748            "the row above and the row below show different slices"
749        );
750        let blank = Grid::new(20, 8, Style::default());
751        assert_eq!(
752            row_key(&blank, 2),
753            row_key(&blank, 4),
754            "empty rows still share a tile, which scrolling depends on"
755        );
756    }
757
758    /// Runs `count` frames of a glide, and gives back what they sent.
759    fn frames(b: &mut PixelBackend<Sized>, count: u32) -> String {
760        let mut out = Vec::new();
761        for _ in 0..count {
762            let now = b.glide.as_ref().map_or_else(Instant::now, |g| g.last) + STEP;
763            b.glide(now, &mut out).unwrap();
764        }
765        String::from_utf8(out).unwrap()
766    }
767
768    #[test]
769    fn regions_scroll_by_pixels() {
770        let mut b = smooth();
771        let (from, to) = (pane(0), pane(3));
772        present_sized(&mut b, &from);
773        scroll(&mut b, &from, &to, 3);
774        let moving = frames(&mut b, 4);
775        assert_eq!(count(&moving, "\x1b[?2026h"), 4, "every frame is atomic");
776        let offsets: HashSet<String> = moving
777            .split(",Y=")
778            .skip(1)
779            .map(|rest| rest.split(',').next().unwrap().to_string())
780            .collect();
781        assert!(
782            offsets.iter().any(|y| y != "0"),
783            "it sits between cells: {offsets:?}"
784        );
785        assert!(moving.contains(",z=1,"), "above the row tiles");
786        assert!(
787            !moving.contains("\x1b[1;9H"),
788            "nothing lands on the row above the pane"
789        );
790        assert!(
791            !moving.contains(";1H"),
792            "the sidebar's column is never touched"
793        );
794        frames(&mut b, 200);
795        assert_eq!(b.gliding(), None, "it gets there");
796        let settled = present_sized(&mut b, &to);
797        assert_eq!(
798            count(&settled, "a=d,d=z,z=1"),
799            1,
800            "the layer goes with the final page"
801        );
802        assert_eq!(count(&present_sized(&mut b, &to), "a=d,d=z"), 0);
803    }
804
805    #[test]
806    fn a_glide_moves_quickly_at_first_and_settles_gently() {
807        let mut b = smooth();
808        let (from, to) = (pane(0), pane(3));
809        present_sized(&mut b, &from);
810        scroll(&mut b, &from, &to, 3);
811        let mut places = vec![0.0];
812        while b.gliding().is_some() {
813            frames(&mut b, 1);
814            places.push(b.glide.as_ref().map_or(48.0, |g| g.at));
815            assert!(places.len() < 80, "it takes too long: {places:?}");
816        }
817        let steps: Vec<f32> = places.windows(2).map(|p| p[1] - p[0]).collect();
818        assert!(
819            steps.iter().all(|step| *step >= 0.0),
820            "never back: {steps:?}"
821        );
822        assert!(steps[0] > steps[steps.len() / 2], "it eases: {steps:?}");
823    }
824
825    #[test]
826    fn a_new_notch_carries_on_from_where_it_is() {
827        let mut b = smooth();
828        let (first, second, third) = (pane(0), pane(2), pane(4));
829        present_sized(&mut b, &first);
830        scroll(&mut b, &first, &second, 2);
831        frames(&mut b, 3);
832        let at = b.glide.as_ref().unwrap().at;
833        scroll(&mut b, &second, &third, 2);
834        let glide = b.glide.as_ref().unwrap();
835        assert_eq!((glide.at, glide.target), (at, 4), "no restart, no jump");
836    }
837
838    #[test]
839    fn the_wrong_way_turns_round_smoothly() {
840        let mut b = smooth();
841        let (first, second) = (pane(0), pane(2));
842        present_sized(&mut b, &first);
843        scroll(&mut b, &first, &second, 2);
844        frames(&mut b, 3);
845        let at = b.glide.as_ref().unwrap().at;
846        scroll(&mut b, &second, &first, -2);
847        frames(&mut b, 1);
848        let now = b.glide.as_ref().unwrap().at;
849        assert!(now < at && now > 0.0, "{at} then {now}");
850    }
851
852    #[test]
853    fn scrolling_only_sends_what_the_terminal_hasnt_seen() {
854        let mut b = smooth();
855        let (from, to) = (pane(0), pane(1));
856        present_sized(&mut b, &from);
857        let sent = count(&scroll(&mut b, &from, &to, 1), "a=t,");
858        assert!(sent <= 1, "at most the one new row, not {sent}");
859        assert_eq!(
860            count(&frames(&mut b, 5), "a=t,"),
861            0,
862            "moving costs no pictures"
863        );
864    }
865
866    #[test]
867    fn a_region_clips_at_its_edges() {
868        let mut b = smooth();
869        let (from, to) = (pane(0), pane(1));
870        present_sized(&mut b, &from);
871        scroll(&mut b, &from, &to, 1);
872        let moving = frames(&mut b, 3);
873        assert!(
874            moving.contains(",x=0,y="),
875            "the pane's own tiles: {moving:?}"
876        );
877        let clipped = moving
878            .split(",y=")
879            .skip(1)
880            .any(|rest| !rest.starts_with("0,"));
881        assert!(clipped, "the top row loses its top part: {moving:?}");
882    }
883
884    #[test]
885    fn scrolling_back_needs_nothing_new() {
886        let mut b = smooth();
887        let (from, to) = (pane(0), pane(2));
888        present_sized(&mut b, &from);
889        scroll(&mut b, &from, &to, 2);
890        frames(&mut b, 200);
891        present_sized(&mut b, &to);
892        let back = scroll(&mut b, &to, &from, -2);
893        assert_eq!(
894            count(&back, "a=t,"),
895            0,
896            "the tiles are in the terminal already"
897        );
898    }
899
900    #[test]
901    fn a_scrolled_page_keeps_its_tiles_whatever_stands_beside_it() {
902        let mut b = smooth();
903        let (from, to) = (pane(0), pane(3));
904        present_sized(&mut b, &from);
905        scroll(&mut b, &from, &to, 3);
906        frames(&mut b, 200);
907        let settled = present_sized(&mut b, &to);
908        // A row outside the region can change too, as this page has no bars there.
909        assert!(
910            count(&settled, "a=t,") <= 2,
911            "the region sent nothing: {settled:?}"
912        );
913    }
914
915    #[test]
916    fn a_change_in_one_band_sends_only_that_band() {
917        let mut b = smooth();
918        let mut grid = pane(0);
919        present_sized(&mut b, &grid);
920        grid.put_str(10, 3, "x", Style::default(), 20);
921        let sent = present_sized(&mut b, &grid);
922        assert_eq!(count(&sent, "a=t,"), 1, "{sent:?}");
923    }
924
925    #[test]
926    fn typeset_rows_keep_their_tiles_as_they_move() {
927        let text = |row: u16| Paint::Text {
928            x: 0,
929            y: i32::from(row) * UNIT,
930            max_width: 8 * UNIT,
931            text: "words".into(),
932            color: Rgb(1, 2, 3),
933            font: cellix_render::Font::default(),
934            align_right: false,
935            centred: false,
936            underline: false,
937        };
938        let mut grid = Grid::new(20, 8, Style::default());
939        grid.paint.extend([text(1), text(4)]);
940        assert_eq!(row_key(&grid, 1), row_key(&grid, 4));
941        assert_ne!(row_key(&grid, 1), row_key(&grid, 2));
942    }
943
944    #[test]
945    fn moving_a_panel_recuts_what_is_shown() {
946        let mut b = smooth();
947        let mut grid = pane(0);
948        present_sized(&mut b, &grid);
949        grid.bands = vec![4];
950        let sent = present_sized(&mut b, &grid);
951        assert_eq!(count(&sent, "a=d,d=a,"), 1, "the old cut goes first");
952        assert!(
953            sent.contains("\x1b[1;5H"),
954            "the new one is placed: {sent:?}"
955        );
956    }
957
958    #[test]
959    fn typing_ends_a_glide_at_once() {
960        let mut b = smooth();
961        let (from, to) = (pane(0), pane(3));
962        present_sized(&mut b, &from);
963        scroll(&mut b, &from, &to, 3);
964        frames(&mut b, 1);
965        b.settle();
966        assert_eq!(b.gliding(), None);
967        assert_eq!(count(&present_sized(&mut b, &to), "a=d,d=z,z=1"), 1);
968    }
969
970    #[test]
971    fn tiles_a_glide_is_showing_arent_thrown_away() {
972        let mut b = smooth();
973        let (from, to) = (pane(0), pane(3));
974        present_sized(&mut b, &from);
975        scroll(&mut b, &from, &to, 3);
976        b.quota = 0;
977        let held: Vec<u32> = b.glide.as_ref().unwrap().rows.values().copied().collect();
978        let sent = present_sized(&mut b, &to);
979        for id in held {
980            assert!(
981                !sent.contains(&format!("a=d,d=I,i={id},")),
982                "{id} is on show"
983            );
984        }
985    }
986
987    #[test]
988    fn a_jump_past_the_region_or_a_tier_without_pixels_doesnt_animate() {
989        let mut b = smooth();
990        let (from, to) = (pane(0), pane(9));
991        present_sized(&mut b, &from);
992        assert_eq!(scroll(&mut b, &from, &to, 9), "");
993        assert_eq!(b.gliding(), None);
994        let tmux =
995            PixelBackend::new(Sized, Placement::Placeholder, DEFAULT_QUOTA).with_smooth(SMOOTH);
996        assert_eq!(tmux.smooth, None);
997    }
998
999    fn page(top: usize) -> Grid {
1000        let mut grid = Grid::new(20, 5, Style::default());
1001        for y in 0..5 {
1002            let text = format!("line {}", top + y as usize);
1003            grid.put_str(0, y, &text, Style::default(), 20);
1004        }
1005        grid
1006    }
1007
1008    fn present(backend: &mut PixelBackend<Flat>, grid: &Grid) -> String {
1009        let mut out = Vec::new();
1010        backend.present(grid, &mut out).unwrap();
1011        String::from_utf8(out).unwrap()
1012    }
1013
1014    fn count(haystack: &str, needle: &str) -> usize {
1015        haystack.matches(needle).count()
1016    }
1017
1018    /// What a Kitty-protocol terminal keeps on screen: placements are keyed by image and
1019    /// placement id together, so a new image at a row doesn't replace the old one.
1020    #[derive(Default)]
1021    struct Screen {
1022        placements: HashMap<(u32, u32), u16>,
1023    }
1024
1025    fn field(control: &str, key: &str) -> Option<String> {
1026        control
1027            .split(',')
1028            .find_map(|kv| kv.strip_prefix(&format!("{key}=")).map(str::to_string))
1029    }
1030
1031    impl Screen {
1032        fn apply(&mut self, output: &str) {
1033            let mut rest = output;
1034            let mut row = 0;
1035            while let Some(at) = rest.find('\x1b') {
1036                rest = &rest[at..];
1037                if let Some(after) = rest.strip_prefix("\x1b_G") {
1038                    let end = after.find(['\x1b', ';']).unwrap_or(after.len());
1039                    let control = &after[..end];
1040                    let id = field(control, "i").and_then(|v| v.parse().ok());
1041                    let placement = field(control, "p").and_then(|v| v.parse().ok());
1042                    match (
1043                        field(control, "a").as_deref(),
1044                        field(control, "d").as_deref(),
1045                    ) {
1046                        (Some("p"), _) => {
1047                            self.placements
1048                                .insert((id.unwrap(), placement.unwrap()), row);
1049                        }
1050                        (Some("d"), Some("A")) => self.placements.clear(),
1051                        (Some("d"), Some("I" | "i")) => self.placements.retain(|k, _| {
1052                            k.0 != id.unwrap() || placement.is_some_and(|p| k.1 != p)
1053                        }),
1054                        _ => {}
1055                    }
1056                    rest = &rest[3..];
1057                } else {
1058                    let body = rest.strip_prefix("\x1b[").unwrap_or("");
1059                    if let Some(semi) = body.find(";1H")
1060                        && let Ok(y) = body[..semi].parse::<u16>()
1061                    {
1062                        row = y - 1;
1063                    }
1064                    rest = &rest[1..];
1065                }
1066            }
1067        }
1068
1069        fn rows(&self) -> Vec<usize> {
1070            let mut counts = vec![0; 5];
1071            for row in self.placements.values() {
1072                counts[*row as usize] += 1;
1073            }
1074            counts
1075        }
1076    }
1077
1078    #[test]
1079    fn scroll_leaves_exactly_one_tile_on_each_row() {
1080        let mut b = PixelBackend::new(Flat, Placement::Direct, DEFAULT_QUOTA);
1081        let mut screen = Screen::default();
1082        for top in [0, 1, 2, 3, 1, 0, 7, 2] {
1083            screen.apply(&present(&mut b, &page(top)));
1084            assert_eq!(screen.rows(), vec![1; 5], "after scrolling to {top}");
1085        }
1086    }
1087
1088    #[test]
1089    fn scroll_reuses_tiles_without_retransmit() {
1090        let mut b = PixelBackend::new(Flat, Placement::Direct, DEFAULT_QUOTA);
1091        assert_eq!(count(&present(&mut b, &page(0)), "a=t,"), 5);
1092        let scrolled = present(&mut b, &page(1));
1093        assert_eq!(count(&scrolled, "a=t,"), 1, "only the new line is sent");
1094        assert_eq!(count(&scrolled, "a=p,"), 5, "every row moves by reference");
1095        let back = present(&mut b, &page(0));
1096        assert_eq!(count(&back, "a=t,"), 0, "scrolling back sends nothing new");
1097    }
1098
1099    #[test]
1100    fn a_change_in_paint_makes_a_new_tile() {
1101        let mut b = PixelBackend::new(Flat, Placement::Direct, DEFAULT_QUOTA);
1102        let mut grid = page(0);
1103        present(&mut b, &grid);
1104        let bounds = cellix_render::Bounds::cells(0.0, 2.0, 4.0, 1.0);
1105        grid.panel(bounds, 0, Some(cellix_render::Rgb(1, 2, 3)), None);
1106        assert_eq!(
1107            count(&present(&mut b, &grid), "a=t,"),
1108            1,
1109            "only row 2 changed"
1110        );
1111    }
1112
1113    #[test]
1114    fn moving_the_caret_sends_only_its_rows() {
1115        let mut b = PixelBackend::new(Flat, Placement::Direct, DEFAULT_QUOTA);
1116        let mut grid = page(0);
1117        grid.set_caret(1.0, 1, 0.6);
1118        present(&mut b, &grid);
1119        let mut moved = page(0);
1120        moved.set_caret(2.0, 1, 0.6);
1121        assert_eq!(count(&present(&mut b, &moved), "a=t,"), 1, "only row 1");
1122    }
1123
1124    #[test]
1125    fn an_unchanged_frame_sends_no_graphics() {
1126        let mut b = PixelBackend::new(Flat, Placement::Direct, DEFAULT_QUOTA);
1127        present(&mut b, &page(0));
1128        let again = present(&mut b, &page(0));
1129        assert_eq!(count(&again, "\x1b_G"), 0);
1130    }
1131
1132    #[test]
1133    fn identical_rows_share_a_tile() {
1134        let mut b = PixelBackend::new(Flat, Placement::Direct, DEFAULT_QUOTA);
1135        let blank = Grid::new(20, 5, Style::default());
1136        let out = present(&mut b, &blank);
1137        assert_eq!(count(&out, "a=t,"), 1);
1138        assert_eq!(count(&out, "a=p,"), 5);
1139    }
1140
1141    #[test]
1142    fn placeholder_cells_are_passthrough_wrapped() {
1143        let mut b = PixelBackend::new(Flat, Placement::Placeholder, DEFAULT_QUOTA);
1144        let out = present(&mut b, &page(0));
1145        assert_eq!(
1146            count(&out, "\x1bPtmux;\x1b\x1b_G"),
1147            count(&out, "\x1b\x1b\\\x1b\\")
1148        );
1149        assert_eq!(count(&out.replace("\x1bPtmux;\x1b\x1b_G", ""), "\x1b_G"), 0);
1150        assert_eq!(count(&out, "a=p,U=1,"), 5);
1151        assert_eq!(count(&out, &PLACEHOLDER.to_string()), 5 * 20);
1152        assert!(out.contains("\u{10EEEE}\u{305}\u{305}"));
1153    }
1154
1155    #[test]
1156    fn placeholder_encodes_the_id_in_the_foreground() {
1157        let mut b = PixelBackend::new(Flat, Placement::Placeholder, DEFAULT_QUOTA);
1158        b.next_id = 0x01_02_03;
1159        let out = present(&mut b, &page(0));
1160        assert!(out.contains("\x1b[38;2;1;2;3m\u{10EEEE}"));
1161    }
1162
1163    #[test]
1164    fn tile_cache_respects_quota() {
1165        // Each tile is 60 bytes and a page is five tiles.
1166        let mut b = PixelBackend::new(Flat, Placement::Direct, 60 * 7);
1167        for top in 0..40 {
1168            present(&mut b, &page(top * 5));
1169        }
1170        assert!(b.used_bytes() <= 60 * 7, "used {}", b.used_bytes());
1171        assert!(b.tile_count() >= 5, "the visible page must survive");
1172    }
1173
1174    #[test]
1175    fn eviction_never_removes_a_visible_tile() {
1176        let mut b = PixelBackend::new(Flat, Placement::Direct, 60);
1177        let out = present(&mut b, &page(0));
1178        assert_eq!(count(&out, "a=d,d=I"), 0, "all five tiles are on screen");
1179        assert_eq!(b.tile_count(), 5);
1180    }
1181
1182    #[test]
1183    fn evicted_tiles_are_freed_in_the_terminal() {
1184        let mut b = PixelBackend::new(Flat, Placement::Direct, 60 * 5);
1185        present(&mut b, &page(0));
1186        let out = present(&mut b, &page(5));
1187        assert_eq!(count(&out, "a=d,d=I"), 5);
1188    }
1189
1190    #[test]
1191    fn resize_clears_the_terminal_store() {
1192        let mut b = PixelBackend::new(Flat, Placement::Direct, DEFAULT_QUOTA);
1193        present(&mut b, &page(0));
1194        let wider = Grid::new(30, 5, Style::default());
1195        let out = present(&mut b, &wider);
1196        assert!(out.contains("a=d,d=A"));
1197        assert_eq!(b.tile_count(), 1);
1198    }
1199}