nickel_lang_core/term/pattern/

compile.rs

//! Compilation of pattern matching down to pattern-less Nickel code.
//!
//! # Algorithm
//!
//! Compiling patterns amounts to generate a decision tree - concretely, a term composed mostly of
//! nested if-then-else - which either succeeds to match a value and returns the bindings of
//! pattern variables, or fails and returns `null`.
//!
//! Compilation of pattern matching is a well-studied problem in the literature, where efficient
//! algorithms try to avoid the duplication of checks by "grouping" them in a smart way. A standard
//! resource on this topic is the paper [_Compiling Pattern Matching to Good Decision
//! Trees_](https://dl.acm.org/doi/10.1145/1411304.1411311) by Luc Maranget.
//!
//! The current version of pattern compilation in Nickel is naive: it simply compiles each pattern
//! to a checking expression and tries them all until one works. We don't expect pattern matching
//! to be relevant for performance anytime soon (allegedly, there are much more impacting aspects
//! to handle before that). We might revisit this in the future if pattern matching turns out to be
//! a bottleneck.
//!
//! Most building blocks are generated programmatically rather than written out as e.g. members of
//! the [crate::stdlib::internals] module. While clunkier, this makes it easier to change
//! the compilation strategy in the future and is more efficient in the current setting (combining
//! building blocks from the standard library would require much more function applications, while
//! we can generate inlined versions on-the-fly here).
use std::collections::HashMap;

use indexmap::IndexMap;
use nickel_lang_parser::{
    ast::pattern::{
        ArrayPattern, ConstantPattern, ConstantPatternData, EnumPattern, OrPattern, RecordPattern,
        TailPattern, bindings::Bindings,
    },
    identifier::LocIdent,
};
use smallvec::SmallVec;

use crate::{
    ast::{
        compat::ToMainline,
        pattern::{Pattern, PatternData},
    },
    error::EvalErrorKind,
    eval::value::{NickelValue, RecordData},
    metrics::increment,
    mk_app,
    position::{PosIdx, PosTable},
    term::{
        BinaryOp, BindingType, FunData, LetAttrs, NAryOp, RecordExtKind, RecordOpKind, Term,
        UnaryOp, make,
        record::{Field, FieldMetadata},
    },
};

/// A branch of a match expression.
///
/// This is a weird mix of `Ast` and `NickelValue`, because it's used during the
/// AST lowering. Also, `Pattern` doesn't have a runtime representation.
#[derive(Debug, Clone, PartialEq)]
pub struct MatchBranch<'ast> {
    /// The pattern on the left hand side of `=>`.
    pub pattern: Pattern<'ast>,
    /// A potential guard, which is an additional side-condition defined as `if cond`. The value
    /// stored in this field is the boolean condition itself.
    pub guard: Option<NickelValue>,
    /// The body of the branch, on the right hand side of `=>`.
    pub body: NickelValue,
}

/// Generate a standard `%record/insert%` primop as generated by the parser.
fn record_insert() -> BinaryOp {
    BinaryOp::RecordInsert {
        ext_kind: RecordExtKind::WithValue,
        metadata: Default::default(),
        pending_contracts: Default::default(),
        // We don't really care for optional fields here and we don't need to filter them out
        op_kind: RecordOpKind::ConsiderAllFields,
    }
}

/// Generate a Nickel expression which checks if a field is defined in a record provided as a
/// variable, and if not, insert a default value. Return the result (either the original record
/// unchanged, or the original record with the default value). The resulting record is guaranteed
/// to have the `field` defined. The implementation uses merging to avoid dropping the contracts
/// and other metadata affected to `field`, if the field exists but has no definition.
///
/// More precisely, [with_default_value] generates the following code:
///
/// ```nickel
/// if !(%record/field_is_defined% "<field>" record_id) then
///   if %record/has_field% "<field>" record_id then
///     record_id & { "<field>" = default }
///   else
///     # Merging is potentially more costly, and we can just fallback to record insertion here.
///     %record/insert% "<field>" record_id default
/// else
///   record_id
/// ```
pub(crate) fn with_default_value(
    pos_table: &mut PosTable,
    record_id: LocIdent,
    field: LocIdent,
    default: NickelValue,
) -> NickelValue {
    let field_not_defined = make::op1(
        UnaryOp::BoolNot,
        make::op2(
            BinaryOp::RecordFieldIsDefined(RecordOpKind::ConsiderAllFields),
            NickelValue::string_posless(field.label()),
            Term::Var(record_id),
        ),
    );

    let has_field = make::op2(
        BinaryOp::RecordHasField(RecordOpKind::ConsiderAllFields),
        NickelValue::string_posless(field.label()),
        Term::Var(record_id),
    );

    let insert = mk_app!(
        make::op2(
            record_insert(),
            NickelValue::string_posless(field),
            make::var(record_id)
        ),
        default.clone()
    );

    let inner_let_if = make::if_then_else(
        has_field,
        update_with_merge(pos_table, record_id, field, Field::from(default)),
        insert,
    );

    make::if_then_else(field_not_defined, inner_let_if, Term::Var(record_id))
}

