use std::marker::PhantomData;

pub struct StringRef<'a> {

    _phantom: PhantomData<&'a [u8]>,

impl<'a> StringRef<'a> {

    /// `new` constructs a new StringRef whose data is not owned by the

    /// `StringPool`, hence cannot have a `'static` lifetime.

    pub(crate) fn new(data: &'a [u8]) -> StringRef<'a> {

        // This is an internal (compiler) function: so debug_assert that the

        // string is valid UTF8. Most commonly the input will come from the

        // code's source file, which is checked for ASCII-ness anyway.

        debug_assert!(data.is_ascii());

        let length = data.len();

        let data = data.as_ptr();

        StringRef{ data, length, _phantom: PhantomData }

    }

    pub fn as_str(&self) -> &'a str {

    pub(crate) fn intern(&mut self, data: &[u8]) -> StringRef<'static> {

            StringRef{ data: start, length: data_len, _phantom: PhantomData }

    // Not actually a signed index into the heap. But the index is set to -1 if

    // we don't know an ID yet. This is checked during debug mode.

    pub(crate) index: i32,

    pub(crate) fn new_invalid() -> Self     { Self{ index: -1, _phantom: Default::default() } }

    pub(crate) fn new(index: i32) -> Self   { Self{ index, _phantom: Default::default() } }

    pub(crate) fn is_invalid(&self) -> bool { self.index < 0 }

        // Lets keep this a runtime assert.

        assert!(self.store.len() < i32::max_value() as usize, "Arena out of capacity");

        let id = Id::new(self.store.len() as i32);

        debug_assert!(!id.is_invalid(), "attempted to index into Arena with an invalid id (index < 0)");

        debug_assert!(!id.is_invalid(), "attempted to index_mut into Arena with an invalid id (index < 0)");

            pub(crate) fn new_invalid() -> Self     { Self($parent::new_invalid()) }

            pub(crate) fn is_invalid(&self) -> bool { self.0.is_invalid() }

            pub fn upcast(self) -> $parent          { self.0 }

define_new_ast_id!(StructDefinitionId, DefinitionId, index(StructDefinition, Definition::Struct, definitions), alloc(alloc_struct_definition));

define_new_ast_id!(EnumDefinitionId, DefinitionId, index(EnumDefinition, Definition::Enum, definitions), alloc(alloc_enum_definition));

define_new_ast_id!(UnionDefinitionId, DefinitionId, index(UnionDefinition, Definition::Union, definitions), alloc(alloc_union_definition));

define_new_ast_id!(ComponentDefinitionId, DefinitionId, index(ComponentDefinition, Definition::Component, definitions), alloc(alloc_component_definition));

define_new_ast_id!(FunctionDefinitionId, DefinitionId, index(FunctionDefinition, Definition::Function, definitions), alloc(alloc_function_definition));

    pub span: InputSpan,

    pub module_name: Identifier,

    pub module_id: RootId,

    pub span: InputSpan,

    pub value: StringRef<'static>,

    Component(ComponentDefinition),

    Function(FunctionDefinition),

    pub fn as_component(&self) -> &ComponentDefinition {

    pub fn as_function(&self) -> &FunctionDefinition {

    pub this: StructDefinitionId,

    pub span: InputSpan,

impl StructDefinition {

    pub(crate) fn new_empty(this: StructDefinitionId, span: InputSpan, identifier: Identifier) -> Self {

        Self{ this, span, identifier, poly_vars: Vec::new(), fields: Vec::new() }

    }

}

    pub this: EnumDefinitionId,

    pub span: InputSpan,

impl EnumDefinition {

    pub(crate) fn new_empty(this: EnumDefinitionId, span: InputSpan, identifier: Identifier) -> Self {

        Self{ this, span, identifier, poly_vars: Vec::new(), variants: Vec::new() }

    }

}

    pub this: UnionDefinitionId,

    pub span: InputSpan,

impl UnionDefinition {

    pub(crate) fn new_empty(this: UnionDefinitionId, span: InputSpan, identifier: Identifier) -> Self {

        Self{ this, span, identifier, poly_vars: Vec::new(), variants: Vec::new() }

    }

}

pub struct ComponentDefinition {

    pub this: ComponentDefinitionId,

    pub span: InputSpan,

impl ComponentDefinition {

    pub(crate) fn new_empty(this: ComponentDefinitionId, span: InputSpan, variant: ComponentVariant, identifier: Identifier) -> Self {

        Self{ 

            this, span, variant, identifier, 

            poly_vars: Vec::new(), 

            parameters: Vec::new(), 

            body: StatementId::new_invalid()

        }

    }

}

impl SyntaxElement for ComponentDefinition {

pub struct FunctionDefinition {

    pub this: FunctionDefinitionId,

    pub span: InputSpan,

impl FunctionDefinition {

    pub(crate) fn new_empty(this: FunctionDefinitionId, span: InputSpan, identifier: Identifier) -> Self {

        Self {

            this, span, identifier,

            return_type: ParserTypeId::new_invalid(),

            poly_vars: Vec::new(),

            parameters: Vec::new(),

            body: StatementId::new_invalid(),

        }

    }

}

impl SyntaxElement for FunctionDefinition {

        Ok(h.alloc_component(|this| ComponentDefinition {

        Ok(h.alloc_component(|this| ComponentDefinition {

        Ok(h.alloc_function(|this| FunctionDefinition {

    name: Option<(PragmaId, StringRef<'static>)>,

pub(crate) struct PassPreSymbol {

    imports: Vec<ImportId>,

    definitions: Vec<DefinitionId>,

impl PassPreSymbol {

            imports: Vec::with_capacity(32),

            definitions: Vec::with_capacity(128),

        self.imports.clear();

        self.definitions.clear();

        debug_assert!(module.root_id.is_invalid()); // not set yet,

        // Visit token ranges to detect definitions and pragmas

        let mut range_idx = module_range.first_child_idx;

        loop {

            let range_idx_usize = range_idx as usize;

            let cur_range = &module.tokens.ranges[range_idx_usize];

                self.visit_definition_range(modules, module_idx, ctx, range_idx_usize)?;

                self.visit_pragma_range(modules, module_idx, ctx, range_idx_usize)?;

            match cur_range.next_sibling_idx {

                Some(idx) => { range_idx = idx; },

                None => { break; },

        // Add the module's symbol scope and the symbols we just parsed

        let module_scope = SymbolScope::Module(root_id);

        ctx.symbols.insert_scope(None, module_scope);

        for symbol in self.symbols.drain(..) {

            if let Err((new_symbol, old_symbol)) = ctx.symbols.insert_symbol(module_scope, symbol) {

                return Err(construct_symbol_conflict_error(modules, module_idx, ctx, &new_symbol, old_symbol))

            }

        }

        // Modify the preallocated root

        root.pragmas.extend(self.pragmas.drain(..));

        root.definitions.extend(self.definitions.drain(..));

    fn visit_pragma_range(&mut self, modules: &[Module], module_idx: usize, ctx: &mut Ctx, range_idx: usize) -> Result<(), ParseError> {

        let module = &modules[module_idx];

    fn visit_definition_range(&mut self, modules: &[Module], module_idx: usize, ctx: &mut Ctx, range_idx: usize) -> Result<(), ParseError> {

        // First ident must be type of symbol

        let (kw_text, _) = consume_any_ident(&module.source, &mut iter).unwrap();

        // Retrieve identifier of definition

        let (identifier_text, identifier_span) = consume_ident(&module.source, &mut iter)?;

        let ident_text = ctx.pool.intern(identifier_text);

        let identifier = Identifier{ span: identifier_span, value: ident_text };

        // Reserve space in AST for definition and add it to the symbol table

        let symbol_definition;

        let ast_definition_id;

        match kw {

            KeywordDefinition::Struct => {

                let struct_def_id = ctx.heap.alloc_struct_definition(|this| {

                    StructDefinition::new_empty(this, definition_span, identifier)

                });

                symbol_definition = SymbolDefinition::Struct(struct_def_id);

                ast_definition_id = struct_def_id.upcast();

            },

            KeywordDefinition::Enum => {

                let enum_def_id = ctx.heap.alloc_enum_definition(|this| {

                    EnumDefinition::new_empty(this, definition_span, identifier)

                });

                symbol_definition = SymbolDefinition::Enum(enum_def_id);

                ast_definition_id = enum_def_id.upcast();

            },

            KeywordDefinition::Union => {

                let union_def_id = ctx.heap.alloc_union_definition(|this| {

                    UnionDefinition::new_empty(this, definition_span, identifier)

                });

                symbol_definition = SymbolDefinition::Union(union_def_id);

                ast_definition_id = union_def_id.upcast()

            },

            KeywordDefinition::Function => {

                let func_def_id = ctx.heap.alloc_function_definition(|this| {

                    FunctionDefinition::new_empty(this, definition_span, identifier)

                });

                symbol_definition = SymbolDefinition::Function(func_def_id);

                ast_definition_id = func_def_id.upcast();

            },

            KeywordDefinition::Primitive | KeywordDefinition::Composite => {

                let component_variant = if kw == KeywordDefinition::Primitive {

                    ComponentVariant::Primitive

                } else {

                    ComponentVariant::Composite

                };

                let comp_def_id = ctx.heap.alloc_component_definition(|this| {

                    ComponentDefinition::new_empty(this, definition_span, component_variant, identifier)

                });

                symbol_definition = SymbolDefinition::Component(comp_def_id);

                ast_definition_id = comp_def_id.upcast();

            }

        }

        let symbol = Symbol{

            defined_in_module: module.root_id,

            defined_in_scope: SymbolScope::Module(module.root_id),

            identifier_span,

            introduced_at: None,

            name: definition_ident,

            definition: symbol_definition

        };

        self.symbols.push(symbol);

        self.definitions.push(ast_definition_id);

/// Parses all the imports in the module tokens. Is applied after the

/// definitions and name of modules are resolved. Hence we should be able to

/// resolve all symbols to their appropriate module/definition.

pub(crate) struct PassImport {

    imports: Vec<ImportId>,

impl PassImport {

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

        Self{ imports: Vec::with_capacity(32) }

    }

        debug_assert!(modules.iter().all(|m| m.phase >= ModuleCompilationPhase::DefinitionsScanned));

        let mut range_idx = module_range.first_child_idx;

        loop {

            let range_idx_usize = range_idx as usize;

            let cur_range = &module.tokens.ranges[range_idx_usize];

                self.visit_import_range(modules, module_idx, ctx, range_idx_usize)?;

            match cur_range.next_sibling_idx {

                Some(idx) => { range_idx = idx; },

                None => { break; }

        let (_import_ident, import_span) =

            consume_ident(&module.source, &mut iter)?;

        let (module_name, module_name_span) = consume_domain_ident(&module.source, &mut iter)?;

        let target_root_id = ctx.symbols.get_module_by_name(module_name);

        if target_root_id.is_none() {

            return Err(ParseError::new_error_at_span(

                &module.source, module_name_span,

                format!("could not resolve module '{}'", String::from_utf8_lossy(module_name))

            ));

        }

        let module_name = ctx.pool.intern(module_name);

        let target_root_id = target_root_id.unwrap();

        // Check for subsequent characters

        let next = iter.next();

        if has_ident(&module.source, &mut iter, b"as") {

            iter.consume();

            let (alias_text, alias_span) = consume_ident(source, &mut iter)?;

            let alias = ctx.pool.intern(alias_text);

            let import_id = ctx.heap.alloc_import(|this| Import::Module(ImportModule{

                this,

                span: import_span,

                module_name: Identifier{ span: module_name_span, value: module_name },

                alias: Identifier{ span: alias_span, value: alias },

                module_id: target_root_id

            }));

            ctx.symbols.insert_symbol(SymbolScope::Module(module.root_id), Symbol{

                defined_in_module: target_root_id,

                defined_in_scope: SymbolScope::Module(target_root_id),

                definition_span

            })

        } else if Some(TokenKind::ColonColon) == next {

            iter.consume();

        } else {

            // Assume implicit alias, then check if we get the semicolon next

            let module_name_str = module_name.as_str();

            let last_ident_start = module_name_str.rfind('.').map_or(0, |v| v + 1);

            let alias_text = &module_name_str.as_bytes()[last_ident_start..];

            let alias = ctx.pool.intern(alias_text);

            let alias_span = InputSpan::from_positions(

                module_name_span.begin.with_offset(last_ident_start as u32),

                module_name_span.end

            );

        }

    let (_, mut span) = consume_ident(source, iter)?;

        let (_, new_span) = consume_ident(source, iter)?;

        span.end = new_span.end;

    // Not strictly necessary, but probably a reasonable restriction: this

    // simplifies parsing of module naming and imports.

    if span.begin.line != span.end.line {

        return Err(ParseError::new_error_str_at_span(source, span, "module names may not span multiple lines"));

    }

    // If module name consists of a single identifier, then it may not match any

    // of the reserved keywords

    let section = source.section(span.begin, span.end);

    if is_reserved_keyword(section) {

        return Err(ParseError::new_error_str_at_span(source, span, "encountered reserved keyword"));

    }

    Ok((source.section(span.begin, span.end), span))

fn has_ident(source: &InputSource, iter: &mut TokenIter, expected: &[u8]) -> bool {

    if Some(TokenKind::Ident) == iter.next() {

        let (start, end) = iter.next_range();

        return source.section(start, end) == expected;

    false

}

fn peek_ident<'a>(source: &'a InputSource, iter: &mut TokenIter) -> Option<&'a [u8]> {

    if Some(TokenKind::Ident) == iter.next() {

        let (start, end) = iter.next_range();

        return Some(source.section(start, end))

    }

    None

/// Consumes any identifier and returns it together with its span. Does not

/// check if the identifier is a reserved keyword.

fn consume_any_ident<'a>(source: &'a InputSource, iter: &mut TokenIter) -> Result<(&'a [u8], InputSpan), ParseError> {

    Ok((source.section(ident_start, ident_end), InputSpan::from_positions(ident_start, ident_end)))

}

/// Consumes an identifier that is not a reserved keyword and returns it

/// together with its span.

fn consume_ident<'a>(source: &'a InputSource, iter: &mut TokenIter) -> Result<(&'a [u8], InputSpan), ParseError> {

    let (ident, span) = consume_any_ident(source, iter)?;

    if is_reserved_keyword(ident) {

        return Err(ParseError::new_error_str_at_span(source, span, "encountered reserved keyword"));

    }

    Ok((ident, span))

}

fn is_reserved_definition_keyword(text: &[u8]) -> bool {

    return ([

        b"struct", b"enum", b"union", b"function", b"primitive"

    ] as &[[u8]]).contains(text)

}

fn is_reserved_statement_keyword(text: &[u8]) -> bool {

    return ([

        b"channel", b"import", b"as",

        b"if", b"while", b"break", b"continue", b"goto", b"return",

        b"synchronous", b"assert", b"new",

    ] as &[[u8]]).contains(text)

}

fn is_reserved_expression_keyword(text: &[u8]) -> bool {

    return ([

        b"let", b"true", b"false", b"null", // literals

        b"get", b"put", b"fires", b"create", b"length", // functions

    ] as &[[u8]]).contains(text)

}

fn is_reserved_type_keyword(text: &[u8]) -> bool {

    return ([

        b"in", b"out", b"msg",

        b"bool",

        b"u8", b"u16", b"u32", b"u64",

        b"s8", b"s16", b"s32", b"s64",

        b"auto"

    ] as &[[u8]]).contains(text)

}

fn is_reserved_keyword(text: &[u8]) -> bool {

    return

        is_reserved_definition_keyword(text) ||

        is_reserved_statement_keyword(text) ||

        is_reserved_type_keyword(text);

}

/// Constructs a human-readable message indicating why there is a conflict of

/// symbols.

// Note: passing the `module_idx` is not strictly necessary, but will prevent

// programmer mistakes during development: we get a conflict because we're

// currently parsing a particular module.

fn construct_symbol_conflict_error(modules: &[Module], module_idx: usize, ctx: &Ctx, new_symbol: &Symbol, old_symbol: &Symbol) -> ParseError {

    let module = &modules[module_idx];

    let get_symbol_span_and_msg = |symbol: &Symbol| -> (String, InputSpan) {

        match symbol.introduced_at {

            Some(import_id) => {

                // Symbol is being imported

                let import = &ctx.heap[import_id];

                match import {