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