This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9863

rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef
ClosedPublic

Authored by SimonSapin on Jan 25 2021, 4:13 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG645ee7225fab: rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef
Summary

The *Ref struct only existed to avoid allocating Vecs
when cloning NodePrefix, but we can avoid having Vec
in the first place by using an inline array instead.

This makes NodePrefix 21 bytes (with 1 for the length)
which is smaller than before as Vec alone is 24 bytes.

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.Jan 25 2021, 4:13 PM
SimonSapin updated this revision to Diff 25351.Jan 28 2021, 2:39 PM
Alphare accepted this revision.Jan 29 2021, 6:46 AM
Alphare added a subscriber: Alphare.

This patch has both logic changes and the Copy bound added, which makes it harder to read, but it looks ok. I know that splitting the series even further would be a lot of work so don't bother unless someone else wants you to.

SimonSapin added a commit: rHG645ee7225fab: rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef.Feb 1 2021, 12:34 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG645ee7225fab: rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 25425

rust/Cargo.lock

name = "hermit-abi" name = "hermit-abi"
version = "0.1.17" version = "0.1.17"
source = "registry+https://github.com/rust-lang/crates.io-index" source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [ dependencies = [
"libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)", "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
] ]
[[package]] [[package]]
name = "hex"
version = "0.4.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
[[package]]
name = "hg-core" name = "hg-core"
version = "0.1.0" version = "0.1.0"
dependencies = [ dependencies = [
"byteorder 1.3.4 (registry+https://github.com/rust-lang/crates.io-index)", "byteorder 1.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
"bytes-cast 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "bytes-cast 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
"clap 2.33.3 (registry+https://github.com/rust-lang/crates.io-index)", "clap 2.33.3 (registry+https://github.com/rust-lang/crates.io-index)",
"crossbeam-channel 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)", "crossbeam-channel 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)",
"flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)", "flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)",
"format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)", "format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
"hex 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
"im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)", "im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
"lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
"log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)", "log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)",
"memchr 2.3.4 (registry+https://github.com/rust-lang/crates.io-index)", "memchr 2.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
"memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)", "memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
"micro-timer 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", "micro-timer 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
"pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)", "pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
"rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)", "rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
"checksum flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)" = "7411863d55df97a419aa64cb4d2f167103ea9d767e2c54a1868b7ac3f6b47129" "checksum flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)" = "7411863d55df97a419aa64cb4d2f167103ea9d767e2c54a1868b7ac3f6b47129"
"checksum format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1a7374eb574cd29ae45878554298091c554c3286a17b3afa440a3e2710ae0790" "checksum format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1a7374eb574cd29ae45878554298091c554c3286a17b3afa440a3e2710ae0790"
"checksum format-bytes-macros 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "4edcc04201cea17a0e6b937adebd46b93fba09924c7e6ed8c515a35ce8432cbc" "checksum format-bytes-macros 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "4edcc04201cea17a0e6b937adebd46b93fba09924c7e6ed8c515a35ce8432cbc"
"checksum fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba" "checksum fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba"
"checksum gcc 0.3.55 (registry+https://github.com/rust-lang/crates.io-index)" = "8f5f3913fa0bfe7ee1fd8248b6b9f42a5af4b9d65ec2dd2c3c26132b950ecfc2" "checksum gcc 0.3.55 (registry+https://github.com/rust-lang/crates.io-index)" = "8f5f3913fa0bfe7ee1fd8248b6b9f42a5af4b9d65ec2dd2c3c26132b950ecfc2"
"checksum getrandom 0.1.15 (registry+https://github.com/rust-lang/crates.io-index)" = "fc587bc0ec293155d5bfa6b9891ec18a1e330c234f896ea47fbada4cadbe47e6" "checksum getrandom 0.1.15 (registry+https://github.com/rust-lang/crates.io-index)" = "fc587bc0ec293155d5bfa6b9891ec18a1e330c234f896ea47fbada4cadbe47e6"
"checksum glob 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "9b919933a397b79c37e33b77bb2aa3dc8eb6e165ad809e58ff75bc7db2e34574" "checksum glob 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "9b919933a397b79c37e33b77bb2aa3dc8eb6e165ad809e58ff75bc7db2e34574"
"checksum hermit-abi 0.1.17 (registry+https://github.com/rust-lang/crates.io-index)" = "5aca5565f760fb5b220e499d72710ed156fdb74e631659e99377d9ebfbd13ae8" "checksum hermit-abi 0.1.17 (registry+https://github.com/rust-lang/crates.io-index)" = "5aca5565f760fb5b220e499d72710ed156fdb74e631659e99377d9ebfbd13ae8"
"checksum hex 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "644f9158b2f133fd50f5fb3242878846d9eb792e445c893805ff0e3824006e35"
"checksum humantime 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "df004cfca50ef23c36850aaaa59ad52cc70d0e90243c3c7737a4dd32dc7a3c4f" "checksum humantime 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "df004cfca50ef23c36850aaaa59ad52cc70d0e90243c3c7737a4dd32dc7a3c4f"
"checksum im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3ca8957e71f04a205cb162508f9326aea04676c8dfd0711220190d6b83664f3f" "checksum im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3ca8957e71f04a205cb162508f9326aea04676c8dfd0711220190d6b83664f3f"
"checksum itertools 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "284f18f85651fe11e8a991b2adb42cb078325c996ed026d994719efcfca1d54b" "checksum itertools 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "284f18f85651fe11e8a991b2adb42cb078325c996ed026d994719efcfca1d54b"
"checksum jobserver 0.1.21 (registry+https://github.com/rust-lang/crates.io-index)" = "5c71313ebb9439f74b00d9d2dcec36440beaf57a6aa0623068441dd7cd81a7f2" "checksum jobserver 0.1.21 (registry+https://github.com/rust-lang/crates.io-index)" = "5c71313ebb9439f74b00d9d2dcec36440beaf57a6aa0623068441dd7cd81a7f2"
"checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646" "checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
"checksum libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)" = "1482821306169ec4d07f6aca392a4681f66c75c9918aa49641a2595db64053cb" "checksum libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)" = "1482821306169ec4d07f6aca392a4681f66c75c9918aa49641a2595db64053cb"
"checksum libz-sys 1.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "602113192b08db8f38796c4e85c39e960c145965140e918018bcde1952429655" "checksum libz-sys 1.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "602113192b08db8f38796c4e85c39e960c145965140e918018bcde1952429655"
"checksum log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)" = "4fabed175da42fed1fa0746b0ea71f412aa9d35e76e95e59b192c64b9dc2bf8b" "checksum log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)" = "4fabed175da42fed1fa0746b0ea71f412aa9d35e76e95e59b192c64b9dc2bf8b"

rust/hg-core/Cargo.toml

[package] [package]
name = "hg-core" name = "hg-core"
version = "0.1.0" version = "0.1.0"
authors = ["Georges Racinet <gracinet@anybox.fr>"] authors = ["Georges Racinet <gracinet@anybox.fr>"]
description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)" description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)"
edition = "2018" edition = "2018"
[lib] [lib]
name = "hg" name = "hg"
[dependencies] [dependencies]
bytes-cast = "0.1" bytes-cast = "0.1"
byteorder = "1.3.4" byteorder = "1.3.4"
hex = "0.4.2"
im-rc = "15.0.*" im-rc = "15.0.*"
lazy_static = "1.4.0" lazy_static = "1.4.0"
memchr = "2.3.3" memchr = "2.3.3"
rand = "0.7.3" rand = "0.7.3"
rand_pcg = "0.2.1" rand_pcg = "0.2.1"
rand_distr = "0.2.2" rand_distr = "0.2.2"
rayon = "1.3.0" rayon = "1.3.0"
regex = "1.3.9" regex = "1.3.9"

rust/hg-core/src/operations/cat.rs

let changelog = Changelog::open(repo)?; let changelog = Changelog::open(repo)?;
let manifest = Manifest::open(repo)?; let manifest = Manifest::open(repo)?;
let changelog_entry = match rev.parse::<Revision>() { let changelog_entry = match rev.parse::<Revision>() {
Ok(rev) => changelog.get_rev(rev)?, Ok(rev) => changelog.get_rev(rev)?,
_ => { _ => {
let changelog_node = NodePrefix::from_hex(&rev) let changelog_node = NodePrefix::from_hex(&rev)
.map_err(|_| CatRevErrorKind::InvalidRevision)?; .map_err(|_| CatRevErrorKind::InvalidRevision)?;
changelog.get_node(changelog_node.borrow())? changelog.get_node(changelog_node)?
} }
}; };
let manifest_node = Node::from_hex(&changelog_entry.manifest_node()?) let manifest_node = Node::from_hex(&changelog_entry.manifest_node()?)
.map_err(|_| CatRevErrorKind::CorruptedRevlog)?; .map_err(|_| CatRevErrorKind::CorruptedRevlog)?;
let manifest_entry = manifest.get_node((&manifest_node).into())?; let manifest_entry = manifest.get_node(manifest_node.into())?;
let mut bytes = vec![]; let mut bytes = vec![];
for (manifest_file, node_bytes) in manifest_entry.files_with_nodes() { for (manifest_file, node_bytes) in manifest_entry.files_with_nodes() {
for cat_file in files.iter() { for cat_file in files.iter() {
if cat_file.as_bytes() == manifest_file.as_bytes() { if cat_file.as_bytes() == manifest_file.as_bytes() {
let index_path = store_path(manifest_file, b".i"); let index_path = store_path(manifest_file, b".i");
let data_path = store_path(manifest_file, b".d"); let data_path = store_path(manifest_file, b".d");
let file_log = let file_log =
Revlog::open(repo, &index_path, Some(&data_path))?; Revlog::open(repo, &index_path, Some(&data_path))?;
let file_node = Node::from_hex(node_bytes) let file_node = Node::from_hex(node_bytes)
.map_err(|_| CatRevErrorKind::CorruptedRevlog)?; .map_err(|_| CatRevErrorKind::CorruptedRevlog)?;
let file_rev = file_log.get_node_rev((&file_node).into())?; let file_rev = file_log.get_node_rev(file_node.into())?;
let data = file_log.get_rev_data(file_rev)?; let data = file_log.get_rev_data(file_rev)?;
if data.starts_with(&METADATA_DELIMITER) { if data.starts_with(&METADATA_DELIMITER) {
let end_delimiter_position = data let end_delimiter_position = data
[METADATA_DELIMITER.len()..] [METADATA_DELIMITER.len()..]
.windows(METADATA_DELIMITER.len()) .windows(METADATA_DELIMITER.len())
.position(|bytes| bytes == METADATA_DELIMITER); .position(|bytes| bytes == METADATA_DELIMITER);
if let Some(position) = end_delimiter_position { if let Some(position) = end_delimiter_position {
let offset = METADATA_DELIMITER.len() * 2; let offset = METADATA_DELIMITER.len() * 2;

rust/hg-core/src/operations/debugdata.rs

}; };
let revlog = Revlog::open(repo, index_file, None)?; let revlog = Revlog::open(repo, index_file, None)?;
let data = match rev.parse::<Revision>() { let data = match rev.parse::<Revision>() {
Ok(rev) => revlog.get_rev_data(rev)?, Ok(rev) => revlog.get_rev_data(rev)?,
_ => { _ => {
let node = NodePrefix::from_hex(&rev) let node = NodePrefix::from_hex(&rev)
.map_err(|_| DebugDataErrorKind::InvalidRevision)?; .map_err(|_| DebugDataErrorKind::InvalidRevision)?;
let rev = revlog.get_node_rev(node.borrow())?; let rev = revlog.get_node_rev(node)?;
revlog.get_rev_data(rev)? revlog.get_rev_data(rev)?
} }
}; };
Ok(data) Ok(data)
} }

rust/hg-core/src/operations/list_tracked_files.rs

let changelog = Changelog::open(repo)?; let changelog = Changelog::open(repo)?;
let manifest = Manifest::open(repo)?; let manifest = Manifest::open(repo)?;
let changelog_entry = match rev.parse::<Revision>() { let changelog_entry = match rev.parse::<Revision>() {
Ok(rev) => changelog.get_rev(rev)?, Ok(rev) => changelog.get_rev(rev)?,
_ => { _ => {
let changelog_node = NodePrefix::from_hex(&rev) let changelog_node = NodePrefix::from_hex(&rev)
.or(Err(ListRevTrackedFilesErrorKind::InvalidRevision))?; .or(Err(ListRevTrackedFilesErrorKind::InvalidRevision))?;
changelog.get_node(changelog_node.borrow())? changelog.get_node(changelog_node)?
} }
}; };
let manifest_node = Node::from_hex(&changelog_entry.manifest_node()?) let manifest_node = Node::from_hex(&changelog_entry.manifest_node()?)
.or(Err(ListRevTrackedFilesErrorKind::CorruptedRevlog))?; .or(Err(ListRevTrackedFilesErrorKind::CorruptedRevlog))?;
let manifest_entry = manifest.get_node((&manifest_node).into())?; let manifest_entry = manifest.get_node(manifest_node.into())?;
Ok(FilesForRev(manifest_entry)) Ok(FilesForRev(manifest_entry))
} }
pub struct FilesForRev(ManifestEntry); pub struct FilesForRev(ManifestEntry);
impl FilesForRev { impl FilesForRev {
pub fn iter(&self) -> impl Iterator<Item = &HgPath> { pub fn iter(&self) -> impl Iterator<Item = &HgPath> {
self.0.files() self.0.files()
} }
} }

rust/hg-core/src/revlog.rs

// Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
// and Mercurial contributors // and Mercurial contributors
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Mercurial concepts for handling revision history //! Mercurial concepts for handling revision history
pub mod node; pub mod node;
pub mod nodemap; pub mod nodemap;
mod nodemap_docket; mod nodemap_docket;
pub mod path_encode; pub mod path_encode;
pub use node::{FromHexError, Node, NodePrefix, NodePrefixRef}; pub use node::{FromHexError, Node, NodePrefix};
pub mod changelog; pub mod changelog;
pub mod index; pub mod index;
pub mod manifest; pub mod manifest;
pub mod patch; pub mod patch;
pub mod revlog; pub mod revlog;
/// Mercurial revision numbers /// Mercurial revision numbers
/// ///

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

use crate::repo::Repo; use crate::repo::Repo;
use crate::revlog::revlog::{Revlog, RevlogError}; use crate::revlog::revlog::{Revlog, RevlogError};
use crate::revlog::NodePrefixRef; use crate::revlog::NodePrefix;
use crate::revlog::Revision; use crate::revlog::Revision;
/// A specialized `Revlog` to work with `changelog` data format. /// A specialized `Revlog` to work with `changelog` data format.
pub struct Changelog { pub struct Changelog {
/// The generic `revlog` format. /// The generic `revlog` format.
revlog: Revlog, revlog: Revlog,
} }
impl Changelog { impl Changelog {
/// Open the `changelog` of a repository given by its root. /// Open the `changelog` of a repository given by its root.
pub fn open(repo: &Repo) -> Result<Self, RevlogError> { pub fn open(repo: &Repo) -> Result<Self, RevlogError> {
let revlog = Revlog::open(repo, "00changelog.i", None)?; let revlog = Revlog::open(repo, "00changelog.i", None)?;
Ok(Self { revlog }) Ok(Self { revlog })
} }
/// Return the `ChangelogEntry` a given node id. /// Return the `ChangelogEntry` a given node id.
pub fn get_node( pub fn get_node(
&self, &self,
node: NodePrefixRef, node: NodePrefix,
) -> Result<ChangelogEntry, RevlogError> { ) -> Result<ChangelogEntry, RevlogError> {
let rev = self.revlog.get_node_rev(node)?; let rev = self.revlog.get_node_rev(node)?;
self.get_rev(rev) self.get_rev(rev)
} }
/// Return the `ChangelogEntry` of a given node revision. /// Return the `ChangelogEntry` of a given node revision.
pub fn get_rev( pub fn get_rev(
&self, &self,

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

use crate::repo::Repo; use crate::repo::Repo;
use crate::revlog::revlog::{Revlog, RevlogError}; use crate::revlog::revlog::{Revlog, RevlogError};
use crate::revlog::NodePrefixRef; use crate::revlog::NodePrefix;
use crate::revlog::Revision; use crate::revlog::Revision;
use crate::utils::hg_path::HgPath; use crate::utils::hg_path::HgPath;
/// A specialized `Revlog` to work with `manifest` data format. /// A specialized `Revlog` to work with `manifest` data format.
pub struct Manifest { pub struct Manifest {
/// The generic `revlog` format. /// The generic `revlog` format.
revlog: Revlog, revlog: Revlog,
} }
impl Manifest { impl Manifest {
/// Open the `manifest` of a repository given by its root. /// Open the `manifest` of a repository given by its root.
pub fn open(repo: &Repo) -> Result<Self, RevlogError> { pub fn open(repo: &Repo) -> Result<Self, RevlogError> {
let revlog = Revlog::open(repo, "00manifest.i", None)?; let revlog = Revlog::open(repo, "00manifest.i", None)?;
Ok(Self { revlog }) Ok(Self { revlog })
} }
/// Return the `ManifestEntry` of a given node id. /// Return the `ManifestEntry` of a given node id.
pub fn get_node( pub fn get_node(
&self, &self,
node: NodePrefixRef, node: NodePrefix,
) -> Result<ManifestEntry, RevlogError> { ) -> Result<ManifestEntry, RevlogError> {
let rev = self.revlog.get_node_rev(node)?; let rev = self.revlog.get_node_rev(node)?;
self.get_rev(rev) self.get_rev(rev)
} }
/// Return the `ManifestEntry` of a given node revision. /// Return the `ManifestEntry` of a given node revision.
pub fn get_rev( pub fn get_rev(
&self, &self,

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

// Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net> // Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Definitions and utilities for Revision nodes //! Definitions and utilities for Revision nodes
//! //!
//! In Mercurial code base, it is customary to call "a node" the binary SHA //! In Mercurial code base, it is customary to call "a node" the binary SHA
//! of a revision. //! of a revision.
use bytes_cast::BytesCast; use bytes_cast::BytesCast;
use hex::{self, FromHex}; use std::convert::{TryFrom, TryInto};
use std::convert::TryFrom;
use std::fmt; use std::fmt;
/// The length in bytes of a `Node` /// The length in bytes of a `Node`
/// ///
/// This constant is meant to ease refactors of this module, and /// This constant is meant to ease refactors of this module, and
/// are private so that calling code does not expect all nodes have /// are private so that calling code does not expect all nodes have
/// the same size, should we support several formats concurrently in /// the same size, should we support several formats concurrently in
/// the future. /// the future.
/// All other callers outside of unit tests should just handle `Node` values /// All other callers outside of unit tests should just handle `Node` values
/// and never make any assumption on the actual length, using [`nybbles_len`] /// and never make any assumption on the actual length, using [`nybbles_len`]
/// if they need a loop boundary. /// if they need a loop boundary.
/// ///
/// All methods that create a `Node` either take a type that enforces /// All methods that create a `Node` either take a type that enforces
/// the size or return an error at runtime. /// the size or return an error at runtime.
/// ///
/// [`nybbles_len`]: #method.nybbles_len /// [`nybbles_len`]: #method.nybbles_len
#[derive(Clone, Debug, PartialEq, BytesCast)] #[derive(Copy, Clone, Debug, PartialEq, BytesCast)]
#[repr(transparent)] #[repr(transparent)]
pub struct Node { pub struct Node {
data: NodeData, data: NodeData,
} }
/// The node value for NULL_REVISION /// The node value for NULL_REVISION
pub const NULL_NODE: Node = Node { pub const NULL_NODE: Node = Node {
data: [0; NODE_BYTES_LENGTH], data: [0; NODE_BYTES_LENGTH],
}; };
impl From<NodeData> for Node { impl From<NodeData> for Node {
fn from(data: NodeData) -> Node { fn from(data: NodeData) -> Node {
Node { data } Node { data }
} }
} }
/// Return an error if the slice has an unexpected length /// Return an error if the slice has an unexpected length
impl<'a> TryFrom<&'a [u8]> for &'a Node { impl<'a> TryFrom<&'a [u8]> for &'a Node {
type Error = (); type Error = ();
#[inline] #[inline]
fn try_from(bytes: &'a [u8]) -> Result<&'a Node, Self::Error> { fn try_from(bytes: &'a [u8]) -> Result<Self, Self::Error> {
match Node::from_bytes(bytes) { match Node::from_bytes(bytes) {
Ok((node, rest)) if rest.is_empty() => Ok(node), Ok((node, rest)) if rest.is_empty() => Ok(node),
_ => Err(()), _ => Err(()),
} }
} }
} }
/// Return an error if the slice has an unexpected length
impl TryFrom<&'_ [u8]> for Node {
type Error = std::array::TryFromSliceError;
#[inline]
fn try_from(bytes: &'_ [u8]) -> Result<Self, Self::Error> {
let data = bytes.try_into()?;
Ok(Self { data })
}
}
impl fmt::LowerHex for Node { impl fmt::LowerHex for Node {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
for &byte in &self.data { for &byte in &self.data {
write!(f, "{:02x}", byte)? write!(f, "{:02x}", byte)?
} }
Ok(()) Ok(())
} }
} }
/// Convert from hexadecimal string representation /// Convert from hexadecimal string representation
/// ///
/// Exact length is required. /// Exact length is required.
/// ///
/// To be used in FFI and I/O only, in order to facilitate future /// To be used in FFI and I/O only, in order to facilitate future
/// changes of hash format. /// changes of hash format.
pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Node, FromHexError> { pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Node, FromHexError> {
Ok(NodeData::from_hex(hex.as_ref()) let prefix = NodePrefix::from_hex(hex)?;
.map_err(|_| FromHexError)? if prefix.nybbles_len() == NODE_NYBBLES_LENGTH {
.into()) Ok(Self { data: prefix.data })
} else {
Err(FromHexError)
}
} }
/// Provide access to binary data /// Provide access to binary data
/// ///
/// This is needed by FFI layers, for instance to return expected /// This is needed by FFI layers, for instance to return expected
/// binary values to Python. /// binary values to Python.
pub fn as_bytes(&self) -> &[u8] { pub fn as_bytes(&self) -> &[u8] {
&self.data &self.data
} }
} }
/// The beginning of a binary revision SHA. /// The beginning of a binary revision SHA.
/// ///
/// Since it can potentially come from an hexadecimal representation with /// Since it can potentially come from an hexadecimal representation with
/// odd length, it needs to carry around whether the last 4 bits are relevant /// odd length, it needs to carry around whether the last 4 bits are relevant
/// or not. /// or not.
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq, Copy, Clone)]
pub struct NodePrefix { pub struct NodePrefix {
buf: Vec<u8>, /// In `1..=NODE_NYBBLES_LENGTH`
is_odd: bool, nybbles_len: u8,
/// The first `4 * length_in_nybbles` bits are used (considering bits
/// within a bytes in big-endian: most significant first), the rest
/// are zero.
data: NodeData,
} }
impl NodePrefix { impl NodePrefix {
/// Convert from hexadecimal string representation /// Convert from hexadecimal string representation
/// ///
/// Similarly to `hex::decode`, can be used with Unicode string types /// Similarly to `hex::decode`, can be used with Unicode string types
/// (`String`, `&str`) as well as bytes. /// (`String`, `&str`) as well as bytes.
/// ///
/// To be used in FFI and I/O only, in order to facilitate future /// To be used in FFI and I/O only, in order to facilitate future
/// changes of hash format. /// changes of hash format.
pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Self, FromHexError> { pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Self, FromHexError> {
let hex = hex.as_ref(); let hex = hex.as_ref();
let len = hex.len(); let len = hex.len();
if len > NODE_NYBBLES_LENGTH || len == 0 { if len > NODE_NYBBLES_LENGTH || len == 0 {
return Err(FromHexError); return Err(FromHexError);
} }
let is_odd = len % 2 == 1; let mut data = [0; NODE_BYTES_LENGTH];
let even_part = if is_odd { &hex[..len - 1] } else { hex }; let mut nybbles_len = 0;
let mut buf: Vec<u8> = for &ascii_byte in hex {
Vec::from_hex(&even_part).map_err(|_| FromHexError)?; let nybble = match char::from(ascii_byte).to_digit(16) {
Some(digit) => digit as u8,
if is_odd { None => return Err(FromHexError),
let latest_char = char::from(hex[len - 1]); };
let latest_nybble = // Fill in the upper half of a byte first, then the lower half.
latest_char.to_digit(16).ok_or_else(|| FromHexError)? as u8; let shift = if nybbles_len % 2 == 0 { 4 } else { 0 };
buf.push(latest_nybble << 4); data[nybbles_len as usize / 2] |= nybble << shift;
} nybbles_len += 1;
Ok(NodePrefix { buf, is_odd })
}
pub fn borrow(&self) -> NodePrefixRef {
NodePrefixRef {
buf: &self.buf,
is_odd: self.is_odd,
}
}
} }
Ok(Self { data, nybbles_len })
#[derive(Clone, Debug, PartialEq)]
pub struct NodePrefixRef<'a> {
buf: &'a [u8],
is_odd: bool,
} }
impl<'a> NodePrefixRef<'a> { pub fn nybbles_len(&self) -> usize {
pub fn len(&self) -> usize { self.nybbles_len as _
if self.is_odd {
self.buf.len() * 2 - 1
} else {
self.buf.len() * 2
}
} }
pub fn is_prefix_of(&self, node: &Node) -> bool { pub fn is_prefix_of(&self, node: &Node) -> bool {
if self.is_odd { let full_bytes = self.nybbles_len() / 2;
let buf = self.buf; if self.data[..full_bytes] != node.data[..full_bytes] {
let last_pos = buf.len() - 1; return false;
node.data.starts_with(buf.split_at(last_pos).0)
&& node.data[last_pos] >> 4 == buf[last_pos] >> 4
} else {
node.data.starts_with(self.buf)
} }
if self.nybbles_len() % 2 == 0 {
return true;
}
let last = self.nybbles_len() - 1;
self.get_nybble(last) == node.get_nybble(last)
} }
/// Retrieve the `i`th half-byte from the prefix. /// Retrieve the `i`th half-byte from the prefix.
/// ///
/// This is also the `i`th hexadecimal digit in numeric form, /// This is also the `i`th hexadecimal digit in numeric form,
/// also called a [nybble](https://en.wikipedia.org/wiki/Nibble). /// also called a [nybble](https://en.wikipedia.org/wiki/Nibble).
pub fn get_nybble(&self, i: usize) -> u8 { pub fn get_nybble(&self, i: usize) -> u8 {
assert!(i < self.len()); assert!(i < self.nybbles_len());
get_nybble(self.buf, i) get_nybble(&self.data, i)
}
fn iter_nybbles(&self) -> impl Iterator<Item = u8> + '_ {
(0..self.nybbles_len()).map(move |i| get_nybble(&self.data, i))
} }
/// Return the index first nybble that's different from `node` /// Return the index first nybble that's different from `node`
/// ///
/// If the return value is `None` that means that `self` is /// If the return value is `None` that means that `self` is
/// a prefix of `node`, but the current method is a bit slower /// a prefix of `node`, but the current method is a bit slower
/// than `is_prefix_of`. /// than `is_prefix_of`.
/// ///
/// Returned index is as in `get_nybble`, i.e., starting at 0. /// Returned index is as in `get_nybble`, i.e., starting at 0.
pub fn first_different_nybble(&self, node: &Node) -> Option<usize> { pub fn first_different_nybble(&self, node: &Node) -> Option<usize> {
let buf = self.buf; self.iter_nybbles()
let until = if self.is_odd { .zip(NodePrefix::from(*node).iter_nybbles())
buf.len() - 1 .position(|(a, b)| a != b)
} else {
buf.len()
};
for (i, item) in buf.iter().enumerate().take(until) {
if *item != node.data[i] {
return if *item & 0xf0 == node.data[i] & 0xf0 {
Some(2 * i + 1)
} else {
Some(2 * i)
};
} }
} }
if self.is_odd && buf[until] & 0xf0 != node.data[until] & 0xf0 {
Some(until * 2) impl fmt::LowerHex for NodePrefix {
} else { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
None let full_bytes = self.nybbles_len() / 2;
for &byte in &self.data[..full_bytes] {
write!(f, "{:02x}", byte)?
}
if self.nybbles_len() % 2 == 1 {
let last = self.nybbles_len() - 1;
write!(f, "{:x}", self.get_nybble(last))?
}
Ok(())
}
}
/// A shortcut for full `Node` references
impl From<&'_ Node> for NodePrefix {
fn from(node: &'_ Node) -> Self {
NodePrefix {
nybbles_len: node.nybbles_len() as _,
data: node.data,
} }
} }
} }
/// A shortcut for full `Node` references /// A shortcut for full `Node` references
impl<'a> From<&'a Node> for NodePrefixRef<'a> { impl From<Node> for NodePrefix {
fn from(node: &'a Node) -> Self { fn from(node: Node) -> Self {
NodePrefixRef { NodePrefix {
buf: &node.data, nybbles_len: node.nybbles_len() as _,
is_odd: false, data: node.data,
} }
} }
} }
impl PartialEq<Node> for NodePrefixRef<'_> { impl PartialEq<Node> for NodePrefix {
fn eq(&self, other: &Node) -> bool { fn eq(&self, other: &Node) -> bool {
!self.is_odd && self.buf == other.data Self::from(*other) == *self
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
fn sample_node() -> Node { const SAMPLE_NODE_HEX: &str = "0123456789abcdeffedcba9876543210deadbeef";
let mut data = [0; NODE_BYTES_LENGTH]; const SAMPLE_NODE: Node = Node {
data.copy_from_slice(&[ data: [
0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba,
0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef, 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef,
]); ],
data.into() };
}
/// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH` /// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH`
///check_hash /// The padding is made with zeros.
/// The padding is made with zeros
pub fn hex_pad_right(hex: &str) -> String { pub fn hex_pad_right(hex: &str) -> String {
let mut res = hex.to_string(); let mut res = hex.to_string();
while res.len() < NODE_NYBBLES_LENGTH { while res.len() < NODE_NYBBLES_LENGTH {
res.push('0'); res.push('0');
} }
res res
} }
fn sample_node_hex() -> String {
hex_pad_right("0123456789abcdeffedcba9876543210deadbeef")
}
#[test] #[test]
fn test_node_from_hex() { fn test_node_from_hex() {
assert_eq!(Node::from_hex(&sample_node_hex()).unwrap(), sample_node()); let not_hex = "012... oops";
let too_short = "0123";
let mut short = hex_pad_right("0123"); let too_long = format!("{}0", SAMPLE_NODE_HEX);
short.pop(); assert_eq!(Node::from_hex(SAMPLE_NODE_HEX).unwrap(), SAMPLE_NODE);
short.pop(); assert!(Node::from_hex(not_hex).is_err());
assert!(Node::from_hex(&short).is_err()); assert!(Node::from_hex(too_short).is_err());
assert!(Node::from_hex(&too_long).is_err());
let not_hex = hex_pad_right("012... oops");
assert!(Node::from_hex(&not_hex).is_err(),);
} }
#[test] #[test]
fn test_node_encode_hex() { fn test_node_encode_hex() {
assert_eq!(format!("{:x}", sample_node()), sample_node_hex()); assert_eq!(format!("{:x}", SAMPLE_NODE), SAMPLE_NODE_HEX);
} }
#[test] #[test]
fn test_prefix_from_hex() -> Result<(), FromHexError> { fn test_prefix_from_to_hex() -> Result<(), FromHexError> {
assert_eq!(format!("{:x}", NodePrefix::from_hex("0e1")?), "0e1");
assert_eq!(format!("{:x}", NodePrefix::from_hex("0e1a")?), "0e1a");
assert_eq!( assert_eq!(
NodePrefix::from_hex("0e1")?, format!("{:x}", NodePrefix::from_hex(SAMPLE_NODE_HEX)?),
NodePrefix { SAMPLE_NODE_HEX
buf: vec![14, 16],
is_odd: true
}
); );
assert_eq!(
NodePrefix::from_hex("0e1a")?,
NodePrefix {
buf: vec![14, 26],
is_odd: false
}
);
// checking limit case
let node_as_vec = sample_node().data.iter().cloned().collect();
assert_eq!(
NodePrefix::from_hex(sample_node_hex())?,
NodePrefix {
buf: node_as_vec,
is_odd: false
}
);
Ok(()) Ok(())
} }
#[test] #[test]
fn test_prefix_from_hex_errors() { fn test_prefix_from_hex_errors() {
assert!(NodePrefix::from_hex("testgr").is_err()); assert!(NodePrefix::from_hex("testgr").is_err());
let mut long = format!("{:x}", NULL_NODE); let mut long = format!("{:x}", NULL_NODE);
long.push('c'); long.push('c');
assert!(NodePrefix::from_hex(&long).is_err()) assert!(NodePrefix::from_hex(&long).is_err())
} }
#[test] #[test]
fn test_is_prefix_of() -> Result<(), FromHexError> { fn test_is_prefix_of() -> Result<(), FromHexError> {
let mut node_data = [0; NODE_BYTES_LENGTH]; let mut node_data = [0; NODE_BYTES_LENGTH];
node_data[0] = 0x12; node_data[0] = 0x12;
node_data[1] = 0xca; node_data[1] = 0xca;
let node = Node::from(node_data); let node = Node::from(node_data);
assert!(NodePrefix::from_hex("12")?.borrow().is_prefix_of(&node)); assert!(NodePrefix::from_hex("12")?.is_prefix_of(&node));
assert!(!NodePrefix::from_hex("1a")?.borrow().is_prefix_of(&node)); assert!(!NodePrefix::from_hex("1a")?.is_prefix_of(&node));
assert!(NodePrefix::from_hex("12c")?.borrow().is_prefix_of(&node)); assert!(NodePrefix::from_hex("12c")?.is_prefix_of(&node));
assert!(!NodePrefix::from_hex("12d")?.borrow().is_prefix_of(&node)); assert!(!NodePrefix::from_hex("12d")?.is_prefix_of(&node));
Ok(()) Ok(())
} }
#[test] #[test]
fn test_get_nybble() -> Result<(), FromHexError> { fn test_get_nybble() -> Result<(), FromHexError> {
let prefix = NodePrefix::from_hex("dead6789cafe")?; let prefix = NodePrefix::from_hex("dead6789cafe")?;
assert_eq!(prefix.borrow().get_nybble(0), 13); assert_eq!(prefix.get_nybble(0), 13);
assert_eq!(prefix.borrow().get_nybble(7), 9); assert_eq!(prefix.get_nybble(7), 9);
Ok(()) Ok(())
} }
#[test] #[test]
fn test_first_different_nybble_even_prefix() { fn test_first_different_nybble_even_prefix() {
let prefix = NodePrefix::from_hex("12ca").unwrap(); let prefix = NodePrefix::from_hex("12ca").unwrap();
let prefref = prefix.borrow();
let mut node = Node::from([0; NODE_BYTES_LENGTH]); let mut node = Node::from([0; NODE_BYTES_LENGTH]);
assert_eq!(prefref.first_different_nybble(&node), Some(0)); assert_eq!(prefix.first_different_nybble(&node), Some(0));
node.data[0] = 0x13; node.data[0] = 0x13;
assert_eq!(prefref.first_different_nybble(&node), Some(1)); assert_eq!(prefix.first_different_nybble(&node), Some(1));
node.data[0] = 0x12; node.data[0] = 0x12;
assert_eq!(prefref.first_different_nybble(&node), Some(2)); assert_eq!(prefix.first_different_nybble(&node), Some(2));
node.data[1] = 0xca; node.data[1] = 0xca;
// now it is a prefix // now it is a prefix
assert_eq!(prefref.first_different_nybble(&node), None); assert_eq!(prefix.first_different_nybble(&node), None);
} }
#[test] #[test]
fn test_first_different_nybble_odd_prefix() { fn test_first_different_nybble_odd_prefix() {
let prefix = NodePrefix::from_hex("12c").unwrap(); let prefix = NodePrefix::from_hex("12c").unwrap();
let prefref = prefix.borrow();
let mut node = Node::from([0; NODE_BYTES_LENGTH]); let mut node = Node::from([0; NODE_BYTES_LENGTH]);
assert_eq!(prefref.first_different_nybble(&node), Some(0)); assert_eq!(prefix.first_different_nybble(&node), Some(0));
node.data[0] = 0x13; node.data[0] = 0x13;
assert_eq!(prefref.first_different_nybble(&node), Some(1)); assert_eq!(prefix.first_different_nybble(&node), Some(1));
node.data[0] = 0x12; node.data[0] = 0x12;
assert_eq!(prefref.first_different_nybble(&node), Some(2)); assert_eq!(prefix.first_different_nybble(&node), Some(2));
node.data[1] = 0xca; node.data[1] = 0xca;
// now it is a prefix // now it is a prefix
assert_eq!(prefref.first_different_nybble(&node), None); assert_eq!(prefix.first_different_nybble(&node), None);
} }
} }
#[cfg(test)] #[cfg(test)]
pub use tests::hex_pad_right; pub use tests::hex_pad_right;

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

// Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
// and Mercurial contributors // and Mercurial contributors
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Indexing facilities for fast retrieval of `Revision` from `Node` //! Indexing facilities for fast retrieval of `Revision` from `Node`
//! //!
//! This provides a variation on the 16-ary radix tree that is //! This provides a variation on the 16-ary radix tree that is
//! provided as "nodetree" in revlog.c, ready for append-only persistence //! provided as "nodetree" in revlog.c, ready for append-only persistence
//! on disk. //! on disk.
//! //!
//! Following existing implicit conventions, the "nodemap" terminology //! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context. //! is used in a more abstract context.
use super::{ use super::{
node::NULL_NODE, FromHexError, Node, NodePrefix, NodePrefixRef, Revision, node::NULL_NODE, FromHexError, Node, NodePrefix, Revision, RevlogIndex,
RevlogIndex, NULL_REVISION, NULL_REVISION,
}; };
use bytes_cast::{unaligned, BytesCast}; use bytes_cast::{unaligned, BytesCast};
use std::cmp::max; use std::cmp::max;
use std::fmt; use std::fmt;
use std::mem::{self, align_of, size_of}; use std::mem::{self, align_of, size_of};
use std::ops::Deref; use std::ops::Deref;
use std::ops::Index; use std::ops::Index;
/// ///
/// If no Revision matches the given prefix, `Ok(None)` is returned. /// If no Revision matches the given prefix, `Ok(None)` is returned.
/// ///
/// If several Revisions match the given prefix, a [`MultipleResults`] /// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned. /// error is returned.
fn find_bin<'a>( fn find_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>, prefix: NodePrefix,
) -> Result<Option<Revision>, NodeMapError>; ) -> Result<Option<Revision>, NodeMapError>;
/// Find the unique Revision whose `Node` hexadecimal string representation /// Find the unique Revision whose `Node` hexadecimal string representation
/// starts with a given prefix /// starts with a given prefix
/// ///
/// If no Revision matches the given prefix, `Ok(None)` is returned. /// If no Revision matches the given prefix, `Ok(None)` is returned.
/// ///
/// If several Revisions match the given prefix, a [`MultipleResults`] /// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned. /// error is returned.
fn find_hex( fn find_hex(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: &str, prefix: &str,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) self.find_bin(idx, NodePrefix::from_hex(prefix)?)
} }
/// Give the size of the shortest node prefix that determines /// Give the size of the shortest node prefix that determines
/// the revision uniquely. /// the revision uniquely.
/// ///
/// From a binary node prefix, if it is matched in the node map, this /// From a binary node prefix, if it is matched in the node map, this
/// returns the number of hexadecimal digits that would had sufficed /// returns the number of hexadecimal digits that would had sufficed
/// to find the revision uniquely. /// to find the revision uniquely.
/// ///
/// Returns `None` if no `Revision` could be found for the prefix. /// Returns `None` if no `Revision` could be found for the prefix.
/// ///
/// If several Revisions match the given prefix, a [`MultipleResults`] /// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned. /// error is returned.
fn unique_prefix_len_bin<'a>( fn unique_prefix_len_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
node_prefix: NodePrefixRef<'a>, node_prefix: NodePrefix,
) -> Result<Option<usize>, NodeMapError>; ) -> Result<Option<usize>, NodeMapError>;
/// Same as `unique_prefix_len_bin`, with the hexadecimal representation /// Same as `unique_prefix_len_bin`, with the hexadecimal representation
/// of the prefix as input. /// of the prefix as input.
fn unique_prefix_len_hex( fn unique_prefix_len_hex(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: &str, prefix: &str,
) -> Result<Option<usize>, NodeMapError> { ) -> Result<Option<usize>, NodeMapError> {
self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?)
} }
/// Same as `unique_prefix_len_bin`, with a full `Node` as input /// Same as `unique_prefix_len_bin`, with a full `Node` as input
fn unique_prefix_len_node( fn unique_prefix_len_node(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
node: &Node, node: &Node,
) -> Result<Option<usize>, NodeMapError> { ) -> Result<Option<usize>, NodeMapError> {
&self.growable[i - ro_len] &self.growable[i - ro_len]
} }
} }
} }
/// Return `None` unless the `Node` for `rev` has given prefix in `index`. /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
fn has_prefix_or_none( fn has_prefix_or_none(
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef, prefix: NodePrefix,
rev: Revision, rev: Revision,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
idx.node(rev) idx.node(rev)
.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev))
.map(|node| { .map(|node| {
if prefix.is_prefix_of(node) { if prefix.is_prefix_of(node) {
Some(rev) Some(rev)
} else { } else {
None None
} }
}) })
} }
/// validate that the candidate's node starts indeed with given prefix, /// validate that the candidate's node starts indeed with given prefix,
/// and treat ambiguities related to `NULL_REVISION`. /// and treat ambiguities related to `NULL_REVISION`.
/// ///
/// From the data in the NodeTree, one can only conclude that some /// From the data in the NodeTree, one can only conclude that some
/// revision is the only one for a *subprefix* of the one being looked up. /// revision is the only one for a *subprefix* of the one being looked up.
fn validate_candidate( fn validate_candidate(
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef, prefix: NodePrefix,
candidate: (Option<Revision>, usize), candidate: (Option<Revision>, usize),
) -> Result<(Option<Revision>, usize), NodeMapError> { ) -> Result<(Option<Revision>, usize), NodeMapError> {
let (rev, steps) = candidate; let (rev, steps) = candidate;
if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) { if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) {
rev.map_or(Ok((None, steps)), |r| { rev.map_or(Ok((None, steps)), |r| {
has_prefix_or_none(idx, prefix, r) has_prefix_or_none(idx, prefix, r)
.map(|opt| (opt, max(steps, nz_nybble + 1))) .map(|opt| (opt, max(steps, nz_nybble + 1)))
}) })
/// common node prefix with the given prefix. /// common node prefix with the given prefix.
/// ///
/// The second returned value is the size of the smallest subprefix /// The second returned value is the size of the smallest subprefix
/// of `prefix` that would give the same result, i.e. not the /// of `prefix` that would give the same result, i.e. not the
/// `MultipleResults` error variant (again, using only the data of the /// `MultipleResults` error variant (again, using only the data of the
/// `NodeTree`). /// `NodeTree`).
fn lookup( fn lookup(
&self, &self,
prefix: NodePrefixRef, prefix: NodePrefix,
) -> Result<(Option<Revision>, usize), NodeMapError> { ) -> Result<(Option<Revision>, usize), NodeMapError> {
for (i, visit_item) in self.visit(prefix).enumerate() { for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() { if let Some(opt) = visit_item.final_revision() {
return Ok((opt, i + 1)); return Ok((opt, i + 1));
} }
} }
Err(NodeMapError::MultipleResults) Err(NodeMapError::MultipleResults)
} }
fn visit<'n, 'p>( fn visit<'n>(&'n self, prefix: NodePrefix) -> NodeTreeVisitor<'n> {
&'n self,
prefix: NodePrefixRef<'p>,
) -> NodeTreeVisitor<'n, 'p> {
NodeTreeVisitor { NodeTreeVisitor {
nt: self, nt: self,
prefix, prefix,
visit: self.len() - 1, visit: self.len() - 1,
nybble_idx: 0, nybble_idx: 0,
done: false, done: false,
} }
} }
Block::slice_from_bytes(&self.buffer, self.len_in_blocks) Block::slice_from_bytes(&self.buffer, self.len_in_blocks)
// `NodeTreeBytes::new` already asserted that `self.buffer` is // `NodeTreeBytes::new` already asserted that `self.buffer` is
// large enough. // large enough.
.unwrap() .unwrap()
.0 .0
} }
} }
struct NodeTreeVisitor<'n, 'p> { struct NodeTreeVisitor<'n> {
nt: &'n NodeTree, nt: &'n NodeTree,
prefix: NodePrefixRef<'p>, prefix: NodePrefix,
visit: usize, visit: usize,
nybble_idx: usize, nybble_idx: usize,
done: bool, done: bool,
} }
#[derive(Debug, PartialEq, Clone)] #[derive(Debug, PartialEq, Clone)]
struct NodeTreeVisitItem { struct NodeTreeVisitItem {
block_idx: usize, block_idx: usize,
nybble: u8, nybble: u8,
element: Element, element: Element,
} }
impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> { impl<'n> Iterator for NodeTreeVisitor<'n> {
type Item = NodeTreeVisitItem; type Item = NodeTreeVisitItem;
fn next(&mut self) -> Option<Self::Item> { fn next(&mut self) -> Option<Self::Item> {
if self.done || self.nybble_idx >= self.prefix.len() { if self.done || self.nybble_idx >= self.prefix.nybbles_len() {
return None; return None;
} }
let nybble = self.prefix.get_nybble(self.nybble_idx); let nybble = self.prefix.get_nybble(self.nybble_idx);
self.nybble_idx += 1; self.nybble_idx += 1;
let visit = self.visit; let visit = self.visit;
let element = self.nt[visit].get(nybble); let element = self.nt[visit].get(nybble);
NodeTree::new(Box::new(Vec::new())) NodeTree::new(Box::new(Vec::new()))
} }
} }
impl NodeMap for NodeTree { impl NodeMap for NodeTree {
fn find_bin<'a>( fn find_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>, prefix: NodePrefix,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) validate_candidate(idx, prefix, self.lookup(prefix)?)
.map(|(opt, _shortest)| opt) .map(|(opt, _shortest)| opt)
} }
fn unique_prefix_len_bin<'a>( fn unique_prefix_len_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>, prefix: NodePrefix,
) -> Result<Option<usize>, NodeMapError> { ) -> Result<Option<usize>, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) validate_candidate(idx, prefix, self.lookup(prefix)?)
.map(|(opt, shortest)| opt.map(|_rev| shortest)) .map(|(opt, shortest)| opt.map(|_rev| shortest))
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::NodeMapError::*; use super::NodeMapError::*;
use super::*; use super::*;

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

