```pdl

primitive fifo<T>(in<T> i, out<T> o) {

    // impl

}

T pick_one_of_two<T>(T one, T two) {

    // impl

}

enum Option<T>{ None, Some(T) }

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

struct Pair<T> { T first, T second }

```

This means that during the initial validation/linker phase all of the types may have polymorphic arguments. These polyargs have just an identifier, we can only determine the concrete type when we encounter it in another body where we either defer the type or where the user has explicitly instantiated the type.

For now we will use the C++-like trait/interfaceless polymorphism: once we know all of the polymorphic arguments we will try to monomorphize the type and check whether or not all calls make sense. This in itself is a recursive operation: inside the polymorph we may use other polymorphic types.

## Polymorphic Type Usage

Within functions and connectors we may employ polymorphic types. The specification of the polymorphic arguments is not required if they can be inferred. Polymorphic arguments may be partially specified by using somekind of throwaway `_` or `auto` type. When we are monomorphizing a type we must be able to fully determine all of the polymorphic arguments, if we can't then we throw a compiler error.

## Type Inference - Monomorphization

There are two parts to type inference: determining polymorphic variables and determining the `auto` variables. Among the polymorphic types we have: `struct`s, `enum`s, `union`s, `component`s and `function`s. The first three are datatypes and have no body to infer. The latter two are, for the lack of a better word, procedural types or proctypes.

We may only infer the types within a proctype if its polymorphic arguments are already inferred. Hence the type inference algorithm for a proctype does not work on the polymorphic types in its body. The type inference algorithm needs to work on all of the `auto` types in the body (potentially those of polymorphic types without explicitly specified polymorphic arguments).

If the type inference algorithm determines the arguments to a polymorphic type within the body of a proctype then we need to (recursively) instantiate a monomorph of that type. This process is potentially recursive in two ways:

1. **for datatypes**: when one instantiates a monomorph we suddenly know all of the embedded types within a datatype. At this point we may determine whether the type is potentially recursive or not. We may use this fact to mark struct members or union variants as pointerlike. We can at this point lay out the size and the offsets of the type.

2. **for proctypes**: when one instantiates a monomorph we can restart the inference process for the body of the function. During this process we may arrive at new monomorphs for datatypes or new monomorphs for function types.

## Type Inference - The Algorithm

So as determined above: when we perform type inference for a function we create a lookup for the assigned polymorphic variables and assign these where used in the expression trees. After this we end up with expression trees with `auto` types scattered here and there, potentially embedded within concrete types (e.g. `in<array<SomeStruct<byte, auto>>>`, an input port from which we get arrays of a monomorphized struct `SomeStruct` whose second argument should be inferred).

Since memory statements have already been converted into variable declarations (present in the appropriate scope) we only truly need to care about the expression trees that reside within a body. The one exception is the place where those expression trees are used: the expression tree used as the condition in an `if` statement must have a boolean return type. We have the following types of expressions, together with the constraints they impose on the inference algorithm (note that I will use the word "matching" types a lot. With that I will disregard implicit casting, for now. This is later fixed by inserting casting expressions that allow for (builtin) type conversion):

- **assignment**:

    Assignment expression (e.g. `a = 5 + 2` or `a <<= 2`). Where we make the distinction between:

    - **=**: We require that the RHS type matches the type of the LHS. If any side is known (partially) then the other side may be inferred. The return type is the type of the LHS.

    - **\*=**, **/=**, **%=**, **+=**, **-=**: We require that the LHS is of the appropriate number type and the RHS is of equal type. The return type is the type of the LHS.

    - **<<=**, **>>=**: The LHS is of an integer type and the RHS is of any integer type. The return type is the type of the LHS.

    - **&=**, **|=**, **^=**: The LHS and the RHS are of equal integer type. The return type is the type of the LHS.

- **conditional**:

    C-like ternary operator (e.g. `something() ? true : false`). We require that the test-expression is of boolean type. We require that the true-expression and the false-expression are of equal type. The return type is of the same type as the true/false-expression return type.

