* recursively try to lay out each member type of a particular type. This is

 * done in a stack-like fashion, where each embedded type pushes a breadcrumb

 * unto the stack. We may discover a cycle in embedded types (we call this a

 * "type loop"). After which the type table attempts to break the type loop by

 * making specific types heap-allocated. Upon doing so we know their size

 * because their stack-size is now based on pointers. Hence breaking the type

 * loop required for computing the byte size of types.

 *

 * The reason for these type shenanigans is because PDL is a value-based

 * language, but we would still like to be able to express recursively defined

 * types like trees or linked lists. Hence we need to insert pointers somewhere

 * to break these cycles.

 *

 * We will insert these pointers into the variants of unions. However note that

 * we can only compute the stack size of a union until we've looked at *all*

 * variants. Hence we perform an initial pass where we detect type loops, a

 * second pass where we compute the stack sizes of everything, and a third pass

 * where we actually compute the size of the heap allocations for unions.

 *

 * As a final bit of global documentation: non-polymorphic types will always

 * have one "monomorph" entry. This contains the non-polymorphic type's memory

 * layout.

 */

use std::collections::HashMap;

use std::hash::{Hash, Hasher};

use crate::protocol::ast::*;

use crate::protocol::parser::symbol_table::SymbolScope;

use crate::protocol::input_source::ParseError;

use crate::protocol::parser::*;

//------------------------------------------------------------------------------

// Defined Types

//------------------------------------------------------------------------------

/// Struct wrapping around a potentially polymorphic type. If the type does not

/// have any polymorphic arguments then it will not have any monomorphs and

/// `is_polymorph` will be set to `false`. A type with polymorphic arguments

/// only has `is_polymorph` set to `true` if the polymorphic arguments actually

/// appear in the types associated types (function return argument, struct

/// field, enum variant, etc.). Otherwise the polymorphic argument is just a

/// marker and does not influence the bytesize of the type.

pub struct DefinedType {

    pub(crate) ast_root: RootId,

    pub(crate) ast_definition: DefinitionId,

    pub(crate) definition: DefinedTypeVariant,

    pub(crate) poly_vars: Vec<PolymorphicVariable>,

        if index >= self.parts.len() {

            return index;

        }

        // Iterate until bit flips, or until at end

        let expected_bit = self.parts[index].0 & Self::KEY_CHANGE_BIT;

        index += 1;

        while index < self.parts.len() {

            let current_bit = self.parts[index].0 & Self::KEY_CHANGE_BIT;

            if current_bit != expected_bit {

                return index;

            }

            index += 1;

        }

        return index;

    }

}

impl Hash for MonoSearchKey {

    fn hash<H: Hasher>(&self, state: &mut H) {

        for index in 0..self.parts.len() {

            part.hash(state);

        }

    }

}

impl PartialEq for MonoSearchKey {

