clang/lib/Sema/SemaCodeComplete.cpp

//===---------------- SemaCodeComplete.cpp - Code Completion ----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
//  This file defines the code-completion semantic actions.
//
//===----------------------------------------------------------------------===//
#include "clang/AST/ASTConcept.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclBase.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/Expr.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/ExprConcepts.h"
#include "clang/AST/ExprObjC.h"
#include "clang/AST/NestedNameSpecifier.h"
#include "clang/AST/QualTypeNames.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/AST/Type.h"
#include "clang/Basic/AttributeCommonInfo.h"
#include "clang/Basic/CharInfo.h"
#include "clang/Basic/OperatorKinds.h"
#include "clang/Basic/Specifiers.h"
#include "clang/Lex/HeaderSearch.h"
#include "clang/Lex/MacroInfo.h"
#include "clang/Lex/Preprocessor.h"
#include "clang/Sema/CodeCompleteConsumer.h"
#include "clang/Sema/DeclSpec.h"
#include "clang/Sema/Designator.h"
#include "clang/Sema/Lookup.h"
#include "clang/Sema/Overload.h"
#include "clang/Sema/ParsedAttr.h"
#include "clang/Sema/Scope.h"
#include "clang/Sema/ScopeInfo.h"
#include "clang/Sema/Sema.h"
#include "clang/Sema/SemaInternal.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/raw_ostream.h"
#include <list>
#include <map>
#include <string>
#include <vector>

using namespace clang;
using namespace sema;

namespace {
/// A container of code-completion results.
class ResultBuilder {
public:
  /// The type of a name-lookup filter, which can be provided to the
  /// name-lookup routines to specify which declarations should be included in
  /// the result set (when it returns true) and which declarations should be
  /// filtered out (returns false).
  typedef bool (ResultBuilder::*LookupFilter)(const NamedDecl *) const;

  typedef CodeCompletionResult Result;

private:
  /// The actual results we have found.
  std::vector<Result> Results;

  /// A record of all of the declarations we have found and placed
  /// into the result set, used to ensure that no declaration ever gets into
  /// the result set twice.
  llvm::SmallPtrSet<const Decl *, 16> AllDeclsFound;

  typedef std::pair<const NamedDecl *, unsigned> DeclIndexPair;

  /// An entry in the shadow map, which is optimized to store
  /// a single (declaration, index) mapping (the common case) but
  /// can also store a list of (declaration, index) mappings.
  class ShadowMapEntry {
    typedef SmallVector<DeclIndexPair, 4> DeclIndexPairVector;

    /// Contains either the solitary NamedDecl * or a vector
    /// of (declaration, index) pairs.
    llvm::PointerUnion<const NamedDecl *, DeclIndexPairVector *> DeclOrVector;

    /// When the entry contains a single declaration, this is
    /// the index associated with that entry.
    unsigned SingleDeclIndex;

  public:
    ShadowMapEntry() : DeclOrVector(), SingleDeclIndex(0) {}
    ShadowMapEntry(const ShadowMapEntry &) = delete;
    ShadowMapEntry(ShadowMapEntry &&Move) { *this = std::move(Move); }
    ShadowMapEntry &operator=(const ShadowMapEntry &) = delete;
    ShadowMapEntry &operator=(ShadowMapEntry &&Move) {
      SingleDeclIndex = Move.SingleDeclIndex;
      DeclOrVector = Move.DeclOrVector;
      Move.DeclOrVector = nullptr;
      return *this;
    }

    void Add(const NamedDecl *ND, unsigned Index) {
      if (DeclOrVector.isNull()) {
        // 0 - > 1 elements: just set the single element information.
        DeclOrVector = ND;
        SingleDeclIndex = Index;
        return;
      }

      if (const NamedDecl *PrevND =
              DeclOrVector.dyn_cast<const NamedDecl *>()) {
        // 1 -> 2 elements: create the vector of results and push in the
        // existing declaration.
        DeclIndexPairVector *Vec = new DeclIndexPairVector;
        Vec->push_back(DeclIndexPair(PrevND, SingleDeclIndex));
        DeclOrVector = Vec;
      }

      // Add the new element to the end of the vector.
      DeclOrVector.get<DeclIndexPairVector *>()->push_back(
          DeclIndexPair(ND, Index));
    }

    ~ShadowMapEntry() {
      if (DeclIndexPairVector *Vec =
              DeclOrVector.dyn_cast<DeclIndexPairVector *>()) {
        delete Vec;
        DeclOrVector = ((NamedDecl *)nullptr);
      }
    }

    // Iteration.
    class iterator;
    iterator begin() const;
    iterator end() const;
  };

  /// A mapping from declaration names to the declarations that have
  /// this name within a particular scope and their index within the list of
  /// results.
  typedef llvm::DenseMap<DeclarationName, ShadowMapEntry> ShadowMap;

  /// The semantic analysis object for which results are being
  /// produced.
  Sema &SemaRef;

  /// The allocator used to allocate new code-completion strings.
  CodeCompletionAllocator &Allocator;

  CodeCompletionTUInfo &CCTUInfo;

  /// If non-NULL, a filter function used to remove any code-completion
  /// results that are not desirable.
  LookupFilter Filter;

  /// Whether we should allow declarations as
  /// nested-name-specifiers that would otherwise be filtered out.
  bool AllowNestedNameSpecifiers;

  /// If set, the type that we would prefer our resulting value
  /// declarations to have.
  ///
  /// Closely matching the preferred type gives a boost to a result's
  /// priority.
  CanQualType PreferredType;

  /// A list of shadow maps, which is used to model name hiding at
  /// different levels of, e.g., the inheritance hierarchy.
  std::list<ShadowMap> ShadowMaps;

  /// Overloaded C++ member functions found by SemaLookup.
  /// Used to determine when one overload is dominated by another.
  llvm::DenseMap<std::pair<DeclContext *, /*Name*/uintptr_t>, ShadowMapEntry>
      OverloadMap;

  /// If we're potentially referring to a C++ member function, the set
  /// of qualifiers applied to the object type.
  Qualifiers ObjectTypeQualifiers;
  /// The kind of the object expression, for rvalue/lvalue overloads.
  ExprValueKind ObjectKind;

  /// Whether the \p ObjectTypeQualifiers field is active.
  bool HasObjectTypeQualifiers;

  /// The selector that we prefer.
  Selector PreferredSelector;

  /// The completion context in which we are gathering results.
  CodeCompletionContext CompletionContext;

  /// If we are in an instance method definition, the \@implementation
  /// object.
  ObjCImplementationDecl *ObjCImplementation;

  void AdjustResultPriorityForDecl(Result &R);

  void MaybeAddConstructorResults(Result R);

public:
  explicit ResultBuilder(Sema &SemaRef, CodeCompletionAllocator &Allocator,
                         CodeCompletionTUInfo &CCTUInfo,
                         const CodeCompletionContext &CompletionContext,
                         LookupFilter Filter = nullptr)
      : SemaRef(SemaRef), Allocator(Allocator), CCTUInfo(CCTUInfo),
        Filter(Filter), AllowNestedNameSpecifiers(false),
        HasObjectTypeQualifiers(false), CompletionContext(CompletionContext),
        ObjCImplementation(nullptr) {
    // If this is an Objective-C instance method definition, dig out the
    // corresponding implementation.
    switch (CompletionContext.getKind()) {
    case CodeCompletionContext::CCC_Expression:
    case CodeCompletionContext::CCC_ObjCMessageReceiver:
    case CodeCompletionContext::CCC_ParenthesizedExpression:
    case CodeCompletionContext::CCC_Statement:
    case CodeCompletionContext::CCC_Recovery:
      if (ObjCMethodDecl *Method = SemaRef.getCurMethodDecl())
        if (Method->isInstanceMethod())
          if (ObjCInterfaceDecl *Interface = Method->getClassInterface())
            ObjCImplementation = Interface->getImplementation();
      break;

    default:
      break;
    }
  }

  /// Determine the priority for a reference to the given declaration.
  unsigned getBasePriority(const NamedDecl *D);

  /// Whether we should include code patterns in the completion
  /// results.
  bool includeCodePatterns() const {
    return SemaRef.CodeCompleter &&
           SemaRef.CodeCompleter->includeCodePatterns();
  }

  /// Set the filter used for code-completion results.
  void setFilter(LookupFilter Filter) { this->Filter = Filter; }

  Result *data() { return Results.empty() ? nullptr : &Results.front(); }
  unsigned size() const { return Results.size(); }
  bool empty() const { return Results.empty(); }

  /// Specify the preferred type.
  void setPreferredType(QualType T) {
    PreferredType = SemaRef.Context.getCanonicalType(T);
  }

  /// Set the cv-qualifiers on the object type, for us in filtering
  /// calls to member functions.
  ///
  /// When there are qualifiers in this set, they will be used to filter
  /// out member functions that aren't available (because there will be a
  /// cv-qualifier mismatch) or prefer functions with an exact qualifier
  /// match.
  void setObjectTypeQualifiers(Qualifiers Quals, ExprValueKind Kind) {
    ObjectTypeQualifiers = Quals;
    ObjectKind = Kind;
    HasObjectTypeQualifiers = true;
  }

  /// Set the preferred selector.
  ///
  /// When an Objective-C method declaration result is added, and that
  /// method's selector matches this preferred selector, we give that method
  /// a slight priority boost.
  void setPreferredSelector(Selector Sel) { PreferredSelector = Sel; }

  /// Retrieve the code-completion context for which results are
  /// being collected.
  const CodeCompletionContext &getCompletionContext() const {
    return CompletionContext;
  }

  /// Specify whether nested-name-specifiers are allowed.
  void allowNestedNameSpecifiers(bool Allow = true) {
    AllowNestedNameSpecifiers = Allow;
  }

  /// Return the semantic analysis object for which we are collecting
  /// code completion results.
  Sema &getSema() const { return SemaRef; }

  /// Retrieve the allocator used to allocate code completion strings.
  CodeCompletionAllocator &getAllocator() const { return Allocator; }

  CodeCompletionTUInfo &getCodeCompletionTUInfo() const { return CCTUInfo; }

  /// Determine whether the given declaration is at all interesting
  /// as a code-completion result.
  ///
  /// \param ND the declaration that we are inspecting.
  ///
  /// \param AsNestedNameSpecifier will be set true if this declaration is
  /// only interesting when it is a nested-name-specifier.
  bool isInterestingDecl(const NamedDecl *ND,
                         bool &AsNestedNameSpecifier) const;

  /// Check whether the result is hidden by the Hiding declaration.
  ///
  /// \returns true if the result is hidden and cannot be found, false if
  /// the hidden result could still be found. When false, \p R may be
  /// modified to describe how the result can be found (e.g., via extra
  /// qualification).
  bool CheckHiddenResult(Result &R, DeclContext *CurContext,
                         const NamedDecl *Hiding);

  /// Add a new result to this result set (if it isn't already in one
  /// of the shadow maps), or replace an existing result (for, e.g., a
  /// redeclaration).
  ///
  /// \param R the result to add (if it is unique).
  ///
  /// \param CurContext the context in which this result will be named.
  void MaybeAddResult(Result R, DeclContext *CurContext = nullptr);

  /// Add a new result to this result set, where we already know
  /// the hiding declaration (if any).
  ///
  /// \param R the result to add (if it is unique).
  ///
  /// \param CurContext the context in which this result will be named.
  ///
  /// \param Hiding the declaration that hides the result.
  ///
  /// \param InBaseClass whether the result was found in a base
  /// class of the searched context.
  void AddResult(Result R, DeclContext *CurContext, NamedDecl *Hiding,
                 bool InBaseClass);

  /// Add a new non-declaration result to this result set.
  void AddResult(Result R);

  /// Enter into a new scope.
  void EnterNewScope();

  /// Exit from the current scope.
  void ExitScope();

  /// Ignore this declaration, if it is seen again.
  void Ignore(const Decl *D) { AllDeclsFound.insert(D->getCanonicalDecl()); }

  /// Add a visited context.
  void addVisitedContext(DeclContext *Ctx) {
    CompletionContext.addVisitedContext(Ctx);
  }

