/// may be called with two kinds of intentions:

    /// 1. To resolve a ParserType within the body of a function, or on

    ///     polymorphic arguments to calls/instantiations within that body. This

    ///     means that the polymorphic variables are known and can be replaced

    ///     with the monomorph we're instantiating.

    /// 2. To resolve a ParserType on a called function's definition or on

    ///     an instantiated datatype's members. This means that the polymorphic

    ///     arguments inside those ParserTypes refer to the polymorphic

    ///     variables in the called/instantiated type's definition.

    /// In the second case we place InferenceTypePart::Marker instances such

    /// that we can perform type inference on the polymorphic variables.

    fn determine_inference_type_from_parser_type_elements(

        &mut self, elements: &[ParserTypeElement],

        use_definitions_known_poly_args: bool

    ) -> InferenceType {

        use ParserTypeVariant as PTV;

        use InferenceTypePart as ITP;

        let mut infer_type = Vec::with_capacity(elements.len());

        let mut has_inferred = false;

        let mut has_markers = false;

        for element in elements {

            match &element.variant {

                // Compiler-only types

                PTV::Void => { infer_type.push(ITP::Void); },

                PTV::InputOrOutput => { infer_type.push(ITP::PortLike); has_inferred = true },

                PTV::ArrayLike => { infer_type.push(ITP::ArrayLike); has_inferred = true },

                PTV::IntegerLike => { infer_type.push(ITP::IntegerLike); has_inferred = true },

                // Builtins

                PTV::Message => {

                    // TODO: @types Remove the Message -> Byte hack at some point...

                    infer_type.push(ITP::Message);

                    infer_type.push(ITP::UInt8);

                },

                PTV::Bool => { infer_type.push(ITP::Bool); },

                PTV::UInt8 => { infer_type.push(ITP::UInt8); },

                PTV::UInt16 => { infer_type.push(ITP::UInt16); },

                PTV::UInt32 => { infer_type.push(ITP::UInt32); },

                PTV::UInt64 => { infer_type.push(ITP::UInt64); },

                PTV::SInt8 => { infer_type.push(ITP::SInt8); },

                PTV::SInt16 => { infer_type.push(ITP::SInt16); },

                PTV::SInt32 => { infer_type.push(ITP::SInt32); },

                PTV::SInt64 => { infer_type.push(ITP::SInt64); },

                PTV::Character => { infer_type.push(ITP::Character); },

                PTV::String => {

                    infer_type.push(ITP::String);

                    infer_type.push(ITP::Character);

                },

                // Special markers

                PTV::IntegerLiteral => { unreachable!("integer literal type on variable type"); },

                PTV::Inferred => {

                    infer_type.push(ITP::Unknown);

                    has_inferred = true;

                },

                // With nested types

                PTV::Array => { infer_type.push(ITP::Array); },

                PTV::Input => { infer_type.push(ITP::Input); },

                PTV::Output => { infer_type.push(ITP::Output); },

                PTV::PolymorphicArgument(belongs_to_definition, poly_arg_idx) => {

                    let poly_arg_idx = *poly_arg_idx;

                    if use_definitions_known_poly_args {

                        // Refers to polymorphic argument on procedure we're currently processing.

                        // This argument is already known.

                        debug_assert_eq!(*belongs_to_definition, self.definition_type.definition_id());

                        debug_assert!((poly_arg_idx as usize) < self.poly_vars.len());

                        Self::determine_inference_type_from_concrete_type(

                            &mut infer_type, &self.poly_vars[poly_arg_idx as usize].parts

                        );

                    } else {

                        // Polymorphic argument has to be inferred

                        has_markers = true;

                        has_inferred = true;

                        infer_type.push(ITP::Marker(poly_arg_idx));

                        infer_type.push(ITP::Unknown)

                    }

                },

                PTV::Definition(definition_id, num_embedded) => {

                    infer_type.push(ITP::Instance(*definition_id, *num_embedded));

                }

            }

        }

        InferenceType::new(has_markers, !has_inferred, infer_type)

    }

    /// Determines the inference type from an already concrete type. Applies the

    /// various type "hacks" inside the type inferencer.

    fn determine_inference_type_from_concrete_type(parser_type: &mut Vec<InferenceTypePart>, concrete_type: &[ConcreteTypePart]) {

        use InferenceTypePart as ITP;

        use ConcreteTypePart as CTP;

        for concrete_part in concrete_type {

            match concrete_part {

                CTP::Void => parser_type.push(ITP::Void),

                CTP::Bool => parser_type.push(ITP::Bool),

                CTP::UInt8 => parser_type.push(ITP::UInt8),

                CTP::UInt16 => parser_type.push(ITP::UInt16),

                CTP::UInt32 => parser_type.push(ITP::UInt32),

                CTP::UInt64 => parser_type.push(ITP::UInt64),

                CTP::SInt8 => parser_type.push(ITP::SInt8),

                CTP::SInt16 => parser_type.push(ITP::SInt16),

                CTP::SInt32 => parser_type.push(ITP::SInt32),

                CTP::SInt64 => parser_type.push(ITP::SInt64),

                CTP::Character => parser_type.push(ITP::Character),

                CTP::String => {

                    parser_type.push(ITP::String);

                    parser_type.push(ITP::Character)

                },

                CTP::Array => parser_type.push(ITP::Array),

                CTP::Slice => parser_type.push(ITP::Slice),

                CTP::Input => parser_type.push(ITP::Input),

                CTP::Output => parser_type.push(ITP::Output),

                CTP::Instance(id, num) => parser_type.push(ITP::Instance(*id, *num)),

                CTP::Function(_, _) => unreachable!("function type during concrete to inference type conversion"),

                CTP::Component(_, _) => unreachable!("component type during concrete to inference type conversion"),

            }

        }

    }

    /// Construct an error when an expression's type does not match. This

    /// happens if we infer the expression type from its arguments (e.g. the

    /// expression type of an addition operator is the type of the arguments)

    /// But the expression type was already set due to our parent (e.g. an

    /// "if statement" or a "logical not" always expecting a boolean)

    fn construct_expr_type_error(

        &self, ctx: &Ctx, expr_id: ExpressionId, arg_id: ExpressionId

    ) -> ParseError {

        // TODO: Expand and provide more meaningful information for humans

        let expr = &ctx.heap[expr_id];

        let arg_expr = &ctx.heap[arg_id];

        let expr_idx = expr.get_unique_id_in_definition();

        let arg_expr_idx = arg_expr.get_unique_id_in_definition();

        let expr_type = &self.expr_types[expr_idx as usize].expr_type;

        let arg_type = &self.expr_types[arg_expr_idx as usize].expr_type;

        return ParseError::new_error_at_span(

            &ctx.module().source, expr.operation_span(), format!(

                "incompatible types: this expression expected a '{}'",

                expr_type.display_name(&ctx.heap)

            )

        ).with_info_at_span(

            &ctx.module().source, arg_expr.full_span(), format!(

                "but this expression yields a '{}'",

                arg_type.display_name(&ctx.heap)

            )

        )

    }

    fn construct_arg_type_error(

        &self, ctx: &Ctx, expr_id: ExpressionId,

        arg1_id: ExpressionId, arg2_id: ExpressionId

    ) -> ParseError {

        let expr = &ctx.heap[expr_id];

        let arg1 = &ctx.heap[arg1_id];

        let arg2 = &ctx.heap[arg2_id];

        let arg1_idx = arg1.get_unique_id_in_definition();

        let arg1_type = &self.expr_types[arg1_idx as usize].expr_type;

        let arg2_idx = arg2.get_unique_id_in_definition();

        let arg2_type = &self.expr_types[arg2_idx as usize].expr_type;

        return ParseError::new_error_str_at_span(

            &ctx.module().source, expr.operation_span(),

            "incompatible types: cannot apply this expression"

        ).with_info_at_span(

            &ctx.module().source, arg1.full_span(), format!(

                "Because this expression has type '{}'",

                arg1_type.display_name(&ctx.heap)

            )

        ).with_info_at_span(

            &ctx.module().source, arg2.full_span(), format!(

                "But this expression has type '{}'",

                arg2_type.display_name(&ctx.heap)

            )

        )

    }

    fn construct_template_type_error(

        &self, ctx: &Ctx, expr_id: ExpressionId, template: &[InferenceTypePart]

    ) -> ParseError {

        let expr = &ctx.heap[expr_id];

        let expr_idx = expr.get_unique_id_in_definition();

        let expr_type = &self.expr_types[expr_idx as usize].expr_type;

        return ParseError::new_error_at_span(

            &ctx.module().source, expr.full_span(), format!(

                "incompatible types: got a '{}' but expected a '{}'",

                expr_type.display_name(&ctx.heap), 

                InferenceType::partial_display_name(&ctx.heap, template)

            )

            fields.push(StructField{

                identifier: field.field.clone(),

                parser_type: field.parser_type.clone(),

            });

        }

        // Make sure there are no conflicting variables

        Self::check_identifier_collision(

            modules, root_id, &fields, |field| &field.identifier, "struct field"

        )?;

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        // Construct base type in table

        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        for field in &fields {

            Self::mark_used_polymorphic_variables(&mut poly_vars, &field.parser_type);

        }

        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);

        self.lookup.insert(definition_id, DefinedType{

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Struct(StructType{

                fields,

                monomorphs: Vec::new(),

            }),

            poly_vars,

            is_polymorph

        });

        return Ok(())

    }

    /// Builds base function type.

    fn build_base_function_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {

        debug_assert!(!self.lookup.contains_key(&definition_id), "base function already built");

        let definition = ctx.heap[definition_id].as_function();

        let root_id = definition.defined_in;

        // Check and construct return types and argument types.

        debug_assert_eq!(definition.return_types.len(), 1, "not one return type"); // TODO: @ReturnValues

        for return_type in &definition.return_types {

            Self::check_member_parser_type(

                modules, ctx, root_id, return_type, definition.builtin

            )?;

        }

        let mut arguments = Vec::with_capacity(definition.parameters.len());

        for parameter_id in &definition.parameters {

            let parameter = &ctx.heap[*parameter_id];

            Self::check_member_parser_type(

                modules, ctx, root_id, &parameter.parser_type, definition.builtin

            )?;

            arguments.push(FunctionArgument{

                identifier: parameter.identifier.clone(),

                parser_type: parameter.parser_type.clone(),

            });

        }

        // Check conflict of identifiers

        Self::check_identifier_collision(

            modules, root_id, &arguments, |arg| &arg.identifier, "function argument"

        )?;

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        // Construct internal representation of function type

        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        for return_type in &definition.return_types {

            Self::mark_used_polymorphic_variables(&mut poly_vars, return_type);

        }

        for argument in &arguments {

            Self::mark_used_polymorphic_variables(&mut poly_vars, &argument.parser_type);

        }

        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);

        self.lookup.insert(definition_id, DefinedType{

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Function(FunctionType{

                return_types: definition.return_types.clone(),

                arguments,

                monomorphs: Vec::new(),

            }),

            poly_vars,

            is_polymorph

        });

        return Ok(());

    }

    /// Builds base component type.

    fn build_base_component_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {

        let definition = &ctx.heap[definition_id].as_component();

        let root_id = definition.defined_in;

        // Check the argument types

        let mut arguments = Vec::with_capacity(definition.parameters.len());

        for parameter_id in &definition.parameters {

            let parameter = &ctx.heap[*parameter_id];

            Self::check_member_parser_type(

                modules, ctx, root_id, &parameter.parser_type, false

            )?;

            arguments.push(FunctionArgument{

                identifier: parameter.identifier.clone(),

                parser_type: parameter.parser_type.clone(),

            });

        }

        // Check conflict of identifiers

        Self::check_identifier_collision(

            modules, root_id, &arguments, |arg| &arg.identifier, "connector argument"

        )?;

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        // Construct internal representation of component

        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        for argument in &arguments {

            Self::mark_used_polymorphic_variables(&mut poly_vars, &argument.parser_type);

        }

        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);

        self.lookup.insert(definition_id, DefinedType{

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Component(ComponentType{

                variant: definition.variant,

                arguments,

                monomorphs: Vec::new()

            }),

            poly_vars,

            is_polymorph

        });

        Ok(())

    }

    /// Will check if the member type (field of a struct, embedded type in a

    /// union variant) is valid.

    fn check_member_parser_type(

        modules: &[Module], ctx: &PassCtx, base_definition_root_id: RootId,

        member_parser_type: &ParserType, allow_special_compiler_types: bool

    ) -> Result<(), ParseError> {

        use ParserTypeVariant as PTV;

        for element in &member_parser_type.elements {

            match element.variant {

                // Special cases

                PTV::Void | PTV::InputOrOutput | PTV::ArrayLike | PTV::IntegerLike => {

                    if !allow_special_compiler_types {

                        unreachable!("compiler-only ParserTypeVariant in member type");

                    }

                },

                // Builtin types, always valid

                PTV::Message | PTV::Bool |

                PTV::UInt8 | PTV::UInt16 | PTV::UInt32 | PTV::UInt64 |

                PTV::SInt8 | PTV::SInt16 | PTV::SInt32 | PTV::SInt64 |

                PTV::Character | PTV::String |

                PTV::Array | PTV::Input | PTV::Output |

                // Likewise, polymorphic variables are always valid

                PTV::PolymorphicArgument(_, _) => {},

                // Types that are not constructable, or types that are not

                // allowed (and checked earlier)

                PTV::IntegerLiteral | PTV::Inferred => {

                    unreachable!("illegal ParserTypeVariant within type definition");

                },

                // Finally, user-defined types

                PTV::Definition(definition_id, _) => {

                    let definition = &ctx.heap[definition_id];

                    if !(definition.is_struct() || definition.is_enum() || definition.is_union()) {

                        let source = &modules[base_definition_root_id.index as usize].source;

                        return Err(ParseError::new_error_str_at_span(

                            source, element.element_span, "expected a datatype (a struct, enum or union)"

                        ));

                    }

                    // Otherwise, we're fine

                }

            }

        }

        // If here, then all elements check out

        return Ok(());

    }

    /// Go through a list of identifiers and ensure that all identifiers have

            auto rhs = create_array();

            auto total = lhs @ rhs;

            auto is_equal =

                check_pair(total, 0) &&

                check_pair(total, 2) &&

                check_pair(total, 4) &&

                check_pair(total, 6);

            auto is_not_equal =

                !check_pair(total, 0) ||

                !check_pair(total, 2) ||

                !check_pair(total, 4) ||

                !check_pair(total, 6);

            auto has_correct_fields =

                check_values(total, 3, 3, 4) &&

                check_values(total, 4, 1, 2);

            auto array_check = lhs == rhs && total == total;

            return is_equal && !is_not_equal && has_correct_fields && array_check;

        }

        "

    ).for_function("foo", |f| {

        f.call_ok(Some(Value::Bool(true)));

    });

}

