https://github.com/alejandro-alvarez-sonarsource created https://github.com/llvm/llvm-project/pull/118288
...in `ASTContext::getAutoTypeInternal` Given ```cpp template < typename > concept C1 = true; template < typename , auto > concept C2 = true; template < C1 auto V, C2< V > auto> struct S; ``` Both `C1 auto V` and `C2<V> auto` end on the set `AutoType`, the former being a template parameter for the latter. Since the hashing is not deterministic (i.e., pointers are hashed), every now and then, both will end on the same bucket. Given that `FoldingSet` recomputes the `FoldingSetID` for each node in the target bucket on lookup, this triggers an infinite recursion: 1. Look for `X` in `AutoTypes` 2. Let's assume it would be in bucket N, so it iterates over nodes in that bucket. Let's assume the first is `C2<V> auto`. 3. Computes the `FoldingSetID` for this one, which requires the profile of its template parameters, so they are visited. 4. In some frames below, we end on the same `FoldingSet`, and, by chance, `C1 auto V` would be in bucket N too. 5. But the first node in the bucket is `C2<V> auto` for which we need to profile `C1 auto V` 6. ... stack overflow! No step individually does anything wrong, but in general, `FoldingSet` seems not to be re-entrant, and this fact is hidden behind many nested calls. With this change, we store the `AutoType`s inside a `DenseMap` instead. The `FoldingSetID` is computed once only and then kept as the map's key, avoiding the need to do recursive lookups. We also now make sure the key for the inserted `AutoType` is the same as the key used for lookup. Before, this was not the case, and it caused also non-deterministic parsing errors. Fixes https://github.com/llvm/llvm-project/issues/110231 From 998ea6184faa12f6137d5b20f0a5f9279b14623a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Alejandro=20=C3=81lvarez=20Ayll=C3=B3n?= <alejandro.alva...@sonarsource.com> Date: Mon, 2 Dec 2024 10:48:52 +0100 Subject: [PATCH] [clang] Fix non-deterministic infinite recursion... ...in `ASTContext::getAutoTypeInternal` Given ```cpp template < typename > concept C1 = true; template < typename , auto > concept C2 = true; template < C1 auto V, C2< V > auto> struct S; ``` Both `C1 auto V` and `C2<V> auto` end on the set `AutoType`, the former being a template parameter for the latter. Since the hashing is not deterministic (i.e., pointers are hashed), every now and then, both will end on the same bucket. Given that `FoldingSet` recomputes the `FoldingSetID` for each node in the target bucket on lookup, this triggers an infinite recursion: 1. Look for `X` in `AutoTypes` 2. Let's assume it would be in bucket N, so it iterates over nodes in that bucket. Let's assume the first is `C2<V> auto`. 3. Computes the `FoldingSetID` for this one, which requires the profile of its template parameters, so they are visited. 4. In some frames below, we end on the same `FoldingSet`, and, by chance, `C1 auto V` would be in bucket N too. 5. But the first node in the bucket is `C2<V> auto` for which we need to profile `C1 auto V` 6. ... stack overflow! No step individually does anything wrong, but in general, `FoldingSet` seems not to be re-entrant, and this fact is hidden behind many nested calls. With this change, we store the `AutoType`s inside a `DenseMap` instead. The `FoldingSetID` is computed once only and then kept as the map's key, avoiding the need to do recursive lookups. We also now make sure the key for the inserted `AutoType` is the same as the key used for lookup. Before, this was not the case, and it caused also non-deterministic parsing errors. Fixes https://github.com/llvm/llvm-project/issues/110231 --- clang/include/clang/AST/ASTContext.h | 6 +++- clang/include/clang/AST/Type.h | 2 +- clang/lib/AST/ASTContext.cpp | 43 +++++++++++++++++++++------- clang/test/Parser/gh110231.cpp | 12 ++++++++ 4 files changed, 51 insertions(+), 12 deletions(-) create mode 100644 clang/test/Parser/gh110231.cpp diff --git a/clang/include/clang/AST/ASTContext.h b/clang/include/clang/AST/ASTContext.h index 89fcb6789d880a..1e89a6805ce9c6 100644 --- a/clang/include/clang/AST/ASTContext.h +++ b/clang/include/clang/AST/ASTContext.h @@ -245,7 +245,11 @@ class ASTContext : public RefCountedBase<ASTContext> { mutable llvm::FoldingSet<ObjCObjectPointerType> ObjCObjectPointerTypes; mutable llvm::FoldingSet<DependentUnaryTransformType> DependentUnaryTransformTypes; - mutable llvm::ContextualFoldingSet<AutoType, ASTContext&> AutoTypes; + // An AutoType can have a dependency on another AutoType via its template + // arguments. Since both dependent and dependency are on the same set, + // we can end up in an infinite recursion when looking for a node if we used + // a `FoldingSet`, since both could end up in the same bucket. + mutable llvm::DenseMap<llvm::FoldingSetNodeID, AutoType *> AutoTypes; mutable llvm::FoldingSet<DeducedTemplateSpecializationType> DeducedTemplateSpecializationTypes; mutable llvm::FoldingSet<AtomicType> AtomicTypes; diff --git a/clang/include/clang/AST/Type.h b/clang/include/clang/AST/Type.h index 90a52b1dcbf624..7a10aedbcb6437 100644 --- a/clang/include/clang/AST/Type.h +++ b/clang/include/clang/AST/Type.h @@ -6551,7 +6551,7 @@ class DeducedType : public Type { /// Represents a C++11 auto or C++14 decltype(auto) type, possibly constrained /// by a type-constraint. -class AutoType : public DeducedType, public llvm::FoldingSetNode { +class AutoType : public DeducedType { friend class ASTContext; // ASTContext creates these ConceptDecl *TypeConstraintConcept; diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp index 80e8c5b9df58e7..f2cb9d3c57b5e9 100644 --- a/clang/lib/AST/ASTContext.cpp +++ b/clang/lib/AST/ASTContext.cpp @@ -112,6 +112,27 @@ enum FloatingRank { Ibm128Rank }; +template <> struct llvm::DenseMapInfo<llvm::FoldingSetNodeID> { + static FoldingSetNodeID getEmptyKey() { return FoldingSetNodeID{}; } + + static FoldingSetNodeID getTombstoneKey() { + FoldingSetNodeID id; + for (size_t i = 0; i < sizeof(id) / sizeof(unsigned); ++i) { + id.AddInteger(std::numeric_limits<unsigned>::max()); + } + return id; + } + + static unsigned getHashValue(const FoldingSetNodeID &Val) { + return Val.ComputeHash(); + } + + static bool isEqual(const FoldingSetNodeID &LHS, + const FoldingSetNodeID &RHS) { + return LHS == RHS; + } +}; + /// \returns The locations that are relevant when searching for Doc comments /// related to \p D. static SmallVector<SourceLocation, 2> @@ -899,7 +920,7 @@ ASTContext::ASTContext(LangOptions &LOpts, SourceManager &SM, FunctionProtoTypes(this_(), FunctionProtoTypesLog2InitSize), DependentTypeOfExprTypes(this_()), DependentDecltypeTypes(this_()), TemplateSpecializationTypes(this_()), - DependentTemplateSpecializationTypes(this_()), AutoTypes(this_()), + DependentTemplateSpecializationTypes(this_()), DependentBitIntTypes(this_()), SubstTemplateTemplateParmPacks(this_()), DeducedTemplates(this_()), ArrayParameterTypes(this_()), CanonTemplateTemplateParms(this_()), SourceMgr(SM), LangOpts(LOpts), @@ -6294,12 +6315,13 @@ QualType ASTContext::getAutoTypeInternal( return getAutoDeductType(); // Look in the folding set for an existing type. - void *InsertPos = nullptr; llvm::FoldingSetNodeID ID; - AutoType::Profile(ID, *this, DeducedType, Keyword, IsDependent, + bool IsDeducedDependent = + !DeducedType.isNull() && DeducedType->isDependentType(); + AutoType::Profile(ID, *this, DeducedType, Keyword, IsDependent || IsDeducedDependent, TypeConstraintConcept, TypeConstraintArgs); - if (AutoType *AT = AutoTypes.FindNodeOrInsertPos(ID, InsertPos)) - return QualType(AT, 0); + if (auto const AT_iter = AutoTypes.find(ID); AT_iter != AutoTypes.end()) + return QualType(AT_iter->getSecond(), 0); QualType Canon; if (!IsCanon) { @@ -6314,10 +6336,6 @@ QualType ASTContext::getAutoTypeInternal( Canon = getAutoTypeInternal(QualType(), Keyword, IsDependent, IsPack, CanonicalConcept, CanonicalConceptArgs, true); - // Find the insert position again. - [[maybe_unused]] auto *Nothing = - AutoTypes.FindNodeOrInsertPos(ID, InsertPos); - assert(!Nothing && "canonical type broken"); } } } @@ -6331,8 +6349,13 @@ QualType ASTContext::getAutoTypeInternal( : TypeDependence::None) | (IsPack ? TypeDependence::UnexpandedPack : TypeDependence::None), Canon, TypeConstraintConcept, TypeConstraintArgs); +#ifndef NDEBUG + llvm::FoldingSetNodeID InsertedID; + AT->Profile(InsertedID, *this); + assert(InsertedID == ID && "ID does not match"); +#endif Types.push_back(AT); - AutoTypes.InsertNode(AT, InsertPos); + AutoTypes.try_emplace(ID, AT); return QualType(AT, 0); } diff --git a/clang/test/Parser/gh110231.cpp b/clang/test/Parser/gh110231.cpp new file mode 100644 index 00000000000000..b1405517505ff7 --- /dev/null +++ b/clang/test/Parser/gh110231.cpp @@ -0,0 +1,12 @@ +// RUN: seq 100 | xargs -Ifoo %clang_cc1 -std=c++20 -fsyntax-only -verify %s +// expected-no-diagnostics +// This is a regression test for a non-deterministic stack-overflow. + +template < typename > +concept C1 = true; + +template < typename , auto > +concept C2 = true; + +template < C1 auto V, C2< V > auto> +struct S; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
