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