// Copyright 2023 The Jujutsu Authors//// Licensed under the Apache License, Version 2.0 (the "License");// you may not use this file except in compliance with the License.// You may obtain a copy of the License at//// https://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.// See the License for the specific language governing permissions and// limitations under the License. //! An on-disk index of the commits in a repository.//!//! Implements an index of the commits in a repository that conforms to the//! trains in the [index module](crate::index). The index is stored on local//! disk and contains an entry for every commit in the repository. See//! [`DefaultReadonlyIndex`] and [`DefaultMutableIndex`]. mod bit_set;mod changed_path;mod composite;mod entry;mod mutable;mod readonly;mod rev_walk;mod rev_walk_queue;mod revset_engine;mod revset_graph_iterator;mod store; pub use self::mutable::DefaultMutableIndex;pub use self::readonly::ChangedPathIndexLevelStats;pub use self::readonly::CommitIndexLevelStats;pub use self::readonly::DefaultReadonlyIndex;pub use self::readonly::DefaultReadonlyIndexRevset;pub use self::readonly::IndexStats;pub use self::readonly::ReadonlyIndexLoadError;pub use self::store::DefaultIndexStore;pub use self::store::DefaultIndexStoreError;pub use self::store::DefaultIndexStoreInitError; #[cfg(test)]#[rustversion::attr(    since(1.89),    expect(clippy::cloned_ref_to_slice_refs, reason = "makes tests more readable"))]mod tests {    use std::cmp::Reverse;    use std::convert::Infallible;    use std::ops::Range;    use std::sync::Arc;     use itertools::Itertools as _;    use smallvec::smallvec_inline;    use test_case::test_case;     use super::changed_path::CompositeChangedPathIndex;    use super::composite::AsCompositeIndex as _;    use super::composite::CommitIndexSegment as _;    use super::composite::CompositeCommitIndex;    use super::composite::DynCommitIndexSegment;    use super::entry::GlobalCommitPosition;    use super::entry::SmallGlobalCommitPositionsVec;    use super::mutable::MutableCommitIndexSegment;    use super::readonly::ReadonlyCommitIndexSegment;    use super::*;    use crate::backend::ChangeId;    use crate::backend::CommitId;    use crate::default_index::entry::LocalCommitPosition;    use crate::default_index::entry::SmallLocalCommitPositionsVec;    use crate::default_index::readonly::FieldLengths;    use crate::index::Index as _;    use crate::object_id::HexPrefix;    use crate::object_id::PrefixResolution;    use crate::revset::PARENTS_RANGE_FULL;    use crate::tests::new_temp_dir;     const TEST_FIELD_LENGTHS: FieldLengths = FieldLengths {        // TODO: align with commit_id_generator()?        commit_id: 3,        change_id: 16,    };     /// Generator of unique 16-byte CommitId excluding root id    fn commit_id_generator() -> impl FnMut() -> CommitId {        let mut iter = (1_u128..).map(|n| CommitId::new(n.to_le_bytes().into()));        move || iter.next().unwrap()    }     /// Generator of unique 16-byte ChangeId excluding root id    fn change_id_generator() -> impl FnMut() -> ChangeId {        let mut iter = (1_u128..).map(|n| ChangeId::new(n.to_le_bytes().into()));        move || iter.next().unwrap()    }     fn get_commit_index_stats(commits: &Arc<ReadonlyCommitIndexSegment>) -> IndexStats {        let changed_paths = CompositeChangedPathIndex::null();        let index = DefaultReadonlyIndex::from_segment(commits.clone(), changed_paths);        index.stats()    }     #[test_case(false; "memory")]    #[test_case(true; "file")]    fn index_empty(on_disk: bool) {        let temp_dir = new_temp_dir();        let mutable_segment = MutableCommitIndexSegment::full(TEST_FIELD_LENGTHS);        let index_segment: Box<DynCommitIndexSegment> = if on_disk {            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();            // Stats are as expected            let stats = get_commit_index_stats(&saved_index);            assert_eq!(stats.num_commits, 0);            assert_eq!(stats.num_heads, 0);            assert_eq!(stats.max_generation_number, 0);            assert_eq!(stats.num_merges, 0);            assert_eq!(stats.num_changes, 0);            Box::new(Arc::try_unwrap(saved_index).unwrap())        } else {            Box::new(mutable_segment)        };        let index = CompositeCommitIndex::new(index_segment.as_ref());        assert_eq!(index.num_commits(), 0);         // Cannot find any commits        assert!(index.entry_by_id(&CommitId::from_hex("000000")).is_none());        assert!(index.entry_by_id(&CommitId::from_hex("aaa111")).is_none());        assert!(index.entry_by_id(&CommitId::from_hex("ffffff")).is_none());    }     #[test_case(false; "memory")]    #[test_case(true; "file")]    fn index_root_commit(on_disk: bool) {        let temp_dir = new_temp_dir();        let mut new_change_id = change_id_generator();        let mut mutable_segment = MutableCommitIndexSegment::full(TEST_FIELD_LENGTHS);        let id_0 = CommitId::from_hex("000000");        let change_id0 = new_change_id();        mutable_segment.add_commit_data(id_0.clone(), change_id0.clone(), &[]);        let index_segment: Box<DynCommitIndexSegment> = if on_disk {            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();            // Stats are as expected            let stats = get_commit_index_stats(&saved_index);            assert_eq!(stats.num_commits, 1);            assert_eq!(stats.num_heads, 1);            assert_eq!(stats.max_generation_number, 0);            assert_eq!(stats.num_merges, 0);            assert_eq!(stats.num_changes, 1);            Box::new(Arc::try_unwrap(saved_index).unwrap())        } else {            Box::new(mutable_segment)        };        let index = CompositeCommitIndex::new(index_segment.as_ref());        assert_eq!(index.num_commits(), 1);         // Can find only the root commit        assert_eq!(index.commit_id_to_pos(&id_0), Some(GlobalCommitPosition(0)));        assert_eq!(index.commit_id_to_pos(&CommitId::from_hex("aaaaaa")), None);        assert_eq!(index.commit_id_to_pos(&CommitId::from_hex("ffffff")), None);        // Check properties of root entry        let entry = index.entry_by_id(&id_0).unwrap();        assert_eq!(entry.position(), GlobalCommitPosition(0));        assert_eq!(entry.commit_id(), id_0);        assert_eq!(entry.change_id(), change_id0);        assert_eq!(entry.generation_number(), 0);        assert_eq!(entry.num_parents(), 0);        assert_eq!(            entry.parent_positions(),            SmallGlobalCommitPositionsVec::new()        );        assert_eq!(entry.parents().len(), 0);    }     #[test]    #[should_panic(expected = "parent commit is not indexed")]    fn index_missing_parent_commit() {        let mut new_change_id = change_id_generator();        let mut index = DefaultMutableIndex::full(TEST_FIELD_LENGTHS);        let id_0 = CommitId::from_hex("000000");        let id_1 = CommitId::from_hex("111111");        index.add_commit_data(id_1, new_change_id(), &[id_0]);    }     #[test_case(false, false; "full in memory")]    #[test_case(false, true; "full on disk")]    #[test_case(true, false; "incremental in memory")]    #[test_case(true, true; "incremental on disk")]    fn index_multiple_commits(incremental: bool, on_disk: bool) {        let temp_dir = new_temp_dir();        let mut new_change_id = change_id_generator();        let mut mutable_segment = MutableCommitIndexSegment::full(TEST_FIELD_LENGTHS);        // 5        // |\        // 4 | 3        // | |/        // 1 2        // |/        // 0        let id_0 = CommitId::from_hex("000000");        let change_id0 = new_change_id();        let id_1 = CommitId::from_hex("111111");        let change_id1 = new_change_id();        let id_2 = CommitId::from_hex("222222");        let change_id2 = change_id1.clone();        mutable_segment.add_commit_data(id_0.clone(), change_id0, &[]);        mutable_segment.add_commit_data(id_1.clone(), change_id1.clone(), &[id_0.clone()]);        mutable_segment.add_commit_data(id_2.clone(), change_id2.clone(), &[id_0.clone()]);         // If testing incremental indexing, write the first three commits to one file        // now and build the remainder as another segment on top.        if incremental {            let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();            mutable_segment = MutableCommitIndexSegment::incremental(initial_file);        }         let id_3 = CommitId::from_hex("333333");        let change_id3 = new_change_id();        let id_4 = CommitId::from_hex("444444");        let change_id4 = new_change_id();        let id_5 = CommitId::from_hex("555555");        let change_id5 = change_id3.clone();        mutable_segment.add_commit_data(id_3.clone(), change_id3.clone(), &[id_2.clone()]);        mutable_segment.add_commit_data(id_4.clone(), change_id4, &[id_1.clone()]);        mutable_segment.add_commit_data(id_5.clone(), change_id5, &[id_4.clone(), id_2.clone()]);        let index_segment: Box<DynCommitIndexSegment> = if on_disk {            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();            // Stats are as expected            let stats = get_commit_index_stats(&saved_index);            assert_eq!(stats.num_commits, 6);            assert_eq!(stats.num_heads, 2);            assert_eq!(stats.max_generation_number, 3);            assert_eq!(stats.num_merges, 1);            assert_eq!(stats.num_changes, 4);            Box::new(Arc::try_unwrap(saved_index).unwrap())        } else {            Box::new(mutable_segment)        };        let index = CompositeCommitIndex::new(index_segment.as_ref());        assert_eq!(index.num_commits(), 6);         // Can find all the commits        let entry_0 = index.entry_by_id(&id_0).unwrap();        let entry_1 = index.entry_by_id(&id_1).unwrap();        let entry_2 = index.entry_by_id(&id_2).unwrap();        let entry_3 = index.entry_by_id(&id_3).unwrap();        let entry_4 = index.entry_by_id(&id_4).unwrap();        let entry_5 = index.entry_by_id(&id_5).unwrap();        // Check properties of some entries        assert_eq!(entry_0.position(), GlobalCommitPosition(0));        assert_eq!(entry_0.commit_id(), id_0);        assert_eq!(entry_1.position(), GlobalCommitPosition(1));        assert_eq!(entry_1.commit_id(), id_1);        assert_eq!(entry_1.change_id(), change_id1);        assert_eq!(entry_1.generation_number(), 1);        assert_eq!(entry_1.num_parents(), 1);        assert_eq!(            entry_1.parent_positions(),            smallvec_inline![GlobalCommitPosition(0)]        );        assert_eq!(entry_1.parents().len(), 1);        assert_eq!(            entry_1.parents().next().unwrap().position(),            GlobalCommitPosition(0)        );        assert_eq!(entry_2.position(), GlobalCommitPosition(2));        assert_eq!(entry_2.commit_id(), id_2);        assert_eq!(entry_2.change_id(), change_id2);        assert_eq!(entry_2.generation_number(), 1);        assert_eq!(entry_2.num_parents(), 1);        assert_eq!(            entry_2.parent_positions(),            smallvec_inline![GlobalCommitPosition(0)]        );        assert_eq!(entry_3.change_id(), change_id3);        assert_eq!(entry_3.generation_number(), 2);        assert_eq!(            entry_3.parent_positions(),            smallvec_inline![GlobalCommitPosition(2)]        );        assert_eq!(entry_4.position(), GlobalCommitPosition(4));        assert_eq!(entry_4.generation_number(), 2);        assert_eq!(entry_4.num_parents(), 1);        assert_eq!(            entry_4.parent_positions(),            smallvec_inline![GlobalCommitPosition(1)]        );        assert_eq!(entry_5.generation_number(), 3);        assert_eq!(entry_5.num_parents(), 2);        assert_eq!(            entry_5.parent_positions(),            smallvec_inline![GlobalCommitPosition(4), GlobalCommitPosition(2)]        );        assert_eq!(entry_5.parents().len(), 2);        assert_eq!(            entry_5.parents().next().unwrap().position(),            GlobalCommitPosition(4)        );        assert_eq!(            entry_5.parents().nth(1).unwrap().position(),            GlobalCommitPosition(2)        );    }     #[test_case(false; "in memory")]    #[test_case(true; "on disk")]    fn index_many_parents(on_disk: bool) {        let temp_dir = new_temp_dir();        let mut new_change_id = change_id_generator();        let mut mutable_segment = MutableCommitIndexSegment::full(TEST_FIELD_LENGTHS);        //     6        //    /|\        //   / | \        //  / /|\ \        // 1 2 3 4 5        //  \ \|/ /        //   \ | /        //    \|/        //     0        let id_0 = CommitId::from_hex("000000");        let id_1 = CommitId::from_hex("111111");        let id_2 = CommitId::from_hex("222222");        let id_3 = CommitId::from_hex("333333");        let id_4 = CommitId::from_hex("444444");        let id_5 = CommitId::from_hex("555555");        let id_6 = CommitId::from_hex("666666");        mutable_segment.add_commit_data(id_0.clone(), new_change_id(), &[]);        mutable_segment.add_commit_data(id_1.clone(), new_change_id(), &[id_0.clone()]);        mutable_segment.add_commit_data(id_2.clone(), new_change_id(), &[id_0.clone()]);        mutable_segment.add_commit_data(id_3.clone(), new_change_id(), &[id_0.clone()]);        mutable_segment.add_commit_data(id_4.clone(), new_change_id(), &[id_0.clone()]);        mutable_segment.add_commit_data(id_5.clone(), new_change_id(), &[id_0]);        mutable_segment.add_commit_data(            id_6.clone(),            new_change_id(),            &[id_1, id_2, id_3, id_4, id_5],        );        let index_segment: Box<DynCommitIndexSegment> = if on_disk {            let saved_index = mutable_segment.save_in(temp_dir.path()).unwrap();            // Stats are as expected            let stats = get_commit_index_stats(&saved_index);            assert_eq!(stats.num_commits, 7);            assert_eq!(stats.num_heads, 1);            assert_eq!(stats.max_generation_number, 2);            assert_eq!(stats.num_merges, 1);            Box::new(Arc::try_unwrap(saved_index).unwrap())        } else {            Box::new(mutable_segment)        };        let index = CompositeCommitIndex::new(index_segment.as_ref());        assert_eq!(index.num_commits(), 7);         // The octopus merge has the right parents        let entry_6 = index.entry_by_id(&id_6).unwrap();        assert_eq!(entry_6.commit_id(), id_6.clone());        assert_eq!(entry_6.num_parents(), 5);        assert_eq!(            entry_6.parent_positions(),            smallvec_inline![                GlobalCommitPosition(1),                GlobalCommitPosition(2),                GlobalCommitPosition(3),                GlobalCommitPosition(4),                GlobalCommitPosition(5),            ]        );        assert_eq!(entry_6.generation_number(), 2);    }     #[test]    fn resolve_commit_id_prefix() {        let temp_dir = new_temp_dir();        let mut new_change_id = change_id_generator();        let mut mutable_segment = MutableCommitIndexSegment::full(TEST_FIELD_LENGTHS);         // Create some commits with different various common prefixes.        let id_0 = CommitId::from_hex("000000");        let id_1 = CommitId::from_hex("009999");        let id_2 = CommitId::from_hex("055488");        mutable_segment.add_commit_data(id_0.clone(), new_change_id(), &[]);        mutable_segment.add_commit_data(id_1.clone(), new_change_id(), &[]);        mutable_segment.add_commit_data(id_2.clone(), new_change_id(), &[]);         // Write the first three commits to one file and build the remainder on top.        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();        mutable_segment = MutableCommitIndexSegment::incremental(initial_file);         let id_3 = CommitId::from_hex("055444");        let id_4 = CommitId::from_hex("055555");        let id_5 = CommitId::from_hex("033333");        mutable_segment.add_commit_data(id_3, new_change_id(), &[]);        mutable_segment.add_commit_data(id_4, new_change_id(), &[]);        mutable_segment.add_commit_data(id_5, new_change_id(), &[]);         let index = mutable_segment.as_composite();         // Can find commits given the full hex number        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::from_id(&id_0)),            PrefixResolution::SingleMatch(id_0)        );        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::from_id(&id_1)),            PrefixResolution::SingleMatch(id_1)        );        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::from_id(&id_2)),            PrefixResolution::SingleMatch(id_2)        );        // Test nonexistent commits        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::try_from_hex("ffffff").unwrap()),            PrefixResolution::NoMatch        );        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::try_from_hex("000001").unwrap()),            PrefixResolution::NoMatch        );        // Test ambiguous prefix        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::try_from_hex("0").unwrap()),            PrefixResolution::AmbiguousMatch        );        // Test a globally unique prefix in initial part        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::try_from_hex("009").unwrap()),            PrefixResolution::SingleMatch(CommitId::from_hex("009999"))        );        // Test a globally unique prefix in incremental part        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::try_from_hex("03").unwrap()),            PrefixResolution::SingleMatch(CommitId::from_hex("033333"))        );        // Test a locally unique but globally ambiguous prefix        assert_eq!(            index.resolve_commit_id_prefix(&HexPrefix::try_from_hex("0554").unwrap()),            PrefixResolution::AmbiguousMatch        );    }     #[test]    #[expect(clippy::redundant_clone)] // allow id_n.clone()    fn neighbor_commit_ids() {        let temp_dir = new_temp_dir();        let mut new_change_id = change_id_generator();        let mut mutable_segment = MutableCommitIndexSegment::full(TEST_FIELD_LENGTHS);         // Create some commits with different various common prefixes.        let id_0 = CommitId::from_hex("000001");        let id_1 = CommitId::from_hex("009999");        let id_2 = CommitId::from_hex("055488");        mutable_segment.add_commit_data(id_0.clone(), new_change_id(), &[]);        mutable_segment.add_commit_data(id_1.clone(), new_change_id(), &[]);        mutable_segment.add_commit_data(id_2.clone(), new_change_id(), &[]);         // Write the first three commits to one file and build the remainder on top.        let initial_file = mutable_segment.save_in(temp_dir.path()).unwrap();        mutable_segment = MutableCommitIndexSegment::incremental(initial_file.clone());         let id_3 = CommitId::from_hex("055444");        let id_4 = CommitId::from_hex("055555");        let id_5 = CommitId::from_hex("033333");        mutable_segment.add_commit_data(id_3.clone(), new_change_id(), &[]);        mutable_segment.add_commit_data(id_4.clone(), new_change_id(), &[]);        mutable_segment.add_commit_data(id_5.clone(), new_change_id(), &[]);         // Local lookup in readonly index, commit_id exists.        assert_eq!(            initial_file.resolve_neighbor_commit_ids(&id_0),            (None, Some(id_1.clone())),        );        assert_eq!(            initial_file.resolve_neighbor_commit_ids(&id_1),            (Some(id_0.clone()), Some(id_2.clone())),        );        assert_eq!(            initial_file.resolve_neighbor_commit_ids(&id_2),            (Some(id_1.clone()), None),        );         // Local lookup in readonly index, commit_id does not exist.        assert_eq!(            initial_file.resolve_neighbor_commit_ids(&CommitId::from_hex("000000")),            (None, Some(id_0.clone())),        );        assert_eq!(            initial_file.resolve_neighbor_commit_ids(&CommitId::from_hex("000002")),            (Some(id_0.clone()), Some(id_1.clone())),        );        assert_eq!(            initial_file.resolve_neighbor_commit_ids(&CommitId::from_hex("ffffff")),            (Some(id_2.clone()), None),        );         // Local lookup in mutable index, commit_id exists. id_5 < id_3 < id_4        assert_eq!(            mutable_segment.resolve_neighbor_commit_ids(&id_5),            (None, Some(id_3.clone())),        );        assert_eq!(

Lines 1–500 of 1394. Load more