Skip to content
This repository was archived by the owner on Apr 10, 2025. It is now read-only.

Commit 76c6815

Browse files
danakjzygoloid
danakj
and
zygoloid
authored
Look for final impl when accessing associated constant in facet (#5269)
While facets may come with a rewrite for an associated constant, they are symbolic. A final impl has the ability to provide a concrete value instead, which allows generic code to use the concrete value in place of the associated constant's (fully qualified) name. For instance, instead of `I.Type`, the concrete type `()` can be used if there is an `impl final [T:! type] T as I where .Type = ()` impl. This does not yet cache the result of the lookups. Depends on carbon-language/carbon-lang#5255 --------- Co-authored-by: Richard Smith <richard@metafoo.co.uk>
1 parent 68111a9 commit 76c6815

11 files changed

Lines changed: 2247 additions & 109 deletions

File tree

‎toolchain/check/BUILD‎

Lines changed: 2 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ cc_library(
2929
"function.cpp",
3030
"generic.cpp",
3131
"global_init.cpp",
32+
"impl.cpp",
3233
"impl_lookup.cpp",
3334
"import.cpp",
3435
"import_cpp.cpp",
@@ -68,6 +69,7 @@ cc_library(
6869
"function.h",
6970
"generic.h",
7071
"global_init.h",
72+
"impl.h",
7173
"impl_lookup.h",
7274
"import.h",
7375
"import_cpp.h",
@@ -166,7 +168,6 @@ cc_library(
166168
":context",
167169
":diagnostic_emitter",
168170
":dump",
169-
":impl",
170171
":pointer_dereference",
171172
"//common:check",
172173
"//common:error",
@@ -223,21 +224,6 @@ cc_library(
223224
],
224225
)
225226

226-
cc_library(
227-
name = "impl",
228-
srcs = ["impl.cpp"],
229-
hdrs = ["impl.h"],
230-
deps = [
231-
":context",
232-
"//common:check",
233-
"//toolchain/base:kind_switch",
234-
"//toolchain/diagnostics:diagnostic_emitter",
235-
"//toolchain/sem_ir:file",
236-
"//toolchain/sem_ir:inst",
237-
"//toolchain/sem_ir:typed_insts",
238-
],
239-
)
240-
241227
cc_library(
242228
name = "node_stack",
243229
srcs = ["node_stack.cpp"],

‎toolchain/check/handle_impl.cpp‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -364,11 +364,12 @@ static auto BuildImplDecl(Context& context, Parse::AnyImplDeclId node_id,
364364

365365
// Process modifiers.
366366
// TODO: Should we somehow permit access specifiers on `impl`s?
367-
// TODO: Handle `final` modifier.
368367
auto introducer =
369368
context.decl_introducer_state_stack().Pop<Lex::TokenKind::Impl>();
370369
LimitModifiersOnDecl(context, introducer, KeywordModifierSet::ImplDecl);
371370

371+
bool is_final = introducer.modifier_set.HasAnyOf(KeywordModifierSet::Final);
372+
372373
// Finish processing the name, which should be empty, but might have
373374
// parameters.
374375
auto name_context = context.decl_name_stack().FinishImplName();
@@ -387,7 +388,8 @@ static auto BuildImplDecl(Context& context, Parse::AnyImplDeclId node_id,
387388
{.self_id = self_inst_id,
388389
.constraint_id = constraint_inst_id,
389390
.interface = CheckConstraintIsInterface(
390-
context, impl_decl_id, constraint_inst_id)}};
391+
context, impl_decl_id, constraint_inst_id),
392+
.is_final = is_final}};
391393
// Add the impl declaration.
392394
bool invalid_redeclaration = false;
393395
auto lookup_bucket_ref = context.impls().GetOrAddLookupBucket(impl_info);

‎toolchain/check/impl.cpp‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -249,4 +249,10 @@ auto FillImplWitnessWithErrors(Context& context, SemIR::Impl& impl) -> void {
249249
}
250250
}
251251

252+
auto IsImplEffectivelyFinal(Context& context, const SemIR::Impl& impl) -> bool {
253+
return impl.is_final ||
254+
(context.constant_values().Get(impl.self_id).is_concrete() &&
255+
context.constant_values().Get(impl.constraint_id).is_concrete());
256+
}
257+
252258
} // namespace Carbon::Check

