SemaLookup.cpp

//===--------------------- SemaLookup.cpp - Name Lookup  ------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file implements name lookup for C, C++, Objective-C, and
//  Objective-C++.
//
//===----------------------------------------------------------------------===//
#include "Sema.h"
#include "SemaInherit.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/Expr.h"
#include "clang/Parse/DeclSpec.h"
#include "clang/Basic/LangOptions.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include <set>
#include <vector>
#include <iterator>
#include <utility>
#include <algorithm>

using namespace clang;

typedef llvm::SmallVector<UsingDirectiveDecl*, 4> UsingDirectivesTy;
typedef llvm::DenseSet<NamespaceDecl*> NamespaceSet;
typedef llvm::SmallVector<Sema::LookupResult, 3> LookupResultsTy;

/// UsingDirAncestorCompare - Implements strict weak ordering of
/// UsingDirectives. It orders them by address of its common ancestor.
struct UsingDirAncestorCompare {

  /// @brief Compares UsingDirectiveDecl common ancestor with DeclContext.
  bool operator () (UsingDirectiveDecl *U, const DeclContext *Ctx) const {
    return U->getCommonAncestor() < Ctx;
  }

  /// @brief Compares UsingDirectiveDecl common ancestor with DeclContext.
  bool operator () (const DeclContext *Ctx, UsingDirectiveDecl *U) const {
    return Ctx < U->getCommonAncestor();
  }

  /// @brief Compares UsingDirectiveDecl common ancestors.
  bool operator () (UsingDirectiveDecl *U1, UsingDirectiveDecl *U2) const {
    return U1->getCommonAncestor() < U2->getCommonAncestor();
  }
};

/// AddNamespaceUsingDirectives - Adds all UsingDirectiveDecl's to heap UDirs
/// (ordered by common ancestors), found in namespace NS,
/// including all found (recursively) in their nominated namespaces.
void AddNamespaceUsingDirectives(ASTContext &Context, 
                                 DeclContext *NS,
                                 UsingDirectivesTy &UDirs,
                                 NamespaceSet &Visited) {
  DeclContext::udir_iterator I, End;

  for (llvm::tie(I, End) = NS->getUsingDirectives(Context); I !=End; ++I) {
    UDirs.push_back(*I);
    std::push_heap(UDirs.begin(), UDirs.end(), UsingDirAncestorCompare());
    NamespaceDecl *Nominated = (*I)->getNominatedNamespace();
    if (Visited.insert(Nominated).second)
      AddNamespaceUsingDirectives(Context, Nominated, UDirs, /*ref*/ Visited);
  }
}

/// AddScopeUsingDirectives - Adds all UsingDirectiveDecl's found in Scope S,
/// including all found in the namespaces they nominate.
static void AddScopeUsingDirectives(ASTContext &Context, Scope *S, 
                                    UsingDirectivesTy &UDirs) {
  NamespaceSet VisitedNS;

  if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) {

    if (NamespaceDecl *NS = dyn_cast<NamespaceDecl>(Ctx))
      VisitedNS.insert(NS);

    AddNamespaceUsingDirectives(Context, Ctx, UDirs, /*ref*/ VisitedNS);

  } else {
    Scope::udir_iterator I = S->using_directives_begin(),
                         End = S->using_directives_end();

    for (; I != End; ++I) {
      UsingDirectiveDecl *UD = I->getAs<UsingDirectiveDecl>();
      UDirs.push_back(UD);
      std::push_heap(UDirs.begin(), UDirs.end(), UsingDirAncestorCompare());

      NamespaceDecl *Nominated = UD->getNominatedNamespace();
      if (!VisitedNS.count(Nominated)) {
        VisitedNS.insert(Nominated);
        AddNamespaceUsingDirectives(Context, Nominated, UDirs, 
                                    /*ref*/ VisitedNS);
      }
    }
  }
}

/// MaybeConstructOverloadSet - Name lookup has determined that the
/// elements in [I, IEnd) have the name that we are looking for, and
/// *I is a match for the namespace. This routine returns an
/// appropriate Decl for name lookup, which may either be *I or an
/// OverloadedFunctionDecl that represents the overloaded functions in
/// [I, IEnd). 
///
/// The existance of this routine is temporary; users of LookupResult
/// should be able to handle multiple results, to deal with cases of
/// ambiguity and overloaded functions without needing to create a
/// Decl node.
template<typename DeclIterator>
static NamedDecl *
MaybeConstructOverloadSet(ASTContext &Context, 
                          DeclIterator I, DeclIterator IEnd) {
  assert(I != IEnd && "Iterator range cannot be empty");
  assert(!isa<OverloadedFunctionDecl>(*I) && 
         "Cannot have an overloaded function");

  if (isa<FunctionDecl>(*I)) {
    // If we found a function, there might be more functions. If
    // so, collect them into an overload set.
    DeclIterator Last = I;
    OverloadedFunctionDecl *Ovl = 0;
    for (++Last; Last != IEnd && isa<FunctionDecl>(*Last); ++Last) {
      if (!Ovl) {
        // FIXME: We leak this overload set. Eventually, we want to
        // stop building the declarations for these overload sets, so
        // there will be nothing to leak.
        Ovl = OverloadedFunctionDecl::Create(Context, (*I)->getDeclContext(),
                                             (*I)->getDeclName());
        Ovl->addOverload(cast<FunctionDecl>(*I));
      }
      Ovl->addOverload(cast<FunctionDecl>(*Last));
    }
    
    // If we had more than one function, we built an overload
    // set. Return it.
    if (Ovl)
      return Ovl;
  }
  
  return *I;
}

