Use FuzzyMatcher for Cider completion filtering and sorting.

scheglov · commit-bot@chromium.org · commit 03429b20cd67 · 2020-04-27T04:10:09.000Z
R=brianwilkerson@google.com, keertip@google.com Change-Id: I1b8360e95327dfd4eaefaa8990105bd4750c2acc Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/144864 Reviewed-by: Brian Wilkerson <brianwilkerson@google.com> Commit-Queue: Konstantin Shcheglov <scheglov@google.com>
diff --git a/pkg/analysis_server/lib/src/cider/completion.dart b/pkg/analysis_server/lib/src/cider/completion.dart
@@ -9,10 +9,13 @@ import 'package:analysis_server/src/services/completion/completion_core.dart';
 import 'package:analysis_server/src/services/completion/completion_performance.dart';
 import 'package:analysis_server/src/services/completion/dart/completion_manager.dart';
 import 'package:analysis_server/src/services/completion/dart/local_library_contributor.dart';
+import 'package:analysis_server/src/services/completion/filtering/fuzzy_matcher.dart';
+import 'package:analyzer/dart/ast/ast.dart';
 import 'package:analyzer/dart/element/element.dart' show LibraryElement;
 import 'package:analyzer/src/dart/analysis/performance_logger.dart';
 import 'package:analyzer/src/dart/micro/resolve_file.dart';
 import 'package:analyzer/src/dartdoc/dartdoc_directive_info.dart';
+import 'package:analyzer/src/test_utilities/function_ast_visitor.dart';
 import 'package:analyzer_plugin/protocol/protocol_common.dart';
 import 'package:meta/meta.dart';
 
@@ -131,6 +134,13 @@ class CiderCompletionComputer {
       });
     }
 
+    _logger.run('Filter suggestions', () {
+      suggestions = _FilterSort(
+        _dartCompletionRequest,
+        suggestions,
+      ).perform();
+    });
+
     var result = CiderCompletionResult._(suggestions);
 
     _cache._lastResult =
@@ -200,6 +210,74 @@ class _CiderImportedLibrarySuggestions {
   _CiderImportedLibrarySuggestions(this.signature, this.suggestions);
 }
 
+class _FilterSort {
+  final DartCompletionRequestImpl _request;
+  final List<CompletionSuggestion> _suggestions;
+
+  FuzzyMatcher _matcher;
+
+  _FilterSort(this._request, this._suggestions);
+
+  List<CompletionSuggestion> perform() {
+    var pattern = _matchingPattern();
+    _matcher = FuzzyMatcher(pattern, matchStyle: MatchStyle.SYMBOL);
+
+    var scored = _suggestions
+        .map((e) => _FuzzyScoredSuggestion(e, _score(e)))
+        .where((e) => e.score > 0)
+        .toList();
+
+    scored.sort((a, b) {
+      // Prefer what the user requested by typing.
+      if (a.score > b.score) {
+        return -1;
+      } else if (a.score < b.score) {
+        return 1;
+      }
+
+      // Then prefer what is more relevant in the context.
+      if (a.suggestion.relevance != b.suggestion.relevance) {
+        return -(a.suggestion.relevance - b.suggestion.relevance);
+      }
+
+      // Other things being equal, sort by name.
+      return a.suggestion.completion.compareTo(b.suggestion.completion);
+    });
+
+    return scored.map((e) => e.suggestion).toList();
+  }
+
+  /// Return the pattern to match suggestions against, from the identifier
+  /// to the left of the caret. Return the empty string if cannot find the
+  /// identifier.
+  String _matchingPattern() {
+    SimpleIdentifier patternNode;
+    _request.target.containingNode.accept(
+      FunctionAstVisitor(simpleIdentifier: (node) {
+        if (node.end == _request.offset) {
+          patternNode = node;
+        }
+      }),
+    );
+
+    if (patternNode != null) {
+      return patternNode.name;
+    }
+
+    return '';
+  }
+
+  double _score(CompletionSuggestion e) => _matcher.score(e.completion);
+}
+
+/// [CompletionSuggestion] scored using [FuzzyMatcher].
+class _FuzzyScoredSuggestion {
+  final CompletionSuggestion suggestion;
+  final double score;
+
+  _FuzzyScoredSuggestion(this.suggestion, this.score);
+}
+
 class _LastCompletionResult {
   final String path;
   final String signature;
diff --git a/pkg/analysis_server/test/src/cider/completion_test.dart b/pkg/analysis_server/test/src/cider/completion_test.dart
@@ -156,6 +156,120 @@ var a = ^;
     _assertHasClass(text: 'String');
   }
 
