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