CIndex.cpp revision 98c16b8b4fe7bb26b17a479d6872e390816e57d4 
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      CXCursor C = MakeCXCursor(Prot, tu);
3926      C.kind = CXCursor_ObjCProtocolDecl; // override "Unexposed".
3927      return C;
3928    }
3929
3930    case CXCursor_ObjCClassRef: {
3931      ObjCInterfaceDecl *Class = getCursorObjCClassRef(C).first;
3932      if (ObjCInterfaceDecl *Def = Class->getDefinition())
3933        return MakeCXCursor(Def, tu);
3934
3935      CXCursor C = MakeCXCursor(Class, tu);
3936      C.kind = CXCursor_ObjCInterfaceDecl; // override "Unexposed".
3937      return C;
3938    }
3939
3940    case CXCursor_TypeRef:
3941      return MakeCXCursor(getCursorTypeRef(C).first, tu );
3942
3943    case CXCursor_TemplateRef:
3944      return MakeCXCursor(getCursorTemplateRef(C).first, tu );
3945
3946    case CXCursor_NamespaceRef:
3947      return MakeCXCursor(getCursorNamespaceRef(C).first, tu );
3948
3949    case CXCursor_MemberRef:
3950      return MakeCXCursor(getCursorMemberRef(C).first, tu );
3951
3952    case CXCursor_CXXBaseSpecifier: {
3953      CXXBaseSpecifier *B = cxcursor::getCursorCXXBaseSpecifier(C);
3954      return clang_getTypeDeclaration(cxtype::MakeCXType(B->getType(),
3955                                                         tu ));
3956    }
3957
3958    case CXCursor_LabelRef:
3959      // FIXME: We end up faking the "parent" declaration here because we
3960      // don't want to make CXCursor larger.
3961      return MakeCXCursor(getCursorLabelRef(C).first,
3962               static_cast<ASTUnit*>(tu->TUData)->getASTContext()
3963                          .getTranslationUnitDecl(),
3964                          tu);
3965
3966    case CXCursor_OverloadedDeclRef:
3967      return C;
3968
3969    default:
3970      // We would prefer to enumerate all non-reference cursor kinds here.
3971      llvm_unreachable("Unhandled reference cursor kind");
3972  }
3973}
3974
3975CXCursor clang_getCursorDefinition(CXCursor C) {
3976  if (clang_isInvalid(C.kind))
3977    return clang_getNullCursor();
3978
3979  CXTranslationUnit TU = getCursorTU(C);
3980
3981  bool WasReference = false;
3982  if (clang_isReference(C.kind) || clang_isExpression(C.kind)) {
3983    C = clang_getCursorReferenced(C);
3984    WasReference = true;
3985  }
3986
3987  if (C.kind == CXCursor_MacroExpansion)
3988    return clang_getCursorReferenced(C);
3989
3990  if (!clang_isDeclaration(C.kind))
3991    return clang_getNullCursor();
3992
3993  Decl *D = getCursorDecl(C);
3994  if (!D)
3995    return clang_getNullCursor();
3996
3997  switch (D->getKind()) {
3998  // Declaration kinds that don't really separate the notions of
3999  // declaration and definition.
4000  case Decl::Namespace:
4001  case Decl::Typedef:
4002  case Decl::TypeAlias:
4003  case Decl::TypeAliasTemplate:
4004  case Decl::TemplateTypeParm:
4005  case Decl::EnumConstant:
4006  case Decl::Field:
4007  case Decl::IndirectField:
4008  case Decl::ObjCIvar:
4009  case Decl::ObjCAtDefsField:
4010  case Decl::ImplicitParam:
4011  case Decl::ParmVar:
4012  case Decl::NonTypeTemplateParm:
4013  case Decl::TemplateTemplateParm:
4014  case Decl::ObjCCategoryImpl:
4015  case Decl::ObjCImplementation:
4016  case Decl::AccessSpec:
4017  case Decl::LinkageSpec:
4018  case Decl::ObjCPropertyImpl:
4019  case Decl::FileScopeAsm:
4020  case Decl::StaticAssert:
4021  case Decl::Block:
4022  case Decl::Label:  // FIXME: Is this right??
4023  case Decl::ClassScopeFunctionSpecialization:
4024  case Decl::Import:
4025    return C;
4026
4027  // Declaration kinds that don't make any sense here, but are
4028  // nonetheless harmless.
4029  case Decl::TranslationUnit:
4030    break;
4031
4032  // Declaration kinds for which the definition is not resolvable.
4033  case Decl::UnresolvedUsingTypename:
4034  case Decl::UnresolvedUsingValue:
4035    break;
4036
4037  case Decl::UsingDirective:
4038    return MakeCXCursor(cast<UsingDirectiveDecl>(D)->getNominatedNamespace(),
4039                        TU);
4040
4041  case Decl::NamespaceAlias:
4042    return MakeCXCursor(cast<NamespaceAliasDecl>(D)->getNamespace(), TU);
4043
4044  case Decl::Enum:
4045  case Decl::Record:
4046  case Decl::CXXRecord:
4047  case Decl::ClassTemplateSpecialization:
4048  case Decl::ClassTemplatePartialSpecialization:
4049    if (TagDecl *Def = cast<TagDecl>(D)->getDefinition())
4050      return MakeCXCursor(Def, TU);
4051    return clang_getNullCursor();
4052
4053  case Decl::Function:
4054  case Decl::CXXMethod:
4055  case Decl::CXXConstructor:
4056  case Decl::CXXDestructor:
4057  case Decl::CXXConversion: {
4058    const FunctionDecl *Def = 0;
4059    if (cast<FunctionDecl>(D)->getBody(Def))
4060      return MakeCXCursor(const_cast<FunctionDecl *>(Def), TU);
4061    return clang_getNullCursor();
4062  }
4063
4064  case Decl::Var: {
4065    // Ask the variable if it has a definition.
4066    if (VarDecl *Def = cast<VarDecl>(D)->getDefinition())
4067      return MakeCXCursor(Def, TU);
4068    return clang_getNullCursor();
4069  }
4070
4071  case Decl::FunctionTemplate: {
4072    const FunctionDecl *Def = 0;
4073    if (cast<FunctionTemplateDecl>(D)->getTemplatedDecl()->getBody(Def))
4074      return MakeCXCursor(Def->getDescribedFunctionTemplate(), TU);
4075    return clang_getNullCursor();
4076  }
4077
4078  case Decl::ClassTemplate: {
4079    if (RecordDecl *Def = cast<ClassTemplateDecl>(D)->getTemplatedDecl()
4080                                                            ->getDefinition())
4081      return MakeCXCursor(cast<CXXRecordDecl>(Def)->getDescribedClassTemplate(),
4082                          TU);
4083    return clang_getNullCursor();
4084  }
4085
4086  case Decl::Using:
4087    return MakeCursorOverloadedDeclRef(cast<UsingDecl>(D),
4088                                       D->getLocation(), TU);
4089
4090  case Decl::UsingShadow:
4091    return clang_getCursorDefinition(
4092                       MakeCXCursor(cast<UsingShadowDecl>(D)->getTargetDecl(),
4093                                    TU));
4094
4095  case Decl::ObjCMethod: {
4096    ObjCMethodDecl *Method = cast<ObjCMethodDecl>(D);
4097    if (Method->isThisDeclarationADefinition())
4098      return C;
4099
4100    // Dig out the method definition in the associated
4101    // @implementation, if we have it.
4102    // FIXME: The ASTs should make finding the definition easier.
4103    if (ObjCInterfaceDecl *Class
4104                       = dyn_cast<ObjCInterfaceDecl>(Method->getDeclContext()))
4105      if (ObjCImplementationDecl *ClassImpl = Class->getImplementation())
4106        if (ObjCMethodDecl *Def = ClassImpl->getMethod(Method->getSelector(),
4107                                                  Method->isInstanceMethod()))
4108          if (Def->isThisDeclarationADefinition())
4109            return MakeCXCursor(Def, TU);
4110
4111    return clang_getNullCursor();
4112  }
4113
4114  case Decl::ObjCCategory:
4115    if (ObjCCategoryImplDecl *Impl
4116                               = cast<ObjCCategoryDecl>(D)->getImplementation())
4117      return MakeCXCursor(Impl, TU);
4118    return clang_getNullCursor();
4119
4120  case Decl::ObjCProtocol:
4121    if (ObjCProtocolDecl *Def = cast<ObjCProtocolDecl>(D)->getDefinition())
4122      return MakeCXCursor(Def, TU);
4123    return clang_getNullCursor();
4124
4125  case Decl::ObjCInterface: {
4126    // There are two notions of a "definition" for an Objective-C
4127    // class: the interface and its implementation. When we resolved a
4128    // reference to an Objective-C class, produce the @interface as
4129    // the definition; when we were provided with the interface,
4130    // produce the @implementation as the definition.
4131    ObjCInterfaceDecl *IFace = cast<ObjCInterfaceDecl>(D);
4132    if (WasReference) {
4133      if (ObjCInterfaceDecl *Def = IFace->getDefinition())
4134        return MakeCXCursor(Def, TU);
4135    } else if (ObjCImplementationDecl *Impl = IFace->getImplementation())
4136      return MakeCXCursor(Impl, TU);
4137    return clang_getNullCursor();
4138  }
4139
4140  case Decl::ObjCProperty:
4141    // FIXME: We don't really know where to find the
4142    // ObjCPropertyImplDecls that implement this property.
4143    return clang_getNullCursor();
4144
4145  case Decl::ObjCCompatibleAlias:
4146    if (ObjCInterfaceDecl *Class
4147          = cast<ObjCCompatibleAliasDecl>(D)->getClassInterface())
4148      if (ObjCInterfaceDecl *Def = Class->getDefinition())
4149        return MakeCXCursor(Def, TU);
4150
4151    return clang_getNullCursor();
4152
4153  case Decl::Friend:
4154    if (NamedDecl *Friend = cast<FriendDecl>(D)->getFriendDecl())
4155      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4156    return clang_getNullCursor();
4157
4158  case Decl::FriendTemplate:
4159    if (NamedDecl *Friend = cast<FriendTemplateDecl>(D)->getFriendDecl())
4160      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4161    return clang_getNullCursor();
4162  }
4163
4164  return clang_getNullCursor();
4165}
4166
4167unsigned clang_isCursorDefinition(CXCursor C) {
4168  if (!clang_isDeclaration(C.kind))
4169    return 0;
4170
4171  return clang_getCursorDefinition(C) == C;
4172}
4173
4174CXCursor clang_getCanonicalCursor(CXCursor C) {
4175  if (!clang_isDeclaration(C.kind))
4176    return C;
4177
4178  if (Decl *D = getCursorDecl(C)) {
4179    if (ObjCCategoryImplDecl *CatImplD = dyn_cast<ObjCCategoryImplDecl>(D))
4180      if (ObjCCategoryDecl *CatD = CatImplD->getCategoryDecl())
4181        return MakeCXCursor(CatD, getCursorTU(C));
4182
4183    if (ObjCImplDecl *ImplD = dyn_cast<ObjCImplDecl>(D))
4184      if (ObjCInterfaceDecl *IFD = ImplD->getClassInterface())
4185        return MakeCXCursor(IFD, getCursorTU(C));
4186
4187    return MakeCXCursor(D->getCanonicalDecl(), getCursorTU(C));
4188  }
4189
4190  return C;
4191}
4192
4193unsigned clang_getNumOverloadedDecls(CXCursor C) {
4194  if (C.kind != CXCursor_OverloadedDeclRef)
4195    return 0;
4196
4197  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
4198  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4199    return E->getNumDecls();
4200
4201  if (OverloadedTemplateStorage *S
4202                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4203    return S->size();
4204
4205  Decl *D = Storage.get<Decl*>();
4206  if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
4207    return Using->shadow_size();
4208
4209  return 0;
4210}
4211
4212CXCursor clang_getOverloadedDecl(CXCursor cursor, unsigned index) {
4213  if (cursor.kind != CXCursor_OverloadedDeclRef)
4214    return clang_getNullCursor();
4215
4216  if (index >= clang_getNumOverloadedDecls(cursor))
4217    return clang_getNullCursor();
4218
4219  CXTranslationUnit TU = getCursorTU(cursor);
4220  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(cursor).first;
4221  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4222    return MakeCXCursor(E->decls_begin()[index], TU);
4223
4224  if (OverloadedTemplateStorage *S
4225                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4226    return MakeCXCursor(S->begin()[index], TU);
4227
4228  Decl *D = Storage.get<Decl*>();
4229  if (UsingDecl *Using = dyn_cast<UsingDecl>(D)) {
4230    // FIXME: This is, unfortunately, linear time.
4231    UsingDecl::shadow_iterator Pos = Using->shadow_begin();
4232    std::advance(Pos, index);
4233    return MakeCXCursor(cast<UsingShadowDecl>(*Pos)->getTargetDecl(), TU);
4234  }
4235
4236  return clang_getNullCursor();
4237}
4238
4239void clang_getDefinitionSpellingAndExtent(CXCursor C,
4240                                          const char **startBuf,
4241                                          const char **endBuf,
4242                                          unsigned *startLine,
4243                                          unsigned *startColumn,
4244                                          unsigned *endLine,
4245                                          unsigned *endColumn) {
4246  assert(getCursorDecl(C) && "CXCursor has null decl");
4247  NamedDecl *ND = static_cast<NamedDecl *>(getCursorDecl(C));
4248  FunctionDecl *FD = dyn_cast<FunctionDecl>(ND);
4249  CompoundStmt *Body = dyn_cast<CompoundStmt>(FD->getBody());
4250
4251  SourceManager &SM = FD->getASTContext().getSourceManager();
4252  *startBuf = SM.getCharacterData(Body->getLBracLoc());
4253  *endBuf = SM.getCharacterData(Body->getRBracLoc());
4254  *startLine = SM.getSpellingLineNumber(Body->getLBracLoc());
4255  *startColumn = SM.getSpellingColumnNumber(Body->getLBracLoc());
4256  *endLine = SM.getSpellingLineNumber(Body->getRBracLoc());
4257  *endColumn = SM.getSpellingColumnNumber(Body->getRBracLoc());
4258}
4259
4260
4261CXSourceRange clang_getCursorReferenceNameRange(CXCursor C, unsigned NameFlags,
4262                                                unsigned PieceIndex) {
4263  RefNamePieces Pieces;
4264
4265  switch (C.kind) {
4266  case CXCursor_MemberRefExpr:
4267    if (MemberExpr *E = dyn_cast<MemberExpr>(getCursorExpr(C)))
4268      Pieces = buildPieces(NameFlags, true, E->getMemberNameInfo(),
4269                           E->getQualifierLoc().getSourceRange());
4270    break;
4271
4272  case CXCursor_DeclRefExpr:
4273    if (DeclRefExpr *E = dyn_cast<DeclRefExpr>(getCursorExpr(C)))
4274      Pieces = buildPieces(NameFlags, false, E->getNameInfo(),
4275                           E->getQualifierLoc().getSourceRange(),
4276                           E->getExplicitTemplateArgsOpt());
4277    break;
4278
4279  case CXCursor_CallExpr:
4280    if (CXXOperatorCallExpr *OCE =
4281        dyn_cast<CXXOperatorCallExpr>(getCursorExpr(C))) {
4282      Expr *Callee = OCE->getCallee();
4283      if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Callee))
4284        Callee = ICE->getSubExpr();
4285
4286      if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Callee))
4287        Pieces = buildPieces(NameFlags, false, DRE->getNameInfo(),
4288                             DRE->getQualifierLoc().getSourceRange());
4289    }
4290    break;
4291
4292  default:
4293    break;
4294  }
4295
4296  if (Pieces.empty()) {
4297    if (PieceIndex == 0)
4298      return clang_getCursorExtent(C);
4299  } else if (PieceIndex < Pieces.size()) {
4300      SourceRange R = Pieces[PieceIndex];
4301      if (R.isValid())
4302        return cxloc::translateSourceRange(getCursorContext(C), R);
4303  }
4304
4305  return clang_getNullRange();
4306}
4307
4308void clang_enableStackTraces(void) {
4309  llvm::sys::PrintStackTraceOnErrorSignal();
4310}
4311
4312void clang_executeOnThread(void (*fn)(void*), void *user_data,
4313                           unsigned stack_size) {
4314  llvm::llvm_execute_on_thread(fn, user_data, stack_size);
4315}
4316
4317} // end: extern "C"
4318
4319//===----------------------------------------------------------------------===//
4320// Token-based Operations.
4321//===----------------------------------------------------------------------===//
4322
4323/* CXToken layout:
4324 *   int_data[0]: a CXTokenKind
4325 *   int_data[1]: starting token location
4326 *   int_data[2]: token length
4327 *   int_data[3]: reserved
4328 *   ptr_data: for identifiers and keywords, an IdentifierInfo*.
4329 *   otherwise unused.
4330 */
4331extern "C" {
4332
4333CXTokenKind clang_getTokenKind(CXToken CXTok) {
4334  return static_cast<CXTokenKind>(CXTok.int_data[0]);
4335}
4336
4337CXString clang_getTokenSpelling(CXTranslationUnit TU, CXToken CXTok) {
4338  switch (clang_getTokenKind(CXTok)) {
4339  case CXToken_Identifier:
4340  case CXToken_Keyword:
4341    // We know we have an IdentifierInfo*, so use that.
4342    return createCXString(static_cast<IdentifierInfo *>(CXTok.ptr_data)
4343                            ->getNameStart());
4344
4345  case CXToken_Literal: {
4346    // We have stashed the starting pointer in the ptr_data field. Use it.
4347    const char *Text = static_cast<const char *>(CXTok.ptr_data);
4348    return createCXString(StringRef(Text, CXTok.int_data[2]));
4349  }
4350
4351  case CXToken_Punctuation:
4352  case CXToken_Comment:
4353    break;
4354  }
4355
4356  // We have to find the starting buffer pointer the hard way, by
4357  // deconstructing the source location.
4358  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4359  if (!CXXUnit)
4360    return createCXString("");
4361
4362  SourceLocation Loc = SourceLocation::getFromRawEncoding(CXTok.int_data[1]);
4363  std::pair<FileID, unsigned> LocInfo
4364    = CXXUnit->getSourceManager().getDecomposedSpellingLoc(Loc);
4365  bool Invalid = false;
4366  StringRef Buffer
4367    = CXXUnit->getSourceManager().getBufferData(LocInfo.first, &Invalid);
4368  if (Invalid)
4369    return createCXString("");
4370
4371  return createCXString(Buffer.substr(LocInfo.second, CXTok.int_data[2]));
4372}
4373
4374CXSourceLocation clang_getTokenLocation(CXTranslationUnit TU, CXToken CXTok) {
4375  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4376  if (!CXXUnit)
4377    return clang_getNullLocation();
4378
4379  return cxloc::translateSourceLocation(CXXUnit->getASTContext(),
4380                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4381}
4382
4383CXSourceRange clang_getTokenExtent(CXTranslationUnit TU, CXToken CXTok) {
4384  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4385  if (!CXXUnit)
4386    return clang_getNullRange();
4387
4388  return cxloc::translateSourceRange(CXXUnit->getASTContext(),
4389                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4390}
4391
4392static void getTokens(ASTUnit *CXXUnit, SourceRange Range,
4393                      SmallVectorImpl<CXToken> &CXTokens) {
4394  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4395  std::pair<FileID, unsigned> BeginLocInfo
4396    = SourceMgr.getDecomposedLoc(Range.getBegin());
4397  std::pair<FileID, unsigned> EndLocInfo
4398    = SourceMgr.getDecomposedLoc(Range.getEnd());
4399
4400  // Cannot tokenize across files.
4401  if (BeginLocInfo.first != EndLocInfo.first)
4402    return;
4403
4404  // Create a lexer
4405  bool Invalid = false;
4406  StringRef Buffer
4407    = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4408  if (Invalid)
4409    return;
4410
4411  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4412            CXXUnit->getASTContext().getLangOptions(),
4413            Buffer.begin(), Buffer.data() + BeginLocInfo.second, Buffer.end());
4414  Lex.SetCommentRetentionState(true);
4415
4416  // Lex tokens until we hit the end of the range.
4417  const char *EffectiveBufferEnd = Buffer.data() + EndLocInfo.second;
4418  Token Tok;
4419  bool previousWasAt = false;
4420  do {
4421    // Lex the next token
4422    Lex.LexFromRawLexer(Tok);
4423    if (Tok.is(tok::eof))
4424      break;
4425
4426    // Initialize the CXToken.
4427    CXToken CXTok;
4428
4429    //   - Common fields
4430    CXTok.int_data[1] = Tok.getLocation().getRawEncoding();
4431    CXTok.int_data[2] = Tok.getLength();
4432    CXTok.int_data[3] = 0;
4433
4434    //   - Kind-specific fields
4435    if (Tok.isLiteral()) {
4436      CXTok.int_data[0] = CXToken_Literal;
4437      CXTok.ptr_data = (void *)Tok.getLiteralData();
4438    } else if (Tok.is(tok::raw_identifier)) {
4439      // Lookup the identifier to determine whether we have a keyword.
4440      IdentifierInfo *II
4441        = CXXUnit->getPreprocessor().LookUpIdentifierInfo(Tok);
4442
4443      if ((II->getObjCKeywordID() != tok::objc_not_keyword) && previousWasAt) {
4444        CXTok.int_data[0] = CXToken_Keyword;
4445      }
4446      else {
4447        CXTok.int_data[0] = Tok.is(tok::identifier)
4448          ? CXToken_Identifier
4449          : CXToken_Keyword;
4450      }
4451      CXTok.ptr_data = II;
4452    } else if (Tok.is(tok::comment)) {
4453      CXTok.int_data[0] = CXToken_Comment;
4454      CXTok.ptr_data = 0;
4455    } else {
4456      CXTok.int_data[0] = CXToken_Punctuation;
4457      CXTok.ptr_data = 0;
4458    }
4459    CXTokens.push_back(CXTok);
4460    previousWasAt = Tok.is(tok::at);
4461  } while (Lex.getBufferLocation() <= EffectiveBufferEnd);
4462}
4463
4464void clang_tokenize(CXTranslationUnit TU, CXSourceRange Range,
4465                    CXToken **Tokens, unsigned *NumTokens) {
4466  if (Tokens)
4467    *Tokens = 0;
4468  if (NumTokens)
4469    *NumTokens = 0;
4470
4471  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4472  if (!CXXUnit || !Tokens || !NumTokens)
4473    return;
4474
4475  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
4476
4477  SourceRange R = cxloc::translateCXSourceRange(Range);
4478  if (R.isInvalid())
4479    return;
4480
4481  SmallVector<CXToken, 32> CXTokens;
4482  getTokens(CXXUnit, R, CXTokens);
4483
4484  if (CXTokens.empty())
4485    return;
4486
4487  *Tokens = (CXToken *)malloc(sizeof(CXToken) * CXTokens.size());
4488  memmove(*Tokens, CXTokens.data(), sizeof(CXToken) * CXTokens.size());
4489  *NumTokens = CXTokens.size();
4490}
4491
4492void clang_disposeTokens(CXTranslationUnit TU,
4493                         CXToken *Tokens, unsigned NumTokens) {
4494  free(Tokens);
4495}
4496
4497} // end: extern "C"
4498
4499//===----------------------------------------------------------------------===//
4500// Token annotation APIs.
4501//===----------------------------------------------------------------------===//
4502
4503typedef llvm::DenseMap<unsigned, CXCursor> AnnotateTokensData;
4504static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4505                                                     CXCursor parent,
4506                                                     CXClientData client_data);
4507namespace {
4508class AnnotateTokensWorker {
4509  AnnotateTokensData &Annotated;
4510  CXToken *Tokens;
4511  CXCursor *Cursors;
4512  unsigned NumTokens;
4513  unsigned TokIdx;
4514  unsigned PreprocessingTokIdx;
4515  CursorVisitor AnnotateVis;
4516  SourceManager &SrcMgr;
4517  bool HasContextSensitiveKeywords;
4518
4519  bool MoreTokens() const { return TokIdx < NumTokens; }
4520  unsigned NextToken() const { return TokIdx; }
4521  void AdvanceToken() { ++TokIdx; }
4522  SourceLocation GetTokenLoc(unsigned tokI) {
4523    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4524  }
4525  bool isFunctionMacroToken(unsigned tokI) const {
4526    return Tokens[tokI].int_data[3] != 0;
4527  }
4528  SourceLocation getFunctionMacroTokenLoc(unsigned tokI) const {
4529    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[3]);
4530  }
4531
4532  void annotateAndAdvanceTokens(CXCursor, RangeComparisonResult, SourceRange);
4533  void annotateAndAdvanceFunctionMacroTokens(CXCursor, RangeComparisonResult,
4534                                             SourceRange);
4535
4536public:
4537  AnnotateTokensWorker(AnnotateTokensData &annotated,
4538                       CXToken *tokens, CXCursor *cursors, unsigned numTokens,
4539                       CXTranslationUnit tu, SourceRange RegionOfInterest)
4540    : Annotated(annotated), Tokens(tokens), Cursors(cursors),
4541      NumTokens(numTokens), TokIdx(0), PreprocessingTokIdx(0),
4542      AnnotateVis(tu,
4543                  AnnotateTokensVisitor, this,
4544                  /*VisitPreprocessorLast=*/true,
4545                  /*VisitIncludedEntities=*/false,
4546                  RegionOfInterest),
4547      SrcMgr(static_cast<ASTUnit*>(tu->TUData)->getSourceManager()),
4548      HasContextSensitiveKeywords(false) { }
4549
4550  void VisitChildren(CXCursor C) { AnnotateVis.VisitChildren(C); }
4551  enum CXChildVisitResult Visit(CXCursor cursor, CXCursor parent);
4552  void AnnotateTokens();
4553
4554  /// \brief Determine whether the annotator saw any cursors that have
4555  /// context-sensitive keywords.
4556  bool hasContextSensitiveKeywords() const {
4557    return HasContextSensitiveKeywords;
4558  }
4559};
4560}
4561
4562void AnnotateTokensWorker::AnnotateTokens() {
4563  // Walk the AST within the region of interest, annotating tokens
4564  // along the way.
4565  AnnotateVis.visitFileRegion();
4566
4567  for (unsigned I = 0 ; I < TokIdx ; ++I) {
4568    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4569    if (Pos != Annotated.end() &&
4570        (clang_isInvalid(Cursors[I].kind) ||
4571         Pos->second.kind != CXCursor_PreprocessingDirective))
4572      Cursors[I] = Pos->second;
4573  }
4574
4575  // Finish up annotating any tokens left.
4576  if (!MoreTokens())
4577    return;
4578
4579  const CXCursor &C = clang_getNullCursor();
4580  for (unsigned I = TokIdx ; I < NumTokens ; ++I) {
4581    if (I < PreprocessingTokIdx && clang_isPreprocessing(Cursors[I].kind))
4582      continue;
4583
4584    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4585    Cursors[I] = (Pos == Annotated.end()) ? C : Pos->second;
4586  }
4587}
4588
4589/// \brief It annotates and advances tokens with a cursor until the comparison
4590//// between the cursor location and the source range is the same as
4591/// \arg compResult.
4592///
4593/// Pass RangeBefore to annotate tokens with a cursor until a range is reached.
4594/// Pass RangeOverlap to annotate tokens inside a range.
4595void AnnotateTokensWorker::annotateAndAdvanceTokens(CXCursor updateC,
4596                                               RangeComparisonResult compResult,
4597                                               SourceRange range) {
4598  while (MoreTokens()) {
4599    const unsigned I = NextToken();
4600    if (isFunctionMacroToken(I))
4601      return annotateAndAdvanceFunctionMacroTokens(updateC, compResult, range);
4602
4603    SourceLocation TokLoc = GetTokenLoc(I);
4604    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4605      Cursors[I] = updateC;
4606      AdvanceToken();
4607      continue;
4608    }
4609    break;
4610  }
4611}
4612
4613/// \brief Special annotation handling for macro argument tokens.
4614void AnnotateTokensWorker::annotateAndAdvanceFunctionMacroTokens(
4615                                               CXCursor updateC,
4616                                               RangeComparisonResult compResult,
4617                                               SourceRange range) {
4618  assert(MoreTokens());
4619  assert(isFunctionMacroToken(NextToken()) &&
4620         "Should be called only for macro arg tokens");
4621
4622  // This works differently than annotateAndAdvanceTokens; because expanded
4623  // macro arguments can have arbitrary translation-unit source order, we do not
4624  // advance the token index one by one until a token fails the range test.
4625  // We only advance once past all of the macro arg tokens if all of them
4626  // pass the range test. If one of them fails we keep the token index pointing
4627  // at the start of the macro arg tokens so that the failing token will be
4628  // annotated by a subsequent annotation try.
4629
4630  bool atLeastOneCompFail = false;
4631
4632  unsigned I = NextToken();
4633  for (; I < NumTokens && isFunctionMacroToken(I); ++I) {
4634    SourceLocation TokLoc = getFunctionMacroTokenLoc(I);
4635    if (TokLoc.isFileID())
4636      continue; // not macro arg token, it's parens or comma.
4637    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4638      if (clang_isInvalid(clang_getCursorKind(Cursors[I])))
4639        Cursors[I] = updateC;
4640    } else
4641      atLeastOneCompFail = true;
4642  }
4643
4644  if (!atLeastOneCompFail)
4645    TokIdx = I; // All of the tokens were handled, advance beyond all of them.
4646}
4647
4648enum CXChildVisitResult
4649AnnotateTokensWorker::Visit(CXCursor cursor, CXCursor parent) {
4650  CXSourceLocation Loc = clang_getCursorLocation(cursor);
4651  SourceRange cursorRange = getRawCursorExtent(cursor);
4652  if (cursorRange.isInvalid())
4653    return CXChildVisit_Recurse;
4654
4655  if (!HasContextSensitiveKeywords) {
4656    // Objective-C properties can have context-sensitive keywords.
4657    if (cursor.kind == CXCursor_ObjCPropertyDecl) {
4658      if (ObjCPropertyDecl *Property
4659                  = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(cursor)))
4660        HasContextSensitiveKeywords = Property->getPropertyAttributesAsWritten() != 0;
4661    }
4662    // Objective-C methods can have context-sensitive keywords.
4663    else if (cursor.kind == CXCursor_ObjCInstanceMethodDecl ||
4664             cursor.kind == CXCursor_ObjCClassMethodDecl) {
4665      if (ObjCMethodDecl *Method
4666            = dyn_cast_or_null<ObjCMethodDecl>(getCursorDecl(cursor))) {
4667        if (Method->getObjCDeclQualifier())
4668          HasContextSensitiveKeywords = true;
4669        else {
4670          for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
4671                                           PEnd = Method->param_end();
4672               P != PEnd; ++P) {
4673            if ((*P)->getObjCDeclQualifier()) {
4674              HasContextSensitiveKeywords = true;
4675              break;
4676            }
4677          }
4678        }
4679      }
4680    }
4681    // C++ methods can have context-sensitive keywords.
4682    else if (cursor.kind == CXCursor_CXXMethod) {
4683      if (CXXMethodDecl *Method
4684                  = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(cursor))) {
4685        if (Method->hasAttr<FinalAttr>() || Method->hasAttr<OverrideAttr>())
4686          HasContextSensitiveKeywords = true;
4687      }
4688    }
4689    // C++ classes can have context-sensitive keywords.
4690    else if (cursor.kind == CXCursor_StructDecl ||
4691             cursor.kind == CXCursor_ClassDecl ||
4692             cursor.kind == CXCursor_ClassTemplate ||
4693             cursor.kind == CXCursor_ClassTemplatePartialSpecialization) {
4694      if (Decl *D = getCursorDecl(cursor))
4695        if (D->hasAttr<FinalAttr>())
4696          HasContextSensitiveKeywords = true;
4697    }
4698  }
4699
4700  if (clang_isPreprocessing(cursor.kind)) {
4701    // For macro expansions, just note where the beginning of the macro
4702    // expansion occurs.
4703    if (cursor.kind == CXCursor_MacroExpansion) {
4704      Annotated[Loc.int_data] = cursor;
4705      return CXChildVisit_Recurse;
4706    }
4707
4708    // Items in the preprocessing record are kept separate from items in
4709    // declarations, so we keep a separate token index.
4710    unsigned SavedTokIdx = TokIdx;
4711    TokIdx = PreprocessingTokIdx;
4712
4713    // Skip tokens up until we catch up to the beginning of the preprocessing
4714    // entry.
4715    while (MoreTokens()) {
4716      const unsigned I = NextToken();
4717      SourceLocation TokLoc = GetTokenLoc(I);
4718      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4719      case RangeBefore:
4720        AdvanceToken();
4721        continue;
4722      case RangeAfter:
4723      case RangeOverlap:
4724        break;
4725      }
4726      break;
4727    }
4728
4729    // Look at all of the tokens within this range.
4730    while (MoreTokens()) {
4731      const unsigned I = NextToken();
4732      SourceLocation TokLoc = GetTokenLoc(I);
4733      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4734      case RangeBefore:
4735        llvm_unreachable("Infeasible");
4736      case RangeAfter:
4737        break;
4738      case RangeOverlap:
4739        Cursors[I] = cursor;
4740        AdvanceToken();
4741        continue;
4742      }
4743      break;
4744    }
4745
4746    // Save the preprocessing token index; restore the non-preprocessing
4747    // token index.
4748    PreprocessingTokIdx = TokIdx;
4749    TokIdx = SavedTokIdx;
4750    return CXChildVisit_Recurse;
4751  }
4752
4753  if (cursorRange.isInvalid())
4754    return CXChildVisit_Continue;
4755
4756  SourceLocation L = SourceLocation::getFromRawEncoding(Loc.int_data);
4757
4758  // Adjust the annotated range based specific declarations.
4759  const enum CXCursorKind cursorK = clang_getCursorKind(cursor);
4760  if (cursorK >= CXCursor_FirstDecl && cursorK <= CXCursor_LastDecl) {
4761    Decl *D = cxcursor::getCursorDecl(cursor);
4762
4763    SourceLocation StartLoc;
4764    if (const DeclaratorDecl *DD = dyn_cast_or_null<DeclaratorDecl>(D)) {
4765      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
4766        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4767    } else if (TypedefDecl *Typedef = dyn_cast_or_null<TypedefDecl>(D)) {
4768      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
4769        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4770    }
4771
4772    if (StartLoc.isValid() && L.isValid() &&
4773        SrcMgr.isBeforeInTranslationUnit(StartLoc, L))
4774      cursorRange.setBegin(StartLoc);
4775  }
4776
4777  // If the location of the cursor occurs within a macro instantiation, record
4778  // the spelling location of the cursor in our annotation map.  We can then
4779  // paper over the token labelings during a post-processing step to try and
4780  // get cursor mappings for tokens that are the *arguments* of a macro
4781  // instantiation.
4782  if (L.isMacroID()) {
4783    unsigned rawEncoding = SrcMgr.getSpellingLoc(L).getRawEncoding();
4784    // Only invalidate the old annotation if it isn't part of a preprocessing
4785    // directive.  Here we assume that the default construction of CXCursor
4786    // results in CXCursor.kind being an initialized value (i.e., 0).  If
4787    // this isn't the case, we can fix by doing lookup + insertion.
4788
4789    CXCursor &oldC = Annotated[rawEncoding];
4790    if (!clang_isPreprocessing(oldC.kind))
4791      oldC = cursor;
4792  }
4793
4794  const enum CXCursorKind K = clang_getCursorKind(parent);
4795  const CXCursor updateC =
4796    (clang_isInvalid(K) || K == CXCursor_TranslationUnit)
4797     ? clang_getNullCursor() : parent;
4798
4799  annotateAndAdvanceTokens(updateC, RangeBefore, cursorRange);
4800
4801  // Avoid having the cursor of an expression "overwrite" the annotation of the
4802  // variable declaration that it belongs to.
4803  // This can happen for C++ constructor expressions whose range generally
4804  // include the variable declaration, e.g.:
4805  //  MyCXXClass foo; // Make sure we don't annotate 'foo' as a CallExpr cursor.
4806  if (clang_isExpression(cursorK)) {
4807    Expr *E = getCursorExpr(cursor);
4808    if (Decl *D = getCursorParentDecl(cursor)) {
4809      const unsigned I = NextToken();
4810      if (E->getLocStart().isValid() && D->getLocation().isValid() &&
4811          E->getLocStart() == D->getLocation() &&
4812          E->getLocStart() == GetTokenLoc(I)) {
4813        Cursors[I] = updateC;
4814        AdvanceToken();
4815      }
4816    }
4817  }
4818
4819  // Visit children to get their cursor information.
4820  const unsigned BeforeChildren = NextToken();
4821  VisitChildren(cursor);
4822  const unsigned AfterChildren = NextToken();
4823
4824  // Scan the tokens that are at the end of the cursor, but are not captured
4825  // but the child cursors.
4826  annotateAndAdvanceTokens(cursor, RangeOverlap, cursorRange);
4827
4828  // Scan the tokens that are at the beginning of the cursor, but are not
4829  // capture by the child cursors.
4830  for (unsigned I = BeforeChildren; I != AfterChildren; ++I) {
4831    if (!clang_isInvalid(clang_getCursorKind(Cursors[I])))
4832      break;
4833
4834    Cursors[I] = cursor;
4835  }
4836
4837  return CXChildVisit_Continue;
4838}
4839
4840static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4841                                                     CXCursor parent,
4842                                                     CXClientData client_data) {
4843  return static_cast<AnnotateTokensWorker*>(client_data)->Visit(cursor, parent);
4844}
4845
4846namespace {
4847
4848/// \brief Uses the macro expansions in the preprocessing record to find
4849/// and mark tokens that are macro arguments. This info is used by the
4850/// AnnotateTokensWorker.
4851class MarkMacroArgTokensVisitor {
4852  SourceManager &SM;
4853  CXToken *Tokens;
4854  unsigned NumTokens;
4855  unsigned CurIdx;
4856
4857public:
4858  MarkMacroArgTokensVisitor(SourceManager &SM,
4859                            CXToken *tokens, unsigned numTokens)
4860    : SM(SM), Tokens(tokens), NumTokens(numTokens), CurIdx(0) { }
4861
4862  CXChildVisitResult visit(CXCursor cursor, CXCursor parent) {
4863    if (cursor.kind != CXCursor_MacroExpansion)
4864      return CXChildVisit_Continue;
4865
4866    SourceRange macroRange = getCursorMacroExpansion(cursor)->getSourceRange();
4867    if (macroRange.getBegin() == macroRange.getEnd())
4868      return CXChildVisit_Continue; // it's not a function macro.
4869
4870    for (; CurIdx < NumTokens; ++CurIdx) {
4871      if (!SM.isBeforeInTranslationUnit(getTokenLoc(CurIdx),
4872                                        macroRange.getBegin()))
4873        break;
4874    }
4875
4876    if (CurIdx == NumTokens)
4877      return CXChildVisit_Break;
4878
4879    for (; CurIdx < NumTokens; ++CurIdx) {
4880      SourceLocation tokLoc = getTokenLoc(CurIdx);
4881      if (!SM.isBeforeInTranslationUnit(tokLoc, macroRange.getEnd()))
4882        break;
4883
4884      setFunctionMacroTokenLoc(CurIdx, SM.getMacroArgExpandedLocation(tokLoc));
4885    }
4886
4887    if (CurIdx == NumTokens)
4888      return CXChildVisit_Break;
4889
4890    return CXChildVisit_Continue;
4891  }
4892
4893private:
4894  SourceLocation getTokenLoc(unsigned tokI) {
4895    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4896  }
4897
4898  void setFunctionMacroTokenLoc(unsigned tokI, SourceLocation loc) {
4899    // The third field is reserved and currently not used. Use it here
4900    // to mark macro arg expanded tokens with their expanded locations.
4901    Tokens[tokI].int_data[3] = loc.getRawEncoding();
4902  }
4903};
4904
4905} // end anonymous namespace
4906
4907static CXChildVisitResult
4908MarkMacroArgTokensVisitorDelegate(CXCursor cursor, CXCursor parent,
4909                                  CXClientData client_data) {
4910  return static_cast<MarkMacroArgTokensVisitor*>(client_data)->visit(cursor,
4911                                                                     parent);
4912}
4913
4914namespace {
4915  struct clang_annotateTokens_Data {
4916    CXTranslationUnit TU;
4917    ASTUnit *CXXUnit;
4918    CXToken *Tokens;
4919    unsigned NumTokens;
4920    CXCursor *Cursors;
4921  };
4922}
4923
4924static void annotatePreprocessorTokens(CXTranslationUnit TU,
4925                                       SourceRange RegionOfInterest,
4926                                       AnnotateTokensData &Annotated) {
4927  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4928
4929  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4930  std::pair<FileID, unsigned> BeginLocInfo
4931    = SourceMgr.getDecomposedLoc(RegionOfInterest.getBegin());
4932  std::pair<FileID, unsigned> EndLocInfo
4933    = SourceMgr.getDecomposedLoc(RegionOfInterest.getEnd());
4934
4935  if (BeginLocInfo.first != EndLocInfo.first)
4936    return;
4937
4938  StringRef Buffer;
4939  bool Invalid = false;
4940  Buffer = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4941  if (Buffer.empty() || Invalid)
4942    return;
4943
4944  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4945            CXXUnit->getASTContext().getLangOptions(),
4946            Buffer.begin(), Buffer.data() + BeginLocInfo.second,
4947            Buffer.end());
4948  Lex.SetCommentRetentionState(true);
4949
4950  // Lex tokens in raw mode until we hit the end of the range, to avoid
4951  // entering #includes or expanding macros.
4952  while (true) {
4953    Token Tok;
4954    Lex.LexFromRawLexer(Tok);
4955
4956  reprocess:
4957    if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
4958      // We have found a preprocessing directive. Gobble it up so that we
4959      // don't see it while preprocessing these tokens later, but keep track
4960      // of all of the token locations inside this preprocessing directive so
4961      // that we can annotate them appropriately.
4962      //
4963      // FIXME: Some simple tests here could identify macro definitions and
4964      // #undefs, to provide specific cursor kinds for those.
4965      SmallVector<SourceLocation, 32> Locations;
4966      do {
4967        Locations.push_back(Tok.getLocation());
4968        Lex.LexFromRawLexer(Tok);
4969      } while (!Tok.isAtStartOfLine() && !Tok.is(tok::eof));
4970
4971      using namespace cxcursor;
4972      CXCursor Cursor
4973      = MakePreprocessingDirectiveCursor(SourceRange(Locations.front(),
4974                                                     Locations.back()),
4975                                         TU);
4976      for (unsigned I = 0, N = Locations.size(); I != N; ++I) {
4977        Annotated[Locations[I].getRawEncoding()] = Cursor;
4978      }
4979
4980      if (Tok.isAtStartOfLine())
4981        goto reprocess;
4982
4983      continue;
4984    }
4985
4986    if (Tok.is(tok::eof))
4987      break;
4988  }
4989}
4990
4991// This gets run a separate thread to avoid stack blowout.
4992static void clang_annotateTokensImpl(void *UserData) {
4993  CXTranslationUnit TU = ((clang_annotateTokens_Data*)UserData)->TU;
4994  ASTUnit *CXXUnit = ((clang_annotateTokens_Data*)UserData)->CXXUnit;
4995  CXToken *Tokens = ((clang_annotateTokens_Data*)UserData)->Tokens;
4996  const unsigned NumTokens = ((clang_annotateTokens_Data*)UserData)->NumTokens;
4997  CXCursor *Cursors = ((clang_annotateTokens_Data*)UserData)->Cursors;
4998
4999  // Determine the region of interest, which contains all of the tokens.
5000  SourceRange RegionOfInterest;
5001  RegionOfInterest.setBegin(
5002    cxloc::translateSourceLocation(clang_getTokenLocation(TU, Tokens[0])));
5003  RegionOfInterest.setEnd(
5004    cxloc::translateSourceLocation(clang_getTokenLocation(TU,
5005                                                         Tokens[NumTokens-1])));
5006
5007  // A mapping from the source locations found when re-lexing or traversing the
5008  // region of interest to the corresponding cursors.
5009  AnnotateTokensData Annotated;
5010
5011  // Relex the tokens within the source range to look for preprocessing
5012  // directives.
5013  annotatePreprocessorTokens(TU, RegionOfInterest, Annotated);
5014
5015  if (CXXUnit->getPreprocessor().getPreprocessingRecord()) {
5016    // Search and mark tokens that are macro argument expansions.
5017    MarkMacroArgTokensVisitor Visitor(CXXUnit->getSourceManager(),
5018                                      Tokens, NumTokens);
5019    CursorVisitor MacroArgMarker(TU,
5020                                 MarkMacroArgTokensVisitorDelegate, &Visitor,
5021                                 /*VisitPreprocessorLast=*/true,
5022                                 /*VisitIncludedEntities=*/false,
5023                                 RegionOfInterest);
5024    MacroArgMarker.visitPreprocessedEntitiesInRegion();
5025  }
5026
5027  // Annotate all of the source locations in the region of interest that map to
5028  // a specific cursor.
5029  AnnotateTokensWorker W(Annotated, Tokens, Cursors, NumTokens,
5030                         TU, RegionOfInterest);
5031
5032  // FIXME: We use a ridiculous stack size here because the data-recursion
5033  // algorithm uses a large stack frame than the non-data recursive version,
5034  // and AnnotationTokensWorker currently transforms the data-recursion
5035  // algorithm back into a traditional recursion by explicitly calling
5036  // VisitChildren().  We will need to remove this explicit recursive call.
5037  W.AnnotateTokens();
5038
5039  // If we ran into any entities that involve context-sensitive keywords,
5040  // take another pass through the tokens to mark them as such.
5041  if (W.hasContextSensitiveKeywords()) {
5042    for (unsigned I = 0; I != NumTokens; ++I) {
5043      if (clang_getTokenKind(Tokens[I]) != CXToken_Identifier)
5044        continue;
5045
5046      if (Cursors[I].kind == CXCursor_ObjCPropertyDecl) {
5047        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5048        if (ObjCPropertyDecl *Property
5049            = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(Cursors[I]))) {
5050          if (Property->getPropertyAttributesAsWritten() != 0 &&
5051              llvm::StringSwitch<bool>(II->getName())
5052              .Case("readonly", true)
5053              .Case("assign", true)
5054              .Case("unsafe_unretained", true)
5055              .Case("readwrite", true)
5056              .Case("retain", true)
5057              .Case("copy", true)
5058              .Case("nonatomic", true)
5059              .Case("atomic", true)
5060              .Case("getter", true)
5061              .Case("setter", true)
5062              .Case("strong", true)
5063              .Case("weak", true)
5064              .Default(false))
5065            Tokens[I].int_data[0] = CXToken_Keyword;
5066        }
5067        continue;
5068      }
5069
5070      if (Cursors[I].kind == CXCursor_ObjCInstanceMethodDecl ||
5071          Cursors[I].kind == CXCursor_ObjCClassMethodDecl) {
5072        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5073        if (llvm::StringSwitch<bool>(II->getName())
5074            .Case("in", true)
5075            .Case("out", true)
5076            .Case("inout", true)
5077            .Case("oneway", true)
5078            .Case("bycopy", true)
5079            .Case("byref", true)
5080            .Default(false))
5081          Tokens[I].int_data[0] = CXToken_Keyword;
5082        continue;
5083      }
5084
5085      if (Cursors[I].kind == CXCursor_CXXFinalAttr ||
5086          Cursors[I].kind == CXCursor_CXXOverrideAttr) {
5087        Tokens[I].int_data[0] = CXToken_Keyword;
5088        continue;
5089      }
5090    }
5091  }
5092}
5093
5094extern "C" {
5095
5096void clang_annotateTokens(CXTranslationUnit TU,
5097                          CXToken *Tokens, unsigned NumTokens,
5098                          CXCursor *Cursors) {
5099
5100  if (NumTokens == 0 || !Tokens || !Cursors)
5101    return;
5102
5103  // Any token we don't specifically annotate will have a NULL cursor.
5104  CXCursor C = clang_getNullCursor();
5105  for (unsigned I = 0; I != NumTokens; ++I)
5106    Cursors[I] = C;
5107
5108  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
5109  if (!CXXUnit)
5110    return;
5111
5112  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
5113
5114  clang_annotateTokens_Data data = { TU, CXXUnit, Tokens, NumTokens, Cursors };
5115  llvm::CrashRecoveryContext CRC;
5116  if (!RunSafely(CRC, clang_annotateTokensImpl, &data,
5117                 GetSafetyThreadStackSize() * 2)) {
5118    fprintf(stderr, "libclang: crash detected while annotating tokens\n");
5119  }
5120}
5121
5122} // end: extern "C"
5123
5124//===----------------------------------------------------------------------===//
5125// Operations for querying linkage of a cursor.
5126//===----------------------------------------------------------------------===//
5127
5128extern "C" {
5129CXLinkageKind clang_getCursorLinkage(CXCursor cursor) {
5130  if (!clang_isDeclaration(cursor.kind))
5131    return CXLinkage_Invalid;
5132
5133  Decl *D = cxcursor::getCursorDecl(cursor);
5134  if (NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
5135    switch (ND->getLinkage()) {
5136      case NoLinkage: return CXLinkage_NoLinkage;
5137      case InternalLinkage: return CXLinkage_Internal;
5138      case UniqueExternalLinkage: return CXLinkage_UniqueExternal;
5139      case ExternalLinkage: return CXLinkage_External;
5140    };
5141
5142  return CXLinkage_Invalid;
5143}
5144} // end: extern "C"
5145
5146//===----------------------------------------------------------------------===//
5147// Operations for querying language of a cursor.
5148//===----------------------------------------------------------------------===//
5149
5150static CXLanguageKind getDeclLanguage(const Decl *D) {
5151  if (!D)
5152    return CXLanguage_C;
5153
5154  switch (D->getKind()) {
5155    default:
5156      break;
5157    case Decl::ImplicitParam:
5158    case Decl::ObjCAtDefsField:
5159    case Decl::ObjCCategory:
5160    case Decl::ObjCCategoryImpl:
5161    case Decl::ObjCCompatibleAlias:
5162    case Decl::ObjCImplementation:
5163    case Decl::ObjCInterface:
5164    case Decl::ObjCIvar:
5165    case Decl::ObjCMethod:
5166    case Decl::ObjCProperty:
5167    case Decl::ObjCPropertyImpl:
5168    case Decl::ObjCProtocol:
5169      return CXLanguage_ObjC;
5170    case Decl::CXXConstructor:
5171    case Decl::CXXConversion:
5172    case Decl::CXXDestructor:
5173    case Decl::CXXMethod:
5174    case Decl::CXXRecord:
5175    case Decl::ClassTemplate:
5176    case Decl::ClassTemplatePartialSpecialization:
5177    case Decl::ClassTemplateSpecialization:
5178    case Decl::Friend:
5179    case Decl::FriendTemplate:
5180    case Decl::FunctionTemplate:
5181    case Decl::LinkageSpec:
5182    case Decl::Namespace:
5183    case Decl::NamespaceAlias:
5184    case Decl::NonTypeTemplateParm:
5185    case Decl::StaticAssert:
5186    case Decl::TemplateTemplateParm:
5187    case Decl::TemplateTypeParm:
5188    case Decl::UnresolvedUsingTypename:
5189    case Decl::UnresolvedUsingValue:
5190    case Decl::Using:
5191    case Decl::UsingDirective:
5192    case Decl::UsingShadow:
5193      return CXLanguage_CPlusPlus;
5194  }
5195
5196  return CXLanguage_C;
5197}
5198
5199extern "C" {
5200
5201enum CXAvailabilityKind clang_getCursorAvailability(CXCursor cursor) {
5202  if (clang_isDeclaration(cursor.kind))
5203    if (Decl *D = cxcursor::getCursorDecl(cursor)) {
5204      if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->isDeleted())
5205        return CXAvailability_Available;
5206
5207      switch (D->getAvailability()) {
5208      case AR_Available:
5209      case AR_NotYetIntroduced:
5210        return CXAvailability_Available;
5211
5212      case AR_Deprecated:
5213        return CXAvailability_Deprecated;
5214
5215      case AR_Unavailable:
5216        return CXAvailability_NotAvailable;
5217      }
5218    }
5219
5220  return CXAvailability_Available;
5221}
5222
5223CXLanguageKind clang_getCursorLanguage(CXCursor cursor) {
5224  if (clang_isDeclaration(cursor.kind))
5225    return getDeclLanguage(cxcursor::getCursorDecl(cursor));
5226
5227  return CXLanguage_Invalid;
5228}
5229
5230 /// \brief If the given cursor is the "templated" declaration
5231 /// descibing a class or function template, return the class or
5232 /// function template.
5233static Decl *maybeGetTemplateCursor(Decl *D) {
5234  if (!D)
5235    return 0;
5236
5237  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
5238    if (FunctionTemplateDecl *FunTmpl = FD->getDescribedFunctionTemplate())
5239      return FunTmpl;
5240
5241  if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D))
5242    if (ClassTemplateDecl *ClassTmpl = RD->getDescribedClassTemplate())
5243      return ClassTmpl;
5244
5245  return D;
5246}
5247
5248CXCursor clang_getCursorSemanticParent(CXCursor cursor) {
5249  if (clang_isDeclaration(cursor.kind)) {
5250    if (Decl *D = getCursorDecl(cursor)) {
5251      DeclContext *DC = D->getDeclContext();
5252      if (!DC)
5253        return clang_getNullCursor();
5254
5255      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5256                          getCursorTU(cursor));
5257    }
5258  }
5259
5260  if (clang_isStatement(cursor.kind) || clang_isExpression(cursor.kind)) {
5261    if (Decl *D = getCursorDecl(cursor))
5262      return MakeCXCursor(D, getCursorTU(cursor));
5263  }
5264
5265  return clang_getNullCursor();
5266}
5267
5268CXCursor clang_getCursorLexicalParent(CXCursor cursor) {
5269  if (clang_isDeclaration(cursor.kind)) {
5270    if (Decl *D = getCursorDecl(cursor)) {
5271      DeclContext *DC = D->getLexicalDeclContext();
5272      if (!DC)
5273        return clang_getNullCursor();
5274
5275      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5276                          getCursorTU(cursor));
5277    }
5278  }
5279
5280  // FIXME: Note that we can't easily compute the lexical context of a
5281  // statement or expression, so we return nothing.
5282  return clang_getNullCursor();
5283}
5284
5285void clang_getOverriddenCursors(CXCursor cursor,
5286                                CXCursor **overridden,
5287                                unsigned *num_overridden) {
5288  if (overridden)
5289    *overridden = 0;
5290  if (num_overridden)
5291    *num_overridden = 0;
5292  if (!overridden || !num_overridden)
5293    return;
5294
5295  SmallVector<CXCursor, 8> Overridden;
5296  cxcursor::getOverriddenCursors(cursor, Overridden);
5297
5298  // Don't allocate memory if we have no overriden cursors.
5299  if (Overridden.size() == 0)
5300    return;
5301
5302  *num_overridden = Overridden.size();
5303  *overridden = new CXCursor [Overridden.size()];
5304  std::copy(Overridden.begin(), Overridden.end(), *overridden);
5305}
5306
5307void clang_disposeOverriddenCursors(CXCursor *overridden) {
5308  delete [] overridden;
5309}
5310
5311CXFile clang_getIncludedFile(CXCursor cursor) {
5312  if (cursor.kind != CXCursor_InclusionDirective)
5313    return 0;
5314
5315  InclusionDirective *ID = getCursorInclusionDirective(cursor);
5316  return (void *)ID->getFile();
5317}
5318
5319} // end: extern "C"
5320
5321
5322//===----------------------------------------------------------------------===//
5323// C++ AST instrospection.
5324//===----------------------------------------------------------------------===//
5325
5326extern "C" {
5327unsigned clang_CXXMethod_isStatic(CXCursor C) {
5328  if (!clang_isDeclaration(C.kind))
5329    return 0;
5330
5331  CXXMethodDecl *Method = 0;
5332  Decl *D = cxcursor::getCursorDecl(C);
5333  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5334    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5335  else
5336    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5337  return (Method && Method->isStatic()) ? 1 : 0;
5338}
5339
5340unsigned clang_CXXMethod_isVirtual(CXCursor C) {
5341  if (!clang_isDeclaration(C.kind))
5342    return 0;
5343
5344  CXXMethodDecl *Method = 0;
5345  Decl *D = cxcursor::getCursorDecl(C);
5346  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5347    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5348  else
5349    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5350  return (Method && Method->isVirtual()) ? 1 : 0;
5351}
5352} // end: extern "C"
5353
5354//===----------------------------------------------------------------------===//
5355// Attribute introspection.
5356//===----------------------------------------------------------------------===//
5357
5358extern "C" {
5359CXType clang_getIBOutletCollectionType(CXCursor C) {
5360  if (C.kind != CXCursor_IBOutletCollectionAttr)
5361    return cxtype::MakeCXType(QualType(), cxcursor::getCursorTU(C));
5362
5363  IBOutletCollectionAttr *A =
5364    cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(C));
5365
5366  return cxtype::MakeCXType(A->getInterface(), cxcursor::getCursorTU(C));
5367}
5368} // end: extern "C"
5369
5370//===----------------------------------------------------------------------===//
5371// Inspecting memory usage.
5372//===----------------------------------------------------------------------===//
5373
5374typedef std::vector<CXTUResourceUsageEntry> MemUsageEntries;
5375
5376static inline void createCXTUResourceUsageEntry(MemUsageEntries &entries,
5377                                              enum CXTUResourceUsageKind k,
5378                                              unsigned long amount) {
5379  CXTUResourceUsageEntry entry = { k, amount };
5380  entries.push_back(entry);
5381}
5382
5383extern "C" {
5384
5385const char *clang_getTUResourceUsageName(CXTUResourceUsageKind kind) {
5386  const char *str = "";
5387  switch (kind) {
5388    case CXTUResourceUsage_AST:
5389      str = "ASTContext: expressions, declarations, and types";
5390      break;
5391    case CXTUResourceUsage_Identifiers:
5392      str = "ASTContext: identifiers";
5393      break;
5394    case CXTUResourceUsage_Selectors:
5395      str = "ASTContext: selectors";
5396      break;
5397    case CXTUResourceUsage_GlobalCompletionResults:
5398      str = "Code completion: cached global results";
5399      break;
5400    case CXTUResourceUsage_SourceManagerContentCache:
5401      str = "SourceManager: content cache allocator";
5402      break;
5403    case CXTUResourceUsage_AST_SideTables:
5404      str = "ASTContext: side tables";
5405      break;
5406    case CXTUResourceUsage_SourceManager_Membuffer_Malloc:
5407      str = "SourceManager: malloc'ed memory buffers";
5408      break;
5409    case CXTUResourceUsage_SourceManager_Membuffer_MMap:
5410      str = "SourceManager: mmap'ed memory buffers";
5411      break;
5412    case CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc:
5413      str = "ExternalASTSource: malloc'ed memory buffers";
5414      break;
5415    case CXTUResourceUsage_ExternalASTSource_Membuffer_MMap:
5416      str = "ExternalASTSource: mmap'ed memory buffers";
5417      break;
5418    case CXTUResourceUsage_Preprocessor:
5419      str = "Preprocessor: malloc'ed memory";
5420      break;
5421    case CXTUResourceUsage_PreprocessingRecord:
5422      str = "Preprocessor: PreprocessingRecord";
5423      break;
5424    case CXTUResourceUsage_SourceManager_DataStructures:
5425      str = "SourceManager: data structures and tables";
5426      break;
5427    case CXTUResourceUsage_Preprocessor_HeaderSearch:
5428      str = "Preprocessor: header search tables";
5429      break;
5430  }
5431  return str;
5432}
5433
5434CXTUResourceUsage clang_getCXTUResourceUsage(CXTranslationUnit TU) {
5435  if (!TU) {
5436    CXTUResourceUsage usage = { (void*) 0, 0, 0 };
5437    return usage;
5438  }
5439
5440  ASTUnit *astUnit = static_cast<ASTUnit*>(TU->TUData);
5441  llvm::OwningPtr<MemUsageEntries> entries(new MemUsageEntries());
5442  ASTContext &astContext = astUnit->getASTContext();
5443
5444  // How much memory is used by AST nodes and types?
5445  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST,
5446    (unsigned long) astContext.getASTAllocatedMemory());
5447
5448  // How much memory is used by identifiers?
5449  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Identifiers,
5450    (unsigned long) astContext.Idents.getAllocator().getTotalMemory());
5451
5452  // How much memory is used for selectors?
5453  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Selectors,
5454    (unsigned long) astContext.Selectors.getTotalMemory());
5455
5456  // How much memory is used by ASTContext's side tables?
5457  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST_SideTables,
5458    (unsigned long) astContext.getSideTableAllocatedMemory());
5459
5460  // How much memory is used for caching global code completion results?
5461  unsigned long completionBytes = 0;
5462  if (GlobalCodeCompletionAllocator *completionAllocator =
5463      astUnit->getCachedCompletionAllocator().getPtr()) {
5464    completionBytes = completionAllocator->getTotalMemory();
5465  }
5466  createCXTUResourceUsageEntry(*entries,
5467                               CXTUResourceUsage_GlobalCompletionResults,
5468                               completionBytes);
5469
5470  // How much memory is being used by SourceManager's content cache?
5471  createCXTUResourceUsageEntry(*entries,
5472          CXTUResourceUsage_SourceManagerContentCache,
5473          (unsigned long) astContext.getSourceManager().getContentCacheSize());
5474
5475  // How much memory is being used by the MemoryBuffer's in SourceManager?
5476  const SourceManager::MemoryBufferSizes &srcBufs =
5477    astUnit->getSourceManager().getMemoryBufferSizes();
5478
5479  createCXTUResourceUsageEntry(*entries,
5480                               CXTUResourceUsage_SourceManager_Membuffer_Malloc,
5481                               (unsigned long) srcBufs.malloc_bytes);
5482  createCXTUResourceUsageEntry(*entries,
5483                               CXTUResourceUsage_SourceManager_Membuffer_MMap,
5484                               (unsigned long) srcBufs.mmap_bytes);
5485  createCXTUResourceUsageEntry(*entries,
5486                               CXTUResourceUsage_SourceManager_DataStructures,
5487                               (unsigned long) astContext.getSourceManager()
5488                                .getDataStructureSizes());
5489
5490  // How much memory is being used by the ExternalASTSource?
5491  if (ExternalASTSource *esrc = astContext.getExternalSource()) {
5492    const ExternalASTSource::MemoryBufferSizes &sizes =
5493      esrc->getMemoryBufferSizes();
5494
5495    createCXTUResourceUsageEntry(*entries,
5496      CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc,
5497                                 (unsigned long) sizes.malloc_bytes);
5498    createCXTUResourceUsageEntry(*entries,
5499      CXTUResourceUsage_ExternalASTSource_Membuffer_MMap,
5500                                 (unsigned long) sizes.mmap_bytes);
5501  }
5502
5503  // How much memory is being used by the Preprocessor?
5504  Preprocessor &pp = astUnit->getPreprocessor();
5505  createCXTUResourceUsageEntry(*entries,
5506                               CXTUResourceUsage_Preprocessor,
5507                               pp.getTotalMemory());
5508
5509  if (PreprocessingRecord *pRec = pp.getPreprocessingRecord()) {
5510    createCXTUResourceUsageEntry(*entries,
5511                                 CXTUResourceUsage_PreprocessingRecord,
5512                                 pRec->getTotalMemory());
5513  }
5514
5515  createCXTUResourceUsageEntry(*entries,
5516                               CXTUResourceUsage_Preprocessor_HeaderSearch,
5517                               pp.getHeaderSearchInfo().getTotalMemory());
5518
5519  CXTUResourceUsage usage = { (void*) entries.get(),
5520                            (unsigned) entries->size(),
5521                            entries->size() ? &(*entries)[0] : 0 };
5522  entries.take();
5523  return usage;
5524}
5525
5526void clang_disposeCXTUResourceUsage(CXTUResourceUsage usage) {
5527  if (usage.data)
5528    delete (MemUsageEntries*) usage.data;
5529}
5530
5531} // end extern "C"
5532
5533void clang::PrintLibclangResourceUsage(CXTranslationUnit TU) {
5534  CXTUResourceUsage Usage = clang_getCXTUResourceUsage(TU);
5535  for (unsigned I = 0; I != Usage.numEntries; ++I)
5536    fprintf(stderr, "  %s: %lu\n",
5537            clang_getTUResourceUsageName(Usage.entries[I].kind),
5538            Usage.entries[I].amount);
5539
5540  clang_disposeCXTUResourceUsage(Usage);
5541}
5542
5543//===----------------------------------------------------------------------===//
5544// Misc. utility functions.
5545//===----------------------------------------------------------------------===//
5546
5547/// Default to using an 8 MB stack size on "safety" threads.
5548static unsigned SafetyStackThreadSize = 8 << 20;
5549
5550namespace clang {
5551
5552bool RunSafely(llvm::CrashRecoveryContext &CRC,
5553               void (*Fn)(void*), void *UserData,
5554               unsigned Size) {
5555  if (!Size)
5556    Size = GetSafetyThreadStackSize();
5557  if (Size)
5558    return CRC.RunSafelyOnThread(Fn, UserData, Size);
5559  return CRC.RunSafely(Fn, UserData);
5560}
5561
5562unsigned GetSafetyThreadStackSize() {
5563  return SafetyStackThreadSize;
5564}
5565
5566void SetSafetyThreadStackSize(unsigned Value) {
5567  SafetyStackThreadSize = Value;
5568}
5569
5570}
5571
5572extern "C" {
5573
5574CXString clang_getClangVersion() {
5575  return createCXString(getClangFullVersion());
5576}
5577
5578} // end: extern "C"
5579
5580