carbon-lang/toolchain/check/context.cpp

// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#include "toolchain/check/context.h"

#include <string>
#include <utility>

#include "common/check.h"
#include "common/vlog.h"
#include "llvm/ADT/Sequence.h"
#include "toolchain/base/kind_switch.h"
#include "toolchain/check/decl_name_stack.h"
#include "toolchain/check/eval.h"
#include "toolchain/check/generic_region_stack.h"
#include "toolchain/check/import_ref.h"
#include "toolchain/check/inst_block_stack.h"
#include "toolchain/check/merge.h"
#include "toolchain/diagnostics/diagnostic_emitter.h"
#include "toolchain/lex/tokenized_buffer.h"
#include "toolchain/parse/node_ids.h"
#include "toolchain/parse/node_kind.h"
#include "toolchain/sem_ir/builtin_kind.h"
#include "toolchain/sem_ir/file.h"
#include "toolchain/sem_ir/ids.h"
#include "toolchain/sem_ir/import_ir.h"
#include "toolchain/sem_ir/inst.h"
#include "toolchain/sem_ir/inst_kind.h"
#include "toolchain/sem_ir/name_scope.h"
#include "toolchain/sem_ir/typed_insts.h"

namespace Carbon::Check {

Context::Context(const Lex::TokenizedBuffer& tokens, DiagnosticEmitter& emitter,
                 const Parse::Tree& parse_tree, SemIR::File& sem_ir,
                 llvm::raw_ostream* vlog_stream)
    : tokens_(&tokens),
      emitter_(&emitter),
      parse_tree_(&parse_tree),
      sem_ir_(&sem_ir),
      vlog_stream_(vlog_stream),
      node_stack_(parse_tree, vlog_stream),
      inst_block_stack_("inst_block_stack_", sem_ir, vlog_stream),
      param_and_arg_refs_stack_(sem_ir, vlog_stream, node_stack_),
      args_type_info_stack_("args_type_info_stack_", sem_ir, vlog_stream),
      decl_name_stack_(this),
      scope_stack_(sem_ir_->identifiers()) {
  // Map the builtin `<error>` and `type` type constants to their corresponding
  // special `TypeId` values.
  type_ids_for_type_constants_.Insert(
      SemIR::ConstantId::ForTemplateConstant(SemIR::InstId::BuiltinError),
      SemIR::TypeId::Error);
  type_ids_for_type_constants_.Insert(
      SemIR::ConstantId::ForTemplateConstant(SemIR::InstId::BuiltinTypeType),
      SemIR::TypeId::TypeType);

  // TODO: Remove this and add a `VerifyOnFinish` once we properly push and pop
  // in the right places.
  generic_region_stack().Push();
}

auto Context::TODO(SemIRLoc loc, std::string label) -> bool {
  CARBON_DIAGNOSTIC(SemanticsTodo, Error, "Semantics TODO: `{0}`.",
                    std::string);
  emitter_->Emit(loc, SemanticsTodo, std::move(label));
  return false;
}

auto Context::VerifyOnFinish() -> void {
  // Information in all the various context objects should be cleaned up as
  // various pieces of context go out of scope. At this point, nothing should
  // remain.
  // node_stack_ will still contain top-level entities.
  scope_stack_.VerifyOnFinish();
  inst_block_stack_.VerifyOnFinish();
  param_and_arg_refs_stack_.VerifyOnFinish();
}

// Finish producing an instruction. Set its constant value, and register it in
// any applicable instruction lists.
auto Context::FinishInst(SemIR::InstId inst_id, SemIR::Inst inst) -> void {
  GenericRegionStack::DependencyKind dep_kind =
      GenericRegionStack::DependencyKind::None;

  // If the instruction has a symbolic constant type, track that we need to
  // substitute into it.
  if (types().GetConstantId(inst.type_id()).is_symbolic()) {
    dep_kind |= GenericRegionStack::DependencyKind::SymbolicType;
  }

  // If the instruction has a constant value, compute it.
  auto const_id = TryEvalInst(*this, inst_id, inst);
  constant_values().Set(inst_id, const_id);
  if (const_id.is_constant()) {
    CARBON_VLOG() << "Constant: " << inst << " -> "
                  << constant_values().GetInstId(const_id) << "\n";

    // If the constant value is symbolic, track that we need to substitute into
    // it.
    if (const_id.is_symbolic()) {
      dep_kind |= GenericRegionStack::DependencyKind::SymbolicConstant;
    }
  }

  // Keep track of dependent instructions.
  if (dep_kind != GenericRegionStack::DependencyKind::None) {
    // TODO: Also check for template-dependent instructions.
    generic_region_stack().AddDependentInst(
        {.inst_id = inst_id, .kind = dep_kind});
  }
}

auto Context::AddInstInNoBlock(SemIR::LocIdAndInst loc_id_and_inst)
    -> SemIR::InstId {
  auto inst_id = sem_ir().insts().AddInNoBlock(loc_id_and_inst);
  CARBON_VLOG() << "AddInst: " << loc_id_and_inst.inst << "\n";
  FinishInst(inst_id, loc_id_and_inst.inst);
  return inst_id;
}

auto Context::AddInst(SemIR::LocIdAndInst loc_id_and_inst) -> SemIR::InstId {
  auto inst_id = AddInstInNoBlock(loc_id_and_inst);
  inst_block_stack_.AddInstId(inst_id);
  return inst_id;
}

auto Context::AddPlaceholderInstInNoBlock(SemIR::LocIdAndInst loc_id_and_inst)
    -> SemIR::InstId {
  auto inst_id = sem_ir().insts().AddInNoBlock(loc_id_and_inst);
  CARBON_VLOG() << "AddPlaceholderInst: " << loc_id_and_inst.inst << "\n";
  constant_values().Set(inst_id, SemIR::ConstantId::Invalid);
  return inst_id;
}

auto Context::AddPlaceholderInst(SemIR::LocIdAndInst loc_id_and_inst)
    -> SemIR::InstId {
  auto inst_id = AddPlaceholderInstInNoBlock(loc_id_and_inst);
  inst_block_stack_.AddInstId(inst_id);
  return inst_id;
}

auto Context::AddConstant(SemIR::Inst inst, bool is_symbolic)
    -> SemIR::ConstantId {
  auto const_id = constants().GetOrAdd(inst, is_symbolic);
  CARBON_VLOG() << "AddConstant: " << inst << "\n";
  return const_id;
}

auto Context::ReplaceLocIdAndInstBeforeConstantUse(
    SemIR::InstId inst_id, SemIR::LocIdAndInst loc_id_and_inst) -> void {
  sem_ir().insts().SetLocIdAndInst(inst_id, loc_id_and_inst);
  CARBON_VLOG() << "ReplaceInst: " << inst_id << " -> " << loc_id_and_inst.inst
                << "\n";
  FinishInst(inst_id, loc_id_and_inst.inst);
}

auto Context::ReplaceInstBeforeConstantUse(SemIR::InstId inst_id,
                                           SemIR::Inst inst) -> void {
  sem_ir().insts().Set(inst_id, inst);
  CARBON_VLOG() << "ReplaceInst: " << inst_id << " -> " << inst << "\n";
  FinishInst(inst_id, inst);
}

auto Context::DiagnoseDuplicateName(SemIRLoc dup_def, SemIRLoc prev_def)
    -> void {
  CARBON_DIAGNOSTIC(NameDeclDuplicate, Error,
                    "Duplicate name being declared in the same scope.");
  CARBON_DIAGNOSTIC(NameDeclPrevious, Note,
                    "Name is previously declared here.");
  emitter_->Build(dup_def, NameDeclDuplicate)
      .Note(prev_def, NameDeclPrevious)
      .Emit();
}

auto Context::DiagnoseNameNotFound(SemIRLoc loc, SemIR::NameId name_id)
    -> void {
  CARBON_DIAGNOSTIC(NameNotFound, Error, "Name `{0}` not found.",
                    SemIR::NameId);
  emitter_->Emit(loc, NameNotFound, name_id);
}

auto Context::NoteIncompleteClass(SemIR::ClassId class_id,
                                  DiagnosticBuilder& builder) -> void {
  const auto& class_info = classes().Get(class_id);
  CARBON_CHECK(!class_info.is_defined()) << "Class is not incomplete";
  if (class_info.definition_id.is_valid()) {
    CARBON_DIAGNOSTIC(ClassIncompleteWithinDefinition, Note,
                      "Class is incomplete within its definition.");
    builder.Note(class_info.definition_id, ClassIncompleteWithinDefinition);
  } else {
    CARBON_DIAGNOSTIC(ClassForwardDeclaredHere, Note,
                      "Class was forward declared here.");
    builder.Note(class_info.decl_id, ClassForwardDeclaredHere);
  }
}

auto Context::NoteUndefinedInterface(SemIR::InterfaceId interface_id,
                                     DiagnosticBuilder& builder) -> void {
  const auto& interface_info = interfaces().Get(interface_id);
  CARBON_CHECK(!interface_info.is_defined()) << "Interface is not incomplete";
  if (interface_info.is_being_defined()) {
    CARBON_DIAGNOSTIC(InterfaceUndefinedWithinDefinition, Note,
                      "Interface is currently being defined.");
    builder.Note(interface_info.definition_id,
                 InterfaceUndefinedWithinDefinition);
  } else {
    CARBON_DIAGNOSTIC(InterfaceForwardDeclaredHere, Note,
                      "Interface was forward declared here.");
    builder.Note(interface_info.decl_id, InterfaceForwardDeclaredHere);
  }
}

auto Context::AddNameToLookup(SemIR::NameId name_id, SemIR::InstId target_id)
    -> void {
  if (auto existing = scope_stack().LookupOrAddName(name_id, target_id);
      existing.is_valid()) {
    DiagnoseDuplicateName(target_id, existing);
  }
}

auto Context::LookupNameInDecl(SemIR::LocId loc_id, SemIR::NameId name_id,
                               SemIR::NameScopeId scope_id) -> SemIR::InstId {
  if (!scope_id.is_valid()) {
    // Look for a name in the current scope only. There are two cases where the
    // name would be in an outer scope:
    //
    //  - The name is the sole component of the declared name:
    //
    //    class A;
    //    fn F() {
    //      class A;
    //    }
    //
    //    In this case, the inner A is not the same class as the outer A, so
    //    lookup should not find the outer A.
    //
    //  - The name is a qualifier of some larger declared name:
    //
    //    class A { class B; }
    //    fn F() {
    //      class A.B {}
    //    }
    //
    //    In this case, we're not in the correct scope to define a member of
    //    class A, so we should reject, and we achieve this by not finding the
    //    name A from the outer scope.
    return scope_stack().LookupInCurrentScope(name_id);
  } else {
    // We do not look into `extend`ed scopes here. A qualified name in a
    // declaration must specify the exact scope in which the name was originally
    // introduced:
    //
    //    base class A { fn F(); }
    //    class B { extend base: A; }
    //
    //    // Error, no `F` in `B`.
    //    fn B.F() {}
    return LookupNameInExactScope(loc_id, name_id, scope_id,
                                  name_scopes().Get(scope_id));
  }
}

auto Context::LookupUnqualifiedName(Parse::NodeId node_id,
                                    SemIR::NameId name_id) -> SemIR::InstId {
  // TODO: Check for shadowed lookup results.

  // Find the results from ancestor lexical scopes. These will be combined with
  // results from non-lexical scopes such as namespaces and classes.
  auto [lexical_result, non_lexical_scopes] =
      scope_stack().LookupInLexicalScopes(name_id);

  // Walk the non-lexical scopes and perform lookups into each of them.
  for (auto [index, name_scope_id] : llvm::reverse(non_lexical_scopes)) {
    if (auto non_lexical_result =
            LookupQualifiedName(node_id, name_id, name_scope_id,
                                /*required=*/false);
        non_lexical_result.is_valid()) {
      return non_lexical_result;
    }
  }

  if (lexical_result.is_valid()) {
    return lexical_result;
  }

  // We didn't find anything at all.
  DiagnoseNameNotFound(node_id, name_id);
  return SemIR::InstId::BuiltinError;
}

// Handles lookup through the import_ir_scopes for LookupNameInExactScope.
static auto LookupInImportIRScopes(Context& context, SemIRLoc loc,
                                   SemIR::NameId name_id,
                                   SemIR::NameScopeId scope_id,
                                   const SemIR::NameScope& scope)
    -> SemIR::InstId {
  auto identifier_id = name_id.AsIdentifierId();
  llvm::StringRef identifier;
  if (identifier_id.is_valid()) {
    identifier = context.identifiers().Get(identifier_id);
  }

  DiagnosticAnnotationScope annotate_diagnostics(
      &context.emitter(), [&](auto& builder) {
        CARBON_DIAGNOSTIC(InNameLookup, Note, "In name lookup for `{0}`.",
                          SemIR::NameId);
        builder.Note(loc, InNameLookup, name_id);
      });

  auto result_id = SemIR::InstId::Invalid;
  std::optional<SemIR::ImportIRInst> canonical_result_inst;

  for (auto [import_ir_id, import_scope_id] : scope.import_ir_scopes) {
    auto& import_ir = context.import_irs().Get(import_ir_id);

    // Determine the NameId in the import IR.
    SemIR::NameId import_name_id = name_id;
    if (identifier_id.is_valid()) {
      auto import_identifier_id =
          import_ir.sem_ir->identifiers().Lookup(identifier);
      if (!import_identifier_id.is_valid()) {
        // Name doesn't exist in the import IR.
        continue;
      }
      import_name_id = SemIR::NameId::ForIdentifier(import_identifier_id);
    }

    // Look up the name in the import scope.
    const auto& import_scope =
        import_ir.sem_ir->name_scopes().Get(import_scope_id);
    auto lookup = import_scope.name_map.Lookup(import_name_id);
    if (!lookup) {
      // Name doesn't exist in the import scope.
      continue;
    }
    const auto& import_scope_entry = import_scope.names[lookup.value()];
    auto import_inst =
        import_ir.sem_ir->insts().Get(import_scope_entry.inst_id);
    if (import_inst.Is<SemIR::AnyImportRef>()) {
      // This entity was added to name lookup by using an import, and is not
      // exported.
      continue;
    }

    if (import_scope_entry.access_kind != SemIR::AccessKind::Public) {
      // Ignore cross-package non-public names.
      continue;
    }

    if (result_id.is_valid()) {
      // On a conflict, we verify the canonical instruction is the same.
      if (!canonical_result_inst) {
        canonical_result_inst =
            GetCanonicalImportIRInst(context, &context.sem_ir(), result_id);
      }
      VerifySameCanonicalImportIRInst(
          context, result_id, *canonical_result_inst, import_ir_id,
          import_ir.sem_ir, import_scope_entry.inst_id);
    } else {
      // Add the first result found.
      auto bind_name_id = context.bind_names().Add(
          {.name_id = name_id,
           .parent_scope_id = scope_id,
           .bind_index = SemIR::CompileTimeBindIndex::Invalid});
      result_id = AddImportRef(
          context,
          {.ir_id = import_ir_id, .inst_id = import_scope_entry.inst_id},
          bind_name_id);
      LoadImportRef(context, result_id);
    }
  }

  return result_id;
}

auto Context::LookupNameInExactScope(SemIRLoc loc, SemIR::NameId name_id,
                                     SemIR::NameScopeId scope_id,
                                     const SemIR::NameScope& scope)
    -> SemIR::InstId {
  if (auto lookup = scope.name_map.Lookup(name_id)) {
    auto inst_id = scope.names[lookup.value()].inst_id;
    LoadImportRef(*this, inst_id);
    return inst_id;
  }
  if (!scope.import_ir_scopes.empty()) {
    return LookupInImportIRScopes(*this, loc, name_id, scope_id, scope);
  }
  return SemIR::InstId::Invalid;
}

auto Context::LookupQualifiedName(Parse::NodeId node_id, SemIR::NameId name_id,
                                  SemIR::NameScopeId scope_id, bool required)
    -> SemIR::InstId {
  llvm::SmallVector<SemIR::NameScopeId> scope_ids = {scope_id};
  auto result_id = SemIR::InstId::Invalid;
  bool has_error = false;

  // Walk this scope and, if nothing is found here, the scopes it extends.
  while (!scope_ids.empty()) {
    auto scope_id = scope_ids.pop_back_val();
    const auto& scope = name_scopes().Get(scope_id);
    has_error |= scope.has_error;

    auto scope_result_id =
        LookupNameInExactScope(node_id, name_id, scope_id, scope);
    if (!scope_result_id.is_valid()) {
      // Nothing found in this scope: also look in its extended scopes.
      auto extended = llvm::reverse(scope.extended_scopes);
      scope_ids.append(extended.begin(), extended.end());
      continue;
    }

    // If this is our second lookup result, diagnose an ambiguity.
    if (result_id.is_valid()) {
      // TODO: This is currently not reachable because the only scope that can
      // extend is a class scope, and it can only extend a single base class.
      // Add test coverage once this is possible.
      CARBON_DIAGNOSTIC(
          NameAmbiguousDueToExtend, Error,
          "Ambiguous use of name `{0}` found in multiple extended scopes.",
          SemIR::NameId);
      emitter_->Emit(node_id, NameAmbiguousDueToExtend, name_id);
      // TODO: Add notes pointing to the scopes.
      return SemIR::InstId::BuiltinError;
    }

    result_id = scope_result_id;
  }

  if (required && !result_id.is_valid()) {
    if (!has_error) {
      DiagnoseNameNotFound(node_id, name_id);
    }
    return SemIR::InstId::BuiltinError;
  }

  return result_id;
}

// Returns the scope of the Core package, or Invalid if it's not found.
//
// TODO: Consider tracking the Core package in SemIR so we don't need to use
// name lookup to find it.
static auto GetCorePackage(Context& context, SemIRLoc loc)
    -> SemIR::NameScopeId {
  auto core_ident_id = context.identifiers().Add("Core");
  auto packaging = context.parse_tree().packaging_decl();
  if (packaging && packaging->names.package_id == core_ident_id) {
    return SemIR::NameScopeId::Package;
  }
  auto core_name_id = SemIR::NameId::ForIdentifier(core_ident_id);

  // Look up `package.Core`.
  auto core_inst_id = context.LookupNameInExactScope(
      loc, core_name_id, SemIR::NameScopeId::Package,
      context.name_scopes().Get(SemIR::NameScopeId::Package));
  if (!core_inst_id.is_valid()) {
    context.DiagnoseNameNotFound(loc, core_name_id);
    return SemIR::NameScopeId::Invalid;
  }

  // We expect it to be a namespace.
  if (auto namespace_inst =
          context.insts().TryGetAs<SemIR::Namespace>(core_inst_id)) {
    return namespace_inst->name_scope_id;
  }
  // TODO: This should really diagnose the name issue.
  context.DiagnoseNameNotFound(loc, core_name_id);
  return SemIR::NameScopeId::Invalid;
}

auto Context::LookupNameInCore(SemIRLoc loc, llvm::StringRef name)
    -> SemIR::InstId {
  auto core_package_id = GetCorePackage(*this, loc);
  if (!core_package_id.is_valid()) {
    return SemIR::InstId::BuiltinError;
  }

  auto name_id = SemIR::NameId::ForIdentifier(identifiers().Add(name));
  auto inst_id = LookupNameInExactScope(loc, name_id, core_package_id,
                                        name_scopes().Get(core_package_id));
  if (!inst_id.is_valid()) {
    DiagnoseNameNotFound(loc, name_id);
    return SemIR::InstId::BuiltinError;
  }

  // Look through import_refs and aliases.
  return constant_values().GetConstantInstId(inst_id);
}

template <typename BranchNode, typename... Args>
static auto AddDominatedBlockAndBranchImpl(Context& context,
                                           Parse::NodeId node_id, Args... args)
    -> SemIR::InstBlockId {
  if (!context.inst_block_stack().is_current_block_reachable()) {
    return SemIR::InstBlockId::Unreachable;
  }
  auto block_id = context.inst_blocks().AddDefaultValue();
  context.AddInst<BranchNode>(node_id, {block_id, args...});
  return block_id;
}

auto Context::AddDominatedBlockAndBranch(Parse::NodeId node_id)
    -> SemIR::InstBlockId {
  return AddDominatedBlockAndBranchImpl<SemIR::Branch>(*this, node_id);
}

auto Context::AddDominatedBlockAndBranchWithArg(Parse::NodeId node_id,
                                                SemIR::InstId arg_id)
    -> SemIR::InstBlockId {
  return AddDominatedBlockAndBranchImpl<SemIR::BranchWithArg>(*this, node_id,
                                                              arg_id);
}

auto Context::AddDominatedBlockAndBranchIf(Parse::NodeId node_id,
                                           SemIR::InstId cond_id)
    -> SemIR::InstBlockId {
  return AddDominatedBlockAndBranchImpl<SemIR::BranchIf>(*this, node_id,
                                                         cond_id);
}

auto Context::AddConvergenceBlockAndPush(Parse::NodeId node_id, int num_blocks)
    -> void {
  CARBON_CHECK(num_blocks >= 2) << "no convergence";

  SemIR::InstBlockId new_block_id = SemIR::InstBlockId::Unreachable;
  for ([[maybe_unused]] auto _ : llvm::seq(num_blocks)) {
    if (inst_block_stack().is_current_block_reachable()) {
      if (new_block_id == SemIR::InstBlockId::Unreachable) {
        new_block_id = inst_blocks().AddDefaultValue();
      }
      AddInst<SemIR::Branch>(node_id, {.target_id = new_block_id});
    }
    inst_block_stack().Pop();
  }
  inst_block_stack().Push(new_block_id);
}

auto Context::AddConvergenceBlockWithArgAndPush(
    Parse::NodeId node_id, std::initializer_list<SemIR::InstId> block_args)
    -> SemIR::InstId {
  CARBON_CHECK(block_args.size() >= 2) << "no convergence";

  SemIR::InstBlockId new_block_id = SemIR::InstBlockId::Unreachable;
  for (auto arg_id : block_args) {
    if (inst_block_stack().is_current_block_reachable()) {
      if (new_block_id == SemIR::InstBlockId::Unreachable) {
        new_block_id = inst_blocks().AddDefaultValue();
      }
      AddInst<SemIR::BranchWithArg>(
          node_id, {.target_id = new_block_id, .arg_id = arg_id});
    }
    inst_block_stack().Pop();
  }
  inst_block_stack().Push(new_block_id);

  // Acquire the result value.
  SemIR::TypeId result_type_id = insts().Get(*block_args.begin()).type_id();
  return AddInst<SemIR::BlockArg>(
      node_id, {.type_id = result_type_id, .block_id = new_block_id});
}

auto Context::SetBlockArgResultBeforeConstantUse(SemIR::InstId select_id,
                                                 SemIR::InstId cond_id,
                                                 SemIR::InstId if_true,
                                                 SemIR::InstId if_false)
    -> void {
  CARBON_CHECK(insts().Is<SemIR::BlockArg>(select_id));

  // Determine the constant result based on the condition value.
  SemIR::ConstantId const_id = SemIR::ConstantId::NotConstant;
  auto cond_const_id = constant_values().Get(cond_id);
  if (!cond_const_id.is_template()) {
    // Symbolic or non-constant condition means a non-constant result.
  } else if (auto literal = insts().TryGetAs<SemIR::BoolLiteral>(
                 constant_values().GetInstId(cond_const_id))) {
    const_id = constant_values().Get(literal.value().value.ToBool() ? if_true
                                                                    : if_false);
  } else {
    CARBON_CHECK(cond_const_id == SemIR::ConstantId::Error)
        << "Unexpected constant branch condition.";
    const_id = SemIR::ConstantId::Error;
  }

  if (const_id.is_constant()) {
    CARBON_VLOG() << "Constant: " << insts().Get(select_id) << " -> "
                  << constant_values().GetInstId(const_id) << "\n";
    constant_values().Set(select_id, const_id);
  }
}

auto Context::AddCurrentCodeBlockToFunction(Parse::NodeId node_id) -> void {
  CARBON_CHECK(!inst_block_stack().empty()) << "no current code block";

  if (return_scope_stack().empty()) {
    CARBON_CHECK(node_id.is_valid())
        << "No current function, but node_id not provided";
    TODO(node_id,
         "Control flow expressions are currently only supported inside "
         "functions.");
    return;
  }

  if (!inst_block_stack().is_current_block_reachable()) {
    // Don't include unreachable blocks in the function.
    return;
  }

  auto function_id =
      insts()
          .GetAs<SemIR::FunctionDecl>(return_scope_stack().back().decl_id)
          .function_id;
  functions()
      .Get(function_id)
      .body_block_ids.push_back(inst_block_stack().PeekOrAdd());
}

auto Context::is_current_position_reachable() -> bool {
  if (!inst_block_stack().is_current_block_reachable()) {
    return false;
  }

  // Our current position is at the end of a reachable block. That position is
  // reachable unless the previous instruction is a terminator instruction.
  auto block_contents = inst_block_stack().PeekCurrentBlockContents();
  if (block_contents.empty()) {
    return true;
  }
  const auto& last_inst = insts().Get(block_contents.back());
  return last_inst.kind().terminator_kind() !=
         SemIR::TerminatorKind::Terminator;
}

auto Context::FinalizeGlobalInit() -> void {
  inst_block_stack().PushGlobalInit();
  if (!inst_block_stack().PeekCurrentBlockContents().empty()) {
    AddInst<SemIR::Return>(Parse::NodeId::Invalid, {});
    // Pop the GlobalInit block here to finalize it.
    inst_block_stack().Pop();

    // __global_init is only added if there are initialization instructions.
    auto name_id = sem_ir().identifiers().Add("__global_init");
    sem_ir().functions().Add(
        {.name_id = SemIR::NameId::ForIdentifier(name_id),
         .parent_scope_id = SemIR::NameScopeId::Package,
         .decl_id = SemIR::InstId::Invalid,
         .generic_id = SemIR::GenericId::Invalid,
         .implicit_param_refs_id = SemIR::InstBlockId::Invalid,
         .param_refs_id = SemIR::InstBlockId::Empty,
         .return_storage_id = SemIR::InstId::Invalid,
         .is_extern = false,
         .return_slot = SemIR::Function::ReturnSlot::Absent,
         .body_block_ids = {SemIR::InstBlockId::GlobalInit}});
  } else {
    inst_block_stack().PopGlobalInit();
  }
}

namespace {
// Worklist-based type completion mechanism.
//
// When attempting to complete a type, we may find other types that also need to
// be completed: types nested within that type, and the value representation of
// the type. In order to complete a type without recursing arbitrarily deeply,
// we use a worklist of tasks:
//
// - An `AddNestedIncompleteTypes` step adds a task for all incomplete types
//   nested within a type to the work list.
// - A `BuildValueRepr` step computes the value representation for a
//   type, once all of its nested types are complete, and marks the type as
//   complete.
class TypeCompleter {
 public:
  TypeCompleter(
      Context& context,
      std::optional<llvm::function_ref<auto()->Context::DiagnosticBuilder>>
          diagnoser)
      : context_(context), diagnoser_(diagnoser) {}

