Switch to uuidv7 (#864)

* Add uuid_v7

* Actually use the new uuid

* Add a test to ensure all uuids are unique, even in a tight loop

* Make clippy happy

2 files changed, 57 insertions, 0 deletions

diff --git a/atuin-common/Cargo.toml b/atuin-common/Cargo.toml
index 16592381..d065a32d 100644
--- a/atuin-common/Cargo.toml
+++ b/atuin-common/Cargo.toml
@@ -14,3 +14,4 @@ repository = "https://github.com/ellie/atuin"
 chrono = { version = "0.4", features = ["serde"] }
 serde = { version = "1.0.145", features = ["derive"] }
 uuid = { version = "1.2", features = ["v4"] }
+rand = { version = "0.8.5", features = ["std"] }
diff --git a/atuin-common/src/utils.rs b/atuin-common/src/utils.rs
index 5fe6eeea..776a63de 100644
--- a/atuin-common/src/utils.rs
+++ b/atuin-common/src/utils.rs
@@ -2,8 +2,46 @@ use std::env;
 use std::path::PathBuf;
 
 use chrono::{Months, NaiveDate};
+use rand::RngCore;
 use uuid::Uuid;
 
+pub fn random_bytes<const N: usize>() -> [u8; N] {
+    let mut ret = [0u8; N];
+
+    rand::thread_rng().fill_bytes(&mut ret);
+
+    ret
+}
+
+// basically just ripped from the uuid crate. they have it as unstable, but we can use it fine.
+const fn encode_unix_timestamp_millis(millis: u64, random_bytes: &[u8; 10]) -> Uuid {
+    let millis_high = ((millis >> 16) & 0xFFFF_FFFF) as u32;
+    let millis_low = (millis & 0xFFFF) as u16;
+
+    let random_and_version =
+        (random_bytes[0] as u16 | ((random_bytes[1] as u16) << 8) & 0x0FFF) | (0x7 << 12);
+
+    let mut d4 = [0; 8];
+
+    d4[0] = (random_bytes[2] & 0x3F) | 0x80;
+    d4[1] = random_bytes[3];
+    d4[2] = random_bytes[4];
+    d4[3] = random_bytes[5];
+    d4[4] = random_bytes[6];
+    d4[5] = random_bytes[7];
+    d4[6] = random_bytes[8];
+    d4[7] = random_bytes[9];
+
+    Uuid::from_fields(millis_high, millis_low, random_and_version, &d4)
+}
+
+pub fn uuid_v7() -> Uuid {
+    let bytes = random_bytes();
+    let now: u64 = chrono::Utc::now().timestamp_millis() as u64;
+
+    encode_unix_timestamp_millis(now, &bytes)
+}
+
 pub fn uuid_v4() -> String {
     Uuid::new_v4().as_simple().to_string()
 }
@@ -59,6 +97,8 @@ mod tests {
     use super::*;
     use std::env;
 
+    use std::collections::HashSet;
+
     #[test]
     fn test_dirs() {
         // these tests need to be run sequentially to prevent race condition
@@ -117,4 +157,20 @@ mod tests {
         // leap years
         assert_eq!(get_days_from_month(2024, 2), 29);
     }
+
+    #[test]
+    fn uuid_is_unique() {
+        let how_many: usize = 1000000;
+
+        // for peace of mind
+        let mut uuids: HashSet<Uuid> = HashSet::with_capacity(how_many);
+
+        // there will be many in the same millisecond
+        for _ in 0..how_many {
+            let uuid = uuid_v7();
+            uuids.insert(uuid);
+        }
+
+        assert_eq!(uuids.len(), how_many);
+    }
 }