Subtyping.cpp

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

#include "Luau/Subtyping.h"

#include "Luau/Common.h"
#include "Luau/Error.h"
#include "Luau/Normalize.h"
#include "Luau/RecursionCounter.h"
#include "Luau/Scope.h"
#include "Luau/ScopedSeenSet.h"
#include "Luau/Substitution.h"
#include "Luau/TxnLog.h"
#include "Luau/Type.h"
#include "Luau/TypeArena.h"
#include "Luau/TypeFunction.h"
#include "Luau/TypeIds.h"
#include "Luau/TypePack.h"
#include "Luau/TypePath.h"
#include "Luau/TypeUtils.h"

LUAU_DYNAMIC_FASTINTVARIABLE(LuauSubtypingRecursionLimit, 100)

LUAU_FASTFLAGVARIABLE(DebugLuauSubtypingCheckPathValidity)
LUAU_FASTINTVARIABLE(LuauSubtypingReasoningLimit, 100)
LUAU_FASTFLAGVARIABLE(LuauMorePreciseErrorSuppression)
LUAU_FASTFLAGVARIABLE(LuauSubtypingMissingPropertiesAsNil)
LUAU_FASTFLAG(LuauTableFreezeCheckIsSubtype)
LUAU_FASTFLAG(LuauUnifyWithSubtyping2)
LUAU_FASTINTVARIABLE(LuauSubtypingIterationLimit, 20000)
LUAU_FASTFLAGVARIABLE(LuauSubtypingReplaceBounds)
LUAU_FASTFLAG(LuauOverloadGetsInstantiated)
LUAU_FASTFLAGVARIABLE(LuauFollowGenericBeforeCheckingIfMapped)

namespace Luau
{

bool SubtypingReasoning::operator==(const SubtypingReasoning& other) const
{
    return subPath == other.subPath && superPath == other.superPath && variance == other.variance;
}

size_t SubtypingReasoningHash::operator()(const SubtypingReasoning& r) const
{
    return TypePath::PathHash()(r.subPath) ^ (TypePath::PathHash()(r.superPath) << 1) ^ (static_cast<size_t>(r.variance) << 1);
}

MappedGenericEnvironment::MappedGenericFrame::MappedGenericFrame(
    DenseHashMap<TypePackId, std::optional<TypePackId>> mappings,
    const std::optional<size_t> parentScopeIndex
)
    : mappings(std::move(mappings))
    , parentScopeIndex(parentScopeIndex)
{
}

MappedGenericEnvironment::LookupResult MappedGenericEnvironment::lookupGenericPack(TypePackId genericTp) const
{
    genericTp = follow(genericTp);

    std::optional<size_t> currentFrameIndex = currentScopeIndex;

    while (currentFrameIndex)
    {
        const MappedGenericFrame& currentFrame = frames[*currentFrameIndex];
        if (const auto mappedPack = currentFrame.mappings.find(genericTp))
        {
            if (*mappedPack)
                return mappedPack->value();
            else
                return Unmapped{*currentFrameIndex};
        }

        currentFrameIndex = currentFrame.parentScopeIndex;
    }

    // Do a DFS of children to see if any enclosed scope mentions this generic pack
    if (currentScopeIndex)
    {
        const MappedGenericFrame& baseFrame = frames[*currentScopeIndex];
        std::vector<size_t> toCheck = std::vector(baseFrame.children.begin(), baseFrame.children.end());

        while (!toCheck.empty())
        {
            const size_t currIndex = toCheck.back();
            toCheck.pop_back();

            const MappedGenericFrame& currentFrame = frames[currIndex];
            if (const auto mappedPack = currentFrame.mappings.find(genericTp))
            {
                if (*mappedPack)
                    return mappedPack->value();
                else
                    return Unmapped{currIndex};
            }

            toCheck.insert(toCheck.end(), currentFrame.children.begin(), currentFrame.children.end());
        }
    }

    return NotBindable{};
}

void MappedGenericEnvironment::pushFrame(const std::vector<TypePackId>& genericTps)
{
    DenseHashMap<TypePackId, std::optional<TypePackId>> mappings{nullptr};

    for (TypePackId tp : genericTps)
        mappings[tp] = std::nullopt;

    frames.emplace_back(std::move(mappings), currentScopeIndex);

    const size_t newFrameIndex = frames.size() - 1;

    if (currentScopeIndex)
        frames[*currentScopeIndex].children.insert(newFrameIndex);

    currentScopeIndex = newFrameIndex;
}

void MappedGenericEnvironment::popFrame()
{
    LUAU_ASSERT(currentScopeIndex);
    if (currentScopeIndex)
    {
        const std::optional<size_t> newFrameIndex = frames[*currentScopeIndex].parentScopeIndex;
        currentScopeIndex = newFrameIndex.value_or(0);
    }
}

bool MappedGenericEnvironment::bindGeneric(TypePackId genericTp, TypePackId bindeeTp)
{
    // We shouldn't bind generic type packs to themselves
    if (genericTp == bindeeTp)
        return true;

    if (!get<GenericTypePack>(genericTp))
    {
        LUAU_ASSERT(!"bindGeneric should not be called with a non-generic type pack");
        return false;
    }

    const LookupResult lookupResult = lookupGenericPack(genericTp);
    if (const Unmapped* unmapped = get_if<Unmapped>(&lookupResult))
    {
        frames[unmapped->scopeIndex].mappings[genericTp] = bindeeTp;
        return true;
    }
    else
    {
        return false;
    }
}

template<typename TID>
static void assertReasoningValid_DEPRECATED(TID subTy, TID superTy, const SubtypingResult& result, NotNull<BuiltinTypes> builtinTypes)
{
    if (!FFlag::DebugLuauSubtypingCheckPathValidity)
        return;

    for (const SubtypingReasoning& reasoning : result.reasoning)
    {
        LUAU_ASSERT(traverse_DEPRECATED(subTy, reasoning.subPath, builtinTypes));
        LUAU_ASSERT(traverse_DEPRECATED(superTy, reasoning.superPath, builtinTypes));
    }
}

template<typename TID>
static void assertReasoningValid(TID subTy, TID superTy, const SubtypingResult& result, NotNull<BuiltinTypes> builtinTypes, NotNull<TypeArena> arena)
{
    if (!FFlag::DebugLuauSubtypingCheckPathValidity)
        return;

    for (const SubtypingReasoning& reasoning : result.reasoning)
    {
        LUAU_ASSERT(traverse(subTy, reasoning.subPath, builtinTypes, arena));
        LUAU_ASSERT(traverse(superTy, reasoning.superPath, builtinTypes, arena));
    }
}

template<>
void assertReasoningValid<TableIndexer>(TableIndexer, TableIndexer, const SubtypingResult&, NotNull<BuiltinTypes>, NotNull<TypeArena>)
{
    // This specialization exists so that we can invoke methods like
    // isInvariantWith() on a pair of TableIndexers.
}

static SubtypingReasonings mergeReasonings(const SubtypingReasonings& a, const SubtypingReasonings& b)
{
    SubtypingReasonings result{kEmptyReasoning};

    for (const SubtypingReasoning& r : a)
    {
        if (r.variance == SubtypingVariance::Invariant)
            result.insert(r);
        else if (r.variance == SubtypingVariance::Covariant || r.variance == SubtypingVariance::Contravariant)
        {
            SubtypingReasoning inverseReasoning = SubtypingReasoning{
                r.subPath, r.superPath, r.variance == SubtypingVariance::Covariant ? SubtypingVariance::Contravariant : SubtypingVariance::Covariant
            };
            if (b.contains(inverseReasoning))
                result.insert(SubtypingReasoning{r.subPath, r.superPath, SubtypingVariance::Invariant});
            else
                result.insert(r);
        }

        if (result.size() >= size_t(FInt::LuauSubtypingReasoningLimit))
            return result;
    }

    for (const SubtypingReasoning& r : b)
    {
        if (r.variance == SubtypingVariance::Invariant)
            result.insert(r);
        else if (r.variance == SubtypingVariance::Covariant || r.variance == SubtypingVariance::Contravariant)
        {
            SubtypingReasoning inverseReasoning = SubtypingReasoning{
                r.subPath, r.superPath, r.variance == SubtypingVariance::Covariant ? SubtypingVariance::Contravariant : SubtypingVariance::Covariant
            };
            if (a.contains(inverseReasoning))
                result.insert(SubtypingReasoning{r.subPath, r.superPath, SubtypingVariance::Invariant});
            else
                result.insert(r);
        }

        if (result.size() >= size_t(FInt::LuauSubtypingReasoningLimit))
            return result;
    }

    return result;
}

SubtypingResult& SubtypingResult::andAlso(SubtypingResult other, SubtypingSuppressionPolicy policy)
{
    // If the other result is not a subtype, we want to join all of its
    // reasonings to this one. If this result already has reasonings of its own,
    // those need to be attributed here whenever this _also_ failed.
    if (!other.isSubtype)
    {
        if (isSubtype)
            reasoning = std::move(other.reasoning);
        else
            // NOTE: This probably doesn't need to be two copies.
            reasoning = mergeReasonings(reasoning, other.reasoning);
    }

    isSubtype &= other.isSubtype;
    if (FFlag::LuauMorePreciseErrorSuppression)
    {
        if (policy == SubtypingSuppressionPolicy::All)
            isErrorSuppressing &= other.isErrorSuppressing;
        else
            isErrorSuppressing |= other.isErrorSuppressing;
    }
    normalizationTooComplex |= other.normalizationTooComplex;
    isCacheable &= other.isCacheable;
    errors.insert(errors.end(), other.errors.begin(), other.errors.end());
    genericBoundsMismatches.insert(genericBoundsMismatches.end(), other.genericBoundsMismatches.begin(), other.genericBoundsMismatches.end());
    assumedConstraints.insert(assumedConstraints.end(), other.assumedConstraints.begin(), other.assumedConstraints.end());

    return *this;
}

SubtypingResult& SubtypingResult::orElse(SubtypingResult other)
{
    // If this result is a subtype, we do not join the reasoning lists. If this
    // result is not a subtype, but the other is a subtype, we want to _clear_
    // our reasoning list. If both results are not subtypes, we join the
    // reasoning lists.
    if (!isSubtype)
    {
        if (other.isSubtype)
        {
            reasoning.clear();
            assumedConstraints = std::move(other.assumedConstraints);
        }
        else
        {
            reasoning = mergeReasonings(reasoning, other.reasoning);
            if (FFlag::LuauMorePreciseErrorSuppression)
                isErrorSuppressing |= other.isErrorSuppressing;
        }
    }
    else if (FFlag::LuauUnifyWithSubtyping2 && other.isSubtype)
    {
        // If the other result has assumed constraints, we drop ours (given
        // we represent a failed subtype) and then take the constraints of
        // the other check.
        assumedConstraints = std::move(other.assumedConstraints);
    }

    isSubtype |= other.isSubtype;
    normalizationTooComplex |= other.normalizationTooComplex;
    isCacheable &= other.isCacheable;
    errors.insert(errors.end(), other.errors.begin(), other.errors.end());
    genericBoundsMismatches.insert(genericBoundsMismatches.end(), other.genericBoundsMismatches.begin(), other.genericBoundsMismatches.end());

    return *this;
}

SubtypingResult& SubtypingResult::withBothComponent(TypePath::Component component)
{
    return withSubComponent(component).withSuperComponent(std::move(component));
}

SubtypingResult& SubtypingResult::withSubComponent(TypePath::Component component)
{
    if (reasoning.empty())
        reasoning.insert(SubtypingReasoning{Path(std::move(component)), TypePath::kEmpty});
    else
    {
        for (auto& r : reasoning)
            r.subPath = r.subPath.push_front(component);
    }

    return *this;
}

SubtypingResult& SubtypingResult::withSuperComponent(TypePath::Component component)
{
    if (reasoning.empty())
        reasoning.insert(SubtypingReasoning{TypePath::kEmpty, Path(std::move(component))});
    else
    {
        for (auto& r : reasoning)
            r.superPath = r.superPath.push_front(component);
    }

    return *this;
}

SubtypingResult& SubtypingResult::withBothPath(TypePath::Path path)
{
    return withSubPath(path).withSuperPath(std::move(path));
}

SubtypingResult& SubtypingResult::withSubPath(TypePath::Path path)
{
    if (reasoning.empty())
        reasoning.insert(SubtypingReasoning{std::move(path), TypePath::kEmpty});
    else
    {
        for (auto& r : reasoning)
            r.subPath = path.append(r.subPath);
    }

    return *this;
}

SubtypingResult& SubtypingResult::withSuperPath(TypePath::Path path)
{
    if (reasoning.empty())
        reasoning.insert(SubtypingReasoning{TypePath::kEmpty, std::move(path)});
    else
    {
        for (auto& r : reasoning)
            r.superPath = path.append(r.superPath);
    }

    return *this;
}

SubtypingResult& SubtypingResult::withErrors(ErrorVec& err)
{
    for (TypeError& e : err)
        errors.emplace_back(e);
    return *this;
}

SubtypingResult& SubtypingResult::withError(TypeError err)
{
    errors.push_back(std::move(err));
    return *this;
}

SubtypingResult& SubtypingResult::withAssumedConstraint(ConstraintV constraint)
{
    assumedConstraints.push_back(std::move(constraint));
    return *this;
}

SubtypingResult SubtypingResult::negate(const SubtypingResult& result)
{
    return SubtypingResult{
        !result.isSubtype,
        result.normalizationTooComplex,
    };
}

struct ApplyMappedGenerics : Substitution
{
    NotNull<BuiltinTypes> builtinTypes;
    NotNull<TypeArena> arena;
    NotNull<InternalErrorReporter> iceReporter;

    NotNull<SubtypingEnvironment> env;

