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 "llvm/ADT/SmallString.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 namespace {
  26 class USRGenerator : public ConstDeclVisitor<USRGenerator> {
  27   SmallVectorImpl<char> &Buf;
  28   llvm::raw_svector_ostream Out;
  29   bool IgnoreResults;
  30   ASTContext *Context;
  31   bool generatedLoc;
  32
  33   llvm::DenseMap<const Type *, unsigned> TypeSubstitutions;
  34
  35 public:
  36   explicit USRGenerator(ASTContext *Ctx, SmallVectorImpl<char> &Buf)
  37   : Buf(Buf),
  38     Out(Buf),
  39     IgnoreResults(false),
  40     Context(Ctx),
  41     generatedLoc(false)
  42   {
  43     // Add the USR space prefix.
  44     Out << getUSRSpacePrefix();
  45   }
  46
  47   bool ignoreResults() const { return IgnoreResults; }
  48
  49   // Visitation methods from generating USRs from AST elements.
  50   void VisitDeclContext(const DeclContext *D);
  51   void VisitFieldDecl(const FieldDecl *D);
  52   void VisitFunctionDecl(const FunctionDecl *D);
  53   void VisitNamedDecl(const NamedDecl *D);
  54   void VisitNamespaceDecl(const NamespaceDecl *D);
  55   void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D);
  56   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D);
  57   void VisitClassTemplateDecl(const ClassTemplateDecl *D);
  58   void VisitObjCContainerDecl(const ObjCContainerDecl *CD);
  59   void VisitObjCMethodDecl(const ObjCMethodDecl *MD);
  60   void VisitObjCPropertyDecl(const ObjCPropertyDecl *D);
  61   void VisitObjCPropertyImplDecl(const ObjCPropertyImplDecl *D);
  62   void VisitTagDecl(const TagDecl *D);
  63   void VisitTypedefDecl(const TypedefDecl *D);
  64   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D);
  65   void VisitVarDecl(const VarDecl *D);
  66   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D);
  67   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D);
  68   void VisitLinkageSpecDecl(const LinkageSpecDecl *D) {
  69     IgnoreResults = true;
  70   }
  71   void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) {
  72     IgnoreResults = true;
  73   }
  74   void VisitUsingDecl(const UsingDecl *D) {
  75     IgnoreResults = true;
  76   }
  77   void VisitUnresolvedUsingValueDecl(const UnresolvedUsingValueDecl *D) {
  78     IgnoreResults = true;
  79   }
  80   void VisitUnresolvedUsingTypenameDecl(const UnresolvedUsingTypenameDecl *D) {
  81     IgnoreResults = true;
  82   }
  83
  84   /// Generate the string component containing the location of the
  85   ///  declaration.
  86   bool GenLoc(const Decl *D);
  87
  88   /// String generation methods used both by the visitation methods
  89   /// and from other clients that want to directly generate USRs.  These
  90   /// methods do not construct complete USRs (which incorporate the parents
  91   /// of an AST element), but only the fragments concerning the AST element
  92   /// itself.
  93
  94   /// Generate a USR for an Objective-C class.
  95   void GenObjCClass(StringRef cls) {
  96     generateUSRForObjCClass(cls, Out);
  97   }
  98   /// Generate a USR for an Objective-C class category.
  99   void GenObjCCategory(StringRef cls, StringRef cat) {
 100     generateUSRForObjCCategory(cls, cat, Out);
 101   }
 102   /// Generate a USR fragment for an Objective-C instance variable.  The
 103   /// complete USR can be created by concatenating the USR for the
 104   /// encompassing class with this USR fragment.
 105   void GenObjCIvar(StringRef ivar) {
 106     generateUSRForObjCIvar(ivar, Out);
 107   }
 108   /// Generate a USR fragment for an Objective-C method.
 109   void GenObjCMethod(StringRef sel, bool isInstanceMethod) {
 110     generateUSRForObjCMethod(sel, isInstanceMethod, Out);
 111   }
 112   /// Generate a USR fragment for an Objective-C property.
 113   void GenObjCProperty(StringRef prop) {
 114     generateUSRForObjCProperty(prop, Out);
 115   }
 116   /// Generate a USR for an Objective-C protocol.
 117   void GenObjCProtocol(StringRef prot) {
 118     generateUSRForObjCProtocol(prot, Out);
 119   }
 120
 121   void VisitType(QualType T);
 122   void VisitTemplateParameterList(const TemplateParameterList *Params);
 123   void VisitTemplateName(TemplateName Name);
 124   void VisitTemplateArgument(const TemplateArgument &Arg);
 125
 126   /// Emit a Decl's name using NamedDecl::printName() and return true if
 127   ///  the decl had no name.
 128   bool EmitDeclName(const NamedDecl *D);
 129 };
 130
 131 } // end anonymous namespace
 132
 133 //===----------------------------------------------------------------------===//
 134 // Generating USRs from ASTS.
 135 //===----------------------------------------------------------------------===//
 136
 137 bool USRGenerator::EmitDeclName(const NamedDecl *D) {
 138   Out.flush();
 139   const unsigned startSize = Buf.size();
 140   D->printName(Out);
 141   Out.flush();
 142   const unsigned endSize = Buf.size();
 143   return startSize == endSize;
 144 }
 145
 146 static inline bool ShouldGenerateLocation(const NamedDecl *D) {
 147   return !D->isExternallyVisible();
 148 }
 149
 150 void USRGenerator::VisitDeclContext(const DeclContext *DC) {
 151   if (const NamedDecl *D = dyn_cast<NamedDecl>(DC))
 152     Visit(D);
 153 }
 154
 155 void USRGenerator::VisitFieldDecl(const FieldDecl *D) {
 156   // The USR for an ivar declared in a class extension is based on the
 157   // ObjCInterfaceDecl, not the ObjCCategoryDecl.
 158   if (const ObjCInterfaceDecl *ID = Context->getObjContainingInterface(D))
 159     Visit(ID);
 160   else
 161     VisitDeclContext(D->getDeclContext());
 162   Out << (isa<ObjCIvarDecl>(D) ? "@" : "@FI@");
 163   if (EmitDeclName(D)) {
 164     // Bit fields can be anonymous.
 165     IgnoreResults = true;
 166     return;
 167   }
 168 }
 169
 170 void USRGenerator::VisitFunctionDecl(const FunctionDecl *D) {
 171   if (ShouldGenerateLocation(D) && GenLoc(D))
 172     return;
 173
 174   VisitDeclContext(D->getDeclContext());
 175   if (FunctionTemplateDecl *FunTmpl = D->getDescribedFunctionTemplate()) {
 176     Out << "@FT@";
 177     VisitTemplateParameterList(FunTmpl->getTemplateParameters());
 178   } else
 179     Out << "@F@";
 180   D->printName(Out);
 181
 182   ASTContext &Ctx = *Context;
 183   if (!Ctx.getLangOpts().CPlusPlus || D->isExternC())
 184     return;
 185
 186   if (const TemplateArgumentList *
 187         SpecArgs = D->getTemplateSpecializationArgs()) {
 188     Out << '<';
 189     for (unsigned I = 0, N = SpecArgs->size(); I != N; ++I) {
 190       Out << '#';
 191       VisitTemplateArgument(SpecArgs->get(I));
 192     }
 193     Out << '>';
 194   }
 195
 196   // Mangle in type information for the arguments.
 197   for (FunctionDecl::param_const_iterator I = D->param_begin(),
 198                                           E = D->param_end();
 199        I != E; ++I) {
 200     Out << '#';
 201     if (ParmVarDecl *PD = *I)
 202       VisitType(PD->getType());
 203   }
 204   if (D->isVariadic())
 205     Out << '.';
 206   Out << '#';
 207   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
 208     if (MD->isStatic())
 209       Out << 'S';
 210     if (unsigned quals = MD->getTypeQualifiers())
 211       Out << (char)('0' + quals);
 212   }
 213 }
 214
 215 void USRGenerator::VisitNamedDecl(const NamedDecl *D) {
 216   VisitDeclContext(D->getDeclContext());
 217   Out << "@";
 218
 219   if (EmitDeclName(D)) {
 220     // The string can be empty if the declaration has no name; e.g., it is
 221     // the ParmDecl with no name for declaration of a function pointer type,
 222     // e.g.: void  (*f)(void *);
 223     // In this case, don't generate a USR.
 224     IgnoreResults = true;
 225   }
 226 }
 227
 228 void USRGenerator::VisitVarDecl(const VarDecl *D) {
 229   // VarDecls can be declared 'extern' within a function or method body,
 230   // but their enclosing DeclContext is the function, not the TU.  We need
 231   // to check the storage class to correctly generate the USR.
 232   if (ShouldGenerateLocation(D) && GenLoc(D))
 233     return;
 234
 235   VisitDeclContext(D->getDeclContext());
 236
 237   // Variables always have simple names.
 238   StringRef s = D->getName();
 239
 240   // The string can be empty if the declaration has no name; e.g., it is
 241   // the ParmDecl with no name for declaration of a function pointer type, e.g.:
 242   //    void  (*f)(void *);
 243   // In this case, don't generate a USR.
 244   if (s.empty())
 245     IgnoreResults = true;
 246   else
 247     Out << '@' << s;
 248 }
 249
 250 void USRGenerator::VisitNonTypeTemplateParmDecl(
 251                                         const NonTypeTemplateParmDecl *D) {
 252   GenLoc(D);
 253   return;
 254 }
 255
 256 void USRGenerator::VisitTemplateTemplateParmDecl(
 257                                         const TemplateTemplateParmDecl *D) {
 258   GenLoc(D);
 259   return;
 260 }
 261
 262 void USRGenerator::VisitNamespaceDecl(const NamespaceDecl *D) {
 263   if (D->isAnonymousNamespace()) {
 264     Out << "@aN";
 265     return;
 266   }
 267
 268   VisitDeclContext(D->getDeclContext());
 269   if (!IgnoreResults)
 270     Out << "@N@" << D->getName();
 271 }
 272
 273 void USRGenerator::VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
 274   VisitFunctionDecl(D->getTemplatedDecl());
 275 }
 276
 277 void USRGenerator::VisitClassTemplateDecl(const ClassTemplateDecl *D) {
 278   VisitTagDecl(D->getTemplatedDecl());
 279 }
 280
 281 void USRGenerator::VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) {
 282   VisitDeclContext(D->getDeclContext());
 283   if (!IgnoreResults)
 284     Out << "@NA@" << D->getName();
 285 }
 286
 287 void USRGenerator::VisitObjCMethodDecl(const ObjCMethodDecl *D) {
 288   const DeclContext *container = D->getDeclContext();
 289   if (const ObjCProtocolDecl *pd = dyn_cast<ObjCProtocolDecl>(container)) {
 290     Visit(pd);
 291   }
 292   else {
 293     // The USR for a method declared in a class extension or category is based on
 294     // the ObjCInterfaceDecl, not the ObjCCategoryDecl.
 295     const ObjCInterfaceDecl *ID = D->getClassInterface();
 296     if (!ID) {
 297       IgnoreResults = true;
 298       return;
 299     }
 300     Visit(ID);
 301   }
 302   // Ideally we would use 'GenObjCMethod', but this is such a hot path
 303   // for Objective-C code that we don't want to use
 304   // DeclarationName::getAsString().
 305   Out << (D->isInstanceMethod() ? "(im)" : "(cm)")
 306       << DeclarationName(D->getSelector());
 307 }
 308
 309 void USRGenerator::VisitObjCContainerDecl(const ObjCContainerDecl *D) {
 310   switch (D->getKind()) {
 311     default:
 312       llvm_unreachable("Invalid ObjC container.");
 313     case Decl::ObjCInterface:
 314     case Decl::ObjCImplementation:
 315       GenObjCClass(D->getName());
 316       break;
 317     case Decl::ObjCCategory: {
 318       const ObjCCategoryDecl *CD = cast<ObjCCategoryDecl>(D);
 319       const ObjCInterfaceDecl *ID = CD->getClassInterface();
 320       if (!ID) {
 321         // Handle invalid code where the @interface might not
 322         // have been specified.
 323         // FIXME: We should be able to generate this USR even if the
 324         // @interface isn't available.
 325         IgnoreResults = true;
 326         return;
 327       }
 328       // Specially handle class extensions, which are anonymous categories.
 329       // We want to mangle in the location to uniquely distinguish them.
 330       if (CD->IsClassExtension()) {
 331         Out << "objc(ext)" << ID->getName() << '@';
 332         GenLoc(CD);
 333       }
 334       else
 335         GenObjCCategory(ID->getName(), CD->getName());
 336
 337       break;
 338     }
 339     case Decl::ObjCCategoryImpl: {
 340       const ObjCCategoryImplDecl *CD = cast<ObjCCategoryImplDecl>(D);
 341       const ObjCInterfaceDecl *ID = CD->getClassInterface();
 342       if (!ID) {
 343         // Handle invalid code where the @interface might not
 344         // have been specified.
 345         // FIXME: We should be able to generate this USR even if the
 346         // @interface isn't available.
 347         IgnoreResults = true;
 348         return;
 349       }
 350       GenObjCCategory(ID->getName(), CD->getName());
 351       break;
 352     }
 353     case Decl::ObjCProtocol:
 354       GenObjCProtocol(cast<ObjCProtocolDecl>(D)->getName());
 355       break;
 356   }
 357 }
 358
 359 void USRGenerator::VisitObjCPropertyDecl(const ObjCPropertyDecl *D) {
 360   // The USR for a property declared in a class extension or category is based
 361   // on the ObjCInterfaceDecl, not the ObjCCategoryDecl.
 362   if (const ObjCInterfaceDecl *ID = Context->getObjContainingInterface(D))
 363     Visit(ID);
 364   else
 365     Visit(cast<Decl>(D->getDeclContext()));
 366   GenObjCProperty(D->getName());
 367 }
 368
 369 void USRGenerator::VisitObjCPropertyImplDecl(const ObjCPropertyImplDecl *D) {
 370   if (ObjCPropertyDecl *PD = D->getPropertyDecl()) {
 371     VisitObjCPropertyDecl(PD);
 372     return;
 373   }
 374
 375   IgnoreResults = true;
 376 }
 377
 378 void USRGenerator::VisitTagDecl(const TagDecl *D) {
 379   // Add the location of the tag decl to handle resolution across
 380   // translation units.
 381   if (ShouldGenerateLocation(D) && GenLoc(D))
 382     return;
 383
 384   D = D->getCanonicalDecl();
 385   VisitDeclContext(D->getDeclContext());
 386
 387   bool AlreadyStarted = false;
 388   if (const CXXRecordDecl *CXXRecord = dyn_cast<CXXRecordDecl>(D)) {
 389     if (ClassTemplateDecl *ClassTmpl = CXXRecord->getDescribedClassTemplate()) {
 390       AlreadyStarted = true;
 391
 392       switch (D->getTagKind()) {
 393       case TTK_Interface:
 394       case TTK_Struct: Out << "@ST"; break;
 395       case TTK_Class:  Out << "@CT"; break;
 396       case TTK_Union:  Out << "@UT"; break;
 397       case TTK_Enum: llvm_unreachable("enum template");
 398       }
 399       VisitTemplateParameterList(ClassTmpl->getTemplateParameters());
 400     } else if (const ClassTemplatePartialSpecializationDecl *PartialSpec
 401                 = dyn_cast<ClassTemplatePartialSpecializationDecl>(CXXRecord)) {
 402       AlreadyStarted = true;
 403
 404       switch (D->getTagKind()) {
 405       case TTK_Interface:
 406       case TTK_Struct: Out << "@SP"; break;
 407       case TTK_Class:  Out << "@CP"; break;
 408       case TTK_Union:  Out << "@UP"; break;
 409       case TTK_Enum: llvm_unreachable("enum partial specialization");
 410       }
 411       VisitTemplateParameterList(PartialSpec->getTemplateParameters());
 412     }
 413   }
 414
 415   if (!AlreadyStarted) {
 416     switch (D->getTagKind()) {
 417       case TTK_Interface:
 418       case TTK_Struct: Out << "@S"; break;
 419       case TTK_Class:  Out << "@C"; break;
 420       case TTK_Union:  Out << "@U"; break;
 421       case TTK_Enum:   Out << "@E"; break;
 422     }
 423   }
 424
 425   Out << '@';
 426   Out.flush();
 427   assert(Buf.size() > 0);
 428   const unsigned off = Buf.size() - 1;
 429
 430   if (EmitDeclName(D)) {
 431     if (const TypedefNameDecl *TD = D->getTypedefNameForAnonDecl()) {
 432       Buf[off] = 'A';
 433       Out << '@' << *TD;
 434     }
 435     else
 436       Buf[off] = 'a';
 437   }
 438
 439   // For a class template specialization, mangle the template arguments.
 440   if (const ClassTemplateSpecializationDecl *Spec
 441                               = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
 442     const TemplateArgumentList &Args = Spec->getTemplateInstantiationArgs();
 443     Out << '>';
 444     for (unsigned I = 0, N = Args.size(); I != N; ++I) {
 445       Out << '#';
 446       VisitTemplateArgument(Args.get(I));
 447     }
 448   }
 449 }
 450
 451 void USRGenerator::VisitTypedefDecl(const TypedefDecl *D) {
 452   if (ShouldGenerateLocation(D) && GenLoc(D))
 453     return;
 454   const DeclContext *DC = D->getDeclContext();
 455   if (const NamedDecl *DCN = dyn_cast<NamedDecl>(DC))
 456     Visit(DCN);
 457   Out << "@T@";
 458   Out << D->getName();
 459 }
 460
 461 void USRGenerator::VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
 462   GenLoc(D);
 463   return;
 464 }
 465
 466 bool USRGenerator::GenLoc(const Decl *D) {
 467   if (generatedLoc)
 468     return IgnoreResults;
 469   generatedLoc = true;
 470
 471   // Guard against null declarations in invalid code.
 472   if (!D) {
 473     IgnoreResults = true;
 474     return true;
 475   }
 476
 477   // Use the location of canonical decl.
 478   D = D->getCanonicalDecl();
 479
 480   const SourceManager &SM = Context->getSourceManager();
 481   SourceLocation L = D->getLocStart();
 482   if (L.isInvalid()) {
 483     IgnoreResults = true;
 484     return true;
 485   }
 486   L = SM.getExpansionLoc(L);
 487   const std::pair<FileID, unsigned> &Decomposed = SM.getDecomposedLoc(L);
 488   const FileEntry *FE = SM.getFileEntryForID(Decomposed.first);
 489   if (FE) {
 490     Out << llvm::sys::path::filename(FE->getName());
 491   }
 492   else {
 493     // This case really isn't interesting.
 494     IgnoreResults = true;
 495     return true;
 496   }
 497   // Use the offest into the FileID to represent the location.  Using
 498   // a line/column can cause us to look back at the original source file,
 499   // which is expensive.
 500   Out << '@' << Decomposed.second;
 501   return IgnoreResults;
 502 }
 503
 504 void USRGenerator::VisitType(QualType T) {
 505   // This method mangles in USR information for types.  It can possibly
 506   // just reuse the naming-mangling logic used by codegen, although the
 507   // requirements for USRs might not be the same.
 508   ASTContext &Ctx = *Context;
 509
 510   do {
 511     T = Ctx.getCanonicalType(T);
 512     Qualifiers Q = T.getQualifiers();
 513     unsigned qVal = 0;
 514     if (Q.hasConst())
 515       qVal |= 0x1;
 516     if (Q.hasVolatile())
 517       qVal |= 0x2;
 518     if (Q.hasRestrict())
 519       qVal |= 0x4;
 520     if(qVal)
 521       Out << ((char) ('0' + qVal));
 522
 523     // Mangle in ObjC GC qualifiers?
 524
 525     if (const PackExpansionType *Expansion = T->getAs<PackExpansionType>()) {
 526       Out << 'P';
 527       T = Expansion->getPattern();
 528     }
 529
 530     if (const BuiltinType *BT = T->getAs<BuiltinType>()) {
 531       unsigned char c = '\0';
 532       switch (BT->getKind()) {
 533         case BuiltinType::Void:
 534           c = 'v'; break;
 535         case BuiltinType::Bool:
 536           c = 'b'; break;
 537         case BuiltinType::Char_U:
 538         case BuiltinType::UChar:
 539           c = 'c'; break;
 540         case BuiltinType::Char16:
 541           c = 'q'; break;
 542         case BuiltinType::Char32:
 543           c = 'w'; break;
 544         case BuiltinType::UShort:
 545           c = 's'; break;
 546         case BuiltinType::UInt:
 547           c = 'i'; break;
 548         case BuiltinType::ULong:
 549           c = 'l'; break;
 550         case BuiltinType::ULongLong:
 551           c = 'k'; break;
 552         case BuiltinType::UInt128:
 553           c = 'j'; break;
 554         case BuiltinType::Char_S:
 555         case BuiltinType::SChar:
 556           c = 'C'; break;
 557         case BuiltinType::WChar_S:
 558         case BuiltinType::WChar_U:
 559           c = 'W'; break;
 560         case BuiltinType::Short:
 561           c = 'S'; break;
 562         case BuiltinType::Int:
 563           c = 'I'; break;
 564         case BuiltinType::Long:
 565           c = 'L'; break;
 566         case BuiltinType::LongLong:
 567           c = 'K'; break;
 568         case BuiltinType::Int128:
 569           c = 'J'; break;
 570         case BuiltinType::Half:
 571           c = 'h'; break;
 572         case BuiltinType::Float:
 573           c = 'f'; break;
 574         case BuiltinType::Double:
 575           c = 'd'; break;
 576         case BuiltinType::LongDouble:
 577           c = 'D'; break;
 578         case BuiltinType::NullPtr:
 579           c = 'n'; break;
 580 #define BUILTIN_TYPE(Id, SingletonId)
 581 #define PLACEHOLDER_TYPE(Id, SingletonId) case BuiltinType::Id:
 582 #include "clang/AST/BuiltinTypes.def"
 583         case BuiltinType::Dependent:
 584         case BuiltinType::OCLImage1d:
 585         case BuiltinType::OCLImage1dArray:
 586         case BuiltinType::OCLImage1dBuffer:
 587         case BuiltinType::OCLImage2d:
 588         case BuiltinType::OCLImage2dArray:
 589         case BuiltinType::OCLImage3d:
 590         case BuiltinType::OCLEvent:
 591         case BuiltinType::OCLSampler:
 592           IgnoreResults = true;
 593           return;
 594         case BuiltinType::ObjCId:
 595           c = 'o'; break;
 596         case BuiltinType::ObjCClass:
 597           c = 'O'; break;
 598         case BuiltinType::ObjCSel:
 599           c = 'e'; break;
 600       }
 601       Out << c;
 602       return;
 603     }
 604
 605     // If we have already seen this (non-built-in) type, use a substitution
 606     // encoding.
 607     llvm::DenseMap<const Type *, unsigned>::iterator Substitution
 608       = TypeSubstitutions.find(T.getTypePtr());
 609     if (Substitution != TypeSubstitutions.end()) {
 610       Out << 'S' << Substitution->second << '_';
 611       return;
 612     } else {
 613       // Record this as a substitution.
 614       unsigned Number = TypeSubstitutions.size();
 615       TypeSubstitutions[T.getTypePtr()] = Number;
 616     }
 617
 618     if (const PointerType *PT = T->getAs<PointerType>()) {
 619       Out << '*';
 620       T = PT->getPointeeType();
 621       continue;
 622     }
 623     if (const ReferenceType *RT = T->getAs<ReferenceType>()) {
 624       Out << '&';
 625       T = RT->getPointeeType();
 626       continue;
 627     }
 628     if (const FunctionProtoType *FT = T->getAs<FunctionProtoType>()) {
 629       Out << 'F';
 630       VisitType(FT->getResultType());
 631       for (FunctionProtoType::arg_type_iterator
 632             I = FT->arg_type_begin(), E = FT->arg_type_end(); I!=E; ++I) {
 633         VisitType(*I);
 634       }
 635       if (FT->isVariadic())
 636         Out << '.';
 637       return;
 638     }
 639     if (const BlockPointerType *BT = T->getAs<BlockPointerType>()) {
 640       Out << 'B';
 641       T = BT->getPointeeType();
 642       continue;
 643     }
 644     if (const ComplexType *CT = T->getAs<ComplexType>()) {
 645       Out << '<';
 646       T = CT->getElementType();
 647       continue;
 648     }
 649     if (const TagType *TT = T->getAs<TagType>()) {
 650       Out << '$';
 651       VisitTagDecl(TT->getDecl());
 652       return;
 653     }
 654     if (const TemplateTypeParmType *TTP = T->getAs<TemplateTypeParmType>()) {
 655       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
 656       return;
 657     }
 658     if (const TemplateSpecializationType *Spec
 659                                     = T->getAs<TemplateSpecializationType>()) {
 660       Out << '>';
 661       VisitTemplateName(Spec->getTemplateName());
 662       Out << Spec->getNumArgs();
 663       for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
 664         VisitTemplateArgument(Spec->getArg(I));
 665       return;
 666     }
 667
 668     // Unhandled type.
 669     Out << ' ';
 670     break;
 671   } while (true);
 672 }
 673
 674 void USRGenerator::VisitTemplateParameterList(
 675                                          const TemplateParameterList *Params) {
 676   if (!Params)
 677     return;
 678   Out << '>' << Params->size();
 679   for (TemplateParameterList::const_iterator P = Params->begin(),
 680                                           PEnd = Params->end();
 681        P != PEnd; ++P) {
 682     Out << '#';
 683     if (isa<TemplateTypeParmDecl>(*P)) {
 684       if (cast<TemplateTypeParmDecl>(*P)->isParameterPack())
 685         Out<< 'p';
 686       Out << 'T';
 687       continue;
 688     }
 689
 690     if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
 691       if (NTTP->isParameterPack())
 692         Out << 'p';
 693       Out << 'N';
 694       VisitType(NTTP->getType());
 695       continue;
 696     }
 697
 698     TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
 699     if (TTP->isParameterPack())
 700       Out << 'p';
 701     Out << 't';
 702     VisitTemplateParameterList(TTP->getTemplateParameters());
 703   }
 704 }
 705
 706 void USRGenerator::VisitTemplateName(TemplateName Name) {
 707   if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
 708     if (TemplateTemplateParmDecl *TTP
 709                               = dyn_cast<TemplateTemplateParmDecl>(Template)) {
 710       Out << 't' << TTP->getDepth() << '.' << TTP->getIndex();
 711       return;
 712     }
 713
 714     Visit(Template);
 715     return;
 716   }
 717
 718   // FIXME: Visit dependent template names.
 719 }
 720
 721 void USRGenerator::VisitTemplateArgument(const TemplateArgument &Arg) {
 722   switch (Arg.getKind()) {
 723   case TemplateArgument::Null:
 724     break;
 725
 726   case TemplateArgument::Declaration:
 727     Visit(Arg.getAsDecl());
 728     break;
 729
 730   case TemplateArgument::NullPtr:
 731     break;
 732
 733   case TemplateArgument::TemplateExpansion:
 734     Out << 'P'; // pack expansion of...
 735     // Fall through
 736   case TemplateArgument::Template:
 737     VisitTemplateName(Arg.getAsTemplateOrTemplatePattern());
 738     break;
 739
 740   case TemplateArgument::Expression:
 741     // FIXME: Visit expressions.
 742     break;
 743
 744   case TemplateArgument::Pack:
 745     Out << 'p' << Arg.pack_size();
 746     for (TemplateArgument::pack_iterator P = Arg.pack_begin(), PEnd = Arg.pack_end();
 747          P != PEnd; ++P)
 748       VisitTemplateArgument(*P);
 749     break;
 750
 751   case TemplateArgument::Type:
 752     VisitType(Arg.getAsType());
 753     break;
 754
 755   case TemplateArgument::Integral:
 756     Out << 'V';
 757     VisitType(Arg.getIntegralType());
 758     Out << Arg.getAsIntegral();
 759     break;
 760   }
 761 }
 762
 763 //===----------------------------------------------------------------------===//
 764 // USR generation functions.
 765 //===----------------------------------------------------------------------===//
 766
 767 void clang::index::generateUSRForObjCClass(StringRef Cls, raw_ostream &OS) {
 768   OS << "objc(cs)" << Cls;
 769 }
 770
 771 void clang::index::generateUSRForObjCCategory(StringRef Cls, StringRef Cat,
 772                                               raw_ostream &OS) {
 773   OS << "objc(cy)" << Cls << '@' << Cat;
 774 }
 775
 776 void clang::index::generateUSRForObjCIvar(StringRef Ivar, raw_ostream &OS) {
 777   OS << '@' << Ivar;
 778 }
 779
 780 void clang::index::generateUSRForObjCMethod(StringRef Sel,
 781                                             bool IsInstanceMethod,
 782                                             raw_ostream &OS) {
 783   OS << (IsInstanceMethod ? "(im)" : "(cm)") << Sel;
 784 }
 785
 786 void clang::index::generateUSRForObjCProperty(StringRef Prop, raw_ostream &OS) {
 787   OS << "(py)" << Prop;
 788 }
 789
 790 void clang::index::generateUSRForObjCProtocol(StringRef Prot, raw_ostream &OS) {
 791   OS << "objc(pl)" << Prot;
 792 }
 793
 794 bool clang::index::generateUSRForDecl(const Decl *D,
 795                                       SmallVectorImpl<char> &Buf) {
 796   // Don't generate USRs for things with invalid locations.
 797   if (!D || D->getLocStart().isInvalid())
 798     return true;
 799
 800   USRGenerator UG(&D->getASTContext(), Buf);
 801   UG.Visit(D);
 802   return UG.ignoreResults();
 803 }