  // Attempts to complete the given type. Returns true if it is now complete,
  // false if it could not be completed.
  auto Complete(SemIR::TypeId type_id) -> bool {
    Push(type_id);
    while (!work_list_.empty()) {
      if (!ProcessStep()) {
        return false;
      }
    }
    return true;
  }

 private:
  // Adds `type_id` to the work list, if it's not already complete.
  auto Push(SemIR::TypeId type_id) -> void {
    if (!context_.types().IsComplete(type_id)) {
      work_list_.push_back(
          {.type_id = type_id, .phase = Phase::AddNestedIncompleteTypes});
    }
  }

  // Runs the next step.
  auto ProcessStep() -> bool {
    auto [type_id, phase] = work_list_.back();

    // We might have enqueued the same type more than once. Just skip the
    // type if it's already complete.
    if (context_.types().IsComplete(type_id)) {
      work_list_.pop_back();
      return true;
    }

    auto inst_id = context_.types().GetInstId(type_id);
    auto inst = context_.insts().Get(inst_id);
    auto old_work_list_size = work_list_.size();

    switch (phase) {
      case Phase::AddNestedIncompleteTypes:
        if (!AddNestedIncompleteTypes(inst)) {
          return false;
        }
        CARBON_CHECK(work_list_.size() >= old_work_list_size)
            << "AddNestedIncompleteTypes should not remove work items";
        work_list_[old_work_list_size - 1].phase = Phase::BuildValueRepr;
        break;

      case Phase::BuildValueRepr: {
        auto value_rep = BuildValueRepr(type_id, inst);
        context_.sem_ir().CompleteType(type_id, value_rep);
        CARBON_CHECK(old_work_list_size == work_list_.size())
            << "BuildValueRepr should not change work items";
        work_list_.pop_back();

        // Also complete the value representation type, if necessary. This
        // should never fail: the value representation shouldn't require any
        // additional nested types to be complete.
        if (!context_.types().IsComplete(value_rep.type_id)) {
          work_list_.push_back(
              {.type_id = value_rep.type_id, .phase = Phase::BuildValueRepr});
        }
        // For a pointer representation, the pointee also needs to be complete.
        if (value_rep.kind == SemIR::ValueRepr::Pointer) {
          if (value_rep.type_id == SemIR::TypeId::Error) {
            break;
          }
          auto pointee_type_id =
              context_.sem_ir().GetPointeeType(value_rep.type_id);
          if (!context_.types().IsComplete(pointee_type_id)) {
            work_list_.push_back(
                {.type_id = pointee_type_id, .phase = Phase::BuildValueRepr});
          }
        }
        break;
      }
    }

    return true;
  }

