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