This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1510

treedirstate: extract serialization methods to separate module
ClosedPublic

Authored by mbthomas on Nov 24 2017, 11:53 AM.
Tags
None
Subscribers
None

Details

Reviewers
stash
durham
Group Reviewers
Restricted Project
Commits
rFBHGXe2f0a8a03d2d: treedirstate: extract serialization methods to separate module
Summary

The serialization and deserialization of the treedirstate tree file is
scattered across various functions in several files. Gather these together in
a single module so that the file format is obvious.

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

mbthomas created this revision.Nov 24 2017, 11:53 AM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 24 2017, 11:53 AM
mbthomas updated this revision to Diff 3838.Nov 24 2017, 2:46 PM
stash accepted this revision.Nov 27 2017, 4:58 AM
This revision is now accepted and ready to land.Nov 27 2017, 4:58 AM
durham accepted this revision.Nov 27 2017, 1:08 PM
Closed by commit rFBHGXe2f0a8a03d2d: treedirstate: extract serialization methods to separate module (authored by mbthomas). · Explain WhyNov 28 2017, 6:03 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 3944

rust/treedirstate/src/dirstate.rs

// Copyright Facebook, Inc. 2017 // Copyright Facebook, Inc. 2017
//! Directory State. //! Directory State.
use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
use errors::*; use errors::*;
use filestore::FileStore; use filestore::FileStore;
use std::io::{Cursor, Read, Write}; use serialization::Serializable;
use std::io::Cursor;
use std::path::Path; use std::path::Path;
use store::{BlockId, NullStore, Store, StoreView}; use store::{BlockId, NullStore, Store, StoreView};
use tree::{Key, KeyRef, Storable, Tree}; use tree::{Key, KeyRef, Tree};
/// Marker indicating that a block is probably a root node.
const MAGIC: &[u8] = b"////";
const MAGIC_LEN: usize = 4;
/// Selected backend implementation for the dirstate. /// Selected backend implementation for the dirstate.
enum Backend { enum Backend {
/// The dirstate is not currently backed by a file. /// The dirstate is not currently backed by a file.
Empty(NullStore), Empty(NullStore),
/// The dirstate is backed by a file on disk. /// The dirstate is backed by a file on disk.
File(FileStore), File(FileStore),
/// The tree of removed files. /// The tree of removed files.
removed: Tree<T>, removed: Tree<T>,
/// The ID of the root block. /// The ID of the root block.
root_id: Option<BlockId>, root_id: Option<BlockId>,
} }
impl<T: Storable + Clone> Dirstate<T> { /// Representation of the root of a dirstate tree that can be serialized to disk.
pub(crate) struct DirstateRoot {
pub(crate) tracked_root_id: BlockId,
pub(crate) tracked_file_count: u32,
pub(crate) removed_root_id: BlockId,
pub(crate) removed_file_count: u32,
}
impl<T: Serializable + Clone> Dirstate<T> {
/// Create a new, empty dirstate, with no backend store. /// Create a new, empty dirstate, with no backend store.
pub fn new() -> Dirstate<T> { pub fn new() -> Dirstate<T> {
Dirstate { Dirstate {
store: Backend::Empty(NullStore::new()), store: Backend::Empty(NullStore::new()),
tracked: Tree::new(), tracked: Tree::new(),
removed: Tree::new(), removed: Tree::new(),
root_id: None, root_id: None,
} }
} }
/// Open an existing dirstate file. The entries in the file will not be materialized from /// Open an existing dirstate file. The entries in the file will not be materialized from
/// the disk until they are accessed. /// the disk until they are accessed.
pub fn open<P: AsRef<Path>>(&mut self, filename: P, root_id: BlockId) -> Result<()> { pub fn open<P: AsRef<Path>>(&mut self, filename: P, root_id: BlockId) -> Result<()> {
let store = FileStore::open(filename)?; let store = FileStore::open(filename)?;
{ let root = DirstateRoot::deserialize(&mut Cursor::new(store.read(root_id)?))?;
let root_data = store.read(root_id)?; self.tracked = Tree::open(root.tracked_root_id, root.tracked_file_count);
let mut root = Cursor::new(root_data); self.removed = Tree::open(root.removed_root_id, root.removed_file_count);
// Sanity check that this is a root
let mut buffer = [0; MAGIC_LEN];
root.read_exact(&mut buffer)?;
if buffer != MAGIC {
bail!(ErrorKind::InvalidStoreId(root_id.0));
}
let tracked_root_id = BlockId(root.read_u64::<BigEndian>()?);
let tracked_file_count = root.read_u32::<BigEndian>()?;
let removed_root_id = BlockId(root.read_u64::<BigEndian>()?);
let removed_file_count = root.read_u32::<BigEndian>()?;
self.tracked = Tree::open(tracked_root_id, tracked_file_count);
self.removed = Tree::open(removed_root_id, removed_file_count);
}
self.store = Backend::File(store); self.store = Backend::File(store);
self.root_id = Some(root_id); self.root_id = Some(root_id);
Ok(()) Ok(())
} }
/// Write a new root block to the store. This contains the identities of the tree roots /// Write a new root block to the store. This contains the identities of the tree roots
/// and the tree sizes. /// and the tree sizes.
fn write_root(&mut self) -> Result<()> { fn write_root(&mut self) -> Result<()> {
let root = DirstateRoot {
tracked_root_id: self.tracked.root_id().unwrap(),
tracked_file_count: self.tracked.file_count(),
removed_root_id: self.removed.root_id().unwrap(),
removed_file_count: self.removed.file_count(),
};
let store = self.store.store(); let store = self.store.store();
let mut data = Vec::new(); let mut data = Vec::new();
data.write(MAGIC)?; root.serialize(&mut data)?;
data.write_u64::<BigEndian>(self.tracked.root_id().unwrap().0)?;
data.write_u32::<BigEndian>(self.tracked.file_count())?;
data.write_u64::<BigEndian>(self.removed.root_id().unwrap().0)?;
data.write_u32::<BigEndian>(self.removed.file_count())?;
self.root_id = Some(store.append(&data)?); self.root_id = Some(store.append(&data)?);
store.flush()?; store.flush()?;
Ok(()) Ok(())
} }
/// Write a full copy of the dirstate out to a new file. /// Write a full copy of the dirstate out to a new file.
pub fn write_full<P: AsRef<Path>>(&mut self, filename: P) -> Result<()> { pub fn write_full<P: AsRef<Path>>(&mut self, filename: P) -> Result<()> {
{ {
self.tracked.clear_filtered_keys(); self.tracked.clear_filtered_keys();
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use dirstate::Dirstate; use dirstate::Dirstate;
use tempdir::TempDir; use tempdir::TempDir;
use tree::Storable;
use std::io::{Read, Write}; use std::io::{Read, Write};
use byteorder::{ReadBytesExt, WriteBytesExt}; use byteorder::{ReadBytesExt, WriteBytesExt};
use serialization::Serializable;
use errors::*; use errors::*;
#[derive(PartialEq, Clone, Debug)] #[derive(PartialEq, Clone, Debug)]
struct State(char); struct State(char);
impl Storable for State { impl Serializable for State {
fn write(&self, w: &mut Write) -> Result<()> { fn serialize(&self, w: &mut Write) -> Result<()> {
w.write_u8(self.0 as u8)?; w.write_u8(self.0 as u8)?;
Ok(()) Ok(())
} }
fn read(r: &mut Read) -> Result<State> { fn deserialize(r: &mut Read) -> Result<State> {
Ok(State(r.read_u8()? as char)) Ok(State(r.read_u8()? as char))
} }
} }
#[test] #[test]
fn goodpath() { fn goodpath() {
let dir = TempDir::new("dirstate_test").expect("create temp dir"); let dir = TempDir::new("dirstate_test").expect("create temp dir");
let p = dir.path().join("store"); let p = dir.path().join("store");

rust/treedirstate/src/filestate.rs

// Copyright Facebook, Inc. 2017 // Copyright Facebook, Inc. 2017
//! File State. //! File State.
use byteorder::{ReadBytesExt, WriteBytesExt};
use errors::*;
use std::io::{Read, Write};
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: u8, pub state: u8,
FileState { FileState {
state, state,
mode, mode,
size, size,
mtime, mtime,
} }
} }
} }
impl Storable for FileState {
/// Write a file entry to the store.
fn write(&self, mut w: &mut Write) -> Result<()> {
w.write_u8(self.state)?;
w.write_vlq(self.mode)?;
w.write_vlq(self.size)?;
w.write_vlq(self.mtime)?;
Ok(())
}
/// Read an entry from the store.
fn read(mut r: &mut Read) -> Result<FileState> {
let state = r.read_u8()?;
let mode = r.read_vlq()?;
let size = r.read_vlq()?;
let mtime = r.read_vlq()?;
Ok(FileState {
state,
mode,
size,
mtime,
})
}
}

rust/treedirstate/src/lib.rs

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))]
#[allow(non_camel_case_types)] #[allow(non_camel_case_types)]
pub mod python; pub mod python;
pub mod serialization;
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/serialization.rs