‎toolchain/check/impl.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,10 @@ auto FinishImplWitness(Context& context, SemIR::Impl& impl) -> void;
2626
// Sets all unset members of the witness for `impl` to the error instruction.
2727
auto FillImplWitnessWithErrors(Context& context, SemIR::Impl& impl) -> void;
2828

29+
// Returns whether the impl is either `final` explicitly, or implicitly due to
30+
// being concrete.
31+
auto IsImplEffectivelyFinal(Context& context, const SemIR::Impl& impl) -> bool;
32+
2933
} // namespace Carbon::Check
3034

3135
#endif // CARBON_TOOLCHAIN_CHECK_IMPL_H_

‎toolchain/check/impl_lookup.cpp‎

Lines changed: 68 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
#include "toolchain/check/diagnostic_helpers.h"
1313
#include "toolchain/check/eval.h"
1414
#include "toolchain/check/generic.h"
15+
#include "toolchain/check/impl.h"
1516
#include "toolchain/check/import_ref.h"
1617
#include "toolchain/check/inst.h"
1718
#include "toolchain/check/type.h"
@@ -220,6 +221,7 @@ static auto GetWitnessIdForImpl(Context& context, SemIR::LocId loc_id,
220221
// DeduceImplArguments can import new impls which can invalidate any
221222
// pointers into `context.impls()`.
222223
const SemIR::Impl& impl = context.impls().Get(impl_id);
224+
223225
if (impl.generic_id.has_value()) {
224226
specific_id =
225227
DeduceImplArguments(context, loc_id,
@@ -290,11 +292,12 @@ static auto GetWitnessIdForImpl(Context& context, SemIR::LocId loc_id,
290292
ResolveSpecificDefinition(context, loc_id, specific_id);
291293
}
292294

293-
bool impl_is_effectively_final =
294-
// TODO: impl.is_final ||
295-
(context.constant_values().Get(impl.self_id).is_concrete() &&
296-
context.constant_values().Get(impl.constraint_id).is_concrete());
297-
if (query_is_concrete || impl_is_effectively_final) {
295+
if (query_is_concrete || IsImplEffectivelyFinal(context, impl)) {
296+
// TODO: These final results should be cached somehow. Positive (non-None)
297+
// results could be cached globally, as they can not change. But
298+
// negative results can change after a final impl is written, so
299+
// they can only be cached in a limited way, or the cache needs to
300+
// be invalidated by writing a final impl that would match.
298301
return EvalImplLookupResult::MakeFinal(
299302
context.constant_values().GetInstId(SemIR::GetConstantValueInSpecific(
300303
context.sem_ir(), specific_id, impl.witness_id)));
@@ -340,9 +343,9 @@ static auto FindWitnessInFacet(
340343
// if not, it will evaluate to itself as a symbolic witness to be further
341344
// evaluated with a more specific query when building a specific for the generic
342345
// context the query came from.
343-
static auto FindWitnessInImpls(Context& context, SemIR::LocId loc_id,
344-
SemIR::ConstantId query_self_const_id,
345-
SemIR::SpecificInterface interface)
346+
static auto GetOrAddLookupImplWitness(Context& context, SemIR::LocId loc_id,
347+
SemIR::ConstantId query_self_const_id,
348+
SemIR::SpecificInterface interface)
346349
-> SemIR::InstId {
347350
auto witness_const_id = EvalOrAddInst(
348351
context, loc_id.ToImplicit(),
@@ -434,9 +437,12 @@ auto LookupImplWitness(Context& context, SemIR::LocId loc_id,
434437
// do an O(N+M) merge instead of O(N*M) nested loops.
435438
auto result_witness_id =
436439
FindWitnessInFacet(context, loc_id, query_self_const_id, interface);
440+
// TODO: If the impl lookup finds a final impl, it should take precedence
441+
// over the witness from the facet value. See the test:
442+
// fail_todo_final_impl_precidence_over_facet_value.carbon.
437443
if (!result_witness_id.has_value()) {
438-
result_witness_id =
439-
FindWitnessInImpls(context, loc_id, query_self_const_id, interface);
444+
result_witness_id = GetOrAddLookupImplWitness(
445+
context, loc_id, query_self_const_id, interface);
440446
}
441447
if (result_witness_id.has_value()) {
442448
result_witness_ids.push_back(result_witness_id);
@@ -491,11 +497,16 @@ struct CandidateImpl {
491497

492498
// Returns the list of candidates impls for lookup to select from.
493499
static auto CollectCandidateImplsForQuery(
494-
Context& context, const TypeStructure& query_type_structure,
500+
Context& context, bool final_only,
501+
const TypeStructure& query_type_structure,
495502
SemIR::SpecificInterface& query_specific_interface)
496503
-> llvm::SmallVector<CandidateImpl> {
497504
llvm::SmallVector<CandidateImpl> candidate_impls;
498505
for (auto [id, impl] : context.impls().enumerate()) {
506+
if (final_only && !IsImplEffectivelyFinal(context, impl)) {
507+
continue;
508+
}
509+
499510
// If the impl's interface_id differs from the query, then this impl can
500511
// not possibly provide the queried interface.
501512
if (impl.interface.interface_id != query_specific_interface.interface_id) {
@@ -593,7 +604,8 @@ auto EvalLookupSingleImplWitness(Context& context, SemIR::LocId loc_id,
593604
QueryIsConcrete(context, query_self_const_id, query_specific_interface);
594605

595606
auto candidate_impls = CollectCandidateImplsForQuery(
596-
context, query_type_structure, query_specific_interface);
607+
context, /*final_only=*/false, query_type_structure,
608+
query_specific_interface);
597609

598610
for (const auto& candidate : candidate_impls) {
599611
// In deferred lookup for a symbolic impl witness, while building a
@@ -619,4 +631,48 @@ auto EvalLookupSingleImplWitness(Context& context, SemIR::LocId loc_id,
619631
return EvalImplLookupResult::MakeNone();
620632
}
621633

634+
auto LookupFinalImplWitnessForSpecificInterface(
635+
Context& context, SemIR::LocId loc_id,
636+
SemIR::ConstantId query_self_const_id,
637+
SemIR::SpecificInterface query_specific_interface) -> SemIR::InstId {
638+
// This would mean we need to UnwrapFacetAccessType(query_self_const_id), but
639+
// it's already done by member access, which is the one use of this function.
640+
CARBON_DCHECK(!context.insts().Is<SemIR::FacetAccessType>(
641+
context.constant_values().GetInstId(query_self_const_id)));
642+
643+
auto query_type_structure = BuildTypeStructure(
644+
context, context.constant_values().GetInstId(query_self_const_id),
645+
query_specific_interface);
646+
bool query_is_concrete =
647+
QueryIsConcrete(context, query_self_const_id, query_specific_interface);
648+
649+
auto candidate_impls = CollectCandidateImplsForQuery(
650+
context, /*final_only=*/true, query_type_structure,
651+
query_specific_interface);
652+
653+
for (const auto& candidate : candidate_impls) {
654+
// In deferred lookup for a symbolic impl witness, while building a
655+
// specific, there may be no stack yet as this may be the first lookup. If
656+
// further lookups are started as a result in deduce, they will build the
657+
// stack.
658+
//
659+
// NOTE: Don't retain a reference into the stack, it may be invalidated if
660+
// we do further impl lookups when GetWitnessIdForImpl() does deduction.
661+
if (!context.impl_lookup_stack().empty()) {
662+
context.impl_lookup_stack().back().impl_loc = candidate.loc_inst_id;
663+
}
664+
665+
// NOTE: GetWitnessIdForImpl() does deduction, which can cause new impls
666+
// to be imported, invalidating any pointer into `context.impls()`.
667+
auto result = GetWitnessIdForImpl(
668+
context, loc_id, query_is_concrete, query_self_const_id,
669+
query_specific_interface, candidate.impl_id);
670+
if (result.has_value()) {
671+
CARBON_CHECK(result.has_concrete_value());
672+
return result.concrete_witness();
673+
}
674+
}
675+
return SemIR::InstId::None;
676+
}
677+
622678
} // namespace Carbon::Check

‎toolchain/check/impl_lookup.h‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,18 @@ auto EvalLookupSingleImplWitness(Context& context, SemIR::LocId loc_id,
9797
SemIR::LookupImplWitness eval_query)
9898
-> EvalImplLookupResult;
9999

100+
// Looks for a witness of a _final_ impl declaration. Since only final impls are
101+
// returned, it always returns a concrete ImplWitness or None, it will never
102+
// return a symbolic LookupImplWitness instruction.
103+
//
104+
// Generally prefer to call LookupImplWitness(). This method is used to look for
105+
// a final specialization in order to get concrete associated constants in
106+
// generic contexts.
107+
auto LookupFinalImplWitnessForSpecificInterface(
108+
Context& context, SemIR::LocId loc_id,
109+
SemIR::ConstantId query_self_const_id,
110+
SemIR::SpecificInterface query_specific_interface) -> SemIR::InstId;
111+
100112
} // namespace Carbon::Check
101113

102114
#endif // CARBON_TOOLCHAIN_CHECK_IMPL_LOOKUP_H_

‎toolchain/check/member_access.cpp‎

Lines changed: 74 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -176,6 +176,27 @@ static auto AccessMemberOfImplWitness(Context& context, SemIR::LocId loc_id,
176176
.index = assoc_entity->index});
177177
}
178178

179+
// For an impl lookup query with a single interface in it, we can convert the
180+
// result to a single witness InstId.
181+
//
182+
// This CHECKs that the result (and thus the query) was a single interface. This
183+
// generally only makes sense in member access, where the lookup query's
184+
// interface is found through name lookup, and we don't have an arbitrary
185+
// `FacetType`.
186+
static auto GetWitnessFromSingleImplLookupResult(
187+
Context& context, SemIR::InstBlockIdOrError lookup_result)
188+
-> SemIR::InstId {
189+
auto witness_id = SemIR::InstId::None;
190+
if (lookup_result.has_error_value()) {
191+
witness_id = SemIR::ErrorInst::SingletonInstId;
192+
} else {
193+
auto witnesses = context.inst_blocks().Get(lookup_result.inst_block_id());
194+
CARBON_CHECK(witnesses.size() == 1);
195+
witness_id = witnesses[0];
196+
}
197+
return witness_id;
198+
}
199+
179200
// Performs impl lookup for a member name expression. This finds the relevant
180201
// impl witness and extracts the corresponding impl member.
181202
static auto PerformImplLookup(
@@ -210,18 +231,8 @@ static auto PerformImplLookup(
210231
return SemIR::ErrorInst::SingletonInstId;
211232
}
212233

213-
// The query facet type given to `LookupImplWitness()` had only a single
214-
// interface in it, so the returned witness set will have the same. Convert
215-
// from the InstBlockId to the single ImplWitness instruction.
216-
auto witness_id = SemIR::InstId::None;
217-
if (lookup_result.has_error_value()) {
218-
witness_id = SemIR::ErrorInst::SingletonInstId;
219-
} else {
220-
auto witnesses = context.inst_blocks().Get(lookup_result.inst_block_id());
221-
CARBON_CHECK(witnesses.size() == 1);
222-
witness_id = witnesses[0];
223-
}
224-
234+
auto witness_id =
235+
GetWitnessFromSingleImplLookupResult(context, lookup_result);
225236
return AccessMemberOfImplWitness(context, loc_id, self_type_id, witness_id,
226237
assoc_type.interface_specific_id, member_id);
227238
}
@@ -303,26 +314,59 @@ static auto LookupMemberNameInScope(Context& context, SemIR::LocId loc_id,
303314

304315
auto assoc_interface = assoc_type->GetSpecificInterface();
305316

306-
// First look for `assoc_interface` in the type of the base. If it is
307-
// found, get the witness that the interface is implemented from
308-
// `base_id`.
309-
auto identified_id = RequireIdentifiedFacetType(context, *facet_type);
310-
const auto& identified =
311-
context.identified_facet_types().Get(identified_id);
312317
// Witness that `T` implements the `assoc_interface`.
313318
SemIR::InstId witness_inst_id = SemIR::InstId::None;
314-
for (auto [index, base_interface] :
315-
llvm::enumerate(identified.required_interfaces())) {
316-
// Get the witness that `T` implements `base_type_id`.
317-
if (base_interface == assoc_interface) {
318-
witness_inst_id = GetOrAddInst(
319-
context, loc_id,
320-
SemIR::FacetAccessWitness{
321-
.type_id = GetSingletonType(
322-
context, SemIR::WitnessType::SingletonInstId),
323-
.facet_value_inst_id = base_id,
324-
.index = SemIR::ElementIndex(index)});
325-
break;
319+
320+
bool is_lookup_in_period_self = false;
321+
if (auto name = context.insts().TryGetAs<SemIR::NameRef>(base_id)) {
322+
if (name->name_id == SemIR::NameId::PeriodSelf) {
323+
is_lookup_in_period_self = true;
324+
}
325+
}
326+
327+
// TODO: In `.Self` we want to find the witness through its FacetType,
328+
// which is the code below this block. Instead of special-casing that
329+
// here, we could have the impl lookup also include witnesses
330+
// (FacetAccessWitness) from the FacetType? And even non-final results.
331+
// Then we just call into lookup once here, for `.Self` or otherwise,
332+
// and can drop the construction of FacetAccessWitness from this
333+
// function, and resolve TODO below that for "associated entity not
334+
// found in facet type".
335+
if (!is_lookup_in_period_self) {
336+
// For an associated constant value, we need to do impl lookup to try
337+
// find a final impl declaration. If we find one, we can use the value
338+
// assigned to the constant there, instead of its symbolic value.
339+
auto assoc_entity = context.insts().GetAs<SemIR::AssociatedEntity>(
340+
context.constant_values().GetConstantInstId(
341+
result.scope_result.target_inst_id()));
342+
if (context.insts().Is<SemIR::AssociatedConstantDecl>(
343+
assoc_entity.decl_id)) {
344+
witness_inst_id = LookupFinalImplWitnessForSpecificInterface(
345+
context, loc_id, context.constant_values().Get(base_id),
346+
assoc_interface);
347+
}
348+
}
349+
350+
if (!witness_inst_id.has_value()) {
351+
// First look for `assoc_interface` in the type of the base. If it is
352+
// found, get the witness that the interface is implemented from
353+
// `base_id`.
354+
auto identified_id = RequireIdentifiedFacetType(context, *facet_type);
355+
const auto& identified =
356+
context.identified_facet_types().Get(identified_id);
357+
for (auto [index, base_interface] :
358+
llvm::enumerate(identified.required_interfaces())) {
359+
// Get the witness that `T` implements `base_type_id`.
360+
if (base_interface == assoc_interface) {
361+
witness_inst_id = GetOrAddInst(
362+
context, loc_id,
363+
SemIR::FacetAccessWitness{
364+
.type_id = GetSingletonType(
365+
context, SemIR::WitnessType::SingletonInstId),
366+
.facet_value_inst_id = base_id,
367+
.index = SemIR::ElementIndex(index)});
368+
break;
369+
}
326370
}
327371
}
328372
// TODO: If that fails, would need to do impl lookup to see if the facet

0 commit comments

Comments
 (0)