( )⚙ 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
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

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 25957

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 hold 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>,