[Sema] fix nondeterminism in ASTContext::getDeducedTemplateSpecializationType

[sugak]

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!

[sugak]

apply clang-format suggestion

[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]

clang/lib/AST/ASTContext.cpp

5673

Thanks for the suggestion! Indeed that look better.

[sugak]

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

[weiwang]

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.

[sugak]

ping @rsmith

[bruno]

This is good to go, sorry for the delay.

clang/include/clang/AST/Type.h

public:
 
   void Profile(llvm::FoldingSetNodeID &ID) {
     Profile(ID, getTemplateName(), getDeducedType(), isDependentType());
   }
 
   static void Profile(llvm::FoldingSetNodeID &ID, TemplateName Template,
                       QualType Deduced, bool IsDependent) {
     Template.Profile(ID);
-    ID.AddPointer(Deduced.getAsOpaquePtr());
-    ID.AddBoolean(IsDependent);
+    QualType CanonicalType =
+        Deduced.isNull() ? Deduced : Deduced.getCanonicalType();
+    ID.AddPointer(CanonicalType.getAsOpaquePtr());
+    ID.AddBoolean(IsDependent || Template.isDependent());
   }
 
   static bool classof(const Type *T) {
     return T->getTypeClass() == DeducedTemplateSpecialization;
   }
 };
 
 /// Represents a type template specialization; the template

clang/lib/AST/ASTContext.cpp

 /// such type, or the canonical deduced-but-dependent such type.
 QualType ASTContext::getDeducedTemplateSpecializationType(
     TemplateName Template, QualType DeducedType, bool IsDependent) const {
   // Look in the folding set for an existing type.
   void *InsertPos = nullptr;
   llvm::FoldingSetNodeID ID;
   DeducedTemplateSpecializationType::Profile(ID, Template, DeducedType,
                                              IsDependent);
   if (DeducedTemplateSpecializationType *DTST =
           DeducedTemplateSpecializationTypes.FindNodeOrInsertPos(ID, InsertPos))
     return QualType(DTST, 0);
 
   auto *DTST = new (*this, TypeAlignment)
       DeducedTemplateSpecializationType(Template, DeducedType, IsDependent);
+  llvm::FoldingSetNodeID TempID;
+  DTST->Profile(TempID);
+  assert(ID == TempID && "ID does not match");
   Types.push_back(DTST);
   DeducedTemplateSpecializationTypes.InsertNode(DTST, InsertPos);
   return QualType(DTST, 0);
 }
 
 /// getAtomicType - Return the uniqued reference to the atomic type for
 /// the given value type.
 QualType ASTContext::getAtomicType(QualType T) const {