toolchain/check/impl.cpp - trunk - githubmirror/carbon-lang

toolchain/check/impl.cpp
1 058 строк45 KB
Dana Jansens
Find the current impl from accesses in a named constraint being implemented (#7592)
31 июл 2026, 23:17
31 июл 2026, 23:172f58185
// 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/impl.h"

#include "toolchain/base/kind_switch.h"
#include "toolchain/check/context.h"
#include "toolchain/check/convert.h"
#include "toolchain/check/deduce.h"
#include "toolchain/check/eval.h"
#include "toolchain/check/facet_type.h"
#include "toolchain/check/function.h"
#include "toolchain/check/generic.h"
#include "toolchain/check/impl_lookup.h"
#include "toolchain/check/import_ref.h"
#include "toolchain/check/inst.h"
#include "toolchain/check/interface.h"
#include "toolchain/check/merge.h"
#include "toolchain/check/name_lookup.h"
#include "toolchain/check/name_scope.h"
#include "toolchain/check/period_self.h"
#include "toolchain/check/subst.h"
#include "toolchain/check/thunk.h"
#include "toolchain/check/type.h"
#include "toolchain/check/type_completion.h"
#include "toolchain/check/type_structure.h"
#include "toolchain/diagnostics/emitter.h"
#include "toolchain/sem_ir/generic.h"
#include "toolchain/sem_ir/identified_facet_type.h"
#include "toolchain/sem_ir/ids.h"
#include "toolchain/sem_ir/impl.h"
#include "toolchain/sem_ir/inst.h"
#include "toolchain/sem_ir/specific_interface.h"
#include "toolchain/sem_ir/typed_insts.h"

namespace Carbon::Check {

// Adds the location of the associated function to a diagnostic.
static auto NoteAssociatedFunction(Context& context, DiagnosticBuilder& builder,
                                   SemIR::FunctionId function_id) -> void {
  CARBON_DIAGNOSTIC(AssociatedFunctionHere, Note,
                    "associated function {0} declared here", SemIR::NameId);
  const auto& function = context.functions().Get(function_id);
  builder.Note(function.latest_decl_id(), AssociatedFunctionHere,
               function.name_id);
}

auto CheckAssociatedFunctionImplementation(
    Context& context, SemIR::FunctionType interface_function_type,
    SemIR::SpecificId enclosing_specific_id, SemIR::InstId impl_decl_id,
    bool defer_thunk_definition) -> SemIR::InstId {
  auto impl_function_decl =
      context.insts().TryGetAs<SemIR::FunctionDecl>(impl_decl_id);
  if (!impl_function_decl) {
    if (impl_decl_id != SemIR::ErrorInst::InstId) {
      CARBON_DIAGNOSTIC(ImplFunctionWithNonFunction, Error,
                        "associated function {0} implemented by non-function",
                        SemIR::NameId);
      auto builder = context.emitter().Build(
          impl_decl_id, ImplFunctionWithNonFunction,
          context.functions().Get(interface_function_type.function_id).name_id);
      NoteAssociatedFunction(context, builder,
                             interface_function_type.function_id);
      builder.Emit();
    }

    return SemIR::ErrorInst::InstId;
  }

  // Map from the specific for the function type to the specific for the
  // function signature. The function signature may have additional generic
  // parameters.
  auto interface_function_specific_id =
      GetSelfSpecificForInterfaceMemberWithSelfType(
          context, SemIR::LocId(impl_decl_id),
          interface_function_type.specific_id,
          context.functions()
              .Get(interface_function_type.function_id)
              .generic_id,
          enclosing_specific_id);

  return BuildThunk(context, interface_function_type.function_id,
                    interface_function_specific_id,
                    /*override_self_type_id=*/SemIR::TypeId::None, impl_decl_id,
                    defer_thunk_definition);
}

static auto GetScopeInstId(Context& context, SemIR::InstId scope_inst_id)
    -> SemIR::InstId {
  if (!scope_inst_id.has_value()) {
    return SemIR::InstId::None;
  }
  auto inst_id = context.constant_values().GetConstantInstId(scope_inst_id);
  if (auto struct_val = context.insts().TryGetAs<SemIR::StructValue>(inst_id)) {
    inst_id = context.types().GetTypeInstId(struct_val->type_id);
  }
  return inst_id;
}

enum class ImplRedeclType {
  ValidRedecl,
  Mismatch,
  DiagnosedInvalidRedecl,
};

// Returns whether the scope of the `new_impl` is the same as the scope of the
// `prev_impl`. If the `new_impl` is in an invalid scope for a redecl, that is
// diagnosed.
static auto ScopesMatch(Context& context, const SemIR::Impl& new_impl,
                        const SemIR::Impl& prev_impl) -> ImplRedeclType {
  auto new_id = GetScopeInstId(context, new_impl.parent_scope_inst_id);
  auto prev_id = GetScopeInstId(context, prev_impl.parent_scope_inst_id);
  if (new_id.has_value()) {
    auto new_scope_inst = context.insts().Get(new_id);
    CARBON_KIND_SWITCH(new_scope_inst) {
      case CARBON_KIND(SemIR::ClassType new_scope): {
        if (auto prev_scope =
                context.insts().TryGetAs<SemIR::ClassType>(prev_id)) {
          if (new_scope.class_id == prev_scope->class_id) {
            return ImplRedeclType::ValidRedecl;
          }
        }
        return ImplRedeclType::Mismatch;
      }
      case CARBON_KIND(SemIR::GenericClassType new_scope): {
        if (auto prev_scope =
                context.insts().TryGetAs<SemIR::GenericClassType>(prev_id)) {
          if (new_scope.class_id == prev_scope->class_id) {
            return ImplRedeclType::ValidRedecl;
          }
        }
        return ImplRedeclType::Mismatch;
      }
      case CARBON_KIND(SemIR::Namespace new_scope): {
        if (auto prev_scope =
                context.insts().TryGetAs<SemIR::Namespace>(prev_id)) {
          if (new_scope.name_scope_id == prev_scope->name_scope_id) {
            return ImplRedeclType::ValidRedecl;
          }
        }
        return ImplRedeclType::Mismatch;
      }
      default:
        break;
    }
  }

  // The redecl is is an invalid scope.
  CARBON_DIAGNOSTIC(ImplDeclInInvalidScope, Error,
                    "impl redeclation not in a declarative scope; "
                    "redeclaration is allowed only in a class or namespace");
  context.emitter().Emit(new_impl.latest_decl_id(), ImplDeclInInvalidScope);
  return ImplRedeclType::DiagnosedInvalidRedecl;
}

// Returns true if impl redeclaration parameters and scopes match.
//
// TODO: Generalize things to validate re-declarations of other entity types,
// which also have some similar rules such as sharing scopes.
static auto VerifyImplRedecl(Context& context, const SemIR::Impl& new_impl,
                             const SemIR::Impl& prev_impl) -> ImplRedeclType {
  // If the parameters aren't the same, then this is not a redeclaration of this
  // `impl`. Keep looking for a prior declaration without issuing a diagnostic.
  if (!CheckRedeclParamsMatch(context, DeclParams(new_impl),
                              DeclParams(prev_impl), SemIR::SpecificId::None,
                              /*diagnose=*/false, /*check_syntax=*/true)) {
    return ImplRedeclType::Mismatch;
  }

  // If the scopes are different, it is not treated as a redeclaration.
  if (auto scope_result = ScopesMatch(context, new_impl, prev_impl);
      scope_result != ImplRedeclType::ValidRedecl) {
    return scope_result;
  }

  // Following #4672, disallowing defining non-extern declarations in another
  // file.
  if (auto import_ref =
          context.insts().TryGetAs<SemIR::AnyImportRef>(prev_impl.self_id)) {
    // TODO: Handle extern.
    CARBON_DIAGNOSTIC(RedeclImportedImpl, Error,
                      "redeclaration of imported impl");
    // TODO: Note imported declaration
    context.emitter().Emit(new_impl.latest_decl_id(), RedeclImportedImpl);
    return ImplRedeclType::DiagnosedInvalidRedecl;
  }

  if (new_impl.has_definition_started() && prev_impl.has_definition_started()) {
    // Impls aren't merged in order to avoid generic region lookup into a
    // mismatching table.
    CARBON_DIAGNOSTIC(ImplRedefinition, Error,
                      "redefinition of `impl {0} as {1}`", InstIdAsRawType,
                      InstIdAsRawType);
    CARBON_DIAGNOSTIC(ImplPreviousDefinition, Note,
                      "previous definition was here");
    context.emitter()
        .Build(new_impl.latest_decl_id(), ImplRedefinition, new_impl.self_id,
               new_impl.constraint_id)
        .Note(prev_impl.definition_id, ImplPreviousDefinition)
        .Emit();
    return ImplRedeclType::DiagnosedInvalidRedecl;
  }

  return ImplRedeclType::ValidRedecl;
}

// Looks for any unused generic bindings. If one is found, it is diagnosed and
// false is returned.
static auto VerifyAllGenericBindingsUsed(Context& context, SemIR::LocId loc_id,
                                         SemIR::LocId implicit_params_loc_id,
                                         SemIR::ImplId impl_id,
                                         SemIR::Impl& impl) -> bool {
  if (impl.witness_id == SemIR::ErrorInst::InstId) {
    return true;
  }
  if (!impl.generic_id.has_value()) {
    return true;
  }

  if (impl.implicit_param_patterns_id.has_value()) {
    for (auto inst_id :
         context.inst_blocks().Get(impl.implicit_param_patterns_id)) {
      if (inst_id == SemIR::ErrorInst::InstId) {
        // An error was already diagnosed for a generic binding.
        return true;
      }
    }
  }

  auto deduced_specific_id = DeduceImplArguments(
      context, loc_id, impl_id, context.constant_values().Get(impl.self_id),
      impl.interface.specific_id);
  if (deduced_specific_id.has_value()) {
    // Deduction succeeded, all bindings were used.
    return true;
  }

  CARBON_DIAGNOSTIC(ImplUnusedBinding, Error,
                    "`impl` with unused generic binding");
  // TODO: This location may be incorrect, the binding may be inherited
  // from an outer declaration. It would be nice to get the particular
  // binding that was undeducible back from DeduceImplArguments here and
  // use that.
  auto diag_loc_id =
      implicit_params_loc_id.has_value() ? implicit_params_loc_id : loc_id;
  context.emitter().Emit(diag_loc_id, ImplUnusedBinding);
  return false;
}

// Apply an `extend impl` declaration by extending the parent scope with the
// `impl`. If there's an error it is diagnosed and false is returned.
static auto ApplyExtendImplAs(Context& context, SemIR::LocId loc_id,
                              const SemIR::Impl& impl,
                              Parse::NodeId extend_node,
                              SemIR::LocId implicit_params_loc_id) -> bool {
  auto parent_scope_id = context.decl_name_stack().PeekParentScopeId();

  // TODO: Also handle the parent scope being a mixin.
  auto class_scope = TryAsClassScope(context, parent_scope_id);
  if (!class_scope) {
    if (impl.witness_id != SemIR::ErrorInst::InstId) {
      CARBON_DIAGNOSTIC(
          ExtendImplOutsideClass, Error,
          "`extend impl` can only be used in an interface or class");
      context.emitter().Emit(loc_id, ExtendImplOutsideClass);
    }
    return false;
  }

  auto& parent_scope = *class_scope->name_scope;

  // An error was already diagnosed, but this is `extend impl as` inside a
  // class, so propagate the error into the enclosing class scope.
  if (impl.witness_id == SemIR::ErrorInst::InstId) {
    parent_scope.set_has_error();
    return false;
  }

  if (implicit_params_loc_id.has_value()) {
    CARBON_DIAGNOSTIC(ExtendImplForall, Error,
                      "cannot `extend` a parameterized `impl`");
    context.emitter().Emit(extend_node, ExtendImplForall);
    parent_scope.set_has_error();
    return false;
  }

  if (!RequireCompleteType(
          context, context.types().GetTypeIdForTypeInstId(impl.constraint_id),
          SemIR::LocId(impl.constraint_id), [&](auto& builder) {
            CARBON_DIAGNOSTIC(ExtendImplAsIncomplete, Context,
                              "`extend impl as` incomplete facet type {0}",
                              InstIdAsType);
            builder.Context(impl.latest_decl_id(), ExtendImplAsIncomplete,
                            impl.constraint_id);
          })) {
    parent_scope.set_has_error();
    return false;
  }

  if (!impl.generic_id.has_value()) {
    parent_scope.AddExtendedScope(impl.constraint_id);
  } else {
    // The extended scope instruction must be part of the enclosing scope (and
    // generic). A specific for the enclosing scope will be applied to it when
    // using the instruction later. To do so, we wrap the constraint facet type
    // it in a SpecificConstant, which preserves the impl declaration's
    // specific along with the facet type.
    auto constraint_id_in_self_specific = AddTypeInst<SemIR::SpecificConstant>(
        context, SemIR::LocId(impl.constraint_id),
        {.type_id = SemIR::TypeType::TypeId,
         .inst_id = impl.constraint_id,
         .specific_id = context.generics().GetSelfSpecific(impl.generic_id)});
    parent_scope.AddExtendedScope(constraint_id_in_self_specific);
  }
  return true;
}

auto FindImplId(Context& context, const SemIR::Impl& query_impl)
    -> std::variant<RedeclaredImpl, NewImpl> {
  // Look for an existing matching declaration.
  auto lookup_bucket_ref = context.impls().GetOrAddLookupBucket(query_impl);
  // TODO: Detect two impl declarations with the same self type and interface,
  // and issue an error if they don't match.
  for (auto prev_impl_id : lookup_bucket_ref) {
    auto& prev_impl = context.impls().Get(prev_impl_id);

    auto redecl_type = VerifyImplRedecl(context, query_impl, prev_impl);
    switch (redecl_type) {
      case ImplRedeclType::ValidRedecl:
        // Found a valid redecl.
        return RedeclaredImpl{.prev_impl_id = prev_impl_id};
      case ImplRedeclType::Mismatch:
        // Did not match as a redecl, try again.
        break;
      case ImplRedeclType::DiagnosedInvalidRedecl:
        // Found an invalid redecl, which has been diagnosed as such. Treat it
        // as a new decl, with an error.
        return NewImpl{.lookup_bucket = lookup_bucket_ref,
                       .find_had_error = true};
    }
  }

  return NewImpl{.lookup_bucket = lookup_bucket_ref, .find_had_error = false};
}

// Sets the `ImplId` in the `ImplWitnessTable`.
static auto AssignImplIdInWitness(Context& context, SemIR::ImplId impl_id,
                                  SemIR::InstId witness_id) -> void {
  if (witness_id == SemIR::ErrorInst::InstId) {
    return;
  }
  auto witness = context.insts().GetAs<SemIR::ImplWitness>(witness_id);
  auto witness_table =
      context.insts().GetAs<SemIR::ImplWitnessTable>(witness.witness_table_id);
  witness_table.impl_id = impl_id;
  // Note: The `ImplWitnessTable` instruction is `Unique`, so while this marks
  // the instruction as being a dependent instruction of a generic impl, it will
  // not be substituted into the eval block.
  ReplaceInstBeforeConstantUse(context, witness.witness_table_id,
                               witness_table);
}

auto AddImpl(Context& context, const SemIR::Impl& impl,
             SemIR::ImplStore::LookupBucketRef lookup_bucket,
             Parse::NodeId extend_node, SemIR::LocId implicit_params_loc_id)
    -> SemIR::ImplId {
  auto impl_decl_id = impl.latest_decl_id();

  // From here on, use the `Impl` from the `ImplStore` instead of `impl` in
  // order to make and see any changes to the `Impl`.
  auto impl_id = context.impls().Add(impl);
  lookup_bucket.push_back(impl_id);
  AssignImplIdInWitness(context, impl_id, impl.witness_id);

  auto& stored_impl = context.impls().Get(impl_id);

  // Look to see if there are any generic bindings on the `impl` declaration
  // that are not deducible. If so, and the `impl` does not actually use all
  // its generic bindings, and will never be matched. This should be
  // diagnossed to the user.
  if (!VerifyAllGenericBindingsUsed(context, SemIR::LocId(impl_decl_id),
                                    implicit_params_loc_id, impl_id,
                                    stored_impl)) {
    FillImplWitnessWithErrors(context, stored_impl);
  }

  if (extend_node.has_value()) {
    if (!ApplyExtendImplAs(context, SemIR::LocId(impl_decl_id), stored_impl,
                           extend_node, implicit_params_loc_id)) {
      FillImplWitnessWithErrors(context, stored_impl);
    }
  }

  return impl_id;
}

auto AddImplWitnessForDeclaration(Context& context, SemIR::LocId loc_id,
                                  const SemIR::Impl& impl,
                                  SemIR::TypeInstId full_constraint_id,
                                  SemIR::SpecificId self_specific_id)
    -> SemIR::InstId {
  auto facet_type_id =
      context.types().GetTypeIdForTypeInstId(full_constraint_id);
  CARBON_CHECK(facet_type_id != SemIR::ErrorInst::TypeId);
  auto facet_type = context.types().GetAs<SemIR::FacetType>(facet_type_id);
  // TODO: We need to collect rewrites from named constraints too, so we will
  // want to get them from the IdentifiedFacetType, or something similar. That
  // process should also replace `.Self` in the constraints as appropriate.
  const auto& declared_facet_type =
      context.declared_facet_types().Get(facet_type.declared_facet_type_id);

  // An iterator over the rewrite_constraints where the LHS of the rewrite names
  // a member of the `impl.interface`. This filters out rewrites of names
  // from other interfaces, as they do not set values in the witness table.
  auto rewrites_into_interface_to_witness = llvm::make_filter_range(
      declared_facet_type.rewrite_constraints,
      [&](const SemIR::DeclaredFacetType::RewriteConstraint& rewrite) {
        auto access = context.insts().GetAs<SemIR::ImplWitnessAccess>(
            GetImplWitnessAccessWithoutSubstitution(context, rewrite.lhs_id));
        return context.insts().Is<SemIR::ImplSelfWitness>(access.witness_id);
      });

  if (rewrites_into_interface_to_witness.empty()) {
    // The witness table is not needed until the definition. Make a placeholder
    // for the declaration.
    auto witness_table_inst_id = AddInst<SemIR::ImplWitnessTable>(
        context, loc_id,
        {.elements_id = context.inst_blocks().AddPlaceholder(),
         .impl_id = SemIR::ImplId::None});
    return AddInst<SemIR::ImplWitness>(
        context, loc_id,
        {.type_id = GetSingletonType(context, SemIR::WitnessType::TypeInstId),
         .witness_table_id = witness_table_inst_id,
         .specific_id = self_specific_id});
  }

  const auto& interface = context.interfaces().Get(impl.interface.interface_id);
  if (!interface.is_complete()) {
    // This is a declaration with rewrite constraints into `.Self`, but the
    // interface is not complete. Those rewrites have already been diagnosed as
    // an error in their member access.
    return SemIR::ErrorInst::InstId;
  }

  auto assoc_entities =
      context.inst_blocks().Get(interface.associated_entities_id);
  // TODO: When this function is used for things other than just impls, may want
  // to only load the specific associated entities that are mentioned in rewrite
  // rules.
  for (auto decl_id : assoc_entities) {
    LoadImportRef(context, decl_id);
  }

  SemIR::InstId witness_inst_id = SemIR::InstId::None;
  llvm::MutableArrayRef<SemIR::InstId> table;
  {
    auto elements_id =
        context.inst_blocks().AddUninitialized(assoc_entities.size());
    table = context.inst_blocks().GetMutable(elements_id);
    for (auto& uninit : table) {
      uninit = SemIR::InstId::ImplWitnessTablePlaceholder;
    }

    auto witness_table_inst_id = AddInst<SemIR::ImplWitnessTable>(
        context, loc_id,
        {.elements_id = elements_id, .impl_id = SemIR::ImplId::None});

    witness_inst_id = AddInst<SemIR::ImplWitness>(
        context, loc_id,
        {.type_id = GetSingletonType(context, SemIR::WitnessType::TypeInstId),
         .witness_table_id = witness_table_inst_id,
         .specific_id = self_specific_id});
  }

  for (auto rewrite : rewrites_into_interface_to_witness) {
    auto access = context.insts().GetAs<SemIR::ImplWitnessAccess>(
        GetImplWitnessAccessWithoutSubstitution(context, rewrite.lhs_id));
    auto& table_entry = table[access.index.index];
    if (table_entry == SemIR::ErrorInst::InstId) {
      // Don't overwrite an error value. This prioritizes not generating
      // multiple errors for one associated constant over picking a value
      // for it to use to attempt recovery.
      continue;
    }
    auto rewrite_inst_id = rewrite.rhs_id;
    if (rewrite_inst_id == SemIR::ErrorInst::InstId) {
      table_entry = SemIR::ErrorInst::InstId;
      continue;
    }

    // We don't want to leak `.Self` into the witness table, since it loses its
    // meaning outside of the impl declaration. Replace any use of `.Self` here
    // with the impl's self type.
    rewrite_inst_id = context.constant_values().GetInstId(SubstPeriodSelf(
        context, loc_id, context.constant_values().Get(rewrite_inst_id),
        context.constant_values().Get(impl.self_id)));

    auto decl_id = context.constant_values().GetConstantInstId(
        assoc_entities[access.index.index]);
    CARBON_CHECK(decl_id.has_value(), "Non-constant associated entity");
    if (decl_id == SemIR::ErrorInst::InstId) {
      table_entry = SemIR::ErrorInst::InstId;
      continue;
    }

    auto assoc_constant_decl =
        context.insts().TryGetAs<SemIR::AssociatedConstantDecl>(decl_id);
    if (!assoc_constant_decl) {
      auto type_id = context.insts().Get(decl_id).type_id();
      auto type_inst = context.types().GetAsInst(type_id);
      auto fn_type = type_inst.As<SemIR::FunctionType>();
      const auto& fn = context.functions().Get(fn_type.function_id);
      CARBON_DIAGNOSTIC(RewriteForAssociatedFunction, Error,
                        "rewrite specified for associated function {0}",
                        SemIR::NameId);
      context.emitter().Emit(full_constraint_id, RewriteForAssociatedFunction,
                             fn.name_id);
      table_entry = SemIR::ErrorInst::InstId;
      continue;
    }

    // FacetTypes resolution disallows two rewrites to the same associated
    // constant, so we won't ever have a facet write twice to the same position
    // in the witness table.
    CARBON_CHECK(table_entry == SemIR::InstId::ImplWitnessTablePlaceholder);

    // If the associated constant has a symbolic type, convert the rewrite
    // value to that type now we know the value of `Self`.
    SemIR::TypeId assoc_const_type_id = assoc_constant_decl->type_id;
    if (assoc_const_type_id.is_symbolic()) {
      auto self_facet = GetConstantFacetValueForType(context, impl.self_id);
      auto interface_with_self_specific_id = MakeSpecificWithInnerSelf(
          context, loc_id, interface.generic_id, interface.generic_with_self_id,
          impl.interface.specific_id, self_facet);

      // Get the type of the associated constant in this interface with this
      // value for `Self`.
      assoc_const_type_id = GetTypeForSpecificAssociatedEntity(
          context, interface_with_self_specific_id, decl_id);
      // Perform the conversion of the value to the type. We skipped this when
      // forming the facet type because the type of the associated constant
      // was symbolic.
      auto converted_inst_id =
          ConvertToValueOfType(context, SemIR::LocId(full_constraint_id),
                               rewrite_inst_id, assoc_const_type_id);
      // Canonicalize the converted constant value.
      converted_inst_id =
          context.constant_values().GetConstantInstId(converted_inst_id);
      // The result of conversion can be non-constant even if the original
      // value was constant.
      if (converted_inst_id.has_value()) {
        rewrite_inst_id = converted_inst_id;
      } else {
        const auto& assoc_const = context.associated_constants().Get(
            assoc_constant_decl->assoc_const_id);
        CARBON_DIAGNOSTIC(
            AssociatedConstantNotConstantAfterConversion, Error,
            "associated constant {0} given value {1} that is not constant "
            "after conversion to {2}",
            SemIR::NameId, InstIdAsConstant, SemIR::TypeId);
        context.emitter().Emit(
            full_constraint_id, AssociatedConstantNotConstantAfterConversion,
            assoc_const.name_id, rewrite_inst_id, assoc_const_type_id);
        rewrite_inst_id = SemIR::ErrorInst::InstId;
      }
    }

    CARBON_CHECK(rewrite_inst_id == context.constant_values().GetConstantInstId(
                                        rewrite_inst_id),
                 "Rewritten value for associated constant is not canonical.");

    table_entry = AddInst<SemIR::ImplWitnessAssociatedConstant>(
        context, loc_id,
        {.type_id = context.insts().Get(rewrite_inst_id).type_id(),
         .inst_id = rewrite_inst_id});
  }
  return witness_inst_id;
}

auto ImplWitnessStartDefinition(Context& context, SemIR::Impl& impl) -> void {
  CARBON_CHECK(impl.is_being_defined());
  CARBON_CHECK(impl.witness_id.has_value());
  if (impl.witness_id == SemIR::ErrorInst::InstId) {
    return;
  }

  {
    if (!RequireCompleteType(
            context, context.types().GetTypeIdForTypeInstId(impl.constraint_id),
            SemIR::LocId(impl.constraint_id), [&](auto& builder) {
              CARBON_DIAGNOSTIC(
                  ImplAsIncompleteFacetTypeDefinition, Context,
                  "definition of impl as incomplete facet type {0}",
                  InstIdAsType);
              builder.Context(SemIR::LocId(impl.latest_decl_id()),
                              ImplAsIncompleteFacetTypeDefinition,
                              impl.constraint_id);
            })) {
      FillImplWitnessWithErrors(context, impl);
      return;
    }
  }

  const auto& interface = context.interfaces().Get(impl.interface.interface_id);

  auto assoc_entities =
      context.inst_blocks().Get(interface.associated_entities_id);
  for (auto decl_id : assoc_entities) {
    LoadImportRef(context, decl_id);
  }

  auto witness = context.insts().GetAs<SemIR::ImplWitness>(impl.witness_id);
  auto witness_table =
      context.insts().GetAs<SemIR::ImplWitnessTable>(witness.witness_table_id);
  auto witness_block =
      context.inst_blocks().GetMutable(witness_table.elements_id);

  // The impl declaration may have created a placeholder witness table, or a
  // full witness table. We can detect that the witness table is a placeholder
  // table if it's not the `Empty` id, but it is empty still. If it was a
  // placeholder, we can replace the placeholder here with a table of the proper
  // size, since the interface must be complete for the impl definition.
  bool witness_table_is_placeholder =
      witness_table.elements_id != SemIR::InstBlockId::Empty &&
      witness_block.empty();
  if (witness_table_is_placeholder) {
    // TODO: Since our `empty_table` repeats the same value throughout, we could
    // skip an allocation here if there was a `ReplacePlaceholder` function that
    // took a size and value instead of an array of values.
    llvm::SmallVector<SemIR::InstId> empty_table(
        assoc_entities.size(), SemIR::InstId::ImplWitnessTablePlaceholder);
    context.inst_blocks().ReplacePlaceholder(witness_table.elements_id,
                                             empty_table);
    witness_block = context.inst_blocks().GetMutable(witness_table.elements_id);
  }

  // Check we have a value for all non-function associated constants in the
  // witness.
  for (auto [assoc_entity, witness_value] :
       llvm::zip_equal(assoc_entities, witness_block)) {
    auto decl_id = context.constant_values().GetConstantInstId(assoc_entity);
    CARBON_CHECK(decl_id.has_value(), "Non-constant associated entity");
    if (auto decl =
            context.insts().TryGetAs<SemIR::AssociatedConstantDecl>(decl_id)) {
      if (witness_value == SemIR::InstId::ImplWitnessTablePlaceholder) {
        CARBON_DIAGNOSTIC(ImplAssociatedConstantNeedsValue, Error,
                          "associated constant {0} not given a value in impl "
                          "of interface {1}",
                          SemIR::NameId, SemIR::NameId);
        CARBON_DIAGNOSTIC(AssociatedConstantHere, Note,
                          "associated constant declared here");
        context.emitter()
            .Build(impl.definition_id, ImplAssociatedConstantNeedsValue,
                   context.associated_constants()
                       .Get(decl->assoc_const_id)
                       .name_id,
                   interface.name_id)
            .Note(assoc_entity, AssociatedConstantHere)
            .Emit();

        witness_value = SemIR::ErrorInst::InstId;
      }
    }
  }
}

// Adds functions to the witness that the specified impl implements the given
// interface.
auto FinishImplWitness(Context& context, const SemIR::Impl& impl) -> void {
  CARBON_CHECK(impl.is_being_defined());
  CARBON_CHECK(impl.witness_id.has_value());
  if (impl.witness_id == SemIR::ErrorInst::InstId) {
    return;
  }
  auto witness = context.insts().GetAs<SemIR::ImplWitness>(impl.witness_id);
  auto witness_table =
      context.insts().GetAs<SemIR::ImplWitnessTable>(witness.witness_table_id);
  auto witness_block =
      context.inst_blocks().GetMutable(witness_table.elements_id);
  auto& impl_scope = context.name_scopes().Get(impl.scope_id);
  const auto& interface = context.interfaces().Get(impl.interface.interface_id);
  auto assoc_entities =
      context.inst_blocks().Get(interface.associated_entities_id);
  llvm::SmallVector<SemIR::InstId> used_decl_ids;

  auto self_facet = GetConstantFacetValueForTypeAndInterface(
      context, impl.self_id, impl.interface, impl.witness_id);
  auto interface_with_self_specific_id = MakeSpecificWithInnerSelf(
      context, SemIR::LocId(impl.definition_id), interface.generic_id,
      interface.generic_with_self_id, impl.interface.specific_id, self_facet);

  for (auto [assoc_entity, witness_value] :
       llvm::zip_equal(assoc_entities, witness_block)) {
    auto decl_id =
        context.constant_values().GetInstId(SemIR::GetConstantValueInSpecific(
            context.sem_ir(), interface_with_self_specific_id, assoc_entity));
    CARBON_CHECK(decl_id.has_value(), "Non-constant associated entity");
    auto decl = context.insts().Get(decl_id);
    CARBON_KIND_SWITCH(decl) {
      case CARBON_KIND(SemIR::StructValue struct_value): {
        if (struct_value.type_id == SemIR::ErrorInst::TypeId) {
          witness_value = SemIR::ErrorInst::InstId;
          break;
        }
        auto type_inst = context.types().GetAsInst(struct_value.type_id);
        auto fn_type = type_inst.TryAs<SemIR::FunctionType>();
        if (!fn_type) {
          CARBON_FATAL("Unexpected type: {0}", type_inst);
        }
        auto& fn = context.functions().Get(fn_type->function_id);
        auto lookup_result =
            LookupNameInExactScope(context, SemIR::LocId(decl_id), fn.name_id,
                                   impl.scope_id, impl_scope);
        if (lookup_result.is_found()) {
          used_decl_ids.push_back(lookup_result.target_inst_id());
          witness_value = CheckAssociatedFunctionImplementation(
              context, *fn_type,
              context.generics().GetSelfSpecific(impl.generic_id),
              lookup_result.target_inst_id(),
              /*defer_thunk_definition=*/true);
        } else {
          CARBON_DIAGNOSTIC(
              ImplMissingFunction, Error,
              "missing implementation of {0} in impl of interface {1}",
              SemIR::NameId, SemIR::NameId);
          auto builder =
              context.emitter().Build(impl.definition_id, ImplMissingFunction,
                                      fn.name_id, interface.name_id);
          NoteAssociatedFunction(context, builder, fn_type->function_id);
          builder.Emit();

          witness_value = SemIR::ErrorInst::InstId;
        }
        break;
      }
      case SemIR::AssociatedConstantDecl::Kind: {
        // These are set to their final values already.
        break;
      }
      default:
        CARBON_CHECK(decl_id == SemIR::ErrorInst::InstId,
                     "Unexpected kind of associated entity {0}", decl);
        witness_value = SemIR::ErrorInst::InstId;
        break;
    }
  }

  // TODO: Diagnose if any declarations in the impl are not in used_decl_ids.
}

// Replace any `ImplSelfWitness` with the final `ImplWitness`. This causes any
// enclosing ImplWitnessAccess be resolved to the corresponding value from the
// impl's witness table.
static auto SubstImplSelfWitnesses(Context& context, SemIR::LocId loc_id,
                                   SemIR::IdentifiedFacetType::RequiredImpl req,
                                   SemIR::InterfaceId impl_interface_id,
                                   SemIR::InstId witness_id)
    -> SemIR::IdentifiedFacetType::RequiredImpl {
  class Callbacks : public SubstInstCallbacks {
   public:
    explicit Callbacks(Context* context, SemIR::LocId loc_id,
                       SemIR::InterfaceId impl_interface_id,
                       SemIR::InstId witness_id)
        : SubstInstCallbacks(context),
          loc_id_(loc_id),
          impl_interface_id_(impl_interface_id),
          witness_id_(witness_id) {}
    auto Subst(SemIR::InstId& inst_id) -> SubstResult override {
      auto const_inst_id =
          context().constant_values().GetConstantInstId(inst_id);
      if (const_inst_id == SemIR::TypeType::TypeInstId ||
          const_inst_id == SemIR::ErrorInst::InstId) {
        return FullySubstituted;
      }

      auto self_witness =
          context().insts().TryGetAs<SemIR::ImplSelfWitness>(inst_id);
      if (!self_witness) {
        return SubstOperands;
      }
      // It would be nice to check the full specific interface. But the witness
      // has an interface with `.Self` references unresolved, and the impl's
      // specific interface has them resolved. It doesn't seem worth identifying
      // the witness's interface to substitute in the impl's self type just for
      // this CHECK.
      CARBON_CHECK(
          context()
                  .specific_interfaces()
                  .Get(self_witness->specific_interface_id)
                  .interface_id == impl_interface_id_,
          "found incorrect ImplSelfWitness that is not a witness for the "
          "impl's target interface; expected a LookupImplWitness");
      inst_id = witness_id_;
      return FullySubstituted;
    }

    auto Rebuild(SemIR::InstId /*orig_inst_id*/, SemIR::Inst new_inst)
        -> SemIR::InstId override {
      return RebuildNewInst(loc_id_, new_inst);
    }

   private:
    SemIR::LocId loc_id_;
    SemIR::InterfaceId impl_interface_id_;
    SemIR::InstId witness_id_;
  };

  Callbacks callbacks(&context, loc_id, impl_interface_id, witness_id);

  auto self_inst_id = context.constant_values().GetInstId(req.self_facet_value);
  self_inst_id = SubstInst(context, self_inst_id, callbacks);

  auto specific_id = req.specific_interface.specific_id;
  if (specific_id.has_value()) {
    const auto& specific = context.specifics().Get(specific_id);
    llvm::SmallVector<SemIR::InstId> args(
        context.inst_blocks().Get(specific.args_id));
    for (auto& arg_id : args) {
      arg_id = SubstInst(context, arg_id, callbacks);
    }
    specific_id = MakeSpecific(context, loc_id, specific.generic_id, args);
  }

  return {
      .self_facet_value = context.constant_values().Get(self_inst_id),
      .specific_interface = {req.specific_interface.interface_id, specific_id}};
}

auto CheckRequireDeclsSatisfied(Context& context, SemIR::LocId loc_id,
                                SemIR::Impl& impl,
                                SemIR::TypeInstId full_constraint_id) -> void {
  if (impl.witness_id == SemIR::ErrorInst::InstId) {
    return;
  }

  // TODO: Check other kinds of constraints too: rewrites into targets other
  // than `Self.(TargetInterface.__)` and same-type constraints. Consider maybe
  // building a facet type that just excludes anything about the impl-as target
  // interface, and then just perform lookup of Self as that facet type, so we
  // don't have to re-implement all of the validation of impl lookup?

  // The IdentifiedFacetType canonicalizes the self facets, so we do the same
  // for comparing with it.
  auto self_const_id = GetCanonicalFacetOrTypeValue(
      context, context.constant_values().Get(impl.self_id));

  // We already identified the `impl.self_id` as the canonical
  // `full_constraint_id`, so this should just be a cache lookup and can't fail.
  //
  // This is critical because the identification constructs specifics in named
  // constraints which may refer back to the impl itself through access of an
  // associated constant. Those references back to the impl need to be
  // represented as `ImplSelfWitness` which can only be done inside the impl
  // declaration. It is too late to form those specifics here, we need to find
  // the specifics formed during the impl declaration.
  //
  // TODO: Consider a function that just forms the key and returns the ID for an
  // already-identified facet type? Or plumb through the IdentifiedFacetType?
  auto identified_id = TryToIdentifyFacetType(
      context, loc_id, context.constant_values().Get(impl.self_id),
      context.constant_values().GetConstantTypeInstId(
          context.types().GetAsTypeInstId(full_constraint_id)),
      /*allow_partially_identified=*/false);
  CARBON_CHECK(identified_id.has_value());
  const auto& identified = context.identified_facet_types().Get(identified_id);
  for (auto req : identified.required_impls()) {
    if (req.self_facet_value == self_const_id &&
        req.specific_interface == identified.impl_as_target_interface()) {
      // This is what the impl is implementing, so it's not already satisfied.
      continue;
    }

    // Resolve any accesses in the declaration by using the impl's witness
    // table, now that it exists. Since these accesses are from an
    // IdentifiedFacetType first constructed inside the impl declaration, they
    // were originally evaluated before the impl existed.
    req = SubstImplSelfWitnesses(context, loc_id, req,
                                 impl.interface.interface_id, impl.witness_id);

    auto result = LookupImplWitness(
        context, loc_id, req.self_facet_value,
        GetInterfaceType(context, req.specific_interface.interface_id,
                         req.specific_interface.specific_id)
            .AsConstantId());
    if (!result.has_value()) {
      CARBON_DIAGNOSTIC(IdentifiedRequireImplsNotImplemented, Error,
                        "constraint {0} being implemented requires that {1} "
                        "implements `{2}`",
                        SemIR::DeclaredFacetTypeId, InstIdAsConstant,
                        SemIR::SpecificInterface);
      context.emitter().Emit(
          loc_id, IdentifiedRequireImplsNotImplemented,
          context.insts()
              .GetAs<SemIR::FacetType>(
                  context.constant_values().GetConstantInstId(
                      full_constraint_id))
              .declared_facet_type_id,
          context.constant_values().GetInstId(req.self_facet_value),
          req.specific_interface);
    }
    if (!result.has_value() || result.has_error_value()) {
      FillImplWitnessWithErrors(context, impl);
      return;
    }
  }

  const auto& interface = context.interfaces().Get(impl.interface.interface_id);

  auto require_ids =
      context.require_impls_blocks().Get(interface.require_impls_block_id);
  if (require_ids.empty()) {
    return;
  }

  // Make a facet value for the self type.
  auto self_facet = GetConstantFacetValueForType(context, impl.self_id);
  auto interface_with_self_specific_id = MakeSpecificWithInnerSelf(
      context, loc_id, interface.generic_id, interface.generic_with_self_id,
      impl.interface.specific_id, self_facet);

  for (auto require_id : require_ids) {
    const auto& require = context.require_impls().Get(require_id);

    // Each require is in its own generic, with no additional bindings and no
    // definition, so that they can have their specifics independently
    // instantiated.
    auto require_specific_id = CopySpecificToGeneric(
        context, SemIR::LocId(require.decl_id), interface_with_self_specific_id,
        require.generic_id);
    auto req_self_const_id = GetConstantValueInSpecific(
        context.sem_ir(), require_specific_id, require.self_id);
    auto req_facet_type_const_id = GetConstantValueInSpecific(
        context.sem_ir(), require_specific_id, require.facet_type_inst_id);
    if (req_self_const_id == SemIR::ErrorInst::ConstantId ||
        req_facet_type_const_id == SemIR::ErrorInst::ConstantId) {
      FillImplWitnessWithErrors(context, impl);
      return;
    }

    auto result = LookupImplWitness(context, loc_id, req_self_const_id,
                                    req_facet_type_const_id);
    if (!result.has_value()) {
      CARBON_DIAGNOSTIC(InterfaceRequireImplsNotImplemented, Error,
                        "interface `{0}` being implemented requires that {1} "
                        "implements {2}",
                        SemIR::SpecificInterface, SemIR::TypeId,
                        SemIR::DeclaredFacetTypeId);
      context.emitter().Emit(
          loc_id, InterfaceRequireImplsNotImplemented, impl.interface,
          context.types().GetTypeIdForTypeConstantId(req_self_const_id),
          context.constant_values()
              .GetInstAs<SemIR::FacetType>(req_facet_type_const_id)
              .declared_facet_type_id);
    }
    if (!result.has_value() || result.has_error_value()) {
      FillImplWitnessWithErrors(context, impl);
      return;
    }
  }
}

auto FillImplWitnessWithErrors(Context& context, SemIR::Impl& impl) -> void {
  if (impl.witness_id == SemIR::ErrorInst::InstId) {
    return;
  }
  auto witness = context.insts().GetAs<SemIR::ImplWitness>(impl.witness_id);
  auto witness_table =
      context.insts().GetAs<SemIR::ImplWitnessTable>(witness.witness_table_id);
  auto witness_block =
      context.inst_blocks().GetMutable(witness_table.elements_id);
  for (auto& elem : witness_block) {
    if (elem == SemIR::InstId::ImplWitnessTablePlaceholder) {
      elem = SemIR::ErrorInst::InstId;
    }
  }
  impl.witness_id = SemIR::ErrorInst::InstId;
}

auto IsImplEffectivelyFinal(Context& context, const SemIR::Impl& impl) -> bool {
  return impl.is_final ||
         (context.constant_values().Get(impl.self_id).is_concrete() &&
          context.constant_values().Get(impl.constraint_id).is_concrete());
}

auto CheckConstraintIsFacetType(Context& context, SemIR::LocId loc_id,
                                SemIR::TypeInstId constraint_id) -> bool {
  auto facet_type_const_inst_id =
      context.constant_values().GetConstantInstId(constraint_id);
  auto facet_type =
      context.insts().TryGetAs<SemIR::FacetType>(facet_type_const_inst_id);
  if (!facet_type && facet_type_const_inst_id != SemIR::ErrorInst::InstId) {
    CARBON_DIAGNOSTIC(ImplAsNonFacetType, Error, "impl as non-facet type {0}",
                      InstIdAsType);
    context.emitter().Emit(loc_id, ImplAsNonFacetType, constraint_id);
    return false;
  }
  return true;
}

auto CheckConstraintIsInterface(Context& context, SemIR::LocId loc_id,
                                SemIR::InstId self_id,
                                SemIR::TypeInstId constraint_id)
    -> SemIR::SpecificInterface {
  auto canon_constraint_id =
      context.constant_values().GetConstantTypeInstId(constraint_id);
  if (canon_constraint_id == SemIR::ErrorInst::TypeInstId) {
    return SemIR::SpecificInterface::None;
  }
  auto identified_id = RequireIdentifiedFacetType(
      context, SemIR::LocId(constraint_id),
      context.constant_values().Get(self_id), canon_constraint_id,
      [&](auto& builder) {
        CARBON_DIAGNOSTIC(ImplOfUnidentifiedFacetType, Context,
                          "facet type {0} cannot be identified in `impl as`",
                          InstIdAsType);
        builder.Context(loc_id, ImplOfUnidentifiedFacetType, constraint_id);
      });
  if (!identified_id.has_value()) {
    return SemIR::SpecificInterface::None;
  }
  const auto& identified = context.identified_facet_types().Get(identified_id);
  if (!identified.is_valid_impl_as_target()) {
    CARBON_DIAGNOSTIC(ImplOfNotOneInterface, Error,
                      "impl as {0} interfaces, expected 1", int);
    context.emitter().Emit(loc_id, ImplOfNotOneInterface,
                           identified.num_interfaces_to_impl());
    return SemIR::SpecificInterface::None;
  }
  return identified.impl_as_target_interface();
}

auto GetImplInterfaceInSpecific(Context& context, const SemIR::Impl& impl,
                                SemIR::SpecificId specific_id)
    -> SemIR::SpecificInterface {
  if (!specific_id.has_value()) {
    CARBON_CHECK(!impl.generic_id.has_value());
    // The impl is not generic, the specific interface will be concrete.
    return impl.interface;
  }

  CARBON_CHECK(context.specifics().Get(specific_id).generic_id ==
               impl.generic_id);
  // The `interface_inst_id` is an instruction that contains the impl's target
  // specific interface. We get its constant value to apply the impl's specific
  // to that target interface.
  auto interface_in_specific = SemIR::GetConstantValueInSpecific(
      context.sem_ir(), specific_id, impl.interface_inst_id);
  if (interface_in_specific == SemIR::ErrorInst::ConstantId) {
    return SemIR::SpecificInterface::None;
  }
  // The `interface_inst_id` is always an `ImplSelfWitness` at this time.
  auto inst = context.constant_values().GetInstAs<SemIR::ImplSelfWitness>(
      interface_in_specific);
  return context.specific_interfaces().Get(inst.specific_interface_id);
}

}  // namespace Carbon::Check