/// Merges together multiple LookupResults dealing with duplicated Decl's.
static Sema::LookupResult
MergeLookupResults(ASTContext &Context, LookupResultsTy &Results) {
  typedef Sema::LookupResult LResult;
  typedef llvm::SmallPtrSet<NamedDecl*, 4> DeclsSetTy;

  // Remove duplicated Decl pointing at same Decl, by storing them in
  // associative collection. This might be case for code like:
  //
  //    namespace A { int i; }
  //    namespace B { using namespace A; }
  //    namespace C { using namespace A; }
  //
  //    void foo() {
  //      using namespace B;
  //      using namespace C;
  //      ++i; // finds A::i, from both namespace B and C at global scope
  //    }
  //
  //  C++ [namespace.qual].p3:
  //    The same declaration found more than once is not an ambiguity
  //    (because it is still a unique declaration).
  DeclsSetTy FoundDecls;

  // Counter of tag names, and functions for resolving ambiguity
  // and name hiding.
  std::size_t TagNames = 0, Functions = 0, OrdinaryNonFunc = 0;

  LookupResultsTy::iterator I = Results.begin(), End = Results.end();

  // No name lookup results, return early.
  if (I == End) return LResult::CreateLookupResult(Context, 0);

  // Keep track of the tag declaration we found. We only use this if
  // we find a single tag declaration.
  TagDecl *TagFound = 0;

  for (; I != End; ++I) {
    switch (I->getKind()) {
    case LResult::NotFound:
      assert(false &&
             "Should be always successful name lookup result here.");
      break;

    case LResult::AmbiguousReference:
    case LResult::AmbiguousBaseSubobjectTypes:
    case LResult::AmbiguousBaseSubobjects:
      assert(false && "Shouldn't get ambiguous lookup here.");
      break;

    case LResult::Found: {
      NamedDecl *ND = I->getAsDecl();
      if (TagDecl *TD = dyn_cast<TagDecl>(ND)) {
        TagFound = Context.getCanonicalDecl(TD);
        TagNames += FoundDecls.insert(TagFound)?  1 : 0;
      } else if (isa<FunctionDecl>(ND))
        Functions += FoundDecls.insert(ND)? 1 : 0;
      else
        FoundDecls.insert(ND);
      break;
    }

    case LResult::FoundOverloaded:
      for (LResult::iterator FI = I->begin(), FEnd = I->end(); FI != FEnd; ++FI)
        Functions += FoundDecls.insert(*FI)? 1 : 0;
      break;
    }
  }
  OrdinaryNonFunc = FoundDecls.size() - TagNames - Functions;
  bool Ambiguous = false, NameHidesTags = false;
  
  if (FoundDecls.size() == 1) {
    // 1) Exactly one result.
  } else if (TagNames > 1) {
    // 2) Multiple tag names (even though they may be hidden by an
    // object name).
    Ambiguous = true;
  } else if (FoundDecls.size() - TagNames == 1) {
    // 3) Ordinary name hides (optional) tag.
    NameHidesTags = TagFound;
  } else if (Functions) {
    // C++ [basic.lookup].p1:
    // ... Name lookup may associate more than one declaration with
    // a name if it finds the name to be a function name; the declarations
    // are said to form a set of overloaded functions (13.1).
    // Overload resolution (13.3) takes place after name lookup has succeeded.
    //
    if (!OrdinaryNonFunc) {
      // 4) Functions hide tag names.
      NameHidesTags = TagFound;
    } else {
      // 5) Functions + ordinary names.
      Ambiguous = true;
    }
  } else {
    // 6) Multiple non-tag names
    Ambiguous = true;
  }

  if (Ambiguous)
    return LResult::CreateLookupResult(Context, 
                                       FoundDecls.begin(), FoundDecls.size());
  if (NameHidesTags) {
    // There's only one tag, TagFound. Remove it.
    assert(TagFound && FoundDecls.count(TagFound) && "No tag name found?");
    FoundDecls.erase(TagFound);
  }

  // Return successful name lookup result.
  return LResult::CreateLookupResult(Context,
                                MaybeConstructOverloadSet(Context,
                                                          FoundDecls.begin(),
                                                          FoundDecls.end()));
}