  • This file was added.
// Copyright Facebook, Inc. 2017
//! Trait for serialization and deserialization of tree data.
use filestate::FileState;
use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
use errors::*;
use std::io::{Read, Write};
use vlqencoding::{VLQDecode, VLQEncode};
use tree::{Key, Node, NodeEntry, NodeEntryMap};
use dirstate::DirstateRoot;
use store::BlockId;
pub trait Serializable
where
Self: Sized,
{
/// Serialize the storable data to a `Write` stream.
fn serialize(&self, w: &mut Write) -> Result<()>;
/// Deserialize a new data item from a `Read` stream.
fn deserialize(r: &mut Read) -> Result<Self>;
}
impl Serializable for FileState {
/// Write a file entry to the store.
fn serialize(&self, mut w: &mut Write) -> Result<()> {
w.write_u8(self.state)?;
w.write_vlq(self.mode)?;
w.write_vlq(self.size)?;
w.write_vlq(self.mtime)?;
Ok(())
}
/// Read an entry from the store.
fn deserialize(mut r: &mut Read) -> Result<FileState> {
let state = r.read_u8()?;
let mode = r.read_vlq()?;
let size = r.read_vlq()?;
let mtime = r.read_vlq()?;
Ok(FileState {
state,
mode,
size,
mtime,
})
}
}
/// Deserialize a single entry in a node's entry map. Returns the name and the entry.
fn deserialize_node_entry<T>(mut r: &mut Read) -> Result<(Key, NodeEntry<T>)>
where
T: Serializable + Clone,
{
let entry_type = r.read_u8()?;
match entry_type {
b'f' => {
// File entry.
let data = T::deserialize(r)?;
let name_len = r.read_vlq()?;
let mut name = Vec::with_capacity(name_len);
unsafe {
// Safe as we've just allocated the buffer and are about to read into it.
name.set_len(name_len);
}
r.read_exact(name.as_mut_slice())?;
Ok((name, NodeEntry::File(data)))
}
b'd' => {
// Directory entry.
let id = r.read_vlq()?;
let name_len = r.read_vlq()?;
let mut name = Vec::with_capacity(name_len);
unsafe {
// Safe as we've just allocated the buffer and are about to read into it.
name.set_len(name_len);
}
r.read_exact(name.as_mut_slice())?;
Ok((name, NodeEntry::Directory(Node::open(BlockId(id)))))
}
_ => {
bail!(ErrorKind::CorruptTree);
}
}
}
impl<T: Serializable + Clone> Serializable for NodeEntryMap<T> {
fn deserialize(r: &mut Read) -> Result<NodeEntryMap<T>> {
let mut r = r;
let count = r.read_vlq()?;
let mut entries = NodeEntryMap::with_capacity(count);
for _i in 0..count {
let (name, entry) = deserialize_node_entry(r)?;
entries.insert_hint_end(name, entry);
}
Ok(entries)
}
fn serialize(&self, w: &mut Write) -> Result<()> {
let mut w = w;
w.write_vlq(self.len())?;
for (name, entry) in self.iter() {
match entry {
&NodeEntry::File(ref file) => {
w.write_u8(b'f')?;
file.serialize(w)?;
}
&NodeEntry::Directory(ref node) => {
w.write_u8(b'd')?;
w.write_vlq(node.id.unwrap().0)?;
}
}
w.write_vlq(name.len())?;
w.write(name)?;
}
Ok(())
}
}
/// Marker indicating that a block is probably a root node.
const DIRSTATE_ROOT_MAGIC_LEN: usize = 4;
const DIRSTATE_ROOT_MAGIC: [u8; DIRSTATE_ROOT_MAGIC_LEN] = *b"////";
impl Serializable for DirstateRoot {
fn deserialize(r: &mut Read) -> Result<DirstateRoot> {
// Sanity check that this is a root
let mut buffer = [0; DIRSTATE_ROOT_MAGIC_LEN];
r.read_exact(&mut buffer)?;
if buffer != DIRSTATE_ROOT_MAGIC {
bail!(ErrorKind::CorruptTree);
}
let tracked_root_id = BlockId(r.read_u64::<BigEndian>()?);
let tracked_file_count = r.read_u32::<BigEndian>()?;
let removed_root_id = BlockId(r.read_u64::<BigEndian>()?);
let removed_file_count = r.read_u32::<BigEndian>()?;
Ok(DirstateRoot {
tracked_root_id,
tracked_file_count,
removed_root_id,
removed_file_count,
})
}
fn serialize(&self, w: &mut Write) -> Result<()> {
w.write(&DIRSTATE_ROOT_MAGIC)?;
w.write_u64::<BigEndian>(self.tracked_root_id.0)?;
w.write_u32::<BigEndian>(self.tracked_file_count)?;
w.write_u64::<BigEndian>(self.removed_root_id.0)?;
w.write_u32::<BigEndian>(self.removed_file_count)?;
Ok(())
}
}

rust/treedirstate/src/tree.rs

// Copyright Facebook, Inc. 2017 // Copyright Facebook, Inc. 2017
//! Directory State Tree. //! Directory State Tree.
use byteorder::{ReadBytesExt, WriteBytesExt};
use errors::*; use errors::*;
use serialization::Serializable;
use std::collections::Bound; use std::collections::Bound;
use std::io::{Cursor, Read, Write}; use std::io::Cursor;
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.
pub trait Storable
where
Self: Sized,
{
/// Serialize the storable data to a `Write` stream.
fn write(&self, w: &mut Write) -> Result<()>;
/// Deserialize a new data item from a `Read` stream.
fn read(r: &mut Read) -> Result<Self>;
}
/// A node entry is an entry in a directory, either a file or another directory. /// A node entry is an entry in a directory, either a file or another directory.
#[derive(Debug)] #[derive(Debug)]
enum NodeEntry<T> { pub(crate) enum NodeEntry<T> {
Directory(Node<T>), Directory(Node<T>),
File(T), File(T),
} }
/// Filenames are buffers of bytes. They're not stored in Strings as they may not be UTF-8. /// Filenames are buffers of bytes. They're not stored in Strings as they may not be UTF-8.
pub type Key = Vec<u8>; pub type Key = Vec<u8>;
pub type KeyRef<'a> = &'a [u8]; pub type KeyRef<'a> = &'a [u8];
/// Store the node entries in an ordered map from name to node entry. /// Store the node entries in an ordered map from name to node entry.
type NodeEntryMap<T> = VecMap<Key, NodeEntry<T>>; pub(crate) type NodeEntryMap<T> = VecMap<Key, NodeEntry<T>>;
/// The contents of a directory. /// The contents of a directory.
#[derive(Debug)] #[derive(Debug)]
struct Node<T> { pub(crate) struct Node<T> {
/// The ID of the directory in the store. If None, this directory has not yet been /// The ID of the directory in the store. If None, this directory has not yet been
/// written to the back-end store in its current state. /// written to the back-end store in its current state.
id: Option<BlockId>, pub(crate) id: Option<BlockId>,
/// The set of files and directories in this directory, indexed by their name. If None, /// The set of files and directories in this directory, indexed by their name. If None,
/// then the ID must not be None, and the entries are yet to be loaded from the back-end /// then the ID must not be None, and the entries are yet to be loaded from the back-end
/// store. /// store.
entries: Option<NodeEntryMap<T>>, pub(crate) entries: Option<NodeEntryMap<T>>,
/// A map from keys that have been filtered through a case-folding filter function to the /// A map from keys that have been filtered through a case-folding filter function to the
/// original key. This is used for case-folded look-ups. Filtered values are cached, so /// original key. This is used for case-folded look-ups. Filtered values are cached, so
/// only a single filter function can be used with a tree. Call `clear_filtered_keys` to /// only a single filter function can be used with a tree. Call `clear_filtered_keys` to
/// clear the cache in order to use a different filter function. /// clear the cache in order to use a different filter function.
filtered_keys: Option<VecMap<Key, Key>>, filtered_keys: Option<VecMap<Key, Key>>,
} }
for (index, value) in key.iter().take(key.len() - 1).enumerate() { for (index, value) in key.iter().take(key.len() - 1).enumerate() {
if *value == b'/' { if *value == b'/' {
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: Serializable + Clone> Node<T> {
/// Read an entry from the store. Returns the name and the entry.
fn read(mut r: &mut Read) -> Result<(Key, NodeEntry<T>)> {
let entry_type = r.read_u8()?;
match entry_type {
b'f' => {
// File entry.
let data = T::read(r)?;
let name_len = r.read_vlq()?;
let mut name = Vec::with_capacity(name_len);
unsafe {
// Safe as we've just allocated the buffer and are about to read into it.
name.set_len(name_len);
}
r.read_exact(name.as_mut_slice())?;
Ok((name, NodeEntry::File(data)))
}
b'd' => {
// Directory entry.
let id = r.read_vlq()?;
let name_len = r.read_vlq()?;
let mut name = Vec::with_capacity(name_len);
unsafe {
// Safe as we've just allocated the buffer and are about to read into it.
name.set_len(name_len);
}
r.read_exact(name.as_mut_slice())?;
Ok((name, NodeEntry::Directory(Node::open(BlockId(id)))))
}
_ => {
bail!(ErrorKind::CorruptTree);
}
}
}
}
impl<T: Storable + Clone> Node<T> {
/// Create a new empty Node. This has no ID as it is not yet written to the store. /// Create a new empty Node. This has no ID as it is not yet written to the store.
fn new() -> Node<T> { fn new() -> Node<T> {
Node { Node {
id: None, id: None,
entries: Some(NodeEntryMap::new()), entries: Some(NodeEntryMap::new()),
filtered_keys: None, filtered_keys: None,
} }
} }
/// Create a new Node for an existing entry in the store. The entries are not loaded until /// Create a new Node for an existing entry in the store. The entries are not loaded until
/// the load method is called. /// the load method is called.
fn open(id: BlockId) -> Node<T> { pub(crate) fn open(id: BlockId) -> Node<T> {
Node { Node {
id: Some(id), id: Some(id),
entries: None, entries: None,
filtered_keys: None, filtered_keys: None,
} }
} }
/// Attempt to load a node from a store. /// Attempt to load a node from a store.
fn load(&mut self, store: &StoreView) -> Result<()> { fn load(&mut self, store: &StoreView) -> Result<()> {
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; self.entries = Some(NodeEntryMap::<T>::deserialize(&mut Cursor::new(data))?);
let mut cursor = Cursor::new(data);
let count = cursor.read_vlq()?;
let mut entries = NodeEntryMap::with_capacity(count);
while cursor.position() < len {
let (name, entry) = NodeEntry::read(&mut cursor)?;
entries.insert_hint_end(name, entry);
}
self.entries = Some(entries);
Ok(()) Ok(())
} }
/// Get access to the node entries, ensuring they are loaded first. /// Get access to the node entries, ensuring they are loaded first.
#[inline] #[inline]
fn load_entries(&mut self, store: &StoreView) -> Result<&mut NodeEntryMap<T>> { fn load_entries(&mut self, store: &StoreView) -> Result<&mut NodeEntryMap<T>> {
self.load(store)?; self.load(store)?;
let entries = self.entries let entries = self.entries
.as_mut() .as_mut()
.expect("Entries should have been populated by loading"); .expect("Entries should have been populated by loading");
Ok(entries) Ok(entries)
} }
/// 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_vlq(entries.len())?; entries.serialize(&mut data)?;
for (name, entry) in entries.iter_mut() {
match entry {
&mut NodeEntry::File(ref file) => {
data.write_u8(b'f')?;
file.write(&mut data)?;
}
&mut NodeEntry::Directory(ref mut node) => {
data.write_u8(b'd')?;
data.write_vlq(node.id.unwrap().0)?;
}
}
data.write_vlq(name.len())?;
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.
fn write_full(&mut self, store: &mut Store, old_store: &StoreView) -> Result<()> { fn write_full(&mut self, store: &mut Store, old_store: &StoreView) -> Result<()> {
// Write out all the child nodes. // Write out all the child nodes.
if let &mut NodeEntry::Directory(ref mut node) = v { if let &mut NodeEntry::Directory(ref mut node) = v {
node.clear_filtered_keys(); node.clear_filtered_keys();
} }
} }
} }
} }
} }
impl<T: Storable + Clone> Tree<T> { impl<T: Serializable + Clone> Tree<T> {
/// Create a new empty tree. /// Create a new empty tree.
pub fn new() -> Tree<T> { pub fn new() -> Tree<T> {
Tree { Tree {
root: Node::new(), root: Node::new(),
file_count: 0, file_count: 0,
} }
} }