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