( )⚙ D1408 treedirstate: use vlqencoding for numbers

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1408

treedirstate: use vlqencoding for numbers
ClosedPublic

Authored by mbthomas on Nov 14 2017, 12:39 PM.
Tags
None
Subscribers
jsgf, quark, durham

Details

Reviewers
durham
Group Reviewers
Restricted Project
Commits
rFBHGXa636c026aa4f: treedirstate: use vlqencoding for numbers
Summary

Change to use VLQ-encoded numbers for everything in the tree file. Block sizes
remain as u32s so that they can be read by the store in a single read
operation, but everything else is a VLQ as it is generally smaller and more
futureproof.

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

mbthomas created this revision.Nov 14 2017, 12:39 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 14 2017, 12:39 PM
mbthomas updated this revision to Diff 3605.Nov 17 2017, 9:45 AM
mbthomas updated this revision to Diff 3660.Nov 20 2017, 12:21 PM
durham added a subscriber: durham.Nov 21 2017, 12:11 PM
durham added inline comments.
rust/treedirstate/src/tree.rs
86

noob question: why did this change?

durham accepted this revision.Nov 21 2017, 12:11 PM
This revision is now accepted and ready to land.Nov 21 2017, 12:11 PM
mbthomas added inline comments.Nov 21 2017, 12:54 PM
rust/treedirstate/src/tree.rs
86

I'm actually not sure. I think it has something to do with the way read_vlq() expects the reference for the Read trait object, but in trying to explain it I realized I don't understand it. I know the compiler requires it, though.

Would any Rust experts care to weigh in?

mbthomas updated this revision to Diff 3735.Nov 21 2017, 1:36 PM
quark added a subscriber: quark.Nov 23 2017, 5:56 PM
quark added inline comments.
rust/treedirstate/src/tree.rs
86

My understanding is &mut Read as a whole implements Read and is not a typical reference despite having the letter &. So

&mut &mut Read

makes it a reference and works.

I guess &mut Read itself can also be implicitly converted to a reference (how?). If itself is not marked as mut, it cannot be converted to a &mut reference. Hence the need of mut.

mbthomas updated this revision to Diff 3829.Nov 24 2017, 11:53 AM
mbthomas updated this revision to Diff 3846.Nov 24 2017, 3:18 PM
Closed by commit rFBHGXa636c026aa4f: treedirstate: use vlqencoding for numbers (authored by mbthomas). · Explain WhyNov 28 2017, 6:02 PM
This revision was automatically updated to reflect the committed changes.
jsgf added a subscriber: jsgf.Dec 6 2017, 6:01 PM
jsgf added inline comments.
rust/treedirstate/src/tree.rs
86

Yeah, there's some subtle things going on here.

It's because .read_vlq() is a method on the VLQDecode trait, not Read. But VLQDecode has a blanket implementation for all types which implement Read.

In this case the object which implements Read is r, which has type &mut Read. The .read_vlq() method takes &mut self as its parameter, so it's getting &mut r as the parameter (hence the requirement for mut r).

But &mut &mut Read doesn't implement Read (and therefore VLQDecode) itself, so the Rust compiler's deref coercion kicks in - effectively, it keeps adding * on the front until either the type doesn't implement Deref (or DerefMut in this case), or it gets a type that matches the signature. (Alternatively it will also add at most one &/&mut if needed, which is why you don't need to keep typing (&foo).bar() for bar(&self)).

This means the end result is an effective method call of:

VLQDecode::read_vlq(*&mut &mut r)

