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 "gmock/gmock.h"
11#include "gtest/gtest.h"
12
13using namespace lldb_private;
14
15TEST(RangeVector, SignedBaseType) {
16 using RangeVector = RangeVector<int32_t, uint32_t>;
17 using Entry = RangeVector::Entry;
18
19 RangeVector V;
20 V.Append(base: 10, size: 5);
21 V.Append(base: -3, size: 6);
22 V.Append(base: -10, size: 3);
23 V.Sort();
24 EXPECT_THAT(V,
25 testing::ElementsAre(Entry(-10, 3), Entry(-3, 6), Entry(10, 5)));
26 Entry e = *V.begin();
27 EXPECT_EQ(e.GetRangeBase(), -10);
28 EXPECT_EQ(e.GetByteSize(), 3u);
29 EXPECT_EQ(e.GetRangeEnd(), -7);
30 EXPECT_TRUE(e.Contains(-10));
31 EXPECT_TRUE(e.Contains(-8));
32 EXPECT_FALSE(e.Contains(-7));
33 EXPECT_TRUE(e.Union(Entry(-8, 2)));
34 EXPECT_EQ(e, Entry(-10, 4));
35 EXPECT_EQ(e.Intersect(Entry(-7, 3)), Entry(-7, 1));
36}
37
38TEST(RangeVector, CombineConsecutiveRanges) {
39 using RangeVector = RangeVector<uint32_t, uint32_t>;
40 using Entry = RangeVector::Entry;
41
42 RangeVector V;
43 V.Append(base: 0, size: 1);
44 V.Append(base: 5, size: 1);
45 V.Append(base: 6, size: 1);
46 V.Append(base: 10, size: 9);
47 V.Append(base: 15, size: 1);
48 V.Append(base: 20, size: 9);
49 V.Append(base: 21, size: 9);
50 V.Sort();
51 V.CombineConsecutiveRanges();
52 EXPECT_THAT(V, testing::ElementsAre(Entry(0, 1), Entry(5, 2), Entry(10, 9),
53 Entry(20, 10)));
54
55 V.Clear();
56 V.Append(base: 0, size: 20);
57 V.Append(base: 5, size: 1);
58 V.Append(base: 10, size: 1);
59 V.Sort();
60 V.CombineConsecutiveRanges();
61 EXPECT_THAT(V, testing::ElementsAre(Entry(0, 20)));
62}
63
64TEST(RangeVector, GetOverlaps) {
65 using RangeVector = RangeVector<uint32_t, uint32_t>;
66
67 RangeVector V1;
68 RangeVector V2;
69 RangeVector Expected;
70 // same range
71 V1.Append(base: 0, size: 1);
72 V2.Append(base: 0, size: 1);
73 Expected.Append(base: 0, size: 1);
74
75 // no overlap
76 V1.Append(base: 2, size: 2);
77 V2.Append(base: 4, size: 1);
78
79 // same base overlap
80 V1.Append(base: 10, size: 5);
81 V2.Append(base: 10, size: 3);
82 Expected.Append(base: 10, size: 3);
83
84 // same end overlap
85 V1.Append(base: 27, size: 1);
86 V2.Append(base: 20, size: 8);
87 Expected.Append(base: 27, size: 1);
88
89 // smaller base overlap
90 V1.Append(base: 33, size: 4);
91 V2.Append(base: 30, size: 5);
92 Expected.Append(base: 33, size: 2);
93
94 // larger base overlap
95 V1.Append(base: 46, size: 3);
96 V2.Append(base: 40, size: 7);
97 Expected.Append(base: 46, size: 1);
98
99 // encompass 1 range
100 V1.Append(base: 50, size: 9);
101 V2.Append(base: 51, size: 7);
102 Expected.Append(base: 51, size: 7);
103
104 // encompass 2 ranges
105 V1.Append(base: 60, size: 9);
106 V2.Append(base: 60, size: 3);
107 V2.Append(base: 65, size: 3);
108 Expected.Append(base: 60, size: 3);
109 Expected.Append(base: 65, size: 3);
110
111 V1.Sort();
112 V2.Sort();
113 Expected.Sort();
114
115 EXPECT_EQ(RangeVector::GetOverlaps(V1, V2), Expected);
116 EXPECT_EQ(RangeVector::GetOverlaps(V2, V1), Expected);
117}
118
119using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
120using EntryT = RangeDataVectorT::Entry;
121
122static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
123 return testing::Pointee(inner_matcher: testing::Field(field: &EntryT::data, matcher: ID));
124}
125
126std::vector<uint32_t> FindEntryIndexes(uint32_t address, RangeDataVectorT map) {
127 std::vector<uint32_t> result;
128 map.FindEntryIndexesThatContain(addr: address, indexes&: result);
129 return result;
130}
131
132TEST(RangeDataVector, FindEntryThatContains) {
133 RangeDataVectorT Map;
134 uint32_t NextID = 0;
135 Map.Append(entry: EntryT(0, 10, NextID++));
136 Map.Append(entry: EntryT(10, 10, NextID++));
137 Map.Append(entry: EntryT(20, 10, NextID++));
138 Map.Sort();
139
140 EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));
141 EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));
142 EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));
143 EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));
144 EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));
145 EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));
146 EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);
147}
148
149TEST(RangeDataVector, FindEntryThatContains_Overlap) {
150 RangeDataVectorT Map;
151 uint32_t NextID = 0;
152 Map.Append(entry: EntryT(0, 40, NextID++));
153 Map.Append(entry: EntryT(10, 20, NextID++));
154 Map.Append(entry: EntryT(20, 10, NextID++));
155 Map.Sort();
156
157 // With overlapping intervals, the intention seems to be to return the first
158 // interval which contains the address.
159 EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
160
161 // However, this does not always succeed.
162 // TODO: This should probably return the range (0, 40) as well.
163 EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
164}
165
166TEST(RangeDataVector, CustomSort) {
167 // First the default ascending order sorting of the data field.
168 auto Map = RangeDataVectorT();
169 Map.Append(entry: EntryT(0, 10, 50));
170 Map.Append(entry: EntryT(0, 10, 52));
171 Map.Append(entry: EntryT(0, 10, 53));
172 Map.Append(entry: EntryT(0, 10, 51));
173 Map.Sort();
174
175 EXPECT_THAT(Map.GetSize(), 4);
176 EXPECT_THAT(Map.GetEntryRef(0).data, 50);
177 EXPECT_THAT(Map.GetEntryRef(1).data, 51);
178 EXPECT_THAT(Map.GetEntryRef(2).data, 52);
179 EXPECT_THAT(Map.GetEntryRef(3).data, 53);
180
181 // And then a custom descending order sorting of the data field.
182 class CtorParam {};
183 class CustomSort {
184 public:
185 CustomSort(CtorParam) {}
186 bool operator()(const uint32_t a_data, const uint32_t b_data) {
187 return a_data > b_data;
188 }
189 };
190 using RangeDataVectorCustomSortT =
191 RangeDataVector<uint32_t, uint32_t, uint32_t, 0, CustomSort>;
192 using EntryT = RangeDataVectorT::Entry;
193
194 auto MapC = RangeDataVectorCustomSortT(CtorParam());
195 MapC.Append(entry: EntryT(0, 10, 50));
196 MapC.Append(entry: EntryT(0, 10, 52));
197 MapC.Append(entry: EntryT(0, 10, 53));
198 MapC.Append(entry: EntryT(0, 10, 51));
199 MapC.Sort();
200
201 EXPECT_THAT(MapC.GetSize(), 4);
202 EXPECT_THAT(MapC.GetEntryRef(0).data, 53);
203 EXPECT_THAT(MapC.GetEntryRef(1).data, 52);
204 EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
205 EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
206}
207
208TEST(RangeDataVector, FindEntryIndexesThatContain) {
209 RangeDataVectorT Map;
210 Map.Append(entry: EntryT(0, 10, 10));
211 Map.Append(entry: EntryT(10, 10, 11));
212 Map.Append(entry: EntryT(20, 10, 12));
213 Map.Sort();
214
215 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
216 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
217 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
218 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
219 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
220 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
221 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
222}
223
224TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
225 RangeDataVectorT Map;
226 Map.Append(entry: EntryT(0, 40, 10));
227 Map.Append(entry: EntryT(10, 20, 11));
228 Map.Append(entry: EntryT(20, 10, 12));
229 Map.Sort();
230
231 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
232 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
233 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
234 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
235 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
236 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
237 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
238 EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
239 EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
240}
241
242TEST(RangeDataVector, CombineConsecutiveEntriesWithEqualData) {
243 RangeDataVectorT Map;
244 Map.Append(entry: EntryT(0, 10, 47));
245 Map.Append(entry: EntryT(10, 10, 47));
246 Map.Sort();
247 Map.CombineConsecutiveEntriesWithEqualData();
248 EXPECT_THAT(FindEntryIndexes(5, Map), testing::ElementsAre(47));
249 EXPECT_THAT(FindEntryIndexes(15, Map), testing::ElementsAre(47));
250 EXPECT_THAT(FindEntryIndexes(25, Map), testing::ElementsAre());
251
252 Map.Clear();
253 Map.Append(entry: EntryT(0, 10, 47));
254 Map.Append(entry: EntryT(20, 10, 47));
255 Map.Sort();
256 Map.CombineConsecutiveEntriesWithEqualData();
257 EXPECT_THAT(FindEntryIndexes(5, Map), testing::ElementsAre(47));
258 EXPECT_THAT(FindEntryIndexes(15, Map), testing::ElementsAre());
259 EXPECT_THAT(FindEntryIndexes(25, Map), testing::ElementsAre(47));
260 EXPECT_THAT(FindEntryIndexes(35, Map), testing::ElementsAre());
261}
262

source code of lldb/unittests/Utility/RangeMapTest.cpp