This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10005

rust: Rewrite dirstate parsing usin the `bytes-cast` crate
ClosedPublic

Authored by SimonSapin on Feb 17 2021, 7:58 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHGf88e8ae0aa8f: rust: Rewrite dirstate parsing usin the `bytes-cast` crate
rHGd10a0652d1d6: rust: Rewrite dirstate parsing usin the `bytes-cast` crate

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

SimonSapin created this revision.Feb 17 2021, 7:58 AM
Alphare accepted this revision.Feb 18 2021, 4:13 AM
Alphare added a subscriber: Alphare.
Alphare added inline comments.
rust/hg-core/src/dirstate/parsers.rs
53

We could possibly drop the dependency on memchr then. I wrote this code when I was first starting with Rust, it's likely that I had no idea that splitn existed or something.

SimonSapin marked an inline comment as done.Feb 19 2021, 3:02 AM
SimonSapin added inline comments.
rust/hg-core/src/dirstate/parsers.rs
53

Good point. I’m removing the direct dependency, though it’s still an indirect dependency through regex.

SimonSapin marked an inline comment as done.Feb 19 2021, 3:30 AM
SimonSapin updated this revision to Diff 25659.
SimonSapin added a commit: rHGd10a0652d1d6: rust: Rewrite dirstate parsing usin the `bytes-cast` crate.Feb 24 2021, 11:08 AM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGd10a0652d1d6: rust: Rewrite dirstate parsing usin the `bytes-cast` crate (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 25872

rust/Cargo.lock

"crossbeam-channel 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)", "crossbeam-channel 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)",
"derive_more 0.99.11 (registry+https://github.com/rust-lang/crates.io-index)", "derive_more 0.99.11 (registry+https://github.com/rust-lang/crates.io-index)",
"flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)", "flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)",
"format-bytes 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", "format-bytes 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
"home 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)", "home 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)",
"im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)", "im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
"lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
"log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)", "log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)",
"memchr 2.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
"memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)", "memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
"micro-timer 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", "micro-timer 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
"pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)", "pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
"rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)", "rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
"rand_distr 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", "rand_distr 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
"rand_pcg 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)", "rand_pcg 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
"rayon 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)", "rayon 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
"regex 1.4.2 (registry+https://github.com/rust-lang/crates.io-index)", "regex 1.4.2 (registry+https://github.com/rust-lang/crates.io-index)",

rust/hg-core/Cargo.toml

[dependencies] [dependencies]
bytes-cast = "0.1" bytes-cast = "0.1"
byteorder = "1.3.4" byteorder = "1.3.4"
derive_more = "0.99" derive_more = "0.99"
home = "0.5" home = "0.5"
im-rc = "15.0.*" im-rc = "15.0.*"
lazy_static = "1.4.0" lazy_static = "1.4.0"
memchr = "2.3.3"
rand = "0.7.3" rand = "0.7.3"
rand_pcg = "0.2.1" rand_pcg = "0.2.1"
rand_distr = "0.2.2" rand_distr = "0.2.2"
rayon = "1.3.0" rayon = "1.3.0"
regex = "1.3.9" regex = "1.3.9"
twox-hash = "1.5.0" twox-hash = "1.5.0"
same-file = "1.0.6" same-file = "1.0.6"
crossbeam-channel = "0.4" crossbeam-channel = "0.4"

rust/hg-core/src/dirstate.rs

// dirstate module // dirstate module
// //
// Copyright 2019 Raphaël Gomès <rgomes@octobus.net> // Copyright 2019 Raphaël Gomès <rgomes@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
use crate::errors::HgError; use crate::errors::HgError;
use crate::{utils::hg_path::HgPathBuf, FastHashMap}; use crate::{utils::hg_path::HgPathBuf, FastHashMap};
use bytes_cast::{unaligned, BytesCast};
use std::collections::hash_map; use std::collections::hash_map;
use std::convert::TryFrom; use std::convert::TryFrom;
pub mod dirs_multiset; pub mod dirs_multiset;
pub mod dirstate_map; pub mod dirstate_map;
#[cfg(feature = "dirstate-tree")] #[cfg(feature = "dirstate-tree")]
pub mod dirstate_tree; pub mod dirstate_tree;
pub mod parsers; pub mod parsers;
pub mod status; pub mod status;
#[derive(Debug, PartialEq, Clone)] #[derive(Debug, PartialEq, Clone, BytesCast)]
#[repr(C)]
pub struct DirstateParents { pub struct DirstateParents {
pub p1: [u8; 20], pub p1: [u8; 20],
pub p2: [u8; 20], pub p2: [u8; 20],
} }
/// The C implementation uses all signed types. This will be an issue /// The C implementation uses all signed types. This will be an issue
/// either when 4GB+ source files are commonplace or in 2038, whichever /// either when 4GB+ source files are commonplace or in 2038, whichever
/// comes first. /// comes first.
#[derive(Debug, PartialEq, Copy, Clone)] #[derive(Debug, PartialEq, Copy, Clone)]
pub struct DirstateEntry { pub struct DirstateEntry {
pub state: EntryState, pub state: EntryState,
pub mode: i32, pub mode: i32,
pub mtime: i32, pub mtime: i32,
pub size: i32, pub size: i32,
} }
#[derive(BytesCast)]
#[repr(C)]
struct RawEntry {
state: u8,
mode: unaligned::I32Be,
size: unaligned::I32Be,
mtime: unaligned::I32Be,
length: unaligned::I32Be,
}
/// A `DirstateEntry` with a size of `-2` means that it was merged from the /// A `DirstateEntry` with a size of `-2` means that it was merged from the
/// other parent. This allows revert to pick the right status back during a /// other parent. This allows revert to pick the right status back during a
/// merge. /// merge.
pub const SIZE_FROM_OTHER_PARENT: i32 = -2; pub const SIZE_FROM_OTHER_PARENT: i32 = -2;
#[cfg(not(feature = "dirstate-tree"))] #[cfg(not(feature = "dirstate-tree"))]
pub type StateMap = FastHashMap<HgPathBuf, DirstateEntry>; pub type StateMap = FastHashMap<HgPathBuf, DirstateEntry>;
#[cfg(not(feature = "dirstate-tree"))] #[cfg(not(feature = "dirstate-tree"))]

rust/hg-core/src/dirstate/dirstate_map.rs

} }
pub fn set_parents(&mut self, parents: &DirstateParents) { pub fn set_parents(&mut self, parents: &DirstateParents) {
self.parents = Some(parents.clone()); self.parents = Some(parents.clone());
self.dirty_parents = true; self.dirty_parents = true;
} }
#[timed] #[timed]
pub fn read( pub fn read<'a>(
&mut self, &mut self,
file_contents: &[u8], file_contents: &'a [u8],
) -> Result<Option<DirstateParents>, DirstateError> { ) -> Result<Option<&'a DirstateParents>, DirstateError> {
if file_contents.is_empty() { if file_contents.is_empty() {
return Ok(None); return Ok(None);
} }
let (parents, entries, copies) = parse_dirstate(file_contents)?; let (parents, entries, copies) = parse_dirstate(file_contents)?;
self.state_map.extend( self.state_map.extend(
entries entries
.into_iter() .into_iter()

rust/hg-core/src/dirstate/parsers.rs

// Copyright 2019 Raphaël Gomès <rgomes@octobus.net> // Copyright 2019 Raphaël Gomès <rgomes@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
use crate::errors::HgError; use crate::errors::HgError;
use crate::utils::hg_path::HgPath; use crate::utils::hg_path::HgPath;
use crate::{ use crate::{
dirstate::{CopyMap, EntryState, StateMap}, dirstate::{CopyMap, EntryState, RawEntry, StateMap},
DirstateEntry, DirstateParents, DirstateEntry, DirstateParents,
}; };
use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt}; use byteorder::{BigEndian, WriteBytesExt};
use bytes_cast::BytesCast;
use micro_timer::timed; use micro_timer::timed;
use std::convert::{TryFrom, TryInto}; use std::convert::{TryFrom, TryInto};
use std::io::Cursor;
use std::time::Duration; use std::time::Duration;
/// Parents are stored in the dirstate as byte hashes. /// Parents are stored in the dirstate as byte hashes.
pub const PARENT_SIZE: usize = 20; pub const PARENT_SIZE: usize = 20;
/// Dirstate entries have a static part of 8 + 32 + 32 + 32 + 32 bits. /// Dirstate entries have a static part of 8 + 32 + 32 + 32 + 32 bits.
const MIN_ENTRY_SIZE: usize = 17; const MIN_ENTRY_SIZE: usize = 17;
type ParseResult<'a> = ( type ParseResult<'a> = (
DirstateParents, &'a DirstateParents,
Vec<(&'a HgPath, DirstateEntry)>, Vec<(&'a HgPath, DirstateEntry)>,
Vec<(&'a HgPath, &'a HgPath)>, Vec<(&'a HgPath, &'a HgPath)>,
); );
#[timed] #[timed]
pub fn parse_dirstate(contents: &[u8]) -> Result<ParseResult, HgError> { pub fn parse_dirstate(mut contents: &[u8]) -> Result<ParseResult, HgError> {
if contents.len() < PARENT_SIZE * 2 { let mut copies = Vec::new();
return Err(HgError::corrupted("Too little data for dirstate.")); let mut entries = Vec::new();
let (parents, rest) = DirstateParents::from_bytes(contents)
.map_err(|_| HgError::corrupted("Too little data for dirstate."))?;
contents = rest;
while !contents.is_empty() {
let (raw_entry, rest) = RawEntry::from_bytes(contents)
.map_err(|_| HgError::corrupted("Overflow in dirstate."))?;
let entry = DirstateEntry {
state: EntryState::try_from(raw_entry.state)?,
mode: raw_entry.mode.get(),
mtime: raw_entry.mtime.get(),
size: raw_entry.size.get(),
};
let (paths, rest) =
u8::slice_from_bytes(rest, raw_entry.length.get() as usize)
.map_err(|_| HgError::corrupted("Overflow in dirstate."))?;
// `paths` is either a single path, or two paths separated by a NULL
// byte
let mut iter = paths.splitn(2, |&byte| byte == b'\0');
AlphareUnsubmitted
Done

We could possibly drop the dependency on memchr then. I wrote this code when I was first starting with Rust, it's likely that I had no idea that splitn existed or something.

Alphare: We could possibly drop the dependency on `memchr` then. I wrote this code when I was first…
SimonSapinAuthorUnsubmitted
Done

Good point. I’m removing the direct dependency, though it’s still an indirect dependency through regex.

SimonSapin: Good point. I’m removing the direct dependency, though it’s still an indirect dependency…
let path = HgPath::new(
iter.next().expect("splitn always yields at least one item"),
);
if let Some(copy_source) = iter.next() {
copies.push((path, HgPath::new(copy_source)));
} }
let mut copies = vec![];
let mut entries = vec![];
let mut curr_pos = PARENT_SIZE * 2;
let parents = DirstateParents {
p1: contents[..PARENT_SIZE].try_into().unwrap(),
p2: contents[PARENT_SIZE..curr_pos].try_into().unwrap(),
};
while curr_pos < contents.len() {
if curr_pos + MIN_ENTRY_SIZE > contents.len() {
return Err(HgError::corrupted("Overflow in dirstate."));
}
let entry_bytes = &contents[curr_pos..];
let mut cursor = Cursor::new(entry_bytes);
// Unwraping errors from `byteorder` as we’ve already checked
// `MIN_ENTRY_SIZE` so the input should never be too short.
let state = EntryState::try_from(cursor.read_u8().unwrap())?;
let mode = cursor.read_i32::<BigEndian>().unwrap();
let size = cursor.read_i32::<BigEndian>().unwrap();
let mtime = cursor.read_i32::<BigEndian>().unwrap();
let path_len = cursor.read_i32::<BigEndian>().unwrap() as usize;
if path_len > contents.len() - curr_pos {
return Err(HgError::corrupted("Overflow in dirstate."));
}
// Slice instead of allocating a Vec needed for `read_exact`
let path = &entry_bytes[MIN_ENTRY_SIZE..MIN_ENTRY_SIZE + (path_len)];
let (path, copy) = match memchr::memchr(0, path) {
None => (path, None),
Some(i) => (&path[..i], Some(&path[(i + 1)..])),
};
if let Some(copy_path) = copy { entries.push((path, entry));
copies.push((HgPath::new(path), HgPath::new(copy_path))); contents = rest;
};
entries.push((
HgPath::new(path),
DirstateEntry {
state,
mode,
size,
mtime,
},
));
curr_pos = curr_pos + MIN_ENTRY_SIZE + (path_len);
} }
Ok((parents, entries, copies)) Ok((parents, entries, copies))
} }
/// `now` is the duration in seconds since the Unix epoch /// `now` is the duration in seconds since the Unix epoch
#[cfg(not(feature = "dirstate-tree"))] #[cfg(not(feature = "dirstate-tree"))]
pub fn pack_dirstate( pub fn pack_dirstate(
state_map: &mut StateMap, state_map: &mut StateMap,
.map(|(path, entry)| (path.to_owned(), entry)) .map(|(path, entry)| (path.to_owned(), entry))
.collect(); .collect();
let new_copy_map: CopyMap = copies let new_copy_map: CopyMap = copies
.into_iter() .into_iter()
.map(|(path, copy)| (path.to_owned(), copy.to_owned())) .map(|(path, copy)| (path.to_owned(), copy.to_owned()))
.collect(); .collect();
assert_eq!( assert_eq!(
(parents, state_map, copymap), (&parents, state_map, copymap),
(new_parents, new_state_map, new_copy_map) (new_parents, new_state_map, new_copy_map)
) )
} }
#[test] #[test]
fn test_parse_pack_multiple_entries_with_copy() { fn test_parse_pack_multiple_entries_with_copy() {
let mut state_map: StateMap = [ let mut state_map: StateMap = [
( (
.map(|(path, entry)| (path.to_owned(), entry)) .map(|(path, entry)| (path.to_owned(), entry))
.collect(); .collect();
let new_copy_map: CopyMap = copies let new_copy_map: CopyMap = copies
.into_iter() .into_iter()
.map(|(path, copy)| (path.to_owned(), copy.to_owned())) .map(|(path, copy)| (path.to_owned(), copy.to_owned()))
.collect(); .collect();
assert_eq!( assert_eq!(
(parents, state_map, copymap), (&parents, state_map, copymap),
(new_parents, new_state_map, new_copy_map) (new_parents, new_state_map, new_copy_map)
) )
} }
#[test] #[test]
/// https://www.mercurial-scm.org/repo/hg/rev/af3f26b6bba4 /// https://www.mercurial-scm.org/repo/hg/rev/af3f26b6bba4
fn test_parse_pack_one_entry_with_copy_and_time_conflict() { fn test_parse_pack_one_entry_with_copy_and_time_conflict() {
let mut state_map: StateMap = [( let mut state_map: StateMap = [(
.collect(); .collect();
let new_copy_map: CopyMap = copies let new_copy_map: CopyMap = copies
.into_iter() .into_iter()
.map(|(path, copy)| (path.to_owned(), copy.to_owned())) .map(|(path, copy)| (path.to_owned(), copy.to_owned()))
.collect(); .collect();
assert_eq!( assert_eq!(
( (
parents, &parents,
[( [(
HgPathBuf::from_bytes(b"f1"), HgPathBuf::from_bytes(b"f1"),
DirstateEntry { DirstateEntry {
state: EntryState::Normal, state: EntryState::Normal,
mode: 0o644, mode: 0o644,
size: 0, size: 0,
mtime: -1 mtime: -1
} }