// This file is part of the Luau programming language and is licensed under MIT License; see LICENSE.txt for details
#include "Luau/ConstraintGenerator.h"

#include "Luau/Ast.h"
#include "Luau/AstUtils.h"
#include "Luau/BuiltinDefinitions.h"
#include "Luau/BuiltinTypeFunctions.h"
#include "Luau/Common.h"
#include "Luau/Constraint.h"
#include "Luau/ControlFlow.h"
#include "Luau/ControlFlowGraph.h"
#include "Luau/DcrLogger.h"
#include "Luau/Def.h"
#include "Luau/DenseHash.h"
#include "Luau/IterativeTypeVisitor.h"
#include "Luau/ModuleResolver.h"
#include "Luau/Normalize.h"
#include "Luau/NotNull.h"
#include "Luau/RecursionCounter.h"
#include "Luau/Refinement.h"
#include "Luau/Scope.h"
#include "Luau/Simplify.h"
#include "Luau/StringUtils.h"
#include "Luau/Subtyping.h"
#include "Luau/TimeTrace.h"
#include "Luau/Type.h"
#include "Luau/TypeFunction.h"
#include "Luau/TypeFunctionError.h"
#include "Luau/TypePack.h"
#include "Luau/TypeStateMap.h"
#include "Luau/TypeUtils.h"
#include "Luau/Unifier2.h"
#include "Luau/VisitType.h"

#include <memory>

LUAU_DYNAMIC_FASTINTVARIABLE(LuauConstraintGeneratorRecursionLimit, 300)

LUAU_FASTINT(LuauCheckRecursionLimit)
LUAU_FASTFLAG(DebugLuauLogSolverToJson)
LUAU_FASTFLAG(DebugLuauMagicTypes)
LUAU_FASTINTVARIABLE(LuauPrimitiveInferenceInTableLimit, 500)
LUAU_FASTFLAGVARIABLE(LuauDisallowRedefiningBuiltinTypes)
LUAU_FASTFLAG(LuauIntegerType2)
LUAU_FASTFLAG(DebugLuauUserDefinedClasses)
LUAU_FASTFLAGVARIABLE(DebugLuauCFG)
LUAU_FASTFLAG(LuauCyclicRequireTypeInference)
LUAU_FASTFLAGVARIABLE(DebugLuauExactTableTypes)
LUAU_FASTFLAG(LuauSetmetatableOverrides)
LUAU_FASTFLAGVARIABLE(LuauThreadGeneralizeThroughConstraintGeneration)
LUAU_FASTFLAGVARIABLE(LuauExperimentalIfLocalAnalysis)
LUAU_FLAGVERSION(LuauExperimentalIfLocalAnalysis, 2)
LUAU_FASTFLAG(LuauTraverseScopeToFunction)
LUAU_FASTFLAGVARIABLE(LuauUnconditionallyVisitTypeAliasParams)

namespace Luau
{

bool doesCallError(const AstExprCall* call);        // TypeInfer.cpp
const AstStat* getFallthrough(const AstStat* node); // TypeInfer.cpp

static bool isValidClassMetamethod(const Name& name)
{
    return name == "__call" || name == "__concat" || name == "__unm" || name == "__add" || name == "__sub" || name == "__mul" || name == "__div" ||
           name == "__mod" || name == "__pow" || name == "__tostring" || name == "__eq" || name == "__lt" || name == "__le" || name == "__iter" ||
           name == "__len" || name == "__idiv";
}

static std::optional<AstExpr*> matchRequire(const AstExprCall& call)
{
    const char* require = "require";

    if (call.args.size != 1)
        return std::nullopt;

    const AstExprGlobal* funcAsGlobal = call.func->as<AstExprGlobal>();
    if (!funcAsGlobal || funcAsGlobal->name != require)
        return std::nullopt;

    if (call.args.size != 1)
        return std::nullopt;

    return call.args.data[0];
}


static const RefinementKey* matchIsInstanceGuard(const AstExprCall& call, NotNull<const DataFlowGraph> dfg)
{
    AstExprIndexName* index = call.func->as<AstExprIndexName>();
    if (!index || index->op != '.')
        return nullptr;

    if (index->index != "isinstance")
        return nullptr;

    if (!index->expr->is<AstExprGlobal>())
        return nullptr;

    if (call.args.size < 1)
        return nullptr;

    return dfg->getRefinementKey(call.args.data[0]);
}

namespace
{

Checkpoint checkpoint(const ConstraintGenerator* cg)
{
    if (FFlag::LuauCyclicRequireTypeInference)
        return Checkpoint{cg->cgraph->constraints.size()};
    return Checkpoint{cg->constraints.size()};
}

template<typename F>
void forEachConstraint(const Checkpoint& start, const Checkpoint& end, const ConstraintGenerator* cg, F f)
{
    if (FFlag::LuauCyclicRequireTypeInference)
    {
        for (size_t i = start.offset; i < end.offset; ++i)
        {
            f(cg->cgraph->constraints[i]);
        }
    }
    else
    {
        for (size_t i = start.offset; i < end.offset; ++i)
        {
            f(cg->constraints[i]);
        }
    }
}

/**
 * For all constraints [C] from [start] to [end], block dispatching
 * [target] on [C].
 */
LUAU_NOINLINE void addAllAsDependencies(const Checkpoint& start, const Checkpoint& end, const ConstraintGenerator* cg, NotNull<Constraint> target)
{
    forEachConstraint(
        start,
        end,
        cg,
        [cg, target](const ConstraintPtr& ptr)
        {
            cg->cgraph->addDependencyOf(ptr.get(), target);
        }
    );
}

/**
 * For all constraints [C] from [start] to [end], block dispatching
 * [C] on [target].
 */
LUAU_NOINLINE void addAllAsReverseDependencies(
    const Checkpoint& start,
    const Checkpoint& end,
    const ConstraintGenerator* cg,
    NotNull<Constraint> target
)
{
    forEachConstraint(
        start,
        end,
        cg,
        [cg, target](const ConstraintPtr& ptr)
        {
            cg->cgraph->addDependencyOf(target, ptr.get());
        }
    );
}

/**
 * For all constraints [C] from [start] to [end], block dispatching
 * [target] on [C].
 *
 * HACK: Additionally, chain `PackSubtypeConstraint`s that are tied to return
 * statements in order to preserve some behavior from the old solver.
 */
LUAU_NOINLINE void addAllAsDependenciesAndChainReturns(
    const Checkpoint& start,
    const Checkpoint& end,
    const ConstraintGenerator* cg,
    NotNull<Constraint> target
)
{
    Constraint* previous = nullptr;
    forEachConstraint(
        start,
        end,
        cg,
        [cg, target, &previous](const ConstraintPtr& constraint)
        {
            cg->cgraph->addDependencyOf(constraint.get(), target);
            if (auto psc = get<PackSubtypeConstraint>(*constraint); psc && psc->returns)
            {
                if (previous)
                    cg->cgraph->addDependencyOf(previous, constraint.get());

                previous = constraint.get();
            }
        }
    );
}

struct HasFreeType : TypeOnceVisitor
{
    bool result = false;

    HasFreeType()
        : TypeOnceVisitor("TypeOnceVisitor", /* skipBoundTypes */ true)
    {
    }

    bool visit(TypeId ty) override
    {
        if (result || ty->persistent)
            return false;
        return true;
    }

    bool visit(TypePackId tp) override
    {
        if (result)
            return false;
        return true;
    }

    bool visit(TypeId ty, const ExternType&) override
    {
        return false;
    }

    bool visit(TypeId ty, const FreeType&) override
    {
        result = true;
        return false;
    }

    bool visit(TypePackId ty, const FreeTypePack&) override
    {
        result = true;
        return false;
    }
};

bool hasFreeType(TypeId ty)
{
    HasFreeType hft{};
    hft.traverse(ty);
    return hft.result;
}

struct GlobalNameCollector : public AstVisitor
{
    DenseHashSet<AstName> names;

    GlobalNameCollector() = default;

    bool visit(AstExprGlobal* node) override
    {
        names.insert(node->name);
        return true;
    }
};

struct TypeFunctionEnvGlobalBinder : AstVisitor
{
    NotNull<Scope> environmentScope;
    NotNull<const DataFlowGraph> dfg;

    TypeFunctionEnvGlobalBinder(NotNull<Scope> environmentScope, NotNull<const DataFlowGraph> dfg)
        : environmentScope(environmentScope)
        , dfg(dfg)
    {
    }

    bool visit(AstExprGlobal* global) override
    {
        if (auto ty = environmentScope->lookup(global->name))
            environmentScope->lvalueTypes[dfg->getDef(global)] = *ty;

        return true;
    }
};

TypeId findSetmetatableTargetOf(TypeId target)
{
    target = follow(target);

    // NOTE: This does not correctly handle tables with
    // __metatable.
    if (auto tt = get<MetatableType>(target))
        return tt->table;

    return target;
}

} // namespace

ConstraintGenerator::ConstraintGenerator(
    ModulePtr module,
    NotNull<Normalizer> normalizer,
    NotNull<TypeFunctionRuntime> typeFunctionRuntime,
    NotNull<ModuleResolver> moduleResolver,
    NotNull<BuiltinTypes> builtinTypes,
    NotNull<InternalErrorReporter> ice,
    ScopePtr globalScope,
    ScopePtr typeFunctionScope,
    std::function<void(const ModuleName&, const ScopePtr&)> prepareModuleScope,
    DcrLogger* logger,
    NotNull<DataFlowGraph> dfg,
    std::vector<RequireCycle> requireCycles,
    NotNull<ConstraintGraph> cgraph,
    CFG::TypeStateMap* typestate
)
    : module(module)
    , sharedModuleName(std::make_shared<ModuleName>(module->name))
    , builtinTypes(builtinTypes)
    , arena(normalizer->arena)
    , rootScope(nullptr)
    , dfg(dfg)
    , normalizer(normalizer)
    , typeFunctionRuntime(typeFunctionRuntime)
    , moduleResolver(moduleResolver)
    , ice(ice)
    , globalScope(std::move(globalScope))
    , typeFunctionScope(std::move(typeFunctionScope))
    , prepareModuleScope(std::move(prepareModuleScope))
    , requireCycles(std::move(requireCycles))
    , logger(logger)
    , cgraph(cgraph)
    , typestate(typestate)
{
    LUAU_ASSERT(module);
}

ConstraintSet ConstraintGenerator::run(AstStatBlock* block)
{
    visitModuleRoot(block);

    if (FFlag::LuauCyclicRequireTypeInference)
    {
        std::vector<ConstraintPtr> deferred;
        if (moduleGeneralizationConstraint)
            deferred.push_back(std::move(moduleGeneralizationConstraint));

        // constraints, freeTypes, and ScopeToFunction are empty with LuauCyclicRequireTypeInference because they're added to ConstraintGraph instead
        // of ConstraintSet
        return ConstraintSet{NotNull{rootScope}, {}, {}, DenseHashMap<Scope*, TypeId>{}, std::move(errors), std::move(deferred)};
    }

    return ConstraintSet{NotNull{rootScope}, std::move(constraints), std::move(freeTypes), std::move(scopeToFunction), std::move(errors)};
}

ConstraintSet ConstraintGenerator::runOnFragment(const ScopePtr& resumeScope, AstStatBlock* block)
{
    visitFragmentRoot(resumeScope, block);

    if (FFlag::LuauCyclicRequireTypeInference)
        return ConstraintSet{NotNull{rootScope}, {}, {}, DenseHashMap<Scope*, TypeId>{}, std::move(errors)};
    return ConstraintSet{NotNull{rootScope}, std::move(constraints), std::move(freeTypes), std::move(scopeToFunction), std::move(errors)};
}

void ConstraintGenerator::visitModuleRoot(AstStatBlock* block)
{
    LUAU_TIMETRACE_SCOPE("ConstraintGenerator::visitModuleRoot", "Typechecking");

    LUAU_ASSERT(scopes.empty());
    LUAU_ASSERT(rootScope == nullptr);
    ScopePtr scope = std::make_shared<Scope>(globalScope);
    rootScope = scope.get();
    scopes.emplace_back(block->location, scope);
    rootScope->location = block->location;
    module->astScopes[block] = NotNull{scope.get()};

    interiorFreeTypes.emplace_back();

    // Create module-local scope for the type function environment
    ScopePtr localTypeFunctionScope = std::make_shared<Scope>(typeFunctionScope);
    localTypeFunctionScope->location = block->location;
    typeFunctionRuntime->rootScope = localTypeFunctionScope;

    rootScope->returnType = freshTypePack(scope, Polarity::Positive);
    TypeId moduleFnTy = arena->addType(FunctionType{TypeLevel{}, builtinTypes->anyTypePack, rootScope->returnType});

    prepopulateGlobalScope(scope, block);

    Checkpoint start = checkpoint(this);

    ControlFlow cf = visitBlockWithoutChildScope(scope, block);
    if (cf == ControlFlow::None)
        addConstraint(scope, block->location, PackSubtypeConstraint{builtinTypes->emptyTypePack, rootScope->returnType});

    Checkpoint end = checkpoint(this);

    TypeId result = arena->addType(BlockedType{});

    if (FFlag::LuauCyclicRequireTypeInference)
    {
        moduleGeneralizationConstraint = std::make_unique<Constraint>(
            NotNull{scope.get()}, block->location, GeneralizationConstraint{result, moduleFnTy, nullptr, true}, sharedModuleName
        );
        getMutable<BlockedType>(result)->setOwner(NotNull{moduleGeneralizationConstraint.get()});
        addAllAsDependencies(start, end, this, NotNull{moduleGeneralizationConstraint.get()});
    }
    else
    {
        NotNull<Constraint> genConstraint = addConstraint(
            scope,
            block->location,
            GeneralizationConstraint{
                result,
                moduleFnTy,
                /* maybeDeprecatedAttr */ nullptr,
                /* noGenerics */ true
            }
        );
        getMutable<BlockedType>(result)->setOwner(genConstraint);
        addAllAsDependencies(start, end, this, genConstraint);
    }

    scope->interiorFreeTypes = std::move(interiorFreeTypes.back().types);
    scope->interiorFreeTypePacks = std::move(interiorFreeTypes.back().typePacks);

    interiorFreeTypes.pop_back();

    if (!FFlag::DebugLuauCFG)
        fillInInferredBindings(scope, block);

    if (logger)
        logger->captureGenerationModule(module);

    for (const auto& [ty, domain] : localTypes)
    {
        // FIXME: This isn't the most efficient thing.
        TypeId domainTy = builtinTypes->neverType;
        for (TypeId d : domain)
        {
            d = follow(d);
            if (d == ty)
                continue;
            domainTy = simplifyUnion(scope, Location{}, domainTy, d);
        }

        LUAU_ASSERT(get<BlockedType>(ty));
        asMutable(ty)->ty.emplace<BoundType>(domainTy);
    }

    for (TypeId ty : unionsToSimplify)
        addConstraint(scope, block->location, SimplifyConstraint{ty});
}

void ConstraintGenerator::visitFragmentRoot(const ScopePtr& resumeScope, AstStatBlock* block)
{
    // We prepopulate global data in the resumeScope to avoid writing data into the old modules scopes
    prepopulateGlobalScopeForFragmentTypecheck(globalScope, resumeScope, block);
    // Pre
    interiorFreeTypes.emplace_back();
    visitBlockWithoutChildScope(resumeScope, block);
    // Post
    interiorFreeTypes.pop_back();

    if (!FFlag::DebugLuauCFG)
        fillInInferredBindings(resumeScope, block);

    if (logger)
        logger->captureGenerationModule(module);

    for (const auto& [ty, domain] : localTypes)
    {
        // FIXME: This isn't the most efficient thing.
        TypeId domainTy = builtinTypes->neverType;
        for (TypeId d : domain)
        {
            d = follow(d);
            if (d == ty)
                continue;
            domainTy = simplifyUnion(resumeScope, resumeScope->location, domainTy, d);
        }

        LUAU_ASSERT(get<BlockedType>(ty));
        asMutable(ty)->ty.emplace<BoundType>(domainTy);
    }
}


TypeId ConstraintGenerator::freshType(const ScopePtr& scope, Polarity polarity)
{
    const TypeId ft = Luau::freshType(arena, builtinTypes, scope.get(), polarity);
    interiorFreeTypes.back().types.push_back(ft);
    if (FFlag::LuauCyclicRequireTypeInference)
        cgraph->freeTypes.insert(ft);
    else
        freeTypes.insert(ft);
    return ft;
}

TypePackId ConstraintGenerator::freshTypePack(const ScopePtr& scope, Polarity polarity)
{
    FreeTypePack f{scope.get(), polarity};
    TypePackId result = arena->addTypePack(TypePackVar{std::move(f)});
    interiorFreeTypes.back().typePacks.push_back(result);
    return result;
}

TypePackId ConstraintGenerator::addTypePack(std::vector<TypeId> head, std::optional<TypePackId> tail)
{
    if (head.empty())
    {
        if (tail)
            return *tail;
        else
            return builtinTypes->emptyTypePack;
    }
    else
        return arena->addTypePack(TypePack{std::move(head), tail});
}

ScopePtr ConstraintGenerator::childScope(AstNode* node, const ScopePtr& parent)
{
    auto scope = std::make_shared<Scope>(parent);
    scopes.emplace_back(node->location, scope);
    scope->location = node->location;

    scope->returnType = parent->returnType;
    scope->varargPack = parent->varargPack;

    parent->children.emplace_back(scope.get());
    module->astScopes[node] = scope.get();

    return scope;
}

std::optional<TypeId> ConstraintGenerator::lookup(const ScopePtr& scope, Location location, DefId def, bool prototype)
{
    if (get<Cell>(def))
        return scope->lookup(def);
    if (auto phi = get<Phi>(def))
    {
        if (auto found = scope->lookup(def))
            return *found;
        else if (!prototype && phi->operands.size() == 1)
            return lookup(scope, location, phi->operands.at(0), prototype);
        else if (!prototype)
            return std::nullopt;

        TypeId res = builtinTypes->neverType;

        for (DefId operand : phi->operands)
        {
            // `scope->lookup(operand)` may return nothing because we only bind a type to that operand
            // once we've seen that particular `DefId`. In this case, we need to prototype those typeArguments
            // and use those at a later time.
            std::optional<TypeId> ty = lookup(scope, location, operand, /*prototype*/ false);
            if (!ty)
            {
                ty = arena->addType(BlockedType{});
                localTypes.try_insert(*ty, {});
                rootScope->lvalueTypes[operand] = *ty;
            }

            res = makeUnion(scope, location, res, *ty);
        }

        scope->lvalueTypes[def] = res;
        return res;
    }
    else
        ice->ice("ConstraintGenerator::lookup is inexhaustive?");
}

TypeId ConstraintGenerator::resolveRHSType(const ScopePtr& scope, Location location, AstExpr* expr)
{
    LUAU_ASSERT(FFlag::DebugLuauCFG);
    TypeId ty = typestate->getRHSType(expr);
    LUAU_ASSERT(ty);
    ty = follow(ty);
    if (auto c = typestate->getOptionalConstraint(ty))
    {
        auto oc = addConstraint(scope, location, std::move(*c));
        if (auto bt = getMutable<BlockedType>(ty))
            bt->setOwner(oc.get());
    }

    return ty;
}

TypeId ConstraintGenerator::resolveLHSType(const ScopePtr& scope, Location location, const CFG::LValue& lv)
{
    LUAU_ASSERT(FFlag::DebugLuauCFG);
    TypeId ty = typestate->getLHSType(lv);
    LUAU_ASSERT(ty);
    ty = follow(ty);
    if (auto c = typestate->getOptionalConstraint(ty))
    {
        auto oc = addConstraint(scope, location, std::move(*c));
        if (auto bt = getMutable<BlockedType>(ty))
            bt->setOwner(oc.get());
    }

    return ty;
}

NotNull<Constraint> ConstraintGenerator::addConstraint(const ScopePtr& scope, const Location& location, ConstraintV cv)
{
    if (FFlag::LuauCyclicRequireTypeInference)
        return NotNull{cgraph->constraints.emplace_back(new Constraint{NotNull{scope.get()}, location, std::move(cv), sharedModuleName}).get()};
    return NotNull{constraints.emplace_back(new Constraint{NotNull{scope.get()}, location, std::move(cv)}).get()};
}

NotNull<Constraint> ConstraintGenerator::addConstraint(const ScopePtr& scope, std::unique_ptr<Constraint> c)
{
    if (FFlag::LuauCyclicRequireTypeInference)
    {
        c->moduleName = sharedModuleName;
        return NotNull{cgraph->constraints.emplace_back(std::move(c)).get()};
    }
    return NotNull{constraints.emplace_back(std::move(c)).get()};
}

void ConstraintGenerator::unionRefinements(
    const ScopePtr& scope,
    Location location,
    const RefinementContext& lhs,
    const RefinementContext& rhs,
    RefinementContext& dest,
    std::vector<ConstraintV>* constraints
)
{
    const auto intersect = [&](const std::vector<TypeId>& types)
    {
        if (1 == types.size())
            return types[0];
        else if (2 == types.size())
            return makeIntersect(scope, location, types[0], types[1]);

        return arena->addType(IntersectionType{types});
    };

    for (auto& [def, partition] : lhs)
    {
        auto rhsIt = rhs.find(def);
        if (rhsIt == rhs.end())
            continue;

        LUAU_ASSERT(!partition.discriminantTypes.empty());
        LUAU_ASSERT(!rhsIt->second.discriminantTypes.empty());

        TypeId leftDiscriminantTy = partition.discriminantTypes.size() == 1 ? partition.discriminantTypes[0] : intersect(partition.discriminantTypes);

        TypeId rightDiscriminantTy =
            rhsIt->second.discriminantTypes.size() == 1 ? rhsIt->second.discriminantTypes[0] : intersect(rhsIt->second.discriminantTypes);

        dest.insert(def, {});
        dest.get(def)->discriminantTypes.push_back(makeUnion(scope, location, leftDiscriminantTy, rightDiscriminantTy));
        dest.get(def)->shouldAppendNilType |= partition.shouldAppendNilType || rhsIt->second.shouldAppendNilType;
    }
}

void ConstraintGenerator::computeRefinement(
    const ScopePtr& scope,
    Location location,
    RefinementId refinement,
    RefinementContext* refis,
    bool sense,
    bool eq,
    std::vector<ConstraintV>* constraints
)
{
    if (!refinement)
        return;
    else if (auto variadic = get<Variadic>(refinement))
    {
        for (RefinementId refi : variadic->refinements)
            computeRefinement(scope, location, refi, refis, sense, eq, constraints);
    }
    else if (auto negation = get<Negation>(refinement))
        return computeRefinement(scope, location, negation->refinement, refis, !sense, eq, constraints);
    else if (auto conjunction = get<Conjunction>(refinement))
    {
        RefinementContext lhsRefis;
        RefinementContext rhsRefis;

        computeRefinement(scope, location, conjunction->lhs, sense ? refis : &lhsRefis, sense, eq, constraints);
        computeRefinement(scope, location, conjunction->rhs, sense ? refis : &rhsRefis, sense, eq, constraints);

        if (!sense)
            unionRefinements(scope, location, lhsRefis, rhsRefis, *refis, constraints);
    }
    else if (auto disjunction = get<Disjunction>(refinement))
    {
        RefinementContext lhsRefis;
        RefinementContext rhsRefis;

        computeRefinement(scope, location, disjunction->lhs, sense ? &lhsRefis : refis, sense, eq, constraints);
        computeRefinement(scope, location, disjunction->rhs, sense ? &rhsRefis : refis, sense, eq, constraints);

        if (sense)
            unionRefinements(scope, location, lhsRefis, rhsRefis, *refis, constraints);
    }
    else if (auto equivalence = get<Equivalence>(refinement))
    {
        computeRefinement(scope, location, equivalence->lhs, refis, sense, true, constraints);
        computeRefinement(scope, location, equivalence->rhs, refis, sense, true, constraints);
    }
    else if (auto proposition = get<Proposition>(refinement))
    {
        TypeId discriminantTy = proposition->discriminantTy;

        // if we have a negative sense, then we need to negate the discriminant
        if (!sense)
        {
            if (auto nt = get<NegationType>(follow(discriminantTy)))
                discriminantTy = nt->ty;
            else
                discriminantTy = arena->addType(NegationType{discriminantTy});
        }

        if (eq)
            discriminantTy = createTypeFunctionInstance(builtinTypes->typeFunctions->singletonFunc, {discriminantTy}, {}, scope, location);

        for (const RefinementKey* key = proposition->key; key; key = key->parent)
        {
            refis->insert(key->def, {});
            refis->get(key->def)->discriminantTypes.push_back(discriminantTy);

            // Reached leaf node
            if (!key->propName)
                break;

            TypeId nextDiscriminantTy = arena->addType(TableType{});
            NotNull<TableType> table{getMutable<TableType>(nextDiscriminantTy)};
            table->props[*key->propName] = Property::readonly(discriminantTy);
            table->scope = scope.get();
            table->state = TableState::Sealed;

            discriminantTy = nextDiscriminantTy;
        }

        // When the top-level expression is `t[x]`, we want to refine it into `nil`, not `never`.
        LUAU_ASSERT(refis->get(proposition->key->def));
        refis->get(proposition->key->def)->shouldAppendNilType =
            (sense || !eq) && containsSubscriptedDefinition(proposition->key->def) && !proposition->implicitFromCall;
    }
}

namespace
{

/*
 * Constraint generation may be called upon to simplify an intersection or union
 * of typeArguments that are not sufficiently solved yet.  We use
 * FindSimplificationBlockers to recognize these typeArguments and defer the
 * simplification until constraint solution.
 */
struct FindSimplificationBlockers : IterativeTypeVisitor
{
    bool found = false;