  /// \name Name lookup predicates
  ///
  /// These predicates can be passed to the name lookup functions to filter the
  /// results of name lookup. All of the predicates have the same type, so that
  ///
  //@{
  bool IsOrdinaryName(const NamedDecl *ND) const;
  bool IsOrdinaryNonTypeName(const NamedDecl *ND) const;
  bool IsIntegralConstantValue(const NamedDecl *ND) const;
  bool IsOrdinaryNonValueName(const NamedDecl *ND) const;
  bool IsNestedNameSpecifier(const NamedDecl *ND) const;
  bool IsEnum(const NamedDecl *ND) const;
  bool IsClassOrStruct(const NamedDecl *ND) const;
  bool IsUnion(const NamedDecl *ND) const;
  bool IsNamespace(const NamedDecl *ND) const;
  bool IsNamespaceOrAlias(const NamedDecl *ND) const;
  bool IsType(const NamedDecl *ND) const;
  bool IsMember(const NamedDecl *ND) const;
  bool IsObjCIvar(const NamedDecl *ND) const;
  bool IsObjCMessageReceiver(const NamedDecl *ND) const;
  bool IsObjCMessageReceiverOrLambdaCapture(const NamedDecl *ND) const;
  bool IsObjCCollection(const NamedDecl *ND) const;
  bool IsImpossibleToSatisfy(const NamedDecl *ND) const;
  //@}
};
} // namespace

void PreferredTypeBuilder::enterReturn(Sema &S, SourceLocation Tok) {
  if (!Enabled)
    return;
  if (isa<BlockDecl>(S.CurContext)) {
    if (sema::BlockScopeInfo *BSI = S.getCurBlock()) {
      ComputeType = nullptr;
      Type = BSI->ReturnType;
      ExpectedLoc = Tok;
    }
  } else if (const auto *Function = dyn_cast<FunctionDecl>(S.CurContext)) {
    ComputeType = nullptr;
    Type = Function->getReturnType();
    ExpectedLoc = Tok;
  } else if (const auto *Method = dyn_cast<ObjCMethodDecl>(S.CurContext)) {
    ComputeType = nullptr;
    Type = Method->getReturnType();
    ExpectedLoc = Tok;
  }
}

void PreferredTypeBuilder::enterVariableInit(SourceLocation Tok, Decl *D) {
  if (!Enabled)
    return;
  auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
  ComputeType = nullptr;
  Type = VD ? VD->getType() : QualType();
  ExpectedLoc = Tok;
}

static QualType getDesignatedType(QualType BaseType, const Designation &Desig);

void PreferredTypeBuilder::enterDesignatedInitializer(SourceLocation Tok,
                                                      QualType BaseType,
                                                      const Designation &D) {
  if (!Enabled)
    return;
  ComputeType = nullptr;
  Type = getDesignatedType(BaseType, D);
  ExpectedLoc = Tok;
}

void PreferredTypeBuilder::enterFunctionArgument(
    SourceLocation Tok, llvm::function_ref<QualType()> ComputeType) {
  if (!Enabled)
    return;
  this->ComputeType = ComputeType;
  Type = QualType();
  ExpectedLoc = Tok;
}

void PreferredTypeBuilder::enterParenExpr(SourceLocation Tok,
                                          SourceLocation LParLoc) {
  if (!Enabled)
    return;
  // expected type for parenthesized expression does not change.
  if (ExpectedLoc == LParLoc)
    ExpectedLoc = Tok;
}

static QualType getPreferredTypeOfBinaryRHS(Sema &S, Expr *LHS,
                                            tok::TokenKind Op) {
  if (!LHS)
    return QualType();

  QualType LHSType = LHS->getType();
  if (LHSType->isPointerType()) {
    if (Op == tok::plus || Op == tok::plusequal || Op == tok::minusequal)
      return S.getASTContext().getPointerDiffType();
    // Pointer difference is more common than subtracting an int from a pointer.
    if (Op == tok::minus)
      return LHSType;
  }

  switch (Op) {
  // No way to infer the type of RHS from LHS.
  case tok::comma:
    return QualType();
  // Prefer the type of the left operand for all of these.
  // Arithmetic operations.
  case tok::plus:
  case tok::plusequal:
  case tok::minus:
  case tok::minusequal:
  case tok::percent:
  case tok::percentequal:
  case tok::slash:
  case tok::slashequal:
  case tok::star:
  case tok::starequal:
  // Assignment.
  case tok::equal:
  // Comparison operators.
  case tok::equalequal:
  case tok::exclaimequal:
  case tok::less:
  case tok::lessequal:
  case tok::greater:
  case tok::greaterequal:
  case tok::spaceship:
    return LHS->getType();
  // Binary shifts are often overloaded, so don't try to guess those.
  case tok::greatergreater:
  case tok::greatergreaterequal:
  case tok::lessless:
  case tok::lesslessequal:
    if (LHSType->isIntegralOrEnumerationType())
      return S.getASTContext().IntTy;
    return QualType();
  // Logical operators, assume we want bool.
  case tok::ampamp:
  case tok::pipepipe:
  case tok::caretcaret:
    return S.getASTContext().BoolTy;
  // Operators often used for bit manipulation are typically used with the type
  // of the left argument.
  case tok::pipe:
  case tok::pipeequal:
  case tok::caret:
  case tok::caretequal:
  case tok::amp:
  case tok::ampequal:
    if (LHSType->isIntegralOrEnumerationType())
      return LHSType;
    return QualType();
  // RHS should be a pointer to a member of the 'LHS' type, but we can't give
  // any particular type here.
  case tok::periodstar:
  case tok::arrowstar:
    return QualType();
  default:
    // FIXME(ibiryukov): handle the missing op, re-add the assertion.
    // assert(false && "unhandled binary op");
    return QualType();
  }
}

/// Get preferred type for an argument of an unary expression. \p ContextType is
/// preferred type of the whole unary expression.
static QualType getPreferredTypeOfUnaryArg(Sema &S, QualType ContextType,
                                           tok::TokenKind Op) {
  switch (Op) {
  case tok::exclaim:
    return S.getASTContext().BoolTy;
  case tok::amp:
    if (!ContextType.isNull() && ContextType->isPointerType())
      return ContextType->getPointeeType();
    return QualType();
  case tok::star:
    if (ContextType.isNull())
      return QualType();
    return S.getASTContext().getPointerType(ContextType.getNonReferenceType());
  case tok::plus:
  case tok::minus:
  case tok::tilde:
  case tok::minusminus:
  case tok::plusplus:
    if (ContextType.isNull())
      return S.getASTContext().IntTy;
    // leave as is, these operators typically return the same type.
    return ContextType;
  case tok::kw___real:
  case tok::kw___imag:
    return QualType();
  default:
    assert(false && "unhandled unary op");
    return QualType();
  }
}

void PreferredTypeBuilder::enterBinary(Sema &S, SourceLocation Tok, Expr *LHS,
                                       tok::TokenKind Op) {
  if (!Enabled)
    return;
  ComputeType = nullptr;
  Type = getPreferredTypeOfBinaryRHS(S, LHS, Op);
  ExpectedLoc = Tok;
}

void PreferredTypeBuilder::enterMemAccess(Sema &S, SourceLocation Tok,
                                          Expr *Base) {
  if (!Enabled || !Base)
    return;
  // Do we have expected type for Base?
  if (ExpectedLoc != Base->getBeginLoc())
    return;
  // Keep the expected type, only update the location.
  ExpectedLoc = Tok;
  return;
}

void PreferredTypeBuilder::enterUnary(Sema &S, SourceLocation Tok,
                                      tok::TokenKind OpKind,
                                      SourceLocation OpLoc) {
  if (!Enabled)
    return;
  ComputeType = nullptr;
  Type = getPreferredTypeOfUnaryArg(S, this->get(OpLoc), OpKind);
  ExpectedLoc = Tok;
}

void PreferredTypeBuilder::enterSubscript(Sema &S, SourceLocation Tok,
                                          Expr *LHS) {
  if (!Enabled)
    return;
  ComputeType = nullptr;
  Type = S.getASTContext().IntTy;
  ExpectedLoc = Tok;
}

void PreferredTypeBuilder::enterTypeCast(SourceLocation Tok,
                                         QualType CastType) {
  if (!Enabled)
    return;
  ComputeType = nullptr;
  Type = !CastType.isNull() ? CastType.getCanonicalType() : QualType();
  ExpectedLoc = Tok;
}

void PreferredTypeBuilder::enterCondition(Sema &S, SourceLocation Tok) {
  if (!Enabled)
    return;
  ComputeType = nullptr;
  Type = S.getASTContext().BoolTy;
  ExpectedLoc = Tok;
}

class ResultBuilder::ShadowMapEntry::iterator {
  llvm::PointerUnion<const NamedDecl *, const DeclIndexPair *> DeclOrIterator;
  unsigned SingleDeclIndex;

public:
  typedef DeclIndexPair value_type;
  typedef value_type reference;
  typedef std::ptrdiff_t difference_type;
  typedef std::input_iterator_tag iterator_category;

  class pointer {
    DeclIndexPair Value;

  public:
    pointer(const DeclIndexPair &Value) : Value(Value) {}

    const DeclIndexPair *operator->() const { return &Value; }
  };

  iterator() : DeclOrIterator((NamedDecl *)nullptr), SingleDeclIndex(0) {}

  iterator(const NamedDecl *SingleDecl, unsigned Index)
      : DeclOrIterator(SingleDecl), SingleDeclIndex(Index) {}

  iterator(const DeclIndexPair *Iterator)
      : DeclOrIterator(Iterator), SingleDeclIndex(0) {}

  iterator &operator++() {
    if (DeclOrIterator.is<const NamedDecl *>()) {
      DeclOrIterator = (NamedDecl *)nullptr;
      SingleDeclIndex = 0;
      return *this;
    }

    const DeclIndexPair *I = DeclOrIterator.get<const DeclIndexPair *>();
    ++I;
    DeclOrIterator = I;
    return *this;
  }

  /*iterator operator++(int) {
    iterator tmp(*this);
    ++(*this);
    return tmp;
  }*/

  reference operator*() const {
    if (const NamedDecl *ND = DeclOrIterator.dyn_cast<const NamedDecl *>())
      return reference(ND, SingleDeclIndex);

    return *DeclOrIterator.get<const DeclIndexPair *>();
  }

  pointer operator->() const { return pointer(**this); }

  friend bool operator==(const iterator &X, const iterator &Y) {
    return X.DeclOrIterator.getOpaqueValue() ==
               Y.DeclOrIterator.getOpaqueValue() &&
           X.SingleDeclIndex == Y.SingleDeclIndex;
  }

  friend bool operator!=(const iterator &X, const iterator &Y) {
    return !(X == Y);
  }
};

ResultBuilder::ShadowMapEntry::iterator
ResultBuilder::ShadowMapEntry::begin() const {
  if (DeclOrVector.isNull())
    return iterator();

  if (const NamedDecl *ND = DeclOrVector.dyn_cast<const NamedDecl *>())
    return iterator(ND, SingleDeclIndex);

  return iterator(DeclOrVector.get<DeclIndexPairVector *>()->begin());
}

ResultBuilder::ShadowMapEntry::iterator
ResultBuilder::ShadowMapEntry::end() const {
  if (DeclOrVector.is<const NamedDecl *>() || DeclOrVector.isNull())
    return iterator();

  return iterator(DeclOrVector.get<DeclIndexPairVector *>()->end());
}

/// Compute the qualification required to get from the current context
/// (\p CurContext) to the target context (\p TargetContext).
///
/// \param Context the AST context in which the qualification will be used.
///
/// \param CurContext the context where an entity is being named, which is
/// typically based on the current scope.
///
/// \param TargetContext the context in which the named entity actually
/// resides.
///
/// \returns a nested name specifier that refers into the target context, or
/// NULL if no qualification is needed.
static NestedNameSpecifier *
getRequiredQualification(ASTContext &Context, const DeclContext *CurContext,
                         const DeclContext *TargetContext) {
  SmallVector<const DeclContext *, 4> TargetParents;

  for (const DeclContext *CommonAncestor = TargetContext;
       CommonAncestor && !CommonAncestor->Encloses(CurContext);
       CommonAncestor = CommonAncestor->getLookupParent()) {
    if (CommonAncestor->isTransparentContext() ||
        CommonAncestor->isFunctionOrMethod())
      continue;

    TargetParents.push_back(CommonAncestor);
  }

  NestedNameSpecifier *Result = nullptr;
  while (!TargetParents.empty()) {
    const DeclContext *Parent = TargetParents.pop_back_val();

    if (const auto *Namespace = dyn_cast<NamespaceDecl>(Parent)) {
      if (!Namespace->getIdentifier())
        continue;

      Result = NestedNameSpecifier::Create(Context, Result, Namespace);
    } else if (const auto *TD = dyn_cast<TagDecl>(Parent))
      Result = NestedNameSpecifier::Create(
          Context, Result, false, Context.getTypeDeclType(TD).getTypePtr());
  }
  return Result;
}

