ic_memory/
key.rs

1use serde::{Deserialize, Deserializer, Serialize, de::Error as _};
2use std::{fmt, str::FromStr};
3
4const MAX_KEY_BYTES: usize = 128;
5
6///
7/// StableKey
8///
9/// Canonical durable logical allocation identity.
10///
11/// A stable key names the logical store, not the current storage backend or
12/// `MemoryManager` ID. Once committed, the key is permanently bound to its
13/// physical allocation slot; changing the key declares a new logical store.
14///
15/// Construction and deserialization enforce the same bounded canonical grammar.
16/// A checked key establishes identity syntax, not allocation or open authority.
17///
18
19#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize)]
20pub struct StableKey(String);
21
22impl<'de> Deserialize<'de> for StableKey {
23    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
24        // Retain the serialized newtype shape before checking its owned text.
25        #[derive(Deserialize)]
26        #[serde(rename = "StableKey")]
27        struct Text(String);
28
29        let Text(value) = Text::deserialize(deserializer)?;
30        validate(&value).map_err(D::Error::custom)?;
31        Ok(Self(value))
32    }
33}
34
35impl StableKey {
36    /// Parse and validate a canonical stable key string.
37    ///
38    /// Keys are bounded lowercase ASCII dot-separated names ending in a
39    /// nonzero `.vN` suffix.
40    pub fn parse(value: impl AsRef<str>) -> Result<Self, StableKeyError> {
41        let value = value.as_ref();
42        validate(value)?;
43        Ok(Self(value.to_string()))
44    }
45
46    /// Borrow the canonical stable-key string.
47    #[must_use]
48    pub fn as_str(&self) -> &str {
49        &self.0
50    }
51
52    /// Consume the key and return the canonical stable-key string.
53    #[must_use]
54    pub fn into_string(self) -> String {
55        self.0
56    }
57}
58
59impl AsRef<str> for StableKey {
60    fn as_ref(&self) -> &str {
61        self.as_str()
62    }
63}
64
65impl fmt::Display for StableKey {
66    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
67        formatter.write_str(self.as_str())
68    }
69}
70
71impl FromStr for StableKey {
72    type Err = StableKeyError;
73
74    fn from_str(value: &str) -> Result<Self, Self::Err> {
75        Self::parse(value)
76    }
77}
78
79///
80/// StableKeyError
81///
82/// Stable-key grammar validation failure.
83#[derive(Clone, Debug, Eq, thiserror::Error, PartialEq)]
84#[error("stable key '{stable_key}' is invalid: {reason}")]
85pub struct StableKeyError {
86    /// Rejected stable-key string.
87    pub stable_key: String,
88    /// Stable-key grammar failure.
89    pub reason: &'static str,
90}
91
92pub fn validate(stable_key: &str) -> Result<(), StableKeyError> {
93    if stable_key.is_empty() {
94        return invalid(stable_key, "must not be empty");
95    }
96    if stable_key.len() > MAX_KEY_BYTES {
97        return invalid(stable_key, "must be at most 128 bytes");
98    }
99    if !stable_key.is_ascii() {
100        return invalid(stable_key, "must be ASCII");
101    }
102    if stable_key.bytes().any(|byte| byte.is_ascii_uppercase()) {
103        return invalid(stable_key, "must be lowercase");
104    }
105    if stable_key
106        .bytes()
107        .any(|byte| matches!(byte, b'\t'..=b'\r' | b' '))
108    {
109        return invalid(stable_key, "must not contain whitespace");
110    }
111    if stable_key.bytes().any(|byte| matches!(byte, b'/' | b'-')) {
112        return invalid(stable_key, "must not contain slashes or hyphens");
113    }
114    if stable_key.starts_with('.') || stable_key.ends_with('.') {
115        return invalid(stable_key, "must not start or end with a dot");
116    }
117
118    let Some(version_index) = stable_key
119        .as_bytes()
120        .windows(2)
121        .rposition(|pair| pair == b".v")
122    else {
123        return invalid(stable_key, "must end with .vN");
124    };
125    let version = &stable_key[version_index + 2..];
126    if version.is_empty()
127        || version.starts_with('0')
128        || !version.bytes().all(|byte| byte.is_ascii_digit())
129    {
130        return invalid(stable_key, "version suffix must be nonzero .vN");
131    }
132
133    let prefix = &stable_key[..version_index];
134    if prefix.is_empty() {
135        return invalid(
136            stable_key,
137            "must contain at least one segment before version",
138        );
139    }
140
141    for segment in prefix.as_bytes().split(|byte| *byte == b'.') {
142        if let Err(reason) = validate_segment(segment) {
143            return invalid(stable_key, reason);
144        }
145    }
146
147    Ok(())
148}
149
150// A namespace plus its synthetic `v1` suffix must fit the same key grammar.
151// Borrow the prefix rather than allocating a temporary key just to discard it.
152pub fn is_key_prefix(value: &str) -> bool {
153    let Some(prefix) = value.strip_suffix('.') else {
154        return false;
155    };
156    value.len() <= MAX_KEY_BYTES - "v1".len()
157        && prefix
158            .as_bytes()
159            .split(|byte| *byte == b'.')
160            .all(|segment| validate_segment(segment).is_ok())
161}
162
163fn validate_segment(segment: &[u8]) -> Result<(), &'static str> {
164    let mut bytes = segment.iter().copied();
165    let Some(first) = bytes.next() else {
166        return Err("must not contain empty segments");
167    };
168    if !first.is_ascii_lowercase() {
169        return Err("segments must start with a lowercase letter");
170    }
171    if !bytes.all(|byte| byte.is_ascii_lowercase() || byte.is_ascii_digit() || byte == b'_') {
172        return Err("segments may contain only lowercase letters, digits, and underscores");
173    }
174    Ok(())
175}
176
177fn invalid<T>(stable_key: &str, reason: &'static str) -> Result<T, StableKeyError> {
178    Err(StableKeyError {
179        stable_key: stable_key.to_string(),
180        reason,
181    })
182}
183
184/// Mark later occurrences while preserving each boundary's original traversal.
185/// Callers bound the collection and supply its enumerated input positions.
186pub fn duplicate_key_positions(
187    mut keys: Vec<(&StableKey, usize)>,
188) -> [bool; crate::constants::MAX_ALLOCATIONS] {
189    crate::sort::sort_unstable_by(&mut keys, Ord::cmp);
190    let mut duplicates = [false; crate::constants::MAX_ALLOCATIONS];
191    for pair in keys.windows(2) {
192        if pair[0].0 == pair[1].0 {
193            duplicates[pair[1].1] = true;
194        }
195    }
196    duplicates
197}
198
199#[cfg(test)]
200mod tests {
201    use super::*;
202
203    #[test]
204    fn parse_stores_the_string_it_validates() {
205        struct ChangingKey(std::cell::Cell<bool>);
206
207        impl AsRef<str> for ChangingKey {
208            fn as_ref(&self) -> &str {
209                if self.0.replace(true) {
210                    "INVALID"
211                } else {
212                    "app.rows.v1"
213                }
214            }
215        }
216
217        let key = StableKey::parse(ChangingKey(std::cell::Cell::new(false))).unwrap();
218        assert_eq!(key.as_str(), "app.rows.v1");
219    }
220
221    #[test]
222    fn uniqueness_errors_follow_input_order_and_boundary_precedence() {
223        use crate::{AllocationDeclaration, DeclarationSnapshot, DeclarationSnapshotError};
224        let duplicate = StableKey::parse("app.b.v1").unwrap();
225        for slots in [[10, 11, 12, 13], [10, 11, 10, 13]] {
226            let declarations: Vec<_> = ["app.a.v1", "app.b.v1", "app.b.v1", "app.a.v1"]
227                .into_iter()
228                .zip(slots)
229                .map(|(key, slot)| {
230                    AllocationDeclaration::memory_manager_unlabeled(key, slot).unwrap()
231                })
232                .collect();
233            let expected = if slots[2] == slots[0] {
234                DeclarationSnapshotError::DuplicateSlot(crate::MemoryManagerSlot::new(10).unwrap())
235            } else {
236                DeclarationSnapshotError::DuplicateStableKey(duplicate.clone())
237            };
238            assert_eq!(
239                DeclarationSnapshot::new(declarations.clone()).unwrap_err(),
240                expected
241            );
242            let ledger = crate::AllocationLedger {
243                current_generation: 1,
244                records: declarations
245                    .iter()
246                    .map(crate::AllocationRecord::active)
247                    .collect(),
248            };
249            assert_eq!(
250                ledger.validate_integrity(),
251                Err(crate::LedgerIntegrityError::DuplicateStableKey {
252                    stable_key: duplicate.clone(),
253                })
254            );
255        }
256    }
257
258    #[test]
259    fn accepts_canonical_keys() {
260        assert_eq!(
261            StableKey::parse("app.users.primary.v1")
262                .expect("valid key")
263                .as_str(),
264            "app.users.primary.v1"
265        );
266        assert!(StableKey::parse("framework.core.auth_state.v12").is_ok());
267        assert!(StableKey::parse("app.vault.v1").is_ok());
268        assert!(StableKey::parse("app.v1.v2").is_ok());
269    }
270
271    #[test]
272    fn key_decode_enforces_grammar_and_preserves_current_encoding() {
273        let key = StableKey::parse("app.users.v1").unwrap();
274        let json = serde_json::to_string(&key).unwrap();
275        assert_eq!(json, "\"app.users.v1\"");
276        assert_eq!(serde_json::from_str::<StableKey>(&json).unwrap(), key);
277        let bytes = crate::test_cbor::to_vec(&key).unwrap();
278        assert_eq!(bytes, b"\x6capp.users.v1");
279        assert_eq!(
280            crate::test_cbor::from_slice::<StableKey>(&bytes).unwrap(),
281            key
282        );
283
284        for invalid in [
285            "App.users.v1",
286            "app.users.v0",
287            "app.vault",
288            "app.users.v1.tail",
289            "app..users.v1",
290            &"x".repeat(129),
291        ] {
292            let json = serde_json::to_string(invalid).unwrap();
293            assert!(serde_json::from_str::<StableKey>(&json).is_err());
294            let bytes = crate::test_cbor::to_vec(&invalid).unwrap();
295            assert!(crate::test_cbor::from_slice::<StableKey>(&bytes).is_err());
296        }
297    }
298
299    #[test]
300    fn whitespace_rejection_preserves_input_and_precedence() {
301        for whitespace in [' ', '\t', '\n', '\u{b}', '\u{c}', '\r'] {
302            let key = format!("app.us{whitespace}ers.v1");
303            assert_eq!(
304                StableKey::parse(&key),
305                Err(StableKeyError {
306                    stable_key: key,
307                    reason: "must not contain whitespace",
308                })
309            );
310        }
311        for (key, reason) in [
312            ("app.us\u{a0}ers.v1", "must be ASCII"),
313            ("App.us\u{b}ers.v1", "must be lowercase"),
314        ] {
315            assert_eq!(StableKey::parse(key).unwrap_err().reason, reason);
316        }
317    }
318
319    #[test]
320    fn rejects_noncanonical_keys() {
321        for key in [
322            "",
323            "App.users.v1",
324            "app.users",
325            "app.users.v0",
326            "app..users.v1",
327            ".app.users.v1",
328            "app.users.v1.",
329            "app-users.v1",
330            "app/users.v1",
331            "app.1users.v1",
332        ] {
333            assert!(StableKey::parse(key).is_err(), "{key} should fail");
334        }
335    }
336}
ic_memory/key.rs

ic_memory/
key.rs
