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#![allow(missing_docs)]
16
17use std::iter;
18use std::marker::PhantomData;
19use std::rc::Rc;
20use std::sync::Arc;
21
22use itertools::Itertools as _;
23use once_cell::unsync::OnceCell;
24use thiserror::Error;
25
26use crate::backend::ChangeId;
27use crate::backend::CommitId;
28use crate::hex_util;
29use crate::object_id::HexPrefix;
30use crate::object_id::ObjectId;
31use crate::object_id::PrefixResolution;
32use crate::repo::Repo;
33use crate::revset::DefaultSymbolResolver;
34use crate::revset::RevsetEvaluationError;
35use crate::revset::RevsetExtensions;
36use crate::revset::RevsetResolutionError;
37use crate::revset::SymbolResolverExtension;
38use crate::revset::UserRevsetExpression;
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: Rc<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: &[impl AsRef<dyn SymbolResolverExtension>],
64    ) -> Result<&Indexes, IdPrefixIndexLoadError> {
65        self.indexes.get_or_try_init(|| {
66            let symbol_resolver = DefaultSymbolResolver::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: Rc<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            if let PrefixResolution::SingleMatch(id) = resolution {
168                // The disambiguation set may be loaded from a different repo,
169                // and contain a commit that doesn't exist in the current repo.
170                if repo.index().has_id(&id) {
171                    return PrefixResolution::SingleMatch(id);
172                } else {
173                    return PrefixResolution::NoMatch;
174                }
175            }
176        }
177        repo.index().resolve_commit_id_prefix(prefix)
178    }
179
180    /// Returns the shortest length of a prefix of `commit_id` that
181    /// can still be resolved by `resolve_commit_prefix()`.
182    pub fn shortest_commit_prefix_len(&self, repo: &dyn Repo, commit_id: &CommitId) -> usize {
183        if let Some(indexes) = self.indexes {
184            if let Some(lookup) = indexes
185                .commit_index
186                .lookup_exact(&*indexes.commit_change_ids, commit_id)
187            {
188                return lookup.shortest_unique_prefix_len();
189            }
190        }
191        repo.index().shortest_unique_commit_id_prefix_len(commit_id)
192    }
193
194    /// Resolve an unambiguous change ID prefix to the commit IDs in the revset.
195    pub fn resolve_change_prefix(
196        &self,
197        repo: &dyn Repo,
198        prefix: &HexPrefix,
199    ) -> PrefixResolution<Vec<CommitId>> {
200        if let Some(indexes) = self.indexes {
201            let resolution = indexes
202                .change_index
203                .resolve_prefix_to_key(&*indexes.commit_change_ids, prefix);
204            if let PrefixResolution::SingleMatch(change_id) = resolution {
205                return match repo.resolve_change_id(&change_id) {
206                    // There may be more commits with this change id outside the narrower sets.
207                    Some(commit_ids) => PrefixResolution::SingleMatch(commit_ids),
208                    // The disambiguation set may contain hidden commits.
209                    None => PrefixResolution::NoMatch,
210                };
211            }
212        }
213        repo.resolve_change_id_prefix(prefix)
214    }
215
216    /// Returns the shortest length of a prefix of `change_id` that
217    /// can still be resolved by `resolve_change_prefix()`.
218    pub fn shortest_change_prefix_len(&self, repo: &dyn Repo, change_id: &ChangeId) -> usize {
219        if let Some(indexes) = self.indexes {
220            if let Some(lookup) = indexes
221                .change_index
222                .lookup_exact(&*indexes.commit_change_ids, change_id)
223            {
224                return lookup.shortest_unique_prefix_len();
225            }
226        }
227        repo.shortest_unique_change_id_prefix_len(change_id)
228    }
229}
230
231/// In-memory immutable index to do prefix lookup of key `K` through `P`.
232///
233/// In a nutshell, this is a mapping of `K` -> `P` -> `S::Entry` where `S:
234/// IdIndexSource<P>`. The source table `S` isn't owned by this index.
235///
236/// This index stores first `N` bytes of each key `K` associated with the
237/// pointer `P`. `K` may be a heap-allocated object. `P` is supposed to be
238/// a cheap value type like `u32` or `usize`. As the index entry of type
239/// `([u8; N], P)` is small and has no indirect reference, constructing
240/// the index should be faster than sorting the source `(K, _)` pairs.
241///
242/// A key `K` must be at least `N` bytes long.
243#[derive(Clone, Debug)]
244pub struct IdIndex<K, P, const N: usize> {
245    // Maybe better to build separate (keys, values) vectors, but there's no std function
246    // to co-sort them.
247    index: Vec<([u8; N], P)>,
248    // Let's pretend [u8; N] above were of type K. It helps type inference, and ensures that
249    // IdIndexSource has the same key type.
250    phantom_key: PhantomData<K>,
251}
252
253/// Source table for `IdIndex` to map pointer of type `P` to entry.
254pub trait IdIndexSource<P> {
255    type Entry;
256
257    fn entry_at(&self, pointer: &P) -> Self::Entry;
258}
259
260/// Source table entry of `IdIndex`, which is conceptually a `(key, value)`
261/// pair.
262pub trait IdIndexSourceEntry<K> {
263    fn to_key(&self) -> K;
264}
265
266#[derive(Clone, Debug)]
267pub struct IdIndexBuilder<K, P, const N: usize> {
268    unsorted_index: Vec<([u8; N], P)>,
269    phantom_key: PhantomData<K>,
270}
271
272impl<K, P, const N: usize> IdIndexBuilder<K, P, N>
273where
274    K: ObjectId + Ord,
275{
276    /// Inserts new entry. Multiple values can be associated with a single key.
277    pub fn insert(&mut self, key: &K, pointer: P) {
278        let short_key = unwrap_as_short_key(key.as_bytes());
279        self.unsorted_index.push((*short_key, pointer));
280    }
281
282    pub fn build(self) -> IdIndex<K, P, N> {
283        let mut index = self.unsorted_index;
284        index.sort_unstable_by_key(|(s, _)| *s);
285        let phantom_key = self.phantom_key;
286        IdIndex { index, phantom_key }
287    }
288}
289
290impl<K, P, const N: usize> IdIndex<K, P, N>
291where
292    K: ObjectId + Ord,
293{
294    pub fn builder() -> IdIndexBuilder<K, P, N> {
295        IdIndexBuilder {
296            unsorted_index: Vec::new(),
297            phantom_key: PhantomData,
298        }
299    }
300
301    pub fn with_capacity(capacity: usize) -> IdIndexBuilder<K, P, N> {
302        IdIndexBuilder {
303            unsorted_index: Vec::with_capacity(capacity),
304            phantom_key: PhantomData,
305        }
306    }
307
308    /// Looks up entries with the given prefix, and collects values if matched
309    /// entries have unambiguous keys.
310    pub fn resolve_prefix_with<B, S, U>(
311        &self,
312        source: S,
313        prefix: &HexPrefix,
314        entry_mapper: impl FnMut(S::Entry) -> U,
315    ) -> PrefixResolution<(K, B)>
316    where
317        B: FromIterator<U>,
318        S: IdIndexSource<P>,
319        S::Entry: IdIndexSourceEntry<K>,
320    {
321        fn collect<B, K, E, U>(
322            mut range: impl Iterator<Item = (K, E)>,
323            mut entry_mapper: impl FnMut(E) -> U,
324        ) -> PrefixResolution<(K, B)>
325        where
326            B: FromIterator<U>,
327            K: Eq,
328        {
329            if let Some((first_key, first_entry)) = range.next() {
330                let maybe_values: Option<B> = iter::once(Some(entry_mapper(first_entry)))
331                    .chain(range.map(|(k, e)| (k == first_key).then(|| entry_mapper(e))))
332                    .collect();
333                if let Some(values) = maybe_values {
334                    PrefixResolution::SingleMatch((first_key, values))
335                } else {
336                    PrefixResolution::AmbiguousMatch
337                }
338            } else {
339                PrefixResolution::NoMatch
340            }
341        }
342
343        let min_bytes = prefix.min_prefix_bytes();
344        if min_bytes.is_empty() {
345            // We consider an empty prefix ambiguous even if the index has a single entry.
346            return PrefixResolution::AmbiguousMatch;
347        }
348
349        let to_key_entry_pair = |(_, pointer): &(_, P)| -> (K, S::Entry) {
350            let entry = source.entry_at(pointer);
351            (entry.to_key(), entry)
352        };
353        if min_bytes.len() > N {
354            // If the min prefix (including odd byte) is longer than the stored short keys,
355            // we are sure that min_bytes[..N] does not include the odd byte. Use it to
356            // take contiguous range, then filter by (longer) prefix.matches().
357            let short_bytes = unwrap_as_short_key(min_bytes);
358            let pos = self.index.partition_point(|(s, _)| s < short_bytes);
359            let range = self.index[pos..]
360                .iter()
361                .take_while(|(s, _)| s == short_bytes)
362                .map(to_key_entry_pair)
363                .filter(|(k, _)| prefix.matches(k));
364            collect(range, entry_mapper)
365        } else {
366            // Otherwise, use prefix.matches() to deal with odd byte. Since the prefix is
367            // covered by short key width, we're sure that the matching prefixes are sorted.
368            let pos = self.index.partition_point(|(s, _)| &s[..] < min_bytes);
369            let range = self.index[pos..]
370                .iter()
371                .map(to_key_entry_pair)
372                .take_while(|(k, _)| prefix.matches(k));
373            collect(range, entry_mapper)
374        }
375    }
376
377    /// Looks up unambiguous key with the given prefix.
378    pub fn resolve_prefix_to_key<S>(&self, source: S, prefix: &HexPrefix) -> PrefixResolution<K>
379    where
380        S: IdIndexSource<P>,
381        S::Entry: IdIndexSourceEntry<K>,
382    {
383        self.resolve_prefix_with(source, prefix, |_| ())
384            .map(|(key, ())| key)
385    }
386
387    /// Looks up entry for the key. Returns accessor to neighbors.
388    pub fn lookup_exact<'i, 'q, S>(
389        &'i self,
390        source: S,
391        key: &'q K,
392    ) -> Option<IdIndexLookup<'i, 'q, K, P, S, N>>
393    where
394        S: IdIndexSource<P>,
395        S::Entry: IdIndexSourceEntry<K>,
396    {
397        let lookup = self.lookup_some(source, key);
398        lookup.has_key().then_some(lookup)
399    }
400
401    fn lookup_some<'i, 'q, S>(&'i self, source: S, key: &'q K) -> IdIndexLookup<'i, 'q, K, P, S, N>
402    where
403        S: IdIndexSource<P>,
404    {
405        let short_key = unwrap_as_short_key(key.as_bytes());
406        let index = &self.index;
407        let pos = index.partition_point(|(s, _)| s < short_key);
408        IdIndexLookup {
409            index,
410            source,
411            key,
412            pos,
413        }
414    }
415
416    /// This function returns the shortest length of a prefix of `key` that
417    /// disambiguates it from every other key in the index.
418    ///
419    /// The length to be returned is a number of hexadecimal digits.
420    ///
421    /// This has some properties that we do not currently make much use of:
422    ///
423    /// - The algorithm works even if `key` itself is not in the index.
424    ///
425    /// - In the special case when there are keys in the trie for which our
426    ///   `key` is an exact prefix, returns `key.len() + 1`. Conceptually, in
427    ///   order to disambiguate, you need every letter of the key *and* the
428    ///   additional fact that it's the entire key). This case is extremely
429    ///   unlikely for hashes with 12+ hexadecimal characters.
430    pub fn shortest_unique_prefix_len<S>(&self, source: S, key: &K) -> usize
431    where
432        S: IdIndexSource<P>,
433        S::Entry: IdIndexSourceEntry<K>,
434    {
435        self.lookup_some(source, key).shortest_unique_prefix_len()
436    }
437}
438
439#[derive(Clone, Copy, Debug)]
440pub struct IdIndexLookup<'i, 'q, K, P, S, const N: usize> {
441    index: &'i Vec<([u8; N], P)>,
442    source: S,
443    key: &'q K,
444    pos: usize, // may be index.len()
445}
446
447impl<K, P, S, const N: usize> IdIndexLookup<'_, '_, K, P, S, N>
448where
449    K: ObjectId + Eq,
450    S: IdIndexSource<P>,
451    S::Entry: IdIndexSourceEntry<K>,
452{
453    fn has_key(&self) -> bool {
454        let short_key = unwrap_as_short_key(self.key.as_bytes());
455        self.index[self.pos..]
456            .iter()
457            .take_while(|(s, _)| s == short_key)
458            .any(|(_, p)| self.source.entry_at(p).to_key() == *self.key)
459    }
460
461    pub fn shortest_unique_prefix_len(&self) -> usize {
462        // Since entries having the same short key aren't sorted by the full-length key,
463        // we need to scan all entries in the current chunk, plus left/right neighbors.
464        // Typically, current.len() is 1.
465        let short_key = unwrap_as_short_key(self.key.as_bytes());
466        let left = self.pos.checked_sub(1).map(|p| &self.index[p]);
467        let (current, right) = {
468            let range = &self.index[self.pos..];
469            let count = range.iter().take_while(|(s, _)| s == short_key).count();
470            (&range[..count], range.get(count))
471        };
472
473        // Left/right neighbors should have unique short keys. For the current chunk,
474        // we need to look up full-length keys.
475        let unique_len = |a: &[u8], b: &[u8]| hex_util::common_hex_len(a, b) + 1;
476        let neighbor_lens = left
477            .iter()
478            .chain(&right)
479            .map(|(s, _)| unique_len(s, short_key));
480        let current_lens = current
481            .iter()
482            .map(|(_, p)| self.source.entry_at(p).to_key())
483            .filter(|key| key != self.key)
484            .map(|key| unique_len(key.as_bytes(), self.key.as_bytes()));
485        // Even if the key is the only one in the index, we require at least one digit.
486        neighbor_lens.chain(current_lens).max().unwrap_or(1)
487    }
488}
489
490fn unwrap_as_short_key<const N: usize>(key_bytes: &[u8]) -> &[u8; N] {
491    let short_slice = key_bytes.get(..N).expect("key too short");
492    short_slice.try_into().unwrap()
493}
494
495#[cfg(test)]
496mod tests {
497    use super::*;
498
499    #[derive(Clone, Copy, Eq, PartialEq)]
500    struct Position(usize);
501
502    impl<'a, V> IdIndexSource<Position> for &'a [(ChangeId, V)] {
503        type Entry = &'a (ChangeId, V);
504
505        fn entry_at(&self, pointer: &Position) -> Self::Entry {
506            &self[pointer.0]
507        }
508    }
509
510    impl<V> IdIndexSourceEntry<ChangeId> for &'_ (ChangeId, V) {
511        fn to_key(&self) -> ChangeId {
512            let (change_id, _) = self;
513            change_id.clone()
514        }
515    }
516
517    fn build_id_index<V, const N: usize>(
518        entries: &[(ChangeId, V)],
519    ) -> IdIndex<ChangeId, Position, N> {
520        let mut builder = IdIndex::with_capacity(entries.len());
521        for (i, (k, _)) in entries.iter().enumerate() {
522            builder.insert(k, Position(i));
523        }
524        builder.build()
525    }
526
527    #[test]
528    fn test_id_index_resolve_prefix() {
529        let source = vec![
530            (ChangeId::from_hex("0000"), 0),
531            (ChangeId::from_hex("0099"), 1),
532            (ChangeId::from_hex("0099"), 2),
533            (ChangeId::from_hex("0aaa"), 3),
534            (ChangeId::from_hex("0aab"), 4),
535        ];
536
537        // short_key.len() == full_key.len()
538        let id_index = build_id_index::<_, 2>(&source);
539        let resolve_prefix = |prefix: &HexPrefix| {
540            let resolution: PrefixResolution<(_, Vec<_>)> =
541                id_index.resolve_prefix_with(&*source, prefix, |(_, v)| *v);
542            resolution.map(|(key, mut values)| {
543                values.sort(); // order of values might not be preserved by IdIndex
544                (key, values)
545            })
546        };
547        assert_eq!(
548            resolve_prefix(&HexPrefix::new("0").unwrap()),
549            PrefixResolution::AmbiguousMatch,
550        );
551        assert_eq!(
552            resolve_prefix(&HexPrefix::new("00").unwrap()),
553            PrefixResolution::AmbiguousMatch,
554        );
555        assert_eq!(
556            resolve_prefix(&HexPrefix::new("000").unwrap()),
557            PrefixResolution::SingleMatch((ChangeId::from_hex("0000"), vec![0])),
558        );
559        assert_eq!(
560            resolve_prefix(&HexPrefix::new("0001").unwrap()),
561            PrefixResolution::NoMatch,
562        );
563        assert_eq!(
564            resolve_prefix(&HexPrefix::new("009").unwrap()),
565            PrefixResolution::SingleMatch((ChangeId::from_hex("0099"), vec![1, 2])),
566        );
567        assert_eq!(
568            resolve_prefix(&HexPrefix::new("0aa").unwrap()),
569            PrefixResolution::AmbiguousMatch,
570        );
571        assert_eq!(
572            resolve_prefix(&HexPrefix::new("0aab").unwrap()),
573            PrefixResolution::SingleMatch((ChangeId::from_hex("0aab"), vec![4])),
574        );
575        assert_eq!(
576            resolve_prefix(&HexPrefix::new("f").unwrap()),
577            PrefixResolution::NoMatch,
578        );
579
580        // short_key.len() < full_key.len()
581        let id_index = build_id_index::<_, 1>(&source);
582        let resolve_prefix = |prefix: &HexPrefix| {
583            let resolution: PrefixResolution<(_, Vec<_>)> =
584                id_index.resolve_prefix_with(&*source, prefix, |(_, v)| *v);
585            resolution.map(|(key, mut values)| {
586                values.sort(); // order of values might not be preserved by IdIndex
587                (key, values)
588            })
589        };
590        assert_eq!(
591            resolve_prefix(&HexPrefix::new("00").unwrap()),
592            PrefixResolution::AmbiguousMatch,
593        );
594        assert_eq!(
595            resolve_prefix(&HexPrefix::new("000").unwrap()),
596            PrefixResolution::SingleMatch((ChangeId::from_hex("0000"), vec![0])),
597        );
598        assert_eq!(
599            resolve_prefix(&HexPrefix::new("0001").unwrap()),
600            PrefixResolution::NoMatch,
601        );
602        // For short key "00", ["0000", "0099", "0099"] would match. We shouldn't
603        // break at "009".matches("0000").
604        assert_eq!(
605            resolve_prefix(&HexPrefix::new("009").unwrap()),
606            PrefixResolution::SingleMatch((ChangeId::from_hex("0099"), vec![1, 2])),
607        );
608        assert_eq!(
609            resolve_prefix(&HexPrefix::new("0a").unwrap()),
610            PrefixResolution::AmbiguousMatch,
611        );
612        assert_eq!(
613            resolve_prefix(&HexPrefix::new("0aa").unwrap()),
614            PrefixResolution::AmbiguousMatch,
615        );
616        assert_eq!(
617            resolve_prefix(&HexPrefix::new("0aab").unwrap()),
618            PrefixResolution::SingleMatch((ChangeId::from_hex("0aab"), vec![4])),
619        );
620    }
621
622    #[test]
623    fn test_lookup_exact() {
624        // No crash if empty
625        let source: Vec<(ChangeId, ())> = vec![];
626        let id_index = build_id_index::<_, 1>(&source);
627        assert!(id_index
628            .lookup_exact(&*source, &ChangeId::from_hex("00"))
629            .is_none());
630
631        let source = vec![
632            (ChangeId::from_hex("ab00"), ()),
633            (ChangeId::from_hex("ab01"), ()),
634        ];
635        let id_index = build_id_index::<_, 1>(&source);
636        assert!(id_index
637            .lookup_exact(&*source, &ChangeId::from_hex("aa00"))
638            .is_none());
639        assert!(id_index
640            .lookup_exact(&*source, &ChangeId::from_hex("ab00"))
641            .is_some());
642        assert!(id_index
643            .lookup_exact(&*source, &ChangeId::from_hex("ab01"))
644            .is_some());
645        assert!(id_index
646            .lookup_exact(&*source, &ChangeId::from_hex("ab02"))
647            .is_none());
648        assert!(id_index
649            .lookup_exact(&*source, &ChangeId::from_hex("ac00"))
650            .is_none());
651    }
652
653    #[test]
654    fn test_id_index_shortest_unique_prefix_len() {
655        // No crash if empty
656        let source: Vec<(ChangeId, ())> = vec![];
657        let id_index = build_id_index::<_, 1>(&source);
658        assert_eq!(
659            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("00")),
660            1
661        );
662
663        let source = vec![
664            (ChangeId::from_hex("ab"), ()),
665            (ChangeId::from_hex("acd0"), ()),
666            (ChangeId::from_hex("acd0"), ()), // duplicated key is allowed
667        ];
668        let id_index = build_id_index::<_, 1>(&source);
669        assert_eq!(
670            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("acd0")),
671            2
672        );
673        assert_eq!(
674            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ac")),
675            3
676        );
677
678        let source = vec![
679            (ChangeId::from_hex("ab"), ()),
680            (ChangeId::from_hex("acd0"), ()),
681            (ChangeId::from_hex("acf0"), ()),
682            (ChangeId::from_hex("a0"), ()),
683            (ChangeId::from_hex("ba"), ()),
684        ];
685        let id_index = build_id_index::<_, 1>(&source);
686
687        assert_eq!(
688            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("a0")),
689            2
690        );
691        assert_eq!(
692            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ba")),
693            1
694        );
695        assert_eq!(
696            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ab")),
697            2
698        );
699        assert_eq!(
700            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("acd0")),
701            3
702        );
703        // If it were there, the length would be 1.
704        assert_eq!(
705            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("c0")),
706            1
707        );
708
709        let source = vec![
710            (ChangeId::from_hex("000000"), ()),
711            (ChangeId::from_hex("01ffff"), ()),
712            (ChangeId::from_hex("010000"), ()),
713            (ChangeId::from_hex("01fffe"), ()),
714            (ChangeId::from_hex("ffffff"), ()),
715        ];
716        let id_index = build_id_index::<_, 1>(&source);
717        // Multiple candidates in the current chunk "01"
718        assert_eq!(
719            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("01ffff")),
720            6
721        );
722        assert_eq!(
723            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("010000")),
724            3
725        );
726        assert_eq!(
727            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("01fffe")),
728            6
729        );
730        // Only right neighbor
731        assert_eq!(
732            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("000000")),
733            2
734        );
735        // Only left neighbor
736        assert_eq!(
737            id_index.shortest_unique_prefix_len(&*source, &ChangeId::from_hex("ffffff")),
738            1
739        );
740    }
741}
jj_lib/id_prefix.rs

jj_lib/
id_prefix.rs
