This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7791

rust-nodemap: NodeMap trait with simplest implementation
ClosedPublic

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

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGe52401a95b94: rust-nodemap: NodeMap trait with simplest implementation
Summary

We're defining here only a small part of the immutable
methods it will have at the end. This is so we can
focus in the following changesets on the needed abstractions
for a mutable append-only serializable version.

The first implementor exposes the actual lookup
algorithm in its simplest form. It will have to be expanded
to account for the missing methods, and the special cases
related to NULL_NODE.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

gracinet created this revision.Jan 6 2020, 2:25 PM
gracinet updated this revision to Diff 19134.Jan 10 2020, 10:03 AM
gracinet updated this revision to Diff 19324.Jan 15 2020, 6:47 PM
kevincox accepted this revision.Jan 16 2020, 5:08 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
37

Can you please add doc-comments for this? I find that documenting trait methods is especially important.

205

I don't think the <'_> is necessary.

martinvonz added a subscriber: martinvonz.Jan 21 2020, 4:42 PM
martinvonz added inline comments.
rust/hg-core/src/revlog/nodemap.rs
150

I find Deref<Target = [Block]> + Send hard to understand. I think it would be helpful to name it. Could we at least define an alias for it?

Perhaps it's even better to define a trait for it and add named methods on that, but if those methods would just be len() and index() it probably doesn't make any sense to define the trait.

150

Do we need Send? Maybe it later when you need it (unless you actually need it now and I'm just mistaken, of course).

153

I understand that you picked this interface because it works well for the caller, but it feel a little weird to always return None or Some(rev) where rev is one of the function inputs. It's practically a boolean-valued function. Do the callers get much harder to read if you actually make it boolean-valued?

Alphare added a subscriber: Alphare.Jan 21 2020, 5:17 PM
Alphare added inline comments.
rust/hg-core/src/revlog/nodemap.rs
150

I find Deref<Target = [Block]> + Send hard to understand. I think it would be helpful to name it. Could we at least define an alias for it?

Alas, trait aliases are not stable: rust#55628.

On a more subjective note, I find this syntax quite readable as it is (as readable as Rust usually is), and since this is a single occurrence in a private field, I find it reasonable.

martinvonz added inline comments.Jan 21 2020, 5:27 PM
rust/hg-core/src/revlog/nodemap.rs
150

Alas, trait aliases are not stable: rust#55628.

I didn't know about trait aliases, but I think you can already do this:

trait Thing : Deref<Target = [Block]> + Send  {}

... since this is a single occurrence in a private field, I find it reasonable.

It's one instance right now. It's 7 instances of Box<dyn Deref<...>> at the end of the series...

Alphare added inline comments.Jan 22 2020, 4:43 AM
rust/hg-core/src/revlog/nodemap.rs
150

I didn't know about trait aliases, but I think you can already do this:
trait Thing : Deref<Target = [Block]> + Send {}

Using an empty supertrait will not work because fat pointers have different metadata.
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=4f1d374e426c9791cbf73421160dc7c3

It's one instance right now. It's 7 instances of Box<dyn Deref<...>> at the end of the series...

Ah true, that is indeed verbose, but manageable. Unfortunately, from a language perspective, I think that a type macro would be our only choice, but my opinion is that 1) it's ugly and more code to maintain and 2) I'm not even sure it would work.

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

I've looked into trait alias while working on this, for the exact same reason, and went through most you guys are saying about that.

Seems that this is complicated for the language because they'd like to have the
possibility to impl it.

150

About Send, without it we can't expose NodeTree to the Python layer, IIRC

martinvonz added inline comments.Jan 22 2020, 11:23 AM
rust/hg-core/src/revlog/nodemap.rs
150

How about something like this then?

type BlockSource = Box<dyn Deref<Target = [Block]> + Send>;
type ByteSource = Box<dyn Deref<Target = [u8]> + Send>;

I won't insist, so up to you if you think it helps.

