rust/treedirstate/src/filestate.rs
11	This could be `Copy` too.
13	This is a unicode character. Do you mean `u8`? What are the actual meaningful values this can have? Edit: looks like this should be its own enum type that implements `Storable`.
15–16	What does -ve mean for these? Is 31 bits enough for mtime?
32	Could you use a serde-derived implementation? Or do you not want to take a dependency on serde?
rust/treedirstate/src/tree.rs
7	This is imported by the prelude.
13–20	I found this a little confusing. Would it be more accurate to say that implementations of this trait do no storing directly, but they're responsible for serializing/deserializing to/from a byte stream, and its the Store that's doing the actual storing?
34	`List` seems misleading for a map.
57	Does this need two independent lifetimes? If one is always the same as or shorter than the other, then you can just use one.
68–74	This is equiv aside from handling the last key byte being '/', which would need a second check to return `(key, None)` if the result is `(_, [])`. { let mut bits = key.splitn(2, \|c\| *c == b'/'); (bits.next().expect("empty bits!?"), bits.next()) }
71	`&key[..index + 1]` is fine. rustfmt might want to put spaces around `..`.
85–91	Looks like a name should have its own distinct type and implement `Storable`.
96	This would be cleaner if `BlockId` were a newtype and had its own implementation of `Storable`.
150	I'd push this up to the top: let id = self.id.expect("Node must have valid ID..."); then just put the rest of the code at the function level.
157–158	I'd still `.expect()`.
181–183	Same comment as above - push the non-populated check to the top, then make the rest of the code at function level.
204–207	I'd flip this around by using `.is_none()`, since that's the interesting case here.
217–219	(ditto)
309	Rather than duplicating the `Ok(...)` everywhere, which I think obscures the real logic, it would be better to have something like: let res = if let Some(path) = path { ... }; Ok(res)

rust/treedirstate/src/filestate.rs
13	Mercurial uses a character to represent the state of the file (actually it uses a string, but it only uses one character in those strings). Current values are 'r', 'n', 'a' and 'm', but future changes to Mercurial may add new characters, so I don't want to create an enum here that might cause compatibility problems with those changes. I'm limiting it to a single ASCII character, so maybe u8 would be better here.
15–16	Mercurial uses -ve sizes as sentinel values for special meanings. Unix time is signed, so -ve mtimes just mean before 1970, which is valid even if it is unusual. I switch to VLQ values in a later diff, so the 32-bit limitation won't be a problem.
32	I looked at serde, but it seemed like it did way more than I needed, and then didn't really support this use-case (small chunks of binary data, lazily loaded). I don't think it's really needed here, as this isn't an interchange format.
rust/treedirstate/src/tree.rs
13–20	Yes. Really the trait is supposed to represent the constraints on things that can be the Value type in the tree. The name is supposed to suggest "something that can be put in a Store". Would `TreeValue` be a better name?
57	They do need to be separate lifetimes. One is the lifetime of the nodes within the tree, the other is the lifetime of the `KeyRef` we get passed in by various functions, which are usually different objects with competing requirements on their lifetime constraints. If I try to make them the same lifetime, the compiler complains that there are mutually exclusive conditions that can't be satisfied.
68–74	It's not quite right as I need to include the `'/'` in the first return value. The reason being that we include the trailing / in directory names so that file/directory clashes are allowed to exist (the dirstate, particularly during merges, can include information about both a file called `foo` and a file called `foo/bar`, and I need to handle this).
85–91	Name's type is always `Vec[u8]`, as we're interested in filesystem paths, and functions like `path_recurse` expect and require this. I could type parameterise it, but it seemed like excessive genericness to me.
96	`Storable` is meant to encapsulate "can be the right hand side of the map type", rather than just a generic "can be serialized" trait. I'll try to make that clearer in the comments. I've made BlockId a newtype, but arguably what I should be doing here is extending `Read` and `Write` to add new methods `write_block_id`, `read_block_id`. I've not done that, as it seems like lots of work for what is largely an internal implementation detail. Let me know if you think it would be valuable.

rust/treedirstate/src/tree.rs
191	If we load a node, then immediately write it, are we rewriting it's id in place? Does that mean that node instance is no longer useful for reading against the old store?

rust/treedirstate/src/tree.rs
191	Yes, a node is only valid in one store at a time. The `write_full` method has the side-effect of moving all entries in the tree from the old store to the new store. This is how we repack. I shall beef up the comments on `Tree::write_full` to make it clear that it has this effect.

rust/treedirstate/src/filestate.rs
13	But all the compatibility problems should be caught by unittests, shouldn't they?
15–16	What `-ve` are you talking about :) ?
23	Why not i64?

rust/treedirstate/src/filestate.rs
15–16	`-ve` is "negative". Sorry for the obscure abbreviation.
23	Memory usage, mostly. Mercurial currently uses an i32, so we're no worse with this limit. The file format will later be changed to VLQ, so the on-disk format is safe for future expansion should we need to store >2GB source files.

rust/treedirstate/src/filestate.rs
13	Possibly not. If someone adds an obscure state in core Hg, there may not be a test with treedirstate enabled that triggers it. I think it's safer to stick to the established dirstate API and implement it fully.

rust/treedirstate/src/tree.rs
96	My main concern is mixing the serialization format details with other logic. If you're hand-coding what the on-disk format looks like in the first place, it would be best to have that in completely separate functions from the other logic that operates on those types/fields. In practice I think using a trait to represent the property of "can be serialized/stored/etc" and hiding those details in the implementations of its methods is a nice way to do that, which composes well if you have well-defined types for each part of your structure which can implement that trait (even if they're just very thin newtype wrappers around more mundane types). Since you already have the `Storable` trait which seems to be the right thing, I think you may as well take advantage of it.