- **binary**:

    Binary operator, where we make the distinction between:

    - **@** (concatenate): *I might kick this one out*, requires that the LHS and RHS are arrays with equal subtype (`Array<T>`), or LHS and RHS are strings. The result is an array with the same subtype (`Array<T>`), or string.

    - **||**, **&&**: Both LHS and RHS must be booleans. The result is a boolean.

    - **|**, **&**, **^**: Both LHS and RHS must be of equal integer type. The return type is the type of the LHS.

    - **==**, **!=**: Both LHS and RHS must be of the same type. The return type is boolean

    - **<**, **>**, **<=**, **>=**: Both LHS and RHS must be of equal numeric type. The return type is boolean.

    - **<<**, **>>**: The LHS is of an integer type and the RHS if of any integer type. The return type is the type of the LHS.

    - **+**, **-**, **\***, **/**, **%**: The LHS and RHS are of equal integer type. The return type is the type of the LHS.

- **unary**:

    Unary operator, where we make the distinction between:

    **+**, **-**: Argument may be any numeric type, the return type is the same as the argument.

    **!**: Argument must be of boolean type, the return type is also boolean.

    **~**: Argument must be of any integer type, the return type is the same as the argument.

    **--**, **++**: Argument must be of any integer type. The return type is the same as the argument.

- **indexing expression**:

    Indexes into an array or a string (e.g. `variable[i]`). The index must always be a `usize`/`isize` integer type (with the appropriate implicit casts). The subject must always be of type `Array<T>` or string and the result is of type `T`. 

- **slicing expression**:

    Slices an array or a string (e.g. `some_array[5..calculate_the_end()]`). The beginning and ending indices must always be of **equal** `usize`/`isize` integer type. The subject must always be of type `Array<T>` or string, the return type is of the same type as the subject.

- **select expression**:

    Selects a member from a struct (e.g. `some_struct.some_field`). This expression can only be evaluated if we know the type of the subject (which must be a struct). If the field exists on that struct then we may determine the return type to be the type of that field.

- **array expression**:

    Constructs an array by explicitly specifying the members of that array. Lets assume for now that you cannot specify a string in this silly fashion. Then all of the array elements must have the same type `T`, and the result type of the expression is `Array<T>`.

- **call expression**: 

    Calls a particular function (e.g. `some_function<some_type>(some_arg)`). Non-polymorphic function arguments imply that the argument must be of the type of the argument. A non-polymorphic return type fixes the output type of the expression.

    In the polymorphic case the inference works the other way around: once we know the output type of the expression that is used as a polymorphic variable, then we can fix that particular polymorphic argument and feed that information to all places where that polymorphic argument is used.

    The same is true for the return type: if the return type of the call is polymorphic then the place where this return type is used determines the type of the polymorphic argument.

- **constant expression**: *This requires a lot of rework at some point.*

    A constant expression contains a literal of a specific type. Hence the output type of the literal is the type of the literal itself. In case of literal `struct`, `enum` and `union` instances the output type is that exact datatype.

    For the embedded types we have two cases: if the embedded type is not polymorphic and some expression is used at that position, then the embedded type must match the output type of the expression. If the embedded type is polymorphic then the output type of the expression determines the polymorphic argument. 

    In case of `string` literals the output type is also a `string`. However, in the case of integer literals we can only determine that the output type is some integer, the place where the literal is employed determines the integer type. It is valid to use this for byteshifting, but also for operating on floating-point types. In the case of decimal literals we can use these for operations on floating point types. But again: whether it is a `float` or a `double` depends on the place where the literal is used.

- **variable expression**:

    Refers to some variable declared somewhere. Hence the return type is the same as the type of the variable.

        for root_id in heap.protocol_descriptions.iter().map(|v| v.this) {

            self.write_module(heap, root_id);

            w.write_all(self.buffer.as_bytes()).expect("flush buffer");

            self.buffer.clear();

        }

    }

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

    // Top-level module writing

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

    fn write_module(&mut self, heap: &Heap, root_id: RootId) {

        self.kv(0).with_id(PREFIX_ROOT_ID, root_id.index)

            .with_s_key("Module");

        let root = &heap[root_id];

        self.kv(1).with_s_key("Pragmas");

        for pragma_id in &root.pragmas {

            self.write_pragma(heap, *pragma_id, 2);

        }

        self.kv(1).with_s_key("Imports");

        for import_id in &root.imports {

            self.write_import(heap, *import_id, 2);

        }

        self.kv(1).with_s_key("Definitions");

        for def_id in &root.definitions {

            self.write_definition(heap, *def_id, 2);

        }

    }

    fn write_pragma(&mut self, heap: &Heap, pragma_id: PragmaId, indent: usize) {

        match &heap[pragma_id] {

            Pragma::Version(pragma) => {

                self.kv(indent).with_id(PREFIX_PRAGMA_ID, pragma.this.index)

                    .with_s_key("PragmaVersion")

                    .with_disp_val(&pragma.version);

            },

            Pragma::Module(pragma) => {

                self.kv(indent).with_id(PREFIX_PRAGMA_ID, pragma.this.index)

                    .with_s_key("PragmaModule")

                    .with_ascii_val(&pragma.value);

            }

        }

    }

    fn write_import(&mut self, heap: &Heap, import_id: ImportId, indent: usize) {

        let import = &heap[import_id];

        let indent2 = indent + 1;

        match import {

            Import::Module(import) => {

                self.kv(indent).with_id(PREFIX_IMPORT_ID, import.this.index)

                    .with_s_key("ImportModule");

                self.kv(indent2).with_s_key("Name").with_ascii_val(&import.module_name);

                self.kv(indent2).with_s_key("Alias").with_ascii_val(&import.alias);

                self.kv(indent2).with_s_key("Target")

                    .with_opt_disp_val(import.module_id.as_ref().map(|v| &v.index));

            },

            Import::Symbols(import) => {

                self.kv(indent).with_id(PREFIX_IMPORT_ID, import.this.index)

                    .with_s_key("ImportSymbol");

                self.kv(indent2).with_s_key("Name").with_ascii_val(&import.module_name);

                self.kv(indent2).with_s_key("Target")

                    .with_opt_disp_val(import.module_id.as_ref().map(|v| &v.index));

                self.kv(indent2).with_s_key("Symbols");

                let indent3 = indent2 + 1;

                let indent4 = indent3 + 1;

                for symbol in &import.symbols {

                    self.kv(indent3).with_s_key("AliasedSymbol");

                    self.kv(indent4).with_s_key("Name").with_ascii_val(&symbol.name);

                    self.kv(indent4).with_s_key("Alias").with_ascii_val(&symbol.alias);

                    self.kv(indent4).with_s_key("Definition")

                        .with_opt_disp_val(symbol.definition_id.as_ref().map(|v| &v.index));

                }

            }

        }

    }

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

    // Top-level definition writing

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

    fn write_definition(&mut self, heap: &Heap, def_id: DefinitionId, indent: usize) {

        let indent2 = indent + 1;

        let indent3 = indent2 + 1;

        let indent4 = indent3 + 1;

        match &heap[def_id] {

            Definition::Struct(_) => todo!("implement Definition::Struct"),

            Definition::Enum(_) => todo!("implement Definition::Enum"),

            Definition::Component(def) => {

                self.kv(indent).with_id(PREFIX_COMPONENT_ID,def.this.0.index)

                    .with_s_key("DefinitionComponent");

                self.kv(indent2).with_s_key("Name").with_ascii_val(&def.identifier.value);

                self.kv(indent2).with_s_key("Variant").with_debug_val(&def.variant);

                self.kv(indent2).with_s_key("Parameters");

                for param_id in &def.parameters {

                }

                self.kv(indent2).with_s_key("Body");

                self.write_stmt(heap, def.body, indent3);

            }

        }

    }

    fn write_stmt(&mut self, heap: &Heap, stmt_id: StatementId, indent: usize) {

        let stmt = &heap[stmt_id];

        let indent2 = indent + 1;

        let indent3 = indent2 + 1;

        match stmt {

            Statement::Block(stmt) => {

                self.kv(indent).with_id(PREFIX_BLOCK_STMT_ID, stmt.this.0.index)

                    .with_s_key("Block");

                for stmt_id in &stmt.statements {

                    self.write_stmt(heap, *stmt_id, indent2);

                }

            },

            Statement::Local(stmt) => {

                match stmt {

                    LocalStatement::Channel(stmt) => {

                        self.kv(indent).with_id(PREFIX_CHANNEL_STMT_ID, stmt.this.0.0.index)

                            .with_s_key("LocalChannel");

                        self.kv(indent2).with_s_key("From");

                        self.write_local(heap, stmt.from, indent3);

                        self.kv(indent2).with_s_key("To");

                        self.write_local(heap, stmt.to, indent3);

                        self.kv(indent2).with_s_key("Next")

                            .with_opt_disp_val(stmt.next.as_ref().map(|v| &v.index));

                    },

                    LocalStatement::Memory(stmt) => {

                        self.kv(indent).with_id(PREFIX_MEM_STMT_ID, stmt.this.0.0.index)

                            .with_s_key("LocalMemory");

                        self.kv(indent2).with_s_key("Variable");

                        self.write_local(heap, stmt.variable, indent3);

                        self.kv(indent2).with_s_key("initial");

                        self.write_expr(heap, stmt.initial, indent3);

                        self.kv(indent2).with_s_key("Next")

                            .with_opt_disp_val(stmt.next.as_ref().map(|v| &v.index));

                    }

                }

            },

            Statement::Skip(stmt) => {

                self.kv(indent).with_id(PREFIX_SKIP_STMT_ID, stmt.this.0.index)

                    .with_s_key("Skip");

                self.kv(indent2).with_s_key("Next")

                    .with_opt_disp_val(stmt.next.as_ref().map(|v| &v.index));

            },

            Statement::Labeled(stmt) => {

                self.kv(indent).with_id(PREFIX_LABELED_STMT_ID, stmt.this.0.index)

                    .with_s_key("Labeled");

                self.kv(indent2).with_s_key("Label").with_ascii_val(&stmt.label.value);

                self.kv(indent2).with_s_key("Statement");

                self.write_stmt(heap, stmt.body, indent3);

            },

            Statement::If(stmt) => {

                self.kv(indent).with_id(PREFIX_IF_STMT_ID, stmt.this.0.index)

                    .with_s_key("If");

                self.kv(indent2).with_s_key("EndIf")

                    .with_opt_disp_val(stmt.end_if.as_ref().map(|v| &v.0.index));

                self.kv(indent2).with_s_key("Condition");

                self.write_expr(heap, stmt.test, indent3);

                self.kv(indent2).with_s_key("TrueBody");

                self.write_stmt(heap, stmt.true_body, indent3);

                self.kv(indent2).with_s_key("FalseBody");

                self.write_stmt(heap, stmt.false_body, indent3);

            },

            Statement::EndIf(stmt) => {

                self.kv(indent).with_id(PREFIX_ENDIF_STMT_ID, stmt.this.0.index)

                    .with_s_key("EndIf");

                self.kv(indent2).with_s_key("StartIf").with_disp_val(&stmt.start_if.0.index);

                self.kv(indent2).with_s_key("Next")

                    .with_opt_disp_val(stmt.next.as_ref().map(|v| &v.index));

            },

            Statement::While(stmt) => {

                self.kv(indent).with_id(PREFIX_WHILE_STMT_ID, stmt.this.0.index)

                    .with_s_key("While");

                self.kv(indent2).with_s_key("EndWhile")

                    .with_opt_disp_val(stmt.end_while.as_ref().map(|v| &v.0.index));

                self.kv(indent2).with_s_key("InSync")

                    .with_opt_disp_val(stmt.in_sync.as_ref().map(|v| &v.0.index));

                self.kv(indent2).with_s_key("Condition");

                self.write_expr(heap, stmt.test, indent3);

                self.kv(indent2).with_s_key("Body");

                self.write_stmt(heap, stmt.body, indent3);

            },

            Statement::EndWhile(stmt) => {

                self.kv(indent).with_id(PREFIX_ENDWHILE_STMT_ID, stmt.this.0.index)

                    .with_s_key("EndWhile");

                self.kv(indent2).with_s_key("StartWhile").with_disp_val(&stmt.start_while.0.index);

                self.kv(indent2).with_s_key("Next")

                    .with_opt_disp_val(stmt.next.as_ref().map(|v| &v.index));

                self.kv(indent2).with_s_key("Parent")

                    .with_custom_val(|v| write_expression_parent(v, &expr.parent));

            },

            Expression::Call(expr) => {

                self.kv(indent).with_id(PREFIX_CALL_EXPR_ID, expr.this.0.index)

                    .with_s_key("CallExpr");

                // Method

                let method = self.kv(indent2).with_s_key("Method");

                match &expr.method {

                    Method::Get => { method.with_s_val("get"); },

                    Method::Fires => { method.with_s_val("fires"); },

                    Method::Create => { method.with_s_val("create"); },

                    Method::Symbolic(symbolic) => {

                        method.with_s_val("symbolic");

                        self.kv(indent3).with_s_key("Name").with_ascii_val(&symbolic.identifier.value);

                        self.kv(indent3).with_s_key("Definition")

                            .with_opt_disp_val(symbolic.definition.as_ref().map(|v| &v.index));

                    }

                }

                // Arguments

                self.kv(indent2).with_s_key("Arguments");

                for arg_id in &expr.arguments {

                    self.write_expr(heap, *arg_id, indent3);

                }

                // Parent

                self.kv(indent2).with_s_key("Parent")

                    .with_custom_val(|v| write_expression_parent(v, &expr.parent));

            },

            Expression::Variable(expr) => {

                self.kv(indent).with_id(PREFIX_VARIABLE_EXPR_ID, expr.this.0.index)

                    .with_s_key("VariableExpr");

                self.kv(indent2).with_s_key("Name").with_ascii_val(&expr.identifier.value);

                self.kv(indent2).with_s_key("Definition")

                    .with_opt_disp_val(expr.declaration.as_ref().map(|v| &v.index));

                self.kv(indent2).with_s_key("Parent")

                    .with_custom_val(|v| write_expression_parent(v, &expr.parent));

            }

        }

    }

    fn write_local(&mut self, heap: &Heap, local_id: LocalId, indent: usize) {

        let local = &heap[local_id];

        let indent2 = indent + 1;

        self.kv(indent).with_id(PREFIX_LOCAL_ID, local_id.0.index)

            .with_s_key("Local");

        self.kv(indent2).with_s_key("Name").with_ascii_val(&local.identifier.value);

        self.kv(indent2).with_s_key("Type")

            .with_custom_val(|w| write_type(w, heap, &heap[local.parser_type]));

    }

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

    // Printing Utilities

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

    fn kv(&mut self, indent: usize) -> KV {

        KV::new(&mut self.buffer, &mut self.temp1, &mut self.temp2, indent)

    }

    fn flush<W: IOWrite>(&mut self, w: &mut W) {

        w.write(self.buffer.as_bytes()).unwrap();

        self.buffer.clear()

    }

}

fn write_option<V: Display>(target: &mut String, value: Option<V>) {

    target.clear();

    match &value {

        Some(v) => write!(target, "Some({})", v),

        None => target.write_str("None")

    };

}

fn write_type(target: &mut String, heap: &Heap, t: &ParserType) {

    use ParserTypeVariant as PTV;

    let mut embedded = Vec::new();

    match &t.variant {

        PTV::Input(id) => { target.write_str("in"); embedded.push(*id); }

        PTV::Output(id) => { target.write_str("out"); embedded.push(*id) }

        PTV::Array(id) => { target.write_str("array"); embedded.push(*id) }

        PTV::Message => { target.write_str("msg"); }

        PTV::Bool => { target.write_str("bool"); }

        PTV::Byte => { target.write_str("byte"); }

        PTV::Short => { target.write_str("short"); }

        PTV::Int => { target.write_str("int"); }

        PTV::Long => { target.write_str("long"); }

        PTV::String => { target.write_str("str"); }

        PTV::IntegerLiteral => { target.write_str("int_lit"); }

        PTV::Inferred => { target.write_str("auto"); }

        PTV::Symbolic(symbolic) => {

            target.write_str(&String::from_utf8_lossy(&symbolic.identifier.value));

            embedded.extend(&symbolic.poly_args);

        }

    };

    if !embedded.is_empty() {

        target.write_str("<");

        for (idx, embedded_id) in embedded.into_iter().enumerate() {

            if idx != 0 { target.write_str(", "); }

            write_type(target, heap, &heap[embedded_id]);

        }

        target.write_str(">");

    }

}

fn write_expression_parent(target: &mut String, parent: &ExpressionParent) {

    use ExpressionParent as EP;

    *target = match parent {

        EP::None => String::from("None"),

        EP::Memory(id) => format!("MemoryStmt({})", id.0.0.index),

        EP::If(id) => format!("IfStmt({})", id.0.index),

        EP::While(id) => format!("WhileStmt({})", id.0.index),

        EP::Return(id) => format!("ReturnStmt({})", id.0.index),

        EP::Assert(id) => format!("AssertStmt({})", id.0.index),

        EP::New(id) => format!("NewStmt({})", id.0.index),

        EP::Put(id, idx) => format!("PutStmt({}, {})", id.0.index, idx),

        EP::ExpressionStmt(id) => format!("ExprStmt({})", id.0.index),

        EP::Expression(id, idx) => format!("Expr({}, {})", id.index, idx)

    };

}

mod depth_visitor;

mod symbol_table;

// mod type_table_old;

mod type_table;

mod visitor;

mod visitor_linker;

mod utils;

use depth_visitor::*;

use symbol_table::SymbolTable;

use visitor::Visitor2;

use visitor_linker::ValidityAndLinkerVisitor;

use type_table::{TypeTable, TypeCtx};

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

use crate::protocol::inputsource::*;

use crate::protocol::lexer::*;

use std::collections::HashMap;

use crate::protocol::ast_printer::ASTWriter;

// TODO: @fixme, pub qualifier

pub(crate) struct LexedModule {

    pub(crate) source: InputSource,

    module_name: Vec<u8>,

    version: Option<u64>,

    root_id: RootId,

}

pub struct Parser {

    pub(crate) heap: Heap,

    pub(crate) modules: Vec<LexedModule>,

    pub(crate) module_lookup: HashMap<Vec<u8>, usize>, // from (optional) module name to `modules` idx

}

impl Parser {

    pub fn new() -> Self {

        Parser{

            heap: Heap::new(),

            modules: Vec::new(),

            module_lookup: HashMap::new()

        }

    }

    // TODO: @fix, temporary implementation to keep code compilable

    pub fn new_with_source(source: InputSource) -> Result<Self, ParseError2> {

        let mut parser = Parser::new();

        parser.feed(source)?;

        Ok(parser)

    }

    pub fn feed(&mut self, mut source: InputSource) -> Result<RootId, ParseError2> {

        // Lex the input source

        let mut lex = Lexer::new(&mut source);

        let pd = lex.consume_protocol_description(&mut self.heap)?;

        // Seek the module name and version

        let root = &self.heap[pd];

        let mut module_name_pos = InputPosition::default();

        let mut module_name = Vec::new();

        let mut module_version_pos = InputPosition::default();

        let mut module_version = None;

        for pragma in &root.pragmas {

            match &self.heap[*pragma] {

                Pragma::Module(module) => {

                    if !module_name.is_empty() {

                        return Err(

                            ParseError2::new_error(&source, module.position, "Double definition of module name in the same file")

                                .with_postfixed_info(&source, module_name_pos, "Previous definition was here")

                        )

                    }

                    module_name_pos = module.position.clone();

                    module_name = module.value.clone();

                },

                Pragma::Version(version) => {

                    if module_version.is_some() {

                        return Err(

                            ParseError2::new_error(&source, version.position, "Double definition of module version")

                                .with_postfixed_info(&source, module_version_pos, "Previous definition was here")

                        )

                    }

                    module_version_pos = version.position.clone();

                    module_version = Some(version.version);

                },

            }

        }

        // Add module to list of modules and prevent naming conflicts

        let cur_module_idx = self.modules.len();

        if let Some(prev_module_idx) = self.module_lookup.get(&module_name) {

            // Find `#module` statement in other module again

            let prev_module = &self.modules[*prev_module_idx];

            let prev_module_pos = self.heap[prev_module.root_id].pragmas

                .iter()

                .find_map(|p| {

                    match &self.heap[*p] {

                        Pragma::Module(module) => Some(module.position.clone()),

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

use crate::protocol::inputsource::*;

use super::type_table::*;

use super::symbol_table::*;

use super::visitor::{

    STMT_BUFFER_INIT_CAPACITY,

    EXPR_BUFFER_INIT_CAPACITY,

    Ctx,

    Visitor2,

    VisitorResult

};

use std::collections::HashMap;

pub(crate) enum InferredPart {

    // Unknown section of inferred type, yet to be inferred

    Unknown,

    // No subtypes

    Message,

    Bool,

    Byte,

    Short,

    Int,

    Long,

    String,

    // One subtype

    Array,

    Slice,

    Input,

    Output,

    // One or more subtypes

    Instance(DefinitionId, usize),

}

impl From<ConcreteTypeVariant> for InferredPart {

    fn from(v: ConcreteTypeVariant) -> Self {

        use ConcreteTypeVariant as CTV;

        use InferredPart as IP;

        match v {

            CTV::Message => IP::Message,

            CTV::Bool => IP::Bool,

            CTV::Byte => IP::Byte,

            CTV::Short => IP::Short,

            CTV::Int => IP::Int,

            CTV::Long => IP::Long,

            CTV::String => IP::String,

            CTV::Array => IP::Array,

            CTV::Slice => IP::Slice,

            CTV::Input => IP::Input,

            CTV::Output => IP::Output,

            CTV::Instance(definition_id, num_sub) => IP::Instance(definition_id, num_sub),

        }

    }

}

pub(crate) struct InferenceType {

    origin: ParserTypeId,

    inferred: Vec<InferredPart>,

}

impl InferenceType {

    fn new(inferred_type: ParserTypeId) -> Self {

    }

    fn assign_concrete(&mut self, concrete_type: &ConcreteType) {

        self.inferred.clear();

        self.inferred.reserve(concrete_type.v.len());

        for variant in concrete_type.v {

            self.inferred.push(InferredPart::from(variant))

        }

    }

}

// TODO: @cleanup I will do a very dirty implementation first, because I have no idea

//  what I am doing.

// Very rough idea:

//  - go through entire AST first, find all places where we have inferred types

//      (which may be embedded) and store them in some kind of map.

//  - go through entire AST and visit all expressions depth-first. We will

//      attempt to resolve the return type of each expression. If we can't then

//      we store them in another lookup map and link the dependency on an

//      inferred variable to that expression.

//  - keep iterating until we have completely resolved all variables.

/// This particular visitor will recurse depth-first into the AST and ensures

/// that all expressions have the appropriate types. At the moment this implies:

///

///     - Type checking arguments to unary and binary operators.

///     - Type checking assignment, indexing, slicing and select expressions.

///     - Checking arguments to functions and component instantiations.

///

/// This will be achieved by slowly descending into the AST. At any given

/// expression we may depend on

pub(crate) struct TypeResolvingVisitor {

    // Buffers for iteration over substatements and subexpressions

    stmt_buffer: Vec<StatementId>,

    expr_buffer: Vec<ExpressionId>,

    // If instantiating a monomorph of a polymorphic proctype, then we store the

    // Mapping from parser type to inferred type. We attempt to continue to

    // specify these types until we're stuck or we've fully determined the type.

    infer_types: HashMap<ParserTypeId, InferenceType>,

    // Mapping from variable ID to parser type, optionally inferred, so then

    var_types: HashMap<VariableId, ParserTypeId>,

}

impl TypeResolvingVisitor {

    pub(crate) fn new() -> Self {

        TypeResolvingVisitor{

            stmt_buffer: Vec::with_capacity(STMT_BUFFER_INIT_CAPACITY),

            expr_buffer: Vec::with_capacity(EXPR_BUFFER_INIT_CAPACITY),

            infer_types: HashMap::new(),

            var_types: HashMap::new(),

        }

    }

    fn reset(&mut self) {

        self.stmt_buffer.clear();

        self.expr_buffer.clear();

        self.infer_types.clear();

        self.var_types.clear();

    }

}

impl Visitor2 for TypeResolvingVisitor {

    // Definitions

    fn visit_component_definition(&mut self, ctx: &mut Ctx, id: ComponentId) -> VisitorResult {

        self.reset();

        let comp_def = &ctx.heap[id];

        for param_id in comp_def.parameters.clone() {

            let param = &ctx.heap[param_id];

            self.var_types.insert(param_id.upcast(), param.parser_type);

        }

        let body_stmt_id = ctx.heap[id].body;

        self.visit_stmt(ctx, body_stmt_id)

    }

    fn visit_function_definition(&mut self, ctx: &mut Ctx, id: FunctionId) -> VisitorResult {

        self.reset();

        let func_def = &ctx.heap[id];

        for param_id in func_def.parameters.clone() {

            let param = &ctx.heap[param_id];

            self.var_types.insert(param_id.upcast(), param.parser_type);

        }

        let body_stmt_id = ctx.heap[id].body;

        self.visit_stmt(ctx, body_stmt_id)

    }

    // Statements

    fn visit_block_stmt(&mut self, ctx: &mut Ctx, id: BlockStatementId) -> VisitorResult {

        // Transfer statements for traversal

        let block = &ctx.heap[id];

        for stmt_id in block.statements.clone() {

            self.visit_stmt(ctx, stmt_id);

        }

        Ok(())

    }

    fn visit_local_memory_stmt(&mut self, ctx: &mut Ctx, id: MemoryStatementId) -> VisitorResult {

        let memory_stmt = &ctx.heap[id];

        let local = &ctx.heap[memory_stmt.variable];

        self.var_types.insert(memory_stmt.variable, )

        Ok(())

    }

    fn visit_local_channel_stmt(&mut self, ctx: &mut Ctx, id: ChannelStatementId) -> VisitorResult {

        Ok(())

    }

}

impl TypeResolvingVisitor {

    fn insert_parser_type_if_needs_inference(

        &mut self, ctx: &mut Ctx, root_id: RootId, parser_type_id: ParserTypeId

    ) -> Result<(), ParseError2> {

        use ParserTypeVariant as PTV;

        let mut to_consider = vec![parser_type_id];

        while !to_consider.is_empty() {

            let parser_type_id = to_consider.pop().unwrap();

                PTV::Inferred => {

                    self.env.insert(parser_type_id, InferenceType::new(parser_type_id));

                },

                PTV::Array(subtype_id) => { to_consider.push(*subtype_id); },

                PTV::Input(subtype_id) => { to_consider.push(*subtype_id); },

                PTV::Output(subtype_id) => { to_consider.push(*subtype_id); },

                PTV::Symbolic(symbolic) => {