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