| //===--- CodeCompletionOrganizer.cpp --------------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "CodeCompletionOrganizer.h" |
| #include "swift/AST/ASTContext.h" |
| #include "swift/AST/Module.h" |
| #include "swift/IDE/CodeCompletionResultPrinter.h" |
| #include "swift/IDE/FuzzyStringMatcher.h" |
| #include "swift/Frontend/Frontend.h" |
| #include "swift/Markup/XMLUtils.h" |
| #include "clang/Basic/CharInfo.h" |
| #include "clang/Basic/Module.h" |
| #include "llvm/ADT/DenseSet.h" |
| #include "llvm/ADT/ilist.h" |
| #include "llvm/ADT/ilist_node.h" |
| #include <deque> |
| |
| using namespace SourceKit; |
| using namespace CodeCompletion; |
| using namespace swift; |
| using namespace ide; |
| |
| namespace { |
| enum class ItemKind : uint8_t { |
| None, |
| Group, |
| Result, |
| }; |
| struct Item { |
| std::string name; |
| std::string description; |
| uint8_t kind : 2; |
| uint8_t isExactMatch : 1; |
| double matchScore = 0.0; ///< The quality of the filter matching. |
| double finalScore = -1.0; ///< The final score including match and context. |
| ItemKind getKind() const { return static_cast<ItemKind>(kind); } |
| Item(ItemKind k = ItemKind::None) |
| : kind(static_cast<decltype(kind)>(k)), isExactMatch(0) {} |
| virtual ~Item() {} |
| }; |
| struct Result : public Item { |
| Completion *value; |
| Result(Completion *result = nullptr) |
| : Item(ItemKind::Result), value(result) {} |
| static bool classof(const Item *item) { |
| return item->getKind() == ItemKind::Result; |
| } |
| }; |
| class ImportDepth { |
| llvm::StringMap<uint8_t> depths; |
| |
| public: |
| ImportDepth() = default; |
| ImportDepth(ASTContext &context, const CompilerInvocation &invocation); |
| |
| Optional<uint8_t> lookup(StringRef module) { |
| auto I = depths.find(module); |
| if (I == depths.end()) |
| return None; |
| return I->getValue(); |
| } |
| }; |
| } // end anonymous namespace |
| |
| struct CodeCompletion::Group : public Item { |
| std::vector<std::unique_ptr<Item>> contents; |
| Group() : Item(ItemKind::Group) {} |
| static bool classof(const Item *item) { |
| return item->getKind() == ItemKind::Group; |
| } |
| }; |
| |
| //===----------------------------------------------------------------------===// |
| // extendCompletions |
| //===----------------------------------------------------------------------===// |
| |
| std::vector<Completion *> SourceKit::CodeCompletion::extendCompletions( |
| ArrayRef<SwiftResult *> swiftResults, CompletionSink &sink, |
| SwiftCompletionInfo &info, const NameToPopularityMap *nameToPopularity, |
| const Options &options, Completion *prefix, |
| Optional<SemanticContextKind> overrideContext, |
| Optional<SemanticContextKind> overrideOperatorContext) { |
| |
| ImportDepth depth; |
| if (info.swiftASTContext) { |
| // Build import depth map. |
| depth = ImportDepth(*info.swiftASTContext, *info.invocation); |
| } |
| |
| if (info.completionContext) |
| sink.adoptSwiftSink(info.completionContext->getResultSink()); |
| |
| std::vector<Completion *> results; |
| for (auto *result : swiftResults) { |
| CompletionBuilder builder(sink, *result); |
| if (result->getSemanticContext() == SemanticContextKind::OtherModule) { |
| builder.setModuleImportDepth(depth.lookup(result->getModuleName())); |
| |
| if (info.completionContext->typeContextKind == TypeContextKind::Required && |
| result->getKind() == Completion::Declaration) { |
| // FIXME: because other-module results are cached, they will not be |
| // given a type-relation of invalid. As a hack, we look at the text of |
| // the result type and look for 'Void'. |
| bool isVoid = false; |
| auto chunks = result->getCompletionString()->getChunks(); |
| for (auto i = chunks.begin(), e = chunks.end(); i != e; ++i) { |
| using ChunkKind = ide::CodeCompletionString::Chunk::ChunkKind; |
| bool isVoid = false; |
| if (i->is(ChunkKind::TypeAnnotation)) { |
| isVoid = i->getText() == "Void"; |
| break; |
| } else if (i->is(ChunkKind::TypeAnnotationBegin)) { |
| auto n = i + 1, t = i + 2; |
| isVoid = |
| // i+1 has text 'Void'. |
| n != e && n->hasText() && n->getText() == "Void" && |
| // i+2 terminates the group. |
| (t == e || t->endsPreviousNestedGroup(i->getNestingLevel())); |
| break; |
| } |
| } |
| if (isVoid) |
| builder.setExpectedTypeRelation(Completion::Invalid); |
| } |
| } |
| |
| if (prefix) { |
| builder.setPrefix(prefix->getCompletionString()); |
| builder.setSemanticContext(prefix->getSemanticContext()); |
| } |
| |
| if (overrideOperatorContext && result->isOperator()) { |
| builder.setSemanticContext(*overrideOperatorContext); |
| } else if (overrideContext) { |
| builder.setSemanticContext(*overrideContext); |
| } |
| |
| // If this result is not from the current module, try to get a popularity |
| // score for it. |
| if (nameToPopularity) { |
| builder.setPopularityFactor( |
| nameToPopularity->lookup(builder.getOriginalName())); |
| } |
| |
| results.push_back(builder.finish()); |
| } |
| |
| return results; |
| } |
| |
| static StringRef copyString(llvm::BumpPtrAllocator &allocator, StringRef str); |
| |
| bool SourceKit::CodeCompletion::addCustomCompletions( |
| CompletionSink &sink, std::vector<Completion *> &completions, |
| ArrayRef<CustomCompletionInfo> customCompletions, |
| CompletionKind completionKind) { |
| |
| auto addCompletion = [&](CustomCompletionInfo customCompletion) { |
| using Chunk = CodeCompletionString::Chunk; |
| auto nameCopy = copyString(sink.allocator, customCompletion.Name); |
| auto chunk = Chunk::createWithText(Chunk::ChunkKind::Text, 0, nameCopy); |
| auto *completionString = |
| CodeCompletionString::create(sink.allocator, chunk); |
| CodeCompletion::SwiftResult swiftResult( |
| CodeCompletion::SwiftResult::ResultKind::Pattern, |
| SemanticContextKind::ExpressionSpecific, |
| /*NumBytesToErase=*/0, completionString, |
| CodeCompletionResult::ExpectedTypeRelation::Unknown); |
| |
| CompletionBuilder builder(sink, swiftResult); |
| builder.setCustomKind(customCompletion.Kind); |
| completions.push_back(builder.finish()); |
| }; |
| |
| bool changed = false; |
| |
| for (auto &custom : customCompletions) { |
| switch (completionKind) { |
| case CompletionKind::StmtOrExpr: |
| if (custom.Contexts.contains(CustomCompletionInfo::Stmt)) { |
| changed = true; |
| addCompletion(custom); |
| } |
| break; |
| case CompletionKind::PostfixExprBeginning: |
| case CompletionKind::CallArg: |
| case CompletionKind::ReturnStmtExpr: |
| case CompletionKind::YieldStmtExpr: |
| if (custom.Contexts.contains(CustomCompletionInfo::Expr)) { |
| changed = true; |
| addCompletion(custom); |
| } |
| break; |
| case CompletionKind::ForEachSequence: |
| if (custom.Contexts.contains(CustomCompletionInfo::ForEachSequence)) { |
| changed = true; |
| addCompletion(custom); |
| } |
| break; |
| case CompletionKind::TypeDeclResultBeginning: |
| case CompletionKind::TypeSimpleBeginning: |
| if (custom.Contexts.contains(CustomCompletionInfo::Type)) { |
| changed = true; |
| addCompletion(custom); |
| } |
| break; |
| default: |
| break; |
| } |
| } |
| |
| return changed; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // CodeCompletionOrganizer::Impl declaration |
| //===----------------------------------------------------------------------===// |
| |
| class CodeCompletionOrganizer::Impl { |
| std::unique_ptr<Group> rootGroup; |
| CompletionKind completionKind; |
| TypeContextKind typeContextKind; |
| |
| void groupStemsRecursive(Group *group, bool recurseIntoNewGroups, |
| StringRef(getStem)(StringRef)); |
| |
| public: |
| Impl(CompletionKind kind, TypeContextKind typeContextKind); |
| |
| void addCompletionsWithFilter(ArrayRef<Completion *> completions, |
| StringRef filterText, Options options, |
| const FilterRules &rules, |
| Completion *&exactMatch); |
| |
| void sort(Options options); |
| |
| void groupOverloads() { |
| groupStemsRecursive( |
| rootGroup.get(), /*recurseIntoNewGroups*/ false, [](StringRef name) { |
| auto endIdx = name.find_first_of("(["); |
| if (endIdx == 0 && !name.empty()) |
| return name.slice(0, 1); // [ => subscript, ( => initializer |
| return name.slice(0, endIdx); |
| }); |
| } |
| |
| void groupStems() { |
| groupStemsRecursive(rootGroup.get(), /*recurseIntoNewGroups*/ true, |
| [](StringRef name) { |
| unsigned i = 0; |
| while (i < name.size()) { |
| char c = name[i]; |
| // FIXME: unicode |
| if (i > 0 && clang::isUppercase(c) && |
| !clang::isUppercase(name[i - 1])) |
| break; |
| if (!clang::isAlphanumeric(c)) |
| break; |
| ++i; |
| } |
| if (i == 0 && !name.empty()) |
| return name.slice(0, 1); |
| return name.slice(0, i); |
| }); |
| } |
| |
| CodeCompletionViewRef takeView() { |
| assert(rootGroup); |
| auto view = std::make_shared<CodeCompletionView>(); |
| view->rootGroup = rootGroup.release(); // View takes ownership. |
| |
| // Reset fields manually in case the move constructors don't. |
| rootGroup = nullptr; |
| |
| return view; |
| } |
| }; |
| |
| //===----------------------------------------------------------------------===// |
| // CodeCompletionOrganizer implementation |
| //===----------------------------------------------------------------------===// |
| |
| CodeCompletionOrganizer::CodeCompletionOrganizer(const Options &options, |
| CompletionKind kind, |
| TypeContextKind typeContextKind) |
| : impl(*new Impl(kind, typeContextKind)), options(options) {} |
| CodeCompletionOrganizer::~CodeCompletionOrganizer() { delete &impl; } |
| |
| void CodeCompletionOrganizer::preSortCompletions( |
| llvm::MutableArrayRef<Completion *> completions) { |
| // We do a case-sensitive sort here, then do a case-insensitive sort after any |
| // name-based grouping. |
| |
| llvm::array_pod_sort(completions.begin(), completions.end(), |
| [](Completion *const *a, Completion *const *b) { |
| |
| // Sort first by filter name (case-sensitive). |
| if (int primary = (*a)->getName().compare((*b)->getName())) |
| return primary; |
| |
| // Next, sort by full description text. |
| return (*a)->getDescription().compare((*b)->getDescription()); |
| }); |
| } |
| |
| void CodeCompletionOrganizer::addCompletionsWithFilter( |
| ArrayRef<Completion *> completions, StringRef filterText, |
| const FilterRules &rules, Completion *&exactMatch) { |
| impl.addCompletionsWithFilter(completions, filterText, options, rules, |
| exactMatch); |
| } |
| |
| void CodeCompletionOrganizer::groupAndSort(const Options &options) { |
| if (options.groupStems) |
| impl.groupStems(); |
| else if (options.groupOverloads) |
| impl.groupOverloads(); |
| |
| impl.sort(options); |
| } |
| |
| CodeCompletionViewRef CodeCompletionOrganizer::takeResultsView() { |
| return impl.takeView(); |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // ImportDepth |
| //===----------------------------------------------------------------------===// |
| |
| ImportDepth::ImportDepth(ASTContext &context, |
| const CompilerInvocation &invocation) { |
| llvm::DenseSet<ModuleDecl *> seen; |
| std::deque<std::pair<ModuleDecl *, uint8_t>> worklist; |
| |
| StringRef mainModule = invocation.getModuleName(); |
| auto *main = context.getLoadedModule(context.getIdentifier(mainModule)); |
| assert(main && "missing main module"); |
| worklist.emplace_back(main, uint8_t(0)); |
| |
| // Imports from -import-name such as Playground auxiliary sources are treated |
| // specially by applying import depth 0. |
| llvm::StringSet<> auxImports; |
| for (StringRef moduleName : |
| invocation.getFrontendOptions().getImplicitImportModuleNames()) |
| auxImports.insert(moduleName); |
| |
| // Private imports from this module. |
| // FIXME: only the private imports from the current source file. |
| // FIXME: ImportFilterKind::ShadowedBySeparateOverlay? |
| SmallVector<ModuleDecl::ImportedModule, 16> mainImports; |
| main->getImportedModules(mainImports, |
| {ModuleDecl::ImportFilterKind::Private, |
| ModuleDecl::ImportFilterKind::ImplementationOnly}); |
| for (auto &import : mainImports) { |
| uint8_t depth = 1; |
| if (auxImports.count(import.importedModule->getName().str())) |
| depth = 0; |
| worklist.emplace_back(import.importedModule, depth); |
| } |
| |
| // Fill depths with BFS over module imports. |
| while (!worklist.empty()) { |
| ModuleDecl *module; |
| uint8_t depth; |
| std::tie(module, depth) = worklist.front(); |
| worklist.pop_front(); |
| |
| if (!seen.insert(module).second) |
| continue; |
| |
| // Insert new module:depth mapping. |
| const clang::Module *CM = module->findUnderlyingClangModule(); |
| if (CM) { |
| depths[CM->getFullModuleName()] = depth; |
| } else { |
| depths[module->getName().str()] = depth; |
| } |
| |
| // Add imports to the worklist. |
| SmallVector<ModuleDecl::ImportedModule, 16> imports; |
| module->getImportedModules(imports); |
| for (auto &import : imports) { |
| uint8_t next = std::max(depth, uint8_t(depth + 1)); // unsigned wrap |
| |
| // Implicitly imported sub-modules get the same depth as their parent. |
| if (const clang::Module *CMI = |
| import.importedModule->findUnderlyingClangModule()) |
| if (CM && CMI->isSubModuleOf(CM)) |
| next = depth; |
| worklist.emplace_back(import.importedModule, next); |
| } |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // CodeCompletionOrganizer::Impl utilities |
| //===----------------------------------------------------------------------===// |
| |
| static StringRef copyString(llvm::BumpPtrAllocator &allocator, StringRef str) { |
| char *newStr = allocator.Allocate<char>(str.size()); |
| std::copy(str.begin(), str.end(), newStr); |
| return StringRef(newStr, str.size()); |
| } |
| |
| static std::unique_ptr<Group> make_group(StringRef name) { |
| auto g = std::make_unique<Group>(); |
| g->name = name.str(); |
| g->description = name.str(); |
| return g; |
| } |
| |
| static std::unique_ptr<Result> make_result(Completion *result) { |
| auto r = std::make_unique<Result>(result); |
| r->name = result->getName().str(); |
| r->description = result->getDescription().str(); |
| return r; |
| } |
| |
| |
| //===----------------------------------------------------------------------===// |
| // CodeCompletionOrganizer::Impl implementation |
| //===----------------------------------------------------------------------===// |
| |
| CodeCompletionOrganizer::Impl::Impl(CompletionKind kind, TypeContextKind typeContextKind) |
| : completionKind(kind), typeContextKind(typeContextKind) { |
| assert(!rootGroup && "initialized twice"); |
| rootGroup = make_group(""); |
| } |
| |
| static bool matchesExpectedStyle(Completion *completion, NameStyle style) { |
| switch (completion->getAssociatedDeclKind()) { |
| case CodeCompletionDeclKind::Class: |
| case CodeCompletionDeclKind::Struct: |
| case CodeCompletionDeclKind::Enum: |
| case CodeCompletionDeclKind::Protocol: |
| case CodeCompletionDeclKind::TypeAlias: |
| case CodeCompletionDeclKind::AssociatedType: |
| return style.possiblyUpperCamelCase(); |
| |
| case CodeCompletionDeclKind::StaticMethod: |
| case CodeCompletionDeclKind::InstanceMethod: |
| case CodeCompletionDeclKind::FreeFunction: |
| case CodeCompletionDeclKind::StaticVar: |
| case CodeCompletionDeclKind::InstanceVar: |
| case CodeCompletionDeclKind::LocalVar: |
| case CodeCompletionDeclKind::GlobalVar: |
| return style.possiblyLowerCamelCase(); |
| |
| default: |
| return true; // Conservatively say yes. |
| } |
| } |
| |
| static bool isHighPriorityKeyword(CodeCompletionKeywordKind kind) { |
| switch (kind) { |
| case CodeCompletionKeywordKind::kw_let: |
| case CodeCompletionKeywordKind::kw_var: |
| case CodeCompletionKeywordKind::kw_if: |
| case CodeCompletionKeywordKind::kw_for: |
| case CodeCompletionKeywordKind::kw_while: |
| case CodeCompletionKeywordKind::kw_return: |
| case CodeCompletionKeywordKind::kw_func: |
| return true; |
| default: |
| return false; |
| } |
| } |
| |
| bool FilterRules::hideFilterName(StringRef name) const { |
| auto I = hideByFilterName.find(name); |
| if (I != hideByFilterName.end()) |
| return I->getValue(); |
| return hideAll; |
| } |
| |
| bool FilterRules::hideCompletion(Completion *completion) const { |
| return hideCompletion(completion, completion->getName(), |
| completion->getDescription(), |
| completion->getCustomKind()); |
| } |
| |
| bool FilterRules::hideCompletion(SwiftResult *completion, StringRef filterName, |
| StringRef description, |
| void *customKind) const { |
| |
| if (!description.empty()) { |
| auto I = hideByDescription.find(description); |
| if (I != hideByDescription.end()) |
| return I->getValue(); |
| } |
| |
| if (!filterName.empty()) { |
| auto I = hideByFilterName.find(filterName); |
| if (I != hideByFilterName.end()) |
| return I->getValue(); |
| } |
| |
| switch (completion->getKind()) { |
| case Completion::BuiltinOperator: |
| case Completion::Declaration: |
| break; |
| case Completion::Keyword: { |
| auto I = hideKeyword.find(completion->getKeywordKind()); |
| if (I != hideKeyword.end()) |
| return I->second; |
| if (hideAllKeywords) |
| return true; |
| break; |
| } |
| case Completion::Pattern: { |
| if (customKind) { |
| // FIXME: individual custom completions |
| if (hideCustomCompletions) |
| return true; |
| } |
| break; |
| } |
| case Completion::Literal: { |
| auto I = hideValueLiteral.find(completion->getLiteralKind()); |
| if (I != hideValueLiteral.end()) |
| return I->second; |
| if (hideAllValueLiterals) |
| return true; |
| break; |
| } |
| } |
| |
| if (!completion->getModuleName().empty()) { |
| // FIXME: try each submodule chain starting from the most specific. |
| auto M = hideModule.find(completion->getModuleName()); |
| if (M != hideModule.end()) |
| return M->getValue(); |
| } |
| |
| return hideAll; |
| } |
| |
| void CodeCompletionOrganizer::Impl::addCompletionsWithFilter( |
| ArrayRef<Completion *> completions, StringRef filterText, Options options, |
| const FilterRules &rules, Completion *&exactMatch) { |
| assert(rootGroup); |
| |
| auto &contents = rootGroup->contents; |
| |
| // If we have no filter text, add all non-hidden results. |
| if (filterText.empty()) { |
| bool hideLowPriority = |
| options.hideLowPriority && |
| completionKind != CompletionKind::TypeDeclResultBeginning && |
| completionKind != CompletionKind::TypeSimpleBeginning && |
| completionKind != CompletionKind::PostfixExpr; |
| for (Completion *completion : completions) { |
| if (rules.hideCompletion(completion)) |
| continue; |
| |
| if (options.hideLowPriority && |
| (completion->isNotRecommended() || |
| completion->getExpectedTypeRelation() == Completion::Invalid)) |
| continue; |
| |
| NameStyle style(completion->getName()); |
| bool hideUnderscore = options.hideUnderscores && style.leadingUnderscores; |
| if (hideUnderscore && options.reallyHideAllUnderscores) |
| continue; |
| |
| bool hideByNameStyle = options.hideByNameStyle && |
| completion->getKind() == Completion::Declaration && |
| !matchesExpectedStyle(completion, style); |
| |
| hideByNameStyle |= hideUnderscore; |
| |
| switch (completion->getSemanticContext()) { |
| case SemanticContextKind::Super: |
| case SemanticContextKind::OutsideNominal: |
| if (hideUnderscore) |
| continue; |
| break; |
| case SemanticContextKind::OtherModule: |
| case SemanticContextKind::None: |
| if (auto depth = completion->getModuleImportDepth()) { |
| if (*depth == 0) // Treat as if it's "thismodule" |
| break; |
| } |
| if (completion->getExpectedTypeRelation() >= Completion::Convertible || |
| (completion->getKind() == Completion::Literal && |
| completionKind != CompletionKind::StmtOrExpr && |
| typeContextKind < TypeContextKind::Required)) |
| break; |
| |
| if (completion->getKind() == Completion::Keyword && |
| completionKind == CompletionKind::StmtOrExpr && |
| isHighPriorityKeyword(completion->getKeywordKind())) |
| break; |
| |
| if (hideByNameStyle || hideLowPriority) |
| continue; |
| break; |
| default: |
| break; |
| } |
| |
| // Build wrapper and add to results. |
| contents.push_back(make_result(completion)); |
| } |
| return; |
| } |
| |
| FuzzyStringMatcher pattern(filterText); |
| pattern.normalize = true; |
| for (Completion *completion : completions) { |
| if (rules.hideCompletion(completion)) |
| continue; |
| |
| // Hide literals other than the ones that are also keywords if they don't |
| // match the expected types. |
| if (completion->getKind() == Completion::Literal && |
| typeContextKind == TypeContextKind::Required && |
| completion->getExpectedTypeRelation() < Completion::Convertible && |
| completion->getLiteralKind() != |
| CodeCompletionLiteralKind::BooleanLiteral && |
| completion->getLiteralKind() != CodeCompletionLiteralKind::NilLiteral) |
| continue; |
| |
| bool match = false; |
| if (options.fuzzyMatching && filterText.size() >= options.minFuzzyLength) { |
| match = pattern.matchesCandidate(completion->getName()); |
| } else { |
| match = completion->getName().startswith_lower(filterText); |
| } |
| |
| bool isExactMatch = match && completion->getName().equals_lower(filterText); |
| |
| if (isExactMatch) { |
| if (!exactMatch) { // first match |
| exactMatch = completion; |
| } else if (completion->getName() != exactMatch->getName()) { |
| if (completion->getName() == filterText && // first case-sensitive match |
| exactMatch->getName() != filterText) |
| exactMatch = completion; |
| else if (pattern.scoreCandidate(completion->getName()) > // better match |
| pattern.scoreCandidate(exactMatch->getName())) |
| exactMatch = completion; |
| } |
| |
| match = (options.addInnerResults || options.addInnerOperators) |
| ? options.includeExactMatch |
| : true; |
| } |
| |
| // Build wrapper and add to results. |
| if (match) { |
| auto wrapper = make_result(completion); |
| if (options.fuzzyMatching) { |
| wrapper->matchScore = pattern.scoreCandidate(completion->getName()); |
| } |
| wrapper->isExactMatch = isExactMatch; |
| |
| contents.push_back(std::move(wrapper)); |
| } |
| } |
| } |
| |
| static double getSemanticContextScore(bool useImportDepth, |
| Completion *completion) { |
| double order = -1.0; |
| switch (completion->getSemanticContext()) { |
| case SemanticContextKind::ExpressionSpecific: order = 0; break; |
| case SemanticContextKind::Local: order = 1; break; |
| case SemanticContextKind::CurrentNominal: order = 2; break; |
| case SemanticContextKind::Super: order = 3; break; |
| case SemanticContextKind::OutsideNominal: order = 4; break; |
| case SemanticContextKind::CurrentModule: order = 5; break; |
| case SemanticContextKind::OtherModule: { |
| unsigned depth = Completion::maxModuleImportDepth + 1; // unknown > known |
| if (useImportDepth && completion->getModuleImportDepth()) |
| depth = *completion->getModuleImportDepth(); |
| // We treat depth == 0 the same as CurrentModule. |
| // Note: there is a gap in between that we use for keywords. |
| order = (depth == 0) ? 5.0 : 6.0; // Base value. |
| order += double(depth) / (Completion::maxModuleImportDepth + 1); |
| assert((depth == 0 && order == 5.0) || |
| (depth && 6.0 <= order && order <= 7.0)); |
| break; |
| } |
| case SemanticContextKind::None: { |
| order = completion->getKind() == Completion::Keyword ? 5.5 : 8.0; |
| break; |
| } |
| } |
| assert(0.0 <= order && order <= 8.0); |
| return (8.0 - order) / 8.0; |
| } |
| |
| static double combinedScore(const Options &options, double matchScore, |
| Completion *completion) { |
| |
| double score = matchScore * options.fuzzyMatchWeight; |
| score += getSemanticContextScore(options.useImportDepth, completion) * |
| options.semanticContextWeight; |
| |
| PopularityFactor popularity = completion->getPopularityFactor(); |
| if (popularity.isPopular()) |
| score += popularity.rawValue + options.popularityBonus; |
| else if (popularity.isUnpopular()) |
| score += popularity.rawValue - options.popularityBonus; |
| |
| return score; |
| } |
| |
| static int compareResultName(Item &a, Item &b) { |
| // Sort first by filter name (case-insensitive). |
| if (int primary = StringRef(a.name).compare_lower(b.name)) |
| return primary; |
| |
| // Next, sort by full description text. |
| return a.description.compare(b.description); |
| }; |
| |
| namespace { |
| enum class ResultBucket { |
| NotRecommended, |
| Normal, |
| Literal, |
| NormalTypeMatch, |
| LiteralTypeMatch, |
| HighPriorityKeyword, |
| Operator, |
| ExpressionSpecific, |
| ExactMatch, |
| }; |
| } // end anonymous namespace |
| |
| static ResultBucket getResultBucket(Item &item, bool hasRequiredTypes, |
| bool skipMetaGroups = false) { |
| if (item.isExactMatch && !skipMetaGroups) |
| return ResultBucket::ExactMatch; |
| |
| if (isa<Group>(item)) |
| return ResultBucket::Normal; // FIXME: take best contained result. |
| auto *completion = cast<Result>(item).value; |
| |
| if (completion->isNotRecommended() && !skipMetaGroups) |
| return ResultBucket::NotRecommended; |
| |
| if (completion->getSemanticContext() == |
| SemanticContextKind::ExpressionSpecific && |
| !skipMetaGroups) |
| return ResultBucket::ExpressionSpecific; |
| |
| if (completion->isOperator()) |
| return ResultBucket::Operator; |
| |
| switch (completion->getKind()) { |
| case Completion::Literal: |
| if (completion->getExpectedTypeRelation() >= Completion::Convertible) { |
| return ResultBucket::LiteralTypeMatch; |
| } else if (!hasRequiredTypes) { |
| return ResultBucket::Literal; |
| } else { |
| // When we have type context, we still show literals that are keywords, |
| // but we treat them as keywords instead of literals for prioritization. |
| return ResultBucket::Normal; |
| } |
| case Completion::Keyword: |
| return isHighPriorityKeyword(completion->getKeywordKind()) |
| ? ResultBucket::HighPriorityKeyword |
| : ResultBucket::Normal; |
| case Completion::Pattern: |
| case Completion::Declaration: |
| switch (completion->getExpectedTypeRelation()) { |
| case swift::ide::CodeCompletionResult::Convertible: |
| case swift::ide::CodeCompletionResult::Identical: |
| return ResultBucket::NormalTypeMatch; |
| case swift::ide::CodeCompletionResult::NotApplicable: |
| case swift::ide::CodeCompletionResult::Unknown: |
| case swift::ide::CodeCompletionResult::Unrelated: |
| return ResultBucket::Normal; |
| case swift::ide::CodeCompletionResult::Invalid: |
| if (!skipMetaGroups) |
| return ResultBucket::NotRecommended; |
| return ResultBucket::Normal; |
| } |
| case Completion::BuiltinOperator: |
| llvm_unreachable("operators should be handled above"); |
| } |
| } |
| |
| static int compareHighPriorityKeywords(Item &a_, Item &b_) { |
| static CodeCompletionKeywordKind order[] = { |
| CodeCompletionKeywordKind::kw_let, |
| CodeCompletionKeywordKind::kw_var, |
| CodeCompletionKeywordKind::kw_if, |
| CodeCompletionKeywordKind::kw_for, |
| CodeCompletionKeywordKind::kw_while, |
| CodeCompletionKeywordKind::kw_return, |
| CodeCompletionKeywordKind::kw_func, |
| }; |
| auto size = sizeof(order) / sizeof(order[0]); |
| |
| auto getIndex = [=](Item &item) { |
| auto I = std::find(order, &order[size], cast<Result>(item).value->getKeywordKind()); |
| assert(I != &order[size]); |
| return std::distance(order, I); |
| }; |
| |
| auto a = getIndex(a_); |
| auto b = getIndex(b_); |
| return a < b ? -1 : (b < a ? 1 : 0); |
| } |
| |
| static int compareLiterals(Item &a_, Item &b_) { |
| static CodeCompletionLiteralKind order[] = { |
| CodeCompletionLiteralKind::IntegerLiteral, |
| CodeCompletionLiteralKind::StringLiteral, |
| CodeCompletionLiteralKind::BooleanLiteral, |
| CodeCompletionLiteralKind::ColorLiteral, |
| CodeCompletionLiteralKind::ImageLiteral, |
| CodeCompletionLiteralKind::ArrayLiteral, |
| CodeCompletionLiteralKind::DictionaryLiteral, |
| CodeCompletionLiteralKind::Tuple, |
| CodeCompletionLiteralKind::NilLiteral, |
| }; |
| auto size = sizeof(order) / sizeof(order[0]); |
| |
| auto getIndex = [=](Item &item) { |
| auto I = std::find(order, &order[size], cast<Result>(item).value->getLiteralKind()); |
| assert(I != &order[size]); |
| return std::distance(order, I); |
| }; |
| |
| auto a = getIndex(a_); |
| auto b = getIndex(b_); |
| |
| if (a != b) |
| return a < b ? -1 : 1; |
| |
| // Sort true before false instead of alphabetically. |
| if (cast<Result>(a_).value->getLiteralKind() == CodeCompletionLiteralKind::BooleanLiteral) |
| return b_.name.compare(a_.name); |
| |
| return 0; |
| } |
| |
| static int compareOperators(Item &a_, Item &b_) { |
| using CCOK = CodeCompletionOperatorKind; |
| static CCOK order[] = { |
| CCOK::Dot, // . |
| CCOK::QuestionDot, // ?. |
| CCOK::Bang, // ! |
| CCOK::LParen, // ( -- not really an operator, but treated as one in some |
| // cases. |
| CCOK::Eq, // = |
| |
| CCOK::EqEq, // == |
| CCOK::NotEq, // != |
| CCOK::Less, // < |
| CCOK::Greater, // > |
| CCOK::LessEq, // <= |
| CCOK::GreaterEq, // >= |
| |
| CCOK::Plus, // + |
| CCOK::Minus, // - |
| CCOK::Star, // * |
| CCOK::Slash, // / |
| CCOK::Modulo, // % |
| |
| CCOK::PlusEq, // += |
| CCOK::MinusEq, // -= |
| CCOK::StarEq, // *= |
| CCOK::SlashEq, // /= |
| CCOK::ModuloEq, // %= |
| |
| CCOK::AmpAmp, // && |
| CCOK::PipePipe, // || |
| |
| CCOK::Unknown, |
| |
| CCOK::Amp, // & |
| CCOK::Pipe, // | |
| CCOK::Caret, // ^ |
| CCOK::LessLess, // << |
| CCOK::GreaterGreater, // >> |
| |
| CCOK::AmpEq, // &= |
| CCOK::PipeEq, // |= |
| CCOK::CaretEq, // ^= |
| CCOK::LessLessEq, // <<= |
| CCOK::GreaterGreaterEq, // >>= |
| |
| // Range |
| CCOK::DotDotDot, // ... |
| CCOK::DotDotLess, // ..< |
| |
| CCOK::AmpStar, // &* |
| CCOK::AmpPlus, // &+ |
| CCOK::AmpMinus, // &- |
| |
| // Misc. |
| CCOK::EqEqEq, // === |
| CCOK::NotEqEq, // !== |
| CCOK::TildeEq, // ~= |
| }; |
| auto size = sizeof(order) / sizeof(order[0]); |
| |
| auto getIndex = [=](Item &item) { |
| auto I = std::find(order, &order[size], |
| cast<Result>(item).value->getOperatorKind()); |
| assert(I != &order[size]); |
| return std::distance(order, I); |
| }; |
| |
| auto a = getIndex(a_); |
| auto b = getIndex(b_); |
| return a < b ? -1 : (b < a ? 1 : 0); |
| } |
| |
| static bool isTopNonLiteralResult(Item &item, ResultBucket literalBucket) { |
| if (isa<Group>(item)) |
| return true; // FIXME: should have a semantic context for groups. |
| auto *completion = cast<Result>(item).value; |
| |
| switch (literalBucket) { |
| case ResultBucket::Literal: |
| return completion->getSemanticContext() <= |
| SemanticContextKind::CurrentNominal; |
| case ResultBucket::LiteralTypeMatch: |
| return completion->getExpectedTypeRelation() >= Completion::Convertible; |
| default: |
| llvm_unreachable("invalid literal bucket"); |
| } |
| } |
| |
| static void sortTopN(const Options &options, Group *group, |
| bool hasRequiredTypes) { |
| |
| auto &contents = group->contents; |
| if (contents.empty() || options.showTopNonLiteralResults == 0) |
| return; |
| |
| auto best = getResultBucket(*contents[0], hasRequiredTypes); |
| if (best == ResultBucket::LiteralTypeMatch || best == ResultBucket::Literal) { |
| |
| unsigned beginNewIndex = 0; |
| unsigned endNewIndex = 0; |
| for (unsigned i = 1; i < contents.size(); ++i) { |
| auto bucket = getResultBucket(*contents[i], hasRequiredTypes); |
| if (bucket < best) { |
| // This algorithm assumes we don't have both literal and |
| // literal-type-match at the start of the list. |
| assert(bucket != ResultBucket::Literal); |
| if (isTopNonLiteralResult(*contents[i], best)) { |
| beginNewIndex = i; |
| endNewIndex = beginNewIndex + 1; |
| for (; endNewIndex < contents.size() && |
| endNewIndex < beginNewIndex + options.showTopNonLiteralResults; |
| ++endNewIndex) { |
| if (!isTopNonLiteralResult(*contents[endNewIndex], best)) |
| break; |
| } |
| } |
| break; |
| } |
| } |
| |
| if (!beginNewIndex) |
| return; |
| |
| assert(endNewIndex > beginNewIndex && endNewIndex <= contents.size()); |
| |
| // Temporarily copy the first result to temporary storage. |
| SmallVector<Item *, 16> firstResults; |
| for (unsigned i = 0; i < endNewIndex; ++i) { |
| firstResults.push_back(contents[i].release()); |
| } |
| |
| // Swap the literals with the next few results. |
| for (unsigned ci = 0, i = beginNewIndex; i < endNewIndex; ++i, ++ci) { |
| assert(ci < contents.size() && !contents[ci]); |
| contents[ci] = std::unique_ptr<Item>(firstResults[i]); |
| } |
| unsigned topN = endNewIndex - beginNewIndex; |
| assert(topN <= options.showTopNonLiteralResults); |
| for (unsigned ci = topN, i = 0; i < beginNewIndex; ++i, ++ci) { |
| assert(ci < contents.size() && !contents[ci]); |
| contents[ci] = std::unique_ptr<Item>(firstResults[i]); |
| } |
| } |
| } |
| |
| static void sortRecursive(const Options &options, Group *group, |
| bool hasRequiredTypes) { |
| // Sort all of the subgroups first, and fill in the bucket for each result. |
| auto &contents = group->contents; |
| double best = -1.0; |
| for (auto &item : contents) { |
| if (auto *g = dyn_cast<Group>(item.get())) { |
| sortRecursive(options, g, hasRequiredTypes); |
| } else { |
| Result *r = cast<Result>(item.get()); |
| item->finalScore = combinedScore(options, item->matchScore, r->value); |
| } |
| |
| if (item->finalScore > best) |
| best = item->finalScore; |
| } |
| |
| group->finalScore = best; |
| |
| // Now sort the group itself. |
| |
| if (options.sortByName) { |
| llvm::array_pod_sort(contents.begin(), contents.end(), |
| [](const std::unique_ptr<Item> *a, const std::unique_ptr<Item> *b) { |
| return compareResultName(**a, **b); |
| }); |
| return; |
| } |
| |
| std::sort(contents.begin(), contents.end(), [=](const std::unique_ptr<Item> &a_, const std::unique_ptr<Item> &b_) { |
| Item &a = *a_; |
| Item &b = *b_; |
| |
| auto bucketA = getResultBucket(a, hasRequiredTypes); |
| auto bucketB = getResultBucket(b, hasRequiredTypes); |
| if (bucketA < bucketB) |
| return false; |
| else if (bucketB < bucketA) |
| return true; |
| |
| // Try again, skipping any meta groups like "expr-specific" in case that |
| // lets us order |
| if (bucketA == ResultBucket::ExactMatch || |
| bucketA == ResultBucket::ExpressionSpecific || |
| bucketA == ResultBucket::NotRecommended) { |
| bucketA = getResultBucket(a, hasRequiredTypes, /*skipMetaGroups*/ true); |
| bucketB = getResultBucket(b, hasRequiredTypes, /*skipMetaGroups*/ true); |
| if (bucketA < bucketB) |
| return false; |
| else if (bucketB < bucketA) |
| return true; |
| } |
| |
| // Special internal orderings. |
| switch (bucketA) { |
| case ResultBucket::HighPriorityKeyword: |
| return compareHighPriorityKeywords(a, b) < 0; |
| case ResultBucket::Literal: |
| case ResultBucket::LiteralTypeMatch: |
| return compareLiterals(a, b) < 0; |
| case ResultBucket::Operator: { |
| int cmp = compareOperators(a, b); |
| if (cmp != 0) |
| return cmp < 0; |
| break; |
| } |
| default: |
| break; |
| } |
| |
| // "Normal" order. |
| if (a.finalScore < b.finalScore) |
| return false; |
| else if (b.finalScore < a.finalScore) |
| return true; |
| |
| return compareResultName(a, b) < 0; |
| }); |
| } |
| |
| void CodeCompletionOrganizer::Impl::sort(Options options) { |
| bool hasRequiredTypes = typeContextKind == TypeContextKind::Required; |
| sortRecursive(options, rootGroup.get(), hasRequiredTypes); |
| if (options.showTopNonLiteralResults != 0) |
| sortTopN(options, rootGroup.get(), hasRequiredTypes); |
| } |
| |
| void CodeCompletionOrganizer::Impl::groupStemsRecursive( |
| Group *group, bool recurseIntoNewGroups, StringRef(getStem)(StringRef)) { |
| std::vector<std::unique_ptr<Item>> newContents; |
| std::vector<std::unique_ptr<Item>> &worklist = group->contents; |
| |
| auto getSubStem = [getStem](StringRef name, StringRef groupName) { |
| StringRef subName = name.slice(groupName.size(), StringRef::npos); |
| return getStem(subName); |
| }; |
| |
| if (worklist.empty()) |
| return; |
| |
| auto start = worklist.begin(); |
| while (start != worklist.end()) { |
| if (auto *g = dyn_cast<Group>(start->get())) { |
| groupStemsRecursive(g, recurseIntoNewGroups, getStem); |
| newContents.push_back(std::move(*start)); |
| ++start; |
| continue; |
| } |
| |
| StringRef stem = getSubStem((*start)->name, group->name); |
| auto end = start; |
| auto next = ++end; |
| while (end != worklist.end() && !stem.empty() && |
| stem == getSubStem((*end)->name, group->name)) |
| ++end; |
| if (end == next) { |
| // Only one element; don't group. |
| newContents.push_back(std::move(*start)); |
| start = end; // == next == ++start |
| } else if (end == worklist.end() && newContents.empty()) { |
| // Only one group; inline it. |
| // FIXME: this is wrong, we should try to sub-group. |
| assert(start == worklist.begin()); |
| std::swap(newContents, worklist); |
| break; |
| } else { |
| std::string name = (Twine(group->name) + stem).str(); |
| if (recurseIntoNewGroups) { |
| while (true) { |
| StringRef next = getSubStem((*start)->name, name); |
| if (next.empty()) |
| break; |
| auto I = start; ++I; |
| for ( ; I != end; ++I) |
| if (next != getSubStem((*I)->name, name)) |
| goto done; |
| name += next; |
| } |
| done: |
| ; // exit label |
| } |
| |
| auto newGroup = make_group(name); |
| for (; start != end; ++start) |
| newGroup->contents.push_back(std::move(*start)); |
| |
| if (recurseIntoNewGroups) |
| groupStemsRecursive(newGroup.get(), recurseIntoNewGroups, getStem); |
| newContents.push_back(std::move(newGroup)); |
| } |
| } |
| |
| group->contents = std::move(newContents); |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // CodeCompletionView |
| //===----------------------------------------------------------------------===// |
| |
| static bool walkRecursive(CodeCompletionView::Walker &walker, const Item *item) { |
| if (auto *result = dyn_cast<Result>(item)) |
| return walker.handleResult(result->value); |
| |
| walker.startGroup(item->name); |
| for (auto &child : cast<Group>(item)->contents) { |
| if (!walkRecursive(walker, child.get())) |
| return false; |
| } |
| walker.endGroup(); |
| return true; |
| } |
| |
| bool CodeCompletionView::walk(CodeCompletionView::Walker &walker) const { |
| assert(rootGroup); |
| return walkRecursive(walker, rootGroup); |
| } |
| |
| CodeCompletionView::~CodeCompletionView() { delete rootGroup; } |
| |
| unsigned LimitedResultView::getNextOffset() const { return start; } |
| |
| bool LimitedResultView::walk(CodeCompletionView::Walker &walker) const { |
| const Group *root = baseView.rootGroup; |
| walker.startGroup(root->name); |
| auto begin = root->contents.begin(); |
| auto end = root->contents.end(); |
| unsigned count = 0; |
| while (count < start && begin != end) { |
| ++count; |
| ++begin; |
| } |
| while (begin != end && (maxResults == 0 || count < start + maxResults)) { |
| if (!walkRecursive(walker, begin->get())) |
| return false; |
| ++count; |
| ++begin; |
| } |
| |
| if (begin == end) { |
| assert(maxResults == 0 || count <= start + maxResults); |
| start = 0; |
| } else { |
| start = count; |
| } |
| |
| walker.endGroup(); |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // CompletionBuilder |
| //===----------------------------------------------------------------------===// |
| |
| CompletionBuilder::CompletionBuilder(CompletionSink &sink, SwiftResult &base) |
| : sink(sink), current(base) { |
| typeRelation = current.getExpectedTypeRelation(); |
| semanticContext = current.getSemanticContext(); |
| completionString = |
| const_cast<CodeCompletionString *>(current.getCompletionString()); |
| |
| // FIXME: this works around the fact we're producing invalid completion |
| // strings for our inner "." result. |
| if (current.getCompletionString()->getFirstTextChunkIndex().hasValue()) { |
| llvm::raw_svector_ostream OSS(originalName); |
| ide::printCodeCompletionResultFilterName(current, OSS); |
| } |
| } |
| |
| void CompletionBuilder::setPrefix(CodeCompletionString *prefix) { |
| if (!prefix) |
| return; |
| |
| modified = true; |
| |
| // The underlying text is kept alive by an CompletionSink. The chunks |
| // themselves get copied into the CodeCompletionString. |
| std::vector<CodeCompletionString::Chunk> chunks; |
| chunks.reserve(prefix->getChunks().size()); |
| for (auto chunk : prefix->getChunks()) { |
| if (chunk.is(CodeCompletionString::Chunk::ChunkKind::TypeAnnotation)) |
| continue; // The type is the type of the actual result, not the prefix. |
| chunks.push_back(chunk); |
| } |
| |
| auto existing = current.getCompletionString()->getChunks(); |
| chunks.insert(chunks.end(), existing.begin(), existing.end()); |
| completionString = CodeCompletionString::create(sink.allocator, chunks); |
| } |
| |
| Completion *CompletionBuilder::finish() { |
| SwiftResult base = current; |
| llvm::SmallString<64> nameStorage; |
| StringRef name = getOriginalName(); |
| if (modified) { |
| // We've modified the original result, so build a new one. |
| auto opKind = CodeCompletionOperatorKind::None; |
| if (current.isOperator()) |
| opKind = current.getOperatorKind(); |
| |
| if (current.getKind() == SwiftResult::Declaration) { |
| base = SwiftResult( |
| semanticContext, current.getNumBytesToErase(), completionString, |
| current.getAssociatedDeclKind(), current.isSystem(), |
| current.getModuleName(), current.isNotRecommended(), |
| current.getNotRecommendedReason(), current.getBriefDocComment(), |
| current.getAssociatedUSRs(), current.getDeclKeywords(), |
| typeRelation, opKind); |
| } else { |
| base = SwiftResult(current.getKind(), semanticContext, |
| current.getNumBytesToErase(), completionString, |
| typeRelation, opKind); |
| } |
| |
| llvm::raw_svector_ostream OSS(nameStorage); |
| ide::printCodeCompletionResultFilterName(base, OSS); |
| name = OSS.str(); |
| } |
| |
| llvm::SmallString<64> description; |
| { |
| llvm::raw_svector_ostream OSS(description); |
| ide::printCodeCompletionResultDescription(base, OSS, |
| /*leadingPunctuation=*/true); |
| } |
| |
| auto *result = new (sink.allocator) |
| Completion(std::move(base), copyString(sink.allocator, name), |
| copyString(sink.allocator, description)); |
| result->moduleImportDepth = moduleImportDepth; |
| result->popularityFactor = popularityFactor; |
| result->opaqueCustomKind = customKind; |
| return result; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // NameStyle |
| //===----------------------------------------------------------------------===// |
| |
| NameStyle::NameStyle(StringRef name) |
| : leadingUnderscores(0), trailingUnderscores(0) { |
| // Trim leading and trailing underscores. |
| StringRef center = name.ltrim("_"); |
| if (center == "") |
| return; |
| leadingUnderscores = name.size() - center.size(); |
| center = center.rtrim("_"); |
| assert(!center.empty()); |
| trailingUnderscores = name.size() - center.size() - leadingUnderscores; |
| |
| unsigned pos = 0; |
| |
| enum Case { |
| None = 0, |
| Lower, |
| Upper, |
| }; |
| |
| auto caseOf = [](char c) { |
| if (clang::isLowercase(c)) |
| return Lower; |
| if (clang::isUppercase(c)) |
| return Upper; |
| return None; |
| }; |
| |
| unsigned underscores = 0; |
| unsigned caseCount[3] = {0, 0, 0}; |
| Case leadingCase = None; |
| for (; pos < center.size(); ++pos) { |
| char c = center[pos]; |
| Case curCase = caseOf(c); |
| if (!leadingCase) |
| leadingCase = curCase; |
| |
| underscores += (c == '_'); |
| caseCount[curCase] += 1; |
| } |
| |
| assert(caseCount[leadingCase] > 0); |
| |
| if (caseCount[Lower] && !caseCount[Upper]) { |
| wordDelimiter = underscores ? LowercaseWithUnderscores : Lowercase; |
| return; |
| } |
| if (caseCount[Upper] && !caseCount[Lower]) { |
| wordDelimiter = underscores ? UppercaseWithUnderscores : Uppercase; |
| return; |
| } |
| if (leadingCase && !underscores) { |
| wordDelimiter = leadingCase == Lower ? LowerCamelCase : UpperCamelCase; |
| return; |
| } |
| |
| // FIXME: should we try to choose a delimiter if there is more than one? |
| wordDelimiter = Unknown; |
| } |
