cedar_policy_core/tpe/
entities.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
17//! This module contains partial entities.
18
19use crate::ast::{Entity, PartialValueToValueError};
20use crate::entities::conformance::err::EntitySchemaConformanceError;
21use crate::entities::err::Duplicate;
22use crate::entities::SchemaType;
23use crate::entities::{Dereference, Entities, TCComputation};
24use crate::tpe::err::{
25    AncestorValidationError, EntitiesConsistencyError, EntitiesError, EntityConsistencyError,
26    EntityValidationError, JsonDeserializationError, MismatchedActionAncestorsError,
27    MismatchedAncestorError, MismatchedAttributeError, MismatchedTagError, MissingEntityError,
28    UnexpectedActionError, UnknownActionComponentError, UnknownAttributeError, UnknownEntityError,
29    UnknownTagError,
30};
31use crate::transitive_closure::{enforce_tc_and_dag, TcError};
32use crate::validator::{
33    CoreSchema, EntityTypeDescription as CoreEntityTypeDescription, ValidatorSchema,
34};
35use crate::{
36    ast::PartialValue,
37    entities::{conformance::EntitySchemaConformanceChecker, Schema},
38};
39use crate::{
40    ast::{EntityUID, Value},
41    entities::{
42        json::{err::JsonDeserializationErrorContext, ValueParser},
43        EntityUidJson,
44    },
45    evaluator::RestrictedEvaluator,
46    extensions::Extensions,
47    jsonvalue::JsonValueWithNoDuplicateKeys,
48};
49use crate::{
50    entities::{conformance::validate_euid, EntityTypeDescription},
51    transitive_closure::{compute_tc, repair_tc, TCNode},
52};
53use itertools::Itertools;
54use serde::{Deserialize, Serialize};
55use serde_with::serde_as;
56use smol_str::SmolStr;
57use std::collections::hash_map::Entry;
58use std::collections::{BTreeMap, HashMap, HashSet};
59
60#[derive(Debug, Clone, PartialEq, Eq, Deserialize, Serialize)]
61#[serde_as]
62#[serde(transparent)]
63struct DeduplicatedMap {
64    #[serde_as(as = "serde_with::MapPreventDuplicates<_,_>")]
65    pub map: HashMap<SmolStr, JsonValueWithNoDuplicateKeys>,
66}
67
68/// Serde JSON format for a single entity
69#[derive(Debug, Clone, PartialEq, Eq, Deserialize, Serialize)]
70pub struct EntityJson {
71    /// UID of the entity, specified in any form accepted by `EntityUidJson`
72    uid: EntityUidJson,
73    /// attributes, whose values can be any JSON value.
74    /// (Probably a `CedarValueJson`, but for schema-based parsing, it could for
75    /// instance be an `EntityUidJson` if we're expecting an entity reference,
76    /// so for now we leave it in its raw json-value form, albeit not allowing
77    /// any duplicate keys in any records that may occur in an attribute value
78    /// (even nested).)
79    #[serde(default)]
80    // the annotation covers duplicates in this `HashMap` itself, while the `JsonValueWithNoDuplicateKeys` covers duplicates in any records contained in attribute values (including recursively)
81    attrs: Option<DeduplicatedMap>,
82    #[serde(default)]
83    /// Parents of the entity, specified in any form accepted by `EntityUidJson`
84    parents: Option<Vec<EntityUidJson>>,
85    #[serde(default)]
86    // the annotation covers duplicates in this `HashMap` itself, while the `JsonValueWithNoDuplicateKeys` covers duplicates in any records contained in tag values (including recursively)
87    // Note that unlike the concrete JSON entity format, when the `tags` field
88    // is missing, it means `tags` are unknown
89    // This is because we need to represent `tags` being unknowns
90    tags: Option<DeduplicatedMap>,
91}
92
93/// The partial entity
94#[derive(Debug, Clone, PartialEq, Eq)]
95pub struct PartialEntity {
96    // The uid of the partial entity
97    uid: EntityUID,
98    // Optional attributes
99    attrs: Option<BTreeMap<SmolStr, Value>>,
100    // Optional ancestors
101    ancestors: Option<HashSet<EntityUID>>,
102    // Optional tags
103    tags: Option<BTreeMap<SmolStr, Value>>,
104}
105
106// An `Entity` without unknowns is a `PartialEntity`
107impl TryFrom<Entity> for PartialEntity {
108    type Error = PartialValueToValueError;
109    fn try_from(value: Entity) -> Result<Self, Self::Error> {
110        let uid = value.uid().clone();
111        let attrs = value
112            .attrs()
113            .map(|(a, v)| Ok((a.clone(), Value::try_from(v.clone())?)))
114            .collect::<Result<BTreeMap<_, _>, PartialValueToValueError>>()?;
115        let ancestors = value.ancestors().cloned().collect();
116        let tags = value
117            .tags()
118            .map(|(a, v)| Ok((a.clone(), Value::try_from(v.clone())?)))
119            .collect::<Result<BTreeMap<_, _>, PartialValueToValueError>>()?;
120        Ok(Self {
121            uid,
122            attrs: Some(attrs),
123            ancestors: Some(ancestors),
124            tags: Some(tags),
125        })
126    }
127}
128
129impl PartialEntity {
130    /// Construct a new [`PartialEntity`]
131    pub fn new(
132        uid: EntityUID,
133        attrs: Option<BTreeMap<SmolStr, Value>>,
134        ancestors: Option<HashSet<EntityUID>>,
135        tags: Option<BTreeMap<SmolStr, Value>>,
136        schema: &ValidatorSchema,
137    ) -> Result<Self, EntitiesError> {
138        let e = Self {
139            uid,
140            attrs,
141            ancestors,
142            tags,
143        };
144        e.validate(schema)?;
145        Ok(e)
146    }
147
148    /// Get the uid of this partial entity
149    pub fn uid(&self) -> &EntityUID {
150        &self.uid
151    }
152
153    /// Get the optional attributes of this partial entity
154    pub fn attrs(&self) -> Option<&BTreeMap<SmolStr, Value>> {
155        self.attrs.as_ref()
156    }
157
158    /// Get the optional ancestors of this partial entity
159    pub fn ancestors(&self) -> Option<&HashSet<EntityUID>> {
160        self.ancestors.as_ref()
161    }
162
163    /// Get the optional tags of this partial entity
164    pub fn tags(&self) -> Option<&BTreeMap<SmolStr, Value>> {
165        self.tags.as_ref()
166    }
167
168    /// Check if an [`Entity`] is consistent with a [`PartialEntity`]
169    pub(crate) fn check_consistency(&self, entity: &Entity) -> Result<(), EntityConsistencyError> {
170        // `Entity` stores values as the old `PartialValue`, but we should never see the unknown here.
171        fn as_values<'a>(
172            pairs: impl Iterator<Item = (&'a SmolStr, &'a PartialValue)>,
173        ) -> Result<BTreeMap<SmolStr, Value>, SmolStr> {
174            pairs
175                .map(|(a, pv)| match pv {
176                    PartialValue::Value(v) => Ok((a.clone(), v.clone())),
177                    PartialValue::Residual(_) => Err(a.clone()),
178                })
179                .collect()
180        }
181
182        if let Some(attrs) = &self.attrs {
183            let other_attrs = as_values(entity.attrs()).map_err(|attr| UnknownAttributeError {
184                uid: self.uid.clone(),
185                attr,
186            })?;
187            if attrs != &other_attrs {
188                return Err(MismatchedAttributeError {
189                    uid: self.uid.clone(),
190                }
191                .into());
192            }
193        }
194        if let Some(ancestors) = &self.ancestors {
195            let other_ancestors: HashSet<EntityUID> = entity.ancestors().cloned().collect();
196            if ancestors != &other_ancestors {
197                return Err(MismatchedAncestorError {
198                    uid: self.uid.clone(),
199                }
200                .into());
201            }
202        }
203        if let Some(tags) = &self.tags {
204            let other_tags = as_values(entity.tags()).map_err(|tag| UnknownTagError {
205                uid: self.uid.clone(),
206                tag,
207            })?;
208            if tags != &other_tags {
209                return Err(MismatchedTagError {
210                    uid: self.uid.clone(),
211                }
212                .into());
213            }
214        }
215        Ok(())
216    }
217}
218
219/// Parse a JSON map of attribute/tag values into concrete [`Value`]s.
220///
221/// `type_of` returns the expected [`SchemaType`] for a given key (tag or attribute). If `uid`'s
222/// entity type is not declared in the schema, an `UnexpectedEntityType` error
223/// is raised.
224fn parse_value_map(
225    map: DeduplicatedMap,
226    uid: &EntityUID,
227    core_schema: &CoreSchema<'_>,
228    vparser: &ValueParser<'_>,
229    type_of: impl Fn(&CoreEntityTypeDescription, &str) -> Option<SchemaType>,
230) -> Result<BTreeMap<SmolStr, Value>, JsonDeserializationError> {
231    let eval = RestrictedEvaluator::new(Extensions::all_available());
232    let ty = core_schema.entity_type(uid.entity_type()).ok_or_else(|| {
233        JsonDeserializationError::Concrete(
234            EntitySchemaConformanceError::unexpected_entity_type(core_schema, uid.clone()).into(),
235        )
236    })?;
237    map.map
238        .into_iter()
239        .map(|(k, v)| {
240            let expr =
241                vparser.val_into_restricted_expr(v.into(), type_of(&ty, &k).as_ref(), &|| {
242                    JsonDeserializationErrorContext::EntityAttribute {
243                        uid: uid.clone(),
244                        attr: k.clone(),
245                    }
246                })?;
247            Ok((k, eval.interpret(expr.as_borrowed())?))
248        })
249        .collect()
250}
251
252/// Parse an [`EntityJson`] into a [`PartialEntity`] according to `schema`
253pub fn parse_ejson(
254    e: EntityJson,
255    schema: &ValidatorSchema,
256) -> Result<PartialEntity, JsonDeserializationError> {
257    let uid = e
258        .uid
259        .into_euid(&|| JsonDeserializationErrorContext::EntityUid)?;
260    let core_schema = CoreSchema::new(schema);
261
262    if uid.is_action() {
263        return Err(UnexpectedActionError { action: uid }.into());
264    }
265    let vparser = ValueParser::new(Extensions::all_available());
266    let attrs = e
267        .attrs
268        .map(|m| parse_value_map(m, &uid, &core_schema, &vparser, |ty, k| ty.attr_type(k)))
269        .transpose()?;
270
271    let ancestors = e
272        .parents
273        .map(|parents| {
274            parents
275                .into_iter()
276                .map(|parent| {
277                    parent
278                        .into_euid(&|| JsonDeserializationErrorContext::EntityParents {
279                            uid: uid.clone(),
280                        })
281                        .map_err(JsonDeserializationError::Concrete)
282                })
283                .collect::<Result<HashSet<_>, _>>()
284        })
285        .transpose()?;
286
287    let tags = e
288        .tags
289        .map(|m| parse_value_map(m, &uid, &core_schema, &vparser, |ty, _| ty.tag_type()))
290        .transpose()?;
291
292    Ok(PartialEntity {
293        uid,
294        attrs,
295        ancestors,
296        tags,
297    })
298}
299
300impl TCNode<EntityUID> for PartialEntity {
301    fn add_edge_to(&mut self, k: EntityUID) {
302        self.add_ancestor(k);
303    }
304
305    fn get_key(&self) -> EntityUID {
306        self.uid.clone()
307    }
308
309    fn has_edge_to(&self, k: &EntityUID) -> bool {
310        match self.ancestors.as_ref() {
311            Some(ancestors) => ancestors.contains(k),
312            None => false,
313        }
314    }
315
316    fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
317        match self.ancestors.as_ref() {
318            Some(ancestors) => Box::new(ancestors.iter()),
319            None => Box::new(std::iter::empty()),
320        }
321    }
322
323    fn reset_edges(&mut self) {}
324}
325
326impl PartialEntity {
327    /// This method should be only called on entities that have known ancestors
328    pub(crate) fn add_ancestor(&mut self, uid: EntityUID) {
329        #[expect(
330            clippy::expect_used,
331            reason = "this method should be only called on entities that have known ancestors"
332        )]
333        self.ancestors
334            .as_mut()
335            .expect("should not be unknown")
336            .insert(uid);
337    }
338
339    /// Validate `self` according to `schema`
340    pub fn validate(&self, schema: &ValidatorSchema) -> Result<(), EntityValidationError> {
341        let core_schema = CoreSchema::new(schema);
342        let uid = &self.uid;
343        let etype = uid.entity_type();
344
345        if self.uid.is_action() {
346            if self.attrs.is_none() || self.tags.is_none() {
347                return Err(UnknownActionComponentError {
348                    action: uid.clone(),
349                }
350                .into());
351            }
352            if let Some(attrs) = &self.attrs {
353                if let Some((attr, _)) = attrs.first_key_value() {
354                    return Err(EntitySchemaConformanceError::unexpected_entity_attr(
355                        uid.clone(),
356                        attr.clone(),
357                    )
358                    .into());
359                }
360            }
361            if let Some(tags) = &self.tags {
362                if let Some((tag, _)) = tags.first_key_value() {
363                    return Err(EntitySchemaConformanceError::unexpected_entity_tag(
364                        uid.clone(),
365                        tag.clone(),
366                    )
367                    .into());
368                }
369            }
370            if let Some(action) = core_schema.action(uid) {
371                if let Some(ancestors) = &self.ancestors {
372                    let schema_ancestors: HashSet<EntityUID> =
373                        action.ancestors().cloned().collect();
374                    if &schema_ancestors != ancestors {
375                        return Err(MismatchedActionAncestorsError {
376                            action: uid.clone(),
377                        }
378                        .into());
379                    }
380                } else {
381                    return Err(UnknownActionComponentError {
382                        action: uid.clone(),
383                    }
384                    .into());
385                }
386            } else {
387                return Err(EntitySchemaConformanceError::UndeclaredAction(
388                    crate::entities::conformance::err::UndeclaredAction { uid: uid.clone() },
389                )
390                .into());
391            }
392            return Ok(());
393        }
394        validate_euid(&core_schema, uid).map_err(EntitySchemaConformanceError::from)?;
395        let schema_etype = core_schema.entity_type(etype).ok_or_else(|| {
396            EntitySchemaConformanceError::unexpected_entity_type(&core_schema, uid.clone())
397        })?;
398        let checker =
399            EntitySchemaConformanceChecker::new(&core_schema, Extensions::all_available());
400        if let Some(ancestors) = &self.ancestors {
401            checker.validate_entity_ancestors(uid, ancestors.iter(), &schema_etype)?;
402        }
403        if let Some(attrs) = &self.attrs {
404            let attrs: BTreeMap<_, PartialValue> = attrs
405                .iter()
406                .map(|(a, v)| (a.clone(), v.clone().into()))
407                .collect();
408            checker.validate_entity_attributes(uid, attrs.iter(), &schema_etype)?;
409        }
410        if let Some(tags) = &self.tags {
411            let tags: BTreeMap<_, PartialValue> = tags
412                .iter()
413                .map(|(a, v)| (a.clone(), v.clone().into()))
414                .collect();
415            checker.validate_tags(uid, tags.iter(), &schema_etype)?;
416        }
417        Ok(())
418    }
419}
420
421// Validate if ancestors are well-formed
422// i.e., ancestors of any ancestor of a `PartialEntity` should not be unknown
423// This ensures that we can always compute a TC for entities with concrete
424// ancestors
425pub(crate) fn validate_concrete_ancestors_concrete(
426    entities: &HashMap<EntityUID, PartialEntity>,
427) -> Result<(), AncestorValidationError> {
428    for e in entities.values() {
429        if let Some(ancestors) = e.ancestors.as_ref() {
430            for ancestor in ancestors {
431                if let Some(ancestor_entity) = entities.get(ancestor) {
432                    if ancestor_entity.ancestors.is_none() {
433                        return Err(AncestorValidationError {
434                            uid: e.uid.clone(),
435                            ancestor: ancestor.clone(),
436                        });
437                    }
438                }
439            }
440        }
441    }
442    Ok(())
443}
444
445/// The partial entity store
446#[derive(Clone, Debug, Default, PartialEq, Eq)]
447pub struct PartialEntities {
448    /// Important internal invariant: for any `Entities` object that exists,
449    /// the `ancestor` relation is transitively closed.
450    entities: HashMap<EntityUID, PartialEntity>,
451}
452
453impl PartialEntities {
454    /// Get an empty partial entities
455    pub fn new() -> Self {
456        Self::default()
457    }
458
459    /// Get an iterator of entities
460    pub fn entities(&self) -> impl Iterator<Item = &PartialEntity> {
461        self.entities.values()
462    }
463
464    /// Compute transitive closure
465    pub fn compute_tc(&mut self) -> Result<(), TcError<EntityUID>> {
466        compute_tc(&mut self.entities, true)
467    }
468
469    /// Check that the tc is computed and forms a dag
470    pub fn enforce_tc_and_dag(&self) -> Result<(), TcError<EntityUID>> {
471        enforce_tc_and_dag(&self.entities)
472    }
473
474    /// Get the `PartialEntity` with this identifier
475    pub fn get(&self, euid: &EntityUID) -> Option<&PartialEntity> {
476        self.entities.get(euid)
477    }
478
479    /// Get the ancestors for this `PartialEntity`
480    ///
481    /// Returns ancestors if this entity exists and its ancestors are known. TPE treats a missing
482    /// entity and unknown ancestors identically. If you need to distinguish them, get the full
483    /// partial entity (if it exists) using [`PartialEntities::get`].
484    pub fn get_ancestors(&self, euid: &EntityUID) -> Option<&HashSet<EntityUID>> {
485        self.get(euid).and_then(|e| e.ancestors())
486    }
487
488    /// Get the attributes for this `PartialEntity`
489    ///
490    /// Returns attributes if this entity exists and its attributes are known. TPE treats a missing
491    /// entity and unknown attributes identically. If you need to distinguish them, get the full
492    /// partial entity (if it exists) using [`PartialEntities::get`].
493    pub fn get_attrs(&self, euid: &EntityUID) -> Option<&BTreeMap<SmolStr, Value>> {
494        self.get(euid).and_then(|e| e.attrs())
495    }
496
497    /// Get the tags for this `PartialEntity`
498    ///
499    /// Returns tags if this entity exists and its tags are known. TPE treats a missing entity and
500    /// unknown tags identically. If you need to distinguish them, get the full partial entity (if
501    /// it exists) using [`PartialEntities::get`].
502    pub fn get_tags(&self, euid: &EntityUID) -> Option<&BTreeMap<SmolStr, Value>> {
503        self.get(euid).and_then(|e| e.tags())
504    }
505
506    /// Check if there is a `PartialEntity` with identifier
507    pub fn contains_entity(&self, euid: &EntityUID) -> bool {
508        self.entities.contains_key(euid)
509    }
510
511    /// Shared internal constructor for building from maps. Validates each
512    /// entity, concreteness of the ancestor hierarchy, and optionally compute
513    /// the transitive closure. Also inserts actions entities from the schema.
514    fn from_entities_map(
515        entities: HashMap<EntityUID, PartialEntity>,
516        schema: &ValidatorSchema,
517        compute_tc: bool,
518    ) -> Result<Self, EntitiesError> {
519        entities.values().try_for_each(|e| e.validate(schema))?;
520        validate_concrete_ancestors_concrete(&entities)?;
521        let mut entities = Self { entities };
522        if compute_tc {
523            entities.compute_tc()?;
524        }
525        entities.insert_actions(schema);
526        Ok(entities)
527    }
528
529    fn collect_unique(
530        entities: impl Iterator<Item = PartialEntity>,
531    ) -> Result<HashMap<EntityUID, PartialEntity>, EntitiesError> {
532        let mut map: HashMap<EntityUID, PartialEntity> = HashMap::new();
533        for entity in entities {
534            match map.entry(entity.uid.clone()) {
535                Entry::Vacant(e) => {
536                    e.insert(entity);
537                }
538                Entry::Occupied(e) => {
539                    return Err(Duplicate {
540                        euid: e.key().clone(),
541                    }
542                    .into())
543                }
544            }
545        }
546        Ok(map)
547    }
548
549    /// Construct `PartialEntities` from `Entities`, ensuring that the entities are valid.
550    /// TC is already computed in the source `Entities`, so we skip recomputation.
551    pub fn from_concrete(
552        entities: Entities,
553        schema: &ValidatorSchema,
554    ) -> Result<Self, EntitiesError> {
555        let entities_map: HashMap<EntityUID, PartialEntity> = entities
556            .into_iter()
557            .map(|e| e.try_into().map(|e: PartialEntity| (e.uid.clone(), e)))
558            .try_collect()?;
559        // TC is already computed in the source Entities — the conversion to
560        // PartialEntity preserves all ancestors (direct + indirect).
561        Self::from_entities_map(entities_map, schema, false)
562    }
563
564    /// Construct `PartialEntities` from an iterator
565    pub fn from_entities(
566        entity_mappings: impl Iterator<Item = PartialEntity>,
567        schema: &ValidatorSchema,
568    ) -> Result<Self, EntitiesError> {
569        Self::from_entities_map(Self::collect_unique(entity_mappings)?, schema, true)
570    }
571
572    /// Add a partial entity without checking if it conforms to the schema,
573    /// assuming the TC is already computed.
574    /// Errors on duplicate entries.
575    pub(crate) fn add_entity_trusted(
576        &mut self,
577        uid: EntityUID,
578        entity: PartialEntity,
579    ) -> Result<(), EntitiesError> {
580        match self.entities.entry(uid) {
581            Entry::Vacant(e) => {
582                e.insert(entity);
583            }
584            Entry::Occupied(e) => {
585                return Err(Duplicate {
586                    euid: e.key().clone(),
587                }
588                .into())
589            }
590        }
591
592        Ok(())
593    }
594
595    /// Add a set of partial entities to this store,
596    /// erroring on duplicates.
597    pub fn add_entities(
598        &mut self,
599        entity_mappings: impl Iterator<Item = (EntityUID, PartialEntity)>,
600        schema: &ValidatorSchema,
601        tc_computation: TCComputation,
602    ) -> Result<(), EntitiesError> {
603        let mut entities_touched: HashSet<EntityUID> = HashSet::new();
604        for (id, entity) in entity_mappings {
605            entity.validate(schema)?;
606            entities_touched.insert(id.clone());
607            self.add_entity_trusted(id, entity)?;
608        }
609
610        validate_concrete_ancestors_concrete(&self.entities)?;
611
612        match tc_computation {
613            TCComputation::AssumeAlreadyComputed => (),
614            TCComputation::EnforceAlreadyComputed => {
615                self.enforce_tc_and_dag()?;
616            }
617            TCComputation::ComputeNow => {
618                for entity in self.entities.values() {
619                    if let Some(ancestors) = entity.ancestors.as_ref() {
620                        if !entities_touched.is_disjoint(ancestors) {
621                            entities_touched.insert(entity.uid.clone());
622                        }
623                    }
624                }
625                repair_tc(&entities_touched, &mut self.entities, true)?;
626            }
627        }
628        Ok(())
629    }
630
631    // Insert action entities from the schema
632    // Overwriting existing action entities is fine because they should come
633    // from schema or be consistent with schema anyways
634    fn insert_actions(&mut self, schema: &ValidatorSchema) {
635        for (uid, action) in &schema.actions {
636            self.entities.insert(
637                uid.clone(),
638                #[expect(
639                    clippy::unwrap_used,
640                    reason = "action entities do not contain unknowns"
641                )]
642                action.as_ref().clone().try_into().unwrap(),
643            );
644        }
645    }
646
647    /// Construct [`PartialEntities`] from a JSON list
648    pub fn from_json_value(
649        value: serde_json::Value,
650        schema: &ValidatorSchema,
651    ) -> Result<Self, EntitiesError> {
652        let entities: Vec<EntityJson> = serde_json::from_value(value)
653            .map_err(|e| JsonDeserializationError::Concrete(e.into()))?;
654        let parsed = entities
655            .into_iter()
656            .map(|e| parse_ejson(e, schema))
657            .collect::<Result<Vec<_>, _>>()?;
658        Self::from_entities_map(Self::collect_unique(parsed.into_iter())?, schema, true)
659    }
660
661    /// Check if [`PartialEntities`] are consistent with [`Entities`]
662    pub fn check_consistency(&self, concrete: &Entities) -> Result<(), EntitiesConsistencyError> {
663        for (uid, e) in &self.entities {
664            match concrete.entity(uid) {
665                Dereference::NoSuchEntity => {
666                    return Err(MissingEntityError { uid: uid.clone() }.into());
667                }
668                Dereference::Residual(_) => {
669                    return Err(UnknownEntityError { uid: uid.clone() }.into());
670                }
671                Dereference::Data(entity) => e.check_consistency(entity)?,
672            }
673        }
674        Ok(())
675    }
676}
677
678#[cfg(test)]
679mod tests {
680    use std::collections::{BTreeMap, HashMap, HashSet};
681
682    use crate::tpe::err::AncestorValidationError;
683    use crate::validator::ValidatorSchema;
684    use crate::{
685        ast::{EntityUID, Value},
686        extensions::Extensions,
687    };
688    use cool_asserts::assert_matches;
689
690    use super::{
691        parse_ejson, validate_concrete_ancestors_concrete, EntityJson, PartialEntities,
692        PartialEntity,
693    };
694
695    #[track_caller]
696    fn basic_schema() -> ValidatorSchema {
697        ValidatorSchema::from_cedarschema_str(
698            r#"
699        entity A {
700            a? : String,
701            b? : Long,
702            c? : {"x" : Bool}
703        } tags Long;
704         action a appliesTo {
705           principal : A,
706           resource : A
707         };
708        "#,
709            Extensions::all_available(),
710        )
711        .unwrap()
712        .0
713    }
714
715    #[test]
716    fn basic() {
717        let schema = basic_schema();
718        // unlike the existing JSON format, absence of `tags` or `tags` being
719        // `null` means unknown tags, as opposed to empty tags
720        let json = serde_json::json!(
721            {
722                "uid" : {
723                    "type" : "A",
724                    "id" : "",
725                },
726                "tags" : null,
727            }
728        );
729        let ejson: EntityJson = serde_json::from_value(json).expect("should parse");
730        assert_matches!(parse_ejson(ejson, &schema), Ok(e) => {
731            assert_eq!(e, PartialEntity { uid: r#"A::"""#.parse().unwrap(), attrs: None, ancestors: None, tags: None });
732        });
733
734        // empty tags need to be specified explicitly
735        let schema = basic_schema();
736        let json = serde_json::json!(
737            {
738                "uid" : {
739                    "type" : "A",
740                    "id" : "",
741                },
742                "tags" : {},
743            }
744        );
745        let ejson: EntityJson = serde_json::from_value(json).expect("should parse");
746        assert_matches!(parse_ejson(ejson, &schema), Ok(e) => {
747            assert_eq!(e, PartialEntity { uid: r#"A::"""#.parse().unwrap(), attrs: None, ancestors: None, tags: Some(BTreeMap::default()) });
748        });
749
750        let schema = basic_schema();
751        let json = serde_json::json!(
752            {
753                "uid" : {
754                    "type" : "A",
755                    "id" : "",
756                },
757                "parents" : [],
758                "attrs" : {},
759                "tags" : {},
760            }
761        );
762        let ejson: EntityJson = serde_json::from_value(json).expect("should parse");
763        assert_matches!(parse_ejson(ejson, &schema), Ok(e) => {
764            assert_eq!(e, PartialEntity { uid: r#"A::"""#.parse().unwrap(), attrs: Some(BTreeMap::new()), ancestors: Some(HashSet::default()), tags: Some(BTreeMap::default()) });
765        });
766
767        let schema = basic_schema();
768        let json = serde_json::json!(
769            {
770                "uid" : {
771                    "type" : "A",
772                    "id" : "",
773                },
774                "parents" : [],
775                "attrs" : {
776                    "b" : 1,
777                    "c" : {"x": false},
778                },
779                "tags" : {},
780            }
781        );
782        let ejson: EntityJson = serde_json::from_value(json).expect("should parse");
783        assert_matches!(parse_ejson(ejson, &schema), Ok(e) => {
784            assert_eq!(e, PartialEntity { uid: r#"A::"""#.parse().unwrap(), attrs: Some(BTreeMap::from_iter([("b".into(), 1.into()), ("c".into(), Value::record(std::iter::once(("x", false)), None)
785            )])), ancestors: Some(HashSet::default()), tags: Some(BTreeMap::default()) });
786        });
787    }
788
789    #[test]
790    fn invalid_hierarchy() {
791        let uid_a: EntityUID = r#"A::"a""#.parse().unwrap();
792        let uid_b: EntityUID = r#"A::"b""#.parse().unwrap();
793        assert_matches!(
794            validate_concrete_ancestors_concrete(&HashMap::from_iter([
795                (
796                    uid_a.clone(),
797                    PartialEntity {
798                        uid: uid_a,
799                        ancestors: Some(HashSet::from_iter([uid_b.clone()])),
800                        attrs: None,
801                        tags: None
802                    }
803                ),
804                (
805                    uid_b.clone(),
806                    PartialEntity {
807                        uid: uid_b,
808                        ancestors: None,
809                        attrs: None,
810                        tags: None
811                    }
812                )
813            ])),
814            Err(AncestorValidationError { .. })
815        )
816    }
817
818    #[test]
819    fn tc_computation() {
820        let a = PartialEntity {
821            uid: r#"E::"a""#.parse().unwrap(),
822            attrs: None,
823            ancestors: Some(HashSet::from_iter([
824                r#"E::"b""#.parse().unwrap(),
825                r#"E::"c""#.parse().unwrap(),
826            ])),
827            tags: None,
828        };
829        let b = PartialEntity {
830            uid: r#"E::"b""#.parse().unwrap(),
831            attrs: None,
832            ancestors: Some(HashSet::from_iter([r#"E::"d""#.parse().unwrap()])),
833            tags: None,
834        };
835        let c = PartialEntity {
836            uid: r#"E::"c""#.parse().unwrap(),
837            attrs: None,
838            ancestors: Some(HashSet::from_iter([r#"E::"e""#.parse().unwrap()])),
839            tags: None,
840        };
841        let e = PartialEntity {
842            uid: r#"E::"e""#.parse().unwrap(),
843            attrs: None,
844            ancestors: Some(HashSet::from_iter([r#"E::"f""#.parse().unwrap()])),
845            tags: None,
846        };
847        let x = PartialEntity {
848            uid: r#"E::"x""#.parse().unwrap(),
849            attrs: None,
850            ancestors: None,
851            tags: None,
852        };
853        let mut entities = PartialEntities {
854            entities: vec![a, b, c, e, x]
855                .into_iter()
856                .map(|e| (e.uid.clone(), e))
857                .collect(),
858        };
859        entities.compute_tc().expect("should compute tc");
860        assert_eq!(
861            entities
862                .entities
863                .get(&r#"E::"a""#.parse().unwrap())
864                .as_ref()
865                .unwrap()
866                .ancestors
867                .clone()
868                .unwrap(),
869            HashSet::from_iter([
870                r#"E::"b""#.parse().unwrap(),
871                r#"E::"c""#.parse().unwrap(),
872                r#"E::"d""#.parse().unwrap(),
873                r#"E::"e""#.parse().unwrap(),
874                r#"E::"f""#.parse().unwrap()
875            ])
876        );
877        assert_eq!(
878            entities
879                .entities
880                .get(&r#"E::"b""#.parse().unwrap())
881                .as_ref()
882                .unwrap()
883                .ancestors
884                .clone()
885                .unwrap(),
886            HashSet::from_iter([r#"E::"d""#.parse().unwrap(),])
887        );
888        assert_eq!(
889            entities
890                .entities
891                .get(&r#"E::"c""#.parse().unwrap())
892                .as_ref()
893                .unwrap()
894                .ancestors
895                .clone()
896                .unwrap(),
897            HashSet::from_iter([r#"E::"e""#.parse().unwrap(), r#"E::"f""#.parse().unwrap()])
898        );
899        assert_eq!(
900            entities
901                .entities
902                .get(&r#"E::"e""#.parse().unwrap())
903                .as_ref()
904                .unwrap()
905                .ancestors
906                .clone()
907                .unwrap(),
908            HashSet::from_iter([r#"E::"f""#.parse().unwrap()])
909        );
910        assert_eq!(
911            entities
912                .entities
913                .get(&r#"E::"x""#.parse().unwrap())
914                .as_ref()
915                .unwrap()
916                .ancestors,
917            None
918        );
919    }
920}
921
922#[cfg(test)]
923mod test_validate {
924    use super::*;
925    use crate::entities::conformance::err::EntitySchemaConformanceError;
926    use crate::tpe::err::{
927        EntityValidationError, MismatchedActionAncestorsError, UnknownActionComponentError,
928    };
929    use cool_asserts::assert_matches;
930
931    fn test_schema() -> ValidatorSchema {
932        ValidatorSchema::from_cedarschema_str(
933            r#"
934            entity User {
935                name: String,
936            } tags String;
937
938            entity Resource;
939
940            action view appliesTo {
941                principal: User,
942                resource: Resource
943            };
944            "#,
945            Extensions::all_available(),
946        )
947        .unwrap()
948        .0
949    }
950
951    #[test]
952    fn valid_entity() {
953        let schema = test_schema();
954        let entity = PartialEntity {
955            uid: "User::\"alice\"".parse().unwrap(),
956            attrs: Some(BTreeMap::from_iter([("name".into(), Value::from("Alice"))])),
957            ancestors: Some(HashSet::new()),
958            tags: Some(BTreeMap::from_iter([(
959                "department".into(),
960                Value::from("Engineering"),
961            )])),
962        };
963
964        assert_matches!(entity.validate(&schema), Ok(()));
965    }
966
967    #[test]
968    fn valid_action() {
969        let schema = test_schema();
970        let action = PartialEntity {
971            uid: "Action::\"view\"".parse().unwrap(),
972            attrs: Some(BTreeMap::new()),
973            ancestors: Some(HashSet::new()),
974            tags: Some(BTreeMap::new()),
975        };
976
977        assert_matches!(action.validate(&schema), Ok(()));
978    }
979
980    #[test]
981    fn invalid_action_with_unknown_ancestors() {
982        let schema = test_schema();
983        let action = PartialEntity {
984            uid: "Action::\"view\"".parse().unwrap(),
985            attrs: Some(BTreeMap::new()),
986            ancestors: None,
987            tags: Some(BTreeMap::new()),
988        };
989
990        assert_matches!(
991            action.validate(&schema),
992            Err(EntityValidationError::UnknownActionComponent(
993                UnknownActionComponentError { .. }
994            ))
995        );
996    }
997
998    #[test]
999    fn invalid_action_with_unknown_tags() {
1000        let schema = test_schema();
1001        let action = PartialEntity {
1002            uid: "Action::\"view\"".parse().unwrap(),
1003            attrs: Some(BTreeMap::new()),
1004            ancestors: Some(HashSet::new()),
1005            tags: None,
1006        };
1007
1008        assert_matches!(
1009            action.validate(&schema),
1010            Err(EntityValidationError::UnknownActionComponent(
1011                UnknownActionComponentError { .. }
1012            ))
1013        );
1014    }
1015
1016    #[test]
1017    fn invalid_action_with_unknown_attrs() {
1018        let schema = test_schema();
1019        let action = PartialEntity {
1020            uid: "Action::\"view\"".parse().unwrap(),
1021            attrs: None,
1022            ancestors: Some(HashSet::new()),
1023            tags: Some(BTreeMap::new()),
1024        };
1025
1026        assert_matches!(
1027            action.validate(&schema),
1028            Err(EntityValidationError::UnknownActionComponent(
1029                UnknownActionComponentError { .. }
1030            ))
1031        );
1032    }
1033
1034    #[test]
1035    fn invalid_action_with_unexpected_attr() {
1036        let schema = test_schema();
1037        let action = PartialEntity {
1038            uid: "Action::\"view\"".parse().unwrap(),
1039            attrs: Some(BTreeMap::from_iter([(
1040                "unexpected_attr".into(),
1041                Value::from("value"),
1042            )])),
1043            ancestors: Some(HashSet::new()),
1044            tags: Some(BTreeMap::new()),
1045        };
1046
1047        assert_matches!(
1048            action.validate(&schema),
1049            Err(EntityValidationError::Concrete(
1050                EntitySchemaConformanceError::UnexpectedEntityAttr(_)
1051            ))
1052        );
1053    }
1054
1055    #[test]
1056    fn invalid_action_with_unexpected_tag() {
1057        let schema = test_schema();
1058        let action = PartialEntity {
1059            uid: "Action::\"view\"".parse().unwrap(),
1060            attrs: Some(BTreeMap::new()),
1061            ancestors: Some(HashSet::new()),
1062            tags: Some(BTreeMap::from_iter([(
1063                "unexpected_tag".into(),
1064                Value::from("value"),
1065            )])),
1066        };
1067
1068        assert_matches!(
1069            action.validate(&schema),
1070            Err(EntityValidationError::Concrete(
1071                EntitySchemaConformanceError::UnexpectedEntityTag(_)
1072            ))
1073        );
1074    }
1075
1076    #[test]
1077    fn invalid_action_with_incorrect_ancestors() {
1078        let schema = test_schema();
1079        let action = PartialEntity {
1080            uid: "Action::\"view\"".parse().unwrap(),
1081            attrs: Some(BTreeMap::new()),
1082            ancestors: Some(HashSet::from_iter(["Action::\"other\"".parse().unwrap()])),
1083            tags: Some(BTreeMap::new()),
1084        };
1085
1086        assert_matches!(
1087            action.validate(&schema),
1088            Err(EntityValidationError::MismatchedActionAncestors(
1089                MismatchedActionAncestorsError { .. }
1090            ))
1091        );
1092    }
1093
1094    #[test]
1095    fn invalid_unexpected_action() {
1096        let schema = test_schema();
1097        let action = PartialEntity {
1098            uid: "Action::\"other\"".parse().unwrap(),
1099            attrs: Some(BTreeMap::new()),
1100            ancestors: Some(HashSet::new()),
1101            tags: Some(BTreeMap::new()),
1102        };
1103
1104        assert_matches!(
1105            action.validate(&schema),
1106            Err(EntityValidationError::Concrete(
1107                EntitySchemaConformanceError::UndeclaredAction(_)
1108            ))
1109        );
1110    }
1111
1112    #[test]
1113    fn invalid_unexpected_entity_type() {
1114        let schema = test_schema();
1115        let entity = PartialEntity {
1116            uid: "UnknownType::\"test\"".parse().unwrap(),
1117            attrs: None,
1118            ancestors: None,
1119            tags: None,
1120        };
1121
1122        assert_matches!(
1123            entity.validate(&schema),
1124            Err(EntityValidationError::Concrete(
1125                EntitySchemaConformanceError::UnexpectedEntityType(_)
1126            ))
1127        );
1128    }
1129
1130    #[test]
1131    fn invalid_entity_invalid_ancestor() {
1132        let schema = test_schema();
1133        let entity = PartialEntity {
1134            uid: "User::\"alice\"".parse().unwrap(),
1135            attrs: None,
1136            ancestors: Some(HashSet::from_iter(["Resource::\"doc1\"".parse().unwrap()])),
1137            tags: None,
1138        };
1139
1140        assert_matches!(
1141            entity.validate(&schema),
1142            Err(EntityValidationError::Concrete(
1143                EntitySchemaConformanceError::InvalidAncestorType(_)
1144            ))
1145        );
1146    }
1147
1148    #[test]
1149    fn invalid_entity_invalid_attr() {
1150        let schema = test_schema();
1151        let entity = PartialEntity {
1152            uid: "User::\"alice\"".parse().unwrap(),
1153            attrs: Some(BTreeMap::from_iter([("name".into(), Value::from(42))])),
1154            ancestors: None,
1155            tags: None,
1156        };
1157
1158        assert_matches!(
1159            entity.validate(&schema),
1160            Err(EntityValidationError::Concrete(
1161                EntitySchemaConformanceError::TypeMismatch(_)
1162            ))
1163        );
1164    }
1165
1166    #[test]
1167    fn invalid_entity_invalid_tag() {
1168        let schema = test_schema();
1169        let entity = PartialEntity {
1170            uid: "User::\"alice\"".parse().unwrap(),
1171            attrs: None,
1172            ancestors: None,
1173            tags: Some(BTreeMap::from_iter([(
1174                "department".into(),
1175                Value::from(42),
1176            )])),
1177        };
1178
1179        assert_matches!(
1180            entity.validate(&schema),
1181            Err(EntityValidationError::Concrete(
1182                EntitySchemaConformanceError::TypeMismatch(_)
1183            ))
1184        );
1185    }
1186}
1187
1188#[cfg(test)]
1189mod test_consistency {
1190    use cool_asserts::assert_matches;
1191
1192    use crate::{
1193        ast::Entity,
1194        entities::{Entities, EntityJsonParser, TCComputation},
1195        extensions::Extensions,
1196        tpe::{self, entities::PartialEntities},
1197        validator::ValidatorSchema,
1198    };
1199
1200    fn schema() -> ValidatorSchema {
1201        ValidatorSchema::from_cedarschema_str(
1202            "entity A { a: Bool } tags Long;",
1203            Extensions::all_available(),
1204        )
1205        .unwrap()
1206        .0
1207    }
1208
1209    #[track_caller]
1210    fn parse_concrete_json(entity_json: serde_json::Value) -> Entity {
1211        let eparser: EntityJsonParser<'_, '_> =
1212            EntityJsonParser::new(None, Extensions::all_available(), TCComputation::ComputeNow);
1213        eparser.single_from_json_value(entity_json).unwrap()
1214    }
1215
1216    #[test]
1217    fn consistent_eq_entity() {
1218        let entity_json = serde_json::json!(
1219            {
1220                "uid" : { "type" : "A", "id" : "foo", },
1221                "attrs": { "a": false },
1222                "tags" : { "t": 0 },
1223                "parents" : [ {"type": "A", "id": "bar"} ],
1224            }
1225        );
1226        let partial_entity = tpe::entities::parse_ejson(
1227            serde_json::from_value(entity_json.clone()).unwrap(),
1228            &schema(),
1229        )
1230        .unwrap();
1231        let entity = parse_concrete_json(entity_json);
1232        assert_matches!(partial_entity.check_consistency(&entity), Ok(()))
1233    }
1234
1235    #[test]
1236    fn consistent_missing_attrs() {
1237        let partial_entity_json = serde_json::json!(
1238            {
1239                "uid" : { "type" : "A", "id" : "foo", },
1240                "tags" : { "t": 0 },
1241                "parents" : [ {"type": "A", "id": "bar"} ],
1242            }
1243        );
1244        let concrete_entity_json = serde_json::json!(
1245            {
1246                "uid" : { "type" : "A", "id" : "foo", },
1247                "attrs": { "a": false },
1248                "tags" : { "t": 0 },
1249                "parents" : [ {"type": "A", "id": "bar"} ],
1250            }
1251        );
1252        let partial_entity = tpe::entities::parse_ejson(
1253            serde_json::from_value(partial_entity_json).unwrap(),
1254            &schema(),
1255        )
1256        .unwrap();
1257        let entity = parse_concrete_json(concrete_entity_json);
1258        assert_matches!(partial_entity.check_consistency(&entity), Ok(()))
1259    }
1260
1261    #[test]
1262    fn consistent_missing_tags() {
1263        let partial_entity_json = serde_json::json!(
1264            {
1265                "uid" : { "type" : "A", "id" : "foo", },
1266                "attrs": { "a": false },
1267                "parents" : [ {"type": "A", "id": "bar"} ],
1268            }
1269        );
1270        let concrete_entity_json = serde_json::json!(
1271            {
1272                "uid" : { "type" : "A", "id" : "foo", },
1273                "attrs": { "a": false },
1274                "tags" : { "t": 0 },
1275                "parents" : [ {"type": "A", "id": "bar"} ],
1276            }
1277        );
1278        let partial_entity = tpe::entities::parse_ejson(
1279            serde_json::from_value(partial_entity_json).unwrap(),
1280            &schema(),
1281        )
1282        .unwrap();
1283        let entity = parse_concrete_json(concrete_entity_json);
1284        assert_matches!(partial_entity.check_consistency(&entity), Ok(()))
1285    }
1286
1287    #[test]
1288    fn consistent_missing_parents() {
1289        let partial_entity_json = serde_json::json!(
1290            {
1291                "uid" : { "type" : "A", "id" : "foo", },
1292                "attrs": { "a": false },
1293                "tags" : { "t": 0 },
1294            }
1295        );
1296        let concrete_entity_json = serde_json::json!(
1297            {
1298                "uid" : { "type" : "A", "id" : "foo", },
1299                "attrs": { "a": false },
1300                "tags" : { "t": 0 },
1301                "parents" : [ {"type": "A", "id": "bar"} ],
1302            }
1303        );
1304        let partial_entity = tpe::entities::parse_ejson(
1305            serde_json::from_value(partial_entity_json).unwrap(),
1306            &schema(),
1307        )
1308        .unwrap();
1309        let entity = parse_concrete_json(concrete_entity_json);
1310        assert_matches!(partial_entity.check_consistency(&entity), Ok(()))
1311    }
1312
1313    #[test]
1314    fn not_consistent_different_attrs() {
1315        let partial_entity_json = serde_json::json!(
1316            {
1317                "uid" : { "type" : "A", "id" : "foo", },
1318                "attrs": { "a": true },
1319            }
1320        );
1321        let concrete_entity_json = serde_json::json!(
1322            {
1323                "uid" : { "type" : "A", "id" : "foo", },
1324                "attrs": { "a": false },
1325                "tags" : { "t": 0 },
1326                "parents" : [ {"type": "A", "id": "bar"} ],
1327            }
1328        );
1329        let partial_entity = tpe::entities::parse_ejson(
1330            serde_json::from_value(partial_entity_json).unwrap(),
1331            &schema(),
1332        )
1333        .unwrap();
1334        let entity = parse_concrete_json(concrete_entity_json);
1335        assert_matches!(
1336            partial_entity.check_consistency(&entity),
1337            Err(tpe::err::EntityConsistencyError::MismatchedAttribute(_))
1338        )
1339    }
1340
1341    #[test]
1342    fn not_consistent_different_tags() {
1343        let partial_entity_json = serde_json::json!(
1344            {
1345                "uid" : { "type" : "A", "id" : "foo", },
1346                "tags" : { "t": 1 },
1347            }
1348        );
1349        let concrete_entity_json = serde_json::json!(
1350            {
1351                "uid" : { "type" : "A", "id" : "foo", },
1352                "attrs": { "a": false },
1353                "tags" : { "t": 0 },
1354                "parents" : [ {"type": "A", "id": "bar"} ],
1355            }
1356        );
1357        let partial_entity = tpe::entities::parse_ejson(
1358            serde_json::from_value(partial_entity_json).unwrap(),
1359            &schema(),
1360        )
1361        .unwrap();
1362        let entity = parse_concrete_json(concrete_entity_json);
1363        assert_matches!(
1364            partial_entity.check_consistency(&entity),
1365            Err(tpe::err::EntityConsistencyError::MismatchedTag(_))
1366        )
1367    }
1368
1369    #[test]
1370    fn not_consistent_different_parents() {
1371        let partial_entity_json = serde_json::json!(
1372            {
1373                "uid" : { "type" : "A", "id" : "foo", },
1374                "parents" : [ {"type": "A", "id": "baz"} ],  // Different parent
1375            }
1376        );
1377        let concrete_entity_json = serde_json::json!(
1378            {
1379                "uid" : { "type" : "A", "id" : "foo", },
1380                "attrs": { "a": false },
1381                "tags" : { "t": 0 },
1382                "parents" : [ {"type": "A", "id": "bar"} ],  // Different parent
1383            }
1384        );
1385        let partial_entity = tpe::entities::parse_ejson(
1386            serde_json::from_value(partial_entity_json).unwrap(),
1387            &schema(),
1388        )
1389        .unwrap();
1390        let entity = parse_concrete_json(concrete_entity_json);
1391        assert_matches!(
1392            partial_entity.check_consistency(&entity),
1393            Err(tpe::err::EntityConsistencyError::MismatchedAncestor(_))
1394        )
1395    }
1396
1397    #[test]
1398    fn not_consistent_missing_entity() {
1399        let partial_entity_json = serde_json::json!(
1400            [{ "uid" : { "type" : "A", "id" : "foo", }, }]
1401        );
1402        let partial_entities = PartialEntities::from_json_value(
1403            serde_json::from_value(partial_entity_json).unwrap(),
1404            &schema(),
1405        )
1406        .unwrap();
1407        let concrete_entities = Entities::new();
1408        assert_matches!(
1409            partial_entities.check_consistency(&concrete_entities),
1410            Err(tpe::err::EntitiesConsistencyError::MissingEntity(_))
1411        )
1412    }
1413}
cedar_policy_core/tpe/entities.rs

cedar_policy_core/tpe/
entities.rs
