Bug 1493435 - Upgrade to uluru 0.3. r=nox,emilio
authorMatt Brubeck <mbrubeck@limpet.net>
Sat, 22 Sep 2018 17:24:47 -0700
changeset 496275 a5d7a71300f8000625634d67ce5cd242e5e8e4d9
parent 496274 664ee5906d32a4cec74eeb06ec971dfc88116ec7
child 496276 5e43b977f631d6889a63deb281cec2445b7ac67e
push id1864
push userffxbld-merge
push dateMon, 03 Dec 2018 15:51:40 +0000
treeherdermozilla-release@f040763d99ad [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnox, emilio
bugs1493435, 21789
milestone64.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1493435 - Upgrade to uluru 0.3. r=nox,emilio This cherry-picks servo/servo#21789.
Cargo.lock
servo/components/style/Cargo.toml
third_party/rust/uluru/.cargo-checksum.json
third_party/rust/uluru/.cargo_vcs_info.json
third_party/rust/uluru/Cargo.toml
third_party/rust/uluru/README.md
third_party/rust/uluru/lib.rs
third_party/rust/uluru/tests.rs
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2132,17 +2132,17 @@ dependencies = [
  "servo_arc 0.1.1",
  "smallbitvec 2.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "style_derive 0.0.1",
  "style_traits 0.0.1",
  "thin-slice 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "time 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
  "toml 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)",
- "uluru 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "uluru 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "unicode-bidi 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "unicode-segmentation 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "void 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "walkdir 2.1.4 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "style_derive"
@@ -2497,17 +2497,17 @@ dependencies = [
 
 [[package]]
 name = "ucd-util"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "uluru"
-version = "0.2.0"
+version = "0.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "arrayvec 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "unicode-bidi"
 version = "0.3.4"
@@ -3048,17 +3048,17 @@ dependencies = [
 "checksum tokio-tcp 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "5b4c329b47f071eb8a746040465fa751bd95e4716e98daef6a9b4e434c17d565"
 "checksum tokio-threadpool 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "24ab84f574027b0e875378f31575cf175360891919e93a3490f07e76e00e4efb"
 "checksum tokio-timer 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)" = "1c76b4e97a4f61030edff8bd272364e4f731b9f54c7307eb4eb733c3926eb96a"
 "checksum tokio-udp 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "43eb534af6e8f37d43ab1b612660df14755c42bd003c5f8d2475ee78cc4600c0"
 "checksum tokio-uds 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "65ae5d255ce739e8537221ed2942e0445f4b3b813daebac1c0050ddaaa3587f9"
 "checksum toml 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)" = "a7540f4ffc193e0d3c94121edb19b055670d369f77d5804db11ae053a45b6e7e"
 "checksum try-lock 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "e604eb7b43c06650e854be16a2a03155743d3752dd1c943f6829e26b7a36e382"
 "checksum ucd-util 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "fd2be2d6639d0f8fe6cdda291ad456e23629558d466e2789d2c3e9892bda285d"
-"checksum uluru 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "519130f0ea964ba540a9d8af1373738c2226f1d465eda07e61db29feb5479db9"
+"checksum uluru 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d2606e9192f308ddc4f0b3c5d1bf3400e28a70fff956e9d9f46d23b094746d9f"
 "checksum unicode-bidi 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)" = "49f2bd0c6468a8230e1db229cff8029217cf623c767ea5d60bfbd42729ea54d5"
 "checksum unicode-normalization 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "51ccda9ef9efa3f7ef5d91e8f9b83bbe6955f9bf86aec89d5cce2c874625920f"
 "checksum unicode-segmentation 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "aa6024fc12ddfd1c6dbc14a80fa2324d4568849869b779f6bd37e5e4c03344d1"
 "checksum unicode-width 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "bf3a113775714a22dcb774d8ea3655c53a32debae63a063acc00a91cc586245f"
 "checksum unicode-xid 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "fc72304796d0818e357ead4e000d19c9c174ab23dc11093ac919054d20a6a7fc"
 "checksum unreachable 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "382810877fe448991dfc7f0dd6e3ae5d58088fd0ea5e35189655f84e6814fa56"
 "checksum url 1.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f808aadd8cfec6ef90e4a14eb46f24511824d1ac596b9682703c87056c8678b7"
 "checksum utf8-ranges 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "662fab6525a98beff2921d7f61a39e7d59e0b425ebc7d0d9e66d316e55124122"
--- a/servo/components/style/Cargo.toml
+++ b/servo/components/style/Cargo.toml
@@ -65,17 +65,17 @@ servo_config = {path = "../config", opti
 smallbitvec = "2.1.1"
 smallvec = "0.6"
 string_cache = { version = "0.7", optional = true }
 style_derive = {path = "../style_derive"}
 style_traits = {path = "../style_traits"}
 servo_url = {path = "../url", optional = true}
 thin-slice = "0.1.0"
 time = "0.1"
-uluru = "0.2"
+uluru = "0.3"
 unicode-bidi = "0.3"
 unicode-segmentation = "1.0"
 void = "1.0.2"
 
 [build-dependencies]
 lazy_static = "1"
 log = "0.4"
 bindgen = { version = "0.39", optional = true, default-features = false }
--- a/third_party/rust/uluru/.cargo-checksum.json
+++ b/third_party/rust/uluru/.cargo-checksum.json
@@ -1,1 +1,1 @@
-{"files":{"Cargo.toml":"7c10953d660c87fe16c4bf1936007deadebe6832ff81adadb962acf1a87c5432","LICENSE":"3db78572e8657cca9e9446ce56a057b8a981eb41af318c49a5fe08e7a10fa52a","README.md":"de12b77db6f2e0a9e8c3d0c16dc0e23e3d97d7b93010d522552339f619a5e4c1","lib.rs":"125207560eb1b29d06869e7c24da2daba6c19a5c51d33c2377e710de4fb553b0","tests.rs":"3bc80e05bdc7b95fc4443f0b2face27c9ce36a16ee697183328d441c82c7a951"},"package":"519130f0ea964ba540a9d8af1373738c2226f1d465eda07e61db29feb5479db9"}
\ No newline at end of file
+{"files":{".cargo_vcs_info.json":"bd4e94a467fbc1c26612dc6dada6298fe1ec73663b47810797b1492de7ed520c","Cargo.toml":"7040d9d576e67a8c86293a132992390b64adc5380917abce864dd9d8f3df7b06","LICENSE":"3db78572e8657cca9e9446ce56a057b8a981eb41af318c49a5fe08e7a10fa52a","README.md":"e918fd4e18659a1d4438ca8f198f979cfdd7a9d27dc8e16f65bcf198c2f3d1cd","lib.rs":"4393ac1bd1d1d41bdcf21901d2aee31187232f95af273dead63913a2fc195b51","tests.rs":"056ea5bd7bd7793107c057cb1600ba831400c29be8938df41a3f9ac8d92fccfd"},"package":"d2606e9192f308ddc4f0b3c5d1bf3400e28a70fff956e9d9f46d23b094746d9f"}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/third_party/rust/uluru/.cargo_vcs_info.json
@@ -0,0 +1,5 @@
+{
+  "git": {
+    "sha1": "feb5fbafe004a3483d99669775bffc4d4b99ce3f"
+  }
+}
--- a/third_party/rust/uluru/Cargo.toml
+++ b/third_party/rust/uluru/Cargo.toml
@@ -7,17 +7,17 @@
 #
 # If you believe there's an error in this file please file an
 # issue against the rust-lang/cargo repository. If you're
 # editing this file be aware that the upstream Cargo.toml
 # will likely look very different (and much more reasonable)
 
 [package]
 name = "uluru"
-version = "0.2.0"
+version = "0.3.0"
 authors = ["The Servo Project Developers"]
 description = "A simple, fast, LRU cache implementation"
 readme = "README.md"
 keywords = ["cache", "linkedlist", "array", "no_std"]
 categories = ["data-structures", "no-std"]
 license = "MPL-2.0"
 repository = "https://github.com/servo/uluru"
 
--- a/third_party/rust/uluru/README.md
+++ b/third_party/rust/uluru/README.md
@@ -1,3 +1,12 @@
 # uluru
 
-A simple, fast, least-recently-used (LRU) cache implementation used for Servo's style system.
+A simple, fast, least-recently-used (LRU) cache implementation used for
+Servo's style system.
+
+`LRUCache` uses a fixed-capacity array for storage. It provides `O(1)`
+insertion, and `O(n)` lookup.  It does not require an allocator and can be
+used in `no_std` crates.
+
+* [Documentation](https://docs.rs/uluru)
+* [crates.io](https://crates.io/crates/uluru)
+* [Release notes](https://github.com/servo/uluru/releases)
--- a/third_party/rust/uluru/lib.rs
+++ b/third_party/rust/uluru/lib.rs
@@ -1,44 +1,77 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #![no_std]
 
-//! A simple least-recently-used (LRU) cache.
+//! A simple, fast, least-recently-used (LRU) cache.
+//!
+//! `LRUCache` uses a fixed-capacity array for storage. It provides `O(1)` insertion, and `O(n)`
+//! lookup.  It does not require an allocator and can be used in `no_std` crates.
+//!
+//! See the [`LRUCache`](LRUCache) docs for details.
 
 extern crate arrayvec;
 
 use arrayvec::{Array, ArrayVec};
 
 #[cfg(test)] mod tests;
 
 /// A LRU cache using a statically-sized array for storage.
 ///
 /// `LRUCache` uses a fixed-capacity array for storage. It provides `O(1)` insertion, and `O(n)`
 /// lookup.
 ///
 /// All items are stored inline within the `LRUCache`, so it does not impose any heap allocation or
 /// indirection.  A linked list is used to record the cache order, so the items themselves do not
 /// need to be moved when the order changes.  (This is important for speed if the items are large.)
+///
+/// # Example
+///
+/// ```
+/// use uluru::{LRUCache, Entry};
+///
+/// struct MyValue {
+///     id: u32,
+///     name: &'static str,
+/// }
+///
+/// // A cache with a capacity of three.
+/// type MyCache = LRUCache<[Entry<MyValue>; 3]>;
+///
+/// // Create an empty cache, then insert some items.
+/// let mut cache = MyCache::default();
+/// cache.insert(MyValue { id: 1, name: "Mercury" });
+/// cache.insert(MyValue { id: 2, name: "Venus" });
+/// cache.insert(MyValue { id: 3, name: "Earth" });
+///
+/// {
+///     // Use the `find` method to retrieve an item from the cache.
+///     // This also "touches" the item, marking it most-recently-used.
+///     let item = cache.find(|x| x.id == 1);
+///     assert_eq!(item.unwrap().name, "Mercury");
+/// }
+///
+/// // If the cache is full, inserting a new item evicts the least-recently-used item:
+/// cache.insert(MyValue { id: 4, name: "Mars" });
+/// assert!(cache.find(|x| x.id == 2).is_none());
+/// ```
 pub struct LRUCache<A: Array> {
     /// The most-recently-used entry is at index `head`. The entries form a linked list, linked to
     /// each other by indices within the `entries` array.  After an entry is added to the array,
     /// its index never changes, so these links are never invalidated.
     entries: ArrayVec<A>,
     /// Index of the first entry. If the cache is empty, ignore this field.
     head: u16,
     /// Index of the last entry. If the cache is empty, ignore this field.
     tail: u16,
 }
 
-/// An opaque token used as an index into an LRUCache.
-pub struct CacheIndex(u16);
-
 /// An entry in an LRUCache.
 pub struct Entry<T> {
     val: T,
     /// Index of the previous entry. If this entry is the head, ignore this field.
     prev: u16,
     /// Index of the next entry. If this entry is the tail, ignore this field.
     next: u16,
 }
@@ -58,45 +91,35 @@ impl<A: Array> Default for LRUCache<A> {
 impl<T, A: Array<Item=Entry<T>>> LRUCache<A> {
     /// Returns the number of elements in the cache.
     pub fn num_entries(&self) -> usize {
         self.entries.len()
     }
 
     #[inline]
     /// Touch a given entry, putting it first in the list.
-    pub fn touch(&mut self, idx: CacheIndex) {
-        if idx.0 != self.head {
-            self.remove(idx.0);
-            self.push_front(idx.0);
+    fn touch(&mut self, idx: u16) {
+        if idx != self.head {
+            self.remove(idx);
+            self.push_front(idx);
         }
     }
 
     /// Returns the front entry in the list (most recently used).
     pub fn front(&self) -> Option<&T> {
         self.entries.get(self.head as usize).map(|e| &e.val)
     }
 
     /// Returns a mutable reference to the front entry in the list (most recently used).
     pub fn front_mut(&mut self) -> Option<&mut T> {
         self.entries.get_mut(self.head as usize).map(|e| &mut e.val)
     }
 
-    /// Iterate over the contents of this cache, from more to less recently
-    /// used.
-    pub fn iter(&self) -> LRUCacheIterator<A> {
-        LRUCacheIterator {
-            pos: self.head,
-            done: self.entries.len() == 0,
-            cache: self,
-        }
-    }
-
     /// Iterate mutably over the contents of this cache.
-    pub fn iter_mut(&mut self) -> LRUCacheMutIterator<A> {
+    fn iter_mut(&mut self) -> LRUCacheMutIterator<A> {
         LRUCacheMutIterator {
             pos: self.head,
             done: self.entries.len() == 0,
             cache: self,
         }
     }
 
     /// Performs a lookup on the cache with the given test routine. Touches
@@ -199,66 +222,38 @@ impl<T, A: Array<Item=Entry<T>>> LRUCach
     }
 
     /// Evict all elements from the cache.
     pub fn evict_all(&mut self) {
         self.entries.clear();
     }
 }
 
-/// Immutable iterator over values in an LRUCache, from most-recently-used to least-recently-used.
-pub struct LRUCacheIterator<'a, A: 'a + Array> {
-    cache: &'a LRUCache<A>,
-    pos: u16,
-    done: bool,
-}
-
-impl<'a, T, A> Iterator for LRUCacheIterator<'a, A>
-where T: 'a,
-      A: 'a + Array<Item=Entry<T>>
-{
-    type Item = (CacheIndex, &'a T);
-
-    fn next(&mut self) -> Option<Self::Item> {
-        if self.done { return None }
-
-        let entry = &self.cache.entries[self.pos as usize];
-
-        let index = CacheIndex(self.pos);
-        if self.pos == self.cache.tail {
-            self.done = true;
-        }
-        self.pos = entry.next;
-
-        Some((index, &entry.val))
-    }
-}
-
 /// Mutable iterator over values in an LRUCache, from most-recently-used to least-recently-used.
-pub struct LRUCacheMutIterator<'a, A: 'a + Array> {
+struct LRUCacheMutIterator<'a, A: 'a + Array> {
     cache: &'a mut LRUCache<A>,
     pos: u16,
     done: bool,
 }
 
 impl<'a, T, A> Iterator for LRUCacheMutIterator<'a, A>
 where T: 'a,
       A: 'a + Array<Item=Entry<T>>
 {
-    type Item = (CacheIndex, &'a mut T);
+    type Item = (u16, &'a mut T);
 
     fn next(&mut self) -> Option<Self::Item> {
         if self.done { return None }
 
         // Use a raw pointer because the compiler doesn't know that subsequent calls can't alias.
         let entry = unsafe {
             &mut *(&mut self.cache.entries[self.pos as usize] as *mut Entry<T>)
         };
 
-        let index = CacheIndex(self.pos);
+        let index = self.pos;
         if self.pos == self.cache.tail {
             self.done = true;
         }
         self.pos = entry.next;
 
         Some((index, &mut entry.val))
     }
 }
--- a/third_party/rust/uluru/tests.rs
+++ b/third_party/rust/uluru/tests.rs
@@ -1,81 +1,81 @@
 extern crate std;
 
 use self::std::vec::Vec;
 use super::*;
 
 type TestCache = LRUCache<[Entry<i32>; 4]>;
 
 /// Convenience function for test assertions
-fn items<T, A>(cache: &LRUCache<A>) -> Vec<T>
+fn items<T, A>(cache: &mut LRUCache<A>) -> Vec<T>
 where
     T: Clone,
     A: Array<Item=Entry<T>>
 {
-    cache.iter().map(|(_, x)| x.clone()).collect()
+    cache.iter_mut().map(|(_, x)| x.clone()).collect()
 }
 
 #[test]
 fn empty() {
-    let cache = TestCache::default();
+    let mut cache = TestCache::default();
     assert_eq!(cache.num_entries(), 0);
-    assert_eq!(items(&cache), []);
+    assert_eq!(items(&mut cache), []);
 }
 
 #[test]
 fn insert() {
     let mut cache = TestCache::default();
     cache.insert(1);
     assert_eq!(cache.num_entries(), 1);
     cache.insert(2);
     assert_eq!(cache.num_entries(), 2);
     cache.insert(3);
     assert_eq!(cache.num_entries(), 3);
     cache.insert(4);
     assert_eq!(cache.num_entries(), 4);
-    assert_eq!(items(&cache), [4, 3, 2, 1], "Ordered from most- to least-recent.");
+    assert_eq!(items(&mut cache), [4, 3, 2, 1], "Ordered from most- to least-recent.");
 
     cache.insert(5);
     assert_eq!(cache.num_entries(), 4);
-    assert_eq!(items(&cache), [5, 4, 3, 2], "Least-recently-used item evicted.");
+    assert_eq!(items(&mut cache), [5, 4, 3, 2], "Least-recently-used item evicted.");
 
     cache.insert(6);
     cache.insert(7);
     cache.insert(8);
     cache.insert(9);
-    assert_eq!(items(&cache), [9, 8, 7, 6], "Least-recently-used item evicted.");
+    assert_eq!(items(&mut cache), [9, 8, 7, 6], "Least-recently-used item evicted.");
 }
 
 #[test]
 fn lookup() {
     let mut cache = TestCache::default();
     cache.insert(1);
     cache.insert(2);
     cache.insert(3);
     cache.insert(4);
 
     let result = cache.lookup(|x| if *x == 5 { Some(()) } else { None });
     assert_eq!(result, None, "Cache miss.");
-    assert_eq!(items(&cache), [4, 3, 2, 1], "Order not changed.");
+    assert_eq!(items(&mut cache), [4, 3, 2, 1], "Order not changed.");
 
     // Cache hit
     let result = cache.lookup(|x| if *x == 3 { Some(*x * 2) } else { None });
     assert_eq!(result, Some(6), "Cache hit.");
-    assert_eq!(items(&cache), [3, 4, 2, 1], "Matching item moved to front.");
+    assert_eq!(items(&mut cache), [3, 4, 2, 1], "Matching item moved to front.");
 }
 
 #[test]
 fn evict_all() {
     let mut cache = TestCache::default();
     cache.insert(1);
     cache.evict_all();
-    assert_eq!(items(&cache), [], "all items evicted");
+    assert_eq!(items(&mut cache), [], "all items evicted");
 
     cache.insert(1);
     cache.insert(2);
     cache.insert(3);
     cache.insert(4);
-    assert_eq!(items(&cache), [4, 3, 2, 1]);
+    assert_eq!(items(&mut cache), [4, 3, 2, 1]);
     cache.evict_all();
-    assert_eq!(items(&cache), [], "all items evicted again");
+    assert_eq!(items(&mut cache), [], "all items evicted again");
 }