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