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    #[must_use]
66    pub fn from_versioned_key(key: &[u8; 16]) -> (u64, Self) {
67        let entity_id = u64::from_be_bytes(
68            key[..8]
69                .try_into()
70                .expect("first 8 bytes of a [u8; 16] are always a valid [u8; 8]"),
71        );
72        let ts = i64::from_be_bytes(
73            key[8..]
74                .try_into()
75                .expect("last 8 bytes of a [u8; 16] are always a valid [u8; 8]"),
76        );
77        (entity_id, Self::new(ts))
78    }
79}
80
81impl Ord for ValidityTs {
82    fn cmp(&self, other: &Self) -> Ordering {
83        self.0.cmp(&other.0)
84    }
85}
86
87impl PartialOrd for ValidityTs {
88    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
89        Some(self.cmp(other))
90    }
91}
92
93impl From<i64> for ValidityTs {
94    fn from(ts: i64) -> Self {
95        Self::new(ts)
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_reverse_ordering() {
105        let ts1 = ValidityTs::new(10);
106        let ts2 = ValidityTs::new(20);
107
108        // Reverse ordering: higher timestamp sorts first (is "less")
109        assert!(ts2 < ts1);
110        assert!(ts1 > ts2);
111    }
112
113    #[test]
114    fn test_current_sentinel() {
115        let current = ValidityTs::current();
116        let recent = ValidityTs::new(1_000_000);
117
118        // Current sorts before everything (smallest in reverse order)
119        assert!(current < recent);
120        assert_eq!(current.timestamp(), i64::MAX);
121    }
122
123    #[test]
124    fn test_versioned_key_roundtrip() {
125        let entity_id = 42u64;
126        let ts = ValidityTs::new(12345);
127
128        let key = ValidityTs::versioned_key(entity_id, ts);
129        let (decoded_id, decoded_ts) = ValidityTs::from_versioned_key(&key);
130
131        assert_eq!(decoded_id, entity_id);
132        assert_eq!(decoded_ts, ts);
133    }
134
135    #[test]
136    fn test_versioned_key_entity_ordering() {
137        // Keys with different entity IDs: entity order is preserved
138        let key1 = ValidityTs::versioned_key(1, ValidityTs::new(100));
139        let key2 = ValidityTs::versioned_key(2, ValidityTs::new(100));
140
141        assert!(key1 < key2);
142    }
143
144    #[test]
145    fn test_equality() {
146        let ts1 = ValidityTs::new(42);
147        let ts2 = ValidityTs::new(42);
148        let ts3 = ValidityTs::new(43);
149
150        assert_eq!(ts1, ts2);
151        assert_ne!(ts1, ts3);
152    }
153
154    #[test]
155    fn test_from_i64() {
156        let ts: ValidityTs = 42i64.into();
157        assert_eq!(ts.timestamp(), 42);
158    }
159}
grafeo_common/types/validity.rs

grafeo_common/types/
validity.rs
