CIndex.cpp revision b0c3e0909bb04af0bfb82ad01ab6909649d68cca 
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, ASTTemplateArgumentListInfo,
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 ASTTemplateArgumentListInfo *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 ASTTemplateArgumentListInfo *A) {
1803  if (A)
1804    WL.push_back(ExplicitTemplateArgsVisit(
1805                        const_cast<ASTTemplateArgumentListInfo*>(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 ASTTemplateArgumentListInfo *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 ASTTemplateArgumentListInfo *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  *BestCursor = cursor;
3472  return CXChildVisit_Recurse;
3473}
3474
3475CXCursor clang_getCursor(CXTranslationUnit TU, CXSourceLocation Loc) {
3476  if (!TU)
3477    return clang_getNullCursor();
3478
3479  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
3480  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
3481
3482  // Translate the given source location to make it point at the beginning of
3483  // the token under the cursor.
3484  SourceLocation SLoc = cxloc::translateSourceLocation(Loc);
3485
3486  // Guard against an invalid SourceLocation, or we may assert in one
3487  // of the following calls.
3488  if (SLoc.isInvalid())
3489    return clang_getNullCursor();
3490
3491  bool Logging = getenv("LIBCLANG_LOGGING");
3492  SLoc = Lexer::GetBeginningOfToken(SLoc, CXXUnit->getSourceManager(),
3493                                    CXXUnit->getASTContext().getLangOptions());
3494
3495  CXCursor Result = MakeCXCursorInvalid(CXCursor_NoDeclFound);
3496  if (SLoc.isValid()) {
3497    // FIXME: Would be great to have a "hint" cursor, then walk from that
3498    // hint cursor upward until we find a cursor whose source range encloses
3499    // the region of interest, rather than starting from the translation unit.
3500    GetCursorData ResultData(CXXUnit->getSourceManager(), SLoc, Result);
3501    CXCursor Parent = clang_getTranslationUnitCursor(TU);
3502    CursorVisitor CursorVis(TU, GetCursorVisitor, &ResultData,
3503                            /*VisitPreprocessorLast=*/true,
3504                            SourceLocation(SLoc));
3505    CursorVis.VisitChildren(Parent);
3506  }
3507
3508  if (Logging) {
3509    CXFile SearchFile;
3510    unsigned SearchLine, SearchColumn;
3511    CXFile ResultFile;
3512    unsigned ResultLine, ResultColumn;
3513    CXString SearchFileName, ResultFileName, KindSpelling, USR;
3514    const char *IsDef = clang_isCursorDefinition(Result)? " (Definition)" : "";
3515    CXSourceLocation ResultLoc = clang_getCursorLocation(Result);
3516
3517    clang_getExpansionLocation(Loc, &SearchFile, &SearchLine, &SearchColumn, 0);
3518    clang_getExpansionLocation(ResultLoc, &ResultFile, &ResultLine,
3519                               &ResultColumn, 0);
3520    SearchFileName = clang_getFileName(SearchFile);
3521    ResultFileName = clang_getFileName(ResultFile);
3522    KindSpelling = clang_getCursorKindSpelling(Result.kind);
3523    USR = clang_getCursorUSR(Result);
3524    fprintf(stderr, "clang_getCursor(%s:%d:%d) = %s(%s:%d:%d):%s%s\n",
3525            clang_getCString(SearchFileName), SearchLine, SearchColumn,
3526            clang_getCString(KindSpelling),
3527            clang_getCString(ResultFileName), ResultLine, ResultColumn,
3528            clang_getCString(USR), IsDef);
3529    clang_disposeString(SearchFileName);
3530    clang_disposeString(ResultFileName);
3531    clang_disposeString(KindSpelling);
3532    clang_disposeString(USR);
3533
3534    CXCursor Definition = clang_getCursorDefinition(Result);
3535    if (!clang_equalCursors(Definition, clang_getNullCursor())) {
3536      CXSourceLocation DefinitionLoc = clang_getCursorLocation(Definition);
3537      CXString DefinitionKindSpelling
3538                                = clang_getCursorKindSpelling(Definition.kind);
3539      CXFile DefinitionFile;
3540      unsigned DefinitionLine, DefinitionColumn;
3541      clang_getExpansionLocation(DefinitionLoc, &DefinitionFile,
3542                                 &DefinitionLine, &DefinitionColumn, 0);
3543      CXString DefinitionFileName = clang_getFileName(DefinitionFile);
3544      fprintf(stderr, "  -> %s(%s:%d:%d)\n",
3545              clang_getCString(DefinitionKindSpelling),
3546              clang_getCString(DefinitionFileName),
3547              DefinitionLine, DefinitionColumn);
3548      clang_disposeString(DefinitionFileName);
3549      clang_disposeString(DefinitionKindSpelling);
3550    }
3551  }
3552
3553  return Result;
3554}
3555
3556CXCursor clang_getNullCursor(void) {
3557  return MakeCXCursorInvalid(CXCursor_InvalidFile);
3558}
3559
3560unsigned clang_equalCursors(CXCursor X, CXCursor Y) {
3561  return X == Y;
3562}
3563
3564unsigned clang_hashCursor(CXCursor C) {
3565  unsigned Index = 0;
3566  if (clang_isExpression(C.kind) || clang_isStatement(C.kind))
3567    Index = 1;
3568
3569  return llvm::DenseMapInfo<std::pair<unsigned, void*> >::getHashValue(
3570                                        std::make_pair(C.kind, C.data[Index]));
3571}
3572
3573unsigned clang_isInvalid(enum CXCursorKind K) {
3574  return K >= CXCursor_FirstInvalid && K <= CXCursor_LastInvalid;
3575}
3576
3577unsigned clang_isDeclaration(enum CXCursorKind K) {
3578  return K >= CXCursor_FirstDecl && K <= CXCursor_LastDecl;
3579}
3580
3581unsigned clang_isReference(enum CXCursorKind K) {
3582  return K >= CXCursor_FirstRef && K <= CXCursor_LastRef;
3583}
3584
3585unsigned clang_isExpression(enum CXCursorKind K) {
3586  return K >= CXCursor_FirstExpr && K <= CXCursor_LastExpr;
3587}
3588
3589unsigned clang_isStatement(enum CXCursorKind K) {
3590  return K >= CXCursor_FirstStmt && K <= CXCursor_LastStmt;
3591}
3592
3593unsigned clang_isAttribute(enum CXCursorKind K) {
3594    return K >= CXCursor_FirstAttr && K <= CXCursor_LastAttr;
3595}
3596
3597unsigned clang_isTranslationUnit(enum CXCursorKind K) {
3598  return K == CXCursor_TranslationUnit;
3599}
3600
3601unsigned clang_isPreprocessing(enum CXCursorKind K) {
3602  return K >= CXCursor_FirstPreprocessing && K <= CXCursor_LastPreprocessing;
3603}
3604
3605unsigned clang_isUnexposed(enum CXCursorKind K) {
3606  switch (K) {
3607    case CXCursor_UnexposedDecl:
3608    case CXCursor_UnexposedExpr:
3609    case CXCursor_UnexposedStmt:
3610    case CXCursor_UnexposedAttr:
3611      return true;
3612    default:
3613      return false;
3614  }
3615}
3616
3617CXCursorKind clang_getCursorKind(CXCursor C) {
3618  return C.kind;
3619}
3620
3621CXSourceLocation clang_getCursorLocation(CXCursor C) {
3622  if (clang_isReference(C.kind)) {
3623    switch (C.kind) {
3624    case CXCursor_ObjCSuperClassRef: {
3625      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3626        = getCursorObjCSuperClassRef(C);
3627      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3628    }
3629
3630    case CXCursor_ObjCProtocolRef: {
3631      std::pair<ObjCProtocolDecl *, SourceLocation> P
3632        = getCursorObjCProtocolRef(C);
3633      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3634    }
3635
3636    case CXCursor_ObjCClassRef: {
3637      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3638        = getCursorObjCClassRef(C);
3639      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3640    }
3641
3642    case CXCursor_TypeRef: {
3643      std::pair<TypeDecl *, SourceLocation> P = getCursorTypeRef(C);
3644      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3645    }
3646
3647    case CXCursor_TemplateRef: {
3648      std::pair<TemplateDecl *, SourceLocation> P = getCursorTemplateRef(C);
3649      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3650    }
3651
3652    case CXCursor_NamespaceRef: {
3653      std::pair<NamedDecl *, SourceLocation> P = getCursorNamespaceRef(C);
3654      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3655    }
3656
3657    case CXCursor_MemberRef: {
3658      std::pair<FieldDecl *, SourceLocation> P = getCursorMemberRef(C);
3659      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3660    }
3661
3662    case CXCursor_CXXBaseSpecifier: {
3663      CXXBaseSpecifier *BaseSpec = getCursorCXXBaseSpecifier(C);
3664      if (!BaseSpec)
3665        return clang_getNullLocation();
3666
3667      if (TypeSourceInfo *TSInfo = BaseSpec->getTypeSourceInfo())
3668        return cxloc::translateSourceLocation(getCursorContext(C),
3669                                            TSInfo->getTypeLoc().getBeginLoc());
3670
3671      return cxloc::translateSourceLocation(getCursorContext(C),
3672                                        BaseSpec->getSourceRange().getBegin());
3673    }
3674
3675    case CXCursor_LabelRef: {
3676      std::pair<LabelStmt *, SourceLocation> P = getCursorLabelRef(C);
3677      return cxloc::translateSourceLocation(getCursorContext(C), P.second);
3678    }
3679
3680    case CXCursor_OverloadedDeclRef:
3681      return cxloc::translateSourceLocation(getCursorContext(C),
3682                                          getCursorOverloadedDeclRef(C).second);
3683
3684    default:
3685      // FIXME: Need a way to enumerate all non-reference cases.
3686      llvm_unreachable("Missed a reference kind");
3687    }
3688  }
3689
3690  if (clang_isExpression(C.kind))
3691    return cxloc::translateSourceLocation(getCursorContext(C),
3692                                   getLocationFromExpr(getCursorExpr(C)));
3693
3694  if (clang_isStatement(C.kind))
3695    return cxloc::translateSourceLocation(getCursorContext(C),
3696                                          getCursorStmt(C)->getLocStart());
3697
3698  if (C.kind == CXCursor_PreprocessingDirective) {
3699    SourceLocation L = cxcursor::getCursorPreprocessingDirective(C).getBegin();
3700    return cxloc::translateSourceLocation(getCursorContext(C), L);
3701  }
3702
3703  if (C.kind == CXCursor_MacroExpansion) {
3704    SourceLocation L
3705      = cxcursor::getCursorMacroExpansion(C)->getSourceRange().getBegin();
3706    return cxloc::translateSourceLocation(getCursorContext(C), L);
3707  }
3708
3709  if (C.kind == CXCursor_MacroDefinition) {
3710    SourceLocation L = cxcursor::getCursorMacroDefinition(C)->getLocation();
3711    return cxloc::translateSourceLocation(getCursorContext(C), L);
3712  }
3713
3714  if (C.kind == CXCursor_InclusionDirective) {
3715    SourceLocation L
3716      = cxcursor::getCursorInclusionDirective(C)->getSourceRange().getBegin();
3717    return cxloc::translateSourceLocation(getCursorContext(C), L);
3718  }
3719
3720  if (C.kind < CXCursor_FirstDecl || C.kind > CXCursor_LastDecl)
3721    return clang_getNullLocation();
3722
3723  Decl *D = getCursorDecl(C);
3724  SourceLocation Loc = D->getLocation();
3725  if (ObjCInterfaceDecl *Class = dyn_cast<ObjCInterfaceDecl>(D))
3726    Loc = Class->getClassLoc();
3727  // FIXME: Multiple variables declared in a single declaration
3728  // currently lack the information needed to correctly determine their
3729  // ranges when accounting for the type-specifier.  We use context
3730  // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3731  // and if so, whether it is the first decl.
3732  if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3733    if (!cxcursor::isFirstInDeclGroup(C))
3734      Loc = VD->getLocation();
3735  }
3736
3737  return cxloc::translateSourceLocation(getCursorContext(C), Loc);
3738}
3739
3740} // end extern "C"
3741
3742static SourceRange getRawCursorExtent(CXCursor C) {
3743  if (clang_isReference(C.kind)) {
3744    switch (C.kind) {
3745    case CXCursor_ObjCSuperClassRef:
3746      return  getCursorObjCSuperClassRef(C).second;
3747
3748    case CXCursor_ObjCProtocolRef:
3749      return getCursorObjCProtocolRef(C).second;
3750
3751    case CXCursor_ObjCClassRef:
3752      return getCursorObjCClassRef(C).second;
3753
3754    case CXCursor_TypeRef:
3755      return getCursorTypeRef(C).second;
3756
3757    case CXCursor_TemplateRef:
3758      return getCursorTemplateRef(C).second;
3759
3760    case CXCursor_NamespaceRef:
3761      return getCursorNamespaceRef(C).second;
3762
3763    case CXCursor_MemberRef:
3764      return getCursorMemberRef(C).second;
3765
3766    case CXCursor_CXXBaseSpecifier:
3767      return getCursorCXXBaseSpecifier(C)->getSourceRange();
3768
3769    case CXCursor_LabelRef:
3770      return getCursorLabelRef(C).second;
3771
3772    case CXCursor_OverloadedDeclRef:
3773      return getCursorOverloadedDeclRef(C).second;
3774
3775    default:
3776      // FIXME: Need a way to enumerate all non-reference cases.
3777      llvm_unreachable("Missed a reference kind");
3778    }
3779  }
3780
3781  if (clang_isExpression(C.kind))
3782    return getCursorExpr(C)->getSourceRange();
3783
3784  if (clang_isStatement(C.kind))
3785    return getCursorStmt(C)->getSourceRange();
3786
3787  if (clang_isAttribute(C.kind))
3788    return getCursorAttr(C)->getRange();
3789
3790  if (C.kind == CXCursor_PreprocessingDirective)
3791    return cxcursor::getCursorPreprocessingDirective(C);
3792
3793  if (C.kind == CXCursor_MacroExpansion)
3794    return cxcursor::getCursorMacroExpansion(C)->getSourceRange();
3795
3796  if (C.kind == CXCursor_MacroDefinition)
3797    return cxcursor::getCursorMacroDefinition(C)->getSourceRange();
3798
3799  if (C.kind == CXCursor_InclusionDirective)
3800    return cxcursor::getCursorInclusionDirective(C)->getSourceRange();
3801
3802  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3803    Decl *D = cxcursor::getCursorDecl(C);
3804    SourceRange R = D->getSourceRange();
3805    // FIXME: Multiple variables declared in a single declaration
3806    // currently lack the information needed to correctly determine their
3807    // ranges when accounting for the type-specifier.  We use context
3808    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3809    // and if so, whether it is the first decl.
3810    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3811      if (!cxcursor::isFirstInDeclGroup(C))
3812        R.setBegin(VD->getLocation());
3813    }
3814    return R;
3815  }
3816  return SourceRange();
3817}
3818
3819/// \brief Retrieves the "raw" cursor extent, which is then extended to include
3820/// the decl-specifier-seq for declarations.
3821static SourceRange getFullCursorExtent(CXCursor C, SourceManager &SrcMgr) {
3822  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3823    Decl *D = cxcursor::getCursorDecl(C);
3824    SourceRange R = D->getSourceRange();
3825
3826    // Adjust the start of the location for declarations preceded by
3827    // declaration specifiers.
3828    SourceLocation StartLoc;
3829    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
3830      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
3831        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3832    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
3833      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
3834        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3835    }
3836
3837    if (StartLoc.isValid() && R.getBegin().isValid() &&
3838        SrcMgr.isBeforeInTranslationUnit(StartLoc, R.getBegin()))
3839      R.setBegin(StartLoc);
3840
3841    // FIXME: Multiple variables declared in a single declaration
3842    // currently lack the information needed to correctly determine their
3843    // ranges when accounting for the type-specifier.  We use context
3844    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3845    // and if so, whether it is the first decl.
3846    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3847      if (!cxcursor::isFirstInDeclGroup(C))
3848        R.setBegin(VD->getLocation());
3849    }
3850
3851    return R;
3852  }
3853
3854  return getRawCursorExtent(C);
3855}
3856
3857extern "C" {
3858
3859CXSourceRange clang_getCursorExtent(CXCursor C) {
3860  SourceRange R = getRawCursorExtent(C);
3861  if (R.isInvalid())
3862    return clang_getNullRange();
3863
3864  return cxloc::translateSourceRange(getCursorContext(C), R);
3865}
3866
3867CXCursor clang_getCursorReferenced(CXCursor C) {
3868  if (clang_isInvalid(C.kind))
3869    return clang_getNullCursor();
3870
3871  CXTranslationUnit tu = getCursorTU(C);
3872  if (clang_isDeclaration(C.kind)) {
3873    Decl *D = getCursorDecl(C);
3874    if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
3875      return MakeCursorOverloadedDeclRef(Using, D->getLocation(), tu);
3876    if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
3877      return MakeCursorOverloadedDeclRef(Classes, D->getLocation(), tu);
3878    if (ObjCForwardProtocolDecl *Protocols
3879                                        = dyn_cast<ObjCForwardProtocolDecl>(D))
3880      return MakeCursorOverloadedDeclRef(Protocols, D->getLocation(), tu);
3881    if (ObjCPropertyImplDecl *PropImpl =dyn_cast<ObjCPropertyImplDecl>(D))
3882      if (ObjCPropertyDecl *Property = PropImpl->getPropertyDecl())
3883        return MakeCXCursor(Property, tu);
3884
3885    return C;
3886  }
3887
3888  if (clang_isExpression(C.kind)) {
3889    Expr *E = getCursorExpr(C);
3890    Decl *D = getDeclFromExpr(E);
3891    if (D)
3892      return MakeCXCursor(D, tu);
3893
3894    if (OverloadExpr *Ovl = dyn_cast_or_null<OverloadExpr>(E))
3895      return MakeCursorOverloadedDeclRef(Ovl, tu);
3896
3897    return clang_getNullCursor();
3898  }
3899
3900  if (clang_isStatement(C.kind)) {
3901    Stmt *S = getCursorStmt(C);
3902    if (GotoStmt *Goto = dyn_cast_or_null<GotoStmt>(S))
3903      if (LabelDecl *label = Goto->getLabel())
3904        if (LabelStmt *labelS = label->getStmt())
3905        return MakeCXCursor(labelS, getCursorDecl(C), tu);
3906
3907    return clang_getNullCursor();
3908  }
3909
3910  if (C.kind == CXCursor_MacroExpansion) {
3911    if (MacroDefinition *Def = getCursorMacroExpansion(C)->getDefinition())
3912      return MakeMacroDefinitionCursor(Def, tu);
3913  }
3914
3915  if (!clang_isReference(C.kind))
3916    return clang_getNullCursor();
3917
3918  switch (C.kind) {
3919    case CXCursor_ObjCSuperClassRef:
3920      return MakeCXCursor(getCursorObjCSuperClassRef(C).first, tu);
3921
3922    case CXCursor_ObjCProtocolRef: {
3923      return MakeCXCursor(getCursorObjCProtocolRef(C).first, tu);
3924
3925    case CXCursor_ObjCClassRef:
3926      return MakeCXCursor(getCursorObjCClassRef(C).first, tu );
3927
3928    case CXCursor_TypeRef:
3929      return MakeCXCursor(getCursorTypeRef(C).first, tu );
3930
3931    case CXCursor_TemplateRef:
3932      return MakeCXCursor(getCursorTemplateRef(C).first, tu );
3933
3934    case CXCursor_NamespaceRef:
3935      return MakeCXCursor(getCursorNamespaceRef(C).first, tu );
3936
3937    case CXCursor_MemberRef:
3938      return MakeCXCursor(getCursorMemberRef(C).first, tu );
3939
3940    case CXCursor_CXXBaseSpecifier: {
3941      CXXBaseSpecifier *B = cxcursor::getCursorCXXBaseSpecifier(C);
3942      return clang_getTypeDeclaration(cxtype::MakeCXType(B->getType(),
3943                                                         tu ));
3944    }
3945
3946    case CXCursor_LabelRef:
3947      // FIXME: We end up faking the "parent" declaration here because we
3948      // don't want to make CXCursor larger.
3949      return MakeCXCursor(getCursorLabelRef(C).first,
3950               static_cast<ASTUnit*>(tu->TUData)->getASTContext()
3951                          .getTranslationUnitDecl(),
3952                          tu);
3953
3954    case CXCursor_OverloadedDeclRef:
3955      return C;
3956
3957    default:
3958      // We would prefer to enumerate all non-reference cursor kinds here.
3959      llvm_unreachable("Unhandled reference cursor kind");
3960      break;
3961    }
3962  }
3963
3964  return clang_getNullCursor();
3965}
3966
3967CXCursor clang_getCursorDefinition(CXCursor C) {
3968  if (clang_isInvalid(C.kind))
3969    return clang_getNullCursor();
3970
3971  CXTranslationUnit TU = getCursorTU(C);
3972
3973  bool WasReference = false;
3974  if (clang_isReference(C.kind) || clang_isExpression(C.kind)) {
3975    C = clang_getCursorReferenced(C);
3976    WasReference = true;
3977  }
3978
3979  if (C.kind == CXCursor_MacroExpansion)
3980    return clang_getCursorReferenced(C);
3981
3982  if (!clang_isDeclaration(C.kind))
3983    return clang_getNullCursor();
3984
3985  Decl *D = getCursorDecl(C);
3986  if (!D)
3987    return clang_getNullCursor();
3988
3989  switch (D->getKind()) {
3990  // Declaration kinds that don't really separate the notions of
3991  // declaration and definition.
3992  case Decl::Namespace:
3993  case Decl::Typedef:
3994  case Decl::TypeAlias:
3995  case Decl::TypeAliasTemplate:
3996  case Decl::TemplateTypeParm:
3997  case Decl::EnumConstant:
3998  case Decl::Field:
3999  case Decl::IndirectField:
4000  case Decl::ObjCIvar:
4001  case Decl::ObjCAtDefsField:
4002  case Decl::ImplicitParam:
4003  case Decl::ParmVar:
4004  case Decl::NonTypeTemplateParm:
4005  case Decl::TemplateTemplateParm:
4006  case Decl::ObjCCategoryImpl:
4007  case Decl::ObjCImplementation:
4008  case Decl::AccessSpec:
4009  case Decl::LinkageSpec:
4010  case Decl::ObjCPropertyImpl:
4011  case Decl::FileScopeAsm:
4012  case Decl::StaticAssert:
4013  case Decl::Block:
4014  case Decl::Label:  // FIXME: Is this right??
4015  case Decl::ClassScopeFunctionSpecialization:
4016    return C;
4017
4018  // Declaration kinds that don't make any sense here, but are
4019  // nonetheless harmless.
4020  case Decl::TranslationUnit:
4021    break;
4022
4023  // Declaration kinds for which the definition is not resolvable.
4024  case Decl::UnresolvedUsingTypename:
4025  case Decl::UnresolvedUsingValue:
4026    break;
4027
4028  case Decl::UsingDirective:
4029    return MakeCXCursor(cast<UsingDirectiveDecl>(D)->getNominatedNamespace(),
4030                        TU);
4031
4032  case Decl::NamespaceAlias:
4033    return MakeCXCursor(cast<NamespaceAliasDecl>(D)->getNamespace(), TU);
4034
4035  case Decl::Enum:
4036  case Decl::Record:
4037  case Decl::CXXRecord:
4038  case Decl::ClassTemplateSpecialization:
4039  case Decl::ClassTemplatePartialSpecialization:
4040    if (TagDecl *Def = cast<TagDecl>(D)->getDefinition())
4041      return MakeCXCursor(Def, TU);
4042    return clang_getNullCursor();
4043
4044  case Decl::Function:
4045  case Decl::CXXMethod:
4046  case Decl::CXXConstructor:
4047  case Decl::CXXDestructor:
4048  case Decl::CXXConversion: {
4049    const FunctionDecl *Def = 0;
4050    if (cast<FunctionDecl>(D)->getBody(Def))
4051      return MakeCXCursor(const_cast<FunctionDecl *>(Def), TU);
4052    return clang_getNullCursor();
4053  }
4054
4055  case Decl::Var: {
4056    // Ask the variable if it has a definition.
4057    if (VarDecl *Def = cast<VarDecl>(D)->getDefinition())
4058      return MakeCXCursor(Def, TU);
4059    return clang_getNullCursor();
4060  }
4061
4062  case Decl::FunctionTemplate: {
4063    const FunctionDecl *Def = 0;
4064    if (cast<FunctionTemplateDecl>(D)->getTemplatedDecl()->getBody(Def))
4065      return MakeCXCursor(Def->getDescribedFunctionTemplate(), TU);
4066    return clang_getNullCursor();
4067  }
4068
4069  case Decl::ClassTemplate: {
4070    if (RecordDecl *Def = cast<ClassTemplateDecl>(D)->getTemplatedDecl()
4071                                                            ->getDefinition())
4072      return MakeCXCursor(cast<CXXRecordDecl>(Def)->getDescribedClassTemplate(),
4073                          TU);
4074    return clang_getNullCursor();
4075  }
4076
4077  case Decl::Using:
4078    return MakeCursorOverloadedDeclRef(cast<UsingDecl>(D),
4079                                       D->getLocation(), TU);
4080
4081  case Decl::UsingShadow:
4082    return clang_getCursorDefinition(
4083                       MakeCXCursor(cast<UsingShadowDecl>(D)->getTargetDecl(),
4084                                    TU));
4085
4086  case Decl::ObjCMethod: {
4087    ObjCMethodDecl *Method = cast<ObjCMethodDecl>(D);
4088    if (Method->isThisDeclarationADefinition())
4089      return C;
4090
4091    // Dig out the method definition in the associated
4092    // @implementation, if we have it.
4093    // FIXME: The ASTs should make finding the definition easier.
4094    if (ObjCInterfaceDecl *Class
4095                       = dyn_cast<ObjCInterfaceDecl>(Method->getDeclContext()))
4096      if (ObjCImplementationDecl *ClassImpl = Class->getImplementation())
4097        if (ObjCMethodDecl *Def = ClassImpl->getMethod(Method->getSelector(),
4098                                                  Method->isInstanceMethod()))
4099          if (Def->isThisDeclarationADefinition())
4100            return MakeCXCursor(Def, TU);
4101
4102    return clang_getNullCursor();
4103  }
4104
4105  case Decl::ObjCCategory:
4106    if (ObjCCategoryImplDecl *Impl
4107                               = cast<ObjCCategoryDecl>(D)->getImplementation())
4108      return MakeCXCursor(Impl, TU);
4109    return clang_getNullCursor();
4110
4111  case Decl::ObjCProtocol:
4112    if (!cast<ObjCProtocolDecl>(D)->isForwardDecl())
4113      return C;
4114    return clang_getNullCursor();
4115
4116  case Decl::ObjCInterface:
4117    // There are two notions of a "definition" for an Objective-C
4118    // class: the interface and its implementation. When we resolved a
4119    // reference to an Objective-C class, produce the @interface as
4120    // the definition; when we were provided with the interface,
4121    // produce the @implementation as the definition.
4122    if (WasReference) {
4123      if (!cast<ObjCInterfaceDecl>(D)->isForwardDecl())
4124        return C;
4125    } else if (ObjCImplementationDecl *Impl
4126                              = cast<ObjCInterfaceDecl>(D)->getImplementation())
4127      return MakeCXCursor(Impl, TU);
4128    return clang_getNullCursor();
4129
4130  case Decl::ObjCProperty:
4131    // FIXME: We don't really know where to find the
4132    // ObjCPropertyImplDecls that implement this property.
4133    return clang_getNullCursor();
4134
4135  case Decl::ObjCCompatibleAlias:
4136    if (ObjCInterfaceDecl *Class
4137          = cast<ObjCCompatibleAliasDecl>(D)->getClassInterface())
4138      if (!Class->isForwardDecl())
4139        return MakeCXCursor(Class, TU);
4140
4141    return clang_getNullCursor();
4142
4143  case Decl::ObjCForwardProtocol:
4144    return MakeCursorOverloadedDeclRef(cast<ObjCForwardProtocolDecl>(D),
4145                                       D->getLocation(), TU);
4146
4147  case Decl::ObjCClass:
4148    return MakeCursorOverloadedDeclRef(cast<ObjCClassDecl>(D), D->getLocation(),
4149                                       TU);
4150
4151  case Decl::Friend:
4152    if (NamedDecl *Friend = cast<FriendDecl>(D)->getFriendDecl())
4153      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4154    return clang_getNullCursor();
4155
4156  case Decl::FriendTemplate:
4157    if (NamedDecl *Friend = cast<FriendTemplateDecl>(D)->getFriendDecl())
4158      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4159    return clang_getNullCursor();
4160  }
4161
4162  return clang_getNullCursor();
4163}
4164
4165unsigned clang_isCursorDefinition(CXCursor C) {
4166  if (!clang_isDeclaration(C.kind))
4167    return 0;
4168
4169  return clang_getCursorDefinition(C) == C;
4170}
4171
4172CXCursor clang_getCanonicalCursor(CXCursor C) {
4173  if (!clang_isDeclaration(C.kind))
4174    return C;
4175
4176  if (Decl *D = getCursorDecl(C)) {
4177    if (ObjCCategoryImplDecl *CatImplD = dyn_cast<ObjCCategoryImplDecl>(D))
4178      if (ObjCCategoryDecl *CatD = CatImplD->getCategoryDecl())
4179        return MakeCXCursor(CatD, getCursorTU(C));
4180
4181    if (ObjCImplDecl *ImplD = dyn_cast<ObjCImplDecl>(D))
4182      if (ObjCInterfaceDecl *IFD = ImplD->getClassInterface())
4183        return MakeCXCursor(IFD, getCursorTU(C));
4184
4185    return MakeCXCursor(D->getCanonicalDecl(), getCursorTU(C));
4186  }
4187
4188  return C;
4189}
4190
4191unsigned clang_getNumOverloadedDecls(CXCursor C) {
4192  if (C.kind != CXCursor_OverloadedDeclRef)
4193    return 0;
4194
4195  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
4196  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4197    return E->getNumDecls();
4198
4199  if (OverloadedTemplateStorage *S
4200                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4201    return S->size();
4202
4203  Decl *D = Storage.get<Decl*>();
4204  if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
4205    return Using->shadow_size();
4206  if (isa<ObjCClassDecl>(D))
4207    return 1;
4208  if (ObjCForwardProtocolDecl *Protocols =dyn_cast<ObjCForwardProtocolDecl>(D))
4209    return Protocols->protocol_size();
4210
4211  return 0;
4212}
4213
4214CXCursor clang_getOverloadedDecl(CXCursor cursor, unsigned index) {
4215  if (cursor.kind != CXCursor_OverloadedDeclRef)
4216    return clang_getNullCursor();
4217
4218  if (index >= clang_getNumOverloadedDecls(cursor))
4219    return clang_getNullCursor();
4220
4221  CXTranslationUnit TU = getCursorTU(cursor);
4222  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(cursor).first;
4223  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4224    return MakeCXCursor(E->decls_begin()[index], TU);
4225
4226  if (OverloadedTemplateStorage *S
4227                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4228    return MakeCXCursor(S->begin()[index], TU);
4229
4230  Decl *D = Storage.get<Decl*>();
4231  if (UsingDecl *Using = dyn_cast<UsingDecl>(D)) {
4232    // FIXME: This is, unfortunately, linear time.
4233    UsingDecl::shadow_iterator Pos = Using->shadow_begin();
4234    std::advance(Pos, index);
4235    return MakeCXCursor(cast<UsingShadowDecl>(*Pos)->getTargetDecl(), TU);
4236  }
4237  if (ObjCClassDecl *Classes = dyn_cast<ObjCClassDecl>(D))
4238    return MakeCXCursor(Classes->getForwardInterfaceDecl(), TU);
4239  if (ObjCForwardProtocolDecl *Protocols = dyn_cast<ObjCForwardProtocolDecl>(D))
4240    return MakeCXCursor(Protocols->protocol_begin()[index], TU);
4241
4242  return clang_getNullCursor();
4243}
4244
4245void clang_getDefinitionSpellingAndExtent(CXCursor C,
4246                                          const char **startBuf,
4247                                          const char **endBuf,
4248                                          unsigned *startLine,
4249                                          unsigned *startColumn,
4250                                          unsigned *endLine,
4251                                          unsigned *endColumn) {
4252  assert(getCursorDecl(C) && "CXCursor has null decl");
4253  NamedDecl *ND = static_cast<NamedDecl *>(getCursorDecl(C));
4254  FunctionDecl *FD = dyn_cast<FunctionDecl>(ND);
4255  CompoundStmt *Body = dyn_cast<CompoundStmt>(FD->getBody());
4256
4257  SourceManager &SM = FD->getASTContext().getSourceManager();
4258  *startBuf = SM.getCharacterData(Body->getLBracLoc());
4259  *endBuf = SM.getCharacterData(Body->getRBracLoc());
4260  *startLine = SM.getSpellingLineNumber(Body->getLBracLoc());
4261  *startColumn = SM.getSpellingColumnNumber(Body->getLBracLoc());
4262  *endLine = SM.getSpellingLineNumber(Body->getRBracLoc());
4263  *endColumn = SM.getSpellingColumnNumber(Body->getRBracLoc());
4264}
4265
4266
4267CXSourceRange clang_getCursorReferenceNameRange(CXCursor C, unsigned NameFlags,
4268                                                unsigned PieceIndex) {
4269  RefNamePieces Pieces;
4270
4271  switch (C.kind) {
4272  case CXCursor_MemberRefExpr:
4273    if (MemberExpr *E = dyn_cast<MemberExpr>(getCursorExpr(C)))
4274      Pieces = buildPieces(NameFlags, true, E->getMemberNameInfo(),
4275                           E->getQualifierLoc().getSourceRange());
4276    break;
4277
4278  case CXCursor_DeclRefExpr:
4279    if (DeclRefExpr *E = dyn_cast<DeclRefExpr>(getCursorExpr(C)))
4280      Pieces = buildPieces(NameFlags, false, E->getNameInfo(),
4281                           E->getQualifierLoc().getSourceRange(),
4282                           E->getExplicitTemplateArgsOpt());
4283    break;
4284
4285  case CXCursor_CallExpr:
4286    if (CXXOperatorCallExpr *OCE =
4287        dyn_cast<CXXOperatorCallExpr>(getCursorExpr(C))) {
4288      Expr *Callee = OCE->getCallee();
4289      if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Callee))
4290        Callee = ICE->getSubExpr();
4291
4292      if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Callee))
4293        Pieces = buildPieces(NameFlags, false, DRE->getNameInfo(),
4294                             DRE->getQualifierLoc().getSourceRange());
4295    }
4296    break;
4297
4298  default:
4299    break;
4300  }
4301
4302  if (Pieces.empty()) {
4303    if (PieceIndex == 0)
4304      return clang_getCursorExtent(C);
4305  } else if (PieceIndex < Pieces.size()) {
4306      SourceRange R = Pieces[PieceIndex];
4307      if (R.isValid())
4308        return cxloc::translateSourceRange(getCursorContext(C), R);
4309  }
4310
4311  return clang_getNullRange();
4312}
4313
4314void clang_enableStackTraces(void) {
4315  llvm::sys::PrintStackTraceOnErrorSignal();
4316}
4317
4318void clang_executeOnThread(void (*fn)(void*), void *user_data,
4319                           unsigned stack_size) {
4320  llvm::llvm_execute_on_thread(fn, user_data, stack_size);
4321}
4322
4323} // end: extern "C"
4324
4325//===----------------------------------------------------------------------===//
4326// Token-based Operations.
4327//===----------------------------------------------------------------------===//
4328
4329/* CXToken layout:
4330 *   int_data[0]: a CXTokenKind
4331 *   int_data[1]: starting token location
4332 *   int_data[2]: token length
4333 *   int_data[3]: reserved
4334 *   ptr_data: for identifiers and keywords, an IdentifierInfo*.
4335 *   otherwise unused.
4336 */
4337extern "C" {
4338
4339CXTokenKind clang_getTokenKind(CXToken CXTok) {
4340  return static_cast<CXTokenKind>(CXTok.int_data[0]);
4341}
4342
4343CXString clang_getTokenSpelling(CXTranslationUnit TU, CXToken CXTok) {
4344  switch (clang_getTokenKind(CXTok)) {
4345  case CXToken_Identifier:
4346  case CXToken_Keyword:
4347    // We know we have an IdentifierInfo*, so use that.
4348    return createCXString(static_cast<IdentifierInfo *>(CXTok.ptr_data)
4349                            ->getNameStart());
4350
4351  case CXToken_Literal: {
4352    // We have stashed the starting pointer in the ptr_data field. Use it.
4353    const char *Text = static_cast<const char *>(CXTok.ptr_data);
4354    return createCXString(StringRef(Text, CXTok.int_data[2]));
4355  }
4356
4357  case CXToken_Punctuation:
4358  case CXToken_Comment:
4359    break;
4360  }
4361
4362  // We have to find the starting buffer pointer the hard way, by
4363  // deconstructing the source location.
4364  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4365  if (!CXXUnit)
4366    return createCXString("");
4367
4368  SourceLocation Loc = SourceLocation::getFromRawEncoding(CXTok.int_data[1]);
4369  std::pair<FileID, unsigned> LocInfo
4370    = CXXUnit->getSourceManager().getDecomposedSpellingLoc(Loc);
4371  bool Invalid = false;
4372  StringRef Buffer
4373    = CXXUnit->getSourceManager().getBufferData(LocInfo.first, &Invalid);
4374  if (Invalid)
4375    return createCXString("");
4376
4377  return createCXString(Buffer.substr(LocInfo.second, CXTok.int_data[2]));
4378}
4379
4380CXSourceLocation clang_getTokenLocation(CXTranslationUnit TU, CXToken CXTok) {
4381  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4382  if (!CXXUnit)
4383    return clang_getNullLocation();
4384
4385  return cxloc::translateSourceLocation(CXXUnit->getASTContext(),
4386                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4387}
4388
4389CXSourceRange clang_getTokenExtent(CXTranslationUnit TU, CXToken CXTok) {
4390  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4391  if (!CXXUnit)
4392    return clang_getNullRange();
4393
4394  return cxloc::translateSourceRange(CXXUnit->getASTContext(),
4395                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4396}
4397
4398void clang_tokenize(CXTranslationUnit TU, CXSourceRange Range,
4399                    CXToken **Tokens, unsigned *NumTokens) {
4400  if (Tokens)
4401    *Tokens = 0;
4402  if (NumTokens)
4403    *NumTokens = 0;
4404
4405  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4406  if (!CXXUnit || !Tokens || !NumTokens)
4407    return;
4408
4409  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
4410
4411  SourceRange R = cxloc::translateCXSourceRange(Range);
4412  if (R.isInvalid())
4413    return;
4414
4415  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4416  std::pair<FileID, unsigned> BeginLocInfo
4417    = SourceMgr.getDecomposedLoc(R.getBegin());
4418  std::pair<FileID, unsigned> EndLocInfo
4419    = SourceMgr.getDecomposedLoc(R.getEnd());
4420
4421  // Cannot tokenize across files.
4422  if (BeginLocInfo.first != EndLocInfo.first)
4423    return;
4424
4425  // Create a lexer
4426  bool Invalid = false;
4427  StringRef Buffer
4428    = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4429  if (Invalid)
4430    return;
4431
4432  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4433            CXXUnit->getASTContext().getLangOptions(),
4434            Buffer.begin(), Buffer.data() + BeginLocInfo.second, Buffer.end());
4435  Lex.SetCommentRetentionState(true);
4436
4437  // Lex tokens until we hit the end of the range.
4438  const char *EffectiveBufferEnd = Buffer.data() + EndLocInfo.second;
4439  SmallVector<CXToken, 32> CXTokens;
4440  Token Tok;
4441  bool previousWasAt = false;
4442  do {
4443    // Lex the next token
4444    Lex.LexFromRawLexer(Tok);
4445    if (Tok.is(tok::eof))
4446      break;
4447
4448    // Initialize the CXToken.
4449    CXToken CXTok;
4450
4451    //   - Common fields
4452    CXTok.int_data[1] = Tok.getLocation().getRawEncoding();
4453    CXTok.int_data[2] = Tok.getLength();
4454    CXTok.int_data[3] = 0;
4455
4456    //   - Kind-specific fields
4457    if (Tok.isLiteral()) {
4458      CXTok.int_data[0] = CXToken_Literal;
4459      CXTok.ptr_data = (void *)Tok.getLiteralData();
4460    } else if (Tok.is(tok::raw_identifier)) {
4461      // Lookup the identifier to determine whether we have a keyword.
4462      IdentifierInfo *II
4463        = CXXUnit->getPreprocessor().LookUpIdentifierInfo(Tok);
4464
4465      if ((II->getObjCKeywordID() != tok::objc_not_keyword) && previousWasAt) {
4466        CXTok.int_data[0] = CXToken_Keyword;
4467      }
4468      else {
4469        CXTok.int_data[0] = Tok.is(tok::identifier)
4470          ? CXToken_Identifier
4471          : CXToken_Keyword;
4472      }
4473      CXTok.ptr_data = II;
4474    } else if (Tok.is(tok::comment)) {
4475      CXTok.int_data[0] = CXToken_Comment;
4476      CXTok.ptr_data = 0;
4477    } else {
4478      CXTok.int_data[0] = CXToken_Punctuation;
4479      CXTok.ptr_data = 0;
4480    }
4481    CXTokens.push_back(CXTok);
4482    previousWasAt = Tok.is(tok::at);
4483  } while (Lex.getBufferLocation() <= EffectiveBufferEnd);
4484
4485  if (CXTokens.empty())
4486    return;
4487
4488  *Tokens = (CXToken *)malloc(sizeof(CXToken) * CXTokens.size());
4489  memmove(*Tokens, CXTokens.data(), sizeof(CXToken) * CXTokens.size());
4490  *NumTokens = CXTokens.size();
4491}
4492
4493void clang_disposeTokens(CXTranslationUnit TU,
4494                         CXToken *Tokens, unsigned NumTokens) {
4495  free(Tokens);
4496}
4497
4498} // end: extern "C"
4499
4500//===----------------------------------------------------------------------===//
4501// Token annotation APIs.
4502//===----------------------------------------------------------------------===//
4503
4504typedef llvm::DenseMap<unsigned, CXCursor> AnnotateTokensData;
4505static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4506                                                     CXCursor parent,
4507                                                     CXClientData client_data);
4508namespace {
4509class AnnotateTokensWorker {
4510  AnnotateTokensData &Annotated;
4511  CXToken *Tokens;
4512  CXCursor *Cursors;
4513  unsigned NumTokens;
4514  unsigned TokIdx;
4515  unsigned PreprocessingTokIdx;
4516  CursorVisitor AnnotateVis;
4517  SourceManager &SrcMgr;
4518  bool HasContextSensitiveKeywords;
4519
4520  bool MoreTokens() const { return TokIdx < NumTokens; }
4521  unsigned NextToken() const { return TokIdx; }
4522  void AdvanceToken() { ++TokIdx; }
4523  SourceLocation GetTokenLoc(unsigned tokI) {
4524    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4525  }
4526  bool isFunctionMacroToken(unsigned tokI) const {
4527    return Tokens[tokI].int_data[3] != 0;
4528  }
4529  SourceLocation getFunctionMacroTokenLoc(unsigned tokI) const {
4530    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[3]);
4531  }
4532
4533  void annotateAndAdvanceTokens(CXCursor, RangeComparisonResult, SourceRange);
4534  void annotateAndAdvanceFunctionMacroTokens(CXCursor, RangeComparisonResult,
4535                                             SourceRange);
4536
4537public:
4538  AnnotateTokensWorker(AnnotateTokensData &annotated,
4539                       CXToken *tokens, CXCursor *cursors, unsigned numTokens,
4540                       CXTranslationUnit tu, SourceRange RegionOfInterest)
4541    : Annotated(annotated), Tokens(tokens), Cursors(cursors),
4542      NumTokens(numTokens), TokIdx(0), PreprocessingTokIdx(0),
4543      AnnotateVis(tu,
4544                  AnnotateTokensVisitor, this, true, RegionOfInterest),
4545      SrcMgr(static_cast<ASTUnit*>(tu->TUData)->getSourceManager()),
4546      HasContextSensitiveKeywords(false) { }
4547
4548  void VisitChildren(CXCursor C) { AnnotateVis.VisitChildren(C); }
4549  enum CXChildVisitResult Visit(CXCursor cursor, CXCursor parent);
4550  void AnnotateTokens(CXCursor parent);
4551  void AnnotateTokens() {
4552    AnnotateTokens(clang_getTranslationUnitCursor(AnnotateVis.getTU()));
4553  }
4554
4555  /// \brief Determine whether the annotator saw any cursors that have
4556  /// context-sensitive keywords.
4557  bool hasContextSensitiveKeywords() const {
4558    return HasContextSensitiveKeywords;
4559  }
4560};
4561}
4562
4563void AnnotateTokensWorker::AnnotateTokens(CXCursor parent) {
4564  // Walk the AST within the region of interest, annotating tokens
4565  // along the way.
4566  VisitChildren(parent);
4567
4568  for (unsigned I = 0 ; I < TokIdx ; ++I) {
4569    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4570    if (Pos != Annotated.end() &&
4571        (clang_isInvalid(Cursors[I].kind) ||
4572         Pos->second.kind != CXCursor_PreprocessingDirective))
4573      Cursors[I] = Pos->second;
4574  }
4575
4576  // Finish up annotating any tokens left.
4577  if (!MoreTokens())
4578    return;
4579
4580  const CXCursor &C = clang_getNullCursor();
4581  for (unsigned I = TokIdx ; I < NumTokens ; ++I) {
4582    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4583    Cursors[I] = (Pos == Annotated.end()) ? C : Pos->second;
4584  }
4585}
4586
4587/// \brief It annotates and advances tokens with a cursor until the comparison
4588//// between the cursor location and the source range is the same as
4589/// \arg compResult.
4590///
4591/// Pass RangeBefore to annotate tokens with a cursor until a range is reached.
4592/// Pass RangeOverlap to annotate tokens inside a range.
4593void AnnotateTokensWorker::annotateAndAdvanceTokens(CXCursor updateC,
4594                                               RangeComparisonResult compResult,
4595                                               SourceRange range) {
4596  while (MoreTokens()) {
4597    const unsigned I = NextToken();
4598    if (isFunctionMacroToken(I))
4599      return annotateAndAdvanceFunctionMacroTokens(updateC, compResult, range);
4600
4601    SourceLocation TokLoc = GetTokenLoc(I);
4602    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4603      Cursors[I] = updateC;
4604      AdvanceToken();
4605      continue;
4606    }
4607    break;
4608  }
4609}
4610
4611/// \brief Special annotation handling for macro argument tokens.
4612void AnnotateTokensWorker::annotateAndAdvanceFunctionMacroTokens(
4613                                               CXCursor updateC,
4614                                               RangeComparisonResult compResult,
4615                                               SourceRange range) {
4616  assert(MoreTokens());
4617  assert(isFunctionMacroToken(NextToken()) &&
4618         "Should be called only for macro arg tokens");
4619
4620  // This works differently than annotateAndAdvanceTokens; because expanded
4621  // macro arguments can have arbitrary translation-unit source order, we do not
4622  // advance the token index one by one until a token fails the range test.
4623  // We only advance once past all of the macro arg tokens if all of them
4624  // pass the range test. If one of them fails we keep the token index pointing
4625  // at the start of the macro arg tokens so that the failing token will be
4626  // annotated by a subsequent annotation try.
4627
4628  bool atLeastOneCompFail = false;
4629
4630  unsigned I = NextToken();
4631  for (; I < NumTokens && isFunctionMacroToken(I); ++I) {
4632    SourceLocation TokLoc = getFunctionMacroTokenLoc(I);
4633    if (TokLoc.isFileID())
4634      continue; // not macro arg token, it's parens or comma.
4635    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4636      if (clang_isInvalid(clang_getCursorKind(Cursors[I])))
4637        Cursors[I] = updateC;
4638    } else
4639      atLeastOneCompFail = true;
4640  }
4641
4642  if (!atLeastOneCompFail)
4643    TokIdx = I; // All of the tokens were handled, advance beyond all of them.
4644}
4645
4646enum CXChildVisitResult
4647AnnotateTokensWorker::Visit(CXCursor cursor, CXCursor parent) {
4648  CXSourceLocation Loc = clang_getCursorLocation(cursor);
4649  SourceRange cursorRange = getRawCursorExtent(cursor);
4650  if (cursorRange.isInvalid())
4651    return CXChildVisit_Recurse;
4652
4653  if (!HasContextSensitiveKeywords) {
4654    // Objective-C properties can have context-sensitive keywords.
4655    if (cursor.kind == CXCursor_ObjCPropertyDecl) {
4656      if (ObjCPropertyDecl *Property
4657                  = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(cursor)))
4658        HasContextSensitiveKeywords = Property->getPropertyAttributesAsWritten() != 0;
4659    }
4660    // Objective-C methods can have context-sensitive keywords.
4661    else if (cursor.kind == CXCursor_ObjCInstanceMethodDecl ||
4662             cursor.kind == CXCursor_ObjCClassMethodDecl) {
4663      if (ObjCMethodDecl *Method
4664            = dyn_cast_or_null<ObjCMethodDecl>(getCursorDecl(cursor))) {
4665        if (Method->getObjCDeclQualifier())
4666          HasContextSensitiveKeywords = true;
4667        else {
4668          for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
4669                                           PEnd = Method->param_end();
4670               P != PEnd; ++P) {
4671            if ((*P)->getObjCDeclQualifier()) {
4672              HasContextSensitiveKeywords = true;
4673              break;
4674            }
4675          }
4676        }
4677      }
4678    }
4679    // C++ methods can have context-sensitive keywords.
4680    else if (cursor.kind == CXCursor_CXXMethod) {
4681      if (CXXMethodDecl *Method
4682                  = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(cursor))) {
4683        if (Method->hasAttr<FinalAttr>() || Method->hasAttr<OverrideAttr>())
4684          HasContextSensitiveKeywords = true;
4685      }
4686    }
4687    // C++ classes can have context-sensitive keywords.
4688    else if (cursor.kind == CXCursor_StructDecl ||
4689             cursor.kind == CXCursor_ClassDecl ||
4690             cursor.kind == CXCursor_ClassTemplate ||
4691             cursor.kind == CXCursor_ClassTemplatePartialSpecialization) {
4692      if (Decl *D = getCursorDecl(cursor))
4693        if (D->hasAttr<FinalAttr>())
4694          HasContextSensitiveKeywords = true;
4695    }
4696  }
4697
4698  if (clang_isPreprocessing(cursor.kind)) {
4699    // For macro expansions, just note where the beginning of the macro
4700    // expansion occurs.
4701    if (cursor.kind == CXCursor_MacroExpansion) {
4702      Annotated[Loc.int_data] = cursor;
4703      return CXChildVisit_Recurse;
4704    }
4705
4706    // Items in the preprocessing record are kept separate from items in
4707    // declarations, so we keep a separate token index.
4708    unsigned SavedTokIdx = TokIdx;
4709    TokIdx = PreprocessingTokIdx;
4710
4711    // Skip tokens up until we catch up to the beginning of the preprocessing
4712    // entry.
4713    while (MoreTokens()) {
4714      const unsigned I = NextToken();
4715      SourceLocation TokLoc = GetTokenLoc(I);
4716      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4717      case RangeBefore:
4718        AdvanceToken();
4719        continue;
4720      case RangeAfter:
4721      case RangeOverlap:
4722        break;
4723      }
4724      break;
4725    }
4726
4727    // Look at all of the tokens within this range.
4728    while (MoreTokens()) {
4729      const unsigned I = NextToken();
4730      SourceLocation TokLoc = GetTokenLoc(I);
4731      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4732      case RangeBefore:
4733        assert(0 && "Infeasible");
4734      case RangeAfter:
4735        break;
4736      case RangeOverlap:
4737        Cursors[I] = cursor;
4738        AdvanceToken();
4739        continue;
4740      }
4741      break;
4742    }
4743
4744    // Save the preprocessing token index; restore the non-preprocessing
4745    // token index.
4746    PreprocessingTokIdx = TokIdx;
4747    TokIdx = SavedTokIdx;
4748    return CXChildVisit_Recurse;
4749  }
4750
4751  if (cursorRange.isInvalid())
4752    return CXChildVisit_Continue;
4753
4754  SourceLocation L = SourceLocation::getFromRawEncoding(Loc.int_data);
4755
4756  // Adjust the annotated range based specific declarations.
4757  const enum CXCursorKind cursorK = clang_getCursorKind(cursor);
4758  if (cursorK >= CXCursor_FirstDecl && cursorK <= CXCursor_LastDecl) {
4759    Decl *D = cxcursor::getCursorDecl(cursor);
4760
4761    SourceLocation StartLoc;
4762    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
4763      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
4764        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4765    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
4766      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
4767        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4768    }
4769
4770    if (StartLoc.isValid() && L.isValid() &&
4771        SrcMgr.isBeforeInTranslationUnit(StartLoc, L))
4772      cursorRange.setBegin(StartLoc);
4773  }
4774
4775  // If the location of the cursor occurs within a macro instantiation, record
4776  // the spelling location of the cursor in our annotation map.  We can then
4777  // paper over the token labelings during a post-processing step to try and
4778  // get cursor mappings for tokens that are the *arguments* of a macro
4779  // instantiation.
4780  if (L.isMacroID()) {
4781    unsigned rawEncoding = SrcMgr.getSpellingLoc(L).getRawEncoding();
4782    // Only invalidate the old annotation if it isn't part of a preprocessing
4783    // directive.  Here we assume that the default construction of CXCursor
4784    // results in CXCursor.kind being an initialized value (i.e., 0).  If
4785    // this isn't the case, we can fix by doing lookup + insertion.
4786
4787    CXCursor &oldC = Annotated[rawEncoding];
4788    if (!clang_isPreprocessing(oldC.kind))
4789      oldC = cursor;
4790  }
4791
4792  const enum CXCursorKind K = clang_getCursorKind(parent);
4793  const CXCursor updateC =
4794    (clang_isInvalid(K) || K == CXCursor_TranslationUnit)
4795     ? clang_getNullCursor() : parent;
4796
4797  annotateAndAdvanceTokens(updateC, RangeBefore, cursorRange);
4798
4799  // Avoid having the cursor of an expression "overwrite" the annotation of the
4800  // variable declaration that it belongs to.
4801  // This can happen for C++ constructor expressions whose range generally
4802  // include the variable declaration, e.g.:
4803  //  MyCXXClass foo; // Make sure we don't annotate 'foo' as a CallExpr cursor.
4804  if (clang_isExpression(cursorK)) {
4805    Expr *E = getCursorExpr(cursor);
4806    if (Decl *D = getCursorParentDecl(cursor)) {
4807      const unsigned I = NextToken();
4808      if (E->getLocStart().isValid() && D->getLocation().isValid() &&
4809          E->getLocStart() == D->getLocation() &&
4810          E->getLocStart() == GetTokenLoc(I)) {
4811        Cursors[I] = updateC;
4812        AdvanceToken();
4813      }
4814    }
4815  }
4816
4817  // Visit children to get their cursor information.
4818  const unsigned BeforeChildren = NextToken();
4819  VisitChildren(cursor);
4820  const unsigned AfterChildren = NextToken();
4821
4822  // Scan the tokens that are at the end of the cursor, but are not captured
4823  // but the child cursors.
4824  annotateAndAdvanceTokens(cursor, RangeOverlap, cursorRange);
4825
4826  // Scan the tokens that are at the beginning of the cursor, but are not
4827  // capture by the child cursors.
4828  for (unsigned I = BeforeChildren; I != AfterChildren; ++I) {
4829    if (!clang_isInvalid(clang_getCursorKind(Cursors[I])))
4830      break;
4831
4832    Cursors[I] = cursor;
4833  }
4834
4835  return CXChildVisit_Continue;
4836}
4837
4838static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4839                                                     CXCursor parent,
4840                                                     CXClientData client_data) {
4841  return static_cast<AnnotateTokensWorker*>(client_data)->Visit(cursor, parent);
4842}
4843
4844namespace {
4845
4846/// \brief Uses the macro expansions in the preprocessing record to find
4847/// and mark tokens that are macro arguments. This info is used by the
4848/// AnnotateTokensWorker.
4849class MarkMacroArgTokensVisitor {
4850  SourceManager &SM;
4851  CXToken *Tokens;
4852  unsigned NumTokens;
4853  unsigned CurIdx;
4854
4855public:
4856  MarkMacroArgTokensVisitor(SourceManager &SM,
4857                            CXToken *tokens, unsigned numTokens)
4858    : SM(SM), Tokens(tokens), NumTokens(numTokens), CurIdx(0) { }
4859
4860  CXChildVisitResult visit(CXCursor cursor, CXCursor parent) {
4861    if (cursor.kind != CXCursor_MacroExpansion)
4862      return CXChildVisit_Continue;
4863
4864    SourceRange macroRange = getCursorMacroExpansion(cursor)->getSourceRange();
4865    if (macroRange.getBegin() == macroRange.getEnd())
4866      return CXChildVisit_Continue; // it's not a function macro.
4867
4868    for (; CurIdx < NumTokens; ++CurIdx) {
4869      if (!SM.isBeforeInTranslationUnit(getTokenLoc(CurIdx),
4870                                        macroRange.getBegin()))
4871        break;
4872    }
4873
4874    if (CurIdx == NumTokens)
4875      return CXChildVisit_Break;
4876
4877    for (; CurIdx < NumTokens; ++CurIdx) {
4878      SourceLocation tokLoc = getTokenLoc(CurIdx);
4879      if (!SM.isBeforeInTranslationUnit(tokLoc, macroRange.getEnd()))
4880        break;
4881
4882      setFunctionMacroTokenLoc(CurIdx, SM.getMacroArgExpandedLocation(tokLoc));
4883    }
4884
4885    if (CurIdx == NumTokens)
4886      return CXChildVisit_Break;
4887
4888    return CXChildVisit_Continue;
4889  }
4890
4891private:
4892  SourceLocation getTokenLoc(unsigned tokI) {
4893    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4894  }
4895
4896  void setFunctionMacroTokenLoc(unsigned tokI, SourceLocation loc) {
4897    // The third field is reserved and currently not used. Use it here
4898    // to mark macro arg expanded tokens with their expanded locations.
4899    Tokens[tokI].int_data[3] = loc.getRawEncoding();
4900  }
4901};
4902
4903} // end anonymous namespace
4904
4905static CXChildVisitResult
4906MarkMacroArgTokensVisitorDelegate(CXCursor cursor, CXCursor parent,
4907                                  CXClientData client_data) {
4908  return static_cast<MarkMacroArgTokensVisitor*>(client_data)->visit(cursor,
4909                                                                     parent);
4910}
4911
4912namespace {
4913  struct clang_annotateTokens_Data {
4914    CXTranslationUnit TU;
4915    ASTUnit *CXXUnit;
4916    CXToken *Tokens;
4917    unsigned NumTokens;
4918    CXCursor *Cursors;
4919  };
4920}
4921
4922// This gets run a separate thread to avoid stack blowout.
4923static void clang_annotateTokensImpl(void *UserData) {
4924  CXTranslationUnit TU = ((clang_annotateTokens_Data*)UserData)->TU;
4925  ASTUnit *CXXUnit = ((clang_annotateTokens_Data*)UserData)->CXXUnit;
4926  CXToken *Tokens = ((clang_annotateTokens_Data*)UserData)->Tokens;
4927  const unsigned NumTokens = ((clang_annotateTokens_Data*)UserData)->NumTokens;
4928  CXCursor *Cursors = ((clang_annotateTokens_Data*)UserData)->Cursors;
4929
4930  // Determine the region of interest, which contains all of the tokens.
4931  SourceRange RegionOfInterest;
4932  RegionOfInterest.setBegin(
4933    cxloc::translateSourceLocation(clang_getTokenLocation(TU, Tokens[0])));
4934  RegionOfInterest.setEnd(
4935    cxloc::translateSourceLocation(clang_getTokenLocation(TU,
4936                                                         Tokens[NumTokens-1])));
4937
4938  // A mapping from the source locations found when re-lexing or traversing the
4939  // region of interest to the corresponding cursors.
4940  AnnotateTokensData Annotated;
4941
4942  // Relex the tokens within the source range to look for preprocessing
4943  // directives.
4944  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4945  std::pair<FileID, unsigned> BeginLocInfo
4946    = SourceMgr.getDecomposedLoc(RegionOfInterest.getBegin());
4947  std::pair<FileID, unsigned> EndLocInfo
4948    = SourceMgr.getDecomposedLoc(RegionOfInterest.getEnd());
4949
4950  StringRef Buffer;
4951  bool Invalid = false;
4952  if (BeginLocInfo.first == EndLocInfo.first &&
4953      ((Buffer = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid)),true) &&
4954      !Invalid) {
4955    Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4956              CXXUnit->getASTContext().getLangOptions(),
4957              Buffer.begin(), Buffer.data() + BeginLocInfo.second,
4958              Buffer.end());
4959    Lex.SetCommentRetentionState(true);
4960
4961    // Lex tokens in raw mode until we hit the end of the range, to avoid
4962    // entering #includes or expanding macros.
4963    while (true) {
4964      Token Tok;
4965      Lex.LexFromRawLexer(Tok);
4966
4967    reprocess:
4968      if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
4969        // We have found a preprocessing directive. Gobble it up so that we
4970        // don't see it while preprocessing these tokens later, but keep track
4971        // of all of the token locations inside this preprocessing directive so
4972        // that we can annotate them appropriately.
4973        //
4974        // FIXME: Some simple tests here could identify macro definitions and
4975        // #undefs, to provide specific cursor kinds for those.
4976        SmallVector<SourceLocation, 32> Locations;
4977        do {
4978          Locations.push_back(Tok.getLocation());
4979          Lex.LexFromRawLexer(Tok);
4980        } while (!Tok.isAtStartOfLine() && !Tok.is(tok::eof));
4981
4982        using namespace cxcursor;
4983        CXCursor Cursor
4984        = MakePreprocessingDirectiveCursor(SourceRange(Locations.front(),
4985                                                       Locations.back()),
4986                                           TU);
4987        for (unsigned I = 0, N = Locations.size(); I != N; ++I) {
4988          Annotated[Locations[I].getRawEncoding()] = Cursor;
4989        }
4990
4991        if (Tok.isAtStartOfLine())
4992          goto reprocess;
4993
4994        continue;
4995      }
4996
4997      if (Tok.is(tok::eof))
4998        break;
4999    }
5000  }
5001
5002  if (CXXUnit->getPreprocessor().getPreprocessingRecord()) {
5003    // Search and mark tokens that are macro argument expansions.
5004    MarkMacroArgTokensVisitor Visitor(CXXUnit->getSourceManager(),
5005                                      Tokens, NumTokens);
5006    CursorVisitor MacroArgMarker(TU,
5007                                 MarkMacroArgTokensVisitorDelegate, &Visitor,
5008                                 true, RegionOfInterest);
5009    MacroArgMarker.visitPreprocessedEntitiesInRegion();
5010  }
5011
5012  // Annotate all of the source locations in the region of interest that map to
5013  // a specific cursor.
5014  AnnotateTokensWorker W(Annotated, Tokens, Cursors, NumTokens,
5015                         TU, RegionOfInterest);
5016
5017  // FIXME: We use a ridiculous stack size here because the data-recursion
5018  // algorithm uses a large stack frame than the non-data recursive version,
5019  // and AnnotationTokensWorker currently transforms the data-recursion
5020  // algorithm back into a traditional recursion by explicitly calling
5021  // VisitChildren().  We will need to remove this explicit recursive call.
5022  W.AnnotateTokens();
5023
5024  // If we ran into any entities that involve context-sensitive keywords,
5025  // take another pass through the tokens to mark them as such.
5026  if (W.hasContextSensitiveKeywords()) {
5027    for (unsigned I = 0; I != NumTokens; ++I) {
5028      if (clang_getTokenKind(Tokens[I]) != CXToken_Identifier)
5029        continue;
5030
5031      if (Cursors[I].kind == CXCursor_ObjCPropertyDecl) {
5032        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5033        if (ObjCPropertyDecl *Property
5034            = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(Cursors[I]))) {
5035          if (Property->getPropertyAttributesAsWritten() != 0 &&
5036              llvm::StringSwitch<bool>(II->getName())
5037              .Case("readonly", true)
5038              .Case("assign", true)
5039              .Case("unsafe_unretained", true)
5040              .Case("readwrite", true)
5041              .Case("retain", true)
5042              .Case("copy", true)
5043              .Case("nonatomic", true)
5044              .Case("atomic", true)
5045              .Case("getter", true)
5046              .Case("setter", true)
5047              .Case("strong", true)
5048              .Case("weak", true)
5049              .Default(false))
5050            Tokens[I].int_data[0] = CXToken_Keyword;
5051        }
5052        continue;
5053      }
5054
5055      if (Cursors[I].kind == CXCursor_ObjCInstanceMethodDecl ||
5056          Cursors[I].kind == CXCursor_ObjCClassMethodDecl) {
5057        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5058        if (llvm::StringSwitch<bool>(II->getName())
5059            .Case("in", true)
5060            .Case("out", true)
5061            .Case("inout", true)
5062            .Case("oneway", true)
5063            .Case("bycopy", true)
5064            .Case("byref", true)
5065            .Default(false))
5066          Tokens[I].int_data[0] = CXToken_Keyword;
5067        continue;
5068      }
5069
5070      if (Cursors[I].kind == CXCursor_CXXFinalAttr ||
5071          Cursors[I].kind == CXCursor_CXXOverrideAttr) {
5072        Tokens[I].int_data[0] = CXToken_Keyword;
5073        continue;
5074      }
5075    }
5076  }
5077}
5078
5079extern "C" {
5080
5081void clang_annotateTokens(CXTranslationUnit TU,
5082                          CXToken *Tokens, unsigned NumTokens,
5083                          CXCursor *Cursors) {
5084
5085  if (NumTokens == 0 || !Tokens || !Cursors)
5086    return;
5087
5088  // Any token we don't specifically annotate will have a NULL cursor.
5089  CXCursor C = clang_getNullCursor();
5090  for (unsigned I = 0; I != NumTokens; ++I)
5091    Cursors[I] = C;
5092
5093  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
5094  if (!CXXUnit)
5095    return;
5096
5097  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
5098
5099  clang_annotateTokens_Data data = { TU, CXXUnit, Tokens, NumTokens, Cursors };
5100  llvm::CrashRecoveryContext CRC;
5101  if (!RunSafely(CRC, clang_annotateTokensImpl, &data,
5102                 GetSafetyThreadStackSize() * 2)) {
5103    fprintf(stderr, "libclang: crash detected while annotating tokens\n");
5104  }
5105}
5106
5107} // end: extern "C"
5108
5109//===----------------------------------------------------------------------===//
5110// Operations for querying linkage of a cursor.
5111//===----------------------------------------------------------------------===//
5112
5113extern "C" {
5114CXLinkageKind clang_getCursorLinkage(CXCursor cursor) {
5115  if (!clang_isDeclaration(cursor.kind))
5116    return CXLinkage_Invalid;
5117
5118  Decl *D = cxcursor::getCursorDecl(cursor);
5119  if (NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
5120    switch (ND->getLinkage()) {
5121      case NoLinkage: return CXLinkage_NoLinkage;
5122      case InternalLinkage: return CXLinkage_Internal;
5123      case UniqueExternalLinkage: return CXLinkage_UniqueExternal;
5124      case ExternalLinkage: return CXLinkage_External;
5125    };
5126
5127  return CXLinkage_Invalid;
5128}
5129} // end: extern "C"
5130
5131//===----------------------------------------------------------------------===//
5132// Operations for querying language of a cursor.
5133//===----------------------------------------------------------------------===//
5134
5135static CXLanguageKind getDeclLanguage(const Decl *D) {
5136  switch (D->getKind()) {
5137    default:
5138      break;
5139    case Decl::ImplicitParam:
5140    case Decl::ObjCAtDefsField:
5141    case Decl::ObjCCategory:
5142    case Decl::ObjCCategoryImpl:
5143    case Decl::ObjCClass:
5144    case Decl::ObjCCompatibleAlias:
5145    case Decl::ObjCForwardProtocol:
5146    case Decl::ObjCImplementation:
5147    case Decl::ObjCInterface:
5148    case Decl::ObjCIvar:
5149    case Decl::ObjCMethod:
5150    case Decl::ObjCProperty:
5151    case Decl::ObjCPropertyImpl:
5152    case Decl::ObjCProtocol:
5153      return CXLanguage_ObjC;
5154    case Decl::CXXConstructor:
5155    case Decl::CXXConversion:
5156    case Decl::CXXDestructor:
5157    case Decl::CXXMethod:
5158    case Decl::CXXRecord:
5159    case Decl::ClassTemplate:
5160    case Decl::ClassTemplatePartialSpecialization:
5161    case Decl::ClassTemplateSpecialization:
5162    case Decl::Friend:
5163    case Decl::FriendTemplate:
5164    case Decl::FunctionTemplate:
5165    case Decl::LinkageSpec:
5166    case Decl::Namespace:
5167    case Decl::NamespaceAlias:
5168    case Decl::NonTypeTemplateParm:
5169    case Decl::StaticAssert:
5170    case Decl::TemplateTemplateParm:
5171    case Decl::TemplateTypeParm:
5172    case Decl::UnresolvedUsingTypename:
5173    case Decl::UnresolvedUsingValue:
5174    case Decl::Using:
5175    case Decl::UsingDirective:
5176    case Decl::UsingShadow:
5177      return CXLanguage_CPlusPlus;
5178  }
5179
5180  return CXLanguage_C;
5181}
5182
5183extern "C" {
5184
5185enum CXAvailabilityKind clang_getCursorAvailability(CXCursor cursor) {
5186  if (clang_isDeclaration(cursor.kind))
5187    if (Decl *D = cxcursor::getCursorDecl(cursor)) {
5188      if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->isDeleted())
5189        return CXAvailability_Available;
5190
5191      switch (D->getAvailability()) {
5192      case AR_Available:
5193      case AR_NotYetIntroduced:
5194        return CXAvailability_Available;
5195
5196      case AR_Deprecated:
5197        return CXAvailability_Deprecated;
5198
5199      case AR_Unavailable:
5200        return CXAvailability_NotAvailable;
5201      }
5202    }
5203
5204  return CXAvailability_Available;
5205}
5206
5207CXLanguageKind clang_getCursorLanguage(CXCursor cursor) {
5208  if (clang_isDeclaration(cursor.kind))
5209    return getDeclLanguage(cxcursor::getCursorDecl(cursor));
5210
5211  return CXLanguage_Invalid;
5212}
5213
5214 /// \brief If the given cursor is the "templated" declaration
5215 /// descibing a class or function template, return the class or
5216 /// function template.
5217static Decl *maybeGetTemplateCursor(Decl *D) {
5218  if (!D)
5219    return 0;
5220
5221  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
5222    if (FunctionTemplateDecl *FunTmpl = FD->getDescribedFunctionTemplate())
5223      return FunTmpl;
5224
5225  if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D))
5226    if (ClassTemplateDecl *ClassTmpl = RD->getDescribedClassTemplate())
5227      return ClassTmpl;
5228
5229  return D;
5230}
5231
5232CXCursor clang_getCursorSemanticParent(CXCursor cursor) {
5233  if (clang_isDeclaration(cursor.kind)) {
5234    if (Decl *D = getCursorDecl(cursor)) {
5235      DeclContext *DC = D->getDeclContext();
5236      if (!DC)
5237        return clang_getNullCursor();
5238
5239      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5240                          getCursorTU(cursor));
5241    }
5242  }
5243
5244  if (clang_isStatement(cursor.kind) || clang_isExpression(cursor.kind)) {
5245    if (Decl *D = getCursorDecl(cursor))
5246      return MakeCXCursor(D, getCursorTU(cursor));
5247  }
5248
5249  return clang_getNullCursor();
5250}
5251
5252CXCursor clang_getCursorLexicalParent(CXCursor cursor) {
5253  if (clang_isDeclaration(cursor.kind)) {
5254    if (Decl *D = getCursorDecl(cursor)) {
5255      DeclContext *DC = D->getLexicalDeclContext();
5256      if (!DC)
5257        return clang_getNullCursor();
5258
5259      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5260                          getCursorTU(cursor));
5261    }
5262  }
5263
5264  // FIXME: Note that we can't easily compute the lexical context of a
5265  // statement or expression, so we return nothing.
5266  return clang_getNullCursor();
5267}
5268
5269static void CollectOverriddenMethods(DeclContext *Ctx,
5270                                     ObjCMethodDecl *Method,
5271                            SmallVectorImpl<ObjCMethodDecl *> &Methods) {
5272  if (!Ctx)
5273    return;
5274
5275  // If we have a class or category implementation, jump straight to the
5276  // interface.
5277  if (ObjCImplDecl *Impl = dyn_cast<ObjCImplDecl>(Ctx))
5278    return CollectOverriddenMethods(Impl->getClassInterface(), Method, Methods);
5279
5280  ObjCContainerDecl *Container = dyn_cast<ObjCContainerDecl>(Ctx);
5281  if (!Container)
5282    return;
5283
5284  // Check whether we have a matching method at this level.
5285  if (ObjCMethodDecl *Overridden = Container->getMethod(Method->getSelector(),
5286                                                    Method->isInstanceMethod()))
5287    if (Method != Overridden) {
5288      // We found an override at this level; there is no need to look
5289      // into other protocols or categories.
5290      Methods.push_back(Overridden);
5291      return;
5292    }
5293
5294  if (ObjCProtocolDecl *Protocol = dyn_cast<ObjCProtocolDecl>(Container)) {
5295    for (ObjCProtocolDecl::protocol_iterator P = Protocol->protocol_begin(),
5296                                          PEnd = Protocol->protocol_end();
5297         P != PEnd; ++P)
5298      CollectOverriddenMethods(*P, Method, Methods);
5299  }
5300
5301  if (ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(Container)) {
5302    for (ObjCCategoryDecl::protocol_iterator P = Category->protocol_begin(),
5303                                          PEnd = Category->protocol_end();
5304         P != PEnd; ++P)
5305      CollectOverriddenMethods(*P, Method, Methods);
5306  }
5307
5308  if (ObjCInterfaceDecl *Interface = dyn_cast<ObjCInterfaceDecl>(Container)) {
5309    for (ObjCInterfaceDecl::protocol_iterator P = Interface->protocol_begin(),
5310                                           PEnd = Interface->protocol_end();
5311         P != PEnd; ++P)
5312      CollectOverriddenMethods(*P, Method, Methods);
5313
5314    for (ObjCCategoryDecl *Category = Interface->getCategoryList();
5315         Category; Category = Category->getNextClassCategory())
5316      CollectOverriddenMethods(Category, Method, Methods);
5317
5318    // We only look into the superclass if we haven't found anything yet.
5319    if (Methods.empty())
5320      if (ObjCInterfaceDecl *Super = Interface->getSuperClass())
5321        return CollectOverriddenMethods(Super, Method, Methods);
5322  }
5323}
5324
5325void clang_getOverriddenCursors(CXCursor cursor,
5326                                CXCursor **overridden,
5327                                unsigned *num_overridden) {
5328  if (overridden)
5329    *overridden = 0;
5330  if (num_overridden)
5331    *num_overridden = 0;
5332  if (!overridden || !num_overridden)
5333    return;
5334
5335  if (!clang_isDeclaration(cursor.kind))
5336    return;
5337
5338  Decl *D = getCursorDecl(cursor);
5339  if (!D)
5340    return;
5341
5342  // Handle C++ member functions.
5343  CXTranslationUnit TU = getCursorTU(cursor);
5344  if (CXXMethodDecl *CXXMethod = dyn_cast<CXXMethodDecl>(D)) {
5345    *num_overridden = CXXMethod->size_overridden_methods();
5346    if (!*num_overridden)
5347      return;
5348
5349    *overridden = new CXCursor [*num_overridden];
5350    unsigned I = 0;
5351    for (CXXMethodDecl::method_iterator
5352              M = CXXMethod->begin_overridden_methods(),
5353           MEnd = CXXMethod->end_overridden_methods();
5354         M != MEnd; (void)++M, ++I)
5355      (*overridden)[I] = MakeCXCursor(const_cast<CXXMethodDecl*>(*M), TU);
5356    return;
5357  }
5358
5359  ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(D);
5360  if (!Method)
5361    return;
5362
5363  // Handle Objective-C methods.
5364  SmallVector<ObjCMethodDecl *, 4> Methods;
5365  CollectOverriddenMethods(Method->getDeclContext(), Method, Methods);
5366
5367  if (Methods.empty())
5368    return;
5369
5370  *num_overridden = Methods.size();
5371  *overridden = new CXCursor [Methods.size()];
5372  for (unsigned I = 0, N = Methods.size(); I != N; ++I)
5373    (*overridden)[I] = MakeCXCursor(Methods[I], TU);
5374}
5375
5376void clang_disposeOverriddenCursors(CXCursor *overridden) {
5377  delete [] overridden;
5378}
5379
5380CXFile clang_getIncludedFile(CXCursor cursor) {
5381  if (cursor.kind != CXCursor_InclusionDirective)
5382    return 0;
5383
5384  InclusionDirective *ID = getCursorInclusionDirective(cursor);
5385  return (void *)ID->getFile();
5386}
5387
5388} // end: extern "C"
5389
5390
5391//===----------------------------------------------------------------------===//
5392// C++ AST instrospection.
5393//===----------------------------------------------------------------------===//
5394
5395extern "C" {
5396unsigned clang_CXXMethod_isStatic(CXCursor C) {
5397  if (!clang_isDeclaration(C.kind))
5398    return 0;
5399
5400  CXXMethodDecl *Method = 0;
5401  Decl *D = cxcursor::getCursorDecl(C);
5402  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5403    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5404  else
5405    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5406  return (Method && Method->isStatic()) ? 1 : 0;
5407}
5408
5409unsigned clang_CXXMethod_isVirtual(CXCursor C) {
5410  if (!clang_isDeclaration(C.kind))
5411    return 0;
5412
5413  CXXMethodDecl *Method = 0;
5414  Decl *D = cxcursor::getCursorDecl(C);
5415  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5416    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5417  else
5418    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5419  return (Method && Method->isVirtual()) ? 1 : 0;
5420}
5421} // end: extern "C"
5422
5423//===----------------------------------------------------------------------===//
5424// Attribute introspection.
5425//===----------------------------------------------------------------------===//
5426
5427extern "C" {
5428CXType clang_getIBOutletCollectionType(CXCursor C) {
5429  if (C.kind != CXCursor_IBOutletCollectionAttr)
5430    return cxtype::MakeCXType(QualType(), cxcursor::getCursorTU(C));
5431
5432  IBOutletCollectionAttr *A =
5433    cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(C));
5434
5435  return cxtype::MakeCXType(A->getInterface(), cxcursor::getCursorTU(C));
5436}
5437} // end: extern "C"
5438
5439//===----------------------------------------------------------------------===//
5440// Inspecting memory usage.
5441//===----------------------------------------------------------------------===//
5442
5443typedef std::vector<CXTUResourceUsageEntry> MemUsageEntries;
5444
5445static inline void createCXTUResourceUsageEntry(MemUsageEntries &entries,
5446                                              enum CXTUResourceUsageKind k,
5447                                              unsigned long amount) {
5448  CXTUResourceUsageEntry entry = { k, amount };
5449  entries.push_back(entry);
5450}
5451
5452extern "C" {
5453
5454const char *clang_getTUResourceUsageName(CXTUResourceUsageKind kind) {
5455  const char *str = "";
5456  switch (kind) {
5457    case CXTUResourceUsage_AST:
5458      str = "ASTContext: expressions, declarations, and types";
5459      break;
5460    case CXTUResourceUsage_Identifiers:
5461      str = "ASTContext: identifiers";
5462      break;
5463    case CXTUResourceUsage_Selectors:
5464      str = "ASTContext: selectors";
5465      break;
5466    case CXTUResourceUsage_GlobalCompletionResults:
5467      str = "Code completion: cached global results";
5468      break;
5469    case CXTUResourceUsage_SourceManagerContentCache:
5470      str = "SourceManager: content cache allocator";
5471      break;
5472    case CXTUResourceUsage_AST_SideTables:
5473      str = "ASTContext: side tables";
5474      break;
5475    case CXTUResourceUsage_SourceManager_Membuffer_Malloc:
5476      str = "SourceManager: malloc'ed memory buffers";
5477      break;
5478    case CXTUResourceUsage_SourceManager_Membuffer_MMap:
5479      str = "SourceManager: mmap'ed memory buffers";
5480      break;
5481    case CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc:
5482      str = "ExternalASTSource: malloc'ed memory buffers";
5483      break;
5484    case CXTUResourceUsage_ExternalASTSource_Membuffer_MMap:
5485      str = "ExternalASTSource: mmap'ed memory buffers";
5486      break;
5487    case CXTUResourceUsage_Preprocessor:
5488      str = "Preprocessor: malloc'ed memory";
5489      break;
5490    case CXTUResourceUsage_PreprocessingRecord:
5491      str = "Preprocessor: PreprocessingRecord";
5492      break;
5493    case CXTUResourceUsage_SourceManager_DataStructures:
5494      str = "SourceManager: data structures and tables";
5495      break;
5496    case CXTUResourceUsage_Preprocessor_HeaderSearch:
5497      str = "Preprocessor: header search tables";
5498      break;
5499  }
5500  return str;
5501}
5502
5503CXTUResourceUsage clang_getCXTUResourceUsage(CXTranslationUnit TU) {
5504  if (!TU) {
5505    CXTUResourceUsage usage = { (void*) 0, 0, 0 };
5506    return usage;
5507  }
5508
5509  ASTUnit *astUnit = static_cast<ASTUnit*>(TU->TUData);
5510  llvm::OwningPtr<MemUsageEntries> entries(new MemUsageEntries());
5511  ASTContext &astContext = astUnit->getASTContext();
5512
5513  // How much memory is used by AST nodes and types?
5514  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST,
5515    (unsigned long) astContext.getASTAllocatedMemory());
5516
5517  // How much memory is used by identifiers?
5518  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Identifiers,
5519    (unsigned long) astContext.Idents.getAllocator().getTotalMemory());
5520
5521  // How much memory is used for selectors?
5522  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Selectors,
5523    (unsigned long) astContext.Selectors.getTotalMemory());
5524
5525  // How much memory is used by ASTContext's side tables?
5526  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST_SideTables,
5527    (unsigned long) astContext.getSideTableAllocatedMemory());
5528
5529  // How much memory is used for caching global code completion results?
5530  unsigned long completionBytes = 0;
5531  if (GlobalCodeCompletionAllocator *completionAllocator =
5532      astUnit->getCachedCompletionAllocator().getPtr()) {
5533    completionBytes = completionAllocator->getTotalMemory();
5534  }
5535  createCXTUResourceUsageEntry(*entries,
5536                               CXTUResourceUsage_GlobalCompletionResults,
5537                               completionBytes);
5538
5539  // How much memory is being used by SourceManager's content cache?
5540  createCXTUResourceUsageEntry(*entries,
5541          CXTUResourceUsage_SourceManagerContentCache,
5542          (unsigned long) astContext.getSourceManager().getContentCacheSize());
5543
5544  // How much memory is being used by the MemoryBuffer's in SourceManager?
5545  const SourceManager::MemoryBufferSizes &srcBufs =
5546    astUnit->getSourceManager().getMemoryBufferSizes();
5547
5548  createCXTUResourceUsageEntry(*entries,
5549                               CXTUResourceUsage_SourceManager_Membuffer_Malloc,
5550                               (unsigned long) srcBufs.malloc_bytes);
5551  createCXTUResourceUsageEntry(*entries,
5552                               CXTUResourceUsage_SourceManager_Membuffer_MMap,
5553                               (unsigned long) srcBufs.mmap_bytes);
5554  createCXTUResourceUsageEntry(*entries,
5555                               CXTUResourceUsage_SourceManager_DataStructures,
5556                               (unsigned long) astContext.getSourceManager()
5557                                .getDataStructureSizes());
5558
5559  // How much memory is being used by the ExternalASTSource?
5560  if (ExternalASTSource *esrc = astContext.getExternalSource()) {
5561    const ExternalASTSource::MemoryBufferSizes &sizes =
5562      esrc->getMemoryBufferSizes();
5563
5564    createCXTUResourceUsageEntry(*entries,
5565      CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc,
5566                                 (unsigned long) sizes.malloc_bytes);
5567    createCXTUResourceUsageEntry(*entries,
5568      CXTUResourceUsage_ExternalASTSource_Membuffer_MMap,
5569                                 (unsigned long) sizes.mmap_bytes);
5570  }
5571
5572  // How much memory is being used by the Preprocessor?
5573  Preprocessor &pp = astUnit->getPreprocessor();
5574  createCXTUResourceUsageEntry(*entries,
5575                               CXTUResourceUsage_Preprocessor,
5576                               pp.getTotalMemory());
5577
5578  if (PreprocessingRecord *pRec = pp.getPreprocessingRecord()) {
5579    createCXTUResourceUsageEntry(*entries,
5580                                 CXTUResourceUsage_PreprocessingRecord,
5581                                 pRec->getTotalMemory());
5582  }
5583
5584  createCXTUResourceUsageEntry(*entries,
5585                               CXTUResourceUsage_Preprocessor_HeaderSearch,
5586                               pp.getHeaderSearchInfo().getTotalMemory());
5587
5588  CXTUResourceUsage usage = { (void*) entries.get(),
5589                            (unsigned) entries->size(),
5590                            entries->size() ? &(*entries)[0] : 0 };
5591  entries.take();
5592  return usage;
5593}
5594
5595void clang_disposeCXTUResourceUsage(CXTUResourceUsage usage) {
5596  if (usage.data)
5597    delete (MemUsageEntries*) usage.data;
5598}
5599
5600} // end extern "C"
5601
5602void clang::PrintLibclangResourceUsage(CXTranslationUnit TU) {
5603  CXTUResourceUsage Usage = clang_getCXTUResourceUsage(TU);
5604  for (unsigned I = 0; I != Usage.numEntries; ++I)
5605    fprintf(stderr, "  %s: %lu\n",
5606            clang_getTUResourceUsageName(Usage.entries[I].kind),
5607            Usage.entries[I].amount);
5608
5609  clang_disposeCXTUResourceUsage(Usage);
5610}
5611
5612//===----------------------------------------------------------------------===//
5613// Misc. utility functions.
5614//===----------------------------------------------------------------------===//
5615
5616/// Default to using an 8 MB stack size on "safety" threads.
5617static unsigned SafetyStackThreadSize = 8 << 20;
5618
5619namespace clang {
5620
5621bool RunSafely(llvm::CrashRecoveryContext &CRC,
5622               void (*Fn)(void*), void *UserData,
5623               unsigned Size) {
5624  if (!Size)
5625    Size = GetSafetyThreadStackSize();
5626  if (Size)
5627    return CRC.RunSafelyOnThread(Fn, UserData, Size);
5628  return CRC.RunSafely(Fn, UserData);
5629}
5630
5631unsigned GetSafetyThreadStackSize() {
5632  return SafetyStackThreadSize;
5633}
5634
5635void SetSafetyThreadStackSize(unsigned Value) {
5636  SafetyStackThreadSize = Value;
5637}
5638
5639}
5640
5641extern "C" {
5642
5643CXString clang_getClangVersion() {
5644  return createCXString(getClangFullVersion());
5645}
5646
5647} // end: extern "C"
5648
5649