// Some declarations have reserved names that we don't want to ever show.
// Filter out names reserved for the implementation if they come from a
// system header.
static bool shouldIgnoreDueToReservedName(const NamedDecl *ND, Sema &SemaRef) {
  ReservedIdentifierStatus Status = ND->isReserved(SemaRef.getLangOpts());
  // Ignore reserved names for compiler provided decls.
  if (isReservedInAllContexts(Status) && ND->getLocation().isInvalid())
    return true;

  // For system headers ignore only double-underscore names.
  // This allows for system headers providing private symbols with a single
  // underscore.
  if (Status == ReservedIdentifierStatus::StartsWithDoubleUnderscore &&
      SemaRef.SourceMgr.isInSystemHeader(
          SemaRef.SourceMgr.getSpellingLoc(ND->getLocation())))
    return true;

  return false;
}

bool ResultBuilder::isInterestingDecl(const NamedDecl *ND,
                                      bool &AsNestedNameSpecifier) const {
  AsNestedNameSpecifier = false;

  auto *Named = ND;
  ND = ND->getUnderlyingDecl();

  // Skip unnamed entities.
  if (!ND->getDeclName())
    return false;

  // Friend declarations and declarations introduced due to friends are never
  // added as results.
  if (ND->getFriendObjectKind() == Decl::FOK_Undeclared)
    return false;

  // Class template (partial) specializations are never added as results.
  if (isa<ClassTemplateSpecializationDecl>(ND) ||
      isa<ClassTemplatePartialSpecializationDecl>(ND))
    return false;

  // Using declarations themselves are never added as results.
  if (isa<UsingDecl>(ND))
    return false;

  if (shouldIgnoreDueToReservedName(ND, SemaRef))
    return false;

  if (Filter == &ResultBuilder::IsNestedNameSpecifier ||
      (isa<NamespaceDecl>(ND) && Filter != &ResultBuilder::IsNamespace &&
       Filter != &ResultBuilder::IsNamespaceOrAlias && Filter != nullptr))
    AsNestedNameSpecifier = true;

  // Filter out any unwanted results.
  if (Filter && !(this->*Filter)(Named)) {
    // Check whether it is interesting as a nested-name-specifier.
    if (AllowNestedNameSpecifiers && SemaRef.getLangOpts().CPlusPlus &&
        IsNestedNameSpecifier(ND) &&
        (Filter != &ResultBuilder::IsMember ||
         (isa<CXXRecordDecl>(ND) &&
          cast<CXXRecordDecl>(ND)->isInjectedClassName()))) {
      AsNestedNameSpecifier = true;
      return true;
    }

    return false;
  }
  // ... then it must be interesting!
  return true;
}

bool ResultBuilder::CheckHiddenResult(Result &R, DeclContext *CurContext,
                                      const NamedDecl *Hiding) {
  // In C, there is no way to refer to a hidden name.
  // FIXME: This isn't true; we can find a tag name hidden by an ordinary
  // name if we introduce the tag type.
  if (!SemaRef.getLangOpts().CPlusPlus)
    return true;

  const DeclContext *HiddenCtx =
      R.Declaration->getDeclContext()->getRedeclContext();

  // There is no way to qualify a name declared in a function or method.
  if (HiddenCtx->isFunctionOrMethod())
    return true;

  if (HiddenCtx == Hiding->getDeclContext()->getRedeclContext())
    return true;

  // We can refer to the result with the appropriate qualification. Do it.
  R.Hidden = true;
  R.QualifierIsInformative = false;

  if (!R.Qualifier)
    R.Qualifier = getRequiredQualification(SemaRef.Context, CurContext,
                                           R.Declaration->getDeclContext());
  return false;
}

/// A simplified classification of types used to determine whether two
/// types are "similar enough" when adjusting priorities.
SimplifiedTypeClass clang::getSimplifiedTypeClass(CanQualType T) {
  switch (T->getTypeClass()) {
  case Type::Builtin:
    switch (cast<BuiltinType>(T)->getKind()) {
    case BuiltinType::Void:
      return STC_Void;

    case BuiltinType::NullPtr:
      return STC_Pointer;

    case BuiltinType::Overload:
    case BuiltinType::Dependent:
      return STC_Other;

    case BuiltinType::ObjCId:
    case BuiltinType::ObjCClass:
    case BuiltinType::ObjCSel:
      return STC_ObjectiveC;

    default:
      return STC_Arithmetic;
    }

  case Type::Complex:
    return STC_Arithmetic;

  case Type::Pointer:
    return STC_Pointer;

  case Type::BlockPointer:
    return STC_Block;

  case Type::LValueReference:
  case Type::RValueReference:
    return getSimplifiedTypeClass(T->getAs<ReferenceType>()->getPointeeType());

  case Type::ConstantArray:
  case Type::IncompleteArray:
  case Type::VariableArray:
  case Type::DependentSizedArray:
    return STC_Array;

  case Type::DependentSizedExtVector:
  case Type::Vector:
  case Type::ExtVector:
    return STC_Arithmetic;

  case Type::FunctionProto:
  case Type::FunctionNoProto:
    return STC_Function;

  case Type::Record:
    return STC_Record;

  case Type::Enum:
    return STC_Arithmetic;

  case Type::ObjCObject:
  case Type::ObjCInterface:
  case Type::ObjCObjectPointer:
    return STC_ObjectiveC;

  default:
    return STC_Other;
  }
}

/// Get the type that a given expression will have if this declaration
/// is used as an expression in its "typical" code-completion form.
QualType clang::getDeclUsageType(ASTContext &C, const NamedDecl *ND) {
  ND = ND->getUnderlyingDecl();

  if (const auto *Type = dyn_cast<TypeDecl>(ND))
    return C.getTypeDeclType(Type);
  if (const auto *Iface = dyn_cast<ObjCInterfaceDecl>(ND))
    return C.getObjCInterfaceType(Iface);

  QualType T;
  if (const FunctionDecl *Function = ND->getAsFunction())
    T = Function->getCallResultType();
  else if (const auto *Method = dyn_cast<ObjCMethodDecl>(ND))
    T = Method->getSendResultType();
  else if (const auto *Enumerator = dyn_cast<EnumConstantDecl>(ND))
    T = C.getTypeDeclType(cast<EnumDecl>(Enumerator->getDeclContext()));
  else if (const auto *Property = dyn_cast<ObjCPropertyDecl>(ND))
    T = Property->getType();
  else if (const auto *Value = dyn_cast<ValueDecl>(ND))
    T = Value->getType();

  if (T.isNull())
    return QualType();

  // Dig through references, function pointers, and block pointers to
  // get down to the likely type of an expression when the entity is
  // used.
  do {
    if (const auto *Ref = T->getAs<ReferenceType>()) {
      T = Ref->getPointeeType();
      continue;
    }

    if (const auto *Pointer = T->getAs<PointerType>()) {
      if (Pointer->getPointeeType()->isFunctionType()) {
        T = Pointer->getPointeeType();
        continue;
      }

      break;
    }

    if (const auto *Block = T->getAs<BlockPointerType>()) {
      T = Block->getPointeeType();
      continue;
    }

    if (const auto *Function = T->getAs<FunctionType>()) {
      T = Function->getReturnType();
      continue;
    }

    break;
  } while (true);

  return T;
}

unsigned ResultBuilder::getBasePriority(const NamedDecl *ND) {
  if (!ND)
    return CCP_Unlikely;

  // Context-based decisions.
  const DeclContext *LexicalDC = ND->getLexicalDeclContext();
  if (LexicalDC->isFunctionOrMethod()) {
    // _cmd is relatively rare
    if (const auto *ImplicitParam = dyn_cast<ImplicitParamDecl>(ND))
      if (ImplicitParam->getIdentifier() &&
          ImplicitParam->getIdentifier()->isStr("_cmd"))
        return CCP_ObjC_cmd;

    return CCP_LocalDeclaration;
  }

  const DeclContext *DC = ND->getDeclContext()->getRedeclContext();
  if (DC->isRecord() || isa<ObjCContainerDecl>(DC)) {
    // Explicit destructor calls are very rare.
    if (isa<CXXDestructorDecl>(ND))
      return CCP_Unlikely;
    // Explicit operator and conversion function calls are also very rare.
    auto DeclNameKind = ND->getDeclName().getNameKind();
    if (DeclNameKind == DeclarationName::CXXOperatorName ||
        DeclNameKind == DeclarationName::CXXLiteralOperatorName ||
        DeclNameKind == DeclarationName::CXXConversionFunctionName)
      return CCP_Unlikely;
    return CCP_MemberDeclaration;
  }

  // Content-based decisions.
  if (isa<EnumConstantDecl>(ND))
    return CCP_Constant;

  // Use CCP_Type for type declarations unless we're in a statement, Objective-C
  // message receiver, or parenthesized expression context. There, it's as
  // likely that the user will want to write a type as other declarations.
  if ((isa<TypeDecl>(ND) || isa<ObjCInterfaceDecl>(ND)) &&
      !(CompletionContext.getKind() == CodeCompletionContext::CCC_Statement ||
        CompletionContext.getKind() ==
            CodeCompletionContext::CCC_ObjCMessageReceiver ||
        CompletionContext.getKind() ==
            CodeCompletionContext::CCC_ParenthesizedExpression))
    return CCP_Type;

  return CCP_Declaration;
}

void ResultBuilder::AdjustResultPriorityForDecl(Result &R) {
  // If this is an Objective-C method declaration whose selector matches our
  // preferred selector, give it a priority boost.
  if (!PreferredSelector.isNull())
    if (const auto *Method = dyn_cast<ObjCMethodDecl>(R.Declaration))
      if (PreferredSelector == Method->getSelector())
        R.Priority += CCD_SelectorMatch;

  // If we have a preferred type, adjust the priority for results with exactly-
  // matching or nearly-matching types.
  if (!PreferredType.isNull()) {
    QualType T = getDeclUsageType(SemaRef.Context, R.Declaration);
    if (!T.isNull()) {
      CanQualType TC = SemaRef.Context.getCanonicalType(T);
      // Check for exactly-matching types (modulo qualifiers).
      if (SemaRef.Context.hasSameUnqualifiedType(PreferredType, TC))
        R.Priority /= CCF_ExactTypeMatch;
      // Check for nearly-matching types, based on classification of each.
      else if ((getSimplifiedTypeClass(PreferredType) ==
                getSimplifiedTypeClass(TC)) &&
               !(PreferredType->isEnumeralType() && TC->isEnumeralType()))
        R.Priority /= CCF_SimilarTypeMatch;
    }
  }
}

static DeclContext::lookup_result getConstructors(ASTContext &Context,
                                                  const CXXRecordDecl *Record) {
  QualType RecordTy = Context.getTypeDeclType(Record);
  DeclarationName ConstructorName =
      Context.DeclarationNames.getCXXConstructorName(
          Context.getCanonicalType(RecordTy));
  return Record->lookup(ConstructorName);
}

void ResultBuilder::MaybeAddConstructorResults(Result R) {
  if (!SemaRef.getLangOpts().CPlusPlus || !R.Declaration ||
      !CompletionContext.wantConstructorResults())
    return;

  const NamedDecl *D = R.Declaration;
  const CXXRecordDecl *Record = nullptr;
  if (const ClassTemplateDecl *ClassTemplate = dyn_cast<ClassTemplateDecl>(D))
    Record = ClassTemplate->getTemplatedDecl();
  else if ((Record = dyn_cast<CXXRecordDecl>(D))) {
    // Skip specializations and partial specializations.
    if (isa<ClassTemplateSpecializationDecl>(Record))
      return;
  } else {
    // There are no constructors here.
    return;
  }

  Record = Record->getDefinition();
  if (!Record)
    return;

  for (NamedDecl *Ctor : getConstructors(SemaRef.Context, Record)) {
    R.Declaration = Ctor;
    R.CursorKind = getCursorKindForDecl(R.Declaration);
    Results.push_back(R);
  }
}

