TypeScript type inference prototype

builder.rs

use estree::{visit::Visit, TSType, *};
use rustc_hash::FxHashMap;

use super::{
    facts::TypeFacts,
    helper::*,
    links::{NodeLink, SymbolLink},
    resolution::{TypeResolution, TypeSystemEntity},
    signature::{SignatureId, SignaturesTable},
    LiteralValue, ObjectFlags, TypeFlags, TypeId, TypeKind, TypeTable, UnionReduction,
    WideningContext,
};
use crate::{
    flow::FlowBuilder,
    node::{AstNodeId, AstNodes},
    scope::{ScopeFlags, ScopeTree},
    symbol::{SymbolFlags, SymbolId, SymbolMap, SymbolTable},
    SemanticBuilderOptions,
};

pub type SymbolLinks = FxHashMap<SymbolId, SymbolLink>;
pub type NodeLinks = FxHashMap<Span, NodeLink>;

#[derive(Debug)]
pub struct TypeBuilder<'a> {
    options: SemanticBuilderOptions,
    pub types: TypeTable,
    pub signatures: SignaturesTable,

    pub nodes: AstNodes<'a>,
    pub scopes: ScopeTree,
    pub flow: FlowBuilder,
    pub symbols: SymbolTable,

    pub span_to_node: FxHashMap<Span, AstNodeId>,

    pub symbol_links: SymbolLinks,
    pub node_links: NodeLinks,

    /// Type Resolution for detecting circular type queries during type inference
    /// see `push_type_resolution` for implementation details
    pub resolutions: Vec<TypeResolution>,
}

impl<'a> Visit<'a> for TypeBuilder<'a> {
    fn enter_node(&mut self, kind: AstKind<'a>) {
        self.check_source_element(kind);
    }

    fn visit_expression(&mut self, expr: &'a Expression<'a>) {
        self.check_expression_cached(expr);
        self.visit_expression_match(expr);
    }
}

/// Type Building Utilities / Main Entry Points
impl<'a> TypeBuilder<'a> {
    #[must_use]
    pub fn new(
        options: &SemanticBuilderOptions,
        nodes: AstNodes<'a>,
        scopes: ScopeTree,
        flow: FlowBuilder,
        symbols: SymbolTable,
        span_to_node: FxHashMap<Span, AstNodeId>,
    ) -> Self {
        let mut types = TypeTable::new(options, &symbols);

        let mut symbol_links: FxHashMap<SymbolId, SymbolLink> = FxHashMap::default();
        symbol_links.entry(symbols.unknown_symbol_id).or_default().t = Some(types.error_type_id);
        symbol_links.entry(symbols.undefined_symbol_id).or_default().t =
            Some(types.undefined_type_id);

        let signatures = SignaturesTable::new(&mut types);
        Self {
            options: *options,
            types,
            signatures,
            nodes,
            scopes,
            flow,
            symbols,
            span_to_node,
            symbol_links,
            node_links: FxHashMap::default(),
            resolutions: Vec::new(),
        }
    }

    #[must_use]
    pub fn build(mut self, program: &'a Program<'a>) -> Self {
        self.visit_program(program);
        self
    }

    /// Get `Symbol` cache
    fn get_symbol_links(&mut self, symbol_id: SymbolId) -> &mut SymbolLink {
        self.symbol_links.entry(symbol_id).or_default()
    }

    /// Get `Node` cache
    fn get_node_links(&mut self, span: Span) -> &mut NodeLink {
        self.node_links.entry(span).or_default()
    }

    /// Main entry point for: `Symbol` -> `Type`
    fn get_type_of_symbol(&mut self, symbol_id: SymbolId) -> TypeId {
        let symbol = &self.symbols[symbol_id];

        // A quick route for getting the type from a global symbol.
        // This is not part of tsc.
        match symbol_id {
            _ if symbol_id == self.symbols.global_array_symbol_id => {
                return self.types.global_array_type_id;
            }
            _ if symbol_id == self.symbols.global_object_symbol_id => {
                return self.types.global_object_type_id;
            }
            _ if symbol_id == self.symbols.global_function_symbol_id => {
                return self.types.global_function_type_id;
            }
            _ if symbol_id == self.symbols.global_string_symbol_id => {
                return self.types.global_string_type_id;
            }
            _ if symbol_id == self.symbols.global_number_symbol_id => {
                return self.types.global_number_type_id;
            }
            _ if symbol_id == self.symbols.global_boolean_symbol_id => {
                return self.types.global_boolean_type_id;
            }
            _ if symbol_id == self.symbols.global_regexp_symbol_id => {
                return self.types.global_regexp_type_id;
            }
            _ if symbol_id == self.symbols.global_promise_symbol_id => {
                return self.types.global_promise_type_id;
            }
            _ => {}
        }

        let flags = symbol.flags;
        if flags.intersects(SymbolFlags::Variable | SymbolFlags::Property) {
            return self.get_type_of_variable_or_parameter_or_property(symbol_id);
        }
        if flags.is_function_or_class_or_enum_or_module() {
            return self.get_type_of_func_class_enum_module(symbol_id);
        }
        self.types.any_type_id
    }

    /// Main entry point for: `IdentifierReference` -> `Symbol`
    fn get_resolved_symbol(&mut self, name: &Atom, span: Span) -> SymbolId {
        if let Some(symbol_id) = self.get_node_links(span.clone()).resolved_symbol {
            return symbol_id;
        }
        let symbol_id =
            self.resolve_name(name, span.clone()).unwrap_or(self.symbols.unknown_symbol_id);
        self.get_node_links(span).resolved_symbol.replace(symbol_id);
        symbol_id
    }

    fn resolve_name(&mut self, name: &Atom, span: Span) -> Option<SymbolId> {
        self.span_to_node
            .get(&span)
            .and_then(|node_id| {
                // try find from ancestor scopes
                self.scopes
                    .node_scope_ancestors(&self.nodes[node_id.id()])
                    .map(|scope_id| self.scopes[scope_id].get())
                    .find_map(|scope| scope.variables.get(name))
            })
            // or from the global symbol table
            .or_else(|| self.symbols.globals.get(name))
            .copied()
    }

    fn with_resolved_type<F>(&mut self, span: Span, resolver: F) -> TypeId
    where
        F: FnOnce(&mut Self) -> TypeId,
    {
        if let Some(resolved) = self.get_node_links(span.clone()).resolved_type {
            return resolved;
        }
        let type_id = resolver(self);
        self.get_node_links(span).resolved_type.replace(type_id);
        type_id
    }

    fn get_declared_type_of_symbol(&mut self, symbol_id: SymbolId) -> TypeId {
        self.try_get_declared_type_of_symbol(symbol_id).unwrap_or(self.types.error_type_id)
    }

    fn try_get_declared_type_of_symbol(&mut self, symbol_id: SymbolId) -> Option<TypeId> {
        let flags = self.symbols[symbol_id].flags;
        if flags.intersects(SymbolFlags::Class | SymbolFlags::Interface) {
            return Some(self.get_declared_type_of_class_or_interface(symbol_id));
        }
        if flags.intersects(SymbolFlags::TypeAlias) {
            return Some(self.get_declared_type_of_type_alias(symbol_id));
        }
        if flags.intersects(SymbolFlags::Enum) {
            return Some(self.get_declared_type_of_enum(symbol_id));
        }
        None
    }

    /// ```
    /// semantic::check(r#"
    ///   type A = number;
    ///   let a: A;
    ///   //  ^? number
    /// "#);
    /// ```
    fn get_declared_type_of_type_alias(&mut self, symbol_id: SymbolId) -> TypeId {
        if let Some(resolved) = self.get_symbol_links(symbol_id).declared_type {
            return resolved;
        }

        if !self.push_type_resolution(TypeSystemEntity::DeclaredType(symbol_id)) {
            return self.types.error_type_id;
        }

        let symbol = &self.symbols[symbol_id];

        let mut type_id = symbol
            .declarations
            .iter()
            .find_map(|node_id| match self.nodes[*node_id].kind {
                AstKind::TSTypeAliasDeclaration(decl) => Some(decl),
                _ => None,
            })
            .map_or(self.types.error_type_id, |decl| {
                self.get_type_from_type_node(&decl.type_annotation)
            });

        if self.pop_type_resolution() {
            // TODO init type parameters
        } else {
            type_id = self.types.error_type_id;
        }

        self.get_symbol_links(symbol_id).declared_type.replace(type_id);
        type_id
    }

    fn get_declared_type_of_class_or_interface(&mut self, symbol_id: SymbolId) -> TypeId {
        self.get_symbol_links(symbol_id).declared_type.unwrap_or_else(|| {
            let flags = self.symbols[symbol_id].flags;
            let kind = if flags.contains(SymbolFlags::Class) {
                ObjectFlags::Class
            } else {
                ObjectFlags::Interface
            };

            let object_type_id = self.types.create_object_type(kind, Some(symbol_id));
            self.get_symbol_links(symbol_id).declared_type.replace(object_type_id);
            object_type_id
        })
    }

    fn get_declared_type_of_enum(&mut self, symbol_id: SymbolId) -> TypeId {
        self.get_symbol_links(symbol_id).declared_type.unwrap_or_else(|| {
            let enum_type_id = self.types.create_enum_type(symbol_id);
            self.get_symbol_links(symbol_id).declared_type.replace(enum_type_id);
            enum_type_id
        })
    }
}

/// Type Inference Methods
impl<'a> TypeBuilder<'a> {
    fn get_type_reference_type(
        &mut self,
        reference: &TSTypeReference<'a>,
        symbol_id: SymbolId,
    ) -> TypeId {
        if symbol_id == self.symbols.unknown_symbol_id {
            return self.types.error_type_id;
        }

        let flags = self.symbols[symbol_id].flags;
        if flags.intersects(SymbolFlags::Class | SymbolFlags::Interface) {}

        if flags.intersects(SymbolFlags::TypeAlias) {
            return self.get_type_from_type_alias_reference(reference, symbol_id);
        }

        if let Some(type_id) = self.try_get_declared_type_of_symbol(symbol_id) {
            return type_id;
        }

        self.types.error_type_id
    }

    fn get_type_from_type_alias_reference(
        &mut self,
        _reference: &TSTypeReference<'a>,
        symbol_id: SymbolId,
    ) -> TypeId {
        self.get_declared_type_of_symbol(symbol_id)
    }

    fn resolve_type_reference_name(&mut self, reference: &TSTypeReference<'a>) -> SymbolId {
        match &reference.type_name {
            TSTypeName::IdentifierName(ident) => Some(ident),
            TSTypeName::QualifiedName(_) => None,
        }
        .and_then(|name| self.resolve_entity_name(&name.name, name.node.range()))
        .unwrap_or(self.symbols.unknown_symbol_id)
    }

    /// Resolves a qualified name and any involved aliases.
    fn resolve_entity_name(&mut self, name: &Atom, span: Span) -> Option<SymbolId> {
        self.span_to_node
            .get(&span)
            .and_then(|node_id| {
                // try find from ancestor scopes
                self.scopes
                    .node_scope_ancestors(&self.nodes[node_id.id()])
                    .map(|scope_id| self.scopes[scope_id].get())
                    .find_map(|scope| scope.variables.get(name))
            })
            // or from the global symbol table
            .or_else(|| self.symbols.globals.get(name))
            .copied()
    }

    fn resolve_call_expression(&mut self, expr: &'a CallExpression<'a>) -> SignatureId {
        let func_type_id = self.check_expression(&expr.callee);
        let signatures = self.get_signatures_of_type(func_type_id);
        if signatures.is_empty() { self.signatures.empty_signature_id } else { signatures[0] }
    }

    fn resolve_new_expression(&mut self, expr: &'a NewExpression<'a>) -> SignatureId {
        let expression_type = self.check_expression(&expr.callee);
        let construct_signatures = self.get_signatures_of_type(expression_type);
        if construct_signatures.is_empty() {
            self.signatures.empty_signature_id
        } else {
            construct_signatures[0]
        }
    }

    fn resolve_signature(&mut self, expr: CallLikeExpression<'a>) -> SignatureId {
        match expr {
            CallLikeExpression::CallExpression(expr) => self.resolve_call_expression(expr),
            CallLikeExpression::NewExpression(expr) => self.resolve_new_expression(expr),
        }
    }

