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