ic_memory/
key.rs

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

ic_memory/
key.rs
