CIndex.cpp revision e1d4330adaaa7faf093e725c9c993207eb2d778a 
1//===- CIndex.cpp - Clang-C Source Indexing Library -----------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the main API hooks in the Clang-C Source Indexing
11// library.
12//
13//===----------------------------------------------------------------------===//
14
15#include "CIndexer.h"
16#include "CXCursor.h"
17#include "CXTranslationUnit.h"
18#include "CXString.h"
19#include "CXType.h"
20#include "CXSourceLocation.h"
21#include "CIndexDiagnostic.h"
22#include "CursorVisitor.h"
23
24#include "clang/Basic/Version.h"
25
26#include "clang/AST/StmtVisitor.h"
27#include "clang/Basic/Diagnostic.h"
28#include "clang/Frontend/ASTUnit.h"
29#include "clang/Frontend/CompilerInstance.h"
30#include "clang/Frontend/FrontendDiagnostic.h"
31#include "clang/Lex/Lexer.h"
32#include "clang/Lex/HeaderSearch.h"
33#include "clang/Lex/PreprocessingRecord.h"
34#include "clang/Lex/Preprocessor.h"
35#include "llvm/ADT/STLExtras.h"
36#include "llvm/ADT/Optional.h"
37#include "llvm/ADT/StringSwitch.h"
38#include "clang/Analysis/Support/SaveAndRestore.h"
39#include "llvm/Support/CrashRecoveryContext.h"
40#include "llvm/Support/PrettyStackTrace.h"
41#include "llvm/Support/MemoryBuffer.h"
42#include "llvm/Support/raw_ostream.h"
43#include "llvm/Support/Timer.h"
44#include "llvm/Support/Mutex.h"
45#include "llvm/Support/Program.h"
46#include "llvm/Support/Signals.h"
47#include "llvm/Support/Threading.h"
48#include "llvm/Support/Compiler.h"
49
50using namespace clang;
51using namespace clang::cxcursor;
52using namespace clang::cxstring;
53using namespace clang::cxtu;
54
55CXTranslationUnit cxtu::MakeCXTranslationUnit(ASTUnit *TU) {
56  if (!TU)
57    return 0;
58  CXTranslationUnit D = new CXTranslationUnitImpl();
59  D->TUData = TU;
60  D->StringPool = createCXStringPool();
61  D->Diagnostics = 0;
62  return D;
63}
64
65cxtu::CXTUOwner::~CXTUOwner() {
66  if (TU)
67    clang_disposeTranslationUnit(TU);
68}
69
70/// \brief Compare two source ranges to determine their relative position in
71/// the translation unit.
72static RangeComparisonResult RangeCompare(SourceManager &SM,
73                                          SourceRange R1,
74                                          SourceRange R2) {
75  assert(R1.isValid() && "First range is invalid?");
76  assert(R2.isValid() && "Second range is invalid?");
77  if (R1.getEnd() != R2.getBegin() &&
78      SM.isBeforeInTranslationUnit(R1.getEnd(), R2.getBegin()))
79    return RangeBefore;
80  if (R2.getEnd() != R1.getBegin() &&
81      SM.isBeforeInTranslationUnit(R2.getEnd(), R1.getBegin()))
82    return RangeAfter;
83  return RangeOverlap;
84}
85
86/// \brief Determine if a source location falls within, before, or after a
87///   a given source range.
88static RangeComparisonResult LocationCompare(SourceManager &SM,
89                                             SourceLocation L, SourceRange R) {
90  assert(R.isValid() && "First range is invalid?");
91  assert(L.isValid() && "Second range is invalid?");
92  if (L == R.getBegin() || L == R.getEnd())
93    return RangeOverlap;
94  if (SM.isBeforeInTranslationUnit(L, R.getBegin()))
95    return RangeBefore;
96  if (SM.isBeforeInTranslationUnit(R.getEnd(), L))
97    return RangeAfter;
98  return RangeOverlap;
99}
100
101/// \brief Translate a Clang source range into a CIndex source range.
102///
103/// Clang internally represents ranges where the end location points to the
104/// start of the token at the end. However, for external clients it is more
105/// useful to have a CXSourceRange be a proper half-open interval. This routine
106/// does the appropriate translation.
107CXSourceRange cxloc::translateSourceRange(const SourceManager &SM,
108                                          const LangOptions &LangOpts,
109                                          const CharSourceRange &R) {
110  // We want the last character in this location, so we will adjust the
111  // location accordingly.
112  SourceLocation EndLoc = R.getEnd();
113  if (EndLoc.isValid() && EndLoc.isMacroID())
114    EndLoc = SM.getExpansionRange(EndLoc).second;
115  if (R.isTokenRange() && !EndLoc.isInvalid() && EndLoc.isFileID()) {
116    unsigned Length = Lexer::MeasureTokenLength(EndLoc, SM, LangOpts);
117    EndLoc = EndLoc.getLocWithOffset(Length);
118  }
119
120  CXSourceRange Result = { { (void *)&SM, (void *)&LangOpts },
121                           R.getBegin().getRawEncoding(),
122                           EndLoc.getRawEncoding() };
123  return Result;
124}
125
126//===----------------------------------------------------------------------===//
127// Cursor visitor.
128//===----------------------------------------------------------------------===//
129
130static SourceRange getRawCursorExtent(CXCursor C);
131static SourceRange getFullCursorExtent(CXCursor C, SourceManager &SrcMgr);
132
133
134RangeComparisonResult CursorVisitor::CompareRegionOfInterest(SourceRange R) {
135  return RangeCompare(AU->getSourceManager(), R, RegionOfInterest);
136}
137
138/// \brief Visit the given cursor and, if requested by the visitor,
139/// its children.
140///
141/// \param Cursor the cursor to visit.
142///
143/// \param CheckRegionOfInterest if true, then the caller already checked that
144/// this cursor is within the region of interest.
145///
146/// \returns true if the visitation should be aborted, false if it
147/// should continue.
148bool CursorVisitor::Visit(CXCursor Cursor, bool CheckedRegionOfInterest) {
149  if (clang_isInvalid(Cursor.kind))
150    return false;
151
152  if (clang_isDeclaration(Cursor.kind)) {
153    Decl *D = getCursorDecl(Cursor);
154    if (!D) {
155      assert(0 && "Invalid declaration cursor");
156      return true; // abort.
157    }
158
159    // Ignore implicit declarations, unless it's an objc method because
160    // currently we should report implicit methods for properties when indexing.
161    if (D->isImplicit() && !isa<ObjCMethodDecl>(D))
162      return false;
163  }
164
165  // If we have a range of interest, and this cursor doesn't intersect with it,
166  // we're done.
167  if (RegionOfInterest.isValid() && !CheckedRegionOfInterest) {
168    SourceRange Range = getRawCursorExtent(Cursor);
169    if (Range.isInvalid() || CompareRegionOfInterest(Range))
170      return false;
171  }
172
173  switch (Visitor(Cursor, Parent, ClientData)) {
174  case CXChildVisit_Break:
175    return true;
176
177  case CXChildVisit_Continue:
178    return false;
179
180  case CXChildVisit_Recurse:
181    return VisitChildren(Cursor);
182  }
183
184  llvm_unreachable("Invalid CXChildVisitResult!");
185}
186
187static bool visitPreprocessedEntitiesInRange(SourceRange R,
188                                             PreprocessingRecord &PPRec,
189                                             CursorVisitor &Visitor) {
190  SourceManager &SM = Visitor.getASTUnit()->getSourceManager();
191  FileID FID;
192
193  if (!Visitor.shouldVisitIncludedEntities()) {
194    // If the begin/end of the range lie in the same FileID, do the optimization
195    // where we skip preprocessed entities that do not come from the same FileID.
196    FID = SM.getFileID(SM.getFileLoc(R.getBegin()));
197    if (FID != SM.getFileID(SM.getFileLoc(R.getEnd())))
198      FID = FileID();
199  }
200
201  std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
202    Entities = PPRec.getPreprocessedEntitiesInRange(R);
203  return Visitor.visitPreprocessedEntities(Entities.first, Entities.second,
204                                           PPRec, FID);
205}
206
207void CursorVisitor::visitFileRegion() {
208  if (RegionOfInterest.isInvalid())
209    return;
210
211  ASTUnit *Unit = static_cast<ASTUnit *>(TU->TUData);
212  SourceManager &SM = Unit->getSourceManager();
213
214  std::pair<FileID, unsigned>
215    Begin = SM.getDecomposedLoc(SM.getFileLoc(RegionOfInterest.getBegin())),
216    End = SM.getDecomposedLoc(SM.getFileLoc(RegionOfInterest.getEnd()));
217
218  if (End.first != Begin.first) {
219    // If the end does not reside in the same file, try to recover by
220    // picking the end of the file of begin location.
221    End.first = Begin.first;
222    End.second = SM.getFileIDSize(Begin.first);
223  }
224
225  assert(Begin.first == End.first);
226  if (Begin.second > End.second)
227    return;
228
229  FileID File = Begin.first;
230  unsigned Offset = Begin.second;
231  unsigned Length = End.second - Begin.second;
232
233  if (!VisitDeclsOnly && !VisitPreprocessorLast)
234    if (visitPreprocessedEntitiesInRegion())
235      return; // visitation break.
236
237  visitDeclsFromFileRegion(File, Offset, Length);
238
239  if (!VisitDeclsOnly && VisitPreprocessorLast)
240    visitPreprocessedEntitiesInRegion();
241}
242
243static bool isInLexicalContext(Decl *D, DeclContext *DC) {
244  if (!DC)
245    return false;
246
247  for (DeclContext *DeclDC = D->getLexicalDeclContext();
248         DeclDC; DeclDC = DeclDC->getLexicalParent()) {
249    if (DeclDC == DC)
250      return true;
251  }
252  return false;
253}
254
255void CursorVisitor::visitDeclsFromFileRegion(FileID File,
256                                             unsigned Offset, unsigned Length) {
257  ASTUnit *Unit = static_cast<ASTUnit *>(TU->TUData);
258  SourceManager &SM = Unit->getSourceManager();
259  SourceRange Range = RegionOfInterest;
260
261  SmallVector<Decl *, 16> Decls;
262  Unit->findFileRegionDecls(File, Offset, Length, Decls);
263
264  // If we didn't find any file level decls for the file, try looking at the
265  // file that it was included from.
266  while (Decls.empty() || Decls.front()->isTopLevelDeclInObjCContainer()) {
267    bool Invalid = false;
268    const SrcMgr::SLocEntry &SLEntry = SM.getSLocEntry(File, &Invalid);
269    if (Invalid)
270      return;
271
272    SourceLocation Outer;
273    if (SLEntry.isFile())
274      Outer = SLEntry.getFile().getIncludeLoc();
275    else
276      Outer = SLEntry.getExpansion().getExpansionLocStart();
277    if (Outer.isInvalid())
278      return;
279
280    llvm::tie(File, Offset) = SM.getDecomposedExpansionLoc(Outer);
281    Length = 0;
282    Unit->findFileRegionDecls(File, Offset, Length, Decls);
283  }
284
285  assert(!Decls.empty());
286
287  bool VisitedAtLeastOnce = false;
288  DeclContext *CurDC = 0;
289  SmallVector<Decl *, 16>::iterator DIt = Decls.begin();
290  for (SmallVector<Decl *, 16>::iterator DE = Decls.end(); DIt != DE; ++DIt) {
291    Decl *D = *DIt;
292    if (D->getSourceRange().isInvalid())
293      continue;
294
295    if (isInLexicalContext(D, CurDC))
296      continue;
297
298    CurDC = dyn_cast<DeclContext>(D);
299
300    if (TagDecl *TD = dyn_cast<TagDecl>(D))
301      if (!TD->isFreeStanding())
302        continue;
303
304    RangeComparisonResult CompRes = RangeCompare(SM, D->getSourceRange(),Range);
305    if (CompRes == RangeBefore)
306      continue;
307    if (CompRes == RangeAfter)
308      break;
309
310    assert(CompRes == RangeOverlap);
311    VisitedAtLeastOnce = true;
312
313    if (isa<ObjCContainerDecl>(D)) {
314      FileDI_current = &DIt;
315      FileDE_current = DE;
316    } else {
317      FileDI_current = 0;
318    }
319
320    if (Visit(MakeCXCursor(D, TU, Range), /*CheckedRegionOfInterest=*/true))
321      break;
322  }
323
324  if (VisitedAtLeastOnce)
325    return;
326
327  // No Decls overlapped with the range. Move up the lexical context until there
328  // is a context that contains the range or we reach the translation unit
329  // level.
330  DeclContext *DC = DIt == Decls.begin() ? (*DIt)->getLexicalDeclContext()
331                                         : (*(DIt-1))->getLexicalDeclContext();
332
333  while (DC && !DC->isTranslationUnit()) {
334    Decl *D = cast<Decl>(DC);
335    SourceRange CurDeclRange = D->getSourceRange();
336    if (CurDeclRange.isInvalid())
337      break;
338
339    if (RangeCompare(SM, CurDeclRange, Range) == RangeOverlap) {
340      Visit(MakeCXCursor(D, TU, Range), /*CheckedRegionOfInterest=*/true);
341      break;
342    }
343
344    DC = D->getLexicalDeclContext();
345  }
346}
347
348bool CursorVisitor::visitPreprocessedEntitiesInRegion() {
349  if (!AU->getPreprocessor().getPreprocessingRecord())
350    return false;
351
352  PreprocessingRecord &PPRec
353    = *AU->getPreprocessor().getPreprocessingRecord();
354  SourceManager &SM = AU->getSourceManager();
355
356  if (RegionOfInterest.isValid()) {
357    SourceRange MappedRange = AU->mapRangeToPreamble(RegionOfInterest);
358    SourceLocation B = MappedRange.getBegin();
359    SourceLocation E = MappedRange.getEnd();
360
361    if (AU->isInPreambleFileID(B)) {
362      if (SM.isLoadedSourceLocation(E))
363        return visitPreprocessedEntitiesInRange(SourceRange(B, E),
364                                                 PPRec, *this);
365
366      // Beginning of range lies in the preamble but it also extends beyond
367      // it into the main file. Split the range into 2 parts, one covering
368      // the preamble and another covering the main file. This allows subsequent
369      // calls to visitPreprocessedEntitiesInRange to accept a source range that
370      // lies in the same FileID, allowing it to skip preprocessed entities that
371      // do not come from the same FileID.
372      bool breaked =
373        visitPreprocessedEntitiesInRange(
374                                   SourceRange(B, AU->getEndOfPreambleFileID()),
375                                          PPRec, *this);
376      if (breaked) return true;
377      return visitPreprocessedEntitiesInRange(
378                                    SourceRange(AU->getStartOfMainFileID(), E),
379                                        PPRec, *this);
380    }
381
382    return visitPreprocessedEntitiesInRange(SourceRange(B, E), PPRec, *this);
383  }
384
385  bool OnlyLocalDecls
386    = !AU->isMainFileAST() && AU->getOnlyLocalDecls();
387
388  if (OnlyLocalDecls)
389    return visitPreprocessedEntities(PPRec.local_begin(), PPRec.local_end(),
390                                     PPRec);
391
392  return visitPreprocessedEntities(PPRec.begin(), PPRec.end(), PPRec);
393}
394
395template<typename InputIterator>
396bool CursorVisitor::visitPreprocessedEntities(InputIterator First,
397                                              InputIterator Last,
398                                              PreprocessingRecord &PPRec,
399                                              FileID FID) {
400  for (; First != Last; ++First) {
401    if (!FID.isInvalid() && !PPRec.isEntityInFileID(First, FID))
402      continue;
403
404    PreprocessedEntity *PPE = *First;
405    if (MacroExpansion *ME = dyn_cast<MacroExpansion>(PPE)) {
406      if (Visit(MakeMacroExpansionCursor(ME, TU)))
407        return true;
408
409      continue;
410    }
411
412    if (MacroDefinition *MD = dyn_cast<MacroDefinition>(PPE)) {
413      if (Visit(MakeMacroDefinitionCursor(MD, TU)))
414        return true;
415
416      continue;
417    }
418
419    if (InclusionDirective *ID = dyn_cast<InclusionDirective>(PPE)) {
420      if (Visit(MakeInclusionDirectiveCursor(ID, TU)))
421        return true;
422
423      continue;
424    }
425  }
426
427  return false;
428}
429
430/// \brief Visit the children of the given cursor.
431///
432/// \returns true if the visitation should be aborted, false if it
433/// should continue.
434bool CursorVisitor::VisitChildren(CXCursor Cursor) {
435  if (clang_isReference(Cursor.kind) &&
436      Cursor.kind != CXCursor_CXXBaseSpecifier) {
437    // By definition, references have no children.
438    return false;
439  }
440
441  // Set the Parent field to Cursor, then back to its old value once we're
442  // done.
443  SetParentRAII SetParent(Parent, StmtParent, Cursor);
444
445  if (clang_isDeclaration(Cursor.kind)) {
446    Decl *D = getCursorDecl(Cursor);
447    if (!D)
448      return false;
449
450    return VisitAttributes(D) || Visit(D);
451  }
452
453  if (clang_isStatement(Cursor.kind)) {
454    if (Stmt *S = getCursorStmt(Cursor))
455      return Visit(S);
456
457    return false;
458  }
459
460  if (clang_isExpression(Cursor.kind)) {
461    if (Expr *E = getCursorExpr(Cursor))
462      return Visit(E);
463
464    return false;
465  }
466
467  if (clang_isTranslationUnit(Cursor.kind)) {
468    CXTranslationUnit tu = getCursorTU(Cursor);
469    ASTUnit *CXXUnit = static_cast<ASTUnit*>(tu->TUData);
470
471    int VisitOrder[2] = { VisitPreprocessorLast, !VisitPreprocessorLast };
472    for (unsigned I = 0; I != 2; ++I) {
473      if (VisitOrder[I]) {
474        if (!CXXUnit->isMainFileAST() && CXXUnit->getOnlyLocalDecls() &&
475            RegionOfInterest.isInvalid()) {
476          for (ASTUnit::top_level_iterator TL = CXXUnit->top_level_begin(),
477                                        TLEnd = CXXUnit->top_level_end();
478               TL != TLEnd; ++TL) {
479            if (Visit(MakeCXCursor(*TL, tu, RegionOfInterest), true))
480              return true;
481          }
482        } else if (VisitDeclContext(
483                                CXXUnit->getASTContext().getTranslationUnitDecl()))
484          return true;
485        continue;
486      }
487
488      // Walk the preprocessing record.
489      if (CXXUnit->getPreprocessor().getPreprocessingRecord())
490        visitPreprocessedEntitiesInRegion();
491    }
492
493    return false;
494  }
495
496  if (Cursor.kind == CXCursor_CXXBaseSpecifier) {
497    if (CXXBaseSpecifier *Base = getCursorCXXBaseSpecifier(Cursor)) {
498      if (TypeSourceInfo *BaseTSInfo = Base->getTypeSourceInfo()) {
499        return Visit(BaseTSInfo->getTypeLoc());
500      }
501    }
502  }
503
504  if (Cursor.kind == CXCursor_IBOutletCollectionAttr) {
505    IBOutletCollectionAttr *A =
506      cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(Cursor));
507    if (const ObjCInterfaceType *InterT = A->getInterface()->getAs<ObjCInterfaceType>())
508      return Visit(cxcursor::MakeCursorObjCClassRef(InterT->getInterface(),
509                                                    A->getInterfaceLoc(), TU));
510  }
511
512  // Nothing to visit at the moment.
513  return false;
514}
515
516bool CursorVisitor::VisitBlockDecl(BlockDecl *B) {
517  if (TypeSourceInfo *TSInfo = B->getSignatureAsWritten())
518    if (Visit(TSInfo->getTypeLoc()))
519        return true;
520
521  if (Stmt *Body = B->getBody())
522    return Visit(MakeCXCursor(Body, StmtParent, TU, RegionOfInterest));
523
524  return false;
525}
526
527llvm::Optional<bool> CursorVisitor::shouldVisitCursor(CXCursor Cursor) {
528  if (RegionOfInterest.isValid()) {
529    SourceRange Range = getFullCursorExtent(Cursor, AU->getSourceManager());
530    if (Range.isInvalid())
531      return llvm::Optional<bool>();
532
533    switch (CompareRegionOfInterest(Range)) {
534    case RangeBefore:
535      // This declaration comes before the region of interest; skip it.
536      return llvm::Optional<bool>();
537
538    case RangeAfter:
539      // This declaration comes after the region of interest; we're done.
540      return false;
541
542    case RangeOverlap:
543      // This declaration overlaps the region of interest; visit it.
544      break;
545    }
546  }
547  return true;
548}
549
550bool CursorVisitor::VisitDeclContext(DeclContext *DC) {
551  DeclContext::decl_iterator I = DC->decls_begin(), E = DC->decls_end();
552
553  // FIXME: Eventually remove.  This part of a hack to support proper
554  // iteration over all Decls contained lexically within an ObjC container.
555  SaveAndRestore<DeclContext::decl_iterator*> DI_saved(DI_current, &I);
556  SaveAndRestore<DeclContext::decl_iterator> DE_saved(DE_current, E);
557
558  for ( ; I != E; ++I) {
559    Decl *D = *I;
560    if (D->getLexicalDeclContext() != DC)
561      continue;
562    CXCursor Cursor = MakeCXCursor(D, TU, RegionOfInterest);
563
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_ObjCEncodeExpr:
3295      return createCXString("ObjCEncodeExpr");
3296  case CXCursor_ObjCSelectorExpr:
3297      return createCXString("ObjCSelectorExpr");
3298  case CXCursor_ObjCProtocolExpr:
3299      return createCXString("ObjCProtocolExpr");
3300  case CXCursor_ObjCBridgedCastExpr:
3301      return createCXString("ObjCBridgedCastExpr");
3302  case CXCursor_BlockExpr:
3303      return createCXString("BlockExpr");
3304  case CXCursor_PackExpansionExpr:
3305      return createCXString("PackExpansionExpr");
3306  case CXCursor_SizeOfPackExpr:
3307      return createCXString("SizeOfPackExpr");
3308  case CXCursor_LambdaExpr:
3309    return createCXString("LambdaExpr");
3310  case CXCursor_UnexposedExpr:
3311      return createCXString("UnexposedExpr");
3312  case CXCursor_DeclRefExpr:
3313      return createCXString("DeclRefExpr");
3314  case CXCursor_MemberRefExpr:
3315      return createCXString("MemberRefExpr");
3316  case CXCursor_CallExpr:
3317      return createCXString("CallExpr");
3318  case CXCursor_ObjCMessageExpr:
3319      return createCXString("ObjCMessageExpr");
3320  case CXCursor_UnexposedStmt:
3321      return createCXString("UnexposedStmt");
3322  case CXCursor_DeclStmt:
3323      return createCXString("DeclStmt");
3324  case CXCursor_LabelStmt:
3325      return createCXString("LabelStmt");
3326  case CXCursor_CompoundStmt:
3327      return createCXString("CompoundStmt");
3328  case CXCursor_CaseStmt:
3329      return createCXString("CaseStmt");
3330  case CXCursor_DefaultStmt:
3331      return createCXString("DefaultStmt");
3332  case CXCursor_IfStmt:
3333      return createCXString("IfStmt");
3334  case CXCursor_SwitchStmt:
3335      return createCXString("SwitchStmt");
3336  case CXCursor_WhileStmt:
3337      return createCXString("WhileStmt");
3338  case CXCursor_DoStmt:
3339      return createCXString("DoStmt");
3340  case CXCursor_ForStmt:
3341      return createCXString("ForStmt");
3342  case CXCursor_GotoStmt:
3343      return createCXString("GotoStmt");
3344  case CXCursor_IndirectGotoStmt:
3345      return createCXString("IndirectGotoStmt");
3346  case CXCursor_ContinueStmt:
3347      return createCXString("ContinueStmt");
3348  case CXCursor_BreakStmt:
3349      return createCXString("BreakStmt");
3350  case CXCursor_ReturnStmt:
3351      return createCXString("ReturnStmt");
3352  case CXCursor_AsmStmt:
3353      return createCXString("AsmStmt");
3354  case CXCursor_ObjCAtTryStmt:
3355      return createCXString("ObjCAtTryStmt");
3356  case CXCursor_ObjCAtCatchStmt:
3357      return createCXString("ObjCAtCatchStmt");
3358  case CXCursor_ObjCAtFinallyStmt:
3359      return createCXString("ObjCAtFinallyStmt");
3360  case CXCursor_ObjCAtThrowStmt:
3361      return createCXString("ObjCAtThrowStmt");
3362  case CXCursor_ObjCAtSynchronizedStmt:
3363      return createCXString("ObjCAtSynchronizedStmt");
3364  case CXCursor_ObjCAutoreleasePoolStmt:
3365      return createCXString("ObjCAutoreleasePoolStmt");
3366  case CXCursor_ObjCForCollectionStmt:
3367      return createCXString("ObjCForCollectionStmt");
3368  case CXCursor_CXXCatchStmt:
3369      return createCXString("CXXCatchStmt");
3370  case CXCursor_CXXTryStmt:
3371      return createCXString("CXXTryStmt");
3372  case CXCursor_CXXForRangeStmt:
3373      return createCXString("CXXForRangeStmt");
3374  case CXCursor_SEHTryStmt:
3375      return createCXString("SEHTryStmt");
3376  case CXCursor_SEHExceptStmt:
3377      return createCXString("SEHExceptStmt");
3378  case CXCursor_SEHFinallyStmt:
3379      return createCXString("SEHFinallyStmt");
3380  case CXCursor_NullStmt:
3381      return createCXString("NullStmt");
3382  case CXCursor_InvalidFile:
3383      return createCXString("InvalidFile");
3384  case CXCursor_InvalidCode:
3385    return createCXString("InvalidCode");
3386  case CXCursor_NoDeclFound:
3387      return createCXString("NoDeclFound");
3388  case CXCursor_NotImplemented:
3389      return createCXString("NotImplemented");
3390  case CXCursor_TranslationUnit:
3391      return createCXString("TranslationUnit");
3392  case CXCursor_UnexposedAttr:
3393      return createCXString("UnexposedAttr");
3394  case CXCursor_IBActionAttr:
3395      return createCXString("attribute(ibaction)");
3396  case CXCursor_IBOutletAttr:
3397     return createCXString("attribute(iboutlet)");
3398  case CXCursor_IBOutletCollectionAttr:
3399      return createCXString("attribute(iboutletcollection)");
3400  case CXCursor_CXXFinalAttr:
3401      return createCXString("attribute(final)");
3402  case CXCursor_CXXOverrideAttr:
3403      return createCXString("attribute(override)");
3404  case CXCursor_AnnotateAttr:
3405    return createCXString("attribute(annotate)");
3406  case CXCursor_AsmLabelAttr:
3407    return createCXString("asm label");
3408  case CXCursor_PreprocessingDirective:
3409    return createCXString("preprocessing directive");
3410  case CXCursor_MacroDefinition:
3411    return createCXString("macro definition");
3412  case CXCursor_MacroExpansion:
3413    return createCXString("macro expansion");
3414  case CXCursor_InclusionDirective:
3415    return createCXString("inclusion directive");
3416  case CXCursor_Namespace:
3417    return createCXString("Namespace");
3418  case CXCursor_LinkageSpec:
3419    return createCXString("LinkageSpec");
3420  case CXCursor_CXXBaseSpecifier:
3421    return createCXString("C++ base class specifier");
3422  case CXCursor_Constructor:
3423    return createCXString("CXXConstructor");
3424  case CXCursor_Destructor:
3425    return createCXString("CXXDestructor");
3426  case CXCursor_ConversionFunction:
3427    return createCXString("CXXConversion");
3428  case CXCursor_TemplateTypeParameter:
3429    return createCXString("TemplateTypeParameter");
3430  case CXCursor_NonTypeTemplateParameter:
3431    return createCXString("NonTypeTemplateParameter");
3432  case CXCursor_TemplateTemplateParameter:
3433    return createCXString("TemplateTemplateParameter");
3434  case CXCursor_FunctionTemplate:
3435    return createCXString("FunctionTemplate");
3436  case CXCursor_ClassTemplate:
3437    return createCXString("ClassTemplate");
3438  case CXCursor_ClassTemplatePartialSpecialization:
3439    return createCXString("ClassTemplatePartialSpecialization");
3440  case CXCursor_NamespaceAlias:
3441    return createCXString("NamespaceAlias");
3442  case CXCursor_UsingDirective:
3443    return createCXString("UsingDirective");
3444  case CXCursor_UsingDeclaration:
3445    return createCXString("UsingDeclaration");
3446  case CXCursor_TypeAliasDecl:
3447    return createCXString("TypeAliasDecl");
3448  case CXCursor_ObjCSynthesizeDecl:
3449    return createCXString("ObjCSynthesizeDecl");
3450  case CXCursor_ObjCDynamicDecl:
3451    return createCXString("ObjCDynamicDecl");
3452  case CXCursor_CXXAccessSpecifier:
3453    return createCXString("CXXAccessSpecifier");
3454  }
3455
3456  llvm_unreachable("Unhandled CXCursorKind");
3457}
3458
3459struct GetCursorData {
3460  SourceLocation TokenBeginLoc;
3461  bool PointsAtMacroArgExpansion;
3462  CXCursor &BestCursor;
3463
3464  GetCursorData(SourceManager &SM,
3465                SourceLocation tokenBegin, CXCursor &outputCursor)
3466    : TokenBeginLoc(tokenBegin), BestCursor(outputCursor) {
3467    PointsAtMacroArgExpansion = SM.isMacroArgExpansion(tokenBegin);
3468  }
3469};
3470
3471static enum CXChildVisitResult GetCursorVisitor(CXCursor cursor,
3472                                                CXCursor parent,
3473                                                CXClientData client_data) {
3474  GetCursorData *Data = static_cast<GetCursorData *>(client_data);
3475  CXCursor *BestCursor = &Data->BestCursor;
3476
3477  // If we point inside a macro argument we should provide info of what the
3478  // token is so use the actual cursor, don't replace it with a macro expansion
3479  // cursor.
3480  if (cursor.kind == CXCursor_MacroExpansion && Data->PointsAtMacroArgExpansion)
3481    return CXChildVisit_Recurse;
3482
3483  if (clang_isDeclaration(cursor.kind)) {
3484    // Avoid having the implicit methods override the property decls.
3485    if (ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(getCursorDecl(cursor)))
3486      if (MD->isImplicit())
3487        return CXChildVisit_Break;
3488  }
3489
3490  if (clang_isExpression(cursor.kind) &&
3491      clang_isDeclaration(BestCursor->kind)) {
3492    if (Decl *D = getCursorDecl(*BestCursor)) {
3493      // Avoid having the cursor of an expression replace the declaration cursor
3494      // when the expression source range overlaps the declaration range.
3495      // This can happen for C++ constructor expressions whose range generally
3496      // include the variable declaration, e.g.:
3497      //  MyCXXClass foo; // Make sure pointing at 'foo' returns a VarDecl cursor.
3498      if (D->getLocation().isValid() && Data->TokenBeginLoc.isValid() &&
3499          D->getLocation() == Data->TokenBeginLoc)
3500        return CXChildVisit_Break;
3501    }
3502  }
3503
3504  // If our current best cursor is the construction of a temporary object,
3505  // don't replace that cursor with a type reference, because we want
3506  // clang_getCursor() to point at the constructor.
3507  if (clang_isExpression(BestCursor->kind) &&
3508      isa<CXXTemporaryObjectExpr>(getCursorExpr(*BestCursor)) &&
3509      cursor.kind == CXCursor_TypeRef) {
3510    // Keep the cursor pointing at CXXTemporaryObjectExpr but also mark it
3511    // as having the actual point on the type reference.
3512    *BestCursor = getTypeRefedCallExprCursor(*BestCursor);
3513    return CXChildVisit_Recurse;
3514  }
3515
3516  *BestCursor = cursor;
3517  return CXChildVisit_Recurse;
3518}
3519
3520CXCursor clang_getCursor(CXTranslationUnit TU, CXSourceLocation Loc) {
3521  if (!TU)
3522    return clang_getNullCursor();
3523
3524  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
3525  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
3526
3527  SourceLocation SLoc = cxloc::translateSourceLocation(Loc);
3528  CXCursor Result = cxcursor::getCursor(TU, SLoc);
3529
3530  bool Logging = getenv("LIBCLANG_LOGGING");
3531  if (Logging) {
3532    CXFile SearchFile;
3533    unsigned SearchLine, SearchColumn;
3534    CXFile ResultFile;
3535    unsigned ResultLine, ResultColumn;
3536    CXString SearchFileName, ResultFileName, KindSpelling, USR;
3537    const char *IsDef = clang_isCursorDefinition(Result)? " (Definition)" : "";
3538    CXSourceLocation ResultLoc = clang_getCursorLocation(Result);
3539
3540    clang_getExpansionLocation(Loc, &SearchFile, &SearchLine, &SearchColumn, 0);
3541    clang_getExpansionLocation(ResultLoc, &ResultFile, &ResultLine,
3542                               &ResultColumn, 0);
3543    SearchFileName = clang_getFileName(SearchFile);
3544    ResultFileName = clang_getFileName(ResultFile);
3545    KindSpelling = clang_getCursorKindSpelling(Result.kind);
3546    USR = clang_getCursorUSR(Result);
3547    fprintf(stderr, "clang_getCursor(%s:%d:%d) = %s(%s:%d:%d):%s%s\n",
3548            clang_getCString(SearchFileName), SearchLine, SearchColumn,
3549            clang_getCString(KindSpelling),
3550            clang_getCString(ResultFileName), ResultLine, ResultColumn,
3551            clang_getCString(USR), IsDef);
3552    clang_disposeString(SearchFileName);
3553    clang_disposeString(ResultFileName);
3554    clang_disposeString(KindSpelling);
3555    clang_disposeString(USR);
3556
3557    CXCursor Definition = clang_getCursorDefinition(Result);
3558    if (!clang_equalCursors(Definition, clang_getNullCursor())) {
3559      CXSourceLocation DefinitionLoc = clang_getCursorLocation(Definition);
3560      CXString DefinitionKindSpelling
3561                                = clang_getCursorKindSpelling(Definition.kind);
3562      CXFile DefinitionFile;
3563      unsigned DefinitionLine, DefinitionColumn;
3564      clang_getExpansionLocation(DefinitionLoc, &DefinitionFile,
3565                                 &DefinitionLine, &DefinitionColumn, 0);
3566      CXString DefinitionFileName = clang_getFileName(DefinitionFile);
3567      fprintf(stderr, "  -> %s(%s:%d:%d)\n",
3568              clang_getCString(DefinitionKindSpelling),
3569              clang_getCString(DefinitionFileName),
3570              DefinitionLine, DefinitionColumn);
3571      clang_disposeString(DefinitionFileName);
3572      clang_disposeString(DefinitionKindSpelling);
3573    }
3574  }
3575
3576  return Result;
3577}
3578
3579CXCursor clang_getNullCursor(void) {
3580  return MakeCXCursorInvalid(CXCursor_InvalidFile);
3581}
3582
3583unsigned clang_equalCursors(CXCursor X, CXCursor Y) {
3584  return X == Y;
3585}
3586
3587unsigned clang_hashCursor(CXCursor C) {
3588  unsigned Index = 0;
3589  if (clang_isExpression(C.kind) || clang_isStatement(C.kind))
3590    Index = 1;
3591
3592  return llvm::DenseMapInfo<std::pair<unsigned, void*> >::getHashValue(
3593                                        std::make_pair(C.kind, C.data[Index]));
3594}
3595
3596unsigned clang_isInvalid(enum CXCursorKind K) {
3597  return K >= CXCursor_FirstInvalid && K <= CXCursor_LastInvalid;
3598}
3599
3600unsigned clang_isDeclaration(enum CXCursorKind K) {
3601  return K >= CXCursor_FirstDecl && K <= CXCursor_LastDecl;
3602}
3603
3604unsigned clang_isReference(enum CXCursorKind K) {
3605  return K >= CXCursor_FirstRef && K <= CXCursor_LastRef;
3606}
3607
3608unsigned clang_isExpression(enum CXCursorKind K) {
3609  return K >= CXCursor_FirstExpr && K <= CXCursor_LastExpr;
3610}
3611
3612unsigned clang_isStatement(enum CXCursorKind K) {
3613  return K >= CXCursor_FirstStmt && K <= CXCursor_LastStmt;
3614}
3615
3616unsigned clang_isAttribute(enum CXCursorKind K) {
3617    return K >= CXCursor_FirstAttr && K <= CXCursor_LastAttr;
3618}
3619
3620unsigned clang_isTranslationUnit(enum CXCursorKind K) {
3621  return K == CXCursor_TranslationUnit;
3622}
3623
3624unsigned clang_isPreprocessing(enum CXCursorKind K) {
3625  return K >= CXCursor_FirstPreprocessing && K <= CXCursor_LastPreprocessing;
3626}
3627
3628unsigned clang_isUnexposed(enum CXCursorKind K) {
3629  switch (K) {
3630    case CXCursor_UnexposedDecl:
3631    case CXCursor_UnexposedExpr:
3632    case CXCursor_UnexposedStmt:
3633    case CXCursor_UnexposedAttr:
3634      return true;
3635    default:
3636      return false;
3637  }
3638}
3639
3640CXCursorKind clang_getCursorKind(CXCursor C) {
3641  return C.kind;
3642}
3643
3644CXSourceLocation clang_getCursorLocation(CXCursor C) {
3645  if (clang_isReference(C.kind)) {
3646    switch (C.kind) {
3647    case CXCursor_ObjCSuperClassRef: {
3648      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3649        = getCursorObjCSuperClassRef(C);
3650      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3651    }
3652
3653    case CXCursor_ObjCProtocolRef: {
3654      std::pair<ObjCProtocolDecl *, SourceLocation> P
3655        = getCursorObjCProtocolRef(C);
3656      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3657    }
3658
3659    case CXCursor_ObjCClassRef: {
3660      std::pair<ObjCInterfaceDecl *, SourceLocation> P
3661        = getCursorObjCClassRef(C);
3662      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3663    }
3664
3665    case CXCursor_TypeRef: {
3666      std::pair<TypeDecl *, SourceLocation> P = getCursorTypeRef(C);
3667      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3668    }
3669
3670    case CXCursor_TemplateRef: {
3671      std::pair<TemplateDecl *, SourceLocation> P = getCursorTemplateRef(C);
3672      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3673    }
3674
3675    case CXCursor_NamespaceRef: {
3676      std::pair<NamedDecl *, SourceLocation> P = getCursorNamespaceRef(C);
3677      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3678    }
3679
3680    case CXCursor_MemberRef: {
3681      std::pair<FieldDecl *, SourceLocation> P = getCursorMemberRef(C);
3682      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3683    }
3684
3685    case CXCursor_VariableRef: {
3686      std::pair<VarDecl *, SourceLocation> P = getCursorVariableRef(C);
3687      return cxloc::translateSourceLocation(P.first->getASTContext(), P.second);
3688    }
3689
3690    case CXCursor_CXXBaseSpecifier: {
3691      CXXBaseSpecifier *BaseSpec = getCursorCXXBaseSpecifier(C);
3692      if (!BaseSpec)
3693        return clang_getNullLocation();
3694
3695      if (TypeSourceInfo *TSInfo = BaseSpec->getTypeSourceInfo())
3696        return cxloc::translateSourceLocation(getCursorContext(C),
3697                                            TSInfo->getTypeLoc().getBeginLoc());
3698
3699      return cxloc::translateSourceLocation(getCursorContext(C),
3700                                        BaseSpec->getSourceRange().getBegin());
3701    }
3702
3703    case CXCursor_LabelRef: {
3704      std::pair<LabelStmt *, SourceLocation> P = getCursorLabelRef(C);
3705      return cxloc::translateSourceLocation(getCursorContext(C), P.second);
3706    }
3707
3708    case CXCursor_OverloadedDeclRef:
3709      return cxloc::translateSourceLocation(getCursorContext(C),
3710                                          getCursorOverloadedDeclRef(C).second);
3711
3712    default:
3713      // FIXME: Need a way to enumerate all non-reference cases.
3714      llvm_unreachable("Missed a reference kind");
3715    }
3716  }
3717
3718  if (clang_isExpression(C.kind))
3719    return cxloc::translateSourceLocation(getCursorContext(C),
3720                                   getLocationFromExpr(getCursorExpr(C)));
3721
3722  if (clang_isStatement(C.kind))
3723    return cxloc::translateSourceLocation(getCursorContext(C),
3724                                          getCursorStmt(C)->getLocStart());
3725
3726  if (C.kind == CXCursor_PreprocessingDirective) {
3727    SourceLocation L = cxcursor::getCursorPreprocessingDirective(C).getBegin();
3728    return cxloc::translateSourceLocation(getCursorContext(C), L);
3729  }
3730
3731  if (C.kind == CXCursor_MacroExpansion) {
3732    SourceLocation L
3733      = cxcursor::getCursorMacroExpansion(C)->getSourceRange().getBegin();
3734    return cxloc::translateSourceLocation(getCursorContext(C), L);
3735  }
3736
3737  if (C.kind == CXCursor_MacroDefinition) {
3738    SourceLocation L = cxcursor::getCursorMacroDefinition(C)->getLocation();
3739    return cxloc::translateSourceLocation(getCursorContext(C), L);
3740  }
3741
3742  if (C.kind == CXCursor_InclusionDirective) {
3743    SourceLocation L
3744      = cxcursor::getCursorInclusionDirective(C)->getSourceRange().getBegin();
3745    return cxloc::translateSourceLocation(getCursorContext(C), L);
3746  }
3747
3748  if (C.kind < CXCursor_FirstDecl || C.kind > CXCursor_LastDecl)
3749    return clang_getNullLocation();
3750
3751  Decl *D = getCursorDecl(C);
3752  if (!D)
3753    return clang_getNullLocation();
3754
3755  SourceLocation Loc = D->getLocation();
3756  // FIXME: Multiple variables declared in a single declaration
3757  // currently lack the information needed to correctly determine their
3758  // ranges when accounting for the type-specifier.  We use context
3759  // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3760  // and if so, whether it is the first decl.
3761  if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3762    if (!cxcursor::isFirstInDeclGroup(C))
3763      Loc = VD->getLocation();
3764  }
3765
3766  return cxloc::translateSourceLocation(getCursorContext(C), Loc);
3767}
3768
3769} // end extern "C"
3770
3771CXCursor cxcursor::getCursor(CXTranslationUnit TU, SourceLocation SLoc) {
3772  assert(TU);
3773
3774  // Guard against an invalid SourceLocation, or we may assert in one
3775  // of the following calls.
3776  if (SLoc.isInvalid())
3777    return clang_getNullCursor();
3778
3779  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
3780
3781  // Translate the given source location to make it point at the beginning of
3782  // the token under the cursor.
3783  SLoc = Lexer::GetBeginningOfToken(SLoc, CXXUnit->getSourceManager(),
3784                                    CXXUnit->getASTContext().getLangOptions());
3785
3786  CXCursor Result = MakeCXCursorInvalid(CXCursor_NoDeclFound);
3787  if (SLoc.isValid()) {
3788    GetCursorData ResultData(CXXUnit->getSourceManager(), SLoc, Result);
3789    CursorVisitor CursorVis(TU, GetCursorVisitor, &ResultData,
3790                            /*VisitPreprocessorLast=*/true,
3791                            /*VisitIncludedEntities=*/false,
3792                            SourceLocation(SLoc));
3793    CursorVis.visitFileRegion();
3794  }
3795
3796  return Result;
3797}
3798
3799static SourceRange getRawCursorExtent(CXCursor C) {
3800  if (clang_isReference(C.kind)) {
3801    switch (C.kind) {
3802    case CXCursor_ObjCSuperClassRef:
3803      return  getCursorObjCSuperClassRef(C).second;
3804
3805    case CXCursor_ObjCProtocolRef:
3806      return getCursorObjCProtocolRef(C).second;
3807
3808    case CXCursor_ObjCClassRef:
3809      return getCursorObjCClassRef(C).second;
3810
3811    case CXCursor_TypeRef:
3812      return getCursorTypeRef(C).second;
3813
3814    case CXCursor_TemplateRef:
3815      return getCursorTemplateRef(C).second;
3816
3817    case CXCursor_NamespaceRef:
3818      return getCursorNamespaceRef(C).second;
3819
3820    case CXCursor_MemberRef:
3821      return getCursorMemberRef(C).second;
3822
3823    case CXCursor_CXXBaseSpecifier:
3824      return getCursorCXXBaseSpecifier(C)->getSourceRange();
3825
3826    case CXCursor_LabelRef:
3827      return getCursorLabelRef(C).second;
3828
3829    case CXCursor_OverloadedDeclRef:
3830      return getCursorOverloadedDeclRef(C).second;
3831
3832    case CXCursor_VariableRef:
3833      return getCursorVariableRef(C).second;
3834
3835    default:
3836      // FIXME: Need a way to enumerate all non-reference cases.
3837      llvm_unreachable("Missed a reference kind");
3838    }
3839  }
3840
3841  if (clang_isExpression(C.kind))
3842    return getCursorExpr(C)->getSourceRange();
3843
3844  if (clang_isStatement(C.kind))
3845    return getCursorStmt(C)->getSourceRange();
3846
3847  if (clang_isAttribute(C.kind))
3848    return getCursorAttr(C)->getRange();
3849
3850  if (C.kind == CXCursor_PreprocessingDirective)
3851    return cxcursor::getCursorPreprocessingDirective(C);
3852
3853  if (C.kind == CXCursor_MacroExpansion) {
3854    ASTUnit *TU = getCursorASTUnit(C);
3855    SourceRange Range = cxcursor::getCursorMacroExpansion(C)->getSourceRange();
3856    return TU->mapRangeFromPreamble(Range);
3857  }
3858
3859  if (C.kind == CXCursor_MacroDefinition) {
3860    ASTUnit *TU = getCursorASTUnit(C);
3861    SourceRange Range = cxcursor::getCursorMacroDefinition(C)->getSourceRange();
3862    return TU->mapRangeFromPreamble(Range);
3863  }
3864
3865  if (C.kind == CXCursor_InclusionDirective) {
3866    ASTUnit *TU = getCursorASTUnit(C);
3867    SourceRange Range = cxcursor::getCursorInclusionDirective(C)->getSourceRange();
3868    return TU->mapRangeFromPreamble(Range);
3869  }
3870
3871  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3872    Decl *D = cxcursor::getCursorDecl(C);
3873    if (!D)
3874      return SourceRange();
3875
3876    SourceRange R = D->getSourceRange();
3877    // FIXME: Multiple variables declared in a single declaration
3878    // currently lack the information needed to correctly determine their
3879    // ranges when accounting for the type-specifier.  We use context
3880    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3881    // and if so, whether it is the first decl.
3882    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3883      if (!cxcursor::isFirstInDeclGroup(C))
3884        R.setBegin(VD->getLocation());
3885    }
3886    return R;
3887  }
3888  return SourceRange();
3889}
3890
3891/// \brief Retrieves the "raw" cursor extent, which is then extended to include
3892/// the decl-specifier-seq for declarations.
3893static SourceRange getFullCursorExtent(CXCursor C, SourceManager &SrcMgr) {
3894  if (C.kind >= CXCursor_FirstDecl && C.kind <= CXCursor_LastDecl) {
3895    Decl *D = cxcursor::getCursorDecl(C);
3896    if (!D)
3897      return SourceRange();
3898
3899    SourceRange R = D->getSourceRange();
3900
3901    // Adjust the start of the location for declarations preceded by
3902    // declaration specifiers.
3903    SourceLocation StartLoc;
3904    if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(D)) {
3905      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
3906        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3907    } else if (TypedefDecl *Typedef = dyn_cast<TypedefDecl>(D)) {
3908      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
3909        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
3910    }
3911
3912    if (StartLoc.isValid() && R.getBegin().isValid() &&
3913        SrcMgr.isBeforeInTranslationUnit(StartLoc, R.getBegin()))
3914      R.setBegin(StartLoc);
3915
3916    // FIXME: Multiple variables declared in a single declaration
3917    // currently lack the information needed to correctly determine their
3918    // ranges when accounting for the type-specifier.  We use context
3919    // stored in the CXCursor to determine if the VarDecl is in a DeclGroup,
3920    // and if so, whether it is the first decl.
3921    if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
3922      if (!cxcursor::isFirstInDeclGroup(C))
3923        R.setBegin(VD->getLocation());
3924    }
3925
3926    return R;
3927  }
3928
3929  return getRawCursorExtent(C);
3930}
3931
3932extern "C" {
3933
3934CXSourceRange clang_getCursorExtent(CXCursor C) {
3935  SourceRange R = getRawCursorExtent(C);
3936  if (R.isInvalid())
3937    return clang_getNullRange();
3938
3939  return cxloc::translateSourceRange(getCursorContext(C), R);
3940}
3941
3942CXCursor clang_getCursorReferenced(CXCursor C) {
3943  if (clang_isInvalid(C.kind))
3944    return clang_getNullCursor();
3945
3946  CXTranslationUnit tu = getCursorTU(C);
3947  if (clang_isDeclaration(C.kind)) {
3948    Decl *D = getCursorDecl(C);
3949    if (!D)
3950      return clang_getNullCursor();
3951    if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
3952      return MakeCursorOverloadedDeclRef(Using, D->getLocation(), tu);
3953    if (ObjCPropertyImplDecl *PropImpl =dyn_cast<ObjCPropertyImplDecl>(D))
3954      if (ObjCPropertyDecl *Property = PropImpl->getPropertyDecl())
3955        return MakeCXCursor(Property, tu);
3956
3957    return C;
3958  }
3959
3960  if (clang_isExpression(C.kind)) {
3961    Expr *E = getCursorExpr(C);
3962    Decl *D = getDeclFromExpr(E);
3963    if (D) {
3964      CXCursor declCursor = MakeCXCursor(D, tu);
3965      declCursor = getSelectorIdentifierCursor(getSelectorIdentifierIndex(C),
3966                                               declCursor);
3967      return declCursor;
3968    }
3969
3970    if (OverloadExpr *Ovl = dyn_cast_or_null<OverloadExpr>(E))
3971      return MakeCursorOverloadedDeclRef(Ovl, tu);
3972
3973    return clang_getNullCursor();
3974  }
3975
3976  if (clang_isStatement(C.kind)) {
3977    Stmt *S = getCursorStmt(C);
3978    if (GotoStmt *Goto = dyn_cast_or_null<GotoStmt>(S))
3979      if (LabelDecl *label = Goto->getLabel())
3980        if (LabelStmt *labelS = label->getStmt())
3981        return MakeCXCursor(labelS, getCursorDecl(C), tu);
3982
3983    return clang_getNullCursor();
3984  }
3985
3986  if (C.kind == CXCursor_MacroExpansion) {
3987    if (MacroDefinition *Def = getCursorMacroExpansion(C)->getDefinition())
3988      return MakeMacroDefinitionCursor(Def, tu);
3989  }
3990
3991  if (!clang_isReference(C.kind))
3992    return clang_getNullCursor();
3993
3994  switch (C.kind) {
3995    case CXCursor_ObjCSuperClassRef:
3996      return MakeCXCursor(getCursorObjCSuperClassRef(C).first, tu);
3997
3998    case CXCursor_ObjCProtocolRef: {
3999      ObjCProtocolDecl *Prot = getCursorObjCProtocolRef(C).first;
4000      if (ObjCProtocolDecl *Def = Prot->getDefinition())
4001        return MakeCXCursor(Def, tu);
4002
4003      return MakeCXCursor(Prot, tu);
4004    }
4005
4006    case CXCursor_ObjCClassRef: {
4007      ObjCInterfaceDecl *Class = getCursorObjCClassRef(C).first;
4008      if (ObjCInterfaceDecl *Def = Class->getDefinition())
4009        return MakeCXCursor(Def, tu);
4010
4011      return MakeCXCursor(Class, tu);
4012    }
4013
4014    case CXCursor_TypeRef:
4015      return MakeCXCursor(getCursorTypeRef(C).first, tu );
4016
4017    case CXCursor_TemplateRef:
4018      return MakeCXCursor(getCursorTemplateRef(C).first, tu );
4019
4020    case CXCursor_NamespaceRef:
4021      return MakeCXCursor(getCursorNamespaceRef(C).first, tu );
4022
4023    case CXCursor_MemberRef:
4024      return MakeCXCursor(getCursorMemberRef(C).first, tu );
4025
4026    case CXCursor_CXXBaseSpecifier: {
4027      CXXBaseSpecifier *B = cxcursor::getCursorCXXBaseSpecifier(C);
4028      return clang_getTypeDeclaration(cxtype::MakeCXType(B->getType(),
4029                                                         tu ));
4030    }
4031
4032    case CXCursor_LabelRef:
4033      // FIXME: We end up faking the "parent" declaration here because we
4034      // don't want to make CXCursor larger.
4035      return MakeCXCursor(getCursorLabelRef(C).first,
4036               static_cast<ASTUnit*>(tu->TUData)->getASTContext()
4037                          .getTranslationUnitDecl(),
4038                          tu);
4039
4040    case CXCursor_OverloadedDeclRef:
4041      return C;
4042
4043    case CXCursor_VariableRef:
4044      return MakeCXCursor(getCursorVariableRef(C).first, tu);
4045
4046    default:
4047      // We would prefer to enumerate all non-reference cursor kinds here.
4048      llvm_unreachable("Unhandled reference cursor kind");
4049  }
4050}
4051
4052CXCursor clang_getCursorDefinition(CXCursor C) {
4053  if (clang_isInvalid(C.kind))
4054    return clang_getNullCursor();
4055
4056  CXTranslationUnit TU = getCursorTU(C);
4057
4058  bool WasReference = false;
4059  if (clang_isReference(C.kind) || clang_isExpression(C.kind)) {
4060    C = clang_getCursorReferenced(C);
4061    WasReference = true;
4062  }
4063
4064  if (C.kind == CXCursor_MacroExpansion)
4065    return clang_getCursorReferenced(C);
4066
4067  if (!clang_isDeclaration(C.kind))
4068    return clang_getNullCursor();
4069
4070  Decl *D = getCursorDecl(C);
4071  if (!D)
4072    return clang_getNullCursor();
4073
4074  switch (D->getKind()) {
4075  // Declaration kinds that don't really separate the notions of
4076  // declaration and definition.
4077  case Decl::Namespace:
4078  case Decl::Typedef:
4079  case Decl::TypeAlias:
4080  case Decl::TypeAliasTemplate:
4081  case Decl::TemplateTypeParm:
4082  case Decl::EnumConstant:
4083  case Decl::Field:
4084  case Decl::IndirectField:
4085  case Decl::ObjCIvar:
4086  case Decl::ObjCAtDefsField:
4087  case Decl::ImplicitParam:
4088  case Decl::ParmVar:
4089  case Decl::NonTypeTemplateParm:
4090  case Decl::TemplateTemplateParm:
4091  case Decl::ObjCCategoryImpl:
4092  case Decl::ObjCImplementation:
4093  case Decl::AccessSpec:
4094  case Decl::LinkageSpec:
4095  case Decl::ObjCPropertyImpl:
4096  case Decl::FileScopeAsm:
4097  case Decl::StaticAssert:
4098  case Decl::Block:
4099  case Decl::Label:  // FIXME: Is this right??
4100  case Decl::ClassScopeFunctionSpecialization:
4101  case Decl::Import:
4102    return C;
4103
4104  // Declaration kinds that don't make any sense here, but are
4105  // nonetheless harmless.
4106  case Decl::TranslationUnit:
4107    break;
4108
4109  // Declaration kinds for which the definition is not resolvable.
4110  case Decl::UnresolvedUsingTypename:
4111  case Decl::UnresolvedUsingValue:
4112    break;
4113
4114  case Decl::UsingDirective:
4115    return MakeCXCursor(cast<UsingDirectiveDecl>(D)->getNominatedNamespace(),
4116                        TU);
4117
4118  case Decl::NamespaceAlias:
4119    return MakeCXCursor(cast<NamespaceAliasDecl>(D)->getNamespace(), TU);
4120
4121  case Decl::Enum:
4122  case Decl::Record:
4123  case Decl::CXXRecord:
4124  case Decl::ClassTemplateSpecialization:
4125  case Decl::ClassTemplatePartialSpecialization:
4126    if (TagDecl *Def = cast<TagDecl>(D)->getDefinition())
4127      return MakeCXCursor(Def, TU);
4128    return clang_getNullCursor();
4129
4130  case Decl::Function:
4131  case Decl::CXXMethod:
4132  case Decl::CXXConstructor:
4133  case Decl::CXXDestructor:
4134  case Decl::CXXConversion: {
4135    const FunctionDecl *Def = 0;
4136    if (cast<FunctionDecl>(D)->getBody(Def))
4137      return MakeCXCursor(const_cast<FunctionDecl *>(Def), TU);
4138    return clang_getNullCursor();
4139  }
4140
4141  case Decl::Var: {
4142    // Ask the variable if it has a definition.
4143    if (VarDecl *Def = cast<VarDecl>(D)->getDefinition())
4144      return MakeCXCursor(Def, TU);
4145    return clang_getNullCursor();
4146  }
4147
4148  case Decl::FunctionTemplate: {
4149    const FunctionDecl *Def = 0;
4150    if (cast<FunctionTemplateDecl>(D)->getTemplatedDecl()->getBody(Def))
4151      return MakeCXCursor(Def->getDescribedFunctionTemplate(), TU);
4152    return clang_getNullCursor();
4153  }
4154
4155  case Decl::ClassTemplate: {
4156    if (RecordDecl *Def = cast<ClassTemplateDecl>(D)->getTemplatedDecl()
4157                                                            ->getDefinition())
4158      return MakeCXCursor(cast<CXXRecordDecl>(Def)->getDescribedClassTemplate(),
4159                          TU);
4160    return clang_getNullCursor();
4161  }
4162
4163  case Decl::Using:
4164    return MakeCursorOverloadedDeclRef(cast<UsingDecl>(D),
4165                                       D->getLocation(), TU);
4166
4167  case Decl::UsingShadow:
4168    return clang_getCursorDefinition(
4169                       MakeCXCursor(cast<UsingShadowDecl>(D)->getTargetDecl(),
4170                                    TU));
4171
4172  case Decl::ObjCMethod: {
4173    ObjCMethodDecl *Method = cast<ObjCMethodDecl>(D);
4174    if (Method->isThisDeclarationADefinition())
4175      return C;
4176
4177    // Dig out the method definition in the associated
4178    // @implementation, if we have it.
4179    // FIXME: The ASTs should make finding the definition easier.
4180    if (ObjCInterfaceDecl *Class
4181                       = dyn_cast<ObjCInterfaceDecl>(Method->getDeclContext()))
4182      if (ObjCImplementationDecl *ClassImpl = Class->getImplementation())
4183        if (ObjCMethodDecl *Def = ClassImpl->getMethod(Method->getSelector(),
4184                                                  Method->isInstanceMethod()))
4185          if (Def->isThisDeclarationADefinition())
4186            return MakeCXCursor(Def, TU);
4187
4188    return clang_getNullCursor();
4189  }
4190
4191  case Decl::ObjCCategory:
4192    if (ObjCCategoryImplDecl *Impl
4193                               = cast<ObjCCategoryDecl>(D)->getImplementation())
4194      return MakeCXCursor(Impl, TU);
4195    return clang_getNullCursor();
4196
4197  case Decl::ObjCProtocol:
4198    if (ObjCProtocolDecl *Def = cast<ObjCProtocolDecl>(D)->getDefinition())
4199      return MakeCXCursor(Def, TU);
4200    return clang_getNullCursor();
4201
4202  case Decl::ObjCInterface: {
4203    // There are two notions of a "definition" for an Objective-C
4204    // class: the interface and its implementation. When we resolved a
4205    // reference to an Objective-C class, produce the @interface as
4206    // the definition; when we were provided with the interface,
4207    // produce the @implementation as the definition.
4208    ObjCInterfaceDecl *IFace = cast<ObjCInterfaceDecl>(D);
4209    if (WasReference) {
4210      if (ObjCInterfaceDecl *Def = IFace->getDefinition())
4211        return MakeCXCursor(Def, TU);
4212    } else if (ObjCImplementationDecl *Impl = IFace->getImplementation())
4213      return MakeCXCursor(Impl, TU);
4214    return clang_getNullCursor();
4215  }
4216
4217  case Decl::ObjCProperty:
4218    // FIXME: We don't really know where to find the
4219    // ObjCPropertyImplDecls that implement this property.
4220    return clang_getNullCursor();
4221
4222  case Decl::ObjCCompatibleAlias:
4223    if (ObjCInterfaceDecl *Class
4224          = cast<ObjCCompatibleAliasDecl>(D)->getClassInterface())
4225      if (ObjCInterfaceDecl *Def = Class->getDefinition())
4226        return MakeCXCursor(Def, TU);
4227
4228    return clang_getNullCursor();
4229
4230  case Decl::Friend:
4231    if (NamedDecl *Friend = cast<FriendDecl>(D)->getFriendDecl())
4232      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4233    return clang_getNullCursor();
4234
4235  case Decl::FriendTemplate:
4236    if (NamedDecl *Friend = cast<FriendTemplateDecl>(D)->getFriendDecl())
4237      return clang_getCursorDefinition(MakeCXCursor(Friend, TU));
4238    return clang_getNullCursor();
4239  }
4240
4241  return clang_getNullCursor();
4242}
4243
4244unsigned clang_isCursorDefinition(CXCursor C) {
4245  if (!clang_isDeclaration(C.kind))
4246    return 0;
4247
4248  return clang_getCursorDefinition(C) == C;
4249}
4250
4251CXCursor clang_getCanonicalCursor(CXCursor C) {
4252  if (!clang_isDeclaration(C.kind))
4253    return C;
4254
4255  if (Decl *D = getCursorDecl(C)) {
4256    if (ObjCCategoryImplDecl *CatImplD = dyn_cast<ObjCCategoryImplDecl>(D))
4257      if (ObjCCategoryDecl *CatD = CatImplD->getCategoryDecl())
4258        return MakeCXCursor(CatD, getCursorTU(C));
4259
4260    if (ObjCImplDecl *ImplD = dyn_cast<ObjCImplDecl>(D))
4261      if (ObjCInterfaceDecl *IFD = ImplD->getClassInterface())
4262        return MakeCXCursor(IFD, getCursorTU(C));
4263
4264    return MakeCXCursor(D->getCanonicalDecl(), getCursorTU(C));
4265  }
4266
4267  return C;
4268}
4269
4270unsigned clang_getNumOverloadedDecls(CXCursor C) {
4271  if (C.kind != CXCursor_OverloadedDeclRef)
4272    return 0;
4273
4274  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(C).first;
4275  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4276    return E->getNumDecls();
4277
4278  if (OverloadedTemplateStorage *S
4279                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4280    return S->size();
4281
4282  Decl *D = Storage.get<Decl*>();
4283  if (UsingDecl *Using = dyn_cast<UsingDecl>(D))
4284    return Using->shadow_size();
4285
4286  return 0;
4287}
4288
4289CXCursor clang_getOverloadedDecl(CXCursor cursor, unsigned index) {
4290  if (cursor.kind != CXCursor_OverloadedDeclRef)
4291    return clang_getNullCursor();
4292
4293  if (index >= clang_getNumOverloadedDecls(cursor))
4294    return clang_getNullCursor();
4295
4296  CXTranslationUnit TU = getCursorTU(cursor);
4297  OverloadedDeclRefStorage Storage = getCursorOverloadedDeclRef(cursor).first;
4298  if (OverloadExpr *E = Storage.dyn_cast<OverloadExpr *>())
4299    return MakeCXCursor(E->decls_begin()[index], TU);
4300
4301  if (OverloadedTemplateStorage *S
4302                              = Storage.dyn_cast<OverloadedTemplateStorage*>())
4303    return MakeCXCursor(S->begin()[index], TU);
4304
4305  Decl *D = Storage.get<Decl*>();
4306  if (UsingDecl *Using = dyn_cast<UsingDecl>(D)) {
4307    // FIXME: This is, unfortunately, linear time.
4308    UsingDecl::shadow_iterator Pos = Using->shadow_begin();
4309    std::advance(Pos, index);
4310    return MakeCXCursor(cast<UsingShadowDecl>(*Pos)->getTargetDecl(), TU);
4311  }
4312
4313  return clang_getNullCursor();
4314}
4315
4316void clang_getDefinitionSpellingAndExtent(CXCursor C,
4317                                          const char **startBuf,
4318                                          const char **endBuf,
4319                                          unsigned *startLine,
4320                                          unsigned *startColumn,
4321                                          unsigned *endLine,
4322                                          unsigned *endColumn) {
4323  assert(getCursorDecl(C) && "CXCursor has null decl");
4324  NamedDecl *ND = static_cast<NamedDecl *>(getCursorDecl(C));
4325  FunctionDecl *FD = dyn_cast<FunctionDecl>(ND);
4326  CompoundStmt *Body = dyn_cast<CompoundStmt>(FD->getBody());
4327
4328  SourceManager &SM = FD->getASTContext().getSourceManager();
4329  *startBuf = SM.getCharacterData(Body->getLBracLoc());
4330  *endBuf = SM.getCharacterData(Body->getRBracLoc());
4331  *startLine = SM.getSpellingLineNumber(Body->getLBracLoc());
4332  *startColumn = SM.getSpellingColumnNumber(Body->getLBracLoc());
4333  *endLine = SM.getSpellingLineNumber(Body->getRBracLoc());
4334  *endColumn = SM.getSpellingColumnNumber(Body->getRBracLoc());
4335}
4336
4337
4338CXSourceRange clang_getCursorReferenceNameRange(CXCursor C, unsigned NameFlags,
4339                                                unsigned PieceIndex) {
4340  RefNamePieces Pieces;
4341
4342  switch (C.kind) {
4343  case CXCursor_MemberRefExpr:
4344    if (MemberExpr *E = dyn_cast<MemberExpr>(getCursorExpr(C)))
4345      Pieces = buildPieces(NameFlags, true, E->getMemberNameInfo(),
4346                           E->getQualifierLoc().getSourceRange());
4347    break;
4348
4349  case CXCursor_DeclRefExpr:
4350    if (DeclRefExpr *E = dyn_cast<DeclRefExpr>(getCursorExpr(C)))
4351      Pieces = buildPieces(NameFlags, false, E->getNameInfo(),
4352                           E->getQualifierLoc().getSourceRange(),
4353                           E->getOptionalExplicitTemplateArgs());
4354    break;
4355
4356  case CXCursor_CallExpr:
4357    if (CXXOperatorCallExpr *OCE =
4358        dyn_cast<CXXOperatorCallExpr>(getCursorExpr(C))) {
4359      Expr *Callee = OCE->getCallee();
4360      if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Callee))
4361        Callee = ICE->getSubExpr();
4362
4363      if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Callee))
4364        Pieces = buildPieces(NameFlags, false, DRE->getNameInfo(),
4365                             DRE->getQualifierLoc().getSourceRange());
4366    }
4367    break;
4368
4369  default:
4370    break;
4371  }
4372
4373  if (Pieces.empty()) {
4374    if (PieceIndex == 0)
4375      return clang_getCursorExtent(C);
4376  } else if (PieceIndex < Pieces.size()) {
4377      SourceRange R = Pieces[PieceIndex];
4378      if (R.isValid())
4379        return cxloc::translateSourceRange(getCursorContext(C), R);
4380  }
4381
4382  return clang_getNullRange();
4383}
4384
4385void clang_enableStackTraces(void) {
4386  llvm::sys::PrintStackTraceOnErrorSignal();
4387}
4388
4389void clang_executeOnThread(void (*fn)(void*), void *user_data,
4390                           unsigned stack_size) {
4391  llvm::llvm_execute_on_thread(fn, user_data, stack_size);
4392}
4393
4394} // end: extern "C"
4395
4396//===----------------------------------------------------------------------===//
4397// Token-based Operations.
4398//===----------------------------------------------------------------------===//
4399
4400/* CXToken layout:
4401 *   int_data[0]: a CXTokenKind
4402 *   int_data[1]: starting token location
4403 *   int_data[2]: token length
4404 *   int_data[3]: reserved
4405 *   ptr_data: for identifiers and keywords, an IdentifierInfo*.
4406 *   otherwise unused.
4407 */
4408extern "C" {
4409
4410CXTokenKind clang_getTokenKind(CXToken CXTok) {
4411  return static_cast<CXTokenKind>(CXTok.int_data[0]);
4412}
4413
4414CXString clang_getTokenSpelling(CXTranslationUnit TU, CXToken CXTok) {
4415  switch (clang_getTokenKind(CXTok)) {
4416  case CXToken_Identifier:
4417  case CXToken_Keyword:
4418    // We know we have an IdentifierInfo*, so use that.
4419    return createCXString(static_cast<IdentifierInfo *>(CXTok.ptr_data)
4420                            ->getNameStart());
4421
4422  case CXToken_Literal: {
4423    // We have stashed the starting pointer in the ptr_data field. Use it.
4424    const char *Text = static_cast<const char *>(CXTok.ptr_data);
4425    return createCXString(StringRef(Text, CXTok.int_data[2]));
4426  }
4427
4428  case CXToken_Punctuation:
4429  case CXToken_Comment:
4430    break;
4431  }
4432
4433  // We have to find the starting buffer pointer the hard way, by
4434  // deconstructing the source location.
4435  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4436  if (!CXXUnit)
4437    return createCXString("");
4438
4439  SourceLocation Loc = SourceLocation::getFromRawEncoding(CXTok.int_data[1]);
4440  std::pair<FileID, unsigned> LocInfo
4441    = CXXUnit->getSourceManager().getDecomposedSpellingLoc(Loc);
4442  bool Invalid = false;
4443  StringRef Buffer
4444    = CXXUnit->getSourceManager().getBufferData(LocInfo.first, &Invalid);
4445  if (Invalid)
4446    return createCXString("");
4447
4448  return createCXString(Buffer.substr(LocInfo.second, CXTok.int_data[2]));
4449}
4450
4451CXSourceLocation clang_getTokenLocation(CXTranslationUnit TU, CXToken CXTok) {
4452  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4453  if (!CXXUnit)
4454    return clang_getNullLocation();
4455
4456  return cxloc::translateSourceLocation(CXXUnit->getASTContext(),
4457                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4458}
4459
4460CXSourceRange clang_getTokenExtent(CXTranslationUnit TU, CXToken CXTok) {
4461  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4462  if (!CXXUnit)
4463    return clang_getNullRange();
4464
4465  return cxloc::translateSourceRange(CXXUnit->getASTContext(),
4466                        SourceLocation::getFromRawEncoding(CXTok.int_data[1]));
4467}
4468
4469static void getTokens(ASTUnit *CXXUnit, SourceRange Range,
4470                      SmallVectorImpl<CXToken> &CXTokens) {
4471  SourceManager &SourceMgr = CXXUnit->getSourceManager();
4472  std::pair<FileID, unsigned> BeginLocInfo
4473    = SourceMgr.getDecomposedLoc(Range.getBegin());
4474  std::pair<FileID, unsigned> EndLocInfo
4475    = SourceMgr.getDecomposedLoc(Range.getEnd());
4476
4477  // Cannot tokenize across files.
4478  if (BeginLocInfo.first != EndLocInfo.first)
4479    return;
4480
4481  // Create a lexer
4482  bool Invalid = false;
4483  StringRef Buffer
4484    = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
4485  if (Invalid)
4486    return;
4487
4488  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
4489            CXXUnit->getASTContext().getLangOptions(),
4490            Buffer.begin(), Buffer.data() + BeginLocInfo.second, Buffer.end());
4491  Lex.SetCommentRetentionState(true);
4492
4493  // Lex tokens until we hit the end of the range.
4494  const char *EffectiveBufferEnd = Buffer.data() + EndLocInfo.second;
4495  Token Tok;
4496  bool previousWasAt = false;
4497  do {
4498    // Lex the next token
4499    Lex.LexFromRawLexer(Tok);
4500    if (Tok.is(tok::eof))
4501      break;
4502
4503    // Initialize the CXToken.
4504    CXToken CXTok;
4505
4506    //   - Common fields
4507    CXTok.int_data[1] = Tok.getLocation().getRawEncoding();
4508    CXTok.int_data[2] = Tok.getLength();
4509    CXTok.int_data[3] = 0;
4510
4511    //   - Kind-specific fields
4512    if (Tok.isLiteral()) {
4513      CXTok.int_data[0] = CXToken_Literal;
4514      CXTok.ptr_data = (void *)Tok.getLiteralData();
4515    } else if (Tok.is(tok::raw_identifier)) {
4516      // Lookup the identifier to determine whether we have a keyword.
4517      IdentifierInfo *II
4518        = CXXUnit->getPreprocessor().LookUpIdentifierInfo(Tok);
4519
4520      if ((II->getObjCKeywordID() != tok::objc_not_keyword) && previousWasAt) {
4521        CXTok.int_data[0] = CXToken_Keyword;
4522      }
4523      else {
4524        CXTok.int_data[0] = Tok.is(tok::identifier)
4525          ? CXToken_Identifier
4526          : CXToken_Keyword;
4527      }
4528      CXTok.ptr_data = II;
4529    } else if (Tok.is(tok::comment)) {
4530      CXTok.int_data[0] = CXToken_Comment;
4531      CXTok.ptr_data = 0;
4532    } else {
4533      CXTok.int_data[0] = CXToken_Punctuation;
4534      CXTok.ptr_data = 0;
4535    }
4536    CXTokens.push_back(CXTok);
4537    previousWasAt = Tok.is(tok::at);
4538  } while (Lex.getBufferLocation() <= EffectiveBufferEnd);
4539}
4540
4541void clang_tokenize(CXTranslationUnit TU, CXSourceRange Range,
4542                    CXToken **Tokens, unsigned *NumTokens) {
4543  if (Tokens)
4544    *Tokens = 0;
4545  if (NumTokens)
4546    *NumTokens = 0;
4547
4548  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
4549  if (!CXXUnit || !Tokens || !NumTokens)
4550    return;
4551
4552  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
4553
4554  SourceRange R = cxloc::translateCXSourceRange(Range);
4555  if (R.isInvalid())
4556    return;
4557
4558  SmallVector<CXToken, 32> CXTokens;
4559  getTokens(CXXUnit, R, CXTokens);
4560
4561  if (CXTokens.empty())
4562    return;
4563
4564  *Tokens = (CXToken *)malloc(sizeof(CXToken) * CXTokens.size());
4565  memmove(*Tokens, CXTokens.data(), sizeof(CXToken) * CXTokens.size());
4566  *NumTokens = CXTokens.size();
4567}
4568
4569void clang_disposeTokens(CXTranslationUnit TU,
4570                         CXToken *Tokens, unsigned NumTokens) {
4571  free(Tokens);
4572}
4573
4574} // end: extern "C"
4575
4576//===----------------------------------------------------------------------===//
4577// Token annotation APIs.
4578//===----------------------------------------------------------------------===//
4579
4580typedef llvm::DenseMap<unsigned, CXCursor> AnnotateTokensData;
4581static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4582                                                     CXCursor parent,
4583                                                     CXClientData client_data);
4584namespace {
4585class AnnotateTokensWorker {
4586  AnnotateTokensData &Annotated;
4587  CXToken *Tokens;
4588  CXCursor *Cursors;
4589  unsigned NumTokens;
4590  unsigned TokIdx;
4591  unsigned PreprocessingTokIdx;
4592  CursorVisitor AnnotateVis;
4593  SourceManager &SrcMgr;
4594  bool HasContextSensitiveKeywords;
4595
4596  bool MoreTokens() const { return TokIdx < NumTokens; }
4597  unsigned NextToken() const { return TokIdx; }
4598  void AdvanceToken() { ++TokIdx; }
4599  SourceLocation GetTokenLoc(unsigned tokI) {
4600    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4601  }
4602  bool isFunctionMacroToken(unsigned tokI) const {
4603    return Tokens[tokI].int_data[3] != 0;
4604  }
4605  SourceLocation getFunctionMacroTokenLoc(unsigned tokI) const {
4606    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[3]);
4607  }
4608
4609  void annotateAndAdvanceTokens(CXCursor, RangeComparisonResult, SourceRange);
4610  void annotateAndAdvanceFunctionMacroTokens(CXCursor, RangeComparisonResult,
4611                                             SourceRange);
4612
4613public:
4614  AnnotateTokensWorker(AnnotateTokensData &annotated,
4615                       CXToken *tokens, CXCursor *cursors, unsigned numTokens,
4616                       CXTranslationUnit tu, SourceRange RegionOfInterest)
4617    : Annotated(annotated), Tokens(tokens), Cursors(cursors),
4618      NumTokens(numTokens), TokIdx(0), PreprocessingTokIdx(0),
4619      AnnotateVis(tu,
4620                  AnnotateTokensVisitor, this,
4621                  /*VisitPreprocessorLast=*/true,
4622                  /*VisitIncludedEntities=*/false,
4623                  RegionOfInterest),
4624      SrcMgr(static_cast<ASTUnit*>(tu->TUData)->getSourceManager()),
4625      HasContextSensitiveKeywords(false) { }
4626
4627  void VisitChildren(CXCursor C) { AnnotateVis.VisitChildren(C); }
4628  enum CXChildVisitResult Visit(CXCursor cursor, CXCursor parent);
4629  void AnnotateTokens();
4630
4631  /// \brief Determine whether the annotator saw any cursors that have
4632  /// context-sensitive keywords.
4633  bool hasContextSensitiveKeywords() const {
4634    return HasContextSensitiveKeywords;
4635  }
4636};
4637}
4638
4639void AnnotateTokensWorker::AnnotateTokens() {
4640  // Walk the AST within the region of interest, annotating tokens
4641  // along the way.
4642  AnnotateVis.visitFileRegion();
4643
4644  for (unsigned I = 0 ; I < TokIdx ; ++I) {
4645    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4646    if (Pos != Annotated.end() &&
4647        (clang_isInvalid(Cursors[I].kind) ||
4648         Pos->second.kind != CXCursor_PreprocessingDirective))
4649      Cursors[I] = Pos->second;
4650  }
4651
4652  // Finish up annotating any tokens left.
4653  if (!MoreTokens())
4654    return;
4655
4656  const CXCursor &C = clang_getNullCursor();
4657  for (unsigned I = TokIdx ; I < NumTokens ; ++I) {
4658    if (I < PreprocessingTokIdx && clang_isPreprocessing(Cursors[I].kind))
4659      continue;
4660
4661    AnnotateTokensData::iterator Pos = Annotated.find(Tokens[I].int_data[1]);
4662    Cursors[I] = (Pos == Annotated.end()) ? C : Pos->second;
4663  }
4664}
4665
4666/// \brief It annotates and advances tokens with a cursor until the comparison
4667//// between the cursor location and the source range is the same as
4668/// \arg compResult.
4669///
4670/// Pass RangeBefore to annotate tokens with a cursor until a range is reached.
4671/// Pass RangeOverlap to annotate tokens inside a range.
4672void AnnotateTokensWorker::annotateAndAdvanceTokens(CXCursor updateC,
4673                                               RangeComparisonResult compResult,
4674                                               SourceRange range) {
4675  while (MoreTokens()) {
4676    const unsigned I = NextToken();
4677    if (isFunctionMacroToken(I))
4678      return annotateAndAdvanceFunctionMacroTokens(updateC, compResult, range);
4679
4680    SourceLocation TokLoc = GetTokenLoc(I);
4681    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4682      Cursors[I] = updateC;
4683      AdvanceToken();
4684      continue;
4685    }
4686    break;
4687  }
4688}
4689
4690/// \brief Special annotation handling for macro argument tokens.
4691void AnnotateTokensWorker::annotateAndAdvanceFunctionMacroTokens(
4692                                               CXCursor updateC,
4693                                               RangeComparisonResult compResult,
4694                                               SourceRange range) {
4695  assert(MoreTokens());
4696  assert(isFunctionMacroToken(NextToken()) &&
4697         "Should be called only for macro arg tokens");
4698
4699  // This works differently than annotateAndAdvanceTokens; because expanded
4700  // macro arguments can have arbitrary translation-unit source order, we do not
4701  // advance the token index one by one until a token fails the range test.
4702  // We only advance once past all of the macro arg tokens if all of them
4703  // pass the range test. If one of them fails we keep the token index pointing
4704  // at the start of the macro arg tokens so that the failing token will be
4705  // annotated by a subsequent annotation try.
4706
4707  bool atLeastOneCompFail = false;
4708
4709  unsigned I = NextToken();
4710  for (; I < NumTokens && isFunctionMacroToken(I); ++I) {
4711    SourceLocation TokLoc = getFunctionMacroTokenLoc(I);
4712    if (TokLoc.isFileID())
4713      continue; // not macro arg token, it's parens or comma.
4714    if (LocationCompare(SrcMgr, TokLoc, range) == compResult) {
4715      if (clang_isInvalid(clang_getCursorKind(Cursors[I])))
4716        Cursors[I] = updateC;
4717    } else
4718      atLeastOneCompFail = true;
4719  }
4720
4721  if (!atLeastOneCompFail)
4722    TokIdx = I; // All of the tokens were handled, advance beyond all of them.
4723}
4724
4725enum CXChildVisitResult
4726AnnotateTokensWorker::Visit(CXCursor cursor, CXCursor parent) {
4727  CXSourceLocation Loc = clang_getCursorLocation(cursor);
4728  SourceRange cursorRange = getRawCursorExtent(cursor);
4729  if (cursorRange.isInvalid())
4730    return CXChildVisit_Recurse;
4731
4732  if (!HasContextSensitiveKeywords) {
4733    // Objective-C properties can have context-sensitive keywords.
4734    if (cursor.kind == CXCursor_ObjCPropertyDecl) {
4735      if (ObjCPropertyDecl *Property
4736                  = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(cursor)))
4737        HasContextSensitiveKeywords = Property->getPropertyAttributesAsWritten() != 0;
4738    }
4739    // Objective-C methods can have context-sensitive keywords.
4740    else if (cursor.kind == CXCursor_ObjCInstanceMethodDecl ||
4741             cursor.kind == CXCursor_ObjCClassMethodDecl) {
4742      if (ObjCMethodDecl *Method
4743            = dyn_cast_or_null<ObjCMethodDecl>(getCursorDecl(cursor))) {
4744        if (Method->getObjCDeclQualifier())
4745          HasContextSensitiveKeywords = true;
4746        else {
4747          for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
4748                                           PEnd = Method->param_end();
4749               P != PEnd; ++P) {
4750            if ((*P)->getObjCDeclQualifier()) {
4751              HasContextSensitiveKeywords = true;
4752              break;
4753            }
4754          }
4755        }
4756      }
4757    }
4758    // C++ methods can have context-sensitive keywords.
4759    else if (cursor.kind == CXCursor_CXXMethod) {
4760      if (CXXMethodDecl *Method
4761                  = dyn_cast_or_null<CXXMethodDecl>(getCursorDecl(cursor))) {
4762        if (Method->hasAttr<FinalAttr>() || Method->hasAttr<OverrideAttr>())
4763          HasContextSensitiveKeywords = true;
4764      }
4765    }
4766    // C++ classes can have context-sensitive keywords.
4767    else if (cursor.kind == CXCursor_StructDecl ||
4768             cursor.kind == CXCursor_ClassDecl ||
4769             cursor.kind == CXCursor_ClassTemplate ||
4770             cursor.kind == CXCursor_ClassTemplatePartialSpecialization) {
4771      if (Decl *D = getCursorDecl(cursor))
4772        if (D->hasAttr<FinalAttr>())
4773          HasContextSensitiveKeywords = true;
4774    }
4775  }
4776
4777  if (clang_isPreprocessing(cursor.kind)) {
4778    // For macro expansions, just note where the beginning of the macro
4779    // expansion occurs.
4780    if (cursor.kind == CXCursor_MacroExpansion) {
4781      Annotated[Loc.int_data] = cursor;
4782      return CXChildVisit_Recurse;
4783    }
4784
4785    // Items in the preprocessing record are kept separate from items in
4786    // declarations, so we keep a separate token index.
4787    unsigned SavedTokIdx = TokIdx;
4788    TokIdx = PreprocessingTokIdx;
4789
4790    // Skip tokens up until we catch up to the beginning of the preprocessing
4791    // entry.
4792    while (MoreTokens()) {
4793      const unsigned I = NextToken();
4794      SourceLocation TokLoc = GetTokenLoc(I);
4795      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4796      case RangeBefore:
4797        AdvanceToken();
4798        continue;
4799      case RangeAfter:
4800      case RangeOverlap:
4801        break;
4802      }
4803      break;
4804    }
4805
4806    // Look at all of the tokens within this range.
4807    while (MoreTokens()) {
4808      const unsigned I = NextToken();
4809      SourceLocation TokLoc = GetTokenLoc(I);
4810      switch (LocationCompare(SrcMgr, TokLoc, cursorRange)) {
4811      case RangeBefore:
4812        llvm_unreachable("Infeasible");
4813      case RangeAfter:
4814        break;
4815      case RangeOverlap:
4816        Cursors[I] = cursor;
4817        AdvanceToken();
4818        continue;
4819      }
4820      break;
4821    }
4822
4823    // Save the preprocessing token index; restore the non-preprocessing
4824    // token index.
4825    PreprocessingTokIdx = TokIdx;
4826    TokIdx = SavedTokIdx;
4827    return CXChildVisit_Recurse;
4828  }
4829
4830  if (cursorRange.isInvalid())
4831    return CXChildVisit_Continue;
4832
4833  SourceLocation L = SourceLocation::getFromRawEncoding(Loc.int_data);
4834
4835  // Adjust the annotated range based specific declarations.
4836  const enum CXCursorKind cursorK = clang_getCursorKind(cursor);
4837  if (cursorK >= CXCursor_FirstDecl && cursorK <= CXCursor_LastDecl) {
4838    Decl *D = cxcursor::getCursorDecl(cursor);
4839
4840    SourceLocation StartLoc;
4841    if (const DeclaratorDecl *DD = dyn_cast_or_null<DeclaratorDecl>(D)) {
4842      if (TypeSourceInfo *TI = DD->getTypeSourceInfo())
4843        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4844    } else if (TypedefDecl *Typedef = dyn_cast_or_null<TypedefDecl>(D)) {
4845      if (TypeSourceInfo *TI = Typedef->getTypeSourceInfo())
4846        StartLoc = TI->getTypeLoc().getSourceRange().getBegin();
4847    }
4848
4849    if (StartLoc.isValid() && L.isValid() &&
4850        SrcMgr.isBeforeInTranslationUnit(StartLoc, L))
4851      cursorRange.setBegin(StartLoc);
4852  }
4853
4854  // If the location of the cursor occurs within a macro instantiation, record
4855  // the spelling location of the cursor in our annotation map.  We can then
4856  // paper over the token labelings during a post-processing step to try and
4857  // get cursor mappings for tokens that are the *arguments* of a macro
4858  // instantiation.
4859  if (L.isMacroID()) {
4860    unsigned rawEncoding = SrcMgr.getSpellingLoc(L).getRawEncoding();
4861    // Only invalidate the old annotation if it isn't part of a preprocessing
4862    // directive.  Here we assume that the default construction of CXCursor
4863    // results in CXCursor.kind being an initialized value (i.e., 0).  If
4864    // this isn't the case, we can fix by doing lookup + insertion.
4865
4866    CXCursor &oldC = Annotated[rawEncoding];
4867    if (!clang_isPreprocessing(oldC.kind))
4868      oldC = cursor;
4869  }
4870
4871  const enum CXCursorKind K = clang_getCursorKind(parent);
4872  const CXCursor updateC =
4873    (clang_isInvalid(K) || K == CXCursor_TranslationUnit)
4874     ? clang_getNullCursor() : parent;
4875
4876  annotateAndAdvanceTokens(updateC, RangeBefore, cursorRange);
4877
4878  // Avoid having the cursor of an expression "overwrite" the annotation of the
4879  // variable declaration that it belongs to.
4880  // This can happen for C++ constructor expressions whose range generally
4881  // include the variable declaration, e.g.:
4882  //  MyCXXClass foo; // Make sure we don't annotate 'foo' as a CallExpr cursor.
4883  if (clang_isExpression(cursorK)) {
4884    Expr *E = getCursorExpr(cursor);
4885    if (Decl *D = getCursorParentDecl(cursor)) {
4886      const unsigned I = NextToken();
4887      if (E->getLocStart().isValid() && D->getLocation().isValid() &&
4888          E->getLocStart() == D->getLocation() &&
4889          E->getLocStart() == GetTokenLoc(I)) {
4890        Cursors[I] = updateC;
4891        AdvanceToken();
4892      }
4893    }
4894  }
4895
4896  // Visit children to get their cursor information.
4897  const unsigned BeforeChildren = NextToken();
4898  VisitChildren(cursor);
4899  const unsigned AfterChildren = NextToken();
4900
4901  // Scan the tokens that are at the end of the cursor, but are not captured
4902  // but the child cursors.
4903  annotateAndAdvanceTokens(cursor, RangeOverlap, cursorRange);
4904
4905  // Scan the tokens that are at the beginning of the cursor, but are not
4906  // capture by the child cursors.
4907  for (unsigned I = BeforeChildren; I != AfterChildren; ++I) {
4908    if (!clang_isInvalid(clang_getCursorKind(Cursors[I])))
4909      break;
4910
4911    Cursors[I] = cursor;
4912  }
4913
4914  return CXChildVisit_Continue;
4915}
4916
4917static enum CXChildVisitResult AnnotateTokensVisitor(CXCursor cursor,
4918                                                     CXCursor parent,
4919                                                     CXClientData client_data) {
4920  return static_cast<AnnotateTokensWorker*>(client_data)->Visit(cursor, parent);
4921}
4922
4923namespace {
4924
4925/// \brief Uses the macro expansions in the preprocessing record to find
4926/// and mark tokens that are macro arguments. This info is used by the
4927/// AnnotateTokensWorker.
4928class MarkMacroArgTokensVisitor {
4929  SourceManager &SM;
4930  CXToken *Tokens;
4931  unsigned NumTokens;
4932  unsigned CurIdx;
4933
4934public:
4935  MarkMacroArgTokensVisitor(SourceManager &SM,
4936                            CXToken *tokens, unsigned numTokens)
4937    : SM(SM), Tokens(tokens), NumTokens(numTokens), CurIdx(0) { }
4938
4939  CXChildVisitResult visit(CXCursor cursor, CXCursor parent) {
4940    if (cursor.kind != CXCursor_MacroExpansion)
4941      return CXChildVisit_Continue;
4942
4943    SourceRange macroRange = getCursorMacroExpansion(cursor)->getSourceRange();
4944    if (macroRange.getBegin() == macroRange.getEnd())
4945      return CXChildVisit_Continue; // it's not a function macro.
4946
4947    for (; CurIdx < NumTokens; ++CurIdx) {
4948      if (!SM.isBeforeInTranslationUnit(getTokenLoc(CurIdx),
4949                                        macroRange.getBegin()))
4950        break;
4951    }
4952
4953    if (CurIdx == NumTokens)
4954      return CXChildVisit_Break;
4955
4956    for (; CurIdx < NumTokens; ++CurIdx) {
4957      SourceLocation tokLoc = getTokenLoc(CurIdx);
4958      if (!SM.isBeforeInTranslationUnit(tokLoc, macroRange.getEnd()))
4959        break;
4960
4961      setFunctionMacroTokenLoc(CurIdx, SM.getMacroArgExpandedLocation(tokLoc));
4962    }
4963
4964    if (CurIdx == NumTokens)
4965      return CXChildVisit_Break;
4966
4967    return CXChildVisit_Continue;
4968  }
4969
4970private:
4971  SourceLocation getTokenLoc(unsigned tokI) {
4972    return SourceLocation::getFromRawEncoding(Tokens[tokI].int_data[1]);
4973  }
4974
4975  void setFunctionMacroTokenLoc(unsigned tokI, SourceLocation loc) {
4976    // The third field is reserved and currently not used. Use it here
4977    // to mark macro arg expanded tokens with their expanded locations.
4978    Tokens[tokI].int_data[3] = loc.getRawEncoding();
4979  }
4980};
4981
4982} // end anonymous namespace
4983
4984static CXChildVisitResult
4985MarkMacroArgTokensVisitorDelegate(CXCursor cursor, CXCursor parent,
4986                                  CXClientData client_data) {
4987  return static_cast<MarkMacroArgTokensVisitor*>(client_data)->visit(cursor,
4988                                                                     parent);
4989}
4990
4991namespace {
4992  struct clang_annotateTokens_Data {
4993    CXTranslationUnit TU;
4994    ASTUnit *CXXUnit;
4995    CXToken *Tokens;
4996    unsigned NumTokens;
4997    CXCursor *Cursors;
4998  };
4999}
5000
5001static void annotatePreprocessorTokens(CXTranslationUnit TU,
5002                                       SourceRange RegionOfInterest,
5003                                       AnnotateTokensData &Annotated) {
5004  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
5005
5006  SourceManager &SourceMgr = CXXUnit->getSourceManager();
5007  std::pair<FileID, unsigned> BeginLocInfo
5008    = SourceMgr.getDecomposedLoc(RegionOfInterest.getBegin());
5009  std::pair<FileID, unsigned> EndLocInfo
5010    = SourceMgr.getDecomposedLoc(RegionOfInterest.getEnd());
5011
5012  if (BeginLocInfo.first != EndLocInfo.first)
5013    return;
5014
5015  StringRef Buffer;
5016  bool Invalid = false;
5017  Buffer = SourceMgr.getBufferData(BeginLocInfo.first, &Invalid);
5018  if (Buffer.empty() || Invalid)
5019    return;
5020
5021  Lexer Lex(SourceMgr.getLocForStartOfFile(BeginLocInfo.first),
5022            CXXUnit->getASTContext().getLangOptions(),
5023            Buffer.begin(), Buffer.data() + BeginLocInfo.second,
5024            Buffer.end());
5025  Lex.SetCommentRetentionState(true);
5026
5027  // Lex tokens in raw mode until we hit the end of the range, to avoid
5028  // entering #includes or expanding macros.
5029  while (true) {
5030    Token Tok;
5031    Lex.LexFromRawLexer(Tok);
5032
5033  reprocess:
5034    if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
5035      // We have found a preprocessing directive. Gobble it up so that we
5036      // don't see it while preprocessing these tokens later, but keep track
5037      // of all of the token locations inside this preprocessing directive so
5038      // that we can annotate them appropriately.
5039      //
5040      // FIXME: Some simple tests here could identify macro definitions and
5041      // #undefs, to provide specific cursor kinds for those.
5042      SmallVector<SourceLocation, 32> Locations;
5043      do {
5044        Locations.push_back(Tok.getLocation());
5045        Lex.LexFromRawLexer(Tok);
5046      } while (!Tok.isAtStartOfLine() && !Tok.is(tok::eof));
5047
5048      using namespace cxcursor;
5049      CXCursor Cursor
5050      = MakePreprocessingDirectiveCursor(SourceRange(Locations.front(),
5051                                                     Locations.back()),
5052                                         TU);
5053      for (unsigned I = 0, N = Locations.size(); I != N; ++I) {
5054        Annotated[Locations[I].getRawEncoding()] = Cursor;
5055      }
5056
5057      if (Tok.isAtStartOfLine())
5058        goto reprocess;
5059
5060      continue;
5061    }
5062
5063    if (Tok.is(tok::eof))
5064      break;
5065  }
5066}
5067
5068// This gets run a separate thread to avoid stack blowout.
5069static void clang_annotateTokensImpl(void *UserData) {
5070  CXTranslationUnit TU = ((clang_annotateTokens_Data*)UserData)->TU;
5071  ASTUnit *CXXUnit = ((clang_annotateTokens_Data*)UserData)->CXXUnit;
5072  CXToken *Tokens = ((clang_annotateTokens_Data*)UserData)->Tokens;
5073  const unsigned NumTokens = ((clang_annotateTokens_Data*)UserData)->NumTokens;
5074  CXCursor *Cursors = ((clang_annotateTokens_Data*)UserData)->Cursors;
5075
5076  // Determine the region of interest, which contains all of the tokens.
5077  SourceRange RegionOfInterest;
5078  RegionOfInterest.setBegin(
5079    cxloc::translateSourceLocation(clang_getTokenLocation(TU, Tokens[0])));
5080  RegionOfInterest.setEnd(
5081    cxloc::translateSourceLocation(clang_getTokenLocation(TU,
5082                                                         Tokens[NumTokens-1])));
5083
5084  // A mapping from the source locations found when re-lexing or traversing the
5085  // region of interest to the corresponding cursors.
5086  AnnotateTokensData Annotated;
5087
5088  // Relex the tokens within the source range to look for preprocessing
5089  // directives.
5090  annotatePreprocessorTokens(TU, RegionOfInterest, Annotated);
5091
5092  if (CXXUnit->getPreprocessor().getPreprocessingRecord()) {
5093    // Search and mark tokens that are macro argument expansions.
5094    MarkMacroArgTokensVisitor Visitor(CXXUnit->getSourceManager(),
5095                                      Tokens, NumTokens);
5096    CursorVisitor MacroArgMarker(TU,
5097                                 MarkMacroArgTokensVisitorDelegate, &Visitor,
5098                                 /*VisitPreprocessorLast=*/true,
5099                                 /*VisitIncludedEntities=*/false,
5100                                 RegionOfInterest);
5101    MacroArgMarker.visitPreprocessedEntitiesInRegion();
5102  }
5103
5104  // Annotate all of the source locations in the region of interest that map to
5105  // a specific cursor.
5106  AnnotateTokensWorker W(Annotated, Tokens, Cursors, NumTokens,
5107                         TU, RegionOfInterest);
5108
5109  // FIXME: We use a ridiculous stack size here because the data-recursion
5110  // algorithm uses a large stack frame than the non-data recursive version,
5111  // and AnnotationTokensWorker currently transforms the data-recursion
5112  // algorithm back into a traditional recursion by explicitly calling
5113  // VisitChildren().  We will need to remove this explicit recursive call.
5114  W.AnnotateTokens();
5115
5116  // If we ran into any entities that involve context-sensitive keywords,
5117  // take another pass through the tokens to mark them as such.
5118  if (W.hasContextSensitiveKeywords()) {
5119    for (unsigned I = 0; I != NumTokens; ++I) {
5120      if (clang_getTokenKind(Tokens[I]) != CXToken_Identifier)
5121        continue;
5122
5123      if (Cursors[I].kind == CXCursor_ObjCPropertyDecl) {
5124        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5125        if (ObjCPropertyDecl *Property
5126            = dyn_cast_or_null<ObjCPropertyDecl>(getCursorDecl(Cursors[I]))) {
5127          if (Property->getPropertyAttributesAsWritten() != 0 &&
5128              llvm::StringSwitch<bool>(II->getName())
5129              .Case("readonly", true)
5130              .Case("assign", true)
5131              .Case("unsafe_unretained", true)
5132              .Case("readwrite", true)
5133              .Case("retain", true)
5134              .Case("copy", true)
5135              .Case("nonatomic", true)
5136              .Case("atomic", true)
5137              .Case("getter", true)
5138              .Case("setter", true)
5139              .Case("strong", true)
5140              .Case("weak", true)
5141              .Default(false))
5142            Tokens[I].int_data[0] = CXToken_Keyword;
5143        }
5144        continue;
5145      }
5146
5147      if (Cursors[I].kind == CXCursor_ObjCInstanceMethodDecl ||
5148          Cursors[I].kind == CXCursor_ObjCClassMethodDecl) {
5149        IdentifierInfo *II = static_cast<IdentifierInfo *>(Tokens[I].ptr_data);
5150        if (llvm::StringSwitch<bool>(II->getName())
5151            .Case("in", true)
5152            .Case("out", true)
5153            .Case("inout", true)
5154            .Case("oneway", true)
5155            .Case("bycopy", true)
5156            .Case("byref", true)
5157            .Default(false))
5158          Tokens[I].int_data[0] = CXToken_Keyword;
5159        continue;
5160      }
5161
5162      if (Cursors[I].kind == CXCursor_CXXFinalAttr ||
5163          Cursors[I].kind == CXCursor_CXXOverrideAttr) {
5164        Tokens[I].int_data[0] = CXToken_Keyword;
5165        continue;
5166      }
5167    }
5168  }
5169}
5170
5171extern "C" {
5172
5173void clang_annotateTokens(CXTranslationUnit TU,
5174                          CXToken *Tokens, unsigned NumTokens,
5175                          CXCursor *Cursors) {
5176
5177  if (NumTokens == 0 || !Tokens || !Cursors)
5178    return;
5179
5180  // Any token we don't specifically annotate will have a NULL cursor.
5181  CXCursor C = clang_getNullCursor();
5182  for (unsigned I = 0; I != NumTokens; ++I)
5183    Cursors[I] = C;
5184
5185  ASTUnit *CXXUnit = static_cast<ASTUnit *>(TU->TUData);
5186  if (!CXXUnit)
5187    return;
5188
5189  ASTUnit::ConcurrencyCheck Check(*CXXUnit);
5190
5191  clang_annotateTokens_Data data = { TU, CXXUnit, Tokens, NumTokens, Cursors };
5192  llvm::CrashRecoveryContext CRC;
5193  if (!RunSafely(CRC, clang_annotateTokensImpl, &data,
5194                 GetSafetyThreadStackSize() * 2)) {
5195    fprintf(stderr, "libclang: crash detected while annotating tokens\n");
5196  }
5197}
5198
5199} // end: extern "C"
5200
5201//===----------------------------------------------------------------------===//
5202// Operations for querying linkage of a cursor.
5203//===----------------------------------------------------------------------===//
5204
5205extern "C" {
5206CXLinkageKind clang_getCursorLinkage(CXCursor cursor) {
5207  if (!clang_isDeclaration(cursor.kind))
5208    return CXLinkage_Invalid;
5209
5210  Decl *D = cxcursor::getCursorDecl(cursor);
5211  if (NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
5212    switch (ND->getLinkage()) {
5213      case NoLinkage: return CXLinkage_NoLinkage;
5214      case InternalLinkage: return CXLinkage_Internal;
5215      case UniqueExternalLinkage: return CXLinkage_UniqueExternal;
5216      case ExternalLinkage: return CXLinkage_External;
5217    };
5218
5219  return CXLinkage_Invalid;
5220}
5221} // end: extern "C"
5222
5223//===----------------------------------------------------------------------===//
5224// Operations for querying language of a cursor.
5225//===----------------------------------------------------------------------===//
5226
5227static CXLanguageKind getDeclLanguage(const Decl *D) {
5228  if (!D)
5229    return CXLanguage_C;
5230
5231  switch (D->getKind()) {
5232    default:
5233      break;
5234    case Decl::ImplicitParam:
5235    case Decl::ObjCAtDefsField:
5236    case Decl::ObjCCategory:
5237    case Decl::ObjCCategoryImpl:
5238    case Decl::ObjCCompatibleAlias:
5239    case Decl::ObjCImplementation:
5240    case Decl::ObjCInterface:
5241    case Decl::ObjCIvar:
5242    case Decl::ObjCMethod:
5243    case Decl::ObjCProperty:
5244    case Decl::ObjCPropertyImpl:
5245    case Decl::ObjCProtocol:
5246      return CXLanguage_ObjC;
5247    case Decl::CXXConstructor:
5248    case Decl::CXXConversion:
5249    case Decl::CXXDestructor:
5250    case Decl::CXXMethod:
5251    case Decl::CXXRecord:
5252    case Decl::ClassTemplate:
5253    case Decl::ClassTemplatePartialSpecialization:
5254    case Decl::ClassTemplateSpecialization:
5255    case Decl::Friend:
5256    case Decl::FriendTemplate:
5257    case Decl::FunctionTemplate:
5258    case Decl::LinkageSpec:
5259    case Decl::Namespace:
5260    case Decl::NamespaceAlias:
5261    case Decl::NonTypeTemplateParm:
5262    case Decl::StaticAssert:
5263    case Decl::TemplateTemplateParm:
5264    case Decl::TemplateTypeParm:
5265    case Decl::UnresolvedUsingTypename:
5266    case Decl::UnresolvedUsingValue:
5267    case Decl::Using:
5268    case Decl::UsingDirective:
5269    case Decl::UsingShadow:
5270      return CXLanguage_CPlusPlus;
5271  }
5272
5273  return CXLanguage_C;
5274}
5275
5276extern "C" {
5277
5278enum CXAvailabilityKind clang_getCursorAvailability(CXCursor cursor) {
5279  if (clang_isDeclaration(cursor.kind))
5280    if (Decl *D = cxcursor::getCursorDecl(cursor)) {
5281      if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->isDeleted())
5282        return CXAvailability_Available;
5283
5284      switch (D->getAvailability()) {
5285      case AR_Available:
5286      case AR_NotYetIntroduced:
5287        return CXAvailability_Available;
5288
5289      case AR_Deprecated:
5290        return CXAvailability_Deprecated;
5291
5292      case AR_Unavailable:
5293        return CXAvailability_NotAvailable;
5294      }
5295    }
5296
5297  return CXAvailability_Available;
5298}
5299
5300CXLanguageKind clang_getCursorLanguage(CXCursor cursor) {
5301  if (clang_isDeclaration(cursor.kind))
5302    return getDeclLanguage(cxcursor::getCursorDecl(cursor));
5303
5304  return CXLanguage_Invalid;
5305}
5306
5307 /// \brief If the given cursor is the "templated" declaration
5308 /// descibing a class or function template, return the class or
5309 /// function template.
5310static Decl *maybeGetTemplateCursor(Decl *D) {
5311  if (!D)
5312    return 0;
5313
5314  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
5315    if (FunctionTemplateDecl *FunTmpl = FD->getDescribedFunctionTemplate())
5316      return FunTmpl;
5317
5318  if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D))
5319    if (ClassTemplateDecl *ClassTmpl = RD->getDescribedClassTemplate())
5320      return ClassTmpl;
5321
5322  return D;
5323}
5324
5325CXCursor clang_getCursorSemanticParent(CXCursor cursor) {
5326  if (clang_isDeclaration(cursor.kind)) {
5327    if (Decl *D = getCursorDecl(cursor)) {
5328      DeclContext *DC = D->getDeclContext();
5329      if (!DC)
5330        return clang_getNullCursor();
5331
5332      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5333                          getCursorTU(cursor));
5334    }
5335  }
5336
5337  if (clang_isStatement(cursor.kind) || clang_isExpression(cursor.kind)) {
5338    if (Decl *D = getCursorDecl(cursor))
5339      return MakeCXCursor(D, getCursorTU(cursor));
5340  }
5341
5342  return clang_getNullCursor();
5343}
5344
5345CXCursor clang_getCursorLexicalParent(CXCursor cursor) {
5346  if (clang_isDeclaration(cursor.kind)) {
5347    if (Decl *D = getCursorDecl(cursor)) {
5348      DeclContext *DC = D->getLexicalDeclContext();
5349      if (!DC)
5350        return clang_getNullCursor();
5351
5352      return MakeCXCursor(maybeGetTemplateCursor(cast<Decl>(DC)),
5353                          getCursorTU(cursor));
5354    }
5355  }
5356
5357  // FIXME: Note that we can't easily compute the lexical context of a
5358  // statement or expression, so we return nothing.
5359  return clang_getNullCursor();
5360}
5361
5362void clang_getOverriddenCursors(CXCursor cursor,
5363                                CXCursor **overridden,
5364                                unsigned *num_overridden) {
5365  if (overridden)
5366    *overridden = 0;
5367  if (num_overridden)
5368    *num_overridden = 0;
5369  if (!overridden || !num_overridden)
5370    return;
5371
5372  SmallVector<CXCursor, 8> Overridden;
5373  cxcursor::getOverriddenCursors(cursor, Overridden);
5374
5375  // Don't allocate memory if we have no overriden cursors.
5376  if (Overridden.size() == 0)
5377    return;
5378
5379  *num_overridden = Overridden.size();
5380  *overridden = new CXCursor [Overridden.size()];
5381  std::copy(Overridden.begin(), Overridden.end(), *overridden);
5382}
5383
5384void clang_disposeOverriddenCursors(CXCursor *overridden) {
5385  delete [] overridden;
5386}
5387
5388CXFile clang_getIncludedFile(CXCursor cursor) {
5389  if (cursor.kind != CXCursor_InclusionDirective)
5390    return 0;
5391
5392  InclusionDirective *ID = getCursorInclusionDirective(cursor);
5393  return (void *)ID->getFile();
5394}
5395
5396} // end: extern "C"
5397
5398
5399//===----------------------------------------------------------------------===//
5400// C++ AST instrospection.
5401//===----------------------------------------------------------------------===//
5402
5403extern "C" {
5404unsigned clang_CXXMethod_isStatic(CXCursor C) {
5405  if (!clang_isDeclaration(C.kind))
5406    return 0;
5407
5408  CXXMethodDecl *Method = 0;
5409  Decl *D = cxcursor::getCursorDecl(C);
5410  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5411    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5412  else
5413    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5414  return (Method && Method->isStatic()) ? 1 : 0;
5415}
5416
5417unsigned clang_CXXMethod_isVirtual(CXCursor C) {
5418  if (!clang_isDeclaration(C.kind))
5419    return 0;
5420
5421  CXXMethodDecl *Method = 0;
5422  Decl *D = cxcursor::getCursorDecl(C);
5423  if (FunctionTemplateDecl *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
5424    Method = dyn_cast<CXXMethodDecl>(FunTmpl->getTemplatedDecl());
5425  else
5426    Method = dyn_cast_or_null<CXXMethodDecl>(D);
5427  return (Method && Method->isVirtual()) ? 1 : 0;
5428}
5429} // end: extern "C"
5430
5431//===----------------------------------------------------------------------===//
5432// Attribute introspection.
5433//===----------------------------------------------------------------------===//
5434
5435extern "C" {
5436CXType clang_getIBOutletCollectionType(CXCursor C) {
5437  if (C.kind != CXCursor_IBOutletCollectionAttr)
5438    return cxtype::MakeCXType(QualType(), cxcursor::getCursorTU(C));
5439
5440  IBOutletCollectionAttr *A =
5441    cast<IBOutletCollectionAttr>(cxcursor::getCursorAttr(C));
5442
5443  return cxtype::MakeCXType(A->getInterface(), cxcursor::getCursorTU(C));
5444}
5445} // end: extern "C"
5446
5447//===----------------------------------------------------------------------===//
5448// Inspecting memory usage.
5449//===----------------------------------------------------------------------===//
5450
5451typedef std::vector<CXTUResourceUsageEntry> MemUsageEntries;
5452
5453static inline void createCXTUResourceUsageEntry(MemUsageEntries &entries,
5454                                              enum CXTUResourceUsageKind k,
5455                                              unsigned long amount) {
5456  CXTUResourceUsageEntry entry = { k, amount };
5457  entries.push_back(entry);
5458}
5459
5460extern "C" {
5461
5462const char *clang_getTUResourceUsageName(CXTUResourceUsageKind kind) {
5463  const char *str = "";
5464  switch (kind) {
5465    case CXTUResourceUsage_AST:
5466      str = "ASTContext: expressions, declarations, and types";
5467      break;
5468    case CXTUResourceUsage_Identifiers:
5469      str = "ASTContext: identifiers";
5470      break;
5471    case CXTUResourceUsage_Selectors:
5472      str = "ASTContext: selectors";
5473      break;
5474    case CXTUResourceUsage_GlobalCompletionResults:
5475      str = "Code completion: cached global results";
5476      break;
5477    case CXTUResourceUsage_SourceManagerContentCache:
5478      str = "SourceManager: content cache allocator";
5479      break;
5480    case CXTUResourceUsage_AST_SideTables:
5481      str = "ASTContext: side tables";
5482      break;
5483    case CXTUResourceUsage_SourceManager_Membuffer_Malloc:
5484      str = "SourceManager: malloc'ed memory buffers";
5485      break;
5486    case CXTUResourceUsage_SourceManager_Membuffer_MMap:
5487      str = "SourceManager: mmap'ed memory buffers";
5488      break;
5489    case CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc:
5490      str = "ExternalASTSource: malloc'ed memory buffers";
5491      break;
5492    case CXTUResourceUsage_ExternalASTSource_Membuffer_MMap:
5493      str = "ExternalASTSource: mmap'ed memory buffers";
5494      break;
5495    case CXTUResourceUsage_Preprocessor:
5496      str = "Preprocessor: malloc'ed memory";
5497      break;
5498    case CXTUResourceUsage_PreprocessingRecord:
5499      str = "Preprocessor: PreprocessingRecord";
5500      break;
5501    case CXTUResourceUsage_SourceManager_DataStructures:
5502      str = "SourceManager: data structures and tables";
5503      break;
5504    case CXTUResourceUsage_Preprocessor_HeaderSearch:
5505      str = "Preprocessor: header search tables";
5506      break;
5507  }
5508  return str;
5509}
5510
5511CXTUResourceUsage clang_getCXTUResourceUsage(CXTranslationUnit TU) {
5512  if (!TU) {
5513    CXTUResourceUsage usage = { (void*) 0, 0, 0 };
5514    return usage;
5515  }
5516
5517  ASTUnit *astUnit = static_cast<ASTUnit*>(TU->TUData);
5518  OwningPtr<MemUsageEntries> entries(new MemUsageEntries());
5519  ASTContext &astContext = astUnit->getASTContext();
5520
5521  // How much memory is used by AST nodes and types?
5522  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST,
5523    (unsigned long) astContext.getASTAllocatedMemory());
5524
5525  // How much memory is used by identifiers?
5526  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Identifiers,
5527    (unsigned long) astContext.Idents.getAllocator().getTotalMemory());
5528
5529  // How much memory is used for selectors?
5530  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_Selectors,
5531    (unsigned long) astContext.Selectors.getTotalMemory());
5532
5533  // How much memory is used by ASTContext's side tables?
5534  createCXTUResourceUsageEntry(*entries, CXTUResourceUsage_AST_SideTables,
5535    (unsigned long) astContext.getSideTableAllocatedMemory());
5536
5537  // How much memory is used for caching global code completion results?
5538  unsigned long completionBytes = 0;
5539  if (GlobalCodeCompletionAllocator *completionAllocator =
5540      astUnit->getCachedCompletionAllocator().getPtr()) {
5541    completionBytes = completionAllocator->getTotalMemory();
5542  }
5543  createCXTUResourceUsageEntry(*entries,
5544                               CXTUResourceUsage_GlobalCompletionResults,
5545                               completionBytes);
5546
5547  // How much memory is being used by SourceManager's content cache?
5548  createCXTUResourceUsageEntry(*entries,
5549          CXTUResourceUsage_SourceManagerContentCache,
5550          (unsigned long) astContext.getSourceManager().getContentCacheSize());
5551
5552  // How much memory is being used by the MemoryBuffer's in SourceManager?
5553  const SourceManager::MemoryBufferSizes &srcBufs =
5554    astUnit->getSourceManager().getMemoryBufferSizes();
5555
5556  createCXTUResourceUsageEntry(*entries,
5557                               CXTUResourceUsage_SourceManager_Membuffer_Malloc,
5558                               (unsigned long) srcBufs.malloc_bytes);
5559  createCXTUResourceUsageEntry(*entries,
5560                               CXTUResourceUsage_SourceManager_Membuffer_MMap,
5561                               (unsigned long) srcBufs.mmap_bytes);
5562  createCXTUResourceUsageEntry(*entries,
5563                               CXTUResourceUsage_SourceManager_DataStructures,
5564                               (unsigned long) astContext.getSourceManager()
5565                                .getDataStructureSizes());
5566
5567  // How much memory is being used by the ExternalASTSource?
5568  if (ExternalASTSource *esrc = astContext.getExternalSource()) {
5569    const ExternalASTSource::MemoryBufferSizes &sizes =
5570      esrc->getMemoryBufferSizes();
5571
5572    createCXTUResourceUsageEntry(*entries,
5573      CXTUResourceUsage_ExternalASTSource_Membuffer_Malloc,
5574                                 (unsigned long) sizes.malloc_bytes);
5575    createCXTUResourceUsageEntry(*entries,
5576      CXTUResourceUsage_ExternalASTSource_Membuffer_MMap,
5577                                 (unsigned long) sizes.mmap_bytes);
5578  }
5579
5580  // How much memory is being used by the Preprocessor?
5581  Preprocessor &pp = astUnit->getPreprocessor();
5582  createCXTUResourceUsageEntry(*entries,
5583                               CXTUResourceUsage_Preprocessor,
5584                               pp.getTotalMemory());
5585
5586  if (PreprocessingRecord *pRec = pp.getPreprocessingRecord()) {
5587    createCXTUResourceUsageEntry(*entries,
5588                                 CXTUResourceUsage_PreprocessingRecord,
5589                                 pRec->getTotalMemory());
5590  }
5591
5592  createCXTUResourceUsageEntry(*entries,
5593                               CXTUResourceUsage_Preprocessor_HeaderSearch,
5594                               pp.getHeaderSearchInfo().getTotalMemory());
5595
5596  CXTUResourceUsage usage = { (void*) entries.get(),
5597                            (unsigned) entries->size(),
5598                            entries->size() ? &(*entries)[0] : 0 };
5599  entries.take();
5600  return usage;
5601}
5602
5603void clang_disposeCXTUResourceUsage(CXTUResourceUsage usage) {
5604  if (usage.data)
5605    delete (MemUsageEntries*) usage.data;
5606}
5607
5608} // end extern "C"
5609
5610void clang::PrintLibclangResourceUsage(CXTranslationUnit TU) {
5611  CXTUResourceUsage Usage = clang_getCXTUResourceUsage(TU);
5612  for (unsigned I = 0; I != Usage.numEntries; ++I)
5613    fprintf(stderr, "  %s: %lu\n",
5614            clang_getTUResourceUsageName(Usage.entries[I].kind),
5615            Usage.entries[I].amount);
5616
5617  clang_disposeCXTUResourceUsage(Usage);
5618}
5619
5620//===----------------------------------------------------------------------===//
5621// Misc. utility functions.
5622//===----------------------------------------------------------------------===//
5623
5624/// Default to using an 8 MB stack size on "safety" threads.
5625static unsigned SafetyStackThreadSize = 8 << 20;
5626
5627namespace clang {
5628
5629bool RunSafely(llvm::CrashRecoveryContext &CRC,
5630               void (*Fn)(void*), void *UserData,
5631               unsigned Size) {
5632  if (!Size)
5633    Size = GetSafetyThreadStackSize();
5634  if (Size)
5635    return CRC.RunSafelyOnThread(Fn, UserData, Size);
5636  return CRC.RunSafely(Fn, UserData);
5637}
5638
5639unsigned GetSafetyThreadStackSize() {
5640  return SafetyStackThreadSize;
5641}
5642
5643void SetSafetyThreadStackSize(unsigned Value) {
5644  SafetyStackThreadSize = Value;
5645}
5646
5647}
5648
5649extern "C" {
5650
5651CXString clang_getClangVersion() {
5652  return createCXString(getClangFullVersion());
5653}
5654
5655} // end: extern "C"
5656
5657