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