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