  // Adds any types nested within `type_inst` that need to be complete for
  // `type_inst` to be complete to our work list.
  auto AddNestedIncompleteTypes(SemIR::Inst type_inst) -> bool {
    CARBON_KIND_SWITCH(type_inst) {
      case CARBON_KIND(SemIR::ArrayType inst): {
        Push(inst.element_type_id);
        break;
      }
      case CARBON_KIND(SemIR::StructType inst): {
        for (auto field_id : context_.inst_blocks().Get(inst.fields_id)) {
          Push(context_.insts()
                   .GetAs<SemIR::StructTypeField>(field_id)
                   .field_type_id);
        }
        break;
      }
      case CARBON_KIND(SemIR::TupleType inst): {
        for (auto element_type_id :
             context_.type_blocks().Get(inst.elements_id)) {
          Push(element_type_id);
        }
        break;
      }
      case CARBON_KIND(SemIR::ClassType inst): {
        auto& class_info = context_.classes().Get(inst.class_id);
        if (!class_info.is_defined()) {
          if (diagnoser_) {
            auto builder = (*diagnoser_)();
            context_.NoteIncompleteClass(inst.class_id, builder);
            builder.Emit();
          }
          return false;
        }
        Push(class_info.object_repr_id);
        break;
      }
      case CARBON_KIND(SemIR::ConstType inst): {
        Push(inst.inner_id);
        break;
      }
      default:
        break;
    }

    return true;
  }

