// 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. use std::cmp::min; use super::composite::CompositeCommitIndex;use super::entry::GlobalCommitPosition; /// Unit of buffer allocation, which is 4kB.const PAGE_SIZE_IN_BITS: u32 = 4096 * 8;const PAGE_SIZE_IN_WORDS: u32 = PAGE_SIZE_IN_BITS / u64::BITS; /// Bit set of [`GlobalCommitPosition`]s.#[derive(Clone, Debug)]pub(super) struct PositionsBitSet {    data: Vec<u64>,    bitset_len: u32,} impl PositionsBitSet {    /// Creates bit set of the specified capacity.    pub fn with_capacity(len: u32) -> Self {        Self {            data: vec![],            bitset_len: u32::div_ceil(len, u64::BITS),        }    }     /// Creates bit set with the maximum position.    pub fn with_max_pos(max_pos: GlobalCommitPosition) -> Self {        assert_ne!(max_pos, GlobalCommitPosition::MAX);        Self::with_capacity(max_pos.0 + 1)    }     fn ensure_data(&mut self, bitset_pos: u32) {        if usize::try_from(bitset_pos).unwrap() < self.data.len() {            return;        }         // Do not pre-allocate large buffer which might not be used. We could        // manage buffer chunks as Vec<Vec<u64>>, but the extra indirection        // appeared to make get() slow.        let new_len = usize::try_from(min(            u32::div_ceil(bitset_pos + 1, PAGE_SIZE_IN_WORDS) * PAGE_SIZE_IN_WORDS,            self.bitset_len,        ))        .unwrap();        if self.data.is_empty() {            self.data = vec![0; new_len]; // request zeroed page        } else {            self.data.resize(new_len, 0); // realloc + copy        }    }     fn to_global_pos(&self, (bitset_pos, bit_pos): (u32, u32)) -> GlobalCommitPosition {        let bitset_rev_pos = u32::checked_sub(self.bitset_len, bitset_pos + 1)            .expect("bitset_pos < self.bitset_len");        GlobalCommitPosition(bitset_rev_pos * u64::BITS + bit_pos)    }     fn to_bitset_pos(&self, pos: GlobalCommitPosition) -> (u32, u32) {        let bitset_rev_pos = pos.0 / u64::BITS;        let bit_pos = pos.0 % u64::BITS;        let bitset_pos = u32::checked_sub(self.bitset_len, bitset_rev_pos + 1)            .expect("bitset_rev_pos < self.bitset_len");        (bitset_pos, bit_pos)    }     /// Returns `true` if the given `pos` is set.    ///    /// Panics if the `pos` exceeds the capacity.    pub fn get(&self, pos: GlobalCommitPosition) -> bool {        self.get_bit(self.to_bitset_pos(pos))    }     fn get_bit(&self, (bitset_pos, bit_pos): (u32, u32)) -> bool {        let bit = 1_u64 << bit_pos;        match self.data.get(usize::try_from(bitset_pos).unwrap()) {            Some(word) => *word & bit != 0,            None => false,        }    }     /// Sets `pos` to true.    ///    /// Panics if the `pos` exceeds the capacity.    pub fn set(&mut self, pos: GlobalCommitPosition) {        self.set_bit(self.to_bitset_pos(pos));    }     fn set_bit(&mut self, (bitset_pos, bit_pos): (u32, u32)) {        self.ensure_data(bitset_pos);        let bit = 1_u64 << bit_pos;        self.data[usize::try_from(bitset_pos).unwrap()] |= bit;    }     /// Sets `pos` to true. Returns `true` if the old value was set.    ///    /// Panics if the `pos` exceeds the capacity.    pub fn get_set(&mut self, pos: GlobalCommitPosition) -> bool {        self.get_set_bit(self.to_bitset_pos(pos))    }     fn get_set_bit(&mut self, (bitset_pos, bit_pos): (u32, u32)) -> bool {        self.ensure_data(bitset_pos);        let bit = 1_u64 << bit_pos;        let word = &mut self.data[usize::try_from(bitset_pos).unwrap()];        let old = *word & bit != 0;        *word |= bit;        old    }} /// Computes ancestors set lazily.////// This is similar to `RevWalk` functionality-wise, but implemented with the/// different design goals:////// * optimized for dense ancestors set/// * optimized for testing set membership/// * no iterator API (which could be implemented on top)#[derive(Clone, Debug)]pub(super) struct AncestorsBitSet {    bitset: PositionsBitSet,    next_bitset_pos_to_visit: u32,} impl AncestorsBitSet {    /// Creates bit set of the specified capacity.    pub fn with_capacity(len: u32) -> Self {        let bitset = PositionsBitSet::with_capacity(len);        let next_bitset_pos_to_visit = bitset.bitset_len;        Self {            bitset,            next_bitset_pos_to_visit,        }    }     /// Adds head `pos` to the set.    ///    /// Panics if the `pos` exceeds the capacity.    pub fn add_head(&mut self, pos: GlobalCommitPosition) {        let (bitset_pos, bit_pos) = self.bitset.to_bitset_pos(pos);        self.bitset.set_bit((bitset_pos, bit_pos));        self.next_bitset_pos_to_visit = min(self.next_bitset_pos_to_visit, bitset_pos);    }     /// Returns `true` if the given `pos` is ancestors of the heads.    ///    /// Panics if the `pos` exceeds the capacity or has not been visited yet.    pub fn contains(&self, pos: GlobalCommitPosition) -> bool {        let (bitset_pos, bit_pos) = self.bitset.to_bitset_pos(pos);        assert!(bitset_pos < self.next_bitset_pos_to_visit);        self.bitset.get_bit((bitset_pos, bit_pos))    }     /// Updates set by visiting ancestors until the given `to_visit_pos`.    pub fn visit_until(        &mut self,        index: &CompositeCommitIndex,        to_visit_pos: GlobalCommitPosition,    ) {        let (last_bitset_pos_to_visit, _) = self.bitset.to_bitset_pos(to_visit_pos);        if last_bitset_pos_to_visit < self.next_bitset_pos_to_visit {            return;        }        self.bitset.ensure_data(last_bitset_pos_to_visit);        for visiting_bitset_pos in self.next_bitset_pos_to_visit..=last_bitset_pos_to_visit {            let mut unvisited_bits =                self.bitset.data[usize::try_from(visiting_bitset_pos).unwrap()];            while unvisited_bits != 0 {                let bit_pos = u64::BITS - unvisited_bits.leading_zeros() - 1; // from MSB                unvisited_bits ^= 1_u64 << bit_pos;                let current_pos = self.bitset.to_global_pos((visiting_bitset_pos, bit_pos));                for parent_pos in index.entry_by_pos(current_pos).parent_positions() {                    assert!(parent_pos < current_pos);                    let (parent_bitset_pos, parent_bit_pos) = self.bitset.to_bitset_pos(parent_pos);                    self.bitset.ensure_data(parent_bitset_pos);                    let bit = 1_u64 << parent_bit_pos;                    self.bitset.data[usize::try_from(parent_bitset_pos).unwrap()] |= bit;                    if visiting_bitset_pos == parent_bitset_pos {                        unvisited_bits |= bit;                    }                }            }        }        self.next_bitset_pos_to_visit = last_bitset_pos_to_visit + 1;    }} #[cfg(test)]mod tests {    use super::super::composite::AsCompositeIndex as _;    use super::super::mutable::DefaultMutableIndex;    use super::super::readonly::FieldLengths;    use super::*;    use crate::backend::ChangeId;    use crate::backend::CommitId;    use crate::tests::TestResult;     /// 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()    }     #[test]    fn test_positions_bit_set() {        // Create with empty capacity, which is useless, but shouldn't panic        let _set = PositionsBitSet::with_capacity(0);         let mut set = PositionsBitSet::with_capacity(128);        assert!(!set.get(GlobalCommitPosition(0)));        assert!(!set.get(GlobalCommitPosition(127)));        set.set(GlobalCommitPosition(0));        assert!(set.get(GlobalCommitPosition(0)));        assert!(!set.get(GlobalCommitPosition(1)));        assert!(!set.get(GlobalCommitPosition(127)));        let old = set.get_set(GlobalCommitPosition(127));        assert!(!old);        assert!(!set.get(GlobalCommitPosition(63)));        assert!(!set.get(GlobalCommitPosition(64)));        assert!(set.get(GlobalCommitPosition(127)));        let old = set.get_set(GlobalCommitPosition(127));        assert!(old);    }     #[test]    fn test_positions_bit_set_allocation() -> TestResult {        let page_size_in_words = usize::try_from(PAGE_SIZE_IN_WORDS)?;        // Exactly one page        let mut set = PositionsBitSet::with_capacity(PAGE_SIZE_IN_BITS);        assert!(set.data.is_empty());        assert!(!set.get(GlobalCommitPosition(0)));        assert!(!set.get(GlobalCommitPosition(PAGE_SIZE_IN_BITS - 1)));        assert!(set.data.is_empty());        set.set(GlobalCommitPosition(0));        assert_eq!(set.data.len(), page_size_in_words);        set.set(GlobalCommitPosition(PAGE_SIZE_IN_BITS - 1));        assert_eq!(set.data.len(), page_size_in_words);        assert!(set.get(GlobalCommitPosition(0)));        assert!(set.get(GlobalCommitPosition(PAGE_SIZE_IN_BITS - 1)));         // Two pages        let mut set = PositionsBitSet::with_capacity(PAGE_SIZE_IN_BITS + 1);        assert!(set.data.is_empty());        set.set(GlobalCommitPosition(u64::BITS));        set.set(GlobalCommitPosition(PAGE_SIZE_IN_BITS));        assert_eq!(set.data.len(), page_size_in_words);        let old = set.get_set(GlobalCommitPosition(u64::BITS - 1));        assert!(!old);        assert_eq!(set.data.len(), usize::try_from(PAGE_SIZE_IN_WORDS + 1)?);        assert!(set.get(GlobalCommitPosition(u64::BITS - 1)));        assert!(set.get(GlobalCommitPosition(u64::BITS)));        assert!(set.get(GlobalCommitPosition(PAGE_SIZE_IN_BITS)));         // Exactly three pages        let mut set = PositionsBitSet::with_capacity(PAGE_SIZE_IN_BITS * 3);        assert!(set.data.is_empty());        set.set(GlobalCommitPosition(PAGE_SIZE_IN_BITS * 2));        assert_eq!(set.data.len(), page_size_in_words);        set.set(GlobalCommitPosition(PAGE_SIZE_IN_BITS));        assert_eq!(set.data.len(), usize::try_from(PAGE_SIZE_IN_WORDS * 2)?);        set.set(GlobalCommitPosition(0));        assert_eq!(set.data.len(), usize::try_from(PAGE_SIZE_IN_WORDS * 3)?);        assert!(set.get(GlobalCommitPosition(0)));        assert!(set.get(GlobalCommitPosition(PAGE_SIZE_IN_BITS)));        assert!(set.get(GlobalCommitPosition(PAGE_SIZE_IN_BITS * 2)));        Ok(())    }     #[test]    fn test_ancestors_bit_set() {        let mut new_commit_id = commit_id_generator();        let mut new_change_id = change_id_generator();        let mut mutable_index = DefaultMutableIndex::full(FieldLengths {            commit_id: 16,            change_id: 16,        });         // F      F = 256        // |\     E = 193,194,195,..,254        // E | D  D = 192,255        // | |/   C = 66,68,70,..,190        // B C    B = 65,67,69,..,189,191        // |/     A = 0,1,2,..,64        // A        let id_a0 = new_commit_id();        mutable_index.add_commit_data(id_a0.clone(), new_change_id(), &[]);        let id_a64 = (1..=64).fold(id_a0.clone(), |parent_id, i| {            assert_eq!(mutable_index.num_commits(), i);            let id = new_commit_id();            mutable_index.add_commit_data(id.clone(), new_change_id(), &[parent_id]);            id        });        let (id_b189, id_c190) = (65..=190).step_by(2).fold(            (id_a64.clone(), id_a64.clone()),            |(parent_id_b, parent_id_c), i| {                assert_eq!(mutable_index.num_commits(), i);                let id_b = new_commit_id();                let id_c = new_commit_id();                mutable_index.add_commit_data(id_b.clone(), new_change_id(), &[parent_id_b]);                mutable_index.add_commit_data(id_c.clone(), new_change_id(), &[parent_id_c]);                (id_b, id_c)            },        );        let id_b191 = new_commit_id();        mutable_index.add_commit_data(id_b191.clone(), new_change_id(), &[id_b189]);        let id_d192 = new_commit_id();        mutable_index.add_commit_data(            id_d192.clone(),            new_change_id(),            std::slice::from_ref(&id_c190),        );        let id_e254 = (193..=254).fold(id_b191.clone(), |parent_id, i| {            assert_eq!(mutable_index.num_commits(), i);            let id = new_commit_id();            mutable_index.add_commit_data(id.clone(), new_change_id(), &[parent_id]);            id        });        let id_d255 = new_commit_id();        mutable_index.add_commit_data(            id_d255.clone(),            new_change_id(),            std::slice::from_ref(&id_d192),        );        let id_f256 = new_commit_id();        mutable_index.add_commit_data(            id_f256.clone(),            new_change_id(),            &[id_c190.clone(), id_e254.clone()],        );        assert_eq!(mutable_index.num_commits(), 257);         let index = mutable_index.as_composite().commits();        let to_pos = |id: &CommitId| index.commit_id_to_pos(id).unwrap();        let new_ancestors_set = |heads: &[&CommitId]| {            let mut set = AncestorsBitSet::with_capacity(index.num_commits());            for &id in heads {                set.add_head(to_pos(id));            }            set        };         // Nothing reachable        let set = new_ancestors_set(&[]);        assert_eq!(set.next_bitset_pos_to_visit, 5);        for pos in (0..=256).map(GlobalCommitPosition) {            assert!(!set.contains(pos), "{pos:?} should be unreachable");        }         // All reachable        let mut set = new_ancestors_set(&[&id_f256, &id_d255]);        assert_eq!(set.next_bitset_pos_to_visit, 0);        set.visit_until(index, to_pos(&id_f256));        assert_eq!(set.next_bitset_pos_to_visit, 1);        assert!(set.contains(to_pos(&id_f256)));        set.visit_until(index, to_pos(&id_d192));        assert_eq!(set.next_bitset_pos_to_visit, 2);        assert!(set.contains(to_pos(&id_e254)));        assert!(set.contains(to_pos(&id_d255)));        assert!(set.contains(to_pos(&id_d192)));        set.visit_until(index, to_pos(&id_a0));        assert_eq!(set.next_bitset_pos_to_visit, 5);        set.visit_until(index, to_pos(&id_f256)); // should be noop        assert_eq!(set.next_bitset_pos_to_visit, 5);        for pos in (0..=256).map(GlobalCommitPosition) {            assert!(set.contains(pos), "{pos:?} should be reachable");        }         // A, B, C, E, F are reachable        let mut set = new_ancestors_set(&[&id_f256]);        assert_eq!(set.next_bitset_pos_to_visit, 0);        set.visit_until(index, to_pos(&id_f256));        assert_eq!(set.next_bitset_pos_to_visit, 1);        assert!(set.contains(to_pos(&id_f256)));        set.visit_until(index, to_pos(&id_d192));        assert_eq!(set.next_bitset_pos_to_visit, 2);        assert!(!set.contains(to_pos(&id_d255)));        assert!(!set.contains(to_pos(&id_d192)));        set.visit_until(index, to_pos(&id_c190));        assert_eq!(set.next_bitset_pos_to_visit, 3);        assert!(set.contains(to_pos(&id_c190)));        set.visit_until(index, to_pos(&id_a64));        assert_eq!(set.next_bitset_pos_to_visit, 4);        assert!(set.contains(to_pos(&id_b191)));        assert!(set.contains(to_pos(&id_a64)));        set.visit_until(index, to_pos(&id_a0));        assert_eq!(set.next_bitset_pos_to_visit, 5);        assert!(set.contains(to_pos(&id_a0)));         // A, C, D are reachable        let mut set = new_ancestors_set(&[&id_d255]);        assert_eq!(set.next_bitset_pos_to_visit, 1);        assert!(!set.contains(to_pos(&id_f256)));        set.visit_until(index, to_pos(&id_e254));        assert_eq!(set.next_bitset_pos_to_visit, 2);        assert!(!set.contains(to_pos(&id_e254)));        set.visit_until(index, to_pos(&id_d255));        assert_eq!(set.next_bitset_pos_to_visit, 2);        assert!(set.contains(to_pos(&id_d255)));        set.visit_until(index, to_pos(&id_b191));        assert_eq!(set.next_bitset_pos_to_visit, 3);        assert!(!set.contains(to_pos(&id_b191)));        set.visit_until(index, to_pos(&id_c190));        assert_eq!(set.next_bitset_pos_to_visit, 3);        assert!(set.contains(to_pos(&id_c190)));        set.visit_until(index, to_pos(&id_a0));        assert_eq!(set.next_bitset_pos_to_visit, 5);        assert!(set.contains(to_pos(&id_a64)));        assert!(set.contains(to_pos(&id_a0)));    }     #[test]    fn test_ancestors_bit_set_allocation() -> TestResult {        let page_size_in_words = usize::try_from(PAGE_SIZE_IN_WORDS)?;        let mut new_commit_id = commit_id_generator();        let mut new_change_id = change_id_generator();        let mut mutable_index = DefaultMutableIndex::full(FieldLengths {            commit_id: 16,            change_id: 16,        });        // Linear history of two-page size        let id_0 = new_commit_id();        mutable_index.add_commit_data(id_0.clone(), new_change_id(), &[]);        (1..=PAGE_SIZE_IN_BITS).fold(id_0.clone(), |parent_id, i| {            assert_eq!(mutable_index.num_commits(), i);            let id = new_commit_id();            mutable_index.add_commit_data(id.clone(), new_change_id(), &[parent_id]);            id        });        let index = mutable_index.as_composite().commits();         let mut set = AncestorsBitSet::with_capacity(index.num_commits());        assert_eq!(set.next_bitset_pos_to_visit, PAGE_SIZE_IN_WORDS + 1);         // Mark the head commit        set.add_head(GlobalCommitPosition(PAGE_SIZE_IN_BITS));        assert_eq!(set.next_bitset_pos_to_visit, 0);        assert_eq!(set.bitset.data.len(), page_size_in_words);         set.visit_until(index, GlobalCommitPosition(PAGE_SIZE_IN_BITS));        assert_eq!(set.next_bitset_pos_to_visit, 1);        assert_eq!(set.bitset.data.len(), page_size_in_words);        assert!(set.contains(GlobalCommitPosition(PAGE_SIZE_IN_BITS)));         set.visit_until(index, GlobalCommitPosition(PAGE_SIZE_IN_BITS - 1));        assert_eq!(set.next_bitset_pos_to_visit, 2);        assert_eq!(set.bitset.data.len(), page_size_in_words);        assert!(set.contains(GlobalCommitPosition(PAGE_SIZE_IN_BITS - 1)));         // Parent link across page boundary        set.visit_until(index, GlobalCommitPosition(u64::BITS));        assert_eq!(set.next_bitset_pos_to_visit, PAGE_SIZE_IN_WORDS);        assert_eq!(            set.bitset.data.len(),            usize::try_from(PAGE_SIZE_IN_WORDS + 1)?        );        assert!(set.contains(GlobalCommitPosition(u64::BITS)));         set.visit_until(index, GlobalCommitPosition(0));        assert_eq!(set.next_bitset_pos_to_visit, PAGE_SIZE_IN_WORDS + 1);        assert_eq!(            set.bitset.data.len(),            usize::try_from(PAGE_SIZE_IN_WORDS + 1)?        );        assert!(set.contains(GlobalCommitPosition(0)));        Ok(())    }}