rgx/
cursor.rs

1//! Opaque pagination cursor for the compact view. A cursor carries the entire query (pattern +
2//! options) plus a keyset resume position, so page N is provably the same search as page 1 (no flag
3//! can be dropped between pages) and a changed result set is detectable via the stored fingerprint.
4//! The encoded blob is parked in the daemon's [`crate::pagination`] store, which hands the caller a
5//! short token to echo back, so the blob itself never has to be small or text-safe. Encoding mirrors
6//! the hand-rolled, length-prefixed style in `proto` and reuses its exact options bit-layout.
7
8use std::hash::Hasher;
9
10use anyhow::{Result, bail};
11use rustc_hash::FxHasher;
12
13use crate::confirm::SearchOptions;
14use crate::proto::{pack_opts, unpack_opts};
15
16const KIND: u8 = 0x01;
17const VERSION: u8 = 0x02;
18
19/// The compact output shape a cursor paginates over.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
21pub enum Mode {
22    /// `path` + `  line: text` rows, paged by match (default).
23    #[default]
24    Matches,
25    /// One matching path per line (`-l`), paged by file.
26    Files,
27    /// `path:count` per file (`-c`), paged by file.
28    Count,
29}
30
31/// Everything needed to reproduce a query and resume where the previous page ended.
32#[derive(Debug, Clone, PartialEq, Eq)]
33pub struct Cursor {
34    pub mode: Mode,
35    pub pattern: String,
36    pub opts: SearchOptions,
37    pub page_size: usize,
38    /// Keyset position: resume after this `(path, lineno)` (lineno is 0 in files/count modes).
39    pub last_path: Option<String>,
40    pub last_lineno: u64,
41    /// `total_matches` when the cursor was minted, so a resume can report "N -> M matches".
42    pub prev_total: usize,
43    /// Low 32 bits of the result-set fingerprint when minted, for (advisory) staleness detection.
44    pub fingerprint: u32,
45    /// The positional path the query was scoped to, relative to the cwd (None = the cwd itself). The
46    /// caller pages from the same directory, so a short relative scope re-resolves the same tree.
47    pub root_hint: Option<String>,
48}
49
50/// Fold every `(path, lineno)` match key into a stable fingerprint; any add/remove/reorder changes it.
51pub fn fingerprint<'a>(keys: impl Iterator<Item = (&'a str, u64)>) -> u64 {
52    let mut h = FxHasher::default();
53    for (path, lineno) in keys {
54        h.write(path.as_bytes());
55        h.write_u8(0xff);
56        h.write_u64(lineno);
57    }
58    h.finish()
59}
60
61pub fn encode(c: &Cursor) -> Vec<u8> {
62    let mode = match c.mode {
63        Mode::Matches => 0,
64        Mode::Files => 1,
65        Mode::Count => 2,
66    };
67    let mut b = vec![KIND, VERSION, mode, pack_opts(&c.opts)];
68    put_varint(&mut b, c.opts.before_context as u64);
69    put_varint(&mut b, c.opts.after_context as u64);
70    put_varint(&mut b, c.page_size as u64);
71    put_varint(&mut b, c.prev_total as u64);
72    put_varint(&mut b, c.fingerprint as u64);
73    put_varint(&mut b, c.last_lineno);
74    put_opt(&mut b, c.last_path.as_deref());
75    put_opt(&mut b, c.root_hint.as_deref());
76    put_bytes(&mut b, c.pattern.as_bytes());
77    b
78}
79
80pub fn decode(bytes: &[u8]) -> Result<Cursor> {
81    let mut cur = bytes;
82    if take_u8(&mut cur)? != KIND {
83        bail!("not an rgx cursor");
84    }
85    if take_u8(&mut cur)? != VERSION {
86        bail!("unsupported cursor version");
87    }
88    let mode = match take_u8(&mut cur)? {
89        0 => Mode::Matches,
90        1 => Mode::Files,
91        2 => Mode::Count,
92        other => bail!("unknown cursor mode {other}"),
93    };
94    let packed = take_u8(&mut cur)?;
95    let before = take_varint(&mut cur)? as u32;
96    let after = take_varint(&mut cur)? as u32;
97    let opts = unpack_opts(packed, before, after);
98    let page_size = take_varint(&mut cur)? as usize;
99    let prev_total = take_varint(&mut cur)? as usize;
100    let fingerprint = take_varint(&mut cur)? as u32;
101    let last_lineno = take_varint(&mut cur)?;
102    let last_path = take_opt(&mut cur)?;
103    let root_hint = take_opt(&mut cur)?;
104    let pattern = String::from_utf8(take_bytes(&mut cur)?)?;
105    Ok(Cursor {
106        mode,
107        pattern,
108        opts,
109        page_size,
110        last_path,
111        last_lineno,
112        prev_total,
113        fingerprint,
114        root_hint,
115    })
116}
117
118/// LEB128 unsigned varint: small values cost 1 byte, keeping a typical cursor short.
119fn put_varint(buf: &mut Vec<u8>, mut n: u64) {
120    loop {
121        let byte = (n & 0x7f) as u8;
122        n >>= 7;
123        if n == 0 {
124            buf.push(byte);
125            return;
126        }
127        buf.push(byte | 0x80);
128    }
129}
130
131fn take_varint(cur: &mut &[u8]) -> Result<u64> {
132    let mut result: u64 = 0;
133    let mut shift = 0u32;
134    loop {
135        let b = take_u8(cur)?;
136        if shift >= 64 {
137            bail!("malformed cursor varint");
138        }
139        result |= u64::from(b & 0x7f) << shift;
140        if b & 0x80 == 0 {
141            return Ok(result);
142        }
143        shift += 7;
144    }
145}
146
147fn put_bytes(buf: &mut Vec<u8>, b: &[u8]) {
148    put_varint(buf, b.len() as u64);
149    buf.extend_from_slice(b);
150}
151
152fn put_opt(buf: &mut Vec<u8>, s: Option<&str>) {
153    match s {
154        Some(s) => {
155            buf.push(1);
156            put_bytes(buf, s.as_bytes());
157        }
158        None => buf.push(0),
159    }
160}
161
162fn take_u8(cur: &mut &[u8]) -> Result<u8> {
163    let (&b, rest) = cur
164        .split_first()
165        .ok_or_else(|| anyhow::anyhow!("truncated cursor"))?;
166    *cur = rest;
167    Ok(b)
168}
169
170fn take_bytes(cur: &mut &[u8]) -> Result<Vec<u8>> {
171    let n = take_varint(cur)? as usize;
172    if cur.len() < n {
173        bail!("truncated cursor");
174    }
175    let (head, rest) = cur.split_at(n);
176    *cur = rest;
177    Ok(head.to_vec())
178}
179
180fn take_opt(cur: &mut &[u8]) -> Result<Option<String>> {
181    Ok(match take_u8(cur)? {
182        0 => None,
183        _ => Some(String::from_utf8(take_bytes(cur)?)?),
184    })
185}
186
187#[cfg(test)]
188mod tests {
189    use super::*;
190
191    fn sample() -> Cursor {
192        Cursor {
193            mode: Mode::Count,
194            pattern: "Foo|Bar".into(),
195            opts: SearchOptions {
196                case_insensitive: true,
197                word: true,
198                after_context: 3,
199                ..Default::default()
200            },
201            page_size: 25,
202            last_path: Some("src/café.rs".into()),
203            last_lineno: 42,
204            prev_total: 421,
205            fingerprint: 0xdead_beef,
206            root_hint: Some("src/".into()),
207        }
208    }
209
210    #[test]
211    fn encode_decode_roundtrip() {
212        let c = sample();
213        assert_eq!(decode(&encode(&c)).unwrap(), c);
214    }
215
216    #[test]
217    fn decode_rejects_garbage() {
218        assert!(decode(b"not a cursor").is_err());
219        assert!(decode(b"").is_err());
220    }
221
222    #[test]
223    fn decode_rejects_wrong_kind() {
224        assert!(decode(&[0x02, VERSION, 0]).is_err());
225    }
226
227    #[test]
228    fn fingerprint_changes_when_keys_change() {
229        let a = fingerprint([("a.rs", 1), ("b.rs", 2)].into_iter());
230        let same = fingerprint([("a.rs", 1), ("b.rs", 2)].into_iter());
231        let diff = fingerprint([("a.rs", 1), ("b.rs", 3)].into_iter());
232        assert_eq!(a, same);
233        assert_ne!(a, diff);
234    }
235}
rgx/cursor.rs

rgx/
cursor.rs
