use super::*;

    #[test]

    fn display_empty_string_ref() {

        // Makes sure that null pointer inside StringRef will not cause issues

        let v = StringRef::new_empty();

    }

    #[test]

    fn test_string_just_fits() {

        let large = "0".repeat(SLAB_SIZE);

        let mut pool = StringPool::new();

    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

}

pub enum Definition {

    Struct(StructDefinition),

    Enum(EnumDefinition),

    Union(UnionDefinition),

    Procedure(ProcedureDefinition),

}

    Primitive, // without return type

    Composite,

}

/// Monomorphed instantiation of a procedure (or the sole instantiation of a

/// non-polymorphic procedure).

pub struct ProcedureDefinitionMonomorph {

    pub argument_types: Vec<TypeId>,

    pub expr_info: Vec<ExpressionInfo>

}

impl ProcedureDefinitionMonomorph {

            argument_types: Vec::new(),

            expr_info: Vec::new(),

        }

    }

}

pub struct ExpressionInfo {

    pub type_id: TypeId,

    pub variant: ExpressionInfoVariant,

}

impl ExpressionInfo {

            type_id: TypeId::new_invalid(),

            variant: ExpressionInfoVariant::Generic,

        }

    }

}

pub enum ExpressionInfoVariant {

    Generic,

    Procedure(TypeId, u32), // procedure TypeID and its monomorph index

    Select(i32), // index

}

}

/// Generic storage for functions, primitive components and composite

/// components.

// Note that we will have function definitions for builtin functions as well. In

// that case the span, the identifier span and the body are all invalid.

pub struct ProcedureDefinition {

    pub this: ProcedureDefinitionId,

    pub defined_in: RootId,

    // Symbol scanning

    pub builtin: bool,

    pub kind: ProcedureKind,

    pub return_type: Option<ParserType>, // present on functions, not components

    pub parameters: Vec<VariableId>,

    pub scope: ScopeId,

    pub body: BlockStatementId,

    // Monomorphization of typed procedures

    pub monomorphs: Vec<ProcedureDefinitionMonomorph>,

}

impl ProcedureDefinition {

    pub(crate) fn new_empty(

        this: ProcedureDefinitionId, defined_in: RootId, span: InputSpan,

        kind: ProcedureKind, identifier: Identifier, poly_vars: Vec<Identifier>

            kind, identifier, poly_vars,

            return_type: None,

            parameters: Vec::new(),

            scope: ScopeId::new_invalid(),

            body: BlockStatementId::new_invalid(),

            monomorphs: Vec::new(),

        }

    }

}

#[derive(Debug, Clone)]

pub enum Statement {

    pub(crate) expr_values: VecDeque<Value>, // hack for expression results, evaluated by popping from front/back

    pub(crate) max_stack_size: u32,

}

impl Frame {

    /// Creates a new execution frame. Does not modify the stack in any way.

        let definition = &heap[definition_id];

        let outer_scope_id = definition.scope;

        let first_statement_id = definition.body;

        // Another not-so-pretty thing that has to be replaced somewhere in the

        // future...

        let mut max_stack_size = 0;

        determine_max_stack_size(heap, outer_scope_id, &mut max_stack_size);

        Frame{

            definition: definition_id,

            monomorph_type_id,

            position: first_statement_id.upcast(),

            expr_stack: VecDeque::with_capacity(128),

            expr_values: VecDeque::with_capacity(128),

            max_stack_size,

        }

    }

pub struct Prompt {

    pub(crate) frames: Vec<Frame>,

    pub(crate) store: Store,

}

impl Prompt {

        let mut prompt = Self{

            frames: Vec::new(),

            store: Store::new(),

        };

        // Maybe do typechecking in the future?

        let max_stack_size = new_frame.max_stack_size;

        prompt.frames.push(new_frame);

        args.into_store(&mut prompt.store);

        prompt.store.reserve_stack(max_stack_size);

        prompt

                                        let argument = self.store.read_take_ownership(cur_frame.expr_values.pop_front().unwrap());

