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