rust/treedirstate/src/tree.rs
96	I've refactored this out in D1510. Can you take a look at that and see if it addresses your concerns?

		Path
M		rust/treedirstate/src/errors.rs (3 lines)
A	M	rust/treedirstate/src/filestate.rs (62 lines)
M		rust/treedirstate/src/lib.rs (2 lines)
A	M	rust/treedirstate/src/tree.rs (670 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	3479		Nov 14 2017, 12:39 PM	★	★
Diff 2	3596		Nov 17 2017, 9:44 AM	★	★
Diff 3	3651		Nov 20 2017, 12:20 PM	★	★
Diff 4	3821		Nov 24 2017, 11:52 AM	★	★
Diff 5	3840		Nov 24 2017, 3:18 PM	★	★
Diff 6	3851		Nov 24 2017, 3:35 PM	★	★
Diff 7	3928	rFBHGX95cb381f49cd2d198e34b2a0368c1a4d75a7280d	Nov 28 2017, 7:51 AM	★	★

Status	Author	Revision
Closed	mbthomas	D1528 treedirstate: prevent interference with other dirstate implementations
Closed	mbthomas	D1512 treedirstate: de-genericize Dirstate
Closed	mbthomas	D1510 treedirstate: extract serialization methods to separate module
Closed	mbthomas	D1490 treedirstate: add integration tests
Closed	mbthomas	D1434 treedirstate: add configuration options
Closed	mbthomas	D1412 setup: build treedirstate and rusttreedirstate packages
Closed	mbthomas	D1411 distutils_rust: add distutils extension to compile Rust extension modules
Closed	mbthomas	D1410 perftweaks: support treedirstate maps
Closed	mbthomas	D1409 treedirstate: implement casefolding maps for case insensitive filesystems
Closed	mbthomas	D1408 treedirstate: use vlqencoding for numbers
Closed	mbthomas	D1407 treedirstate: auto-repack treedirstate once it reaches 3x its original size
Closed	mbthomas	D1406 treedirstate: implement efficient case collision detection
Closed	mbthomas	D1405 treedirstate: allow absent non-normal sets
Closed	mbthomas	D1404 treedirstate: clear ambiguous times when writing the dirstate
Closed	mbthomas	D1403 treedirstate: better iteration using visitor pattern
Closed	mbthomas	D1402 treedirstate: cache dirstate data when iterating all files
Closed	mbthomas	D1401 treedirstate: add Python linkage
Closed	mbthomas	D1400 treedirstate: add Dirstate
Closed	mbthomas	D1399 treedirstate: add Tree
Closed	mbthomas	D1398 treedirstate: add FileStore
Closed	mbthomas	D1397 treedirstate: add Store and StoreView traits
Closed	mbthomas	D1396 treedirstate: add vecmap implementation
Closed	mbthomas	D1395 treedirstate: create empty Rust project

Diff 3928

rust/treedirstate/src/errors.rs

	}			}
	InvalidStoreId(id: u64) {			InvalidStoreId(id: u64) {
	description("invalid store id"),			description("invalid store id"),
	display("invalid store id: {}", id),			display("invalid store id: {}", id),
	}			}
	ReadOnlyStore {			ReadOnlyStore {
	description("store is read-only"),			description("store is read-only"),
	}			}
				CorruptTree {
				description("treedirstate is corrupt"),
				}
	}			}
	foreign_links {			foreign_links {
	Io(::std::io::Error);			Io(::std::io::Error);
	Utf8(::std::str::Utf8Error);			Utf8(::std::str::Utf8Error);
	Utf8String(::std::string::FromUtf8Error);			Utf8String(::std::string::FromUtf8Error);
	}			}
	}			}

rust/treedirstate/src/filestate.rs

