cedar_policy_core/ast/
policy_set.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 super::{
18    EntityUID, LinkingError, LiteralPolicy, Policy, PolicyID, ReificationError, SlotId,
19    StaticPolicy, Template,
20};
21use itertools::Itertools;
22use serde::{Deserialize, Serialize};
23use std::collections::{hash_map::Entry, HashMap};
24use std::{borrow::Borrow, sync::Arc};
25use thiserror::Error;
26
27/// Represents a set of `Policy`s
28#[derive(Debug, Default, Clone, PartialEq, Eq, Serialize, Deserialize)]
29#[serde(try_from = "LiteralPolicySet")]
30#[serde(into = "LiteralPolicySet")]
31pub struct PolicySet {
32    /// `templates` contains all bodies of policies in the `PolicySet`
33    /// A body is either:
34    ///    A Body of a `Template`, which has slots that need to be filled in
35    ///    A Body of an `StaticPolicy`, which has been converted into a `Template` that has zero slots
36    templates: HashMap<PolicyID, Arc<Template>>,
37    /// `links` contains all of the executable policies in the `PolicySet`
38    /// A `StaticPolicy` must have exactly one `Policy` in `links`
39    ///   (this is managed by `PolicySet::add)
40    /// A `Template` may have zero or many links
41    links: HashMap<PolicyID, Policy>,
42}
43
44/// Converts a LiteralPolicySet into a PolicySet, ensuring the invariants are met
45/// Every `Policy` must point to a `Template` that exists in the set.
46impl TryFrom<LiteralPolicySet> for PolicySet {
47    type Error = ReificationError;
48    fn try_from(pset: LiteralPolicySet) -> Result<Self, Self::Error> {
49        // Allocate the templates into Arc's
50        let templates = pset
51            .templates
52            .into_iter()
53            .map(|(id, template)| (id, Arc::new(template)))
54            .collect();
55        let links = pset
56            .links
57            .into_iter()
58            .map(|(id, literal)| literal.reify(&templates).map(|linked| (id, linked)))
59            .collect::<Result<HashMap<PolicyID, Policy>, ReificationError>>()?;
60        Ok(Self { templates, links })
61    }
62}
63
64/// A Policy Set that can be serialized, but does not maintain the invariants that `PolicySet` does
65#[derive(Debug, Serialize, Deserialize)]
66struct LiteralPolicySet {
67    templates: HashMap<PolicyID, Template>,
68    links: HashMap<PolicyID, LiteralPolicy>,
69}
70
71impl From<PolicySet> for LiteralPolicySet {
72    fn from(pset: PolicySet) -> Self {
73        let templates = pset
74            .templates
75            .into_iter()
76            .map(|(id, template)| (id, template.as_ref().clone()))
77            .collect();
78        let links = pset
79            .links
80            .into_iter()
81            .map(|(id, p)| (id, p.into()))
82            .collect();
83        Self { templates, links }
84    }
85}
86
87/// Potential errors when working with `PolicySet`s.
88#[derive(Error, Debug)]
89pub enum PolicySetError {
90    /// There was a `PolicyId` collision in either the set of templates or the set of policies.
91    /// Nothing was added.
92    #[error("collision in policy id")]
93    Occupied,
94}
95
96// The public interface of `PolicySet` is intentionally narrow, to allow us
97// maximum flexibility to change the underlying implementation in the future
98impl PolicySet {
99    /// Create a fresh empty `PolicySet`
100    pub fn new() -> Self {
101        Self {
102            templates: HashMap::new(),
103            links: HashMap::new(),
104        }
105    }
106
107    /// Add a `Policy` to the `PolicySet`.
108    pub fn add(&mut self, policy: Policy) -> Result<(), PolicySetError> {
109        let t = policy.template_arc();
110
111        // we need to check for all possible errors before making any
112        // modifications to `self`.
113        // So we just collect the `ventry` here, and we only do the insertion
114        // once we know there will be no error
115        let template_ventry = match self.templates.entry(t.id().clone()) {
116            Entry::Vacant(ventry) => Some(ventry),
117            Entry::Occupied(oentry) => {
118                if oentry.get() != &t {
119                    return Err(PolicySetError::Occupied);
120                }
121                None
122            }
123        };
124
125        let link_ventry = match self.links.entry(policy.id().clone()) {
126            Entry::Vacant(ventry) => Some(ventry),
127            Entry::Occupied(_) => {
128                return Err(PolicySetError::Occupied);
129            }
130        };
131
132        // if we get here, there will be no errors.  So actually do the
133        // insertions.
134        if let Some(ventry) = template_ventry {
135            ventry.insert(t);
136        }
137        if let Some(ventry) = link_ventry {
138            ventry.insert(policy);
139        }
140
141        Ok(())
142    }
143
144    /// Add a `StaticPolicy` to the `PolicySet`.
145    pub fn add_static(&mut self, policy: StaticPolicy) -> Result<(), PolicySetError> {
146        let (t, p) = Template::link_static_policy(policy);
147
148        // TODO: Use `try_insert` when stabilized.
149        // https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.try_insert
150        if self.templates.contains_key(t.id()) || self.links.contains_key(p.id()) {
151            Err(PolicySetError::Occupied)
152        } else {
153            if self.templates.insert(t.id().clone(), t).is_some() {
154                unreachable!("Template key was already present");
155            }
156
157            if self.links.insert(p.id().clone(), p).is_some() {
158                unreachable!("Link key was already present");
159            }
160
161            Ok(())
162        }
163    }
164
165    /// Add a template to the policy set.
166    pub fn add_template(&mut self, t: Template) -> Result<(), PolicySetError> {
167        // TODO: Use `try_insert` when stabilized.
168        // https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.try_insert
169        if self.templates.contains_key(t.id()) {
170            Err(PolicySetError::Occupied)
171        } else {
172            if self.templates.insert(t.id().clone(), Arc::new(t)).is_some() {
173                unreachable!("Template key was already present");
174            }
175            Ok(())
176        }
177    }
178
179    /// Attempt to create a new template linked policy and add it to the policy set
180    /// Errors for two reasons
181    ///   1) The the passed SlotEnv either does not match the slots in the templates
182    ///   2) The passed link Id conflicts with an Id already in the set
183    pub fn link(
184        &mut self,
185        template_id: PolicyID,
186        new_id: PolicyID,
187        vals: HashMap<SlotId, EntityUID>,
188    ) -> Result<(), LinkingError> {
189        let t = self
190            .get_template(&template_id)
191            .ok_or_else(|| LinkingError::NoSuchTemplate(template_id.clone()))?;
192        let r = Template::link(t, new_id.clone(), vals)?;
193        if self.links.contains_key(&new_id) || self.templates.contains_key(&new_id) {
194            Err(LinkingError::PolicyIdConflict)
195        } else {
196            if self.links.insert(new_id, r).is_some() {
197                unreachable!("Links already has `new_id` as a key!")
198            }
199            Ok(())
200        }
201    }
202
203    /// Iterate over all policies
204    pub fn policies(&self) -> impl Iterator<Item = &Policy> {
205        self.links.values()
206    }
207
208    /// Iterate over everything stored as template, including static policies.
209    /// Ie: all_templates() should equal templates() ++ static_policies().map(|p| p.template())
210    pub fn all_templates(&self) -> impl Iterator<Item = &Template> {
211        self.templates.values().map(|t| t.borrow())
212    }
213
214    /// Iterate over templates with slots
215    pub fn templates(&self) -> impl Iterator<Item = &Template> {
216        self.all_templates().filter(|t| t.slots().count() != 0)
217    }
218
219    /// Iterate over all of the static policies.
220    pub fn static_policies(&self) -> impl Iterator<Item = &Policy> {
221        self.policies().filter(|p| p.is_static())
222    }
223
224    /// Returns true iff the `PolicySet` is empty
225    pub fn is_empty(&self) -> bool {
226        self.templates.is_empty() && self.links.is_empty()
227    }
228
229    /// Lookup a template by policy id
230    pub fn get_template(&self, id: &PolicyID) -> Option<Arc<Template>> {
231        self.templates.get(id).map(Arc::clone)
232    }
233
234    /// Lookup an policy by policy id
235    pub fn get(&self, id: &PolicyID) -> Option<&Policy> {
236        self.links.get(id)
237    }
238
239    /// Attempt to collect an iterator over policies into a PolicySet
240    pub fn try_from_iter<T: IntoIterator<Item = Policy>>(iter: T) -> Result<Self, PolicySetError> {
241        let mut set = Self::new();
242        for p in iter {
243            set.add(p)?;
244        }
245        Ok(set)
246    }
247}
248
249impl std::fmt::Display for PolicySet {
250    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
251        // we don't show the ID, because the Display impl for Policy itself shows the ID
252        if self.is_empty() {
253            write!(f, "<empty policyset>")
254        } else {
255            write!(
256                f,
257                "Templates:\n{}, Template Linked Policies:\n{}",
258                self.all_templates().join("\n"),
259                self.policies().join("\n")
260            )
261        }
262    }
263}
264
265#[cfg(test)]
266mod test {
267    use std::collections::{BTreeMap, HashMap};
268
269    use crate::{
270        ast::{ActionConstraint, Effect, Expr, PrincipalConstraint, ResourceConstraint},
271        parser,
272    };
273
274    use super::*;
275
276    #[test]
277    fn link_conflicts() {
278        let mut pset = PolicySet::new();
279        let p1 = parser::parse_policy(Some("id".into()), "permit(principal,action,resource);")
280            .expect("Failed to parse");
281        pset.add_static(p1).expect("Failed to add!");
282        let template = parser::parse_policy_template(
283            Some("t".into()),
284            "permit(principal == ?principal, action, resource);",
285        )
286        .expect("Failed to parse");
287        pset.add_template(template).expect("Add failed");
288
289        let env: HashMap<SlotId, EntityUID> = [(
290            SlotId::principal(),
291            r#"Test::"test""#.parse().expect("Failed to parse"),
292        )]
293        .into_iter()
294        .collect();
295
296        let r = pset.link(PolicyID::from_string("t"), PolicyID::from_string("id"), env);
297
298        match r {
299            Ok(_) => panic!("Should have failed due to conflict"),
300            Err(LinkingError::PolicyIdConflict) => (),
301            Err(e) => panic!("Incorrect error: {e}"),
302        };
303    }
304
305    /// This test focuses on `PolicySet::add()`, while other tests mostly use
306    /// `PolicySet::add_static()` and `PolicySet::link()`.
307    #[test]
308    fn policyset_add() {
309        let mut pset = PolicySet::new();
310        let static_policy =
311            parser::parse_policy(Some("id".into()), "permit(principal,action,resource);")
312                .expect("Failed to parse");
313        let static_policy: Policy = static_policy.into();
314        pset.add(static_policy)
315            .expect("Adding static policy in Policy form should succeed");
316
317        let template = Arc::new(
318            parser::parse_policy_template(
319                Some("t".into()),
320                "permit(principal == ?principal, action, resource);",
321            )
322            .expect("Failed to parse"),
323        );
324        let env1: HashMap<SlotId, EntityUID> = [(
325            SlotId::principal(),
326            r#"Test::"test1""#.parse().expect("Failed to parse"),
327        )]
328        .into_iter()
329        .collect();
330
331        let p1 = Template::link(Arc::clone(&template), PolicyID::from_string("link"), env1)
332            .expect("Failed to link");
333        pset.add(p1).expect(
334            "Adding link should succeed, even though the template wasn't previously in the pset",
335        );
336        assert!(
337            pset.get_template(&PolicyID::from_string("t")).is_some(),
338            "Adding link should implicitly add the template"
339        );
340
341        let env2: HashMap<SlotId, EntityUID> = [(
342            SlotId::principal(),
343            r#"Test::"test2""#.parse().expect("Failed to parse"),
344        )]
345        .into_iter()
346        .collect();
347
348        let p2 = Template::link(
349            Arc::clone(&template),
350            PolicyID::from_string("link"),
351            env2.clone(),
352        )
353        .expect("Failed to link");
354        match pset.add(p2) {
355            Ok(_) => panic!("Should have failed due to conflict with existing link id"),
356            Err(PolicySetError::Occupied) => (),
357        }
358
359        let p3 = Template::link(Arc::clone(&template), PolicyID::from_string("link2"), env2)
360            .expect("Failed to link");
361        pset.add(p3).expect(
362            "Adding link should succeed, even though the template already existed in the pset",
363        );
364
365        let template2 = Arc::new(
366            parser::parse_policy_template(
367                Some("t".into()),
368                "forbid(principal, action, resource == ?resource);",
369            )
370            .expect("Failed to parse"),
371        );
372        let env3: HashMap<SlotId, EntityUID> = [(
373            SlotId::resource(),
374            r#"Test::"test3""#.parse().expect("Failed to parse"),
375        )]
376        .into_iter()
377        .collect();
378
379        let p4 = Template::link(
380            Arc::clone(&template2),
381            PolicyID::from_string("unique3"),
382            env3,
383        )
384        .expect("Failed to link");
385        match pset.add(p4) {
386            Ok(_) => panic!("Should have failed due to conflict on template id"),
387            Err(PolicySetError::Occupied) => (),
388        }
389    }
390
391    #[test]
392    fn policy_conflicts() {
393        let mut pset = PolicySet::new();
394        let p1 = parser::parse_policy(Some("id".into()), "permit(principal,action,resource);")
395            .expect("Failed to parse");
396        let p2 = parser::parse_policy(
397            Some("id".into()),
398            "permit(principal,action,resource) when { false };",
399        )
400        .expect("Failed to parse");
401        pset.add_static(p1).expect("Failed to add!");
402        match pset.add_static(p2) {
403            Ok(_) => panic!("Should have failed to due name conflict"),
404            Err(PolicySetError::Occupied) => (),
405        }
406    }
407
408    #[test]
409    fn template_filtering() {
410        let template = parser::parse_policy_template(
411            Some("template".into()),
412            "permit(principal == ?principal, action, resource);",
413        )
414        .expect("Template Parse Failure");
415        let static_policy = parser::parse_policy(
416            Some("static".into()),
417            "permit(principal, action, resource);",
418        )
419        .expect("Static parse failure");
420        let mut set = PolicySet::new();
421        set.add_template(template).unwrap();
422        set.add_static(static_policy).unwrap();
423
424        assert_eq!(set.all_templates().count(), 2);
425        assert_eq!(set.templates().count(), 1);
426        assert_eq!(set.static_policies().count(), 1);
427        assert_eq!(set.policies().count(), 1);
428        set.link(
429            PolicyID::from_string("template"),
430            PolicyID::from_string("id"),
431            [(SlotId::principal(), EntityUID::with_eid("eid"))]
432                .into_iter()
433                .collect(),
434        )
435        .expect("Linking failed!");
436        assert_eq!(set.static_policies().count(), 1);
437        assert_eq!(set.policies().count(), 2);
438    }
439
440    #[test]
441    fn linking_missing_template() {
442        let tid = PolicyID::from_string("template");
443        let lid = PolicyID::from_string("link");
444        let t = Template::new(
445            tid.clone(),
446            BTreeMap::new(),
447            Effect::Permit,
448            PrincipalConstraint::any(),
449            ActionConstraint::any(),
450            ResourceConstraint::any(),
451            Expr::val(true),
452        );
453
454        let mut s = PolicySet::new();
455        let e = s
456            .link(tid.clone(), lid.clone(), HashMap::new())
457            .expect_err("Should fail");
458
459        match e {
460            LinkingError::NoSuchTemplate(id) => assert_eq!(tid, id),
461            e => panic!("Wrong error {e}"),
462        };
463
464        s.add_template(t).unwrap();
465        s.link(tid, lid, HashMap::new()).expect("Should succeed");
466    }
467
468    #[test]
469    fn linkinv_valid_link() {
470        let tid = PolicyID::from_string("template");
471        let lid = PolicyID::from_string("link");
472        let t = Template::new(
473            tid.clone(),
474            BTreeMap::new(),
475            Effect::Permit,
476            PrincipalConstraint::is_eq_slot(),
477            ActionConstraint::any(),
478            ResourceConstraint::is_in_slot(),
479            Expr::val(true),
480        );
481
482        let mut s = PolicySet::new();
483        s.add_template(t).unwrap();
484
485        let mut vals = HashMap::new();
486        vals.insert(SlotId::principal(), EntityUID::with_eid("p"));
487        vals.insert(SlotId::resource(), EntityUID::with_eid("a"));
488
489        s.link(tid.clone(), lid.clone(), vals).expect("Should link");
490
491        let v: Vec<_> = s.policies().collect();
492
493        assert_eq!(v[0].id(), &lid);
494        assert_eq!(v[0].template().id(), &tid);
495    }
496
497    #[test]
498    fn linking_empty_set() {
499        let s = PolicySet::new();
500        assert_eq!(s.policies().count(), 0);
501    }
502
503    #[test]
504    fn linking_raw_policy() {
505        let mut s = PolicySet::new();
506        let id = PolicyID::from_string("id");
507        let p = StaticPolicy::new(
508            id.clone(),
509            BTreeMap::new(),
510            Effect::Forbid,
511            PrincipalConstraint::any(),
512            ActionConstraint::any(),
513            ResourceConstraint::any(),
514            Expr::val(true),
515        )
516        .expect("Policy Creation Failed");
517        s.add_static(p).unwrap();
518
519        let mut iter = s.policies();
520        match iter.next() {
521            Some(pol) => {
522                assert_eq!(pol.id(), &id);
523                assert_eq!(pol.effect(), Effect::Forbid);
524                assert!(pol.env().is_empty())
525            }
526            None => panic!("Linked Record Not Present"),
527        };
528    }
529
530    #[test]
531    fn link_slotmap() {
532        let mut s = PolicySet::new();
533        let template_id = PolicyID::from_string("template");
534        let link_id = PolicyID::from_string("link");
535        let t = Template::new(
536            template_id.clone(),
537            BTreeMap::new(),
538            Effect::Forbid,
539            PrincipalConstraint::is_eq_slot(),
540            ActionConstraint::any(),
541            ResourceConstraint::any(),
542            Expr::val(true),
543        );
544        s.add_template(t).unwrap();
545
546        let mut v = HashMap::new();
547        let entity = EntityUID::with_eid("eid");
548        v.insert(SlotId::principal(), entity.clone());
549        s.link(template_id.clone(), link_id.clone(), v)
550            .expect("Linking failed!");
551
552        let link = s.get(&link_id).expect("Link should exist");
553        assert_eq!(&link_id, link.id());
554        assert_eq!(&template_id, link.template().id());
555        assert_eq!(
556            &entity,
557            link.env()
558                .get(&SlotId::principal())
559                .expect("Mapping was incorrect")
560        );
561    }
562
563    #[test]
564    fn policy_sets() {
565        let mut pset = PolicySet::new();
566        assert!(pset.is_empty());
567        let id1 = PolicyID::from_string("id1");
568        let tid1 = PolicyID::from_string("template");
569        let policy1 = StaticPolicy::new(
570            id1.clone(),
571            BTreeMap::new(),
572            Effect::Permit,
573            PrincipalConstraint::any(),
574            ActionConstraint::any(),
575            ResourceConstraint::any(),
576            Expr::val(true),
577        )
578        .expect("Policy Creation Failed");
579        let template1 = Template::new(
580            tid1.clone(),
581            BTreeMap::new(),
582            Effect::Permit,
583            PrincipalConstraint::any(),
584            ActionConstraint::any(),
585            ResourceConstraint::any(),
586            Expr::val(true),
587        );
588        let added = pset.add_static(policy1.clone()).is_ok();
589        assert!(added);
590        let added = pset.add_static(policy1).is_ok();
591        assert!(!added);
592        let added = pset.add_template(template1.clone()).is_ok();
593        assert!(added);
594        let added = pset.add_template(template1).is_ok();
595        assert!(!added);
596        assert!(!pset.is_empty());
597        let id2 = PolicyID::from_string("id2");
598        let policy2 = StaticPolicy::new(
599            id2.clone(),
600            BTreeMap::new(),
601            Effect::Forbid,
602            PrincipalConstraint::is_eq(EntityUID::with_eid("jane")),
603            ActionConstraint::any(),
604            ResourceConstraint::any(),
605            Expr::val(true),
606        )
607        .expect("Policy Creation Failed");
608        let added = pset.add_static(policy2).is_ok();
609        assert!(added);
610
611        let tid2 = PolicyID::from_string("template2");
612        let template2 = Template::new(
613            tid2.clone(),
614            BTreeMap::new(),
615            Effect::Permit,
616            PrincipalConstraint::is_eq_slot(),
617            ActionConstraint::any(),
618            ResourceConstraint::any(),
619            Expr::val(true),
620        );
621        let id3 = PolicyID::from_string("link");
622        let added = pset.add_template(template2).is_ok();
623        assert!(added);
624
625        let r = pset.link(
626            tid2.clone(),
627            id3.clone(),
628            HashMap::from([(SlotId::principal(), EntityUID::with_eid("example"))]),
629        );
630        r.expect("Linking failed");
631
632        assert_eq!(pset.get(&id1).expect("should find the policy").id(), &id1);
633        assert_eq!(pset.get(&id2).expect("should find the policy").id(), &id2);
634        assert_eq!(pset.get(&id3).expect("should find link").id(), &id3);
635        assert_eq!(
636            pset.get(&id3).expect("should find link").template().id(),
637            &tid2
638        );
639        assert!(pset.get(&tid2).is_none());
640        assert!(pset.get_template(&id1).is_some()); // Static policies are also templates
641        assert!(pset.get_template(&id2).is_some()); // Static policies are also templates
642        assert!(pset.get_template(&tid2).is_some());
643        assert_eq!(pset.policies().count(), 3);
644
645        assert_eq!(
646            pset.get_template(&tid1)
647                .expect("should find the template")
648                .id(),
649            &tid1
650        );
651        assert!(pset.get(&tid1).is_none());
652        assert_eq!(pset.all_templates().count(), 4);
653    }
654}
cedar_policy_core/ast/policy_set.rs

cedar_policy_core/ast/
policy_set.rs