    fn resolve_anonymous_type_members(&mut self, type_id: TypeId) {
        let r#type = &self.types[type_id];
        if let Some(symbol_id) = r#type.symbol_id {
            let symbol = &self.symbols[symbol_id];
            if symbol.flags.intersects(SymbolFlags::Function) {
                let signatures = self.get_signatures_of_symbol(symbol_id);
                if let TypeKind::ObjectType(object_type) = &mut self.types[type_id].kind {
                    object_type.call_signatures = signatures;
                }
            }
        }
    }

    fn get_signatures_of_symbol(&mut self, symbol_id: SymbolId) -> Vec<SignatureId> {
        self.symbols[symbol_id]
            .declarations
            .clone()
            .into_iter()
            .filter_map(|node_id| {
                self.nodes[node_id]
                    .kind
                    .is_function_like()
                    .then(|| self.get_signature_from_declaration(node_id))
            })
            .collect()
    }

    fn resolve_structured_type_members(&mut self, type_id: TypeId) -> TypeId {
        let ty = &self.types[type_id];
        if ty.flags.intersects(TypeFlags::Object) {
            if let TypeKind::ObjectType(object_type) = &ty.kind {
                if object_type.object_flags.intersects(ObjectFlags::Anonymous) {
                    self.resolve_anonymous_type_members(type_id);
                }
            }
        }
        type_id
    }

    /// ```
    /// semantic::check(r#"
    ///   function x() { };
    ///   //       ^? () => void
    /// "#);
    /// ```
    fn get_type_of_func_class_enum_module(&mut self, symbol_id: SymbolId) -> TypeId {
        self.get_symbol_links(symbol_id).t.unwrap_or_else(|| {
            let type_id = self.get_type_of_func_class_enum_module_worker(symbol_id);
            self.get_symbol_links(symbol_id).t.replace(type_id);
            type_id
        })
    }

    fn get_type_of_func_class_enum_module_worker(&mut self, symbol_id: SymbolId) -> TypeId {
        // TODO handle module and binary expression

        let type_id = self.types.create_object_type(ObjectFlags::Anonymous, Some(symbol_id));

        // TODO: this should be replaced with `contextuallyCheckFunctionExpressionOrObjectLiteralMethod` -> `resolveAnonymousTypeMembers`
        match self.types[type_id].kind {
            TypeKind::ObjectType(_) => {
                if self.symbols[symbol_id].flags.intersects(SymbolFlags::Function) {
                    let call_signatures = self.get_signatures_of_symbol(symbol_id);
                    if let TypeKind::ObjectType(object_type) = &mut self.types[type_id].kind {
                        object_type.call_signatures = call_signatures;
                    }
                }
            }
            _ => unreachable!(),
        }

        let symbol = &self.symbols[symbol_id];
        if symbol.flags.intersects(SymbolFlags::Class) { self.types.any_type_id } else { type_id }
    }

    /// ```
    /// semantic::check(r#"
    ///   function a (n: number) {}
    ///   //       ^? (n: number) => void
    /// "#);
    /// ```
    fn get_signature_from_declaration(&mut self, node_id: AstNodeId) -> SignatureId {
        let kind = self.nodes[node_id].kind;
        let span = kind.node().range();
        if let Some(resolved) = self.get_node_links(span.clone()).resolved_signature {
            return resolved;
        }

        let signature_id = self.signatures.create_signature(Some(node_id), None);
        self.get_node_links(span).resolved_signature.replace(signature_id);

        // unlike tsc, we eagerly resolve and cache return type here
        if matches!(kind, AstKind::Function(_) | AstKind::ArrowExpression(_)) {
            self.get_return_type_of_signature(signature_id);
        }

        if let AstKind::Function(Function { params, .. })
        | AstKind::ArrowExpression(ArrowExpression { params, .. }) = kind
        {
            self.signatures[signature_id].parameters = params
                .items
                .iter()
                .map(|param| self.symbols.span_to_symbol[&param.node.range()])
                .collect();
        }

        signature_id
    }

    fn get_type_of_variable_or_parameter_or_property(&mut self, symbol_id: SymbolId) -> TypeId {
        self.get_symbol_links(symbol_id).t.unwrap_or_else(|| {
            let type_id = self.get_type_of_variable_or_parameter_or_property_worker(symbol_id);
            self.get_symbol_links(symbol_id).t.replace(type_id);
            type_id
        })
    }

    /// ```
    /// semantic::check(r#"
    ///   let foo = foo; // case for `push_type_resolution`
    ///   //  ^? any
    ///   let a = 1, b = "2";
    ///   //         ^? string
    ///   interface B { key: boolean }
    ///   //         // ^? boolean
    ///   function c (n: number) {}
    ///   //       // ^? number
    /// "#);
    /// ```
    fn get_type_of_variable_or_parameter_or_property_worker(
        &mut self,
        symbol_id: SymbolId,
    ) -> TypeId {
        let symbol = &self.symbols[symbol_id];
        let declaration = symbol
            .value_declaration
            .map(|node_id| self.nodes.kind(*node_id))
            .map_or_else(|| unreachable!(), |kind| kind);

        // Handle variable, parameter or property
        if !self.push_type_resolution(TypeSystemEntity::Type(symbol_id)) {
            return self.types.error_type_id;
        }

        let type_id = match declaration {
            AstKind::VariableDeclarator(decl) => self
                .get_widened_type_for_variable_like_declaration(
                    VariableLikeDeclaration::VariableDeclarator(decl),
                ),
            AstKind::TSPropertySignature(sig) => self
                .get_widened_type_for_variable_like_declaration(
                    VariableLikeDeclaration::PropertySignature(sig),
                ),
            AstKind::FormalParameter(param) => self.get_widened_type_for_variable_like_declaration(
                VariableLikeDeclaration::FormalParameter(param),
            ),
            AstKind::Function(_) => self.get_type_of_func_class_enum_module(symbol_id),
            AstKind::Property(property) => self.check_property_assignment(property),
            _ => self.types.any_type_id,
        };
        if !self.pop_type_resolution() {
            // Symbol is property of some kind that is merged with something - should use `getTypeOfFuncClassEnumModule` and not `getTypeOfVariableOrParameterOrProperty`
            // if (symbol.flags & SymbolFlags.ValueModule && !(symbol.flags & SymbolFlags.Assignment)) {
            // return getTypeOfFuncClassEnumModule(symbol);
            // }
            return self.types.error_type_id;
        }
        type_id
    }

    fn get_union_type(&mut self, types: &[TypeId], union_reduction: UnionReduction) -> TypeId {
        match types[..] {
            [] => return self.types.never_type_id,
            [type_id] => return type_id,
            _ => {}
        }
        let mut type_set: Vec<TypeId> = vec![];
        let includes = self.add_types_to_union(&mut type_set, TypeFlags::empty(), types);
        if union_reduction != UnionReduction::None {
            if includes.intersects(TypeFlags::AnyOrUnknown) {
                return if includes.intersects(TypeFlags::Any) {
                    if includes.intersects(TypeFlags::IncludesWildcard) {
                        self.types.wildcard_type_id
                    } else {
                        self.types.any_type_id
                    }
                } else if includes.intersects(TypeFlags::Null)
                    || type_set.contains(&self.types.unknown_type_id)
                {
                    self.types.unknown_type_id
                } else {
                    self.types.non_null_unknown_type_id
                };
            }
            // if (exactOptionalPropertyTypes && includes & TypeFlags.Undefined) {
            // const missingIndex = binarySearch(typeSet, missingType, getTypeId, compareValues);
            // if (missingIndex >= 0 && containsType(typeSet, undefinedType)) {
            // orderedRemoveItemAt(typeSet, missingIndex);
            // }
            // }
            if includes.intersects(
                TypeFlags::Literal
                    | TypeFlags::UniqueESSymbol
                    | TypeFlags::TemplateLiteral
                    | TypeFlags::StringMapping,
            ) || (includes.intersects(TypeFlags::Void)
                && includes.intersects(TypeFlags::Undefined))
            {
                type_set = self.remove_redundant_literal_types(
                    &type_set,
                    includes,
                    union_reduction == UnionReduction::Subtype,
                );
            }
            // if (includes & TypeFlags.StringLiteral && includes & TypeFlags.TemplateLiteral) {
            // removeStringLiteralsMatchedByTemplateLiterals(typeSet);
            // }
            // if (unionReduction === UnionReduction.Subtype) {
            // typeSet = removeSubtypes(typeSet, !!(includes & TypeFlags.Object));
            // if (!typeSet) {
            // return errorType;
            // }
            // }
            if type_set.is_empty() {
                return if includes.intersects(TypeFlags::Null) {
                    if includes.intersects(TypeFlags::IncludesNonWideningType) {
                        self.types.null_type_id
                    } else {
                        self.types.null_widening_type_id
                    }
                } else if includes.intersects(TypeFlags::Undefined) {
                    if includes.intersects(TypeFlags::IncludesNonWideningType) {
                        self.types.undefined_type_id
                    } else {
                        self.types.undefined_widening_type_id
                    }
                } else {
                    self.types.never_type_id
                };
            }
        }
        // if (!origin && includes & TypeFlags.Union) {
        // const namedUnions: Type[] = [];
        // addNamedUnions(namedUnions, types);
        // const reducedTypes: Type[] = [];
        // for (const t of typeSet) {
        // if (!some(namedUnions, union => containsType((union as UnionType).types, t))) {
        // reducedTypes.push(t);
        // }
        // }
        // if (!aliasSymbol && namedUnions.length === 1 && reducedTypes.length === 0) {
        // return namedUnions[0];
        // }
        // // We create a denormalized origin type only when the union was created from one or more named unions
        // // (unions with alias symbols or origins) and when there is no overlap between those named unions.
        // const namedTypesCount = reduceLeft(namedUnions, (sum, union) => sum + (union as UnionType).types.length, 0);
        // if (namedTypesCount + reducedTypes.length === typeSet.length) {
        // for (const t of namedUnions) {
        // insertType(reducedTypes, t);
        // }
        // origin = createOriginUnionOrIntersectionType(TypeFlags.Union, reducedTypes);
        // }
        // }
        self.types.create_union_type(type_set)
    }

    // This function assumes the constituent type list is sorted and deduplicated.
    fn get_union_type_from_sorted_list(
        &mut self,
        types: &[TypeId],
        _object_flags: ObjectFlags,
    ) -> TypeId {
        match types[..] {
            [] => return self.types.never_type_id,
            [type_id] => return type_id,
            _ => {}
        }

        // const typeKey = !origin ? getTypeListId(types) :
        // origin.flags & TypeFlags.Union ? `|${getTypeListId((origin as UnionType).types)}` :
        // origin.flags & TypeFlags.Intersection ? `&${getTypeListId((origin as IntersectionType).types)}` :
        // `#${(origin as IndexType).type.id}|${getTypeListId(types)}`; // origin type id alone is insufficient, as `keyof x` may resolve to multiple WIP values while `x` is still resolving
        // const id = typeKey + getAliasId(aliasSymbol, aliasTypeArguments);
        // let type = unionTypes.get(id);
        // if (!type) {

        // type.objectFlags = objectFlags | getPropagatingFlagsOfTypes(types, [>excludeKinds<] TypeFlags.Nullable);
        // type.types = types;
        // type.origin = origin;
        // type.aliasSymbol = aliasSymbol;
        // type.aliasTypeArguments = aliasTypeArguments;
        // if (types.length === 2 && types[0].flags & TypeFlags.BooleanLiteral && types[1].flags & TypeFlags.BooleanLiteral) {
        // type.flags |= TypeFlags.Boolean;
        // (type as UnionType & IntrinsicType).intrinsicName = "boolean";
        // }
        // unionTypes.set(id, type);
        // }
        // return type;
        self.types.create_union_type(types.to_vec())
    }

    /// ```
    /// semantic::check(r#"
    ///   let a: null & unknown
    ///   //  ^? null
    /// "#);
    /// ```
    fn get_intersection_type(&mut self, types: &[TypeId]) -> TypeId {
        let mut type_membership_map: FxHashMap<TypeId, TypeId> = FxHashMap::default();
        let includes =
            self.add_types_to_intersection(&mut type_membership_map, TypeFlags::default(), types);
        let type_set: Vec<TypeId> = type_membership_map.values().copied().collect();
        if includes.intersects(TypeFlags::Never) {
            return if type_set.contains(&self.types.silent_never_type_id) {
                self.types.silent_never_type_id
            } else {
                self.types.never_type_id
            };
        }
        if self.options.strict_null_checks
            && includes.intersects(includes & TypeFlags::Nullable)
            && includes.intersects(
                TypeFlags::Object | TypeFlags::NonPrimitive | TypeFlags::IncludesEmptyObject,
            )
            || includes.intersects(includes & TypeFlags::NonPrimitive)
                && includes.intersects(TypeFlags::DisjointDomains - TypeFlags::NonPrimitive)
            || includes.intersects(includes & TypeFlags::StringLike)
                && includes.intersects(TypeFlags::DisjointDomains - TypeFlags::StringLike)
            || includes.intersects(includes & TypeFlags::NumberLike)
                && includes.intersects(TypeFlags::DisjointDomains - TypeFlags::NumberLike)
            || includes.intersects(includes & TypeFlags::BigIntLike)
                && includes.intersects(TypeFlags::DisjointDomains - TypeFlags::BigIntLike)
            || includes.intersects(includes & TypeFlags::ESSymbolLike)
                && includes.intersects(TypeFlags::DisjointDomains - TypeFlags::ESSymbolLike)
            || includes.intersects(includes & TypeFlags::VoidLike)
                && includes.intersects(TypeFlags::DisjointDomains - TypeFlags::VoidLike)
        {
            return self.types.never_type_id;
        }
        if includes.intersects(TypeFlags::Any) {
            return if includes.intersects(TypeFlags::IncludesWildcard) {
                self.types.wildcard_type_id
            } else {
                self.types.any_type_id
            };
        } else if !self.options.strict_null_checks && includes.intersects(TypeFlags::Nullable) {
            return if includes.intersects(TypeFlags::IncludesEmptyObject) {
                self.types.never_type_id
            } else if includes.intersects(TypeFlags::Undefined) {
                self.types.undefined_type_id
            } else {
                self.types.null_type_id
            };
        }
        if type_set.is_empty() {
            return self.types.unknown_type_id;
        }
        if type_set.len() == 1 {
            return type_set[0];
        }
        self.types.any_type_id
    }

    // Add the given types to the given type set. Order is preserved, duplicates are removed,
    // and nested types of the given kind are flattened into the set.
    fn add_types_to_union(
        &self,
        type_set: &mut Vec<TypeId>,
        includes: TypeFlags,
        types: &[TypeId],
    ) -> TypeFlags {
        types.iter().fold(includes, |includes, type_id| {
            self.add_type_to_union(type_set, includes, *type_id)
        })
    }

    fn add_type_to_union(
        &self,
        type_set: &mut Vec<TypeId>,
        includes: TypeFlags,
        type_id: TypeId,
    ) -> TypeFlags {
        let ty = &self.types[type_id];
        let flags = ty.flags;
        if flags.intersects(TypeFlags::Union) {
            let includes = includes
                | if ty.is_named_union_type() { TypeFlags::Union } else { TypeFlags::empty() };
            let types = match &ty.kind {
                TypeKind::UnionType(ty) => &ty.types,
                _ => unreachable!(),
            };
            return self.add_types_to_union(type_set, includes, types);
        }
        let mut includes = includes;
        // We ignore 'never' types in unions
        if !flags.intersects(TypeFlags::Never) {
            includes |= flags & TypeFlags::IncludesMask;
            if flags.intersects(TypeFlags::Instantiable) {
                includes |= TypeFlags::IncludesInstantiable;
            }
            if type_id == self.types.wildcard_type_id {
                includes |= TypeFlags::IncludesWildcard;
            };
            if !self.options.strict_null_checks && flags.intersects(TypeFlags::Nullable) {
                if !ty.get_object_flags().intersects(ObjectFlags::ContainsWideningType) {
                    includes |= TypeFlags::IncludesNonWideningType;
                }
            } else {
                match type_set.binary_search(&type_id) {
                    Ok(_) => {}
                    Err(pos) => type_set.insert(pos, type_id),
                }
            }
        }
        includes
    }

    // Add the given types to the given type set. Order is preserved, freshness is removed from literal
    // types, duplicates are removed, and nested types of the given kind are flattened into the set.
    fn add_types_to_intersection(
        &mut self,
        type_set: &mut FxHashMap<TypeId, TypeId>,
        includes: TypeFlags,
        types: &[TypeId],
    ) -> TypeFlags {
        types.iter().fold(includes, |includes, type_id| {
            let regular_type_id = self.get_regular_type_of_literal_type(*type_id);
            self.add_type_to_intersection(type_set, includes, regular_type_id)
        })
    }

    fn add_type_to_intersection(
        &mut self,
        type_set: &mut FxHashMap<TypeId, TypeId>,
        includes: TypeFlags,
        type_id: TypeId,
    ) -> TypeFlags {
        let mut includes = includes;
        let flags = self.types[type_id].flags;
        if flags.intersects(TypeFlags::AnyOrUnknown) {
            if type_id == self.types.wildcard_type_id {
                includes |= TypeFlags::IncludesWildcard;
            }
        } else if self.options.strict_null_checks || !flags.intersects(TypeFlags::Nullable) {
            type_set.entry(type_id).or_insert_with(|| {
                if flags.intersects(TypeFlags::Unit) && includes.intersects(TypeFlags::Unit) {
                    includes |= TypeFlags::NonPrimitive;
                }
                type_id
            });
        }
        includes |= flags & TypeFlags::IncludesMask;
        includes
    }

    fn remove_redundant_literal_types(
        &self,
        types: &[TypeId],
        includes: TypeFlags,
        reduce_void_undefined: bool,
    ) -> Vec<TypeId> {
        types
            .iter()
            .copied()
            .filter(|type_id| {
                let ty = &self.types[*type_id];
                let flags = ty.flags;
                let remove = flags.intersects(
                    TypeFlags::StringLiteral
                        | TypeFlags::TemplateLiteral
                        | TypeFlags::StringMapping,
                ) && includes.intersects(TypeFlags::String)
                    || flags.intersects(TypeFlags::NumberLiteral)
                        && includes.intersects(TypeFlags::Number)
                    || flags.intersects(TypeFlags::BigIntLiteral)
                        && includes.intersects(TypeFlags::BigInt)
                    || flags.intersects(TypeFlags::UniqueESSymbol)
                        && includes.intersects(TypeFlags::ESSymbol)
                    || reduce_void_undefined
                        && flags.intersects(TypeFlags::Undefined)
                        && includes.intersects(TypeFlags::Void)
                    || ty.is_fresh_literal_type()
                        && types.contains(&ty.get_regular_type().unwrap());
                !remove
            })
            .collect()
    }

    fn get_optional_type(&mut self, type_id: TypeId) -> TypeId {
        let r#type = &self.types[type_id];
        if r#type.flags.intersects(TypeFlags::Undefined) {
            type_id
        } else {
            self.get_union_type(&[type_id, self.types.undefined_type_id], UnionReduction::None)
        }
    }

    fn add_optionality(&mut self, type_id: TypeId, is_optional: bool) -> TypeId {
        if is_optional { self.get_optional_type(type_id) } else { type_id }
    }

    fn get_widened_type_for_variable_like_declaration(
        &mut self,
        decl: VariableLikeDeclaration<'a>,
    ) -> TypeId {
        let type_id = self.get_type_for_variable_like_declaration(decl);
        self.widen_type_for_variable_like_declaration(type_id)
    }

    fn widen_type_for_variable_like_declaration(&mut self, type_id: TypeId) -> TypeId {
        self.get_widened_type(type_id)
    }

    /// ```
    /// semantic::check(r#"
    ///   for (let i in x) {}
    ///   //       ^? string
    ///   for (let i = 1 in x) {}
    ///   //       ^? string
    /// "#);
    /// ```
    fn get_type_for_variable_like_declaration(
        &mut self,
        decl: VariableLikeDeclaration<'a>,
    ) -> TypeId {
        if matches!(decl, VariableLikeDeclaration::VariableDeclarator(_)) {
            // A variable declared in a for..in statement is of type string, or of type keyof T when the
            // right hand expression is of a type parameter type.
            let ast_node = &self.nodes[*self.span_to_node[&decl.node().range()]];
            for (i, node_id) in self.nodes.node_ancestors(ast_node).enumerate() {
                let kind = self.nodes.kind(node_id);
                if matches!(kind, AstKind::ForInStatement(_)) {
                    return self.types.string_type_id;
                }
                if i > 3 || matches!(kind, AstKind::BlockStatement(_)) {
                    break;
                }
            }
        }

        // Use type from type annotation if one is present
        if let Some(type_annotation) = decl.type_annotation() {
            let declared_type = self.get_type_from_type_node(&type_annotation.type_annotation);
            return self.add_optionality(declared_type, decl.optional());
        }

        if let VariableLikeDeclaration::VariableDeclarator(decl) = decl {
            if decl.init.is_some() {
                let type_id = self.check_declaration_initializer(decl);
                return self.widen_type_inferred_from_initializer(decl, type_id);
            }
        }

        self.types.any_type_id
    }

    fn get_quick_type_of_expression(&mut self, expression: &'a Expression<'a>) -> Option<TypeId> {
        match expression {
            Expression::CallExpression(expr)
                if !matches!(expr.callee, Expression::Super(_))
                    && !expr.is_require_call()
                    && !expr.is_symbol_or_symbol_for_call() =>
            {
                None
            }
            Expression::TSAsExpression(expr) if !expr.type_annotation.is_const_type_reference() => {
                Some(self.get_type_from_type_node(&expr.type_annotation))
            }
            Expression::TSTypeAssertion(expr) => {
                Some(self.get_type_from_type_node(&expr.type_annotation))
            }
            Expression::ParenthesizedExpression(expr) => {
                self.get_quick_type_of_expression(&expr.expression)
            }
            expr if expr.is_literal_expression() => Some(self.check_expression(expr)),
            _ => None,
        }
    }

    /// ```
    /// semantic::check(r#"
    ///   let x = 1;
    ///   //  ^? number
    ///   const y = -3n;
    ///   // .  ^? bigint
    /// "#);
    /// ```
    fn get_literal_type(&mut self, value: LiteralValue, flags: TypeFlags) -> TypeId {
        self.types
            .literal_values
            .get(&value)
            .copied()
            .unwrap_or_else(|| self.types.create_literal_type(flags, value, None, None))
    }

    fn get_fresh_type_of_literal_type(&mut self, type_id: TypeId) -> TypeId {
        let ty = &self.types[type_id];
        if let TypeKind::LiteralType(lit) = &ty.kind {
            return if lit.fresh_type == TypeId::new(1) {
                let fresh_type_id = self.types.create_literal_type(
                    ty.flags,
                    lit.value.clone(),
                    ty.symbol_id,
                    Some(type_id),
                );
                self.types[fresh_type_id].set_fresh_type(fresh_type_id);
                self.types[type_id].set_fresh_type(fresh_type_id);
                fresh_type_id
            } else {
                lit.fresh_type
            };
        }
        type_id
    }

    fn get_regular_type_of_literal_type(&self, type_id: TypeId) -> TypeId {
        match &self.types[type_id].kind {
            TypeKind::LiteralType(lit) => lit.regular_type,
            // TODO: type.flags & TypeFlags.Union ? ((type as UnionType).regularType || ((type as UnionType).regularType = mapType(type, getRegularTypeOfLiteralType) as UnionType)) :
            _ => type_id,
        }
    }

    fn get_widened_type(&mut self, type_id: TypeId) -> TypeId {
        self.get_widened_type_with_context(type_id, None)
    }

    /// ```
    /// semantic::check(r#"
    ///   let a = null;
    ///   //  ^? any
    ///   let b = []
    ///   //  ^? any[]
    /// "#);
    /// ```
    #[allow(clippy::if_same_then_else)]
    fn get_widened_type_with_context(
        &mut self,
        type_id: TypeId,
        context: Option<WideningContext>,
    ) -> TypeId {
        let ty = &self.types[type_id];
        let flags = ty.flags;
        let object_flags = ty.get_object_flags();
        if object_flags.intersects(ObjectFlags::RequiresWidening) {
            if context.is_none() {
                if let Some(widened_type_id) = ty.widened {
                    return widened_type_id;
                }
            }
            let result = if flags.intersects(TypeFlags::Any | TypeFlags::Nullable) {
                Some(self.types.any_type_id)
            } else if self.types.is_object_literal_type(ty) {
                // result = getWidenedTypeOfObjectLiteral(type, context);
                Some(self.types.any_type_id)
            } else if flags.intersects(TypeFlags::Union) {
                // const unionContext = context || createWideningContext([>parent*/ undefined, /*propertyName<] undefined, (type as UnionType).types);
                // const widenedTypes = sameMap((type as UnionType).types, t => t.flags & TypeFlags.Nullable ? t : getWidenedTypeWithContext(t, unionContext));
                // result = getUnionType(widenedTypes, some(widenedTypes, isEmptyObjectType) ? UnionReduction.Subtype : UnionReduction.Literal);
                Some(self.types.any_type_id)
            } else if flags.intersects(TypeFlags::Intersection) {
                // result = getIntersectionType(sameMap((type as IntersectionType).types, getWidenedType));
                Some(self.types.any_type_id)
            } else if self.types.is_array_or_tuple_type(ty) {
                let (target, resolved_type_arguments) = match &ty.kind {
                    TypeKind::ObjectType(object_type) => {
                        (object_type.target, object_type.resolved_type_arguments.clone())
                    }
                    _ => unreachable!(),
                };
                // TODO: getTypeArgument
                // result = createTypeReference(type.target, sameMap(getTypeArguments(type), getWidenedType));
                let type_arguments = resolved_type_arguments
                    .iter()
                    .map(|type_id| self.get_widened_type(*type_id))
                    .collect();
                Some(self.types.create_type_reference(target, type_arguments))
            } else {
                None
            };
            if result.is_some() && context.is_none() {
                self.types[type_id].widened = result;
            }
            result.unwrap_or(type_id)
        } else {
            type_id
        }
    }

    fn get_widened_literal_like_type_for_contextual_type(
        &mut self,
        type_id: TypeId,
        _contextual_type_id: Option<TypeId>,
    ) -> TypeId {
        // if (!isLiteralOfContextualType(type, contextualType)) {
        let type_id = self.get_widened_literal_type(type_id);
        // }

        self.get_regular_type_of_literal_type(type_id)
    }

    fn get_widened_literal_type(&self, type_id: TypeId) -> TypeId {
        let ty = &self.types[type_id];
        let flags = ty.flags;
        let is_fresh_literal_type = ty.is_fresh_literal_type();
        // TODO: type.flags & TypeFlags.EnumLiteral && isFreshLiteralType(type) ? getBaseTypeOfEnumLiteralType(type as LiteralType) :
        // TODO: type.flags & TypeFlags.Union ? mapType(type as UnionType, getWidenedLiteralType) :
        if flags.intersects(TypeFlags::StringLiteral) && is_fresh_literal_type {
            self.types.string_type_id
        } else if flags.intersects(TypeFlags::NumberLiteral) && is_fresh_literal_type {
            self.types.number_type_id
        } else if flags.intersects(TypeFlags::BigIntLiteral) && is_fresh_literal_type {
            self.types.bigint_type_id
        } else if flags.intersects(TypeFlags::BooleanLiteral) && is_fresh_literal_type {
            self.types.boolean_type_id
        } else {
            type_id
        }
    }

    fn get_widened_literal_like_type_for_contextual_return_type_if_needed(
        &mut self,
        type_id: TypeId,
        _contextual_type_id: Option<TypeId>,
        _is_async: bool,
    ) -> TypeId {
        if self.types[type_id].is_unit_type() {
            // const contextualType = !contextualSignatureReturnType ? undefined :
            // isAsync ? getPromisedTypeOfPromise(contextualSignatureReturnType) :
            // contextualSignatureReturnType;
            return self.get_widened_literal_like_type_for_contextual_type(type_id, None);
        }
        type_id
    }

    fn get_unary_result_type(&mut self, _operand_type: TypeId) -> TypeId {
        self.types.number_type_id
    }

    fn get_narrowed_type_of_symbol(
        &mut self,
        symbol_id: SymbolId,
        _location: &IdentifierReference,
    ) -> TypeId {
        self.get_type_of_symbol(symbol_id)
    }

    fn widen_type_inferred_from_initializer(
        &self,
        decl: &VariableDeclarator<'a>,
        t: TypeId,
    ) -> TypeId {
        if decl.kind == VariableDeclarationKind::Const {
            t
        } else {
            self.get_widened_literal_type(t)
        }
    }

    #[must_use]
    fn get_type_from_type_node(&mut self, ty: &'a TSType<'a>) -> TypeId {
        self.get_type_from_type_node_worker(ty)
    }

    #[must_use]
    #[allow(clippy::match_same_arms)]
    fn get_type_from_type_node_worker(&mut self, ty: &'a TSType<'a>) -> TypeId {
        match ty {
            // Keyword
            TSType::TSAnyKeyword(_) => self.types.any_type_id,
            TSType::TSBigIntKeyword(_) => self.types.bigint_type_id,
            TSType::TSBooleanKeyword(_) => self.types.boolean_type_id,
            TSType::TSNeverKeyword(_) => self.types.never_type_id,
            TSType::TSNullKeyword(_) => self.types.null_widening_type_id,
            TSType::TSNumberKeyword(_) => self.types.number_type_id,
            TSType::TSObjectKeyword(_) => self.types.non_primitive_type_id,
            TSType::TSStringKeyword(_) => self.types.string_type_id,
            TSType::TSSymbolKeyword(_) => self.types.es_symbol_type_id,
            TSType::TSThisKeyword(node) => self.get_type_from_this_type_node(node),
            TSType::TSUndefinedKeyword(_) => self.types.undefined_type_id,
            TSType::TSUnknownKeyword(_) => self.types.unknown_type_id,
            TSType::TSVoidKeyword(_) => self.types.void_type_id,
            // Compound
            TSType::TSArrayType(node) => self.get_type_from_array_type_node(node),
            TSType::TSConditionalType(node) => self.get_type_from_conditional_type_node(node),
            TSType::TSConstructorType(_) => self.types.any_type_id,
            TSType::TSFunctionType(_) => self.types.any_type_id,
            TSType::TSImportType(node) => self.get_type_from_import_type_node(node),
            TSType::TSIndexedAccessType(node) => self.get_type_from_indexed_access_type_node(node),
            TSType::TSInferType(node) => self.get_type_from_infer_type_node(node),
            TSType::TSIntersectionType(node) => self.get_type_from_intersection_type_node(node),
            TSType::TSLiteralType(node) => self.get_type_from_literal_type_node(node),
            TSType::TSMappedType(node) => self.get_type_from_mapped_type_node(node),
            TSType::TSQualifiedName(_) => self.types.any_type_id,
            TSType::TSTemplateLiteralType(_) => self.types.string_type_id,
            TSType::TSTupleType(node) => self.get_type_from_tuple_type_node(node),
            TSType::TSTypeLiteral(_) => self.types.any_type_id,
            TSType::TSTypeOperatorType(node) => self.get_type_from_type_operator_type_node(node),
            TSType::TSTypePredicate(predicate) => {
                if predicate.asserts {
                    self.types.void_type_id
                } else {
                    self.types.boolean_type_id
                }
            }
            TSType::TSTypeQuery(query) => self.get_type_from_type_query_node(query),
            TSType::TSTypeReference(reference) => self.get_type_from_type_reference(reference),
            TSType::TSUnionType(union) => self.get_type_from_union_type_node(union),
            TSType::JSDocNullableType(_) => self.types.any_type_id,
            TSType::JSDocUnknownType(_) => self.types.unknown_type_id,
        }
    }

    fn get_type_from_this_type_node(&mut self, _node: &TSThisKeyword) -> TypeId {
        self.types.any_type_id
    }

    /// ```
    /// semantic::check(r#"
    /// let a: any[] = []
    /// //  ^? any[]
    /// "#);
    /// ```
    fn get_type_from_array_type_node(&mut self, ty: &'a TSArrayType<'a>) -> TypeId {
        self.with_resolved_type(ty.node.range(), |builder| {
            let target = builder.types.global_array_type_id;
            let type_arguments = vec![builder.get_type_from_type_node(&ty.element_type)];
            builder.types.create_type_reference(target, type_arguments)
        })
    }

    fn get_type_from_conditional_type_node(&mut self, _node: &TSConditionalType<'a>) -> TypeId {
        self.types.any_type_id
    }

    fn get_type_from_import_type_node(&mut self, _node: &TSImportType<'a>) -> TypeId {
        self.types.any_type_id
    }

    fn get_type_from_indexed_access_type_node(
        &mut self,
        _node: &TSIndexedAccessType<'a>,
    ) -> TypeId {
        self.types.any_type_id
    }

    fn get_type_from_infer_type_node(&mut self, _node: &TSInferType<'a>) -> TypeId {
        self.types.any_type_id
    }

    fn get_type_from_intersection_type_node(&mut self, ty: &'a TSIntersectionType<'a>) -> TypeId {
        self.with_resolved_type(ty.node.range(), |builder| {
            let types = ty
                .types
                .iter()
                .map(|type_id| builder.get_type_from_type_node(type_id))
                .collect::<Vec<_>>();
            builder.get_intersection_type(&types)
        })
    }

    fn get_type_from_literal_type_node(&mut self, literal: &'a TSLiteralType<'a>) -> TypeId {
        self.with_resolved_type(literal.node.range(), |builder| {
            let literal_type = match &literal.literal {
                TSLiteral::NullLiteral(_) => builder.types.null_type_id,
                TSLiteral::BooleanLiteral(lit) => builder.check_boolean_literal(lit.value),
                TSLiteral::StringLiteral(lit) => builder.check_string_literal(&lit.value),
                TSLiteral::NumberLiteral(lit) => builder.check_number_literal(*lit.value),
                TSLiteral::BigintLiteral(lit) => builder.check_bigint_literal(&lit.value),
                TSLiteral::TemplateLiteral(lit) => builder.check_templatei_literal(lit),
                TSLiteral::RegExpLiteral(_) => builder.check_regexp_literal(),
                TSLiteral::UnaryExpression(unary_expr) => {
                    builder.check_unary_expression(unary_expr)
                }
            };

            builder.get_fresh_type_of_literal_type(literal_type)
        })
    }

    fn get_type_from_mapped_type_node(&mut self, _node: &TSMappedType<'a>) -> TypeId {
        self.types.any_type_id
    }

    fn get_type_from_tuple_type_node(&mut self, _node: &TSTupleType<'a>) -> TypeId {
        self.types.any_type_id
    }

    /// ```
    /// semantic::check(r#"
    /// let a: 1 | string = "s";
    /// //  ^? string | 1
    /// "#);
    /// ```
    fn get_type_from_union_type_node(&mut self, union: &'a TSUnionType<'a>) -> TypeId {
        self.with_resolved_type(union.node.range(), |builder| {
            let types =
                union.types.iter().map(|t| builder.get_type_from_type_node(t)).collect::<Vec<_>>();
            builder.get_union_type(&types, UnionReduction::Literal)
        })
    }

    fn get_type_from_type_operator_type_node(&mut self, _node: &TSTypeOperatorType<'a>) -> TypeId {
        self.types.any_type_id
    }

    fn get_type_from_type_query_node(&mut self, query: &'a TSTypeQuery<'a>) -> TypeId {
        self.with_resolved_type(query.node.range(), |builder| {
            let type_id = builder.check_expression_with_type_arguments(
                ExpressionWithTypeArguments::TSTypeQuery(query),
            );
            let widened_type = builder.get_widened_type(type_id);
            builder.get_regular_type_of_literal_type(widened_type)
        })
    }

    /// ```
    /// semantic::check(r#"
    /// let a: Promise<any> = "s";
    /// //  ^? Promise
    /// "#);
    /// ```
    fn get_type_from_type_reference(&mut self, reference: &TSTypeReference<'a>) -> TypeId {
        self.with_resolved_type(reference.node.range(), |builder| {
            // TODO handle `x as const`
            let symbol_id = builder.resolve_type_reference_name(reference);
            builder.get_type_reference_type(reference, symbol_id)
        })
    }

    fn get_resolved_signature(&mut self, call: CallLikeExpression<'a>) -> SignatureId {
        let span = call.node().range();
        if let Some(resolved) = self.get_node_links(span.clone()).resolved_signature {
            return resolved;
        }
        let signature_id = self.resolve_signature(call);
        self.get_node_links(span).resolved_signature.replace(signature_id);
        signature_id
    }

    /// ```
    /// semantic::check(r#"
    ///   function x(): number {};
    ///   const a = x();
    ///   //    ^? number
    ///
    ///   function y(): Promise<number> {};
    ///   const b = y();
    ///   //    ^? Promise
    /// "#);
    /// ```
    fn get_return_type_of_annotation(&mut self, decl_id: AstNodeId) -> Option<TypeId> {
        let kind = self.nodes[decl_id];
        match kind.kind {
            AstKind::Function(func) => func.return_type.as_ref(),
            AstKind::ArrowExpression(arrow) => arrow.return_type.as_ref(),
            _ => None,
        }
        .map(|annotation| self.get_type_from_type_node(&annotation.type_annotation))
    }

    /// ```
    /// semantic::check(r#"
    ///   function x() { return 3 };
    ///   const a = x();
    ///   //    ^? number
    ///   async function y() { return 3 };
    ///   const b = y();
    ///   //    ^? Promise
    ///   let c = () => 0;
    ///   //  ^? () => number
    /// "#);
    /// ```
    fn get_return_type_from_body(&mut self, decl_id: AstNodeId) -> TypeId {
        let (is_async, body, is_expression_body) = match self.nodes[decl_id].kind {
            AstKind::Function(func) => (func.r#async, func.body.as_ref(), false),
            AstKind::ArrowExpression(arrow) => (arrow.r#async, Some(&arrow.body), arrow.expression),
            _ => unreachable!(),
        };

        let Some(body) = body else {
            return self.types.error_type_id;
        };

        let fallback_return_type = self.types.void_type_id;

        let mut return_type: Option<TypeId> = None;

        // () => 0
        if is_expression_body {
            if let Some(Statement::ExpressionStatement(expr)) = body.statements.get(0) {
                return_type.replace(self.check_expression_cached(&expr.expression));
            }
        // function foo() { return 0 }
        } else if let Some(return_types) = self.check_and_aggregate_return_expression_types(body) {
            if return_types.is_empty() {
                return if is_async {
                    self.types.create_promise_type(self.types.void_type_id)
                } else {
                    self.types.void_type_id
                };
            }
            return_type.replace(self.get_union_type(&return_types, UnionReduction::Subtype));
        } else {
            return if is_async {
                self.types.create_promise_type(self.types.never_type_id)
            } else {
                self.types.never_type_id
            };
        }

        if let Some(return_type_id) = return_type {
            let mut return_type_id = return_type_id;
            if self.types[return_type_id].is_unit_type() {
                return_type_id = self
                    .get_widened_literal_like_type_for_contextual_return_type_if_needed(
                        return_type_id,
                        None,
                        is_async,
                    );
            }
            return_type.replace(self.get_widened_type(return_type_id));
        }

        let return_type = return_type.unwrap_or(fallback_return_type);
        if is_async { self.types.create_promise_type(return_type) } else { return_type }
    }

    /// ```
    /// semantic::check(r#"
    /// function fib(x:number) { return x <= 1 ? x : fib(x - 1) + fib(x - 2); }
    /// var result = fib(5);
    /// "#);
    /// ```
    #[allow(clippy::useless_let_if_seq)]
    fn get_return_type_of_signature(&mut self, signature_id: SignatureId) -> TypeId {
        if let Some(resolved_type_id) = self.signatures[signature_id].resolved_return_type {
            return resolved_type_id;
        }
        if !self.push_type_resolution(TypeSystemEntity::ResolvedReturnType(signature_id)) {
            return self.types.error_type_id;
        }
        let signature = &self.signatures[signature_id];
        let mut type_id = signature.declaration.map_or(self.types.any_type_id, |decl_id| {
            self.get_return_type_of_annotation(decl_id)
                .unwrap_or_else(|| self.get_return_type_from_body(decl_id))
        });
        if !self.pop_type_resolution() {
            type_id = self.types.any_type_id;
        }
        self.signatures[signature_id].resolved_return_type.replace(type_id);
        type_id
    }

    fn get_signatures_of_type(&mut self, type_id: TypeId) -> Vec<SignatureId> {
        let type_id = self.resolve_structured_type_members(type_id);
        match &self.types[type_id].kind {
            TypeKind::ObjectType(object_type) => object_type.call_signatures.clone(),
            _ => vec![],
        }
    }

    fn get_type_facts(&self, type_id: TypeId) -> TypeFacts {
        let mut type_id = type_id;
        let flags = self.types[type_id].flags;
        if flags.intersects(TypeFlags::Intersection | TypeFlags::Instantiable) {
            type_id =
                self.get_base_constraint_of_type(type_id).unwrap_or(self.types.unknown_type_id);
        }
        let ty = &self.types[type_id];
        let flags = ty.flags;
        let strict_null_checks = self.options.strict_null_checks;
        if flags.intersects(TypeFlags::String | TypeFlags::StringMapping) {
            return if strict_null_checks {
                TypeFacts::StringStrictFacts
            } else {
                TypeFacts::StringFacts
            };
        }
        if flags.intersects(TypeFlags::StringLiteral | TypeFlags::TemplateLiteral) {
            return match (strict_null_checks, ty.is_zero()) {
                (true, true) => TypeFacts::EmptyStringStrictFacts,
                (true, false) => TypeFacts::NonEmptyStringStrictFacts,
                (false, true) => TypeFacts::EmptyStringFacts,
                (false, false) => TypeFacts::NonEmptyStringFacts,
            };
        }
        if flags.intersects(TypeFlags::Number | TypeFlags::Enum) {
            return if strict_null_checks {
                TypeFacts::NumberStrictFacts
            } else {
                TypeFacts::NumberFacts
            };
        }
        if flags.intersects(TypeFlags::NumberLiteral) {
            return match (strict_null_checks, ty.is_zero()) {
                (true, true) => TypeFacts::ZeroNumberStrictFacts,
                (true, false) => TypeFacts::NonZeroNumberStrictFacts,
                (false, true) => TypeFacts::ZeroNumberFacts,
                (false, false) => TypeFacts::NonZeroNumberFacts,
            };
        }
        if flags.intersects(TypeFlags::BigInt) {
            return if strict_null_checks {
                TypeFacts::BigIntStrictFacts
            } else {
                TypeFacts::BigIntFacts
            };
        }
        if flags.intersects(TypeFlags::BigIntLiteral) {
            return match (strict_null_checks, ty.is_zero()) {
                (true, true) => TypeFacts::ZeroBigIntStrictFacts,
                (true, false) => TypeFacts::NonZeroBigIntStrictFacts,
                (false, true) => TypeFacts::ZeroBigIntFacts,
                (false, false) => TypeFacts::NonZeroBigIntFacts,
            };
        }
        if flags.intersects(TypeFlags::Boolean) {
            return if strict_null_checks {
                TypeFacts::BooleanStrictFacts
            } else {
                TypeFacts::BooleanFacts
            };
        }
        if flags.intersects(TypeFlags::BooleanLike) {
            let is_falsy =
                type_id == self.types.false_type_id || type_id == self.types.regular_false_type_id;
            return match (strict_null_checks, is_falsy) {
                (true, true) => TypeFacts::FalseStrictFacts,
                (true, false) => TypeFacts::TrueStrictFacts,
                (false, true) => TypeFacts::FalseFacts,
                (false, false) => TypeFacts::TrueFacts,
            };
        }
        // if flags.intersects(TypeFlags::Object) {
        // return getObjectFlags(type) & ObjectFlags.Anonymous && isEmptyObjectType(type as ObjectType) ?
        // strict_null_checks ? TypeFacts::EmptyObjectStrictFacts : TypeFacts::EmptyObjectFacts :
        // isFunctionObjectType(type as ObjectType) ?
        // strict_null_checks ? TypeFacts::FunctionStrictFacts : TypeFacts::FunctionFacts :
        // strict_null_checks ? TypeFacts::ObjectStrictFacts : TypeFacts::ObjectFacts;
        // }
        if flags.intersects(TypeFlags::Void) {
            return TypeFacts::VoidFacts;
        }
        if flags.intersects(TypeFlags::Undefined) {
            return TypeFacts::UndefinedFacts;
        }
        if flags.intersects(TypeFlags::Null) {
            return TypeFacts::NullFacts;
        }
        if flags.intersects(TypeFlags::ESSymbolLike) {
            return if strict_null_checks {
                TypeFacts::SymbolStrictFacts
            } else {
                TypeFacts::SymbolFacts
            };
        }
        if flags.intersects(TypeFlags::NonPrimitive) {
            return if strict_null_checks {
                TypeFacts::ObjectStrictFacts
            } else {
                TypeFacts::ObjectFacts
            };
        }
        if flags.intersects(TypeFlags::Never) {
            return TypeFacts::None;
        }
        // if flags.intersects(TypeFlags::Union) {
        // return reduceLeft((type as UnionType).types, (facts, t) => facts | getTypeFacts::t), TypeFacts::None);
        // }
        // if flags.intersects(TypeFlags::Intersection) {
        // return getIntersectionTypeFacts::type as IntersectionType);
        // }
        TypeFacts::UnknownFacts
    }

    fn get_type_with_facts(&mut self, type_id: TypeId, include: TypeFacts) -> TypeId {
        self.filter_type(type_id, |builder, type_id| {
            builder.get_type_facts(type_id).intersects(include)
        })
    }

    // This function is similar to getTypeWithFacts, except that in strictNullChecks mode it replaces type
    // unknown with the union {} | null | undefined (and reduces that accordingly), and it intersects remaining
    // instantiable types with {}, {} | null, or {} | undefined in order to remove null and/or undefined.
    fn get_adjusted_type_with_facts(&mut self, type_id: TypeId, facts: TypeFacts) -> TypeId {
        let strict_null_checks = self.options.strict_null_checks;
        let ty = &self.types[type_id];
        let type_id = self.get_type_with_facts(
            if strict_null_checks && ty.flags.intersects(TypeFlags::Unknown) {
                self.types.unknown_union_type_id
            } else {
                type_id
            },
            facts,
        );
        let reduced = self.recombine_unknown_type(type_id);
        if strict_null_checks {
            match facts {
                TypeFacts::NEUndefined => {
                    return self.map_type(
                        reduced,
                        |builder, type_id| {
                            if builder.get_type_facts(type_id).intersects(TypeFacts::EQUndefined) {
                                let type_id2 = if builder
                                    .get_type_facts(type_id)
                                    .intersects(TypeFacts::EQNull)
                                    && !builder.maybe_type_of_kind(reduced, TypeFlags::Null)
                                {
                                    builder.get_union_type(
                                        &[
                                            builder.types.empty_object_type_id,
                                            builder.types.null_type_id,
                                        ],
                                        UnionReduction::Literal,
                                    )
                                } else {
                                    builder.types.empty_object_type_id
                                };
                                builder.get_intersection_type(&[type_id, type_id2])
                            } else {
                                type_id
                            }
                        },
                        false,
                    );
                }
                TypeFacts::NENull => {
                    return self.map_type(
                        reduced,
                        |builder, type_id| {
                            if builder.get_type_facts(type_id).intersects(TypeFacts::EQNull) {
                                let type_id2 = if builder
                                    .get_type_facts(type_id)
                                    .intersects(TypeFacts::EQUndefined)
                                    && !builder.maybe_type_of_kind(reduced, TypeFlags::Undefined)
                                {
                                    builder.get_union_type(
                                        &[
                                            builder.types.empty_object_type_id,
                                            builder.types.undefined_type_id,
                                        ],
                                        UnionReduction::Literal,
                                    )
                                } else {
                                    builder.types.empty_object_type_id
                                };
                                builder.get_intersection_type(&[type_id, type_id2])
                            } else {
                                type_id
                            }
                        },
                        false,
                    );
                }
                TypeFacts::NEUndefinedOrNull | TypeFacts::Truthy => {
                    return self.map_type(
                        reduced,
                        |builder, type_id| {
                            if builder
                                .get_type_facts(type_id)
                                .intersects(TypeFacts::EQUndefinedOrNull)
                            {
                                builder.get_global_non_nullable_type_instantiation(type_id)
                            } else {
                                type_id
                            }
                        },
                        false,
                    );
                }
                _ => {}
            }
        }
        reduced
    }

    #[allow(clippy::unused_self)]
    const fn get_global_non_nullable_type_instantiation(&self, type_id: TypeId) -> TypeId {
        type_id
        // if (!deferredGlobalNonNullableTypeAlias) {
        // deferredGlobalNonNullableTypeAlias = getGlobalSymbol("NonNullable" as __String, SymbolFlags.TypeAlias, [>diagnostic<] undefined) || unknownSymbol;
        // }
        // return deferredGlobalNonNullableTypeAlias !== unknownSymbol ?
        // getTypeAliasInstantiation(deferredGlobalNonNullableTypeAlias, [type]) :
        // getIntersectionType([type, emptyObjectType]);
    }

    // Apply a mapping function to a type and return the resulting type. If the source type
    // is a union type, the mapping function is applied to each constituent type and a union
    // of the resulting types is returned.
    // function mapType(type: Type, mapper: (t: Type) => Type, noReductions?: boolean): Type;
    // function mapType(type: Type, mapper: (t: Type) => Type | undefined, noReductions?: boolean): Type | undefined;
    fn map_type<F>(&mut self, type_id: TypeId, mapper: F, _no_reductions: bool) -> TypeId
    where
        F: Fn(&mut Self, TypeId) -> TypeId,
    {
        let ty = &self.types[type_id];
        if ty.flags.intersects(TypeFlags::Never) {
            return type_id;
        }
        if ty.flags.intersects(TypeFlags::Union) {
            return mapper(self, type_id);
        }
        // const origin = (type as UnionType).origin;
        // const types = origin && origin.flags & TypeFlags.Union ? (origin as UnionType).types : (type as UnionType).types;
        // let mappedTypes: Type[] | undefined;
        // let changed = false;
        // for (const t of types) {
        // const mapped = t.flags & TypeFlags.Union ? mapType(t, mapper, noReductions) : mapper(t);
        // changed ||= t !== mapped;
        // if (mapped) {
        // if (!mappedTypes) {
        // mappedTypes = [mapped];
        // }
        // else {
        // mappedTypes.push(mapped);
        // }
        // }
        // }
        // return changed ? mappedTypes && getUnionType(mappedTypes, noReductions ? UnionReduction.None : UnionReduction.Literal) : type;
        type_id
    }

    fn filter_type<F>(&mut self, type_id: TypeId, f: F) -> TypeId
    where
        F: Fn(&Self, TypeId) -> bool,
    {
        let ty = &self.types[type_id];
        if let TypeKind::UnionType(union_type) = &ty.kind {
            let types = &union_type.types;
            let filtered =
                types.iter().copied().filter(|type_id| f(self, *type_id)).collect::<Vec<_>>();
            if filtered.iter().zip(types).all(|(a, b)| a == b) {
                return type_id;
            }
            // const origin = (type as UnionType).origin;
            // let newOrigin: Type | undefined;
            // if (origin && origin.flags & TypeFlags.Union) {
            // // If the origin type is a (denormalized) union type, filter its non-union constituents. If that ends
            // // up removing a smaller number of types than in the normalized constituent set (meaning some of the
            // // filtered types are within nested unions in the origin), then we can't construct a new origin type.
            // // Otherwise, if we have exactly one type left in the origin set, return that as the filtered type.
            // // Otherwise, construct a new filtered origin type.
            // const originTypes = (origin as UnionType).types;
            // const originFiltered = filter(originTypes, t => !!(t.flags & TypeFlags.Union) || f(t));
            // if (originTypes.length - originFiltered.length === types.length - filtered.length) {
            // if (originFiltered.length === 1) {
            // return originFiltered[0];
            // }
            // newOrigin = createOriginUnionOrIntersectionType(TypeFlags.Union, originFiltered);
            // }
            // }
            return self.get_union_type_from_sorted_list(&filtered, ty.get_object_flags());
        }
        if ty.flags.intersects(TypeFlags::Never) || f(self, type_id) {
            type_id
        } else {
            self.types.never_type_id
        }
    }

    fn remove_definitely_falsy_types(&mut self, type_id: TypeId) -> TypeId {
        self.filter_type(type_id, |builder, type_id| {
            builder.get_type_facts(type_id).intersects(TypeFacts::Truthy)
        })
    }

    fn extract_definitely_falsy_types(&mut self, type_id: TypeId) -> TypeId {
        self.map_type(
            type_id,
            |builder, type_id| builder.get_definitely_falsy_part_of_type(type_id),
            false,
        )
    }

    fn get_definitely_falsy_part_of_type(&self, type_id: TypeId) -> TypeId {
        let ty = &self.types[type_id];
        let flags = ty.flags;
        if flags.intersects(TypeFlags::String) {
            self.types.empty_string_type_id
        } else if flags.intersects(TypeFlags::Number) {
            self.types.zero_type_id
        } else if flags.intersects(TypeFlags::BigInt) {
            self.types.zero_big_int_type_id
        } else if type_id == self.types.regular_false_type_id
            || type_id == self.types.false_type_id
            || flags.intersects(
                TypeFlags::Void | TypeFlags::Undefined | TypeFlags::Null | TypeFlags::AnyOrUnknown,
            )
            || flags.intersects(
                TypeFlags::StringLiteral | TypeFlags::NumberLiteral | TypeFlags::BigIntLiteral,
            ) && ty.is_zero()
        {
            type_id
        } else {
            self.types.never_type_id
        }
    }

    // Return true if type might be of the given kind. A union or intersection type might be of a given
    // kind if at least one constituent type is of the given kind.
    fn maybe_type_of_kind(&self, type_id: TypeId, kind: TypeFlags) -> bool {
        let ty = &self.types[type_id];
        if ty.flags.intersects(kind) {
            return true;
        }
        if let TypeKind::UnionType(union) = &ty.kind {
            for type_id in &union.types {
                if self.maybe_type_of_kind(*type_id, kind) {
                    return true;
                }
            }
        }
        false
    }

    fn recombine_unknown_type(&self, type_id: TypeId) -> TypeId {
        if type_id == self.types.unknown_union_type_id {
            self.types.unknown_type_id
        } else {
            type_id
        }
    }

    #[allow(clippy::unused_self)]
    const fn get_base_constraint_of_type(&self, _type_id: TypeId) -> Option<TypeId> {
        None
    }

    fn get_non_nullable_type(&mut self, type_id: TypeId) -> TypeId {
        if self.options.strict_null_checks {
            self.get_adjusted_type_with_facts(type_id, TypeFacts::NEUndefinedOrNull)
        } else {
            type_id
        }
    }

    fn check_non_null_type(&mut self, type_id: TypeId) -> TypeId {
        let ty = &self.types[type_id];
        if self.options.strict_null_checks && ty.flags.intersects(TypeFlags::Unknown) {
            // if (isEntityNameExpression(node)) {
            // const nodeText = entityNameToString(node);
            // if (nodeText.length < 100) {
            // error(node, Diagnostics._0_is_of_type_unknown, nodeText);
            // }
            // error(node, Diagnostics.Object_is_of_type_unknown);
            return self.types.error_type_id;
        }
        let facts = self.get_type_facts(type_id);
        if facts.intersects(TypeFacts::IsUndefinedOrNull) {
            // reportError(node, facts);
            let type_id = self.get_non_nullable_type(type_id);
            let ty = &self.types[type_id];
            return if ty.flags.intersects(TypeFlags::Nullable | TypeFlags::Never) {
                self.types.error_type_id
            } else {
                type_id
            };
        }
        type_id
    }

    fn get_base_type_of_literal_type(&mut self, type_id: TypeId) -> TypeId {
        let flags = self.types[type_id].flags;
        if flags.intersects(TypeFlags::EnumLiteral) {
            // getBaseTypeOfEnumLiteralType(type as LiteralType)
            self.types.any_type_id
        } else if flags.intersects(
            TypeFlags::StringLiteral | TypeFlags::TemplateLiteral | TypeFlags::StringMapping,
        ) {
            self.types.string_type_id
        } else if flags.intersects(TypeFlags::NumberLiteral) {
            self.types.number_type_id
        } else if flags.intersects(TypeFlags::BigIntLiteral) {
            self.types.bigint_type_id
        } else if flags.intersects(TypeFlags::Union) {
            // getBaseTypeOfLiteralTypeUnion(type as UnionType)
            self.types.any_type_id
        } else {
            type_id
        }
    }
}

/// Type Check Methods
impl<'a> TypeBuilder<'a> {
    fn check_source_element(&mut self, kind: AstKind<'a>) {
        self.check_source_element_worker(kind);
    }

    fn check_source_element_worker(&mut self, kind: AstKind<'a>) {
        match kind {
            AstKind::Directive(directive) => self.check_directive(directive),
            AstKind::IdentifierReference(ident) => {
                self.check_identifier(ident);
            }
            AstKind::BindingIdentifier(ident) => self.check_binding_identifier(ident),
            AstKind::FormalParameter(param) => self
                .check_variable_like_declaration(VariableLikeDeclaration::FormalParameter(param)),
            AstKind::Class(class) if class.is_declaration() => {
                self.check_class_like_declaration(class);
            }
            AstKind::TSTypeAliasDeclaration(decl) => {
                // cache symbol name
                let symbol_id = self.symbols.get_symbol_id_of_span(&decl.node.range());
                self.get_declared_type_of_symbol(symbol_id);
            }
            AstKind::TSEnumDeclaration(decl) => {
                self.check_enum_declaration(decl);
            }
            AstKind::TSModuleDeclaration(decl) => {
                self.check_module_declaration(decl);
            }
            AstKind::TSPropertySignature(sig) => {
                self.check_variable_like_declaration(VariableLikeDeclaration::PropertySignature(
                    sig,
                ));
            }
            _ => {}
        }
    }

    fn check_expression_cached(&mut self, expr: &'a Expression<'a>) -> TypeId {
        self.with_resolved_type(expr.node().range(), |builder| builder.check_expression(expr))
    }

    fn check_expression(&mut self, expr: &'a Expression<'a>) -> TypeId {
        self.check_expression_worker(expr)
    }

    fn check_expression_for_mutable_location(&mut self, expr: &'a Expression<'a>) -> TypeId {
        let type_id = self.check_expression(expr);
        self.get_widened_literal_like_type_for_contextual_type(type_id, None)
    }

    /// ```
    /// semantic::check(r#"
    ///    undefined;
    /// // ^? undefined
    ///    1;
    /// // ^? 1
    /// "#);
    /// ```
    #[allow(clippy::match_same_arms)]
    fn check_expression_worker(&mut self, expr: &'a Expression<'a>) -> TypeId {
        match expr {
            Expression::Identifier(ident) => self.check_identifier(ident),
            // Literals
            Expression::NullLiteral(_) => self.types.null_widening_type_id,
            Expression::BooleanLiteral(lit) => self.check_boolean_literal(lit.value),
            Expression::StringLiteral(lit) => self.check_string_literal(&lit.value),
            Expression::NumberLiteral(lit) => self.check_number_literal(*lit.value),
            Expression::BigintLiteral(lit) => self.check_bigint_literal(&lit.value),
            Expression::TemplateLiteral(lit) => self.check_templatei_literal(lit),
            Expression::RegExpLiteral(_) => self.check_regexp_literal(),
            Expression::MetaProperty(_) => self.types.any_type_id,
            Expression::Super(_) => self.types.any_type_id,
            // Expressions
            Expression::ParenthesizedExpression(expr) => {
                self.check_expression_worker(&expr.expression)
            }
            Expression::ArrayExpression(expr) => self.check_array_literal(expr),
            Expression::AssignmentExpression(expr) => self.check_assignment_expression(expr),
            Expression::AwaitExpression(_expr) => self.types.any_type_id,
            Expression::BinaryExpression(expr) => self.check_binary_expression(expr),
            Expression::CallExpression(expr) => {
                self.check_call_expression(CallLikeExpression::CallExpression(expr))
            }
            Expression::ChainExpression(expr) => self.check_chain_expression(expr),
            Expression::ConditionalExpression(expr) => self.check_conditional_expression(expr),
            Expression::ImportExpression(_expr) => self.types.any_type_id,
            Expression::JSXElement(_expr) => self.types.any_type_id,
            Expression::JSXFragment(_expr) => self.types.any_type_id,
            Expression::LogicalExpression(expr) => self.check_logical_expression(expr),
            Expression::MemberExpression(expr) => self.check_member_expression(expr),
            Expression::NewExpression(expr) => {
                self.check_call_expression(CallLikeExpression::NewExpression(expr))
            }
            Expression::ObjectExpression(expr) => self.check_object_literal(expr),
            Expression::PrivateInExpression(_expr) => self.types.any_type_id,
            Expression::SequenceExpression(expr) => self.check_sequence_expression(expr),
            Expression::TaggedTemplateExpression(_expr) => self.types.any_type_id,
            Expression::ThisExpression(_expr) => self.types.any_type_id,
            Expression::UnaryExpression(expr) => self.check_unary_expression(expr),
            Expression::UpdateExpression(expr) => self.check_update_expression(expr),
            Expression::YieldExpression(_expr) => self.types.any_type_id,
            Expression::ClassExpression(expr) => self.check_class_like_declaration(expr),
            Expression::FunctionExpression(expr) => self
                .check_function_expression_or_object_literal_method(FunctionKind::Function(expr)),
            Expression::ArrowFunctionExpression(expr) => self
                .check_function_expression_or_object_literal_method(FunctionKind::ArrowExpression(
                    expr,
                )),
            // Types
            Expression::TSNonNullExpression(expr) => self.check_non_null_expression(expr),
            Expression::TSAsExpression(expr) => {
                self.check_assertion_worker(&expr.type_annotation, &expr.expression)
            }
            Expression::TSTypeAssertion(expr) => {
                self.check_assertion_worker(&expr.type_annotation, &expr.expression)
            }
            Expression::TSInstantiationExpression(expr) => self
                .check_expression_with_type_arguments(
                    ExpressionWithTypeArguments::TSInstantiationExpression(expr),
                ),
        }
    }

    fn check_boolean_literal(&mut self, value: bool) -> TypeId {
        if value { self.types.true_type_id } else { self.types.false_type_id }
    }

    /// ```
    /// semantic::check(r#"
    /// let a = "x";
    /// //      ^? "x"
    /// let b = `y`;
    /// //      ^? "y"
    /// "#);
    /// ```
    fn check_string_literal(&mut self, value: &Atom) -> TypeId {
        let value = LiteralValue::String(value.clone());
        let type_id = self.get_literal_type(value, TypeFlags::StringLiteral);
        self.get_fresh_type_of_literal_type(type_id)
    }

    /// ```
    /// semantic::check(r#"
    /// let a = 1
    /// //      ^ 1
    /// "#);
    /// ```
    fn check_number_literal(&mut self, value: f64) -> TypeId {
        let value = LiteralValue::Number(value);
        let type_id = self.get_literal_type(value, TypeFlags::NumberLiteral);
        self.get_fresh_type_of_literal_type(type_id)
    }

    /// ```
    /// semantic::check(r#"
    /// let a = 1n
    /// //      ^ bigint
    /// "#);
    /// ```
    fn check_bigint_literal(&mut self, value: &BigUint) -> TypeId {
        let value = LiteralValue::BigInt(value.clone(), false);
        let type_id = self.get_literal_type(value, TypeFlags::BigInt);
        self.get_fresh_type_of_literal_type(type_id)
    }

    fn check_regexp_literal(&mut self) -> TypeId {
        self.types.global_regexp_type_id
    }

    fn check_templatei_literal(&mut self, lit: &TemplateLiteral<'a>) -> TypeId {
        if lit.is_no_substitution_template() {
            lit.quasi().map_or(self.types.string_type_id, |quasi| self.check_string_literal(quasi))
        } else {
            self.types.string_type_id
        }
    }

    /// ```
    /// semantic::check(r#"
    ///   function x(): 3 {};
    ///   const y = x();
    ///   //    ^? 3
    ///   let a = String()
    ///   //  ^? string
    ///   let b = Number()
    ///   //  ^? number
    ///   let c = Boolean()
    ///   //  ^? boolean
    /// "#);
    /// ```
    fn check_call_expression(&mut self, expr: CallLikeExpression<'a>) -> TypeId {
        let signature_id = self.get_resolved_signature(expr);

        if matches!(expr, CallLikeExpression::NewExpression(_)) {
            if let Some(declaration) = self.signatures[signature_id].declaration {
                let scope_id = self.nodes[declaration].scope_id;
                if !self.scopes[scope_id].flags.contains(ScopeFlags::Constructor) {
                    // When resolved signature is a call signature (and not a construct signature) the result type is any
                    return self.types.any_type_id;
                }
            }
        }

        self.get_return_type_of_signature(signature_id)
    }

    /// ```
    /// semantic::check(r#"
    ///   let a = () => {}
    ///   //  ^? () => void
    ///   let b = function() {}
    ///   //  ^? () => void
    /// "#);
    /// ```
    fn check_function_expression_or_object_literal_method(&mut self, func: FunctionKind) -> TypeId {
        let node = func.node();
        let symbol_id = self.symbols.get_symbol_id_of_span(&node.range());
        self.get_type_of_symbol(symbol_id)
    }

    fn check_identifier(&mut self, ident: &IdentifierReference) -> TypeId {
        let symbol_id = self.get_resolved_symbol(&ident.name, ident.node.range());
        if symbol_id == self.symbols.unknown_symbol_id {
            return self.types.error_type_id;
        }
        self.get_narrowed_type_of_symbol(symbol_id, ident)
    }

    /// ```
    /// semantic::check(r#"
    /// let a = [];
    /// //  ^? any[]
    /// let b = [1];
    /// //  ^? number[]
    /// let c = [1, 2];
    /// //  ^? number[]
    /// "#);
    /// ```
    fn check_array_literal(&mut self, array: &'a ArrayExpression<'a>) -> TypeId {
        let mut element_types: Vec<TypeId> = vec![];
        for e in (&array.elements).into_iter().flatten() {
            if let Argument::Expression(expr) = e {
                let type_id = self.check_expression_for_mutable_location(expr);
                element_types.push(type_id);
            }
        }

        let element_type = if element_types.is_empty() {
            if self.options.strict_null_checks {
                self.types.implicit_never_type_id
            } else {
                self.types.undefined_widening_type_id
            }
        } else {
            self.get_union_type(&element_types, UnionReduction::Subtype)
        };

        let type_id = self.types.create_array_type(element_type, /* readonly */ false);
        self.types.create_array_literal_type(type_id)
    }

    /// ```
    /// semantic::check(r#"
    /// let x = 1;
    ///     x = 1;
    /// //  ^? number
    ///     x += 1;
    /// //  ^? number
    /// "#);
    /// ```
    fn check_assignment_expression(&mut self, expr: &'a AssignmentExpression<'a>) -> TypeId {
        let left = match &expr.left {
            AssignmentTarget::SimpleAssignmentTarget(target) => {
                self.check_simple_assignment_target(target)
            }
            AssignmentTarget::AssignmentTargetPattern(_) => self.types.any_type_id,
        };
        let right = self.check_expression(&expr.right);
        match expr.operator {
            AssignmentOperator::Assign => right,
            AssignmentOperator::Addition => self.check_binary_addition(left, right),
            AssignmentOperator::LogicalOr => self.check_logical_or(left, right),
            AssignmentOperator::LogicalAnd => self.check_logical_and(left, right),
            AssignmentOperator::LogicalNullish => self.check_logical_nullish(left, right),
            AssignmentOperator::Subtraction
            | AssignmentOperator::Multiplication
            | AssignmentOperator::Division
            | AssignmentOperator::Remainder
            | AssignmentOperator::Exponential
            | AssignmentOperator::ShiftLeft
            | AssignmentOperator::ShiftRight
            | AssignmentOperator::ShiftRightZeroFill
            | AssignmentOperator::BitwiseOR
            | AssignmentOperator::BitwiseXOR
            | AssignmentOperator::BitwiseAnd => self.check_binary_arithmetic(left, right),
        }
    }

    fn check_simple_assignment_target(&mut self, target: &'a SimpleAssignmentTarget<'a>) -> TypeId {
        match target {
            SimpleAssignmentTarget::AssignmentTargetIdentifier(ident) => {
                self.check_identifier(ident)
            }
            SimpleAssignmentTarget::TSAsExpression(expr) => self.check_expression(&expr.expression),
            SimpleAssignmentTarget::TSNonNullExpression(expr) => {
                self.check_expression(&expr.expression)
            }
            SimpleAssignmentTarget::TSTypeAssertion(expr) => {
                self.check_expression(&expr.expression)
            }
            SimpleAssignmentTarget::MemberAssignmentTarget(expr) => {
                self.check_property_access_expression(expr)
            }
        }
    }

    /// ```
    /// semantic::check(r#"
    /// let a = {};
    /// //  ^? {}
    /// let b = { x: "string" };
    /// //        ^? string
    /// "#);
    /// ```
    fn check_object_literal(&mut self, object: &'a ObjectExpression<'a>) -> TypeId {
        let mut members = SymbolMap::default();
        let mut properties = vec![];
        for object_property in &object.properties {
            if let ObjectProperty::Property(property) = object_property {
                let symbol_id = self.symbols.get_symbol_id_of_span(&property.node.range());
                let symbol_flags = self.symbols[symbol_id].flags;
                let resolved_type_id = self.check_property_assignment(property);
                if let Some(name) = property.key.static_name() {
                    let property_symbol_id = self.symbols.create_symbol(
                        name.as_str(),
                        property.key.node(),
                        SymbolFlags::Property | symbol_flags,
                    );
                    self.get_symbol_links(property_symbol_id).t.replace(resolved_type_id);
                    self.get_symbol_links(symbol_id).t.replace(resolved_type_id);
                    members.insert(name, property_symbol_id);
                    properties.push(property_symbol_id);
                }
            }
        }
        self.types.create_anonymous_type(None, members, properties)
    }

    /// ```
    /// semantic::check(r#"
    /// let _ = { x: 1 };
    /// //        ^? number
    /// "#);
    /// ```
    fn check_property_assignment(&mut self, property: &'a Property<'a>) -> TypeId {
        if property.shorthand {
            return self.types.any_type_id;
        }
        match &property.value {
            PropertyValue::Expression(expr) => self.check_expression_for_mutable_location(expr),
            PropertyValue::Pattern(_) => self.types.any_type_id,
        }
    }

    fn check_binding_identifier(&mut self, ident: &'a BindingIdentifier) {
        self.check_variable_like_declaration(VariableLikeDeclaration::BindingIdentifier(ident));
    }

    fn check_variable_like_declaration(&mut self, decl: VariableLikeDeclaration<'a>) {
        let symbol_id = self.symbols.get_symbol_id_of_span(&decl.node().range());
        self.get_type_of_symbol(symbol_id);
    }

    /// ```
    /// semantic::check(r#"
    /// let _ = "s";
    /// //  ^? string
    /// "#);
    /// ```
    fn check_declaration_initializer(&mut self, decl: &'a VariableDeclarator<'a>) -> TypeId {
        let initializer = decl.init.as_ref().unwrap();
        self.get_quick_type_of_expression(initializer)
            .unwrap_or_else(|| self.check_expression_cached(initializer))
    }

    fn check_non_null_expression(&mut self, expr: &'a TSNonNullExpression<'a>) -> TypeId {
        self.check_expression(&expr.expression)
    }

    fn check_assertion_worker(
        &mut self,
        type_node: &'a TSType<'a>,
        expr: &'a Expression<'a>,
    ) -> TypeId {
        if type_node.is_const_type_reference() {
            let literal = self.check_expression(expr);
            return self.get_regular_type_of_literal_type(literal);
        }

        self.get_type_from_type_node(type_node)
    }

    /// ```
    /// semantic::check(r#"
    /// const x = true ? 1 : '1';
    /// //    ^? 1 | "1"
    /// "#);
    /// ```
    fn check_conditional_expression(&mut self, expr: &'a ConditionalExpression<'a>) -> TypeId {
        let type1 = self.check_expression(&expr.consequent);
        let type2 = self.check_expression(&expr.alternate);
        self.get_union_type(&[type1, type2], UnionReduction::Subtype)
    }

    /// ```
    /// semantic::check(r#"
    /// const a = -1;
    /// //    ^? -1
    /// const b = -0;
    /// //    ^? 0
    /// const c = typeof x;
    /// //    ^? "string" | "number" | "bigint" | "boolean" | "symbol" | "undefined" | "object" | "function"
    /// const d = !"";
    /// //    ^? true
    /// "#);
    /// ```
    fn check_unary_expression(&mut self, expr: &'a UnaryExpression<'a>) -> TypeId {
        let operand_type_id = self.check_expression(&expr.argument);
        if operand_type_id == self.types.silent_never_type_id {
            return self.types.silent_never_type_id;
        }

        let operator = expr.operator;
        let is_plus_or_minus =
            operator == UnaryOperator::UnaryPlus || operator == UnaryOperator::UnaryNegation;
        match &expr.argument {
            Expression::NumberLiteral(literal) if is_plus_or_minus => {
                let value = literal.value;
                let value = LiteralValue::Number(
                    if operator == UnaryOperator::UnaryNegation && value != 0.0 {
                        -*value
                    } else {
                        *value
                    },
                );
                let lit = self.get_literal_type(value, TypeFlags::NumberLiteral);
                return self.get_fresh_type_of_literal_type(lit);
            }
            Expression::BigintLiteral(literal) if is_plus_or_minus => {
                let negative = operator == UnaryOperator::UnaryNegation;
                let value = LiteralValue::BigInt(literal.value.clone(), negative);
                let lit = self.get_literal_type(value, TypeFlags::BigIntLiteral);
                return self.get_fresh_type_of_literal_type(lit);
            }
            _ => {}
        }

        match operator {
            UnaryOperator::UnaryPlus | UnaryOperator::UnaryNegation | UnaryOperator::BitwiseNot => {
                if operator == UnaryOperator::UnaryPlus {
                    return self.types.number_type_id;
                }
                self.get_unary_result_type(operand_type_id)
            }
            UnaryOperator::Delete => self.check_delete_expression(expr),
            UnaryOperator::Void => self.check_void_expression(expr),
            UnaryOperator::LogicalNot => {
                let facts =
                    self.get_type_facts(operand_type_id) & (TypeFacts::Truthy | TypeFacts::Falsy);
                if facts == TypeFacts::Truthy {
                    self.types.false_type_id
                } else if facts == TypeFacts::Falsy {
                    self.types.true_type_id
                } else {
                    self.types.boolean_type_id
                }
            }
            UnaryOperator::Typeof => self.types.type_of_type_id,
        }
    }

    /// ```
    /// semantic::check(r#"
    /// let a = 1 === 2;
    /// //  ^? boolean
    /// let b = "x" + "y";
    /// //  ^? string
    /// let c = x in y;
    /// //  ^? boolean
    /// let d = x instanceof y;
    /// //  ^? boolean
    /// let e = 1 + 1;
    /// //  ^? number
    /// "#);
    /// ```
    fn check_binary_expression(&mut self, expr: &'a BinaryExpression<'a>) -> TypeId {
        let left = self.check_expression_cached(&expr.left);
        let right = self.check_expression_cached(&expr.right);
        match expr.operator {
            BinaryOperator::Equality
            | BinaryOperator::Inequality
            | BinaryOperator::StrictEquality
            | BinaryOperator::StrictInequality
            | BinaryOperator::LessThan
            | BinaryOperator::LessEqualThan
            | BinaryOperator::GreaterThan
            | BinaryOperator::GreaterEqualThan => self.types.boolean_type_id,
            BinaryOperator::Addition => self.check_binary_addition(left, right),
            BinaryOperator::Subtraction
            | BinaryOperator::Multiplication
            | BinaryOperator::Division
            | BinaryOperator::Remainder
            | BinaryOperator::Exponential
            | BinaryOperator::ShiftLeft
            | BinaryOperator::ShiftRight
            | BinaryOperator::ShiftRightZeroFill
            | BinaryOperator::BitwiseOR
            | BinaryOperator::BitwiseXOR
            | BinaryOperator::BitwiseAnd => self.check_binary_arithmetic(left, right),
            BinaryOperator::Instanceof => {
                self.check_instance_of_expression(&expr.left, &expr.right, left, right)
            }
            BinaryOperator::In => self.check_in_expression(&expr.left, &expr.right, left, right),
        }
    }

    fn check_binary_addition(&mut self, left_type: TypeId, right_type: TypeId) -> TypeId {
        let mut left_type = left_type;
        let mut right_type = right_type;

        if left_type == self.types.silent_never_type_id
            || right_type == self.types.silent_never_type_id
        {
            return self.types.silent_never_type_id;
        }

        if !self.types.is_type_assignable_to_kind(left_type, TypeFlags::StringLike, false)
            && !self.types.is_type_assignable_to_kind(right_type, TypeFlags::StringLike, false)
        {
            left_type = self.check_non_null_type(left_type);
            right_type = self.check_non_null_type(right_type);
        }

        let result =
            if self.types.is_type_assignable_to_kind(left_type, TypeFlags::NumberLike, true)
                && self.types.is_type_assignable_to_kind(right_type, TypeFlags::NumberLike, true)
            {
                Some(self.types.number_type_id)
            } else if self.types.is_type_assignable_to_kind(left_type, TypeFlags::BigIntLike, true)
                && self.types.is_type_assignable_to_kind(right_type, TypeFlags::BigIntLike, true)
            {
                Some(self.types.bigint_type_id)
            } else if self.types.is_type_assignable_to_kind(left_type, TypeFlags::StringLike, true)
                || self.types.is_type_assignable_to_kind(right_type, TypeFlags::StringLike, true)
            {
                Some(self.types.string_type_id)
            } else {
                None
            };
        result.unwrap_or(self.types.any_type_id)
    }

    fn check_binary_arithmetic(&mut self, left_type: TypeId, right_type: TypeId) -> TypeId {
        if left_type == self.types.silent_never_type_id
            || right_type == self.types.silent_never_type_id
        {
            return self.types.silent_never_type_id;
        }
        self.types.number_type_id
    }

    fn check_chain_expression(&mut self, chain: &'a ChainExpression<'a>) -> TypeId {
        match &chain.expression {
            ChainElement::CallExpression(e) => {
                self.check_call_expression(CallLikeExpression::CallExpression(e))
            }
            ChainElement::MemberExpression(e) => self.check_member_expression(e),
        }
    }

    /// ```
    /// semantic::check(r#"
    /// let a = x instanceof y;
    /// //  ^? boolean
    /// "#);
    /// ```
    fn check_instance_of_expression(
        &mut self,
        _left: &Expression<'a>,
        _right: &Expression<'a>,
        _left_type_id: TypeId,
        _right_type_id: TypeId,
    ) -> TypeId {
        self.types.boolean_type_id
    }

    /// ```
    /// semantic::check(r#"
    /// let a = x in y;
    /// //  ^? boolean
    /// "#);
    /// ```
    fn check_in_expression(
        &mut self,
        _left: &Expression<'a>,
        _right: &Expression<'a>,
        _left_type_id: TypeId,
        _right_type_id: TypeId,
    ) -> TypeId {
        self.types.boolean_type_id
    }

    // TODO
    fn check_property_access_expression(&mut self, _expr: &MemberExpression<'a>) -> TypeId {
        self.types.any_type_id
    }

    /// ```
    /// semantic::check(r#"
    ///   let x = ("1", true, 3);
    ///   //  ^? number
    /// "#);
    /// ```
    fn check_sequence_expression(&mut self, expr: &'a SequenceExpression<'a>) -> TypeId {
        let len = expr.expressions.len();
        for (i, e) in expr.expressions.iter().enumerate() {
            let type_id = self.check_expression_cached(e);
            if i == len - 1 {
                return type_id;
            }
        }
        // for empty sequence expression from incorrect AST
        self.types.error_type_id
    }

    /// ```
    /// semantic::check(r#"
    ///   let x = 1;
    ///   const y = ++x;
    ///   //    ^? number
    /// "#);
    /// ```
    fn check_update_expression(&mut self, expr: &'a UpdateExpression<'a>) -> TypeId {
        let operand_type = self.check_simple_assignment_target(&expr.argument);
        self.get_unary_result_type(operand_type)
    }

    fn check_logical_expression(&mut self, expr: &'a LogicalExpression<'a>) -> TypeId {
        let left_type_id = self.check_expression_cached(&expr.left);
        let right_type_id = self.check_expression_cached(&expr.right);
        match expr.operator {
            LogicalOperator::Or => self.check_logical_or(left_type_id, right_type_id),
            LogicalOperator::And => self.check_logical_and(left_type_id, right_type_id),
            LogicalOperator::Coalesce => self.check_logical_nullish(left_type_id, right_type_id),
        }
    }

    /// ```
    /// semantic::check(r#"
    ///   let a = null || "string";
    ///   //  ^? "string"
    /// "#);
    /// ```
    fn check_logical_or(&mut self, left_type_id: TypeId, right_type_id: TypeId) -> TypeId {
        if self.get_type_facts(left_type_id).intersects(TypeFacts::Falsy) {
            let left_type_id = self.remove_definitely_falsy_types(left_type_id);
            let left_type_id = self.get_non_nullable_type(left_type_id);
            self.get_union_type(&[left_type_id, right_type_id], UnionReduction::Subtype)
        } else {
            left_type_id
        }
    }

    /// ```
    /// semantic::check(r#"
    ///   let a = true && false;
    ///   //  ^? false
    /// "#);
    /// ```
    fn check_logical_and(&mut self, left_type_id: TypeId, right_type_id: TypeId) -> TypeId {
        if self.get_type_facts(left_type_id).intersects(TypeFacts::Truthy) {
            let left_type_id = if self.options.strict_null_checks {
                left_type_id
            } else {
                self.get_base_type_of_literal_type(right_type_id)
            };
            let left_type_id = self.extract_definitely_falsy_types(left_type_id);
            self.get_union_type(&[left_type_id, right_type_id], UnionReduction::Literal)
        } else {
            left_type_id
        }
    }

    /// ```
    /// semantic::check(r#"
    ///   let a = null ?? "string";
    ///   //  ^? "string"
    /// "#);
    /// ```
    fn check_logical_nullish(&mut self, left_type_id: TypeId, right_type_id: TypeId) -> TypeId {
        if self.get_type_facts(left_type_id).intersects(TypeFacts::EQUndefinedOrNull) {
            let left_type_id = self.get_non_nullable_type(left_type_id);
            self.get_union_type(&[left_type_id, right_type_id], UnionReduction::Subtype)
        } else {
            left_type_id
        }
    }

    fn check_member_expression(&mut self, _expr: &MemberExpression<'a>) -> TypeId {
        self.types.any_type_id
    }

    /// ```
    /// semantic::check(r#"
    ///   let x = 1;
    ///   const y = delete x;
    ///   //    ^? boolean
    /// "#);
    /// ```
    fn check_delete_expression(&mut self, _expr: &UnaryExpression<'a>) -> TypeId {
        self.types.boolean_type_id
    }

    /// ```
    /// semantic::check(r#"
    ///   let x = void 0;
    ///    // ^? undefined
    /// "#);
    /// ```
    fn check_void_expression(&mut self, _expr: &UnaryExpression<'a>) -> TypeId {
        self.types.undefined_type_id
    }

    // TODO
    fn check_this_expression(&mut self) -> TypeId {
        self.types.any_type_id
    }

    // TODO
    fn check_expression_with_type_arguments(
        &mut self,
        expr: ExpressionWithTypeArguments<'a>,
    ) -> TypeId {
        match expr {
            ExpressionWithTypeArguments::TSInstantiationExpression(expr) => {
                self.check_expression(&expr.expression)
            }
            ExpressionWithTypeArguments::TSTypeQuery(query) => match &query.expr_name {
                TSTypeName::IdentifierName(ident) => {
                    if ident.name == "this" {
                        self.check_this_expression()
                    } else {
                        self.check_identifier(&IdentifierReference {
                            name: ident.name.clone(),
                            node: ident.node,
                        })
                    }
                }
                // TODO
                TSTypeName::QualifiedName(_name) => self.types.any_type_id,
            },
        }
    }

    /// ```
    /// semantic::check(r#"
    ///    "use strict";
    /// // ^? "use strict"
    /// "#);
    /// ```
    fn check_directive(&mut self, directive: &Directive<'a>) {
        self.with_resolved_type(directive.expression.node.range(), |builder| {
            builder.check_string_literal(&directive.expression.value)
        });
    }

    /// ```
    /// semantic::check(r#"
    ///   function x() { if (1) {return 3} else {return '4'} };
    ///   const a = x();
    ///   //    ^? 3 | "4"
    /// "#);
    /// ```
    fn check_and_aggregate_return_expression_types(
        &mut self,
        body: &FunctionBody<'a>,
    ) -> Option<Vec<TypeId>> {
        let mut aggregated_types = vec![];
        let mut has_return_with_no_expression = false;
        let mut has_return_of_never_type = false;

        if let Some(return_nodes) = self
            .span_to_node
            .get(&body.node.range())
            .and_then(|ast_node| self.nodes.function_return_statements.get(ast_node).cloned())
        {
            for node_id in return_nodes {
                if let AstKind::ReturnStatement(stmt) = self.nodes[node_id].kind {
                    if let Some(argument) = &stmt.argument {
                        let type_id = self.check_expression_cached(argument);
                        let r#type = &self.types[type_id];
                        if r#type.flags.intersects(TypeFlags::Never) {
                            has_return_of_never_type = true;
                        }
                        aggregated_types.push(type_id);
                    } else {
                        has_return_with_no_expression = true;
                    }
                }
            }
        }

        if aggregated_types.is_empty() && !has_return_with_no_expression && has_return_of_never_type
        {
            return None;
        }

        Some(aggregated_types)
    }

    /// ```
    /// semantic::check(r#"
    ///   class A {}
    ///   //    ^? A
    /// "#);
    /// ```
    // ClassLikeDeclaration = | ClassDeclaration | ClassExpression
    fn check_class_like_declaration(&mut self, class: &Class<'a>) -> TypeId {
        let symbol_id = self.symbols.get_symbol_id_of_span(&class.node.range());
        self.get_declared_type_of_symbol(symbol_id)
    }

    /// ```
    /// semantic::check(r#"
    ///   enum A {}
    ///   //   ^? A
    /// "#);
    /// ```
    fn check_enum_declaration(&mut self, decl: &TSEnumDeclaration<'a>) -> TypeId {
        let symbol_id = self.symbols.get_symbol_id_of_span(&decl.node.range());
        self.get_declared_type_of_symbol(symbol_id)
    }

    /// ```
    /// semantic::check(r#"
    ///   namespace A {}
    ///   //     ^? typeof A
    /// "#);
    /// ```
    fn check_module_declaration(&mut self, decl: &TSModuleDeclaration<'a>) -> TypeId {
        let symbol_id = self.symbols.get_symbol_id_of_span(&decl.node.range());
        self.get_type_of_symbol(symbol_id)
    }
}

