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