use std::borrow::Cow; use std::borrow::Cow;
use std::io::Read; use std::io::Read;
use std::ops::Deref; use std::ops::Deref;
use std::path::Path; use std::path::Path;
use byteorder::{BigEndian, ByteOrder}; use byteorder::{BigEndian, ByteOrder};
use crypto::digest::Digest; use crypto::digest::Digest;
use crypto::sha1::Sha1; use crypto::sha1::Sha1;
use flate2::read::ZlibDecoder; use flate2::read::ZlibDecoder;
use micro_timer::timed; use micro_timer::timed;
use zstd; use zstd;
use super::index::Index; use super::index::Index;
use super::node::{NodePrefixRef, NODE_BYTES_LENGTH, NULL_NODE}; use super::node::{NodePrefix, NODE_BYTES_LENGTH, NULL_NODE};
use super::nodemap; use super::nodemap;
use super::nodemap::NodeMap; use super::nodemap::NodeMap;
use super::nodemap_docket::NodeMapDocket; use super::nodemap_docket::NodeMapDocket;
use super::patch; use super::patch;
use crate::repo::Repo; use crate::repo::Repo;
use crate::revlog::Revision; use crate::revlog::Revision;
pub enum RevlogError { pub enum RevlogError {
pub fn is_empty(&self) -> bool { pub fn is_empty(&self) -> bool {
self.index.is_empty() self.index.is_empty()
} }
/// Return the full data associated to a node. /// Return the full data associated to a node.
#[timed] #[timed]
pub fn get_node_rev( pub fn get_node_rev(
&self, &self,
node: NodePrefixRef, node: NodePrefix,
) -> Result<Revision, RevlogError> { ) -> Result<Revision, RevlogError> {
if let Some(nodemap) = &self.nodemap { if let Some(nodemap) = &self.nodemap {
return nodemap return nodemap
.find_bin(&self.index, node) .find_bin(&self.index, node)
// TODO: propagate details of this error: // TODO: propagate details of this error:
.map_err(|_| RevlogError::Corrupted)? .map_err(|_| RevlogError::Corrupted)?
.ok_or(RevlogError::InvalidRevision); .ok_or(RevlogError::InvalidRevision);
} }

rust/hg-cpython/src/revlog.rs

/// Return Revision if found, raises a bare `error.RevlogError` /// Return Revision if found, raises a bare `error.RevlogError`
/// in case of ambiguity, same as C version does /// in case of ambiguity, same as C version does
def get_rev(&self, node: PyBytes) -> PyResult<Option<Revision>> { def get_rev(&self, node: PyBytes) -> PyResult<Option<Revision>> {
let opt = self.get_nodetree(py)?.borrow(); let opt = self.get_nodetree(py)?.borrow();
let nt = opt.as_ref().unwrap(); let nt = opt.as_ref().unwrap();
let idx = &*self.cindex(py).borrow(); let idx = &*self.cindex(py).borrow();
let node = node_from_py_bytes(py, &node)?; let node = node_from_py_bytes(py, &node)?;
nt.find_bin(idx, (&node).into()).map_err(|e| nodemap_error(py, e)) nt.find_bin(idx, node.into()).map_err(|e| nodemap_error(py, e))
} }
/// same as `get_rev()` but raises a bare `error.RevlogError` if node /// same as `get_rev()` but raises a bare `error.RevlogError` if node
/// is not found. /// is not found.
/// ///
/// No need to repeat `node` in the exception, `mercurial/revlog.py` /// No need to repeat `node` in the exception, `mercurial/revlog.py`
/// will catch and rewrap with it /// will catch and rewrap with it
def rev(&self, node: PyBytes) -> PyResult<Revision> { def rev(&self, node: PyBytes) -> PyResult<Revision> {