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

7 files changed, 70 insertions, 7 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 64d77c53..8037efa9 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -152,6 +152,7 @@ name = "atuin-common"
 version = "14.0.0"
 dependencies = [
  "chrono",
+ "rand",
  "serde",
  "uuid",
 ]
diff --git a/atuin-client/src/history.rs b/atuin-client/src/history.rs
index a710db2b..bb50a02a 100644
--- a/atuin-client/src/history.rs
+++ b/atuin-client/src/history.rs
@@ -3,7 +3,7 @@ use std::env;
 use chrono::Utc;
 use serde::{Deserialize, Serialize};
 
-use atuin_common::utils::uuid_v4;
+use atuin_common::utils::uuid_v7;
 
 // Any new fields MUST be Optional<>!
 #[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, sqlx::FromRow)]
@@ -48,12 +48,12 @@ impl History {
     ) -> Self {
         let session = session
             .or_else(|| env::var("ATUIN_SESSION").ok())
-            .unwrap_or_else(uuid_v4);
+            .unwrap_or_else(|| uuid_v7().as_simple().to_string());
         let hostname =
             hostname.unwrap_or_else(|| format!("{}:{}", whoami::hostname(), whoami::username()));
 
         Self {
-            id: uuid_v4(),
+            id: uuid_v7().as_simple().to_string(),
             timestamp,
             command,
             cwd,
diff --git a/atuin-client/src/import/resh.rs b/atuin-client/src/import/resh.rs
index 41f54836..6fa27b5a 100644
--- a/atuin-client/src/import/resh.rs
+++ b/atuin-client/src/import/resh.rs
@@ -6,7 +6,7 @@ use directories::UserDirs;
 use eyre::{eyre, Result};
 use serde::Deserialize;
 
-use atuin_common::utils::uuid_v4;
+use atuin_common::utils::uuid_v7;
 
 use super::{get_histpath, unix_byte_lines, Importer, Loader};
 use crate::history::History;
@@ -123,13 +123,13 @@ impl Importer for Resh {
             };
 
             h.push(History {
-                id: uuid_v4(),
+                id: uuid_v7().as_simple().to_string(),
                 timestamp,
                 duration,
                 exit: entry.exit_code,
                 command: entry.cmd_line,
                 cwd: entry.pwd,
-                session: uuid_v4(),
+                session: uuid_v7().as_simple().to_string(),
                 hostname: entry.host,
                 deleted_at: None,
             })
diff --git a/atuin-client/src/message.rs b/atuin-client/src/message.rs
new file mode 100644
index 00000000..1c34ee4e
--- /dev/null
+++ b/atuin-client/src/message.rs
@@ -0,0 +1,5 @@
+
+pub struct Message {
+    pub id: Uuid,
+    pub type: String,
+}
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);
+    }
 }
diff --git a/src/command/mod.rs b/src/command/mod.rs
index 1411bfd2..4ed1691a 100644
--- a/src/command/mod.rs
+++ b/src/command/mod.rs
@@ -60,7 +60,7 @@ impl AtuinCmd {
                 Ok(())
             }
             Self::Uuid => {
-                println!("{}", atuin_common::utils::uuid_v4());
+                println!("{}", atuin_common::utils::uuid_v7().as_simple());
                 Ok(())
             }
             Self::GenCompletions { shell, out_dir } => {