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,
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, HashMap, 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    loc: Option<Loc>,
222}
223
224impl EntityUIDImpl {
225    /// The source location of this entity
226    pub fn loc(&self) -> Option<Loc> {
227        self.loc.clone()
228    }
229}
230
231/// Unique ID for an entity. These represent entities in the AST.
232#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
233pub enum EntityUID {
234    /// Unique ID for an entity. These represent entities in the AST
235    EntityUID(EntityUIDImpl),
236    #[cfg(feature = "tolerant-ast")]
237    /// Represents the ID of an error that failed to parse
238    Error,
239}
240
241impl<'de> Deserialize<'de> for EntityUID {
242    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
243    where
244        D: Deserializer<'de>,
245    {
246        let uid_impl = EntityUIDImpl::deserialize(deserializer)?;
247        Ok(EntityUID::EntityUID(uid_impl))
248    }
249}
250
251impl Serialize for EntityUID {
252    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
253    where
254        S: Serializer,
255    {
256        match self {
257            EntityUID::EntityUID(uid_impl) => uid_impl.serialize(serializer),
258            #[cfg(feature = "tolerant-ast")]
259            EntityUID::Error => serializer.serialize_str(ENTITY_UID_ERROR_STR),
260        }
261    }
262}
263
264impl StaticallyTyped for EntityUID {
265    fn type_of(&self) -> Type {
266        match self {
267            EntityUID::EntityUID(entity_uid) => Type::Entity {
268                ty: entity_uid.ty.clone(),
269            },
270            #[cfg(feature = "tolerant-ast")]
271            EntityUID::Error => Type::Entity {
272                ty: EntityType::ErrorEntityType,
273            },
274        }
275    }
276}
277
278#[cfg(test)]
279impl EntityUID {
280    /// Create an `EntityUID` with the given string as its EID.
281    /// Useful for testing.
282    pub(crate) fn with_eid(eid: &str) -> Self {
283        Self::EntityUID(EntityUIDImpl {
284            ty: Self::test_entity_type(),
285            eid: Eid::Eid(eid.into()),
286            loc: None,
287        })
288    }
289
290    /// The type of entities created with the above `with_eid()`.
291    pub(crate) fn test_entity_type() -> EntityType {
292        let name = Name::parse_unqualified_name("test_entity_type")
293            .expect("test_entity_type should be a valid identifier");
294        EntityType::EntityType(name)
295    }
296}
297
298impl EntityUID {
299    /// Create an `EntityUID` with the given (unqualified) typename, and the given string as its EID.
300    pub fn with_eid_and_type(typename: &str, eid: &str) -> Result<Self, ParseErrors> {
301        Ok(Self::EntityUID(EntityUIDImpl {
302            ty: EntityType::EntityType(Name::parse_unqualified_name(typename)?),
303            eid: Eid::Eid(eid.into()),
304            loc: None,
305        }))
306    }
307
308    /// Split into the `EntityType` representing the entity type, and the `Eid`
309    /// representing its name
310    pub fn components(self) -> (EntityType, Eid) {
311        match self {
312            EntityUID::EntityUID(entity_uid) => (entity_uid.ty, entity_uid.eid),
313            #[cfg(feature = "tolerant-ast")]
314            EntityUID::Error => (EntityType::ErrorEntityType, Eid::ErrorEid),
315        }
316    }
317
318    /// Get the source location for this `EntityUID`.
319    pub fn loc(&self) -> Option<&Loc> {
320        match self {
321            EntityUID::EntityUID(entity_uid) => entity_uid.loc.as_ref(),
322            #[cfg(feature = "tolerant-ast")]
323            EntityUID::Error => None,
324        }
325    }
326
327    /// Create an [`EntityUID`] with the given typename and [`Eid`]
328    pub fn from_components(ty: EntityType, eid: Eid, loc: Option<Loc>) -> Self {
329        Self::EntityUID(EntityUIDImpl { ty, eid, loc })
330    }
331
332    /// Get the type component.
333    pub fn entity_type(&self) -> &EntityType {
334        match self {
335            EntityUID::EntityUID(entity_uid) => &entity_uid.ty,
336            #[cfg(feature = "tolerant-ast")]
337            EntityUID::Error => &EntityType::ErrorEntityType,
338        }
339    }
340
341    /// Get the Eid component.
342    pub fn eid(&self) -> &Eid {
343        match self {
344            EntityUID::EntityUID(entity_uid) => &entity_uid.eid,
345            #[cfg(feature = "tolerant-ast")]
346            EntityUID::Error => &Eid::ErrorEid,
347        }
348    }
349
350    /// Does this EntityUID refer to an action entity?
351    pub fn is_action(&self) -> bool {
352        self.entity_type().is_action()
353    }
354}
355
356impl std::fmt::Display for EntityUID {
357    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
358        write!(f, "{}::\"{}\"", self.entity_type(), self.eid().escaped())
359    }
360}
361
362// allow `.parse()` on a string to make an `EntityUID`
363impl std::str::FromStr for EntityUID {
364    type Err = ParseErrors;
365
366    fn from_str(s: &str) -> Result<Self, Self::Err> {
367        crate::parser::parse_euid(s)
368    }
369}
370
371impl FromNormalizedStr for EntityUID {
372    fn describe_self() -> &'static str {
373        "Entity UID"
374    }
375}
376
377#[cfg(feature = "arbitrary")]
378impl<'a> arbitrary::Arbitrary<'a> for EntityUID {
379    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
380        Ok(Self::EntityUID(EntityUIDImpl {
381            ty: u.arbitrary()?,
382            eid: u.arbitrary()?,
383            loc: None,
384        }))
385    }
386}
387
388/// The `Eid` type represents the id of an `Entity`, without the typename.
389/// Together with the typename it comprises an `EntityUID`.
390/// For example, in `User::"alice"`, the `Eid` is `alice`.
391///
392/// `Eid` does not implement `Display`, partly because it is unclear whether
393/// `Display` should produce an escaped representation or an unescaped representation
394/// (see [#884](https://github.com/cedar-policy/cedar/issues/884)).
395/// To get an escaped representation, use `.escaped()`.
396/// To get an unescaped representation, use `.as_ref()`.
397#[derive(PartialEq, Eq, Debug, Clone, Hash, PartialOrd, Ord)]
398pub enum Eid {
399    /// Actual Eid
400    Eid(SmolStr),
401    #[cfg(feature = "tolerant-ast")]
402    /// Represents an Eid of an entity that failed to parse
403    ErrorEid,
404}
405
406impl<'de> Deserialize<'de> for Eid {
407    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
408    where
409        D: Deserializer<'de>,
410    {
411        let value = String::deserialize(deserializer)?;
412        Ok(Eid::Eid(SmolStr::from(value)))
413    }
414}
415
416impl Serialize for Eid {
417    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
418    where
419        S: Serializer,
420    {
421        match self {
422            Eid::Eid(s) => s.serialize(serializer),
423            #[cfg(feature = "tolerant-ast")]
424            Eid::ErrorEid => serializer.serialize_str(EID_ERROR_STR),
425        }
426    }
427}
428
429impl Eid {
430    /// Construct an Eid
431    pub fn new(eid: impl Into<SmolStr>) -> Self {
432        Eid::Eid(eid.into())
433    }
434
435    /// Get the contents of the `Eid` as an escaped string
436    pub fn escaped(&self) -> SmolStr {
437        match self {
438            Eid::Eid(smol_str) => smol_str.escape_debug().collect(),
439            #[cfg(feature = "tolerant-ast")]
440            Eid::ErrorEid => SmolStr::new_static(EID_ERROR_STR),
441        }
442    }
443
444    /// Get the underlying smolstr for this `Eid`
445    pub fn into_smolstr(self) -> SmolStr {
446        match self {
447            Eid::Eid(smol_str) => smol_str,
448            #[cfg(feature = "tolerant-ast")]
449            Eid::ErrorEid => SmolStr::new_static(EID_ERROR_STR),
450        }
451    }
452}
453
454impl AsRef<str> for Eid {
455    fn as_ref(&self) -> &str {
456        match self {
457            Eid::Eid(smol_str) => smol_str,
458            #[cfg(feature = "tolerant-ast")]
459            Eid::ErrorEid => EID_ERROR_STR,
460        }
461    }
462}
463
464#[cfg(feature = "arbitrary")]
465impl<'a> arbitrary::Arbitrary<'a> for Eid {
466    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
467        let x: String = u.arbitrary()?;
468        Ok(Self::Eid(x.into()))
469    }
470}
471
472/// Entity datatype
473#[derive(Debug, Clone)]
474pub struct Entity {
475    /// UID
476    uid: EntityUID,
477
478    /// Internal `BTreeMap` of attributes.
479    ///
480    /// We use a `BTreeMap` so that the keys have a deterministic order.
481    attrs: BTreeMap<SmolStr, PartialValue>,
482
483    /// Set of indirect ancestors of this `Entity` as UIDs
484    indirect_ancestors: HashSet<EntityUID>,
485
486    /// Set of direct ancestors (i.e., parents) as UIDs
487    ///
488    /// indirect_ancestors and parents should be disjoint
489    /// even if a parent is also an indirect parent through
490    /// a different parent
491    parents: HashSet<EntityUID>,
492
493    /// Tags on this entity (RFC 82)
494    ///
495    /// Like for `attrs`, we use a `BTreeMap` so that the tags have a
496    /// deterministic order.
497    tags: BTreeMap<SmolStr, PartialValue>,
498}
499
500impl std::hash::Hash for Entity {
501    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
502        self.uid.hash(state);
503    }
504}
505
506impl Entity {
507    /// Create a new `Entity` with this UID, attributes, ancestors, and tags
508    ///
509    /// # Errors
510    /// - Will error if any of the [`RestrictedExpr]`s in `attrs` or `tags` error when evaluated
511    pub fn new(
512        uid: EntityUID,
513        attrs: impl IntoIterator<Item = (SmolStr, RestrictedExpr)>,
514        indirect_ancestors: HashSet<EntityUID>,
515        parents: HashSet<EntityUID>,
516        tags: impl IntoIterator<Item = (SmolStr, RestrictedExpr)>,
517        extensions: &Extensions<'_>,
518    ) -> Result<Self, EntityAttrEvaluationError> {
519        let evaluator = RestrictedEvaluator::new(extensions);
520        let evaluate_kvs = |(k, v): (SmolStr, RestrictedExpr), was_attr: bool| {
521            let attr_val = evaluator
522                .partial_interpret(v.as_borrowed())
523                .map_err(|err| EntityAttrEvaluationError {
524                    uid: uid.clone(),
525                    attr_or_tag: k.clone(),
526                    was_attr,
527                    err,
528                })?;
529            Ok((k, attr_val))
530        };
531        let evaluated_attrs = attrs
532            .into_iter()
533            .map(|kv| evaluate_kvs(kv, true))
534            .collect::<Result<_, EntityAttrEvaluationError>>()?;
535        let evaluated_tags = tags
536            .into_iter()
537            .map(|kv| evaluate_kvs(kv, false))
538            .collect::<Result<_, EntityAttrEvaluationError>>()?;
539        Ok(Entity {
540            uid,
541            attrs: evaluated_attrs,
542            indirect_ancestors,
543            parents,
544            tags: evaluated_tags,
545        })
546    }
547
548    /// Create a new [`Entity`] with this UID, attributes, ancestors, and tags
549    ///
550    /// Unlike in `Entity::new()`, in this constructor, attributes and tags are
551    /// expressed as `PartialValue`.
552    pub fn new_with_attr_partial_value(
553        uid: EntityUID,
554        attrs: impl IntoIterator<Item = (SmolStr, PartialValue)>,
555        indirect_ancestors: HashSet<EntityUID>,
556        parents: HashSet<EntityUID>,
557        tags: impl IntoIterator<Item = (SmolStr, PartialValue)>,
558    ) -> Self {
559        Self {
560            uid,
561            attrs: attrs.into_iter().collect(),
562            indirect_ancestors,
563            parents,
564            tags: tags.into_iter().collect(),
565        }
566    }
567
568    /// Get the UID of this entity
569    pub fn uid(&self) -> &EntityUID {
570        &self.uid
571    }
572
573    /// Get the value for the given attribute, or `None` if not present
574    pub fn get(&self, attr: &str) -> Option<&PartialValue> {
575        self.attrs.get(attr)
576    }
577
578    /// Get the value for the given tag, or `None` if not present
579    pub fn get_tag(&self, tag: &str) -> Option<&PartialValue> {
580        self.tags.get(tag)
581    }
582
583    /// Is this `Entity` a (direct or indirect) descendant of `e` in the entity hierarchy?
584    pub fn is_descendant_of(&self, e: &EntityUID) -> bool {
585        self.parents.contains(e) || self.indirect_ancestors.contains(e)
586    }
587
588    /// Is this `Entity` a an indirect descendant of `e` in the entity hierarchy?
589    pub fn is_indirect_descendant_of(&self, e: &EntityUID) -> bool {
590        self.indirect_ancestors.contains(e)
591    }
592
593    /// Is this `Entity` a direct decendant (child) of `e` in the entity hierarchy?
594    pub fn is_child_of(&self, e: &EntityUID) -> bool {
595        self.parents.contains(e)
596    }
597
598    /// Iterate over this entity's (direct or indirect) ancestors
599    pub fn ancestors(&self) -> impl Iterator<Item = &EntityUID> {
600        self.parents.iter().chain(self.indirect_ancestors.iter())
601    }
602
603    /// Iterate over this entity's indirect ancestors
604    pub fn indirect_ancestors(&self) -> impl Iterator<Item = &EntityUID> {
605        self.indirect_ancestors.iter()
606    }
607
608    /// Iterate over this entity's direct ancestors (parents)
609    pub fn parents(&self) -> impl Iterator<Item = &EntityUID> {
610        self.parents.iter()
611    }
612
613    /// Get the number of attributes on this entity
614    pub fn attrs_len(&self) -> usize {
615        self.attrs.len()
616    }
617
618    /// Get the number of tags on this entity
619    pub fn tags_len(&self) -> usize {
620        self.tags.len()
621    }
622
623    /// Iterate over this entity's attribute names
624    pub fn keys(&self) -> impl Iterator<Item = &SmolStr> {
625        self.attrs.keys()
626    }
627
628    /// Iterate over this entity's tag names
629    pub fn tag_keys(&self) -> impl Iterator<Item = &SmolStr> {
630        self.tags.keys()
631    }
632
633    /// Iterate over this entity's attributes
634    pub fn attrs(&self) -> impl Iterator<Item = (&SmolStr, &PartialValue)> {
635        self.attrs.iter()
636    }
637
638    /// Iterate over this entity's tags
639    pub fn tags(&self) -> impl Iterator<Item = (&SmolStr, &PartialValue)> {
640        self.tags.iter()
641    }
642
643    /// Create an `Entity` with the given UID, no attributes, no parents, and no tags.
644    pub fn with_uid(uid: EntityUID) -> Self {
645        Self {
646            uid,
647            attrs: BTreeMap::new(),
648            indirect_ancestors: HashSet::new(),
649            parents: HashSet::new(),
650            tags: BTreeMap::new(),
651        }
652    }
653
654    /// Test if two `Entity` objects are deep/structurally equal.
655    /// That is, not only do they have the same UID, but also the same
656    /// attributes, attribute values, and ancestors/parents.
657    ///
658    /// Does not test that they have the same _direct_ parents, only that they have the same overall ancestor set.
659    pub fn deep_eq(&self, other: &Self) -> bool {
660        self.uid == other.uid
661            && self.attrs == other.attrs
662            && self.tags == other.tags
663            && (self.ancestors().collect::<HashSet<_>>())
664                == (other.ancestors().collect::<HashSet<_>>())
665    }
666
667    /// Mark the given `UID` as an indirect ancestor of this `Entity`
668    ///
669    /// The given `UID` will not be added as an indirecty ancestor if
670    /// it is already a direct ancestor (parent) of this `Entity`
671    /// The caller of this code is responsible for maintaining
672    /// transitive closure of hierarchy.
673    pub fn add_indirect_ancestor(&mut self, uid: EntityUID) {
674        if !self.parents.contains(&uid) {
675            self.indirect_ancestors.insert(uid);
676        }
677    }
678
679    /// Mark the given `UID` as a (direct) parent of this `Entity`, and
680    /// remove the UID from indirect ancestors
681    /// if it was previously added as an indirect ancestor
682    /// The caller of this code is responsible for maintaining
683    /// transitive closure of hierarchy.
684    pub fn add_parent(&mut self, uid: EntityUID) {
685        self.indirect_ancestors.remove(&uid);
686        self.parents.insert(uid);
687    }
688
689    /// Remove the given `UID` as an indirect ancestor of this `Entity`.
690    ///
691    /// No effect if the `UID` is a direct parent.
692    /// The caller of this code is responsible for maintaining
693    /// transitive closure of hierarchy.
694    pub fn remove_indirect_ancestor(&mut self, uid: &EntityUID) {
695        self.indirect_ancestors.remove(uid);
696    }
697
698    /// Remove the given `UID` as a (direct) parent of this `Entity`.
699    ///
700    /// No effect on the `Entity`'s indirect ancestors.
701    /// The caller of this code is responsible for maintaining
702    /// transitive closure of hierarchy.
703    pub fn remove_parent(&mut self, uid: &EntityUID) {
704        self.parents.remove(uid);
705    }
706
707    /// Remove all indirect ancestors of this `Entity`.
708    ///
709    /// The caller of this code is responsible for maintaining
710    /// transitive closure of hierarchy.
711    pub fn remove_all_indirect_ancestors(&mut self) {
712        self.indirect_ancestors.clear();
713    }
714
715    /// Consume the entity and return the entity's owned Uid, attributes, ancestors, parents, and tags.
716    #[expect(
717        clippy::type_complexity,
718        reason = "needs to return a 5-tuple by design"
719    )]
720    pub fn into_inner(
721        self,
722    ) -> (
723        EntityUID,
724        HashMap<SmolStr, PartialValue>,
725        HashSet<EntityUID>,
726        HashSet<EntityUID>,
727        HashMap<SmolStr, PartialValue>,
728    ) {
729        (
730            self.uid,
731            self.attrs.into_iter().collect(),
732            self.indirect_ancestors,
733            self.parents,
734            self.tags.into_iter().collect(),
735        )
736    }
737
738    /// Write the entity to a json document
739    pub fn write_to_json(&self, f: impl std::io::Write) -> Result<(), EntitiesError> {
740        let ejson = EntityJson::from_entity(self)?;
741        serde_json::to_writer_pretty(f, &ejson).map_err(JsonSerializationError::from)?;
742        Ok(())
743    }
744
745    /// write the entity to a json value
746    pub fn to_json_value(&self) -> Result<serde_json::Value, EntitiesError> {
747        let ejson = EntityJson::from_entity(self)?;
748        let v = serde_json::to_value(ejson).map_err(JsonSerializationError::from)?;
749        Ok(v)
750    }
751
752    /// write the entity to a json string
753    pub fn to_json_string(&self) -> Result<String, EntitiesError> {
754        let ejson = EntityJson::from_entity(self)?;
755        let string = serde_json::to_string(&ejson).map_err(JsonSerializationError::from)?;
756        Ok(string)
757    }
758
759    /// Validate that this is a well formed entity, otherwise return an [EntitiesError].
760    /// The following invariants are checked:
761    /// - entity should not be its own ancestor
762    /// - parents and indirect_ancestors should be disjoint
763    /// - action entities must only have action parents
764    ///
765    /// The [`uid`], [`attrs`] and [`tags`] are correct by construction (valid names where
766    /// applicable).
767    pub fn try_validate(self) -> Result<Self, EntitiesError> {
768        self.validate()?;
769        Ok(self)
770    }
771
772    /// Validate that this is a well formed entity by reference.
773    pub fn validate(&self) -> Result<(), EntitiesError> {
774        // Invariant: entity should not be its own ancestor
775        if self.parents.contains(&self.uid) || self.indirect_ancestors.contains(&self.uid) {
776            return Err(InvalidEntityStructureError::SelfAncestor {
777                uid: self.uid.clone(),
778            }
779            .into());
780        }
781        // Invariant: parents and indirect_ancestors should be disjoint
782        if let Some(dup) = self.parents.intersection(&self.indirect_ancestors).next() {
783            return Err(InvalidEntityStructureError::DuplicateAncestor {
784                uid: self.uid.clone(),
785                ancestor: dup.clone(),
786            }
787            .into());
788        }
789        // Invariant: action entities must only have action parents
790        if self.uid.is_action() {
791            if let Some(parent) = self
792                .parents
793                .iter()
794                .chain(self.indirect_ancestors.iter())
795                .find(|p| !p.is_action())
796            {
797                return Err(InvalidEntityStructureError::ActionParentIsNotAction {
798                    uid: self.uid.clone(),
799                    parent: parent.clone(),
800                }
801                .into());
802            }
803        }
804        Ok(())
805    }
806}
807
808/// `Entity`s are equal if their UIDs are equal
809impl PartialEq for Entity {
810    fn eq(&self, other: &Self) -> bool {
811        self.uid() == other.uid()
812    }
813}
814
815impl Eq for Entity {}
816
817impl StaticallyTyped for Entity {
818    fn type_of(&self) -> Type {
819        self.uid.type_of()
820    }
821}
822
823impl TCNode<EntityUID> for Entity {
824    fn get_key(&self) -> EntityUID {
825        self.uid().clone()
826    }
827
828    fn add_edge_to(&mut self, k: EntityUID) {
829        self.add_indirect_ancestor(k);
830    }
831
832    fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
833        Box::new(self.ancestors())
834    }
835
836    fn has_edge_to(&self, e: &EntityUID) -> bool {
837        self.is_descendant_of(e)
838    }
839
840    fn reset_edges(&mut self) {
841        self.remove_all_indirect_ancestors()
842    }
843
844    fn direct_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
845        Box::new(self.parents())
846    }
847}
848
849impl TCNode<EntityUID> for Arc<Entity> {
850    fn get_key(&self) -> EntityUID {
851        self.uid().clone()
852    }
853
854    fn add_edge_to(&mut self, k: EntityUID) {
855        // Use Arc::make_mut to get a mutable reference to the inner value
856        Arc::make_mut(self).add_indirect_ancestor(k)
857    }
858
859    fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
860        Box::new(self.ancestors())
861    }
862
863    fn has_edge_to(&self, e: &EntityUID) -> bool {
864        self.is_descendant_of(e)
865    }
866
867    fn reset_edges(&mut self) {
868        // Use Arc::make_mut to get a mutable reference to the inner value
869        Arc::make_mut(self).remove_all_indirect_ancestors()
870    }
871
872    fn direct_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
873        Box::new(self.parents())
874    }
875}
876
877impl std::fmt::Display for Entity {
878    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
879        write!(
880            f,
881            "{}:\n  attrs:{}\n  ancestors:{}",
882            self.uid,
883            self.attrs
884                .iter()
885                .map(|(k, v)| format!("{k}: {v}"))
886                .join("; "),
887            self.ancestors().join(", ")
888        )
889    }
890}
891
892/// Error type for evaluation errors when evaluating an entity attribute or tag.
893/// Contains some extra contextual information and the underlying
894/// `EvaluationError`.
895//
896// This is NOT a publicly exported error type.
897#[derive(Debug, Diagnostic, Error)]
898#[error("failed to evaluate {} `{attr_or_tag}` of `{uid}`: {err}", if *.was_attr { "attribute" } else { "tag" })]
899pub struct EntityAttrEvaluationError {
900    /// UID of the entity where the error was encountered
901    pub uid: EntityUID,
902    /// Attribute or tag of the entity where the error was encountered
903    pub attr_or_tag: SmolStr,
904    /// If `attr_or_tag` was an attribute (`true`) or tag (`false`)
905    pub was_attr: bool,
906    /// Underlying evaluation error
907    #[diagnostic(transparent)]
908    pub err: EvaluationError,
909}
910
911#[cfg(test)]
912mod test {
913    use std::str::FromStr;
914
915    use super::*;
916
917    #[test]
918    fn display() {
919        let e = EntityUID::with_eid("eid");
920        assert_eq!(format!("{e}"), "test_entity_type::\"eid\"");
921    }
922
923    #[test]
924    fn test_euid_equality() {
925        let e1 = EntityUID::with_eid("foo");
926        let e2 = EntityUID::from_components(
927            Name::parse_unqualified_name("test_entity_type")
928                .expect("should be a valid identifier")
929                .into(),
930            Eid::Eid("foo".into()),
931            None,
932        );
933        let e3 = EntityUID::from_components(
934            Name::parse_unqualified_name("Unspecified")
935                .expect("should be a valid identifier")
936                .into(),
937            Eid::Eid("foo".into()),
938            None,
939        );
940
941        // an EUID is equal to itself
942        assert_eq!(e1, e1);
943        assert_eq!(e2, e2);
944
945        // constructing with `with_euid` or `from_components` is the same
946        assert_eq!(e1, e2);
947
948        // other pairs are not equal
949        assert!(e1 != e3);
950    }
951
952    #[test]
953    fn action_checker() {
954        let euid = EntityUID::from_str("Action::\"view\"").unwrap();
955        assert!(euid.is_action());
956        let euid = EntityUID::from_str("Foo::Action::\"view\"").unwrap();
957        assert!(euid.is_action());
958        let euid = EntityUID::from_str("Foo::\"view\"").unwrap();
959        assert!(!euid.is_action());
960        let euid = EntityUID::from_str("Action::Foo::\"view\"").unwrap();
961        assert!(!euid.is_action());
962    }
963
964    #[test]
965    fn action_type_is_valid_id() {
966        Id::from_normalized_str(ACTION_ENTITY_TYPE).unwrap();
967    }
968
969    #[cfg(feature = "tolerant-ast")]
970    #[test]
971    fn error_entity() {
972        use cool_asserts::assert_matches;
973
974        let e = EntityUID::Error;
975        assert_matches!(e.eid(), Eid::ErrorEid);
976        assert_matches!(e.entity_type(), EntityType::ErrorEntityType);
977        assert!(!e.is_action());
978        assert_matches!(e.loc(), None);
979
980        let error_eid = Eid::ErrorEid;
981        assert_eq!(error_eid.escaped(), "Eid::Error");
982
983        let error_type = EntityType::ErrorEntityType;
984        assert!(!error_type.is_action());
985        assert_eq!(error_type.qualify_with(None), EntityType::ErrorEntityType);
986        assert_eq!(
987            error_type.qualify_with(Some(&Name(InternalName::from(Id::new_unchecked_const(
988                "EntityTypeError"
989            ))))),
990            EntityType::ErrorEntityType
991        );
992
993        assert_eq!(
994            error_type.name(),
995            &Name(InternalName::from(Id::new_unchecked_const(
996                "EntityTypeError"
997            )))
998        );
999        assert_eq!(error_type.loc(), None)
1000    }
1001
1002    #[test]
1003    fn entity_type_deserialization() {
1004        let json = r#""some_entity_type""#;
1005        let entity_type: EntityType = serde_json::from_str(json).unwrap();
1006        assert_eq!(
1007            entity_type.name().0.to_string(),
1008            "some_entity_type".to_string()
1009        )
1010    }
1011
1012    #[test]
1013    fn entity_type_serialization() {
1014        let entity_type = EntityType::EntityType(Name(InternalName::from(
1015            Id::new_unchecked_const("some_entity_type"),
1016        )));
1017        let serialized = serde_json::to_string(&entity_type).unwrap();
1018
1019        assert_eq!(serialized, r#""some_entity_type""#);
1020    }
1021
1022    #[test]
1023    fn euid_ordering_matches_type_then_eid() {
1024        let euid1 = EntityUID::from_str("AA::\"zzz\"").unwrap();
1025        let euid2 = EntityUID::from_str("B::\"aaa\"").unwrap();
1026        // The type is the primary sort key: `AA` < `B` regardless of eid.
1027        assert!(euid1 < euid2);
1028        let euid3 = EntityUID::from_str("AA::\"aaa\"").unwrap();
1029        // The eid is the tie-breaker when the types are equal.
1030        assert!(euid3 < euid1);
1031    }
1032}
1033
1034#[cfg(test)]
1035mod validate_test {
1036    use std::str::FromStr;
1037
1038    use super::*;
1039
1040    /// Helper to build an entity with the given uid, parents, and indirect ancestors
1041    fn entity_with(
1042        uid: EntityUID,
1043        parents: impl IntoIterator<Item = EntityUID>,
1044        indirect_ancestors: impl IntoIterator<Item = EntityUID>,
1045    ) -> Entity {
1046        Entity::new_with_attr_partial_value(
1047            uid,
1048            std::iter::empty(),
1049            indirect_ancestors.into_iter().collect(),
1050            parents.into_iter().collect(),
1051            std::iter::empty(),
1052        )
1053    }
1054
1055    #[test]
1056    fn self_in_parents_rejected() {
1057        let uid = EntityUID::with_eid("self");
1058        let e = entity_with(uid.clone(), [uid], []);
1059        assert!(e.try_validate().is_err());
1060    }
1061
1062    #[test]
1063    fn self_in_indirect_ancestors_rejected() {
1064        let uid = EntityUID::with_eid("self");
1065        let e = entity_with(uid.clone(), [], [uid]);
1066        assert!(e.try_validate().is_err());
1067    }
1068
1069    #[test]
1070    fn no_self_ancestor_accepted() {
1071        let e = entity_with(EntityUID::with_eid("ok"), [], []);
1072        assert!(e.try_validate().is_ok());
1073    }
1074
1075    #[test]
1076    fn duplicate_ancestor_rejected() {
1077        let uid = EntityUID::with_eid("child");
1078        let ancestor = EntityUID::with_eid("parent");
1079        let e = entity_with(uid, [ancestor.clone()], [ancestor]);
1080        assert!(e.try_validate().is_err());
1081    }
1082
1083    #[test]
1084    fn action_with_non_action_parent_rejected() {
1085        let uid = EntityUID::from_str("Action::\"view\"").unwrap();
1086        let parent = EntityUID::from_str("User::\"alice\"").unwrap();
1087        let e = entity_with(uid, [parent], []);
1088        assert!(e.try_validate().is_err());
1089    }
1090
1091    #[test]
1092    fn action_with_action_parent_accepted() {
1093        let uid = EntityUID::from_str("Action::\"view\"").unwrap();
1094        let parent = EntityUID::from_str("Action::\"read\"").unwrap();
1095        let e = entity_with(uid, [parent], []);
1096        assert!(e.try_validate().is_ok());
1097    }
1098
1099    #[test]
1100    fn non_action_with_action_parent_accepted() {
1101        let uid = EntityUID::from_str("User::\"alice\"").unwrap();
1102        let parent = EntityUID::from_str("Action::\"read\"").unwrap();
1103        let e = entity_with(uid, [parent], []);
1104        assert!(e.try_validate().is_ok());
1105    }
1106}
cedar_policy_core/ast/entity.rs

cedar_policy_core/ast/
entity.rs