static bool isConstructor(const Decl *ND) {
  if (const auto *Tmpl = dyn_cast<FunctionTemplateDecl>(ND))
    ND = Tmpl->getTemplatedDecl();
  return isa<CXXConstructorDecl>(ND);
}

void ResultBuilder::MaybeAddResult(Result R, DeclContext *CurContext) {
  assert(!ShadowMaps.empty() && "Must enter into a results scope");

  if (R.Kind != Result::RK_Declaration) {
    // For non-declaration results, just add the result.
    Results.push_back(R);
    return;
  }

  // Look through using declarations.
  if (const UsingShadowDecl *Using = dyn_cast<UsingShadowDecl>(R.Declaration)) {
    CodeCompletionResult Result(Using->getTargetDecl(),
                                getBasePriority(Using->getTargetDecl()),
                                R.Qualifier);
    Result.ShadowDecl = Using;
    MaybeAddResult(Result, CurContext);
    return;
  }

  const Decl *CanonDecl = R.Declaration->getCanonicalDecl();
  unsigned IDNS = CanonDecl->getIdentifierNamespace();

  bool AsNestedNameSpecifier = false;
  if (!isInterestingDecl(R.Declaration, AsNestedNameSpecifier))
    return;

  // C++ constructors are never found by name lookup.
  if (isConstructor(R.Declaration))
    return;

  ShadowMap &SMap = ShadowMaps.back();
  ShadowMapEntry::iterator I, IEnd;
  ShadowMap::iterator NamePos = SMap.find(R.Declaration->getDeclName());
  if (NamePos != SMap.end()) {
    I = NamePos->second.begin();
    IEnd = NamePos->second.end();
  }

  for (; I != IEnd; ++I) {
    const NamedDecl *ND = I->first;
    unsigned Index = I->second;
    if (ND->getCanonicalDecl() == CanonDecl) {
      // This is a redeclaration. Always pick the newer declaration.
      Results[Index].Declaration = R.Declaration;

      // We're done.
      return;
    }
  }

  // This is a new declaration in this scope. However, check whether this
  // declaration name is hidden by a similarly-named declaration in an outer
  // scope.
  std::list<ShadowMap>::iterator SM, SMEnd = ShadowMaps.end();
  --SMEnd;
  for (SM = ShadowMaps.begin(); SM != SMEnd; ++SM) {
    ShadowMapEntry::iterator I, IEnd;
    ShadowMap::iterator NamePos = SM->find(R.Declaration->getDeclName());
    if (NamePos != SM->end()) {
      I = NamePos->second.begin();
      IEnd = NamePos->second.end();
    }
    for (; I != IEnd; ++I) {
      // A tag declaration does not hide a non-tag declaration.
      if (I->first->hasTagIdentifierNamespace() &&
          (IDNS & (Decl::IDNS_Member | Decl::IDNS_Ordinary |
                   Decl::IDNS_LocalExtern | Decl::IDNS_ObjCProtocol)))
        continue;

      // Protocols are in distinct namespaces from everything else.
      if (((I->first->getIdentifierNamespace() & Decl::IDNS_ObjCProtocol) ||
           (IDNS & Decl::IDNS_ObjCProtocol)) &&
          I->first->getIdentifierNamespace() != IDNS)
        continue;

      // The newly-added result is hidden by an entry in the shadow map.
      if (CheckHiddenResult(R, CurContext, I->first))
        return;

      break;
    }
  }

  // Make sure that any given declaration only shows up in the result set once.
  if (!AllDeclsFound.insert(CanonDecl).second)
    return;

  // If the filter is for nested-name-specifiers, then this result starts a
  // nested-name-specifier.
  if (AsNestedNameSpecifier) {
    R.StartsNestedNameSpecifier = true;
    R.Priority = CCP_NestedNameSpecifier;
  } else
    AdjustResultPriorityForDecl(R);

  // If this result is supposed to have an informative qualifier, add one.
  if (R.QualifierIsInformative && !R.Qualifier &&
      !R.StartsNestedNameSpecifier) {
    const DeclContext *Ctx = R.Declaration->getDeclContext();
    if (const NamespaceDecl *Namespace = dyn_cast<NamespaceDecl>(Ctx))
      R.Qualifier =
          NestedNameSpecifier::Create(SemaRef.Context, nullptr, Namespace);
    else if (const TagDecl *Tag = dyn_cast<TagDecl>(Ctx))
      R.Qualifier = NestedNameSpecifier::Create(
          SemaRef.Context, nullptr, false,
          SemaRef.Context.getTypeDeclType(Tag).getTypePtr());
    else
      R.QualifierIsInformative = false;
  }

  // Insert this result into the set of results and into the current shadow
  // map.
  SMap[R.Declaration->getDeclName()].Add(R.Declaration, Results.size());
  Results.push_back(R);

  if (!AsNestedNameSpecifier)
    MaybeAddConstructorResults(R);
}

static void setInBaseClass(ResultBuilder::Result &R) {
  R.Priority += CCD_InBaseClass;
  R.InBaseClass = true;
}

enum class OverloadCompare { BothViable, Dominates, Dominated };
// Will Candidate ever be called on the object, when overloaded with Incumbent?
// Returns Dominates if Candidate is always called, Dominated if Incumbent is
// always called, BothViable if either may be called dependending on arguments.
// Precondition: must actually be overloads!
static OverloadCompare compareOverloads(const CXXMethodDecl &Candidate,
                                        const CXXMethodDecl &Incumbent,
                                        const Qualifiers &ObjectQuals,
                                        ExprValueKind ObjectKind) {
  // Base/derived shadowing is handled elsewhere.
  if (Candidate.getDeclContext() != Incumbent.getDeclContext())
    return OverloadCompare::BothViable;
  if (Candidate.isVariadic() != Incumbent.isVariadic() ||
      Candidate.getNumParams() != Incumbent.getNumParams() ||
      Candidate.getMinRequiredArguments() !=
          Incumbent.getMinRequiredArguments())
    return OverloadCompare::BothViable;
  for (unsigned I = 0, E = Candidate.getNumParams(); I != E; ++I)
    if (Candidate.parameters()[I]->getType().getCanonicalType() !=
        Incumbent.parameters()[I]->getType().getCanonicalType())
      return OverloadCompare::BothViable;
  if (!llvm::empty(Candidate.specific_attrs<EnableIfAttr>()) ||
      !llvm::empty(Incumbent.specific_attrs<EnableIfAttr>()))
    return OverloadCompare::BothViable;
  // At this point, we know calls can't pick one or the other based on
  // arguments, so one of the two must win. (Or both fail, handled elsewhere).
  RefQualifierKind CandidateRef = Candidate.getRefQualifier();
  RefQualifierKind IncumbentRef = Incumbent.getRefQualifier();
  if (CandidateRef != IncumbentRef) {
    // If the object kind is LValue/RValue, there's one acceptable ref-qualifier
    // and it can't be mixed with ref-unqualified overloads (in valid code).

    // For xvalue objects, we prefer the rvalue overload even if we have to
    // add qualifiers (which is rare, because const&& is rare).
    if (ObjectKind == clang::VK_XValue)
      return CandidateRef == RQ_RValue ? OverloadCompare::Dominates
                                       : OverloadCompare::Dominated;
  }
  // Now the ref qualifiers are the same (or we're in some invalid state).
  // So make some decision based on the qualifiers.
  Qualifiers CandidateQual = Candidate.getMethodQualifiers();
  Qualifiers IncumbentQual = Incumbent.getMethodQualifiers();
  bool CandidateSuperset = CandidateQual.compatiblyIncludes(IncumbentQual);
  bool IncumbentSuperset = IncumbentQual.compatiblyIncludes(CandidateQual);
  if (CandidateSuperset == IncumbentSuperset)
    return OverloadCompare::BothViable;
  return IncumbentSuperset ? OverloadCompare::Dominates
                           : OverloadCompare::Dominated;
}

void ResultBuilder::AddResult(Result R, DeclContext *CurContext,
                              NamedDecl *Hiding, bool InBaseClass = false) {
  if (R.Kind != Result::RK_Declaration) {
    // For non-declaration results, just add the result.
    Results.push_back(R);
    return;
  }

  // Look through using declarations.
  if (const auto *Using = dyn_cast<UsingShadowDecl>(R.Declaration)) {
    CodeCompletionResult Result(Using->getTargetDecl(),
                                getBasePriority(Using->getTargetDecl()),
                                R.Qualifier);
    Result.ShadowDecl = Using;
    AddResult(Result, CurContext, Hiding);
    return;
  }

  bool AsNestedNameSpecifier = false;
  if (!isInterestingDecl(R.Declaration, AsNestedNameSpecifier))
    return;

  // C++ constructors are never found by name lookup.
  if (isConstructor(R.Declaration))
    return;

  if (Hiding && CheckHiddenResult(R, CurContext, Hiding))
    return;

  // Make sure that any given declaration only shows up in the result set once.
  if (!AllDeclsFound.insert(R.Declaration->getCanonicalDecl()).second)
    return;

  // If the filter is for nested-name-specifiers, then this result starts a
  // nested-name-specifier.
  if (AsNestedNameSpecifier) {
    R.StartsNestedNameSpecifier = true;
    R.Priority = CCP_NestedNameSpecifier;
  } else if (Filter == &ResultBuilder::IsMember && !R.Qualifier &&
             InBaseClass &&
             isa<CXXRecordDecl>(
                 R.Declaration->getDeclContext()->getRedeclContext()))
    R.QualifierIsInformative = true;

  // If this result is supposed to have an informative qualifier, add one.
  if (R.QualifierIsInformative && !R.Qualifier &&
      !R.StartsNestedNameSpecifier) {
    const DeclContext *Ctx = R.Declaration->getDeclContext();
    if (const auto *Namespace = dyn_cast<NamespaceDecl>(Ctx))
      R.Qualifier =
          NestedNameSpecifier::Create(SemaRef.Context, nullptr, Namespace);
    else if (const auto *Tag = dyn_cast<TagDecl>(Ctx))
      R.Qualifier = NestedNameSpecifier::Create(
          SemaRef.Context, nullptr, false,
          SemaRef.Context.getTypeDeclType(Tag).getTypePtr());
    else
      R.QualifierIsInformative = false;
  }

  // Adjust the priority if this result comes from a base class.
  if (InBaseClass)
    setInBaseClass(R);

  AdjustResultPriorityForDecl(R);

  if (HasObjectTypeQualifiers)
    if (const auto *Method = dyn_cast<CXXMethodDecl>(R.Declaration))
      if (Method->isInstance()) {
        Qualifiers MethodQuals = Method->getMethodQualifiers();
        if (ObjectTypeQualifiers == MethodQuals)
          R.Priority += CCD_ObjectQualifierMatch;
        else if (ObjectTypeQualifiers - MethodQuals) {
          // The method cannot be invoked, because doing so would drop
          // qualifiers.
          return;
        }
        // Detect cases where a ref-qualified method cannot be invoked.
        switch (Method->getRefQualifier()) {
          case RQ_LValue:
            if (ObjectKind != VK_LValue && !MethodQuals.hasConst())
              return;
            break;
          case RQ_RValue:
            if (ObjectKind == VK_LValue)
              return;
            break;
          case RQ_None:
            break;
        }

        /// Check whether this dominates another overloaded method, which should
        /// be suppressed (or vice versa).
        /// Motivating case is const_iterator begin() const vs iterator begin().
        auto &OverloadSet = OverloadMap[std::make_pair(
            CurContext, Method->getDeclName().getAsOpaqueInteger())];
        for (const DeclIndexPair Entry : OverloadSet) {
          Result &Incumbent = Results[Entry.second];
          switch (compareOverloads(*Method,
                                   *cast<CXXMethodDecl>(Incumbent.Declaration),
                                   ObjectTypeQualifiers, ObjectKind)) {
          case OverloadCompare::Dominates:
            // Replace the dominated overload with this one.
            // FIXME: if the overload dominates multiple incumbents then we
            // should remove all. But two overloads is by far the common case.
            Incumbent = std::move(R);
            return;
          case OverloadCompare::Dominated:
            // This overload can't be called, drop it.
            return;
          case OverloadCompare::BothViable:
            break;
          }
        }
        OverloadSet.Add(Method, Results.size());
      }

  // Insert this result into the set of results.
  Results.push_back(R);

  if (!AsNestedNameSpecifier)
    MaybeAddConstructorResults(R);
}

