This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7787

rust-nodemap: building blocks for nodetree structures
ClosedPublic

Authored by gracinet on Jan 6 2020, 2:24 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG63db6657d280: rust-nodemap: building blocks for nodetree structures
Summary

This is similar to nodetreenode in revlog.c. We give it
a higher level feeling for ease of handling in Rust context
and provide tools for tests and debugging.

The encoding choice is dictated by our ultimate goal in this
series, that is to make an append-only persistent version of
nodetree: the 0th Block must be adressed from other Blocks.

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

gracinet created this revision.Jan 6 2020, 2:24 PM
gracinet updated this revision to Diff 19133.Jan 10 2020, 10:03 AM
kevincox accepted this revision.Jan 15 2020, 9:02 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
93

I would call these get and set.

112

You can use this helper: https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.debug_map

gracinet added a comment.Jan 15 2020, 9:19 AM

@kevincox thanks for the review!

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

Yes, I suppose read and write feel like I/O. Will do.

112

Nice, thanks for the tip

gracinet updated this revision to Diff 19322.Jan 15 2020, 6:46 PM
gracinet marked 2 inline comments as done.Jan 15 2020, 6:55 PM
gracinet added inline comments.
rust/hg-core/src/revlog/nodemap.rs
112

So, that gives formatting with braces, hence for consistency I changed the block! macro, too.

I didn't keep the hexadecimal formatting, because it'd now lead to lots of \" making the tests less readable.

An upside of this is that it's now really consistent with block!. A downside is that someone using it for real debugging with input given in hexadecimal would presumably have to mentally convert hexadecimal nybbles to their decimal form.
It would have been a bit of a drag in the intiial development effort, but I don't think
that'll be a problem in the future: : either it'll be on small data or with diffrent tools anyway.

martinvonz added a subscriber: martinvonz.Jan 21 2020, 1:02 PM

Just a few nits here, but it looks like we're expecting an update on this series anyway, so maybe you can address them.

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

i think s/valency/arity/ is a more common term for it

37

s/endianity/endianness/ (same further down)

97

Could you call it element instead? I think it's a little obvious what that means. elt is at least not an abbreviation I'm familiar with.

gracinet added a comment.Jan 22 2020, 9:52 AM

@martinvonz

Just a few nits here, but it looks like we're expecting an update on this series anyway, so maybe you can address them.

No problem with these. I'll be doing a swipe on the whole series today and will include them.

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

right, I've must have spent too much of my life using XML libraries, I suppose ;-)

gracinet added inline comments.Jan 22 2020, 9:53 AM
rust/hg-core/src/revlog/nodemap.rs
9

yes, and valency is actually almost incorrect actually in that case, it turns out

gracinet marked 3 inline comments as done.Jan 22 2020, 10:34 AM
gracinet updated this revision to Diff 19503.
gracinet added a comment.Jan 22 2020, 10:34 AM

These are done, thanks for the remarks.

