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