  // Makes an empty value representation, which is used for types that have no
  // state, such as empty structs and tuples.
  auto MakeEmptyValueRepr() const -> SemIR::ValueRepr {
    return {.kind = SemIR::ValueRepr::None,
            .type_id = context_.GetTupleType({})};
  }

  // Makes a value representation that uses pass-by-copy, copying the given
  // type.
  auto MakeCopyValueRepr(SemIR::TypeId rep_id,
                         SemIR::ValueRepr::AggregateKind aggregate_kind =
                             SemIR::ValueRepr::NotAggregate) const
      -> SemIR::ValueRepr {
    return {.kind = SemIR::ValueRepr::Copy,
            .aggregate_kind = aggregate_kind,
            .type_id = rep_id};
  }

  // Makes a value representation that uses pass-by-address with the given
  // pointee type.
  auto MakePointerValueRepr(SemIR::TypeId pointee_id,
                            SemIR::ValueRepr::AggregateKind aggregate_kind =
                                SemIR::ValueRepr::NotAggregate) const
      -> SemIR::ValueRepr {
    // TODO: Should we add `const` qualification to `pointee_id`?
    return {.kind = SemIR::ValueRepr::Pointer,
            .aggregate_kind = aggregate_kind,
            .type_id = context_.GetPointerType(pointee_id)};
  }