    fn eq(&self, other: &Self) -> bool {

        let mut self_index = 0;

        let mut other_index = 0;

        while self_index < self.parts.len() && other_index < other.parts.len() {

            // Retrieve part and flags

            let (self_bits, _) = self.parts[self_index];

            let (other_bits, _) = other.parts[other_index];

            // Determine ending indices

            let self_end_index = self.find_end_index(self_index);

            let other_end_index = other.find_end_index(other_index);

            if self_in_use == other_in_use {

                if self_in_use {

                    // Both are in use, so both parts should be equal

                    let delta_self = self_end_index - self_index;

                    let delta_other = other_end_index - other_index;

                    if delta_self != delta_other {

                        // Both in use, but not of equal length, so the types

                        // cannot match

                        return false;

                    }

                    for _ in 0..delta_self {

                        let (_, self_part) = self.parts[self_index];

                        let (_, other_part) = other.parts[other_index];

                        if self_part != other_part {

                            return false;

                        }

    fn mark_used_polymorphic_variables(poly_vars: &mut Vec<PolymorphicVariable>, parser_type: &ParserType) {

        for element in &parser_type.elements {

            if let ParserTypeVariant::PolymorphicArgument(_, idx) = &element.variant {

                poly_vars[*idx as usize].is_in_use = true;

            }

        }

    }

    /// Sets the search key to a specific type.

    fn set_search_key_to_type(search_key: &mut MonoSearchKey, definition_map: &DefinitionMap, type_parts: &[ConcreteTypePart]) {

        use ConcreteTypePart as CTP;

        match type_parts[0] {

            // Builtin types without any embedded types

            CTP::Void | CTP::Message | CTP::Bool |

            CTP::UInt8 | CTP::UInt16 | CTP::UInt32 | CTP::UInt64 |

            CTP::SInt8 | CTP::SInt16 | CTP::SInt32 | CTP::SInt64 |

            CTP::Character | CTP::String => {

                debug_assert_eq!(type_parts.len(), 1);

                search_key.set_top_type(type_parts[0]);

            },

            // Builtin types with a single nested type

            CTP::Array | CTP::Slice | CTP::Input | CTP::Output | CTP::Pointer => {

                search_key.set(type_parts, &POLY_VARS_IN_USE[..1])

            },

            // User-defined types

            CTP::Tuple(_) => {

                Self::set_search_key_to_tuple(search_key, definition_map, type_parts);

            },

            CTP::Instance(definition_id, _) => {

                let definition_type = definition_map.get(&definition_id).unwrap();

                search_key.set(type_parts, &definition_type.poly_vars);

            },

            CTP::Function(_, _) | CTP::Component(_, _) => {

                todo!("implement function pointers")

            },

        }

    }

    fn set_search_key_to_tuple(search_key: &mut MonoSearchKey, definition_map: &DefinitionMap, type_parts: &[ConcreteTypePart]) {

        dbg_code!({

            let is_tuple = if let ConcreteTypePart::Tuple(_) = type_parts[0] { true } else { false };

            assert!(is_tuple);

        });

        search_key.set_top_type(type_parts[0]);

        for subtree in ConcreteTypeIter::new(type_parts, 0) {

            if let Some(definition_id) = get_concrete_type_definition(subtree) {

        .assert_has_monomorph("Number<Number<s16>>")

        .assert_num_monomorphs(5);

    }).for_function("instantiator", |f| { f

        .for_variable("a", |v| {v.assert_concrete_type("Number<s8>");} )

        .for_variable("e", |v| {v.assert_concrete_type("Number<Number<s16>>");} );

    });

}

#[test]

fn test_enum_monomorphs() {

    Tester::new_single_source_expect_ok(

        "no polymorph",

        "

        enum Answer{ Yes, No }

        func do_it() -> s32 { auto a = Answer::Yes; return 0; }

        "

    ).for_enum("Answer", |e| { e

        .assert_num_monomorphs(1)

        .assert_has_monomorph("Answer")

        .assert_size_alignment("Answer", 1, 1);

    });

    // Note for reader: because the enum doesn't actually use the polymorphic

    // variable, we expect to have 1 monomorph: the type only has to be laid

    Tester::new_single_source_expect_ok(

        "single polymorph",

        "

        enum Answer<T> { Yes, No }

        func instantiator() -> s32 {

            auto a = Answer<s8>::Yes;

            auto b = Answer<s8>::No;

            auto c = Answer<s32>::Yes;

            auto d = Answer<Answer<Answer<s64>>>::No;

            return 0;

        }

        "

    ).for_enum("Answer", |e| { e

    });

}

#[test]

fn test_union_monomorphs() {

    Tester::new_single_source_expect_ok(

        "no polymorph",

        "

        union Trinary { Undefined, Value(bool) }

        func do_it() -> s32 { auto a = Trinary::Value(true); return 0; }

        "

    ).for_union("Trinary", |e| { e

        .assert_num_monomorphs(1)

        .assert_has_monomorph("Trinary");

    });

    Tester::new_single_source_expect_ok(

        "polymorphs",

        "

        union Result<T, E>{ Ok(T), Err(E) }

        func instantiator() -> s32 {

            s16 a_s16 = 5;

            auto a = Result<s8, bool>::Ok(0);

            auto b = Result<bool, s8>::Ok(true);