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