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