(Though TBH I've probably got some details wrong here.)

But echoing a comment I made earlier in the series, I think it would be better to express this as:

fn read(r: &mut Read) -> Result<(Key, NodeEntry<T>)> {
    let mut r = r;

to keep the confusing extra mut out of the function definition.

Revision Contents
Changeset List

Diff 3735

rust/treedirstate/Cargo.toml

[package] [package]
name = "rusttreedirstate" name = "rusttreedirstate"
version = "0.1.0" version = "0.1.0"
authors = ["Facebook Source Control Team <sourcecontrol-dev@fb.com>"] authors = ["Facebook Source Control Team <sourcecontrol-dev@fb.com>"]
[profile.release] [profile.release]
lto = true lto = true
[lib] [lib]
name = "rusttreedirstate" name = "rusttreedirstate"
crate-type = ["cdylib"] crate-type = ["cdylib"]
[dependencies] [dependencies]
byteorder = "*" byteorder = "*"
error-chain = "*" error-chain = "*"
vlqencoding = { version = "*", path = "../vlqencoding" }
[dev-dependencies] [dev-dependencies]
itertools = "0.7.2" itertools = "0.7.2"
quickcheck = "*" quickcheck = "*"
tempdir = "*" tempdir = "*"
[dependencies.cpython] [dependencies.cpython]
version = "0.1" version = "0.1"
default-features = false default-features = false
features = ["python27-sys", "extension-module-2-7"] features = ["python27-sys", "extension-module-2-7"]
git = "https://github.com/dgrunwald/rust-cpython.git" git = "https://github.com/dgrunwald/rust-cpython.git"

rust/treedirstate/src/filestate.rs

// Copyright Facebook, Inc. 2017 // Copyright Facebook, Inc. 2017
//! File State. //! File State.
use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt}; use byteorder::{ReadBytesExt, WriteBytesExt};
use errors::*; use errors::*;
use std::io::{Read, Write}; use std::io::{Read, Write};
use tree::Storable; use tree::Storable;
use vlqencoding::{VLQDecode, VLQEncode};
/// Information relating to a file in the dirstate. /// Information relating to a file in the dirstate.
#[derive(Debug, PartialEq, Copy, Clone)] #[derive(Debug, PartialEq, Copy, Clone)]
pub struct FileState { pub struct FileState {
/// State of the file, as recorded by Mercurial. Mercurial uses a single character to /// State of the file, as recorded by Mercurial. Mercurial uses a single character to
/// represent the current state of the file. Only a single byte is used in the file, so only /// represent the current state of the file. Only a single byte is used in the file, so only
/// ASCII characters are valid here. /// ASCII characters are valid here.
pub state: char, pub state: char,
size, size,
mtime, mtime,
} }
} }
} }
impl Storable for FileState { impl Storable for FileState {
/// Write a file entry to the store. /// Write a file entry to the store.
fn write(&self, w: &mut Write) -> Result<()> { fn write(&self, mut w: &mut Write) -> Result<()> {
w.write_u8(self.state as u8)?; w.write_u8(self.state as u8)?;
w.write_u32::<BigEndian>(self.mode)?; w.write_vlq(self.mode)?;
w.write_i32::<BigEndian>(self.size)?; w.write_vlq(self.size)?;
w.write_i32::<BigEndian>(self.mtime)?; w.write_vlq(self.mtime)?;
Ok(()) Ok(())
} }
/// Read an entry from the store. /// Read an entry from the store.
fn read(r: &mut Read) -> Result<FileState> { fn read(mut r: &mut Read) -> Result<FileState> {
let state = r.read_u8()? as char; let state = r.read_u8()? as char;
let mode = r.read_u32::<BigEndian>()?; let mode = r.read_vlq()?;
let size = r.read_i32::<BigEndian>()?; let size = r.read_vlq()?;
let mtime = r.read_i32::<BigEndian>()?; let mtime = r.read_vlq()?;
Ok(FileState { Ok(FileState {
state, state,
mode, mode,
size, size,
mtime, mtime,
}) })
} }
} }

rust/treedirstate/src/lib.rs

#[cfg(test)] #[cfg(test)]
#[macro_use] #[macro_use]
extern crate quickcheck; extern crate quickcheck;
#[cfg(test)] #[cfg(test)]
extern crate tempdir; extern crate tempdir;
extern crate vlqencoding;
pub mod dirstate; pub mod dirstate;
pub mod errors; pub mod errors;
pub mod filestate; pub mod filestate;
pub mod filestore; pub mod filestore;
#[cfg(not(test))] #[cfg(not(test))]
pub mod python; pub mod python;
pub mod store; pub mod store;
pub mod tree; pub mod tree;
pub mod vecmap; pub mod vecmap;
pub use errors::*; pub use errors::*;

rust/treedirstate/src/tree.rs

