haste_fhir_search/pg_search/
keys.rs

1//! Hashed keys that scope rows in the search tables.
2//!
3//! Each key is SHA-256 over length-prefixed parts, truncated to 64 bits.
4//! Stored rows carry these values, so changing the hash requires a full
5//! reindex.
6//!
7//! Collisions are mostly harmless: searches filter the anchor on its real
8//! `tenant`/`project` columns and join other tables by the unique `res_key`, so
9//! a collision only makes an index scan read rows that get discarded. The one
10//! harmful case, two parameters in one project sharing an identity, is caught
11//! by [`check_identities`].
12
13use std::collections::HashMap;
14
15use sha2::{Digest, Sha256};
16
17/// Scope of a resource type table row (one tenant's project). Leads every
18/// index on those tables.
19#[must_use]
20pub fn scope_key(tenant: &str, project: &str) -> i64 {
21    hash_parts(&[b"scope", tenant.as_bytes(), project.as_bytes()])
22}
23
24/// Identifies a parameter's rows in the shared tables, in place of its URL.
25#[must_use]
26pub fn param_identity(tenant: &str, project: &str, param_url: &str) -> i64 {
27    hash_parts(&[
28        b"param",
29        tenant.as_bytes(),
30        project.as_bytes(),
31        param_url.as_bytes(),
32    ])
33}
34
35/// Fails if two distinct `param_urls` hash to the same identity.
36///
37/// # Errors
38///
39/// Returns the two colliding URLs.
40pub fn check_identities<'a>(
41    tenant: &str,
42    project: &str,
43    param_urls: impl IntoIterator<Item = &'a str>,
44) -> Result<(), (String, String)> {
45    param_urls
46        .into_iter()
47        .try_fold(HashMap::<i64, &str>::new(), |mut seen, url| {
48            match seen.insert(param_identity(tenant, project, url), url) {
49                Some(existing) if existing != url => Err((existing.to_string(), url.to_string())),
50                _ => Ok(seen),
51            }
52        })
53        .map(|_| ())
54}
55
56/// Length-prefixes each part, so `("ab", "c")` and `("a", "bc")` differ.
57fn hash_parts(parts: &[&[u8]]) -> i64 {
58    let digest = parts
59        .iter()
60        .fold(Sha256::new(), |hasher, part| {
61            hasher
62                .chain_update((part.len() as u64).to_be_bytes())
63                .chain_update(part)
64        })
65        .finalize();
66
67    let mut first = [0u8; 8];
68    first.copy_from_slice(&digest[..8]);
69    i64::from_be_bytes(first)
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    /// Stored rows carry these values, so they must be deterministic.
77    #[test]
78    fn hashes_are_stable() {
79        assert_eq!(scope_key("t", "p"), scope_key("t", "p"));
80        assert_eq!(
81            param_identity("t", "p", "http://hl7.org/fhir/SearchParameter/Patient-name"),
82            param_identity("t", "p", "http://hl7.org/fhir/SearchParameter/Patient-name"),
83        );
84    }
85
86    #[test]
87    fn part_boundaries_are_part_of_the_input() {
88        assert_ne!(scope_key("ab", "c"), scope_key("a", "bc"));
89        assert_ne!(
90            param_identity("t", "pa", "b"),
91            param_identity("t", "p", "ab")
92        );
93    }
94
95    #[test]
96    fn identities_are_scoped_to_the_project() {
97        let url = "http://hl7.org/fhir/SearchParameter/Patient-name";
98        assert_ne!(
99            param_identity("t", "p1", url),
100            param_identity("t", "p2", url)
101        );
102        assert_ne!(
103            param_identity("t1", "p", url),
104            param_identity("t2", "p", url)
105        );
106    }
107
108    #[test]
109    fn scopes_and_identities_do_not_share_a_space() {
110        assert_ne!(scope_key("t", "p"), param_identity("t", "p", ""));
111    }
112
113    #[test]
114    fn repeated_urls_are_not_collisions() {
115        assert!(check_identities("t", "p", ["a", "b", "a"]).is_ok());
116    }
117}
haste_fhir_search/pg_search/keys.rs

haste_fhir_search/pg_search/
keys.rs
