lib/Index/USRGeneration.cpp

   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 #define SVE_TYPE(Name, Id, SingletonId) \
 728         case BuiltinType::Id:
 729 #include "clang/Basic/AArch64SVEACLETypes.def"
 730         case BuiltinType::ShortAccum:
 731         case BuiltinType::Accum:
 732         case BuiltinType::LongAccum:
 733         case BuiltinType::UShortAccum:
 734         case BuiltinType::UAccum:
 735         case BuiltinType::ULongAccum:
 736         case BuiltinType::ShortFract:
 737         case BuiltinType::Fract:
 738         case BuiltinType::LongFract:
 739         case BuiltinType::UShortFract:
 740         case BuiltinType::UFract:
 741         case BuiltinType::ULongFract:
 742         case BuiltinType::SatShortAccum:
 743         case BuiltinType::SatAccum:
 744         case BuiltinType::SatLongAccum:
 745         case BuiltinType::SatUShortAccum:
 746         case BuiltinType::SatUAccum:
 747         case BuiltinType::SatULongAccum:
 748         case BuiltinType::SatShortFract:
 749         case BuiltinType::SatFract:
 750         case BuiltinType::SatLongFract:
 751         case BuiltinType::SatUShortFract:
 752         case BuiltinType::SatUFract:
 753         case BuiltinType::SatULongFract:
 754           IgnoreResults = true;
 755           return;
 756         case BuiltinType::ObjCId:
 757           c = 'o'; break;
 758         case BuiltinType::ObjCClass:
 759           c = 'O'; break;
 760         case BuiltinType::ObjCSel:
 761           c = 'e'; break;
 762       }
 763       Out << c;
 764       return;
 765     }
 766
 767     // If we have already seen this (non-built-in) type, use a substitution
 768     // encoding.
 769     llvm::DenseMap<const Type *, unsigned>::iterator Substitution
 770       = TypeSubstitutions.find(T.getTypePtr());
 771     if (Substitution != TypeSubstitutions.end()) {
 772       Out << 'S' << Substitution->second << '_';
 773       return;
 774     } else {
 775       // Record this as a substitution.
 776       unsigned Number = TypeSubstitutions.size();
 777       TypeSubstitutions[T.getTypePtr()] = Number;
 778     }
 779
 780     if (const PointerType *PT = T->getAs<PointerType>()) {
 781       Out << '*';
 782       T = PT->getPointeeType();
 783       continue;
 784     }
 785     if (const ObjCObjectPointerType *OPT = T->getAs<ObjCObjectPointerType>()) {
 786       Out << '*';
 787       T = OPT->getPointeeType();
 788       continue;
 789     }
 790     if (const RValueReferenceType *RT = T->getAs<RValueReferenceType>()) {
 791       Out << "&&";
 792       T = RT->getPointeeType();
 793       continue;
 794     }
 795     if (const ReferenceType *RT = T->getAs<ReferenceType>()) {
 796       Out << '&';
 797       T = RT->getPointeeType();
 798       continue;
 799     }
 800     if (const FunctionProtoType *FT = T->getAs<FunctionProtoType>()) {
 801       Out << 'F';
 802       VisitType(FT->getReturnType());
 803       Out << '(';
 804       for (const auto &I : FT->param_types()) {
 805         Out << '#';
 806         VisitType(I);
 807       }
 808       Out << ')';
 809       if (FT->isVariadic())
 810         Out << '.';
 811       return;
 812     }
 813     if (const BlockPointerType *BT = T->getAs<BlockPointerType>()) {
 814       Out << 'B';
 815       T = BT->getPointeeType();
 816       continue;
 817     }
 818     if (const ComplexType *CT = T->getAs<ComplexType>()) {
 819       Out << '<';
 820       T = CT->getElementType();
 821       continue;
 822     }
 823     if (const TagType *TT = T->getAs<TagType>()) {
 824       Out << '$';
 825       VisitTagDecl(TT->getDecl());
 826       return;
 827     }
 828     if (const ObjCInterfaceType *OIT = T->getAs<ObjCInterfaceType>()) {
 829       Out << '$';
 830       VisitObjCInterfaceDecl(OIT->getDecl());
 831       return;
 832     }
 833     if (const ObjCObjectType *OIT = T->getAs<ObjCObjectType>()) {
 834       Out << 'Q';
 835       VisitType(OIT->getBaseType());
 836       for (auto *Prot : OIT->getProtocols())
 837         VisitObjCProtocolDecl(Prot);
 838       return;
 839     }
 840     if (const TemplateTypeParmType *TTP = T->getAs<TemplateTypeParmType>()) {
 841       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
 842       return;
 843     }
 844     if (const TemplateSpecializationType *Spec
 845                                     = T->getAs<TemplateSpecializationType>()) {
 846       Out << '>';
 847       VisitTemplateName(Spec->getTemplateName());
 848       Out << Spec->getNumArgs();
 849       for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
 850         VisitTemplateArgument(Spec->getArg(I));
 851       return;
 852     }
 853     if (const DependentNameType *DNT = T->getAs<DependentNameType>()) {
 854       Out << '^';
 855       printQualifier(Out, Ctx, DNT->getQualifier());
 856       Out << ':' << DNT->getIdentifier()->getName();
 857       return;
 858     }
 859     if (const InjectedClassNameType *InjT = T->getAs<InjectedClassNameType>()) {
 860       T = InjT->getInjectedSpecializationType();
 861       continue;
 862     }
 863     if (const auto *VT = T->getAs<VectorType>()) {
 864       Out << (T->isExtVectorType() ? ']' : '[');
 865       Out << VT->getNumElements();
 866       T = VT->getElementType();
 867       continue;
 868     }
 869     if (const auto *const AT = dyn_cast<ArrayType>(T)) {
 870       Out << '{';
 871       switch (AT->getSizeModifier()) {
 872       case ArrayType::Static:
 873         Out << 's';
 874         break;
 875       case ArrayType::Star:
 876         Out << '*';
 877         break;
 878       case ArrayType::Normal:
 879         Out << 'n';
 880         break;
 881       }
 882       if (const auto *const CAT = dyn_cast<ConstantArrayType>(T))
 883         Out << CAT->getSize();
 884
 885       T = AT->getElementType();
 886       continue;
 887     }
 888
 889     // Unhandled type.
 890     Out << ' ';
 891     break;
 892   } while (true);
 893 }
 894
 895 void USRGenerator::VisitTemplateParameterList(
 896                                          const TemplateParameterList *Params) {
 897   if (!Params)
 898     return;
 899   Out << '>' << Params->size();
 900   for (TemplateParameterList::const_iterator P = Params->begin(),
 901                                           PEnd = Params->end();
 902        P != PEnd; ++P) {
 903     Out << '#';
 904     if (isa<TemplateTypeParmDecl>(*P)) {
 905       if (cast<TemplateTypeParmDecl>(*P)->isParameterPack())
 906         Out<< 'p';
 907       Out << 'T';
 908       continue;
 909     }
 910
 911     if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
 912       if (NTTP->isParameterPack())
 913         Out << 'p';
 914       Out << 'N';
 915       VisitType(NTTP->getType());
 916       continue;
 917     }
 918
 919     TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
 920     if (TTP->isParameterPack())
 921       Out << 'p';
 922     Out << 't';
 923     VisitTemplateParameterList(TTP->getTemplateParameters());
 924   }
 925 }
 926
 927 void USRGenerator::VisitTemplateName(TemplateName Name) {
 928   if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
 929     if (TemplateTemplateParmDecl *TTP
 930                               = dyn_cast<TemplateTemplateParmDecl>(Template)) {
 931       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
 932       return;
 933     }
 934
 935     Visit(Template);
 936     return;
 937   }
 938
 939   // FIXME: Visit dependent template names.
 940 }
 941
 942 void USRGenerator::VisitTemplateArgument(const TemplateArgument &Arg) {
 943   switch (Arg.getKind()) {
 944   case TemplateArgument::Null:
 945     break;
 946
 947   case TemplateArgument::Declaration:
 948     Visit(Arg.getAsDecl());
 949     break;
 950
 951   case TemplateArgument::NullPtr:
 952     break;
 953
 954   case TemplateArgument::TemplateExpansion:
 955     Out << 'P'; // pack expansion of...
 956     LLVM_FALLTHROUGH;
 957   case TemplateArgument::Template:
 958     VisitTemplateName(Arg.getAsTemplateOrTemplatePattern());
 959     break;
 960
 961   case TemplateArgument::Expression:
 962     // FIXME: Visit expressions.
 963     break;
 964
 965   case TemplateArgument::Pack:
 966     Out << 'p' << Arg.pack_size();
 967     for (const auto &P : Arg.pack_elements())
 968       VisitTemplateArgument(P);
 969     break;
 970
 971   case TemplateArgument::Type:
 972     VisitType(Arg.getAsType());
 973     break;
 974
 975   case TemplateArgument::Integral:
 976     Out << 'V';
 977     VisitType(Arg.getIntegralType());
 978     Out << Arg.getAsIntegral();
 979     break;
 980   }
 981 }
 982
 983 void USRGenerator::VisitUnresolvedUsingValueDecl(const UnresolvedUsingValueDecl *D) {
 984   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
 985     return;
 986   VisitDeclContext(D->getDeclContext());
 987   Out << "@UUV@";
 988   printQualifier(Out, D->getASTContext(), D->getQualifier());
 989   EmitDeclName(D);
 990 }
 991
 992 void USRGenerator::VisitUnresolvedUsingTypenameDecl(const UnresolvedUsingTypenameDecl *D) {
 993   if (ShouldGenerateLocation(D) && GenLoc(D, /*IncludeOffset=*/isLocal(D)))
 994     return;
 995   VisitDeclContext(D->getDeclContext());
 996   Out << "@UUT@";
 997   printQualifier(Out, D->getASTContext(), D->getQualifier());
 998   Out << D->getName(); // Simple name.
 999 }
