[ADT] IntervalMap: fix setStart and setStop

[mlemay-intel]

Summary

These functions currently require that the new closed interval has a length of
at least 2. They also currently permit empty half-open intervals. This patch
defines nonEmpty in each traits structure and uses it to correct the
implementations of setStart and setStop.

[vsk]

Could you add unit tests to unittest/ADT/IntervalMapTest? I want to make sure that:

• We're allowed to create 1-element intervals using setStart/setStop.
• If we create a 0-element interval using setStart/setStop, it just gets deleted.

[mlemay-intel]

In D26064#581794, @vsk wrote:

...

• If we create a 0-element interval using setStart/setStop, it just gets deleted.

The revised assertion will fail in that case. Is deleting the interval actually the desired behavior?

[vsk]

In D26064#582164, @mlemay-intel wrote:

In D26064#581794, @vsk wrote:

...

• If we create a 0-element interval using setStart/setStop, it just gets deleted.

The revised assertion will fail in that case. Is deleting the interval actually the desired behavior?

Looking at it more, it shouldn't be possible to do what I described (creating a 0-element interval using setStart/setStop). I'm walking the request for that test back :).

[mlemay-intel]

In D26064#582202, @vsk wrote:

In D26064#582164, @mlemay-intel wrote:

In D26064#581794, @vsk wrote:

...

• If we create a 0-element interval using setStart/setStop, it just gets deleted.

The revised assertion will fail in that case. Is deleting the interval actually the desired behavior?

Looking at it more, it shouldn't be possible to do what I described (creating a 0-element interval using setStart/setStop). I'm walking the request for that test back :).

Sounds good, thanks. :)

[mlemay-intel]

Added unit tests.

[vsk]

LGTM. Could you wait a day or two before committing? I haven't worked on IntervalMap before, so it'd be nice to others a chance to chime in.

unittests/ADT/IntervalMapTest.cpp

19

nit: You don't need the extra space, 'IntervalMapHalfOpenInfo<unsigned>>' would be fine.

[mlemay-intel]

In D26064#582725, @vsk wrote:

LGTM. Could you wait a day or two before committing? I haven't worked on IntervalMap before, so it'd be nice to others a chance to chime in.

Sure, I'll wait a couple of days. Thanks!

[mlemay-intel]

Eliminated unnecessary space in template instantiation.
Revised test for half-open intervals to cover using setStop to create an interval with a length of 1.

include/llvm/ADT/IntervalMap.h

struct IntervalMapInfo {
   }
 
   /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
   /// This is a+1 == b for closed intervals, a == b for half-open intervals.
   static inline bool adjacent(const T &a, const T &b) {
     return a+1 == b;
   }
 
+  /// nonEmpty - Return true if [a;b] is non-empty.
+  /// This is a <= b for a closed interval, a < b for [a;b) half-open intervals.
+  static inline bool nonEmpty(const T &a, const T &b) {
+    return a <= b;
+  }
+
 };
 
 template <typename T>
 struct IntervalMapHalfOpenInfo {
 
   /// startLess - Return true if x is not in [a;b).
   static inline bool startLess(const T &x, const T &a) {
     return x < a;
   }
 
   /// stopLess - Return true if x is not in [a;b).
   static inline bool stopLess(const T &b, const T &x) {
     return b <= x;
   }
 
   /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
   static inline bool adjacent(const T &a, const T &b) {
     return a == b;
   }
 
+  /// nonEmpty - Return true if [a;b) is non-empty.
+  static inline bool nonEmpty(const T &a, const T &b) {
+    return a < b;
+  }
+
 };
 
 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
 /// It should be considered private to the implementation.
 namespace IntervalMapImpl {
 
 // Forward declarations.
 template <typename, typename, unsigned, typename> class LeafNode;
iterator::setNodeStop(unsigned Level, KeyT Stop) {
   }
   // Update root separately since it has a different layout.
   P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::setStart(KeyT a) {
-  assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop");
+  assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");
   KeyT &CurStart = this->unsafeStart();
   if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
     CurStart = a;
     return;
   }
   // Coalesce with the interval to the left.
   --*this;
   a = this->start();
   erase();
   setStartUnchecked(a);
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::setStop(KeyT b) {
-  assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start");
+  assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");
   if (Traits::startLess(b, this->stop()) ||
       !canCoalesceRight(b, this->value())) {
     setStopUnchecked(b);
     return;
   }
   // Coalesce with interval to the right.
   KeyT a = this->start();
   erase();

unittests/ADT/IntervalMapTest.cpp

 #include "llvm/ADT/IntervalMap.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 typedef IntervalMap<unsigned, unsigned, 4> UUMap;
+typedef IntervalMap<unsigned, unsigned, 4,
+                    IntervalMapHalfOpenInfo<unsigned> > UUHalfOpenMap;
 
 // Empty map tests
 TEST(IntervalMapTest, EmptyMap) {
   UUMap::Allocator allocator;
   UUMap map(allocator);
   EXPECT_TRUE(map.empty());
 
   // Lookup on empty map.
TEST(IntervalMapTest, SingleEntryMap) {
 
   // Shrink the bounds.
   I.setStart(150);
   ASSERT_TRUE(I.valid());
   EXPECT_EQ(150u, I.start());
   EXPECT_EQ(200u, I.stop());
   EXPECT_EQ(2u, I.value());
 
+  // Shrink the interval to have a length of 1
+  I.setStop(150);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(150u, I.start());
+  EXPECT_EQ(150u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
   I.setStop(160);
   ASSERT_TRUE(I.valid());
   EXPECT_EQ(150u, I.start());
   EXPECT_EQ(160u, I.stop());
   EXPECT_EQ(2u, I.value());
 
+  // Shrink the interval to have a length of 1
+  I.setStart(160);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(160u, I.start());
+  EXPECT_EQ(160u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
   // Erase last elem.
   I.erase();
   EXPECT_TRUE(map.empty());
   EXPECT_EQ(0, std::distance(map.begin(), map.end()));
 }
 
+// Single entry half-open map tests
+TEST(IntervalMapTest, SingleEntryHalfOpenMap) {
+  UUHalfOpenMap::Allocator allocator;
+  UUHalfOpenMap map(allocator);
+  map.insert(100, 150, 1);
+  EXPECT_FALSE(map.empty());
+
+  UUHalfOpenMap::iterator I = map.begin();
+  ASSERT_TRUE(I.valid());
+
+  // Shrink the interval to have a length of 1
+  I.setStart(149);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(149u, I.start());
+  EXPECT_EQ(150u, I.stop());
+  EXPECT_EQ(1u, I.value());
+
+  I.setStop(160);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(149u, I.start());
+  EXPECT_EQ(160u, I.stop());
+  EXPECT_EQ(1u, I.value());
+
+  // Shrink the interval to have a length of 1
+  I.setStart(159);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(159u, I.start());
+  EXPECT_EQ(160u, I.stop());
+  EXPECT_EQ(1u, I.value());
+}
+
 // Flat coalescing tests.
 TEST(IntervalMapTest, RootCoalescing) {
   UUMap::Allocator allocator;
   UUMap map(allocator);
   map.insert(100, 150, 1);
 
   // Coalesce from the left.
   map.insert(90, 99, 1);