nextest_runner/record/
run_id_index.rs

1// Copyright (c) The nextest Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Index for run IDs enabling efficient prefix lookup and shortest unique prefix computation.
5
6use super::{format::has_zip_extension, store::RecordedRunInfo};
7use crate::errors::{InvalidRunIdOrRecordingSelector, InvalidRunIdSelector};
8use camino::Utf8PathBuf;
9use quick_junit::ReportUuid;
10use std::{fmt, str::FromStr};
11
12/// Selector that can be either a run ID (for store lookup) or a recording path.
13///
14/// Used by commands that can consume recorded runs from either source, such as
15/// `store info`, `replay`, and `run --rerun`.
16///
17/// When parsing from a string:
18/// - Paths ending in `.zip` are treated as recording paths.
19/// - Everything else is parsed as a [`RunIdSelector`].
20#[derive(Clone, Debug, PartialEq, Eq)]
21pub enum RunIdOrRecordingSelector {
22    /// Select from the run store.
23    RunId(RunIdSelector),
24    /// Read from a portable recording file.
25    RecordingPath(Utf8PathBuf),
26}
27
28impl FromStr for RunIdOrRecordingSelector {
29    type Err = InvalidRunIdOrRecordingSelector;
30
31    fn from_str(s: &str) -> Result<Self, Self::Err> {
32        let path = Utf8PathBuf::from(s);
33        if has_zip_extension(&path) {
34            Ok(RunIdOrRecordingSelector::RecordingPath(path))
35        } else {
36            match s.parse::<RunIdSelector>() {
37                Ok(selector) => Ok(RunIdOrRecordingSelector::RunId(selector)),
38                Err(_) => Err(InvalidRunIdOrRecordingSelector {
39                    input: s.to_owned(),
40                }),
41            }
42        }
43    }
44}
45
46impl Default for RunIdOrRecordingSelector {
47    fn default() -> Self {
48        RunIdOrRecordingSelector::RunId(RunIdSelector::Latest)
49    }
50}
51
52impl fmt::Display for RunIdOrRecordingSelector {
53    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
54        match self {
55            RunIdOrRecordingSelector::RunId(selector) => write!(f, "{selector}"),
56            RunIdOrRecordingSelector::RecordingPath(path) => write!(f, "{path}"),
57        }
58    }
59}
60
61/// Selector for identifying a run, either the most recent or by prefix.
62///
63/// This is used by CLI commands that need to specify a run ID. The `Latest`
64/// variant selects the most recent completed run, while `Prefix` allows
65/// specifying a run by its ID prefix.
66#[derive(Clone, Debug, Default, PartialEq, Eq)]
67pub enum RunIdSelector {
68    /// Select the most recent completed run.
69    #[default]
70    Latest,
71
72    /// Select a run by ID prefix.
73    ///
74    /// The prefix contains only hex digits and optional dashes (for UUID format).
75    Prefix(String),
76}
77
78impl FromStr for RunIdSelector {
79    type Err = InvalidRunIdSelector;
80
81    fn from_str(s: &str) -> Result<Self, Self::Err> {
82        if s == "latest" {
83            Ok(RunIdSelector::Latest)
84        } else {
85            // Validate that the prefix contains only hex digits and dashes.
86            let is_valid = !s.is_empty() && s.chars().all(|c| c.is_ascii_hexdigit() || c == '-');
87            if is_valid {
88                Ok(RunIdSelector::Prefix(s.to_owned()))
89            } else {
90                Err(InvalidRunIdSelector {
91                    input: s.to_owned(),
92                })
93            }
94        }
95    }
96}
97
98impl fmt::Display for RunIdSelector {
99    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
100        match self {
101            RunIdSelector::Latest => write!(f, "latest"),
102            RunIdSelector::Prefix(prefix) => write!(f, "{prefix}"),
103        }
104    }
105}
106
107/// An index of run IDs enabling efficient prefix lookup and shortest unique
108/// prefix computation.
109///
110/// This uses a sorted index with neighbor comparison (inspired by jujutsu's
111/// approach) rather than a trie. For each ID, the shortest unique prefix is
112/// determined by comparing with the lexicographically adjacent IDs—the minimum
113/// prefix length needed to distinguish from both neighbors.
114#[derive(Clone, Debug)]
115pub struct RunIdIndex {
116    /// Run IDs paired with their normalized hex representation, sorted by hex.
117    sorted_entries: Vec<RunIdIndexEntry>,
118}
119
120/// An entry in the run ID index.
121#[derive(Clone, Debug)]
122struct RunIdIndexEntry {
123    run_id: ReportUuid,
124    /// Normalized hex representation (lowercase, no dashes).
125    hex: String,
126}
127
128impl RunIdIndex {
129    /// Creates a new index from a list of runs.
130    pub fn new(runs: &[RecordedRunInfo]) -> Self {
131        let mut sorted_entries: Vec<_> = runs
132            .iter()
133            .map(|r| RunIdIndexEntry {
134                run_id: r.run_id,
135                hex: r.run_id.to_string().replace('-', "").to_lowercase(),
136            })
137            .collect();
138
139        // Sort by normalized hex representation for consistent ordering.
140        sorted_entries.sort_by(|a, b| a.hex.cmp(&b.hex));
141        Self { sorted_entries }
142    }
143
144    /// Returns the shortest unique prefix length for the given run ID.
145    ///
146    /// The returned length is in hex characters (not including dashes). Returns `None` if the
147    /// run ID is not in the index.
148    pub fn shortest_unique_prefix_len(&self, run_id: ReportUuid) -> Option<usize> {
149        // Find the position of this ID in the sorted list.
150        let pos = self
151            .sorted_entries
152            .iter()
153            .position(|entry| entry.run_id == run_id)?;
154
155        let target_hex = &self.sorted_entries[pos].hex;
156
157        // Compare with neighbors to find the minimum distinguishing prefix length.
158        let mut min_len = 1; // At least 1 character.
159
160        // Compare with previous neighbor.
161        if pos > 0 {
162            let prev_hex = &self.sorted_entries[pos - 1].hex;
163            let common = common_hex_prefix_len(target_hex, prev_hex);
164            min_len = min_len.max(common + 1);
165        }
166
167        // Compare with next neighbor.
168        if pos + 1 < self.sorted_entries.len() {
169            let next_hex = &self.sorted_entries[pos + 1].hex;
170            let common = common_hex_prefix_len(target_hex, next_hex);
171            min_len = min_len.max(common + 1);
172        }
173
174        Some(min_len)
175    }
176
177    /// Returns the shortest unique prefix for the given run ID.
178    ///
179    /// The prefix is the minimum string needed to uniquely identify this run
180    /// among all runs in the index. Both parts include dashes in the standard
181    /// UUID positions.
182    ///
183    /// Returns `None` if the run ID is not in the index.
184    pub fn shortest_unique_prefix(&self, run_id: ReportUuid) -> Option<ShortestRunIdPrefix> {
185        let prefix_len = self.shortest_unique_prefix_len(run_id)?;
186        Some(ShortestRunIdPrefix::new(run_id, prefix_len))
187    }
188
189    /// Resolves a prefix to a run ID.
190    ///
191    /// The prefix can include or omit dashes. Returns `Ok(run_id)` if exactly
192    /// one run matches, or an error if none or multiple match.
193    pub fn resolve_prefix(&self, prefix: &str) -> Result<ReportUuid, PrefixResolutionError> {
194        // Validate and normalize the prefix.
195        let normalized = prefix.replace('-', "").to_lowercase();
196        if !normalized.chars().all(|c| c.is_ascii_hexdigit()) {
197            return Err(PrefixResolutionError::InvalidPrefix);
198        }
199
200        // Find all matching IDs using binary search for the range.
201        // First, find the start of the range.
202        let start = self
203            .sorted_entries
204            .partition_point(|entry| entry.hex.as_str() < normalized.as_str());
205
206        // Collect matches: all entries whose hex starts with the normalized prefix.
207        let matches: Vec<_> = self.sorted_entries[start..]
208            .iter()
209            .take_while(|entry| entry.hex.starts_with(&normalized))
210            .map(|entry| entry.run_id)
211            .collect();
212
213        match matches.len() {
214            0 => Err(PrefixResolutionError::NotFound),
215            1 => Ok(matches[0]),
216            n => {
217                let candidates = matches.into_iter().take(8).collect();
218                Err(PrefixResolutionError::Ambiguous {
219                    count: n,
220                    candidates,
221                })
222            }
223        }
224    }
225
226    /// Returns the number of run IDs in the index.
227    pub fn len(&self) -> usize {
228        self.sorted_entries.len()
229    }
230
231    /// Returns true if the index is empty.
232    pub fn is_empty(&self) -> bool {
233        self.sorted_entries.is_empty()
234    }
235
236    /// Returns an iterator over all run IDs in sorted order.
237    pub fn iter(&self) -> impl Iterator<Item = ReportUuid> + '_ {
238        self.sorted_entries.iter().map(|entry| entry.run_id)
239    }
240}
241
242/// The shortest unique prefix for a run ID, split into the unique prefix and remaining portion.
243///
244/// This is useful for display purposes where the unique prefix can be highlighted differently
245/// (e.g., in a different color) from the rest of the ID.
246#[derive(Clone, Debug, PartialEq, Eq)]
247pub struct ShortestRunIdPrefix {
248    /// The unique prefix portion (the minimum needed to identify this run).
249    pub prefix: String,
250    /// The remaining portion of the run ID.
251    pub rest: String,
252}
253
254impl ShortestRunIdPrefix {
255    /// Creates a new shortest prefix by splitting a UUID at the given hex character count.
256    ///
257    /// The `hex_len` is the number of hex characters (not including dashes) for the prefix.
258    fn new(run_id: ReportUuid, hex_len: usize) -> Self {
259        let full = run_id.to_string();
260
261        // The UUID format is xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx.
262        // The dash positions (0-indexed) are at 8, 13, 18, 23.
263        // We need to find the string index that corresponds to `hex_len` hex characters.
264        let split_index = hex_len_to_string_index(hex_len);
265        let split_index = split_index.min(full.len());
266
267        let (prefix, rest) = full.split_at(split_index);
268        Self {
269            prefix: prefix.to_string(),
270            rest: rest.to_string(),
271        }
272    }
273
274    /// Returns the full run ID by concatenating prefix and rest.
275    pub fn full(&self) -> String {
276        format!("{}{}", self.prefix, self.rest)
277    }
278}
279
280/// Converts a hex character count to a string index in UUID format.
281///
282/// UUID format: `xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx`
283/// - Positions 0-7: 8 hex chars
284/// - Position 8: dash
285/// - Positions 9-12: 4 hex chars (total 12)
286/// - Position 13: dash
287/// - Positions 14-17: 4 hex chars (total 16)
288/// - Position 18: dash
289/// - Positions 19-22: 4 hex chars (total 20)
290/// - Position 23: dash
291/// - Positions 24-35: 12 hex chars (total 32)
292fn hex_len_to_string_index(hex_len: usize) -> usize {
293    // Count how many dashes come before the hex_len'th hex character.
294    let dashes = match hex_len {
295        0..=8 => 0,
296        9..=12 => 1,
297        13..=16 => 2,
298        17..=20 => 3,
299        21..=32 => 4,
300        _ => 4, // Max 32 hex chars in a UUID.
301    };
302    hex_len + dashes
303}
304
305/// Computes the length of the common prefix between two hex strings.
306fn common_hex_prefix_len(a: &str, b: &str) -> usize {
307    a.chars()
308        .zip(b.chars())
309        .take_while(|(ca, cb)| ca == cb)
310        .count()
311}
312
313/// Internal error type for prefix resolution.
314///
315/// This is converted to [`crate::errors::RunIdResolutionError`] by
316/// [`super::store::RunStoreSnapshot::resolve_run_id`], which can enrich the
317/// error with full `RecordedRunInfo` data.
318#[derive(Clone, Debug)]
319pub enum PrefixResolutionError {
320    /// No run found matching the prefix.
321    NotFound,
322
323    /// Multiple runs match the prefix.
324    Ambiguous {
325        /// The total number of matching runs.
326        count: usize,
327        /// The candidates that matched (up to a limit).
328        candidates: Vec<ReportUuid>,
329    },
330
331    /// The prefix contains invalid characters (expected hexadecimal).
332    InvalidPrefix,
333}
334
335#[cfg(test)]
336mod tests {
337    use super::*;
338    use crate::record::{RecordedRunStatus, RecordedSizes, format::STORE_FORMAT_VERSION};
339    use chrono::TimeZone;
340    use semver::Version;
341    use std::collections::BTreeMap;
342
343    /// Creates a test run with the given run ID.
344    fn make_run(run_id: ReportUuid) -> RecordedRunInfo {
345        let started_at = chrono::FixedOffset::east_opt(0)
346            .unwrap()
347            .with_ymd_and_hms(2024, 1, 1, 0, 0, 0)
348            .unwrap();
349        RecordedRunInfo {
350            run_id,
351            store_format_version: STORE_FORMAT_VERSION,
352            nextest_version: Version::new(0, 1, 0),
353            started_at,
354            last_written_at: started_at,
355            duration_secs: None,
356            cli_args: Vec::new(),
357            build_scope_args: Vec::new(),
358            env_vars: BTreeMap::new(),
359            parent_run_id: None,
360            sizes: RecordedSizes::default(),
361            status: RecordedRunStatus::Incomplete,
362        }
363    }
364
365    #[test]
366    fn test_empty_index() {
367        let index = RunIdIndex::new(&[]);
368        assert!(index.is_empty());
369        assert_eq!(index.len(), 0);
370    }
371
372    #[test]
373    fn test_single_entry() {
374        let runs = vec![make_run(ReportUuid::from_u128(
375            0x550e8400_e29b_41d4_a716_446655440000,
376        ))];
377        let index = RunIdIndex::new(&runs);
378
379        assert_eq!(index.len(), 1);
380
381        // With only one entry, shortest prefix is 1 character.
382        assert_eq!(index.shortest_unique_prefix_len(runs[0].run_id), Some(1));
383
384        let prefix = index.shortest_unique_prefix(runs[0].run_id).unwrap();
385        assert_eq!(prefix.prefix, "5");
386        assert_eq!(prefix.rest, "50e8400-e29b-41d4-a716-446655440000");
387        assert_eq!(prefix.full(), "550e8400-e29b-41d4-a716-446655440000");
388    }
389
390    #[test]
391    fn test_shared_prefix() {
392        // Two UUIDs that share the first 4 hex characters "5555".
393        let runs = vec![
394            make_run(ReportUuid::from_u128(
395                0x55551111_0000_0000_0000_000000000000,
396            )),
397            make_run(ReportUuid::from_u128(
398                0x55552222_0000_0000_0000_000000000000,
399            )),
400        ];
401        let index = RunIdIndex::new(&runs);
402
403        // Both need 5 characters to be unique (shared "5555", differ at position 5).
404        assert_eq!(index.shortest_unique_prefix_len(runs[0].run_id), Some(5));
405        assert_eq!(index.shortest_unique_prefix_len(runs[1].run_id), Some(5));
406
407        let prefix0 = index.shortest_unique_prefix(runs[0].run_id).unwrap();
408        assert_eq!(prefix0.prefix, "55551");
409        assert_eq!(prefix0.rest, "111-0000-0000-0000-000000000000");
410
411        let prefix1 = index.shortest_unique_prefix(runs[1].run_id).unwrap();
412        assert_eq!(prefix1.prefix, "55552");
413    }
414
415    #[test]
416    fn test_asymmetric_neighbors() {
417        // Three UUIDs where prefix lengths differ based on neighbors.
418        // 1111... < 1112... < 2222...
419        let runs = vec![
420            make_run(ReportUuid::from_u128(
421                0x11110000_0000_0000_0000_000000000000,
422            )),
423            make_run(ReportUuid::from_u128(
424                0x11120000_0000_0000_0000_000000000000,
425            )),
426            make_run(ReportUuid::from_u128(
427                0x22220000_0000_0000_0000_000000000000,
428            )),
429        ];
430        let index = RunIdIndex::new(&runs);
431
432        // First two share "111", need 4 chars each.
433        assert_eq!(index.shortest_unique_prefix_len(runs[0].run_id), Some(4));
434        assert_eq!(index.shortest_unique_prefix_len(runs[1].run_id), Some(4));
435        // Third differs at first char from its only neighbor.
436        assert_eq!(index.shortest_unique_prefix_len(runs[2].run_id), Some(1));
437    }
438
439    #[test]
440    fn test_prefix_crosses_dash() {
441        // Prefix extends past the first dash (position 8). Share first 9 hex chars.
442        let runs = vec![
443            make_run(ReportUuid::from_u128(
444                0x12345678_9000_0000_0000_000000000000,
445            )),
446            make_run(ReportUuid::from_u128(
447                0x12345678_9111_0000_0000_000000000000,
448            )),
449        ];
450        let index = RunIdIndex::new(&runs);
451
452        assert_eq!(index.shortest_unique_prefix_len(runs[0].run_id), Some(10));
453
454        // Prefix string includes the dash.
455        let prefix = index.shortest_unique_prefix(runs[0].run_id).unwrap();
456        assert_eq!(prefix.prefix, "12345678-90");
457        assert_eq!(prefix.rest, "00-0000-0000-000000000000");
458    }
459
460    #[test]
461    fn test_resolve_prefix() {
462        let runs = vec![
463            make_run(ReportUuid::from_u128(
464                0xabcdef00_1234_5678_9abc_def012345678,
465            )),
466            make_run(ReportUuid::from_u128(
467                0x22222222_2222_2222_2222_222222222222,
468            )),
469            make_run(ReportUuid::from_u128(
470                0x23333333_3333_3333_3333_333333333333,
471            )),
472        ];
473        let index = RunIdIndex::new(&runs);
474
475        // Single match.
476        assert_eq!(index.resolve_prefix("abc").unwrap(), runs[0].run_id);
477        assert_eq!(index.resolve_prefix("22").unwrap(), runs[1].run_id);
478
479        // Case insensitive.
480        assert_eq!(index.resolve_prefix("ABC").unwrap(), runs[0].run_id);
481        assert_eq!(index.resolve_prefix("AbC").unwrap(), runs[0].run_id);
482
483        // With dashes.
484        assert_eq!(index.resolve_prefix("abcdef00-").unwrap(), runs[0].run_id);
485        assert_eq!(index.resolve_prefix("abcdef00-12").unwrap(), runs[0].run_id);
486
487        // Ambiguous.
488        let err = index.resolve_prefix("2").unwrap_err();
489        assert!(matches!(
490            err,
491            PrefixResolutionError::Ambiguous { count: 2, .. }
492        ));
493
494        // Not found.
495        let err = index.resolve_prefix("9").unwrap_err();
496        assert!(matches!(err, PrefixResolutionError::NotFound));
497
498        // Invalid.
499        let err = index.resolve_prefix("xyz").unwrap_err();
500        assert!(matches!(err, PrefixResolutionError::InvalidPrefix));
501    }
502
503    #[test]
504    fn test_not_in_index() {
505        let runs = vec![make_run(ReportUuid::from_u128(
506            0x11111111_1111_1111_1111_111111111111,
507        ))];
508        let index = RunIdIndex::new(&runs);
509
510        let other = ReportUuid::from_u128(0x22222222_2222_2222_2222_222222222222);
511        assert_eq!(index.shortest_unique_prefix_len(other), None);
512        assert_eq!(index.shortest_unique_prefix(other), None);
513    }
514
515    #[test]
516    fn test_hex_len_to_string_index() {
517        // Before first dash (position 8).
518        assert_eq!(hex_len_to_string_index(0), 0);
519        assert_eq!(hex_len_to_string_index(8), 8);
520        // After each dash.
521        assert_eq!(hex_len_to_string_index(9), 10);
522        assert_eq!(hex_len_to_string_index(13), 15);
523        assert_eq!(hex_len_to_string_index(17), 20);
524        assert_eq!(hex_len_to_string_index(21), 25);
525        // Full UUID.
526        assert_eq!(hex_len_to_string_index(32), 36);
527    }
528
529    #[test]
530    fn test_run_id_selector_default() {
531        assert_eq!(RunIdSelector::default(), RunIdSelector::Latest);
532    }
533
534    #[test]
535    fn test_run_id_selector_from_str() {
536        // Only exact "latest" parses to Latest.
537        assert_eq!(
538            "latest".parse::<RunIdSelector>().unwrap(),
539            RunIdSelector::Latest
540        );
541
542        // Valid hex prefixes.
543        assert_eq!(
544            "abc123".parse::<RunIdSelector>().unwrap(),
545            RunIdSelector::Prefix("abc123".to_owned())
546        );
547        assert_eq!(
548            "550e8400-e29b-41d4".parse::<RunIdSelector>().unwrap(),
549            RunIdSelector::Prefix("550e8400-e29b-41d4".to_owned())
550        );
551        assert_eq!(
552            "ABCDEF".parse::<RunIdSelector>().unwrap(),
553            RunIdSelector::Prefix("ABCDEF".to_owned())
554        );
555        assert_eq!(
556            "0".parse::<RunIdSelector>().unwrap(),
557            RunIdSelector::Prefix("0".to_owned())
558        );
559
560        // "Latest" contains non-hex characters.
561        assert!("Latest".parse::<RunIdSelector>().is_err());
562        assert!("LATEST".parse::<RunIdSelector>().is_err());
563
564        // Contains non-hex characters.
565        assert!("xyz".parse::<RunIdSelector>().is_err());
566        assert!("abc_123".parse::<RunIdSelector>().is_err());
567        assert!("hello".parse::<RunIdSelector>().is_err());
568
569        // Empty string is invalid.
570        assert!("".parse::<RunIdSelector>().is_err());
571    }
572
573    #[test]
574    fn test_run_id_selector_display() {
575        assert_eq!(RunIdSelector::Latest.to_string(), "latest");
576        assert_eq!(
577            RunIdSelector::Prefix("abc123".to_owned()).to_string(),
578            "abc123"
579        );
580    }
581
582    #[test]
583    fn test_run_id_or_archive_selector_default() {
584        assert_eq!(
585            RunIdOrRecordingSelector::default(),
586            RunIdOrRecordingSelector::RunId(RunIdSelector::Latest)
587        );
588    }
589
590    #[test]
591    fn test_run_id_or_archive_selector_from_str() {
592        // "latest" parses to RunId(Latest).
593        assert_eq!(
594            "latest".parse::<RunIdOrRecordingSelector>().unwrap(),
595            RunIdOrRecordingSelector::RunId(RunIdSelector::Latest)
596        );
597
598        // Hex prefixes parse to RunId(Prefix(...)).
599        assert_eq!(
600            "abc123".parse::<RunIdOrRecordingSelector>().unwrap(),
601            RunIdOrRecordingSelector::RunId(RunIdSelector::Prefix("abc123".to_owned()))
602        );
603
604        // Paths ending in .zip parse to RecordingPath.
605        assert_eq!(
606            "nextest-run-abc123.zip"
607                .parse::<RunIdOrRecordingSelector>()
608                .unwrap(),
609            RunIdOrRecordingSelector::RecordingPath(Utf8PathBuf::from("nextest-run-abc123.zip"))
610        );
611        assert_eq!(
612            "/path/to/archive.zip"
613                .parse::<RunIdOrRecordingSelector>()
614                .unwrap(),
615            RunIdOrRecordingSelector::RecordingPath(Utf8PathBuf::from("/path/to/archive.zip"))
616        );
617        assert_eq!(
618            "../relative/path.zip"
619                .parse::<RunIdOrRecordingSelector>()
620                .unwrap(),
621            RunIdOrRecordingSelector::RecordingPath(Utf8PathBuf::from("../relative/path.zip"))
622        );
623
624        // Invalid run ID selector (not hex, not .zip) still fails.
625        assert!("xyz".parse::<RunIdOrRecordingSelector>().is_err());
626        assert!("hello".parse::<RunIdOrRecordingSelector>().is_err());
627    }
628
629    #[test]
630    fn test_run_id_or_archive_selector_display() {
631        assert_eq!(
632            RunIdOrRecordingSelector::RunId(RunIdSelector::Latest).to_string(),
633            "latest"
634        );
635        assert_eq!(
636            RunIdOrRecordingSelector::RunId(RunIdSelector::Prefix("abc123".to_owned())).to_string(),
637            "abc123"
638        );
639        assert_eq!(
640            RunIdOrRecordingSelector::RecordingPath(Utf8PathBuf::from("/path/to/archive.zip"))
641                .to_string(),
642            "/path/to/archive.zip"
643        );
644    }
645}