gracinet retitled this revision from rust-nodemap: NodeMap trait with simplest implementor to rust-nodemap: NodeMap trait with simplest implementation.Jan 27 2020, 10:49 AM
gracinet updated this revision to Diff 19631.
gracinet marked 3 inline comments as done.Jan 27 2020, 10:53 AM
gracinet added inline comments.
rust/hg-core/src/revlog/nodemap.rs
37

Sure, indeed it's more important than with the impl.

150

Missed the type (not trait) alias suggestion. Maybe for the next update, then

153

Perhaps a better name would be better than this has_ that indeed feels boolean?

check_prefix? confirm ?

Previous naming was validate_candidate, but that very same name is used at the end of the series when it becomes involved with NULL_NODE etc. Then this has_prefix_or_none becomes one step in the final verification.

Returning a bool would mean adding a closure to the callers. making it less obvious that they are just chaining the maturation of the response.

I'm leaving unchanged for now, not sure what the best is. Still note that this is a private function, there's no risk an external caller would be confused by what it does.

205

Removed

martinvonz added inline comments.Jan 27 2020, 1:40 PM
rust/hg-core/src/revlog/nodemap.rs
74

can the explicit lifetime be dropped?

153

Yes, validate_candidate sounds much better. Could you send a follow-up with a better name for it?

154

can the explicit lifetime be dropped?

174

can the explicit lifetime be dropped?

205

Still there? Or maybe it's a different one, but I think you can remove the <'_> from the fm::Formatter<'_>.

211

can the explicit lifetime be dropped?

