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

jj_lib/
id_prefix.rs
