CIndex.cpp revision 211924b563aa31421836cee7655be729ad02733f 
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->doesThisDeclarationHaveABody() && !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  unsigned Options = CXTranslationUnit_DetailedPreprocessingRecord |
2380                     CXTranslationUnit_NestedMacroInstantiations;
2381  return clang_parseTranslationUnit(CIdx, source_filename,
2382                                    command_line_args, num_command_line_args,
2383                                    unsaved_files, num_unsaved_files,
2384                                    Options);
2385}
2386
2387struct ParseTranslationUnitInfo {
2388  CXIndex CIdx;
2389  const char *source_filename;
2390  const char *const *command_line_args;
2391  int num_command_line_args;
2392  struct CXUnsavedFile *unsaved_files;
2393  unsigned num_unsaved_files;
2394  unsigned options;
2395  CXTranslationUnit result;
2396};
2397static void clang_parseTranslationUnit_Impl(void *UserData) {
2398  ParseTranslationUnitInfo *PTUI =
2399    static_cast<ParseTranslationUnitInfo*>(UserData);
2400  CXIndex CIdx = PTUI->CIdx;
2401  const char *source_filename = PTUI->source_filename;
2402  const char * const *command_line_args = PTUI->command_line_args;
2403  int num_command_line_args = PTUI->num_command_line_args;
2404  struct CXUnsavedFile *unsaved_files = PTUI->unsaved_files;
2405  unsigned num_unsaved_files = PTUI->num_unsaved_files;
2406  unsigned options = PTUI->options;
2407  PTUI->result = 0;
2408
2409  if (!CIdx)
2410    return;
2411
2412  CIndexer *CXXIdx = static_cast<CIndexer *>(CIdx);
2413
2414  bool PrecompilePreamble = options & CXTranslationUnit_PrecompiledPreamble;
2415  bool CompleteTranslationUnit
2416    = ((options & CXTranslationUnit_Incomplete) == 0);
2417  bool CacheCodeCompetionResults
2418    = options & CXTranslationUnit_CacheCompletionResults;
2419  bool CXXPrecompilePreamble
2420    = options & CXTranslationUnit_CXXPrecompiledPreamble;
2421  bool CXXChainedPCH
2422    = options & CXTranslationUnit_CXXChainedPCH;
2423
2424  // Configure the diagnostics.
2425  DiagnosticOptions DiagOpts;
2426  llvm::IntrusiveRefCntPtr<Diagnostic>
2427    Diags(CompilerInstance::createDiagnostics(DiagOpts, num_command_line_args,
2428                                                command_line_args));
2429
2430  // Recover resources if we crash before exiting this function.
2431  llvm::CrashRecoveryContextCleanupRegistrar<Diagnostic,
2432    llvm::CrashRecoveryContextReleaseRefCleanup<Diagnostic> >
2433    DiagCleanup(Diags.getPtr());
2434
2435  llvm::OwningPtr<std::vector<ASTUnit::RemappedFile> >
2436    RemappedFiles(new std::vector<ASTUnit::RemappedFile>());
2437
2438  // Recover resources if we crash before exiting this function.
2439  llvm::CrashRecoveryContextCleanupRegistrar<
2440    std::vector<ASTUnit::RemappedFile> > RemappedCleanup(RemappedFiles.get());
2441
2442  for (unsigned I = 0; I != num_unsaved_files; ++I) {
2443    llvm::StringRef Data(unsaved_files[I].Contents, unsaved_files[I].Length);
2444    const llvm::MemoryBuffer *Buffer
2445      = llvm::MemoryBuffer::getMemBufferCopy(Data, unsaved_files[I].Filename);
2446    RemappedFiles->push_back(std::make_pair(unsaved_files[I].Filename,
2447                                            Buffer));
2448  }
2449
2450  llvm::OwningPtr<std::vector<const char *> >
2451    Args(new std::vector<const char*>());
2452
2453  // Recover resources if we crash before exiting this method.
2454  llvm::CrashRecoveryContextCleanupRegistrar<std::vector<const char*> >
2455    ArgsCleanup(Args.get());
2456
2457  // Since the Clang C library is primarily used by batch tools dealing with
2458  // (often very broken) source code, where spell-checking can have a
2459  // significant negative impact on performance (particularly when
2460  // precompiled headers are involved), we disable it by default.
2461  // Only do this if we haven't found a spell-checking-related argument.
2462  bool FoundSpellCheckingArgument = false;
2463  for (int I = 0; I != num_command_line_args; ++I) {
2464    if (strcmp(command_line_args[I], "-fno-spell-checking") == 0 ||
2465        strcmp(command_line_args[I], "-fspell-checking") == 0) {
2466      FoundSpellCheckingArgument = true;
2467      break;
2468    }
2469  }
2470  if (!FoundSpellCheckingArgument)
2471    Args->push_back("-fno-spell-checking");
2472
2473  Args->insert(Args->end(), command_line_args,
2474               command_line_args + num_command_line_args);
2475
2476  // The 'source_filename' argument is optional.  If the caller does not
2477  // specify it then it is assumed that the source file is specified
2478  // in the actual argument list.
2479  // Put the source file after command_line_args otherwise if '-x' flag is
2480  // present it will be unused.
2481  if (source_filename)
2482    Args->push_back(source_filename);
2483
2484  // Do we need the detailed preprocessing record?
2485  bool NestedMacroInstantiations = false;
2486  if (options & CXTranslationUnit_DetailedPreprocessingRecord) {
2487    Args->push_back("-Xclang");
2488    Args->push_back("-detailed-preprocessing-record");
2489    NestedMacroInstantiations
2490      = (options & CXTranslationUnit_NestedMacroInstantiations);
2491  }
2492
2493  unsigned NumErrors = Diags->getClient()->getNumErrors();
2494  llvm::OwningPtr<ASTUnit> Unit(
2495    ASTUnit::LoadFromCommandLine(Args->size() ? &(*Args)[0] : 0
2496                                 /* vector::data() not portable */,
2497                                 Args->size() ? (&(*Args)[0] + Args->size()) :0,
2498                                 Diags,
2499                                 CXXIdx->getClangResourcesPath(),
2500                                 CXXIdx->getOnlyLocalDecls(),
2501                                 /*CaptureDiagnostics=*/true,
2502                                 RemappedFiles->size() ? &(*RemappedFiles)[0]:0,
2503                                 RemappedFiles->size(),
2504                                 /*RemappedFilesKeepOriginalName=*/true,
2505                                 PrecompilePreamble,
2506                                 CompleteTranslationUnit,
2507                                 CacheCodeCompetionResults,
2508                                 CXXPrecompilePreamble,
2509                                 CXXChainedPCH,
2510                                 NestedMacroInstantiations));
2511
2512  if (NumErrors != Diags->getClient()->getNumErrors()) {
2513    // Make sure to check that 'Unit' is non-NULL.
2514    if (CXXIdx->getDisplayDiagnostics() && Unit.get()) {
2515      for (ASTUnit::stored_diag_iterator D = Unit->stored_diag_begin(),
2516                                      DEnd = Unit->stored_diag_end();
2517           D != DEnd; ++D) {
2518        CXStoredDiagnostic Diag(*D, Unit->getASTContext().getLangOptions());
2519        CXString Msg = clang_formatDiagnostic(&Diag,
2520                                    clang_defaultDiagnosticDisplayOptions());
2521        fprintf(stderr, "%s\n", clang_getCString(Msg));
2522        clang_disposeString(Msg);
2523      }
2524#ifdef LLVM_ON_WIN32
2525      // On Windows, force a flush, since there may be multiple copies of
2526      // stderr and stdout in the file system, all with different buffers
2527      // but writing to the same device.
2528      fflush(stderr);
2529#endif
2530    }
2531  }
2532
2533  PTUI->result = MakeCXTranslationUnit(Unit.take());
2534}
2535CXTranslationUnit clang_parseTranslationUnit(CXIndex CIdx,
2536                                             const char *source_filename,
2537                                         const char * const *command_line_args,
2538                                             int num_command_line_args,
2539                                            struct CXUnsavedFile *unsaved_files,
2540                                             unsigned num_unsaved_files,
2541                                             unsigned options) {
2542  ParseTranslationUnitInfo PTUI = { CIdx, source_filename, command_line_args,
2543                                    num_command_line_args, unsaved_files,
2544                                    num_unsaved_files, options, 0 };
2545  llvm::CrashRecoveryContext CRC;
2546
2547  if (!RunSafely(CRC, clang_parseTranslationUnit_Impl, &PTUI)) {
2548    fprintf(stderr, "libclang: crash detected during parsing: {\n");
2549    fprintf(stderr, "  'source_filename' : '%s'\n", source_filename);
2550    fprintf(stderr, "  'command_line_args' : [");
2551    for (int i = 0; i != num_command_line_args; ++i) {
2552      if (i)
2553        fprintf(stderr, ", ");
2554      fprintf(stderr, "'%s'", command_line_args[i]);
2555    }
2556    fprintf(stderr, "],\n");
2557    fprintf(stderr, "  'unsaved_files' : [");
2558    for (unsigned i = 0; i != num_unsaved_files; ++i) {
2559      if (i)
2560        fprintf(stderr, ", ");
2561      fprintf(stderr, "('%s', '...', %ld)", unsaved_files[i].Filename,
2562              unsaved_files[i].Length);
2563    }
2564    fprintf(stderr, "],\n");
2565    fprintf(stderr, "  'options' : %d,\n", options);
2566    fprintf(stderr, "}\n");
2567
2568    return 0;
2569  } else if (getenv("LIBCLANG_RESOURCE_USAGE")) {
2570    PrintLibclangResourceUsage(PTUI.result);
2571  }
2572
2573  return PTUI.result;
2574}
2575
2576unsigned clang_defaultSaveOptions(CXTranslationUnit TU) {
2577  return CXSaveTranslationUnit_None;
2578}
2579
2580int clang_saveTranslationUnit(CXTranslationUnit TU, const char *FileName,
2581                              unsigned options) {
2582  if (!TU)
2583    return 1;
2584
2585  int result = static_cast<ASTUnit *>(TU->TUData)->Save(FileName);
2586  if (getenv("LIBCLANG_RESOURCE_USAGE"))
2587    PrintLibclangResourceUsage(TU);
2588  return result;
2589}
2590
2591void clang_disposeTranslationUnit(CXTranslationUnit CTUnit) {
2592  if (CTUnit) {
2593    // If the translation unit has been marked as unsafe to free, just discard
2594    // it.
2595    if (static_cast<ASTUnit *>(CTUnit->TUData)->isUnsafeToFree())
2596      return;
2597
2598    delete static_cast<ASTUnit *>(CTUnit->TUData);
2599    disposeCXStringPool(CTUnit->StringPool);
2600    delete CTUnit;
2601  }
2602}
2603
2604unsigned clang_defaultReparseOptions(CXTranslationUnit TU) {
2605  return CXReparse_None;
2606}
2607
2608struct ReparseTranslationUnitInfo {
2609  CXTranslationUnit TU;
2610  unsigned num_unsaved_files;
2611  struct CXUnsavedFile *unsaved_files;
2612  unsigned options;
2613  int result;
2614};
2615
2616static void clang_reparseTranslationUnit_Impl(void *UserData) {
2617  ReparseTranslationUnitInfo *RTUI =
2618    static_cast<ReparseTranslationUnitInfo*>(UserData);
2619  CXTranslationUnit TU = RTUI->TU;
2620  unsigned num_unsaved_files = RTUI->num_unsaved_files;
2621  struct CXUnsavedFile *unsaved_files = RTUI->unsaved_files;
2622  unsigned options = RTUI->options;
2623  (void) options;
2624  RTUI->result = 1;
2625
2626  if (!TU)
2627    return;
2628
2629  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
2630  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
2631
2632  llvm::OwningPtr<std::vector<ASTUnit::RemappedFile> >
2633    RemappedFiles(new std::vector<ASTUnit::RemappedFile>());
2634
2635  // Recover resources if we crash before exiting this function.
2636  llvm::CrashRecoveryContextCleanupRegistrar<
2637    std::vector<ASTUnit::RemappedFile> > RemappedCleanup(RemappedFiles.get());
2638
2639  for (unsigned I = 0; I != num_unsaved_files; ++I) {
2640    llvm::StringRef Data(unsaved_files[I].Contents, unsaved_files[I].Length);
2641    const llvm::MemoryBuffer *Buffer
2642      = llvm::MemoryBuffer::getMemBufferCopy(Data, unsaved_files[I].Filename);
2643    RemappedFiles->push_back(std::make_pair(unsaved_files[I].Filename,
2644                                            Buffer));
2645  }
2646
2647  if (!CXXUnit->Reparse(RemappedFiles->size() ? &(*RemappedFiles)[0] : 0,
2648                        RemappedFiles->size()))
2649    RTUI->result = 0;
2650}
2651
2652int clang_reparseTranslationUnit(CXTranslationUnit TU,
2653                                 unsigned num_unsaved_files,
2654                                 struct CXUnsavedFile *unsaved_files,
2655                                 unsigned options) {
2656  ReparseTranslationUnitInfo RTUI = { TU, num_unsaved_files, unsaved_files,
2657                                      options, 0 };
2658  llvm::CrashRecoveryContext CRC;
2659
2660  if (!RunSafely(CRC, clang_reparseTranslationUnit_Impl, &RTUI)) {
2661    fprintf(stderr, "libclang: crash detected during reparsing\n");
2662    static_cast<ASTUnit *>(TU->TUData)->setUnsafeToFree(true);
2663    return 1;
2664  } else if (getenv("LIBCLANG_RESOURCE_USAGE"))
2665    PrintLibclangResourceUsage(TU);
2666
2667  return RTUI.result;
2668}
2669
2670
2671CXString clang_getTranslationUnitSpelling(CXTranslationUnit CTUnit) {
2672  if (!CTUnit)
2673    return createCXString("");
2674
2675  ASTUnit *CXXUnit = static_cast<ASTUnit *>(CTUnit->TUData);
2676  return createCXString(CXXUnit->getOriginalSourceFileName(), true);
2677}
2678
2679CXCursor clang_getTranslationUnitCursor(CXTranslationUnit TU) {
2680  CXCursor Result = { CXCursor_TranslationUnit, { 0, 0, TU } };
2681  return Result;
2682}
2683
2684} // end: extern "C"
2685
2686//===----------------------------------------------------------------------===//
2687// CXSourceLocation and CXSourceRange Operations.
2688//===----------------------------------------------------------------------===//
2689
2690extern "C" {
2691CXSourceLocation clang_getNullLocation() {
2692  CXSourceLocation Result = { { 0, 0 }, 0 };
2693  return Result;
2694}
2695
2696unsigned clang_equalLocations(CXSourceLocation loc1, CXSourceLocation loc2) {
2697  return (loc1.ptr_data[0] == loc2.ptr_data[0] &&
2698          loc1.ptr_data[1] == loc2.ptr_data[1] &&
2699          loc1.int_data == loc2.int_data);
2700}
2701
2702CXSourceLocation clang_getLocation(CXTranslationUnit tu,
2703                                   CXFile file,
2704                                   unsigned line,
2705                                   unsigned column) {
2706  if (!tu || !file)
2707    return clang_getNullLocation();
2708
2709  bool Logging = ::getenv("LIBCLANG_LOGGING");
2710  ASTUnit *CXXUnit = static_cast<ASTUnit *>(tu->TUData);
2711  const FileEntry *File = static_cast<const FileEntry *>(file);
2712  SourceLocation SLoc
2713    = CXXUnit->getSourceManager().getLocation(File, line, column);
2714  if (SLoc.isInvalid()) {
2715    if (Logging)
2716      llvm::errs() << "clang_getLocation(\"" << File->getName()
2717                   << "\", " << line << ", " << column << ") = invalid\n";
2718    return clang_getNullLocation();
2719  }
2720
2721  if (Logging)
2722    llvm::errs() << "clang_getLocation(\"" << File->getName()
2723                 << "\", " << line << ", " << column << ") = "
2724                 << SLoc.getRawEncoding() << "\n";
2725
2726  return cxloc::translateSourceLocation(CXXUnit->getASTContext(), SLoc);
2727}
2728
2729CXSourceLocation clang_getLocationForOffset(CXTranslationUnit tu,
2730                                            CXFile file,
2731                                            unsigned offset) {
2732  if (!tu || !file)
2733    return clang_getNullLocation();
2734
2735  ASTUnit *CXXUnit = static_cast<ASTUnit *>(tu->TUData);
2736  SourceLocation Start
2737    = CXXUnit->getSourceManager().getLocation(
2738                                        static_cast<const FileEntry *>(file),
2739                                              1, 1);
2740  if (Start.isInvalid()) return clang_getNullLocation();
2741
2742  SourceLocation SLoc = Start.getFileLocWithOffset(offset);
2743
2744  if (SLoc.isInvalid()) return clang_getNullLocation();
2745
2746  return cxloc::translateSourceLocation(CXXUnit->getASTContext(), SLoc);
2747}
2748
2749CXSourceRange clang_getNullRange() {
2750  CXSourceRange Result = { { 0, 0 }, 0, 0 };
2751  return Result;
2752}
2753
2754CXSourceRange clang_getRange(CXSourceLocation begin, CXSourceLocation end) {
2755  if (begin.ptr_data[0] != end.ptr_data[0] ||
2756      begin.ptr_data[1] != end.ptr_data[1])
2757    return clang_getNullRange();
2758
2759  CXSourceRange Result = { { begin.ptr_data[0], begin.ptr_data[1] },
2760                           begin.int_data, end.int_data };
2761  return Result;
2762}
2763} // end: extern "C"
2764
2765static void createNullLocation(CXFile *file, unsigned *line,
2766                               unsigned *column, unsigned *offset) {
2767  if (file)
2768   *file = 0;
2769  if (line)
2770   *line = 0;
2771  if (column)
2772   *column = 0;
2773  if (offset)
2774   *offset = 0;
2775  return;
2776}
2777
2778extern "C" {
2779void clang_getInstantiationLocation(CXSourceLocation location,
2780                                    CXFile *file,
2781                                    unsigned *line,
2782                                    unsigned *column,
2783                                    unsigned *offset) {
2784  SourceLocation Loc = SourceLocation::getFromRawEncoding(location.int_data);
2785
2786  if (!location.ptr_data[0] || Loc.isInvalid()) {
2787    createNullLocation(file, line, column, offset);
2788    return;
2789  }
2790
2791  const SourceManager &SM =
2792    *static_cast<const SourceManager*>(location.ptr_data[0]);
2793  SourceLocation InstLoc = SM.getInstantiationLoc(Loc);
2794
2795  // Check that the FileID is invalid on the instantiation location.
2796  // This can manifest in invalid code.
2797  FileID fileID = SM.getFileID(InstLoc);
2798  bool Invalid = false;
2799  const SrcMgr::SLocEntry &sloc = SM.getSLocEntry(fileID, &Invalid);
2800  if (!sloc.isFile() || Invalid) {
2801    createNullLocation(file, line, column, offset);
2802    return;
2803  }
2804
2805  if (file)
2806    *file = (void *)SM.getFileEntryForSLocEntry(sloc);
2807  if (line)
2808    *line = SM.getInstantiationLineNumber(InstLoc);
2809  if (column)
2810    *column = SM.getInstantiationColumnNumber(InstLoc);
2811  if (offset)
2812    *offset = SM.getDecomposedLoc(InstLoc).second;
2813}
2814
2815void clang_getSpellingLocation(CXSourceLocation location,
2816                               CXFile *file,
2817                               unsigned *line,
2818                               unsigned *column,
2819                               unsigned *offset) {
2820  SourceLocation Loc = SourceLocation::getFromRawEncoding(location.int_data);
2821
2822  if (!location.ptr_data[0] || Loc.isInvalid()) {
2823    if (file)
2824      *file = 0;
2825    if (line)
2826      *line = 0;
2827    if (column)
2828      *column = 0;
2829    if (offset)
2830      *offset = 0;
2831    return;
2832  }
2833
2834  const SourceManager &SM =
2835    *static_cast<const SourceManager*>(location.ptr_data[0]);
2836  SourceLocation SpellLoc = Loc;
2837  if (SpellLoc.isMacroID()) {
2838    SourceLocation SimpleSpellingLoc = SM.getImmediateSpellingLoc(SpellLoc);
2839    if (SimpleSpellingLoc.isFileID() &&
2840        SM.getFileEntryForID(SM.getDecomposedLoc(SimpleSpellingLoc).first))
2841      SpellLoc = SimpleSpellingLoc;
2842    else
2843      SpellLoc = SM.getInstantiationLoc(SpellLoc);
2844  }
2845
2846  std::pair<FileID, unsigned> LocInfo = SM.getDecomposedLoc(SpellLoc);
2847  FileID FID = LocInfo.first;
2848  unsigned FileOffset = LocInfo.second;
2849
2850  if (file)
2851    *file = (void *)SM.getFileEntryForID(FID);
2852  if (line)
2853    *line = SM.getLineNumber(FID, FileOffset);
2854  if (column)
2855    *column = SM.getColumnNumber(FID, FileOffset);
2856  if (offset)
2857    *offset = FileOffset;
2858}
2859
2860CXSourceLocation clang_getRangeStart(CXSourceRange range) {
2861  CXSourceLocation Result = { { range.ptr_data[0], range.ptr_data[1] },
2862                              range.begin_int_data };
2863  return Result;
2864}
2865
2866CXSourceLocation clang_getRangeEnd(CXSourceRange range) {
2867  CXSourceLocation Result = { { range.ptr_data[0], range.ptr_data[1] },
2868                              range.end_int_data };
2869  return Result;
2870}
2871
2872} // end: extern "C"
2873
2874//===----------------------------------------------------------------------===//
2875// CXFile Operations.
2876//===----------------------------------------------------------------------===//
2877
2878extern "C" {
2879CXString clang_getFileName(CXFile SFile) {
2880  if (!SFile)
2881    return createCXString((const char*)NULL);
2882
2883  FileEntry *FEnt = static_cast<FileEntry *>(SFile);
2884  return createCXString(FEnt->getName());
2885}
2886
2887time_t clang_getFileTime(CXFile SFile) {
2888  if (!SFile)
2889    return 0;
2890
2891  FileEntry *FEnt = static_cast<FileEntry *>(SFile);
2892  return FEnt->getModificationTime();
2893}
2894
2895CXFile clang_getFile(CXTranslationUnit tu, const char *file_name) {
2896  if (!tu)
2897    return 0;
2898
2899  ASTUnit *CXXUnit = static_cast<ASTUnit *>(tu->TUData);
2900
2901  FileManager &FMgr = CXXUnit->getFileManager();
2902  return const_cast<FileEntry *>(FMgr.getFile(file_name));
2903}
2904
2905unsigned clang_isFileMultipleIncludeGuarded(CXTranslationUnit tu, CXFile file) {
2906  if (!tu || !file)
2907    return 0;
2908
2909  ASTUnit *CXXUnit = static_cast<ASTUnit *>(tu->TUData);
2910  FileEntry *FEnt = static_cast<FileEntry *>(file);
2911  return CXXUnit->getPreprocessor().getHeaderSearchInfo()
2912                                          .isFileMultipleIncludeGuarded(FEnt);
2913}
2914
2915} // end: extern "C"
2916
2917//===----------------------------------------------------------------------===//
2918// CXCursor Operations.
2919//===----------------------------------------------------------------------===//
2920
2921static Decl *getDeclFromExpr(Stmt *E) {
2922  if (CastExpr *CE = dyn_cast<CastExpr>(E))
2923    return getDeclFromExpr(CE->getSubExpr());
2924
2925  if (DeclRefExpr *RefExpr = dyn_cast<DeclRefExpr>(E))
2926    return RefExpr->getDecl();
2927  if (BlockDeclRefExpr *RefExpr = dyn_cast<BlockDeclRefExpr>(E))
2928    return RefExpr->getDecl();
2929  if (MemberExpr *ME = dyn_cast<MemberExpr>(E))
2930    return ME->getMemberDecl();
2931  if (ObjCIvarRefExpr *RE = dyn_cast<ObjCIvarRefExpr>(E))
2932    return RE->getDecl();
2933  if (ObjCPropertyRefExpr *PRE = dyn_cast<ObjCPropertyRefExpr>(E))
2934    return PRE->isExplicitProperty() ? PRE->getExplicitProperty() : 0;
2935
2936  if (CallExpr *CE = dyn_cast<CallExpr>(E))
2937    return getDeclFromExpr(CE->getCallee());
2938  if (CXXConstructExpr *CE = llvm::dyn_cast<CXXConstructExpr>(E))
2939    if (!CE->isElidable())
2940    return CE->getConstructor();
2941  if (ObjCMessageExpr *OME = dyn_cast<ObjCMessageExpr>(E))
2942    return OME->getMethodDecl();
2943
2944  if (ObjCProtocolExpr *PE = dyn_cast<ObjCProtocolExpr>(E))
2945    return PE->getProtocol();
2946  if (SubstNonTypeTemplateParmPackExpr *NTTP
2947                              = dyn_cast<SubstNonTypeTemplateParmPackExpr>(E))
2948    return NTTP->getParameterPack();
2949  if (SizeOfPackExpr *SizeOfPack = dyn_cast<SizeOfPackExpr>(E))
2950    if (isa<NonTypeTemplateParmDecl>(SizeOfPack->getPack()) ||
2951        isa<ParmVarDecl>(SizeOfPack->getPack()))
2952      return SizeOfPack->getPack();
2953
2954  return 0;
2955}
2956
2957static SourceLocation getLocationFromExpr(Expr *E) {
2958  if (ObjCMessageExpr *Msg = dyn_cast<ObjCMessageExpr>(E))
2959    return /*FIXME:*/Msg->getLeftLoc();
2960  if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
2961    return DRE->getLocation();
2962  if (BlockDeclRefExpr *RefExpr = dyn_cast<BlockDeclRefExpr>(E))
2963    return RefExpr->getLocation();
2964  if (MemberExpr *Member = dyn_cast<MemberExpr>(E))
2965    return Member->getMemberLoc();
2966  if (ObjCIvarRefExpr *Ivar = dyn_cast<ObjCIvarRefExpr>(E))
2967    return Ivar->getLocation();
2968  if (SizeOfPackExpr *SizeOfPack = dyn_cast<SizeOfPackExpr>(E))
2969    return SizeOfPack->getPackLoc();
2970
2971  return E->getLocStart();
2972}
2973
2974extern "C" {
2975
2976unsigned clang_visitChildren(CXCursor parent,
2977                             CXCursorVisitor visitor,
2978                             CXClientData client_data) {
2979  CursorVisitor CursorVis(getCursorTU(parent), visitor, client_data,
2980                          getCursorASTUnit(parent)->getMaxPCHLevel(),
2981                          false);
2982  return CursorVis.VisitChildren(parent);
2983}
2984
2985#ifndef __has_feature
2986#define __has_feature(x) 0
2987#endif
2988#if __has_feature(blocks)
2989typedef enum CXChildVisitResult
2990     (^CXCursorVisitorBlock)(CXCursor cursor, CXCursor parent);
2991
2992static enum CXChildVisitResult visitWithBlock(CXCursor cursor, CXCursor parent,
2993    CXClientData client_data) {
2994  CXCursorVisitorBlock block = (CXCursorVisitorBlock)client_data;
2995  return block(cursor, parent);
2996}
2997#else
2998// If we are compiled with a compiler that doesn't have native blocks support,
2999// define and call the block manually, so the
3000typedef struct _CXChildVisitResult
3001{
3002	void *isa;
3003	int flags;
3004	int reserved;
3005	enum CXChildVisitResult(*invoke)(struct _CXChildVisitResult*, CXCursor,
3006                                         CXCursor);
3007} *CXCursorVisitorBlock;
3008
3009static enum CXChildVisitResult visitWithBlock(CXCursor cursor, CXCursor parent,
3010    CXClientData client_data) {
3011  CXCursorVisitorBlock block = (CXCursorVisitorBlock)client_data;
3012  return block->invoke(block, cursor, parent);
3013}
3014#endif
3015
3016
3017unsigned clang_visitChildrenWithBlock(CXCursor parent,
3018                                      CXCursorVisitorBlock block) {
3019  return clang_visitChildren(parent, visitWithBlock, block);
3020}
3021
3022static CXString getDeclSpelling(Decl *D) {
3023  NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D);
3024  if (!ND) {
3025    if (ObjCPropertyImplDecl *PropImpl =llvm::dyn_cast<ObjCPropertyImplDecl>(D))
3026      if (ObjCPropertyDecl *Property = PropImpl->getPropertyDecl())
3027        return createCXString(Property->getIdentifier()->getName());
3028
3029    return createCXString("");
3030  }
3031
3032  if (ObjCMethodDecl *OMD = dyn_cast<ObjCMethodDecl>(ND))
3033    return createCXString(OMD->getSelector().getAsString());
3034
3035  if (ObjCCategoryImplDecl *CIMP = dyn_cast<ObjCCategoryImplDecl>(ND))
3036    // No, this isn't the same as the code below. getIdentifier() is non-virtual
3037    // and returns different names. NamedDecl returns the class name and
3038    // ObjCCategoryImplDecl returns the category name.
3039    return createCXString(CIMP->getIdentifier()->getNameStart());
3040
3041  if (isa<UsingDirectiveDecl>(D))
3042    return createCXString("");
3043
3044  llvm::SmallString<1024> S;
3045  llvm::raw_svector_ostream os(S);
3046  ND->printName(os);
3047
3048  return createCXString(os.str());
3049}
3050
3051CXString clang_getCursorSpelling(CXCursor C) {
3052  if (clang_isTranslationUnit(C.kind))
3053    return clang_getTranslationUnitSpelling(
3054                            static_cast<CXTranslationUnit>(C.data[2]));
3055
3056  if (clang_isReference(C.kind)) {
3057    switch (C.kind) {
3058    case CXCursor_ObjCSuperClassRef: {
3059      ObjCInterfaceDecl *Super = getCursorObjCSuperClassRef(C).first;
3060      return createCXString(Super->getIdentifier()->getNameStart());
3061    }
3062    case CXCursor_ObjCClassRef: {
3063      ObjCInterfaceDecl *Class = getCursorObjCClassRef(C).first;
3064      return createCXString(Class->getIdentifier()->getNameStart());
3065    }
3066    case CXCursor_ObjCProtocolRef: {
3067      ObjCProtocolDecl *OID = getCursorObjCProtocolRef(C).first;
3068      assert(OID && "getCursorSpelling(): Missing protocol decl");
3069      return createCXString(OID->getIdentifier()->getNameStart());
3070    }
3071    case CXCursor_CXXBaseSpecifier: {
3072      CXXBaseSpecifier *B = getCursorCXXBaseSpecifier(C);
3073      return createCXString(B->getType().getAsString());
3074    }
3075    case CXCursor_TypeRef: {
3076      TypeDecl *Type = getCursorTypeRef(C).first;
3077      assert(Type && "Missing type decl");
3078
3079      return createCXString(getCursorContext(C).getTypeDeclType(Type).
3080                              getAsString());
3081    }
3082    case CXCursor_TemplateRef: {
3083      TemplateDecl *Template = getCursorTemplateRef(C).first;
3084      assert(Template && "Missing template decl");
3085
3086      return createCXString(Template->getNameAsString());
3087    }
3088
3089    case CXCursor_NamespaceRef: {
3090      NamedDecl *NS = getCursorNamespaceRef(C).first;
3091      assert(NS && "Missing namespace decl");
3092
3093      return createCXString(NS->getNameAsString());
3094    }
3095
3096    case CXCursor_MemberRef: {
3097      FieldDecl *Field = getCursorMemberRef(C).first;
3098      assert(Field && "Missing member decl");
3099
3100      return createCXString(Field->getNameAsString());
3101    }
3102
3103    case CXCursor_LabelRef: {
3104      LabelStmt *Label = getCursorLabelRef(C).first;
3105      assert(Label && "Missing label");
3106
3107      return createCXString(Label->getName());
3108    }
3109
3110    case CXCursor_OverloadedDeclRef: {
3111      OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
3112      if (Decl *D = Storage.dyn_cast<Decl *>()) {
3113        if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
3114          return createCXString(ND->getNameAsString());
3115        return createCXString("");
3116      }
3117      if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
3118        return createCXString(E->getName().getAsString());
3119      OverloadedTemplateStorage *Ovl
3120        = Storage.get<OverloadedTemplateStorage*>();
3121      if (Ovl->size() == 0)
3122        return createCXString("");
3123      return createCXString((*Ovl->begin())->getNameAsString());
3124    }
3125
3126    default:
3127      return createCXString("<not implemented>");
3128    }
3129  }
3130
3131  if (clang_isExpression(C.kind)) {
3132    Decl *D = getDeclFromExpr(getCursorExpr(C));
3133    if (D)
3134      return getDeclSpelling(D);
3135    return createCXString("");
3136  }
3137
3138  if (clang_isStatement(C.kind)) {
3139    Stmt *S = getCursorStmt(C);
3140    if (LabelStmt *Label = dyn_cast_or_null<LabelStmt>(S))
3141      return createCXString(Label->getName());
3142
3143    return createCXString("");
3144  }
3145
3146  if (C.kind == CXCursor_MacroInstantiation)
3147    return createCXString(getCursorMacroInstantiation(C)->getName()
3148                                                           ->getNameStart());
3149
3150  if (C.kind == CXCursor_MacroDefinition)
3151    return createCXString(getCursorMacroDefinition(C)->getName()
3152                                                           ->getNameStart());
3153
3154  if (C.kind == CXCursor_InclusionDirective)
3155    return createCXString(getCursorInclusionDirective(C)->getFileName());
3156
3157  if (clang_isDeclaration(C.kind))
3158    return getDeclSpelling(getCursorDecl(C));
3159
3160  return createCXString("");
3161}
3162
3163CXString clang_getCursorDisplayName(CXCursor C) {
3164  if (!clang_isDeclaration(C.kind))
3165    return clang_getCursorSpelling(C);
3166
3167  Decl *D = getCursorDecl(C);
3168  if (!D)
3169    return createCXString("");
3170
3171  PrintingPolicy &Policy = getCursorContext(C).PrintingPolicy;
3172  if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D))
3173    D = FunTmpl->getTemplatedDecl();
3174
3175  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
3176    llvm::SmallString<64> Str;
3177    llvm::raw_svector_ostream OS(Str);
3178    OS << Function->getNameAsString();
3179    if (Function->getPrimaryTemplate())
3180      OS << "<>";
3181    OS << "(";
3182    for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I) {
3183      if (I)
3184        OS << ", ";
3185      OS << Function->getParamDecl(I)->getType().getAsString(Policy);
3186    }
3187
3188    if (Function->isVariadic()) {
3189      if (Function->getNumParams())
3190        OS << ", ";
3191      OS << "...";
3192    }
3193    OS << ")";
3194    return createCXString(OS.str());
3195  }
3196
3197  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(D)) {
3198    llvm::SmallString<64> Str;
3199    llvm::raw_svector_ostream OS(Str);
3200    OS << ClassTemplate->getNameAsString();
3201    OS << "<";
3202    TemplateParameterList *Params = ClassTemplate->getTemplateParameters();
3203    for (unsigned I = 0, N = Params->size(); I != N; ++I) {
3204      if (I)
3205        OS << ", ";
3206
3207      NamedDecl *Param = Params->getParam(I);
3208      if (Param->getIdentifier()) {
3209        OS << Param->getIdentifier()->getName();
3210        continue;
3211      }
3212
3213      // There is no parameter name, which makes this tricky. Try to come up
3214      // with something useful that isn't too long.
3215      if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
3216        OS << (TTP->wasDeclaredWithTypename()? "typename" : "class");
3217      else if (NonTypeTemplateParmDecl *NTTP
3218                                    = dyn_cast<NonTypeTemplateParmDecl>(Param))
3219        OS << NTTP->getType().getAsString(Policy);
3220      else
3221        OS << "template<...> class";
3222    }
3223
3224    OS << ">";
3225    return createCXString(OS.str());
3226  }
3227
3228  if (ClassTemplateSpecializationDecl *ClassSpec
3229                              = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
3230    // If the type was explicitly written, use that.
3231    if (TypeSourceInfo *TSInfo = ClassSpec->getTypeAsWritten())
3232      return createCXString(TSInfo->getType().getAsString(Policy));
3233
3234    llvm::SmallString<64> Str;
3235    llvm::raw_svector_ostream OS(Str);
3236    OS << ClassSpec->getNameAsString();
3237    OS << TemplateSpecializationType::PrintTemplateArgumentList(
3238                                      ClassSpec->getTemplateArgs().data(),
3239                                      ClassSpec->getTemplateArgs().size(),
3240                                                                Policy);
3241    return createCXString(OS.str());
3242  }
3243
3244  return clang_getCursorSpelling(C);
3245}
3246
3247CXString clang_getCursorKindSpelling(enum CXCursorKind Kind) {
3248  switch (Kind) {
3249  case CXCursor_FunctionDecl:
3250      return createCXString("FunctionDecl");
3251  case CXCursor_TypedefDecl:
3252      return createCXString("TypedefDecl");
3253  case CXCursor_EnumDecl:
3254      return createCXString("EnumDecl");
3255  case CXCursor_EnumConstantDecl:
3256      return createCXString("EnumConstantDecl");
3257  case CXCursor_StructDecl:
3258      return createCXString("StructDecl");
3259  case CXCursor_UnionDecl:
3260      return createCXString("UnionDecl");
3261  case CXCursor_ClassDecl:
3262      return createCXString("ClassDecl");
3263  case CXCursor_FieldDecl:
3264      return createCXString("FieldDecl");
3265  case CXCursor_VarDecl:
3266      return createCXString("VarDecl");
3267  case CXCursor_ParmDecl:
3268      return createCXString("ParmDecl");
3269  case CXCursor_ObjCInterfaceDecl:
3270      return createCXString("ObjCInterfaceDecl");
3271  case CXCursor_ObjCCategoryDecl:
3272      return createCXString("ObjCCategoryDecl");
3273  case CXCursor_ObjCProtocolDecl:
3274      return createCXString("ObjCProtocolDecl");
3275  case CXCursor_ObjCPropertyDecl:
3276      return createCXString("ObjCPropertyDecl");
3277  case CXCursor_ObjCIvarDecl:
3278      return createCXString("ObjCIvarDecl");
3279  case CXCursor_ObjCInstanceMethodDecl:
3280      return createCXString("ObjCInstanceMethodDecl");
3281  case CXCursor_ObjCClassMethodDecl:
3282      return createCXString("ObjCClassMethodDecl");
3283  case CXCursor_ObjCImplementationDecl:
3284      return createCXString("ObjCImplementationDecl");
3285  case CXCursor_ObjCCategoryImplDecl:
3286      return createCXString("ObjCCategoryImplDecl");
3287  case CXCursor_CXXMethod:
3288      return createCXString("CXXMethod");
3289  case CXCursor_UnexposedDecl:
3290      return createCXString("UnexposedDecl");
3291  case CXCursor_ObjCSuperClassRef:
3292      return createCXString("ObjCSuperClassRef");
3293  case CXCursor_ObjCProtocolRef:
3294      return createCXString("ObjCProtocolRef");
3295  case CXCursor_ObjCClassRef:
3296      return createCXString("ObjCClassRef");
3297  case CXCursor_TypeRef:
3298      return createCXString("TypeRef");
3299  case CXCursor_TemplateRef:
3300      return createCXString("TemplateRef");
3301  case CXCursor_NamespaceRef:
3302    return createCXString("NamespaceRef");
3303  case CXCursor_MemberRef:
3304    return createCXString("MemberRef");
3305  case CXCursor_LabelRef:
3306    return createCXString("LabelRef");
3307  case CXCursor_OverloadedDeclRef:
3308    return createCXString("OverloadedDeclRef");
3309  case CXCursor_UnexposedExpr:
3310      return createCXString("UnexposedExpr");
3311  case CXCursor_BlockExpr:
3312      return createCXString("BlockExpr");
3313  case CXCursor_DeclRefExpr:
3314      return createCXString("DeclRefExpr");
3315  case CXCursor_MemberRefExpr:
3316      return createCXString("MemberRefExpr");
3317  case CXCursor_CallExpr:
3318      return createCXString("CallExpr");
3319  case CXCursor_ObjCMessageExpr:
3320      return createCXString("ObjCMessageExpr");
3321  case CXCursor_UnexposedStmt:
3322      return createCXString("UnexposedStmt");
3323  case CXCursor_LabelStmt:
3324      return createCXString("LabelStmt");
3325  case CXCursor_InvalidFile:
3326      return createCXString("InvalidFile");
3327  case CXCursor_InvalidCode:
3328    return createCXString("InvalidCode");
3329  case CXCursor_NoDeclFound:
3330      return createCXString("NoDeclFound");
3331  case CXCursor_NotImplemented:
3332      return createCXString("NotImplemented");
3333  case CXCursor_TranslationUnit:
3334      return createCXString("TranslationUnit");
3335  case CXCursor_UnexposedAttr:
3336      return createCXString("UnexposedAttr");
3337  case CXCursor_IBActionAttr:
3338      return createCXString("attribute(ibaction)");
3339  case CXCursor_IBOutletAttr:
3340     return createCXString("attribute(iboutlet)");
3341  case CXCursor_IBOutletCollectionAttr:
3342      return createCXString("attribute(iboutletcollection)");
3343  case CXCursor_PreprocessingDirective:
3344    return createCXString("preprocessing directive");
3345  case CXCursor_MacroDefinition:
3346    return createCXString("macro definition");
3347  case CXCursor_MacroInstantiation:
3348    return createCXString("macro instantiation");
3349  case CXCursor_InclusionDirective:
3350    return createCXString("inclusion directive");
3351  case CXCursor_Namespace:
3352    return createCXString("Namespace");
3353  case CXCursor_LinkageSpec:
3354    return createCXString("LinkageSpec");
3355  case CXCursor_CXXBaseSpecifier:
3356    return createCXString("C++ base class specifier");
3357  case CXCursor_Constructor:
3358    return createCXString("CXXConstructor");
3359  case CXCursor_Destructor:
3360    return createCXString("CXXDestructor");
3361  case CXCursor_ConversionFunction:
3362    return createCXString("CXXConversion");
3363  case CXCursor_TemplateTypeParameter:
3364    return createCXString("TemplateTypeParameter");
3365  case CXCursor_NonTypeTemplateParameter:
3366    return createCXString("NonTypeTemplateParameter");
3367  case CXCursor_TemplateTemplateParameter:
3368    return createCXString("TemplateTemplateParameter");
3369  case CXCursor_FunctionTemplate:
3370    return createCXString("FunctionTemplate");
3371  case CXCursor_ClassTemplate:
3372    return createCXString("ClassTemplate");
3373  case CXCursor_ClassTemplatePartialSpecialization:
3374    return createCXString("ClassTemplatePartialSpecialization");
3375  case CXCursor_NamespaceAlias:
3376    return createCXString("NamespaceAlias");
3377  case CXCursor_UsingDirective:
3378    return createCXString("UsingDirective");
3379  case CXCursor_UsingDeclaration:
3380    return createCXString("UsingDeclaration");
3381  case CXCursor_TypeAliasDecl:
3382      return createCXString("TypeAliasDecl");
3383  }
3384
3385  llvm_unreachable("Unhandled CXCursorKind");
3386  return createCXString((const char*) 0);
3387}
3388
3389enum CXChildVisitResult GetCursorVisitor(CXCursor cursor,
3390                                         CXCursor parent,
3391                                         CXClientData client_data) {
3392  CXCursor *BestCursor = static_cast<CXCursor *>(client_data);
3393
3394  // If our current best cursor is the construction of a temporary object,
3395  // don't replace that cursor with a type reference, because we want
3396  // clang_getCursor() to point at the constructor.
3397  if (clang_isExpression(BestCursor->kind) &&
3398      isa<CXXTemporaryObjectExpr>(getCursorExpr(*BestCursor)) &&
3399      cursor.kind == CXCursor_TypeRef)
3400    return CXChildVisit_Recurse;
3401
3402  // Don't override a preprocessing cursor with another preprocessing
3403  // cursor; we want the outermost preprocessing cursor.
3404  if (clang_isPreprocessing(cursor.kind) &&
3405      clang_isPreprocessing(BestCursor->kind))
3406    return CXChildVisit_Recurse;
3407
3408  *BestCursor = cursor;
3409  return CXChildVisit_Recurse;
3410}
3411
3412CXCursor clang_getCursor(CXTranslationUnit TU, CXSourceLocation Loc) {
3413  if (!TU)
3414    return clang_getNullCursor();
3415
3416  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
3417  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
3418
3419  // Translate the given source location to make it point at the beginning of
3420  // the token under the cursor.
3421  SourceLocation SLoc = cxloc::translateSourceLocation(Loc);
3422
3423  // Guard against an invalid SourceLocation, or we may assert in one
3424  // of the following calls.
3425  if (SLoc.isInvalid())
3426    return clang_getNullCursor();
3427
3428  bool Logging = getenv("LIBCLANG_LOGGING");
3429  SLoc = Lexer::GetBeginningOfToken(SLoc, CXXUnit->getSourceManager(),
3430                                    CXXUnit->getASTContext().getLangOptions());
3431
3432  CXCursor Result = MakeCXCursorInvalid(CXCursor_NoDeclFound);
3433  if (SLoc.isValid()) {
3434    // FIXME: Would be great to have a "hint" cursor, then walk from that
3435    // hint cursor upward until we find a cursor whose source range encloses
3436    // the region of interest, rather than starting from the translation unit.
3437    CXCursor Parent = clang_getTranslationUnitCursor(TU);
3438    CursorVisitor CursorVis(TU, GetCursorVisitor, &Result,
3439                            Decl::MaxPCHLevel, true, SourceLocation(SLoc));
3440    CursorVis.VisitChildren(Parent);
3441  }
3442
3443  if (Logging) {
3444    CXFile SearchFile;
3445    unsigned SearchLine, SearchColumn;
3446    CXFile ResultFile;
3447    unsigned ResultLine, ResultColumn;
3448    CXString SearchFileName, ResultFileName, KindSpelling, USR;
3449    const char *IsDef = clang_isCursorDefinition(Result)? " (Definition)" : "";
3450    CXSourceLocation ResultLoc = clang_getCursorLocation(Result);
3451
3452    clang_getInstantiationLocation(Loc, &SearchFile, &SearchLine, &SearchColumn,
3453                                   0);
3454    clang_getInstantiationLocation(ResultLoc, &ResultFile, &ResultLine,
3455                                   &ResultColumn, 0);
3456    SearchFileName = clang_getFileName(SearchFile);
3457    ResultFileName = clang_getFileName(ResultFile);
3458    KindSpelling = clang_getCursorKindSpelling(Result.kind);
3459    USR = clang_getCursorUSR(Result);
3460    fprintf(stderr, "clang_getCursor(%s:%d:%d) = %s(%s:%d:%d):%s%s\n",
3461            clang_getCString(SearchFileName), SearchLine, SearchColumn,
3462            clang_getCString(KindSpelling),
3463            clang_getCString(ResultFileName), ResultLine, ResultColumn,
3464            clang_getCString(USR), IsDef);
3465    clang_disposeString(SearchFileName);
3466    clang_disposeString(ResultFileName);
3467    clang_disposeString(KindSpelling);
3468    clang_disposeString(USR);
3469
3470    CXCursor Definition = clang_getCursorDefinition(Result);
3471    if (!clang_equalCursors(Definition, clang_getNullCursor())) {
3472      CXSourceLocation DefinitionLoc = clang_getCursorLocation(Definition);
3473      CXString DefinitionKindSpelling
3474                                = clang_getCursorKindSpelling(Definition.kind);
3475      CXFile DefinitionFile;
3476      unsigned DefinitionLine, DefinitionColumn;
3477      clang_getInstantiationLocation(DefinitionLoc, &DefinitionFile,
3478                                     &DefinitionLine, &DefinitionColumn, 0);
3479      CXString DefinitionFileName = clang_getFileName(DefinitionFile);
3480      fprintf(stderr, "  -> %s(%s:%d:%d)\n",
3481              clang_getCString(DefinitionKindSpelling),
3482              clang_getCString(DefinitionFileName),
3483              DefinitionLine, DefinitionColumn);
3484      clang_disposeString(DefinitionFileName);
3485      clang_disposeString(DefinitionKindSpelling);
3486    }
3487  }
3488
3489  return Result;
3490}
3491
3492CXCursor clang_getNullCursor(void) {
3493  return MakeCXCursorInvalid(CXCursor_InvalidFile);
3494}
3495
3496unsigned clang_equalCursors(CXCursor X, CXCursor Y) {
3497  return X == Y;
3498}
3499
3500unsigned clang_hashCursor(CXCursor C) {
3501  unsigned Index = 0;
3502  if (clang_isExpression(C.kind) || clang_isStatement(C.kind))
3503    Index = 1;
3504
3505  return llvm::DenseMapInfo<std::pair<unsigned, void*> >::getHashValue(
3506                                        std::make_pair(C.kind, C.data[Index]));
3507}
3508
3509unsigned clang_isInvalid(enum CXCursorKind K) {
3510  return K >= CXCursor_FirstInvalid && K <= CXCursor_LastInvalid;
3511}
3512
3513unsigned clang_isDeclaration(enum CXCursorKind K) {
3514  return K >= CXCursor_FirstDecl && K <= CXCursor_LastDecl;
3515}
3516
3517unsigned clang_isReference(enum CXCursorKind K) {
3518  return K >= CXCursor_FirstRef && K <= CXCursor_LastRef;
3519}
3520
3521unsigned clang_isExpression(enum CXCursorKind K) {
3522  return K >= CXCursor_FirstExpr && K <= CXCursor_LastExpr;
3523}
3524
3525unsigned clang_isStatement(enum CXCursorKind K) {
3526  return K >= CXCursor_FirstStmt && K <= CXCursor_LastStmt;
3527}
3528
3529unsigned clang_isTranslationUnit(enum CXCursorKind K) {
3530  return K == CXCursor_TranslationUnit;
3531}
3532
3533unsigned clang_isPreprocessing(enum CXCursorKind K) {
3534  return K >= CXCursor_FirstPreprocessing && K <= CXCursor_LastPreprocessing;
3535}
3536
3537unsigned clang_isUnexposed(enum CXCursorKind K) {
3538  switch (K) {
3539    case CXCursor_UnexposedDecl:
3540    case CXCursor_UnexposedExpr:
3541    case CXCursor_UnexposedStmt:
3542    case CXCursor_UnexposedAttr:
3543      return true;
3544    default:
3545      return false;
3546  }
3547}
3548
3549CXCursorKind clang_getCursorKind(CXCursor C) {
3550  return C.kind;
3551}
3552
3553CXSourceLocation clang_getCursorLocation(CXCursor C) {
3554  if (clang_isReference(C.kind)) {
3555    switch (C.kind) {
3556    case CXCursor_ObjCSuperClassRef: {
3557      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3558        = getCursorObjCSuperClassRef(C);
3559      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3560    }
3561
3562    case CXCursor_ObjCProtocolRef: {
3563      std::pair<ObjCProtocolDecl *, SourceLocation> P
3564        = getCursorObjCProtocolRef(C);
3565      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3566    }
3567
3568    case CXCursor_ObjCClassRef: {
3569      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3570        = getCursorObjCClassRef(C);
3571      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3572    }
3573
3574    case CXCursor_TypeRef: {
3575      std::pair<TypeDecl *, SourceLocation> P = getCursorTypeRef(C);
3576      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3577    }
3578
3579    case CXCursor_TemplateRef: {
3580      std::pair<TemplateDecl *, SourceLocation> P = getCursorTemplateRef(C);
3581      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3582    }
3583
3584    case CXCursor_NamespaceRef: {
3585      std::pair<NamedDecl *, SourceLocation> P = getCursorNamespaceRef(C);
3586      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3587    }
3588
3589    case CXCursor_MemberRef: {
3590      std::pair<FieldDecl *, SourceLocation> P = getCursorMemberRef(C);
3591      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3592    }
3593
3594    case CXCursor_CXXBaseSpecifier: {
3595      CXXBaseSpecifier *BaseSpec = getCursorCXXBaseSpecifier(C);
3596      if (!BaseSpec)
3597        return clang_getNullLocation();
3598
3599      if (TypeSourceInfo *TSInfo = BaseSpec->getTypeSourceInfo())
3600        return cxloc::translateSourceLocation(getCursorContext(C),
3601                                            TSInfo->getTypeLoc().getBeginLoc());
3602
3603      return cxloc::translateSourceLocation(getCursorContext(C),
3604                                        BaseSpec->getSourceRange().getBegin());
3605    }
3606
3607    case CXCursor_LabelRef: {
3608      std::pair<LabelStmt *, SourceLocation> P = getCursorLabelRef(C);
3609      return cxloc::translateSourceLocation(getCursorContext(C), P.second);
3610    }
3611
3612    case CXCursor_OverloadedDeclRef:
3613      return cxloc::translateSourceLocation(getCursorContext(C),
3614                                          getCursorOverloadedDeclRef(C).second);
3615
3616    default:
3617      // FIXME: Need a way to enumerate all non-reference cases.
3618      llvm_unreachable("Missed a reference kind");
3619    }
3620  }
3621
3622  if (clang_isExpression(C.kind))
3623    return cxloc::translateSourceLocation(getCursorContext(C),
3624                                   getLocationFromExpr(getCursorExpr(C)));
3625
3626  if (clang_isStatement(C.kind))
3627    return cxloc::translateSourceLocation(getCursorContext(C),
3628                                          getCursorStmt(C)->getLocStart());
3629
3630  if (C.kind == CXCursor_PreprocessingDirective) {
3631    SourceLocation L = cxcursor::getCursorPreprocessingDirective(C).getBegin();
3632    return cxloc::translateSourceLocation(getCursorContext(C), L);
3633  }
3634
3635  if (C.kind == CXCursor_MacroInstantiation) {
3636    SourceLocation L
3637      = cxcursor::getCursorMacroInstantiation(C)->getSourceRange().getBegin();
3638    return cxloc::translateSourceLocation(getCursorContext(C), L);
3639  }
3640
3641  if (C.kind == CXCursor_MacroDefinition) {
3642    SourceLocation L = cxcursor::getCursorMacroDefinition(C)->getLocation();
3643    return cxloc::translateSourceLocation(getCursorContext(C), L);
3644  }
3645
3646  if (C.kind == CXCursor_InclusionDirective) {
3647    SourceLocation L
3648      = cxcursor::getCursorInclusionDirective(C)->getSourceRange().getBegin();
3649    return cxloc::translateSourceLocation(getCursorContext(C), L);
3650  }
3651
3652  if (C.kind < CXCursor_FirstDecl || C.kind > CXCursor_LastDecl)
3653    return clang_getNullLocation();
3654
3655  Decl *D = getCursorDecl(C);
3656  SourceLocation Loc = D->getLocation();
3657  if (ObjCInterfaceDecl *Class = dyn_cast<ObjCInterfaceDecl>(D))
3658    Loc = Class->getClassLoc();
3659  // FIXME: Multiple variables declared in a single declaration
3660  // currently lack the information needed to correctly determine their
3661  // ranges when accounting for the type-specifier.  We use context
3662  // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3663  // and if so, whether it is the first decl.
3664  if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3665    if (!cxcursor::isFirstInDeclGroup(C))
3666      Loc = VD->getLocation();
3667  }
3668
3669  return cxloc::translateSourceLocation(getCursorContext(C), Loc);
3670}
3671
3672} // end extern "C"
3673
3674static SourceRange getRawCursorExtent(CXCursor C) {
3675  if (clang_isReference(C.kind)) {
3676    switch (C.kind) {
3677    case CXCursor_ObjCSuperClassRef:
3678      return  getCursorObjCSuperClassRef(C).second;
3679
3680    case CXCursor_ObjCProtocolRef:
3681      return getCursorObjCProtocolRef(C).second;
3682
3683    case CXCursor_ObjCClassRef:
3684      return getCursorObjCClassRef(C).second;
3685
3686    case CXCursor_TypeRef:
3687      return getCursorTypeRef(C).second;
3688
3689    case CXCursor_TemplateRef:
3690      return getCursorTemplateRef(C).second;
3691
3692    case CXCursor_NamespaceRef:
3693      return getCursorNamespaceRef(C).second;
3694
3695    case CXCursor_MemberRef:
3696      return getCursorMemberRef(C).second;
3697
3698    case CXCursor_CXXBaseSpecifier:
3699      return getCursorCXXBaseSpecifier(C)->getSourceRange();
3700
3701    case CXCursor_LabelRef:
3702      return getCursorLabelRef(C).second;
3703
3704    case CXCursor_OverloadedDeclRef:
3705      return getCursorOverloadedDeclRef(C).second;
3706
3707    default:
3708      // FIXME: Need a way to enumerate all non-reference cases.
3709      llvm_unreachable("Missed a reference kind");
3710    }
3711  }
3712
3713  if (clang_isExpression(C.kind))
3714    return getCursorExpr(C)->getSourceRange();
3715
3716  if (clang_isStatement(C.kind))
3717    return getCursorStmt(C)->getSourceRange();
3718
3719  if (C.kind == CXCursor_PreprocessingDirective)
3720    return cxcursor::getCursorPreprocessingDirective(C);
3721
3722  if (C.kind == CXCursor_MacroInstantiation)
3723    return cxcursor::getCursorMacroInstantiation(C)->getSourceRange();
3724
3725  if (C.kind == CXCursor_MacroDefinition)
3726    return cxcursor::getCursorMacroDefinition(C)->getSourceRange();
3727
3728  if (C.kind == CXCursor_InclusionDirective)
3729    return cxcursor::getCursorInclusionDirective(C)->getSourceRange();
3730
3731  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3732    Decl *D = cxcursor::getCursorDecl(C);
3733    SourceRange R = D->getSourceRange();
3734    // FIXME: Multiple variables declared in a single declaration
3735    // currently lack the information needed to correctly determine their
3736    // ranges when accounting for the type-specifier.  We use context
3737    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3738    // and if so, whether it is the first decl.
3739    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3740      if (!cxcursor::isFirstInDeclGroup(C))
3741        R.setBegin(VD->getLocation());
3742    }
3743    return R;
3744  }
3745  return SourceRange();
3746}
3747
3748/// \brief Retrieves the "raw" cursor extent, which is then extended to include
3749/// the decl-specifier-seq for declarations.
3750static SourceRange getFullCursorExtent(CXCursor C, SourceManager &SrcMgr) {
3751  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3752    Decl *D = cxcursor::getCursorDecl(C);
3753    SourceRange R = D->getSourceRange();
3754
3755    // Adjust the start of the location for declarations preceded by
3756    // declaration specifiers.
3757    SourceLocation StartLoc;
3758    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
3759      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
3760        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3761    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
3762      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
3763        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3764    }
3765
3766    if (StartLoc.isValid() && R.getBegin().isValid() &&
3767        SrcMgr.isBeforeInTranslationUnit(StartLoc, R.getBegin()))
3768      R.setBegin(StartLoc);
3769
3770    // FIXME: Multiple variables declared in a single declaration
3771    // currently lack the information needed to correctly determine their
3772    // ranges when accounting for the type-specifier.  We use context
3773    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3774    // and if so, whether it is the first decl.
3775    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3776      if (!cxcursor::isFirstInDeclGroup(C))
3777        R.setBegin(VD->getLocation());
3778    }
3779
3780    return R;
3781  }
3782
3783  return getRawCursorExtent(C);
3784}
3785
3786extern "C" {
3787
3788CXSourceRange clang_getCursorExtent(CXCursor C) {
3789  SourceRange R = getRawCursorExtent(C);
3790  if (R.isInvalid())
3791    return clang_getNullRange();
3792
3793  return cxloc::translateSourceRange(getCursorContext(C), R);
3794}
3795
3796CXCursor clang_getCursorReferenced(CXCursor C) {
3797  if (clang_isInvalid(C.kind))
3798    return clang_getNullCursor();
3799
3800  CXTranslationUnit tu = getCursorTU(C);
3801  if (clang_isDeclaration(C.kind)) {
3802    Decl *D = getCursorDecl(C);
3803    if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
3804      return MakeCursorOverloadedDeclRef(Using, D->getLocation(), tu);
3805    if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
3806      return MakeCursorOverloadedDeclRef(Classes, D->getLocation(), tu);
3807    if (ObjCForwardProtocolDecl *Protocols
3808                                        = dyn_cast<ObjCForwardProtocolDecl>(D))
3809      return MakeCursorOverloadedDeclRef(Protocols, D->getLocation(), tu);
3810    if (ObjCPropertyImplDecl *PropImpl =llvm::dyn_cast<ObjCPropertyImplDecl>(D))
3811      if (ObjCPropertyDecl *Property = PropImpl->getPropertyDecl())
3812        return MakeCXCursor(Property, tu);
3813
3814    return C;
3815  }
3816
3817  if (clang_isExpression(C.kind)) {
3818    Expr *E = getCursorExpr(C);
3819    Decl *D = getDeclFromExpr(E);
3820    if (D)
3821      return MakeCXCursor(D, tu);
3822
3823    if (OverloadExpr *Ovl = dyn_cast_or_null<OverloadExpr>(E))
3824      return MakeCursorOverloadedDeclRef(Ovl, tu);
3825
3826    return clang_getNullCursor();
3827  }
3828
3829  if (clang_isStatement(C.kind)) {
3830    Stmt *S = getCursorStmt(C);
3831    if (GotoStmt *Goto = dyn_cast_or_null<GotoStmt>(S))
3832      if (LabelDecl *label = Goto->getLabel())
3833        if (LabelStmt *labelS = label->getStmt())
3834        return MakeCXCursor(labelS, getCursorDecl(C), tu);
3835
3836    return clang_getNullCursor();
3837  }
3838
3839  if (C.kind == CXCursor_MacroInstantiation) {
3840    if (MacroDefinition *Def = getCursorMacroInstantiation(C)->getDefinition())
3841      return MakeMacroDefinitionCursor(Def, tu);
3842  }
3843
3844  if (!clang_isReference(C.kind))
3845    return clang_getNullCursor();
3846
3847  switch (C.kind) {
3848    case CXCursor_ObjCSuperClassRef:
3849      return MakeCXCursor(getCursorObjCSuperClassRef(C).first, tu);
3850
3851    case CXCursor_ObjCProtocolRef: {
3852      return MakeCXCursor(getCursorObjCProtocolRef(C).first, tu);
3853
3854    case CXCursor_ObjCClassRef:
3855      return MakeCXCursor(getCursorObjCClassRef(C).first, tu );
3856
3857    case CXCursor_TypeRef:
3858      return MakeCXCursor(getCursorTypeRef(C).first, tu );
3859
3860    case CXCursor_TemplateRef:
3861      return MakeCXCursor(getCursorTemplateRef(C).first, tu );
3862
3863    case CXCursor_NamespaceRef:
3864      return MakeCXCursor(getCursorNamespaceRef(C).first, tu );
3865
3866    case CXCursor_MemberRef:
3867      return MakeCXCursor(getCursorMemberRef(C).first, tu );
3868
3869    case CXCursor_CXXBaseSpecifier: {
3870      CXXBaseSpecifier *B = cxcursor::getCursorCXXBaseSpecifier(C);
3871      return clang_getTypeDeclaration(cxtype::MakeCXType(B->getType(),
3872                                                         tu ));
3873    }
3874
3875    case CXCursor_LabelRef:
3876      // FIXME: We end up faking the "parent" declaration here because we
3877      // don't want to make CXCursor larger.
3878      return MakeCXCursor(getCursorLabelRef(C).first,
3879               static_cast<ASTUnit*>(tu->TUData)->getASTContext()
3880                          .getTranslationUnitDecl(),
3881                          tu);
3882
3883    case CXCursor_OverloadedDeclRef:
3884      return C;
3885
3886    default:
3887      // We would prefer to enumerate all non-reference cursor kinds here.
3888      llvm_unreachable("Unhandled reference cursor kind");
3889      break;
3890    }
3891  }
3892
3893  return clang_getNullCursor();
3894}
3895
3896CXCursor clang_getCursorDefinition(CXCursor C) {
3897  if (clang_isInvalid(C.kind))
3898    return clang_getNullCursor();
3899
3900  CXTranslationUnit TU = getCursorTU(C);
3901
3902  bool WasReference = false;
3903  if (clang_isReference(C.kind) || clang_isExpression(C.kind)) {
3904    C = clang_getCursorReferenced(C);
3905    WasReference = true;
3906  }
3907
3908  if (C.kind == CXCursor_MacroInstantiation)
3909    return clang_getCursorReferenced(C);
3910
3911  if (!clang_isDeclaration(C.kind))
3912    return clang_getNullCursor();
3913
3914  Decl *D = getCursorDecl(C);
3915  if (!D)
3916    return clang_getNullCursor();
3917
3918  switch (D->getKind()) {
3919  // Declaration kinds that don't really separate the notions of
3920  // declaration and definition.
3921  case Decl::Namespace:
3922  case Decl::Typedef:
3923  case Decl::TypeAlias:
3924  case Decl::TypeAliasTemplate:
3925  case Decl::TemplateTypeParm:
3926  case Decl::EnumConstant:
3927  case Decl::Field:
3928  case Decl::IndirectField:
3929  case Decl::ObjCIvar:
3930  case Decl::ObjCAtDefsField:
3931  case Decl::ImplicitParam:
3932  case Decl::ParmVar:
3933  case Decl::NonTypeTemplateParm:
3934  case Decl::TemplateTemplateParm:
3935  case Decl::ObjCCategoryImpl:
3936  case Decl::ObjCImplementation:
3937  case Decl::AccessSpec:
3938  case Decl::LinkageSpec:
3939  case Decl::ObjCPropertyImpl:
3940  case Decl::FileScopeAsm:
3941  case Decl::StaticAssert:
3942  case Decl::Block:
3943  case Decl::Label:  // FIXME: Is this right??
3944    return C;
3945
3946  // Declaration kinds that don't make any sense here, but are
3947  // nonetheless harmless.
3948  case Decl::TranslationUnit:
3949    break;
3950
3951  // Declaration kinds for which the definition is not resolvable.
3952  case Decl::UnresolvedUsingTypename:
3953  case Decl::UnresolvedUsingValue:
3954    break;
3955
3956  case Decl::UsingDirective:
3957    return MakeCXCursor(cast<UsingDirectiveDecl>(D)->getNominatedNamespace(),
3958                        TU);
3959
3960  case Decl::NamespaceAlias:
3961    return MakeCXCursor(cast<NamespaceAliasDecl>(D)->getNamespace(), TU);
3962
3963  case Decl::Enum:
3964  case Decl::Record:
3965  case Decl::CXXRecord:
3966  case Decl::ClassTemplateSpecialization:
3967  case Decl::ClassTemplatePartialSpecialization:
3968    if (TagDecl *Def = cast<TagDecl>(D)->getDefinition())
3969      return MakeCXCursor(Def, TU);
3970    return clang_getNullCursor();
3971
3972  case Decl::Function:
3973  case Decl::CXXMethod:
3974  case Decl::CXXConstructor:
3975  case Decl::CXXDestructor:
3976  case Decl::CXXConversion: {
3977    const FunctionDecl *Def = 0;
3978    if (cast<FunctionDecl>(D)->getBody(Def))
3979      return MakeCXCursor(const_cast<FunctionDecl *>(Def), TU);
3980    return clang_getNullCursor();
3981  }
3982
3983  case Decl::Var: {
3984    // Ask the variable if it has a definition.
3985    if (VarDecl *Def = cast<VarDecl>(D)->getDefinition())
3986      return MakeCXCursor(Def, TU);
3987    return clang_getNullCursor();
3988  }
3989
3990  case Decl::FunctionTemplate: {
3991    const FunctionDecl *Def = 0;
3992    if (cast<FunctionTemplateDecl>(D)->getTemplatedDecl()->getBody(Def))
3993      return MakeCXCursor(Def->getDescribedFunctionTemplate(), TU);
3994    return clang_getNullCursor();
3995  }
3996
3997  case Decl::ClassTemplate: {
3998    if (RecordDecl *Def = cast<ClassTemplateDecl>(D)->getTemplatedDecl()
3999                                                            ->getDefinition())
4000      return MakeCXCursor(cast<CXXRecordDecl>(Def)->getDescribedClassTemplate(),
4001                          TU);
4002    return clang_getNullCursor();
4003  }
4004
4005  case Decl::Using:
4006    return MakeCursorOverloadedDeclRef(cast<UsingDecl>(D),
4007                                       D->getLocation(), TU);
4008
4009  case Decl::UsingShadow:
4010    return clang_getCursorDefinition(
4011                       MakeCXCursor(cast<UsingShadowDecl>(D)->getTargetDecl(),
4012                                    TU));
4013
4014  case Decl::ObjCMethod: {
4015    ObjCMethodDecl *Method = cast<ObjCMethodDecl>(D);
4016    if (Method->isThisDeclarationADefinition())
4017      return C;
4018
4019    // Dig out the method definition in the associated
4020    // @implementation, if we have it.
4021    // FIXME: The ASTs should make finding the definition easier.
4022    if (ObjCInterfaceDecl *Class
4023                       = dyn_cast<ObjCInterfaceDecl>(Method->getDeclContext()))
4024      if (ObjCImplementationDecl *ClassImpl = Class->getImplementation())
4025        if (ObjCMethodDecl *Def = ClassImpl->getMethod(Method->getSelector(),
4026                                                  Method->isInstanceMethod()))
4027          if (Def->isThisDeclarationADefinition())
4028            return MakeCXCursor(Def, TU);
4029
4030    return clang_getNullCursor();
4031  }
4032
4033  case Decl::ObjCCategory:
4034    if (ObjCCategoryImplDecl *Impl
4035                               = cast<ObjCCategoryDecl>(D)->getImplementation())
4036      return MakeCXCursor(Impl, TU);
4037    return clang_getNullCursor();
4038
4039  case Decl::ObjCProtocol:
4040    if (!cast<ObjCProtocolDecl>(D)->isForwardDecl())
4041      return C;
4042    return clang_getNullCursor();
4043
4044  case Decl::ObjCInterface:
4045    // There are two notions of a "definition" for an Objective-C
4046    // class: the interface and its implementation. When we resolved a
4047    // reference to an Objective-C class, produce the @interface as
4048    // the definition; when we were provided with the interface,
4049    // produce the @implementation as the definition.
4050    if (WasReference) {
4051      if (!cast<ObjCInterfaceDecl>(D)->isForwardDecl())
4052        return C;
4053    } else if (ObjCImplementationDecl *Impl
4054                              = cast<ObjCInterfaceDecl>(D)->getImplementation())
4055      return MakeCXCursor(Impl, TU);
4056    return clang_getNullCursor();
4057
4058  case Decl::ObjCProperty:
4059    // FIXME: We don't really know where to find the
4060    // ObjCPropertyImplDecls that implement this property.
4061    return clang_getNullCursor();
4062
4063  case Decl::ObjCCompatibleAlias:
4064    if (ObjCInterfaceDecl *Class
4065          = cast<ObjCCompatibleAliasDecl>(D)->getClassInterface())
4066      if (!Class->isForwardDecl())
4067        return MakeCXCursor(Class, TU);
4068
4069    return clang_getNullCursor();
4070
4071  case Decl::ObjCForwardProtocol:
4072    return MakeCursorOverloadedDeclRef(cast<ObjCForwardProtocolDecl>(D),
4073                                       D->getLocation(), TU);
4074
4075  case Decl::ObjCClass:
4076    return MakeCursorOverloadedDeclRef(cast<ObjCClassDecl>(D), D->getLocation(),
4077                                       TU);
4078
4079  case Decl::Friend:
4080    if (NamedDecl *Friend = cast<FriendDecl>(D)->getFriendDecl())
4081      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4082    return clang_getNullCursor();
4083
4084  case Decl::FriendTemplate:
4085    if (NamedDecl *Friend = cast<FriendTemplateDecl>(D)->getFriendDecl())
4086      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4087    return clang_getNullCursor();
4088  }
4089
4090  return clang_getNullCursor();
4091}
4092
4093unsigned clang_isCursorDefinition(CXCursor C) {
4094  if (!clang_isDeclaration(C.kind))
4095    return 0;
4096
4097  return clang_getCursorDefinition(C) == C;
4098}
4099
4100CXCursor clang_getCanonicalCursor(CXCursor C) {
4101  if (!clang_isDeclaration(C.kind))
4102    return C;
4103
4104  if (Decl *D = getCursorDecl(C))
4105    return MakeCXCursor(D->getCanonicalDecl(), getCursorTU(C));
4106
4107  return C;
4108}
4109
4110unsigned clang_getNumOverloadedDecls(CXCursor C) {
4111  if (C.kind != CXCursor_OverloadedDeclRef)
4112    return 0;
4113
4114  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
4115  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4116    return E->getNumDecls();
4117
4118  if (OverloadedTemplateStorage *S
4119                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4120    return S->size();
4121
4122  Decl *D = Storage.get<Decl*>();
4123  if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
4124    return Using->shadow_size();
4125  if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
4126    return Classes->size();
4127  if (ObjCForwardProtocolDecl *Protocols =dyn_cast<ObjCForwardProtocolDecl>(D))
4128    return Protocols->protocol_size();
4129
4130  return 0;
4131}
4132
4133CXCursor clang_getOverloadedDecl(CXCursor cursor, unsigned index) {
4134  if (cursor.kind != CXCursor_OverloadedDeclRef)
4135    return clang_getNullCursor();
4136
4137  if (index >= clang_getNumOverloadedDecls(cursor))
4138    return clang_getNullCursor();
4139
4140  CXTranslationUnit TU = getCursorTU(cursor);
4141  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(cursor).first;
4142  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4143    return MakeCXCursor(E->decls_begin()[index], TU);
4144
4145  if (OverloadedTemplateStorage *S
4146                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4147    return MakeCXCursor(S->begin()[index], TU);
4148
4149  Decl *D = Storage.get<Decl*>();
4150  if (UsingDecl *Using = dyn_cast<UsingDecl>(D)) {
4151    // FIXME: This is, unfortunately, linear time.
4152    UsingDecl::shadow_iterator Pos = Using->shadow_begin();
4153    std::advance(Pos, index);
4154    return MakeCXCursor(cast<UsingShadowDecl>(*Pos)->getTargetDecl(), TU);
4155  }
4156
4157  if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
4158    return MakeCXCursor(Classes->begin()[index].getInterface(), TU);
4159
4160  if (ObjCForwardProtocolDecl *Protocols = dyn_cast<ObjCForwardProtocolDecl>(D))
4161    return MakeCXCursor(Protocols->protocol_begin()[index], TU);
4162
4163  return clang_getNullCursor();
4164}
4165
4166void clang_getDefinitionSpellingAndExtent(CXCursor C,
4167                                          const char **startBuf,
4168                                          const char **endBuf,
4169                                          unsigned *startLine,
4170                                          unsigned *startColumn,
4171                                          unsigned *endLine,
4172                                          unsigned *endColumn) {
4173  assert(getCursorDecl(C) && "CXCursor has null decl");
4174  NamedDecl *ND = static_cast<NamedDecl *>(getCursorDecl(C));
4175  FunctionDecl *FD = dyn_cast<FunctionDecl>(ND);
4176  CompoundStmt *Body = dyn_cast<CompoundStmt>(FD->getBody());
4177
4178  SourceManager &SM = FD->getASTContext().getSourceManager();
4179  *startBuf = SM.getCharacterData(Body->getLBracLoc());
4180  *endBuf = SM.getCharacterData(Body->getRBracLoc());
4181  *startLine = SM.getSpellingLineNumber(Body->getLBracLoc());
4182  *startColumn = SM.getSpellingColumnNumber(Body->getLBracLoc());
4183  *endLine = SM.getSpellingLineNumber(Body->getRBracLoc());
4184  *endColumn = SM.getSpellingColumnNumber(Body->getRBracLoc());
4185}
4186
4187void clang_enableStackTraces(void) {
4188  llvm::sys::PrintStackTraceOnErrorSignal();
4189}
4190
4191void clang_executeOnThread(void (*fn)(void*), void *user_data,
4192                           unsigned stack_size) {
4193  llvm::llvm_execute_on_thread(fn, user_data, stack_size);
4194}
4195
4196} // end: extern "C"
4197
4198//===----------------------------------------------------------------------===//
4199// Token-based Operations.
4200//===----------------------------------------------------------------------===//
4201
4202/* CXToken layout:
4203 *   int_data[0]: a CXTokenKind
4204 *   int_data[1]: starting token location
4205 *   int_data[2]: token length
4206 *   int_data[3]: reserved
4207 *   ptr_data: for identifiers and keywords, an IdentifierInfo*.
4208 *   otherwise unused.
4209 */
4210extern "C" {
4211
4212CXTokenKind clang_getTokenKind(CXToken CXTok) {
4213  return static_cast<CXTokenKind>(CXTok.int_data[0]);
4214}
4215
4216CXString clang_getTokenSpelling(CXTranslationUnit TU, CXToken CXTok) {
4217  switch (clang_getTokenKind(CXTok)) {
4218  case CXToken_Identifier:
4219  case CXToken_Keyword:
4220    // We know we have an IdentifierInfo*, so use that.
4221    return createCXString(static_cast<IdentifierInfo *>(CXTok.ptr_data)
4222                            ->getNameStart());
4223
4224  case CXToken_Literal: {
4225    // We have stashed the starting pointer in the ptr_data field. Use it.
4226    const char *Text = static_cast<const char *>(CXTok.ptr_data);
4227    return createCXString(llvm::StringRef(Text, CXTok.int_data[2]));
4228  }
4229
4230  case CXToken_Punctuation:
4231  case CXToken_Comment:
4232    break;
4233  }
4234
4235  // We have to find the starting buffer pointer the hard way, by
4236  // deconstructing the source location.
4237  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4238  if (!CXXUnit)
4239    return createCXString("");
4240
4241  SourceLocation Loc = SourceLocation::getFromRawEncoding(CXTok.int_data[1]);
4242  std::pair<FileID, unsigned> LocInfo
4243    = CXXUnit->getSourceManager().getDecomposedLoc(Loc);
4244  bool Invalid = false;
4245  llvm::StringRef Buffer
4246    = CXXUnit->getSourceManager().getBufferData(LocInfo.first, &Invalid);
4247  if (Invalid)
4248    return createCXString("");
4249
4250  return createCXString(Buffer.substr(LocInfo.second, CXTok.int_data[2]));
4251}
4252
4253CXSourceLocation clang_getTokenLocation(CXTranslationUnit TU, CXToken CXTok) {
4254  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4255  if (!CXXUnit)
4256    return clang_getNullLocation();
4257
4258  return cxloc::translateSourceLocation(CXXUnit->getASTContext(),
4259                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4260}
4261
4262CXSourceRange clang_getTokenExtent(CXTranslationUnit TU, CXToken CXTok) {
4263  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4264  if (!CXXUnit)
4265    return clang_getNullRange();
4266
4267  return cxloc::translateSourceRange(CXXUnit->getASTContext(),
4268                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4269}
4270
4271void clang_tokenize(CXTranslationUnit TU, CXSourceRange Range,
4272                    CXToken **Tokens, unsigned *NumTokens) {
4273  if (Tokens)
4274    *Tokens = 0;
4275  if (NumTokens)
4276    *NumTokens = 0;
4277
4278  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4279  if (!CXXUnit || !Tokens || !NumTokens)
4280    return;
4281
4282  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
4283
4284  SourceRange R = cxloc::translateCXSourceRange(Range);
4285  if (R.isInvalid())
4286    return;
4287
4288  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4289  std::pair<FileID, unsigned> BeginLocInfo
4290    = SourceMgr.getDecomposedLoc(R.getBegin());
4291  std::pair<FileID, unsigned> EndLocInfo
4292    = SourceMgr.getDecomposedLoc(R.getEnd());
4293
4294  // Cannot tokenize across files.
4295  if (BeginLocInfo.first != EndLocInfo.first)
4296    return;
4297
4298  // Create a lexer
4299  bool Invalid = false;
4300  llvm::StringRef Buffer
4301    = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4302  if (Invalid)
4303    return;
4304
4305  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4306            CXXUnit->getASTContext().getLangOptions(),
4307            Buffer.begin(), Buffer.data() + BeginLocInfo.second, Buffer.end());
4308  Lex.SetCommentRetentionState(true);
4309
4310  // Lex tokens until we hit the end of the range.
4311  const char *EffectiveBufferEnd = Buffer.data() + EndLocInfo.second;
4312  llvm::SmallVector<CXToken, 32> CXTokens;
4313  Token Tok;
4314  bool previousWasAt = false;
4315  do {
4316    // Lex the next token
4317    Lex.LexFromRawLexer(Tok);
4318    if (Tok.is(tok::eof))
4319      break;
4320
4321    // Initialize the CXToken.
4322    CXToken CXTok;
4323
4324    //   - Common fields
4325    CXTok.int_data[1] = Tok.getLocation().getRawEncoding();
4326    CXTok.int_data[2] = Tok.getLength();
4327    CXTok.int_data[3] = 0;
4328
4329    //   - Kind-specific fields
4330    if (Tok.isLiteral()) {
4331      CXTok.int_data[0] = CXToken_Literal;
4332      CXTok.ptr_data = (void *)Tok.getLiteralData();
4333    } else if (Tok.is(tok::raw_identifier)) {
4334      // Lookup the identifier to determine whether we have a keyword.
4335      IdentifierInfo *II
4336        = CXXUnit->getPreprocessor().LookUpIdentifierInfo(Tok);
4337
4338      if ((II->getObjCKeywordID() != tok::objc_not_keyword) && previousWasAt) {
4339        CXTok.int_data[0] = CXToken_Keyword;
4340      }
4341      else {
4342        CXTok.int_data[0] = Tok.is(tok::identifier)
4343          ? CXToken_Identifier
4344          : CXToken_Keyword;
4345      }
4346      CXTok.ptr_data = II;
4347    } else if (Tok.is(tok::comment)) {
4348      CXTok.int_data[0] = CXToken_Comment;
4349      CXTok.ptr_data = 0;
4350    } else {
4351      CXTok.int_data[0] = CXToken_Punctuation;
4352      CXTok.ptr_data = 0;
4353    }
4354    CXTokens.push_back(CXTok);
4355    previousWasAt = Tok.is(tok::at);
4356  } while (Lex.getBufferLocation() <= EffectiveBufferEnd);
4357
4358  if (CXTokens.empty())
4359    return;
4360
4361  *Tokens = (CXToken *)malloc(sizeof(CXToken) * CXTokens.size());
4362  memmove(*Tokens, CXTokens.data(), sizeof(CXToken) * CXTokens.size());
4363  *NumTokens = CXTokens.size();
4364}
4365
4366void clang_disposeTokens(CXTranslationUnit TU,
4367                         CXToken *Tokens, unsigned NumTokens) {
4368  free(Tokens);
4369}
4370
4371} // end: extern "C"
4372
4373//===----------------------------------------------------------------------===//
4374// Token annotation APIs.
4375//===----------------------------------------------------------------------===//
4376
4377typedef llvm::DenseMap<unsigned, CXCursor> AnnotateTokensData;
4378static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4379                                                     CXCursor parent,
4380                                                     CXClientData client_data);
4381namespace {
4382class AnnotateTokensWorker {
4383  AnnotateTokensData &Annotated;
4384  CXToken *Tokens;
4385  CXCursor *Cursors;
4386  unsigned NumTokens;
4387  unsigned TokIdx;
4388  unsigned PreprocessingTokIdx;
4389  CursorVisitor AnnotateVis;
4390  SourceManager &SrcMgr;
4391  bool HasContextSensitiveKeywords;
4392
4393  bool MoreTokens() const { return TokIdx < NumTokens; }
4394  unsigned NextToken() const { return TokIdx; }
4395  void AdvanceToken() { ++TokIdx; }
4396  SourceLocation GetTokenLoc(unsigned tokI) {
4397    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4398  }
4399
4400public:
4401  AnnotateTokensWorker(AnnotateTokensData &annotated,
4402                       CXToken *tokens, CXCursor *cursors, unsigned numTokens,
4403                       CXTranslationUnit tu, SourceRange RegionOfInterest)
4404    : Annotated(annotated), Tokens(tokens), Cursors(cursors),
4405      NumTokens(numTokens), TokIdx(0), PreprocessingTokIdx(0),
4406      AnnotateVis(tu,
4407                  AnnotateTokensVisitor, this,
4408                  Decl::MaxPCHLevel, true, RegionOfInterest),
4409      SrcMgr(static_cast<ASTUnit*>(tu->TUData)->getSourceManager()),
4410      HasContextSensitiveKeywords(false) { }
4411
4412  void VisitChildren(CXCursor C) { AnnotateVis.VisitChildren(C); }
4413  enum CXChildVisitResult Visit(CXCursor cursor, CXCursor parent);
4414  void AnnotateTokens(CXCursor parent);
4415  void AnnotateTokens() {
4416    AnnotateTokens(clang_getTranslationUnitCursor(AnnotateVis.getTU()));
4417  }
4418
4419  /// \brief Determine whether the annotator saw any cursors that have
4420  /// context-sensitive keywords.
4421  bool hasContextSensitiveKeywords() const {
4422    return HasContextSensitiveKeywords;
4423  }
4424};
4425}
4426
4427void AnnotateTokensWorker::AnnotateTokens(CXCursor parent) {
4428  // Walk the AST within the region of interest, annotating tokens
4429  // along the way.
4430  VisitChildren(parent);
4431
4432  for (unsigned I = 0 ; I < TokIdx ; ++I) {
4433    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4434    if (Pos != Annotated.end() &&
4435        (clang_isInvalid(Cursors[I].kind) ||
4436         Pos->second.kind != CXCursor_PreprocessingDirective))
4437      Cursors[I] = Pos->second;
4438  }
4439
4440  // Finish up annotating any tokens left.
4441  if (!MoreTokens())
4442    return;
4443
4444  const CXCursor &C = clang_getNullCursor();
4445  for (unsigned I = TokIdx ; I < NumTokens ; ++I) {
4446    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4447    Cursors[I] = (Pos == Annotated.end()) ? C : Pos->second;
4448  }
4449}
4450
4451enum CXChildVisitResult
4452AnnotateTokensWorker::Visit(CXCursor cursor, CXCursor parent) {
4453  CXSourceLocation Loc = clang_getCursorLocation(cursor);
4454  SourceRange cursorRange = getRawCursorExtent(cursor);
4455  if (cursorRange.isInvalid())
4456    return CXChildVisit_Recurse;
4457
4458  if (!HasContextSensitiveKeywords) {
4459    // Objective-C properties can have context-sensitive keywords.
4460    if (cursor.kind == CXCursor_ObjCPropertyDecl) {
4461      if (ObjCPropertyDecl *Property
4462                  = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(cursor)))
4463        HasContextSensitiveKeywords = Property->getPropertyAttributesAsWritten() != 0;
4464    }
4465    // Objective-C methods can have context-sensitive keywords.
4466    else if (cursor.kind == CXCursor_ObjCInstanceMethodDecl ||
4467             cursor.kind == CXCursor_ObjCClassMethodDecl) {
4468      if (ObjCMethodDecl *Method
4469            = dyn_cast_or_null<ObjCMethodDecl>(getCursorDecl(cursor))) {
4470        if (Method->getObjCDeclQualifier())
4471          HasContextSensitiveKeywords = true;
4472        else {
4473          for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
4474                                           PEnd = Method->param_end();
4475               P != PEnd; ++P) {
4476            if ((*P)->getObjCDeclQualifier()) {
4477              HasContextSensitiveKeywords = true;
4478              break;
4479            }
4480          }
4481        }
4482      }
4483    }
4484    // C++ methods can have context-sensitive keywords.
4485    else if (cursor.kind == CXCursor_CXXMethod) {
4486      if (CXXMethodDecl *Method
4487                  = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(cursor))) {
4488        if (Method->hasAttr<FinalAttr>() || Method->hasAttr<OverrideAttr>())
4489          HasContextSensitiveKeywords = true;
4490      }
4491    }
4492    // C++ classes can have context-sensitive keywords.
4493    else if (cursor.kind == CXCursor_StructDecl ||
4494             cursor.kind == CXCursor_ClassDecl ||
4495             cursor.kind == CXCursor_ClassTemplate ||
4496             cursor.kind == CXCursor_ClassTemplatePartialSpecialization) {
4497      if (Decl *D = getCursorDecl(cursor))
4498        if (D->hasAttr<FinalAttr>())
4499          HasContextSensitiveKeywords = true;
4500    }
4501  }
4502
4503  if (clang_isPreprocessing(cursor.kind)) {
4504    // For macro instantiations, just note where the beginning of the macro
4505    // instantiation occurs.
4506    if (cursor.kind == CXCursor_MacroInstantiation) {
4507      Annotated[Loc.int_data] = cursor;
4508      return CXChildVisit_Recurse;
4509    }
4510
4511    // Items in the preprocessing record are kept separate from items in
4512    // declarations, so we keep a separate token index.
4513    unsigned SavedTokIdx = TokIdx;
4514    TokIdx = PreprocessingTokIdx;
4515
4516    // Skip tokens up until we catch up to the beginning of the preprocessing
4517    // entry.
4518    while (MoreTokens()) {
4519      const unsigned I = NextToken();
4520      SourceLocation TokLoc = GetTokenLoc(I);
4521      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4522      case RangeBefore:
4523        AdvanceToken();
4524        continue;
4525      case RangeAfter:
4526      case RangeOverlap:
4527        break;
4528      }
4529      break;
4530    }
4531
4532    // Look at all of the tokens within this range.
4533    while (MoreTokens()) {
4534      const unsigned I = NextToken();
4535      SourceLocation TokLoc = GetTokenLoc(I);
4536      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4537      case RangeBefore:
4538        assert(0 && "Infeasible");
4539      case RangeAfter:
4540        break;
4541      case RangeOverlap:
4542        Cursors[I] = cursor;
4543        AdvanceToken();
4544        continue;
4545      }
4546      break;
4547    }
4548
4549    // Save the preprocessing token index; restore the non-preprocessing
4550    // token index.
4551    PreprocessingTokIdx = TokIdx;
4552    TokIdx = SavedTokIdx;
4553    return CXChildVisit_Recurse;
4554  }
4555
4556  if (cursorRange.isInvalid())
4557    return CXChildVisit_Continue;
4558
4559  SourceLocation L = SourceLocation::getFromRawEncoding(Loc.int_data);
4560
4561  // Adjust the annotated range based specific declarations.
4562  const enum CXCursorKind cursorK = clang_getCursorKind(cursor);
4563  if (cursorK >= CXCursor_FirstDecl && cursorK <= CXCursor_LastDecl) {
4564    Decl *D = cxcursor::getCursorDecl(cursor);
4565    // Don't visit synthesized ObjC methods, since they have no syntatic
4566    // representation in the source.
4567    if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
4568      if (MD->isSynthesized())
4569        return CXChildVisit_Continue;
4570    }
4571
4572    SourceLocation StartLoc;
4573    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
4574      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
4575        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4576    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
4577      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
4578        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4579    }
4580
4581    if (StartLoc.isValid() && L.isValid() &&
4582        SrcMgr.isBeforeInTranslationUnit(StartLoc, L))
4583      cursorRange.setBegin(StartLoc);
4584  }
4585
4586  // If the location of the cursor occurs within a macro instantiation, record
4587  // the spelling location of the cursor in our annotation map.  We can then
4588  // paper over the token labelings during a post-processing step to try and
4589  // get cursor mappings for tokens that are the *arguments* of a macro
4590  // instantiation.
4591  if (L.isMacroID()) {
4592    unsigned rawEncoding = SrcMgr.getSpellingLoc(L).getRawEncoding();
4593    // Only invalidate the old annotation if it isn't part of a preprocessing
4594    // directive.  Here we assume that the default construction of CXCursor
4595    // results in CXCursor.kind being an initialized value (i.e., 0).  If
4596    // this isn't the case, we can fix by doing lookup + insertion.
4597
4598    CXCursor &oldC = Annotated[rawEncoding];
4599    if (!clang_isPreprocessing(oldC.kind))
4600      oldC = cursor;
4601  }
4602
4603  const enum CXCursorKind K = clang_getCursorKind(parent);
4604  const CXCursor updateC =
4605    (clang_isInvalid(K) || K == CXCursor_TranslationUnit)
4606     ? clang_getNullCursor() : parent;
4607
4608  while (MoreTokens()) {
4609    const unsigned I = NextToken();
4610    SourceLocation TokLoc = GetTokenLoc(I);
4611    switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4612      case RangeBefore:
4613        Cursors[I] = updateC;
4614        AdvanceToken();
4615        continue;
4616      case RangeAfter:
4617      case RangeOverlap:
4618        break;
4619    }
4620    break;
4621  }
4622
4623  // Visit children to get their cursor information.
4624  const unsigned BeforeChildren = NextToken();
4625  VisitChildren(cursor);
4626  const unsigned AfterChildren = NextToken();
4627
4628  // Adjust 'Last' to the last token within the extent of the cursor.
4629  while (MoreTokens()) {
4630    const unsigned I = NextToken();
4631    SourceLocation TokLoc = GetTokenLoc(I);
4632    switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4633      case RangeBefore:
4634        assert(0 && "Infeasible");
4635      case RangeAfter:
4636        break;
4637      case RangeOverlap:
4638        Cursors[I] = updateC;
4639        AdvanceToken();
4640        continue;
4641    }
4642    break;
4643  }
4644  const unsigned Last = NextToken();
4645
4646  // Scan the tokens that are at the beginning of the cursor, but are not
4647  // capture by the child cursors.
4648
4649  // For AST elements within macros, rely on a post-annotate pass to
4650  // to correctly annotate the tokens with cursors.  Otherwise we can
4651  // get confusing results of having tokens that map to cursors that really
4652  // are expanded by an instantiation.
4653  if (L.isMacroID())
4654    cursor = clang_getNullCursor();
4655
4656  for (unsigned I = BeforeChildren; I != AfterChildren; ++I) {
4657    if (!clang_isInvalid(clang_getCursorKind(Cursors[I])))
4658      break;
4659
4660    Cursors[I] = cursor;
4661  }
4662  // Scan the tokens that are at the end of the cursor, but are not captured
4663  // but the child cursors.
4664  for (unsigned I = AfterChildren; I != Last; ++I)
4665    Cursors[I] = cursor;
4666
4667  TokIdx = Last;
4668  return CXChildVisit_Continue;
4669}
4670
4671static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4672                                                     CXCursor parent,
4673                                                     CXClientData client_data) {
4674  return static_cast<AnnotateTokensWorker*>(client_data)->Visit(cursor, parent);
4675}
4676
4677namespace {
4678  struct clang_annotateTokens_Data {
4679    CXTranslationUnit TU;
4680    ASTUnit *CXXUnit;
4681    CXToken *Tokens;
4682    unsigned NumTokens;
4683    CXCursor *Cursors;
4684  };
4685}
4686
4687// This gets run a separate thread to avoid stack blowout.
4688static void clang_annotateTokensImpl(void *UserData) {
4689  CXTranslationUnit TU = ((clang_annotateTokens_Data*)UserData)->TU;
4690  ASTUnit *CXXUnit = ((clang_annotateTokens_Data*)UserData)->CXXUnit;
4691  CXToken *Tokens = ((clang_annotateTokens_Data*)UserData)->Tokens;
4692  const unsigned NumTokens = ((clang_annotateTokens_Data*)UserData)->NumTokens;
4693  CXCursor *Cursors = ((clang_annotateTokens_Data*)UserData)->Cursors;
4694
4695  // Determine the region of interest, which contains all of the tokens.
4696  SourceRange RegionOfInterest;
4697  RegionOfInterest.setBegin(
4698    cxloc::translateSourceLocation(clang_getTokenLocation(TU, Tokens[0])));
4699  RegionOfInterest.setEnd(
4700    cxloc::translateSourceLocation(clang_getTokenLocation(TU,
4701                                                         Tokens[NumTokens-1])));
4702
4703  // A mapping from the source locations found when re-lexing or traversing the
4704  // region of interest to the corresponding cursors.
4705  AnnotateTokensData Annotated;
4706
4707  // Relex the tokens within the source range to look for preprocessing
4708  // directives.
4709  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4710  std::pair<FileID, unsigned> BeginLocInfo
4711    = SourceMgr.getDecomposedLoc(RegionOfInterest.getBegin());
4712  std::pair<FileID, unsigned> EndLocInfo
4713    = SourceMgr.getDecomposedLoc(RegionOfInterest.getEnd());
4714
4715  llvm::StringRef Buffer;
4716  bool Invalid = false;
4717  if (BeginLocInfo.first == EndLocInfo.first &&
4718      ((Buffer = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid)),true) &&
4719      !Invalid) {
4720    Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4721              CXXUnit->getASTContext().getLangOptions(),
4722              Buffer.begin(), Buffer.data() + BeginLocInfo.second,
4723              Buffer.end());
4724    Lex.SetCommentRetentionState(true);
4725
4726    // Lex tokens in raw mode until we hit the end of the range, to avoid
4727    // entering #includes or expanding macros.
4728    while (true) {
4729      Token Tok;
4730      Lex.LexFromRawLexer(Tok);
4731
4732    reprocess:
4733      if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
4734        // We have found a preprocessing directive. Gobble it up so that we
4735        // don't see it while preprocessing these tokens later, but keep track
4736        // of all of the token locations inside this preprocessing directive so
4737        // that we can annotate them appropriately.
4738        //
4739        // FIXME: Some simple tests here could identify macro definitions and
4740        // #undefs, to provide specific cursor kinds for those.
4741        llvm::SmallVector<SourceLocation, 32> Locations;
4742        do {
4743          Locations.push_back(Tok.getLocation());
4744          Lex.LexFromRawLexer(Tok);
4745        } while (!Tok.isAtStartOfLine() && !Tok.is(tok::eof));
4746
4747        using namespace cxcursor;
4748        CXCursor Cursor
4749        = MakePreprocessingDirectiveCursor(SourceRange(Locations.front(),
4750                                                       Locations.back()),
4751                                           TU);
4752        for (unsigned I = 0, N = Locations.size(); I != N; ++I) {
4753          Annotated[Locations[I].getRawEncoding()] = Cursor;
4754        }
4755
4756        if (Tok.isAtStartOfLine())
4757          goto reprocess;
4758
4759        continue;
4760      }
4761
4762      if (Tok.is(tok::eof))
4763        break;
4764    }
4765  }
4766
4767  // Annotate all of the source locations in the region of interest that map to
4768  // a specific cursor.
4769  AnnotateTokensWorker W(Annotated, Tokens, Cursors, NumTokens,
4770                         TU, RegionOfInterest);
4771
4772  // FIXME: We use a ridiculous stack size here because the data-recursion
4773  // algorithm uses a large stack frame than the non-data recursive version,
4774  // and AnnotationTokensWorker currently transforms the data-recursion
4775  // algorithm back into a traditional recursion by explicitly calling
4776  // VisitChildren().  We will need to remove this explicit recursive call.
4777  W.AnnotateTokens();
4778
4779  // If we ran into any entities that involve context-sensitive keywords,
4780  // take another pass through the tokens to mark them as such.
4781  if (W.hasContextSensitiveKeywords()) {
4782    for (unsigned I = 0; I != NumTokens; ++I) {
4783      if (clang_getTokenKind(Tokens[I]) != CXToken_Identifier)
4784        continue;
4785
4786      if (Cursors[I].kind == CXCursor_ObjCPropertyDecl) {
4787        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
4788        if (ObjCPropertyDecl *Property
4789            = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(Cursors[I]))) {
4790          if (Property->getPropertyAttributesAsWritten() != 0 &&
4791              llvm::StringSwitch<bool>(II->getName())
4792              .Case("readonly", true)
4793              .Case("assign", true)
4794              .Case("readwrite", true)
4795              .Case("retain", true)
4796              .Case("copy", true)
4797              .Case("nonatomic", true)
4798              .Case("atomic", true)
4799              .Case("getter", true)
4800              .Case("setter", true)
4801              .Default(false))
4802            Tokens[I].int_data[0] = CXToken_Keyword;
4803        }
4804        continue;
4805      }
4806
4807      if (Cursors[I].kind == CXCursor_ObjCInstanceMethodDecl ||
4808          Cursors[I].kind == CXCursor_ObjCClassMethodDecl) {
4809        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
4810        if (llvm::StringSwitch<bool>(II->getName())
4811            .Case("in", true)
4812            .Case("out", true)
4813            .Case("inout", true)
4814            .Case("oneway", true)
4815            .Case("bycopy", true)
4816            .Case("byref", true)
4817            .Default(false))
4818          Tokens[I].int_data[0] = CXToken_Keyword;
4819        continue;
4820      }
4821
4822      if (Cursors[I].kind == CXCursor_CXXMethod) {
4823        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
4824        if (CXXMethodDecl *Method
4825            = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(Cursors[I]))) {
4826          if ((Method->hasAttr<FinalAttr>() ||
4827               Method->hasAttr<OverrideAttr>()) &&
4828              Method->getLocation().getRawEncoding() != Tokens[I].int_data[1] &&
4829              llvm::StringSwitch<bool>(II->getName())
4830              .Case("final", true)
4831              .Case("override", true)
4832              .Default(false))
4833            Tokens[I].int_data[0] = CXToken_Keyword;
4834        }
4835        continue;
4836      }
4837
4838      if (Cursors[I].kind == CXCursor_ClassDecl ||
4839          Cursors[I].kind == CXCursor_StructDecl ||
4840          Cursors[I].kind == CXCursor_ClassTemplate) {
4841        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
4842        if (II->getName() == "final") {
4843          // We have to be careful with 'final', since it could be the name
4844          // of a member class rather than the context-sensitive keyword.
4845          // So, check whether the cursor associated with this
4846          Decl *D = getCursorDecl(Cursors[I]);
4847          if (CXXRecordDecl *Record = dyn_cast_or_null<CXXRecordDecl>(D)) {
4848            if ((Record->hasAttr<FinalAttr>()) &&
4849                Record->getIdentifier() != II)
4850              Tokens[I].int_data[0] = CXToken_Keyword;
4851          } else if (ClassTemplateDecl *ClassTemplate
4852                     = dyn_cast_or_null<ClassTemplateDecl>(D)) {
4853            CXXRecordDecl *Record = ClassTemplate->getTemplatedDecl();
4854            if ((Record->hasAttr<FinalAttr>()) &&
4855                Record->getIdentifier() != II)
4856              Tokens[I].int_data[0] = CXToken_Keyword;
4857          }
4858        }
4859        continue;
4860      }
4861    }
4862  }
4863}
4864
4865extern "C" {
4866
4867void clang_annotateTokens(CXTranslationUnit TU,
4868                          CXToken *Tokens, unsigned NumTokens,
4869                          CXCursor *Cursors) {
4870
4871  if (NumTokens == 0 || !Tokens || !Cursors)
4872    return;
4873
4874  // Any token we don't specifically annotate will have a NULL cursor.
4875  CXCursor C = clang_getNullCursor();
4876  for (unsigned I = 0; I != NumTokens; ++I)
4877    Cursors[I] = C;
4878
4879  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4880  if (!CXXUnit)
4881    return;
4882
4883  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
4884
4885  clang_annotateTokens_Data data = { TU, CXXUnit, Tokens, NumTokens, Cursors };
4886  llvm::CrashRecoveryContext CRC;
4887  if (!RunSafely(CRC, clang_annotateTokensImpl, &data,
4888                 GetSafetyThreadStackSize() * 2)) {
4889    fprintf(stderr, "libclang: crash detected while annotating tokens\n");
4890  }
4891}
4892
4893} // end: extern "C"
4894
4895//===----------------------------------------------------------------------===//
4896// Operations for querying linkage of a cursor.
4897//===----------------------------------------------------------------------===//
4898
4899extern "C" {
4900CXLinkageKind clang_getCursorLinkage(CXCursor cursor) {
4901  if (!clang_isDeclaration(cursor.kind))
4902    return CXLinkage_Invalid;
4903
4904  Decl *D = cxcursor::getCursorDecl(cursor);
4905  if (NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
4906    switch (ND->getLinkage()) {
4907      case NoLinkage: return CXLinkage_NoLinkage;
4908      case InternalLinkage: return CXLinkage_Internal;
4909      case UniqueExternalLinkage: return CXLinkage_UniqueExternal;
4910      case ExternalLinkage: return CXLinkage_External;
4911    };
4912
4913  return CXLinkage_Invalid;
4914}
4915} // end: extern "C"
4916
4917//===----------------------------------------------------------------------===//
4918// Operations for querying language of a cursor.
4919//===----------------------------------------------------------------------===//
4920
4921static CXLanguageKind getDeclLanguage(const Decl *D) {
4922  switch (D->getKind()) {
4923    default:
4924      break;
4925    case Decl::ImplicitParam:
4926    case Decl::ObjCAtDefsField:
4927    case Decl::ObjCCategory:
4928    case Decl::ObjCCategoryImpl:
4929    case Decl::ObjCClass:
4930    case Decl::ObjCCompatibleAlias:
4931    case Decl::ObjCForwardProtocol:
4932    case Decl::ObjCImplementation:
4933    case Decl::ObjCInterface:
4934    case Decl::ObjCIvar:
4935    case Decl::ObjCMethod:
4936    case Decl::ObjCProperty:
4937    case Decl::ObjCPropertyImpl:
4938    case Decl::ObjCProtocol:
4939      return CXLanguage_ObjC;
4940    case Decl::CXXConstructor:
4941    case Decl::CXXConversion:
4942    case Decl::CXXDestructor:
4943    case Decl::CXXMethod:
4944    case Decl::CXXRecord:
4945    case Decl::ClassTemplate:
4946    case Decl::ClassTemplatePartialSpecialization:
4947    case Decl::ClassTemplateSpecialization:
4948    case Decl::Friend:
4949    case Decl::FriendTemplate:
4950    case Decl::FunctionTemplate:
4951    case Decl::LinkageSpec:
4952    case Decl::Namespace:
4953    case Decl::NamespaceAlias:
4954    case Decl::NonTypeTemplateParm:
4955    case Decl::StaticAssert:
4956    case Decl::TemplateTemplateParm:
4957    case Decl::TemplateTypeParm:
4958    case Decl::UnresolvedUsingTypename:
4959    case Decl::UnresolvedUsingValue:
4960    case Decl::Using:
4961    case Decl::UsingDirective:
4962    case Decl::UsingShadow:
4963      return CXLanguage_CPlusPlus;
4964  }
4965
4966  return CXLanguage_C;
4967}
4968
4969extern "C" {
4970
4971enum CXAvailabilityKind clang_getCursorAvailability(CXCursor cursor) {
4972  if (clang_isDeclaration(cursor.kind))
4973    if (Decl *D = cxcursor::getCursorDecl(cursor)) {
4974      if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->isDeleted())
4975        return CXAvailability_Available;
4976
4977      switch (D->getAvailability()) {
4978      case AR_Available:
4979      case AR_NotYetIntroduced:
4980        return CXAvailability_Available;
4981
4982      case AR_Deprecated:
4983        return CXAvailability_Deprecated;
4984
4985      case AR_Unavailable:
4986        return CXAvailability_NotAvailable;
4987      }
4988    }
4989
4990  return CXAvailability_Available;
4991}
4992
4993CXLanguageKind clang_getCursorLanguage(CXCursor cursor) {
4994  if (clang_isDeclaration(cursor.kind))
4995    return getDeclLanguage(cxcursor::getCursorDecl(cursor));
4996
4997  return CXLanguage_Invalid;
4998}
4999
5000 /// \brief If the given cursor is the "templated" declaration
5001 /// descibing a class or function template, return the class or
5002 /// function template.
5003static Decl *maybeGetTemplateCursor(Decl *D) {
5004  if (!D)
5005    return 0;
5006
5007  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
5008    if (FunctionTemplateDecl *FunTmpl = FD->getDescribedFunctionTemplate())
5009      return FunTmpl;
5010
5011  if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D))
5012    if (ClassTemplateDecl *ClassTmpl = RD->getDescribedClassTemplate())
5013      return ClassTmpl;
5014
5015  return D;
5016}
5017
5018CXCursor clang_getCursorSemanticParent(CXCursor cursor) {
5019  if (clang_isDeclaration(cursor.kind)) {
5020    if (Decl *D = getCursorDecl(cursor)) {
5021      DeclContext *DC = D->getDeclContext();
5022      if (!DC)
5023        return clang_getNullCursor();
5024
5025      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5026                          getCursorTU(cursor));
5027    }
5028  }
5029
5030  if (clang_isStatement(cursor.kind) || clang_isExpression(cursor.kind)) {
5031    if (Decl *D = getCursorDecl(cursor))
5032      return MakeCXCursor(D, getCursorTU(cursor));
5033  }
5034
5035  return clang_getNullCursor();
5036}
5037
5038CXCursor clang_getCursorLexicalParent(CXCursor cursor) {
5039  if (clang_isDeclaration(cursor.kind)) {
5040    if (Decl *D = getCursorDecl(cursor)) {
5041      DeclContext *DC = D->getLexicalDeclContext();
5042      if (!DC)
5043        return clang_getNullCursor();
5044
5045      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5046                          getCursorTU(cursor));
5047    }
5048  }
5049
5050  // FIXME: Note that we can't easily compute the lexical context of a
5051  // statement or expression, so we return nothing.
5052  return clang_getNullCursor();
5053}
5054
5055static void CollectOverriddenMethods(DeclContext *Ctx,
5056                                     ObjCMethodDecl *Method,
5057                            llvm::SmallVectorImpl<ObjCMethodDecl *> &Methods) {
5058  if (!Ctx)
5059    return;
5060
5061  // If we have a class or category implementation, jump straight to the
5062  // interface.
5063  if (ObjCImplDecl *Impl = dyn_cast<ObjCImplDecl>(Ctx))
5064    return CollectOverriddenMethods(Impl->getClassInterface(), Method, Methods);
5065
5066  ObjCContainerDecl *Container = dyn_cast<ObjCContainerDecl>(Ctx);
5067  if (!Container)
5068    return;
5069
5070  // Check whether we have a matching method at this level.
5071  if (ObjCMethodDecl *Overridden = Container->getMethod(Method->getSelector(),
5072                                                    Method->isInstanceMethod()))
5073    if (Method != Overridden) {
5074      // We found an override at this level; there is no need to look
5075      // into other protocols or categories.
5076      Methods.push_back(Overridden);
5077      return;
5078    }
5079
5080  if (ObjCProtocolDecl *Protocol = dyn_cast<ObjCProtocolDecl>(Container)) {
5081    for (ObjCProtocolDecl::protocol_iterator P = Protocol->protocol_begin(),
5082                                          PEnd = Protocol->protocol_end();
5083         P != PEnd; ++P)
5084      CollectOverriddenMethods(*P, Method, Methods);
5085  }
5086
5087  if (ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(Container)) {
5088    for (ObjCCategoryDecl::protocol_iterator P = Category->protocol_begin(),
5089                                          PEnd = Category->protocol_end();
5090         P != PEnd; ++P)
5091      CollectOverriddenMethods(*P, Method, Methods);
5092  }
5093
5094  if (ObjCInterfaceDecl *Interface = dyn_cast<ObjCInterfaceDecl>(Container)) {
5095    for (ObjCInterfaceDecl::protocol_iterator P = Interface->protocol_begin(),
5096                                           PEnd = Interface->protocol_end();
5097         P != PEnd; ++P)
5098      CollectOverriddenMethods(*P, Method, Methods);
5099
5100    for (ObjCCategoryDecl *Category = Interface->getCategoryList();
5101         Category; Category = Category->getNextClassCategory())
5102      CollectOverriddenMethods(Category, Method, Methods);
5103
5104    // We only look into the superclass if we haven't found anything yet.
5105    if (Methods.empty())
5106      if (ObjCInterfaceDecl *Super = Interface->getSuperClass())
5107        return CollectOverriddenMethods(Super, Method, Methods);
5108  }
5109}
5110
5111void clang_getOverriddenCursors(CXCursor cursor,
5112                                CXCursor **overridden,
5113                                unsigned *num_overridden) {
5114  if (overridden)
5115    *overridden = 0;
5116  if (num_overridden)
5117    *num_overridden = 0;
5118  if (!overridden || !num_overridden)
5119    return;
5120
5121  if (!clang_isDeclaration(cursor.kind))
5122    return;
5123
5124  Decl *D = getCursorDecl(cursor);
5125  if (!D)
5126    return;
5127
5128  // Handle C++ member functions.
5129  CXTranslationUnit TU = getCursorTU(cursor);
5130  if (CXXMethodDecl *CXXMethod = dyn_cast<CXXMethodDecl>(D)) {
5131    *num_overridden = CXXMethod->size_overridden_methods();
5132    if (!*num_overridden)
5133      return;
5134
5135    *overridden = new CXCursor [*num_overridden];
5136    unsigned I = 0;
5137    for (CXXMethodDecl::method_iterator
5138              M = CXXMethod->begin_overridden_methods(),
5139           MEnd = CXXMethod->end_overridden_methods();
5140         M != MEnd; (void)++M, ++I)
5141      (*overridden)[I] = MakeCXCursor(const_cast<CXXMethodDecl*>(*M), TU);
5142    return;
5143  }
5144
5145  ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(D);
5146  if (!Method)
5147    return;
5148
5149  // Handle Objective-C methods.
5150  llvm::SmallVector<ObjCMethodDecl *, 4> Methods;
5151  CollectOverriddenMethods(Method->getDeclContext(), Method, Methods);
5152
5153  if (Methods.empty())
5154    return;
5155
5156  *num_overridden = Methods.size();
5157  *overridden = new CXCursor [Methods.size()];
5158  for (unsigned I = 0, N = Methods.size(); I != N; ++I)
5159    (*overridden)[I] = MakeCXCursor(Methods[I], TU);
5160}
5161
5162void clang_disposeOverriddenCursors(CXCursor *overridden) {
5163  delete [] overridden;
5164}
5165
5166CXFile clang_getIncludedFile(CXCursor cursor) {
5167  if (cursor.kind != CXCursor_InclusionDirective)
5168    return 0;
5169
5170  InclusionDirective *ID = getCursorInclusionDirective(cursor);
5171  return (void *)ID->getFile();
5172}
5173
5174} // end: extern "C"
5175
5176
5177//===----------------------------------------------------------------------===//
5178// C++ AST instrospection.
5179//===----------------------------------------------------------------------===//
5180
5181extern "C" {
5182unsigned clang_CXXMethod_isStatic(CXCursor C) {
5183  if (!clang_isDeclaration(C.kind))
5184    return 0;
5185
5186  CXXMethodDecl *Method = 0;
5187  Decl *D = cxcursor::getCursorDecl(C);
5188  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5189    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5190  else
5191    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5192  return (Method && Method->isStatic()) ? 1 : 0;
5193}
5194
5195unsigned clang_CXXMethod_isVirtual(CXCursor C) {
5196  if (!clang_isDeclaration(C.kind))
5197    return 0;
5198
5199  CXXMethodDecl *Method = 0;
5200  Decl *D = cxcursor::getCursorDecl(C);
5201  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5202    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5203  else
5204    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5205  return (Method && Method->isVirtual()) ? 1 : 0;
5206}
5207
5208} // end: extern "C"
5209
5210//===----------------------------------------------------------------------===//
5211// Attribute introspection.
5212//===----------------------------------------------------------------------===//
5213
5214extern "C" {
5215CXType clang_getIBOutletCollectionType(CXCursor C) {
5216  if (C.kind != CXCursor_IBOutletCollectionAttr)
5217    return cxtype::MakeCXType(QualType(), cxcursor::getCursorTU(C));
5218
5219  IBOutletCollectionAttr *A =
5220    cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(C));
5221
5222  return cxtype::MakeCXType(A->getInterFace(), cxcursor::getCursorTU(C));
5223}
5224} // end: extern "C"
5225
5226//===----------------------------------------------------------------------===//
5227// Inspecting memory usage.
5228//===----------------------------------------------------------------------===//
5229
5230typedef std::vector<CXTUResourceUsageEntry> MemUsageEntries;
5231
5232static inline void createCXTUResourceUsageEntry(MemUsageEntries &entries,
5233                                              enum CXTUResourceUsageKind k,
5234                                              unsigned long amount) {
5235  CXTUResourceUsageEntry entry = { k, amount };
5236  entries.push_back(entry);
5237}
5238
5239extern "C" {
5240
5241const char *clang_getTUResourceUsageName(CXTUResourceUsageKind kind) {
5242  const char *str = "";
5243  switch (kind) {
5244    case CXTUResourceUsage_AST:
5245      str = "ASTContext: expressions, declarations, and types";
5246      break;
5247    case CXTUResourceUsage_Identifiers:
5248      str = "ASTContext: identifiers";
5249      break;
5250    case CXTUResourceUsage_Selectors:
5251      str = "ASTContext: selectors";
5252      break;
5253    case CXTUResourceUsage_GlobalCompletionResults:
5254      str = "Code completion: cached global results";
5255      break;
5256    case CXTUResourceUsage_SourceManagerContentCache:
5257      str = "SourceManager: content cache allocator";
5258      break;
5259    case CXTUResourceUsage_AST_SideTables:
5260      str = "ASTContext: side tables";
5261      break;
5262    case CXTUResourceUsage_SourceManager_Membuffer_Malloc:
5263      str = "SourceManager: malloc'ed memory buffers";
5264      break;
5265    case CXTUResourceUsage_SourceManager_Membuffer_MMap:
5266      str = "SourceManager: mmap'ed memory buffers";
5267      break;
5268    case CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc:
5269      str = "ExternalASTSource: malloc'ed memory buffers";
5270      break;
5271    case CXTUResourceUsage_ExternalASTSource_Membuffer_MMap:
5272      str = "ExternalASTSource: mmap'ed memory buffers";
5273      break;
5274    case CXTUResourceUsage_Preprocessor:
5275      str = "Preprocessor: malloc'ed memory";
5276      break;
5277    case CXTUResourceUsage_PreprocessingRecord:
5278      str = "Preprocessor: PreprocessingRecord";
5279      break;
5280  }
5281  return str;
5282}
5283
5284CXTUResourceUsage clang_getCXTUResourceUsage(CXTranslationUnit TU) {
5285  if (!TU) {
5286    CXTUResourceUsage usage = { (void*) 0, 0, 0 };
5287    return usage;
5288  }
5289
5290  ASTUnit *astUnit = static_cast<ASTUnit*>(TU->TUData);
5291  llvm::OwningPtr<MemUsageEntries> entries(new MemUsageEntries());
5292  ASTContext &astContext = astUnit->getASTContext();
5293
5294  // How much memory is used by AST nodes and types?
5295  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST,
5296    (unsigned long) astContext.getASTAllocatedMemory());
5297
5298  // How much memory is used by identifiers?
5299  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Identifiers,
5300    (unsigned long) astContext.Idents.getAllocator().getTotalMemory());
5301
5302  // How much memory is used for selectors?
5303  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Selectors,
5304    (unsigned long) astContext.Selectors.getTotalMemory());
5305
5306  // How much memory is used by ASTContext's side tables?
5307  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST_SideTables,
5308    (unsigned long) astContext.getSideTableAllocatedMemory());
5309
5310  // How much memory is used for caching global code completion results?
5311  unsigned long completionBytes = 0;
5312  if (GlobalCodeCompletionAllocator *completionAllocator =
5313      astUnit->getCachedCompletionAllocator().getPtr()) {
5314    completionBytes = completionAllocator->getTotalMemory();
5315  }
5316  createCXTUResourceUsageEntry(*entries,
5317                               CXTUResourceUsage_GlobalCompletionResults,
5318                               completionBytes);
5319
5320  // How much memory is being used by SourceManager's content cache?
5321  createCXTUResourceUsageEntry(*entries,
5322          CXTUResourceUsage_SourceManagerContentCache,
5323          (unsigned long) astContext.getSourceManager().getContentCacheSize());
5324
5325  // How much memory is being used by the MemoryBuffer's in SourceManager?
5326  const SourceManager::MemoryBufferSizes &srcBufs =
5327    astUnit->getSourceManager().getMemoryBufferSizes();
5328
5329  createCXTUResourceUsageEntry(*entries,
5330                               CXTUResourceUsage_SourceManager_Membuffer_Malloc,
5331                               (unsigned long) srcBufs.malloc_bytes);
5332    createCXTUResourceUsageEntry(*entries,
5333                               CXTUResourceUsage_SourceManager_Membuffer_MMap,
5334                               (unsigned long) srcBufs.mmap_bytes);
5335
5336  // How much memory is being used by the ExternalASTSource?
5337  if (ExternalASTSource *esrc = astContext.getExternalSource()) {
5338    const ExternalASTSource::MemoryBufferSizes &sizes =
5339      esrc->getMemoryBufferSizes();
5340
5341    createCXTUResourceUsageEntry(*entries,
5342      CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc,
5343                                 (unsigned long) sizes.malloc_bytes);
5344    createCXTUResourceUsageEntry(*entries,
5345      CXTUResourceUsage_ExternalASTSource_Membuffer_MMap,
5346                                 (unsigned long) sizes.mmap_bytes);
5347  }
5348
5349  // How much memory is being used by the Preprocessor?
5350  Preprocessor &pp = astUnit->getPreprocessor();
5351  const llvm::BumpPtrAllocator &ppAlloc = pp.getPreprocessorAllocator();
5352  createCXTUResourceUsageEntry(*entries,
5353                               CXTUResourceUsage_Preprocessor,
5354                               ppAlloc.getTotalMemory());
5355
5356  if (PreprocessingRecord *pRec = pp.getPreprocessingRecord()) {
5357    createCXTUResourceUsageEntry(*entries,
5358                                 CXTUResourceUsage_PreprocessingRecord,
5359                                 pRec->getTotalMemory());
5360  }
5361
5362
5363  CXTUResourceUsage usage = { (void*) entries.get(),
5364                            (unsigned) entries->size(),
5365                            entries->size() ? &(*entries)[0] : 0 };
5366  entries.take();
5367  return usage;
5368}
5369
5370void clang_disposeCXTUResourceUsage(CXTUResourceUsage usage) {
5371  if (usage.data)
5372    delete (MemUsageEntries*) usage.data;
5373}
5374
5375} // end extern "C"
5376
5377void clang::PrintLibclangResourceUsage(CXTranslationUnit TU) {
5378  CXTUResourceUsage Usage = clang_getCXTUResourceUsage(TU);
5379  for (unsigned I = 0; I != Usage.numEntries; ++I)
5380    fprintf(stderr, "  %s: %lu\n",
5381            clang_getTUResourceUsageName(Usage.entries[I].kind),
5382            Usage.entries[I].amount);
5383
5384  clang_disposeCXTUResourceUsage(Usage);
5385}
5386
5387//===----------------------------------------------------------------------===//
5388// Misc. utility functions.
5389//===----------------------------------------------------------------------===//
5390
5391/// Default to using an 8 MB stack size on "safety" threads.
5392static unsigned SafetyStackThreadSize = 8 << 20;
5393
5394namespace clang {
5395
5396bool RunSafely(llvm::CrashRecoveryContext &CRC,
5397               void (*Fn)(void*), void *UserData,
5398               unsigned Size) {
5399  if (!Size)
5400    Size = GetSafetyThreadStackSize();
5401  if (Size)
5402    return CRC.RunSafelyOnThread(Fn, UserData, Size);
5403  return CRC.RunSafely(Fn, UserData);
5404}
5405
5406unsigned GetSafetyThreadStackSize() {
5407  return SafetyStackThreadSize;
5408}
5409
5410void SetSafetyThreadStackSize(unsigned Value) {
5411  SafetyStackThreadSize = Value;
5412}
5413
5414}
5415
5416extern "C" {
5417
5418CXString clang_getClangVersion() {
5419  return createCXString(getClangFullVersion());
5420}
5421
5422} // end: extern "C"
5423
5424