diff --git a/rust/treedirstate/Cargo.lock b/rust/treedirstate/Cargo.lock --- a/rust/treedirstate/Cargo.lock +++ b/rust/treedirstate/Cargo.lock @@ -1,4 +1,175 @@ +[[package]] +name = "aho-corasick" +version = "0.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "bitflags" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "either" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "env_logger" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", + "regex 0.1.80 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "fuchsia-zircon" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "fuchsia-zircon-sys 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "fuchsia-zircon-sys" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "itertools" +version = "0.7.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "either 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "kernel32-sys" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi-build 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "libc" +version = "0.2.33" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "log" +version = "0.3.8" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "memchr" +version = "0.1.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "libc 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "quickcheck" +version = "0.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "env_logger 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)", + "log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", + "rand 0.3.18 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand" +version = "0.3.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "fuchsia-zircon 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "regex" +version = "0.1.80" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "aho-corasick 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)", + "memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)", + "regex-syntax 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)", + "thread_local 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)", + "utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "regex-syntax" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" + [[package]] name = "rusttreedirstate" version = "0.1.0" +dependencies = [ + "itertools 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)", + "quickcheck 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)", +] +[[package]] +name = "thread-id" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "thread_local" +version = "0.2.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "thread-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "utf8-ranges" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi" +version = "0.2.8" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi-build" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[metadata] +"checksum aho-corasick 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ca972c2ea5f742bfce5687b9aef75506a764f61d37f8f649047846a9686ddb66" +"checksum bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "aad18937a628ec6abcd26d1489012cc0e18c21798210f491af69ded9b881106d" +"checksum either 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "740178ddf48b1a9e878e6d6509a1442a2d42fd2928aae8e7a6f8a36fb01981b3" +"checksum env_logger 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "15abd780e45b3ea4f76b4e9a26ff4843258dd8a3eed2775a0e7368c2e7936c2f" +"checksum fuchsia-zircon 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f6c0581a4e363262e52b87f59ee2afe3415361c6ec35e665924eb08afe8ff159" +"checksum fuchsia-zircon-sys 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "43f3795b4bae048dc6123a6b972cadde2e676f9ded08aef6bb77f5f157684a82" +"checksum itertools 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "2c52051d3fd3b505796a0ee90f2e5ec43213808585e8adc4d0182492cf62751a" +"checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d" +"checksum libc 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)" = "5ba3df4dcb460b9dfbd070d41c94c19209620c191b0340b929ce748a2bcd42d2" +"checksum log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "880f77541efa6e5cc74e76910c9884d9859683118839d6a1dc3b11e63512565b" +"checksum memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "d8b629fb514376c675b98c1421e80b151d3817ac42d7c667717d282761418d20" +"checksum quickcheck 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "02c2411d418cea2364325b18a205664f9ef8252e06b2e911db97c0b0d98b1406" +"checksum rand 0.3.18 (registry+https://github.com/rust-lang/crates.io-index)" = "6475140dfd8655aeb72e1fd4b7a1cc1c202be65d71669476e392fe62532b9edd" +"checksum regex 0.1.80 (registry+https://github.com/rust-lang/crates.io-index)" = "4fd4ace6a8cf7860714a2c2280d6c1f7e6a413486c13298bbc86fd3da019402f" +"checksum regex-syntax 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "f9ec002c35e86791825ed294b50008eea9ddfc8def4420124fbc6b08db834957" +"checksum thread-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9539db560102d1cef46b8b78ce737ff0bb64e7e18d35b2a5688f7d097d0ff03" +"checksum thread_local 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "8576dbbfcaef9641452d5cf0df9b0e7eeab7694956dd33bb61515fb8f18cfdd5" +"checksum utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a1ca13c08c41c9c3e04224ed9ff80461d97e121589ff27c753a16cb10830ae0f" +"checksum winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "167dc9d6949a9b857f3451275e911c3f44255842c1f7a76f33c55103a909087a" +"checksum winapi-build 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "2d315eee3b34aca4797b2da6b13ed88266e6d612562a0c46390af8299fc699bc" diff --git a/rust/treedirstate/Cargo.toml b/rust/treedirstate/Cargo.toml --- a/rust/treedirstate/Cargo.toml +++ b/rust/treedirstate/Cargo.toml @@ -9,3 +9,7 @@ [lib] name = "rusttreedirstate" crate-type = ["cdylib"] + +[dev-dependencies] +itertools = "0.7.2" +quickcheck = "*" diff --git a/rust/treedirstate/src/lib.rs b/rust/treedirstate/src/lib.rs --- a/rust/treedirstate/src/lib.rs +++ b/rust/treedirstate/src/lib.rs @@ -11,3 +11,12 @@ //! //! The directory state also stores files that are in the working copy parent manifest but have //! been marked as removed. + +#[cfg(test)] +extern crate itertools; + +#[cfg(test)] +#[macro_use] +extern crate quickcheck; + +pub mod vecmap; diff --git a/rust/treedirstate/src/vecmap.rs b/rust/treedirstate/src/vecmap.rs new file mode 100644 --- /dev/null +++ b/rust/treedirstate/src/vecmap.rs @@ -0,0 +1,340 @@ +// Copyright Facebook, Inc. 2017 +//! Ordered map implementation using a sorted vector + +use std::mem; +use std::borrow::Borrow; +use std::slice::{Iter as VecIter, IterMut as VecIterMut}; +use std::collections::Bound; +use std::collections::Bound::*; + +#[derive(Debug)] +pub struct VecMap { + vec: Vec<(K, V)>, +} + +pub struct Iter<'a, K: 'a, V: 'a>(VecIter<'a, (K, V)>); + +pub struct IterMut<'a, K: 'a, V: 'a>(VecIterMut<'a, (K, V)>); + +impl VecMap +where + K: Ord, +{ + /// Creates a new, empty VecMap. + pub fn new() -> VecMap { + VecMap { vec: Vec::new() } + } + + /// Creates a new, empty VecMap, with capacity for `capacity` entries. + pub fn with_capacity(capacity: usize) -> VecMap { + VecMap { + vec: Vec::with_capacity(capacity), + } + } + + pub fn is_empty(&self) -> bool { + self.vec.is_empty() + } + + pub fn len(&self) -> usize { + self.vec.len() + } + + /// Utility function to binary search for an index using the key. + fn find_index(&self, q: &Q) -> Result + where + K: Borrow, + Q: Ord, + { + self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) + } + + /// Inserts a key-value pair into the map. If the key already had a value present in the + /// map, that value is replaced and returned. Otherwise, `None` is returned. + pub fn insert(&mut self, k: K, v: V) -> Option { + let mut v = v; + match self.find_index(&k) { + Ok(index) => { + mem::swap(&mut self.vec[index].1, &mut v); + Some(v) + } + Err(index) => { + self.vec.insert(index, (k, v)); + None + } + } + } + + /// Inserts a key-value pair into the map. Fast-path for when the key is not already + /// present and is at the end of the map. + pub fn insert_hint_end(&mut self, k: K, v: V) -> Option { + let len = self.vec.len(); + if len == 0 || self.vec[len - 1].0 < k { + self.vec.push((k, v)); + None + } else { + self.insert(k, v) + } + } + + /// Removes a key-value pair from the map, returning the value if the key was previously in + /// the map. + pub fn remove(&mut self, q: &Q) -> Option + where + K: Borrow, + Q: Ord, + { + match self.find_index(q) { + Ok(index) => { + let (_k, v) = self.vec.remove(index); + Some(v) + } + Err(_index) => None, + } + } + + /// Returns a reference to the value corresponding to the key. + pub fn get<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<&'a V> + where + K: Borrow, + Q: Ord, + { + match self.find_index(q) { + Ok(index) => Some(&self.vec[index].1), + Err(_index) => None, + } + } + + /// Returns a mutable reference to the value corresponding to the key. + pub fn get_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<&'a mut V> + where + K: Borrow, + Q: Ord, + { + match self.find_index(q) { + Ok(index) => Some(&mut self.vec[index].1), + Err(_index) => None, + } + } + + // Returns an iterator over the pairs of entries in the map. + pub fn iter(&self) -> Iter { + Iter(self.vec.iter()) + } + + /// Returns a mutable iterator over the pairs of entries in the map. + pub fn iter_mut(&mut self) -> IterMut { + IterMut(self.vec.iter_mut()) + } + + /// Utility function for implementing `range` and `range_mut`. Convert a range boundary for + /// the start of a range into a slice index suitable for use in a range expression. + fn range_index_start(&self, b: Bound<&Q>) -> usize + where + K: Borrow, + Q: Ord, + { + match b { + Unbounded => 0, + Included(q) => match self.find_index(q) { + Ok(index) => index, + Err(index) => index, + }, + Excluded(q) => match self.find_index(q) { + Ok(index) => index + 1, + Err(index) => index, + }, + } + } + + /// Utility function for implementing `range` and `range_mut`. Convert a range boundary for + /// the end of a range into a slice index suitable for use in a range expression. + fn range_index_end(&self, b: Bound<&Q>) -> usize + where + K: Borrow, + Q: Ord, + { + match b { + Unbounded => self.vec.len(), + Included(q) => match self.find_index(q) { + Ok(index) => index + 1, + Err(index) => index, + }, + Excluded(q) => match self.find_index(q) { + Ok(index) => index, + Err(index) => index, + }, + } + } + + /// Returns an iterator over the given range of keys. + pub fn range(&self, range: (Bound<&Q>, Bound<&Q>)) -> Iter + where + K: Borrow, + Q: Ord + ?Sized, + { + let start = self.range_index_start(range.0); + let end = self.range_index_end(range.1); + Iter(self.vec[start..end].iter()) + } + + /// Returns a mutuable iterator over the given range of keys. + pub fn range_mut(&mut self, range: (Bound<&Q>, Bound<&Q>)) -> IterMut + where + K: Borrow, + Q: Ord + ?Sized, + { + let start = self.range_index_start(range.0); + let end = self.range_index_end(range.1); + IterMut(self.vec[start..end].iter_mut()) + } +} + +// Wrap `Iter` and `IterMut` for `VecMap` types. These implementations adapt the `next` methods, +// converting their yielded types from `Option<&(K, V)>` to `Option<(&K, &V)>`, and from +// `Option<&mut (K, V)>` to `Option<(&K, &mut V)>`. This allows `VecMap` iterators to be used +// in the same way as other map iterators to iterate over key-value pairs, and prevents callers +// from using the mutable iterator to mutate keys. + +impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> { + type Item = (&'a K, &'a V); + + #[inline] + fn next(&mut self) -> Option { + self.0.next().map(|&(ref k, ref v)| (k, v)) + } +} + +impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + #[inline] + fn next(&mut self) -> Option { + self.0.next().map(|&mut (ref k, ref mut v)| (k, v)) + } +} + +#[cfg(test)] +mod tests { + + use vecmap::{Iter, VecMap}; + use itertools; + use std::collections::Bound::*; + use std::collections::BTreeMap; + + #[test] + fn insert_get_remove() { + let mut vm = VecMap::new(); + assert_eq!(vm.insert("test1", "value1".to_string()), None); + assert_eq!(vm.insert("test2", "value2".to_string()), None); + assert_eq!(vm.insert_hint_end("test4", "value4".to_string()), None); + assert_eq!(vm.insert_hint_end("test3", "value3".to_string()), None); + assert_eq!( + vm.insert("test1", "value1b".to_string()), + Some("value1".to_string()) + ); + assert_eq!(vm.get(&"test1"), Some(&"value1b".to_string())); + if let Some(v) = vm.get_mut(&"test1") { + *v = "value1c".to_string(); + } + assert_eq!(vm.get(&"test1"), Some(&"value1c".to_string())); + assert_eq!(vm.remove("test2"), Some("value2".to_string())); + assert_eq!(vm.remove("test2"), None); + assert_eq!(vm.get(&"test2"), None); + assert_eq!(vm.get_mut(&"never"), None); + } + + #[test] + fn iter() { + let mut vm = VecMap::with_capacity(4); + assert!(vm.is_empty()); + vm.insert(2, "value2"); + vm.insert(1, "value1"); + vm.insert(4, "value4"); + vm.insert(3, "value3"); + assert!(!vm.is_empty()); + assert_eq!(vm.len(), 4); + { + let mut im = vm.iter_mut(); + im.next(); + let e2 = im.next().unwrap(); + *e2.1 = "value2 - modified"; + } + let mut i = vm.iter(); + assert_eq!(i.next(), Some((&1, &"value1"))); + assert_eq!(i.next(), Some((&2, &"value2 - modified"))); + assert_eq!(i.next(), Some((&3, &"value3"))); + assert_eq!(i.next(), Some((&4, &"value4"))); + assert_eq!(i.next(), None); + } + + #[test] + fn range() { + let mut vm: VecMap = VecMap::new(); + for n in 0..20 { + vm.insert(n * 2, n * 4); + } + + fn check_iter(mut x: Iter, start: i32, end: i32) { + let mut i = start; + while i < end { + assert_eq!(x.next(), Some((&i, &(i * 2)))); + i += 2; + } + assert_eq!(x.next(), None); + } + + check_iter(vm.range((Unbounded, Unbounded)), 0, 39); + check_iter(vm.range((Unbounded, Included(&2))), 0, 3); + check_iter(vm.range((Unbounded, Excluded(&2))), 0, 1); + check_iter(vm.range((Unbounded, Excluded(&7))), 0, 7); + check_iter(vm.range((Unbounded, Included(&13))), 0, 13); + check_iter(vm.range((Included(&4), Included(&13))), 4, 13); + check_iter(vm.range((Included(&5), Included(&14))), 6, 15); + check_iter(vm.range((Excluded(&5), Included(&20))), 6, 21); + check_iter(vm.range((Excluded(&6), Included(&60))), 8, 39); + check_iter(vm.range((Excluded(&-30), Unbounded)), 0, 39); + check_iter(vm.range((Included(&-1), Unbounded)), 0, 39); + + assert_eq!(vm.get(&16), Some(&32)); + { + let mut im = vm.range_mut((Included(&16), Excluded(&18))); + *im.next().unwrap().1 *= 2; + assert_eq!(im.next(), None); + } + assert_eq!(vm.get(&16), Some(&64)); + } + + fn vecmap_from_btreemap(b: &BTreeMap) -> VecMap { + let mut vm = VecMap::new(); + for (k, v) in b.iter() { + vm.insert(k.clone(), v.clone()); + } + vm + } + + quickcheck! { + fn like_btreemap_is_empty (b: BTreeMap) -> bool { + let vm = vecmap_from_btreemap(&b); + vm.is_empty() == b.is_empty() + } + + fn like_btreemap_len (b: BTreeMap) -> bool { + let vm = vecmap_from_btreemap(&b); + vm.len() == b.len() + } + + fn like_btreemap_iter (b: BTreeMap) -> bool { + let vm = vecmap_from_btreemap(&b); + itertools::equal(vm.iter(), b.iter()) + } + + fn like_btreemap_range (b: BTreeMap, key1: u32, key2: u32) -> bool { + // range requires start key is not after end key. + let (start, end) = if key1 <= key2 { (key1, key2) } else { (key2, key1) }; + let vm = vecmap_from_btreemap(&b); + let range = (Included(&start), Excluded(&end)); + itertools::equal(vm.range(range), b.range(range)) + } + } +}