CIndex.cpp revision 76852c218a207ef43583515cb835b6e855353a0f 
1//===- CIndex.cpp - Clang-C Source Indexing Library -----------------------===//
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// This file implements the main API hooks in the Clang-C Source Indexing
11// library.
12//
13//===----------------------------------------------------------------------===//
14
15#include "CIndexer.h"
16#include "CXCursor.h"
17#include "CXTranslationUnit.h"
18#include "CXString.h"
19#include "CXType.h"
20#include "CXSourceLocation.h"
21#include "CIndexDiagnostic.h"
22
23#include "clang/Basic/Version.h"
24
25#include "clang/AST/DeclVisitor.h"
26#include "clang/AST/StmtVisitor.h"
27#include "clang/AST/TypeLocVisitor.h"
28#include "clang/Basic/Diagnostic.h"
29#include "clang/Frontend/ASTUnit.h"
30#include "clang/Frontend/CompilerInstance.h"
31#include "clang/Frontend/FrontendDiagnostic.h"
32#include "clang/Lex/Lexer.h"
33#include "clang/Lex/HeaderSearch.h"
34#include "clang/Lex/PreprocessingRecord.h"
35#include "clang/Lex/Preprocessor.h"
36#include "llvm/ADT/STLExtras.h"
37#include "llvm/ADT/Optional.h"
38#include "llvm/ADT/StringSwitch.h"
39#include "clang/Analysis/Support/SaveAndRestore.h"
40#include "llvm/Support/CrashRecoveryContext.h"
41#include "llvm/Support/PrettyStackTrace.h"
42#include "llvm/Support/MemoryBuffer.h"
43#include "llvm/Support/raw_ostream.h"
44#include "llvm/Support/Timer.h"
45#include "llvm/Support/Mutex.h"
46#include "llvm/Support/Program.h"
47#include "llvm/Support/Signals.h"
48#include "llvm/Support/Threading.h"
49#include "llvm/Support/Compiler.h"
50
51using namespace clang;
52using namespace clang::cxcursor;
53using namespace clang::cxstring;
54using namespace clang::cxtu;
55
56CXTranslationUnit cxtu::MakeCXTranslationUnit(ASTUnit *TU) {
57  if (!TU)
58    return 0;
59  CXTranslationUnit D = new CXTranslationUnitImpl();
60  D->TUData = TU;
61  D->StringPool = createCXStringPool();
62  return D;
63}
64
65cxtu::CXTUOwner::~CXTUOwner() {
66  if (TU)
67    clang_disposeTranslationUnit(TU);
68}
69
70/// \brief The result of comparing two source ranges.
71enum RangeComparisonResult {
72  /// \brief Either the ranges overlap or one of the ranges is invalid.
73  RangeOverlap,
74
75  /// \brief The first range ends before the second range starts.
76  RangeBefore,
77
78  /// \brief The first range starts after the second range ends.
79  RangeAfter
80};
81
82/// \brief Compare two source ranges to determine their relative position in
83/// the translation unit.
84static RangeComparisonResult RangeCompare(SourceManager &SM,
85                                          SourceRange R1,
86                                          SourceRange R2) {
87  assert(R1.isValid() && "First range is invalid?");
88  assert(R2.isValid() && "Second range is invalid?");
89  if (R1.getEnd() != R2.getBegin() &&
90      SM.isBeforeInTranslationUnit(R1.getEnd(), R2.getBegin()))
91    return RangeBefore;
92  if (R2.getEnd() != R1.getBegin() &&
93      SM.isBeforeInTranslationUnit(R2.getEnd(), R1.getBegin()))
94    return RangeAfter;
95  return RangeOverlap;
96}
97
98/// \brief Determine if a source location falls within, before, or after a
99///   a given source range.
100static RangeComparisonResult LocationCompare(SourceManager &SM,
101                                             SourceLocation L, SourceRange R) {
102  assert(R.isValid() && "First range is invalid?");
103  assert(L.isValid() && "Second range is invalid?");
104  if (L == R.getBegin() || L == R.getEnd())
105    return RangeOverlap;
106  if (SM.isBeforeInTranslationUnit(L, R.getBegin()))
107    return RangeBefore;
108  if (SM.isBeforeInTranslationUnit(R.getEnd(), L))
109    return RangeAfter;
110  return RangeOverlap;
111}
112
113/// \brief Translate a Clang source range into a CIndex source range.
114///
115/// Clang internally represents ranges where the end location points to the
116/// start of the token at the end. However, for external clients it is more
117/// useful to have a CXSourceRange be a proper half-open interval. This routine
118/// does the appropriate translation.
119CXSourceRange cxloc::translateSourceRange(const SourceManager &SM,
120                                          const LangOptions &LangOpts,
121                                          const CharSourceRange &R) {
122  // We want the last character in this location, so we will adjust the
123  // location accordingly.
124  SourceLocation EndLoc = R.getEnd();
125  if (EndLoc.isValid() && EndLoc.isMacroID())
126    EndLoc = SM.getExpansionRange(EndLoc).second;
127  if (R.isTokenRange() && !EndLoc.isInvalid() && EndLoc.isFileID()) {
128    unsigned Length = Lexer::MeasureTokenLength(EndLoc, SM, LangOpts);
129    EndLoc = EndLoc.getLocWithOffset(Length);
130  }
131
132  CXSourceRange Result = { { (void *)&SM, (void *)&LangOpts },
133                           R.getBegin().getRawEncoding(),
134                           EndLoc.getRawEncoding() };
135  return Result;
136}
137
138//===----------------------------------------------------------------------===//
139// Cursor visitor.
140//===----------------------------------------------------------------------===//
141
142namespace {
143
144class VisitorJob {
145public:
146  enum Kind { DeclVisitKind, StmtVisitKind, MemberExprPartsKind,
147              TypeLocVisitKind, OverloadExprPartsKind,
148              DeclRefExprPartsKind, LabelRefVisitKind,
149              ExplicitTemplateArgsVisitKind,
150              NestedNameSpecifierLocVisitKind,
151              DeclarationNameInfoVisitKind,
152              MemberRefVisitKind, SizeOfPackExprPartsKind };
153protected:
154  void *data[3];
155  CXCursor parent;
156  Kind K;
157  VisitorJob(CXCursor C, Kind k, void *d1, void *d2 = 0, void *d3 = 0)
158    : parent(C), K(k) {
159    data[0] = d1;
160    data[1] = d2;
161    data[2] = d3;
162  }
163public:
164  Kind getKind() const { return K; }
165  const CXCursor &getParent() const { return parent; }
166  static bool classof(VisitorJob *VJ) { return true; }
167};
168
169typedef SmallVector<VisitorJob, 10> VisitorWorkList;
170
171// Cursor visitor.
172class CursorVisitor : public DeclVisitor<CursorVisitor, bool>,
173                      public TypeLocVisitor<CursorVisitor, bool>
174{
175  /// \brief The translation unit we are traversing.
176  CXTranslationUnit TU;
177  ASTUnit *AU;
178
179  /// \brief The parent cursor whose children we are traversing.
180  CXCursor Parent;
181
182  /// \brief The declaration that serves at the parent of any statement or
183  /// expression nodes.
184  Decl *StmtParent;
185
186  /// \brief The visitor function.
187  CXCursorVisitor Visitor;
188
189  /// \brief The opaque client data, to be passed along to the visitor.
190  CXClientData ClientData;
191
192  /// \brief Whether we should visit the preprocessing record entries last,
193  /// after visiting other declarations.
194  bool VisitPreprocessorLast;
195
196  /// \brief Whether we should visit declarations or preprocessing record
197  /// entries that are #included inside the \arg RegionOfInterest.
198  bool VisitIncludedEntities;
199
200  /// \brief When valid, a source range to which the cursor should restrict
201  /// its search.
202  SourceRange RegionOfInterest;
203
204  // FIXME: Eventually remove.  This part of a hack to support proper
205  // iteration over all Decls contained lexically within an ObjC container.
206  DeclContext::decl_iterator *DI_current;
207  DeclContext::decl_iterator DE_current;
208
209  // Cache of pre-allocated worklists for data-recursion walk of Stmts.
210  SmallVector<VisitorWorkList*, 5> WorkListFreeList;
211  SmallVector<VisitorWorkList*, 5> WorkListCache;
212
213  using DeclVisitor<CursorVisitor, bool>::Visit;
214  using TypeLocVisitor<CursorVisitor, bool>::Visit;
215
216  /// \brief Determine whether this particular source range comes before, comes
217  /// after, or overlaps the region of interest.
218  ///
219  /// \param R a half-open source range retrieved from the abstract syntax tree.
220  RangeComparisonResult CompareRegionOfInterest(SourceRange R);
221
222  class SetParentRAII {
223    CXCursor &Parent;
224    Decl *&StmtParent;
225    CXCursor OldParent;
226
227  public:
228    SetParentRAII(CXCursor &Parent, Decl *&StmtParent, CXCursor NewParent)
229      : Parent(Parent), StmtParent(StmtParent), OldParent(Parent)
230    {
231      Parent = NewParent;
232      if (clang_isDeclaration(Parent.kind))
233        StmtParent = getCursorDecl(Parent);
234    }
235
236    ~SetParentRAII() {
237      Parent = OldParent;
238      if (clang_isDeclaration(Parent.kind))
239        StmtParent = getCursorDecl(Parent);
240    }
241  };
242
243public:
244  CursorVisitor(CXTranslationUnit TU, CXCursorVisitor Visitor,
245                CXClientData ClientData,
246                bool VisitPreprocessorLast,
247                bool VisitIncludedPreprocessingEntries = false,
248                SourceRange RegionOfInterest = SourceRange())
249    : TU(TU), AU(static_cast<ASTUnit*>(TU->TUData)),
250      Visitor(Visitor), ClientData(ClientData),
251      VisitPreprocessorLast(VisitPreprocessorLast),
252      VisitIncludedEntities(VisitIncludedPreprocessingEntries),
253      RegionOfInterest(RegionOfInterest), DI_current(0)
254  {
255    Parent.kind = CXCursor_NoDeclFound;
256    Parent.data[0] = 0;
257    Parent.data[1] = 0;
258    Parent.data[2] = 0;
259    StmtParent = 0;
260  }
261
262  ~CursorVisitor() {
263    // Free the pre-allocated worklists for data-recursion.
264    for (SmallVectorImpl<VisitorWorkList*>::iterator
265          I = WorkListCache.begin(), E = WorkListCache.end(); I != E; ++I) {
266      delete *I;
267    }
268  }
269
270  ASTUnit *getASTUnit() const { return static_cast<ASTUnit*>(TU->TUData); }
271  CXTranslationUnit getTU() const { return TU; }
272
273  bool Visit(CXCursor Cursor, bool CheckedRegionOfInterest = false);
274
275  bool visitPreprocessedEntitiesInRegion();
276
277  bool shouldVisitIncludedEntities() const {
278    return VisitIncludedEntities;
279  }
280
281  template<typename InputIterator>
282  bool visitPreprocessedEntities(InputIterator First, InputIterator Last,
283                                 PreprocessingRecord &PPRec,
284                                 FileID FID = FileID());
285
286  bool VisitChildren(CXCursor Parent);
287
288  // Declaration visitors
289  bool VisitTypeAliasDecl(TypeAliasDecl *D);
290  bool VisitAttributes(Decl *D);
291  bool VisitBlockDecl(BlockDecl *B);
292  bool VisitCXXRecordDecl(CXXRecordDecl *D);
293  llvm::Optional<bool> shouldVisitCursor(CXCursor C);
294  bool VisitDeclContext(DeclContext *DC);
295  bool VisitTranslationUnitDecl(TranslationUnitDecl *D);
296  bool VisitTypedefDecl(TypedefDecl *D);
297  bool VisitTagDecl(TagDecl *D);
298  bool VisitClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *D);
299  bool VisitClassTemplatePartialSpecializationDecl(
300                                     ClassTemplatePartialSpecializationDecl *D);
301  bool VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
302  bool VisitEnumConstantDecl(EnumConstantDecl *D);
303  bool VisitDeclaratorDecl(DeclaratorDecl *DD);
304  bool VisitFunctionDecl(FunctionDecl *ND);
305  bool VisitFieldDecl(FieldDecl *D);
306  bool VisitVarDecl(VarDecl *);
307  bool VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
308  bool VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
309  bool VisitClassTemplateDecl(ClassTemplateDecl *D);
310  bool VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
311  bool VisitObjCMethodDecl(ObjCMethodDecl *ND);
312  bool VisitObjCContainerDecl(ObjCContainerDecl *D);
313  bool VisitObjCCategoryDecl(ObjCCategoryDecl *ND);
314  bool VisitObjCProtocolDecl(ObjCProtocolDecl *PID);
315  bool VisitObjCPropertyDecl(ObjCPropertyDecl *PD);
316  bool VisitObjCInterfaceDecl(ObjCInterfaceDecl *D);
317  bool VisitObjCImplDecl(ObjCImplDecl *D);
318  bool VisitObjCCategoryImplDecl(ObjCCategoryImplDecl *D);
319  bool VisitObjCImplementationDecl(ObjCImplementationDecl *D);
320  // FIXME: ObjCCompatibleAliasDecl requires aliased-class locations.
321  bool VisitObjCForwardProtocolDecl(ObjCForwardProtocolDecl *D);
322  bool VisitObjCClassDecl(ObjCClassDecl *D);
323  bool VisitObjCPropertyImplDecl(ObjCPropertyImplDecl *PD);
324  bool VisitLinkageSpecDecl(LinkageSpecDecl *D);
325  bool VisitNamespaceDecl(NamespaceDecl *D);
326  bool VisitNamespaceAliasDecl(NamespaceAliasDecl *D);
327  bool VisitUsingDirectiveDecl(UsingDirectiveDecl *D);
328  bool VisitUsingDecl(UsingDecl *D);
329  bool VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D);
330  bool VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D);
331
332  // Name visitor
333  bool VisitDeclarationNameInfo(DeclarationNameInfo Name);
334  bool VisitNestedNameSpecifier(NestedNameSpecifier *NNS, SourceRange Range);
335  bool VisitNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
336
337  // Template visitors
338  bool VisitTemplateParameters(const TemplateParameterList *Params);
339  bool VisitTemplateName(TemplateName Name, SourceLocation Loc);
340  bool VisitTemplateArgumentLoc(const TemplateArgumentLoc &TAL);
341
342  // Type visitors
343#define ABSTRACT_TYPELOC(CLASS, PARENT)
344#define TYPELOC(CLASS, PARENT) \
345  bool Visit##CLASS##TypeLoc(CLASS##TypeLoc TyLoc);
346#include "clang/AST/TypeLocNodes.def"
347
348  bool VisitTagTypeLoc(TagTypeLoc TL);
349  bool VisitArrayTypeLoc(ArrayTypeLoc TL);
350  bool VisitFunctionTypeLoc(FunctionTypeLoc TL, bool SkipResultType = false);
351
352  // Data-recursive visitor functions.
353  bool IsInRegionOfInterest(CXCursor C);
354  bool RunVisitorWorkList(VisitorWorkList &WL);
355  void EnqueueWorkList(VisitorWorkList &WL, Stmt *S);
356  LLVM_ATTRIBUTE_NOINLINE bool Visit(Stmt *S);
357};
358
359} // end anonymous namespace
360
361static SourceRange getRawCursorExtent(CXCursor C);
362static SourceRange getFullCursorExtent(CXCursor C, SourceManager &SrcMgr);
363
364
365RangeComparisonResult CursorVisitor::CompareRegionOfInterest(SourceRange R) {
366  return RangeCompare(AU->getSourceManager(), R, RegionOfInterest);
367}
368
369/// \brief Visit the given cursor and, if requested by the visitor,
370/// its children.
371///
372/// \param Cursor the cursor to visit.
373///
374/// \param CheckRegionOfInterest if true, then the caller already checked that
375/// this cursor is within the region of interest.
376///
377/// \returns true if the visitation should be aborted, false if it
378/// should continue.
379bool CursorVisitor::Visit(CXCursor Cursor, bool CheckedRegionOfInterest) {
380  if (clang_isInvalid(Cursor.kind))
381    return false;
382
383  if (clang_isDeclaration(Cursor.kind)) {
384    Decl *D = getCursorDecl(Cursor);
385    assert(D && "Invalid declaration cursor");
386    // Ignore implicit declarations, unless it's an objc method because
387    // currently we should report implicit methods for properties when indexing.
388    if (D->isImplicit() && !isa<ObjCMethodDecl>(D))
389      return false;
390  }
391
392  // If we have a range of interest, and this cursor doesn't intersect with it,
393  // we're done.
394  if (RegionOfInterest.isValid() && !CheckedRegionOfInterest) {
395    SourceRange Range = getRawCursorExtent(Cursor);
396    if (Range.isInvalid() || CompareRegionOfInterest(Range))
397      return false;
398  }
399
400  switch (Visitor(Cursor, Parent, ClientData)) {
401  case CXChildVisit_Break:
402    return true;
403
404  case CXChildVisit_Continue:
405    return false;
406
407  case CXChildVisit_Recurse:
408    return VisitChildren(Cursor);
409  }
410
411  return false;
412}
413
414static bool visitPreprocessedEntitiesInRange(SourceRange R,
415                                             PreprocessingRecord &PPRec,
416                                             CursorVisitor &Visitor) {
417  SourceManager &SM = Visitor.getASTUnit()->getSourceManager();
418  FileID FID;
419
420  if (!Visitor.shouldVisitIncludedEntities()) {
421    // If the begin/end of the range lie in the same FileID, do the optimization
422    // where we skip preprocessed entities that do not come from the same FileID.
423    FID = SM.getFileID(R.getBegin());
424    if (FID != SM.getFileID(R.getEnd()))
425      FID = FileID();
426  }
427
428  std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
429    Entities = PPRec.getPreprocessedEntitiesInRange(R);
430  return Visitor.visitPreprocessedEntities(Entities.first, Entities.second,
431                                           PPRec, FID);
432}
433
434bool CursorVisitor::visitPreprocessedEntitiesInRegion() {
435  PreprocessingRecord &PPRec
436    = *AU->getPreprocessor().getPreprocessingRecord();
437  SourceManager &SM = AU->getSourceManager();
438
439  if (RegionOfInterest.isValid()) {
440    SourceRange MappedRange = AU->mapRangeToPreamble(RegionOfInterest);
441    SourceLocation B = MappedRange.getBegin();
442    SourceLocation E = MappedRange.getEnd();
443
444    if (AU->isInPreambleFileID(B)) {
445      if (SM.isLoadedSourceLocation(E))
446        return visitPreprocessedEntitiesInRange(SourceRange(B, E),
447                                                 PPRec, *this);
448
449      // Beginning of range lies in the preamble but it also extends beyond
450      // it into the main file. Split the range into 2 parts, one covering
451      // the preamble and another covering the main file. This allows subsequent
452      // calls to visitPreprocessedEntitiesInRange to accept a source range that
453      // lies in the same FileID, allowing it to skip preprocessed entities that
454      // do not come from the same FileID.
455      bool breaked =
456        visitPreprocessedEntitiesInRange(
457                                   SourceRange(B, AU->getEndOfPreambleFileID()),
458                                          PPRec, *this);
459      if (breaked) return true;
460      return visitPreprocessedEntitiesInRange(
461                                    SourceRange(AU->getStartOfMainFileID(), E),
462                                        PPRec, *this);
463    }
464
465    return visitPreprocessedEntitiesInRange(SourceRange(B, E), PPRec, *this);
466  }
467
468  bool OnlyLocalDecls
469    = !AU->isMainFileAST() && AU->getOnlyLocalDecls();
470
471  if (OnlyLocalDecls)
472    return visitPreprocessedEntities(PPRec.local_begin(), PPRec.local_end(),
473                                     PPRec);
474
475  return visitPreprocessedEntities(PPRec.begin(), PPRec.end(), PPRec);
476}
477
478template<typename InputIterator>
479bool CursorVisitor::visitPreprocessedEntities(InputIterator First,
480                                              InputIterator Last,
481                                              PreprocessingRecord &PPRec,
482                                              FileID FID) {
483  for (; First != Last; ++First) {
484    if (!FID.isInvalid() && !PPRec.isEntityInFileID(First, FID))
485      continue;
486
487    PreprocessedEntity *PPE = *First;
488    if (MacroExpansion *ME = dyn_cast<MacroExpansion>(PPE)) {
489      if (Visit(MakeMacroExpansionCursor(ME, TU)))
490        return true;
491
492      continue;
493    }
494
495    if (MacroDefinition *MD = dyn_cast<MacroDefinition>(PPE)) {
496      if (Visit(MakeMacroDefinitionCursor(MD, TU)))
497        return true;
498
499      continue;
500    }
501
502    if (InclusionDirective *ID = dyn_cast<InclusionDirective>(PPE)) {
503      if (Visit(MakeInclusionDirectiveCursor(ID, TU)))
504        return true;
505
506      continue;
507    }
508  }
509
510  return false;
511}
512
513/// \brief Visit the children of the given cursor.
514///
515/// \returns true if the visitation should be aborted, false if it
516/// should continue.
517bool CursorVisitor::VisitChildren(CXCursor Cursor) {
518  if (clang_isReference(Cursor.kind) &&
519      Cursor.kind != CXCursor_CXXBaseSpecifier) {
520    // By definition, references have no children.
521    return false;
522  }
523
524  // Set the Parent field to Cursor, then back to its old value once we're
525  // done.
526  SetParentRAII SetParent(Parent, StmtParent, Cursor);
527
528  if (clang_isDeclaration(Cursor.kind)) {
529    Decl *D = getCursorDecl(Cursor);
530    if (!D)
531      return false;
532
533    return VisitAttributes(D) || Visit(D);
534  }
535
536  if (clang_isStatement(Cursor.kind)) {
537    if (Stmt *S = getCursorStmt(Cursor))
538      return Visit(S);
539
540    return false;
541  }
542
543  if (clang_isExpression(Cursor.kind)) {
544    if (Expr *E = getCursorExpr(Cursor))
545      return Visit(E);
546
547    return false;
548  }
549
550  if (clang_isTranslationUnit(Cursor.kind)) {
551    CXTranslationUnit tu = getCursorTU(Cursor);
552    ASTUnit *CXXUnit = static_cast<ASTUnit*>(tu->TUData);
553
554    int VisitOrder[2] = { VisitPreprocessorLast, !VisitPreprocessorLast };
555    for (unsigned I = 0; I != 2; ++I) {
556      if (VisitOrder[I]) {
557        if (!CXXUnit->isMainFileAST() && CXXUnit->getOnlyLocalDecls() &&
558            RegionOfInterest.isInvalid()) {
559          for (ASTUnit::top_level_iterator TL = CXXUnit->top_level_begin(),
560                                        TLEnd = CXXUnit->top_level_end();
561               TL != TLEnd; ++TL) {
562            if (Visit(MakeCXCursor(*TL, tu, RegionOfInterest), true))
563              return true;
564          }
565        } else if (VisitDeclContext(
566                                CXXUnit->getASTContext().getTranslationUnitDecl()))
567          return true;
568        continue;
569      }
570
571      // Walk the preprocessing record.
572      if (CXXUnit->getPreprocessor().getPreprocessingRecord())
573        visitPreprocessedEntitiesInRegion();
574    }
575
576    return false;
577  }
578
579  if (Cursor.kind == CXCursor_CXXBaseSpecifier) {
580    if (CXXBaseSpecifier *Base = getCursorCXXBaseSpecifier(Cursor)) {
581      if (TypeSourceInfo *BaseTSInfo = Base->getTypeSourceInfo()) {
582        return Visit(BaseTSInfo->getTypeLoc());
583      }
584    }
585  }
586
587  if (Cursor.kind == CXCursor_IBOutletCollectionAttr) {
588    IBOutletCollectionAttr *A =
589      cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(Cursor));
590    if (const ObjCInterfaceType *InterT = A->getInterface()->getAs<ObjCInterfaceType>())
591      return Visit(cxcursor::MakeCursorObjCClassRef(InterT->getInterface(),
592                                                    A->getInterfaceLoc(), TU));
593  }
594
595  // Nothing to visit at the moment.
596  return false;
597}
598
599bool CursorVisitor::VisitBlockDecl(BlockDecl *B) {
600  if (TypeSourceInfo *TSInfo = B->getSignatureAsWritten())
601    if (Visit(TSInfo->getTypeLoc()))
602        return true;
603
604  if (Stmt *Body = B->getBody())
605    return Visit(MakeCXCursor(Body, StmtParent, TU, RegionOfInterest));
606
607  return false;
608}
609
610llvm::Optional<bool> CursorVisitor::shouldVisitCursor(CXCursor Cursor) {
611  if (RegionOfInterest.isValid()) {
612    SourceRange Range = getFullCursorExtent(Cursor, AU->getSourceManager());
613    if (Range.isInvalid())
614      return llvm::Optional<bool>();
615
616    switch (CompareRegionOfInterest(Range)) {
617    case RangeBefore:
618      // This declaration comes before the region of interest; skip it.
619      return llvm::Optional<bool>();
620
621    case RangeAfter:
622      // This declaration comes after the region of interest; we're done.
623      return false;
624
625    case RangeOverlap:
626      // This declaration overlaps the region of interest; visit it.
627      break;
628    }
629  }
630  return true;
631}
632
633bool CursorVisitor::VisitDeclContext(DeclContext *DC) {
634  DeclContext::decl_iterator I = DC->decls_begin(), E = DC->decls_end();
635
636  // FIXME: Eventually remove.  This part of a hack to support proper
637  // iteration over all Decls contained lexically within an ObjC container.
638  SaveAndRestore<DeclContext::decl_iterator*> DI_saved(DI_current, &I);
639  SaveAndRestore<DeclContext::decl_iterator> DE_saved(DE_current, E);
640
641  for ( ; I != E; ++I) {
642    Decl *D = *I;
643    if (D->getLexicalDeclContext() != DC)
644      continue;
645    CXCursor Cursor = MakeCXCursor(D, TU, RegionOfInterest);
646    const llvm::Optional<bool> &V = shouldVisitCursor(Cursor);
647    if (!V.hasValue())
648      continue;
649    if (!V.getValue())
650      return false;
651    if (Visit(Cursor, true))
652      return true;
653  }
654  return false;
655}
656
657bool CursorVisitor::VisitTranslationUnitDecl(TranslationUnitDecl *D) {
658  llvm_unreachable("Translation units are visited directly by Visit()");
659  return false;
660}
661
662bool CursorVisitor::VisitTypeAliasDecl(TypeAliasDecl *D) {
663  if (TypeSourceInfo *TSInfo = D->getTypeSourceInfo())
664    return Visit(TSInfo->getTypeLoc());
665
666  return false;
667}
668
669bool CursorVisitor::VisitTypedefDecl(TypedefDecl *D) {
670  if (TypeSourceInfo *TSInfo = D->getTypeSourceInfo())
671    return Visit(TSInfo->getTypeLoc());
672
673  return false;
674}
675
676bool CursorVisitor::VisitTagDecl(TagDecl *D) {
677  return VisitDeclContext(D);
678}
679
680bool CursorVisitor::VisitClassTemplateSpecializationDecl(
681                                          ClassTemplateSpecializationDecl *D) {
682  bool ShouldVisitBody = false;
683  switch (D->getSpecializationKind()) {
684  case TSK_Undeclared:
685  case TSK_ImplicitInstantiation:
686    // Nothing to visit
687    return false;
688
689  case TSK_ExplicitInstantiationDeclaration:
690  case TSK_ExplicitInstantiationDefinition:
691    break;
692
693  case TSK_ExplicitSpecialization:
694    ShouldVisitBody = true;
695    break;
696  }
697
698  // Visit the template arguments used in the specialization.
699  if (TypeSourceInfo *SpecType = D->getTypeAsWritten()) {
700    TypeLoc TL = SpecType->getTypeLoc();
701    if (TemplateSpecializationTypeLoc *TSTLoc
702          = dyn_cast<TemplateSpecializationTypeLoc>(&TL)) {
703      for (unsigned I = 0, N = TSTLoc->getNumArgs(); I != N; ++I)
704        if (VisitTemplateArgumentLoc(TSTLoc->getArgLoc(I)))
705          return true;
706    }
707  }
708
709  if (ShouldVisitBody && VisitCXXRecordDecl(D))
710    return true;
711
712  return false;
713}
714
715bool CursorVisitor::VisitClassTemplatePartialSpecializationDecl(
716                                   ClassTemplatePartialSpecializationDecl *D) {
717  // FIXME: Visit the "outer" template parameter lists on the TagDecl
718  // before visiting these template parameters.
719  if (VisitTemplateParameters(D->getTemplateParameters()))
720    return true;
721
722  // Visit the partial specialization arguments.
723  const TemplateArgumentLoc *TemplateArgs = D->getTemplateArgsAsWritten();
724  for (unsigned I = 0, N = D->getNumTemplateArgsAsWritten(); I != N; ++I)
725    if (VisitTemplateArgumentLoc(TemplateArgs[I]))
726      return true;
727
728  return VisitCXXRecordDecl(D);
729}
730
731bool CursorVisitor::VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D) {
732  // Visit the default argument.
733  if (D->hasDefaultArgument() && !D->defaultArgumentWasInherited())
734    if (TypeSourceInfo *DefArg = D->getDefaultArgumentInfo())
735      if (Visit(DefArg->getTypeLoc()))
736        return true;
737
738  return false;
739}
740
741bool CursorVisitor::VisitEnumConstantDecl(EnumConstantDecl *D) {
742  if (Expr *Init = D->getInitExpr())
743    return Visit(MakeCXCursor(Init, StmtParent, TU, RegionOfInterest));
744  return false;
745}
746
747bool CursorVisitor::VisitDeclaratorDecl(DeclaratorDecl *DD) {
748  if (TypeSourceInfo *TSInfo = DD->getTypeSourceInfo())
749    if (Visit(TSInfo->getTypeLoc()))
750      return true;
751
752  // Visit the nested-name-specifier, if present.
753  if (NestedNameSpecifierLoc QualifierLoc = DD->getQualifierLoc())
754    if (VisitNestedNameSpecifierLoc(QualifierLoc))
755      return true;
756
757  return false;
758}
759
760/// \brief Compare two base or member initializers based on their source order.
761static int CompareCXXCtorInitializers(const void* Xp, const void *Yp) {
762  CXXCtorInitializer const * const *X
763    = static_cast<CXXCtorInitializer const * const *>(Xp);
764  CXXCtorInitializer const * const *Y
765    = static_cast<CXXCtorInitializer const * const *>(Yp);
766
767  if ((*X)->getSourceOrder() < (*Y)->getSourceOrder())
768    return -1;
769  else if ((*X)->getSourceOrder() > (*Y)->getSourceOrder())
770    return 1;
771  else
772    return 0;
773}
774
775bool CursorVisitor::VisitFunctionDecl(FunctionDecl *ND) {
776  if (TypeSourceInfo *TSInfo = ND->getTypeSourceInfo()) {
777    // Visit the function declaration's syntactic components in the order
778    // written. This requires a bit of work.
779    TypeLoc TL = TSInfo->getTypeLoc().IgnoreParens();
780    FunctionTypeLoc *FTL = dyn_cast<FunctionTypeLoc>(&TL);
781
782    // If we have a function declared directly (without the use of a typedef),
783    // visit just the return type. Otherwise, just visit the function's type
784    // now.
785    if ((FTL && !isa<CXXConversionDecl>(ND) && Visit(FTL->getResultLoc())) ||
786        (!FTL && Visit(TL)))
787      return true;
788
789    // Visit the nested-name-specifier, if present.
790    if (NestedNameSpecifierLoc QualifierLoc = ND->getQualifierLoc())
791      if (VisitNestedNameSpecifierLoc(QualifierLoc))
792        return true;
793
794    // Visit the declaration name.
795    if (VisitDeclarationNameInfo(ND->getNameInfo()))
796      return true;
797
798    // FIXME: Visit explicitly-specified template arguments!
799
800    // Visit the function parameters, if we have a function type.
801    if (FTL && VisitFunctionTypeLoc(*FTL, true))
802      return true;
803
804    // FIXME: Attributes?
805  }
806
807  if (ND->doesThisDeclarationHaveABody() && !ND->isLateTemplateParsed()) {
808    if (CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(ND)) {
809      // Find the initializers that were written in the source.
810      SmallVector<CXXCtorInitializer *, 4> WrittenInits;
811      for (CXXConstructorDecl::init_iterator I = Constructor->init_begin(),
812                                          IEnd = Constructor->init_end();
813           I != IEnd; ++I) {
814        if (!(*I)->isWritten())
815          continue;
816
817        WrittenInits.push_back(*I);
818      }
819
820      // Sort the initializers in source order
821      llvm::array_pod_sort(WrittenInits.begin(), WrittenInits.end(),
822                           &CompareCXXCtorInitializers);
823
824      // Visit the initializers in source order
825      for (unsigned I = 0, N = WrittenInits.size(); I != N; ++I) {
826        CXXCtorInitializer *Init = WrittenInits[I];
827        if (Init->isAnyMemberInitializer()) {
828          if (Visit(MakeCursorMemberRef(Init->getAnyMember(),
829                                        Init->getMemberLocation(), TU)))
830            return true;
831        } else if (TypeSourceInfo *TInfo = Init->getTypeSourceInfo()) {
832          if (Visit(TInfo->getTypeLoc()))
833            return true;
834        }
835
836        // Visit the initializer value.
837        if (Expr *Initializer = Init->getInit())
838          if (Visit(MakeCXCursor(Initializer, ND, TU, RegionOfInterest)))
839            return true;
840      }
841    }
842
843    if (Visit(MakeCXCursor(ND->getBody(), StmtParent, TU, RegionOfInterest)))
844      return true;
845  }
846
847  return false;
848}
849
850bool CursorVisitor::VisitFieldDecl(FieldDecl *D) {
851  if (VisitDeclaratorDecl(D))
852    return true;
853
854  if (Expr *BitWidth = D->getBitWidth())
855    return Visit(MakeCXCursor(BitWidth, StmtParent, TU, RegionOfInterest));
856
857  return false;
858}
859
860bool CursorVisitor::VisitVarDecl(VarDecl *D) {
861  if (VisitDeclaratorDecl(D))
862    return true;
863
864  if (Expr *Init = D->getInit())
865    return Visit(MakeCXCursor(Init, StmtParent, TU, RegionOfInterest));
866
867  return false;
868}
869
870bool CursorVisitor::VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D) {
871  if (VisitDeclaratorDecl(D))
872    return true;
873
874  if (D->hasDefaultArgument() && !D->defaultArgumentWasInherited())
875    if (Expr *DefArg = D->getDefaultArgument())
876      return Visit(MakeCXCursor(DefArg, StmtParent, TU, RegionOfInterest));
877
878  return false;
879}
880
881bool CursorVisitor::VisitFunctionTemplateDecl(FunctionTemplateDecl *D) {
882  // FIXME: Visit the "outer" template parameter lists on the FunctionDecl
883  // before visiting these template parameters.
884  if (VisitTemplateParameters(D->getTemplateParameters()))
885    return true;
886
887  return VisitFunctionDecl(D->getTemplatedDecl());
888}
889
890bool CursorVisitor::VisitClassTemplateDecl(ClassTemplateDecl *D) {
891  // FIXME: Visit the "outer" template parameter lists on the TagDecl
892  // before visiting these template parameters.
893  if (VisitTemplateParameters(D->getTemplateParameters()))
894    return true;
895
896  return VisitCXXRecordDecl(D->getTemplatedDecl());
897}
898
899bool CursorVisitor::VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D) {
900  if (VisitTemplateParameters(D->getTemplateParameters()))
901    return true;
902
903  if (D->hasDefaultArgument() && !D->defaultArgumentWasInherited() &&
904      VisitTemplateArgumentLoc(D->getDefaultArgument()))
905    return true;
906
907  return false;
908}
909
910bool CursorVisitor::VisitObjCMethodDecl(ObjCMethodDecl *ND) {
911  if (TypeSourceInfo *TSInfo = ND->getResultTypeSourceInfo())
912    if (Visit(TSInfo->getTypeLoc()))
913      return true;
914
915  for (ObjCMethodDecl::param_iterator P = ND->param_begin(),
916       PEnd = ND->param_end();
917       P != PEnd; ++P) {
918    if (Visit(MakeCXCursor(*P, TU, RegionOfInterest)))
919      return true;
920  }
921
922  if (ND->isThisDeclarationADefinition() &&
923      Visit(MakeCXCursor(ND->getBody(), StmtParent, TU, RegionOfInterest)))
924    return true;
925
926  return false;
927}
928
929namespace {
930  struct ContainerDeclsSort {
931    SourceManager &SM;
932    ContainerDeclsSort(SourceManager &sm) : SM(sm) {}
933    bool operator()(Decl *A, Decl *B) {
934      SourceLocation L_A = A->getLocStart();
935      SourceLocation L_B = B->getLocStart();
936      assert(L_A.isValid() && L_B.isValid());
937      return SM.isBeforeInTranslationUnit(L_A, L_B);
938    }
939  };
940}
941
942bool CursorVisitor::VisitObjCContainerDecl(ObjCContainerDecl *D) {
943  // FIXME: Eventually convert back to just 'VisitDeclContext()'.  Essentially
944  // an @implementation can lexically contain Decls that are not properly
945  // nested in the AST.  When we identify such cases, we need to retrofit
946  // this nesting here.
947  if (!DI_current)
948    return VisitDeclContext(D);
949
950  // Scan the Decls that immediately come after the container
951  // in the current DeclContext.  If any fall within the
952  // container's lexical region, stash them into a vector
953  // for later processing.
954  SmallVector<Decl *, 24> DeclsInContainer;
955  SourceLocation EndLoc = D->getSourceRange().getEnd();
956  SourceManager &SM = AU->getSourceManager();
957  if (EndLoc.isValid()) {
958    DeclContext::decl_iterator next = *DI_current;
959    while (++next != DE_current) {
960      Decl *D_next = *next;
961      if (!D_next)
962        break;
963      SourceLocation L = D_next->getLocStart();
964      if (!L.isValid())
965        break;
966      if (SM.isBeforeInTranslationUnit(L, EndLoc)) {
967        *DI_current = next;
968        DeclsInContainer.push_back(D_next);
969        continue;
970      }
971      break;
972    }
973  }
974
975  // The common case.
976  if (DeclsInContainer.empty())
977    return VisitDeclContext(D);
978
979  // Get all the Decls in the DeclContext, and sort them with the
980  // additional ones we've collected.  Then visit them.
981  for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end();
982       I!=E; ++I) {
983    Decl *subDecl = *I;
984    if (!subDecl || subDecl->getLexicalDeclContext() != D ||
985        subDecl->getLocStart().isInvalid())
986      continue;
987    DeclsInContainer.push_back(subDecl);
988  }
989
990  // Now sort the Decls so that they appear in lexical order.
991  std::sort(DeclsInContainer.begin(), DeclsInContainer.end(),
992            ContainerDeclsSort(SM));
993
994  // Now visit the decls.
995  for (SmallVectorImpl<Decl*>::iterator I = DeclsInContainer.begin(),
996         E = DeclsInContainer.end(); I != E; ++I) {
997    CXCursor Cursor = MakeCXCursor(*I, TU, RegionOfInterest);
998    const llvm::Optional<bool> &V = shouldVisitCursor(Cursor);
999    if (!V.hasValue())
1000      continue;
1001    if (!V.getValue())
1002      return false;
1003    if (Visit(Cursor, true))
1004      return true;
1005  }
1006  return false;
1007}
1008
1009bool CursorVisitor::VisitObjCCategoryDecl(ObjCCategoryDecl *ND) {
1010  if (Visit(MakeCursorObjCClassRef(ND->getClassInterface(), ND->getLocation(),
1011                                   TU)))
1012    return true;
1013
1014  ObjCCategoryDecl::protocol_loc_iterator PL = ND->protocol_loc_begin();
1015  for (ObjCCategoryDecl::protocol_iterator I = ND->protocol_begin(),
1016         E = ND->protocol_end(); I != E; ++I, ++PL)
1017    if (Visit(MakeCursorObjCProtocolRef(*I, *PL, TU)))
1018      return true;
1019
1020  return VisitObjCContainerDecl(ND);
1021}
1022
1023bool CursorVisitor::VisitObjCProtocolDecl(ObjCProtocolDecl *PID) {
1024  ObjCProtocolDecl::protocol_loc_iterator PL = PID->protocol_loc_begin();
1025  for (ObjCProtocolDecl::protocol_iterator I = PID->protocol_begin(),
1026       E = PID->protocol_end(); I != E; ++I, ++PL)
1027    if (Visit(MakeCursorObjCProtocolRef(*I, *PL, TU)))
1028      return true;
1029
1030  return VisitObjCContainerDecl(PID);
1031}
1032
1033bool CursorVisitor::VisitObjCPropertyDecl(ObjCPropertyDecl *PD) {
1034  if (PD->getTypeSourceInfo() && Visit(PD->getTypeSourceInfo()->getTypeLoc()))
1035    return true;
1036
1037  // FIXME: This implements a workaround with @property declarations also being
1038  // installed in the DeclContext for the @interface.  Eventually this code
1039  // should be removed.
1040  ObjCCategoryDecl *CDecl = dyn_cast<ObjCCategoryDecl>(PD->getDeclContext());
1041  if (!CDecl || !CDecl->IsClassExtension())
1042    return false;
1043
1044  ObjCInterfaceDecl *ID = CDecl->getClassInterface();
1045  if (!ID)
1046    return false;
1047
1048  IdentifierInfo *PropertyId = PD->getIdentifier();
1049  ObjCPropertyDecl *prevDecl =
1050    ObjCPropertyDecl::findPropertyDecl(cast<DeclContext>(ID), PropertyId);
1051
1052  if (!prevDecl)
1053    return false;
1054
1055  // Visit synthesized methods since they will be skipped when visiting
1056  // the @interface.
1057  if (ObjCMethodDecl *MD = prevDecl->getGetterMethodDecl())
1058    if (MD->isSynthesized() && MD->getLexicalDeclContext() == CDecl)
1059      if (Visit(MakeCXCursor(MD, TU, RegionOfInterest)))
1060        return true;
1061
1062  if (ObjCMethodDecl *MD = prevDecl->getSetterMethodDecl())
1063    if (MD->isSynthesized() && MD->getLexicalDeclContext() == CDecl)
1064      if (Visit(MakeCXCursor(MD, TU, RegionOfInterest)))
1065        return true;
1066
1067  return false;
1068}
1069
1070bool CursorVisitor::VisitObjCInterfaceDecl(ObjCInterfaceDecl *D) {
1071  // Issue callbacks for super class.
1072  if (D->getSuperClass() &&
1073      Visit(MakeCursorObjCSuperClassRef(D->getSuperClass(),
1074                                        D->getSuperClassLoc(),
1075                                        TU)))
1076    return true;
1077
1078  ObjCInterfaceDecl::protocol_loc_iterator PL = D->protocol_loc_begin();
1079  for (ObjCInterfaceDecl::protocol_iterator I = D->protocol_begin(),
1080         E = D->protocol_end(); I != E; ++I, ++PL)
1081    if (Visit(MakeCursorObjCProtocolRef(*I, *PL, TU)))
1082      return true;
1083
1084  return VisitObjCContainerDecl(D);
1085}
1086
1087bool CursorVisitor::VisitObjCImplDecl(ObjCImplDecl *D) {
1088  return VisitObjCContainerDecl(D);
1089}
1090
1091bool CursorVisitor::VisitObjCCategoryImplDecl(ObjCCategoryImplDecl *D) {
1092  // 'ID' could be null when dealing with invalid code.
1093  if (ObjCInterfaceDecl *ID = D->getClassInterface())
1094    if (Visit(MakeCursorObjCClassRef(ID, D->getLocation(), TU)))
1095      return true;
1096
1097  return VisitObjCImplDecl(D);
1098}
1099
1100bool CursorVisitor::VisitObjCImplementationDecl(ObjCImplementationDecl *D) {
1101#if 0
1102  // Issue callbacks for super class.
1103  // FIXME: No source location information!
1104  if (D->getSuperClass() &&
1105      Visit(MakeCursorObjCSuperClassRef(D->getSuperClass(),
1106                                        D->getSuperClassLoc(),
1107                                        TU)))
1108    return true;
1109#endif
1110
1111  return VisitObjCImplDecl(D);
1112}
1113
1114bool CursorVisitor::VisitObjCForwardProtocolDecl(ObjCForwardProtocolDecl *D) {
1115  ObjCForwardProtocolDecl::protocol_loc_iterator PL = D->protocol_loc_begin();
1116  for (ObjCForwardProtocolDecl::protocol_iterator I = D->protocol_begin(),
1117                                                  E = D->protocol_end();
1118       I != E; ++I, ++PL)
1119    if (Visit(MakeCursorObjCProtocolRef(*I, *PL, TU)))
1120      return true;
1121
1122  return false;
1123}
1124
1125bool CursorVisitor::VisitObjCClassDecl(ObjCClassDecl *D) {
1126  if (Visit(MakeCursorObjCClassRef(D->getForwardInterfaceDecl(),
1127                                   D->getForwardDecl()->getLocation(), TU)))
1128      return true;
1129  return false;
1130}
1131
1132bool CursorVisitor::VisitObjCPropertyImplDecl(ObjCPropertyImplDecl *PD) {
1133  if (ObjCIvarDecl *Ivar = PD->getPropertyIvarDecl())
1134    return Visit(MakeCursorMemberRef(Ivar, PD->getPropertyIvarDeclLoc(), TU));
1135
1136  return false;
1137}
1138
1139bool CursorVisitor::VisitNamespaceDecl(NamespaceDecl *D) {
1140  return VisitDeclContext(D);
1141}
1142
1143bool CursorVisitor::VisitNamespaceAliasDecl(NamespaceAliasDecl *D) {
1144  // Visit nested-name-specifier.
1145  if (NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc())
1146    if (VisitNestedNameSpecifierLoc(QualifierLoc))
1147      return true;
1148
1149  return Visit(MakeCursorNamespaceRef(D->getAliasedNamespace(),
1150                                      D->getTargetNameLoc(), TU));
1151}
1152
1153bool CursorVisitor::VisitUsingDecl(UsingDecl *D) {
1154  // Visit nested-name-specifier.
1155  if (NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc()) {
1156    if (VisitNestedNameSpecifierLoc(QualifierLoc))
1157      return true;
1158  }
1159
1160  if (Visit(MakeCursorOverloadedDeclRef(D, D->getLocation(), TU)))
1161    return true;
1162
1163  return VisitDeclarationNameInfo(D->getNameInfo());
1164}
1165
1166bool CursorVisitor::VisitUsingDirectiveDecl(UsingDirectiveDecl *D) {
1167  // Visit nested-name-specifier.
1168  if (NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc())
1169    if (VisitNestedNameSpecifierLoc(QualifierLoc))
1170      return true;
1171
1172  return Visit(MakeCursorNamespaceRef(D->getNominatedNamespaceAsWritten(),
1173                                      D->getIdentLocation(), TU));
1174}
1175
1176bool CursorVisitor::VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D) {
1177  // Visit nested-name-specifier.
1178  if (NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc()) {
1179    if (VisitNestedNameSpecifierLoc(QualifierLoc))
1180      return true;
1181  }
1182
1183  return VisitDeclarationNameInfo(D->getNameInfo());
1184}
1185
1186bool CursorVisitor::VisitUnresolvedUsingTypenameDecl(
1187                                               UnresolvedUsingTypenameDecl *D) {
1188  // Visit nested-name-specifier.
1189  if (NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc())
1190    if (VisitNestedNameSpecifierLoc(QualifierLoc))
1191      return true;
1192
1193  return false;
1194}
1195
1196bool CursorVisitor::VisitDeclarationNameInfo(DeclarationNameInfo Name) {
1197  switch (Name.getName().getNameKind()) {
1198  case clang::DeclarationName::Identifier:
1199  case clang::DeclarationName::CXXLiteralOperatorName:
1200  case clang::DeclarationName::CXXOperatorName:
1201  case clang::DeclarationName::CXXUsingDirective:
1202    return false;
1203
1204  case clang::DeclarationName::CXXConstructorName:
1205  case clang::DeclarationName::CXXDestructorName:
1206  case clang::DeclarationName::CXXConversionFunctionName:
1207    if (TypeSourceInfo *TSInfo = Name.getNamedTypeInfo())
1208      return Visit(TSInfo->getTypeLoc());
1209    return false;
1210
1211  case clang::DeclarationName::ObjCZeroArgSelector:
1212  case clang::DeclarationName::ObjCOneArgSelector:
1213  case clang::DeclarationName::ObjCMultiArgSelector:
1214    // FIXME: Per-identifier location info?
1215    return false;
1216  }
1217
1218  return false;
1219}
1220
1221bool CursorVisitor::VisitNestedNameSpecifier(NestedNameSpecifier *NNS,
1222                                             SourceRange Range) {
1223  // FIXME: This whole routine is a hack to work around the lack of proper
1224  // source information in nested-name-specifiers (PR5791). Since we do have
1225  // a beginning source location, we can visit the first component of the
1226  // nested-name-specifier, if it's a single-token component.
1227  if (!NNS)
1228    return false;
1229
1230  // Get the first component in the nested-name-specifier.
1231  while (NestedNameSpecifier *Prefix = NNS->getPrefix())
1232    NNS = Prefix;
1233
1234  switch (NNS->getKind()) {
1235  case NestedNameSpecifier::Namespace:
1236    return Visit(MakeCursorNamespaceRef(NNS->getAsNamespace(), Range.getBegin(),
1237                                        TU));
1238
1239  case NestedNameSpecifier::NamespaceAlias:
1240    return Visit(MakeCursorNamespaceRef(NNS->getAsNamespaceAlias(),
1241                                        Range.getBegin(), TU));
1242
1243  case NestedNameSpecifier::TypeSpec: {
1244    // If the type has a form where we know that the beginning of the source
1245    // range matches up with a reference cursor. Visit the appropriate reference
1246    // cursor.
1247    const Type *T = NNS->getAsType();
1248    if (const TypedefType *Typedef = dyn_cast<TypedefType>(T))
1249      return Visit(MakeCursorTypeRef(Typedef->getDecl(), Range.getBegin(), TU));
1250    if (const TagType *Tag = dyn_cast<TagType>(T))
1251      return Visit(MakeCursorTypeRef(Tag->getDecl(), Range.getBegin(), TU));
1252    if (const TemplateSpecializationType *TST
1253                                      = dyn_cast<TemplateSpecializationType>(T))
1254      return VisitTemplateName(TST->getTemplateName(), Range.getBegin());
1255    break;
1256  }
1257
1258  case NestedNameSpecifier::TypeSpecWithTemplate:
1259  case NestedNameSpecifier::Global:
1260  case NestedNameSpecifier::Identifier:
1261    break;
1262  }
1263
1264  return false;
1265}
1266
1267bool
1268CursorVisitor::VisitNestedNameSpecifierLoc(NestedNameSpecifierLoc Qualifier) {
1269  SmallVector<NestedNameSpecifierLoc, 4> Qualifiers;
1270  for (; Qualifier; Qualifier = Qualifier.getPrefix())
1271    Qualifiers.push_back(Qualifier);
1272
1273  while (!Qualifiers.empty()) {
1274    NestedNameSpecifierLoc Q = Qualifiers.pop_back_val();
1275    NestedNameSpecifier *NNS = Q.getNestedNameSpecifier();
1276    switch (NNS->getKind()) {
1277    case NestedNameSpecifier::Namespace:
1278      if (Visit(MakeCursorNamespaceRef(NNS->getAsNamespace(),
1279                                       Q.getLocalBeginLoc(),
1280                                       TU)))
1281        return true;
1282
1283      break;
1284
1285    case NestedNameSpecifier::NamespaceAlias:
1286      if (Visit(MakeCursorNamespaceRef(NNS->getAsNamespaceAlias(),
1287                                       Q.getLocalBeginLoc(),
1288                                       TU)))
1289        return true;
1290
1291      break;
1292
1293    case NestedNameSpecifier::TypeSpec:
1294    case NestedNameSpecifier::TypeSpecWithTemplate:
1295      if (Visit(Q.getTypeLoc()))
1296        return true;
1297
1298      break;
1299
1300    case NestedNameSpecifier::Global:
1301    case NestedNameSpecifier::Identifier:
1302      break;
1303    }
1304  }
1305
1306  return false;
1307}
1308
1309bool CursorVisitor::VisitTemplateParameters(
1310                                          const TemplateParameterList *Params) {
1311  if (!Params)
1312    return false;
1313
1314  for (TemplateParameterList::const_iterator P = Params->begin(),
1315                                          PEnd = Params->end();
1316       P != PEnd; ++P) {
1317    if (Visit(MakeCXCursor(*P, TU, RegionOfInterest)))
1318      return true;
1319  }
1320
1321  return false;
1322}
1323
1324bool CursorVisitor::VisitTemplateName(TemplateName Name, SourceLocation Loc) {
1325  switch (Name.getKind()) {
1326  case TemplateName::Template:
1327    return Visit(MakeCursorTemplateRef(Name.getAsTemplateDecl(), Loc, TU));
1328
1329  case TemplateName::OverloadedTemplate:
1330    // Visit the overloaded template set.
1331    if (Visit(MakeCursorOverloadedDeclRef(Name, Loc, TU)))
1332      return true;
1333
1334    return false;
1335
1336  case TemplateName::DependentTemplate:
1337    // FIXME: Visit nested-name-specifier.
1338    return false;
1339
1340  case TemplateName::QualifiedTemplate:
1341    // FIXME: Visit nested-name-specifier.
1342    return Visit(MakeCursorTemplateRef(
1343                                  Name.getAsQualifiedTemplateName()->getDecl(),
1344                                       Loc, TU));
1345
1346  case TemplateName::SubstTemplateTemplateParm:
1347    return Visit(MakeCursorTemplateRef(
1348                         Name.getAsSubstTemplateTemplateParm()->getParameter(),
1349                                       Loc, TU));
1350
1351  case TemplateName::SubstTemplateTemplateParmPack:
1352    return Visit(MakeCursorTemplateRef(
1353                  Name.getAsSubstTemplateTemplateParmPack()->getParameterPack(),
1354                                       Loc, TU));
1355  }
1356
1357  return false;
1358}
1359
1360bool CursorVisitor::VisitTemplateArgumentLoc(const TemplateArgumentLoc &TAL) {
1361  switch (TAL.getArgument().getKind()) {
1362  case TemplateArgument::Null:
1363  case TemplateArgument::Integral:
1364  case TemplateArgument::Pack:
1365    return false;
1366
1367  case TemplateArgument::Type:
1368    if (TypeSourceInfo *TSInfo = TAL.getTypeSourceInfo())
1369      return Visit(TSInfo->getTypeLoc());
1370    return false;
1371
1372  case TemplateArgument::Declaration:
1373    if (Expr *E = TAL.getSourceDeclExpression())
1374      return Visit(MakeCXCursor(E, StmtParent, TU, RegionOfInterest));
1375    return false;
1376
1377  case TemplateArgument::Expression:
1378    if (Expr *E = TAL.getSourceExpression())
1379      return Visit(MakeCXCursor(E, StmtParent, TU, RegionOfInterest));
1380    return false;
1381
1382  case TemplateArgument::Template:
1383  case TemplateArgument::TemplateExpansion:
1384    if (VisitNestedNameSpecifierLoc(TAL.getTemplateQualifierLoc()))
1385      return true;
1386
1387    return VisitTemplateName(TAL.getArgument().getAsTemplateOrTemplatePattern(),
1388                             TAL.getTemplateNameLoc());
1389  }
1390
1391  return false;
1392}
1393
1394bool CursorVisitor::VisitLinkageSpecDecl(LinkageSpecDecl *D) {
1395  return VisitDeclContext(D);
1396}
1397
1398bool CursorVisitor::VisitQualifiedTypeLoc(QualifiedTypeLoc TL) {
1399  return Visit(TL.getUnqualifiedLoc());
1400}
1401
1402bool CursorVisitor::VisitBuiltinTypeLoc(BuiltinTypeLoc TL) {
1403  ASTContext &Context = AU->getASTContext();
1404
1405  // Some builtin types (such as Objective-C's "id", "sel", and
1406  // "Class") have associated declarations. Create cursors for those.
1407  QualType VisitType;
1408  switch (TL.getTypePtr()->getKind()) {
1409
1410  case BuiltinType::Void:
1411  case BuiltinType::NullPtr:
1412  case BuiltinType::Dependent:
1413#define BUILTIN_TYPE(Id, SingletonId)
1414#define SIGNED_TYPE(Id, SingletonId) case BuiltinType::Id:
1415#define UNSIGNED_TYPE(Id, SingletonId) case BuiltinType::Id:
1416#define FLOATING_TYPE(Id, SingletonId) case BuiltinType::Id:
1417#define PLACEHOLDER_TYPE(Id, SingletonId) case BuiltinType::Id:
1418#include "clang/AST/BuiltinTypes.def"
1419    break;
1420
1421  case BuiltinType::ObjCId:
1422    VisitType = Context.getObjCIdType();
1423    break;
1424
1425  case BuiltinType::ObjCClass:
1426    VisitType = Context.getObjCClassType();
1427    break;
1428
1429  case BuiltinType::ObjCSel:
1430    VisitType = Context.getObjCSelType();
1431    break;
1432  }
1433
1434  if (!VisitType.isNull()) {
1435    if (const TypedefType *Typedef = VisitType->getAs<TypedefType>())
1436      return Visit(MakeCursorTypeRef(Typedef->getDecl(), TL.getBuiltinLoc(),
1437                                     TU));
1438  }
1439
1440  return false;
1441}
1442
1443bool CursorVisitor::VisitTypedefTypeLoc(TypedefTypeLoc TL) {
1444  return Visit(MakeCursorTypeRef(TL.getTypedefNameDecl(), TL.getNameLoc(), TU));
1445}
1446
1447bool CursorVisitor::VisitUnresolvedUsingTypeLoc(UnresolvedUsingTypeLoc TL) {
1448  return Visit(MakeCursorTypeRef(TL.getDecl(), TL.getNameLoc(), TU));
1449}
1450
1451bool CursorVisitor::VisitTagTypeLoc(TagTypeLoc TL) {
1452  if (TL.isDefinition())
1453    return Visit(MakeCXCursor(TL.getDecl(), TU, RegionOfInterest));
1454
1455  return Visit(MakeCursorTypeRef(TL.getDecl(), TL.getNameLoc(), TU));
1456}
1457
1458bool CursorVisitor::VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc TL) {
1459  return Visit(MakeCursorTypeRef(TL.getDecl(), TL.getNameLoc(), TU));
1460}
1461
1462bool CursorVisitor::VisitObjCInterfaceTypeLoc(ObjCInterfaceTypeLoc TL) {
1463  if (Visit(MakeCursorObjCClassRef(TL.getIFaceDecl(), TL.getNameLoc(), TU)))
1464    return true;
1465
1466  return false;
1467}
1468
1469bool CursorVisitor::VisitObjCObjectTypeLoc(ObjCObjectTypeLoc TL) {
1470  if (TL.hasBaseTypeAsWritten() && Visit(TL.getBaseLoc()))
1471    return true;
1472
1473  for (unsigned I = 0, N = TL.getNumProtocols(); I != N; ++I) {
1474    if (Visit(MakeCursorObjCProtocolRef(TL.getProtocol(I), TL.getProtocolLoc(I),
1475                                        TU)))
1476      return true;
1477  }
1478
1479  return false;
1480}
1481
1482bool CursorVisitor::VisitObjCObjectPointerTypeLoc(ObjCObjectPointerTypeLoc TL) {
1483  return Visit(TL.getPointeeLoc());
1484}
1485
1486bool CursorVisitor::VisitParenTypeLoc(ParenTypeLoc TL) {
1487  return Visit(TL.getInnerLoc());
1488}
1489
1490bool CursorVisitor::VisitPointerTypeLoc(PointerTypeLoc TL) {
1491  return Visit(TL.getPointeeLoc());
1492}
1493
1494bool CursorVisitor::VisitBlockPointerTypeLoc(BlockPointerTypeLoc TL) {
1495  return Visit(TL.getPointeeLoc());
1496}
1497
1498bool CursorVisitor::VisitMemberPointerTypeLoc(MemberPointerTypeLoc TL) {
1499  return Visit(TL.getPointeeLoc());
1500}
1501
1502bool CursorVisitor::VisitLValueReferenceTypeLoc(LValueReferenceTypeLoc TL) {
1503  return Visit(TL.getPointeeLoc());
1504}
1505
1506bool CursorVisitor::VisitRValueReferenceTypeLoc(RValueReferenceTypeLoc TL) {
1507  return Visit(TL.getPointeeLoc());
1508}
1509
1510bool CursorVisitor::VisitAttributedTypeLoc(AttributedTypeLoc TL) {
1511  return Visit(TL.getModifiedLoc());
1512}
1513
1514bool CursorVisitor::VisitFunctionTypeLoc(FunctionTypeLoc TL,
1515                                         bool SkipResultType) {
1516  if (!SkipResultType && Visit(TL.getResultLoc()))
1517    return true;
1518
1519  for (unsigned I = 0, N = TL.getNumArgs(); I != N; ++I)
1520    if (Decl *D = TL.getArg(I))
1521      if (Visit(MakeCXCursor(D, TU, RegionOfInterest)))
1522        return true;
1523
1524  return false;
1525}
1526
1527bool CursorVisitor::VisitArrayTypeLoc(ArrayTypeLoc TL) {
1528  if (Visit(TL.getElementLoc()))
1529    return true;
1530
1531  if (Expr *Size = TL.getSizeExpr())
1532    return Visit(MakeCXCursor(Size, StmtParent, TU, RegionOfInterest));
1533
1534  return false;
1535}
1536
1537bool CursorVisitor::VisitTemplateSpecializationTypeLoc(
1538                                             TemplateSpecializationTypeLoc TL) {
1539  // Visit the template name.
1540  if (VisitTemplateName(TL.getTypePtr()->getTemplateName(),
1541                        TL.getTemplateNameLoc()))
1542    return true;
1543
1544  // Visit the template arguments.
1545  for (unsigned I = 0, N = TL.getNumArgs(); I != N; ++I)
1546    if (VisitTemplateArgumentLoc(TL.getArgLoc(I)))
1547      return true;
1548
1549  return false;
1550}
1551
1552bool CursorVisitor::VisitTypeOfExprTypeLoc(TypeOfExprTypeLoc TL) {
1553  return Visit(MakeCXCursor(TL.getUnderlyingExpr(), StmtParent, TU));
1554}
1555
1556bool CursorVisitor::VisitTypeOfTypeLoc(TypeOfTypeLoc TL) {
1557  if (TypeSourceInfo *TSInfo = TL.getUnderlyingTInfo())
1558    return Visit(TSInfo->getTypeLoc());
1559
1560  return false;
1561}
1562
1563bool CursorVisitor::VisitUnaryTransformTypeLoc(UnaryTransformTypeLoc TL) {
1564  if (TypeSourceInfo *TSInfo = TL.getUnderlyingTInfo())
1565    return Visit(TSInfo->getTypeLoc());
1566
1567  return false;
1568}
1569
1570bool CursorVisitor::VisitDependentNameTypeLoc(DependentNameTypeLoc TL) {
1571  if (VisitNestedNameSpecifierLoc(TL.getQualifierLoc()))
1572    return true;
1573
1574  return false;
1575}
1576
1577bool CursorVisitor::VisitDependentTemplateSpecializationTypeLoc(
1578                                    DependentTemplateSpecializationTypeLoc TL) {
1579  // Visit the nested-name-specifier, if there is one.
1580  if (TL.getQualifierLoc() &&
1581      VisitNestedNameSpecifierLoc(TL.getQualifierLoc()))
1582    return true;
1583
1584  // Visit the template arguments.
1585  for (unsigned I = 0, N = TL.getNumArgs(); I != N; ++I)
1586    if (VisitTemplateArgumentLoc(TL.getArgLoc(I)))
1587      return true;
1588
1589  return false;
1590}
1591
1592bool CursorVisitor::VisitElaboratedTypeLoc(ElaboratedTypeLoc TL) {
1593  if (VisitNestedNameSpecifierLoc(TL.getQualifierLoc()))
1594    return true;
1595
1596  return Visit(TL.getNamedTypeLoc());
1597}
1598
1599bool CursorVisitor::VisitPackExpansionTypeLoc(PackExpansionTypeLoc TL) {
1600  return Visit(TL.getPatternLoc());
1601}
1602
1603bool CursorVisitor::VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
1604  if (Expr *E = TL.getUnderlyingExpr())
1605    return Visit(MakeCXCursor(E, StmtParent, TU));
1606
1607  return false;
1608}
1609
1610bool CursorVisitor::VisitInjectedClassNameTypeLoc(InjectedClassNameTypeLoc TL) {
1611  return Visit(MakeCursorTypeRef(TL.getDecl(), TL.getNameLoc(), TU));
1612}
1613
1614bool CursorVisitor::VisitAtomicTypeLoc(AtomicTypeLoc TL) {
1615  return Visit(TL.getValueLoc());
1616}
1617
1618#define DEFAULT_TYPELOC_IMPL(CLASS, PARENT) \
1619bool CursorVisitor::Visit##CLASS##TypeLoc(CLASS##TypeLoc TL) { \
1620  return Visit##PARENT##Loc(TL); \
1621}
1622
1623DEFAULT_TYPELOC_IMPL(Complex, Type)
1624DEFAULT_TYPELOC_IMPL(ConstantArray, ArrayType)
1625DEFAULT_TYPELOC_IMPL(IncompleteArray, ArrayType)
1626DEFAULT_TYPELOC_IMPL(VariableArray, ArrayType)
1627DEFAULT_TYPELOC_IMPL(DependentSizedArray, ArrayType)
1628DEFAULT_TYPELOC_IMPL(DependentSizedExtVector, Type)
1629DEFAULT_TYPELOC_IMPL(Vector, Type)
1630DEFAULT_TYPELOC_IMPL(ExtVector, VectorType)
1631DEFAULT_TYPELOC_IMPL(FunctionProto, FunctionType)
1632DEFAULT_TYPELOC_IMPL(FunctionNoProto, FunctionType)
1633DEFAULT_TYPELOC_IMPL(Record, TagType)
1634DEFAULT_TYPELOC_IMPL(Enum, TagType)
1635DEFAULT_TYPELOC_IMPL(SubstTemplateTypeParm, Type)
1636DEFAULT_TYPELOC_IMPL(SubstTemplateTypeParmPack, Type)
1637DEFAULT_TYPELOC_IMPL(Auto, Type)
1638
1639bool CursorVisitor::VisitCXXRecordDecl(CXXRecordDecl *D) {
1640  // Visit the nested-name-specifier, if present.
1641  if (NestedNameSpecifierLoc QualifierLoc = D->getQualifierLoc())
1642    if (VisitNestedNameSpecifierLoc(QualifierLoc))
1643      return true;
1644
1645  if (D->isCompleteDefinition()) {
1646    for (CXXRecordDecl::base_class_iterator I = D->bases_begin(),
1647         E = D->bases_end(); I != E; ++I) {
1648      if (Visit(cxcursor::MakeCursorCXXBaseSpecifier(I, TU)))
1649        return true;
1650    }
1651  }
1652
1653  return VisitTagDecl(D);
1654}
1655
1656bool CursorVisitor::VisitAttributes(Decl *D) {
1657  for (AttrVec::const_iterator i = D->attr_begin(), e = D->attr_end();
1658       i != e; ++i)
1659    if (Visit(MakeCXCursor(*i, D, TU)))
1660        return true;
1661
1662  return false;
1663}
1664
1665//===----------------------------------------------------------------------===//
1666// Data-recursive visitor methods.
1667//===----------------------------------------------------------------------===//
1668
1669namespace {
1670#define DEF_JOB(NAME, DATA, KIND)\
1671class NAME : public VisitorJob {\
1672public:\
1673  NAME(DATA *d, CXCursor parent) : VisitorJob(parent, VisitorJob::KIND, d) {} \
1674  static bool classof(const VisitorJob *VJ) { return VJ->getKind() == KIND; }\
1675  DATA *get() const { return static_cast<DATA*>(data[0]); }\
1676};
1677
1678DEF_JOB(StmtVisit, Stmt, StmtVisitKind)
1679DEF_JOB(MemberExprParts, MemberExpr, MemberExprPartsKind)
1680DEF_JOB(DeclRefExprParts, DeclRefExpr, DeclRefExprPartsKind)
1681DEF_JOB(OverloadExprParts, OverloadExpr, OverloadExprPartsKind)
1682DEF_JOB(ExplicitTemplateArgsVisit, ASTTemplateArgumentListInfo,
1683        ExplicitTemplateArgsVisitKind)
1684DEF_JOB(SizeOfPackExprParts, SizeOfPackExpr, SizeOfPackExprPartsKind)
1685#undef DEF_JOB
1686
1687class DeclVisit : public VisitorJob {
1688public:
1689  DeclVisit(Decl *d, CXCursor parent, bool isFirst) :
1690    VisitorJob(parent, VisitorJob::DeclVisitKind,
1691               d, isFirst ? (void*) 1 : (void*) 0) {}
1692  static bool classof(const VisitorJob *VJ) {
1693    return VJ->getKind() == DeclVisitKind;
1694  }
1695  Decl *get() const { return static_cast<Decl*>(data[0]); }
1696  bool isFirst() const { return data[1] ? true : false; }
1697};
1698class TypeLocVisit : public VisitorJob {
1699public:
1700  TypeLocVisit(TypeLoc tl, CXCursor parent) :
1701    VisitorJob(parent, VisitorJob::TypeLocVisitKind,
1702               tl.getType().getAsOpaquePtr(), tl.getOpaqueData()) {}
1703
1704  static bool classof(const VisitorJob *VJ) {
1705    return VJ->getKind() == TypeLocVisitKind;
1706  }
1707
1708  TypeLoc get() const {
1709    QualType T = QualType::getFromOpaquePtr(data[0]);
1710    return TypeLoc(T, data[1]);
1711  }
1712};
1713
1714class LabelRefVisit : public VisitorJob {
1715public:
1716  LabelRefVisit(LabelDecl *LD, SourceLocation labelLoc, CXCursor parent)
1717    : VisitorJob(parent, VisitorJob::LabelRefVisitKind, LD,
1718                 labelLoc.getPtrEncoding()) {}
1719
1720  static bool classof(const VisitorJob *VJ) {
1721    return VJ->getKind() == VisitorJob::LabelRefVisitKind;
1722  }
1723  LabelDecl *get() const { return static_cast<LabelDecl*>(data[0]); }
1724  SourceLocation getLoc() const {
1725    return SourceLocation::getFromPtrEncoding(data[1]); }
1726};
1727
1728class NestedNameSpecifierLocVisit : public VisitorJob {
1729public:
1730  NestedNameSpecifierLocVisit(NestedNameSpecifierLoc Qualifier, CXCursor parent)
1731    : VisitorJob(parent, VisitorJob::NestedNameSpecifierLocVisitKind,
1732                 Qualifier.getNestedNameSpecifier(),
1733                 Qualifier.getOpaqueData()) { }
1734
1735  static bool classof(const VisitorJob *VJ) {
1736    return VJ->getKind() == VisitorJob::NestedNameSpecifierLocVisitKind;
1737  }
1738
1739  NestedNameSpecifierLoc get() const {
1740    return NestedNameSpecifierLoc(static_cast<NestedNameSpecifier*>(data[0]),
1741                                  data[1]);
1742  }
1743};
1744
1745class DeclarationNameInfoVisit : public VisitorJob {
1746public:
1747  DeclarationNameInfoVisit(Stmt *S, CXCursor parent)
1748    : VisitorJob(parent, VisitorJob::DeclarationNameInfoVisitKind, S) {}
1749  static bool classof(const VisitorJob *VJ) {
1750    return VJ->getKind() == VisitorJob::DeclarationNameInfoVisitKind;
1751  }
1752  DeclarationNameInfo get() const {
1753    Stmt *S = static_cast<Stmt*>(data[0]);
1754    switch (S->getStmtClass()) {
1755    default:
1756      llvm_unreachable("Unhandled Stmt");
1757    case clang::Stmt::MSDependentExistsStmtClass:
1758      return cast<MSDependentExistsStmt>(S)->getNameInfo();
1759    case Stmt::CXXDependentScopeMemberExprClass:
1760      return cast<CXXDependentScopeMemberExpr>(S)->getMemberNameInfo();
1761    case Stmt::DependentScopeDeclRefExprClass:
1762      return cast<DependentScopeDeclRefExpr>(S)->getNameInfo();
1763    }
1764  }
1765};
1766class MemberRefVisit : public VisitorJob {
1767public:
1768  MemberRefVisit(FieldDecl *D, SourceLocation L, CXCursor parent)
1769    : VisitorJob(parent, VisitorJob::MemberRefVisitKind, D,
1770                 L.getPtrEncoding()) {}
1771  static bool classof(const VisitorJob *VJ) {
1772    return VJ->getKind() == VisitorJob::MemberRefVisitKind;
1773  }
1774  FieldDecl *get() const {
1775    return static_cast<FieldDecl*>(data[0]);
1776  }
1777  SourceLocation getLoc() const {
1778    return SourceLocation::getFromRawEncoding((unsigned)(uintptr_t) data[1]);
1779  }
1780};
1781class EnqueueVisitor : public StmtVisitor<EnqueueVisitor, void> {
1782  VisitorWorkList &WL;
1783  CXCursor Parent;
1784public:
1785  EnqueueVisitor(VisitorWorkList &wl, CXCursor parent)
1786    : WL(wl), Parent(parent) {}
1787
1788  void VisitAddrLabelExpr(AddrLabelExpr *E);
1789  void VisitBlockExpr(BlockExpr *B);
1790  void VisitCompoundLiteralExpr(CompoundLiteralExpr *E);
1791  void VisitCompoundStmt(CompoundStmt *S);
1792  void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) { /* Do nothing. */ }
1793  void VisitMSDependentExistsStmt(MSDependentExistsStmt *S);
1794  void VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E);
1795  void VisitCXXNewExpr(CXXNewExpr *E);
1796  void VisitCXXScalarValueInitExpr(CXXScalarValueInitExpr *E);
1797  void VisitCXXOperatorCallExpr(CXXOperatorCallExpr *E);
1798  void VisitCXXPseudoDestructorExpr(CXXPseudoDestructorExpr *E);
1799  void VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *E);
1800  void VisitCXXTypeidExpr(CXXTypeidExpr *E);
1801  void VisitCXXUnresolvedConstructExpr(CXXUnresolvedConstructExpr *E);
1802  void VisitCXXUuidofExpr(CXXUuidofExpr *E);
1803  void VisitDeclRefExpr(DeclRefExpr *D);
1804  void VisitDeclStmt(DeclStmt *S);
1805  void VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E);
1806  void VisitDesignatedInitExpr(DesignatedInitExpr *E);
1807  void VisitExplicitCastExpr(ExplicitCastExpr *E);
1808  void VisitForStmt(ForStmt *FS);
1809  void VisitGotoStmt(GotoStmt *GS);
1810  void VisitIfStmt(IfStmt *If);
1811  void VisitInitListExpr(InitListExpr *IE);
1812  void VisitMemberExpr(MemberExpr *M);
1813  void VisitOffsetOfExpr(OffsetOfExpr *E);
1814  void VisitObjCEncodeExpr(ObjCEncodeExpr *E);
1815  void VisitObjCMessageExpr(ObjCMessageExpr *M);
1816  void VisitOverloadExpr(OverloadExpr *E);
1817  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E);
1818  void VisitStmt(Stmt *S);
1819  void VisitSwitchStmt(SwitchStmt *S);
1820  void VisitWhileStmt(WhileStmt *W);
1821  void VisitUnaryTypeTraitExpr(UnaryTypeTraitExpr *E);
1822  void VisitBinaryTypeTraitExpr(BinaryTypeTraitExpr *E);
1823  void VisitArrayTypeTraitExpr(ArrayTypeTraitExpr *E);
1824  void VisitExpressionTraitExpr(ExpressionTraitExpr *E);
1825  void VisitUnresolvedMemberExpr(UnresolvedMemberExpr *U);
1826  void VisitVAArgExpr(VAArgExpr *E);
1827  void VisitSizeOfPackExpr(SizeOfPackExpr *E);
1828
1829private:
1830  void AddDeclarationNameInfo(Stmt *S);
1831  void AddNestedNameSpecifierLoc(NestedNameSpecifierLoc Qualifier);
1832  void AddExplicitTemplateArgs(const ASTTemplateArgumentListInfo *A);
1833  void AddMemberRef(FieldDecl *D, SourceLocation L);
1834  void AddStmt(Stmt *S);
1835  void AddDecl(Decl *D, bool isFirst = true);
1836  void AddTypeLoc(TypeSourceInfo *TI);
1837  void EnqueueChildren(Stmt *S);
1838};
1839} // end anonyous namespace
1840
1841void EnqueueVisitor::AddDeclarationNameInfo(Stmt *S) {
1842  // 'S' should always be non-null, since it comes from the
1843  // statement we are visiting.
1844  WL.push_back(DeclarationNameInfoVisit(S, Parent));
1845}
1846
1847void
1848EnqueueVisitor::AddNestedNameSpecifierLoc(NestedNameSpecifierLoc Qualifier) {
1849  if (Qualifier)
1850    WL.push_back(NestedNameSpecifierLocVisit(Qualifier, Parent));
1851}
1852
1853void EnqueueVisitor::AddStmt(Stmt *S) {
1854  if (S)
1855    WL.push_back(StmtVisit(S, Parent));
1856}
1857void EnqueueVisitor::AddDecl(Decl *D, bool isFirst) {
1858  if (D)
1859    WL.push_back(DeclVisit(D, Parent, isFirst));
1860}
1861void EnqueueVisitor::
1862  AddExplicitTemplateArgs(const ASTTemplateArgumentListInfo *A) {
1863  if (A)
1864    WL.push_back(ExplicitTemplateArgsVisit(
1865                        const_cast<ASTTemplateArgumentListInfo*>(A), Parent));
1866}
1867void EnqueueVisitor::AddMemberRef(FieldDecl *D, SourceLocation L) {
1868  if (D)
1869    WL.push_back(MemberRefVisit(D, L, Parent));
1870}
1871void EnqueueVisitor::AddTypeLoc(TypeSourceInfo *TI) {
1872  if (TI)
1873    WL.push_back(TypeLocVisit(TI->getTypeLoc(), Parent));
1874 }
1875void EnqueueVisitor::EnqueueChildren(Stmt *S) {
1876  unsigned size = WL.size();
1877  for (Stmt::child_range Child = S->children(); Child; ++Child) {
1878    AddStmt(*Child);
1879  }
1880  if (size == WL.size())
1881    return;
1882  // Now reverse the entries we just added.  This will match the DFS
1883  // ordering performed by the worklist.
1884  VisitorWorkList::iterator I = WL.begin() + size, E = WL.end();
1885  std::reverse(I, E);
1886}
1887void EnqueueVisitor::VisitAddrLabelExpr(AddrLabelExpr *E) {
1888  WL.push_back(LabelRefVisit(E->getLabel(), E->getLabelLoc(), Parent));
1889}
1890void EnqueueVisitor::VisitBlockExpr(BlockExpr *B) {
1891  AddDecl(B->getBlockDecl());
1892}
1893void EnqueueVisitor::VisitCompoundLiteralExpr(CompoundLiteralExpr *E) {
1894  EnqueueChildren(E);
1895  AddTypeLoc(E->getTypeSourceInfo());
1896}
1897void EnqueueVisitor::VisitCompoundStmt(CompoundStmt *S) {
1898  for (CompoundStmt::reverse_body_iterator I = S->body_rbegin(),
1899        E = S->body_rend(); I != E; ++I) {
1900    AddStmt(*I);
1901  }
1902}
1903void EnqueueVisitor::
1904VisitMSDependentExistsStmt(MSDependentExistsStmt *S) {
1905  AddStmt(S->getSubStmt());
1906  AddDeclarationNameInfo(S);
1907  if (NestedNameSpecifierLoc QualifierLoc = S->getQualifierLoc())
1908    AddNestedNameSpecifierLoc(QualifierLoc);
1909}
1910
1911void EnqueueVisitor::
1912VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
1913  AddExplicitTemplateArgs(E->getOptionalExplicitTemplateArgs());
1914  AddDeclarationNameInfo(E);
1915  if (NestedNameSpecifierLoc QualifierLoc = E->getQualifierLoc())
1916    AddNestedNameSpecifierLoc(QualifierLoc);
1917  if (!E->isImplicitAccess())
1918    AddStmt(E->getBase());
1919}
1920void EnqueueVisitor::VisitCXXNewExpr(CXXNewExpr *E) {
1921  // Enqueue the initializer or constructor arguments.
1922  for (unsigned I = E->getNumConstructorArgs(); I > 0; --I)
1923    AddStmt(E->getConstructorArg(I-1));
1924  // Enqueue the array size, if any.
1925  AddStmt(E->getArraySize());
1926  // Enqueue the allocated type.
1927  AddTypeLoc(E->getAllocatedTypeSourceInfo());
1928  // Enqueue the placement arguments.
1929  for (unsigned I = E->getNumPlacementArgs(); I > 0; --I)
1930    AddStmt(E->getPlacementArg(I-1));
1931}
1932void EnqueueVisitor::VisitCXXOperatorCallExpr(CXXOperatorCallExpr *CE) {
1933  for (unsigned I = CE->getNumArgs(); I > 1 /* Yes, this is 1 */; --I)
1934    AddStmt(CE->getArg(I-1));
1935  AddStmt(CE->getCallee());
1936  AddStmt(CE->getArg(0));
1937}
1938void EnqueueVisitor::VisitCXXPseudoDestructorExpr(CXXPseudoDestructorExpr *E) {
1939  // Visit the name of the type being destroyed.
1940  AddTypeLoc(E->getDestroyedTypeInfo());
1941  // Visit the scope type that looks disturbingly like the nested-name-specifier
1942  // but isn't.
1943  AddTypeLoc(E->getScopeTypeInfo());
1944  // Visit the nested-name-specifier.
1945  if (NestedNameSpecifierLoc QualifierLoc = E->getQualifierLoc())
1946    AddNestedNameSpecifierLoc(QualifierLoc);
1947  // Visit base expression.
1948  AddStmt(E->getBase());
1949}
1950void EnqueueVisitor::VisitCXXScalarValueInitExpr(CXXScalarValueInitExpr *E) {
1951  AddTypeLoc(E->getTypeSourceInfo());
1952}
1953void EnqueueVisitor::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *E) {
1954  EnqueueChildren(E);
1955  AddTypeLoc(E->getTypeSourceInfo());
1956}
1957void EnqueueVisitor::VisitCXXTypeidExpr(CXXTypeidExpr *E) {
1958  EnqueueChildren(E);
1959  if (E->isTypeOperand())
1960    AddTypeLoc(E->getTypeOperandSourceInfo());
1961}
1962
1963void EnqueueVisitor::VisitCXXUnresolvedConstructExpr(CXXUnresolvedConstructExpr
1964                                                     *E) {
1965  EnqueueChildren(E);
1966  AddTypeLoc(E->getTypeSourceInfo());
1967}
1968void EnqueueVisitor::VisitCXXUuidofExpr(CXXUuidofExpr *E) {
1969  EnqueueChildren(E);
1970  if (E->isTypeOperand())
1971    AddTypeLoc(E->getTypeOperandSourceInfo());
1972}
1973void EnqueueVisitor::VisitDeclRefExpr(DeclRefExpr *DR) {
1974  if (DR->hasExplicitTemplateArgs()) {
1975    AddExplicitTemplateArgs(&DR->getExplicitTemplateArgs());
1976  }
1977  WL.push_back(DeclRefExprParts(DR, Parent));
1978}
1979void EnqueueVisitor::VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E) {
1980  AddExplicitTemplateArgs(E->getOptionalExplicitTemplateArgs());
1981  AddDeclarationNameInfo(E);
1982  AddNestedNameSpecifierLoc(E->getQualifierLoc());
1983}
1984void EnqueueVisitor::VisitDeclStmt(DeclStmt *S) {
1985  unsigned size = WL.size();
1986  bool isFirst = true;
1987  for (DeclStmt::decl_iterator D = S->decl_begin(), DEnd = S->decl_end();
1988       D != DEnd; ++D) {
1989    AddDecl(*D, isFirst);
1990    isFirst = false;
1991  }
1992  if (size == WL.size())
1993    return;
1994  // Now reverse the entries we just added.  This will match the DFS
1995  // ordering performed by the worklist.
1996  VisitorWorkList::iterator I = WL.begin() + size, E = WL.end();
1997  std::reverse(I, E);
1998}
1999void EnqueueVisitor::VisitDesignatedInitExpr(DesignatedInitExpr *E) {
2000  AddStmt(E->getInit());
2001  typedef DesignatedInitExpr::Designator Designator;
2002  for (DesignatedInitExpr::reverse_designators_iterator
2003         D = E->designators_rbegin(), DEnd = E->designators_rend();
2004         D != DEnd; ++D) {
2005    if (D->isFieldDesignator()) {
2006      if (FieldDecl *Field = D->getField())
2007        AddMemberRef(Field, D->getFieldLoc());
2008      continue;
2009    }
2010    if (D->isArrayDesignator()) {
2011      AddStmt(E->getArrayIndex(*D));
2012      continue;
2013    }
2014    assert(D->isArrayRangeDesignator() && "Unknown designator kind");
2015    AddStmt(E->getArrayRangeEnd(*D));
2016    AddStmt(E->getArrayRangeStart(*D));
2017  }
2018}
2019void EnqueueVisitor::VisitExplicitCastExpr(ExplicitCastExpr *E) {
2020  EnqueueChildren(E);
2021  AddTypeLoc(E->getTypeInfoAsWritten());
2022}
2023void EnqueueVisitor::VisitForStmt(ForStmt *FS) {
2024  AddStmt(FS->getBody());
2025  AddStmt(FS->getInc());
2026  AddStmt(FS->getCond());
2027  AddDecl(FS->getConditionVariable());
2028  AddStmt(FS->getInit());
2029}
2030void EnqueueVisitor::VisitGotoStmt(GotoStmt *GS) {
2031  WL.push_back(LabelRefVisit(GS->getLabel(), GS->getLabelLoc(), Parent));
2032}
2033void EnqueueVisitor::VisitIfStmt(IfStmt *If) {
2034  AddStmt(If->getElse());
2035  AddStmt(If->getThen());
2036  AddStmt(If->getCond());
2037  AddDecl(If->getConditionVariable());
2038}
2039void EnqueueVisitor::VisitInitListExpr(InitListExpr *IE) {
2040  // We care about the syntactic form of the initializer list, only.
2041  if (InitListExpr *Syntactic = IE->getSyntacticForm())
2042    IE = Syntactic;
2043  EnqueueChildren(IE);
2044}
2045void EnqueueVisitor::VisitMemberExpr(MemberExpr *M) {
2046  WL.push_back(MemberExprParts(M, Parent));
2047
2048  // If the base of the member access expression is an implicit 'this', don't
2049  // visit it.
2050  // FIXME: If we ever want to show these implicit accesses, this will be
2051  // unfortunate. However, clang_getCursor() relies on this behavior.
2052  if (!M->isImplicitAccess())
2053    AddStmt(M->getBase());
2054}
2055void EnqueueVisitor::VisitObjCEncodeExpr(ObjCEncodeExpr *E) {
2056  AddTypeLoc(E->getEncodedTypeSourceInfo());
2057}
2058void EnqueueVisitor::VisitObjCMessageExpr(ObjCMessageExpr *M) {
2059  EnqueueChildren(M);
2060  AddTypeLoc(M->getClassReceiverTypeInfo());
2061}
2062void EnqueueVisitor::VisitOffsetOfExpr(OffsetOfExpr *E) {
2063  // Visit the components of the offsetof expression.
2064  for (unsigned N = E->getNumComponents(), I = N; I > 0; --I) {
2065    typedef OffsetOfExpr::OffsetOfNode OffsetOfNode;
2066    const OffsetOfNode &Node = E->getComponent(I-1);
2067    switch (Node.getKind()) {
2068    case OffsetOfNode::Array:
2069      AddStmt(E->getIndexExpr(Node.getArrayExprIndex()));
2070      break;
2071    case OffsetOfNode::Field:
2072      AddMemberRef(Node.getField(), Node.getSourceRange().getEnd());
2073      break;
2074    case OffsetOfNode::Identifier:
2075    case OffsetOfNode::Base:
2076      continue;
2077    }
2078  }
2079  // Visit the type into which we're computing the offset.
2080  AddTypeLoc(E->getTypeSourceInfo());
2081}
2082void EnqueueVisitor::VisitOverloadExpr(OverloadExpr *E) {
2083  AddExplicitTemplateArgs(E->getOptionalExplicitTemplateArgs());
2084  WL.push_back(OverloadExprParts(E, Parent));
2085}
2086void EnqueueVisitor::VisitUnaryExprOrTypeTraitExpr(
2087                                              UnaryExprOrTypeTraitExpr *E) {
2088  EnqueueChildren(E);
2089  if (E->isArgumentType())
2090    AddTypeLoc(E->getArgumentTypeInfo());
2091}
2092void EnqueueVisitor::VisitStmt(Stmt *S) {
2093  EnqueueChildren(S);
2094}
2095void EnqueueVisitor::VisitSwitchStmt(SwitchStmt *S) {
2096  AddStmt(S->getBody());
2097  AddStmt(S->getCond());
2098  AddDecl(S->getConditionVariable());
2099}
2100
2101void EnqueueVisitor::VisitWhileStmt(WhileStmt *W) {
2102  AddStmt(W->getBody());
2103  AddStmt(W->getCond());
2104  AddDecl(W->getConditionVariable());
2105}
2106
2107void EnqueueVisitor::VisitUnaryTypeTraitExpr(UnaryTypeTraitExpr *E) {
2108  AddTypeLoc(E->getQueriedTypeSourceInfo());
2109}
2110
2111void EnqueueVisitor::VisitBinaryTypeTraitExpr(BinaryTypeTraitExpr *E) {
2112  AddTypeLoc(E->getRhsTypeSourceInfo());
2113  AddTypeLoc(E->getLhsTypeSourceInfo());
2114}
2115
2116void EnqueueVisitor::VisitArrayTypeTraitExpr(ArrayTypeTraitExpr *E) {
2117  AddTypeLoc(E->getQueriedTypeSourceInfo());
2118}
2119
2120void EnqueueVisitor::VisitExpressionTraitExpr(ExpressionTraitExpr *E) {
2121  EnqueueChildren(E);
2122}
2123
2124void EnqueueVisitor::VisitUnresolvedMemberExpr(UnresolvedMemberExpr *U) {
2125  VisitOverloadExpr(U);
2126  if (!U->isImplicitAccess())
2127    AddStmt(U->getBase());
2128}
2129void EnqueueVisitor::VisitVAArgExpr(VAArgExpr *E) {
2130  AddStmt(E->getSubExpr());
2131  AddTypeLoc(E->getWrittenTypeInfo());
2132}
2133void EnqueueVisitor::VisitSizeOfPackExpr(SizeOfPackExpr *E) {
2134  WL.push_back(SizeOfPackExprParts(E, Parent));
2135}
2136
2137void CursorVisitor::EnqueueWorkList(VisitorWorkList &WL, Stmt *S) {
2138  EnqueueVisitor(WL, MakeCXCursor(S, StmtParent, TU,RegionOfInterest)).Visit(S);
2139}
2140
2141bool CursorVisitor::IsInRegionOfInterest(CXCursor C) {
2142  if (RegionOfInterest.isValid()) {
2143    SourceRange Range = getRawCursorExtent(C);
2144    if (Range.isInvalid() || CompareRegionOfInterest(Range))
2145      return false;
2146  }
2147  return true;
2148}
2149
2150bool CursorVisitor::RunVisitorWorkList(VisitorWorkList &WL) {
2151  while (!WL.empty()) {
2152    // Dequeue the worklist item.
2153    VisitorJob LI = WL.back();
2154    WL.pop_back();
2155
2156    // Set the Parent field, then back to its old value once we're done.
2157    SetParentRAII SetParent(Parent, StmtParent, LI.getParent());
2158
2159    switch (LI.getKind()) {
2160      case VisitorJob::DeclVisitKind: {
2161        Decl *D = cast<DeclVisit>(&LI)->get();
2162        if (!D)
2163          continue;
2164
2165        // For now, perform default visitation for Decls.
2166        if (Visit(MakeCXCursor(D, TU, RegionOfInterest,
2167                               cast<DeclVisit>(&LI)->isFirst())))
2168            return true;
2169
2170        continue;
2171      }
2172      case VisitorJob::ExplicitTemplateArgsVisitKind: {
2173        const ASTTemplateArgumentListInfo *ArgList =
2174          cast<ExplicitTemplateArgsVisit>(&LI)->get();
2175        for (const TemplateArgumentLoc *Arg = ArgList->getTemplateArgs(),
2176               *ArgEnd = Arg + ArgList->NumTemplateArgs;
2177               Arg != ArgEnd; ++Arg) {
2178          if (VisitTemplateArgumentLoc(*Arg))
2179            return true;
2180        }
2181        continue;
2182      }
2183      case VisitorJob::TypeLocVisitKind: {
2184        // Perform default visitation for TypeLocs.
2185        if (Visit(cast<TypeLocVisit>(&LI)->get()))
2186          return true;
2187        continue;
2188      }
2189      case VisitorJob::LabelRefVisitKind: {
2190        LabelDecl *LS = cast<LabelRefVisit>(&LI)->get();
2191        if (LabelStmt *stmt = LS->getStmt()) {
2192          if (Visit(MakeCursorLabelRef(stmt, cast<LabelRefVisit>(&LI)->getLoc(),
2193                                       TU))) {
2194            return true;
2195          }
2196        }
2197        continue;
2198      }
2199
2200      case VisitorJob::NestedNameSpecifierLocVisitKind: {
2201        NestedNameSpecifierLocVisit *V = cast<NestedNameSpecifierLocVisit>(&LI);
2202        if (VisitNestedNameSpecifierLoc(V->get()))
2203          return true;
2204        continue;
2205      }
2206
2207      case VisitorJob::DeclarationNameInfoVisitKind: {
2208        if (VisitDeclarationNameInfo(cast<DeclarationNameInfoVisit>(&LI)
2209                                     ->get()))
2210          return true;
2211        continue;
2212      }
2213      case VisitorJob::MemberRefVisitKind: {
2214        MemberRefVisit *V = cast<MemberRefVisit>(&LI);
2215        if (Visit(MakeCursorMemberRef(V->get(), V->getLoc(), TU)))
2216          return true;
2217        continue;
2218      }
2219      case VisitorJob::StmtVisitKind: {
2220        Stmt *S = cast<StmtVisit>(&LI)->get();
2221        if (!S)
2222          continue;
2223
2224        // Update the current cursor.
2225        CXCursor Cursor = MakeCXCursor(S, StmtParent, TU, RegionOfInterest);
2226        if (!IsInRegionOfInterest(Cursor))
2227          continue;
2228        switch (Visitor(Cursor, Parent, ClientData)) {
2229          case CXChildVisit_Break: return true;
2230          case CXChildVisit_Continue: break;
2231          case CXChildVisit_Recurse:
2232            EnqueueWorkList(WL, S);
2233            break;
2234        }
2235        continue;
2236      }
2237      case VisitorJob::MemberExprPartsKind: {
2238        // Handle the other pieces in the MemberExpr besides the base.
2239        MemberExpr *M = cast<MemberExprParts>(&LI)->get();
2240
2241        // Visit the nested-name-specifier
2242        if (NestedNameSpecifierLoc QualifierLoc = M->getQualifierLoc())
2243          if (VisitNestedNameSpecifierLoc(QualifierLoc))
2244            return true;
2245
2246        // Visit the declaration name.
2247        if (VisitDeclarationNameInfo(M->getMemberNameInfo()))
2248          return true;
2249
2250        // Visit the explicitly-specified template arguments, if any.
2251        if (M->hasExplicitTemplateArgs()) {
2252          for (const TemplateArgumentLoc *Arg = M->getTemplateArgs(),
2253               *ArgEnd = Arg + M->getNumTemplateArgs();
2254               Arg != ArgEnd; ++Arg) {
2255            if (VisitTemplateArgumentLoc(*Arg))
2256              return true;
2257          }
2258        }
2259        continue;
2260      }
2261      case VisitorJob::DeclRefExprPartsKind: {
2262        DeclRefExpr *DR = cast<DeclRefExprParts>(&LI)->get();
2263        // Visit nested-name-specifier, if present.
2264        if (NestedNameSpecifierLoc QualifierLoc = DR->getQualifierLoc())
2265          if (VisitNestedNameSpecifierLoc(QualifierLoc))
2266            return true;
2267        // Visit declaration name.
2268        if (VisitDeclarationNameInfo(DR->getNameInfo()))
2269          return true;
2270        continue;
2271      }
2272      case VisitorJob::OverloadExprPartsKind: {
2273        OverloadExpr *O = cast<OverloadExprParts>(&LI)->get();
2274        // Visit the nested-name-specifier.
2275        if (NestedNameSpecifierLoc QualifierLoc = O->getQualifierLoc())
2276          if (VisitNestedNameSpecifierLoc(QualifierLoc))
2277            return true;
2278        // Visit the declaration name.
2279        if (VisitDeclarationNameInfo(O->getNameInfo()))
2280          return true;
2281        // Visit the overloaded declaration reference.
2282        if (Visit(MakeCursorOverloadedDeclRef(O, TU)))
2283          return true;
2284        continue;
2285      }
2286      case VisitorJob::SizeOfPackExprPartsKind: {
2287        SizeOfPackExpr *E = cast<SizeOfPackExprParts>(&LI)->get();
2288        NamedDecl *Pack = E->getPack();
2289        if (isa<TemplateTypeParmDecl>(Pack)) {
2290          if (Visit(MakeCursorTypeRef(cast<TemplateTypeParmDecl>(Pack),
2291                                      E->getPackLoc(), TU)))
2292            return true;
2293
2294          continue;
2295        }
2296
2297        if (isa<TemplateTemplateParmDecl>(Pack)) {
2298          if (Visit(MakeCursorTemplateRef(cast<TemplateTemplateParmDecl>(Pack),
2299                                          E->getPackLoc(), TU)))
2300            return true;
2301
2302          continue;
2303        }
2304
2305        // Non-type template parameter packs and function parameter packs are
2306        // treated like DeclRefExpr cursors.
2307        continue;
2308      }
2309    }
2310  }
2311  return false;
2312}
2313
2314bool CursorVisitor::Visit(Stmt *S) {
2315  VisitorWorkList *WL = 0;
2316  if (!WorkListFreeList.empty()) {
2317    WL = WorkListFreeList.back();
2318    WL->clear();
2319    WorkListFreeList.pop_back();
2320  }
2321  else {
2322    WL = new VisitorWorkList();
2323    WorkListCache.push_back(WL);
2324  }
2325  EnqueueWorkList(*WL, S);
2326  bool result = RunVisitorWorkList(*WL);
2327  WorkListFreeList.push_back(WL);
2328  return result;
2329}
2330
2331namespace {
2332typedef llvm::SmallVector<SourceRange, 4> RefNamePieces;
2333RefNamePieces buildPieces(unsigned NameFlags, bool IsMemberRefExpr,
2334                          const DeclarationNameInfo &NI,
2335                          const SourceRange &QLoc,
2336                          const ASTTemplateArgumentListInfo *TemplateArgs = 0){
2337  const bool WantQualifier = NameFlags & CXNameRange_WantQualifier;
2338  const bool WantTemplateArgs = NameFlags & CXNameRange_WantTemplateArgs;
2339  const bool WantSinglePiece = NameFlags & CXNameRange_WantSinglePiece;
2340
2341  const DeclarationName::NameKind Kind = NI.getName().getNameKind();
2342
2343  RefNamePieces Pieces;
2344
2345  if (WantQualifier && QLoc.isValid())
2346    Pieces.push_back(QLoc);
2347
2348  if (Kind != DeclarationName::CXXOperatorName || IsMemberRefExpr)
2349    Pieces.push_back(NI.getLoc());
2350
2351  if (WantTemplateArgs && TemplateArgs)
2352    Pieces.push_back(SourceRange(TemplateArgs->LAngleLoc,
2353                                 TemplateArgs->RAngleLoc));
2354
2355  if (Kind == DeclarationName::CXXOperatorName) {
2356    Pieces.push_back(SourceLocation::getFromRawEncoding(
2357                       NI.getInfo().CXXOperatorName.BeginOpNameLoc));
2358    Pieces.push_back(SourceLocation::getFromRawEncoding(
2359                       NI.getInfo().CXXOperatorName.EndOpNameLoc));
2360  }
2361
2362  if (WantSinglePiece) {
2363    SourceRange R(Pieces.front().getBegin(), Pieces.back().getEnd());
2364    Pieces.clear();
2365    Pieces.push_back(R);
2366  }
2367
2368  return Pieces;
2369}
2370}
2371
2372//===----------------------------------------------------------------------===//
2373// Misc. API hooks.
2374//===----------------------------------------------------------------------===//
2375
2376static llvm::sys::Mutex EnableMultithreadingMutex;
2377static bool EnabledMultithreading;
2378
2379extern "C" {
2380CXIndex clang_createIndex(int excludeDeclarationsFromPCH,
2381                          int displayDiagnostics) {
2382  // Disable pretty stack trace functionality, which will otherwise be a very
2383  // poor citizen of the world and set up all sorts of signal handlers.
2384  llvm::DisablePrettyStackTrace = true;
2385
2386  // We use crash recovery to make some of our APIs more reliable, implicitly
2387  // enable it.
2388  llvm::CrashRecoveryContext::Enable();
2389
2390  // Enable support for multithreading in LLVM.
2391  {
2392    llvm::sys::ScopedLock L(EnableMultithreadingMutex);
2393    if (!EnabledMultithreading) {
2394      llvm::llvm_start_multithreaded();
2395      EnabledMultithreading = true;
2396    }
2397  }
2398
2399  CIndexer *CIdxr = new CIndexer();
2400  if (excludeDeclarationsFromPCH)
2401    CIdxr->setOnlyLocalDecls();
2402  if (displayDiagnostics)
2403    CIdxr->setDisplayDiagnostics();
2404  return CIdxr;
2405}
2406
2407void clang_disposeIndex(CXIndex CIdx) {
2408  if (CIdx)
2409    delete static_cast<CIndexer *>(CIdx);
2410}
2411
2412void clang_toggleCrashRecovery(unsigned isEnabled) {
2413  if (isEnabled)
2414    llvm::CrashRecoveryContext::Enable();
2415  else
2416    llvm::CrashRecoveryContext::Disable();
2417}
2418
2419CXTranslationUnit clang_createTranslationUnit(CXIndex CIdx,
2420                                              const char *ast_filename) {
2421  if (!CIdx)
2422    return 0;
2423
2424  CIndexer *CXXIdx = static_cast<CIndexer *>(CIdx);
2425  FileSystemOptions FileSystemOpts;
2426  FileSystemOpts.WorkingDir = CXXIdx->getWorkingDirectory();
2427
2428  llvm::IntrusiveRefCntPtr<DiagnosticsEngine> Diags;
2429  ASTUnit *TU = ASTUnit::LoadFromASTFile(ast_filename, Diags, FileSystemOpts,
2430                                  CXXIdx->getOnlyLocalDecls(),
2431                                  0, 0, true);
2432  return MakeCXTranslationUnit(TU);
2433}
2434
2435unsigned clang_defaultEditingTranslationUnitOptions() {
2436  return CXTranslationUnit_PrecompiledPreamble |
2437         CXTranslationUnit_CacheCompletionResults;
2438}
2439
2440CXTranslationUnit
2441clang_createTranslationUnitFromSourceFile(CXIndex CIdx,
2442                                          const char *source_filename,
2443                                          int num_command_line_args,
2444                                          const char * const *command_line_args,
2445                                          unsigned num_unsaved_files,
2446                                          struct CXUnsavedFile *unsaved_files) {
2447  unsigned Options = CXTranslationUnit_DetailedPreprocessingRecord |
2448                     CXTranslationUnit_NestedMacroExpansions;
2449  return clang_parseTranslationUnit(CIdx, source_filename,
2450                                    command_line_args, num_command_line_args,
2451                                    unsaved_files, num_unsaved_files,
2452                                    Options);
2453}
2454
2455struct ParseTranslationUnitInfo {
2456  CXIndex CIdx;
2457  const char *source_filename;
2458  const char *const *command_line_args;
2459  int num_command_line_args;
2460  struct CXUnsavedFile *unsaved_files;
2461  unsigned num_unsaved_files;
2462  unsigned options;
2463  CXTranslationUnit result;
2464};
2465static void clang_parseTranslationUnit_Impl(void *UserData) {
2466  ParseTranslationUnitInfo *PTUI =
2467    static_cast<ParseTranslationUnitInfo*>(UserData);
2468  CXIndex CIdx = PTUI->CIdx;
2469  const char *source_filename = PTUI->source_filename;
2470  const char * const *command_line_args = PTUI->command_line_args;
2471  int num_command_line_args = PTUI->num_command_line_args;
2472  struct CXUnsavedFile *unsaved_files = PTUI->unsaved_files;
2473  unsigned num_unsaved_files = PTUI->num_unsaved_files;
2474  unsigned options = PTUI->options;
2475  PTUI->result = 0;
2476
2477  if (!CIdx)
2478    return;
2479
2480  CIndexer *CXXIdx = static_cast<CIndexer *>(CIdx);
2481
2482  bool PrecompilePreamble = options & CXTranslationUnit_PrecompiledPreamble;
2483  // FIXME: Add a flag for modules.
2484  TranslationUnitKind TUKind
2485    = (options & CXTranslationUnit_Incomplete)? TU_Prefix : TU_Complete;
2486  bool CacheCodeCompetionResults
2487    = options & CXTranslationUnit_CacheCompletionResults;
2488
2489  // Configure the diagnostics.
2490  DiagnosticOptions DiagOpts;
2491  llvm::IntrusiveRefCntPtr<DiagnosticsEngine>
2492    Diags(CompilerInstance::createDiagnostics(DiagOpts, num_command_line_args,
2493                                                command_line_args));
2494
2495  // Recover resources if we crash before exiting this function.
2496  llvm::CrashRecoveryContextCleanupRegistrar<DiagnosticsEngine,
2497    llvm::CrashRecoveryContextReleaseRefCleanup<DiagnosticsEngine> >
2498    DiagCleanup(Diags.getPtr());
2499
2500  llvm::OwningPtr<std::vector<ASTUnit::RemappedFile> >
2501    RemappedFiles(new std::vector<ASTUnit::RemappedFile>());
2502
2503  // Recover resources if we crash before exiting this function.
2504  llvm::CrashRecoveryContextCleanupRegistrar<
2505    std::vector<ASTUnit::RemappedFile> > RemappedCleanup(RemappedFiles.get());
2506
2507  for (unsigned I = 0; I != num_unsaved_files; ++I) {
2508    StringRef Data(unsaved_files[I].Contents, unsaved_files[I].Length);
2509    const llvm::MemoryBuffer *Buffer
2510      = llvm::MemoryBuffer::getMemBufferCopy(Data, unsaved_files[I].Filename);
2511    RemappedFiles->push_back(std::make_pair(unsaved_files[I].Filename,
2512                                            Buffer));
2513  }
2514
2515  llvm::OwningPtr<std::vector<const char *> >
2516    Args(new std::vector<const char*>());
2517
2518  // Recover resources if we crash before exiting this method.
2519  llvm::CrashRecoveryContextCleanupRegistrar<std::vector<const char*> >
2520    ArgsCleanup(Args.get());
2521
2522  // Since the Clang C library is primarily used by batch tools dealing with
2523  // (often very broken) source code, where spell-checking can have a
2524  // significant negative impact on performance (particularly when
2525  // precompiled headers are involved), we disable it by default.
2526  // Only do this if we haven't found a spell-checking-related argument.
2527  bool FoundSpellCheckingArgument = false;
2528  for (int I = 0; I != num_command_line_args; ++I) {
2529    if (strcmp(command_line_args[I], "-fno-spell-checking") == 0 ||
2530        strcmp(command_line_args[I], "-fspell-checking") == 0) {
2531      FoundSpellCheckingArgument = true;
2532      break;
2533    }
2534  }
2535  if (!FoundSpellCheckingArgument)
2536    Args->push_back("-fno-spell-checking");
2537
2538  Args->insert(Args->end(), command_line_args,
2539               command_line_args + num_command_line_args);
2540
2541  // The 'source_filename' argument is optional.  If the caller does not
2542  // specify it then it is assumed that the source file is specified
2543  // in the actual argument list.
2544  // Put the source file after command_line_args otherwise if '-x' flag is
2545  // present it will be unused.
2546  if (source_filename)
2547    Args->push_back(source_filename);
2548
2549  // Do we need the detailed preprocessing record?
2550  bool NestedMacroExpansions = false;
2551  if (options & CXTranslationUnit_DetailedPreprocessingRecord) {
2552    Args->push_back("-Xclang");
2553    Args->push_back("-detailed-preprocessing-record");
2554    NestedMacroExpansions
2555      = (options & CXTranslationUnit_NestedMacroExpansions);
2556  }
2557
2558  unsigned NumErrors = Diags->getClient()->getNumErrors();
2559  llvm::OwningPtr<ASTUnit> Unit(
2560    ASTUnit::LoadFromCommandLine(Args->size() ? &(*Args)[0] : 0
2561                                 /* vector::data() not portable */,
2562                                 Args->size() ? (&(*Args)[0] + Args->size()) :0,
2563                                 Diags,
2564                                 CXXIdx->getClangResourcesPath(),
2565                                 CXXIdx->getOnlyLocalDecls(),
2566                                 /*CaptureDiagnostics=*/true,
2567                                 RemappedFiles->size() ? &(*RemappedFiles)[0]:0,
2568                                 RemappedFiles->size(),
2569                                 /*RemappedFilesKeepOriginalName=*/true,
2570                                 PrecompilePreamble,
2571                                 TUKind,
2572                                 CacheCodeCompetionResults,
2573                                 NestedMacroExpansions));
2574
2575  if (NumErrors != Diags->getClient()->getNumErrors()) {
2576    // Make sure to check that 'Unit' is non-NULL.
2577    if (CXXIdx->getDisplayDiagnostics() && Unit.get()) {
2578      for (ASTUnit::stored_diag_iterator D = Unit->stored_diag_begin(),
2579                                      DEnd = Unit->stored_diag_end();
2580           D != DEnd; ++D) {
2581        CXStoredDiagnostic Diag(*D, Unit->getASTContext().getLangOptions());
2582        CXString Msg = clang_formatDiagnostic(&Diag,
2583                                    clang_defaultDiagnosticDisplayOptions());
2584        fprintf(stderr, "%s\n", clang_getCString(Msg));
2585        clang_disposeString(Msg);
2586      }
2587#ifdef LLVM_ON_WIN32
2588      // On Windows, force a flush, since there may be multiple copies of
2589      // stderr and stdout in the file system, all with different buffers
2590      // but writing to the same device.
2591      fflush(stderr);
2592#endif
2593    }
2594  }
2595
2596  PTUI->result = MakeCXTranslationUnit(Unit.take());
2597}
2598CXTranslationUnit clang_parseTranslationUnit(CXIndex CIdx,
2599                                             const char *source_filename,
2600                                         const char * const *command_line_args,
2601                                             int num_command_line_args,
2602                                            struct CXUnsavedFile *unsaved_files,
2603                                             unsigned num_unsaved_files,
2604                                             unsigned options) {
2605  ParseTranslationUnitInfo PTUI = { CIdx, source_filename, command_line_args,
2606                                    num_command_line_args, unsaved_files,
2607                                    num_unsaved_files, options, 0 };
2608  llvm::CrashRecoveryContext CRC;
2609
2610  if (!RunSafely(CRC, clang_parseTranslationUnit_Impl, &PTUI)) {
2611    fprintf(stderr, "libclang: crash detected during parsing: {\n");
2612    fprintf(stderr, "  'source_filename' : '%s'\n", source_filename);
2613    fprintf(stderr, "  'command_line_args' : [");
2614    for (int i = 0; i != num_command_line_args; ++i) {
2615      if (i)
2616        fprintf(stderr, ", ");
2617      fprintf(stderr, "'%s'", command_line_args[i]);
2618    }
2619    fprintf(stderr, "],\n");
2620    fprintf(stderr, "  'unsaved_files' : [");
2621    for (unsigned i = 0; i != num_unsaved_files; ++i) {
2622      if (i)
2623        fprintf(stderr, ", ");
2624      fprintf(stderr, "('%s', '...', %ld)", unsaved_files[i].Filename,
2625              unsaved_files[i].Length);
2626    }
2627    fprintf(stderr, "],\n");
2628    fprintf(stderr, "  'options' : %d,\n", options);
2629    fprintf(stderr, "}\n");
2630
2631    return 0;
2632  } else if (getenv("LIBCLANG_RESOURCE_USAGE")) {
2633    PrintLibclangResourceUsage(PTUI.result);
2634  }
2635
2636  return PTUI.result;
2637}
2638
2639unsigned clang_defaultSaveOptions(CXTranslationUnit TU) {
2640  return CXSaveTranslationUnit_None;
2641}
2642
2643int clang_saveTranslationUnit(CXTranslationUnit TU, const char *FileName,
2644                              unsigned options) {
2645  if (!TU)
2646    return CXSaveError_InvalidTU;
2647
2648  CXSaveError result = static_cast<ASTUnit *>(TU->TUData)->Save(FileName);
2649  if (getenv("LIBCLANG_RESOURCE_USAGE"))
2650    PrintLibclangResourceUsage(TU);
2651  return result;
2652}
2653
2654void clang_disposeTranslationUnit(CXTranslationUnit CTUnit) {
2655  if (CTUnit) {
2656    // If the translation unit has been marked as unsafe to free, just discard
2657    // it.
2658    if (static_cast<ASTUnit *>(CTUnit->TUData)->isUnsafeToFree())
2659      return;
2660
2661    delete static_cast<ASTUnit *>(CTUnit->TUData);
2662    disposeCXStringPool(CTUnit->StringPool);
2663    delete CTUnit;
2664  }
2665}
2666
2667unsigned clang_defaultReparseOptions(CXTranslationUnit TU) {
2668  return CXReparse_None;
2669}
2670
2671struct ReparseTranslationUnitInfo {
2672  CXTranslationUnit TU;
2673  unsigned num_unsaved_files;
2674  struct CXUnsavedFile *unsaved_files;
2675  unsigned options;
2676  int result;
2677};
2678
2679static void clang_reparseTranslationUnit_Impl(void *UserData) {
2680  ReparseTranslationUnitInfo *RTUI =
2681    static_cast<ReparseTranslationUnitInfo*>(UserData);
2682  CXTranslationUnit TU = RTUI->TU;
2683  unsigned num_unsaved_files = RTUI->num_unsaved_files;
2684  struct CXUnsavedFile *unsaved_files = RTUI->unsaved_files;
2685  unsigned options = RTUI->options;
2686  (void) options;
2687  RTUI->result = 1;
2688
2689  if (!TU)
2690    return;
2691
2692  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
2693  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
2694
2695  llvm::OwningPtr<std::vector<ASTUnit::RemappedFile> >
2696    RemappedFiles(new std::vector<ASTUnit::RemappedFile>());
2697
2698  // Recover resources if we crash before exiting this function.
2699  llvm::CrashRecoveryContextCleanupRegistrar<
2700    std::vector<ASTUnit::RemappedFile> > RemappedCleanup(RemappedFiles.get());
2701
2702  for (unsigned I = 0; I != num_unsaved_files; ++I) {
2703    StringRef Data(unsaved_files[I].Contents, unsaved_files[I].Length);
2704    const llvm::MemoryBuffer *Buffer
2705      = llvm::MemoryBuffer::getMemBufferCopy(Data, unsaved_files[I].Filename);
2706    RemappedFiles->push_back(std::make_pair(unsaved_files[I].Filename,
2707                                            Buffer));
2708  }
2709
2710  if (!CXXUnit->Reparse(RemappedFiles->size() ? &(*RemappedFiles)[0] : 0,
2711                        RemappedFiles->size()))
2712    RTUI->result = 0;
2713}
2714
2715int clang_reparseTranslationUnit(CXTranslationUnit TU,
2716                                 unsigned num_unsaved_files,
2717                                 struct CXUnsavedFile *unsaved_files,
2718                                 unsigned options) {
2719  ReparseTranslationUnitInfo RTUI = { TU, num_unsaved_files, unsaved_files,
2720                                      options, 0 };
2721
2722  if (getenv("LIBCLANG_NOTHREADS")) {
2723    clang_reparseTranslationUnit_Impl(&RTUI);
2724    return RTUI.result;
2725  }
2726
2727  llvm::CrashRecoveryContext CRC;
2728
2729  if (!RunSafely(CRC, clang_reparseTranslationUnit_Impl, &RTUI)) {
2730    fprintf(stderr, "libclang: crash detected during reparsing\n");
2731    static_cast<ASTUnit *>(TU->TUData)->setUnsafeToFree(true);
2732    return 1;
2733  } else if (getenv("LIBCLANG_RESOURCE_USAGE"))
2734    PrintLibclangResourceUsage(TU);
2735
2736  return RTUI.result;
2737}
2738
2739
2740CXString clang_getTranslationUnitSpelling(CXTranslationUnit CTUnit) {
2741  if (!CTUnit)
2742    return createCXString("");
2743
2744  ASTUnit *CXXUnit = static_cast<ASTUnit *>(CTUnit->TUData);
2745  return createCXString(CXXUnit->getOriginalSourceFileName(), true);
2746}
2747
2748CXCursor clang_getTranslationUnitCursor(CXTranslationUnit TU) {
2749  CXCursor Result = { CXCursor_TranslationUnit, 0, { 0, 0, TU } };
2750  return Result;
2751}
2752
2753} // end: extern "C"
2754
2755//===----------------------------------------------------------------------===//
2756// CXFile Operations.
2757//===----------------------------------------------------------------------===//
2758
2759extern "C" {
2760CXString clang_getFileName(CXFile SFile) {
2761  if (!SFile)
2762    return createCXString((const char*)NULL);
2763
2764  FileEntry *FEnt = static_cast<FileEntry *>(SFile);
2765  return createCXString(FEnt->getName());
2766}
2767
2768time_t clang_getFileTime(CXFile SFile) {
2769  if (!SFile)
2770    return 0;
2771
2772  FileEntry *FEnt = static_cast<FileEntry *>(SFile);
2773  return FEnt->getModificationTime();
2774}
2775
2776CXFile clang_getFile(CXTranslationUnit tu, const char *file_name) {
2777  if (!tu)
2778    return 0;
2779
2780  ASTUnit *CXXUnit = static_cast<ASTUnit *>(tu->TUData);
2781
2782  FileManager &FMgr = CXXUnit->getFileManager();
2783  return const_cast<FileEntry *>(FMgr.getFile(file_name));
2784}
2785
2786unsigned clang_isFileMultipleIncludeGuarded(CXTranslationUnit tu, CXFile file) {
2787  if (!tu || !file)
2788    return 0;
2789
2790  ASTUnit *CXXUnit = static_cast<ASTUnit *>(tu->TUData);
2791  FileEntry *FEnt = static_cast<FileEntry *>(file);
2792  return CXXUnit->getPreprocessor().getHeaderSearchInfo()
2793                                          .isFileMultipleIncludeGuarded(FEnt);
2794}
2795
2796} // end: extern "C"
2797
2798//===----------------------------------------------------------------------===//
2799// CXCursor Operations.
2800//===----------------------------------------------------------------------===//
2801
2802static Decl *getDeclFromExpr(Stmt *E) {
2803  if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E))
2804    return getDeclFromExpr(CE->getSubExpr());
2805
2806  if (DeclRefExpr *RefExpr = dyn_cast<DeclRefExpr>(E))
2807    return RefExpr->getDecl();
2808  if (BlockDeclRefExpr *RefExpr = dyn_cast<BlockDeclRefExpr>(E))
2809    return RefExpr->getDecl();
2810  if (MemberExpr *ME = dyn_cast<MemberExpr>(E))
2811    return ME->getMemberDecl();
2812  if (ObjCIvarRefExpr *RE = dyn_cast<ObjCIvarRefExpr>(E))
2813    return RE->getDecl();
2814  if (ObjCPropertyRefExpr *PRE = dyn_cast<ObjCPropertyRefExpr>(E))
2815    return PRE->isExplicitProperty() ? PRE->getExplicitProperty() : 0;
2816
2817  if (CallExpr *CE = dyn_cast<CallExpr>(E))
2818    return getDeclFromExpr(CE->getCallee());
2819  if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(E))
2820    if (!CE->isElidable())
2821    return CE->getConstructor();
2822  if (ObjCMessageExpr *OME = dyn_cast<ObjCMessageExpr>(E))
2823    return OME->getMethodDecl();
2824
2825  if (ObjCProtocolExpr *PE = dyn_cast<ObjCProtocolExpr>(E))
2826    return PE->getProtocol();
2827  if (SubstNonTypeTemplateParmPackExpr *NTTP
2828                              = dyn_cast<SubstNonTypeTemplateParmPackExpr>(E))
2829    return NTTP->getParameterPack();
2830  if (SizeOfPackExpr *SizeOfPack = dyn_cast<SizeOfPackExpr>(E))
2831    if (isa<NonTypeTemplateParmDecl>(SizeOfPack->getPack()) ||
2832        isa<ParmVarDecl>(SizeOfPack->getPack()))
2833      return SizeOfPack->getPack();
2834
2835  return 0;
2836}
2837
2838static SourceLocation getLocationFromExpr(Expr *E) {
2839  if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E))
2840    return getLocationFromExpr(CE->getSubExpr());
2841
2842  if (ObjCMessageExpr *Msg = dyn_cast<ObjCMessageExpr>(E))
2843    return /*FIXME:*/Msg->getLeftLoc();
2844  if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
2845    return DRE->getLocation();
2846  if (BlockDeclRefExpr *RefExpr = dyn_cast<BlockDeclRefExpr>(E))
2847    return RefExpr->getLocation();
2848  if (MemberExpr *Member = dyn_cast<MemberExpr>(E))
2849    return Member->getMemberLoc();
2850  if (ObjCIvarRefExpr *Ivar = dyn_cast<ObjCIvarRefExpr>(E))
2851    return Ivar->getLocation();
2852  if (SizeOfPackExpr *SizeOfPack = dyn_cast<SizeOfPackExpr>(E))
2853    return SizeOfPack->getPackLoc();
2854
2855  return E->getLocStart();
2856}
2857
2858extern "C" {
2859
2860unsigned clang_visitChildren(CXCursor parent,
2861                             CXCursorVisitor visitor,
2862                             CXClientData client_data) {
2863  CursorVisitor CursorVis(getCursorTU(parent), visitor, client_data,
2864                          /*VisitPreprocessorLast=*/false);
2865  return CursorVis.VisitChildren(parent);
2866}
2867
2868#ifndef __has_feature
2869#define __has_feature(x) 0
2870#endif
2871#if __has_feature(blocks)
2872typedef enum CXChildVisitResult
2873     (^CXCursorVisitorBlock)(CXCursor cursor, CXCursor parent);
2874
2875static enum CXChildVisitResult visitWithBlock(CXCursor cursor, CXCursor parent,
2876    CXClientData client_data) {
2877  CXCursorVisitorBlock block = (CXCursorVisitorBlock)client_data;
2878  return block(cursor, parent);
2879}
2880#else
2881// If we are compiled with a compiler that doesn't have native blocks support,
2882// define and call the block manually, so the
2883typedef struct _CXChildVisitResult
2884{
2885	void *isa;
2886	int flags;
2887	int reserved;
2888	enum CXChildVisitResult(*invoke)(struct _CXChildVisitResult*, CXCursor,
2889                                         CXCursor);
2890} *CXCursorVisitorBlock;
2891
2892static enum CXChildVisitResult visitWithBlock(CXCursor cursor, CXCursor parent,
2893    CXClientData client_data) {
2894  CXCursorVisitorBlock block = (CXCursorVisitorBlock)client_data;
2895  return block->invoke(block, cursor, parent);
2896}
2897#endif
2898
2899
2900unsigned clang_visitChildrenWithBlock(CXCursor parent,
2901                                      CXCursorVisitorBlock block) {
2902  return clang_visitChildren(parent, visitWithBlock, block);
2903}
2904
2905static CXString getDeclSpelling(Decl *D) {
2906  NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D);
2907  if (!ND) {
2908    if (ObjCPropertyImplDecl *PropImpl =dyn_cast<ObjCPropertyImplDecl>(D))
2909      if (ObjCPropertyDecl *Property = PropImpl->getPropertyDecl())
2910        return createCXString(Property->getIdentifier()->getName());
2911
2912    return createCXString("");
2913  }
2914
2915  if (ObjCMethodDecl *OMD = dyn_cast<ObjCMethodDecl>(ND))
2916    return createCXString(OMD->getSelector().getAsString());
2917
2918  if (ObjCCategoryImplDecl *CIMP = dyn_cast<ObjCCategoryImplDecl>(ND))
2919    // No, this isn't the same as the code below. getIdentifier() is non-virtual
2920    // and returns different names. NamedDecl returns the class name and
2921    // ObjCCategoryImplDecl returns the category name.
2922    return createCXString(CIMP->getIdentifier()->getNameStart());
2923
2924  if (isa<UsingDirectiveDecl>(D))
2925    return createCXString("");
2926
2927  llvm::SmallString<1024> S;
2928  llvm::raw_svector_ostream os(S);
2929  ND->printName(os);
2930
2931  return createCXString(os.str());
2932}
2933
2934CXString clang_getCursorSpelling(CXCursor C) {
2935  if (clang_isTranslationUnit(C.kind))
2936    return clang_getTranslationUnitSpelling(
2937                            static_cast<CXTranslationUnit>(C.data[2]));
2938
2939  if (clang_isReference(C.kind)) {
2940    switch (C.kind) {
2941    case CXCursor_ObjCSuperClassRef: {
2942      ObjCInterfaceDecl *Super = getCursorObjCSuperClassRef(C).first;
2943      return createCXString(Super->getIdentifier()->getNameStart());
2944    }
2945    case CXCursor_ObjCClassRef: {
2946      ObjCInterfaceDecl *Class = getCursorObjCClassRef(C).first;
2947      return createCXString(Class->getIdentifier()->getNameStart());
2948    }
2949    case CXCursor_ObjCProtocolRef: {
2950      ObjCProtocolDecl *OID = getCursorObjCProtocolRef(C).first;
2951      assert(OID && "getCursorSpelling(): Missing protocol decl");
2952      return createCXString(OID->getIdentifier()->getNameStart());
2953    }
2954    case CXCursor_CXXBaseSpecifier: {
2955      CXXBaseSpecifier *B = getCursorCXXBaseSpecifier(C);
2956      return createCXString(B->getType().getAsString());
2957    }
2958    case CXCursor_TypeRef: {
2959      TypeDecl *Type = getCursorTypeRef(C).first;
2960      assert(Type && "Missing type decl");
2961
2962      return createCXString(getCursorContext(C).getTypeDeclType(Type).
2963                              getAsString());
2964    }
2965    case CXCursor_TemplateRef: {
2966      TemplateDecl *Template = getCursorTemplateRef(C).first;
2967      assert(Template && "Missing template decl");
2968
2969      return createCXString(Template->getNameAsString());
2970    }
2971
2972    case CXCursor_NamespaceRef: {
2973      NamedDecl *NS = getCursorNamespaceRef(C).first;
2974      assert(NS && "Missing namespace decl");
2975
2976      return createCXString(NS->getNameAsString());
2977    }
2978
2979    case CXCursor_MemberRef: {
2980      FieldDecl *Field = getCursorMemberRef(C).first;
2981      assert(Field && "Missing member decl");
2982
2983      return createCXString(Field->getNameAsString());
2984    }
2985
2986    case CXCursor_LabelRef: {
2987      LabelStmt *Label = getCursorLabelRef(C).first;
2988      assert(Label && "Missing label");
2989
2990      return createCXString(Label->getName());
2991    }
2992
2993    case CXCursor_OverloadedDeclRef: {
2994      OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
2995      if (Decl *D = Storage.dyn_cast<Decl *>()) {
2996        if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
2997          return createCXString(ND->getNameAsString());
2998        return createCXString("");
2999      }
3000      if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
3001        return createCXString(E->getName().getAsString());
3002      OverloadedTemplateStorage *Ovl
3003        = Storage.get<OverloadedTemplateStorage*>();
3004      if (Ovl->size() == 0)
3005        return createCXString("");
3006      return createCXString((*Ovl->begin())->getNameAsString());
3007    }
3008
3009    default:
3010      return createCXString("<not implemented>");
3011    }
3012  }
3013
3014  if (clang_isExpression(C.kind)) {
3015    Decl *D = getDeclFromExpr(getCursorExpr(C));
3016    if (D)
3017      return getDeclSpelling(D);
3018    return createCXString("");
3019  }
3020
3021  if (clang_isStatement(C.kind)) {
3022    Stmt *S = getCursorStmt(C);
3023    if (LabelStmt *Label = dyn_cast_or_null<LabelStmt>(S))
3024      return createCXString(Label->getName());
3025
3026    return createCXString("");
3027  }
3028
3029  if (C.kind == CXCursor_MacroExpansion)
3030    return createCXString(getCursorMacroExpansion(C)->getName()
3031                                                           ->getNameStart());
3032
3033  if (C.kind == CXCursor_MacroDefinition)
3034    return createCXString(getCursorMacroDefinition(C)->getName()
3035                                                           ->getNameStart());
3036
3037  if (C.kind == CXCursor_InclusionDirective)
3038    return createCXString(getCursorInclusionDirective(C)->getFileName());
3039
3040  if (clang_isDeclaration(C.kind))
3041    return getDeclSpelling(getCursorDecl(C));
3042
3043  if (C.kind == CXCursor_AnnotateAttr) {
3044    AnnotateAttr *AA = cast<AnnotateAttr>(cxcursor::getCursorAttr(C));
3045    return createCXString(AA->getAnnotation());
3046  }
3047
3048  return createCXString("");
3049}
3050
3051CXString clang_getCursorDisplayName(CXCursor C) {
3052  if (!clang_isDeclaration(C.kind))
3053    return clang_getCursorSpelling(C);
3054
3055  Decl *D = getCursorDecl(C);
3056  if (!D)
3057    return createCXString("");
3058
3059  PrintingPolicy Policy = getCursorContext(C).getPrintingPolicy();
3060  if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D))
3061    D = FunTmpl->getTemplatedDecl();
3062
3063  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
3064    llvm::SmallString<64> Str;
3065    llvm::raw_svector_ostream OS(Str);
3066    OS << Function->getNameAsString();
3067    if (Function->getPrimaryTemplate())
3068      OS << "<>";
3069    OS << "(";
3070    for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) {
3071      if (I)
3072        OS << ", ";
3073      OS << Function->getParamDecl(I)->getType().getAsString(Policy);
3074    }
3075
3076    if (Function->isVariadic()) {
3077      if (Function->getNumParams())
3078        OS << ", ";
3079      OS << "...";
3080    }
3081    OS << ")";
3082    return createCXString(OS.str());
3083  }
3084
3085  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(D)) {
3086    llvm::SmallString<64> Str;
3087    llvm::raw_svector_ostream OS(Str);
3088    OS << ClassTemplate->getNameAsString();
3089    OS << "<";
3090    TemplateParameterList *Params = ClassTemplate->getTemplateParameters();
3091    for (unsigned I = 0, N = Params->size(); I != N; ++I) {
3092      if (I)
3093        OS << ", ";
3094
3095      NamedDecl *Param = Params->getParam(I);
3096      if (Param->getIdentifier()) {
3097        OS << Param->getIdentifier()->getName();
3098        continue;
3099      }
3100
3101      // There is no parameter name, which makes this tricky. Try to come up
3102      // with something useful that isn't too long.
3103      if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
3104        OS << (TTP->wasDeclaredWithTypename()? "typename" : "class");
3105      else if (NonTypeTemplateParmDecl *NTTP
3106                                    = dyn_cast<NonTypeTemplateParmDecl>(Param))
3107        OS << NTTP->getType().getAsString(Policy);
3108      else
3109        OS << "template<...> class";
3110    }
3111
3112    OS << ">";
3113    return createCXString(OS.str());
3114  }
3115
3116  if (ClassTemplateSpecializationDecl *ClassSpec
3117                              = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
3118    // If the type was explicitly written, use that.
3119    if (TypeSourceInfo *TSInfo = ClassSpec->getTypeAsWritten())
3120      return createCXString(TSInfo->getType().getAsString(Policy));
3121
3122    llvm::SmallString<64> Str;
3123    llvm::raw_svector_ostream OS(Str);
3124    OS << ClassSpec->getNameAsString();
3125    OS << TemplateSpecializationType::PrintTemplateArgumentList(
3126                                      ClassSpec->getTemplateArgs().data(),
3127                                      ClassSpec->getTemplateArgs().size(),
3128                                                                Policy);
3129    return createCXString(OS.str());
3130  }
3131
3132  return clang_getCursorSpelling(C);
3133}
3134
3135CXString clang_getCursorKindSpelling(enum CXCursorKind Kind) {
3136  switch (Kind) {
3137  case CXCursor_FunctionDecl:
3138      return createCXString("FunctionDecl");
3139  case CXCursor_TypedefDecl:
3140      return createCXString("TypedefDecl");
3141  case CXCursor_EnumDecl:
3142      return createCXString("EnumDecl");
3143  case CXCursor_EnumConstantDecl:
3144      return createCXString("EnumConstantDecl");
3145  case CXCursor_StructDecl:
3146      return createCXString("StructDecl");
3147  case CXCursor_UnionDecl:
3148      return createCXString("UnionDecl");
3149  case CXCursor_ClassDecl:
3150      return createCXString("ClassDecl");
3151  case CXCursor_FieldDecl:
3152      return createCXString("FieldDecl");
3153  case CXCursor_VarDecl:
3154      return createCXString("VarDecl");
3155  case CXCursor_ParmDecl:
3156      return createCXString("ParmDecl");
3157  case CXCursor_ObjCInterfaceDecl:
3158      return createCXString("ObjCInterfaceDecl");
3159  case CXCursor_ObjCCategoryDecl:
3160      return createCXString("ObjCCategoryDecl");
3161  case CXCursor_ObjCProtocolDecl:
3162      return createCXString("ObjCProtocolDecl");
3163  case CXCursor_ObjCPropertyDecl:
3164      return createCXString("ObjCPropertyDecl");
3165  case CXCursor_ObjCIvarDecl:
3166      return createCXString("ObjCIvarDecl");
3167  case CXCursor_ObjCInstanceMethodDecl:
3168      return createCXString("ObjCInstanceMethodDecl");
3169  case CXCursor_ObjCClassMethodDecl:
3170      return createCXString("ObjCClassMethodDecl");
3171  case CXCursor_ObjCImplementationDecl:
3172      return createCXString("ObjCImplementationDecl");
3173  case CXCursor_ObjCCategoryImplDecl:
3174      return createCXString("ObjCCategoryImplDecl");
3175  case CXCursor_CXXMethod:
3176      return createCXString("CXXMethod");
3177  case CXCursor_UnexposedDecl:
3178      return createCXString("UnexposedDecl");
3179  case CXCursor_ObjCSuperClassRef:
3180      return createCXString("ObjCSuperClassRef");
3181  case CXCursor_ObjCProtocolRef:
3182      return createCXString("ObjCProtocolRef");
3183  case CXCursor_ObjCClassRef:
3184      return createCXString("ObjCClassRef");
3185  case CXCursor_TypeRef:
3186      return createCXString("TypeRef");
3187  case CXCursor_TemplateRef:
3188      return createCXString("TemplateRef");
3189  case CXCursor_NamespaceRef:
3190    return createCXString("NamespaceRef");
3191  case CXCursor_MemberRef:
3192    return createCXString("MemberRef");
3193  case CXCursor_LabelRef:
3194    return createCXString("LabelRef");
3195  case CXCursor_OverloadedDeclRef:
3196    return createCXString("OverloadedDeclRef");
3197  case CXCursor_IntegerLiteral:
3198      return createCXString("IntegerLiteral");
3199  case CXCursor_FloatingLiteral:
3200      return createCXString("FloatingLiteral");
3201  case CXCursor_ImaginaryLiteral:
3202      return createCXString("ImaginaryLiteral");
3203  case CXCursor_StringLiteral:
3204      return createCXString("StringLiteral");
3205  case CXCursor_CharacterLiteral:
3206      return createCXString("CharacterLiteral");
3207  case CXCursor_ParenExpr:
3208      return createCXString("ParenExpr");
3209  case CXCursor_UnaryOperator:
3210      return createCXString("UnaryOperator");
3211  case CXCursor_ArraySubscriptExpr:
3212      return createCXString("ArraySubscriptExpr");
3213  case CXCursor_BinaryOperator:
3214      return createCXString("BinaryOperator");
3215  case CXCursor_CompoundAssignOperator:
3216      return createCXString("CompoundAssignOperator");
3217  case CXCursor_ConditionalOperator:
3218      return createCXString("ConditionalOperator");
3219  case CXCursor_CStyleCastExpr:
3220      return createCXString("CStyleCastExpr");
3221  case CXCursor_CompoundLiteralExpr:
3222      return createCXString("CompoundLiteralExpr");
3223  case CXCursor_InitListExpr:
3224      return createCXString("InitListExpr");
3225  case CXCursor_AddrLabelExpr:
3226      return createCXString("AddrLabelExpr");
3227  case CXCursor_StmtExpr:
3228      return createCXString("StmtExpr");
3229  case CXCursor_GenericSelectionExpr:
3230      return createCXString("GenericSelectionExpr");
3231  case CXCursor_GNUNullExpr:
3232      return createCXString("GNUNullExpr");
3233  case CXCursor_CXXStaticCastExpr:
3234      return createCXString("CXXStaticCastExpr");
3235  case CXCursor_CXXDynamicCastExpr:
3236      return createCXString("CXXDynamicCastExpr");
3237  case CXCursor_CXXReinterpretCastExpr:
3238      return createCXString("CXXReinterpretCastExpr");
3239  case CXCursor_CXXConstCastExpr:
3240      return createCXString("CXXConstCastExpr");
3241  case CXCursor_CXXFunctionalCastExpr:
3242      return createCXString("CXXFunctionalCastExpr");
3243  case CXCursor_CXXTypeidExpr:
3244      return createCXString("CXXTypeidExpr");
3245  case CXCursor_CXXBoolLiteralExpr:
3246      return createCXString("CXXBoolLiteralExpr");
3247  case CXCursor_CXXNullPtrLiteralExpr:
3248      return createCXString("CXXNullPtrLiteralExpr");
3249  case CXCursor_CXXThisExpr:
3250      return createCXString("CXXThisExpr");
3251  case CXCursor_CXXThrowExpr:
3252      return createCXString("CXXThrowExpr");
3253  case CXCursor_CXXNewExpr:
3254      return createCXString("CXXNewExpr");
3255  case CXCursor_CXXDeleteExpr:
3256      return createCXString("CXXDeleteExpr");
3257  case CXCursor_UnaryExpr:
3258      return createCXString("UnaryExpr");
3259  case CXCursor_ObjCStringLiteral:
3260      return createCXString("ObjCStringLiteral");
3261  case CXCursor_ObjCEncodeExpr:
3262      return createCXString("ObjCEncodeExpr");
3263  case CXCursor_ObjCSelectorExpr:
3264      return createCXString("ObjCSelectorExpr");
3265  case CXCursor_ObjCProtocolExpr:
3266      return createCXString("ObjCProtocolExpr");
3267  case CXCursor_ObjCBridgedCastExpr:
3268      return createCXString("ObjCBridgedCastExpr");
3269  case CXCursor_BlockExpr:
3270      return createCXString("BlockExpr");
3271  case CXCursor_PackExpansionExpr:
3272      return createCXString("PackExpansionExpr");
3273  case CXCursor_SizeOfPackExpr:
3274      return createCXString("SizeOfPackExpr");
3275  case CXCursor_UnexposedExpr:
3276      return createCXString("UnexposedExpr");
3277  case CXCursor_DeclRefExpr:
3278      return createCXString("DeclRefExpr");
3279  case CXCursor_MemberRefExpr:
3280      return createCXString("MemberRefExpr");
3281  case CXCursor_CallExpr:
3282      return createCXString("CallExpr");
3283  case CXCursor_ObjCMessageExpr:
3284      return createCXString("ObjCMessageExpr");
3285  case CXCursor_UnexposedStmt:
3286      return createCXString("UnexposedStmt");
3287  case CXCursor_DeclStmt:
3288      return createCXString("DeclStmt");
3289  case CXCursor_LabelStmt:
3290      return createCXString("LabelStmt");
3291  case CXCursor_CompoundStmt:
3292      return createCXString("CompoundStmt");
3293  case CXCursor_CaseStmt:
3294      return createCXString("CaseStmt");
3295  case CXCursor_DefaultStmt:
3296      return createCXString("DefaultStmt");
3297  case CXCursor_IfStmt:
3298      return createCXString("IfStmt");
3299  case CXCursor_SwitchStmt:
3300      return createCXString("SwitchStmt");
3301  case CXCursor_WhileStmt:
3302      return createCXString("WhileStmt");
3303  case CXCursor_DoStmt:
3304      return createCXString("DoStmt");
3305  case CXCursor_ForStmt:
3306      return createCXString("ForStmt");
3307  case CXCursor_GotoStmt:
3308      return createCXString("GotoStmt");
3309  case CXCursor_IndirectGotoStmt:
3310      return createCXString("IndirectGotoStmt");
3311  case CXCursor_ContinueStmt:
3312      return createCXString("ContinueStmt");
3313  case CXCursor_BreakStmt:
3314      return createCXString("BreakStmt");
3315  case CXCursor_ReturnStmt:
3316      return createCXString("ReturnStmt");
3317  case CXCursor_AsmStmt:
3318      return createCXString("AsmStmt");
3319  case CXCursor_ObjCAtTryStmt:
3320      return createCXString("ObjCAtTryStmt");
3321  case CXCursor_ObjCAtCatchStmt:
3322      return createCXString("ObjCAtCatchStmt");
3323  case CXCursor_ObjCAtFinallyStmt:
3324      return createCXString("ObjCAtFinallyStmt");
3325  case CXCursor_ObjCAtThrowStmt:
3326      return createCXString("ObjCAtThrowStmt");
3327  case CXCursor_ObjCAtSynchronizedStmt:
3328      return createCXString("ObjCAtSynchronizedStmt");
3329  case CXCursor_ObjCAutoreleasePoolStmt:
3330      return createCXString("ObjCAutoreleasePoolStmt");
3331  case CXCursor_ObjCForCollectionStmt:
3332      return createCXString("ObjCForCollectionStmt");
3333  case CXCursor_CXXCatchStmt:
3334      return createCXString("CXXCatchStmt");
3335  case CXCursor_CXXTryStmt:
3336      return createCXString("CXXTryStmt");
3337  case CXCursor_CXXForRangeStmt:
3338      return createCXString("CXXForRangeStmt");
3339  case CXCursor_SEHTryStmt:
3340      return createCXString("SEHTryStmt");
3341  case CXCursor_SEHExceptStmt:
3342      return createCXString("SEHExceptStmt");
3343  case CXCursor_SEHFinallyStmt:
3344      return createCXString("SEHFinallyStmt");
3345  case CXCursor_NullStmt:
3346      return createCXString("NullStmt");
3347  case CXCursor_InvalidFile:
3348      return createCXString("InvalidFile");
3349  case CXCursor_InvalidCode:
3350    return createCXString("InvalidCode");
3351  case CXCursor_NoDeclFound:
3352      return createCXString("NoDeclFound");
3353  case CXCursor_NotImplemented:
3354      return createCXString("NotImplemented");
3355  case CXCursor_TranslationUnit:
3356      return createCXString("TranslationUnit");
3357  case CXCursor_UnexposedAttr:
3358      return createCXString("UnexposedAttr");
3359  case CXCursor_IBActionAttr:
3360      return createCXString("attribute(ibaction)");
3361  case CXCursor_IBOutletAttr:
3362     return createCXString("attribute(iboutlet)");
3363  case CXCursor_IBOutletCollectionAttr:
3364      return createCXString("attribute(iboutletcollection)");
3365  case CXCursor_CXXFinalAttr:
3366      return createCXString("attribute(final)");
3367  case CXCursor_CXXOverrideAttr:
3368      return createCXString("attribute(override)");
3369  case CXCursor_AnnotateAttr:
3370    return createCXString("attribute(annotate)");
3371  case CXCursor_PreprocessingDirective:
3372    return createCXString("preprocessing directive");
3373  case CXCursor_MacroDefinition:
3374    return createCXString("macro definition");
3375  case CXCursor_MacroExpansion:
3376    return createCXString("macro expansion");
3377  case CXCursor_InclusionDirective:
3378    return createCXString("inclusion directive");
3379  case CXCursor_Namespace:
3380    return createCXString("Namespace");
3381  case CXCursor_LinkageSpec:
3382    return createCXString("LinkageSpec");
3383  case CXCursor_CXXBaseSpecifier:
3384    return createCXString("C++ base class specifier");
3385  case CXCursor_Constructor:
3386    return createCXString("CXXConstructor");
3387  case CXCursor_Destructor:
3388    return createCXString("CXXDestructor");
3389  case CXCursor_ConversionFunction:
3390    return createCXString("CXXConversion");
3391  case CXCursor_TemplateTypeParameter:
3392    return createCXString("TemplateTypeParameter");
3393  case CXCursor_NonTypeTemplateParameter:
3394    return createCXString("NonTypeTemplateParameter");
3395  case CXCursor_TemplateTemplateParameter:
3396    return createCXString("TemplateTemplateParameter");
3397  case CXCursor_FunctionTemplate:
3398    return createCXString("FunctionTemplate");
3399  case CXCursor_ClassTemplate:
3400    return createCXString("ClassTemplate");
3401  case CXCursor_ClassTemplatePartialSpecialization:
3402    return createCXString("ClassTemplatePartialSpecialization");
3403  case CXCursor_NamespaceAlias:
3404    return createCXString("NamespaceAlias");
3405  case CXCursor_UsingDirective:
3406    return createCXString("UsingDirective");
3407  case CXCursor_UsingDeclaration:
3408    return createCXString("UsingDeclaration");
3409  case CXCursor_TypeAliasDecl:
3410    return createCXString("TypeAliasDecl");
3411  case CXCursor_ObjCSynthesizeDecl:
3412    return createCXString("ObjCSynthesizeDecl");
3413  case CXCursor_ObjCDynamicDecl:
3414    return createCXString("ObjCDynamicDecl");
3415  case CXCursor_CXXAccessSpecifier:
3416    return createCXString("CXXAccessSpecifier");
3417  }
3418
3419  llvm_unreachable("Unhandled CXCursorKind");
3420  return createCXString((const char*) 0);
3421}
3422
3423struct GetCursorData {
3424  SourceLocation TokenBeginLoc;
3425  bool PointsAtMacroArgExpansion;
3426  CXCursor &BestCursor;
3427
3428  GetCursorData(SourceManager &SM,
3429                SourceLocation tokenBegin, CXCursor &outputCursor)
3430    : TokenBeginLoc(tokenBegin), BestCursor(outputCursor) {
3431    PointsAtMacroArgExpansion = SM.isMacroArgExpansion(tokenBegin);
3432  }
3433};
3434
3435static enum CXChildVisitResult GetCursorVisitor(CXCursor cursor,
3436                                                CXCursor parent,
3437                                                CXClientData client_data) {
3438  GetCursorData *Data = static_cast<GetCursorData *>(client_data);
3439  CXCursor *BestCursor = &Data->BestCursor;
3440
3441  // If we point inside a macro argument we should provide info of what the
3442  // token is so use the actual cursor, don't replace it with a macro expansion
3443  // cursor.
3444  if (cursor.kind == CXCursor_MacroExpansion && Data->PointsAtMacroArgExpansion)
3445    return CXChildVisit_Recurse;
3446
3447  if (clang_isDeclaration(cursor.kind)) {
3448    // Avoid having the implicit methods override the property decls.
3449    if (ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(getCursorDecl(cursor)))
3450      if (MD->isImplicit())
3451        return CXChildVisit_Break;
3452  }
3453
3454  if (clang_isExpression(cursor.kind) &&
3455      clang_isDeclaration(BestCursor->kind)) {
3456    Decl *D = getCursorDecl(*BestCursor);
3457
3458    // Avoid having the cursor of an expression replace the declaration cursor
3459    // when the expression source range overlaps the declaration range.
3460    // This can happen for C++ constructor expressions whose range generally
3461    // include the variable declaration, e.g.:
3462    //  MyCXXClass foo; // Make sure pointing at 'foo' returns a VarDecl cursor.
3463    if (D->getLocation().isValid() && Data->TokenBeginLoc.isValid() &&
3464        D->getLocation() == Data->TokenBeginLoc)
3465      return CXChildVisit_Break;
3466  }
3467
3468  // If our current best cursor is the construction of a temporary object,
3469  // don't replace that cursor with a type reference, because we want
3470  // clang_getCursor() to point at the constructor.
3471  if (clang_isExpression(BestCursor->kind) &&
3472      isa<CXXTemporaryObjectExpr>(getCursorExpr(*BestCursor)) &&
3473      cursor.kind == CXCursor_TypeRef) {
3474    // Keep the cursor pointing at CXXTemporaryObjectExpr but also mark it
3475    // as having the actual point on the type reference.
3476    *BestCursor = getTypeRefedCallExprCursor(*BestCursor);
3477    return CXChildVisit_Recurse;
3478  }
3479
3480  *BestCursor = cursor;
3481  return CXChildVisit_Recurse;
3482}
3483
3484CXCursor clang_getCursor(CXTranslationUnit TU, CXSourceLocation Loc) {
3485  if (!TU)
3486    return clang_getNullCursor();
3487
3488  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
3489  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
3490
3491  SourceLocation SLoc = cxloc::translateSourceLocation(Loc);
3492  CXCursor Result = cxcursor::getCursor(TU, SLoc);
3493
3494  bool Logging = getenv("LIBCLANG_LOGGING");
3495  if (Logging) {
3496    CXFile SearchFile;
3497    unsigned SearchLine, SearchColumn;
3498    CXFile ResultFile;
3499    unsigned ResultLine, ResultColumn;
3500    CXString SearchFileName, ResultFileName, KindSpelling, USR;
3501    const char *IsDef = clang_isCursorDefinition(Result)? " (Definition)" : "";
3502    CXSourceLocation ResultLoc = clang_getCursorLocation(Result);
3503
3504    clang_getExpansionLocation(Loc, &SearchFile, &SearchLine, &SearchColumn, 0);
3505    clang_getExpansionLocation(ResultLoc, &ResultFile, &ResultLine,
3506                               &ResultColumn, 0);
3507    SearchFileName = clang_getFileName(SearchFile);
3508    ResultFileName = clang_getFileName(ResultFile);
3509    KindSpelling = clang_getCursorKindSpelling(Result.kind);
3510    USR = clang_getCursorUSR(Result);
3511    fprintf(stderr, "clang_getCursor(%s:%d:%d) = %s(%s:%d:%d):%s%s\n",
3512            clang_getCString(SearchFileName), SearchLine, SearchColumn,
3513            clang_getCString(KindSpelling),
3514            clang_getCString(ResultFileName), ResultLine, ResultColumn,
3515            clang_getCString(USR), IsDef);
3516    clang_disposeString(SearchFileName);
3517    clang_disposeString(ResultFileName);
3518    clang_disposeString(KindSpelling);
3519    clang_disposeString(USR);
3520
3521    CXCursor Definition = clang_getCursorDefinition(Result);
3522    if (!clang_equalCursors(Definition, clang_getNullCursor())) {
3523      CXSourceLocation DefinitionLoc = clang_getCursorLocation(Definition);
3524      CXString DefinitionKindSpelling
3525                                = clang_getCursorKindSpelling(Definition.kind);
3526      CXFile DefinitionFile;
3527      unsigned DefinitionLine, DefinitionColumn;
3528      clang_getExpansionLocation(DefinitionLoc, &DefinitionFile,
3529                                 &DefinitionLine, &DefinitionColumn, 0);
3530      CXString DefinitionFileName = clang_getFileName(DefinitionFile);
3531      fprintf(stderr, "  -> %s(%s:%d:%d)\n",
3532              clang_getCString(DefinitionKindSpelling),
3533              clang_getCString(DefinitionFileName),
3534              DefinitionLine, DefinitionColumn);
3535      clang_disposeString(DefinitionFileName);
3536      clang_disposeString(DefinitionKindSpelling);
3537    }
3538  }
3539
3540  return Result;
3541}
3542
3543CXCursor clang_getNullCursor(void) {
3544  return MakeCXCursorInvalid(CXCursor_InvalidFile);
3545}
3546
3547unsigned clang_equalCursors(CXCursor X, CXCursor Y) {
3548  return X == Y;
3549}
3550
3551unsigned clang_hashCursor(CXCursor C) {
3552  unsigned Index = 0;
3553  if (clang_isExpression(C.kind) || clang_isStatement(C.kind))
3554    Index = 1;
3555
3556  return llvm::DenseMapInfo<std::pair<unsigned, void*> >::getHashValue(
3557                                        std::make_pair(C.kind, C.data[Index]));
3558}
3559
3560unsigned clang_isInvalid(enum CXCursorKind K) {
3561  return K >= CXCursor_FirstInvalid && K <= CXCursor_LastInvalid;
3562}
3563
3564unsigned clang_isDeclaration(enum CXCursorKind K) {
3565  return K >= CXCursor_FirstDecl && K <= CXCursor_LastDecl;
3566}
3567
3568unsigned clang_isReference(enum CXCursorKind K) {
3569  return K >= CXCursor_FirstRef && K <= CXCursor_LastRef;
3570}
3571
3572unsigned clang_isExpression(enum CXCursorKind K) {
3573  return K >= CXCursor_FirstExpr && K <= CXCursor_LastExpr;
3574}
3575
3576unsigned clang_isStatement(enum CXCursorKind K) {
3577  return K >= CXCursor_FirstStmt && K <= CXCursor_LastStmt;
3578}
3579
3580unsigned clang_isAttribute(enum CXCursorKind K) {
3581    return K >= CXCursor_FirstAttr && K <= CXCursor_LastAttr;
3582}
3583
3584unsigned clang_isTranslationUnit(enum CXCursorKind K) {
3585  return K == CXCursor_TranslationUnit;
3586}
3587
3588unsigned clang_isPreprocessing(enum CXCursorKind K) {
3589  return K >= CXCursor_FirstPreprocessing && K <= CXCursor_LastPreprocessing;
3590}
3591
3592unsigned clang_isUnexposed(enum CXCursorKind K) {
3593  switch (K) {
3594    case CXCursor_UnexposedDecl:
3595    case CXCursor_UnexposedExpr:
3596    case CXCursor_UnexposedStmt:
3597    case CXCursor_UnexposedAttr:
3598      return true;
3599    default:
3600      return false;
3601  }
3602}
3603
3604CXCursorKind clang_getCursorKind(CXCursor C) {
3605  return C.kind;
3606}
3607
3608CXSourceLocation clang_getCursorLocation(CXCursor C) {
3609  if (clang_isReference(C.kind)) {
3610    switch (C.kind) {
3611    case CXCursor_ObjCSuperClassRef: {
3612      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3613        = getCursorObjCSuperClassRef(C);
3614      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3615    }
3616
3617    case CXCursor_ObjCProtocolRef: {
3618      std::pair<ObjCProtocolDecl *, SourceLocation> P
3619        = getCursorObjCProtocolRef(C);
3620      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3621    }
3622
3623    case CXCursor_ObjCClassRef: {
3624      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3625        = getCursorObjCClassRef(C);
3626      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3627    }
3628
3629    case CXCursor_TypeRef: {
3630      std::pair<TypeDecl *, SourceLocation> P = getCursorTypeRef(C);
3631      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3632    }
3633
3634    case CXCursor_TemplateRef: {
3635      std::pair<TemplateDecl *, SourceLocation> P = getCursorTemplateRef(C);
3636      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3637    }
3638
3639    case CXCursor_NamespaceRef: {
3640      std::pair<NamedDecl *, SourceLocation> P = getCursorNamespaceRef(C);
3641      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3642    }
3643
3644    case CXCursor_MemberRef: {
3645      std::pair<FieldDecl *, SourceLocation> P = getCursorMemberRef(C);
3646      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3647    }
3648
3649    case CXCursor_CXXBaseSpecifier: {
3650      CXXBaseSpecifier *BaseSpec = getCursorCXXBaseSpecifier(C);
3651      if (!BaseSpec)
3652        return clang_getNullLocation();
3653
3654      if (TypeSourceInfo *TSInfo = BaseSpec->getTypeSourceInfo())
3655        return cxloc::translateSourceLocation(getCursorContext(C),
3656                                            TSInfo->getTypeLoc().getBeginLoc());
3657
3658      return cxloc::translateSourceLocation(getCursorContext(C),
3659                                        BaseSpec->getSourceRange().getBegin());
3660    }
3661
3662    case CXCursor_LabelRef: {
3663      std::pair<LabelStmt *, SourceLocation> P = getCursorLabelRef(C);
3664      return cxloc::translateSourceLocation(getCursorContext(C), P.second);
3665    }
3666
3667    case CXCursor_OverloadedDeclRef:
3668      return cxloc::translateSourceLocation(getCursorContext(C),
3669                                          getCursorOverloadedDeclRef(C).second);
3670
3671    default:
3672      // FIXME: Need a way to enumerate all non-reference cases.
3673      llvm_unreachable("Missed a reference kind");
3674    }
3675  }
3676
3677  if (clang_isExpression(C.kind))
3678    return cxloc::translateSourceLocation(getCursorContext(C),
3679                                   getLocationFromExpr(getCursorExpr(C)));
3680
3681  if (clang_isStatement(C.kind))
3682    return cxloc::translateSourceLocation(getCursorContext(C),
3683                                          getCursorStmt(C)->getLocStart());
3684
3685  if (C.kind == CXCursor_PreprocessingDirective) {
3686    SourceLocation L = cxcursor::getCursorPreprocessingDirective(C).getBegin();
3687    return cxloc::translateSourceLocation(getCursorContext(C), L);
3688  }
3689
3690  if (C.kind == CXCursor_MacroExpansion) {
3691    SourceLocation L
3692      = cxcursor::getCursorMacroExpansion(C)->getSourceRange().getBegin();
3693    return cxloc::translateSourceLocation(getCursorContext(C), L);
3694  }
3695
3696  if (C.kind == CXCursor_MacroDefinition) {
3697    SourceLocation L = cxcursor::getCursorMacroDefinition(C)->getLocation();
3698    return cxloc::translateSourceLocation(getCursorContext(C), L);
3699  }
3700
3701  if (C.kind == CXCursor_InclusionDirective) {
3702    SourceLocation L
3703      = cxcursor::getCursorInclusionDirective(C)->getSourceRange().getBegin();
3704    return cxloc::translateSourceLocation(getCursorContext(C), L);
3705  }
3706
3707  if (C.kind < CXCursor_FirstDecl || C.kind > CXCursor_LastDecl)
3708    return clang_getNullLocation();
3709
3710  Decl *D = getCursorDecl(C);
3711  SourceLocation Loc = D->getLocation();
3712  // FIXME: Multiple variables declared in a single declaration
3713  // currently lack the information needed to correctly determine their
3714  // ranges when accounting for the type-specifier.  We use context
3715  // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3716  // and if so, whether it is the first decl.
3717  if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3718    if (!cxcursor::isFirstInDeclGroup(C))
3719      Loc = VD->getLocation();
3720  }
3721
3722  return cxloc::translateSourceLocation(getCursorContext(C), Loc);
3723}
3724
3725} // end extern "C"
3726
3727CXCursor cxcursor::getCursor(CXTranslationUnit TU, SourceLocation SLoc) {
3728  assert(TU);
3729
3730  // Guard against an invalid SourceLocation, or we may assert in one
3731  // of the following calls.
3732  if (SLoc.isInvalid())
3733    return clang_getNullCursor();
3734
3735  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
3736
3737  // Translate the given source location to make it point at the beginning of
3738  // the token under the cursor.
3739  SLoc = Lexer::GetBeginningOfToken(SLoc, CXXUnit->getSourceManager(),
3740                                    CXXUnit->getASTContext().getLangOptions());
3741
3742  CXCursor Result = MakeCXCursorInvalid(CXCursor_NoDeclFound);
3743  if (SLoc.isValid()) {
3744    // FIXME: Would be great to have a "hint" cursor, then walk from that
3745    // hint cursor upward until we find a cursor whose source range encloses
3746    // the region of interest, rather than starting from the translation unit.
3747    GetCursorData ResultData(CXXUnit->getSourceManager(), SLoc, Result);
3748    CXCursor Parent = clang_getTranslationUnitCursor(TU);
3749    CursorVisitor CursorVis(TU, GetCursorVisitor, &ResultData,
3750                            /*VisitPreprocessorLast=*/true,
3751                            /*VisitIncludedEntities=*/false,
3752                            SourceLocation(SLoc));
3753    CursorVis.VisitChildren(Parent);
3754  }
3755
3756  return Result;
3757}
3758
3759static SourceRange getRawCursorExtent(CXCursor C) {
3760  if (clang_isReference(C.kind)) {
3761    switch (C.kind) {
3762    case CXCursor_ObjCSuperClassRef:
3763      return  getCursorObjCSuperClassRef(C).second;
3764
3765    case CXCursor_ObjCProtocolRef:
3766      return getCursorObjCProtocolRef(C).second;
3767
3768    case CXCursor_ObjCClassRef:
3769      return getCursorObjCClassRef(C).second;
3770
3771    case CXCursor_TypeRef:
3772      return getCursorTypeRef(C).second;
3773
3774    case CXCursor_TemplateRef:
3775      return getCursorTemplateRef(C).second;
3776
3777    case CXCursor_NamespaceRef:
3778      return getCursorNamespaceRef(C).second;
3779
3780    case CXCursor_MemberRef:
3781      return getCursorMemberRef(C).second;
3782
3783    case CXCursor_CXXBaseSpecifier:
3784      return getCursorCXXBaseSpecifier(C)->getSourceRange();
3785
3786    case CXCursor_LabelRef:
3787      return getCursorLabelRef(C).second;
3788
3789    case CXCursor_OverloadedDeclRef:
3790      return getCursorOverloadedDeclRef(C).second;
3791
3792    default:
3793      // FIXME: Need a way to enumerate all non-reference cases.
3794      llvm_unreachable("Missed a reference kind");
3795    }
3796  }
3797
3798  if (clang_isExpression(C.kind))
3799    return getCursorExpr(C)->getSourceRange();
3800
3801  if (clang_isStatement(C.kind))
3802    return getCursorStmt(C)->getSourceRange();
3803
3804  if (clang_isAttribute(C.kind))
3805    return getCursorAttr(C)->getRange();
3806
3807  if (C.kind == CXCursor_PreprocessingDirective)
3808    return cxcursor::getCursorPreprocessingDirective(C);
3809
3810  if (C.kind == CXCursor_MacroExpansion) {
3811    ASTUnit *TU = getCursorASTUnit(C);
3812    SourceRange Range = cxcursor::getCursorMacroExpansion(C)->getSourceRange();
3813    return TU->mapRangeFromPreamble(Range);
3814  }
3815
3816  if (C.kind == CXCursor_MacroDefinition) {
3817    ASTUnit *TU = getCursorASTUnit(C);
3818    SourceRange Range = cxcursor::getCursorMacroDefinition(C)->getSourceRange();
3819    return TU->mapRangeFromPreamble(Range);
3820  }
3821
3822  if (C.kind == CXCursor_InclusionDirective) {
3823    ASTUnit *TU = getCursorASTUnit(C);
3824    SourceRange Range = cxcursor::getCursorInclusionDirective(C)->getSourceRange();
3825    return TU->mapRangeFromPreamble(Range);
3826  }
3827
3828  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3829    Decl *D = cxcursor::getCursorDecl(C);
3830    SourceRange R = D->getSourceRange();
3831    // FIXME: Multiple variables declared in a single declaration
3832    // currently lack the information needed to correctly determine their
3833    // ranges when accounting for the type-specifier.  We use context
3834    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3835    // and if so, whether it is the first decl.
3836    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3837      if (!cxcursor::isFirstInDeclGroup(C))
3838        R.setBegin(VD->getLocation());
3839    }
3840    return R;
3841  }
3842  return SourceRange();
3843}
3844
3845/// \brief Retrieves the "raw" cursor extent, which is then extended to include
3846/// the decl-specifier-seq for declarations.
3847static SourceRange getFullCursorExtent(CXCursor C, SourceManager &SrcMgr) {
3848  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3849    Decl *D = cxcursor::getCursorDecl(C);
3850    SourceRange R = D->getSourceRange();
3851
3852    // Adjust the start of the location for declarations preceded by
3853    // declaration specifiers.
3854    SourceLocation StartLoc;
3855    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
3856      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
3857        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3858    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
3859      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
3860        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3861    }
3862
3863    if (StartLoc.isValid() && R.getBegin().isValid() &&
3864        SrcMgr.isBeforeInTranslationUnit(StartLoc, R.getBegin()))
3865      R.setBegin(StartLoc);
3866
3867    // FIXME: Multiple variables declared in a single declaration
3868    // currently lack the information needed to correctly determine their
3869    // ranges when accounting for the type-specifier.  We use context
3870    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3871    // and if so, whether it is the first decl.
3872    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3873      if (!cxcursor::isFirstInDeclGroup(C))
3874        R.setBegin(VD->getLocation());
3875    }
3876
3877    return R;
3878  }
3879
3880  return getRawCursorExtent(C);
3881}
3882
3883extern "C" {
3884
3885CXSourceRange clang_getCursorExtent(CXCursor C) {
3886  SourceRange R = getRawCursorExtent(C);
3887  if (R.isInvalid())
3888    return clang_getNullRange();
3889
3890  return cxloc::translateSourceRange(getCursorContext(C), R);
3891}
3892
3893CXCursor clang_getCursorReferenced(CXCursor C) {
3894  if (clang_isInvalid(C.kind))
3895    return clang_getNullCursor();
3896
3897  CXTranslationUnit tu = getCursorTU(C);
3898  if (clang_isDeclaration(C.kind)) {
3899    Decl *D = getCursorDecl(C);
3900    if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
3901      return MakeCursorOverloadedDeclRef(Using, D->getLocation(), tu);
3902    if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
3903      return MakeCursorOverloadedDeclRef(Classes, D->getLocation(), tu);
3904    if (ObjCForwardProtocolDecl *Protocols
3905                                        = dyn_cast<ObjCForwardProtocolDecl>(D))
3906      return MakeCursorOverloadedDeclRef(Protocols, D->getLocation(), tu);
3907    if (ObjCPropertyImplDecl *PropImpl =dyn_cast<ObjCPropertyImplDecl>(D))
3908      if (ObjCPropertyDecl *Property = PropImpl->getPropertyDecl())
3909        return MakeCXCursor(Property, tu);
3910
3911    return C;
3912  }
3913
3914  if (clang_isExpression(C.kind)) {
3915    Expr *E = getCursorExpr(C);
3916    Decl *D = getDeclFromExpr(E);
3917    if (D) {
3918      CXCursor declCursor = MakeCXCursor(D, tu);
3919      declCursor = getSelectorIdentifierCursor(getSelectorIdentifierIndex(C),
3920                                               declCursor);
3921      return declCursor;
3922    }
3923
3924    if (OverloadExpr *Ovl = dyn_cast_or_null<OverloadExpr>(E))
3925      return MakeCursorOverloadedDeclRef(Ovl, tu);
3926
3927    return clang_getNullCursor();
3928  }
3929
3930  if (clang_isStatement(C.kind)) {
3931    Stmt *S = getCursorStmt(C);
3932    if (GotoStmt *Goto = dyn_cast_or_null<GotoStmt>(S))
3933      if (LabelDecl *label = Goto->getLabel())
3934        if (LabelStmt *labelS = label->getStmt())
3935        return MakeCXCursor(labelS, getCursorDecl(C), tu);
3936
3937    return clang_getNullCursor();
3938  }
3939
3940  if (C.kind == CXCursor_MacroExpansion) {
3941    if (MacroDefinition *Def = getCursorMacroExpansion(C)->getDefinition())
3942      return MakeMacroDefinitionCursor(Def, tu);
3943  }
3944
3945  if (!clang_isReference(C.kind))
3946    return clang_getNullCursor();
3947
3948  switch (C.kind) {
3949    case CXCursor_ObjCSuperClassRef:
3950      return MakeCXCursor(getCursorObjCSuperClassRef(C).first, tu);
3951
3952    case CXCursor_ObjCProtocolRef: {
3953      return MakeCXCursor(getCursorObjCProtocolRef(C).first, tu);
3954
3955    case CXCursor_ObjCClassRef:
3956      return MakeCXCursor(getCursorObjCClassRef(C).first, tu );
3957
3958    case CXCursor_TypeRef:
3959      return MakeCXCursor(getCursorTypeRef(C).first, tu );
3960
3961    case CXCursor_TemplateRef:
3962      return MakeCXCursor(getCursorTemplateRef(C).first, tu );
3963
3964    case CXCursor_NamespaceRef:
3965      return MakeCXCursor(getCursorNamespaceRef(C).first, tu );
3966
3967    case CXCursor_MemberRef:
3968      return MakeCXCursor(getCursorMemberRef(C).first, tu );
3969
3970    case CXCursor_CXXBaseSpecifier: {
3971      CXXBaseSpecifier *B = cxcursor::getCursorCXXBaseSpecifier(C);
3972      return clang_getTypeDeclaration(cxtype::MakeCXType(B->getType(),
3973                                                         tu ));
3974    }
3975
3976    case CXCursor_LabelRef:
3977      // FIXME: We end up faking the "parent" declaration here because we
3978      // don't want to make CXCursor larger.
3979      return MakeCXCursor(getCursorLabelRef(C).first,
3980               static_cast<ASTUnit*>(tu->TUData)->getASTContext()
3981                          .getTranslationUnitDecl(),
3982                          tu);
3983
3984    case CXCursor_OverloadedDeclRef:
3985      return C;
3986
3987    default:
3988      // We would prefer to enumerate all non-reference cursor kinds here.
3989      llvm_unreachable("Unhandled reference cursor kind");
3990      break;
3991    }
3992  }
3993
3994  return clang_getNullCursor();
3995}
3996
3997CXCursor clang_getCursorDefinition(CXCursor C) {
3998  if (clang_isInvalid(C.kind))
3999    return clang_getNullCursor();
4000
4001  CXTranslationUnit TU = getCursorTU(C);
4002
4003  bool WasReference = false;
4004  if (clang_isReference(C.kind) || clang_isExpression(C.kind)) {
4005    C = clang_getCursorReferenced(C);
4006    WasReference = true;
4007  }
4008
4009  if (C.kind == CXCursor_MacroExpansion)
4010    return clang_getCursorReferenced(C);
4011
4012  if (!clang_isDeclaration(C.kind))
4013    return clang_getNullCursor();
4014
4015  Decl *D = getCursorDecl(C);
4016  if (!D)
4017    return clang_getNullCursor();
4018
4019  switch (D->getKind()) {
4020  // Declaration kinds that don't really separate the notions of
4021  // declaration and definition.
4022  case Decl::Namespace:
4023  case Decl::Typedef:
4024  case Decl::TypeAlias:
4025  case Decl::TypeAliasTemplate:
4026  case Decl::TemplateTypeParm:
4027  case Decl::EnumConstant:
4028  case Decl::Field:
4029  case Decl::IndirectField:
4030  case Decl::ObjCIvar:
4031  case Decl::ObjCAtDefsField:
4032  case Decl::ImplicitParam:
4033  case Decl::ParmVar:
4034  case Decl::NonTypeTemplateParm:
4035  case Decl::TemplateTemplateParm:
4036  case Decl::ObjCCategoryImpl:
4037  case Decl::ObjCImplementation:
4038  case Decl::AccessSpec:
4039  case Decl::LinkageSpec:
4040  case Decl::ObjCPropertyImpl:
4041  case Decl::FileScopeAsm:
4042  case Decl::StaticAssert:
4043  case Decl::Block:
4044  case Decl::Label:  // FIXME: Is this right??
4045  case Decl::ClassScopeFunctionSpecialization:
4046    return C;
4047
4048  // Declaration kinds that don't make any sense here, but are
4049  // nonetheless harmless.
4050  case Decl::TranslationUnit:
4051    break;
4052
4053  // Declaration kinds for which the definition is not resolvable.
4054  case Decl::UnresolvedUsingTypename:
4055  case Decl::UnresolvedUsingValue:
4056    break;
4057
4058  case Decl::UsingDirective:
4059    return MakeCXCursor(cast<UsingDirectiveDecl>(D)->getNominatedNamespace(),
4060                        TU);
4061
4062  case Decl::NamespaceAlias:
4063    return MakeCXCursor(cast<NamespaceAliasDecl>(D)->getNamespace(), TU);
4064
4065  case Decl::Enum:
4066  case Decl::Record:
4067  case Decl::CXXRecord:
4068  case Decl::ClassTemplateSpecialization:
4069  case Decl::ClassTemplatePartialSpecialization:
4070    if (TagDecl *Def = cast<TagDecl>(D)->getDefinition())
4071      return MakeCXCursor(Def, TU);
4072    return clang_getNullCursor();
4073
4074  case Decl::Function:
4075  case Decl::CXXMethod:
4076  case Decl::CXXConstructor:
4077  case Decl::CXXDestructor:
4078  case Decl::CXXConversion: {
4079    const FunctionDecl *Def = 0;
4080    if (cast<FunctionDecl>(D)->getBody(Def))
4081      return MakeCXCursor(const_cast<FunctionDecl *>(Def), TU);
4082    return clang_getNullCursor();
4083  }
4084
4085  case Decl::Var: {
4086    // Ask the variable if it has a definition.
4087    if (VarDecl *Def = cast<VarDecl>(D)->getDefinition())
4088      return MakeCXCursor(Def, TU);
4089    return clang_getNullCursor();
4090  }
4091
4092  case Decl::FunctionTemplate: {
4093    const FunctionDecl *Def = 0;
4094    if (cast<FunctionTemplateDecl>(D)->getTemplatedDecl()->getBody(Def))
4095      return MakeCXCursor(Def->getDescribedFunctionTemplate(), TU);
4096    return clang_getNullCursor();
4097  }
4098
4099  case Decl::ClassTemplate: {
4100    if (RecordDecl *Def = cast<ClassTemplateDecl>(D)->getTemplatedDecl()
4101                                                            ->getDefinition())
4102      return MakeCXCursor(cast<CXXRecordDecl>(Def)->getDescribedClassTemplate(),
4103                          TU);
4104    return clang_getNullCursor();
4105  }
4106
4107  case Decl::Using:
4108    return MakeCursorOverloadedDeclRef(cast<UsingDecl>(D),
4109                                       D->getLocation(), TU);
4110
4111  case Decl::UsingShadow:
4112    return clang_getCursorDefinition(
4113                       MakeCXCursor(cast<UsingShadowDecl>(D)->getTargetDecl(),
4114                                    TU));
4115
4116  case Decl::ObjCMethod: {
4117    ObjCMethodDecl *Method = cast<ObjCMethodDecl>(D);
4118    if (Method->isThisDeclarationADefinition())
4119      return C;
4120
4121    // Dig out the method definition in the associated
4122    // @implementation, if we have it.
4123    // FIXME: The ASTs should make finding the definition easier.
4124    if (ObjCInterfaceDecl *Class
4125                       = dyn_cast<ObjCInterfaceDecl>(Method->getDeclContext()))
4126      if (ObjCImplementationDecl *ClassImpl = Class->getImplementation())
4127        if (ObjCMethodDecl *Def = ClassImpl->getMethod(Method->getSelector(),
4128                                                  Method->isInstanceMethod()))
4129          if (Def->isThisDeclarationADefinition())
4130            return MakeCXCursor(Def, TU);
4131
4132    return clang_getNullCursor();
4133  }
4134
4135  case Decl::ObjCCategory:
4136    if (ObjCCategoryImplDecl *Impl
4137                               = cast<ObjCCategoryDecl>(D)->getImplementation())
4138      return MakeCXCursor(Impl, TU);
4139    return clang_getNullCursor();
4140
4141  case Decl::ObjCProtocol:
4142    if (!cast<ObjCProtocolDecl>(D)->isForwardDecl())
4143      return C;
4144    return clang_getNullCursor();
4145
4146  case Decl::ObjCInterface:
4147    // There are two notions of a "definition" for an Objective-C
4148    // class: the interface and its implementation. When we resolved a
4149    // reference to an Objective-C class, produce the @interface as
4150    // the definition; when we were provided with the interface,
4151    // produce the @implementation as the definition.
4152    if (WasReference) {
4153      if (!cast<ObjCInterfaceDecl>(D)->isForwardDecl())
4154        return C;
4155    } else if (ObjCImplementationDecl *Impl
4156                              = cast<ObjCInterfaceDecl>(D)->getImplementation())
4157      return MakeCXCursor(Impl, TU);
4158    return clang_getNullCursor();
4159
4160  case Decl::ObjCProperty:
4161    // FIXME: We don't really know where to find the
4162    // ObjCPropertyImplDecls that implement this property.
4163    return clang_getNullCursor();
4164
4165  case Decl::ObjCCompatibleAlias:
4166    if (ObjCInterfaceDecl *Class
4167          = cast<ObjCCompatibleAliasDecl>(D)->getClassInterface())
4168      if (!Class->isForwardDecl())
4169        return MakeCXCursor(Class, TU);
4170
4171    return clang_getNullCursor();
4172
4173  case Decl::ObjCForwardProtocol:
4174    return MakeCursorOverloadedDeclRef(cast<ObjCForwardProtocolDecl>(D),
4175                                       D->getLocation(), TU);
4176
4177  case Decl::ObjCClass:
4178    return MakeCursorOverloadedDeclRef(cast<ObjCClassDecl>(D), D->getLocation(),
4179                                       TU);
4180
4181  case Decl::Friend:
4182    if (NamedDecl *Friend = cast<FriendDecl>(D)->getFriendDecl())
4183      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4184    return clang_getNullCursor();
4185
4186  case Decl::FriendTemplate:
4187    if (NamedDecl *Friend = cast<FriendTemplateDecl>(D)->getFriendDecl())
4188      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4189    return clang_getNullCursor();
4190  }
4191
4192  return clang_getNullCursor();
4193}
4194
4195unsigned clang_isCursorDefinition(CXCursor C) {
4196  if (!clang_isDeclaration(C.kind))
4197    return 0;
4198
4199  return clang_getCursorDefinition(C) == C;
4200}
4201
4202CXCursor clang_getCanonicalCursor(CXCursor C) {
4203  if (!clang_isDeclaration(C.kind))
4204    return C;
4205
4206  if (Decl *D = getCursorDecl(C)) {
4207    if (ObjCCategoryImplDecl *CatImplD = dyn_cast<ObjCCategoryImplDecl>(D))
4208      if (ObjCCategoryDecl *CatD = CatImplD->getCategoryDecl())
4209        return MakeCXCursor(CatD, getCursorTU(C));
4210
4211    if (ObjCImplDecl *ImplD = dyn_cast<ObjCImplDecl>(D))
4212      if (ObjCInterfaceDecl *IFD = ImplD->getClassInterface())
4213        return MakeCXCursor(IFD, getCursorTU(C));
4214
4215    return MakeCXCursor(D->getCanonicalDecl(), getCursorTU(C));
4216  }
4217
4218  return C;
4219}
4220
4221unsigned clang_getNumOverloadedDecls(CXCursor C) {
4222  if (C.kind != CXCursor_OverloadedDeclRef)
4223    return 0;
4224
4225  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
4226  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4227    return E->getNumDecls();
4228
4229  if (OverloadedTemplateStorage *S
4230                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4231    return S->size();
4232
4233  Decl *D = Storage.get<Decl*>();
4234  if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
4235    return Using->shadow_size();
4236  if (isa<ObjCClassDecl>(D))
4237    return 1;
4238  if (ObjCForwardProtocolDecl *Protocols =dyn_cast<ObjCForwardProtocolDecl>(D))
4239    return Protocols->protocol_size();
4240
4241  return 0;
4242}
4243
4244CXCursor clang_getOverloadedDecl(CXCursor cursor, unsigned index) {
4245  if (cursor.kind != CXCursor_OverloadedDeclRef)
4246    return clang_getNullCursor();
4247
4248  if (index >= clang_getNumOverloadedDecls(cursor))
4249    return clang_getNullCursor();
4250
4251  CXTranslationUnit TU = getCursorTU(cursor);
4252  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(cursor).first;
4253  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4254    return MakeCXCursor(E->decls_begin()[index], TU);
4255
4256  if (OverloadedTemplateStorage *S
4257                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4258    return MakeCXCursor(S->begin()[index], TU);
4259
4260  Decl *D = Storage.get<Decl*>();
4261  if (UsingDecl *Using = dyn_cast<UsingDecl>(D)) {
4262    // FIXME: This is, unfortunately, linear time.
4263    UsingDecl::shadow_iterator Pos = Using->shadow_begin();
4264    std::advance(Pos, index);
4265    return MakeCXCursor(cast<UsingShadowDecl>(*Pos)->getTargetDecl(), TU);
4266  }
4267  if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
4268    return MakeCXCursor(Classes->getForwardInterfaceDecl(), TU);
4269  if (ObjCForwardProtocolDecl *Protocols = dyn_cast<ObjCForwardProtocolDecl>(D))
4270    return MakeCXCursor(Protocols->protocol_begin()[index], TU);
4271
4272  return clang_getNullCursor();
4273}
4274
4275void clang_getDefinitionSpellingAndExtent(CXCursor C,
4276                                          const char **startBuf,
4277                                          const char **endBuf,
4278                                          unsigned *startLine,
4279                                          unsigned *startColumn,
4280                                          unsigned *endLine,
4281                                          unsigned *endColumn) {
4282  assert(getCursorDecl(C) && "CXCursor has null decl");
4283  NamedDecl *ND = static_cast<NamedDecl *>(getCursorDecl(C));
4284  FunctionDecl *FD = dyn_cast<FunctionDecl>(ND);
4285  CompoundStmt *Body = dyn_cast<CompoundStmt>(FD->getBody());
4286
4287  SourceManager &SM = FD->getASTContext().getSourceManager();
4288  *startBuf = SM.getCharacterData(Body->getLBracLoc());
4289  *endBuf = SM.getCharacterData(Body->getRBracLoc());
4290  *startLine = SM.getSpellingLineNumber(Body->getLBracLoc());
4291  *startColumn = SM.getSpellingColumnNumber(Body->getLBracLoc());
4292  *endLine = SM.getSpellingLineNumber(Body->getRBracLoc());
4293  *endColumn = SM.getSpellingColumnNumber(Body->getRBracLoc());
4294}
4295
4296
4297CXSourceRange clang_getCursorReferenceNameRange(CXCursor C, unsigned NameFlags,
4298                                                unsigned PieceIndex) {
4299  RefNamePieces Pieces;
4300
4301  switch (C.kind) {
4302  case CXCursor_MemberRefExpr:
4303    if (MemberExpr *E = dyn_cast<MemberExpr>(getCursorExpr(C)))
4304      Pieces = buildPieces(NameFlags, true, E->getMemberNameInfo(),
4305                           E->getQualifierLoc().getSourceRange());
4306    break;
4307
4308  case CXCursor_DeclRefExpr:
4309    if (DeclRefExpr *E = dyn_cast<DeclRefExpr>(getCursorExpr(C)))
4310      Pieces = buildPieces(NameFlags, false, E->getNameInfo(),
4311                           E->getQualifierLoc().getSourceRange(),
4312                           E->getExplicitTemplateArgsOpt());
4313    break;
4314
4315  case CXCursor_CallExpr:
4316    if (CXXOperatorCallExpr *OCE =
4317        dyn_cast<CXXOperatorCallExpr>(getCursorExpr(C))) {
4318      Expr *Callee = OCE->getCallee();
4319      if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Callee))
4320        Callee = ICE->getSubExpr();
4321
4322      if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Callee))
4323        Pieces = buildPieces(NameFlags, false, DRE->getNameInfo(),
4324                             DRE->getQualifierLoc().getSourceRange());
4325    }
4326    break;
4327
4328  default:
4329    break;
4330  }
4331
4332  if (Pieces.empty()) {
4333    if (PieceIndex == 0)
4334      return clang_getCursorExtent(C);
4335  } else if (PieceIndex < Pieces.size()) {
4336      SourceRange R = Pieces[PieceIndex];
4337      if (R.isValid())
4338        return cxloc::translateSourceRange(getCursorContext(C), R);
4339  }
4340
4341  return clang_getNullRange();
4342}
4343
4344void clang_enableStackTraces(void) {
4345  llvm::sys::PrintStackTraceOnErrorSignal();
4346}
4347
4348void clang_executeOnThread(void (*fn)(void*), void *user_data,
4349                           unsigned stack_size) {
4350  llvm::llvm_execute_on_thread(fn, user_data, stack_size);
4351}
4352
4353} // end: extern "C"
4354
4355//===----------------------------------------------------------------------===//
4356// Token-based Operations.
4357//===----------------------------------------------------------------------===//
4358
4359/* CXToken layout:
4360 *   int_data[0]: a CXTokenKind
4361 *   int_data[1]: starting token location
4362 *   int_data[2]: token length
4363 *   int_data[3]: reserved
4364 *   ptr_data: for identifiers and keywords, an IdentifierInfo*.
4365 *   otherwise unused.
4366 */
4367extern "C" {
4368
4369CXTokenKind clang_getTokenKind(CXToken CXTok) {
4370  return static_cast<CXTokenKind>(CXTok.int_data[0]);
4371}
4372
4373CXString clang_getTokenSpelling(CXTranslationUnit TU, CXToken CXTok) {
4374  switch (clang_getTokenKind(CXTok)) {
4375  case CXToken_Identifier:
4376  case CXToken_Keyword:
4377    // We know we have an IdentifierInfo*, so use that.
4378    return createCXString(static_cast<IdentifierInfo *>(CXTok.ptr_data)
4379                            ->getNameStart());
4380
4381  case CXToken_Literal: {
4382    // We have stashed the starting pointer in the ptr_data field. Use it.
4383    const char *Text = static_cast<const char *>(CXTok.ptr_data);
4384    return createCXString(StringRef(Text, CXTok.int_data[2]));
4385  }
4386
4387  case CXToken_Punctuation:
4388  case CXToken_Comment:
4389    break;
4390  }
4391
4392  // We have to find the starting buffer pointer the hard way, by
4393  // deconstructing the source location.
4394  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4395  if (!CXXUnit)
4396    return createCXString("");
4397
4398  SourceLocation Loc = SourceLocation::getFromRawEncoding(CXTok.int_data[1]);
4399  std::pair<FileID, unsigned> LocInfo
4400    = CXXUnit->getSourceManager().getDecomposedSpellingLoc(Loc);
4401  bool Invalid = false;
4402  StringRef Buffer
4403    = CXXUnit->getSourceManager().getBufferData(LocInfo.first, &Invalid);
4404  if (Invalid)
4405    return createCXString("");
4406
4407  return createCXString(Buffer.substr(LocInfo.second, CXTok.int_data[2]));
4408}
4409
4410CXSourceLocation clang_getTokenLocation(CXTranslationUnit TU, CXToken CXTok) {
4411  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4412  if (!CXXUnit)
4413    return clang_getNullLocation();
4414
4415  return cxloc::translateSourceLocation(CXXUnit->getASTContext(),
4416                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4417}
4418
4419CXSourceRange clang_getTokenExtent(CXTranslationUnit TU, CXToken CXTok) {
4420  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4421  if (!CXXUnit)
4422    return clang_getNullRange();
4423
4424  return cxloc::translateSourceRange(CXXUnit->getASTContext(),
4425                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4426}
4427
4428static void getTokens(ASTUnit *CXXUnit, SourceRange Range,
4429                      SmallVectorImpl<CXToken> &CXTokens) {
4430  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4431  std::pair<FileID, unsigned> BeginLocInfo
4432    = SourceMgr.getDecomposedLoc(Range.getBegin());
4433  std::pair<FileID, unsigned> EndLocInfo
4434    = SourceMgr.getDecomposedLoc(Range.getEnd());
4435
4436  // Cannot tokenize across files.
4437  if (BeginLocInfo.first != EndLocInfo.first)
4438    return;
4439
4440  // Create a lexer
4441  bool Invalid = false;
4442  StringRef Buffer
4443    = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4444  if (Invalid)
4445    return;
4446
4447  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4448            CXXUnit->getASTContext().getLangOptions(),
4449            Buffer.begin(), Buffer.data() + BeginLocInfo.second, Buffer.end());
4450  Lex.SetCommentRetentionState(true);
4451
4452  // Lex tokens until we hit the end of the range.
4453  const char *EffectiveBufferEnd = Buffer.data() + EndLocInfo.second;
4454  Token Tok;
4455  bool previousWasAt = false;
4456  do {
4457    // Lex the next token
4458    Lex.LexFromRawLexer(Tok);
4459    if (Tok.is(tok::eof))
4460      break;
4461
4462    // Initialize the CXToken.
4463    CXToken CXTok;
4464
4465    //   - Common fields
4466    CXTok.int_data[1] = Tok.getLocation().getRawEncoding();
4467    CXTok.int_data[2] = Tok.getLength();
4468    CXTok.int_data[3] = 0;
4469
4470    //   - Kind-specific fields
4471    if (Tok.isLiteral()) {
4472      CXTok.int_data[0] = CXToken_Literal;
4473      CXTok.ptr_data = (void *)Tok.getLiteralData();
4474    } else if (Tok.is(tok::raw_identifier)) {
4475      // Lookup the identifier to determine whether we have a keyword.
4476      IdentifierInfo *II
4477        = CXXUnit->getPreprocessor().LookUpIdentifierInfo(Tok);
4478
4479      if ((II->getObjCKeywordID() != tok::objc_not_keyword) && previousWasAt) {
4480        CXTok.int_data[0] = CXToken_Keyword;
4481      }
4482      else {
4483        CXTok.int_data[0] = Tok.is(tok::identifier)
4484          ? CXToken_Identifier
4485          : CXToken_Keyword;
4486      }
4487      CXTok.ptr_data = II;
4488    } else if (Tok.is(tok::comment)) {
4489      CXTok.int_data[0] = CXToken_Comment;
4490      CXTok.ptr_data = 0;
4491    } else {
4492      CXTok.int_data[0] = CXToken_Punctuation;
4493      CXTok.ptr_data = 0;
4494    }
4495    CXTokens.push_back(CXTok);
4496    previousWasAt = Tok.is(tok::at);
4497  } while (Lex.getBufferLocation() <= EffectiveBufferEnd);
4498}
4499
4500void clang_tokenize(CXTranslationUnit TU, CXSourceRange Range,
4501                    CXToken **Tokens, unsigned *NumTokens) {
4502  if (Tokens)
4503    *Tokens = 0;
4504  if (NumTokens)
4505    *NumTokens = 0;
4506
4507  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4508  if (!CXXUnit || !Tokens || !NumTokens)
4509    return;
4510
4511  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
4512
4513  SourceRange R = cxloc::translateCXSourceRange(Range);
4514  if (R.isInvalid())
4515    return;
4516
4517  SmallVector<CXToken, 32> CXTokens;
4518  getTokens(CXXUnit, R, CXTokens);
4519
4520  if (CXTokens.empty())
4521    return;
4522
4523  *Tokens = (CXToken *)malloc(sizeof(CXToken) * CXTokens.size());
4524  memmove(*Tokens, CXTokens.data(), sizeof(CXToken) * CXTokens.size());
4525  *NumTokens = CXTokens.size();
4526}
4527
4528void clang_disposeTokens(CXTranslationUnit TU,
4529                         CXToken *Tokens, unsigned NumTokens) {
4530  free(Tokens);
4531}
4532
4533} // end: extern "C"
4534
4535//===----------------------------------------------------------------------===//
4536// Token annotation APIs.
4537//===----------------------------------------------------------------------===//
4538
4539typedef llvm::DenseMap<unsigned, CXCursor> AnnotateTokensData;
4540static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4541                                                     CXCursor parent,
4542                                                     CXClientData client_data);
4543namespace {
4544class AnnotateTokensWorker {
4545  AnnotateTokensData &Annotated;
4546  CXToken *Tokens;
4547  CXCursor *Cursors;
4548  unsigned NumTokens;
4549  unsigned TokIdx;
4550  unsigned PreprocessingTokIdx;
4551  CursorVisitor AnnotateVis;
4552  SourceManager &SrcMgr;
4553  bool HasContextSensitiveKeywords;
4554
4555  bool MoreTokens() const { return TokIdx < NumTokens; }
4556  unsigned NextToken() const { return TokIdx; }
4557  void AdvanceToken() { ++TokIdx; }
4558  SourceLocation GetTokenLoc(unsigned tokI) {
4559    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4560  }
4561  bool isFunctionMacroToken(unsigned tokI) const {
4562    return Tokens[tokI].int_data[3] != 0;
4563  }
4564  SourceLocation getFunctionMacroTokenLoc(unsigned tokI) const {
4565    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[3]);
4566  }
4567
4568  void annotateAndAdvanceTokens(CXCursor, RangeComparisonResult, SourceRange);
4569  void annotateAndAdvanceFunctionMacroTokens(CXCursor, RangeComparisonResult,
4570                                             SourceRange);
4571
4572public:
4573  AnnotateTokensWorker(AnnotateTokensData &annotated,
4574                       CXToken *tokens, CXCursor *cursors, unsigned numTokens,
4575                       CXTranslationUnit tu, SourceRange RegionOfInterest)
4576    : Annotated(annotated), Tokens(tokens), Cursors(cursors),
4577      NumTokens(numTokens), TokIdx(0), PreprocessingTokIdx(0),
4578      AnnotateVis(tu,
4579                  AnnotateTokensVisitor, this,
4580                  /*VisitPreprocessorLast=*/true,
4581                  /*VisitIncludedEntities=*/false,
4582                  RegionOfInterest),
4583      SrcMgr(static_cast<ASTUnit*>(tu->TUData)->getSourceManager()),
4584      HasContextSensitiveKeywords(false) { }
4585
4586  void VisitChildren(CXCursor C) { AnnotateVis.VisitChildren(C); }
4587  enum CXChildVisitResult Visit(CXCursor cursor, CXCursor parent);
4588  void AnnotateTokens(CXCursor parent);
4589  void AnnotateTokens() {
4590    AnnotateTokens(clang_getTranslationUnitCursor(AnnotateVis.getTU()));
4591  }
4592
4593  /// \brief Determine whether the annotator saw any cursors that have
4594  /// context-sensitive keywords.
4595  bool hasContextSensitiveKeywords() const {
4596    return HasContextSensitiveKeywords;
4597  }
4598};
4599}
4600
4601void AnnotateTokensWorker::AnnotateTokens(CXCursor parent) {
4602  // Walk the AST within the region of interest, annotating tokens
4603  // along the way.
4604  VisitChildren(parent);
4605
4606  for (unsigned I = 0 ; I < TokIdx ; ++I) {
4607    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4608    if (Pos != Annotated.end() &&
4609        (clang_isInvalid(Cursors[I].kind) ||
4610         Pos->second.kind != CXCursor_PreprocessingDirective))
4611      Cursors[I] = Pos->second;
4612  }
4613
4614  // Finish up annotating any tokens left.
4615  if (!MoreTokens())
4616    return;
4617
4618  const CXCursor &C = clang_getNullCursor();
4619  for (unsigned I = TokIdx ; I < NumTokens ; ++I) {
4620    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4621    Cursors[I] = (Pos == Annotated.end()) ? C : Pos->second;
4622  }
4623}
4624
4625/// \brief It annotates and advances tokens with a cursor until the comparison
4626//// between the cursor location and the source range is the same as
4627/// \arg compResult.
4628///
4629/// Pass RangeBefore to annotate tokens with a cursor until a range is reached.
4630/// Pass RangeOverlap to annotate tokens inside a range.
4631void AnnotateTokensWorker::annotateAndAdvanceTokens(CXCursor updateC,
4632                                               RangeComparisonResult compResult,
4633                                               SourceRange range) {
4634  while (MoreTokens()) {
4635    const unsigned I = NextToken();
4636    if (isFunctionMacroToken(I))
4637      return annotateAndAdvanceFunctionMacroTokens(updateC, compResult, range);
4638
4639    SourceLocation TokLoc = GetTokenLoc(I);
4640    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4641      Cursors[I] = updateC;
4642      AdvanceToken();
4643      continue;
4644    }
4645    break;
4646  }
4647}
4648
4649/// \brief Special annotation handling for macro argument tokens.
4650void AnnotateTokensWorker::annotateAndAdvanceFunctionMacroTokens(
4651                                               CXCursor updateC,
4652                                               RangeComparisonResult compResult,
4653                                               SourceRange range) {
4654  assert(MoreTokens());
4655  assert(isFunctionMacroToken(NextToken()) &&
4656         "Should be called only for macro arg tokens");
4657
4658  // This works differently than annotateAndAdvanceTokens; because expanded
4659  // macro arguments can have arbitrary translation-unit source order, we do not
4660  // advance the token index one by one until a token fails the range test.
4661  // We only advance once past all of the macro arg tokens if all of them
4662  // pass the range test. If one of them fails we keep the token index pointing
4663  // at the start of the macro arg tokens so that the failing token will be
4664  // annotated by a subsequent annotation try.
4665
4666  bool atLeastOneCompFail = false;
4667
4668  unsigned I = NextToken();
4669  for (; I < NumTokens && isFunctionMacroToken(I); ++I) {
4670    SourceLocation TokLoc = getFunctionMacroTokenLoc(I);
4671    if (TokLoc.isFileID())
4672      continue; // not macro arg token, it's parens or comma.
4673    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4674      if (clang_isInvalid(clang_getCursorKind(Cursors[I])))
4675        Cursors[I] = updateC;
4676    } else
4677      atLeastOneCompFail = true;
4678  }
4679
4680  if (!atLeastOneCompFail)
4681    TokIdx = I; // All of the tokens were handled, advance beyond all of them.
4682}
4683
4684enum CXChildVisitResult
4685AnnotateTokensWorker::Visit(CXCursor cursor, CXCursor parent) {
4686  CXSourceLocation Loc = clang_getCursorLocation(cursor);
4687  SourceRange cursorRange = getRawCursorExtent(cursor);
4688  if (cursorRange.isInvalid())
4689    return CXChildVisit_Recurse;
4690
4691  if (!HasContextSensitiveKeywords) {
4692    // Objective-C properties can have context-sensitive keywords.
4693    if (cursor.kind == CXCursor_ObjCPropertyDecl) {
4694      if (ObjCPropertyDecl *Property
4695                  = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(cursor)))
4696        HasContextSensitiveKeywords = Property->getPropertyAttributesAsWritten() != 0;
4697    }
4698    // Objective-C methods can have context-sensitive keywords.
4699    else if (cursor.kind == CXCursor_ObjCInstanceMethodDecl ||
4700             cursor.kind == CXCursor_ObjCClassMethodDecl) {
4701      if (ObjCMethodDecl *Method
4702            = dyn_cast_or_null<ObjCMethodDecl>(getCursorDecl(cursor))) {
4703        if (Method->getObjCDeclQualifier())
4704          HasContextSensitiveKeywords = true;
4705        else {
4706          for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
4707                                           PEnd = Method->param_end();
4708               P != PEnd; ++P) {
4709            if ((*P)->getObjCDeclQualifier()) {
4710              HasContextSensitiveKeywords = true;
4711              break;
4712            }
4713          }
4714        }
4715      }
4716    }
4717    // C++ methods can have context-sensitive keywords.
4718    else if (cursor.kind == CXCursor_CXXMethod) {
4719      if (CXXMethodDecl *Method
4720                  = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(cursor))) {
4721        if (Method->hasAttr<FinalAttr>() || Method->hasAttr<OverrideAttr>())
4722          HasContextSensitiveKeywords = true;
4723      }
4724    }
4725    // C++ classes can have context-sensitive keywords.
4726    else if (cursor.kind == CXCursor_StructDecl ||
4727             cursor.kind == CXCursor_ClassDecl ||
4728             cursor.kind == CXCursor_ClassTemplate ||
4729             cursor.kind == CXCursor_ClassTemplatePartialSpecialization) {
4730      if (Decl *D = getCursorDecl(cursor))
4731        if (D->hasAttr<FinalAttr>())
4732          HasContextSensitiveKeywords = true;
4733    }
4734  }
4735
4736  if (clang_isPreprocessing(cursor.kind)) {
4737    // For macro expansions, just note where the beginning of the macro
4738    // expansion occurs.
4739    if (cursor.kind == CXCursor_MacroExpansion) {
4740      Annotated[Loc.int_data] = cursor;
4741      return CXChildVisit_Recurse;
4742    }
4743
4744    // Items in the preprocessing record are kept separate from items in
4745    // declarations, so we keep a separate token index.
4746    unsigned SavedTokIdx = TokIdx;
4747    TokIdx = PreprocessingTokIdx;
4748
4749    // Skip tokens up until we catch up to the beginning of the preprocessing
4750    // entry.
4751    while (MoreTokens()) {
4752      const unsigned I = NextToken();
4753      SourceLocation TokLoc = GetTokenLoc(I);
4754      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4755      case RangeBefore:
4756        AdvanceToken();
4757        continue;
4758      case RangeAfter:
4759      case RangeOverlap:
4760        break;
4761      }
4762      break;
4763    }
4764
4765    // Look at all of the tokens within this range.
4766    while (MoreTokens()) {
4767      const unsigned I = NextToken();
4768      SourceLocation TokLoc = GetTokenLoc(I);
4769      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4770      case RangeBefore:
4771        llvm_unreachable("Infeasible");
4772      case RangeAfter:
4773        break;
4774      case RangeOverlap:
4775        Cursors[I] = cursor;
4776        AdvanceToken();
4777        continue;
4778      }
4779      break;
4780    }
4781
4782    // Save the preprocessing token index; restore the non-preprocessing
4783    // token index.
4784    PreprocessingTokIdx = TokIdx;
4785    TokIdx = SavedTokIdx;
4786    return CXChildVisit_Recurse;
4787  }
4788
4789  if (cursorRange.isInvalid())
4790    return CXChildVisit_Continue;
4791
4792  SourceLocation L = SourceLocation::getFromRawEncoding(Loc.int_data);
4793
4794  // Adjust the annotated range based specific declarations.
4795  const enum CXCursorKind cursorK = clang_getCursorKind(cursor);
4796  if (cursorK >= CXCursor_FirstDecl && cursorK <= CXCursor_LastDecl) {
4797    Decl *D = cxcursor::getCursorDecl(cursor);
4798
4799    SourceLocation StartLoc;
4800    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
4801      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
4802        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4803    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
4804      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
4805        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4806    }
4807
4808    if (StartLoc.isValid() && L.isValid() &&
4809        SrcMgr.isBeforeInTranslationUnit(StartLoc, L))
4810      cursorRange.setBegin(StartLoc);
4811  }
4812
4813  // If the location of the cursor occurs within a macro instantiation, record
4814  // the spelling location of the cursor in our annotation map.  We can then
4815  // paper over the token labelings during a post-processing step to try and
4816  // get cursor mappings for tokens that are the *arguments* of a macro
4817  // instantiation.
4818  if (L.isMacroID()) {
4819    unsigned rawEncoding = SrcMgr.getSpellingLoc(L).getRawEncoding();
4820    // Only invalidate the old annotation if it isn't part of a preprocessing
4821    // directive.  Here we assume that the default construction of CXCursor
4822    // results in CXCursor.kind being an initialized value (i.e., 0).  If
4823    // this isn't the case, we can fix by doing lookup + insertion.
4824
4825    CXCursor &oldC = Annotated[rawEncoding];
4826    if (!clang_isPreprocessing(oldC.kind))
4827      oldC = cursor;
4828  }
4829
4830  const enum CXCursorKind K = clang_getCursorKind(parent);
4831  const CXCursor updateC =
4832    (clang_isInvalid(K) || K == CXCursor_TranslationUnit)
4833     ? clang_getNullCursor() : parent;
4834
4835  annotateAndAdvanceTokens(updateC, RangeBefore, cursorRange);
4836
4837  // Avoid having the cursor of an expression "overwrite" the annotation of the
4838  // variable declaration that it belongs to.
4839  // This can happen for C++ constructor expressions whose range generally
4840  // include the variable declaration, e.g.:
4841  //  MyCXXClass foo; // Make sure we don't annotate 'foo' as a CallExpr cursor.
4842  if (clang_isExpression(cursorK)) {
4843    Expr *E = getCursorExpr(cursor);
4844    if (Decl *D = getCursorParentDecl(cursor)) {
4845      const unsigned I = NextToken();
4846      if (E->getLocStart().isValid() && D->getLocation().isValid() &&
4847          E->getLocStart() == D->getLocation() &&
4848          E->getLocStart() == GetTokenLoc(I)) {
4849        Cursors[I] = updateC;
4850        AdvanceToken();
4851      }
4852    }
4853  }
4854
4855  // Visit children to get their cursor information.
4856  const unsigned BeforeChildren = NextToken();
4857  VisitChildren(cursor);
4858  const unsigned AfterChildren = NextToken();
4859
4860  // Scan the tokens that are at the end of the cursor, but are not captured
4861  // but the child cursors.
4862  annotateAndAdvanceTokens(cursor, RangeOverlap, cursorRange);
4863
4864  // Scan the tokens that are at the beginning of the cursor, but are not
4865  // capture by the child cursors.
4866  for (unsigned I = BeforeChildren; I != AfterChildren; ++I) {
4867    if (!clang_isInvalid(clang_getCursorKind(Cursors[I])))
4868      break;
4869
4870    Cursors[I] = cursor;
4871  }
4872
4873  return CXChildVisit_Continue;
4874}
4875
4876static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4877                                                     CXCursor parent,
4878                                                     CXClientData client_data) {
4879  return static_cast<AnnotateTokensWorker*>(client_data)->Visit(cursor, parent);
4880}
4881
4882namespace {
4883
4884/// \brief Uses the macro expansions in the preprocessing record to find
4885/// and mark tokens that are macro arguments. This info is used by the
4886/// AnnotateTokensWorker.
4887class MarkMacroArgTokensVisitor {
4888  SourceManager &SM;
4889  CXToken *Tokens;
4890  unsigned NumTokens;
4891  unsigned CurIdx;
4892
4893public:
4894  MarkMacroArgTokensVisitor(SourceManager &SM,
4895                            CXToken *tokens, unsigned numTokens)
4896    : SM(SM), Tokens(tokens), NumTokens(numTokens), CurIdx(0) { }
4897
4898  CXChildVisitResult visit(CXCursor cursor, CXCursor parent) {
4899    if (cursor.kind != CXCursor_MacroExpansion)
4900      return CXChildVisit_Continue;
4901
4902    SourceRange macroRange = getCursorMacroExpansion(cursor)->getSourceRange();
4903    if (macroRange.getBegin() == macroRange.getEnd())
4904      return CXChildVisit_Continue; // it's not a function macro.
4905
4906    for (; CurIdx < NumTokens; ++CurIdx) {
4907      if (!SM.isBeforeInTranslationUnit(getTokenLoc(CurIdx),
4908                                        macroRange.getBegin()))
4909        break;
4910    }
4911
4912    if (CurIdx == NumTokens)
4913      return CXChildVisit_Break;
4914
4915    for (; CurIdx < NumTokens; ++CurIdx) {
4916      SourceLocation tokLoc = getTokenLoc(CurIdx);
4917      if (!SM.isBeforeInTranslationUnit(tokLoc, macroRange.getEnd()))
4918        break;
4919
4920      setFunctionMacroTokenLoc(CurIdx, SM.getMacroArgExpandedLocation(tokLoc));
4921    }
4922
4923    if (CurIdx == NumTokens)
4924      return CXChildVisit_Break;
4925
4926    return CXChildVisit_Continue;
4927  }
4928
4929private:
4930  SourceLocation getTokenLoc(unsigned tokI) {
4931    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4932  }
4933
4934  void setFunctionMacroTokenLoc(unsigned tokI, SourceLocation loc) {
4935    // The third field is reserved and currently not used. Use it here
4936    // to mark macro arg expanded tokens with their expanded locations.
4937    Tokens[tokI].int_data[3] = loc.getRawEncoding();
4938  }
4939};
4940
4941} // end anonymous namespace
4942
4943static CXChildVisitResult
4944MarkMacroArgTokensVisitorDelegate(CXCursor cursor, CXCursor parent,
4945                                  CXClientData client_data) {
4946  return static_cast<MarkMacroArgTokensVisitor*>(client_data)->visit(cursor,
4947                                                                     parent);
4948}
4949
4950namespace {
4951  struct clang_annotateTokens_Data {
4952    CXTranslationUnit TU;
4953    ASTUnit *CXXUnit;
4954    CXToken *Tokens;
4955    unsigned NumTokens;
4956    CXCursor *Cursors;
4957  };
4958}
4959
4960static void annotatePreprocessorTokens(CXTranslationUnit TU,
4961                                       SourceRange RegionOfInterest,
4962                                       AnnotateTokensData &Annotated) {
4963  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4964
4965  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4966  std::pair<FileID, unsigned> BeginLocInfo
4967    = SourceMgr.getDecomposedLoc(RegionOfInterest.getBegin());
4968  std::pair<FileID, unsigned> EndLocInfo
4969    = SourceMgr.getDecomposedLoc(RegionOfInterest.getEnd());
4970
4971  if (BeginLocInfo.first != EndLocInfo.first)
4972    return;
4973
4974  StringRef Buffer;
4975  bool Invalid = false;
4976  Buffer = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4977  if (Buffer.empty() || Invalid)
4978    return;
4979
4980  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4981            CXXUnit->getASTContext().getLangOptions(),
4982            Buffer.begin(), Buffer.data() + BeginLocInfo.second,
4983            Buffer.end());
4984  Lex.SetCommentRetentionState(true);
4985
4986  // Lex tokens in raw mode until we hit the end of the range, to avoid
4987  // entering #includes or expanding macros.
4988  while (true) {
4989    Token Tok;
4990    Lex.LexFromRawLexer(Tok);
4991
4992  reprocess:
4993    if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
4994      // We have found a preprocessing directive. Gobble it up so that we
4995      // don't see it while preprocessing these tokens later, but keep track
4996      // of all of the token locations inside this preprocessing directive so
4997      // that we can annotate them appropriately.
4998      //
4999      // FIXME: Some simple tests here could identify macro definitions and
5000      // #undefs, to provide specific cursor kinds for those.
5001      SmallVector<SourceLocation, 32> Locations;
5002      do {
5003        Locations.push_back(Tok.getLocation());
5004        Lex.LexFromRawLexer(Tok);
5005      } while (!Tok.isAtStartOfLine() && !Tok.is(tok::eof));
5006
5007      using namespace cxcursor;
5008      CXCursor Cursor
5009      = MakePreprocessingDirectiveCursor(SourceRange(Locations.front(),
5010                                                     Locations.back()),
5011                                         TU);
5012      for (unsigned I = 0, N = Locations.size(); I != N; ++I) {
5013        Annotated[Locations[I].getRawEncoding()] = Cursor;
5014      }
5015
5016      if (Tok.isAtStartOfLine())
5017        goto reprocess;
5018
5019      continue;
5020    }
5021
5022    if (Tok.is(tok::eof))
5023      break;
5024  }
5025}
5026
5027// This gets run a separate thread to avoid stack blowout.
5028static void clang_annotateTokensImpl(void *UserData) {
5029  CXTranslationUnit TU = ((clang_annotateTokens_Data*)UserData)->TU;
5030  ASTUnit *CXXUnit = ((clang_annotateTokens_Data*)UserData)->CXXUnit;
5031  CXToken *Tokens = ((clang_annotateTokens_Data*)UserData)->Tokens;
5032  const unsigned NumTokens = ((clang_annotateTokens_Data*)UserData)->NumTokens;
5033  CXCursor *Cursors = ((clang_annotateTokens_Data*)UserData)->Cursors;
5034
5035  // Determine the region of interest, which contains all of the tokens.
5036  SourceRange RegionOfInterest;
5037  RegionOfInterest.setBegin(
5038    cxloc::translateSourceLocation(clang_getTokenLocation(TU, Tokens[0])));
5039  RegionOfInterest.setEnd(
5040    cxloc::translateSourceLocation(clang_getTokenLocation(TU,
5041                                                         Tokens[NumTokens-1])));
5042
5043  // A mapping from the source locations found when re-lexing or traversing the
5044  // region of interest to the corresponding cursors.
5045  AnnotateTokensData Annotated;
5046
5047  // Relex the tokens within the source range to look for preprocessing
5048  // directives.
5049  annotatePreprocessorTokens(TU, RegionOfInterest, Annotated);
5050
5051  if (CXXUnit->getPreprocessor().getPreprocessingRecord()) {
5052    // Search and mark tokens that are macro argument expansions.
5053    MarkMacroArgTokensVisitor Visitor(CXXUnit->getSourceManager(),
5054                                      Tokens, NumTokens);
5055    CursorVisitor MacroArgMarker(TU,
5056                                 MarkMacroArgTokensVisitorDelegate, &Visitor,
5057                                 /*VisitPreprocessorLast=*/true,
5058                                 /*VisitIncludedEntities=*/false,
5059                                 RegionOfInterest);
5060    MacroArgMarker.visitPreprocessedEntitiesInRegion();
5061  }
5062
5063  // Annotate all of the source locations in the region of interest that map to
5064  // a specific cursor.
5065  AnnotateTokensWorker W(Annotated, Tokens, Cursors, NumTokens,
5066                         TU, RegionOfInterest);
5067
5068  // FIXME: We use a ridiculous stack size here because the data-recursion
5069  // algorithm uses a large stack frame than the non-data recursive version,
5070  // and AnnotationTokensWorker currently transforms the data-recursion
5071  // algorithm back into a traditional recursion by explicitly calling
5072  // VisitChildren().  We will need to remove this explicit recursive call.
5073  W.AnnotateTokens();
5074
5075  // If we ran into any entities that involve context-sensitive keywords,
5076  // take another pass through the tokens to mark them as such.
5077  if (W.hasContextSensitiveKeywords()) {
5078    for (unsigned I = 0; I != NumTokens; ++I) {
5079      if (clang_getTokenKind(Tokens[I]) != CXToken_Identifier)
5080        continue;
5081
5082      if (Cursors[I].kind == CXCursor_ObjCPropertyDecl) {
5083        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5084        if (ObjCPropertyDecl *Property
5085            = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(Cursors[I]))) {
5086          if (Property->getPropertyAttributesAsWritten() != 0 &&
5087              llvm::StringSwitch<bool>(II->getName())
5088              .Case("readonly", true)
5089              .Case("assign", true)
5090              .Case("unsafe_unretained", true)
5091              .Case("readwrite", true)
5092              .Case("retain", true)
5093              .Case("copy", true)
5094              .Case("nonatomic", true)
5095              .Case("atomic", true)
5096              .Case("getter", true)
5097              .Case("setter", true)
5098              .Case("strong", true)
5099              .Case("weak", true)
5100              .Default(false))
5101            Tokens[I].int_data[0] = CXToken_Keyword;
5102        }
5103        continue;
5104      }
5105
5106      if (Cursors[I].kind == CXCursor_ObjCInstanceMethodDecl ||
5107          Cursors[I].kind == CXCursor_ObjCClassMethodDecl) {
5108        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5109        if (llvm::StringSwitch<bool>(II->getName())
5110            .Case("in", true)
5111            .Case("out", true)
5112            .Case("inout", true)
5113            .Case("oneway", true)
5114            .Case("bycopy", true)
5115            .Case("byref", true)
5116            .Default(false))
5117          Tokens[I].int_data[0] = CXToken_Keyword;
5118        continue;
5119      }
5120
5121      if (Cursors[I].kind == CXCursor_CXXFinalAttr ||
5122          Cursors[I].kind == CXCursor_CXXOverrideAttr) {
5123        Tokens[I].int_data[0] = CXToken_Keyword;
5124        continue;
5125      }
5126    }
5127  }
5128}
5129
5130extern "C" {
5131
5132void clang_annotateTokens(CXTranslationUnit TU,
5133                          CXToken *Tokens, unsigned NumTokens,
5134                          CXCursor *Cursors) {
5135
5136  if (NumTokens == 0 || !Tokens || !Cursors)
5137    return;
5138
5139  // Any token we don't specifically annotate will have a NULL cursor.
5140  CXCursor C = clang_getNullCursor();
5141  for (unsigned I = 0; I != NumTokens; ++I)
5142    Cursors[I] = C;
5143
5144  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
5145  if (!CXXUnit)
5146    return;
5147
5148  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
5149
5150  clang_annotateTokens_Data data = { TU, CXXUnit, Tokens, NumTokens, Cursors };
5151  llvm::CrashRecoveryContext CRC;
5152  if (!RunSafely(CRC, clang_annotateTokensImpl, &data,
5153                 GetSafetyThreadStackSize() * 2)) {
5154    fprintf(stderr, "libclang: crash detected while annotating tokens\n");
5155  }
5156}
5157
5158} // end: extern "C"
5159
5160//===----------------------------------------------------------------------===//
5161// Operations for querying linkage of a cursor.
5162//===----------------------------------------------------------------------===//
5163
5164extern "C" {
5165CXLinkageKind clang_getCursorLinkage(CXCursor cursor) {
5166  if (!clang_isDeclaration(cursor.kind))
5167    return CXLinkage_Invalid;
5168
5169  Decl *D = cxcursor::getCursorDecl(cursor);
5170  if (NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
5171    switch (ND->getLinkage()) {
5172      case NoLinkage: return CXLinkage_NoLinkage;
5173      case InternalLinkage: return CXLinkage_Internal;
5174      case UniqueExternalLinkage: return CXLinkage_UniqueExternal;
5175      case ExternalLinkage: return CXLinkage_External;
5176    };
5177
5178  return CXLinkage_Invalid;
5179}
5180} // end: extern "C"
5181
5182//===----------------------------------------------------------------------===//
5183// Operations for querying language of a cursor.
5184//===----------------------------------------------------------------------===//
5185
5186static CXLanguageKind getDeclLanguage(const Decl *D) {
5187  switch (D->getKind()) {
5188    default:
5189      break;
5190    case Decl::ImplicitParam:
5191    case Decl::ObjCAtDefsField:
5192    case Decl::ObjCCategory:
5193    case Decl::ObjCCategoryImpl:
5194    case Decl::ObjCClass:
5195    case Decl::ObjCCompatibleAlias:
5196    case Decl::ObjCForwardProtocol:
5197    case Decl::ObjCImplementation:
5198    case Decl::ObjCInterface:
5199    case Decl::ObjCIvar:
5200    case Decl::ObjCMethod:
5201    case Decl::ObjCProperty:
5202    case Decl::ObjCPropertyImpl:
5203    case Decl::ObjCProtocol:
5204      return CXLanguage_ObjC;
5205    case Decl::CXXConstructor:
5206    case Decl::CXXConversion:
5207    case Decl::CXXDestructor:
5208    case Decl::CXXMethod:
5209    case Decl::CXXRecord:
5210    case Decl::ClassTemplate:
5211    case Decl::ClassTemplatePartialSpecialization:
5212    case Decl::ClassTemplateSpecialization:
5213    case Decl::Friend:
5214    case Decl::FriendTemplate:
5215    case Decl::FunctionTemplate:
5216    case Decl::LinkageSpec:
5217    case Decl::Namespace:
5218    case Decl::NamespaceAlias:
5219    case Decl::NonTypeTemplateParm:
5220    case Decl::StaticAssert:
5221    case Decl::TemplateTemplateParm:
5222    case Decl::TemplateTypeParm:
5223    case Decl::UnresolvedUsingTypename:
5224    case Decl::UnresolvedUsingValue:
5225    case Decl::Using:
5226    case Decl::UsingDirective:
5227    case Decl::UsingShadow:
5228      return CXLanguage_CPlusPlus;
5229  }
5230
5231  return CXLanguage_C;
5232}
5233
5234extern "C" {
5235
5236enum CXAvailabilityKind clang_getCursorAvailability(CXCursor cursor) {
5237  if (clang_isDeclaration(cursor.kind))
5238    if (Decl *D = cxcursor::getCursorDecl(cursor)) {
5239      if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->isDeleted())
5240        return CXAvailability_Available;
5241
5242      switch (D->getAvailability()) {
5243      case AR_Available:
5244      case AR_NotYetIntroduced:
5245        return CXAvailability_Available;
5246
5247      case AR_Deprecated:
5248        return CXAvailability_Deprecated;
5249
5250      case AR_Unavailable:
5251        return CXAvailability_NotAvailable;
5252      }
5253    }
5254
5255  return CXAvailability_Available;
5256}
5257
5258CXLanguageKind clang_getCursorLanguage(CXCursor cursor) {
5259  if (clang_isDeclaration(cursor.kind))
5260    return getDeclLanguage(cxcursor::getCursorDecl(cursor));
5261
5262  return CXLanguage_Invalid;
5263}
5264
5265 /// \brief If the given cursor is the "templated" declaration
5266 /// descibing a class or function template, return the class or
5267 /// function template.
5268static Decl *maybeGetTemplateCursor(Decl *D) {
5269  if (!D)
5270    return 0;
5271
5272  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
5273    if (FunctionTemplateDecl *FunTmpl = FD->getDescribedFunctionTemplate())
5274      return FunTmpl;
5275
5276  if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D))
5277    if (ClassTemplateDecl *ClassTmpl = RD->getDescribedClassTemplate())
5278      return ClassTmpl;
5279
5280  return D;
5281}
5282
5283CXCursor clang_getCursorSemanticParent(CXCursor cursor) {
5284  if (clang_isDeclaration(cursor.kind)) {
5285    if (Decl *D = getCursorDecl(cursor)) {
5286      DeclContext *DC = D->getDeclContext();
5287      if (!DC)
5288        return clang_getNullCursor();
5289
5290      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5291                          getCursorTU(cursor));
5292    }
5293  }
5294
5295  if (clang_isStatement(cursor.kind) || clang_isExpression(cursor.kind)) {
5296    if (Decl *D = getCursorDecl(cursor))
5297      return MakeCXCursor(D, getCursorTU(cursor));
5298  }
5299
5300  return clang_getNullCursor();
5301}
5302
5303CXCursor clang_getCursorLexicalParent(CXCursor cursor) {
5304  if (clang_isDeclaration(cursor.kind)) {
5305    if (Decl *D = getCursorDecl(cursor)) {
5306      DeclContext *DC = D->getLexicalDeclContext();
5307      if (!DC)
5308        return clang_getNullCursor();
5309
5310      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5311                          getCursorTU(cursor));
5312    }
5313  }
5314
5315  // FIXME: Note that we can't easily compute the lexical context of a
5316  // statement or expression, so we return nothing.
5317  return clang_getNullCursor();
5318}
5319
5320void clang_getOverriddenCursors(CXCursor cursor,
5321                                CXCursor **overridden,
5322                                unsigned *num_overridden) {
5323  if (overridden)
5324    *overridden = 0;
5325  if (num_overridden)
5326    *num_overridden = 0;
5327  if (!overridden || !num_overridden)
5328    return;
5329
5330  SmallVector<CXCursor, 8> Overridden;
5331  cxcursor::getOverriddenCursors(cursor, Overridden);
5332
5333  *num_overridden = Overridden.size();
5334  *overridden = new CXCursor [Overridden.size()];
5335  std::copy(Overridden.begin(), Overridden.end(), *overridden);
5336}
5337
5338void clang_disposeOverriddenCursors(CXCursor *overridden) {
5339  delete [] overridden;
5340}
5341
5342CXFile clang_getIncludedFile(CXCursor cursor) {
5343  if (cursor.kind != CXCursor_InclusionDirective)
5344    return 0;
5345
5346  InclusionDirective *ID = getCursorInclusionDirective(cursor);
5347  return (void *)ID->getFile();
5348}
5349
5350} // end: extern "C"
5351
5352
5353//===----------------------------------------------------------------------===//
5354// C++ AST instrospection.
5355//===----------------------------------------------------------------------===//
5356
5357extern "C" {
5358unsigned clang_CXXMethod_isStatic(CXCursor C) {
5359  if (!clang_isDeclaration(C.kind))
5360    return 0;
5361
5362  CXXMethodDecl *Method = 0;
5363  Decl *D = cxcursor::getCursorDecl(C);
5364  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5365    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5366  else
5367    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5368  return (Method && Method->isStatic()) ? 1 : 0;
5369}
5370
5371unsigned clang_CXXMethod_isVirtual(CXCursor C) {
5372  if (!clang_isDeclaration(C.kind))
5373    return 0;
5374
5375  CXXMethodDecl *Method = 0;
5376  Decl *D = cxcursor::getCursorDecl(C);
5377  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5378    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5379  else
5380    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5381  return (Method && Method->isVirtual()) ? 1 : 0;
5382}
5383} // end: extern "C"
5384
5385//===----------------------------------------------------------------------===//
5386// Attribute introspection.
5387//===----------------------------------------------------------------------===//
5388
5389extern "C" {
5390CXType clang_getIBOutletCollectionType(CXCursor C) {
5391  if (C.kind != CXCursor_IBOutletCollectionAttr)
5392    return cxtype::MakeCXType(QualType(), cxcursor::getCursorTU(C));
5393
5394  IBOutletCollectionAttr *A =
5395    cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(C));
5396
5397  return cxtype::MakeCXType(A->getInterface(), cxcursor::getCursorTU(C));
5398}
5399} // end: extern "C"
5400
5401//===----------------------------------------------------------------------===//
5402// Inspecting memory usage.
5403//===----------------------------------------------------------------------===//
5404
5405typedef std::vector<CXTUResourceUsageEntry> MemUsageEntries;
5406
5407static inline void createCXTUResourceUsageEntry(MemUsageEntries &entries,
5408                                              enum CXTUResourceUsageKind k,
5409                                              unsigned long amount) {
5410  CXTUResourceUsageEntry entry = { k, amount };
5411  entries.push_back(entry);
5412}
5413
5414extern "C" {
5415
5416const char *clang_getTUResourceUsageName(CXTUResourceUsageKind kind) {
5417  const char *str = "";
5418  switch (kind) {
5419    case CXTUResourceUsage_AST:
5420      str = "ASTContext: expressions, declarations, and types";
5421      break;
5422    case CXTUResourceUsage_Identifiers:
5423      str = "ASTContext: identifiers";
5424      break;
5425    case CXTUResourceUsage_Selectors:
5426      str = "ASTContext: selectors";
5427      break;
5428    case CXTUResourceUsage_GlobalCompletionResults:
5429      str = "Code completion: cached global results";
5430      break;
5431    case CXTUResourceUsage_SourceManagerContentCache:
5432      str = "SourceManager: content cache allocator";
5433      break;
5434    case CXTUResourceUsage_AST_SideTables:
5435      str = "ASTContext: side tables";
5436      break;
5437    case CXTUResourceUsage_SourceManager_Membuffer_Malloc:
5438      str = "SourceManager: malloc'ed memory buffers";
5439      break;
5440    case CXTUResourceUsage_SourceManager_Membuffer_MMap:
5441      str = "SourceManager: mmap'ed memory buffers";
5442      break;
5443    case CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc:
5444      str = "ExternalASTSource: malloc'ed memory buffers";
5445      break;
5446    case CXTUResourceUsage_ExternalASTSource_Membuffer_MMap:
5447      str = "ExternalASTSource: mmap'ed memory buffers";
5448      break;
5449    case CXTUResourceUsage_Preprocessor:
5450      str = "Preprocessor: malloc'ed memory";
5451      break;
5452    case CXTUResourceUsage_PreprocessingRecord:
5453      str = "Preprocessor: PreprocessingRecord";
5454      break;
5455    case CXTUResourceUsage_SourceManager_DataStructures:
5456      str = "SourceManager: data structures and tables";
5457      break;
5458    case CXTUResourceUsage_Preprocessor_HeaderSearch:
5459      str = "Preprocessor: header search tables";
5460      break;
5461  }
5462  return str;
5463}
5464
5465CXTUResourceUsage clang_getCXTUResourceUsage(CXTranslationUnit TU) {
5466  if (!TU) {
5467    CXTUResourceUsage usage = { (void*) 0, 0, 0 };
5468    return usage;
5469  }
5470
5471  ASTUnit *astUnit = static_cast<ASTUnit*>(TU->TUData);
5472  llvm::OwningPtr<MemUsageEntries> entries(new MemUsageEntries());
5473  ASTContext &astContext = astUnit->getASTContext();
5474
5475  // How much memory is used by AST nodes and types?
5476  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST,
5477    (unsigned long) astContext.getASTAllocatedMemory());
5478
5479  // How much memory is used by identifiers?
5480  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Identifiers,
5481    (unsigned long) astContext.Idents.getAllocator().getTotalMemory());
5482
5483  // How much memory is used for selectors?
5484  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Selectors,
5485    (unsigned long) astContext.Selectors.getTotalMemory());
5486
5487  // How much memory is used by ASTContext's side tables?
5488  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST_SideTables,
5489    (unsigned long) astContext.getSideTableAllocatedMemory());
5490
5491  // How much memory is used for caching global code completion results?
5492  unsigned long completionBytes = 0;
5493  if (GlobalCodeCompletionAllocator *completionAllocator =
5494      astUnit->getCachedCompletionAllocator().getPtr()) {
5495    completionBytes = completionAllocator->getTotalMemory();
5496  }
5497  createCXTUResourceUsageEntry(*entries,
5498                               CXTUResourceUsage_GlobalCompletionResults,
5499                               completionBytes);
5500
5501  // How much memory is being used by SourceManager's content cache?
5502  createCXTUResourceUsageEntry(*entries,
5503          CXTUResourceUsage_SourceManagerContentCache,
5504          (unsigned long) astContext.getSourceManager().getContentCacheSize());
5505
5506  // How much memory is being used by the MemoryBuffer's in SourceManager?
5507  const SourceManager::MemoryBufferSizes &srcBufs =
5508    astUnit->getSourceManager().getMemoryBufferSizes();
5509
5510  createCXTUResourceUsageEntry(*entries,
5511                               CXTUResourceUsage_SourceManager_Membuffer_Malloc,
5512                               (unsigned long) srcBufs.malloc_bytes);
5513  createCXTUResourceUsageEntry(*entries,
5514                               CXTUResourceUsage_SourceManager_Membuffer_MMap,
5515                               (unsigned long) srcBufs.mmap_bytes);
5516  createCXTUResourceUsageEntry(*entries,
5517                               CXTUResourceUsage_SourceManager_DataStructures,
5518                               (unsigned long) astContext.getSourceManager()
5519                                .getDataStructureSizes());
5520
5521  // How much memory is being used by the ExternalASTSource?
5522  if (ExternalASTSource *esrc = astContext.getExternalSource()) {
5523    const ExternalASTSource::MemoryBufferSizes &sizes =
5524      esrc->getMemoryBufferSizes();
5525
5526    createCXTUResourceUsageEntry(*entries,
5527      CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc,
5528                                 (unsigned long) sizes.malloc_bytes);
5529    createCXTUResourceUsageEntry(*entries,
5530      CXTUResourceUsage_ExternalASTSource_Membuffer_MMap,
5531                                 (unsigned long) sizes.mmap_bytes);
5532  }
5533
5534  // How much memory is being used by the Preprocessor?
5535  Preprocessor &pp = astUnit->getPreprocessor();
5536  createCXTUResourceUsageEntry(*entries,
5537                               CXTUResourceUsage_Preprocessor,
5538                               pp.getTotalMemory());
5539
5540  if (PreprocessingRecord *pRec = pp.getPreprocessingRecord()) {
5541    createCXTUResourceUsageEntry(*entries,
5542                                 CXTUResourceUsage_PreprocessingRecord,
5543                                 pRec->getTotalMemory());
5544  }
5545
5546  createCXTUResourceUsageEntry(*entries,
5547                               CXTUResourceUsage_Preprocessor_HeaderSearch,
5548                               pp.getHeaderSearchInfo().getTotalMemory());
5549
5550  CXTUResourceUsage usage = { (void*) entries.get(),
5551                            (unsigned) entries->size(),
5552                            entries->size() ? &(*entries)[0] : 0 };
5553  entries.take();
5554  return usage;
5555}
5556
5557void clang_disposeCXTUResourceUsage(CXTUResourceUsage usage) {
5558  if (usage.data)
5559    delete (MemUsageEntries*) usage.data;
5560}
5561
5562} // end extern "C"
5563
5564void clang::PrintLibclangResourceUsage(CXTranslationUnit TU) {
5565  CXTUResourceUsage Usage = clang_getCXTUResourceUsage(TU);
5566  for (unsigned I = 0; I != Usage.numEntries; ++I)
5567    fprintf(stderr, "  %s: %lu\n",
5568            clang_getTUResourceUsageName(Usage.entries[I].kind),
5569            Usage.entries[I].amount);
5570
5571  clang_disposeCXTUResourceUsage(Usage);
5572}
5573
5574//===----------------------------------------------------------------------===//
5575// Misc. utility functions.
5576//===----------------------------------------------------------------------===//
5577
5578/// Default to using an 8 MB stack size on "safety" threads.
5579static unsigned SafetyStackThreadSize = 8 << 20;
5580
5581namespace clang {
5582
5583bool RunSafely(llvm::CrashRecoveryContext &CRC,
5584               void (*Fn)(void*), void *UserData,
5585               unsigned Size) {
5586  if (!Size)
5587    Size = GetSafetyThreadStackSize();
5588  if (Size)
5589    return CRC.RunSafelyOnThread(Fn, UserData, Size);
5590  return CRC.RunSafely(Fn, UserData);
5591}
5592
5593unsigned GetSafetyThreadStackSize() {
5594  return SafetyStackThreadSize;
5595}
5596
5597void SetSafetyThreadStackSize(unsigned Value) {
5598  SafetyStackThreadSize = Value;
5599}
5600
5601}
5602
5603extern "C" {
5604
5605CXString clang_getClangVersion() {
5606  return createCXString(getClangFullVersion());
5607}
5608
5609} // end: extern "C"
5610
5611