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
Lint Skipped
Unit
Unit Tests Skipped

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 3848

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,
} }
} }