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