grafeo_common/types/
validity.rs

1//! Reverse-ordered validity timestamp for versioned storage.
2//!
3//! When used as a key component in disk-backed storage, the reverse ordering
4//! ensures most-recent versions appear first in sorted key order, enabling
5//! efficient "get latest version at epoch X" queries with a single range scan.
6
7use std::cmp::{Ordering, Reverse};
8
9/// Reverse-ordered validity timestamp for efficient disk-storage scans.
10///
11/// Wraps a signed 64-bit timestamp with reversed ordering so that
12/// newer timestamps sort before older ones in byte-ordered storage.
13///
14/// # Key Encoding
15///
16/// Use [`versioned_key`](Self::versioned_key) to produce a 16-byte key
17/// combining an entity ID with a validity timestamp. The entity ID sorts
18/// in natural order, while the timestamp sorts in reverse order within
19/// each entity, so a forward scan returns the newest version first.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
21pub struct ValidityTs(Reverse<i64>);
22
23impl ValidityTs {
24    /// Creates a new validity timestamp.
25    #[must_use]
26    pub fn new(ts: i64) -> Self {
27        Self(Reverse(ts))
28    }
29
30    /// Returns a sentinel value representing "always current."
31    ///
32    /// Uses `i64::MAX` so it sorts before every real timestamp in
33    /// reverse order.
34    #[must_use]
35    pub fn current() -> Self {
36        Self(Reverse(i64::MAX))
37    }
38
39    /// Returns the underlying timestamp value.
40    #[must_use]
41    pub fn timestamp(&self) -> i64 {
42        self.0.0
43    }
44
45    /// Encodes an entity ID and validity timestamp into a 16-byte key.
46    ///
47    /// Layout: `[entity_id: 8 bytes BE][timestamp: 8 bytes BE]`
48    ///
49    /// Because `ValidityTs` uses `Reverse<i64>`, the timestamp bytes
50    /// are the raw `i64` in big-endian. To get reverse-sorted timestamps
51    /// in byte order, callers should negate or bitwise-complement the
52    /// timestamp before creating the `ValidityTs`. For a simpler approach,
53    /// use `i64::MAX - epoch` as the timestamp value.
54    #[must_use]
55    pub fn versioned_key(entity_id: u64, ts: Self) -> [u8; 16] {
56        let mut key = [0u8; 16];
57        key[..8].copy_from_slice(&entity_id.to_be_bytes());
58        key[8..].copy_from_slice(&ts.0.0.to_be_bytes());
59        key
60    }
61
62    /// Decodes entity ID and timestamp from a 16-byte versioned key.
63    ///
64    /// Returns `(entity_id, ValidityTs)`.
65    ///
66    /// # Panics
67    ///
68    /// Panics if the byte slices cannot be converted to fixed-size arrays
69    /// (cannot happen for a `&[u8; 16]` input).
70    #[must_use]
71    pub fn from_versioned_key(key: &[u8; 16]) -> (u64, Self) {
72        let entity_id = u64::from_be_bytes(
73            key[..8]
74                .try_into()
75                .expect("first 8 bytes of a [u8; 16] are always a valid [u8; 8]"),
76        );
77        let ts = i64::from_be_bytes(
78            key[8..]
79                .try_into()
80                .expect("last 8 bytes of a [u8; 16] are always a valid [u8; 8]"),
81        );
82        (entity_id, Self::new(ts))
83    }
84}
85
86impl Ord for ValidityTs {
87    fn cmp(&self, other: &Self) -> Ordering {
88        self.0.cmp(&other.0)
89    }
90}
91
92impl PartialOrd for ValidityTs {
93    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
94        Some(self.cmp(other))
95    }
96}
97
98impl From<i64> for ValidityTs {
99    fn from(ts: i64) -> Self {
100        Self::new(ts)
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn test_reverse_ordering() {
110        let ts1 = ValidityTs::new(10);
111        let ts2 = ValidityTs::new(20);
112
113        // Reverse ordering: higher timestamp sorts first (is "less")
114        assert!(ts2 < ts1);
115        assert!(ts1 > ts2);
116    }
117
118    #[test]
119    fn test_current_sentinel() {
120        let current = ValidityTs::current();
121        let recent = ValidityTs::new(1_000_000);
122
123        // Current sorts before everything (smallest in reverse order)
124        assert!(current < recent);
125        assert_eq!(current.timestamp(), i64::MAX);
126    }
127
128    #[test]
129    fn test_versioned_key_roundtrip() {
130        let entity_id = 42u64;
131        let ts = ValidityTs::new(12345);
132
133        let key = ValidityTs::versioned_key(entity_id, ts);
134        let (decoded_id, decoded_ts) = ValidityTs::from_versioned_key(&key);
135
136        assert_eq!(decoded_id, entity_id);
137        assert_eq!(decoded_ts, ts);
138    }
139
140    #[test]
141    fn test_versioned_key_entity_ordering() {
142        // Keys with different entity IDs: entity order is preserved
143        let key1 = ValidityTs::versioned_key(1, ValidityTs::new(100));
144        let key2 = ValidityTs::versioned_key(2, ValidityTs::new(100));
145
146        assert!(key1 < key2);
147    }
148
149    #[test]
150    fn test_equality() {
151        let ts1 = ValidityTs::new(42);
152        let ts2 = ValidityTs::new(42);
153        let ts3 = ValidityTs::new(43);
154
155        assert_eq!(ts1, ts2);
156        assert_ne!(ts1, ts3);
157    }
158
159    #[test]
160    fn test_from_i64() {
161        let ts: ValidityTs = 42i64.into();
162        assert_eq!(ts.timestamp(), 42);
163    }
164}
grafeo_common/types/validity.rs

grafeo_common/types/
validity.rs
