unittests/Support/ItaniumManglingCanonicalizerTest.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Support/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       {
  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::foo
  73         {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_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         {FragmentKind::Name,
  89          "NSt3__111char_traitsE",
  90          "NSt7__cxx1111char_traitsE"},
  91         // std::__1::allocator == std::allocator
  92         {FragmentKind::Name,
  93          "NSt3__19allocatorE",
  94          "Sa"}, // "Sa" is not strictly a <name> but we accept it as one.
  95         // std::__1::vector == std::vector
  96         {FragmentKind::Name,
  97          "St6vector",
  98          "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         {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 <-> Y
 113         {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::__cxx11
 132         {FragmentKind::Name, "St3__1", "St7__cxx11"},
 133         // std::__1::allocator == std::allocator
 134         {FragmentKind::Name, "NSt3__19allocatorE", "Sa"},
 135         // std::vector == std::__1::vector
 136         {FragmentKind::Name, "St6vector", "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         {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 == std
 164         {FragmentKind::Name, "St3__1", "St"},
 165         // std::__1 == std::__cxx11
 166         {FragmentKind::Name, "St3__1", "St7__cxx11"},
 167         // FIXME: Should a 'std' equivalence also cover the predefined
 168         // substitutions?
 169         // std::__1::allocator == std::allocator
 170         {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> <-> B
 216         {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 }
 254
 255 // A function to get a set of test cases for forward template references.
 256 static std::vector<Testcase> getForwardTemplateReferenceTestcases() {
 257   return {
 258     // ForwardTemplateReference does not support canonicalization.
 259     // FIXME: We should consider ways of fixing this, perhaps by eliminating
 260     // the ForwardTemplateReference node with a tree transformation.
 261     {
 262       {
 263         // X::operator T() <with T = A> == Y::operator T() <with T = A>
 264         {FragmentKind::Encoding, "N1XcvT_I1AEEv", "N1YcvT_I1AEEv"},
 265         // A == B
 266         {FragmentKind::Name, "1A", "1B"},
 267       },
 268       {
 269         // All combinations result in unique equivalence classes.
 270         {"_ZN1XcvT_I1AEEv"},
 271         {"_ZN1XcvT_I1BEEv"},
 272         {"_ZN1YcvT_I1AEEv"},
 273         {"_ZN1YcvT_I1BEEv"},
 274         // Even giving the same string twice gives a new class.
 275         {"_ZN1XcvT_I1AEEv"},
 276       }
 277     },
 278   };
 279 }
 280
 281 template<bool CanonicalizeFirst>
 282 static void testTestcases(ArrayRef<Testcase> Testcases) {
 283   for (const auto &Testcase : Testcases) {
 284     llvm::ItaniumManglingCanonicalizer Canonicalizer;
 285     for (const auto &Equiv : Testcase.Equivalences) {
 286       auto Result =
 287           Canonicalizer.addEquivalence(Equiv.Kind, Equiv.First, Equiv.Second);
 288       EXPECT_EQ(Result, EquivalenceError::Success)
 289           << "couldn't add equivalence between " << Equiv.First << " and "
 290           << Equiv.Second;
 291     }
 292
 293     using CanonKey = llvm::ItaniumManglingCanonicalizer::Key;
 294
 295     std::map<const EquivalenceClass*, CanonKey> Keys;
 296     if (CanonicalizeFirst)
 297       for (const auto &Class : Testcase.Classes)
 298         Keys.insert({&Class, Canonicalizer.canonicalize(*Class.begin())});
 299
 300     std::map<CanonKey, llvm::StringRef> Found;
 301     for (const auto &Class : Testcase.Classes) {
 302       CanonKey ClassKey = Keys[&Class];
 303       for (llvm::StringRef Str : Class) {
 304         // Force a copy to be made when calling lookup to test that it doesn't
 305         // retain any part of the provided string.
 306         CanonKey ThisKey = CanonicalizeFirst
 307                                ? Canonicalizer.lookup(std::string(Str))
 308                                : Canonicalizer.canonicalize(Str);
 309         EXPECT_NE(ThisKey, CanonKey()) << "couldn't canonicalize " << Str;
 310         if (ClassKey) {
 311           EXPECT_EQ(ThisKey, ClassKey)
 312               << Str << " not in the same class as " << *Class.begin();
 313         } else {
 314           ClassKey = ThisKey;
 315         }
 316       }
 317       EXPECT_TRUE(Found.insert({ClassKey, *Class.begin()}).second)
 318           << *Class.begin() << " is in the same class as " << Found[ClassKey];
 319     }
 320   }
 321 }
 322
 323 TEST(ItaniumManglingCanonicalizerTest, TestCanonicalize) {
 324   testTestcases<false>(getTestcases());
 325 }
 326
 327 TEST(ItaniumManglingCanonicalizerTest, TestLookup) {
 328   testTestcases<true>(getTestcases());
 329 }
 330
 331 TEST(ItaniumManglingCanonicalizerTest, TestForwardTemplateReference) {
 332   // lookup(...) after canonicalization (intentionally) returns different
 333   // values for this testcase.
 334   testTestcases<false>(getForwardTemplateReferenceTestcases());
 335 }
 336
 337
 338 TEST(ItaniumManglingCanonicalizerTest, TestInvalidManglings) {
 339   llvm::ItaniumManglingCanonicalizer Canonicalizer;
 340   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "", "1X"),
 341             EquivalenceError::InvalidFirstMangling);
 342   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1X", "1ab"),
 343             EquivalenceError::InvalidSecondMangling);
 344   EXPECT_EQ(Canonicalizer.canonicalize("_Z3fooE"),
 345             llvm::ItaniumManglingCanonicalizer::Key());
 346   EXPECT_EQ(Canonicalizer.canonicalize("foo"),
 347             llvm::ItaniumManglingCanonicalizer::Key());
 348
 349   // A reference to a template parameter ('T_' etc) cannot appear in a <name>,
 350   // because we don't have template arguments to bind to it. (The arguments in
 351   // an 'I ... E' construct in the <name> aren't registered as
 352   // backreferenceable arguments in this sense, because they're not part of
 353   // the template argument list of an <encoding>.
 354   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Name, "N1XcvT_I1AEE",
 355                                          "1f"),
 356             EquivalenceError::InvalidFirstMangling);
 357 }
 358
 359 TEST(ItaniumManglingCanonicalizerTest, TestBadEquivalenceOrder) {
 360   llvm::ItaniumManglingCanonicalizer Canonicalizer;
 361   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "N1P1XE", "N1Q1XE"),
 362             EquivalenceError::Success);
 363   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1P", "1Q"),
 364             EquivalenceError::ManglingAlreadyUsed);
 365
 366   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "N1C1XE", "N1A1YE"),
 367             EquivalenceError::Success);
 368   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1A", "1B"),
 369             EquivalenceError::Success);
 370   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1C", "1D"),
 371             EquivalenceError::Success);
 372   EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1B", "1D"),
 373             EquivalenceError::ManglingAlreadyUsed);
 374 }
 375
 376 } // end anonymous namespace