+  Future<void> test_filterSort_byPattern_excludeNotMatching() async {
+    await _compute2(r'''
+var a = F^;
+''');
+
+    _assertHasClass(text: 'Future');
+    _assertNoClass(text: 'String');
+  }
+
+  Future<void> test_filterSort_byPattern_location_beforeMethod() async {
+    await _compute2(r'''
+class A {
+  F^
+  void foo() {}
+}
+''');
+
+    _assertHasClass(text: 'Future');
+    _assertNoClass(text: 'String');
+  }
+
+  Future<void> test_filterSort_byPattern_location_functionReturnType() async {
+    await _compute2(r'''
+F^ foo() {}
+''');
+
+    _assertHasClass(text: 'Future');
+    _assertNoClass(text: 'String');
+  }
+
+  Future<void> test_filterSort_byPattern_location_methodReturnType() async {
+    await _compute2(r'''
+class A {
+  F^ foo() {}
+}
+''');
+
+    _assertHasClass(text: 'Future');
+    _assertNoClass(text: 'String');
+  }
+
+  Future<void> test_filterSort_byPattern_location_parameterType() async {
+    await _compute2(r'''
+void foo(F^ a) {}
+''');
+
+    _assertHasClass(text: 'Future');
+    _assertNoClass(text: 'String');
+  }
+
+  Future<void> test_filterSort_byPattern_location_parameterType2() async {
+    await _compute2(r'''
+void foo(^a) {}
+''');
+
+    _assertHasClass(text: 'Future');
+    _assertHasClass(text: 'String');
+  }
+
+  Future<void> test_filterSort_byPattern_location_statement() async {
+    await _compute2(r'''
+main() {
+  F^
+  0;
+}
+''');
+
+    _assertHasClass(text: 'Future');
+    _assertNoClass(text: 'String');
+  }
+
+  Future<void> test_filterSort_byPattern_preferPrefix() async {
+    await _compute2(r'''
+class Foobar {}
+class Falcon {}
+var a = Fo^;
+''');
+
+    _assertOrder([
+      _assertHasClass(text: 'Foobar'),
+      _assertHasClass(text: 'Falcon'),
+    ]);
+  }
+
+  Future<void> test_filterSort_preferLocal() async {
+    await _compute2(r'''
+var a = 0;
+main() {
+  var b = 0;
+  var v = ^;
+}
+''');
+
+    _assertOrder([
+      _assertHasLocalVariable(text: 'b'),
+      _assertHasTopLevelVariable(text: 'a'),
+    ]);
+  }
+
+  Future<void> test_filterSort_sortByName() async {
+    await _compute2(r'''
+main() {
+  var a = 0;
+  var b = 0;
+  var v = ^;
+}
+''');
+
+    _assertOrder([
+      _assertHasLocalVariable(text: 'a'),
+      _assertHasLocalVariable(text: 'b'),
+    ]);
+  }
+
   void _assertComputedImportedLibraries(List<String> expected) {
     expected = expected.map(convertPath).toList();
     expect(
@@ -164,19 +278,46 @@ var a = ^;
     );
   }
 
-  void _assertHasClass({@required String text}) {
+  CompletionSuggestion _assertHasClass({@required String text}) {
     var matching = _matchingCompletions(
       text: text,
       elementKind: ElementKind.CLASS,
     );
     expect(matching, hasLength(1), reason: 'Expected exactly one completion');
+    return matching.single;
   }
 
   void _assertHasCompletion({@required String text}) {
     var matching = _matchingCompletions(text: text);
     expect(matching, hasLength(1), reason: 'Expected exactly one completion');
   }
 
+  CompletionSuggestion _assertHasLocalVariable({@required String text}) {
+    var matching = _matchingCompletions(
+      text: text,
+      elementKind: ElementKind.LOCAL_VARIABLE,
+    );
+    expect(
+      matching,
+      hasLength(1),
+      reason: 'Expected exactly one completion in $_suggestions',
+    );
+    return matching.single;
+  }
+
+  CompletionSuggestion _assertHasTopLevelVariable({@required String text}) {
+    var matching = _matchingCompletions(
+      text: text,
+      elementKind: ElementKind.TOP_LEVEL_VARIABLE,
+    );
+    expect(
+      matching,
+      hasLength(1),
+      reason: 'Expected exactly one completion in $_suggestions',
+    );
+    return matching.single;
+  }
+
   void _assertNoClass({@required String text}) {
     var matching = _matchingCompletions(
       text: text,
@@ -185,6 +326,16 @@ var a = ^;
     expect(matching, isEmpty, reason: 'Expected zero completions');
   }
 
+  void _assertOrder(List<CompletionSuggestion> suggestions) {
+    var lastIndex = -2;
+    for (var suggestion in suggestions) {
+      var index = _suggestions.indexOf(suggestion);
+      expect(index, isNonNegative, reason: '$suggestion');
+      expect(index, greaterThan(lastIndex), reason: '$suggestion');
+      lastIndex = index;
+    }
+  }
+
   Future _compute2(String content) async {
     var context = _updateFile(content);
 
@@ -227,15 +378,16 @@ var a = ^;
   }
 
   _CompletionContext _updateFile(String content) {
-    newFile(testPath, content: content);
-
     var offset = content.indexOf('^');
     expect(offset, isPositive, reason: 'Expected to find ^');
     expect(content.indexOf('^', offset + 1), -1, reason: 'Expected only one ^');
 
     var lineInfo = LineInfo.fromContent(content);
     var location = lineInfo.getLocation(offset);
 
+    content = content.substring(0, offset) + content.substring(offset + 1);
+    newFile(testPath, content: content);
+
     return _CompletionContext(
       content,
       offset,