table.rs

use std::ops::{Index, IndexMut};

use estree::BigUint;
use rustc_hash::FxHashMap;

use super::{
    IntrinsicType, LiteralType, LiteralValue, ObjectFlags, ObjectType, Type, TypeFlags, TypeId,
    TypeKind, UnionType,
};
use crate::{
    symbol::{SymbolId, SymbolMap, SymbolTable},
    SemanticBuilderOptions,
};

const TYPE_OF_TYPES: &[&str; 8] =
    &["string", "number", "bigint", "boolean", "symbol", "undefined", "object", "function"];

#[derive(Debug, Default)]
pub struct TypeTable {
    types: Vec<Type>,
    pub literal_values: FxHashMap<LiteralValue, TypeId>,

    // NOTE: These must be declared in the same declaration order per TypeScript's source.
    // The order of union types are sorted by TypeId
    pub any_type_id: TypeId,
    pub wildcard_type_id: TypeId,
    pub error_type_id: TypeId,
    pub unknown_type_id: TypeId,
    pub non_null_unknown_type_id: TypeId,
    pub undefined_type_id: TypeId,
    pub undefined_widening_type_id: TypeId,
    pub null_type_id: TypeId,
    pub null_widening_type_id: TypeId,
    pub string_type_id: TypeId,
    pub number_type_id: TypeId,
    pub bigint_type_id: TypeId,
    pub false_type_id: TypeId,
    pub regular_false_type_id: TypeId,
    pub true_type_id: TypeId,
    pub regular_true_type_id: TypeId,
    pub boolean_type_id: TypeId,
    pub es_symbol_type_id: TypeId,
    pub void_type_id: TypeId,
    pub never_type_id: TypeId,
    pub silent_never_type_id: TypeId,
    pub implicit_never_type_id: TypeId,
    pub non_primitive_type_id: TypeId,

