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

Code before:
// ```
// Z where .X = () and .Y = .X
// ```
// 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:
  explicit SubstImplWitnessAccessCallbacks(
      Context* context, SemIR::LocId loc_id,
      const SemIR::FacetTypeInfo* facet_type,
      const SemIR::FacetTypeInfo::RewriteConstraint* current_constraint)
      : SubstInstCallbacks(context),
        loc_id_(loc_id),
        facet_type_(facet_type),
        current_constraint_(current_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().rewrite_constraints) {
      if (search_constraint.lhs_id == SemIR::ErrorInst::InstId ||
          search_constraint.rhs_id == SemIR::ErrorInst::InstId) {
        continue;
      }

      auto search_lhs_access = TryGetImplWitnessAccessOfPeriodSelf(
          context(), search_constraint.lhs_id);
      if (!search_lhs_access) {

Review comment (suggestion):
Could this have a comment, particularly to explain the parameters? For example, my guess is that `current_constraint` is the constraint being substituted into (`.Y = .X` in the example), but I'm not sure about that.

Code after:
// to the same associated constant. For example:
// ```
// Z where .X = () and .Y = .X
// ```
// 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(