Page MenuHomePhabricator

[Sema] fix nondeterminism in ASTContext::getDeducedTemplateSpecializationType
ClosedPublic

Authored by sugak on Oct 25 2021, 12:36 PM.

Details

Summary

DeducedTemplateSpecializationTypes is a llvm::FoldingSet<DeducedTemplateSpecializationType> [1], where FoldingSetNodeID is based on the values: {TemplateName, QualType, IsDeducedAsDependent}, those values are also used as DeducedTemplateSpecializationType constructor arguments.

A FoldingSetNodeID created by the static DeducedTemplateSpecializationType::Profile may not be equal to`FoldingSetNodeID` created by a member DeducedTemplateSpecializationType::Profile of an instance created with the same {TemplateName, QualType, IsDeducedAsDependent}, which makes DeducedTemplateSpecializationTypes lookups nondeterministic.

Specifically, while IsDeducedAsDependent value is passes to the constructor, IsDependent() method on the created instance may return a different value, because IsDependent is not saved as is:

clang/include/clang/AST/Type.h
DeducedTemplateSpecializationType(TemplateName Template,  QualType DeducedAsType, bool IsDeducedAsDependent)
    : DeducedType(DeducedTemplateSpecialization, DeducedAsType,
                  toTypeDependence(Template.getDependence()) | // <~  also considers `TemplateName` parameter
                      (IsDeducedAsDependent ? TypeDependence::DependentInstantiation : TypeDependence::None)),

For example, if an instance A with key FoldingSetNodeID {A, B, false} is inserted. Then a key FoldingSetNodeID {A, B, true} is probed: if it happens to correspond to the same bucket in FoldingSet as the first key, and A.Profile() returns FoldingSetNodeID {A, B, true}, then it's a
hit. If the bucket for the second key is different from the first key, instance A is not considered at all, and it's a no hit, even if A.Profile() returns FoldingSetNodeID {A, B, true}. Since TemplateName, QualType parameter values involve memory pointers, the lookup result depend on allocator, and may differ from run to run.

When this is used as part of modules compilation, it may result in "module out of date" errors, if imported modules are built on different machines.

This makes ASTContext::getDeducedTemplateSpecializationType consider Template.isDependent() similar DeducedTemplateSpecializationType constructor.

Tested on a very big codebase, by running modules compilations from directories with varied path length (seem to affect allocator seed).

  1. https://llvm.org/docs/ProgrammersManual.html#llvm-adt-foldingset-h

Patch by Wei Wang and Igor Sugak!

Diff Detail

Event Timeline

sugak created this revision.Oct 25 2021, 12:36 PM
sugak requested review of this revision.Oct 25 2021, 12:36 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 25 2021, 12:36 PM
Herald added a subscriber: cfe-commits. · View Herald Transcript
sugak edited the summary of this revision. (Show Details)Oct 25 2021, 12:39 PM
sugak edited the summary of this revision. (Show Details)
sugak edited the summary of this revision. (Show Details)Oct 25 2021, 12:44 PM
sugak updated this revision to Diff 382109.Oct 25 2021, 1:29 PM

apply clang-format suggestion

wenlei added a subscriber: wenlei.Oct 25 2021, 2:01 PM
bruno added a subscriber: bruno.

Nice catch, thanks for working on this!

clang/lib/AST/ASTContext.cpp
5673

Should this be done in the implementation (like done for the ctor)?

static void Profile(llvm::FoldingSetNodeID &ID, TemplateName Template,
                      QualType Deduced, bool IsDependent) {
    Template.Profile(ID);
    ID.AddPointer(Deduced.getAsOpaquePtr());
    ID.AddBoolean(IsDependent || Template.isDependent());
  }
5681

Seems like this assertion is failing in some of the tests above!

sugak added inline comments.Oct 26 2021, 9:36 AM
clang/lib/AST/ASTContext.cpp
5673

Thanks for the suggestion! Indeed that look better.

sugak updated this revision to Diff 382375.Oct 26 2021, 9:46 AM

Updated following @bruno's suggestion, and fixed tests (thanks @weiwang)!

dblaikie added a project: Restricted Project.Oct 26 2021, 10:07 AM
sugak marked an inline comment as done.Oct 26 2021, 11:33 AM
sugak marked an inline comment as done.

This issue has been blocking our internal module re-enablement for some time now, and we really appreciate any feedback. We also wonder if only DeducedTemplateSpecializationType is affected or it could also happen to other types.

bruno accepted this revision.Thu, Nov 18, 6:31 PM

This is good to go, sorry for the delay.

This revision is now accepted and ready to land.Thu, Nov 18, 6:31 PM
sugak edited the summary of this revision. (Show Details)Fri, Nov 19, 9:57 AM