void ResultBuilder::AddResult(Result R) {
  assert(R.Kind != Result::RK_Declaration &&
         "Declaration results need more context");
  Results.push_back(R);
}

/// Enter into a new scope.
void ResultBuilder::EnterNewScope() { ShadowMaps.emplace_back(); }

/// Exit from the current scope.
void ResultBuilder::ExitScope() {
  ShadowMaps.pop_back();
}

/// Determines whether this given declaration will be found by
/// ordinary name lookup.
bool ResultBuilder::IsOrdinaryName(const NamedDecl *ND) const {
  ND = ND->getUnderlyingDecl();

  // If name lookup finds a local extern declaration, then we are in a
  // context where it behaves like an ordinary name.
  unsigned IDNS = Decl::IDNS_Ordinary | Decl::IDNS_LocalExtern;
  if (SemaRef.getLangOpts().CPlusPlus)
    IDNS |= Decl::IDNS_Tag | Decl::IDNS_Namespace | Decl::IDNS_Member;
  else if (SemaRef.getLangOpts().ObjC) {
    if (isa<ObjCIvarDecl>(ND))
      return true;
  }

  return ND->getIdentifierNamespace() & IDNS;
}

/// Determines whether this given declaration will be found by
/// ordinary name lookup but is not a type name.
bool ResultBuilder::IsOrdinaryNonTypeName(const NamedDecl *ND) const {
  ND = ND->getUnderlyingDecl();
  if (isa<TypeDecl>(ND))
    return false;
  // Objective-C interfaces names are not filtered by this method because they
  // can be used in a class property expression. We can still filter out
  // @class declarations though.
  if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(ND)) {
    if (!ID->getDefinition())
      return false;
  }

  unsigned IDNS = Decl::IDNS_Ordinary | Decl::IDNS_LocalExtern;
  if (SemaRef.getLangOpts().CPlusPlus)
    IDNS |= Decl::IDNS_Tag | Decl::IDNS_Namespace | Decl::IDNS_Member;
  else if (SemaRef.getLangOpts().ObjC) {
    if (isa<ObjCIvarDecl>(ND))
      return true;
  }

  return ND->getIdentifierNamespace() & IDNS;
}

bool ResultBuilder::IsIntegralConstantValue(const NamedDecl *ND) const {
  if (!IsOrdinaryNonTypeName(ND))
    return 0;

  if (const auto *VD = dyn_cast<ValueDecl>(ND->getUnderlyingDecl()))
    if (VD->getType()->isIntegralOrEnumerationType())
      return true;

  return false;
}

/// Determines whether this given declaration will be found by
/// ordinary name lookup.
bool ResultBuilder::IsOrdinaryNonValueName(const NamedDecl *ND) const {
  ND = ND->getUnderlyingDecl();

  unsigned IDNS = Decl::IDNS_Ordinary | Decl::IDNS_LocalExtern;
  if (SemaRef.getLangOpts().CPlusPlus)
    IDNS |= Decl::IDNS_Tag | Decl::IDNS_Namespace;

  return (ND->getIdentifierNamespace() & IDNS) && !isa<ValueDecl>(ND) &&
         !isa<FunctionTemplateDecl>(ND) && !isa<ObjCPropertyDecl>(ND);
}

/// Determines whether the given declaration is suitable as the
/// start of a C++ nested-name-specifier, e.g., a class or namespace.
bool ResultBuilder::IsNestedNameSpecifier(const NamedDecl *ND) const {
  // Allow us to find class templates, too.
  if (const auto *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
    ND = ClassTemplate->getTemplatedDecl();

  return SemaRef.isAcceptableNestedNameSpecifier(ND);
}

/// Determines whether the given declaration is an enumeration.
bool ResultBuilder::IsEnum(const NamedDecl *ND) const {
  return isa<EnumDecl>(ND);
}

/// Determines whether the given declaration is a class or struct.
bool ResultBuilder::IsClassOrStruct(const NamedDecl *ND) const {
  // Allow us to find class templates, too.
  if (const auto *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
    ND = ClassTemplate->getTemplatedDecl();

  // For purposes of this check, interfaces match too.
  if (const auto *RD = dyn_cast<RecordDecl>(ND))
    return RD->getTagKind() == TTK_Class || RD->getTagKind() == TTK_Struct ||
           RD->getTagKind() == TTK_Interface;

  return false;
}

/// Determines whether the given declaration is a union.
bool ResultBuilder::IsUnion(const NamedDecl *ND) const {
  // Allow us to find class templates, too.
  if (const auto *ClassTemplate = dyn_cast<ClassTemplateDecl>(ND))
    ND = ClassTemplate->getTemplatedDecl();

  if (const auto *RD = dyn_cast<RecordDecl>(ND))
    return RD->getTagKind() == TTK_Union;

  return false;
}

/// Determines whether the given declaration is a namespace.
bool ResultBuilder::IsNamespace(const NamedDecl *ND) const {
  return isa<NamespaceDecl>(ND);
}

/// Determines whether the given declaration is a namespace or
/// namespace alias.
bool ResultBuilder::IsNamespaceOrAlias(const NamedDecl *ND) const {
  return isa<NamespaceDecl>(ND->getUnderlyingDecl());
}

/// Determines whether the given declaration is a type.
bool ResultBuilder::IsType(const NamedDecl *ND) const {
  ND = ND->getUnderlyingDecl();
  return isa<TypeDecl>(ND) || isa<ObjCInterfaceDecl>(ND);
}

/// Determines which members of a class should be visible via
/// "." or "->".  Only value declarations, nested name specifiers, and
/// using declarations thereof should show up.
bool ResultBuilder::IsMember(const NamedDecl *ND) const {
  ND = ND->getUnderlyingDecl();
  return isa<ValueDecl>(ND) || isa<FunctionTemplateDecl>(ND) ||
         isa<ObjCPropertyDecl>(ND);
}

static bool isObjCReceiverType(ASTContext &C, QualType T) {
  T = C.getCanonicalType(T);
  switch (T->getTypeClass()) {
  case Type::ObjCObject:
  case Type::ObjCInterface:
  case Type::ObjCObjectPointer:
    return true;

  case Type::Builtin:
    switch (cast<BuiltinType>(T)->getKind()) {
    case BuiltinType::ObjCId:
    case BuiltinType::ObjCClass:
    case BuiltinType::ObjCSel:
      return true;

    default:
      break;
    }
    return false;

  default:
    break;
  }

  if (!C.getLangOpts().CPlusPlus)
    return false;

  // FIXME: We could perform more analysis here to determine whether a
  // particular class type has any conversions to Objective-C types. For now,
  // just accept all class types.
  return T->isDependentType() || T->isRecordType();
}

bool ResultBuilder::IsObjCMessageReceiver(const NamedDecl *ND) const {
  QualType T = getDeclUsageType(SemaRef.Context, ND);
  if (T.isNull())
    return false;

  T = SemaRef.Context.getBaseElementType(T);
  return isObjCReceiverType(SemaRef.Context, T);
}

bool ResultBuilder::IsObjCMessageReceiverOrLambdaCapture(
    const NamedDecl *ND) const {
  if (IsObjCMessageReceiver(ND))
    return true;

  const auto *Var = dyn_cast<VarDecl>(ND);
  if (!Var)
    return false;

  return Var->hasLocalStorage() && !Var->hasAttr<BlocksAttr>();
}

bool ResultBuilder::IsObjCCollection(const NamedDecl *ND) const {
  if ((SemaRef.getLangOpts().CPlusPlus && !IsOrdinaryName(ND)) ||
      (!SemaRef.getLangOpts().CPlusPlus && !IsOrdinaryNonTypeName(ND)))
    return false;

  QualType T = getDeclUsageType(SemaRef.Context, ND);
  if (T.isNull())
    return false;

  T = SemaRef.Context.getBaseElementType(T);
  return T->isObjCObjectType() || T->isObjCObjectPointerType() ||
         T->isObjCIdType() ||
         (SemaRef.getLangOpts().CPlusPlus && T->isRecordType());
}

bool ResultBuilder::IsImpossibleToSatisfy(const NamedDecl *ND) const {
  return false;
}

/// Determines whether the given declaration is an Objective-C
/// instance variable.
bool ResultBuilder::IsObjCIvar(const NamedDecl *ND) const {
  return isa<ObjCIvarDecl>(ND);
}

namespace {

/// Visible declaration consumer that adds a code-completion result
/// for each visible declaration.
class CodeCompletionDeclConsumer : public VisibleDeclConsumer {
  ResultBuilder &Results;
  DeclContext *InitialLookupCtx;
  // NamingClass and BaseType are used for access-checking. See
  // Sema::IsSimplyAccessible for details.
  CXXRecordDecl *NamingClass;
  QualType BaseType;
  std::vector<FixItHint> FixIts;

public:
  CodeCompletionDeclConsumer(
      ResultBuilder &Results, DeclContext *InitialLookupCtx,
      QualType BaseType = QualType(),
      std::vector<FixItHint> FixIts = std::vector<FixItHint>())
      : Results(Results), InitialLookupCtx(InitialLookupCtx),
        FixIts(std::move(FixIts)) {
    NamingClass = llvm::dyn_cast<CXXRecordDecl>(InitialLookupCtx);
    // If BaseType was not provided explicitly, emulate implicit 'this->'.
    if (BaseType.isNull()) {
      auto ThisType = Results.getSema().getCurrentThisType();
      if (!ThisType.isNull()) {
        assert(ThisType->isPointerType());
        BaseType = ThisType->getPointeeType();
        if (!NamingClass)
          NamingClass = BaseType->getAsCXXRecordDecl();
      }
    }
    this->BaseType = BaseType;
  }

  void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, DeclContext *Ctx,
                 bool InBaseClass) override {
    ResultBuilder::Result Result(ND, Results.getBasePriority(ND), nullptr,
                                 false, IsAccessible(ND, Ctx), FixIts);
    Results.AddResult(Result, InitialLookupCtx, Hiding, InBaseClass);
  }

  void EnteredContext(DeclContext *Ctx) override {
    Results.addVisitedContext(Ctx);
  }

private:
  bool IsAccessible(NamedDecl *ND, DeclContext *Ctx) {
    // Naming class to use for access check. In most cases it was provided
    // explicitly (e.g. member access (lhs.foo) or qualified lookup (X::)),
    // for unqualified lookup we fallback to the \p Ctx in which we found the
    // member.
    auto *NamingClass = this->NamingClass;
    QualType BaseType = this->BaseType;
    if (auto *Cls = llvm::dyn_cast_or_null<CXXRecordDecl>(Ctx)) {
      if (!NamingClass)
        NamingClass = Cls;
      // When we emulate implicit 'this->' in an unqualified lookup, we might
      // end up with an invalid naming class. In that case, we avoid emulating
      // 'this->' qualifier to satisfy preconditions of the access checking.
      if (NamingClass->getCanonicalDecl() != Cls->getCanonicalDecl() &&
          !NamingClass->isDerivedFrom(Cls)) {
        NamingClass = Cls;
        BaseType = QualType();
      }
    } else {
      // The decl was found outside the C++ class, so only ObjC access checks
      // apply. Those do not rely on NamingClass and BaseType, so we clear them
      // out.
      NamingClass = nullptr;
      BaseType = QualType();
    }
    return Results.getSema().IsSimplyAccessible(ND, NamingClass, BaseType);
  }
};
} // namespace

/// Add type specifiers for the current language as keyword results.
static void AddTypeSpecifierResults(const LangOptions &LangOpts,
                                    ResultBuilder &Results) {
  typedef CodeCompletionResult Result;
  Results.AddResult(Result("short", CCP_Type));
  Results.AddResult(Result("long", CCP_Type));
  Results.AddResult(Result("signed", CCP_Type));
  Results.AddResult(Result("unsigned", CCP_Type));
  Results.AddResult(Result("void", CCP_Type));
  Results.AddResult(Result("char", CCP_Type));
  Results.AddResult(Result("int", CCP_Type));
  Results.AddResult(Result("float", CCP_Type));
  Results.AddResult(Result("double", CCP_Type));
  Results.AddResult(Result("enum", CCP_Type));
  Results.AddResult(Result("struct", CCP_Type));
  Results.AddResult(Result("union", CCP_Type));
  Results.AddResult(Result("const", CCP_Type));
  Results.AddResult(Result("volatile", CCP_Type));

  if (LangOpts.C99) {
    // C99-specific
    Results.AddResult(Result("_Complex", CCP_Type));
    Results.AddResult(Result("_Imaginary", CCP_Type));
    Results.AddResult(Result("_Bool", CCP_Type));
    Results.AddResult(Result("restrict", CCP_Type));
  }

  CodeCompletionBuilder Builder(Results.getAllocator(),
                                Results.getCodeCompletionTUInfo());
  if (LangOpts.CPlusPlus) {
    // C++-specific
    Results.AddResult(
        Result("bool", CCP_Type + (LangOpts.ObjC ? CCD_bool_in_ObjC : 0)));
    Results.AddResult(Result("class", CCP_Type));
    Results.AddResult(Result("wchar_t", CCP_Type));

    // typename name
    Builder.AddTypedTextChunk("typename");
    Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
    Builder.AddPlaceholderChunk("name");
    Results.AddResult(Result(Builder.TakeString()));

    if (LangOpts.CPlusPlus11) {
      Results.AddResult(Result("auto", CCP_Type));
      Results.AddResult(Result("char16_t", CCP_Type));
      Results.AddResult(Result("char32_t", CCP_Type));

      Builder.AddTypedTextChunk("decltype");
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));
    }
  } else
    Results.AddResult(Result("__auto_type", CCP_Type));

  // GNU keywords
  if (LangOpts.GNUKeywords) {
    // FIXME: Enable when we actually support decimal floating point.
    //    Results.AddResult(Result("_Decimal32"));
    //    Results.AddResult(Result("_Decimal64"));
    //    Results.AddResult(Result("_Decimal128"));

    Builder.AddTypedTextChunk("typeof");
    Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
    Builder.AddPlaceholderChunk("expression");
    Results.AddResult(Result(Builder.TakeString()));

    Builder.AddTypedTextChunk("typeof");
    Builder.AddChunk(CodeCompletionString::CK_LeftParen);
    Builder.AddPlaceholderChunk("type");
    Builder.AddChunk(CodeCompletionString::CK_RightParen);
    Results.AddResult(Result(Builder.TakeString()));
  }

  // Nullability
  Results.AddResult(Result("_Nonnull", CCP_Type));
  Results.AddResult(Result("_Null_unspecified", CCP_Type));
  Results.AddResult(Result("_Nullable", CCP_Type));
}