// Retrieve the set of identifier namespaces that correspond to a
// specific kind of name lookup.
inline unsigned 
getIdentifierNamespacesFromLookupNameKind(Sema::LookupNameKind NameKind, 
                                          bool CPlusPlus) {
  unsigned IDNS = 0;
  switch (NameKind) {
  case Sema::LookupOrdinaryName:
  case Sema::LookupOperatorName:
  case Sema::LookupRedeclarationWithLinkage:
    IDNS = Decl::IDNS_Ordinary;
    if (CPlusPlus)
      IDNS |= Decl::IDNS_Tag | Decl::IDNS_Member;
    break;

  case Sema::LookupTagName:
    IDNS = Decl::IDNS_Tag;
    break;

  case Sema::LookupMemberName:
    IDNS = Decl::IDNS_Member;
    if (CPlusPlus)
      IDNS |= Decl::IDNS_Tag | Decl::IDNS_Ordinary;    
    break;

  case Sema::LookupNestedNameSpecifierName:
  case Sema::LookupNamespaceName:
    IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag | Decl::IDNS_Member;
    break;
  }
  return IDNS;
}

Sema::LookupResult
Sema::LookupResult::CreateLookupResult(ASTContext &Context, NamedDecl *D) {
  LookupResult Result;
  Result.StoredKind = (D && isa<OverloadedFunctionDecl>(D))?
    OverloadedDeclSingleDecl : SingleDecl;
  Result.First = reinterpret_cast<uintptr_t>(D);
  Result.Last = 0;
  Result.Context = &Context;
  return Result;
}

/// @brief Moves the name-lookup results from Other to this LookupResult.
Sema::LookupResult
Sema::LookupResult::CreateLookupResult(ASTContext &Context, 
                                       IdentifierResolver::iterator F, 
                                       IdentifierResolver::iterator L) {
  LookupResult Result;
  Result.Context = &Context;

  if (F != L && isa<FunctionDecl>(*F)) {
    IdentifierResolver::iterator Next = F;
    ++Next;
    if (Next != L && isa<FunctionDecl>(*Next)) {
      Result.StoredKind = OverloadedDeclFromIdResolver;
      Result.First = F.getAsOpaqueValue();
      Result.Last = L.getAsOpaqueValue();
      return Result;
    }
  } 
    
  Result.StoredKind = SingleDecl;
  Result.First = reinterpret_cast<uintptr_t>(*F);
  Result.Last = 0;
  return Result;
}

Sema::LookupResult
Sema::LookupResult::CreateLookupResult(ASTContext &Context, 
                                       DeclContext::lookup_iterator F, 
                                       DeclContext::lookup_iterator L) {
  LookupResult Result;
  Result.Context = &Context;

  if (F != L && isa<FunctionDecl>(*F)) {
    DeclContext::lookup_iterator Next = F;
    ++Next;
    if (Next != L && isa<FunctionDecl>(*Next)) {
      Result.StoredKind = OverloadedDeclFromDeclContext;
      Result.First = reinterpret_cast<uintptr_t>(F);
      Result.Last = reinterpret_cast<uintptr_t>(L);
      return Result;
    }
  }
  
  Result.StoredKind = SingleDecl;
  Result.First = reinterpret_cast<uintptr_t>(*F);
  Result.Last = 0;
  return Result;
}

/// @brief Determine the result of name lookup.
Sema::LookupResult::LookupKind Sema::LookupResult::getKind() const {
  switch (StoredKind) {
  case SingleDecl:
    return (reinterpret_cast<Decl *>(First) != 0)? Found : NotFound;

  case OverloadedDeclSingleDecl:
  case OverloadedDeclFromIdResolver:
  case OverloadedDeclFromDeclContext:
    return FoundOverloaded;

  case AmbiguousLookupStoresBasePaths:
    return Last? AmbiguousBaseSubobjectTypes : AmbiguousBaseSubobjects;

  case AmbiguousLookupStoresDecls:
    return AmbiguousReference;
  }

  // We can't ever get here.
  return NotFound;
}