    ApplyMappedGenerics(
        NotNull<BuiltinTypes> builtinTypes,
        NotNull<TypeArena> arena,
        SubtypingEnvironment& env,
        NotNull<InternalErrorReporter> iceReporter
    )
        : Substitution(TxnLog::empty(), arena)
        , builtinTypes(builtinTypes)
        , arena(arena)
        , iceReporter(iceReporter.get())
        , env(NotNull{&env})
    {
    }

    bool isDirty(TypeId ty) override
    {
        return env->containsMappedType(ty);
    }

    bool isDirty(TypePackId tp) override
    {
        return env->containsMappedPack(tp);
    }

    TypeId clean(TypeId ty) override
    {
        const auto& [lowerBound, upperBound] = env->getMappedTypeBounds(ty, NotNull{iceReporter});

        if (upperBound.empty() && lowerBound.empty())
        {
            // No bounds for the generic we're mapping.
            // In this case, unknown vs never is an arbitrary choice:
            // ie, does it matter if we map add<A, A> to add<unknown, unknown> or add<never, never> in the context of subtyping?
            // We choose unknown here, since it's closest to the original behavior.
            return builtinTypes->unknownType;
        }
        else if (!upperBound.empty())
        {
            if (FFlag::LuauSubtypingReplaceBounds)
            {
                IntersectionBuilder ib{arena, builtinTypes};
                for (TypeId ub : upperBound)
                {
                    // NOTE: The original implementation skips over generic
                    // types, but that seems incorrect to me.
                    if (!get<GenericType>(ub))
                        ib.add(ub);
                }
                return ib.build();
            }
            else
            {
                TypeIds boundsToUse;

                for (TypeId ub : upperBound)
                {
                    // quick and dirty check to avoid adding generic types
                    if (!get<GenericType>(ub))
                        boundsToUse.insert(ub);
                }

                if (boundsToUse.empty())
                {
                    // This case happens when we've collected no bounds for the generic we're mapping.
                    // In this case, unknown vs never is an arbitrary choice:
                    // ie, does it matter if we map add<A, A> to add<unknown, unknown> or add<never, never> in the context of subtyping?
                    // We choose unknown here, since it's closest to the original behavior.
                    return builtinTypes->unknownType;
                }
                if (boundsToUse.size() == 1)
                    return *boundsToUse.begin();

                return arena->addType(IntersectionType{boundsToUse.take()});
            }
        }
        else if (!lowerBound.empty())
        {
            if (FFlag::LuauSubtypingReplaceBounds)
            {
                UnionBuilder ub{arena, builtinTypes};
                for (TypeId lb : lowerBound)
                {
                    // NOTE: The original implementation skips over generic
                    // types, but that seems incorrect to me.
                    if (!get<GenericType>(lb))
                        ub.add(lb);
                }
                return ub.build();
            }
            else
            {
                TypeIds boundsToUse;

                for (TypeId lb : lowerBound)
                {
                    // quick and dirty check to avoid adding generic types
                    if (!get<GenericType>(lb))
                        boundsToUse.insert(lb);
                }

                if (boundsToUse.empty())
                {
                    // This case happens when we've collected no bounds for the generic we're mapping.
                    // In this case, unknown vs never is an arbitrary choice:
                    // ie, does it matter if we map add<A, A> to add<unknown, unknown> or add<never, never> in the context of subtyping?
                    // We choose unknown here, since it's closest to the original behavior.
                    return builtinTypes->unknownType;
                }
                else if (lowerBound.size() == 1)
                    return *boundsToUse.begin();
                else
                    return arena->addType(UnionType{boundsToUse.take()});
            }
        }
        else
        {
            LUAU_ASSERT(!"Unreachable path");
            return builtinTypes->unknownType;
        }
    }

    TypePackId clean(TypePackId tp) override
    {
        const MappedGenericEnvironment::LookupResult result = env->lookupGenericPack(tp);
        if (const TypePackId* mappedGen = get_if<TypePackId>(&result))
            return *mappedGen;
        // Clean is only called when isDirty found a pack bound
        LUAU_ASSERT(!"Unreachable");
        return builtinTypes->anyTypePack;
    }