  // Gets the value representation of a nested type, which should already be
  // complete.
  auto GetNestedValueRepr(SemIR::TypeId nested_type_id) const {
    CARBON_CHECK(context_.types().IsComplete(nested_type_id))
        << "Nested type should already be complete";
    auto value_rep = context_.types().GetValueRepr(nested_type_id);
    CARBON_CHECK(value_rep.kind != SemIR::ValueRepr::Unknown)
        << "Complete type should have a value representation";
    return value_rep;
  }

  auto BuildBuiltinValueRepr(SemIR::TypeId type_id,
                             SemIR::Builtin builtin) const -> SemIR::ValueRepr {
    switch (builtin.builtin_kind) {
      case SemIR::BuiltinKind::TypeType:
      case SemIR::BuiltinKind::Error:
      case SemIR::BuiltinKind::Invalid:
      case SemIR::BuiltinKind::BoolType:
      case SemIR::BuiltinKind::IntType:
      case SemIR::BuiltinKind::FloatType:
      case SemIR::BuiltinKind::NamespaceType:
      case SemIR::BuiltinKind::BoundMethodType:
      case SemIR::BuiltinKind::WitnessType:
        return MakeCopyValueRepr(type_id);

      case SemIR::BuiltinKind::StringType:
        // TODO: Decide on string value semantics. This should probably be a
        // custom value representation carrying a pointer and size or
        // similar.
        return MakePointerValueRepr(type_id);
    }
    llvm_unreachable("All builtin kinds were handled above");
  }