/// Update a record field by merging it with a singleton record containing the new value.
///
/// ```nickel
/// record_id & { "<id>" = <field> }
/// ```
fn update_with_merge(
    pos_table: &mut PosTable,
    record_id: LocIdent,
    id: LocIdent,
    field: Field,
) -> NickelValue {
    use crate::{ast::MergeKind, label::MergeLabel};

    let annot_spans = field
        .metadata
        .iter_annots()
        .filter_map(|labeled_ty| pos_table.get(labeled_ty.label.span).into_opt());
    let value_spans = field
        .value
        .as_ref()
        .and_then(|v| pos_table.get(v.pos_idx()).into_opt());
    let span = annot_spans
        .chain(value_spans)
        // We fuse all the definite spans together.
        // unwrap(): all span should come from the same file
        .reduce(|span1, span2| span1.fuse(span2).unwrap());

    let singleton = NickelValue::record_posless(RecordData {
        fields: IndexMap::from_iter([(id, field)]),
        ..Default::default()
    });
    // Right now, patterns are compiled on-the-fly during evaluation. We thus need to
    // perform the gen_pending_contract transformation manually, or the contracts will
    // just be ignored. One step suffices, as we create a singleton record that doesn't
    // contain other non-transformed records (the default value, if any, has been
    // transformed normally).
    //
    // unwrap(): typechecking ensures that there are no unbound variables at this point
    let singleton =
        crate::transform::gen_pending_contracts::transform_one(pos_table, singleton).unwrap();

    // Since we generate a non-recursive record and inject it in the evaluation, we must manually
    // enforce it's properly closurized.
    let singleton = NickelValue::term_posless(Term::Closurize(singleton));

    let merge_label = MergeLabel {
        span: pos_table.push(span.into()),
        kind: MergeKind::Standard,
    };

    make::op2(
        BinaryOp::Merge(merge_label),
        Term::Var(record_id),
        singleton,
    )
}

pub trait CompilePart {
    /// Compile part of a broader pattern to a Nickel expression.
    ///
    /// `value_id` is the value being matched on. The caller of `compile_part`
    /// is in charge of putting it into the environment.
    ///
    /// `match_cont` and `fail_cont` are continuations: `match_cont` is the
    /// one to use if this pattern matches, while `fail_cont` is the one to
    /// use if this pattern fails to match. Both `match_cont` and `fail_cont`
    /// are allowed to contain -- as free variables -- identifiers bound by this
    /// match expression.
    ///
    /// Pattern compilation must avoid shadowing any variables. In particular,
    /// `compile_part` is not responsible for binding any of the free variables
    /// in `match_cont` or `fail_cont`.
    ///
    /// As a motivating example, consider a match block like
    ///
    /// ```nickel
    /// let foo = 1 in
    /// [2, 'Blah] |> match {
    ///   [foo, 'Bar] => foo,
    ///   [_, 'Blah] => foo,
    /// }
    /// ```
    ///
    /// This gets compiled by calling `compile_part` on the first match arm,
    /// with a `fail_cont` continuation that falls through to the second match
    /// arm. If the first match arm's pattern were to bind `foo` to `2` and
    /// then fail to match `'Bar`, the second match arm would see the wrong
    /// binding for `foo`.
    ///
    /// To avoid this unwanted shadowing, we accept a `bindings` mapping that
    /// maps the pattern variables to pattern-local identifiers. In the example
    /// above, `bindings` would be `{ foo => %1 }`. Pattern compilation can
    /// safely bind `%1` because it doesn't shadow anything, and the actual
    /// `foo` binding will be done by the match arm just before entering the
    /// body.
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue;
}

impl<'ast> CompilePart for Pattern<'ast> {
    // Compilation of the top-level pattern wrapper. If there's an alias,
    // compiles to
    //
    // pattern_data.compile(value_id, let <alias> = value_id in <match_cont>, <fail_cont>)
    //
    // where `<alias>` is a generated id, not the actual id bound in the pattern.
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        let match_cont = if let Some(alias) = self.alias {
            make::let_one_in(bindings[&alias], Term::Var(value_id), match_cont)
        } else {
            match_cont
        };

