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->params()) {
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::NullPtr:
622           c = 'n'; break;
623 #define BUILTIN_TYPE(Id, SingletonId)
624 #define PLACEHOLDER_TYPE(Id, SingletonId) case BuiltinType::Id:
625 #include "clang/AST/BuiltinTypes.def"
626         case BuiltinType::Dependent:
627         case BuiltinType::OCLImage1d:
628         case BuiltinType::OCLImage1dArray:
629         case BuiltinType::OCLImage1dBuffer:
630         case BuiltinType::OCLImage2d:
631         case BuiltinType::OCLImage2dArray:
632         case BuiltinType::OCLImage2dDepth:
633         case BuiltinType::OCLImage2dArrayDepth:
634         case BuiltinType::OCLImage2dMSAA:
635         case BuiltinType::OCLImage2dArrayMSAA:
636         case BuiltinType::OCLImage2dMSAADepth:
637         case BuiltinType::OCLImage2dArrayMSAADepth:
638         case BuiltinType::OCLImage3d:
639         case BuiltinType::OCLEvent:
640         case BuiltinType::OCLClkEvent:
641         case BuiltinType::OCLQueue:
642         case BuiltinType::OCLNDRange:
643         case BuiltinType::OCLReserveID:
644         case BuiltinType::OCLSampler:
645           IgnoreResults = true;
646           return;
647         case BuiltinType::ObjCId:
648           c = 'o'; break;
649         case BuiltinType::ObjCClass:
650           c = 'O'; break;
651         case BuiltinType::ObjCSel:
652           c = 'e'; break;
653       }
654       Out << c;
655       return;
656     }
657 
658     // If we have already seen this (non-built-in) type, use a substitution
659     // encoding.
660     llvm::DenseMap<const Type *, unsigned>::iterator Substitution
661       = TypeSubstitutions.find(T.getTypePtr());
662     if (Substitution != TypeSubstitutions.end()) {
663       Out << 'S' << Substitution->second << '_';
664       return;
665     } else {
666       // Record this as a substitution.
667       unsigned Number = TypeSubstitutions.size();
668       TypeSubstitutions[T.getTypePtr()] = Number;
669     }
670 
671     if (const PointerType *PT = T->getAs<PointerType>()) {
672       Out << '*';
673       T = PT->getPointeeType();
674       continue;
675     }
676     if (const ObjCObjectPointerType *OPT = T->getAs<ObjCObjectPointerType>()) {
677       Out << '*';
678       T = OPT->getPointeeType();
679       continue;
680     }
681     if (const RValueReferenceType *RT = T->getAs<RValueReferenceType>()) {
682       Out << "&&";
683       T = RT->getPointeeType();
684       continue;
685     }
686     if (const ReferenceType *RT = T->getAs<ReferenceType>()) {
687       Out << '&';
688       T = RT->getPointeeType();
689       continue;
690     }
691     if (const FunctionProtoType *FT = T->getAs<FunctionProtoType>()) {
692       Out << 'F';
693       VisitType(FT->getReturnType());
694       for (const auto &I : FT->param_types())
695         VisitType(I);
696       if (FT->isVariadic())
697         Out << '.';
698       return;
699     }
700     if (const BlockPointerType *BT = T->getAs<BlockPointerType>()) {
701       Out << 'B';
702       T = BT->getPointeeType();
703       continue;
704     }
705     if (const ComplexType *CT = T->getAs<ComplexType>()) {
706       Out << '<';
707       T = CT->getElementType();
708       continue;
709     }
710     if (const TagType *TT = T->getAs<TagType>()) {
711       Out << '$';
712       VisitTagDecl(TT->getDecl());
713       return;
714     }
715     if (const ObjCInterfaceType *OIT = T->getAs<ObjCInterfaceType>()) {
716       Out << '$';
717       VisitObjCInterfaceDecl(OIT->getDecl());
718       return;
719     }
720     if (const ObjCObjectType *OIT = T->getAs<ObjCObjectType>()) {
721       Out << 'Q';
722       VisitType(OIT->getBaseType());
723       for (auto *Prot : OIT->getProtocols())
724         VisitObjCProtocolDecl(Prot);
725       return;
726     }
727     if (const TemplateTypeParmType *TTP = T->getAs<TemplateTypeParmType>()) {
728       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
729       return;
730     }
731     if (const TemplateSpecializationType *Spec
732                                     = T->getAs<TemplateSpecializationType>()) {
733       Out << '>';
734       VisitTemplateName(Spec->getTemplateName());
735       Out << Spec->getNumArgs();
736       for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
737         VisitTemplateArgument(Spec->getArg(I));
738       return;
739     }
740     if (const DependentNameType *DNT = T->getAs<DependentNameType>()) {
741       Out << '^';
742       // FIXME: Encode the qualifier, don't just print it.
743       PrintingPolicy PO(Ctx.getLangOpts());
744       PO.SuppressTagKeyword = true;
745       PO.SuppressUnwrittenScope = true;
746       PO.ConstantArraySizeAsWritten = false;
747       PO.AnonymousTagLocations = false;
748       DNT->getQualifier()->print(Out, PO);
749       Out << ':' << DNT->getIdentifier()->getName();
750       return;
751     }
752     if (const InjectedClassNameType *InjT = T->getAs<InjectedClassNameType>()) {
753       T = InjT->getInjectedSpecializationType();
754       continue;
755     }
756 
757     // Unhandled type.
758     Out << ' ';
759     break;
760   } while (true);
761 }
762 
763 void USRGenerator::VisitTemplateParameterList(
764                                          const TemplateParameterList *Params) {
765   if (!Params)
766     return;
767   Out << '>' << Params->size();
768   for (TemplateParameterList::const_iterator P = Params->begin(),
769                                           PEnd = Params->end();
770        P != PEnd; ++P) {
771     Out << '#';
772     if (isa<TemplateTypeParmDecl>(*P)) {
773       if (cast<TemplateTypeParmDecl>(*P)->isParameterPack())
774         Out<< 'p';
775       Out << 'T';
776       continue;
777     }
778 
779     if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
780       if (NTTP->isParameterPack())
781         Out << 'p';
782       Out << 'N';
783       VisitType(NTTP->getType());
784       continue;
785     }
786 
787     TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
788     if (TTP->isParameterPack())
789       Out << 'p';
790     Out << 't';
791     VisitTemplateParameterList(TTP->getTemplateParameters());
792   }
793 }
794 
795 void USRGenerator::VisitTemplateName(TemplateName Name) {
796   if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
797     if (TemplateTemplateParmDecl *TTP
798                               = dyn_cast<TemplateTemplateParmDecl>(Template)) {
799       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
800       return;
801     }
802 
803     Visit(Template);
804     return;
805   }
806 
807   // FIXME: Visit dependent template names.
808 }
809 
810 void USRGenerator::VisitTemplateArgument(const TemplateArgument &Arg) {
811   switch (Arg.getKind()) {
812   case TemplateArgument::Null:
813     break;
814 
815   case TemplateArgument::Declaration:
816     Visit(Arg.getAsDecl());
817     break;
818 
819   case TemplateArgument::NullPtr:
820     break;
821 
822   case TemplateArgument::TemplateExpansion:
823     Out << 'P'; // pack expansion of...
824     // Fall through
825   case TemplateArgument::Template:
826     VisitTemplateName(Arg.getAsTemplateOrTemplatePattern());
827     break;
828 
829   case TemplateArgument::Expression:
830     // FIXME: Visit expressions.
831     break;
832 
833   case TemplateArgument::Pack:
834     Out << 'p' << Arg.pack_size();
835     for (const auto &P : Arg.pack_elements())
836       VisitTemplateArgument(P);
837     break;
838 
839   case TemplateArgument::Type:
840     VisitType(Arg.getAsType());
841     break;
842 
843   case TemplateArgument::Integral:
844     Out << 'V';
845     VisitType(Arg.getIntegralType());
846     Out << Arg.getAsIntegral();
847     break;
848   }
849 }
850 
851 //===----------------------------------------------------------------------===//
852 // USR generation functions.
853 //===----------------------------------------------------------------------===//
854 
855 void clang::index::generateUSRForObjCClass(StringRef Cls, raw_ostream &OS) {
856   OS << "objc(cs)" << Cls;
857 }
858 
859 void clang::index::generateUSRForObjCCategory(StringRef Cls, StringRef Cat,
860                                               raw_ostream &OS) {
861   OS << "objc(cy)" << Cls << '@' << Cat;
862 }
863 
864 void clang::index::generateUSRForObjCIvar(StringRef Ivar, raw_ostream &OS) {
865   OS << '@' << Ivar;
866 }
867 
868 void clang::index::generateUSRForObjCMethod(StringRef Sel,
869                                             bool IsInstanceMethod,
870                                             raw_ostream &OS) {
871   OS << (IsInstanceMethod ? "(im)" : "(cm)") << Sel;
872 }
873 
874 void clang::index::generateUSRForObjCProperty(StringRef Prop, raw_ostream &OS) {
875   OS << "(py)" << Prop;
876 }
877 
878 void clang::index::generateUSRForObjCProtocol(StringRef Prot, raw_ostream &OS) {
879   OS << "objc(pl)" << Prot;
880 }
881 
882 bool clang::index::generateUSRForDecl(const Decl *D,
883                                       SmallVectorImpl<char> &Buf) {
884   // Don't generate USRs for things with invalid locations.
885   if (!D || D->getLocStart().isInvalid())
886     return true;
887 
888   USRGenerator UG(&D->getASTContext(), Buf);
889   UG.Visit(D);
890   return UG.ignoreResults();
891 }
892 
893 bool clang::index::generateUSRForMacro(const MacroDefinitionRecord *MD,
894                                        const SourceManager &SM,
895                                        SmallVectorImpl<char> &Buf) {
896   // Don't generate USRs for things with invalid locations.
897   if (!MD || MD->getLocation().isInvalid())
898     return true;
899 
900   llvm::raw_svector_ostream Out(Buf);
901 
902   // Assume that system headers are sane.  Don't put source location
903   // information into the USR if the macro comes from a system header.
904   SourceLocation Loc = MD->getLocation();
905   bool ShouldGenerateLocation = !SM.isInSystemHeader(Loc);
906 
907   Out << getUSRSpacePrefix();
908   if (ShouldGenerateLocation)
909     printLoc(Out, Loc, SM, /*IncludeOffset=*/true);
910   Out << "@macro@";
911   Out << MD->getName()->getName();
912   return false;
913 }
914