cedar_policy_core/ast/
entity.rs

1/*
2 * Copyright Cedar Contributors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17use crate::ast::*;
18use crate::entities::{
19    err::{EntitiesError, InvalidEntityStructureError},
20    json::{err::JsonSerializationError, is_reserved_key},
21    EntityJson,
22};
23use crate::evaluator::{EvaluationError, RestrictedEvaluator};
24use crate::extensions::Extensions;
25use crate::parser::err::ParseErrors;
26use crate::parser::Loc;
27use crate::transitive_closure::TCNode;
28use crate::FromNormalizedStr;
29use educe::Educe;
30use itertools::Itertools;
31use miette::Diagnostic;
32use serde::{de::Deserializer, ser::Serializer, Deserialize, Serialize};
33use smol_str::SmolStr;
34use std::collections::{BTreeMap, HashSet};
35use std::str::FromStr;
36use std::sync::Arc;
37use thiserror::Error;
38
39#[cfg(feature = "tolerant-ast")]
40static ERROR_NAME: std::sync::LazyLock<Name> = std::sync::LazyLock::new(|| {
41    Name(InternalName::from(Id::new_unchecked_const(
42        "EntityTypeError",
43    )))
44});
45
46#[cfg(feature = "tolerant-ast")]
47static EID_ERROR_STR: &str = "Eid::Error";
48
49#[cfg(feature = "tolerant-ast")]
50static ENTITY_TYPE_ERROR_STR: &str = "EntityType::Error";
51
52#[cfg(feature = "tolerant-ast")]
53static ENTITY_UID_ERROR_STR: &str = "EntityUID::Error";
54
55/// The entity type that Actions must have
56pub static ACTION_ENTITY_TYPE: &str = "Action";
57
58#[derive(PartialEq, Eq, Debug, Clone, Hash, PartialOrd, Ord)]
59#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
60/// Entity type - can be an error type when 'tolerant-ast' feature is enabled
61pub enum EntityType {
62    /// Entity type names are just [`Name`]s, but we have some operations on them specific to entity types.
63    EntityType(Name),
64    #[cfg(feature = "tolerant-ast")]
65    /// Represents an error node of an entity that failed to parse
66    ErrorEntityType,
67}
68
69impl<'de> Deserialize<'de> for EntityType {
70    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
71    where
72        D: Deserializer<'de>,
73    {
74        let name = Name::deserialize(deserializer)?;
75        Ok(EntityType::EntityType(name))
76    }
77}
78
79impl Serialize for EntityType {
80    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
81    where
82        S: Serializer,
83    {
84        match self {
85            EntityType::EntityType(name) => name.serialize(serializer),
86            #[cfg(feature = "tolerant-ast")]
87            EntityType::ErrorEntityType => serializer.serialize_str(ENTITY_TYPE_ERROR_STR),
88        }
89    }
90}
91
92impl EntityType {
93    /// Is this an Action entity type?
94    /// Returns true when an entity type is an action entity type. This compares the
95    /// base name for the type, so this will return true for any entity type named
96    /// `Action` regardless of namespaces.
97    pub fn is_action(&self) -> bool {
98        match self {
99            EntityType::EntityType(name) => {
100                name.as_ref().basename() == &Id::new_unchecked_const(ACTION_ENTITY_TYPE)
101            }
102            #[cfg(feature = "tolerant-ast")]
103            EntityType::ErrorEntityType => false,
104        }
105    }
106
107    /// The name of this entity type
108    pub fn name(&self) -> &Name {
109        match self {
110            EntityType::EntityType(name) => name,
111            #[cfg(feature = "tolerant-ast")]
112            EntityType::ErrorEntityType => &ERROR_NAME,
113        }
114    }
115
116    /// Consumes this entity type and returns the owned name. Clones the statically defined name
117    /// for entity errors when this entity type is ErrorEntityType.
118    pub fn into_name(self) -> Name {
119        match self {
120            EntityType::EntityType(name) => name,
121            #[cfg(feature = "tolerant-ast")]
122            EntityType::ErrorEntityType => ERROR_NAME.clone(),
123        }
124    }
125
126    /// The source location of this entity type
127    pub fn loc(&self) -> Option<&Loc> {
128        match self {
129            EntityType::EntityType(name) => name.as_ref().loc(),
130            #[cfg(feature = "tolerant-ast")]
131            EntityType::ErrorEntityType => None,
132        }
133    }
134
135    /// Create a clone of this EntityType with given loc
136    pub fn with_loc(&self, loc: Option<&Loc>) -> Self {
137        match self {
138            EntityType::EntityType(name) => EntityType::EntityType(Name(InternalName {
139                id: name.0.id.clone(),
140                path: name.0.path.clone(),
141                loc: loc.cloned(),
142            })),
143            #[cfg(feature = "tolerant-ast")]
144            EntityType::ErrorEntityType => self.clone(),
145        }
146    }
147
148    /// Calls [`Name::qualify_with_name`] on the underlying [`Name`]
149    pub fn qualify_with(&self, namespace: Option<&Name>) -> Self {
150        match self {
151            EntityType::EntityType(name) => Self::EntityType(name.qualify_with_name(namespace)),
152            #[cfg(feature = "tolerant-ast")]
153            EntityType::ErrorEntityType => Self::ErrorEntityType,
154        }
155    }
156
157    /// Wraps [`Name::from_normalized_str`]
158    pub fn from_normalized_str(src: &str) -> Result<Self, ParseErrors> {
159        Name::from_normalized_str(src).map(Into::into)
160    }
161}
162
163impl From<Name> for EntityType {
164    fn from(n: Name) -> Self {
165        Self::EntityType(n)
166    }
167}
168
169impl From<EntityType> for Name {
170    fn from(ty: EntityType) -> Name {
171        match ty {
172            EntityType::EntityType(name) => name,
173            #[cfg(feature = "tolerant-ast")]
174            EntityType::ErrorEntityType => ERROR_NAME.clone(),
175        }
176    }
177}
178
179impl AsRef<Name> for EntityType {
180    fn as_ref(&self) -> &Name {
181        match self {
182            EntityType::EntityType(name) => name,
183            #[cfg(feature = "tolerant-ast")]
184            EntityType::ErrorEntityType => &ERROR_NAME,
185        }
186    }
187}
188
189impl FromStr for EntityType {
190    type Err = ParseErrors;
191
192    fn from_str(s: &str) -> Result<Self, Self::Err> {
193        s.parse().map(Self::EntityType)
194    }
195}
196
197impl std::fmt::Display for EntityType {
198    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
199        match self {
200            EntityType::EntityType(name) => write!(f, "{name}"),
201            #[cfg(feature = "tolerant-ast")]
202            EntityType::ErrorEntityType => write!(f, "{ENTITY_TYPE_ERROR_STR}"),
203        }
204    }
205}
206
207/// Unique ID for an entity. These represent entities in the AST.
208#[derive(Educe, Serialize, Deserialize, Debug, Clone)]
209#[serde(rename = "EntityUID")]
210#[educe(PartialEq, Eq, Hash, PartialOrd, Ord)]
211pub struct EntityUIDImpl {
212    /// Typename of the entity
213    ty: EntityType,
214    /// EID of the entity
215    eid: Eid,
216    /// Location of the entity in policy source
217    #[serde(skip)]
218    #[educe(PartialEq(ignore))]
219    #[educe(Hash(ignore))]
220    #[educe(PartialOrd(ignore))]
221    #[educe(Ord(ignore))]
222    loc: Option<Loc>,
223}
224
225impl EntityUIDImpl {
226    /// The source location of this entity
227    pub fn loc(&self) -> Option<Loc> {
228        self.loc.clone()
229    }
230}
231
232/// Unique ID for an entity. These represent entities in the AST.
233#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
234pub enum EntityUID {
235    /// Unique ID for an entity. These represent entities in the AST
236    EntityUID(EntityUIDImpl),
237    #[cfg(feature = "tolerant-ast")]
238    /// Represents the ID of an error that failed to parse
239    Error,
240}
241
242impl<'de> Deserialize<'de> for EntityUID {
243    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
244    where
245        D: Deserializer<'de>,
246    {
247        let uid_impl = EntityUIDImpl::deserialize(deserializer)?;
248        Ok(EntityUID::EntityUID(uid_impl))
249    }
250}
251
252impl Serialize for EntityUID {
253    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
254    where
255        S: Serializer,
256    {
257        match self {
258            EntityUID::EntityUID(uid_impl) => uid_impl.serialize(serializer),
259            #[cfg(feature = "tolerant-ast")]
260            EntityUID::Error => serializer.serialize_str(ENTITY_UID_ERROR_STR),
261        }
262    }
263}
264
265impl StaticallyTyped for EntityUID {
266    fn type_of(&self) -> Type {
267        match self {
268            EntityUID::EntityUID(entity_uid) => Type::Entity {
269                ty: entity_uid.ty.clone(),
270            },
271            #[cfg(feature = "tolerant-ast")]
272            EntityUID::Error => Type::Entity {
273                ty: EntityType::ErrorEntityType,
274            },
275        }
276    }
277}
278
279#[cfg(test)]
280impl EntityUID {
281    /// Create an `EntityUID` with the given string as its EID.
282    /// Useful for testing.
283    pub(crate) fn with_eid(eid: &str) -> Self {
284        Self::EntityUID(EntityUIDImpl {
285            ty: Self::test_entity_type(),
286            eid: Eid::Eid(eid.into()),
287            loc: None,
288        })
289    }
290
291    /// The type of entities created with the above `with_eid()`.
292    pub(crate) fn test_entity_type() -> EntityType {
293        let name = Name::parse_unqualified_name("test_entity_type")
294            .expect("test_entity_type should be a valid identifier");
295        EntityType::EntityType(name)
296    }
297}
298
299impl EntityUID {
300    /// Create an `EntityUID` with the given (unqualified) typename, and the given string as its EID.
301    pub fn with_eid_and_type(typename: &str, eid: &str) -> Result<Self, ParseErrors> {
302        Ok(Self::EntityUID(EntityUIDImpl {
303            ty: EntityType::EntityType(Name::parse_unqualified_name(typename)?),
304            eid: Eid::Eid(eid.into()),
305            loc: None,
306        }))
307    }
308
309    /// Split into the `EntityType` representing the entity type, and the `Eid`
310    /// representing its name
311    pub fn components(self) -> (EntityType, Eid) {
312        match self {
313            EntityUID::EntityUID(entity_uid) => (entity_uid.ty, entity_uid.eid),
314            #[cfg(feature = "tolerant-ast")]
315            EntityUID::Error => (EntityType::ErrorEntityType, Eid::ErrorEid),
316        }
317    }
318
319    /// Get the source location for this `EntityUID`.
320    pub fn loc(&self) -> Option<&Loc> {
321        match self {
322            EntityUID::EntityUID(entity_uid) => entity_uid.loc.as_ref(),
323            #[cfg(feature = "tolerant-ast")]
324            EntityUID::Error => None,
325        }
326    }
327
328    /// Create an [`EntityUID`] with the given typename and [`Eid`]
329    pub fn from_components(ty: EntityType, eid: Eid, loc: Option<Loc>) -> Self {
330        Self::EntityUID(EntityUIDImpl { ty, eid, loc })
331    }
332
333    /// Get the type component.
334    pub fn entity_type(&self) -> &EntityType {
335        match self {
336            EntityUID::EntityUID(entity_uid) => &entity_uid.ty,
337            #[cfg(feature = "tolerant-ast")]
338            EntityUID::Error => &EntityType::ErrorEntityType,
339        }
340    }
341
342    /// Get the Eid component.
343    pub fn eid(&self) -> &Eid {
344        match self {
345            EntityUID::EntityUID(entity_uid) => &entity_uid.eid,
346            #[cfg(feature = "tolerant-ast")]
347            EntityUID::Error => &Eid::ErrorEid,
348        }
349    }
350
351    /// Does this EntityUID refer to an action entity?
352    pub fn is_action(&self) -> bool {
353        self.entity_type().is_action()
354    }
355}
356
357impl std::fmt::Display for EntityUID {
358    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
359        write!(f, "{}::\"{}\"", self.entity_type(), self.eid().escaped())
360    }
361}
362
363// allow `.parse()` on a string to make an `EntityUID`
364impl std::str::FromStr for EntityUID {
365    type Err = ParseErrors;
366
367    fn from_str(s: &str) -> Result<Self, Self::Err> {
368        crate::parser::parse_euid(s)
369    }
370}
371
372impl FromNormalizedStr for EntityUID {
373    fn describe_self() -> &'static str {
374        "Entity UID"
375    }
376}
377
378#[cfg(feature = "arbitrary")]
379impl<'a> arbitrary::Arbitrary<'a> for EntityUID {
380    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
381        Ok(Self::EntityUID(EntityUIDImpl {
382            ty: u.arbitrary()?,
383            eid: u.arbitrary()?,
384            loc: None,
385        }))
386    }
387}
388
389/// The `Eid` type represents the id of an `Entity`, without the typename.
390/// Together with the typename it comprises an `EntityUID`.
391/// For example, in `User::"alice"`, the `Eid` is `alice`.
392///
393/// `Eid` does not implement `Display`, partly because it is unclear whether
394/// `Display` should produce an escaped representation or an unescaped representation
395/// (see [#884](https://github.com/cedar-policy/cedar/issues/884)).
396/// To get an escaped representation, use `.escaped()`.
397/// To get an unescaped representation, use `.as_ref()`.
398#[derive(PartialEq, Eq, Debug, Clone, Hash, PartialOrd, Ord)]
399pub enum Eid {
400    /// Actual Eid
401    Eid(SmolStr),
402    #[cfg(feature = "tolerant-ast")]
403    /// Represents an Eid of an entity that failed to parse
404    ErrorEid,
405}
406
407impl<'de> Deserialize<'de> for Eid {
408    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
409    where
410        D: Deserializer<'de>,
411    {
412        let value = String::deserialize(deserializer)?;
413        Ok(Eid::Eid(SmolStr::from(value)))
414    }
415}
416
417impl Serialize for Eid {
418    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
419    where
420        S: Serializer,
421    {
422        match self {
423            Eid::Eid(s) => s.serialize(serializer),
424            #[cfg(feature = "tolerant-ast")]
425            Eid::ErrorEid => serializer.serialize_str(EID_ERROR_STR),
426        }
427    }
428}
429
430impl Eid {
431    /// Construct an Eid
432    pub fn new(eid: impl Into<SmolStr>) -> Self {
433        Eid::Eid(eid.into())
434    }
435
436    /// Get the contents of the `Eid` as an escaped string
437    pub fn escaped(&self) -> SmolStr {
438        match self {
439            Eid::Eid(smol_str) => smol_str.escape_debug().collect(),
440            #[cfg(feature = "tolerant-ast")]
441            Eid::ErrorEid => SmolStr::new_static(EID_ERROR_STR),
442        }
443    }
444
445    /// Get the underlying smolstr for this `Eid`
446    pub fn into_smolstr(self) -> SmolStr {
447        match self {
448            Eid::Eid(smol_str) => smol_str,
449            #[cfg(feature = "tolerant-ast")]
450            Eid::ErrorEid => SmolStr::new_static(EID_ERROR_STR),
451        }
452    }
453}
454
455impl AsRef<str> for Eid {
456    fn as_ref(&self) -> &str {
457        match self {
458            Eid::Eid(smol_str) => smol_str,
459            #[cfg(feature = "tolerant-ast")]
460            Eid::ErrorEid => EID_ERROR_STR,
461        }
462    }
463}
464
465#[cfg(feature = "arbitrary")]
466impl<'a> arbitrary::Arbitrary<'a> for Eid {
467    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
468        let x: String = u.arbitrary()?;
469        Ok(Self::Eid(x.into()))
470    }
471}
472
473/// Entity datatype
474#[derive(Debug, Clone)]
475pub struct Entity {
476    /// UID
477    uid: EntityUID,
478
479    /// Internal `BTreeMap` of attributes.
480    ///
481    /// We use a `BTreeMap` so that the keys have a deterministic order.
482    attrs: BTreeMap<SmolStr, PartialValue>,
483
484    /// Set of indirect ancestors of this `Entity` as UIDs
485    indirect_ancestors: HashSet<EntityUID>,
486
487    /// Set of direct ancestors (i.e., parents) as UIDs
488    ///
489    /// indirect_ancestors and parents should be disjoint
490    /// even if a parent is also an indirect parent through
491    /// a different parent
492    parents: HashSet<EntityUID>,
493
494    /// Tags on this entity (RFC 82)
495    ///
496    /// Like for `attrs`, we use a `BTreeMap` so that the tags have a
497    /// deterministic order.
498    tags: BTreeMap<SmolStr, PartialValue>,
499}
500
501impl std::hash::Hash for Entity {
502    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
503        self.uid.hash(state);
504    }
505}
506
507impl Entity {
508    /// Create a new `Entity` with this UID, attributes, ancestors, and tags
509    ///
510    /// # Errors
511    /// - Will error if any of the [`RestrictedExpr]`s in `attrs` or `tags` error when evaluated
512    pub fn new(
513        uid: EntityUID,
514        attrs: impl IntoIterator<Item = (SmolStr, RestrictedExpr)>,
515        indirect_ancestors: HashSet<EntityUID>,
516        parents: HashSet<EntityUID>,
517        tags: impl IntoIterator<Item = (SmolStr, RestrictedExpr)>,
518        extensions: &Extensions<'_>,
519    ) -> Result<Self, EntityAttrEvaluationError> {
520        let evaluator = RestrictedEvaluator::new(extensions);
521        let evaluate_kvs = |(k, v): (SmolStr, RestrictedExpr), was_attr: bool| {
522            let attr_val = evaluator
523                .partial_interpret(v.as_borrowed())
524                .map_err(|err| EntityAttrEvaluationError {
525                    uid: uid.clone(),
526                    attr_or_tag: k.clone(),
527                    was_attr,
528                    err,
529                })?;
530            Ok((k, attr_val))
531        };
532        let evaluated_attrs = attrs
533            .into_iter()
534            .map(|kv| evaluate_kvs(kv, true))
535            .collect::<Result<_, EntityAttrEvaluationError>>()?;
536        let evaluated_tags = tags
537            .into_iter()
538            .map(|kv| evaluate_kvs(kv, false))
539            .collect::<Result<_, EntityAttrEvaluationError>>()?;
540        Ok(Entity {
541            uid,
542            attrs: evaluated_attrs,
543            indirect_ancestors,
544            parents,
545            tags: evaluated_tags,
546        })
547    }
548
549    /// Create a new [`Entity`] with this UID, attributes, ancestors, and tags
550    ///
551    /// Unlike in `Entity::new()`, in this constructor, attributes and tags are
552    /// expressed as `PartialValue`.
553    pub fn new_with_attr_partial_value(
554        uid: EntityUID,
555        attrs: impl IntoIterator<Item = (SmolStr, PartialValue)>,
556        indirect_ancestors: HashSet<EntityUID>,
557        parents: HashSet<EntityUID>,
558        tags: impl IntoIterator<Item = (SmolStr, PartialValue)>,
559    ) -> Self {
560        Self {
561            uid,
562            attrs: attrs.into_iter().collect(),
563            indirect_ancestors,
564            parents,
565            tags: tags.into_iter().collect(),
566        }
567    }
568
569    /// Get the UID of this entity
570    pub fn uid(&self) -> &EntityUID {
571        &self.uid
572    }
573
574    /// Get the value for the given attribute, or `None` if not present
575    pub fn get(&self, attr: &str) -> Option<&PartialValue> {
576        self.attrs.get(attr)
577    }
578
579    /// Get the value for the given tag, or `None` if not present
580    pub fn get_tag(&self, tag: &str) -> Option<&PartialValue> {
581        self.tags.get(tag)
582    }
583
584    /// Is this `Entity` a (direct or indirect) descendant of `e` in the entity hierarchy?
585    pub fn is_descendant_of(&self, e: &EntityUID) -> bool {
586        self.parents.contains(e) || self.indirect_ancestors.contains(e)
587    }
588
589    /// Is this `Entity` a an indirect descendant of `e` in the entity hierarchy?
590    pub fn is_indirect_descendant_of(&self, e: &EntityUID) -> bool {
591        self.indirect_ancestors.contains(e)
592    }
593
594    /// Is this `Entity` a direct decendant (child) of `e` in the entity hierarchy?
595    pub fn is_child_of(&self, e: &EntityUID) -> bool {
596        self.parents.contains(e)
597    }
598
599    /// Iterate over this entity's (direct or indirect) ancestors
600    pub fn ancestors(&self) -> impl Iterator<Item = &EntityUID> {
601        self.parents.iter().chain(self.indirect_ancestors.iter())
602    }
603
604    /// Iterate over this entity's indirect ancestors
605    pub fn indirect_ancestors(&self) -> impl Iterator<Item = &EntityUID> {
606        self.indirect_ancestors.iter()
607    }
608
609    /// Iterate over this entity's direct ancestors (parents)
610    pub fn parents(&self) -> impl Iterator<Item = &EntityUID> {
611        self.parents.iter()
612    }
613
614    /// Get the number of attributes on this entity
615    pub fn attrs_len(&self) -> usize {
616        self.attrs.len()
617    }
618
619    /// Get the number of tags on this entity
620    pub fn tags_len(&self) -> usize {
621        self.tags.len()
622    }
623
624    /// Iterate over this entity's attribute names
625    pub fn keys(&self) -> impl Iterator<Item = &SmolStr> {
626        self.attrs.keys()
627    }
628
629    /// Iterate over this entity's tag names
630    pub fn tag_keys(&self) -> impl Iterator<Item = &SmolStr> {
631        self.tags.keys()
632    }
633
634    /// Iterate over this entity's attributes
635    pub fn attrs(&self) -> impl Iterator<Item = (&SmolStr, &PartialValue)> {
636        self.attrs.iter()
637    }
638
639    /// Iterate over this entity's tags
640    pub fn tags(&self) -> impl Iterator<Item = (&SmolStr, &PartialValue)> {
641        self.tags.iter()
642    }
643
644    /// Create an `Entity` with the given UID, no attributes, no parents, and no tags.
645    pub fn with_uid(uid: EntityUID) -> Self {
646        Self {
647            uid,
648            attrs: BTreeMap::new(),
649            indirect_ancestors: HashSet::new(),
650            parents: HashSet::new(),
651            tags: BTreeMap::new(),
652        }
653    }
654
655    /// Test if two `Entity` objects are deep/structurally equal.
656    /// That is, not only do they have the same UID, but also the same
657    /// attributes, attribute values, and ancestors/parents.
658    ///
659    /// Does not test that they have the same _direct_ parents, only that they have the same overall ancestor set.
660    pub fn deep_eq(&self, other: &Self) -> bool {
661        self.uid == other.uid
662            && self.attrs == other.attrs
663            && self.tags == other.tags
664            && (self.ancestors().collect::<HashSet<_>>())
665                == (other.ancestors().collect::<HashSet<_>>())
666    }
667
668    /// Mark the given `UID` as an indirect ancestor of this `Entity`
669    ///
670    /// The given `UID` will not be added as an indirecty ancestor if
671    /// it is already a direct ancestor (parent) of this `Entity`
672    /// The caller of this code is responsible for maintaining
673    /// transitive closure of hierarchy.
674    pub fn add_indirect_ancestor(&mut self, uid: EntityUID) {
675        if !self.parents.contains(&uid) {
676            self.indirect_ancestors.insert(uid);
677        }
678    }
679
680    /// Mark the given `UID` as a (direct) parent of this `Entity`, and
681    /// remove the UID from indirect ancestors
682    /// if it was previously added as an indirect ancestor
683    /// The caller of this code is responsible for maintaining
684    /// transitive closure of hierarchy.
685    pub fn add_parent(&mut self, uid: EntityUID) {
686        self.indirect_ancestors.remove(&uid);
687        self.parents.insert(uid);
688    }
689
690    /// Remove the given `UID` as an indirect ancestor of this `Entity`.
691    ///
692    /// No effect if the `UID` is a direct parent.
693    /// The caller of this code is responsible for maintaining
694    /// transitive closure of hierarchy.
695    pub fn remove_indirect_ancestor(&mut self, uid: &EntityUID) {
696        self.indirect_ancestors.remove(uid);
697    }
698
699    /// Remove the given `UID` as a (direct) parent of this `Entity`.
700    ///
701    /// No effect on the `Entity`'s indirect ancestors.
702    /// The caller of this code is responsible for maintaining
703    /// transitive closure of hierarchy.
704    pub fn remove_parent(&mut self, uid: &EntityUID) {
705        self.parents.remove(uid);
706    }
707
708    /// Remove all indirect ancestors of this `Entity`.
709    ///
710    /// The caller of this code is responsible for maintaining
711    /// transitive closure of hierarchy.
712    pub fn remove_all_indirect_ancestors(&mut self) {
713        self.indirect_ancestors.clear();
714    }
715
716    /// Consume the entity and return the entity's owned Uid, attributes, ancestors, parents, and tags.
717    #[expect(
718        clippy::type_complexity,
719        reason = "needs to return a 5-tuple by design"
720    )]
721    pub fn into_inner(
722        self,
723    ) -> (
724        EntityUID,
725        BTreeMap<SmolStr, PartialValue>,
726        HashSet<EntityUID>,
727        HashSet<EntityUID>,
728        BTreeMap<SmolStr, PartialValue>,
729    ) {
730        (
731            self.uid,
732            self.attrs,
733            self.indirect_ancestors,
734            self.parents,
735            self.tags,
736        )
737    }
738
739    /// Write the entity to a json document
740    pub fn write_to_json(&self, f: impl std::io::Write) -> Result<(), EntitiesError> {
741        let ejson = EntityJson::from_entity(self)?;
742        serde_json::to_writer_pretty(f, &ejson).map_err(JsonSerializationError::from)?;
743        Ok(())
744    }
745
746    /// write the entity to a json value
747    pub fn to_json_value(&self) -> Result<serde_json::Value, EntitiesError> {
748        let ejson = EntityJson::from_entity(self)?;
749        let v = serde_json::to_value(ejson).map_err(JsonSerializationError::from)?;
750        Ok(v)
751    }
752
753    /// write the entity to a json string
754    pub fn to_json_string(&self) -> Result<String, EntitiesError> {
755        let ejson = EntityJson::from_entity(self)?;
756        let string = serde_json::to_string(&ejson).map_err(JsonSerializationError::from)?;
757        Ok(string)
758    }
759
760    /// Validate that this is a well formed entity, otherwise return an [EntitiesError].
761    /// The following invariants are checked:
762    /// - entity should not be its own ancestor
763    /// - parents and indirect_ancestors should be disjoint
764    /// - action entities must only have action parents
765    /// - no attribute or tag value contains a record with a reserved key
766    pub fn try_validate(self) -> Result<Self, EntitiesError> {
767        self.validate()?;
768        Ok(self)
769    }
770
771    /// Validate that this is a well formed entity by reference.
772    pub fn validate(&self) -> Result<(), EntitiesError> {
773        // Invariant: entity should not be its own ancestor
774        if self.parents.contains(&self.uid) || self.indirect_ancestors.contains(&self.uid) {
775            return Err(InvalidEntityStructureError::SelfAncestor {
776                uid: self.uid.clone(),
777            }
778            .into());
779        }
780        // Invariant: parents and indirect_ancestors should be disjoint
781        if let Some(dup) = self.parents.intersection(&self.indirect_ancestors).next() {
782            return Err(InvalidEntityStructureError::DuplicateAncestor {
783                uid: self.uid.clone(),
784                ancestor: dup.clone(),
785            }
786            .into());
787        }
788        // Invariant: action entities must only have action parents
789        if self.uid.is_action() {
790            if let Some(parent) = self
791                .parents
792                .iter()
793                .chain(self.indirect_ancestors.iter())
794                .find(|p| !p.is_action())
795            {
796                return Err(InvalidEntityStructureError::ActionParentIsNotAction {
797                    uid: self.uid.clone(),
798                    parent: parent.clone(),
799                }
800                .into());
801            }
802        }
803        // Invariant: no attribute or tag value uses a reserved JSON key, which
804        // would not round-trip through the JSON format
805        if let Some(key) = self
806            .attrs
807            .values()
808            .chain(self.tags.values())
809            .find_map(|pv| match pv {
810                PartialValue::Value(v) => value_reserved_key(v),
811                PartialValue::Residual(_) => None,
812            })
813        {
814            return Err(JsonSerializationError::reserved_key(key.clone()).into());
815        }
816        Ok(())
817    }
818}
819
820/// Return the first reserved key found in a record anywhere within `v`, if any.
821/// Read-only and allocation-free; returns early on the first hit.
822fn value_reserved_key(v: &Value) -> Option<&SmolStr> {
823    match &v.value {
824        ValueKind::Record(fields) => fields.iter().find_map(|(k, v)| {
825            is_reserved_key(k)
826                .then_some(k)
827                .or_else(|| value_reserved_key(v))
828        }),
829        ValueKind::Set(s) => s.authoritative.iter().find_map(value_reserved_key),
830        ValueKind::Lit(_) | ValueKind::ExtensionValue(_) => None,
831    }
832}
833
834/// `Entity`s are equal if their UIDs are equal
835impl PartialEq for Entity {
836    fn eq(&self, other: &Self) -> bool {
837        self.uid() == other.uid()
838    }
839}
840
841impl Eq for Entity {}
842
843impl StaticallyTyped for Entity {
844    fn type_of(&self) -> Type {
845        self.uid.type_of()
846    }
847}
848
849impl TCNode<EntityUID> for Entity {
850    fn get_key(&self) -> EntityUID {
851        self.uid().clone()
852    }
853
854    fn add_edge_to(&mut self, k: EntityUID) {
855        self.add_indirect_ancestor(k);
856    }
857
858    fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
859        Box::new(self.ancestors())
860    }
861
862    fn has_edge_to(&self, e: &EntityUID) -> bool {
863        self.is_descendant_of(e)
864    }
865
866    fn reset_edges(&mut self) {
867        self.remove_all_indirect_ancestors()
868    }
869
870    fn direct_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
871        Box::new(self.parents())
872    }
873}
874
875impl TCNode<EntityUID> for Arc<Entity> {
876    fn get_key(&self) -> EntityUID {
877        self.uid().clone()
878    }
879
880    fn add_edge_to(&mut self, k: EntityUID) {
881        // Use Arc::make_mut to get a mutable reference to the inner value
882        Arc::make_mut(self).add_indirect_ancestor(k)
883    }
884
885    fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
886        Box::new(self.ancestors())
887    }
888
889    fn has_edge_to(&self, e: &EntityUID) -> bool {
890        self.is_descendant_of(e)
891    }
892
893    fn reset_edges(&mut self) {
894        // Use Arc::make_mut to get a mutable reference to the inner value
895        Arc::make_mut(self).remove_all_indirect_ancestors()
896    }
897
898    fn direct_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
899        Box::new(self.parents())
900    }
901}
902
903impl std::fmt::Display for Entity {
904    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
905        write!(
906            f,
907            "{}:\n  attrs:{}\n  ancestors:{}",
908            self.uid,
909            self.attrs
910                .iter()
911                .map(|(k, v)| format!("{k}: {v}"))
912                .join("; "),
913            self.ancestors().join(", ")
914        )
915    }
916}
917
918/// Error type for evaluation errors when evaluating an entity attribute or tag.
919/// Contains some extra contextual information and the underlying
920/// `EvaluationError`.
921//
922// This is NOT a publicly exported error type.
923#[derive(Debug, Diagnostic, Error)]
924#[error("failed to evaluate {} `{attr_or_tag}` of `{uid}`: {err}", if *.was_attr { "attribute" } else { "tag" })]
925pub struct EntityAttrEvaluationError {
926    /// UID of the entity where the error was encountered
927    pub uid: EntityUID,
928    /// Attribute or tag of the entity where the error was encountered
929    pub attr_or_tag: SmolStr,
930    /// If `attr_or_tag` was an attribute (`true`) or tag (`false`)
931    pub was_attr: bool,
932    /// Underlying evaluation error
933    #[diagnostic(transparent)]
934    pub err: EvaluationError,
935}
936
937#[cfg(test)]
938mod test {
939    use std::str::FromStr;
940
941    use super::*;
942
943    #[test]
944    fn display() {
945        let e = EntityUID::with_eid("eid");
946        assert_eq!(format!("{e}"), "test_entity_type::\"eid\"");
947    }
948
949    #[test]
950    fn test_euid_equality() {
951        let e1 = EntityUID::with_eid("foo");
952        let e2 = EntityUID::from_components(
953            Name::parse_unqualified_name("test_entity_type")
954                .expect("should be a valid identifier")
955                .into(),
956            Eid::Eid("foo".into()),
957            None,
958        );
959        let e3 = EntityUID::from_components(
960            Name::parse_unqualified_name("Unspecified")
961                .expect("should be a valid identifier")
962                .into(),
963            Eid::Eid("foo".into()),
964            None,
965        );
966
967        // an EUID is equal to itself
968        assert_eq!(e1, e1);
969        assert_eq!(e2, e2);
970
971        // constructing with `with_euid` or `from_components` is the same
972        assert_eq!(e1, e2);
973
974        // other pairs are not equal
975        assert!(e1 != e3);
976    }
977
978    #[test]
979    fn action_checker() {
980        let euid = EntityUID::from_str("Action::\"view\"").unwrap();
981        assert!(euid.is_action());
982        let euid = EntityUID::from_str("Foo::Action::\"view\"").unwrap();
983        assert!(euid.is_action());
984        let euid = EntityUID::from_str("Foo::\"view\"").unwrap();
985        assert!(!euid.is_action());
986        let euid = EntityUID::from_str("Action::Foo::\"view\"").unwrap();
987        assert!(!euid.is_action());
988    }
989
990    #[test]
991    fn action_type_is_valid_id() {
992        Id::from_normalized_str(ACTION_ENTITY_TYPE).unwrap();
993    }
994
995    #[test]
996    fn validate_rejects_reserved_key_in_value() {
997        let tag = |v: Value| {
998            Entity::new_with_attr_partial_value(
999                EntityUID::with_eid("a"),
1000                [],
1001                HashSet::new(),
1002                HashSet::new(),
1003                [("t".into(), v.into())],
1004            )
1005            .validate()
1006        };
1007        let reserveds = [
1008            Value::record([("__extn", Value::from(true))], None),
1009            Value::record([("__expr", Value::from(true))], None),
1010            Value::record([("__entity", Value::from(true))], None),
1011        ];
1012
1013        // reserved keys directly in a value, and nested inside a set
1014        for reserved in reserveds {
1015            assert!(tag(reserved.clone()).is_err());
1016            assert!(tag(Value::set([Value::set([reserved], None)], None)).is_err());
1017        }
1018        // ordinary keys are fine
1019        assert!(tag(Value::record([("ordinary", Value::from(1))], None)).is_ok());
1020    }
1021
1022    #[cfg(feature = "tolerant-ast")]
1023    #[test]
1024    fn error_entity() {
1025        use cool_asserts::assert_matches;
1026
1027        let e = EntityUID::Error;
1028        assert_matches!(e.eid(), Eid::ErrorEid);
1029        assert_matches!(e.entity_type(), EntityType::ErrorEntityType);
1030        assert!(!e.is_action());
1031        assert_matches!(e.loc(), None);
1032
1033        let error_eid = Eid::ErrorEid;
1034        assert_eq!(error_eid.escaped(), "Eid::Error");
1035
1036        let error_type = EntityType::ErrorEntityType;
1037        assert!(!error_type.is_action());
1038        assert_eq!(error_type.qualify_with(None), EntityType::ErrorEntityType);
1039        assert_eq!(
1040            error_type.qualify_with(Some(&Name(InternalName::from(Id::new_unchecked_const(
1041                "EntityTypeError"
1042            ))))),
1043            EntityType::ErrorEntityType
1044        );
1045
1046        assert_eq!(
1047            error_type.name(),
1048            &Name(InternalName::from(Id::new_unchecked_const(
1049                "EntityTypeError"
1050            )))
1051        );
1052        assert_eq!(error_type.loc(), None)
1053    }
1054
1055    #[test]
1056    fn entity_type_deserialization() {
1057        let json = r#""some_entity_type""#;
1058        let entity_type: EntityType = serde_json::from_str(json).unwrap();
1059        assert_eq!(
1060            entity_type.name().0.to_string(),
1061            "some_entity_type".to_string()
1062        )
1063    }
1064
1065    #[test]
1066    fn entity_type_serialization() {
1067        let entity_type = EntityType::EntityType(Name(InternalName::from(
1068            Id::new_unchecked_const("some_entity_type"),
1069        )));
1070        let serialized = serde_json::to_string(&entity_type).unwrap();
1071
1072        assert_eq!(serialized, r#""some_entity_type""#);
1073    }
1074
1075    #[test]
1076    fn euid_ordering_matches_type_then_eid() {
1077        let euid1 = EntityUID::from_str("AA::\"zzz\"").unwrap();
1078        let euid2 = EntityUID::from_str("B::\"aaa\"").unwrap();
1079        // The type is the primary sort key: `AA` < `B` regardless of eid.
1080        assert!(euid1 < euid2);
1081        let euid3 = EntityUID::from_str("AA::\"aaa\"").unwrap();
1082        // The eid is the tie-breaker when the types are equal.
1083        assert!(euid3 < euid1);
1084    }
1085}
1086
1087#[cfg(test)]
1088mod validate_test {
1089    use std::str::FromStr;
1090
1091    use super::*;
1092
1093    /// Helper to build an entity with the given uid, parents, and indirect ancestors
1094    fn entity_with(
1095        uid: EntityUID,
1096        parents: impl IntoIterator<Item = EntityUID>,
1097        indirect_ancestors: impl IntoIterator<Item = EntityUID>,
1098    ) -> Entity {
1099        Entity::new_with_attr_partial_value(
1100            uid,
1101            std::iter::empty(),
1102            indirect_ancestors.into_iter().collect(),
1103            parents.into_iter().collect(),
1104            std::iter::empty(),
1105        )
1106    }
1107
1108    #[test]
1109    fn self_in_parents_rejected() {
1110        let uid = EntityUID::with_eid("self");
1111        let e = entity_with(uid.clone(), [uid], []);
1112        assert!(e.try_validate().is_err());
1113    }
1114
1115    #[test]
1116    fn self_in_indirect_ancestors_rejected() {
1117        let uid = EntityUID::with_eid("self");
1118        let e = entity_with(uid.clone(), [], [uid]);
1119        assert!(e.try_validate().is_err());
1120    }
1121
1122    #[test]
1123    fn no_self_ancestor_accepted() {
1124        let e = entity_with(EntityUID::with_eid("ok"), [], []);
1125        assert!(e.try_validate().is_ok());
1126    }
1127
1128    #[test]
1129    fn duplicate_ancestor_rejected() {
1130        let uid = EntityUID::with_eid("child");
1131        let ancestor = EntityUID::with_eid("parent");
1132        let e = entity_with(uid, [ancestor.clone()], [ancestor]);
1133        assert!(e.try_validate().is_err());
1134    }
1135
1136    #[test]
1137    fn action_with_non_action_parent_rejected() {
1138        let uid = EntityUID::from_str("Action::\"view\"").unwrap();
1139        let parent = EntityUID::from_str("User::\"alice\"").unwrap();
1140        let e = entity_with(uid, [parent], []);
1141        assert!(e.try_validate().is_err());
1142    }
1143
1144    #[test]
1145    fn action_with_action_parent_accepted() {
1146        let uid = EntityUID::from_str("Action::\"view\"").unwrap();
1147        let parent = EntityUID::from_str("Action::\"read\"").unwrap();
1148        let e = entity_with(uid, [parent], []);
1149        assert!(e.try_validate().is_ok());
1150    }
1151
1152    #[test]
1153    fn non_action_with_action_parent_accepted() {
1154        let uid = EntityUID::from_str("User::\"alice\"").unwrap();
1155        let parent = EntityUID::from_str("Action::\"read\"").unwrap();
1156        let e = entity_with(uid, [parent], []);
1157        assert!(e.try_validate().is_ok());
1158    }
1159}
cedar_policy_core/ast/entity.rs

cedar_policy_core/ast/
entity.rs