gracinet marked 2 inline comments as done.Jan 27 2020, 2:13 PM
gracinet added a commit: rHGe52401a95b94: rust-nodemap: NodeMap trait with simplest implementation.
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGe52401a95b94: rust-nodemap: NodeMap trait with simplest implementation (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/revlog/nodemap.rs (181 lines)

Diff 19324

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 radix tree with valency 16 that is //! This provides a variation on the radix tree with valency 16 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::Revision; use super::{NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex};
use std::fmt; use std::fmt;
use std::ops::Deref;
#[derive(Debug, PartialEq)]
pub enum NodeMapError {
MultipleResults,
InvalidNodePrefix(NodeError),
/// A `Revision` stored in the nodemap could not be found in the index
RevisionNotInIndex(Revision),
}
impl From<NodeError> for NodeMapError {
fn from(err: NodeError) -> Self {
NodeMapError::InvalidNodePrefix(err)
}
}
/// Mapping system from Mercurial nodes to revision numbers.
///
/// Many methods in this trait work in conjunction with a `RevlogIndex`
/// whose data should not be owned by the `NodeMap`.
pub trait NodeMap {
kevincoxUnsubmitted
Done

Can you please add doc-comments for this? I find that documenting trait methods is especially important.

kevincox: Can you please add doc-comments for this? I find that documenting trait methods is especially…
gracinetAuthorUnsubmitted
Done

Sure, indeed it's more important than with the impl.

gracinet: Sure, indeed it's more important than with the `impl`.
fn find_bin<'a>(
&self,
idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>,
) -> Result<Option<Revision>, NodeMapError>;
fn find_hex(
&self,
idx: &impl RevlogIndex,
prefix: &str,
) -> Result<Option<Revision>, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
}
/// Low level NodeTree [`Blocks`] elements /// Low level NodeTree [`Blocks`] elements
/// ///
/// These are exactly as for instance on persistent storage. /// These are exactly as for instance on persistent storage.
type RawElement = i32; type RawElement = i32;
/// High level representation of values in NodeTree /// High level representation of values in NodeTree
/// [`Blocks`](struct.Block.html) /// [`Blocks`](struct.Block.html)
/// ///
/// This is the high level representation that most algorithms should /// This is the high level representation that most algorithms should
/// use. /// use.
#[derive(Clone, Debug, Eq, PartialEq)] #[derive(Clone, Debug, Eq, PartialEq)]
enum Element { enum Element {
Rev(Revision), Rev(Revision),
Block(usize), Block(usize),
None, None,
} }
impl From<RawElement> for Element { impl From<RawElement> for Element {
/// Conversion from low level representation, after endianity conversion. /// Conversion from low level representation, after endianity conversion.
/// ///
/// See [`Block`](struct.Block.html) for explanation about the encoding. /// See [`Block`](struct.Block.html) for explanation about the encoding.
fn from(raw: RawElement) -> Element { fn from(raw: RawElement) -> Element {
martinvonzUnsubmitted
Not Done

can the explicit lifetime be dropped?

martinvonz: can the explicit lifetime be dropped?
if raw >= 0 { if raw >= 0 {
Element::Block(raw as usize) Element::Block(raw as usize)
} else if raw == -1 { } else if raw == -1 {
Element::None Element::None
} else { } else {
Element::Rev(-raw - 2) Element::Rev(-raw - 2)
} }
} }
.entries((0..16).filter_map(|i| match self.get(i) { .entries((0..16).filter_map(|i| match self.get(i) {
Element::None => None, Element::None => None,
elt => Some((i, elt)), elt => Some((i, elt)),
})) }))
.finish() .finish()
} }
} }
/// A 16-radix tree with the root block at the end
pub struct NodeTree {
readonly: Box<dyn Deref<Target = [Block]> + Send>,
martinvonzUnsubmitted
Not Done

I find Deref<Target = [Block]> + Send hard to understand. I think it would be helpful to name it. Could we at least define an alias for it?

Perhaps it's even better to define a trait for it and add named methods on that, but if those methods would just be len() and index() it probably doesn't make any sense to define the trait.

martinvonz: I find `Deref<Target = [Block]> + Send` hard to understand. I think it would be helpful to name…
AlphareUnsubmitted
Not Done

I find Deref<Target = [Block]> + Send hard to understand. I think it would be helpful to name it. Could we at least define an alias for it?

Alas, trait aliases are not stable: rust#55628.

On a more subjective note, I find this syntax quite readable as it is (as readable as Rust usually is), and since this is a single occurrence in a private field, I find it reasonable.

Alphare: > I find Deref<Target = [Block]> + Send hard to understand. I think it would be helpful to name…
martinvonzUnsubmitted
Not Done

Alas, trait aliases are not stable: rust#55628.

I didn't know about trait aliases, but I think you can already do this:

trait Thing : Deref<Target = [Block]> + Send  {}

... since this is a single occurrence in a private field, I find it reasonable.

It's one instance right now. It's 7 instances of Box<dyn Deref<...>> at the end of the series...

martinvonz: > Alas, trait aliases are not stable: rust#55628. I didn't know about trait aliases, but I…
AlphareUnsubmitted
Not Done

I didn't know about trait aliases, but I think you can already do this:
trait Thing : Deref<Target = [Block]> + Send {}

Using an empty supertrait will not work because fat pointers have different metadata.
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=4f1d374e426c9791cbf73421160dc7c3

It's one instance right now. It's 7 instances of Box<dyn Deref<...>> at the end of the series...

Ah true, that is indeed verbose, but manageable. Unfortunately, from a language perspective, I think that a type macro would be our only choice, but my opinion is that 1) it's ugly and more code to maintain and 2) I'm not even sure it would work.

Alphare: >I didn't know about trait aliases, but I think you can already do this: > `trait Thing…
gracinetAuthorUnsubmitted
Done

I've looked into trait alias while working on this, for the exact same reason, and went through most you guys are saying about that.

Seems that this is complicated for the language because they'd like to have the
possibility to impl it.

gracinet: I've looked into trait alias while working on this, for the exact same reason, and went through…
martinvonzUnsubmitted
Not Done

How about something like this then?

type BlockSource = Box<dyn Deref<Target = [Block]> + Send>;
type ByteSource = Box<dyn Deref<Target = [u8]> + Send>;

