This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6348

rust-dirstate: add rust implementation of `parse_dirstate` and `pack_dirstate`
ClosedPublic

Authored by Alphare on May 6 2019, 5:03 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGd1786c1d34fa: rust-dirstate: add rust implementation of `parse_dirstate` and `pack_dirstate`
Summary

Working towards the goal of having a complete Rust implementation of
hg status, these two utils are a first step of many to be taken
to improve performance and code maintainability.

Two dependencies have been added: memchr and byteorder.
Both of them have been written by reputable community members and are
very mature crates.
The Rust code will often need to use their byte-oriented functions.

A few unit tests have been added and may help future development and debugging.

In a future patch that uses parse_dirstate to stat the working tree in
parallel - which neither the Python nor the C implementations do - actual
performance improvements will be seen for larger repositories.

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

Alphare created this revision.May 6 2019, 5:03 PM
kevincox requested changes to this revision.May 10 2019, 11:04 AM
kevincox added inline comments.
rust/hg-core/src/dirstate.rs
17

You have a lot of tuples here an it is unclear what they represent. I would much prefer making structs for these, then you can give the members names which will really help the reader.

35

You check for PARENT_SIZE then index by PERENT_SIZE*2. This will panic if the size is between the two.

37

It would be nice to define the above the definition of parents and use it in that slice.

44

This isn't a very useful name. Maybe entry or entry_bytes.

49

This is a lot of manual index numbers. It would probably me more clear to wrap it in a Cursor and use https://docs.rs/byteorder/1.3.1/byteorder/trait.ReadBytesExt.html to read the values. This way the cursor is automatically moved to match the data you have read.

This revision now requires changes to proceed.May 10 2019, 11:04 AM
Alphare marked 5 inline comments as done.May 13 2019, 5:47 AM
Alphare updated this revision to Diff 15066.
Alphare added a comment.May 13 2019, 5:48 AM

Thanks for review. I think I've addressed all of your points.

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

Good catch, thanks!

Closed by commit rHGd1786c1d34fa: rust-dirstate: add rust implementation of `parse_dirstate` and `pack_dirstate` (authored by Alphare). · Explain WhyMay 15 2019, 2:15 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 15114

rust/hg-core/Cargo.toml

[package] [package]
name = "hg-core" name = "hg-core"
version = "0.1.0" version = "0.1.0"
authors = ["Georges Racinet <gracinet@anybox.fr>"] authors = ["Georges Racinet <gracinet@anybox.fr>"]
description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)" description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)"
[lib] [lib]
name = "hg" name = "hg"
[dev-dependencies] [dev-dependencies]
rand = "*" rand = "*"
rand_pcg = "*" rand_pcg = "*"
[dependencies]
memchr = "2.2.0"
byteorder = "1.3.1"
No newline at end of file

rust/hg-core/src/dirstate.rs

  • This file was added.
// Copyright 2019 Raphaël Gomès <rgomes@octobus.net>
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
use std::collections::HashMap;
use std::io::Cursor;
use {DirstatePackError, DirstateParseError};
#[derive(Debug, PartialEq, Copy, Clone)]
pub struct DirstateParents<'a> {
pub p1: &'a [u8],
pub p2: &'a [u8],
}
/// The C implementation uses all signed types. This will be an issue
/// either when 4GB+ source files are commonplace or in 2038, whichever
kevincoxUnsubmitted
Done

You have a lot of tuples here an it is unclear what they represent. I would much prefer making structs for these, then you can give the members names which will really help the reader.

kevincox: You have a lot of tuples here an it is unclear what they represent. I would much prefer making…
/// comes first.
#[derive(Debug, PartialEq)]
pub struct DirstateEntry {
pub state: i8,
pub mode: i32,
pub mtime: i32,
pub size: i32,
}
pub type DirstateVec = Vec<(Vec<u8>, DirstateEntry)>;
#[derive(Debug, PartialEq)]
pub struct CopyVecEntry<'a> {
pub path: &'a [u8],
pub copy_path: &'a [u8],
}
pub type CopyVec<'a> = Vec<CopyVecEntry<'a>>;
/// Parents are stored in the dirstate as byte hashes.
kevincoxUnsubmitted
Done