        self.data
            .compile_part(pos_table, value_id, match_cont, fail_cont, bindings)
    }
}

impl<'ast> CompilePart for PatternData<'ast> {
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        match self {
            PatternData::Wildcard => match_cont,
            PatternData::Any(id) => make::let_one_in(bindings[id], Term::Var(value_id), match_cont),
            PatternData::Record(pat) => {
                pat.compile_part(pos_table, value_id, match_cont, fail_cont, bindings)
            }
            PatternData::Array(pat) => {
                pat.compile_part(pos_table, value_id, match_cont, fail_cont, bindings)
            }
            PatternData::Enum(pat) => {
                pat.compile_part(pos_table, value_id, match_cont, fail_cont, bindings)
            }
            PatternData::Constant(pat) => {
                pat.compile_part(pos_table, value_id, match_cont, fail_cont, bindings)
            }
            PatternData::Or(pat) => {
                pat.compile_part(pos_table, value_id, match_cont, fail_cont, bindings)
            }
        }
    }
}

impl<'ast> CompilePart for ConstantPattern<'ast> {
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        self.data
            .compile_part(pos_table, value_id, match_cont, fail_cont, bindings)
    }
}

impl<'ast> CompilePart for ConstantPatternData<'ast> {
    fn compile_part(
        &self,
        _: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        _bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        let compile_constant = |nickel_type: &str, value: NickelValue| {
            // if %typeof% value_id == '<nickel_type> && value_id == <value> then
            //   match_cont
            // else
            //   fail_cont

            // %typeof% value_id == '<nickel_type>
            let type_matches = make::op2(
                BinaryOp::Eq,
                make::op1(UnaryOp::Typeof, Term::Var(value_id)),
                NickelValue::enum_tag_posless(nickel_type),
            );

            // value_id == <value>
            let value_matches = make::op2(BinaryOp::Eq, Term::Var(value_id), value);

            // <type_matches> && <value_matches>
            let if_condition = mk_app!(make::op1(UnaryOp::BoolAnd, type_matches), value_matches);

            make::if_then_else(if_condition, match_cont, fail_cont)
        };

        match self {
            ConstantPatternData::Bool(b) => {
                compile_constant("Bool", NickelValue::bool_value_posless(*b))
            }
            ConstantPatternData::Number(n) => {
                compile_constant("Number", NickelValue::number_posless((*n).clone()))
            }
            ConstantPatternData::String(s) => {
                compile_constant("String", NickelValue::string_posless(s.to_owned()))
            }
            ConstantPatternData::Null => compile_constant("Other", NickelValue::null()),
        }
    }
}

impl<'ast> CompilePart for OrPattern<'ast> {
    // Compilation of or patterns.
    //
    // We fold over the patterns in reverse order. In the fold, the accumulator is
    // `fail_cont`, because if an element in the or pattern fails to match then it
    // falls through to the next case (which is what's in the accumulator because
    // we're folding in reverse).
    //
    // We clone `match_cont` for each alternative. This looks wasteful
    // when pretty-printing, but `NickelValue` is cheaply clonable so it's
    // probably fine. Another option would be to add an indirection through
    // a `Term::Var`.
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        self.patterns.iter().rev().fold(fail_cont, |cont, pattern| {
            pattern.compile_part(pos_table, value_id, match_cont.clone(), cont, bindings)
        })
    }
}

impl<'ast> CompilePart for RecordPattern<'ast> {
    // Compilation of the top-level record pattern wrapper.
    //
    // We check the match shallowly before extracting bindings, ensuring that
    // all non-defaulted fields are present. If the record isn't open, we also
    // check that there are no extra fields. We do this just by checking the
    // record length, because typechecking has already ensured that there are no
    // duplicate bindings.
    //
    // The very first thing the generated code does is to insert default values:
    // if there are any default values in the pattern, redefine `value_id` to
    // include them. This is the last part of this function (because we're in a
    // sort of continuation-passing style), but just keep in mind that the eager
    // tests are working on a record that already has default values.
    //
    // if %typeof% value_id == 'Record
    //   <if self.patterns has any default value>
    //     let value_id = <with_default_value(with_default_value(value_id, field0, default0), field1, default1) ...> in
    //   <end if>
    //
    //   <let length_check = if self.is_open { true } else { (%record/fields_with_opts% value_id |> %array/length%) == <self.patterns.len()> }>
    //
    //   if (%record/has_field_with_opts% field0 value_id) && (%record/has_field_with_opts% field1 value_id) && ... && <length_check> then
    //     <fold block (see below)>
    //   else
    //     <fail_cont>
    // else
    //   <fail_cont>
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        // <a> && <b>
        // (with a small optimization if one is `true`)
        fn and(a: NickelValue, b: NickelValue) -> NickelValue {
            if a.is_bool_true() {
                b
            } else if b.is_bool_true() {
                a
            } else {
                mk_app!(make::op1(UnaryOp::BoolAnd, a), b)
            }
        }

