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

jj_lib/
id_prefix.rs
