contrib/llvm/tools/clang/lib/Tooling/Core/Lookup.cpp

   1 //===--- Lookup.cpp - Framework for clang refactoring tools ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines helper methods for clang tools performing name lookup.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Tooling/Core/Lookup.h"
  15 #include "clang/AST/Decl.h"
  16 #include "clang/AST/DeclCXX.h"
  17 #include "clang/AST/DeclarationName.h"
  18 using namespace clang;
  19 using namespace clang::tooling;
  20
  21 // Gets all namespaces that \p Context is in as a vector (ignoring anonymous
  22 // namespaces). The inner namespaces come before outer namespaces in the vector.
  23 // For example, if the context is in the following namespace:
  24 //    `namespace a { namespace b { namespace c ( ... ) } }`,
  25 // the vector will be `{c, b, a}`.
  26 static llvm::SmallVector<const NamespaceDecl *, 4>
  27 getAllNamedNamespaces(const DeclContext *Context) {
  28   llvm::SmallVector<const NamespaceDecl *, 4> Namespaces;
  29   auto GetNextNamedNamespace = [](const DeclContext *Context) {
  30     // Look past non-namespaces and anonymous namespaces on FromContext.
  31     while (Context && (!isa<NamespaceDecl>(Context) ||
  32                        cast<NamespaceDecl>(Context)->isAnonymousNamespace()))
  33       Context = Context->getParent();
  34     return Context;
  35   };
  36   for (Context = GetNextNamedNamespace(Context); Context != nullptr;
  37        Context = GetNextNamedNamespace(Context->getParent()))
  38     Namespaces.push_back(cast<NamespaceDecl>(Context));
  39   return Namespaces;
  40 }
  41
  42 // Returns true if the context in which the type is used and the context in
  43 // which the type is declared are the same semantical namespace but different
  44 // lexical namespaces.
  45 static bool
  46 usingFromDifferentCanonicalNamespace(const DeclContext *FromContext,
  47                                      const DeclContext *UseContext) {
  48   // We can skip anonymous namespace because:
  49   // 1. `FromContext` and `UseContext` must be in the same anonymous namespaces
  50   // since referencing across anonymous namespaces is not possible.
  51   // 2. If `FromContext` and `UseContext` are in the same anonymous namespace,
  52   // the function will still return `false` as expected.
  53   llvm::SmallVector<const NamespaceDecl *, 4> FromNamespaces =
  54       getAllNamedNamespaces(FromContext);
  55   llvm::SmallVector<const NamespaceDecl *, 4> UseNamespaces =
  56       getAllNamedNamespaces(UseContext);
  57   // If `UseContext` has fewer level of nested namespaces, it cannot be in the
  58   // same canonical namespace as the `FromContext`.
  59   if (UseNamespaces.size() < FromNamespaces.size())
  60     return false;
  61   unsigned Diff = UseNamespaces.size() - FromNamespaces.size();
  62   auto FromIter = FromNamespaces.begin();
  63   // Only compare `FromNamespaces` with namespaces in `UseNamespaces` that can
  64   // collide, i.e. the top N namespaces where N is the number of namespaces in
  65   // `FromNamespaces`.
  66   auto UseIter = UseNamespaces.begin() + Diff;
  67   for (; FromIter != FromNamespaces.end() && UseIter != UseNamespaces.end();
  68        ++FromIter, ++UseIter) {
  69     // Literally the same namespace, not a collision.
  70     if (*FromIter == *UseIter)
  71       return false;
  72     // Now check the names. If they match we have a different canonical
  73     // namespace with the same name.
  74     if (cast<NamespaceDecl>(*FromIter)->getDeclName() ==
  75         cast<NamespaceDecl>(*UseIter)->getDeclName())
  76       return true;
  77   }
  78   assert(FromIter == FromNamespaces.end() && UseIter == UseNamespaces.end());
  79   return false;
  80 }
  81
  82 static StringRef getBestNamespaceSubstr(const DeclContext *DeclA,
  83                                         StringRef NewName,
  84                                         bool HadLeadingColonColon) {
  85   while (true) {
  86     while (DeclA && !isa<NamespaceDecl>(DeclA))
  87       DeclA = DeclA->getParent();
  88
  89     // Fully qualified it is! Leave :: in place if it's there already.
  90     if (!DeclA)
  91       return HadLeadingColonColon ? NewName : NewName.substr(2);
  92
  93     // Otherwise strip off redundant namespace qualifications from the new name.
  94     // We use the fully qualified name of the namespace and remove that part
  95     // from NewName if it has an identical prefix.
  96     std::string NS =
  97         "::" + cast<NamespaceDecl>(DeclA)->getQualifiedNameAsString() + "::";
  98     if (NewName.startswith(NS))
  99       return NewName.substr(NS.size());
 100
 101     // No match yet. Strip of a namespace from the end of the chain and try
 102     // again. This allows to get optimal qualifications even if the old and new
 103     // decl only share common namespaces at a higher level.
 104     DeclA = DeclA->getParent();
 105   }
 106 }
 107
 108 /// Check if the name specifier begins with a written "::".
 109 static bool isFullyQualified(const NestedNameSpecifier *NNS) {
 110   while (NNS) {
 111     if (NNS->getKind() == NestedNameSpecifier::Global)
 112       return true;
 113     NNS = NNS->getPrefix();
 114   }
 115   return false;
 116 }
 117
 118 // Returns true if spelling symbol \p QName as \p Spelling in \p UseContext is
 119 // ambiguous. For example, if QName is "::y::bar" and the spelling is "y::bar"
 120 // in `UseContext` "a" that contains a nested namespace "a::y", then "y::bar"
 121 // can be resolved to ::a::y::bar, which can cause compile error.
 122 // FIXME: consider using namespaces.
 123 static bool isAmbiguousNameInScope(StringRef Spelling, StringRef QName,
 124                                    const DeclContext &UseContext) {
 125   assert(QName.startswith("::"));
 126   if (Spelling.startswith("::"))
 127     return false;
 128
 129   // Lookup the first component of Spelling in all enclosing namespaces and
 130   // check if there is any existing symbols with the same name but in different
 131   // scope.
 132   StringRef Head = Spelling.split("::").first;
 133
 134   llvm::SmallVector<const NamespaceDecl *, 4> UseNamespaces =
 135       getAllNamedNamespaces(&UseContext);
 136   auto &AST = UseContext.getParentASTContext();
 137   StringRef TrimmedQName = QName.substr(2);
 138   for (const auto *NS : UseNamespaces) {
 139     auto LookupRes = NS->lookup(DeclarationName(&AST.Idents.get(Head)));
 140     if (!LookupRes.empty()) {
 141       for (const NamedDecl *Res : LookupRes)
 142         if (!TrimmedQName.startswith(Res->getQualifiedNameAsString()))
 143           return true;
 144     }
 145   }
 146   return false;
 147 }
 148
 149 std::string tooling::replaceNestedName(const NestedNameSpecifier *Use,
 150                                        const DeclContext *UseContext,
 151                                        const NamedDecl *FromDecl,
 152                                        StringRef ReplacementString) {
 153   assert(ReplacementString.startswith("::") &&
 154          "Expected fully-qualified name!");
 155
 156   // We can do a raw name replacement when we are not inside the namespace for
 157   // the original class/function and it is not in the global namespace.  The
 158   // assumption is that outside the original namespace we must have a using
 159   // statement that makes this work out and that other parts of this refactor
 160   // will automatically fix using statements to point to the new class/function.
 161   // However, if the `FromDecl` is a class forward declaration, the reference is
 162   // still considered as referring to the original definition, so we can't do a
 163   // raw name replacement in this case.
 164   const bool class_name_only = !Use;
 165   const bool in_global_namespace =
 166       isa<TranslationUnitDecl>(FromDecl->getDeclContext());
 167   const bool is_class_forward_decl =
 168       isa<CXXRecordDecl>(FromDecl) &&
 169       !cast<CXXRecordDecl>(FromDecl)->isCompleteDefinition();
 170   if (class_name_only && !in_global_namespace && !is_class_forward_decl &&
 171       !usingFromDifferentCanonicalNamespace(FromDecl->getDeclContext(),
 172                                             UseContext)) {
 173     auto Pos = ReplacementString.rfind("::");
 174     return Pos != StringRef::npos ? ReplacementString.substr(Pos + 2)
 175                                   : ReplacementString;
 176   }
 177   // We did not match this because of a using statement, so we will need to
 178   // figure out how good a namespace match we have with our destination type.
 179   // We work backwards (from most specific possible namespace to least
 180   // specific).
 181   StringRef Suggested = getBestNamespaceSubstr(UseContext, ReplacementString,
 182                                                isFullyQualified(Use));
 183   // Use the fully qualified name if the suggested name is ambiguous.
 184   // FIXME: consider re-shortening the name until the name is not ambiguous. We
 185   // are not doing this because ambiguity is pretty bad and we should not try to
 186   // be clever in handling such cases. Making this noticeable to users seems to
 187   // be a better option.
 188   return isAmbiguousNameInScope(Suggested, ReplacementString, *UseContext)
 189              ? ReplacementString
 190              : Suggested;
 191 }