static void AddStorageSpecifiers(Sema::ParserCompletionContext CCC,
                                 const LangOptions &LangOpts,
                                 ResultBuilder &Results) {
  typedef CodeCompletionResult Result;
  // Note: we don't suggest either "auto" or "register", because both
  // are pointless as storage specifiers. Elsewhere, we suggest "auto"
  // in C++0x as a type specifier.
  Results.AddResult(Result("extern"));
  Results.AddResult(Result("static"));

  if (LangOpts.CPlusPlus11) {
    CodeCompletionAllocator &Allocator = Results.getAllocator();
    CodeCompletionBuilder Builder(Allocator, Results.getCodeCompletionTUInfo());

    // alignas
    Builder.AddTypedTextChunk("alignas");
    Builder.AddChunk(CodeCompletionString::CK_LeftParen);
    Builder.AddPlaceholderChunk("expression");
    Builder.AddChunk(CodeCompletionString::CK_RightParen);
    Results.AddResult(Result(Builder.TakeString()));

    Results.AddResult(Result("constexpr"));
    Results.AddResult(Result("thread_local"));
  }
}

static void AddFunctionSpecifiers(Sema::ParserCompletionContext CCC,
                                  const LangOptions &LangOpts,
                                  ResultBuilder &Results) {
  typedef CodeCompletionResult Result;
  switch (CCC) {
  case Sema::PCC_Class:
  case Sema::PCC_MemberTemplate:
    if (LangOpts.CPlusPlus) {
      Results.AddResult(Result("explicit"));
      Results.AddResult(Result("friend"));
      Results.AddResult(Result("mutable"));
      Results.AddResult(Result("virtual"));
    }
    LLVM_FALLTHROUGH;

  case Sema::PCC_ObjCInterface:
  case Sema::PCC_ObjCImplementation:
  case Sema::PCC_Namespace:
  case Sema::PCC_Template:
    if (LangOpts.CPlusPlus || LangOpts.C99)
      Results.AddResult(Result("inline"));
    break;

  case Sema::PCC_ObjCInstanceVariableList:
  case Sema::PCC_Expression:
  case Sema::PCC_Statement:
  case Sema::PCC_ForInit:
  case Sema::PCC_Condition:
  case Sema::PCC_RecoveryInFunction:
  case Sema::PCC_Type:
  case Sema::PCC_ParenthesizedExpression:
  case Sema::PCC_LocalDeclarationSpecifiers:
    break;
  }
}

static void AddObjCExpressionResults(ResultBuilder &Results, bool NeedAt);
static void AddObjCStatementResults(ResultBuilder &Results, bool NeedAt);
static void AddObjCVisibilityResults(const LangOptions &LangOpts,
                                     ResultBuilder &Results, bool NeedAt);
static void AddObjCImplementationResults(const LangOptions &LangOpts,
                                         ResultBuilder &Results, bool NeedAt);
static void AddObjCInterfaceResults(const LangOptions &LangOpts,
                                    ResultBuilder &Results, bool NeedAt);
static void AddObjCTopLevelResults(ResultBuilder &Results, bool NeedAt);

static void AddTypedefResult(ResultBuilder &Results) {
  CodeCompletionBuilder Builder(Results.getAllocator(),
                                Results.getCodeCompletionTUInfo());
  Builder.AddTypedTextChunk("typedef");
  Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
  Builder.AddPlaceholderChunk("type");
  Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
  Builder.AddPlaceholderChunk("name");
  Builder.AddChunk(CodeCompletionString::CK_SemiColon);
  Results.AddResult(CodeCompletionResult(Builder.TakeString()));
}

// using name = type
static void AddUsingAliasResult(CodeCompletionBuilder &Builder,
                                ResultBuilder &Results) {
  Builder.AddTypedTextChunk("using");
  Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
  Builder.AddPlaceholderChunk("name");
  Builder.AddChunk(CodeCompletionString::CK_Equal);
  Builder.AddPlaceholderChunk("type");
  Builder.AddChunk(CodeCompletionString::CK_SemiColon);
  Results.AddResult(CodeCompletionResult(Builder.TakeString()));
}

static bool WantTypesInContext(Sema::ParserCompletionContext CCC,
                               const LangOptions &LangOpts) {
  switch (CCC) {
  case Sema::PCC_Namespace:
  case Sema::PCC_Class:
  case Sema::PCC_ObjCInstanceVariableList:
  case Sema::PCC_Template:
  case Sema::PCC_MemberTemplate:
  case Sema::PCC_Statement:
  case Sema::PCC_RecoveryInFunction:
  case Sema::PCC_Type:
  case Sema::PCC_ParenthesizedExpression:
  case Sema::PCC_LocalDeclarationSpecifiers:
    return true;

  case Sema::PCC_Expression:
  case Sema::PCC_Condition:
    return LangOpts.CPlusPlus;

  case Sema::PCC_ObjCInterface:
  case Sema::PCC_ObjCImplementation:
    return false;

  case Sema::PCC_ForInit:
    return LangOpts.CPlusPlus || LangOpts.ObjC || LangOpts.C99;
  }

  llvm_unreachable("Invalid ParserCompletionContext!");
}

static PrintingPolicy getCompletionPrintingPolicy(const ASTContext &Context,
                                                  const Preprocessor &PP) {
  PrintingPolicy Policy = Sema::getPrintingPolicy(Context, PP);
  Policy.AnonymousTagLocations = false;
  Policy.SuppressStrongLifetime = true;
  Policy.SuppressUnwrittenScope = true;
  Policy.SuppressScope = true;
  return Policy;
}

/// Retrieve a printing policy suitable for code completion.
static PrintingPolicy getCompletionPrintingPolicy(Sema &S) {
  return getCompletionPrintingPolicy(S.Context, S.PP);
}

/// Retrieve the string representation of the given type as a string
/// that has the appropriate lifetime for code completion.
///
/// This routine provides a fast path where we provide constant strings for
/// common type names.
static const char *GetCompletionTypeString(QualType T, ASTContext &Context,
                                           const PrintingPolicy &Policy,
                                           CodeCompletionAllocator &Allocator) {
  if (!T.getLocalQualifiers()) {
    // Built-in type names are constant strings.
    if (const BuiltinType *BT = dyn_cast<BuiltinType>(T))
      return BT->getNameAsCString(Policy);

    // Anonymous tag types are constant strings.
    if (const TagType *TagT = dyn_cast<TagType>(T))
      if (TagDecl *Tag = TagT->getDecl())
        if (!Tag->hasNameForLinkage()) {
          switch (Tag->getTagKind()) {
          case TTK_Struct:
            return "struct <anonymous>";
          case TTK_Interface:
            return "__interface <anonymous>";
          case TTK_Class:
            return "class <anonymous>";
          case TTK_Union:
            return "union <anonymous>";
          case TTK_Enum:
            return "enum <anonymous>";
          }
        }
  }

  // Slow path: format the type as a string.
  std::string Result;
  T.getAsStringInternal(Result, Policy);
  return Allocator.CopyString(Result);
}

/// Add a completion for "this", if we're in a member function.
static void addThisCompletion(Sema &S, ResultBuilder &Results) {
  QualType ThisTy = S.getCurrentThisType();
  if (ThisTy.isNull())
    return;

  CodeCompletionAllocator &Allocator = Results.getAllocator();
  CodeCompletionBuilder Builder(Allocator, Results.getCodeCompletionTUInfo());
  PrintingPolicy Policy = getCompletionPrintingPolicy(S);
  Builder.AddResultTypeChunk(
      GetCompletionTypeString(ThisTy, S.Context, Policy, Allocator));
  Builder.AddTypedTextChunk("this");
  Results.AddResult(CodeCompletionResult(Builder.TakeString()));
}

static void AddStaticAssertResult(CodeCompletionBuilder &Builder,
                                  ResultBuilder &Results,
                                  const LangOptions &LangOpts) {
  if (!LangOpts.CPlusPlus11)
    return;

  Builder.AddTypedTextChunk("static_assert");
  Builder.AddChunk(CodeCompletionString::CK_LeftParen);
  Builder.AddPlaceholderChunk("expression");
  Builder.AddChunk(CodeCompletionString::CK_Comma);
  Builder.AddPlaceholderChunk("message");
  Builder.AddChunk(CodeCompletionString::CK_RightParen);
  Builder.AddChunk(CodeCompletionString::CK_SemiColon);
  Results.AddResult(CodeCompletionResult(Builder.TakeString()));
}

static void AddOverrideResults(ResultBuilder &Results,
                               const CodeCompletionContext &CCContext,
                               CodeCompletionBuilder &Builder) {
  Sema &S = Results.getSema();
  const auto *CR = llvm::dyn_cast<CXXRecordDecl>(S.CurContext);
  // If not inside a class/struct/union return empty.
  if (!CR)
    return;
  // First store overrides within current class.
  // These are stored by name to make querying fast in the later step.
  llvm::StringMap<std::vector<FunctionDecl *>> Overrides;
  for (auto *Method : CR->methods()) {
    if (!Method->isVirtual() || !Method->getIdentifier())
      continue;
    Overrides[Method->getName()].push_back(Method);
  }

  for (const auto &Base : CR->bases()) {
    const auto *BR = Base.getType().getTypePtr()->getAsCXXRecordDecl();
    if (!BR)
      continue;
    for (auto *Method : BR->methods()) {
      if (!Method->isVirtual() || !Method->getIdentifier())
        continue;
      const auto it = Overrides.find(Method->getName());
      bool IsOverriden = false;
      if (it != Overrides.end()) {
        for (auto *MD : it->second) {
          // If the method in current body is not an overload of this virtual
          // function, then it overrides this one.
          if (!S.IsOverload(MD, Method, false)) {
            IsOverriden = true;
            break;
          }
        }
      }
      if (!IsOverriden) {
        // Generates a new CodeCompletionResult by taking this function and
        // converting it into an override declaration with only one chunk in the
        // final CodeCompletionString as a TypedTextChunk.
        std::string OverrideSignature;
        llvm::raw_string_ostream OS(OverrideSignature);
        CodeCompletionResult CCR(Method, 0);
        PrintingPolicy Policy =
            getCompletionPrintingPolicy(S.getASTContext(), S.getPreprocessor());
        auto *CCS = CCR.createCodeCompletionStringForOverride(
            S.getPreprocessor(), S.getASTContext(), Builder,
            /*IncludeBriefComments=*/false, CCContext, Policy);
        Results.AddResult(CodeCompletionResult(CCS, Method, CCP_CodePattern));
      }
    }
  }
}