    bool ignoreChildren(TypeId ty) override
    {
        if (get<ExternType>(ty))
            return true;

        if (const FunctionType* f = get<FunctionType>(ty))
        {
            for (TypeId g : f->generics)
            {
                if (FFlag::LuauFollowGenericBeforeCheckingIfMapped)
                    g = follow(g);
                if (const std::vector<SubtypingEnvironment::GenericBounds>* bounds = env->mappedGenerics.find(g); bounds && !bounds->empty())
                    // We don't want to mutate the generics of a function that's being subtyped
                    return true;
            }
        }

        return ty->persistent;
    }
    bool ignoreChildren(TypePackId ty) override
    {
        return ty->persistent;
    }
};

std::optional<TypeId> SubtypingEnvironment::applyMappedGenerics(
    NotNull<BuiltinTypes> builtinTypes,
    NotNull<TypeArena> arena,
    TypeId ty,
    NotNull<InternalErrorReporter> iceReporter
)
{
    ApplyMappedGenerics amg{builtinTypes, arena, *this, iceReporter};
    return amg.substitute(ty);
}

std::optional<TypeId> SubtypingEnvironment::tryFindSubstitution(TypeId ty) const
{
    if (const TypeId* it = substitutions.find(ty))
        return *it;

    if (parent)
        return parent->tryFindSubstitution(ty);

    return std::nullopt;
}

const SubtypingResult* SubtypingEnvironment::tryFindSubtypingResult(std::pair<TypeId, TypeId> subAndSuper) const
{
    if (const auto it = seenSetCache.find(subAndSuper))
        return it;

    if (parent)
        return parent->tryFindSubtypingResult(subAndSuper);

    return nullptr;
}

bool SubtypingEnvironment::containsMappedType(TypeId ty) const
{
    ty = follow(ty);
    if (const auto bounds = mappedGenerics.find(ty); bounds && !bounds->empty())
        return true;

    if (parent)
        return parent->containsMappedType(ty);

    return false;
}

bool SubtypingEnvironment::containsMappedPack(TypePackId tp) const
{
    if (const MappedGenericEnvironment::LookupResult lookupResult = mappedGenericPacks.lookupGenericPack(tp); get_if<TypePackId>(&lookupResult))
        return true;

    if (parent)
        return parent->containsMappedPack(tp);

    return false;
}

SubtypingEnvironment::GenericBounds& SubtypingEnvironment::getMappedTypeBounds(TypeId ty, NotNull<InternalErrorReporter> iceReporter)
{
    ty = follow(ty);
    std::vector<GenericBounds>* bounds = mappedGenerics.find(ty);
    if (bounds && !bounds->empty())
        return bounds->back();

    if (parent)
        return parent->getMappedTypeBounds(ty, iceReporter);

    LUAU_ASSERT(!"Use containsMappedType before asking for bounds!");
    iceReporter->ice("Trying to access bounds for a type with no in-scope bounds");
}

MappedGenericEnvironment::LookupResult SubtypingEnvironment::lookupGenericPack(TypePackId tp) const
{
    MappedGenericEnvironment::LookupResult result = mappedGenericPacks.lookupGenericPack(tp);
    if (get_if<TypePackId>(&result))
        return result;
    else if (parent)
        return parent->lookupGenericPack(tp);
    else
        return result;
}

Subtyping::Subtyping(
    NotNull<BuiltinTypes> builtinTypes,
    NotNull<TypeArena> typeArena,
    NotNull<Normalizer> normalizer,
    NotNull<TypeFunctionRuntime> typeFunctionRuntime,
    NotNull<InternalErrorReporter> iceReporter
)
    : builtinTypes(builtinTypes)
    , arena(typeArena)
    , normalizer(normalizer)
    , typeFunctionRuntime(typeFunctionRuntime)
    , iceReporter(iceReporter)
{
}

SubtypingResult Subtyping::isSubtype(TypeId subTy, TypeId superTy, NotNull<Scope> scope)
{
    SubtypingEnvironment env;

    SubtypingResult result = isCovariantWith(env, subTy, superTy, scope);

    if (result.normalizationTooComplex)
    {
        if (result.isCacheable)
            resultCache[{subTy, superTy}] = result;

        return result;
    }

    for (const auto& [_, bounds] : env.mappedGenerics)
        LUAU_ASSERT(bounds.empty());

    /* TODO: We presently don't store subtype test results in the persistent
     * cache if the left-side type is a generic function.
     *
     * The implementation would be a bit tricky and we haven't seen any material
     * impact on benchmarks.
     *
     * What we would want to do is to remember points within the type where
     * mapped generics are introduced.  When all the contingent generics are
     * introduced at which we're doing the test, we can mark the result as
     * cacheable.
     */

    if (result.isCacheable)
        resultCache[{subTy, superTy}] = result;

    return result;
}

SubtypingResult Subtyping::isSubtype(TypePackId subTp, TypePackId superTp, NotNull<Scope> scope, const std::vector<TypeId>& bindableGenerics)
{
    const std::vector<TypePackId> bindableGenericPacks;
    return isSubtype(subTp, superTp, scope, bindableGenerics, bindableGenericPacks);
}

SubtypingResult Subtyping::isSubtype(
    TypePackId subTp,
    TypePackId superTp,
    NotNull<Scope> scope,
    const std::vector<TypeId>& bindableGenerics,
    const std::vector<TypePackId>& bindableGenericPacks
)
{
    SubtypingEnvironment env;
    for (TypeId g : bindableGenerics)
        env.mappedGenerics[follow(g)] = {SubtypingEnvironment::GenericBounds{}};

    env.mappedGenericPacks.pushFrame(bindableGenericPacks);

    SubtypingResult result = isCovariantWith(env, subTp, superTp, scope);

    for (TypeId bg : bindableGenerics)
    {
        bg = follow(bg);

        LUAU_ASSERT(env.mappedGenerics.contains(bg));

        if (const std::vector<SubtypingEnvironment::GenericBounds>* bounds = env.mappedGenerics.find(bg))
        {
            // Bounds should have exactly one entry
            LUAU_ASSERT(bounds->size() == 1);
            if (bounds->empty())
                continue;
            if (const GenericType* gen = get<GenericType>(bg))
                result.andAlso(checkGenericBounds(bounds->back(), env, scope, gen->name));
        }
    }

    return result;
}

SubtypingResult Subtyping::cache(SubtypingEnvironment& env, SubtypingResult result, TypeId subTy, TypeId superTy)
{
    const std::pair<TypeId, TypeId> p{subTy, superTy};

    if (result.isCacheable)
        resultCache[p] = result;

    return result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, TypeId subTy, TypeId superTy, NotNull<Scope> scope)
{
    NonExceptionalRecursionLimiter nerl(&normalizer->sharedState->counters.recursionCount);
    if (!nerl.isOk(DFInt::LuauSubtypingRecursionLimit))
        return SubtypingResult{false, true};

    if (FFlag::LuauUnifyWithSubtyping2)
    {
        env.iterationCount++;
        if (FInt::LuauSubtypingIterationLimit > 0 && env.iterationCount >= FInt::LuauSubtypingIterationLimit)
            return SubtypingResult{false, true};
    }

    subTy = follow(subTy);
    superTy = follow(superTy);

    if (std::optional<TypeId> subIt = env.tryFindSubstitution(subTy); subIt && *subIt)
        subTy = *subIt;

    if (std::optional<TypeId> superIt = env.tryFindSubstitution(superTy); superIt && *superIt)
        subTy = *superIt;

    const SubtypingResult* cachedResult = resultCache.find({subTy, superTy});
    if (cachedResult)
    {
        return *cachedResult;
    }

    cachedResult = env.tryFindSubtypingResult({subTy, superTy});
    if (cachedResult)
    {
        return *cachedResult;
    }

    // TODO: Do we care about returning a proof that this is error-suppressing?
    // e.g. given `a | error <: a | error` where both operands are pointer equal,
    // then should it also carry the information that it's error-suppressing?
    // If it should, then `error <: error` should also do the same.
    if (subTy == superTy)
        return {true};

    std::pair<TypeId, TypeId> typePair{subTy, superTy};
    if (!seenTypes.insert(typePair))
    {
        /* TODO: Caching results for recursive types is really tricky to think
         * about.
         *
         * We'd like to cache at the outermost level where we encounter the
         * recursive type, but we do not want to cache interior results that
         * involve the cycle.
         *
         * Presently, we stop at cycles and assume that the subtype check will
         * succeed because we'll eventually get there if it won't. However, if
         * that cyclic type turns out not to have the asked-for subtyping
         * relation, then all the intermediate cached results that were
         * contingent on that assumption need to be evicted from the cache, or
         * not entered into the cache, or something.
         *
         * For now, we do the conservative thing and refuse to cache anything
         * that touches a cycle.
         */
        SubtypingResult res;
        res.isSubtype = true;
        res.isCacheable = false;

        env.seenSetCache[typePair] = res;

        return res;
    }

    ScopedSeenSet ssp{seenTypes, typePair};

    // Within the scope to which a generic belongs, that generic should be
    // tested as though it were its upper bounds.  We do not yet support bounded
    // generics, so the upper bound is always unknown.
    if (!FFlag::LuauUnifyWithSubtyping2)
    {
        if (auto subGeneric = get<GenericType>(subTy); subGeneric && subsumes(subGeneric->scope, scope))
            return isCovariantWith(env, builtinTypes->neverType, superTy, scope);
        if (auto superGeneric = get<GenericType>(superTy); superGeneric && subsumes(superGeneric->scope, scope))
            return isCovariantWith(env, subTy, builtinTypes->unknownType, scope);
    }

    SubtypingResult result;

    if (FFlag::LuauUnifyWithSubtyping2 && get2<FreeType, FreeType>(subTy, superTy))
    {
        // Any two free types are potentially subtypes of one another because
        // both of them could be narrowed to never.
        result = {true};
        result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
    }
    else if (auto superFree = get<FreeType>(superTy); FFlag::LuauUnifyWithSubtyping2 && superFree)
    {
        // FIXME CLI-185582: See comment below with the same ticket number.

        // Given SubTy <: (LB <: SuperTy <: UB)
        //
        // If SubTy <: UB, then it is possible that SubTy <: SuperTy.
        // If SubTy </: UB, then it is definitely the case that SubTy </: SuperTy.
        //
        // It's always possible for SuperTy's upper bound to later be
        // constrained, so this relation may not actually hold.

        result = isCovariantWith(env, subTy, superFree->upperBound, scope);

        if (result.isSubtype)
            result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
    }
    else if (auto subFree = get<FreeType>(subTy); FFlag::LuauUnifyWithSubtyping2 && subFree)
    {
        // FIXME CLI-185582: When combined with unification via subtyping, this
        // can allow generics to appear upper bounds, but unless this is used
        // to resolve function calls (which the linked ticket is for) said
        // generics will be from within the scope of said generic, for example:
        //
        //  local function foo<T>(x): T
        //      -- `T` will appear in the upper bound of `x`, but that's
        //      -- fine, as we are within the scope of T
        //      return x
        //  end

        // Given (LB <: SubTy <: UB) <: SuperTy
        //
        // If UB <: SuperTy, then it is certainly the case that SubTy <: SuperTy.
        // If SuperTy <: UB and LB <: SuperTy, then it is possible that UB will later be narrowed such that SubTy <: SuperTy.
        // If LB </: SuperTy, then SubTy </: SuperTy

        if (isCovariantWith(env, subFree->lowerBound, superTy, scope).isSubtype)
        {
            result = {true};
            result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
        }
        else
            result = {false};
    }
    else if (FFlag::LuauUnifyWithSubtyping2 && (is<BlockedType>(subTy) || is<BlockedType>(superTy)))
    {
        result = {true};
        result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
    }
    else if (auto subGeneric = get<GenericType>(subTy); FFlag::LuauUnifyWithSubtyping2 && subGeneric && subsumes(subGeneric->scope, scope))
        return isCovariantWith(env, builtinTypes->neverType, superTy, scope);
    else if (auto superGeneric = get<GenericType>(superTy); FFlag::LuauUnifyWithSubtyping2 && superGeneric && subsumes(superGeneric->scope, scope))
        return isCovariantWith(env, subTy, builtinTypes->unknownType, scope);
    else if (get<AnyType>(superTy))
        result = {true};

    // We have added this as an exception - the set of inhabitants of any is exactly the set of inhabitants of unknown (since error has no
    // inhabitants). any = err | unknown, so under semantic subtyping, {} U unknown = unknown
    else if (get<AnyType>(subTy) && get<UnknownType>(superTy))
        result = {true};
    else if (get<AnyType>(subTy))
    {
        // any = unknown | error, so we rewrite this to match.
        // As per TAPL: A | B <: T iff A <: T && B <: T
        result =
            isCovariantWith(env, builtinTypes->unknownType, superTy, scope).andAlso(isCovariantWith(env, builtinTypes->errorType, superTy, scope));
        if (FFlag::LuauMorePreciseErrorSuppression)
            result.isErrorSuppressing = true;
    }
    else if (get<UnknownType>(superTy) && !get<UnionType>(subTy) && !get<IntersectionType>(subTy))
    {
        LUAU_ASSERT(!get<AnyType>(subTy));          // TODO: replace with ice.
        LUAU_ASSERT(!get<UnionType>(subTy));        // TODO: replace with ice.
        LUAU_ASSERT(!get<IntersectionType>(subTy)); // TODO: replace with ice.

        bool errorSuppressing = nullptr != get<ErrorType>(subTy);
        if (FFlag::LuauMorePreciseErrorSuppression)
        {
            result.isSubtype = !errorSuppressing;
            result.isErrorSuppressing = errorSuppressing;
        }
        else
            result = {!errorSuppressing};
    }
    else if (get<NeverType>(subTy))
        result = {true};
    else if (get<ErrorType>(superTy))
        result = {false};
    else if (get<ErrorType>(subTy))
    {
        result = {true};
        if (FFlag::LuauMorePreciseErrorSuppression)
            result.isErrorSuppressing = true;
    }
    else if (auto subTypeFunctionInstance = get<TypeFunctionInstanceType>(subTy))
    {
        bool mappedGenericsApplied = false;
        if (auto substSubTy = env.applyMappedGenerics(builtinTypes, arena, subTy, iceReporter))
        {
            mappedGenericsApplied = *substSubTy != subTy;
            subTypeFunctionInstance = get<TypeFunctionInstanceType>(*substSubTy);
        }

        result = isCovariantWith(env, subTypeFunctionInstance, superTy, scope);
        result.isCacheable = !mappedGenericsApplied;
    }
    else if (auto superTypeFunctionInstance = get<TypeFunctionInstanceType>(superTy))
    {
        bool mappedGenericsApplied = false;
        if (auto substSuperTy = env.applyMappedGenerics(builtinTypes, arena, superTy, iceReporter))
        {
            mappedGenericsApplied = *substSuperTy != superTy;
            superTypeFunctionInstance = get<TypeFunctionInstanceType>(*substSuperTy);
        }

        result = isCovariantWith(env, subTy, superTypeFunctionInstance, scope);
        result.isCacheable = !mappedGenericsApplied;
    }
    else if (get<GenericType>(subTy) || get<GenericType>(superTy))
    {
        if (const auto subBounds = env.mappedGenerics.find(subTy); subBounds && !subBounds->empty())
        {
            bool ok = bindGeneric(env, subTy, superTy);
            result.isSubtype = ok;
            result.isCacheable = false;
        }
        else if (const auto superBounds = env.mappedGenerics.find(superTy); superBounds && !superBounds->empty())
        {
            bool ok = bindGeneric(env, subTy, superTy);
            result.isSubtype = ok;
            result.isCacheable = false;
        }
    }
    else if (auto subUnion = get<UnionType>(subTy))
        result = isCovariantWith(env, subUnion, superTy, scope);
    else if (auto superUnion = get<UnionType>(superTy))
    {
        result = isCovariantWith(env, subTy, superUnion, scope);
        if (!result.isSubtype && !result.normalizationTooComplex)
            result = trySemanticSubtyping(env, subTy, superTy, scope, result);
    }
    else if (auto superIntersection = get<IntersectionType>(superTy))
        result = isCovariantWith(env, subTy, superIntersection, scope);
    else if (auto subIntersection = get<IntersectionType>(subTy))
    {
        result = isCovariantWith(env, subIntersection, superTy, scope);
        if (!result.isSubtype && !result.normalizationTooComplex)
            result = trySemanticSubtyping(env, subTy, superTy, scope, result);
    }
    else if (auto pair = get2<FreeType, FreeType>(subTy, superTy); !FFlag::LuauUnifyWithSubtyping2 && pair)
    {
        // Any two free types are potentially subtypes of one another because
        // both of them could be narrowed to never.
        result = {true};
        result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
    }
    else if (auto superFree = get<FreeType>(superTy); !FFlag::LuauUnifyWithSubtyping2 && superFree)
    {
        // Given SubTy <: (LB <: SuperTy <: UB)
        //
        // If SubTy <: UB, then it is possible that SubTy <: SuperTy.
        // If SubTy </: UB, then it is definitely the case that SubTy </: SuperTy.
        //
        // It's always possible for SuperTy's upper bound to later be
        // constrained, so this relation may not actually hold.

        result = isCovariantWith(env, subTy, superFree->upperBound, scope);

        if (result.isSubtype)
            result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
    }
    else if (auto subFree = get<FreeType>(subTy); !FFlag::LuauUnifyWithSubtyping2 && subFree)
    {
        // Given (LB <: SubTy <: UB) <: SuperTy
        //
        // If UB <: SuperTy, then it is certainly the case that SubTy <: SuperTy.
        // If SuperTy <: UB and LB <: SuperTy, then it is possible that UB will later be narrowed such that SubTy <: SuperTy.
        // If LB </: SuperTy, then SubTy </: SuperTy

        if (FFlag::LuauMorePreciseErrorSuppression)
        {
            SubtypingResult r = isCovariantWith(env, subFree->lowerBound, superTy, scope);
            result.isSubtype = r.isSubtype;
            result.isErrorSuppressing = r.isErrorSuppressing;
            if (r.isSubtype)
                result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
        }
        else
        {
            if (isCovariantWith(env, subFree->lowerBound, superTy, scope).isSubtype)
            {
                result = {true};
                result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
            }
            else
                result = {false};
        }
    }
    else if (auto p = get2<NegationType, NegationType>(subTy, superTy))
    {
        // We use `isContravariantWith` here in order to make sure that the
        // type paths still look coherent.
        result = isContravariantWith(env, p.first->ty, p.second->ty, scope).withBothComponent(TypePath::TypeField::Negated);
    }
    else if (auto subNegation = get<NegationType>(subTy))
    {
        result = isCovariantWith(env, subNegation, superTy, scope);
        if (!result.isSubtype && !result.normalizationTooComplex)
            result = trySemanticSubtyping(env, subTy, superTy, scope, result);
    }
    else if (auto superNegation = get<NegationType>(superTy))
    {
        result = isCovariantWith(env, subTy, superNegation, scope);
        if (!result.isSubtype && !result.normalizationTooComplex)
            result = trySemanticSubtyping(env, subTy, superTy, scope, result);
    }
    else if (auto p = get2<PrimitiveType, PrimitiveType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<SingletonType, PrimitiveType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<SingletonType, SingletonType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<FunctionType, PrimitiveType>(subTy, superTy))
    {
        auto [subFunction, superPrimitive] = p;
        result.isSubtype = superPrimitive->type == PrimitiveType::Function;
    }
    else if (auto p = get2<FunctionType, FunctionType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<TableType, TableType>(subTy, superTy))
    {
        const bool forceCovariantTest = uniqueTypes != nullptr && uniqueTypes->contains(subTy);
        result = isCovariantWith(env, p.first, p.second, forceCovariantTest, scope);
        if (FFlag::LuauUnifyWithSubtyping2)
        {
            if (result.isSubtype && !p.first->indexer && p.second->indexer && p.first->state != TableState::Sealed)
            {
                // FIXME CLI-182960
                //
                // Currently, unification is also the mechanism by which unsealed
                // tables may receive an indexer. If we've observed that this is
                // already a subtype and this is something of the form:
                //
                //  {| ... |} <: { [A]: B ... }
                //
                // Then add an assumed constraint stating such.
                result.assumedConstraints.emplace_back(SubtypeConstraint{subTy, superTy});
            }
        }
    }
    else if (auto p = get2<MetatableType, MetatableType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<MetatableType, TableType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (FFlag::LuauTableFreezeCheckIsSubtype && get2<MetatableType, PrimitiveType>(subTy, superTy))
    {
        // When FFlag::LuauTableFreezeCheckIsSubtype is clipped, will update the `if` to follow the same pattern of `auto p = get2<...>` as above.
        auto p = get2<MetatableType, PrimitiveType>(subTy, superTy);
        result = isCovariantWith(env, p, scope);
    }
    else if (auto p = get2<ExternType, ExternType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<ExternType, TableType>(subTy, superTy))
        result = isCovariantWith(env, subTy, p.first, superTy, p.second, scope);
    else if (auto p = get2<TableType, PrimitiveType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<PrimitiveType, TableType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);
    else if (auto p = get2<SingletonType, TableType>(subTy, superTy))
        result = isCovariantWith(env, p, scope);

    assertReasoningValid(subTy, superTy, result, builtinTypes, arena);

    return cache(env, std::move(result), subTy, superTy);
}

/*
 * Subtyping of packs is fairly involved. There are three parts to the test.
 *
 * 1. If both packs have types at their heads, we do a pairwise test for each
 *    pair of types.
 * 2. If the finite parts of the packs are of inequal length and the pack on the
 *    opposite side has a tail, we test that. (eg
 *    testing concrete types against variadics or a generic pack)
 * 3. Lastly, do a subtype test on non-finite tails. (eg between two generic
 *    packs or variadics)
 */
SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, TypePackId subTp, TypePackId superTp, NotNull<Scope> scope)
{
    NonExceptionalRecursionLimiter nerl{&normalizer->sharedState->counters.recursionCount};
    if (!nerl.isOk(DFInt::LuauSubtypingRecursionLimit))
        return SubtypingResult{false, true};

    subTp = follow(subTp);
    superTp = follow(superTp);

    std::pair<TypePackId, TypePackId> typePair = {subTp, superTp};
    if (!seenPacks.insert(typePair))
        return SubtypingResult{true, false, false};
    ScopedSeenSet<Subtyping::SeenTypePackSet, std::pair<TypePackId, TypePackId>> popper{seenPacks, std::move(typePair)};

    auto [subHead, subTail] = flatten(subTp);
    auto [superHead, superTail] = flatten(superTp);

    const size_t headSize = std::min(subHead.size(), superHead.size());

    // SubtypingResult is pretty heavy, we keep it as a pointer for stack pressure reasons.
    std::unique_ptr<SubtypingResult> result = std::make_unique<SubtypingResult>();
    result->isSubtype = true;

    if (subTp == superTp)
        return {true};

    // Match head types pairwise

    for (size_t i = 0; i < headSize; ++i)
        result->andAlso(isCovariantWith(env, subHead[i], superHead[i], scope).withBothComponent(TypePath::Index{i, TypePath::Index::Variant::Pack}));

    // Handle mismatched head sizes

    if (subHead.size() < superHead.size())
    {
        if (subTail)
        {
            auto earlyExit = isSubTailCovariantWith(env, *result, subTp, *subTail, superTp, headSize, superHead, superTail, scope);
            if (earlyExit == EarlyExit::Yes)
                return *result;
        }
        else
        {
            result->andAlso({false});
            return *result;
        }
    }
    else if (subHead.size() > superHead.size())
    {
        if (superTail)
        {
            auto earlyExit = isCovariantWithSuperTail(env, *result, subTp, headSize, subHead, subTail, superTp, *superTail, scope);
            if (earlyExit == EarlyExit::Yes)
                return *result;
        }
        else
            return {false};
    }

    // Handle tails

    if (subTail && superTail)
    {
        if (auto p = get2<VariadicTypePack, VariadicTypePack>(*subTail, *superTail))
        {
            result->andAlso(isTailCovariantWithTail(env, scope, *subTail, p.first, *superTail, p.second));
        }
        else if (auto p = get2<GenericTypePack, GenericTypePack>(*subTail, *superTail))
        {
            result->andAlso(isTailCovariantWithTail(env, scope, *subTail, p.first, *superTail, p.second));
        }
        else if (auto p = get2<VariadicTypePack, GenericTypePack>(*subTail, *superTail))
        {
            result->andAlso(isTailCovariantWithTail(env, scope, *subTail, p.first, *superTail, p.second));
        }
        else if (auto p = get2<GenericTypePack, VariadicTypePack>(*subTail, *superTail))
        {
            result->andAlso(isTailCovariantWithTail(env, scope, *subTail, p.first, *superTail, p.second));
        }
        else if (FFlag::LuauUnifyWithSubtyping2 && (is<FreeTypePack>(*subTail) || is<FreeTypePack>(*superTail)))
        {
            result->andAlso(
                SubtypingResult{true}.withBothComponent(TypePath::PackField::Tail).withAssumedConstraint(PackSubtypeConstraint{*subTail, *superTail})
            );
        }
        else if (get<ErrorTypePack>(*subTail) || get<ErrorTypePack>(*superTail))
            // error type is fine on either side
            result->andAlso(SubtypingResult{true}.withBothComponent(TypePath::PackField::Tail));
        else if (get<FreeTypePack>(*subTail) || get<FreeTypePack>(*superTail))
        {
            // This seems incorrect in the event that the heads don't match ...
            return SubtypingResult{true}
                .withBothComponent(TypePath::PackField::Tail)
                .withAssumedConstraint(PackSubtypeConstraint{*subTail, *superTail});
        }
        else
            return SubtypingResult{false}
                .withBothComponent(TypePath::PackField::Tail)
                .withError({scope->location, UnexpectedTypePackInSubtyping{*subTail}})
                .withError({scope->location, UnexpectedTypePackInSubtyping{*superTail}});
    }
    else if (subTail)
    {
        if (get<VariadicTypePack>(*subTail))
        {
            return SubtypingResult{false}.withSubComponent(TypePath::PackField::Tail);
        }
        else if (auto g = get<GenericTypePack>(*subTail))
        {
            return isTailCovariantWithTail(env, scope, *subTail, g, Nothing{});
        }
        else if (FFlag::LuauUnifyWithSubtyping2 && is<FreeTypePack>(*subTail))
        {
            // This is the case where:
            // 1. Both the `superTp` and `subTp` have the same number of types in the head
            // 2. `superTp` does not have a tail (as if it did we'd hit a different branch)
            // 3. `subTp` has a free tail
            // We can treat the lack of a tail as the empty type pack.
            return SubtypingResult{true}
                .withBothComponent(TypePath::PackField::Tail)
                .withAssumedConstraint(PackSubtypeConstraint{*subTail, builtinTypes->emptyTypePack});
        }
        else
            return SubtypingResult{false}
                .withSubComponent(TypePath::PackField::Tail)
                .withError({scope->location, UnexpectedTypePackInSubtyping{*subTail}});
    }
    else if (superTail)
    {
        if (get<VariadicTypePack>(*superTail))
        {
            /*
             * A variadic type pack ...T can be thought of as an infinite union of finite type packs.
             *     () | (T) | (T, T) | (T, T, T) | ...
             *
             * And, per TAPL:
             *     T <: A | B iff T <: A or T <: B
             *
             * All variadic type packs are therefore supertypes of the empty type pack.
             */
        }
        else if (auto g = get<GenericTypePack>(*superTail))
        {
            result->andAlso(isTailCovariantWithTail(env, scope, Nothing{}, *superTail, g));
        }
        else if (FFlag::LuauUnifyWithSubtyping2 && is<FreeTypePack>(*superTail))
        {
            // This is the case where:
            // 1. Both the `superTp` and `subTp` have the same number of types in the head
            // 2. `subTp` does not have a tail
            // 3. `superTp` has a free tail
            result->andAlso(
                SubtypingResult{true}
                    .withBothComponent(TypePath::PackField::Tail)
                    .withAssumedConstraint(PackSubtypeConstraint{builtinTypes->emptyTypePack, *superTail})
            );
        }
        else
            return SubtypingResult{false}
                .withSuperComponent(TypePath::PackField::Tail)
                .withError({scope->location, UnexpectedTypePackInSubtyping{*superTail}});
    }

    assertReasoningValid(subTp, superTp, *result, builtinTypes, arena);

    return *result;
}

/* Check the tail of the subtype pack against a slice of the finite part of the
 * pack in supertype position. For example, in the following type, the head of
 * the pack in supertype position is longer than that of the subtype head:
 *
 *     (number, string, any...) <: (number, string, boolean, thread, any...),
 *
 * This function handles the mismatched heads: any... <: (boolean, thread)
 *
 * Notably, this function does _not_ handle the test between the actual tail
 * packs.
 *
 * The contract on this function is a bit strange. If the function returns a
 * SubtypingResult, it should be considered to be the result for the entire pack
 * subtyping relation.  It is not necessary to further check the tails.
 */
Subtyping::EarlyExit Subtyping::isSubTailCovariantWith(
    SubtypingEnvironment& env,
    SubtypingResult& outputResult,
    TypePackId subTp,
    TypePackId subTail,
    TypePackId superTp,
    size_t superHeadStartIndex,
    const std::vector<TypeId>& superHead,
    std::optional<TypePackId> superTail,
    NotNull<Scope> scope
)
{
    if (auto vt = get<VariadicTypePack>(subTail))
    {
        for (size_t i = superHeadStartIndex; i < superHead.size(); ++i)
            outputResult.andAlso(isCovariantWith(env, vt->ty, superHead[i], scope)
                                     .withSubPath(TypePath::PathBuilder().tail().variadic().build())
                                     .withSuperComponent(TypePath::Index{i, TypePath::Index::Variant::Pack}));
        return EarlyExit::No;
    }
    else if (get<GenericTypePack>(subTail))
    {
        MappedGenericEnvironment::LookupResult lookupResult = env.lookupGenericPack(subTail);
        SubtypingResult result;
        if (get_if<MappedGenericEnvironment::NotBindable>(&lookupResult))
            result = SubtypingResult{false, /* normalizationTooComplex */ false, /* isCacheable */ false}
                         .withSubComponent(TypePath::PackField::Tail)
                         .withSuperComponent(TypePath::PackSlice{superHeadStartIndex});
        else
        {
            TypePackId superTailPack = sliceTypePack(superHeadStartIndex, superTp, superHead, superTail, builtinTypes, arena);

            if (const TypePackId* mappedGen = get_if<TypePackId>(&lookupResult))
            {
                // Subtype against the mapped generic pack.
                TypePackId subTpToCompare = *mappedGen;

                // If mappedGen has a hidden variadic tail, we clip it for better arity mismatch reporting.
                const TypePack* tp = get<TypePack>(*mappedGen);
                if (const VariadicTypePack* vtp = tp ? get<VariadicTypePack>(follow(tp->tail)) : nullptr; vtp && vtp->hidden)
                    subTpToCompare = arena->addTypePack(tp->head);

                result = isCovariantWith(env, subTpToCompare, superTailPack, scope)
                             .withSubPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*mappedGen}}))
                             .withSuperComponent(TypePath::PackSlice{superHeadStartIndex});
            }
            else
            {
                LUAU_ASSERT(get_if<MappedGenericEnvironment::Unmapped>(&lookupResult));
                bool ok = env.mappedGenericPacks.bindGeneric(subTail, superTailPack);
                result = SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}
                             .withSubComponent(TypePath::PackField::Tail)
                             .withSuperComponent(TypePath::PackSlice{superHeadStartIndex});
            }
        }

        outputResult.andAlso(result);
        return EarlyExit::Yes;
    }
    else if (get<ErrorTypePack>(subTail))
    {
        outputResult = SubtypingResult{true}.withSubComponent(TypePath::PackField::Tail);
        return EarlyExit::Yes;
    }
    else if (FFlag::LuauUnifyWithSubtyping2 && get<FreeTypePack>(subTail))
    {
        TypePackId superTailPack = sliceTypePack(superHeadStartIndex, superTp, superHead, superTail, builtinTypes, arena);
        outputResult.andAlso(
            SubtypingResult{true}.withSubComponent(TypePath::PackField::Tail).withAssumedConstraint(PackSubtypeConstraint{subTail, superTailPack})
        );
        return EarlyExit::Yes;
    }
    else
    {
        outputResult =
            SubtypingResult{false}.withSubComponent(TypePath::PackField::Tail).withError({scope->location, UnexpectedTypePackInSubtyping{subTail}});
        return EarlyExit::Yes;
    }
}