1000
1001
1002
1003 //===----------------------------------------------------------------------===//
1004 // USR generation functions.
1005 //===----------------------------------------------------------------------===//
1006
1007 static void combineClassAndCategoryExtContainers(StringRef ClsSymDefinedIn,
1008                                                  StringRef CatSymDefinedIn,
1009                                                  raw_ostream &OS) {
1010   if (ClsSymDefinedIn.empty() && CatSymDefinedIn.empty())
1011     return;
1012   if (CatSymDefinedIn.empty()) {
1013     OS << "@M@" << ClsSymDefinedIn << '@';
1014     return;
1015   }
1016   OS << "@CM@" << CatSymDefinedIn << '@';
1017   if (ClsSymDefinedIn != CatSymDefinedIn) {
1018     OS << ClsSymDefinedIn << '@';
1019   }
1020 }
1021
1022 void clang::index::generateUSRForObjCClass(StringRef Cls, raw_ostream &OS,
1023                                            StringRef ExtSymDefinedIn,
1024                                   StringRef CategoryContextExtSymbolDefinedIn) {
1025   combineClassAndCategoryExtContainers(ExtSymDefinedIn,
1026                                        CategoryContextExtSymbolDefinedIn, OS);
1027   OS << "objc(cs)" << Cls;
1028 }
1029
1030 void clang::index::generateUSRForObjCCategory(StringRef Cls, StringRef Cat,
1031                                               raw_ostream &OS,
1032                                               StringRef ClsSymDefinedIn,
1033                                               StringRef CatSymDefinedIn) {
1034   combineClassAndCategoryExtContainers(ClsSymDefinedIn, CatSymDefinedIn, OS);
1035   OS << "objc(cy)" << Cls << '@' << Cat;
1036 }
1037
1038 void clang::index::generateUSRForObjCIvar(StringRef Ivar, raw_ostream &OS) {
1039   OS << '@' << Ivar;
1040 }
1041
1042 void clang::index::generateUSRForObjCMethod(StringRef Sel,
1043                                             bool IsInstanceMethod,
1044                                             raw_ostream &OS) {
1045   OS << (IsInstanceMethod ? "(im)" : "(cm)") << Sel;
1046 }
1047
1048 void clang::index::generateUSRForObjCProperty(StringRef Prop, bool isClassProp,
1049                                               raw_ostream &OS) {
1050   OS << (isClassProp ? "(cpy)" : "(py)") << Prop;
1051 }
1052
1053 void clang::index::generateUSRForObjCProtocol(StringRef Prot, raw_ostream &OS,
1054                                               StringRef ExtSymDefinedIn) {
1055   if (!ExtSymDefinedIn.empty())
1056     OS << "@M@" << ExtSymDefinedIn << '@';
1057   OS << "objc(pl)" << Prot;
1058 }
1059
1060 void clang::index::generateUSRForGlobalEnum(StringRef EnumName, raw_ostream &OS,
1061                                             StringRef ExtSymDefinedIn) {
1062   if (!ExtSymDefinedIn.empty())
1063     OS << "@M@" << ExtSymDefinedIn;
1064   OS << "@E@" << EnumName;
1065 }
1066
1067 void clang::index::generateUSRForEnumConstant(StringRef EnumConstantName,
1068                                               raw_ostream &OS) {
1069   OS << '@' << EnumConstantName;
1070 }
1071
1072 bool clang::index::generateUSRForDecl(const Decl *D,
1073                                       SmallVectorImpl<char> &Buf) {
1074   if (!D)
1075     return true;
1076   // We don't ignore decls with invalid source locations. Implicit decls, like
1077   // C++'s operator new function, can have invalid locations but it is fine to
1078   // create USRs that can identify them.
1079
1080   USRGenerator UG(&D->getASTContext(), Buf);
1081   UG.Visit(D);
1082   return UG.ignoreResults();
1083 }
1084
1085 bool clang::index::generateUSRForMacro(const MacroDefinitionRecord *MD,
1086                                        const SourceManager &SM,
1087                                        SmallVectorImpl<char> &Buf) {
1088   if (!MD)
1089     return true;
1090   return generateUSRForMacro(MD->getName()->getName(), MD->getLocation(),
1091                              SM, Buf);
1092
1093 }
1094
1095 bool clang::index::generateUSRForMacro(StringRef MacroName, SourceLocation Loc,
1096                                        const SourceManager &SM,
1097                                        SmallVectorImpl<char> &Buf) {
1098   // Don't generate USRs for things with invalid locations.
1099   if (MacroName.empty() || Loc.isInvalid())
1100     return true;
1101
1102   llvm::raw_svector_ostream Out(Buf);
1103
1104   // Assume that system headers are sane.  Don't put source location
1105   // information into the USR if the macro comes from a system header.
1106   bool ShouldGenerateLocation = !SM.isInSystemHeader(Loc);
1107
1108   Out << getUSRSpacePrefix();
1109   if (ShouldGenerateLocation)
1110     printLoc(Out, Loc, SM, /*IncludeOffset=*/true);
1111   Out << "@macro@";
1112   Out << MacroName;
1113   return false;
1114 }
1115
1116 bool clang::index::generateUSRForType(QualType T, ASTContext &Ctx,
1117                                       SmallVectorImpl<char> &Buf) {
1118   if (T.isNull())
1119     return true;
1120   T = T.getCanonicalType();
1121
1122   USRGenerator UG(&Ctx, Buf);
1123   UG.VisitType(T);
1124   return UG.ignoreResults();
1125 }
1126
1127 bool clang::index::generateFullUSRForModule(const Module *Mod,
1128                                             raw_ostream &OS) {
1129   if (!Mod->Parent)
1130     return generateFullUSRForTopLevelModuleName(Mod->Name, OS);
1131   if (generateFullUSRForModule(Mod->Parent, OS))
1132     return true;
1133   return generateUSRFragmentForModule(Mod, OS);
1134 }
1135
1136 bool clang::index::generateFullUSRForTopLevelModuleName(StringRef ModName,
1137                                                         raw_ostream &OS) {
1138   OS << getUSRSpacePrefix();
1139   return generateUSRFragmentForModuleName(ModName, OS);
1140 }
1141
1142 bool clang::index::generateUSRFragmentForModule(const Module *Mod,
1143                                                 raw_ostream &OS) {
1144   return generateUSRFragmentForModuleName(Mod->Name, OS);
1145 }
1146
1147 bool clang::index::generateUSRFragmentForModuleName(StringRef ModName,
1148                                                     raw_ostream &OS) {
1149   OS << "@M@" << ModName;
1150   return false;
1151 }