/// Add language constructs that show up for "ordinary" names.
static void AddOrdinaryNameResults(Sema::ParserCompletionContext CCC, Scope *S,
                                   Sema &SemaRef, ResultBuilder &Results) {
  CodeCompletionAllocator &Allocator = Results.getAllocator();
  CodeCompletionBuilder Builder(Allocator, Results.getCodeCompletionTUInfo());

  typedef CodeCompletionResult Result;
  switch (CCC) {
  case Sema::PCC_Namespace:
    if (SemaRef.getLangOpts().CPlusPlus) {
      if (Results.includeCodePatterns()) {
        // namespace <identifier> { declarations }
        Builder.AddTypedTextChunk("namespace");
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddPlaceholderChunk("identifier");
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
        Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
        Builder.AddPlaceholderChunk("declarations");
        Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
        Builder.AddChunk(CodeCompletionString::CK_RightBrace);
        Results.AddResult(Result(Builder.TakeString()));
      }

      // namespace identifier = identifier ;
      Builder.AddTypedTextChunk("namespace");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("name");
      Builder.AddChunk(CodeCompletionString::CK_Equal);
      Builder.AddPlaceholderChunk("namespace");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Results.AddResult(Result(Builder.TakeString()));

      // Using directives
      Builder.AddTypedTextChunk("using namespace");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("identifier");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Results.AddResult(Result(Builder.TakeString()));

      // asm(string-literal)
      Builder.AddTypedTextChunk("asm");
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("string-literal");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));

      if (Results.includeCodePatterns()) {
        // Explicit template instantiation
        Builder.AddTypedTextChunk("template");
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddPlaceholderChunk("declaration");
        Results.AddResult(Result(Builder.TakeString()));
      } else {
        Results.AddResult(Result("template", CodeCompletionResult::RK_Keyword));
      }
    }

    if (SemaRef.getLangOpts().ObjC)
      AddObjCTopLevelResults(Results, true);

    AddTypedefResult(Results);
    LLVM_FALLTHROUGH;

  case Sema::PCC_Class:
    if (SemaRef.getLangOpts().CPlusPlus) {
      // Using declaration
      Builder.AddTypedTextChunk("using");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("qualifier");
      Builder.AddTextChunk("::");
      Builder.AddPlaceholderChunk("name");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Results.AddResult(Result(Builder.TakeString()));

      if (SemaRef.getLangOpts().CPlusPlus11)
        AddUsingAliasResult(Builder, Results);

      // using typename qualifier::name (only in a dependent context)
      if (SemaRef.CurContext->isDependentContext()) {
        Builder.AddTypedTextChunk("using typename");
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddPlaceholderChunk("qualifier");
        Builder.AddTextChunk("::");
        Builder.AddPlaceholderChunk("name");
        Builder.AddChunk(CodeCompletionString::CK_SemiColon);
        Results.AddResult(Result(Builder.TakeString()));
      }

      AddStaticAssertResult(Builder, Results, SemaRef.getLangOpts());

      if (CCC == Sema::PCC_Class) {
        AddTypedefResult(Results);

        bool IsNotInheritanceScope =
            !(S->getFlags() & Scope::ClassInheritanceScope);
        // public:
        Builder.AddTypedTextChunk("public");
        if (IsNotInheritanceScope && Results.includeCodePatterns())
          Builder.AddChunk(CodeCompletionString::CK_Colon);
        Results.AddResult(Result(Builder.TakeString()));

        // protected:
        Builder.AddTypedTextChunk("protected");
        if (IsNotInheritanceScope && Results.includeCodePatterns())
          Builder.AddChunk(CodeCompletionString::CK_Colon);
        Results.AddResult(Result(Builder.TakeString()));

        // private:
        Builder.AddTypedTextChunk("private");
        if (IsNotInheritanceScope && Results.includeCodePatterns())
          Builder.AddChunk(CodeCompletionString::CK_Colon);
        Results.AddResult(Result(Builder.TakeString()));

        // FIXME: This adds override results only if we are at the first word of
        // the declaration/definition. Also call this from other sides to have
        // more use-cases.
        AddOverrideResults(Results, CodeCompletionContext::CCC_ClassStructUnion,
                           Builder);
      }
    }
    LLVM_FALLTHROUGH;

  case Sema::PCC_Template:
  case Sema::PCC_MemberTemplate:
    if (SemaRef.getLangOpts().CPlusPlus && Results.includeCodePatterns()) {
      // template < parameters >
      Builder.AddTypedTextChunk("template");
      Builder.AddChunk(CodeCompletionString::CK_LeftAngle);
      Builder.AddPlaceholderChunk("parameters");
      Builder.AddChunk(CodeCompletionString::CK_RightAngle);
      Results.AddResult(Result(Builder.TakeString()));
    } else {
      Results.AddResult(Result("template", CodeCompletionResult::RK_Keyword));
    }

    AddStorageSpecifiers(CCC, SemaRef.getLangOpts(), Results);
    AddFunctionSpecifiers(CCC, SemaRef.getLangOpts(), Results);
    break;

  case Sema::PCC_ObjCInterface:
    AddObjCInterfaceResults(SemaRef.getLangOpts(), Results, true);
    AddStorageSpecifiers(CCC, SemaRef.getLangOpts(), Results);
    AddFunctionSpecifiers(CCC, SemaRef.getLangOpts(), Results);
    break;

  case Sema::PCC_ObjCImplementation:
    AddObjCImplementationResults(SemaRef.getLangOpts(), Results, true);
    AddStorageSpecifiers(CCC, SemaRef.getLangOpts(), Results);
    AddFunctionSpecifiers(CCC, SemaRef.getLangOpts(), Results);
    break;

  case Sema::PCC_ObjCInstanceVariableList:
    AddObjCVisibilityResults(SemaRef.getLangOpts(), Results, true);
    break;

  case Sema::PCC_RecoveryInFunction:
  case Sema::PCC_Statement: {
    if (SemaRef.getLangOpts().CPlusPlus11)
      AddUsingAliasResult(Builder, Results);

    AddTypedefResult(Results);

    if (SemaRef.getLangOpts().CPlusPlus && Results.includeCodePatterns() &&
        SemaRef.getLangOpts().CXXExceptions) {
      Builder.AddTypedTextChunk("try");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddPlaceholderChunk("statements");
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddChunk(CodeCompletionString::CK_RightBrace);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddTextChunk("catch");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("declaration");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddPlaceholderChunk("statements");
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddChunk(CodeCompletionString::CK_RightBrace);
      Results.AddResult(Result(Builder.TakeString()));
    }
    if (SemaRef.getLangOpts().ObjC)
      AddObjCStatementResults(Results, true);

    if (Results.includeCodePatterns()) {
      // if (condition) { statements }
      Builder.AddTypedTextChunk("if");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      if (SemaRef.getLangOpts().CPlusPlus)
        Builder.AddPlaceholderChunk("condition");
      else
        Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddPlaceholderChunk("statements");
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddChunk(CodeCompletionString::CK_RightBrace);
      Results.AddResult(Result(Builder.TakeString()));

      // switch (condition) { }
      Builder.AddTypedTextChunk("switch");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      if (SemaRef.getLangOpts().CPlusPlus)
        Builder.AddPlaceholderChunk("condition");
      else
        Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddPlaceholderChunk("cases");
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddChunk(CodeCompletionString::CK_RightBrace);
      Results.AddResult(Result(Builder.TakeString()));
    }

    // Switch-specific statements.
    if (SemaRef.getCurFunction() &&
        !SemaRef.getCurFunction()->SwitchStack.empty()) {
      // case expression:
      Builder.AddTypedTextChunk("case");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_Colon);
      Results.AddResult(Result(Builder.TakeString()));

      // default:
      Builder.AddTypedTextChunk("default");
      Builder.AddChunk(CodeCompletionString::CK_Colon);
      Results.AddResult(Result(Builder.TakeString()));
    }

    if (Results.includeCodePatterns()) {
      /// while (condition) { statements }
      Builder.AddTypedTextChunk("while");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      if (SemaRef.getLangOpts().CPlusPlus)
        Builder.AddPlaceholderChunk("condition");
      else
        Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddPlaceholderChunk("statements");
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddChunk(CodeCompletionString::CK_RightBrace);
      Results.AddResult(Result(Builder.TakeString()));

      // do { statements } while ( expression );
      Builder.AddTypedTextChunk("do");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddPlaceholderChunk("statements");
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddChunk(CodeCompletionString::CK_RightBrace);
      Builder.AddTextChunk("while");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));

      // for ( for-init-statement ; condition ; expression ) { statements }
      Builder.AddTypedTextChunk("for");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      if (SemaRef.getLangOpts().CPlusPlus || SemaRef.getLangOpts().C99)
        Builder.AddPlaceholderChunk("init-statement");
      else
        Builder.AddPlaceholderChunk("init-expression");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("condition");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("inc-expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddPlaceholderChunk("statements");
      Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
      Builder.AddChunk(CodeCompletionString::CK_RightBrace);
      Results.AddResult(Result(Builder.TakeString()));

      if (SemaRef.getLangOpts().CPlusPlus11 || SemaRef.getLangOpts().ObjC) {
        // for ( range_declaration (:|in) range_expression ) { statements }
        Builder.AddTypedTextChunk("for");
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddChunk(CodeCompletionString::CK_LeftParen);
        Builder.AddPlaceholderChunk("range-declaration");
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        if (SemaRef.getLangOpts().ObjC)
          Builder.AddTextChunk("in");
        else
          Builder.AddChunk(CodeCompletionString::CK_Colon);
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddPlaceholderChunk("range-expression");
        Builder.AddChunk(CodeCompletionString::CK_RightParen);
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddChunk(CodeCompletionString::CK_LeftBrace);
        Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
        Builder.AddPlaceholderChunk("statements");
        Builder.AddChunk(CodeCompletionString::CK_VerticalSpace);
        Builder.AddChunk(CodeCompletionString::CK_RightBrace);
        Results.AddResult(Result(Builder.TakeString()));
      }
    }

    if (S->getContinueParent()) {
      // continue ;
      Builder.AddTypedTextChunk("continue");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Results.AddResult(Result(Builder.TakeString()));
    }

    if (S->getBreakParent()) {
      // break ;
      Builder.AddTypedTextChunk("break");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Results.AddResult(Result(Builder.TakeString()));
    }

    // "return expression ;" or "return ;", depending on the return type.
    QualType ReturnType;
    if (const auto *Function = dyn_cast<FunctionDecl>(SemaRef.CurContext))
      ReturnType = Function->getReturnType();
    else if (const auto *Method = dyn_cast<ObjCMethodDecl>(SemaRef.CurContext))
      ReturnType = Method->getReturnType();
    else if (SemaRef.getCurBlock() &&
             !SemaRef.getCurBlock()->ReturnType.isNull())
      ReturnType = SemaRef.getCurBlock()->ReturnType;;
    if (ReturnType.isNull() || ReturnType->isVoidType()) {
      Builder.AddTypedTextChunk("return");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Results.AddResult(Result(Builder.TakeString()));
    } else {
      assert(!ReturnType.isNull());
      // "return expression ;"
      Builder.AddTypedTextChunk("return");
      Builder.AddChunk(clang::CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_SemiColon);
      Results.AddResult(Result(Builder.TakeString()));
      // When boolean, also add 'return true;' and 'return false;'.
      if (ReturnType->isBooleanType()) {
        Builder.AddTypedTextChunk("return true");
        Builder.AddChunk(CodeCompletionString::CK_SemiColon);
        Results.AddResult(Result(Builder.TakeString()));

        Builder.AddTypedTextChunk("return false");
        Builder.AddChunk(CodeCompletionString::CK_SemiColon);
        Results.AddResult(Result(Builder.TakeString()));
      }
      // For pointers, suggest 'return nullptr' in C++.
      if (SemaRef.getLangOpts().CPlusPlus11 &&
          (ReturnType->isPointerType() || ReturnType->isMemberPointerType())) {
        Builder.AddTypedTextChunk("return nullptr");
        Builder.AddChunk(CodeCompletionString::CK_SemiColon);
        Results.AddResult(Result(Builder.TakeString()));
      }
    }

    // goto identifier ;
    Builder.AddTypedTextChunk("goto");
    Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
    Builder.AddPlaceholderChunk("label");
    Builder.AddChunk(CodeCompletionString::CK_SemiColon);
    Results.AddResult(Result(Builder.TakeString()));

    // Using directives
    Builder.AddTypedTextChunk("using namespace");
    Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
    Builder.AddPlaceholderChunk("identifier");
    Builder.AddChunk(CodeCompletionString::CK_SemiColon);
    Results.AddResult(Result(Builder.TakeString()));

    AddStaticAssertResult(Builder, Results, SemaRef.getLangOpts());
  }
    LLVM_FALLTHROUGH;

  // Fall through (for statement expressions).
  case Sema::PCC_ForInit:
  case Sema::PCC_Condition:
    AddStorageSpecifiers(CCC, SemaRef.getLangOpts(), Results);
    // Fall through: conditions and statements can have expressions.
    LLVM_FALLTHROUGH;

  case Sema::PCC_ParenthesizedExpression:
    if (SemaRef.getLangOpts().ObjCAutoRefCount &&
        CCC == Sema::PCC_ParenthesizedExpression) {
      // (__bridge <type>)<expression>
      Builder.AddTypedTextChunk("__bridge");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("type");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddPlaceholderChunk("expression");
      Results.AddResult(Result(Builder.TakeString()));

      // (__bridge_transfer <Objective-C type>)<expression>
      Builder.AddTypedTextChunk("__bridge_transfer");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("Objective-C type");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddPlaceholderChunk("expression");
      Results.AddResult(Result(Builder.TakeString()));

      // (__bridge_retained <CF type>)<expression>
      Builder.AddTypedTextChunk("__bridge_retained");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("CF type");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Builder.AddPlaceholderChunk("expression");
      Results.AddResult(Result(Builder.TakeString()));
    }
    // Fall through
    LLVM_FALLTHROUGH;

  case Sema::PCC_Expression: {
    if (SemaRef.getLangOpts().CPlusPlus) {
      // 'this', if we're in a non-static member function.
      addThisCompletion(SemaRef, Results);

      // true
      Builder.AddResultTypeChunk("bool");
      Builder.AddTypedTextChunk("true");
      Results.AddResult(Result(Builder.TakeString()));

      // false
      Builder.AddResultTypeChunk("bool");
      Builder.AddTypedTextChunk("false");
      Results.AddResult(Result(Builder.TakeString()));

      if (SemaRef.getLangOpts().RTTI) {
        // dynamic_cast < type-id > ( expression )
        Builder.AddTypedTextChunk("dynamic_cast");
        Builder.AddChunk(CodeCompletionString::CK_LeftAngle);
        Builder.AddPlaceholderChunk("type");
        Builder.AddChunk(CodeCompletionString::CK_RightAngle);
        Builder.AddChunk(CodeCompletionString::CK_LeftParen);
        Builder.AddPlaceholderChunk("expression");
        Builder.AddChunk(CodeCompletionString::CK_RightParen);
        Results.AddResult(Result(Builder.TakeString()));
      }

      // static_cast < type-id > ( expression )
      Builder.AddTypedTextChunk("static_cast");
      Builder.AddChunk(CodeCompletionString::CK_LeftAngle);
      Builder.AddPlaceholderChunk("type");
      Builder.AddChunk(CodeCompletionString::CK_RightAngle);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));

      // reinterpret_cast < type-id > ( expression )
      Builder.AddTypedTextChunk("reinterpret_cast");
      Builder.AddChunk(CodeCompletionString::CK_LeftAngle);
      Builder.AddPlaceholderChunk("type");
      Builder.AddChunk(CodeCompletionString::CK_RightAngle);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));

      // const_cast < type-id > ( expression )
      Builder.AddTypedTextChunk("const_cast");
      Builder.AddChunk(CodeCompletionString::CK_LeftAngle);
      Builder.AddPlaceholderChunk("type");
      Builder.AddChunk(CodeCompletionString::CK_RightAngle);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("expression");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));

      if (SemaRef.getLangOpts().RTTI) {
        // typeid ( expression-or-type )
        Builder.AddResultTypeChunk("std::type_info");
        Builder.AddTypedTextChunk("typeid");
        Builder.AddChunk(CodeCompletionString::CK_LeftParen);
        Builder.AddPlaceholderChunk("expression-or-type");
        Builder.AddChunk(CodeCompletionString::CK_RightParen);
        Results.AddResult(Result(Builder.TakeString()));
      }

      // new T ( ... )
      Builder.AddTypedTextChunk("new");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("type");
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("expressions");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));

      // new T [ ] ( ... )
      Builder.AddTypedTextChunk("new");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("type");
      Builder.AddChunk(CodeCompletionString::CK_LeftBracket);
      Builder.AddPlaceholderChunk("size");
      Builder.AddChunk(CodeCompletionString::CK_RightBracket);
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("expressions");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));

      // delete expression
      Builder.AddResultTypeChunk("void");
      Builder.AddTypedTextChunk("delete");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("expression");
      Results.AddResult(Result(Builder.TakeString()));

      // delete [] expression
      Builder.AddResultTypeChunk("void");
      Builder.AddTypedTextChunk("delete");
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddChunk(CodeCompletionString::CK_LeftBracket);
      Builder.AddChunk(CodeCompletionString::CK_RightBracket);
      Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
      Builder.AddPlaceholderChunk("expression");
      Results.AddResult(Result(Builder.TakeString()));

      if (SemaRef.getLangOpts().CXXExceptions) {
        // throw expression
        Builder.AddResultTypeChunk("void");
        Builder.AddTypedTextChunk("throw");
        Builder.AddChunk(CodeCompletionString::CK_HorizontalSpace);
        Builder.AddPlaceholderChunk("expression");
        Results.AddResult(Result(Builder.TakeString()));
      }

      // FIXME: Rethrow?

      if (SemaRef.getLangOpts().CPlusPlus11) {
        // nullptr
        Builder.AddResultTypeChunk("std::nullptr_t");
        Builder.AddTypedTextChunk("nullptr");
        Results.AddResult(Result(Builder.TakeString()));

        // alignof
        Builder.AddResultTypeChunk("size_t");
        Builder.AddTypedTextChunk("alignof");
        Builder.AddChunk(CodeCompletionString::CK_LeftParen);
        Builder.AddPlaceholderChunk("type");
        Builder.AddChunk(CodeCompletionString::CK_RightParen);
        Results.AddResult(Result(Builder.TakeString()));

        // noexcept
        Builder.AddResultTypeChunk("bool");
        Builder.AddTypedTextChunk("noexcept");
        Builder.AddChunk(CodeCompletionString::CK_LeftParen);
        Builder.AddPlaceholderChunk("expression");
        Builder.AddChunk(CodeCompletionString::CK_RightParen);
        Results.AddResult(Result(Builder.TakeString()));

        // sizeof... expression
        Builder.AddResultTypeChunk("size_t");
        Builder.AddTypedTextChunk("sizeof...");
        Builder.AddChunk(CodeCompletionString::CK_LeftParen);
        Builder.AddPlaceholderChunk("parameter-pack");
        Builder.AddChunk(CodeCompletionString::CK_RightParen);
        Results.AddResult(Result(Builder.TakeString()));
      }
    }

    if (SemaRef.getLangOpts().ObjC) {
      // Add "super", if we're in an Objective-C class with a superclass.
      if (ObjCMethodDecl *Method = SemaRef.getCurMethodDecl()) {
        // The interface can be NULL.
        if (ObjCInterfaceDecl *ID = Method->getClassInterface())
          if (ID->getSuperClass()) {
            std::string SuperType;
            SuperType = ID->getSuperClass()->getNameAsString();
            if (Method->isInstanceMethod())
              SuperType += " *";

            Builder.AddResultTypeChunk(Allocator.CopyString(SuperType));
            Builder.AddTypedTextChunk("super");
            Results.AddResult(Result(Builder.TakeString()));
          }
      }

      AddObjCExpressionResults(Results, true);
    }

    if (SemaRef.getLangOpts().C11) {
      // _Alignof
      Builder.AddResultTypeChunk("size_t");
      if (SemaRef.PP.isMacroDefined("alignof"))
        Builder.AddTypedTextChunk("alignof");
      else
        Builder.AddTypedTextChunk("_Alignof");
      Builder.AddChunk(CodeCompletionString::CK_LeftParen);
      Builder.AddPlaceholderChunk("type");
      Builder.AddChunk(CodeCompletionString::CK_RightParen);
      Results.AddResult(Result(Builder.TakeString()));
    }

    // sizeof expression
    Builder.AddResultTypeChunk("size_t");
    Builder.AddTypedTextChunk("sizeof");
    Builder.AddChunk(CodeCompletionString::CK_LeftParen);
    Builder.AddPlaceholderChunk("expression-or-type");
    Builder.AddChunk(CodeCompletionString::CK_RightParen);
    Results.AddResult(Result(Builder.TakeString()));
    break;
  }

  case Sema::PCC_Type:
  case Sema::PCC_LocalDeclarationSpecifiers:
    break;
  }

  if (WantTypesInContext(CCC, SemaRef.getLangOpts()))
    AddTypeSpecifierResults(SemaRef.getLangOpts(), Results);

  if (SemaRef.getLangOpts().CPlusPlus && CCC != Sema::PCC_Type)
    Results.AddResult(Result("operator"));
}

