// Copyright (c) 2019-2024 Alexander Medvednikov. All rights reserved.
// Use of this source code is governed by an MIT license
// that can be found in the LICENSE file.
//
// Type layout information (32 bits)
// flag (8 bits) | nr_muls (8 bits) | idx (16 bits)
// pack: (int(flag)<<24) | (nr_muls<<16) | u16(idx)
// unpack:
// flag: (int(type)>>24) & 0xff
// nr_muls: (int(type)>>16) & 0xff
// idx:  u16(type) & 0xffff
module ast

import strings
import v.pref
import v.token

pub type Type = u32

@[inline]
pub fn idx_to_type(idx int) Type {
    return Type(u32(idx))
}

pub struct UnknownTypeInfo {}

pub type TypeInfo = UnknownTypeInfo
    | Aggregate
    | Alias
    | Array
    | ArrayFixed
    | Chan
    | Enum
    | FnType
    | GenericInst
    | Interface
    | Map
    | MultiReturn
    | Struct
    | SumType
    | Thread

pub enum Language {
    v
    c
    js
    wasm
    amd64 // aka x86_64
    i386
    arm64 // 64-bit arm
    arm32 // 32-bit arm
    rv64  // 64-bit risc-v
    rv32  // 32-bit risc-v
    s390x
    ppc64le
    loongarch64
    sparc64
    ppc64
    wasm32
}

// pref_arch_to_table_language returns target language based on pref_arch
pub fn pref_arch_to_table_language(pref_arch pref.Arch) Language {
    return match pref_arch {
        .amd64 {
            .amd64
        }
        .arm64 {
            .arm64
        }
        .arm32 {
            .arm32
        }
        .rv64 {
            .rv64
        }
        .rv32 {
            .rv32
        }
        .i386 {
            .i386
        }
        .s390x {
            .s390x
        }
        .ppc64le {
            .ppc64le
        }
        .loongarch64 {
            .loongarch64
        }
        .sparc64 {
            .sparc64
        }
        .ppc64 {
            .ppc64
        }
        .ppc {
            .v
        }
        .js_node, .js_browser, .js_freestanding {
            .js
        }
        .wasm32 {
            .wasm32
        }
        ._auto, ._max {
            .v
        }
    }
}

// Represents a type that only needs an identifier, e.g. int, array_int.
// A pointer type `&T` would have a TypeSymbol `T`.
// Note: For a Type, use:
// * Table.type_to_str(typ) not TypeSymbol.name.
// * Table.type_kind(typ) not TypeSymbol.kind.
// Each TypeSymbol is entered into `Table.type_symbols`.
// See also: Table.sym.
@[minify]
pub struct TypeSymbol {
pub mut:
    parent_idx    int
    info          TypeInfo
    kind          Kind
    name          string // the internal & source name of the type, i.e. `[5]int`.
    cname         string // the name with no dots for use in the generated C code
    rname         string // the raw name
    ngname        string // the name without generic parameters
    methods       []Fn
    generic_types []Type
    mod           string
    is_pub        bool
    is_builtin    bool
    language      Language
    idx           int
    size          int = -1
    align         int = -1
}

pub fn (sym TypeSymbol) aggregate_variant_type(idx int) Type {
    info := sym.info
    return match info {
        Aggregate {
            if idx >= 0 && idx < info.types.len {
                info.types[idx]
            } else {
                Type(0)
            }
        }
        else {
            Type(0)
        }
    }
}

// max of 8
pub enum TypeFlag as u32 {
    option             = 1 << 24
    result             = 1 << 25
    variadic           = 1 << 26
    generic            = 1 << 27
    shared_f           = 1 << 28
    atomic_f           = 1 << 29
    option_mut_param_t = 1 << 30
}

/*
To save precious TypeFlag bits the 4 possible ShareTypes are coded in the two
bits `shared` and `atomic_or_rw` (see sharetype_from_flags() below).
*/
pub enum ShareType {
    mut_t
    shared_t
    atomic_t
}

// str converts t to it's string form of ShareType i.e. mut, shared, atomic
pub fn (t ShareType) str() string {
    match t {
        .mut_t { return 'mut' }
        .shared_t { return 'shared' }
        .atomic_t { return 'atomic' }
    }
}

pub struct MultiReturn {
pub mut:
    types []Type
}

pub struct FnType {
pub mut:
    is_anon  bool
    has_decl bool
    func     Fn
}

@[minify]
pub struct Struct {
pub:
    attrs       []Attr
    scoped_name string
pub mut:
    embeds         []Type
    fields         []StructField
    is_typedef     bool // C. [typedef]
    is_union       bool
    is_heap        bool
    is_minify      bool
    is_anon        bool
    is_generic     bool
    is_shared      bool
    is_markused    bool
    has_option     bool // contains any option field
    generic_types  []Type
    concrete_types []Type
    parent_type    Type
    name_pos       token.Pos
}

// instantiation of a generic struct
pub struct GenericInst {
pub mut:
    parent_idx     int    // idx of the base generic struct
    concrete_types []Type // concrete types, e.g. [int, string]
}

@[minify]
pub struct Interface {
pub mut:
    types     []Type // all types that implement this interface immutably
    mut_types []Type // all types that require a mutable interface binding
    fields    []StructField
    methods   []Fn
    embeds    []Type
    // `I1 is I2` conversions
    conversions shared map[int][]Type
    // generic interface support
    is_generic     bool
    is_markused    bool
    generic_types  []Type
    concrete_types []Type
    parent_type    Type
    name_pos       token.Pos
}

pub fn (info &Interface) has_implementor(typ Type, include_mut_types bool) bool {
    if info.types.any(it.idx() == typ.idx()) {
        return true
    }
    return include_mut_types && info.mut_types.any(it.idx() == typ.idx())
}

pub fn (info &Interface) implementor_types(include_mut_types bool) []Type {
    mut implementors := info.types.clone()
    if !include_mut_types {
        return implementors
    }
    for typ in info.mut_types {
        if !implementors.any(it.idx() == typ.idx()) {
            implementors << typ
        }
    }
    return implementors
}

pub struct Enum {
pub:
    vals             []string
    is_flag          bool
    is_multi_allowed bool
    is_typedef       bool
    uses_exprs       bool
    typ              Type
    attrs            map[string][]Attr
    name_pos         token.Pos
}

@[minify]
pub struct Alias {
pub mut:
    parent_type Type
pub:
    language  Language
    is_import bool
    name_pos  token.Pos
}

pub struct Aggregate {
mut:
    fields []StructField // used for faster lookup inside the module
pub:
    sum_type Type
    types    []Type
}

pub struct Array {
pub:
    nr_dims int
pub mut:
    elem_type Type
}

@[minify]
pub struct ArrayFixed {
pub:
    size      int
    size_expr Expr // used by fmt for e.g. ´[my_const]u8´
pub mut:
    elem_type Type
    is_fn_ret bool
}

pub struct Chan {
pub mut:
    elem_type Type
    is_mut    bool
}

pub struct Thread {
pub mut:
    return_type Type
}

pub struct Map {
pub mut:
    key_type   Type
    value_type Type
    name_pos   token.Pos
}

@[minify]
pub struct SumType {
pub mut:
    fields       []StructField
    found_fields bool
    is_anon      bool
    // generic sumtype support
    is_generic     bool
    variants       []Type
    generic_types  []Type
    concrete_types []Type
    parent_type    Type
    name_pos       token.Pos
}

pub fn (ti TypeInfo) get_name_pos() ?token.Pos {
    return match ti {
        Struct, Alias, SumType, Enum, Interface {
            ti.name_pos
        }
        else {
            none
        }
    }
}

// <atomic.h> defines special typenames
pub fn (t Type) atomic_typename() string {
    idx := t.idx()
    match idx {
        u32_type_idx { return 'atomic_uint' }
        int_type_idx { return '_Atomic int' }
        i32_type_idx { return '_Atomic int' }
        u64_type_idx { return 'atomic_ullong' }
        i64_type_idx { return 'atomic_llong' }
        else { return 'unknown_atomic' }
    }
}

pub fn sharetype_from_flags(is_shared bool, is_atomic bool) ShareType {
    return unsafe { ShareType(int(u32(is_atomic) << 1) | int(is_shared)) }
}

pub fn (t Type) share() ShareType {
    return sharetype_from_flags(t.has_flag(.shared_f), t.has_flag(.atomic_f))
}