// Copyright Facebook, Inc. 2017 // Copyright Facebook, Inc. 2017
//! Directory State Tree. //! Directory State Tree.
use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt}; use byteorder::{ReadBytesExt, WriteBytesExt};
use errors::*; use errors::*;
use std::collections::Bound; use std::collections::Bound;
use std::io::{Cursor, Read, Write}; use std::io::{Cursor, Read, Write};
use store::{BlockId, Store, StoreView}; use store::{BlockId, Store, StoreView};
use vecmap::VecMap; use vecmap::VecMap;
use vlqencoding::{VLQDecode, VLQEncode};
/// Trait that must be implemented by types that can be stored as the value in the tree. /// Trait that must be implemented by types that can be stored as the value in the tree.
pub trait Storable pub trait Storable
where where
Self: Sized, Self: Sized,
{ {
/// Serialize the storable data to a `Write` stream. /// Serialize the storable data to a `Write` stream.
fn write(&self, w: &mut Write) -> Result<()>; fn write(&self, w: &mut Write) -> Result<()>;
return (&key[..index + 1], Some(&key[index + 1..])); return (&key[..index + 1], Some(&key[index + 1..]));
} }
} }
(key, None) (key, None)
} }
impl<T: Storable + Clone> NodeEntry<T> { impl<T: Storable + Clone> NodeEntry<T> {
/// Read an entry from the store. Returns the name and the entry. /// Read an entry from the store. Returns the name and the entry.
fn read(r: &mut Read) -> Result<(Key, NodeEntry<T>)> { fn read(mut r: &mut Read) -> Result<(Key, NodeEntry<T>)> {
durhamUnsubmitted
Not Done

noob question: why did this change?

durham: noob question: why did this change?
mbthomasAuthorUnsubmitted
Not Done

I'm actually not sure. I think it has something to do with the way read_vlq() expects the reference for the Read trait object, but in trying to explain it I realized I don't understand it. I know the compiler requires it, though.

Would any Rust experts care to weigh in?

mbthomas: I'm actually not sure. I think it has something to do with the way `read_vlq()` expects the…
quarkUnsubmitted
Not Done

My understanding is &mut Read as a whole implements Read and is not a typical reference despite having the letter &. So

&mut &mut Read

makes it a reference and works.

I guess &mut Read itself can also be implicitly converted to a reference (how?). If itself is not marked as mut, it cannot be converted to a &mut reference. Hence the need of mut.

quark: My understanding is `&mut Read` as a whole implements `Read` and is not a typical reference…
jsgfUnsubmitted
Not Done

Yeah, there's some subtle things going on here.

It's because .read_vlq() is a method on the VLQDecode trait, not Read. But VLQDecode has a blanket implementation for all types which implement Read.

In this case the object which implements Read is r, which has type &mut Read. The .read_vlq() method takes &mut self as its parameter, so it's getting &mut r as the parameter (hence the requirement for mut r).

But &mut &mut Read doesn't implement Read (and therefore VLQDecode) itself, so the Rust compiler's deref coercion kicks in - effectively, it keeps adding * on the front until either the type doesn't implement Deref (or DerefMut in this case), or it gets a type that matches the signature. (Alternatively it will also add at most one &/&mut if needed, which is why you don't need to keep typing (&foo).bar() for bar(&self)).

This means the end result is an effective method call of:

VLQDecode::read_vlq(*&mut &mut r)

(Though TBH I've probably got some details wrong here.)

But echoing a comment I made earlier in the series, I think it would be better to express this as:

fn read(r: &mut Read) -> Result<(Key, NodeEntry<T>)> {
    let mut r = r;

to keep the confusing extra mut out of the function definition.

jsgf: Yeah, there's some subtle things going on here. It's because `.read_vlq()` is a method on the…
let entry_type = r.read_u8()?; let entry_type = r.read_u8()?;
match entry_type { match entry_type {
b'f' => { b'f' => {
// File entry. // File entry.
let data = T::read(r)?; let data = T::read(r)?;
let name_len = r.read_u32::<BigEndian>()?; let name_len = r.read_vlq()?;
let mut name = Vec::with_capacity(name_len as usize); let mut name = Vec::with_capacity(name_len);
unsafe { unsafe {
// Safe as we've just allocated the buffer and are about to read into it. // Safe as we've just allocated the buffer and are about to read into it.
name.set_len(name_len as usize); name.set_len(name_len);
} }
r.read_exact(name.as_mut_slice())?; r.read_exact(name.as_mut_slice())?;
Ok((name, NodeEntry::File(data))) Ok((name, NodeEntry::File(data)))
} }
b'd' => { b'd' => {
// Directory entry. // Directory entry.
let id = r.read_u64::<BigEndian>()?; let id = r.read_vlq()?;
let name_len = r.read_u32::<BigEndian>()?; let name_len = r.read_vlq()?;
let mut name = Vec::with_capacity(name_len as usize); let mut name = Vec::with_capacity(name_len);
unsafe { unsafe {
// Safe as we've just allocated the buffer and are about to read into it. // Safe as we've just allocated the buffer and are about to read into it.
name.set_len(name_len as usize); name.set_len(name_len);
} }
r.read_exact(name.as_mut_slice())?; r.read_exact(name.as_mut_slice())?;
Ok((name, NodeEntry::Directory(Node::open(BlockId(id))))) Ok((name, NodeEntry::Directory(Node::open(BlockId(id)))))
} }
_ => { _ => {
bail!(ErrorKind::CorruptTree); bail!(ErrorKind::CorruptTree);
} }
} }
if self.entries.is_some() { if self.entries.is_some() {
// Already loaded. // Already loaded.
return Ok(()); return Ok(());
} }
let id = self.id.expect("Node must have a valid ID to be loaded"); let id = self.id.expect("Node must have a valid ID to be loaded");
let data = store.read(id)?; let data = store.read(id)?;
let len = data.len() as u64; let len = data.len() as u64;
let mut cursor = Cursor::new(data); let mut cursor = Cursor::new(data);
let count = cursor.read_u32::<BigEndian>()? as usize; let count = cursor.read_vlq()?;
let mut entries = NodeEntryMap::with_capacity(count); let mut entries = NodeEntryMap::with_capacity(count);
while cursor.position() < len { while cursor.position() < len {
let (name, entry) = NodeEntry::read(&mut cursor)?; let (name, entry) = NodeEntry::read(&mut cursor)?;
entries.insert_hint_end(name, entry); entries.insert_hint_end(name, entry);
} }
self.entries = Some(entries); self.entries = Some(entries);
Ok(()) Ok(())
} }
/// Writes all entries for this node to the store. Any child directory entries must have /// Writes all entries for this node to the store. Any child directory entries must have
/// had IDs assigned to them. /// had IDs assigned to them.
fn write_entries(&mut self, store: &mut Store) -> Result<()> { fn write_entries(&mut self, store: &mut Store) -> Result<()> {
let mut data = Vec::new(); let mut data = Vec::new();
let entries = self.entries let entries = self.entries
.as_mut() .as_mut()
.expect("Node should have entries populated before writing out."); .expect("Node should have entries populated before writing out.");
data.write_u32::<BigEndian>(entries.len() as u32)?; data.write_vlq(entries.len())?;
for (name, entry) in entries.iter_mut() { for (name, entry) in entries.iter_mut() {
match entry { match entry {
&mut NodeEntry::File(ref file) => { &mut NodeEntry::File(ref file) => {
data.write_u8(b'f')?; data.write_u8(b'f')?;
file.write(&mut data)?; file.write(&mut data)?;
} }
&mut NodeEntry::Directory(ref mut node) => { &mut NodeEntry::Directory(ref mut node) => {
data.write_u8(b'd')?; data.write_u8(b'd')?;
data.write_u64::<BigEndian>(node.id.unwrap().0)?; data.write_vlq(node.id.unwrap().0)?;
} }
} }
data.write_u32::<BigEndian>(name.len() as u32)?; data.write_vlq(name.len())?;
data.write(name)?; data.write(name)?;
} }
self.id = Some(store.append(&data)?); self.id = Some(store.append(&data)?);
Ok(()) Ok(())
} }
/// Perform a full write of the node and its children to the store. Old entries are /// Perform a full write of the node and its children to the store. Old entries are
/// loaded from the old_store before being written back to the new store. /// loaded from the old_store before being written back to the new store.