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