/// @brief Converts the result of name lookup into a single (possible
/// NULL) pointer to a declaration.
///
/// The resulting declaration will either be the declaration we found
/// (if only a single declaration was found), an
/// OverloadedFunctionDecl (if an overloaded function was found), or
/// NULL (if no declaration was found). This conversion must not be
/// used anywhere where name lookup could result in an ambiguity. 
///
/// The OverloadedFunctionDecl conversion is meant as a stop-gap
/// solution, since it causes the OverloadedFunctionDecl to be
/// leaked. FIXME: Eventually, there will be a better way to iterate
/// over the set of overloaded functions returned by name lookup.
NamedDecl *Sema::LookupResult::getAsDecl() const {
  switch (StoredKind) {
  case SingleDecl:
    return reinterpret_cast<NamedDecl *>(First);

  case OverloadedDeclFromIdResolver:
    return MaybeConstructOverloadSet(*Context,
                         IdentifierResolver::iterator::getFromOpaqueValue(First),
                         IdentifierResolver::iterator::getFromOpaqueValue(Last));

  case OverloadedDeclFromDeclContext:
    return MaybeConstructOverloadSet(*Context, 
                           reinterpret_cast<DeclContext::lookup_iterator>(First),
                           reinterpret_cast<DeclContext::lookup_iterator>(Last));

  case OverloadedDeclSingleDecl:
    return reinterpret_cast<OverloadedFunctionDecl*>(First);

  case AmbiguousLookupStoresDecls:
  case AmbiguousLookupStoresBasePaths:
    assert(false && 
           "Name lookup returned an ambiguity that could not be handled");
    break;
  }

  return 0;
}

/// @brief Retrieves the BasePaths structure describing an ambiguous
/// name lookup, or null.
BasePaths *Sema::LookupResult::getBasePaths() const {
  if (StoredKind == AmbiguousLookupStoresBasePaths)
      return reinterpret_cast<BasePaths *>(First);
  return 0;
}

Sema::LookupResult::iterator::reference 
Sema::LookupResult::iterator::operator*() const {
  switch (Result->StoredKind) {
  case SingleDecl:
    return reinterpret_cast<NamedDecl*>(Current);

  case OverloadedDeclSingleDecl:
    return *reinterpret_cast<NamedDecl**>(Current);

  case OverloadedDeclFromIdResolver:
    return *IdentifierResolver::iterator::getFromOpaqueValue(Current);

  case AmbiguousLookupStoresBasePaths:
    if (Result->Last)
      return *reinterpret_cast<NamedDecl**>(Current);

    // Fall through to handle the DeclContext::lookup_iterator we're
    // storing.

  case OverloadedDeclFromDeclContext:
  case AmbiguousLookupStoresDecls:
    return *reinterpret_cast<DeclContext::lookup_iterator>(Current);
  }

  return 0;
}

Sema::LookupResult::iterator& Sema::LookupResult::iterator::operator++() {
  switch (Result->StoredKind) {
  case SingleDecl:
    Current = reinterpret_cast<uintptr_t>((NamedDecl*)0);
    break;

  case OverloadedDeclSingleDecl: {
    NamedDecl ** I = reinterpret_cast<NamedDecl**>(Current);
    ++I;
    Current = reinterpret_cast<uintptr_t>(I);
    break;
  }

  case OverloadedDeclFromIdResolver: {
    IdentifierResolver::iterator I 
      = IdentifierResolver::iterator::getFromOpaqueValue(Current);
    ++I;
    Current = I.getAsOpaqueValue();
    break;
  }

  case AmbiguousLookupStoresBasePaths: 
    if (Result->Last) {
      NamedDecl ** I = reinterpret_cast<NamedDecl**>(Current);
      ++I;
      Current = reinterpret_cast<uintptr_t>(I);
      break;
    }
    // Fall through to handle the DeclContext::lookup_iterator we're
    // storing.

  case OverloadedDeclFromDeclContext:
  case AmbiguousLookupStoresDecls: {
    DeclContext::lookup_iterator I 
      = reinterpret_cast<DeclContext::lookup_iterator>(Current);
    ++I;
    Current = reinterpret_cast<uintptr_t>(I);
    break;
  }
  }

  return *this;
}

Sema::LookupResult::iterator Sema::LookupResult::begin() {
  switch (StoredKind) {
  case SingleDecl:
  case OverloadedDeclFromIdResolver:
  case OverloadedDeclFromDeclContext:
  case AmbiguousLookupStoresDecls:
    return iterator(this, First);

  case OverloadedDeclSingleDecl: {
    OverloadedFunctionDecl * Ovl =
      reinterpret_cast<OverloadedFunctionDecl*>(First);
    return iterator(this, 
                    reinterpret_cast<uintptr_t>(&(*Ovl->function_begin())));
  }

  case AmbiguousLookupStoresBasePaths:
    if (Last)
      return iterator(this, 
              reinterpret_cast<uintptr_t>(getBasePaths()->found_decls_begin()));
    else
      return iterator(this,
              reinterpret_cast<uintptr_t>(getBasePaths()->front().Decls.first));
  }

  // Required to suppress GCC warning.
  return iterator();
}

