575 lines · cpp
1//===--- Quality.cpp ---------------------------------------------*- C++-*-===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "Quality.h"10#include "AST.h"11#include "ASTSignals.h"12#include "FileDistance.h"13#include "SourceCode.h"14#include "index/Symbol.h"15#include "clang/AST/ASTContext.h"16#include "clang/AST/Decl.h"17#include "clang/AST/DeclCXX.h"18#include "clang/AST/DeclTemplate.h"19#include "clang/AST/DeclVisitor.h"20#include "clang/Basic/SourceManager.h"21#include "clang/Sema/CodeCompleteConsumer.h"22#include "llvm/ADT/StringRef.h"23#include "llvm/Support/Casting.h"24#include "llvm/Support/FormatVariadic.h"25#include "llvm/Support/MathExtras.h"26#include "llvm/Support/raw_ostream.h"27#include <algorithm>28#include <cmath>29#include <optional>30 31namespace clang {32namespace clangd {33 34static bool hasDeclInMainFile(const Decl &D) {35 auto &SourceMgr = D.getASTContext().getSourceManager();36 for (auto *Redecl : D.redecls()) {37 if (isInsideMainFile(Redecl->getLocation(), SourceMgr))38 return true;39 }40 return false;41}42 43static bool hasUsingDeclInMainFile(const CodeCompletionResult &R) {44 const auto &Context = R.Declaration->getASTContext();45 const auto &SourceMgr = Context.getSourceManager();46 if (R.ShadowDecl) {47 if (isInsideMainFile(R.ShadowDecl->getLocation(), SourceMgr))48 return true;49 }50 return false;51}52 53static SymbolQualitySignals::SymbolCategory categorize(const NamedDecl &ND) {54 if (const auto *FD = dyn_cast<FunctionDecl>(&ND)) {55 if (FD->isOverloadedOperator())56 return SymbolQualitySignals::Operator;57 }58 class Switch59 : public ConstDeclVisitor<Switch, SymbolQualitySignals::SymbolCategory> {60 public:61#define MAP(DeclType, Category) \62 SymbolQualitySignals::SymbolCategory Visit##DeclType(const DeclType *) { \63 return SymbolQualitySignals::Category; \64 }65 MAP(NamespaceDecl, Namespace);66 MAP(NamespaceAliasDecl, Namespace);67 MAP(TypeDecl, Type);68 MAP(TypeAliasTemplateDecl, Type);69 MAP(ClassTemplateDecl, Type);70 MAP(CXXConstructorDecl, Constructor);71 MAP(CXXDestructorDecl, Destructor);72 MAP(ValueDecl, Variable);73 MAP(VarTemplateDecl, Variable);74 MAP(FunctionDecl, Function);75 MAP(FunctionTemplateDecl, Function);76 MAP(Decl, Unknown);77#undef MAP78 };79 return Switch().Visit(&ND);80}81 82static SymbolQualitySignals::SymbolCategory83categorize(const CodeCompletionResult &R) {84 if (R.Declaration)85 return categorize(*R.Declaration);86 if (R.Kind == CodeCompletionResult::RK_Macro)87 return SymbolQualitySignals::Macro;88 // Everything else is a keyword or a pattern. Patterns are mostly keywords89 // too, except a few which we recognize by cursor kind.90 switch (R.CursorKind) {91 case CXCursor_CXXMethod:92 return SymbolQualitySignals::Function;93 case CXCursor_ModuleImportDecl:94 return SymbolQualitySignals::Namespace;95 case CXCursor_MacroDefinition:96 return SymbolQualitySignals::Macro;97 case CXCursor_TypeRef:98 return SymbolQualitySignals::Type;99 case CXCursor_MemberRef:100 return SymbolQualitySignals::Variable;101 case CXCursor_Constructor:102 return SymbolQualitySignals::Constructor;103 default:104 return SymbolQualitySignals::Keyword;105 }106}107 108static SymbolQualitySignals::SymbolCategory109categorize(const index::SymbolInfo &D) {110 switch (D.Kind) {111 case index::SymbolKind::Namespace:112 case index::SymbolKind::NamespaceAlias:113 return SymbolQualitySignals::Namespace;114 case index::SymbolKind::Macro:115 return SymbolQualitySignals::Macro;116 case index::SymbolKind::Enum:117 case index::SymbolKind::Struct:118 case index::SymbolKind::Class:119 case index::SymbolKind::Protocol:120 case index::SymbolKind::Extension:121 case index::SymbolKind::Union:122 case index::SymbolKind::TypeAlias:123 case index::SymbolKind::TemplateTypeParm:124 case index::SymbolKind::TemplateTemplateParm:125 case index::SymbolKind::Concept:126 return SymbolQualitySignals::Type;127 case index::SymbolKind::Function:128 case index::SymbolKind::ClassMethod:129 case index::SymbolKind::InstanceMethod:130 case index::SymbolKind::StaticMethod:131 case index::SymbolKind::InstanceProperty:132 case index::SymbolKind::ClassProperty:133 case index::SymbolKind::StaticProperty:134 case index::SymbolKind::ConversionFunction:135 return SymbolQualitySignals::Function;136 case index::SymbolKind::Destructor:137 return SymbolQualitySignals::Destructor;138 case index::SymbolKind::Constructor:139 return SymbolQualitySignals::Constructor;140 case index::SymbolKind::Variable:141 case index::SymbolKind::Field:142 case index::SymbolKind::EnumConstant:143 case index::SymbolKind::Parameter:144 case index::SymbolKind::NonTypeTemplateParm:145 return SymbolQualitySignals::Variable;146 // FIXME: for backwards compatibility, the include directive kind is treated147 // the same as Unknown148 case index::SymbolKind::IncludeDirective:149 case index::SymbolKind::Using:150 case index::SymbolKind::Module:151 case index::SymbolKind::Unknown:152 return SymbolQualitySignals::Unknown;153 }154 llvm_unreachable("Unknown index::SymbolKind");155}156 157static bool isInstanceMember(const NamedDecl *ND) {158 if (!ND)159 return false;160 if (const auto *TP = dyn_cast<FunctionTemplateDecl>(ND))161 ND = TP->TemplateDecl::getTemplatedDecl();162 if (const auto *CM = dyn_cast<CXXMethodDecl>(ND))163 return !CM->isStatic();164 return isa<FieldDecl>(ND); // Note that static fields are VarDecl.165}166 167static bool isInstanceMember(const index::SymbolInfo &D) {168 switch (D.Kind) {169 case index::SymbolKind::InstanceMethod:170 case index::SymbolKind::InstanceProperty:171 case index::SymbolKind::Field:172 return true;173 default:174 return false;175 }176}177 178void SymbolQualitySignals::merge(const CodeCompletionResult &SemaCCResult) {179 Deprecated |= (SemaCCResult.Availability == CXAvailability_Deprecated);180 Category = categorize(SemaCCResult);181 182 if (SemaCCResult.Declaration) {183 ImplementationDetail |= isImplementationDetail(SemaCCResult.Declaration);184 if (auto *ID = SemaCCResult.Declaration->getIdentifier())185 ReservedName = ReservedName || isReservedName(ID->getName());186 } else if (SemaCCResult.Kind == CodeCompletionResult::RK_Macro)187 ReservedName =188 ReservedName || isReservedName(SemaCCResult.Macro->getName());189}190 191void SymbolQualitySignals::merge(const Symbol &IndexResult) {192 Deprecated |= (IndexResult.Flags & Symbol::Deprecated);193 ImplementationDetail |= (IndexResult.Flags & Symbol::ImplementationDetail);194 References = std::max(IndexResult.References, References);195 Category = categorize(IndexResult.SymInfo);196 ReservedName = ReservedName || isReservedName(IndexResult.Name);197}198 199float SymbolQualitySignals::evaluateHeuristics() const {200 float Score = 1;201 202 // This avoids a sharp gradient for tail symbols, and also neatly avoids the203 // question of whether 0 references means a bad symbol or missing data.204 if (References >= 10) {205 // Use a sigmoid style boosting function, which flats out nicely for large206 // numbers (e.g. 2.58 for 1M references).207 // The following boosting function is equivalent to:208 // m = 0.06209 // f = 12.0210 // boost = f * sigmoid(m * std::log(References)) - 0.5 * f + 0.59211 // Sample data points: (10, 1.00), (100, 1.41), (1000, 1.82),212 // (10K, 2.21), (100K, 2.58), (1M, 2.94)213 float S = std::pow(References, -0.06);214 Score *= 6.0 * (1 - S) / (1 + S) + 0.59;215 }216 217 if (Deprecated)218 Score *= 0.1f;219 if (ReservedName)220 Score *= 0.1f;221 if (ImplementationDetail)222 Score *= 0.2f;223 224 switch (Category) {225 case Keyword: // Often relevant, but misses most signals.226 Score *= 4; // FIXME: important keywords should have specific boosts.227 break;228 case Type:229 case Function:230 case Variable:231 Score *= 1.1f;232 break;233 case Namespace:234 Score *= 0.8f;235 break;236 case Macro:237 case Destructor:238 case Operator:239 Score *= 0.5f;240 break;241 case Constructor: // No boost constructors so they are after class types.242 case Unknown:243 break;244 }245 246 return Score;247}248 249llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,250 const SymbolQualitySignals &S) {251 OS << llvm::formatv("=== Symbol quality: {0}\n", S.evaluateHeuristics());252 OS << llvm::formatv("\tReferences: {0}\n", S.References);253 OS << llvm::formatv("\tDeprecated: {0}\n", S.Deprecated);254 OS << llvm::formatv("\tReserved name: {0}\n", S.ReservedName);255 OS << llvm::formatv("\tImplementation detail: {0}\n", S.ImplementationDetail);256 OS << llvm::formatv("\tCategory: {0}\n", static_cast<int>(S.Category));257 return OS;258}259 260static SymbolRelevanceSignals::AccessibleScope261computeScope(const NamedDecl *D) {262 // Injected "Foo" within the class "Foo" has file scope, not class scope.263 const DeclContext *DC = D->getDeclContext();264 if (auto *R = dyn_cast_or_null<CXXRecordDecl>(D))265 if (R->isInjectedClassName())266 DC = DC->getParent();267 // Class constructor should have the same scope as the class.268 if (isa<CXXConstructorDecl>(D))269 DC = DC->getParent();270 bool InClass = false;271 for (; !DC->isFileContext(); DC = DC->getParent()) {272 if (DC->isFunctionOrMethod())273 return SymbolRelevanceSignals::FunctionScope;274 InClass = InClass || DC->isRecord();275 }276 if (InClass)277 return SymbolRelevanceSignals::ClassScope;278 // ExternalLinkage threshold could be tweaked, e.g. module-visible as global.279 // Avoid caching linkage if it may change after enclosing code completion.280 if (hasUnstableLinkage(D) || llvm::to_underlying(D->getLinkageInternal()) <281 llvm::to_underlying(Linkage::External))282 return SymbolRelevanceSignals::FileScope;283 return SymbolRelevanceSignals::GlobalScope;284}285 286void SymbolRelevanceSignals::merge(const Symbol &IndexResult) {287 SymbolURI = IndexResult.CanonicalDeclaration.FileURI;288 SymbolScope = IndexResult.Scope;289 IsInstanceMember |= isInstanceMember(IndexResult.SymInfo);290 if (!(IndexResult.Flags & Symbol::VisibleOutsideFile)) {291 Scope = AccessibleScope::FileScope;292 }293 if (MainFileSignals) {294 MainFileRefs =295 std::max(MainFileRefs,296 MainFileSignals->ReferencedSymbols.lookup(IndexResult.ID));297 ScopeRefsInFile =298 std::max(ScopeRefsInFile,299 MainFileSignals->RelatedNamespaces.lookup(IndexResult.Scope));300 }301}302 303void SymbolRelevanceSignals::computeASTSignals(304 const CodeCompletionResult &SemaResult) {305 if (!MainFileSignals)306 return;307 if ((SemaResult.Kind != CodeCompletionResult::RK_Declaration) &&308 (SemaResult.Kind != CodeCompletionResult::RK_Pattern))309 return;310 if (const NamedDecl *ND = SemaResult.getDeclaration()) {311 if (hasUnstableLinkage(ND))312 return;313 auto ID = getSymbolID(ND);314 if (!ID)315 return;316 MainFileRefs =317 std::max(MainFileRefs, MainFileSignals->ReferencedSymbols.lookup(ID));318 if (const auto *NSD = dyn_cast<NamespaceDecl>(ND->getDeclContext())) {319 if (NSD->isAnonymousNamespace())320 return;321 std::string Scope = printNamespaceScope(*NSD);322 if (!Scope.empty())323 ScopeRefsInFile = std::max(324 ScopeRefsInFile, MainFileSignals->RelatedNamespaces.lookup(Scope));325 }326 }327}328 329void SymbolRelevanceSignals::merge(const CodeCompletionResult &SemaCCResult) {330 if (SemaCCResult.Availability == CXAvailability_NotAvailable ||331 SemaCCResult.Availability == CXAvailability_NotAccessible)332 Forbidden = true;333 334 if (SemaCCResult.Declaration) {335 SemaSaysInScope = true;336 // We boost things that have decls in the main file. We give a fixed score337 // for all other declarations in sema as they are already included in the338 // translation unit.339 float DeclProximity = (hasDeclInMainFile(*SemaCCResult.Declaration) ||340 hasUsingDeclInMainFile(SemaCCResult))341 ? 1.0342 : 0.6;343 SemaFileProximityScore = std::max(DeclProximity, SemaFileProximityScore);344 IsInstanceMember |= isInstanceMember(SemaCCResult.Declaration);345 InBaseClass |= SemaCCResult.InBaseClass;346 }347 348 computeASTSignals(SemaCCResult);349 // Declarations are scoped, others (like macros) are assumed global.350 if (SemaCCResult.Declaration)351 Scope = std::min(Scope, computeScope(SemaCCResult.Declaration));352 353 NeedsFixIts = !SemaCCResult.FixIts.empty();354}355 356static float fileProximityScore(unsigned FileDistance) {357 // Range: [0, 1]358 // FileDistance = [0, 1, 2, 3, 4, .., FileDistance::Unreachable]359 // Score = [1, 0.82, 0.67, 0.55, 0.45, .., 0]360 if (FileDistance == FileDistance::Unreachable)361 return 0;362 // Assume approximately default options are used for sensible scoring.363 return std::exp(FileDistance * -0.4f / FileDistanceOptions().UpCost);364}365 366static float scopeProximityScore(unsigned ScopeDistance) {367 // Range: [0.6, 2].368 // ScopeDistance = [0, 1, 2, 3, 4, 5, 6, 7, .., FileDistance::Unreachable]369 // Score = [2.0, 1.55, 1.2, 0.93, 0.72, 0.65, 0.65, 0.65, .., 0.6]370 if (ScopeDistance == FileDistance::Unreachable)371 return 0.6f;372 return std::max(0.65, 2.0 * std::pow(0.6, ScopeDistance / 2.0));373}374 375static std::optional<llvm::StringRef>376wordMatching(llvm::StringRef Name, const llvm::StringSet<> *ContextWords) {377 if (ContextWords)378 for (const auto &Word : ContextWords->keys())379 if (Name.contains_insensitive(Word))380 return Word;381 return std::nullopt;382}383 384SymbolRelevanceSignals::DerivedSignals385SymbolRelevanceSignals::calculateDerivedSignals() const {386 DerivedSignals Derived;387 Derived.NameMatchesContext = wordMatching(Name, ContextWords).has_value();388 Derived.FileProximityDistance = !FileProximityMatch || SymbolURI.empty()389 ? FileDistance::Unreachable390 : FileProximityMatch->distance(SymbolURI);391 if (ScopeProximityMatch) {392 // For global symbol, the distance is 0.393 Derived.ScopeProximityDistance =394 SymbolScope ? ScopeProximityMatch->distance(*SymbolScope) : 0;395 }396 return Derived;397}398 399float SymbolRelevanceSignals::evaluateHeuristics() const {400 DerivedSignals Derived = calculateDerivedSignals();401 float Score = 1;402 403 if (Forbidden)404 return 0;405 406 Score *= NameMatch;407 408 // File proximity scores are [0,1] and we translate them into a multiplier in409 // the range from 1 to 3.410 Score *= 1 + 2 * std::max(fileProximityScore(Derived.FileProximityDistance),411 SemaFileProximityScore);412 413 if (ScopeProximityMatch)414 // Use a constant scope boost for sema results, as scopes of sema results415 // can be tricky (e.g. class/function scope). Set to the max boost as we416 // don't load top-level symbols from the preamble and sema results are417 // always in the accessible scope.418 Score *= SemaSaysInScope419 ? 2.0420 : scopeProximityScore(Derived.ScopeProximityDistance);421 422 if (Derived.NameMatchesContext)423 Score *= 1.5;424 425 // Symbols like local variables may only be referenced within their scope.426 // Conversely if we're in that scope, it's likely we'll reference them.427 if (Query == CodeComplete) {428 // The narrower the scope where a symbol is visible, the more likely it is429 // to be relevant when it is available.430 switch (Scope) {431 case GlobalScope:432 break;433 case FileScope:434 Score *= 1.5f;435 break;436 case ClassScope:437 Score *= 2;438 break;439 case FunctionScope:440 Score *= 4;441 break;442 }443 } else {444 // For non-completion queries, the wider the scope where a symbol is445 // visible, the more likely it is to be relevant.446 switch (Scope) {447 case GlobalScope:448 break;449 case FileScope:450 Score *= 0.5f;451 break;452 default:453 // TODO: Handle other scopes as we start to use them for index results.454 break;455 }456 }457 458 if (TypeMatchesPreferred)459 Score *= 5.0;460 461 // Penalize non-instance members when they are accessed via a class instance.462 if (!IsInstanceMember &&463 (Context == CodeCompletionContext::CCC_DotMemberAccess ||464 Context == CodeCompletionContext::CCC_ArrowMemberAccess)) {465 Score *= 0.2f;466 }467 468 if (InBaseClass)469 Score *= 0.5f;470 471 // Penalize for FixIts.472 if (NeedsFixIts)473 Score *= 0.5f;474 475 // Use a sigmoid style boosting function similar to `References`, which flats476 // out nicely for large values. This avoids a sharp gradient for heavily477 // referenced symbols. Use smaller gradient for ScopeRefsInFile since ideally478 // MainFileRefs <= ScopeRefsInFile.479 if (MainFileRefs >= 2) {480 // E.g.: (2, 1.12), (9, 2.0), (48, 3.0).481 float S = std::pow(MainFileRefs, -0.11);482 Score *= 11.0 * (1 - S) / (1 + S) + 0.7;483 }484 if (ScopeRefsInFile >= 2) {485 // E.g.: (2, 1.04), (14, 2.0), (109, 3.0), (400, 3.6).486 float S = std::pow(ScopeRefsInFile, -0.10);487 Score *= 10.0 * (1 - S) / (1 + S) + 0.7;488 }489 490 return Score;491}492 493llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,494 const SymbolRelevanceSignals &S) {495 OS << llvm::formatv("=== Symbol relevance: {0}\n", S.evaluateHeuristics());496 OS << llvm::formatv("\tName: {0}\n", S.Name);497 OS << llvm::formatv("\tName match: {0}\n", S.NameMatch);498 if (S.ContextWords)499 OS << llvm::formatv(500 "\tMatching context word: {0}\n",501 wordMatching(S.Name, S.ContextWords).value_or("<none>"));502 OS << llvm::formatv("\tForbidden: {0}\n", S.Forbidden);503 OS << llvm::formatv("\tNeedsFixIts: {0}\n", S.NeedsFixIts);504 OS << llvm::formatv("\tIsInstanceMember: {0}\n", S.IsInstanceMember);505 OS << llvm::formatv("\tInBaseClass: {0}\n", S.InBaseClass);506 OS << llvm::formatv("\tContext: {0}\n", getCompletionKindString(S.Context));507 OS << llvm::formatv("\tQuery type: {0}\n", static_cast<int>(S.Query));508 OS << llvm::formatv("\tScope: {0}\n", static_cast<int>(S.Scope));509 510 OS << llvm::formatv("\tSymbol URI: {0}\n", S.SymbolURI);511 OS << llvm::formatv("\tSymbol scope: {0}\n",512 S.SymbolScope ? *S.SymbolScope : "<None>");513 514 SymbolRelevanceSignals::DerivedSignals Derived = S.calculateDerivedSignals();515 if (S.FileProximityMatch) {516 unsigned Score = fileProximityScore(Derived.FileProximityDistance);517 OS << llvm::formatv("\tIndex URI proximity: {0} (distance={1})\n", Score,518 Derived.FileProximityDistance);519 }520 OS << llvm::formatv("\tSema file proximity: {0}\n", S.SemaFileProximityScore);521 522 OS << llvm::formatv("\tSema says in scope: {0}\n", S.SemaSaysInScope);523 if (S.ScopeProximityMatch)524 OS << llvm::formatv("\tIndex scope boost: {0}\n",525 scopeProximityScore(Derived.ScopeProximityDistance));526 527 OS << llvm::formatv(528 "\tType matched preferred: {0} (Context type: {1}, Symbol type: {2}\n",529 S.TypeMatchesPreferred, S.HadContextType, S.HadSymbolType);530 531 return OS;532}533 534float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance) {535 return SymbolQuality * SymbolRelevance;536}537 538// Produces an integer that sorts in the same order as F.539// That is: a < b <==> encodeFloat(a) < encodeFloat(b).540static uint32_t encodeFloat(float F) {541 static_assert(std::numeric_limits<float>::is_iec559);542 constexpr uint32_t TopBit = ~(~uint32_t{0} >> 1);543 544 // Get the bits of the float. Endianness is the same as for integers.545 uint32_t U = llvm::bit_cast<uint32_t>(F);546 // IEEE 754 floats compare like sign-magnitude integers.547 if (U & TopBit) // Negative float.548 return 0 - U; // Map onto the low half of integers, order reversed.549 return U + TopBit; // Positive floats map onto the high half of integers.550}551 552std::string sortText(float Score, llvm::StringRef Name) {553 // We convert -Score to an integer, and hex-encode for readability.554 // Example: [0.5, "foo"] -> "41000000foo"555 std::string S;556 llvm::raw_string_ostream OS(S);557 llvm::write_hex(OS, encodeFloat(-Score), llvm::HexPrintStyle::Lower,558 /*Width=*/2 * sizeof(Score));559 OS << Name;560 return S;561}562 563llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,564 const SignatureQualitySignals &S) {565 OS << llvm::formatv("=== Signature Quality:\n");566 OS << llvm::formatv("\tNumber of parameters: {0}\n", S.NumberOfParameters);567 OS << llvm::formatv("\tNumber of optional parameters: {0}\n",568 S.NumberOfOptionalParameters);569 OS << llvm::formatv("\tKind: {0}\n", S.Kind);570 return OS;571}572 573} // namespace clangd574} // namespace clang575