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