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/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 /// \returns true on error.
printLoc(llvm::raw_ostream & OS,SourceLocation Loc,const SourceManager & SM,bool IncludeOffset)26 static bool printLoc(llvm::raw_ostream &OS, SourceLocation Loc,
27                      const SourceManager &SM, bool IncludeOffset) {
28   if (Loc.isInvalid()) {
29     return true;
30   }
31   Loc = SM.getExpansionLoc(Loc);
32   const std::pair<FileID, unsigned> &Decomposed = SM.getDecomposedLoc(Loc);
33   const FileEntry *FE = SM.getFileEntryForID(Decomposed.first);
34   if (FE) {
35     OS << llvm::sys::path::filename(FE->getName());
36   } else {
37     // This case really isn't interesting.
38     return true;
39   }
40   if (IncludeOffset) {
41     // Use the offest into the FileID to represent the location.  Using
42     // a line/column can cause us to look back at the original source file,
43     // which is expensive.
44     OS << '@' << Decomposed.second;
45   }
46   return false;
47 }
48 
GetExternalSourceContainer(const NamedDecl * D)49 static StringRef GetExternalSourceContainer(const NamedDecl *D) {
50   if (!D)
51     return StringRef();
52   if (auto *attr = D->getExternalSourceSymbolAttr()) {
53     return attr->getDefinedIn();
54   }
55   return StringRef();
56 }
57 
58 namespace {
59 class USRGenerator : public ConstDeclVisitor<USRGenerator> {
60   SmallVectorImpl<char> &Buf;
61   llvm::raw_svector_ostream Out;
62   bool IgnoreResults;
63   ASTContext *Context;
64   bool generatedLoc;
65 
66   llvm::DenseMap<const Type *, unsigned> TypeSubstitutions;
67 
68 public:
USRGenerator(ASTContext * Ctx,SmallVectorImpl<char> & Buf)69   explicit USRGenerator(ASTContext *Ctx, SmallVectorImpl<char> &Buf)
70   : Buf(Buf),
71     Out(Buf),
72     IgnoreResults(false),
73     Context(Ctx),
74     generatedLoc(false)
75   {
76     // Add the USR space prefix.
77     Out << getUSRSpacePrefix();
78   }
79 
ignoreResults() const80   bool ignoreResults() const { return IgnoreResults; }
81 
82   // Visitation methods from generating USRs from AST elements.
83   void VisitDeclContext(const DeclContext *D);
84   void VisitFieldDecl(const FieldDecl *D);
85   void VisitFunctionDecl(const FunctionDecl *D);
86   void VisitNamedDecl(const NamedDecl *D);
87   void VisitNamespaceDecl(const NamespaceDecl *D);
88   void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D);
89   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D);
90   void VisitClassTemplateDecl(const ClassTemplateDecl *D);
91   void VisitObjCContainerDecl(const ObjCContainerDecl *CD,
92                               const ObjCCategoryDecl *CatD = nullptr);
93   void VisitObjCMethodDecl(const ObjCMethodDecl *MD);
94   void VisitObjCPropertyDecl(const ObjCPropertyDecl *D);
95   void VisitObjCPropertyImplDecl(const ObjCPropertyImplDecl *D);
96   void VisitTagDecl(const TagDecl *D);
97   void VisitTypedefDecl(const TypedefDecl *D);
98   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D);
99   void VisitVarDecl(const VarDecl *D);
100   void VisitBindingDecl(const BindingDecl *D);
101   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D);
102   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D);
103   void VisitUnresolvedUsingValueDecl(const UnresolvedUsingValueDecl *D);
104   void VisitUnresolvedUsingTypenameDecl(const UnresolvedUsingTypenameDecl *D);
105 
VisitLinkageSpecDecl(const LinkageSpecDecl * D)106   void VisitLinkageSpecDecl(const LinkageSpecDecl *D) {
107     IgnoreResults = true; // No USRs for linkage specs themselves.
108   }
109 
VisitUsingDirectiveDecl(const UsingDirectiveDecl * D)110   void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) {
111     IgnoreResults = true;
112   }
113 
VisitUsingDecl(const UsingDecl * D)114   void VisitUsingDecl(const UsingDecl *D) {
115     IgnoreResults = true;
116   }
117 
118   bool ShouldGenerateLocation(const NamedDecl *D);
119 
isLocal(const NamedDecl * D)120   bool isLocal(const NamedDecl *D) {
121     return D->getParentFunctionOrMethod() != nullptr;
122   }
123 
124   void GenExtSymbolContainer(const NamedDecl *D);
125 
126   /// Generate the string component containing the location of the
127   ///  declaration.
128   bool GenLoc(const Decl *D, bool IncludeOffset);
129 
130   /// String generation methods used both by the visitation methods
131   /// and from other clients that want to directly generate USRs.  These
132   /// methods do not construct complete USRs (which incorporate the parents
133   /// of an AST element), but only the fragments concerning the AST element
134   /// itself.
135 
136   /// Generate a USR for an Objective-C class.
GenObjCClass(StringRef cls,StringRef ExtSymDefinedIn,StringRef CategoryContextExtSymbolDefinedIn)137   void GenObjCClass(StringRef cls, StringRef ExtSymDefinedIn,
138                     StringRef CategoryContextExtSymbolDefinedIn) {
139     generateUSRForObjCClass(cls, Out, ExtSymDefinedIn,
140                             CategoryContextExtSymbolDefinedIn);
141   }
142 
143   /// Generate a USR for an Objective-C class category.
GenObjCCategory(StringRef cls,StringRef cat,StringRef clsExt,StringRef catExt)144   void GenObjCCategory(StringRef cls, StringRef cat,
145                        StringRef clsExt, StringRef catExt) {
146     generateUSRForObjCCategory(cls, cat, Out, clsExt, catExt);
147   }
148 
149   /// Generate a USR fragment for an Objective-C property.
GenObjCProperty(StringRef prop,bool isClassProp)150   void GenObjCProperty(StringRef prop, bool isClassProp) {
151     generateUSRForObjCProperty(prop, isClassProp, Out);
152   }
153 
154   /// Generate a USR for an Objective-C protocol.
GenObjCProtocol(StringRef prot,StringRef ext)155   void GenObjCProtocol(StringRef prot, StringRef ext) {
156     generateUSRForObjCProtocol(prot, Out, ext);
157   }
158 
159   void VisitType(QualType T);
160   void VisitTemplateParameterList(const TemplateParameterList *Params);
161   void VisitTemplateName(TemplateName Name);
162   void VisitTemplateArgument(const TemplateArgument &Arg);
163 
164   /// Emit a Decl's name using NamedDecl::printName() and return true if
165   ///  the decl had no name.
166   bool EmitDeclName(const NamedDecl *D);
167 };
168 } // end anonymous namespace
169 
170 //===----------------------------------------------------------------------===//
171 // Generating USRs from ASTS.
172 //===----------------------------------------------------------------------===//
173 
EmitDeclName(const NamedDecl * D)174 bool USRGenerator::EmitDeclName(const NamedDecl *D) {
175   const unsigned startSize = Buf.size();
176   D->printName(Out);
177   const unsigned endSize = Buf.size();
178   return startSize == endSize;
179 }
180 
ShouldGenerateLocation(const NamedDecl * D)181 bool USRGenerator::ShouldGenerateLocation(const NamedDecl *D) {
182   if (D->isExternallyVisible())
183     return false;
184   if (D->getParentFunctionOrMethod())
185     return true;
186   SourceLocation Loc = D->getLocation();
187   if (Loc.isInvalid())
188     return false;
189   const SourceManager &SM = Context->getSourceManager();
190   return !SM.isInSystemHeader(Loc);
191 }
192 
VisitDeclContext(const DeclContext * DC)193 void USRGenerator::VisitDeclContext(const DeclContext *DC) {
194   if (const NamedDecl *D = dyn_cast<NamedDecl>(DC))
195     Visit(D);
196   else if (isa<LinkageSpecDecl>(DC)) // Linkage specs are transparent in USRs.
197     VisitDeclContext(DC->getParent());
198 }
199 
VisitFieldDecl(const FieldDecl * D)200 void USRGenerator::VisitFieldDecl(const FieldDecl *D) {
201   // The USR for an ivar declared in a class extension is based on the
202   // ObjCInterfaceDecl, not the ObjCCategoryDecl.
203   if (const ObjCInterfaceDecl *ID = Context->getObjContainingInterface(D))
204     Visit(ID);
205   else
206     VisitDeclContext(D->getDeclContext());
207   Out << (isa<ObjCIvarDecl>(D) ? "@" : "@FI@");
208   if (EmitDeclName(D)) {
209     // Bit fields can be anonymous.
210     IgnoreResults = true;
211     return;
212   }
213 }
214 
VisitFunctionDecl(const FunctionDecl * D)215 void USRGenerator::VisitFunctionDecl(const FunctionDecl *D) {
216   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
217     return;
218 
219   const unsigned StartSize = Buf.size();
220   VisitDeclContext(D->getDeclContext());
221   if (Buf.size() == StartSize)
222     GenExtSymbolContainer(D);
223 
224   bool IsTemplate = false;
225   if (FunctionTemplateDecl *FunTmpl = D->getDescribedFunctionTemplate()) {
226     IsTemplate = true;
227     Out << "@FT@";
228     VisitTemplateParameterList(FunTmpl->getTemplateParameters());
229   } else
230     Out << "@F@";
231 
232   PrintingPolicy Policy(Context->getLangOpts());
233   // Forward references can have different template argument names. Suppress the
234   // template argument names in constructors to make their USR more stable.
235   Policy.SuppressTemplateArgsInCXXConstructors = true;
236   D->getDeclName().print(Out, Policy);
237 
238   ASTContext &Ctx = *Context;
239   if ((!Ctx.getLangOpts().CPlusPlus || D->isExternC()) &&
240       !D->hasAttr<OverloadableAttr>())
241     return;
242 
243   if (const TemplateArgumentList *
244         SpecArgs = D->getTemplateSpecializationArgs()) {
245     Out << '<';
246     for (unsigned I = 0, N = SpecArgs->size(); I != N; ++I) {
247       Out << '#';
248       VisitTemplateArgument(SpecArgs->get(I));
249     }
250     Out << '>';
251   }
252 
253   // Mangle in type information for the arguments.
254   for (auto PD : D->parameters()) {
255     Out << '#';
256     VisitType(PD->getType());
257   }
258   if (D->isVariadic())
259     Out << '.';
260   if (IsTemplate) {
261     // Function templates can be overloaded by return type, for example:
262     // \code
263     //   template <class T> typename T::A foo() {}
264     //   template <class T> typename T::B foo() {}
265     // \endcode
266     Out << '#';
267     VisitType(D->getReturnType());
268   }
269   Out << '#';
270   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
271     if (MD->isStatic())
272       Out << 'S';
273     // FIXME: OpenCL: Need to consider address spaces
274     if (unsigned quals = MD->getTypeQualifiers().getCVRUQualifiers())
275       Out << (char)('0' + quals);
276     switch (MD->getRefQualifier()) {
277     case RQ_None: break;
278     case RQ_LValue: Out << '&'; break;
279     case RQ_RValue: Out << "&&"; break;
280     }
281   }
282 }
283 
VisitNamedDecl(const NamedDecl * D)284 void USRGenerator::VisitNamedDecl(const NamedDecl *D) {
285   VisitDeclContext(D->getDeclContext());
286   Out << "@";
287 
288   if (EmitDeclName(D)) {
289     // The string can be empty if the declaration has no name; e.g., it is
290     // the ParmDecl with no name for declaration of a function pointer type,
291     // e.g.: void  (*f)(void *);
292     // In this case, don't generate a USR.
293     IgnoreResults = true;
294   }
295 }
296 
VisitVarDecl(const VarDecl * D)297 void USRGenerator::VisitVarDecl(const VarDecl *D) {
298   // VarDecls can be declared 'extern' within a function or method body,
299   // but their enclosing DeclContext is the function, not the TU.  We need
300   // to check the storage class to correctly generate the USR.
301   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
302     return;
303 
304   VisitDeclContext(D->getDeclContext());
305 
306   if (VarTemplateDecl *VarTmpl = D->getDescribedVarTemplate()) {
307     Out << "@VT";
308     VisitTemplateParameterList(VarTmpl->getTemplateParameters());
309   } else if (const VarTemplatePartialSpecializationDecl *PartialSpec
310              = dyn_cast<VarTemplatePartialSpecializationDecl>(D)) {
311     Out << "@VP";
312     VisitTemplateParameterList(PartialSpec->getTemplateParameters());
313   }
314 
315   // Variables always have simple names.
316   StringRef s = D->getName();
317 
318   // The string can be empty if the declaration has no name; e.g., it is
319   // the ParmDecl with no name for declaration of a function pointer type, e.g.:
320   //    void  (*f)(void *);
321   // In this case, don't generate a USR.
322   if (s.empty())
323     IgnoreResults = true;
324   else
325     Out << '@' << s;
326 
327   // For a template specialization, mangle the template arguments.
328   if (const VarTemplateSpecializationDecl *Spec
329                               = dyn_cast<VarTemplateSpecializationDecl>(D)) {
330     const TemplateArgumentList &Args = Spec->getTemplateArgs();
331     Out << '>';
332     for (unsigned I = 0, N = Args.size(); I != N; ++I) {
333       Out << '#';
334       VisitTemplateArgument(Args.get(I));
335     }
336   }
337 }
338 
VisitBindingDecl(const BindingDecl * D)339 void USRGenerator::VisitBindingDecl(const BindingDecl *D) {
340   if (isLocal(D) && GenLoc(D, /*IncludeOffset=*/true))
341     return;
342   VisitNamedDecl(D);
343 }
344 
VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl * D)345 void USRGenerator::VisitNonTypeTemplateParmDecl(
346                                         const NonTypeTemplateParmDecl *D) {
347   GenLoc(D, /*IncludeOffset=*/true);
348 }
349 
VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl * D)350 void USRGenerator::VisitTemplateTemplateParmDecl(
351                                         const TemplateTemplateParmDecl *D) {
352   GenLoc(D, /*IncludeOffset=*/true);
353 }
354 
VisitNamespaceDecl(const NamespaceDecl * D)355 void USRGenerator::VisitNamespaceDecl(const NamespaceDecl *D) {
356   if (D->isAnonymousNamespace()) {
357     Out << "@aN";
358     return;
359   }
360 
361   VisitDeclContext(D->getDeclContext());
362   if (!IgnoreResults)
363     Out << "@N@" << D->getName();
364 }
365 
VisitFunctionTemplateDecl(const FunctionTemplateDecl * D)366 void USRGenerator::VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
367   VisitFunctionDecl(D->getTemplatedDecl());
368 }
369 
VisitClassTemplateDecl(const ClassTemplateDecl * D)370 void USRGenerator::VisitClassTemplateDecl(const ClassTemplateDecl *D) {
371   VisitTagDecl(D->getTemplatedDecl());
372 }
373 
VisitNamespaceAliasDecl(const NamespaceAliasDecl * D)374 void USRGenerator::VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) {
375   VisitDeclContext(D->getDeclContext());
376   if (!IgnoreResults)
377     Out << "@NA@" << D->getName();
378 }
379 
VisitObjCMethodDecl(const ObjCMethodDecl * D)380 void USRGenerator::VisitObjCMethodDecl(const ObjCMethodDecl *D) {
381   const DeclContext *container = D->getDeclContext();
382   if (const ObjCProtocolDecl *pd = dyn_cast<ObjCProtocolDecl>(container)) {
383     Visit(pd);
384   }
385   else {
386     // The USR for a method declared in a class extension or category is based on
387     // the ObjCInterfaceDecl, not the ObjCCategoryDecl.
388     const ObjCInterfaceDecl *ID = D->getClassInterface();
389     if (!ID) {
390       IgnoreResults = true;
391       return;
392     }
393     auto getCategoryContext = [](const ObjCMethodDecl *D) ->
394                                     const ObjCCategoryDecl * {
395       if (auto *CD = dyn_cast<ObjCCategoryDecl>(D->getDeclContext()))
396         return CD;
397       if (auto *ICD = dyn_cast<ObjCCategoryImplDecl>(D->getDeclContext()))
398         return ICD->getCategoryDecl();
399       return nullptr;
400     };
401     auto *CD = getCategoryContext(D);
402     VisitObjCContainerDecl(ID, CD);
403   }
404   // Ideally we would use 'GenObjCMethod', but this is such a hot path
405   // for Objective-C code that we don't want to use
406   // DeclarationName::getAsString().
407   Out << (D->isInstanceMethod() ? "(im)" : "(cm)")
408       << DeclarationName(D->getSelector());
409 }
410 
VisitObjCContainerDecl(const ObjCContainerDecl * D,const ObjCCategoryDecl * CatD)411 void USRGenerator::VisitObjCContainerDecl(const ObjCContainerDecl *D,
412                                           const ObjCCategoryDecl *CatD) {
413   switch (D->getKind()) {
414     default:
415       llvm_unreachable("Invalid ObjC container.");
416     case Decl::ObjCInterface:
417     case Decl::ObjCImplementation:
418       GenObjCClass(D->getName(), GetExternalSourceContainer(D),
419                    GetExternalSourceContainer(CatD));
420       break;
421     case Decl::ObjCCategory: {
422       const ObjCCategoryDecl *CD = cast<ObjCCategoryDecl>(D);
423       const ObjCInterfaceDecl *ID = CD->getClassInterface();
424       if (!ID) {
425         // Handle invalid code where the @interface might not
426         // have been specified.
427         // FIXME: We should be able to generate this USR even if the
428         // @interface isn't available.
429         IgnoreResults = true;
430         return;
431       }
432       // Specially handle class extensions, which are anonymous categories.
433       // We want to mangle in the location to uniquely distinguish them.
434       if (CD->IsClassExtension()) {
435         Out << "objc(ext)" << ID->getName() << '@';
436         GenLoc(CD, /*IncludeOffset=*/true);
437       }
438       else
439         GenObjCCategory(ID->getName(), CD->getName(),
440                         GetExternalSourceContainer(ID),
441                         GetExternalSourceContainer(CD));
442 
443       break;
444     }
445     case Decl::ObjCCategoryImpl: {
446       const ObjCCategoryImplDecl *CD = cast<ObjCCategoryImplDecl>(D);
447       const ObjCInterfaceDecl *ID = CD->getClassInterface();
448       if (!ID) {
449         // Handle invalid code where the @interface might not
450         // have been specified.
451         // FIXME: We should be able to generate this USR even if the
452         // @interface isn't available.
453         IgnoreResults = true;
454         return;
455       }
456       GenObjCCategory(ID->getName(), CD->getName(),
457                       GetExternalSourceContainer(ID),
458                       GetExternalSourceContainer(CD));
459       break;
460     }
461     case Decl::ObjCProtocol: {
462       const ObjCProtocolDecl *PD = cast<ObjCProtocolDecl>(D);
463       GenObjCProtocol(PD->getName(), GetExternalSourceContainer(PD));
464       break;
465     }
466   }
467 }
468 
VisitObjCPropertyDecl(const ObjCPropertyDecl * D)469 void USRGenerator::VisitObjCPropertyDecl(const ObjCPropertyDecl *D) {
470   // The USR for a property declared in a class extension or category is based
471   // on the ObjCInterfaceDecl, not the ObjCCategoryDecl.
472   if (const ObjCInterfaceDecl *ID = Context->getObjContainingInterface(D))
473     Visit(ID);
474   else
475     Visit(cast<Decl>(D->getDeclContext()));
476   GenObjCProperty(D->getName(), D->isClassProperty());
477 }
478 
VisitObjCPropertyImplDecl(const ObjCPropertyImplDecl * D)479 void USRGenerator::VisitObjCPropertyImplDecl(const ObjCPropertyImplDecl *D) {
480   if (ObjCPropertyDecl *PD = D->getPropertyDecl()) {
481     VisitObjCPropertyDecl(PD);
482     return;
483   }
484 
485   IgnoreResults = true;
486 }
487 
VisitTagDecl(const TagDecl * D)488 void USRGenerator::VisitTagDecl(const TagDecl *D) {
489   // Add the location of the tag decl to handle resolution across
490   // translation units.
491   if (!isa<EnumDecl>(D) &&
492       ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
493     return;
494 
495   GenExtSymbolContainer(D);
496 
497   D = D->getCanonicalDecl();
498   VisitDeclContext(D->getDeclContext());
499 
500   bool AlreadyStarted = false;
501   if (const CXXRecordDecl *CXXRecord = dyn_cast<CXXRecordDecl>(D)) {
502     if (ClassTemplateDecl *ClassTmpl = CXXRecord->getDescribedClassTemplate()) {
503       AlreadyStarted = true;
504 
505       switch (D->getTagKind()) {
506       case TTK_Interface:
507       case TTK_Class:
508       case TTK_Struct: Out << "@ST"; break;
509       case TTK_Union:  Out << "@UT"; break;
510       case TTK_Enum: llvm_unreachable("enum template");
511       }
512       VisitTemplateParameterList(ClassTmpl->getTemplateParameters());
513     } else if (const ClassTemplatePartialSpecializationDecl *PartialSpec
514                 = dyn_cast<ClassTemplatePartialSpecializationDecl>(CXXRecord)) {
515       AlreadyStarted = true;
516 
517       switch (D->getTagKind()) {
518       case TTK_Interface:
519       case TTK_Class:
520       case TTK_Struct: Out << "@SP"; break;
521       case TTK_Union:  Out << "@UP"; break;
522       case TTK_Enum: llvm_unreachable("enum partial specialization");
523       }
524       VisitTemplateParameterList(PartialSpec->getTemplateParameters());
525     }
526   }
527 
528   if (!AlreadyStarted) {
529     switch (D->getTagKind()) {
530       case TTK_Interface:
531       case TTK_Class:
532       case TTK_Struct: Out << "@S"; break;
533       case TTK_Union:  Out << "@U"; break;
534       case TTK_Enum:   Out << "@E"; break;
535     }
536   }
537 
538   Out << '@';
539   assert(Buf.size() > 0);
540   const unsigned off = Buf.size() - 1;
541 
542   if (EmitDeclName(D)) {
543     if (const TypedefNameDecl *TD = D->getTypedefNameForAnonDecl()) {
544       Buf[off] = 'A';
545       Out << '@' << *TD;
546     }
547   else {
548     if (D->isEmbeddedInDeclarator() && !D->isFreeStanding()) {
549       printLoc(Out, D->getLocation(), Context->getSourceManager(), true);
550     } else {
551       Buf[off] = 'a';
552       if (auto *ED = dyn_cast<EnumDecl>(D)) {
553         // Distinguish USRs of anonymous enums by using their first enumerator.
554         auto enum_range = ED->enumerators();
555         if (enum_range.begin() != enum_range.end()) {
556           Out << '@' << **enum_range.begin();
557         }
558       }
559     }
560   }
561   }
562 
563   // For a class template specialization, mangle the template arguments.
564   if (const ClassTemplateSpecializationDecl *Spec
565                               = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
566     const TemplateArgumentList &Args = Spec->getTemplateArgs();
567     Out << '>';
568     for (unsigned I = 0, N = Args.size(); I != N; ++I) {
569       Out << '#';
570       VisitTemplateArgument(Args.get(I));
571     }
572   }
573 }
574 
VisitTypedefDecl(const TypedefDecl * D)575 void USRGenerator::VisitTypedefDecl(const TypedefDecl *D) {
576   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
577     return;
578   const DeclContext *DC = D->getDeclContext();
579   if (const NamedDecl *DCN = dyn_cast<NamedDecl>(DC))
580     Visit(DCN);
581   Out << "@T@";
582   Out << D->getName();
583 }
584 
VisitTemplateTypeParmDecl(const TemplateTypeParmDecl * D)585 void USRGenerator::VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
586   GenLoc(D, /*IncludeOffset=*/true);
587 }
588 
GenExtSymbolContainer(const NamedDecl * D)589 void USRGenerator::GenExtSymbolContainer(const NamedDecl *D) {
590   StringRef Container = GetExternalSourceContainer(D);
591   if (!Container.empty())
592     Out << "@M@" << Container;
593 }
594 
GenLoc(const Decl * D,bool IncludeOffset)595 bool USRGenerator::GenLoc(const Decl *D, bool IncludeOffset) {
596   if (generatedLoc)
597     return IgnoreResults;
598   generatedLoc = true;
599 
600   // Guard against null declarations in invalid code.
601   if (!D) {
602     IgnoreResults = true;
603     return true;
604   }
605 
606   // Use the location of canonical decl.
607   D = D->getCanonicalDecl();
608 
609   IgnoreResults =
610       IgnoreResults || printLoc(Out, D->getBeginLoc(),
611                                 Context->getSourceManager(), IncludeOffset);
612 
613   return IgnoreResults;
614 }
615 
printQualifier(llvm::raw_ostream & Out,ASTContext & Ctx,NestedNameSpecifier * NNS)616 static void printQualifier(llvm::raw_ostream &Out, ASTContext &Ctx, NestedNameSpecifier *NNS) {
617   // FIXME: Encode the qualifier, don't just print it.
618   PrintingPolicy PO(Ctx.getLangOpts());
619   PO.SuppressTagKeyword = true;
620   PO.SuppressUnwrittenScope = true;
621   PO.ConstantArraySizeAsWritten = false;
622   PO.AnonymousTagLocations = false;
623   NNS->print(Out, PO);
624 }
625 
VisitType(QualType T)626 void USRGenerator::VisitType(QualType T) {
627   // This method mangles in USR information for types.  It can possibly
628   // just reuse the naming-mangling logic used by codegen, although the
629   // requirements for USRs might not be the same.
630   ASTContext &Ctx = *Context;
631 
632   do {
633     T = Ctx.getCanonicalType(T);
634     Qualifiers Q = T.getQualifiers();
635     unsigned qVal = 0;
636     if (Q.hasConst())
637       qVal |= 0x1;
638     if (Q.hasVolatile())
639       qVal |= 0x2;
640     if (Q.hasRestrict())
641       qVal |= 0x4;
642     if(qVal)
643       Out << ((char) ('0' + qVal));
644 
645     // Mangle in ObjC GC qualifiers?
646 
647     if (const PackExpansionType *Expansion = T->getAs<PackExpansionType>()) {
648       Out << 'P';
649       T = Expansion->getPattern();
650     }
651 
652     if (const BuiltinType *BT = T->getAs<BuiltinType>()) {
653       unsigned char c = '\0';
654       switch (BT->getKind()) {
655         case BuiltinType::Void:
656           c = 'v'; break;
657         case BuiltinType::Bool:
658           c = 'b'; break;
659         case BuiltinType::UChar:
660           c = 'c'; break;
661         case BuiltinType::Char8:
662           c = 'u'; break; // FIXME: Check this doesn't collide
663         case BuiltinType::Char16:
664           c = 'q'; break;
665         case BuiltinType::Char32:
666           c = 'w'; break;
667         case BuiltinType::UShort:
668           c = 's'; break;
669         case BuiltinType::UInt:
670           c = 'i'; break;
671         case BuiltinType::ULong:
672           c = 'l'; break;
673         case BuiltinType::ULongLong:
674           c = 'k'; break;
675         case BuiltinType::UInt128:
676           c = 'j'; break;
677         case BuiltinType::Char_U:
678         case BuiltinType::Char_S:
679           c = 'C'; break;
680         case BuiltinType::SChar:
681           c = 'r'; break;
682         case BuiltinType::WChar_S:
683         case BuiltinType::WChar_U:
684           c = 'W'; break;
685         case BuiltinType::Short:
686           c = 'S'; break;
687         case BuiltinType::Int:
688           c = 'I'; break;
689         case BuiltinType::Long:
690           c = 'L'; break;
691         case BuiltinType::LongLong:
692           c = 'K'; break;
693         case BuiltinType::Int128:
694           c = 'J'; break;
695         case BuiltinType::Float16:
696         case BuiltinType::Half:
697           c = 'h'; break;
698         case BuiltinType::Float:
699           c = 'f'; break;
700         case BuiltinType::Double:
701           c = 'd'; break;
702         case BuiltinType::LongDouble:
703           c = 'D'; break;
704         case BuiltinType::Float128:
705           c = 'Q'; break;
706         case BuiltinType::NullPtr:
707           c = 'n'; break;
708 #define BUILTIN_TYPE(Id, SingletonId)
709 #define PLACEHOLDER_TYPE(Id, SingletonId) case BuiltinType::Id:
710 #include "clang/AST/BuiltinTypes.def"
711         case BuiltinType::Dependent:
712 #define IMAGE_TYPE(ImgType, Id, SingletonId, Access, Suffix) \
713         case BuiltinType::Id:
714 #include "clang/Basic/OpenCLImageTypes.def"
715 #define EXT_OPAQUE_TYPE(ExtType, Id, Ext) \
716         case BuiltinType::Id:
717 #include "clang/Basic/OpenCLExtensionTypes.def"
718         case BuiltinType::OCLEvent:
719         case BuiltinType::OCLClkEvent:
720         case BuiltinType::OCLQueue:
721         case BuiltinType::OCLReserveID:
722         case BuiltinType::OCLSampler:
723         case BuiltinType::ShortAccum:
724         case BuiltinType::Accum:
725         case BuiltinType::LongAccum:
726         case BuiltinType::UShortAccum:
727         case BuiltinType::UAccum:
728         case BuiltinType::ULongAccum:
729         case BuiltinType::ShortFract:
730         case BuiltinType::Fract:
731         case BuiltinType::LongFract:
732         case BuiltinType::UShortFract:
733         case BuiltinType::UFract:
734         case BuiltinType::ULongFract:
735         case BuiltinType::SatShortAccum:
736         case BuiltinType::SatAccum:
737         case BuiltinType::SatLongAccum:
738         case BuiltinType::SatUShortAccum:
739         case BuiltinType::SatUAccum:
740         case BuiltinType::SatULongAccum:
741         case BuiltinType::SatShortFract:
742         case BuiltinType::SatFract:
743         case BuiltinType::SatLongFract:
744         case BuiltinType::SatUShortFract:
745         case BuiltinType::SatUFract:
746         case BuiltinType::SatULongFract:
747           IgnoreResults = true;
748           return;
749         case BuiltinType::ObjCId:
750           c = 'o'; break;
751         case BuiltinType::ObjCClass:
752           c = 'O'; break;
753         case BuiltinType::ObjCSel:
754           c = 'e'; break;
755       }
756       Out << c;
757       return;
758     }
759 
760     // If we have already seen this (non-built-in) type, use a substitution
761     // encoding.
762     llvm::DenseMap<const Type *, unsigned>::iterator Substitution
763       = TypeSubstitutions.find(T.getTypePtr());
764     if (Substitution != TypeSubstitutions.end()) {
765       Out << 'S' << Substitution->second << '_';
766       return;
767     } else {
768       // Record this as a substitution.
769       unsigned Number = TypeSubstitutions.size();
770       TypeSubstitutions[T.getTypePtr()] = Number;
771     }
772 
773     if (const PointerType *PT = T->getAs<PointerType>()) {
774       Out << '*';
775       T = PT->getPointeeType();
776       continue;
777     }
778     if (const ObjCObjectPointerType *OPT = T->getAs<ObjCObjectPointerType>()) {
779       Out << '*';
780       T = OPT->getPointeeType();
781       continue;
782     }
783     if (const RValueReferenceType *RT = T->getAs<RValueReferenceType>()) {
784       Out << "&&";
785       T = RT->getPointeeType();
786       continue;
787     }
788     if (const ReferenceType *RT = T->getAs<ReferenceType>()) {
789       Out << '&';
790       T = RT->getPointeeType();
791       continue;
792     }
793     if (const FunctionProtoType *FT = T->getAs<FunctionProtoType>()) {
794       Out << 'F';
795       VisitType(FT->getReturnType());
796       Out << '(';
797       for (const auto &I : FT->param_types()) {
798         Out << '#';
799         VisitType(I);
800       }
801       Out << ')';
802       if (FT->isVariadic())
803         Out << '.';
804       return;
805     }
806     if (const BlockPointerType *BT = T->getAs<BlockPointerType>()) {
807       Out << 'B';
808       T = BT->getPointeeType();
809       continue;
810     }
811     if (const ComplexType *CT = T->getAs<ComplexType>()) {
812       Out << '<';
813       T = CT->getElementType();
814       continue;
815     }
816     if (const TagType *TT = T->getAs<TagType>()) {
817       Out << '$';
818       VisitTagDecl(TT->getDecl());
819       return;
820     }
821     if (const ObjCInterfaceType *OIT = T->getAs<ObjCInterfaceType>()) {
822       Out << '$';
823       VisitObjCInterfaceDecl(OIT->getDecl());
824       return;
825     }
826     if (const ObjCObjectType *OIT = T->getAs<ObjCObjectType>()) {
827       Out << 'Q';
828       VisitType(OIT->getBaseType());
829       for (auto *Prot : OIT->getProtocols())
830         VisitObjCProtocolDecl(Prot);
831       return;
832     }
833     if (const TemplateTypeParmType *TTP = T->getAs<TemplateTypeParmType>()) {
834       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
835       return;
836     }
837     if (const TemplateSpecializationType *Spec
838                                     = T->getAs<TemplateSpecializationType>()) {
839       Out << '>';
840       VisitTemplateName(Spec->getTemplateName());
841       Out << Spec->getNumArgs();
842       for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
843         VisitTemplateArgument(Spec->getArg(I));
844       return;
845     }
846     if (const DependentNameType *DNT = T->getAs<DependentNameType>()) {
847       Out << '^';
848       printQualifier(Out, Ctx, DNT->getQualifier());
849       Out << ':' << DNT->getIdentifier()->getName();
850       return;
851     }
852     if (const InjectedClassNameType *InjT = T->getAs<InjectedClassNameType>()) {
853       T = InjT->getInjectedSpecializationType();
854       continue;
855     }
856     if (const auto *VT = T->getAs<VectorType>()) {
857       Out << (T->isExtVectorType() ? ']' : '[');
858       Out << VT->getNumElements();
859       T = VT->getElementType();
860       continue;
861     }
862     if (const auto *const AT = dyn_cast<ArrayType>(T)) {
863       Out << '{';
864       switch (AT->getSizeModifier()) {
865       case ArrayType::Static:
866         Out << 's';
867         break;
868       case ArrayType::Star:
869         Out << '*';
870         break;
871       case ArrayType::Normal:
872         Out << 'n';
873         break;
874       }
875       if (const auto *const CAT = dyn_cast<ConstantArrayType>(T))
876         Out << CAT->getSize();
877 
878       T = AT->getElementType();
879       continue;
880     }
881 
882     // Unhandled type.
883     Out << ' ';
884     break;
885   } while (true);
886 }
887 
VisitTemplateParameterList(const TemplateParameterList * Params)888 void USRGenerator::VisitTemplateParameterList(
889                                          const TemplateParameterList *Params) {
890   if (!Params)
891     return;
892   Out << '>' << Params->size();
893   for (TemplateParameterList::const_iterator P = Params->begin(),
894                                           PEnd = Params->end();
895        P != PEnd; ++P) {
896     Out << '#';
897     if (isa<TemplateTypeParmDecl>(*P)) {
898       if (cast<TemplateTypeParmDecl>(*P)->isParameterPack())
899         Out<< 'p';
900       Out << 'T';
901       continue;
902     }
903 
904     if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
905       if (NTTP->isParameterPack())
906         Out << 'p';
907       Out << 'N';
908       VisitType(NTTP->getType());
909       continue;
910     }
911 
912     TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
913     if (TTP->isParameterPack())
914       Out << 'p';
915     Out << 't';
916     VisitTemplateParameterList(TTP->getTemplateParameters());
917   }
918 }
919 
VisitTemplateName(TemplateName Name)920 void USRGenerator::VisitTemplateName(TemplateName Name) {
921   if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
922     if (TemplateTemplateParmDecl *TTP
923                               = dyn_cast<TemplateTemplateParmDecl>(Template)) {
924       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
925       return;
926     }
927 
928     Visit(Template);
929     return;
930   }
931 
932   // FIXME: Visit dependent template names.
933 }
934 
VisitTemplateArgument(const TemplateArgument & Arg)935 void USRGenerator::VisitTemplateArgument(const TemplateArgument &Arg) {
936   switch (Arg.getKind()) {
937   case TemplateArgument::Null:
938     break;
939 
940   case TemplateArgument::Declaration:
941     Visit(Arg.getAsDecl());
942     break;
943 
944   case TemplateArgument::NullPtr:
945     break;
946 
947   case TemplateArgument::TemplateExpansion:
948     Out << 'P'; // pack expansion of...
949     LLVM_FALLTHROUGH;
950   case TemplateArgument::Template:
951     VisitTemplateName(Arg.getAsTemplateOrTemplatePattern());
952     break;
953 
954   case TemplateArgument::Expression:
955     // FIXME: Visit expressions.
956     break;
957 
958   case TemplateArgument::Pack:
959     Out << 'p' << Arg.pack_size();
960     for (const auto &P : Arg.pack_elements())
961       VisitTemplateArgument(P);
962     break;
963 
964   case TemplateArgument::Type:
965     VisitType(Arg.getAsType());
966     break;
967 
968   case TemplateArgument::Integral:
969     Out << 'V';
970     VisitType(Arg.getIntegralType());
971     Out << Arg.getAsIntegral();
972     break;
973   }
974 }
975 
VisitUnresolvedUsingValueDecl(const UnresolvedUsingValueDecl * D)976 void USRGenerator::VisitUnresolvedUsingValueDecl(const UnresolvedUsingValueDecl *D) {
977   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
978     return;
979   VisitDeclContext(D->getDeclContext());
980   Out << "@UUV@";
981   printQualifier(Out, D->getASTContext(), D->getQualifier());
982   EmitDeclName(D);
983 }
984 
VisitUnresolvedUsingTypenameDecl(const UnresolvedUsingTypenameDecl * D)985 void USRGenerator::VisitUnresolvedUsingTypenameDecl(const UnresolvedUsingTypenameDecl *D) {
986   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
987     return;
988   VisitDeclContext(D->getDeclContext());
989   Out << "@UUT@";
990   printQualifier(Out, D->getASTContext(), D->getQualifier());
991   Out << D->getName(); // Simple name.
992 }
993 
994 
995 
996 //===----------------------------------------------------------------------===//
997 // USR generation functions.
998 //===----------------------------------------------------------------------===//
999 
combineClassAndCategoryExtContainers(StringRef ClsSymDefinedIn,StringRef CatSymDefinedIn,raw_ostream & OS)1000 static void combineClassAndCategoryExtContainers(StringRef ClsSymDefinedIn,
1001                                                  StringRef CatSymDefinedIn,
1002                                                  raw_ostream &OS) {
1003   if (ClsSymDefinedIn.empty() && CatSymDefinedIn.empty())
1004     return;
1005   if (CatSymDefinedIn.empty()) {
1006     OS << "@M@" << ClsSymDefinedIn << '@';
1007     return;
1008   }
1009   OS << "@CM@" << CatSymDefinedIn << '@';
1010   if (ClsSymDefinedIn != CatSymDefinedIn) {
1011     OS << ClsSymDefinedIn << '@';
1012   }
1013 }
1014 
generateUSRForObjCClass(StringRef Cls,raw_ostream & OS,StringRef ExtSymDefinedIn,StringRef CategoryContextExtSymbolDefinedIn)1015 void clang::index::generateUSRForObjCClass(StringRef Cls, raw_ostream &OS,
1016                                            StringRef ExtSymDefinedIn,
1017                                   StringRef CategoryContextExtSymbolDefinedIn) {
1018   combineClassAndCategoryExtContainers(ExtSymDefinedIn,
1019                                        CategoryContextExtSymbolDefinedIn, OS);
1020   OS << "objc(cs)" << Cls;
1021 }
1022 
generateUSRForObjCCategory(StringRef Cls,StringRef Cat,raw_ostream & OS,StringRef ClsSymDefinedIn,StringRef CatSymDefinedIn)1023 void clang::index::generateUSRForObjCCategory(StringRef Cls, StringRef Cat,
1024                                               raw_ostream &OS,
1025                                               StringRef ClsSymDefinedIn,
1026                                               StringRef CatSymDefinedIn) {
1027   combineClassAndCategoryExtContainers(ClsSymDefinedIn, CatSymDefinedIn, OS);
1028   OS << "objc(cy)" << Cls << '@' << Cat;
1029 }
1030 
generateUSRForObjCIvar(StringRef Ivar,raw_ostream & OS)1031 void clang::index::generateUSRForObjCIvar(StringRef Ivar, raw_ostream &OS) {
1032   OS << '@' << Ivar;
1033 }
1034 
generateUSRForObjCMethod(StringRef Sel,bool IsInstanceMethod,raw_ostream & OS)1035 void clang::index::generateUSRForObjCMethod(StringRef Sel,
1036                                             bool IsInstanceMethod,
1037                                             raw_ostream &OS) {
1038   OS << (IsInstanceMethod ? "(im)" : "(cm)") << Sel;
1039 }
1040 
generateUSRForObjCProperty(StringRef Prop,bool isClassProp,raw_ostream & OS)1041 void clang::index::generateUSRForObjCProperty(StringRef Prop, bool isClassProp,
1042                                               raw_ostream &OS) {
1043   OS << (isClassProp ? "(cpy)" : "(py)") << Prop;
1044 }
1045 
generateUSRForObjCProtocol(StringRef Prot,raw_ostream & OS,StringRef ExtSymDefinedIn)1046 void clang::index::generateUSRForObjCProtocol(StringRef Prot, raw_ostream &OS,
1047                                               StringRef ExtSymDefinedIn) {
1048   if (!ExtSymDefinedIn.empty())
1049     OS << "@M@" << ExtSymDefinedIn << '@';
1050   OS << "objc(pl)" << Prot;
1051 }
1052 
generateUSRForGlobalEnum(StringRef EnumName,raw_ostream & OS,StringRef ExtSymDefinedIn)1053 void clang::index::generateUSRForGlobalEnum(StringRef EnumName, raw_ostream &OS,
1054                                             StringRef ExtSymDefinedIn) {
1055   if (!ExtSymDefinedIn.empty())
1056     OS << "@M@" << ExtSymDefinedIn;
1057   OS << "@E@" << EnumName;
1058 }
1059 
generateUSRForEnumConstant(StringRef EnumConstantName,raw_ostream & OS)1060 void clang::index::generateUSRForEnumConstant(StringRef EnumConstantName,
1061                                               raw_ostream &OS) {
1062   OS << '@' << EnumConstantName;
1063 }
1064 
generateUSRForDecl(const Decl * D,SmallVectorImpl<char> & Buf)1065 bool clang::index::generateUSRForDecl(const Decl *D,
1066                                       SmallVectorImpl<char> &Buf) {
1067   if (!D)
1068     return true;
1069   // We don't ignore decls with invalid source locations. Implicit decls, like
1070   // C++'s operator new function, can have invalid locations but it is fine to
1071   // create USRs that can identify them.
1072 
1073   USRGenerator UG(&D->getASTContext(), Buf);
1074   UG.Visit(D);
1075   return UG.ignoreResults();
1076 }
1077 
generateUSRForMacro(const MacroDefinitionRecord * MD,const SourceManager & SM,SmallVectorImpl<char> & Buf)1078 bool clang::index::generateUSRForMacro(const MacroDefinitionRecord *MD,
1079                                        const SourceManager &SM,
1080                                        SmallVectorImpl<char> &Buf) {
1081   if (!MD)
1082     return true;
1083   return generateUSRForMacro(MD->getName()->getName(), MD->getLocation(),
1084                              SM, Buf);
1085 
1086 }
1087 
generateUSRForMacro(StringRef MacroName,SourceLocation Loc,const SourceManager & SM,SmallVectorImpl<char> & Buf)1088 bool clang::index::generateUSRForMacro(StringRef MacroName, SourceLocation Loc,
1089                                        const SourceManager &SM,
1090                                        SmallVectorImpl<char> &Buf) {
1091   // Don't generate USRs for things with invalid locations.
1092   if (MacroName.empty() || Loc.isInvalid())
1093     return true;
1094 
1095   llvm::raw_svector_ostream Out(Buf);
1096 
1097   // Assume that system headers are sane.  Don't put source location
1098   // information into the USR if the macro comes from a system header.
1099   bool ShouldGenerateLocation = !SM.isInSystemHeader(Loc);
1100 
1101   Out << getUSRSpacePrefix();
1102   if (ShouldGenerateLocation)
1103     printLoc(Out, Loc, SM, /*IncludeOffset=*/true);
1104   Out << "@macro@";
1105   Out << MacroName;
1106   return false;
1107 }
1108 
generateUSRForType(QualType T,ASTContext & Ctx,SmallVectorImpl<char> & Buf)1109 bool clang::index::generateUSRForType(QualType T, ASTContext &Ctx,
1110                                       SmallVectorImpl<char> &Buf) {
1111   if (T.isNull())
1112     return true;
1113   T = T.getCanonicalType();
1114 
1115   USRGenerator UG(&Ctx, Buf);
1116   UG.VisitType(T);
1117   return UG.ignoreResults();
1118 }
1119 
generateFullUSRForModule(const Module * Mod,raw_ostream & OS)1120 bool clang::index::generateFullUSRForModule(const Module *Mod,
1121                                             raw_ostream &OS) {
1122   if (!Mod->Parent)
1123     return generateFullUSRForTopLevelModuleName(Mod->Name, OS);
1124   if (generateFullUSRForModule(Mod->Parent, OS))
1125     return true;
1126   return generateUSRFragmentForModule(Mod, OS);
1127 }
1128 
generateFullUSRForTopLevelModuleName(StringRef ModName,raw_ostream & OS)1129 bool clang::index::generateFullUSRForTopLevelModuleName(StringRef ModName,
1130                                                         raw_ostream &OS) {
1131   OS << getUSRSpacePrefix();
1132   return generateUSRFragmentForModuleName(ModName, OS);
1133 }
1134 
generateUSRFragmentForModule(const Module * Mod,raw_ostream & OS)1135 bool clang::index::generateUSRFragmentForModule(const Module *Mod,
1136                                                 raw_ostream &OS) {
1137   return generateUSRFragmentForModuleName(Mod->Name, OS);
1138 }
1139 
generateUSRFragmentForModuleName(StringRef ModName,raw_ostream & OS)1140 bool clang::index::generateUSRFragmentForModuleName(StringRef ModName,
1141                                                     raw_ostream &OS) {
1142   OS << "@M@" << ModName;
1143   return false;
1144 }
1145