                                        self.store.stack.push(argument);

                                    }

                                    // Determine the monomorph index of the function we're calling

                                    let mono_data = &heap[cur_frame.definition].monomorphs[cur_frame.monomorph_index];

                                    // Push the new frame and reserve its stack size

                                    let new_stack_size = new_frame.max_stack_size;

                                    self.frames.push(new_frame);

                                    self.store.cur_stack_boundary = new_stack_boundary;

                                    self.store.reserve_stack(new_stack_size);

                                    // To simplify the logic a little bit we will now

                debug_assert_eq!(

                    cur_frame.expr_values.len(), heap[call_expr.procedure].parameters.len(),

                    "mismatch in expr stack size and number of arguments for new statement"

                );

                let mono_data = &heap[cur_frame.definition].monomorphs[cur_frame.monomorph_index];

                // Note that due to expression value evaluation they exist in

                // reverse order on the stack.

                // TODO: Revise this code, keep it as is to be compatible with current runtime

                let mut args = Vec::new();

                while let Some(value) = cur_frame.expr_values.pop_front() {

            return Err(ComponentCreationError::DefinitionNotComponent);

        }

        // - check number of arguments by retrieving the one instantiated

        //   monomorph

        let concrete_type = ConcreteType{ parts: vec![ConcreteTypePart::Component(ast_definition.this, 0)] };

            return Err(ComponentCreationError::InvalidNumArguments);

        }

        // - for each argument try to make sure the types match

        for arg_idx in 0..arguments.values.len() {

            let provided_value = &arguments.values[arg_idx];

            if !self.verify_same_type(expected_type, 0, &arguments, provided_value) {

                return Err(ComponentCreationError::InvalidArgumentType(arg_idx));

            }

        }

        // By now we're sure that all of the arguments are correct. So create

        // the connector.

    }

    fn lookup_module_root(&self, module_name: &[u8]) -> Option<RootId> {

        for module in self.modules.iter() {

            match &module.name {

                Some(name) => if name.as_bytes() == module_name {

                modules: &mut self.modules,

                module_idx,

                symbols: &mut self.symbol_table,

                types: &mut self.type_table,

                arch: &self.arch,

            };

        };

        while !queue.is_empty() {

            let top = queue.pop().unwrap();

            let mut ctx = visitor::Ctx{

                heap: &mut self.heap,

                modules: &mut self.modules,

    let poly_var = if has_poly_var {

        POLY_VARS.as_slice()

    } else {

        &[]

    };

}

// Note: args and return type need to be a function because we need to know the function ID.

fn insert_builtin_function<T: Fn(ProcedureDefinitionId) -> (Vec<(&'static str, ParserType)>, ParserType)> (

    p: &mut Parser, func_name: &str, polymorphic: &[&str], arg_and_return_fn: T

) {

    for poly_var in polymorphic {

    }

    let func_ident_ref = p.string_pool.intern(func_name.as_bytes());

    let procedure_id = p.heap.alloc_procedure_definition(|this| ProcedureDefinition {

        this,

        defined_in: RootId::new_invalid(),

        builtin: true,

        kind: ProcedureKind::Function,

        span: InputSpan::new(),

        identifier: Identifier{ span: InputSpan::new(), value: func_ident_ref.clone() },

        return_type: None,

        parameters: Vec::new(),

        scope: ScopeId::new_invalid(),

        body: BlockStatementId::new_invalid(),

    });

    let (arguments, return_type) = arg_and_return_fn(procedure_id);

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

    for (arg_name, arg_type) in arguments {

        let identifier = Identifier{ span: InputSpan::new(), value: p.string_pool.intern(arg_name.as_bytes()) };

        let param_id = p.heap.alloc_variable(|this| Variable{

    }

    let func = &mut p.heap[procedure_id];

    func.parameters = parameters;

    func.return_type = Some(return_type);

    p.symbol_table.insert_symbol(SymbolScope::Global, Symbol{

        name: func_ident_ref,

        variant: SymbolVariant::Definition(SymbolDefinition{

            defined_in_module: RootId::new_invalid(),

            defined_in_scope: SymbolScope::Global,

            definition_span: InputSpan::new(),

            identifier_span: InputSpan::new(),

            imported_at: None,

            class: DefinitionClass::Function,

            definition_id: procedure_id.upcast(),

        })

    }).unwrap();

}

        outer_block_stmt.statements = transformed_stmts;

        return Ok(())

    }

}

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

// Utilities to create compiler-generated AST nodes

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

fn create_ast_variable(ctx: &mut Ctx, scope_id: ScopeId) -> VariableId {

    let variable_id = ctx.heap.alloc_variable(|this| Variable{

    // Buffers for iteration over various types

    var_buffer: ScopedBuffer<VariableId>,

    expr_buffer: ScopedBuffer<ExpressionId>,

    stmt_buffer: ScopedBuffer<StatementId>,

    bool_buffer: ScopedBuffer<bool>,

    index_buffer: ScopedBuffer<usize>,

    poly_progress_buffer: ScopedBuffer<u32>,

    // 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_nodes: Vec<InferenceNode>,                     // will be transferred to type table at end

    poly_data: Vec<PolyData>,       // data for polymorph inference

    var_data: Vec<VarData>,

            parent_index: None,

            var_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),

            expr_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),

            stmt_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),

            bool_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),

            index_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),

            poly_progress_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),

            infer_nodes: Vec::with_capacity(BUFFER_INIT_CAP_LARGE),

            poly_data: Vec::with_capacity(BUFFER_INIT_CAP_SMALL),

            var_data: Vec::with_capacity(BUFFER_INIT_CAP_SMALL),

            node_queued: DequeSet::new(),

        }

    }

        debug_assert_eq!(ctx.module().phase, ModuleCompilationPhase::ValidatedAndLinked);

        let root_id = ctx.module().root_id;

        let root = &ctx.heap.protocol_descriptions[root_id];

            let first_concrete_part_and_procedure_id = match definition {

                Definition::Procedure(definition) => {

                    if definition.poly_vars.is_empty() {

                        if definition.kind == ProcedureKind::Function {

                            Some((ConcreteTypePart::Function(definition.this, 0), definition.this))

            if let Some((first_concrete_part, procedure_id)) = first_concrete_part_and_procedure_id {

                let procedure = &mut ctx.heap[procedure_id];

                let monomorph_index = procedure.monomorphs.len() as u32;

                procedure.monomorphs.push(ProcedureDefinitionMonomorph::new_invalid());

                let concrete_type = ConcreteType{ parts: vec![first_concrete_part] };

                queue.push(ResolveQueueElement{

                    root_id,

                    reserved_type_id: type_id,

                    reserved_monomorph_index: monomorph_index,

                })

            }

        }

    }

    pub(crate) fn handle_module_definition(

        &mut self, ctx: &mut Ctx, queue: &mut ResolveQueue, element: ResolveQueueElement

    ) -> VisitorResult {

        self.reset();

        }

        // Every expression checked, and new monomorphs are queued. Transfer the

        // expression information to the AST. If this is the first time we're

        // visiting this procedure then we assign expression indices as well.

        let procedure = &ctx.heap[self.procedure_id];

        let mut monomorph = ProcedureDefinitionMonomorph{

            argument_types: Vec::with_capacity(procedure.parameters.len()),

            expr_info: Vec::with_capacity(num_infer_nodes),

        };

        // For all of the expressions look up the TypeId (or create a new one).

        // For function calls and component instantiations figure out if they

        // need to be typechecked

        for infer_node in self.infer_nodes.iter_mut() {

            // Determine type ID

            let expr = &ctx.heap[infer_node.expr_id];

            // TODO: Maybe optimize? Split insertion up into lookup, then clone

            //  if needed?

            let mut concrete_type = ConcreteType::default();

            infer_node.expr_type.write_concrete_type(&mut concrete_type);

            let info_type_id = ctx.types.add_monomorphed_type(ctx.modules, ctx.heap, ctx.arch, concrete_type)?;

            // Determine procedure type ID, i.e. a called/instantiated

            // procedure's signature.

            let info_variant = if let Expression::Call(expr) = expr {

                // Construct full function type. If not yet typechecked then

                // queue it for typechecking.

                debug_assert!(expr.method.is_user_defined() || expr.method.is_public_builtin());

                let num_poly_vars = poly_data.poly_vars.len() as u32;

                let first_part = match expr.method {

                };

                let signature_type = poly_data_type_to_concrete_type(

                    ctx, infer_node.expr_id, &poly_data.poly_vars, first_part

                )?;

                let (type_id, monomorph_index) = if let Some(type_id) = ctx.types.get_procedure_monomorph_type_id(&definition_id, &signature_type.parts) {

                    // Procedure is already typechecked

                    let monomorph_index = ctx.types.get_monomorph(type_id).variant.as_procedure().monomorph_index;

                    (type_id, monomorph_index)

                } else {

                    // Procedure is not yet typechecked, reserve a TypeID and a monomorph index

                    let monomorph_index = procedure_to_check.monomorphs.len() as u32;

                    procedure_to_check.monomorphs.push(ProcedureDefinitionMonomorph::new_invalid());

                    let type_id = ctx.types.reserve_procedure_monomorph_type_id(&definition_id, signature_type, monomorph_index);

                    queue.push(ResolveQueueElement{

                        root_id: ctx.heap[definition_id].defined_in(),

                        definition_id,

                    });

                    (type_id, monomorph_index)

                };

                ExpressionInfoVariant::Procedure(type_id, monomorph_index)

                ExpressionInfoVariant::Select(infer_node.field_index)

            } else {

                ExpressionInfoVariant::Generic

            };

            infer_node.info_type_id = info_type_id;

            infer_node.info_variant = info_variant;

        }

        // Write the types of the arguments

        for parameter_id in procedure.parameters.iter().copied() {

            let mut concrete = ConcreteType::default();

            let var_data = self.var_data.iter().find(|v| v.var_id == parameter_id).unwrap();

            var_data.var_type.write_concrete_type(&mut concrete);

            let type_id = ctx.types.add_monomorphed_type(ctx.modules, ctx.heap, ctx.arch, concrete)?;

            monomorph.argument_types.push(type_id)

        }

        // Determine if we have already assigned type indices to the expressions

        // before (the indices that, for a monomorph, can retrieve the type of

        // the expression).

        if has_type_indices {

            // already have indices, so resize and then index into it

            for infer_node in self.infer_nodes.iter() {

                let type_index = ctx.heap[infer_node.expr_id].type_index();

                monomorph.expr_info[type_index as usize] = infer_node.as_expression_info();

            }

        } else {

            // no indices yet, need to be assigned in AST

        let (expr_is_str, expr_is_not_str) = self.type_is_certainly_or_certainly_not_string(node_index);

        let (arg1_is_str, arg1_is_not_str) = self.type_is_certainly_or_certainly_not_string(arg1_index);

        let (arg2_is_str, arg2_is_not_str) = self.type_is_certainly_or_certainly_not_string(arg2_index);

        let someone_is_str = expr_is_str || arg1_is_str || arg2_is_str;

        let someone_is_not_str = expr_is_not_str || arg1_is_not_str || arg2_is_not_str;

        // Note: this statement is an expression returning the progression bools

        let (node_progress, arg1_progress, arg2_progress) = if someone_is_str {

            // One of the arguments is a string, then all must be strings

            self.apply_equal3_constraint(ctx, node_index, arg1_index, arg2_index, 0)?

        } else {

            let progress_expr = if someone_is_not_str {

        let (from_index_progress, to_index_progress) =

            self.apply_equal2_constraint(ctx, node_index, from_index_index, 0, to_index_index, 0)?;

        // Same as array indexing: result depends on whether subject is string

        // or array

        let (is_string, is_not_string) = self.type_is_certainly_or_certainly_not_string(node_index);

        let (node_progress, subject_progress) = if is_string {

            // Certainly a string

            (

                self.apply_forced_constraint(ctx, node_index, &STRING_TEMPLATE)?,

                false

            )

    }

    /// Returns whether the type is certainly a string (true, false), certainly

    /// not a string (false, true), or still unknown (false, false).

    fn type_is_certainly_or_certainly_not_string(&self, node_index: InferNodeIndex) -> (bool, bool) {

        let expr_type = &self.infer_nodes[node_index].expr_type;

        let mut part_index = 0;

        while part_index < expr_type.parts.len() {

            let part = &expr_type.parts[part_index];

            if part.is_marker() {

                part_index += 1;

            prev_stmt: StatementId::new_invalid(),

            expr_parent: ExpressionParent::None,

            proc_id: ProcedureDefinitionId::new_invalid(),

            proc_kind: ProcedureKind::Function,

            must_be_assignable: None,

            relative_pos_in_parent: 0,

            control_flow_stmts: Vec::with_capacity(BUFFER_INIT_CAP_SMALL),

            variable_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),

            definition_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),

            statement_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),

            expression_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),

            scope_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),

        self.proc_id = ProcedureDefinitionId::new_invalid();

        self.proc_kind = ProcedureKind::Function;

        self.prev_stmt = StatementId::new_invalid();

        self.expr_parent = ExpressionParent::None;

        self.must_be_assignable = None;

        self.relative_pos_in_parent = 0;

        self.control_flow_stmts.clear();

    }

}

macro_rules! assign_then_erase_next_stmt {

    ($self:ident, $ctx:ident, $stmt_id:expr) => {

        section.forget();

        // Visit statements in function body

        self.visit_block_stmt(ctx, body_id)?;

        self.pop_scope(old_scope);

        self.resolve_pending_control_flow_targets(ctx)?;

        Ok(())

    }

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

        }

        let left_expr_id = assignment_expr.left;

        let right_expr_id = assignment_expr.right;

        let old_expr_parent = self.expr_parent;

        assignment_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);

        self.must_be_assignable = Some(assignment_expr.operator_span);

        self.visit_expr(ctx, left_expr_id)?;

        self.expr_parent = ExpressionParent::Expression(upcast_id, 1);

        self.must_be_assignable = None;

}