        let local_value_id = LocIdent::fresh();

        // (%record/has_field_with_opts% field0 local_value_id) && (%record/has_field_with_opts% field1 local_value_id) && ...
        //
        // Where field0, field1, etc. are all the non-defaulted fields.
        let has_fields = self.patterns.iter().rev().fold(
            NickelValue::bool_true(),
            |has_other_fields, field_pat| {
                if field_pat.default.is_some() {
                    has_other_fields
                } else {
                    let has_field = make::op2(
                        BinaryOp::RecordFieldIsDefined(RecordOpKind::ConsiderAllFields),
                        NickelValue::string_posless(field_pat.matched_id.label()),
                        Term::Var(local_value_id),
                    );

                    and(has_field, has_other_fields)
                }
            },
        );

        // If this pattern is non-open, this is
        //
        // (%record/fields_with_opts% local_value_id |> %array/length%) == <self.patterns.len()>
        let has_right_length = if self.is_open() {
            NickelValue::bool_true()
        } else {
            make::op2(
                BinaryOp::Eq,
                make::op1(
                    UnaryOp::ArrayLength,
                    make::op1(
                        UnaryOp::RecordFields(RecordOpKind::IgnoreEmptyOpt),
                        Term::Var(local_value_id),
                    ),
                ),
                NickelValue::number_posless(self.patterns.len()),
            )
        };

        let matches_shallow = and(has_fields, has_right_length);

        let match_cont = if let TailPattern::Capture(tail) = self.tail {
            // let
            //   <tail> = (%record/remove_with_opts% field0 (%record/remove_with_opts% field1 local_value_id) ... )
            // in <match_cont>
            //
            // where field0, field1, ... are all the fields matched in the pattern, and <tail> is a generated
            // id, not the actual id bound in the pattern.
            let tail_value = self.patterns.iter().fold(
                NickelValue::term_posless(Term::Var(local_value_id)),
                |tail, field_pat| {
                    make::op2(
                        BinaryOp::RecordRemove(RecordOpKind::ConsiderAllFields),
                        NickelValue::string_posless(field_pat.matched_id.label()),
                        tail,
                    )
                },
            );
            make::let_one_in(bindings[&tail], tail_value, match_cont)
        } else {
            match_cont
        };

        // The main fold block where we extract all of the bound variables.
        // Because there's an eager check before we enter this block, we
        // can't fail to extract any of the variables. However, there could be
        // sub-patterns that fail to match.
        //
        // Our accumulator is `match_cont`, the continuation to take when
        // the match succeeds.
        //
        // There are two cases in the match block, depending on whether the
        // field in the pattern has an annotation. If it doesn't, we yield
        //
        // let <field> = %static_access(<field>)% local_value_id in
        // <field_pat.pattern.compile_part(field, match_cont, fail_cont)>
        //
        // If there is an annotation, we yield
        //
        // let value_id = <update_with_merge value_id field annotation> in
        // let <field> = %static_access(<field>)% local_value_id in
        // <field_pat.pattern.compile_part(field, match_cont, fail_cont)>
        let fold_block = self
            .patterns
            .iter()
            .rev()
            .fold(match_cont, |match_cont, field_pat| {
                let local_field_id = LocIdent::fresh();
                let field = field_pat.matched_id;

                let match_cont = field_pat.pattern.compile_part(
                    pos_table,
                    local_field_id,
                    match_cont,
                    fail_cont.clone(),
                    bindings,
                );

                // %static_access(field)% value_id
                let extracted_value =
                    make::op1(UnaryOp::RecordAccess(field), Term::Var(local_value_id));

                // let <local_field_id> = <extracted_value> in <match_cont>
                let match_cont = make::let_one_in(local_field_id, extracted_value, match_cont);

                // <if !field.annotation.is_empty()>
                //   let value_id = <update_with_merge...> in <match_cont>
                // <else>
                //   <match_cont>
                // <end if>
                if !field_pat.annotation.is_empty() {
                    let annotation = field_pat.annotation.to_mainline(pos_table);
                    make::let_one_in(
                        local_value_id,
                        update_with_merge(
                            pos_table,
                            local_value_id,
                            field,
                            Field::from(FieldMetadata {
                                annotation,
                                ..Default::default()
                            }),
                        ),
                        match_cont,
                    )
                } else {
                    match_cont
                }
            });