  auto BuildStructOrTupleValueRepr(std::size_t num_elements,
                                   SemIR::TypeId elementwise_rep,
                                   bool same_as_object_rep) const
      -> SemIR::ValueRepr {
    SemIR::ValueRepr::AggregateKind aggregate_kind =
        same_as_object_rep ? SemIR::ValueRepr::ValueAndObjectAggregate
                           : SemIR::ValueRepr::ValueAggregate;

    if (num_elements == 1) {
      // The value representation for a struct or tuple with a single element
      // is a struct or tuple containing the value representation of the
      // element.
      // TODO: Consider doing the same whenever `elementwise_rep` is
      // sufficiently small.
      return MakeCopyValueRepr(elementwise_rep, aggregate_kind);
    }
    // For a struct or tuple with multiple fields, we use a pointer
    // to the elementwise value representation.
    return MakePointerValueRepr(elementwise_rep, aggregate_kind);
  }

  auto BuildStructTypeValueRepr(SemIR::TypeId type_id,
                                SemIR::StructType struct_type) const
      -> SemIR::ValueRepr {
    // TODO: Share more code with tuples.
    auto fields = context_.inst_blocks().Get(struct_type.fields_id);
    if (fields.empty()) {
      return MakeEmptyValueRepr();
    }

    // Find the value representation for each field, and construct a struct
    // of value representations.
    llvm::SmallVector<SemIR::InstId> value_rep_fields;
    value_rep_fields.reserve(fields.size());
    bool same_as_object_rep = true;
    for (auto field_id : fields) {
      auto field = context_.insts().GetAs<SemIR::StructTypeField>(field_id);
      auto field_value_rep = GetNestedValueRepr(field.field_type_id);
      if (field_value_rep.type_id != field.field_type_id) {
        same_as_object_rep = false;
        field.field_type_id = field_value_rep.type_id;
        field_id = context_.constant_values().GetInstId(
            TryEvalInst(context_, SemIR::InstId::Invalid, field));
      }
      value_rep_fields.push_back(field_id);
    }

    auto value_rep = same_as_object_rep
                         ? type_id
                         : context_.GetStructType(
                               context_.inst_blocks().Add(value_rep_fields));
    return BuildStructOrTupleValueRepr(fields.size(), value_rep,
                                       same_as_object_rep);
  }

