mirror of
https://github.com/carbon-language/carbon-lang.git
synced 2026-11-15 22:28:14 +00:00
Dana Jansens
9fb428d713
When impl lookup results in an `ImplWitness`, either directly or later through `LookupImplWitness` evaluating to an `ImplWitness` inside some specific, it represents a dependency on the eval blocks of the `ImplDecl` that the `ImplWitness` comes from. The `ImplWitness` contains a `SpecificId` of the `ImplDecl`, and the constants in the witness table must be viewed through that `SpecificId`. The constants may depend on the declaration or the definition block of the `ImplDecl`'s specific, so any use of the witness table from `ImplWitness` requires the specific from the `ImplWitness` to be fully resolved: both the decl and definition blocks. The specific declaration block is always resolved immediately when forming a specific id, so there's nothing to do there. And things are simple when the `ImplWitness` returned from impl lookup is concrete. We would simply resolve the specific definition directly in the evaluation of `LookupImplWitness`. But when the `ImplWitness` is symbolic, meaning there's a dependency on generic parameters in its referenced specific, then we have a dependency on resolving the specific definition in the `ImplWitness` for every specific that gets applied to the `ImplWitness`, eventually resulting in a concrete specific. Previously we attempted to do this by representing a dependency edge from the eval block containing the `ImplWitness` instruction to the definition block of the specific inside the `ImplWitness`. We represented this dependency edge with the `RequireSpecificDefinition` instruction. The challenge with the `RequireSpecificDefinition` instruction was ensuring it always landed in the _same eval block_ as the one holding the symbolic `ImplWitness`. Ultimately, we've found a way to do this without the `RequireSpecificDefinition`. The witness table is accessed through `ImplWitnessAccess`, so we resolve the specific definition before each access to the witness table. If the definition is already resolved, this just costs a lookup of the Specific from the value store. We document the other things we tried, which don't work or were too complex, below. In PR #6236, we added the `RequireSpecificDefinition` instruction in the eval of `LookupImplWitness`, but this is too late. If impl lookup resolved to a symbolic `LookupImplWitness`, the `LookupImplWitness` is added some eval block. Later, we form specifics and re-evaluate that eval block, and the `LookupImplWitness` can evaluate to an `ImplWitness`. Adding the `RequireSpecificDefinition` instruction at this point inserts the instruction into whatever generic's eval block happens to be on the top of the generic stack, not the eval block of the generic we are building a specific for. And indeed we can't add instructions to a generic's eval block later like this, as it would be missing from specifics that were already resolved for the generic. This incorrect insertion shows up as a crash in eval at the CHECK introduced but commented out in [eval.cpp in #7981](https://github.com/carbon-language/carbon-lang/blob/56d9bbc40add1e9263f2f9b2555c3a27292d1725/toolchain/check/eval.cpp#L3507-L3512). This is covered by the `require_specific_impl_definition_through_specific_instantiation.carbon` test. We tried moving the insertion of `RequireSpecificDefinition` to be earlier - at the point where the `LookupImplWitness` is constructed, in the `LookupImplWitness()` function, instead of inside evaluation. This seemed like a straightforwardly correct answer, as the eval block that contains the `LookupImplWitness` will then also contain the `RequireSpecificDefinition`. However, this can cause us to lose the `RequireSpecificDefinition` entirely. Because it's a separate instruction, not an operand of `LookupImplWitness`, it does not get treated as a dependency of the witness. When we do an impl lookup inside an `alias`, we build a generic for the alias and then discard it. This discards the eval block containing the `LookupImplWitness`. Then, in an enclosing generic, we refer to the constructed `AliasDecl` instruction, which pulls all its dependent operands into the enclosing eval block. This pulls in the `LookupImplWitness` into the enclosing eval block, but it does not preserve the `RequireSpecificDefinition`. This is covered by the `require_specific_impl_definition_from_lookup_impl_witness_in_class_definition.carbon` test. We tried having `ImplWitness` evaluation resolve the specific definition of the specific `ImplDecl` it refers to. This seems like the simplest approach by far as we should always be working with the correct eval block and nothing can get lost. However it does not work because of the recursive nature of `ImplWitness`. The `ImplWitness` instruction appears in the declaration of an `ImplDecl`, and the `ImplWitness` holds a `SpecificId` for that same `ImplDecl`. When building a specific `ImplDecl`, we evaluate the `ImplWitness` in the `ImplDecl`'s declaration block which then immediately resolves the specific definition before the declaration is finished. This leads to missing instructions in the specific definition. In short, this puts the dependency edge to the `ImplDecl`'s specific inside the `ImplDecl` itself, which is problematic. We tried wrapping `ImplWitness` in another instruction, `ImplWitnessUse`. Inside the `ImplDecl` declaration there is still `ImplWitness`, but then in the definition there is `ImplWitnessUse` and that is what is returned from the evaluation of `LookupImplWitness`. The `ImplWitnessUse` is an `ImplWitness` plus it ensures the specific referred to by the witness has its definition resolved. However this breaks constant comparisons, as we get different witnesses inside an impl versus outside. The first iteration of this PR's solution had us insert the `RequireSpecificDefinition` into the eval block when we sniffed a `LookupImplWitness` instruction, however that missed cases where impl lookup immediately resolved to a symbolic `ImplWitness`, which is why we now sniff for the `ImplWitness` in the eval block. This is covered by the `require_specific_impl_definition_from_symbolic_impl_in_class_definition.carbon` test. We also originally made a mistake of not inserting `RequireSpecificDefinition` when inside the impl definition that the `ImplWitness` refers to. But we can form specifics ImplWitness values through function signatures, and these must add the dependency edge on that specific ImplDecl definition. This is covered by the `require_specific_impl_definition_from_inside_impl_definition.carbon` test. Finally, we did have a working solution. It was to sniff instructions added to the eval block of a generic, and when an `ImplWitness` is added to the eval block (it is implied that it is symbolic), also add a `RequireSpecificDefinition` to that eval block immediately. We also resolved the definition of a specific referred to by `ImplWitness` when `LookupImplWitness` evaluates to `ImplWitness` to cover the concrete witness case. This complicated the construction of the eval block immensely, however. It caused a situation where adding one inst to the eval block actually adds two, which we needed to avoid when importing. And it required inst-kind specific behaviour in the very general construction of an eval block, completely outside of eval itself.
391 lines
15 KiB
C++
391 lines
15 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
|
|
|
|
#include "toolchain/sem_ir/mangler.h"
|
|
|
|
#include <string>
|
|
|
|
#include "clang/AST/ASTContext.h"
|
|
#include "clang/Basic/TargetInfo.h"
|
|
#include "clang/CodeGen/ModuleBuilder.h"
|
|
#include "common/raw_string_ostream.h"
|
|
#include "llvm/IR/Module.h"
|
|
#include "toolchain/base/kind_switch.h"
|
|
#include "toolchain/sem_ir/entry_point.h"
|
|
#include "toolchain/sem_ir/ids.h"
|
|
#include "toolchain/sem_ir/name_scope.h"
|
|
#include "toolchain/sem_ir/pattern.h"
|
|
#include "toolchain/sem_ir/specific_interface.h"
|
|
#include "toolchain/sem_ir/specific_named_constraint.h"
|
|
#include "toolchain/sem_ir/thunk.h"
|
|
#include "toolchain/sem_ir/typed_insts.h"
|
|
|
|
namespace Carbon::SemIR {
|
|
|
|
Mangler::Mangler(const SemIR::File& sem_ir, int total_ir_count,
|
|
bool use_string_fingerprint)
|
|
: sem_ir_(sem_ir),
|
|
fingerprinter_(
|
|
use_string_fingerprint
|
|
? std::variant<HashInstFingerprinter, StringInstFingerprinter>(
|
|
std::in_place_type<StringInstFingerprinter>, total_ir_count)
|
|
: std::variant<HashInstFingerprinter, StringInstFingerprinter>(
|
|
std::in_place_type<HashInstFingerprinter>,
|
|
total_ir_count)) {}
|
|
|
|
auto Mangler::MangleNameId(llvm::raw_ostream& os, SemIR::NameId name_id)
|
|
-> void {
|
|
CARBON_CHECK(name_id.AsIdentifierId().has_value(),
|
|
"Mangling non-identifier name {0}", name_id);
|
|
os << names().GetAsStringIfIdentifier(name_id);
|
|
}
|
|
|
|
auto Mangler::MangleInverseQualifiedNameScope(llvm::raw_ostream& os,
|
|
SemIR::NameScopeId name_scope_id,
|
|
SemIR::SpecificId specific_id,
|
|
char initial_prefix) -> void {
|
|
// Maintain a stack of names for delayed rendering of interface impls.
|
|
struct NameEntry {
|
|
SemIR::NameScopeId name_scope_id;
|
|
SemIR::SpecificId specific_id;
|
|
|
|
// The prefix emitted before this name component. If '\0', no prefix will be
|
|
// emitted.
|
|
// - Namespace components are separated by '.'.
|
|
// - The two components of an interface are separated by ':'.
|
|
char prefix;
|
|
};
|
|
llvm::SmallVector<NameEntry> names_to_render;
|
|
names_to_render.push_back({.name_scope_id = name_scope_id,
|
|
.specific_id = specific_id,
|
|
.prefix = initial_prefix});
|
|
while (!names_to_render.empty()) {
|
|
auto [name_scope_id, specific_id, prefix] = names_to_render.pop_back_val();
|
|
if (!name_scope_id.has_value()) {
|
|
// TODO: Include something in the mangling to identify the scope for a
|
|
// function-local class, function, or similar. We may need to number
|
|
// these within the enclosing function, as their name need not be unique.
|
|
os << ":enclosed";
|
|
continue;
|
|
}
|
|
if (prefix) {
|
|
os << prefix;
|
|
}
|
|
if (name_scope_id == SemIR::NameScopeId::Package) {
|
|
auto package_id = sem_ir().package_id();
|
|
if (auto ident_id = package_id.AsIdentifierId(); ident_id.has_value()) {
|
|
os << sem_ir().identifiers().Get(ident_id);
|
|
} else {
|
|
// TODO: Handle name conflicts between special package names and raw
|
|
// identifier package names. Note that any change here will also require
|
|
// a change to namespace mangling for imported packages.
|
|
os << package_id.AsSpecialName();
|
|
}
|
|
continue;
|
|
}
|
|
const auto& name_scope = sem_ir().name_scopes().Get(name_scope_id);
|
|
auto next_scope_id = name_scope.parent_scope_id();
|
|
CARBON_KIND_SWITCH(sem_ir().insts().Get(name_scope.inst_id())) {
|
|
case CARBON_KIND(SemIR::ImplDecl impl_decl): {
|
|
const auto& impl = sem_ir().impls().Get(impl_decl.impl_id);
|
|
const auto& interface =
|
|
sem_ir().interfaces().Get(impl.interface.interface_id);
|
|
names_to_render.push_back(
|
|
// We mangle names in an interface without `Self` in the specific
|
|
// since it would just add noise and `Self` is not part of how you
|
|
// name the entities syntactically.
|
|
{.name_scope_id = interface.scope_without_self_id,
|
|
.specific_id = impl.interface.specific_id,
|
|
.prefix = ':'});
|
|
|
|
auto self_const_inst_id =
|
|
constant_values().GetConstantInstId(impl.self_id);
|
|
auto self_inst = insts().Get(self_const_inst_id);
|
|
CARBON_KIND_SWITCH(self_inst) {
|
|
case CARBON_KIND(SemIR::ClassType class_type): {
|
|
const auto& class_info =
|
|
sem_ir().classes().Get(class_type.class_id);
|
|
|
|
names_to_render.push_back(
|
|
{.name_scope_id = class_info.parent_scope_id,
|
|
.specific_id = class_type.specific_id,
|
|
.prefix = '.'});
|
|
|
|
MangleUnqualifiedName(os, class_info, class_type.specific_id);
|
|
break;
|
|
}
|
|
case SemIR::AutoType::Kind:
|
|
case SemIR::BoolType::Kind:
|
|
case SemIR::BoundMethodType::Kind:
|
|
case SemIR::FloatLiteralType::Kind:
|
|
case SemIR::IntLiteralType::Kind:
|
|
case SemIR::NamespaceType::Kind:
|
|
case SemIR::SpecificFunctionType::Kind:
|
|
case SemIR::VtableType::Kind:
|
|
case SemIR::WitnessType::Kind: {
|
|
os << self_inst.kind().ir_name();
|
|
break;
|
|
}
|
|
case CARBON_KIND(SemIR::IntType int_type): {
|
|
os << (int_type.int_kind == SemIR::IntKind::Signed ? "i" : "u")
|
|
<< sem_ir().ints().Get(
|
|
sem_ir()
|
|
.insts()
|
|
.GetAs<SemIR::IntValue>(int_type.bit_width_id)
|
|
.int_id);
|
|
break;
|
|
}
|
|
default: {
|
|
if (self_const_inst_id == SemIR::TypeType::TypeInstId) {
|
|
os << "type";
|
|
break;
|
|
}
|
|
|
|
// Fall back to including a fingerprint.
|
|
MangleFingerprint(os, &sem_ir(), self_const_inst_id);
|
|
break;
|
|
}
|
|
}
|
|
// Skip the tail of the loop that adds the parent name scope to the
|
|
// stack - the scope in which the impl was defined is not part of the
|
|
// mangling, the constraint and interface alone uniquelify identify an
|
|
// impl.
|
|
continue;
|
|
}
|
|
case CARBON_KIND(SemIR::ClassDecl class_decl): {
|
|
MangleUnqualifiedName(os, sem_ir().classes().Get(class_decl.class_id),
|
|
specific_id);
|
|
break;
|
|
}
|
|
case CARBON_KIND(SemIR::InterfaceDecl interface_decl): {
|
|
MangleUnqualifiedName(
|
|
os, sem_ir().interfaces().Get(interface_decl.interface_id),
|
|
specific_id);
|
|
break;
|
|
}
|
|
case CARBON_KIND(SemIR::InterfaceWithSelfDecl interface_with_self_decl): {
|
|
MangleUnqualifiedName(
|
|
os,
|
|
sem_ir().interfaces().Get(interface_with_self_decl.interface_id),
|
|
specific_id);
|
|
// Skip the enclosing `InterfaceDecl` as we already mangled its name.
|
|
next_scope_id =
|
|
sem_ir().name_scopes().Get(next_scope_id).parent_scope_id();
|
|
break;
|
|
}
|
|
case SemIR::Namespace::Kind: {
|
|
os << names().GetIRBaseName(name_scope.name_id());
|
|
break;
|
|
}
|
|
default:
|
|
CARBON_FATAL("Attempting to mangle unsupported SemIR.");
|
|
break;
|
|
}
|
|
if (!name_scope.is_imported_package()) {
|
|
names_to_render.push_back({.name_scope_id = next_scope_id,
|
|
.specific_id = SemIR::SpecificId::None,
|
|
.prefix = '.'});
|
|
}
|
|
}
|
|
}
|
|
|
|
auto Mangler::MangleImpl(SemIR::FunctionId function_id,
|
|
SemIR::SpecificId specific_id, llvm::raw_ostream& os)
|
|
-> void {
|
|
const auto& function = sem_ir().functions().Get(function_id);
|
|
if (SemIR::IsEntryPoint(sem_ir(), function_id)) {
|
|
CARBON_CHECK(!specific_id.has_value(), "entry point should not be generic");
|
|
os << "main";
|
|
return;
|
|
}
|
|
|
|
// Clang should emit C++ function declarations for us.
|
|
if (function_id != sem_ir().global_ctor_id()) {
|
|
const auto* clang_decl =
|
|
sem_ir().clang_decls().Lookup(function.first_decl_id());
|
|
CARBON_CHECK(!clang_decl || !clang_decl->is_imported,
|
|
"Shouldn't mangle C++ function");
|
|
}
|
|
|
|
os << "_C";
|
|
|
|
if (function.name_id.has_value()) {
|
|
MangleNameId(os, function.name_id);
|
|
} else {
|
|
os << "fn";
|
|
}
|
|
char separator = '.';
|
|
|
|
// For a special function, add a marker to disambiguate.
|
|
switch (function.special_function_kind) {
|
|
case SemIR::Function::SpecialFunctionKind::None:
|
|
case SemIR::Function::SpecialFunctionKind::CppThunk:
|
|
break;
|
|
|
|
case SemIR::Function::SpecialFunctionKind::Generated: {
|
|
os << ".";
|
|
const auto& canonical_key = sem_ir()
|
|
.generated_functions()
|
|
.Get(function.generated_function_id())
|
|
.canonical_key;
|
|
auto specific_interface = sem_ir().specific_interfaces().Get(
|
|
canonical_key.specific_interface_id);
|
|
if (specific_interface.specific_id.has_value()) {
|
|
const auto& specific =
|
|
sem_ir().specifics().Get(specific_interface.specific_id);
|
|
// TODO: Should we use the fully qualified name of each argument (and
|
|
// any parameters each type has...) when possible?
|
|
MangleFingerprint(os, &sem_ir(), specific.args_id);
|
|
os << ".";
|
|
}
|
|
MangleFingerprint(
|
|
os, &sem_ir(),
|
|
sem_ir().types().GetTypeInstId(canonical_key.self_type_id));
|
|
// TODO: We want to include the function's parameters here when they are
|
|
// part of the GeneratedFunction::CanonicalKey to disambiguate overloads.
|
|
// Or perhaps using the index of the function in the witness table?
|
|
os << ":core";
|
|
break;
|
|
}
|
|
case SemIR::Function::SpecialFunctionKind::Thunk:
|
|
os << ":thunk";
|
|
if (function.thunk_id().has_value()) {
|
|
const auto& thunk_info = sem_ir().thunks().Get(function.thunk_id());
|
|
if (thunk_info.signature_id.has_value()) {
|
|
const auto& sig_fn =
|
|
sem_ir().functions().Get(thunk_info.signature_id);
|
|
// If this ever becomes possible, we'll need to include the signature
|
|
// name in the mangling too.
|
|
CARBON_CHECK(sig_fn.name_id == function.name_id,
|
|
"Thunk name mismatches signature name");
|
|
MangleInverseQualifiedNameScope(os, sig_fn.parent_scope_id,
|
|
thunk_info.specific_id, ':');
|
|
separator = ':';
|
|
}
|
|
}
|
|
break;
|
|
|
|
case SemIR::Function::SpecialFunctionKind::Builtin:
|
|
CARBON_FATAL("Attempting to mangle declaration of builtin function {0}",
|
|
function.non_generated_builtin_function_kind());
|
|
case SemIR::Function::SpecialFunctionKind::HasCppThunk:
|
|
CARBON_FATAL("C++ functions should have been handled earlier");
|
|
case SemIR::Function::SpecialFunctionKind::CppFunctionPointerThunk:
|
|
CARBON_FATAL("Attempting to mangle call to function pointer");
|
|
}
|
|
|
|
MangleInverseQualifiedNameScope(os, function.parent_scope_id,
|
|
SemIR::SpecificId::None, separator);
|
|
|
|
if (!function.name_id.has_value() ||
|
|
sem_ir().name_scopes().IsPrivateToLibrary(function.name_id,
|
|
function.parent_scope_id)) {
|
|
os << ".";
|
|
MangleFingerprint(os, &sem_ir(), function.first_decl_id());
|
|
}
|
|
|
|
MangleSpecificId(os, specific_id);
|
|
}
|
|
|
|
auto Mangler::Mangle(SemIR::FunctionId function_id,
|
|
SemIR::SpecificId specific_id) -> std::string {
|
|
RawStringOstream os;
|
|
MangleImpl(function_id, specific_id, os);
|
|
return os.TakeStr();
|
|
}
|
|
|
|
auto Mangler::MangleWithPlatform(SemIR::FunctionId function_id,
|
|
SemIR::SpecificId specific_id) -> std::string {
|
|
RawStringOstream os;
|
|
|
|
CARBON_CHECK(sem_ir_.cpp_file());
|
|
// The only platform mangling that's relevant for us is applying a global
|
|
// prefix, if the platform has one.
|
|
// TODO: Cache this rather than parsing the data layout string each time we
|
|
// need it.
|
|
if (char prefix = llvm::DataLayout(sem_ir_.cpp_file()
|
|
->ast_context()
|
|
.getTargetInfo()
|
|
.getDataLayoutString())
|
|
.getGlobalPrefix()) {
|
|
os << prefix;
|
|
}
|
|
MangleImpl(function_id, specific_id, os);
|
|
return os.TakeStr();
|
|
}
|
|
|
|
auto Mangler::MangleSpecificId(llvm::raw_ostream& os,
|
|
SemIR::SpecificId specific_id) -> void {
|
|
// TODO: Add proper support for mangling generic entities. For now we use a
|
|
// fingerprint of the specific arguments, which should be stable across files,
|
|
// but isn't necessarily stable across toolchain changes.
|
|
if (specific_id.has_value()) {
|
|
os << ".";
|
|
MangleFingerprint(os, &sem_ir(),
|
|
sem_ir().specifics().Get(specific_id).args_id);
|
|
}
|
|
}
|
|
|
|
auto Mangler::MangleGlobalVariable(SemIR::InstId pattern_id) -> std::string {
|
|
// Use the name of the first binding in the variable as its mangled name.
|
|
auto var_name_id =
|
|
SemIR::GetFirstBindingNameFromPatternId(sem_ir(), pattern_id);
|
|
if (!var_name_id.has_value()) {
|
|
return std::string();
|
|
}
|
|
|
|
if (const auto* clang_decl = sem_ir().clang_decls().Lookup(pattern_id)) {
|
|
CARBON_CHECK(!clang_decl->is_imported, "Mangling a C++ variable");
|
|
}
|
|
|
|
RawStringOstream os;
|
|
os << "_C";
|
|
|
|
auto var_name = sem_ir().entity_names().Get(var_name_id);
|
|
MangleNameId(os, var_name.name_id);
|
|
MangleInverseQualifiedNameScope(os, var_name.parent_scope_id);
|
|
|
|
if (sem_ir().name_scopes().IsPrivateToLibrary(var_name.name_id,
|
|
var_name.parent_scope_id)) {
|
|
os << ".";
|
|
MangleFingerprint(os, &sem_ir(), pattern_id);
|
|
}
|
|
return os.TakeStr();
|
|
}
|
|
|
|
auto Mangler::MangleVTable(const SemIR::Class& class_info,
|
|
SemIR::SpecificId specific_id) -> std::string {
|
|
RawStringOstream os;
|
|
os << "_C";
|
|
|
|
MangleNameId(os, class_info.name_id);
|
|
MangleInverseQualifiedNameScope(os, class_info.parent_scope_id);
|
|
|
|
if (sem_ir().name_scopes().IsPrivateToLibrary(class_info.name_id,
|
|
class_info.parent_scope_id)) {
|
|
os << ".";
|
|
MangleFingerprint(os, &sem_ir(), class_info.first_decl_id());
|
|
}
|
|
|
|
os << ".$vtable";
|
|
|
|
MangleSpecificId(os, specific_id);
|
|
|
|
return os.TakeStr();
|
|
}
|
|
|
|
auto Mangler::MangleSpecificId(SemIR::SpecificId specific_id) -> std::string {
|
|
RawStringOstream os;
|
|
MangleSpecificId(os, specific_id);
|
|
return os.TakeStr();
|
|
}
|
|
|
|
auto Mangler::MangleUnqualifiedName(llvm::raw_ostream& os,
|
|
const SemIR::EntityWithParamsBase& entity,
|
|
SemIR::SpecificId specific_id) -> void {
|
|
MangleNameId(os, entity.name_id);
|
|
MangleSpecificId(os, specific_id);
|
|
}
|
|
} // namespace Carbon::SemIR
|