| Alphare |
| hg-reviewers |
Prevent building Index every time it is needed. It was a bad idea anyway.
When Index::new will return Result it will avoid things like Revlog::len
returning Result<usize> instead of usize.
| Automatic diff as part of commit; lint not applicable. |
| Automatic diff as part of commit; unit tests not applicable. |
In D9106#136640, @Alphare wrote:Yep, this is a lot better. Does this affect the benchmarks at all?
The whole series improves rhg cat by 2ms
| Path | Packages | |||
|---|---|---|---|---|
| M | rust/hg-core/src/revlog/index.rs (67 lines) | |||
| M | rust/hg-core/src/revlog/revlog.rs (171 lines) |
| use std::ops::Deref; | |||||
| use byteorder::{BigEndian, ByteOrder}; | use byteorder::{BigEndian, ByteOrder}; | ||||
| use crate::revlog::{Revision, NULL_REVISION}; | use crate::revlog::{Revision, NULL_REVISION}; | ||||
| pub const INDEX_ENTRY_SIZE: usize = 64; | pub const INDEX_ENTRY_SIZE: usize = 64; | ||||
| /// A Revlog index | /// A Revlog index | ||||
| #[derive(Debug)] | pub struct Index { | ||||
| pub struct Index<'a> { | bytes: Box<dyn Deref<Target = [u8]> + Send>, | ||||
| bytes: &'a [u8], | |||||
| /// Offsets of starts of index blocks. | /// Offsets of starts of index blocks. | ||||
| /// Only needed when the index is interleaved with data. | /// Only needed when the index is interleaved with data. | ||||
| offsets: Option<Vec<usize>>, | offsets: Option<Vec<usize>>, | ||||
| } | } | ||||
| impl<'a> Index<'a> { | impl Index { | ||||
| /// Create an index from bytes. | /// Create an index from bytes. | ||||
| /// Calculate the start of each entry when is_inline is true. | /// Calculate the start of each entry when is_inline is true. | ||||
| pub fn new(bytes: &'a [u8], is_inline: bool) -> Self { | pub fn new(bytes: Box<dyn Deref<Target = [u8]> + Send>) -> Self { | ||||
| if is_inline { | if is_inline(&bytes) { | ||||
| let mut offset: usize = 0; | let mut offset: usize = 0; | ||||
| let mut offsets = Vec::new(); | let mut offsets = Vec::new(); | ||||
| while offset + INDEX_ENTRY_SIZE <= bytes.len() { | while offset + INDEX_ENTRY_SIZE <= bytes.len() { | ||||
| offsets.push(offset); | offsets.push(offset); | ||||
| let end = offset + INDEX_ENTRY_SIZE; | let end = offset + INDEX_ENTRY_SIZE; | ||||
| let entry = IndexEntry { | let entry = IndexEntry { | ||||
| bytes: &bytes[offset..end], | bytes: &bytes[offset..end], | ||||
| } else { | } else { | ||||
| Self { | Self { | ||||
| bytes, | bytes, | ||||
| offsets: None, | offsets: None, | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| /// Value of the inline flag. | |||||
| pub fn is_inline(&self) -> bool { | |||||
| is_inline(&self.bytes) | |||||
| } | |||||
| /// Return a slice of bytes if `revlog` is inline. Panic if not. | |||||
| pub fn data(&self, start: usize, end: usize) -> &[u8] { | |||||
| if !self.is_inline() { | |||||
| panic!("tried to access data in the index of a revlog that is not inline"); | |||||
| } | |||||
| &self.bytes[start..end] | |||||
| } | |||||
| /// Return number of entries of the revlog index. | /// Return number of entries of the revlog index. | ||||
| pub fn len(&self) -> usize { | pub fn len(&self) -> usize { | ||||
| if let Some(offsets) = &self.offsets { | if let Some(offsets) = &self.offsets { | ||||
| offsets.len() | offsets.len() | ||||
| } else { | } else { | ||||
| self.bytes.len() / INDEX_ENTRY_SIZE | self.bytes.len() / INDEX_ENTRY_SIZE | ||||
| } | } | ||||
| } | } | ||||
| /// | /// | ||||
| /// Currently, SHA-1 is used and only the first 20 bytes of this field | /// Currently, SHA-1 is used and only the first 20 bytes of this field | ||||
| /// are used. | /// are used. | ||||
| pub fn hash(&self) -> &[u8] { | pub fn hash(&self) -> &[u8] { | ||||
| &self.bytes[32..52] | &self.bytes[32..52] | ||||
| } | } | ||||
| } | } | ||||
| /// Value of the inline flag. | |||||
| pub fn is_inline(index_bytes: &[u8]) -> bool { | |||||
| match &index_bytes[0..=1] { | |||||
| [0, 0] | [0, 2] => false, | |||||
| _ => true, | |||||
| } | |||||
| } | |||||
| #[cfg(test)] | #[cfg(test)] | ||||
| mod tests { | mod tests { | ||||
| use super::*; | use super::*; | ||||
| #[cfg(test)] | #[cfg(test)] | ||||
| #[derive(Debug, Copy, Clone)] | #[derive(Debug, Copy, Clone)] | ||||
| pub struct IndexEntryBuilder { | pub struct IndexEntryBuilder { | ||||
| is_first: bool, | is_first: bool, | ||||
| bytes.extend(&self.compressed_len.to_be_bytes()[4..]); | bytes.extend(&self.compressed_len.to_be_bytes()[4..]); | ||||
| bytes.extend(&self.uncompressed_len.to_be_bytes()[4..]); | bytes.extend(&self.uncompressed_len.to_be_bytes()[4..]); | ||||
| bytes.extend(&self.base_revision.to_be_bytes()); | bytes.extend(&self.base_revision.to_be_bytes()); | ||||
| bytes | bytes | ||||
| } | } | ||||
| } | } | ||||
| #[test] | #[test] | ||||
| fn is_not_inline_when_no_inline_flag_test() { | |||||
| let bytes = IndexEntryBuilder::new() | |||||
| .is_first(true) | |||||
| .with_general_delta(false) | |||||
| .with_inline(false) | |||||
| .build(); | |||||
| assert_eq!(is_inline(&bytes), false) | |||||
| } | |||||
| #[test] | |||||
| fn is_inline_when_inline_flag_test() { | |||||
| let bytes = IndexEntryBuilder::new() | |||||
| .is_first(true) | |||||
| .with_general_delta(false) | |||||
| .with_inline(true) | |||||
| .build(); | |||||
| assert_eq!(is_inline(&bytes), true) | |||||
| } | |||||
| #[test] | |||||
| fn is_inline_when_inline_and_generaldelta_flags_test() { | |||||
| let bytes = IndexEntryBuilder::new() | |||||
| .is_first(true) | |||||
| .with_general_delta(true) | |||||
| .with_inline(true) | |||||
| .build(); | |||||
| assert_eq!(is_inline(&bytes), true) | |||||
| } | |||||
| #[test] | |||||
| fn test_offset() { | fn test_offset() { | ||||
| let bytes = IndexEntryBuilder::new().with_offset(1).build(); | let bytes = IndexEntryBuilder::new().with_offset(1).build(); | ||||
| let entry = IndexEntry { | let entry = IndexEntry { | ||||
| bytes: &bytes, | bytes: &bytes, | ||||
| offset_override: None, | offset_override: None, | ||||
| }; | }; | ||||
| assert_eq!(entry.offset(), 1) | assert_eq!(entry.offset(), 1) | ||||
| Ok(mmap) | Ok(mmap) | ||||
| } | } | ||||
| /// Read only implementation of revlog. | /// Read only implementation of revlog. | ||||
| pub struct Revlog { | pub struct Revlog { | ||||
| /// When index and data are not interleaved: bytes of the revlog index. | /// When index and data are not interleaved: bytes of the revlog index. | ||||
| /// When index and data are interleaved: bytes of the revlog index and | /// When index and data are interleaved: bytes of the revlog index and | ||||
| /// data. | /// data. | ||||
| index_bytes: Box<dyn Deref<Target = [u8]> + Send>, | index: Index, | ||||
| /// When index and data are not interleaved: bytes of the revlog data | /// When index and data are not interleaved: bytes of the revlog data | ||||
| data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>, | data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>, | ||||
| } | } | ||||
| impl Revlog { | impl Revlog { | ||||
| /// Open a revlog index file. | /// Open a revlog index file. | ||||
| /// | /// | ||||
| /// It will also open the associated data file if index and data are not | /// It will also open the associated data file if index and data are not | ||||
| /// interleaved. | /// interleaved. | ||||
| #[timed] | #[timed] | ||||
| pub fn open(index_path: &Path) -> Result<Self, RevlogError> { | pub fn open(index_path: &Path) -> Result<Self, RevlogError> { | ||||
| let index_mmap = | let index_mmap = | ||||
| mmap_open(&index_path).map_err(RevlogError::IoError)?; | mmap_open(&index_path).map_err(RevlogError::IoError)?; | ||||
| let version = get_version(&index_mmap); | let version = get_version(&index_mmap); | ||||
| if version != 1 { | if version != 1 { | ||||
| return Err(RevlogError::UnsuportedVersion(version)); | return Err(RevlogError::UnsuportedVersion(version)); | ||||
| } | } | ||||
| let is_inline = is_inline(&index_mmap); | let index = Index::new(Box::new(index_mmap)); | ||||
| let index_bytes = Box::new(index_mmap); | |||||
| // TODO load data only when needed // | // TODO load data only when needed // | ||||
| // type annotation required | // type annotation required | ||||
| // won't recognize Mmap as Deref<Target = [u8]> | // won't recognize Mmap as Deref<Target = [u8]> | ||||
| let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> = | let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> = | ||||
| if is_inline { | if index.is_inline() { | ||||
| None | None | ||||
| } else { | } else { | ||||
| let data_path = index_path.with_extension("d"); | let data_path = index_path.with_extension("d"); | ||||
| let data_mmap = | let data_mmap = | ||||
| mmap_open(&data_path).map_err(RevlogError::IoError)?; | mmap_open(&data_path).map_err(RevlogError::IoError)?; | ||||
| Some(Box::new(data_mmap)) | Some(Box::new(data_mmap)) | ||||
| }; | }; | ||||
| Ok(Revlog { | Ok(Revlog { index, data_bytes }) | ||||
| index_bytes, | |||||
| data_bytes, | |||||
| }) | |||||
| } | } | ||||
| /// Return number of entries of the `Revlog`. | /// Return number of entries of the `Revlog`. | ||||
| pub fn len(&self) -> usize { | pub fn len(&self) -> usize { | ||||
| self.index().len() | self.index.len() | ||||
| } | } | ||||
| /// Returns `true` if the `Revlog` has zero `entries`. | /// Returns `true` if the `Revlog` has zero `entries`. | ||||
| pub fn is_empty(&self) -> bool { | pub fn is_empty(&self) -> bool { | ||||
| self.index().is_empty() | self.index.is_empty() | ||||
| } | } | ||||
| /// Return the full data associated to a node. | /// Return the full data associated to a node. | ||||
| #[timed] | #[timed] | ||||
| pub fn get_node_rev(&self, node: &[u8]) -> Result<Revision, RevlogError> { | pub fn get_node_rev(&self, node: &[u8]) -> Result<Revision, RevlogError> { | ||||
| let index = self.index(); | |||||
| // This is brute force. But it is fast enough for now. | // This is brute force. But it is fast enough for now. | ||||
| // Optimization will come later. | // Optimization will come later. | ||||
| for rev in (0..self.len() as Revision).rev() { | for rev in (0..self.len() as Revision).rev() { | ||||
| let index_entry = | let index_entry = | ||||
| index.get_entry(rev).ok_or(RevlogError::Corrupted)?; | self.index.get_entry(rev).ok_or(RevlogError::Corrupted)?; | ||||
| if node == index_entry.hash() { | if node == index_entry.hash() { | ||||
| return Ok(rev); | return Ok(rev); | ||||
| } | } | ||||
| } | } | ||||
| Err(RevlogError::InvalidRevision) | Err(RevlogError::InvalidRevision) | ||||
| } | } | ||||
| /// Return the full data associated to a revision. | /// Return the full data associated to a revision. | ||||
| while let Some(base_rev) = entry.base_rev { | while let Some(base_rev) = entry.base_rev { | ||||
| delta_chain.push(entry); | delta_chain.push(entry); | ||||
| entry = self | entry = self | ||||
| .get_entry(base_rev) | .get_entry(base_rev) | ||||
| .map_err(|_| RevlogError::Corrupted)?; | .map_err(|_| RevlogError::Corrupted)?; | ||||
| } | } | ||||
| // TODO do not look twice in the index | // TODO do not look twice in the index | ||||
| let index = self.index(); | let index_entry = self | ||||
| let index_entry = | .index | ||||
| index.get_entry(rev).ok_or(RevlogError::InvalidRevision)?; | .get_entry(rev) | ||||
| .ok_or(RevlogError::InvalidRevision)?; | |||||
| let data: Vec<u8> = if delta_chain.is_empty() { | let data: Vec<u8> = if delta_chain.is_empty() { | ||||
| entry.data()?.into() | entry.data()?.into() | ||||
| } else { | } else { | ||||
| Revlog::build_data_from_deltas(entry, &delta_chain)? | Revlog::build_data_from_deltas(entry, &delta_chain)? | ||||
| }; | }; | ||||
| if self.check_hash( | if self.check_hash( | ||||
| /// Check the hash of some given data against the recorded hash. | /// Check the hash of some given data against the recorded hash. | ||||
| pub fn check_hash( | pub fn check_hash( | ||||
| &self, | &self, | ||||
| p1: Revision, | p1: Revision, | ||||
| p2: Revision, | p2: Revision, | ||||
| expected: &[u8], | expected: &[u8], | ||||
| data: &[u8], | data: &[u8], | ||||
| ) -> bool { | ) -> bool { | ||||
| let index = self.index(); | let e1 = self.index.get_entry(p1); | ||||
| let e1 = index.get_entry(p1); | |||||
| let h1 = match e1 { | let h1 = match e1 { | ||||
| Some(ref entry) => entry.hash(), | Some(ref entry) => entry.hash(), | ||||
| None => &NULL_NODE_ID, | None => &NULL_NODE_ID, | ||||
| }; | }; | ||||
| let e2 = index.get_entry(p2); | let e2 = self.index.get_entry(p2); | ||||
| let h2 = match e2 { | let h2 = match e2 { | ||||
| Some(ref entry) => entry.hash(), | Some(ref entry) => entry.hash(), | ||||
| None => &NULL_NODE_ID, | None => &NULL_NODE_ID, | ||||
| }; | }; | ||||
| hash(data, &h1, &h2).as_slice() == expected | hash(data, &h1, &h2).as_slice() == expected | ||||
| } | } | ||||
| .map(RevlogEntry::data) | .map(RevlogEntry::data) | ||||
| .collect::<Result<Vec<Cow<'_, [u8]>>, RevlogError>>()?; | .collect::<Result<Vec<Cow<'_, [u8]>>, RevlogError>>()?; | ||||
| let patches: Vec<_> = | let patches: Vec<_> = | ||||
| deltas.iter().map(|d| patch::PatchList::new(d)).collect(); | deltas.iter().map(|d| patch::PatchList::new(d)).collect(); | ||||
| let patch = patch::fold_patch_lists(&patches); | let patch = patch::fold_patch_lists(&patches); | ||||
| Ok(patch.apply(&snapshot)) | Ok(patch.apply(&snapshot)) | ||||
| } | } | ||||
| /// Return the revlog index. | |||||
| pub fn index(&self) -> Index { | |||||
| let is_inline = self.data_bytes.is_none(); | |||||
| Index::new(&self.index_bytes, is_inline) | |||||
| } | |||||
| /// Return the revlog data. | /// Return the revlog data. | ||||
| fn data(&self) -> &[u8] { | fn data(&self) -> &[u8] { | ||||
| match self.data_bytes { | match self.data_bytes { | ||||
| Some(ref data_bytes) => &data_bytes, | Some(ref data_bytes) => &data_bytes, | ||||
| None => &self.index_bytes, | None => panic!( | ||||
| "forgot to load the data or trying to access inline data" | |||||
| ), | |||||
| } | } | ||||
| } | } | ||||
| /// Get an entry of the revlog. | /// Get an entry of the revlog. | ||||
| fn get_entry(&self, rev: Revision) -> Result<RevlogEntry, RevlogError> { | fn get_entry(&self, rev: Revision) -> Result<RevlogEntry, RevlogError> { | ||||
| let index = self.index(); | let index_entry = self | ||||
| let index_entry = | .index | ||||
| index.get_entry(rev).ok_or(RevlogError::InvalidRevision)?; | .get_entry(rev) | ||||
| .ok_or(RevlogError::InvalidRevision)?; | |||||
| let start = index_entry.offset(); | let start = index_entry.offset(); | ||||
| let end = start + index_entry.compressed_len(); | let end = start + index_entry.compressed_len(); | ||||
| let data = if self.index.is_inline() { | |||||
| self.index.data(start, end) | |||||
| } else { | |||||
| &self.data()[start..end] | |||||
| }; | |||||
| let entry = RevlogEntry { | let entry = RevlogEntry { | ||||
| rev, | rev, | ||||
| bytes: &self.data()[start..end], | bytes: data, | ||||
| compressed_len: index_entry.compressed_len(), | compressed_len: index_entry.compressed_len(), | ||||
| uncompressed_len: index_entry.uncompressed_len(), | uncompressed_len: index_entry.uncompressed_len(), | ||||
| base_rev: if index_entry.base_revision() == rev { | base_rev: if index_entry.base_revision() == rev { | ||||
| None | None | ||||
| } else { | } else { | ||||
| Some(index_entry.base_revision()) | Some(index_entry.base_revision()) | ||||
| }, | }, | ||||
| }; | }; | ||||
| /// Tell if the entry is a snapshot or a delta | /// Tell if the entry is a snapshot or a delta | ||||
| /// (influences on decompression). | /// (influences on decompression). | ||||
| fn is_delta(&self) -> bool { | fn is_delta(&self) -> bool { | ||||
| self.base_rev.is_some() | self.base_rev.is_some() | ||||
| } | } | ||||
| } | } | ||||
| /// Value of the inline flag. | |||||
| pub fn is_inline(index_bytes: &[u8]) -> bool { | |||||
| match &index_bytes[0..=1] { | |||||
| [0, 0] | [0, 2] => false, | |||||
| _ => true, | |||||
| } | |||||
| } | |||||
| /// Format version of the revlog. | /// Format version of the revlog. | ||||
| pub fn get_version(index_bytes: &[u8]) -> u16 { | pub fn get_version(index_bytes: &[u8]) -> u16 { | ||||
| BigEndian::read_u16(&index_bytes[2..=3]) | BigEndian::read_u16(&index_bytes[2..=3]) | ||||
| } | } | ||||
| /// Calculate the hash of a revision given its data and its parents. | /// Calculate the hash of a revision given its data and its parents. | ||||
| fn hash(data: &[u8], p1_hash: &[u8], p2_hash: &[u8]) -> Vec<u8> { | fn hash(data: &[u8], p1_hash: &[u8], p2_hash: &[u8]) -> Vec<u8> { | ||||
| let mut hasher = Sha1::new(); | let mut hasher = Sha1::new(); | ||||
| } | } | ||||
| #[cfg(test)] | #[cfg(test)] | ||||
| mod tests { | mod tests { | ||||
| use super::*; | use super::*; | ||||
| use super::super::index::IndexEntryBuilder; | use super::super::index::IndexEntryBuilder; | ||||
| #[cfg(test)] | |||||
| pub struct RevlogBuilder { | |||||
| version: u16, | |||||
| is_general_delta: bool, | |||||
| is_inline: bool, | |||||
| offset: usize, | |||||
| index: Vec<Vec<u8>>, | |||||
| data: Vec<Vec<u8>>, | |||||
| } | |||||
| #[cfg(test)] | |||||
| impl RevlogBuilder { | |||||
| pub fn new() -> Self { | |||||
| Self { | |||||
| version: 2, | |||||
| is_inline: false, | |||||
| is_general_delta: true, | |||||
| offset: 0, | |||||
| index: vec![], | |||||
| data: vec![], | |||||
| } | |||||
| } | |||||
| pub fn with_inline(&mut self, value: bool) -> &mut Self { | |||||
| self.is_inline = value; | |||||
| self | |||||
| } | |||||
| pub fn with_general_delta(&mut self, value: bool) -> &mut Self { | |||||
| self.is_general_delta = value; | |||||
| self | |||||
| } | |||||
| pub fn with_version(&mut self, value: u16) -> &mut Self { | |||||
| self.version = value; | |||||
| self | |||||
| } | |||||
| pub fn push( | |||||
| &mut self, | |||||
| mut index: IndexEntryBuilder, | |||||
| data: Vec<u8>, | |||||
| ) -> &mut Self { | |||||
| if self.index.is_empty() { | |||||
| index.is_first(true); | |||||
| index.with_general_delta(self.is_general_delta); | |||||
| index.with_inline(self.is_inline); | |||||
| index.with_version(self.version); | |||||
| } else { | |||||
| index.with_offset(self.offset); | |||||
| } | |||||
| self.index.push(index.build()); | |||||
| self.offset += data.len(); | |||||
| self.data.push(data); | |||||
| self | |||||
| } | |||||
| pub fn build_inline(&self) -> Vec<u8> { | |||||
| let mut bytes = | |||||
| Vec::with_capacity(self.index.len() + self.data.len()); | |||||
| for (index, data) in self.index.iter().zip(self.data.iter()) { | |||||
| bytes.extend(index); | |||||
| bytes.extend(data); | |||||
| } | |||||
| bytes | |||||
| } | |||||
| } | |||||
| #[test] | |||||
| fn is_not_inline_when_no_inline_flag_test() { | |||||
| let bytes = RevlogBuilder::new() | |||||
| .with_general_delta(false) | |||||
| .with_inline(false) | |||||
| .push(IndexEntryBuilder::new(), vec![]) | |||||
| .build_inline(); | |||||
| assert_eq!(is_inline(&bytes), false) | |||||
| } | |||||
| #[test] | |||||
| fn is_inline_when_inline_flag_test() { | |||||
| let bytes = RevlogBuilder::new() | |||||
| .with_general_delta(false) | |||||
| .with_inline(true) | |||||
| .push(IndexEntryBuilder::new(), vec![]) | |||||
| .build_inline(); | |||||
| assert_eq!(is_inline(&bytes), true) | |||||
| } | |||||
| #[test] | |||||
| fn is_inline_when_inline_and_generaldelta_flags_test() { | |||||
| let bytes = RevlogBuilder::new() | |||||
| .with_general_delta(true) | |||||
| .with_inline(true) | |||||
| .push(IndexEntryBuilder::new(), vec![]) | |||||
| .build_inline(); | |||||
| assert_eq!(is_inline(&bytes), true) | |||||
| } | |||||
| #[test] | #[test] | ||||
| fn version_test() { | fn version_test() { | ||||
| let bytes = RevlogBuilder::new() | let bytes = IndexEntryBuilder::new() | ||||
| .is_first(true) | |||||
| .with_version(1) | .with_version(1) | ||||
| .push(IndexEntryBuilder::new(), vec![]) | .build(); | ||||
| .build_inline(); | |||||
| assert_eq!(get_version(&bytes), 1) | assert_eq!(get_version(&bytes), 1) | ||||
| } | } | ||||
| } | } | ||||