    FindSimplificationBlockers()
        : IterativeTypeVisitor("FindSimplificationBlockers", /* skipBoundTypes */ true)
    {
    }

    bool visit(TypeId) override
    {
        return !found;
    }

    bool visit(TypeId, const BlockedType&) override
    {
        found = true;
        return false;
    }

    bool visit(TypeId, const FreeType&) override
    {
        found = true;
        return false;
    }

    bool visit(TypeId, const PendingExpansionType&) override
    {
        found = true;
        return false;
    }

    // We do not need to know anything at all about a function's argument or
    // return typeArguments in order to simplify it in an intersection or union.
    bool visit(TypeId, const FunctionType&) override
    {
        return false;
    }

    bool visit(TypeId, const ExternType&) override
    {
        return false;
    }
};

bool mustDeferIntersection(TypeId ty)
{
    FindSimplificationBlockers bts;
    bts.run(ty);
    return bts.found;
}
} // namespace

enum RefinementsOpKind
{
    Intersect,
    Refine,
    None
};

void ConstraintGenerator::applyRefinements(const ScopePtr& scope, Location location, RefinementId refinement)
{
    if (!refinement)
        return;

    RefinementContext refinements;
    std::vector<ConstraintV> constraints;
    computeRefinement(scope, location, refinement, &refinements, /*sense*/ true, /*eq*/ false, &constraints);
    auto flushConstraints = [this, &scope, &location](RefinementsOpKind kind, TypeId ty, std::vector<TypeId>& discriminants)
    {
        if (discriminants.empty())
            return ty;
        if (kind == RefinementsOpKind::None)
        {
            LUAU_ASSERT(false);
            return ty;
        }
        std::vector<TypeId> args = {ty};
        const TypeFunction& func =
            kind == RefinementsOpKind::Intersect ? builtinTypes->typeFunctions->intersectFunc : builtinTypes->typeFunctions->refineFunc;
        LUAU_ASSERT(!func.name.empty());
        args.insert(args.end(), discriminants.begin(), discriminants.end());
        TypeId resultType = createTypeFunctionInstance(func, std::move(args), {}, scope, location);
        discriminants.clear();
        return resultType;
    };

    for (auto& [def, partition] : refinements)
    {
        if (std::optional<TypeId> defTy = lookup(scope, location, def))
        {
            TypeId ty = *defTy;
            // Intersect ty with every discriminant type. If either type is not
            // sufficiently solved, we queue the intersection up via an
            // IntersectConstraint.
            // For each discriminant ty, we accumulated it onto ty, creating a longer and longer
            // sequence of refine constraints. On every loop of this we called mustDeferIntersection.
            // For sufficiently large typeArguments, we would blow the stack.
            // Instead, we record all the discriminant typeArguments in sequence
            // and then dispatch a single refine constraint with multiple arguments. This helps us avoid
            // the potentially expensive check on mustDeferIntersection
            std::vector<TypeId> discriminants;
            RefinementsOpKind kind = RefinementsOpKind::None;
            bool mustDefer = mustDeferIntersection(ty);
            for (TypeId dt : partition.discriminantTypes)
            {
                mustDefer = mustDefer || mustDeferIntersection(dt);
                if (mustDefer)
                {
                    if (kind == RefinementsOpKind::Intersect)
                        ty = flushConstraints(kind, ty, discriminants);
                    kind = RefinementsOpKind::Refine;

                    discriminants.push_back(dt);
                }
                else
                {
                    ErrorSuppression status = shouldSuppressErrors(normalizer, ty);
                    if (status == ErrorSuppression::NormalizationFailed)
                        reportError(location, NormalizationTooComplex{});
                    if (kind == RefinementsOpKind::Refine)
                        ty = flushConstraints(kind, ty, discriminants);
                    kind = RefinementsOpKind::Intersect;

                    discriminants.push_back(dt);

                    if (status == ErrorSuppression::Suppress)
                    {
                        ty = flushConstraints(kind, ty, discriminants);
                        ty = makeUnion(scope, location, ty, builtinTypes->errorType);
                    }
                }
            }

            // Finalize - if there are any discriminants left, make one big constraint for refining them
            if (kind != RefinementsOpKind::None)
                ty = flushConstraints(kind, ty, discriminants);

            if (partition.shouldAppendNilType)
                ty = createTypeFunctionInstance(builtinTypes->typeFunctions->weakoptionalFunc, {ty}, {}, scope, location);
            updateRValueRefinements(scope, def, ty);
        }
    }

    for (auto& c : constraints)
        addConstraint(scope, location, c);
}

/*
 * To support things like recursive and corecursive type aliases, we handle them
 * in two passes. First, we do a surface scan where we count generic arguments
 * and stub types in with BlockedTypes.  Later, we'll process the bodies of
 * these statements and actually work out how to expand them.  In the case of
 * class definitions, we'll run type inference on class methods during that
 * second pass.
 *
 * This function implements the early prototyping pass.  The main execution flow
 * of ConstraintGenerator handles the second pass.
 */
void ConstraintGenerator::prototypeTypeDefinitions(const ScopePtr& scope, AstStatBlock* block)
{
    DenseHashMap<Name, Location> typeNameLocations;

    bool hasTypeFunction = false;
    ScopePtr typeFunctionEnvScope;

    // Stub out class declarations so that they can refer to one another in any order.
    DenseHashMap<AstStatClass*, TypeId> allClasses;
    for (AstStat* stat : block->body)
    {
        if (auto classDecl = stat->as<AstStatClass>())
        {
            TypeId classObjectTy = arena->addType(
                ExternType{classDecl->name->name.value, {}, std::nullopt, std::nullopt, Tags{}, nullptr, module->name, classDecl->location}
            );

            allClasses[classDecl] = classObjectTy;
        }
    }

    // In order to enable mutually-recursive type aliases, we need to
    // populate the type bindings before we actually check any of the
    // alias statements.
    for (AstStat* stat : block->body)
    {
        if (auto alias = stat->as<AstStatTypeAlias>())
        {
            if (FFlag::LuauDisallowRedefiningBuiltinTypes && globalScope->builtinTypeNames.contains(alias->name.value))
            {
                reportError(alias->location, DuplicateTypeDefinition{alias->name.value});
                continue;
            }

            // A type alias might have no name if the code is syntactically
            // illegal. We mustn't prepopulate anything in this case.
            if (alias->name == kParseNameError || alias->name == "typeof")
                continue;

            if (const Location* loc = typeNameLocations.find(alias->name.value))
            {
                reportError(alias->location, DuplicateTypeDefinition{alias->name.value, *loc});
                continue;
            }

            ScopePtr defnScope = childScope(alias, scope);

            TypeId initialType = arena->addType(BlockedType{});
            TypeFun initialFun{initialType};

            /* The boolean toggle `addTypes` decides whether or not to introduce the generic type/pack param into the privateType/Pack bindings.
               This map is used by resolveType(Pack) to determine whether or not to produce an error for `F<T... = ...T>`. Because we are delaying
               the the initialization of the generic default to the point at which we check the type alias, we need to ensure that we don't
               prematurely add `T` as this will cause us to allow the above example (T is in the bindings so we return that as the resolved type).
               Done this way, we can evaluate the default safely and then introduce the variable into the map again once the default has been
               evaluated. Note, only generic type aliases support default generic parameters.
             */

            for (const auto& [name, gen] : createGenerics(defnScope, alias->generics, /* useCache */ true, /* addTypes */ false))
            {
                initialFun.typeParams.push_back(gen);
            }

            for (const auto& [name, genPack] : createGenericPacks(defnScope, alias->genericPacks, /* useCache */ true, /* addTypes */ false))
            {
                initialFun.typePackParams.push_back(genPack);
            }
            initialFun.definitionLocation = alias->location;

            if (alias->exported)
                scope->exportedTypeBindings[alias->name.value] = std::move(initialFun);
            else
                scope->privateTypeBindings[alias->name.value] = std::move(initialFun);

            astTypeAliasDefiningScopes[alias] = defnScope;
            typeNameLocations[alias->name.value] = alias->location;
        }
        else if (auto function = stat->as<AstStatTypeFunction>())
        {
            hasTypeFunction = true;

            // If a type function w/ same name has already been defined, error for having duplicates
            if (const Location* loc = typeNameLocations.find(function->name.value))
            {
                reportError(function->location, DuplicateTypeDefinition{function->name.value, *loc});
                continue;
            }

            // Create TypeFunctionInstanceType
            std::vector<TypeId> typeParams;
            typeParams.reserve(function->body->args.size);

            std::vector<GenericTypeDefinition> quantifiedTypeParams;
            quantifiedTypeParams.reserve(function->body->args.size);

            for (size_t i = 0; i < function->body->args.size; i++)
            {
                std::string name = format("T%zu", i);
                TypeId ty = arena->addType(GenericType{name, Polarity::Unknown});
                typeParams.push_back(ty);

                GenericTypeDefinition genericTy{ty};
                quantifiedTypeParams.push_back(genericTy);
            }

            if (std::optional<TypeFunctionError> error = typeFunctionRuntime->registerFunction(function))
                reportError(function->location, BuiltInTypeFunctionError{*error});

            UserDefinedFunctionData udtfData;

            udtfData.owner = module;
            udtfData.definition = function;

            TypeId typeFunctionTy = arena->addType(
                TypeFunctionInstanceType{NotNull{&builtinTypes->typeFunctions->userFunc}, std::move(typeParams), {}, function->name, udtfData}
            );

            TypeFun typeFunction{std::move(quantifiedTypeParams), typeFunctionTy};

            typeFunction.definitionLocation = function->location;

            // Set type bindings and definition locations for this user-defined type function
            if (function->exported)
                scope->exportedTypeBindings[function->name.value] = std::move(typeFunction);
            else
                scope->privateTypeBindings[function->name.value] = std::move(typeFunction);

            typeNameLocations[function->name.value] = function->location;
        }
        else if (auto classDeclaration = stat->as<AstStatDeclareExternType>())
        {
            // A class might have no name if the code is syntactically
            // illegal. We mustn't prepopulate anything in this case.
            if (classDeclaration->name == kParseNameError)
                continue;

            if (const Location* loc = typeNameLocations.find(classDeclaration->name.value))
            {
                reportError(classDeclaration->location, DuplicateTypeDefinition{classDeclaration->name.value, *loc});
                continue;
            }

            ScopePtr defnScope = childScope(classDeclaration, scope);

            TypeId initialType = arena->addType(BlockedType{});
            TypeFun initialFun{initialType};
            initialFun.definitionLocation = classDeclaration->location;
            scope->exportedTypeBindings[classDeclaration->name.value] = std::move(initialFun);

            typeNameLocations[classDeclaration->name.value] = classDeclaration->location;
        }
        else if (auto classDecl = stat->as<AstStatClass>())
        {
            Name declName = classDecl->name->name.value;
            DefId theDef = dfg->getDef(classDecl->name);

            if (Location* loc = typeNameLocations.find(declName))
            {
                reportError(classDecl->location, DuplicateTypeDefinition{declName, *loc});
                scope->bindings[classDecl->name] = Binding{builtinTypes->errorType, classDecl->location};
                scope->lvalueTypes[theDef] = builtinTypes->errorType;
                continue;
            }
            typeNameLocations[declName] = classDecl->location;

            TypeId* classObjectTy = allClasses.find(classDecl);
            LUAU_ASSERT(classObjectTy && *classObjectTy);

            scope->bindings[classDecl->name] = Binding{*classObjectTy, classDecl->name->location};
            scope->lvalueTypes[theDef] = *classObjectTy;

            prototypeClass(scope, classDecl, *classObjectTy);
        }
    }

    if (hasTypeFunction)
        typeFunctionEnvScope = std::make_shared<Scope>(typeFunctionRuntime->rootScope);

    std::vector<TypeFunctionInstanceType*> createdTypeFunctions;
    DenseHashMap<AstStatTypeFunction*, const TypeFunctionInstanceType*> referencedTypeFunctions;

    // Additional pass for user-defined type functions to fill in their environments completely
    for (AstStat* stat : block->body)
    {
        if (auto function = stat->as<AstStatTypeFunction>())
        {
            // Similar to global pre-population, create a binding for each type function in the scope upfront
            TypeId bt = arena->addType(BlockedType{});
            typeFunctionEnvScope->bindings[function->name] = Binding{bt, function->location};
            astTypeFunctionEnvironmentScopes[function] = typeFunctionEnvScope;

            // Find the type function we have already created
            TypeFunctionInstanceType* mainTypeFun = nullptr;

            if (auto it = scope->privateTypeBindings.find(function->name.value); it != scope->privateTypeBindings.end())
                mainTypeFun = getMutable<TypeFunctionInstanceType>(it->second.type);

            if (!mainTypeFun)
            {
                if (auto it = scope->exportedTypeBindings.find(function->name.value); it != scope->exportedTypeBindings.end())
                    mainTypeFun = getMutable<TypeFunctionInstanceType>(it->second.type);
            }

            // Fill it with all visible type functions and referenced type aliases
            if (mainTypeFun)
            {
                createdTypeFunctions.push_back(mainTypeFun);

                GlobalNameCollector globalNameCollector;
                stat->visit(&globalNameCollector);

                UserDefinedFunctionData& userFuncData = mainTypeFun->userFuncData;
                size_t level = 0;

                auto addToEnvironment = [this, &globalNameCollector, &referencedTypeFunctions](
                                            UserDefinedFunctionData& userFuncData, ScopePtr scope, const Name& name, TypeFun tf, size_t level
                                        )
                {
                    if (auto ty = get<TypeFunctionInstanceType>(follow(tf.type)); ty && ty->userFuncData.definition)
                    {
                        if (userFuncData.environmentFunction.find(name))
                            return;

                        userFuncData.environmentFunction[name] = std::make_pair(ty->userFuncData.definition, level);

                        referencedTypeFunctions[ty->userFuncData.definition] = ty;

                        if (auto it = astTypeFunctionEnvironmentScopes.find(ty->userFuncData.definition))
                        {
                            if (auto existing = (*it)->linearSearchForBinding(name, /* traverseScopeChain */ false))
                                scope->bindings[ty->userFuncData.definition->name] = Binding{existing->typeId, ty->userFuncData.definition->location};
                        }
                    }
                    else if (!get<TypeFunctionInstanceType>(follow(tf.type)))
                    {
                        if (userFuncData.environmentAlias.find(name))
                            return;

                        AstName astName = module->names->get(name.c_str());

                        // Only register globals that we have detected to be used
                        if (!globalNameCollector.names.find(astName))
                            return;

                        // Function evaluation environment needs a stable reference to the alias
                        module->typeFunctionAliases.push_back(std::make_unique<TypeFun>(tf));

                        userFuncData.environmentAlias[name] = std::make_pair(module->typeFunctionAliases.back().get(), level);

                        // TODO: create a specific type alias type
                        scope->bindings[astName] = Binding{builtinTypes->anyType, tf.definitionLocation.value_or(Location())};
                    }
                };

                // Go up the scopes to register type functions and aliases, but without reaching into the global scope
                for (Scope* curr = scope.get(); curr && curr != globalScope.get(); curr = curr->parent.get())
                {
                    for (auto& [name, tf] : curr->privateTypeBindings)
                        addToEnvironment(userFuncData, typeFunctionEnvScope, name, tf, level);

                    for (auto& [name, tf] : curr->exportedTypeBindings)
                        addToEnvironment(userFuncData, typeFunctionEnvScope, name, tf, level);

                    level++;
                }
            }
        }
    }

    if (typeFunctionEnvScope)
    {
        TypeFunctionEnvGlobalBinder binder{NotNull{typeFunctionEnvScope.get()}, dfg};

        for (AstStat* stat : block->body)
        {
            if (auto function = stat->as<AstStatTypeFunction>())
                function->body->visit(&binder);
        }
    }

    // Finally, we need to include aliases from functions we might call
    for (TypeFunctionInstanceType* type : createdTypeFunctions)
    {
        UserDefinedFunctionData& sourceFuncData = type->userFuncData;

        // Go over all functions in our environment
        for (const auto& [targetFuncName, definitionAndLevel] : sourceFuncData.environmentFunction)
        {
            if (const TypeFunctionInstanceType** it = referencedTypeFunctions.find(definitionAndLevel.first))
            {
                const UserDefinedFunctionData& targetFuncData = (*it)->userFuncData;

                for (const auto& [aliasName, typeAndLevel] : targetFuncData.environmentAlias)
                {
                    if (!sourceFuncData.environmentAlias.find(aliasName))
                    {
                        // Combine definition levels because we are viewing target function aliases from the perspective of the target function
                        sourceFuncData.environmentAlias[aliasName] = {typeAndLevel.first, typeAndLevel.second + definitionAndLevel.second};
                    }
                }
            }
        }
    }
}

void ConstraintGenerator::prototypeClass(const ScopePtr& scope, AstStatClass* classDecl, TypeId classObjectTy)
{
    LUAU_ASSERT(FFlag::DebugLuauUserDefinedClasses);

    Name declName = classDecl->name->name.value;

    // Objects are ExternTypes, where the metatable field represents the metamethods associated with the instance.
    // Class: ExternType { props, parent: top class type, metatable: constructor }
    // Object: ExternType { props, parent: top object type for now, metatable: instance metamethods }
    TableType::Props staticProps;
    ExternType::Props props;
    TableType::Props instanceMetatableProps;
    DenseHashMap<AstName, TypeId> memberTypes;

    bool hasExplicitConstructor = false;
    TypeId constructorTy = nullptr;
    TableType::Props defaultConstructorProps;

    for (const auto& member : classDecl->members)
    {
        Luau::visit(
            overloaded{
                [&](const AstClassProperty& classProp)
                {
                    if (memberTypes.contains(classProp.name))
                        return;

                    auto [propertyType, _] = memberTypes.try_insert(classProp.name, arena->addType(BlockedType{}));
                    auto& p = props[classProp.name.value];

                    // This needs to be blocked initially: if this type refers
                    // to a type that contains a typeof or an alias that we have
                    // yet to define, then we'll ICE or misbehave.
                    p = Property::rw(propertyType);
                    p.location = classProp.nameLocation;

                    // We make the default constructor take read-only args. This is true, in that we do not write to the table you pass for
                    // constructing an object.
                    defaultConstructorProps[classProp.name.value] = Property::readonly(propertyType);
                },
                [&](const AstClassMethod& method)
                {
                    if (memberTypes.contains(method.functionName))
                        return;

                    auto [propertyType, _] = memberTypes.try_insert(method.functionName, arena->addType(BlockedType{}));

                    auto prop = Property::readonly(propertyType);
                    prop.location = method.nameLocation;
                    if (method.function->args.size < 1 || method.function->args.data[0]->name != "self")
                        staticProps[method.functionName.value] = prop;

                    // The parser will report an error for classes that define disallowed metamethods.
                    // The RFC also requires that it is a syntax error for methods to have __ in their name whose name is not in the
                    // validClassMetamethod set.
                    if (isValidClassMetamethod(method.functionName.value))
                        instanceMetatableProps[method.functionName.value] = prop;
                    else
                        props[method.functionName.value] = prop;

                    if (method.functionName == "__init")
                    {
                        hasExplicitConstructor = true;
                        constructorTy = arena->addType(BlockedType{});
                    }
                }
            },
            member
        );
    }

    TypeId instanceMetatable = arena->addType(TableType{instanceMetatableProps, std::nullopt, TypeLevel{}, scope.get(), TableState::Sealed});

    TypeId classInstanceTy = arena->addType(
        ExternType{declName, std::move(props), builtinTypes->objectType, instanceMetatable, Tags{}, nullptr, module->name, classDecl->location}
    );

    // If the class does not define an explicit constructor, then we know the type of the default constructor at this point.
    // We handle the explicit constructor in ConstraintGenerator::visit(AstStatClass)
    if (!hasExplicitConstructor)
    {
        TypeId ctorArgTy = arena->addType(TableType{defaultConstructorProps, std::nullopt, TypeLevel{}, scope.get(), TableState::Sealed});
        constructorTy = arena->addType(FunctionType{arena->addTypePack({classObjectTy, ctorArgTy}), arena->addTypePack({classInstanceTy})});
    }

    LUAU_ASSERT(constructorTy);
    TypeId classMetatable =
        arena->addType(TableType{{{"__call", Property::readonly(constructorTy)}}, std::nullopt, TypeLevel{}, scope.get(), TableState::Sealed});

    {
        ExternType* classObject = getMutable<ExternType>(classObjectTy);
        LUAU_ASSERT(classObject);
        classObject->props = std::move(staticProps);
        classObject->parent = builtinTypes->classType;
        classObject->metatable = classMetatable;
        classObject->isOpen = classDecl->open;
    }

    // Setup a bidirectional relationship between classes and objects
    getMutable<ExternType>(classObjectTy)->relation.emplace(Obj{classInstanceTy});
    getMutable<ExternType>(classInstanceTy)->relation.emplace(Klass{classObjectTy});

    if (classDecl->exported)
        scope->exportedTypeBindings[classDecl->name->name.value] = TypeFun{{}, {}, classInstanceTy, classDecl->location};
    else
        scope->privateTypeBindings[classDecl->name->name.value] = TypeFun{{}, {}, classInstanceTy, classDecl->location};

    classDeclRecords[classDecl->name] = std::make_unique<ClassDeclRecord>(classObjectTy, classInstanceTy, std::move(memberTypes));
}

ControlFlow ConstraintGenerator::visitBlockWithoutChildScope(const ScopePtr& scope, AstStatBlock* block)
{
    RecursionCounter counter{&recursionCount};

    if (recursionCount >= DFInt::LuauConstraintGeneratorRecursionLimit)
    {
        reportCodeTooComplex(block->location);
        return ControlFlow::None;
    }

    prototypeTypeDefinitions(scope, block);

    std::optional<ControlFlow> firstControlFlow;
    for (AstStat* stat : block->body)
    {
        ControlFlow cf = visit(scope, stat);
        if (cf != ControlFlow::None && !firstControlFlow)
            firstControlFlow = cf;
    }

    return firstControlFlow.value_or(ControlFlow::None);
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStat* stat)
{
    RecursionCounter counter{&recursionCount};
    std::optional<RecursionLimiter> limiter;

    if (recursionCount >= DFInt::LuauConstraintGeneratorRecursionLimit)
    {
        reportCodeTooComplex(stat->location);
        return ControlFlow::None;
    }

    if (auto s = stat->as<AstStatBlock>())
        return visit(scope, s);
    else if (auto i = stat->as<AstStatIf>())
        return visit(scope, i);
    else if (auto s = stat->as<AstStatWhile>())
        return visit(scope, s);
    else if (auto s = stat->as<AstStatRepeat>())
        return visit(scope, s);
    else if (stat->is<AstStatBreak>())
        return ControlFlow::Breaks;
    else if (stat->is<AstStatContinue>())
        return ControlFlow::Continues;
    else if (auto r = stat->as<AstStatReturn>())
        return visit(scope, r);
    else if (auto e = stat->as<AstStatExpr>())
    {
        checkPack(scope, e->expr);

        if (auto call = e->expr->as<AstExprCall>(); call && doesCallError(call))
            return ControlFlow::Throws;

        return ControlFlow::None;
    }
    else if (auto s = stat->as<AstStatLocal>())
        return visit(scope, s);
    else if (auto s = stat->as<AstStatFor>())
        return visit(scope, s);
    else if (auto s = stat->as<AstStatForIn>())
        return visit(scope, s);
    else if (auto a = stat->as<AstStatAssign>())
        return visit(scope, a);
    else if (auto a = stat->as<AstStatCompoundAssign>())
        return visit(scope, a);
    else if (auto f = stat->as<AstStatFunction>())
        return visit(scope, f);
    else if (auto f = stat->as<AstStatLocalFunction>())
        return visit(scope, f);
    else if (auto a = stat->as<AstStatTypeAlias>())
        return visit(scope, a);
    else if (auto f = stat->as<AstStatTypeFunction>())
        return visit(scope, f);
    else if (auto s = stat->as<AstStatDeclareGlobal>())
        return visit(scope, s);
    else if (auto s = stat->as<AstStatDeclareFunction>())
        return visit(scope, s);
    else if (auto s = stat->as<AstStatDeclareExternType>())
        return visit(scope, s);
    else if (auto s = stat->as<AstStatClass>())
    {
        LUAU_ASSERT(FFlag::DebugLuauUserDefinedClasses);
        return visit(scope, s);
    }
    else if (auto s = stat->as<AstStatError>())
        return visit(scope, s);
    else
    {
        LUAU_ASSERT(0 && "Internal error: Unknown AstStat type");
        return ControlFlow::None;
    }
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatLocal* statLocal)
{
    std::vector<TypeId> annotatedTypes;
    annotatedTypes.reserve(statLocal->vars.size);
    bool hasAnnotation = false;

    std::vector<std::optional<TypeId>> expectedTypes;
    expectedTypes.reserve(statLocal->vars.size);

    std::vector<TypeId> assignees;
    assignees.reserve(statLocal->vars.size);

    // Used to name the first value type, even if it's not placed in varTypes,
    // for the purpose of synthetic name attribution.
    std::optional<TypeId> firstValueType;

    for (AstLocal* local : statLocal->vars)
    {
        const Location location = local->location;

        TypeId assignee;
        if (FFlag::DebugLuauCFG)
        {
            assignee = resolveLHSType(scope, location, CFG::LValue{Symbol{local}});
        }
        else
        {
            assignee = arena->addType(BlockedType{});
        }

        localTypes.try_insert(assignee, {});
        assignees.push_back(assignee);

        if (!firstValueType)
            firstValueType = assignee;

        if (local->annotation)
        {
            hasAnnotation = true;
            TypeId annotationTy = resolveType(scope, local->annotation, /* inTypeArguments */ false);
            annotatedTypes.push_back(annotationTy);
            expectedTypes.emplace_back(annotationTy);
            scope->bindings[local] = Binding{annotationTy, location};
        }
        else
        {
            // annotatedTypes must contain one type per local.  If a particular
            // local has no annotation at, assume the most conservative thing.
            annotatedTypes.push_back(builtinTypes->unknownType);

            expectedTypes.emplace_back(std::nullopt);
            scope->bindings[local] = Binding{builtinTypes->unknownType, location};

            inferredBindings[local] = {scope.get(), location, {assignee}};
        }

        if (!FFlag::DebugLuauCFG)
        {
            DefId def = dfg->getDef(local);
            scope->lvalueTypes[def] = assignee;
        }
    }

    Checkpoint start = checkpoint(this);
    TypePackId rvaluePack = nullptr;
    if (FFlag::LuauThreadGeneralizeThroughConstraintGeneration)
    {
        rvaluePack = checkPack(scope, statLocal->values, expectedTypes, /* generalize */ true).tp;
    }
    else
    {
        rvaluePack = checkPack_DEPRECATED(scope, statLocal->values, expectedTypes).tp;
    }
    Checkpoint end = checkpoint(this);

    std::vector<TypeId> deferredTypes;
    auto [head, tail] = flatten(rvaluePack);

    DenseHashSet<BlockedType*> freshBlockedTypes;

    for (size_t i = 0; i < statLocal->vars.size; ++i)
    {
        LUAU_ASSERT(get<BlockedType>(assignees[i]));
        TypeIds* localDomain = localTypes.find(assignees[i]);
        LUAU_ASSERT(localDomain);

        if (statLocal->vars.data[i]->annotation)
        {
            localDomain->insert(annotatedTypes[i]);
            if (i >= head.size() && tail)
            {
                deferredTypes.push_back(arena->addType(BlockedType{}));
                freshBlockedTypes.insert(getMutable<BlockedType>(deferredTypes.back()));
            }
        }
        else
        {
            if (i < head.size())
            {
                localDomain->insert(head[i]);
            }
            else if (tail)
            {
                deferredTypes.push_back(arena->addType(BlockedType{}));
                localDomain->insert(deferredTypes.back());
                freshBlockedTypes.insert(getMutable<BlockedType>(deferredTypes.back()));
            }
            else
            {
                localDomain->insert(builtinTypes->nilType);
            }
        }
    }

    if (hasAnnotation)
    {
        TypePackId annotatedPack = arena->addTypePack(std::move(annotatedTypes));
        addConstraint(scope, statLocal->location, PackSubtypeConstraint{rvaluePack, annotatedPack});
    }

    if (!deferredTypes.empty())
    {
        LUAU_ASSERT(tail);
        NotNull<Constraint> uc = addConstraint(scope, statLocal->location, UnpackConstraint{deferredTypes, *tail});

        addAllAsDependencies(start, end, this, uc);
        // This is a separate set from `deferredTypes` to
        // distinguish between blocked types we just minted
        // and blocked types that correspond to annotations.
        for (BlockedType* bt : freshBlockedTypes)
            bt->setOwner(uc);
    }

    if (statLocal->vars.size == 1 && statLocal->values.size == 1 && firstValueType && scope.get() == rootScope && !hasAnnotation)
    {
        AstLocal* var = statLocal->vars.data[0];
        AstExpr* value = statLocal->values.data[0];

        if (value->is<AstExprTable>())
            addConstraint(scope, value->location, NameConstraint{*firstValueType, var->name.value, /*synthetic*/ true});
        else if (const AstExprCall* call = value->as<AstExprCall>())
        {
            if (matchSetMetatable(*call))
                addConstraint(scope, value->location, NameConstraint{*firstValueType, var->name.value, /*synthetic*/ true});
        }
    }

    if (statLocal->values.size > 0)
    {
        // To correctly handle 'require', we need to import the exported type bindings into the variable 'namespace'.
        for (size_t i = 0; i < statLocal->values.size && i < statLocal->vars.size; ++i)
        {
            const AstExprCall* call = statLocal->values.data[i]->as<AstExprCall>();
            if (!call)
                continue;

            auto maybeRequire = matchRequire(*call);
            if (!maybeRequire)
                continue;

            AstExpr* require = *maybeRequire;

            auto moduleInfo = moduleResolver->resolveModuleInfo(module->name, *require);
            if (!moduleInfo)
                continue;

            ModulePtr module = moduleResolver->getModule(moduleInfo->name);
            if (!module)
                continue;

            const Name name{statLocal->vars.data[i]->name.value};
            scope->importedTypeBindings[name] = module->exportedTypeBindings;
            scope->importedModules[name] = moduleInfo->name;

            // Imported typeArguments of requires that transitively refer to current module have to be replaced with 'any'
            for (const auto& [location, path] : requireCycles)
            {
                if (path.empty() || path.front() != moduleInfo->name)
                    continue;

                for (auto& [name, tf] : scope->importedTypeBindings[name])
                    tf = TypeFun{{}, {}, builtinTypes->anyType};
            }
        }
    }

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatFor* for_)
{
    TypeId annotationTy = builtinTypes->numberType;
    if (for_->var->annotation)
        annotationTy = resolveType(scope, for_->var->annotation, /* inTypeArguments */ false);

    auto inferNumber = [&](AstExpr* expr)
    {
        if (!expr)
            return;

        TypeId t = check(scope, expr).ty;
        addConstraint(scope, expr->location, SubtypeConstraint{t, builtinTypes->numberType});
    };

    inferNumber(for_->from);
    inferNumber(for_->to);
    inferNumber(for_->step);

    ScopePtr forScope = childScope(for_, scope);
    forScope->bindings[for_->var] = Binding{annotationTy, for_->var->location};

    DefId def = dfg->getDef(for_->var);
    forScope->lvalueTypes[def] = annotationTy;
    updateRValueRefinements(forScope, def, annotationTy);

    visit(forScope, for_->body);

    scope->inheritAssignments(forScope);

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatForIn* forIn)
{
    ScopePtr loopScope = childScope(forIn, scope);
    TypePackId iterator = nullptr;
    if (FFlag::LuauThreadGeneralizeThroughConstraintGeneration)
    {
        iterator = checkPack(scope, forIn->values, {}, true).tp;
    }
    else
    {
        iterator = checkPack_DEPRECATED(scope, forIn->values).tp;
    }

    std::vector<TypeId> variableTypes;
    variableTypes.reserve(forIn->vars.size);

    for (AstLocal* var : forIn->vars)
    {
        TypeId loopVar = arena->addType(BlockedType{});
        variableTypes.push_back(loopVar);

        DefId def = dfg->getDef(var);

        if (var->annotation)
        {
            TypeId annotationTy = resolveType(loopScope, var->annotation, /*inTypeArguments*/ false);
            loopScope->bindings[var] = Binding{annotationTy, var->location};
            addConstraint(scope, var->location, SubtypeConstraint{loopVar, annotationTy});
            loopScope->lvalueTypes[def] = annotationTy;
        }
        else
        {
            loopScope->bindings[var] = Binding{loopVar, var->location};
            loopScope->lvalueTypes[def] = loopVar;
        }
    }

    auto iterable = addConstraint(
        loopScope, getLocation(forIn->values), IterableConstraint{iterator, variableTypes, forIn->values.data[0], &module->astForInNextTypes}
    );

    // Add an intersection ReduceConstraint for the key variable to denote that it can't be nil
    AstLocal* keyVar = *forIn->vars.begin();
    const DefId keyDef = dfg->getDef(keyVar);
    const TypeId loopVar = loopScope->lvalueTypes[keyDef];

    const TypeId intersectionTy =
        createTypeFunctionInstance(builtinTypes->typeFunctions->refineFunc, {loopVar, builtinTypes->notNilType}, {}, loopScope, keyVar->location);

    loopScope->bindings[keyVar] = Binding{intersectionTy, keyVar->location};
    loopScope->lvalueTypes[keyDef] = intersectionTy;

    auto c = addConstraint(loopScope, keyVar->location, ReduceConstraint{intersectionTy});
    cgraph->addDependencyOf(iterable, c);
    for (TypeId var : variableTypes)
    {
        auto bt = getMutable<BlockedType>(var);
        LUAU_ASSERT(bt);
        bt->setOwner(iterable);
    }

    Checkpoint start = checkpoint(this);
    visit(loopScope, forIn->body);
    Checkpoint end = checkpoint(this);

    scope->inheritAssignments(loopScope);

    // This iter constraint must dispatch first.
    addAllAsReverseDependencies(start, end, this, iterable);
    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatWhile* while_)
{
    if (FFlag::DebugLuauCFG)
    {
        check(scope, while_->condition);
        ScopePtr whileScope = childScope(while_->body, scope);
        visit(whileScope, while_->body);
        return ControlFlow::None;
    }

    RefinementId refinement = check(scope, while_->condition).refinement;

    ScopePtr whileScope = childScope(while_, scope);
    applyRefinements(whileScope, while_->condition->location, refinement);

    visit(whileScope, while_->body);

    scope->inheritAssignments(whileScope);

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatRepeat* repeat)
{
    ScopePtr repeatScope = childScope(repeat, scope);

    visitBlockWithoutChildScope(repeatScope, repeat->body);

    check(repeatScope, repeat->condition);

    scope->inheritAssignments(repeatScope);

    return ControlFlow::None;
}

static void propagateDeprecatedAttributeToConstraint(ConstraintV& c, const AstExprFunction* func)
{
    if (GeneralizationConstraint* genConstraint = c.get_if<GeneralizationConstraint>())
    {
        if (AstAttr* deprecatedAttribute = func->getAttribute(AstAttr::Type::Deprecated))
        {
            genConstraint->maybeDeprecatedAttr = deprecatedAttribute;
        }
    }
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatLocalFunction* function)
{
    // Local
    // Global
    // Dotted path
    // Self?

    TypeId functionType = nullptr;
    auto ty = scope->lookup(function->name);
    LUAU_ASSERT(!ty.has_value()); // The parser ensures that every local function has a distinct Symbol for its name.

    functionType = arena->addType(BlockedType{});
    scope->bindings[function->name] = Binding{functionType, function->name->location};

    FunctionSignature sig = checkFunctionSignature(scope, nullptr, function->func, /* expectedType */ std::nullopt, function->name->location);
    sig.bodyScope->bindings[function->name] = Binding{sig.signature, function->name->location};

    DefId def = dfg->getDef(function->name);
    scope->lvalueTypes[def] = functionType;
    updateRValueRefinements(scope, def, functionType);
    sig.bodyScope->lvalueTypes[def] = sig.signature;
    updateRValueRefinements(sig.bodyScope, def, sig.signature);

    Checkpoint start = checkpoint(this);
    checkFunctionBody(sig.bodyScope, function->func);
    Checkpoint end = checkpoint(this);

    NotNull<Scope> constraintScope{sig.signatureScope ? sig.signatureScope.get() : sig.bodyScope.get()};
    std::unique_ptr<Constraint> c =
        FFlag::LuauCyclicRequireTypeInference
            ? std::make_unique<Constraint>(
                  constraintScope, function->name->location, GeneralizationConstraint{functionType, sig.signature}, sharedModuleName
              )
            : std::make_unique<Constraint>(constraintScope, function->name->location, GeneralizationConstraint{functionType, sig.signature});

    propagateDeprecatedAttributeToConstraint(c->c, function->func);

    addAllAsDependenciesAndChainReturns(start, end, this, NotNull{c.get()});
    getMutable<BlockedType>(functionType)->setOwner(addConstraint(scope, std::move(c)));
    module->astTypes[function->func] = functionType;

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatFunction* function)
{
    // Name could be AstStatLocal, AstStatGlobal, AstStatIndexName.
    // With or without self

    Checkpoint start = checkpoint(this);
    FunctionSignature sig = checkFunctionSignature(scope, nullptr, function->func, /* expectedType */ std::nullopt, function->name->location);

    DefId def = dfg->getDef(function->name);

    if (AstExprLocal* localName = function->name->as<AstExprLocal>())
    {
        sig.bodyScope->bindings[localName->local] = Binding{sig.signature, localName->location};
        sig.bodyScope->lvalueTypes[def] = sig.signature;
        updateRValueRefinements(sig.bodyScope, def, sig.signature);
    }
    else if (AstExprGlobal* globalName = function->name->as<AstExprGlobal>())
    {
        sig.bodyScope->bindings[globalName->name] = Binding{sig.signature, globalName->location};
        sig.bodyScope->lvalueTypes[def] = sig.signature;
        updateRValueRefinements(sig.bodyScope, def, sig.signature);
    }
    else if (function->name->is<AstExprIndexName>())
    {
        updateRValueRefinements(sig.bodyScope, def, sig.signature);
    }

    if (auto indexName = function->name->as<AstExprIndexName>())
    {
        auto beginProp = checkpoint(this);
        auto [fn, _] = check(scope, indexName);
        auto endProp = checkpoint(this);
        auto pftc = addConstraint(
            sig.signatureScope,
            function->func->location,
            PushFunctionTypeConstraint{
                fn,
                sig.signature,
                NotNull{function->func},
                /* isSelf */ indexName->op == ':',
            }
        );

        addAllAsDependencies(beginProp, endProp, this, pftc);

        auto beginBody = checkpoint(this);
        checkFunctionBody(sig.bodyScope, function->func);
        auto endBody = checkpoint(this);

        addAllAsReverseDependencies(beginBody, endBody, this, pftc);
    }
    else
    {
        checkFunctionBody(sig.bodyScope, function->func);
    }

    Checkpoint end = checkpoint(this);

    TypeId generalizedType = arena->addType(BlockedType{});
    const ScopePtr& constraintScope = sig.signatureScope ? sig.signatureScope : sig.bodyScope;

    NotNull<Constraint> c = addConstraint(constraintScope, function->name->location, GeneralizationConstraint{generalizedType, sig.signature});
    getMutable<BlockedType>(generalizedType)->setOwner(c);

    propagateDeprecatedAttributeToConstraint(c->c, function->func);

    addAllAsDependenciesAndChainReturns(start, end, this, c);
    std::optional<TypeId> existingFunctionTy = follow(lookup(scope, function->name->location, def));

    if (AstExprLocal* localName = function->name->as<AstExprLocal>())
    {
        visitLValue(scope, localName, generalizedType);

        scope->bindings[localName->local] = Binding{sig.signature, localName->location};
        scope->lvalueTypes[def] = sig.signature;
    }
    else if (AstExprGlobal* globalName = function->name->as<AstExprGlobal>())
    {
        if (!existingFunctionTy)
            ice->ice("prepopulateGlobalScope did not populate a global name", globalName->location);

        if (auto bt = get<BlockedType>(*existingFunctionTy); bt && uninitializedGlobals.contains(globalName->name))
        {
            LUAU_ASSERT(bt->getOwner() == nullptr);
            uninitializedGlobals.erase(globalName->name);
            emplaceType<BoundType>(asMutable(*existingFunctionTy), generalizedType);
        }


        scope->bindings[globalName->name] = Binding{sig.signature, globalName->location};
        scope->lvalueTypes[def] = sig.signature;
    }
    else if (AstExprIndexName* indexName = function->name->as<AstExprIndexName>())
    {
        visitLValue(scope, indexName, generalizedType);
    }
    else if (function->name->is<AstExprError>())
    {
        generalizedType = builtinTypes->errorType;
    }

    if (generalizedType == nullptr)
        ice->ice("generalizedType == nullptr", function->location);

    updateRValueRefinements(scope, def, generalizedType);

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatReturn* ret)
{
    // At this point, the only way scope->returnType should have anything
    // interesting in it is if the function has an explicit return annotation.
    // If this is the case, then we can expect that the return expression
    // conforms to that.
    std::vector<std::optional<TypeId>> expectedTypes;
    for (TypeId ty : scope->returnType)
        expectedTypes.emplace_back(ty);
    TypePackId exprTypes = nullptr;
    if (FFlag::LuauThreadGeneralizeThroughConstraintGeneration)
    {
        exprTypes = checkPack(scope, ret->list, expectedTypes, false).tp;
    }
    else
    {
        exprTypes = checkPack_DEPRECATED(scope, ret->list, expectedTypes).tp;
    }
    addConstraint(scope, ret->location, PackSubtypeConstraint{exprTypes, scope->returnType, /*returns*/ true});

    return ControlFlow::Returns;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatBlock* block)
{
    ScopePtr innerScope = childScope(block, scope);

    ControlFlow flow = visitBlockWithoutChildScope(innerScope, block);

    // An AstStatBlock has linear control flow, i.e. one entry and one exit, so we can inherit
    // all the changes to the environment occurred by the statements in that block.
    if (!FFlag::DebugLuauCFG)
    {
        scope->inheritRefinements(innerScope);
        scope->inheritAssignments(innerScope);
    }


    return flow;
}

// TODO Clip?
static void bindFreeType(TypeId a, TypeId b)
{
    FreeType* af = getMutable<FreeType>(a);
    FreeType* bf = getMutable<FreeType>(b);

    LUAU_ASSERT(af || bf);

    if (!bf)
        emplaceType<BoundType>(asMutable(a), b);
    else if (!af)
        emplaceType<BoundType>(asMutable(b), a);
    else if (subsumes(bf->scope, af->scope))
        emplaceType<BoundType>(asMutable(a), b);
    else if (subsumes(af->scope, bf->scope))
        emplaceType<BoundType>(asMutable(b), a);
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatAssign* assign)
{
    TypePackId resultPack;
    if (FFlag::LuauThreadGeneralizeThroughConstraintGeneration)
    {
        resultPack = checkPack(scope, assign->values, {}, true).tp;
    }
    else
    {
        resultPack = checkPack_DEPRECATED(scope, assign->values).tp;
    }

    std::vector<TypeId> valueTypes;
    valueTypes.reserve(assign->vars.size);

    auto [head, tail] = flatten(resultPack);
    if (head.size() >= assign->vars.size)
    {
        // If the resultPack is definitely long enough for each variable, we can
        // skip the UnpackConstraint and use the result typeArguments directly.

        for (size_t i = 0; i < assign->vars.size; ++i)
            valueTypes.push_back(head[i]);
    }
    else
    {
        // We're not sure how many typeArguments are produced by the right-side
        // expressions.  We'll use an UnpackConstraint to defer this until
        // later.
        for (size_t i = 0; i < assign->vars.size; ++i)
            valueTypes.push_back(arena->addType(BlockedType{}));

        auto uc = addConstraint(scope, assign->location, UnpackConstraint{valueTypes, resultPack});

        for (TypeId t : valueTypes)
            getMutable<BlockedType>(t)->setOwner(uc);
    }

    for (size_t i = 0; i < assign->vars.size; ++i)
    {
        visitLValue(scope, assign->vars.data[i], valueTypes[i]);
    }

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatCompoundAssign* assign)
{
    TypeId resultTy = checkAstExprBinary(scope, assign->location, assign->op, assign->var, assign->value, std::nullopt).ty;
    module->astCompoundAssignResultTypes[assign] = resultTy;
    // NOTE: We do not update lvalues for compound assignments. This is
    // intentional.
    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatIf* ifStatement)
{
    if (FFlag::DebugLuauCFG)
    {
        // TODO CLI-222927: `if local`/`if const` support in CFG branch left for later as its design isn't fully complete
        check(scope, ifStatement->condition, std::nullopt);
        ScopePtr thenScope = childScope(ifStatement->thenbody, scope);

        visit(thenScope, ifStatement->thenbody);
        if (ifStatement->elsebody)
        {
            ScopePtr elseScope = childScope(ifStatement->elsebody ? ifStatement->elsebody : ifStatement, scope);
            visit(elseScope, ifStatement->elsebody);
        }
        return ControlFlow::None;
    }
    else
    {
        ScopePtr thenScope = childScope(ifStatement->thenbody, scope);
        ScopePtr elseScope = childScope(ifStatement->elsebody ? ifStatement->elsebody : ifStatement, scope);

        if (FFlag::LuauExperimentalIfLocalAnalysis && ifStatement->conditionLocal)
        {
            std::optional<TypeId> annotatedType;
            if (ifStatement->conditionLocal->annotation)
                annotatedType = resolveType(scope, ifStatement->conditionLocal->annotation, /* inTypeArguments */ false);

            TypeId initType = [&]()
            {
                InConditionalContext flipper{&typeContext};
                return check(scope, ifStatement->condition, annotatedType).ty;
            }();

            TypeId baseType = annotatedType ? *annotatedType : initType;
            TypeId boundType = createTypeFunctionInstance(
                builtinTypes->typeFunctions->refineFunc, {baseType, builtinTypes->truthyType}, {}, thenScope, ifStatement->conditionLocal->location
            );

            thenScope->bindings[ifStatement->conditionLocal] = Binding{boundType, ifStatement->conditionLocal->location};

            DefId def = dfg->getDef(ifStatement->conditionLocal);
            thenScope->lvalueTypes[def] = boundType;
        }
        else
        {
            RefinementId refinement = [&]()
            {
                InConditionalContext flipper{&typeContext};
                return check(scope, ifStatement->condition, std::nullopt).refinement;
            }();

            applyRefinements(thenScope, ifStatement->condition->location, refinement);
            applyRefinements(elseScope, ifStatement->elseLocation.value_or(ifStatement->condition->location), refinementArena.negation(refinement));
        }

        ControlFlow thencf = visit(thenScope, ifStatement->thenbody);
        ControlFlow elsecf = ControlFlow::None;
        if (ifStatement->elsebody)
            elsecf = visit(elseScope, ifStatement->elsebody);

        if (thencf != ControlFlow::None && elsecf == ControlFlow::None)
            scope->inheritRefinements(elseScope);
        else if (thencf == ControlFlow::None && elsecf != ControlFlow::None)
            scope->inheritRefinements(thenScope);

        if (thencf == ControlFlow::None)
            scope->inheritAssignments(thenScope);
        if (elsecf == ControlFlow::None)
            scope->inheritAssignments(elseScope);

        if (thencf == elsecf)
            return thencf;
        else if (matches(thencf, ControlFlow::Returns | ControlFlow::Throws) && matches(elsecf, ControlFlow::Returns | ControlFlow::Throws))
            return ControlFlow::Returns;
        else
            return ControlFlow::None;
    }
}

void ConstraintGenerator::resolveGenericDefaultParameters(const ScopePtr& defnScope, AstStatTypeAlias* alias, const TypeFun& fun)
{
    LUAU_ASSERT(alias->generics.size == fun.typeParams.size());
    for (size_t i = 0; i < alias->generics.size; i++)
    {
        auto astTy = alias->generics.data[i];
        auto param = fun.typeParams[i];
        if (param.defaultValue && astTy->defaultValue != nullptr)
        {
            auto resolvesTo = astTy->defaultValue;
            auto toUnblock = *param.defaultValue;
            emplaceType<BoundType>(asMutable(toUnblock), resolveType(defnScope, resolvesTo, /*  inTypeArguments */ false));
        }
        defnScope->privateTypeBindings[astTy->name.value] = TypeFun{param.ty};
    }

    LUAU_ASSERT(alias->genericPacks.size == fun.typePackParams.size());
    for (size_t i = 0; i < alias->genericPacks.size; i++)
    {
        auto astPack = alias->genericPacks.data[i];
        auto param = fun.typePackParams[i];
        if (param.defaultValue && astPack->defaultValue != nullptr)
        {
            auto resolvesTo = astPack->defaultValue;
            auto toUnblock = *param.defaultValue;
            emplaceTypePack<BoundTypePack>(asMutable(toUnblock), resolveTypePack(defnScope, resolvesTo, /*  inTypeArguments */ false));
        }
        defnScope->privateTypePackBindings[astPack->name.value] = param.tp;
    }
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatTypeAlias* alias)
{
    if (alias->name == kParseNameError)
        return ControlFlow::None;

    if (alias->name == "typeof")
    {
        reportError(alias->location, ReservedIdentifier{"typeof"});
        return ControlFlow::None;
    }

    scope->typeAliasLocations[alias->name.value] = alias->location;
    scope->typeAliasNameLocations[alias->name.value] = alias->nameLocation;

    ScopePtr* defnScopePtr = astTypeAliasDefiningScopes.find(alias);

    std::unordered_map<Name, TypeFun>* typeBindings;
    if (alias->exported)
        typeBindings = &scope->exportedTypeBindings;
    else
        typeBindings = &scope->privateTypeBindings;

    // These will be undefined if the alias was a duplicate definition, in which
    // case we just skip over it.
    auto bindingIt = typeBindings->find(alias->name.value);
    if (bindingIt == typeBindings->end() || defnScopePtr == nullptr)
        return ControlFlow::None;

    ScopePtr defnScope = *defnScopePtr;
    resolveGenericDefaultParameters(defnScope, alias, bindingIt->second);

    TypeId ty = resolveType(
        defnScope,
        alias->type,
        /* inTypeArguments */ false,
        /* replaceErrorWithFresh */ false
    );

    TypeId aliasTy = bindingIt->second.type;
    LUAU_ASSERT(get<BlockedType>(aliasTy));
    if (occursCheck(aliasTy, ty))
    {
        emplaceType<BoundType>(asMutable(aliasTy), builtinTypes->anyType);
        reportError(alias->nameLocation, OccursCheckFailed{});
    }
    else
        emplaceType<BoundType>(asMutable(aliasTy), ty);

    std::vector<TypeId> typeParams;
    for (const auto& tyParam : createGenerics(defnScope, alias->generics, /* useCache */ true, /* addTypes */ false))
        typeParams.push_back(tyParam.second.ty);

    std::vector<TypePackId> typePackParams;
    for (const auto& tpParam : createGenericPacks(defnScope, alias->genericPacks, /* useCache */ true, /* addTypes */ false))
        typePackParams.push_back(tpParam.second.tp);

    addConstraint(
        scope,
        alias->type->location,
        NameConstraint{
            ty,
            alias->name.value,
            /*synthetic=*/false,
            std::move(typeParams),
            std::move(typePackParams),
        }
    );

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatTypeFunction* function)
{
    if (function->name == "typeof")
    {
        reportError(function->location, ReservedIdentifier{"typeof"});
    }

    auto scopeIt = astTypeFunctionEnvironmentScopes.find(function);
    LUAU_ASSERT(scopeIt);

    ScopePtr environmentScope = *scopeIt;

    Checkpoint startCheckpoint = checkpoint(this);
    FunctionSignature sig = checkFunctionSignature(environmentScope, nullptr, function->body, /* expectedType */ std::nullopt);

    // Place this function as a child of the non-type function scope
    scope->children.emplace_back(sig.signatureScope.get());
    interiorFreeTypes.emplace_back();
    checkFunctionBody(sig.bodyScope, function->body);
    Checkpoint endCheckpoint = checkpoint(this);

    TypeId generalizedTy = arena->addType(BlockedType{});
    NotNull<Constraint> gc = addConstraint(
        sig.signatureScope,
        function->location,
        GeneralizationConstraint{
            generalizedTy,
            sig.signature,
        }
    );

    sig.signatureScope->interiorFreeTypes = std::move(interiorFreeTypes.back().types);
    sig.signatureScope->interiorFreeTypePacks = std::move(interiorFreeTypes.back().typePacks);

    getMutable<BlockedType>(generalizedTy)->setOwner(gc);
    interiorFreeTypes.pop_back();

    addAllAsDependenciesAndChainReturns(startCheckpoint, endCheckpoint, this, gc);
    std::optional<TypeId> existingFunctionTy = environmentScope->lookup(function->name);

    if (!existingFunctionTy)
        ice->ice("checkAliases did not populate type function name", function->nameLocation);

    TypeId unpackedTy = follow(*existingFunctionTy);

    if (auto bt = get<BlockedType>(unpackedTy); bt && nullptr == bt->getOwner())
        emplaceType<BoundType>(asMutable(unpackedTy), generalizedTy);

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatDeclareGlobal* global)
{
    LUAU_ASSERT(global->type);

    TypeId globalTy = resolveType(scope, global->type, /* inTypeArguments */ false);
    Name globalName(global->name.value);

    module->declaredGlobals[globalName] = globalTy;
    rootScope->bindings[global->name] = Binding{globalTy, global->location};

    DefId def = dfg->getDef(global);
    rootScope->lvalueTypes[def] = globalTy;
    updateRValueRefinements(rootScope, def, globalTy);

    return ControlFlow::None;
}

static bool isMetamethod(const Name& name)
{
    return name == "__index" || name == "__newindex" || name == "__call" || name == "__concat" || name == "__unm" || name == "__add" ||
           name == "__sub" || name == "__mul" || name == "__div" || name == "__mod" || name == "__pow" || name == "__tostring" ||
           name == "__metatable" || name == "__eq" || name == "__lt" || name == "__le" || name == "__mode" || name == "__iter" || name == "__len" ||
           name == "__idiv";
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatDeclareExternType* declaredExternType)
{
    // If a class with the same name was already defined, we skip over
    auto bindingIt = scope->exportedTypeBindings.find(declaredExternType->name.value);
    if (bindingIt == scope->exportedTypeBindings.end())
        return ControlFlow::None;

    std::optional<TypeId> superTy = std::make_optional(builtinTypes->externType);
    if (declaredExternType->superName)
    {
        Name superName = Name(declaredExternType->superName->value);
        std::optional<TypeFun> lookupType = scope->lookupType(superName);

        if (!lookupType)
        {
            reportError(declaredExternType->location, UnknownSymbol{std::move(superName), UnknownSymbol::Type});
            return ControlFlow::None;
        }

        // We don't have generic extern typeArguments, so this assertion _should_ never be hit.
        LUAU_ASSERT(lookupType->typeParams.size() == 0 && lookupType->typePackParams.size() == 0);
        superTy = follow(lookupType->type);

        if (!get<ExternType>(follow(*superTy)))
        {
            reportError(
                declaredExternType->location,
                GenericError{
                    format("Cannot use non-class type '%s' as a superclass of class '%s'", superName.c_str(), declaredExternType->name.value)
                }
            );

            // If we don't emplace an error type here, then later we'll be
            // exposing a blocked type in this file's type interface. This
            // is _normally_ harmless.
            emplaceType<BoundType>(asMutable(bindingIt->second.type), builtinTypes->errorType);

            return ControlFlow::None;
        }
    }

    Name className(declaredExternType->name.value);

    TypeId externTy = arena->addType(ExternType(std::move(className), {}, superTy, std::nullopt, {}, {}, module->name, declaredExternType->location));
    ExternType* etv = getMutable<ExternType>(externTy);

    TypeId metaTy = arena->addType(TableType{TableState::Sealed, scope->level, scope.get()});
    TableType* metatable = getMutable<TableType>(metaTy);

    etv->metatable = metaTy;

    TypeId classBindTy = bindingIt->second.type;
    emplaceType<BoundType>(asMutable(classBindTy), externTy);

    if (declaredExternType->indexer)
    {
        if (recursionCount >= DFInt::LuauConstraintGeneratorRecursionLimit)
        {
            reportCodeTooComplex(declaredExternType->indexer->location);
        }
        else
        {
            // I don't think extern types can *be* generic, but if they
            // have an indexer over those generics, the polarity is
            // mixed.
            etv->indexer = TableIndexer{
                resolveType(
                    scope,
                    declaredExternType->indexer->indexType,
                    /* inTypeArguments */ false,
                    /* replaceErrorWithFresh */ false,
                    /* initialPolarity */ Polarity::Mixed
                ),
                resolveType(
                    scope,
                    declaredExternType->indexer->resultType,
                    /* inTypeArguments */ false,
                    /* replaceErrorWithFresh */ false,
                    /* initialPolarity */ Polarity::Mixed
                ),
            };
        }
    }

    for (const AstDeclaredExternTypeProperty& externProp : declaredExternType->props)
    {
        Name propName(externProp.name.value);
        TypeId propTy =
            resolveType(scope, externProp.ty, /* inTypeArguments */ false, /* replaceErrorWithFresh */ false, /* initialPolarity */ Polarity::Mixed);

        bool assignToMetatable = isMetamethod(propName);

        // Function typeArguments always take 'self', but this isn't reflected in the
        // parsed annotation. Add it here.
        if (externProp.isMethod)
        {
            if (FunctionType* ftv = getMutable<FunctionType>(propTy))
            {
                ftv->argNames.insert(ftv->argNames.begin(), FunctionArgument{"self", {}});
                ftv->argTypes = addTypePack({externTy}, ftv->argTypes);

                ftv->hasSelf = true;

                FunctionDefinition defn;

                defn.definitionModuleName = module->name;
                defn.definitionLocation = externProp.location;
                // No data is preserved for varargLocation
                defn.originalNameLocation = externProp.nameLocation;

                ftv->definition = defn;
            }
        }

        TableType::Props& props = assignToMetatable ? metatable->props : etv->props;

        if (props.count(propName) == 0)
        {
            Property tableProp;

            if (externProp.access == AstTableAccess::Read)
                tableProp = Property::readonly(propTy);
            else if (externProp.access == AstTableAccess::Write)
                tableProp = Property::writeonly(propTy);
            else
                tableProp = Property::rw(propTy);

            tableProp.location = externProp.location;

            props[propName] = tableProp;
        }
        else
        {
            Luau::Property& prop = props[propName];
            bool addedWriteTypeByOverload = false;

            if (auto readTy = prop.readTy)
            {
                // We special-case this logic to keep the intersection flat; otherwise we
                // would create a ton of nested intersection typeArguments.
                if (const IntersectionType* itv = get<IntersectionType>(*readTy))
                {
                    std::vector<TypeId> options = itv->parts;
                    options.push_back(propTy);
                    TypeId newItv = arena->addType(IntersectionType{std::move(options)});

                    prop.readTy = newItv;
                }
                else if (get<FunctionType>(*readTy))
                {
                    TypeId intersection = arena->addType(IntersectionType{{*readTy, propTy}});

                    prop.readTy = intersection;
                }
                else if (externProp.access == AstTableAccess::Write && !prop.writeTy.has_value())
                {
                    prop.writeTy = propTy;
                    addedWriteTypeByOverload = true;
                }
                else
                    reportError(
                        declaredExternType->location,
                        GenericError{format("Cannot overload read type of non-function extern type member '%s'", propName.c_str())}
                    );
            }

            if (auto writeTy = prop.writeTy; writeTy && !addedWriteTypeByOverload)
            {
                // We special-case this logic to keep the intersection flat; otherwise we
                // would create a ton of nested intersection typeArguments.
                if (const IntersectionType* itv = get<IntersectionType>(*writeTy))
                {
                    std::vector<TypeId> options = itv->parts;
                    options.push_back(propTy);
                    TypeId newItv = arena->addType(IntersectionType{std::move(options)});

                    prop.writeTy = newItv;
                }
                else if (get<FunctionType>(*writeTy))
                {
                    TypeId intersection = arena->addType(IntersectionType{{*writeTy, propTy}});

                    prop.writeTy = intersection;
                }
                else if (externProp.access == AstTableAccess::Read && !prop.readTy.has_value())
                    prop.readTy = propTy;
                else
                    reportError(
                        declaredExternType->location,
                        GenericError{format("Cannot overload write type of non-function extern type member '%s'", propName.c_str())}
                    );
            }
        }
    }

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatDeclareFunction* global)
{
    std::vector<std::pair<Name, GenericTypeDefinition>> generics = createGenerics(scope, global->generics);
    std::vector<std::pair<Name, GenericTypePackDefinition>> genericPacks = createGenericPacks(scope, global->genericPacks);

    std::vector<TypeId> genericTys;
    genericTys.reserve(generics.size());
    for (auto& [name, generic] : generics)
    {
        genericTys.push_back(generic.ty);
    }

    std::vector<TypePackId> genericTps;
    genericTps.reserve(genericPacks.size());
    for (auto& [name, generic] : genericPacks)
    {
        genericTps.push_back(generic.tp);
    }

    ScopePtr funScope = scope;
    if (!generics.empty() || !genericPacks.empty())
        funScope = childScope(global, scope);

    TypePackId paramPack = resolveTypePack(
        funScope, global->params, /* inTypeArguments */ false, /* replaceErrorWithFresh */ false, /* initialPolarity */ Polarity::Negative
    );
    TypePackId retPack = resolveTypePack(
        funScope, global->retTypes, /* inTypeArguments */ false, /* replaceErrorWithFresh */ false, /* initialPolarity */ Polarity::Positive
    );

    FunctionDefinition defn;

    defn.definitionModuleName = module->name;
    defn.definitionLocation = global->location;
    defn.varargLocation = global->vararg ? std::make_optional(global->varargLocation) : std::nullopt;
    defn.originalNameLocation = global->nameLocation;

    TypeId fnType = arena->addType(FunctionType{TypeLevel{}, std::move(genericTys), std::move(genericTps), paramPack, retPack, defn});

    FunctionType* ftv = getMutable<FunctionType>(fnType);
    ftv->isCheckedFunction = global->isCheckedFunction();
    AstAttr* deprecatedAttr = global->getAttribute(AstAttr::Type::Deprecated);
    ftv->isDeprecatedFunction = deprecatedAttr != nullptr;
    if (deprecatedAttr)
    {
        ftv->deprecatedInfo = std::make_shared<AstAttr::DeprecatedInfo>(deprecatedAttr->deprecatedInfo());
    }

    ftv->argNames.reserve(global->paramNames.size);
    for (const auto& el : global->paramNames)
        ftv->argNames.emplace_back(FunctionArgument{el.first.value, el.second});
    Name fnName(global->name.value);

    module->declaredGlobals[fnName] = fnType;
    scope->bindings[global->name] = Binding{fnType, global->location};

    DefId def = dfg->getDef(global);
    rootScope->lvalueTypes[def] = fnType;
    updateRValueRefinements(rootScope, def, fnType);

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatClass* statClass)
{
    LUAU_ASSERT(FFlag::DebugLuauUserDefinedClasses);

    if (statClass->super)
        check(scope, statClass->super);

    const std::unique_ptr<ClassDeclRecord>* classDeclRecordPtr = classDeclRecords.find(statClass->name);
    // TODO CLI-199124: This is unpopulated in fragment autocomplete.
    if (classDeclRecordPtr == nullptr)
        return ControlFlow::None;

    NotNull<ClassDeclRecord> classDeclRecord{classDeclRecordPtr->get()};

    for (const auto& member : statClass->members)
    {
        Luau::visit(
            overloaded{
                [&](const AstClassProperty& classProp)
                {
                    auto entry = classDeclRecord->memberTypes.find(classProp.name);
                    if (entry == nullptr)
                    {
                        LUAU_ASSERT(!"Unexpected missing class property type");
                        return;
                    }

                    auto blockedTy = follow(*entry);
                    if (!is<BlockedType>(blockedTy))
                        return;

                    auto target = classProp.ty ? resolveType(scope, classProp.ty, false) : builtinTypes->anyType;
                    emplaceType<BoundType>(asMutable(blockedTy), target);
                },
                [&](const AstClassMethod& method)
                {
                    auto entry = classDeclRecord->memberTypes.find(method.functionName);
                    if (entry == nullptr)
                    {
                        LUAU_ASSERT(!"Unexpected missing class method type");
                        return;
                    }

                    auto functionType = follow(*entry);

                    // TODO: This might have strange behavior if you ever
                    // copy a method.
                    if (!is<BlockedType>(functionType))
                        return;

                    FunctionSignature sig =
                        checkFunctionSignature(scope, classDeclRecord, method.function, /* expectedType */ std::nullopt, method.function->location);

                    Checkpoint start = checkpoint(this);
                    checkFunctionBody(sig.bodyScope, method.function);
                    Checkpoint end = checkpoint(this);

                    NotNull<Scope> constraintScope{sig.signatureScope ? sig.signatureScope.get() : sig.bodyScope.get()};

                    NotNull<Constraint> genConstraint = addConstraint(
                        scope,
                        FFlag::LuauCyclicRequireTypeInference
                            ? std::make_unique<Constraint>(
                                  constraintScope, method.function->location, GeneralizationConstraint{functionType, sig.signature}, sharedModuleName
                              )
                            : std::make_unique<Constraint>(
                                  constraintScope, method.function->location, GeneralizationConstraint{functionType, sig.signature}
                              )
                    );

                    propagateDeprecatedAttributeToConstraint(genConstraint->c, method.function);

                    addAllAsDependenciesAndChainReturns(start, end, this, genConstraint);

                    getMutable<BlockedType>(functionType)->setOwner(genConstraint);

                    if (method.functionName == "__init")
                    {
                        std::optional<TypeId> classTy_ = classDeclRecord->classTy;
                        LUAU_ASSERT(classTy_.has_value());
                        TypeId classTy = follow(*classTy_);

                        // The signature of ClassName() is the same as that of __init() except with the class itself as the leading argument instead
                        // of self. It also always returns an instance of the class.
                        const FunctionType* initFn = get<FunctionType>(sig.signature);
                        LUAU_ASSERT(initFn);

                        TypePackId constructorArgs = nullptr;

                        auto iter = begin(initFn->argTypes);
                        auto endIter = Luau::end(initFn->argTypes);
                        if (iter == endIter)
                        {
                            // The parser complains if __init() does not take self as its first argument.
                            constructorArgs = iter.tail().value_or(builtinTypes->emptyTypePack);
                        }
                        else
                        {
                            // Skip the first argument (self).  Collect the rest.
                            ++iter;
                            constructorArgs = typePackFromIterator(arena, iter, endIter);
                        }

                        LUAU_ASSERT(constructorArgs != nullptr);

                        // Copy all properties of the __init function except for its first argument, return type, and hasSelf.
                        FunctionType constructorFunction = *initFn;
                        // __call metamethod implicitly passes the class as the first argument
                        constructorFunction.argTypes = arena->addTypePack({classTy}, constructorArgs);
                        constructorFunction.retTypes = arena->addTypePack({classDeclRecord->instanceTy});
                        constructorFunction.hasSelf = false;

                        // Also clip self and the return pack from the generic list.
                        auto eraseValue = [](auto& vec, auto val)
                        {
                            vec.erase(std::remove(vec.begin(), vec.end(), val), vec.end());
                        };
                        eraseValue(constructorFunction.generics, classDeclRecord->instanceTy);
                        eraseValue(constructorFunction.genericPacks, initFn->retTypes);

                        TypeId constructorFn = arena->addType(std::move(constructorFunction));

                        const ExternType* classExternTy = get<ExternType>(classTy);
                        LUAU_ASSERT(classExternTy && classExternTy->metatable);
                        TableType* classMetatable = getMutable<TableType>(follow(*classExternTy->metatable));
                        LUAU_ASSERT(classMetatable);
                        std::optional<TypeId> classCallTy = classMetatable->props["__call"].readTy;
                        LUAU_ASSERT(classCallTy);
                        LUAU_ASSERT(is<BlockedType>(*classCallTy));
                        emplaceType<BoundType>(asMutable(*classCallTy), constructorFn);
                    }
                }
            },
            member
        );
    }

    if (statClass->super)
    {
        const TypeId classInstanceTy = classDeclRecord->instanceTy;

        TypeId superTy = builtinTypes->errorType;

        // The superclass is an "expression" but it's also a type.  This is a
        // bit kooky.
        //
        // * It could be a bare identifier which indicates a class type in the
        //   current scope.

        auto lookupClass = [&scope, this](AstName name)
        {
            auto tf = scope->lookupType(name.value);
            if (!tf.has_value())
            {
                // If there is no type by this name, but there is a value, the
                // developer has probably extended something they shouldn't
                // have. We grab it here and retain it anyway for error
                // reporting.
                return scope->lookup(name).value_or(builtinTypes->errorType);
            }
            else if (!tf->typePackParams.empty() || !tf->typeParams.empty())
            {
                LUAU_ASSERT(!"Classes cannot yet inherit from generics");
                return builtinTypes->errorType;
            }
            else
            {
                TypeId t = follow(tf->type);
                if (is<ExternType>(t))
                    return t;

                return builtinTypes->errorType;
            }
        };

        if (auto astLocal = statClass->super->as<AstExprLocal>())
            superTy = lookupClass(astLocal->local->name);
        else if (auto astGlobal = statClass->super->as<AstExprGlobal>())
            superTy = lookupClass(astGlobal->name);

        // * It could be ModuleName.TypeName, which indicates a class in another
        //   module.

        else if (auto indexName = statClass->super->as<AstExprIndexName>())
        {
            if (auto baseLocal = indexName->expr->as<AstExprLocal>())
            {
                std::optional<TypeFun> tf;

                if (auto imported = scope->importedTypeBindings.find(baseLocal->local->name.value); imported != scope->importedTypeBindings.end())
                {
                    if (auto binding = imported->second.find(indexName->index.value); binding != imported->second.end())
                        tf = binding->second;
                }

                if (!tf.has_value())
                    superTy = builtinTypes->errorType;
                else
                {
                    if (!tf->typeParams.empty() || !tf->typePackParams.empty())
                    {
                        LUAU_ASSERT(!"Classes cannot yet inherit from generics");
                        superTy = builtinTypes->errorType;
                    }
                    else
                    {
                        TypeId t = follow(tf->type);
                        if (is<ExternType>(t))
                            superTy = tf->type;
                    }
                }
            }
        }

        // * It could be something else entirely, in which case I think we just
        //   inherit from `error` and hope for the best.

        // Check for an inheritance cycle.  If there is, this class's base class
        // is then errorType.
        TypeId cycleTest = superTy;
        while (cycleTest)
        {
            cycleTest = follow(cycleTest);

            if (cycleTest == classInstanceTy)
            {
                // Cyclic inheritance detected
                superTy = arena->addType(ErrorType{superTy});
                break;
            }

            auto et = get<ExternType>(follow(cycleTest));
            if (!et)
                break;

            cycleTest = et->parent.value_or(nullptr);
        }

        ExternType* classExtern = getMutable<ExternType>(classInstanceTy);
        classExtern->parent = superTy;
    }

    return ControlFlow::None;
}

ControlFlow ConstraintGenerator::visit(const ScopePtr& scope, AstStatError* error)
{
    for (AstStat* stat : error->statements)
        visit(scope, stat);
    for (AstExpr* expr : error->expressions)
        check(scope, expr);

    return ControlFlow::None;
}

InferencePack ConstraintGenerator::checkPack(
    const ScopePtr& scope,
    AstArray<AstExpr*> exprs,
    const std::vector<std::optional<TypeId>>& expectedTypes,
    bool generalize
)
{
    LUAU_ASSERT(FFlag::LuauThreadGeneralizeThroughConstraintGeneration);
    std::vector<TypeId> head;
    std::optional<TypePackId> tail;

    for (size_t i = 0; i < exprs.size; ++i)
    {
        AstExpr* expr = exprs.data[i];
        if (i < exprs.size - 1)
        {
            std::optional<TypeId> expectedType;
            if (i < expectedTypes.size())
                expectedType = expectedTypes[i];
            head.push_back(check(scope, expr, expectedType, /* forceSingleton */ false, generalize).ty);
        }
        else
        {
            std::vector<std::optional<TypeId>> expectedTailTypes;
            if (i < expectedTypes.size())
                expectedTailTypes.assign(begin(expectedTypes) + i, end(expectedTypes));
            tail = checkPack(scope, expr, expectedTailTypes, generalize).tp;
        }
    }

    return InferencePack{addTypePack(std::move(head), tail)};
}

InferencePack ConstraintGenerator::checkPack_DEPRECATED(
    const ScopePtr& scope,
    AstArray<AstExpr*> exprs,
    const std::vector<std::optional<TypeId>>& expectedTypes
)
{
    LUAU_ASSERT(!FFlag::LuauThreadGeneralizeThroughConstraintGeneration);
    std::vector<TypeId> head;
    std::optional<TypePackId> tail;

    for (size_t i = 0; i < exprs.size; ++i)
    {
        AstExpr* expr = exprs.data[i];
        if (i < exprs.size - 1)
        {
            std::optional<TypeId> expectedType;
            if (i < expectedTypes.size())
                expectedType = expectedTypes[i];
            head.push_back(check(scope, expr, expectedType).ty);
        }
        else
        {
            std::vector<std::optional<TypeId>> expectedTailTypes;
            if (i < expectedTypes.size())
                expectedTailTypes.assign(begin(expectedTypes) + i, end(expectedTypes));
            tail = checkPack(scope, expr, expectedTailTypes).tp;
        }
    }

    return InferencePack{addTypePack(std::move(head), tail)};
}

InferencePack ConstraintGenerator::checkPack(
    const ScopePtr& scope,
    AstExpr* expr,
    const std::vector<std::optional<TypeId>>& expectedTypes,
    bool generalize
)
{
    RecursionCounter counter{&recursionCount};

    if (recursionCount >= DFInt::LuauConstraintGeneratorRecursionLimit)
    {
        reportCodeTooComplex(expr->location);
        return InferencePack{builtinTypes->errorTypePack};
    }

    InferencePack result;

    if (AstExprCall* call = expr->as<AstExprCall>())
    {
        if (!expectedTypes.empty() && matchSetMetatable(*call))
            result = checkPack(scope, call, expectedTypes.front());
        else
            result = checkPack(scope, call);
    }
    else if (expr->is<AstExprVarargs>())
    {
        if (scope->varargPack)
            result = InferencePack{*scope->varargPack};
        else
            result = InferencePack{builtinTypes->errorTypePack};
    }
    else
    {
        std::optional<TypeId> expectedType;
        if (!expectedTypes.empty())
            expectedType = expectedTypes[0];
        TypeId t = nullptr;
        if (FFlag::LuauThreadGeneralizeThroughConstraintGeneration)
        {
            // If we are given an expected type, then we will use the ungeneralized type of
            // any lambdas that are children of this expression. If we are not given an
            // expected type, then we check what value of generalize was passed in.
            t = check(scope, expr, expectedType, /* forceSingleton */ false, !expectedType.has_value() && generalize).ty;
        }
        else
        {
            t = check(scope, expr, expectedType, /*forceSingletons*/ false, generalize).ty;
        }

        result = InferencePack{arena->addTypePack({t})};
    }

    LUAU_ASSERT(result.tp);
    module->astTypePacks[expr] = result.tp;
    return result;
}

InferencePack ConstraintGenerator::checkPack(const ScopePtr& scope, AstExprCall* call, std::optional<TypeId> expectedType)
{
    Checkpoint funcBeginCheckpoint = checkpoint(this);

    TypeId fnType = nullptr;
    {
        InConditionalContext icc2{&typeContext, TypeContext::Default};
        fnType = check(scope, call->func).ty;
    }

    Checkpoint funcEndCheckpoint = checkpoint(this);

    return checkExprCall(scope, call, fnType, funcBeginCheckpoint, funcEndCheckpoint, expectedType);
}

InferencePack ConstraintGenerator::checkExprCall(
    const ScopePtr& scope,
    AstExprCall* call,
    TypeId fnType,
    Checkpoint funcBeginCheckpoint,
    Checkpoint funcEndCheckpoint,
    std::optional<TypeId> expectedType
)
{
    std::vector<AstExpr*> exprArgs;

    std::vector<RefinementId> returnRefinements;
    std::vector<std::optional<TypeId>> discriminantTypes;

    if (call->self)
    {
        AstExprIndexName* indexExpr = call->func->as<AstExprIndexName>();
        if (!indexExpr)
            ice->ice("method call expression has no 'self'");

        exprArgs.push_back(indexExpr->expr);

        if (auto key = dfg->getRefinementKey(indexExpr->expr))
        {
            TypeId discriminantTy = arena->addType(BlockedType{});
            returnRefinements.push_back(refinementArena.implicitProposition(key, discriminantTy));
            discriminantTypes.emplace_back(discriminantTy);
        }
        else
            discriminantTypes.emplace_back(std::nullopt);
    }

    for (AstExpr* arg : call->args)
    {
        exprArgs.push_back(arg);

        if (auto key = dfg->getRefinementKey(arg))
        {
            TypeId discriminantTy = arena->addType(BlockedType{});
            returnRefinements.push_back(refinementArena.implicitProposition(key, discriminantTy));
            discriminantTypes.emplace_back(discriminantTy);
        }
        else
            discriminantTypes.emplace_back(std::nullopt);
    }

    std::vector<std::optional<TypeId>> expectedTypesForCall = getExpectedCallTypesForFunctionOverloads(fnType);

    if (matchSetMetatable(*call) && expectedType)
    {
        if (const MetatableType* expectedMetatable = get<MetatableType>(follow(*expectedType)))
            expectedTypesForCall = {expectedMetatable->table, expectedMetatable->metatable};
    }

    module->astOriginalCallTypes[call->func] = fnType;

    Checkpoint argBeginCheckpoint = checkpoint(this);

    std::vector<TypeId> args;
    std::optional<TypePackId> argTail;
    std::vector<RefinementId> argumentRefinements;

    // Currently, `setmetatable` is bespoke in that instead of resolving a
    // function call, we *manually* construct a `MetatableType`. This causes
    // an issue for something like:
    //
    //  local a = setmetatable({ a = 1 }, {
    //      __call = function(self, b: number)
    //          return self.a * b
    //      end,
    //  })
    //  local foo = a(12)
    //
    // ... we want lambda calls within a function call to be open to
    // bidirectional inference, but we also need to ensure that they're
    // generalized at the right time.
    //
    // Aside from a future where we use an expected return type in order
    // to bidirectionally infer a function call, `setmetatable` should
    // never be able to `check` its arguments, so we just claim that
    // lambdas within `setmetatable` should be let-generalized.
    bool generalize = FFlag::LuauTraverseScopeToFunction ? matchSetMetatable(*call) : false;
    if (matchSetMetatable(*call))
    {
        if (expectedType)
            generalize = false;
    }

    for (size_t i = 0; i < exprArgs.size(); ++i)
    {
        AstExpr* arg = exprArgs[i];

        if (i == 0 && call->self)
        {
            // The self type has already been computed as a side effect of
            // computing fnType.  If computing that did not cause us to exceed a
            // recursion limit, we can fetch it from astTypes rather than
            // recomputing it.
            TypeId* selfTy = module->astTypes.find(exprArgs[0]);
            if (selfTy)
                args.push_back(*selfTy);
            else
                args.push_back(freshType(scope, Polarity::Negative));
        }
        else if (i < exprArgs.size() - 1 || !(arg->is<AstExprCall>() || arg->is<AstExprVarargs>()))
        {
            std::optional<TypeId> expectedType = std::nullopt;
            if (i < expectedTypesForCall.size())
            {
                expectedType = expectedTypesForCall[i];
            }

            if (i == 0 && matchAssert(*call))
            {
                InConditionalContext flipper{&typeContext};
                auto [ty, refinement] = check(scope, arg, expectedType, /*forceSingleton*/ false, generalize);
                args.push_back(ty);
                argumentRefinements.push_back(refinement);
            }
            else
            {
                auto [ty, refinement] = check(scope, arg, expectedType, /*forceSingleton*/ false, generalize);
                args.push_back(ty);
                argumentRefinements.push_back(refinement);
            }
        }
        else
        {
            std::vector<std::optional<Luau::TypeId>> expectedTypes = {};
            if (i < expectedTypesForCall.size())
            {
                expectedTypes.insert(expectedTypes.end(), expectedTypesForCall.begin() + int(i), expectedTypesForCall.end());
            }
            auto [tp, refis] = checkPack(scope, arg, expectedTypes);
            argTail = tp;
            argumentRefinements.insert(argumentRefinements.end(), refis.begin(), refis.end());
        }
    }

    Checkpoint argEndCheckpoint = checkpoint(this);

    if (FFlag::DebugLuauUserDefinedClasses)
    {
        if (auto instanceGuard = matchIsInstanceGuard(*call, dfg))
        {
            if (args.size() >= 2)
            {
                // The class type may not be solved yet (e.g. `A.Point` from a
                // required module).
                TypeId objectofInst = createTypeFunctionInstance(builtinTypes->typeFunctions->objectofFunc, {args[1]}, {}, scope, call->location);
                returnRefinements.emplace_back(refinementArena.implicitProposition(instanceGuard, objectofInst));
            }
        }
    }

    if (matchSetMetatable(*call))
    {
        TypePack argTailPack;
        if (argTail && args.size() < 2)
            argTailPack = extendTypePack(*arena, builtinTypes, *argTail, 2 - args.size());

        TypeId target = nullptr;
        TypeId mt = nullptr;

        if (args.size() + argTailPack.head.size() == 2)
        {
            target = args.size() > 0 ? args[0] : argTailPack.head[0];
            mt = args.size() > 1 ? args[1] : argTailPack.head[args.size() == 0 ? 1 : 0];
        }
        else
        {
            std::vector<TypeId> unpackedTypes;
            if (args.size() > 0)
                target = follow(args[0]);
            else
            {
                target = arena->addType(BlockedType{});
                unpackedTypes.emplace_back(target);
            }

            mt = arena->addType(BlockedType{});
            unpackedTypes.emplace_back(mt);

            auto c = addConstraint(scope, call->location, UnpackConstraint{std::move(unpackedTypes), *argTail});
            getMutable<BlockedType>(mt)->setOwner(c);
            if (auto b = getMutable<BlockedType>(target); b && b->getOwner() == nullptr)
                b->setOwner(c);
        }

        LUAU_ASSERT(target);
        LUAU_ASSERT(mt);

        target = follow(target);

        AstExpr* targetExpr = call->args.data[0];

        TypeId resultTy = nullptr;

        if (FFlag::LuauSetmetatableOverrides)
        {
            if (isTableUnion(target))
            {
                const UnionType* targetUnion = get<UnionType>(target);
                UnionBuilder ub{arena, builtinTypes};

                for (TypeId ty : targetUnion)
                    ub.add(arena->addType(MetatableType{findSetmetatableTargetOf(ty), mt}));

                resultTy = ub.build();
            }
            else
                resultTy = arena->addType(MetatableType{findSetmetatableTargetOf(target), mt});
        }
        else
        {
            if (isTableUnion(target))
            {
                const UnionType* targetUnion = get<UnionType>(target);
                UnionBuilder ub{arena, builtinTypes};

                for (TypeId ty : targetUnion)
                    ub.add(arena->addType(MetatableType{ty, mt}));

                resultTy = ub.build();
            }
            else
                resultTy = arena->addType(MetatableType{target, mt});
        }

        module->astTypes[call] = resultTy;

        if (expectedType)
        {
            NotNull<Constraint> ptc = addConstraint(
                scope,
                call->location,
                PushTypeConstraint{
                    /* expectedType */ *expectedType,
                    /* targetType */ resultTy,
                    /* astTypes */ NotNull{&module->astTypes},
                    /* astExpectedTypes */ NotNull{&module->astExpectedTypes},
                    /* expr */ NotNull{call},
                }
            );

            addAllAsReverseDependencies(argBeginCheckpoint, argEndCheckpoint, this, ptc);
        }

        if (AstExprLocal* targetLocal = targetExpr->as<AstExprLocal>())
        {
            scope->bindings[targetLocal->local].typeId = resultTy;

            DefId def = dfg->getDef(targetLocal);
            scope->lvalueTypes[def] = resultTy;            // TODO: typestates: track this as an assignment
            updateRValueRefinements(scope, def, resultTy); // TODO: typestates: track this as an assignment

            // HACK: If we have a targetLocal, it has already been added to the
            // inferredBindings table.  We want to replace it so that we don't
            // infer a weird union like tbl | { @metatable something, tbl }
            if (InferredBinding* ib = inferredBindings.find(targetLocal->local))
                ib->types.erase(target);

            recordInferredBinding(targetLocal->local, resultTy);
        }

        return InferencePack{arena->addTypePack({resultTy}), {refinementArena.variadic(returnRefinements)}};
    }

    if (shouldTypestateForFirstArgument(*call) && call->args.size > 0 && isLValue(call->args.data[0]))
    {
        AstExpr* targetExpr = call->args.data[0];
        auto resultTy = arena->addType(BlockedType{});

        if (auto def = dfg->getDefOptional(targetExpr))
        {
            scope->lvalueTypes[*def] = resultTy;
            updateRValueRefinements(scope, *def, resultTy);
        }
    }

    if (matchAssert(*call) && !argumentRefinements.empty())
        applyRefinements(scope, call->args.data[0]->location, argumentRefinements[0]);

    // TODO: How do expectedTypes play into this?  Do they?
    TypePackId rets = arena->addTypePack(BlockedTypePack{});
    TypePackId argPack = addTypePack(std::move(args), argTail);
    FunctionType ftv(TypeLevel{}, argPack, rets, std::nullopt, call->self);

    auto [explicitTypeIds, explicitTypePackIds] =
        call->typeArguments.size ? resolveTypeArguments(scope, call->typeArguments) : std::pair<std::vector<TypeId>, std::vector<TypePackId>>();

    /*
     * To make bidirectional type checking work, we need to solve these constraints in a particular order:
     *
     * 1. Solve the function type
     * 2. Propagate type information from the function type to the argument typeArguments
     * 3. Solve the argument typeArguments
     * 4. Solve the call
     */

    NotNull<Constraint> checkConstraint = addConstraint(
        scope, call->func->location, FunctionCheckConstraint{fnType, argPack, call, NotNull{&module->astTypes}, NotNull{&module->astExpectedTypes}}
    );

    addAllAsDependencies(funcBeginCheckpoint, funcEndCheckpoint, this, checkConstraint);

    NotNull<Constraint> callConstraint = addConstraint(
        scope,
        call->func->location,
        FunctionCallConstraint{
            fnType,
            argPack,
            rets,
            call,
            std::move(discriminantTypes),
            std::move(explicitTypeIds),
            std::move(explicitTypePackIds),
            FFlag::LuauCyclicRequireTypeInference ? &module->astTypes : nullptr,
            &module->astOverloadResolvedTypes,
        }
    );

    getMutable<BlockedTypePack>(rets)->owner = callConstraint.get();

    cgraph->addDependencyOf(checkConstraint, callConstraint);
    forEachConstraint(
        argBeginCheckpoint,
        argEndCheckpoint,
        this,
        [this, checkConstraint, callConstraint](const ConstraintPtr& constraint)
        {
            cgraph->addDependencyOf(checkConstraint, constraint.get());
            cgraph->addDependencyOf(constraint.get(), callConstraint);
        }
    );

    return InferencePack{rets, {refinementArena.variadic(returnRefinements)}};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExpr* expr, std::optional<TypeId> expectedType, bool forceSingleton, bool generalize)
{
    RecursionCounter counter{&recursionCount};

    if (recursionCount >= DFInt::LuauConstraintGeneratorRecursionLimit)
    {
        reportCodeTooComplex(expr->location);
        return Inference{builtinTypes->errorType};
    }

    // We may recurse a given expression more than once when checking compound
    // assignment, so we store and cache expressions here s.t. when we generate
    // constraints for something like:
    //
    //   a[b] += c
    //
    // We only solve _one_ set of constraints for `b`.
    if (inferredExprCache.contains(expr))
        return inferredExprCache[expr];

    Inference result;

    if (auto group = expr->as<AstExprGroup>())
        result = check(scope, group->expr, expectedType, forceSingleton, generalize);
    else if (auto stringExpr = expr->as<AstExprConstantString>())
        result = check(scope, stringExpr, expectedType, forceSingleton);
    else if (expr->is<AstExprConstantNumber>())
        result = Inference{builtinTypes->numberType};
    else if (expr->is<AstExprConstantInteger>())
        result = Inference{builtinTypes->integerType};
    else if (auto boolExpr = expr->as<AstExprConstantBool>())
        result = check(scope, boolExpr, expectedType, forceSingleton);
    else if (expr->is<AstExprConstantNil>())
        result = Inference{builtinTypes->nilType};
    else if (auto local = expr->as<AstExprLocal>())
        result = check(scope, local);
    else if (auto global = expr->as<AstExprGlobal>())
        result = check(scope, global);
    else if (expr->is<AstExprVarargs>())
        result = flattenPack(scope, expr->location, checkPack(scope, expr));
    else if (auto call = expr->as<AstExprCall>())
        result = flattenPack(
            scope, expr->location, checkPack(scope, call, matchSetMetatable(*call) ? expectedType : std::nullopt)
        ); // TODO: needs predicates too
    else if (auto a = expr->as<AstExprFunction>())
        result = check(scope, a, expectedType, generalize);
    else if (auto indexName = expr->as<AstExprIndexName>())
        result = check(scope, indexName);
    else if (auto indexExpr = expr->as<AstExprIndexExpr>())
        result = check(scope, indexExpr);
    else if (auto table = expr->as<AstExprTable>())
    {
        if (FFlag::LuauThreadGeneralizeThroughConstraintGeneration)
            result = check(scope, table, expectedType, generalize);
        else
            result = check_DEPRECATED(scope, table, expectedType);
    }
    else if (auto unary = expr->as<AstExprUnary>())
        result = check(scope, unary);
    else if (auto binary = expr->as<AstExprBinary>())
        result = check(scope, binary, expectedType);
    else if (auto ifElse = expr->as<AstExprIfElse>())
        result = check(scope, ifElse, expectedType);
    else if (auto typeAssert = expr->as<AstExprTypeAssertion>())
        result = check(scope, typeAssert);
    else if (auto interpString = expr->as<AstExprInterpString>())
        result = check(scope, interpString);
    else if (auto explicitTypeInstantiation = expr->as<AstExprInstantiate>())
        result = check(scope, explicitTypeInstantiation);
    else if (auto err = expr->as<AstExprError>())
    {
        // Open question: Should we traverse into this?
        for (AstExpr* subExpr : err->expressions)
            check(scope, subExpr);

        result = Inference{builtinTypes->errorType};
    }
    else
    {
        LUAU_ASSERT(0);
        result = Inference{freshType(scope)};
    }

    inferredExprCache[expr] = result;

    LUAU_ASSERT(result.ty);
    module->astTypes[expr] = result.ty;
    if (expectedType)
        module->astExpectedTypes[expr] = *expectedType;
    return result;
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprConstantString* string, std::optional<TypeId> expectedType, bool forceSingleton)
{

    if (forceSingleton)
        return Inference{arena->addType(SingletonType{StringSingleton{std::string{string->value.data, string->value.size}}})};

    // Consider a table like:
    //
    //  local DICTIONARY = { "aback", "abacus", "abandon", --[[ so on and so forth ]] }
    //
    // The intent is (probably) not for this to be an array-like table with a massive
    // union for the value, but instead a `{ string }`.
    if (largeTableDepth > 0)
        return Inference{builtinTypes->stringType};

    TypeId freeTy = freshType(scope, Polarity::Positive);
    FreeType* ft = getMutable<FreeType>(freeTy);
    LUAU_ASSERT(ft);
    ft->lowerBound = arena->addType(SingletonType{StringSingleton{std::string{string->value.data, string->value.size}}});
    ft->upperBound = builtinTypes->stringType;
    ft->primitiveType = builtinTypes->stringType;
    if (expectedType)
        addConstraint(scope, string->location, SubtypeConstraint{freeTy, *expectedType});
    return Inference{freeTy};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprConstantBool* boolExpr, std::optional<TypeId> expectedType, bool forceSingleton)
{
    const TypeId singletonType = boolExpr->value ? builtinTypes->trueType : builtinTypes->falseType;
    if (forceSingleton)
        return Inference{singletonType};

    // Consider a table like:
    //
    //  local FLAGS = {
    //      Foo = true,
    //      Bar = false,
    //      Baz = true,
    //      -- so on and so forth
    //  }
    //
    // The intent is (probably) not for this to be a table where each element
    // is potentially `true` or `false` as a singleton, but just `boolean`.
    if (largeTableDepth > 0)
        return Inference{builtinTypes->booleanType};

    TypeId freeTy = freshType(scope, Polarity::Positive);
    FreeType* ft = getMutable<FreeType>(freeTy);
    LUAU_ASSERT(ft);
    ft->lowerBound = singletonType;
    ft->upperBound = builtinTypes->booleanType;
    ft->primitiveType = builtinTypes->booleanType;
    if (expectedType)
        addConstraint(scope, boolExpr->location, SubtypeConstraint{freeTy, *expectedType});
    return Inference{freeTy};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprLocal* local)
{
    if (FFlag::DebugLuauCFG)
        return Inference{resolveRHSType(scope, local->location, local), nullptr};
    else
    {
        const RefinementKey* key = dfg->getRefinementKey(local);
        LUAU_ASSERT(key);

        std::optional<TypeId> maybeTy;

        // if we have a refinement key, we can look up its type.
        if (key)
            maybeTy = lookup(scope, local->location, key->def);

        if (maybeTy)
        {
            TypeId ty = follow(*maybeTy);

            recordInferredBinding(local->local, ty);

            return Inference{ty, refinementArena.proposition(key, builtinTypes->truthyType)};
        }
        else
            ice->ice("CG: AstExprLocal came before its declaration?");
    }
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprGlobal* global)
{
    const RefinementKey* key = dfg->getRefinementKey(global);
    LUAU_ASSERT(key);

    DefId def = key->def;

    /* prepopulateGlobalScope() has already added all global functions to the environment by this point, so any
     * global that is not already in-scope is definitely an unknown symbol.
     */
    if (auto ty = lookup(scope, global->location, def, /*prototype=*/false))
    {
        return Inference{*ty, refinementArena.proposition(key, builtinTypes->truthyType)};
    }
    else
        return Inference{builtinTypes->errorType};
}

Inference ConstraintGenerator::checkIndexName(
    const ScopePtr& scope,
    const RefinementKey* key,
    AstExpr* indexee,
    const std::string& index,
    Location indexLocation
)
{
    TypeId obj = check(scope, indexee).ty;
    TypeId result = nullptr;

    // We optimize away the HasProp constraint in simple cases so that we can
    // reason about updates to unsealed tables more accurately.

    const TableType* tt = getTableType(obj);

    // This is a little bit iffy but I *believe* it is okay because, if the
    // local's domain is going to be extended at all, it will be someplace after
    // the current lexical position within the script.
    if (!tt)
    {
        if (TypeIds* localDomain = localTypes.find(obj); localDomain && 1 == localDomain->size())
            tt = getTableType(*localDomain->begin());
    }

    if (tt)
    {
        auto it = tt->props.find(index);
        if (it != tt->props.end() && it->second.readTy.has_value())
            result = *it->second.readTy;
    }

    if (auto cachedHasPropResult = propIndexPairsSeen.find({obj, index}))
        result = *cachedHasPropResult;

    if (!result)
    {
        result = arena->addType(BlockedType{});

        auto c = addConstraint(scope, indexee->location, HasPropConstraint{result, obj, index, inConditional(typeContext)});
        getMutable<BlockedType>(result)->setOwner(c);
        propIndexPairsSeen[{obj, index}] = result;
    }

    if (key)
    {
        if (auto ty = lookup(scope, indexLocation, key->def, false))
            return Inference{*ty, refinementArena.proposition(key, builtinTypes->truthyType)};

        updateRValueRefinements(scope, key->def, result);
    }

    if (key)
        return Inference{result, refinementArena.proposition(key, builtinTypes->truthyType)};
    else
        return Inference{result};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprIndexName* indexName)
{
    const RefinementKey* key = dfg->getRefinementKey(indexName);
    return checkIndexName(scope, key, indexName->expr, indexName->index.value, indexName->indexLocation);
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprIndexExpr* indexExpr)
{
    if (auto constantString = indexExpr->index->as<AstExprConstantString>())
    {
        module->astTypes[indexExpr->index] = builtinTypes->stringType;
        const RefinementKey* key = dfg->getRefinementKey(indexExpr);
        return checkIndexName(scope, key, indexExpr->expr, constantString->value.data, indexExpr->location);
    }

    TypeId obj = check(scope, indexExpr->expr).ty;
    TypeId indexType = check(scope, indexExpr->index).ty;

    TypeId result = arena->addType(BlockedType{});

    const RefinementKey* key = dfg->getRefinementKey(indexExpr);
    if (key)
    {
        if (auto ty = lookup(scope, indexExpr->location, key->def))
            return Inference{*ty, refinementArena.proposition(key, builtinTypes->truthyType)};
        updateRValueRefinements(scope, key->def, result);
    }

    auto c = addConstraint(scope, indexExpr->expr->location, HasIndexerConstraint{result, obj, indexType});
    getMutable<BlockedType>(result)->setOwner(c);

    if (key)
        return Inference{result, refinementArena.proposition(key, builtinTypes->truthyType)};
    else
        return Inference{result};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprFunction* func, std::optional<TypeId> expectedType, bool generalize)
{
    InConditionalContext inContext(&typeContext, TypeContext::Default);

    Checkpoint startCheckpoint = checkpoint(this);
    FunctionSignature sig = checkFunctionSignature(scope, nullptr, func, expectedType);

    interiorFreeTypes.emplace_back();
    checkFunctionBody(sig.bodyScope, func);
    Checkpoint endCheckpoint = checkpoint(this);

    TypeId generalizedTy = arena->addType(BlockedType{});
    NotNull<Constraint> gc = addConstraint(
        sig.signatureScope,
        func->location,
        GeneralizationConstraint{
            generalizedTy,
            sig.signature,
        }
    );

    propagateDeprecatedAttributeToConstraint(gc->c, func);

    sig.signatureScope->interiorFreeTypes = std::move(interiorFreeTypes.back().types);
    sig.signatureScope->interiorFreeTypePacks = std::move(interiorFreeTypes.back().typePacks);
    interiorFreeTypes.pop_back();

    getMutable<BlockedType>(generalizedTy)->setOwner(gc);

    addAllAsDependenciesAndChainReturns(startCheckpoint, endCheckpoint, this, gc);
    if (generalize && hasFreeType(sig.signature))
    {
        return Inference{generalizedTy};
    }
    else
    {
        return Inference{sig.signature};
    }
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprUnary* unary)
{
    std::optional<InConditionalContext> inContext;
    if (unary->op != AstExprUnary::Op::Not)
        inContext.emplace(&typeContext, TypeContext::Default);

    auto [operandType, refinement] = check(scope, unary->expr);

    switch (unary->op)
    {
    case AstExprUnary::Op::Not:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->notFunc, {operandType}, {}, scope, unary->location);
        return Inference{resultType, refinementArena.negation(refinement)};
    }
    case AstExprUnary::Op::Len:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->lenFunc, {operandType}, {}, scope, unary->location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprUnary::Op::Minus:
    {
        // compileExprUnary folds `-1i` into one negative constant, so a negated integer literal is a value rather than
        // an operation. A non-literal integer still reaches the runtime, which has no __unm, so it keeps the check.
        if (FFlag::LuauIntegerType2 && unary->expr->is<AstExprConstantInteger>())
            return Inference{builtinTypes->integerType, std::move(refinement)};

        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->unmFunc, {operandType}, {}, scope, unary->location);
        return Inference{resultType, std::move(refinement)};
    }
    default: // msvc can't prove that this is exhaustive.
        LUAU_UNREACHABLE();
    }
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprBinary* binary, std::optional<TypeId> expectedType)
{
    return checkAstExprBinary(scope, binary->location, binary->op, binary->left, binary->right, expectedType);
}