I won't insist, so up to you if you think it helps.

martinvonz: How about something like this then? ``` type BlockSource = Box<dyn Deref<Target = [Block]> +…
gracinetAuthorUnsubmitted
Done

Missed the type (not trait) alias suggestion. Maybe for the next update, then

gracinet: Missed the type (not trait) alias suggestion. Maybe for the next update, then
martinvonzUnsubmitted
Done

Do we need Send? Maybe it later when you need it (unless you actually need it now and I'm just mistaken, of course).

martinvonz: Do we need `Send`? Maybe it later when you need it (unless you actually need it now and I'm…
gracinetAuthorUnsubmitted
Done

About Send, without it we can't expose NodeTree to the Python layer, IIRC

gracinet: About `Send`, without it we can't expose `NodeTree` to the Python layer, IIRC
}
/// Return `None` unless the `Node` for `rev` has given prefix in `index`.
martinvonzUnsubmitted
Not Done

I understand that you picked this interface because it works well for the caller, but it feel a little weird to always return None or Some(rev) where rev is one of the function inputs. It's practically a boolean-valued function. Do the callers get much harder to read if you actually make it boolean-valued?

martinvonz: I understand that you picked this interface because it works well for the caller, but it feel a…
gracinetAuthorUnsubmitted
Done

Perhaps a better name would be better than this has_ that indeed feels boolean?

check_prefix? confirm ?

Previous naming was validate_candidate, but that very same name is used at the end of the series when it becomes involved with NULL_NODE etc. Then this has_prefix_or_none becomes one step in the final verification.

Returning a bool would mean adding a closure to the callers. making it less obvious that they are just chaining the maturation of the response.

I'm leaving unchanged for now, not sure what the best is. Still note that this is a private function, there's no risk an external caller would be confused by what it does.

gracinet: Perhaps a better name would be better than this `has_` that indeed feels boolean?
martinvonzUnsubmitted
Not Done

Yes, validate_candidate sounds much better. Could you send a follow-up with a better name for it?

martinvonz: Yes, `validate_candidate` sounds much better. Could you send a follow-up with a better name for…
fn has_prefix_or_none<'p>(
martinvonzUnsubmitted
Not Done

can the explicit lifetime be dropped?

martinvonz: can the explicit lifetime be dropped?
idx: &impl RevlogIndex,
prefix: NodePrefixRef<'p>,
rev: Revision,
) -> Result<Option<Revision>, NodeMapError> {
idx.node(rev)
.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev))
.map(|node| {
if prefix.is_prefix_of(node) {
Some(rev)
} else {
None
}
})
}
impl NodeTree {
/// Main working method for `NodeTree` searches
///
/// This partial implementation lacks
/// - special cases for NULL_REVISION
martinvonzUnsubmitted
Not Done

can the explicit lifetime be dropped?

martinvonz: can the explicit lifetime be dropped?
fn lookup<'p>(
&self,
prefix: NodePrefixRef<'p>,
) -> Result<Option<Revision>, NodeMapError> {
let blocks: &[Block] = &*self.readonly;
if blocks.is_empty() {
return Ok(None);
}
let mut visit = blocks.len() - 1;
for i in 0..prefix.len() {
let nybble = prefix.get_nybble(i);
match blocks[visit].get(nybble) {
Element::None => return Ok(None),
Element::Rev(r) => return Ok(Some(r)),
Element::Block(idx) => visit = idx,
}
}
Err(NodeMapError::MultipleResults)
}
}
impl From<Vec<Block>> for NodeTree {
fn from(vec: Vec<Block>) -> Self {
NodeTree {
readonly: Box::new(vec),
}
}
}
impl fmt::Debug for NodeTree {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
kevincoxUnsubmitted
Done

I don't think the <'_> is necessary.

kevincox: I don't think the `<'_>` is necessary.
gracinetAuthorUnsubmitted
Done

