1 //===-- RangeTest.cpp ----------------------------------------*- C++ -*-===// 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 } 329