Inference ConstraintGenerator::checkAstExprBinary(
    const ScopePtr& scope,
    const Location& location,
    AstExprBinary::Op op,
    AstExpr* left,
    AstExpr* right,
    std::optional<TypeId> expectedType
)
{
    auto [leftType, rightType, refinement] = checkBinary(scope, op, left, right, expectedType);

    switch (op)
    {
    case AstExprBinary::Op::Add:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->addFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::Sub:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->subFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::Mul:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->mulFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::Div:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->divFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::FloorDiv:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->idivFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::Pow:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->powFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::Mod:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->modFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::Concat:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->concatFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::And:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->andFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::Or:
    {
        TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->orFunc, {leftType, rightType}, {}, scope, location);
        return Inference{resultType, std::move(refinement)};
    }
    case AstExprBinary::Op::CompareLt:
    {
        addConstraint(scope, location, EqualityConstraint{leftType, rightType});
        return Inference{builtinTypes->booleanType, std::move(refinement)};
    }
    case AstExprBinary::Op::CompareGe:
    {
        addConstraint(scope, location, EqualityConstraint{leftType, rightType});
        return Inference{builtinTypes->booleanType, std::move(refinement)};
    }
    case AstExprBinary::Op::CompareLe:
    {
        addConstraint(scope, location, EqualityConstraint{leftType, rightType});
        return Inference{builtinTypes->booleanType, std::move(refinement)};
    }
    case AstExprBinary::Op::CompareGt:
    {
        addConstraint(scope, location, EqualityConstraint{leftType, rightType});
        return Inference{builtinTypes->booleanType, std::move(refinement)};
    }
    case AstExprBinary::Op::CompareEq:
    case AstExprBinary::Op::CompareNe:
        return Inference{builtinTypes->booleanType, std::move(refinement)};
    case AstExprBinary::Op::Op__Count:
        ice->ice("Op__Count should never be generated in an AST.");
    default: // msvc can't prove that this is exhaustive.
        LUAU_UNREACHABLE();
    }
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprIfElse* ifElse, std::optional<TypeId> expectedType)
{
    InConditionalContext inContext(&typeContext, TypeContext::Default);

    if (FFlag::LuauExperimentalIfLocalAnalysis && ifElse->conditionLocal)
    {
        ScopePtr thenScope = childScope(ifElse->trueExpr, scope);
        ScopePtr elseScope = childScope(ifElse->falseExpr, scope);

        std::optional<TypeId> annotatedType;
        if (ifElse->conditionLocal->annotation)
            annotatedType = resolveType(scope, ifElse->conditionLocal->annotation, /* inTypeArguments */ false);

        TypeId initType = [&]()
        {
            InConditionalContext flipper{&typeContext};
            return check(scope, ifElse->condition, annotatedType).ty;
        }();

        TypeId baseType = annotatedType ? *annotatedType : initType;
        TypeId boundType = createTypeFunctionInstance(
            builtinTypes->typeFunctions->refineFunc, {baseType, builtinTypes->truthyType}, {}, thenScope, ifElse->conditionLocal->location
        );

        thenScope->bindings[ifElse->conditionLocal] = Binding{boundType, ifElse->conditionLocal->location};

        DefId def = dfg->getDef(ifElse->conditionLocal);
        thenScope->lvalueTypes[def] = boundType;

        TypeId thenType = check(thenScope, ifElse->trueExpr, expectedType).ty;
        TypeId elseType = check(elseScope, ifElse->falseExpr, expectedType).ty;

        return Inference{makeUnion(scope, ifElse->location, thenType, elseType)};
    }

    RefinementId refinement = [&]()
    {
        InConditionalContext flipper{&typeContext};
        ScopePtr condScope = childScope(ifElse->condition, scope);
        return check(condScope, ifElse->condition).refinement;
    }();

    ScopePtr thenScope = childScope(ifElse->trueExpr, scope);
    applyRefinements(thenScope, ifElse->trueExpr->location, refinement);
    TypeId thenType = check(thenScope, ifElse->trueExpr, expectedType).ty;

    ScopePtr elseScope = childScope(ifElse->falseExpr, scope);
    applyRefinements(elseScope, ifElse->falseExpr->location, refinementArena.negation(refinement));
    TypeId elseType = check(elseScope, ifElse->falseExpr, expectedType).ty;

    return Inference{makeUnion(scope, ifElse->location, thenType, elseType)};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprTypeAssertion* typeAssert)
{
    check(scope, typeAssert->expr, std::nullopt);
    return Inference{resolveType(scope, typeAssert->annotation, /* inTypeArguments */ false)};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprInterpString* interpString)
{
    InConditionalContext inContext(&typeContext, TypeContext::Default);

    for (AstExpr* expr : interpString->expressions)
        check(scope, expr);

    return Inference{builtinTypes->stringType};
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprInstantiate* explicitTypeInstantiation)
{
    TypeId functionType = check(scope, explicitTypeInstantiation->expr, std::nullopt).ty;

    auto [explicitTypeIds, explicitTypePackIds] = resolveTypeArguments(scope, explicitTypeInstantiation->typeArguments);

    TypeId placeholderType = arena->addType(BlockedType{});

    NotNull<Constraint> constraint = addConstraint(
        scope,
        explicitTypeInstantiation->location,
        TypeInstantiationConstraint{functionType, placeholderType, std::move(explicitTypeIds), std::move(explicitTypePackIds)}
    );

    getMutable<BlockedType>(placeholderType)->setOwner(constraint);

    return Inference{placeholderType};
}

