impl Root {

    pub fn get_definition_by_ident(&self, h: &Heap, id: &[u8]) -> Option<DefinitionId> {

        for &def in self.definitions.iter() {

            if h[def].identifier().value.as_bytes() == id {

                return Some(def);

            }

        }

        None

    }

}

#[derive(Debug, Clone)]

pub enum Pragma {

    Version(PragmaVersion),

    Module(PragmaModule),

}

impl Pragma {

    pub(crate) fn as_module(&self) -> &PragmaModule {

        match self {

            Pragma::Module(pragma) => pragma,

            _ => unreachable!("Tried to obtain {:?} as PragmaModule", self),

        }

    }

}

#[derive(Debug, Clone)]

pub struct PragmaVersion {

    pub this: PragmaId,

    // Phase 1: parser

    pub span: InputSpan, // of full pragma

    pub version: u64,

}

#[derive(Debug, Clone)]

pub struct PragmaModule {

    pub this: PragmaId,

    // Phase 1: parser

    pub span: InputSpan, // of full pragma

    pub value: Identifier,

}

#[derive(Debug, Clone)]

pub enum Import {

    Module(ImportModule),

    Symbols(ImportSymbols)

}

impl Import {

    pub(crate) fn span(&self) -> InputSpan {

        match self {

            Import::Module(v) => v.span,

            Import::Symbols(v) => v.span,

        }

    }

    pub(crate) fn as_module(&self) -> &ImportModule {

        match self {

            Import::Module(m) => m,

            _ => unreachable!("Unable to cast 'Import' to 'ImportModule'")

        }

    }

    pub(crate) fn as_symbols(&self) -> &ImportSymbols {

        match self {

            Import::Symbols(m) => m,

            _ => unreachable!("Unable to cast 'Import' to 'ImportSymbols'")

        }

    }

    pub(crate) fn as_symbols_mut(&mut self) -> &mut ImportSymbols {

        match self {

            Import::Symbols(m) => m,

            _ => unreachable!("Unable to cast 'Import' to 'ImportSymbols'")

        }

    }

}

#[derive(Debug, Clone)]

pub struct ImportModule {

    pub this: ImportId,

    // Phase 1: parser

    pub span: InputSpan,

    pub module: Identifier,

    pub alias: Identifier,

    pub module_id: RootId,

}

#[derive(Debug, Clone)]

pub struct AliasedSymbol {

    pub name: Identifier,

    pub alias: Option<Identifier>,

    pub definition_id: DefinitionId,

}

#[derive(Debug, Clone)]

pub struct ImportSymbols {

    pub this: ImportId,

    // Phase 1: parser

    pub span: InputSpan,

    pub module: Identifier,

    pub module_id: RootId,

    pub symbols: Vec<AliasedSymbol>,

}

#[derive(Debug, Clone)]

pub struct Identifier {

    pub span: InputSpan,

    pub value: StringRef<'static>,

}

impl Identifier {

    pub(crate) const fn new_empty(span: InputSpan) -> Identifier {

        return Identifier{

            span,

            value: StringRef::new_empty(),

        };

    }

}

impl PartialEq for Identifier {

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

        return self.value == other.value

    }

}

impl Display for Identifier {

    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {

        write!(f, "{}", self.value.as_str())

    }

}

#[derive(Debug, Clone, PartialEq, Eq)]

pub enum ParserTypeVariant {

    // Special builtin, only usable by the compiler and not constructable by the

    // programmer

    Void,

    InputOrOutput,

    ArrayLike,

    IntegerLike,

    // Basic builtin

    Message,

    Bool,

    UInt8, UInt16, UInt32, UInt64,

    SInt8, SInt16, SInt32, SInt64,

    Character, String,

    // Literals (need to get concrete builtin type during typechecking)

    IntegerLiteral,

    // Marker for inference

    Inferred,

    // Builtins expecting one subsequent type

    Array,

    Input,

    Output,

    // Tuple: expecting any number of elements. Note that the parser type can

    // have one-valued tuples, these will be filtered out later during type

    // checking.

    Tuple(u32), // u32 = number of subsequent types

    // User-defined types

    PolymorphicArgument(DefinitionId, u32), // u32 = index into polymorphic variables

    Definition(DefinitionId, u32), // u32 = number of subsequent types in the type tree.

}

impl ParserTypeVariant {

    pub(crate) fn num_embedded(&self) -> usize {

        use ParserTypeVariant::*;

        match self {

            Void | IntegerLike |

            Message | Bool |

            UInt8 | UInt16 | UInt32 | UInt64 |

            SInt8 | SInt16 | SInt32 | SInt64 |

            Character | String | IntegerLiteral |

            Inferred | PolymorphicArgument(_, _) =>

                0,

            ArrayLike | InputOrOutput | Array | Input | Output =>

                1,

            Definition(_, num) | Tuple(num) => *num as usize,

        }

    }

}