Sema::LookupResult::iterator Sema::LookupResult::end() {
  switch (StoredKind) {
  case SingleDecl:
  case OverloadedDeclFromIdResolver:
  case OverloadedDeclFromDeclContext:
  case AmbiguousLookupStoresDecls:
    return iterator(this, Last);

  case OverloadedDeclSingleDecl: {
    OverloadedFunctionDecl * Ovl =
      reinterpret_cast<OverloadedFunctionDecl*>(First);
    return iterator(this, 
                    reinterpret_cast<uintptr_t>(&(*Ovl->function_end())));
  }

  case AmbiguousLookupStoresBasePaths:
    if (Last)
      return iterator(this, 
               reinterpret_cast<uintptr_t>(getBasePaths()->found_decls_end()));
    else
      return iterator(this, reinterpret_cast<uintptr_t>(
                                     getBasePaths()->front().Decls.second));
  }

  // Required to suppress GCC warning.
  return iterator();
}

void Sema::LookupResult::Destroy() {
  if (BasePaths *Paths = getBasePaths())
    delete Paths;
  else if (getKind() == AmbiguousReference)
    delete[] reinterpret_cast<NamedDecl **>(First);
}

static void
CppNamespaceLookup(ASTContext &Context, DeclContext *NS,
                   DeclarationName Name, Sema::LookupNameKind NameKind,
                   unsigned IDNS, LookupResultsTy &Results,
                   UsingDirectivesTy *UDirs = 0) {

  assert(NS && NS->isFileContext() && "CppNamespaceLookup() requires namespace!");

  // Perform qualified name lookup into the LookupCtx.
  DeclContext::lookup_iterator I, E;
  for (llvm::tie(I, E) = NS->lookup(Context, Name); I != E; ++I)
    if (Sema::isAcceptableLookupResult(*I, NameKind, IDNS)) {
      Results.push_back(Sema::LookupResult::CreateLookupResult(Context, I, E));
      break;
    }

  if (UDirs) {
    // For each UsingDirectiveDecl, which common ancestor is equal
    // to NS, we preform qualified name lookup into namespace nominated by it.
    UsingDirectivesTy::const_iterator UI, UEnd;
    llvm::tie(UI, UEnd) =
      std::equal_range(UDirs->begin(), UDirs->end(), NS,
                       UsingDirAncestorCompare());
 
    for (; UI != UEnd; ++UI)
      CppNamespaceLookup(Context, (*UI)->getNominatedNamespace(),
                         Name, NameKind, IDNS, Results);
  }
}

static bool isNamespaceOrTranslationUnitScope(Scope *S) {
  if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity()))
    return Ctx->isFileContext();
  return false;
}

