cedar_policy_core/ast/
entity.rs

1/*
2 * Copyright 2022-2023 Amazon.com, Inc. or its affiliates. All Rights Reserved.
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::evaluator::{EvaluationError, RestrictedEvaluator};
19use crate::extensions::Extensions;
20use crate::parser::err::ParseErrors;
21use crate::transitive_closure::TCNode;
22use crate::FromNormalizedStr;
23use itertools::Itertools;
24use serde::{Deserialize, Serialize};
25use serde_with::{serde_as, TryFromInto};
26use smol_str::SmolStr;
27use std::collections::{HashMap, HashSet};
28use thiserror::Error;
29
30/// We support two types of entities. The first is a nominal type (e.g., User, Action)
31/// and the second is an unspecified type, which is used (internally) to represent cases
32/// where the input request does not provide a principal, action, and/or resource.
33#[derive(Serialize, Deserialize, PartialEq, Eq, Debug, Clone, Hash, PartialOrd, Ord)]
34#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
35pub enum EntityType {
36    /// Concrete nominal type
37    Specified(Name),
38    /// Unspecified
39    Unspecified,
40}
41
42impl EntityType {
43    /// Is this an Action entity type
44    pub fn is_action(&self) -> bool {
45        match self {
46            Self::Specified(name) => name.basename() == &Id::new_unchecked("Action"),
47            Self::Unspecified => false,
48        }
49    }
50}
51
52// Note: the characters '<' and '>' are not allowed in `Name`s, so the display for
53// `Unspecified` never conflicts with `Specified(name)`.
54impl std::fmt::Display for EntityType {
55    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
56        match self {
57            Self::Unspecified => write!(f, "<Unspecified>"),
58            Self::Specified(name) => write!(f, "{}", name),
59        }
60    }
61}
62
63/// Unique ID for an entity. These represent entities in the AST.
64#[derive(Serialize, Deserialize, PartialEq, Eq, Debug, Clone, Hash, PartialOrd, Ord)]
65#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
66pub struct EntityUID {
67    /// Typename of the entity
68    ty: EntityType,
69    /// EID of the entity
70    eid: Eid,
71}
72
73impl StaticallyTyped for EntityUID {
74    fn type_of(&self) -> Type {
75        Type::Entity {
76            ty: self.ty.clone(),
77        }
78    }
79}
80
81impl EntityUID {
82    /// Create an `EntityUID` with the given string as its EID.
83    /// Useful for testing.
84    #[cfg(test)]
85    pub(crate) fn with_eid(eid: &str) -> Self {
86        Self {
87            ty: Self::test_entity_type(),
88            eid: Eid(eid.into()),
89        }
90    }
91    // by default, Coverlay does not track coverage for lines after a line
92    // containing #[cfg(test)].
93    // we use the following sentinel to "turn back on" coverage tracking for
94    // remaining lines of this file, until the next #[cfg(test)]
95    // GRCOV_BEGIN_COVERAGE
96
97    /// The type of entities created with the above `with_eid()`.
98    #[cfg(test)]
99    pub(crate) fn test_entity_type() -> EntityType {
100        let name = Name::parse_unqualified_name("test_entity_type")
101            .expect("test_entity_type should be a valid identifier");
102        EntityType::Specified(name)
103    }
104    // by default, Coverlay does not track coverage for lines after a line
105    // containing #[cfg(test)].
106    // we use the following sentinel to "turn back on" coverage tracking for
107    // remaining lines of this file, until the next #[cfg(test)]
108    // GRCOV_BEGIN_COVERAGE
109
110    /// Create an `EntityUID` with the given (unqualified) typename, and the given string as its EID.
111    pub fn with_eid_and_type(typename: &str, eid: &str) -> Result<Self, ParseErrors> {
112        Ok(Self {
113            ty: EntityType::Specified(Name::parse_unqualified_name(typename)?),
114            eid: Eid(eid.into()),
115        })
116    }
117
118    /// Split into the `EntityType` representing the entity type, and the `Eid`
119    /// representing its name
120    pub fn components(self) -> (EntityType, Eid) {
121        (self.ty, self.eid)
122    }
123
124    /// Create a nominally-typed `EntityUID` with the given typename and EID
125    pub fn from_components(name: Name, eid: Eid) -> Self {
126        Self {
127            ty: EntityType::Specified(name),
128            eid,
129        }
130    }
131
132    /// Create an unspecified `EntityUID` with the given EID
133    pub fn unspecified_from_eid(eid: Eid) -> Self {
134        Self {
135            ty: EntityType::Unspecified,
136            eid,
137        }
138    }
139
140    /// Get the type component.
141    pub fn entity_type(&self) -> &EntityType {
142        &self.ty
143    }
144
145    /// Get the Eid component.
146    pub fn eid(&self) -> &Eid {
147        &self.eid
148    }
149
150    /// Does this EntityUID refer to an action entity?
151    pub fn is_action(&self) -> bool {
152        self.entity_type().is_action()
153    }
154}
155
156impl std::fmt::Display for EntityUID {
157    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
158        write!(f, "{}::\"{}\"", self.entity_type(), self.eid)
159    }
160}
161
162// allow `.parse()` on a string to make an `EntityUID`
163impl std::str::FromStr for EntityUID {
164    type Err = ParseErrors;
165
166    fn from_str(s: &str) -> Result<Self, Self::Err> {
167        crate::parser::parse_euid(s)
168    }
169}
170
171impl FromNormalizedStr for EntityUID {
172    fn describe_self() -> &'static str {
173        "Entity UID"
174    }
175}
176
177/// EID type is just a SmolStr for now
178#[derive(Serialize, Deserialize, PartialEq, Eq, Debug, Clone, Hash, PartialOrd, Ord)]
179pub struct Eid(SmolStr);
180
181impl Eid {
182    /// Construct an Eid
183    pub fn new(eid: impl Into<SmolStr>) -> Self {
184        Eid(eid.into())
185    }
186}
187
188impl AsRef<SmolStr> for Eid {
189    fn as_ref(&self) -> &SmolStr {
190        &self.0
191    }
192}
193
194impl AsRef<str> for Eid {
195    fn as_ref(&self) -> &str {
196        &self.0
197    }
198}
199
200#[cfg(feature = "arbitrary")]
201impl<'a> arbitrary::Arbitrary<'a> for Eid {
202    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
203        let x: String = u.arbitrary()?;
204        Ok(Self(x.into()))
205    }
206}
207
208impl std::fmt::Display for Eid {
209    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
210        write!(f, "{}", self.0.escape_debug())
211    }
212}
213
214/// Entity datatype
215#[derive(Debug, Clone, Serialize)]
216pub struct Entity {
217    /// UID
218    uid: EntityUID,
219
220    /// Internal HashMap of attributes.
221    ///
222    /// In the serialized form of `Entity`, attribute values appear as
223    /// `RestrictedExpr`s, for mostly historical reasons.
224    attrs: HashMap<SmolStr, PartialValueSerializedAsExpr>,
225
226    /// Set of ancestors of this `Entity` (i.e., all direct and transitive
227    /// parents), as UIDs
228    ancestors: HashSet<EntityUID>,
229}
230
231impl Entity {
232    /// Create a new `Entity` with this UID, attributes, and ancestors
233    pub fn new(
234        uid: EntityUID,
235        attrs: HashMap<SmolStr, RestrictedExpr>,
236        ancestors: HashSet<EntityUID>,
237        extensions: &Extensions<'_>,
238    ) -> Result<Self, EntityAttrEvaluationError> {
239        let evaluator = RestrictedEvaluator::new(extensions);
240        let evaluated_attrs = attrs
241            .into_iter()
242            .map(|(k, v)| {
243                let attr_val = evaluator
244                    .partial_interpret(v.as_borrowed())
245                    .map_err(|err| EntityAttrEvaluationError {
246                        uid: uid.clone(),
247                        attr: k.clone(),
248                        err,
249                    })?;
250                Ok((k, attr_val.into()))
251            })
252            .collect::<Result<_, EntityAttrEvaluationError>>()?;
253        Ok(Entity {
254            uid,
255            attrs: evaluated_attrs,
256            ancestors,
257        })
258    }
259
260    /// Create a new `Entity` with this UID, attributes, and ancestors.
261    ///
262    /// Unlike in `Entity::new()`, in this constructor, attributes are expressed
263    /// as `PartialValue`.
264    pub fn new_with_attr_partial_value(
265        uid: EntityUID,
266        attrs: HashMap<SmolStr, PartialValue>,
267        ancestors: HashSet<EntityUID>,
268    ) -> Self {
269        Entity {
270            uid,
271            attrs: attrs.into_iter().map(|(k, v)| (k, v.into())).collect(), // TODO: can we do this without disassembling and reassembling the HashMap
272            ancestors,
273        }
274    }
275
276    /// Create a new `Entity` with this UID, attributes, and ancestors.
277    ///
278    /// Unlike in `Entity::new()`, in this constructor, attributes are expressed
279    /// as `PartialValueSerializedAsExpr`.
280    pub fn new_with_attr_partial_value_serialized_as_expr(
281        uid: EntityUID,
282        attrs: HashMap<SmolStr, PartialValueSerializedAsExpr>,
283        ancestors: HashSet<EntityUID>,
284    ) -> Self {
285        Entity {
286            uid,
287            attrs,
288            ancestors,
289        }
290    }
291
292    /// Get the UID of this entity
293    pub fn uid(&self) -> EntityUID {
294        self.uid.clone()
295    }
296
297    /// Get the value for the given attribute, or `None` if not present
298    pub fn get(&self, attr: &str) -> Option<&PartialValue> {
299        self.attrs.get(attr).map(|v| v.as_ref())
300    }
301
302    /// Is this `Entity` a descendant of `e` in the entity hierarchy?
303    pub fn is_descendant_of(&self, e: &EntityUID) -> bool {
304        self.ancestors.contains(e)
305    }
306
307    /// Iterate over this entity's ancestors
308    pub fn ancestors(&self) -> impl Iterator<Item = &EntityUID> {
309        self.ancestors.iter()
310    }
311
312    /// Iterate over this entity's attributes
313    pub fn attrs(&self) -> impl Iterator<Item = (&SmolStr, &PartialValue)> {
314        self.attrs.iter().map(|(k, v)| (k, v.as_ref()))
315    }
316
317    /// Create an `Entity` with the given UID, no attributes, and no parents.
318    pub fn with_uid(uid: EntityUID) -> Self {
319        Self {
320            uid,
321            attrs: HashMap::new(),
322            ancestors: HashSet::new(),
323        }
324    }
325
326    /// Test if two `Entity` objects are deep/structurally equal.
327    /// That is, not only do they have the same UID, but also the same
328    /// attributes, attribute values, and ancestors.
329    pub(crate) fn deep_eq(&self, other: &Self) -> bool {
330        self.uid == other.uid && self.attrs == other.attrs && self.ancestors == other.ancestors
331    }
332
333    /// Set the given attribute to the given value.
334    // Only used for convenience in some tests and when fuzzing
335    #[cfg(any(test, fuzzing))]
336    pub fn set_attr(
337        &mut self,
338        attr: SmolStr,
339        val: RestrictedExpr,
340        extensions: &Extensions<'_>,
341    ) -> Result<(), EvaluationError> {
342        let val = RestrictedEvaluator::new(extensions).partial_interpret(val.as_borrowed())?;
343        self.attrs.insert(attr, val.into());
344        Ok(())
345    }
346
347    /// Mark the given `UID` as an ancestor of this `Entity`.
348    // When fuzzing, `add_ancestor()` is fully `pub`.
349    #[cfg(not(fuzzing))]
350    pub(crate) fn add_ancestor(&mut self, uid: EntityUID) {
351        self.ancestors.insert(uid);
352    }
353    /// Mark the given `UID` as an ancestor of this `Entity`
354    #[cfg(fuzzing)]
355    pub fn add_ancestor(&mut self, uid: EntityUID) {
356        self.ancestors.insert(uid);
357    }
358}
359
360impl PartialEq for Entity {
361    fn eq(&self, other: &Self) -> bool {
362        self.uid() == other.uid()
363    }
364}
365
366impl Eq for Entity {}
367
368impl StaticallyTyped for Entity {
369    fn type_of(&self) -> Type {
370        self.uid.type_of()
371    }
372}
373
374impl TCNode<EntityUID> for Entity {
375    fn get_key(&self) -> EntityUID {
376        self.uid()
377    }
378
379    fn add_edge_to(&mut self, k: EntityUID) {
380        self.add_ancestor(k)
381    }
382
383    fn out_edges(&self) -> Box<dyn Iterator<Item = &EntityUID> + '_> {
384        Box::new(self.ancestors())
385    }
386
387    fn has_edge_to(&self, e: &EntityUID) -> bool {
388        self.is_descendant_of(e)
389    }
390}
391
392impl std::fmt::Display for Entity {
393    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
394        write!(
395            f,
396            "{}:\n  attrs:{}\n  ancestors:{}",
397            self.uid,
398            self.attrs
399                .iter()
400                .map(|(k, v)| format!("{}: {}", k, v))
401                .join("; "),
402            self.ancestors.iter().join(", ")
403        )
404    }
405}
406
407/// `PartialValue`, but serialized as a `RestrictedExpr`.
408///
409/// (Extension values can't be directly serialized, but can be serialized as
410/// `RestrictedExpr`)
411#[serde_as]
412#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
413pub struct PartialValueSerializedAsExpr(
414    #[serde_as(as = "TryFromInto<RestrictedExpr>")] PartialValue,
415);
416
417impl AsRef<PartialValue> for PartialValueSerializedAsExpr {
418    fn as_ref(&self) -> &PartialValue {
419        &self.0
420    }
421}
422
423impl std::ops::Deref for PartialValueSerializedAsExpr {
424    type Target = PartialValue;
425    fn deref(&self) -> &Self::Target {
426        &self.0
427    }
428}
429
430impl From<PartialValue> for PartialValueSerializedAsExpr {
431    fn from(value: PartialValue) -> PartialValueSerializedAsExpr {
432        PartialValueSerializedAsExpr(value)
433    }
434}
435
436impl From<PartialValueSerializedAsExpr> for PartialValue {
437    fn from(value: PartialValueSerializedAsExpr) -> PartialValue {
438        value.0
439    }
440}
441
442impl std::fmt::Display for PartialValueSerializedAsExpr {
443    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
444        write!(f, "{}", self.0)
445    }
446}
447
448/// Error type for evaluation errors when evaluating an entity attribute.
449/// Contains some extra contextual information and the underlying
450/// `EvaluationError`.
451#[derive(Debug, Error)]
452#[error("failed to evaluate attribute `{attr}` of `{uid}`: {err}")]
453pub struct EntityAttrEvaluationError {
454    /// UID of the entity where the error was encountered
455    pub uid: EntityUID,
456    /// Attribute of the entity where the error was encountered
457    pub attr: SmolStr,
458    /// Underlying evaluation error
459    pub err: EvaluationError,
460}
461
462#[cfg(test)]
463mod test {
464    use super::*;
465
466    #[test]
467    fn display() {
468        let e = EntityUID::with_eid("eid");
469        assert_eq!(format!("{e}"), "test_entity_type::\"eid\"");
470    }
471
472    #[test]
473    fn test_euid_equality() {
474        let e1 = EntityUID::with_eid("foo");
475        let e2 = EntityUID::from_components(
476            Name::parse_unqualified_name("test_entity_type").expect("should be a valid identifier"),
477            Eid("foo".into()),
478        );
479        let e3 = EntityUID::unspecified_from_eid(Eid("foo".into()));
480        let e4 = EntityUID::unspecified_from_eid(Eid("bar".into()));
481        let e5 = EntityUID::from_components(
482            Name::parse_unqualified_name("Unspecified").expect("should be a valid identifier"),
483            Eid("foo".into()),
484        );
485
486        // an EUID is equal to itself
487        assert_eq!(e1, e1);
488        assert_eq!(e2, e2);
489        assert_eq!(e3, e3);
490
491        // constructing with `with_euid` or `from_components` is the same
492        assert_eq!(e1, e2);
493
494        // other pairs are not equal
495        assert!(e1 != e3);
496        assert!(e1 != e4);
497        assert!(e1 != e5);
498        assert!(e3 != e4);
499        assert!(e3 != e5);
500        assert!(e4 != e5);
501
502        // e3 and e5 are displayed differently
503        assert!(format!("{e3}") != format!("{e5}"));
504    }
505}
cedar_policy_core/ast/entity.rs

cedar_policy_core/ast/
entity.rs
