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 | let ticks = UUID_TICKS_BETWEEN_EPOCHS |
149 | .wrapping_add(seconds.wrapping_mul(10_000_000)) |
150 | .wrapping_add(nanos as u64 / 100); |
151 | |
152 | ticks |
153 | } |
154 | |
155 | const fn rfc4122_to_unix(ticks: u64) -> (u64, u32) { |
156 | ( |
157 | ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) / 10_000_000, |
158 | (ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) % 10_000_000) as u32 * 100, |
159 | ) |
160 | } |
161 | |
162 | #[deprecated (note = "use `to_unix` instead; this method will be removed in a future release" )] |
163 | /// Get the number of fractional nanoseconds in the Unix timestamp. |
164 | /// |
165 | /// This method is deprecated and probably doesn't do what you're expecting it to. |
166 | /// It doesn't return the timestamp as nanoseconds since the Unix epoch, it returns |
167 | /// the fractional seconds of the timestamp. |
168 | pub const fn to_unix_nanos(&self) -> u32 { |
169 | panic!("`Timestamp::to_unix_nanos` is deprecated and will be removed: use `Timestamp::to_unix` instead" ) |
170 | } |
171 | } |
172 | |
173 | pub(crate) const fn encode_rfc4122_timestamp(ticks: u64, counter: u16, node_id: &[u8; 6]) -> Uuid { |
174 | let time_low: u32 = (ticks & 0xFFFF_FFFF) as u32; |
175 | let time_mid: u16 = ((ticks >> 32) & 0xFFFF) as u16; |
176 | let time_high_and_version: u16 = (((ticks >> 48) & 0x0FFF) as u16) | (1 << 12); |
177 | |
178 | let mut d4: [u8; 8] = [0; 8]; |
179 | |
180 | d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80; |
181 | d4[1] = (counter & 0xFF) as u8; |
182 | d4[2] = node_id[0]; |
183 | d4[3] = node_id[1]; |
184 | d4[4] = node_id[2]; |
185 | d4[5] = node_id[3]; |
186 | d4[6] = node_id[4]; |
187 | d4[7] = node_id[5]; |
188 | |
189 | Uuid::from_fields(d1:time_low, d2:time_mid, d3:time_high_and_version, &d4) |
190 | } |
191 | |
192 | pub(crate) const fn decode_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) { |
193 | let bytes: &[u8; 16] = uuid.as_bytes(); |
194 | |
195 | let ticks: u64 = ((bytes[6] & 0x0F) as u64) << 56 |
196 | | (bytes[7] as u64) << 48 |
197 | | (bytes[4] as u64) << 40 |
198 | | (bytes[5] as u64) << 32 |
199 | | (bytes[0] as u64) << 24 |
200 | | (bytes[1] as u64) << 16 |
201 | | (bytes[2] as u64) << 8 |
202 | | (bytes[3] as u64); |
203 | |
204 | let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16); |
205 | |
206 | (ticks, counter) |
207 | } |
208 | |
209 | #[cfg (uuid_unstable)] |
210 | pub(crate) const fn encode_sorted_rfc4122_timestamp( |
211 | ticks: u64, |
212 | counter: u16, |
213 | node_id: &[u8; 6], |
214 | ) -> Uuid { |
215 | let time_high = ((ticks >> 28) & 0xFFFF_FFFF) as u32; |
216 | let time_mid = ((ticks >> 12) & 0xFFFF) as u16; |
217 | let time_low_and_version = ((ticks & 0x0FFF) as u16) | (0x6 << 12); |
218 | |
219 | let mut d4 = [0; 8]; |
220 | |
221 | d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80; |
222 | d4[1] = (counter & 0xFF) as u8; |
223 | d4[2] = node_id[0]; |
224 | d4[3] = node_id[1]; |
225 | d4[4] = node_id[2]; |
226 | d4[5] = node_id[3]; |
227 | d4[6] = node_id[4]; |
228 | d4[7] = node_id[5]; |
229 | |
230 | Uuid::from_fields(time_high, time_mid, time_low_and_version, &d4) |
231 | } |
232 | |
233 | #[cfg (uuid_unstable)] |
234 | pub(crate) const fn decode_sorted_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) { |
235 | let bytes = uuid.as_bytes(); |
236 | |
237 | let ticks: u64 = ((bytes[0]) as u64) << 52 |
238 | | (bytes[1] as u64) << 44 |
239 | | (bytes[2] as u64) << 36 |
240 | | (bytes[3] as u64) << 28 |
241 | | (bytes[4] as u64) << 20 |
242 | | (bytes[5] as u64) << 12 |
243 | | ((bytes[6] & 0xF) as u64) << 8 |
244 | | (bytes[7] as u64); |
245 | |
246 | let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16); |
247 | |
248 | (ticks, counter) |
249 | } |
250 | |
251 | #[cfg (uuid_unstable)] |
252 | pub(crate) const fn encode_unix_timestamp_millis(millis: u64, random_bytes: &[u8; 10]) -> Uuid { |
253 | let millis_high = ((millis >> 16) & 0xFFFF_FFFF) as u32; |
254 | let millis_low = (millis & 0xFFFF) as u16; |
255 | |
256 | let random_and_version = |
257 | (random_bytes[1] as u16 | ((random_bytes[0] as u16) << 8) & 0x0FFF) | (0x7 << 12); |
258 | |
259 | let mut d4 = [0; 8]; |
260 | |
261 | d4[0] = (random_bytes[2] & 0x3F) | 0x80; |
262 | d4[1] = random_bytes[3]; |
263 | d4[2] = random_bytes[4]; |
264 | d4[3] = random_bytes[5]; |
265 | d4[4] = random_bytes[6]; |
266 | d4[5] = random_bytes[7]; |
267 | d4[6] = random_bytes[8]; |
268 | d4[7] = random_bytes[9]; |
269 | |
270 | Uuid::from_fields(millis_high, millis_low, random_and_version, &d4) |
271 | } |
272 | |
273 | #[cfg (uuid_unstable)] |
274 | pub(crate) const fn decode_unix_timestamp_millis(uuid: &Uuid) -> u64 { |
275 | let bytes = uuid.as_bytes(); |
276 | |
277 | let millis: u64 = (bytes[0] as u64) << 40 |
278 | | (bytes[1] as u64) << 32 |
279 | | (bytes[2] as u64) << 24 |
280 | | (bytes[3] as u64) << 16 |
281 | | (bytes[4] as u64) << 8 |
282 | | (bytes[5] as u64); |
283 | |
284 | millis |
285 | } |
286 | |
287 | #[cfg (all( |
288 | feature = "std" , |
289 | feature = "js" , |
290 | all( |
291 | target_arch = "wasm32" , |
292 | target_vendor = "unknown" , |
293 | target_os = "unknown" |
294 | ) |
295 | ))] |
296 | fn now() -> (u64, u32) { |
297 | use wasm_bindgen::prelude::*; |
298 | |
299 | #[wasm_bindgen] |
300 | extern "C" { |
301 | // NOTE: This signature works around https://bugzilla.mozilla.org/show_bug.cgi?id=1787770 |
302 | #[wasm_bindgen(js_namespace = Date, catch)] |
303 | fn now() -> Result<f64, JsValue>; |
304 | } |
305 | |
306 | let now = now().unwrap_throw(); |
307 | |
308 | let secs = (now / 1_000.0) as u64; |
309 | let nanos = ((now % 1_000.0) * 1_000_000.0) as u32; |
310 | |
311 | (secs, nanos) |
312 | } |
313 | |
314 | #[cfg (all( |
315 | feature = "std" , |
316 | any( |
317 | not(feature = "js" ), |
318 | not(all( |
319 | target_arch = "wasm32" , |
320 | target_vendor = "unknown" , |
321 | target_os = "unknown" |
322 | )) |
323 | ) |
324 | ))] |
325 | fn now() -> (u64, u32) { |
326 | let dur: Duration = std::time::SystemTime::UNIX_EPOCH.elapsed().expect( |
327 | msg:"Getting elapsed time since UNIX_EPOCH. If this fails, we've somehow violated causality" , |
328 | ); |
329 | |
330 | (dur.as_secs(), dur.subsec_nanos()) |
331 | } |
332 | |
333 | /// A counter that can be used by version 1 and version 6 UUIDs to support |
334 | /// the uniqueness of timestamps. |
335 | /// |
336 | /// # References |
337 | /// |
338 | /// * [Clock Sequence in RFC4122](https://datatracker.ietf.org/doc/html/rfc4122#section-4.1.5) |
339 | pub trait ClockSequence { |
340 | /// The type of sequence returned by this counter. |
341 | type Output; |
342 | |
343 | /// Get the next value in the sequence to feed into a timestamp. |
344 | /// |
345 | /// This method will be called each time a [`Timestamp`] is constructed. |
346 | fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output; |
347 | } |
348 | |
349 | impl<'a, T: ClockSequence + ?Sized> ClockSequence for &'a T { |
350 | type Output = T::Output; |
351 | fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output { |
352 | (**self).generate_sequence(seconds, subsec_nanos) |
353 | } |
354 | } |
355 | |
356 | /// Default implementations for the [`ClockSequence`] trait. |
357 | pub mod context { |
358 | use super::ClockSequence; |
359 | |
360 | #[cfg (any(feature = "v1" , feature = "v6" ))] |
361 | use atomic::{Atomic, Ordering}; |
362 | |
363 | /// An empty counter that will always return the value `0`. |
364 | /// |
365 | /// This type should be used when constructing timestamps for version 7 UUIDs, |
366 | /// since they don't need a counter for uniqueness. |
367 | #[derive (Debug, Clone, Copy, Default)] |
368 | pub struct NoContext; |
369 | |
370 | impl ClockSequence for NoContext { |
371 | type Output = u16; |
372 | |
373 | fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output { |
374 | 0 |
375 | } |
376 | } |
377 | |
378 | #[cfg (all(any(feature = "v1" , feature = "v6" ), feature = "std" , feature = "rng" ))] |
379 | static CONTEXT: Context = Context { |
380 | count: Atomic::new(0), |
381 | }; |
382 | |
383 | #[cfg (all(any(feature = "v1" , feature = "v6" ), feature = "std" , feature = "rng" ))] |
384 | static CONTEXT_INITIALIZED: Atomic<bool> = Atomic::new(false); |
385 | |
386 | #[cfg (all(any(feature = "v1" , feature = "v6" ), feature = "std" , feature = "rng" ))] |
387 | pub(crate) fn shared_context() -> &'static Context { |
388 | // If the context is in its initial state then assign it to a random value |
389 | // It doesn't matter if multiple threads observe `false` here and initialize the context |
390 | if CONTEXT_INITIALIZED |
391 | .compare_exchange(false, true, Ordering::Relaxed, Ordering::Relaxed) |
392 | .is_ok() |
393 | { |
394 | CONTEXT.count.store(crate::rng::u16(), Ordering::Release); |
395 | } |
396 | |
397 | &CONTEXT |
398 | } |
399 | |
400 | /// A thread-safe, wrapping counter that produces 14-bit numbers. |
401 | /// |
402 | /// This type should be used when constructing version 1 and version 6 UUIDs. |
403 | #[derive (Debug)] |
404 | #[cfg (any(feature = "v1" , feature = "v6" ))] |
405 | pub struct Context { |
406 | count: Atomic<u16>, |
407 | } |
408 | |
409 | #[cfg (any(feature = "v1" , feature = "v6" ))] |
410 | impl Context { |
411 | /// Construct a new context that's initialized with the given value. |
412 | /// |
413 | /// The starting value should be a random number, so that UUIDs from |
414 | /// different systems with the same timestamps are less likely to collide. |
415 | /// When the `rng` feature is enabled, prefer the [`Context::new_random`] method. |
416 | pub const fn new(count: u16) -> Self { |
417 | Self { |
418 | count: Atomic::<u16>::new(count), |
419 | } |
420 | } |
421 | |
422 | /// Construct a new context that's initialized with a random value. |
423 | #[cfg (feature = "rng" )] |
424 | pub fn new_random() -> Self { |
425 | Self { |
426 | count: Atomic::<u16>::new(crate::rng::u16()), |
427 | } |
428 | } |
429 | } |
430 | |
431 | #[cfg (any(feature = "v1" , feature = "v6" ))] |
432 | impl ClockSequence for Context { |
433 | type Output = u16; |
434 | |
435 | fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output { |
436 | // RFC4122 reserves 2 bits of the clock sequence so the actual |
437 | // maximum value is smaller than `u16::MAX`. Since we unconditionally |
438 | // increment the clock sequence we want to wrap once it becomes larger |
439 | // than what we can represent in a "u14". Otherwise there'd be patches |
440 | // where the clock sequence doesn't change regardless of the timestamp |
441 | self.count.fetch_add(1, Ordering::AcqRel) % (u16::MAX >> 2) |
442 | } |
443 | } |
444 | } |
445 | |
446 | #[cfg (all(test, any(feature = "v1" , feature = "v6" )))] |
447 | mod tests { |
448 | use super::*; |
449 | |
450 | #[cfg (all( |
451 | target_arch = "wasm32" , |
452 | target_vendor = "unknown" , |
453 | target_os = "unknown" |
454 | ))] |
455 | use wasm_bindgen_test::*; |
456 | |
457 | #[test ] |
458 | #[cfg_attr ( |
459 | all( |
460 | target_arch = "wasm32" , |
461 | target_vendor = "unknown" , |
462 | target_os = "unknown" |
463 | ), |
464 | wasm_bindgen_test |
465 | )] |
466 | fn rfc4122_unix_does_not_panic() { |
467 | // Ensure timestamp conversions never panic |
468 | Timestamp::unix_to_rfc4122_ticks(u64::MAX, 0); |
469 | Timestamp::unix_to_rfc4122_ticks(0, u32::MAX); |
470 | Timestamp::unix_to_rfc4122_ticks(u64::MAX, u32::MAX); |
471 | |
472 | Timestamp::rfc4122_to_unix(u64::MAX); |
473 | } |
474 | } |
475 | |