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

nextest_runner/record/
run_id_index.rs