#[test]

fn test_slicing_magic() {

    Tester::new_single_source_expect_ok("slicing", "

        struct Holder<T> {

            T[] left,

            T[] right,

        }

        func create_array<T>(T first_index, T last_index) -> T[] {

            auto result = {};

            while (first_index < last_index) {

                // Absolutely rediculous, but we don't have builtin array functions yet...

                result = result @ { first_index };

                first_index += 1;

            }

            return result;

        }

        func create_holder<T>(T left_first, T left_last, T right_first, T right_last) -> Holder<T> {

            return Holder{

                left: create_array(left_first, left_last),

                right: create_array(right_first, right_last)

            };

        }

        // Another silly thing, we first slice the full thing. Then subslice a single

        // element, then concatenate. We always return an array of two things.

        func slicing_magic<T>(Holder<T> holder, u32 left_base, u32 left_amount, u32 right_base, u32 right_amount) -> T[] {

            auto left = holder.left[left_base..left_base + left_amount];

            auto right = holder.right[right_base..right_base + right_amount];

            return left[0..1] @ right[0..1];

        }

        func foo() -> bool {

            // Preliminaries:

            // 1. construct a holder, where:

            //      - left array will be [0, 1, 2, ...]

            //      - right array will be [2, 3, 4, ...]

            // 2. Perform slicing magic, always returning an array [3, 3]

            // 3. Make sure result is 6

            // But ofcourse, because we want to be silly, we will check this for

            // any possible integer type.

            auto created_u08 = create_holder<u8> (0, 5, 2, 8);

            auto created_u16 = create_holder<u16>(0, 5, 2, 8);

            auto created_u32 = create_holder<u32>(0, 5, 2, 8);

            auto created_u64 = create_holder<u64>(0, 5, 2, 8);

            auto result_u08 = slicing_magic(created_u08, 3, 2, 1, 2);

            auto result_u16 = slicing_magic(created_u16, 3, 2, 1, 2);

            auto result_u32 = slicing_magic(created_u32, 3, 2, 1, 2);

            auto result_u64 = slicing_magic(created_u64, 3, 2, 1, 2);

            auto result_s08 = slicing_magic(create_holder<s8> (0, 5, 2, 8), 3, 2, 1, 2);

            auto result_s16 = slicing_magic(create_holder<s16>(0, 5, 2, 8), 3, 2, 1, 2);

            auto result_s32 = slicing_magic(create_holder<s32>(0, 5, 2, 8), 3, 2, 1, 2);

            auto result_s64 = slicing_magic(create_holder<s64>(0, 5, 2, 8), 3, 2, 1, 2);

            return

                result_u08[0] + result_u08[1] == 6 &&

                result_u16[0] + result_u16[1] == 6 &&

                result_u32[0] + result_u32[1] == 6 &&

                result_u64[0] + result_u64[1] == 6 &&

                result_s08[0] + result_s08[1] == 6 &&

                result_s16[0] + result_s16[1] == 6 &&

                result_s32[0] + result_s32[1] == 6 &&

                result_s64[0] + result_s64[1] == 6;

        }

    ").for_function("foo", |f| {

        f.call_ok(Some(Value::Bool(true)));

    }).for_struct("Holder", |s| { s

        .assert_num_monomorphs(8)

    });

}

