( )⚙ D11932 rhg: Use binary search in manifest lookup

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11932

rhg: Use binary search in manifest lookup
ClosedPublic

Authored by SimonSapin on Dec 16 2021, 12:13 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHGe293ff808a05: rhg: Use binary search in manifest lookup
Summary

… instead of linear scan, when looking for a single entry based on its path.
Manifest entries are sorted by path, but are variable-size so we can’t use
the standard library’s [T]::binary_search. We can still jump to a byte
index and then look around for entry boundaries.

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.Dec 16 2021, 12:13 PM
Alphare accepted this revision.Dec 17 2021, 6:09 AM
This revision is now accepted and ready to land.Dec 17 2021, 6:09 AM
SimonSapin added a commit: rHGe293ff808a05: rhg: Use binary search in manifest lookup.Dec 17 2021, 6:15 AM
Closed by commit rHGe293ff808a05: rhg: Use binary search in manifest lookup (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 31526

rust/hg-core/src/revlog/manifest.rs

let bytes = self.revlog.get_rev_data(rev)?; let bytes = self.revlog.get_rev_data(rev)?;
Ok(Manifest { bytes }) Ok(Manifest { bytes })
} }
} }
/// `Manifestlog` entry which knows how to interpret the `manifest` data bytes. /// `Manifestlog` entry which knows how to interpret the `manifest` data bytes.
#[derive(Debug)] #[derive(Debug)]
pub struct Manifest { pub struct Manifest {
/// Format for a manifest: flat sequence of variable-size entries,
/// sorted by path, each as:
///
/// ```text
/// <path> \0 <hex_node_id> <flags> \n
/// ```
///
/// The last entry is also terminated by a newline character.
/// Flags is one of `b""` (the empty string), `b"x"`, `b"l"`, or `b"t"`.
bytes: Vec<u8>, bytes: Vec<u8>,
} }
impl Manifest { impl Manifest {
pub fn iter( pub fn iter(
&self, &self,
) -> impl Iterator<Item = Result<ManifestEntry, HgError>> { ) -> impl Iterator<Item = Result<ManifestEntry, HgError>> {
self.bytes self.bytes
.split(|b| b == &b'\n') .split(|b| b == &b'\n')
.filter(|line| !line.is_empty()) .filter(|line| !line.is_empty())
.map(|line| { .map(ManifestEntry::from_raw)
let (path, rest) = line.split_2(b'\0').ok_or_else(|| {
HgError::corrupted("manifest line should contain \\0")
})?;
let path = HgPath::new(path);
let (hex_node_id, flags) = match rest.split_last() {
Some((&b'x', rest)) => (rest, Some(b'x')),
Some((&b'l', rest)) => (rest, Some(b'l')),
Some((&b't', rest)) => (rest, Some(b't')),
_ => (rest, None),
};
Ok(ManifestEntry {
path,
hex_node_id,
flags,
})
})
} }
/// If the given path is in this manifest, return its filelog node ID /// If the given path is in this manifest, return its filelog node ID
pub fn find_file( pub fn find_by_path(
&self, &self,
path: &HgPath, path: &HgPath,
) -> Result<Option<ManifestEntry>, HgError> { ) -> Result<Option<ManifestEntry>, HgError> {
// TODO: use binary search instead of linear scan. This may involve use std::cmp::Ordering::*;
// building (and caching) an index of the byte indicex of each manifest let path = path.as_bytes();
// line. // Both boundaries of this `&[u8]` slice are always at the boundary of
// an entry
// TODO: use try_find when available (if still using linear scan) let mut bytes = &*self.bytes;
// https://github.com/rust-lang/rust/issues/63178
for entry in self.iter() { // Binary search algorithm derived from `[T]::binary_search_by`
let entry = entry?; // <https://github.com/rust-lang/rust/blob/1.57.0/library/core/src/slice/mod.rs#L2221>
if entry.path == path { // except we don’t have a slice of entries. Instead we jump to the
return Ok(Some(entry)); // middle of the byte slice and look around for entry delimiters
// (newlines).
while let Some(entry_range) = Self::find_entry_near_middle_of(bytes)? {
let (entry_path, rest) =
ManifestEntry::split_path(&bytes[entry_range.clone()])?;
let cmp = entry_path.cmp(path);
if cmp == Less {
let after_newline = entry_range.end + 1;
bytes = &bytes[after_newline..];
} else if cmp == Greater {
bytes = &bytes[..entry_range.start];
} else {
return Ok(Some(ManifestEntry::from_path_and_rest(
entry_path, rest,
)));
} }
} }
Ok(None) Ok(None)
} }
/// If there is at least one, return the byte range of an entry *excluding*
/// the final newline.
fn find_entry_near_middle_of(
bytes: &[u8],
) -> Result<Option<std::ops::Range<usize>>, HgError> {
let len = bytes.len();
if len > 0 {
let middle = bytes.len() / 2;
// Integer division rounds down, so `middle < len`.
let (before, after) = bytes.split_at(middle);
let is_newline = |&byte: &u8| byte == b'\n';
let entry_start = match before.iter().rposition(is_newline) {
Some(i) => i + 1,
None => 0, // We choose the first entry in `bytes`
};
let entry_end = match after.iter().position(is_newline) {
Some(i) => {
// No `+ 1` here to exclude this newline from the range
middle + i
}
None => {
// In a well-formed manifest:
//
// * Since `len > 0`, `bytes` contains at least one entry
// * Every entry ends with a newline
// * Since `middle < len`, `after` contains at least the
// newline at the end of the last entry of `bytes`.
//
// We didn’t find a newline, so this manifest is not
// well-formed.
return Err(HgError::corrupted(
"manifest entry without \\n delimiter",
));
}
};
Ok(Some(entry_start..entry_end))
} else {
// len == 0
Ok(None)
}
}
} }
/// `Manifestlog` entry which knows how to interpret the `manifest` data bytes. /// `Manifestlog` entry which knows how to interpret the `manifest` data bytes.
#[derive(Debug)] #[derive(Debug)]
pub struct ManifestEntry<'manifest> { pub struct ManifestEntry<'manifest> {
pub path: &'manifest HgPath, pub path: &'manifest HgPath,
pub hex_node_id: &'manifest [u8], pub hex_node_id: &'manifest [u8],
/// `Some` values are b'x', b'l', or 't' /// `Some` values are b'x', b'l', or 't'
pub flags: Option<u8>, pub flags: Option<u8>,
} }
impl ManifestEntry<'_> { impl<'a> ManifestEntry<'a> {
fn split_path(bytes: &[u8]) -> Result<(&[u8], &[u8]), HgError> {
bytes.split_2(b'\0').ok_or_else(|| {
HgError::corrupted("manifest entry without \\0 delimiter")
})
}
fn from_path_and_rest(path: &'a [u8], rest: &'a [u8]) -> Self {
let (hex_node_id, flags) = match rest.split_last() {
Some((&b'x', rest)) => (rest, Some(b'x')),
Some((&b'l', rest)) => (rest, Some(b'l')),
Some((&b't', rest)) => (rest, Some(b't')),
_ => (rest, None),
};
Self {
path: HgPath::new(path),
hex_node_id,
flags,
}
}
fn from_raw(bytes: &'a [u8]) -> Result<Self, HgError> {
let (path, rest) = Self::split_path(bytes)?;
Ok(Self::from_path_and_rest(path, rest))
}
pub fn node_id(&self) -> Result<Node, HgError> { pub fn node_id(&self) -> Result<Node, HgError> {
Node::from_hex_for_repo(self.hex_node_id) Node::from_hex_for_repo(self.hex_node_id)
} }
} }

rust/rhg/src/commands/status.rs

Some(b'l') Some(b'l')
} else if has_exec_bit(&fs_metadata) { } else if has_exec_bit(&fs_metadata) {
Some(b'x') Some(b'x')
} else { } else {
None None
}; };
let entry = manifest let entry = manifest
.find_file(hg_path)? .find_by_path(hg_path)?
.expect("ambgious file not in p1"); .expect("ambgious file not in p1");
if entry.flags != fs_flags { if entry.flags != fs_flags {
return Ok(true); return Ok(true);
} }
let filelog = repo.filelog(hg_path)?; let filelog = repo.filelog(hg_path)?;
let fs_len = fs_metadata.len(); let fs_len = fs_metadata.len();
// TODO: check `fs_len` here like below, but based on // TODO: check `fs_len` here like below, but based on
// `RevlogEntry::uncompressed_len` without decompressing the full filelog // `RevlogEntry::uncompressed_len` without decompressing the full filelog