// return TypeSymbol idx for `t`
@[inline]
pub fn (t Type) idx() int {
    return u16(t) & 0xffff
}

// is_void return true if `t` is of type `void`
@[inline]
pub fn (t Type) is_void() bool {
    return t == void_type
}

// is_full return true if `t` is not of type `void`
@[inline]
pub fn (t Type) is_full() bool {
    return t != 0 && t != void_type
}

// return nr_muls for `t`
@[inline]
pub fn (t Type) nr_muls() int {
    return (t >> 16) & 0xff
}

// return true if `t` is a pointer (nr_muls>0)
@[inline]
pub fn (t Type) is_ptr() bool {
    // any normal pointer, i.e. &Type, &&Type etc;
    // Note: voidptr, charptr and byteptr are NOT included!
    return (t >> 16) & 0xff != 0
}

// is_pointer returns true if `typ` is any of the builtin pointer types (voidptr, byteptr, charptr)
@[inline]
pub fn (typ Type) is_pointer() bool {
    // builtin pointer types (voidptr, byteptr, charptr)
    return typ.idx() in pointer_type_idxs
}

// is_voidptr returns true if `typ` is a voidptr
@[inline]
pub fn (typ Type) is_voidptr() bool {
    return typ.idx() == voidptr_type_idx
}

// is_any_kind_of_pointer returns true if t is any type of pointer
@[inline]
pub fn (t Type) is_any_kind_of_pointer() bool {
    return (t >> 16) & 0xff != 0 || (u16(t) & 0xffff) in pointer_type_idxs
}

// set nr_muls on `t` and return it
@[inline]
pub fn (t Type) set_nr_muls(nr_muls int) Type {
    if nr_muls < 0 || nr_muls > 255 {
        panic('set_nr_muls: nr_muls must be between 0 & 255')
    }
    return t & 0xff00ffff | u32(nr_muls) << 16
}

// increments nr_muls on `t` and return it
@[inline]
pub fn (t Type) ref() Type {
    nr_muls := (t >> 16) & 0xff
    if nr_muls == 255 {
        panic('ref: nr_muls is already at max of 255')
    }
    return t & 0xff00ffff | (nr_muls + 1) << 16
}

// decrement nr_muls on `t` and return it
@[inline]
pub fn (t Type) deref() Type {
    nr_muls := (t >> 16) & 0xff
    if nr_muls == 0 {
        panic('deref: type `${t}` is not a pointer')
    }
    return t & 0xff00ffff | (nr_muls - 1) << 16
}

// flags returns type's flags
@[inline]
pub fn (t Type) flags() int {
    return t >> 16
}

// has_flag returns whether the given named `flag` is set
@[inline]
pub fn (t Type) has_flag(flag TypeFlag) bool {
    return (t & u32(flag)) != 0
}

// set_flag returns a new type, that is like the input `t`, but with the named `flag` set
@[inline]
pub fn (t Type) set_flag(flag TypeFlag) Type {
    return t | u32(flag)
}

// clear_flag returns a new type, that is like `t`, but with the named `flag` cleared
@[inline]
pub fn (t Type) clear_flag(flag TypeFlag) Type {
    return t & ~(u32(flag))
}

// clear_flags returns a new type, based on `t`, but with cleared named `flags`
@[inline]
pub fn (t Type) clear_flags(flags ...TypeFlag) Type {
    if flags.len == 0 {
        return t & 0xffffff
    } else {
        mut typ := u32(t)
        for flag in flags {
            typ = typ & ~(u32(flag))
        }
        return typ
    }
}

// clear_ref clear refs of type
@[inline]
pub fn (t Type) clear_ref() Type {
    return t & ~0x00FF_0000
}

// clear option and result flags
@[inline]
pub fn (t Type) clear_option_and_result() Type {
    return t & ~0x0300_0000
}

@[inline]
pub fn (t Type) has_option_or_result() bool {
    return t & 0x0300_0000 != 0
}

@[inline]
pub fn (ts &TypeSymbol) scoped_name() string {
    return if ts.info is Struct && ts.info.scoped_name != '' { ts.info.scoped_name } else { ts.name }
}

@[inline]
pub fn (ts &TypeSymbol) scoped_cname() string {
    return if ts.info is Struct && ts.info.scoped_name != '' {
        if ts.language == .v && ts.info.scoped_name.contains('[') {
            ts.info.scoped_name.replace('.', '__').replace_each([
                '[',
                '_T_',
                ']',
                '',
                ', ',
                '_T_',
                ',',
                '_T_',
                ' ',
                '',
                '&',
                '__ptr__',
                '(',
                '_',
                ')',
                '_',
            ])
        } else {
            ts.info.scoped_name.replace('.', '__')
        }
    } else if ts.language == .v && ts.kind in [.placeholder, .generic_inst] && ts.name.contains('[') {
        ts.name.replace('.', '__').replace_each([
            '[',
            '_T_',
            ']',
            '',
            ', ',
            '_T_',
            ',',
            '_T_',
            ' ',
            '',
            '&',
            '__ptr__',
            '(',
            '_',
            ')',
            '_',
        ])
    } else {
        ts.cname
    }
}

// debug returns a verbose representation of the information in ts, useful for tracing/debugging
pub fn (ts &TypeSymbol) debug() []string {
    mut res := []string{}
    ts.dbg_common(mut res)
    res << 'info: ${ts.info}'
    res << 'methods (${ts.methods.len}): ' + ts.methods.map(it.str()).join(', ')
    return res
}

// same as .debug(), but without the verbose .info and .methods fields
pub fn (ts &TypeSymbol) dbg() []string {
    mut res := []string{}
    ts.dbg_common(mut res)
    return res
}

fn (ts &TypeSymbol) dbg_common(mut res []string) {
    res << 'idx: 0x${ts.idx.hex()}'
    res << 'parent_idx: 0x${ts.parent_idx.hex()}'
    res << 'mod: ${ts.mod}'
    res << 'name: ${ts.name}'
    res << 'cname: ${ts.cname}'
    res << 'kind: ${ts.kind}'
    res << 'is_pub: ${ts.is_pub}'
    res << 'language: ${ts.language}'
}

pub fn (ts &TypeSymbol) nr_dims() int {
    match ts.info {
        Alias {
            parent_sym := global_table.sym(ts.info.parent_type)
            if parent_sym.info is Array {
                return parent_sym.info.nr_dims
            }
            return 0
        }
        Array {
            elem_sym := global_table.sym(ts.info.elem_type)
            if elem_sym.info is Alias {
                return ts.info.nr_dims + elem_sym.nr_dims()
            }
            return ts.info.nr_dims
        }
        else {
            return 0
        }
    }
}

// str returns a string representation of the type.
pub fn (t Type) str() string {
    return 'ast.Type(0x${t.hex()} = ${u32(t)})'
}

pub fn (t &Table) type_str(typ Type) string {
    idx := typ.idx()
    if idx == 0 || idx >= t.type_symbols.len {
        return 'unknown'
    }
    return t.sym(typ).name
}

// debug returns a verbose representation of the information in the type `t`, useful for tracing/debugging
pub fn (t Type) debug() []string {
    mut res := []string{}
    res << 'idx: 0x${t.idx().hex():-8}'
    res << 'type: 0x${t.hex():-8}'
    res << 'nr_muls: ${t.nr_muls()}'
    if t.has_flag(.option) {
        res << 'option'
    }
    if t.has_flag(.result) {
        res << 'result'
    }
    if t.has_flag(.variadic) {
        res << 'variadic'
    }
    if t.has_flag(.generic) {
        res << 'generic'
    }
    if t.has_flag(.shared_f) {
        res << 'shared_f'
    }
    if t.has_flag(.atomic_f) {
        res << 'atomic_f'
    }
    return res
}

// copy flags & nr_muls from `t_from` to `t` and return `t`
@[inline]
pub fn (t Type) derive(t_from Type) Type {
    return (0xffff0000 & t_from) | u16(t)
}

// copy flags from `t_from` to `t` and return `t`
@[inline]
pub fn (t Type) derive_add_muls(t_from Type) Type {
    return Type((0xff000000 & t_from) | u16(t)).set_nr_muls(t.nr_muls() + t_from.nr_muls())
}

// return new type from its `idx`
@[inline]
pub fn (t Type) idx_type() Type {
    return idx_to_type(t.idx())
}

