cedar_policy_core/

parser.rs

/*
 * Copyright Cedar Contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//! This module contains the parser for the Cedar language.

/// Concrete Syntax Tree def used as parser first pass
pub mod cst;
/// Step two: convert CST to package AST
pub mod cst_to_ast;
/// error handling utilities
pub mod err;
/// implementations for formatting, like `Display`
mod fmt;
pub use fmt::join_with_conjunction;
/// Source location struct
mod loc;
pub use loc::Loc;
/// Metadata wrapper for CST Nodes
mod node;
pub use node::Node;
/// Step one: Convert text to CST
pub mod text_to_cst;
/// Utility functions to unescape string literals
pub mod unescape;
/// Utility functions
pub mod util;

use smol_str::SmolStr;
use std::collections::HashMap;

use crate::ast;
use crate::ast::RestrictedExpressionParseError;
use crate::est;

/// simple main function for parsing policies
/// generates numbered ids
pub fn parse_policyset(text: &str) -> Result<ast::PolicySet, err::ParseErrors> {
    let cst = text_to_cst::parse_policies(text)?;
    cst.to_policyset()
}

/// Like `parse_policyset()`, but also returns the (lossless) original text of
/// each individual policy.
/// INVARIANT: The `PolicyId` of every `Policy` and `Template` returned by the
/// `policies()` and `templates()` methods on the returned `Policy` _must_
/// appear as a key in the returned map.
pub fn parse_policyset_and_also_return_policy_text(
    text: &str,
) -> Result<(HashMap<ast::PolicyID, &str>, ast::PolicySet), err::ParseErrors> {
    let cst = text_to_cst::parse_policies(text)?;
    let pset = cst.to_policyset()?;
    // PANIC SAFETY Shouldn't be `none` since `parse_policies()` and `to_policyset()` didn't return `Err`
    #[allow(clippy::expect_used)]
    // PANIC SAFETY Indexing is safe because of how the `SourceSpan` is constructed
    #[allow(clippy::indexing_slicing)]
    // The `PolicyID` keys for `texts` are generated by
    // `cst.with_generated_policyids()`. This is the same method used to
    // generate the ids for policies and templates in `cst.to_policyset()`,
    // so every static policy and template in the policy set will have its
    // `PolicyId` present as a key in this map.
    let texts = cst
        .with_generated_policyids()
        .expect("shouldn't be None since parse_policies() and to_policyset() didn't return Err")
        .map(|(id, policy)| (id, &text[policy.loc.start()..policy.loc.end()]))
        .collect::<HashMap<ast::PolicyID, &str>>();
    Ok((texts, pset))
}

/// Like `parse_policyset()`, but also returns the (lossless) ESTs -- that is,
/// the ESTs of the original policies without any of the lossy transforms
/// involved in converting to AST.
pub fn parse_policyset_to_ests_and_pset(
    text: &str,
) -> Result<(HashMap<ast::PolicyID, est::Policy>, ast::PolicySet), err::ParseErrors> {
    let cst = text_to_cst::parse_policies(text)?;
    let pset = cst.to_policyset()?;
    // PANIC SAFETY Shouldn't be `None` since `parse_policies()` and `to_policyset()` didn't return `Err`
    #[allow(clippy::expect_used)]
    let ests = cst
        .with_generated_policyids()
        .expect("missing policy set node")
        .map(|(id, policy)| {
            let p = policy.node.as_ref().expect("missing policy node").clone();
            Ok((id, p.try_into()?))
        })
        .collect::<Result<HashMap<ast::PolicyID, est::Policy>, err::ParseErrors>>()?;
    Ok((ests, pset))
}

/// Main function for parsing a policy _or_ template. In either case, the
/// returned value will be a [`ast::Template`].
/// If `id` is Some, then the resulting template will have that `id`.
/// If the `id` is None, the parser will use "policy0".
pub fn parse_policy_or_template(
    id: Option<ast::PolicyID>,
    text: &str,
) -> Result<ast::Template, err::ParseErrors> {
    let id = id.unwrap_or_else(|| ast::PolicyID::from_string("policy0"));
    let cst = text_to_cst::parse_policy(text)?;
    cst.to_policy_template(id)
}

/// Like `parse_policy_or_template()`, but also returns the (lossless) EST -- that
/// is, the EST of the original policy/template without any of the lossy transforms
/// involved in converting to AST.
pub fn parse_policy_or_template_to_est_and_ast(
    id: Option<ast::PolicyID>,
    text: &str,
) -> Result<(est::Policy, ast::Template), err::ParseErrors> {
    let id = id.unwrap_or_else(|| ast::PolicyID::from_string("policy0"));
    let cst = text_to_cst::parse_policy(text)?;
    let ast = cst.to_policy_template(id)?;
    let est = cst.try_into_inner()?.try_into()?;
    Ok((est, ast))
}

/// Main function for parsing a template.
/// Will return an error if provided with a static policy.
/// If `id` is Some, then the resulting policy will have that `id`.
/// If the `id` is None, the parser will use "policy0".
pub fn parse_template(
    id: Option<ast::PolicyID>,
    text: &str,
) -> Result<ast::Template, err::ParseErrors> {
    let id = id.unwrap_or_else(|| ast::PolicyID::from_string("policy0"));
    let cst = text_to_cst::parse_policy(text)?;
    let template = cst.to_policy_template(id)?;
    if template.slots().count() == 0 {
        Err(err::ToASTError::new(err::ToASTErrorKind::expected_template(), cst.loc).into())
    } else {
        Ok(template)
    }
}

/// Main function for parsing a (static) policy.
/// Will return an error if provided with a template.
/// If `id` is Some, then the resulting policy will have that `id`.
/// If the `id` is None, the parser will use "policy0".
pub fn parse_policy(
    id: Option<ast::PolicyID>,
    text: &str,
) -> Result<ast::StaticPolicy, err::ParseErrors> {
    let id = id.unwrap_or_else(|| ast::PolicyID::from_string("policy0"));
    let cst = text_to_cst::parse_policy(text)?;
    cst.to_policy(id)
}

/// Like `parse_policy()`, but also returns the (lossless) EST -- that is, the
/// EST of the original policy without any of the lossy transforms involved in
/// converting to AST.
pub fn parse_policy_to_est_and_ast(
    id: Option<ast::PolicyID>,
    text: &str,
) -> Result<(est::Policy, ast::StaticPolicy), err::ParseErrors> {
    let id = id.unwrap_or_else(|| ast::PolicyID::from_string("policy0"));
    let cst = text_to_cst::parse_policy(text)?;
    let ast = cst.to_policy(id)?;
    let est = cst.try_into_inner()?.try_into()?;
    Ok((est, ast))
}

/// Parse a policy or template (either one works) to its EST representation
pub fn parse_policy_or_template_to_est(text: &str) -> Result<est::Policy, err::ParseErrors> {
    // We parse to EST and AST even though we only want the EST because some
    // checks are applied by the CST-to-AST conversion and not CST-to-EST, and
    // we do not want to return any EST if the policy text would not parse
    // normally.
    parse_policy_or_template_to_est_and_ast(None, text).map(|(est, _ast)| est)
}

/// parse an Expr
///
/// Private to this crate. Users outside Core should use `Expr`'s `FromStr` impl
/// or its constructors
pub(crate) fn parse_expr(ptext: &str) -> Result<ast::Expr, err::ParseErrors> {
    let cst = text_to_cst::parse_expr(ptext)?;
    cst.to_expr::<ast::ExprBuilder<()>>()
}

/// parse a RestrictedExpr
///
/// Private to this crate. Users outside Core should use `RestrictedExpr`'s
/// `FromStr` impl or its constructors
pub(crate) fn parse_restrictedexpr(
    ptext: &str,
) -> Result<ast::RestrictedExpr, RestrictedExpressionParseError> {
    let expr = parse_expr(ptext)?;
    Ok(ast::RestrictedExpr::new(expr)?)
}

/// parse an EntityUID
///
/// Private to this crate. Users outside Core should use `EntityUID`'s `FromStr`
/// impl or its constructors
pub(crate) fn parse_euid(euid: &str) -> Result<ast::EntityUID, err::ParseErrors> {
    let cst = text_to_cst::parse_ref(euid)?;
    cst.to_ref()
}

/// parse an [`ast::InternalName`]
///
/// Private to this crate. Users outside Core should use [`ast::InternalName`]'s
/// `FromStr` impl or its constructors
pub(crate) fn parse_internal_name(name: &str) -> Result<ast::InternalName, err::ParseErrors> {
    let cst = text_to_cst::parse_name(name)?;
    cst.to_internal_name()
}

/// parse a string into an ast::Literal (does not support expressions)
///
/// Private to this crate. Users outside Core should use `Literal`'s `FromStr` impl
/// or its constructors
pub(crate) fn parse_literal(val: &str) -> Result<ast::Literal, err::LiteralParseError> {
    let cst = text_to_cst::parse_primary(val)?;
    match cst.to_expr::<ast::ExprBuilder<()>>() {
        Ok(ast) => match ast.expr_kind() {
            ast::ExprKind::Lit(v) => Ok(v.clone()),
            _ => Err(err::LiteralParseError::InvalidLiteral(ast)),
        },
        Err(errs) => Err(err::LiteralParseError::Parse(errs)),
    }
}

/// parse a string into an internal Cedar string
///
/// This performs unescaping and validation, returning
/// a String suitable for an attr, eid, or literal.
///
/// Quote handling is as if the input is surrounded by
/// double quotes ("{val}").
///
/// It does not return a string suitable for a pattern. Use the
/// full expression parser for those.
pub fn parse_internal_string(val: &str) -> Result<SmolStr, err::ParseErrors> {
    // we need to add quotes for this to be a valid string literal
    let cst = text_to_cst::parse_primary(&format!(r#""{val}""#))?;
    cst.to_string_literal::<ast::ExprBuilder<()>>()
}

/// parse an identifier
///
/// Private to this crate. Users outside Core should use `Id`'s `FromStr` impl
/// or its constructors
pub(crate) fn parse_ident(id: &str) -> Result<ast::Id, err::ParseErrors> {
    let cst = text_to_cst::parse_ident(id)?;
    cst.to_valid_ident()
}

/// parse an `AnyId`
///
/// Private to this crate. Users outside Core should use `AnyId`'s `FromStr` impl
/// or its constructors
pub(crate) fn parse_anyid(id: &str) -> Result<ast::AnyId, err::ParseErrors> {
    let cst = text_to_cst::parse_ident(id)?;
    cst.to_any_ident()
}

/// Utilities used in tests in this file (and maybe other files in this crate)
#[cfg(test)]
// PANIC SAFETY unit tests
#[allow(clippy::panic)]
pub(crate) mod test_utils {
    use super::err::ParseErrors;
    use crate::test_utils::*;

    /// Expect that the given `ParseErrors` contains a particular number of errors.
    ///
    /// `src` is the original input text (which the miette labels index into).
    #[track_caller] // report the caller's location as the location of the panic, not the location in this function
    pub fn expect_n_errors(src: &str, errs: &ParseErrors, n: usize) {
        assert_eq!(
            errs.len(),
            n,
            "for the following input:\n{src}\nexpected {n} error(s), but saw {}\nactual errors were:\n{:?}", // the Debug representation of `miette::Report` is the pretty one, for some reason
            errs.len(),
            miette::Report::new(errs.clone())
        );
    }

    /// Expect that the given `ParseErrors` contains at least one error with the given `ExpectedErrorMessage`.
    ///
    /// `src` is the original input text (which the miette labels index into).
    #[track_caller] // report the caller's location as the location of the panic, not the location in this function
    pub fn expect_some_error_matches(
        src: &str,
        errs: &ParseErrors,
        msg: &ExpectedErrorMessage<'_>,
    ) {
        assert!(
            errs.iter().any(|e| msg.matches(e)),
            "for the following input:\n{src}\nexpected some error to match the following:\n{msg}\nbut actual errors were:\n{:?}", // the Debug representation of `miette::Report` is the pretty one, for some reason
            miette::Report::new(errs.clone()),
        );
    }

    /// Expect that the given `ParseErrors` contains exactly one error, and that it matches the given `ExpectedErrorMessage`.
    ///
    /// `src` is the original input text (which the miette labels index into).
    #[track_caller] // report the caller's location as the location of the panic, not the location in this function
    pub fn expect_exactly_one_error(src: &str, errs: &ParseErrors, msg: &ExpectedErrorMessage<'_>) {
        match errs.len() {
            0 => panic!("for the following input:\n{src}\nexpected an error, but the `ParseErrors` was empty"),
            1 => {
                let err = errs.iter().next().expect("already checked that len was 1");
                expect_err(src, &miette::Report::new(err.clone()), msg);
            }
            n => panic!(
                "for the following input:\n{src}\nexpected only one error, but got {n}. Expected to match the following:\n{msg}\nbut actual errors were:\n{:?}", // the Debug representation of `miette::Report` is the pretty one, for some reason
                miette::Report::new(errs.clone()),
            )
        }
    }
}

// PANIC SAFETY: Unit Test Code
#[allow(clippy::panic, clippy::indexing_slicing)]
#[allow(clippy::cognitive_complexity)]
#[cfg(test)]
/// Tests for the top-level parsing APIs
mod tests {

    use super::*;

    use crate::ast::test_generators::*;
    use crate::ast::{Eid, Literal, Template, Value};
    use crate::evaluator as eval;
    use crate::extensions::Extensions;
    use crate::parser::err::*;
    use crate::parser::test_utils::*;
    use crate::test_utils::*;
    use cool_asserts::assert_matches;
    use std::collections::HashSet;
    use std::sync::Arc;

    #[test]
    fn test_template_parsing() {
        for template in all_templates().map(Template::from) {
            let id = template.id();
            let src = format!("{template}");
            let parsed =
                parse_policy_or_template(Some(ast::PolicyID::from_string(id)), &src).unwrap();
            assert_eq!(
                parsed.slots().collect::<HashSet<_>>(),
                template.slots().collect::<HashSet<_>>()
            );
            assert_eq!(parsed.id(), template.id());
            assert_eq!(parsed.effect(), template.effect());
            assert_eq!(
                parsed.principal_constraint(),
                template.principal_constraint()
            );
            assert_eq!(parsed.action_constraint(), template.action_constraint());
            assert_eq!(parsed.resource_constraint(), template.resource_constraint());
            assert!(
                parsed
                    .non_scope_constraints()
                    .eq_shape(template.non_scope_constraints()),
                "{:?} and {:?} should have the same shape.",
                parsed.non_scope_constraints(),
                template.non_scope_constraints()
            );
        }
    }

    #[test]
    fn test_error_out() {
        let src = r#"
            permit(principal:p,action:a,resource:r)
            when{w or if c but not z} // expr error
            unless{u if c else d or f} // expr error
            advice{"doit"};

            permit(principality in Group::"jane_friends", // policy error
            action in [PhotoOp::"view", PhotoOp::"comment"],
            resource in Album::"jane_trips");

            forbid(principal, action, resource)
            when   { "private" in resource.tags }
            unless { resource in principal.account };
        "#;
        let errs = parse_policyset(src).expect_err("expected parsing to fail");
        let unrecognized_tokens = vec![
            ("or", "expected `!=`, `&&`, `(`, `*`, `+`, `-`, `.`, `::`, `<`, `<=`, `==`, `>`, `>=`, `[`, `||`, `}`, `has`, `in`, `is`, or `like`"),
            ("if", "expected `!=`, `&&`, `(`, `*`, `+`, `-`, `.`, `::`, `<`, `<=`, `==`, `>`, `>=`, `[`, `||`, `}`, `has`, `in`, `is`, or `like`"),
        ];
        for (token, label) in unrecognized_tokens {
            expect_some_error_matches(
                src,
                &errs,
                &ExpectedErrorMessageBuilder::error(&format!("unexpected token `{token}`"))
                    .exactly_one_underline_with_label(token, label)
                    .build(),
            );
        }
        expect_n_errors(src, &errs, 2);
        assert!(errs.iter().all(|err| matches!(err, ParseError::ToCST(_))));
    }

    #[test]
    fn entity_literals1() {
        let src = r#"Test::{ test : "Test" }"#;
        let errs = parse_euid(src).unwrap_err();
        expect_exactly_one_error(
            src,
            &errs,
            &ExpectedErrorMessageBuilder::error("invalid entity literal: Test::{test: \"Test\"}")
                .help("entity literals should have a form like `Namespace::User::\"alice\"`")
                .exactly_one_underline("Test::{ test : \"Test\" }")
                .build(),
        );
    }

    #[test]
    fn entity_literals2() {
        let src = r#"permit(principal == Test::{ test : "Test" }, action, resource);"#;
        let errs = parse_policy(None, src).unwrap_err();
        expect_exactly_one_error(
            src,
            &errs,
            &ExpectedErrorMessageBuilder::error("invalid entity literal: Test::{test: \"Test\"}")
                .help("entity literals should have a form like `Namespace::User::\"alice\"`")
                .exactly_one_underline("Test::{ test : \"Test\" }")
                .build(),
        );
    }

    #[test]
    fn interpret_exprs() {
        let request = eval::test::basic_request();
        let entities = eval::test::basic_entities();
        let exts = Extensions::none();
        let evaluator = eval::Evaluator::new(request, &entities, exts);
        // The below tests check not only that we get the expected `Value`, but
        // that it has the expected source location.
        // We have to check that separately because the `PartialEq` and `Eq`
        // impls for `Value` do not compare source locations.
        // This is somewhat a test of the evaluator, not just the parser; but
        // the actual evaluator unit tests do not use the parser and thus do
        // not have source locations attached to their input expressions, so
        // this file is where we effectively perform evaluator tests related to
        // propagating source locations from expressions to values.

        // bools
        let src = "false";
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(false));
        assert_eq!(val.source_loc(), Some(&Loc::new(0..5, Arc::from(src))));

        let src = "true && true";
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(true));
        assert_eq!(val.source_loc(), Some(&Loc::new(0..12, Arc::from(src))));

        let src = "!true || false && !true";
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(false));
        assert_eq!(val.source_loc(), Some(&Loc::new(0..23, Arc::from(src))));

        let src = "!!!!true";
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(true));
        assert_eq!(val.source_loc(), Some(&Loc::new(0..8, Arc::from(src))));

        let src = r#"
        if false || true != 4 then
            600
        else
            -200
        "#;
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(600));
        assert_eq!(val.source_loc(), Some(&Loc::new(9..81, Arc::from(src))));
    }

    #[test]
    fn interpret_membership() {
        let request = eval::test::basic_request();
        let entities = eval::test::rich_entities();
        let exts = Extensions::none();
        let evaluator = eval::Evaluator::new(request, &entities, exts);
        // The below tests check not only that we get the expected `Value`, but
        // that it has the expected source location.
        // See note on this in the above test.

        let src = r#"

        test_entity_type::"child" in
            test_entity_type::"unrelated"

        "#;
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(false));
        assert_eq!(val.source_loc(), Some(&Loc::new(10..80, Arc::from(src))));
        // because "10..80" is hard to read, we also assert that the correct portion of `src` is indicated
        assert_eq!(
            val.source_loc().unwrap().snippet(),
            Some(
                r#"test_entity_type::"child" in
            test_entity_type::"unrelated""#
            )
        );

        let src = r#"

        test_entity_type::"child" in
            test_entity_type::"child"

        "#;
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(true));
        assert_eq!(val.source_loc(), Some(&Loc::new(10..76, Arc::from(src))));
        assert_eq!(
            val.source_loc().unwrap().snippet(),
            Some(
                r#"test_entity_type::"child" in
            test_entity_type::"child""#
            )
        );

        let src = r#"

        other_type::"other_child" in
            test_entity_type::"parent"

        "#;
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(true));
        assert_eq!(val.source_loc(), Some(&Loc::new(10..77, Arc::from(src))));
        assert_eq!(
            val.source_loc().unwrap().snippet(),
            Some(
                r#"other_type::"other_child" in
            test_entity_type::"parent""#
            )
        );

        let src = r#"

        test_entity_type::"child" in
            test_entity_type::"grandparent"

        "#;
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(true));
        assert_eq!(val.source_loc(), Some(&Loc::new(10..82, Arc::from(src))));
        assert_eq!(
            val.source_loc().unwrap().snippet(),
            Some(
                r#"test_entity_type::"child" in
            test_entity_type::"grandparent""#
            )
        );
    }

    /// Tests parser+evaluator with relations `<`, `<=`, `>`, `&&`, `||`, `!=`
    #[test]
    fn interpret_relation() {
        let request = eval::test::basic_request();
        let entities = eval::test::basic_entities();
        let exts = Extensions::none();
        let evaluator = eval::Evaluator::new(request, &entities, exts);
        // The below tests check not only that we get the expected `Value`, but
        // that it has the expected source location.
        // See note on this in the above test.

        let src = r#"

            3 < 2 || 2 > 3

        "#;
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(false));
        assert_eq!(val.source_loc(), Some(&Loc::new(14..28, Arc::from(src))));
        // because "14..28" is hard to read, we also assert that the correct portion of `src` is indicated
        assert_eq!(val.source_loc().unwrap().snippet(), Some("3 < 2 || 2 > 3"));

        let src = r#"

            7 <= 7 && 4 != 5

        "#;
        let expr = parse_expr(src).unwrap();
        let val = evaluator.interpret_inline_policy(&expr).unwrap();
        assert_eq!(val, Value::from(true));
        assert_eq!(val.source_loc(), Some(&Loc::new(14..30, Arc::from(src))));
        assert_eq!(
            val.source_loc().unwrap().snippet(),
            Some("7 <= 7 && 4 != 5")
        );
    }

    /// Tests parser+evaluator with builtin methods `containsAll()`, `hasTag()`, `getTag()`
    #[test]
    fn interpret_methods() {
        let src = r#"
            [2, 3, "foo"].containsAll([3, "foo"])
            && context.violations.isEmpty()
            && principal.hasTag(resource.getTag(context.cur_time))
        "#;
        let request = eval::test::basic_request();
        let entities = eval::test::basic_entities();
        let exts = Extensions::none();
        let evaluator = eval::Evaluator::new(request, &entities, exts);

        let expr = parse_expr(src).unwrap();
        assert_matches!(evaluator.interpret_inline_policy(&expr), Err(e) => {
            expect_err(
                src,
                &miette::Report::new(e),
                &ExpectedErrorMessageBuilder::error(r#"`test_entity_type::"test_resource"` does not have the tag `03:22:11`"#)
                    .help(r#"`test_entity_type::"test_resource"` does not have any tags"#)
                    .exactly_one_underline("resource.getTag(context.cur_time)")
                    .build(),
            );
        });
    }

    #[test]
    fn unquoted_tags() {
        let src = r#"
            principal.hasTag(foo)
        "#;
        assert_matches!(parse_expr(src), Err(e) => {
            expect_err(
                src,
                &miette::Report::new(e),
                &ExpectedErrorMessageBuilder::error("invalid variable: foo")
                    .help("the valid Cedar variables are `principal`, `action`, `resource`, and `context`; did you mean to enclose `foo` in quotes to make a string?")
                    .exactly_one_underline("foo")
                    .build(),
            );
        });

        let src = r#"
            principal.getTag(foo)
        "#;
        assert_matches!(parse_expr(src), Err(e) => {
            expect_err(
                src,
                &miette::Report::new(e),
                &ExpectedErrorMessageBuilder::error("invalid variable: foo")
                    .help("the valid Cedar variables are `principal`, `action`, `resource`, and `context`; did you mean to enclose `foo` in quotes to make a string?")
                    .exactly_one_underline("foo")
                    .build(),
            );
        });
    }

    #[test]
    fn parse_exists() {
        let result = parse_policyset(
            r#"
            permit(principal, action, resource)
            when{ true };
        "#,
        );
        assert!(!result.expect("parse error").is_empty());
    }

    #[test]
    fn attr_named_tags() {
        let src = r#"
            permit(principal, action, resource)
            when {
                resource.tags.contains({k: "foo", v: "bar"})
            };
        "#;
        parse_policy_to_est_and_ast(None, src)
            .unwrap_or_else(|e| panic!("{:?}", &miette::Report::new(e)));
    }

    #[test]
    fn test_parse_policyset() {
        use crate::ast::PolicyID;
        let multiple_policies = r#"
            permit(principal, action, resource)
            when { principal == resource.owner };

            forbid(principal, action == Action::"modify", resource) // a comment
            when { resource . highSecurity }; // intentionally not conforming to our formatter
        "#;
        let pset = parse_policyset(multiple_policies).expect("Should parse");
        assert_eq!(pset.policies().count(), 2);
        assert_eq!(pset.static_policies().count(), 2);
        let (texts, pset) =
            parse_policyset_and_also_return_policy_text(multiple_policies).expect("Should parse");
        assert_eq!(pset.policies().count(), 2);
        assert_eq!(pset.static_policies().count(), 2);
        assert_eq!(texts.len(), 2);
        assert_eq!(
            texts.get(&PolicyID::from_string("policy0")),
            Some(
                &r#"permit(principal, action, resource)
            when { principal == resource.owner };"#
            )
        );
        assert_eq!(
            texts.get(&PolicyID::from_string("policy1")),
            Some(
                &r#"forbid(principal, action == Action::"modify", resource) // a comment
            when { resource . highSecurity };"#
            )
        );
    }

    #[test]
    fn test_parse_string() {
        // test idempotence
        assert_eq!(
            Eid::new(parse_internal_string(r"a\nblock\nid").expect("should parse")).escaped(),
            r"a\nblock\nid",
        );
        parse_internal_string(r#"oh, no, a '! "#).expect("single quote should be fine");
        parse_internal_string(r#"oh, no, a \"! and a \'! "#).expect("escaped quotes should parse");
        let src = r#"oh, no, a "! "#;
        let errs = parse_internal_string(src).expect_err("unescaped double quote not allowed");
        expect_exactly_one_error(
            src,
            &errs,
            &ExpectedErrorMessageBuilder::error("invalid token")
                .exactly_one_underline("")
                .build(),
        );
    }

    #[test]
    fn good_cst_bad_ast() {
        let src = r#"
            permit(principal, action, resource) when { principal.name.like == "3" };
            "#;
        let p = parse_policyset_to_ests_and_pset(src);
        assert_matches!(p, Err(e) => expect_err(src, &miette::Report::new(e), &ExpectedErrorMessageBuilder::error("this identifier is reserved and cannot be used: like").exactly_one_underline("like").build()));
    }

    #[test]
    fn no_slots_in_condition() {
        let src = r#"
            permit(principal, action, resource) when {
                resource == ?resource
            };
            "#;
        let slot_in_when_clause =
            ExpectedErrorMessageBuilder::error("found template slot ?resource in a `when` clause")
                .help("slots are currently unsupported in `when` clauses")
                .exactly_one_underline("?resource")
                .build();
        let unexpected_template = ExpectedErrorMessageBuilder::error(
            "expected a static policy, got a template containing the slot ?resource",
        )
        .help("try removing the template slot(s) from this policy")
        .exactly_one_underline("?resource")
        .build();
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });
        assert_matches!(parse_policy_to_est_and_ast(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });
        assert_matches!(parse_policyset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });
        assert_matches!(parse_policyset_to_ests_and_pset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });

        let src = r#"
            permit(principal, action, resource) when {
                resource == ?principal
            };
            "#;
        let slot_in_when_clause =
            ExpectedErrorMessageBuilder::error("found template slot ?principal in a `when` clause")
                .help("slots are currently unsupported in `when` clauses")
                .exactly_one_underline("?principal")
                .build();
        let unexpected_template = ExpectedErrorMessageBuilder::error(
            "expected a static policy, got a template containing the slot ?principal",
        )
        .help("try removing the template slot(s) from this policy")
        .exactly_one_underline("?principal")
        .build();
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });
        assert_matches!(parse_policy_to_est_and_ast(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });
        assert_matches!(parse_policyset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });
        assert_matches!(parse_policyset_to_ests_and_pset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_when_clause);
        });

        let src = r#"
            permit(principal, action, resource) when {
                resource == ?blah
            };
            "#;
        let error = ExpectedErrorMessageBuilder::error("`?blah` is not a valid template slot")
            .help("a template slot may only be `?principal` or `?resource`")
            .exactly_one_underline("?blah")
            .build();
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policy_or_template(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policy_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policy_or_template_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policyset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policyset_to_ests_and_pset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });

        let src = r#"
            permit(principal, action, resource) unless {
                resource == ?resource
            };
            "#;
        let slot_in_unless_clause = ExpectedErrorMessageBuilder::error(
            "found template slot ?resource in a `unless` clause",
        )
        .help("slots are currently unsupported in `unless` clauses")
        .exactly_one_underline("?resource")
        .build();
        let unexpected_template = ExpectedErrorMessageBuilder::error(
            "expected a static policy, got a template containing the slot ?resource",
        )
        .help("try removing the template slot(s) from this policy")
        .exactly_one_underline("?resource")
        .build();
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policy_to_est_and_ast(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policyset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policyset_to_ests_and_pset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });

        let src = r#"
            permit(principal, action, resource) unless {
                resource == ?principal
            };
            "#;
        let slot_in_unless_clause = ExpectedErrorMessageBuilder::error(
            "found template slot ?principal in a `unless` clause",
        )
        .help("slots are currently unsupported in `unless` clauses")
        .exactly_one_underline("?principal")
        .build();
        let unexpected_template = ExpectedErrorMessageBuilder::error(
            "expected a static policy, got a template containing the slot ?principal",
        )
        .help("try removing the template slot(s) from this policy")
        .exactly_one_underline("?principal")
        .build();
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policy_to_est_and_ast(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
            expect_some_error_matches(src, &e, &unexpected_template);
        });
        assert_matches!(parse_policy_or_template_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policyset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policyset_to_ests_and_pset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &slot_in_unless_clause);
        });

        let src = r#"
            permit(principal, action, resource) unless {
                resource == ?blah
            };
            "#;
        let error = ExpectedErrorMessageBuilder::error("`?blah` is not a valid template slot")
            .help("a template slot may only be `?principal` or `?resource`")
            .exactly_one_underline("?blah")
            .build();
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policy_or_template(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policy_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policy_or_template_to_est_and_ast(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policyset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });
        assert_matches!(parse_policyset_to_ests_and_pset(src), Err(e) => {
            expect_exactly_one_error(src, &e, &error);
        });

        let src = r#"
            permit(principal, action, resource) unless {
                resource == ?resource
            } when {
                resource == ?resource
            };
            "#;
        let slot_in_when_clause =
            ExpectedErrorMessageBuilder::error("found template slot ?resource in a `when` clause")
                .help("slots are currently unsupported in `when` clauses")
                .exactly_one_underline("?resource")
                .build();
        let slot_in_unless_clause = ExpectedErrorMessageBuilder::error(
            "found template slot ?resource in a `unless` clause",
        )
        .help("slots are currently unsupported in `unless` clauses")
        .exactly_one_underline("?resource")
        .build();
        let unexpected_template = ExpectedErrorMessageBuilder::error(
            "expected a static policy, got a template containing the slot ?resource",
        )
        .help("try removing the template slot(s) from this policy")
        .exactly_one_underline("?resource")
        .build();
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_n_errors(src, &e, 4);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
            expect_some_error_matches(src, &e, &unexpected_template); // 2 copies of this error
        });
        assert_matches!(parse_policy_or_template(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policy_to_est_and_ast(None, src), Err(e) => {
            expect_n_errors(src, &e, 4);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
            expect_some_error_matches(src, &e, &unexpected_template); // 2 copies of this error
        });
        assert_matches!(parse_policy_or_template_to_est_and_ast(None, src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policyset(src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
        });
        assert_matches!(parse_policyset_to_ests_and_pset(src), Err(e) => {
            expect_n_errors(src, &e, 2);
            expect_some_error_matches(src, &e, &slot_in_when_clause);
            expect_some_error_matches(src, &e, &slot_in_unless_clause);
        });
    }

    #[test]
    fn record_literals() {
        // unquoted keys
        let src = r#"permit(principal, action, resource) when { context.foo == { foo: 2, bar: "baz" } };"#;
        assert_matches!(parse_policy(None, src), Ok(_));
        // quoted keys
        let src = r#"permit(principal, action, resource) when { context.foo == { "foo": 2, "hi mom it's 🦀": "baz" } };"#;
        assert_matches!(parse_policy(None, src), Ok(_));
        // duplicate key
        let src = r#"permit(principal, action, resource) when { context.foo == { "spam": -341, foo: 2, "🦀": true, foo: "baz" } };"#;
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &ExpectedErrorMessageBuilder::error("duplicate key `foo` in record literal").exactly_one_underline(r#"{ "spam": -341, foo: 2, "🦀": true, foo: "baz" }"#).build());
        });
    }

    #[test]
    fn annotation_errors() {
        let src = r#"
            @foo("1")
            @foo("2")
            permit(principal, action, resource);
        "#;
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &ExpectedErrorMessageBuilder::error("duplicate annotation: @foo").exactly_one_underline(r#"@foo("2")"#).build());
        });

        let src = r#"
            @foo("1")
            @foo("1")
            permit(principal, action, resource);
        "#;
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_exactly_one_error(src, &e, &ExpectedErrorMessageBuilder::error("duplicate annotation: @foo").exactly_one_underline(r#"@foo("1")"#).build());
        });

        let src = r#"
            @foo("1")
            @bar("yellow")
            @foo("abc")
            @hello("goodbye")
            @bar("123")
            @foo("def")
            permit(principal, action, resource);
        "#;
        assert_matches!(parse_policy(None, src), Err(e) => {
            expect_n_errors(src, &e, 3); // two errors for @foo and one for @bar
            expect_some_error_matches(src, &e, &ExpectedErrorMessageBuilder::error("duplicate annotation: @foo").exactly_one_underline(r#"@foo("abc")"#).build());
            expect_some_error_matches(src, &e, &ExpectedErrorMessageBuilder::error("duplicate annotation: @foo").exactly_one_underline(r#"@foo("def")"#).build());
            expect_some_error_matches(src, &e, &ExpectedErrorMessageBuilder::error("duplicate annotation: @bar").exactly_one_underline(r#"@bar("123")"#).build());
        })
    }

    #[test]
    fn unexpected_token_errors() {
        #[track_caller]
        fn assert_labeled_span(src: &str, msg: &str, underline: &str, label: &str) {
            assert_matches!(parse_policy(None, src), Err(e) => {
                expect_exactly_one_error(
                    src,
                    &e,
                    &ExpectedErrorMessageBuilder::error(msg)
                        .exactly_one_underline_with_label(underline, label)
                        .build());
            });
        }

        // Don't list out all the special case identifiers
        assert_labeled_span("@", "unexpected end of input", "", "expected identifier");
        assert_labeled_span(
            "permit(principal, action, resource) when { principal.",
            "unexpected end of input",
            "",
            "expected identifier",
        );

        // We specifically want `when` or `unless`, but we previously listed all
        // identifier tokens, so this is an improvement.
        assert_labeled_span(
            "permit(principal, action, resource)",
            "unexpected end of input",
            "",
            "expected `;` or identifier",
        );
        // AST actually requires `permit` or `forbid`, but grammar looks for any
        // identifier.
        assert_labeled_span(
            "@if(\"a\")",
            "unexpected end of input",
            "",
            "expected `@` or identifier",
        );
        // AST actually requires `principal` (`action`, `resource`, resp.). In
        // the `principal` case we also claim to expect `)` because an empty scope
        // initially parses to a CST. The trailing comma rules this out in the others.
        assert_labeled_span(
            "permit(",
            "unexpected end of input",
            "",
            "expected `)` or identifier",
        );
        assert_labeled_span(
            "permit(,,);",
            "unexpected token `,`",
            ",",
            "expected `)` or identifier",
        );
        assert_labeled_span(
            "permit(principal,",
            "unexpected end of input",
            "",
            "expected identifier",
        );
        assert_labeled_span(
            "permit(principal,action,",
            "unexpected end of input",
            "",
            "expected identifier",
        );
        // Nothing will actually convert to an AST here.
        assert_labeled_span(
            "permit(principal,action,resource,",
            "unexpected end of input",
            "",
            "expected identifier",
        );
        // We still list out `if` as an expected token because it doesn't get
        // parsed as an ident in this position.
        assert_labeled_span(
            "permit(principal, action, resource) when {",
            "unexpected end of input",
            "",
            "expected `!`, `(`, `-`, `[`, `{`, `}`, `false`, identifier, `if`, number, `?principal`, `?resource`, string literal, or `true`",
        );
        // The right operand of an `is` gets parsed as any `Expr`, so we will
        // list out all the possible expression tokens even though _only_
        // `identifier` is accepted. This choice allows nicer error messages for
        // `principal is User::"alice"`, but it doesn't work in our favor here.
        assert_labeled_span(
            "permit(principal, action, resource) when { principal is",
            "unexpected end of input",
            "",
            "expected `!`, `(`, `-`, `[`, `{`, `false`, identifier, `if`, number, `?principal`, `?resource`, string literal, or `true`",
        );

        // We expect binary operators, but don't claim to expect `=`, `%` or
        // `/`. We still expect `::` even though `true` is a reserved identifier
        // and so we can't have an entity reference `true::"eid"`
        assert_labeled_span(
            "permit(principal, action, resource) when { if true",
            "unexpected end of input",
            "",
            "expected `!=`, `&&`, `(`, `*`, `+`, `-`, `.`, `::`, `<`, `<=`, `==`, `>`, `>=`, `[`, `||`, `has`, `in`, `is`, `like`, or `then`",
        )
    }

    #[test]
    fn string_escapes() {
        // test strings with valid escapes
        // convert a string `s` to `<double-quote> <escaped-form-of-s> <double-quote>`
        // and test if the resulting string literal AST contains exactly `s`
        // for instance, "\u{1F408}"" is converted into r#""\u{1F408}""#,
        // the latter should be parsed into `Literal(String("🐈"))` and
        // `🐈` is represented by '\u{1F408}'
        let test_valid = |s: &str| {
            let r = parse_literal(&format!("\"{}\"", s.escape_default()));
            assert_eq!(r, Ok(Literal::String(s.into())));
        };
        test_valid("\t");
        test_valid("\0");
        test_valid("👍");
        test_valid("🐈");
        test_valid("\u{1F408}");
        test_valid("abc\tde\\fg");
        test_valid("aaa\u{1F408}bcd👍👍👍");
        // test string with invalid escapes
        let test_invalid = |s: &str, bad_escapes: Vec<&str>| {
            let src: &str = &format!("\"{}\"", s);
            assert_matches!(parse_literal(src), Err(LiteralParseError::Parse(e)) => {
                expect_n_errors(src, &e, bad_escapes.len());
                bad_escapes.iter().for_each(|esc|
                    expect_some_error_matches(
                        src,
                        &e,
                        &ExpectedErrorMessageBuilder::error(&format!("the input `{esc}` is not a valid escape"))
                            .exactly_one_underline(src)
                            .build()
                    )
                );
            })
        };
        // invalid escape `\a`
        test_invalid("\\a", vec!["\\a"]);
        // invalid escape `\b`
        test_invalid("\\b", vec!["\\b"]);
        // invalid escape `\p`
        test_invalid("\\\\aa\\p", vec!["\\p"]);
        // invalid escape `\a` and empty unicode escape
        test_invalid(r"\aaa\u{}", vec!["\\a", "\\u{}"]);
    }
}