lldb/unittests/Utility/RangeTest.cpp

   1 //===-- RangeTest.cpp -----------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "lldb/Utility/RangeMap.h"
  10 #include <cstdint>
  11 #include <type_traits>
  12
  13 #include "gtest/gtest.h"
  14
  15 using namespace lldb;
  16 using namespace lldb_private;
  17
  18 TEST(RangeTest, SizeTypes) {
  19   Range<lldb::addr_t, uint32_t> r;
  20   static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeBase())>::value,
  21                 "RangeBase type is not equal to the given one.");
  22   static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeEnd())>::value,
  23                 "RangeEnd type is not equal to the given one.");
  24   static_assert(std::is_same<uint32_t, decltype(r.GetByteSize())>::value,
  25                 "Size type is not equal to the given one.");
  26 }
  27
  28 typedef Range<lldb::addr_t, uint32_t> RangeT;
  29
  30 TEST(RangeTest, DefaultConstructor) {
  31   RangeT r;
  32   EXPECT_FALSE(r.IsValid());
  33   EXPECT_EQ(0U, r.GetByteSize());
  34   EXPECT_EQ(0U, r.GetRangeBase());
  35   EXPECT_EQ(0U, r.GetRangeEnd());
  36 }
  37
  38 TEST(RangeTest, Constructor) {
  39   RangeT r(3, 5);
  40   EXPECT_TRUE(r.IsValid());
  41   EXPECT_EQ(5U, r.GetByteSize());
  42   EXPECT_EQ(3U, r.GetRangeBase());
  43   EXPECT_EQ(8U, r.GetRangeEnd());
  44 }
  45
  46 TEST(RangeTest, Copy) {
  47   RangeT orig(3, 5);
  48   RangeT r = orig;
  49   EXPECT_TRUE(r.IsValid());
  50   EXPECT_EQ(5U, r.GetByteSize());
  51   EXPECT_EQ(3U, r.GetRangeBase());
  52   EXPECT_EQ(8U, r.GetRangeEnd());
  53 }
  54
  55 TEST(RangeTest, Clear) {
  56   RangeT r(3, 5);
  57   r.Clear();
  58   EXPECT_TRUE(r == RangeT());
  59 }
  60
  61 TEST(RangeTest, ClearWithStarAddress) {
  62   RangeT r(3, 5);
  63   r.Clear(4);
  64   EXPECT_TRUE(r == RangeT(4, 0));
  65 }
  66
  67 TEST(RangeTest, SetRangeBase) {
  68   RangeT r(3, 5);
  69   r.SetRangeBase(6);
  70   EXPECT_EQ(6U, r.GetRangeBase());
  71   EXPECT_EQ(11U, r.GetRangeEnd());
  72   EXPECT_EQ(5U, r.GetByteSize());
  73 }
  74
  75 TEST(RangeTest, Slide) {
  76   RangeT r(3, 5);
  77   r.Slide(1);
  78   EXPECT_EQ(4U, r.GetRangeBase());
  79   EXPECT_EQ(9U, r.GetRangeEnd());
  80   EXPECT_EQ(5U, r.GetByteSize());
  81
  82   r.Slide(2);
  83   EXPECT_EQ(6U, r.GetRangeBase());
  84   EXPECT_EQ(11U, r.GetRangeEnd());
  85   EXPECT_EQ(5U, r.GetByteSize());
  86 }
  87
  88 TEST(RangeTest, SlideZero) {
  89   RangeT r(3, 5);
  90   r.Slide(0);
  91   EXPECT_EQ(3U, r.GetRangeBase());
  92   EXPECT_EQ(8U, r.GetRangeEnd());
  93   EXPECT_EQ(5U, r.GetByteSize());
  94 }
  95
  96 TEST(RangeTest, ContainsAddr) {
  97   RangeT r(3, 5);
  98   EXPECT_FALSE(r.Contains(0));
  99   EXPECT_FALSE(r.Contains(1));
 100   EXPECT_FALSE(r.Contains(2));
 101   EXPECT_TRUE(r.Contains(3));
 102   EXPECT_TRUE(r.Contains(4));
 103   EXPECT_TRUE(r.Contains(5));
 104   EXPECT_TRUE(r.Contains(6));
 105   EXPECT_TRUE(r.Contains(7));
 106   EXPECT_FALSE(r.Contains(8));
 107   EXPECT_FALSE(r.Contains(9));
 108   EXPECT_FALSE(r.Contains(10));
 109 }
 110
 111 TEST(RangeTest, ContainsAddrInvalid) {
 112   RangeT r;
 113   EXPECT_FALSE(r.Contains(0));
 114   EXPECT_FALSE(r.Contains(1));
 115   EXPECT_FALSE(r.Contains(2));
 116   EXPECT_FALSE(r.Contains(3));
 117   EXPECT_FALSE(r.Contains(4));
 118 }
 119
 120 TEST(RangeTest, ContainsEndInclusive) {
 121   RangeT r(3, 5);
 122   EXPECT_FALSE(r.ContainsEndInclusive(0));
 123   EXPECT_FALSE(r.ContainsEndInclusive(1));
 124   EXPECT_FALSE(r.ContainsEndInclusive(2));
 125   EXPECT_TRUE(r.ContainsEndInclusive(3));
 126   EXPECT_TRUE(r.ContainsEndInclusive(4));
 127   EXPECT_TRUE(r.ContainsEndInclusive(5));
 128   EXPECT_TRUE(r.ContainsEndInclusive(6));
 129   EXPECT_TRUE(r.ContainsEndInclusive(7));
 130   EXPECT_TRUE(r.ContainsEndInclusive(8));
 131   EXPECT_FALSE(r.ContainsEndInclusive(9));
 132   EXPECT_FALSE(r.ContainsEndInclusive(10));
 133 }
 134
 135 TEST(RangeTest, ContainsEndInclusiveInvalid) {
 136   RangeT r;
 137   // FIXME: This is probably not intended.
 138   EXPECT_TRUE(r.ContainsEndInclusive(0));
 139
 140   EXPECT_FALSE(r.ContainsEndInclusive(1));
 141   EXPECT_FALSE(r.ContainsEndInclusive(2));
 142 }
 143
 144 TEST(RangeTest, ContainsRange) {
 145   RangeT r(3, 5);
 146
 147   // Range always contains itself.
 148   EXPECT_TRUE(r.Contains(r));
 149   // Invalid range.
 150   EXPECT_FALSE(r.Contains(RangeT()));
 151   // Range starts and ends before.
 152   EXPECT_FALSE(r.Contains(RangeT(0, 3)));
 153   // Range starts before but contains beginning.
 154   EXPECT_FALSE(r.Contains(RangeT(0, 4)));
 155   // Range starts before but contains beginning and more.
 156   EXPECT_FALSE(r.Contains(RangeT(0, 5)));
 157   // Range starts before and contains the other.
 158   EXPECT_FALSE(r.Contains(RangeT(0, 9)));
 159   // Range is fully inside.
 160   EXPECT_TRUE(r.Contains(RangeT(4, 3)));
 161   // Range has same start, but not as large.
 162   EXPECT_TRUE(r.Contains(RangeT(3, 4)));
 163   // Range has same end, but starts earlier.
 164   EXPECT_TRUE(r.Contains(RangeT(4, 4)));
 165   // Range starts inside, but stops after the end of r.
 166   EXPECT_FALSE(r.Contains(RangeT(4, 5)));
 167   // Range starts directly after r.
 168   EXPECT_FALSE(r.Contains(RangeT(8, 2)));
 169   // Range starts directly after r.
 170   EXPECT_FALSE(r.Contains(RangeT(9, 2)));
 171
 172   // Invalid range with different start.
 173   // FIXME: The first two probably not intended.
 174   EXPECT_TRUE(r.Contains(RangeT(3, 0)));
 175   EXPECT_TRUE(r.Contains(RangeT(4, 0)));
 176   EXPECT_FALSE(r.Contains(RangeT(8, 0)));
 177 }
 178
 179 TEST(RangeTest, ContainsRangeStartingFromZero) {
 180   RangeT r(0, 3);
 181   EXPECT_TRUE(r.Contains(r));
 182
 183   // FIXME: This is probably not intended.
 184   EXPECT_TRUE(r.Contains(RangeT()));
 185 }
 186
 187 TEST(RangeTest, Union) {
 188   RangeT r(3, 5);
 189
 190   // Ranges that we can't merge because it's not adjoin/intersecting.
 191   EXPECT_FALSE(r.Union(RangeT(9, 1)));
 192   // Check that we didn't modify our range.
 193   EXPECT_EQ(r, RangeT(3, 5));
 194
 195   // Another range we can't merge, but before r.
 196   EXPECT_FALSE(r.Union(RangeT(1, 1)));
 197   EXPECT_EQ(r, RangeT(3, 5));
 198
 199   // Merge an adjoin range after.
 200   EXPECT_TRUE(r.Union(RangeT(8, 2)));
 201   EXPECT_EQ(r, RangeT(3, 7));
 202
 203   // Merge an adjoin range before.
 204   EXPECT_TRUE(r.Union(RangeT(1, 2)));
 205   EXPECT_EQ(r, RangeT(1, 9));
 206
 207   // Merge an intersecting range after.
 208   EXPECT_TRUE(r.Union(RangeT(8, 3)));
 209   EXPECT_EQ(r, RangeT(1, 10));
 210
 211   // Merge an intersecting range before.
 212   EXPECT_TRUE(r.Union(RangeT(0, 1)));
 213   EXPECT_EQ(r, RangeT(0, 11));
 214
 215   // Merge a few ranges inside that shouldn't do anything.
 216   EXPECT_TRUE(r.Union(RangeT(0, 3)));
 217   EXPECT_EQ(r, RangeT(0, 11));
 218   EXPECT_TRUE(r.Union(RangeT(5, 1)));
 219   EXPECT_EQ(r, RangeT(0, 11));
 220   EXPECT_TRUE(r.Union(RangeT(9, 2)));
 221   EXPECT_EQ(r, RangeT(0, 11));
 222 }
 223
 224 TEST(RangeTest, DoesAdjoinOrIntersect) {
 225   RangeT r(3, 4);
 226
 227   EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(1, 1)));
 228   EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(1, 2)));
 229   EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(2, 2)));
 230   EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(4, 2)));
 231   EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(6, 2)));
 232   EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(7, 2)));
 233   EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(8, 2)));
 234 }
 235
 236 TEST(RangeTest, DoesIntersect) {
 237   RangeT r(3, 4);
 238
 239   EXPECT_FALSE(r.DoesIntersect(RangeT(1, 1)));
 240   EXPECT_FALSE(r.DoesIntersect(RangeT(1, 2)));
 241   EXPECT_TRUE(r.DoesIntersect(RangeT(2, 2)));
 242   EXPECT_TRUE(r.DoesIntersect(RangeT(4, 2)));
 243   EXPECT_TRUE(r.DoesIntersect(RangeT(6, 2)));
 244   EXPECT_FALSE(r.DoesIntersect(RangeT(7, 2)));
 245   EXPECT_FALSE(r.DoesIntersect(RangeT(8, 2)));
 246 }
 247
 248 TEST(RangeTest, LessThan) {
 249   RangeT r(10, 20);
 250
 251   // Equal range.
 252   EXPECT_FALSE(r < RangeT(10, 20));
 253   EXPECT_FALSE(RangeT(10, 20) < r);
 254
 255   auto expect_ordered_less_than = [](RangeT r1, RangeT r2) {
 256     EXPECT_TRUE(r1 < r2);
 257     EXPECT_FALSE(r2 < r1);
 258   };
 259
 260   // Same start, but bigger size.
 261   expect_ordered_less_than(r, RangeT(10, 21));
 262
 263   // Start before and ends before.
 264   expect_ordered_less_than(RangeT(9, 20), r);
 265
 266   // Start before and equal size.
 267   expect_ordered_less_than(RangeT(9, 21), r);
 268
 269   // Start before and bigger size.
 270   expect_ordered_less_than(RangeT(9, 22), r);
 271
 272   // Start after and ends before.
 273   expect_ordered_less_than(r, RangeT(11, 18));
 274
 275   // Start after and equal size.
 276   expect_ordered_less_than(r, RangeT(11, 19));
 277
 278   // Start after and bigger size.
 279   expect_ordered_less_than(r, RangeT(11, 20));
 280 }
 281
 282 TEST(RangeTest, Equal) {
 283   RangeT r(10, 20);
 284
 285   // Equal range.
 286   EXPECT_TRUE(r == RangeT(10, 20));
 287
 288   // Same start, different size.
 289   EXPECT_FALSE(r == RangeT(10, 21));
 290
 291   // Different start, same size.
 292   EXPECT_FALSE(r == RangeT(9, 20));
 293
 294   // Different start, different size.
 295   EXPECT_FALSE(r == RangeT(9, 21));
 296   EXPECT_FALSE(r == RangeT(11, 19));
 297 }
 298
 299 TEST(RangeTest, NotEqual) {
 300   RangeT r(10, 20);
 301
 302   EXPECT_FALSE(r != RangeT(10, 20));
 303
 304   EXPECT_TRUE(r != RangeT(10, 21));
 305   EXPECT_TRUE(r != RangeT(9, 20));
 306   EXPECT_TRUE(r != RangeT(9, 21));
 307 }
 308
 309 // Comparison tests for invalid ranges (size == 0).
 310
 311 TEST(RangeTest, LessThanInvalid) {
 312   EXPECT_TRUE(RangeT() < RangeT(1, 0));
 313   EXPECT_TRUE(RangeT() < RangeT(2, 0));
 314   EXPECT_TRUE(RangeT(1, 0) < RangeT(2, 0));
 315 }
 316
 317 TEST(RangeTest, EqualInvalid) {
 318   RangeT r;
 319   EXPECT_TRUE(r == RangeT());
 320   // Another invalid range, but with a different start.
 321   EXPECT_FALSE(r == RangeT(3, 0));
 322 }
 323
 324 TEST(RangeTest, NotEqualInvalid) {
 325   RangeT r;
 326   EXPECT_FALSE(r != RangeT());
 327   EXPECT_FALSE(r == RangeT(3, 0));
 328 }