  auto BuildTupleTypeValueRepr(SemIR::TypeId type_id,
                               SemIR::TupleType tuple_type) const
      -> SemIR::ValueRepr {
    // TODO: Share more code with structs.
    auto elements = context_.type_blocks().Get(tuple_type.elements_id);
    if (elements.empty()) {
      return MakeEmptyValueRepr();
    }

    // Find the value representation for each element, and construct a tuple
    // of value representations.
    llvm::SmallVector<SemIR::TypeId> value_rep_elements;
    value_rep_elements.reserve(elements.size());
    bool same_as_object_rep = true;
    for (auto element_type_id : elements) {
      auto element_value_rep = GetNestedValueRepr(element_type_id);
      if (element_value_rep.type_id != element_type_id) {
        same_as_object_rep = false;
      }
      value_rep_elements.push_back(element_value_rep.type_id);
    }

    auto value_rep = same_as_object_rep
                         ? type_id
                         : context_.GetTupleType(value_rep_elements);
    return BuildStructOrTupleValueRepr(elements.size(), value_rep,
                                       same_as_object_rep);
  }

  // Builds and returns the value representation for the given type. All nested
  // types, as found by AddNestedIncompleteTypes, are known to be complete.
  auto BuildValueRepr(SemIR::TypeId type_id, SemIR::Inst inst) const
      -> SemIR::ValueRepr {
    CARBON_KIND_SWITCH(inst) {
#define CARBON_SEM_IR_INST_KIND_TYPE_ALWAYS(...)
#define CARBON_SEM_IR_INST_KIND_TYPE_MAYBE(...)
#define CARBON_SEM_IR_INST_KIND(Name) case SemIR::Name::Kind:
#include "toolchain/sem_ir/inst_kind.def"
      CARBON_FATAL() << "Type refers to non-type inst " << inst;

      case SemIR::ArrayType::Kind: {
        // For arrays, it's convenient to always use a pointer representation,
        // even when the array has zero or one element, in order to support
        // indexing.
        return MakePointerValueRepr(type_id, SemIR::ValueRepr::ObjectAggregate);
      }

      case CARBON_KIND(SemIR::StructType struct_type): {
        return BuildStructTypeValueRepr(type_id, struct_type);
      }
      case CARBON_KIND(SemIR::TupleType tuple_type): {
        return BuildTupleTypeValueRepr(type_id, tuple_type);
      }
      case CARBON_KIND(SemIR::ClassType class_type): {
        auto& class_info = context_.classes().Get(class_type.class_id);
        // The value representation of an adapter is the value representation of
        // its adapted type.
        if (class_info.adapt_id.is_valid()) {
          return GetNestedValueRepr(class_info.object_repr_id);
        }
        // Otherwise, the value representation for a class is a pointer to the
        // object representation.
        // TODO: Support customized value representations for classes.
        // TODO: Pick a better value representation when possible.
        return MakePointerValueRepr(class_info.object_repr_id,
                                    SemIR::ValueRepr::ObjectAggregate);
      }
      case SemIR::AssociatedEntityType::Kind:
      case SemIR::FunctionType::Kind:
      case SemIR::GenericClassType::Kind:
      case SemIR::GenericInterfaceType::Kind:
      case SemIR::InterfaceType::Kind:
      case SemIR::UnboundElementType::Kind: {
        // These types have no runtime operations, so we use an empty value
        // representation.
        //
        // TODO: There is information we could model here:
        // - For an interface, we could use a witness.
        // - For an associated entity, we could use an index into the witness.
        // - For an unbound element, we could use an index or offset.
        return MakeEmptyValueRepr();
      }
      case CARBON_KIND(SemIR::Builtin builtin): {
        return BuildBuiltinValueRepr(type_id, builtin);
      }

      case SemIR::BindSymbolicName::Kind:
      case SemIR::InterfaceWitnessAccess::Kind:
        // For symbolic types, we arbitrarily pick a copy representation.
        return MakeCopyValueRepr(type_id);

      case SemIR::FloatType::Kind:
      case SemIR::IntType::Kind:
      case SemIR::PointerType::Kind:
        return MakeCopyValueRepr(type_id);

      case CARBON_KIND(SemIR::ConstType const_type): {
        // The value representation of `const T` is the same as that of `T`.
        // Objects are not modifiable through their value representations.
        return GetNestedValueRepr(const_type.inner_id);
      }
    }
  }

