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