This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1289

radixbuf: initial boilerplate
ClosedPublic

Authored by quark on Nov 2 2017, 2:45 PM.
Tags
None
Subscribers
jsgf

Details

Reviewers
jsgf
durham
Group Reviewers
Restricted Project
Commits
rFBHGX5c8a6bd3d751: radixbuf: initial boilerplate
Summary

This is an implementation of the radix tree in Rust that converts [u8] to
integers. It is intended to be used as a basic building block for efficient
source-control related key-value lookups. For example, to convert a commit
hash to an internal number (ex. revision number).

The file format is quite similar to the C radix tree implementation in
mercurial/cext/revlog.c, with some improvements:

  • Not coupled with CPython APIs
  • Not coupled with revlog or revision numbers
  • Not coupled with malloc / realloc so the abstraction managing the buffer could be more flexible
  • Support variant-length keys
  • Explicitly use little-endian so the format is platform-independent
Test Plan

cargo test --lib

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Nov 2 2017, 2:45 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 2 2017, 2:45 PM
jsgf requested changes to this revision.Nov 2 2017, 3:54 PM
jsgf added a subscriber: jsgf.
jsgf added inline comments.
rust/radix204/src/constants.rs
8 ↗(On Diff #3209)

Why not define this next to where the type is defined? Or even part of the type itself, so you can use KeyId::MAX.

9 ↗(On Diff #3209)

This seems super-brittle. What if we ever wanted a different size hash, or some kind of other per-key metadata (like what kind of entity its a reference to)?

rust/radix204/src/types.rs
12–13 ↗(On Diff #3209)

Why not use newtypes for these? Ie

#[derive(Debug, Eq, Partialeq, ...)]
pub struct KeyId(u32);

Then you can control how they get used, they'll print distinctively in debug output, etc.

This revision now requires changes to proceed.Nov 2 2017, 3:54 PM
quark added inline comments.Nov 2 2017, 6:35 PM
rust/radix204/src/constants.rs
8 ↗(On Diff #3209)

They were defined in types.rs until I thought types was not an accurate word for them.

9 ↗(On Diff #3209)

I was using it as a constant somewhere. Since both const fn (ideally mem::size_of) and associated consts are unstable. Now that I scan the code base it does not have to be a constant. I'll make it a function.

rust/radix204/src/types.rs
12–13 ↗(On Diff #3209)

Was doing that until I found I need to redefine lots of proxy methods. But that is actually cleaner since required methods are explicitly listed. Will change.

quark edited the summary of this revision. (Show Details)Nov 3 2017, 2:17 AM
quark updated this revision to Diff 3249.
quark edited the summary of this revision. (Show Details)Nov 6 2017, 2:10 PM
quark edited the test plan for this revision. (Show Details)
quark updated this revision to Diff 3294.
quark edited the summary of this revision. (Show Details)Nov 11 2017, 1:33 AM
quark retitled this revision from radix204: initial boilerplate to radix20: initial boilerplate.
quark updated this revision to Diff 3417.
quark edited the summary of this revision. (Show Details)Nov 15 2017, 8:55 PM
quark retitled this revision from radix20: initial boilerplate to radixbuf: initial boilerplate.
quark updated this revision to Diff 3543.
durham accepted this revision.Nov 29 2017, 4:43 PM
Closed by commit rFBHGX5c8a6bd3d751: radixbuf: initial boilerplate (authored by quark). · Explain WhyDec 15 2017, 2:34 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 4505

rust/radixbuf/Cargo.toml

  • This file was added.
[package]
name = "radixbuf"
version = "0.1.0"
[dependencies]
error-chain = "0.11"
vlqencoding = { path = "../vlqencoding" }
[dev-dependencies]
quickcheck = "0.4"
rand = "0.3"
rustc-test = "0.2"

rust/radixbuf/README.md

  • This file was added.
# radixbuf
Radix tree based on plain buffers.
There are 2 plain buffers:
- Radix buffer: One or more radix trees mapping keys to their IDs. Read and write by the library.
- Key buffer: The source of truth of full keys. Read by the library, write by the application.
An ID of a key could be an offset, or other meaningful numbers understood by the function reading a key.

rust/radixbuf/src/errors.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
error_chain! {
foreign_links {
Io(::std::io::Error);
}
errors {
}
}

rust/radixbuf/src/lib.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
#[macro_use]
extern crate error_chain;
#[cfg(test)]
#[macro_use]
extern crate quickcheck;
#[cfg(test)]
extern crate rand;
#[cfg(test)]
extern crate test;
extern crate vlqencoding;
pub mod errors;