/// ParserTypeElement is an element of the type tree. An element may be

/// implicit, meaning that the user didn't specify the type, but it was set by

/// the compiler.

#[derive(Debug, Clone)]

pub struct ParserTypeElement {

    pub element_span: InputSpan, // span of this element, not including the child types

    pub variant: ParserTypeVariant,

}

/// ParserType is a specification of a type during the parsing phase and initial

/// linker/validator phase of the compilation process. These types may be

/// (partially) inferred or represent literals (e.g. a integer whose bytesize is

/// not yet determined).

///

/// Its contents are the depth-first serialization of the type tree. Each node

/// is a type that may accept polymorphic arguments. The polymorphic arguments

/// are then the children of the node.

#[derive(Debug, Clone)]

pub struct ParserType {

    pub elements: Vec<ParserTypeElement>,

    pub full_span: InputSpan,

}

impl ParserType {

    pub(crate) fn iter_embedded(&self, parent_idx: usize) -> ParserTypeIter {

        ParserTypeIter::new(&self.elements, parent_idx)

    }

}

/// Iterator over the embedded elements of a specific element.

pub struct ParserTypeIter<'a> {

    pub elements: &'a [ParserTypeElement],

    pub cur_embedded_idx: usize,

}

impl<'a> ParserTypeIter<'a> {

    fn new(elements: &'a [ParserTypeElement], parent_idx: usize) -> Self {

        debug_assert!(parent_idx < elements.len(), "parent index exceeds number of elements in ParserType");

        if elements[0].variant.num_embedded() == 0 {

            // Parent element does not have any embedded types, place

            // `cur_embedded_idx` at end so we will always return `None`

            Self{ elements, cur_embedded_idx: elements.len() }

        } else {

            // Parent element has an embedded type

            Self{ elements, cur_embedded_idx: parent_idx + 1 }

        }

    }

}

impl<'a> Iterator for ParserTypeIter<'a> {

    type Item = &'a [ParserTypeElement];

    fn next(&mut self) -> Option<Self::Item> {

        let elements_len = self.elements.len();

        if self.cur_embedded_idx >= elements_len {

            return None;

        }

        // Seek to the end of the subtree

        let mut depth = 1;

        let start_element = self.cur_embedded_idx;

        while self.cur_embedded_idx < elements_len {

            let cur_element = &self.elements[self.cur_embedded_idx];

            let depth_change = cur_element.variant.num_embedded() as i32 - 1;

            depth += depth_change;

            debug_assert!(depth >= 0, "illegally constructed ParserType: {:?}", self.elements);

            self.cur_embedded_idx += 1;

            if depth == 0 {

                break;

            }

        }

        debug_assert!(depth == 0, "illegally constructed ParserType: {:?}", self.elements);

        return Some(&self.elements[start_element..self.cur_embedded_idx]);

    }

}

/// ConcreteType is the representation of a type after the type inference and

/// checker is finished. These are fully typed.

#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]

pub enum ConcreteTypePart {

    // Special types (cannot be explicitly constructed by the programmer)

    Void,

    // Builtin types without nested types

    Message,

    Bool,

    UInt8, UInt16, UInt32, UInt64,

    SInt8, SInt16, SInt32, SInt64,

    Character, String,

    // Builtin types with one nested type

    Array,

    Slice,

    Input,

    Output,

    Pointer,

    // Tuple: variable number of nested types, will never be 1

    Tuple(u32),

    // User defined type with any number of nested types

    Instance(DefinitionId, u32),    // instance of data type

    Function(ProcedureDefinitionId, u32),    // instance of function

    Component(ProcedureDefinitionId, u32),   // instance of a connector

}

impl ConcreteTypePart {

    pub(crate) fn num_embedded(&self) -> u32 {

        use ConcreteTypePart::*;

        match self {

            Void | Message | Bool |

            UInt8 | UInt16 | UInt32 | UInt64 |

            SInt8 | SInt16 | SInt32 | SInt64 |

            Character | String =>

                0,

            Array | Slice | Input | Output | Pointer =>

                1,

            Tuple(num_embedded) => *num_embedded,

            Instance(_, num_embedded) => *num_embedded,

            Function(_, num_embedded) => *num_embedded,

            Component(_, num_embedded) => *num_embedded,

        }

    }

}

#[derive(Debug, Clone, Eq, PartialEq)]

pub struct ConcreteType {

    pub(crate) parts: Vec<ConcreteTypePart>

}

