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