Repository: carbon-language/carbon-lang
File: toolchain/check/impl_lookup.cpp (C++)

Code before:
  // Deduction of the interface parameters can do further impl lookups, and we
  // need to ensure we terminate.
  //
  // https://docs.carbon-lang.dev/docs/design/generics/details.html#acyclic-rule
  // - We look for violations of the acyclic rule by seeing if a previous lookup
  //   had all the same type inputs.
  // - The `interface_const_id` encodes the entire facet type being looked up,
  //   including any specific parameters for a generic interface.
  //
  // TODO: Implement the termination rule, which requires looking at the
  // complexity of the types on the top of (or throughout?) the stack:
  // https://docs.carbon-lang.dev/docs/design/generics/details.html#termination-rule
  for (auto entry : stack) {
    if (entry.type_const_id == type_const_id &&
        entry.interface_const_id == interface_const_id) {
      CARBON_DIAGNOSTIC(ImplLookupCycle, Error,
                        "cycle found in lookup of interface {0} for type {1}",
                        std::string, SemIR::TypeId);
      context.emitter()
          .Build(loc_id, ImplLookupCycle, "<TODO: interface name>",
                 context.GetTypeIdForTypeConstant(type_const_id))
          .Emit();
      return SemIR::ErrorInst::SingletonInstId;
    }
  }
  stack.push_back(Context::ImplLookupStackEntry{
      .type_const_id = type_const_id,
      .interface_const_id = interface_const_id,
  });
  auto pop_stack = llvm::make_scope_exit([&] { stack.pop_back(); });

  for (const auto& impl : context.impls().array_ref()) {
    // If impl.constraint_id is not symbolic, and doesn't match the query, then
    // we don't need to proceed.
    auto impl_interface_const_id =
        context.constant_values().Get(impl.constraint_id);
    if (!impl_interface_const_id.is_symbolic() &&
        interface_const_id != impl_interface_const_id) {
      continue;
    }

    // TODO: If the interface id of the `impl` and the query are not the same,
    // then we can skip this `impl`. (The interface id is the root of the
    // constraint, the unique `interface` declaration.)

    auto specific_id = SemIR::SpecificId::None;
    // This check comes first to avoid deduction with an invalid impl. We use an
    // error value to indicate an error during creation of the impl, such as a
    // recursive impl which will cause deduction to recurse infinitely.
    if (impl.witness_id == SemIR::ErrorInst::SingletonInstId) {
      continue;

Review comment (suggestion):
```suggestion
  stack.push_back({
```

Style: https://github.com/carbon-language/carbon-lang/blob/trunk/docs/project/cpp_style_guide.md#syntax-and-formatting

"Prefer to only include the typename when required to compile (WizType{.a = 1})."

Code after:
  // recursive impl which will cause deduction to recurse infinitely.
  if (impl.witness_id == SemIR::ErrorInst::SingletonInstId) {
    return SemIR::InstId::None;
  }
  if (impl.generic_id.has_value()) {
    specific_id = DeduceImplArguments(context, loc_id, impl, type_const_id,
                                      interface_const_id);
    if (!specific_id.has_value()) {
      return SemIR::InstId::None;
    }
  }
  if (!context.constant_values().AreEqualAcrossDeclarations(
          SemIR::GetConstantValueInSpecific(context.sem_ir(), specific_id,
                                            impl.self_id),
          type_const_id)) {
    return SemIR::InstId::None;
  }
  if (!context.constant_values().AreEqualAcrossDeclarations(
          SemIR::GetConstantValueInSpecific(context.sem_ir(), specific_id,
                                            impl.constraint_id),
          interface_const_id)) {
    // TODO: An impl of a constraint type should be treated as implementing
    // the constraint's interfaces.
    return SemIR::InstId::None;
  }
  if (!impl.witness_id.has_value()) {
    // TODO: Diagnose if the impl isn't defined yet?
    return SemIR::InstId::None;
  }
  LoadImportRef(context, impl.witness_id);
  if (specific_id.has_value()) {
    // We need a definition of the specific `impl` so we can access its
    // witness.
    ResolveSpecificDefinition(context, loc_id, specific_id);
  }
  return context.constant_values().GetInstId(SemIR::GetConstantValueInSpecific(
      context.sem_ir(), specific_id, impl.witness_id));
}

auto LookupImplWitness(Context& context, SemIR::LocId loc_id,
                       SemIR::ConstantId type_const_id,
                       SemIR::ConstantId interface_const_id) -> SemIR::InstId {
  if (type_const_id == SemIR::ErrorInst::SingletonConstantId ||
      interface_const_id == SemIR::ErrorInst::SingletonConstantId) {
    return SemIR::ErrorInst::SingletonInstId;
  }
  auto import_irs =
      FindAssociatedImportIRs(context, type_const_id, interface_const_id);
  for (auto import_ir : import_irs) {
    // TODO: Instead of importing all impls, only import ones that are in some
    // way connected to this query.