// return new type with TypeSymbol idx set to `idx`
@[inline]
pub fn new_type(idx int) Type {
    if idx < 1 || idx > 65535 {
        panic('new_type: idx must be between 1 & 65535')
    }
    return idx
}

// return new type with TypeSymbol idx set to `idx` & nr_muls set to `nr_muls`
@[inline]
pub fn new_type_ptr(idx int, nr_muls int) Type {
    if idx < 1 || idx > 65535 {
        panic('new_type_ptr: idx must be between 1 & 65535')
    }
    if nr_muls < 0 || nr_muls > 255 {
        panic('new_type_ptr: nr_muls must be between 0 & 255')
    }
    return (u32(nr_muls) << 16) | u16(idx)
}

// is_float returns `true` if `typ` is float
@[inline]
pub fn (typ Type) is_float() bool {
    return !typ.is_ptr() && typ.idx() in float_type_idxs
}

// is_int returns `true` if `typ` is int
@[inline]
pub fn (typ Type) is_int() bool {
    return !typ.is_ptr() && typ.idx() in integer_type_idxs
}

// is_int_valptr returns `true` if `typ` is a pointer to a int
@[inline]
pub fn (typ Type) is_int_valptr() bool {
    return typ.is_ptr() && typ.idx() in integer_type_idxs
}

// is_float_valptr return `true` if `typ` is a pointer to float
@[inline]
pub fn (typ Type) is_float_valptr() bool {
    return typ.is_ptr() && typ.idx() in float_type_idxs
}

// is_pure_int return `true` if `typ` is a pure int
@[inline]
pub fn (typ Type) is_pure_int() bool {
    return int(typ) in integer_type_idxs
}

// is_pure_float return `true` if `typ` is a pure float
@[inline]
pub fn (typ Type) is_pure_float() bool {
    return int(typ) in float_type_idxs
}

// is_signed return `true` if `typ` is signed
@[inline]
pub fn (typ Type) is_signed() bool {
    return typ.idx() in signed_integer_type_idxs
}

// is_unsigned return `true` if `typ` is unsigned
@[inline]
pub fn (typ Type) is_unsigned() bool {
    return typ.idx() in unsigned_integer_type_idxs
}

pub fn (typ Type) flip_signedness() Type {
    return match typ {
        i8_type {
            u8_type
        }
        i16_type {
            u16_type
        }
        i32_type {
            u32_type
        }
        i64_type {
            u64_type
        }
        int_type {
            $if new_int ? && x64 {
                u64_type
            } $else {
                u32_type
            }
        }
        isize_type {
            usize_type
        }
        u8_type {
            i8_type
        }
        u16_type {
            i16_type
        }
        u32_type {
            i32_type
        }
        u64_type {
            i64_type
        }
        usize_type {
            isize_type
        }
        else {
            void_type
        }
    }
}

// is_int_literal returns `true` if `typ` is a int literal
@[inline]
pub fn (typ Type) is_int_literal() bool {
    return int(typ) == int_literal_type_idx
}

// is_number returns `true` if `typ` is a number
@[inline]
pub fn (typ Type) is_number() bool {
    return typ.clear_flags() in number_type_idxs
}

// is_string returns `true` if `typ` is a string type
@[inline]
pub fn (typ Type) is_string() bool {
    return typ.idx() == string_type_idx
}

// is_bool returns `true` if `typ` is of bool type
@[inline]
pub fn (typ Type) is_bool() bool {
    return typ.idx() == bool_type_idx
}

pub const invalid_type_idx = -1
pub const no_type_idx = 0
pub const void_type_idx = 1
pub const voidptr_type_idx = 2
pub const byteptr_type_idx = 3
pub const charptr_type_idx = 4
pub const i8_type_idx = 5
pub const i16_type_idx = 6
pub const i32_type_idx = 7
pub const int_type_idx = 8
pub const i64_type_idx = 9
pub const isize_type_idx = 10
pub const u8_type_idx = 11
pub const u16_type_idx = 12
pub const u32_type_idx = 13
pub const u64_type_idx = 14
pub const usize_type_idx = 15
pub const f32_type_idx = 16
pub const f64_type_idx = 17
pub const char_type_idx = 18
pub const bool_type_idx = 19
pub const none_type_idx = 20
pub const string_type_idx = 21
pub const rune_type_idx = 22
pub const array_type_idx = 23
pub const map_type_idx = 24
pub const chan_type_idx = 25
pub const any_type_idx = 26
pub const float_literal_type_idx = 27
pub const int_literal_type_idx = 28
pub const thread_type_idx = 29
pub const error_type_idx = 30
pub const nil_type_idx = 31

// Note: builtin_type_names must be in the same order as the idx consts above
pub const builtin_type_names = ['void', 'voidptr', 'byteptr', 'charptr', 'i8', 'i16', 'i32', 'int',
    'i64', 'isize', 'u8', 'u16', 'u32', 'u64', 'usize', 'f32', 'f64', 'char', 'bool', 'none',
    'string', 'rune', 'array', 'map', 'chan', 'any', 'float_literal', 'int_literal', 'thread',
    'Error', 'nil']

pub const builtin_type_names_matcher = token.new_keywords_matcher_from_array_trie(builtin_type_names)

pub const integer_type_idxs = [i8_type_idx, i16_type_idx, i32_type_idx, int_type_idx, i64_type_idx,
    u8_type_idx, u16_type_idx, u32_type_idx, u64_type_idx, isize_type_idx, usize_type_idx,
    int_literal_type_idx, rune_type_idx]
pub const signed_integer_type_idxs = [char_type_idx, i8_type_idx, i16_type_idx, i32_type_idx,
    int_type_idx, i64_type_idx, isize_type_idx]
pub const unsigned_integer_type_idxs = [u8_type_idx, u16_type_idx, u32_type_idx, u64_type_idx,
    usize_type_idx]
// C will promote any type smaller than int to int in an expression
pub const int_promoted_type_idxs = [char_type_idx, i8_type_idx, i16_type_idx, u8_type_idx,
    u16_type_idx]
pub const float_type_idxs = [f32_type_idx, f64_type_idx, float_literal_type_idx]
pub const number_type_idxs = [i8_type_idx, i16_type_idx, int_type_idx, i32_type_idx, i64_type_idx,
    u8_type_idx, char_type_idx, u16_type_idx, u32_type_idx, u64_type_idx, isize_type_idx,
    usize_type_idx, f32_type_idx, f64_type_idx, int_literal_type_idx, float_literal_type_idx,
    rune_type_idx]
pub const pointer_type_idxs = [voidptr_type_idx, byteptr_type_idx, charptr_type_idx, nil_type_idx]

pub const invalid_type = idx_to_type(invalid_type_idx) // -1 is a purposefully invalid type, not by default, but to signify checker errors
pub const no_type = idx_to_type(no_type_idx) // 0 is an invalid type, but it is useful for initialising default ast.Type values, in fields or before loops
pub const void_type = new_type(void_type_idx)
pub const ovoid_type = new_type(void_type_idx).set_flag(.option) // the return type of `fn ()?`
pub const rvoid_type = new_type(void_type_idx).set_flag(.result) // the return type of `fn () !`
pub const voidptr_type = new_type(voidptr_type_idx)
pub const byteptr_type = new_type(byteptr_type_idx)
pub const charptr_type = new_type(charptr_type_idx)
pub const i8_type = new_type(i8_type_idx)
pub const i16_type = new_type(i16_type_idx)
pub const i32_type = new_type(i32_type_idx)
pub const int_type = new_type(int_type_idx)
pub const i64_type = new_type(i64_type_idx)
pub const isize_type = new_type(isize_type_idx)
pub const u8_type = new_type(u8_type_idx)
pub const u16_type = new_type(u16_type_idx)
pub const u32_type = new_type(u32_type_idx)
pub const u64_type = new_type(u64_type_idx)
pub const usize_type = new_type(usize_type_idx)
pub const f32_type = new_type(f32_type_idx)
pub const f64_type = new_type(f64_type_idx)
pub const char_type = new_type(char_type_idx)
pub const bool_type = new_type(bool_type_idx)
pub const none_type = new_type(none_type_idx)
pub const string_type = new_type(string_type_idx)
pub const rune_type = new_type(rune_type_idx)
pub const array_type = new_type(array_type_idx)
pub const map_type = new_type(map_type_idx)
pub const chan_type = new_type(chan_type_idx)
pub const any_type = new_type(any_type_idx)
pub const float_literal_type = new_type(float_literal_type_idx)
pub const int_literal_type = new_type(int_literal_type_idx)
pub const thread_type = new_type(thread_type_idx)
pub const error_type = new_type(error_type_idx)
pub const charptr_types = new_charptr_types()
pub const byteptr_types = new_byteptr_types()
pub const voidptr_types = new_voidptr_types()
pub const cptr_types = merge_types(voidptr_types, byteptr_types, charptr_types)
pub const nil_type = new_type(nil_type_idx)

