text: #include "core/errors/resolver.h"
  #include "ast/Helpers.h"
  #include "ast/Trees.h"
  #include "ast/ast.h"
  #include "ast/treemap/treemap.h"
  #include "common/sort.h"
  #include "core/Error.h"
  #include "core/Names.h"
  #include "core/StrictLevel.h"
  #include "core/core.h"
  #include "resolver/CorrectTypeAlias.h"
  #include "resolver/resolver.h"
  #include "resolver/type_syntax.h"
  
  #include "absl/strings/str_cat.h"
  #include "common/Timer.h"
  #include "common/concurrency/ConcurrentQueue.h"
  #include "core/Symbols.h"
  #include <utility>
  #include <vector>
  
  using namespace std;
  
  namespace sorbet::resolver {
  namespace {
  
  /*
   * Note: There are multiple separate tree walks defined in this file, the main
   * ones being:
   *
   * - ResolveConstantsWalk
   * - ResolveSignaturesWalk
   *
   * There are also other important parts of resolver found elsewhere in the
   * resolver/ package (GlobalPass, type_syntax). Below we describe
   * ResolveConstantsWalk, which is particularly sophisticated.
   *
   *                                - - - - -
   *
   * Ruby supports resolving constants via ancestors--superclasses and mixins.
   * Since superclass and mixins are themselves constant references, we thus may
   * not be able to resolve certain constants until after we've resolved others.
   *
   * To solve this, we collect any failed resolutions in a number of TODO lists,
   * and iterate over them to a fixed point (namely, either all constants
   * resolve, or no new constants resolve and we stub out any that remain).
   * In practice this fixed point computation terminates after 3 or fewer passes
   * on most real codebases.
   *
   * The four TODO lists that this loop maintains are:
   *
   *  - constants to be resolved
   *  - ancestors to be filled that require constants to be resolved
   *  - class aliases (class aliases know the symbol they alias to)
   *  - type aliases (type aliases know the fully parsed type of their RHS, and
   *    thus require their RHS to be resolved)
   *
   * Successful resolutions are removed from the lists, and then we loop again.
   * We track all these lists separately for the dual reasons that
   *
   * 1. Upon successful resolution, we need to do additional work (mutating the
   *    symbol table to reflect the new ancestors) and
   * 2. Resolving those constants potentially renders additional constants
   *    resolvable, and so if any resolution succeeds, we need to keep looping in
   *    the outer loop.
   *
   * We also track failure in the item, in order to distinguish a thing left in the
   * list because we simply haven't succeeded yet and a thing left in the list
   * because we have actively found a failure. For example, we might know that a
   * given constant is unresolvable by Sorbet because it was qualified under
   * not-a-constant: we mark this kind of job `resolution_failed`. The reason for
   * this is unresolved constants are set to noSymbol, and once constant resolution
   * has truly finished, we want to know which remaining failed jobs we need to set
   * to a sensible default value. (Setting a conceptually failed job to untyped()
   * before we've completed this loop can occasionally cause other jobs to
   * non-deterministically half-resolve in the presence of multiple errors---c.f.
   * issue #1126 on Github---so we mark jobs as failed rather than reporting an
   * error and "resolving" them as untyped during the loop.)
   *
   * After the above passes:
   *
   * - ast::UnresolvedConstantLit nodes (constants that have a NameRef) are
   *   replaced with ast::ConstantLit nodes (constants that have a SymbolRef).
   * - Every constant SymbolRef has enough to completely understand it's own
   *   place in the ancestor hierarchy.
   * - Every type alias symbol carries with it the type it should be treated as.
   *
   * The resolveConstants method is the best place to start if you want to browse
   * the fixed point loop at a high level.
   */
  
  class ResolveConstantsWalk {
      friend class ResolveSanityCheckWalk;
  
  private:
      struct Nesting {
          const shared_ptr<Nesting> parent;
          const core::SymbolRef scope;
  
          Nesting(shared_ptr<Nesting> parent, core::SymbolRef scope) : parent(std::move(parent)), scope(scope) {}
      };
      shared_ptr<Nesting> nesting_;
  
      struct ResolutionItem {
          shared_ptr<Nesting> scope;
          ast::ConstantLit *out;
          bool resolutionFailed = false;
  
          ResolutionItem() = default;
          ResolutionItem(ResolutionItem &&rhs) noexcept = default;
          ResolutionItem &operator=(ResolutionItem &&rhs) noexcept = default;
  
          ResolutionItem(const ResolutionItem &rhs) = delete;
          const ResolutionItem &operator=(const ResolutionItem &rhs) = delete;
      };
      struct AncestorResolutionItem {
          ast::ConstantLit *ancestor;
          core::SymbolRef klass;
  
          bool isSuperclass; // true if superclass, false for mixin
  
          AncestorResolutionItem() = default;
          AncestorResolutionItem(AncestorResolutionItem &&rhs) noexcept = default;
          AncestorResolutionItem &operator=(AncestorResolutionItem &&rhs) noexcept = default;
  
          AncestorResolutionItem(const AncestorResolutionItem &rhs) = delete;
          const AncestorResolutionItem &operator=(const AncestorResolutionItem &rhs) = delete;
      };
  
      struct ClassAliasResolutionItem {
          core::SymbolRef lhs;
          ast::ConstantLit *rhs;
  
          ClassAliasResolutionItem() = default;
          ClassAliasResolutionItem(ClassAliasResolutionItem &&) noexcept = default;
          ClassAliasResolutionItem &operator=(ClassAliasResolutionItem &&rhs) noexcept = default;
  
          ClassAliasResolutionItem(const ClassAliasResolutionItem &) = delete;
          const ClassAliasResolutionItem &operator=(const ClassAliasResolutionItem &) = delete;
      };
  
      struct TypeAliasResolutionItem {
          core::SymbolRef lhs;
          ast::Expression *rhs;
  
          TypeAliasResolutionItem(core::SymbolRef lhs, ast::Expression *rhs) : lhs(lhs), rhs(rhs) {}
          TypeAliasResolutionItem(TypeAliasResolutionItem &&) noexcept = default;
          TypeAliasResolutionItem &operator=(TypeAliasResolutionItem &&rhs) noexcept = default;
  
          TypeAliasResolutionItem(const TypeAliasResolutionItem &) = delete;
          const TypeAliasResolutionItem &operator=(const TypeAliasResolutionItem &) = delete;
      };
  
      vector<ResolutionItem> todo_;
      vector<AncestorResolutionItem> todoAncestors_;
      vector<ClassAliasResolutionItem> todoClassAliases_;
      vector<TypeAliasResolutionItem> todoTypeAliases_;
  
      static core::SymbolRef resolveLhs(core::Context ctx, shared_ptr<Nesting> nesting, core::NameRef name) {
          Nesting *scope = nesting.get();
          while (scope != nullptr) {
              auto lookup = scope->scope.data(ctx)->findMember(ctx, name);
              if (lookup.exists()) {
                  return lookup;
              }
              scope = scope->parent.get();
          }
          return nesting->scope.data(ctx)->findMemberTransitive(ctx, name);
      }
  
      static bool isAlreadyResolved(core::Context ctx, const ast::ConstantLit &original) {
          auto sym = original.symbol;
          if (!sym.exists()) {
              return false;
          }
          auto data = sym.data(ctx);
          if (data->isTypeAlias()) {
              return data->resultType != nullptr;
          } else {
              return true;
          }
      }
  
      class ResolutionChecker {
      public:
          bool seenUnresolved = false;
  
          unique_ptr<ast::ConstantLit> postTransformConstantLit(core::Context ctx,
                                                                unique_ptr<ast::ConstantLit> original) {
              seenUnresolved |= !isAlreadyResolved(ctx, *original);
              return original;
          };
      };
  
      static bool isFullyResolved(core::Context ctx, const ast::Expression *expression) {
          ResolutionChecker checker;
          unique_ptr<ast::Expression> dummy(const_cast<ast::Expression *>(expression));
          dummy = ast::TreeMap::apply(ctx, checker, std::move(dummy));
          ENFORCE(dummy.get() == expression);
          dummy.release();
          return !checker.seenUnresolved;
      }
  
      static core::SymbolRef resolveConstant(core::Context ctx, shared_ptr<Nesting> nesting,
                                             const unique_ptr<ast::UnresolvedConstantLit> &c, bool &resolutionFailed) {
          if (ast::isa_tree<ast::EmptyTree>(c->scope.get())) {
              core::SymbolRef result = resolveLhs(ctx, nesting, c->cnst);
              return result;
          }
          ast::Expression *resolvedScope = c->scope.get();
          if (auto *id = ast::cast_tree<ast::ConstantLit>(resolvedScope)) {
              auto sym = id->symbol;
              if (sym.exists() && sym.data(ctx)->isTypeAlias() && !resolutionFailed) {
                  if (auto e = ctx.state.beginError(c->loc, core::errors::Resolver::ConstantInTypeAlias)) {
                      e.setHeader("Resolving constants through type aliases is not supported");
                  }
                  resolutionFailed = true;
                  return core::Symbols::noSymbol();
              }
              if (!sym.exists()) {
                  return core::Symbols::noSymbol();
              }
              core::SymbolRef resolved = id->symbol.data(ctx)->dealias(ctx);
              core::SymbolRef result = resolved.data(ctx)->findMember(ctx, c->cnst);
              return result;
          } else {
              if (!resolutionFailed) {
                  if (auto e = ctx.state.beginError(c->loc, core::errors::Resolver::DynamicConstant)) {
                      e.setHeader("Dynamic constant references are unsupported");
                  }
              }
              resolutionFailed = true;
              return core::Symbols::noSymbol();
          }
      }
  
      // We have failed to resolve the constant. We'll need to report the error and stub it so that we can proceed
      static void constantResolutionFailed(core::MutableContext ctx, ResolutionItem &job, bool suggestDidYouMean) {
          auto resolved =
              resolveConstant(ctx.withOwner(job.scope->scope), job.scope, job.out->original, job.resolutionFailed);
          if (resolved.exists() && resolved.data(ctx)->isTypeAlias()) {
              if (resolved.data(ctx)->resultType == nullptr) {
                  // This is actually a use-site error, but we limit ourselves to emitting it once by checking resultType
                  auto loc = resolved.data(ctx)->loc();
                  if (auto e = ctx.state.beginError(loc, core::errors::Resolver::RecursiveTypeAlias)) {
                      e.setHeader("Unable to resolve right hand side of type alias `{}`", resolved.data(ctx)->show(ctx));
                      e.addErrorLine(job.out->original->loc, "Type alias used here");
                  }
                  resolved.data(ctx)->resultType =
                      core::Types::untyped(ctx, resolved); // <<-- This is the reason this takes a MutableContext
              }
              job.out->symbol = resolved;
              return;
          }
          if (job.resolutionFailed) {
              // we only set this when a job has failed for other reasons and we've already reported an error, and
              // continuining on will only redundantly report that we can't resolve the constant, so bail early here
              job.out->symbol = core::Symbols::untyped();
              return;
          }
          ENFORCE(!resolved.exists());
          ENFORCE(!job.out->symbol.exists());
  
          job.out->symbol = core::Symbols::StubModule();
  
          bool alreadyReported = false;
          if (auto *id = ast::cast_tree<ast::ConstantLit>(job.out->original->scope.get())) {
              auto originalScope = id->symbol.data(ctx)->dealias(ctx);
              if (originalScope == core::Symbols::StubModule()) {
                  // If we were trying to resolve some literal like C::D but `C` itself was already stubbed,
                  // no need to also report that `D` is missing.
                  alreadyReported = true;
  
                  job.out->resolutionScopes = {core::Symbols::noSymbol()};
              } else {
                  // We were trying to resolve a constant literal that had an explicit scope.
                  // Since Sorbet doesn't combine ancestor resolution and explicit scope resolution,
                  // we just put a single entry in the resolutionScopes list.
                  job.out->resolutionScopes = {originalScope};
              }
          } else {
              auto nesting = job.scope;
              while (true) {
                  job.out->resolutionScopes.emplace_back(nesting->scope);
                  if (nesting->parent == nullptr) {
                      break;
                  }
  
                  nesting = nesting->parent;
              }
          }
  
          ENFORCE(!job.out->resolutionScopes.empty());
          ENFORCE(job.scope->scope != core::Symbols::StubModule());
  
          auto customAutogenError = job.out->original->cnst == core::Symbols::Subclasses().data(ctx)->name;
          if (!alreadyReported || customAutogenError) {
              if (auto e = ctx.state.beginError(job.out->original->loc, core::errors::Resolver::StubConstant)) {
                  e.setHeader("Unable to resolve constant `{}`", job.out->original->cnst.show(ctx));
  
                  auto suggestScope = job.out->resolutionScopes.front();
                  if (customAutogenError) {
                      e.addErrorSection(
                          core::ErrorSection("If this constant is generated by Autogen, you "
                                             "may need to re-generate the .rbi. Try running:\n"
                                             "  scripts/bin/remote-script sorbet/shim_generation/autogen.rb"));
                  } else if (suggestDidYouMean && suggestScope.exists() && suggestScope.data(ctx)->isClassOrModule()) {
                      auto suggested = suggestScope.data(ctx)->findMemberFuzzyMatch(ctx, job.out->original->cnst);
                      if (suggested.size() > 3) {
                          suggested.resize(3);
                      }
                      if (!suggested.empty()) {
                          vector<core::ErrorLine> lines;
                          for (auto suggestion : suggested) {
                              const auto replacement = suggestion.symbol.show(ctx);
                              lines.emplace_back(core::ErrorLine::from(suggestion.symbol.data(ctx)->loc(),
                                                                       "Did you mean: `{}`?", replacement));
                              e.replaceWith(fmt::format("Replace with `{}`", replacement), job.out->loc, "{}",
                                            replacement);
                          }
                          e.addErrorSection(core::ErrorSection(lines));
                      }
                  }
              }
          }
      }
  
      static bool resolveJob(core::Context ctx, ResolutionItem &job) {
          if (isAlreadyResolved(ctx, *job.out)) {
              return true;
          }
          auto resolved =
              resolveConstant(ctx.withOwner(job.scope->scope), job.scope, job.out->original, job.resolutionFailed);
          if (!resolved.exists()) {
              return false;
          }
          if (resolved.data(ctx)->isTypeAlias()) {
              if (resolved.data(ctx)->resultType != nullptr) {
                  job.out->symbol = resolved;
                  return true;
              }
              return false;
          }
  
          job.out->symbol = resolved;
          return true;
      }
  
      static bool resolveTypeAliasJob(core::MutableContext ctx, TypeAliasResolutionItem &job) {
          core::SymbolRef enclosingTypeMember;
          core::SymbolRef enclosingClass = job.lhs.data(ctx)->enclosingClass(ctx);
          while (enclosingClass != core::Symbols::root()) {
              auto typeMembers = enclosingClass.data(ctx)->typeMembers();
              if (!typeMembers.empty()) {
                  enclosingTypeMember = typeMembers[0];
                  break;
              }
              enclosingClass = enclosingClass.data(ctx)->owner.data(ctx)->enclosingClass(ctx);
          }
          if (enclosingTypeMember.exists()) {
              if (auto e = ctx.state.beginError(job.rhs->loc, core::errors::Resolver::TypeAliasInGenericClass)) {
                  e.setHeader("Type aliases are not allowed in generic classes");
                  e.addErrorLine(enclosingTypeMember.data(ctx)->loc(), "Here is enclosing generic member");
              }
              job.lhs.data(ctx)->resultType = core::Types::untyped(ctx, job.lhs);
              return true;
          }
          if (isFullyResolved(ctx, job.rhs)) {
              // this todo will be resolved during ResolveTypeMembersWalk below
              job.lhs.data(ctx)->resultType = core::make_type<core::ClassType>(core::Symbols::todo());
              return true;
          }
  
          return false;
      }
  
      static bool resolveClassAliasJob(core::MutableContext ctx, ClassAliasResolutionItem &it) {
          auto rhsSym = it.rhs->symbol;
          if (!rhsSym.exists()) {
              return false;
          }
  
          auto rhsData = rhsSym.data(ctx);
          if (rhsData->isTypeAlias()) {
              if (auto e = ctx.state.beginError(it.rhs->loc, core::errors::Resolver::ReassignsTypeAlias)) {
                  e.setHeader("Reassigning a type alias is not allowed");
                  e.addErrorLine(rhsData->loc(), "Originally defined here");
                  e.replaceWith("Declare as type alias", it.rhs->loc, "T.type_alias {{{}}}", it.rhs->loc.source(ctx));
              }
              it.lhs.data(ctx)->resultType = core::Types::untypedUntracked();
              return true;
          } else {
              if (rhsData->dealias(ctx) != it.lhs) {
                  it.lhs.data(ctx)->resultType = core::make_type<core::AliasType>(rhsSym);
              } else {
                  if (auto e =
                          ctx.state.beginError(it.lhs.data(ctx)->loc(), core::errors::Resolver::RecursiveClassAlias)) {
                      e.setHeader("Class alias aliases to itself");
                  }
                  it.lhs.data(ctx)->resultType = core::Types::untypedUntracked();
              }
              return true;
          }
      }
  
      static void saveAncestorTypeForHashing(core::MutableContext ctx, const AncestorResolutionItem &item) {
          // For LSP, create a synthetic method <unresolved-ancestors> that has a return type containing a type
          // for every ancestor. When this return type changes, LSP takes the slow path (see
          // Symbol::methodShapeHash()).
          auto unresolvedPath = item.ancestor->fullUnresolvedPath(ctx);
          if (!unresolvedPath.has_value()) {
              return;
          }
  
          auto ancestorType =
              core::make_type<core::UnresolvedClassType>(unresolvedPath->first, move(unresolvedPath->second));
  
          core::SymbolRef uaSym =
              ctx.state.enterMethodSymbol(core::Loc::none(), item.klass, core::Names::unresolvedAncestors());
          core::TypePtr resultType = uaSym.data(ctx)->resultType;
          if (!resultType) {
              uaSym.data(ctx)->resultType = core::TupleType::build(ctx, {ancestorType});
          } else if (auto tt = core::cast_type<core::TupleType>(resultType.get())) {
              tt->elems.push_back(ancestorType);
          } else {
              ENFORCE(false);
          }
      }
  
      static core::SymbolRef stubSymbolForAncestor(const AncestorResolutionItem &item) {
          if (item.isSuperclass) {
              return core::Symbols::StubSuperClass();
          } else {
              return core::Symbols::StubMixin();
          }
      }
  
      static bool resolveAncestorJob(core::MutableContext ctx, AncestorResolutionItem &job, bool lastRun) {
          auto ancestorSym = job.ancestor->symbol;
          if (!ancestorSym.exists()) {
              return false;
          }
  
          core::SymbolRef resolved;
          if (ancestorSym.data(ctx)->isTypeAlias()) {
              if (!lastRun) {
                  return false;
              }
              if (auto e = ctx.state.beginError(job.ancestor->loc, core::errors::Resolver::DynamicSuperclass)) {
                  e.setHeader("Superclasses and mixins may not be type aliases");
              }
              resolved = stubSymbolForAncestor(job);
          } else {
              resolved = ancestorSym.data(ctx)->dealias(ctx);
          }
  
          if (!resolved.data(ctx)->isClassOrModule()) {
              if (!lastRun) {
                  return false;
              }
              if (auto e = ctx.state.beginError(job.ancestor->loc, core::errors::Resolver::DynamicSuperclass)) {
                  e.setHeader("Superclasses and mixins may only use class aliases like `{}`", "A = Integer");
              }
              resolved = stubSymbolForAncestor(job);
          }
  
          if (resolved == job.klass) {
              if (auto e = ctx.state.beginError(job.ancestor->loc, core::errors::Resolver::CircularDependency)) {
                  e.setHeader("Circular dependency: `{}` is a parent of itself", job.klass.data(ctx)->show(ctx));
                  e.addErrorLine(resolved.data(ctx)->loc(), "Class definition");
              }
              resolved = stubSymbolForAncestor(job);
          } else if (resolved.data(ctx)->derivesFrom(ctx, job.klass)) {
              if (auto e = ctx.state.beginError(job.ancestor->loc, core::errors::Resolver::CircularDependency)) {
                  e.setHeader("Circular dependency: `{}` and `{}` are declared as parents of each other",
                              job.klass.data(ctx)->show(ctx), resolved.data(ctx)->show(ctx));
                  e.addErrorLine(job.klass.data(ctx)->loc(), "One definition");
                  e.addErrorLine(resolved.data(ctx)->loc(), "Other definition");
              }
              resolved = stubSymbolForAncestor(job);
          }
  
          bool ancestorPresent = true;
          if (job.isSuperclass) {
              if (resolved == core::Symbols::todo()) {
                  // No superclass specified
                  ancestorPresent = false;
              } else if (!job.klass.data(ctx)->superClass().exists() ||
                         job.klass.data(ctx)->superClass() == core::Symbols::todo() ||
                         job.klass.data(ctx)->superClass() == resolved) {
                  job.klass.data(ctx)->setSuperClass(resolved);
              } else {
                  if (auto e = ctx.state.beginError(job.ancestor->loc, core::errors::Resolver::RedefinitionOfParents)) {
                      e.setHeader("Parent of class `{}` redefined from `{}` to `{}`", job.klass.data(ctx)->show(ctx),
                                  job.klass.data(ctx)->superClass().show(ctx), resolved.show(ctx));
                  }
              }
          } else {
              ENFORCE(resolved.data(ctx)->isClassOrModule());
              job.klass.data(ctx)->addMixin(resolved);
          }
  
          if (ancestorPresent) {
              saveAncestorTypeForHashing(ctx, job);
          }
          return true;
      }
  
      static void tryRegisterSealedSubclass(core::MutableContext ctx, AncestorResolutionItem &job) {
          ENFORCE(job.ancestor->symbol.exists(), "Ancestor must exist, or we can't check whether it's sealed.");
          auto ancestorSym = job.ancestor->symbol.data(ctx)->dealias(ctx);
  
          if (!ancestorSym.data(ctx)->isClassOrModuleSealed()) {
              return;
          }
          Timer timeit(ctx.state.tracer(), "resolver.registerSealedSubclass");
  
          ancestorSym.data(ctx)->recordSealedSubclass(ctx, job.klass);
      }
  
      void transformAncestor(core::Context ctx, core::SymbolRef klass, unique_ptr<ast::Expression> &ancestor,
                             bool isSuperclass = false) {
          if (auto *constScope = ast::cast_tree<ast::UnresolvedConstantLit>(ancestor.get())) {
              unique_ptr<ast::UnresolvedConstantLit> inner(constScope);
              ancestor.release();
              auto scopeTmp = nesting_;
              if (isSuperclass) {
                  nesting_ = nesting_->parent;
              }
              ancestor = postTransformUnresolvedConstantLit(ctx, std::move(inner));
              nesting_ = scopeTmp;
          }
          AncestorResolutionItem job;
          job.klass = klass;
          job.isSuperclass = isSuperclass;
  
          if (auto *cnst = ast::cast_tree<ast::ConstantLit>(ancestor.get())) {
              auto sym = cnst->symbol;
              if (sym.exists() && sym.data(ctx)->isTypeAlias()) {
                  if (auto e = ctx.state.beginError(cnst->loc, core::errors::Resolver::DynamicSuperclass)) {
                      e.setHeader("Superclasses and mixins may not be type aliases");
                  }
                  return;
              }
              ENFORCE(sym.exists() || ast::isa_tree<ast::ConstantLit>(cnst->original->scope.get()) ||
                      ast::isa_tree<ast::EmptyTree>(cnst->original->scope.get()));
              if (isSuperclass && sym == core::Symbols::todo()) {
                  return;
              }
              job.ancestor = cnst;
          } else if (ancestor->isSelfReference()) {
              auto loc = ancestor->loc;
              auto enclosingClass = ctx.owner.data(ctx)->enclosingClass(ctx);
              auto nw = ast::MK::UnresolvedConstant(loc, std::move(ancestor), enclosingClass.data(ctx)->name);
              auto out = make_unique<ast::ConstantLit>(loc, enclosingClass, std::move(nw));
              job.ancestor = out.get();
              ancestor = std::move(out);
          } else if (ast::isa_tree<ast::EmptyTree>(ancestor.get())) {
              return;
          } else {
              ENFORCE(false, "Namer should have not allowed this");
          }
  
          todoAncestors_.emplace_back(std::move(job));
      }
  
  public:
      ResolveConstantsWalk(core::Context ctx) : nesting_(nullptr) {}
  
      unique_ptr<ast::ClassDef> preTransformClassDef(core::Context ctx, unique_ptr<ast::ClassDef> original) {
          nesting_ = make_unique<Nesting>(std::move(nesting_), original->symbol);
          return original;
      }
  
      unique_ptr<ast::Expression> postTransformUnresolvedConstantLit(core::Context ctx,
                                                                     unique_ptr<ast::UnresolvedConstantLit> c) {
          if (auto *constScope = ast::cast_tree<ast::UnresolvedConstantLit>(c->scope.get())) {
              unique_ptr<ast::UnresolvedConstantLit> inner(constScope);
              c->scope.release();
              c->scope = postTransformUnresolvedConstantLit(ctx, std::move(inner));
          }
          auto loc = c->loc;
          auto out = make_unique<ast::ConstantLit>(loc, core::Symbols::noSymbol(), std::move(c));
          ResolutionItem job{nesting_, out.get()};
          if (resolveJob(ctx, job)) {
              categoryCounterInc("resolve.constants.nonancestor", "firstpass");
          } else {
              todo_.emplace_back(std::move(job));
          }
          return out;
      }
  
      unique_ptr<ast::Expression> postTransformClassDef(core::Context ctx, unique_ptr<ast::ClassDef> original) {
          core::SymbolRef klass = original->symbol;
  
          for (auto &ancst : original->ancestors) {
              bool isSuperclass = (original->kind == ast::ClassDef::Kind::Class &&
                                   &ancst == &original->ancestors.front() && !klass.data(ctx)->isSingletonClass(ctx));
              transformAncestor(isSuperclass ? ctx : ctx.withOwner(klass), klass, ancst, isSuperclass);
          }
  
          auto singleton = klass.data(ctx)->lookupSingletonClass(ctx);
          for (auto &ancst : original->singletonAncestors) {
              ENFORCE(singleton.exists());
              transformAncestor(ctx.withOwner(klass), singleton, ancst);
          }
  
          nesting_ = nesting_->parent;
          return original;
      }
  
      unique_ptr<ast::Expression> postTransformAssign(core::Context ctx, unique_ptr<ast::Assign> asgn) {
          auto *id = ast::cast_tree<ast::ConstantLit>(asgn->lhs.get());
          if (id == nullptr || !id->symbol.dataAllowingNone(ctx)->isStaticField()) {
              return asgn;
          }
  
          auto *send = ast::cast_tree<ast::Send>(asgn->rhs.get());
          if (send != nullptr && send->fun == core::Names::typeAlias()) {
              if (!send->block) {
                  // if we have an invalid (i.e. nullary) call to TypeAlias, then we'll treat it as a type alias for
                  // Untyped and report an error here: otherwise, we end up in a state at the end of constant resolution
                  // that won't match our expected invariants (and in fact will fail our sanity checks)
                  // auto temporaryUntyped = ast::MK::Untyped(asgn->lhs.get()->loc);
                  auto temporaryUntyped = ast::MK::Block0(asgn->lhs.get()->loc, ast::MK::Untyped(asgn->lhs.get()->loc));
                  send->block = std::move(temporaryUntyped);
  
                  // because we're synthesizing a fake "untyped" here and actually adding it to the AST, we won't report
                  // an arity mismatch for `T.untyped` in the future, so report the arity mismatch now
                  if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::InvalidTypeAlias)) {
                      e.setHeader("No block given to `{}`", "T.type_alias");
                      CorrectTypeAlias::eagerToLazy(ctx, e, send);
                  }
              }
              auto typeAliasItem = TypeAliasResolutionItem{id->symbol, send->block->body.get()};
              this->todoTypeAliases_.emplace_back(std::move(typeAliasItem));
  
              // We also enter a ResolutionItem for the lhs of a type alias so even if the type alias isn't used,
              // we'll still emit a warning when the rhs of a type alias doesn't resolve.
              auto item = ResolutionItem{nesting_, id};
              this->todo_.emplace_back(std::move(item));
              return asgn;
          }
  
          auto *rhs = ast::cast_tree<ast::ConstantLit>(asgn->rhs.get());
          if (rhs == nullptr) {
              return asgn;
          }
  
          auto item = ClassAliasResolutionItem{id->symbol, rhs};
  
          // TODO(perf) currently, by construction the last item in resolve todo list is the one this alias depends on
          // We may be able to get some perf by using this
          this->todoClassAliases_.emplace_back(std::move(item));
          return asgn;
      }
  
      static bool compareLocs(core::Context ctx, core::Loc lhs, core::Loc rhs) {
          core::StrictLevel left = core::StrictLevel::Strong;
          core::StrictLevel right = core::StrictLevel::Strong;
  
          if (lhs.file().exists()) {
              left = lhs.file().data(ctx).strictLevel;
          }
          if (rhs.file().exists()) {
              right = rhs.file().data(ctx).strictLevel;
          }
  
          if (left != right) {
              return right < left;
          }
          if (lhs.file() != rhs.file()) {
              return lhs.file() < rhs.file();
          }
          if (lhs.beginPos() != rhs.beginPos()) {
              return lhs.beginPos() < rhs.beginPos();
          }
          return lhs.endPos() < rhs.endPos();
      }
  
      static int constantDepth(ast::ConstantLit *exp) {
          int depth = 0;
          ast::ConstantLit *scope = exp;
          while (scope->original && (scope = ast::cast_tree<ast::ConstantLit>(scope->original->scope.get()))) {
              depth += 1;
          }
          return depth;
      }
  
      struct ResolveWalkResult {
          vector<ResolutionItem> todo_;
          vector<AncestorResolutionItem> todoAncestors_;
          vector<ClassAliasResolutionItem> todoClassAliases_;
          vector<TypeAliasResolutionItem> todoTypeAliases_;
          vector<ast::ParsedFile> trees;
      };
  
      static bool locCompare(core::Loc lhs, core::Loc rhs) {
          if (lhs.file() < rhs.file()) {
              return true;
          }
          if (lhs.file() > rhs.file()) {
              return false;
          }
          if (lhs.beginPos() < rhs.beginPos()) {
              return true;
          }
          if (lhs.beginPos() > rhs.beginPos()) {
              return false;
          }
          return lhs.endPos() < rhs.endPos();
      }
  
      static vector<ast::ParsedFile> resolveConstants(core::MutableContext ctx, vector<ast::ParsedFile> trees,
                                                      WorkerPool &workers) {
          Timer timeit(ctx.state.tracer(), "resolver.resolve_constants");
          core::Context ictx = ctx;
          auto resultq = make_shared<BlockingBoundedQueue<ResolveWalkResult>>(trees.size());
          auto fileq = make_shared<ConcurrentBoundedQueue<ast::ParsedFile>>(trees.size());
          for (auto &tree : trees) {
              fileq->push(move(tree), 1);
          }
  
          workers.multiplexJob("resolveConstantsWalk", [ictx, fileq, resultq]() {
              Timer timeit(ictx.state.tracer(), "ResolveConstantsWorker");
              ResolveConstantsWalk constants(ictx);
              vector<ast::ParsedFile> partiallyResolvedTrees;
              ast::ParsedFile job;
              for (auto result = fileq->try_pop(job); !result.done(); result = fileq->try_pop(job)) {
                  if (result.gotItem()) {
                      job.tree = ast::TreeMap::apply(ictx, constants, std::move(job.tree));
                      partiallyResolvedTrees.emplace_back(move(job));
                  }
              }
              if (!partiallyResolvedTrees.empty()) {
                  ResolveWalkResult result{move(constants.todo_), move(constants.todoAncestors_),
                                           move(constants.todoClassAliases_), move(constants.todoTypeAliases_),
                                           move(partiallyResolvedTrees)};
                  auto computedTreesCount = result.trees.size();
                  resultq->push(move(result), computedTreesCount);
              }
          });
          trees.clear();
          vector<ResolutionItem> todo;
          vector<AncestorResolutionItem> todoAncestors;
          vector<ClassAliasResolutionItem> todoClassAliases;
          vector<TypeAliasResolutionItem> todoTypeAliases;
  
          {
              ResolveWalkResult threadResult;
              for (auto result = resultq->wait_pop_timed(threadResult, WorkerPool::BLOCK_INTERVAL(), ctx.state.tracer());
                   !result.done();
                   result = resultq->wait_pop_timed(threadResult, WorkerPool::BLOCK_INTERVAL(), ctx.state.tracer())) {
                  if (result.gotItem()) {
                      todo.insert(todo.end(), make_move_iterator(threadResult.todo_.begin()),
                                  make_move_iterator(threadResult.todo_.end()));
                      todoAncestors.insert(todoAncestors.end(), make_move_iterator(threadResult.todoAncestors_.begin()),
                                           make_move_iterator(threadResult.todoAncestors_.end()));
                      todoClassAliases.insert(todoClassAliases.end(),
                                              make_move_iterator(threadResult.todoClassAliases_.begin()),
                                              make_move_iterator(threadResult.todoClassAliases_.end()));
                      todoTypeAliases.insert(todoTypeAliases.end(),
                                             make_move_iterator(threadResult.todoTypeAliases_.begin()),
                                             make_move_iterator(threadResult.todoTypeAliases_.end()));
                      trees.insert(trees.end(), make_move_iterator(threadResult.trees.begin()),
                                   make_move_iterator(threadResult.trees.end()));
                  }
              }
          }
  
          fast_sort(todo,
                    [](const auto &lhs, const auto &rhs) -> bool { return locCompare(lhs.out->loc, rhs.out->loc); });
          fast_sort(todoAncestors, [](const auto &lhs, const auto &rhs) -> bool {
              return locCompare(lhs.ancestor->loc, rhs.ancestor->loc);
          });
          fast_sort(todoClassAliases,
                    [](const auto &lhs, const auto &rhs) -> bool { return locCompare(lhs.rhs->loc, rhs.rhs->loc); });
          fast_sort(todoTypeAliases,
                    [](const auto &lhs, const auto &rhs) -> bool { return locCompare(lhs.rhs->loc, rhs.rhs->loc); });
          fast_sort(trees,
                    [](const auto &lhs, const auto &rhs) -> bool { return locCompare(lhs.tree->loc, rhs.tree->loc); });
  
          Timer timeit1(ctx.state.tracer(), "resolver.resolve_constants.fixed_point");
  
          bool progress = true;
          bool first = true; // we need to run at least once to force class aliases and type aliases
  
          while (progress && (first || !todo.empty() || !todoAncestors.empty())) {
              first = false;
              counterInc("resolve.constants.retries");
              {
                  Timer timeit(ctx.state.tracer(), "resolver.resolve_constants.fixed_point.ancestors");
                  // This is an optimization. The order should not matter semantically
                  // We try to resolve most ancestors second because this makes us much more likely to resolve everything
                  // else.
                  int origSize = todoAncestors.size();
                  auto it =
                      remove_if(todoAncestors.begin(), todoAncestors.end(), [ctx](AncestorResolutionItem &job) -> bool {
                          auto resolved = resolveAncestorJob(ctx, job, false);
                          if (resolved) {
                              tryRegisterSealedSubclass(ctx, job);
                          }
                          return resolved;
                      });
                  todoAncestors.erase(it, todoAncestors.end());
                  progress = (origSize != todoAncestors.size());
                  categoryCounterAdd("resolve.constants.ancestor", "retry", origSize - todoAncestors.size());
              }
              {
                  Timer timeit(ctx.state.tracer(), "resolver.resolve_constants.fixed_point.constants");
                  int origSize = todo.size();
                  auto it = remove_if(todo.begin(), todo.end(),
                                      [ctx](ResolutionItem &job) -> bool { return resolveJob(ctx, job); });
                  todo.erase(it, todo.end());
                  progress = progress || (origSize != todo.size());
                  categoryCounterAdd("resolve.constants.nonancestor", "retry", origSize - todo.size());
              }
              {
                  Timer timeit(ctx.state.tracer(), "resolver.resolve_constants.fixed_point.class_aliases");
                  // This is an optimization. The order should not matter semantically
                  // This is done as a "pre-step" because the first iteration of this effectively ran in TreeMap.
                  // every item in todoClassAliases implicitly depends on an item in item in todo
                  // there would be no point in running the todoClassAliases step before todo
  
                  int origSize = todoClassAliases.size();
                  auto it =
                      remove_if(todoClassAliases.begin(), todoClassAliases.end(),
                                [ctx](ClassAliasResolutionItem &it) -> bool { return resolveClassAliasJob(ctx, it); });
                  todoClassAliases.erase(it, todoClassAliases.end());
                  progress = progress || (origSize != todoClassAliases.size());
                  categoryCounterAdd("resolve.constants.aliases", "retry", origSize - todoClassAliases.size());
              }
              {
                  Timer timeit(ctx.state.tracer(), "resolver.resolve_constants.fixed_point.type_aliases");
                  int origSize = todoTypeAliases.size();
                  auto it =
                      remove_if(todoTypeAliases.begin(), todoTypeAliases.end(),
                                [ctx](TypeAliasResolutionItem &it) -> bool { return resolveTypeAliasJob(ctx, it); });
                  todoTypeAliases.erase(it, todoTypeAliases.end());
                  progress = progress || (origSize != todoTypeAliases.size());
                  categoryCounterAdd("resolve.constants.typealiases", "retry", origSize - todoTypeAliases.size());
              }
          }
          // We can no longer resolve new constants. All the code below reports errors
  
          categoryCounterAdd("resolve.constants.nonancestor", "failure", todo.size());
          categoryCounterAdd("resolve.constants.ancestor", "failure", todoAncestors.size());
  
          /*
           * Sort errors so we choose a deterministic error to report for each
           * missing constant:
           *
           * - Visit the strictest files first. If we were to report an error in
           *     an untyped file it would get suppressed, even if the same error
           *     also appeared in a typed file.
           *
           * - Break ties within strictness levels by file ID. We populate file
           *     IDs in the order we are given files on the command-line, so this
           *     means users see the error on the first file they provided.
           *
           * - Within a file, report the first occurrence.
           */
          fast_sort(todo, [ctx](const auto &lhs, const auto &rhs) -> bool {
              if (lhs.out->loc == rhs.out->loc) {
                  return constantDepth(lhs.out) < constantDepth(rhs.out);
              }
              return compareLocs(ctx, lhs.out->loc, rhs.out->loc);
          });
  
          fast_sort(todoAncestors, [ctx](const auto &lhs, const auto &rhs) -> bool {
              if (lhs.ancestor->loc == rhs.ancestor->loc) {
                  return constantDepth(lhs.ancestor) < constantDepth(rhs.ancestor);
              }
              return compareLocs(ctx, lhs.ancestor->loc, rhs.ancestor->loc);
          });
  
          // Note that this is missing alias stubbing, thus resolveJob needs to be able to handle missing aliases.
  
          {
              Timer timeit(ctx.state.tracer(), "resolver.resolve_constants.errors");
              int i = -1;
              for (auto &job : todo) {
                  i++;
                  // Only give suggestions for the first 10, because fuzzy suggestions are expensive.
                  auto suggestDidYouMean = i < 10;
                  constantResolutionFailed(ctx, job, suggestDidYouMean);
              }
  
              for (auto &job : todoAncestors) {
                  auto resolved = resolveAncestorJob(ctx, job, true);
                  if (!resolved) {
                      resolved = resolveAncestorJob(ctx, job, true);
                      ENFORCE(resolved);
                  }
              }
          }
  
          return trees;
      }
  };
  
  class ResolveTypeMembersWalk {
      // A type_member, type_template, or T.type_alias that needs to have types
      // resolved.
      struct ResolveAssignItem {
          // The owner at the time the assignment was encountered.
          core::SymbolRef owner;
  
          // The symbol being populated, either a type alias or an individual
          // type_member.
          core::SymbolRef lhs;
  
          // The type_member, type_template, or type_alias of the RHS.
          ast::Send *rhs;
  
          // The symbols that this alias depends on that have type members.
          vector<core::SymbolRef> dependencies;
      };
  
      vector<ResolveAssignItem> todoAssigns_;
  
      // State for tracking type usage inside of a type alias or type member
      // definition
      bool trackDependencies_ = false;
      vector<bool> classOfDepth_;
      vector<core::SymbolRef> dependencies_;
  
      void extendClassOfDepth(unique_ptr<ast::Send> &send) {
          if (trackDependencies_) {
              classOfDepth_.emplace_back(isT(send->recv) && send->fun == core::Names::classOf());
          }
      }
  
      static bool isT(unique_ptr<ast::Expression> &expr) {
          auto *tMod = ast::cast_tree<ast::ConstantLit>(expr.get());
          return tMod && tMod->symbol == core::Symbols::T();
      }
  
      static bool isTodo(core::TypePtr type) {
          auto *todo = core::cast_type<core::ClassType>(type.get());
          return todo != nullptr && todo->symbol == core::Symbols::todo();
      }
  
      static bool isLHSResolved(core::MutableContext ctx, core::SymbolRef sym) {
          if (sym.data(ctx)->isTypeMember()) {
              auto *lambdaParam = core::cast_type<core::LambdaParam>(sym.data(ctx)->resultType.get());
              ENFORCE(lambdaParam != nullptr);
  
              // both bounds are set to todo in the namer, so it's sufficient to
              // just check one here.
              return !isTodo(lambdaParam->lowerBound);
          } else {
              return !isTodo(sym.data(ctx)->resultType);
          }
      }
  
      static bool isGenericResolved(core::MutableContext ctx, core::SymbolRef sym) {
          if (sym.data(ctx)->isClassOrModule()) {
              return absl::c_all_of(sym.data(ctx)->typeMembers(),
                                    [&](core::SymbolRef tm) { return isLHSResolved(ctx, tm); });
          } else {
              return isLHSResolved(ctx, sym);
          }
      }
  
      static void resolveTypeMember(core::MutableContext ctx, core::SymbolRef lhs, ast::Send *rhs) {
          auto data = lhs.data(ctx);
          auto owner = data->owner;
  
          core::LambdaParam *parentType = nullptr;
          auto parentMember = owner.data(ctx)->superClass().data(ctx)->findMember(ctx, data->name);
          if (parentMember.exists()) {
              if (parentMember.data(ctx)->isTypeMember()) {
                  parentType = core::cast_type<core::LambdaParam>(parentMember.data(ctx)->resultType.get());
                  ENFORCE(parentType != nullptr);
              } else if (auto e = ctx.state.beginError(rhs->loc, core::errors::Resolver::ParentTypeBoundsMismatch)) {
                  const auto parentShow = parentMember.data(ctx)->show(ctx);
                  e.setHeader("`{}` is a type member but `{}` is not a type member", data->show(ctx), parentShow);
                  e.addErrorLine(parentMember.data(ctx)->loc(), "`{}` definition", parentShow);
              }
          }
  
          // Initialize the resultType to a LambdaParam with default bounds
          auto lambdaParam = core::make_type<core::LambdaParam>(lhs, core::Types::bottom(), core::Types::top());
          data->resultType = lambdaParam;
          auto *memberType = core::cast_type<core::LambdaParam>(lambdaParam.get());
  
          // When no args are supplied, this implies that the upper and lower
          // bounds of the type parameter are top and bottom.
          ast::Hash *hash = nullptr;
          if (rhs->args.size() == 1) {
              hash = ast::cast_tree<ast::Hash>(rhs->args[0].get());
          } else if (rhs->args.size() == 2) {
              hash = ast::cast_tree<ast::Hash>(rhs->args[1].get());
          }
  
          if (hash) {
              int i = -1;
              for (auto &keyExpr : hash->keys) {
                  i++;
                  auto lit = ast::cast_tree<ast::Literal>(keyExpr.get());
                  if (lit && lit->isSymbol(ctx)) {
                      ParsedSig emptySig;
                      auto allowSelfType = true;
                      auto allowRebind = false;
                      auto allowTypeMember = false;
                      core::TypePtr resTy =
                          TypeSyntax::getResultType(ctx, *(hash->values[i]), emptySig,
                                                    TypeSyntaxArgs{allowSelfType, allowRebind, allowTypeMember, lhs});
  
                      switch (lit->asSymbol(ctx)._id) {
                          case core::Names::fixed()._id:
                              memberType->lowerBound = resTy;
                              memberType->upperBound = resTy;
                              break;
  
                          case core::Names::lower()._id:
                              memberType->lowerBound = resTy;
                              break;
  
                          case core::Names::upper()._id:
                              memberType->upperBound = resTy;
                              break;
                      }
                  }
              }
          }
  
          // If the parent bounds existis, validate the new bounds against
          // those of the parent.
          // NOTE: these errors could be better for cases involving
          // `fixed`.
          if (parentType != nullptr) {
              if (!core::Types::isSubType(ctx, parentType->lowerBound, memberType->lowerBound)) {
                  if (auto e = ctx.state.beginError(rhs->loc, core::errors::Resolver::ParentTypeBoundsMismatch)) {
                      e.setHeader("parent lower bound `{}` is not a subtype of lower bound `{}`",
                                  parentType->lowerBound->show(ctx), memberType->lowerBound->show(ctx));
                  }
              }
              if (!core::Types::isSubType(ctx, memberType->upperBound, parentType->upperBound)) {
                  if (auto e = ctx.state.beginError(rhs->loc, core::errors::Resolver::ParentTypeBoundsMismatch)) {
                      e.setHeader("upper bound `{}` is not a subtype of parent upper bound `{}`",
                                  memberType->upperBound->show(ctx), parentType->upperBound->show(ctx));
                  }
              }
          }
  
          // Ensure that the new lower bound is a subtype of the upper
          // bound. This will be a no-op in the case that the type member
          // is fixed.
          if (!core::Types::isSubType(ctx, memberType->lowerBound, memberType->upperBound)) {
              if (auto e = ctx.state.beginError(rhs->loc, core::errors::Resolver::InvalidTypeMemberBounds)) {
                  e.setHeader("`{}` is not a subtype of `{}`", memberType->lowerBound->show(ctx),
                              memberType->upperBound->show(ctx));
              }
          }
  
          // Once the owner has had all of its type members resolved, resolve the
          // AttachedClass on its singleton.
          if (isGenericResolved(ctx, owner)) {
              resolveAttachedClass(ctx, owner);
          }
      }
  
      static void resolveAttachedClass(core::MutableContext ctx, core::SymbolRef sym) {
          ENFORCE(sym.data(ctx)->isClassOrModule());
  
          auto singleton = sym.data(ctx)->lookupSingletonClass(ctx);
          if (!singleton.exists()) {
              return;
          }
  
          // NOTE: AttachedClass will not exist on `T.untyped`, which is a problem
          // because RuntimeProfiled is used as a synonym for `T.untyped`
          // internally.
          auto attachedClass = singleton.data(ctx)->findMember(ctx, core::Names::Constants::AttachedClass());
          if (!attachedClass.exists()) {
              return;
          }
  
          auto *lambdaParam = core::cast_type<core::LambdaParam>(attachedClass.data(ctx)->resultType.get());
          ENFORCE(lambdaParam != nullptr);
  
          if (isTodo(lambdaParam->lowerBound)) {
              lambdaParam->upperBound = sym.data(ctx)->externalType(ctx);
              lambdaParam->lowerBound = core::Types::bottom();
          }
  
          // If all of the singleton members have been resolved, attempt to
          // resolve the singleton of the singleton, if it exists. This case is
          // not redundant with resolveTypeMember, as it will cover the case where
          // there are no non-AttachedClass type members defined on the singleton.
          if (isGenericResolved(ctx, singleton)) {
              // Since we've resolved the singleton's AttachedClass type member, check
              // to see if there's another singleton above that must also be resolved.
              auto parent = singleton.data(ctx)->lookupSingletonClass(ctx);
              if (parent.exists()) {
                  resolveAttachedClass(ctx, singleton);
              }
          }
      }
  
      static void resolveTypeAlias(core::MutableContext ctx, core::SymbolRef lhs, ast::Send *rhs) {
          // this is provided by ResolveConstantsWalk
          ENFORCE(rhs->block);
          ENFORCE(rhs->block->body);
  
          auto allowSelfType = true;
          auto allowRebind = false;
          auto allowTypeMember = true;
          lhs.data(ctx)->resultType = TypeSyntax::getResultType(
              ctx, *(rhs->block->body), ParsedSig{}, TypeSyntaxArgs{allowSelfType, allowRebind, allowTypeMember, lhs});
      }
  
      static bool resolveJob(core::MutableContext ctx, ResolveAssignItem &job) {
          ENFORCE(job.lhs.data(ctx)->isTypeAlias() || job.lhs.data(ctx)->isTypeMember());
  
          if (isLHSResolved(ctx, job.lhs)) {
              return true;
          }
  
          auto it = std::remove_if(job.dependencies.begin(), job.dependencies.end(),
                                   [&](core::SymbolRef dep) { return isGenericResolved(ctx, dep); });
          job.dependencies.erase(it, job.dependencies.end());
          if (!job.dependencies.empty()) {
              return false;
          }
  
          if (job.lhs.data(ctx)->isTypeMember()) {
              auto superclass = job.lhs.data(ctx)->owner.data(ctx)->superClass();
              if (!isGenericResolved(ctx, superclass)) {
                  return false;
              }
  
              resolveTypeMember(ctx.withOwner(job.owner), job.lhs, job.rhs);
          } else {
              resolveTypeAlias(ctx.withOwner(job.owner), job.lhs, job.rhs);
          }
  
          return true;
      }
  
  public:
      unique_ptr<ast::ClassDef> preTransformClassDef(core::MutableContext ctx, unique_ptr<ast::ClassDef> klass) {
          // If this is a class with no type members defined, resolve attached
          // class immediately. Otherwise, it will be resolved once all type
          // members have been resolved as well.
          if (isGenericResolved(ctx, klass->symbol)) {
              resolveAttachedClass(ctx, klass->symbol);
          }
  
          return klass;
      }
  
      unique_ptr<ast::Send> preTransformSend(core::MutableContext ctx, unique_ptr<ast::Send> send) {
          switch (send->fun._id) {
              case core::Names::typeAlias()._id:
              case core::Names::typeMember()._id:
              case core::Names::typeTemplate()._id:
                  break;
  
              default:
                  extendClassOfDepth(send);
                  return send;
          }
  
          if (send->fun == core::Names::typeAlias()) {
              // don't track dependencies if this is some other method named `type_alias`
              if (!isT(send->recv)) {
                  extendClassOfDepth(send);
                  return send;
              }
          }
  
          trackDependencies_ = true;
          classOfDepth_.clear();
          dependencies_.clear();
          return send;
      }
  
      unique_ptr<ast::ConstantLit> postTransformConstantLit(core::MutableContext ctx, unique_ptr<ast::ConstantLit> lit) {
          if (trackDependencies_) {
              core::SymbolRef symbol = lit->symbol.data(ctx)->dealias(ctx);
              if (symbol == core::Symbols::T()) {
                  return lit;
              }
  
              if (symbol.data(ctx)->isClassOrModule()) {
                  // crawl up uses of `T.class_of` to find the right singleton symbol.
                  // This is for cases like `T.class_of(T.class_of(A))`.
                  for (auto it = classOfDepth_.rbegin(); it != classOfDepth_.rend() && *it; ++it) {
                      // ignore this as a potential dependency if the singleton
                      // doesn't exist -- this is an indication that there are no type
                      // members on the singleton.
                      symbol = symbol.data(ctx)->lookupSingletonClass(ctx);
                      if (!symbol.exists()) {
                          return lit;
                      }
                  }
  
                  if (!symbol.data(ctx)->typeMembers().empty()) {
                      dependencies_.emplace_back(symbol);
                  }
              } else if (symbol.data(ctx)->isTypeAlias()) {
                  dependencies_.emplace_back(symbol);
              }
          }
  
          return lit;
      }
  
      unique_ptr<ast::Send> postTransformSend(core::MutableContext ctx, unique_ptr<ast::Send> send) {
          switch (send->fun._id) {
              case core::Names::typeMember()._id:
              case core::Names::typeTemplate()._id:
              case core::Names::typeAlias()._id:
                  trackDependencies_ = false;
                  break;
  
              default:
                  if (trackDependencies_) {
                      classOfDepth_.pop_back();
                  }
                  break;
          }
  
          return send;
      }
  
      unique_ptr<ast::Assign> postTransformAssign(core::MutableContext ctx, unique_ptr<ast::Assign> asgn) {
          auto *id = ast::cast_tree<ast::ConstantLit>(asgn->lhs.get());
          if (id == nullptr || !id->symbol.exists()) {
              return asgn;
          }
  
          auto *send = ast::cast_tree<ast::Send>(asgn->rhs.get());
          if (send == nullptr) {
              return asgn;
          }
  
          auto sym = id->symbol;
          auto data = sym.data(ctx);
          if (data->isTypeAlias() || data->isTypeMember()) {
              ENFORCE(!data->isTypeMember() || send->recv->isSelfReference());
  
              // This is for a special case that happens with the generation of
              // reflection.rbi: it re-creates the type aliases of the payload,
              // without the knowledge that they are type aliases. The manifestation
              // of this, is that there are entries like:
              //
              // > module T
              // >   Boolean = T.let(nil, T.untyped)
              // > end
              if (data->isTypeAlias() && send->fun == core::Names::let()) {
                  data->resultType = core::Types::untypedUntracked();
                  return asgn;
              }
  
              ENFORCE(send->fun == core::Names::typeAlias() || send->fun == core::Names::typeMember() ||
                      send->fun == core::Names::typeTemplate());
  
              auto job = ResolveAssignItem{ctx.owner, sym, send, dependencies_};
              if (!resolveJob(ctx, job)) {
                  todoAssigns_.emplace_back(std::move(job));
              }
          }
  
          trackDependencies_ = false;
          dependencies_.clear();
          classOfDepth_.clear();
  
          return asgn;
      }
  
      static vector<ast::ParsedFile> run(core::MutableContext ctx, vector<ast::ParsedFile> trees) {
          ResolveTypeMembersWalk walk;
          Timer timeit(ctx.state.tracer(), "resolver.type_params");
  
          for (auto &tree : trees) {
              tree.tree = ast::ShallowMap::apply(ctx, walk, std::move(tree.tree));
          }
  
          // loop over any out-of-order type_member/type_alias references
          bool progress = true;
          while (progress && !walk.todoAssigns_.empty()) {
              auto origSize = walk.todoAssigns_.size();
              auto it = std::remove_if(walk.todoAssigns_.begin(), walk.todoAssigns_.end(),
                                       [&](ResolveAssignItem &job) { return resolveJob(ctx, job); });
              walk.todoAssigns_.erase(it, walk.todoAssigns_.end());
              progress = walk.todoAssigns_.size() != origSize;
          }
  
          // If there was a step with no progress, there's a cycle in the
          // type member/alias declarations. This is handled by reporting an error
          // at `typed: false`, and marking all of the involved type
          // members/aliases as T.untyped.
          if (!walk.todoAssigns_.empty()) {
              for (auto &job : walk.todoAssigns_) {
                  auto data = job.lhs.data(ctx);
  
                  if (data->isTypeMember()) {
                      data->resultType = core::make_type<core::LambdaParam>(job.lhs, core::Types::untypedUntracked(),
                                                                            core::Types::untypedUntracked());
                  } else {
                      data->resultType = core::Types::untypedUntracked();
                  }
  
                  if (auto e = ctx.state.beginError(data->loc(), core::errors::Resolver::TypeMemberCycle)) {
                      auto flavor = data->isTypeAlias() ? "alias" : "member";
                      e.setHeader("Type {} `{}` is involved in a cycle", flavor, data->show(ctx));
                  }
              }
          }
  
          return trees;
      }
  };
  
  class ResolveSignaturesWalk {
  private:
      std::vector<int> nestedBlockCounts;
  
      ast::Local *getArgLocal(core::Context ctx, const core::ArgInfo &argSym, const ast::MethodDef &mdef, int pos,
                              bool isOverloaded) {
          if (!isOverloaded) {
              return ast::MK::arg2Local(mdef.args[pos].get());
          } else {
              // we cannot rely on method and symbol arguments being aligned, as method could have more arguments.
              // we roundtrip through original symbol that is stored in mdef.
              auto internalNameToLookFor = argSym.name;
              auto originalArgIt = absl::c_find_if(mdef.symbol.data(ctx)->arguments(),
                                                   [&](const auto &arg) { return arg.name == internalNameToLookFor; });
              ENFORCE(originalArgIt != mdef.symbol.data(ctx)->arguments().end());
              auto realPos = originalArgIt - mdef.symbol.data(ctx)->arguments().begin();
              return ast::MK::arg2Local(mdef.args[realPos].get());
          }
      }
  
      void fillInInfoFromSig(core::MutableContext ctx, core::SymbolRef method, core::Loc exprLoc, ParsedSig sig,
                             bool isOverloaded, const ast::MethodDef &mdef) {
          ENFORCE(isOverloaded || mdef.symbol == method);
          ENFORCE(isOverloaded || method.data(ctx)->arguments().size() == mdef.args.size());
  
          if (!sig.seen.returns && !sig.seen.void_) {
              if (auto e = ctx.state.beginError(exprLoc, core::errors::Resolver::InvalidMethodSignature)) {
                  e.setHeader("Malformed `{}`: No return type specified. Specify one with .returns()", "sig");
              }
          }
          if (sig.seen.returns && sig.seen.void_) {
              if (auto e = ctx.state.beginError(exprLoc, core::errors::Resolver::InvalidMethodSignature)) {
                  e.setHeader("Malformed `{}`: Don't use both .returns() and .void", "sig");
              }
          }
  
          if (sig.seen.abstract) {
              method.data(ctx)->setAbstract();
          }
          if (sig.seen.incompatibleOverride) {
              method.data(ctx)->setIncompatibleOverride();
          }
          if (!sig.typeArgs.empty()) {
              method.data(ctx)->setGenericMethod();
              for (auto &typeSpec : sig.typeArgs) {
                  if (typeSpec.type) {
                      auto name = ctx.state.freshNameUnique(core::UniqueNameKind::TypeVarName, typeSpec.name, 1);
                      auto sym = ctx.state.enterTypeArgument(typeSpec.loc, method, name, core::Variance::CoVariant);
                      auto asTypeVar = core::cast_type<core::TypeVar>(typeSpec.type.get());
                      ENFORCE(asTypeVar != nullptr);
                      asTypeVar->sym = sym;
                      sym.data(ctx)->resultType = typeSpec.type;
                  }
              }
          }
          if (sig.seen.overridable) {
              method.data(ctx)->setOverridable();
          }
          if (sig.seen.override_) {
              method.data(ctx)->setOverride();
          }
          if (sig.seen.final) {
              method.data(ctx)->setFinalMethod();
          }
          if (sig.seen.bind) {
              method.data(ctx)->setReBind(sig.bind);
          }
  
          // Get the parameters order from the signature
          vector<ParsedSig::ArgSpec> sigParams;
          for (auto &spec : sig.argTypes) {
              sigParams.push_back(spec);
          }
  
          vector<ast::Local *> defParams; // Parameters order from the method declaration
          bool seenOptional = false;
  
          auto methodInfo = method.data(ctx);
          methodInfo->resultType = sig.returns;
          int i = -1;
          for (auto &arg : methodInfo->arguments()) {
              ++i;
              const auto local = getArgLocal(ctx, arg, mdef, i, isOverloaded);
              auto treeArgName = local->localVariable._name;
              ENFORCE(local != nullptr);
  
              // Check that optional keyword parameters are after all the required ones
              bool isKwd = arg.flags.isKeyword;
              bool isReq = !arg.flags.isBlock && !arg.flags.isRepeated && !arg.flags.isDefault;
              if (isKwd && !isReq) {
                  seenOptional = true;
              } else if (isKwd && seenOptional && isReq) {
                  if (auto e = ctx.state.beginError(arg.loc, core::errors::Resolver::BadParameterOrdering)) {
                      e.setHeader("Malformed `{}`. Required parameter `{}` must be declared before all the optional ones",
                                  "sig", treeArgName.show(ctx));
                      e.addErrorLine(exprLoc, "Signature");
                  }
              }
  
              defParams.push_back(local);
  
              auto spec = absl::c_find_if(sig.argTypes, [&](const auto &spec) { return spec.name == treeArgName; });
  
              if (spec != sig.argTypes.end()) {
                  ENFORCE(spec->type != nullptr);
                  arg.type = spec->type;
                  arg.loc = spec->loc;
                  arg.rebind = spec->rebind;
                  sig.argTypes.erase(spec);
              } else {
                  if (arg.type == nullptr) {
                      arg.type = core::Types::untyped(ctx, method);
                  }
  
                  // We silence the "type not specified" error when a sig does not mention the synthesized block arg.
                  bool isBlkArg = arg.name == core::Names::blkArg();
                  if (!isOverloaded && !isBlkArg && (sig.seen.params || sig.seen.returns || sig.seen.void_)) {
                      // Only error if we have any types
                      if (auto e = ctx.state.beginError(arg.loc, core::errors::Resolver::InvalidMethodSignature)) {
                          e.setHeader("Malformed `{}`. Type not specified for argument `{}`", "sig",
                                      treeArgName.show(ctx));
                          e.addErrorLine(exprLoc, "Signature");
                      }
                  }
              }
  
              if (isOverloaded && arg.flags.isKeyword) {
                  if (auto e = ctx.state.beginError(arg.loc, core::errors::Resolver::InvalidMethodSignature)) {
                      e.setHeader("Malformed `{}`. Overloaded functions cannot have keyword arguments:  `{}`", "sig",
                                  treeArgName.show(ctx));
                  }
              }
          }
  
          for (auto spec : sig.argTypes) {
              if (auto e = ctx.state.beginError(spec.loc, core::errors::Resolver::InvalidMethodSignature)) {
                  e.setHeader("Unknown argument name `{}`", spec.name.show(ctx));
              }
          }
  
          // Check params ordering match between signature and definition
          if (sig.argTypes.empty()) {
              int j = 0;
              for (auto spec : sigParams) {
                  auto param = defParams[j];
                  auto sname = spec.name.show(ctx);
                  auto dname = param->localVariable._name.show(ctx);
                  if (sname != dname) {
                      if (auto e = ctx.state.beginError(param->loc, core::errors::Resolver::BadParameterOrdering)) {
                          e.setHeader("Bad parameter ordering for `{}`, expected `{}` instead", dname, sname);
                          e.addErrorLine(spec.loc, "Expected index in signature:");
                      }
                  }
                  j++;
              }
          }
      }
  
      // Force errors from any signatures that didn't attach to methods.
      // `lastSigs` will always be empty after this function is called.
      void processLeftoverSigs(core::MutableContext ctx, InlinedVector<ast::Send *, 1> &lastSigs) {
          if (!lastSigs.empty()) {
              // These sigs won't have been parsed, as there was no methods to
              // attach them to -- parse them here manually to force any errors.
              for (auto sig : lastSigs) {
                  auto allowSelfType = true;
                  auto allowRebind = false;
                  auto allowTypeMember = true;
                  TypeSyntax::parseSig(
                      ctx, sig, nullptr,
                      TypeSyntaxArgs{allowSelfType, allowRebind, allowTypeMember, core::Symbols::untyped()});
              }
  
              if (auto e = ctx.state.beginError(lastSigs[0]->loc, core::errors::Resolver::InvalidMethodSignature)) {
                  e.setHeader("Malformed `{}`. No method def following it", "sig");
              }
  
              lastSigs.clear();
          }
      }
  
      void processClassBody(core::MutableContext ctx, unique_ptr<ast::ClassDef> &klass) {
          InlinedVector<ast::Send *, 1> lastSigs;
          for (auto &stat : klass->rhs) {
              processStatement(ctx, stat, lastSigs);
          }
  
          processLeftoverSigs(ctx, lastSigs);
  
          auto toRemove = remove_if(klass->rhs.begin(), klass->rhs.end(),
                                    [](unique_ptr<ast::Expression> &stat) -> bool { return stat.get() == nullptr; });
          klass->rhs.erase(toRemove, klass->rhs.end());
      }
  
      void processInSeq(core::MutableContext ctx, unique_ptr<ast::InsSeq> &seq) {
          InlinedVector<ast::Send *, 1> lastSigs;
  
          // Explicitly check in the contxt of the class, not <static-init>
          auto classCtx = ctx.withOwner(ctx.owner.data(ctx)->enclosingClass(ctx));
  
          for (auto &stat : seq->stats) {
              processStatement(classCtx, stat, lastSigs);
          }
          if (!ast::isa_tree<ast::EmptyTree>(seq->expr.get())) {
              processStatement(classCtx, seq->expr, lastSigs);
          }
  
          processLeftoverSigs(classCtx, lastSigs);
  
          auto toRemove = remove_if(seq->stats.begin(), seq->stats.end(),
                                    [](unique_ptr<ast::Expression> &stat) -> bool { return stat.get() == nullptr; });
          seq->stats.erase(toRemove, seq->stats.end());
      }
  
      void processStatement(core::MutableContext ctx, unique_ptr<ast::Expression> &stat,
                            InlinedVector<ast::Send *, 1> &lastSigs) {
          typecase(
              stat.get(),
  
              [&](ast::Send *send) {
                  if (TypeSyntax::isSig(ctx, send)) {
                      if (!lastSigs.empty()) {
                          if (!ctx.permitOverloadDefinitions(send->loc.file())) {
                              if (auto e = ctx.state.beginError(lastSigs[0]->loc,
                                                                core::errors::Resolver::OverloadNotAllowed)) {
                                  e.setHeader("Unused type annotation. No method def before next annotation");
                                  e.addErrorLine(send->loc, "Type annotation that will be used instead");
                              }
                          }
                      }
  
                      lastSigs.emplace_back(send);
                      return;
                  }
              },
  
              [&](ast::MethodDef *mdef) {
                  if (debug_mode) {
                      bool hasSig = !lastSigs.empty();
                      bool rewriten = mdef->isRewriterSynthesized();
                      bool isRBI = mdef->loc.file().data(ctx).isRBI();
                      if (hasSig) {
                          categoryCounterInc("method.sig", "true");
                      } else {
                          categoryCounterInc("method.sig", "false");
                      }
                      if (rewriten) {
                          categoryCounterInc("method.dsl", "true");
                      } else {
                          categoryCounterInc("method.dsl", "false");
                      }
                      if (isRBI) {
                          categoryCounterInc("method.rbi", "true");
                      } else {
                          categoryCounterInc("method.rbi", "false");
                      }
                      if (hasSig && !isRBI && !rewriten) {
                          counterInc("types.sig.human");
                      }
                  }
  
                  if (!lastSigs.empty()) {
                      prodCounterInc("types.sig.count");
  
                      auto loc = lastSigs[0]->loc;
                      if (loc.file().data(ctx).originalSigil == core::StrictLevel::None &&
                          !lastSigs.front()->isRewriterSynthesized()) {
                          if (auto e = ctx.state.beginError(loc, core::errors::Resolver::SigInFileWithoutSigil)) {
                              e.setHeader("To use `{}`, this file must declare an explicit `{}` sigil (found: "
                                          "none). If you're not sure which one to use, start with `{}`",
                                          "sig", "# typed:", "# typed: false");
                          }
                      }
  
                      bool isOverloaded = lastSigs.size() > 1 && ctx.permitOverloadDefinitions(loc.file());
                      auto originalName = mdef->symbol.data(ctx)->name;
                      if (isOverloaded) {
                          ctx.state.mangleRenameSymbol(mdef->symbol, originalName);
                      }
                      int i = 0;
  
                      // process signatures in the context of either the current
                      // class, or the current singleton class, depending on if
                      // the current method is a self method.
                      core::SymbolRef sigOwner;
                      if (mdef->isSelf()) {
                          sigOwner = ctx.owner.data(ctx)->singletonClass(ctx);
                      } else {
                          sigOwner = ctx.owner;
                      }
  
                      while (i < lastSigs.size()) {
                          auto allowSelfType = true;
                          auto allowRebind = false;
                          auto allowTypeMember = true;
                          auto sig = TypeSyntax::parseSig(
                              ctx.withOwner(sigOwner), ast::cast_tree<ast::Send>(lastSigs[i]), nullptr,
                              TypeSyntaxArgs{allowSelfType, allowRebind, allowTypeMember, mdef->symbol});
                          core::SymbolRef overloadSym;
                          if (isOverloaded) {
                              vector<int> argsToKeep;
                              int argId = -1;
                              for (auto &argTree : mdef->args) {
                                  argId++;
                                  const auto local = ast::MK::arg2Local(argTree.get());
                                  auto treeArgName = local->localVariable._name;
                                  ENFORCE(local != nullptr);
                                  auto spec =
                                      absl::c_find_if(sig.argTypes, [&](auto &spec) { return spec.name == treeArgName; });
                                  if (spec != sig.argTypes.end()) {
                                      argsToKeep.emplace_back(argId);
                                  }
                              }
                              overloadSym = ctx.state.enterNewMethodOverload(lastSigs[i]->loc, mdef->symbol, originalName,
                                                                             i, argsToKeep);
                              if (i != lastSigs.size() - 1) {
                                  overloadSym.data(ctx)->setOverloaded();
                              }
                          } else {
                              overloadSym = mdef->symbol;
                          }
                          fillInInfoFromSig(ctx, overloadSym, lastSigs[i]->loc, move(sig), isOverloaded, *mdef);
                          i++;
                      }
  
                      // OVERLOAD
                      lastSigs.clear();
                  }
  
                  if (mdef->symbol.data(ctx)->isAbstract()) {
                      if (!ast::isa_tree<ast::EmptyTree>(mdef->rhs.get())) {
                          if (auto e =
                                  ctx.state.beginError(mdef->rhs->loc, core::errors::Resolver::AbstractMethodWithBody)) {
                              e.setHeader("Abstract methods must not contain any code in their body");
                              e.replaceWith("Delete the body", mdef->rhs->loc, "");
                          }
  
                          mdef->rhs = ast::MK::EmptyTree();
                      }
                      if (!mdef->symbol.data(ctx)->enclosingClass(ctx).data(ctx)->isClassOrModuleAbstract()) {
                          if (auto e = ctx.state.beginError(mdef->loc,
                                                            core::errors::Resolver::AbstractMethodOutsideAbstract)) {
                              e.setHeader("Before declaring an abstract method, you must mark your class/module "
                                          "as abstract using `abstract!` or `interface!`");
                          }
                      }
                  } else if (mdef->symbol.data(ctx)->enclosingClass(ctx).data(ctx)->isClassOrModuleInterface()) {
                      if (auto e = ctx.state.beginError(mdef->loc, core::errors::Resolver::ConcreteMethodInInterface)) {
                          e.setHeader("All methods in an interface must be declared abstract");
                      }
                  }
              },
              [&](ast::ClassDef *cdef) {
                  // Leave in place
              },
  
              [&](ast::EmptyTree *e) { stat.reset(nullptr); },
  
              [&](ast::Expression *e) {});
      }
  
      // Resolve the type of the rhs of a constant declaration. This logic is
      // extremely simplistic; We only handle simple literals, and explicit casts.
      //
      // We don't handle array or hash literals, because intuiting the element
      // type (once we have generics) will be nontrivial.
      core::TypePtr resolveConstantType(core::Context ctx, unique_ptr<ast::Expression> &expr, core::SymbolRef ofSym) {
          core::TypePtr result;
          typecase(
              expr.get(), [&](ast::Literal *a) { result = a->value; },
              [&](ast::Cast *cast) {
                  if (cast->cast != core::Names::let()) {
                      if (auto e = ctx.state.beginError(cast->loc, core::errors::Resolver::ConstantAssertType)) {
                          e.setHeader("Use `{}` to specify the type of constants", "T.let");
                      }
                  }
                  result = cast->type;
              },
              [&](ast::InsSeq *outer) { result = resolveConstantType(ctx, outer->expr, ofSym); },
              [&](ast::Expression *expr) {});
          return result;
      }
  
      bool handleDeclaration(core::MutableContext ctx, unique_ptr<ast::Assign> &asgn) {
          auto *uid = ast::cast_tree<ast::UnresolvedIdent>(asgn->lhs.get());
          if (uid == nullptr) {
              return false;
          }
  
          if (uid->kind != ast::UnresolvedIdent::Kind::Instance && uid->kind != ast::UnresolvedIdent::Kind::Class) {
              return false;
          }
          ast::Expression *recur = asgn->rhs.get();
          while (auto outer = ast::cast_tree<ast::InsSeq>(recur)) {
              recur = outer->expr.get();
          }
  
          auto *cast = ast::cast_tree<ast::Cast>(recur);
          if (cast == nullptr) {
              return false;
          } else if (cast->cast != core::Names::let()) {
              if (auto e = ctx.state.beginError(cast->loc, core::errors::Resolver::ConstantAssertType)) {
                  e.setHeader("Use `{}` to specify the type of constants", "T.let");
              }
          }
  
          core::SymbolRef scope;
          if (uid->kind == ast::UnresolvedIdent::Kind::Class) {
              if (!ctx.owner.data(ctx)->isClassOrModule()) {
                  if (auto e = ctx.state.beginError(uid->loc, core::errors::Resolver::InvalidDeclareVariables)) {
                      e.setHeader("The class variable `{}` must be declared at class scope", uid->name.show(ctx));
                  }
              }
  
              scope = ctx.owner.data(ctx)->enclosingClass(ctx);
          } else {
              // we need to check nested block counts because we want all fields to be declared on top level of either
              // class or body, rather then nested in some block
              if (nestedBlockCounts.back() == 0 && ctx.owner.data(ctx)->isClassOrModule()) {
                  // Declaring a class instance variable
              } else if (nestedBlockCounts.back() == 0 && ctx.owner.data(ctx)->name == core::Names::initialize()) {
                  // Declaring a instance variable
              } else if (ctx.owner.data(ctx)->isMethod() && ctx.owner.data(ctx)->owner.data(ctx)->isSingletonClass(ctx) &&
                         !core::Types::isSubType(ctx, core::Types::nilClass(), cast->type)) {
                  // Declaring a class instance variable in a static method
                  if (auto e = ctx.state.beginError(uid->loc, core::errors::Resolver::InvalidDeclareVariables)) {
                      e.setHeader("The singleton instance variable `{}` must be declared inside the class body or "
                                  "declared nilable",
                                  uid->name.show(ctx));
                  }
              } else if (!core::Types::isSubType(ctx, core::Types::nilClass(), cast->type)) {
                  // Inside a method; declaring a normal instance variable
                  if (auto e = ctx.state.beginError(uid->loc, core::errors::Resolver::InvalidDeclareVariables)) {
                      e.setHeader("The instance variable `{}` must be declared inside `{}` or declared nilable",
                                  uid->name.show(ctx), "initialize");
                  }
              }
              scope = ctx.selfClass();
          }
  
          auto prior = scope.data(ctx)->findMember(ctx, uid->name);
          if (prior.exists()) {
              if (core::Types::equiv(ctx, prior.data(ctx)->resultType, cast->type)) {
                  // We already have a symbol for this field, and it matches what we already saw, so we can short
                  // circuit.
                  return true;
              } else {
                  // We do some normalization here to ensure that the file / line we report the error on doesn't
                  // depend on the order that we traverse files nor the order we traverse within a file.
                  auto priorLoc = prior.data(ctx)->loc();
                  core::Loc reportOn;
                  core::Loc errorLine;
                  if (uid->loc.file() == priorLoc.file()) {
                      reportOn = uid->loc.beginPos() < priorLoc.beginPos() ? uid->loc : priorLoc;
                      errorLine = uid->loc.beginPos() < priorLoc.beginPos() ? priorLoc : uid->loc;
                  } else {
                      reportOn = uid->loc.file() < priorLoc.file() ? uid->loc : priorLoc;
                      errorLine = uid->loc.file() < priorLoc.file() ? priorLoc : uid->loc;
                  }
  
                  if (auto e = ctx.state.beginError(reportOn, core::errors::Resolver::DuplicateVariableDeclaration)) {
                      e.setHeader("Redeclaring variable `{}` with mismatching type", uid->name.data(ctx)->show(ctx));
                      e.addErrorLine(errorLine, "Previous declaration is here:");
                  }
                  return false;
              }
          }
          core::SymbolRef var;
  
          if (uid->kind == ast::UnresolvedIdent::Kind::Class) {
              var = ctx.state.enterStaticFieldSymbol(uid->loc, scope, uid->name);
          } else {
              var = ctx.state.enterFieldSymbol(uid->loc, scope, uid->name);
          }
  
          var.data(ctx)->resultType = cast->type;
          return true;
      }
  
      core::SymbolRef methodOwner(core::Context ctx) {
          core::SymbolRef owner = ctx.owner.data(ctx)->enclosingClass(ctx);
          if (owner == core::Symbols::root()) {
              // Root methods end up going on object
              owner = core::Symbols::Object();
          }
          return owner;
      }
  
  public:
      ResolveSignaturesWalk() {
          nestedBlockCounts.emplace_back(0);
      }
  
      unique_ptr<ast::Assign> postTransformAssign(core::MutableContext ctx, unique_ptr<ast::Assign> asgn) {
          if (handleDeclaration(ctx, asgn)) {
              return asgn;
          }
  
          auto *id = ast::cast_tree<ast::ConstantLit>(asgn->lhs.get());
          if (id == nullptr || !id->symbol.exists()) {
              return asgn;
          }
  
          auto sym = id->symbol;
          auto data = sym.data(ctx);
          if (data->isTypeAlias() || data->isTypeMember()) {
              return asgn;
          }
  
          if (data->isStaticField()) {
              if (data->resultType == nullptr) {
                  data->resultType = resolveConstantType(ctx, asgn->rhs, sym);
                  if (data->resultType == nullptr) {
                      // Instead of emitting an error now, emit an error in infer that has a proper type suggestion
                      auto rhs = move(asgn->rhs);
                      auto loc = rhs->loc;
                      asgn->rhs = ast::MK::Send1(loc, ast::MK::Constant(loc, core::Symbols::Magic()),
                                                 core::Names::suggestType(), move(rhs));
                  }
              } else if (!core::isa_type<core::AliasType>(data->resultType.get())) {
                  // If we've already resolved a temporary constant, we still want to run resolveConstantType to
                  // report errors (e.g. so that a stand-in untyped value won't suppress errors in subsequent
                  // typechecking runs) but we only want to run this on constants that are value-level and not class
                  // or type aliases. The check for isa_type<AliasType> makes sure that we skip aliases of the form `X
                  // = Integer` and only run this over constant value assignments like `X = 5` or `Y = 5; X = Y`.
                  if (resolveConstantType(ctx, asgn->rhs, sym) == nullptr) {
                      if (auto e = ctx.state.beginError(asgn->rhs->loc,
                                                        core::errors::Resolver::ConstantMissingTypeAnnotation)) {
                          e.setHeader("Constants must have type annotations with `{}` when specifying `{}`", "T.let",
                                      "# typed: strict");
                      }
                  }
              }
          }
  
          return asgn;
      }
  
      unique_ptr<ast::ClassDef> preTransformClassDef(core::Context ctx, unique_ptr<ast::ClassDef> original) {
          nestedBlockCounts.emplace_back(0);
          return original;
      }
  
      unique_ptr<ast::Expression> postTransformClassDef(core::MutableContext ctx, unique_ptr<ast::ClassDef> original) {
          processClassBody(ctx.withOwner(original->symbol), original);
          return original;
      }
  
      unique_ptr<ast::MethodDef> preTransformMethodDef(core::Context ctx, unique_ptr<ast::MethodDef> original) {
          nestedBlockCounts.emplace_back(0);
          return original;
      }
  
      unique_ptr<ast::Expression> postTransformMethodDef(core::Context ctx, unique_ptr<ast::MethodDef> original) {
          nestedBlockCounts.pop_back();
          return original;
      }
  
      unique_ptr<ast::Block> preTransformBlock(core::Context ctx, unique_ptr<ast::Block> block) {
          nestedBlockCounts.back() += 1;
          return block;
      }
  
      unique_ptr<ast::Expression> postTransformBlock(core::Context ctx, unique_ptr<ast::Block> block) {
          nestedBlockCounts.back() -= 1;
          return block;
      }
  
      unique_ptr<ast::Expression> postTransformInsSeq(core::MutableContext ctx, unique_ptr<ast::InsSeq> original) {
          processInSeq(ctx, original);
          return original;
      }
  
      unique_ptr<ast::Expression> postTransformSend(core::MutableContext ctx, unique_ptr<ast::Send> send) {
          if (auto *id = ast::cast_tree<ast::ConstantLit>(send->recv.get())) {
              if (id->symbol != core::Symbols::T()) {
                  return send;
              }
              switch (send->fun._id) {
                  case core::Names::let()._id:
                  case core::Names::assertType()._id:
                  case core::Names::cast()._id: {
                      if (send->args.size() < 2) {
                          return send;
                      }
  
                      // Compute the containing class when translating the type,
                      // as there's a very good chance this has been called from a
                      // method context.
                      core::SymbolRef ownerClass = ctx.owner.data(ctx)->enclosingClass(ctx);
  
                      auto expr = std::move(send->args[0]);
                      ParsedSig emptySig;
                      auto allowSelfType = true;
                      auto allowRebind = false;
                      auto allowTypeMember = true;
                      auto type = TypeSyntax::getResultType(
                          ctx.withOwner(ownerClass), *(send->args[1]), emptySig,
                          TypeSyntaxArgs{allowSelfType, allowRebind, allowTypeMember, core::Symbols::noSymbol()});
                      return ast::MK::InsSeq1(send->loc, ast::MK::KeepForTypechecking(std::move(send->args[1])),
                                              make_unique<ast::Cast>(send->loc, type, std::move(expr), send->fun));
                  }
                  case core::Names::revealType()._id:
                      // This error does not match up with our "upper error levels are super sets
                      // of errors from lower levels" claim. This is ONLY an error in lower levels.
                      if (send->loc.file().data(ctx).strictLevel <= core::StrictLevel::False) {
                          if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::RevealTypeInUntypedFile)) {
                              e.setHeader("`{}` can only reveal types in `{}` files (or higher)", "T.reveal_type",
                                          "# typed: true");
                          }
                      }
                      return send;
                  default:
                      return send;
              }
          } else if (send->recv.get()->isSelfReference()) {
              if (send->fun != core::Names::aliasMethod()) {
                  return send;
              }
  
              vector<core::NameRef> args;
              for (auto &arg : send->args) {
                  auto lit = ast::cast_tree<ast::Literal>(arg.get());
                  if (lit == nullptr || !lit->isSymbol(ctx)) {
                      continue;
                  }
                  core::NameRef name = lit->asSymbol(ctx);
  
                  args.emplace_back(name);
              }
              if (send->args.size() != 2) {
                  return send;
              }
              if (args.size() != 2) {
                  return send;
              }
  
              auto fromName = args[0];
              auto toName = args[1];
  
              auto owner = methodOwner(ctx);
              core::SymbolRef toMethod = owner.data(ctx)->findMemberNoDealias(ctx, toName);
              if (toMethod.exists()) {
                  toMethod = toMethod.data(ctx)->dealiasMethod(ctx);
              }
  
              if (!toMethod.exists()) {
                  if (auto e = ctx.state.beginError(send->args[1]->loc, core::errors::Resolver::BadAliasMethod)) {
                      e.setHeader("Can't make method alias from `{}` to non existing method `{}`", fromName.show(ctx),
                                  toName.show(ctx));
                  }
                  toMethod = core::Symbols::Sorbet_Private_Static_badAliasMethodStub();
              }
  
              core::SymbolRef fromMethod = owner.data(ctx)->findMemberNoDealias(ctx, fromName);
              if (fromMethod.exists() && fromMethod.data(ctx)->dealiasMethod(ctx) != toMethod) {
                  if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::BadAliasMethod)) {
                      auto dealiased = fromMethod.data(ctx)->dealiasMethod(ctx);
                      if (fromMethod == dealiased) {
                          e.setHeader("Redefining the existing method `{}` as a method alias",
                                      fromMethod.data(ctx)->show(ctx));
                          e.addErrorLine(fromMethod.data(ctx)->loc(), "Previous definition");
                      } else {
                          e.setHeader("Redefining method alias `{}` from `{}` to `{}`", fromMethod.data(ctx)->show(ctx),
                                      dealiased.data(ctx)->show(ctx), toMethod.data(ctx)->show(ctx));
                          e.addErrorLine(fromMethod.data(ctx)->loc(), "Previous alias definition");
                          e.addErrorLine(dealiased.data(ctx)->loc(), "Previous alias pointed to");
                          e.addErrorLine(toMethod.data(ctx)->loc(), "Redefining alias to");
                      }
                  }
                  return send;
              }
  
              // No need to make an alias when they're already the same symbol.
              if (fromMethod == toMethod) {
                  return send;
              }
  
              core::SymbolRef alias = ctx.state.enterMethodSymbol(send->loc, owner, fromName);
              alias.data(ctx)->resultType = core::make_type<core::AliasType>(toMethod);
  
              return send;
          } else {
              return send;
          }
      }
  };
  
  class ResolveMixesInClassMethodsWalk {
      void processMixesInClassMethods(core::MutableContext ctx, ast::Send *send) {
          if (!ctx.owner.data(ctx)->isClassOrModule() || !ctx.owner.data(ctx)->isClassOrModuleModule()) {
              if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::InvalidMixinDeclaration)) {
                  e.setHeader("`{}` can only be declared inside a module, not a class", send->fun.data(ctx)->show(ctx));
              }
              // Keep processing it anyways
          }
  
          if (send->args.size() != 1) {
              if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::InvalidMixinDeclaration)) {
                  e.setHeader("Wrong number of arguments to `{}`: Expected: `{}`, got: `{}`",
                              send->fun.data(ctx)->show(ctx), 1, send->args.size());
              }
              return;
          }
          auto *front = send->args.front().get();
          auto *id = ast::cast_tree<ast::ConstantLit>(front);
          if (id == nullptr || !id->symbol.exists() || !id->symbol.data(ctx)->isClassOrModule()) {
              if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::InvalidMixinDeclaration)) {
                  e.setHeader("Argument to `{}` must be statically resolvable to a module",
                              send->fun.data(ctx)->show(ctx));
              }
              return;
          }
          if (id->symbol.data(ctx)->isClassOrModuleClass()) {
              if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::InvalidMixinDeclaration)) {
                  e.setHeader("`{}` is a class, not a module; Only modules may be mixins",
                              id->symbol.data(ctx)->show(ctx));
              }
              return;
          }
          if (id->symbol == ctx.owner) {
              if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::InvalidMixinDeclaration)) {
                  e.setHeader("Must not pass your self to `{}`", send->fun.data(ctx)->show(ctx));
              }
              return;
          }
          auto existing = ctx.owner.data(ctx)->findMember(ctx, core::Names::classMethods());
          if (existing.exists() && existing != id->symbol) {
              if (auto e = ctx.state.beginError(send->loc, core::errors::Resolver::InvalidMixinDeclaration)) {
                  e.setHeader("Redeclaring `{}` from module `{}` to module `{}`", send->fun.data(ctx)->show(ctx),
                              existing.data(ctx)->show(ctx), id->symbol.data(ctx)->show(ctx));
              }
              return;
          }
          ctx.owner.data(ctx)->members()[core::Names::classMethods()] = id->symbol;
      }
  
  public:
      unique_ptr<ast::Expression> postTransformSend(core::MutableContext ctx, unique_ptr<ast::Send> original) {
          if (original->recv->isSelfReference() && original->fun == core::Names::mixesInClassMethods()) {
              processMixesInClassMethods(ctx, original.get());
              return ast::MK::EmptyTree();
          }
          return original;
      }
  };
  
  class ResolveSanityCheckWalk {
  public:
      unique_ptr<ast::Expression> postTransformClassDef(core::MutableContext ctx, unique_ptr<ast::ClassDef> original) {
          ENFORCE(original->symbol != core::Symbols::todo(), "These should have all been resolved: {}",
                  original->toString(ctx));
          if (original->symbol == core::Symbols::root()) {
              ENFORCE(ctx.state.lookupStaticInitForFile(original->loc).exists());
          } else {
              ENFORCE(ctx.state.lookupStaticInitForClass(original->symbol).exists());
          }
          return original;
      }
      unique_ptr<ast::Expression> postTransformMethodDef(core::MutableContext ctx, unique_ptr<ast::MethodDef> original) {
          ENFORCE(original->symbol != core::Symbols::todo(), "These should have all been resolved: {}",
                  original->toString(ctx));
          return original;
      }
      unique_ptr<ast::Expression> postTransformUnresolvedConstantLit(core::MutableContext ctx,
                                                                     unique_ptr<ast::UnresolvedConstantLit> original) {
          ENFORCE(false, "These should have all been removed: {}", original->toString(ctx));
          return original;
      }
      unique_ptr<ast::Expression> postTransformUnresolvedIdent(core::MutableContext ctx,
                                                               unique_ptr<ast::UnresolvedIdent> original) {
          ENFORCE(original->kind != ast::UnresolvedIdent::Kind::Local, "{} should have been removed by local_vars",
                  original->toString(ctx));
          return original;
      }
      unique_ptr<ast::ConstantLit> postTransformConstantLit(core::MutableContext ctx,
                                                            unique_ptr<ast::ConstantLit> original) {
          ENFORCE(ResolveConstantsWalk::isAlreadyResolved(ctx, *original));
          return original;
      }
  };
  }; // namespace
  
  ast::ParsedFilesOrCancelled Resolver::run(core::MutableContext ctx, vector<ast::ParsedFile> trees,
                                            WorkerPool &workers) {
      trees = ResolveConstantsWalk::resolveConstants(ctx, std::move(trees), workers);
      if (ctx.state.wasTypecheckingCanceled()) {
          return ast::ParsedFilesOrCancelled();
      }
      finalizeAncestors(ctx.state);
      if (ctx.state.wasTypecheckingCanceled()) {
          return ast::ParsedFilesOrCancelled();
      }
      trees = resolveMixesInClassMethods(ctx, std::move(trees));
      if (ctx.state.wasTypecheckingCanceled()) {
          return ast::ParsedFilesOrCancelled();
      }
      finalizeSymbols(ctx.state);
      if (ctx.state.wasTypecheckingCanceled()) {
          return ast::ParsedFilesOrCancelled();
      }
      trees = ResolveTypeMembersWalk::run(ctx, std::move(trees));
      if (ctx.state.wasTypecheckingCanceled()) {
          return ast::ParsedFilesOrCancelled();
      }
      trees = resolveSigs(ctx, std::move(trees));
      if (ctx.state.wasTypecheckingCanceled()) {
          return ast::ParsedFilesOrCancelled();
      }
      sanityCheck(ctx, trees);
  
      return ast::ParsedFilesOrCancelled(move(trees));
  }
  
  vector<ast::ParsedFile> Resolver::resolveSigs(core::MutableContext ctx, vector<ast::ParsedFile> trees) {
      ResolveSignaturesWalk sigs;
      Timer timeit(ctx.state.tracer(), "resolver.sigs_vars_and_flatten");
      for (auto &tree : trees) {
          tree.tree = ast::TreeMap::apply(ctx, sigs, std::move(tree.tree));
      }
  
      return trees;
  }
  
  vector<ast::ParsedFile> Resolver::resolveMixesInClassMethods(core::MutableContext ctx, vector<ast::ParsedFile> trees) {
      ResolveMixesInClassMethodsWalk mixesInClassMethods;
      Timer timeit(ctx.state.tracer(), "resolver.mixes_in_class_methods");
      for (auto &tree : trees) {
          tree.tree = ast::TreeMap::apply(ctx, mixesInClassMethods, std::move(tree.tree));
      }
      return trees;
  }
  
  void Resolver::sanityCheck(core::MutableContext ctx, vector<ast::ParsedFile> &trees) {
      if (debug_mode) {
          Timer timeit(ctx.state.tracer(), "resolver.sanity_check");
          ResolveSanityCheckWalk sanity;
          for (auto &tree : trees) {
              tree.tree = ast::TreeMap::apply(ctx, sanity, std::move(tree.tree));
          }
      }
  }
  
  vector<ast::ParsedFile> Resolver::runTreePasses(core::MutableContext ctx, vector<ast::ParsedFile> trees) {
      auto workers = WorkerPool::create(0, ctx.state.tracer());
      trees = ResolveConstantsWalk::resolveConstants(ctx, std::move(trees), *workers);
      trees = resolveMixesInClassMethods(ctx, std::move(trees));
      computeLinearization(ctx.state);
      trees = ResolveTypeMembersWalk::run(ctx, std::move(trees));
      trees = resolveSigs(ctx, std::move(trees));
      sanityCheck(ctx, trees);
      // This check is FAR too slow to run on large codebases, especially with sanitizers on.
      // But it can be super useful to uncomment when debugging certain issues.
      // ctx.state.sanityCheck();
  
      return trees;
  }
  
  vector<ast::ParsedFile> Resolver::runConstantResolution(core::MutableContext ctx, vector<ast::ParsedFile> trees,
                                                          WorkerPool &workers) {
      trees = ResolveConstantsWalk::resolveConstants(ctx, std::move(trees), workers);
      sanityCheck(ctx, trees);
  
      return trees;
  }
  
  } // namespace sorbet::resolver
  