This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7792

rust-nodemap: abstracting the indexing
ClosedPublic

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

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG220d4d2e3185: rust-nodemap: abstracting the indexing
Summary

In the forthcoming mutable implementation, we'll have to visit
node trees that are more complex than a single slice, although
the algorithm will still be expressed in simple indexing terms.

We still refrain using #[inline] indications as being
premature optimizations, but we strongly hope the compiler will
indeed inline most of the glue.

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:25 PM
gracinet updated this revision to Diff 19135.Jan 10 2020, 10:03 AM
gracinet updated this revision to Diff 19325.Jan 15 2020, 6:47 PM
kevincox accepted this revision.Jan 16 2020, 5:10 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
240

I don't think this variable helps readability. I would just repeat self.len().

241

I would add a self.is_empty() helper. It's good practice for anything that has a .len().

gracinet updated this revision to Diff 19632.Jan 27 2020, 10:49 AM
gracinet marked 2 inline comments as done.Jan 27 2020, 10:53 AM
gracinet added inline comments.
rust/hg-core/src/revlog/nodemap.rs
241

Sure

gracinet marked an inline comment as done.Jan 27 2020, 2:13 PM
gracinet added a commit: rHG220d4d2e3185: rust-nodemap: abstracting the indexing.
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG220d4d2e3185: rust-nodemap: abstracting the indexing (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 (24 lines)

Diff 19645

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

//! 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, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex, Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex,
}; };
use std::fmt; use std::fmt;
use std::ops::Deref; use std::ops::Deref;
use std::ops::Index;
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq)]
pub enum NodeMapError { pub enum NodeMapError {
MultipleResults, MultipleResults,
InvalidNodePrefix(NodeError), InvalidNodePrefix(NodeError),
/// A `Revision` stored in the nodemap could not be found in the index /// A `Revision` stored in the nodemap could not be found in the index
RevisionNotInIndex(Revision), RevisionNotInIndex(Revision),
} }
} }
} }
/// A 16-radix tree with the root block at the end /// A 16-radix tree with the root block at the end
pub struct NodeTree { pub struct NodeTree {
readonly: Box<dyn Deref<Target = [Block]> + Send>, readonly: Box<dyn Deref<Target = [Block]> + Send>,
} }
impl Index<usize> for NodeTree {
type Output = Block;
fn index(&self, i: usize) -> &Block {
&self.readonly[i]
}
}
/// 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<'p>( fn has_prefix_or_none<'p>(
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
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
} }
}) })
} }
impl NodeTree { impl NodeTree {
fn len(&self) -> usize {
self.readonly.len()
}
fn is_empty(&self) -> bool {
self.len() == 0
}
/// Main working method for `NodeTree` searches /// Main working method for `NodeTree` searches
/// ///
/// This partial implementation lacks special cases for NULL_REVISION /// This partial implementation lacks special cases for NULL_REVISION
fn lookup<'p>( fn lookup<'p>(
&self, &self,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
let blocks: &[Block] = &*self.readonly; if self.is_empty() {
kevincoxUnsubmitted
Done

I don't think this variable helps readability. I would just repeat self.len().

kevincox: I don't think this variable helps readability. I would just repeat `self.len()`.
if blocks.is_empty() {
return Ok(None); return Ok(None);
kevincoxUnsubmitted
Done

I would add a self.is_empty() helper. It's good practice for anything that has a .len().

kevincox: I would add a `self.is_empty()` helper. It's good practice for anything that has a `.len()`.
gracinetAuthorUnsubmitted
Done

Sure

gracinet: Sure
} }
let mut visit = blocks.len() - 1; let mut visit = self.len() - 1;
for i in 0..prefix.len() { for i in 0..prefix.len() {
let nybble = prefix.get_nybble(i); let nybble = prefix.get_nybble(i);
match blocks[visit].get(nybble) { match self[visit].get(nybble) {
Element::None => return Ok(None), Element::None => return Ok(None),
Element::Rev(r) => return Ok(Some(r)), Element::Rev(r) => return Ok(Some(r)),
Element::Block(idx) => visit = idx, Element::Block(idx) => visit = idx,
} }
} }
Err(NodeMapError::MultipleResults) Err(NodeMapError::MultipleResults)
} }
} }