( )⚙ D10068 copies-rust: rewrite ChangedFiles binary parsing

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10068

copies-rust: rewrite ChangedFiles binary parsing
ClosedPublic

Authored by SimonSapin on Feb 25 2021, 5:32 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHGf977a065c7c2: copies-rust: rewrite ChangedFiles binary parsing
rHGdf6be4ede63a: copies-rust: rewrite ChangedFiles binary parsing
Summary

by using the new from-bytes-safe crate and a custom struct
that encodes the expected data structure.

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 25 2021, 5:32 AM
Alphare accepted this revision.Mar 2 2021, 8:36 AM
Alphare added a subscriber: Alphare.
Alphare added inline comments.
rust/hg-core/src/copy_tracing.rs
165

If you can fix s/hold/holds/ while you're here, that'd be great.

baymax updated this revision to Diff 26020.Mar 2 2021, 9:07 AM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

SimonSapin added a commit: rHGdf6be4ede63a: copies-rust: rewrite ChangedFiles binary parsing.Mar 8 2021, 3:27 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGdf6be4ede63a: copies-rust: rewrite ChangedFiles binary parsing (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/copy_tracing.rs (210 lines)

Diff 26147

rust/hg-core/src/copy_tracing.rs

use crate::utils::hg_path::HgPath; use crate::utils::hg_path::HgPath;
use crate::utils::hg_path::HgPathBuf; use crate::utils::hg_path::HgPathBuf;
use crate::Revision; use crate::Revision;
use crate::NULL_REVISION; use crate::NULL_REVISION;
use bytes_cast::{unaligned, BytesCast};
use im_rc::ordmap::Entry; use im_rc::ordmap::Entry;
use im_rc::ordmap::OrdMap; use im_rc::ordmap::OrdMap;
use im_rc::OrdSet; use im_rc::OrdSet;
use std::cmp::Ordering; use std::cmp::Ordering;
use std::collections::HashMap; use std::collections::HashMap;
use std::convert::TryInto;
pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>; pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
type PathToken = usize; type PathToken = usize;
#[derive(Clone, Debug)] #[derive(Clone, Debug)]
struct CopySource { struct CopySource {
/// revision at which the copy information was added /// revision at which the copy information was added
} }
self.rev == other.rev self.rev == other.rev
} }
} }
/// maps CopyDestination to Copy Source (+ a "timestamp" for the operation) /// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)
type InternalPathCopies = OrdMap<PathToken, CopySource>; type InternalPathCopies = OrdMap<PathToken, CopySource>;
/// represent the files affected by a changesets
///
/// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
/// all the data categories tracked by it.
/// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
/// all the data categories tracked by it.
pub struct ChangedFiles<'a> {
nb_items: u32,
index: &'a [u8],
data: &'a [u8],
}
/// Represent active changes that affect the copy tracing. /// Represent active changes that affect the copy tracing.
enum Action<'a> { enum Action<'a> {
/// The parent ? children edge is removing a file /// The parent ? children edge is removing a file
/// ///
/// (actually, this could be the edge from the other parent, but it does /// (actually, this could be the edge from the other parent, but it does
/// not matters) /// not matters)
Removed(&'a HgPath), Removed(&'a HgPath),
/// The parent ? children edge introduce copy information between (dest, /// The parent ? children edge introduce copy information between (dest,
/// Merged: file had history on both side that needed to be merged /// Merged: file had history on both side that needed to be merged
Merged, Merged,
/// Salvaged: file was candidate for deletion, but survived the merge /// Salvaged: file was candidate for deletion, but survived the merge
Salvaged, Salvaged,
/// Normal: Not one of the two cases above /// Normal: Not one of the two cases above
Normal, Normal,
} }
type FileChange<'a> = (u8, &'a HgPath, &'a HgPath);
const EMPTY: &[u8] = b"";
const COPY_MASK: u8 = 3; const COPY_MASK: u8 = 3;
const P1_COPY: u8 = 2; const P1_COPY: u8 = 2;
const P2_COPY: u8 = 3; const P2_COPY: u8 = 3;
const ACTION_MASK: u8 = 28; const ACTION_MASK: u8 = 28;
const REMOVED: u8 = 12; const REMOVED: u8 = 12;
const MERGED: u8 = 8; const MERGED: u8 = 8;
const SALVAGED: u8 = 16; const SALVAGED: u8 = 16;
impl<'a> ChangedFiles<'a> { #[derive(BytesCast)]
const INDEX_START: usize = 4; #[repr(C)]
const ENTRY_SIZE: u32 = 9; struct ChangedFilesIndexEntry {
const FILENAME_START: u32 = 1; flags: u8,
const COPY_SOURCE_START: u32 = 5;
pub fn new(data: &'a [u8]) -> Self { /// Only the end position is stored. The start is at the end of the
assert!( /// previous entry.
data.len() >= 4, destination_path_end_position: unaligned::U32Be,
"data size ({}) is too small to contain the header (4)",
data.len()
);
let nb_items_raw: [u8; 4] = (&data[0..=3])
.try_into()
.expect("failed to turn 4 bytes into 4 bytes");
let nb_items = u32::from_be_bytes(nb_items_raw);
let index_size = (nb_items * Self::ENTRY_SIZE) as usize;
let index_end = Self::INDEX_START + index_size;
assert!(
data.len() >= index_end,
"data size ({}) is too small to fit the index_data ({})",
data.len(),
index_end
);
let ret = ChangedFiles { source_index_entry_position: unaligned::U32Be,
nb_items, }
index: &data[Self::INDEX_START..index_end],
data: &data[index_end..], fn _static_assert_size_of() {
}; let _ = std::mem::transmute::<ChangedFilesIndexEntry, [u8; 9]>;
let max_data = ret.filename_end(nb_items - 1) as usize; }
assert!(
ret.data.len() >= max_data, /// Represents the files affected by a changeset.
"data size ({}) is too small to fit all data ({})", ///
data.len(), /// This holds a subset of `mercurial.metadata.ChangingFiles` as we do not need
AlphareUnsubmitted
Not Done

If you can fix s/hold/holds/ while you're here, that'd be great.

Alphare: If you can fix `s/hold/holds/` while you're here, that'd be great.
index_end + max_data /// all the data categories tracked by it.
); pub struct ChangedFiles<'a> {
ret index: &'a [ChangedFilesIndexEntry],
paths: &'a [u8],
}
impl<'a> ChangedFiles<'a> {
pub fn new(data: &'a [u8]) -> Self {
let (header, rest) = unaligned::U32Be::from_bytes(data).unwrap();
let nb_index_entries = header.get() as usize;
let (index, paths) =
ChangedFilesIndexEntry::slice_from_bytes(rest, nb_index_entries)
.unwrap();
Self { index, paths }
} }
pub fn new_empty() -> Self { pub fn new_empty() -> Self {
ChangedFiles { ChangedFiles {
nb_items: 0, index: &[],
index: EMPTY, paths: &[],
data: EMPTY, }
} }
}
/// Internal function to return the filename of the entry at a given index
/// internal function to return an individual entry at a given index fn path(&self, idx: usize) -> &HgPath {
fn entry(&'a self, idx: u32) -> FileChange<'a> { let start = if idx == 0 {
if idx >= self.nb_items { 0
panic!( } else {
"index for entry is higher that the number of file {} >= {}", self.index[idx - 1].destination_path_end_position.get() as usize
idx, self.nb_items };
) let end = self.index[idx].destination_path_end_position.get() as usize;
} HgPath::new(&self.paths[start..end])
let flags = self.flags(idx);
let filename = self.filename(idx);
let copy_idx = self.copy_idx(idx);
let copy_source = self.filename(copy_idx);
(flags, filename, copy_source)
}
/// internal function to return the filename of the entry at a given index
fn filename(&self, idx: u32) -> &HgPath {
let filename_start;
if idx == 0 {
filename_start = 0;
} else {
filename_start = self.filename_end(idx - 1)
}
let filename_end = self.filename_end(idx);
let filename_start = filename_start as usize;
let filename_end = filename_end as usize;
HgPath::new(&self.data[filename_start..filename_end])
}
/// internal function to return the flag field of the entry at a given
/// index
fn flags(&self, idx: u32) -> u8 {
let idx = idx as usize;
self.index[idx * (Self::ENTRY_SIZE as usize)]
}
/// internal function to return the end of a filename part at a given index
fn filename_end(&self, idx: u32) -> u32 {
let start = (idx * Self::ENTRY_SIZE) + Self::FILENAME_START;
let end = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
let start = start as usize;
let end = end as usize;
let raw = (&self.index[start..end])
.try_into()
.expect("failed to turn 4 bytes into 4 bytes");
u32::from_be_bytes(raw)
}
/// internal function to return index of the copy source of the entry at a
/// given index
fn copy_idx(&self, idx: u32) -> u32 {
let start = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
let end = (idx + 1) * Self::ENTRY_SIZE;
let start = start as usize;
let end = end as usize;
let raw = (&self.index[start..end])
.try_into()
.expect("failed to turn 4 bytes into 4 bytes");
u32::from_be_bytes(raw)
} }
/// Return an iterator over all the `Action` in this instance. /// Return an iterator over all the `Action` in this instance.
fn iter_actions(&self) -> ActionsIterator { fn iter_actions(&self) -> impl Iterator<Item = Action> {
ActionsIterator { self.index.iter().enumerate().flat_map(move |(idx, entry)| {
changes: &self, let path = self.path(idx);
current: 0, if (entry.flags & ACTION_MASK) == REMOVED {
Some(Action::Removed(path))
} else if (entry.flags & COPY_MASK) == P1_COPY {
let source_idx =
entry.source_index_entry_position.get() as usize;
Some(Action::CopiedFromP1(path, self.path(source_idx)))
} else if (entry.flags & COPY_MASK) == P2_COPY {
let source_idx =
entry.source_index_entry_position.get() as usize;
Some(Action::CopiedFromP2(path, self.path(source_idx)))
} else {
None
} }
})
} }
/// return the MergeCase value associated with a filename /// return the MergeCase value associated with a filename
fn get_merge_case(&self, path: &HgPath) -> MergeCase { fn get_merge_case(&self, path: &HgPath) -> MergeCase {
if self.nb_items == 0 { if self.index.is_empty() {
return MergeCase::Normal; return MergeCase::Normal;
} }
let mut low_part = 0; let mut low_part = 0;
let mut high_part = self.nb_items; let mut high_part = self.index.len();
while low_part < high_part { while low_part < high_part {
let cursor = (low_part + high_part - 1) / 2; let cursor = (low_part + high_part - 1) / 2;
let (flags, filename, _source) = self.entry(cursor); match path.cmp(self.path(cursor)) {
match path.cmp(filename) {
Ordering::Less => low_part = cursor + 1, Ordering::Less => low_part = cursor + 1,
Ordering::Greater => high_part = cursor, Ordering::Greater => high_part = cursor,
Ordering::Equal => { Ordering::Equal => {
return match flags & ACTION_MASK { return match self.index[cursor].flags & ACTION_MASK {
MERGED => MergeCase::Merged, MERGED => MergeCase::Merged,
SALVAGED => MergeCase::Salvaged, SALVAGED => MergeCase::Salvaged,
_ => MergeCase::Normal, _ => MergeCase::Normal,
}; };
} }
} }
} }
MergeCase::Normal MergeCase::Normal
} }
} }
struct ActionsIterator<'a> {
changes: &'a ChangedFiles<'a>,
current: u32,
}
impl<'a> Iterator for ActionsIterator<'a> {
type Item = Action<'a>;
fn next(&mut self) -> Option<Action<'a>> {
while self.current < self.changes.nb_items {
let (flags, file, source) = self.changes.entry(self.current);
self.current += 1;
if (flags & ACTION_MASK) == REMOVED {
return Some(Action::Removed(file));
}
let copy = flags & COPY_MASK;
if copy == P1_COPY {
return Some(Action::CopiedFromP1(file, source));
} else if copy == P2_COPY {
return Some(Action::CopiedFromP2(file, source));
}
}
return None;
}
}
/// A small "tokenizer" responsible of turning full HgPath into lighter /// A small "tokenizer" responsible of turning full HgPath into lighter
/// PathToken /// PathToken
/// ///
/// Dealing with small object, like integer is much faster, so HgPath input are /// Dealing with small object, like integer is much faster, so HgPath input are
/// turned into integer "PathToken" and converted back in the end. /// turned into integer "PathToken" and converted back in the end.
#[derive(Clone, Debug, Default)] #[derive(Clone, Debug, Default)]
struct TwoWayPathMap { struct TwoWayPathMap {
token: HashMap<HgPathBuf, PathToken>, token: HashMap<HgPathBuf, PathToken>,