impl Default for ConcreteType {

    fn default() -> Self {

        Self{ parts: Vec::new() }

    }

}

impl ConcreteType {

    /// Returns an iterator over the subtrees that are type arguments (e.g. an

    /// array element's type, or a polymorphic type's arguments) to the

    /// provided parent type (specified by its index in the `parts` array).

    pub(crate) fn embedded_iter(&self, parent_part_idx: usize) -> ConcreteTypeIter {

        return ConcreteTypeIter::new(&self.parts, parent_part_idx);

    }

    /// Construct a human-readable name for the type. Because this performs

    /// a string allocation don't use it for anything else then displaying the

    /// type to the user.

    pub(crate) fn display_name(&self, heap: &Heap) -> String {

        return Self::type_parts_display_name(self.parts.as_slice(), heap);

    }

    // --- Utilities that operate on slice of parts

    /// Given the starting position of a type tree, determine the exclusive

    /// ending index.

    pub(crate) fn type_parts_subtree_end_idx(parts: &[ConcreteTypePart], start_idx: usize) -> usize {

        let mut depth = 1;

        let num_parts = parts.len();

        debug_assert!(start_idx < num_parts);

        for part_idx in start_idx..parts.len() {

            let depth_change = parts[part_idx].num_embedded() as i32 - 1;

            depth += depth_change;

            debug_assert!(depth >= 0);

            if depth == 0 {

                return part_idx + 1;

            }

        }

        debug_assert!(false, "incorrectly constructed ConcreteType instance");

        return 0;

    }

    /// Produces a human-readable representation of the concrete type parts

    fn type_parts_display_name(parts: &[ConcreteTypePart], heap: &Heap) -> String {

        let mut name = String::with_capacity(128);

        let _final_idx = Self::render_type_part_at(parts, heap, 0, &mut name);

        debug_assert_eq!(_final_idx, parts.len());

        return name;

    }

    /// Produces a human-readable representation of a single type part. Lower

    /// level utility for `type_parts_display_name`.

    fn render_type_part_at(parts: &[ConcreteTypePart], heap: &Heap, mut idx: usize, target: &mut String) -> usize {

        use ConcreteTypePart as CTP;

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

        let cur_idx = idx;

        idx += 1; // increment by 1, because it always happens

        match parts[cur_idx] {

            CTP::Void => { target.push_str("void"); },

            CTP::Message => { target.push_str(KW_TYPE_MESSAGE_STR); },

            CTP::Bool => { target.push_str(KW_TYPE_BOOL_STR); },

            CTP::UInt8 => { target.push_str(KW_TYPE_UINT8_STR); },

            CTP::UInt16 => { target.push_str(KW_TYPE_UINT16_STR); },

            CTP::UInt32 => { target.push_str(KW_TYPE_UINT32_STR); },

            CTP::UInt64 => { target.push_str(KW_TYPE_UINT64_STR); },

            CTP::SInt8 => { target.push_str(KW_TYPE_SINT8_STR); },

            CTP::SInt16 => { target.push_str(KW_TYPE_SINT16_STR); },

            CTP::SInt32 => { target.push_str(KW_TYPE_SINT32_STR); },

            CTP::SInt64 => { target.push_str(KW_TYPE_SINT64_STR); },

            CTP::Character => { target.push_str(KW_TYPE_CHAR_STR); },

            CTP::String => { target.push_str(KW_TYPE_STRING_STR); },

            CTP::Array | CTP::Slice => {

                idx = Self::render_type_part_at(parts, heap, idx, target);

                target.push_str("[]");

            },

            CTP::Input => {

                target.push_str(KW_TYPE_IN_PORT_STR);

                target.push('<');

                idx = Self::render_type_part_at(parts, heap, idx, target);

                target.push('>');

            },

            CTP::Output => {

                target.push_str(KW_TYPE_OUT_PORT_STR);

                target.push('<');

                idx = Self::render_type_part_at(parts, heap, idx, target);

                target.push('>');

            },

            CTP::Pointer => {

                target.push('*');

                idx = Self::render_type_part_at(parts, heap, idx, target);

            }

            CTP::Tuple(num_parts) => {

                target.push('(');

                if num_parts != 0 {

                    idx = Self::render_type_part_at(parts, heap, idx, target);

                    for _ in 1..num_parts {

                        target.push(',');

                        idx = Self::render_type_part_at(parts, heap, idx, target);

                    }

                }

                target.push(')');

            },

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

                idx = Self::render_definition_type_parts_at(parts, heap, definition_id, num_poly_args, idx, target);

            }

            CTP::Function(definition_id, num_poly_args) |

            CTP::Component(definition_id, num_poly_args) => {

                idx = Self::render_definition_type_parts_at(parts, heap, definition_id.upcast(), num_poly_args, idx, target);

            }

        }

