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