| 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 |
} |