// 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
}