std::pair<std::vector<TypeId>, std::vector<TypePackId>> ConstraintGenerator::resolveTypeArguments(
    const ScopePtr& scope,
    const AstArray<AstTypeOrPack>& typeArguments
)
{
    std::vector<TypeId> resolvedTypeArguments;
    std::vector<TypePackId> resolvedTypePackArguments;

    for (const AstTypeOrPack& typeOrPack : typeArguments)
    {
        if (typeOrPack.type)
        {
            resolvedTypeArguments.push_back(resolveType(
                scope,
                typeOrPack.type,
                /* inTypeArguments = */ false
            ));
        }
        else
        {
            LUAU_ASSERT(typeOrPack.typePack);
            resolvedTypePackArguments.push_back(resolveTypePack(
                scope,
                typeOrPack.typePack,
                /* inTypeArguments = */ false
            ));
        }
    }

    return {std::move(resolvedTypeArguments), std::move(resolvedTypePackArguments)};
}

std::tuple<TypeId, TypeId, RefinementId> ConstraintGenerator::checkBinary(
    const ScopePtr& scope,
    AstExprBinary::Op op,
    AstExpr* left,
    AstExpr* right,
    std::optional<TypeId> expectedType
)
{
    std::optional<InConditionalContext> inContext;
    if (op != AstExprBinary::And && op != AstExprBinary::Or && op != AstExprBinary::CompareEq && op != AstExprBinary::CompareNe)
        inContext.emplace(&typeContext, TypeContext::Default);

    if (op == AstExprBinary::And)
    {
        std::optional<TypeId> relaxedExpectedLhs;

        if (expectedType)
            relaxedExpectedLhs = arena->addType(UnionType{{builtinTypes->falsyType, *expectedType}});

        auto [leftType, leftRefinement] = check(scope, left, relaxedExpectedLhs);

        ScopePtr rightScope = childScope(right, scope);
        applyRefinements(rightScope, right->location, leftRefinement);
        auto [rightType, rightRefinement] = check(rightScope, right, expectedType);

        return {leftType, rightType, refinementArena.conjunction(leftRefinement, rightRefinement)};
    }
    else if (op == AstExprBinary::Or)
    {
        std::optional<TypeId> relaxedExpectedLhs;

        if (expectedType)
            relaxedExpectedLhs = arena->addType(UnionType{{builtinTypes->falsyType, *expectedType}});

        auto [leftType, leftRefinement] = check(scope, left, relaxedExpectedLhs);

        ScopePtr rightScope = childScope(right, scope);
        applyRefinements(rightScope, right->location, refinementArena.negation(leftRefinement));
        auto [rightType, rightRefinement] = check(rightScope, right, expectedType);

        return {leftType, rightType, refinementArena.disjunction(leftRefinement, rightRefinement)};
    }
    else if (auto typeguard = matchTypeGuard(op, left, right))
    {
        TypeId leftType = check(scope, left).ty;
        TypeId rightType = check(scope, right).ty;

        const RefinementKey* key = dfg->getRefinementKey(typeguard->target);
        if (!key)
            return {leftType, rightType, nullptr};

        TypeId discriminantTy = builtinTypes->neverType;
        if (typeguard->type == "nil")
            discriminantTy = builtinTypes->nilType;
        else if (typeguard->type == "string")
            discriminantTy = builtinTypes->stringType;
        else if (typeguard->type == "number")
            discriminantTy = builtinTypes->numberType;
        else if (typeguard->type == "integer")
            discriminantTy = builtinTypes->integerType;
        else if (typeguard->type == "boolean")
            discriminantTy = builtinTypes->booleanType;
        else if (typeguard->type == "thread")
            discriminantTy = builtinTypes->threadType;
        else if (typeguard->type == "buffer")
            discriminantTy = builtinTypes->bufferType;
        else if (typeguard->type == "table")
            discriminantTy = builtinTypes->tableType;
        else if (typeguard->type == "function")
            discriminantTy = builtinTypes->functionType;
        else if (typeguard->type == "userdata")
        {
            // For now, we don't really care about being accurate with userdata if the typeguard was using typeof.
            discriminantTy = builtinTypes->externType;
        }
        else if (typeguard->type == "vector" && !typeguard->isTypeof)
        {
            // `vector` is defined in EmbeddedBuiltinDefinitions, not as an actual built-in type
            auto typeFun = globalScope->lookupType("vector");
            if (typeFun)
                discriminantTy = follow(typeFun->type);
        }
        else if (!typeguard->isTypeof)
            discriminantTy = builtinTypes->neverType;
        else if (auto typeFun = globalScope->lookupType(typeguard->type); typeFun && typeFun->typeParams.empty() && typeFun->typePackParams.empty())
        {
            TypeId ty = follow(typeFun->type);

            // We're only interested in the root type of any extern type.
            if (auto etv = get<ExternType>(ty); etv && (etv->parent == builtinTypes->externType || hasTag(ty, kTypeofRootTag)))
                discriminantTy = ty;
        }

        RefinementId proposition = refinementArena.proposition(key, discriminantTy);
        if (op == AstExprBinary::CompareEq)
            return {leftType, rightType, proposition};
        else if (op == AstExprBinary::CompareNe)
            return {leftType, rightType, refinementArena.negation(proposition)};
        else
            ice->ice("matchTypeGuard should only return a Some under `==` or `~=`!");
    }
    else if (op == AstExprBinary::CompareEq || op == AstExprBinary::CompareNe)
    {
        // We are checking a binary expression of the form a op b
        // Just because a op b is expected to return a bool, doesn't mean a, b are expected to be bools too
        TypeId leftType = check(scope, left, {}, true).ty;
        TypeId rightType = check(scope, right, {}, true).ty;

        RefinementId leftRefinement = refinementArena.proposition(dfg->getRefinementKey(left), rightType);
        RefinementId rightRefinement = refinementArena.proposition(dfg->getRefinementKey(right), leftType);

        if (op == AstExprBinary::CompareNe)
        {
            leftRefinement = refinementArena.negation(leftRefinement);
            rightRefinement = refinementArena.negation(rightRefinement);
        }

        return {leftType, rightType, refinementArena.equivalence(leftRefinement, rightRefinement)};
    }
    else
    {
        TypeId leftType = check(scope, left).ty;
        TypeId rightType = check(scope, right).ty;
        return {leftType, rightType, nullptr};
    }
}