std::pair<bool, Sema::LookupResult>
Sema::CppLookupName(Scope *S, DeclarationName Name,
                    LookupNameKind NameKind, bool RedeclarationOnly) {
  assert(getLangOptions().CPlusPlus &&
         "Can perform only C++ lookup");
  unsigned IDNS 
    = getIdentifierNamespacesFromLookupNameKind(NameKind, /*CPlusPlus*/ true);
  Scope *Initial = S;
  DeclContext *OutOfLineCtx = 0;
  IdentifierResolver::iterator 
    I = IdResolver.begin(Name),
    IEnd = IdResolver.end();

  // First we lookup local scope.
  // We don't consider using-directives, as per 7.3.4.p1 [namespace.udir]
  // ...During unqualified name lookup (3.4.1), the names appear as if
  // they were declared in the nearest enclosing namespace which contains
  // both the using-directive and the nominated namespace.
  // [Note: in this context, “contains” means “contains directly or
  // indirectly”. 
  //
  // For example:
  // namespace A { int i; }
  // void foo() {
  //   int i;
  //   {
  //     using namespace A;
  //     ++i; // finds local 'i', A::i appears at global scope
  //   }
  // }
  //
  for (; S && !isNamespaceOrTranslationUnitScope(S); S = S->getParent()) {
    // Check whether the IdResolver has anything in this scope.
    for (; I != IEnd && S->isDeclScope(DeclPtrTy::make(*I)); ++I) {
      if (isAcceptableLookupResult(*I, NameKind, IDNS)) {
        // We found something.  Look for anything else in our scope
        // with this same name and in an acceptable identifier
        // namespace, so that we can construct an overload set if we
        // need to.
        IdentifierResolver::iterator LastI = I;
        for (++LastI; LastI != IEnd; ++LastI) {
          if (!S->isDeclScope(DeclPtrTy::make(*LastI)))
            break;
        }
        LookupResult Result =
          LookupResult::CreateLookupResult(Context, I, LastI);
        return std::make_pair(true, Result);
      }
    }
    if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) {
      LookupResult R;
      // Perform member lookup into struct.
      // FIXME: In some cases, we know that every name that could be
      // found by this qualified name lookup will also be on the
      // identifier chain. For example, inside a class without any
      // base classes, we never need to perform qualified lookup
      // because all of the members are on top of the identifier
      // chain.
      if (isa<RecordDecl>(Ctx)) {
        R = LookupQualifiedName(Ctx, Name, NameKind, RedeclarationOnly);
        if (R || RedeclarationOnly)
          return std::make_pair(true, R);
      }
      if (Ctx->getParent() != Ctx->getLexicalParent()) {
        // It is out of line defined C++ method or struct, we continue
        // doing name lookup in parent context. Once we will find namespace
        // or translation-unit we save it for possible checking
        // using-directives later.
        for (OutOfLineCtx = Ctx; OutOfLineCtx && !OutOfLineCtx->isFileContext();
             OutOfLineCtx = OutOfLineCtx->getParent()) {
          R = LookupQualifiedName(OutOfLineCtx, Name, NameKind, RedeclarationOnly);
          if (R || RedeclarationOnly)
            return std::make_pair(true, R);
        }
      }
    }
  }

  // Collect UsingDirectiveDecls in all scopes, and recursively all
  // nominated namespaces by those using-directives.
  // UsingDirectives are pushed to heap, in common ancestor pointer
  // value order.
  // FIXME: Cache this sorted list in Scope structure, and DeclContext,
  // so we don't build it for each lookup!
  UsingDirectivesTy UDirs;
  for (Scope *SC = Initial; SC; SC = SC->getParent())
    if (SC->getFlags() & Scope::DeclScope)
      AddScopeUsingDirectives(Context, SC, UDirs);

  // Sort heapified UsingDirectiveDecls.
  std::sort_heap(UDirs.begin(), UDirs.end());

  // Lookup namespace scope, and global scope.
  // Unqualified name lookup in C++ requires looking into scopes
  // that aren't strictly lexical, and therefore we walk through the
  // context as well as walking through the scopes.

  LookupResultsTy LookupResults;
  assert((!OutOfLineCtx || OutOfLineCtx->isFileContext()) &&
         "We should have been looking only at file context here already.");
  bool LookedInCtx = false;
  LookupResult Result;
  while (OutOfLineCtx &&
         OutOfLineCtx != S->getEntity() &&
         OutOfLineCtx->isNamespace()) {
    LookedInCtx = true;

    // Look into context considering using-directives.
    CppNamespaceLookup(Context, OutOfLineCtx, Name, NameKind, IDNS,
                       LookupResults, &UDirs);

    if ((Result = MergeLookupResults(Context, LookupResults)) ||
        (RedeclarationOnly && !OutOfLineCtx->isTransparentContext()))
      return std::make_pair(true, Result);

    OutOfLineCtx = OutOfLineCtx->getParent();
  }

  for (; S; S = S->getParent()) {
    DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity());
    assert(Ctx && Ctx->isFileContext() &&
           "We should have been looking only at file context here already.");

    // Check whether the IdResolver has anything in this scope.
    for (; I != IEnd && S->isDeclScope(DeclPtrTy::make(*I)); ++I) {
      if (isAcceptableLookupResult(*I, NameKind, IDNS)) {
        // We found something.  Look for anything else in our scope
        // with this same name and in an acceptable identifier
        // namespace, so that we can construct an overload set if we
        // need to.
        IdentifierResolver::iterator LastI = I;
        for (++LastI; LastI != IEnd; ++LastI) {
          if (!S->isDeclScope(DeclPtrTy::make(*LastI)))
            break;
        }
        
        // We store name lookup result, and continue trying to look into
        // associated context, and maybe namespaces nominated by
        // using-directives.
        LookupResults.push_back(
          LookupResult::CreateLookupResult(Context, I, LastI));
        break;
      }
    }

    LookedInCtx = true;
    // Look into context considering using-directives.
    CppNamespaceLookup(Context, Ctx, Name, NameKind, IDNS,
                       LookupResults, &UDirs);

    if ((Result = MergeLookupResults(Context, LookupResults)) ||
        (RedeclarationOnly && !Ctx->isTransparentContext()))
      return std::make_pair(true, Result);
  }

  if (!(LookedInCtx || LookupResults.empty())) {
    // We didn't Performed lookup in Scope entity, so we return
    // result form IdentifierResolver.
    assert((LookupResults.size() == 1) && "Wrong size!");
    return std::make_pair(true, LookupResults.front());
  }
  return std::make_pair(false, LookupResult());
}