#[test]

fn test_struct_fields() {

    Tester::new_single_source_expect_ok("struct field access", "

        struct Nester<T> {

            T v,

        }

        func make<T>(T inner) -> Nester<T> {

            return Nester{ v: inner };

        }

        func modify<T>(Nester<T> outer, T inner) -> Nester<T> {

            outer.v = inner;

            return outer;

        }

        func foo() -> bool {

            // Single depth modification

            auto original1 = make<u32>(5);

            auto modified1 = modify(original1, 2);

            auto success1 = original1.v == 5 && modified1.v == 2;

            // Multiple levels of modification

            auto original2 = make(make(make(make(true))));

            auto modified2 = modify(original2.v, make(make(false))); // strip one Nester level

            auto success2 = original2.v.v.v.v == true && modified2.v.v.v == false;

            return success1 && success2;

        }

    ").for_function("foo", |f| {

        f.call_ok(Some(Value::Bool(true)));

    });

}

#[test]

fn test_field_selection_polymorphism() {

    // Bit silly, but just to be sure

    Tester::new_single_source_expect_ok("struct field shuffles", "

        struct VecXYZ<T> { T x, T y, T z }

        struct VecYZX<T> { T y, T z, T x }

        struct VecZXY<T> { T z, T x, T y }

        func modify_x<T>(T input) -> T {

            input.x = 1337;

            return input;

        }

        func foo() -> bool {

            auto xyz = VecXYZ<u16>{ x: 1, y: 2, z: 3 };

            auto yzx = VecYZX<u32>{ y: 2, z: 3, x: 1 };

            auto zxy = VecZXY<u64>{ x: 1, y: 2, z: 3 }; // different initialization order

            auto mod_xyz = modify_x(xyz);

            auto mod_yzx = modify_x(yzx);

            auto mod_zxy = modify_x(zxy);

            return

                xyz.x == 1 && xyz.y == 2 && xyz.z == 3 &&

                yzx.x == 1 && yzx.y == 2 && yzx.z == 3 &&

                zxy.x == 1 && zxy.y == 2 && zxy.z == 3 &&

                mod_xyz.x == 1337 && mod_xyz.y == 2 && mod_xyz.z == 3 &&

                mod_yzx.x == 1337 && mod_yzx.y == 2 && mod_yzx.z == 3 &&

                mod_zxy.x == 1337 && mod_zxy.y == 2 && mod_zxy.z == 3;

        }

    ").for_function("foo", |f| {

        f.call_ok(Some(Value::Bool(true)));

    });

}

#[test]

fn test_index_error() {

    Tester::new_single_source_expect_ok("indexing error", "

        func check_array(u32[] vals, u32 idx) -> u32 {

            return vals[idx];

        }

        func foo() -> u32 {

            auto array = {1, 2, 3, 4, 5, 6, 7};

            check_array(array, 7);

            return array[0];

        }

    ").for_function("foo", |f| {

        f.call_err("index 7 is out of bounds: array length is 7");

    });

}