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

jj_lib/default_index/
mod.rs
