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