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

Code before:
      return &it->second;
    }

    auto InsertNotRewritten(Context& context, SemIR::ImplWitnessAccess access,
                            SemIR::InstId inst_id) -> void {
      map_.insert({GetKey(context, access), {NotRewritten, inst_id}});
    }

    auto SetBeingRewritten(Context& context, SemIR::ImplWitnessAccess access)
        -> void {
      auto it = map_.find({GetKey(context, access)});
      CARBON_CHECK(it != map_.end());
      if (it->second.state == NotRewritten) {
        it->second.state = BeingRewritten;
      }
    }

    auto SetFullyRewritten(Context& context, SemIR::LocId loc_id,
                           SemIR::ImplWitnessAccess access,
                           SemIR::InstId access_inst_id,
                           SemIR::InstId rewritten_to_inst_id)
        -> SemIR::InstId {
      auto it = map_.find({GetKey(context, access)});
      CARBON_CHECK(it != map_.end());
      if (it->second.state == FullyRewritten) {
        auto ord = CompareFacetTypeConstraintValues(context, it->second.inst_id,
                                                    rewritten_to_inst_id);
        if (ord != std::weak_ordering::equivalent) {
          if (it->second.inst_id != SemIR::ErrorInst::InstId &&
              rewritten_to_inst_id != SemIR::ErrorInst::InstId) {
            CARBON_DIAGNOSTIC(AssociatedConstantWithDifferentValues, Error,
                              "associated constant {0} given two different "
                              "values {1} and {2}",
                              InstIdAsConstant, InstIdAsConstant,
                              InstIdAsConstant);
            // Use inst id ordering as a simple proxy for source ordering, to
            // try to name the values in the same order they appear in the facet
            // type.
            auto source_order1 =
                it->second.inst_id.index < rewritten_to_inst_id.index
                    ? it->second.inst_id
                    : rewritten_to_inst_id;
            auto source_order2 =
                it->second.inst_id.index >= rewritten_to_inst_id.index
                    ? it->second.inst_id
                    : rewritten_to_inst_id;
            // TODO: It would be nice to note the places where the values are
            // assigned but rewrite constraint instructions are from canonical
            // constant values, and have no locations. We'd need to store a
            // location along with them in the rewrite constraints.
            context.emitter().Emit(

Review comment (suggestion):
I think this can be simplified further: this is the only caller of `CompareFacetTypeConstraintValues` and only cares about equality, so we can remove the ordering part of it and just do an equality comparison. I think the equality comparison we want would reduce to `context.constant_values().GetConstantInstId(it->second.inst_id) == context.constant_values().GetConstantInstId(rewritten_to_inst_id)`.

Code after:
    }
  };

  auto GetKey(Context& context, SemIR::ImplWitnessAccess access) -> Key {
    return {*GetFacetTypeConstraintValue(context, access)};
  }

  // Try avoid heap allocations in the common case where there are a small
  // number of rewrite rules referring to each other by keeping up to 16 on
  // the stack.
  //
  // TODO: Revisit if 16 is an appropriate number when we can measure how deep
  // rewrite constraint chains go in practice.
  llvm::SmallDenseMap<Key, Value, 16, KeyInfo> map_;
};

// To be used for substituting into the RHS of a rewrite constraint.
//
// It will substitute any `ImplWitnessAccess` into `.Self` (a reference to an
// associated constant) with the RHS of another rewrite constraint that writes
// 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.
//
// The `rewrite_values` given to the constructor must be set up initially with
// each rewrite rule of an associated constant inserted with its unresolved
// value via `InsertNotRewritten`. Then for each rewrite rule of an associated
// constant, the LHS access should be set as being rewritten with its state
// changed to `BeingRewritten` in order to detect cycles before performing
// SubstInst. The result of SubstInst should be preserved afterward by changing
// the state and value for the LHS to `FullyRewritten` and the subst output
// instruction, respectively, to avoid duplicating work.
class SubstImplWitnessAccessCallbacks : public SubstInstCallbacks {
 public:
  explicit SubstImplWitnessAccessCallbacks(Context* context,
                                           SemIR::LocId loc_id,
                                           AccessRewriteValues* rewrite_values)