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