SemaCodeComplete.cpp revision 9201d5cde8e918dc2f7272b8fcbcde96c245a567 
1//===---------------- SemaCodeComplete.cpp - Code Completion ----*- C++ -*-===//
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 defines the code-completion semantic actions.
11//
12//===----------------------------------------------------------------------===//
13#include "Sema.h"
14#include "clang/Sema/CodeCompleteConsumer.h"
15#include "clang/AST/ExprCXX.h"
16#include "clang/AST/ExprObjC.h"
17#include "clang/Lex/MacroInfo.h"
18#include "clang/Lex/Preprocessor.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/ADT/StringExtras.h"
21#include <list>
22#include <map>
23#include <vector>
24
25using namespace clang;
26
27namespace {
28  /// \brief A container of code-completion results.
29  class ResultBuilder {
30  public:
31    /// \brief The type of a name-lookup filter, which can be provided to the
32    /// name-lookup routines to specify which declarations should be included in
33    /// the result set (when it returns true) and which declarations should be
34    /// filtered out (returns false).
35    typedef bool (ResultBuilder::*LookupFilter)(NamedDecl *) const;
36
37    typedef CodeCompleteConsumer::Result Result;
38
39  private:
40    /// \brief The actual results we have found.
41    std::vector<Result> Results;
42
43    /// \brief A record of all of the declarations we have found and placed
44    /// into the result set, used to ensure that no declaration ever gets into
45    /// the result set twice.
46    llvm::SmallPtrSet<Decl*, 16> AllDeclsFound;
47
48    /// \brief A mapping from declaration names to the declarations that have
49    /// this name within a particular scope and their index within the list of
50    /// results.
51    typedef std::multimap<DeclarationName,
52                          std::pair<NamedDecl *, unsigned> > ShadowMap;
53
54    /// \brief The semantic analysis object for which results are being
55    /// produced.
56    Sema &SemaRef;
57
58    /// \brief If non-NULL, a filter function used to remove any code-completion
59    /// results that are not desirable.
60    LookupFilter Filter;
61
62    /// \brief A list of shadow maps, which is used to model name hiding at
63    /// different levels of, e.g., the inheritance hierarchy.
64    std::list<ShadowMap> ShadowMaps;
65
66  public:
67    explicit ResultBuilder(Sema &SemaRef, LookupFilter Filter = 0)
68      : SemaRef(SemaRef), Filter(Filter) { }
69
70    /// \brief Set the filter used for code-completion results.
71    void setFilter(LookupFilter Filter) {
72      this->Filter = Filter;
73    }
74
75    typedef std::vector<Result>::iterator iterator;
76    iterator begin() { return Results.begin(); }
77    iterator end() { return Results.end(); }
78
79    Result *data() { return Results.empty()? 0 : &Results.front(); }
80    unsigned size() const { return Results.size(); }
81    bool empty() const { return Results.empty(); }
82
83    /// \brief Add a new result to this result set (if it isn't already in one
84    /// of the shadow maps), or replace an existing result (for, e.g., a
85    /// redeclaration).
86    ///
87    /// \param R the result to add (if it is unique).
88    ///
89    /// \param R the context in which this result will be named.
90    void MaybeAddResult(Result R, DeclContext *CurContext = 0);
91
92    /// \brief Enter into a new scope.
93    void EnterNewScope();
94
95    /// \brief Exit from the current scope.
96    void ExitScope();
97
98    /// \name Name lookup predicates
99    ///
100    /// These predicates can be passed to the name lookup functions to filter the
101    /// results of name lookup. All of the predicates have the same type, so that
102    ///
103    //@{
104    bool IsOrdinaryName(NamedDecl *ND) const;
105    bool IsNestedNameSpecifier(NamedDecl *ND) const;
106    bool IsEnum(NamedDecl *ND) const;
107    bool IsClassOrStruct(NamedDecl *ND) const;
108    bool IsUnion(NamedDecl *ND) const;
109    bool IsNamespace(NamedDecl *ND) const;
110    bool IsNamespaceOrAlias(NamedDecl *ND) const;
111    bool IsType(NamedDecl *ND) const;
112    bool IsMember(NamedDecl *ND) const;
113    //@}
114  };
115}
116
117/// \brief Determines whether the given hidden result could be found with
118/// some extra work, e.g., by qualifying the name.
119///
120/// \param Hidden the declaration that is hidden by the currenly \p Visible
121/// declaration.
122///
123/// \param Visible the declaration with the same name that is already visible.
124///
125/// \returns true if the hidden result can be found by some mechanism,
126/// false otherwise.
127static bool canHiddenResultBeFound(const LangOptions &LangOpts,
128                                   NamedDecl *Hidden, NamedDecl *Visible) {
129  // In C, there is no way to refer to a hidden name.
130  if (!LangOpts.CPlusPlus)
131    return false;
132
133  DeclContext *HiddenCtx = Hidden->getDeclContext()->getLookupContext();
134
135  // There is no way to qualify a name declared in a function or method.
136  if (HiddenCtx->isFunctionOrMethod())
137    return false;
138
139  return HiddenCtx != Visible->getDeclContext()->getLookupContext();
140}
141
142/// \brief Compute the qualification required to get from the current context
143/// (\p CurContext) to the target context (\p TargetContext).
144///
145/// \param Context the AST context in which the qualification will be used.
146///
147/// \param CurContext the context where an entity is being named, which is
148/// typically based on the current scope.
149///
150/// \param TargetContext the context in which the named entity actually
151/// resides.
152///
153/// \returns a nested name specifier that refers into the target context, or
154/// NULL if no qualification is needed.
155static NestedNameSpecifier *
156getRequiredQualification(ASTContext &Context,
157                         DeclContext *CurContext,
158                         DeclContext *TargetContext) {
159  llvm::SmallVector<DeclContext *, 4> TargetParents;
160
161  for (DeclContext *CommonAncestor = TargetContext;
162       CommonAncestor && !CommonAncestor->Encloses(CurContext);
163       CommonAncestor = CommonAncestor->getLookupParent()) {
164    if (CommonAncestor->isTransparentContext() ||
165        CommonAncestor->isFunctionOrMethod())
166      continue;
167
168    TargetParents.push_back(CommonAncestor);
169  }
170
171  NestedNameSpecifier *Result = 0;
172  while (!TargetParents.empty()) {
173    DeclContext *Parent = TargetParents.back();
174    TargetParents.pop_back();
175
176    if (NamespaceDecl *Namespace = dyn_cast<NamespaceDecl>(Parent))
177      Result = NestedNameSpecifier::Create(Context, Result, Namespace);
178    else if (TagDecl *TD = dyn_cast<TagDecl>(Parent))
179      Result = NestedNameSpecifier::Create(Context, Result,
180                                           false,
181                                     Context.getTypeDeclType(TD).getTypePtr());
182    else
183      assert(Parent->isTranslationUnit());
184  }
185  return Result;
186}
187
188void ResultBuilder::MaybeAddResult(Result R, DeclContext *CurContext) {
189  assert(!ShadowMaps.empty() && "Must enter into a results scope");
190
191  if (R.Kind != Result::RK_Declaration) {
192    // For non-declaration results, just add the result.
193    Results.push_back(R);
194    return;
195  }
196
197  // Skip unnamed entities.
198  if (!R.Declaration->getDeclName())
199    return;
200
201  // Look through using declarations.
202  if (UsingShadowDecl *Using = dyn_cast<UsingShadowDecl>(R.Declaration))
203    MaybeAddResult(Result(Using->getTargetDecl(), R.Rank, R.Qualifier),
204                   CurContext);
205
206  // Handle each declaration in an overload set separately.
207  if (OverloadedFunctionDecl *Ovl
208        = dyn_cast<OverloadedFunctionDecl>(R.Declaration)) {
209    for (OverloadedFunctionDecl::function_iterator F = Ovl->function_begin(),
210         FEnd = Ovl->function_end();
211         F != FEnd; ++F)
212      MaybeAddResult(Result(*F, R.Rank, R.Qualifier), CurContext);
213
214    return;
215  }
216
217  Decl *CanonDecl = R.Declaration->getCanonicalDecl();
218  unsigned IDNS = CanonDecl->getIdentifierNamespace();
219
220  // Friend declarations and declarations introduced due to friends are never
221  // added as results.
222  if (isa<FriendDecl>(CanonDecl) ||
223      (IDNS & (Decl::IDNS_OrdinaryFriend | Decl::IDNS_TagFriend)))
224    return;
225
226  if (const IdentifierInfo *Id = R.Declaration->getIdentifier()) {
227    // __va_list_tag is a freak of nature. Find it and skip it.
228    if (Id->isStr("__va_list_tag") || Id->isStr("__builtin_va_list"))
229      return;
230
231    // Filter out names reserved for the implementation (C99 7.1.3,
232    // C++ [lib.global.names]). Users don't need to see those.
233    //
234    // FIXME: Add predicate for this.
235    if (Id->getLength() >= 2) {
236      const char *Name = Id->getNameStart();
237      if (Name[0] == '_' &&
238          (Name[1] == '_' || (Name[1] >= 'A' && Name[1] <= 'Z')))
239        return;
240    }
241  }
242
243  // C++ constructors are never found by name lookup.
244  if (isa<CXXConstructorDecl>(CanonDecl))
245    return;
246
247  // Filter out any unwanted results.
248  if (Filter && !(this->*Filter)(R.Declaration))
249    return;
250
251  ShadowMap &SMap = ShadowMaps.back();
252  ShadowMap::iterator I, IEnd;
253  for (llvm::tie(I, IEnd) = SMap.equal_range(R.Declaration->getDeclName());
254       I != IEnd; ++I) {
255    NamedDecl *ND = I->second.first;
256    unsigned Index = I->second.second;
257    if (ND->getCanonicalDecl() == CanonDecl) {
258      // This is a redeclaration. Always pick the newer declaration.
259      I->second.first = R.Declaration;
260      Results[Index].Declaration = R.Declaration;
261
262      // Pick the best rank of the two.
263      Results[Index].Rank = std::min(Results[Index].Rank, R.Rank);
264
265      // We're done.
266      return;
267    }
268  }
269
270  // This is a new declaration in this scope. However, check whether this
271  // declaration name is hidden by a similarly-named declaration in an outer
272  // scope.
273  std::list<ShadowMap>::iterator SM, SMEnd = ShadowMaps.end();
274  --SMEnd;
275  for (SM = ShadowMaps.begin(); SM != SMEnd; ++SM) {
276    for (llvm::tie(I, IEnd) = SM->equal_range(R.Declaration->getDeclName());
277         I != IEnd; ++I) {
278      // A tag declaration does not hide a non-tag declaration.
279      if (I->second.first->getIdentifierNamespace() == Decl::IDNS_Tag &&
280          (IDNS & (Decl::IDNS_Member | Decl::IDNS_Ordinary |
281                   Decl::IDNS_ObjCProtocol)))
282        continue;
283
284      // Protocols are in distinct namespaces from everything else.
285      if (((I->second.first->getIdentifierNamespace() & Decl::IDNS_ObjCProtocol)
286           || (IDNS & Decl::IDNS_ObjCProtocol)) &&
287          I->second.first->getIdentifierNamespace() != IDNS)
288        continue;
289
290      // The newly-added result is hidden by an entry in the shadow map.
291      if (canHiddenResultBeFound(SemaRef.getLangOptions(), R.Declaration,
292                                 I->second.first)) {
293        // Note that this result was hidden.
294        R.Hidden = true;
295        R.QualifierIsInformative = false;
296
297        if (!R.Qualifier)
298          R.Qualifier = getRequiredQualification(SemaRef.Context,
299                                                 CurContext,
300                                              R.Declaration->getDeclContext());
301      } else {
302        // This result was hidden and cannot be found; don't bother adding
303        // it.
304        return;
305      }
306
307      break;
308    }
309  }
310
311  // Make sure that any given declaration only shows up in the result set once.
312  if (!AllDeclsFound.insert(CanonDecl))
313    return;
314
315  // If the filter is for nested-name-specifiers, then this result starts a
316  // nested-name-specifier.
317  if ((Filter == &ResultBuilder::IsNestedNameSpecifier) ||
318      (Filter == &ResultBuilder::IsMember &&
319       isa<CXXRecordDecl>(R.Declaration) &&
320       cast<CXXRecordDecl>(R.Declaration)->isInjectedClassName()))
321    R.StartsNestedNameSpecifier = true;
322
323  // If this result is supposed to have an informative qualifier, add one.
324  if (R.QualifierIsInformative && !R.Qualifier &&
325      !R.StartsNestedNameSpecifier) {
326    DeclContext *Ctx = R.Declaration->getDeclContext();
327    if (NamespaceDecl *Namespace = dyn_cast<NamespaceDecl>(Ctx))
328      R.Qualifier = NestedNameSpecifier::Create(SemaRef.Context, 0, Namespace);
329    else if (TagDecl *Tag = dyn_cast<TagDecl>(Ctx))
330      R.Qualifier = NestedNameSpecifier::Create(SemaRef.Context, 0, false,
331                             SemaRef.Context.getTypeDeclType(Tag).getTypePtr());
332    else
333      R.QualifierIsInformative = false;
334  }
335
336  // Insert this result into the set of results and into the current shadow
337  // map.
338  SMap.insert(std::make_pair(R.Declaration->getDeclName(),
339                             std::make_pair(R.Declaration, Results.size())));
340  Results.push_back(R);
341}
342
343/// \brief Enter into a new scope.
344void ResultBuilder::EnterNewScope() {
345  ShadowMaps.push_back(ShadowMap());
346}
347
348/// \brief Exit from the current scope.
349void ResultBuilder::ExitScope() {
350  ShadowMaps.pop_back();
351}
352
353/// \brief Determines whether this given declaration will be found by
354/// ordinary name lookup.
355bool ResultBuilder::IsOrdinaryName(NamedDecl *ND) const {
356  unsigned IDNS = Decl::IDNS_Ordinary;
357  if (SemaRef.getLangOptions().CPlusPlus)
358    IDNS |= Decl::IDNS_Tag;
359
360  return ND->getIdentifierNamespace() & IDNS;
361}
362
363/// \brief Determines whether the given declaration is suitable as the
364/// start of a C++ nested-name-specifier, e.g., a class or namespace.
365bool ResultBuilder::IsNestedNameSpecifier(NamedDecl *ND) const {
366  // Allow us to find class templates, too.
367  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
368    ND = ClassTemplate->getTemplatedDecl();
369
370  return SemaRef.isAcceptableNestedNameSpecifier(ND);
371}
372
373/// \brief Determines whether the given declaration is an enumeration.
374bool ResultBuilder::IsEnum(NamedDecl *ND) const {
375  return isa<EnumDecl>(ND);
376}
377
378/// \brief Determines whether the given declaration is a class or struct.
379bool ResultBuilder::IsClassOrStruct(NamedDecl *ND) const {
380  // Allow us to find class templates, too.
381  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
382    ND = ClassTemplate->getTemplatedDecl();
383
384  if (RecordDecl *RD = dyn_cast<RecordDecl>(ND))
385    return RD->getTagKind() == TagDecl::TK_class ||
386    RD->getTagKind() == TagDecl::TK_struct;
387
388  return false;
389}
390
391/// \brief Determines whether the given declaration is a union.
392bool ResultBuilder::IsUnion(NamedDecl *ND) const {
393  // Allow us to find class templates, too.
394  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
395    ND = ClassTemplate->getTemplatedDecl();
396
397  if (RecordDecl *RD = dyn_cast<RecordDecl>(ND))
398    return RD->getTagKind() == TagDecl::TK_union;
399
400  return false;
401}
402
403/// \brief Determines whether the given declaration is a namespace.
404bool ResultBuilder::IsNamespace(NamedDecl *ND) const {
405  return isa<NamespaceDecl>(ND);
406}
407
408/// \brief Determines whether the given declaration is a namespace or
409/// namespace alias.
410bool ResultBuilder::IsNamespaceOrAlias(NamedDecl *ND) const {
411  return isa<NamespaceDecl>(ND) || isa<NamespaceAliasDecl>(ND);
412}
413
414/// \brief Brief determines whether the given declaration is a namespace or
415/// namespace alias.
416bool ResultBuilder::IsType(NamedDecl *ND) const {
417  return isa<TypeDecl>(ND);
418}
419
420/// \brief Since every declaration found within a class is a member that we
421/// care about, always returns true. This predicate exists mostly to
422/// communicate to the result builder that we are performing a lookup for
423/// member access.
424bool ResultBuilder::IsMember(NamedDecl *ND) const {
425  return true;
426}
427
428// Find the next outer declaration context corresponding to this scope.
429static DeclContext *findOuterContext(Scope *S) {
430  for (S = S->getParent(); S; S = S->getParent())
431    if (S->getEntity())
432      return static_cast<DeclContext *>(S->getEntity())->getPrimaryContext();
433
434  return 0;
435}
436
437/// \brief Collect the results of searching for members within the given
438/// declaration context.
439///
440/// \param Ctx the declaration context from which we will gather results.
441///
442/// \param Rank the rank given to results in this declaration context.
443///
444/// \param Visited the set of declaration contexts that have already been
445/// visited. Declaration contexts will only be visited once.
446///
447/// \param Results the result set that will be extended with any results
448/// found within this declaration context (and, for a C++ class, its bases).
449///
450/// \param InBaseClass whether we are in a base class.
451///
452/// \returns the next higher rank value, after considering all of the
453/// names within this declaration context.
454static unsigned CollectMemberLookupResults(DeclContext *Ctx,
455                                           unsigned Rank,
456                                           DeclContext *CurContext,
457                                 llvm::SmallPtrSet<DeclContext *, 16> &Visited,
458                                           ResultBuilder &Results,
459                                           bool InBaseClass = false) {
460  // Make sure we don't visit the same context twice.
461  if (!Visited.insert(Ctx->getPrimaryContext()))
462    return Rank;
463
464  // Enumerate all of the results in this context.
465  typedef CodeCompleteConsumer::Result Result;
466  Results.EnterNewScope();
467  for (DeclContext *CurCtx = Ctx->getPrimaryContext(); CurCtx;
468       CurCtx = CurCtx->getNextContext()) {
469    for (DeclContext::decl_iterator D = CurCtx->decls_begin(),
470                                 DEnd = CurCtx->decls_end();
471         D != DEnd; ++D) {
472      if (NamedDecl *ND = dyn_cast<NamedDecl>(*D))
473        Results.MaybeAddResult(Result(ND, Rank, 0, InBaseClass), CurContext);
474
475      // Visit transparent contexts inside this context.
476      if (DeclContext *InnerCtx = dyn_cast<DeclContext>(*D)) {
477        if (InnerCtx->isTransparentContext())
478          CollectMemberLookupResults(InnerCtx, Rank, CurContext, Visited,
479                                     Results, InBaseClass);
480      }
481    }
482  }
483
484  // Traverse the contexts of inherited classes.
485  if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(Ctx)) {
486    for (CXXRecordDecl::base_class_iterator B = Record->bases_begin(),
487                                         BEnd = Record->bases_end();
488         B != BEnd; ++B) {
489      QualType BaseType = B->getType();
490
491      // Don't look into dependent bases, because name lookup can't look
492      // there anyway.
493      if (BaseType->isDependentType())
494        continue;
495
496      const RecordType *Record = BaseType->getAs<RecordType>();
497      if (!Record)
498        continue;
499
500      // FIXME: It would be nice to be able to determine whether referencing
501      // a particular member would be ambiguous. For example, given
502      //
503      //   struct A { int member; };
504      //   struct B { int member; };
505      //   struct C : A, B { };
506      //
507      //   void f(C *c) { c->### }
508      // accessing 'member' would result in an ambiguity. However, code
509      // completion could be smart enough to qualify the member with the
510      // base class, e.g.,
511      //
512      //   c->B::member
513      //
514      // or
515      //
516      //   c->A::member
517
518      // Collect results from this base class (and its bases).
519      CollectMemberLookupResults(Record->getDecl(), Rank, CurContext, Visited,
520                                 Results, /*InBaseClass=*/true);
521    }
522  }
523
524  // FIXME: Look into base classes in Objective-C!
525
526  Results.ExitScope();
527  return Rank + 1;
528}
529
530/// \brief Collect the results of searching for members within the given
531/// declaration context.
532///
533/// \param Ctx the declaration context from which we will gather results.
534///
535/// \param InitialRank the initial rank given to results in this declaration
536/// context. Larger rank values will be used for, e.g., members found in
537/// base classes.
538///
539/// \param Results the result set that will be extended with any results
540/// found within this declaration context (and, for a C++ class, its bases).
541///
542/// \returns the next higher rank value, after considering all of the
543/// names within this declaration context.
544static unsigned CollectMemberLookupResults(DeclContext *Ctx,
545                                           unsigned InitialRank,
546                                           DeclContext *CurContext,
547                                           ResultBuilder &Results) {
548  llvm::SmallPtrSet<DeclContext *, 16> Visited;
549  return CollectMemberLookupResults(Ctx, InitialRank, CurContext, Visited,
550                                    Results);
551}
552
553/// \brief Collect the results of searching for declarations within the given
554/// scope and its parent scopes.
555///
556/// \param S the scope in which we will start looking for declarations.
557///
558/// \param InitialRank the initial rank given to results in this scope.
559/// Larger rank values will be used for results found in parent scopes.
560///
561/// \param CurContext the context from which lookup results will be found.
562///
563/// \param Results the builder object that will receive each result.
564static unsigned CollectLookupResults(Scope *S,
565                                     TranslationUnitDecl *TranslationUnit,
566                                     unsigned InitialRank,
567                                     DeclContext *CurContext,
568                                     ResultBuilder &Results) {
569  if (!S)
570    return InitialRank;
571
572  // FIXME: Using directives!
573
574  unsigned NextRank = InitialRank;
575  Results.EnterNewScope();
576  if (S->getEntity() &&
577      !((DeclContext *)S->getEntity())->isFunctionOrMethod()) {
578    // Look into this scope's declaration context, along with any of its
579    // parent lookup contexts (e.g., enclosing classes), up to the point
580    // where we hit the context stored in the next outer scope.
581    DeclContext *Ctx = (DeclContext *)S->getEntity();
582    DeclContext *OuterCtx = findOuterContext(S);
583
584    for (; Ctx && Ctx->getPrimaryContext() != OuterCtx;
585         Ctx = Ctx->getLookupParent()) {
586      if (Ctx->isFunctionOrMethod())
587        continue;
588
589      NextRank = CollectMemberLookupResults(Ctx, NextRank + 1, CurContext,
590                                            Results);
591    }
592  } else if (!S->getParent()) {
593    // Look into the translation unit scope. We walk through the translation
594    // unit's declaration context, because the Scope itself won't have all of
595    // the declarations if we loaded a precompiled header.
596    // FIXME: We would like the translation unit's Scope object to point to the
597    // translation unit, so we don't need this special "if" branch. However,
598    // doing so would force the normal C++ name-lookup code to look into the
599    // translation unit decl when the IdentifierInfo chains would suffice.
600    // Once we fix that problem (which is part of a more general "don't look
601    // in DeclContexts unless we have to" optimization), we can eliminate the
602    // TranslationUnit parameter entirely.
603    NextRank = CollectMemberLookupResults(TranslationUnit, NextRank + 1,
604                                          CurContext, Results);
605  } else {
606    // Walk through the declarations in this Scope.
607    for (Scope::decl_iterator D = S->decl_begin(), DEnd = S->decl_end();
608         D != DEnd; ++D) {
609      if (NamedDecl *ND = dyn_cast<NamedDecl>((Decl *)((*D).get())))
610        Results.MaybeAddResult(CodeCompleteConsumer::Result(ND, NextRank),
611                               CurContext);
612    }
613
614    NextRank = NextRank + 1;
615  }
616
617  // Lookup names in the parent scope.
618  NextRank = CollectLookupResults(S->getParent(), TranslationUnit, NextRank,
619                                  CurContext, Results);
620  Results.ExitScope();
621
622  return NextRank;
623}
624
625/// \brief Add type specifiers for the current language as keyword results.
626static void AddTypeSpecifierResults(const LangOptions &LangOpts, unsigned Rank,
627                                    ResultBuilder &Results) {
628  typedef CodeCompleteConsumer::Result Result;
629  Results.MaybeAddResult(Result("short", Rank));
630  Results.MaybeAddResult(Result("long", Rank));
631  Results.MaybeAddResult(Result("signed", Rank));
632  Results.MaybeAddResult(Result("unsigned", Rank));
633  Results.MaybeAddResult(Result("void", Rank));
634  Results.MaybeAddResult(Result("char", Rank));
635  Results.MaybeAddResult(Result("int", Rank));
636  Results.MaybeAddResult(Result("float", Rank));
637  Results.MaybeAddResult(Result("double", Rank));
638  Results.MaybeAddResult(Result("enum", Rank));
639  Results.MaybeAddResult(Result("struct", Rank));
640  Results.MaybeAddResult(Result("union", Rank));
641
642  if (LangOpts.C99) {
643    // C99-specific
644    Results.MaybeAddResult(Result("_Complex", Rank));
645    Results.MaybeAddResult(Result("_Imaginary", Rank));
646    Results.MaybeAddResult(Result("_Bool", Rank));
647  }
648
649  if (LangOpts.CPlusPlus) {
650    // C++-specific
651    Results.MaybeAddResult(Result("bool", Rank));
652    Results.MaybeAddResult(Result("class", Rank));
653    Results.MaybeAddResult(Result("typename", Rank));
654    Results.MaybeAddResult(Result("wchar_t", Rank));
655
656    if (LangOpts.CPlusPlus0x) {
657      Results.MaybeAddResult(Result("char16_t", Rank));
658      Results.MaybeAddResult(Result("char32_t", Rank));
659      Results.MaybeAddResult(Result("decltype", Rank));
660    }
661  }
662
663  // GNU extensions
664  if (LangOpts.GNUMode) {
665    // FIXME: Enable when we actually support decimal floating point.
666    //    Results.MaybeAddResult(Result("_Decimal32", Rank));
667    //    Results.MaybeAddResult(Result("_Decimal64", Rank));
668    //    Results.MaybeAddResult(Result("_Decimal128", Rank));
669    Results.MaybeAddResult(Result("typeof", Rank));
670  }
671}
672
673/// \brief Add function parameter chunks to the given code completion string.
674static void AddFunctionParameterChunks(ASTContext &Context,
675                                       FunctionDecl *Function,
676                                       CodeCompletionString *Result) {
677  typedef CodeCompletionString::Chunk Chunk;
678
679  CodeCompletionString *CCStr = Result;
680
681  for (unsigned P = 0, N = Function->getNumParams(); P != N; ++P) {
682    ParmVarDecl *Param = Function->getParamDecl(P);
683
684    if (Param->hasDefaultArg()) {
685      // When we see an optional default argument, put that argument and
686      // the remaining default arguments into a new, optional string.
687      CodeCompletionString *Opt = new CodeCompletionString;
688      CCStr->AddOptionalChunk(std::auto_ptr<CodeCompletionString>(Opt));
689      CCStr = Opt;
690    }
691
692    if (P != 0)
693      CCStr->AddChunk(Chunk(CodeCompletionString::CK_Comma));
694
695    // Format the placeholder string.
696    std::string PlaceholderStr;
697    if (Param->getIdentifier())
698      PlaceholderStr = Param->getIdentifier()->getName();
699
700    Param->getType().getAsStringInternal(PlaceholderStr,
701                                         Context.PrintingPolicy);
702
703    // Add the placeholder string.
704    CCStr->AddPlaceholderChunk(PlaceholderStr.c_str());
705  }
706
707  if (const FunctionProtoType *Proto
708        = Function->getType()->getAs<FunctionProtoType>())
709    if (Proto->isVariadic())
710      CCStr->AddPlaceholderChunk(", ...");
711}
712
713/// \brief Add template parameter chunks to the given code completion string.
714static void AddTemplateParameterChunks(ASTContext &Context,
715                                       TemplateDecl *Template,
716                                       CodeCompletionString *Result,
717                                       unsigned MaxParameters = 0) {
718  typedef CodeCompletionString::Chunk Chunk;
719
720  CodeCompletionString *CCStr = Result;
721  bool FirstParameter = true;
722
723  TemplateParameterList *Params = Template->getTemplateParameters();
724  TemplateParameterList::iterator PEnd = Params->end();
725  if (MaxParameters)
726    PEnd = Params->begin() + MaxParameters;
727  for (TemplateParameterList::iterator P = Params->begin(); P != PEnd; ++P) {
728    bool HasDefaultArg = false;
729    std::string PlaceholderStr;
730    if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*P)) {
731      if (TTP->wasDeclaredWithTypename())
732        PlaceholderStr = "typename";
733      else
734        PlaceholderStr = "class";
735
736      if (TTP->getIdentifier()) {
737        PlaceholderStr += ' ';
738        PlaceholderStr += TTP->getIdentifier()->getName();
739      }
740
741      HasDefaultArg = TTP->hasDefaultArgument();
742    } else if (NonTypeTemplateParmDecl *NTTP
743               = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
744      if (NTTP->getIdentifier())
745        PlaceholderStr = NTTP->getIdentifier()->getName();
746      NTTP->getType().getAsStringInternal(PlaceholderStr,
747                                          Context.PrintingPolicy);
748      HasDefaultArg = NTTP->hasDefaultArgument();
749    } else {
750      assert(isa<TemplateTemplateParmDecl>(*P));
751      TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
752
753      // Since putting the template argument list into the placeholder would
754      // be very, very long, we just use an abbreviation.
755      PlaceholderStr = "template<...> class";
756      if (TTP->getIdentifier()) {
757        PlaceholderStr += ' ';
758        PlaceholderStr += TTP->getIdentifier()->getName();
759      }
760
761      HasDefaultArg = TTP->hasDefaultArgument();
762    }
763
764    if (HasDefaultArg) {
765      // When we see an optional default argument, put that argument and
766      // the remaining default arguments into a new, optional string.
767      CodeCompletionString *Opt = new CodeCompletionString;
768      CCStr->AddOptionalChunk(std::auto_ptr<CodeCompletionString>(Opt));
769      CCStr = Opt;
770    }
771
772    if (FirstParameter)
773      FirstParameter = false;
774    else
775      CCStr->AddChunk(Chunk(CodeCompletionString::CK_Comma));
776
777    // Add the placeholder string.
778    CCStr->AddPlaceholderChunk(PlaceholderStr.c_str());
779  }
780}
781
782/// \brief Add a qualifier to the given code-completion string, if the
783/// provided nested-name-specifier is non-NULL.
784void AddQualifierToCompletionString(CodeCompletionString *Result,
785                                    NestedNameSpecifier *Qualifier,
786                                    bool QualifierIsInformative,
787                                    ASTContext &Context) {
788  if (!Qualifier)
789    return;
790
791  std::string PrintedNNS;
792  {
793    llvm::raw_string_ostream OS(PrintedNNS);
794    Qualifier->print(OS, Context.PrintingPolicy);
795  }
796  if (QualifierIsInformative)
797    Result->AddInformativeChunk(PrintedNNS.c_str());
798  else
799    Result->AddTextChunk(PrintedNNS.c_str());
800}
801
802/// \brief If possible, create a new code completion string for the given
803/// result.
804///
805/// \returns Either a new, heap-allocated code completion string describing
806/// how to use this result, or NULL to indicate that the string or name of the
807/// result is all that is needed.
808CodeCompletionString *
809CodeCompleteConsumer::Result::CreateCodeCompletionString(Sema &S) {
810  typedef CodeCompletionString::Chunk Chunk;
811
812  if (Kind == RK_Keyword)
813    return 0;
814
815  if (Kind == RK_Macro) {
816    MacroInfo *MI = S.PP.getMacroInfo(Macro);
817    if (!MI || !MI->isFunctionLike())
818      return 0;
819
820    // Format a function-like macro with placeholders for the arguments.
821    CodeCompletionString *Result = new CodeCompletionString;
822    Result->AddTypedTextChunk(Macro->getName().str().c_str());
823    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
824    for (MacroInfo::arg_iterator A = MI->arg_begin(), AEnd = MI->arg_end();
825         A != AEnd; ++A) {
826      if (A != MI->arg_begin())
827        Result->AddChunk(Chunk(CodeCompletionString::CK_Comma));
828
829      if (!MI->isVariadic() || A != AEnd - 1) {
830        // Non-variadic argument.
831        Result->AddPlaceholderChunk((*A)->getName().str().c_str());
832        continue;
833      }
834
835      // Variadic argument; cope with the different between GNU and C99
836      // variadic macros, providing a single placeholder for the rest of the
837      // arguments.
838      if ((*A)->isStr("__VA_ARGS__"))
839        Result->AddPlaceholderChunk("...");
840      else {
841        std::string Arg = (*A)->getName();
842        Arg += "...";
843        Result->AddPlaceholderChunk(Arg.c_str());
844      }
845    }
846    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
847    return Result;
848  }
849
850  assert(Kind == RK_Declaration && "Missed a macro kind?");
851  NamedDecl *ND = Declaration;
852
853  if (StartsNestedNameSpecifier) {
854    CodeCompletionString *Result = new CodeCompletionString;
855    Result->AddTypedTextChunk(ND->getNameAsString().c_str());
856    Result->AddTextChunk("::");
857    return Result;
858  }
859
860  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(ND)) {
861    CodeCompletionString *Result = new CodeCompletionString;
862    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
863                                   S.Context);
864    Result->AddTypedTextChunk(Function->getNameAsString().c_str());
865    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
866    AddFunctionParameterChunks(S.Context, Function, Result);
867    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
868    return Result;
869  }
870
871  if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(ND)) {
872    CodeCompletionString *Result = new CodeCompletionString;
873    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
874                                   S.Context);
875    FunctionDecl *Function = FunTmpl->getTemplatedDecl();
876    Result->AddTypedTextChunk(Function->getNameAsString().c_str());
877
878    // Figure out which template parameters are deduced (or have default
879    // arguments).
880    llvm::SmallVector<bool, 16> Deduced;
881    S.MarkDeducedTemplateParameters(FunTmpl, Deduced);
882    unsigned LastDeducibleArgument;
883    for (LastDeducibleArgument = Deduced.size(); LastDeducibleArgument > 0;
884         --LastDeducibleArgument) {
885      if (!Deduced[LastDeducibleArgument - 1]) {
886        // C++0x: Figure out if the template argument has a default. If so,
887        // the user doesn't need to type this argument.
888        // FIXME: We need to abstract template parameters better!
889        bool HasDefaultArg = false;
890        NamedDecl *Param = FunTmpl->getTemplateParameters()->getParam(
891                                                                      LastDeducibleArgument - 1);
892        if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
893          HasDefaultArg = TTP->hasDefaultArgument();
894        else if (NonTypeTemplateParmDecl *NTTP
895                 = dyn_cast<NonTypeTemplateParmDecl>(Param))
896          HasDefaultArg = NTTP->hasDefaultArgument();
897        else {
898          assert(isa<TemplateTemplateParmDecl>(Param));
899          HasDefaultArg
900            = cast<TemplateTemplateParmDecl>(Param)->hasDefaultArgument();
901        }
902
903        if (!HasDefaultArg)
904          break;
905      }
906    }
907
908    if (LastDeducibleArgument) {
909      // Some of the function template arguments cannot be deduced from a
910      // function call, so we introduce an explicit template argument list
911      // containing all of the arguments up to the first deducible argument.
912      Result->AddChunk(Chunk(CodeCompletionString::CK_LeftAngle));
913      AddTemplateParameterChunks(S.Context, FunTmpl, Result,
914                                 LastDeducibleArgument);
915      Result->AddChunk(Chunk(CodeCompletionString::CK_RightAngle));
916    }
917
918    // Add the function parameters
919    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
920    AddFunctionParameterChunks(S.Context, Function, Result);
921    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
922    return Result;
923  }
924
925  if (TemplateDecl *Template = dyn_cast<TemplateDecl>(ND)) {
926    CodeCompletionString *Result = new CodeCompletionString;
927    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
928                                   S.Context);
929    Result->AddTypedTextChunk(Template->getNameAsString().c_str());
930    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftAngle));
931    AddTemplateParameterChunks(S.Context, Template, Result);
932    Result->AddChunk(Chunk(CodeCompletionString::CK_RightAngle));
933    return Result;
934  }
935
936  if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(ND)) {
937    CodeCompletionString *Result = new CodeCompletionString;
938    Selector Sel = Method->getSelector();
939    if (Sel.isUnarySelector()) {
940      Result->AddTypedTextChunk(Sel.getIdentifierInfoForSlot(0)->getName());
941      return Result;
942    }
943
944    Result->AddTypedTextChunk(
945          Sel.getIdentifierInfoForSlot(0)->getName().str() + std::string(":"));
946    unsigned Idx = 0;
947    for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
948                                     PEnd = Method->param_end();
949         P != PEnd; (void)++P, ++Idx) {
950      if (Idx > 0) {
951        std::string Keyword = " ";
952        if (IdentifierInfo *II = Sel.getIdentifierInfoForSlot(Idx))
953          Keyword += II->getName().str();
954        Keyword += ":";
955        Result->AddTextChunk(Keyword);
956      }
957
958      std::string Arg;
959      (*P)->getType().getAsStringInternal(Arg, S.Context.PrintingPolicy);
960      Arg = "(" + Arg + ")";
961      if (IdentifierInfo *II = (*P)->getIdentifier())
962        Arg += II->getName().str();
963      Result->AddPlaceholderChunk(Arg);
964    }
965
966    return Result;
967  }
968
969  if (Qualifier) {
970    CodeCompletionString *Result = new CodeCompletionString;
971    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
972                                   S.Context);
973    Result->AddTypedTextChunk(ND->getNameAsString().c_str());
974    return Result;
975  }
976
977  return 0;
978}
979
980CodeCompletionString *
981CodeCompleteConsumer::OverloadCandidate::CreateSignatureString(
982                                                          unsigned CurrentArg,
983                                                               Sema &S) const {
984  typedef CodeCompletionString::Chunk Chunk;
985
986  CodeCompletionString *Result = new CodeCompletionString;
987  FunctionDecl *FDecl = getFunction();
988  const FunctionProtoType *Proto
989    = dyn_cast<FunctionProtoType>(getFunctionType());
990  if (!FDecl && !Proto) {
991    // Function without a prototype. Just give the return type and a
992    // highlighted ellipsis.
993    const FunctionType *FT = getFunctionType();
994    Result->AddTextChunk(
995            FT->getResultType().getAsString(S.Context.PrintingPolicy).c_str());
996    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
997    Result->AddChunk(Chunk(CodeCompletionString::CK_CurrentParameter, "..."));
998    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
999    return Result;
1000  }
1001
1002  if (FDecl)
1003    Result->AddTextChunk(FDecl->getNameAsString().c_str());
1004  else
1005    Result->AddTextChunk(
1006         Proto->getResultType().getAsString(S.Context.PrintingPolicy).c_str());
1007
1008  Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
1009  unsigned NumParams = FDecl? FDecl->getNumParams() : Proto->getNumArgs();
1010  for (unsigned I = 0; I != NumParams; ++I) {
1011    if (I)
1012      Result->AddChunk(Chunk(CodeCompletionString::CK_Comma));
1013
1014    std::string ArgString;
1015    QualType ArgType;
1016
1017    if (FDecl) {
1018      ArgString = FDecl->getParamDecl(I)->getNameAsString();
1019      ArgType = FDecl->getParamDecl(I)->getOriginalType();
1020    } else {
1021      ArgType = Proto->getArgType(I);
1022    }
1023
1024    ArgType.getAsStringInternal(ArgString, S.Context.PrintingPolicy);
1025
1026    if (I == CurrentArg)
1027      Result->AddChunk(Chunk(CodeCompletionString::CK_CurrentParameter,
1028                             ArgString.c_str()));
1029    else
1030      Result->AddTextChunk(ArgString.c_str());
1031  }
1032
1033  if (Proto && Proto->isVariadic()) {
1034    Result->AddChunk(Chunk(CodeCompletionString::CK_Comma));
1035    if (CurrentArg < NumParams)
1036      Result->AddTextChunk("...");
1037    else
1038      Result->AddChunk(Chunk(CodeCompletionString::CK_CurrentParameter, "..."));
1039  }
1040  Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
1041
1042  return Result;
1043}
1044
1045namespace {
1046  struct SortCodeCompleteResult {
1047    typedef CodeCompleteConsumer::Result Result;
1048
1049    bool isEarlierDeclarationName(DeclarationName X, DeclarationName Y) const {
1050      if (!X.getObjCSelector().isNull() && !Y.getObjCSelector().isNull()) {
1051        // Consider all selector kinds to be equivalent.
1052      } else if (X.getNameKind() != Y.getNameKind())
1053        return X.getNameKind() < Y.getNameKind();
1054
1055      return llvm::LowercaseString(X.getAsString())
1056        < llvm::LowercaseString(Y.getAsString());
1057    }
1058
1059    bool operator()(const Result &X, const Result &Y) const {
1060      // Sort first by rank.
1061      if (X.Rank < Y.Rank)
1062        return true;
1063      else if (X.Rank > Y.Rank)
1064        return false;
1065
1066      // Result kinds are ordered by decreasing importance.
1067      if (X.Kind < Y.Kind)
1068        return true;
1069      else if (X.Kind > Y.Kind)
1070        return false;
1071
1072      // Non-hidden names precede hidden names.
1073      if (X.Hidden != Y.Hidden)
1074        return !X.Hidden;
1075
1076      // Non-nested-name-specifiers precede nested-name-specifiers.
1077      if (X.StartsNestedNameSpecifier != Y.StartsNestedNameSpecifier)
1078        return !X.StartsNestedNameSpecifier;
1079
1080      // Ordering depends on the kind of result.
1081      switch (X.Kind) {
1082        case Result::RK_Declaration:
1083          // Order based on the declaration names.
1084          return isEarlierDeclarationName(X.Declaration->getDeclName(),
1085                                          Y.Declaration->getDeclName());
1086
1087        case Result::RK_Keyword:
1088          return strcmp(X.Keyword, Y.Keyword) < 0;
1089
1090        case Result::RK_Macro:
1091          return llvm::LowercaseString(X.Macro->getName()) <
1092                   llvm::LowercaseString(Y.Macro->getName());
1093      }
1094
1095      // Silence GCC warning.
1096      return false;
1097    }
1098  };
1099}
1100
1101static void AddMacroResults(Preprocessor &PP, unsigned Rank,
1102                            ResultBuilder &Results) {
1103  Results.EnterNewScope();
1104  for (Preprocessor::macro_iterator M = PP.macro_begin(),
1105                                 MEnd = PP.macro_end();
1106       M != MEnd; ++M)
1107    Results.MaybeAddResult(CodeCompleteConsumer::Result(M->first, Rank));
1108  Results.ExitScope();
1109}
1110
1111static void HandleCodeCompleteResults(Sema *S,
1112                                      CodeCompleteConsumer *CodeCompleter,
1113                                     CodeCompleteConsumer::Result *Results,
1114                                     unsigned NumResults) {
1115  // Sort the results by rank/kind/etc.
1116  std::stable_sort(Results, Results + NumResults, SortCodeCompleteResult());
1117
1118  if (CodeCompleter)
1119    CodeCompleter->ProcessCodeCompleteResults(*S, Results, NumResults);
1120}
1121
1122void Sema::CodeCompleteOrdinaryName(Scope *S) {
1123  ResultBuilder Results(*this, &ResultBuilder::IsOrdinaryName);
1124  unsigned NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1125                                           0, CurContext, Results);
1126  if (CodeCompleter->includeMacros())
1127    AddMacroResults(PP, NextRank, Results);
1128  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1129}
1130
1131void Sema::CodeCompleteMemberReferenceExpr(Scope *S, ExprTy *BaseE,
1132                                           SourceLocation OpLoc,
1133                                           bool IsArrow) {
1134  if (!BaseE || !CodeCompleter)
1135    return;
1136
1137  typedef CodeCompleteConsumer::Result Result;
1138
1139  Expr *Base = static_cast<Expr *>(BaseE);
1140  QualType BaseType = Base->getType();
1141
1142  if (IsArrow) {
1143    if (const PointerType *Ptr = BaseType->getAs<PointerType>())
1144      BaseType = Ptr->getPointeeType();
1145    else if (BaseType->isObjCObjectPointerType())
1146    /*Do nothing*/ ;
1147    else
1148      return;
1149  }
1150
1151  ResultBuilder Results(*this, &ResultBuilder::IsMember);
1152  unsigned NextRank = 0;
1153
1154  // If this isn't a record type, we are done.
1155  const RecordType *Record = BaseType->getAs<RecordType>();
1156  if (!Record)
1157    return;
1158
1159  NextRank = CollectMemberLookupResults(Record->getDecl(), NextRank,
1160                                        Record->getDecl(), Results);
1161
1162  if (getLangOptions().CPlusPlus) {
1163    if (!Results.empty()) {
1164      // The "template" keyword can follow "->" or "." in the grammar.
1165      // However, we only want to suggest the template keyword if something
1166      // is dependent.
1167      bool IsDependent = BaseType->isDependentType();
1168      if (!IsDependent) {
1169        for (Scope *DepScope = S; DepScope; DepScope = DepScope->getParent())
1170          if (DeclContext *Ctx = (DeclContext *)DepScope->getEntity()) {
1171            IsDependent = Ctx->isDependentContext();
1172            break;
1173          }
1174      }
1175
1176      if (IsDependent)
1177        Results.MaybeAddResult(Result("template", NextRank++));
1178    }
1179
1180    // We could have the start of a nested-name-specifier. Add those
1181    // results as well.
1182    Results.setFilter(&ResultBuilder::IsNestedNameSpecifier);
1183    CollectLookupResults(S, Context.getTranslationUnitDecl(), NextRank,
1184                         CurContext, Results);
1185  }
1186
1187  // Add macros
1188  if (CodeCompleter->includeMacros())
1189    AddMacroResults(PP, NextRank, Results);
1190
1191  // Hand off the results found for code completion.
1192  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1193}
1194
1195void Sema::CodeCompleteTag(Scope *S, unsigned TagSpec) {
1196  if (!CodeCompleter)
1197    return;
1198
1199  typedef CodeCompleteConsumer::Result Result;
1200  ResultBuilder::LookupFilter Filter = 0;
1201  switch ((DeclSpec::TST)TagSpec) {
1202  case DeclSpec::TST_enum:
1203    Filter = &ResultBuilder::IsEnum;
1204    break;
1205
1206  case DeclSpec::TST_union:
1207    Filter = &ResultBuilder::IsUnion;
1208    break;
1209
1210  case DeclSpec::TST_struct:
1211  case DeclSpec::TST_class:
1212    Filter = &ResultBuilder::IsClassOrStruct;
1213    break;
1214
1215  default:
1216    assert(false && "Unknown type specifier kind in CodeCompleteTag");
1217    return;
1218  }
1219
1220  ResultBuilder Results(*this, Filter);
1221  unsigned NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1222                                           0, CurContext, Results);
1223
1224  if (getLangOptions().CPlusPlus) {
1225    // We could have the start of a nested-name-specifier. Add those
1226    // results as well.
1227    Results.setFilter(&ResultBuilder::IsNestedNameSpecifier);
1228    NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1229                                    NextRank, CurContext, Results);
1230  }
1231
1232  if (CodeCompleter->includeMacros())
1233    AddMacroResults(PP, NextRank, Results);
1234  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1235}
1236
1237void Sema::CodeCompleteCase(Scope *S) {
1238  if (getSwitchStack().empty() || !CodeCompleter)
1239    return;
1240
1241  SwitchStmt *Switch = getSwitchStack().back();
1242  if (!Switch->getCond()->getType()->isEnumeralType())
1243    return;
1244
1245  // Code-complete the cases of a switch statement over an enumeration type
1246  // by providing the list of
1247  EnumDecl *Enum = Switch->getCond()->getType()->getAs<EnumType>()->getDecl();
1248
1249  // Determine which enumerators we have already seen in the switch statement.
1250  // FIXME: Ideally, we would also be able to look *past* the code-completion
1251  // token, in case we are code-completing in the middle of the switch and not
1252  // at the end. However, we aren't able to do so at the moment.
1253  llvm::SmallPtrSet<EnumConstantDecl *, 8> EnumeratorsSeen;
1254  NestedNameSpecifier *Qualifier = 0;
1255  for (SwitchCase *SC = Switch->getSwitchCaseList(); SC;
1256       SC = SC->getNextSwitchCase()) {
1257    CaseStmt *Case = dyn_cast<CaseStmt>(SC);
1258    if (!Case)
1259      continue;
1260
1261    Expr *CaseVal = Case->getLHS()->IgnoreParenCasts();
1262    if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(CaseVal))
1263      if (EnumConstantDecl *Enumerator
1264            = dyn_cast<EnumConstantDecl>(DRE->getDecl())) {
1265        // We look into the AST of the case statement to determine which
1266        // enumerator was named. Alternatively, we could compute the value of
1267        // the integral constant expression, then compare it against the
1268        // values of each enumerator. However, value-based approach would not
1269        // work as well with C++ templates where enumerators declared within a
1270        // template are type- and value-dependent.
1271        EnumeratorsSeen.insert(Enumerator);
1272
1273        // If this is a qualified-id, keep track of the nested-name-specifier
1274        // so that we can reproduce it as part of code completion, e.g.,
1275        //
1276        //   switch (TagD.getKind()) {
1277        //     case TagDecl::TK_enum:
1278        //       break;
1279        //     case XXX
1280        //
1281        // At the XXX, our completions are TagDecl::TK_union,
1282        // TagDecl::TK_struct, and TagDecl::TK_class, rather than TK_union,
1283        // TK_struct, and TK_class.
1284        Qualifier = DRE->getQualifier();
1285      }
1286  }
1287
1288  if (getLangOptions().CPlusPlus && !Qualifier && EnumeratorsSeen.empty()) {
1289    // If there are no prior enumerators in C++, check whether we have to
1290    // qualify the names of the enumerators that we suggest, because they
1291    // may not be visible in this scope.
1292    Qualifier = getRequiredQualification(Context, CurContext,
1293                                         Enum->getDeclContext());
1294
1295    // FIXME: Scoped enums need to start with "EnumDecl" as the context!
1296  }
1297
1298  // Add any enumerators that have not yet been mentioned.
1299  ResultBuilder Results(*this);
1300  Results.EnterNewScope();
1301  for (EnumDecl::enumerator_iterator E = Enum->enumerator_begin(),
1302                                  EEnd = Enum->enumerator_end();
1303       E != EEnd; ++E) {
1304    if (EnumeratorsSeen.count(*E))
1305      continue;
1306
1307    Results.MaybeAddResult(CodeCompleteConsumer::Result(*E, 0, Qualifier));
1308  }
1309  Results.ExitScope();
1310
1311  if (CodeCompleter->includeMacros())
1312    AddMacroResults(PP, 1, Results);
1313  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1314}
1315
1316namespace {
1317  struct IsBetterOverloadCandidate {
1318    Sema &S;
1319
1320  public:
1321    explicit IsBetterOverloadCandidate(Sema &S) : S(S) { }
1322
1323    bool
1324    operator()(const OverloadCandidate &X, const OverloadCandidate &Y) const {
1325      return S.isBetterOverloadCandidate(X, Y);
1326    }
1327  };
1328}
1329
1330void Sema::CodeCompleteCall(Scope *S, ExprTy *FnIn,
1331                            ExprTy **ArgsIn, unsigned NumArgs) {
1332  if (!CodeCompleter)
1333    return;
1334
1335  Expr *Fn = (Expr *)FnIn;
1336  Expr **Args = (Expr **)ArgsIn;
1337
1338  // Ignore type-dependent call expressions entirely.
1339  if (Fn->isTypeDependent() ||
1340      Expr::hasAnyTypeDependentArguments(Args, NumArgs))
1341    return;
1342
1343  NamedDecl *Function;
1344  DeclarationName UnqualifiedName;
1345  NestedNameSpecifier *Qualifier;
1346  SourceRange QualifierRange;
1347  bool ArgumentDependentLookup;
1348  bool HasExplicitTemplateArgs;
1349  const TemplateArgumentLoc *ExplicitTemplateArgs;
1350  unsigned NumExplicitTemplateArgs;
1351
1352  DeconstructCallFunction(Fn,
1353                          Function, UnqualifiedName, Qualifier, QualifierRange,
1354                          ArgumentDependentLookup, HasExplicitTemplateArgs,
1355                          ExplicitTemplateArgs, NumExplicitTemplateArgs);
1356
1357
1358  // FIXME: What if we're calling something that isn't a function declaration?
1359  // FIXME: What if we're calling a pseudo-destructor?
1360  // FIXME: What if we're calling a member function?
1361
1362  // Build an overload candidate set based on the functions we find.
1363  OverloadCandidateSet CandidateSet;
1364  AddOverloadedCallCandidates(Function, UnqualifiedName,
1365                              ArgumentDependentLookup, HasExplicitTemplateArgs,
1366                              ExplicitTemplateArgs, NumExplicitTemplateArgs,
1367                              Args, NumArgs,
1368                              CandidateSet,
1369                              /*PartialOverloading=*/true);
1370
1371  // Sort the overload candidate set by placing the best overloads first.
1372  std::stable_sort(CandidateSet.begin(), CandidateSet.end(),
1373                   IsBetterOverloadCandidate(*this));
1374
1375  // Add the remaining viable overload candidates as code-completion reslults.
1376  typedef CodeCompleteConsumer::OverloadCandidate ResultCandidate;
1377  llvm::SmallVector<ResultCandidate, 8> Results;
1378
1379  for (OverloadCandidateSet::iterator Cand = CandidateSet.begin(),
1380                                   CandEnd = CandidateSet.end();
1381       Cand != CandEnd; ++Cand) {
1382    if (Cand->Viable)
1383      Results.push_back(ResultCandidate(Cand->Function));
1384  }
1385  CodeCompleter->ProcessOverloadCandidates(*this, NumArgs, Results.data(),
1386                                           Results.size());
1387}
1388
1389void Sema::CodeCompleteQualifiedId(Scope *S, const CXXScopeSpec &SS,
1390                                   bool EnteringContext) {
1391  if (!SS.getScopeRep() || !CodeCompleter)
1392    return;
1393
1394  DeclContext *Ctx = computeDeclContext(SS, EnteringContext);
1395  if (!Ctx)
1396    return;
1397
1398  ResultBuilder Results(*this);
1399  unsigned NextRank = CollectMemberLookupResults(Ctx, 0, Ctx, Results);
1400
1401  // The "template" keyword can follow "::" in the grammar, but only
1402  // put it into the grammar if the nested-name-specifier is dependent.
1403  NestedNameSpecifier *NNS = (NestedNameSpecifier *)SS.getScopeRep();
1404  if (!Results.empty() && NNS->isDependent())
1405    Results.MaybeAddResult(CodeCompleteConsumer::Result("template", NextRank));
1406
1407  if (CodeCompleter->includeMacros())
1408    AddMacroResults(PP, NextRank + 1, Results);
1409  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1410}
1411
1412void Sema::CodeCompleteUsing(Scope *S) {
1413  if (!CodeCompleter)
1414    return;
1415
1416  ResultBuilder Results(*this, &ResultBuilder::IsNestedNameSpecifier);
1417  Results.EnterNewScope();
1418
1419  // If we aren't in class scope, we could see the "namespace" keyword.
1420  if (!S->isClassScope())
1421    Results.MaybeAddResult(CodeCompleteConsumer::Result("namespace", 0));
1422
1423  // After "using", we can see anything that would start a
1424  // nested-name-specifier.
1425  unsigned NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1426                                           0, CurContext, Results);
1427  Results.ExitScope();
1428
1429  if (CodeCompleter->includeMacros())
1430    AddMacroResults(PP, NextRank, Results);
1431  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1432}
1433
1434void Sema::CodeCompleteUsingDirective(Scope *S) {
1435  if (!CodeCompleter)
1436    return;
1437
1438  // After "using namespace", we expect to see a namespace name or namespace
1439  // alias.
1440  ResultBuilder Results(*this, &ResultBuilder::IsNamespaceOrAlias);
1441  Results.EnterNewScope();
1442  unsigned NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1443                                           0, CurContext, Results);
1444  Results.ExitScope();
1445  if (CodeCompleter->includeMacros())
1446    AddMacroResults(PP, NextRank, Results);
1447  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1448}
1449
1450void Sema::CodeCompleteNamespaceDecl(Scope *S)  {
1451  if (!CodeCompleter)
1452    return;
1453
1454  ResultBuilder Results(*this, &ResultBuilder::IsNamespace);
1455  DeclContext *Ctx = (DeclContext *)S->getEntity();
1456  if (!S->getParent())
1457    Ctx = Context.getTranslationUnitDecl();
1458
1459  if (Ctx && Ctx->isFileContext()) {
1460    // We only want to see those namespaces that have already been defined
1461    // within this scope, because its likely that the user is creating an
1462    // extended namespace declaration. Keep track of the most recent
1463    // definition of each namespace.
1464    std::map<NamespaceDecl *, NamespaceDecl *> OrigToLatest;
1465    for (DeclContext::specific_decl_iterator<NamespaceDecl>
1466         NS(Ctx->decls_begin()), NSEnd(Ctx->decls_end());
1467         NS != NSEnd; ++NS)
1468      OrigToLatest[NS->getOriginalNamespace()] = *NS;
1469
1470    // Add the most recent definition (or extended definition) of each
1471    // namespace to the list of results.
1472    Results.EnterNewScope();
1473    for (std::map<NamespaceDecl *, NamespaceDecl *>::iterator
1474         NS = OrigToLatest.begin(), NSEnd = OrigToLatest.end();
1475         NS != NSEnd; ++NS)
1476      Results.MaybeAddResult(CodeCompleteConsumer::Result(NS->second, 0),
1477                             CurContext);
1478    Results.ExitScope();
1479  }
1480
1481  if (CodeCompleter->includeMacros())
1482    AddMacroResults(PP, 1, Results);
1483  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1484}
1485
1486void Sema::CodeCompleteNamespaceAliasDecl(Scope *S)  {
1487  if (!CodeCompleter)
1488    return;
1489
1490  // After "namespace", we expect to see a namespace or alias.
1491  ResultBuilder Results(*this, &ResultBuilder::IsNamespaceOrAlias);
1492  unsigned NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1493                                           0, CurContext, Results);
1494  if (CodeCompleter->includeMacros())
1495    AddMacroResults(PP, NextRank, Results);
1496  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1497}
1498
1499void Sema::CodeCompleteOperatorName(Scope *S) {
1500  if (!CodeCompleter)
1501    return;
1502
1503  typedef CodeCompleteConsumer::Result Result;
1504  ResultBuilder Results(*this, &ResultBuilder::IsType);
1505  Results.EnterNewScope();
1506
1507  // Add the names of overloadable operators.
1508#define OVERLOADED_OPERATOR(Name,Spelling,Token,Unary,Binary,MemberOnly)      \
1509  if (std::strcmp(Spelling, "?"))                                                  \
1510    Results.MaybeAddResult(Result(Spelling, 0));
1511#include "clang/Basic/OperatorKinds.def"
1512
1513  // Add any type names visible from the current scope
1514  unsigned NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1515                                           0, CurContext, Results);
1516
1517  // Add any type specifiers
1518  AddTypeSpecifierResults(getLangOptions(), 0, Results);
1519
1520  // Add any nested-name-specifiers
1521  Results.setFilter(&ResultBuilder::IsNestedNameSpecifier);
1522  NextRank = CollectLookupResults(S, Context.getTranslationUnitDecl(),
1523                                  NextRank + 1, CurContext, Results);
1524  Results.ExitScope();
1525
1526  if (CodeCompleter->includeMacros())
1527    AddMacroResults(PP, NextRank, Results);
1528  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1529}
1530
1531void Sema::CodeCompleteObjCProperty(Scope *S, ObjCDeclSpec &ODS) {
1532  if (!CodeCompleter)
1533    return;
1534  unsigned Attributes = ODS.getPropertyAttributes();
1535
1536  typedef CodeCompleteConsumer::Result Result;
1537  ResultBuilder Results(*this);
1538  Results.EnterNewScope();
1539  if (!(Attributes & ObjCDeclSpec::DQ_PR_readonly))
1540    Results.MaybeAddResult(CodeCompleteConsumer::Result("readonly", 0));
1541  if (!(Attributes & ObjCDeclSpec::DQ_PR_assign))
1542    Results.MaybeAddResult(CodeCompleteConsumer::Result("assign", 0));
1543  if (!(Attributes & ObjCDeclSpec::DQ_PR_readwrite))
1544    Results.MaybeAddResult(CodeCompleteConsumer::Result("readwrite", 0));
1545  if (!(Attributes & ObjCDeclSpec::DQ_PR_retain))
1546    Results.MaybeAddResult(CodeCompleteConsumer::Result("retain", 0));
1547  if (!(Attributes & ObjCDeclSpec::DQ_PR_copy))
1548    Results.MaybeAddResult(CodeCompleteConsumer::Result("copy", 0));
1549  if (!(Attributes & ObjCDeclSpec::DQ_PR_nonatomic))
1550    Results.MaybeAddResult(CodeCompleteConsumer::Result("nonatomic", 0));
1551  if (!(Attributes & ObjCDeclSpec::DQ_PR_setter))
1552    Results.MaybeAddResult(CodeCompleteConsumer::Result("setter", 0));
1553  if (!(Attributes & ObjCDeclSpec::DQ_PR_getter))
1554    Results.MaybeAddResult(CodeCompleteConsumer::Result("getter", 0));
1555  Results.ExitScope();
1556  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1557}
1558
1559/// \brief Add all of the Objective-C methods in the given Objective-C
1560/// container to the set of results.
1561///
1562/// The container will be a class, protocol, category, or implementation of
1563/// any of the above. This mether will recurse to include methods from
1564/// the superclasses of classes along with their categories, protocols, and
1565/// implementations.
1566///
1567/// \param Container the container in which we'll look to find methods.
1568///
1569/// \param WantInstance whether to add instance methods (only); if false, this
1570/// routine will add factory methods (only).
1571///
1572/// \param CurContext the context in which we're performing the lookup that
1573/// finds methods.
1574///
1575/// \param Results the structure into which we'll add results.
1576static void AddObjCMethods(ObjCContainerDecl *Container,
1577                           bool WantInstanceMethods,
1578                           DeclContext *CurContext,
1579                           ResultBuilder &Results) {
1580  typedef CodeCompleteConsumer::Result Result;
1581  for (ObjCContainerDecl::method_iterator M = Container->meth_begin(),
1582                                       MEnd = Container->meth_end();
1583       M != MEnd; ++M) {
1584    if ((*M)->isInstanceMethod() == WantInstanceMethods)
1585      Results.MaybeAddResult(Result(*M, 0), CurContext);
1586  }
1587
1588  ObjCInterfaceDecl *IFace = dyn_cast<ObjCInterfaceDecl>(Container);
1589  if (!IFace)
1590    return;
1591
1592  // Add methods in protocols.
1593  const ObjCList<ObjCProtocolDecl> &Protocols= IFace->getReferencedProtocols();
1594  for (ObjCList<ObjCProtocolDecl>::iterator I = Protocols.begin(),
1595                                            E = Protocols.end();
1596       I != E; ++I)
1597    AddObjCMethods(*I, WantInstanceMethods, CurContext, Results);
1598
1599  // Add methods in categories.
1600  for (ObjCCategoryDecl *CatDecl = IFace->getCategoryList(); CatDecl;
1601       CatDecl = CatDecl->getNextClassCategory()) {
1602    AddObjCMethods(CatDecl, WantInstanceMethods, CurContext, Results);
1603
1604    // Add a categories protocol methods.
1605    const ObjCList<ObjCProtocolDecl> &Protocols
1606      = CatDecl->getReferencedProtocols();
1607    for (ObjCList<ObjCProtocolDecl>::iterator I = Protocols.begin(),
1608                                              E = Protocols.end();
1609         I != E; ++I)
1610      AddObjCMethods(*I, WantInstanceMethods, CurContext, Results);
1611
1612    // Add methods in category implementations.
1613    if (ObjCCategoryImplDecl *Impl = CatDecl->getImplementation())
1614      AddObjCMethods(Impl, WantInstanceMethods, CurContext, Results);
1615  }
1616
1617  // Add methods in superclass.
1618  if (IFace->getSuperClass())
1619    AddObjCMethods(IFace->getSuperClass(), WantInstanceMethods, CurContext,
1620                   Results);
1621
1622  // Add methods in our implementation, if any.
1623  if (ObjCImplementationDecl *Impl = IFace->getImplementation())
1624    AddObjCMethods(Impl, WantInstanceMethods, CurContext, Results);
1625}
1626
1627void Sema::CodeCompleteObjCFactoryMethod(Scope *S, IdentifierInfo *FName) {
1628  typedef CodeCompleteConsumer::Result Result;
1629  ObjCInterfaceDecl *CDecl = 0;
1630
1631  // FIXME: Pass this in!
1632  SourceLocation NameLoc;
1633
1634  if (FName->isStr("super")) {
1635    // We're sending a message to "super".
1636    if (ObjCMethodDecl *CurMethod = getCurMethodDecl()) {
1637      // Figure out which interface we're in.
1638      CDecl = CurMethod->getClassInterface();
1639      if (!CDecl)
1640        return;
1641
1642      // Find the superclass of this class.
1643      CDecl = CDecl->getSuperClass();
1644      if (!CDecl)
1645        return;
1646
1647      if (CurMethod->isInstanceMethod()) {
1648        // We are inside an instance method, which means that the message
1649        // send [super ...] is actually calling an instance method on the
1650        // current object. Build the super expression and handle this like
1651        // an instance method.
1652        QualType SuperTy = Context.getObjCInterfaceType(CDecl);
1653        SuperTy = Context.getObjCObjectPointerType(SuperTy);
1654        OwningExprResult Super
1655          = Owned(new (Context) ObjCSuperExpr(NameLoc, SuperTy));
1656        return CodeCompleteObjCInstanceMethod(S, (Expr *)Super.get());
1657      }
1658
1659      // Okay, we're calling a factory method in our superclass.
1660    }
1661  }
1662
1663  // If the given name refers to an interface type, retrieve the
1664  // corresponding declaration.
1665  if (!CDecl)
1666    if (TypeTy *Ty = getTypeName(*FName, NameLoc, S, 0, false)) {
1667      QualType T = GetTypeFromParser(Ty, 0);
1668      if (!T.isNull())
1669        if (const ObjCInterfaceType *Interface = T->getAs<ObjCInterfaceType>())
1670          CDecl = Interface->getDecl();
1671    }
1672
1673  if (!CDecl && FName->isStr("super")) {
1674    // "super" may be the name of a variable, in which case we are
1675    // probably calling an instance method.
1676    OwningExprResult Super = ActOnDeclarationNameExpr(S, NameLoc, FName,
1677                                                      false, 0, false);
1678    return CodeCompleteObjCInstanceMethod(S, (Expr *)Super.get());
1679  }
1680
1681  // Add all of the factory methods in this Objective-C class, its protocols,
1682  // superclasses, categories, implementation, etc.
1683  ResultBuilder Results(*this);
1684  Results.EnterNewScope();
1685  AddObjCMethods(CDecl, false, CurContext, Results);
1686  Results.ExitScope();
1687
1688  // This also suppresses remaining diagnostics.
1689  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1690}
1691
1692void Sema::CodeCompleteObjCInstanceMethod(Scope *S, ExprTy *Receiver) {
1693  typedef CodeCompleteConsumer::Result Result;
1694
1695  Expr *RecExpr = static_cast<Expr *>(Receiver);
1696  QualType RecType = RecExpr->getType();
1697
1698  // If necessary, apply function/array conversion to the receiver.
1699  // C99 6.7.5.3p[7,8].
1700  DefaultFunctionArrayConversion(RecExpr);
1701  QualType ReceiverType = RecExpr->getType();
1702
1703  if (ReceiverType->isObjCIdType() || ReceiverType->isBlockPointerType()) {
1704    // FIXME: We're messaging 'id'. Do we actually want to look up every method
1705    // in the universe?
1706    return;
1707  }
1708
1709  const ObjCObjectPointerType* OCOPT
1710    = ReceiverType->getAs<ObjCObjectPointerType>();
1711  if (!OCOPT)
1712    return;
1713
1714  // FIXME: handle 'id', 'Class', and qualified types.
1715
1716  // Build the set of methods we can see.
1717  ResultBuilder Results(*this);
1718  Results.EnterNewScope();
1719
1720  ObjCInterfaceDecl *CDecl = OCOPT->getInterfaceDecl();
1721  if (!CDecl)
1722    return;
1723
1724  AddObjCMethods(CDecl, true, CurContext, Results);
1725  Results.ExitScope();
1726
1727  // This also suppresses remaining diagnostics.
1728  HandleCodeCompleteResults(this, CodeCompleter, Results.data(),Results.size());
1729}
1730