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

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 31498

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