contrib/llvm/tools/clang/lib/Index/USRGeneration.cpp

   1 //===- USRGeneration.cpp - Routines for USR generation --------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "clang/Index/USRGeneration.h"
  11 #include "clang/AST/ASTContext.h"
  12 #include "clang/AST/DeclTemplate.h"
  13 #include "clang/AST/DeclVisitor.h"
  14 #include "clang/Lex/PreprocessingRecord.h"
  15 #include "llvm/Support/Path.h"
  16 #include "llvm/Support/raw_ostream.h"
  17
  18 using namespace clang;
  19 using namespace clang::index;
  20
  21 //===----------------------------------------------------------------------===//
  22 // USR generation.
  23 //===----------------------------------------------------------------------===//
  24
  25 /// \returns true on error.
  26 static bool printLoc(llvm::raw_ostream &OS, SourceLocation Loc,
  27                      const SourceManager &SM, bool IncludeOffset) {
  28   if (Loc.isInvalid()) {
  29     return true;
  30   }
  31   Loc = SM.getExpansionLoc(Loc);
  32   const std::pair<FileID, unsigned> &Decomposed = SM.getDecomposedLoc(Loc);
  33   const FileEntry *FE = SM.getFileEntryForID(Decomposed.first);
  34   if (FE) {
  35     OS << llvm::sys::path::filename(FE->getName());
  36   } else {
  37     // This case really isn't interesting.
  38     return true;
  39   }
  40   if (IncludeOffset) {
  41     // Use the offest into the FileID to represent the location.  Using
  42     // a line/column can cause us to look back at the original source file,
  43     // which is expensive.
  44     OS << '@' << Decomposed.second;
  45   }
  46   return false;
  47 }
  48
  49 namespace {
  50 class USRGenerator : public ConstDeclVisitor<USRGenerator> {
  51   SmallVectorImpl<char> &Buf;
  52   llvm::raw_svector_ostream Out;
  53   bool IgnoreResults;
  54   ASTContext *Context;
  55   bool generatedLoc;
  56
  57   llvm::DenseMap<const Type *, unsigned> TypeSubstitutions;
  58
  59 public:
  60   explicit USRGenerator(ASTContext *Ctx, SmallVectorImpl<char> &Buf)
  61   : Buf(Buf),
  62     Out(Buf),
  63     IgnoreResults(false),
  64     Context(Ctx),
  65     generatedLoc(false)
  66   {
  67     // Add the USR space prefix.
  68     Out << getUSRSpacePrefix();
  69   }
  70
  71   bool ignoreResults() const { return IgnoreResults; }
  72
  73   // Visitation methods from generating USRs from AST elements.
  74   void VisitDeclContext(const DeclContext *D);
  75   void VisitFieldDecl(const FieldDecl *D);
  76   void VisitFunctionDecl(const FunctionDecl *D);
  77   void VisitNamedDecl(const NamedDecl *D);
  78   void VisitNamespaceDecl(const NamespaceDecl *D);
  79   void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D);
  80   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D);
  81   void VisitClassTemplateDecl(const ClassTemplateDecl *D);
  82   void VisitObjCContainerDecl(const ObjCContainerDecl *CD);
  83   void VisitObjCMethodDecl(const ObjCMethodDecl *MD);
  84   void VisitObjCPropertyDecl(const ObjCPropertyDecl *D);
  85   void VisitObjCPropertyImplDecl(const ObjCPropertyImplDecl *D);
  86   void VisitTagDecl(const TagDecl *D);
  87   void VisitTypedefDecl(const TypedefDecl *D);
  88   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D);
  89   void VisitVarDecl(const VarDecl *D);
  90   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D);
  91   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D);
  92
  93   void VisitLinkageSpecDecl(const LinkageSpecDecl *D) {
  94     IgnoreResults = true;
  95   }
  96
  97   void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) {
  98     IgnoreResults = true;
  99   }
 100
 101   void VisitUsingDecl(const UsingDecl *D) {
 102     IgnoreResults = true;
 103   }
 104
 105   void VisitUnresolvedUsingValueDecl(const UnresolvedUsingValueDecl *D) {
 106     IgnoreResults = true;
 107   }
 108
 109   void VisitUnresolvedUsingTypenameDecl(const UnresolvedUsingTypenameDecl *D) {
 110     IgnoreResults = true;
 111   }
 112
 113   bool ShouldGenerateLocation(const NamedDecl *D);
 114
 115   bool isLocal(const NamedDecl *D) {
 116     return D->getParentFunctionOrMethod() != nullptr;
 117   }
 118
 119   /// Generate the string component containing the location of the
 120   ///  declaration.
 121   bool GenLoc(const Decl *D, bool IncludeOffset);
 122
 123   /// String generation methods used both by the visitation methods
 124   /// and from other clients that want to directly generate USRs.  These
 125   /// methods do not construct complete USRs (which incorporate the parents
 126   /// of an AST element), but only the fragments concerning the AST element
 127   /// itself.
 128
 129   /// Generate a USR for an Objective-C class.
 130   void GenObjCClass(StringRef cls) {
 131     generateUSRForObjCClass(cls, Out);
 132   }
 133
 134   /// Generate a USR for an Objective-C class category.
 135   void GenObjCCategory(StringRef cls, StringRef cat) {
 136     generateUSRForObjCCategory(cls, cat, Out);
 137   }
 138
 139   /// Generate a USR fragment for an Objective-C property.
 140   void GenObjCProperty(StringRef prop, bool isClassProp) {
 141     generateUSRForObjCProperty(prop, isClassProp, Out);
 142   }
 143
 144   /// Generate a USR for an Objective-C protocol.
 145   void GenObjCProtocol(StringRef prot) {
 146     generateUSRForObjCProtocol(prot, Out);
 147   }
 148
 149   void VisitType(QualType T);
 150   void VisitTemplateParameterList(const TemplateParameterList *Params);
 151   void VisitTemplateName(TemplateName Name);
 152   void VisitTemplateArgument(const TemplateArgument &Arg);
 153
 154   /// Emit a Decl's name using NamedDecl::printName() and return true if
 155   ///  the decl had no name.
 156   bool EmitDeclName(const NamedDecl *D);
 157 };
 158 } // end anonymous namespace
 159
 160 //===----------------------------------------------------------------------===//
 161 // Generating USRs from ASTS.
 162 //===----------------------------------------------------------------------===//
 163
 164 bool USRGenerator::EmitDeclName(const NamedDecl *D) {
 165   const unsigned startSize = Buf.size();
 166   D->printName(Out);
 167   const unsigned endSize = Buf.size();
 168   return startSize == endSize;
 169 }
 170
 171 bool USRGenerator::ShouldGenerateLocation(const NamedDecl *D) {
 172   if (D->isExternallyVisible())
 173     return false;
 174   if (D->getParentFunctionOrMethod())
 175     return true;
 176   SourceLocation Loc = D->getLocation();
 177   if (Loc.isInvalid())
 178     return false;
 179   const SourceManager &SM = Context->getSourceManager();
 180   return !SM.isInSystemHeader(Loc);
 181 }
 182
 183 void USRGenerator::VisitDeclContext(const DeclContext *DC) {
 184   if (const NamedDecl *D = dyn_cast<NamedDecl>(DC))
 185     Visit(D);
 186 }
 187
 188 void USRGenerator::VisitFieldDecl(const FieldDecl *D) {
 189   // The USR for an ivar declared in a class extension is based on the
 190   // ObjCInterfaceDecl, not the ObjCCategoryDecl.
 191   if (const ObjCInterfaceDecl *ID = Context->getObjContainingInterface(D))
 192     Visit(ID);
 193   else
 194     VisitDeclContext(D->getDeclContext());
 195   Out << (isa<ObjCIvarDecl>(D) ? "@" : "@FI@");
 196   if (EmitDeclName(D)) {
 197     // Bit fields can be anonymous.
 198     IgnoreResults = true;
 199     return;
 200   }
 201 }
 202
 203 void USRGenerator::VisitFunctionDecl(const FunctionDecl *D) {
 204   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
 205     return;
 206
 207   VisitDeclContext(D->getDeclContext());
 208   bool IsTemplate = false;
 209   if (FunctionTemplateDecl *FunTmpl = D->getDescribedFunctionTemplate()) {
 210     IsTemplate = true;
 211     Out << "@FT@";
 212     VisitTemplateParameterList(FunTmpl->getTemplateParameters());
 213   } else
 214     Out << "@F@";
 215
 216   PrintingPolicy Policy(Context->getLangOpts());
 217   // Forward references can have different template argument names. Suppress the
 218   // template argument names in constructors to make their USR more stable.
 219   Policy.SuppressTemplateArgsInCXXConstructors = true;
 220   D->getDeclName().print(Out, Policy);
 221
 222   ASTContext &Ctx = *Context;
 223   if ((!Ctx.getLangOpts().CPlusPlus || D->isExternC()) &&
 224       !D->hasAttr<OverloadableAttr>())
 225     return;
 226
 227   if (const TemplateArgumentList *
 228         SpecArgs = D->getTemplateSpecializationArgs()) {
 229     Out << '<';
 230     for (unsigned I = 0, N = SpecArgs->size(); I != N; ++I) {
 231       Out << '#';
 232       VisitTemplateArgument(SpecArgs->get(I));
 233     }
 234     Out << '>';
 235   }
 236
 237   // Mangle in type information for the arguments.
 238   for (auto PD : D->parameters()) {
 239     Out << '#';
 240     VisitType(PD->getType());
 241   }
 242   if (D->isVariadic())
 243     Out << '.';
 244   if (IsTemplate) {
 245     // Function templates can be overloaded by return type, for example:
 246     // \code
 247     //   template <class T> typename T::A foo() {}
 248     //   template <class T> typename T::B foo() {}
 249     // \endcode
 250     Out << '#';
 251     VisitType(D->getReturnType());
 252   }
 253   Out << '#';
 254   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
 255     if (MD->isStatic())
 256       Out << 'S';
 257     if (unsigned quals = MD->getTypeQualifiers())
 258       Out << (char)('0' + quals);
 259     switch (MD->getRefQualifier()) {
 260     case RQ_None: break;
 261     case RQ_LValue: Out << '&'; break;
 262     case RQ_RValue: Out << "&&"; break;
 263     }
 264   }
 265 }
 266
 267 void USRGenerator::VisitNamedDecl(const NamedDecl *D) {
 268   VisitDeclContext(D->getDeclContext());
 269   Out << "@";
 270
 271   if (EmitDeclName(D)) {
 272     // The string can be empty if the declaration has no name; e.g., it is
 273     // the ParmDecl with no name for declaration of a function pointer type,
 274     // e.g.: void  (*f)(void *);
 275     // In this case, don't generate a USR.
 276     IgnoreResults = true;
 277   }
 278 }
 279
 280 void USRGenerator::VisitVarDecl(const VarDecl *D) {
 281   // VarDecls can be declared 'extern' within a function or method body,
 282   // but their enclosing DeclContext is the function, not the TU.  We need
 283   // to check the storage class to correctly generate the USR.
 284   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
 285     return;
 286
 287   VisitDeclContext(D->getDeclContext());
 288
 289   if (VarTemplateDecl *VarTmpl = D->getDescribedVarTemplate()) {
 290     Out << "@VT";
 291     VisitTemplateParameterList(VarTmpl->getTemplateParameters());
 292   } else if (const VarTemplatePartialSpecializationDecl *PartialSpec
 293              = dyn_cast<VarTemplatePartialSpecializationDecl>(D)) {
 294     Out << "@VP";
 295     VisitTemplateParameterList(PartialSpec->getTemplateParameters());
 296   }
 297
 298   // Variables always have simple names.
 299   StringRef s = D->getName();
 300
 301   // The string can be empty if the declaration has no name; e.g., it is
 302   // the ParmDecl with no name for declaration of a function pointer type, e.g.:
 303   //    void  (*f)(void *);
 304   // In this case, don't generate a USR.
 305   if (s.empty())
 306     IgnoreResults = true;
 307   else
 308     Out << '@' << s;
 309
 310   // For a template specialization, mangle the template arguments.
 311   if (const VarTemplateSpecializationDecl *Spec
 312                               = dyn_cast<VarTemplateSpecializationDecl>(D)) {
 313     const TemplateArgumentList &Args = Spec->getTemplateInstantiationArgs();
 314     Out << '>';
 315     for (unsigned I = 0, N = Args.size(); I != N; ++I) {
 316       Out << '#';
 317       VisitTemplateArgument(Args.get(I));
 318     }
 319   }
 320 }
 321
 322 void USRGenerator::VisitNonTypeTemplateParmDecl(
 323                                         const NonTypeTemplateParmDecl *D) {
 324   GenLoc(D, /*IncludeOffset=*/true);
 325 }
 326
 327 void USRGenerator::VisitTemplateTemplateParmDecl(
 328                                         const TemplateTemplateParmDecl *D) {
 329   GenLoc(D, /*IncludeOffset=*/true);
 330 }
 331
 332 void USRGenerator::VisitNamespaceDecl(const NamespaceDecl *D) {
 333   if (D->isAnonymousNamespace()) {
 334     Out << "@aN";
 335     return;
 336   }
 337
 338   VisitDeclContext(D->getDeclContext());
 339   if (!IgnoreResults)
 340     Out << "@N@" << D->getName();
 341 }
 342
 343 void USRGenerator::VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
 344   VisitFunctionDecl(D->getTemplatedDecl());
 345 }
 346
 347 void USRGenerator::VisitClassTemplateDecl(const ClassTemplateDecl *D) {
 348   VisitTagDecl(D->getTemplatedDecl());
 349 }
 350
 351 void USRGenerator::VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) {
 352   VisitDeclContext(D->getDeclContext());
 353   if (!IgnoreResults)
 354     Out << "@NA@" << D->getName();
 355 }
 356
 357 void USRGenerator::VisitObjCMethodDecl(const ObjCMethodDecl *D) {
 358   const DeclContext *container = D->getDeclContext();
 359   if (const ObjCProtocolDecl *pd = dyn_cast<ObjCProtocolDecl>(container)) {
 360     Visit(pd);
 361   }
 362   else {
 363     // The USR for a method declared in a class extension or category is based on
 364     // the ObjCInterfaceDecl, not the ObjCCategoryDecl.
 365     const ObjCInterfaceDecl *ID = D->getClassInterface();
 366     if (!ID) {
 367       IgnoreResults = true;
 368       return;
 369     }
 370     Visit(ID);
 371   }
 372   // Ideally we would use 'GenObjCMethod', but this is such a hot path
 373   // for Objective-C code that we don't want to use
 374   // DeclarationName::getAsString().
 375   Out << (D->isInstanceMethod() ? "(im)" : "(cm)")
 376       << DeclarationName(D->getSelector());
 377 }
 378
 379 void USRGenerator::VisitObjCContainerDecl(const ObjCContainerDecl *D) {
 380   switch (D->getKind()) {
 381     default:
 382       llvm_unreachable("Invalid ObjC container.");
 383     case Decl::ObjCInterface:
 384     case Decl::ObjCImplementation:
 385       GenObjCClass(D->getName());
 386       break;
 387     case Decl::ObjCCategory: {
 388       const ObjCCategoryDecl *CD = cast<ObjCCategoryDecl>(D);
 389       const ObjCInterfaceDecl *ID = CD->getClassInterface();
 390       if (!ID) {
 391         // Handle invalid code where the @interface might not
 392         // have been specified.
 393         // FIXME: We should be able to generate this USR even if the
 394         // @interface isn't available.
 395         IgnoreResults = true;
 396         return;
 397       }
 398       // Specially handle class extensions, which are anonymous categories.
 399       // We want to mangle in the location to uniquely distinguish them.
 400       if (CD->IsClassExtension()) {
 401         Out << "objc(ext)" << ID->getName() << '@';
 402         GenLoc(CD, /*IncludeOffset=*/true);
 403       }
 404       else
 405         GenObjCCategory(ID->getName(), CD->getName());
 406
 407       break;
 408     }
 409     case Decl::ObjCCategoryImpl: {
 410       const ObjCCategoryImplDecl *CD = cast<ObjCCategoryImplDecl>(D);
 411       const ObjCInterfaceDecl *ID = CD->getClassInterface();
 412       if (!ID) {
 413         // Handle invalid code where the @interface might not
 414         // have been specified.
 415         // FIXME: We should be able to generate this USR even if the
 416         // @interface isn't available.
 417         IgnoreResults = true;
 418         return;
 419       }
 420       GenObjCCategory(ID->getName(), CD->getName());
 421       break;
 422     }
 423     case Decl::ObjCProtocol:
 424       GenObjCProtocol(cast<ObjCProtocolDecl>(D)->getName());
 425       break;
 426   }
 427 }
 428
 429 void USRGenerator::VisitObjCPropertyDecl(const ObjCPropertyDecl *D) {
 430   // The USR for a property declared in a class extension or category is based
 431   // on the ObjCInterfaceDecl, not the ObjCCategoryDecl.
 432   if (const ObjCInterfaceDecl *ID = Context->getObjContainingInterface(D))
 433     Visit(ID);
 434   else
 435     Visit(cast<Decl>(D->getDeclContext()));
 436   GenObjCProperty(D->getName(), D->isClassProperty());
 437 }
 438
 439 void USRGenerator::VisitObjCPropertyImplDecl(const ObjCPropertyImplDecl *D) {
 440   if (ObjCPropertyDecl *PD = D->getPropertyDecl()) {
 441     VisitObjCPropertyDecl(PD);
 442     return;
 443   }
 444
 445   IgnoreResults = true;
 446 }
 447
 448 void USRGenerator::VisitTagDecl(const TagDecl *D) {
 449   // Add the location of the tag decl to handle resolution across
 450   // translation units.
 451   if (!isa<EnumDecl>(D) &&
 452       ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
 453     return;
 454
 455   D = D->getCanonicalDecl();
 456   VisitDeclContext(D->getDeclContext());
 457
 458   bool AlreadyStarted = false;
 459   if (const CXXRecordDecl *CXXRecord = dyn_cast<CXXRecordDecl>(D)) {
 460     if (ClassTemplateDecl *ClassTmpl = CXXRecord->getDescribedClassTemplate()) {
 461       AlreadyStarted = true;
 462
 463       switch (D->getTagKind()) {
 464       case TTK_Interface:
 465       case TTK_Class:
 466       case TTK_Struct: Out << "@ST"; break;
 467       case TTK_Union:  Out << "@UT"; break;
 468       case TTK_Enum: llvm_unreachable("enum template");
 469       }
 470       VisitTemplateParameterList(ClassTmpl->getTemplateParameters());
 471     } else if (const ClassTemplatePartialSpecializationDecl *PartialSpec
 472                 = dyn_cast<ClassTemplatePartialSpecializationDecl>(CXXRecord)) {
 473       AlreadyStarted = true;
 474
 475       switch (D->getTagKind()) {
 476       case TTK_Interface:
 477       case TTK_Class:
 478       case TTK_Struct: Out << "@SP"; break;
 479       case TTK_Union:  Out << "@UP"; break;
 480       case TTK_Enum: llvm_unreachable("enum partial specialization");
 481       }
 482       VisitTemplateParameterList(PartialSpec->getTemplateParameters());
 483     }
 484   }
 485
 486   if (!AlreadyStarted) {
 487     switch (D->getTagKind()) {
 488       case TTK_Interface:
 489       case TTK_Class:
 490       case TTK_Struct: Out << "@S"; break;
 491       case TTK_Union:  Out << "@U"; break;
 492       case TTK_Enum:   Out << "@E"; break;
 493     }
 494   }
 495
 496   Out << '@';
 497   assert(Buf.size() > 0);
 498   const unsigned off = Buf.size() - 1;
 499
 500   if (EmitDeclName(D)) {
 501     if (const TypedefNameDecl *TD = D->getTypedefNameForAnonDecl()) {
 502       Buf[off] = 'A';
 503       Out << '@' << *TD;
 504     }
 505   else {
 506     if (D->isEmbeddedInDeclarator() && !D->isFreeStanding()) {
 507       printLoc(Out, D->getLocation(), Context->getSourceManager(), true);
 508     } else {
 509       Buf[off] = 'a';
 510       if (auto *ED = dyn_cast<EnumDecl>(D)) {
 511         // Distinguish USRs of anonymous enums by using their first enumerator.
 512         auto enum_range = ED->enumerators();
 513         if (enum_range.begin() != enum_range.end()) {
 514           Out << '@' << **enum_range.begin();
 515         }
 516       }
 517     }
 518   }
 519   }
 520
 521   // For a class template specialization, mangle the template arguments.
 522   if (const ClassTemplateSpecializationDecl *Spec
 523                               = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
 524     const TemplateArgumentList &Args = Spec->getTemplateInstantiationArgs();
 525     Out << '>';
 526     for (unsigned I = 0, N = Args.size(); I != N; ++I) {
 527       Out << '#';
 528       VisitTemplateArgument(Args.get(I));
 529     }
 530   }
 531 }
 532
 533 void USRGenerator::VisitTypedefDecl(const TypedefDecl *D) {
 534   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
 535     return;
 536   const DeclContext *DC = D->getDeclContext();
 537   if (const NamedDecl *DCN = dyn_cast<NamedDecl>(DC))
 538     Visit(DCN);
 539   Out << "@T@";
 540   Out << D->getName();
 541 }
 542
 543 void USRGenerator::VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
 544   GenLoc(D, /*IncludeOffset=*/true);
 545 }
 546
 547 bool USRGenerator::GenLoc(const Decl *D, bool IncludeOffset) {
 548   if (generatedLoc)
 549     return IgnoreResults;
 550   generatedLoc = true;
 551
 552   // Guard against null declarations in invalid code.
 553   if (!D) {
 554     IgnoreResults = true;
 555     return true;
 556   }
 557
 558   // Use the location of canonical decl.
 559   D = D->getCanonicalDecl();
 560
 561   IgnoreResults =
 562       IgnoreResults || printLoc(Out, D->getLocStart(),
 563                                 Context->getSourceManager(), IncludeOffset);
 564
 565   return IgnoreResults;
 566 }
 567
 568 void USRGenerator::VisitType(QualType T) {
 569   // This method mangles in USR information for types.  It can possibly
 570   // just reuse the naming-mangling logic used by codegen, although the
 571   // requirements for USRs might not be the same.
 572   ASTContext &Ctx = *Context;
 573
 574   do {
 575     T = Ctx.getCanonicalType(T);
 576     Qualifiers Q = T.getQualifiers();
 577     unsigned qVal = 0;
 578     if (Q.hasConst())
 579       qVal |= 0x1;
 580     if (Q.hasVolatile())
 581       qVal |= 0x2;
 582     if (Q.hasRestrict())
 583       qVal |= 0x4;
 584     if(qVal)
 585       Out << ((char) ('0' + qVal));
 586
 587     // Mangle in ObjC GC qualifiers?
 588
 589     if (const PackExpansionType *Expansion = T->getAs<PackExpansionType>()) {
 590       Out << 'P';
 591       T = Expansion->getPattern();
 592     }
 593
 594     if (const BuiltinType *BT = T->getAs<BuiltinType>()) {
 595       unsigned char c = '\0';
 596       switch (BT->getKind()) {
 597         case BuiltinType::Void:
 598           c = 'v'; break;
 599         case BuiltinType::Bool:
 600           c = 'b'; break;
 601         case BuiltinType::UChar:
 602           c = 'c'; break;
 603         case BuiltinType::Char16:
 604           c = 'q'; break;
 605         case BuiltinType::Char32:
 606           c = 'w'; break;
 607         case BuiltinType::UShort:
 608           c = 's'; break;
 609         case BuiltinType::UInt:
 610           c = 'i'; break;
 611         case BuiltinType::ULong:
 612           c = 'l'; break;
 613         case BuiltinType::ULongLong:
 614           c = 'k'; break;
 615         case BuiltinType::UInt128:
 616           c = 'j'; break;
 617         case BuiltinType::Char_U:
 618         case BuiltinType::Char_S:
 619           c = 'C'; break;
 620         case BuiltinType::SChar:
 621           c = 'r'; break;
 622         case BuiltinType::WChar_S:
 623         case BuiltinType::WChar_U:
 624           c = 'W'; break;
 625         case BuiltinType::Short:
 626           c = 'S'; break;
 627         case BuiltinType::Int:
 628           c = 'I'; break;
 629         case BuiltinType::Long:
 630           c = 'L'; break;
 631         case BuiltinType::LongLong:
 632           c = 'K'; break;
 633         case BuiltinType::Int128:
 634           c = 'J'; break;
 635         case BuiltinType::Half:
 636           c = 'h'; break;
 637         case BuiltinType::Float:
 638           c = 'f'; break;
 639         case BuiltinType::Double:
 640           c = 'd'; break;
 641         case BuiltinType::LongDouble:
 642           c = 'D'; break;
 643         case BuiltinType::Float128:
 644           c = 'Q'; break;
 645         case BuiltinType::NullPtr:
 646           c = 'n'; break;
 647 #define BUILTIN_TYPE(Id, SingletonId)
 648 #define PLACEHOLDER_TYPE(Id, SingletonId) case BuiltinType::Id:
 649 #include "clang/AST/BuiltinTypes.def"
 650         case BuiltinType::Dependent:
 651 #define IMAGE_TYPE(ImgType, Id, SingletonId, Access, Suffix) \
 652         case BuiltinType::Id:
 653 #include "clang/Basic/OpenCLImageTypes.def"
 654         case BuiltinType::OCLEvent:
 655         case BuiltinType::OCLClkEvent:
 656         case BuiltinType::OCLQueue:
 657         case BuiltinType::OCLNDRange:
 658         case BuiltinType::OCLReserveID:
 659         case BuiltinType::OCLSampler:
 660           IgnoreResults = true;
 661           return;
 662         case BuiltinType::ObjCId:
 663           c = 'o'; break;
 664         case BuiltinType::ObjCClass:
 665           c = 'O'; break;
 666         case BuiltinType::ObjCSel:
 667           c = 'e'; break;
 668       }
 669       Out << c;
 670       return;
 671     }
 672
 673     // If we have already seen this (non-built-in) type, use a substitution
 674     // encoding.
 675     llvm::DenseMap<const Type *, unsigned>::iterator Substitution
 676       = TypeSubstitutions.find(T.getTypePtr());
 677     if (Substitution != TypeSubstitutions.end()) {
 678       Out << 'S' << Substitution->second << '_';
 679       return;
 680     } else {
 681       // Record this as a substitution.
 682       unsigned Number = TypeSubstitutions.size();
 683       TypeSubstitutions[T.getTypePtr()] = Number;
 684     }
 685
 686     if (const PointerType *PT = T->getAs<PointerType>()) {
 687       Out << '*';
 688       T = PT->getPointeeType();
 689       continue;
 690     }
 691     if (const ObjCObjectPointerType *OPT = T->getAs<ObjCObjectPointerType>()) {
 692       Out << '*';
 693       T = OPT->getPointeeType();
 694       continue;
 695     }
 696     if (const RValueReferenceType *RT = T->getAs<RValueReferenceType>()) {
 697       Out << "&&";
 698       T = RT->getPointeeType();
 699       continue;
 700     }
 701     if (const ReferenceType *RT = T->getAs<ReferenceType>()) {
 702       Out << '&';
 703       T = RT->getPointeeType();
 704       continue;
 705     }
 706     if (const FunctionProtoType *FT = T->getAs<FunctionProtoType>()) {
 707       Out << 'F';
 708       VisitType(FT->getReturnType());
 709       for (const auto &I : FT->param_types())
 710         VisitType(I);
 711       if (FT->isVariadic())
 712         Out << '.';
 713       return;
 714     }
 715     if (const BlockPointerType *BT = T->getAs<BlockPointerType>()) {
 716       Out << 'B';
 717       T = BT->getPointeeType();
 718       continue;
 719     }
 720     if (const ComplexType *CT = T->getAs<ComplexType>()) {
 721       Out << '<';
 722       T = CT->getElementType();
 723       continue;
 724     }
 725     if (const TagType *TT = T->getAs<TagType>()) {
 726       Out << '$';
 727       VisitTagDecl(TT->getDecl());
 728       return;
 729     }
 730     if (const ObjCInterfaceType *OIT = T->getAs<ObjCInterfaceType>()) {
 731       Out << '$';
 732       VisitObjCInterfaceDecl(OIT->getDecl());
 733       return;
 734     }
 735     if (const ObjCObjectType *OIT = T->getAs<ObjCObjectType>()) {
 736       Out << 'Q';
 737       VisitType(OIT->getBaseType());
 738       for (auto *Prot : OIT->getProtocols())
 739         VisitObjCProtocolDecl(Prot);
 740       return;
 741     }
 742     if (const TemplateTypeParmType *TTP = T->getAs<TemplateTypeParmType>()) {
 743       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
 744       return;
 745     }
 746     if (const TemplateSpecializationType *Spec
 747                                     = T->getAs<TemplateSpecializationType>()) {
 748       Out << '>';
 749       VisitTemplateName(Spec->getTemplateName());
 750       Out << Spec->getNumArgs();
 751       for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
 752         VisitTemplateArgument(Spec->getArg(I));
 753       return;
 754     }
 755     if (const DependentNameType *DNT = T->getAs<DependentNameType>()) {
 756       Out << '^';
 757       // FIXME: Encode the qualifier, don't just print it.
 758       PrintingPolicy PO(Ctx.getLangOpts());
 759       PO.SuppressTagKeyword = true;
 760       PO.SuppressUnwrittenScope = true;
 761       PO.ConstantArraySizeAsWritten = false;
 762       PO.AnonymousTagLocations = false;
 763       DNT->getQualifier()->print(Out, PO);
 764       Out << ':' << DNT->getIdentifier()->getName();
 765       return;
 766     }
 767     if (const InjectedClassNameType *InjT = T->getAs<InjectedClassNameType>()) {
 768       T = InjT->getInjectedSpecializationType();
 769       continue;
 770     }
 771
 772     // Unhandled type.
 773     Out << ' ';
 774     break;
 775   } while (true);
 776 }
 777
 778 void USRGenerator::VisitTemplateParameterList(
 779                                          const TemplateParameterList *Params) {
 780   if (!Params)
 781     return;
 782   Out << '>' << Params->size();
 783   for (TemplateParameterList::const_iterator P = Params->begin(),
 784                                           PEnd = Params->end();
 785        P != PEnd; ++P) {
 786     Out << '#';
 787     if (isa<TemplateTypeParmDecl>(*P)) {
 788       if (cast<TemplateTypeParmDecl>(*P)->isParameterPack())
 789         Out<< 'p';
 790       Out << 'T';
 791       continue;
 792     }
 793
 794     if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
 795       if (NTTP->isParameterPack())
 796         Out << 'p';
 797       Out << 'N';
 798       VisitType(NTTP->getType());
 799       continue;
 800     }
 801
 802     TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
 803     if (TTP->isParameterPack())
 804       Out << 'p';
 805     Out << 't';
 806     VisitTemplateParameterList(TTP->getTemplateParameters());
 807   }
 808 }
 809
 810 void USRGenerator::VisitTemplateName(TemplateName Name) {
 811   if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
 812     if (TemplateTemplateParmDecl *TTP
 813                               = dyn_cast<TemplateTemplateParmDecl>(Template)) {
 814       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
 815       return;
 816     }
 817
 818     Visit(Template);
 819     return;
 820   }
 821
 822   // FIXME: Visit dependent template names.
 823 }
 824
 825 void USRGenerator::VisitTemplateArgument(const TemplateArgument &Arg) {
 826   switch (Arg.getKind()) {
 827   case TemplateArgument::Null:
 828     break;
 829
 830   case TemplateArgument::Declaration:
 831     Visit(Arg.getAsDecl());
 832     break;
 833
 834   case TemplateArgument::NullPtr:
 835     break;
 836
 837   case TemplateArgument::TemplateExpansion:
 838     Out << 'P'; // pack expansion of...
 839     // Fall through
 840   case TemplateArgument::Template:
 841     VisitTemplateName(Arg.getAsTemplateOrTemplatePattern());
 842     break;
 843
 844   case TemplateArgument::Expression:
 845     // FIXME: Visit expressions.
 846     break;
 847
 848   case TemplateArgument::Pack:
 849     Out << 'p' << Arg.pack_size();
 850     for (const auto &P : Arg.pack_elements())
 851       VisitTemplateArgument(P);
 852     break;
 853
 854   case TemplateArgument::Type:
 855     VisitType(Arg.getAsType());
 856     break;
 857
 858   case TemplateArgument::Integral:
 859     Out << 'V';
 860     VisitType(Arg.getIntegralType());
 861     Out << Arg.getAsIntegral();
 862     break;
 863   }
 864 }
 865
 866 //===----------------------------------------------------------------------===//
 867 // USR generation functions.
 868 //===----------------------------------------------------------------------===//
 869
 870 void clang::index::generateUSRForObjCClass(StringRef Cls, raw_ostream &OS) {
 871   OS << "objc(cs)" << Cls;
 872 }
 873
 874 void clang::index::generateUSRForObjCCategory(StringRef Cls, StringRef Cat,
 875                                               raw_ostream &OS) {
 876   OS << "objc(cy)" << Cls << '@' << Cat;
 877 }
 878
 879 void clang::index::generateUSRForObjCIvar(StringRef Ivar, raw_ostream &OS) {
 880   OS << '@' << Ivar;
 881 }
 882
 883 void clang::index::generateUSRForObjCMethod(StringRef Sel,
 884                                             bool IsInstanceMethod,
 885                                             raw_ostream &OS) {
 886   OS << (IsInstanceMethod ? "(im)" : "(cm)") << Sel;
 887 }
 888
 889 void clang::index::generateUSRForObjCProperty(StringRef Prop, bool isClassProp,
 890                                               raw_ostream &OS) {
 891   OS << (isClassProp ? "(cpy)" : "(py)") << Prop;
 892 }
 893
 894 void clang::index::generateUSRForObjCProtocol(StringRef Prot, raw_ostream &OS) {
 895   OS << "objc(pl)" << Prot;
 896 }
 897
 898 bool clang::index::generateUSRForDecl(const Decl *D,
 899                                       SmallVectorImpl<char> &Buf) {
 900   if (!D)
 901     return true;
 902   // We don't ignore decls with invalid source locations. Implicit decls, like
 903   // C++'s operator new function, can have invalid locations but it is fine to
 904   // create USRs that can identify them.
 905
 906   USRGenerator UG(&D->getASTContext(), Buf);
 907   UG.Visit(D);
 908   return UG.ignoreResults();
 909 }
 910
 911 bool clang::index::generateUSRForMacro(const MacroDefinitionRecord *MD,
 912                                        const SourceManager &SM,
 913                                        SmallVectorImpl<char> &Buf) {
 914   // Don't generate USRs for things with invalid locations.
 915   if (!MD || MD->getLocation().isInvalid())
 916     return true;
 917
 918   llvm::raw_svector_ostream Out(Buf);
 919
 920   // Assume that system headers are sane.  Don't put source location
 921   // information into the USR if the macro comes from a system header.
 922   SourceLocation Loc = MD->getLocation();
 923   bool ShouldGenerateLocation = !SM.isInSystemHeader(Loc);
 924
 925   Out << getUSRSpacePrefix();
 926   if (ShouldGenerateLocation)
 927     printLoc(Out, Loc, SM, /*IncludeOffset=*/true);
 928   Out << "@macro@";
 929   Out << MD->getName()->getName();
 930   return false;
 931 }