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