void ConstraintGenerator::visitLValue(const ScopePtr& scope, AstExpr* expr, TypeId rhsType)
{
    if (auto e = expr->as<AstExprLocal>())
        visitLValue(scope, e, rhsType);
    else if (auto e = expr->as<AstExprGlobal>())
        visitLValue(scope, e, rhsType);
    else if (auto e = expr->as<AstExprIndexName>())
        visitLValue(scope, e, rhsType);
    else if (auto e = expr->as<AstExprIndexExpr>())
        visitLValue(scope, e, rhsType);
    else if (auto e = expr->as<AstExprError>())
    {
        // If we end up with some sort of error expression in an lvalue
        // position, at least go and check the expressions so that when
        // we visit them later, there aren't any invalid assumptions.
        for (auto subExpr : e->expressions)
        {
            check(scope, subExpr);
        }
    }
    else
        ice->ice("Unexpected lvalue expression", expr->location);
}

void ConstraintGenerator::visitLValue(const ScopePtr& scope, AstExprLocal* local, TypeId rhsType)
{
    if (FFlag::DebugLuauCFG)
    {
        TypeId assignTy = resolveLHSType(scope, local->location, CFG::LValue{static_cast<AstExpr*>(local)});
        localTypes.try_insert(assignTy, {});
        localTypes[assignTy].insert(rhsType);

        std::optional<TypeId> annotatedTy = scope->lookup(local->local);
        if (annotatedTy)
            addConstraint(scope, local->location, SubtypeConstraint{rhsType, *annotatedTy});

        return;
    }

    std::optional<TypeId> annotatedTy = scope->lookup(local->local);
    LUAU_ASSERT(annotatedTy);

    const DefId defId = dfg->getDef(local);
    std::optional<TypeId> ty = scope->lookupUnrefinedType(defId);

    if (ty)
    {
        TypeIds* localDomain = localTypes.find(*ty);
        if (localDomain && !local->upvalue)
            localDomain->insert(rhsType);
    }
    else
    {
        ty = arena->addType(BlockedType{});
        localTypes[*ty].insert(rhsType);

        if (annotatedTy)
        {
            switch (shouldSuppressErrors(normalizer, *annotatedTy))
            {
            case ErrorSuppression::DoNotSuppress:
                break;
            case ErrorSuppression::Suppress:
                ty = simplifyUnion(scope, local->location, *ty, builtinTypes->errorType);
                break;
            case ErrorSuppression::NormalizationFailed:
                reportError(local->local->annotation->location, NormalizationTooComplex{});
                break;
            }
        }

        scope->lvalueTypes[defId] = *ty;
    }

    recordInferredBinding(local->local, *ty);

    if (annotatedTy)
        addConstraint(scope, local->location, SubtypeConstraint{rhsType, *annotatedTy});
}