You check for PARENT_SIZE then index by PERENT_SIZE*2. This will panic if the size is between the two.

kevincox: You check for PARENT_SIZE then index by PERENT_SIZE*2. This will panic if the size is between…
AlphareAuthorUnsubmitted
Not Done

Good catch, thanks!

Alphare: Good catch, thanks!
const PARENT_SIZE: usize = 20;
/// Dirstate entries have a static part of 8 + 32 + 32 + 32 + 32 bits.
kevincoxUnsubmitted
Done

It would be nice to define the above the definition of parents and use it in that slice.

kevincox: It would be nice to define the above the definition of `parents` and use it in that slice.
const MIN_ENTRY_SIZE: usize = 17;
pub fn parse_dirstate(
contents: &[u8],
) -> Result<(DirstateParents, DirstateVec, CopyVec), DirstateParseError> {
if contents.len() < PARENT_SIZE * 2 {
return Err(DirstateParseError::TooLittleData);
kevincoxUnsubmitted
Done

This isn't a very useful name. Maybe entry or entry_bytes.

kevincox: This isn't a very useful name. Maybe `entry` or `entry_bytes`.
}
let mut dirstate_vec = vec![];
let mut copies = vec![];
let mut curr_pos = PARENT_SIZE * 2;
kevincoxUnsubmitted
Done

This is a lot of manual index numbers. It would probably me more clear to wrap it in a Cursor and use https://docs.rs/byteorder/1.3.1/byteorder/trait.ReadBytesExt.html to read the values. This way the cursor is automatically moved to match the data you have read.

kevincox: This is a lot of manual index numbers. It would probably me more clear to wrap it in a Cursor…
let parents = DirstateParents {
p1: &contents[..PARENT_SIZE],
p2: &contents[PARENT_SIZE..curr_pos],
};
while curr_pos < contents.len() {
if curr_pos + MIN_ENTRY_SIZE > contents.len() {
return Err(DirstateParseError::Overflow);
}
let entry_bytes = &contents[curr_pos..];
let mut cursor = Cursor::new(entry_bytes);
let state = cursor.read_i8()?;
let mode = cursor.read_i32::<BigEndian>()?;
let size = cursor.read_i32::<BigEndian>()?;
let mtime = cursor.read_i32::<BigEndian>()?;
let path_len = cursor.read_i32::<BigEndian>()? as usize;
if path_len > contents.len() - curr_pos {
return Err(DirstateParseError::Overflow);
}
// 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 {
copies.push(CopyVecEntry { path, copy_path });
};
dirstate_vec.push((
path.to_owned(),
DirstateEntry {
state,
mode,
size,
mtime,
},
));
curr_pos = curr_pos + MIN_ENTRY_SIZE + (path_len);
}
Ok((parents, dirstate_vec, copies))
}
pub fn pack_dirstate(
dirstate_vec: &DirstateVec,
copymap: &HashMap<Vec<u8>, Vec<u8>>,
parents: DirstateParents,
now: i32,
) -> Result<(Vec<u8>, DirstateVec), DirstatePackError> {
if parents.p1.len() != PARENT_SIZE || parents.p2.len() != PARENT_SIZE {
return Err(DirstatePackError::CorruptedParent);
}
let expected_size: usize = dirstate_vec
.iter()
.map(|(ref filename, _)| {
let mut length = MIN_ENTRY_SIZE + filename.len();
if let Some(ref copy) = copymap.get(filename) {
length += copy.len() + 1;
}
length
})
.sum();
let expected_size = expected_size + PARENT_SIZE * 2;
let mut packed = Vec::with_capacity(expected_size);
let mut new_dirstate_vec = vec![];
packed.extend(parents.p1);
packed.extend(parents.p2);
for (ref filename, entry) in dirstate_vec {
let mut new_filename: Vec<u8> = filename.to_owned();
let mut new_mtime: i32 = entry.mtime;
if entry.state == 'n' as i8 && entry.mtime == now.into() {
// The file was last modified "simultaneously" with the current
// write to dirstate (i.e. within the same second for file-
// systems with a granularity of 1 sec). This commonly happens
// for at least a couple of files on 'update'.
// The user could change the file without changing its size
// within the same second. Invalidate the file's mtime in
// dirstate, forcing future 'status' calls to compare the
// contents of the file if the size is the same. This prevents
// mistakenly treating such files as clean.
new_mtime = -1;
new_dirstate_vec.push((
filename.to_owned(),
DirstateEntry {
mtime: new_mtime,
..*entry
},
));
}
if let Some(copy) = copymap.get(filename) {
new_filename.push('\0' as u8);
new_filename.extend(copy);
}
packed.write_i8(entry.state)?;
packed.write_i32::<BigEndian>(entry.mode)?;
packed.write_i32::<BigEndian>(entry.size)?;
packed.write_i32::<BigEndian>(new_mtime)?;
packed.write_i32::<BigEndian>(new_filename.len() as i32)?;
packed.extend(new_filename)
}
if packed.len() != expected_size {
return Err(DirstatePackError::BadSize(expected_size, packed.len()));
}
Ok((packed, new_dirstate_vec))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_pack_dirstate_empty() {
let dirstate_vec: DirstateVec = vec![];
let copymap = HashMap::new();
let parents = DirstateParents {
p1: b"12345678910111213141",
p2: b"00000000000000000000",
};
let now: i32 = 15000000;
let expected =
(b"1234567891011121314100000000000000000000".to_vec(), vec![]);
assert_eq!(
expected,
pack_dirstate(&dirstate_vec, &copymap, parents, now).unwrap()
);
}
#[test]
fn test_pack_dirstate_one_entry() {
let dirstate_vec: DirstateVec = vec![(
vec!['f' as u8, '1' as u8],
DirstateEntry {
state: 'n' as i8,
mode: 0o644,
size: 0,
mtime: 791231220,
},
)];
let copymap = HashMap::new();
let parents = DirstateParents {
p1: b"12345678910111213141",
p2: b"00000000000000000000",
};
let now: i32 = 15000000;
let expected = (
[
49, 50, 51, 52, 53, 54, 55, 56, 57, 49, 48, 49, 49, 49, 50,
49, 51, 49, 52, 49, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 110, 0, 0, 1, 164, 0,
0, 0, 0, 47, 41, 58, 244, 0, 0, 0, 2, 102, 49,
]
.to_vec(),
vec![],
);
assert_eq!(
expected,
pack_dirstate(&dirstate_vec, &copymap, parents, now).unwrap()
);
}
#[test]
fn test_pack_dirstate_one_entry_with_copy() {
let dirstate_vec: DirstateVec = vec![(
b"f1".to_vec(),
DirstateEntry {
state: 'n' as i8,
mode: 0o644,
size: 0,
mtime: 791231220,
},
)];
let mut copymap = HashMap::new();
copymap.insert(b"f1".to_vec(), b"copyname".to_vec());
let parents = DirstateParents {
p1: b"12345678910111213141",
p2: b"00000000000000000000",
};
let now: i32 = 15000000;
let expected = (
[
49, 50, 51, 52, 53, 54, 55, 56, 57, 49, 48, 49, 49, 49, 50,
49, 51, 49, 52, 49, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 110, 0, 0, 1, 164, 0,
0, 0, 0, 47, 41, 58, 244, 0, 0, 0, 11, 102, 49, 0, 99, 111,
112, 121, 110, 97, 109, 101,
]
.to_vec(),
vec![],
);
assert_eq!(
expected,
pack_dirstate(&dirstate_vec, &copymap, parents, now).unwrap()
);
}
#[test]
fn test_parse_pack_one_entry_with_copy() {
let dirstate_vec: DirstateVec = vec![(
b"f1".to_vec(),
DirstateEntry {
state: 'n' as i8,
mode: 0o644,
size: 0,
mtime: 791231220,
},
)];
let mut copymap = HashMap::new();
copymap.insert(b"f1".to_vec(), b"copyname".to_vec());
let parents = DirstateParents {
p1: b"12345678910111213141",
p2: b"00000000000000000000",
};
let now: i32 = 15000000;
let result =
pack_dirstate(&dirstate_vec, &copymap, parents, now).unwrap();
assert_eq!(
(
parents,
dirstate_vec,
copymap
.iter()
.map(|(k, v)| CopyVecEntry {
path: k.as_slice(),
copy_path: v.as_slice()
})
.collect()
),
parse_dirstate(result.0.as_slice()).unwrap()
)
}
#[test]
fn test_parse_pack_multiple_entries_with_copy() {
let dirstate_vec: DirstateVec = vec![
(
b"f1".to_vec(),
DirstateEntry {
state: 'n' as i8,
mode: 0o644,
size: 0,
mtime: 791231220,
},
),
(
b"f2".to_vec(),
DirstateEntry {
state: 'm' as i8,
mode: 0o777,
size: 1000,
mtime: 791231220,
},
),
(
b"f3".to_vec(),
DirstateEntry {
state: 'r' as i8,
mode: 0o644,
size: 234553,
mtime: 791231220,
},
),
(
b"f4\xF6".to_vec(),
DirstateEntry {
state: 'a' as i8,
mode: 0o644,
size: -1,
mtime: -1,
},
),
];
let mut copymap = HashMap::new();
copymap.insert(b"f1".to_vec(), b"copyname".to_vec());
copymap.insert(b"f4\xF6".to_vec(), b"copyname2".to_vec());
let parents = DirstateParents {
p1: b"12345678910111213141",
p2: b"00000000000000000000",
};
let now: i32 = 15000000;
let result =
pack_dirstate(&dirstate_vec, &copymap, parents, now).unwrap();
assert_eq!(
(parents, dirstate_vec, copymap),
parse_dirstate(result.0.as_slice())
.and_then(|(p, dvec, cvec)| Ok((
p,
dvec,
cvec.iter()
.map(|entry| (
entry.path.to_vec(),
entry.copy_path.to_vec()
))
.collect()
)))
.unwrap()
)
}
#[test]
/// https://www.mercurial-scm.org/repo/hg/rev/af3f26b6bba4
fn test_parse_pack_one_entry_with_copy_and_time_conflict() {
let dirstate_vec: DirstateVec = vec![(
b"f1".to_vec(),
DirstateEntry {
state: 'n' as i8,
mode: 0o644,
size: 0,
mtime: 15000000,
},
)];
let mut copymap = HashMap::new();
copymap.insert(b"f1".to_vec(), b"copyname".to_vec());
let parents = DirstateParents {
p1: b"12345678910111213141",
p2: b"00000000000000000000",
};
let now: i32 = 15000000;
let result =
pack_dirstate(&dirstate_vec, &copymap, parents, now).unwrap();
assert_eq!(
(
parents,
vec![(
b"f1".to_vec(),
DirstateEntry {
state: 'n' as i8,
mode: 0o644,
size: 0,
mtime: -1
}
)],
copymap
.iter()
.map(|(k, v)| CopyVecEntry {
path: k.as_slice(),
copy_path: v.as_slice()
})
.collect()
),
parse_dirstate(result.0.as_slice()).unwrap()
)
}
}

