/**

 * type_table.rs

 *

 * The type table is a lookup from AST definition (which contains just what the

 * programmer typed) to a type with additional information computed (e.g. the

 * byte size and offsets of struct members). The type table should be considered

 * the authoritative source of information on types by the compiler (not the

 * AST itself!).

 *

 * The type table operates in two modes: one is where we just look up the type,

 * check its fields for correctness and mark whether it is polymorphic or not.

 * The second one is where we compute byte sizes, alignment and offsets.

 *

 * The basic algorithm for type resolving and computing byte sizes is to

 * 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>,

    pub(crate) is_polymorph: bool,

}

pub enum DefinedTypeVariant {

    Enum(EnumType),

    Union(UnionType),

    Struct(StructType),

    Procedure(ProcedureType),

}

impl DefinedTypeVariant {

    pub(crate) fn is_data_type(&self) -> bool {

        use DefinedTypeVariant as DTV;

        match self {

            DTV::Struct(_) | DTV::Enum(_) | DTV::Union(_) => return true,

            DTV::Procedure(_) => return false,

        }

    }

    pub(crate) fn as_struct(&self) -> &StructType {

        match self {

            DefinedTypeVariant::Struct(v) => v,

            _ => unreachable!()

        for part in concrete_type {

            self.parts.push((flag, *part));

        }

        self.change_bit ^= Self::KEY_CHANGE_BIT;

    }

    fn push_subtree(&mut self, concrete_type: &[ConcreteTypePart], poly_var_in_use: &[PolymorphicVariable]) {

        self.parts.push((self.change_bit | Self::KEY_IN_USE, concrete_type[0]));

        self.change_bit ^= Self::KEY_CHANGE_BIT;

        let mut poly_var_index = 0;

        for subtype in ConcreteTypeIter::new(concrete_type, 0) {

            let in_use = poly_var_in_use[poly_var_index].is_in_use;

            poly_var_index += 1;

            self.push_subtype(subtype, in_use);

        }

        debug_assert_eq!(poly_var_index, poly_var_in_use.len());

    }

    // Utilities for hashing and comparison

    fn find_end_index(&self, start_index: usize) -> usize {

        // Check if we're already at the end

        let mut index = start_index;

        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;

                        }

                        self_index += 1;

                        other_index += 1;

                    }

                } else {

                    // Both not in use, so skip associated parts

                    self_index = self_end_index;

                    other_index = other_end_index;

                }

            } else {

                // No agreement on importance of parts. This is practically

                // impossible

                unreachable!();

            }

        }

        // Everything matched, so if we're at the end of both arrays then we're

        // certain that the two keys are equal.

        return self_index == self.parts.len() && other_index == other.parts.len();

    }

}

impl Eq for MonoSearchKey{}

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

            } else if min_val >= (i16::MIN as i64) && max_val <= (i16::MAX as i64) {

                (ConcreteTypePart::SInt16, 2)

            } else if min_val >= (i32::MIN as i64) && max_val <= (i32::MAX as i64) {

                (ConcreteTypePart::SInt32, 4)

            } else {

                (ConcreteTypePart::SInt64, 8)

            }

        };

        return (ConcreteType{ parts: vec![part] }, size);

    }

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

    // Small utilities

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

    fn create_polymorphic_variables(variables: &[Identifier]) -> Vec<PolymorphicVariable> {

        let mut result = Vec::with_capacity(variables.len());

        for variable in variables.iter() {

            result.push(PolymorphicVariable{ identifier: variable.clone(), is_in_use: false });

        }

        result

    }

    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) {

                // A definition, so retrieve poly var usage info

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

                search_key.push_subtree(subtree, &definition_type.poly_vars);

            } else {

                // Not a definition, so all type information is important

                search_key.push_subtype(subtree, true);

            }

        }

    }

}

#[inline]

fn align_offset_to(offset: &mut usize, alignment: usize) {

    debug_assert!(alignment > 0);

    let alignment_min_1 = alignment - 1;

    *offset += alignment_min_1;

    *offset &= !(alignment_min_1);

}

#[inline]

fn get_concrete_type_definition(concrete_parts: &[ConcreteTypePart]) -> Option<DefinitionId> {

    match concrete_parts[0] {

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

            return Some(definition_id)

        "struct Integer{ s32 field }"

    ).for_struct("Integer", |s| { s

        .assert_num_monomorphs(1)

        .assert_has_monomorph("Integer");

    });

    Tester::new_single_source_expect_ok(

        "single polymorph",

        "

        struct Number<T>{ T number }

        func instantiator() -> s32 {

            auto a = Number<s8>{ number: 0 };

            auto b = Number<s8>{ number: 1 };

            auto c = Number<s32>{ number: 2 };

            auto d = Number<s64>{ number: 3 };

            auto e = Number<Number<s16>>{ number: Number{ number: 4 }};

            return 0;

        }

        "

    ).for_struct("Number", |s| { s

        .assert_has_monomorph("Number<s8>")

        .assert_has_monomorph("Number<s16>")

        .assert_has_monomorph("Number<s32>")

        .assert_has_monomorph("Number<s64>")

        .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);

            auto c = Result<Result<s8, s32>, Result<s16, s64>>::Err(Result::Ok(5));

            auto d = Result<Result<s8, s32>, auto>::Err(Result<auto, s64>::Ok(a_s16));

            return 0;

        }

        "

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

        .assert_num_monomorphs(5)

        .assert_has_monomorph("Result<s8,bool>")

        .assert_has_monomorph("Result<bool,s8>")

        .assert_has_monomorph("Result<Result<s8,s32>,Result<s16,s64>>")

        .assert_has_monomorph("Result<s8,s32>")

        .assert_has_monomorph("Result<s16,s64>");

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

        .for_variable("d", |v| { v

            .assert_parser_type("auto")

            .assert_concrete_type("Result<Result<s8,s32>,Result<s16,s64>>");

        });

    });

}