void ConstraintGenerator::visitLValue(const ScopePtr& scope, AstExprGlobal* global, TypeId rhsType)
{
    std::optional<TypeId> annotatedTy = scope->lookup(Symbol{global->name});
    if (annotatedTy)
    {
        DefId def = dfg->getDef(global);
        rootScope->lvalueTypes[def] = rhsType;

        // Ignore possible self-assignment, it doesn't create a new constraint
        if (annotatedTy == follow(rhsType))
            return;

        auto followedAnnotation = follow(*annotatedTy);
        if (auto bt = get<BlockedType>(followedAnnotation); bt && uninitializedGlobals.contains(global->name))
        {
            LUAU_ASSERT(bt->getOwner() == nullptr);
            uninitializedGlobals.erase(global->name);
            emplaceType<BoundType>(asMutable(followedAnnotation), rhsType);
        }


        addConstraint(scope, global->location, SubtypeConstraint{rhsType, *annotatedTy});
    }
}

void ConstraintGenerator::visitLValue(const ScopePtr& scope, AstExprIndexName* expr, TypeId rhsType)
{
    TypeId lhsTy = check(scope, expr->expr).ty;
    TypeId propTy = arena->addType(BlockedType{});
    module->astTypes[expr] = propTy;

    bool incremented = recordPropertyAssignment(lhsTy);

    auto apc =
        addConstraint(scope, expr->location, AssignPropConstraint{lhsTy, expr->index.value, rhsType, expr->indexLocation, propTy, incremented});
    getMutable<BlockedType>(propTy)->setOwner(apc);
}

void ConstraintGenerator::visitLValue(const ScopePtr& scope, AstExprIndexExpr* expr, TypeId rhsType)
{
    if (auto constantString = expr->index->as<AstExprConstantString>())
    {
        TypeId lhsTy = check(scope, expr->expr).ty;
        TypeId propTy = arena->addType(BlockedType{});
        module->astTypes[expr] = propTy;
        module->astTypes[expr->index] = builtinTypes->stringType; // FIXME? Singleton strings exist.
        std::string propName{constantString->value.data, constantString->value.size};

        bool incremented = recordPropertyAssignment(lhsTy);

        auto apc = addConstraint(
            scope, expr->location, AssignPropConstraint{lhsTy, std::move(propName), rhsType, expr->index->location, propTy, incremented}
        );
        getMutable<BlockedType>(propTy)->setOwner(apc);

        return;
    }

    TypeId lhsTy = check(scope, expr->expr).ty;
    TypeId indexTy = check(scope, expr->index).ty;
    TypeId propTy = arena->addType(BlockedType{});
    module->astTypes[expr] = propTy;
    auto aic = addConstraint(scope, expr->location, AssignIndexConstraint{lhsTy, indexTy, rhsType, propTy});
    getMutable<BlockedType>(propTy)->setOwner(aic);
}