Subtyping::EarlyExit Subtyping::isCovariantWithSuperTail(
    SubtypingEnvironment& env,
    SubtypingResult& outputResult,
    TypePackId subTp,
    size_t subHeadStartIndex,
    const std::vector<TypeId>& subHead,
    std::optional<TypePackId> subTail,
    TypePackId superTp,
    TypePackId superTail,
    NotNull<Scope> scope
)
{
    if (auto vt = get<VariadicTypePack>(superTail))
    {
        for (size_t i = subHeadStartIndex; i < subHead.size(); ++i)
            outputResult.andAlso(isCovariantWith(env, subHead[i], vt->ty, scope)
                                     .withSubComponent(TypePath::Index{i, TypePath::Index::Variant::Pack})
                                     .withSuperPath(TypePath::PathBuilder().tail().variadic().build()));
        return EarlyExit::No;
    }
    else if (get<GenericTypePack>(superTail))
    {
        MappedGenericEnvironment::LookupResult lookupResult = env.lookupGenericPack(superTail);
        SubtypingResult result;
        if (get_if<MappedGenericEnvironment::NotBindable>(&lookupResult))
            result = SubtypingResult{false, /* normalizationTooComplex */ false, /* isCacheable */ false}
                         .withSubComponent(TypePath::PackSlice{subHeadStartIndex})
                         .withSuperComponent(TypePath::PackField::Tail);
        else
        {
            TypePackId subTailPack = sliceTypePack(subHeadStartIndex, subTp, subHead, subTail, builtinTypes, arena);

            if (const TypePackId* mappedGen = get_if<TypePackId>(&lookupResult))
            {
                TypePackId superTpToCompare = *mappedGen;

                // Subtype against the mapped generic pack.
                const TypePack* tp = get<TypePack>(*mappedGen);
                if (const VariadicTypePack* vtp = tp ? get<VariadicTypePack>(follow(tp->tail)) : nullptr; vtp && vtp->hidden)
                    superTpToCompare = arena->addTypePack(tp->head);

                result = isCovariantWith(env, subTailPack, superTpToCompare, scope)
                             .withSubComponent(TypePath::PackSlice{subHeadStartIndex})
                             .withSuperPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*mappedGen}}));
            }
            else
            {
                LUAU_ASSERT(get_if<MappedGenericEnvironment::Unmapped>(&lookupResult));
                bool ok = env.mappedGenericPacks.bindGeneric(superTail, subTailPack);
                result = SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}
                             .withSubComponent(TypePath::PackSlice{subHeadStartIndex})
                             .withSuperComponent(TypePath::PackField::Tail);
            }
        }

        outputResult.andAlso(result);
        return EarlyExit::Yes;
    }
    else if (get<ErrorTypePack>(superTail))
    {
        outputResult = SubtypingResult{true}.withSuperComponent(TypePath::PackField::Tail);
        return EarlyExit::Yes;
    }
    else if (FFlag::LuauUnifyWithSubtyping2 && is<FreeTypePack>(superTail))
    {
        TypePackId subTailPack = sliceTypePack(subHeadStartIndex, subTp, subHead, subTail, builtinTypes, arena);
        outputResult.andAlso(
            SubtypingResult{true}.withSuperComponent(TypePath::PackField::Tail).withAssumedConstraint({PackSubtypeConstraint{subTailPack, superTail}})
        );
        return EarlyExit::Yes;
    }
    else
    {
        outputResult = SubtypingResult{false}
                           .withSuperComponent(TypePath::PackField::Tail)
                           .withError({scope->location, UnexpectedTypePackInSubtyping{superTail}});
        return EarlyExit::Yes;
    }
}

SubtypingResult Subtyping::isTailCovariantWithTail(
    SubtypingEnvironment& env,
    NotNull<Scope> scope,
    TypePackId subTp,
    const VariadicTypePack* sub,
    TypePackId superTp,
    const VariadicTypePack* super
)
{
    // A variadic type pack is a subtype of another variadic type pack if their
    // respective element types have the same subtyping relationship.
    return isCovariantWith(env, sub->ty, super->ty, scope)
        .withBothComponent(TypePath::TypeField::Variadic)
        .withBothComponent(TypePath::PackField::Tail);
}

