This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10365

dirstate-tree: Add `WithBasename` wrapper for `HgPath`
ClosedPublic

Authored by SimonSapin on Apr 12 2021, 8:23 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG3c11c24b82b6: dirstate-tree: Add `WithBasename` wrapper for `HgPath`
rHG417ad7fe4a3b: dirstate-tree: Add `WithBasename` wrapper for `HgPath`
Summary

In the tree-shaped dirstate we want to have nodes representing files or
directories, where directory nodes contain a map associating "base" names
to child nodes for child files and directories.

Many dirstate operations expect a full path from the repository root, but
re-concatenating string from nested map keys all the time might be expensive.
Instead, WithBasename stores a full path for these operations but
behaves as its base name (last path component) for equality and comparison.

Additionally inclusive_ancestors provides the successive map keys
that are needed when inserting a new dirstate node at a given full path.

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.Apr 12 2021, 8:23 AM
baymax updated this revision to Diff 27049.Apr 19 2021, 11:02 AM

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

Alphare accepted this revision.Apr 19 2021, 11:36 AM
SimonSapin added a commit: rHG417ad7fe4a3b: dirstate-tree: Add `WithBasename` wrapper for `HgPath`.May 6 2021, 12:48 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG417ad7fe4a3b: dirstate-tree: Add `WithBasename` wrapper for `HgPath` (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 27640

rust/hg-core/src/dirstate_tree.rs

pub mod dirstate_map; pub mod dirstate_map;
pub mod dispatch; pub mod dispatch;
pub mod path_with_basename;

rust/hg-core/src/dirstate_tree/path_with_basename.rs

  • This file was added.
use crate::utils::hg_path::HgPath;
use std::borrow::Borrow;
/// Wraps `HgPath` or `HgPathBuf` to make it behave "as" its last path
/// component, a.k.a. its base name (as in Python’s `os.path.basename`), but
/// also allow recovering the full path.
///
/// "Behaving as" means that equality and comparison consider only the base
/// name, and `std::borrow::Borrow` is implemented to return only the base
/// name. This allows using the base name as a map key while still being able
/// to recover the full path, in a single memory allocation.
#[derive(Debug)]
pub struct WithBasename<T> {
full_path: T,
/// The position after the last slash separator in `full_path`, or `0`
/// if there is no slash.
base_name_start: usize,
}
impl<T> WithBasename<T> {
pub fn full_path(&self) -> &T {
&self.full_path
}
}
impl<T: AsRef<HgPath>> WithBasename<T> {
pub fn new(full_path: T) -> Self {
let base_name_start = if let Some(last_slash_position) = full_path
.as_ref()
.as_bytes()
.iter()
.rposition(|&byte| byte == b'/')
{
last_slash_position + 1
} else {
0
};
Self {
base_name_start,
full_path,
}
}
pub fn base_name(&self) -> &HgPath {
HgPath::new(
&self.full_path.as_ref().as_bytes()[self.base_name_start..],
)
}
}
impl<T: AsRef<HgPath>> Borrow<HgPath> for WithBasename<T> {
fn borrow(&self) -> &HgPath {
self.base_name()
}
}
impl<T: AsRef<HgPath> + PartialEq> PartialEq for WithBasename<T> {
fn eq(&self, other: &Self) -> bool {
self.base_name() == other.base_name()
}
}
impl<T: AsRef<HgPath> + Eq> Eq for WithBasename<T> {}
impl<T: AsRef<HgPath> + PartialOrd> PartialOrd for WithBasename<T> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
self.base_name().partial_cmp(other.base_name())
}
}
impl<T: AsRef<HgPath> + Ord> Ord for WithBasename<T> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.base_name().cmp(other.base_name())
}
}
impl<T: ?Sized + ToOwned> WithBasename<&'_ T> {
pub fn to_owned(&self) -> WithBasename<T::Owned> {
WithBasename {
full_path: self.full_path.to_owned(),
base_name_start: self.base_name_start,
}
}
}
impl<'a> WithBasename<&'a HgPath> {
/// Returns an iterator of `WithBasename<&HgPath>` for the ancestor
/// directory paths of the given `path`, as well as `path` itself.
///
/// For example, the full paths of inclusive ancestors of "a/b/c" are "a",
/// "a/b", and "a/b/c" in that order.
pub fn inclusive_ancestors_of(
path: &'a HgPath,
) -> impl Iterator<Item = WithBasename<&'a HgPath>> {
let mut slash_positions =
path.as_bytes().iter().enumerate().filter_map(|(i, &byte)| {
if byte == b'/' {
Some(i)
} else {
None
}
});
let mut opt_next_component_start = Some(0);
std::iter::from_fn(move || {
opt_next_component_start.take().map(|next_component_start| {
if let Some(slash_pos) = slash_positions.next() {
opt_next_component_start = Some(slash_pos + 1);
Self {
full_path: HgPath::new(&path.as_bytes()[..slash_pos]),
base_name_start: next_component_start,
}
} else {
// Not setting `opt_next_component_start` here: there will
// be no iteration after this one because `.take()` set it
// to `None`.
Self {
full_path: path,
base_name_start: next_component_start,
}
}
})
})
}
}
#[test]
fn test() {
let a = WithBasename::new(HgPath::new("a").to_owned());
assert_eq!(&**a.full_path(), HgPath::new(b"a"));
assert_eq!(a.base_name(), HgPath::new(b"a"));
let cba = WithBasename::new(HgPath::new("c/b/a").to_owned());
assert_eq!(&**cba.full_path(), HgPath::new(b"c/b/a"));
assert_eq!(cba.base_name(), HgPath::new(b"a"));
assert_eq!(a, cba);
let borrowed: &HgPath = cba.borrow();
assert_eq!(borrowed, HgPath::new("a"));
}
#[test]
fn test_inclusive_ancestors() {
let mut iter = WithBasename::inclusive_ancestors_of(HgPath::new("a/bb/c"));
let next = iter.next().unwrap();
assert_eq!(*next.full_path(), HgPath::new("a"));
assert_eq!(next.base_name(), HgPath::new("a"));
let next = iter.next().unwrap();
assert_eq!(*next.full_path(), HgPath::new("a/bb"));
assert_eq!(next.base_name(), HgPath::new("bb"));
let next = iter.next().unwrap();
assert_eq!(*next.full_path(), HgPath::new("a/bb/c"));
assert_eq!(next.base_name(), HgPath::new("c"));
assert!(iter.next().is_none());
}