SemaCodeComplete.cpp revision a5fb7c3b56c3698e19a7c1e97d41150de33cf6c9 
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 "clang/Sema/Sema.h"
14#include "clang/Sema/Lookup.h"
15#include "clang/Sema/CodeCompleteConsumer.h"
16#include "clang/Sema/ExternalSemaSource.h"
17#include "clang/AST/ExprCXX.h"
18#include "clang/AST/ExprObjC.h"
19#include "clang/Lex/MacroInfo.h"
20#include "clang/Lex/Preprocessor.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/StringExtras.h"
23#include "llvm/ADT/StringSwitch.h"
24#include <list>
25#include <map>
26#include <vector>
27
28using namespace clang;
29
30namespace {
31  /// \brief A container of code-completion results.
32  class ResultBuilder {
33  public:
34    /// \brief The type of a name-lookup filter, which can be provided to the
35    /// name-lookup routines to specify which declarations should be included in
36    /// the result set (when it returns true) and which declarations should be
37    /// filtered out (returns false).
38    typedef bool (ResultBuilder::*LookupFilter)(NamedDecl *) const;
39
40    typedef CodeCompleteConsumer::Result Result;
41
42  private:
43    /// \brief The actual results we have found.
44    std::vector<Result> Results;
45
46    /// \brief A record of all of the declarations we have found and placed
47    /// into the result set, used to ensure that no declaration ever gets into
48    /// the result set twice.
49    llvm::SmallPtrSet<Decl*, 16> AllDeclsFound;
50
51    typedef std::pair<NamedDecl *, unsigned> DeclIndexPair;
52
53    /// \brief An entry in the shadow map, which is optimized to store
54    /// a single (declaration, index) mapping (the common case) but
55    /// can also store a list of (declaration, index) mappings.
56    class ShadowMapEntry {
57      typedef llvm::SmallVector<DeclIndexPair, 4> DeclIndexPairVector;
58
59      /// \brief Contains either the solitary NamedDecl * or a vector
60      /// of (declaration, index) pairs.
61      llvm::PointerUnion<NamedDecl *, DeclIndexPairVector*> DeclOrVector;
62
63      /// \brief When the entry contains a single declaration, this is
64      /// the index associated with that entry.
65      unsigned SingleDeclIndex;
66
67    public:
68      ShadowMapEntry() : DeclOrVector(), SingleDeclIndex(0) { }
69
70      void Add(NamedDecl *ND, unsigned Index) {
71        if (DeclOrVector.isNull()) {
72          // 0 - > 1 elements: just set the single element information.
73          DeclOrVector = ND;
74          SingleDeclIndex = Index;
75          return;
76        }
77
78        if (NamedDecl *PrevND = DeclOrVector.dyn_cast<NamedDecl *>()) {
79          // 1 -> 2 elements: create the vector of results and push in the
80          // existing declaration.
81          DeclIndexPairVector *Vec = new DeclIndexPairVector;
82          Vec->push_back(DeclIndexPair(PrevND, SingleDeclIndex));
83          DeclOrVector = Vec;
84        }
85
86        // Add the new element to the end of the vector.
87        DeclOrVector.get<DeclIndexPairVector*>()->push_back(
88                                                    DeclIndexPair(ND, Index));
89      }
90
91      void Destroy() {
92        if (DeclIndexPairVector *Vec
93              = DeclOrVector.dyn_cast<DeclIndexPairVector *>()) {
94          delete Vec;
95          DeclOrVector = ((NamedDecl *)0);
96        }
97      }
98
99      // Iteration.
100      class iterator;
101      iterator begin() const;
102      iterator end() const;
103    };
104
105    /// \brief A mapping from declaration names to the declarations that have
106    /// this name within a particular scope and their index within the list of
107    /// results.
108    typedef llvm::DenseMap<DeclarationName, ShadowMapEntry> ShadowMap;
109
110    /// \brief The semantic analysis object for which results are being
111    /// produced.
112    Sema &SemaRef;
113
114    /// \brief If non-NULL, a filter function used to remove any code-completion
115    /// results that are not desirable.
116    LookupFilter Filter;
117
118    /// \brief Whether we should allow declarations as
119    /// nested-name-specifiers that would otherwise be filtered out.
120    bool AllowNestedNameSpecifiers;
121
122    /// \brief If set, the type that we would prefer our resulting value
123    /// declarations to have.
124    ///
125    /// Closely matching the preferred type gives a boost to a result's
126    /// priority.
127    CanQualType PreferredType;
128
129    /// \brief A list of shadow maps, which is used to model name hiding at
130    /// different levels of, e.g., the inheritance hierarchy.
131    std::list<ShadowMap> ShadowMaps;
132
133    void AdjustResultPriorityForPreferredType(Result &R);
134
135  public:
136    explicit ResultBuilder(Sema &SemaRef, LookupFilter Filter = 0)
137      : SemaRef(SemaRef), Filter(Filter), AllowNestedNameSpecifiers(false) { }
138
139    /// \brief Whether we should include code patterns in the completion
140    /// results.
141    bool includeCodePatterns() const {
142      return SemaRef.CodeCompleter &&
143      SemaRef.CodeCompleter->includeCodePatterns();
144    }
145
146    /// \brief Set the filter used for code-completion results.
147    void setFilter(LookupFilter Filter) {
148      this->Filter = Filter;
149    }
150
151    typedef std::vector<Result>::iterator iterator;
152    iterator begin() { return Results.begin(); }
153    iterator end() { return Results.end(); }
154
155    Result *data() { return Results.empty()? 0 : &Results.front(); }
156    unsigned size() const { return Results.size(); }
157    bool empty() const { return Results.empty(); }
158
159    /// \brief Specify the preferred type.
160    void setPreferredType(QualType T) {
161      PreferredType = SemaRef.Context.getCanonicalType(T);
162    }
163
164    /// \brief Specify whether nested-name-specifiers are allowed.
165    void allowNestedNameSpecifiers(bool Allow = true) {
166      AllowNestedNameSpecifiers = Allow;
167    }
168
169    /// \brief Determine whether the given declaration is at all interesting
170    /// as a code-completion result.
171    ///
172    /// \param ND the declaration that we are inspecting.
173    ///
174    /// \param AsNestedNameSpecifier will be set true if this declaration is
175    /// only interesting when it is a nested-name-specifier.
176    bool isInterestingDecl(NamedDecl *ND, bool &AsNestedNameSpecifier) const;
177
178    /// \brief Check whether the result is hidden by the Hiding declaration.
179    ///
180    /// \returns true if the result is hidden and cannot be found, false if
181    /// the hidden result could still be found. When false, \p R may be
182    /// modified to describe how the result can be found (e.g., via extra
183    /// qualification).
184    bool CheckHiddenResult(Result &R, DeclContext *CurContext,
185                           NamedDecl *Hiding);
186
187    /// \brief Add a new result to this result set (if it isn't already in one
188    /// of the shadow maps), or replace an existing result (for, e.g., a
189    /// redeclaration).
190    ///
191    /// \param CurContext the result to add (if it is unique).
192    ///
193    /// \param R the context in which this result will be named.
194    void MaybeAddResult(Result R, DeclContext *CurContext = 0);
195
196    /// \brief Add a new result to this result set, where we already know
197    /// the hiding declation (if any).
198    ///
199    /// \param R the result to add (if it is unique).
200    ///
201    /// \param CurContext the context in which this result will be named.
202    ///
203    /// \param Hiding the declaration that hides the result.
204    ///
205    /// \param InBaseClass whether the result was found in a base
206    /// class of the searched context.
207    void AddResult(Result R, DeclContext *CurContext, NamedDecl *Hiding,
208                   bool InBaseClass);
209
210    /// \brief Add a new non-declaration result to this result set.
211    void AddResult(Result R);
212
213    /// \brief Enter into a new scope.
214    void EnterNewScope();
215
216    /// \brief Exit from the current scope.
217    void ExitScope();
218
219    /// \brief Ignore this declaration, if it is seen again.
220    void Ignore(Decl *D) { AllDeclsFound.insert(D->getCanonicalDecl()); }
221
222    /// \name Name lookup predicates
223    ///
224    /// These predicates can be passed to the name lookup functions to filter the
225    /// results of name lookup. All of the predicates have the same type, so that
226    ///
227    //@{
228    bool IsOrdinaryName(NamedDecl *ND) const;
229    bool IsOrdinaryNonTypeName(NamedDecl *ND) const;
230    bool IsIntegralConstantValue(NamedDecl *ND) const;
231    bool IsOrdinaryNonValueName(NamedDecl *ND) const;
232    bool IsNestedNameSpecifier(NamedDecl *ND) const;
233    bool IsEnum(NamedDecl *ND) const;
234    bool IsClassOrStruct(NamedDecl *ND) const;
235    bool IsUnion(NamedDecl *ND) const;
236    bool IsNamespace(NamedDecl *ND) const;
237    bool IsNamespaceOrAlias(NamedDecl *ND) const;
238    bool IsType(NamedDecl *ND) const;
239    bool IsMember(NamedDecl *ND) const;
240    bool IsObjCIvar(NamedDecl *ND) const;
241    bool IsObjCMessageReceiver(NamedDecl *ND) const;
242    //@}
243  };
244}
245
246class ResultBuilder::ShadowMapEntry::iterator {
247  llvm::PointerUnion<NamedDecl*, const DeclIndexPair*> DeclOrIterator;
248  unsigned SingleDeclIndex;
249
250public:
251  typedef DeclIndexPair value_type;
252  typedef value_type reference;
253  typedef std::ptrdiff_t difference_type;
254  typedef std::input_iterator_tag iterator_category;
255
256  class pointer {
257    DeclIndexPair Value;
258
259  public:
260    pointer(const DeclIndexPair &Value) : Value(Value) { }
261
262    const DeclIndexPair *operator->() const {
263      return &Value;
264    }
265  };
266
267  iterator() : DeclOrIterator((NamedDecl *)0), SingleDeclIndex(0) { }
268
269  iterator(NamedDecl *SingleDecl, unsigned Index)
270    : DeclOrIterator(SingleDecl), SingleDeclIndex(Index) { }
271
272  iterator(const DeclIndexPair *Iterator)
273    : DeclOrIterator(Iterator), SingleDeclIndex(0) { }
274
275  iterator &operator++() {
276    if (DeclOrIterator.is<NamedDecl *>()) {
277      DeclOrIterator = (NamedDecl *)0;
278      SingleDeclIndex = 0;
279      return *this;
280    }
281
282    const DeclIndexPair *I = DeclOrIterator.get<const DeclIndexPair*>();
283    ++I;
284    DeclOrIterator = I;
285    return *this;
286  }
287
288  iterator operator++(int) {
289    iterator tmp(*this);
290    ++(*this);
291    return tmp;
292  }
293
294  reference operator*() const {
295    if (NamedDecl *ND = DeclOrIterator.dyn_cast<NamedDecl *>())
296      return reference(ND, SingleDeclIndex);
297
298    return *DeclOrIterator.get<const DeclIndexPair*>();
299  }
300
301  pointer operator->() const {
302    return pointer(**this);
303  }
304
305  friend bool operator==(const iterator &X, const iterator &Y) {
306    return X.DeclOrIterator.getOpaqueValue()
307                                  == Y.DeclOrIterator.getOpaqueValue() &&
308      X.SingleDeclIndex == Y.SingleDeclIndex;
309  }
310
311  friend bool operator!=(const iterator &X, const iterator &Y) {
312    return !(X == Y);
313  }
314};
315
316ResultBuilder::ShadowMapEntry::iterator
317ResultBuilder::ShadowMapEntry::begin() const {
318  if (DeclOrVector.isNull())
319    return iterator();
320
321  if (NamedDecl *ND = DeclOrVector.dyn_cast<NamedDecl *>())
322    return iterator(ND, SingleDeclIndex);
323
324  return iterator(DeclOrVector.get<DeclIndexPairVector *>()->begin());
325}
326
327ResultBuilder::ShadowMapEntry::iterator
328ResultBuilder::ShadowMapEntry::end() const {
329  if (DeclOrVector.is<NamedDecl *>() || DeclOrVector.isNull())
330    return iterator();
331
332  return iterator(DeclOrVector.get<DeclIndexPairVector *>()->end());
333}
334
335/// \brief Compute the qualification required to get from the current context
336/// (\p CurContext) to the target context (\p TargetContext).
337///
338/// \param Context the AST context in which the qualification will be used.
339///
340/// \param CurContext the context where an entity is being named, which is
341/// typically based on the current scope.
342///
343/// \param TargetContext the context in which the named entity actually
344/// resides.
345///
346/// \returns a nested name specifier that refers into the target context, or
347/// NULL if no qualification is needed.
348static NestedNameSpecifier *
349getRequiredQualification(ASTContext &Context,
350                         DeclContext *CurContext,
351                         DeclContext *TargetContext) {
352  llvm::SmallVector<DeclContext *, 4> TargetParents;
353
354  for (DeclContext *CommonAncestor = TargetContext;
355       CommonAncestor && !CommonAncestor->Encloses(CurContext);
356       CommonAncestor = CommonAncestor->getLookupParent()) {
357    if (CommonAncestor->isTransparentContext() ||
358        CommonAncestor->isFunctionOrMethod())
359      continue;
360
361    TargetParents.push_back(CommonAncestor);
362  }
363
364  NestedNameSpecifier *Result = 0;
365  while (!TargetParents.empty()) {
366    DeclContext *Parent = TargetParents.back();
367    TargetParents.pop_back();
368
369    if (NamespaceDecl *Namespace = dyn_cast<NamespaceDecl>(Parent))
370      Result = NestedNameSpecifier::Create(Context, Result, Namespace);
371    else if (TagDecl *TD = dyn_cast<TagDecl>(Parent))
372      Result = NestedNameSpecifier::Create(Context, Result,
373                                           false,
374                                     Context.getTypeDeclType(TD).getTypePtr());
375  }
376  return Result;
377}
378
379bool ResultBuilder::isInterestingDecl(NamedDecl *ND,
380                                      bool &AsNestedNameSpecifier) const {
381  AsNestedNameSpecifier = false;
382
383  ND = ND->getUnderlyingDecl();
384  unsigned IDNS = ND->getIdentifierNamespace();
385
386  // Skip unnamed entities.
387  if (!ND->getDeclName())
388    return false;
389
390  // Friend declarations and declarations introduced due to friends are never
391  // added as results.
392  if (IDNS & (Decl::IDNS_OrdinaryFriend | Decl::IDNS_TagFriend))
393    return false;
394
395  // Class template (partial) specializations are never added as results.
396  if (isa<ClassTemplateSpecializationDecl>(ND) ||
397      isa<ClassTemplatePartialSpecializationDecl>(ND))
398    return false;
399
400  // Using declarations themselves are never added as results.
401  if (isa<UsingDecl>(ND))
402    return false;
403
404  // Some declarations have reserved names that we don't want to ever show.
405  if (const IdentifierInfo *Id = ND->getIdentifier()) {
406    // __va_list_tag is a freak of nature. Find it and skip it.
407    if (Id->isStr("__va_list_tag") || Id->isStr("__builtin_va_list"))
408      return false;
409
410    // Filter out names reserved for the implementation (C99 7.1.3,
411    // C++ [lib.global.names]) if they come from a system header.
412    //
413    // FIXME: Add predicate for this.
414    if (Id->getLength() >= 2) {
415      const char *Name = Id->getNameStart();
416      if (Name[0] == '_' &&
417          (Name[1] == '_' || (Name[1] >= 'A' && Name[1] <= 'Z')) &&
418          (ND->getLocation().isInvalid() ||
419           SemaRef.SourceMgr.isInSystemHeader(
420                          SemaRef.SourceMgr.getSpellingLoc(ND->getLocation()))))
421        return false;
422    }
423  }
424
425  // C++ constructors are never found by name lookup.
426  if (isa<CXXConstructorDecl>(ND))
427    return false;
428
429  if (Filter == &ResultBuilder::IsNestedNameSpecifier ||
430      ((isa<NamespaceDecl>(ND) || isa<NamespaceAliasDecl>(ND)) &&
431       Filter != &ResultBuilder::IsNamespace &&
432       Filter != &ResultBuilder::IsNamespaceOrAlias))
433    AsNestedNameSpecifier = true;
434
435  // Filter out any unwanted results.
436  if (Filter && !(this->*Filter)(ND)) {
437    // Check whether it is interesting as a nested-name-specifier.
438    if (AllowNestedNameSpecifiers && SemaRef.getLangOptions().CPlusPlus &&
439        IsNestedNameSpecifier(ND) &&
440        (Filter != &ResultBuilder::IsMember ||
441         (isa<CXXRecordDecl>(ND) &&
442          cast<CXXRecordDecl>(ND)->isInjectedClassName()))) {
443      AsNestedNameSpecifier = true;
444      return true;
445    }
446
447    return false;
448  }
449  // ... then it must be interesting!
450  return true;
451}
452
453bool ResultBuilder::CheckHiddenResult(Result &R, DeclContext *CurContext,
454                                      NamedDecl *Hiding) {
455  // In C, there is no way to refer to a hidden name.
456  // FIXME: This isn't true; we can find a tag name hidden by an ordinary
457  // name if we introduce the tag type.
458  if (!SemaRef.getLangOptions().CPlusPlus)
459    return true;
460
461  DeclContext *HiddenCtx = R.Declaration->getDeclContext()->getLookupContext();
462
463  // There is no way to qualify a name declared in a function or method.
464  if (HiddenCtx->isFunctionOrMethod())
465    return true;
466
467  if (HiddenCtx == Hiding->getDeclContext()->getLookupContext())
468    return true;
469
470  // We can refer to the result with the appropriate qualification. Do it.
471  R.Hidden = true;
472  R.QualifierIsInformative = false;
473
474  if (!R.Qualifier)
475    R.Qualifier = getRequiredQualification(SemaRef.Context,
476                                           CurContext,
477                                           R.Declaration->getDeclContext());
478  return false;
479}
480
481/// \brief A simplified classification of types used to determine whether two
482/// types are "similar enough" when adjusting priorities.
483SimplifiedTypeClass clang::getSimplifiedTypeClass(CanQualType T) {
484  switch (T->getTypeClass()) {
485  case Type::Builtin:
486    switch (cast<BuiltinType>(T)->getKind()) {
487      case BuiltinType::Void:
488        return STC_Void;
489
490      case BuiltinType::NullPtr:
491        return STC_Pointer;
492
493      case BuiltinType::Overload:
494      case BuiltinType::Dependent:
495      case BuiltinType::UndeducedAuto:
496        return STC_Other;
497
498      case BuiltinType::ObjCId:
499      case BuiltinType::ObjCClass:
500      case BuiltinType::ObjCSel:
501        return STC_ObjectiveC;
502
503      default:
504        return STC_Arithmetic;
505    }
506    return STC_Other;
507
508  case Type::Complex:
509    return STC_Arithmetic;
510
511  case Type::Pointer:
512    return STC_Pointer;
513
514  case Type::BlockPointer:
515    return STC_Block;
516
517  case Type::LValueReference:
518  case Type::RValueReference:
519    return getSimplifiedTypeClass(T->getAs<ReferenceType>()->getPointeeType());
520
521  case Type::ConstantArray:
522  case Type::IncompleteArray:
523  case Type::VariableArray:
524  case Type::DependentSizedArray:
525    return STC_Array;
526
527  case Type::DependentSizedExtVector:
528  case Type::Vector:
529  case Type::ExtVector:
530    return STC_Arithmetic;
531
532  case Type::FunctionProto:
533  case Type::FunctionNoProto:
534    return STC_Function;
535
536  case Type::Record:
537    return STC_Record;
538
539  case Type::Enum:
540    return STC_Arithmetic;
541
542  case Type::ObjCObject:
543  case Type::ObjCInterface:
544  case Type::ObjCObjectPointer:
545    return STC_ObjectiveC;
546
547  default:
548    return STC_Other;
549  }
550}
551
552/// \brief Get the type that a given expression will have if this declaration
553/// is used as an expression in its "typical" code-completion form.
554QualType clang::getDeclUsageType(ASTContext &C, NamedDecl *ND) {
555  ND = cast<NamedDecl>(ND->getUnderlyingDecl());
556
557  if (TypeDecl *Type = dyn_cast<TypeDecl>(ND))
558    return C.getTypeDeclType(Type);
559  if (ObjCInterfaceDecl *Iface = dyn_cast<ObjCInterfaceDecl>(ND))
560    return C.getObjCInterfaceType(Iface);
561
562  QualType T;
563  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(ND))
564    T = Function->getCallResultType();
565  else if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(ND))
566    T = Method->getSendResultType();
567  else if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(ND))
568    T = FunTmpl->getTemplatedDecl()->getCallResultType();
569  else if (EnumConstantDecl *Enumerator = dyn_cast<EnumConstantDecl>(ND))
570    T = C.getTypeDeclType(cast<EnumDecl>(Enumerator->getDeclContext()));
571  else if (ObjCPropertyDecl *Property = dyn_cast<ObjCPropertyDecl>(ND))
572    T = Property->getType();
573  else if (ValueDecl *Value = dyn_cast<ValueDecl>(ND))
574    T = Value->getType();
575  else
576    return QualType();
577
578  return T.getNonReferenceType();
579}
580
581void ResultBuilder::AdjustResultPriorityForPreferredType(Result &R) {
582  QualType T = getDeclUsageType(SemaRef.Context, R.Declaration);
583  if (T.isNull())
584    return;
585
586  CanQualType TC = SemaRef.Context.getCanonicalType(T);
587  // Check for exactly-matching types (modulo qualifiers).
588  if (SemaRef.Context.hasSameUnqualifiedType(PreferredType, TC))
589    R.Priority /= CCF_ExactTypeMatch;
590  // Check for nearly-matching types, based on classification of each.
591  else if ((getSimplifiedTypeClass(PreferredType)
592                                               == getSimplifiedTypeClass(TC)) &&
593           !(PreferredType->isEnumeralType() && TC->isEnumeralType()))
594    R.Priority /= CCF_SimilarTypeMatch;
595}
596
597void ResultBuilder::MaybeAddResult(Result R, DeclContext *CurContext) {
598  assert(!ShadowMaps.empty() && "Must enter into a results scope");
599
600  if (R.Kind != Result::RK_Declaration) {
601    // For non-declaration results, just add the result.
602    Results.push_back(R);
603    return;
604  }
605
606  // Look through using declarations.
607  if (UsingShadowDecl *Using = dyn_cast<UsingShadowDecl>(R.Declaration)) {
608    MaybeAddResult(Result(Using->getTargetDecl(), R.Qualifier), CurContext);
609    return;
610  }
611
612  Decl *CanonDecl = R.Declaration->getCanonicalDecl();
613  unsigned IDNS = CanonDecl->getIdentifierNamespace();
614
615  bool AsNestedNameSpecifier = false;
616  if (!isInterestingDecl(R.Declaration, AsNestedNameSpecifier))
617    return;
618
619  ShadowMap &SMap = ShadowMaps.back();
620  ShadowMapEntry::iterator I, IEnd;
621  ShadowMap::iterator NamePos = SMap.find(R.Declaration->getDeclName());
622  if (NamePos != SMap.end()) {
623    I = NamePos->second.begin();
624    IEnd = NamePos->second.end();
625  }
626
627  for (; I != IEnd; ++I) {
628    NamedDecl *ND = I->first;
629    unsigned Index = I->second;
630    if (ND->getCanonicalDecl() == CanonDecl) {
631      // This is a redeclaration. Always pick the newer declaration.
632      Results[Index].Declaration = R.Declaration;
633
634      // We're done.
635      return;
636    }
637  }
638
639  // This is a new declaration in this scope. However, check whether this
640  // declaration name is hidden by a similarly-named declaration in an outer
641  // scope.
642  std::list<ShadowMap>::iterator SM, SMEnd = ShadowMaps.end();
643  --SMEnd;
644  for (SM = ShadowMaps.begin(); SM != SMEnd; ++SM) {
645    ShadowMapEntry::iterator I, IEnd;
646    ShadowMap::iterator NamePos = SM->find(R.Declaration->getDeclName());
647    if (NamePos != SM->end()) {
648      I = NamePos->second.begin();
649      IEnd = NamePos->second.end();
650    }
651    for (; I != IEnd; ++I) {
652      // A tag declaration does not hide a non-tag declaration.
653      if (I->first->hasTagIdentifierNamespace() &&
654          (IDNS & (Decl::IDNS_Member | Decl::IDNS_Ordinary |
655                   Decl::IDNS_ObjCProtocol)))
656        continue;
657
658      // Protocols are in distinct namespaces from everything else.
659      if (((I->first->getIdentifierNamespace() & Decl::IDNS_ObjCProtocol)
660           || (IDNS & Decl::IDNS_ObjCProtocol)) &&
661          I->first->getIdentifierNamespace() != IDNS)
662        continue;
663
664      // The newly-added result is hidden by an entry in the shadow map.
665      if (CheckHiddenResult(R, CurContext, I->first))
666        return;
667
668      break;
669    }
670  }
671
672  // Make sure that any given declaration only shows up in the result set once.
673  if (!AllDeclsFound.insert(CanonDecl))
674    return;
675
676  // If the filter is for nested-name-specifiers, then this result starts a
677  // nested-name-specifier.
678  if (AsNestedNameSpecifier) {
679    R.StartsNestedNameSpecifier = true;
680    R.Priority = CCP_NestedNameSpecifier;
681  } else if (!PreferredType.isNull())
682      AdjustResultPriorityForPreferredType(R);
683
684  // If this result is supposed to have an informative qualifier, add one.
685  if (R.QualifierIsInformative && !R.Qualifier &&
686      !R.StartsNestedNameSpecifier) {
687    DeclContext *Ctx = R.Declaration->getDeclContext();
688    if (NamespaceDecl *Namespace = dyn_cast<NamespaceDecl>(Ctx))
689      R.Qualifier = NestedNameSpecifier::Create(SemaRef.Context, 0, Namespace);
690    else if (TagDecl *Tag = dyn_cast<TagDecl>(Ctx))
691      R.Qualifier = NestedNameSpecifier::Create(SemaRef.Context, 0, false,
692                             SemaRef.Context.getTypeDeclType(Tag).getTypePtr());
693    else
694      R.QualifierIsInformative = false;
695  }
696
697  // Insert this result into the set of results and into the current shadow
698  // map.
699  SMap[R.Declaration->getDeclName()].Add(R.Declaration, Results.size());
700  Results.push_back(R);
701}
702
703void ResultBuilder::AddResult(Result R, DeclContext *CurContext,
704                              NamedDecl *Hiding, bool InBaseClass = false) {
705  if (R.Kind != Result::RK_Declaration) {
706    // For non-declaration results, just add the result.
707    Results.push_back(R);
708    return;
709  }
710
711  // Look through using declarations.
712  if (UsingShadowDecl *Using = dyn_cast<UsingShadowDecl>(R.Declaration)) {
713    AddResult(Result(Using->getTargetDecl(), R.Qualifier), CurContext, Hiding);
714    return;
715  }
716
717  bool AsNestedNameSpecifier = false;
718  if (!isInterestingDecl(R.Declaration, AsNestedNameSpecifier))
719    return;
720
721  if (Hiding && CheckHiddenResult(R, CurContext, Hiding))
722    return;
723
724  // Make sure that any given declaration only shows up in the result set once.
725  if (!AllDeclsFound.insert(R.Declaration->getCanonicalDecl()))
726    return;
727
728  // If the filter is for nested-name-specifiers, then this result starts a
729  // nested-name-specifier.
730  if (AsNestedNameSpecifier) {
731    R.StartsNestedNameSpecifier = true;
732    R.Priority = CCP_NestedNameSpecifier;
733  }
734  else if (Filter == &ResultBuilder::IsMember && !R.Qualifier && InBaseClass &&
735           isa<CXXRecordDecl>(R.Declaration->getDeclContext()
736                                                  ->getLookupContext()))
737    R.QualifierIsInformative = true;
738
739  // If this result is supposed to have an informative qualifier, add one.
740  if (R.QualifierIsInformative && !R.Qualifier &&
741      !R.StartsNestedNameSpecifier) {
742    DeclContext *Ctx = R.Declaration->getDeclContext();
743    if (NamespaceDecl *Namespace = dyn_cast<NamespaceDecl>(Ctx))
744      R.Qualifier = NestedNameSpecifier::Create(SemaRef.Context, 0, Namespace);
745    else if (TagDecl *Tag = dyn_cast<TagDecl>(Ctx))
746      R.Qualifier = NestedNameSpecifier::Create(SemaRef.Context, 0, false,
747                            SemaRef.Context.getTypeDeclType(Tag).getTypePtr());
748    else
749      R.QualifierIsInformative = false;
750  }
751
752  // Adjust the priority if this result comes from a base class.
753  if (InBaseClass)
754    R.Priority += CCD_InBaseClass;
755
756  if (!PreferredType.isNull())
757    AdjustResultPriorityForPreferredType(R);
758
759  // Insert this result into the set of results.
760  Results.push_back(R);
761}
762
763void ResultBuilder::AddResult(Result R) {
764  assert(R.Kind != Result::RK_Declaration &&
765          "Declaration results need more context");
766  Results.push_back(R);
767}
768
769/// \brief Enter into a new scope.
770void ResultBuilder::EnterNewScope() {
771  ShadowMaps.push_back(ShadowMap());
772}
773
774/// \brief Exit from the current scope.
775void ResultBuilder::ExitScope() {
776  for (ShadowMap::iterator E = ShadowMaps.back().begin(),
777                        EEnd = ShadowMaps.back().end();
778       E != EEnd;
779       ++E)
780    E->second.Destroy();
781
782  ShadowMaps.pop_back();
783}
784
785/// \brief Determines whether this given declaration will be found by
786/// ordinary name lookup.
787bool ResultBuilder::IsOrdinaryName(NamedDecl *ND) const {
788  ND = cast<NamedDecl>(ND->getUnderlyingDecl());
789
790  unsigned IDNS = Decl::IDNS_Ordinary;
791  if (SemaRef.getLangOptions().CPlusPlus)
792    IDNS |= Decl::IDNS_Tag | Decl::IDNS_Namespace | Decl::IDNS_Member;
793  else if (SemaRef.getLangOptions().ObjC1 && isa<ObjCIvarDecl>(ND))
794    return true;
795
796  return ND->getIdentifierNamespace() & IDNS;
797}
798
799/// \brief Determines whether this given declaration will be found by
800/// ordinary name lookup but is not a type name.
801bool ResultBuilder::IsOrdinaryNonTypeName(NamedDecl *ND) const {
802  ND = cast<NamedDecl>(ND->getUnderlyingDecl());
803  if (isa<TypeDecl>(ND) || isa<ObjCInterfaceDecl>(ND))
804    return false;
805
806  unsigned IDNS = Decl::IDNS_Ordinary;
807  if (SemaRef.getLangOptions().CPlusPlus)
808    IDNS |= Decl::IDNS_Tag | Decl::IDNS_Namespace | Decl::IDNS_Member;
809  else if (SemaRef.getLangOptions().ObjC1 && isa<ObjCIvarDecl>(ND))
810    return true;
811
812  return ND->getIdentifierNamespace() & IDNS;
813}
814
815bool ResultBuilder::IsIntegralConstantValue(NamedDecl *ND) const {
816  if (!IsOrdinaryNonTypeName(ND))
817    return 0;
818
819  if (ValueDecl *VD = dyn_cast<ValueDecl>(ND->getUnderlyingDecl()))
820    if (VD->getType()->isIntegralOrEnumerationType())
821      return true;
822
823  return false;
824}
825
826/// \brief Determines whether this given declaration will be found by
827/// ordinary name lookup.
828bool ResultBuilder::IsOrdinaryNonValueName(NamedDecl *ND) const {
829  ND = cast<NamedDecl>(ND->getUnderlyingDecl());
830
831  unsigned IDNS = Decl::IDNS_Ordinary;
832  if (SemaRef.getLangOptions().CPlusPlus)
833    IDNS |= Decl::IDNS_Tag | Decl::IDNS_Namespace;
834
835  return (ND->getIdentifierNamespace() & IDNS) &&
836    !isa<ValueDecl>(ND) && !isa<FunctionTemplateDecl>(ND) &&
837    !isa<ObjCPropertyDecl>(ND);
838}
839
840/// \brief Determines whether the given declaration is suitable as the
841/// start of a C++ nested-name-specifier, e.g., a class or namespace.
842bool ResultBuilder::IsNestedNameSpecifier(NamedDecl *ND) const {
843  // Allow us to find class templates, too.
844  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
845    ND = ClassTemplate->getTemplatedDecl();
846
847  return SemaRef.isAcceptableNestedNameSpecifier(ND);
848}
849
850/// \brief Determines whether the given declaration is an enumeration.
851bool ResultBuilder::IsEnum(NamedDecl *ND) const {
852  return isa<EnumDecl>(ND);
853}
854
855/// \brief Determines whether the given declaration is a class or struct.
856bool ResultBuilder::IsClassOrStruct(NamedDecl *ND) const {
857  // Allow us to find class templates, too.
858  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
859    ND = ClassTemplate->getTemplatedDecl();
860
861  if (RecordDecl *RD = dyn_cast<RecordDecl>(ND))
862    return RD->getTagKind() == TTK_Class ||
863    RD->getTagKind() == TTK_Struct;
864
865  return false;
866}
867
868/// \brief Determines whether the given declaration is a union.
869bool ResultBuilder::IsUnion(NamedDecl *ND) const {
870  // Allow us to find class templates, too.
871  if (ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
872    ND = ClassTemplate->getTemplatedDecl();
873
874  if (RecordDecl *RD = dyn_cast<RecordDecl>(ND))
875    return RD->getTagKind() == TTK_Union;
876
877  return false;
878}
879
880/// \brief Determines whether the given declaration is a namespace.
881bool ResultBuilder::IsNamespace(NamedDecl *ND) const {
882  return isa<NamespaceDecl>(ND);
883}
884
885/// \brief Determines whether the given declaration is a namespace or
886/// namespace alias.
887bool ResultBuilder::IsNamespaceOrAlias(NamedDecl *ND) const {
888  return isa<NamespaceDecl>(ND) || isa<NamespaceAliasDecl>(ND);
889}
890
891/// \brief Determines whether the given declaration is a type.
892bool ResultBuilder::IsType(NamedDecl *ND) const {
893  return isa<TypeDecl>(ND);
894}
895
896/// \brief Determines which members of a class should be visible via
897/// "." or "->".  Only value declarations, nested name specifiers, and
898/// using declarations thereof should show up.
899bool ResultBuilder::IsMember(NamedDecl *ND) const {
900  if (UsingShadowDecl *Using = dyn_cast<UsingShadowDecl>(ND))
901    ND = Using->getTargetDecl();
902
903  return isa<ValueDecl>(ND) || isa<FunctionTemplateDecl>(ND) ||
904    isa<ObjCPropertyDecl>(ND);
905}
906
907static bool isObjCReceiverType(ASTContext &C, QualType T) {
908  T = C.getCanonicalType(T);
909  switch (T->getTypeClass()) {
910  case Type::ObjCObject:
911  case Type::ObjCInterface:
912  case Type::ObjCObjectPointer:
913    return true;
914
915  case Type::Builtin:
916    switch (cast<BuiltinType>(T)->getKind()) {
917    case BuiltinType::ObjCId:
918    case BuiltinType::ObjCClass:
919    case BuiltinType::ObjCSel:
920      return true;
921
922    default:
923      break;
924    }
925    return false;
926
927  default:
928    break;
929  }
930
931  if (!C.getLangOptions().CPlusPlus)
932    return false;
933
934  // FIXME: We could perform more analysis here to determine whether a
935  // particular class type has any conversions to Objective-C types. For now,
936  // just accept all class types.
937  return T->isDependentType() || T->isRecordType();
938}
939
940bool ResultBuilder::IsObjCMessageReceiver(NamedDecl *ND) const {
941  QualType T = getDeclUsageType(SemaRef.Context, ND);
942  if (T.isNull())
943    return false;
944
945  T = SemaRef.Context.getBaseElementType(T);
946  return isObjCReceiverType(SemaRef.Context, T);
947}
948
949
950/// \rief Determines whether the given declaration is an Objective-C
951/// instance variable.
952bool ResultBuilder::IsObjCIvar(NamedDecl *ND) const {
953  return isa<ObjCIvarDecl>(ND);
954}
955
956namespace {
957  /// \brief Visible declaration consumer that adds a code-completion result
958  /// for each visible declaration.
959  class CodeCompletionDeclConsumer : public VisibleDeclConsumer {
960    ResultBuilder &Results;
961    DeclContext *CurContext;
962
963  public:
964    CodeCompletionDeclConsumer(ResultBuilder &Results, DeclContext *CurContext)
965      : Results(Results), CurContext(CurContext) { }
966
967    virtual void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, bool InBaseClass) {
968      Results.AddResult(ND, CurContext, Hiding, InBaseClass);
969    }
970  };
971}
972
973/// \brief Add type specifiers for the current language as keyword results.
974static void AddTypeSpecifierResults(const LangOptions &LangOpts,
975                                    ResultBuilder &Results) {
976  typedef CodeCompleteConsumer::Result Result;
977  Results.AddResult(Result("short", CCP_Type));
978  Results.AddResult(Result("long", CCP_Type));
979  Results.AddResult(Result("signed", CCP_Type));
980  Results.AddResult(Result("unsigned", CCP_Type));
981  Results.AddResult(Result("void", CCP_Type));
982  Results.AddResult(Result("char", CCP_Type));
983  Results.AddResult(Result("int", CCP_Type));
984  Results.AddResult(Result("float", CCP_Type));
985  Results.AddResult(Result("double", CCP_Type));
986  Results.AddResult(Result("enum", CCP_Type));
987  Results.AddResult(Result("struct", CCP_Type));
988  Results.AddResult(Result("union", CCP_Type));
989  Results.AddResult(Result("const", CCP_Type));
990  Results.AddResult(Result("volatile", CCP_Type));
991
992  if (LangOpts.C99) {
993    // C99-specific
994    Results.AddResult(Result("_Complex", CCP_Type));
995    Results.AddResult(Result("_Imaginary", CCP_Type));
996    Results.AddResult(Result("_Bool", CCP_Type));
997    Results.AddResult(Result("restrict", CCP_Type));
998  }
999
1000  if (LangOpts.CPlusPlus) {
1001    // C++-specific
1002    Results.AddResult(Result("bool", CCP_Type));
1003    Results.AddResult(Result("class", CCP_Type));
1004    Results.AddResult(Result("wchar_t", CCP_Type));
1005
1006    // typename qualified-id
1007    CodeCompletionString *Pattern = new CodeCompletionString;
1008    Pattern->AddTypedTextChunk("typename");
1009    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1010    Pattern->AddPlaceholderChunk("qualifier");
1011    Pattern->AddTextChunk("::");
1012    Pattern->AddPlaceholderChunk("name");
1013    Results.AddResult(Result(Pattern));
1014
1015    if (LangOpts.CPlusPlus0x) {
1016      Results.AddResult(Result("auto", CCP_Type));
1017      Results.AddResult(Result("char16_t", CCP_Type));
1018      Results.AddResult(Result("char32_t", CCP_Type));
1019
1020      CodeCompletionString *Pattern = new CodeCompletionString;
1021      Pattern->AddTypedTextChunk("decltype");
1022      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1023      Pattern->AddPlaceholderChunk("expression");
1024      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1025      Results.AddResult(Result(Pattern));
1026    }
1027  }
1028
1029  // GNU extensions
1030  if (LangOpts.GNUMode) {
1031    // FIXME: Enable when we actually support decimal floating point.
1032    //    Results.AddResult(Result("_Decimal32"));
1033    //    Results.AddResult(Result("_Decimal64"));
1034    //    Results.AddResult(Result("_Decimal128"));
1035
1036    CodeCompletionString *Pattern = new CodeCompletionString;
1037    Pattern->AddTypedTextChunk("typeof");
1038    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1039    Pattern->AddPlaceholderChunk("expression");
1040    Results.AddResult(Result(Pattern));
1041
1042    Pattern = new CodeCompletionString;
1043    Pattern->AddTypedTextChunk("typeof");
1044    Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1045    Pattern->AddPlaceholderChunk("type");
1046    Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1047    Results.AddResult(Result(Pattern));
1048  }
1049}
1050
1051static void AddStorageSpecifiers(Action::ParserCompletionContext CCC,
1052                                 const LangOptions &LangOpts,
1053                                 ResultBuilder &Results) {
1054  typedef CodeCompleteConsumer::Result Result;
1055  // Note: we don't suggest either "auto" or "register", because both
1056  // are pointless as storage specifiers. Elsewhere, we suggest "auto"
1057  // in C++0x as a type specifier.
1058  Results.AddResult(Result("extern"));
1059  Results.AddResult(Result("static"));
1060}
1061
1062static void AddFunctionSpecifiers(Action::ParserCompletionContext CCC,
1063                                  const LangOptions &LangOpts,
1064                                  ResultBuilder &Results) {
1065  typedef CodeCompleteConsumer::Result Result;
1066  switch (CCC) {
1067  case Action::PCC_Class:
1068  case Action::PCC_MemberTemplate:
1069    if (LangOpts.CPlusPlus) {
1070      Results.AddResult(Result("explicit"));
1071      Results.AddResult(Result("friend"));
1072      Results.AddResult(Result("mutable"));
1073      Results.AddResult(Result("virtual"));
1074    }
1075    // Fall through
1076
1077  case Action::PCC_ObjCInterface:
1078  case Action::PCC_ObjCImplementation:
1079  case Action::PCC_Namespace:
1080  case Action::PCC_Template:
1081    if (LangOpts.CPlusPlus || LangOpts.C99)
1082      Results.AddResult(Result("inline"));
1083    break;
1084
1085  case Action::PCC_ObjCInstanceVariableList:
1086  case Action::PCC_Expression:
1087  case Action::PCC_Statement:
1088  case Action::PCC_ForInit:
1089  case Action::PCC_Condition:
1090  case Action::PCC_RecoveryInFunction:
1091    break;
1092  }
1093}
1094
1095static void AddObjCExpressionResults(ResultBuilder &Results, bool NeedAt);
1096static void AddObjCStatementResults(ResultBuilder &Results, bool NeedAt);
1097static void AddObjCVisibilityResults(const LangOptions &LangOpts,
1098                                     ResultBuilder &Results,
1099                                     bool NeedAt);
1100static void AddObjCImplementationResults(const LangOptions &LangOpts,
1101                                         ResultBuilder &Results,
1102                                         bool NeedAt);
1103static void AddObjCInterfaceResults(const LangOptions &LangOpts,
1104                                    ResultBuilder &Results,
1105                                    bool NeedAt);
1106static void AddObjCTopLevelResults(ResultBuilder &Results, bool NeedAt);
1107
1108static void AddTypedefResult(ResultBuilder &Results) {
1109  CodeCompletionString *Pattern = new CodeCompletionString;
1110  Pattern->AddTypedTextChunk("typedef");
1111  Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1112  Pattern->AddPlaceholderChunk("type");
1113  Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1114  Pattern->AddPlaceholderChunk("name");
1115  Results.AddResult(CodeCompleteConsumer::Result(Pattern));
1116}
1117
1118static bool WantTypesInContext(Action::ParserCompletionContext CCC,
1119                               const LangOptions &LangOpts) {
1120  if (LangOpts.CPlusPlus)
1121    return true;
1122
1123  switch (CCC) {
1124  case Action::PCC_Namespace:
1125  case Action::PCC_Class:
1126  case Action::PCC_ObjCInstanceVariableList:
1127  case Action::PCC_Template:
1128  case Action::PCC_MemberTemplate:
1129  case Action::PCC_Statement:
1130  case Action::PCC_RecoveryInFunction:
1131    return true;
1132
1133  case Action::PCC_ObjCInterface:
1134  case Action::PCC_ObjCImplementation:
1135  case Action::PCC_Expression:
1136  case Action::PCC_Condition:
1137    return false;
1138
1139  case Action::PCC_ForInit:
1140    return LangOpts.ObjC1 || LangOpts.C99;
1141  }
1142
1143  return false;
1144}
1145
1146/// \brief Add language constructs that show up for "ordinary" names.
1147static void AddOrdinaryNameResults(Action::ParserCompletionContext CCC,
1148                                   Scope *S,
1149                                   Sema &SemaRef,
1150                                   ResultBuilder &Results) {
1151  typedef CodeCompleteConsumer::Result Result;
1152  switch (CCC) {
1153  case Action::PCC_Namespace:
1154    if (SemaRef.getLangOptions().CPlusPlus) {
1155      CodeCompletionString *Pattern = 0;
1156
1157      if (Results.includeCodePatterns()) {
1158        // namespace <identifier> { declarations }
1159        CodeCompletionString *Pattern = new CodeCompletionString;
1160        Pattern->AddTypedTextChunk("namespace");
1161        Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1162        Pattern->AddPlaceholderChunk("identifier");
1163        Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1164        Pattern->AddPlaceholderChunk("declarations");
1165        Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1166        Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1167        Results.AddResult(Result(Pattern));
1168      }
1169
1170      // namespace identifier = identifier ;
1171      Pattern = new CodeCompletionString;
1172      Pattern->AddTypedTextChunk("namespace");
1173      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1174      Pattern->AddPlaceholderChunk("name");
1175      Pattern->AddChunk(CodeCompletionString::CK_Equal);
1176      Pattern->AddPlaceholderChunk("namespace");
1177      Results.AddResult(Result(Pattern));
1178
1179      // Using directives
1180      Pattern = new CodeCompletionString;
1181      Pattern->AddTypedTextChunk("using");
1182      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1183      Pattern->AddTextChunk("namespace");
1184      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1185      Pattern->AddPlaceholderChunk("identifier");
1186      Results.AddResult(Result(Pattern));
1187
1188      // asm(string-literal)
1189      Pattern = new CodeCompletionString;
1190      Pattern->AddTypedTextChunk("asm");
1191      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1192      Pattern->AddPlaceholderChunk("string-literal");
1193      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1194      Results.AddResult(Result(Pattern));
1195
1196      if (Results.includeCodePatterns()) {
1197        // Explicit template instantiation
1198        Pattern = new CodeCompletionString;
1199        Pattern->AddTypedTextChunk("template");
1200        Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1201        Pattern->AddPlaceholderChunk("declaration");
1202        Results.AddResult(Result(Pattern));
1203      }
1204    }
1205
1206    if (SemaRef.getLangOptions().ObjC1)
1207      AddObjCTopLevelResults(Results, true);
1208
1209    AddTypedefResult(Results);
1210    // Fall through
1211
1212  case Action::PCC_Class:
1213    if (SemaRef.getLangOptions().CPlusPlus) {
1214      // Using declaration
1215      CodeCompletionString *Pattern = new CodeCompletionString;
1216      Pattern->AddTypedTextChunk("using");
1217      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1218      Pattern->AddPlaceholderChunk("qualifier");
1219      Pattern->AddTextChunk("::");
1220      Pattern->AddPlaceholderChunk("name");
1221      Results.AddResult(Result(Pattern));
1222
1223      // using typename qualifier::name (only in a dependent context)
1224      if (SemaRef.CurContext->isDependentContext()) {
1225        Pattern = new CodeCompletionString;
1226        Pattern->AddTypedTextChunk("using");
1227        Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1228        Pattern->AddTextChunk("typename");
1229        Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1230        Pattern->AddPlaceholderChunk("qualifier");
1231        Pattern->AddTextChunk("::");
1232        Pattern->AddPlaceholderChunk("name");
1233        Results.AddResult(Result(Pattern));
1234      }
1235
1236      if (CCC == Action::PCC_Class) {
1237        AddTypedefResult(Results);
1238
1239        // public:
1240        Pattern = new CodeCompletionString;
1241        Pattern->AddTypedTextChunk("public");
1242        Pattern->AddChunk(CodeCompletionString::CK_Colon);
1243        Results.AddResult(Result(Pattern));
1244
1245        // protected:
1246        Pattern = new CodeCompletionString;
1247        Pattern->AddTypedTextChunk("protected");
1248        Pattern->AddChunk(CodeCompletionString::CK_Colon);
1249        Results.AddResult(Result(Pattern));
1250
1251        // private:
1252        Pattern = new CodeCompletionString;
1253        Pattern->AddTypedTextChunk("private");
1254        Pattern->AddChunk(CodeCompletionString::CK_Colon);
1255        Results.AddResult(Result(Pattern));
1256      }
1257    }
1258    // Fall through
1259
1260  case Action::PCC_Template:
1261  case Action::PCC_MemberTemplate:
1262    if (SemaRef.getLangOptions().CPlusPlus && Results.includeCodePatterns()) {
1263      // template < parameters >
1264      CodeCompletionString *Pattern = new CodeCompletionString;
1265      Pattern->AddTypedTextChunk("template");
1266      Pattern->AddChunk(CodeCompletionString::CK_LeftAngle);
1267      Pattern->AddPlaceholderChunk("parameters");
1268      Pattern->AddChunk(CodeCompletionString::CK_RightAngle);
1269      Results.AddResult(Result(Pattern));
1270    }
1271
1272    AddStorageSpecifiers(CCC, SemaRef.getLangOptions(), Results);
1273    AddFunctionSpecifiers(CCC, SemaRef.getLangOptions(), Results);
1274    break;
1275
1276  case Action::PCC_ObjCInterface:
1277    AddObjCInterfaceResults(SemaRef.getLangOptions(), Results, true);
1278    AddStorageSpecifiers(CCC, SemaRef.getLangOptions(), Results);
1279    AddFunctionSpecifiers(CCC, SemaRef.getLangOptions(), Results);
1280    break;
1281
1282  case Action::PCC_ObjCImplementation:
1283    AddObjCImplementationResults(SemaRef.getLangOptions(), Results, true);
1284    AddStorageSpecifiers(CCC, SemaRef.getLangOptions(), Results);
1285    AddFunctionSpecifiers(CCC, SemaRef.getLangOptions(), Results);
1286    break;
1287
1288  case Action::PCC_ObjCInstanceVariableList:
1289    AddObjCVisibilityResults(SemaRef.getLangOptions(), Results, true);
1290    break;
1291
1292  case Action::PCC_RecoveryInFunction:
1293  case Action::PCC_Statement: {
1294    AddTypedefResult(Results);
1295
1296    CodeCompletionString *Pattern = 0;
1297    if (SemaRef.getLangOptions().CPlusPlus && Results.includeCodePatterns()) {
1298      Pattern = new CodeCompletionString;
1299      Pattern->AddTypedTextChunk("try");
1300      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1301      Pattern->AddPlaceholderChunk("statements");
1302      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1303      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1304      Pattern->AddTextChunk("catch");
1305      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1306      Pattern->AddPlaceholderChunk("declaration");
1307      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1308      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1309      Pattern->AddPlaceholderChunk("statements");
1310      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1311      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1312      Results.AddResult(Result(Pattern));
1313    }
1314    if (SemaRef.getLangOptions().ObjC1)
1315      AddObjCStatementResults(Results, true);
1316
1317    if (Results.includeCodePatterns()) {
1318      // if (condition) { statements }
1319      Pattern = new CodeCompletionString;
1320      Pattern->AddTypedTextChunk("if");
1321      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1322      if (SemaRef.getLangOptions().CPlusPlus)
1323        Pattern->AddPlaceholderChunk("condition");
1324      else
1325        Pattern->AddPlaceholderChunk("expression");
1326      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1327      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1328      Pattern->AddPlaceholderChunk("statements");
1329      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1330      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1331      Results.AddResult(Result(Pattern));
1332
1333      // switch (condition) { }
1334      Pattern = new CodeCompletionString;
1335      Pattern->AddTypedTextChunk("switch");
1336      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1337      if (SemaRef.getLangOptions().CPlusPlus)
1338        Pattern->AddPlaceholderChunk("condition");
1339      else
1340        Pattern->AddPlaceholderChunk("expression");
1341      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1342      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1343      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1344      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1345      Results.AddResult(Result(Pattern));
1346    }
1347
1348    // Switch-specific statements.
1349    if (!SemaRef.getSwitchStack().empty()) {
1350      // case expression:
1351      Pattern = new CodeCompletionString;
1352      Pattern->AddTypedTextChunk("case");
1353      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1354      Pattern->AddPlaceholderChunk("expression");
1355      Pattern->AddChunk(CodeCompletionString::CK_Colon);
1356      Results.AddResult(Result(Pattern));
1357
1358      // default:
1359      Pattern = new CodeCompletionString;
1360      Pattern->AddTypedTextChunk("default");
1361      Pattern->AddChunk(CodeCompletionString::CK_Colon);
1362      Results.AddResult(Result(Pattern));
1363    }
1364
1365    if (Results.includeCodePatterns()) {
1366      /// while (condition) { statements }
1367      Pattern = new CodeCompletionString;
1368      Pattern->AddTypedTextChunk("while");
1369      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1370      if (SemaRef.getLangOptions().CPlusPlus)
1371        Pattern->AddPlaceholderChunk("condition");
1372      else
1373        Pattern->AddPlaceholderChunk("expression");
1374      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1375      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1376      Pattern->AddPlaceholderChunk("statements");
1377      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1378      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1379      Results.AddResult(Result(Pattern));
1380
1381      // do { statements } while ( expression );
1382      Pattern = new CodeCompletionString;
1383      Pattern->AddTypedTextChunk("do");
1384      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1385      Pattern->AddPlaceholderChunk("statements");
1386      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1387      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1388      Pattern->AddTextChunk("while");
1389      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1390      Pattern->AddPlaceholderChunk("expression");
1391      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1392      Results.AddResult(Result(Pattern));
1393
1394      // for ( for-init-statement ; condition ; expression ) { statements }
1395      Pattern = new CodeCompletionString;
1396      Pattern->AddTypedTextChunk("for");
1397      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1398      if (SemaRef.getLangOptions().CPlusPlus || SemaRef.getLangOptions().C99)
1399        Pattern->AddPlaceholderChunk("init-statement");
1400      else
1401        Pattern->AddPlaceholderChunk("init-expression");
1402      Pattern->AddChunk(CodeCompletionString::CK_SemiColon);
1403      Pattern->AddPlaceholderChunk("condition");
1404      Pattern->AddChunk(CodeCompletionString::CK_SemiColon);
1405      Pattern->AddPlaceholderChunk("inc-expression");
1406      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1407      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
1408      Pattern->AddPlaceholderChunk("statements");
1409      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
1410      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
1411      Results.AddResult(Result(Pattern));
1412    }
1413
1414    if (S->getContinueParent()) {
1415      // continue ;
1416      Pattern = new CodeCompletionString;
1417      Pattern->AddTypedTextChunk("continue");
1418      Results.AddResult(Result(Pattern));
1419    }
1420
1421    if (S->getBreakParent()) {
1422      // break ;
1423      Pattern = new CodeCompletionString;
1424      Pattern->AddTypedTextChunk("break");
1425      Results.AddResult(Result(Pattern));
1426    }
1427
1428    // "return expression ;" or "return ;", depending on whether we
1429    // know the function is void or not.
1430    bool isVoid = false;
1431    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(SemaRef.CurContext))
1432      isVoid = Function->getResultType()->isVoidType();
1433    else if (ObjCMethodDecl *Method
1434                                 = dyn_cast<ObjCMethodDecl>(SemaRef.CurContext))
1435      isVoid = Method->getResultType()->isVoidType();
1436    else if (SemaRef.getCurBlock() &&
1437             !SemaRef.getCurBlock()->ReturnType.isNull())
1438      isVoid = SemaRef.getCurBlock()->ReturnType->isVoidType();
1439    Pattern = new CodeCompletionString;
1440    Pattern->AddTypedTextChunk("return");
1441    if (!isVoid) {
1442      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1443      Pattern->AddPlaceholderChunk("expression");
1444    }
1445    Results.AddResult(Result(Pattern));
1446
1447    // goto identifier ;
1448    Pattern = new CodeCompletionString;
1449    Pattern->AddTypedTextChunk("goto");
1450    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1451    Pattern->AddPlaceholderChunk("label");
1452    Results.AddResult(Result(Pattern));
1453
1454    // Using directives
1455    Pattern = new CodeCompletionString;
1456    Pattern->AddTypedTextChunk("using");
1457    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1458    Pattern->AddTextChunk("namespace");
1459    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1460    Pattern->AddPlaceholderChunk("identifier");
1461    Results.AddResult(Result(Pattern));
1462  }
1463
1464  // Fall through (for statement expressions).
1465  case Action::PCC_ForInit:
1466  case Action::PCC_Condition:
1467    AddStorageSpecifiers(CCC, SemaRef.getLangOptions(), Results);
1468    // Fall through: conditions and statements can have expressions.
1469
1470  case Action::PCC_Expression: {
1471    CodeCompletionString *Pattern = 0;
1472    if (SemaRef.getLangOptions().CPlusPlus) {
1473      // 'this', if we're in a non-static member function.
1474      if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(SemaRef.CurContext))
1475        if (!Method->isStatic())
1476          Results.AddResult(Result("this"));
1477
1478      // true, false
1479      Results.AddResult(Result("true"));
1480      Results.AddResult(Result("false"));
1481
1482      // dynamic_cast < type-id > ( expression )
1483      Pattern = new CodeCompletionString;
1484      Pattern->AddTypedTextChunk("dynamic_cast");
1485      Pattern->AddChunk(CodeCompletionString::CK_LeftAngle);
1486      Pattern->AddPlaceholderChunk("type");
1487      Pattern->AddChunk(CodeCompletionString::CK_RightAngle);
1488      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1489      Pattern->AddPlaceholderChunk("expression");
1490      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1491      Results.AddResult(Result(Pattern));
1492
1493      // static_cast < type-id > ( expression )
1494      Pattern = new CodeCompletionString;
1495      Pattern->AddTypedTextChunk("static_cast");
1496      Pattern->AddChunk(CodeCompletionString::CK_LeftAngle);
1497      Pattern->AddPlaceholderChunk("type");
1498      Pattern->AddChunk(CodeCompletionString::CK_RightAngle);
1499      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1500      Pattern->AddPlaceholderChunk("expression");
1501      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1502      Results.AddResult(Result(Pattern));
1503
1504      // reinterpret_cast < type-id > ( expression )
1505      Pattern = new CodeCompletionString;
1506      Pattern->AddTypedTextChunk("reinterpret_cast");
1507      Pattern->AddChunk(CodeCompletionString::CK_LeftAngle);
1508      Pattern->AddPlaceholderChunk("type");
1509      Pattern->AddChunk(CodeCompletionString::CK_RightAngle);
1510      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1511      Pattern->AddPlaceholderChunk("expression");
1512      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1513      Results.AddResult(Result(Pattern));
1514
1515      // const_cast < type-id > ( expression )
1516      Pattern = new CodeCompletionString;
1517      Pattern->AddTypedTextChunk("const_cast");
1518      Pattern->AddChunk(CodeCompletionString::CK_LeftAngle);
1519      Pattern->AddPlaceholderChunk("type");
1520      Pattern->AddChunk(CodeCompletionString::CK_RightAngle);
1521      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1522      Pattern->AddPlaceholderChunk("expression");
1523      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1524      Results.AddResult(Result(Pattern));
1525
1526      // typeid ( expression-or-type )
1527      Pattern = new CodeCompletionString;
1528      Pattern->AddTypedTextChunk("typeid");
1529      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1530      Pattern->AddPlaceholderChunk("expression-or-type");
1531      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1532      Results.AddResult(Result(Pattern));
1533
1534      // new T ( ... )
1535      Pattern = new CodeCompletionString;
1536      Pattern->AddTypedTextChunk("new");
1537      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1538      Pattern->AddPlaceholderChunk("type");
1539      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1540      Pattern->AddPlaceholderChunk("expressions");
1541      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1542      Results.AddResult(Result(Pattern));
1543
1544      // new T [ ] ( ... )
1545      Pattern = new CodeCompletionString;
1546      Pattern->AddTypedTextChunk("new");
1547      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1548      Pattern->AddPlaceholderChunk("type");
1549      Pattern->AddChunk(CodeCompletionString::CK_LeftBracket);
1550      Pattern->AddPlaceholderChunk("size");
1551      Pattern->AddChunk(CodeCompletionString::CK_RightBracket);
1552      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1553      Pattern->AddPlaceholderChunk("expressions");
1554      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1555      Results.AddResult(Result(Pattern));
1556
1557      // delete expression
1558      Pattern = new CodeCompletionString;
1559      Pattern->AddTypedTextChunk("delete");
1560      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1561      Pattern->AddPlaceholderChunk("expression");
1562      Results.AddResult(Result(Pattern));
1563
1564      // delete [] expression
1565      Pattern = new CodeCompletionString;
1566      Pattern->AddTypedTextChunk("delete");
1567      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1568      Pattern->AddChunk(CodeCompletionString::CK_LeftBracket);
1569      Pattern->AddChunk(CodeCompletionString::CK_RightBracket);
1570      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1571      Pattern->AddPlaceholderChunk("expression");
1572      Results.AddResult(Result(Pattern));
1573
1574      // throw expression
1575      Pattern = new CodeCompletionString;
1576      Pattern->AddTypedTextChunk("throw");
1577      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1578      Pattern->AddPlaceholderChunk("expression");
1579      Results.AddResult(Result(Pattern));
1580
1581      // FIXME: Rethrow?
1582    }
1583
1584    if (SemaRef.getLangOptions().ObjC1) {
1585      // Add "super", if we're in an Objective-C class with a superclass.
1586      if (ObjCMethodDecl *Method = SemaRef.getCurMethodDecl()) {
1587        // The interface can be NULL.
1588        if (ObjCInterfaceDecl *ID = Method->getClassInterface())
1589          if (ID->getSuperClass())
1590            Results.AddResult(Result("super"));
1591      }
1592
1593      AddObjCExpressionResults(Results, true);
1594    }
1595
1596    // sizeof expression
1597    Pattern = new CodeCompletionString;
1598    Pattern->AddTypedTextChunk("sizeof");
1599    Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
1600    Pattern->AddPlaceholderChunk("expression-or-type");
1601    Pattern->AddChunk(CodeCompletionString::CK_RightParen);
1602    Results.AddResult(Result(Pattern));
1603    break;
1604  }
1605  }
1606
1607  if (WantTypesInContext(CCC, SemaRef.getLangOptions()))
1608    AddTypeSpecifierResults(SemaRef.getLangOptions(), Results);
1609
1610  if (SemaRef.getLangOptions().CPlusPlus)
1611    Results.AddResult(Result("operator"));
1612}
1613
1614/// \brief If the given declaration has an associated type, add it as a result
1615/// type chunk.
1616static void AddResultTypeChunk(ASTContext &Context,
1617                               NamedDecl *ND,
1618                               CodeCompletionString *Result) {
1619  if (!ND)
1620    return;
1621
1622  // Determine the type of the declaration (if it has a type).
1623  QualType T;
1624  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(ND))
1625    T = Function->getResultType();
1626  else if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(ND))
1627    T = Method->getResultType();
1628  else if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(ND))
1629    T = FunTmpl->getTemplatedDecl()->getResultType();
1630  else if (EnumConstantDecl *Enumerator = dyn_cast<EnumConstantDecl>(ND))
1631    T = Context.getTypeDeclType(cast<TypeDecl>(Enumerator->getDeclContext()));
1632  else if (isa<UnresolvedUsingValueDecl>(ND)) {
1633    /* Do nothing: ignore unresolved using declarations*/
1634  } else if (ValueDecl *Value = dyn_cast<ValueDecl>(ND))
1635    T = Value->getType();
1636  else if (ObjCPropertyDecl *Property = dyn_cast<ObjCPropertyDecl>(ND))
1637    T = Property->getType();
1638
1639  if (T.isNull() || Context.hasSameType(T, Context.DependentTy))
1640    return;
1641
1642  PrintingPolicy Policy(Context.PrintingPolicy);
1643  Policy.AnonymousTagLocations = false;
1644
1645  std::string TypeStr;
1646  T.getAsStringInternal(TypeStr, Policy);
1647  Result->AddResultTypeChunk(TypeStr);
1648}
1649
1650/// \brief Add function parameter chunks to the given code completion string.
1651static void AddFunctionParameterChunks(ASTContext &Context,
1652                                       FunctionDecl *Function,
1653                                       CodeCompletionString *Result) {
1654  typedef CodeCompletionString::Chunk Chunk;
1655
1656  CodeCompletionString *CCStr = Result;
1657
1658  for (unsigned P = 0, N = Function->getNumParams(); P != N; ++P) {
1659    ParmVarDecl *Param = Function->getParamDecl(P);
1660
1661    if (Param->hasDefaultArg()) {
1662      // When we see an optional default argument, put that argument and
1663      // the remaining default arguments into a new, optional string.
1664      CodeCompletionString *Opt = new CodeCompletionString;
1665      CCStr->AddOptionalChunk(std::auto_ptr<CodeCompletionString>(Opt));
1666      CCStr = Opt;
1667    }
1668
1669    if (P != 0)
1670      CCStr->AddChunk(Chunk(CodeCompletionString::CK_Comma));
1671
1672    // Format the placeholder string.
1673    std::string PlaceholderStr;
1674    if (Param->getIdentifier())
1675      PlaceholderStr = Param->getIdentifier()->getName();
1676
1677    Param->getType().getAsStringInternal(PlaceholderStr,
1678                                         Context.PrintingPolicy);
1679
1680    // Add the placeholder string.
1681    CCStr->AddPlaceholderChunk(PlaceholderStr);
1682  }
1683
1684  if (const FunctionProtoType *Proto
1685        = Function->getType()->getAs<FunctionProtoType>())
1686    if (Proto->isVariadic())
1687      CCStr->AddPlaceholderChunk(", ...");
1688}
1689
1690/// \brief Add template parameter chunks to the given code completion string.
1691static void AddTemplateParameterChunks(ASTContext &Context,
1692                                       TemplateDecl *Template,
1693                                       CodeCompletionString *Result,
1694                                       unsigned MaxParameters = 0) {
1695  typedef CodeCompletionString::Chunk Chunk;
1696
1697  CodeCompletionString *CCStr = Result;
1698  bool FirstParameter = true;
1699
1700  TemplateParameterList *Params = Template->getTemplateParameters();
1701  TemplateParameterList::iterator PEnd = Params->end();
1702  if (MaxParameters)
1703    PEnd = Params->begin() + MaxParameters;
1704  for (TemplateParameterList::iterator P = Params->begin(); P != PEnd; ++P) {
1705    bool HasDefaultArg = false;
1706    std::string PlaceholderStr;
1707    if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*P)) {
1708      if (TTP->wasDeclaredWithTypename())
1709        PlaceholderStr = "typename";
1710      else
1711        PlaceholderStr = "class";
1712
1713      if (TTP->getIdentifier()) {
1714        PlaceholderStr += ' ';
1715        PlaceholderStr += TTP->getIdentifier()->getName();
1716      }
1717
1718      HasDefaultArg = TTP->hasDefaultArgument();
1719    } else if (NonTypeTemplateParmDecl *NTTP
1720               = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
1721      if (NTTP->getIdentifier())
1722        PlaceholderStr = NTTP->getIdentifier()->getName();
1723      NTTP->getType().getAsStringInternal(PlaceholderStr,
1724                                          Context.PrintingPolicy);
1725      HasDefaultArg = NTTP->hasDefaultArgument();
1726    } else {
1727      assert(isa<TemplateTemplateParmDecl>(*P));
1728      TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
1729
1730      // Since putting the template argument list into the placeholder would
1731      // be very, very long, we just use an abbreviation.
1732      PlaceholderStr = "template<...> class";
1733      if (TTP->getIdentifier()) {
1734        PlaceholderStr += ' ';
1735        PlaceholderStr += TTP->getIdentifier()->getName();
1736      }
1737
1738      HasDefaultArg = TTP->hasDefaultArgument();
1739    }
1740
1741    if (HasDefaultArg) {
1742      // When we see an optional default argument, put that argument and
1743      // the remaining default arguments into a new, optional string.
1744      CodeCompletionString *Opt = new CodeCompletionString;
1745      CCStr->AddOptionalChunk(std::auto_ptr<CodeCompletionString>(Opt));
1746      CCStr = Opt;
1747    }
1748
1749    if (FirstParameter)
1750      FirstParameter = false;
1751    else
1752      CCStr->AddChunk(Chunk(CodeCompletionString::CK_Comma));
1753
1754    // Add the placeholder string.
1755    CCStr->AddPlaceholderChunk(PlaceholderStr);
1756  }
1757}
1758
1759/// \brief Add a qualifier to the given code-completion string, if the
1760/// provided nested-name-specifier is non-NULL.
1761static void
1762AddQualifierToCompletionString(CodeCompletionString *Result,
1763                               NestedNameSpecifier *Qualifier,
1764                               bool QualifierIsInformative,
1765                               ASTContext &Context) {
1766  if (!Qualifier)
1767    return;
1768
1769  std::string PrintedNNS;
1770  {
1771    llvm::raw_string_ostream OS(PrintedNNS);
1772    Qualifier->print(OS, Context.PrintingPolicy);
1773  }
1774  if (QualifierIsInformative)
1775    Result->AddInformativeChunk(PrintedNNS);
1776  else
1777    Result->AddTextChunk(PrintedNNS);
1778}
1779
1780static void AddFunctionTypeQualsToCompletionString(CodeCompletionString *Result,
1781                                                   FunctionDecl *Function) {
1782  const FunctionProtoType *Proto
1783    = Function->getType()->getAs<FunctionProtoType>();
1784  if (!Proto || !Proto->getTypeQuals())
1785    return;
1786
1787  std::string QualsStr;
1788  if (Proto->getTypeQuals() & Qualifiers::Const)
1789    QualsStr += " const";
1790  if (Proto->getTypeQuals() & Qualifiers::Volatile)
1791    QualsStr += " volatile";
1792  if (Proto->getTypeQuals() & Qualifiers::Restrict)
1793    QualsStr += " restrict";
1794  Result->AddInformativeChunk(QualsStr);
1795}
1796
1797/// \brief If possible, create a new code completion string for the given
1798/// result.
1799///
1800/// \returns Either a new, heap-allocated code completion string describing
1801/// how to use this result, or NULL to indicate that the string or name of the
1802/// result is all that is needed.
1803CodeCompletionString *
1804CodeCompleteConsumer::Result::CreateCodeCompletionString(Sema &S,
1805                                               CodeCompletionString *Result) {
1806  typedef CodeCompletionString::Chunk Chunk;
1807
1808  if (Kind == RK_Pattern)
1809    return Pattern->Clone(Result);
1810
1811  if (!Result)
1812    Result = new CodeCompletionString;
1813
1814  if (Kind == RK_Keyword) {
1815    Result->AddTypedTextChunk(Keyword);
1816    return Result;
1817  }
1818
1819  if (Kind == RK_Macro) {
1820    MacroInfo *MI = S.PP.getMacroInfo(Macro);
1821    assert(MI && "Not a macro?");
1822
1823    Result->AddTypedTextChunk(Macro->getName());
1824
1825    if (!MI->isFunctionLike())
1826      return Result;
1827
1828    // Format a function-like macro with placeholders for the arguments.
1829    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
1830    for (MacroInfo::arg_iterator A = MI->arg_begin(), AEnd = MI->arg_end();
1831         A != AEnd; ++A) {
1832      if (A != MI->arg_begin())
1833        Result->AddChunk(Chunk(CodeCompletionString::CK_Comma));
1834
1835      if (!MI->isVariadic() || A != AEnd - 1) {
1836        // Non-variadic argument.
1837        Result->AddPlaceholderChunk((*A)->getName());
1838        continue;
1839      }
1840
1841      // Variadic argument; cope with the different between GNU and C99
1842      // variadic macros, providing a single placeholder for the rest of the
1843      // arguments.
1844      if ((*A)->isStr("__VA_ARGS__"))
1845        Result->AddPlaceholderChunk("...");
1846      else {
1847        std::string Arg = (*A)->getName();
1848        Arg += "...";
1849        Result->AddPlaceholderChunk(Arg);
1850      }
1851    }
1852    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
1853    return Result;
1854  }
1855
1856  assert(Kind == RK_Declaration && "Missed a result kind?");
1857  NamedDecl *ND = Declaration;
1858
1859  if (StartsNestedNameSpecifier) {
1860    Result->AddTypedTextChunk(ND->getNameAsString());
1861    Result->AddTextChunk("::");
1862    return Result;
1863  }
1864
1865  AddResultTypeChunk(S.Context, ND, Result);
1866
1867  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(ND)) {
1868    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
1869                                   S.Context);
1870    Result->AddTypedTextChunk(Function->getNameAsString());
1871    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
1872    AddFunctionParameterChunks(S.Context, Function, Result);
1873    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
1874    AddFunctionTypeQualsToCompletionString(Result, Function);
1875    return Result;
1876  }
1877
1878  if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(ND)) {
1879    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
1880                                   S.Context);
1881    FunctionDecl *Function = FunTmpl->getTemplatedDecl();
1882    Result->AddTypedTextChunk(Function->getNameAsString());
1883
1884    // Figure out which template parameters are deduced (or have default
1885    // arguments).
1886    llvm::SmallVector<bool, 16> Deduced;
1887    S.MarkDeducedTemplateParameters(FunTmpl, Deduced);
1888    unsigned LastDeducibleArgument;
1889    for (LastDeducibleArgument = Deduced.size(); LastDeducibleArgument > 0;
1890         --LastDeducibleArgument) {
1891      if (!Deduced[LastDeducibleArgument - 1]) {
1892        // C++0x: Figure out if the template argument has a default. If so,
1893        // the user doesn't need to type this argument.
1894        // FIXME: We need to abstract template parameters better!
1895        bool HasDefaultArg = false;
1896        NamedDecl *Param = FunTmpl->getTemplateParameters()->getParam(
1897                                                                      LastDeducibleArgument - 1);
1898        if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
1899          HasDefaultArg = TTP->hasDefaultArgument();
1900        else if (NonTypeTemplateParmDecl *NTTP
1901                 = dyn_cast<NonTypeTemplateParmDecl>(Param))
1902          HasDefaultArg = NTTP->hasDefaultArgument();
1903        else {
1904          assert(isa<TemplateTemplateParmDecl>(Param));
1905          HasDefaultArg
1906            = cast<TemplateTemplateParmDecl>(Param)->hasDefaultArgument();
1907        }
1908
1909        if (!HasDefaultArg)
1910          break;
1911      }
1912    }
1913
1914    if (LastDeducibleArgument) {
1915      // Some of the function template arguments cannot be deduced from a
1916      // function call, so we introduce an explicit template argument list
1917      // containing all of the arguments up to the first deducible argument.
1918      Result->AddChunk(Chunk(CodeCompletionString::CK_LeftAngle));
1919      AddTemplateParameterChunks(S.Context, FunTmpl, Result,
1920                                 LastDeducibleArgument);
1921      Result->AddChunk(Chunk(CodeCompletionString::CK_RightAngle));
1922    }
1923
1924    // Add the function parameters
1925    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
1926    AddFunctionParameterChunks(S.Context, Function, Result);
1927    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
1928    AddFunctionTypeQualsToCompletionString(Result, Function);
1929    return Result;
1930  }
1931
1932  if (TemplateDecl *Template = dyn_cast<TemplateDecl>(ND)) {
1933    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
1934                                   S.Context);
1935    Result->AddTypedTextChunk(Template->getNameAsString());
1936    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftAngle));
1937    AddTemplateParameterChunks(S.Context, Template, Result);
1938    Result->AddChunk(Chunk(CodeCompletionString::CK_RightAngle));
1939    return Result;
1940  }
1941
1942  if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(ND)) {
1943    Selector Sel = Method->getSelector();
1944    if (Sel.isUnarySelector()) {
1945      Result->AddTypedTextChunk(Sel.getIdentifierInfoForSlot(0)->getName());
1946      return Result;
1947    }
1948
1949    std::string SelName = Sel.getIdentifierInfoForSlot(0)->getName().str();
1950    SelName += ':';
1951    if (StartParameter == 0)
1952      Result->AddTypedTextChunk(SelName);
1953    else {
1954      Result->AddInformativeChunk(SelName);
1955
1956      // If there is only one parameter, and we're past it, add an empty
1957      // typed-text chunk since there is nothing to type.
1958      if (Method->param_size() == 1)
1959        Result->AddTypedTextChunk("");
1960    }
1961    unsigned Idx = 0;
1962    for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
1963                                     PEnd = Method->param_end();
1964         P != PEnd; (void)++P, ++Idx) {
1965      if (Idx > 0) {
1966        std::string Keyword;
1967        if (Idx > StartParameter)
1968          Result->AddChunk(CodeCompletionString::CK_HorizontalSpace);
1969        if (IdentifierInfo *II = Sel.getIdentifierInfoForSlot(Idx))
1970          Keyword += II->getName().str();
1971        Keyword += ":";
1972        if (Idx < StartParameter || AllParametersAreInformative)
1973          Result->AddInformativeChunk(Keyword);
1974        else if (Idx == StartParameter)
1975          Result->AddTypedTextChunk(Keyword);
1976        else
1977          Result->AddTextChunk(Keyword);
1978      }
1979
1980      // If we're before the starting parameter, skip the placeholder.
1981      if (Idx < StartParameter)
1982        continue;
1983
1984      std::string Arg;
1985      (*P)->getType().getAsStringInternal(Arg, S.Context.PrintingPolicy);
1986      Arg = "(" + Arg + ")";
1987      if (IdentifierInfo *II = (*P)->getIdentifier())
1988        Arg += II->getName().str();
1989      if (DeclaringEntity)
1990        Result->AddTextChunk(Arg);
1991      else if (AllParametersAreInformative)
1992        Result->AddInformativeChunk(Arg);
1993      else
1994        Result->AddPlaceholderChunk(Arg);
1995    }
1996
1997    if (Method->isVariadic()) {
1998      if (DeclaringEntity)
1999        Result->AddTextChunk(", ...");
2000      else if (AllParametersAreInformative)
2001        Result->AddInformativeChunk(", ...");
2002      else
2003        Result->AddPlaceholderChunk(", ...");
2004    }
2005
2006    return Result;
2007  }
2008
2009  if (Qualifier)
2010    AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
2011                                   S.Context);
2012
2013  Result->AddTypedTextChunk(ND->getNameAsString());
2014  return Result;
2015}
2016
2017CodeCompletionString *
2018CodeCompleteConsumer::OverloadCandidate::CreateSignatureString(
2019                                                          unsigned CurrentArg,
2020                                                               Sema &S) const {
2021  typedef CodeCompletionString::Chunk Chunk;
2022
2023  CodeCompletionString *Result = new CodeCompletionString;
2024  FunctionDecl *FDecl = getFunction();
2025  AddResultTypeChunk(S.Context, FDecl, Result);
2026  const FunctionProtoType *Proto
2027    = dyn_cast<FunctionProtoType>(getFunctionType());
2028  if (!FDecl && !Proto) {
2029    // Function without a prototype. Just give the return type and a
2030    // highlighted ellipsis.
2031    const FunctionType *FT = getFunctionType();
2032    Result->AddTextChunk(
2033            FT->getResultType().getAsString(S.Context.PrintingPolicy));
2034    Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
2035    Result->AddChunk(Chunk(CodeCompletionString::CK_CurrentParameter, "..."));
2036    Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
2037    return Result;
2038  }
2039
2040  if (FDecl)
2041    Result->AddTextChunk(FDecl->getNameAsString());
2042  else
2043    Result->AddTextChunk(
2044         Proto->getResultType().getAsString(S.Context.PrintingPolicy));
2045
2046  Result->AddChunk(Chunk(CodeCompletionString::CK_LeftParen));
2047  unsigned NumParams = FDecl? FDecl->getNumParams() : Proto->getNumArgs();
2048  for (unsigned I = 0; I != NumParams; ++I) {
2049    if (I)
2050      Result->AddChunk(Chunk(CodeCompletionString::CK_Comma));
2051
2052    std::string ArgString;
2053    QualType ArgType;
2054
2055    if (FDecl) {
2056      ArgString = FDecl->getParamDecl(I)->getNameAsString();
2057      ArgType = FDecl->getParamDecl(I)->getOriginalType();
2058    } else {
2059      ArgType = Proto->getArgType(I);
2060    }
2061
2062    ArgType.getAsStringInternal(ArgString, S.Context.PrintingPolicy);
2063
2064    if (I == CurrentArg)
2065      Result->AddChunk(Chunk(CodeCompletionString::CK_CurrentParameter,
2066                             ArgString));
2067    else
2068      Result->AddTextChunk(ArgString);
2069  }
2070
2071  if (Proto && Proto->isVariadic()) {
2072    Result->AddChunk(Chunk(CodeCompletionString::CK_Comma));
2073    if (CurrentArg < NumParams)
2074      Result->AddTextChunk("...");
2075    else
2076      Result->AddChunk(Chunk(CodeCompletionString::CK_CurrentParameter, "..."));
2077  }
2078  Result->AddChunk(Chunk(CodeCompletionString::CK_RightParen));
2079
2080  return Result;
2081}
2082
2083namespace {
2084  struct SortCodeCompleteResult {
2085    typedef CodeCompleteConsumer::Result Result;
2086
2087    bool isEarlierDeclarationName(DeclarationName X, DeclarationName Y) const {
2088      Selector XSel = X.getObjCSelector();
2089      Selector YSel = Y.getObjCSelector();
2090      if (!XSel.isNull() && !YSel.isNull()) {
2091        // We are comparing two selectors.
2092        unsigned N = std::min(XSel.getNumArgs(), YSel.getNumArgs());
2093        if (N == 0)
2094          ++N;
2095        for (unsigned I = 0; I != N; ++I) {
2096          IdentifierInfo *XId = XSel.getIdentifierInfoForSlot(I);
2097          IdentifierInfo *YId = YSel.getIdentifierInfoForSlot(I);
2098          if (!XId || !YId)
2099            return XId && !YId;
2100
2101          switch (XId->getName().compare_lower(YId->getName())) {
2102          case -1: return true;
2103          case 1: return false;
2104          default: break;
2105          }
2106        }
2107
2108        return XSel.getNumArgs() < YSel.getNumArgs();
2109      }
2110
2111      // For non-selectors, order by kind.
2112      if (X.getNameKind() != Y.getNameKind())
2113        return X.getNameKind() < Y.getNameKind();
2114
2115      // Order identifiers by comparison of their lowercased names.
2116      if (IdentifierInfo *XId = X.getAsIdentifierInfo())
2117        return XId->getName().compare_lower(
2118                                     Y.getAsIdentifierInfo()->getName()) < 0;
2119
2120      // Order overloaded operators by the order in which they appear
2121      // in our list of operators.
2122      if (OverloadedOperatorKind XOp = X.getCXXOverloadedOperator())
2123        return XOp < Y.getCXXOverloadedOperator();
2124
2125      // Order C++0x user-defined literal operators lexically by their
2126      // lowercased suffixes.
2127      if (IdentifierInfo *XLit = X.getCXXLiteralIdentifier())
2128        return XLit->getName().compare_lower(
2129                                  Y.getCXXLiteralIdentifier()->getName()) < 0;
2130
2131      // The only stable ordering we have is to turn the name into a
2132      // string and then compare the lower-case strings. This is
2133      // inefficient, but thankfully does not happen too often.
2134      return llvm::StringRef(X.getAsString()).compare_lower(
2135                                                 Y.getAsString()) < 0;
2136    }
2137
2138    /// \brief Retrieve the name that should be used to order a result.
2139    ///
2140    /// If the name needs to be constructed as a string, that string will be
2141    /// saved into Saved and the returned StringRef will refer to it.
2142    static llvm::StringRef getOrderedName(const Result &R,
2143                                          std::string &Saved) {
2144      switch (R.Kind) {
2145      case Result::RK_Keyword:
2146        return R.Keyword;
2147
2148      case Result::RK_Pattern:
2149        return R.Pattern->getTypedText();
2150
2151      case Result::RK_Macro:
2152        return R.Macro->getName();
2153
2154      case Result::RK_Declaration:
2155        // Handle declarations below.
2156        break;
2157      }
2158
2159      DeclarationName Name = R.Declaration->getDeclName();
2160
2161      // If the name is a simple identifier (by far the common case), or a
2162      // zero-argument selector, just return a reference to that identifier.
2163      if (IdentifierInfo *Id = Name.getAsIdentifierInfo())
2164        return Id->getName();
2165      if (Name.isObjCZeroArgSelector())
2166        if (IdentifierInfo *Id
2167                          = Name.getObjCSelector().getIdentifierInfoForSlot(0))
2168          return Id->getName();
2169
2170      Saved = Name.getAsString();
2171      return Saved;
2172    }
2173
2174    bool operator()(const Result &X, const Result &Y) const {
2175      std::string XSaved, YSaved;
2176      llvm::StringRef XStr = getOrderedName(X, XSaved);
2177      llvm::StringRef YStr = getOrderedName(Y, YSaved);
2178      int cmp = XStr.compare_lower(YStr);
2179      if (cmp)
2180        return cmp < 0;
2181
2182      // Non-hidden names precede hidden names.
2183      if (X.Hidden != Y.Hidden)
2184        return !X.Hidden;
2185
2186      // Non-nested-name-specifiers precede nested-name-specifiers.
2187      if (X.StartsNestedNameSpecifier != Y.StartsNestedNameSpecifier)
2188        return !X.StartsNestedNameSpecifier;
2189
2190      return false;
2191    }
2192  };
2193}
2194
2195unsigned clang::getMacroUsagePriority(llvm::StringRef MacroName,
2196                                      bool PreferredTypeIsPointer) {
2197  unsigned Priority = CCP_Macro;
2198
2199  // Treat the "nil" and "NULL" macros as null pointer constants.
2200  if (MacroName.equals("nil") || MacroName.equals("NULL")) {
2201    Priority = CCP_Constant;
2202    if (PreferredTypeIsPointer)
2203      Priority = Priority / CCF_SimilarTypeMatch;
2204  }
2205
2206  return Priority;
2207}
2208
2209static void AddMacroResults(Preprocessor &PP, ResultBuilder &Results,
2210                            bool TargetTypeIsPointer = false) {
2211  typedef CodeCompleteConsumer::Result Result;
2212
2213  Results.EnterNewScope();
2214  for (Preprocessor::macro_iterator M = PP.macro_begin(),
2215                                 MEnd = PP.macro_end();
2216       M != MEnd; ++M) {
2217    Results.AddResult(Result(M->first,
2218                             getMacroUsagePriority(M->first->getName(),
2219                                                   TargetTypeIsPointer)));
2220  }
2221  Results.ExitScope();
2222}
2223
2224static void HandleCodeCompleteResults(Sema *S,
2225                                      CodeCompleteConsumer *CodeCompleter,
2226                                      CodeCompletionContext Context,
2227                                      CodeCompleteConsumer::Result *Results,
2228                                      unsigned NumResults) {
2229  std::stable_sort(Results, Results + NumResults, SortCodeCompleteResult());
2230
2231  if (CodeCompleter)
2232    CodeCompleter->ProcessCodeCompleteResults(*S, Context, Results, NumResults);
2233
2234  for (unsigned I = 0; I != NumResults; ++I)
2235    Results[I].Destroy();
2236}
2237
2238static enum CodeCompletionContext::Kind mapCodeCompletionContext(Sema &S,
2239                                            Sema::ParserCompletionContext PCC) {
2240  switch (PCC) {
2241  case Action::PCC_Namespace:
2242    return CodeCompletionContext::CCC_TopLevel;
2243
2244  case Action::PCC_Class:
2245    return CodeCompletionContext::CCC_ClassStructUnion;
2246
2247  case Action::PCC_ObjCInterface:
2248    return CodeCompletionContext::CCC_ObjCInterface;
2249
2250  case Action::PCC_ObjCImplementation:
2251    return CodeCompletionContext::CCC_ObjCImplementation;
2252
2253  case Action::PCC_ObjCInstanceVariableList:
2254    return CodeCompletionContext::CCC_ObjCIvarList;
2255
2256  case Action::PCC_Template:
2257  case Action::PCC_MemberTemplate:
2258  case Action::PCC_RecoveryInFunction:
2259    return CodeCompletionContext::CCC_Other;
2260
2261  case Action::PCC_Expression:
2262  case Action::PCC_ForInit:
2263  case Action::PCC_Condition:
2264    return CodeCompletionContext::CCC_Expression;
2265
2266  case Action::PCC_Statement:
2267    return CodeCompletionContext::CCC_Statement;
2268  }
2269
2270  return CodeCompletionContext::CCC_Other;
2271}
2272
2273void Sema::CodeCompleteOrdinaryName(Scope *S,
2274                                    ParserCompletionContext CompletionContext) {
2275  typedef CodeCompleteConsumer::Result Result;
2276  ResultBuilder Results(*this);
2277
2278  // Determine how to filter results, e.g., so that the names of
2279  // values (functions, enumerators, function templates, etc.) are
2280  // only allowed where we can have an expression.
2281  switch (CompletionContext) {
2282  case PCC_Namespace:
2283  case PCC_Class:
2284  case PCC_ObjCInterface:
2285  case PCC_ObjCImplementation:
2286  case PCC_ObjCInstanceVariableList:
2287  case PCC_Template:
2288  case PCC_MemberTemplate:
2289    Results.setFilter(&ResultBuilder::IsOrdinaryNonValueName);
2290    break;
2291
2292  case PCC_Expression:
2293  case PCC_Statement:
2294  case PCC_ForInit:
2295  case PCC_Condition:
2296    if (WantTypesInContext(CompletionContext, getLangOptions()))
2297      Results.setFilter(&ResultBuilder::IsOrdinaryName);
2298    else
2299      Results.setFilter(&ResultBuilder::IsOrdinaryNonTypeName);
2300    break;
2301
2302  case PCC_RecoveryInFunction:
2303    // Unfiltered
2304    break;
2305  }
2306
2307  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2308  LookupVisibleDecls(S, LookupOrdinaryName, Consumer,
2309                     CodeCompleter->includeGlobals());
2310
2311  Results.EnterNewScope();
2312  AddOrdinaryNameResults(CompletionContext, S, *this, Results);
2313  Results.ExitScope();
2314
2315  if (CodeCompleter->includeMacros())
2316    AddMacroResults(PP, Results);
2317  HandleCodeCompleteResults(this, CodeCompleter,
2318                            mapCodeCompletionContext(*this, CompletionContext),
2319                            Results.data(),Results.size());
2320}
2321
2322/// \brief Perform code-completion in an expression context when we know what
2323/// type we're looking for.
2324///
2325/// \param IntegralConstantExpression Only permit integral constant
2326/// expressions.
2327void Sema::CodeCompleteExpression(Scope *S, QualType T,
2328                                  bool IntegralConstantExpression) {
2329  typedef CodeCompleteConsumer::Result Result;
2330  ResultBuilder Results(*this);
2331
2332  if (IntegralConstantExpression)
2333    Results.setFilter(&ResultBuilder::IsIntegralConstantValue);
2334  else if (WantTypesInContext(PCC_Expression, getLangOptions()))
2335    Results.setFilter(&ResultBuilder::IsOrdinaryName);
2336  else
2337    Results.setFilter(&ResultBuilder::IsOrdinaryNonTypeName);
2338  Results.setPreferredType(T.getNonReferenceType());
2339
2340  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2341  LookupVisibleDecls(S, LookupOrdinaryName, Consumer,
2342                     CodeCompleter->includeGlobals());
2343
2344  Results.EnterNewScope();
2345  AddOrdinaryNameResults(PCC_Expression, S, *this, Results);
2346  Results.ExitScope();
2347
2348  bool PreferredTypeIsPointer = false;
2349  if (!T.isNull())
2350    PreferredTypeIsPointer = T->isAnyPointerType() ||
2351      T->isMemberPointerType() || T->isBlockPointerType();
2352
2353  if (CodeCompleter->includeMacros())
2354    AddMacroResults(PP, Results, PreferredTypeIsPointer);
2355  HandleCodeCompleteResults(this, CodeCompleter,
2356                CodeCompletionContext(CodeCompletionContext::CCC_Expression, T),
2357                            Results.data(),Results.size());
2358}
2359
2360
2361static void AddObjCProperties(ObjCContainerDecl *Container,
2362                              bool AllowCategories,
2363                              DeclContext *CurContext,
2364                              ResultBuilder &Results) {
2365  typedef CodeCompleteConsumer::Result Result;
2366
2367  // Add properties in this container.
2368  for (ObjCContainerDecl::prop_iterator P = Container->prop_begin(),
2369                                     PEnd = Container->prop_end();
2370       P != PEnd;
2371       ++P)
2372    Results.MaybeAddResult(Result(*P, 0), CurContext);
2373
2374  // Add properties in referenced protocols.
2375  if (ObjCProtocolDecl *Protocol = dyn_cast<ObjCProtocolDecl>(Container)) {
2376    for (ObjCProtocolDecl::protocol_iterator P = Protocol->protocol_begin(),
2377                                          PEnd = Protocol->protocol_end();
2378         P != PEnd; ++P)
2379      AddObjCProperties(*P, AllowCategories, CurContext, Results);
2380  } else if (ObjCInterfaceDecl *IFace = dyn_cast<ObjCInterfaceDecl>(Container)){
2381    if (AllowCategories) {
2382      // Look through categories.
2383      for (ObjCCategoryDecl *Category = IFace->getCategoryList();
2384           Category; Category = Category->getNextClassCategory())
2385        AddObjCProperties(Category, AllowCategories, CurContext, Results);
2386    }
2387
2388    // Look through protocols.
2389    for (ObjCInterfaceDecl::protocol_iterator I = IFace->protocol_begin(),
2390                                              E = IFace->protocol_end();
2391         I != E; ++I)
2392      AddObjCProperties(*I, AllowCategories, CurContext, Results);
2393
2394    // Look in the superclass.
2395    if (IFace->getSuperClass())
2396      AddObjCProperties(IFace->getSuperClass(), AllowCategories, CurContext,
2397                        Results);
2398  } else if (const ObjCCategoryDecl *Category
2399                                    = dyn_cast<ObjCCategoryDecl>(Container)) {
2400    // Look through protocols.
2401    for (ObjCInterfaceDecl::protocol_iterator P = Category->protocol_begin(),
2402                                           PEnd = Category->protocol_end();
2403         P != PEnd; ++P)
2404      AddObjCProperties(*P, AllowCategories, CurContext, Results);
2405  }
2406}
2407
2408void Sema::CodeCompleteMemberReferenceExpr(Scope *S, ExprTy *BaseE,
2409                                           SourceLocation OpLoc,
2410                                           bool IsArrow) {
2411  if (!BaseE || !CodeCompleter)
2412    return;
2413
2414  typedef CodeCompleteConsumer::Result Result;
2415
2416  Expr *Base = static_cast<Expr *>(BaseE);
2417  QualType BaseType = Base->getType();
2418
2419  if (IsArrow) {
2420    if (const PointerType *Ptr = BaseType->getAs<PointerType>())
2421      BaseType = Ptr->getPointeeType();
2422    else if (BaseType->isObjCObjectPointerType())
2423    /*Do nothing*/ ;
2424    else
2425      return;
2426  }
2427
2428  ResultBuilder Results(*this, &ResultBuilder::IsMember);
2429  Results.EnterNewScope();
2430  if (const RecordType *Record = BaseType->getAs<RecordType>()) {
2431    // Access to a C/C++ class, struct, or union.
2432    Results.allowNestedNameSpecifiers();
2433    CodeCompletionDeclConsumer Consumer(Results, CurContext);
2434    LookupVisibleDecls(Record->getDecl(), LookupMemberName, Consumer,
2435                       CodeCompleter->includeGlobals());
2436
2437    if (getLangOptions().CPlusPlus) {
2438      if (!Results.empty()) {
2439        // The "template" keyword can follow "->" or "." in the grammar.
2440        // However, we only want to suggest the template keyword if something
2441        // is dependent.
2442        bool IsDependent = BaseType->isDependentType();
2443        if (!IsDependent) {
2444          for (Scope *DepScope = S; DepScope; DepScope = DepScope->getParent())
2445            if (DeclContext *Ctx = (DeclContext *)DepScope->getEntity()) {
2446              IsDependent = Ctx->isDependentContext();
2447              break;
2448            }
2449        }
2450
2451        if (IsDependent)
2452          Results.AddResult(Result("template"));
2453      }
2454    }
2455  } else if (!IsArrow && BaseType->getAsObjCInterfacePointerType()) {
2456    // Objective-C property reference.
2457
2458    // Add property results based on our interface.
2459    const ObjCObjectPointerType *ObjCPtr
2460      = BaseType->getAsObjCInterfacePointerType();
2461    assert(ObjCPtr && "Non-NULL pointer guaranteed above!");
2462    AddObjCProperties(ObjCPtr->getInterfaceDecl(), true, CurContext, Results);
2463
2464    // Add properties from the protocols in a qualified interface.
2465    for (ObjCObjectPointerType::qual_iterator I = ObjCPtr->qual_begin(),
2466                                              E = ObjCPtr->qual_end();
2467         I != E; ++I)
2468      AddObjCProperties(*I, true, CurContext, Results);
2469  } else if ((IsArrow && BaseType->isObjCObjectPointerType()) ||
2470             (!IsArrow && BaseType->isObjCObjectType())) {
2471    // Objective-C instance variable access.
2472    ObjCInterfaceDecl *Class = 0;
2473    if (const ObjCObjectPointerType *ObjCPtr
2474                                    = BaseType->getAs<ObjCObjectPointerType>())
2475      Class = ObjCPtr->getInterfaceDecl();
2476    else
2477      Class = BaseType->getAs<ObjCObjectType>()->getInterface();
2478
2479    // Add all ivars from this class and its superclasses.
2480    if (Class) {
2481      CodeCompletionDeclConsumer Consumer(Results, CurContext);
2482      Results.setFilter(&ResultBuilder::IsObjCIvar);
2483      LookupVisibleDecls(Class, LookupMemberName, Consumer,
2484                         CodeCompleter->includeGlobals());
2485    }
2486  }
2487
2488  // FIXME: How do we cope with isa?
2489
2490  Results.ExitScope();
2491
2492  // Hand off the results found for code completion.
2493  HandleCodeCompleteResults(this, CodeCompleter,
2494            CodeCompletionContext(CodeCompletionContext::CCC_MemberAccess,
2495                                              BaseType),
2496                            Results.data(),Results.size());
2497}
2498
2499void Sema::CodeCompleteTag(Scope *S, unsigned TagSpec) {
2500  if (!CodeCompleter)
2501    return;
2502
2503  typedef CodeCompleteConsumer::Result Result;
2504  ResultBuilder::LookupFilter Filter = 0;
2505  enum CodeCompletionContext::Kind ContextKind
2506    = CodeCompletionContext::CCC_Other;
2507  switch ((DeclSpec::TST)TagSpec) {
2508  case DeclSpec::TST_enum:
2509    Filter = &ResultBuilder::IsEnum;
2510    ContextKind = CodeCompletionContext::CCC_EnumTag;
2511    break;
2512
2513  case DeclSpec::TST_union:
2514    Filter = &ResultBuilder::IsUnion;
2515    ContextKind = CodeCompletionContext::CCC_UnionTag;
2516    break;
2517
2518  case DeclSpec::TST_struct:
2519  case DeclSpec::TST_class:
2520    Filter = &ResultBuilder::IsClassOrStruct;
2521    ContextKind = CodeCompletionContext::CCC_ClassOrStructTag;
2522    break;
2523
2524  default:
2525    assert(false && "Unknown type specifier kind in CodeCompleteTag");
2526    return;
2527  }
2528
2529  ResultBuilder Results(*this);
2530  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2531
2532  // First pass: look for tags.
2533  Results.setFilter(Filter);
2534  LookupVisibleDecls(S, LookupTagName, Consumer,
2535                     CodeCompleter->includeGlobals());
2536
2537  if (CodeCompleter->includeGlobals()) {
2538    // Second pass: look for nested name specifiers.
2539    Results.setFilter(&ResultBuilder::IsNestedNameSpecifier);
2540    LookupVisibleDecls(S, LookupNestedNameSpecifierName, Consumer);
2541  }
2542
2543  HandleCodeCompleteResults(this, CodeCompleter, ContextKind,
2544                            Results.data(),Results.size());
2545}
2546
2547void Sema::CodeCompleteCase(Scope *S) {
2548  if (getSwitchStack().empty() || !CodeCompleter)
2549    return;
2550
2551  SwitchStmt *Switch = getSwitchStack().back();
2552  if (!Switch->getCond()->getType()->isEnumeralType()) {
2553    CodeCompleteExpression(S, Switch->getCond()->getType(), true);
2554    return;
2555  }
2556
2557  // Code-complete the cases of a switch statement over an enumeration type
2558  // by providing the list of
2559  EnumDecl *Enum = Switch->getCond()->getType()->getAs<EnumType>()->getDecl();
2560
2561  // Determine which enumerators we have already seen in the switch statement.
2562  // FIXME: Ideally, we would also be able to look *past* the code-completion
2563  // token, in case we are code-completing in the middle of the switch and not
2564  // at the end. However, we aren't able to do so at the moment.
2565  llvm::SmallPtrSet<EnumConstantDecl *, 8> EnumeratorsSeen;
2566  NestedNameSpecifier *Qualifier = 0;
2567  for (SwitchCase *SC = Switch->getSwitchCaseList(); SC;
2568       SC = SC->getNextSwitchCase()) {
2569    CaseStmt *Case = dyn_cast<CaseStmt>(SC);
2570    if (!Case)
2571      continue;
2572
2573    Expr *CaseVal = Case->getLHS()->IgnoreParenCasts();
2574    if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(CaseVal))
2575      if (EnumConstantDecl *Enumerator
2576            = dyn_cast<EnumConstantDecl>(DRE->getDecl())) {
2577        // We look into the AST of the case statement to determine which
2578        // enumerator was named. Alternatively, we could compute the value of
2579        // the integral constant expression, then compare it against the
2580        // values of each enumerator. However, value-based approach would not
2581        // work as well with C++ templates where enumerators declared within a
2582        // template are type- and value-dependent.
2583        EnumeratorsSeen.insert(Enumerator);
2584
2585        // If this is a qualified-id, keep track of the nested-name-specifier
2586        // so that we can reproduce it as part of code completion, e.g.,
2587        //
2588        //   switch (TagD.getKind()) {
2589        //     case TagDecl::TK_enum:
2590        //       break;
2591        //     case XXX
2592        //
2593        // At the XXX, our completions are TagDecl::TK_union,
2594        // TagDecl::TK_struct, and TagDecl::TK_class, rather than TK_union,
2595        // TK_struct, and TK_class.
2596        Qualifier = DRE->getQualifier();
2597      }
2598  }
2599
2600  if (getLangOptions().CPlusPlus && !Qualifier && EnumeratorsSeen.empty()) {
2601    // If there are no prior enumerators in C++, check whether we have to
2602    // qualify the names of the enumerators that we suggest, because they
2603    // may not be visible in this scope.
2604    Qualifier = getRequiredQualification(Context, CurContext,
2605                                         Enum->getDeclContext());
2606
2607    // FIXME: Scoped enums need to start with "EnumDecl" as the context!
2608  }
2609
2610  // Add any enumerators that have not yet been mentioned.
2611  ResultBuilder Results(*this);
2612  Results.EnterNewScope();
2613  for (EnumDecl::enumerator_iterator E = Enum->enumerator_begin(),
2614                                  EEnd = Enum->enumerator_end();
2615       E != EEnd; ++E) {
2616    if (EnumeratorsSeen.count(*E))
2617      continue;
2618
2619    Results.AddResult(CodeCompleteConsumer::Result(*E, Qualifier),
2620                      CurContext, 0, false);
2621  }
2622  Results.ExitScope();
2623
2624  if (CodeCompleter->includeMacros())
2625    AddMacroResults(PP, Results);
2626  HandleCodeCompleteResults(this, CodeCompleter,
2627                            CodeCompletionContext::CCC_Expression,
2628                            Results.data(),Results.size());
2629}
2630
2631namespace {
2632  struct IsBetterOverloadCandidate {
2633    Sema &S;
2634    SourceLocation Loc;
2635
2636  public:
2637    explicit IsBetterOverloadCandidate(Sema &S, SourceLocation Loc)
2638      : S(S), Loc(Loc) { }
2639
2640    bool
2641    operator()(const OverloadCandidate &X, const OverloadCandidate &Y) const {
2642      return S.isBetterOverloadCandidate(X, Y, Loc);
2643    }
2644  };
2645}
2646
2647static bool anyNullArguments(Expr **Args, unsigned NumArgs) {
2648  if (NumArgs && !Args)
2649    return true;
2650
2651  for (unsigned I = 0; I != NumArgs; ++I)
2652    if (!Args[I])
2653      return true;
2654
2655  return false;
2656}
2657
2658void Sema::CodeCompleteCall(Scope *S, ExprTy *FnIn,
2659                            ExprTy **ArgsIn, unsigned NumArgs) {
2660  if (!CodeCompleter)
2661    return;
2662
2663  // When we're code-completing for a call, we fall back to ordinary
2664  // name code-completion whenever we can't produce specific
2665  // results. We may want to revisit this strategy in the future,
2666  // e.g., by merging the two kinds of results.
2667
2668  Expr *Fn = (Expr *)FnIn;
2669  Expr **Args = (Expr **)ArgsIn;
2670
2671  // Ignore type-dependent call expressions entirely.
2672  if (!Fn || Fn->isTypeDependent() || anyNullArguments(Args, NumArgs) ||
2673      Expr::hasAnyTypeDependentArguments(Args, NumArgs)) {
2674    CodeCompleteOrdinaryName(S, PCC_Expression);
2675    return;
2676  }
2677
2678  // Build an overload candidate set based on the functions we find.
2679  SourceLocation Loc = Fn->getExprLoc();
2680  OverloadCandidateSet CandidateSet(Loc);
2681
2682  // FIXME: What if we're calling something that isn't a function declaration?
2683  // FIXME: What if we're calling a pseudo-destructor?
2684  // FIXME: What if we're calling a member function?
2685
2686  typedef CodeCompleteConsumer::OverloadCandidate ResultCandidate;
2687  llvm::SmallVector<ResultCandidate, 8> Results;
2688
2689  Expr *NakedFn = Fn->IgnoreParenCasts();
2690  if (UnresolvedLookupExpr *ULE = dyn_cast<UnresolvedLookupExpr>(NakedFn))
2691    AddOverloadedCallCandidates(ULE, Args, NumArgs, CandidateSet,
2692                                /*PartialOverloading=*/ true);
2693  else if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(NakedFn)) {
2694    FunctionDecl *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl());
2695    if (FDecl) {
2696      if (!getLangOptions().CPlusPlus ||
2697          !FDecl->getType()->getAs<FunctionProtoType>())
2698        Results.push_back(ResultCandidate(FDecl));
2699      else
2700        // FIXME: access?
2701        AddOverloadCandidate(FDecl, DeclAccessPair::make(FDecl, AS_none),
2702                             Args, NumArgs, CandidateSet,
2703                             false, /*PartialOverloading*/true);
2704    }
2705  }
2706
2707  QualType ParamType;
2708
2709  if (!CandidateSet.empty()) {
2710    // Sort the overload candidate set by placing the best overloads first.
2711    std::stable_sort(CandidateSet.begin(), CandidateSet.end(),
2712                     IsBetterOverloadCandidate(*this, Loc));
2713
2714    // Add the remaining viable overload candidates as code-completion reslults.
2715    for (OverloadCandidateSet::iterator Cand = CandidateSet.begin(),
2716                                     CandEnd = CandidateSet.end();
2717         Cand != CandEnd; ++Cand) {
2718      if (Cand->Viable)
2719        Results.push_back(ResultCandidate(Cand->Function));
2720    }
2721
2722    // From the viable candidates, try to determine the type of this parameter.
2723    for (unsigned I = 0, N = Results.size(); I != N; ++I) {
2724      if (const FunctionType *FType = Results[I].getFunctionType())
2725        if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FType))
2726          if (NumArgs < Proto->getNumArgs()) {
2727            if (ParamType.isNull())
2728              ParamType = Proto->getArgType(NumArgs);
2729            else if (!Context.hasSameUnqualifiedType(
2730                                            ParamType.getNonReferenceType(),
2731                           Proto->getArgType(NumArgs).getNonReferenceType())) {
2732              ParamType = QualType();
2733              break;
2734            }
2735          }
2736    }
2737  } else {
2738    // Try to determine the parameter type from the type of the expression
2739    // being called.
2740    QualType FunctionType = Fn->getType();
2741    if (const PointerType *Ptr = FunctionType->getAs<PointerType>())
2742      FunctionType = Ptr->getPointeeType();
2743    else if (const BlockPointerType *BlockPtr
2744                                    = FunctionType->getAs<BlockPointerType>())
2745      FunctionType = BlockPtr->getPointeeType();
2746    else if (const MemberPointerType *MemPtr
2747                                    = FunctionType->getAs<MemberPointerType>())
2748      FunctionType = MemPtr->getPointeeType();
2749
2750    if (const FunctionProtoType *Proto
2751                                  = FunctionType->getAs<FunctionProtoType>()) {
2752      if (NumArgs < Proto->getNumArgs())
2753        ParamType = Proto->getArgType(NumArgs);
2754    }
2755  }
2756
2757  if (ParamType.isNull())
2758    CodeCompleteOrdinaryName(S, PCC_Expression);
2759  else
2760    CodeCompleteExpression(S, ParamType);
2761
2762  if (!Results.empty())
2763    CodeCompleter->ProcessOverloadCandidates(*this, NumArgs, Results.data(),
2764                                             Results.size());
2765}
2766
2767void Sema::CodeCompleteInitializer(Scope *S, DeclPtrTy D) {
2768  ValueDecl *VD = dyn_cast_or_null<ValueDecl>(D.getAs<Decl>());
2769  if (!VD) {
2770    CodeCompleteOrdinaryName(S, PCC_Expression);
2771    return;
2772  }
2773
2774  CodeCompleteExpression(S, VD->getType());
2775}
2776
2777void Sema::CodeCompleteReturn(Scope *S) {
2778  QualType ResultType;
2779  if (isa<BlockDecl>(CurContext)) {
2780    if (BlockScopeInfo *BSI = getCurBlock())
2781      ResultType = BSI->ReturnType;
2782  } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(CurContext))
2783    ResultType = Function->getResultType();
2784  else if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(CurContext))
2785    ResultType = Method->getResultType();
2786
2787  if (ResultType.isNull())
2788    CodeCompleteOrdinaryName(S, PCC_Expression);
2789  else
2790    CodeCompleteExpression(S, ResultType);
2791}
2792
2793void Sema::CodeCompleteAssignmentRHS(Scope *S, ExprTy *LHS) {
2794  if (LHS)
2795    CodeCompleteExpression(S, static_cast<Expr *>(LHS)->getType());
2796  else
2797    CodeCompleteOrdinaryName(S, PCC_Expression);
2798}
2799
2800void Sema::CodeCompleteQualifiedId(Scope *S, CXXScopeSpec &SS,
2801                                   bool EnteringContext) {
2802  if (!SS.getScopeRep() || !CodeCompleter)
2803    return;
2804
2805  DeclContext *Ctx = computeDeclContext(SS, EnteringContext);
2806  if (!Ctx)
2807    return;
2808
2809  // Try to instantiate any non-dependent declaration contexts before
2810  // we look in them.
2811  if (!isDependentScopeSpecifier(SS) && RequireCompleteDeclContext(SS, Ctx))
2812    return;
2813
2814  ResultBuilder Results(*this);
2815  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2816  LookupVisibleDecls(Ctx, LookupOrdinaryName, Consumer);
2817
2818  // The "template" keyword can follow "::" in the grammar, but only
2819  // put it into the grammar if the nested-name-specifier is dependent.
2820  NestedNameSpecifier *NNS = (NestedNameSpecifier *)SS.getScopeRep();
2821  if (!Results.empty() && NNS->isDependent())
2822    Results.AddResult("template");
2823
2824  HandleCodeCompleteResults(this, CodeCompleter,
2825                            CodeCompletionContext::CCC_Other,
2826                            Results.data(),Results.size());
2827}
2828
2829void Sema::CodeCompleteUsing(Scope *S) {
2830  if (!CodeCompleter)
2831    return;
2832
2833  ResultBuilder Results(*this, &ResultBuilder::IsNestedNameSpecifier);
2834  Results.EnterNewScope();
2835
2836  // If we aren't in class scope, we could see the "namespace" keyword.
2837  if (!S->isClassScope())
2838    Results.AddResult(CodeCompleteConsumer::Result("namespace"));
2839
2840  // After "using", we can see anything that would start a
2841  // nested-name-specifier.
2842  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2843  LookupVisibleDecls(S, LookupOrdinaryName, Consumer,
2844                     CodeCompleter->includeGlobals());
2845  Results.ExitScope();
2846
2847  HandleCodeCompleteResults(this, CodeCompleter,
2848                            CodeCompletionContext::CCC_Other,
2849                            Results.data(),Results.size());
2850}
2851
2852void Sema::CodeCompleteUsingDirective(Scope *S) {
2853  if (!CodeCompleter)
2854    return;
2855
2856  // After "using namespace", we expect to see a namespace name or namespace
2857  // alias.
2858  ResultBuilder Results(*this, &ResultBuilder::IsNamespaceOrAlias);
2859  Results.EnterNewScope();
2860  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2861  LookupVisibleDecls(S, LookupOrdinaryName, Consumer,
2862                     CodeCompleter->includeGlobals());
2863  Results.ExitScope();
2864  HandleCodeCompleteResults(this, CodeCompleter,
2865                            CodeCompletionContext::CCC_Namespace,
2866                            Results.data(),Results.size());
2867}
2868
2869void Sema::CodeCompleteNamespaceDecl(Scope *S)  {
2870  if (!CodeCompleter)
2871    return;
2872
2873  ResultBuilder Results(*this, &ResultBuilder::IsNamespace);
2874  DeclContext *Ctx = (DeclContext *)S->getEntity();
2875  if (!S->getParent())
2876    Ctx = Context.getTranslationUnitDecl();
2877
2878  if (Ctx && Ctx->isFileContext()) {
2879    // We only want to see those namespaces that have already been defined
2880    // within this scope, because its likely that the user is creating an
2881    // extended namespace declaration. Keep track of the most recent
2882    // definition of each namespace.
2883    std::map<NamespaceDecl *, NamespaceDecl *> OrigToLatest;
2884    for (DeclContext::specific_decl_iterator<NamespaceDecl>
2885         NS(Ctx->decls_begin()), NSEnd(Ctx->decls_end());
2886         NS != NSEnd; ++NS)
2887      OrigToLatest[NS->getOriginalNamespace()] = *NS;
2888
2889    // Add the most recent definition (or extended definition) of each
2890    // namespace to the list of results.
2891    Results.EnterNewScope();
2892    for (std::map<NamespaceDecl *, NamespaceDecl *>::iterator
2893         NS = OrigToLatest.begin(), NSEnd = OrigToLatest.end();
2894         NS != NSEnd; ++NS)
2895      Results.AddResult(CodeCompleteConsumer::Result(NS->second, 0),
2896                        CurContext, 0, false);
2897    Results.ExitScope();
2898  }
2899
2900  HandleCodeCompleteResults(this, CodeCompleter,
2901                            CodeCompletionContext::CCC_Other,
2902                            Results.data(),Results.size());
2903}
2904
2905void Sema::CodeCompleteNamespaceAliasDecl(Scope *S)  {
2906  if (!CodeCompleter)
2907    return;
2908
2909  // After "namespace", we expect to see a namespace or alias.
2910  ResultBuilder Results(*this, &ResultBuilder::IsNamespaceOrAlias);
2911  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2912  LookupVisibleDecls(S, LookupOrdinaryName, Consumer,
2913                     CodeCompleter->includeGlobals());
2914  HandleCodeCompleteResults(this, CodeCompleter,
2915                            CodeCompletionContext::CCC_Namespace,
2916                            Results.data(),Results.size());
2917}
2918
2919void Sema::CodeCompleteOperatorName(Scope *S) {
2920  if (!CodeCompleter)
2921    return;
2922
2923  typedef CodeCompleteConsumer::Result Result;
2924  ResultBuilder Results(*this, &ResultBuilder::IsType);
2925  Results.EnterNewScope();
2926
2927  // Add the names of overloadable operators.
2928#define OVERLOADED_OPERATOR(Name,Spelling,Token,Unary,Binary,MemberOnly)      \
2929  if (std::strcmp(Spelling, "?"))                                                  \
2930    Results.AddResult(Result(Spelling));
2931#include "clang/Basic/OperatorKinds.def"
2932
2933  // Add any type names visible from the current scope
2934  Results.allowNestedNameSpecifiers();
2935  CodeCompletionDeclConsumer Consumer(Results, CurContext);
2936  LookupVisibleDecls(S, LookupOrdinaryName, Consumer,
2937                     CodeCompleter->includeGlobals());
2938
2939  // Add any type specifiers
2940  AddTypeSpecifierResults(getLangOptions(), Results);
2941  Results.ExitScope();
2942
2943  HandleCodeCompleteResults(this, CodeCompleter,
2944                            CodeCompletionContext::CCC_Type,
2945                            Results.data(),Results.size());
2946}
2947
2948// Macro that expands to @Keyword or Keyword, depending on whether NeedAt is
2949// true or false.
2950#define OBJC_AT_KEYWORD_NAME(NeedAt,Keyword) NeedAt? "@" #Keyword : #Keyword
2951static void AddObjCImplementationResults(const LangOptions &LangOpts,
2952                                         ResultBuilder &Results,
2953                                         bool NeedAt) {
2954  typedef CodeCompleteConsumer::Result Result;
2955  // Since we have an implementation, we can end it.
2956  Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,end)));
2957
2958  CodeCompletionString *Pattern = 0;
2959  if (LangOpts.ObjC2) {
2960    // @dynamic
2961    Pattern = new CodeCompletionString;
2962    Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,dynamic));
2963    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
2964    Pattern->AddPlaceholderChunk("property");
2965    Results.AddResult(Result(Pattern));
2966
2967    // @synthesize
2968    Pattern = new CodeCompletionString;
2969    Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,synthesize));
2970    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
2971    Pattern->AddPlaceholderChunk("property");
2972    Results.AddResult(Result(Pattern));
2973  }
2974}
2975
2976static void AddObjCInterfaceResults(const LangOptions &LangOpts,
2977                                    ResultBuilder &Results,
2978                                    bool NeedAt) {
2979  typedef CodeCompleteConsumer::Result Result;
2980
2981  // Since we have an interface or protocol, we can end it.
2982  Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,end)));
2983
2984  if (LangOpts.ObjC2) {
2985    // @property
2986    Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,property)));
2987
2988    // @required
2989    Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,required)));
2990
2991    // @optional
2992    Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,optional)));
2993  }
2994}
2995
2996static void AddObjCTopLevelResults(ResultBuilder &Results, bool NeedAt) {
2997  typedef CodeCompleteConsumer::Result Result;
2998  CodeCompletionString *Pattern = 0;
2999
3000  // @class name ;
3001  Pattern = new CodeCompletionString;
3002  Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,class));
3003  Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3004  Pattern->AddPlaceholderChunk("name");
3005  Results.AddResult(Result(Pattern));
3006
3007  if (Results.includeCodePatterns()) {
3008    // @interface name
3009    // FIXME: Could introduce the whole pattern, including superclasses and
3010    // such.
3011    Pattern = new CodeCompletionString;
3012    Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,interface));
3013    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3014    Pattern->AddPlaceholderChunk("class");
3015    Results.AddResult(Result(Pattern));
3016
3017    // @protocol name
3018    Pattern = new CodeCompletionString;
3019    Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,protocol));
3020    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3021    Pattern->AddPlaceholderChunk("protocol");
3022    Results.AddResult(Result(Pattern));
3023
3024    // @implementation name
3025    Pattern = new CodeCompletionString;
3026    Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,implementation));
3027    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3028    Pattern->AddPlaceholderChunk("class");
3029    Results.AddResult(Result(Pattern));
3030  }
3031
3032  // @compatibility_alias name
3033  Pattern = new CodeCompletionString;
3034  Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,compatibility_alias));
3035  Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3036  Pattern->AddPlaceholderChunk("alias");
3037  Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3038  Pattern->AddPlaceholderChunk("class");
3039  Results.AddResult(Result(Pattern));
3040}
3041
3042void Sema::CodeCompleteObjCAtDirective(Scope *S, DeclPtrTy ObjCImpDecl,
3043                                       bool InInterface) {
3044  typedef CodeCompleteConsumer::Result Result;
3045  ResultBuilder Results(*this);
3046  Results.EnterNewScope();
3047  if (ObjCImpDecl)
3048    AddObjCImplementationResults(getLangOptions(), Results, false);
3049  else if (InInterface)
3050    AddObjCInterfaceResults(getLangOptions(), Results, false);
3051  else
3052    AddObjCTopLevelResults(Results, false);
3053  Results.ExitScope();
3054  HandleCodeCompleteResults(this, CodeCompleter,
3055                            CodeCompletionContext::CCC_Other,
3056                            Results.data(),Results.size());
3057}
3058
3059static void AddObjCExpressionResults(ResultBuilder &Results, bool NeedAt) {
3060  typedef CodeCompleteConsumer::Result Result;
3061  CodeCompletionString *Pattern = 0;
3062
3063  // @encode ( type-name )
3064  Pattern = new CodeCompletionString;
3065  Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,encode));
3066  Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
3067  Pattern->AddPlaceholderChunk("type-name");
3068  Pattern->AddChunk(CodeCompletionString::CK_RightParen);
3069  Results.AddResult(Result(Pattern));
3070
3071  // @protocol ( protocol-name )
3072  Pattern = new CodeCompletionString;
3073  Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,protocol));
3074  Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
3075  Pattern->AddPlaceholderChunk("protocol-name");
3076  Pattern->AddChunk(CodeCompletionString::CK_RightParen);
3077  Results.AddResult(Result(Pattern));
3078
3079  // @selector ( selector )
3080  Pattern = new CodeCompletionString;
3081  Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,selector));
3082  Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
3083  Pattern->AddPlaceholderChunk("selector");
3084  Pattern->AddChunk(CodeCompletionString::CK_RightParen);
3085  Results.AddResult(Result(Pattern));
3086}
3087
3088static void AddObjCStatementResults(ResultBuilder &Results, bool NeedAt) {
3089  typedef CodeCompleteConsumer::Result Result;
3090  CodeCompletionString *Pattern = 0;
3091
3092  if (Results.includeCodePatterns()) {
3093    // @try { statements } @catch ( declaration ) { statements } @finally
3094    //   { statements }
3095    Pattern = new CodeCompletionString;
3096    Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,try));
3097    Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
3098    Pattern->AddPlaceholderChunk("statements");
3099    Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
3100    Pattern->AddTextChunk("@catch");
3101    Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
3102    Pattern->AddPlaceholderChunk("parameter");
3103    Pattern->AddChunk(CodeCompletionString::CK_RightParen);
3104    Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
3105    Pattern->AddPlaceholderChunk("statements");
3106    Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
3107    Pattern->AddTextChunk("@finally");
3108    Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
3109    Pattern->AddPlaceholderChunk("statements");
3110    Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
3111    Results.AddResult(Result(Pattern));
3112  }
3113
3114  // @throw
3115  Pattern = new CodeCompletionString;
3116  Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,throw));
3117  Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3118  Pattern->AddPlaceholderChunk("expression");
3119  Results.AddResult(Result(Pattern));
3120
3121  if (Results.includeCodePatterns()) {
3122    // @synchronized ( expression ) { statements }
3123    Pattern = new CodeCompletionString;
3124    Pattern->AddTypedTextChunk(OBJC_AT_KEYWORD_NAME(NeedAt,synchronized));
3125    Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
3126    Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
3127    Pattern->AddPlaceholderChunk("expression");
3128    Pattern->AddChunk(CodeCompletionString::CK_RightParen);
3129    Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
3130    Pattern->AddPlaceholderChunk("statements");
3131    Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
3132    Results.AddResult(Result(Pattern));
3133  }
3134}
3135
3136static void AddObjCVisibilityResults(const LangOptions &LangOpts,
3137                                     ResultBuilder &Results,
3138                                     bool NeedAt) {
3139  typedef CodeCompleteConsumer::Result Result;
3140  Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,private)));
3141  Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,protected)));
3142  Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,public)));
3143  if (LangOpts.ObjC2)
3144    Results.AddResult(Result(OBJC_AT_KEYWORD_NAME(NeedAt,package)));
3145}
3146
3147void Sema::CodeCompleteObjCAtVisibility(Scope *S) {
3148  ResultBuilder Results(*this);
3149  Results.EnterNewScope();
3150  AddObjCVisibilityResults(getLangOptions(), Results, false);
3151  Results.ExitScope();
3152  HandleCodeCompleteResults(this, CodeCompleter,
3153                            CodeCompletionContext::CCC_Other,
3154                            Results.data(),Results.size());
3155}
3156
3157void Sema::CodeCompleteObjCAtStatement(Scope *S) {
3158  ResultBuilder Results(*this);
3159  Results.EnterNewScope();
3160  AddObjCStatementResults(Results, false);
3161  AddObjCExpressionResults(Results, false);
3162  Results.ExitScope();
3163  HandleCodeCompleteResults(this, CodeCompleter,
3164                            CodeCompletionContext::CCC_Other,
3165                            Results.data(),Results.size());
3166}
3167
3168void Sema::CodeCompleteObjCAtExpression(Scope *S) {
3169  ResultBuilder Results(*this);
3170  Results.EnterNewScope();
3171  AddObjCExpressionResults(Results, false);
3172  Results.ExitScope();
3173  HandleCodeCompleteResults(this, CodeCompleter,
3174                            CodeCompletionContext::CCC_Other,
3175                            Results.data(),Results.size());
3176}
3177
3178/// \brief Determine whether the addition of the given flag to an Objective-C
3179/// property's attributes will cause a conflict.
3180static bool ObjCPropertyFlagConflicts(unsigned Attributes, unsigned NewFlag) {
3181  // Check if we've already added this flag.
3182  if (Attributes & NewFlag)
3183    return true;
3184
3185  Attributes |= NewFlag;
3186
3187  // Check for collisions with "readonly".
3188  if ((Attributes & ObjCDeclSpec::DQ_PR_readonly) &&
3189      (Attributes & (ObjCDeclSpec::DQ_PR_readwrite |
3190                     ObjCDeclSpec::DQ_PR_assign |
3191                     ObjCDeclSpec::DQ_PR_copy |
3192                     ObjCDeclSpec::DQ_PR_retain)))
3193    return true;
3194
3195  // Check for more than one of { assign, copy, retain }.
3196  unsigned AssignCopyRetMask = Attributes & (ObjCDeclSpec::DQ_PR_assign |
3197                                             ObjCDeclSpec::DQ_PR_copy |
3198                                             ObjCDeclSpec::DQ_PR_retain);
3199  if (AssignCopyRetMask &&
3200      AssignCopyRetMask != ObjCDeclSpec::DQ_PR_assign &&
3201      AssignCopyRetMask != ObjCDeclSpec::DQ_PR_copy &&
3202      AssignCopyRetMask != ObjCDeclSpec::DQ_PR_retain)
3203    return true;
3204
3205  return false;
3206}
3207
3208void Sema::CodeCompleteObjCPropertyFlags(Scope *S, ObjCDeclSpec &ODS) {
3209  if (!CodeCompleter)
3210    return;
3211
3212  unsigned Attributes = ODS.getPropertyAttributes();
3213
3214  typedef CodeCompleteConsumer::Result Result;
3215  ResultBuilder Results(*this);
3216  Results.EnterNewScope();
3217  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_readonly))
3218    Results.AddResult(CodeCompleteConsumer::Result("readonly"));
3219  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_assign))
3220    Results.AddResult(CodeCompleteConsumer::Result("assign"));
3221  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_readwrite))
3222    Results.AddResult(CodeCompleteConsumer::Result("readwrite"));
3223  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_retain))
3224    Results.AddResult(CodeCompleteConsumer::Result("retain"));
3225  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_copy))
3226    Results.AddResult(CodeCompleteConsumer::Result("copy"));
3227  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_nonatomic))
3228    Results.AddResult(CodeCompleteConsumer::Result("nonatomic"));
3229  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_setter)) {
3230    CodeCompletionString *Setter = new CodeCompletionString;
3231    Setter->AddTypedTextChunk("setter");
3232    Setter->AddTextChunk(" = ");
3233    Setter->AddPlaceholderChunk("method");
3234    Results.AddResult(CodeCompleteConsumer::Result(Setter));
3235  }
3236  if (!ObjCPropertyFlagConflicts(Attributes, ObjCDeclSpec::DQ_PR_getter)) {
3237    CodeCompletionString *Getter = new CodeCompletionString;
3238    Getter->AddTypedTextChunk("getter");
3239    Getter->AddTextChunk(" = ");
3240    Getter->AddPlaceholderChunk("method");
3241    Results.AddResult(CodeCompleteConsumer::Result(Getter));
3242  }
3243  Results.ExitScope();
3244  HandleCodeCompleteResults(this, CodeCompleter,
3245                            CodeCompletionContext::CCC_Other,
3246                            Results.data(),Results.size());
3247}
3248
3249/// \brief Descripts the kind of Objective-C method that we want to find
3250/// via code completion.
3251enum ObjCMethodKind {
3252  MK_Any, //< Any kind of method, provided it means other specified criteria.
3253  MK_ZeroArgSelector, //< Zero-argument (unary) selector.
3254  MK_OneArgSelector //< One-argument selector.
3255};
3256
3257static bool isAcceptableObjCMethod(ObjCMethodDecl *Method,
3258                                   ObjCMethodKind WantKind,
3259                                   IdentifierInfo **SelIdents,
3260                                   unsigned NumSelIdents) {
3261  Selector Sel = Method->getSelector();
3262  if (NumSelIdents > Sel.getNumArgs())
3263    return false;
3264
3265  switch (WantKind) {
3266  case MK_Any:             break;
3267  case MK_ZeroArgSelector: return Sel.isUnarySelector();
3268  case MK_OneArgSelector:  return Sel.getNumArgs() == 1;
3269  }
3270
3271  for (unsigned I = 0; I != NumSelIdents; ++I)
3272    if (SelIdents[I] != Sel.getIdentifierInfoForSlot(I))
3273      return false;
3274
3275  return true;
3276}
3277
3278/// \brief Add all of the Objective-C methods in the given Objective-C
3279/// container to the set of results.
3280///
3281/// The container will be a class, protocol, category, or implementation of
3282/// any of the above. This mether will recurse to include methods from
3283/// the superclasses of classes along with their categories, protocols, and
3284/// implementations.
3285///
3286/// \param Container the container in which we'll look to find methods.
3287///
3288/// \param WantInstance whether to add instance methods (only); if false, this
3289/// routine will add factory methods (only).
3290///
3291/// \param CurContext the context in which we're performing the lookup that
3292/// finds methods.
3293///
3294/// \param Results the structure into which we'll add results.
3295static void AddObjCMethods(ObjCContainerDecl *Container,
3296                           bool WantInstanceMethods,
3297                           ObjCMethodKind WantKind,
3298                           IdentifierInfo **SelIdents,
3299                           unsigned NumSelIdents,
3300                           DeclContext *CurContext,
3301                           ResultBuilder &Results) {
3302  typedef CodeCompleteConsumer::Result Result;
3303  for (ObjCContainerDecl::method_iterator M = Container->meth_begin(),
3304                                       MEnd = Container->meth_end();
3305       M != MEnd; ++M) {
3306    if ((*M)->isInstanceMethod() == WantInstanceMethods) {
3307      // Check whether the selector identifiers we've been given are a
3308      // subset of the identifiers for this particular method.
3309      if (!isAcceptableObjCMethod(*M, WantKind, SelIdents, NumSelIdents))
3310        continue;
3311
3312      Result R = Result(*M, 0);
3313      R.StartParameter = NumSelIdents;
3314      R.AllParametersAreInformative = (WantKind != MK_Any);
3315      Results.MaybeAddResult(R, CurContext);
3316    }
3317  }
3318
3319  ObjCInterfaceDecl *IFace = dyn_cast<ObjCInterfaceDecl>(Container);
3320  if (!IFace)
3321    return;
3322
3323  // Add methods in protocols.
3324  const ObjCList<ObjCProtocolDecl> &Protocols= IFace->getReferencedProtocols();
3325  for (ObjCList<ObjCProtocolDecl>::iterator I = Protocols.begin(),
3326                                            E = Protocols.end();
3327       I != E; ++I)
3328    AddObjCMethods(*I, WantInstanceMethods, WantKind, SelIdents, NumSelIdents,
3329                   CurContext, Results);
3330
3331  // Add methods in categories.
3332  for (ObjCCategoryDecl *CatDecl = IFace->getCategoryList(); CatDecl;
3333       CatDecl = CatDecl->getNextClassCategory()) {
3334    AddObjCMethods(CatDecl, WantInstanceMethods, WantKind, SelIdents,
3335                   NumSelIdents, CurContext, Results);
3336
3337    // Add a categories protocol methods.
3338    const ObjCList<ObjCProtocolDecl> &Protocols
3339      = CatDecl->getReferencedProtocols();
3340    for (ObjCList<ObjCProtocolDecl>::iterator I = Protocols.begin(),
3341                                              E = Protocols.end();
3342         I != E; ++I)
3343      AddObjCMethods(*I, WantInstanceMethods, WantKind, SelIdents,
3344                     NumSelIdents, CurContext, Results);
3345
3346    // Add methods in category implementations.
3347    if (ObjCCategoryImplDecl *Impl = CatDecl->getImplementation())
3348      AddObjCMethods(Impl, WantInstanceMethods, WantKind, SelIdents,
3349                     NumSelIdents, CurContext, Results);
3350  }
3351
3352  // Add methods in superclass.
3353  if (IFace->getSuperClass())
3354    AddObjCMethods(IFace->getSuperClass(), WantInstanceMethods, WantKind,
3355                   SelIdents, NumSelIdents, CurContext, Results);
3356
3357  // Add methods in our implementation, if any.
3358  if (ObjCImplementationDecl *Impl = IFace->getImplementation())
3359    AddObjCMethods(Impl, WantInstanceMethods, WantKind, SelIdents,
3360                   NumSelIdents, CurContext, Results);
3361}
3362
3363
3364void Sema::CodeCompleteObjCPropertyGetter(Scope *S, DeclPtrTy ClassDecl,
3365                                          DeclPtrTy *Methods,
3366                                          unsigned NumMethods) {
3367  typedef CodeCompleteConsumer::Result Result;
3368
3369  // Try to find the interface where getters might live.
3370  ObjCInterfaceDecl *Class
3371    = dyn_cast_or_null<ObjCInterfaceDecl>(ClassDecl.getAs<Decl>());
3372  if (!Class) {
3373    if (ObjCCategoryDecl *Category
3374          = dyn_cast_or_null<ObjCCategoryDecl>(ClassDecl.getAs<Decl>()))
3375      Class = Category->getClassInterface();
3376
3377    if (!Class)
3378      return;
3379  }
3380
3381  // Find all of the potential getters.
3382  ResultBuilder Results(*this);
3383  Results.EnterNewScope();
3384
3385  // FIXME: We need to do this because Objective-C methods don't get
3386  // pushed into DeclContexts early enough. Argh!
3387  for (unsigned I = 0; I != NumMethods; ++I) {
3388    if (ObjCMethodDecl *Method
3389            = dyn_cast_or_null<ObjCMethodDecl>(Methods[I].getAs<Decl>()))
3390      if (Method->isInstanceMethod() &&
3391          isAcceptableObjCMethod(Method, MK_ZeroArgSelector, 0, 0)) {
3392        Result R = Result(Method, 0);
3393        R.AllParametersAreInformative = true;
3394        Results.MaybeAddResult(R, CurContext);
3395      }
3396  }
3397
3398  AddObjCMethods(Class, true, MK_ZeroArgSelector, 0, 0, CurContext, Results);
3399  Results.ExitScope();
3400  HandleCodeCompleteResults(this, CodeCompleter,
3401                            CodeCompletionContext::CCC_Other,
3402                            Results.data(),Results.size());
3403}
3404
3405void Sema::CodeCompleteObjCPropertySetter(Scope *S, DeclPtrTy ObjCImplDecl,
3406                                          DeclPtrTy *Methods,
3407                                          unsigned NumMethods) {
3408  typedef CodeCompleteConsumer::Result Result;
3409
3410  // Try to find the interface where setters might live.
3411  ObjCInterfaceDecl *Class
3412    = dyn_cast_or_null<ObjCInterfaceDecl>(ObjCImplDecl.getAs<Decl>());
3413  if (!Class) {
3414    if (ObjCCategoryDecl *Category
3415          = dyn_cast_or_null<ObjCCategoryDecl>(ObjCImplDecl.getAs<Decl>()))
3416      Class = Category->getClassInterface();
3417
3418    if (!Class)
3419      return;
3420  }
3421
3422  // Find all of the potential getters.
3423  ResultBuilder Results(*this);
3424  Results.EnterNewScope();
3425
3426  // FIXME: We need to do this because Objective-C methods don't get
3427  // pushed into DeclContexts early enough. Argh!
3428  for (unsigned I = 0; I != NumMethods; ++I) {
3429    if (ObjCMethodDecl *Method
3430            = dyn_cast_or_null<ObjCMethodDecl>(Methods[I].getAs<Decl>()))
3431      if (Method->isInstanceMethod() &&
3432          isAcceptableObjCMethod(Method, MK_OneArgSelector, 0, 0)) {
3433        Result R = Result(Method, 0);
3434        R.AllParametersAreInformative = true;
3435        Results.MaybeAddResult(R, CurContext);
3436      }
3437  }
3438
3439  AddObjCMethods(Class, true, MK_OneArgSelector, 0, 0, CurContext, Results);
3440
3441  Results.ExitScope();
3442  HandleCodeCompleteResults(this, CodeCompleter,
3443                            CodeCompletionContext::CCC_Other,
3444                            Results.data(),Results.size());
3445}
3446
3447/// \brief When we have an expression with type "id", we may assume
3448/// that it has some more-specific class type based on knowledge of
3449/// common uses of Objective-C. This routine returns that class type,
3450/// or NULL if no better result could be determined.
3451static ObjCInterfaceDecl *GetAssumedMessageSendExprType(Expr *E) {
3452  ObjCMessageExpr *Msg = dyn_cast<ObjCMessageExpr>(E);
3453  if (!Msg)
3454    return 0;
3455
3456  Selector Sel = Msg->getSelector();
3457  if (Sel.isNull())
3458    return 0;
3459
3460  IdentifierInfo *Id = Sel.getIdentifierInfoForSlot(0);
3461  if (!Id)
3462    return 0;
3463
3464  ObjCMethodDecl *Method = Msg->getMethodDecl();
3465  if (!Method)
3466    return 0;
3467
3468  // Determine the class that we're sending the message to.
3469  ObjCInterfaceDecl *IFace = 0;
3470  switch (Msg->getReceiverKind()) {
3471  case ObjCMessageExpr::Class:
3472    if (const ObjCObjectType *ObjType
3473                           = Msg->getClassReceiver()->getAs<ObjCObjectType>())
3474      IFace = ObjType->getInterface();
3475    break;
3476
3477  case ObjCMessageExpr::Instance: {
3478    QualType T = Msg->getInstanceReceiver()->getType();
3479    if (const ObjCObjectPointerType *Ptr = T->getAs<ObjCObjectPointerType>())
3480      IFace = Ptr->getInterfaceDecl();
3481    break;
3482  }
3483
3484  case ObjCMessageExpr::SuperInstance:
3485  case ObjCMessageExpr::SuperClass:
3486    break;
3487  }
3488
3489  if (!IFace)
3490    return 0;
3491
3492  ObjCInterfaceDecl *Super = IFace->getSuperClass();
3493  if (Method->isInstanceMethod())
3494    return llvm::StringSwitch<ObjCInterfaceDecl *>(Id->getName())
3495      .Case("retain", IFace)
3496      .Case("autorelease", IFace)
3497      .Case("copy", IFace)
3498      .Case("copyWithZone", IFace)
3499      .Case("mutableCopy", IFace)
3500      .Case("mutableCopyWithZone", IFace)
3501      .Case("awakeFromCoder", IFace)
3502      .Case("replacementObjectFromCoder", IFace)
3503      .Case("class", IFace)
3504      .Case("classForCoder", IFace)
3505      .Case("superclass", Super)
3506      .Default(0);
3507
3508  return llvm::StringSwitch<ObjCInterfaceDecl *>(Id->getName())
3509    .Case("new", IFace)
3510    .Case("alloc", IFace)
3511    .Case("allocWithZone", IFace)
3512    .Case("class", IFace)
3513    .Case("superclass", Super)
3514    .Default(0);
3515}
3516
3517void Sema::CodeCompleteObjCMessageReceiver(Scope *S) {
3518  typedef CodeCompleteConsumer::Result Result;
3519  ResultBuilder Results(*this);
3520
3521  // Find anything that looks like it could be a message receiver.
3522  Results.setFilter(&ResultBuilder::IsObjCMessageReceiver);
3523  CodeCompletionDeclConsumer Consumer(Results, CurContext);
3524  Results.EnterNewScope();
3525  LookupVisibleDecls(S, LookupOrdinaryName, Consumer,
3526                     CodeCompleter->includeGlobals());
3527
3528  // If we are in an Objective-C method inside a class that has a superclass,
3529  // add "super" as an option.
3530  if (ObjCMethodDecl *Method = getCurMethodDecl())
3531    if (ObjCInterfaceDecl *Iface = Method->getClassInterface())
3532      if (Iface->getSuperClass())
3533        Results.AddResult(Result("super"));
3534
3535  Results.ExitScope();
3536
3537  if (CodeCompleter->includeMacros())
3538    AddMacroResults(PP, Results);
3539  HandleCodeCompleteResults(this, CodeCompleter,
3540                            CodeCompletionContext::CCC_ObjCMessageReceiver,
3541                            Results.data(), Results.size());
3542
3543}
3544
3545void Sema::CodeCompleteObjCSuperMessage(Scope *S, SourceLocation SuperLoc,
3546                                        IdentifierInfo **SelIdents,
3547                                        unsigned NumSelIdents) {
3548  ObjCInterfaceDecl *CDecl = 0;
3549  if (ObjCMethodDecl *CurMethod = getCurMethodDecl()) {
3550    // Figure out which interface we're in.
3551    CDecl = CurMethod->getClassInterface();
3552    if (!CDecl)
3553      return;
3554
3555    // Find the superclass of this class.
3556    CDecl = CDecl->getSuperClass();
3557    if (!CDecl)
3558      return;
3559
3560    if (CurMethod->isInstanceMethod()) {
3561      // We are inside an instance method, which means that the message
3562      // send [super ...] is actually calling an instance method on the
3563      // current object. Build the super expression and handle this like
3564      // an instance method.
3565      QualType SuperTy = Context.getObjCInterfaceType(CDecl);
3566      SuperTy = Context.getObjCObjectPointerType(SuperTy);
3567      OwningExprResult Super
3568        = Owned(new (Context) ObjCSuperExpr(SuperLoc, SuperTy));
3569      return CodeCompleteObjCInstanceMessage(S, (Expr *)Super.get(),
3570                                             SelIdents, NumSelIdents);
3571    }
3572
3573    // Fall through to send to the superclass in CDecl.
3574  } else {
3575    // "super" may be the name of a type or variable. Figure out which
3576    // it is.
3577    IdentifierInfo *Super = &Context.Idents.get("super");
3578    NamedDecl *ND = LookupSingleName(S, Super, SuperLoc,
3579                                     LookupOrdinaryName);
3580    if ((CDecl = dyn_cast_or_null<ObjCInterfaceDecl>(ND))) {
3581      // "super" names an interface. Use it.
3582    } else if (TypeDecl *TD = dyn_cast_or_null<TypeDecl>(ND)) {
3583      if (const ObjCObjectType *Iface
3584            = Context.getTypeDeclType(TD)->getAs<ObjCObjectType>())
3585        CDecl = Iface->getInterface();
3586    } else if (ND && isa<UnresolvedUsingTypenameDecl>(ND)) {
3587      // "super" names an unresolved type; we can't be more specific.
3588    } else {
3589      // Assume that "super" names some kind of value and parse that way.
3590      CXXScopeSpec SS;
3591      UnqualifiedId id;
3592      id.setIdentifier(Super, SuperLoc);
3593      OwningExprResult SuperExpr = ActOnIdExpression(S, SS, id, false, false);
3594      return CodeCompleteObjCInstanceMessage(S, (Expr *)SuperExpr.get(),
3595                                             SelIdents, NumSelIdents);
3596    }
3597
3598    // Fall through
3599  }
3600
3601  TypeTy *Receiver = 0;
3602  if (CDecl)
3603    Receiver = Context.getObjCInterfaceType(CDecl).getAsOpaquePtr();
3604  return CodeCompleteObjCClassMessage(S, Receiver, SelIdents,
3605                                      NumSelIdents);
3606}
3607
3608void Sema::CodeCompleteObjCClassMessage(Scope *S, TypeTy *Receiver,
3609                                        IdentifierInfo **SelIdents,
3610                                        unsigned NumSelIdents) {
3611  typedef CodeCompleteConsumer::Result Result;
3612  ObjCInterfaceDecl *CDecl = 0;
3613
3614  // If the given name refers to an interface type, retrieve the
3615  // corresponding declaration.
3616  if (Receiver) {
3617    QualType T = GetTypeFromParser(Receiver, 0);
3618    if (!T.isNull())
3619      if (const ObjCObjectType *Interface = T->getAs<ObjCObjectType>())
3620        CDecl = Interface->getInterface();
3621  }
3622
3623  // Add all of the factory methods in this Objective-C class, its protocols,
3624  // superclasses, categories, implementation, etc.
3625  ResultBuilder Results(*this);
3626  Results.EnterNewScope();
3627
3628  if (CDecl)
3629    AddObjCMethods(CDecl, false, MK_Any, SelIdents, NumSelIdents, CurContext,
3630                   Results);
3631  else {
3632    // We're messaging "id" as a type; provide all class/factory methods.
3633
3634    // If we have an external source, load the entire class method
3635    // pool from the PCH file.
3636    if (ExternalSource) {
3637      for (uint32_t I = 0, N = ExternalSource->GetNumExternalSelectors();
3638           I != N; ++I) {
3639        Selector Sel = ExternalSource->GetExternalSelector(I);
3640        if (Sel.isNull() || MethodPool.count(Sel))
3641          continue;
3642
3643        ReadMethodPool(Sel);
3644      }
3645    }
3646
3647    for (GlobalMethodPool::iterator M = MethodPool.begin(),
3648                                    MEnd = MethodPool.end();
3649         M != MEnd; ++M) {
3650      for (ObjCMethodList *MethList = &M->second.second;
3651           MethList && MethList->Method;
3652           MethList = MethList->Next) {
3653        if (!isAcceptableObjCMethod(MethList->Method, MK_Any, SelIdents,
3654                                    NumSelIdents))
3655          continue;
3656
3657        Result R(MethList->Method, 0);
3658        R.StartParameter = NumSelIdents;
3659        R.AllParametersAreInformative = false;
3660        Results.MaybeAddResult(R, CurContext);
3661      }
3662    }
3663  }
3664
3665  Results.ExitScope();
3666  HandleCodeCompleteResults(this, CodeCompleter,
3667                            CodeCompletionContext::CCC_Other,
3668                            Results.data(),Results.size());
3669}
3670
3671void Sema::CodeCompleteObjCInstanceMessage(Scope *S, ExprTy *Receiver,
3672                                           IdentifierInfo **SelIdents,
3673                                           unsigned NumSelIdents) {
3674  typedef CodeCompleteConsumer::Result Result;
3675
3676  Expr *RecExpr = static_cast<Expr *>(Receiver);
3677
3678  // If necessary, apply function/array conversion to the receiver.
3679  // C99 6.7.5.3p[7,8].
3680  DefaultFunctionArrayLvalueConversion(RecExpr);
3681  QualType ReceiverType = RecExpr->getType();
3682
3683  // Build the set of methods we can see.
3684  ResultBuilder Results(*this);
3685  Results.EnterNewScope();
3686
3687  // If we're messaging an expression with type "id" or "Class", check
3688  // whether we know something special about the receiver that allows
3689  // us to assume a more-specific receiver type.
3690  if (ReceiverType->isObjCIdType() || ReceiverType->isObjCClassType())
3691    if (ObjCInterfaceDecl *IFace = GetAssumedMessageSendExprType(RecExpr))
3692      ReceiverType = Context.getObjCObjectPointerType(
3693                                          Context.getObjCInterfaceType(IFace));
3694
3695  // Handle messages to Class. This really isn't a message to an instance
3696  // method, so we treat it the same way we would treat a message send to a
3697  // class method.
3698  if (ReceiverType->isObjCClassType() ||
3699      ReceiverType->isObjCQualifiedClassType()) {
3700    if (ObjCMethodDecl *CurMethod = getCurMethodDecl()) {
3701      if (ObjCInterfaceDecl *ClassDecl = CurMethod->getClassInterface())
3702        AddObjCMethods(ClassDecl, false, MK_Any, SelIdents, NumSelIdents,
3703                       CurContext, Results);
3704    }
3705  }
3706  // Handle messages to a qualified ID ("id<foo>").
3707  else if (const ObjCObjectPointerType *QualID
3708             = ReceiverType->getAsObjCQualifiedIdType()) {
3709    // Search protocols for instance methods.
3710    for (ObjCObjectPointerType::qual_iterator I = QualID->qual_begin(),
3711                                              E = QualID->qual_end();
3712         I != E; ++I)
3713      AddObjCMethods(*I, true, MK_Any, SelIdents, NumSelIdents, CurContext,
3714                     Results);
3715  }
3716  // Handle messages to a pointer to interface type.
3717  else if (const ObjCObjectPointerType *IFacePtr
3718                              = ReceiverType->getAsObjCInterfacePointerType()) {
3719    // Search the class, its superclasses, etc., for instance methods.
3720    AddObjCMethods(IFacePtr->getInterfaceDecl(), true, MK_Any, SelIdents,
3721                   NumSelIdents, CurContext, Results);
3722
3723    // Search protocols for instance methods.
3724    for (ObjCObjectPointerType::qual_iterator I = IFacePtr->qual_begin(),
3725         E = IFacePtr->qual_end();
3726         I != E; ++I)
3727      AddObjCMethods(*I, true, MK_Any, SelIdents, NumSelIdents, CurContext,
3728                     Results);
3729  }
3730  // Handle messages to "id".
3731  else if (ReceiverType->isObjCIdType()) {
3732    // We're messaging "id", so provide all instance methods we know
3733    // about as code-completion results.
3734
3735    // If we have an external source, load the entire class method
3736    // pool from the PCH file.
3737    if (ExternalSource) {
3738      for (uint32_t I = 0, N = ExternalSource->GetNumExternalSelectors();
3739           I != N; ++I) {
3740        Selector Sel = ExternalSource->GetExternalSelector(I);
3741        if (Sel.isNull() || MethodPool.count(Sel))
3742          continue;
3743
3744        ReadMethodPool(Sel);
3745      }
3746    }
3747
3748    for (GlobalMethodPool::iterator M = MethodPool.begin(),
3749                                    MEnd = MethodPool.end();
3750         M != MEnd; ++M) {
3751      for (ObjCMethodList *MethList = &M->second.first;
3752           MethList && MethList->Method;
3753           MethList = MethList->Next) {
3754        if (!isAcceptableObjCMethod(MethList->Method, MK_Any, SelIdents,
3755                                    NumSelIdents))
3756          continue;
3757
3758        Result R(MethList->Method, 0);
3759        R.StartParameter = NumSelIdents;
3760        R.AllParametersAreInformative = false;
3761        Results.MaybeAddResult(R, CurContext);
3762      }
3763    }
3764  }
3765
3766  Results.ExitScope();
3767  HandleCodeCompleteResults(this, CodeCompleter,
3768                            CodeCompletionContext::CCC_Other,
3769                            Results.data(),Results.size());
3770}
3771
3772/// \brief Add all of the protocol declarations that we find in the given
3773/// (translation unit) context.
3774static void AddProtocolResults(DeclContext *Ctx, DeclContext *CurContext,
3775                               bool OnlyForwardDeclarations,
3776                               ResultBuilder &Results) {
3777  typedef CodeCompleteConsumer::Result Result;
3778
3779  for (DeclContext::decl_iterator D = Ctx->decls_begin(),
3780                               DEnd = Ctx->decls_end();
3781       D != DEnd; ++D) {
3782    // Record any protocols we find.
3783    if (ObjCProtocolDecl *Proto = dyn_cast<ObjCProtocolDecl>(*D))
3784      if (!OnlyForwardDeclarations || Proto->isForwardDecl())
3785        Results.AddResult(Result(Proto, 0), CurContext, 0, false);
3786
3787    // Record any forward-declared protocols we find.
3788    if (ObjCForwardProtocolDecl *Forward
3789          = dyn_cast<ObjCForwardProtocolDecl>(*D)) {
3790      for (ObjCForwardProtocolDecl::protocol_iterator
3791             P = Forward->protocol_begin(),
3792             PEnd = Forward->protocol_end();
3793           P != PEnd; ++P)
3794        if (!OnlyForwardDeclarations || (*P)->isForwardDecl())
3795          Results.AddResult(Result(*P, 0), CurContext, 0, false);
3796    }
3797  }
3798}
3799
3800void Sema::CodeCompleteObjCProtocolReferences(IdentifierLocPair *Protocols,
3801                                              unsigned NumProtocols) {
3802  ResultBuilder Results(*this);
3803  Results.EnterNewScope();
3804
3805  // Tell the result set to ignore all of the protocols we have
3806  // already seen.
3807  for (unsigned I = 0; I != NumProtocols; ++I)
3808    if (ObjCProtocolDecl *Protocol = LookupProtocol(Protocols[I].first,
3809                                                    Protocols[I].second))
3810      Results.Ignore(Protocol);
3811
3812  // Add all protocols.
3813  AddProtocolResults(Context.getTranslationUnitDecl(), CurContext, false,
3814                     Results);
3815
3816  Results.ExitScope();
3817  HandleCodeCompleteResults(this, CodeCompleter,
3818                            CodeCompletionContext::CCC_ObjCProtocolName,
3819                            Results.data(),Results.size());
3820}
3821
3822void Sema::CodeCompleteObjCProtocolDecl(Scope *) {
3823  ResultBuilder Results(*this);
3824  Results.EnterNewScope();
3825
3826  // Add all protocols.
3827  AddProtocolResults(Context.getTranslationUnitDecl(), CurContext, true,
3828                     Results);
3829
3830  Results.ExitScope();
3831  HandleCodeCompleteResults(this, CodeCompleter,
3832                            CodeCompletionContext::CCC_ObjCProtocolName,
3833                            Results.data(),Results.size());
3834}
3835
3836/// \brief Add all of the Objective-C interface declarations that we find in
3837/// the given (translation unit) context.
3838static void AddInterfaceResults(DeclContext *Ctx, DeclContext *CurContext,
3839                                bool OnlyForwardDeclarations,
3840                                bool OnlyUnimplemented,
3841                                ResultBuilder &Results) {
3842  typedef CodeCompleteConsumer::Result Result;
3843
3844  for (DeclContext::decl_iterator D = Ctx->decls_begin(),
3845                               DEnd = Ctx->decls_end();
3846       D != DEnd; ++D) {
3847    // Record any interfaces we find.
3848    if (ObjCInterfaceDecl *Class = dyn_cast<ObjCInterfaceDecl>(*D))
3849      if ((!OnlyForwardDeclarations || Class->isForwardDecl()) &&
3850          (!OnlyUnimplemented || !Class->getImplementation()))
3851        Results.AddResult(Result(Class, 0), CurContext, 0, false);
3852
3853    // Record any forward-declared interfaces we find.
3854    if (ObjCClassDecl *Forward = dyn_cast<ObjCClassDecl>(*D)) {
3855      for (ObjCClassDecl::iterator C = Forward->begin(), CEnd = Forward->end();
3856           C != CEnd; ++C)
3857        if ((!OnlyForwardDeclarations || C->getInterface()->isForwardDecl()) &&
3858            (!OnlyUnimplemented || !C->getInterface()->getImplementation()))
3859          Results.AddResult(Result(C->getInterface(), 0), CurContext,
3860                            0, false);
3861    }
3862  }
3863}
3864
3865void Sema::CodeCompleteObjCInterfaceDecl(Scope *S) {
3866  ResultBuilder Results(*this);
3867  Results.EnterNewScope();
3868
3869  // Add all classes.
3870  AddInterfaceResults(Context.getTranslationUnitDecl(), CurContext, true,
3871                      false, Results);
3872
3873  Results.ExitScope();
3874  HandleCodeCompleteResults(this, CodeCompleter,
3875                            CodeCompletionContext::CCC_Other,
3876                            Results.data(),Results.size());
3877}
3878
3879void Sema::CodeCompleteObjCSuperclass(Scope *S, IdentifierInfo *ClassName,
3880                                      SourceLocation ClassNameLoc) {
3881  ResultBuilder Results(*this);
3882  Results.EnterNewScope();
3883
3884  // Make sure that we ignore the class we're currently defining.
3885  NamedDecl *CurClass
3886    = LookupSingleName(TUScope, ClassName, ClassNameLoc, LookupOrdinaryName);
3887  if (CurClass && isa<ObjCInterfaceDecl>(CurClass))
3888    Results.Ignore(CurClass);
3889
3890  // Add all classes.
3891  AddInterfaceResults(Context.getTranslationUnitDecl(), CurContext, false,
3892                      false, Results);
3893
3894  Results.ExitScope();
3895  HandleCodeCompleteResults(this, CodeCompleter,
3896                            CodeCompletionContext::CCC_Other,
3897                            Results.data(),Results.size());
3898}
3899
3900void Sema::CodeCompleteObjCImplementationDecl(Scope *S) {
3901  ResultBuilder Results(*this);
3902  Results.EnterNewScope();
3903
3904  // Add all unimplemented classes.
3905  AddInterfaceResults(Context.getTranslationUnitDecl(), CurContext, false,
3906                      true, Results);
3907
3908  Results.ExitScope();
3909  HandleCodeCompleteResults(this, CodeCompleter,
3910                            CodeCompletionContext::CCC_Other,
3911                            Results.data(),Results.size());
3912}
3913
3914void Sema::CodeCompleteObjCInterfaceCategory(Scope *S,
3915                                             IdentifierInfo *ClassName,
3916                                             SourceLocation ClassNameLoc) {
3917  typedef CodeCompleteConsumer::Result Result;
3918
3919  ResultBuilder Results(*this);
3920
3921  // Ignore any categories we find that have already been implemented by this
3922  // interface.
3923  llvm::SmallPtrSet<IdentifierInfo *, 16> CategoryNames;
3924  NamedDecl *CurClass
3925    = LookupSingleName(TUScope, ClassName, ClassNameLoc, LookupOrdinaryName);
3926  if (ObjCInterfaceDecl *Class = dyn_cast_or_null<ObjCInterfaceDecl>(CurClass))
3927    for (ObjCCategoryDecl *Category = Class->getCategoryList(); Category;
3928         Category = Category->getNextClassCategory())
3929      CategoryNames.insert(Category->getIdentifier());
3930
3931  // Add all of the categories we know about.
3932  Results.EnterNewScope();
3933  TranslationUnitDecl *TU = Context.getTranslationUnitDecl();
3934  for (DeclContext::decl_iterator D = TU->decls_begin(),
3935                               DEnd = TU->decls_end();
3936       D != DEnd; ++D)
3937    if (ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(*D))
3938      if (CategoryNames.insert(Category->getIdentifier()))
3939        Results.AddResult(Result(Category, 0), CurContext, 0, false);
3940  Results.ExitScope();
3941
3942  HandleCodeCompleteResults(this, CodeCompleter,
3943                            CodeCompletionContext::CCC_Other,
3944                            Results.data(),Results.size());
3945}
3946
3947void Sema::CodeCompleteObjCImplementationCategory(Scope *S,
3948                                                  IdentifierInfo *ClassName,
3949                                                  SourceLocation ClassNameLoc) {
3950  typedef CodeCompleteConsumer::Result Result;
3951
3952  // Find the corresponding interface. If we couldn't find the interface, the
3953  // program itself is ill-formed. However, we'll try to be helpful still by
3954  // providing the list of all of the categories we know about.
3955  NamedDecl *CurClass
3956    = LookupSingleName(TUScope, ClassName, ClassNameLoc, LookupOrdinaryName);
3957  ObjCInterfaceDecl *Class = dyn_cast_or_null<ObjCInterfaceDecl>(CurClass);
3958  if (!Class)
3959    return CodeCompleteObjCInterfaceCategory(S, ClassName, ClassNameLoc);
3960
3961  ResultBuilder Results(*this);
3962
3963  // Add all of the categories that have have corresponding interface
3964  // declarations in this class and any of its superclasses, except for
3965  // already-implemented categories in the class itself.
3966  llvm::SmallPtrSet<IdentifierInfo *, 16> CategoryNames;
3967  Results.EnterNewScope();
3968  bool IgnoreImplemented = true;
3969  while (Class) {
3970    for (ObjCCategoryDecl *Category = Class->getCategoryList(); Category;
3971         Category = Category->getNextClassCategory())
3972      if ((!IgnoreImplemented || !Category->getImplementation()) &&
3973          CategoryNames.insert(Category->getIdentifier()))
3974        Results.AddResult(Result(Category, 0), CurContext, 0, false);
3975
3976    Class = Class->getSuperClass();
3977    IgnoreImplemented = false;
3978  }
3979  Results.ExitScope();
3980
3981  HandleCodeCompleteResults(this, CodeCompleter,
3982                            CodeCompletionContext::CCC_Other,
3983                            Results.data(),Results.size());
3984}
3985
3986void Sema::CodeCompleteObjCPropertyDefinition(Scope *S, DeclPtrTy ObjCImpDecl) {
3987  typedef CodeCompleteConsumer::Result Result;
3988  ResultBuilder Results(*this);
3989
3990  // Figure out where this @synthesize lives.
3991  ObjCContainerDecl *Container
3992    = dyn_cast_or_null<ObjCContainerDecl>(ObjCImpDecl.getAs<Decl>());
3993  if (!Container ||
3994      (!isa<ObjCImplementationDecl>(Container) &&
3995       !isa<ObjCCategoryImplDecl>(Container)))
3996    return;
3997
3998  // Ignore any properties that have already been implemented.
3999  for (DeclContext::decl_iterator D = Container->decls_begin(),
4000                               DEnd = Container->decls_end();
4001       D != DEnd; ++D)
4002    if (ObjCPropertyImplDecl *PropertyImpl = dyn_cast<ObjCPropertyImplDecl>(*D))
4003      Results.Ignore(PropertyImpl->getPropertyDecl());
4004
4005  // Add any properties that we find.
4006  Results.EnterNewScope();
4007  if (ObjCImplementationDecl *ClassImpl
4008        = dyn_cast<ObjCImplementationDecl>(Container))
4009    AddObjCProperties(ClassImpl->getClassInterface(), false, CurContext,
4010                      Results);
4011  else
4012    AddObjCProperties(cast<ObjCCategoryImplDecl>(Container)->getCategoryDecl(),
4013                      false, CurContext, Results);
4014  Results.ExitScope();
4015
4016  HandleCodeCompleteResults(this, CodeCompleter,
4017                            CodeCompletionContext::CCC_Other,
4018                            Results.data(),Results.size());
4019}
4020
4021void Sema::CodeCompleteObjCPropertySynthesizeIvar(Scope *S,
4022                                                  IdentifierInfo *PropertyName,
4023                                                  DeclPtrTy ObjCImpDecl) {
4024  typedef CodeCompleteConsumer::Result Result;
4025  ResultBuilder Results(*this);
4026
4027  // Figure out where this @synthesize lives.
4028  ObjCContainerDecl *Container
4029    = dyn_cast_or_null<ObjCContainerDecl>(ObjCImpDecl.getAs<Decl>());
4030  if (!Container ||
4031      (!isa<ObjCImplementationDecl>(Container) &&
4032       !isa<ObjCCategoryImplDecl>(Container)))
4033    return;
4034
4035  // Figure out which interface we're looking into.
4036  ObjCInterfaceDecl *Class = 0;
4037  if (ObjCImplementationDecl *ClassImpl
4038                                 = dyn_cast<ObjCImplementationDecl>(Container))
4039    Class = ClassImpl->getClassInterface();
4040  else
4041    Class = cast<ObjCCategoryImplDecl>(Container)->getCategoryDecl()
4042                                                          ->getClassInterface();
4043
4044  // Add all of the instance variables in this class and its superclasses.
4045  Results.EnterNewScope();
4046  for(; Class; Class = Class->getSuperClass()) {
4047    // FIXME: We could screen the type of each ivar for compatibility with
4048    // the property, but is that being too paternal?
4049    for (ObjCInterfaceDecl::ivar_iterator IVar = Class->ivar_begin(),
4050                                       IVarEnd = Class->ivar_end();
4051         IVar != IVarEnd; ++IVar)
4052      Results.AddResult(Result(*IVar, 0), CurContext, 0, false);
4053  }
4054  Results.ExitScope();
4055
4056  HandleCodeCompleteResults(this, CodeCompleter,
4057                            CodeCompletionContext::CCC_Other,
4058                            Results.data(),Results.size());
4059}
4060
4061typedef llvm::DenseMap<Selector, ObjCMethodDecl *> KnownMethodsMap;
4062
4063/// \brief Find all of the methods that reside in the given container
4064/// (and its superclasses, protocols, etc.) that meet the given
4065/// criteria. Insert those methods into the map of known methods,
4066/// indexed by selector so they can be easily found.
4067static void FindImplementableMethods(ASTContext &Context,
4068                                     ObjCContainerDecl *Container,
4069                                     bool WantInstanceMethods,
4070                                     QualType ReturnType,
4071                                     bool IsInImplementation,
4072                                     KnownMethodsMap &KnownMethods) {
4073  if (ObjCInterfaceDecl *IFace = dyn_cast<ObjCInterfaceDecl>(Container)) {
4074    // Recurse into protocols.
4075    const ObjCList<ObjCProtocolDecl> &Protocols
4076      = IFace->getReferencedProtocols();
4077    for (ObjCList<ObjCProtocolDecl>::iterator I = Protocols.begin(),
4078           E = Protocols.end();
4079         I != E; ++I)
4080      FindImplementableMethods(Context, *I, WantInstanceMethods, ReturnType,
4081                               IsInImplementation, KnownMethods);
4082
4083    // If we're not in the implementation of a class, also visit the
4084    // superclass.
4085    if (!IsInImplementation && IFace->getSuperClass())
4086      FindImplementableMethods(Context, IFace->getSuperClass(),
4087                               WantInstanceMethods, ReturnType,
4088                               IsInImplementation, KnownMethods);
4089
4090    // Add methods from any class extensions (but not from categories;
4091    // those should go into category implementations).
4092    for (const ObjCCategoryDecl *Cat = IFace->getFirstClassExtension(); Cat;
4093         Cat = Cat->getNextClassExtension())
4094      FindImplementableMethods(Context, const_cast<ObjCCategoryDecl*>(Cat),
4095                               WantInstanceMethods, ReturnType,
4096                               IsInImplementation, KnownMethods);
4097  }
4098
4099  if (ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(Container)) {
4100    // Recurse into protocols.
4101    const ObjCList<ObjCProtocolDecl> &Protocols
4102      = Category->getReferencedProtocols();
4103    for (ObjCList<ObjCProtocolDecl>::iterator I = Protocols.begin(),
4104           E = Protocols.end();
4105         I != E; ++I)
4106      FindImplementableMethods(Context, *I, WantInstanceMethods, ReturnType,
4107                               IsInImplementation, KnownMethods);
4108  }
4109
4110  if (ObjCProtocolDecl *Protocol = dyn_cast<ObjCProtocolDecl>(Container)) {
4111    // Recurse into protocols.
4112    const ObjCList<ObjCProtocolDecl> &Protocols
4113      = Protocol->getReferencedProtocols();
4114    for (ObjCList<ObjCProtocolDecl>::iterator I = Protocols.begin(),
4115           E = Protocols.end();
4116         I != E; ++I)
4117      FindImplementableMethods(Context, *I, WantInstanceMethods, ReturnType,
4118                               IsInImplementation, KnownMethods);
4119  }
4120
4121  // Add methods in this container. This operation occurs last because
4122  // we want the methods from this container to override any methods
4123  // we've previously seen with the same selector.
4124  for (ObjCContainerDecl::method_iterator M = Container->meth_begin(),
4125                                       MEnd = Container->meth_end();
4126       M != MEnd; ++M) {
4127    if ((*M)->isInstanceMethod() == WantInstanceMethods) {
4128      if (!ReturnType.isNull() &&
4129          !Context.hasSameUnqualifiedType(ReturnType, (*M)->getResultType()))
4130        continue;
4131
4132      KnownMethods[(*M)->getSelector()] = *M;
4133    }
4134  }
4135}
4136
4137void Sema::CodeCompleteObjCMethodDecl(Scope *S,
4138                                      bool IsInstanceMethod,
4139                                      TypeTy *ReturnTy,
4140                                      DeclPtrTy IDecl) {
4141  // Determine the return type of the method we're declaring, if
4142  // provided.
4143  QualType ReturnType = GetTypeFromParser(ReturnTy);
4144
4145  // Determine where we should start searching for methods, and where we
4146  ObjCContainerDecl *SearchDecl = 0, *CurrentDecl = 0;
4147  bool IsInImplementation = false;
4148  if (Decl *D = IDecl.getAs<Decl>()) {
4149    if (ObjCImplementationDecl *Impl = dyn_cast<ObjCImplementationDecl>(D)) {
4150      SearchDecl = Impl->getClassInterface();
4151      CurrentDecl = Impl;
4152      IsInImplementation = true;
4153    } else if (ObjCCategoryImplDecl *CatImpl
4154                                       = dyn_cast<ObjCCategoryImplDecl>(D)) {
4155      SearchDecl = CatImpl->getCategoryDecl();
4156      CurrentDecl = CatImpl;
4157      IsInImplementation = true;
4158    } else {
4159      SearchDecl = dyn_cast<ObjCContainerDecl>(D);
4160      CurrentDecl = SearchDecl;
4161    }
4162  }
4163
4164  if (!SearchDecl && S) {
4165    if (DeclContext *DC = static_cast<DeclContext *>(S->getEntity())) {
4166      SearchDecl = dyn_cast<ObjCContainerDecl>(DC);
4167      CurrentDecl = SearchDecl;
4168    }
4169  }
4170
4171  if (!SearchDecl || !CurrentDecl) {
4172    HandleCodeCompleteResults(this, CodeCompleter,
4173                              CodeCompletionContext::CCC_Other,
4174                              0, 0);
4175    return;
4176  }
4177
4178  // Find all of the methods that we could declare/implement here.
4179  KnownMethodsMap KnownMethods;
4180  FindImplementableMethods(Context, SearchDecl, IsInstanceMethod,
4181                           ReturnType, IsInImplementation, KnownMethods);
4182
4183  // Erase any methods that have already been declared or
4184  // implemented here.
4185  for (ObjCContainerDecl::method_iterator M = CurrentDecl->meth_begin(),
4186                                       MEnd = CurrentDecl->meth_end();
4187       M != MEnd; ++M) {
4188    if ((*M)->isInstanceMethod() != IsInstanceMethod)
4189      continue;
4190
4191    KnownMethodsMap::iterator Pos = KnownMethods.find((*M)->getSelector());
4192    if (Pos != KnownMethods.end())
4193      KnownMethods.erase(Pos);
4194  }
4195
4196  // Add declarations or definitions for each of the known methods.
4197  typedef CodeCompleteConsumer::Result Result;
4198  ResultBuilder Results(*this);
4199  Results.EnterNewScope();
4200  PrintingPolicy Policy(Context.PrintingPolicy);
4201  Policy.AnonymousTagLocations = false;
4202  for (KnownMethodsMap::iterator M = KnownMethods.begin(),
4203                              MEnd = KnownMethods.end();
4204       M != MEnd; ++M) {
4205    ObjCMethodDecl *Method = M->second;
4206    CodeCompletionString *Pattern = new CodeCompletionString;
4207
4208    // If the result type was not already provided, add it to the
4209    // pattern as (type).
4210    if (ReturnType.isNull()) {
4211      std::string TypeStr;
4212      Method->getResultType().getAsStringInternal(TypeStr, Policy);
4213      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
4214      Pattern->AddTextChunk(TypeStr);
4215      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
4216    }
4217
4218    Selector Sel = Method->getSelector();
4219
4220    // Add the first part of the selector to the pattern.
4221    Pattern->AddTypedTextChunk(Sel.getIdentifierInfoForSlot(0)->getName());
4222
4223    // Add parameters to the pattern.
4224    unsigned I = 0;
4225    for (ObjCMethodDecl::param_iterator P = Method->param_begin(),
4226                                     PEnd = Method->param_end();
4227         P != PEnd; (void)++P, ++I) {
4228      // Add the part of the selector name.
4229      if (I == 0)
4230        Pattern->AddChunk(CodeCompletionString::CK_Colon);
4231      else if (I < Sel.getNumArgs()) {
4232        Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
4233        Pattern->AddTextChunk(Sel.getIdentifierInfoForSlot(1)->getName());
4234        Pattern->AddChunk(CodeCompletionString::CK_Colon);
4235      } else
4236        break;
4237
4238      // Add the parameter type.
4239      std::string TypeStr;
4240      (*P)->getOriginalType().getAsStringInternal(TypeStr, Policy);
4241      Pattern->AddChunk(CodeCompletionString::CK_LeftParen);
4242      Pattern->AddTextChunk(TypeStr);
4243      Pattern->AddChunk(CodeCompletionString::CK_RightParen);
4244
4245      if (IdentifierInfo *Id = (*P)->getIdentifier())
4246        Pattern->AddTextChunk(Id->getName());
4247    }
4248
4249    if (Method->isVariadic()) {
4250      if (Method->param_size() > 0)
4251        Pattern->AddChunk(CodeCompletionString::CK_Comma);
4252      Pattern->AddTextChunk("...");
4253    }
4254
4255    if (IsInImplementation && Results.includeCodePatterns()) {
4256      // We will be defining the method here, so add a compound statement.
4257      Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
4258      Pattern->AddChunk(CodeCompletionString::CK_LeftBrace);
4259      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
4260      if (!Method->getResultType()->isVoidType()) {
4261        // If the result type is not void, add a return clause.
4262        Pattern->AddTextChunk("return");
4263        Pattern->AddChunk(CodeCompletionString::CK_HorizontalSpace);
4264        Pattern->AddPlaceholderChunk("expression");
4265        Pattern->AddChunk(CodeCompletionString::CK_SemiColon);
4266      } else
4267        Pattern->AddPlaceholderChunk("statements");
4268
4269      Pattern->AddChunk(CodeCompletionString::CK_VerticalSpace);
4270      Pattern->AddChunk(CodeCompletionString::CK_RightBrace);
4271    }
4272
4273    Results.AddResult(Result(Pattern));
4274  }
4275
4276  Results.ExitScope();
4277
4278  HandleCodeCompleteResults(this, CodeCompleter,
4279                            CodeCompletionContext::CCC_Other,
4280                            Results.data(),Results.size());
4281}
4282
4283void Sema::CodeCompleteObjCMethodDeclSelector(Scope *S,
4284                                              bool IsInstanceMethod,
4285                                              bool AtParameterName,
4286                                              TypeTy *ReturnTy,
4287                                              IdentifierInfo **SelIdents,
4288                                              unsigned NumSelIdents) {
4289  // If we have an external source, load the entire class method
4290  // pool from the PCH file.
4291  if (ExternalSource) {
4292    for (uint32_t I = 0, N = ExternalSource->GetNumExternalSelectors();
4293         I != N; ++I) {
4294      Selector Sel = ExternalSource->GetExternalSelector(I);
4295      if (Sel.isNull() || MethodPool.count(Sel))
4296        continue;
4297
4298      ReadMethodPool(Sel);
4299    }
4300  }
4301
4302  // Build the set of methods we can see.
4303  typedef CodeCompleteConsumer::Result Result;
4304  ResultBuilder Results(*this);
4305
4306  if (ReturnTy)
4307    Results.setPreferredType(GetTypeFromParser(ReturnTy).getNonReferenceType());
4308
4309  Results.EnterNewScope();
4310  for (GlobalMethodPool::iterator M = MethodPool.begin(),
4311                                  MEnd = MethodPool.end();
4312       M != MEnd; ++M) {
4313    for (ObjCMethodList *MethList = IsInstanceMethod ? &M->second.first :
4314                                                       &M->second.second;
4315         MethList && MethList->Method;
4316         MethList = MethList->Next) {
4317      if (!isAcceptableObjCMethod(MethList->Method, MK_Any, SelIdents,
4318                                  NumSelIdents))
4319        continue;
4320
4321      if (AtParameterName) {
4322        // Suggest parameter names we've seen before.
4323        if (NumSelIdents && NumSelIdents <= MethList->Method->param_size()) {
4324          ParmVarDecl *Param = MethList->Method->param_begin()[NumSelIdents-1];
4325          if (Param->getIdentifier()) {
4326            CodeCompletionString *Pattern = new CodeCompletionString;
4327            Pattern->AddTypedTextChunk(Param->getIdentifier()->getName());
4328            Results.AddResult(Pattern);
4329          }
4330        }
4331
4332        continue;
4333      }
4334
4335      Result R(MethList->Method, 0);
4336      R.StartParameter = NumSelIdents;
4337      R.AllParametersAreInformative = false;
4338      R.DeclaringEntity = true;
4339      Results.MaybeAddResult(R, CurContext);
4340    }
4341  }
4342
4343  Results.ExitScope();
4344  HandleCodeCompleteResults(this, CodeCompleter,
4345                            CodeCompletionContext::CCC_Other,
4346                            Results.data(),Results.size());
4347}
4348
4349void Sema::GatherGlobalCodeCompletions(
4350                 llvm::SmallVectorImpl<CodeCompleteConsumer::Result> &Results) {
4351  ResultBuilder Builder(*this);
4352
4353  if (!CodeCompleter || CodeCompleter->includeGlobals()) {
4354    CodeCompletionDeclConsumer Consumer(Builder,
4355                                        Context.getTranslationUnitDecl());
4356    LookupVisibleDecls(Context.getTranslationUnitDecl(), LookupAnyName,
4357                       Consumer);
4358  }
4359
4360  if (!CodeCompleter || CodeCompleter->includeMacros())
4361    AddMacroResults(PP, Builder);
4362
4363  Results.clear();
4364  Results.insert(Results.end(),
4365                 Builder.data(), Builder.data() + Builder.size());
4366}
4367