jj_lib/default_index/
mod.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//! An on-disk index of the commits in a repository.
16//!
17//! Implements an index of the commits in a repository that conforms to the
18//! trains in the [index module](crate::index). The index is stored on local
19//! disk and contains an entry for every commit in the repository. See
20//! [`DefaultReadonlyIndex`] and [`DefaultMutableIndex`].
21
22#![allow(missing_docs)]
23
24mod composite;
25mod entry;
26mod mutable;
27mod readonly;
28mod rev_walk;
29pub mod revset_engine;
30mod revset_graph_iterator;
31mod store;
32
33pub use self::composite::AsCompositeIndex;
34pub use self::composite::CompositeIndex;
35pub use self::composite::IndexLevelStats;
36pub use self::composite::IndexStats;
37pub use self::entry::IndexEntry;
38pub use self::entry::IndexPosition;
39pub use self::mutable::DefaultMutableIndex;
40pub use self::readonly::DefaultReadonlyIndex;
41pub use self::readonly::ReadonlyIndexLoadError;
42pub use self::store::DefaultIndexStore;
43pub use self::store::DefaultIndexStoreError;
44pub use self::store::DefaultIndexStoreInitError;
45
46#[cfg(test)]
47mod tests {
48    use std::sync::Arc;
49
50    use itertools::Itertools as _;
51    use smallvec::smallvec_inline;
52    use test_case::test_case;
53
54    use super::composite::DynIndexSegment;
55    use super::composite::IndexSegment as _;
56    use super::entry::SmallIndexPositionsVec;
57    use super::mutable::MutableIndexSegment;
58    use super::*;
59    use crate::backend::ChangeId;
60    use crate::backend::CommitId;
61    use crate::default_index::entry::LocalPosition;
62    use crate::default_index::entry::SmallLocalPositionsVec;
63    use crate::index::Index as _;
64    use crate::object_id::HexPrefix;
65    use crate::object_id::ObjectId as _;
66    use crate::object_id::PrefixResolution;
67    use crate::tests::new_temp_dir;
68
69    /// Generator of unique 16-byte CommitId excluding root id
70    fn commit_id_generator() -> impl FnMut() -> CommitId {
71        let mut iter = (1_u128..).map(|n| CommitId::new(n.to_le_bytes().into()));
72        move || iter.next().unwrap()
73    }
74
75    /// Generator of unique 16-byte ChangeId excluding root id
76    fn change_id_generator() -> impl FnMut() -> ChangeId {
77        let mut iter = (1_u128..).map(|n| ChangeId::new(n.to_le_bytes().into()));
78        move || iter.next().unwrap()
79    }
80
81    #[test_case(false; "memory")]
82    #[test_case(true; "file")]
83    fn index_empty(on_disk: bool) {
84        let temp_dir = new_temp_dir();
85        let mutable_segment = MutableIndexSegment::full(3, 16);
86        let index_segment: Box<DynIndexSegment> = if on_disk {
87            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();
88            Box::new(Arc::try_unwrap(saved_index).unwrap())
89        } else {
90            Box::new(mutable_segment)
91        };
92        let index = CompositeIndex::new(index_segment.as_ref());
93
94        // Stats are as expected
95        let stats = index.stats();
96        assert_eq!(stats.num_commits, 0);
97        assert_eq!(stats.num_heads, 0);
98        assert_eq!(stats.max_generation_number, 0);
99        assert_eq!(stats.num_merges, 0);
100        assert_eq!(stats.num_changes, 0);
101        assert_eq!(index.num_commits(), 0);
102        // Cannot find any commits
103        assert!(index.entry_by_id(&CommitId::from_hex("000000")).is_none());
104        assert!(index.entry_by_id(&CommitId::from_hex("aaa111")).is_none());
105        assert!(index.entry_by_id(&CommitId::from_hex("ffffff")).is_none());
106    }
107
108    #[test_case(false; "memory")]
109    #[test_case(true; "file")]
110    fn index_root_commit(on_disk: bool) {
111        let temp_dir = new_temp_dir();
112        let mut new_change_id = change_id_generator();
113        let mut mutable_segment = MutableIndexSegment::full(3, 16);
114        let id_0 = CommitId::from_hex("000000");
115        let change_id0 = new_change_id();
116        mutable_segment.add_commit_data(id_0.clone(), change_id0.clone(), &[]);
117        let index_segment: Box<DynIndexSegment> = if on_disk {
118            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();
119            Box::new(Arc::try_unwrap(saved_index).unwrap())
120        } else {
121            Box::new(mutable_segment)
122        };
123        let index = CompositeIndex::new(index_segment.as_ref());
124
125        // Stats are as expected
126        let stats = index.stats();
127        assert_eq!(stats.num_commits, 1);
128        assert_eq!(stats.num_heads, 1);
129        assert_eq!(stats.max_generation_number, 0);
130        assert_eq!(stats.num_merges, 0);
131        assert_eq!(stats.num_changes, 1);
132        assert_eq!(index.num_commits(), 1);
133        // Can find only the root commit
134        assert_eq!(index.commit_id_to_pos(&id_0), Some(IndexPosition(0)));
135        assert_eq!(index.commit_id_to_pos(&CommitId::from_hex("aaaaaa")), None);
136        assert_eq!(index.commit_id_to_pos(&CommitId::from_hex("ffffff")), None);
137        // Check properties of root entry
138        let entry = index.entry_by_id(&id_0).unwrap();
139        assert_eq!(entry.position(), IndexPosition(0));
140        assert_eq!(entry.commit_id(), id_0);
141        assert_eq!(entry.change_id(), change_id0);
142        assert_eq!(entry.generation_number(), 0);
143        assert_eq!(entry.num_parents(), 0);
144        assert_eq!(entry.parent_positions(), SmallIndexPositionsVec::new());
145        assert_eq!(entry.parents().len(), 0);
146    }
147
148    #[test]
149    #[should_panic(expected = "parent commit is not indexed")]
150    fn index_missing_parent_commit() {
151        let mut new_change_id = change_id_generator();
152        let mut index = DefaultMutableIndex::full(3, 16);
153        let id_0 = CommitId::from_hex("000000");
154        let id_1 = CommitId::from_hex("111111");
155        index.add_commit_data(id_1, new_change_id(), &[id_0]);
156    }
157
158    #[test_case(false, false; "full in memory")]
159    #[test_case(false, true; "full on disk")]
160    #[test_case(true, false; "incremental in memory")]
161    #[test_case(true, true; "incremental on disk")]
162    fn index_multiple_commits(incremental: bool, on_disk: bool) {
163        let temp_dir = new_temp_dir();
164        let mut new_change_id = change_id_generator();
165        let mut mutable_segment = MutableIndexSegment::full(3, 16);
166        // 5
167        // |\
168        // 4 | 3
169        // | |/
170        // 1 2
171        // |/
172        // 0
173        let id_0 = CommitId::from_hex("000000");
174        let change_id0 = new_change_id();
175        let id_1 = CommitId::from_hex("111111");
176        let change_id1 = new_change_id();
177        let id_2 = CommitId::from_hex("222222");
178        #[expect(clippy::redundant_clone)] // Work around nightly clippy false positive
179        // TODO: Remove the exception after https://github.com/rust-lang/rust-clippy/issues/10577
180        // is fixed or file a new bug.
181        let change_id2 = change_id1.clone();
182        mutable_segment.add_commit_data(id_0.clone(), change_id0, &[]);
183        mutable_segment.add_commit_data(id_1.clone(), change_id1.clone(), &[id_0.clone()]);
184        mutable_segment.add_commit_data(id_2.clone(), change_id2.clone(), &[id_0.clone()]);
185
186        // If testing incremental indexing, write the first three commits to one file
187        // now and build the remainder as another segment on top.
188        if incremental {
189            let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();
190            mutable_segment = MutableIndexSegment::incremental(initial_file);
191        }
192
193        let id_3 = CommitId::from_hex("333333");
194        let change_id3 = new_change_id();
195        let id_4 = CommitId::from_hex("444444");
196        let change_id4 = new_change_id();
197        let id_5 = CommitId::from_hex("555555");
198        let change_id5 = change_id3.clone();
199        mutable_segment.add_commit_data(id_3.clone(), change_id3.clone(), &[id_2.clone()]);
200        mutable_segment.add_commit_data(id_4.clone(), change_id4, &[id_1.clone()]);
201        mutable_segment.add_commit_data(id_5.clone(), change_id5, &[id_4.clone(), id_2.clone()]);
202        let index_segment: Box<DynIndexSegment> = if on_disk {
203            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();
204            Box::new(Arc::try_unwrap(saved_index).unwrap())
205        } else {
206            Box::new(mutable_segment)
207        };
208        let index = CompositeIndex::new(index_segment.as_ref());
209
210        // Stats are as expected
211        let stats = index.stats();
212        assert_eq!(stats.num_commits, 6);
213        assert_eq!(stats.num_heads, 2);
214        assert_eq!(stats.max_generation_number, 3);
215        assert_eq!(stats.num_merges, 1);
216        assert_eq!(stats.num_changes, 4);
217        assert_eq!(index.num_commits(), 6);
218        // Can find all the commits
219        let entry_0 = index.entry_by_id(&id_0).unwrap();
220        let entry_1 = index.entry_by_id(&id_1).unwrap();
221        let entry_2 = index.entry_by_id(&id_2).unwrap();
222        let entry_3 = index.entry_by_id(&id_3).unwrap();
223        let entry_4 = index.entry_by_id(&id_4).unwrap();
224        let entry_5 = index.entry_by_id(&id_5).unwrap();
225        // Check properties of some entries
226        assert_eq!(entry_0.position(), IndexPosition(0));
227        assert_eq!(entry_0.commit_id(), id_0);
228        assert_eq!(entry_1.position(), IndexPosition(1));
229        assert_eq!(entry_1.commit_id(), id_1);
230        assert_eq!(entry_1.change_id(), change_id1);
231        assert_eq!(entry_1.generation_number(), 1);
232        assert_eq!(entry_1.num_parents(), 1);
233        assert_eq!(
234            entry_1.parent_positions(),
235            smallvec_inline![IndexPosition(0)]
236        );
237        assert_eq!(entry_1.parents().len(), 1);
238        assert_eq!(
239            entry_1.parents().next().unwrap().position(),
240            IndexPosition(0)
241        );
242        assert_eq!(entry_2.position(), IndexPosition(2));
243        assert_eq!(entry_2.commit_id(), id_2);
244        assert_eq!(entry_2.change_id(), change_id2);
245        assert_eq!(entry_2.generation_number(), 1);
246        assert_eq!(entry_2.num_parents(), 1);
247        assert_eq!(
248            entry_2.parent_positions(),
249            smallvec_inline![IndexPosition(0)]
250        );
251        assert_eq!(entry_3.change_id(), change_id3);
252        assert_eq!(entry_3.generation_number(), 2);
253        assert_eq!(
254            entry_3.parent_positions(),
255            smallvec_inline![IndexPosition(2)]
256        );
257        assert_eq!(entry_4.position(), IndexPosition(4));
258        assert_eq!(entry_4.generation_number(), 2);
259        assert_eq!(entry_4.num_parents(), 1);
260        assert_eq!(
261            entry_4.parent_positions(),
262            smallvec_inline![IndexPosition(1)]
263        );
264        assert_eq!(entry_5.generation_number(), 3);
265        assert_eq!(entry_5.num_parents(), 2);
266        assert_eq!(
267            entry_5.parent_positions(),
268            smallvec_inline![IndexPosition(4), IndexPosition(2)]
269        );
270        assert_eq!(entry_5.parents().len(), 2);
271        assert_eq!(
272            entry_5.parents().next().unwrap().position(),
273            IndexPosition(4)
274        );
275        assert_eq!(
276            entry_5.parents().nth(1).unwrap().position(),
277            IndexPosition(2)
278        );
279    }
280
281    #[test_case(false; "in memory")]
282    #[test_case(true; "on disk")]
283    fn index_many_parents(on_disk: bool) {
284        let temp_dir = new_temp_dir();
285        let mut new_change_id = change_id_generator();
286        let mut mutable_segment = MutableIndexSegment::full(3, 16);
287        //     6
288        //    /|\
289        //   / | \
290        //  / /|\ \
291        // 1 2 3 4 5
292        //  \ \|/ /
293        //   \ | /
294        //    \|/
295        //     0
296        let id_0 = CommitId::from_hex("000000");
297        let id_1 = CommitId::from_hex("111111");
298        let id_2 = CommitId::from_hex("222222");
299        let id_3 = CommitId::from_hex("333333");
300        let id_4 = CommitId::from_hex("444444");
301        let id_5 = CommitId::from_hex("555555");
302        let id_6 = CommitId::from_hex("666666");
303        mutable_segment.add_commit_data(id_0.clone(), new_change_id(), &[]);
304        mutable_segment.add_commit_data(id_1.clone(), new_change_id(), &[id_0.clone()]);
305        mutable_segment.add_commit_data(id_2.clone(), new_change_id(), &[id_0.clone()]);
306        mutable_segment.add_commit_data(id_3.clone(), new_change_id(), &[id_0.clone()]);
307        mutable_segment.add_commit_data(id_4.clone(), new_change_id(), &[id_0.clone()]);
308        mutable_segment.add_commit_data(id_5.clone(), new_change_id(), &[id_0]);
309        mutable_segment.add_commit_data(
310            id_6.clone(),
311            new_change_id(),
312            &[id_1, id_2, id_3, id_4, id_5],
313        );
314        let index_segment: Box<DynIndexSegment> = if on_disk {
315            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();
316            Box::new(Arc::try_unwrap(saved_index).unwrap())
317        } else {
318            Box::new(mutable_segment)
319        };
320        let index = CompositeIndex::new(index_segment.as_ref());
321
322        // Stats are as expected
323        let stats = index.stats();
324        assert_eq!(stats.num_commits, 7);
325        assert_eq!(stats.num_heads, 1);
326        assert_eq!(stats.max_generation_number, 2);
327        assert_eq!(stats.num_merges, 1);
328
329        // The octopus merge has the right parents
330        let entry_6 = index.entry_by_id(&id_6).unwrap();
331        assert_eq!(entry_6.commit_id(), id_6.clone());
332        assert_eq!(entry_6.num_parents(), 5);
333        assert_eq!(
334            entry_6.parent_positions(),
335            smallvec_inline![
336                IndexPosition(1),
337                IndexPosition(2),
338                IndexPosition(3),
339                IndexPosition(4),
340                IndexPosition(5),
341            ]
342        );
343        assert_eq!(entry_6.generation_number(), 2);
344    }
345
346    #[test]
347    fn resolve_commit_id_prefix() {
348        let temp_dir = new_temp_dir();
349        let mut new_change_id = change_id_generator();
350        let mut mutable_segment = MutableIndexSegment::full(3, 16);
351
352        // Create some commits with different various common prefixes.
353        let id_0 = CommitId::from_hex("000000");
354        let id_1 = CommitId::from_hex("009999");
355        let id_2 = CommitId::from_hex("055488");
356        mutable_segment.add_commit_data(id_0.clone(), new_change_id(), &[]);
357        mutable_segment.add_commit_data(id_1.clone(), new_change_id(), &[]);
358        mutable_segment.add_commit_data(id_2.clone(), new_change_id(), &[]);
359
360        // Write the first three commits to one file and build the remainder on top.
361        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();
362        mutable_segment = MutableIndexSegment::incremental(initial_file);
363
364        let id_3 = CommitId::from_hex("055444");
365        let id_4 = CommitId::from_hex("055555");
366        let id_5 = CommitId::from_hex("033333");
367        mutable_segment.add_commit_data(id_3, new_change_id(), &[]);
368        mutable_segment.add_commit_data(id_4, new_change_id(), &[]);
369        mutable_segment.add_commit_data(id_5, new_change_id(), &[]);
370
371        let index = mutable_segment.as_composite();
372
373        // Can find commits given the full hex number
374        assert_eq!(
375            index.resolve_commit_id_prefix(&HexPrefix::new(&id_0.hex()).unwrap()),
376            PrefixResolution::SingleMatch(id_0)
377        );
378        assert_eq!(
379            index.resolve_commit_id_prefix(&HexPrefix::new(&id_1.hex()).unwrap()),
380            PrefixResolution::SingleMatch(id_1)
381        );
382        assert_eq!(
383            index.resolve_commit_id_prefix(&HexPrefix::new(&id_2.hex()).unwrap()),
384            PrefixResolution::SingleMatch(id_2)
385        );
386        // Test nonexistent commits
387        assert_eq!(
388            index.resolve_commit_id_prefix(&HexPrefix::new("ffffff").unwrap()),
389            PrefixResolution::NoMatch
390        );
391        assert_eq!(
392            index.resolve_commit_id_prefix(&HexPrefix::new("000001").unwrap()),
393            PrefixResolution::NoMatch
394        );
395        // Test ambiguous prefix
396        assert_eq!(
397            index.resolve_commit_id_prefix(&HexPrefix::new("0").unwrap()),
398            PrefixResolution::AmbiguousMatch
399        );
400        // Test a globally unique prefix in initial part
401        assert_eq!(
402            index.resolve_commit_id_prefix(&HexPrefix::new("009").unwrap()),
403            PrefixResolution::SingleMatch(CommitId::from_hex("009999"))
404        );
405        // Test a globally unique prefix in incremental part
406        assert_eq!(
407            index.resolve_commit_id_prefix(&HexPrefix::new("03").unwrap()),
408            PrefixResolution::SingleMatch(CommitId::from_hex("033333"))
409        );
410        // Test a locally unique but globally ambiguous prefix
411        assert_eq!(
412            index.resolve_commit_id_prefix(&HexPrefix::new("0554").unwrap()),
413            PrefixResolution::AmbiguousMatch
414        );
415    }
416
417    #[test]
418    #[expect(clippy::redundant_clone)] // allow id_n.clone()
419    fn neighbor_commit_ids() {
420        let temp_dir = new_temp_dir();
421        let mut new_change_id = change_id_generator();
422        let mut mutable_segment = MutableIndexSegment::full(3, 16);
423
424        // Create some commits with different various common prefixes.
425        let id_0 = CommitId::from_hex("000001");
426        let id_1 = CommitId::from_hex("009999");
427        let id_2 = CommitId::from_hex("055488");
428        mutable_segment.add_commit_data(id_0.clone(), new_change_id(), &[]);
429        mutable_segment.add_commit_data(id_1.clone(), new_change_id(), &[]);
430        mutable_segment.add_commit_data(id_2.clone(), new_change_id(), &[]);
431
432        // Write the first three commits to one file and build the remainder on top.
433        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();
434        mutable_segment = MutableIndexSegment::incremental(initial_file.clone());
435
436        let id_3 = CommitId::from_hex("055444");
437        let id_4 = CommitId::from_hex("055555");
438        let id_5 = CommitId::from_hex("033333");
439        mutable_segment.add_commit_data(id_3.clone(), new_change_id(), &[]);
440        mutable_segment.add_commit_data(id_4.clone(), new_change_id(), &[]);
441        mutable_segment.add_commit_data(id_5.clone(), new_change_id(), &[]);
442
443        // Local lookup in readonly index, commit_id exists.
444        assert_eq!(
445            initial_file.resolve_neighbor_commit_ids(&id_0),
446            (None, Some(id_1.clone())),
447        );
448        assert_eq!(
449            initial_file.resolve_neighbor_commit_ids(&id_1),
450            (Some(id_0.clone()), Some(id_2.clone())),
451        );
452        assert_eq!(
453            initial_file.resolve_neighbor_commit_ids(&id_2),
454            (Some(id_1.clone()), None),
455        );
456
457        // Local lookup in readonly index, commit_id does not exist.
458        assert_eq!(
459            initial_file.resolve_neighbor_commit_ids(&CommitId::from_hex("000000")),
460            (None, Some(id_0.clone())),
461        );
462        assert_eq!(
463            initial_file.resolve_neighbor_commit_ids(&CommitId::from_hex("000002")),
464            (Some(id_0.clone()), Some(id_1.clone())),
465        );
466        assert_eq!(
467            initial_file.resolve_neighbor_commit_ids(&CommitId::from_hex("ffffff")),
468            (Some(id_2.clone()), None),
469        );
470
471        // Local lookup in mutable index, commit_id exists. id_5 < id_3 < id_4
472        assert_eq!(
473            mutable_segment.resolve_neighbor_commit_ids(&id_5),
474            (None, Some(id_3.clone())),
475        );
476        assert_eq!(
477            mutable_segment.resolve_neighbor_commit_ids(&id_3),
478            (Some(id_5.clone()), Some(id_4.clone())),
479        );
480        assert_eq!(
481            mutable_segment.resolve_neighbor_commit_ids(&id_4),
482            (Some(id_3.clone()), None),
483        );
484
485        // Local lookup in mutable index, commit_id does not exist. id_5 < id_3 < id_4
486        assert_eq!(
487            mutable_segment.resolve_neighbor_commit_ids(&CommitId::from_hex("033332")),
488            (None, Some(id_5.clone())),
489        );
490        assert_eq!(
491            mutable_segment.resolve_neighbor_commit_ids(&CommitId::from_hex("033334")),
492            (Some(id_5.clone()), Some(id_3.clone())),
493        );
494        assert_eq!(
495            mutable_segment.resolve_neighbor_commit_ids(&CommitId::from_hex("ffffff")),
496            (Some(id_4.clone()), None),
497        );
498
499        // Global lookup, commit_id exists. id_0 < id_1 < id_5 < id_3 < id_2 < id_4
500        let composite_index = CompositeIndex::new(&mutable_segment);
501        assert_eq!(
502            composite_index.resolve_neighbor_commit_ids(&id_0),
503            (None, Some(id_1.clone())),
504        );
505        assert_eq!(
506            composite_index.resolve_neighbor_commit_ids(&id_1),
507            (Some(id_0.clone()), Some(id_5.clone())),
508        );
509        assert_eq!(
510            composite_index.resolve_neighbor_commit_ids(&id_5),
511            (Some(id_1.clone()), Some(id_3.clone())),
512        );
513        assert_eq!(
514            composite_index.resolve_neighbor_commit_ids(&id_3),
515            (Some(id_5.clone()), Some(id_2.clone())),
516        );
517        assert_eq!(
518            composite_index.resolve_neighbor_commit_ids(&id_2),
519            (Some(id_3.clone()), Some(id_4.clone())),
520        );
521        assert_eq!(
522            composite_index.resolve_neighbor_commit_ids(&id_4),
523            (Some(id_2.clone()), None),
524        );
525
526        // Global lookup, commit_id doesn't exist. id_0 < id_1 < id_5 < id_3 < id_2 <
527        // id_4
528        assert_eq!(
529            composite_index.resolve_neighbor_commit_ids(&CommitId::from_hex("000000")),
530            (None, Some(id_0.clone())),
531        );
532        assert_eq!(
533            composite_index.resolve_neighbor_commit_ids(&CommitId::from_hex("010000")),
534            (Some(id_1.clone()), Some(id_5.clone())),
535        );
536        assert_eq!(
537            composite_index.resolve_neighbor_commit_ids(&CommitId::from_hex("033334")),
538            (Some(id_5.clone()), Some(id_3.clone())),
539        );
540        assert_eq!(
541            composite_index.resolve_neighbor_commit_ids(&CommitId::from_hex("ffffff")),
542            (Some(id_4.clone()), None),
543        );
544    }
545
546    #[test]
547    fn shortest_unique_commit_id_prefix() {
548        let temp_dir = new_temp_dir();
549        let mut new_change_id = change_id_generator();
550        let mut mutable_segment = MutableIndexSegment::full(3, 16);
551
552        // Create some commits with different various common prefixes.
553        let id_0 = CommitId::from_hex("000001");
554        let id_1 = CommitId::from_hex("009999");
555        let id_2 = CommitId::from_hex("055488");
556        mutable_segment.add_commit_data(id_0.clone(), new_change_id(), &[]);
557        mutable_segment.add_commit_data(id_1.clone(), new_change_id(), &[]);
558        mutable_segment.add_commit_data(id_2.clone(), new_change_id(), &[]);
559
560        // Write the first three commits to one file and build the remainder on top.
561        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();
562        mutable_segment = MutableIndexSegment::incremental(initial_file);
563
564        let id_3 = CommitId::from_hex("055444");
565        let id_4 = CommitId::from_hex("055555");
566        let id_5 = CommitId::from_hex("033333");
567        mutable_segment.add_commit_data(id_3.clone(), new_change_id(), &[]);
568        mutable_segment.add_commit_data(id_4.clone(), new_change_id(), &[]);
569        mutable_segment.add_commit_data(id_5.clone(), new_change_id(), &[]);
570
571        let index = mutable_segment.as_composite();
572
573        // Public API: calculate shortest unique prefix len with known commit_id
574        assert_eq!(index.shortest_unique_commit_id_prefix_len(&id_0), 3);
575        assert_eq!(index.shortest_unique_commit_id_prefix_len(&id_1), 3);
576        assert_eq!(index.shortest_unique_commit_id_prefix_len(&id_2), 5);
577        assert_eq!(index.shortest_unique_commit_id_prefix_len(&id_3), 5);
578        assert_eq!(index.shortest_unique_commit_id_prefix_len(&id_4), 4);
579        assert_eq!(index.shortest_unique_commit_id_prefix_len(&id_5), 2);
580
581        // Public API: calculate shortest unique prefix len with unknown commit_id
582        assert_eq!(
583            index.shortest_unique_commit_id_prefix_len(&CommitId::from_hex("000002")),
584            6
585        );
586        assert_eq!(
587            index.shortest_unique_commit_id_prefix_len(&CommitId::from_hex("010000")),
588            2
589        );
590        assert_eq!(
591            index.shortest_unique_commit_id_prefix_len(&CommitId::from_hex("033334")),
592            6
593        );
594        assert_eq!(
595            index.shortest_unique_commit_id_prefix_len(&CommitId::from_hex("ffffff")),
596            1
597        );
598    }
599
600    #[test]
601    fn resolve_change_id_prefix() {
602        let temp_dir = new_temp_dir();
603        let mut new_commit_id = commit_id_generator();
604        let local_positions_vec = |positions: &[u32]| -> SmallLocalPositionsVec {
605            positions.iter().copied().map(LocalPosition).collect()
606        };
607        let index_positions_vec = |positions: &[u32]| -> SmallIndexPositionsVec {
608            positions.iter().copied().map(IndexPosition).collect()
609        };
610
611        let id_0 = ChangeId::from_hex("00000001");
612        let id_1 = ChangeId::from_hex("00999999");
613        let id_2 = ChangeId::from_hex("05548888");
614        let id_3 = ChangeId::from_hex("05544444");
615        let id_4 = ChangeId::from_hex("05555555");
616        let id_5 = ChangeId::from_hex("05555333");
617
618        // Create some commits with different various common prefixes.
619        let mut mutable_segment = MutableIndexSegment::full(16, 4);
620        mutable_segment.add_commit_data(new_commit_id(), id_0.clone(), &[]);
621        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
622        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
623        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
624        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
625        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
626
627        // Write these commits to one file and build the remainder on top.
628        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();
629        mutable_segment = MutableIndexSegment::incremental(initial_file.clone());
630
631        mutable_segment.add_commit_data(new_commit_id(), id_3.clone(), &[]);
632        mutable_segment.add_commit_data(new_commit_id(), id_3.clone(), &[]);
633        mutable_segment.add_commit_data(new_commit_id(), id_4.clone(), &[]);
634        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
635        mutable_segment.add_commit_data(new_commit_id(), id_5.clone(), &[]);
636
637        // Local lookup in readonly index with the full hex digits
638        assert_eq!(
639            initial_file.resolve_change_id_prefix(&HexPrefix::new(&id_0.hex()).unwrap()),
640            PrefixResolution::SingleMatch((id_0.clone(), local_positions_vec(&[0])))
641        );
642        assert_eq!(
643            initial_file.resolve_change_id_prefix(&HexPrefix::new(&id_1.hex()).unwrap()),
644            PrefixResolution::SingleMatch((id_1.clone(), local_positions_vec(&[1, 3])))
645        );
646        assert_eq!(
647            initial_file.resolve_change_id_prefix(&HexPrefix::new(&id_2.hex()).unwrap()),
648            PrefixResolution::SingleMatch((id_2.clone(), local_positions_vec(&[2, 4, 5])))
649        );
650
651        // Local lookup in mutable index with the full hex digits
652        assert_eq!(
653            mutable_segment.resolve_change_id_prefix(&HexPrefix::new(&id_1.hex()).unwrap()),
654            PrefixResolution::SingleMatch((id_1.clone(), local_positions_vec(&[3])))
655        );
656        assert_eq!(
657            mutable_segment.resolve_change_id_prefix(&HexPrefix::new(&id_3.hex()).unwrap()),
658            PrefixResolution::SingleMatch((id_3.clone(), local_positions_vec(&[0, 1])))
659        );
660        assert_eq!(
661            mutable_segment.resolve_change_id_prefix(&HexPrefix::new(&id_4.hex()).unwrap()),
662            PrefixResolution::SingleMatch((id_4.clone(), local_positions_vec(&[2])))
663        );
664        assert_eq!(
665            mutable_segment.resolve_change_id_prefix(&HexPrefix::new(&id_5.hex()).unwrap()),
666            PrefixResolution::SingleMatch((id_5.clone(), local_positions_vec(&[4])))
667        );
668
669        // Local lookup with locally unknown prefix
670        assert_eq!(
671            initial_file.resolve_change_id_prefix(&HexPrefix::new("0555").unwrap()),
672            PrefixResolution::NoMatch
673        );
674        assert_eq!(
675            mutable_segment.resolve_change_id_prefix(&HexPrefix::new("000").unwrap()),
676            PrefixResolution::NoMatch
677        );
678
679        // Local lookup with locally unique prefix
680        assert_eq!(
681            initial_file.resolve_change_id_prefix(&HexPrefix::new("0554").unwrap()),
682            PrefixResolution::SingleMatch((id_2.clone(), local_positions_vec(&[2, 4, 5])))
683        );
684        assert_eq!(
685            mutable_segment.resolve_change_id_prefix(&HexPrefix::new("0554").unwrap()),
686            PrefixResolution::SingleMatch((id_3.clone(), local_positions_vec(&[0, 1])))
687        );
688
689        // Local lookup with locally ambiguous prefix
690        assert_eq!(
691            initial_file.resolve_change_id_prefix(&HexPrefix::new("00").unwrap()),
692            PrefixResolution::AmbiguousMatch
693        );
694        assert_eq!(
695            mutable_segment.resolve_change_id_prefix(&HexPrefix::new("05555").unwrap()),
696            PrefixResolution::AmbiguousMatch
697        );
698
699        let index = mutable_segment.as_composite();
700
701        // Global lookup with the full hex digits
702        assert_eq!(
703            index.resolve_change_id_prefix(&HexPrefix::new(&id_0.hex()).unwrap()),
704            PrefixResolution::SingleMatch((id_0.clone(), index_positions_vec(&[0])))
705        );
706        assert_eq!(
707            index.resolve_change_id_prefix(&HexPrefix::new(&id_1.hex()).unwrap()),
708            PrefixResolution::SingleMatch((id_1.clone(), index_positions_vec(&[1, 3, 9])))
709        );
710        assert_eq!(
711            index.resolve_change_id_prefix(&HexPrefix::new(&id_2.hex()).unwrap()),
712            PrefixResolution::SingleMatch((id_2.clone(), index_positions_vec(&[2, 4, 5])))
713        );
714        assert_eq!(
715            index.resolve_change_id_prefix(&HexPrefix::new(&id_3.hex()).unwrap()),
716            PrefixResolution::SingleMatch((id_3.clone(), index_positions_vec(&[6, 7])))
717        );
718        assert_eq!(
719            index.resolve_change_id_prefix(&HexPrefix::new(&id_4.hex()).unwrap()),
720            PrefixResolution::SingleMatch((id_4.clone(), index_positions_vec(&[8])))
721        );
722        assert_eq!(
723            index.resolve_change_id_prefix(&HexPrefix::new(&id_5.hex()).unwrap()),
724            PrefixResolution::SingleMatch((id_5.clone(), index_positions_vec(&[10])))
725        );
726
727        // Global lookup with unknown prefix
728        assert_eq!(
729            index.resolve_change_id_prefix(&HexPrefix::new("ffffffff").unwrap()),
730            PrefixResolution::NoMatch
731        );
732        assert_eq!(
733            index.resolve_change_id_prefix(&HexPrefix::new("00000002").unwrap()),
734            PrefixResolution::NoMatch
735        );
736
737        // Global lookup with globally unique prefix
738        assert_eq!(
739            index.resolve_change_id_prefix(&HexPrefix::new("000").unwrap()),
740            PrefixResolution::SingleMatch((id_0.clone(), index_positions_vec(&[0])))
741        );
742        assert_eq!(
743            index.resolve_change_id_prefix(&HexPrefix::new("055553").unwrap()),
744            PrefixResolution::SingleMatch((id_5.clone(), index_positions_vec(&[10])))
745        );
746
747        // Global lookup with globally unique prefix stored in both parts
748        assert_eq!(
749            index.resolve_change_id_prefix(&HexPrefix::new("009").unwrap()),
750            PrefixResolution::SingleMatch((id_1.clone(), index_positions_vec(&[1, 3, 9])))
751        );
752
753        // Global lookup with locally ambiguous prefix
754        assert_eq!(
755            index.resolve_change_id_prefix(&HexPrefix::new("00").unwrap()),
756            PrefixResolution::AmbiguousMatch
757        );
758        assert_eq!(
759            index.resolve_change_id_prefix(&HexPrefix::new("05555").unwrap()),
760            PrefixResolution::AmbiguousMatch
761        );
762
763        // Global lookup with locally unique but globally ambiguous prefix
764        assert_eq!(
765            index.resolve_change_id_prefix(&HexPrefix::new("0554").unwrap()),
766            PrefixResolution::AmbiguousMatch
767        );
768    }
769
770    #[test]
771    fn neighbor_change_ids() {
772        let temp_dir = new_temp_dir();
773        let mut new_commit_id = commit_id_generator();
774
775        let id_0 = ChangeId::from_hex("00000001");
776        let id_1 = ChangeId::from_hex("00999999");
777        let id_2 = ChangeId::from_hex("05548888");
778        let id_3 = ChangeId::from_hex("05544444");
779        let id_4 = ChangeId::from_hex("05555555");
780        let id_5 = ChangeId::from_hex("05555333");
781
782        // Create some commits with different various common prefixes.
783        let mut mutable_segment = MutableIndexSegment::full(16, 4);
784        mutable_segment.add_commit_data(new_commit_id(), id_0.clone(), &[]);
785        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
786        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
787        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
788        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
789        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
790
791        // Write these commits to one file and build the remainder on top.
792        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();
793        mutable_segment = MutableIndexSegment::incremental(initial_file.clone());
794
795        mutable_segment.add_commit_data(new_commit_id(), id_3.clone(), &[]);
796        mutable_segment.add_commit_data(new_commit_id(), id_3.clone(), &[]);
797        mutable_segment.add_commit_data(new_commit_id(), id_4.clone(), &[]);
798        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
799        mutable_segment.add_commit_data(new_commit_id(), id_5.clone(), &[]);
800
801        // Local lookup in readonly index, change_id exists.
802        assert_eq!(
803            initial_file.resolve_neighbor_change_ids(&id_0),
804            (None, Some(id_1.clone())),
805        );
806        assert_eq!(
807            initial_file.resolve_neighbor_change_ids(&id_1),
808            (Some(id_0.clone()), Some(id_2.clone())),
809        );
810        assert_eq!(
811            initial_file.resolve_neighbor_change_ids(&id_2),
812            (Some(id_1.clone()), None),
813        );
814
815        // Local lookup in readonly index, change_id does not exist.
816        assert_eq!(
817            initial_file.resolve_neighbor_change_ids(&ChangeId::from_hex("00000000")),
818            (None, Some(id_0.clone())),
819        );
820        assert_eq!(
821            initial_file.resolve_neighbor_change_ids(&ChangeId::from_hex("00000002")),
822            (Some(id_0.clone()), Some(id_1.clone())),
823        );
824        assert_eq!(
825            initial_file.resolve_neighbor_change_ids(&ChangeId::from_hex("ffffffff")),
826            (Some(id_2.clone()), None),
827        );
828
829        // Local lookup in mutable index, change_id exists.
830        // id_1 < id_3 < id_5 < id_4
831        assert_eq!(
832            mutable_segment.resolve_neighbor_change_ids(&id_1),
833            (None, Some(id_3.clone())),
834        );
835        assert_eq!(
836            mutable_segment.resolve_neighbor_change_ids(&id_3),
837            (Some(id_1.clone()), Some(id_5.clone())),
838        );
839        assert_eq!(
840            mutable_segment.resolve_neighbor_change_ids(&id_5),
841            (Some(id_3.clone()), Some(id_4.clone())),
842        );
843        assert_eq!(
844            mutable_segment.resolve_neighbor_change_ids(&id_4),
845            (Some(id_5.clone()), None),
846        );
847
848        // Local lookup in mutable index, change_id does not exist.
849        // id_1 < id_3 < id_5 < id_4
850        assert_eq!(
851            mutable_segment.resolve_neighbor_change_ids(&ChangeId::from_hex("00999998")),
852            (None, Some(id_1.clone())),
853        );
854        assert_eq!(
855            mutable_segment.resolve_neighbor_change_ids(&ChangeId::from_hex("01000000")),
856            (Some(id_1.clone()), Some(id_3.clone())),
857        );
858        assert_eq!(
859            mutable_segment.resolve_neighbor_change_ids(&ChangeId::from_hex("05555332")),
860            (Some(id_3.clone()), Some(id_5.clone())),
861        );
862        assert_eq!(
863            mutable_segment.resolve_neighbor_change_ids(&ChangeId::from_hex("ffffffff")),
864            (Some(id_4.clone()), None),
865        );
866
867        let index = mutable_segment.as_composite();
868
869        // Global lookup, change_id exists.
870        // id_0 < id_1 < id_3 < id_2 < id_5 < id_4
871        assert_eq!(
872            index.resolve_neighbor_change_ids(&id_0),
873            (None, Some(id_1.clone())),
874        );
875        assert_eq!(
876            index.resolve_neighbor_change_ids(&id_1),
877            (Some(id_0.clone()), Some(id_3.clone())),
878        );
879        assert_eq!(
880            index.resolve_neighbor_change_ids(&id_3),
881            (Some(id_1.clone()), Some(id_2.clone())),
882        );
883        assert_eq!(
884            index.resolve_neighbor_change_ids(&id_2),
885            (Some(id_3.clone()), Some(id_5.clone())),
886        );
887        assert_eq!(
888            index.resolve_neighbor_change_ids(&id_5),
889            (Some(id_2.clone()), Some(id_4.clone())),
890        );
891        assert_eq!(
892            index.resolve_neighbor_change_ids(&id_4),
893            (Some(id_5.clone()), None),
894        );
895
896        // Global lookup, change_id doesn't exist.
897        // id_0 < id_1 < id_3 < id_2 < id_5 < id_4
898        assert_eq!(
899            index.resolve_neighbor_change_ids(&ChangeId::from_hex("00000000")),
900            (None, Some(id_0.clone())),
901        );
902        assert_eq!(
903            index.resolve_neighbor_change_ids(&ChangeId::from_hex("01000000")),
904            (Some(id_1.clone()), Some(id_3.clone())),
905        );
906        assert_eq!(
907            index.resolve_neighbor_change_ids(&ChangeId::from_hex("05544555")),
908            (Some(id_3.clone()), Some(id_2.clone())),
909        );
910        assert_eq!(
911            index.resolve_neighbor_change_ids(&ChangeId::from_hex("ffffffff")),
912            (Some(id_4.clone()), None),
913        );
914    }
915
916    #[test]
917    fn shortest_unique_change_id_prefix() {
918        let temp_dir = new_temp_dir();
919        let mut new_commit_id = commit_id_generator();
920
921        let id_0 = ChangeId::from_hex("00000001");
922        let id_1 = ChangeId::from_hex("00999999");
923        let id_2 = ChangeId::from_hex("05548888");
924        let id_3 = ChangeId::from_hex("05544444");
925        let id_4 = ChangeId::from_hex("05555555");
926        let id_5 = ChangeId::from_hex("05555333");
927
928        // Create some commits with different various common prefixes.
929        let mut mutable_segment = MutableIndexSegment::full(16, 4);
930        mutable_segment.add_commit_data(new_commit_id(), id_0.clone(), &[]);
931        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
932        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
933        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
934        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
935        mutable_segment.add_commit_data(new_commit_id(), id_2.clone(), &[]);
936
937        // Write these commits to one file and build the remainder on top.
938        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();
939        mutable_segment = MutableIndexSegment::incremental(initial_file.clone());
940
941        mutable_segment.add_commit_data(new_commit_id(), id_3.clone(), &[]);
942        mutable_segment.add_commit_data(new_commit_id(), id_3.clone(), &[]);
943        mutable_segment.add_commit_data(new_commit_id(), id_4.clone(), &[]);
944        mutable_segment.add_commit_data(new_commit_id(), id_1.clone(), &[]);
945        mutable_segment.add_commit_data(new_commit_id(), id_5.clone(), &[]);
946
947        let index = mutable_segment.as_composite();
948
949        // Calculate shortest unique prefix len with known change_id
950        assert_eq!(index.shortest_unique_change_id_prefix_len(&id_0), 3);
951        assert_eq!(index.shortest_unique_change_id_prefix_len(&id_1), 3);
952        assert_eq!(index.shortest_unique_change_id_prefix_len(&id_2), 5);
953        assert_eq!(index.shortest_unique_change_id_prefix_len(&id_3), 5);
954        assert_eq!(index.shortest_unique_change_id_prefix_len(&id_4), 6);
955        assert_eq!(index.shortest_unique_change_id_prefix_len(&id_5), 6);
956
957        // Calculate shortest unique prefix len with unknown change_id
958        assert_eq!(
959            index.shortest_unique_change_id_prefix_len(&ChangeId::from_hex("00000002")),
960            8
961        );
962        assert_eq!(
963            index.shortest_unique_change_id_prefix_len(&ChangeId::from_hex("01000000")),
964            2
965        );
966        assert_eq!(
967            index.shortest_unique_change_id_prefix_len(&ChangeId::from_hex("05555344")),
968            7
969        );
970        assert_eq!(
971            index.shortest_unique_change_id_prefix_len(&ChangeId::from_hex("ffffffff")),
972            1
973        );
974    }
975
976    #[test]
977    fn test_is_ancestor() {
978        let mut new_change_id = change_id_generator();
979        let mut index = DefaultMutableIndex::full(3, 16);
980        // 5
981        // |\
982        // 4 | 3
983        // | |/
984        // 1 2
985        // |/
986        // 0
987        let id_0 = CommitId::from_hex("000000");
988        let id_1 = CommitId::from_hex("111111");
989        let id_2 = CommitId::from_hex("222222");
990        let id_3 = CommitId::from_hex("333333");
991        let id_4 = CommitId::from_hex("444444");
992        let id_5 = CommitId::from_hex("555555");
993        index.add_commit_data(id_0.clone(), new_change_id(), &[]);
994        index.add_commit_data(id_1.clone(), new_change_id(), &[id_0.clone()]);
995        index.add_commit_data(id_2.clone(), new_change_id(), &[id_0.clone()]);
996        index.add_commit_data(id_3.clone(), new_change_id(), &[id_2.clone()]);
997        index.add_commit_data(id_4.clone(), new_change_id(), &[id_1.clone()]);
998        index.add_commit_data(id_5.clone(), new_change_id(), &[id_4.clone(), id_2.clone()]);
999
1000        assert!(index.is_ancestor(&id_0, &id_0));
1001        assert!(index.is_ancestor(&id_0, &id_1));
1002        assert!(index.is_ancestor(&id_2, &id_3));
1003        assert!(index.is_ancestor(&id_2, &id_5));
1004        assert!(index.is_ancestor(&id_1, &id_5));
1005        assert!(index.is_ancestor(&id_0, &id_5));
1006        assert!(!index.is_ancestor(&id_1, &id_0));
1007        assert!(!index.is_ancestor(&id_5, &id_3));
1008        assert!(!index.is_ancestor(&id_3, &id_5));
1009        assert!(!index.is_ancestor(&id_2, &id_4));
1010        assert!(!index.is_ancestor(&id_4, &id_2));
1011    }
1012
1013    #[test]
1014    fn test_common_ancestors() {
1015        let mut new_change_id = change_id_generator();
1016        let mut index = DefaultMutableIndex::full(3, 16);
1017        // 5
1018        // |\
1019        // 4 |
1020        // | |
1021        // 1 2 3
1022        // | |/
1023        // |/
1024        // 0
1025        let id_0 = CommitId::from_hex("000000");
1026        let id_1 = CommitId::from_hex("111111");
1027        let id_2 = CommitId::from_hex("222222");
1028        let id_3 = CommitId::from_hex("333333");
1029        let id_4 = CommitId::from_hex("444444");
1030        let id_5 = CommitId::from_hex("555555");
1031        let id_6 = CommitId::from_hex("666666");
1032        index.add_commit_data(id_0.clone(), new_change_id(), &[]);
1033        index.add_commit_data(id_1.clone(), new_change_id(), &[id_0.clone()]);
1034        index.add_commit_data(id_2.clone(), new_change_id(), &[id_0.clone()]);
1035        index.add_commit_data(id_3.clone(), new_change_id(), &[id_0.clone()]);
1036        index.add_commit_data(id_4.clone(), new_change_id(), &[id_1.clone()]);
1037        index.add_commit_data(id_5.clone(), new_change_id(), &[id_4.clone(), id_2.clone()]);
1038        index.add_commit_data(id_6.clone(), new_change_id(), &[id_4.clone()]);
1039
1040        assert_eq!(
1041            index.common_ancestors(&[id_0.clone()], &[id_0.clone()]),
1042            vec![id_0.clone()]
1043        );
1044        assert_eq!(
1045            index.common_ancestors(&[id_5.clone()], &[id_5.clone()]),
1046            vec![id_5.clone()]
1047        );
1048        assert_eq!(
1049            index.common_ancestors(&[id_1.clone()], &[id_2.clone()]),
1050            vec![id_0.clone()]
1051        );
1052        assert_eq!(
1053            index.common_ancestors(&[id_2.clone()], &[id_1.clone()]),
1054            vec![id_0.clone()]
1055        );
1056        assert_eq!(
1057            index.common_ancestors(&[id_1.clone()], &[id_4.clone()]),
1058            vec![id_1.clone()]
1059        );
1060        assert_eq!(
1061            index.common_ancestors(&[id_4.clone()], &[id_1.clone()]),
1062            vec![id_1.clone()]
1063        );
1064        assert_eq!(
1065            index.common_ancestors(&[id_3.clone()], &[id_5.clone()]),
1066            vec![id_0.clone()]
1067        );
1068        assert_eq!(
1069            index.common_ancestors(&[id_5.clone()], &[id_3.clone()]),
1070            vec![id_0.clone()]
1071        );
1072        assert_eq!(
1073            index.common_ancestors(&[id_2.clone()], &[id_6.clone()]),
1074            vec![id_0.clone()]
1075        );
1076
1077        // With multiple commits in an input set
1078        assert_eq!(
1079            index.common_ancestors(&[id_0.clone(), id_1.clone()], &[id_0.clone()]),
1080            vec![id_0.clone()]
1081        );
1082        assert_eq!(
1083            index.common_ancestors(&[id_0.clone(), id_1.clone()], &[id_1.clone()]),
1084            vec![id_1.clone()]
1085        );
1086        assert_eq!(
1087            index.common_ancestors(&[id_1.clone(), id_2.clone()], &[id_1.clone()]),
1088            vec![id_1.clone()]
1089        );
1090        assert_eq!(
1091            index.common_ancestors(&[id_1.clone(), id_2.clone()], &[id_4]),
1092            vec![id_1.clone()]
1093        );
1094        assert_eq!(
1095            index.common_ancestors(&[id_5.clone(), id_6.clone()], &[id_2.clone()]),
1096            &[id_2.clone()]
1097        );
1098        // Both 1 and 2 are returned since (5) expands to (2, 4), which expands
1099        // to (1,2) and matches the (1,2) of the first input set.
1100        assert_eq!(
1101            index.common_ancestors(&[id_1.clone(), id_2.clone()], &[id_5]),
1102            vec![id_1.clone(), id_2.clone()]
1103        );
1104        assert_eq!(index.common_ancestors(&[id_1, id_2], &[id_3]), vec![id_0]);
1105    }
1106
1107    #[test]
1108    fn test_common_ancestors_criss_cross() {
1109        let mut new_change_id = change_id_generator();
1110        let mut index = DefaultMutableIndex::full(3, 16);
1111        // 3 4
1112        // |X|
1113        // 1 2
1114        // |/
1115        // 0
1116        let id_0 = CommitId::from_hex("000000");
1117        let id_1 = CommitId::from_hex("111111");
1118        let id_2 = CommitId::from_hex("222222");
1119        let id_3 = CommitId::from_hex("333333");
1120        let id_4 = CommitId::from_hex("444444");
1121        index.add_commit_data(id_0.clone(), new_change_id(), &[]);
1122        index.add_commit_data(id_1.clone(), new_change_id(), &[id_0.clone()]);
1123        index.add_commit_data(id_2.clone(), new_change_id(), &[id_0]);
1124        index.add_commit_data(id_3.clone(), new_change_id(), &[id_1.clone(), id_2.clone()]);
1125        index.add_commit_data(id_4.clone(), new_change_id(), &[id_1.clone(), id_2.clone()]);
1126
1127        let mut common_ancestors = index.common_ancestors(&[id_3], &[id_4]);
1128        common_ancestors.sort();
1129        assert_eq!(common_ancestors, vec![id_1, id_2]);
1130    }
1131
1132    #[test]
1133    fn test_common_ancestors_merge_with_ancestor() {
1134        let mut new_change_id = change_id_generator();
1135        let mut index = DefaultMutableIndex::full(3, 16);
1136        // 4   5
1137        // |\ /|
1138        // 1 2 3
1139        //  \|/
1140        //   0
1141        let id_0 = CommitId::from_hex("000000");
1142        let id_1 = CommitId::from_hex("111111");
1143        let id_2 = CommitId::from_hex("222222");
1144        let id_3 = CommitId::from_hex("333333");
1145        let id_4 = CommitId::from_hex("444444");
1146        let id_5 = CommitId::from_hex("555555");
1147        index.add_commit_data(id_0.clone(), new_change_id(), &[]);
1148        index.add_commit_data(id_1, new_change_id(), &[id_0.clone()]);
1149        index.add_commit_data(id_2.clone(), new_change_id(), &[id_0.clone()]);
1150        index.add_commit_data(id_3, new_change_id(), &[id_0.clone()]);
1151        index.add_commit_data(id_4.clone(), new_change_id(), &[id_0.clone(), id_2.clone()]);
1152        index.add_commit_data(id_5.clone(), new_change_id(), &[id_0, id_2.clone()]);
1153
1154        let mut common_ancestors = index.common_ancestors(&[id_4], &[id_5]);
1155        common_ancestors.sort();
1156        assert_eq!(common_ancestors, vec![id_2]);
1157    }
1158
1159    #[test]
1160    fn test_heads() {
1161        let mut new_change_id = change_id_generator();
1162        let mut index = DefaultMutableIndex::full(3, 16);
1163        // 5
1164        // |\
1165        // 4 | 3
1166        // | |/
1167        // 1 2
1168        // |/
1169        // 0
1170        let id_0 = CommitId::from_hex("000000");
1171        let id_1 = CommitId::from_hex("111111");
1172        let id_2 = CommitId::from_hex("222222");
1173        let id_3 = CommitId::from_hex("333333");
1174        let id_4 = CommitId::from_hex("444444");
1175        let id_5 = CommitId::from_hex("555555");
1176        index.add_commit_data(id_0.clone(), new_change_id(), &[]);
1177        index.add_commit_data(id_1.clone(), new_change_id(), &[id_0.clone()]);
1178        index.add_commit_data(id_2.clone(), new_change_id(), &[id_0.clone()]);
1179        index.add_commit_data(id_3.clone(), new_change_id(), &[id_2.clone()]);
1180        index.add_commit_data(id_4.clone(), new_change_id(), &[id_1.clone()]);
1181        index.add_commit_data(id_5.clone(), new_change_id(), &[id_4.clone(), id_2.clone()]);
1182
1183        // Empty input
1184        assert!(index.heads(&mut [].iter()).unwrap().is_empty());
1185        // Single head
1186        assert_eq!(
1187            index.heads(&mut [id_4.clone()].iter()).unwrap(),
1188            vec![id_4.clone()]
1189        );
1190        // Single head and parent
1191        assert_eq!(
1192            index.heads(&mut [id_4.clone(), id_1].iter()).unwrap(),
1193            vec![id_4.clone()]
1194        );
1195        // Single head and grand-parent
1196        assert_eq!(
1197            index.heads(&mut [id_4.clone(), id_0].iter()).unwrap(),
1198            vec![id_4.clone()]
1199        );
1200        // Multiple heads
1201        assert_eq!(
1202            index
1203                .heads(&mut [id_4.clone(), id_3.clone()].iter())
1204                .unwrap(),
1205            vec![id_3.clone(), id_4]
1206        );
1207        // Merge commit and ancestors
1208        assert_eq!(
1209            index.heads(&mut [id_5.clone(), id_2].iter()).unwrap(),
1210            vec![id_5.clone()]
1211        );
1212        // Merge commit and other commit
1213        assert_eq!(
1214            index
1215                .heads(&mut [id_5.clone(), id_3.clone()].iter())
1216                .unwrap(),
1217            vec![id_3.clone(), id_5.clone()]
1218        );
1219
1220        assert_eq!(
1221            index.all_heads_for_gc().unwrap().collect_vec(),
1222            vec![id_3.clone(), id_5.clone()]
1223        );
1224    }
1225}
jj_lib/default_index/mod.rs

jj_lib/default_index/
mod.rs
