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