/// If the given declaration has an associated type, add it as a result
/// type chunk.
static void AddResultTypeChunk(ASTContext &Context,
                               const PrintingPolicy &Policy,
                               const NamedDecl *ND, QualType BaseType,
                               CodeCompletionBuilder &Result) {
  if (!ND)
    return;

  // Skip constructors and conversion functions, which have their return types
  // built into their names.
  if (isConstructor(ND) || isa<CXXConversionDecl>(ND))
    return;

  // Determine the type of the declaration (if it has a type).
  QualType T;
  if (const FunctionDecl *Function = ND->getAsFunction())
    T = Function->getReturnType();
  else if (const auto *Method = dyn_cast<ObjCMethodDecl>(ND)) {
    if (!BaseType.isNull())
      T = Method->getSendResultType(BaseType);
    else
      T = Method->getReturnType();
  } else if (const auto *Enumerator = dyn_cast<EnumConstantDecl>(ND)) {
    T = Context.getTypeDeclType(cast<TypeDecl>(Enumerator->getDeclContext()));
    T = clang::TypeName::getFullyQualifiedType(T, Context);
  } else if (isa<UnresolvedUsingValueDecl>(ND)) {
    /* Do nothing: ignore unresolved using declarations*/
  } else if (const auto *Ivar = dyn_cast<ObjCIvarDecl>(ND)) {
    if (!BaseType.isNull())
      T = Ivar->getUsageType(BaseType);
    else
      T = Ivar->getType();
  } else if (const auto *Value = dyn_cast<ValueDecl>(ND)) {
    T = Value->getType();
  } else if (const auto *Property = dyn_cast<ObjCPropertyDecl>(ND)) {
    if (!BaseType.isNull())
      T = Property->getUsageType(BaseType);
    else
      T = Property->getType();
  }

  if (T.isNull() || Context.hasSameType(T, Context.DependentTy))
    return;

  Result.AddResultTypeChunk(
      GetCompletionTypeString(T, Context, Policy, Result.getAllocator()));
}

static void MaybeAddSentinel(Preprocessor &PP,
                             const NamedDecl *FunctionOrMethod,
                             CodeCompletionBuilder &Result) {
  if (SentinelAttr *Sentinel = FunctionOrMethod->getAttr<SentinelAttr>())
    if (Sentinel->getSentinel() == 0) {
      if (PP.getLangOpts().ObjC && PP.isMacroDefined("nil"))
        Result.AddTextChunk(", nil");
      else if (PP.isMacroDefined