SubtypingResult Subtyping::isTailCovariantWithTail(
    SubtypingEnvironment& env,
    NotNull<Scope> scope,
    TypePackId subTp,
    const GenericTypePack* sub,
    TypePackId superTp,
    const GenericTypePack* super
)
{
    MappedGenericEnvironment::LookupResult subLookupResult = env.lookupGenericPack(subTp);
    MappedGenericEnvironment::LookupResult superLookupResult = env.lookupGenericPack(superTp);

    // match (subLookup, superLookupResult) {
    //     (TypePackId, _) => do covariant test
    //     (Unmapped, _) => bind the generic
    //     (_, TypePackId) => do covariant test
    //     (_, Unmapped) => bind the generic
    //     (_, _) => subtyping succeeds if the two generics are pointer-identical
    // }
    if (const TypePackId* currMapping = get_if<TypePackId>(&subLookupResult))
    {
        return isCovariantWith(env, *currMapping, superTp, scope)
            .withSubPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*currMapping}}))
            .withSuperComponent(TypePath::PackField::Tail);
    }
    else if (get_if<MappedGenericEnvironment::Unmapped>(&subLookupResult))
    {
        bool ok = env.mappedGenericPacks.bindGeneric(subTp, superTp);
        return SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}.withBothComponent(TypePath::PackField::Tail);
    }
    else if (const TypePackId* currMapping = get_if<TypePackId>(&superLookupResult))
    {
        return isCovariantWith(env, subTp, *currMapping, scope)
            .withSubComponent(TypePath::PackField::Tail)
            .withSuperPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*currMapping}}));
    }
    else if (get_if<MappedGenericEnvironment::Unmapped>(&superLookupResult))
    {
        bool ok = env.mappedGenericPacks.bindGeneric(superTp, subTp);
        return SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}.withBothComponent(TypePath::PackField::Tail);
    }
    else
    {
        // Sometimes, we compare generic packs inside the functions which are quantifying them. They're not bindable, but should still
        // subtype against themselves.
        return SubtypingResult{subTp == superTp, /* normalizationTooComplex */ false, /* isCacheable */ false}.withBothComponent(
            TypePath::PackField::Tail
        );
    }
}

SubtypingResult Subtyping::isTailCovariantWithTail(
    SubtypingEnvironment& env,
    NotNull<Scope> scope,
    TypePackId subTp,
    const VariadicTypePack* sub,
    TypePackId superTp,
    const GenericTypePack* super
)
{
    MappedGenericEnvironment::LookupResult lookupResult = env.lookupGenericPack(superTp);
    if (const TypePackId* currMapping = get_if<TypePackId>(&lookupResult))
    {
        return isCovariantWith(env, subTp, *currMapping, scope)
            .withSubComponent(TypePath::PackField::Tail)
            .withSuperPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*currMapping}}));
    }
    else if (get_if<MappedGenericEnvironment::Unmapped>(&lookupResult))
    {
        bool ok = env.mappedGenericPacks.bindGeneric(superTp, subTp);
        return SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}.withBothComponent(TypePath::PackField::Tail);
    }
    else
    {
        LUAU_ASSERT(get_if<MappedGenericEnvironment::NotBindable>(&lookupResult));
        return SubtypingResult{false, /* normalizationTooComplex */ false, /* isCacheable */ false}.withBothComponent(TypePath::PackField::Tail);
    }
}

SubtypingResult Subtyping::isTailCovariantWithTail(
    SubtypingEnvironment& env,
    NotNull<Scope> scope,
    TypePackId subTp,
    const GenericTypePack* sub,
    TypePackId superTp,
    const VariadicTypePack* super
)
{
    if (TypeId t = follow(super->ty); get<AnyType>(t) || get<UnknownType>(t))
    {
        // Extra magic rule:
        // T... <: ...any
        // T... <: ...unknown
        //
        // See https://github.com/luau-lang/luau/issues/767
        return SubtypingResult{true};
    }
    else
    {
        MappedGenericEnvironment::LookupResult lookupResult = env.lookupGenericPack(subTp);
        if (const TypePackId* currMapping = get_if<TypePackId>(&lookupResult))
        {
            return isCovariantWith(env, *currMapping, superTp, scope)
                .withSubPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*currMapping}}))
                .withSuperComponent(TypePath::PackField::Tail);
        }
        else if (get_if<MappedGenericEnvironment::Unmapped>(&lookupResult))
        {
            bool ok = env.mappedGenericPacks.bindGeneric(subTp, superTp);
            return SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}.withBothComponent(TypePath::PackField::Tail);
        }
        else
        {
            LUAU_ASSERT(get_if<MappedGenericEnvironment::NotBindable>(&lookupResult));
            return SubtypingResult{false, /* normalizationTooComplex */ false, /* isCacheable */ false}.withBothComponent(TypePath::PackField::Tail);
        }
    }
}

SubtypingResult Subtyping::isTailCovariantWithTail(
    SubtypingEnvironment& env,
    NotNull<Scope> scope,
    TypePackId subTp,
    const GenericTypePack* sub,
    Nothing
)
{
    MappedGenericEnvironment::LookupResult lookupResult = env.lookupGenericPack(subTp);
    if (const TypePackId* currMapping = get_if<TypePackId>(&lookupResult))
        return isCovariantWith(env, *currMapping, builtinTypes->emptyTypePack, scope)
            .withSubPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*currMapping}}));
    else if (get_if<MappedGenericEnvironment::Unmapped>(&lookupResult))
    {
        bool ok = env.mappedGenericPacks.bindGeneric(subTp, builtinTypes->emptyTypePack);
        return SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}.withSubComponent(TypePath::PackField::Tail);
    }
    else
    {
        LUAU_ASSERT(get_if<MappedGenericEnvironment::NotBindable>(&lookupResult));
        return SubtypingResult{false, /* normalizationTooComplex */ false, /* isCacheable */ false}.withSubComponent(TypePath::PackField::Tail);
    }
}

SubtypingResult Subtyping::isTailCovariantWithTail(
    SubtypingEnvironment& env,
    NotNull<Scope> scope,
    Nothing,
    TypePackId superTp,
    const GenericTypePack* super
)
{
    MappedGenericEnvironment::LookupResult lookupResult = env.lookupGenericPack(superTp);
    if (const TypePackId* currMapping = get_if<TypePackId>(&lookupResult))
        return isCovariantWith(env, builtinTypes->emptyTypePack, *currMapping, scope)
            .withSuperPath(Path({TypePath::PackField::Tail, TypePath::GenericPackMapping{*currMapping}}));
    else if (get_if<MappedGenericEnvironment::Unmapped>(&lookupResult))
    {
        bool ok = env.mappedGenericPacks.bindGeneric(superTp, builtinTypes->emptyTypePack);
        return SubtypingResult{ok, /* normalizationTooComplex */ false, /* isCacheable */ false}.withSuperComponent(TypePath::PackField::Tail);
    }
    else
    {
        LUAU_ASSERT(get_if<MappedGenericEnvironment::NotBindable>(&lookupResult));
        return SubtypingResult{false, /* normalizationTooComplex */ false, /* isCacheable */ false}.withSuperComponent(TypePath::PackField::Tail);
    }
}


template<typename SubTy, typename SuperTy>
SubtypingResult Subtyping::isContravariantWith(SubtypingEnvironment& env, SubTy subTy, SuperTy superTy, NotNull<Scope> scope)
{
    SubtypingResult result = isCovariantWith(env, superTy, subTy, scope);
    if (result.reasoning.empty())
        result.reasoning.insert(SubtypingReasoning{TypePath::kEmpty, TypePath::kEmpty, SubtypingVariance::Contravariant});
    else
    {
        // If we don't swap the paths here, we will end up producing an invalid path
        // whenever we involve contravariance. We'll end up appending path
        // components that should belong to the supertype to the subtype, and vice
        // versa.
        for (auto& reasoning : result.reasoning)
        {
            std::swap(reasoning.subPath, reasoning.superPath);

            // Also swap covariant/contravariant, since those are also the other way
            // around.
            if (reasoning.variance == SubtypingVariance::Covariant)
                reasoning.variance = SubtypingVariance::Contravariant;
            else if (reasoning.variance == SubtypingVariance::Contravariant)
                reasoning.variance = SubtypingVariance::Covariant;
        }
    }

    assertReasoningValid(subTy, superTy, result, builtinTypes, arena);

    return result;
}

template<typename SubTy, typename SuperTy>
SubtypingResult Subtyping::isInvariantWith(SubtypingEnvironment& env, SubTy subTy, SuperTy superTy, NotNull<Scope> scope)
{
    SubtypingResult result = isCovariantWith(env, subTy, superTy, scope);
    result.andAlso(isContravariantWith(env, subTy, superTy, scope));

    if (result.reasoning.empty())
        result.reasoning.insert(SubtypingReasoning{TypePath::kEmpty, TypePath::kEmpty, SubtypingVariance::Invariant});
    else
    {
        for (auto& reasoning : result.reasoning)
            reasoning.variance = SubtypingVariance::Invariant;
    }

    assertReasoningValid(subTy, superTy, result, builtinTypes, arena);

    return result;
}

template<typename SubTy, typename SuperTy>
SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const TryPair<const SubTy*, const SuperTy*>& pair, NotNull<Scope> scope)
{
    return isCovariantWith(env, pair.first, pair.second, scope);
}

template<typename SubTy, typename SuperTy>
SubtypingResult Subtyping::isContravariantWith(SubtypingEnvironment& env, const TryPair<const SubTy*, const SuperTy*>& pair, NotNull<Scope> scope)
{
    return isContravariantWith(env, pair.first, pair.second, scope);
}

template<typename SubTy, typename SuperTy>
SubtypingResult Subtyping::isInvariantWith(SubtypingEnvironment& env, const TryPair<const SubTy*, const SuperTy*>& pair, NotNull<Scope> scope)
{
    return isInvariantWith(env, pair.first, pair.second);
}

/*
 * This is much simpler than the Unifier implementation because we don't
 * actually care about potential "cross-talk" between union parts that match the
 * left side.
 *
 * In fact, we're very limited in what we can do: If multiple choices match, but
 * all of them have non-overlapping constraints, then we're stuck with an "or"
 * conjunction of constraints.  Solving this in the general case is quite
 * difficult.
 *
 * For example, we cannot dispatch anything from this constraint:
 *
 * {x: number, y: string} <: {x: number, y: 'a} | {x: 'b, y: string}
 *
 * From this constraint, we can know that either string <: 'a or number <: 'b,
 * but we don't know which!
 *
 * However:
 *
 * {x: number, y: string} <: {x: number, y: 'a} | {x: number, y: string}
 *
 * We can dispatch this constraint because there is no 'or' conjunction.  One of
 * the arms requires 0 matches.
 *
 * {x: number, y: string, z: boolean} | {x: number, y: 'a, z: 'b} | {x: number,
 * y: string, z: 'b}
 *
 * Here, we have two matches.  One asks for string ~ 'a and boolean ~ 'b.  The
 * other just asks for boolean ~ 'b. We can dispatch this and only commit
 * boolean ~ 'b.  This constraint does not teach us anything about 'a.
 */
SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, TypeId subTy, const UnionType* superUnion, NotNull<Scope> scope)
{
    // As per TAPL: T <: A | B iff T <: A || T <: B

    SubtypingResult result{false};

    size_t index = 0;
    for (TypeId ty : superUnion)
    {
        SubtypingResult next = isCovariantWith(env, subTy, ty, scope);

        if (next.normalizationTooComplex)
            return SubtypingResult{false, /* normalizationTooComplex */ true};

        if (next.isSubtype)
            return FFlag::LuauUnifyWithSubtyping2 ? next : SubtypingResult{true};

        if (FFlag::LuauMorePreciseErrorSuppression)
        {
            result.andAlso(next.withSuperComponent(TypePath::Index{index, TypePath::Index::Variant::Union}));
            ++index;
        }
    }

    return result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const UnionType* subUnion, TypeId superTy, NotNull<Scope> scope)
{
    // As per TAPL: A | B <: T iff A <: T && B <: T
    // Keep in the heap for stack pressure reasons.
    std::unique_ptr<SubtypingResult> result = std::make_unique<SubtypingResult>();
    result->isSubtype = true;
    size_t i = 0;
    for (TypeId ty : subUnion)
    {
        result->andAlso(isCovariantWith(env, ty, superTy, scope).withSubComponent(TypePath::Index{i++, TypePath::Index::Variant::Union}));

        if (result->normalizationTooComplex)
            return SubtypingResult{false, /* normalizationTooComplex */ true};
    }

    return *result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, TypeId subTy, const IntersectionType* superIntersection, NotNull<Scope> scope)
{
    // As per TAPL: T <: A & B iff T <: A && T <: B
    std::unique_ptr<SubtypingResult> result = std::make_unique<SubtypingResult>();
    result->isSubtype = true;
    size_t i = 0;
    for (TypeId ty : superIntersection)
    {
        result->andAlso(isCovariantWith(env, subTy, ty, scope).withSuperComponent(TypePath::Index{i++, TypePath::Index::Variant::Intersection}));

        if (result->normalizationTooComplex)
            return SubtypingResult{false, /* normalizationTooComplex */ true};
    }

    return *result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const IntersectionType* subIntersection, TypeId superTy, NotNull<Scope> scope)
{
    // As per TAPL: A & B <: T iff A <: T || B <: T
    std::unique_ptr<SubtypingResult> result = std::make_unique<SubtypingResult>();
    result->isSubtype = false;
    size_t i = 0;
    for (TypeId ty : subIntersection)
    {
        result->orElse(isCovariantWith(env, ty, superTy, scope).withSubComponent(TypePath::Index{i++, TypePath::Index::Variant::Intersection}));

        if (result->normalizationTooComplex)
            return SubtypingResult{false, /* normalizationTooComplex */ true};
    }

    return *result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const NegationType* subNegation, TypeId superTy, NotNull<Scope> scope)
{
    TypeId negatedTy = follow(subNegation->ty);

    SubtypingResult result;

    // In order to follow a consistent codepath, rather than folding the
    // isCovariantWith test down to its conclusion here, we test the subtyping test
    // of the result of negating the type for never, unknown, any, and error.
    if (is<NeverType>(negatedTy))
    {
        // ¬never ~ unknown
        result = isCovariantWith(env, builtinTypes->unknownType, superTy, scope).withSubComponent(TypePath::TypeField::Negated);
    }
    else if (is<UnknownType>(negatedTy))
    {
        // ¬unknown ~ never
        result = isCovariantWith(env, builtinTypes->neverType, superTy, scope).withSubComponent(TypePath::TypeField::Negated);
    }
    else if (is<AnyType>(negatedTy))
    {
        // ¬any ~ any
        result = isCovariantWith(env, negatedTy, superTy, scope).withSubComponent(TypePath::TypeField::Negated);
    }
    else if (auto u = get<UnionType>(negatedTy))
    {
        // ¬(A ∪ B) ~ ¬A ∩ ¬B
        // follow intersection rules: A & B <: T iff A <: T && B <: T
        result = {true};

        for (TypeId ty : u)
        {
            if (auto negatedPart = get<NegationType>(follow(ty)))
                result.andAlso(isCovariantWith(env, negatedPart->ty, superTy, scope).withSubComponent(TypePath::TypeField::Negated));
            else
            {
                NegationType negatedTmp{ty};
                result.andAlso(isCovariantWith(env, &negatedTmp, superTy, scope));
            }
        }
    }
    else if (auto i = get<IntersectionType>(negatedTy))
    {
        // ¬(A ∩ B) ~ ¬A ∪ ¬B
        // follow union rules: A | B <: T iff A <: T || B <: T
        result = {false};

        for (TypeId ty : i)
        {
            if (auto negatedPart = get<NegationType>(follow(ty)))
                result.orElse(isCovariantWith(env, negatedPart->ty, superTy, scope).withSubComponent(TypePath::TypeField::Negated));
            else
            {
                NegationType negatedTmp{ty};
                result.orElse(isCovariantWith(env, &negatedTmp, superTy, scope));
            }
        }
    }
    else if (is<ErrorType, FunctionType, TableType, MetatableType>(negatedTy))
    {
        iceReporter->ice("attempting to negate a non-testable type");
    }
    // negating a different subtype will get you a very wide type that's not a
    // subtype of other stuff.
    else
    {
        result = SubtypingResult{false}.withSubComponent(TypePath::TypeField::Negated);
    }

    return result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const TypeId subTy, const NegationType* superNegation, NotNull<Scope> scope)
{
    TypeId negatedTy = follow(superNegation->ty);

    SubtypingResult result;

    if (is<NeverType>(negatedTy))
    {
        // ¬never ~ unknown
        result = isCovariantWith(env, subTy, builtinTypes->unknownType, scope);
    }
    else if (is<UnknownType>(negatedTy))
    {
        // ¬unknown ~ never
        result = isCovariantWith(env, subTy, builtinTypes->neverType, scope);
    }
    else if (is<AnyType>(negatedTy))
    {
        // ¬any ~ any
        result = FFlag::LuauUnifyWithSubtyping2 ? isCovariantWith(env, subTy, negatedTy, scope) : isSubtype(subTy, negatedTy, scope);
    }
    else if (auto u = get<UnionType>(negatedTy))
    {
        // ¬(A ∪ B) ~ ¬A ∩ ¬B
        // follow intersection rules: A & B <: T iff A <: T && B <: T
        std::vector<SubtypingResult> subtypings;
        result = {true};

        for (TypeId ty : u)
        {
            if (auto negatedPart = get<NegationType>(follow(ty)))
                result.andAlso(isCovariantWith(env, subTy, negatedPart->ty, scope));
            else
            {
                NegationType negatedTmp{ty};
                result.andAlso(isCovariantWith(env, subTy, &negatedTmp, scope));
            }
        }
    }
    else if (auto i = get<IntersectionType>(negatedTy))
    {
        // ¬(A ∩ B) ~ ¬A ∪ ¬B
        // follow union rules: A | B <: T iff A <: T || B <: T
        result = {false};

        for (TypeId ty : i)
        {
            if (auto negatedPart = get<NegationType>(follow(ty)))
                result.orElse(isCovariantWith(env, subTy, negatedPart->ty, scope));
            else
            {
                NegationType negatedTmp{ty};
                result.orElse(isCovariantWith(env, subTy, &negatedTmp, scope));
            }
        }

    }
    else if (auto p = get2<PrimitiveType, PrimitiveType>(subTy, negatedTy))
    {
        // number <: ¬boolean
        // number </: ¬number
        result = {p.first->type != p.second->type};
    }
    else if (auto p = get2<SingletonType, PrimitiveType>(subTy, negatedTy))
    {
        // "foo" </: ¬string
        if (get<StringSingleton>(p.first) && p.second->type == PrimitiveType::String)
            result = {false};
        // false </: ¬boolean
        else if (get<BooleanSingleton>(p.first) && p.second->type == PrimitiveType::Boolean)
            result = {false};
        // other cases are true
        else
            result = {true};
    }
    else if (auto p = get2<PrimitiveType, SingletonType>(subTy, negatedTy))
    {
        if (p.first->type == PrimitiveType::String && get<StringSingleton>(p.second))
            result = {false};
        else if (p.first->type == PrimitiveType::Boolean && get<BooleanSingleton>(p.second))
            result = {false};
        else
            result = {true};
    }
    // the top class type is not actually a primitive type, so the negation of
    // any one of them includes the top class type.
    else if (auto p = get2<ExternType, PrimitiveType>(subTy, negatedTy))
        result = {true};
    else if (auto p = get<PrimitiveType>(negatedTy); p && is<TableType, MetatableType>(subTy))
        result = {p->type != PrimitiveType::Table};
    else if (auto p = get2<FunctionType, PrimitiveType>(subTy, negatedTy))
        result = {p.second->type != PrimitiveType::Function};
    else if (auto p = get2<SingletonType, SingletonType>(subTy, negatedTy))
        result = {*p.first != *p.second};
    else if (auto p = get2<ExternType, ExternType>(subTy, negatedTy))
        result = SubtypingResult::negate(isCovariantWith(env, p.first, p.second, scope));
    else if (get2<FunctionType, ExternType>(subTy, negatedTy))
        result = {true};
    else if (is<ErrorType, FunctionType, TableType, MetatableType>(negatedTy))
        iceReporter->ice("attempting to negate a non-testable type");
    else
        result = {false};

    return result.withSuperComponent(TypePath::TypeField::Negated);
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const PrimitiveType* subPrim,
    const PrimitiveType* superPrim,
    NotNull<Scope> scope
)
{
    return {subPrim->type == superPrim->type};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const SingletonType* subSingleton,
    const PrimitiveType* superPrim,
    NotNull<Scope> scope
)
{
    if (get<StringSingleton>(subSingleton) && superPrim->type == PrimitiveType::String)
        return {true};
    else if (get<BooleanSingleton>(subSingleton) && superPrim->type == PrimitiveType::Boolean)
        return {true};
    else
        return {false};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const SingletonType* subSingleton,
    const SingletonType* superSingleton,
    NotNull<Scope> scope
)
{
    return {*subSingleton == *superSingleton};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const TableType* subTable,
    const TableType* superTable,
    bool forceCovariantTest,
    NotNull<Scope> scope
)
{
    SubtypingResult result{true};

    if (subTable->props.empty() && !subTable->indexer && subTable->state == TableState::Sealed && superTable->indexer)
    {
        // While it is certainly the case that {} </: {T}, the story is a little bit different for {| |} <: {T}
        // The shape of an unsealed table is still in flux, so it is probably the case that the unsealed table
        // will later gain the necessary indexer as type inference proceeds.
        //
        // Unsealed tables are always sealed by the time inference completes, so this should never affect the
        // type checking phase.
        return {false};
    }

    for (const auto& [name, superProp] : superTable->props)
    {
        std::vector<SubtypingResult> results;
        if (auto subIter = subTable->props.find(name); subIter != subTable->props.end())
            results.push_back(isCovariantWith(env, subIter->second, superProp, name, forceCovariantTest, scope));
        else if (subTable->indexer)
        {
            if (isCovariantWith(env, builtinTypes->stringType, subTable->indexer->indexType, scope).isSubtype)
            {
                if (superProp.isShared())
                {
                    results.push_back(isInvariantWith(env, subTable->indexer->indexResultType, *superProp.readTy, scope)
                                          .withSubComponent(TypePath::TypeField::IndexResult)
                                          .withSuperComponent(TypePath::Property::read(name)));
                }
                else
                {
                    if (superProp.readTy)
                        results.push_back(isCovariantWith(env, subTable->indexer->indexResultType, *superProp.readTy, scope)
                                              .withSubComponent(TypePath::TypeField::IndexResult)
                                              .withSuperComponent(TypePath::Property::read(name)));
                    if (superProp.writeTy)
                        results.push_back(isContravariantWith(env, subTable->indexer->indexResultType, *superProp.writeTy, scope)
                                              .withSubComponent(TypePath::TypeField::IndexResult)
                                              .withSuperComponent(TypePath::Property::write(name)));
                }
            }
        }
        else if (FFlag::LuauSubtypingMissingPropertiesAsNil)
        {
            SubtypingResult result = isCovariantWith(env, Property::readonly(builtinTypes->nilType), superProp, name, forceCovariantTest, scope);
            // We must ignore the actual reasoning from here because the subtype doesn't have a property to traverse into later.
            // If there is a type error, we want to point at this spot as being responsible for it!
            result.reasoning.clear();
            results.push_back(result);
        }

        if (results.empty())
            return SubtypingResult{false};

        if (FFlag::LuauMorePreciseErrorSuppression)
        {
            bool isSubtype = true;
            for (const SubtypingResult& sr : results)
                isSubtype &= sr.isSubtype;

            // If the first failed subtype test is a suppressing failure, then
            // we set the suppression bit in case there are no subsequent
            // non-suppressing failures.
            //
            // If we at any point encounter a non-suppressing failure, then this
            // whole subtype test is a non-suppressing failure.
            if (result.isSubtype && !isSubtype)
            {
                for (const SubtypingResult& sr : results)
                    result.andAlso(sr, SubtypingSuppressionPolicy::Any);
            }
            else
            {
                for (const SubtypingResult& sr : results)
                    result.andAlso(sr, SubtypingSuppressionPolicy::All);
            }
        }
        else
        {
            for (auto&& sr : results)
                result.andAlso(sr);
        }
    }

    if (superTable->indexer)
    {
        if (subTable->indexer)
            result.andAlso(isInvariantWith(env, *subTable->indexer, *superTable->indexer, scope));
        else if (subTable->state != TableState::Sealed)
        {
            // As above, we assume that {| |} <: {T} because the unsealed table
            // on the left will eventually gain the necessary indexer.
            return {true};
        }
        else
            return {false};
    }

    return result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const MetatableType* subMt, const MetatableType* superMt, NotNull<Scope> scope)
{
    return isCovariantWith(env, subMt->table, superMt->table, scope)
        .withBothComponent(TypePath::TypeField::Table)
        .andAlso(isCovariantWith(env, subMt->metatable, superMt->metatable, scope).withBothComponent(TypePath::TypeField::Metatable));
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const MetatableType* subMt, const TableType* superTable, NotNull<Scope> scope)
{
    if (auto subTable = get<TableType>(follow(subMt->table)))
    {
        auto doDefault = [&]()
        {
            return isCovariantWith(env, subTable, superTable, /* forceCovariantTest */ false, scope);
        };

        // My kingdom for `do` notation.

        // TODO CLI-169235: This logic is very mechanical and is,
        // effectively a repeat of the logic for the `index<_, _>`
        // type function. These should use similar logic. Otherwise
        // this all constantly falls over for the same reasons
        // structural subtyping falls over.
        //
        // Notably, this does not support `__index` as a function.

        auto subMTTable = get<TableType>(follow(subMt->metatable));
        if (!subMTTable)
            return doDefault();

        auto indexProp = subMTTable->props.find("__index");
        if (indexProp == subMTTable->props.end())
            return doDefault();

        // `read`-only __index sounds reasonable, but write-only
        // or non-shared sounds weird.
        if (!indexProp->second.readTy)
            return doDefault();

        auto indexTableProp = get<TableType>(follow(*indexProp->second.readTy));
        if (!indexTableProp)
            return doDefault();

        // Consider the snippet:
        //
        //  local ItemContainer = {}
        //  ItemContainer.__index = ItemContainer
        //
        //  function ItemContainer.new()
        //      local self = {}
        //      setmetatable(self, ItemContainer)
        //      return self
        //  end
        //
        //  function ItemContainer:removeItem(itemId, itemType)
        //      self:getItem(itemId, itemType)
        //  end
        //
        //  function ItemContainer:getItem(itemId, itemType) end
        //
        //  local container = ItemContainer.new()
        //  container:removeItem(0, "magic")
        //
        // When we go to check this, we're effectively asking whether
        // `container` is a subtype of the first argument of
        // `container.removeItem`. `container` has a metatable with the
        // `__index` metamethod, so we need to include those fields in the
        // subtype check.
        //
        // However, we need to include a read only view of those fields.
        // Consider:
        //
        //  local Foobar = {}
        //  Foobar.__index = Foobar
        //  Foobar.const = 42
        //
        //  local foobar = setmetatable({}, Foobar)
        //
        //  local _: { const: number } = foobar
        //
        // This should error, as we cannot write to `const`.

        TableType fauxSubTable{*subTable};
        for (auto& [name, prop] : indexTableProp->props)
        {
            if (prop.readTy && fauxSubTable.props.find(name) == fauxSubTable.props.end())
                fauxSubTable.props[name] = Property::readonly(*prop.readTy);
        }

        return isCovariantWith(env, &fauxSubTable, superTable, /* forceCovariantTest */ false, scope);
    }
    else
    {
        // TODO: This may be a case we actually hit?
        return {false};
    }
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const MetatableType* subMt,
    const PrimitiveType* superPrim,
    NotNull<Scope> scope
)
{
    LUAU_ASSERT(FFlag::LuauTableFreezeCheckIsSubtype);

    // Metatable types can be subtypes of primitive table types if their table component is a subtype of table.
    if (superPrim->type == PrimitiveType::Table)
    {
        if (auto subTable = get<TableType>(follow(subMt->table)))
        {
            return isCovariantWith(env, subTable, superPrim, scope);
        }
        else if (auto subNestedMt = get<MetatableType>(follow(subMt->table)))
        {
            return isCovariantWith(env, subNestedMt, superPrim, scope);
        }
    }

    return {false};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const ExternType* subExternType,
    const ExternType* superExternType,
    NotNull<Scope> scope
)
{
    return {isSubclass(subExternType, superExternType)};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    TypeId subTy,
    const ExternType* subExternType,
    TypeId superTy,
    const TableType* superTable,
    NotNull<Scope> scope
)
{
    SubtypingResult result{true};

    env.substitutions[superTy] = subTy;

    for (const auto& [name, prop] : superTable->props)
    {
        if (auto classProp = lookupExternTypeProp(subExternType, name))
        {
            result.andAlso(isCovariantWith(env, *classProp, prop, name, /*forceCovariantTest*/ false, scope));
        }
        else
        {
            result = {false};
            break;
        }
    }

    if (superTable->indexer && subExternType->indexer)
    {
        // NOTE: despite the name, this will internally check that the two
        // indexers are invariant with one another.
        result.andAlso(isCovariantWith(env, *subExternType->indexer, *superTable->indexer, scope));
    }
    else if (superTable->indexer && !subExternType->indexer)
    {
        // If the super table has an indexer and the sub extern type does
        // not, claim this isn't a subtype. For example:
        //
        //  declare extern type Vector3 with
        //      X: number
        //      Y: number
        //      Z: number
        //  end
        //
        //  local function cast(v: Vector3): { [string]: number }
        //      return v
        //  end
        //
        //  local function ohno(v: Vector3)
        //      local v_prime = cast(v)
        //      v_prime["well thats not good"] = 42
        //  end
        result = {/* isSubtype */ false};
    }
    // The remaining cases are:
    //  - The extern type has an indexer and the table does not: this is
    //    fine under width subtyping (for now).
    //  - Neither the extern type nor the table has an indexer, which is
    //    also fine.

    env.substitutions[superTy] = nullptr;

    return result;
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const FunctionType* subFunction,
    const FunctionType* superFunction,
    NotNull<Scope> scope
)
{
    SubtypingResult result;

    if (!subFunction->generics.empty())
    {
        for (TypeId g : subFunction->generics)
        {
            g = follow(g);
            if (get<GenericType>(g))
            {
                if (auto bounds = env.mappedGenerics.find(g))
                    // g may shadow an existing generic, so push a fresh set of bounds
                    bounds->emplace_back();
                else
                    env.mappedGenerics[g] = {SubtypingEnvironment::GenericBounds{}};
            }
        }
    }

    if (!subFunction->genericPacks.empty())
    {
        std::vector<TypePackId> packs;
        packs.reserve(subFunction->genericPacks.size());

        for (TypePackId g : subFunction->genericPacks)
        {
            g = follow(g);
            if (get<GenericTypePack>(g))
                packs.emplace_back(g);
        }

        env.mappedGenericPacks.pushFrame(packs);
    }

    {
        result.orElse(
            isContravariantWith(env, subFunction->argTypes, superFunction->argTypes, scope).withBothComponent(TypePath::PackField::Arguments)
        );

        // If subtyping failed in the argument packs, we should check if there's a hidden variadic tail and try ignoring it.
        // This might cause subtyping correctly because the sub type here may not have a hidden variadic tail or equivalent.
        if (!result.isSubtype)
        {
            auto [arguments, tail] = flatten(superFunction->argTypes);

            if (auto variadic = get<VariadicTypePack>(tail); variadic && variadic->hidden)
            {
                result.orElse(isContravariantWith(env, subFunction->argTypes, arena->addTypePack(TypePack{arguments}), scope)
                                  .withBothComponent(TypePath::PackField::Arguments));
            }
        }
    }

    result.andAlso(isCovariantWith(env, subFunction->retTypes, superFunction->retTypes, scope).withBothComponent(TypePath::PackField::Returns));

    if (*subFunction->argTypes == *superFunction->argTypes && *subFunction->retTypes == *superFunction->retTypes)
    {
        if (FFlag::LuauOverloadGetsInstantiated)
        {
            // It's fine to upcast a function with generics to a function without, for example:
            //
            //  local f: ({number}) -> number = (nil :: <T>({T}) -> T)
            //
            // ... or even ...
            //
            //  local f: () -> () = (nil :: <T>() -> ())
            //
            // Intuitively: a generic function should always be a subtype of its instantiations.
            if (superFunction->generics.size() != subFunction->generics.size() && !superFunction->generics.empty())
                result.andAlso({false}).withError(
                    TypeError{scope->location, GenericTypeCountMismatch{superFunction->generics.size(), subFunction->generics.size()}}
                );

            if (superFunction->genericPacks.size() != subFunction->genericPacks.size() && !superFunction->genericPacks.empty())
                result.andAlso({false}).withError(
                    TypeError{scope->location, GenericTypePackCountMismatch{superFunction->genericPacks.size(), subFunction->genericPacks.size()}}
                );
        }
        else
        {
            if (superFunction->generics.size() != subFunction->generics.size())
                result.andAlso({false}).withError(
                    TypeError{scope->location, GenericTypeCountMismatch{superFunction->generics.size(), subFunction->generics.size()}}
                );
            if (superFunction->genericPacks.size() != subFunction->genericPacks.size())
                result.andAlso({false}).withError(
                    TypeError{scope->location, GenericTypePackCountMismatch{superFunction->genericPacks.size(), subFunction->genericPacks.size()}}
                );
        }
    }

    if (!subFunction->generics.empty())
    {
        for (TypeId g : subFunction->generics)
        {
            g = follow(g);
            if (const GenericType* gen = get<GenericType>(g))
            {
                auto bounds = env.mappedGenerics.find(g);
                LUAU_ASSERT(bounds && !bounds->empty());
                // Check the bounds are valid
                result.andAlso(checkGenericBounds(bounds->back(), env, scope, gen->name));

                bounds->pop_back();
            }
        }
    }

    if (!subFunction->genericPacks.empty())
    {
        env.mappedGenericPacks.popFrame();
        // This result isn't cacheable, because we may need it to populate the generic pack mapping environment again later
        result.isCacheable = false;
    }

    return result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const TableType* subTable, const PrimitiveType* superPrim, NotNull<Scope> scope)
{
    SubtypingResult result{false};
    if (superPrim->type == PrimitiveType::Table)
        result.isSubtype = true;

    return result;
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const PrimitiveType* subPrim, const TableType* superTable, NotNull<Scope> scope)
{
    SubtypingResult result{false};
    if (subPrim->type == PrimitiveType::String)
    {
        if (auto metatable = getMetatable(builtinTypes->stringType, builtinTypes))
        {
            if (auto mttv = get<TableType>(follow(metatable)))
            {
                if (auto it = mttv->props.find("__index"); it != mttv->props.end())
                {
                    // the `string` metatable should not have any write-only types.
                    LUAU_ASSERT(*it->second.readTy);

                    if (auto stringTable = get<TableType>(*it->second.readTy))
                        result.orElse(isCovariantWith(env, stringTable, superTable, /*forceCovariantTest*/ false, scope)
                                          .withSubPath(TypePath::PathBuilder().mt().readProp("__index").build()));
                }
            }
        }
    }
    else if (subPrim->type == PrimitiveType::Table)
    {
        const bool isSubtype = superTable->props.empty() && (!superTable->indexer.has_value() || superTable->state == TableState::Generic);
        return {isSubtype};
    }

    return result;
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const SingletonType* subSingleton,
    const TableType* superTable,
    NotNull<Scope> scope
)
{
    SubtypingResult result{false};
    if (get<StringSingleton>(subSingleton))
    {
        if (auto metatable = getMetatable(builtinTypes->stringType, builtinTypes))
        {
            if (auto mttv = get<TableType>(follow(metatable)))
            {
                if (auto it = mttv->props.find("__index"); it != mttv->props.end())
                {
                    // the `string` metatable should not have any write-only types.
                    LUAU_ASSERT(*it->second.readTy);

                    if (auto stringTable = get<TableType>(*it->second.readTy))
                        result.orElse(isCovariantWith(env, stringTable, superTable, /*forceCovariantTest*/ false, scope)
                                          .withSubPath(TypePath::PathBuilder().mt().readProp("__index").build()));
                }
            }
        }
    }
    return result;
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const TableIndexer& subIndexer,
    const TableIndexer& superIndexer,
    NotNull<Scope> scope
)
{
    return isInvariantWith(env, subIndexer.indexType, superIndexer.indexType, scope)
        .withBothComponent(TypePath::TypeField::IndexLookup)
        .andAlso(
            isInvariantWith(env, subIndexer.indexResultType, superIndexer.indexResultType, scope).withBothComponent(TypePath::TypeField::IndexResult)
        );
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const Property& subProp,
    const Property& superProp,
    const std::string& name,
    bool forceCovariantTest,
    NotNull<Scope> scope
)
{
    SubtypingResult res{true};

    if (superProp.isShared() && subProp.isShared())
    {
        if (forceCovariantTest)
            res.andAlso(isCovariantWith(env, *subProp.readTy, *superProp.readTy, scope).withBothComponent(TypePath::Property::read(name)));
        else
            res.andAlso(isInvariantWith(env, *subProp.readTy, *superProp.readTy, scope).withBothComponent(TypePath::Property::read(name)));
    }
    else
    {
        if (superProp.readTy.has_value() && subProp.readTy.has_value())
            res.andAlso(isCovariantWith(env, *subProp.readTy, *superProp.readTy, scope).withBothComponent(TypePath::Property::read(name)));
        if (superProp.writeTy.has_value() && subProp.writeTy.has_value() && !forceCovariantTest)
            res.andAlso(isContravariantWith(env, *subProp.writeTy, *superProp.writeTy, scope).withBothComponent(TypePath::Property::write(name)));

        if (superProp.isReadWrite())
        {
            if (subProp.isReadOnly())
                res.andAlso(SubtypingResult{false}.withBothComponent(TypePath::Property::read(name)));
            else if (subProp.isWriteOnly())
                res.andAlso(SubtypingResult{false}.withBothComponent(TypePath::Property::write(name)));
        }
    }

    return res;
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const std::shared_ptr<const NormalizedType>& subNorm,
    const std::shared_ptr<const NormalizedType>& superNorm,
    NotNull<Scope> scope
)
{
    if (!subNorm || !superNorm)
        return {false, true};

    SubtypingResult result = isCovariantWith(env, subNorm->tops, superNorm->tops, scope);
    result.andAlso(isCovariantWith(env, subNorm->booleans, superNorm->booleans, scope));
    result.andAlso(isCovariantWith(env, subNorm->externTypes, superNorm->externTypes, scope)
                       .orElse(isCovariantWith(env, subNorm->externTypes, superNorm->tables, scope)));
    result.andAlso(isCovariantWith(env, subNorm->errors, superNorm->errors, scope));
    result.andAlso(isCovariantWith(env, subNorm->nils, superNorm->nils, scope));
    result.andAlso(isCovariantWith(env, subNorm->numbers, superNorm->numbers, scope));
    result.andAlso(isCovariantWith(env, subNorm->strings, superNorm->strings, scope));
    result.andAlso(isCovariantWith(env, subNorm->strings, superNorm->tables, scope));
    result.andAlso(isCovariantWith(env, subNorm->threads, superNorm->threads, scope));
    result.andAlso(isCovariantWith(env, subNorm->buffers, superNorm->buffers, scope));
    result.andAlso(isCovariantWith(env, subNorm->tables, superNorm->tables, scope));
    result.andAlso(isCovariantWith(env, subNorm->functions, superNorm->functions, scope));
    // isCovariantWith(subNorm->tyvars, superNorm->tyvars);
    return result;
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const NormalizedExternType& subExternType,
    const NormalizedExternType& superExternType,
    NotNull<Scope> scope
)
{
    for (const auto& [subExternTypeTy, _] : subExternType.externTypes)
    {
        SubtypingResult result;

        for (const auto& [superExternTypeTy, superNegations] : superExternType.externTypes)
        {
            result.orElse(isCovariantWith(env, subExternTypeTy, superExternTypeTy, scope));
            if (!result.isSubtype)
                continue;

            for (TypeId negation : superNegations)
            {
                result.andAlso(SubtypingResult::negate(isCovariantWith(env, subExternTypeTy, negation, scope)));
                if (result.isSubtype)
                    break;
            }
        }

        if (!result.isSubtype)
            return result;
    }

    return {true};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const NormalizedExternType& subExternType,
    const TypeIds& superTables,
    NotNull<Scope> scope
)
{
    for (const auto& [subExternTypeTy, _] : subExternType.externTypes)
    {
        SubtypingResult result;

        for (TypeId superTableTy : superTables)
            result.orElse(isCovariantWith(env, subExternTypeTy, superTableTy, scope));

        if (!result.isSubtype)
            return result;
    }

    return {true};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const NormalizedStringType& subString,
    const NormalizedStringType& superString,
    NotNull<Scope> scope
)
{
    bool isSubtype = Luau::isSubtype(subString, superString);
    return {isSubtype};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const NormalizedStringType& subString,
    const TypeIds& superTables,
    NotNull<Scope> scope
)
{
    if (subString.isNever())
        return {true};

    if (subString.isCofinite)
    {
        SubtypingResult result;
        for (const auto& superTable : superTables)
        {
            result.orElse(isCovariantWith(env, builtinTypes->stringType, superTable, scope));
            if (result.isSubtype)
                return result;
        }
        return result;
    }

    // Finite case
    // S = s1 | s2 | s3 ... sn <: t1 | t2 | ... | tn
    // iff for some ti, S <: ti
    // iff for all sj, sj <: ti
    for (const auto& superTable : superTables)
    {
        SubtypingResult result{true};
        for (const auto& [_, subString] : subString.singletons)
        {
            result.andAlso(isCovariantWith(env, subString, superTable, scope));
            if (!result.isSubtype)
                break;
        }

        if (!result.isSubtype)
            continue;
        else
            return result;
    }

    return {false};
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const NormalizedFunctionType& subFunction,
    const NormalizedFunctionType& superFunction,
    NotNull<Scope> scope
)
{
    if (subFunction.isNever())
        return {true};
    else if (superFunction.isTop)
        return {true};
    else
        return isCovariantWith(env, subFunction.parts, superFunction.parts, scope);
}

