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