pub const builtin_array_generic_methods = ['all', 'any', 'count', 'filter', 'map', 'sort', 'sorted']
pub const builtin_array_generic_methods_matcher = token.new_keywords_matcher_from_array_trie(builtin_array_generic_methods)

pub const builtin_array_generic_methods_no_sort = ['all', 'any', 'count', 'filter', 'map']
pub const builtin_array_generic_methods_no_sort_matcher = token.new_keywords_matcher_from_array_trie(builtin_array_generic_methods_no_sort)

fn new_charptr_types() []Type {
    return [charptr_type, new_type(char_type_idx).set_nr_muls(1)]
}

fn new_byteptr_types() []Type {
    return [byteptr_type, new_type(u8_type_idx).set_nr_muls(1)]
}

fn new_voidptr_types() []Type {
    return [voidptr_type, new_type(voidptr_type_idx).set_nr_muls(1)]
}

pub fn merge_types(params ...[]Type) []Type {
    mut res := []Type{cap: params.len}
    for types in params {
        for t in types {
            if t !in res {
                res << t
            }
        }
    }
    return res
}

pub fn mktyp(typ Type) Type {
    return match typ {
        float_literal_type { f64_type }
        int_literal_type { int_type }
        else { typ }
    }
}

// type_kind returns the kind of the given type symbol.
pub fn (t &Table) type_kind(typ Type) Kind {
    if typ.nr_muls() > 0 || typ.has_option_or_result() {
        return Kind.placeholder
    }
    return t.sym(typ).kind
}

pub fn (t &Table) type_is_for_pointer_arithmetic(typ Type) bool {
    if t.sym(typ).kind == .struct {
        return false
    } else {
        return typ.is_any_kind_of_pointer() || typ.is_int_valptr()
    }
}

pub enum Kind {
    placeholder
    void
    voidptr
    byteptr
    charptr
    i8
    i16
    i32
    int
    i64
    isize
    u8
    u16
    u32
    u64
    usize
    f32
    f64
    char
    rune
    bool
    none
    string
    array
    array_fixed
    map
    chan
    any
    struct
    generic_inst
    multi_return
    sum_type
    alias
    enum
    function
    interface
    float_literal
    int_literal
    aggregate
    thread
}

// str returns the internal & source name of the type
pub fn (t &TypeSymbol) str() string {
    return t.name.clone()
}

// TODO why is this needed? str() returns incorrect amount of &
pub fn (t &TypeSymbol) str_with_correct_nr_muls(n int) string {
    prefix := strings.repeat(`&`, n)
    return prefix + t.name
}

@[noreturn]
fn (t &TypeSymbol) no_info_panic(fname string) {
    panic('${fname}: no info for type: ${t.name}')
}

