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