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