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