    pub empty_object_type_id: TypeId,
    pub unknown_union_type_id: TypeId,
    pub type_of_type_id: TypeId,

    // Global Types
    // these should eventually be read from a .d.ts file
    pub global_array_type_id: TypeId,    // "Array"
    pub global_object_type_id: TypeId,   // "Object"
    pub global_function_type_id: TypeId, // "Function"
    pub global_string_type_id: TypeId,   // "String"
    pub global_number_type_id: TypeId,   // "Number"
    pub global_boolean_type_id: TypeId,  // "Boolean"
    pub global_regexp_type_id: TypeId,   // "RegExp"
    pub global_promise_type_id: TypeId,  // "Promise"

    pub empty_string_type_id: TypeId,
    pub zero_type_id: TypeId,
    pub zero_big_int_type_id: TypeId,
}

impl Index<TypeId> for TypeTable {
    type Output = Type;

    fn index(&self, index: TypeId) -> &Self::Output {
        &self.types[index.index0()]
    }
}

impl IndexMut<TypeId> for TypeTable {
    fn index_mut(&mut self, index: TypeId) -> &mut Self::Output {
        &mut self.types[index.index0()]
    }
}

/// Type Factory Helpers
impl TypeTable {
    #[rustfmt::skip]
    #[must_use]
    pub fn new(options: &SemanticBuilderOptions, symbols: &SymbolTable) -> Self {
        let mut table = Self::default();

        // NOTE: declaration order matters here, as union types are sorted by TypeId
        table.any_type_id = table.create_intrinsic_type(TypeFlags::Any, "any");
        table.wildcard_type_id = table.create_intrinsic_type(TypeFlags::Any, "any");
        table.error_type_id = table.create_intrinsic_type(TypeFlags::Any, "error");
        table.unknown_type_id = table.create_intrinsic_type(TypeFlags::Unknown, "unknown");
        table.non_null_unknown_type_id = table.create_intrinsic_type(TypeFlags::Unknown, "unknown");
        table.undefined_type_id = table.create_intrinsic_type(TypeFlags::Undefined, "undefined");
        table.undefined_widening_type_id = if options.strict_null_checks { table.unknown_type_id } else {
            table.create_intrinsic_type_with_flags(TypeFlags::Undefined, "undefined", ObjectFlags::ContainsWideningType)
        };
        table.null_type_id = table.create_intrinsic_type(TypeFlags::Null, "null");
        table.null_widening_type_id = if options.strict_null_checks { table.null_type_id } else {
            table.create_intrinsic_type_with_flags(TypeFlags::Null, "null", ObjectFlags::ContainsWideningType)
        };
        table.string_type_id = table.create_intrinsic_type(TypeFlags::String, "string");
        table.number_type_id = table.create_intrinsic_type(TypeFlags::Number, "number");
        table.bigint_type_id = table.create_intrinsic_type(TypeFlags::BigInt, "bigint");
        let false_type_id = table.create_intrinsic_type(TypeFlags::BooleanLiteral, "false");
        let regular_false_type_id = table.create_intrinsic_type(TypeFlags::BooleanLiteral, "false");
        let true_type_id = table.create_intrinsic_type(TypeFlags::BooleanLiteral, "true");
        let regular_true_type_id = table.create_intrinsic_type(TypeFlags::BooleanLiteral, "true");

        table.false_type_id = false_type_id;
        table.regular_false_type_id = regular_false_type_id;
        table.true_type_id = true_type_id;
        table.regular_true_type_id = regular_true_type_id;

        table[true_type_id].set_regular_type(regular_true_type_id);
        table[true_type_id].set_fresh_type(true_type_id);
        table[regular_true_type_id].set_regular_type(regular_true_type_id);
        table[regular_true_type_id].set_fresh_type(true_type_id);
        table[false_type_id].set_regular_type(regular_false_type_id);
        table[false_type_id].set_fresh_type(false_type_id);
        table[regular_false_type_id].set_regular_type(regular_false_type_id);
        table[regular_false_type_id].set_fresh_type(false_type_id);

        table.boolean_type_id = table.create_union_type(vec![table.regular_false_type_id, table.regular_true_type_id]);
        table.es_symbol_type_id = table.create_intrinsic_type(TypeFlags::ESSymbol, "symbol");
        table.void_type_id = table.create_intrinsic_type(TypeFlags::Void, "void");
        table.never_type_id = table.create_intrinsic_type(TypeFlags::Never, "never");
        table.silent_never_type_id = table.create_intrinsic_type_with_flags(TypeFlags::Never, "never", ObjectFlags::NonInferrableType);
        table.implicit_never_type_id = table.create_intrinsic_type(TypeFlags::Never, "never");
        table.non_primitive_type_id = table.create_intrinsic_type(TypeFlags::NonPrimitive, "object");

        table.empty_object_type_id = table.create_anonymous_type(None, SymbolMap::default(), vec![]);
        // table.unknown_union_type_id = if options.strict_null_checks { table.get_union_type([table.undefined_type_id, table.null_type_id, table.unknown_empty_object_type_id]) } else { table.unknown_type_id };

        let typeof_types = TYPE_OF_TYPES.iter().map(|t| table.get_string_literal_type(t)).collect();
        table.type_of_type_id = table.create_union_type(typeof_types);

        table.global_array_type_id = table.create_object_type(ObjectFlags::ClassOrInterface, Some(symbols.global_array_symbol_id));
        table.global_object_type_id = table.create_object_type(ObjectFlags::Interface, Some(symbols.global_object_symbol_id));
        table.global_function_type_id = table.create_object_type(ObjectFlags::Interface, Some(symbols.global_function_symbol_id));
        table.global_string_type_id = table.create_object_type(ObjectFlags::ClassOrInterface, Some(symbols.global_string_symbol_id));
        table.global_number_type_id = table.create_object_type(ObjectFlags::Interface, Some(symbols.global_number_symbol_id));
        table.global_boolean_type_id = table.create_object_type(ObjectFlags::Interface, Some(symbols.global_boolean_symbol_id));
        table.global_regexp_type_id = table.create_object_type(ObjectFlags::ClassOrInterface, Some(symbols.global_regexp_symbol_id));
        table.global_promise_type_id = table.create_object_type(ObjectFlags::ClassOrInterface, Some(symbols.global_promise_symbol_id));

        table.empty_string_type_id = table.get_string_literal_type("");
        table.zero_type_id = table.get_number_literal_type(0.0);
        table.zero_big_int_type_id = table.get_big_int_literal_type(BigUint::from(0u8), false);

        table
    }

