D7787: rust-nodemap: building blocks for nodetree structures
Closed by commit rHG63db6657d280: rust-nodemap: building blocks for nodetree
structures (authored by gracinet).
This revision was automatically updated to reflect the committed changes.
This revision was not accepted when it landed; it landed in state "Needs
Review".
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7787?vs=19504=19522
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7787/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
AFFECTED FILES
rust/hg-core/src/revlog.rs
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/nodemap.rs
b/rust/hg-core/src/revlog/nodemap.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -0,0 +1,160 @@
+// Copyright 2018-2020 Georges Racinet
+// 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
+//! 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 for Element {
+/// Conversion from low level representation, after endianness conversion.
+///
+/// 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 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`,
+/// such as ``
+///
+/// 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(, nybble: u8) -> Element {
+Element::from(RawElement::from_be(self.0[nybble as usize]))
+}
+
+fn set( self, nybble: u8, element: Element) {
+self.0[nybble as usize] = RawElement::to_be(element.into())
+}
+}
+
+impl fmt::Debug for Block {
+/// sparse representation for testing and debugging purposes
+fn fmt(, f: 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()
+}
+}
+
+#[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),
D7787: rust-nodemap: building blocks for nodetree structures
gracinet updated this revision to Diff 19504.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7787?vs=19503=19504
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7787/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
AFFECTED FILES
rust/hg-core/src/revlog.rs
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/nodemap.rs
b/rust/hg-core/src/revlog/nodemap.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -0,0 +1,160 @@
+// Copyright 2018-2020 Georges Racinet
+// 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
+//! 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 for Element {
+/// Conversion from low level representation, after endianness conversion.
+///
+/// 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 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`,
+/// such as ``
+///
+/// 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(, nybble: u8) -> Element {
+Element::from(RawElement::from_be(self.0[nybble as usize]))
+}
+
+fn set( self, nybble: u8, element: Element) {
+self.0[nybble as usize] = RawElement::to_be(element.into())
+}
+}
+
+impl fmt::Debug for Block {
+/// sparse representation for testing and debugging purposes
+fn fmt(, f: 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()
+}
+}
+
+#[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() {
+
D7787: rust-nodemap: building blocks for nodetree structures
gracinet added a comment. These are done, thanks for the remarks. REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7787/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7787 To: gracinet, #hg-reviewers, kevincox Cc: martinvonz, durin42, kevincox, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7787: rust-nodemap: building blocks for nodetree structures
gracinet marked 3 inline comments as done.
gracinet updated this revision to Diff 19503.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7787?vs=19322=19503
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7787/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
AFFECTED FILES
rust/hg-core/src/revlog.rs
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/nodemap.rs
b/rust/hg-core/src/revlog/nodemap.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -0,0 +1,160 @@
+// Copyright 2018-2020 Georges Racinet
+// 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 radix tree with valency 16 that is
+//! provided as "nodetree" in revlog.c, ready for append-only persistence
+//! 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 for Element {
+/// Conversion from low level representation, after endianity conversion.
+///
+/// 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 for RawElement {
+fn from(elt: Element) -> RawElement {
+match elt {
+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`,
+/// such as ``
+///
+/// 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)
+///
+/// Endianity 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(, nybble: u8) -> Element {
+Element::from(RawElement::from_be(self.0[nybble as usize]))
+}
+
+fn set( self, nybble: u8, elt: Element) {
+self.0[nybble as usize] = RawElement::to_be(elt.into())
+}
+}
+
+impl fmt::Debug for Block {
+/// sparse representation for testing and debugging purposes
+fn fmt(, f: fmt::Formatter<'_>) -> fmt::Result {
+f.debug_map()
+.entries((0..16).filter_map(|i| match self.get(i) {
+Element::None => None,
+elt => Some((i, elt)),
+}))
+.finish()
+}
+}
+
+#[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]
+
D7787: rust-nodemap: building blocks for nodetree structures
gracinet added inline comments. INLINE COMMENTS > martinvonz wrote in nodemap.rs:8 > i think s/valency/arity/ is a more common term for it yes, and valency is actually almost incorrect actually in that case, it turns out REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7787/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7787 To: gracinet, #hg-reviewers, kevincox Cc: martinvonz, durin42, kevincox, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7787: rust-nodemap: building blocks for nodetree structures
gracinet added a comment. @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. INLINE COMMENTS > martinvonz wrote in nodemap.rs:96 > 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. right, I've must have spent too much of my life using XML libraries, I suppose ;-) REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7787/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7787 To: gracinet, #hg-reviewers, kevincox Cc: martinvonz, durin42, kevincox, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7787: rust-nodemap: building blocks for nodetree structures
martinvonz added a comment.
Just a few nits here, but it looks like we're expecting an update on this
series anyway, so maybe you can address them.
INLINE COMMENTS
> nodemap.rs:8
> +//!
> +//! This provides a variation on the radix tree with valency 16 that is
> +//! provided as "nodetree" in revlog.c, ready for append-only persistence
i think s/valency/arity/ is a more common term for it
> nodemap.rs:36
> +impl From for Element {
> +/// Conversion from low level representation, after endianity conversion.
> +///
s/endianity/endianness/ (same further down)
> nodemap.rs:96
> +
> +fn set( self, nybble: u8, elt: Element) {
> +self.0[nybble as usize] = RawElement::to_be(elt.into())
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.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7787/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
To: gracinet, #hg-reviewers, kevincox
Cc: martinvonz, durin42, kevincox, mercurial-devel
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7787: rust-nodemap: building blocks for nodetree structures
gracinet added inline comments. gracinet marked 2 inline comments as done. INLINE COMMENTS > gracinet wrote in nodemap.rs:111 > Nice, thanks for the tip 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. REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7787/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7787 To: gracinet, #hg-reviewers, kevincox Cc: durin42, kevincox, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7787: rust-nodemap: building blocks for nodetree structures
gracinet updated this revision to Diff 19322.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7787?vs=19133=19322
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7787/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
AFFECTED FILES
rust/hg-core/src/revlog.rs
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/nodemap.rs
b/rust/hg-core/src/revlog/nodemap.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -0,0 +1,160 @@
+// Copyright 2018-2020 Georges Racinet
+// 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 radix tree with valency 16 that is
+//! provided as "nodetree" in revlog.c, ready for append-only persistence
+//! 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 for Element {
+/// Conversion from low level representation, after endianity conversion.
+///
+/// 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 for RawElement {
+fn from(elt: Element) -> RawElement {
+match elt {
+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`,
+/// such as ``
+///
+/// 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)
+///
+/// Endianity 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(, nybble: u8) -> Element {
+Element::from(RawElement::from_be(self.0[nybble as usize]))
+}
+
+fn set( self, nybble: u8, elt: Element) {
+self.0[nybble as usize] = RawElement::to_be(elt.into())
+}
+}
+
+impl fmt::Debug for Block {
+/// sparse representation for testing and debugging purposes
+fn fmt(, f: fmt::Formatter<'_>) -> fmt::Result {
+f.debug_map()
+.entries((0..16).filter_map(|i| match self.get(i) {
+Element::None => None,
+elt => Some((i, elt)),
+}))
+.finish()
+}
+}
+
+#[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
D7787: rust-nodemap: building blocks for nodetree structures
gracinet added a comment. @kevincox thanks for the review! INLINE COMMENTS > kevincox wrote in nodemap.rs:92 > I would call these `get` and `set`. Yes, I suppose `read` and `write` feel like I/O. Will do. > kevincox wrote in nodemap.rs:111 > You can use this helper: > https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.debug_map Nice, thanks for the tip REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7787/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7787 To: gracinet, #hg-reviewers, kevincox Cc: durin42, kevincox, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7787: rust-nodemap: building blocks for nodetree structures
kevincox added inline comments.
kevincox accepted this revision.
INLINE COMMENTS
> nodemap.rs:92
> +
> +fn read(, nybble: u8) -> Element {
> +Element::from(RawElement::from_be(self.0[nybble as usize]))
I would call these `get` and `set`.
> nodemap.rs:111
> +}
> +write!(f, "[{}]", inner.join(", "))
> +}
You can use this helper:
https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.debug_map
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7787/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
To: gracinet, #hg-reviewers, kevincox
Cc: durin42, kevincox, mercurial-devel
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7787: rust-nodemap: building blocks for nodetree structures
gracinet updated this revision to Diff 19133.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7787?vs=19036=19133
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7787/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
AFFECTED FILES
rust/hg-core/src/revlog.rs
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/nodemap.rs
b/rust/hg-core/src/revlog/nodemap.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -0,0 +1,162 @@
+// Copyright 2018-2020 Georges Racinet
+// 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 radix tree with valency 16 that is
+//! provided as "nodetree" in revlog.c, ready for append-only persistence
+//! 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 for Element {
+/// Conversion from low level representation, after endianity conversion.
+///
+/// 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 for RawElement {
+fn from(elt: Element) -> RawElement {
+match elt {
+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`,
+/// such as ``
+///
+/// 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)
+///
+/// Endianity 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 read(, nybble: u8) -> Element {
+Element::from(RawElement::from_be(self.0[nybble as usize]))
+}
+
+fn write( self, nybble: u8, elt: Element) {
+self.0[nybble as usize] = RawElement::to_be(elt.into())
+}
+}
+
+impl fmt::Debug for Block {
+/// sparse representation for testing and debugging purposes
+fn fmt(, f: fmt::Formatter<'_>) -> fmt::Result {
+let mut inner: Vec = Vec::new();
+for i in 0..16 {
+let elt = self.read(i);
+if elt != Element::None {
+inner.push(format!("{:X}: {:?}", i, elt));
+}
+}
+write!(f, "[{}]", inner.join(", "))
+}
+}
+
+#[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.write($nybble, Element::$variant($val)));*;
+block
+}
+)
+}
+
+#[test]
+fn test_block_debug() {
+let mut block = Block::new();
+block.write(1, Element::Rev(3));
+block.write(10, Element::Block(0));
+assert_eq!(format!("{:?}", block), "[1: Rev(3), A: 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), D:
D7787: rust-nodemap: building blocks for nodetree structures
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.
REVISION 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.
REPOSITORY
rHG Mercurial
BRANCH
default
REVISION DETAIL
https://phab.mercurial-scm.org/D7787
AFFECTED FILES
rust/hg-core/src/revlog.rs
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/nodemap.rs
b/rust/hg-core/src/revlog/nodemap.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -0,0 +1,163 @@
+// Copyright 2018-2020 Georges Racinet
+// 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 radix tree with valency 16 that is
+//! provided as "nodetree" in revlog.c, ready for append-only persistence
+//! 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 for Element {
+/// Conversion from low level representation, after endianity conversion.
+///
+/// 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 for RawElement {
+fn from(elt: Element) -> RawElement {
+match elt {
+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`,
+/// such as ``
+///
+/// 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)
+///
+/// Endianity 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 read(, nybble: u8) -> Element {
+Element::from(RawElement::from_be(self.0[nybble as usize]))
+}
+
+fn write( self, nybble: u8, elt: Element) {
+self.0[nybble as usize] = RawElement::to_be(elt.into())
+}
+}
+
+impl fmt::Debug for Block {
+/// sparse representation for testing and debugging purposes
+fn fmt(, f: fmt::Formatter<'_>) -> fmt::Result {
+let mut inner: Vec = Vec::new();
+for i in 0..16 {
+let elt = self.read(i);
+if elt != Element::None {
+inner.push(format!("{:X}: {:?}", i, elt));
+}
+}
+write!(f, "[{}]", inner.join(", "))
+}
+}
+
+#[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.write($nybble, Element::$variant($val)));*;
+block
+}
+)
+}
+
+#[test]
+fn test_block_debug() {
+let mut block = Block::new();
+block.write(1, Element::Rev(3));
+block.write(10, Element::Block(0));
+assert_eq!(format!("{:?}",
