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

Code before:
// ```
// Here the second `.X` is an `ImplWitnessAccess` which would be substituted by
// finding the first rewrite constraint, where the LHS is for the same
// associated constant and using its RHS. So the substitution would produce:
// ```
// Z where .X = () and .Y = ()
// ```
//
// This additionally diagnoses cycles when the `ImplWitnessAccess` is reading
// from the same rewrite constraint, and is thus assigning to the associated
// constant a value that refers to the same associated constant, such as with
// `Z where .X = C(.X)`. In the event of a cycle, the `ImplWitnessAccess` is
// replaced with `ErrorInst` so that further evaluation of the
// `ImplWitnessAccess` will not loop infinitely.
class SubstImplWitnessAccessCallbacks : public SubstInstCallbacks {
 public:
  // The `facet_type_info` is for the facet whose rewrite constraints are being
  // substituted, and where it looks for rewritten values to substitute from.
  //
  // The `substituting_constaint` is the rewrite constraint for which the RHS is
  // being substituted with the value from another rewrite constraint, if
  // possible. That is, `.Y = .X` in the example in the class docs.
  explicit SubstImplWitnessAccessCallbacks(
      Context* context, SemIR::LocId loc_id,
      const SemIR::FacetTypeInfo* facet_type_info,
      const SemIR::FacetTypeInfo::RewriteConstraint* substituting_constaint)
      : SubstInstCallbacks(context),
        loc_id_(loc_id),
        facet_type_info_(facet_type_info),
        substituting_constaint_(substituting_constaint) {}

  auto Subst(SemIR::InstId& rhs_inst_id) const -> bool override {
    if (context().constant_values().Get(rhs_inst_id).is_concrete()) {
      return true;
    }

    auto rhs_access =
        TryGetImplWitnessAccessOfPeriodSelf(context(), rhs_inst_id);
    if (!rhs_access) {
      return false;
    }

    // TODO: We could consider replacing this loop, which makes for an O(N^2)
    // algorithm with something more efficient for searching, such as a map.
    // However that would probably require heap allocations which may be worse
    // overall since the number of rewrite constraints is generally low.
    for (const auto& search_constraint :
         facet_type_info().rewrite_constraints) {
      auto search_lhs_access = TryGetImplWitnessAccessOfPeriodSelf(
          context(), search_constraint.lhs_id);
      if (!search_lhs_access) {

Review comment (suggestion):
```suggestion
      const SemIR::FacetTypeInfo::RewriteConstraint* substituting_constraint)
```

(and likewise for the other occurrences of `substituting_constaint`)

Code after:
// ```
// Here the second `.X` is an `ImplWitnessAccess` which would be substituted by
// finding the first rewrite constraint, where the LHS is for the same
// associated constant and using its RHS. So the substitution would produce:
// ```
// Z where .X = () and .Y = ()
// ```
//
// This additionally diagnoses cycles when the `ImplWitnessAccess` is reading
// from the same rewrite constraint, and is thus assigning to the associated
// constant a value that refers to the same associated constant, such as with
// `Z where .X = C(.X)`. In the event of a cycle, the `ImplWitnessAccess` is
// replaced with `ErrorInst` so that further evaluation of the
// `ImplWitnessAccess` will not loop infinitely.
class SubstImplWitnessAccessCallbacks : public SubstInstCallbacks {
 public:
  // The `facet_type_info` is for the facet whose rewrite constraints are being
  // substituted, and where it looks for rewritten values to substitute from.
  //
  // The `substituting_constraint` is the rewrite constraint for which the RHS
  // is being substituted with the value from another rewrite constraint, if
  // possible. That is, `.Y = .X` in the example in the class docs.
  explicit SubstImplWitnessAccessCallbacks(
      Context* context, SemIR::LocId loc_id,
      const SemIR::FacetTypeInfo* facet_type_info,
      const SemIR::FacetTypeInfo::RewriteConstraint* substituting_constraint)
      : SubstInstCallbacks(context),
        loc_id_(loc_id),
        facet_type_info_(*facet_type_info),
        substituting_constraint_(substituting_constraint) {}

  auto Subst(SemIR::InstId& rhs_inst_id) const -> bool override {
    if (context().constant_values().Get(rhs_inst_id).is_concrete()) {
      return true;
    }

    auto rhs_access =
        TryGetImplWitnessAccessOfPeriodSelf(context(), rhs_inst_id);
    if (!rhs_access) {
      return false;
    }

    // TODO: We could consider replacing this loop, which makes for an O(N^2)
    // algorithm with something more efficient for searching, such as a map.
    // However that would probably require heap allocations which may be worse
    // overall since the number of rewrite constraints is generally low.
    for (const auto& search_constraint : facet_type_info_.rewrite_constraints) {
      auto search_lhs_access = TryGetImplWitnessAccessOfPeriodSelf(
          context(), search_constraint.lhs_id);
      if (!search_lhs_access) {
        continue;