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