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
18using namespace llvm;
19
20namespace {
21
22using EquivalenceError = llvm::ItaniumManglingCanonicalizer::EquivalenceError;
23using FragmentKind = llvm::ItaniumManglingCanonicalizer::FragmentKind;
24
25struct 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.
32using EquivalenceClass = std::vector<llvm::StringRef>;
33
34struct 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.
43static 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.
269static 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
294template<bool CanonicalizeFirst>
295static 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
336TEST(ItaniumManglingCanonicalizerTest, TestCanonicalize) {
337 testTestcases<false>(Testcases: getTestcases());
338}
339
340TEST(ItaniumManglingCanonicalizerTest, TestLookup) {
341 testTestcases<true>(Testcases: getTestcases());
342}
343
344TEST(ItaniumManglingCanonicalizerTest, TestForwardTemplateReference) {
345 // lookup(...) after canonicalization (intentionally) returns different
346 // values for this testcase.
347 testTestcases<false>(Testcases: getForwardTemplateReferenceTestcases());
348}
349
350
351TEST(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
372TEST(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

source code of llvm/unittests/ProfileData/ItaniumManglingCanonicalizerTest.cpp