SubtypingResult Subtyping::isCovariantWith(SubtypingEnvironment& env, const TypeIds& subTypes, const TypeIds& superTypes, NotNull<Scope> scope)
{
    auto result = std::make_unique<SubtypingResult>();
    result->isSubtype = true;

    for (TypeId subTy : subTypes)
    {
        auto innerResult = std::make_unique<SubtypingResult>();

        for (TypeId superTy : superTypes)
        {
            innerResult->orElse(isCovariantWith(env, subTy, superTy, scope));

            if (innerResult->normalizationTooComplex)
                return SubtypingResult{false, /* normalizationTooComplex */ true};
        }

        result->andAlso(*innerResult);
    }

    return *result;
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const VariadicTypePack* subVariadic,
    const VariadicTypePack* superVariadic,
    NotNull<Scope> scope
)
{
    return isCovariantWith(env, subVariadic->ty, superVariadic->ty, scope).withBothComponent(TypePath::TypeField::Variadic);
}

bool Subtyping::bindGeneric(SubtypingEnvironment& env, TypeId subTy, TypeId superTy) const
{
    subTy = follow(subTy);
    superTy = follow(superTy);
    std::optional<SubtypingEnvironment::GenericBounds> originalSubTyBounds = std::nullopt;

    if (const auto subBounds = env.mappedGenerics.find(subTy); subBounds && !subBounds->empty())
    {
        LUAU_ASSERT(get<GenericType>(subTy));

        originalSubTyBounds = SubtypingEnvironment::GenericBounds{subBounds->back()};

        auto& [lowerSubBounds, upperSubBounds] = subBounds->back();

        if (const auto superBounds = env.mappedGenerics.find(superTy); superBounds && !superBounds->empty())
        {
            LUAU_ASSERT(get<GenericType>(superTy));

            const auto& [lowerSuperBounds, upperSuperBounds] = superBounds->back();

            maybeUpdateBounds(subTy, superTy, upperSubBounds, lowerSuperBounds, upperSuperBounds);
        }
        else
            upperSubBounds.insert(superTy);
    }
    else if (env.containsMappedType(subTy))
        iceReporter->ice("attempting to modify bounds of a potentially visited generic");

    if (const auto superBounds = env.mappedGenerics.find(superTy); superBounds && !superBounds->empty())
    {
        LUAU_ASSERT(get<GenericType>(superTy));

        auto& [lowerSuperBounds, upperSuperBounds] = superBounds->back();

        if (originalSubTyBounds)
        {
            LUAU_ASSERT(get<GenericType>(subTy));

            const auto& [originalLowerSubBound, originalUpperSubBound] = *originalSubTyBounds;

            maybeUpdateBounds(superTy, subTy, lowerSuperBounds, originalUpperSubBound, originalLowerSubBound);
        }
        else
            lowerSuperBounds.insert(subTy);
    }
    else if (env.containsMappedType(superTy))
        iceReporter->ice("attempting to modify bounds of a potentially visited generic");

    return true;
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const TypeFunctionInstanceType* subFunctionInstance,
    const TypeId superTy,
    NotNull<Scope> scope
)
{
    // Reduce the type function instance
    auto [ty, errors] = handleTypeFunctionReductionResult(subFunctionInstance, scope);

    // If we return optional, that means the type function was irreducible - we can reduce that to never
    return isCovariantWith(env, ty, superTy, scope).withErrors(errors).withSubComponent(TypePath::Reduction{ty});
}

