jj_lib/
id_prefix.rs

1// Copyright 2023 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![expect(missing_docs)]
16
17use std::iter;
18use std::marker::PhantomData;
19use std::sync::Arc;
20
21use itertools::Itertools as _;
22use once_cell::sync::OnceCell;
23use thiserror::Error;
24
25use crate::backend::ChangeId;
26use crate::backend::CommitId;
27use crate::hex_util;
28use crate::object_id::HexPrefix;
29use crate::object_id::ObjectId;
30use crate::object_id::PrefixResolution;
31use crate::repo::Repo;
32use crate::revset::RevsetEvaluationError;
33use crate::revset::RevsetExtensions;
34use crate::revset::RevsetResolutionError;
35use crate::revset::SymbolResolver;
36use crate::revset::SymbolResolverExtension;
37use crate::revset::UserRevsetExpression;
38use crate::view::View;
39
40#[derive(Debug, Error)]
41pub enum IdPrefixIndexLoadError {
42    #[error("Failed to resolve short-prefixes disambiguation revset")]
43    Resolution(#[from] RevsetResolutionError),
44    #[error("Failed to evaluate short-prefixes disambiguation revset")]
45    Evaluation(#[from] RevsetEvaluationError),
46}
47
48struct DisambiguationData {
49    expression: Arc<UserRevsetExpression>,
50    indexes: OnceCell<Indexes>,
51}
52
53struct Indexes {
54    commit_change_ids: Vec<(CommitId, ChangeId)>,
55    commit_index: IdIndex<CommitId, u32, 4>,
56    change_index: IdIndex<ChangeId, u32, 4>,
57}
58
59impl DisambiguationData {
60    fn indexes(
61        &self,
62        repo: &dyn Repo,
63        extensions: &[Box<dyn SymbolResolverExtension>],
64    ) -> Result<&Indexes, IdPrefixIndexLoadError> {
65        self.indexes.get_or_try_init(|| {
66            let symbol_resolver = SymbolResolver::new(repo, extensions);
67            let revset = self
68                .expression
69                .resolve_user_expression(repo, &symbol_resolver)?
70                .evaluate(repo)?;
71
72            let commit_change_ids: Vec<_> = revset.commit_change_ids().try_collect()?;
73            let mut commit_index = IdIndex::with_capacity(commit_change_ids.len());
74            let mut change_index = IdIndex::with_capacity(commit_change_ids.len());
75            for (i, (commit_id, change_id)) in commit_change_ids.iter().enumerate() {
76                let i: u32 = i.try_into().unwrap();
77                commit_index.insert(commit_id, i);
78                change_index.insert(change_id, i);
79            }
80            Ok(Indexes {
81                commit_change_ids,
82                commit_index: commit_index.build(),
83                change_index: change_index.build(),
84            })
85        })
86    }
87}
88
89impl<'a> IdIndexSource<u32> for &'a [(CommitId, ChangeId)] {
90    type Entry = &'a (CommitId, ChangeId);
91
92    fn entry_at(&self, pointer: &u32) -> Self::Entry {
93        &self[*pointer as usize]
94    }
95}
96
97impl IdIndexSourceEntry<CommitId> for &'_ (CommitId, ChangeId) {
98    fn to_key(&self) -> CommitId {
99        let (commit_id, _) = self;
100        commit_id.clone()
101    }
102}
103
104impl IdIndexSourceEntry<ChangeId> for &'_ (CommitId, ChangeId) {
105    fn to_key(&self) -> ChangeId {
106        let (_, change_id) = self;
107        change_id.clone()
108    }
109}
110
111/// Manages configuration and cache of commit/change ID disambiguation index.
112#[derive(Default)]
113pub struct IdPrefixContext {
114    disambiguation: Option<DisambiguationData>,
115    extensions: Arc<RevsetExtensions>,
116}
117
118impl IdPrefixContext {
119    pub fn new(extensions: Arc<RevsetExtensions>) -> Self {
120        Self {
121            disambiguation: None,
122            extensions,
123        }
124    }
125
126    pub fn disambiguate_within(mut self, expression: Arc<UserRevsetExpression>) -> Self {
127        self.disambiguation = Some(DisambiguationData {
128            expression,
129            indexes: OnceCell::new(),
130        });
131        self
132    }
133
134    /// Loads disambiguation index once, returns a borrowed index to
135    /// disambiguate commit/change IDs.
136    pub fn populate(&self, repo: &dyn Repo) -> Result<IdPrefixIndex<'_>, IdPrefixIndexLoadError> {
137        let indexes = if let Some(disambiguation) = &self.disambiguation {
138            Some(disambiguation.indexes(repo, self.extensions.symbol_resolvers())?)
139        } else {
140            None
141        };
142        Ok(IdPrefixIndex { indexes })
143    }
144}
145
146/// Loaded index to disambiguate commit/change IDs.
147pub struct IdPrefixIndex<'a> {
148    indexes: Option<&'a Indexes>,
149}
150
151impl IdPrefixIndex<'_> {
152    /// Returns an empty index that just falls back to a provided `repo`.
153    pub const fn empty() -> IdPrefixIndex<'static> {
154        IdPrefixIndex { indexes: None }
155    }
156
157    /// Resolve an unambiguous commit ID prefix.
158    pub fn resolve_commit_prefix(
159        &self,
160        repo: &dyn Repo,
161        prefix: &HexPrefix,
162    ) -> PrefixResolution<CommitId> {
163        if let Some(indexes) = self.indexes {
164            let resolution = indexes
165                .commit_index
166                .resolve_prefix_to_key(&*indexes.commit_change_ids, prefix);
167            match resolution {
168                PrefixResolution::NoMatch => {
169                    // Fall back to resolving in entire repo
170                }
171                PrefixResolution::SingleMatch(id) => {
172                    // The disambiguation set may be loaded from a different repo,
173                    // and contain a commit that doesn't exist in the current repo.
174                    if repo.index().has_id(&id) {
175                        return PrefixResolution::SingleMatch(id);
176                    } else {
177                        return PrefixResolution::NoMatch;
178                    }
179                }
180                PrefixResolution::AmbiguousMatch => {
181                    return PrefixResolution::AmbiguousMatch;
182                }
183            }
184        }
185        repo.index().resolve_commit_id_prefix(prefix)
186    }
187
188    /// Returns the shortest length of a prefix of `commit_id` that can still be
189    /// resolved by `resolve_commit_prefix()` and [`SymbolResolver`].
190    pub fn shortest_commit_prefix_len(&self, repo: &dyn Repo, commit_id: &CommitId) -> usize {
191        let len = self.shortest_commit_prefix_len_exact(repo, commit_id);
192        disambiguate_prefix_with_refs(repo.view(), &commit_id.to_string(), len)
193    }
194
195    pub fn shortest_commit_prefix_len_exact(&self, repo: &dyn Repo, commit_id: &CommitId) -> usize {
196        if let Some(indexes) = self.indexes
197            && let Some(lookup) = indexes
198                .commit_index
199                .lookup_exact(&*indexes.commit_change_ids, commit_id)
200        {
201            return lookup.shortest_unique_prefix_len();
202        }
203        repo.index().shortest_unique_commit_id_prefix_len(commit_id)
204    }
205
206    /// Resolve an unambiguous change ID prefix to the commit IDs in the revset.
207    pub fn resolve_change_prefix(
208        &self,
209        repo: &dyn Repo,
210        prefix: &HexPrefix,
211    ) -> PrefixResolution<Vec<CommitId>> {
212        if let Some(indexes) = self.indexes {
213            let resolution = indexes
214                .change_index
215                .resolve_prefix_to_key(&*indexes.commit_change_ids, prefix);
216            match resolution {
217                PrefixResolution::NoMatch => {
218                    // Fall back to resolving in entire repo
219                }
220                PrefixResolution::SingleMatch(change_id) => {
221                    return match repo.resolve_change_id(&change_id) {
222                        // There may be more commits with this change id outside the narrower sets.
223                        Some(commit_ids) => PrefixResolution::SingleMatch(commit_ids),
224                        // The disambiguation set may contain hidden commits.
225                        None => PrefixResolution::NoMatch,
226                    };
227                }
228                PrefixResolution::AmbiguousMatch => {
229                    return PrefixResolution::AmbiguousMatch;
230                }
231            }
232        }
233        repo.resolve_change_id_prefix(prefix)
234    }
235
236    /// Returns the shortest length of a prefix of `change_id` that can still be
237    /// resolved by `resolve_change_prefix()` and [`SymbolResolver`].
238    pub fn shortest_change_prefix_len(&self, repo: &dyn Repo, change_id: &ChangeId) -> usize {
239        let len = self.shortest_change_prefix_len_exact(repo, change_id);
240        disambiguate_prefix_with_refs(repo.view(), &change_id.to_string(), len)
241    }
242
243    fn shortest_change_prefix_len_exact(&self, repo: &dyn Repo, change_id: &ChangeId) -> usize {
244        if let Some(indexes) = self.indexes
245            && let Some(lookup) = indexes
246                .change_index
247                .lookup_exact(&*indexes.commit_change_ids, change_id)
248        {
249            return lookup.shortest_unique_prefix_len();
250        }
251        repo.shortest_unique_change_id_prefix_len(change_id)
252    }
253}
254
255fn disambiguate_prefix_with_refs(view: &View, id_sym: &str, min_len: usize) -> usize {
256    debug_assert!(id_sym.is_ascii());
257    (min_len..id_sym.len())
258        .find(|&n| {
259            // Tags, bookmarks, and Git refs have higher priority, but Git refs
260            // should include "/" char. Extension symbols have lower priority.
261            let prefix = &id_sym[..n];
262            view.get_local_tag(prefix.as_ref()).is_absent()
263                && view.get_local_bookmark(prefix.as_ref()).is_absent()
264        })
265        // No need to test conflicts with the full ID. We have to return some
266        // valid length anyway.
267        .unwrap_or(id_sym.len())
268}
269
270/// In-memory immutable index to do prefix lookup of key `K` through `P`.
271///
272/// In a nutshell, this is a mapping of `K` -> `P` -> `S::Entry` where `S:
273/// IdIndexSource<P>`. The source table `S` isn't owned by this index.
274///
275/// This index stores first `N` bytes of each key `K` associated with the
276/// pointer `P`. `K` may be a heap-allocated object. `P` is supposed to be
277/// a cheap value type like `u32` or `usize`. As the index entry of type
278/// `([u8; N], P)` is small and has no indirect reference, constructing
279/// the index should be faster than sorting the source `(K, _)` pairs.
280///
281/// A key `K` must be at least `N` bytes long.
282#[derive(Clone, Debug)]
283pub struct IdIndex<K, P, const N: usize> {
284    // Maybe better to build separate (keys, values) vectors, but there's no std function
285    // to co-sort them.
286    index: Vec<([u8; N], P)>,
287    // Let's pretend [u8; N] above were of type K. It helps type inference, and ensures that
288    // IdIndexSource has the same key type.
289    phantom_key: PhantomData<K>,
290}
291
292/// Source table for `IdIndex` to map pointer of type `P` to entry.
293pub trait IdIndexSource<P> {
294    type Entry;
295
296    fn entry_at(&self, pointer: &P) -> Self::Entry;
297}
298
299/// Source table entry of `IdIndex`, which is conceptually a `(key, value)`
300/// pair.
301pub trait IdIndexSourceEntry<K> {
302    fn to_key(&self) -> K;
303}
304
305#[derive(Clone, Debug)]
306pub struct IdIndexBuilder<K, P, const N: usize> {
307    unsorted_index: Vec<([u8; N], P)>,
308    phantom_key: PhantomData<K>,
309}
310
311impl<K, P, const N: usize> IdIndexBuilder<K, P, N>
312where
313    K: ObjectId + Ord,
314{
315    /// Inserts new entry. Multiple values can be associated with a single key.
316    pub fn insert(&mut self, key: &K, pointer: P) {
317        let short_key = unwrap_as_short_key(key.as_bytes());
318        self.unsorted_index.push((*short_key, pointer));
319    }
320
321    pub fn build(self) -> IdIndex<K, P, N> {
322        let mut index = self.unsorted_index;
323        index.sort_unstable_by_key(|(s, _)| *s);
324        let phantom_key = self.phantom_key;
325        IdIndex { index, phantom_key }
326    }
327}
328
329impl<K, P, const N: usize> IdIndex<K, P, N>
330where
331    K: ObjectId + Ord,
332{
333    pub fn builder() -> IdIndexBuilder<K, P, N> {
334        IdIndexBuilder {
335            unsorted_index: Vec::new(),
336            phantom_key: PhantomData,
337        }
338    }
339
340    pub fn with_capacity(capacity: usize) -> IdIndexBuilder<K, P, N> {
341        IdIndexBuilder {
342            unsorted_index: Vec::with_capacity(capacity),
343            phantom_key: PhantomData,
344        }
345    }
346
347    /// Looks up entries with the given prefix, and collects values if matched
348    /// entries have unambiguous keys.
349    pub fn resolve_prefix_with<B, S, U>(
350        &self,
351        source: S,
352        prefix: &HexPrefix,
353        entry_mapper: impl FnMut(S::Entry) -> U,
354    ) -> PrefixResolution<(K, B)>
355    where
356        B: FromIterator<U>,
357        S: IdIndexSource<P>,
358        S::Entry: IdIndexSourceEntry<K>,
359    {
360        fn collect<B, K, E, U>(
361            mut range: impl Iterator<Item = (K, E)>,
362            mut entry_mapper: impl FnMut(E) -> U,
363        ) -> PrefixResolution<(K, B)>
364        where
365            B: FromIterator<U>,
366            K: Eq,
367        {
368            if let Some((first_key, first_entry)) = range.next() {
369                let maybe_values: Option<B> = iter::once(Some(entry_mapper(first_entry)))
370                    .chain(range.map(|(k, e)| (k == first_key).then(|| entry_mapper(e))))
371                    .collect();
372                if let Some(values) = maybe_values {
373                    PrefixResolution::SingleMatch((first_key, values))
374                } else {
375                    PrefixResolution::AmbiguousMatch
376                }
377            } else {
378                PrefixResolution::NoMatch
379            }
380        }
381
382        let min_bytes = prefix.min_prefix_bytes();
383        if min_bytes.is_empty() {
384            // We consider an empty prefix ambiguous even if the index has a single entry.
385            return PrefixResolution::AmbiguousMatch;
386        }
387
388        let to_key_entry_pair = |(_, pointer): &(_, P)| -> (K, S::Entry) {
389            let entry = source.entry_at(pointer);
390            (entry.to_key(), entry)
391        };
392        if min_bytes.len() > N {
393            // If the min prefix (including odd byte) is longer than the stored short keys,
394            // we are sure that min_bytes[..N] does not include the odd byte. Use it to
395            // take contiguous range, then filter by (longer) prefix.matches().
396            let short_bytes = unwrap_as_short_key(min_bytes);
397            let pos = self.index.partition_point(|(s, _)| s < short_bytes);
398            let range = self.index[pos..]
399                .iter()
400                .take_while(|(s, _)| s == short_bytes)
401                .map(to_key_entry_pair)
402                .filter(|(k, _)| prefix.matches(k));
403            collect(range, entry_mapper)
404        } else {
405            // Otherwise, use prefix.matches() to deal with odd byte. Since the prefix is
406            // covered by short key width, we're sure that the matching prefixes are sorted.
407            let pos = self.index.partition_point(|(s, _)| &s[..] < min_bytes);
408            let range = self.index[pos..]
409                .iter()
410                .map(to_key_entry_pair)
411                .take_while(|(k, _)| prefix.matches(k));
412            collect(range, entry_mapper)
413        }
414    }
415
416    /// Looks up unambiguous key with the given prefix.
417    pub fn resolve_prefix_to_key<S>(&self, source: S, prefix: &HexPrefix) -> PrefixResolution<K>
418    where
419        S: IdIndexSource<P>,
420        S::Entry: IdIndexSourceEntry<K>,
421    {
422        self.resolve_prefix_with(source, prefix, |_| ())
423            .map(|(key, ())| key)
424    }
425
426    /// Looks up entry for the key. Returns accessor to neighbors.
427    pub fn lookup_exact<'i, 'q, S>(
428        &'i self,
429        source: S,
430        key: &'q K,
431    ) -> Option<IdIndexLookup<'i, 'q, K, P, S, N>>
432    where
433        S: IdIndexSource<P>,
434        S::Entry: IdIndexSourceEntry<K>,
435    {
436        let lookup = self.lookup_some(source, key);
437        lookup.has_key().then_some(lookup)
438    }
439
440    fn lookup_some<'i, 'q, S>(&'i self, source: S, key: &'q K) -> IdIndexLookup<'i, 'q, K, P, S, N>
441    where
442        S: IdIndexSource<P>,
443    {
444        let short_key = unwrap_as_short_key(key.as_bytes());
445        let index = &self.index;
446        let pos = index.partition_point(|(s, _)| s < short_key);
447        IdIndexLookup {
448            index,
449            source,
450            key,
451            pos,
452        }
453    }
454
455    /// This function returns the shortest length of a prefix of `key` that
456    /// disambiguates it from every other key in the index.
457    ///
458    /// The length to be returned is a number of hexadecimal digits.
459    ///
460    /// This has some properties that we do not currently make much use of:
461    ///
462    /// - The algorithm works even if `key` itself is not in the index.
463    ///
464    /// - In the special case when there are keys in the trie for which our
465    ///   `key` is an exact prefix, returns `key.len() + 1`. Conceptually, in
466    ///   order to disambiguate, you need every letter of the key *and* the
467    ///   additional fact that it's the entire key). This case is extremely
468    ///   unlikely for hashes with 12+ hexadecimal characters.
469    pub fn shortest_unique_prefix_len<S>(&self, source: S, key: &K) -> usize
470    where
471        S: IdIndexSource<P>,
472        S::Entry: IdIndexSourceEntry<K>,
473    {
474        self.lookup_some(source, key).shortest_unique_prefix_len()
475    }
476}
477
478#[derive(Clone, Copy, Debug)]
479pub struct IdIndexLookup<'i, 'q, K, P, S, const N: usize> {
480    index: &'i Vec<([u8; N], P)>,
481    source: S,
482    key: &'q K,
483    pos: usize, // may be index.len()
484}
485
486impl<K, P, S, const N: usize> IdIndexLookup<'_, '_, K, P, S, N>
487where
488    K: ObjectId + Eq,
489    S: IdIndexSource<P>,
490    S::Entry: IdIndexSourceEntry<K>,
491{
492    fn has_key(&self) -> bool {
493        let short_key = unwrap_as_short_key(self.key.as_bytes());
494        self.index[self.pos..]
495            .iter()
496            .take_while(|(s, _)| s == short_key)
497            .any(|(_, p)| self.source.entry_at(p).to_key() == *self.key)
498    }
499
500    pub fn shortest_unique_prefix_len(&self) -> usize {
501        // Since entries having the same short key aren't sorted by the full-length key,
502        // we need to scan all entries in the current chunk, plus left/right neighbors.
503        // Typically, current.len() is 1.
504        let short_key = unwrap_as_short_key(self.key.as_bytes());
505        let left = self.pos.checked_sub(1).map(|p| &self.index[p]);
506        let (current, right) = {
507            let range = &self.index[self.pos..];
508            let count = range.iter().take_while(|(s, _)| s == short_key).count();
509            (&range[..count], range.get(count))
510        };
511
512        // Left/right neighbors should have unique short keys. For the current chunk,
513        // we need to look up full-length keys.
514        let unique_len = |a: &[u8], b: &[u8]| hex_util::common_hex_len(a, b) + 1;
515        let neighbor_lens = left
516            .iter()
517            .chain(&right)
518            .map(|(s, _)| unique_len(s, short_key));
519        let current_lens = current
520            .iter()
521            .map(|(_, p)| self.source.entry_at(p).to_key())
522            .filter(|key| key != self.key)
523            .map(|key| unique_len(key.as_bytes(), self.key.as_bytes()));
524        // Even if the key is the only one in the index, we require at least one digit.
525        neighbor_lens.chain(current_lens).max().unwrap_or(1)
526    }
527}
528
529fn unwrap_as_short_key<const N: usize>(key_bytes: &[u8]) -> &[u8; N] {
530    let short_slice = key_bytes.get(..N).expect("key too short");
531    short_slice.try_into().unwrap()
532}
533
534#[cfg(test)]
535mod tests {
536    use super::*;
537
538    #[derive(Clone, Copy, Eq, PartialEq)]
539    struct Position(usize);
540
541    impl<'a, V> IdIndexSource<Position> for &'a [(ChangeId, V)] {
542        type Entry = &'a (ChangeId, V);
543
544        fn entry_at(&self, pointer: &Position) -> Self::Entry {
545            &self[pointer.0]
546        }
547    }
548
549    impl<V> IdIndexSourceEntry<ChangeId> for &'_ (ChangeId, V) {
550        fn to_key(&self) -> ChangeId {
551            let (change_id, _) = self;
552            change_id.clone()
553        }
554    }
555
556    fn build_id_index<V, const N: usize>(
557        entries: &[(ChangeId, V)],
558    ) -> IdIndex<ChangeId, Position, N> {
559        let mut builder = IdIndex::with_capacity(entries.len());
560        for (i, (k, _)) in entries.iter().enumerate() {
561            builder.insert(k, Position(i));
562        }
563        builder.build()
564    }
565
566    #[test]
567    fn test_id_index_resolve_prefix() {
568        let source = vec![
569            (ChangeId::from_hex("0000"), 0),
570            (ChangeId::from_hex("0099"), 1),
571            (ChangeId::from_hex("0099"), 2),
572            (ChangeId::from_hex("0aaa"), 3),
573            (ChangeId::from_hex("0aab"), 4),
574        ];
575
576        // short_key.len() == full_key.len()
577        let id_index = build_id_index::<_, 2>(&source);
578        let resolve_prefix = |prefix: &HexPrefix| {
579            let resolution: PrefixResolution<(_, Vec<_>)> =
580                id_index.resolve_prefix_with(&*source, prefix, |(_, v)| *v);
581            resolution.map(|(key, mut values)| {
582                values.sort(); // order of values might not be preserved by IdIndex
583                (key, values)
584            })
585        };
586        assert_eq!(
587            resolve_prefix(&HexPrefix::try_from_hex("0").unwrap()),
588            PrefixResolution::AmbiguousMatch,
589        );
590        assert_eq!(
591            resolve_prefix(&HexPrefix::try_from_hex("00").unwrap()),
592            PrefixResolution::AmbiguousMatch,
593        );
594        assert_eq!(
595            resolve_prefix(&HexPrefix::try_from_hex("000").unwrap()),
596            PrefixResolution::SingleMatch((ChangeId::from_hex("0000"), vec![0])),
597        );
598        assert_eq!(
599            resolve_prefix(&HexPrefix::try_from_hex("0001").unwrap()),
600            PrefixResolution::NoMatch,
601        );
602        assert_eq!(
603            resolve_prefix(&HexPrefix::try_from_hex("009").unwrap()),
604            PrefixResolution::SingleMatch((ChangeId::from_hex("0099"), vec![1, 2])),
605        );
606        assert_eq!(
607            resolve_prefix(&HexPrefix::try_from_hex("0aa").unwrap()),
608            PrefixResolution::AmbiguousMatch,
609        );
610        assert_eq!(
611            resolve_prefix(&HexPrefix::try_from_hex("0aab").unwrap()),
612            PrefixResolution::SingleMatch((ChangeId::from_hex("0aab"), vec![4])),
613        );
614        assert_eq!(
615            resolve_prefix(&HexPrefix::try_from_hex("f").unwrap()),
616            PrefixResolution::NoMatch,
617        );
618
619        // short_key.len() < full_key.len()
620        let id_index = build_id_index::<_, 1>(&source);
621        let resolve_prefix = |prefix: &HexPrefix| {
622            let resolution: PrefixResolution<(_, Vec<_>)> =
623                id_index.resolve_prefix_with(&*source, prefix, |(_, v)| *v);
624            resolution.map(|(key, mut values)| {
625                values.sort(); // order of values might not be preserved by IdIndex
626                (key, values)
627            })
628        };
629        assert_eq!(
630            resolve_prefix(&HexPrefix::try_from_hex("00").unwrap()),
631            PrefixResolution::AmbiguousMatch,
632        );
633        assert_eq!(
634            resolve_prefix(&HexPrefix::try_from_hex("000").unwrap()),
635            PrefixResolution::SingleMatch((ChangeId::from_hex("0000"), vec![0])),
636        );
637        assert_eq!(
638            resolve_prefix(&HexPrefix::try_from_hex("0001").unwrap()),
639            PrefixResolution::NoMatch,
640        );
641        // For short key "00", ["0000", "0099", "0099"] would match. We shouldn't
642        // break at "009".matches("0000").
643        assert_eq!(
644            resolve_prefix(&HexPrefix::try_from_hex("009").unwrap()),
645            PrefixResolution::SingleMatch((ChangeId::from_hex("0099"), vec![1, 2])),
646        );
647        assert_eq!(
648            resolve_prefix(&HexPrefix::try_from_hex("0a").unwrap()),
649            PrefixResolution::AmbiguousMatch,
650        );
651        assert_eq!(
652            resolve_prefix(&HexPrefix::try_from_hex("0aa").unwrap()),
653            PrefixResolution::AmbiguousMatch,
654        );
655        assert_eq!(
656            resolve_prefix(&HexPrefix::try_from_hex("0aab").unwrap()),
657            PrefixResolution::SingleMatch((ChangeId::from_hex("0aab"), vec![4])),
658        );
659    }
660
661    #[test]
662    fn test_lookup_exact() {
663        // No crash if empty
664        let source: Vec<(ChangeId, ())> = vec![];
665        let id_index = build_id_index::<_, 1>(&source);
666        assert!(
667            id_index
668                .lookup_exact(&*source, &ChangeId::from_hex("00"))
669                .is_none()
670        );
671
672        let source = vec![
673            (ChangeId::from_hex("ab00"), ()),
674            (ChangeId::from_hex("ab01"), ()),
675        ];
676        let id_index = build_id_index::<_, 1>(&source);
677        assert!(
678            id_index
679                .lookup_exact(&*source, &ChangeId::from_hex("aa00"))
680                .is_none()
681        );
682        assert!(
683            id_index
684                .lookup_exact(&*source, &ChangeId::from_hex("ab00"))
685                .is_some()
686        );
687        assert!(
688            id_index
689                .lookup_exact(&*source, &ChangeId::from_hex("ab01"))
690                .is_some()
691        );
692        assert!(
693            id_index
694                .lookup_exact(&*source, &ChangeId::from_hex("ab02"))
695                .is_none()
696        );
697        assert!(
698            id_index
699                .lookup_exact(&*source, &ChangeId::from_hex("ac00"))
700                .is_none()
701        );
702    }
703
704    #[test]
705    fn test_id_index_shortest_unique_prefix_len() {
706        // No crash if empty
707        let source: Vec<(ChangeId, ())> = vec![];
708        let id_index = build_id_index::<_, 1>(&source);
709        assert_eq!(
710            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("00")),
711            1
712        );
713
714        let source = vec![
715            (ChangeId::from_hex("ab"), ()),
716            (ChangeId::from_hex("acd0"), ()),
717            (ChangeId::from_hex("acd0"), ()), // duplicated key is allowed
718        ];
719        let id_index = build_id_index::<_, 1>(&source);
720        assert_eq!(
721            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("acd0")),
722            2
723        );
724        assert_eq!(
725            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ac")),
726            3
727        );
728
729        let source = vec![
730            (ChangeId::from_hex("ab"), ()),
731            (ChangeId::from_hex("acd0"), ()),
732            (ChangeId::from_hex("acf0"), ()),
733            (ChangeId::from_hex("a0"), ()),
734            (ChangeId::from_hex("ba"), ()),
735        ];
736        let id_index = build_id_index::<_, 1>(&source);
737
738        assert_eq!(
739            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("a0")),
740            2
741        );
742        assert_eq!(
743            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ba")),
744            1
745        );
746        assert_eq!(
747            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ab")),
748            2
749        );
750        assert_eq!(
751            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("acd0")),
752            3
753        );
754        // If it were there, the length would be 1.
755        assert_eq!(
756            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("c0")),
757            1
758        );
759
760        let source = vec![
761            (ChangeId::from_hex("000000"), ()),
762            (ChangeId::from_hex("01ffff"), ()),
763            (ChangeId::from_hex("010000"), ()),
764            (ChangeId::from_hex("01fffe"), ()),
765            (ChangeId::from_hex("ffffff"), ()),
766        ];
767        let id_index = build_id_index::<_, 1>(&source);
768        // Multiple candidates in the current chunk "01"
769        assert_eq!(
770            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("01ffff")),
771            6
772        );
773        assert_eq!(
774            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("010000")),
775            3
776        );
777        assert_eq!(
778            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("01fffe")),
779            6
780        );
781        // Only right neighbor
782        assert_eq!(
783            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("000000")),
784            2
785        );
786        // Only left neighbor
787        assert_eq!(
788            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ffffff")),
789            1
790        );
791    }
792}
jj_lib/id_prefix.rs

jj_lib/
id_prefix.rs
