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