SubtypingResult Subtyping::isCovariantWith(
    SubtypingEnvironment& env,
    const TypeId subTy,
    const TypeFunctionInstanceType* superFunctionInstance,
    NotNull<Scope> scope
)
{
    // Reduce the type function instance
    auto [ty, errors] = handleTypeFunctionReductionResult(superFunctionInstance, scope);
    return isCovariantWith(env, subTy, ty, scope).withErrors(errors).withSuperComponent(TypePath::Reduction{ty});
}

template<typename T, typename Container>
TypeId Subtyping::makeAggregateType(const Container& container, TypeId orElse)
{
    if (container.empty())
        return orElse;
    else if (container.size() == 1)
        return *begin(container);
    else
        return arena->addType(T{std::vector<TypeId>(begin(container), end(container))});
}

std::pair<TypeId, ErrorVec> Subtyping::handleTypeFunctionReductionResult(const TypeFunctionInstanceType* functionInstance, NotNull<Scope> scope)
{
    TypeFunctionContext context{arena, builtinTypes, scope, normalizer, typeFunctionRuntime, iceReporter, NotNull{&limits}};
    TypeId function = arena->addType(*functionInstance);
    FunctionGraphReductionResult result = reduceTypeFunctions(function, {}, NotNull{&context}, true);
    ErrorVec errors;
    if (result.blockedTypes.size() != 0 || result.blockedPacks.size() != 0)
    {
        errors.emplace_back(Location{}, UninhabitedTypeFunction{function});
        return {builtinTypes->neverType, errors};
    }
    if (result.reducedTypes.contains(function))
        return {function, errors};
    return {builtinTypes->neverType, errors};
}

SubtypingResult Subtyping::trySemanticSubtyping(
    SubtypingEnvironment& env,
    TypeId subTy,
    TypeId superTy,
    NotNull<Scope> scope,
    SubtypingResult& original
)
{
    SubtypingResult semantic = isCovariantWith(env, normalizer->normalize(subTy), normalizer->normalize(superTy), scope);

    if (semantic.normalizationTooComplex)
    {
        return semantic;
    }
    else if (semantic.isSubtype)
    {
        semantic.reasoning.clear();
        return semantic;
    }

    return original;
}


SubtypingResult Subtyping::checkGenericBounds(
    const SubtypingEnvironment::GenericBounds& bounds,
    SubtypingEnvironment& env,
    NotNull<Scope> scope,
    std::string_view genericName
)
{
    SubtypingResult result{true};

    const auto& [lb, ub] = bounds;

    if (FFlag::LuauSubtypingReplaceBounds)
    {
        UnionBuilder aggregateLowerBound{arena, builtinTypes};
        aggregateLowerBound.reserve(lb.size());
        for (TypeId t : lb)
        {
            if (const auto mappedBounds = env.mappedGenerics.find(t); mappedBounds && mappedBounds->empty())
                continue;
            aggregateLowerBound.add(t);
        }
        TypeId lowerBound = aggregateLowerBound.build();

        IntersectionBuilder aggregateUpperBound{arena, builtinTypes};
        aggregateUpperBound.reserve(ub.size());
        for (TypeId t : ub)
        {
            if (const auto mappedBounds = env.mappedGenerics.find(t); mappedBounds && mappedBounds->empty())
                continue;
            aggregateUpperBound.add(t);
        }
        TypeId upperBound = aggregateUpperBound.build();

        if (auto substLowerBound = env.applyMappedGenerics(builtinTypes, arena, lowerBound, iceReporter))
            lowerBound = *substLowerBound;

        if (auto substUpperBound = env.applyMappedGenerics(builtinTypes, arena, upperBound, iceReporter))
            upperBound = *substUpperBound;

        std::shared_ptr<const NormalizedType> nt = normalizer->normalize(upperBound);
        // we say that the result is true if normalization failed because complex types are likely to be inhabited.
        NormalizationResult res = nt ? normalizer->isInhabited(nt.get()) : NormalizationResult::True;

        if (!nt || res == NormalizationResult::HitLimits)
            result.normalizationTooComplex = true;
        else if (res == NormalizationResult::False)
        {
            /* If the normalized upper bound we're mapping to a generic is
             * uninhabited, then we must consider the subtyping relation not to
             * hold.
             *
             * This happens eg in <T>() -> (T, T) <: () -> (string, number)
             *
             * T appears in covariant position and would have to be both string
             * and number at once.
             *
             * No actual value is both a string and a number, so the test fails.
             *
             * TODO: We'll need to add explanitory context here.
             */
            result.isSubtype = false;
        }

        SubtypingEnvironment boundsEnv;
        boundsEnv.parent = &env;
        SubtypingResult boundsResult = isCovariantWith(boundsEnv, lowerBound, upperBound, scope);
        boundsResult.reasoning.clear();

        if (res == NormalizationResult::False)
            result.genericBoundsMismatches.emplace_back(genericName, bounds.lowerBound, bounds.upperBound);
        else if (!boundsResult.isSubtype)
        {
            // Check if the bounds are error suppressing before reporting a mismatch
            switch (shouldSuppressErrors(normalizer, lowerBound).orElse(shouldSuppressErrors(normalizer, upperBound)))
            {
            case ErrorSuppression::Suppress:
                break;
            case ErrorSuppression::NormalizationFailed:
                // intentionally fallthrough here since we couldn't prove this was error-suppressing
                [[fallthrough]];
            case ErrorSuppression::DoNotSuppress:
                result.genericBoundsMismatches.emplace_back(genericName, bounds.lowerBound, bounds.upperBound);
                break;
            default:
                LUAU_ASSERT(0);
                break;
            }
        }

        result.andAlso(boundsResult);
    }
    else
    {

        TypeIds lbTypes;
        for (TypeId t : lb)
        {
            t = follow(t);
            if (const auto mappedBounds = env.mappedGenerics.find(t))
            {
                if (mappedBounds->empty()) // If the generic is no longer in scope, we don't have any info about it
                    continue;

                auto& [lowerBound, upperBound] = mappedBounds->back();
                // We're populating the lower bounds, so we prioritize the upper bounds of a mapped generic
                if (!upperBound.empty())
                    lbTypes.insert(upperBound.begin(), upperBound.end());
                else if (!lowerBound.empty())
                    lbTypes.insert(lowerBound.begin(), lowerBound.end());
                else
                    lbTypes.insert(builtinTypes->unknownType);
            }
            else
                lbTypes.insert(t);
        }

        TypeIds ubTypes;
        for (TypeId t : ub)
        {
            t = follow(t);
            if (const auto mappedBounds = env.mappedGenerics.find(t))
            {
                if (mappedBounds->empty()) // If the generic is no longer in scope, we don't have any info about it
                    continue;

                auto& [lowerBound, upperBound] = mappedBounds->back();
                // We're populating the upper bounds, so we prioritize the lower bounds of a mapped generic
                if (!lowerBound.empty())
                    ubTypes.insert(lowerBound.begin(), lowerBound.end());
                else if (!upperBound.empty())
                    ubTypes.insert(upperBound.begin(), upperBound.end());
                else
                    ubTypes.insert(builtinTypes->unknownType);
            }
            else
                ubTypes.insert(t);
        }
        TypeId lowerBound = makeAggregateType<UnionType>(lbTypes.take(), builtinTypes->neverType);
        TypeId upperBound = makeAggregateType<IntersectionType>(ubTypes.take(), builtinTypes->unknownType);

        std::shared_ptr<const NormalizedType> nt = normalizer->normalize(upperBound);
        // we say that the result is true if normalization failed because complex types are likely to be inhabited.
        NormalizationResult res = nt ? normalizer->isInhabited(nt.get()) : NormalizationResult::True;

        if (!nt || res == NormalizationResult::HitLimits)
            result.normalizationTooComplex = true;
        else if (res == NormalizationResult::False)
        {
            /* If the normalized upper bound we're mapping to a generic is
             * uninhabited, then we must consider the subtyping relation not to
             * hold.
             *
             * This happens eg in <T>() -> (T, T) <: () -> (string, number)
             *
             * T appears in covariant position and would have to be both string
             * and number at once.
             *
             * No actual value is both a string and a number, so the test fails.
             *
             * TODO: We'll need to add explanitory context here.
             */
            result.isSubtype = false;
        }

        SubtypingEnvironment boundsEnv;
        boundsEnv.parent = &env;
        SubtypingResult boundsResult = isCovariantWith(boundsEnv, lowerBound, upperBound, scope);
        boundsResult.reasoning.clear();

        if (res == NormalizationResult::False)
            result.genericBoundsMismatches.emplace_back(genericName, bounds.lowerBound, bounds.upperBound);
        else if (!boundsResult.isSubtype)
        {
            // Check if the bounds are error suppressing before reporting a mismatch
            switch (shouldSuppressErrors(normalizer, lowerBound).orElse(shouldSuppressErrors(normalizer, upperBound)))
            {
            case ErrorSuppression::Suppress:
                break;
            case ErrorSuppression::NormalizationFailed:
                // intentionally fallthrough here since we couldn't prove this was error-suppressing
                [[fallthrough]];
            case ErrorSuppression::DoNotSuppress:
                result.genericBoundsMismatches.emplace_back(genericName, bounds.lowerBound, bounds.upperBound);
                break;
            default:
                LUAU_ASSERT(0);
                break;
            }
        }

        result.andAlso(boundsResult);
    }

    return result;
}

void Subtyping::maybeUpdateBounds(
    TypeId here,
    TypeId there,
    TypeIds& boundsToUpdate,
    const TypeIds& firstBoundsToCheck,
    const TypeIds& secondBoundsToCheck
)
{
    bool boundsChanged = false;

    if (!firstBoundsToCheck.empty())
    {
        for (const TypeId t : firstBoundsToCheck)
        {
            if (t != here) // We don't want to bound a generic by itself, ie A <: A
            {
                boundsToUpdate.insert(t);
                boundsChanged = true;
            }
        }
    }
    if (!boundsChanged && !secondBoundsToCheck.empty())
    {
        for (const TypeId t : secondBoundsToCheck)
        {
            if (t != here)
            {
                boundsToUpdate.insert(t);
                boundsChanged = true;
            }
        }
    }
    if (!boundsChanged && here != there)
        boundsToUpdate.insert(there);
}

} // namespace Luau