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