        // if <matches_shallow> then <fold_block> else <fail_cont>
        let inner_if = make::if_then_else(matches_shallow, fold_block, fail_cont.clone());

        // %typeof% value_id == 'Record
        let is_record: NickelValue = make::op2(
            BinaryOp::Eq,
            make::op1(UnaryOp::Typeof, Term::Var(value_id)),
            NickelValue::enum_tag_posless("Record"),
        );

        // <if any default values {>
        //   let local_value_id = <with_default_value(with_default_value(value_id, field0, default0), field1, default1) ...> in match_cont
        // <} else {>
        //   match_cont
        // <}>
        //
        // where field0, default0, etc. range over the fields and their default values.
        let with_defaults = self.patterns.iter().fold(inner_if, |cont, field_pat| {
            if let Some(default) = field_pat.default.as_ref() {
                let default = default.to_mainline(pos_table);
                make::let_one_in(
                    local_value_id,
                    with_default_value(pos_table, local_value_id, field_pat.matched_id, default),
                    cont,
                )
            } else {
                cont
            }
        });

        // if <is_record> then let local_value_id = value_id in <with_defaults> else <fail_cont>
        make::if_then_else(
            is_record,
            make::let_one_in(local_value_id, Term::Var(value_id), with_defaults),
            fail_cont,
        )
    }
}

impl<'ast> CompilePart for ArrayPattern<'ast> {
    // Compilation of an array pattern.
    //
    // let value_len = %array/length% value_id in
    //
    // <if self.is_open()>
    // if %typeof% value_id == 'Array && value_len >= <self.patterns.len()>
    // <else>
    // if %typeof% value_id == 'Array && value_len == <self.patterns.len()>
    // <end if>
    //   <fold block (see below)>
    // else
    //   <fail_cont>
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        let value_len_id = LocIdent::fresh();
        let pats_len = NickelValue::number_posless(self.patterns.len());

        let match_cont = if let TailPattern::Capture(rest) = self.tail {
            // let <rest> = %array/slice% <self.patterns.len()> value_len value_id in <match_cont>
            make::let_one_in(
                bindings[&rest],
                make::opn(
                    NAryOp::ArraySlice,
                    vec![
                        pats_len.clone(),
                        Term::Var(value_len_id).into(),
                        Term::Var(value_id).into(),
                    ],
                ),
                match_cont,
            )
        } else {
            match_cont
        };

        // <fold (idx) in 0..self.patterns.len()
        //  - match_cont is the accumulator
        //  - initial accumulator is `match_cont`, which includes the tail bindings if necessary
        //  >
        //
        //   let local_value_id = %array/at% <idx> value_id in
        //   <self.patterns[idx].compile_part(local_value_id, match_cont, fail_cont)>
        //
        // <end fold>
        let fold_block: NickelValue = self.patterns.iter().enumerate().rev().fold(
            match_cont,
            |match_cont, (idx, elem_pat)| {
                let local_value_id = LocIdent::fresh();

                // %array/at% idx value_id
                let extracted_value = make::op2(
                    BinaryOp::ArrayAt,
                    Term::Var(value_id),
                    NickelValue::number_posless(idx),
                );

                make::let_one_in(
                    local_value_id,
                    extracted_value,
                    elem_pat.compile_part(
                        pos_table,
                        local_value_id,
                        match_cont,
                        fail_cont.clone(),
                        bindings,
                    ),
                )
            },
        );

        // %typeof% value_id == 'Array
        let is_array: NickelValue = make::op2(
            BinaryOp::Eq,
            make::op1(UnaryOp::Typeof, Term::Var(value_id)),
            NickelValue::enum_tag_posless("Array"),
        );

        let comp_op = if self.is_open() {
            BinaryOp::GreaterOrEq
        } else {
            BinaryOp::Eq
        };

        // <is_array> && value_len <comp_op> <self.patterns.len()>
        let outer_check = mk_app!(
            make::op1(UnaryOp::BoolAnd, is_array),
            make::op2(comp_op, Term::Var(value_len_id), pats_len)
        );

        // if <outer_check> then <fold_block> else <fail_cont>
        let outer_if = make::if_then_else(outer_check, fold_block, fail_cont);

        // let <value_len_id> = %array/length% <value_id> in <outer_if>
        make::let_one_in(
            value_len_id,
            make::op1(UnaryOp::ArrayLength, Term::Var(value_id)),
            outer_if,
        )
    }
}

