390 lines · cpp
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-exception6//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 the38 // 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 {49 {FragmentKind::Type, "Ss",50 "NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE"},51 {FragmentKind::Type, "Ss",52 "NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},53 },54 {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 {68 // ::X <-> ::N::X<int>69 {FragmentKind::Type, "1X", "N1N1XIiEE"},70 // ::T<T<int, int>, T<int, int>> <-> T<int>71 {FragmentKind::Type, "1TIS_IiiES0_E", "1TIiE"},72 // A::B::foo <-> AB::foo73 {FragmentKind::Name, "N1A1B3fooE", "N2AB3fooE"},74 },75 {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 {84 // std::__1::char_traits == std::__cxx11::char_traits85 // (Note that this is unused and should make no difference,86 // but it should not cause us to fail to match up the cases87 // below.)88 {FragmentKind::Name,89 "NSt3__111char_traitsE",90 "NSt7__cxx1111char_traitsE"},91 // std::__1::allocator == std::allocator92 {FragmentKind::Name,93 "NSt3__19allocatorE",94 "Sa"}, // "Sa" is not strictly a <name> but we accept it as one.95 // std::__1::vector == std::vector96 {FragmentKind::Name,97 "St6vector",98 "NSt3__16vectorE"},99 // std::__1::basic_string<100 // char101 // 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 {FragmentKind::Type,108 "NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE",109 "NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},110 // X<A> <-> X<B>111 {FragmentKind::Type, "1XI1AE", "1XI1BE"},112 // X <-> Y113 {FragmentKind::Name, "1X", "1Y"},114 },115 {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 {131 // std::__1 == std::__cxx11132 {FragmentKind::Name, "St3__1", "St7__cxx11"},133 // std::__1::allocator == std::allocator134 {FragmentKind::Name, "NSt3__19allocatorE", "Sa"},135 // std::vector == std::__1::vector136 {FragmentKind::Name, "St6vector", "NSt3__16vectorE"},137 // std::__cxx11::char_traits == std::char_traits138 // (This indirectly means that std::__1::char_traits == std::char_traits,139 // due to the std::__cxx11 == std::__1 equivalence, which is what we rely140 // on below.)141 {FragmentKind::Name, "NSt7__cxx1111char_traitsE", "St11char_traits"},142 },143 {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 {163 // std::__1 == std164 {FragmentKind::Name, "St3__1", "St"},165 // std::__1 == std::__cxx11166 {FragmentKind::Name, "St3__1", "St7__cxx11"},167 // FIXME: Should a 'std' equivalence also cover the predefined168 // substitutions?169 // std::__1::allocator == std::allocator170 {FragmentKind::Name, "NSt3__19allocatorE", "Sa"},171 },172 {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 {186 {FragmentKind::Type, "1A", "1B"},187 {FragmentKind::Type, "1A", "1C"},188 {FragmentKind::Type, "1D", "1B"},189 {FragmentKind::Type, "1C", "1E"},190 },191 {192 {"_Z1f1A", "_Z1f1B", "_Z1f1C", "_Z1f1D", "_Z1f1E"},193 {"_Z1f1F"},194 }195 },196 197 // Check <encoding>s.198 {199 {200 {FragmentKind::Encoding, "1fv", "1gv"},201 },202 {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 {213 // X <-> Y<X>214 {FragmentKind::Type, "1X", "1YI1XE"},215 // A<B> <-> B216 {FragmentKind::Type, "1AI1BE", "1B"},217 },218 {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 {229 {FragmentKind::Name, "3std", "St"},230 {FragmentKind::Name, "1X", "1Y"},231 {FragmentKind::Name, "N1X1ZE", "N1Y1ZE"},232 },233 {}234 },235 236 // Check that ctor and dtor variants are considered distinct.237 {238 {},239 {{"_ZN1XC1Ev"}, {"_ZN1XC2Ev"}, {"_ZN1XD1Ev"}, {"_ZN1XD2Ev"}}240 },241 242 // Ensure array types with and without bounds are handled properly.243 {244 {245 {FragmentKind::Type, "A_i", "A1_f"},246 },247 {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 {256 {FragmentKind::Encoding, "3foo", "3bar"},257 },258 {259 // foo == bar260 {"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 eliminating273 // the ForwardTemplateReference node with a tree transformation.274 {275 {276 // X::operator T() <with T = A> == Y::operator T() <with T = A>277 {FragmentKind::Encoding, "N1XcvT_I1AEEv", "N1YcvT_I1AEEv"},278 // A == B279 {FragmentKind::Name, "1A", "1B"},280 },281 {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(Equiv.Kind, Equiv.First, 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({&Class, Canonicalizer.canonicalize(*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't318 // retain any part of the provided string.319 CanonKey ThisKey = CanonicalizeFirst320 ? Canonicalizer.lookup(std::string(Str))321 : Canonicalizer.canonicalize(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>(getTestcases());338}339 340TEST(ItaniumManglingCanonicalizerTest, TestLookup) {341 testTestcases<true>(getTestcases());342}343 344TEST(ItaniumManglingCanonicalizerTest, TestForwardTemplateReference) {345 // lookup(...) after canonicalization (intentionally) returns different346 // values for this testcase.347 testTestcases<false>(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 in364 // an 'I ... E' construct in the <name> aren't registered as365 // backreferenceable arguments in this sense, because they're not part of366 // 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 namespace390