Reject out-of-bounds enum sentinels in DenseMap/DenseSet. by jyknight · Pull Request #150308 · llvm/llvm-project

jyknight · 2025-07-23T20:15:42Z

This makes the bug in PR #125556 which was fixed by dc87a14 into a compile-time error.

...and fix a newly-discovered instance of this issue, triggered by a llvm::MapVector<AccessSpecifier, ...> in clang-tools-extra/clangd/refactor/tweaks/OverridePureVirtuals.cpp.

This makes the bug in PR llvm#125556 which was fixed by dc87a14 into a compile-time error.

llvmbot · 2025-07-23T20:16:17Z

@llvm/pr-subscribers-clang

@llvm/pr-subscribers-llvm-adt

Author: James Y Knight (jyknight)

Changes

This makes the bug in PR #125556 which was fixed by dc87a14 into a compile-time error.

Full diff: https://github.com/llvm/llvm-project/pull/150308.diff

1 Files Affected:

(modified) llvm/include/llvm/ADT/DenseMapInfo.h (+45-33)

diff --git a/llvm/include/llvm/ADT/DenseMapInfo.h b/llvm/include/llvm/ADT/DenseMapInfo.h
index b850223c953da..c05cbf919a0bf 100644
--- a/llvm/include/llvm/ADT/DenseMapInfo.h
+++ b/llvm/include/llvm/ADT/DenseMapInfo.h
@@ -51,8 +51,8 @@ inline unsigned combineHashValue(unsigned a, unsigned b) {
 /// just be `void`.
 template<typename T, typename Enable = void>
 struct DenseMapInfo {
-  //static inline T getEmptyKey();
-  //static inline T getTombstoneKey();
+  //static constexpr T getEmptyKey();
+  //static constexpr T getTombstoneKey();
   //static unsigned getHashValue(const T &Val);
   //static bool isEqual(const T &LHS, const T &RHS);
 };
@@ -70,13 +70,13 @@ struct DenseMapInfo<T*> {
   //               "Log2MaxAlign bits of alignment");
   static constexpr uintptr_t Log2MaxAlign = 12;
 
-  static inline T* getEmptyKey() {
+  static constexpr T* getEmptyKey() {
     uintptr_t Val = static_cast<uintptr_t>(-1);
     Val <<= Log2MaxAlign;
     return reinterpret_cast<T*>(Val);
   }
 
-  static inline T* getTombstoneKey() {
+  static constexpr T* getTombstoneKey() {
     uintptr_t Val = static_cast<uintptr_t>(-2);
     Val <<= Log2MaxAlign;
     return reinterpret_cast<T*>(Val);
@@ -92,8 +92,8 @@ struct DenseMapInfo<T*> {
 
 // Provide DenseMapInfo for chars.
 template<> struct DenseMapInfo<char> {
-  static inline char getEmptyKey() { return ~0; }
-  static inline char getTombstoneKey() { return ~0 - 1; }
+  static constexpr char getEmptyKey() { return ~0; }
+  static constexpr char getTombstoneKey() { return ~0 - 1; }
   static unsigned getHashValue(const char& Val) { return Val * 37U; }
 
   static bool isEqual(const char &LHS, const char &RHS) {
@@ -103,8 +103,8 @@ template<> struct DenseMapInfo<char> {
 
 // Provide DenseMapInfo for unsigned chars.
 template <> struct DenseMapInfo<unsigned char> {
-  static inline unsigned char getEmptyKey() { return ~0; }
-  static inline unsigned char getTombstoneKey() { return ~0 - 1; }
+  static constexpr unsigned char getEmptyKey() { return ~0; }
+  static constexpr unsigned char getTombstoneKey() { return ~0 - 1; }
   static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
 
   static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
@@ -114,8 +114,8 @@ template <> struct DenseMapInfo<unsigned char> {
 
 // Provide DenseMapInfo for unsigned shorts.
 template <> struct DenseMapInfo<unsigned short> {
-  static inline unsigned short getEmptyKey() { return 0xFFFF; }
-  static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
+  static constexpr unsigned short getEmptyKey() { return 0xFFFF; }
+  static constexpr unsigned short getTombstoneKey() { return 0xFFFF - 1; }
   static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
 
   static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
@@ -125,8 +125,8 @@ template <> struct DenseMapInfo<unsigned short> {
 
 // Provide DenseMapInfo for unsigned ints.
 template<> struct DenseMapInfo<unsigned> {
-  static inline unsigned getEmptyKey() { return ~0U; }
-  static inline unsigned getTombstoneKey() { return ~0U - 1; }
+  static constexpr unsigned getEmptyKey() { return ~0U; }
+  static constexpr unsigned getTombstoneKey() { return ~0U - 1; }
   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
 
   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
@@ -136,8 +136,8 @@ template<> struct DenseMapInfo<unsigned> {
 
 // Provide DenseMapInfo for unsigned longs.
 template<> struct DenseMapInfo<unsigned long> {
-  static inline unsigned long getEmptyKey() { return ~0UL; }
-  static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
+  static constexpr unsigned long getEmptyKey() { return ~0UL; }
+  static constexpr unsigned long getTombstoneKey() { return ~0UL - 1L; }
 
   static unsigned getHashValue(const unsigned long& Val) {
     if constexpr (sizeof(Val) == 4)
@@ -153,8 +153,8 @@ template<> struct DenseMapInfo<unsigned long> {
 
 // Provide DenseMapInfo for unsigned long longs.
 template<> struct DenseMapInfo<unsigned long long> {
-  static inline unsigned long long getEmptyKey() { return ~0ULL; }
-  static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
+  static constexpr unsigned long long getEmptyKey() { return ~0ULL; }
+  static constexpr unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
 
   static unsigned getHashValue(const unsigned long long& Val) {
     return densemap::detail::mix(Val);
@@ -168,16 +168,16 @@ template<> struct DenseMapInfo<unsigned long long> {
 
 // Provide DenseMapInfo for shorts.
 template <> struct DenseMapInfo<short> {
-  static inline short getEmptyKey() { return 0x7FFF; }
-  static inline short getTombstoneKey() { return -0x7FFF - 1; }
+  static constexpr short getEmptyKey() { return 0x7FFF; }
+  static constexpr short getTombstoneKey() { return -0x7FFF - 1; }
   static unsigned getHashValue(const short &Val) { return Val * 37U; }
   static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
 };
 
 // Provide DenseMapInfo for ints.
 template<> struct DenseMapInfo<int> {
-  static inline int getEmptyKey() { return 0x7fffffff; }
-  static inline int getTombstoneKey() { return -0x7fffffff - 1; }
+  static constexpr int getEmptyKey() { return 0x7fffffff; }
+  static constexpr int getTombstoneKey() { return -0x7fffffff - 1; }
   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
 
   static bool isEqual(const int& LHS, const int& RHS) {
@@ -187,11 +187,11 @@ template<> struct DenseMapInfo<int> {
 
 // Provide DenseMapInfo for longs.
 template<> struct DenseMapInfo<long> {
-  static inline long getEmptyKey() {
+  static constexpr long getEmptyKey() {
     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
   }
 
-  static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
+  static constexpr long getTombstoneKey() { return getEmptyKey() - 1L; }
 
   static unsigned getHashValue(const long& Val) {
     return (unsigned)(Val * 37UL);
@@ -204,8 +204,8 @@ template<> struct DenseMapInfo<long> {
 
 // Provide DenseMapInfo for long longs.
 template<> struct DenseMapInfo<long long> {
-  static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
-  static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
+  static constexpr long long getEmptyKey() { return 0x7fffffffffffffffLL; }
+  static constexpr long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
 
   static unsigned getHashValue(const long long& Val) {
     return (unsigned)(Val * 37ULL);
@@ -224,12 +224,12 @@ struct DenseMapInfo<std::pair<T, U>> {
   using FirstInfo = DenseMapInfo<T>;
   using SecondInfo = DenseMapInfo<U>;
 
-  static inline Pair getEmptyKey() {
+  static constexpr Pair getEmptyKey() {
     return std::make_pair(FirstInfo::getEmptyKey(),
                           SecondInfo::getEmptyKey());
   }
 
-  static inline Pair getTombstoneKey() {
+  static constexpr Pair getTombstoneKey() {
     return std::make_pair(FirstInfo::getTombstoneKey(),
                           SecondInfo::getTombstoneKey());
   }
@@ -257,11 +257,11 @@ struct DenseMapInfo<std::pair<T, U>> {
 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
   using Tuple = std::tuple<Ts...>;
 
-  static inline Tuple getEmptyKey() {
+  static constexpr Tuple getEmptyKey() {
     return Tuple(DenseMapInfo<Ts>::getEmptyKey()...);
   }
 
-  static inline Tuple getTombstoneKey() {
+  static constexpr Tuple getTombstoneKey() {
     return Tuple(DenseMapInfo<Ts>::getTombstoneKey()...);
   }
 
@@ -309,10 +309,22 @@ struct DenseMapInfo<Enum, std::enable_if_t<std::is_enum_v<Enum>>> {
   using UnderlyingType = std::underlying_type_t<Enum>;
   using Info = DenseMapInfo<UnderlyingType>;
 
-  static Enum getEmptyKey() { return static_cast<Enum>(Info::getEmptyKey()); }
+  // If an enum does not have a "fixed" underlying type, it may be UB to cast
+  // some values of the underlying type to the enum. We use an "extra" constexpr
+  // local to ensure that such UB would trigger "static assertion expression is
+  // not an integral constant expression", rather than runtime UB.
+  //
+  // If you hit this error, you can fix by switching to `enum class`, or adding
+  // an explicit underlying type (e.g. `enum X : int`) to the enum's definition.
 
-  static Enum getTombstoneKey() {
-    return static_cast<Enum>(Info::getTombstoneKey());
+  static constexpr Enum getEmptyKey() {
+    constexpr Enum V = static_cast<Enum>(Info::getEmptyKey());
+    return V;
+  }
+
+  static constexpr Enum getTombstoneKey() {
+    constexpr Enum V = static_cast<Enum>(Info::getTombstoneKey());
+    return V;
   }
 
   static unsigned getHashValue(const Enum &Val) {
@@ -326,9 +338,9 @@ template <typename T> struct DenseMapInfo<std::optional<T>> {
   using Optional = std::optional<T>;
   using Info = DenseMapInfo<T>;
 
-  static inline Optional getEmptyKey() { return {Info::getEmptyKey()}; }
+  static constexpr Optional getEmptyKey() { return {Info::getEmptyKey()}; }
 
-  static inline Optional getTombstoneKey() { return {Info::getTombstoneKey()}; }
+  static constexpr Optional getTombstoneKey() { return {Info::getTombstoneKey()}; }
 
   static unsigned getHashValue(const Optional &OptionalVal) {
     return detail::combineHashValue(

github-actions · 2025-07-23T20:18:05Z

✅ With the latest revision this PR passed the C/C++ code formatter.

jhuber6

Thanks, this one caught me by surprise so it'll definitely help to have it get caught statically.

jyknight · 2025-07-23T21:18:22Z

Looks like this actually caught some UB in clangd (which I hadn't buildt locally). Nice job, presubmit checks!

kadircet · 2025-07-24T09:39:39Z

FYI @marcogmaia, can you reland #139348 after this PR lands?

marcogmaia · 2025-07-24T10:08:14Z

Yes, of course. As soon as I get some free time, I'll look into it.

This makes the bug in PR llvm#125556 which was fixed by dc87a14 into a compile-time error. ...and fix a newly-discovered instance of this issue, triggered by a `llvm::MapVector<AccessSpecifier, ...>` in clang-tools-extra/clangd/refactor/tweaks/OverridePureVirtuals.cpp.

-- This commit bumps IREE to iree-org/iree@402a9be46a. -- As part of the same it :- a. [removes "dangling" builders](iree-org/iree#21364) b. [adds explicit cast](iree-org/iree#21494) c. [adds explicit result type of enum](llvm/llvm-project#150308) Signed-off-by: Abhishek Varma <abhvarma@amd.com>

-- This commit bumps IREE to iree-org/iree@402a9be46a. -- As part of the same it :- a. [removes "dangling" builders](iree-org/iree#21364) b. [adds explicit cast](iree-org/iree#21494) c. [adds explicit result type of enum](llvm/llvm-project#150308) d. updates MLIR-AIR to 53e3f44 e. adds `CascadeFlowOp`, `GetCascadeOp` and `PutCascadeOp` to AIE dialect. Signed-off-by: Abhishek Varma <abhvarma@amd.com>

See llvm/llvm-project#150308.

Reject out-of-bounds enum sentinels in DenseMap/DenseSet.

f8c6135

This makes the bug in PR llvm#125556 which was fixed by dc87a14 into a compile-time error.

jyknight requested a review from jhuber6 July 23, 2025 20:15

llvmbot added the llvm:adt label Jul 23, 2025

jhuber6 approved these changes Jul 23, 2025

View reviewed changes

kuhar requested review from dwblaikie and nikic July 23, 2025 20:27

jyknight added 2 commits July 23, 2025 17:06

Run clang-format

ddd35ec

Fix UB error detected in clangd code.

c1a5ea2

llvmbot added clang Clang issues not falling into any other category clang:frontend Language frontend issues, e.g. anything involving "Sema" labels Jul 23, 2025

nikic approved these changes Jul 24, 2025

View reviewed changes

jyknight merged commit 38f8253 into llvm:main Jul 24, 2025
11 checks passed

jyknight deleted the DenseMap-enum branch July 24, 2025 13:54

Abhishek-Varma mentioned this pull request Jul 30, 2025

Bump IREE to iree-org/iree@402a9be46a nod-ai/iree-amd-aie#1342

Merged

AnthonyLatsis added a commit to swiftlang/swift that referenced this pull request Nov 25, 2025

IRGen: Add fixed underlying type to enum to avoid UB

3e54e64

See llvm/llvm-project#150308.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Reject out-of-bounds enum sentinels in DenseMap/DenseSet.#150308

Reject out-of-bounds enum sentinels in DenseMap/DenseSet.#150308
jyknight merged 3 commits intollvm:mainfrom
jyknight:DenseMap-enum

jyknight commented Jul 23, 2025 •

edited

Loading

Uh oh!

llvmbot commented Jul 23, 2025 •

edited

Loading

Uh oh!

github-actions bot commented Jul 23, 2025 •

edited

Loading

Uh oh!

jhuber6 left a comment

Uh oh!

jyknight commented Jul 23, 2025

Uh oh!

kadircet commented Jul 24, 2025

Uh oh!

marcogmaia commented Jul 24, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

Conversation

jyknight commented Jul 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

llvmbot commented Jul 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Jul 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jhuber6 left a comment

Choose a reason for hiding this comment

Uh oh!

jyknight commented Jul 23, 2025

Uh oh!

kadircet commented Jul 24, 2025

Uh oh!

marcogmaia commented Jul 24, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

jyknight commented Jul 23, 2025 •

edited

Loading

llvmbot commented Jul 23, 2025 •

edited

Loading

github-actions bot commented Jul 23, 2025 •

edited

Loading