| 1 |
//! Generating UUIDs from timestamps. |
| 2 |
//! |
| 3 |
//! Timestamps are used in a few UUID versions as a source of decentralized |
| 4 |
//! uniqueness (as in versions 1 and 6), and as a way to enable sorting (as |
| 5 |
//! in versions 6 and 7). Timestamps aren't encoded the same way by all UUID |
| 6 |
//! versions so this module provides a single [`Timestamp`] type that can |
| 7 |
//! convert between them. |
| 8 |
//! |
| 9 |
//! # Timestamp representations in UUIDs |
| 10 |
//! |
| 11 |
//! Versions 1 and 6 UUIDs use a bespoke timestamp that consists of the |
| 12 |
//! number of 100ns ticks since `1582-10-15 00:00:00`, along with |
| 13 |
//! a counter value to avoid duplicates. |
| 14 |
//! |
| 15 |
//! Version 7 UUIDs use a more standard timestamp that consists of the |
| 16 |
//! number of millisecond ticks since the Unix epoch (`1970-01-01 00:00:00`). |
| 17 |
//! |
| 18 |
//! # References |
| 19 |
//! |
| 20 |
//! * [Timestamp in RFC4122](https://www.rfc-editor.org/rfc/rfc4122#section-4.1.4) |
| 21 |
//! * [Timestamp in Draft RFC: New UUID Formats, Version 4](https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-04#section-6.1) |
| 22 |
|
| 23 |
use crate::Uuid; |
| 24 |
|
| 25 |
/// The number of 100 nanosecond ticks between the RFC4122 epoch |
| 26 |
/// (`1582-10-15 00:00:00`) and the Unix epoch (`1970-01-01 00:00:00`). |
| 27 |
pub const UUID_TICKS_BETWEEN_EPOCHS: u64 = 0x01B2_1DD2_1381_4000; |
| 28 |
|
| 29 |
/// A timestamp that can be encoded into a UUID. |
| 30 |
/// |
| 31 |
/// This type abstracts the specific encoding, so versions 1, 6, and 7 |
| 32 |
/// UUIDs can both be supported through the same type, even |
| 33 |
/// though they have a different representation of a timestamp. |
| 34 |
/// |
| 35 |
/// # References |
| 36 |
/// |
| 37 |
/// * [Timestamp in RFC4122](https://www.rfc-editor.org/rfc/rfc4122#section-4.1.4) |
| 38 |
/// * [Timestamp in Draft RFC: New UUID Formats, Version 4](https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-04#section-6.1) |
| 39 |
/// * [Clock Sequence in RFC4122](https://datatracker.ietf.org/doc/html/rfc4122#section-4.1.5) |
| 40 |
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] |
| 41 |
pub struct Timestamp { |
| 42 |
pub(crate) seconds: u64, |
| 43 |
pub(crate) nanos: u32, |
| 44 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 45 |
pub(crate) counter: u16, |
| 46 |
} |
| 47 |
|
| 48 |
impl Timestamp { |
| 49 |
/// Get a timestamp representing the current system time. |
| 50 |
/// |
| 51 |
/// This method defers to the standard library's `SystemTime` type. |
| 52 |
/// |
| 53 |
/// # Panics |
| 54 |
/// |
| 55 |
/// This method will panic if calculating the elapsed time since the Unix epoch fails. |
| 56 |
#[cfg(feature = "std")] |
| 57 |
pub fn now(context: impl ClockSequence<Output = u16>) -> Self { |
| 58 |
#[cfg(not(any(feature = "v1", feature = "v6")))] |
| 59 |
{ |
| 60 |
let _ = context; |
| 61 |
} |
| 62 |
|
| 63 |
let (seconds, nanos) = now(); |
| 64 |
|
| 65 |
Timestamp { |
| 66 |
seconds, |
| 67 |
nanos, |
| 68 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 69 |
counter: context.generate_sequence(seconds, nanos), |
| 70 |
} |
| 71 |
} |
| 72 |
|
| 73 |
/// Construct a `Timestamp` from an RFC4122 timestamp and counter, as used |
| 74 |
/// in versions 1 and 6 UUIDs. |
| 75 |
/// |
| 76 |
/// # Overflow |
| 77 |
/// |
| 78 |
/// If conversion from RFC4122 ticks to the internal timestamp format would overflow |
| 79 |
/// it will wrap. |
| 80 |
pub const fn from_rfc4122(ticks: u64, counter: u16) -> Self { |
| 81 |
#[cfg(not(any(feature = "v1", feature = "v6")))] |
| 82 |
{ |
| 83 |
let _ = counter; |
| 84 |
} |
| 85 |
|
| 86 |
let (seconds, nanos) = Self::rfc4122_to_unix(ticks); |
| 87 |
|
| 88 |
Timestamp { |
| 89 |
seconds, |
| 90 |
nanos, |
| 91 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 92 |
counter, |
| 93 |
} |
| 94 |
} |
| 95 |
|
| 96 |
/// Construct a `Timestamp` from a Unix timestamp, as used in version 7 UUIDs. |
| 97 |
/// |
| 98 |
/// # Overflow |
| 99 |
/// |
| 100 |
/// If conversion from RFC4122 ticks to the internal timestamp format would overflow |
| 101 |
/// it will wrap. |
| 102 |
pub fn from_unix(context: impl ClockSequence<Output = u16>, seconds: u64, nanos: u32) -> Self { |
| 103 |
#[cfg(not(any(feature = "v1", feature = "v6")))] |
| 104 |
{ |
| 105 |
let _ = context; |
| 106 |
|
| 107 |
Timestamp { seconds, nanos } |
| 108 |
} |
| 109 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 110 |
{ |
| 111 |
let counter = context.generate_sequence(seconds, nanos); |
| 112 |
|
| 113 |
Timestamp { |
| 114 |
seconds, |
| 115 |
nanos, |
| 116 |
counter, |
| 117 |
} |
| 118 |
} |
| 119 |
} |
| 120 |
|
| 121 |
/// Get the value of the timestamp as an RFC4122 timestamp and counter, |
| 122 |
/// as used in versions 1 and 6 UUIDs. |
| 123 |
/// |
| 124 |
/// # Overflow |
| 125 |
/// |
| 126 |
/// If conversion from RFC4122 ticks to the internal timestamp format would overflow |
| 127 |
/// it will wrap. |
| 128 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 129 |
pub const fn to_rfc4122(&self) -> (u64, u16) { |
| 130 |
( |
| 131 |
Self::unix_to_rfc4122_ticks(self.seconds, self.nanos), |
| 132 |
self.counter, |
| 133 |
) |
| 134 |
} |
| 135 |
|
| 136 |
/// Get the value of the timestamp as a Unix timestamp, as used in version 7 UUIDs. |
| 137 |
/// |
| 138 |
/// # Overflow |
| 139 |
/// |
| 140 |
/// If conversion from RFC4122 ticks to the internal timestamp format would overflow |
| 141 |
/// it will wrap. |
| 142 |
pub const fn to_unix(&self) -> (u64, u32) { |
| 143 |
(self.seconds, self.nanos) |
| 144 |
} |
| 145 |
|
| 146 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 147 |
const fn unix_to_rfc4122_ticks(seconds: u64, nanos: u32) -> u64 { |
| 148 |
UUID_TICKS_BETWEEN_EPOCHS |
| 149 |
.wrapping_add(seconds.wrapping_mul(10_000_000)) |
| 150 |
.wrapping_add(nanos as u64 / 100) |
| 151 |
} |
| 152 |
|
| 153 |
const fn rfc4122_to_unix(ticks: u64) -> (u64, u32) { |
| 154 |
( |
| 155 |
ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) / 10_000_000, |
| 156 |
(ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) % 10_000_000) as u32 * 100, |
| 157 |
) |
| 158 |
} |
| 159 |
|
| 160 |
#[deprecated(note = "use `to_unix` instead; this method will be removed in a future release")] |
| 161 |
/// Get the number of fractional nanoseconds in the Unix timestamp. |
| 162 |
/// |
| 163 |
/// This method is deprecated and probably doesn't do what you're expecting it to. |
| 164 |
/// It doesn't return the timestamp as nanoseconds since the Unix epoch, it returns |
| 165 |
/// the fractional seconds of the timestamp. |
| 166 |
pub const fn to_unix_nanos(&self) -> u32 { |
| 167 |
panic!("`Timestamp::to_unix_nanos` is deprecated and will be removed: use `Timestamp::to_unix` instead") |
| 168 |
} |
| 169 |
} |
| 170 |
|
| 171 |
pub(crate) const fn encode_rfc4122_timestamp(ticks: u64, counter: u16, node_id: &[u8; 6]) -> Uuid { |
| 172 |
let time_low = (ticks & 0xFFFF_FFFF) as u32; |
| 173 |
let time_mid = ((ticks >> 32) & 0xFFFF) as u16; |
| 174 |
let time_high_and_version = (((ticks >> 48) & 0x0FFF) as u16) | (1 << 12); |
| 175 |
|
| 176 |
let mut d4 = [0; 8]; |
| 177 |
|
| 178 |
d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80; |
| 179 |
d4[1] = (counter & 0xFF) as u8; |
| 180 |
d4[2] = node_id[0]; |
| 181 |
d4[3] = node_id[1]; |
| 182 |
d4[4] = node_id[2]; |
| 183 |
d4[5] = node_id[3]; |
| 184 |
d4[6] = node_id[4]; |
| 185 |
d4[7] = node_id[5]; |
| 186 |
|
| 187 |
Uuid::from_fields(time_low, time_mid, time_high_and_version, &d4) |
| 188 |
} |
| 189 |
|
| 190 |
pub(crate) const fn decode_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) { |
| 191 |
let bytes = uuid.as_bytes(); |
| 192 |
|
| 193 |
let ticks: u64 = ((bytes[6] & 0x0F) as u64) << 56 |
| 194 |
| (bytes[7] as u64) << 48 |
| 195 |
| (bytes[4] as u64) << 40 |
| 196 |
| (bytes[5] as u64) << 32 |
| 197 |
| (bytes[0] as u64) << 24 |
| 198 |
| (bytes[1] as u64) << 16 |
| 199 |
| (bytes[2] as u64) << 8 |
| 200 |
| (bytes[3] as u64); |
| 201 |
|
| 202 |
let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16); |
| 203 |
|
| 204 |
(ticks, counter) |
| 205 |
} |
| 206 |
|
| 207 |
pub(crate) const fn encode_sorted_rfc4122_timestamp( |
| 208 |
ticks: u64, |
| 209 |
counter: u16, |
| 210 |
node_id: &[u8; 6], |
| 211 |
) -> Uuid { |
| 212 |
let time_high = ((ticks >> 28) & 0xFFFF_FFFF) as u32; |
| 213 |
let time_mid = ((ticks >> 12) & 0xFFFF) as u16; |
| 214 |
let time_low_and_version = ((ticks & 0x0FFF) as u16) | (0x6 << 12); |
| 215 |
|
| 216 |
let mut d4 = [0; 8]; |
| 217 |
|
| 218 |
d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80; |
| 219 |
d4[1] = (counter & 0xFF) as u8; |
| 220 |
d4[2] = node_id[0]; |
| 221 |
d4[3] = node_id[1]; |
| 222 |
d4[4] = node_id[2]; |
| 223 |
d4[5] = node_id[3]; |
| 224 |
d4[6] = node_id[4]; |
| 225 |
d4[7] = node_id[5]; |
| 226 |
|
| 227 |
Uuid::from_fields(time_high, time_mid, time_low_and_version, &d4) |
| 228 |
} |
| 229 |
|
| 230 |
pub(crate) const fn decode_sorted_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) { |
| 231 |
let bytes = uuid.as_bytes(); |
| 232 |
|
| 233 |
let ticks: u64 = ((bytes[0]) as u64) << 52 |
| 234 |
| (bytes[1] as u64) << 44 |
| 235 |
| (bytes[2] as u64) << 36 |
| 236 |
| (bytes[3] as u64) << 28 |
| 237 |
| (bytes[4] as u64) << 20 |
| 238 |
| (bytes[5] as u64) << 12 |
| 239 |
| ((bytes[6] & 0xF) as u64) << 8 |
| 240 |
| (bytes[7] as u64); |
| 241 |
|
| 242 |
let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16); |
| 243 |
|
| 244 |
(ticks, counter) |
| 245 |
} |
| 246 |
|
| 247 |
pub(crate) const fn encode_unix_timestamp_millis(millis: u64, random_bytes: &[u8; 10]) -> Uuid { |
| 248 |
let millis_high = ((millis >> 16) & 0xFFFF_FFFF) as u32; |
| 249 |
let millis_low = (millis & 0xFFFF) as u16; |
| 250 |
|
| 251 |
let random_and_version = |
| 252 |
(random_bytes[1] as u16 | ((random_bytes[0] as u16) << 8) & 0x0FFF) | (0x7 << 12); |
| 253 |
|
| 254 |
let mut d4 = [0; 8]; |
| 255 |
|
| 256 |
d4[0] = (random_bytes[2] & 0x3F) | 0x80; |
| 257 |
d4[1] = random_bytes[3]; |
| 258 |
d4[2] = random_bytes[4]; |
| 259 |
d4[3] = random_bytes[5]; |
| 260 |
d4[4] = random_bytes[6]; |
| 261 |
d4[5] = random_bytes[7]; |
| 262 |
d4[6] = random_bytes[8]; |
| 263 |
d4[7] = random_bytes[9]; |
| 264 |
|
| 265 |
Uuid::from_fields(millis_high, millis_low, random_and_version, &d4) |
| 266 |
} |
| 267 |
|
| 268 |
pub(crate) const fn decode_unix_timestamp_millis(uuid: &Uuid) -> u64 { |
| 269 |
let bytes = uuid.as_bytes(); |
| 270 |
|
| 271 |
let millis: u64 = (bytes[0] as u64) << 40 |
| 272 |
| (bytes[1] as u64) << 32 |
| 273 |
| (bytes[2] as u64) << 24 |
| 274 |
| (bytes[3] as u64) << 16 |
| 275 |
| (bytes[4] as u64) << 8 |
| 276 |
| (bytes[5] as u64); |
| 277 |
|
| 278 |
millis |
| 279 |
} |
| 280 |
|
| 281 |
#[cfg(all( |
| 282 |
feature = "std", |
| 283 |
feature = "js", |
| 284 |
all( |
| 285 |
target_arch = "wasm32", |
| 286 |
target_vendor = "unknown", |
| 287 |
target_os = "unknown" |
| 288 |
) |
| 289 |
))] |
| 290 |
fn now() -> (u64, u32) { |
| 291 |
use wasm_bindgen::prelude::*; |
| 292 |
|
| 293 |
#[wasm_bindgen] |
| 294 |
extern "C" { |
| 295 |
// NOTE: This signature works around https://bugzilla.mozilla.org/show_bug.cgi?id=1787770 |
| 296 |
#[wasm_bindgen(js_namespace = Date, catch)] |
| 297 |
fn now() -> Result<f64, JsValue>; |
| 298 |
} |
| 299 |
|
| 300 |
let now = now().unwrap_throw(); |
| 301 |
|
| 302 |
let secs = (now / 1_000.0) as u64; |
| 303 |
let nanos = ((now % 1_000.0) * 1_000_000.0) as u32; |
| 304 |
|
| 305 |
(secs, nanos) |
| 306 |
} |
| 307 |
|
| 308 |
#[cfg(all( |
| 309 |
feature = "std", |
| 310 |
any( |
| 311 |
not(feature = "js"), |
| 312 |
not(all( |
| 313 |
target_arch = "wasm32", |
| 314 |
target_vendor = "unknown", |
| 315 |
target_os = "unknown" |
| 316 |
)) |
| 317 |
) |
| 318 |
))] |
| 319 |
fn now() -> (u64, u32) { |
| 320 |
let dur = std::time::SystemTime::UNIX_EPOCH.elapsed().expect( |
| 321 |
"Getting elapsed time since UNIX_EPOCH. If this fails, we've somehow violated causality", |
| 322 |
); |
| 323 |
|
| 324 |
(dur.as_secs(), dur.subsec_nanos()) |
| 325 |
} |
| 326 |
|
| 327 |
/// A counter that can be used by version 1 and version 6 UUIDs to support |
| 328 |
/// the uniqueness of timestamps. |
| 329 |
/// |
| 330 |
/// # References |
| 331 |
/// |
| 332 |
/// * [Clock Sequence in RFC4122](https://datatracker.ietf.org/doc/html/rfc4122#section-4.1.5) |
| 333 |
pub trait ClockSequence { |
| 334 |
/// The type of sequence returned by this counter. |
| 335 |
type Output; |
| 336 |
|
| 337 |
/// Get the next value in the sequence to feed into a timestamp. |
| 338 |
/// |
| 339 |
/// This method will be called each time a [`Timestamp`] is constructed. |
| 340 |
fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output; |
| 341 |
} |
| 342 |
|
| 343 |
impl<'a, T: ClockSequence + ?Sized> ClockSequence for &'a T { |
| 344 |
type Output = T::Output; |
| 345 |
fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output { |
| 346 |
(**self).generate_sequence(seconds, subsec_nanos) |
| 347 |
} |
| 348 |
} |
| 349 |
|
| 350 |
/// Default implementations for the [`ClockSequence`] trait. |
| 351 |
pub mod context { |
| 352 |
use super::ClockSequence; |
| 353 |
|
| 354 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 355 |
use atomic::{Atomic, Ordering}; |
| 356 |
|
| 357 |
/// An empty counter that will always return the value `0`. |
| 358 |
/// |
| 359 |
/// This type should be used when constructing timestamps for version 7 UUIDs, |
| 360 |
/// since they don't need a counter for uniqueness. |
| 361 |
#[derive(Debug, Clone, Copy, Default)] |
| 362 |
pub struct NoContext; |
| 363 |
|
| 364 |
impl ClockSequence for NoContext { |
| 365 |
type Output = u16; |
| 366 |
|
| 367 |
fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output { |
| 368 |
0 |
| 369 |
} |
| 370 |
} |
| 371 |
|
| 372 |
#[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))] |
| 373 |
static CONTEXT: Context = Context { |
| 374 |
count: Atomic::new(0), |
| 375 |
}; |
| 376 |
|
| 377 |
#[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))] |
| 378 |
static CONTEXT_INITIALIZED: Atomic<bool> = Atomic::new(false); |
| 379 |
|
| 380 |
#[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))] |
| 381 |
pub(crate) fn shared_context() -> &'static Context { |
| 382 |
// If the context is in its initial state then assign it to a random value |
| 383 |
// It doesn't matter if multiple threads observe `false` here and initialize the context |
| 384 |
if CONTEXT_INITIALIZED |
| 385 |
.compare_exchange(false, true, Ordering::Relaxed, Ordering::Relaxed) |
| 386 |
.is_ok() |
| 387 |
{ |
| 388 |
CONTEXT.count.store(crate::rng::u16(), Ordering::Release); |
| 389 |
} |
| 390 |
|
| 391 |
&CONTEXT |
| 392 |
} |
| 393 |
|
| 394 |
/// A thread-safe, wrapping counter that produces 14-bit numbers. |
| 395 |
/// |
| 396 |
/// This type should be used when constructing version 1 and version 6 UUIDs. |
| 397 |
#[derive(Debug)] |
| 398 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 399 |
pub struct Context { |
| 400 |
count: Atomic<u16>, |
| 401 |
} |
| 402 |
|
| 403 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 404 |
impl Context { |
| 405 |
/// Construct a new context that's initialized with the given value. |
| 406 |
/// |
| 407 |
/// The starting value should be a random number, so that UUIDs from |
| 408 |
/// different systems with the same timestamps are less likely to collide. |
| 409 |
/// When the `rng` feature is enabled, prefer the [`Context::new_random`] method. |
| 410 |
pub const fn new(count: u16) -> Self { |
| 411 |
Self { |
| 412 |
count: Atomic::<u16>::new(count), |
| 413 |
} |
| 414 |
} |
| 415 |
|
| 416 |
/// Construct a new context that's initialized with a random value. |
| 417 |
#[cfg(feature = "rng")] |
| 418 |
pub fn new_random() -> Self { |
| 419 |
Self { |
| 420 |
count: Atomic::<u16>::new(crate::rng::u16()), |
| 421 |
} |
| 422 |
} |
| 423 |
} |
| 424 |
|
| 425 |
#[cfg(any(feature = "v1", feature = "v6"))] |
| 426 |
impl ClockSequence for Context { |
| 427 |
type Output = u16; |
| 428 |
|
| 429 |
fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output { |
| 430 |
// RFC4122 reserves 2 bits of the clock sequence so the actual |
| 431 |
// maximum value is smaller than `u16::MAX`. Since we unconditionally |
| 432 |
// increment the clock sequence we want to wrap once it becomes larger |
| 433 |
// than what we can represent in a "u14". Otherwise there'd be patches |
| 434 |
// where the clock sequence doesn't change regardless of the timestamp |
| 435 |
self.count.fetch_add(1, Ordering::AcqRel) & (u16::MAX >> 2) |
| 436 |
} |
| 437 |
} |
| 438 |
} |
| 439 |
|
| 440 |
#[cfg(all(test, any(feature = "v1", feature = "v6")))] |
| 441 |
mod tests { |
| 442 |
use super::*; |
| 443 |
|
| 444 |
#[cfg(all( |
| 445 |
target_arch = "wasm32", |
| 446 |
target_vendor = "unknown", |
| 447 |
target_os = "unknown" |
| 448 |
))] |
| 449 |
use wasm_bindgen_test::*; |
| 450 |
|
| 451 |
#[test] |
| 452 |
#[cfg_attr( |
| 453 |
all( |
| 454 |
target_arch = "wasm32", |
| 455 |
target_vendor = "unknown", |
| 456 |
target_os = "unknown" |
| 457 |
), |
| 458 |
wasm_bindgen_test |
| 459 |
)] |
| 460 |
fn rfc4122_unix_does_not_panic() { |
| 461 |
// Ensure timestamp conversions never panic |
| 462 |
Timestamp::unix_to_rfc4122_ticks(u64::MAX, 0); |
| 463 |
Timestamp::unix_to_rfc4122_ticks(0, u32::MAX); |
| 464 |
Timestamp::unix_to_rfc4122_ticks(u64::MAX, u32::MAX); |
| 465 |
|
| 466 |
Timestamp::rfc4122_to_unix(u64::MAX); |
| 467 |
} |
| 468 |
} |