gracinet updated this revision to Diff 19504.Jan 22 2020, 10:42 AM
gracinet added a commit: rHG63db6657d280: rust-nodemap: building blocks for nodetree structures.Jan 22 2020, 3:52 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG63db6657d280: rust-nodemap: building blocks for nodetree structures (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 19522

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 nodemap;
/// Mercurial revision numbers /// Mercurial revision numbers
/// ///
/// As noted in revlog.c, revision numbers are actually encoded in /// As noted in revlog.c, revision numbers are actually encoded in
/// 4 bytes, and are liberally converted to ints, whence the i32 /// 4 bytes, and are liberally converted to ints, whence the i32
pub type Revision = i32; pub type Revision = i32;
/// Marker expressing the absence of a parent /// Marker expressing the absence of a parent
/// ///

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

  • This file was added.
// Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
// and Mercurial contributors
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
//! Indexing facilities for fast retrieval of `Revision` from `Node`
//!
//! This provides a variation on the 16-ary radix tree that is
//! provided as "nodetree" in revlog.c, ready for append-only persistence
martinvonzUnsubmitted
Done

i think s/valency/arity/ is a more common term for it

martinvonz: i think s/valency/arity/ is a more common term for it
gracinetAuthorUnsubmitted
Done

yes, and valency is actually almost incorrect actually in that case, it turns out

gracinet: yes, and valency is actually almost incorrect actually in that case, it turns out
//! on disk.
//!
//! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context.
use super::Revision;
use std::fmt;
/// Low level NodeTree [`Blocks`] elements
///
/// These are exactly as for instance on persistent storage.
type RawElement = i32;
/// High level representation of values in NodeTree
/// [`Blocks`](struct.Block.html)
///
/// This is the high level representation that most algorithms should
/// use.
#[derive(Clone, Debug, Eq, PartialEq)]
enum Element {
Rev(Revision),
Block(usize),
None,
}
impl From<RawElement> for Element {
/// Conversion from low level representation, after endianness conversion.
///
martinvonzUnsubmitted
Done

s/endianity/endianness/ (same further down)

martinvonz: s/endianity/endianness/ (same further down)
/// See [`Block`](struct.Block.html) for explanation about the encoding.
fn from(raw: RawElement) -> Element {
if raw >= 0 {
Element::Block(raw as usize)
} else if raw == -1 {
Element::None
} else {
Element::Rev(-raw - 2)
}
}
}
impl From<Element> for RawElement {
fn from(element: Element) -> RawElement {
match element {
Element::None => 0,
Element::Block(i) => i as RawElement,
Element::Rev(rev) => -rev - 2,
}
}
}
/// A logical block of the `NodeTree`, packed with a fixed size.
///
/// These are always used in container types implementing `Index<Block>`,
/// such as `&Block`
///
/// As an array of integers, its ith element encodes that the
/// ith potential edge from the block, representing the ith hexadecimal digit
/// (nybble) `i` is either:
///
/// - absent (value -1)
/// - another `Block` in the same indexable container (value ≥ 0)
/// - a `Revision` leaf (value ≤ -2)
///
/// Endianness has to be fixed for consistency on shared storage across
/// different architectures.
///
/// A key difference with the C `nodetree` is that we need to be
/// able to represent the [`Block`] at index 0, hence -1 is the empty marker
/// rather than 0 and the `Revision` range upper limit of -2 instead of -1.
///
/// Another related difference is that `NULL_REVISION` (-1) is not
/// represented at all, because we want an immutable empty nodetree
/// to be valid.
#[derive(Clone, PartialEq)]
pub struct Block([RawElement; 16]);
impl Block {
fn new() -> Self {
Block([-1; 16])
}
fn get(&self, nybble: u8) -> Element {
Element::from(RawElement::from_be(self.0[nybble as usize]))
kevincoxUnsubmitted
Done

I would call these get and set.

kevincox: I would call these `get` and `set`.
gracinetAuthorUnsubmitted
Done

Yes, I suppose read and write feel like I/O. Will do.

gracinet: Yes, I suppose `read` and `write` feel like I/O. Will do.
}
fn set(&mut self, nybble: u8, element: Element) {
self.0[nybble as usize] = RawElement::to_be(element.into())
martinvonzUnsubmitted
Done

Could you call it element instead? I think it's a little obvious what that means. elt is at least not an abbreviation I'm familiar with.

martinvonz: Could you call it `element` instead? I think it's a little obvious what that means. `elt` is at…
gracinetAuthorUnsubmitted
Done

right, I've must have spent too much of my life using XML libraries, I suppose ;-)

gracinet: right, I've must have spent too much of my life using XML libraries, I suppose ;-)
}
}
impl fmt::Debug for Block {
/// sparse representation for testing and debugging purposes
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_map()
.entries((0..16).filter_map(|i| match self.get(i) {
Element::None => None,
element => Some((i, element)),
}))
.finish()
}
}
kevincoxUnsubmitted
Done

You can use this helper: https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.debug_map

kevincox: You can use this helper: https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.
gracinetAuthorUnsubmitted
Done

Nice, thanks for the tip

gracinet: Nice, thanks for the tip
gracinetAuthorUnsubmitted
Done

So, that gives formatting with braces, hence for consistency I changed the block! macro, too.

I didn't keep the hexadecimal formatting, because it'd now lead to lots of \" making the tests less readable.

An upside of this is that it's now really consistent with block!. A downside is that someone using it for real debugging with input given in hexadecimal would presumably have to mentally convert hexadecimal nybbles to their decimal form.
It would have been a bit of a drag in the intiial development effort, but I don't think
that'll be a problem in the future: : either it'll be on small data or with diffrent tools anyway.

gracinet: So, that gives formatting with braces, hence for consistency I changed the `block!` macro, too.
#[cfg(test)]
mod tests {
use super::*;
/// Creates a `Block` using a syntax close to the `Debug` output
macro_rules! block {
{$($nybble:tt : $variant:ident($val:tt)),*} => (
{
let mut block = Block::new();
$(block.set($nybble, Element::$variant($val)));*;
block
}
)
}
#[test]
fn test_block_debug() {
let mut block = Block::new();
block.set(1, Element::Rev(3));
block.set(10, Element::Block(0));
assert_eq!(format!("{:?}", block), "{1: Rev(3), 10: Block(0)}");
}
#[test]
fn test_block_macro() {
let block = block! {5: Block(2)};
assert_eq!(format!("{:?}", block), "{5: Block(2)}");
let block = block! {13: Rev(15), 5: Block(2)};
assert_eq!(format!("{:?}", block), "{5: Block(2), 13: Rev(15)}");
}
#[test]
fn test_raw_block() {
let mut raw = [-1; 16];
raw[0] = 0;
raw[1] = RawElement::to_be(15);
raw[2] = RawElement::to_be(-2);
raw[3] = RawElement::to_be(-1);
raw[4] = RawElement::to_be(-3);
let block = Block(raw);
assert_eq!(block.get(0), Element::Block(0));
assert_eq!(block.get(1), Element::Block(15));
assert_eq!(block.get(3), Element::None);
assert_eq!(block.get(2), Element::Rev(0));
assert_eq!(block.get(4), Element::Rev(1));
}
}