contrib/llvm/tools/clang/lib/Index/USRGeneration.cpp

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