Removed

gracinet: Removed
martinvonzUnsubmitted
Not Done

Still there? Or maybe it's a different one, but I think you can remove the <'_> from the fm::Formatter<'_>.

martinvonz: Still there? Or maybe it's a different one, but I think you can remove the `<'_>` from the `fm…
let blocks: &[Block] = &*self.readonly;
write!(f, "readonly: {:?}", blocks)
}
}
impl NodeMap for NodeTree {
martinvonzUnsubmitted
Not Done

can the explicit lifetime be dropped?

martinvonz: can the explicit lifetime be dropped?
fn find_bin<'a>(
&self,
idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>,
) -> Result<Option<Revision>, NodeMapError> {
self.lookup(prefix.clone()).and_then(|opt| {
opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev))
})
}
}
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::NodeMapError::*;
use super::*; use super::*;
use crate::revlog::node::{node_from_hex, Node};
use std::collections::HashMap;
/// Creates a `Block` using a syntax close to the `Debug` output /// Creates a `Block` using a syntax close to the `Debug` output
macro_rules! block { macro_rules! block {
{$($nybble:tt : $variant:ident($val:tt)),*} => ( {$($nybble:tt : $variant:ident($val:tt)),*} => (
{ {
let mut block = Block::new(); let mut block = Block::new();
$(block.set($nybble, Element::$variant($val)));*; $(block.set($nybble, Element::$variant($val)));*;
block block
raw[4] = RawElement::to_be(-3); raw[4] = RawElement::to_be(-3);
let block = Block(raw); let block = Block(raw);
assert_eq!(block.get(0), Element::Block(0)); assert_eq!(block.get(0), Element::Block(0));
assert_eq!(block.get(1), Element::Block(15)); assert_eq!(block.get(1), Element::Block(15));
assert_eq!(block.get(3), Element::None); assert_eq!(block.get(3), Element::None);
assert_eq!(block.get(2), Element::Rev(0)); assert_eq!(block.get(2), Element::Rev(0));
assert_eq!(block.get(4), Element::Rev(1)); assert_eq!(block.get(4), Element::Rev(1));
} }
type TestIndex = HashMap<Revision, Node>;
impl RevlogIndex for TestIndex {
fn node(&self, rev: Revision) -> Option<&Node> {
self.get(&rev)
}
fn len(&self) -> usize {
self.len()
}
}
/// Pad hexadecimal Node prefix with zeros on the right, then insert
///
/// This is just to avoid having to repeatedly write 40 hexadecimal
/// digits for test data.
fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
idx.insert(rev, node_from_hex(&format!("{:0<40}", hex)).unwrap());
}
fn sample_nodetree() -> NodeTree {
NodeTree::from(vec![
block![0: Rev(9)],
block![0: Rev(0), 1: Rev(9)],
block![0: Block(1), 1:Rev(1)],
])
}
#[test]
fn test_nt_debug() {
let nt = sample_nodetree();
assert_eq!(
format!("{:?}", nt),
"readonly: \
[{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}]"
);
}
#[test]
fn test_immutable_find_simplest() -> Result<(), NodeMapError> {
let mut idx: TestIndex = HashMap::new();
pad_insert(&mut idx, 1, "1234deadcafe");
let nt = NodeTree::from(vec![block![1: Rev(1)]]);
assert_eq!(nt.find_hex(&idx, "1")?, Some(1));
assert_eq!(nt.find_hex(&idx, "12")?, Some(1));
assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1));
assert_eq!(nt.find_hex(&idx, "1a")?, None);
assert_eq!(nt.find_hex(&idx, "ab")?, None);
Ok(())
}
#[test]
fn test_immutable_find_one_jump() {
let mut idx = TestIndex::new();
pad_insert(&mut idx, 9, "012");
pad_insert(&mut idx, 0, "00a");
let nt = sample_nodetree();
assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0)));
assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
}
} }