    #[must_use]
    pub fn create_type(&mut self, flags: TypeFlags) -> &mut Type {
        let id = TypeId::new(self.types.len() + 1);
        let t = Type::new(id, flags);
        self.types.push(t);
        &mut self.types[id]
    }

    #[must_use]
    pub fn create_intrinsic_type(&mut self, flags: TypeFlags, intrinsic_name: &str) -> TypeId {
        let mut t = self.create_type(flags);
        t.kind = TypeKind::IntrinsicType(IntrinsicType::new(intrinsic_name));
        t.id
    }

    #[must_use]
    pub fn create_intrinsic_type_with_flags(
        &mut self,
        flags: TypeFlags,
        intrinsic_name: &str,
        object_flags: ObjectFlags,
    ) -> TypeId {
        let mut t = self.create_type(flags);
        t.kind = TypeKind::IntrinsicType(IntrinsicType {
            object_flags,
            ..IntrinsicType::new(intrinsic_name)
        });
        t.id
    }

    #[must_use]
    pub fn create_literal_type(
        &mut self,
        flags: TypeFlags,
        value: LiteralValue,
        symbol_id: Option<SymbolId>,
        regular_type: Option<TypeId>,
    ) -> TypeId {
        let type_id = {
            let mut ty = self.create_type(flags);
            ty.kind = TypeKind::LiteralType(LiteralType::new(value.clone()));
            ty.symbol_id = symbol_id;
            ty.set_regular_type(regular_type.unwrap_or(ty.id));
            ty.id
        };
        self.literal_values.insert(value, type_id);
        type_id
    }