impl<'ast> CompilePart for EnumPattern<'ast> {
    fn compile_part(
        &self,
        pos_table: &mut PosTable,
        value_id: LocIdent,
        match_cont: NickelValue,
        fail_cont: NickelValue,
        bindings: &HashMap<LocIdent, LocIdent>,
    ) -> NickelValue {
        // %enum/get_tag% value_id == '<self.tag>
        let tag_matches = make::op2(
            BinaryOp::Eq,
            make::op1(UnaryOp::EnumGetTag, Term::Var(value_id)),
            NickelValue::enum_tag_posless(self.tag),
        );

        if let Some(pat) = &self.pattern {
            // if %enum/is_variant% value_id && %enum/get_tag% value_id == '<self.tag> then
            //   let next_value_id = %enum/get_arg% value_id in
            //   <pattern.compile(next_value_id, match_cont, fail_cont)>
            // else
            //   fail_cont

            // %enum/is_variant% value_id && <tag_matches>
            let if_condition = mk_app!(
                make::op1(
                    UnaryOp::BoolAnd,
                    make::op1(UnaryOp::EnumIsVariant, Term::Var(value_id)),
                ),
                tag_matches
            );

            let next_value_id = LocIdent::fresh();

            make::if_then_else(
                if_condition,
                make::let_one_in(
                    next_value_id,
                    make::op1(UnaryOp::EnumGetArg, Term::Var(value_id)),
                    pat.compile_part(
                        pos_table,
                        next_value_id,
                        match_cont,
                        fail_cont.clone(),
                        bindings,
                    ),
                ),
                fail_cont,
            )
        } else {
            // if %typeof% value_id == 'Enum && !(%enum/is_variant% value_id) && <tag_matches> then
            //   match_cont
            // else
            //   fail_cont

            // %typeof% value_id == 'Enum
            let is_enum = make::op2(
                BinaryOp::Eq,
                make::op1(UnaryOp::Typeof, Term::Var(value_id)),
                NickelValue::enum_tag_posless("Enum"),
            );

            // !(%enum/is_variant% value_id)
            let is_enum_tag = make::op1(
                UnaryOp::BoolNot,
                make::op1(UnaryOp::EnumIsVariant, Term::Var(value_id)),
            );

            // <is_enum> && <is_enum_tag> && <tag_matches>
            let if_condition = mk_app!(
                make::op1(UnaryOp::BoolAnd, is_enum,),
                mk_app!(make::op1(UnaryOp::BoolAnd, is_enum_tag,), tag_matches)
            );

            make::if_then_else(if_condition, match_cont, fail_cont)
        }
    }
}

pub trait Compile {
    /// Compile a match expression to a Nickel expression matching `value`.
    fn compile(self, pos_table: &mut PosTable, value: NickelValue, pos_idx: PosIdx) -> NickelValue;
}

/// Content of a match expression.
#[derive(Debug, Clone, PartialEq)]
pub struct MatchData<'ast> {
    pub branches: Vec<MatchBranch<'ast>>,
}