Inference ConstraintGenerator::check(const ScopePtr& scope, AstExprTable* expr, std::optional<TypeId> expectedType, bool generalize)
{
    LUAU_ASSERT(FFlag::LuauThreadGeneralizeThroughConstraintGeneration);
    InConditionalContext inContext(&typeContext, TypeContext::Default);

    TypeId ty = arena->addType(TableType{});
    TableType* ttv = getMutable<TableType>(ty);
    LUAU_ASSERT(ttv);

    ttv->state = TableState::Unsealed;
    ttv->definitionModuleName = module->name;
    ttv->definitionLocation = expr->location;
    ttv->scope = scope.get();

    if (FInt::LuauPrimitiveInferenceInTableLimit > 0 && expr->items.size > size_t(FInt::LuauPrimitiveInferenceInTableLimit))
        largeTableDepth++;

    interiorFreeTypes.back().types.push_back(ty);

    TypeIds indexKeyLowerBound;
    TypeIds indexValueLowerBound;

    auto createIndexer = [&indexKeyLowerBound, &indexValueLowerBound](const Location& location, TypeId currentIndexType, TypeId currentResultType)
    {
        indexKeyLowerBound.insert(follow(currentIndexType));
        indexValueLowerBound.insert(follow(currentResultType));
    };

    TypeIds valuesLowerBound;

    Checkpoint start = checkpoint(this);

    for (const AstExprTable::Item& item : expr->items)
    {
        // Expected typeArguments are threaded through table literals separately via the
        // function matchLiteralType.

        // generalize is false here as we want to be able to push typeArguments into lambdas in a situation like:
        //
        //  type Callback = (string) -> ()
        //
        //  local t: { Callback } = {
        //      function (s)
        //          -- s should have type `string` here
        //      end
        //  }
        TypeId itemTy = check(scope, item.value, /* expectedType */ std::nullopt, /* forceSingleton */ false, generalize).ty;

        if (item.key)
        {
            // Even though we don't need to use the type of the item's key if
            // it's a string constant, we still want to check it to populate
            // astTypes.
            TypeId keyTy = check(scope, item.key).ty;

            if (AstExprConstantString* key = item.key->as<AstExprConstantString>())
            {
                std::string propName{key->value.data, key->value.size};
                ttv->props[propName] = {itemTy, /*deprecated*/ false, {}, key->location};
            }
            else
            {
                createIndexer(item.key->location, keyTy, itemTy);
            }
        }
        else
        {
            TypeId numberType = builtinTypes->numberType;
            // FIXME?  The location isn't quite right here.  Not sure what is
            // right.
            createIndexer(item.value->location, numberType, itemTy);
        }
    }

    Checkpoint end = checkpoint(this);

    if (!indexKeyLowerBound.empty())
    {
        LUAU_ASSERT(!indexValueLowerBound.empty());

        TypeId indexKey = nullptr;
        TypeId indexValue = nullptr;

        if (indexKeyLowerBound.size() == 1)
        {
            indexKey = *indexKeyLowerBound.begin();
        }
        else
        {
            indexKey = arena->addType(UnionType{std::vector(indexKeyLowerBound.begin(), indexKeyLowerBound.end())});
            unionsToSimplify.push_back(indexKey);
        }

        if (indexValueLowerBound.size() == 1)
        {
            indexValue = *indexValueLowerBound.begin();
        }
        else
        {
            indexValue = arena->addType(UnionType{std::vector(indexValueLowerBound.begin(), indexValueLowerBound.end())});
            unionsToSimplify.push_back(indexValue);
        }

        ttv->indexer = TableIndexer{indexKey, indexValue};
    }

    if (expectedType)
    {
        auto ptc = addConstraint(
            scope,
            expr->location,
            PushTypeConstraint{
                /* expectedType */ *expectedType,
                /* targetType */ ty,
                /* astTypes */ NotNull{&module->astTypes},
                /* astExpectedTypes */ NotNull{&module->astExpectedTypes},
                /* expr */ NotNull{expr},
            }
        );

        addAllAsReverseDependencies(start, end, this, ptc);
    }

    if (FInt::LuauPrimitiveInferenceInTableLimit > 0 && expr->items.size > size_t(FInt::LuauPrimitiveInferenceInTableLimit))
        largeTableDepth--;

    return Inference{ty};
}

Inference ConstraintGenerator::check_DEPRECATED(const ScopePtr& scope, AstExprTable* expr, std::optional<TypeId> expectedType)
{
    LUAU_ASSERT(!FFlag::LuauThreadGeneralizeThroughConstraintGeneration);
    InConditionalContext inContext(&typeContext, TypeContext::Default);

    TypeId ty = arena->addType(TableType{});
    TableType* ttv = getMutable<TableType>(ty);
    LUAU_ASSERT(ttv);

    ttv->state = TableState::Unsealed;
    ttv->definitionModuleName = module->name;
    ttv->definitionLocation = expr->location;
    ttv->scope = scope.get();

    if (FInt::LuauPrimitiveInferenceInTableLimit > 0 && expr->items.size > size_t(FInt::LuauPrimitiveInferenceInTableLimit))
        largeTableDepth++;

    interiorFreeTypes.back().types.push_back(ty);

    TypeIds indexKeyLowerBound;
    TypeIds indexValueLowerBound;

    auto createIndexer = [&indexKeyLowerBound, &indexValueLowerBound](const Location& location, TypeId currentIndexType, TypeId currentResultType)
    {
        indexKeyLowerBound.insert(follow(currentIndexType));
        indexValueLowerBound.insert(follow(currentResultType));
    };

    TypeIds valuesLowerBound;

    Checkpoint start = checkpoint(this);

    for (const AstExprTable::Item& item : expr->items)
    {
        // Expected typeArguments are threaded through table literals separately via the
        // function matchLiteralType.

        // generalize is false here as we want to be able to push typeArguments into lambdas in a situation like:
        //
        //  type Callback = (string) -> ()
        //
        //  local t: { Callback } = {
        //      function (s)
        //          -- s should have type `string` here
        //      end
        //  }
        TypeId itemTy = check(scope, item.value, /* expectedType */ std::nullopt, /* forceSingleton */ false, /* generalize */ false).ty;

        if (item.key)
        {
            // Even though we don't need to use the type of the item's key if
            // it's a string constant, we still want to check it to populate
            // astTypes.
            TypeId keyTy = check(scope, item.key).ty;

            if (AstExprConstantString* key = item.key->as<AstExprConstantString>())
            {
                std::string propName{key->value.data, key->value.size};
                ttv->props[propName] = {itemTy, /*deprecated*/ false, {}, key->location};
            }
            else
            {
                createIndexer(item.key->location, keyTy, itemTy);
            }
        }
        else
        {
            TypeId numberType = builtinTypes->numberType;
            // FIXME?  The location isn't quite right here.  Not sure what is
            // right.
            createIndexer(item.value->location, numberType, itemTy);
        }
    }

    Checkpoint end = checkpoint(this);

    if (!indexKeyLowerBound.empty())
    {
        LUAU_ASSERT(!indexValueLowerBound.empty());

        TypeId indexKey = nullptr;
        TypeId indexValue = nullptr;

        if (indexKeyLowerBound.size() == 1)
        {
            indexKey = *indexKeyLowerBound.begin();
        }
        else
        {
            indexKey = arena->addType(UnionType{std::vector(indexKeyLowerBound.begin(), indexKeyLowerBound.end())});
            unionsToSimplify.push_back(indexKey);
        }

        if (indexValueLowerBound.size() == 1)
        {
            indexValue = *indexValueLowerBound.begin();
        }
        else
        {
            indexValue = arena->addType(UnionType{std::vector(indexValueLowerBound.begin(), indexValueLowerBound.end())});
            unionsToSimplify.push_back(indexValue);
        }

        ttv->indexer = TableIndexer{indexKey, indexValue};
    }

    if (expectedType)
    {
        auto ptc = addConstraint(
            scope,
            expr->location,
            PushTypeConstraint{
                /* expectedType */ *expectedType,
                /* targetType */ ty,
                /* astTypes */ NotNull{&module->astTypes},
                /* astExpectedTypes */ NotNull{&module->astExpectedTypes},
                /* expr */ NotNull{expr},
            }
        );

        addAllAsReverseDependencies(start, end, this, ptc);
    }

    if (FInt::LuauPrimitiveInferenceInTableLimit > 0 && expr->items.size > size_t(FInt::LuauPrimitiveInferenceInTableLimit))
        largeTableDepth--;

    return Inference{ty};
}

ConstraintGenerator::FunctionSignature ConstraintGenerator::checkFunctionSignature(
    const ScopePtr& parent,
    ClassDeclRecord* enclosingClass,
    AstExprFunction* fn,
    std::optional<TypeId> expectedType,
    std::optional<Location> originalName
)
{
    LUAU_ASSERT(FFlag::DebugLuauUserDefinedClasses || enclosingClass == nullptr);
    ScopePtr signatureScope = nullptr;
    ScopePtr bodyScope = nullptr;
    TypePackId returnType = nullptr;

    std::vector<TypeId> genericTypes;
    std::vector<TypePackId> genericTypePacks;

    if (expectedType)
        expectedType = follow(*expectedType);

    bool hasGenerics = fn->generics.size > 0 || fn->genericPacks.size > 0;

    signatureScope = childScope(fn, parent);

    // We need to assign returnType before creating bodyScope so that the
    // return type gets propagated to bodyScope.
    returnType = freshTypePack(signatureScope, Polarity::Positive);
    signatureScope->returnType = returnType;

    bodyScope = childScope(fn->body, signatureScope);

    if (hasGenerics)
    {
        std::vector<std::pair<Name, GenericTypeDefinition>> genericDefinitions = createGenerics(signatureScope, fn->generics);
        std::vector<std::pair<Name, GenericTypePackDefinition>> genericPackDefinitions = createGenericPacks(signatureScope, fn->genericPacks);

        // We do not support default values on function generics, so we only
        // care about the typeArguments involved.
        for (const auto& [name, g] : genericDefinitions)
        {
            genericTypes.push_back(g.ty);
        }

        for (const auto& [name, g] : genericPackDefinitions)
        {
            genericTypePacks.push_back(g.tp);
        }

        // Local variable works around an odd gcc 11.3 warning: <anonymous> may be used uninitialized
        std::optional<TypeId> none = std::nullopt;
        expectedType = none;
    }

    std::vector<TypeId> argTypes;
    std::vector<std::optional<FunctionArgument>> argNames;
    TypePack expectedArgPack;

    const FunctionType* expectedFunction = expectedType ? get<FunctionType>(*expectedType) : nullptr;
    // This check ensures that expectedType is precisely optional and not any (since any is also an optional type)
    if (expectedType && isOptional(*expectedType) && !get<AnyType>(*expectedType))
    {
        if (auto ut = get<UnionType>(*expectedType))
        {
            for (auto u : ut)
            {
                if (get<FunctionType>(u) && !isNil(u))
                {
                    expectedFunction = get<FunctionType>(u);
                    break;
                }
            }
        }
    }

    if (expectedFunction)
    {
        expectedArgPack = extendTypePack(*arena, builtinTypes, expectedFunction->argTypes, fn->args.size);

        genericTypes = expectedFunction->generics;
        genericTypePacks = expectedFunction->genericPacks;
    }


    bool hasExplicitSelf;
    bool hasSelf;

    if (FFlag::DebugLuauUserDefinedClasses)
    {
        hasExplicitSelf = enclosingClass != nullptr && fn->args.size > 0 && fn->args.data[0]->name == "self";
        hasSelf = hasExplicitSelf || fn->self != nullptr;

        if (hasSelf)
        {
            TypeId selfType = nullptr;
            if (enclosingClass != nullptr)
                selfType = enclosingClass->instanceTy;
            else
                selfType = freshType(signatureScope, Polarity::Negative);

            AstLocal* selfLocal = fn->self ? fn->self : hasExplicitSelf ? fn->args.data[0] : nullptr;
            LUAU_ASSERT(selfLocal);

            argTypes.push_back(selfType);
            argNames.emplace_back(FunctionArgument{selfLocal->name.value, selfLocal->location});

            signatureScope->bindings[selfLocal] = Binding{selfType, selfLocal->location};

            DefId def = dfg->getDef(selfLocal);
            signatureScope->lvalueTypes[def] = selfType;
            updateRValueRefinements(signatureScope, def, selfType);
        }
    }
    else
    {
        if (fn->self)
        {
            TypeId selfType = freshType(signatureScope, Polarity::Negative);
            argTypes.push_back(selfType);
            argNames.emplace_back(FunctionArgument{fn->self->name.value, fn->self->location});
            signatureScope->bindings[fn->self] = Binding{selfType, fn->self->location};

            DefId def = dfg->getDef(fn->self);
            signatureScope->lvalueTypes[def] = selfType;
            updateRValueRefinements(signatureScope, def, selfType);
        }
    }


    for (size_t i = 0; i < fn->args.size; ++i)
    {
        if (FFlag::DebugLuauUserDefinedClasses)
        {
            if (hasExplicitSelf && i == 0)
            {
                // It is forbidden to put a type annotation on the self
                // parameter of a class method, but we still need to populate
                // astResolvedTypes for TC2.
                if (AstType* annotation = fn->args.data[0]->annotation)
                    resolveType(signatureScope, annotation, /* inTypeArguments */ false, /* replaceErrorWithFresh */ true, Polarity::Negative);
                continue;
            }
        }

        AstLocal* local = fn->args.data[i];

        TypeId argTy = nullptr;
        if (local->annotation)
        {
            argTy = resolveType(signatureScope, local->annotation, /* inTypeArguments */ false, /* replaceErrorWithFresh*/ true, Polarity::Negative);
        }
        else
        {
            if (i < expectedArgPack.head.size())
                argTy = expectedArgPack.head[i];
            else
                argTy = freshType(signatureScope, Polarity::Negative);
        }

        argTypes.push_back(argTy);
        argNames.emplace_back(FunctionArgument{local->name.value, local->location});

        signatureScope->bindings[local] = Binding{argTy, local->location};

        DefId def = dfg->getDef(local);
        signatureScope->lvalueTypes[def] = argTy;
        updateRValueRefinements(signatureScope, def, argTy);
    }

    TypePackId varargPack = nullptr;

    if (fn->vararg)
    {
        if (fn->varargAnnotation)
        {
            TypePackId annotationType =
                resolveTypePack(signatureScope, fn->varargAnnotation, /* inTypeArguments */ false, /* replaceErrorWithFresh */ true);
            varargPack = annotationType;
        }
        else if (expectedArgPack.tail && get<VariadicTypePack>(*expectedArgPack.tail))
            varargPack = *expectedArgPack.tail;
        else
            varargPack = builtinTypes->anyTypePack;

        signatureScope->varargPack = varargPack;
        bodyScope->varargPack = varargPack;
    }
    else
    {
        varargPack = arena->addTypePack(VariadicTypePack{builtinTypes->anyType, /*hidden*/ true});
        // We do not add to signatureScope->varargPack because ... is not valid
        // in functions without an explicit ellipsis.

        signatureScope->varargPack = std::nullopt;
        bodyScope->varargPack = std::nullopt;
    }

    LUAU_ASSERT(nullptr != varargPack);

    // Some of the unannotated parameters in argTypes will eventually be
    // generics, and some will not. The ones that are not generic will be
    // pruned when GeneralizationConstraint dispatches.

    // The self parameter never has an annotation and so could always become generic.
    if (fn->self)
        genericTypes.push_back(argTypes[0]);

    size_t typeIndex = fn->self ? 1 : 0;
    for (auto astArg : fn->args)
    {
        TypeId argTy = argTypes.at(typeIndex);
        if (!astArg->annotation)
            genericTypes.push_back(argTy);

        ++typeIndex;
    }

    varargPack = follow(varargPack);
    returnType = follow(returnType);
    if (!fn->varargAnnotation)
        genericTypePacks.push_back(varargPack);
    if (!fn->returnAnnotation)
        genericTypePacks.push_back(returnType);

    // If there is both an annotation and an expected type, the annotation wins.
    // Type checking will sort out any discrepancies later.
    if (fn->returnAnnotation)
    {
        TypePackId annotatedRetType =
            resolveTypePack(signatureScope, fn->returnAnnotation, /* inTypeArguments */ false, /* replaceErrorWithFresh*/ true);
        // We bind the annotated type directly here so that, when we need to
        // generate constraints for return typeArguments, we have a guarantee that we
        // know the annotated return type already, if one was provided.
        LUAU_ASSERT(get<FreeTypePack>(returnType));
        emplaceTypePack<BoundTypePack>(asMutable(returnType), annotatedRetType);
    }
    else if (expectedFunction)
    {
        emplaceTypePack<BoundTypePack>(asMutable(returnType), expectedFunction->retTypes);
    }

    // TODO: Preserve argument names in the function's type.

    FunctionType actualFunction{TypeLevel{}, arena->addTypePack(std::move(argTypes), varargPack), returnType};
    actualFunction.generics = std::move(genericTypes);
    actualFunction.genericPacks = std::move(genericTypePacks);
    actualFunction.argNames = std::move(argNames);
    actualFunction.hasSelf = FFlag::DebugLuauUserDefinedClasses ? hasSelf : fn->self != nullptr;

    FunctionDefinition defn;
    defn.definitionModuleName = module->name;
    defn.definitionLocation = fn->location;
    defn.varargLocation = fn->vararg ? std::make_optional(fn->varargLocation) : std::nullopt;
    defn.originalNameLocation = originalName.value_or(Location(fn->location.begin, 0));
    actualFunction.definition = defn;

    TypeId actualFunctionType = arena->addType(std::move(actualFunction));
    LUAU_ASSERT(actualFunctionType);
    module->astTypes[fn] = actualFunctionType;

    if (expectedType && get<FreeType>(*expectedType))
        bindFreeType(*expectedType, actualFunctionType);

    if (FFlag::LuauCyclicRequireTypeInference)
        cgraph->scopeToFunction[signatureScope.get()] = actualFunctionType;
    else
        scopeToFunction[signatureScope.get()] = actualFunctionType;

    return {
        /* signature */ actualFunctionType,
        /* signatureScope */ std::move(signatureScope),
        /* bodyScope */ std::move(bodyScope),
    };
}

void ConstraintGenerator::checkFunctionBody(const ScopePtr& scope, AstExprFunction* fn)
{
    // If it is possible for execution to reach the end of the function, the return type must be compatible with ()
    ControlFlow cf = visitBlockWithoutChildScope(scope, fn->body);
    if (cf == ControlFlow::None)
        addConstraint(scope, fn->location, PackSubtypeConstraint{builtinTypes->emptyTypePack, scope->returnType});
}

TypeId ConstraintGenerator::resolveReferenceType(
    const ScopePtr& scope,
    AstType* ty,
    AstTypeReference* ref,
    bool inTypeArguments,
    bool replaceErrorWithFresh
)
{
    TypeId result = nullptr;

    if (FFlag::DebugLuauMagicTypes)
    {
        if (ref->name == "_luau_ice")
            ice->ice("_luau_ice encountered", ty->location);
        else if (ref->name == "_luau_print")
        {
            if (ref->parameters.size != 1 || !ref->parameters.data[0].type)
            {
                reportError(ty->location, GenericError{"_luau_print requires one generic parameter"});
                module->astResolvedTypes[ty] = builtinTypes->errorType;
                return builtinTypes->errorType;
            }
            else
                return resolveType_(scope, ref->parameters.data[0].type, inTypeArguments);
        }
        else if (ref->name == "_luau_blocked_type")
        {
            return arena->addType(BlockedType{});
        }
    }

    std::optional<TypeFun> alias;

    if (ref->prefix.has_value())
    {
        alias = scope->lookupImportedType(ref->prefix->value, ref->name.value);
    }
    else
    {
        alias = scope->lookupType(ref->name.value);
    }

    if (FFlag::LuauUnconditionallyVisitTypeAliasParams)
    {
        std::vector<TypeId> parameters;
        std::vector<TypePackId> packParameters;

        for (const AstTypeOrPack& p : ref->parameters)
        {
            // We do not enforce the ordering of typeArguments vs. type packs here;
            // that is done in the parser.
            if (p.type)
            {
                parameters.push_back(resolveType_(scope, p.type, /* inTypeArguments */ true));
            }
            else if (p.typePack)
            {
                TypePackId tp = resolveTypePack_(scope, p.typePack, /*inTypeArguments*/ true);

                // If we need more regular typeArguments, we can use single
                // element type packs to fill those in. Alias might be `nullopt`
                // here, if we're referring to an unknown type alias, so check
                // that first.
                if (alias && parameters.size() < alias->typeParams.size() && size(tp) == 1 && finite(tp) && first(tp))
                    parameters.push_back(*first(tp));
                else
                    packParameters.push_back(tp);
            }
            else
            {
                // This indicates a parser bug: one of these two pointers
                // should be set.
                LUAU_ASSERT(false);
            }
        }

        if (!alias)
        {
            // We failed to look up the alias at all. The type checker will
            // report the lookup failure when it visits the type later.
            module->astTypeReferenceLookupFailures.insert(ty);
            result = builtinTypes->errorType;
            if (replaceErrorWithFresh)
                result = freshType(scope, Polarity::Mixed);
        }
        else if (alias->typeParams.empty() && alias->typePackParams.empty() && !ref->hasParameterList)
        {
            // We have an alias, but there are no arguments, nor does this
            // alias require any.
            result = alias->type;
        }
        else
        {
            // We have an alias, but we need to resolve the arguments.
            result = arena->addType(PendingExpansionType{ref->prefix, ref->name, std::move(parameters), std::move(packParameters)});

            // If we're not in a type argument context, we need to create a constraint that expands this.
            // The dispatching of the above constraint will queue up additional constraints for nested
            // type function applications.
            if (!inTypeArguments)
                addConstraint(scope, ty->location, TypeAliasExpansionConstraint{/* target */ result});
        }
    }
    else
    {

        if (alias.has_value())
        {
            // If the alias is not generic, we don't need to set up a blocked type and an instantiation constraint
            if (alias.has_value() && alias->typeParams.empty() && alias->typePackParams.empty() && !ref->hasParameterList)
            {
                result = alias->type;
            }
            else
            {
                std::vector<TypeId> parameters;
                std::vector<TypePackId> packParameters;

                for (const AstTypeOrPack& p : ref->parameters)
                {
                    // We do not enforce the ordering of typeArguments vs. type packs here;
                    // that is done in the parser.
                    if (p.type)
                    {
                        parameters.push_back(resolveType_(scope, p.type, /* inTypeArguments */ true));
                    }
                    else if (p.typePack)
                    {
                        TypePackId tp = resolveTypePack_(scope, p.typePack, /*inTypeArguments*/ true);

                        // If we need more regular typeArguments, we can use single element type packs to fill those in
                        if (parameters.size() < alias->typeParams.size() && size(tp) == 1 && finite(tp) && first(tp))
                            parameters.push_back(*first(tp));
                        else
                            packParameters.push_back(tp);
                    }
                    else
                    {
                        // This indicates a parser bug: one of these two pointers
                        // should be set.
                        LUAU_ASSERT(false);
                    }
                }

                result = arena->addType(PendingExpansionType{ref->prefix, ref->name, std::move(parameters), std::move(packParameters)});

                // If we're not in a type argument context, we need to create a constraint that expands this.
                // The dispatching of the above constraint will queue up additional constraints for nested
                // type function applications.
                if (!inTypeArguments)
                    addConstraint(scope, ty->location, TypeAliasExpansionConstraint{/* target */ result});
            }
        }
        else
        {
            // The type checker will report the lookup failure when it visits the type later.
            module->astTypeReferenceLookupFailures.insert(ty);
            result = builtinTypes->errorType;
            if (replaceErrorWithFresh)
                result = freshType(scope, Polarity::Mixed);
        }
    }

    if (is<TypeFunctionInstanceType>(follow(result)))
    {
        reportError(ty->location, UnappliedTypeFunction{});
        addConstraint(scope, ty->location, ReduceConstraint{result});
    }

    if (auto genericType = getMutable<GenericType>(follow(result)))
        genericType->polarity = (genericType->polarity & Polarity::Mixed) | polarity;

    return result;
}

