From ad4b66fd9b3ef3f78e3f594b32b0ca952453ea68 Mon Sep 17 00:00:00 2001
From: Lang Hames <lhames@gmail.com>
Date: Wed, 18 Jan 2023 17:33:50 -0800
Subject: [PATCH] [ORC-RT] Specialize non-coalescing-IntervalMap to allow
 non-comparable values.

In non-coalescing IntervalMaps the value type should not be requried to be
equality-comparable.
---
 compiler-rt/lib/orc/interval_map.h                 | 73 +++++++++++++---------
 .../lib/orc/tests/unit/interval_map_test.cpp       | 16 +++++
 2 files changed, 60 insertions(+), 29 deletions(-)

diff --git a/compiler-rt/lib/orc/interval_map.h b/compiler-rt/lib/orc/interval_map.h
index 16f22c6..8c1609d 100644
--- a/compiler-rt/lib/orc/interval_map.h
+++ b/compiler-rt/lib/orc/interval_map.h
@@ -26,8 +26,7 @@ enum class IntervalCoalescing { Enabled, Disabled };
 /// NOTE: The interface is kept mostly compatible with LLVM's IntervalMap
 ///       collection to make it easy to swap over in the future if we choose
 ///       to.
-template <typename KeyT, typename ValT, IntervalCoalescing Coalescing>
-class IntervalMap {
+template <typename KeyT, typename ValT> class IntervalMapBase {
 private:
   using KeyPairT = std::pair<KeyT, KeyT>;
 
@@ -76,7 +75,7 @@ public:
   }
 
   const_iterator find(KeyT K) const {
-    return const_cast<IntervalMap<KeyT, ValT, Coalescing> *>(this)->find(K);
+    return const_cast<IntervalMapBase<KeyT, ValT> *>(this)->find(K);
   }
 
   ValT lookup(KeyT K, ValT NotFound = ValT()) const {
@@ -86,31 +85,6 @@ public:
     return I->second;
   }
 
-  void insert(KeyT KS, KeyT KE, ValT V) {
-    if (Coalescing == IntervalCoalescing::Enabled) {
-      auto J = Impl.upper_bound(KS);
-
-      // Coalesce-right if possible. Either way, J points at our insertion
-      // point.
-      if (J != end() && KE == J->first.first && J->second == V) {
-        KE = J->first.second;
-        auto Tmp = J++;
-        Impl.erase(Tmp);
-      }
-
-      // Coalesce-left if possible.
-      if (J != begin()) {
-        auto I = std::prev(J);
-        if (I->first.second == KS && I->second == V) {
-          KS = I->first.first;
-          Impl.erase(I);
-        }
-      }
-      Impl.insert(J, std::make_pair(std::make_pair(KS, KE), std::move(V)));
-    } else
-      Impl.insert(std::make_pair(std::make_pair(KS, KE), std::move(V)));
-  }
-
   // Erase [KS, KE), which must be entirely containing within one existing
   // range in the map. Removal is allowed to split the range.
   void erase(KeyT KS, KeyT KE) {
@@ -144,10 +118,51 @@ public:
           J, std::make_pair(std::make_pair(Tmp.first.first, KS), Tmp.second));
   }
 
-private:
+protected:
   ImplMap Impl;
 };
 
+template <typename KeyT, typename ValT, IntervalCoalescing Coalescing>
+class IntervalMap;
+
+template <typename KeyT, typename ValT>
+class IntervalMap<KeyT, ValT, IntervalCoalescing::Enabled>
+    : public IntervalMapBase<KeyT, ValT> {
+public:
+  // Coalescing insert. Requires that ValTs be equality-comparable.
+  void insert(KeyT KS, KeyT KE, ValT V) {
+    auto J = this->Impl.upper_bound(KS);
+
+    // Coalesce-right if possible. Either way, J points at our insertion
+    // point.
+    if (J != this->end() && KE == J->first.first && J->second == V) {
+      KE = J->first.second;
+      auto Tmp = J++;
+      this->Impl.erase(Tmp);
+    }
+
+    // Coalesce-left if possible.
+    if (J != this->begin()) {
+      auto I = std::prev(J);
+      if (I->first.second == KS && I->second == V) {
+        KS = I->first.first;
+        this->Impl.erase(I);
+      }
+    }
+    this->Impl.insert(J, std::make_pair(std::make_pair(KS, KE), std::move(V)));
+  }
+};
+
+template <typename KeyT, typename ValT>
+class IntervalMap<KeyT, ValT, IntervalCoalescing::Disabled>
+    : public IntervalMapBase<KeyT, ValT> {
+public:
+  // Non-coalescing insert. Does not require ValT to be equality-comparable.
+  void insert(KeyT KS, KeyT KE, ValT V) {
+    this->Impl.insert(std::make_pair(std::make_pair(KS, KE), std::move(V)));
+  }
+};
+
 } // End namespace __orc_rt
 
 #endif // ORC_RT_INTERVAL_MAP_H
diff --git a/compiler-rt/lib/orc/tests/unit/interval_map_test.cpp b/compiler-rt/lib/orc/tests/unit/interval_map_test.cpp
index 6f6474b..a1c6958 100644
--- a/compiler-rt/lib/orc/tests/unit/interval_map_test.cpp
+++ b/compiler-rt/lib/orc/tests/unit/interval_map_test.cpp
@@ -186,3 +186,19 @@ TEST(IntervalMapTest, EraseSplittingBoth) {
   EXPECT_EQ(std::next(M.begin())->first.first, 9U);
   EXPECT_EQ(std::next(M.begin())->first.second, 10U);
 }
+
+TEST(IntervalMapTest, NonCoalescingMapPermitsNonComparableKeys) {
+  // Test that values that can't be equality-compared are still usable when
+  // coalescing is disabled and behave as expected.
+
+  struct S {}; // Struct with no equality comparison.
+
+  IntervalMap<unsigned, S, IntervalCoalescing::Disabled> M;
+
+  M.insert(7, 8, S());
+
+  EXPECT_FALSE(M.empty());
+  EXPECT_EQ(std::next(M.begin()), M.end());
+  EXPECT_EQ(M.find(7), M.begin());
+  EXPECT_EQ(M.find(8), M.end());
+}
-- 
2.7.4