/// @brief Perform unqualified name lookup starting from a given
/// scope.
///
/// Unqualified name lookup (C++ [basic.lookup.unqual], C99 6.2.1) is
/// used to find names within the current scope. For example, 'x' in
/// @code
/// int x;
/// int f() {
///   return x; // unqualified name look finds 'x' in the global scope
/// }
/// @endcode
///
/// Different lookup criteria can find different names. For example, a
/// particular scope can have both a struct and a function of the same
/// name, and each can be found by certain lookup criteria. For more
/// information about lookup criteria, see the documentation for the
/// class LookupCriteria.
///
/// @param S        The scope from which unqualified name lookup will
/// begin. If the lookup criteria permits, name lookup may also search
/// in the parent scopes.
///
/// @param Name     The name of the entity that we are searching for.
///
/// @param Loc      If provided, the source location where we're performing
/// name lookup. At present, this is only used to produce diagnostics when 
/// C library functions (like "malloc") are implicitly declared.
///
/// @returns The result of name lookup, which includes zero or more
/// declarations and possibly additional information used to diagnose
/// ambiguities.
Sema::LookupResult 
Sema::LookupName(Scope *S, DeclarationName Name, LookupNameKind NameKind,
                 bool RedeclarationOnly, bool AllowBuiltinCreation,
                 SourceLocation Loc) {
  if (!Name) return LookupResult::CreateLookupResult(Context, 0);

  if (!getLangOptions().CPlusPlus) {
    // Unqualified name lookup in C/Objective-C is purely lexical, so
    // search in the declarations attached to the name.
    unsigned IDNS = 0;
    switch (NameKind) {
    case Sema::LookupOrdinaryName:
      IDNS = Decl::IDNS_Ordinary;
      break;

    case Sema::LookupTagName:
      IDNS = Decl::IDNS_Tag;
      break;

    case Sema::LookupMemberName:
      IDNS = Decl::IDNS_Member;
      break;

    case Sema::LookupOperatorName:
    case Sema::LookupNestedNameSpecifierName:
    case Sema::LookupNamespaceName:
      assert(false && "C does not perform these kinds of name lookup");
      break;

    case Sema::LookupRedeclarationWithLinkage:
      // Find the nearest non-transparent declaration scope.
      while (!(S->getFlags() & Scope::DeclScope) ||
             (S->getEntity() && 
              static_cast<DeclContext *>(S->getEntity())
                ->isTransparentContext()))
        S = S->getParent();
      IDNS = Decl::IDNS_Ordinary;
      break;
    }

    // Scan up the scope chain looking for a decl that matches this
    // identifier that is in the appropriate namespace.  This search
    // should not take long, as shadowing of names is uncommon, and
    // deep shadowing is extremely uncommon.
    bool LeftStartingScope = false;

    for (IdentifierResolver::iterator I = IdResolver.begin(Name),
                                   IEnd = IdResolver.end(); 
         I != IEnd; ++I)
      if ((*I)->isInIdentifierNamespace(IDNS)) {
        if (NameKind == LookupRedeclarationWithLinkage) {
          // Determine whether this (or a previous) declaration is
          // out-of-scope.
          if (!LeftStartingScope && !S->isDeclScope(DeclPtrTy::make(*I)))
            LeftStartingScope = true;

          // If we found something outside of our starting scope that
          // does not have linkage, skip it.
          if (LeftStartingScope && !((*I)->hasLinkage()))
            continue;
        }

        if ((*I)->getAttr<OverloadableAttr>()) {
          // If this declaration has the "overloadable" attribute, we
          // might have a set of overloaded functions.

          // Figure out what scope the identifier is in.
          while (!(S->getFlags() & Scope::DeclScope) ||
                 !S->isDeclScope(DeclPtrTy::make(*I)))
            S = S->getParent();

          // Find the last declaration in this scope (with the same
          // name, naturally).
          IdentifierResolver::iterator LastI = I;
          for (++LastI; LastI != IEnd; ++LastI) {
            if (!S->isDeclScope(DeclPtrTy::make(*LastI)))
              break;
          }

          return LookupResult::CreateLookupResult(Context, I, LastI);
        }

        // We have a single lookup result.
        return LookupResult::CreateLookupResult(Context, *I);
      }

    /// If the context has an external AST source attached, look at
    /// translation unit scope.
    if (Context.getExternalSource()) {
      DeclContext::lookup_iterator I, E;
      for (llvm::tie(I, E) 
             = Context.getTranslationUnitDecl()->lookup(Context, Name); 
           I != E; ++I)
        if (isAcceptableLookupResult(*I, NameKind, IDNS))
          return LookupResult::CreateLookupResult(Context, I, E);
    }
  } else {
    // Perform C++ unqualified name lookup.
    std::pair<bool, LookupResult> MaybeResult =
      CppLookupName(S, Name, NameKind, RedeclarationOnly);
    if (MaybeResult.first)
      return MaybeResult.second;
  }

  // If we didn't find a use of this identifier, and if the identifier
  // corresponds to a compiler builtin, create the decl object for the builtin
  // now, injecting it into translation unit scope, and return it.
  if (NameKind == LookupOrdinaryName || 
      NameKind == LookupRedeclarationWithLinkage) {
    IdentifierInfo *II = Name.getAsIdentifierInfo();
    if (II && AllowBuiltinCreation) {
      // If this is a builtin on this (or all) targets, create the decl.
      if (unsigned BuiltinID = II->getBuiltinID()) {
        // In C++, we don't have any predefined library functions like
        // 'malloc'. Instead, we'll just error.
        if (getLangOptions().CPlusPlus && 
            Context.BuiltinInfo.isPredefinedLibFunction(BuiltinID))
          return LookupResult::CreateLookupResult(Context, 0);

        return LookupResult::CreateLookupResult(Context,
                            LazilyCreateBuiltin((IdentifierInfo *)II, BuiltinID,
                                                S, RedeclarationOnly, Loc));
      }
    }
    if (getLangOptions().ObjC1 && II) {
      // @interface and @compatibility_alias introduce typedef-like names.
      // Unlike typedef's, they can only be introduced at file-scope (and are 
      // therefore not scoped decls). They can, however, be shadowed by
      // other names in IDNS_Ordinary.
      ObjCInterfaceDeclsTy::iterator IDI = ObjCInterfaceDecls.find(II);
      if (IDI != ObjCInterfaceDecls.end())
        return LookupResult::CreateLookupResult(Context, IDI->second);
      ObjCAliasTy::iterator I = ObjCAliasDecls.find(II);
      if (I != ObjCAliasDecls.end())
        return LookupResult::CreateLookupResult(Context, 
                                                I->second->getClassInterface());
    }
  }
  return LookupResult::CreateLookupResult(Context, 0);
}

