CIndex.cpp revision 427964e15f1b9595659cea3fcb4dd808a00f37b5 
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  CXCursor &BestCursor;
3480
3481  GetCursorData(SourceLocation tokenBegin, CXCursor &outputCursor)
3482    : TokenBeginLoc(tokenBegin), BestCursor(outputCursor) { }
3483};
3484
3485enum CXChildVisitResult GetCursorVisitor(CXCursor cursor,
3486                                         CXCursor parent,
3487                                         CXClientData client_data) {
3488  GetCursorData *Data = static_cast<GetCursorData *>(client_data);
3489  CXCursor *BestCursor = &Data->BestCursor;
3490
3491  if (clang_isDeclaration(cursor.kind)) {
3492    // Avoid having the synthesized methods override the property decls.
3493    if (ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(getCursorDecl(cursor)))
3494      if (MD->isSynthesized())
3495        return CXChildVisit_Break;
3496  }
3497
3498  if (clang_isExpression(cursor.kind) &&
3499      clang_isDeclaration(BestCursor->kind)) {
3500    Decl *D = getCursorDecl(*BestCursor);
3501
3502    // Avoid having the cursor of an expression replace the declaration cursor
3503    // when the expression source range overlaps the declaration range.
3504    // This can happen for C++ constructor expressions whose range generally
3505    // include the variable declaration, e.g.:
3506    //  MyCXXClass foo; // Make sure pointing at 'foo' returns a VarDecl cursor.
3507    if (D->getLocation().isValid() && Data->TokenBeginLoc.isValid() &&
3508        D->getLocation() == Data->TokenBeginLoc)
3509      return CXChildVisit_Break;
3510  }
3511
3512  // If our current best cursor is the construction of a temporary object,
3513  // don't replace that cursor with a type reference, because we want
3514  // clang_getCursor() to point at the constructor.
3515  if (clang_isExpression(BestCursor->kind) &&
3516      isa<CXXTemporaryObjectExpr>(getCursorExpr(*BestCursor)) &&
3517      cursor.kind == CXCursor_TypeRef)
3518    return CXChildVisit_Recurse;
3519
3520  // Don't override a preprocessing cursor with another preprocessing
3521  // cursor; we want the outermost preprocessing cursor.
3522  if (clang_isPreprocessing(cursor.kind) &&
3523      clang_isPreprocessing(BestCursor->kind))
3524    return CXChildVisit_Recurse;
3525
3526  *BestCursor = cursor;
3527  return CXChildVisit_Recurse;
3528}
3529
3530CXCursor clang_getCursor(CXTranslationUnit TU, CXSourceLocation Loc) {
3531  if (!TU)
3532    return clang_getNullCursor();
3533
3534  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
3535  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
3536
3537  // Translate the given source location to make it point at the beginning of
3538  // the token under the cursor.
3539  SourceLocation SLoc = cxloc::translateSourceLocation(Loc);
3540
3541  // Guard against an invalid SourceLocation, or we may assert in one
3542  // of the following calls.
3543  if (SLoc.isInvalid())
3544    return clang_getNullCursor();
3545
3546  bool Logging = getenv("LIBCLANG_LOGGING");
3547  SLoc = Lexer::GetBeginningOfToken(SLoc, CXXUnit->getSourceManager(),
3548                                    CXXUnit->getASTContext().getLangOptions());
3549
3550  CXCursor Result = MakeCXCursorInvalid(CXCursor_NoDeclFound);
3551  if (SLoc.isValid()) {
3552    // FIXME: Would be great to have a "hint" cursor, then walk from that
3553    // hint cursor upward until we find a cursor whose source range encloses
3554    // the region of interest, rather than starting from the translation unit.
3555    GetCursorData ResultData(SLoc, Result);
3556    CXCursor Parent = clang_getTranslationUnitCursor(TU);
3557    CursorVisitor CursorVis(TU, GetCursorVisitor, &ResultData,
3558                            Decl::MaxPCHLevel, true, SourceLocation(SLoc));
3559    CursorVis.VisitChildren(Parent);
3560  }
3561
3562  if (Logging) {
3563    CXFile SearchFile;
3564    unsigned SearchLine, SearchColumn;
3565    CXFile ResultFile;
3566    unsigned ResultLine, ResultColumn;
3567    CXString SearchFileName, ResultFileName, KindSpelling, USR;
3568    const char *IsDef = clang_isCursorDefinition(Result)? " (Definition)" : "";
3569    CXSourceLocation ResultLoc = clang_getCursorLocation(Result);
3570
3571    clang_getInstantiationLocation(Loc, &SearchFile, &SearchLine, &SearchColumn,
3572                                   0);
3573    clang_getInstantiationLocation(ResultLoc, &ResultFile, &ResultLine,
3574                                   &ResultColumn, 0);
3575    SearchFileName = clang_getFileName(SearchFile);
3576    ResultFileName = clang_getFileName(ResultFile);
3577    KindSpelling = clang_getCursorKindSpelling(Result.kind);
3578    USR = clang_getCursorUSR(Result);
3579    fprintf(stderr, "clang_getCursor(%s:%d:%d) = %s(%s:%d:%d):%s%s\n",
3580            clang_getCString(SearchFileName), SearchLine, SearchColumn,
3581            clang_getCString(KindSpelling),
3582            clang_getCString(ResultFileName), ResultLine, ResultColumn,
3583            clang_getCString(USR), IsDef);
3584    clang_disposeString(SearchFileName);
3585    clang_disposeString(ResultFileName);
3586    clang_disposeString(KindSpelling);
3587    clang_disposeString(USR);
3588
3589    CXCursor Definition = clang_getCursorDefinition(Result);
3590    if (!clang_equalCursors(Definition, clang_getNullCursor())) {
3591      CXSourceLocation DefinitionLoc = clang_getCursorLocation(Definition);
3592      CXString DefinitionKindSpelling
3593                                = clang_getCursorKindSpelling(Definition.kind);
3594      CXFile DefinitionFile;
3595      unsigned DefinitionLine, DefinitionColumn;
3596      clang_getInstantiationLocation(DefinitionLoc, &DefinitionFile,
3597                                     &DefinitionLine, &DefinitionColumn, 0);
3598      CXString DefinitionFileName = clang_getFileName(DefinitionFile);
3599      fprintf(stderr, "  -> %s(%s:%d:%d)\n",
3600              clang_getCString(DefinitionKindSpelling),
3601              clang_getCString(DefinitionFileName),
3602              DefinitionLine, DefinitionColumn);
3603      clang_disposeString(DefinitionFileName);
3604      clang_disposeString(DefinitionKindSpelling);
3605    }
3606  }
3607
3608  return Result;
3609}
3610
3611CXCursor clang_getNullCursor(void) {
3612  return MakeCXCursorInvalid(CXCursor_InvalidFile);
3613}
3614
3615unsigned clang_equalCursors(CXCursor X, CXCursor Y) {
3616  return X == Y;
3617}
3618
3619unsigned clang_hashCursor(CXCursor C) {
3620  unsigned Index = 0;
3621  if (clang_isExpression(C.kind) || clang_isStatement(C.kind))
3622    Index = 1;
3623
3624  return llvm::DenseMapInfo<std::pair<unsigned, void*> >::getHashValue(
3625                                        std::make_pair(C.kind, C.data[Index]));
3626}
3627
3628unsigned clang_isInvalid(enum CXCursorKind K) {
3629  return K >= CXCursor_FirstInvalid && K <= CXCursor_LastInvalid;
3630}
3631
3632unsigned clang_isDeclaration(enum CXCursorKind K) {
3633  return K >= CXCursor_FirstDecl && K <= CXCursor_LastDecl;
3634}
3635
3636unsigned clang_isReference(enum CXCursorKind K) {
3637  return K >= CXCursor_FirstRef && K <= CXCursor_LastRef;
3638}
3639
3640unsigned clang_isExpression(enum CXCursorKind K) {
3641  return K >= CXCursor_FirstExpr && K <= CXCursor_LastExpr;
3642}
3643
3644unsigned clang_isStatement(enum CXCursorKind K) {
3645  return K >= CXCursor_FirstStmt && K <= CXCursor_LastStmt;
3646}
3647
3648unsigned clang_isAttribute(enum CXCursorKind K) {
3649    return K >= CXCursor_FirstAttr && K <= CXCursor_LastAttr;
3650}
3651
3652unsigned clang_isTranslationUnit(enum CXCursorKind K) {
3653  return K == CXCursor_TranslationUnit;
3654}
3655
3656unsigned clang_isPreprocessing(enum CXCursorKind K) {
3657  return K >= CXCursor_FirstPreprocessing && K <= CXCursor_LastPreprocessing;
3658}
3659
3660unsigned clang_isUnexposed(enum CXCursorKind K) {
3661  switch (K) {
3662    case CXCursor_UnexposedDecl:
3663    case CXCursor_UnexposedExpr:
3664    case CXCursor_UnexposedStmt:
3665    case CXCursor_UnexposedAttr:
3666      return true;
3667    default:
3668      return false;
3669  }
3670}
3671
3672CXCursorKind clang_getCursorKind(CXCursor C) {
3673  return C.kind;
3674}
3675
3676CXSourceLocation clang_getCursorLocation(CXCursor C) {
3677  if (clang_isReference(C.kind)) {
3678    switch (C.kind) {
3679    case CXCursor_ObjCSuperClassRef: {
3680      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3681        = getCursorObjCSuperClassRef(C);
3682      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3683    }
3684
3685    case CXCursor_ObjCProtocolRef: {
3686      std::pair<ObjCProtocolDecl *, SourceLocation> P
3687        = getCursorObjCProtocolRef(C);
3688      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3689    }
3690
3691    case CXCursor_ObjCClassRef: {
3692      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3693        = getCursorObjCClassRef(C);
3694      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3695    }
3696
3697    case CXCursor_TypeRef: {
3698      std::pair<TypeDecl *, SourceLocation> P = getCursorTypeRef(C);
3699      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3700    }
3701
3702    case CXCursor_TemplateRef: {
3703      std::pair<TemplateDecl *, SourceLocation> P = getCursorTemplateRef(C);
3704      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3705    }
3706
3707    case CXCursor_NamespaceRef: {
3708      std::pair<NamedDecl *, SourceLocation> P = getCursorNamespaceRef(C);
3709      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3710    }
3711
3712    case CXCursor_MemberRef: {
3713      std::pair<FieldDecl *, SourceLocation> P = getCursorMemberRef(C);
3714      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3715    }
3716
3717    case CXCursor_CXXBaseSpecifier: {
3718      CXXBaseSpecifier *BaseSpec = getCursorCXXBaseSpecifier(C);
3719      if (!BaseSpec)
3720        return clang_getNullLocation();
3721
3722      if (TypeSourceInfo *TSInfo = BaseSpec->getTypeSourceInfo())
3723        return cxloc::translateSourceLocation(getCursorContext(C),
3724                                            TSInfo->getTypeLoc().getBeginLoc());
3725
3726      return cxloc::translateSourceLocation(getCursorContext(C),
3727                                        BaseSpec->getSourceRange().getBegin());
3728    }
3729
3730    case CXCursor_LabelRef: {
3731      std::pair<LabelStmt *, SourceLocation> P = getCursorLabelRef(C);
3732      return cxloc::translateSourceLocation(getCursorContext(C), P.second);
3733    }
3734
3735    case CXCursor_OverloadedDeclRef:
3736      return cxloc::translateSourceLocation(getCursorContext(C),
3737                                          getCursorOverloadedDeclRef(C).second);
3738
3739    default:
3740      // FIXME: Need a way to enumerate all non-reference cases.
3741      llvm_unreachable("Missed a reference kind");
3742    }
3743  }
3744
3745  if (clang_isExpression(C.kind))
3746    return cxloc::translateSourceLocation(getCursorContext(C),
3747                                   getLocationFromExpr(getCursorExpr(C)));
3748
3749  if (clang_isStatement(C.kind))
3750    return cxloc::translateSourceLocation(getCursorContext(C),
3751                                          getCursorStmt(C)->getLocStart());
3752
3753  if (C.kind == CXCursor_PreprocessingDirective) {
3754    SourceLocation L = cxcursor::getCursorPreprocessingDirective(C).getBegin();
3755    return cxloc::translateSourceLocation(getCursorContext(C), L);
3756  }
3757
3758  if (C.kind == CXCursor_MacroExpansion) {
3759    SourceLocation L
3760      = cxcursor::getCursorMacroExpansion(C)->getSourceRange().getBegin();
3761    return cxloc::translateSourceLocation(getCursorContext(C), L);
3762  }
3763
3764  if (C.kind == CXCursor_MacroDefinition) {
3765    SourceLocation L = cxcursor::getCursorMacroDefinition(C)->getLocation();
3766    return cxloc::translateSourceLocation(getCursorContext(C), L);
3767  }
3768
3769  if (C.kind == CXCursor_InclusionDirective) {
3770    SourceLocation L
3771      = cxcursor::getCursorInclusionDirective(C)->getSourceRange().getBegin();
3772    return cxloc::translateSourceLocation(getCursorContext(C), L);
3773  }
3774
3775  if (C.kind < CXCursor_FirstDecl || C.kind > CXCursor_LastDecl)
3776    return clang_getNullLocation();
3777
3778  Decl *D = getCursorDecl(C);
3779  SourceLocation Loc = D->getLocation();
3780  if (ObjCInterfaceDecl *Class = dyn_cast<ObjCInterfaceDecl>(D))
3781    Loc = Class->getClassLoc();
3782  // FIXME: Multiple variables declared in a single declaration
3783  // currently lack the information needed to correctly determine their
3784  // ranges when accounting for the type-specifier.  We use context
3785  // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3786  // and if so, whether it is the first decl.
3787  if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3788    if (!cxcursor::isFirstInDeclGroup(C))
3789      Loc = VD->getLocation();
3790  }
3791
3792  return cxloc::translateSourceLocation(getCursorContext(C), Loc);
3793}
3794
3795} // end extern "C"
3796
3797static SourceRange getRawCursorExtent(CXCursor C) {
3798  if (clang_isReference(C.kind)) {
3799    switch (C.kind) {
3800    case CXCursor_ObjCSuperClassRef:
3801      return  getCursorObjCSuperClassRef(C).second;
3802
3803    case CXCursor_ObjCProtocolRef:
3804      return getCursorObjCProtocolRef(C).second;
3805
3806    case CXCursor_ObjCClassRef:
3807      return getCursorObjCClassRef(C).second;
3808
3809    case CXCursor_TypeRef:
3810      return getCursorTypeRef(C).second;
3811
3812    case CXCursor_TemplateRef:
3813      return getCursorTemplateRef(C).second;
3814
3815    case CXCursor_NamespaceRef:
3816      return getCursorNamespaceRef(C).second;
3817
3818    case CXCursor_MemberRef:
3819      return getCursorMemberRef(C).second;
3820
3821    case CXCursor_CXXBaseSpecifier:
3822      return getCursorCXXBaseSpecifier(C)->getSourceRange();
3823
3824    case CXCursor_LabelRef:
3825      return getCursorLabelRef(C).second;
3826
3827    case CXCursor_OverloadedDeclRef:
3828      return getCursorOverloadedDeclRef(C).second;
3829
3830    default:
3831      // FIXME: Need a way to enumerate all non-reference cases.
3832      llvm_unreachable("Missed a reference kind");
3833    }
3834  }
3835
3836  if (clang_isExpression(C.kind))
3837    return getCursorExpr(C)->getSourceRange();
3838
3839  if (clang_isStatement(C.kind))
3840    return getCursorStmt(C)->getSourceRange();
3841
3842  if (C.kind == CXCursor_PreprocessingDirective)
3843    return cxcursor::getCursorPreprocessingDirective(C);
3844
3845  if (C.kind == CXCursor_MacroExpansion)
3846    return cxcursor::getCursorMacroExpansion(C)->getSourceRange();
3847
3848  if (C.kind == CXCursor_MacroDefinition)
3849    return cxcursor::getCursorMacroDefinition(C)->getSourceRange();
3850
3851  if (C.kind == CXCursor_InclusionDirective)
3852    return cxcursor::getCursorInclusionDirective(C)->getSourceRange();
3853
3854  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3855    Decl *D = cxcursor::getCursorDecl(C);
3856    SourceRange R = D->getSourceRange();
3857    // FIXME: Multiple variables declared in a single declaration
3858    // currently lack the information needed to correctly determine their
3859    // ranges when accounting for the type-specifier.  We use context
3860    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3861    // and if so, whether it is the first decl.
3862    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3863      if (!cxcursor::isFirstInDeclGroup(C))
3864        R.setBegin(VD->getLocation());
3865    }
3866    return R;
3867  }
3868  return SourceRange();
3869}
3870
3871/// \brief Retrieves the "raw" cursor extent, which is then extended to include
3872/// the decl-specifier-seq for declarations.
3873static SourceRange getFullCursorExtent(CXCursor C, SourceManager &SrcMgr) {
3874  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3875    Decl *D = cxcursor::getCursorDecl(C);
3876    SourceRange R = D->getSourceRange();
3877
3878    // Adjust the start of the location for declarations preceded by
3879    // declaration specifiers.
3880    SourceLocation StartLoc;
3881    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
3882      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
3883        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3884    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
3885      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
3886        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3887    }
3888
3889    if (StartLoc.isValid() && R.getBegin().isValid() &&
3890        SrcMgr.isBeforeInTranslationUnit(StartLoc, R.getBegin()))
3891      R.setBegin(StartLoc);
3892
3893    // FIXME: Multiple variables declared in a single declaration
3894    // currently lack the information needed to correctly determine their
3895    // ranges when accounting for the type-specifier.  We use context
3896    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3897    // and if so, whether it is the first decl.
3898    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3899      if (!cxcursor::isFirstInDeclGroup(C))
3900        R.setBegin(VD->getLocation());
3901    }
3902
3903    return R;
3904  }
3905
3906  return getRawCursorExtent(C);
3907}
3908
3909extern "C" {
3910
3911CXSourceRange clang_getCursorExtent(CXCursor C) {
3912  SourceRange R = getRawCursorExtent(C);
3913  if (R.isInvalid())
3914    return clang_getNullRange();
3915
3916  return cxloc::translateSourceRange(getCursorContext(C), R);
3917}
3918
3919CXCursor clang_getCursorReferenced(CXCursor C) {
3920  if (clang_isInvalid(C.kind))
3921    return clang_getNullCursor();
3922
3923  CXTranslationUnit tu = getCursorTU(C);
3924  if (clang_isDeclaration(C.kind)) {
3925    Decl *D = getCursorDecl(C);
3926    if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
3927      return MakeCursorOverloadedDeclRef(Using, D->getLocation(), tu);
3928    if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
3929      return MakeCursorOverloadedDeclRef(Classes, D->getLocation(), tu);
3930    if (ObjCForwardProtocolDecl *Protocols
3931                                        = dyn_cast<ObjCForwardProtocolDecl>(D))
3932      return MakeCursorOverloadedDeclRef(Protocols, D->getLocation(), tu);
3933    if (ObjCPropertyImplDecl *PropImpl =dyn_cast<ObjCPropertyImplDecl>(D))
3934      if (ObjCPropertyDecl *Property = PropImpl->getPropertyDecl())
3935        return MakeCXCursor(Property, tu);
3936
3937    return C;
3938  }
3939
3940  if (clang_isExpression(C.kind)) {
3941    Expr *E = getCursorExpr(C);
3942    Decl *D = getDeclFromExpr(E);
3943    if (D)
3944      return MakeCXCursor(D, tu);
3945
3946    if (OverloadExpr *Ovl = dyn_cast_or_null<OverloadExpr>(E))
3947      return MakeCursorOverloadedDeclRef(Ovl, tu);
3948
3949    return clang_getNullCursor();
3950  }
3951
3952  if (clang_isStatement(C.kind)) {
3953    Stmt *S = getCursorStmt(C);
3954    if (GotoStmt *Goto = dyn_cast_or_null<GotoStmt>(S))
3955      if (LabelDecl *label = Goto->getLabel())
3956        if (LabelStmt *labelS = label->getStmt())
3957        return MakeCXCursor(labelS, getCursorDecl(C), tu);
3958
3959    return clang_getNullCursor();
3960  }
3961
3962  if (C.kind == CXCursor_MacroExpansion) {
3963    if (MacroDefinition *Def = getCursorMacroExpansion(C)->getDefinition())
3964      return MakeMacroDefinitionCursor(Def, tu);
3965  }
3966
3967  if (!clang_isReference(C.kind))
3968    return clang_getNullCursor();
3969
3970  switch (C.kind) {
3971    case CXCursor_ObjCSuperClassRef:
3972      return MakeCXCursor(getCursorObjCSuperClassRef(C).first, tu);
3973
3974    case CXCursor_ObjCProtocolRef: {
3975      return MakeCXCursor(getCursorObjCProtocolRef(C).first, tu);
3976
3977    case CXCursor_ObjCClassRef:
3978      return MakeCXCursor(getCursorObjCClassRef(C).first, tu );
3979
3980    case CXCursor_TypeRef:
3981      return MakeCXCursor(getCursorTypeRef(C).first, tu );
3982
3983    case CXCursor_TemplateRef:
3984      return MakeCXCursor(getCursorTemplateRef(C).first, tu );
3985
3986    case CXCursor_NamespaceRef:
3987      return MakeCXCursor(getCursorNamespaceRef(C).first, tu );
3988
3989    case CXCursor_MemberRef:
3990      return MakeCXCursor(getCursorMemberRef(C).first, tu );
3991
3992    case CXCursor_CXXBaseSpecifier: {
3993      CXXBaseSpecifier *B = cxcursor::getCursorCXXBaseSpecifier(C);
3994      return clang_getTypeDeclaration(cxtype::MakeCXType(B->getType(),
3995                                                         tu ));
3996    }
3997
3998    case CXCursor_LabelRef:
3999      // FIXME: We end up faking the "parent" declaration here because we
4000      // don't want to make CXCursor larger.
4001      return MakeCXCursor(getCursorLabelRef(C).first,
4002               static_cast<ASTUnit*>(tu->TUData)->getASTContext()
4003                          .getTranslationUnitDecl(),
4004                          tu);
4005
4006    case CXCursor_OverloadedDeclRef:
4007      return C;
4008
4009    default:
4010      // We would prefer to enumerate all non-reference cursor kinds here.
4011      llvm_unreachable("Unhandled reference cursor kind");
4012      break;
4013    }
4014  }
4015
4016  return clang_getNullCursor();
4017}
4018
4019CXCursor clang_getCursorDefinition(CXCursor C) {
4020  if (clang_isInvalid(C.kind))
4021    return clang_getNullCursor();
4022
4023  CXTranslationUnit TU = getCursorTU(C);
4024
4025  bool WasReference = false;
4026  if (clang_isReference(C.kind) || clang_isExpression(C.kind)) {
4027    C = clang_getCursorReferenced(C);
4028    WasReference = true;
4029  }
4030
4031  if (C.kind == CXCursor_MacroExpansion)
4032    return clang_getCursorReferenced(C);
4033
4034  if (!clang_isDeclaration(C.kind))
4035    return clang_getNullCursor();
4036
4037  Decl *D = getCursorDecl(C);
4038  if (!D)
4039    return clang_getNullCursor();
4040
4041  switch (D->getKind()) {
4042  // Declaration kinds that don't really separate the notions of
4043  // declaration and definition.
4044  case Decl::Namespace:
4045  case Decl::Typedef:
4046  case Decl::TypeAlias:
4047  case Decl::TypeAliasTemplate:
4048  case Decl::TemplateTypeParm:
4049  case Decl::EnumConstant:
4050  case Decl::Field:
4051  case Decl::IndirectField:
4052  case Decl::ObjCIvar:
4053  case Decl::ObjCAtDefsField:
4054  case Decl::ImplicitParam:
4055  case Decl::ParmVar:
4056  case Decl::NonTypeTemplateParm:
4057  case Decl::TemplateTemplateParm:
4058  case Decl::ObjCCategoryImpl:
4059  case Decl::ObjCImplementation:
4060  case Decl::AccessSpec:
4061  case Decl::LinkageSpec:
4062  case Decl::ObjCPropertyImpl:
4063  case Decl::FileScopeAsm:
4064  case Decl::StaticAssert:
4065  case Decl::Block:
4066  case Decl::Label:  // FIXME: Is this right??
4067  case Decl::ClassScopeFunctionSpecialization:
4068    return C;
4069
4070  // Declaration kinds that don't make any sense here, but are
4071  // nonetheless harmless.
4072  case Decl::TranslationUnit:
4073    break;
4074
4075  // Declaration kinds for which the definition is not resolvable.
4076  case Decl::UnresolvedUsingTypename:
4077  case Decl::UnresolvedUsingValue:
4078    break;
4079
4080  case Decl::UsingDirective:
4081    return MakeCXCursor(cast<UsingDirectiveDecl>(D)->getNominatedNamespace(),
4082                        TU);
4083
4084  case Decl::NamespaceAlias:
4085    return MakeCXCursor(cast<NamespaceAliasDecl>(D)->getNamespace(), TU);
4086
4087  case Decl::Enum:
4088  case Decl::Record:
4089  case Decl::CXXRecord:
4090  case Decl::ClassTemplateSpecialization:
4091  case Decl::ClassTemplatePartialSpecialization:
4092    if (TagDecl *Def = cast<TagDecl>(D)->getDefinition())
4093      return MakeCXCursor(Def, TU);
4094    return clang_getNullCursor();
4095
4096  case Decl::Function:
4097  case Decl::CXXMethod:
4098  case Decl::CXXConstructor:
4099  case Decl::CXXDestructor:
4100  case Decl::CXXConversion: {
4101    const FunctionDecl *Def = 0;
4102    if (cast<FunctionDecl>(D)->getBody(Def))
4103      return MakeCXCursor(const_cast<FunctionDecl *>(Def), TU);
4104    return clang_getNullCursor();
4105  }
4106
4107  case Decl::Var: {
4108    // Ask the variable if it has a definition.
4109    if (VarDecl *Def = cast<VarDecl>(D)->getDefinition())
4110      return MakeCXCursor(Def, TU);
4111    return clang_getNullCursor();
4112  }
4113
4114  case Decl::FunctionTemplate: {
4115    const FunctionDecl *Def = 0;
4116    if (cast<FunctionTemplateDecl>(D)->getTemplatedDecl()->getBody(Def))
4117      return MakeCXCursor(Def->getDescribedFunctionTemplate(), TU);
4118    return clang_getNullCursor();
4119  }
4120
4121  case Decl::ClassTemplate: {
4122    if (RecordDecl *Def = cast<ClassTemplateDecl>(D)->getTemplatedDecl()
4123                                                            ->getDefinition())
4124      return MakeCXCursor(cast<CXXRecordDecl>(Def)->getDescribedClassTemplate(),
4125                          TU);
4126    return clang_getNullCursor();
4127  }
4128
4129  case Decl::Using:
4130    return MakeCursorOverloadedDeclRef(cast<UsingDecl>(D),
4131                                       D->getLocation(), TU);
4132
4133  case Decl::UsingShadow:
4134    return clang_getCursorDefinition(
4135                       MakeCXCursor(cast<UsingShadowDecl>(D)->getTargetDecl(),
4136                                    TU));
4137
4138  case Decl::ObjCMethod: {
4139    ObjCMethodDecl *Method = cast<ObjCMethodDecl>(D);
4140    if (Method->isThisDeclarationADefinition())
4141      return C;
4142
4143    // Dig out the method definition in the associated
4144    // @implementation, if we have it.
4145    // FIXME: The ASTs should make finding the definition easier.
4146    if (ObjCInterfaceDecl *Class
4147                       = dyn_cast<ObjCInterfaceDecl>(Method->getDeclContext()))
4148      if (ObjCImplementationDecl *ClassImpl = Class->getImplementation())
4149        if (ObjCMethodDecl *Def = ClassImpl->getMethod(Method->getSelector(),
4150                                                  Method->isInstanceMethod()))
4151          if (Def->isThisDeclarationADefinition())
4152            return MakeCXCursor(Def, TU);
4153
4154    return clang_getNullCursor();
4155  }
4156
4157  case Decl::ObjCCategory:
4158    if (ObjCCategoryImplDecl *Impl
4159                               = cast<ObjCCategoryDecl>(D)->getImplementation())
4160      return MakeCXCursor(Impl, TU);
4161    return clang_getNullCursor();
4162
4163  case Decl::ObjCProtocol:
4164    if (!cast<ObjCProtocolDecl>(D)->isForwardDecl())
4165      return C;
4166    return clang_getNullCursor();
4167
4168  case Decl::ObjCInterface:
4169    // There are two notions of a "definition" for an Objective-C
4170    // class: the interface and its implementation. When we resolved a
4171    // reference to an Objective-C class, produce the @interface as
4172    // the definition; when we were provided with the interface,
4173    // produce the @implementation as the definition.
4174    if (WasReference) {
4175      if (!cast<ObjCInterfaceDecl>(D)->isForwardDecl())
4176        return C;
4177    } else if (ObjCImplementationDecl *Impl
4178                              = cast<ObjCInterfaceDecl>(D)->getImplementation())
4179      return MakeCXCursor(Impl, TU);
4180    return clang_getNullCursor();
4181
4182  case Decl::ObjCProperty:
4183    // FIXME: We don't really know where to find the
4184    // ObjCPropertyImplDecls that implement this property.
4185    return clang_getNullCursor();
4186
4187  case Decl::ObjCCompatibleAlias:
4188    if (ObjCInterfaceDecl *Class
4189          = cast<ObjCCompatibleAliasDecl>(D)->getClassInterface())
4190      if (!Class->isForwardDecl())
4191        return MakeCXCursor(Class, TU);
4192
4193    return clang_getNullCursor();
4194
4195  case Decl::ObjCForwardProtocol:
4196    return MakeCursorOverloadedDeclRef(cast<ObjCForwardProtocolDecl>(D),
4197                                       D->getLocation(), TU);
4198
4199  case Decl::ObjCClass:
4200    return MakeCursorOverloadedDeclRef(cast<ObjCClassDecl>(D), D->getLocation(),
4201                                       TU);
4202
4203  case Decl::Friend:
4204    if (NamedDecl *Friend = cast<FriendDecl>(D)->getFriendDecl())
4205      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4206    return clang_getNullCursor();
4207
4208  case Decl::FriendTemplate:
4209    if (NamedDecl *Friend = cast<FriendTemplateDecl>(D)->getFriendDecl())
4210      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4211    return clang_getNullCursor();
4212  }
4213
4214  return clang_getNullCursor();
4215}
4216
4217unsigned clang_isCursorDefinition(CXCursor C) {
4218  if (!clang_isDeclaration(C.kind))
4219    return 0;
4220
4221  return clang_getCursorDefinition(C) == C;
4222}
4223
4224CXCursor clang_getCanonicalCursor(CXCursor C) {
4225  if (!clang_isDeclaration(C.kind))
4226    return C;
4227
4228  if (Decl *D = getCursorDecl(C)) {
4229    if (ObjCCategoryImplDecl *CatImplD = dyn_cast<ObjCCategoryImplDecl>(D))
4230      if (ObjCCategoryDecl *CatD = CatImplD->getCategoryDecl())
4231        return MakeCXCursor(CatD, getCursorTU(C));
4232
4233    if (ObjCImplDecl *ImplD = dyn_cast<ObjCImplDecl>(D))
4234      if (ObjCInterfaceDecl *IFD = ImplD->getClassInterface())
4235        return MakeCXCursor(IFD, getCursorTU(C));
4236
4237    return MakeCXCursor(D->getCanonicalDecl(), getCursorTU(C));
4238  }
4239
4240  return C;
4241}
4242
4243unsigned clang_getNumOverloadedDecls(CXCursor C) {
4244  if (C.kind != CXCursor_OverloadedDeclRef)
4245    return 0;
4246
4247  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
4248  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4249    return E->getNumDecls();
4250
4251  if (OverloadedTemplateStorage *S
4252                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4253    return S->size();
4254
4255  Decl *D = Storage.get<Decl*>();
4256  if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
4257    return Using->shadow_size();
4258  if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
4259    return Classes->size();
4260  if (ObjCForwardProtocolDecl *Protocols =dyn_cast<ObjCForwardProtocolDecl>(D))
4261    return Protocols->protocol_size();
4262
4263  return 0;
4264}
4265
4266CXCursor clang_getOverloadedDecl(CXCursor cursor, unsigned index) {
4267  if (cursor.kind != CXCursor_OverloadedDeclRef)
4268    return clang_getNullCursor();
4269
4270  if (index >= clang_getNumOverloadedDecls(cursor))
4271    return clang_getNullCursor();
4272
4273  CXTranslationUnit TU = getCursorTU(cursor);
4274  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(cursor).first;
4275  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4276    return MakeCXCursor(E->decls_begin()[index], TU);
4277
4278  if (OverloadedTemplateStorage *S
4279                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4280    return MakeCXCursor(S->begin()[index], TU);
4281
4282  Decl *D = Storage.get<Decl*>();
4283  if (UsingDecl *Using = dyn_cast<UsingDecl>(D)) {
4284    // FIXME: This is, unfortunately, linear time.
4285    UsingDecl::shadow_iterator Pos = Using->shadow_begin();
4286    std::advance(Pos, index);
4287    return MakeCXCursor(cast<UsingShadowDecl>(*Pos)->getTargetDecl(), TU);
4288  }
4289
4290  if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
4291    return MakeCXCursor(Classes->begin()[index].getInterface(), TU);
4292
4293  if (ObjCForwardProtocolDecl *Protocols = dyn_cast<ObjCForwardProtocolDecl>(D))
4294    return MakeCXCursor(Protocols->protocol_begin()[index], TU);
4295
4296  return clang_getNullCursor();
4297}
4298
4299void clang_getDefinitionSpellingAndExtent(CXCursor C,
4300                                          const char **startBuf,
4301                                          const char **endBuf,
4302                                          unsigned *startLine,
4303                                          unsigned *startColumn,
4304                                          unsigned *endLine,
4305                                          unsigned *endColumn) {
4306  assert(getCursorDecl(C) && "CXCursor has null decl");
4307  NamedDecl *ND = static_cast<NamedDecl *>(getCursorDecl(C));
4308  FunctionDecl *FD = dyn_cast<FunctionDecl>(ND);
4309  CompoundStmt *Body = dyn_cast<CompoundStmt>(FD->getBody());
4310
4311  SourceManager &SM = FD->getASTContext().getSourceManager();
4312  *startBuf = SM.getCharacterData(Body->getLBracLoc());
4313  *endBuf = SM.getCharacterData(Body->getRBracLoc());
4314  *startLine = SM.getSpellingLineNumber(Body->getLBracLoc());
4315  *startColumn = SM.getSpellingColumnNumber(Body->getLBracLoc());
4316  *endLine = SM.getSpellingLineNumber(Body->getRBracLoc());
4317  *endColumn = SM.getSpellingColumnNumber(Body->getRBracLoc());
4318}
4319
4320
4321CXSourceRange clang_getCursorReferenceNameRange(CXCursor C, unsigned NameFlags,
4322                                                unsigned PieceIndex) {
4323  RefNamePieces Pieces;
4324
4325  switch (C.kind) {
4326  case CXCursor_MemberRefExpr:
4327    if (MemberExpr *E = dyn_cast<MemberExpr>(getCursorExpr(C)))
4328      Pieces = buildPieces(NameFlags, true, E->getMemberNameInfo(),
4329                           E->getQualifierLoc().getSourceRange());
4330    break;
4331
4332  case CXCursor_DeclRefExpr:
4333    if (DeclRefExpr *E = dyn_cast<DeclRefExpr>(getCursorExpr(C)))
4334      Pieces = buildPieces(NameFlags, false, E->getNameInfo(),
4335                           E->getQualifierLoc().getSourceRange(),
4336                           E->getExplicitTemplateArgsOpt());
4337    break;
4338
4339  case CXCursor_CallExpr:
4340    if (CXXOperatorCallExpr *OCE =
4341        dyn_cast<CXXOperatorCallExpr>(getCursorExpr(C))) {
4342      Expr *Callee = OCE->getCallee();
4343      if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Callee))
4344        Callee = ICE->getSubExpr();
4345
4346      if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Callee))
4347        Pieces = buildPieces(NameFlags, false, DRE->getNameInfo(),
4348                             DRE->getQualifierLoc().getSourceRange());
4349    }
4350    break;
4351
4352  default:
4353    break;
4354  }
4355
4356  if (Pieces.empty()) {
4357    if (PieceIndex == 0)
4358      return clang_getCursorExtent(C);
4359  } else if (PieceIndex < Pieces.size()) {
4360      SourceRange R = Pieces[PieceIndex];
4361      if (R.isValid())
4362        return cxloc::translateSourceRange(getCursorContext(C), R);
4363  }
4364
4365  return clang_getNullRange();
4366}
4367
4368void clang_enableStackTraces(void) {
4369  llvm::sys::PrintStackTraceOnErrorSignal();
4370}
4371
4372void clang_executeOnThread(void (*fn)(void*), void *user_data,
4373                           unsigned stack_size) {
4374  llvm::llvm_execute_on_thread(fn, user_data, stack_size);
4375}
4376
4377} // end: extern "C"
4378
4379//===----------------------------------------------------------------------===//
4380// Token-based Operations.
4381//===----------------------------------------------------------------------===//
4382
4383/* CXToken layout:
4384 *   int_data[0]: a CXTokenKind
4385 *   int_data[1]: starting token location
4386 *   int_data[2]: token length
4387 *   int_data[3]: reserved
4388 *   ptr_data: for identifiers and keywords, an IdentifierInfo*.
4389 *   otherwise unused.
4390 */
4391extern "C" {
4392
4393CXTokenKind clang_getTokenKind(CXToken CXTok) {
4394  return static_cast<CXTokenKind>(CXTok.int_data[0]);
4395}
4396
4397CXString clang_getTokenSpelling(CXTranslationUnit TU, CXToken CXTok) {
4398  switch (clang_getTokenKind(CXTok)) {
4399  case CXToken_Identifier:
4400  case CXToken_Keyword:
4401    // We know we have an IdentifierInfo*, so use that.
4402    return createCXString(static_cast<IdentifierInfo *>(CXTok.ptr_data)
4403                            ->getNameStart());
4404
4405  case CXToken_Literal: {
4406    // We have stashed the starting pointer in the ptr_data field. Use it.
4407    const char *Text = static_cast<const char *>(CXTok.ptr_data);
4408    return createCXString(StringRef(Text, CXTok.int_data[2]));
4409  }
4410
4411  case CXToken_Punctuation:
4412  case CXToken_Comment:
4413    break;
4414  }
4415
4416  // We have to find the starting buffer pointer the hard way, by
4417  // deconstructing the source location.
4418  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4419  if (!CXXUnit)
4420    return createCXString("");
4421
4422  SourceLocation Loc = SourceLocation::getFromRawEncoding(CXTok.int_data[1]);
4423  std::pair<FileID, unsigned> LocInfo
4424    = CXXUnit->getSourceManager().getDecomposedLoc(Loc);
4425  bool Invalid = false;
4426  StringRef Buffer
4427    = CXXUnit->getSourceManager().getBufferData(LocInfo.first, &Invalid);
4428  if (Invalid)
4429    return createCXString("");
4430
4431  return createCXString(Buffer.substr(LocInfo.second, CXTok.int_data[2]));
4432}
4433
4434CXSourceLocation clang_getTokenLocation(CXTranslationUnit TU, CXToken CXTok) {
4435  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4436  if (!CXXUnit)
4437    return clang_getNullLocation();
4438
4439  return cxloc::translateSourceLocation(CXXUnit->getASTContext(),
4440                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4441}
4442
4443CXSourceRange clang_getTokenExtent(CXTranslationUnit TU, CXToken CXTok) {
4444  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4445  if (!CXXUnit)
4446    return clang_getNullRange();
4447
4448  return cxloc::translateSourceRange(CXXUnit->getASTContext(),
4449                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4450}
4451
4452void clang_tokenize(CXTranslationUnit TU, CXSourceRange Range,
4453                    CXToken **Tokens, unsigned *NumTokens) {
4454  if (Tokens)
4455    *Tokens = 0;
4456  if (NumTokens)
4457    *NumTokens = 0;
4458
4459  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4460  if (!CXXUnit || !Tokens || !NumTokens)
4461    return;
4462
4463  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
4464
4465  SourceRange R = cxloc::translateCXSourceRange(Range);
4466  if (R.isInvalid())
4467    return;
4468
4469  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4470  std::pair<FileID, unsigned> BeginLocInfo
4471    = SourceMgr.getDecomposedLoc(R.getBegin());
4472  std::pair<FileID, unsigned> EndLocInfo
4473    = SourceMgr.getDecomposedLoc(R.getEnd());
4474
4475  // Cannot tokenize across files.
4476  if (BeginLocInfo.first != EndLocInfo.first)
4477    return;
4478
4479  // Create a lexer
4480  bool Invalid = false;
4481  StringRef Buffer
4482    = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4483  if (Invalid)
4484    return;
4485
4486  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4487            CXXUnit->getASTContext().getLangOptions(),
4488            Buffer.begin(), Buffer.data() + BeginLocInfo.second, Buffer.end());
4489  Lex.SetCommentRetentionState(true);
4490
4491  // Lex tokens until we hit the end of the range.
4492  const char *EffectiveBufferEnd = Buffer.data() + EndLocInfo.second;
4493  SmallVector<CXToken, 32> CXTokens;
4494  Token Tok;
4495  bool previousWasAt = false;
4496  do {
4497    // Lex the next token
4498    Lex.LexFromRawLexer(Tok);
4499    if (Tok.is(tok::eof))
4500      break;
4501
4502    // Initialize the CXToken.
4503    CXToken CXTok;
4504
4505    //   - Common fields
4506    CXTok.int_data[1] = Tok.getLocation().getRawEncoding();
4507    CXTok.int_data[2] = Tok.getLength();
4508    CXTok.int_data[3] = 0;
4509
4510    //   - Kind-specific fields
4511    if (Tok.isLiteral()) {
4512      CXTok.int_data[0] = CXToken_Literal;
4513      CXTok.ptr_data = (void *)Tok.getLiteralData();
4514    } else if (Tok.is(tok::raw_identifier)) {
4515      // Lookup the identifier to determine whether we have a keyword.
4516      IdentifierInfo *II
4517        = CXXUnit->getPreprocessor().LookUpIdentifierInfo(Tok);
4518
4519      if ((II->getObjCKeywordID() != tok::objc_not_keyword) && previousWasAt) {
4520        CXTok.int_data[0] = CXToken_Keyword;
4521      }
4522      else {
4523        CXTok.int_data[0] = Tok.is(tok::identifier)
4524          ? CXToken_Identifier
4525          : CXToken_Keyword;
4526      }
4527      CXTok.ptr_data = II;
4528    } else if (Tok.is(tok::comment)) {
4529      CXTok.int_data[0] = CXToken_Comment;
4530      CXTok.ptr_data = 0;
4531    } else {
4532      CXTok.int_data[0] = CXToken_Punctuation;
4533      CXTok.ptr_data = 0;
4534    }
4535    CXTokens.push_back(CXTok);
4536    previousWasAt = Tok.is(tok::at);
4537  } while (Lex.getBufferLocation() <= EffectiveBufferEnd);
4538
4539  if (CXTokens.empty())
4540    return;
4541
4542  *Tokens = (CXToken *)malloc(sizeof(CXToken) * CXTokens.size());
4543  memmove(*Tokens, CXTokens.data(), sizeof(CXToken) * CXTokens.size());
4544  *NumTokens = CXTokens.size();
4545}
4546
4547void clang_disposeTokens(CXTranslationUnit TU,
4548                         CXToken *Tokens, unsigned NumTokens) {
4549  free(Tokens);
4550}
4551
4552} // end: extern "C"
4553
4554//===----------------------------------------------------------------------===//
4555// Token annotation APIs.
4556//===----------------------------------------------------------------------===//
4557
4558typedef llvm::DenseMap<unsigned, CXCursor> AnnotateTokensData;
4559static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4560                                                     CXCursor parent,
4561                                                     CXClientData client_data);
4562namespace {
4563class AnnotateTokensWorker {
4564  AnnotateTokensData &Annotated;
4565  CXToken *Tokens;
4566  CXCursor *Cursors;
4567  unsigned NumTokens;
4568  unsigned TokIdx;
4569  unsigned PreprocessingTokIdx;
4570  CursorVisitor AnnotateVis;
4571  SourceManager &SrcMgr;
4572  bool HasContextSensitiveKeywords;
4573
4574  bool MoreTokens() const { return TokIdx < NumTokens; }
4575  unsigned NextToken() const { return TokIdx; }
4576  void AdvanceToken() { ++TokIdx; }
4577  SourceLocation GetTokenLoc(unsigned tokI) {
4578    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4579  }
4580
4581public:
4582  AnnotateTokensWorker(AnnotateTokensData &annotated,
4583                       CXToken *tokens, CXCursor *cursors, unsigned numTokens,
4584                       CXTranslationUnit tu, SourceRange RegionOfInterest)
4585    : Annotated(annotated), Tokens(tokens), Cursors(cursors),
4586      NumTokens(numTokens), TokIdx(0), PreprocessingTokIdx(0),
4587      AnnotateVis(tu,
4588                  AnnotateTokensVisitor, this,
4589                  Decl::MaxPCHLevel, true, RegionOfInterest),
4590      SrcMgr(static_cast<ASTUnit*>(tu->TUData)->getSourceManager()),
4591      HasContextSensitiveKeywords(false) { }
4592
4593  void VisitChildren(CXCursor C) { AnnotateVis.VisitChildren(C); }
4594  enum CXChildVisitResult Visit(CXCursor cursor, CXCursor parent);
4595  void AnnotateTokens(CXCursor parent);
4596  void AnnotateTokens() {
4597    AnnotateTokens(clang_getTranslationUnitCursor(AnnotateVis.getTU()));
4598  }
4599
4600  /// \brief Determine whether the annotator saw any cursors that have
4601  /// context-sensitive keywords.
4602  bool hasContextSensitiveKeywords() const {
4603    return HasContextSensitiveKeywords;
4604  }
4605};
4606}
4607
4608void AnnotateTokensWorker::AnnotateTokens(CXCursor parent) {
4609  // Walk the AST within the region of interest, annotating tokens
4610  // along the way.
4611  VisitChildren(parent);
4612
4613  for (unsigned I = 0 ; I < TokIdx ; ++I) {
4614    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4615    if (Pos != Annotated.end() &&
4616        (clang_isInvalid(Cursors[I].kind) ||
4617         Pos->second.kind != CXCursor_PreprocessingDirective))
4618      Cursors[I] = Pos->second;
4619  }
4620
4621  // Finish up annotating any tokens left.
4622  if (!MoreTokens())
4623    return;
4624
4625  const CXCursor &C = clang_getNullCursor();
4626  for (unsigned I = TokIdx ; I < NumTokens ; ++I) {
4627    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4628    Cursors[I] = (Pos == Annotated.end()) ? C : Pos->second;
4629  }
4630}
4631
4632enum CXChildVisitResult
4633AnnotateTokensWorker::Visit(CXCursor cursor, CXCursor parent) {
4634  CXSourceLocation Loc = clang_getCursorLocation(cursor);
4635  SourceRange cursorRange = getRawCursorExtent(cursor);
4636  if (cursorRange.isInvalid())
4637    return CXChildVisit_Recurse;
4638
4639  if (!HasContextSensitiveKeywords) {
4640    // Objective-C properties can have context-sensitive keywords.
4641    if (cursor.kind == CXCursor_ObjCPropertyDecl) {
4642      if (ObjCPropertyDecl *Property
4643                  = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(cursor)))
4644        HasContextSensitiveKeywords = Property->getPropertyAttributesAsWritten() != 0;
4645    }
4646    // Objective-C methods can have context-sensitive keywords.
4647    else if (cursor.kind == CXCursor_ObjCInstanceMethodDecl ||
4648             cursor.kind == CXCursor_ObjCClassMethodDecl) {
4649      if (ObjCMethodDecl *Method
4650            = dyn_cast_or_null<ObjCMethodDecl>(getCursorDecl(cursor))) {
4651        if (Method->getObjCDeclQualifier())
4652          HasContextSensitiveKeywords = true;
4653        else {
4654          for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
4655                                           PEnd = Method->param_end();
4656               P != PEnd; ++P) {
4657            if ((*P)->getObjCDeclQualifier()) {
4658              HasContextSensitiveKeywords = true;
4659              break;
4660            }
4661          }
4662        }
4663      }
4664    }
4665    // C++ methods can have context-sensitive keywords.
4666    else if (cursor.kind == CXCursor_CXXMethod) {
4667      if (CXXMethodDecl *Method
4668                  = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(cursor))) {
4669        if (Method->hasAttr<FinalAttr>() || Method->hasAttr<OverrideAttr>())
4670          HasContextSensitiveKeywords = true;
4671      }
4672    }
4673    // C++ classes can have context-sensitive keywords.
4674    else if (cursor.kind == CXCursor_StructDecl ||
4675             cursor.kind == CXCursor_ClassDecl ||
4676             cursor.kind == CXCursor_ClassTemplate ||
4677             cursor.kind == CXCursor_ClassTemplatePartialSpecialization) {
4678      if (Decl *D = getCursorDecl(cursor))
4679        if (D->hasAttr<FinalAttr>())
4680          HasContextSensitiveKeywords = true;
4681    }
4682  }
4683
4684  if (clang_isPreprocessing(cursor.kind)) {
4685    // For macro expansions, just note where the beginning of the macro
4686    // expansion occurs.
4687    if (cursor.kind == CXCursor_MacroExpansion) {
4688      Annotated[Loc.int_data] = cursor;
4689      return CXChildVisit_Recurse;
4690    }
4691
4692    // Items in the preprocessing record are kept separate from items in
4693    // declarations, so we keep a separate token index.
4694    unsigned SavedTokIdx = TokIdx;
4695    TokIdx = PreprocessingTokIdx;
4696
4697    // Skip tokens up until we catch up to the beginning of the preprocessing
4698    // entry.
4699    while (MoreTokens()) {
4700      const unsigned I = NextToken();
4701      SourceLocation TokLoc = GetTokenLoc(I);
4702      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4703      case RangeBefore:
4704        AdvanceToken();
4705        continue;
4706      case RangeAfter:
4707      case RangeOverlap:
4708        break;
4709      }
4710      break;
4711    }
4712
4713    // Look at all of the tokens within this range.
4714    while (MoreTokens()) {
4715      const unsigned I = NextToken();
4716      SourceLocation TokLoc = GetTokenLoc(I);
4717      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4718      case RangeBefore:
4719        assert(0 && "Infeasible");
4720      case RangeAfter:
4721        break;
4722      case RangeOverlap:
4723        Cursors[I] = cursor;
4724        AdvanceToken();
4725        continue;
4726      }
4727      break;
4728    }
4729
4730    // Save the preprocessing token index; restore the non-preprocessing
4731    // token index.
4732    PreprocessingTokIdx = TokIdx;
4733    TokIdx = SavedTokIdx;
4734    return CXChildVisit_Recurse;
4735  }
4736
4737  if (cursorRange.isInvalid())
4738    return CXChildVisit_Continue;
4739
4740  SourceLocation L = SourceLocation::getFromRawEncoding(Loc.int_data);
4741
4742  // Adjust the annotated range based specific declarations.
4743  const enum CXCursorKind cursorK = clang_getCursorKind(cursor);
4744  if (cursorK >= CXCursor_FirstDecl && cursorK <= CXCursor_LastDecl) {
4745    Decl *D = cxcursor::getCursorDecl(cursor);
4746    // Don't visit synthesized ObjC methods, since they have no syntatic
4747    // representation in the source.
4748    if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
4749      if (MD->isSynthesized())
4750        return CXChildVisit_Continue;
4751    }
4752
4753    SourceLocation StartLoc;
4754    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
4755      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
4756        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4757    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
4758      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
4759        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4760    }
4761
4762    if (StartLoc.isValid() && L.isValid() &&
4763        SrcMgr.isBeforeInTranslationUnit(StartLoc, L))
4764      cursorRange.setBegin(StartLoc);
4765  }
4766
4767  // If the location of the cursor occurs within a macro instantiation, record
4768  // the spelling location of the cursor in our annotation map.  We can then
4769  // paper over the token labelings during a post-processing step to try and
4770  // get cursor mappings for tokens that are the *arguments* of a macro
4771  // instantiation.
4772  if (L.isMacroID()) {
4773    unsigned rawEncoding = SrcMgr.getSpellingLoc(L).getRawEncoding();
4774    // Only invalidate the old annotation if it isn't part of a preprocessing
4775    // directive.  Here we assume that the default construction of CXCursor
4776    // results in CXCursor.kind being an initialized value (i.e., 0).  If
4777    // this isn't the case, we can fix by doing lookup + insertion.
4778
4779    CXCursor &oldC = Annotated[rawEncoding];
4780    if (!clang_isPreprocessing(oldC.kind))
4781      oldC = cursor;
4782  }
4783
4784  const enum CXCursorKind K = clang_getCursorKind(parent);
4785  const CXCursor updateC =
4786    (clang_isInvalid(K) || K == CXCursor_TranslationUnit)
4787     ? clang_getNullCursor() : parent;
4788
4789  while (MoreTokens()) {
4790    const unsigned I = NextToken();
4791    SourceLocation TokLoc = GetTokenLoc(I);
4792    switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4793      case RangeBefore:
4794        Cursors[I] = updateC;
4795        AdvanceToken();
4796        continue;
4797      case RangeAfter:
4798      case RangeOverlap:
4799        break;
4800    }
4801    break;
4802  }
4803
4804  // Avoid having the cursor of an expression "overwrite" the annotation of the
4805  // variable declaration that it belongs to.
4806  // This can happen for C++ constructor expressions whose range generally
4807  // include the variable declaration, e.g.:
4808  //  MyCXXClass foo; // Make sure we don't annotate 'foo' as a CallExpr cursor.
4809  if (clang_isExpression(cursorK)) {
4810    Expr *E = getCursorExpr(cursor);
4811    if (Decl *D = getCursorParentDecl(cursor)) {
4812      const unsigned I = NextToken();
4813      if (E->getLocStart().isValid() && D->getLocation().isValid() &&
4814          E->getLocStart() == D->getLocation() &&
4815          E->getLocStart() == GetTokenLoc(I)) {
4816        Cursors[I] = updateC;
4817        AdvanceToken();
4818      }
4819    }
4820  }
4821
4822  // Visit children to get their cursor information.
4823  const unsigned BeforeChildren = NextToken();
4824  VisitChildren(cursor);
4825  const unsigned AfterChildren = NextToken();
4826
4827  // Adjust 'Last' to the last token within the extent of the cursor.
4828  while (MoreTokens()) {
4829    const unsigned I = NextToken();
4830    SourceLocation TokLoc = GetTokenLoc(I);
4831    switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4832      case RangeBefore:
4833        assert(0 && "Infeasible");
4834      case RangeAfter:
4835        break;
4836      case RangeOverlap:
4837        Cursors[I] = updateC;
4838        AdvanceToken();
4839        continue;
4840    }
4841    break;
4842  }
4843  const unsigned Last = NextToken();
4844
4845  // Scan the tokens that are at the beginning of the cursor, but are not
4846  // capture by the child cursors.
4847
4848  // For AST elements within macros, rely on a post-annotate pass to
4849  // to correctly annotate the tokens with cursors.  Otherwise we can
4850  // get confusing results of having tokens that map to cursors that really
4851  // are expanded by an instantiation.
4852  if (L.isMacroID())
4853    cursor = clang_getNullCursor();
4854
4855  for (unsigned I = BeforeChildren; I != AfterChildren; ++I) {
4856    if (!clang_isInvalid(clang_getCursorKind(Cursors[I])))
4857      break;
4858
4859    Cursors[I] = cursor;
4860  }
4861  // Scan the tokens that are at the end of the cursor, but are not captured
4862  // but the child cursors.
4863  for (unsigned I = AfterChildren; I != Last; ++I)
4864    Cursors[I] = cursor;
4865
4866  TokIdx = Last;
4867  return CXChildVisit_Continue;
4868}
4869
4870static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4871                                                     CXCursor parent,
4872                                                     CXClientData client_data) {
4873  return static_cast<AnnotateTokensWorker*>(client_data)->Visit(cursor, parent);
4874}
4875
4876namespace {
4877  struct clang_annotateTokens_Data {
4878    CXTranslationUnit TU;
4879    ASTUnit *CXXUnit;
4880    CXToken *Tokens;
4881    unsigned NumTokens;
4882    CXCursor *Cursors;
4883  };
4884}
4885
4886// This gets run a separate thread to avoid stack blowout.
4887static void clang_annotateTokensImpl(void *UserData) {
4888  CXTranslationUnit TU = ((clang_annotateTokens_Data*)UserData)->TU;
4889  ASTUnit *CXXUnit = ((clang_annotateTokens_Data*)UserData)->CXXUnit;
4890  CXToken *Tokens = ((clang_annotateTokens_Data*)UserData)->Tokens;
4891  const unsigned NumTokens = ((clang_annotateTokens_Data*)UserData)->NumTokens;
4892  CXCursor *Cursors = ((clang_annotateTokens_Data*)UserData)->Cursors;
4893
4894  // Determine the region of interest, which contains all of the tokens.
4895  SourceRange RegionOfInterest;
4896  RegionOfInterest.setBegin(
4897    cxloc::translateSourceLocation(clang_getTokenLocation(TU, Tokens[0])));
4898  RegionOfInterest.setEnd(
4899    cxloc::translateSourceLocation(clang_getTokenLocation(TU,
4900                                                         Tokens[NumTokens-1])));
4901
4902  // A mapping from the source locations found when re-lexing or traversing the
4903  // region of interest to the corresponding cursors.
4904  AnnotateTokensData Annotated;
4905
4906  // Relex the tokens within the source range to look for preprocessing
4907  // directives.
4908  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4909  std::pair<FileID, unsigned> BeginLocInfo
4910    = SourceMgr.getDecomposedLoc(RegionOfInterest.getBegin());
4911  std::pair<FileID, unsigned> EndLocInfo
4912    = SourceMgr.getDecomposedLoc(RegionOfInterest.getEnd());
4913
4914  StringRef Buffer;
4915  bool Invalid = false;
4916  if (BeginLocInfo.first == EndLocInfo.first &&
4917      ((Buffer = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid)),true) &&
4918      !Invalid) {
4919    Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4920              CXXUnit->getASTContext().getLangOptions(),
4921              Buffer.begin(), Buffer.data() + BeginLocInfo.second,
4922              Buffer.end());
4923    Lex.SetCommentRetentionState(true);
4924
4925    // Lex tokens in raw mode until we hit the end of the range, to avoid
4926    // entering #includes or expanding macros.
4927    while (true) {
4928      Token Tok;
4929      Lex.LexFromRawLexer(Tok);
4930
4931    reprocess:
4932      if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
4933        // We have found a preprocessing directive. Gobble it up so that we
4934        // don't see it while preprocessing these tokens later, but keep track
4935        // of all of the token locations inside this preprocessing directive so
4936        // that we can annotate them appropriately.
4937        //
4938        // FIXME: Some simple tests here could identify macro definitions and
4939        // #undefs, to provide specific cursor kinds for those.
4940        SmallVector<SourceLocation, 32> Locations;
4941        do {
4942          Locations.push_back(Tok.getLocation());
4943          Lex.LexFromRawLexer(Tok);
4944        } while (!Tok.isAtStartOfLine() && !Tok.is(tok::eof));
4945
4946        using namespace cxcursor;
4947        CXCursor Cursor
4948        = MakePreprocessingDirectiveCursor(SourceRange(Locations.front(),
4949                                                       Locations.back()),
4950                                           TU);
4951        for (unsigned I = 0, N = Locations.size(); I != N; ++I) {
4952          Annotated[Locations[I].getRawEncoding()] = Cursor;
4953        }
4954
4955        if (Tok.isAtStartOfLine())
4956          goto reprocess;
4957
4958        continue;
4959      }
4960
4961      if (Tok.is(tok::eof))
4962        break;
4963    }
4964  }
4965
4966  // Annotate all of the source locations in the region of interest that map to
4967  // a specific cursor.
4968  AnnotateTokensWorker W(Annotated, Tokens, Cursors, NumTokens,
4969                         TU, RegionOfInterest);
4970
4971  // FIXME: We use a ridiculous stack size here because the data-recursion
4972  // algorithm uses a large stack frame than the non-data recursive version,
4973  // and AnnotationTokensWorker currently transforms the data-recursion
4974  // algorithm back into a traditional recursion by explicitly calling
4975  // VisitChildren().  We will need to remove this explicit recursive call.
4976  W.AnnotateTokens();
4977
4978  // If we ran into any entities that involve context-sensitive keywords,
4979  // take another pass through the tokens to mark them as such.
4980  if (W.hasContextSensitiveKeywords()) {
4981    for (unsigned I = 0; I != NumTokens; ++I) {
4982      if (clang_getTokenKind(Tokens[I]) != CXToken_Identifier)
4983        continue;
4984
4985      if (Cursors[I].kind == CXCursor_ObjCPropertyDecl) {
4986        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
4987        if (ObjCPropertyDecl *Property
4988            = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(Cursors[I]))) {
4989          if (Property->getPropertyAttributesAsWritten() != 0 &&
4990              llvm::StringSwitch<bool>(II->getName())
4991              .Case("readonly", true)
4992              .Case("assign", true)
4993              .Case("unsafe_unretained", true)
4994              .Case("readwrite", true)
4995              .Case("retain", true)
4996              .Case("copy", true)
4997              .Case("nonatomic", true)
4998              .Case("atomic", true)
4999              .Case("getter", true)
5000              .Case("setter", true)
5001              .Case("strong", true)
5002              .Case("weak", true)
5003              .Default(false))
5004            Tokens[I].int_data[0] = CXToken_Keyword;
5005        }
5006        continue;
5007      }
5008
5009      if (Cursors[I].kind == CXCursor_ObjCInstanceMethodDecl ||
5010          Cursors[I].kind == CXCursor_ObjCClassMethodDecl) {
5011        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5012        if (llvm::StringSwitch<bool>(II->getName())
5013            .Case("in", true)
5014            .Case("out", true)
5015            .Case("inout", true)
5016            .Case("oneway", true)
5017            .Case("bycopy", true)
5018            .Case("byref", true)
5019            .Default(false))
5020          Tokens[I].int_data[0] = CXToken_Keyword;
5021        continue;
5022      }
5023
5024      if (Cursors[I].kind == CXCursor_CXXMethod) {
5025        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5026        if (CXXMethodDecl *Method
5027            = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(Cursors[I]))) {
5028          if ((Method->hasAttr<FinalAttr>() ||
5029               Method->hasAttr<OverrideAttr>()) &&
5030              Method->getLocation().getRawEncoding() != Tokens[I].int_data[1] &&
5031              llvm::StringSwitch<bool>(II->getName())
5032              .Case("final", true)
5033              .Case("override", true)
5034              .Default(false))
5035            Tokens[I].int_data[0] = CXToken_Keyword;
5036        }
5037        continue;
5038      }
5039
5040      if (Cursors[I].kind == CXCursor_ClassDecl ||
5041          Cursors[I].kind == CXCursor_StructDecl ||
5042          Cursors[I].kind == CXCursor_ClassTemplate) {
5043        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5044        if (II->getName() == "final") {
5045          // We have to be careful with 'final', since it could be the name
5046          // of a member class rather than the context-sensitive keyword.
5047          // So, check whether the cursor associated with this
5048          Decl *D = getCursorDecl(Cursors[I]);
5049          if (CXXRecordDecl *Record = dyn_cast_or_null<CXXRecordDecl>(D)) {
5050            if ((Record->hasAttr<FinalAttr>()) &&
5051                Record->getIdentifier() != II)
5052              Tokens[I].int_data[0] = CXToken_Keyword;
5053          } else if (ClassTemplateDecl *ClassTemplate
5054                     = dyn_cast_or_null<ClassTemplateDecl>(D)) {
5055            CXXRecordDecl *Record = ClassTemplate->getTemplatedDecl();
5056            if ((Record->hasAttr<FinalAttr>()) &&
5057                Record->getIdentifier() != II)
5058              Tokens[I].int_data[0] = CXToken_Keyword;
5059          }
5060        }
5061        continue;
5062      }
5063    }
5064  }
5065}
5066
5067extern "C" {
5068
5069void clang_annotateTokens(CXTranslationUnit TU,
5070                          CXToken *Tokens, unsigned NumTokens,
5071                          CXCursor *Cursors) {
5072
5073  if (NumTokens == 0 || !Tokens || !Cursors)
5074    return;
5075
5076  // Any token we don't specifically annotate will have a NULL cursor.
5077  CXCursor C = clang_getNullCursor();
5078  for (unsigned I = 0; I != NumTokens; ++I)
5079    Cursors[I] = C;
5080
5081  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
5082  if (!CXXUnit)
5083    return;
5084
5085  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
5086
5087  clang_annotateTokens_Data data = { TU, CXXUnit, Tokens, NumTokens, Cursors };
5088  llvm::CrashRecoveryContext CRC;
5089  if (!RunSafely(CRC, clang_annotateTokensImpl, &data,
5090                 GetSafetyThreadStackSize() * 2)) {
5091    fprintf(stderr, "libclang: crash detected while annotating tokens\n");
5092  }
5093}
5094
5095} // end: extern "C"
5096
5097//===----------------------------------------------------------------------===//
5098// Operations for querying linkage of a cursor.
5099//===----------------------------------------------------------------------===//
5100
5101extern "C" {
5102CXLinkageKind clang_getCursorLinkage(CXCursor cursor) {
5103  if (!clang_isDeclaration(cursor.kind))
5104    return CXLinkage_Invalid;
5105
5106  Decl *D = cxcursor::getCursorDecl(cursor);
5107  if (NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
5108    switch (ND->getLinkage()) {
5109      case NoLinkage: return CXLinkage_NoLinkage;
5110      case InternalLinkage: return CXLinkage_Internal;
5111      case UniqueExternalLinkage: return CXLinkage_UniqueExternal;
5112      case ExternalLinkage: return CXLinkage_External;
5113    };
5114
5115  return CXLinkage_Invalid;
5116}
5117} // end: extern "C"
5118
5119//===----------------------------------------------------------------------===//
5120// Operations for querying language of a cursor.
5121//===----------------------------------------------------------------------===//
5122
5123static CXLanguageKind getDeclLanguage(const Decl *D) {
5124  switch (D->getKind()) {
5125    default:
5126      break;
5127    case Decl::ImplicitParam:
5128    case Decl::ObjCAtDefsField:
5129    case Decl::ObjCCategory:
5130    case Decl::ObjCCategoryImpl:
5131    case Decl::ObjCClass:
5132    case Decl::ObjCCompatibleAlias:
5133    case Decl::ObjCForwardProtocol:
5134    case Decl::ObjCImplementation:
5135    case Decl::ObjCInterface:
5136    case Decl::ObjCIvar:
5137    case Decl::ObjCMethod:
5138    case Decl::ObjCProperty:
5139    case Decl::ObjCPropertyImpl:
5140    case Decl::ObjCProtocol:
5141      return CXLanguage_ObjC;
5142    case Decl::CXXConstructor:
5143    case Decl::CXXConversion:
5144    case Decl::CXXDestructor:
5145    case Decl::CXXMethod:
5146    case Decl::CXXRecord:
5147    case Decl::ClassTemplate:
5148    case Decl::ClassTemplatePartialSpecialization:
5149    case Decl::ClassTemplateSpecialization:
5150    case Decl::Friend:
5151    case Decl::FriendTemplate:
5152    case Decl::FunctionTemplate:
5153    case Decl::LinkageSpec:
5154    case Decl::Namespace:
5155    case Decl::NamespaceAlias:
5156    case Decl::NonTypeTemplateParm:
5157    case Decl::StaticAssert:
5158    case Decl::TemplateTemplateParm:
5159    case Decl::TemplateTypeParm:
5160    case Decl::UnresolvedUsingTypename:
5161    case Decl::UnresolvedUsingValue:
5162    case Decl::Using:
5163    case Decl::UsingDirective:
5164    case Decl::UsingShadow:
5165      return CXLanguage_CPlusPlus;
5166  }
5167
5168  return CXLanguage_C;
5169}
5170
5171extern "C" {
5172
5173enum CXAvailabilityKind clang_getCursorAvailability(CXCursor cursor) {
5174  if (clang_isDeclaration(cursor.kind))
5175    if (Decl *D = cxcursor::getCursorDecl(cursor)) {
5176      if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->isDeleted())
5177        return CXAvailability_Available;
5178
5179      switch (D->getAvailability()) {
5180      case AR_Available:
5181      case AR_NotYetIntroduced:
5182        return CXAvailability_Available;
5183
5184      case AR_Deprecated:
5185        return CXAvailability_Deprecated;
5186
5187      case AR_Unavailable:
5188        return CXAvailability_NotAvailable;
5189      }
5190    }
5191
5192  return CXAvailability_Available;
5193}
5194
5195CXLanguageKind clang_getCursorLanguage(CXCursor cursor) {
5196  if (clang_isDeclaration(cursor.kind))
5197    return getDeclLanguage(cxcursor::getCursorDecl(cursor));
5198
5199  return CXLanguage_Invalid;
5200}
5201
5202 /// \brief If the given cursor is the "templated" declaration
5203 /// descibing a class or function template, return the class or
5204 /// function template.
5205static Decl *maybeGetTemplateCursor(Decl *D) {
5206  if (!D)
5207    return 0;
5208
5209  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
5210    if (FunctionTemplateDecl *FunTmpl = FD->getDescribedFunctionTemplate())
5211      return FunTmpl;
5212
5213  if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D))
5214    if (ClassTemplateDecl *ClassTmpl = RD->getDescribedClassTemplate())
5215      return ClassTmpl;
5216
5217  return D;
5218}
5219
5220CXCursor clang_getCursorSemanticParent(CXCursor cursor) {
5221  if (clang_isDeclaration(cursor.kind)) {
5222    if (Decl *D = getCursorDecl(cursor)) {
5223      DeclContext *DC = D->getDeclContext();
5224      if (!DC)
5225        return clang_getNullCursor();
5226
5227      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5228                          getCursorTU(cursor));
5229    }
5230  }
5231
5232  if (clang_isStatement(cursor.kind) || clang_isExpression(cursor.kind)) {
5233    if (Decl *D = getCursorDecl(cursor))
5234      return MakeCXCursor(D, getCursorTU(cursor));
5235  }
5236
5237  return clang_getNullCursor();
5238}
5239
5240CXCursor clang_getCursorLexicalParent(CXCursor cursor) {
5241  if (clang_isDeclaration(cursor.kind)) {
5242    if (Decl *D = getCursorDecl(cursor)) {
5243      DeclContext *DC = D->getLexicalDeclContext();
5244      if (!DC)
5245        return clang_getNullCursor();
5246
5247      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5248                          getCursorTU(cursor));
5249    }
5250  }
5251
5252  // FIXME: Note that we can't easily compute the lexical context of a
5253  // statement or expression, so we return nothing.
5254  return clang_getNullCursor();
5255}
5256
5257static void CollectOverriddenMethods(DeclContext *Ctx,
5258                                     ObjCMethodDecl *Method,
5259                            SmallVectorImpl<ObjCMethodDecl *> &Methods) {
5260  if (!Ctx)
5261    return;
5262
5263  // If we have a class or category implementation, jump straight to the
5264  // interface.
5265  if (ObjCImplDecl *Impl = dyn_cast<ObjCImplDecl>(Ctx))
5266    return CollectOverriddenMethods(Impl->getClassInterface(), Method, Methods);
5267
5268  ObjCContainerDecl *Container = dyn_cast<ObjCContainerDecl>(Ctx);
5269  if (!Container)
5270    return;
5271
5272  // Check whether we have a matching method at this level.
5273  if (ObjCMethodDecl *Overridden = Container->getMethod(Method->getSelector(),
5274                                                    Method->isInstanceMethod()))
5275    if (Method != Overridden) {
5276      // We found an override at this level; there is no need to look
5277      // into other protocols or categories.
5278      Methods.push_back(Overridden);
5279      return;
5280    }
5281
5282  if (ObjCProtocolDecl *Protocol = dyn_cast<ObjCProtocolDecl>(Container)) {
5283    for (ObjCProtocolDecl::protocol_iterator P = Protocol->protocol_begin(),
5284                                          PEnd = Protocol->protocol_end();
5285         P != PEnd; ++P)
5286      CollectOverriddenMethods(*P, Method, Methods);
5287  }
5288
5289  if (ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(Container)) {
5290    for (ObjCCategoryDecl::protocol_iterator P = Category->protocol_begin(),
5291                                          PEnd = Category->protocol_end();
5292         P != PEnd; ++P)
5293      CollectOverriddenMethods(*P, Method, Methods);
5294  }
5295
5296  if (ObjCInterfaceDecl *Interface = dyn_cast<ObjCInterfaceDecl>(Container)) {
5297    for (ObjCInterfaceDecl::protocol_iterator P = Interface->protocol_begin(),
5298                                           PEnd = Interface->protocol_end();
5299         P != PEnd; ++P)
5300      CollectOverriddenMethods(*P, Method, Methods);
5301
5302    for (ObjCCategoryDecl *Category = Interface->getCategoryList();
5303         Category; Category = Category->getNextClassCategory())
5304      CollectOverriddenMethods(Category, Method, Methods);
5305
5306    // We only look into the superclass if we haven't found anything yet.
5307    if (Methods.empty())
5308      if (ObjCInterfaceDecl *Super = Interface->getSuperClass())
5309        return CollectOverriddenMethods(Super, Method, Methods);
5310  }
5311}
5312
5313void clang_getOverriddenCursors(CXCursor cursor,
5314                                CXCursor **overridden,
5315                                unsigned *num_overridden) {
5316  if (overridden)
5317    *overridden = 0;
5318  if (num_overridden)
5319    *num_overridden = 0;
5320  if (!overridden || !num_overridden)
5321    return;
5322
5323  if (!clang_isDeclaration(cursor.kind))
5324    return;
5325
5326  Decl *D = getCursorDecl(cursor);
5327  if (!D)
5328    return;
5329
5330  // Handle C++ member functions.
5331  CXTranslationUnit TU = getCursorTU(cursor);
5332  if (CXXMethodDecl *CXXMethod = dyn_cast<CXXMethodDecl>(D)) {
5333    *num_overridden = CXXMethod->size_overridden_methods();
5334    if (!*num_overridden)
5335      return;
5336
5337    *overridden = new CXCursor [*num_overridden];
5338    unsigned I = 0;
5339    for (CXXMethodDecl::method_iterator
5340              M = CXXMethod->begin_overridden_methods(),
5341           MEnd = CXXMethod->end_overridden_methods();
5342         M != MEnd; (void)++M, ++I)
5343      (*overridden)[I] = MakeCXCursor(const_cast<CXXMethodDecl*>(*M), TU);
5344    return;
5345  }
5346
5347  ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(D);
5348  if (!Method)
5349    return;
5350
5351  // Handle Objective-C methods.
5352  SmallVector<ObjCMethodDecl *, 4> Methods;
5353  CollectOverriddenMethods(Method->getDeclContext(), Method, Methods);
5354
5355  if (Methods.empty())
5356    return;
5357
5358  *num_overridden = Methods.size();
5359  *overridden = new CXCursor [Methods.size()];
5360  for (unsigned I = 0, N = Methods.size(); I != N; ++I)
5361    (*overridden)[I] = MakeCXCursor(Methods[I], TU);
5362}
5363
5364void clang_disposeOverriddenCursors(CXCursor *overridden) {
5365  delete [] overridden;
5366}
5367
5368CXFile clang_getIncludedFile(CXCursor cursor) {
5369  if (cursor.kind != CXCursor_InclusionDirective)
5370    return 0;
5371
5372  InclusionDirective *ID = getCursorInclusionDirective(cursor);
5373  return (void *)ID->getFile();
5374}
5375
5376} // end: extern "C"
5377
5378
5379//===----------------------------------------------------------------------===//
5380// C++ AST instrospection.
5381//===----------------------------------------------------------------------===//
5382
5383extern "C" {
5384unsigned clang_CXXMethod_isStatic(CXCursor C) {
5385  if (!clang_isDeclaration(C.kind))
5386    return 0;
5387
5388  CXXMethodDecl *Method = 0;
5389  Decl *D = cxcursor::getCursorDecl(C);
5390  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5391    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5392  else
5393    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5394  return (Method && Method->isStatic()) ? 1 : 0;
5395}
5396
5397unsigned clang_CXXMethod_isVirtual(CXCursor C) {
5398  if (!clang_isDeclaration(C.kind))
5399    return 0;
5400
5401  CXXMethodDecl *Method = 0;
5402  Decl *D = cxcursor::getCursorDecl(C);
5403  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5404    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5405  else
5406    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5407  return (Method && Method->isVirtual()) ? 1 : 0;
5408}
5409
5410} // end: extern "C"
5411
5412//===----------------------------------------------------------------------===//
5413// Attribute introspection.
5414//===----------------------------------------------------------------------===//
5415
5416extern "C" {
5417CXType clang_getIBOutletCollectionType(CXCursor C) {
5418  if (C.kind != CXCursor_IBOutletCollectionAttr)
5419    return cxtype::MakeCXType(QualType(), cxcursor::getCursorTU(C));
5420
5421  IBOutletCollectionAttr *A =
5422    cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(C));
5423
5424  return cxtype::MakeCXType(A->getInterFace(), cxcursor::getCursorTU(C));
5425}
5426} // end: extern "C"
5427
5428//===----------------------------------------------------------------------===//
5429// Inspecting memory usage.
5430//===----------------------------------------------------------------------===//
5431
5432typedef std::vector<CXTUResourceUsageEntry> MemUsageEntries;
5433
5434static inline void createCXTUResourceUsageEntry(MemUsageEntries &entries,
5435                                              enum CXTUResourceUsageKind k,
5436                                              unsigned long amount) {
5437  CXTUResourceUsageEntry entry = { k, amount };
5438  entries.push_back(entry);
5439}
5440
5441extern "C" {
5442
5443const char *clang_getTUResourceUsageName(CXTUResourceUsageKind kind) {
5444  const char *str = "";
5445  switch (kind) {
5446    case CXTUResourceUsage_AST:
5447      str = "ASTContext: expressions, declarations, and types";
5448      break;
5449    case CXTUResourceUsage_Identifiers:
5450      str = "ASTContext: identifiers";
5451      break;
5452    case CXTUResourceUsage_Selectors:
5453      str = "ASTContext: selectors";
5454      break;
5455    case CXTUResourceUsage_GlobalCompletionResults:
5456      str = "Code completion: cached global results";
5457      break;
5458    case CXTUResourceUsage_SourceManagerContentCache:
5459      str = "SourceManager: content cache allocator";
5460      break;
5461    case CXTUResourceUsage_AST_SideTables:
5462      str = "ASTContext: side tables";
5463      break;
5464    case CXTUResourceUsage_SourceManager_Membuffer_Malloc:
5465      str = "SourceManager: malloc'ed memory buffers";
5466      break;
5467    case CXTUResourceUsage_SourceManager_Membuffer_MMap:
5468      str = "SourceManager: mmap'ed memory buffers";
5469      break;
5470    case CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc:
5471      str = "ExternalASTSource: malloc'ed memory buffers";
5472      break;
5473    case CXTUResourceUsage_ExternalASTSource_Membuffer_MMap:
5474      str = "ExternalASTSource: mmap'ed memory buffers";
5475      break;
5476    case CXTUResourceUsage_Preprocessor:
5477      str = "Preprocessor: malloc'ed memory";
5478      break;
5479    case CXTUResourceUsage_PreprocessingRecord:
5480      str = "Preprocessor: PreprocessingRecord";
5481      break;
5482    case CXTUResourceUsage_SourceManager_DataStructures:
5483      str = "SourceManager: data structures and tables";
5484      break;
5485    case CXTUResourceUsage_Preprocessor_HeaderSearch:
5486      str = "Preprocessor: header search tables";
5487      break;
5488  }
5489  return str;
5490}
5491
5492CXTUResourceUsage clang_getCXTUResourceUsage(CXTranslationUnit TU) {
5493  if (!TU) {
5494    CXTUResourceUsage usage = { (void*) 0, 0, 0 };
5495    return usage;
5496  }
5497
5498  ASTUnit *astUnit = static_cast<ASTUnit*>(TU->TUData);
5499  llvm::OwningPtr<MemUsageEntries> entries(new MemUsageEntries());
5500  ASTContext &astContext = astUnit->getASTContext();
5501
5502  // How much memory is used by AST nodes and types?
5503  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST,
5504    (unsigned long) astContext.getASTAllocatedMemory());
5505
5506  // How much memory is used by identifiers?
5507  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Identifiers,
5508    (unsigned long) astContext.Idents.getAllocator().getTotalMemory());
5509
5510  // How much memory is used for selectors?
5511  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Selectors,
5512    (unsigned long) astContext.Selectors.getTotalMemory());
5513
5514  // How much memory is used by ASTContext's side tables?
5515  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST_SideTables,
5516    (unsigned long) astContext.getSideTableAllocatedMemory());
5517
5518  // How much memory is used for caching global code completion results?
5519  unsigned long completionBytes = 0;
5520  if (GlobalCodeCompletionAllocator *completionAllocator =
5521      astUnit->getCachedCompletionAllocator().getPtr()) {
5522    completionBytes = completionAllocator->getTotalMemory();
5523  }
5524  createCXTUResourceUsageEntry(*entries,
5525                               CXTUResourceUsage_GlobalCompletionResults,
5526                               completionBytes);
5527
5528  // How much memory is being used by SourceManager's content cache?
5529  createCXTUResourceUsageEntry(*entries,
5530          CXTUResourceUsage_SourceManagerContentCache,
5531          (unsigned long) astContext.getSourceManager().getContentCacheSize());
5532
5533  // How much memory is being used by the MemoryBuffer's in SourceManager?
5534  const SourceManager::MemoryBufferSizes &srcBufs =
5535    astUnit->getSourceManager().getMemoryBufferSizes();
5536
5537  createCXTUResourceUsageEntry(*entries,
5538                               CXTUResourceUsage_SourceManager_Membuffer_Malloc,
5539                               (unsigned long) srcBufs.malloc_bytes);
5540  createCXTUResourceUsageEntry(*entries,
5541                               CXTUResourceUsage_SourceManager_Membuffer_MMap,
5542                               (unsigned long) srcBufs.mmap_bytes);
5543  createCXTUResourceUsageEntry(*entries,
5544                               CXTUResourceUsage_SourceManager_DataStructures,
5545                               (unsigned long) astContext.getSourceManager()
5546                                .getDataStructureSizes());
5547
5548  // How much memory is being used by the ExternalASTSource?
5549  if (ExternalASTSource *esrc = astContext.getExternalSource()) {
5550    const ExternalASTSource::MemoryBufferSizes &sizes =
5551      esrc->getMemoryBufferSizes();
5552
5553    createCXTUResourceUsageEntry(*entries,
5554      CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc,
5555                                 (unsigned long) sizes.malloc_bytes);
5556    createCXTUResourceUsageEntry(*entries,
5557      CXTUResourceUsage_ExternalASTSource_Membuffer_MMap,
5558                                 (unsigned long) sizes.mmap_bytes);
5559  }
5560
5561  // How much memory is being used by the Preprocessor?
5562  Preprocessor &pp = astUnit->getPreprocessor();
5563  createCXTUResourceUsageEntry(*entries,
5564                               CXTUResourceUsage_Preprocessor,
5565                               pp.getTotalMemory());
5566
5567  if (PreprocessingRecord *pRec = pp.getPreprocessingRecord()) {
5568    createCXTUResourceUsageEntry(*entries,
5569                                 CXTUResourceUsage_PreprocessingRecord,
5570                                 pRec->getTotalMemory());
5571  }
5572
5573  createCXTUResourceUsageEntry(*entries,
5574                               CXTUResourceUsage_Preprocessor_HeaderSearch,
5575                               pp.getHeaderSearchInfo().getTotalMemory());
5576
5577  CXTUResourceUsage usage = { (void*) entries.get(),
5578                            (unsigned) entries->size(),
5579                            entries->size() ? &(*entries)[0] : 0 };
5580  entries.take();
5581  return usage;
5582}
5583
5584void clang_disposeCXTUResourceUsage(CXTUResourceUsage usage) {
5585  if (usage.data)
5586    delete (MemUsageEntries*) usage.data;
5587}
5588
5589} // end extern "C"
5590
5591void clang::PrintLibclangResourceUsage(CXTranslationUnit TU) {
5592  CXTUResourceUsage Usage = clang_getCXTUResourceUsage(TU);
5593  for (unsigned I = 0; I != Usage.numEntries; ++I)
5594    fprintf(stderr, "  %s: %lu\n",
5595            clang_getTUResourceUsageName(Usage.entries[I].kind),
5596            Usage.entries[I].amount);
5597
5598  clang_disposeCXTUResourceUsage(Usage);
5599}
5600
5601//===----------------------------------------------------------------------===//
5602// Misc. utility functions.
5603//===----------------------------------------------------------------------===//
5604
5605/// Default to using an 8 MB stack size on "safety" threads.
5606static unsigned SafetyStackThreadSize = 8 << 20;
5607
5608namespace clang {
5609
5610bool RunSafely(llvm::CrashRecoveryContext &CRC,
5611               void (*Fn)(void*), void *UserData,
5612               unsigned Size) {
5613  if (!Size)
5614    Size = GetSafetyThreadStackSize();
5615  if (Size)
5616    return CRC.RunSafelyOnThread(Fn, UserData, Size);
5617  return CRC.RunSafely(Fn, UserData);
5618}
5619
5620unsigned GetSafetyThreadStackSize() {
5621  return SafetyStackThreadSize;
5622}
5623
5624void SetSafetyThreadStackSize(unsigned Value) {
5625  SafetyStackThreadSize = Value;
5626}
5627
5628}
5629
5630extern "C" {
5631
5632CXString clang_getClangVersion() {
5633  return createCXString(getClangFullVersion());
5634}
5635
5636} // end: extern "C"
5637
5638