rust/hg-core/src/lib.rs

// Copyright 2018 Georges Racinet <gracinet@anybox.fr> // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
// //
// 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.
extern crate byteorder;
extern crate memchr;
mod ancestors; mod ancestors;
pub mod dagops; pub mod dagops;
pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors}; pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
pub mod testing; // unconditionally built, for use from integration tests pub mod testing; // unconditionally built, for use from integration tests
pub mod discovery; pub mod discovery;
/// Mercurial revision numbers /// Mercurial revision numbers
/// ///
fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>; fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>;
} }
#[derive(Clone, Debug, PartialEq)] #[derive(Clone, Debug, PartialEq)]
pub enum GraphError { pub enum GraphError {
ParentOutOfRange(Revision), ParentOutOfRange(Revision),
WorkingDirectoryUnsupported, WorkingDirectoryUnsupported,
} }
#[derive(Clone, Debug, PartialEq)]
pub enum DirstateParseError {
TooLittleData,
Overflow,
CorruptedEntry(String),
}
#[derive(Debug, PartialEq)]
pub enum DirstatePackError {
CorruptedEntry(String),
CorruptedParent,
BadSize(usize, usize),
}
impl From<std::io::Error> for DirstatePackError {
fn from(e: std::io::Error) -> Self {
DirstatePackError::CorruptedEntry(e.to_string())
}
}
impl From<std::io::Error> for DirstateParseError {
fn from(e: std::io::Error) -> Self {
DirstateParseError::CorruptedEntry(e.to_string())
}
}