This file was added.

				// Copyright Facebook, Inc. 2017
				//! File State.

				use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
				use errors::*;
				use std::io::{Read, Write};
				use tree::Storable;

				/// Information relating to a file in the dirstate.
				#[derive(Debug, PartialEq, Copy, Clone)]
				pub struct FileState {
				jsgfUnsubmitted Done This could be `Copy` too. jsgf: This could be `Copy` too.
				/// 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
				jsgfUnsubmitted Done This is a unicode character. Do you mean `u8`? What are the actual meaningful values this can have? Edit: looks like this should be its own enum type that implements `Storable`. jsgf: This is a unicode character. Do you mean `u8`? What are the actual meaningful values this can…
				mbthomasAuthorUnsubmitted Done Mercurial uses a character to represent the state of the file (actually it uses a string, but it only uses one character in those strings). Current values are 'r', 'n', 'a' and 'm', but future changes to Mercurial may add new characters, so I don't want to create an enum here that might cause compatibility problems with those changes. I'm limiting it to a single ASCII character, so maybe u8 would be better here. mbthomas: Mercurial uses a character to represent the state of the file (actually it uses a string, but…
				stashUnsubmitted Not Done But all the compatibility problems should be caught by unittests, shouldn't they? stash: But all the compatibility problems should be caught by unittests, shouldn't they?
				mbthomasAuthorUnsubmitted Not Done Possibly not. If someone adds an obscure state in core Hg, there may not be a test with treedirstate enabled that triggers it. I think it's safer to stick to the established dirstate API and implement it fully. mbthomas: Possibly not. If someone adds an obscure state in core Hg, there may not be a test with…
				/// ASCII characters are valid here.
				pub state: u8,

				jsgfUnsubmitted Done What does -ve mean for these? Is 31 bits enough for mtime? jsgf: What does -ve mean for these? Is 31 bits enough for mtime?
				mbthomasAuthorUnsubmitted Done Mercurial uses -ve sizes as sentinel values for special meanings. Unix time is signed, so -ve mtimes just mean before 1970, which is valid even if it is unusual. I switch to VLQ values in a later diff, so the 32-bit limitation won't be a problem. mbthomas: Mercurial uses -ve sizes as sentinel values for special meanings. Unix time is signed, so -ve…
				stashUnsubmitted Not Done What `-ve` are you talking about :) ? stash: What `-ve` are you talking about :) ?
				mbthomasAuthorUnsubmitted Not Done `-ve` is "negative". Sorry for the obscure abbreviation. mbthomas: `-ve` is "negative". Sorry for the obscure abbreviation.
				/// Mode (permissions) mask for the file.
				pub mode: u32,

				/// Size of the file. Mercurial uses negative sizes for special values, so this must be
				/// signed.
				pub size: i32,

				stashUnsubmitted Not Done Why not i64? stash: Why not i64?
				mbthomasAuthorUnsubmitted Not Done Memory usage, mostly. Mercurial currently uses an i32, so we're no worse with this limit. The file format will later be changed to VLQ, so the on-disk format is safe for future expansion should we need to store >2GB source files. mbthomas: Memory usage, mostly. Mercurial currently uses an i32, so we're no worse with this limit. The…
				/// Modification time of the file.
				pub mtime: i32,
				}

				impl FileState {
				pub fn new(state: u8, mode: u32, size: i32, mtime: i32) -> FileState {
				FileState {
				state,
				mode,
				jsgfUnsubmitted Not Done Could you use a serde-derived implementation? Or do you not want to take a dependency on serde? jsgf: Could you use a serde-derived implementation? Or do you not want to take a dependency on serde?
				mbthomasAuthorUnsubmitted Not Done I looked at serde, but it seemed like it did way more than I needed, and then didn't really support this use-case (small chunks of binary data, lazily loaded). I don't think it's really needed here, as this isn't an interchange format. mbthomas: I looked at serde, but it seemed like it did way more than I needed, and then didn't really…
				size,
				mtime,
				}
				}
				}

				impl Storable for FileState {
				/// Write a file entry to the store.
				fn write(&self, w: &mut Write) -> Result<()> {
				w.write_u8(self.state)?;
				w.write_u32::<BigEndian>(self.mode)?;
				w.write_i32::<BigEndian>(self.size)?;
				w.write_i32::<BigEndian>(self.mtime)?;
				Ok(())
				}

				/// Read an entry from the store.
				fn read(r: &mut Read) -> Result<FileState> {
				let state = r.read_u8()?;
				let mode = r.read_u32::<BigEndian>()?;
				let size = r.read_i32::<BigEndian>()?;
				let mtime = r.read_i32::<BigEndian>()?;
				Ok(FileState {
				state,
				mode,
				size,
				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;

	pub mod errors;			pub mod errors;
				pub mod filestate;
	pub mod filestore;			pub mod filestore;
	pub mod store;			pub mod store;
				pub mod tree;
	pub mod vecmap;			pub mod vecmap;

	pub use errors::*;			pub use errors::*;

rust/treedirstate/src/tree.rs

This file was added.

				// Copyright Facebook, Inc. 2017
				//! Directory State Tree.

				use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
				use errors::*;
				use std::collections::Bound;
				use std::io::{Cursor, Read, Write};
				jsgfUnsubmitted Not Done This is imported by the prelude. jsgf: This is imported by the prelude.
				use store::{BlockId, Store, StoreView};
				use vecmap::VecMap;

				/// 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>;
				jsgfUnsubmitted Not Done I found this a little confusing. Would it be more accurate to say that implementations of this trait do no storing directly, but they're responsible for serializing/deserializing to/from a byte stream, and its the Store that's doing the actual storing? jsgf: I found this a little confusing. Would it be more accurate to say that implementations of this…
				mbthomasAuthorUnsubmitted Not Done Yes. Really the trait is supposed to represent the constraints on things that can be the Value type in the tree. The name is supposed to suggest "something that can be put in a Store". Would `TreeValue` be a better name? mbthomas: Yes. Really the trait is supposed to represent the constraints on things that can be the Value…
				}

				/// A node entry is an entry in a directory, either a file or another directory.
				#[derive(Debug)]
				enum NodeEntry<T> {
				Directory(Node<T>),
				File(T),
				}

				/// 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 KeyRef<'a> = &'a [u8];

				/// Store the node entries in an ordered map from name to node entry.
				jsgfUnsubmitted Done `List` seems misleading for a map. jsgf: `List` seems misleading for a map.
				type NodeEntryMap<T> = VecMap<Key, NodeEntry<T>>;

				/// The contents of a directory.
				#[derive(Debug)]
				struct Node<T> {
				/// 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.
				id: Option<BlockId>,

				/// 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
				/// store.
				entries: Option<NodeEntryMap<T>>,
				}

				/// The root of the tree. The count of files in the tree is maintained for fast size
				/// determination.
				pub struct Tree<T> {
				root: Node<T>,
				file_count: u32,
				}

				/// Utility enum for recursing through trees.
				jsgfUnsubmitted Done Does this need two independent lifetimes? If one is always the same as or shorter than the other, then you can just use one. jsgf: Does this need two independent lifetimes? If one is always the same as or shorter than the…
				mbthomasAuthorUnsubmitted Done They do need to be separate lifetimes. One is the lifetime of the nodes within the tree, the other is the lifetime of the `KeyRef` we get passed in by various functions, which are usually different objects with competing requirements on their lifetime constraints. If I try to make them the same lifetime, the compiler complains that there are mutually exclusive conditions that can't be satisfied. mbthomas: They do need to be separate lifetimes. One is the lifetime of the nodes within the tree, the…
				enum PathRecurse<'name, 'node, T: 'node> {
				Directory(KeyRef<'name>, KeyRef<'name>, &'node mut Node<T>),
				ExactDirectory(KeyRef<'name>, &'node mut Node<T>),
				MissingDirectory(KeyRef<'name>, KeyRef<'name>),
				File(KeyRef<'name>, &'node mut T),
				MissingFile(KeyRef<'name>),
				ConflictingFile(KeyRef<'name>, KeyRef<'name>, &'node mut T),
				}

				/// Splits a key into the first path element and the remaining path elements (if any).
				fn split_key<'a>(key: KeyRef<'a>) -> (KeyRef<'a>, Option<KeyRef<'a>>) {
				// Skip the last character. Even if it's a '/' we don't want to split on it.
				for (index, value) in key.iter().take(key.len() - 1).enumerate() {
				if *value == b'/' {
				jsgfUnsubmitted Done `&key[..index + 1]` is fine. rustfmt might want to put spaces around `..`. jsgf: `&key[..index + 1]` is fine. rustfmt might want to put spaces around `..`.
				return (&key[..index + 1], Some(&key[index + 1..]));
				}
				}
				jsgfUnsubmitted Done This is equiv aside from handling the last key byte being '/', which would need a second check to return `(key, None)` if the result is `(_, [])`. { let mut bits = key.splitn(2, \|c\| c == b'/'); (bits.next().expect("empty bits!?"), bits.next()) } jsgf:* This is equiv aside from handling the last key byte being '/', which would need a second check…
				mbthomasAuthorUnsubmitted Done It's not quite right as I need to include the `'/'` in the first return value. The reason being that we include the trailing / in directory names so that file/directory clashes are allowed to exist (the dirstate, particularly during merges, can include information about both a file called `foo` and a file called `foo/bar`, and I need to handle this). mbthomas: It's not quite right as I need to include the `'/'` in the first return value. The reason…
				(key, None)
				}

				impl<T: Storable + Clone> NodeEntry<T> {
				/// Read an entry from the store. Returns the name and the entry.
				fn read(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_u32::<BigEndian>()?;
				let mut name = Vec::with_capacity(name_len as usize);
				unsafe {
				// Safe as we've just allocated the buffer and are about to read into it.
				name.set_len(name_len as usize);
				}
				jsgfUnsubmitted Done Looks like a name should have its own distinct type and implement `Storable`. jsgf: Looks like a name should have its own distinct type and implement `Storable`.
				mbthomasAuthorUnsubmitted Done Name's type is always `Vec[u8]`, as we're interested in filesystem paths, and functions like `path_recurse` expect and require this. I could type parameterise it, but it seemed like excessive genericness to me. mbthomas: Name's type is always `Vec[u8]`, as we're interested in filesystem paths, and functions like…
				r.read_exact(name.as_mut_slice())?;
				Ok((name, NodeEntry::File(data)))
				}
				b'd' => {
				// Directory entry.
				jsgfUnsubmitted Not Done This would be cleaner if `BlockId` were a newtype and had its own implementation of `Storable`. jsgf: This would be cleaner if `BlockId` were a newtype and had its own implementation of `Storable`.
				mbthomasAuthorUnsubmitted Not Done `Storable` is meant to encapsulate "can be the right hand side of the map type", rather than just a generic "can be serialized" trait. I'll try to make that clearer in the comments. I've made BlockId a newtype, but arguably what I should be doing here is extending `Read` and `Write` to add new methods `write_block_id`, `read_block_id`. I've not done that, as it seems like lots of work for what is largely an internal implementation detail. Let me know if you think it would be valuable. mbthomas: `Storable` is meant to encapsulate "can be the right hand side of the map type", rather than…
				jsgfUnsubmitted Not Done My main concern is mixing the serialization format details with other logic. If you're hand-coding what the on-disk format looks like in the first place, it would be best to have that in completely separate functions from the other logic that operates on those types/fields. In practice I think using a trait to represent the property of "can be serialized/stored/etc" and hiding those details in the implementations of its methods is a nice way to do that, which composes well if you have well-defined types for each part of your structure which can implement that trait (even if they're just very thin newtype wrappers around more mundane types). Since you already have the `Storable` trait which seems to be the right thing, I think you may as well take advantage of it. jsgf: My main concern is mixing the serialization format details with other logic. If you're hand…
				mbthomasAuthorUnsubmitted Not Done I've refactored this out in D1510. Can you take a look at that and see if it addresses your concerns? mbthomas: I've refactored this out in D1510. Can you take a look at that and see if it addresses your…
				let id = r.read_u64::<BigEndian>()?;
				let name_len = r.read_u32::<BigEndian>()?;
				let mut name = Vec::with_capacity(name_len as usize);
				unsafe {
				// Safe as we've just allocated the buffer and are about to read into it.
				name.set_len(name_len as usize);
				}
				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.
				fn new() -> Node<T> {
				Node {
				id: None,
				entries: Some(NodeEntryMap::new()),
				}
				}

				/// Create a new Node for an existing entry in the store. The entries are not loaded until
				/// the load method is called.
				fn open(id: BlockId) -> Node<T> {
				Node {
				id: Some(id),
				entries: None,
				}
				}

				/// Attempt to load a node from a store.
				fn load(&mut self, store: &StoreView) -> Result<()> {
				if self.entries.is_some() {
				// Already loaded.
				return Ok(());
				}
				let id = self.id.expect("Node must have a valid ID to be loaded");
				let data = store.read(id)?;
				let len = data.len() as u64;
				let mut cursor = Cursor::new(data);
				let count = cursor.read_u32::<BigEndian>()? as usize;
				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(())
				}
				jsgfUnsubmitted Done I'd push this up to the top: let id = self.id.expect("Node must have valid ID..."); then just put the rest of the code at the function level. jsgf: I'd push this up to the top: ``` let id = self.id.expect("Node must have valid ID..."); ```…

				/// Get access to the node entries, ensuring they are loaded first.
				#[inline]
				fn load_entries(&mut self, store: &StoreView) -> Result<&mut NodeEntryMap<T>> {
				self.load(store)?;
				let entries = self.entries
				.as_mut()
				.expect("Entries should have been populated by loading");
				jsgfUnsubmitted Done I'd still `.expect()`. jsgf: I'd still `.expect()`.
				Ok(entries)
				}

				/// Writes all entries for this node to the store. Any child directory entries must have
				/// had IDs assigned to them.
				fn write_entries(&mut self, store: &mut Store) -> Result<()> {
				let mut data = Vec::new();
				let entries = self.entries
				.as_mut()
				.expect("Node should have entries populated before writing out.");
				data.write_u32::<BigEndian>(entries.len() as u32)?;
				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_u64::<BigEndian>(node.id.unwrap().0)?;
				}
				}
				data.write_u32::<BigEndian>(name.len() as u32)?;
				data.write(name)?;
				}
				jsgfUnsubmitted Done Same comment as above - push the non-populated check to the top, then make the rest of the code at function level. jsgf: Same comment as above - push the non-populated check to the top, then make the rest of the code…
				self.id = Some(store.append(&data)?);
				Ok(())
				}

				/// 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.
				fn write_full(&mut self, store: &mut Store, old_store: &StoreView) -> Result<()> {
				// Write out all the child nodes.
				durhamUnsubmitted Not Done If we load a node, then immediately write it, are we rewriting it's id in place? Does that mean that node instance is no longer useful for reading against the old store? durham: If we load a node, then immediately write it, are we rewriting it's id in place? Does that…
				mbthomasAuthorUnsubmitted Not Done Yes, a node is only valid in one store at a time. The `write_full` method has the side-effect of moving all entries in the tree from the old store to the new store. This is how we repack. I shall beef up the comments on `Tree::write_full` to make it clear that it has this effect. mbthomas: Yes, a node is only valid in one store at a time. The `write_full` method has the side-effect…
				for (_name, entry) in self.load_entries(old_store)?.iter_mut() {
				if let &mut NodeEntry::Directory(ref mut node) = entry {
				node.write_full(store, old_store)?;
				}
				}
				// Write out this node.
				self.write_entries(store)
				}

				/// Perform a delta write of the node and its children to the store. Entries that are
				/// already in the store will not be written again.
				fn write_delta(&mut self, store: &mut Store) -> Result<()> {
				if self.id.is_none() {
				// This node has been modified, write out a new copy of any children who have
				// also changed. The entries list must already have been populated when the node
				// was modified, so no need to load it here.
				jsgfUnsubmitted Done I'd flip this around by using `.is_none()`, since that's the interesting case here. jsgf: I'd flip this around by using `.is_none()`, since that's the interesting case here.
				{
				let entries = self.entries
				.as_mut()
				.expect("Node should have entries populated if it was modified.");
				for (_name, entry) in entries.iter_mut() {
				if let &mut NodeEntry::Directory(ref mut node) = entry {
				node.write_delta(store)?;
				}
				}
				}

				// Write out this node.
				jsgfUnsubmitted Not Done (ditto) jsgf: (ditto)
				self.write_entries(store)
				} else {
				// This node and its descendents have not been modified.
				Ok(())
				}
				}

				/// Get the first file in the subtree under this node. If the subtree is not empty, returns a
				/// pair containing the path to the file as a reversed vector of key references for each path
				/// element, and a reference to the file.
				fn get_first<'node>(
				&'node mut self,
				store: &StoreView,
				) -> Result<Option<(Vec<KeyRef<'node>>, &'node T)>> {
				for (name, entry) in self.load_entries(store)?.iter_mut() {
				match entry {
				&mut NodeEntry::Directory(ref mut node) => {
				if let Some((mut next_name, next_file)) = node.get_first(store)? {
				next_name.push(name);
				return Ok(Some((next_name, next_file)));
				}
				}
				&mut NodeEntry::File(ref file) => {
				return Ok(Some((vec![name], file)));
				}
				}
				}
				Ok(None)
				}

				/// Get the next file after a particular file in the tree. Returns a pair containing the path
				/// to the file as a reversed vector of key references for each path element, and a reference
				/// to the file, or None if there are no more files.
				fn get_next<'node>(
				&'node mut self,
				store: &StoreView,
				name: KeyRef,
				) -> Result<Option<(Vec<KeyRef<'node>>, &'node T)>> {
				// Find the entry within this list, and what the remainder of the path is.
				let (elem, mut path) = split_key(name);

				// Get the next entry after the current one. We need to look inside directories as we go.
				// The subpath we obtained from split_key is only relevant if we are looking inside the
				// directory the path refers to.
				for (entry_name, entry) in self.load_entries(store)?
				.range_mut((Bound::Included(elem), Bound::Unbounded))
				{
				match entry {
				&mut NodeEntry::Directory(ref mut node) => {
				// The entry is a directory, check inside it.
				if elem != entry_name.as_slice() {
				// This directory is not the one we were initially looking inside. We
				// have moved on past that directory, so the rest of the path is no
				// longer relevant.
				path = None
				}
				let next = if let Some(path) = path {
				// Find the next file after the given subpath.
				node.get_next(store, path)?
				} else {
				// Find the first file in this subtree.
				node.get_first(store)?
				};
				if let Some((mut next_name, next_file)) = next {
				next_name.push(entry_name);
				return Ok(Some((next_name, next_file)));
				}
				}
				&mut NodeEntry::File(ref file) => {
				// This entry is a file. Skip over it if it is the original file.
				if elem != entry_name.as_slice() {
				return Ok(Some((vec![entry_name], file)));
				}
				}
				}
				}
				Ok(None)
				}

				/// Utility function for recursing through subdirectories. Returns the appropriate
				/// PathRecurse variant for the current position in the file tree given by name.
				fn path_recurse<'name, 'node>(
				&'node mut self,
				store: &StoreView,
				name: KeyRef<'name>,
				) -> Result<PathRecurse<'name, 'node, T>> {
				let (elem, path) = split_key(name);
				let res = if let Some(path) = path {
				// The name is for a subdirectory.
				match self.load_entries(store)?.get_mut(elem) {
				jsgfUnsubmitted Done Rather than duplicating the `Ok(...)` everywhere, which I think obscures the real logic, it would be better to have something like: let res = if let Some(path) = path { ... }; Ok(res) jsgf: Rather than duplicating the `Ok(...)` everywhere, which I think obscures the real logic, it…
				Some(&mut NodeEntry::Directory(ref mut node)) => {
				PathRecurse::Directory(elem, path, node)
				}
				Some(&mut NodeEntry::File(ref mut file)) => {
				PathRecurse::ConflictingFile(elem, path, file)
				}
				None => PathRecurse::MissingDirectory(elem, path),
				}
				} else {
				// The name is for a file or directory in this directory.
				match self.load_entries(store)?.get_mut(elem) {
				Some(&mut NodeEntry::Directory(ref mut node)) => {
				PathRecurse::ExactDirectory(elem, node)
				}
				Some(&mut NodeEntry::File(ref mut file)) => PathRecurse::File(elem, file),
				None => PathRecurse::MissingFile(elem),
				}
				};
				Ok(res)
				}

				/// Get a file's state.
				fn get<'node>(&'node mut self, store: &StoreView, name: KeyRef) -> Result<Option<&'node T>> {
				match self.path_recurse(store, name)? {
				PathRecurse::Directory(_dir, path, node) => node.get(store, path),
				PathRecurse::ExactDirectory(_dir, _node) => Ok(None),
				PathRecurse::MissingDirectory(_dir, _path) => Ok(None),
				PathRecurse::File(_name, file) => Ok(Some(file)),
				PathRecurse::MissingFile(_name) => Ok(None),
				PathRecurse::ConflictingFile(_name, _path, _file) => Ok(None),
				}
				}

				/// Returns true if the given path is a directory.
				fn has_dir(&mut self, store: &StoreView, name: KeyRef) -> Result<bool> {
				match self.path_recurse(store, name)? {
				PathRecurse::Directory(_dir, path, node) => node.has_dir(store, path),
				PathRecurse::ExactDirectory(_dir, _node) => Ok(true),
				PathRecurse::MissingDirectory(_dir, _path) => Ok(false),
				PathRecurse::File(_name, _file) => Ok(false),
				PathRecurse::MissingFile(_name) => Ok(false),
				PathRecurse::ConflictingFile(_name, _path, _file) => Ok(false),
				}
				}

				/// Add a file to the node. The name may contain a path, in which case sufficient
				/// subdirectories are updated to add or update the file.
				fn add(&mut self, store: &StoreView, name: KeyRef, info: &T) -> Result<bool> {
				let (new_entry, file_added) = match self.path_recurse(store, name)? {
				PathRecurse::Directory(_dir, path, node) => {
				// The file is in a subdirectory. Add it to the subdirectory.
				let file_added = node.add(store, path, info)?;
				(None, file_added)
				}
				PathRecurse::ExactDirectory(_dir, _node) => {
				panic!("Adding file which matches the name of a directory.");
				}
				PathRecurse::MissingDirectory(dir, path) => {
				// The file is in a new subdirectory. Create the directory and add the file.
				let mut node = Node::new();
				let file_added = node.add(store, path, info)?;
				(Some((dir.to_vec(), NodeEntry::Directory(node))), file_added)
				}
				PathRecurse::File(_name, file) => {
				// The file is in this directory. Update it.
				file.clone_from(info);
				(None, false)
				}
				PathRecurse::MissingFile(ref name) => {
				// The file should be in this directory. Add it.
				(Some((name.to_vec(), NodeEntry::File(info.clone()))), true)
				}
				PathRecurse::ConflictingFile(_name, _path, _file) => {
				panic!("Adding file with path prefix that matches the name of a file.")
				}
				};
				if let Some((new_key, new_entry)) = new_entry {
				self.load_entries(store)?.insert(new_key, new_entry);
				}
				self.id = None;
				Ok(file_added)
				}

				/// Remove a file from the node. The name may contain a path, in which case sufficient
				/// subdirectories are updated to remove the file.
				///
				/// Returns a pair of booleans (file_removed, now_empty) indicating whether the file
				/// was removed, and whether the diectory is now empty.
				fn remove(&mut self, store: &StoreView, name: KeyRef) -> Result<(bool, bool)> {
				let (file_removed, remove_entry) = match self.path_recurse(store, name)? {
				PathRecurse::Directory(dir, path, node) => {
				let (file_removed, now_empty) = node.remove(store, path)?;
				(file_removed, if now_empty { Some(dir) } else { None })
				}
				PathRecurse::ExactDirectory(_dir, _node) => (false, None),
				PathRecurse::MissingDirectory(_dir, _path) => (false, None),
				PathRecurse::File(name, _file) => (true, Some(name)),
				PathRecurse::MissingFile(_name) => (false, None),
				PathRecurse::ConflictingFile(_name, _path, _file) => (false, None),
				};
				if let Some(entry) = remove_entry {
				self.load_entries(store)?.remove(entry);
				self.id = None;
				}
				if file_removed {
				self.id = None;
				}
				Ok((file_removed, self.load_entries(store)?.is_empty()))
				}
				}

				impl<T: Storable + Clone> Tree<T> {
				/// Create a new empty tree.
				pub fn new() -> Tree<T> {
				Tree {
				root: Node::new(),
				file_count: 0,
				}
				}

				/// Create a tree that references an existing root node.
				pub fn open(root_id: BlockId, file_count: u32) -> Tree<T> {
				Tree {
				root: Node::open(root_id),
				file_count,
				}
				}

				/// Clear all entries in the tree.
				pub fn clear(&mut self) {
				self.root = Node::new();
				self.file_count = 0;
				}

				pub fn root_id(&self) -> Option<BlockId> {
				self.root.id
				}

				pub fn file_count(&self) -> u32 {
				self.file_count
				}

				pub fn write_full(&mut self, store: &mut Store, old_store: &StoreView) -> Result<()> {
				self.root.write_full(store, old_store)?;
				Ok(())
				}

				pub fn write_delta(&mut self, store: &mut Store) -> Result<()> {
				self.root.write_delta(store)?;
				Ok(())
				}

				pub fn get<'a>(&'a mut self, store: &StoreView, name: KeyRef) -> Result<Option<&'a T>> {
				Ok(self.root.get(store, name)?)
				}

				pub fn get_first<'a>(&'a mut self, store: &StoreView) -> Result<Option<(Key, &'a T)>> {
				Ok(self.root.get_first(store)?.map(\|(mut path, file)\| {
				path.reverse();
				(path.concat(), file)
				}))
				}

				pub fn get_next<'a>(
				&'a mut self,
				store: &StoreView,
				name: KeyRef,
				) -> Result<Option<(Key, &'a T)>> {
				Ok(self.root.get_next(store, name)?.map(\|(mut path, file)\| {
				path.reverse();
				(path.concat(), file)
				}))
				}

				pub fn has_dir(&mut self, store: &StoreView, name: KeyRef) -> Result<bool> {
				Ok(self.root.has_dir(store, name)?)
				}

				pub fn add(&mut self, store: &StoreView, name: KeyRef, file: &T) -> Result<()> {
				if self.root.add(store, name, file)? {
				self.file_count += 1;
				}
				Ok(())
				}

				pub fn remove(&mut self, store: &StoreView, name: KeyRef) -> Result<bool> {
				let removed = self.root.remove(store, name)?.0;
				if removed {
				assert!(self.file_count > 0);
				self.file_count -= 1;
				}
				Ok(removed)
				}
				}

				#[cfg(test)]
				mod tests {

				use store::NullStore;
				use store::tests::MapStore;
				use tree::Tree;
				use filestate::FileState;

				// Test files in order. Note lexicographic ordering of file9 and file10.
				static TEST_FILES: [(&[u8], u32, i32, i32); 16] = [
				(b"dirA/subdira/file1", 0o644, 1, 10001),
				(b"dirA/subdira/file2", 0o644, 2, 10002),
				(b"dirA/subdirb/file3", 0o644, 3, 10003),
				(b"dirB/subdira/file4", 0o644, 4, 10004),
				(b"dirB/subdira/subsubdirx/file5", 0o644, 5, 10005),
				(b"dirB/subdira/subsubdiry/file6", 0o644, 6, 10006),
				(b"dirB/subdira/subsubdirz/file7", 0o755, 7, 10007),
				(b"dirB/subdira/subsubdirz/file8", 0o755, 8, 10008),
				(b"dirB/subdirb/file10", 0o644, 10, 10010),
				(b"dirB/subdirb/file9", 0o644, 9, 10009),
				(b"dirC/file11", 0o644, 11, 10011),
				(b"dirC/file12", 0o644, 12, 10012),
				(b"dirC/file13", 0o644, 13, 10013),
				(b"dirC/file14", 0o644, 14, 10014),
				(b"dirC/file15", 0o644, 15, 10015),
				(b"file16", 0o644, 16, 10016),
				];

				fn populate(t: &mut Tree<FileState>, s: &MapStore) {
				for &(name, mode, size, mtime) in TEST_FILES.iter() {
				t.add(s, name, &FileState::new(b'n', mode, size, mtime))
				.expect("can add file");
				}
				}

				#[test]
				fn count_get_and_remove() {
				let ms = MapStore::new();
				let mut t = Tree::new();
				assert_eq!(t.file_count(), 0);
				assert_eq!(
				t.get(&ms, b"dirB/subdira/subsubdirz/file7")
				.expect("can get"),
				None
				);
				populate(&mut t, &ms);
				assert_eq!(t.file_count(), 16);
				assert_eq!(
				t.get(&ms, b"dirB/subdira/subsubdirz/file7")
				.expect("can get"),
				Some(&FileState::new(b'n', 0o755, 7, 10007))
				);
				t.remove(&ms, b"dirB/subdirb/file9").expect("can remove");
				assert_eq!(t.file_count(), 15);
				t.remove(&ms, b"dirB/subdirb/file10").expect("can remove");
				assert_eq!(t.file_count(), 14);
				assert_eq!(
				t.get(&ms, b"dirB/subdira/subsubdirz/file7")
				.expect("can get"),
				Some(&FileState::new(b'n', 0o755, 7, 10007))
				);
				assert_eq!(t.get(&ms, b"dirB/subdirb/file9").expect("can get"), None);
				}

				#[test]
				fn iterate() {
				let ms = MapStore::new();
				let mut t = Tree::new();
				assert_eq!(t.get_first(&ms).expect("can get first"), None);
				populate(&mut t, &ms);
				let mut expect_iter = TEST_FILES.iter();
				let expected = expect_iter.next().unwrap();
				let mut filename = expected.0.to_vec();
				assert_eq!(
				t.get_first(&ms).expect("can get first"),
				Some((
				filename.clone(),
				&FileState::new(b'n', expected.1, expected.2, expected.3)
				))
				);
				while let Some(expected) = expect_iter.next() {
				let actual = t.get_next(&ms, &filename).expect("can get next");
				filename = expected.0.to_vec();
				assert_eq!(
				actual,
				Some((
				filename.clone(),
				&FileState::new(b'n', expected.1, expected.2, expected.3)
				))
				);
				}
				assert_eq!(t.get_next(&ms, &filename).expect("can get next"), None);
				}

				#[test]
				fn has_dir() {
				let ms = MapStore::new();
				let mut t = Tree::new();
				assert_eq!(
				t.has_dir(&ms, b"anything/").expect("can check has_dir"),
				false
				);
				populate(&mut t, &ms);
				assert_eq!(
				t.has_dir(&ms, b"something else/")
				.expect("can check has_dir"),
				false
				);
				assert_eq!(t.has_dir(&ms, b"dirB/").expect("can check has_dir"), true);
				assert_eq!(
				t.has_dir(&ms, b"dirB/subdira/").expect("can check has_dir"),
				true
				);
				assert_eq!(
				t.has_dir(&ms, b"dirB/subdira/subsubdirz/")
				.expect("can check has_dir"),
				true
				);
				assert_eq!(
				t.has_dir(&ms, b"dirB/subdira/subsubdirz/file7")
				.expect("can check has_dir"),
				false
				);
				assert_eq!(
				t.has_dir(&ms, b"dirB/subdira/subsubdirz/file7/")
				.expect("can check has_dir"),
				false
				);
				}

				#[test]
				fn write_empty() {
				let ns = NullStore::new();
				let mut ms = MapStore::new();
				let mut t = Tree::<FileState>::new();
				t.write_full(&mut ms, &ns).expect("can write full");
				t.write_delta(&mut ms).expect("can write delta");
				let mut ms2 = MapStore::new();
				t.write_full(&mut ms2, &ms).expect("can write full");
				let t_root = t.root_id().unwrap();
				let t_count = t.file_count();
				let mut t2 = Tree::<FileState>::open(t_root, t_count);
				assert_eq!(t2.get_first(&ms2).expect("can get first"), None);
				}

				#[test]
				fn write() {
				let ns = NullStore::new();
				let mut ms = MapStore::new();
				let mut t = Tree::new();
				populate(&mut t, &ms);
				t.write_full(&mut ms, &ns).expect("can write full");
				t.write_delta(&mut ms).expect("can write delta");
				let mut ms2 = MapStore::new();
				t.write_full(&mut ms2, &ms).expect("can write full");
				let t_root = t.root_id().unwrap();
				let t_count = t.file_count();
				let mut t2 = Tree::open(t_root, t_count);
				assert_eq!(
				t2.get(&ms2, b"dirB/subdira/subsubdirz/file7")
				.expect("can get"),
				Some(&FileState::new(b'n', 0o755, 7, 10007))
				);
				}

				}

This is an archive of the discontinued Mercurial Phabricator instance.

treedirstate: add Tree
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 3928

rust/treedirstate/src/errors.rs

rust/treedirstate/src/filestate.rs

rust/treedirstate/src/lib.rs

rust/treedirstate/src/tree.rs

This is an archive of the discontinued Mercurial Phabricator instance.

treedirstate: add TreeClosedPublic

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 3928

rust/treedirstate/src/errors.rs

rust/treedirstate/src/filestate.rs

rust/treedirstate/src/lib.rs

rust/treedirstate/src/tree.rs

treedirstate: add Tree
ClosedPublic

Revision Contents
Changeset List