    #[must_use]
    pub fn create_object_type(
        &mut self,
        object_flags: ObjectFlags,
        symbol_id: Option<SymbolId>,
    ) -> TypeId {
        let mut t = self.create_type(TypeFlags::Object);
        t.kind = TypeKind::ObjectType(ObjectType::new(object_flags));
        t.symbol_id = symbol_id;
        t.id
    }

    #[must_use]
    pub fn create_array_literal_type(&mut self, type_id: TypeId) -> TypeId {
        let ty = &self.types[type_id];
        if !ty.object_flags().contains(ObjectFlags::Reference) {
            return type_id;
        }
        match &ty.kind {
            TypeKind::ObjectType(object_type) => {
                if let Some(literal_type) = object_type.literal_type {
                    return literal_type;
                }
                let literal_type_id = self.clone_type_reference(ty.id);
                if let TypeKind::ObjectType(object_type) = &mut self.types[type_id].kind {
                    object_type.literal_type = Some(literal_type_id);
                    object_type.object_flags |=
                        ObjectFlags::ArrayLiteral | ObjectFlags::ContainsObjectOrArrayLiteral;
                }
                literal_type_id
            }
            _ => unreachable!(),
        }
    }

    #[must_use]
    pub fn create_array_type(&mut self, element_type: TypeId, _readonly: bool) -> TypeId {
        self.create_type_from_generic_global_type(self.global_array_type_id, vec![element_type])
    }