namespace
{
Polarity polarityOfAccess(AstTableAccess access, Polarity p)
{
    switch (access)
    {
    case AstTableAccess::Read:
        return p;
    case AstTableAccess::Write:
        return invert(p);
    case AstTableAccess::ReadWrite:
        return Polarity::Mixed;
    default:
        return Polarity::Unknown;
    }
}
} // namespace

TypeId ConstraintGenerator::resolveTableType(const ScopePtr& scope, AstType* ty, AstTypeTable* tab, bool inTypeArguments, bool replaceErrorWithFresh)
{
    TableType::Props props;
    std::optional<TableIndexer> indexer;

    Polarity p = polarity;
    for (const AstTableProp& prop : tab->props)
    {
        Property& propRef = props[prop.name.value];

        // Set the polarity for the inner type
        polarity = polarityOfAccess(prop.access, p);

        TypeId propTy = resolveType_(scope, prop.type, inTypeArguments);

        propRef.typeLocation = prop.location;

        switch (prop.access)
        {
        case AstTableAccess::ReadWrite:
            propRef.readTy = propTy;
            propRef.writeTy = propTy;
            break;
        case AstTableAccess::Read:
            propRef.readTy = propTy;
            break;
        case AstTableAccess::Write:
            propRef.writeTy = propTy;
            break;
        default:
            ice->ice("Unexpected property access " + std::to_string(int(prop.access)));
            break;
        }
    }

    if (AstTableIndexer* astIndexer = tab->indexer)
    {
        if (astIndexer->access == AstTableAccess::Read)
        {
            polarity = p;
            indexer = TableIndexer{
                resolveType_(scope, astIndexer->indexType, inTypeArguments),
                resolveType_(scope, astIndexer->resultType, inTypeArguments),
                /*isReadOnly*/ true
            };
        }
        else if (astIndexer->access == AstTableAccess::Write)
            reportError(astIndexer->accessLocation.value_or(Location{}), GenericError{"write keyword is illegal here"});
        else if (astIndexer->access == AstTableAccess::ReadWrite)
        {
            polarity = Polarity::Mixed;
            indexer = TableIndexer{
                resolveType_(scope, astIndexer->indexType, inTypeArguments),
                resolveType_(scope, astIndexer->resultType, inTypeArguments),
            };
        }
        else
            ice->ice("Unexpected property access " + std::to_string(int(astIndexer->access)));
    }

    polarity = p;

    TableState state = TableState::Sealed;
    if (FFlag::DebugLuauExactTableTypes && tab->isExact)
        state = TableState::Exact;

    TypeId tableTy = arena->addType(TableType{props, indexer, scope->level, scope.get(), state});
    TableType* ttv = getMutable<TableType>(tableTy);

    ttv->definitionModuleName = module->name;
    ttv->definitionLocation = tab->location;

    return tableTy;
}

TypeId ConstraintGenerator::resolveFunctionType(
    const ScopePtr& scope,
    AstType* ty,
    AstTypeFunction* fn,
    bool inTypeArguments,
    bool replaceErrorWithFresh
)
{
    bool hasGenerics = fn->generics.size > 0 || fn->genericPacks.size > 0;
    ScopePtr signatureScope = nullptr;

    std::vector<TypeId> genericTypes;
    std::vector<TypePackId> genericTypePacks;

    // If we don't have generics, we do not need to generate a child scope
    // for the generic bindings to live on.
    if (hasGenerics)
    {
        signatureScope = childScope(fn, scope);

        std::vector<std::pair<Name, GenericTypeDefinition>> genericDefinitions = createGenerics(signatureScope, fn->generics);
        std::vector<std::pair<Name, GenericTypePackDefinition>> genericPackDefinitions = createGenericPacks(signatureScope, fn->genericPacks);

        for (const auto& [name, g] : genericDefinitions)
        {
            genericTypes.push_back(g.ty);
        }

        for (const auto& [name, g] : genericPackDefinitions)
        {
            genericTypePacks.push_back(g.tp);
        }
    }
    else
    {
        // To eliminate the need to branch on hasGenerics below, we say that
        // the signature scope is the parent scope if we don't have
        // generics.
        signatureScope = scope;
    }

    AstTypePackExplicit tempArgTypes{Location{}, fn->argTypes};

    Polarity p = polarity;
    polarity = invert(polarity);
    TypePackId argTypes = resolveTypePack_(signatureScope, &tempArgTypes, inTypeArguments, replaceErrorWithFresh);
    polarity = p;
    TypePackId returnTypes = resolveTypePack_(signatureScope, fn->returnTypes, inTypeArguments, replaceErrorWithFresh);

    // TODO: FunctionType needs a pointer to the scope so that we know
    // how to quantify/instantiate it.
    FunctionType ftv{TypeLevel{}, {}, {}, argTypes, returnTypes};
    ftv.isCheckedFunction = fn->isCheckedFunction();
    AstAttr* deprecatedAttr = fn->getAttribute(AstAttr::Type::Deprecated);
    ftv.isDeprecatedFunction = deprecatedAttr != nullptr;
    if (deprecatedAttr)
    {
        ftv.deprecatedInfo = std::make_shared<AstAttr::DeprecatedInfo>(deprecatedAttr->deprecatedInfo());
    }


    // This replicates the behavior of the appropriate FunctionType
    // constructors.
    ftv.generics = std::move(genericTypes);
    ftv.genericPacks = std::move(genericTypePacks);

    ftv.argNames.reserve(fn->argNames.size);
    for (const auto& el : fn->argNames)
    {
        if (el)
        {
            const auto& [name, location] = *el;
            ftv.argNames.emplace_back(FunctionArgument{name.value, location});
        }
        else
            ftv.argNames.emplace_back(std::nullopt);
    }

    return arena->addType(std::move(ftv));
}

TypeId ConstraintGenerator::resolveType(
    const ScopePtr& scope,
    AstType* ty,
    bool inTypeArguments,
    bool replaceErrorWithFresh,
    Polarity initialPolarity
)
{
    // Reset the polarity
    polarity = initialPolarity;
    return resolveType_(scope, ty, inTypeArguments, replaceErrorWithFresh);
}

TypeId ConstraintGenerator::resolveType_(const ScopePtr& scope, AstType* ty, bool inTypeArguments, bool replaceErrorWithFresh)
{
    TypeId result = nullptr;

    if (auto ref = ty->as<AstTypeReference>())
    {
        result = resolveReferenceType(scope, ty, ref, inTypeArguments, replaceErrorWithFresh);
    }
    else if (auto tab = ty->as<AstTypeTable>())
    {
        result = resolveTableType(scope, ty, tab, inTypeArguments, replaceErrorWithFresh);
    }
    else if (auto fn = ty->as<AstTypeFunction>())
    {
        result = resolveFunctionType(scope, ty, fn, inTypeArguments, replaceErrorWithFresh);
    }
    else if (auto tof = ty->as<AstTypeTypeof>())
    {
        TypeId exprType = check(scope, tof->expr).ty;
        result = exprType;
    }
    else if (ty->is<AstTypeOptional>())
    {
        result = builtinTypes->nilType;
    }
    else if (auto unionAnnotation = ty->as<AstTypeUnion>())
    {
        if (unionAnnotation->types.size == 1)
            result = resolveType_(scope, unionAnnotation->types.data[0], inTypeArguments);
        else
        {
            std::vector<TypeId> parts;
            for (AstType* part : unionAnnotation->types)
            {
                parts.push_back(resolveType_(scope, part, inTypeArguments));
            }

            result = arena->addType(UnionType{std::move(parts)});
        }
    }
    else if (auto intersectionAnnotation = ty->as<AstTypeIntersection>())
    {
        if (intersectionAnnotation->types.size == 1)
            result = resolveType_(scope, intersectionAnnotation->types.data[0], inTypeArguments);
        else
        {
            std::vector<TypeId> parts;
            for (AstType* part : intersectionAnnotation->types)
            {
                parts.push_back(resolveType_(scope, part, inTypeArguments));
            }

            result = arena->addType(IntersectionType{std::move(parts)});
        }
    }
    else if (auto typeGroupAnnotation = ty->as<AstTypeGroup>())
    {
        result = resolveType_(scope, typeGroupAnnotation->type, inTypeArguments);
    }
    else if (auto boolAnnotation = ty->as<AstTypeSingletonBool>())
    {
        if (boolAnnotation->value)
            result = builtinTypes->trueType;
        else
            result = builtinTypes->falseType;
    }
    else if (auto stringAnnotation = ty->as<AstTypeSingletonString>())
    {
        result = arena->addType(SingletonType(StringSingleton{std::string(stringAnnotation->value.data, stringAnnotation->value.size)}));
    }
    else if (ty->is<AstTypeError>())
    {
        result = builtinTypes->errorType;
        if (replaceErrorWithFresh)
            result = freshType(scope, polarity);
    }
    else
    {
        LUAU_ASSERT(0);
        result = builtinTypes->errorType;
    }

    module->astResolvedTypes[ty] = result;
    return result;
}

TypePackId ConstraintGenerator::resolveTypePack(
    const ScopePtr& scope,
    AstTypePack* tp,
    bool inTypeArgument,
    bool replaceErrorWithFresh,
    Polarity initialPolarity
)
{
    polarity = initialPolarity;
    return resolveTypePack_(scope, tp, inTypeArgument, replaceErrorWithFresh);
}

TypePackId ConstraintGenerator::resolveTypePack_(const ScopePtr& scope, AstTypePack* tp, bool inTypeArgument, bool replaceErrorWithFresh)
{
    TypePackId result;
    if (auto expl = tp->as<AstTypePackExplicit>())
    {
        result = resolveTypePack_(scope, expl->typeList, inTypeArgument, replaceErrorWithFresh);
    }
    else if (auto var = tp->as<AstTypePackVariadic>())
    {
        TypeId ty = resolveType_(scope, var->variadicType, inTypeArgument, replaceErrorWithFresh);
        result = arena->addTypePack(TypePackVar{VariadicTypePack{ty}});
    }
    else if (auto gen = tp->as<AstTypePackGeneric>())
    {
        if (std::optional<TypePackId> lookup = scope->lookupPack(gen->genericName.value))
        {
            result = *lookup;
        }
        else
        {
            // The type checker will report the lookup failure when it visits the type pack later.
            module->astTypePackReferenceLookupFailures.insert(tp);
            result = builtinTypes->errorTypePack;
        }
    }
    else
    {
        LUAU_ASSERT(0);
        result = builtinTypes->errorTypePack;
    }

    if (auto gtp = getMutable<GenericTypePack>(follow(result)))
    {
        // The initial polarity is unknown, so we flip that bit off
        // by saying that we are at most Mixed, and then add in the
        // polarity we're currently processing.
        gtp->polarity = (gtp->polarity & Polarity::Mixed) | polarity;
    }

    module->astResolvedTypePacks[tp] = result;
    return result;
}

TypePackId ConstraintGenerator::resolveTypePack_(const ScopePtr& scope, const AstTypeList& list, bool inTypeArguments, bool replaceErrorWithFresh)
{
    std::vector<TypeId> head;

    for (AstType* headTy : list.types)
    {
        head.push_back(resolveType_(scope, headTy, inTypeArguments, replaceErrorWithFresh));
    }

    std::optional<TypePackId> tail = std::nullopt;
    if (list.tailType)
    {
        tail = resolveTypePack_(scope, list.tailType, inTypeArguments, replaceErrorWithFresh);
    }

    return addTypePack(std::move(head), tail);
}

TypePackId ConstraintGenerator::resolveTypePack(
    const ScopePtr& scope,
    const AstTypeList& list,
    bool inTypeArguments,
    bool replaceErrorWithFresh,
    Polarity initialPolarity
)
{
    polarity = initialPolarity;
    return resolveTypePack_(scope, list, inTypeArguments, replaceErrorWithFresh);
}

std::vector<std::pair<Name, GenericTypeDefinition>> ConstraintGenerator::createGenerics(
    const ScopePtr& scope,
    AstArray<AstGenericType*> generics,
    bool useCache,
    bool addTypes
)
{
    std::vector<std::pair<Name, GenericTypeDefinition>> result;
    for (const auto* generic : generics)
    {
        TypeId genericTy = nullptr;

        if (auto it = scope->parent->typeAliasTypeParameters.find(generic->name.value);
            useCache && it != scope->parent->typeAliasTypeParameters.end())
            genericTy = it->second;
        else
        {
            genericTy = arena->addType(GenericType{scope.get(), generic->name.value, Polarity::None});
            scope->parent->typeAliasTypeParameters[generic->name.value] = genericTy;
        }

        std::optional<TypeId> defaultTy = std::nullopt;

        if (generic->defaultValue)
            defaultTy = arena->addType(BlockedType{});

        if (addTypes)
            scope->privateTypeBindings[generic->name.value] = TypeFun{genericTy};

        result.emplace_back(generic->name.value, GenericTypeDefinition{genericTy, defaultTy});
    }

    return result;
}

std::vector<std::pair<Name, GenericTypePackDefinition>> ConstraintGenerator::createGenericPacks(
    const ScopePtr& scope,
    AstArray<AstGenericTypePack*> generics,
    bool useCache,
    bool addTypes
)
{
    std::vector<std::pair<Name, GenericTypePackDefinition>> result;
    for (const auto* generic : generics)
    {
        TypePackId genericTy;

        if (auto it = scope->parent->typeAliasTypePackParameters.find(generic->name.value);
            useCache && it != scope->parent->typeAliasTypePackParameters.end())
            genericTy = it->second;
        else
        {
            genericTy = arena->addTypePack(TypePackVar{GenericTypePack{scope.get(), generic->name.value, Polarity::None}});
            scope->parent->typeAliasTypePackParameters[generic->name.value] = genericTy;
        }

        std::optional<TypePackId> defaultTy = std::nullopt;

        if (generic->defaultValue)
            defaultTy = arena->addTypePack(BlockedTypePack{});

        if (addTypes)
            scope->privateTypePackBindings[generic->name.value] = genericTy;

        result.emplace_back(generic->name.value, GenericTypePackDefinition{genericTy, defaultTy});
    }

    return result;
}

Inference ConstraintGenerator::flattenPack(const ScopePtr& scope, Location location, InferencePack pack)
{
    const auto& [tp, refinements] = pack;
    RefinementId refinement = nullptr;
    if (!refinements.empty())
        refinement = refinements[0];

    if (auto f = first(tp))
        return Inference{*f, refinement};

    TypeId typeResult = arena->addType(BlockedType{});
    auto c = addConstraint(scope, location, UnpackConstraint{{typeResult}, tp});
    getMutable<BlockedType>(typeResult)->setOwner(c);

    return Inference{typeResult, refinement};
}

void ConstraintGenerator::reportError(Location location, TypeErrorData err)
{
    errors.emplace_back(location, module->name, std::move(err));
    if (logger)
        logger->captureGenerationError(errors.back());
}

void ConstraintGenerator::reportCodeTooComplex(Location location)
{
    errors.emplace_back(location, module->name, CodeTooComplex{});
    if (logger)
        logger->captureGenerationError(errors.back());

    recursionLimitMet = true;
}

TypeId ConstraintGenerator::makeUnion(const ScopePtr& scope, Location location, TypeId lhs, TypeId rhs)
{
    if (get<NeverType>(follow(lhs)))
        return rhs;
    if (get<NeverType>(follow(rhs)))
        return lhs;

    TypeId result = simplifyUnion(scope, location, lhs, rhs);
    if (is<UnionType>(follow(result)))
        unionsToSimplify.push_back(result);
    return result;
}

TypeId ConstraintGenerator::makeUnion(std::vector<TypeId> options)
{
    UnionBuilder ub{arena, builtinTypes};
    ub.reserve(options.size());

    for (auto option : options)
        ub.add(option);

    TypeId unionTy = ub.build();

    if (is<UnionType>(unionTy))
        unionsToSimplify.push_back(unionTy);

    return unionTy;
}

TypeId ConstraintGenerator::makeIntersect(const ScopePtr& scope, Location location, TypeId lhs, TypeId rhs)
{
    TypeId resultType = createTypeFunctionInstance(builtinTypes->typeFunctions->intersectFunc, {lhs, rhs}, {}, scope, location);

    return resultType;
}

struct GlobalPrepopulator : AstVisitor
{
    const NotNull<Scope> globalScope;
    const NotNull<TypeArena> arena;
    const NotNull<const DataFlowGraph> dfg;

    DenseHashSet<AstName> uninitializedGlobals;

    GlobalPrepopulator(NotNull<Scope> globalScope, NotNull<TypeArena> arena, NotNull<const DataFlowGraph> dfg)
        : globalScope(globalScope)
        , arena(arena)
        , dfg(dfg)
    {
    }

    bool visit(AstExprGlobal* global) override
    {
        if (auto ty = globalScope->lookup(global->name))
        {
            DefId def = dfg->getDef(global);
            globalScope->lvalueTypes[def] = *ty;
        }

        return true;
    }

    bool visit(AstStatAssign* assign) override
    {
        for (const Luau::AstExpr* expr : assign->vars)
        {
            if (const AstExprGlobal* g = expr->as<AstExprGlobal>())
            {
                if (!globalScope->lookup(g->name))
                    globalScope->globalsToWarn.insert(g->name.value);

                if (globalScope->bindings.find(g->name) == globalScope->bindings.end())
                {
                    TypeId bt = arena->addType(BlockedType{});
                    uninitializedGlobals.insert(g->name);
                    globalScope->bindings[g->name] = Binding{bt, g->location};
                }
            }
        }

        return true;
    }

    bool visit(AstStatFunction* function) override
    {
        if (AstExprGlobal* g = function->name->as<AstExprGlobal>())
        {
            TypeId bt = arena->addType(BlockedType{});
            uninitializedGlobals.insert(g->name);
            globalScope->bindings[g->name] = Binding{bt};
        }

        return true;
    }

    bool visit(AstType*) override
    {
        return true;
    }

    bool visit(class AstTypePack* node) override
    {
        return true;
    }
};

void ConstraintGenerator::prepopulateGlobalScopeForFragmentTypecheck(const ScopePtr& globalScope, const ScopePtr& resumeScope, AstStatBlock* program)
{
    // Handle type function globals as well, without preparing a module scope since they have a separate environment
    GlobalPrepopulator tfgp{NotNull{typeFunctionRuntime->rootScope.get()}, arena, dfg};
    program->visit(&tfgp);

    for (auto name : tfgp.uninitializedGlobals)
        uninitializedGlobals.insert(name);
}

void ConstraintGenerator::prepopulateGlobalScope(const ScopePtr& globalScope, AstStatBlock* program)
{
    GlobalPrepopulator gp{NotNull{globalScope.get()}, arena, dfg};

    if (prepareModuleScope)
        prepareModuleScope(module->name, globalScope);

    program->visit(&gp);

    for (auto name : gp.uninitializedGlobals)
        uninitializedGlobals.insert(name);

    // Handle type function globals as well, without preparing a module scope since they have a separate environment
    GlobalPrepopulator tfgp{NotNull{typeFunctionRuntime->rootScope.get()}, arena, dfg};
    program->visit(&tfgp);

    for (auto name : tfgp.uninitializedGlobals)
        uninitializedGlobals.insert(name);
}

bool ConstraintGenerator::recordPropertyAssignment(TypeId ty)
{
    DenseHashSet<TypeId> seen;
    VecDeque<TypeId> queue;

    queue.push_back(ty);

    bool incremented = false;

    while (!queue.empty())
    {
        const TypeId t = follow(queue.front());
        queue.pop_front();

        if (seen.find(t))
            continue;
        seen.insert(t);

        if (auto tt = getMutable<TableType>(t); tt && tt->state == TableState::Unsealed)
        {
            tt->remainingProps += 1;
            incremented = true;
        }
        else if (auto mt = get<MetatableType>(t))
            queue.push_back(mt->table);
        else if (TypeIds* localDomain = localTypes.find(t))
        {
            for (TypeId domainTy : *localDomain)
                queue.push_back(domainTy);
        }
        else if (auto ut = get<UnionType>(t))
        {
            for (TypeId part : ut)
                queue.push_back(part);
        }
    }

    return incremented;
}

void ConstraintGenerator::recordInferredBinding(AstLocal* local, TypeId ty)
{
    if (InferredBinding* ib = inferredBindings.find(local))
        ib->types.insert(ty);
}

void ConstraintGenerator::fillInInferredBindings(const ScopePtr& globalScope, AstStatBlock* block)
{
    for (const auto& [symbol, p] : inferredBindings)
    {
        const auto& [scope, location, types] = p;

        std::vector<TypeId> tys(types.begin(), types.end());
        if (tys.size() == 1)
            scope->bindings[symbol] = Binding{tys.front(), location};
        else
        {
            TypeId ty = makeUnion(std::move(tys));
            scope->bindings[symbol] = Binding{ty, location};
        }
    }
}

std::vector<std::optional<TypeId>> ConstraintGenerator::getExpectedCallTypesForFunctionOverloads(const TypeId fnType)
{
    std::vector<TypeId> funTys;
    if (auto it = get<IntersectionType>(follow(fnType)))
    {
        for (TypeId intersectionComponent : it)
        {
            funTys.push_back(intersectionComponent);
        }
    }

    std::vector<std::optional<TypeId>> expectedTypes;
    // For a list of functions f_0 : e_0 -> r_0, ... f_n : e_n -> r_n,
    // emit a list of arguments that the function could take at each position
    // by unioning the arguments at each place
    auto assignOption = [this, &expectedTypes](size_t index, TypeId ty)
    {
        if (index == expectedTypes.size())
        {
            expectedTypes.emplace_back(ty);
        }
        else if (ty)
        {
            auto& el = expectedTypes[index];

            if (!el)
                el = ty;
            else
            {
                std::vector<TypeId> result = reduceUnion({*el, ty});
                if (result.empty())
                    el = builtinTypes->neverType;
                else if (result.size() == 1)
                    el = result[0];
                else
                    el = makeUnion(std::move(result));
            }
        }
    };

    for (const TypeId overload : funTys)
    {
        if (const FunctionType* ftv = get<FunctionType>(follow(overload)))
        {
            auto [argsHead, argsTail] = flatten(ftv->argTypes);
            size_t start = ftv->hasSelf ? 1 : 0;
            size_t index = 0;
            for (size_t i = start; i < argsHead.size(); ++i)
                assignOption(index++, argsHead[i]);
            if (argsTail)
            {
                argsTail = follow(*argsTail);
                if (const VariadicTypePack* vtp = get<VariadicTypePack>(*argsTail))
                {
                    while (index < funTys.size())
                        assignOption(index++, vtp->ty);
                }
            }
        }
    }

    // TODO vvijay Feb 24, 2023 apparently we have to demote the typeArguments here?

    return expectedTypes;
}

TypeId ConstraintGenerator::createTypeFunctionInstance(
    const TypeFunction& function,
    std::vector<TypeId> typeArguments,
    std::vector<TypePackId> packArguments,
    const ScopePtr& scope,
    Location location
)
{
    TypeId result = arena->addTypeFunction(function, std::move(typeArguments), std::move(packArguments));
    addConstraint(scope, location, ReduceConstraint{result});
    return result;
}

TypeId ConstraintGenerator::simplifyUnion(const ScopePtr& scope, Location location, TypeId left, TypeId right)
{
    return ::Luau::simplifyUnion(builtinTypes, arena, left, right).result;
}

void ConstraintGenerator::updateRValueRefinements(const ScopePtr& scope, DefId def, TypeId ty) const
{
    updateRValueRefinements(scope.get(), def, ty);
}

void ConstraintGenerator::updateRValueRefinements(Scope* scope, DefId def, TypeId ty) const
{
    scope->rvalueRefinements[def] = ty;
    if (auto sym = dfg->getSymbolFromDef(def))
        scope->refinements[*sym] = ty;
}


} // namespace Luau