@[inline]
pub fn (t &TypeSymbol) enum_info() Enum {
    if t.info is Enum {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is Enum {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) mr_info() MultiReturn {
    if t.info is MultiReturn {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is MultiReturn {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) array_info() Array {
    if t.info is Array {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is Array {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) array_fixed_info() ArrayFixed {
    if t.info is ArrayFixed {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is ArrayFixed {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) chan_info() Chan {
    if t.info is Chan {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is Chan {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) thread_info() Thread {
    if t.info is Thread {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is Thread {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) map_info() Map {
    if t.info is Map {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is Map {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) struct_info() Struct {
    if t.info is Struct {
        return t.info
    }
    if t.info is Alias {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is Struct {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

@[inline]
pub fn (t &TypeSymbol) sumtype_info() SumType {
    if t.info is SumType {
        return t.info
    }
    if t.info is SumType {
        fsym := global_table.final_sym(t.info.parent_type)
        if fsym.info is SumType {
            return fsym.info
        }
    }
    t.no_info_panic(@METHOD)
}

pub fn (t &TypeSymbol) is_heap() bool {
    if t.info is Struct {
        return t.info.is_heap
    } else {
        return false
    }
}

pub fn (t &ArrayFixed) is_compatible(t2 ArrayFixed) bool {
    return t.size == t2.size && t.elem_type == t2.elem_type
}

pub fn (t &TypeSymbol) is_empty_struct_array() bool {
    if t.info is ArrayFixed {
        elem_sym := global_table.final_sym(t.info.elem_type)
        if elem_sym.info is Struct {
            return elem_sym.info.is_empty_struct()
        }
    }
    return false
}

@[inline]
pub fn (t &Struct) is_empty_struct() bool {
    return t.fields.len == 0 && t.embeds.len == 0
}

@[inline]
pub fn (t &Struct) is_unresolved_generic() bool {
    return t.generic_types.len > 0 && t.concrete_types.len == 0
}

pub fn (t &TypeSymbol) is_primitive_fixed_array() bool {
    if t.info is ArrayFixed {
        return global_table.final_sym(t.info.elem_type).is_primitive()
    } else if t.info is Alias {
        return global_table.final_sym(t.info.parent_type).is_primitive_fixed_array()
    } else {
        return false
    }
}

pub fn (t &TypeSymbol) is_array_fixed() bool {
    if t.info is ArrayFixed {
        return true
    } else if t.info is Alias {
        return global_table.final_sym(t.info.parent_type).is_array_fixed()
    } else {
        return false
    }
}

pub fn (t &TypeSymbol) is_c_struct() bool {
    if t.info is Struct {
        // `C___VAnonStruct` need special handle, it need to create a new struct
        return t.language == .c && !t.info.is_anon
    } else if t.info is Alias {
        return global_table.final_sym(t.info.parent_type).is_c_struct()
    }
    return false
}

pub fn (t &TypeSymbol) is_array_fixed_ret() bool {
    if t.info is ArrayFixed {
        return t.info.is_fn_ret
    } else if t.info is Alias {
        return global_table.final_sym(t.info.parent_type).is_array_fixed_ret()
    } else {
        return false
    }
}

pub fn (mut t Table) register_builtin_type_symbols() {
    // reserve index 0 so nothing can go there
    // save index check, 0 will mean not found
    // THE ORDER MUST BE THE SAME AS xxx_type_idx CONSTS EARLIER IN THIS FILE
    t.register_sym(kind: .placeholder, name: 'reserved_0')
    t.register_sym(kind: .void, name: 'void', cname: 'void', mod: 'builtin', is_pub: true) // 1
    t.register_sym(kind: .voidptr, name: 'voidptr', cname: 'voidptr', mod: 'builtin', is_pub: true) // 2
    t.register_sym(kind: .byteptr, name: 'byteptr', cname: 'byteptr', mod: 'builtin', is_pub: true) // 3
    t.register_sym(kind: .charptr, name: 'charptr', cname: 'charptr', mod: 'builtin', is_pub: true) // 4
    t.register_sym(kind: .i8, name: 'i8', cname: 'i8', mod: 'builtin', is_pub: true) // 5
    t.register_sym(kind: .i16, name: 'i16', cname: 'i16', mod: 'builtin', is_pub: true) // 6
    t.register_sym(kind: .i32, name: 'i32', cname: 'i32', mod: 'builtin', is_pub: true) // 7
    t.register_sym(kind: .int, name: 'int', cname: int_type_name, mod: 'builtin', is_pub: true) // 8
    t.register_sym(kind: .i64, name: 'i64', cname: 'i64', mod: 'builtin', is_pub: true) // 9
    t.register_sym(kind: .isize, name: 'isize', cname: 'isize', mod: 'builtin', is_pub: true) // 10
    t.register_sym(kind: .u8, name: 'u8', cname: 'u8', mod: 'builtin', is_pub: true) // 11
    t.register_sym(kind: .u16, name: 'u16', cname: 'u16', mod: 'builtin', is_pub: true) // 12
    t.register_sym(kind: .u32, name: 'u32', cname: 'u32', mod: 'builtin', is_pub: true) // 13
    t.register_sym(kind: .u64, name: 'u64', cname: 'u64', mod: 'builtin', is_pub: true) // 14
    t.register_sym(kind: .usize, name: 'usize', cname: 'usize', mod: 'builtin', is_pub: true) // 15
    t.register_sym(kind: .f32, name: 'f32', cname: 'f32', mod: 'builtin', is_pub: true) // 16
    t.register_sym(kind: .f64, name: 'f64', cname: 'f64', mod: 'builtin', is_pub: true) // 17
    t.register_sym(kind: .char, name: 'char', cname: 'char', mod: 'builtin', is_pub: true) // 18
    t.register_sym(kind: .bool, name: 'bool', cname: 'bool', mod: 'builtin', is_pub: true) // 19
    t.register_sym(kind: .none, name: 'none', cname: 'none', mod: 'builtin', is_pub: true) // 20
    t.register_sym(
        kind:       .string
        name:       'string'
        cname:      'string'
        mod:        'builtin'
        is_builtin: true
        is_pub:     true
    ) // 21
    t.register_sym(kind: .rune, name: 'rune', cname: 'rune', mod: 'builtin', is_pub: true) // 22
    t.register_sym(
        kind:       .array
        name:       'array'
        cname:      'array'
        mod:        'builtin'
        is_builtin: true
        is_pub:     true
    ) // 23
    t.register_sym(
        kind:       .map
        name:       'map'
        cname:      'map'
        mod:        'builtin'
        is_builtin: true
        is_pub:     true
    ) // 24
    t.register_sym(kind: .chan, name: 'chan', cname: 'chan', mod: 'builtin', is_pub: true) // 25
    t.register_sym(kind: .any, name: 'any', cname: 'any', mod: 'builtin', is_pub: true) // 26
    t.register_sym(
        kind:   .float_literal
        name:   'float literal'
        cname:  'float_literal'
        mod:    'builtin'
        is_pub: true
    ) // 27
    t.register_sym(
        kind:   .int_literal
        name:   'int literal'
        cname:  'int_literal'
        mod:    'builtin'
        is_pub: true
    ) // 28
    t.register_sym(
        kind:   .thread
        name:   'thread'
        cname:  '__v_thread'
        mod:    'builtin'
        info:   Thread{
            return_type: void_type
        }
        is_pub: true
    ) // 29
    t.register_sym(
        kind:       .interface
        name:       'IError'
        cname:      'IError'
        mod:        'builtin'
        is_builtin: true
        is_pub:     true
    ) // 30
    t.register_sym(kind: .voidptr, name: 'nil', cname: 'voidptr', mod: 'builtin', is_pub: true) // 31
}

@[inline]
pub fn (t &TypeSymbol) is_pointer() bool {
    return t.kind in [.byteptr, .charptr, .voidptr]
}

@[inline]
pub fn (t &TypeSymbol) is_int() bool {
    res := t.kind in [.i8, .i16, .i32, .int, .i64, .isize, .u8, .u16, .u32, .u64, .usize,
        .int_literal, .rune]
    if !res && t.kind == .alias {
        return (t.info as Alias).parent_type.is_int()
    }
    return res
}

@[inline]
pub fn (t &TypeSymbol) is_float() bool {
    return t.kind in [.f32, .f64, .float_literal]
}

@[inline]
pub fn (t &TypeSymbol) is_string() bool {
    return t.kind == .string
}

@[inline]
pub fn (t &TypeSymbol) is_number() bool {
    return t.is_int() || t.is_float()
}

@[inline]
pub fn (t &TypeSymbol) is_bool() bool {
    return t.kind == .bool
}

@[inline]
pub fn (t &TypeSymbol) is_primitive() bool {
    return t.is_number() || t.is_pointer() || t.is_string() || t.is_bool()
}

@[inline]
pub fn (t &TypeSymbol) is_builtin() bool {
    return t.mod == 'builtin'
}

// type_size returns the size and alignment (in bytes) of `typ`, similarly to  C's `sizeof()` and `alignof()`.
pub fn (t &Table) type_size(typ Type) (int, int) {
    if typ.has_option_or_result() {
        return t.type_size(error_type_idx)
    }
    if typ.nr_muls() > 0 {
        return t.pointer_size, t.pointer_size
    }
    mut sym := t.sym(typ)
    if sym.size != -1 {
        return sym.size, sym.align
    }
    mut size := 0
    mut align := 0
    match sym.kind {
        .placeholder, .void, .none, .generic_inst {}
        .voidptr, .byteptr, .charptr, .function, .usize, .isize, .any, .thread, .chan {
            size = t.pointer_size
            align = t.pointer_size
        }
        .i8, .u8, .char, .bool {
            size = 1
            align = 1
        }
        .i16, .u16 {
            size = 2
            align = 2
        }
        .i32, .u32, .rune, .f32, .enum {
            size = 4
            align = 4
        }
        .int {
            $if new_int ? && x64 {
                size = 8
                align = 8
            } $else {
                size = 4
                align = 4
            }
        }
        .i64, .u64, .int_literal, .f64, .float_literal {
            size = 8
            align = 8
        }
        .alias {
            size, align = t.type_size((sym.info as Alias).parent_type)
        }
        .struct {
            info := sym.info as Struct
            is_packed := info.attrs.contains('packed')
            if info.is_union {
                mut max_alignment := if is_packed { 1 } else { 0 }
                mut max_size := 0
                for field in info.fields {
                    field_size, alignment := t.type_size(field.typ)
                    if field_size > max_size {
                        max_size = field_size
                    }
                    if !is_packed && alignment > max_alignment {
                        max_alignment = alignment
                    }
                }
                if is_packed {
                    size = max_size
                    align = 1
                } else {
                    size = round_up(max_size, max_alignment)
                    align = max_alignment
                }
            } else {
                mut max_alignment := if is_packed { 1 } else { 0 }
                mut total_size := 0
                for field in info.fields {
                    field_size, alignment := t.type_size(field.typ)
                    if is_packed {
                        total_size += field_size
                    } else {
                        if alignment > max_alignment {
                            max_alignment = alignment
                        }
                        total_size = round_up(total_size, alignment) + field_size
                    }
                }
                if is_packed {
                    size = total_size
                    align = 1
                } else {
                    size = round_up(total_size, max_alignment)
                    align = max_alignment
                }
            }
        }
        .string, .multi_return {
            mut max_alignment := 0
            mut total_size := 0
            types := if sym.kind == .string {
                (sym.info as Struct).fields.map(it.typ)
            } else {
                (sym.info as MultiReturn).types
            }
            for ftyp in types {
                field_size, alignment := t.type_size(ftyp)
                if alignment > max_alignment {
                    max_alignment = alignment
                }
                total_size = round_up(total_size, alignment) + field_size
            }
            size = round_up(total_size, max_alignment)
            align = max_alignment
        }
        .sum_type, .interface, .aggregate {
            match mut sym.info {
                SumType, Aggregate {
                    size = (sym.info.fields.len + 2) * t.pointer_size
                    align = t.pointer_size
                }
                Interface {
                    interface_header_size := round_up(t.pointer_size + 4, t.pointer_size) +
                        t.pointer_size
                    size = interface_header_size + sym.info.fields.len * t.pointer_size
                    align = t.pointer_size
                    for etyp in sym.info.embeds {
                        esize, _ := t.type_size(etyp)
                        size += esize - interface_header_size
                    }
                }
                else {
                    // unreachable
                }
            }
        }
        .array_fixed {
            info := sym.info as ArrayFixed
            elem_size, elem_align := t.type_size(info.elem_type)
            size = info.size * elem_size
            align = elem_align
        }
        // TODO: hardcoded:
        .map {
            size = if t.pointer_size == 8 {
                $if new_int ? && x64 { 144 } $else { 120 }
            } else {
                80
            }
            align = t.pointer_size
        }
        .array {
            size = if t.pointer_size == 8 {
                $if new_int ? && x64 { 48 } $else { 32 }
            } else {
                24
            }
            align = t.pointer_size
        }
    }

    sym.size = size
    sym.align = align
    return size, align
}

// round_up rounds the number `n` up to the next multiple `multiple`.
// Note: `multiple` must be a power of 2.
@[inline]
fn round_up(n int, multiple int) int {
    return (n + multiple - 1) & -multiple
}

// for debugging/errors only, perf is not an issue
pub fn (k Kind) str() string {
    return match k {
        .placeholder { 'placeholder' }
        .void { 'void' }
        .voidptr { 'voidptr' }
        .charptr { 'charptr' }
        .byteptr { 'byteptr' }
        .struct { 'struct' }
        .int { 'int' }
        .i8 { 'i8' }
        .i16 { 'i16' }
        .i32 { 'i32' }
        .i64 { 'i64' }
        .isize { 'isize' }
        .u8 { 'u8' }
        .u16 { 'u16' }
        .u32 { 'u32' }
        .u64 { 'u64' }
        .usize { 'usize' }
        .int_literal { 'int_literal' }
        .f32 { 'f32' }
        .f64 { 'f64' }
        .float_literal { 'float_literal' }
        .string { 'string' }
        .char { 'char' }
        .bool { 'bool' }
        .none { 'none' }
        .array { 'array' }
        .array_fixed { 'array_fixed' }
        .map { 'map' }
        .chan { 'chan' }
        .multi_return { 'multi_return' }
        .sum_type { 'sum_type' }
        .alias { 'alias' }
        .enum { 'enum' }
        .any { 'any' }
        .function { 'function' }
        .interface { 'interface' }
        .generic_inst { 'generic_inst' }
        .rune { 'rune' }
        .aggregate { 'aggregate' }
        .thread { 'thread' }
    }
}

pub fn (kinds []Kind) str() string {
    mut kinds_str := ''
    for i, k in kinds {
        kinds_str += k.str()
        if i < kinds.len - 1 {
            kinds_str += '_'
        }
    }
    return kinds_str
}

// human readable type name, also used by vfmt
pub fn (t &Table) type_to_str(typ Type) string {
    return t.type_to_str_using_aliases(typ, map[string]string{})
}

// type name in code (for builtin)
pub fn (t &Table) type_to_code(typ Type) string {
    match typ {
        int_literal_type, float_literal_type { return t.sym(typ).kind.str() }
        else { return t.type_to_str_using_aliases(typ, map[string]string{}) }
    }
}

// clean type name from generics form. From Type[int] -> Type
pub fn (t &Table) clean_generics_type_str(typ Type) string {
    result := t.type_to_str(typ)
    return result.all_before('[')
}

// strip_extra_struct_types removes the `<generic names>` from the
// complete qualified name and keep the `[concrete names]`, For example:
// `main.Foo<T, <T, U>>[int, [int, string]]` -> `main.Foo[int, [int, string]]`
// `main.Foo<T>[int] -> main.Foo[int]`
fn strip_extra_struct_types(name string) string {
    mut start := 0
    mut is_start := false
    mut nested_count := 0
    mut strips := []string{}

    for i, ch in name {
        if ch == `<` {
            if is_start {
                nested_count++
            } else {
                is_start = true
                start = i
            }
        } else if ch == `>` {
            if nested_count > 0 {
                nested_count--
            } else {
                strips << name.substr(start, i + 1)
                strips << ''
                is_start = false
            }
        }
    }
    if strips.len > 0 {
        return name.replace_each(strips)
    } else {
        return name
    }
}

// delete_cached_type_to_str remove a `type_to_str` from the cache
pub fn (t &Table) delete_cached_type_to_str(typ Type, import_aliases_len int) {
    cache_key := (u64(import_aliases_len) << 32) | u64(typ)
    mut mt := unsafe { &Table(t) }
    lock mt.cached_type_to_str {
        mt.cached_type_to_str.delete(cache_key)
    }
}

// import_aliases is a map of imported symbol aliases 'module.Type' => 'Type'
pub fn (t &Table) type_to_str_using_aliases(typ Type, import_aliases map[string]string) string {
    cache_key := (u64(import_aliases.len) << 32) | u64(typ)
    mut mt := unsafe { &Table(t) }
    rlock mt.cached_type_to_str {
        if cached_res := mt.cached_type_to_str[cache_key] {
            return cached_res
        }
    }
    idx := typ.idx()
    if idx == 0 || idx >= t.type_symbols.len {
        return 'unknown'
    }
    sym := t.sym(typ)
    mut res := sym.name
    defer {
        lock mt.cached_type_to_str {
            // Note, that this relies on `res = value return res` if you want to return early!
            mt.cached_type_to_str[cache_key] = res
        }
    }
    // Note, that the duplication of code in some of the match branches here
    // is VERY deliberate. DO NOT be tempted to use `else {}` instead, because
    // that strongly reduces the usefulness of the exhaustive checking that
    // match does.
    //    Using else{} here led to subtle bugs in vfmt discovered *months*
    // after the original code was written.
    //    It is important that each case here is handled *explicitly* and
    // *clearly*, and that when a new kind is added, it should also be handled
    // explicitly.
    match sym.kind {
        .int_literal, .float_literal {}
        .i8, .i16, .i32, .int, .i64, .isize, .u8, .u16, .u32, .u64, .usize, .f32, .f64, .char,
        .rune, .string, .bool, .none, .voidptr, .byteptr, .charptr {
            // primitive types
            res = sym.kind.str()
        }
        .array {
            if typ == array_type {
                res = 'array'
                return res
            }
            if typ.has_flag(.variadic) {
                res = t.type_to_str_using_aliases(t.value_type(typ), import_aliases)
            } else {
                if sym.info is Array {
                    elem_str := t.type_to_str_using_aliases(sym.info.elem_type, import_aliases)
                    res = '[]${elem_str}'
                } else {
                    res = 'array'
                }
            }
        }
        .array_fixed {
            info := sym.info as ArrayFixed
            elem_str := t.type_to_str_using_aliases(info.elem_type, import_aliases)
            if info.size_expr is EmptyExpr {
                res = '[${info.size}]${elem_str}'
            } else {
                size_str := t.fixed_array_size_expr_to_str(info.size_expr, import_aliases)
                res = '[${size_str}]${elem_str}'
            }
        }
        .chan {
            // TODO: currently the `chan` struct in builtin is not considered a struct but a chan
            if sym.mod != 'builtin' && sym.name != 'chan' {
                info := sym.info as Chan
                mut elem_type := info.elem_type
                mut mut_str := ''
                if info.is_mut {
                    mut_str = 'mut '
                    elem_type = elem_type.set_nr_muls(elem_type.nr_muls() - 1)
                }
                elem_str := t.type_to_str_using_aliases(elem_type, import_aliases)
                res = 'chan ${mut_str}${elem_str}'
            }
        }
        .function {
            info := sym.info as FnType
            if !t.is_fmt {
                res = t.fn_signature(info.func, type_only: true)
            } else {
                if res.starts_with('fn (') {
                    // fn foo ()
                    has_names := info.func.params.any(it.name != '')
                    res = t.fn_signature_using_aliases(info.func, import_aliases,
                        type_only: !has_names
                    )
                } else {
                    // FnFoo
                    res = t.shorten_user_defined_typenames(res, import_aliases)
                }
            }
        }
        .map {
            if int(typ) == map_type_idx {
                res = 'map'
                return res
            }
            info := sym.info as Map
            key_str := t.type_to_str_using_aliases(info.key_type, import_aliases)
            val_str := t.type_to_str_using_aliases(info.value_type, import_aliases)
            res = 'map[${key_str}]${val_str}'
        }
        .multi_return {
            res = '('
            info := sym.info as MultiReturn
            for i, typ2 in info.types {
                if i > 0 {
                    res += ', '
                }
                res += t.type_to_str_using_aliases(typ2, import_aliases)
            }
            res += ')'
        }
        .struct, .interface, .sum_type {
            if typ.has_flag(.generic) {
                match sym.info {
                    Struct, Interface, SumType {
                        base_name := if sym.ngname == '' {
                            strip_extra_struct_types(res)
                        } else {
                            sym.ngname
                        }
                        res = t.shorten_user_defined_typenames(base_name, import_aliases)
                        generic_types := if sym.generic_types.len > 0 {
                            sym.generic_types
                        } else {
                            sym.info.generic_types
                        }
                        res += '['
                        for i, gtyp in generic_types {
                            res += t.type_to_str_using_aliases(gtyp, import_aliases)
                            if i != generic_types.len - 1 {
                                res += ', '
                            }
                        }
                        res += ']'
                    }
                    else {}
                }
            } else if sym.info is SumType && (sym.info as SumType).is_anon {
                variant_names := sym.info.variants.map(t.shorten_user_defined_typenames(t.sym(it).name,
                    import_aliases))
                res = '${variant_names.join('|')}'
            } else {
                res = strip_extra_struct_types(res)
                res = t.shorten_user_defined_typenames(res, import_aliases)
            }
        }
        .generic_inst {
            info := sym.info as GenericInst
            res = t.shorten_user_defined_typenames(sym.name.all_before('['), import_aliases)
            res += '['
            for i, ctyp in info.concrete_types {
                res += t.type_to_str_using_aliases(ctyp, import_aliases)
                if i != info.concrete_types.len - 1 {
                    res += ', '
                }
            }
            res += ']'
        }
        .void {
            if typ.has_flag(.option) {
                res = '?'
                return res
            }
            if typ.has_flag(.result) {
                res = '!'
                return res
            }
            res = 'void'
            return res
        }
        .thread {
            rtype := sym.thread_info().return_type
            if rtype != 1 {
                res = 'thread ' + t.type_to_str_using_aliases(rtype, import_aliases)
            }
        }
        .alias, .any, .placeholder, .enum {
            res = t.shorten_user_defined_typenames(res, import_aliases)
            /*
            if res.ends_with('.byte') {
                res = 'u8'
            } else {
                res = t.shorten_user_defined_typenames(res, import_aliases)
            }
            */
        }
        .aggregate {}
    }

    mut nr_muls := typ.nr_muls()
    if typ.has_flag(.shared_f) {
        nr_muls--
        res = 'shared ' + res
    }
    if typ.has_flag(.atomic_f) {
        nr_muls--
        res = 'atomic ' + res
    }
    if nr_muls > 0 && !typ.has_flag(.variadic) {
        res = strings.repeat(`&`, nr_muls) + res
    }
    if typ.has_flag(.option) && res[0] != `?` {
        res = '?${res}'
    }
    if typ.has_flag(.result) {
        res = '!${res}'
    }
    return res
}

// fixed_array_size_expr_to_str renders a fixed-array size expression preserving
// fully-qualified enum names. The default `Expr.str()` drops the enum name on
// `EnumVal` (returning `.value`), which produces invalid output when the size
// is something like `int(TestEnum._max)` because the enum type cannot be
// inferred from context inside the array brackets.
fn (t &Table) fixed_array_size_expr_to_str(expr Expr, import_aliases map[string]string) string {
    match expr {
        CastExpr {
            type_name := t.shorten_user_defined_typenames(t.type_to_str_using_aliases(expr.typ,
                import_aliases), import_aliases)
            return '${type_name}(${t.fixed_array_size_expr_to_str(expr.expr, import_aliases)})'
        }
        EnumVal {
            if expr.enum_name != '' {
                name := t.shorten_user_defined_typenames(expr.enum_name, import_aliases)
                return '${name}.${expr.val}'
            }
            return '.${expr.val}'
        }
        Ident {
            return t.shorten_user_defined_typenames(expr.name, import_aliases)
        }
        else {
            return expr.str()
        }
    }
}

fn (t &Table) shorten_user_defined_typenames(original_name string, import_aliases map[string]string) string {
    if alias := import_aliases[original_name] {
        return alias
    }
    mut mod, mut typ := original_name.rsplit_once('.') or { return original_name }
    if !mod.contains('[') {
        if !t.is_fmt {
            mod = mod.all_after_last('.')
        }
        if alias := import_aliases[mod] {
            mod = alias
        } else if t.cmod_prefix != '' {
            if alias := import_aliases[t.cmod_prefix + mod] {
                mod = alias
            } else {
                // cur_mod.Type => Type
                return original_name.all_after(t.cmod_prefix)
            }
        }
    }
    // E.g.: []mod.Type => []Type; []mod.submod.Type => []submod.Type;
    // imported_mod.Type[mod.Result[[]mod.Token]] => imported_mod.Type[Result[[]Token]]
    if original_name.contains('[]') {
        if lhs, typ_after_lsbr := original_name.split_once('[') {
            if mod_, typ_before_lsbr := lhs.rsplit_once('.') {
                mod = mod_
                typ = '${typ_before_lsbr}[${typ_after_lsbr}'
            }
        }
    }
    return '${mod}.${typ}'
}

@[minify]
pub struct FnSignatureOpts {
pub:
    skip_receiver bool
    type_only     bool
}

pub fn (t &Table) fn_signature(func &Fn, opts FnSignatureOpts) string {
    return t.fn_signature_using_aliases(func, map[string]string{}, opts)
}

pub fn (t &Table) fn_signature_using_aliases(func &Fn, import_aliases map[string]string, opts FnSignatureOpts) string {
    mut sb := strings.new_builder(20)
    if !opts.skip_receiver {
        sb.write_string('fn ')
        // TODO: write receiver
    }
    if !opts.type_only {
        sb.write_string(func.name)
    }
    sb.write_string('(')
    start := int(func.is_method && opts.skip_receiver)
    for i in start .. func.params.len {
        if i != start {
            sb.write_string(', ')
        }
        param := func.params[i]
        mut typ := param.typ
        if param.is_mut {
            if param.typ.is_ptr() {
                typ = typ.deref()
            }
            sb.write_string('mut ')
        }
        if !opts.type_only {
            sb.write_string(param.name)
            sb.write_string(' ')
        }
        styp := t.type_to_str_using_aliases(typ, import_aliases)
        if i == func.params.len - 1 && func.is_variadic && !func.is_c_variadic {
            sb.write_string('...')
            sb.write_string(styp)
        } else {
            sb.write_string(styp)
        }
    }
    if func.is_c_variadic {
        if func.params.len > 0 {
            sb.write_string(', ')
        }
        sb.write_string('...')
    }
    sb.write_string(')')
    if func.return_type != void_type {
        sb.write_string(' ')
        sb.write_string(t.type_to_str_using_aliases(func.return_type, import_aliases))
    }
    return sb.str()
}

// symbol_name_except_generic return the name of the complete qualified name of the type,
// but without the generic parts. The potential `[]`, `&[][]` etc prefixes are kept. For example:
// `main.Abc[int]` -> `main.Abc`
// `main.Abc<T>[int]` -> `main.Abc<T>`
// `[]main.Abc<T>[int]` -> `[]main.Abc<T>`
// `&[][]main.Abc<T>[int]` -> `&[][]main.Abc<T>`
pub fn (t &TypeSymbol) symbol_name_except_generic() string {
    // &[]main.Abc[int], [][]main.Abc[int]...
    mut prefix := ''
    mut name := t.name
    for i, ch in t.name {
        if ch in [`&`, `[`, `]`] {
            continue
        }
        if i > 0 {
            prefix = t.name[..i]
            name = t.name[i..]
        }
        break
    }
    // main.Abc[int]
    // remove generic part from name
    // main.Abc[int] => main.Abc
    if name.contains('[') {
        name = name.all_before('[')
    }
    return prefix + name
}

// embed_name return the pure name of the complete qualified name of the type,
// without the generic parts, concrete parts and mod parts. For example:
// `main.Abc[int]` -> `Abc`
// `main.Abc<T>[int]` -> `Abc`
pub fn (t &TypeSymbol) embed_name() string {
    if t.name.contains('<') {
        // Abc<T>[int] => Abc
        // main.Abc<T>[main.Enum] => Abc
        return t.name.split('<')[0].split('.').last()
    } else if t.name.contains('[') {
        // Abc[int] => Abc
        // main.Abc[main.Enum] => Abc
        return t.name.split('[')[0].split('.').last()
    } else {
        // main.Abc => Abc
        return t.name.split('.').last()
    }
}

pub fn (t &TypeSymbol) has_method(name string) bool {
    for mut method in unsafe { t.methods } {
        if method.name.len == name.len && method.name == name {
            return true
        }
    }
    return false
}

pub fn (t &TypeSymbol) has_method_with_generic_parent(name string) bool {
    m := t.find_method_with_generic_parent(name) or { return false }
    return t.kind != .interface || !m.no_body
}

pub fn (t &TypeSymbol) find_method(name string) ?Fn {
    for mut method in unsafe { t.methods } {
        if method.name.len == name.len && method.name == name {
            return method
        }
    }
    return none
}

fn specialize_method_with_concrete_types(method Fn, generic_names []string, concrete_types []Type) Fn {
    mut table := global_table
    mut resolved := method
    return_sym := table.sym(resolved.return_type)
    if return_sym.kind in [.struct, .interface, .sum_type] {
        resolved.return_type = table.unwrap_generic_type(resolved.return_type, generic_names,
            concrete_types)
    } else if rt := table.convert_generic_type(resolved.return_type, generic_names, concrete_types) {
        resolved.return_type = rt
    }
    resolved.params = resolved.params.clone()
    for mut param in resolved.params {
        if pt := table.convert_generic_type(param.typ, generic_names, concrete_types) {
            param.typ = pt
        }
    }
    return resolved
}

pub fn (t &TypeSymbol) find_method_with_generic_parent(name string) ?Fn {
    mut table := global_table
    mut generic_names := []string{}
    mut concrete_types := []Type{}
    mut generic_inst_parent_idx := 0
    match t.info {
        Struct, Interface, SumType {
            generic_names = t.info.generic_types.map(table.sym(it).name)
            if t.info.concrete_types.len == generic_names.len {
                concrete_types = t.info.concrete_types.clone()
            } else if t.generic_types.len == generic_names.len
                && t.generic_types != t.info.generic_types {
                concrete_types = t.generic_types.clone()
            }
        }
        GenericInst {
            generic_inst_parent_idx = t.info.parent_idx
            parent_sym := table.sym(new_type(generic_inst_parent_idx))
            match parent_sym.info {
                Struct, Interface, SumType {
                    generic_names = parent_sym.info.generic_types.map(table.sym(it).name)
                    concrete_types = t.info.concrete_types.clone()
                }
                FnType {
                    generic_names = parent_sym.info.func.generic_names.clone()
                    concrete_types = t.info.concrete_types.clone()
                }
                else {}
            }
        }
        else {}
    }

    if m := t.find_method(name) {
        if generic_names.len == concrete_types.len && concrete_types.len > 0 {
            return specialize_method_with_concrete_types(m, generic_names, concrete_types)
        }
        return m
    }
    if generic_inst_parent_idx != 0 {
        mut psym := table.sym(new_type(generic_inst_parent_idx))
        for {
            if m := psym.find_method(name) {
                if generic_names.len == concrete_types.len && concrete_types.len > 0 {
                    return specialize_method_with_concrete_types(m, generic_names, concrete_types)
                }
                return m
            }
            if psym.parent_idx == 0 {
                break
            }
            psym = table.type_symbols[psym.parent_idx]
        }
    }
    match t.info {
        Struct, Interface, SumType {
            if t.info.parent_type.has_flag(.generic) {
                mut psym2 := table.sym(t.info.parent_type)
                for {
                    if x := psym2.find_method(name) {
                        match psym2.info {
                            Struct, Interface, SumType {
                                return specialize_method_with_concrete_types(x, generic_names,
                                    concrete_types)
                            }
                            else {}
                        }
                    }
                    if psym2.parent_idx == 0 {
                        break
                    }
                    psym2 = table.type_symbols[psym2.parent_idx]
                }
            }
        }
        else {}
    }

    return none
}

// is_js_compatible returns true if type can be converted to JS type and from JS type back to V type
pub fn (t &TypeSymbol) is_js_compatible() bool {
    mut table := global_table
    if t.kind == .void {
        return true
    }
    if t.kind == .function {
        return true
    }
    if t.language == .js || t.name.starts_with('JS.') {
        return true
    }
    match t.info {
        SumType {
            for variant in t.info.variants {
                sym := table.final_sym(variant)
                if !sym.is_js_compatible() {
                    return false
                }
            }
            return true
        }
        else {
            return true
        }
    }
}

pub fn (t &TypeSymbol) str_method_info() (bool, bool, int) {
    mut has_str_method := false
    mut expects_ptr := false
    mut nr_args := 0
    if sym_str_method := t.find_method_with_generic_parent('str') {
        has_str_method = t.kind != .interface || !sym_str_method.no_body
        nr_args = sym_str_method.params.len
        if nr_args > 0 {
            expects_ptr = sym_str_method.params[0].typ.is_ptr()
        }
    } else {
        // C Struct which does not implement str() are passed as pointer to handle incomplete type
        expects_ptr = t.is_c_struct()
    }
    return has_str_method, expects_ptr, nr_args
}

pub fn (t &TypeSymbol) find_field(name string) ?StructField {
    match t.info {
        Struct { return t.info.find_field(name) }
        Interface { return t.info.find_field(name) }
        SumType { return t.info.find_sum_type_field(name) }
        Aggregate { return t.info.find_field(name) }
        else { return none }
    }
}

pub fn (t &TypeSymbol) has_field(name string) bool {
    t.find_field(name) or { return false }

    return true
}

fn (a &Aggregate) find_field(name string) ?StructField {
    for mut field in unsafe { a.fields } {
        if field.name.len == name.len && field.name == name {
            return field
        }
    }
    return none
}

pub fn (i &Interface) find_field(name string) ?StructField {
    for mut field in unsafe { i.fields } {
        if field.name.len == name.len && field.name == name {
            return field
        }
    }
    return none
}

pub fn (i &Interface) find_method(name string) ?Fn {
    for mut method in unsafe { i.methods } {
        if method.name.len == name.len && method.name == name {
            return method
        }
    }
    return none
}

pub fn (i &Interface) has_method(name string) bool {
    for mut method in unsafe { i.methods } {
        if method.name.len == name.len && method.name == name {
            return true
        }
    }
    return false
}

pub fn (s Struct) find_field(name string) ?StructField {
    for mut field in unsafe { s.fields } {
        if name.len == field.name.len && field.name == name {
            return field
        }
    }
    return none
}

pub fn (s Struct) get_field(name string) StructField {
    if field := s.find_field(name) {
        return field
    }
    panic('unknown field `${name}`')
}

pub fn (s &SumType) find_sum_type_field(name string) ?StructField {
    for mut field in unsafe { s.fields } {
        if field.name == name {
            return field
        }
    }
    return none
}

// For the 'field does not exist or have the same type in all sumtype  variants' error.
// To print all sumtype variants the developer has to fix.
pub fn (t &Table) find_missing_variants(s &SumType, field_name string) string {
    mut res := []string{cap: 5}
    for variant in s.variants {
        ts := t.sym(variant)
        if ts.kind != .struct {
            continue
        }
        mut found := false
        struct_info := ts.info as Struct
        for field in struct_info.fields {
            if field.name == field_name {
                found = true
                break
            }
        }
        if !found {
            res << ts.name
        }
    }
    // println('!!!!! field_name=${field_name}')
    // print_backtrace()
    // println(res)
    str := res.join(', ')
    return str.replace("'", '`')
}

pub fn (i Interface) defines_method(name string) bool {
    if i.methods.any(it.name == name) {
        return true
    }
    if i.parent_type.has_flag(.generic) {
        parent_sym := global_table.sym(i.parent_type)
        parent_info := parent_sym.info as Interface
        if parent_info.methods.any(it.name == name) {
            return true
        }
    }
    return false
}

pub fn (i Interface) get_methods() []string {
    if i.methods.len > 0 {
        return i.methods.map(it.name)
    }
    if i.parent_type.has_flag(.generic) {
        parent_sym := global_table.sym(i.parent_type)
        parent_info := parent_sym.info as Interface
        return parent_info.methods.map(it.name)
    }
    return []
}

pub fn (t &TypeSymbol) get_methods() []Fn {
    mut methods := t.methods.filter(it.attrs.len == 0) // methods without attrs first
    mut methods_with_attrs := t.methods.filter(it.attrs.len > 0) // methods with attrs second
    mut existing_method_names := map[string]bool{}
    for method in t.methods {
        existing_method_names[method.name] = true
    }
    mut inherited_methods := []Fn{}
    match t.info {
        Struct, Interface, SumType {
            if t.info.parent_type.has_flag(.generic) {
                parent_sym := global_table.sym(t.info.parent_type)
                match parent_sym.info {
                    Struct, Interface, SumType, Alias {
                        inherited_methods = parent_sym.get_methods()
                    }
                    else {}
                }
            }
        }
        Alias {
            parent_sym := global_table.sym(t.info.parent_type)
            inherited_methods = parent_sym.get_methods()
        }
        else {}
    }

    for method in inherited_methods {
        if method.name in existing_method_names {
            continue
        }
        existing_method_names[method.name] = true
        if method.attrs.len == 0 {
            methods << method
        } else {
            methods_with_attrs << method
        }
    }
    methods << methods_with_attrs
    return methods
}