        idx

    }

    fn render_definition_type_parts_at(parts: &[ConcreteTypePart], heap: &Heap, definition_id: DefinitionId, num_poly_args: u32, mut idx: usize, target: &mut String) -> usize {

        let definition = &heap[definition_id];

        target.push_str(definition.identifier().value.as_str());

        if num_poly_args != 0 {

            target.push('<');

            for poly_arg_idx in 0..num_poly_args {

                if poly_arg_idx != 0 {

                    target.push(',');

                }

                idx = Self::render_type_part_at(parts, heap, idx, target);

            }

            target.push('>');

        }

        return idx;

    }

}

#[derive(Debug)]

pub struct ConcreteTypeIter<'a> {

    parts: &'a [ConcreteTypePart],

    idx_embedded: u32,

    num_embedded: u32,

    part_idx: usize,

}

impl<'a> ConcreteTypeIter<'a> {

    pub(crate) fn new(parts: &'a[ConcreteTypePart], parent_idx: usize) -> Self {

        let num_embedded = parts[parent_idx].num_embedded();

        return ConcreteTypeIter{

            parts,

            idx_embedded: 0,

            num_embedded,

            part_idx: parent_idx + 1,

        }

    }

}

impl<'a> Iterator for ConcreteTypeIter<'a> {

    type Item = &'a [ConcreteTypePart];

    fn next(&mut self) -> Option<Self::Item> {

        if self.idx_embedded == self.num_embedded {

            return None;

        }

        // Retrieve the subtree of interest

        let start_idx = self.part_idx;

        let end_idx = ConcreteType::type_parts_subtree_end_idx(&self.parts, start_idx);

        self.idx_embedded += 1;

        self.part_idx = end_idx;

        return Some(&self.parts[start_idx..end_idx]);

    }

}

#[derive(Debug, Clone, Copy)]

pub enum ScopeAssociation {

    Definition(DefinitionId),

    Block(BlockStatementId),

    If(IfStatementId, bool), // if true, then body of "if", otherwise body of "else"

    While(WhileStatementId),

    Synchronous(SynchronousStatementId),

    SelectCase(SelectStatementId, u32), // index is select case

}

/// `ScopeNode` is a helper that links scopes in two directions. It doesn't

/// actually contain any information associated with the scope, this may be

/// found on the AST elements that `Scope` points to.

#[derive(Debug, Clone)]

pub struct Scope {

    // Relation to other scopes

    pub this: ScopeId,

    pub parent: Option<ScopeId>,

    pub nested: Vec<ScopeId>,

    // Locally available variables/labels

    pub association: ScopeAssociation,

    pub variables: Vec<VariableId>,

    pub labels: Vec<LabeledStatementId>,

    // Location trackers/counters

    pub relative_pos_in_parent: i32,

    pub first_unique_id_in_scope: i32,

    pub next_unique_id_in_scope: i32,

}

impl Scope {

    pub(crate) fn new(id: ScopeId, association: ScopeAssociation) -> Self {

        return Self{

            this: id,

            parent: None,

            nested: Vec::new(),

            association,

            variables: Vec::new(),

            labels: Vec::new(),

            relative_pos_in_parent: -1,

            first_unique_id_in_scope: -1,

            next_unique_id_in_scope: -1,

        }

    }

}

impl Scope {

    pub(crate) fn new_invalid(this: ScopeId) -> Self {

        return Self{

            this,

            parent: None,

            nested: Vec::new(),

            association: ScopeAssociation::Definition(DefinitionId::new_invalid()),

            variables: Vec::new(),

            labels: Vec::new(),

            relative_pos_in_parent: -1,

            first_unique_id_in_scope: -1,

            next_unique_id_in_scope: -1,

        };

    }

}

#[derive(Debug, Clone, PartialEq, Eq)]

pub enum VariableKind {

    Parameter,      // in parameter list of function/component

    Local,          // declared in function/component body

    Binding,        // may be bound to in a binding expression (determined in validator/linker)

}

#[derive(Debug, Clone)]

pub struct Variable {

    pub this: VariableId,

    // Parsing

    pub kind: VariableKind,

    pub parser_type: ParserType,

    pub identifier: Identifier,

    // Validator/linker

    pub relative_pos_in_parent: i32,

    pub unique_id_in_scope: i32, // Temporary fix until proper bytecode/asm is generated

}

#[derive(Debug)]

pub enum Definition {

    Struct(StructDefinition),

    Enum(EnumDefinition),

    Union(UnionDefinition),

    Procedure(ProcedureDefinition),

}