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