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
TEST(RangeTest,SizeTypes)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
TEST(RangeTest,DefaultConstructor)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
TEST(RangeTest,Constructor)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
TEST(RangeTest,Copy)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
TEST(RangeTest,Clear)55 TEST(RangeTest, Clear) {
56 RangeT r(3, 5);
57 r.Clear();
58 EXPECT_TRUE(r == RangeT());
59 }
60
TEST(RangeTest,ClearWithStarAddress)61 TEST(RangeTest, ClearWithStarAddress) {
62 RangeT r(3, 5);
63 r.Clear(4);
64 EXPECT_TRUE(r == RangeT(4, 0));
65 }
66
TEST(RangeTest,SetRangeBase)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
TEST(RangeTest,Slide)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
TEST(RangeTest,SlideZero)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
TEST(RangeTest,ContainsAddr)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
TEST(RangeTest,ContainsAddrInvalid)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
TEST(RangeTest,ContainsEndInclusive)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
TEST(RangeTest,ContainsEndInclusiveInvalid)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
TEST(RangeTest,ContainsRange)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
TEST(RangeTest,ContainsRangeStartingFromZero)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
TEST(RangeTest,Union)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
TEST(RangeTest,DoesAdjoinOrIntersect)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
TEST(RangeTest,DoesIntersect)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
TEST(RangeTest,LessThan)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
TEST(RangeTest,Equal)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
TEST(RangeTest,NotEqual)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
TEST(RangeTest,LessThanInvalid)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
TEST(RangeTest,EqualInvalid)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
TEST(RangeTest,NotEqualInvalid)324 TEST(RangeTest, NotEqualInvalid) {
325 RangeT r;
326 EXPECT_FALSE(r != RangeT());
327 EXPECT_FALSE(r == RangeT(3, 0));
328 }
329