/// Procedure (functions and components of all possible types) monomorph. Also

/// stores the expression type data from the typechecking/inferencing pass.

pub struct ProcedureMonomorph {

    pub monomorph_index: u32,

}

/// Tuple monomorph. Again a kind of exception because one cannot define a named

/// tuple type containing explicit polymorphic variables. But again: we need to

/// store size/offset/alignment information, so we do it here.

pub struct TupleMonomorph {

impl Eq for MonoSearchKey{}

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

// Type table

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

// Programmer note: keep this struct free of dynamically allocated memory

#[derive(Clone)]

struct TypeLoopBreadcrumb {

    type_id: TypeId,

    next_member: u32,

    next_embedded: u32, // for unions, the index into the variant's embedded types

            // variables, but we might have instantiated it already, so:

            let concrete_parts = [ConcreteTypePart::Instance(definition_id, 0)];

            self.mono_search_key.set(&concrete_parts, &[]);

            let type_id = self.mono_type_lookup.get(&self.mono_search_key);

            if type_id.is_none() {

                self.detect_and_resolve_type_loops_for(

                    ConcreteType{

                        parts: vec![ConcreteTypePart::Instance(definition_id, 0)]

                    },

                )?;

                self.lay_out_memory_for_encountered_types(ctx.arch);

            }

