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