    #[must_use]
    pub fn create_type_from_generic_global_type(
        &mut self,
        generic_global_type: TypeId,
        type_arguments: Vec<TypeId>,
    ) -> TypeId {
        self.create_type_reference(generic_global_type, type_arguments)
    }

    // TODO: add instantiations cache
    #[must_use]
    pub fn create_type_reference(&mut self, target: TypeId, type_arguments: Vec<TypeId>) -> TypeId {
        let ty = &self.types[target];
        let type_id = self.create_object_type(ObjectFlags::Reference, ty.symbol_id);
        let object_flags = self.get_propagating_flags_of_types(&type_arguments, None);
        match &mut self.types[type_id].kind {
            TypeKind::ObjectType(object_type) => {
                object_type.target = target;
                object_type.object_flags |= object_flags;
                object_type.resolved_type_arguments = type_arguments;
            }
            _ => unreachable!(),
        };
        type_id
    }

    #[must_use]
    pub fn create_union_type(&mut self, types: Vec<TypeId>) -> TypeId {
        let mut t = self.create_type(TypeFlags::Union);
        t.kind = TypeKind::UnionType(UnionType { types });
        t.id
    }

    #[must_use]
    pub fn create_anonymous_type(
        &mut self,
        symbol_id: Option<SymbolId>,
        members: SymbolMap,
        properties: Vec<SymbolId>,
    ) -> TypeId {
        let type_id = self.create_object_type(ObjectFlags::Anonymous, symbol_id);
        self.set_structured_type_members(type_id, members, properties)
    }

