helix_graph_algorithms/
identity.rs

1use std::collections::{BTreeMap, BTreeSet};
2use std::fmt;
3
4use serde::{Deserialize, Deserializer, Serialize, Serializer};
5use serde_json::Value;
6
7use crate::GraphError;
8
9const ENVELOPE: &str = "__helix_external_id_v1";
10const MAX_DEPTH: usize = 64;
11const MAX_ENCODED_LEN: usize = 64 * 1024;
12
13/// Lossless, deterministically ordered external graph identity.
14#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
15pub enum ExternalId {
16    Null,
17    Boolean(bool),
18    /// Canonical arbitrary-precision decimal integer.
19    Integer(String),
20    /// Exact IEEE-754 bit representation.
21    Float(u64),
22    String(String),
23    Bytes(Vec<u8>),
24    Tuple(Vec<Self>),
25    FrozenSet(BTreeSet<Self>),
26}
27
28impl ExternalId {
29    /// Borrow the payload when this identity is a string.
30    pub fn as_string(&self) -> Option<&str> {
31        match self {
32            Self::String(value) => Some(value),
33            Self::Null
34            | Self::Boolean(_)
35            | Self::Integer(_)
36            | Self::Float(_)
37            | Self::Bytes(_)
38            | Self::Tuple(_)
39            | Self::FrozenSet(_) => None,
40        }
41    }
42
43    /// Construct a validated arbitrary-precision integer identity.
44    pub fn integer(value: impl Into<String>) -> Result<Self, GraphError> {
45        let value = value.into();
46        validate_integer(&value)?;
47        Ok(Self::Integer(value))
48    }
49
50    /// Construct an exact floating-point identity.
51    pub const fn float(value: f64) -> Self {
52        Self::Float(value.to_bits())
53    }
54
55    /// Construct a tuple identity and validate nesting/size limits.
56    pub fn tuple(values: Vec<Self>) -> Result<Self, GraphError> {
57        let value = Self::Tuple(values);
58        value.validate()?;
59        Ok(value)
60    }
61
62    /// Construct a canonical frozen-set identity.
63    pub fn frozen_set(values: impl IntoIterator<Item = Self>) -> Result<Self, GraphError> {
64        let value = Self::FrozenSet(values.into_iter().collect());
65        value.validate()?;
66        Ok(value)
67    }
68
69    /// Validate canonical payloads and resource bounds.
70    pub fn validate(&self) -> Result<(), GraphError> {
71        self.validate_depth(0)?;
72        let encoded = serde_json::to_vec(&self.tagged_value())
73            .map_err(|error| GraphError::InvalidExternalId(error.to_string()))?;
74        if encoded.len() > MAX_ENCODED_LEN {
75            return Err(GraphError::InvalidExternalId(format!(
76                "encoded identity exceeds {MAX_ENCODED_LEN} bytes"
77            )));
78        }
79        Ok(())
80    }
81
82    /// Encode the canonical tagged JSON envelope used by bindings and stored
83    /// tagged identity properties.
84    pub fn to_json_bytes(&self) -> Result<Vec<u8>, GraphError> {
85        self.validate()?;
86        serde_json::to_vec(&self.tagged_value())
87            .map_err(|error| GraphError::InvalidExternalId(error.to_string()))
88    }
89
90    /// Decode one canonical tagged JSON envelope.
91    pub fn from_tagged_value(value: Value) -> Result<Self, GraphError> {
92        let Value::Object(mut outer) = value else {
93            return Err(invalid("tagged identity must be an object"));
94        };
95        if outer.len() != 1 {
96            return Err(invalid(
97                "tagged identity must contain exactly one envelope key",
98            ));
99        }
100        let Some(payload) = outer.remove(ENVELOPE) else {
101            return Err(invalid("missing tagged identity envelope"));
102        };
103        let Value::Object(mut payload) = payload else {
104            return Err(invalid("tagged identity payload must be an object"));
105        };
106        let Some(Value::String(kind)) = payload.remove("type") else {
107            return Err(invalid("tagged identity type must be a string"));
108        };
109        let value = payload.remove("value");
110        if !payload.is_empty() {
111            return Err(invalid("tagged identity payload contains unknown fields"));
112        }
113        let identity = match (kind.as_str(), value) {
114            ("null", None) => Self::Null,
115            ("boolean", Some(Value::Bool(value))) => Self::Boolean(value),
116            ("integer", Some(Value::String(value))) => Self::integer(value)?,
117            ("float", Some(Value::String(value))) => {
118                if value.len() != 16
119                    || value.bytes().any(|byte| byte.is_ascii_uppercase())
120                    || !value.bytes().all(|byte| byte.is_ascii_hexdigit())
121                {
122                    return Err(invalid("float identity must contain 16 hexadecimal digits"));
123                }
124                Self::Float(
125                    u64::from_str_radix(&value, 16)
126                        .map_err(|_| invalid("invalid float identity bits"))?,
127                )
128            }
129            ("string", Some(Value::String(value))) => Self::String(value),
130            ("bytes", Some(Value::String(value))) => Self::Bytes(decode_hex(&value)?),
131            ("tuple", Some(Value::Array(values))) => Self::Tuple(
132                values
133                    .into_iter()
134                    .map(Self::from_tagged_value)
135                    .collect::<Result<_, _>>()?,
136            ),
137            ("frozenset", Some(Value::Array(values))) => {
138                let values = values
139                    .into_iter()
140                    .map(Self::from_tagged_value)
141                    .collect::<Result<Vec<_>, _>>()?;
142                let set = values.iter().cloned().collect::<BTreeSet<_>>();
143                if set.len() != values.len() || !values.windows(2).all(|pair| pair[0] < pair[1]) {
144                    return Err(invalid("frozenset identity must be sorted and unique"));
145                }
146                Self::FrozenSet(set)
147            }
148            ("null", Some(_)) => return Err(invalid("null identity must not contain a value")),
149            _ => return Err(invalid("invalid tagged identity type or value")),
150        };
151        identity.validate()?;
152        Ok(identity)
153    }
154
155    /// Convert an ordinary JSON scalar without erasing its type.
156    pub fn from_scalar(value: Value) -> Result<Self, GraphError> {
157        let identity = match value {
158            Value::Null => Self::Null,
159            Value::Bool(value) => Self::Boolean(value),
160            Value::String(value) => Self::String(value),
161            Value::Number(value) if value.is_i64() || value.is_u64() => {
162                Self::integer(value.to_string())?
163            }
164            Value::Number(value) => Self::float(
165                value
166                    .as_f64()
167                    .ok_or_else(|| invalid("identity number cannot be represented as f64"))?,
168            ),
169            Value::Array(_) | Value::Object(_) => {
170                return Err(invalid("scalar identity must not be an array or object"));
171            }
172        };
173        identity.validate()?;
174        Ok(identity)
175    }
176
177    fn validate_depth(&self, depth: usize) -> Result<(), GraphError> {
178        if depth > MAX_DEPTH {
179            return Err(invalid(format!(
180                "identity nesting exceeds {MAX_DEPTH} levels"
181            )));
182        }
183        match self {
184            Self::Integer(value) => validate_integer(value),
185            Self::Tuple(values) => values
186                .iter()
187                .try_for_each(|value| value.validate_depth(depth + 1)),
188            Self::FrozenSet(values) => values
189                .iter()
190                .try_for_each(|value| value.validate_depth(depth + 1)),
191            Self::Null | Self::Boolean(_) | Self::Float(_) | Self::String(_) | Self::Bytes(_) => {
192                Ok(())
193            }
194        }
195    }
196
197    fn tagged_value(&self) -> Value {
198        let (kind, value) = match self {
199            Self::Null => ("null", None),
200            Self::Boolean(value) => ("boolean", Some(Value::Bool(*value))),
201            Self::Integer(value) => ("integer", Some(Value::String(value.clone()))),
202            Self::Float(bits) => ("float", Some(Value::String(format!("{bits:016x}")))),
203            Self::String(value) => ("string", Some(Value::String(value.clone()))),
204            Self::Bytes(value) => ("bytes", Some(Value::String(encode_hex(value)))),
205            Self::Tuple(values) => (
206                "tuple",
207                Some(Value::Array(
208                    values.iter().map(Self::tagged_value).collect(),
209                )),
210            ),
211            Self::FrozenSet(values) => (
212                "frozenset",
213                Some(Value::Array(
214                    values.iter().map(Self::tagged_value).collect(),
215                )),
216            ),
217        };
218        let mut payload = BTreeMap::from([("type".to_string(), Value::String(kind.to_string()))]);
219        if let Some(value) = value {
220            payload.insert("value".to_string(), value);
221        }
222        Value::Object(serde_json::Map::from_iter([(
223            ENVELOPE.to_string(),
224            Value::Object(payload.into_iter().collect()),
225        )]))
226    }
227}
228
229impl Serialize for ExternalId {
230    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
231    where
232        S: Serializer,
233    {
234        self.tagged_value().serialize(serializer)
235    }
236}
237
238impl<'de> Deserialize<'de> for ExternalId {
239    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
240    where
241        D: Deserializer<'de>,
242    {
243        let value = Value::deserialize(deserializer)?;
244        let identity = if value
245            .as_object()
246            .is_some_and(|object| object.contains_key(ENVELOPE))
247        {
248            Self::from_tagged_value(value)
249        } else {
250            Self::from_scalar(value)
251        };
252        identity.map_err(serde::de::Error::custom)
253    }
254}
255
256impl fmt::Display for ExternalId {
257    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
258        formatter.write_str(&serde_json::to_string(&self.tagged_value()).map_err(|_| fmt::Error)?)
259    }
260}
261
262impl From<String> for ExternalId {
263    fn from(value: String) -> Self {
264        Self::String(value)
265    }
266}
267
268impl From<&str> for ExternalId {
269    fn from(value: &str) -> Self {
270        Self::String(value.to_string())
271    }
272}
273
274impl From<&String> for ExternalId {
275    fn from(value: &String) -> Self {
276        Self::String(value.clone())
277    }
278}
279
280impl From<&ExternalId> for ExternalId {
281    fn from(value: &ExternalId) -> Self {
282        value.clone()
283    }
284}
285
286impl From<bool> for ExternalId {
287    fn from(value: bool) -> Self {
288        Self::Boolean(value)
289    }
290}
291
292impl From<i64> for ExternalId {
293    fn from(value: i64) -> Self {
294        Self::Integer(value.to_string())
295    }
296}
297
298impl From<u64> for ExternalId {
299    fn from(value: u64) -> Self {
300        Self::Integer(value.to_string())
301    }
302}
303
304impl From<f64> for ExternalId {
305    fn from(value: f64) -> Self {
306        Self::float(value)
307    }
308}
309
310impl PartialEq<&str> for ExternalId {
311    fn eq(&self, other: &&str) -> bool {
312        matches!(self, Self::String(value) if value == *other)
313    }
314}
315
316impl PartialEq<String> for ExternalId {
317    fn eq(&self, other: &String) -> bool {
318        matches!(self, Self::String(value) if value == other)
319    }
320}
321
322/// Property selected as a graph identity source.
323#[derive(Debug, Clone, PartialEq, Eq)]
324pub struct GraphProperty(String);
325
326impl GraphProperty {
327    pub fn new(value: impl Into<String>) -> Result<Self, GraphError> {
328        let value = value.into();
329        if value.is_empty() {
330            return Err(GraphError::InvalidExternalId(
331                "identity property must not be empty".to_string(),
332            ));
333        }
334        Ok(Self(value))
335    }
336
337    pub fn as_str(&self) -> &str {
338        &self.0
339    }
340}
341
342/// Explicit node identity selection contract.
343#[derive(Debug, Clone, PartialEq, Eq)]
344pub enum IdentitySelection {
345    InternalId,
346    ScalarProperty(GraphProperty),
347    TaggedProperty(GraphProperty),
348}
349
350impl IdentitySelection {
351    pub fn property(&self) -> Option<&GraphProperty> {
352        match self {
353            Self::InternalId => None,
354            Self::ScalarProperty(property) | Self::TaggedProperty(property) => Some(property),
355        }
356    }
357
358    pub const fn is_tagged(&self) -> bool {
359        matches!(self, Self::TaggedProperty(_))
360    }
361}
362
363fn validate_integer(value: &str) -> Result<(), GraphError> {
364    let digits = value.strip_prefix('-').unwrap_or(value);
365    let canonical = !digits.is_empty()
366        && digits.bytes().all(|byte| byte.is_ascii_digit())
367        && (digits == "0" || !digits.starts_with('0'))
368        && value != "-0";
369    if canonical {
370        Ok(())
371    } else {
372        Err(invalid("integer identity is not canonical decimal"))
373    }
374}
375
376fn encode_hex(bytes: &[u8]) -> String {
377    const DIGITS: &[u8; 16] = b"0123456789abcdef";
378    let mut encoded = String::with_capacity(bytes.len() * 2);
379    for byte in bytes {
380        encoded.push(DIGITS[(byte >> 4) as usize] as char);
381        encoded.push(DIGITS[(byte & 0x0f) as usize] as char);
382    }
383    encoded
384}
385
386fn decode_hex(value: &str) -> Result<Vec<u8>, GraphError> {
387    if value.len() % 2 != 0 || !value.bytes().all(|byte| byte.is_ascii_hexdigit()) {
388        return Err(invalid(
389            "bytes identity must contain lowercase hexadecimal pairs",
390        ));
391    }
392    if value.bytes().any(|byte| byte.is_ascii_uppercase()) {
393        return Err(invalid("bytes identity hexadecimal must be lowercase"));
394    }
395    value
396        .as_bytes()
397        .chunks_exact(2)
398        .map(|pair| {
399            let text = std::str::from_utf8(pair).expect("hexadecimal is ASCII");
400            u8::from_str_radix(text, 16).map_err(|_| invalid("invalid bytes identity"))
401        })
402        .collect()
403}
404
405fn invalid(message: impl Into<String>) -> GraphError {
406    GraphError::InvalidExternalId(message.into())
407}
408
409#[cfg(test)]
410mod tests {
411    use super::*;
412
413    #[test]
414    fn tagged_round_trip_preserves_every_identity_variant() {
415        let values = [
416            ExternalId::Null,
417            ExternalId::Boolean(true),
418            ExternalId::integer("123456789012345678901234567890").unwrap(),
419            ExternalId::float(-0.0),
420            ExternalId::String(String::new()),
421            ExternalId::Bytes(vec![0, 1, 255]),
422            ExternalId::tuple(vec![ExternalId::from(1_i64), ExternalId::from("1")]).unwrap(),
423            ExternalId::frozen_set([ExternalId::from("b"), ExternalId::from("a")]).unwrap(),
424        ];
425        for value in values {
426            let encoded = value.to_json_bytes().unwrap();
427            assert_eq!(
428                serde_json::from_slice::<ExternalId>(&encoded).unwrap(),
429                value
430            );
431        }
432    }
433
434    #[test]
435    fn identity_types_do_not_collide_and_invalid_canonical_forms_fail() {
436        assert_ne!(ExternalId::from(1_i64), ExternalId::from("1"));
437        assert_ne!(ExternalId::from(true), ExternalId::from("true"));
438        assert_ne!(ExternalId::float(0.0), ExternalId::float(-0.0));
439        assert!(ExternalId::integer("01").is_err());
440        assert!(ExternalId::integer("-0").is_err());
441        assert!(serde_json::from_value::<ExternalId>(serde_json::json!({
442            (ENVELOPE): {"type": "bytes", "value": "FF"}
443        }))
444        .is_err());
445    }
446
447    #[test]
448    fn scalar_and_selection_contracts_cover_every_variant() {
449        let property = GraphProperty::new("identity").unwrap();
450        assert_eq!(property.as_str(), "identity");
451        assert!(matches!(
452            GraphProperty::new(""),
453            Err(GraphError::InvalidExternalId(_))
454        ));
455
456        let internal = IdentitySelection::InternalId;
457        assert_eq!(internal.property(), None);
458        assert!(!internal.is_tagged());
459        let scalar = IdentitySelection::ScalarProperty(property.clone());
460        assert_eq!(scalar.property(), Some(&property));
461        assert!(!scalar.is_tagged());
462        let tagged = IdentitySelection::TaggedProperty(property.clone());
463        assert_eq!(tagged.property(), Some(&property));
464        assert!(tagged.is_tagged());
465
466        assert_eq!(
467            ExternalId::from_scalar(Value::Null).unwrap(),
468            ExternalId::Null
469        );
470        assert_eq!(
471            ExternalId::from_scalar(Value::Bool(false)).unwrap(),
472            ExternalId::Boolean(false)
473        );
474        assert_eq!(
475            ExternalId::from_scalar(Value::String("identity".to_string())).unwrap(),
476            "identity"
477        );
478        assert_eq!(
479            ExternalId::from_scalar(serde_json::json!(42)).unwrap(),
480            ExternalId::from(42_u64)
481        );
482        assert_eq!(
483            ExternalId::from_scalar(serde_json::json!(1.5)).unwrap(),
484            ExternalId::from(1.5_f64)
485        );
486        assert!(ExternalId::from_scalar(serde_json::json!([])).is_err());
487        assert!(ExternalId::from_scalar(serde_json::json!({})).is_err());
488
489        let owned = "owned".to_string();
490        let borrowed = ExternalId::from(&owned);
491        assert_eq!(borrowed.as_string(), Some("owned"));
492        assert_eq!(ExternalId::from(&borrowed), borrowed);
493        assert_eq!(borrowed, owned);
494        for value in [
495            ExternalId::Null,
496            ExternalId::Boolean(false),
497            ExternalId::from(1_u64),
498            ExternalId::from(1.0_f64),
499            ExternalId::Bytes(Vec::new()),
500            ExternalId::tuple(Vec::new()).unwrap(),
501            ExternalId::frozen_set([]).unwrap(),
502        ] {
503            assert_eq!(value.as_string(), None);
504        }
505    }
506
507    #[test]
508    fn tagged_decoder_rejects_every_noncanonical_envelope_shape() {
509        let invalid_values = [
510            serde_json::json!(null),
511            serde_json::json!({(ENVELOPE): {"type": "null"}, "extra": null}),
512            serde_json::json!({"wrong": {"type": "null"}}),
513            serde_json::json!({(ENVELOPE): null}),
514            serde_json::json!({(ENVELOPE): {"value": null}}),
515            serde_json::json!({(ENVELOPE): {"type": 1}}),
516            serde_json::json!({(ENVELOPE): {"type": "null", "unknown": true}}),
517            serde_json::json!({(ENVELOPE): {"type": "float", "value": "0"}}),
518            serde_json::json!({(ENVELOPE): {"type": "float", "value": "000000000000000A"}}),
519            serde_json::json!({(ENVELOPE): {"type": "float", "value": "000000000000000g"}}),
520            serde_json::json!({(ENVELOPE): {"type": "bytes", "value": "0"}}),
521            serde_json::json!({(ENVELOPE): {"type": "bytes", "value": "gg"}}),
522            serde_json::json!({(ENVELOPE): {"type": "bytes", "value": "FF"}}),
523            serde_json::json!({
524                (ENVELOPE): {
525                    "type": "frozenset",
526                    "value": [
527                        {(ENVELOPE): {"type": "string", "value": "b"}},
528                        {(ENVELOPE): {"type": "string", "value": "a"}}
529                    ]
530                }
531            }),
532            serde_json::json!({
533                (ENVELOPE): {
534                    "type": "frozenset",
535                    "value": [
536                        {(ENVELOPE): {"type": "string", "value": "a"}},
537                        {(ENVELOPE): {"type": "string", "value": "a"}}
538                    ]
539                }
540            }),
541            serde_json::json!({(ENVELOPE): {"type": "null", "value": null}}),
542            serde_json::json!({(ENVELOPE): {"type": "unknown"}}),
543            serde_json::json!({(ENVELOPE): {"type": "boolean", "value": "false"}}),
544        ];
545        for value in invalid_values {
546            assert!(matches!(
547                ExternalId::from_tagged_value(value),
548                Err(GraphError::InvalidExternalId(_))
549            ));
550        }
551    }
552
553    #[test]
554    fn identity_resource_bounds_return_typed_errors() {
555        let nested =
556            (0..=MAX_DEPTH).fold(ExternalId::Null, |value, _| ExternalId::Tuple(vec![value]));
557        assert!(matches!(
558            nested.validate(),
559            Err(GraphError::InvalidExternalId(message))
560                if message.contains("nesting exceeds")
561        ));
562
563        let oversized = ExternalId::String("x".repeat(MAX_ENCODED_LEN));
564        assert!(matches!(
565            oversized.validate(),
566            Err(GraphError::InvalidExternalId(message))
567                if message.contains("encoded identity exceeds")
568        ));
569    }
570}
helix_graph_algorithms/identity.rs

helix_graph_algorithms/
identity.rs
