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

Code before:
  // constraint. The value of each associated constant may be changed during
  // substitution, replaced with a fully resolved value for the RHS. This allows
  // us to cache work; when a value for an associated constant is found once it
  // can be reused cheaply, avoiding exponential runtime when rewrite rules
  // refer to each other in ways that create exponential references.
  AccessRewriteValues* rewrite_values_;
  // A stack of instructions being replaced in Subst(). When it's an associated
  // constant, then it represents the constant value is being determined,
  // represented as an ImplWitnessAccess.
  //
  // Avoid heap allocations in common cases, if there are chains of instructions
  // in associated constants with a depth at most 16.
  llvm::SmallVector<SemIR::InstId, 16> substs_in_progress_;
};

auto ResolveFacetTypeRewriteConstraints(
    Context& context, SemIR::LocId loc_id,
    llvm::SmallVector<SemIR::FacetTypeInfo::RewriteConstraint>& rewrites)
    -> bool {
  if (rewrites.empty()) {
    return true;
  }

  // Apply rewrite constraints to each other, so that for example:
  // `.X = Y and .Y = ()` becomes `.X = () and .Y = ()`.
  AccessRewriteValues rewrite_values;
  for (auto& constraint : rewrites) {
    if (constraint.lhs_id == SemIR::ErrorInst::InstId ||
        constraint.rhs_id == SemIR::ErrorInst::InstId) {
      continue;
    }
    auto lhs_access =
        context.insts().TryGetAs<SemIR::ImplWitnessAccess>(constraint.lhs_id);
    if (!lhs_access) {
      continue;
    }

    rewrite_values.InsertNotRewritten(context, *lhs_access, constraint.rhs_id);
  }
  for (auto& constraint : rewrites) {
    if (constraint.lhs_id == SemIR::ErrorInst::InstId ||
        constraint.rhs_id == SemIR::ErrorInst::InstId) {
      continue;
    }
    auto lhs_access =
        context.insts().TryGetAs<SemIR::ImplWitnessAccess>(constraint.lhs_id);
    if (!lhs_access) {
      continue;
    }

    auto* lhs_rewrite_value = rewrite_values.FindRef(context, *lhs_access);

Review comment (suggestion):
Optional: We could make this an `else` for the `state == FullyRewritten` check above; if so, I think it could simply check that the previous state was `BeingRewritten`, which might be slightly simpler than having it also check the `inst_id` hasn't changed.

Code after:
                          "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 =
            lhs_rewrite_value->inst_id.index < rhs_subst_inst_id.index
                ? lhs_rewrite_value->inst_id
                : rhs_subst_inst_id;
        auto source_order2 =
            lhs_rewrite_value->inst_id.index >= rhs_subst_inst_id.index
                ? lhs_rewrite_value->inst_id
                : rhs_subst_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(loc_id, AssociatedConstantWithDifferentValues,
                               constraint.lhs_id, source_order1, source_order2);
      }
      return false;
    }

    rewrite_values.SetFullyRewritten(context, *lhs_rewrite_value,
                                     rhs_subst_inst_id);
  }

  // Rebuild the `rewrites` vector with resolved values for the RHS. Drop any
  // duplicate rewrites in the `rewrites` vector by walking through the
  // `rewrite_values` map and dropping the computed RHS value for each LHS the
  // first time we see it, and erasing the constraint from the vector if we see
  // the same LHS again.
  size_t keep_size = rewrites.size();
  for (size_t i = 0; i < keep_size;) {
    auto& constraint = rewrites[i];

    auto lhs_access =
        context.insts().TryGetAs<SemIR::ImplWitnessAccess>(constraint.lhs_id);
    if (!lhs_access) {
      ++i;
      continue;
    }

    auto& rewrite_value = *rewrite_values.FindRef(context, *lhs_access);
    auto rhs_id = std::exchange(rewrite_value.inst_id, SemIR::InstId::None);
    if (rhs_id == SemIR::InstId::None) {
      std::swap(rewrites[i], rewrites[keep_size - 1]);
      --keep_size;
    } else {
      rewrites[i].rhs_id = rhs_id;