impl<'ast> Compile for MatchData<'ast> {
    // Compilation of a full match expression, represented as an array of
    // its branches. Code between < and > is Rust code, think of it as a kind
    // of templating. Note that some special cases compile differently as
    // optimizations.
    //
    // let value_id = value in <fold_block>
    //
    // The main action is in <fold_block> (see below), which folds over the match branches.
    fn compile(
        mut self,
        pos_table: &mut PosTable,
        value: NickelValue,
        pos_idx: PosIdx,
    ) -> NickelValue {
        increment!("pattern_compile");

        if self.branches.iter().all(|branch| {
            // While we could get something working even with a guard, it's a bit more work and
            // there's no current incentive to do so (a guard on a tags-only match is arguably less
            // common, as such patterns don't bind any variable). For the time being, we just
            // exclude guards from the tags-only optimization.
            matches!(
                branch.pattern.data,
                PatternData::Enum(EnumPattern { pattern: None, .. }) | PatternData::Wildcard
            ) && branch.guard.is_none()
        }) {
            let wildcard_pat = self.branches.iter().enumerate().find_map(
                |(
                    idx,
                    MatchBranch {
                        pattern,
                        guard,
                        body,
                    },
                )| {
                    if matches!((&pattern.data, guard), (PatternData::Wildcard, None)) {
                        Some((idx, body.clone()))
                    } else {
                        None
                    }
                },
            );

            // If we find a wildcard pattern, we record its index in order to discard all the
            // patterns coming after the wildcard, because they are unreachable.
            let default = if let Some((idx, body)) = wildcard_pat {
                self.branches.truncate(idx + 1);
                Some(body)
            } else {
                None
            };

            let tags_only = self
                .branches
                .into_iter()
                .filter_map(
                    |MatchBranch {
                         pattern,
                         guard: _,
                         body,
                     }| {
                        if let PatternData::Enum(EnumPattern { tag, .. }) = pattern.data {
                            Some((*tag, body))
                        } else {
                            None
                        }
                    },
                )
                .collect();

            return TagsOnlyMatch {
                branches: tags_only,
                default,
            }
            .compile(pos_table, value, pos_idx);
        }

        let error_case = NickelValue::term(
            Term::RuntimeError(Box::new(EvalErrorKind::NonExhaustiveMatch {
                value: value.clone(),
                pos: pos_idx,
            })),
            pos_idx,
        );

        let value_id = LocIdent::fresh();

        // The fold block.
        //
        // As in or pattern compilation, we fold in reverse over the
        // alternatives, and our accumulator is the failure continuation. The
        // initial accumulator is a runtime error.
        //
        // This is the point at which we actually bind the variables from the
        // pattern. We start by generating a map of pattern-bound variables
        // to fresh variables (e.g. `{ foo => %1, bar => %2 }`) if `foo` and
        // `bar` are the variables bound by the current pattern. We pass
        // this map to the pattern compilation so that it will bind `%1` to
        // the expression that we'll eventually bind `foo` to.
        // See `CompilePart::compile_part` for why we do this.
        //
        // <for branch in branches.rev()
        //  - fail_cont is the accumulator
        // >
        //    <let match_cont = if there's a guard {
        //      let foo = %1, bar = %2, <...other bindings> in if <guard> then match_cont else fail_cont
        //    } else {
        //      let foo = %1, bar = %2, <...other bindings> in match_cont
        //    }
        //    >
        //    <pattern.compile_part(value_id, match_cont, fail_cont)>
        let fold_block = self
            .branches
            .into_iter()
            .rev()
            .fold(error_case, |fail_cont, branch| {
                let bindings = branch
                    .pattern
                    .bindings()
                    .iter()
                    .map(|b| (b.id, LocIdent::fresh()))
                    .collect::<HashMap<_, _>>();
                let match_cont = if let Some(guard) = branch.guard {
                    // The guard expression becomes part of the match
                    // continuation, so it will be evaluated in the same
                    // environment as the body of the branch.
                    make::if_then_else(guard, branch.body, fail_cont.clone())
                } else {
                    branch.body
                };

                let match_cont = make::let_in(
                    false,
                    bindings
                        .iter()
                        .map(|(binding_id, fresh_id)| (*binding_id, Term::Var(*fresh_id))),
                    match_cont,
                );
                branch
                    .pattern
                    .compile_part(pos_table, value_id, match_cont, fail_cont, &bindings)
            });

        // let value_id = value in <fold_block>
        make::let_one_in(value_id, value, fold_block)
    }
}

/// Simple wrapper used to implement specialization of match statements when all of the patterns
/// are enum tags. Instead of a sequence of conditionals (which has linear time complexity), we use
/// a special primops based on a hashmap, which has amortized constant time complexity.
struct TagsOnlyMatch {
    branches: Vec<(LocIdent, NickelValue)>,
    default: Option<NickelValue>,
}

impl Compile for TagsOnlyMatch {
    fn compile(self, _: &mut PosTable, value: NickelValue, pos_idx: PosIdx) -> NickelValue {
        increment!("pattern_comile(tags_only_match)");

        // We simply use the corresponding specialized primop in that case.
        let match_op = mk_app!(
            make::op1(
                UnaryOp::TagsOnlyMatch {
                    has_default: self.default.is_some()
                },
                value
            )
            .with_pos_idx(pos_idx),
            NickelValue::record_posless(RecordData::with_field_values(self.branches.into_iter()))
        );

        let match_op = if let Some(default) = self.default {
            mk_app!(match_op, default)
        } else {
            match_op
        };

        match_op.with_pos_idx(pos_idx)
    }
}

