contrib/llvm-project/clang/lib/Tooling/Core/Lookup.cpp

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