// 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. #![allow(missing_docs)] use std::any::Any;use std::cmp::Ordering;use std::fmt::Debug;use std::fmt::Formatter;use std::fs::File;use std::io;use std::io::Read;use std::path::Path;use std::sync::Arc; use smallvec::smallvec;use thiserror::Error; use super::composite::AsCompositeIndex;use super::composite::ChangeIdIndexImpl;use super::composite::CompositeIndex;use super::composite::IndexSegment;use super::entry::IndexPosition;use super::entry::LocalPosition;use super::entry::SmallIndexPositionsVec;use super::entry::SmallLocalPositionsVec;use super::mutable::DefaultMutableIndex;use crate::backend::ChangeId;use crate::backend::CommitId;use crate::index::AllHeadsForGcUnsupported;use crate::index::ChangeIdIndex;use crate::index::Index;use crate::index::IndexError;use crate::index::MutableIndex;use crate::index::ReadonlyIndex;use crate::object_id::HexPrefix;use crate::object_id::ObjectId;use crate::object_id::PrefixResolution;use crate::revset::ResolvedExpression;use crate::revset::Revset;use crate::revset::RevsetEvaluationError;use crate::store::Store; /// Error while loading index segment file.#[derive(Debug, Error)]pub enum ReadonlyIndexLoadError {    #[error("Unexpected index version")]    UnexpectedVersion {        found_version: u32,        expected_version: u32,    },    #[error("Failed to load commit index file '{name}'")]    Other {        /// Index file name.        name: String,        /// Underlying error.        #[source]        error: io::Error,    },} impl ReadonlyIndexLoadError {    fn invalid_data(        name: impl Into<String>,        error: impl Into<Box<dyn std::error::Error + Send + Sync>>,    ) -> Self {        Self::from_io_err(name, io::Error::new(io::ErrorKind::InvalidData, error))    }     fn from_io_err(name: impl Into<String>, error: io::Error) -> Self {        ReadonlyIndexLoadError::Other {            name: name.into(),            error,        }    }     /// Returns true if the underlying error suggests data corruption.    pub(super) fn is_corrupt_or_not_found(&self) -> bool {        match self {            ReadonlyIndexLoadError::UnexpectedVersion { .. } => true,            ReadonlyIndexLoadError::Other { name: _, error } => {                // If the parent file name field is corrupt, the file wouldn't be found.                // And there's no need to distinguish it from an empty file.                matches!(                    error.kind(),                    io::ErrorKind::NotFound                        | io::ErrorKind::InvalidData                        | io::ErrorKind::UnexpectedEof                )            }        }    }} /// Current format version of the index segment file.pub(super) const INDEX_SEGMENT_FILE_FORMAT_VERSION: u32 = 6; /// If set, the value is stored in the overflow table.pub(super) const OVERFLOW_FLAG: u32 = 0x8000_0000; /// Global index position of parent entry, or overflow pointer.#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]struct ParentIndexPosition(u32); impl ParentIndexPosition {    fn as_inlined(self) -> Option<IndexPosition> {        (self.0 & OVERFLOW_FLAG == 0).then_some(IndexPosition(self.0))    }     fn as_overflow(self) -> Option<u32> {        (self.0 & OVERFLOW_FLAG != 0).then_some(!self.0)    }} /// Local position of entry pointed by change id, or overflow pointer.#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]struct ChangeLocalPosition(u32); impl ChangeLocalPosition {    fn as_inlined(self) -> Option<LocalPosition> {        (self.0 & OVERFLOW_FLAG == 0).then_some(LocalPosition(self.0))    }     fn as_overflow(self) -> Option<u32> {        (self.0 & OVERFLOW_FLAG != 0).then_some(!self.0)    }} /// Lengths of fields to be serialized.#[derive(Clone, Copy, Debug)]pub(super) struct FieldLengths {    pub commit_id: usize,    pub change_id: usize,} struct CommitGraphEntry<'a> {    data: &'a [u8],} // TODO: Add pointers to ancestors further back, like a skip list. Clear the// lowest set bit to determine which generation number the pointers point to.impl CommitGraphEntry<'_> {    fn size(commit_id_length: usize) -> usize {        16 + commit_id_length    }     fn generation_number(&self) -> u32 {        u32::from_le_bytes(self.data[0..4].try_into().unwrap())    }     fn parent1_pos_or_overflow_pos(&self) -> ParentIndexPosition {        ParentIndexPosition(u32::from_le_bytes(self.data[4..8].try_into().unwrap()))    }     fn parent2_pos_or_overflow_len(&self) -> ParentIndexPosition {        ParentIndexPosition(u32::from_le_bytes(self.data[8..12].try_into().unwrap()))    }     fn change_id_lookup_pos(&self) -> u32 {        u32::from_le_bytes(self.data[12..16].try_into().unwrap())    }     fn commit_id(&self) -> CommitId {        CommitId::from_bytes(self.commit_id_bytes())    }     // might be better to add borrowed version of CommitId    fn commit_id_bytes(&self) -> &[u8] {        &self.data[16..]    }} /// Commit index segment backed by immutable file.////// File format:/// ```text/// u32: file format version/// u32: parent segment file name length (0 means root)/// <length number of bytes>: parent segment file name////// u32: number of local commit entries/// u32: number of local change ids/// u32: number of overflow parent entries/// u32: number of overflow change id positions/// for each entry, in some topological order with parents first:///   u32: generation number///   if number of parents <= 2:///     u32: (< 0x8000_0000) global index position for parent 1///          (==0xffff_ffff) no parent 1///     u32: (< 0x8000_0000) global index position for parent 2///          (==0xffff_ffff) no parent 2///   else:///     u32: (>=0x8000_0000) position in the overflow table, bit-negated///     u32: (>=0x8000_0000) number of parents (in the overflow table), bit-negated///   u32: change id position in the sorted change ids table///   <commit id length number of bytes>: commit id/// for each entry, sorted by commit id:///   u32: local position in the graph entries table/// for each entry, sorted by change id:///   <change id length number of bytes>: change id/// for each entry, sorted by change id:///   if number of associated commits == 1:///     u32: (< 0x8000_0000) local position in the graph entries table///   else:///     u32: (>=0x8000_0000) position in the overflow table, bit-negated/// for each overflow parent:///   u32: global index position/// for each overflow change id entry:///   u32: local position in the graph entries table/// ```////// Note that u32 fields are 4-byte aligned so long as the parent file name/// (which is hexadecimal hash) and commit/change ids aren't of exotic length.// TODO: replace the table by a trie so we don't have to repeat the full commit//       ids// TODO: add a fanout table like git's commit graph has?pub(super) struct ReadonlyIndexSegment {    parent_file: Option<Arc<ReadonlyIndexSegment>>,    num_parent_commits: u32,    name: String,    field_lengths: FieldLengths,    // Number of commits not counting the parent file    num_local_commits: u32,    num_local_change_ids: u32,    num_change_overflow_entries: u32,    // Base data offsets in bytes:    commit_lookup_base: usize,    change_id_table_base: usize,    change_pos_table_base: usize,    parent_overflow_base: usize,    change_overflow_base: usize,    data: Vec<u8>,} impl Debug for ReadonlyIndexSegment {    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {        f.debug_struct("ReadonlyIndexSegment")            .field("name", &self.name)            .field("parent_file", &self.parent_file)            .finish()    }} impl ReadonlyIndexSegment {    /// Loads both parent segments and local entries from the given file `name`.    pub(super) fn load(        dir: &Path,        name: String,        lengths: FieldLengths,    ) -> Result<Arc<ReadonlyIndexSegment>, ReadonlyIndexLoadError> {        let mut file = File::open(dir.join(&name))            .map_err(|err| ReadonlyIndexLoadError::from_io_err(&name, err))?;        Self::load_from(&mut file, dir, name, lengths)    }     /// Loads both parent segments and local entries from the given `file`.    pub(super) fn load_from(        file: &mut dyn Read,        dir: &Path,        name: String,        lengths: FieldLengths,    ) -> Result<Arc<ReadonlyIndexSegment>, ReadonlyIndexLoadError> {        let from_io_err = |err| ReadonlyIndexLoadError::from_io_err(&name, err);        let read_u32 = |file: &mut dyn Read| {            let mut buf = [0; 4];            file.read_exact(&mut buf).map_err(from_io_err)?;            Ok(u32::from_le_bytes(buf))        };        let format_version = read_u32(file)?;        if format_version != INDEX_SEGMENT_FILE_FORMAT_VERSION {            return Err(ReadonlyIndexLoadError::UnexpectedVersion {                found_version: format_version,                expected_version: INDEX_SEGMENT_FILE_FORMAT_VERSION,            });        }        let parent_filename_len = read_u32(file)?;        let maybe_parent_file = if parent_filename_len > 0 {            let mut parent_filename_bytes = vec![0; parent_filename_len as usize];            file.read_exact(&mut parent_filename_bytes)                .map_err(from_io_err)?;            let parent_filename = String::from_utf8(parent_filename_bytes).map_err(|_| {                ReadonlyIndexLoadError::invalid_data(&name, "parent file name is not valid UTF-8")            })?;            let parent_file = ReadonlyIndexSegment::load(dir, parent_filename, lengths)?;            Some(parent_file)        } else {            None        };        Self::load_with_parent_file(file, name, maybe_parent_file, lengths)    }     /// Loads local entries from the given `file`, returns new segment linked to    /// the given `parent_file`.    pub(super) fn load_with_parent_file(        file: &mut dyn Read,        name: String,        parent_file: Option<Arc<ReadonlyIndexSegment>>,        lengths: FieldLengths,    ) -> Result<Arc<ReadonlyIndexSegment>, ReadonlyIndexLoadError> {        let from_io_err = |err| ReadonlyIndexLoadError::from_io_err(&name, err);        let read_u32 = |file: &mut dyn Read| {            let mut buf = [0; 4];            file.read_exact(&mut buf).map_err(from_io_err)?;            Ok(u32::from_le_bytes(buf))        };        let num_parent_commits = parent_file            .as_ref()            .map_or(0, |segment| segment.as_composite().num_commits());        let num_local_commits = read_u32(file)?;        let num_local_change_ids = read_u32(file)?;        let num_parent_overflow_entries = read_u32(file)?;        let num_change_overflow_entries = read_u32(file)?;        let mut data = vec![];        file.read_to_end(&mut data).map_err(from_io_err)?;         let commit_graph_entry_size = CommitGraphEntry::size(lengths.commit_id);        let graph_size = (num_local_commits as usize) * commit_graph_entry_size;        let commit_lookup_size = (num_local_commits as usize) * 4;        let change_id_table_size = (num_local_change_ids as usize) * lengths.change_id;        let change_pos_table_size = (num_local_change_ids as usize) * 4;        let parent_overflow_size = (num_parent_overflow_entries as usize) * 4;        let change_overflow_size = (num_change_overflow_entries as usize) * 4;         let graph_base = 0;        let commit_lookup_base = graph_base + graph_size;        let change_id_table_base = commit_lookup_base + commit_lookup_size;        let change_pos_table_base = change_id_table_base + change_id_table_size;        let parent_overflow_base = change_pos_table_base + change_pos_table_size;        let change_overflow_base = parent_overflow_base + parent_overflow_size;        let expected_size = change_overflow_base + change_overflow_size;         if data.len() != expected_size {            return Err(ReadonlyIndexLoadError::invalid_data(                name,                "unexpected data length",            ));        }         Ok(Arc::new(ReadonlyIndexSegment {            parent_file,            num_parent_commits,            name,            field_lengths: lengths,            num_local_commits,            num_local_change_ids,            num_change_overflow_entries,            commit_lookup_base,            change_id_table_base,            change_pos_table_base,            parent_overflow_base,            change_overflow_base,            data,        }))    }     pub(super) fn as_composite(&self) -> &CompositeIndex {        CompositeIndex::new(self)    }     pub(super) fn name(&self) -> &str {        &self.name    }     pub(super) fn field_lengths(&self) -> FieldLengths {        self.field_lengths    }     fn graph_entry(&self, local_pos: LocalPosition) -> CommitGraphEntry<'_> {        let table = &self.data[..self.commit_lookup_base];        let entry_size = CommitGraphEntry::size(self.field_lengths.commit_id);        let offset = (local_pos.0 as usize) * entry_size;        CommitGraphEntry {            data: &table[offset..][..entry_size],        }    }     fn commit_lookup_pos(&self, lookup_pos: u32) -> LocalPosition {        let table = &self.data[self.commit_lookup_base..self.change_id_table_base];        let offset = (lookup_pos as usize) * 4;        LocalPosition(u32::from_le_bytes(table[offset..][..4].try_into().unwrap()))    }     fn change_lookup_id(&self, lookup_pos: u32) -> ChangeId {        ChangeId::from_bytes(self.change_lookup_id_bytes(lookup_pos))    }     // might be better to add borrowed version of ChangeId    fn change_lookup_id_bytes(&self, lookup_pos: u32) -> &[u8] {        let table = &self.data[self.change_id_table_base..self.change_pos_table_base];        let offset = (lookup_pos as usize) * self.field_lengths.change_id;        &table[offset..][..self.field_lengths.change_id]    }     fn change_lookup_pos(&self, lookup_pos: u32) -> ChangeLocalPosition {        let table = &self.data[self.change_pos_table_base..self.parent_overflow_base];        let offset = (lookup_pos as usize) * 4;        ChangeLocalPosition(u32::from_le_bytes(table[offset..][..4].try_into().unwrap()))    }     fn overflow_parents(&self, overflow_pos: u32, num_parents: u32) -> SmallIndexPositionsVec {        let table = &self.data[self.parent_overflow_base..self.change_overflow_base];        let offset = (overflow_pos as usize) * 4;        let size = (num_parents as usize) * 4;        table[offset..][..size]            .chunks_exact(4)            .map(|chunk| IndexPosition(u32::from_le_bytes(chunk.try_into().unwrap())))            .collect()    }     /// Scans graph entry positions stored in the overflow change ids table.    fn overflow_changes_from(        &self,        overflow_pos: u32,    ) -> impl Iterator<Item = LocalPosition> + use<'_> {        let table = &self.data[self.change_overflow_base..];        let offset = (overflow_pos as usize) * 4;        table[offset..]            .chunks_exact(4)            .map(|chunk| LocalPosition(u32::from_le_bytes(chunk.try_into().unwrap())))    }     /// Binary searches commit id by `prefix`. Returns the lookup position.    fn commit_id_byte_prefix_to_lookup_pos(&self, prefix: &[u8]) -> PositionLookupResult {        binary_search_pos_by(self.num_local_commits, |pos| {            let local_pos = self.commit_lookup_pos(pos);            let entry = self.graph_entry(local_pos);            entry.commit_id_bytes().cmp(prefix)        })    }     /// Binary searches change id by `prefix`. Returns the lookup position.    fn change_id_byte_prefix_to_lookup_pos(&self, prefix: &[u8]) -> PositionLookupResult {        binary_search_pos_by(self.num_local_change_ids, |pos| {            let change_id_bytes = self.change_lookup_id_bytes(pos);            change_id_bytes.cmp(prefix)        })    }} impl IndexSegment for ReadonlyIndexSegment {    fn num_parent_commits(&self) -> u32 {        self.num_parent_commits    }     fn num_local_commits(&self) -> u32 {        self.num_local_commits    }     fn parent_file(&self) -> Option<&Arc<ReadonlyIndexSegment>> {        self.parent_file.as_ref()    }     fn name(&self) -> Option<String> {        Some(self.name.clone())    }     fn commit_id_to_pos(&self, commit_id: &CommitId) -> Option<LocalPosition> {        self.commit_id_byte_prefix_to_lookup_pos(commit_id.as_bytes())            .ok()            .map(|pos| self.commit_lookup_pos(pos))    }     fn resolve_neighbor_commit_ids(        &self,        commit_id: &CommitId,    ) -> (Option<CommitId>, Option<CommitId>) {        self.commit_id_byte_prefix_to_lookup_pos(commit_id.as_bytes())            .map_neighbors(|pos| {                let local_pos = self.commit_lookup_pos(pos);                let entry = self.graph_entry(local_pos);                entry.commit_id()            })    }     fn resolve_commit_id_prefix(&self, prefix: &HexPrefix) -> PrefixResolution<CommitId> {        self.commit_id_byte_prefix_to_lookup_pos(prefix.min_prefix_bytes())            .prefix_matches(prefix, |pos| {                let local_pos = self.commit_lookup_pos(pos);                let entry = self.graph_entry(local_pos);                entry.commit_id()            })            .map(|(id, _)| id)    }     fn resolve_neighbor_change_ids(        &self,        change_id: &ChangeId,    ) -> (Option<ChangeId>, Option<ChangeId>) {        self.change_id_byte_prefix_to_lookup_pos(change_id.as_bytes())

Lines 1–500 of 732. Load more