Files
carbon-lang/toolchain/check/subst.h
Dana Jansens eb66bebc35 New specifics formed during identify need to be marked identified (#8003)
We were explicitly marking the specifics of `require` decls as
`identified` when creating them during identify. But the require may
contain calls to other generics internally. And forming the specific for
the `require` can also form new specifics for those calls, if they
depend on `Self`. The resulting specific can have `IdentifiedWitness`
instructions in its arguments, in accesses or FacetValues, etc. Or they
may appear in the decl block as it's resolved. So it's very important
that the specifics be marked `identified`, as those witnesses may only
appear in `identified` specifics. This allows the new
`access_through_nested_specific_in_named_constraint.carbon` test to
succeed without any poisoning errors.

SemIR formatting is changed so that `identified` specifics are more
clearly differentiated where they are used, so that we can see if
`identified` specifics are misused outside of identifying.

Now that we construct more `identified` specifics, we also need to
ensure we remove the `identified` state from specifics that come out of
`EvaluateIdentifiedWitnesses` and `SubstIdentifiedWitnesses`. To do that
we add a new callback method on `SubstInstCallbacks` that we use to
build specifics during subst. Then during those operations, we drop the
`identified` flag from any specific that we form, because we know that
we have also removed any `IdentifiedWitness` instructions because:
- We replace them all from arguments during subst.
- We CHECK that we're not in the middle of identifying before starting
the subst.

However now an `IdentifiedFacetType` is not fully deduped, because it
may contain a non-identified specific that comes from a
`DeclaredFacetType` along with an identified specific that comes from a
named constraint, where they have the same arguments. That results in
the `IdentifiedFacetType` having two specific interfaces when it really
only refers to one. The
`fail_todo_impl_as_constraint_duplicates_interface.carbon` test
demonstrates this, and that we then diagnose an `impl` as invalid since
we find more than one specific interface being extended. To fix this we
need to dedupe and count specific interfaces _after_
substituting/evaluating away the IdentifiedWitnesses. This is left to
future work.
2026-10-20 21:18:50 +00:00

131 lines
5.6 KiB
C++

// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#ifndef CARBON_TOOLCHAIN_CHECK_SUBST_H_
#define CARBON_TOOLCHAIN_CHECK_SUBST_H_
#include "toolchain/check/context.h"
#include "toolchain/sem_ir/ids.h"
namespace Carbon::Check {
// Callbacks used by SubstInst to recursively substitute into and rebuild an
// instruction.
class SubstInstCallbacks {
public:
explicit SubstInstCallbacks(Context* context) : context_(context) {}
auto context() const -> Context& { return *context_; }
// How further substitution should or should not be applied to the instruction
// after Subst is done.
//
// Rebuild or ReuseUnchaged will always be called when SubstAgain or
// SubstOperands is returned, after processing anything inside the instruction
// after Subst.
enum SubstResult {
// Don't substitute into the operands of the instruction.
FullySubstituted,
// Attempt to substitute into the operands of the instruction.
SubstOperands,
// Attempt to substitute into the operands of the instruction, but omit the
// instruction's `type_id` if it has one.
SubstOperandsSkipType,
// Attempt to substitute again on the resulting instruction, acting like
// recursion on the instruction itself.
SubstAgain,
// Attempt to substitute into the operands of the instruction. If the InstId
// returned from Rebuild or ReuseUnchanged differs from the input (typically
// because some operand in the instruction changed), then the new
// instruction will be given to `Subst` again afterward. This allows for the
// uncommon case of substituting from the inside out.
SubstOperandsAndRetry,
};
// Performs any needed substitution into an instruction. The instruction ID
// should be updated as necessary to represent the new instruction.
//
// Return FullySubstituted if the resulting instruction ID is
// fully-substituted. Return SubstOperands if substitution may be needed into
// operands of the instruction, or SubstAgain if the replaced instruction
// itself should have substitution applied to it again. Return
// SubstOperandsAndRetry to recurse on the instructions operands and then
// substitute the resulting instruction afterward, if the instruction is
// replaced by a new one (typically due to Rebuild when the operands changed).
//
// When SubstOperands, SubstAgain, or SubstOperandsAndRetry is returned, it
// results in a call back to Rebuild or ReuseUnchanged when that instruction's
// substitution step is complete.
virtual auto Subst(SemIR::InstId& inst_id) -> SubstResult = 0;
// Rebuilds the type of an instruction from the substituted type instruction.
// By default this builds the unattached type described by the given type ID.
virtual auto RebuildType(SemIR::TypeInstId type_inst_id) const
-> SemIR::TypeId;
// Rebuilds an instruction whose operands were changed by substitution.
// `orig_inst_id` is the instruction prior to substitution, and `new_inst` is
// the substituted instruction. Returns the new instruction ID to use to refer
// to `new_inst`.
virtual auto Rebuild(SemIR::InstId orig_inst_id, SemIR::Inst new_inst)
-> SemIR::InstId = 0;
// Performs any work needed when no substitutions were performed into an
// instruction for which `Subst` returned `false`. Provides an opportunity to
// perform any necessary updates to the instruction beyond updating its
// operands. Returns the new instruction ID to use to refer to `orig_inst_id`.
virtual auto ReuseUnchanged(SemIR::InstId orig_inst_id) -> SemIR::InstId {
return orig_inst_id;
}
// Rebuilds a specific given the original specific's ID and the new
// arguments. By default this just calls GetOrAdd to make the specific, but
// does not resolve the specific's decl block.
virtual auto RebuildSpecific(SemIR::SpecificId orig_specific_id,
SemIR::InstBlockId args_id) -> SemIR::SpecificId;
// Builds a new constant by evaluating `new_inst`, and returns its `InstId`.
//
// This can be used to implement `Rebuild` in straightforward cases.
auto RebuildNewInst(SemIR::LocId loc_id, SemIR::Inst new_inst) const
-> SemIR::InstId;
template <typename InstT>
auto RebuildNewInst(SemIR::LocId loc_id, InstT new_inst) const
-> SemIR::InstId {
return RebuildNewInst(loc_id, static_cast<SemIR::Inst>(new_inst));
}
private:
Context* context_;
};
// Performs substitution into `inst_id` and its operands recursively, using
// `callbacks` to process each instruction. For each instruction encountered,
// calls `Subst` to perform substitution on that instruction.
auto SubstInst(Context& context, SemIR::InstId inst_id,
SubstInstCallbacks& callbacks) -> SemIR::InstId;
auto SubstInst(Context& context, SemIR::TypeInstId inst_id,
SubstInstCallbacks& callbacks) -> SemIR::TypeInstId;
// A substitution that is being performed.
struct Substitution {
// The index of a `SymbolicBinding` instruction that is being replaced.
SemIR::CompileTimeBindIndex bind_id;
// The replacement constant value to substitute.
SemIR::ConstantId replacement_id;
};
using Substitutions = llvm::ArrayRef<Substitution>;
// Replaces the `SymbolicBinding` instruction `bind_id` with `replacement_id`
// throughout the constant `const_id`, and returns the substituted value.
auto SubstConstant(Context& context, SemIR::LocId loc_id,
SemIR::ConstantId const_id, Substitutions substitutions)
-> SemIR::ConstantId;
} // namespace Carbon::Check
#endif // CARBON_TOOLCHAIN_CHECK_SUBST_H_