reddb_engine/storage/
ordered_secondary_key.rs

1//! Version-one ordered projection for native secondary trees.
2//!
3//! Explicit family tags follow CanonicalKey's order. Signed numbers flip their
4//! sign bit; floats use the reversible total_cmp transform. Variable fields
5//! escape zero as 00 ff and terminate with 00 00. Thus complete keys are prefix
6//! free, including when physical IDs are appended or fixed-arity tuples are
7//! formed by concatenation. No record payload, heap buffer or network is needed:
8//! encoding costs O(key bytes), with output bounded by the caller's scratch.
9use super::error::StoreError;
10use reddb_types::{CanonicalKey, CanonicalKeyFamily};
11
12#[derive(Clone, Copy, PartialEq, Eq)]
13enum Shape {
14    Null,
15    Boolean,
16    Signed,
17    Unsigned,
18    Float,
19    Text,
20    Bytes,
21    TextU64,
22    TextText,
23    U32U8,
24    U32U32,
25    I32I32,
26}
27
28// These tags are a durable codec contract, never enum-discriminant casts.
29fn family_encoding(family: CanonicalKeyFamily) -> (u8, Shape) {
30    use CanonicalKeyFamily as F;
31    match family {
32        F::Null => (0, Shape::Null),
33        F::Boolean => (1, Shape::Boolean),
34        F::Integer => (2, Shape::Signed),
35        F::BigInt => (3, Shape::Signed),
36        F::UnsignedInteger => (4, Shape::Unsigned),
37        F::Float => (5, Shape::Float),
38        F::Text => (6, Shape::Text),
39        F::Blob => (7, Shape::Bytes),
40        F::Timestamp => (8, Shape::Signed),
41        F::Duration => (9, Shape::Signed),
42        F::IpAddr => (10, Shape::Bytes),
43        F::MacAddr => (11, Shape::Bytes),
44        F::Json => (12, Shape::Bytes),
45        F::Uuid => (13, Shape::Bytes),
46        F::NodeRef => (14, Shape::Text),
47        F::EdgeRef => (15, Shape::Text),
48        F::VectorRef => (16, Shape::TextU64),
49        F::RowRef => (17, Shape::TextU64),
50        F::Color => (18, Shape::Bytes),
51        F::Email => (19, Shape::Text),
52        F::Url => (20, Shape::Text),
53        F::Phone => (21, Shape::Unsigned),
54        F::Semver => (22, Shape::Unsigned),
55        F::Cidr => (23, Shape::U32U8),
56        F::Date => (24, Shape::Signed),
57        F::Time => (25, Shape::Unsigned),
58        F::Decimal => (26, Shape::Signed),
59        F::EnumValue => (27, Shape::Unsigned),
60        F::TimestampMs => (28, Shape::Signed),
61        F::Ipv4 => (29, Shape::Bytes),
62        F::Ipv6 => (30, Shape::Bytes),
63        F::Subnet => (31, Shape::U32U32),
64        F::Port => (32, Shape::Unsigned),
65        F::Latitude => (33, Shape::Signed),
66        F::Longitude => (34, Shape::Signed),
67        F::GeoPoint => (35, Shape::I32I32),
68        F::Country2 => (36, Shape::Bytes),
69        F::Country3 => (37, Shape::Bytes),
70        F::Lang2 => (38, Shape::Bytes),
71        F::Lang5 => (39, Shape::Bytes),
72        F::Currency => (40, Shape::Bytes),
73        F::ColorAlpha => (41, Shape::Bytes),
74        F::KeyRef => (42, Shape::TextText),
75        F::DocRef => (43, Shape::TextU64),
76        F::TableRef => (44, Shape::Text),
77        F::PageRef => (45, Shape::Unsigned),
78        F::Password => (46, Shape::Text),
79    }
80}
81
82fn escaped_length(bytes: &[u8]) -> usize {
83    bytes
84        .len()
85        .saturating_add(bytes.iter().filter(|byte| **byte == 0).count())
86        .saturating_add(2)
87}
88
89fn payload_shape_length(key: &CanonicalKey) -> (Shape, usize) {
90    use CanonicalKey as K;
91    match key {
92        K::Null => (Shape::Null, 0),
93        K::Boolean(_) => (Shape::Boolean, 1),
94        K::Signed(..) => (Shape::Signed, 8),
95        K::Unsigned(..) => (Shape::Unsigned, 8),
96        K::Float(_) => (Shape::Float, 8),
97        K::Text(_, text) => (Shape::Text, escaped_length(text.as_bytes())),
98        K::Bytes(_, bytes) => (Shape::Bytes, escaped_length(bytes)),
99        K::PairTextU64(_, text, _) => (
100            Shape::TextU64,
101            escaped_length(text.as_bytes()).saturating_add(8),
102        ),
103        K::PairTextText(_, left, right) => (
104            Shape::TextText,
105            escaped_length(left.as_bytes()).saturating_add(escaped_length(right.as_bytes())),
106        ),
107        K::PairU32U8(..) => (Shape::U32U8, 5),
108        K::PairU32U32(..) => (Shape::U32U32, 8),
109        K::PairI32I32(..) => (Shape::I32I32, 8),
110    }
111}
112
113struct Writer<'a> {
114    output: &'a mut [u8],
115    length: usize,
116}
117
118impl Writer<'_> {
119    fn bytes(&mut self, bytes: &[u8]) {
120        let end = self.length + bytes.len();
121        self.output[self.length..end].copy_from_slice(bytes);
122        self.length = end;
123    }
124
125    fn escaped(&mut self, bytes: &[u8]) {
126        for byte in bytes {
127            self.bytes(&[*byte]);
128            if *byte == 0 {
129                self.bytes(&[255]);
130            }
131        }
132        self.bytes(&[0, 0]);
133    }
134}
135
136/// Encode without allocating. Capacity and family errors leave output intact.
137/// Concatenate encodings only for tuples of fixed arity in the same index.
138/// Persisted projection identities must include this codec's version (1).
139pub fn encode_ordered_key(key: &CanonicalKey, output: &mut [u8]) -> Result<usize, StoreError> {
140    let (tag, expected_shape) = family_encoding(key.family());
141    let (shape, payload_length) = payload_shape_length(key);
142    if shape != expected_shape {
143        return Err(StoreError::Serialization(
144            "ordered key family/value mismatch".into(),
145        ));
146    }
147    let required_bytes = payload_length.saturating_add(1);
148    if required_bytes > output.len() {
149        return Err(StoreError::ReadLimitExceeded {
150            required_bytes,
151            limit_bytes: output.len(),
152        });
153    }
154    let mut writer = Writer { output, length: 0 };
155    writer.bytes(&[tag]);
156    use CanonicalKey as K;
157    match key {
158        K::Null => {}
159        K::Boolean(value) => writer.bytes(&[u8::from(*value)]),
160        K::Signed(_, value) => {
161            writer.bytes(&(u64::from_ne_bytes(value.to_ne_bytes()) ^ (1 << 63)).to_be_bytes())
162        }
163        K::Unsigned(_, value) => writer.bytes(&value.to_be_bytes()),
164        K::Float(bits) => {
165            let ordered = if bits & (1 << 63) != 0 {
166                !bits
167            } else {
168                bits ^ (1 << 63)
169            };
170            writer.bytes(&ordered.to_be_bytes());
171        }
172        K::Text(_, text) => writer.escaped(text.as_bytes()),
173        K::Bytes(_, bytes) => writer.escaped(bytes),
174        K::PairTextU64(_, text, value) => {
175            writer.escaped(text.as_bytes());
176            writer.bytes(&value.to_be_bytes());
177        }
178        K::PairTextText(_, left, right) => {
179            writer.escaped(left.as_bytes());
180            writer.escaped(right.as_bytes());
181        }
182        K::PairU32U8(_, left, right) => {
183            writer.bytes(&left.to_be_bytes());
184            writer.bytes(&[*right]);
185        }
186        K::PairU32U32(_, left, right) => {
187            writer.bytes(&left.to_be_bytes());
188            writer.bytes(&right.to_be_bytes());
189        }
190        K::PairI32I32(_, left, right) => {
191            writer.bytes(&(u32::from_ne_bytes(left.to_ne_bytes()) ^ (1 << 31)).to_be_bytes());
192            writer.bytes(&(u32::from_ne_bytes(right.to_ne_bytes()) ^ (1 << 31)).to_be_bytes());
193        }
194    }
195    assert_eq!(
196        writer.length, required_bytes,
197        "ordered key size matches admitted scratch"
198    );
199    Ok(writer.length)
200}
reddb_engine/storage/ordered_secondary_key.rs

reddb_engine/storage/
ordered_secondary_key.rs