  enum class Phase : int8_t {
    // The next step is to add nested types to the list of types to complete.
    AddNestedIncompleteTypes,
    // The next step is to build the value representation for the type.
    BuildValueRepr,
  };

  struct WorkItem {
    SemIR::TypeId type_id;
    Phase phase;
  };

  Context& context_;
  llvm::SmallVector<WorkItem> work_list_;
  std::optional<llvm::function_ref<auto()->Context::DiagnosticBuilder>>
      diagnoser_;
};
}  // namespace

auto Context::TryToCompleteType(
    SemIR::TypeId type_id,
    std::optional<llvm::function_ref<auto()->DiagnosticBuilder>> diagnoser)
    -> bool {
  return TypeCompleter(*this, diagnoser).Complete(type_id);
}

auto Context::GetTypeIdForTypeConstant(SemIR::ConstantId constant_id)
    -> SemIR::TypeId {
  CARBON_CHECK(constant_id.is_constant())
      << "Canonicalizing non-constant type: " << constant_id;

  auto result = type_ids_for_type_constants_.Insert(
      constant_id, [&]() { return types().Add({.constant_id = constant_id}); });
  return result.value();
}

// Gets or forms a type_id for a type, given the instruction kind and arguments.
template <typename InstT, typename... EachArgT>
static auto GetTypeImpl(Context& context, EachArgT... each_arg)
    -> SemIR::TypeId {
  // TODO: Remove inst_id parameter from TryEvalInst.
  InstT inst = {SemIR::TypeId::TypeType, each_arg...};
  return context.GetTypeIdForTypeConstant(
      TryEvalInst(context, SemIR::InstId::Invalid, inst));
}

// Gets or forms a type_id for a type, given the instruction kind and arguments,
// and completes the type. This should only be used when type completion cannot
// fail.
template <typename InstT, typename... EachArgT>
static auto GetCompleteTypeImpl(Context& context, EachArgT... each_arg)
    -> SemIR::TypeId {
  auto type_id = GetTypeImpl<InstT>(context, each_arg...);
  bool complete = context.TryToCompleteType(type_id);
  CARBON_CHECK(complete) << "Type completion should not fail";
  return type_id;
}

auto Context::GetStructType(SemIR::InstBlockId refs_id) -> SemIR::TypeId {
  return GetTypeImpl<SemIR::StructType>(*this, refs_id);
}

auto Context::GetTupleType(llvm::ArrayRef<SemIR::TypeId> type_ids)
    -> SemIR::TypeId {
  return GetTypeImpl<SemIR::TupleType>(*this,
                                       type_blocks().AddCanonical(type_ids));
}

auto Context::GetAssociatedEntityType(SemIR::InterfaceId interface_id,
                                      SemIR::TypeId entity_type_id)
    -> SemIR::TypeId {
  return GetTypeImpl<SemIR::AssociatedEntityType>(*this, interface_id,
                                                  entity_type_id);
}

auto Context::GetBuiltinType(SemIR::BuiltinKind kind) -> SemIR::TypeId {
  CARBON_CHECK(kind != SemIR::BuiltinKind::Invalid);
  auto type_id = GetTypeIdForTypeInst(SemIR::InstId::ForBuiltin(kind));
  // To keep client code simpler, complete builtin types before returning them.
  bool complete = TryToCompleteType(type_id);
  CARBON_CHECK(complete) << "Failed to complete builtin type";
  return type_id;
}

auto Context::GetFunctionType(SemIR::FunctionId fn_id) -> SemIR::TypeId {
  return GetCompleteTypeImpl<SemIR::FunctionType>(*this, fn_id);
}

auto Context::GetGenericClassType(SemIR::ClassId class_id) -> SemIR::TypeId {
  return GetCompleteTypeImpl<SemIR::GenericClassType>(*this, class_id);
}

auto Context::GetGenericInterfaceType(SemIR::InterfaceId interface_id)
    -> SemIR::TypeId {
  return GetCompleteTypeImpl<SemIR::GenericInterfaceType>(*this, interface_id);
}

auto Context::GetPointerType(SemIR::TypeId pointee_type_id) -> SemIR::TypeId {
  return GetTypeImpl<SemIR::PointerType>(*this, pointee_type_id);
}

auto Context::GetUnboundElementType(SemIR::TypeId class_type_id,
                                    SemIR::TypeId element_type_id)
    -> SemIR::TypeId {
  return GetTypeImpl<SemIR::UnboundElementType>(*this, class_type_id,
                                                element_type_id);
}

auto Context::GetUnqualifiedType(SemIR::TypeId type_id) -> SemIR::TypeId {
  if (auto const_type = types().TryGetAs<SemIR::ConstType>(type_id)) {
    return const_type->inner_id;
  }
  return type_id;
}

auto Context::PrintForStackDump(llvm::raw_ostream& output) const -> void {
  node_stack_.PrintForStackDump(output);
  inst_block_stack_.PrintForStackDump(output);
  param_and_arg_refs_stack_.PrintForStackDump(output);
  args_type_info_stack_.PrintForStackDump(output);
}

}  // namespace Carbon::Check