dialcache/
identity.rs

1//! Logical identities, shared cache keys and rollout cohorts.
2//!
3//! Key construction follows the portable protocol (W01–W03): URI component
4//! escaping, tracked entity hash tags, ordered argument pairs, the frame key
5//! suffix, and FNV-1a cohorts over UTF-16 code units.
6
7use std::borrow::Cow;
8use std::cmp::Ordering;
9use std::fmt::Write as _;
10
11use crate::limits::FRAME_KEY_SUFFIX;
12
13/// Converts an entity identifier to the text used in a cache key.
14///
15/// Strings are preserved, integers use exact decimal notation, and floats use
16/// JavaScript `String(number)` spelling (`f32` is promoted to `f64`). Shared
17/// references to these types are also accepted. For other displayable IDs,
18/// pass `id.to_string()` or implement this trait with the desired spelling.
19pub trait IntoKeyId {
20    /// Consume the identifier and return its canonical text.
21    fn into_key_id(self) -> String;
22}
23
24impl IntoKeyId for String {
25    fn into_key_id(self) -> String {
26        self
27    }
28}
29
30impl IntoKeyId for &str {
31    fn into_key_id(self) -> String {
32        self.to_owned()
33    }
34}
35
36impl IntoKeyId for Box<str> {
37    fn into_key_id(self) -> String {
38        self.into_string()
39    }
40}
41
42impl IntoKeyId for Cow<'_, str> {
43    fn into_key_id(self) -> String {
44        self.into_owned()
45    }
46}
47
48impl IntoKeyId for char {
49    fn into_key_id(self) -> String {
50        self.to_string()
51    }
52}
53
54impl<T: IntoKeyId + Clone> IntoKeyId for &T {
55    fn into_key_id(self) -> String {
56        self.clone().into_key_id()
57    }
58}
59
60macro_rules! integer_key_id {
61    ($($t:ty),*) => { $(impl IntoKeyId for $t {
62        fn into_key_id(self) -> String { self.to_string() }
63    })* };
64}
65integer_key_id!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
66
67impl IntoKeyId for f64 {
68    fn into_key_id(self) -> String {
69        js_number_to_string(self)
70    }
71}
72
73impl IntoKeyId for f32 {
74    fn into_key_id(self) -> String {
75        js_number_to_string(f64::from(self))
76    }
77}
78
79/// A normalized logical identity. Ordered arguments retain caller order;
80/// use [`normalize_args`] to build them from a host-language record.
81#[derive(Debug, Clone, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
82pub struct Identity {
83    /// The instance namespace; empty means the cache fills in its own at execution.
84    #[serde(default)]
85    pub namespace: String,
86    /// The entity type; serialized as `keyType`.
87    #[serde(rename = "keyType")]
88    pub key_type: String,
89    /// The entity identifier.
90    pub id: String,
91    /// The operation name; serialized as `useCase`.
92    #[serde(rename = "useCase")]
93    pub use_case: String,
94    /// Whether the identity is fenced by its entity's invalidation watermark;
95    /// serialized as `trackForInvalidation`. Defaults to false.
96    #[serde(rename = "trackForInvalidation", default)]
97    pub tracked: bool,
98    /// Secondary dimensions as `(name, spelled value)` pairs, already
99    /// normalized and in key order.
100    #[serde(default)]
101    pub args: Vec<(String, String)>,
102}
103
104impl Identity {
105    /// An untracked identity with an empty namespace and no arguments.
106    /// IDs use the same [`IntoKeyId`] conversion as [`crate::KeySpec::new`]
107    /// and [`crate::DialCache::invalidate`].
108    pub fn new(
109        key_type: impl Into<String>,
110        id: impl IntoKeyId,
111        use_case: impl Into<String>,
112    ) -> Self {
113        Identity {
114            namespace: String::new(),
115            key_type: key_type.into(),
116            id: id.into_key_id(),
117            use_case: use_case.into(),
118            tracked: false,
119            args: Vec::new(),
120        }
121    }
122
123    /// Set whether the identity shares its entity's invalidation watermark.
124    pub fn tracked(mut self, tracked: bool) -> Self {
125        self.tracked = tracked;
126        self
127    }
128
129    /// Set the namespace explicitly instead of inheriting the instance's.
130    pub fn namespace(mut self, namespace: impl Into<String>) -> Self {
131        self.namespace = namespace.into();
132        self
133    }
134
135    /// Replace the ordered argument pairs; build them with [`normalize_args`].
136    pub fn args(mut self, args: Vec<(String, String)>) -> Self {
137        self.args = args;
138        self
139    }
140
141    /// The logical key, the stored value key and, for tracked identities, the watermark key.
142    pub fn keys(&self) -> Result<Keys, IdentityError> {
143        keys(self)
144    }
145}
146
147/// Derived key strings of one identity.
148#[derive(Debug, Clone, PartialEq, Eq)]
149pub struct Keys {
150    /// Logical key: `namespace:keyType:id[?args]#useCase`, hash-tagged when tracked.
151    pub logical: String,
152    /// Stored value key: the logical key plus the frame suffix.
153    pub value: String,
154    /// Entity watermark key for tracked identities.
155    pub watermark: Option<String>,
156}
157
158/// Why an identity cannot form a key.
159#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
160pub enum IdentityError {
161    /// A component contains `{` or `}` where it would form the Redis Cluster
162    /// hash tag: the namespace always, the key type and ID when tracked.
163    #[error("DialCache identity component contains a reserved hash-tag delimiter")]
164    ReservedDelimiter,
165    /// An argument value cannot be spelled; the text names the offending value.
166    #[error("DialCache identity contains an unsupported argument value: {0}")]
167    UnsupportedArgument(String),
168}
169
170/// A host scalar accepted as a key argument.
171#[derive(Debug, Clone, PartialEq)]
172pub enum ArgValue {
173    /// Omitted from the key (JavaScript `undefined`).
174    Absent,
175    /// JSON null, spelled `null`.
176    Null,
177    /// Spelled `true` or `false`.
178    Bool(bool),
179    /// Spelled with JavaScript `Number` formatting.
180    Number(f64),
181    /// Spelled as a decimal integer.
182    Int(i64),
183    /// An arbitrary-precision integer as decimal text.
184    BigInt(String),
185    /// Used verbatim, then percent-escaped like every other component.
186    Str(String),
187}
188
189impl ArgValue {
190    /// The JavaScript `String(value)` spelling, or `None` for an absent value.
191    fn spell(self) -> Result<Option<String>, IdentityError> {
192        Ok(Some(match self {
193            ArgValue::Absent => return Ok(None),
194            ArgValue::Null => "null".to_owned(),
195            ArgValue::Bool(value) => if value { "true" } else { "false" }.to_owned(),
196            ArgValue::Number(value) => js_number_to_string(value),
197            ArgValue::Int(value) => value.to_string(),
198            ArgValue::BigInt(text) => {
199                if !is_decimal_integer(&text) {
200                    return Err(IdentityError::UnsupportedArgument(format!(
201                        "bigint text {text:?} is not a decimal integer"
202                    )));
203                }
204                text
205            }
206            ArgValue::Str(text) => text,
207        }))
208    }
209}
210
211fn is_decimal_integer(text: &str) -> bool {
212    let digits = text.strip_prefix('-').unwrap_or(text);
213    !digits.is_empty() && digits.bytes().all(|byte| byte.is_ascii_digit())
214}
215
216/// Normalize a record of key arguments: omit absent values, spell scalars
217/// the JavaScript way, and sort names by UTF-16 code units.
218///
219/// The sort is stable, so entries whose names compare equal keep their input order.
220pub fn normalize_args<I, K>(args: I) -> Result<Vec<(String, String)>, IdentityError>
221where
222    I: IntoIterator<Item = (K, ArgValue)>,
223    K: Into<String>,
224{
225    let mut pairs = Vec::new();
226    for (name, value) in args {
227        if let Some(text) = value.spell()? {
228            pairs.push((name.into(), text));
229        }
230    }
231    pairs.sort_by(|left, right| compare_utf16(&left.0, &right.0));
232    Ok(pairs)
233}
234
235fn contains_brace(component: &str) -> bool {
236    component.contains(['{', '}'])
237}
238
239/// Build every key of an identity.
240///
241/// The namespace may never contain a hash-tag brace. The key type and ID
242/// are restricted the same way only when the identity is tracked, because
243/// only then do they form the Redis Cluster hash tag; untracked braces are
244/// percent-escaped like any other reserved character.
245pub fn keys(identity: &Identity) -> Result<Keys, IdentityError> {
246    if contains_brace(&identity.namespace)
247        || (identity.tracked
248            && (contains_brace(&identity.key_type) || contains_brace(&identity.id)))
249    {
250        return Err(IdentityError::ReservedDelimiter);
251    }
252    let entity = format!(
253        "{}:{}:{}",
254        escape_component(&identity.namespace),
255        escape_component(&identity.key_type),
256        escape_component(&identity.id)
257    );
258    let (mut logical, watermark) = if identity.tracked {
259        let tagged = format!("{{{entity}}}");
260        let watermark = format!("{tagged}#watermark");
261        (tagged, Some(watermark))
262    } else {
263        (entity, None)
264    };
265    for (index, (name, value)) in identity.args.iter().enumerate() {
266        logical.push(if index == 0 { '?' } else { '&' });
267        logical.push_str(&escape_component(name));
268        logical.push('=');
269        logical.push_str(&escape_component(value));
270    }
271    logical.push('#');
272    logical.push_str(&escape_component(&identity.use_case));
273    let value = format!("{logical}{FRAME_KEY_SUFFIX}");
274    Ok(Keys {
275        logical,
276        value,
277        watermark,
278    })
279}
280
281/// `encodeURIComponent` escaping of one component.
282///
283/// Bytes of the UTF-8 encoding are kept literally when they are
284/// `A-Z a-z 0-9 - _ . ! ~ * ' ( )` and percent-encoded with uppercase hex otherwise.
285pub fn escape_component(component: &str) -> String {
286    let mut escaped = String::with_capacity(component.len());
287    for byte in component.bytes() {
288        if byte.is_ascii_alphanumeric() || b"-_.!~*'()".contains(&byte) {
289            escaped.push(byte as char);
290        } else {
291            let _ = write!(escaped, "%{byte:02X}");
292        }
293    }
294    escaped
295}
296
297/// FNV-1a 32-bit hash over the UTF-16 code units of `logical_key:discriminator`;
298/// the integer numerator behind [`cohort`].
299pub fn cohort_hash(logical_key: &str, discriminator: &str) -> u32 {
300    let units = logical_key
301        .encode_utf16()
302        .chain(":".encode_utf16())
303        .chain(discriminator.encode_utf16());
304    units.fold(0x811c_9dc5_u32, |hash, unit| {
305        (hash ^ u32::from(unit)).wrapping_mul(0x0100_0193)
306    })
307}
308
309/// Deterministic rollout sample in `[0, 100)` for a logical key and layer or
310/// shadow discriminator: FNV-1a over the UTF-16 units of `key:discriminator`.
311pub fn cohort(logical_key: &str, discriminator: &str) -> f64 {
312    f64::from(cohort_hash(logical_key, discriminator)) / 4_294_967_296.0 * 100.0
313}
314
315/// Spell a number the way JavaScript's `String(number)` does.
316///
317/// This is ECMA-262 `Number::toString(10)`: the shortest digit string that
318/// round-trips, laid out as plain decimal for exponents in `(-7, 21]` and as
319/// `d.ddde±X` otherwise. Negative zero spells `0`.
320pub fn js_number_to_string(value: f64) -> String {
321    // Rust's standard shortest formatter rounds some decimal ties away from
322    // zero; ECMAScript chooses the even significand. Those spellings are part
323    // of the shared key identity, so use the ECMAScript variant of Ryū.
324    ryu_js::Buffer::new().format(value).to_owned()
325}
326
327/// Compare two strings by UTF-16 code units, as JavaScript's `<` does.
328pub fn compare_utf16(left: &str, right: &str) -> Ordering {
329    left.encode_utf16().cmp(right.encode_utf16())
330}
331
332#[cfg(test)]
333mod tests {
334    use super::*;
335
336    #[test]
337    fn js_numbers_follow_ecmascript_spelling() {
338        let cases: &[(f64, &str)] = &[
339            (f64::NAN, "NaN"),
340            (f64::INFINITY, "Infinity"),
341            (f64::NEG_INFINITY, "-Infinity"),
342            (0.0, "0"),
343            (-0.0, "0"),
344            (1.5, "1.5"),
345            (-1.5, "-1.5"),
346            (100.0, "100"),
347            (1e21, "1e+21"),
348            (1e-7, "1e-7"),
349            (-1e-7, "-1e-7"),
350            (0.000001, "0.000001"),
351            (123456789012345680000.0, "123456789012345680000"),
352            (9007199254740991.0, "9007199254740991"),
353            (1.25, "1.25"),
354            (0.1, "0.1"),
355            (1.2345e-7, "1.2345e-7"),
356            (1.5e300, "1.5e+300"),
357            (5e-324, "5e-324"),
358            (f64::MAX, "1.7976931348623157e+308"),
359            (0.5, "0.5"),
360            (123.456, "123.456"),
361            (1e20, "100000000000000000000"),
362            // Exact binary fractions whose shortest decimal candidates tie.
363            (f64::from_bits(0x430c6bf526340002), "1000000000000000.2"),
364            (f64::from_bits(0xc30c6bf526340002), "-1000000000000000.2"),
365            (f64::from_bits(0x430c6bf526340006), "1000000000000000.8"),
366            (f64::from_bits(0xc30c6bf526340006), "-1000000000000000.8"),
367            (f64::from_bits(0x42d6bcc41e900008), "100000000000000.12"),
368            (f64::from_bits(0x42d6bcc41e900018), "100000000000000.38"),
369        ];
370        for (value, expected) in cases {
371            assert_eq!(
372                js_number_to_string(*value),
373                *expected,
374                "spelling of {value:?}"
375            );
376        }
377    }
378
379    #[test]
380    fn escaping_matches_encode_uri_component() {
381        assert_eq!(escape_component("é"), "%C3%A9");
382        assert_eq!(escape_component("😀"), "%F0%9F%98%80");
383        assert_eq!(escape_component("~!*'()-._"), "~!*'()-._");
384        assert_eq!(
385            escape_component("a b+c/d?e=f&g#h%"),
386            "a%20b%2Bc%2Fd%3Fe%3Df%26g%23h%25"
387        );
388        assert_eq!(escape_component("{1}"), "%7B1%7D");
389        assert_eq!(escape_component(""), "");
390    }
391
392    #[test]
393    fn utf16_ordering_places_astral_before_private_use() {
394        assert_eq!(compare_utf16("😀", "\u{e000}"), Ordering::Less);
395        assert_eq!(compare_utf16("\u{ffff}", "😀"), Ordering::Greater);
396        assert_eq!(compare_utf16("a", "ab"), Ordering::Less);
397        assert_eq!(compare_utf16("b", "ab"), Ordering::Greater);
398        assert_eq!(compare_utf16("", ""), Ordering::Equal);
399    }
400
401    #[test]
402    fn normalization_spells_scalars_and_sorts_names() {
403        let normalized = normalize_args(vec![
404            ("z", ArgValue::Str("last".into())),
405            ("missing", ArgValue::Absent),
406            ("a", ArgValue::Int(1)),
407            ("nil", ArgValue::Null),
408            ("flag", ArgValue::Bool(false)),
409            ("wide", ArgValue::BigInt("-9007199254740993".into())),
410            ("tiny", ArgValue::Number(1e-7)),
411        ])
412        .unwrap();
413        let expected: Vec<(String, String)> = [
414            ("a", "1"),
415            ("flag", "false"),
416            ("nil", "null"),
417            ("tiny", "1e-7"),
418            ("wide", "-9007199254740993"),
419            ("z", "last"),
420        ]
421        .into_iter()
422        .map(|(name, value)| (name.to_owned(), value.to_owned()))
423        .collect();
424        assert_eq!(normalized, expected);
425    }
426
427    #[test]
428    fn malformed_bigint_text_is_rejected() {
429        for text in ["", "-", "1.5", "0x10", "1e3", "+1", "１"] {
430            assert!(
431                matches!(
432                    normalize_args(vec![("n", ArgValue::BigInt(text.into()))]),
433                    Err(IdentityError::UnsupportedArgument(_))
434                ),
435                "bigint text {text:?} should be rejected"
436            );
437        }
438    }
439
440    #[test]
441    fn braces_are_reserved_only_where_they_form_a_hash_tag() {
442        let untracked = Identity::new("{kind}", "{1}", "Get").namespace("urn");
443        assert_eq!(
444            untracked.keys().unwrap().logical,
445            "urn:%7Bkind%7D:%7B1%7D#Get"
446        );
447        assert_eq!(
448            untracked.clone().tracked(true).keys(),
449            Err(IdentityError::ReservedDelimiter)
450        );
451        assert_eq!(
452            Identity::new("k", "1", "Get").namespace("bad{ns").keys(),
453            Err(IdentityError::ReservedDelimiter)
454        );
455        let tracked = Identity::new("user_id", "123", "GetUser")
456            .namespace("users-api")
457            .tracked(true)
458            .args(vec![("locale".into(), "en".into())]);
459        let keys = tracked.keys().unwrap();
460        assert_eq!(keys.logical, "{users-api:user_id:123}?locale=en#GetUser");
461        assert_eq!(
462            keys.value,
463            "{users-api:user_id:123}?locale=en#GetUser:dialcache-frame-v1"
464        );
465        assert_eq!(
466            keys.watermark.as_deref(),
467            Some("{users-api:user_id:123}#watermark")
468        );
469    }
470
471    #[test]
472    fn cohort_is_fnv1a_over_utf16_units() {
473        assert_eq!(cohort_hash("urn:id:1#Get", "local"), 1_652_509_740);
474        assert_eq!(cohort("urn:id:1#Get", "local"), 38.475490640848875);
475        assert_eq!(cohort_hash("", ""), {
476            let mut hash = 0x811c_9dc5_u32;
477            hash ^= u32::from(b':');
478            hash.wrapping_mul(0x0100_0193)
479        });
480    }
481}
dialcache/identity.rs

dialcache/
identity.rs
