path: root/lib/Sema/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/Parse/DeclSpec.h"
#include "clang/Basic/LangOptions.h"
#include "llvm/ADT/STLExtras.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(DeclContext *NS,
                                 UsingDirectivesTy &UDirs,
                                 NamespaceSet &Visited) {
  DeclContext::udir_iterator I, End;

  for (llvm::tie(I, End) = NS->getUsingDirectives(); 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(Nominated, UDirs, /*ref*/ Visited);
  }
}

/// AddScopeUsingDirectives - Adds all UsingDirectiveDecl's found in Scope S,
/// including all found in the namespaces they nominate.
static void AddScopeUsingDirectives(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(Ctx, UDirs, /*ref*/ VisitedNS);

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

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

      NamespaceDecl *Nominated = UD->getNominatedNamespace();
      if (!VisitedNS.count(Nominated)) {
        VisitedNS.insert(Nominated);
        AddNamespaceUsingDirectives(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