1 | //===-------------- ItaniumManglingCanonicalizerTest.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 "llvm/ProfileData/ItaniumManglingCanonicalizer.h" |
10 | #include "llvm/ADT/ArrayRef.h" |
11 | #include "llvm/ADT/StringRef.h" |
12 | #include "gtest/gtest.h" |
13 | |
14 | #include <cstdlib> |
15 | #include <map> |
16 | #include <vector> |
17 | |
18 | using namespace llvm; |
19 | |
20 | namespace { |
21 | |
22 | using EquivalenceError = llvm::ItaniumManglingCanonicalizer::EquivalenceError; |
23 | using FragmentKind = llvm::ItaniumManglingCanonicalizer::FragmentKind; |
24 | |
25 | struct Equivalence { |
26 | FragmentKind Kind; |
27 | llvm::StringRef First; |
28 | llvm::StringRef Second; |
29 | }; |
30 | |
31 | // A set of manglings that should all be considered equivalent. |
32 | using EquivalenceClass = std::vector<llvm::StringRef>; |
33 | |
34 | struct Testcase { |
35 | // A set of equivalences to register. |
36 | std::vector<Equivalence> Equivalences; |
37 | // A set of distinct equivalence classes created by registering the |
38 | // equivalences. |
39 | std::vector<EquivalenceClass> Classes; |
40 | }; |
41 | |
42 | // A function that returns a set of test cases. |
43 | static std::vector<Testcase> getTestcases() { |
44 | return { |
45 | // Three different manglings for std::string (old libstdc++, new libstdc++, |
46 | // libc++). |
47 | { |
48 | .Equivalences: { |
49 | {.Kind: FragmentKind::Type, .First: "Ss" , |
50 | .Second: "NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE" }, |
51 | {.Kind: FragmentKind::Type, .First: "Ss" , |
52 | .Second: "NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE" }, |
53 | }, |
54 | .Classes: { |
55 | {"_Z1fv" }, |
56 | {"_Z1fSs" , |
57 | "_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE" , |
58 | "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE" }, |
59 | {"_ZNKSs4sizeEv" , |
60 | "_ZNKSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEE4sizeEv" , |
61 | "_ZNKSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE4sizeEv" }, |
62 | } |
63 | }, |
64 | |
65 | // Check that substitutions are properly handled. |
66 | { |
67 | .Equivalences: { |
68 | // ::X <-> ::N::X<int> |
69 | {.Kind: FragmentKind::Type, .First: "1X" , .Second: "N1N1XIiEE" }, |
70 | // ::T<T<int, int>, T<int, int>> <-> T<int> |
71 | {.Kind: FragmentKind::Type, .First: "1TIS_IiiES0_E" , .Second: "1TIiE" }, |
72 | // A::B::foo <-> AB::foo |
73 | {.Kind: FragmentKind::Name, .First: "N1A1B3fooE" , .Second: "N2AB3fooE" }, |
74 | }, |
75 | .Classes: { |
76 | {"_Z1f1XPS_RS_" , "_Z1fN1N1XIiEEPS1_RS1_" }, |
77 | {"_ZN1A1B3fooE1TIS1_IiiES2_EPS3_RS3_" , "_ZN2AB3fooE1TIiEPS1_RS1_" }, |
78 | } |
79 | }, |
80 | |
81 | // Check that nested equivalences are properly handled. |
82 | { |
83 | .Equivalences: { |
84 | // std::__1::char_traits == std::__cxx11::char_traits |
85 | // (Note that this is unused and should make no difference, |
86 | // but it should not cause us to fail to match up the cases |
87 | // below.) |
88 | {.Kind: FragmentKind::Name, |
89 | .First: "NSt3__111char_traitsE" , |
90 | .Second: "NSt7__cxx1111char_traitsE" }, |
91 | // std::__1::allocator == std::allocator |
92 | {.Kind: FragmentKind::Name, |
93 | .First: "NSt3__19allocatorE" , |
94 | .Second: "Sa" }, // "Sa" is not strictly a <name> but we accept it as one. |
95 | // std::__1::vector == std::vector |
96 | {.Kind: FragmentKind::Name, |
97 | .First: "St6vector" , |
98 | .Second: "NSt3__16vectorE" }, |
99 | // std::__1::basic_string< |
100 | // char |
101 | // std::__1::char_traits<char>, |
102 | // std::__1::allocator<char>> == |
103 | // std::__cxx11::basic_string< |
104 | // char, |
105 | // std::char_traits<char>, |
106 | // std::allocator<char>> |
107 | {.Kind: FragmentKind::Type, |
108 | .First: "NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE" , |
109 | .Second: "NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE" }, |
110 | // X<A> <-> X<B> |
111 | {.Kind: FragmentKind::Type, .First: "1XI1AE" , .Second: "1XI1BE" }, |
112 | // X <-> Y |
113 | {.Kind: FragmentKind::Name, .First: "1X" , .Second: "1Y" }, |
114 | }, |
115 | .Classes: { |
116 | // f(std::string) |
117 | {"_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE" , |
118 | "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE" }, |
119 | // f(std::vector<int>) |
120 | {"_Z1fSt6vectorIiSaIiEE" , "_Z1fNSt3__16vectorIiNS_9allocatorIiEEEE" }, |
121 | // f(X<A>), f(X<B>), f(Y<A>), f(Y<B>) |
122 | {"_Z1f1XI1AE" , "_Z1f1XI1BE" , "_Z1f1YI1AE" , "_Z1f1YI1BE" }, |
123 | // f(X<C>), f(Y<C>) |
124 | {"_Z1f1XI1CE" , "_Z1f1YI1CE" }, |
125 | } |
126 | }, |
127 | |
128 | // Check namespace equivalences. |
129 | { |
130 | .Equivalences: { |
131 | // std::__1 == std::__cxx11 |
132 | {.Kind: FragmentKind::Name, .First: "St3__1" , .Second: "St7__cxx11" }, |
133 | // std::__1::allocator == std::allocator |
134 | {.Kind: FragmentKind::Name, .First: "NSt3__19allocatorE" , .Second: "Sa" }, |
135 | // std::vector == std::__1::vector |
136 | {.Kind: FragmentKind::Name, .First: "St6vector" , .Second: "NSt3__16vectorE" }, |
137 | // std::__cxx11::char_traits == std::char_traits |
138 | // (This indirectly means that std::__1::char_traits == std::char_traits, |
139 | // due to the std::__cxx11 == std::__1 equivalence, which is what we rely |
140 | // on below.) |
141 | {.Kind: FragmentKind::Name, .First: "NSt7__cxx1111char_traitsE" , .Second: "St11char_traits" }, |
142 | }, |
143 | .Classes: { |
144 | // f(std::foo) |
145 | {"_Z1fNSt7__cxx113fooE" , |
146 | "_Z1fNSt3__13fooE" }, |
147 | // f(std::string) |
148 | {"_Z1fNSt7__cxx1111char_traitsIcEE" , |
149 | "_Z1fNSt3__111char_traitsIcEE" , |
150 | "_Z1fSt11char_traitsIcE" }, |
151 | // f(std::string) |
152 | {"_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE" , |
153 | "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE" }, |
154 | // f(std::vector<int>) |
155 | {"_Z1fSt6vectorIiSaIiEE" , "_Z1fNSt3__16vectorIiNS_9allocatorIiEEEE" }, |
156 | } |
157 | }, |
158 | |
159 | // Check namespace equivalences for namespace 'std'. We support using 'St' |
160 | // for this, despite it not technically being a <name>. |
161 | { |
162 | .Equivalences: { |
163 | // std::__1 == std |
164 | {.Kind: FragmentKind::Name, .First: "St3__1" , .Second: "St" }, |
165 | // std::__1 == std::__cxx11 |
166 | {.Kind: FragmentKind::Name, .First: "St3__1" , .Second: "St7__cxx11" }, |
167 | // FIXME: Should a 'std' equivalence also cover the predefined |
168 | // substitutions? |
169 | // std::__1::allocator == std::allocator |
170 | {.Kind: FragmentKind::Name, .First: "NSt3__19allocatorE" , .Second: "Sa" }, |
171 | }, |
172 | .Classes: { |
173 | {"_Z1fSt3foo" , "_Z1fNSt3__13fooE" , "_Z1fNSt7__cxx113fooE" }, |
174 | {"_Z1fNSt3bar3bazE" , "_Z1fNSt3__13bar3bazE" }, |
175 | // f(std::string) |
176 | {"_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE" , |
177 | "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE" }, |
178 | // f(std::vector<int>) |
179 | {"_Z1fSt6vectorIiSaIiEE" , "_Z1fNSt3__16vectorIiNS_9allocatorIiEEEE" }, |
180 | } |
181 | }, |
182 | |
183 | // Check mutually-recursive equivalences. |
184 | { |
185 | .Equivalences: { |
186 | {.Kind: FragmentKind::Type, .First: "1A" , .Second: "1B" }, |
187 | {.Kind: FragmentKind::Type, .First: "1A" , .Second: "1C" }, |
188 | {.Kind: FragmentKind::Type, .First: "1D" , .Second: "1B" }, |
189 | {.Kind: FragmentKind::Type, .First: "1C" , .Second: "1E" }, |
190 | }, |
191 | .Classes: { |
192 | {"_Z1f1A" , "_Z1f1B" , "_Z1f1C" , "_Z1f1D" , "_Z1f1E" }, |
193 | {"_Z1f1F" }, |
194 | } |
195 | }, |
196 | |
197 | // Check <encoding>s. |
198 | { |
199 | .Equivalences: { |
200 | {.Kind: FragmentKind::Encoding, .First: "1fv" , .Second: "1gv" }, |
201 | }, |
202 | .Classes: { |
203 | // f(void) -> g(void) |
204 | {"_Z1fv" , "_Z1gv" }, |
205 | // static local 'n' in f(void) -> static local 'n' in g(void) |
206 | {"_ZZ1fvE1n" , "_ZZ1gvE1n" }, |
207 | } |
208 | }, |
209 | |
210 | // Corner case: the substitution can appear within its own expansion. |
211 | { |
212 | .Equivalences: { |
213 | // X <-> Y<X> |
214 | {.Kind: FragmentKind::Type, .First: "1X" , .Second: "1YI1XE" }, |
215 | // A<B> <-> B |
216 | {.Kind: FragmentKind::Type, .First: "1AI1BE" , .Second: "1B" }, |
217 | }, |
218 | .Classes: { |
219 | // f(X) == f(Y<X>) == f(Y<Y<X>>) == f(Y<Y<Y<X>>>) |
220 | {"_Z1f1X" , "_Z1f1YI1XE" , "_Z1f1YIS_I1XEE" , "_Z1f1YIS_IS_I1XEEE" }, |
221 | // f(B) == f(A<B>) == f(A<A<B>>) == f(A<A<A<B>>>) |
222 | {"_Z1f1B" , "_Z1f1AI1BE" , "_Z1f1AIS_I1BEE" , "_Z1f1AIS_IS_I1BEEE" }, |
223 | } |
224 | }, |
225 | |
226 | // Redundant equivalences are accepted (and have no effect). |
227 | { |
228 | .Equivalences: { |
229 | {.Kind: FragmentKind::Name, .First: "3std" , .Second: "St" }, |
230 | {.Kind: FragmentKind::Name, .First: "1X" , .Second: "1Y" }, |
231 | {.Kind: FragmentKind::Name, .First: "N1X1ZE" , .Second: "N1Y1ZE" }, |
232 | }, |
233 | .Classes: {} |
234 | }, |
235 | |
236 | // Check that ctor and dtor variants are considered distinct. |
237 | { |
238 | .Equivalences: {}, |
239 | .Classes: {{"_ZN1XC1Ev" }, {"_ZN1XC2Ev" }, {"_ZN1XD1Ev" }, {"_ZN1XD2Ev" }} |
240 | }, |
241 | |
242 | // Ensure array types with and without bounds are handled properly. |
243 | { |
244 | .Equivalences: { |
245 | {.Kind: FragmentKind::Type, .First: "A_i" , .Second: "A1_f" }, |
246 | }, |
247 | .Classes: { |
248 | {"_Z1fRA_i" , "_Z1fRA_i" , "_Z1fRA1_f" }, |
249 | {"_Z1fRA1_i" }, {"_Z1fRA_f" }, |
250 | } |
251 | }, |
252 | |
253 | // Unmangled names can be remapped as complete encodings. |
254 | { |
255 | .Equivalences: { |
256 | {.Kind: FragmentKind::Encoding, .First: "3foo" , .Second: "3bar" }, |
257 | }, |
258 | .Classes: { |
259 | // foo == bar |
260 | {"foo" , "bar" }, |
261 | // void f<foo>() == void f<bar>() |
262 | {"_Z1fIL_Z3fooEEvv" , "_Z1fIL_Z3barEEvv" }, |
263 | } |
264 | }, |
265 | }; |
266 | } |
267 | |
268 | // A function to get a set of test cases for forward template references. |
269 | static std::vector<Testcase> getForwardTemplateReferenceTestcases() { |
270 | return { |
271 | // ForwardTemplateReference does not support canonicalization. |
272 | // FIXME: We should consider ways of fixing this, perhaps by eliminating |
273 | // the ForwardTemplateReference node with a tree transformation. |
274 | { |
275 | .Equivalences: { |
276 | // X::operator T() <with T = A> == Y::operator T() <with T = A> |
277 | {.Kind: FragmentKind::Encoding, .First: "N1XcvT_I1AEEv" , .Second: "N1YcvT_I1AEEv" }, |
278 | // A == B |
279 | {.Kind: FragmentKind::Name, .First: "1A" , .Second: "1B" }, |
280 | }, |
281 | .Classes: { |
282 | // All combinations result in unique equivalence classes. |
283 | {"_ZN1XcvT_I1AEEv" }, |
284 | {"_ZN1XcvT_I1BEEv" }, |
285 | {"_ZN1YcvT_I1AEEv" }, |
286 | {"_ZN1YcvT_I1BEEv" }, |
287 | // Even giving the same string twice gives a new class. |
288 | {"_ZN1XcvT_I1AEEv" }, |
289 | } |
290 | }, |
291 | }; |
292 | } |
293 | |
294 | template<bool CanonicalizeFirst> |
295 | static void testTestcases(ArrayRef<Testcase> Testcases) { |
296 | for (const auto &Testcase : Testcases) { |
297 | llvm::ItaniumManglingCanonicalizer Canonicalizer; |
298 | for (const auto &Equiv : Testcase.Equivalences) { |
299 | auto Result = |
300 | Canonicalizer.addEquivalence(Kind: Equiv.Kind, First: Equiv.First, Second: Equiv.Second); |
301 | EXPECT_EQ(Result, EquivalenceError::Success) |
302 | << "couldn't add equivalence between " << Equiv.First << " and " |
303 | << Equiv.Second; |
304 | } |
305 | |
306 | using CanonKey = llvm::ItaniumManglingCanonicalizer::Key; |
307 | |
308 | std::map<const EquivalenceClass*, CanonKey> Keys; |
309 | if (CanonicalizeFirst) |
310 | for (const auto &Class : Testcase.Classes) |
311 | Keys.insert(x: {&Class, Canonicalizer.canonicalize(Mangling: *Class.begin())}); |
312 | |
313 | std::map<CanonKey, llvm::StringRef> Found; |
314 | for (const auto &Class : Testcase.Classes) { |
315 | CanonKey ClassKey = Keys[&Class]; |
316 | for (llvm::StringRef Str : Class) { |
317 | // Force a copy to be made when calling lookup to test that it doesn't |
318 | // retain any part of the provided string. |
319 | CanonKey ThisKey = CanonicalizeFirst |
320 | ? Canonicalizer.lookup(Mangling: std::string(Str)) |
321 | : Canonicalizer.canonicalize(Mangling: Str); |
322 | EXPECT_NE(ThisKey, CanonKey()) << "couldn't canonicalize " << Str; |
323 | if (ClassKey) { |
324 | EXPECT_EQ(ThisKey, ClassKey) |
325 | << Str << " not in the same class as " << *Class.begin(); |
326 | } else { |
327 | ClassKey = ThisKey; |
328 | } |
329 | } |
330 | EXPECT_TRUE(Found.insert({ClassKey, *Class.begin()}).second) |
331 | << *Class.begin() << " is in the same class as " << Found[ClassKey]; |
332 | } |
333 | } |
334 | } |
335 | |
336 | TEST(ItaniumManglingCanonicalizerTest, TestCanonicalize) { |
337 | testTestcases<false>(Testcases: getTestcases()); |
338 | } |
339 | |
340 | TEST(ItaniumManglingCanonicalizerTest, TestLookup) { |
341 | testTestcases<true>(Testcases: getTestcases()); |
342 | } |
343 | |
344 | TEST(ItaniumManglingCanonicalizerTest, TestForwardTemplateReference) { |
345 | // lookup(...) after canonicalization (intentionally) returns different |
346 | // values for this testcase. |
347 | testTestcases<false>(Testcases: getForwardTemplateReferenceTestcases()); |
348 | } |
349 | |
350 | |
351 | TEST(ItaniumManglingCanonicalizerTest, TestInvalidManglings) { |
352 | llvm::ItaniumManglingCanonicalizer Canonicalizer; |
353 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "" , "1X" ), |
354 | EquivalenceError::InvalidFirstMangling); |
355 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1X" , "1ab" ), |
356 | EquivalenceError::InvalidSecondMangling); |
357 | EXPECT_EQ(Canonicalizer.canonicalize("_Z3fooE" ), |
358 | llvm::ItaniumManglingCanonicalizer::Key()); |
359 | EXPECT_EQ(Canonicalizer.canonicalize("_Zfoo" ), |
360 | llvm::ItaniumManglingCanonicalizer::Key()); |
361 | |
362 | // A reference to a template parameter ('T_' etc) cannot appear in a <name>, |
363 | // because we don't have template arguments to bind to it. (The arguments in |
364 | // an 'I ... E' construct in the <name> aren't registered as |
365 | // backreferenceable arguments in this sense, because they're not part of |
366 | // the template argument list of an <encoding>. |
367 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Name, "N1XcvT_I1AEE" , |
368 | "1f" ), |
369 | EquivalenceError::InvalidFirstMangling); |
370 | } |
371 | |
372 | TEST(ItaniumManglingCanonicalizerTest, TestBadEquivalenceOrder) { |
373 | llvm::ItaniumManglingCanonicalizer Canonicalizer; |
374 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "N1P1XE" , "N1Q1XE" ), |
375 | EquivalenceError::Success); |
376 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1P" , "1Q" ), |
377 | EquivalenceError::ManglingAlreadyUsed); |
378 | |
379 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "N1C1XE" , "N1A1YE" ), |
380 | EquivalenceError::Success); |
381 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1A" , "1B" ), |
382 | EquivalenceError::Success); |
383 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1C" , "1D" ), |
384 | EquivalenceError::Success); |
385 | EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1B" , "1D" ), |
386 | EquivalenceError::ManglingAlreadyUsed); |
387 | } |
388 | |
389 | } // end anonymous namespace |
390 | |