    #[must_use]
    pub fn create_enum_type(&mut self, symbol_id: SymbolId) -> TypeId {
        let mut t = self.create_type(TypeFlags::Enum);
        t.symbol_id = Some(symbol_id);
        t.id
    }

    pub fn create_promise_type(&mut self, _promised_type: TypeId) -> TypeId {
        // TODO
        self.global_promise_type_id
    }

    #[must_use]
    fn clone_type_reference(&mut self, type_id: TypeId) -> TypeId {
        let source = &self.types[type_id];
        let flags = source.flags;
        let kind = source.kind.clone();
        let t = self.create_type(flags);
        t.kind = kind;
        t.id
    }

    fn set_structured_type_members(
        &mut self,
        type_id: TypeId,
        members: SymbolMap,
        properties: Vec<SymbolId>,
    ) -> TypeId {
        if let TypeKind::ObjectType(object_type) = &mut self.types[type_id].kind {
            object_type.members = members;
            object_type.properties = properties;
        }
        type_id
    }
}

/// Type Getter Helpers
impl TypeTable {
    #[must_use]
    pub fn get_string_literal_type(&mut self, value: &str) -> TypeId {
        let value = LiteralValue::String(value.into());
        self.literal_values.get(&value).copied().unwrap_or_else(|| {
            let type_id =
                self.create_literal_type(TypeFlags::StringLiteral, value.clone(), None, None);
            self.literal_values.insert(value, type_id);
            type_id
        })
    }

    #[must_use]
    pub fn get_number_literal_type(&mut self, value: f64) -> TypeId {
        let value = LiteralValue::Number(value);
        self.literal_values.get(&value).copied().unwrap_or_else(|| {
            let type_id =
                self.create_literal_type(TypeFlags::NumberLiteral, value.clone(), None, None);
            self.literal_values.insert(value, type_id);
            type_id
        })
    }

    #[must_use]
    pub fn get_big_int_literal_type(&mut self, value: BigUint, negative: bool) -> TypeId {
        let value = LiteralValue::BigInt(value, negative);
        self.literal_values.get(&value).copied().unwrap_or_else(|| {
            let type_id =
                self.create_literal_type(TypeFlags::BigIntLiteral, value.clone(), None, None);
            self.literal_values.insert(value, type_id);
            type_id
        })
    }

    // This function is used to propagate certain flags when creating new object type references and union types.
    // It is only necessary to do so if a constituent type might be the undefined type, the null type, the type
    // of an object literal or a non-inferrable type. This is because there are operations in the type checker
    // that care about the presence of such types at arbitrary depth in a containing type.
    #[must_use]
    pub fn get_propagating_flags_of_types(
        &self,
        type_ids: &[TypeId],
        exclude_kinds: Option<TypeFlags>,
    ) -> ObjectFlags {
        let mut result = ObjectFlags::empty();
        for type_id in type_ids {
            let ty = &self.types[*type_id];
            if exclude_kinds.map_or(true, |f| !f.intersects(ty.flags)) {
                result |= ty.get_object_flags();
            }
        }
        result & ObjectFlags::PropagatingFlags
    }
}

/// Type Checking Helpers
impl TypeTable {
    #[must_use]
    pub fn is_object_literal_type(&self, ty: &Type) -> bool {
        ty.get_object_flags().intersects(ObjectFlags::ObjectLiteral)
    }

    #[must_use]
    pub fn is_array_type(&self, ty: &Type) -> bool {
        ty.get_object_flags().intersects(ObjectFlags::Reference)
            && match &ty.kind {
                // TODO: (type as TypeReference).target === globalReadonlyArrayType);
                TypeKind::ObjectType(object_type) => {
                    object_type.target == self.global_array_type_id
                }
                _ => false,
            }
    }

    #[must_use]
    pub const fn is_tuple_type(&self, _ty: &Type) -> bool {
        // return !!(getObjectFlags(type) & ObjectFlags.Reference && (type as TypeReference).target.objectFlags & ObjectFlags.Tuple);
        false
    }

    #[must_use]
    pub fn is_array_or_tuple_type(&self, ty: &Type) -> bool {
        self.is_array_type(ty) || self.is_tuple_type(ty)
    }

    #[must_use]
    pub fn is_type_identifical_to(&self, source: TypeId, target: TypeId) -> bool {
        self.is_type_related_to(source, target /* identity_relation */)
    }

    #[must_use]
    pub fn is_type_assignable_to(&self, source: TypeId, target: TypeId) -> bool {
        self.is_type_related_to(source, target /* assignableRelation */)
    }

    #[must_use]
    pub fn is_type_related_to(&self, source: TypeId, target: TypeId /* relation */) -> bool {
        if source == target {
            return true;
        }

        let source = &self.types[source];
        let target = &self.types[target];

        if source.id == target.id {
            return true;
        }

        if self.is_simple_type_replated_to(source, target)
            || self.is_simple_type_replated_to(target, source)
        {
            return true;
        }

        false
    }

    #[must_use]
    #[allow(clippy::unused_self)]
    const fn is_simple_type_replated_to(&self, source: &Type, target: &Type) -> bool {
        let s = source.flags;
        let t = target.flags;
        if s.intersects(TypeFlags::StringLike) && t.intersects(TypeFlags::String) {
            return true;
        }
        false
    }

    #[must_use]
    pub fn is_type_assignable_to_kind(
        &self,
        source_id: TypeId,
        kind: TypeFlags,
        strict: bool,
    ) -> bool {
        let source = &self.types[source_id];
        if source.flags.intersects(kind) {
            return true;
        }
        if strict
            && source.flags.intersects(
                TypeFlags::AnyOrUnknown | TypeFlags::Void | TypeFlags::Undefined | TypeFlags::Null,
            )
        {
            return false;
        }
        kind.intersects(TypeFlags::NumberLike)
            && self.is_type_assignable_to(source_id, self.number_type_id)
            || kind.intersects(TypeFlags::BigIntLike)
                && self.is_type_assignable_to(source_id, self.bigint_type_id)
            || kind.intersects(TypeFlags::StringLike)
                && self.is_type_assignable_to(source_id, self.string_type_id)
            || kind.intersects(TypeFlags::BooleanLike)
                && self.is_type_assignable_to(source_id, self.boolean_type_id)
            || kind.intersects(TypeFlags::Void)
                && self.is_type_assignable_to(source_id, self.void_type_id)
            || kind.intersects(TypeFlags::Never)
                && self.is_type_assignable_to(source_id, self.never_type_id)
            || kind.intersects(TypeFlags::Null)
                && self.is_type_assignable_to(source_id, self.null_type_id)
            || kind.intersects(TypeFlags::Undefined)
                && self.is_type_assignable_to(source_id, self.undefined_type_id)
            || kind.intersects(TypeFlags::ESSymbol)
                && self.is_type_assignable_to(source_id, self.es_symbol_type_id)
            || kind.intersects(TypeFlags::NonPrimitive)
                && self.is_type_assignable_to(source_id, self.non_primitive_type_id)
    }
}