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" 21 using namespace clang; 22 using 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}`. 29 static llvm::SmallVector<const NamespaceDecl *, 4> 30 getAllNamedNamespaces(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. 48 static bool 49 usingFromDifferentCanonicalNamespace(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 85 static 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.startswith(NS)) 102 return NewName.substr(NS.size()); 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 "::". 112 static 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. 127 static std::string disambiguateSpellingInScope(StringRef Spelling, 128 StringRef QName, 129 const DeclContext &UseContext, 130 SourceLocation UseLoc) { 131 assert(QName.startswith("::")); 132 assert(QName.endswith(Spelling)); 133 if (Spelling.startswith("::")) 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.startswith("::")) 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.startswith(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 185 std::string tooling::replaceNestedName(const NestedNameSpecifier *Use, 186 SourceLocation UseLoc, 187 const DeclContext *UseContext, 188 const NamedDecl *FromDecl, 189 StringRef ReplacementString) { 190 assert(ReplacementString.startswith("::") && 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