/// Compile a destructuring let-binding into a `Term` (which has no destructuring let)
///
/// A let-binding
///
/// ```text
/// let
///   <pat1> = <bound1>,
///   <pat2> = <bound2>
/// in body
/// ```
///
/// in which `<pat1>` binds `foo` and `<pat2>` binds `bar` is desugared to
///
/// ```text
/// let
///   %b1 = <bound1>,
///   %b2 = <bound2>,
/// in
/// let
///   %r1 = <pat1.compile_part(%b1, { foo = %c1 }, <error>, <{ foo => %c1 }>)>,
///   %r2 = <pat2.compile_part(%b2, { baz = %c2 }, <error>), <{ bar => %c2 }>)>,
/// in
/// let
///   foo = %r1.foo,
///   ...
///   baz = %r2.baz,
/// in (%seq% %r1) (%seq% %r2) body
/// ```
/// where `foo` and `baz` are names bound in `<pat1>` and `<pat2>`.
///
/// There's some ambiguity about where to put the error-checking. It might be natural
/// to put it before trying to access `%r1.foo`, but that would only raise the error
/// if someone tries to evaluate `foo`. Putting it in the body as above raises
/// an error, for example, in `let 'Foo = 'Bar in true`.
///
/// A recursive let-binding is desugared almost the same way, except that everything is
/// shoved into a single let-rec block instead of three nested blocks.
pub fn compile_let_pattern<'ast>(
    pos_table: &mut PosTable,
    bindings: &[(&Pattern<'ast>, NickelValue)],
    body: NickelValue,
    attrs: LetAttrs,
) -> Term {
    // Outer bindings are the ones we called %b1 and %b2, and %empty_record_id in the doc above.
    let mut outer_bindings = SmallVec::new();
    // Mid bindings are the ones we called %r1 and %r2 above.
    let mut mid_bindings = SmallVec::new();
    // Inner bindings are the ones that bind the actual variables defined in the patterns.
    let mut inner_bindings = SmallVec::new();

    for (pat, rhs) in bindings {
        let fused_pos = pat.pos.fuse(pos_table.get(rhs.pos_idx()));
        let error_case = NickelValue::term(
            Term::RuntimeError(Box::new(EvalErrorKind::FailedDestructuring {
                value: rhs.clone(),
                pattern_pos: pos_table.push(pat.pos),
            })),
            pos_table.push(fused_pos),
        );

        let outer_id = LocIdent::fresh();
        outer_bindings.push((outer_id, rhs.clone()));

        let mid_id = LocIdent::fresh();

        let mut pattern_bindings = HashMap::new();
        for binding in pat.bindings() {
            let id = binding.id;
            inner_bindings.push((
                id,
                make::static_access(Term::Var(mid_id), std::iter::once(id)),
            ));
            pattern_bindings.insert(id, LocIdent::fresh());
        }

        // Build the mapping from pattern variables to fresh variables
        // (see `CompilePart::compile_part` for details). This corresponds
        // to the <{ foo => %c1 }> part of the documentation above.
        let bindings_record = NickelValue::record_posless(RecordData {
            fields: pattern_bindings
                .iter()
                .map(|(bound_id, fresh_id)| {
                    (*bound_id, NickelValue::from(Term::Var(*fresh_id)).into())
                })
                .collect(),
            attrs: Default::default(),
            sealed_tail: None,
        });

        mid_bindings.push((
            mid_id,
            pat.compile_part(
                pos_table,
                outer_id,
                bindings_record,
                error_case,
                &pattern_bindings,
            ),
        ));
    }

    // Force all the "mid" ids, to make pattern failures more eager.
    // Without this, `let 'Foo = 'Bar in 1` wouldn't fail.
    let checked_body = mid_bindings.iter().rev().fold(body, |acc, (id, _)| {
        mk_app!(make::op1(UnaryOp::Seq, Term::Var(*id)), acc)
    });

    let attrs = LetAttrs {
        binding_type: BindingType::Normal,
        rec: attrs.rec,
    };
    if attrs.rec {
        Term::let_in(
            outer_bindings
                .into_iter()
                .chain(mid_bindings)
                .chain(inner_bindings)
                .collect(),
            checked_body,
            attrs,
        )
    } else {
        Term::let_in(
            outer_bindings,
            Term::let_in(
                mid_bindings,
                Term::let_in(inner_bindings, checked_body, attrs.clone()).into(),
                attrs.clone(),
            )
            .into(),
            attrs,
        )
    }
}

/// Compile a destructuring function into a `Term` (which has no destructuring function).
///
/// A function `fun <pat> => body` is desugared to `fun x => let <pat> = x in body`, and then we compile
/// the destructuring let.
pub fn compile_fun_pattern<'ast>(
    pos_table: &mut PosTable,
    pattern: &Pattern<'ast>,
    body: NickelValue,
) -> Term {
    let id = pattern.alias.unwrap_or_else(LocIdent::fresh);
    let wrapped_body = compile_let_pattern(
        pos_table,
        &[(pattern, Term::Var(id).into())],
        body,
        LetAttrs::default(),
    );
    Term::Fun(FunData {
        arg: id,
        body: wrapped_body.into(),
    })
}