// 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. #![expect(missing_docs)] use std::cmp::Ordering;use std::collections::HashSet;use std::fmt;use std::fmt::Debug;use std::fs::File;use std::io;use std::io::Read;use std::iter;use std::ops::Range;use std::path::Path;use std::sync::Arc; use itertools::Itertools as _;use smallvec::smallvec;use thiserror::Error; use super::changed_path::CompositeChangedPathIndex;use super::composite::AsCompositeIndex;use super::composite::ChangeIdIndexImpl;use super::composite::CommitIndexSegment;use super::composite::CommitIndexSegmentId;use super::composite::CompositeCommitIndex;use super::composite::CompositeIndex;use super::entry::GlobalCommitPosition;use super::entry::LocalCommitPosition;use super::entry::SmallGlobalCommitPositionsVec;use super::entry::SmallLocalCommitPositionsVec;use super::mutable::DefaultMutableIndex;use super::revset_engine;use super::revset_engine::RevsetImpl;use crate::backend::ChangeId;use crate::backend::CommitId;use crate::graph::GraphNode;use crate::index::ChangeIdIndex;use crate::index::Index;use crate::index::IndexResult;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::repo_path::RepoPathBuf;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 {kind} index version")]    UnexpectedVersion {        /// Index type.        kind: &'static str,        found_version: u32,        expected_version: u32,    },    #[error("Failed to load {kind} index file '{name}'")]    Other {        /// Index type.        kind: &'static str,        /// Index file name.        name: String,        /// Underlying error.        #[source]        error: io::Error,    },} impl ReadonlyIndexLoadError {    pub(super) fn invalid_data(        kind: &'static str,        name: impl Into<String>,        error: impl Into<Box<dyn std::error::Error + Send + Sync>>,    ) -> Self {        Self::from_io_err(            kind,            name,            io::Error::new(io::ErrorKind::InvalidData, error),        )    }     pub(super) fn from_io_err(        kind: &'static str,        name: impl Into<String>,        error: io::Error,    ) -> Self {        Self::Other {            kind,            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 {            Self::UnexpectedVersion { .. } => true,            Self::Other { 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 commit index segment file.pub(super) const COMMIT_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<GlobalCommitPosition> {        (self.0 & OVERFLOW_FLAG == 0).then_some(GlobalCommitPosition(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<LocalCommitPosition> {        (self.0 & OVERFLOW_FLAG == 0).then_some(LocalCommitPosition(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 ReadonlyCommitIndexSegment {    parent_file: Option<Arc<Self>>,    num_parent_commits: u32,    id: CommitIndexSegmentId,    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 ReadonlyCommitIndexSegment {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {        f.debug_struct("ReadonlyCommitIndexSegment")            .field("id", &self.id)            .field("parent_file", &self.parent_file)            .finish_non_exhaustive()    }} impl ReadonlyCommitIndexSegment {    /// Loads both parent segments and local entries from the given file `name`.    pub(super) fn load(        dir: &Path,        id: CommitIndexSegmentId,        lengths: FieldLengths,    ) -> Result<Arc<Self>, ReadonlyIndexLoadError> {        let mut file = File::open(dir.join(id.hex()))            .map_err(|err| ReadonlyIndexLoadError::from_io_err("commit", id.hex(), err))?;        Self::load_from(&mut file, dir, id, lengths)    }     /// Loads both parent segments and local entries from the given `file`.    pub(super) fn load_from(        file: &mut dyn Read,        dir: &Path,        id: CommitIndexSegmentId,        lengths: FieldLengths,    ) -> Result<Arc<Self>, ReadonlyIndexLoadError> {        let from_io_err = |err| ReadonlyIndexLoadError::from_io_err("commit", id.hex(), 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 != COMMIT_INDEX_SEGMENT_FILE_FORMAT_VERSION {            return Err(ReadonlyIndexLoadError::UnexpectedVersion {                kind: "commit",                found_version: format_version,                expected_version: COMMIT_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_file_id = CommitIndexSegmentId::try_from_hex(parent_filename_bytes)                .ok_or_else(|| {                    ReadonlyIndexLoadError::invalid_data(                        "commit",                        id.hex(),                        "parent file name is not valid hex",                    )                })?;            let parent_file = Self::load(dir, parent_file_id, lengths)?;            Some(parent_file)        } else {            None        };        Self::load_with_parent_file(file, id, 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,        id: CommitIndexSegmentId,        parent_file: Option<Arc<Self>>,        lengths: FieldLengths,    ) -> Result<Arc<Self>, ReadonlyIndexLoadError> {        let from_io_err = |err| ReadonlyIndexLoadError::from_io_err("commit", id.hex(), 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(                "commit",                id.hex(),                "unexpected data length",            ));        }         Ok(Arc::new(Self {            parent_file,            num_parent_commits,            id,            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) -> &CompositeCommitIndex {        CompositeCommitIndex::new(self)    }     pub(super) fn id(&self) -> &CommitIndexSegmentId {        &self.id    }     pub(super) fn field_lengths(&self) -> FieldLengths {        self.field_lengths    }     fn graph_entry(&self, local_pos: LocalCommitPosition) -> 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) -> LocalCommitPosition {        let table = &self.data[self.commit_lookup_base..self.change_id_table_base];        let offset = (lookup_pos as usize) * 4;        LocalCommitPosition(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,    ) -> SmallGlobalCommitPositionsVec {        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;        let (chunks, _remainder) = table[offset..][..size].as_chunks();        chunks            .iter()            .map(|&chunk: &[u8; 4]| GlobalCommitPosition(u32::from_le_bytes(chunk)))            .collect()    }     /// Scans graph entry positions stored in the overflow change ids table.    fn overflow_changes_from(        &self,        overflow_pos: u32,    ) -> impl Iterator<Item = LocalCommitPosition> {        let table = &self.data[self.change_overflow_base..];        let offset = (overflow_pos as usize) * 4;        let (chunks, _remainder) = table[offset..].as_chunks();        chunks            .iter()            .map(|&chunk: &[u8; 4]| LocalCommitPosition(u32::from_le_bytes(chunk)))    }     /// 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 CommitIndexSegment for ReadonlyCommitIndexSegment {    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<ReadonlyCommitIndexSegment>> {        self.parent_file.as_ref()    }     fn commit_id_to_pos(&self, commit_id: &CommitId) -> Option<LocalCommitPosition> {

Lines 1–500 of 900. Load more