/// @brief Perform qualified name lookup into a given context.
///
/// Qualified name lookup (C++ [basic.lookup.qual]) is used to find
/// names when the context of those names is explicit specified, e.g.,
/// "std::vector" or "x->member".
///
/// Different lookup criteria can find different names. For example, a
/// particular scope can have both a struct and a function of the same
/// name, and each can be found by certain lookup criteria. For more
/// information about lookup criteria, see the documentation for the
/// class LookupCriteria.
///
/// @param LookupCtx The context in which qualified name lookup will
/// search. If the lookup criteria permits, name lookup may also search
/// in the parent contexts or (for C++ classes) base classes.
///
/// @param Name     The name of the entity that we are searching for.
///
/// @param Criteria The criteria that this routine will use to
/// determine which names are visible and which names will be
/// found. Note that name lookup will find a name that is visible by
/// the given criteria, but the entity itself may not be semantically
/// correct or even the kind of entity expected based on the
/// lookup. For example, searching for a nested-name-specifier name
/// might result in an EnumDecl, which is visible but is not permitted
/// as a nested-name-specifier in C++03.
///
/// @returns The result of name lookup, which includes zero or more
/// declarations and possibly additional information used to diagnose
/// ambiguities.
Sema::LookupResult
Sema::LookupQualifiedName(DeclContext *LookupCtx, DeclarationName Name,
                          LookupNameKind NameKind, bool RedeclarationOnly) {
  assert(LookupCtx && "Sema::LookupQualifiedName requires a lookup context");
  
  if (!Name) return LookupResult::CreateLookupResult(Context, 0);

  // If we're performing qualified name lookup (e.g., lookup into a
  // struct), find fields as part of ordinary name lookup.
  unsigned IDNS
    = getIdentifierNamespacesFromLookupNameKind(NameKind, 
                                                getLangOptions().CPlusPlus);
  if (NameKind == LookupOrdinaryName)
    IDNS |= Decl::IDNS_Member;

  // Perform qualified name lookup into the LookupCtx.
  DeclContext::lookup_iterator I, E;
  for (llvm::tie(I, E) = LookupCtx->lookup(Context, Name); I != E; ++I)
    if (isAcceptableLookupResult(*I, NameKind, IDNS))
      return LookupResult::CreateLookupResult(Context, I, E);

  // If this isn't a C++ class or we aren't allowed to look into base
  // classes, we're done.
  if (RedeclarationOnly || !isa<CXXRecordDecl>(LookupCtx))
    return LookupResult::CreateLookupResult(Context, 0);

  // Perform lookup into our base classes.
  BasePaths Paths;
  Paths.setOrigin(Context.getTypeDeclType(cast<RecordDecl>(LookupCtx)));

  // Look for this member in our base classes
  if (!LookupInBases(cast<CXXRecordDecl>(LookupCtx), 
                     MemberLookupCriteria(Name, NameKind, IDNS), Paths))
    return LookupResult::CreateLookupResult(Context, 0);