        self.mono_search_key.set(&concrete_type.parts, &base_type.poly_vars);

        debug_assert!(!self.mono_type_lookup.contains_key(&self.mono_search_key));

        self.mono_type_lookup.insert(self.mono_search_key.clone(), type_id);

        self.mono_types.push(MonoType::new_empty(type_id, concrete_type, MonoTypeVariant::Procedure(ProcedureMonomorph{

            monomorph_index,

        })));

        return type_id;

    }

    /// Adds a builtin type to the type table. As this is only called by the

    /// compiler during setup we assume it cannot fail.

        self.mono_search_key.set(&concrete_type.parts, poly_vars);

        debug_assert!(!self.mono_type_lookup.contains_key(&self.mono_search_key));

        debug_assert_ne!(alignment, 0);

        let type_id = TypeId(self.mono_types.len() as i64);

        self.mono_type_lookup.insert(self.mono_search_key.clone(), type_id);

        self.mono_types.push(MonoType{

            variant: MonoTypeVariant::Builtin,

        });

        return type_id;

    }

    /// Adds a monomorphed type to the type table. If it already exists then the

    /// previous entry will be used.

    pub(crate) fn add_monomorphed_type(

        &mut self, modules: &[Module], heap: &Heap, arch: &TargetArch, concrete_type: ConcreteType

    ) -> Result<TypeId, ParseError> {

        // Check if the concrete type was already added

        if let Some(type_id) = self.mono_type_lookup.get(&self.mono_search_key) {

            return Ok(*type_id);

        }

        // Concrete type needs to be added

        let type_id = self.encountered_types[0].type_id;

        self.lay_out_memory_for_encountered_types(arch);

        return Ok(type_id);

    }

    // Detecting type loops

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

    /// Internal function that will detect type loops and check if they're

    /// resolvable. If so then the appropriate union variants will be marked as

    /// "living on heap". If not then a `ParseError` will be returned

        // Programmer notes: what happens here is the we call

        // `check_member_for_type_loops` for a particular type's member, and

        // then take action using the return value:

        // 1. It might already be resolved: in this case it implies we don't

        //  have type loops, or they have been resolved.

        // 2. A new type is encountered. If so then it is added to the type loop

        // Push the initial breadcrumb

        let initial_breadcrumb = Self::check_member_for_type_loops(

            &self.type_loop_breadcrumbs, &self.definition_lookup, &self.mono_type_lookup,

            &mut self.mono_search_key, &concrete_type

        );

        if let TypeLoopResult::PushBreadcrumb(definition_id, concrete_type) = initial_breadcrumb {

        } else {

        // Enter into the main resolving loop

        while !self.type_loop_breadcrumbs.is_empty() {

            // Because we might be modifying the breadcrumb array we need to

            let breadcrumb_idx = self.type_loop_breadcrumbs.len() - 1;

            let mut breadcrumb = self.type_loop_breadcrumbs[breadcrumb_idx].clone();

                    // We finished parsing the type

                    self.type_loop_breadcrumbs.pop();

                },

                TypeLoopResult::PushBreadcrumb(definition_id, concrete_type) => {

                    // We recurse into the member type.

                    self.type_loop_breadcrumbs[breadcrumb_idx] = breadcrumb;

                },

                TypeLoopResult::TypeLoop(first_idx) => {

                    // Because we will be modifying breadcrumbs within the

                    // type-loop handling code, put back the modified breadcrumb

                    self.type_loop_breadcrumbs[breadcrumb_idx] = breadcrumb;

        use ConcreteTypePart as CTP;

        // Depending on the type, lookup if the type has already been visited