[#1651] Implement completion

Motivation and Context

For feature parity with the old language server, we'd like to support textDocument/completion in the new language server.

Related issues

Resolves #1651 (closed).

✅ Checklist for the LIGO Language Server

• I checked whether I need to update the README.md file for the plugin and did so if necessary:
  • If I implemented a new LSP request, I added it to the list of supported features that may be disabled
  • If I implemented a new LSP method, I added it to the list of supported functionality
• I checked that my changes work in Emacs, Vim, and Visual Studio Code
• (Before merging) The commit history is squashed and prettified, and follows the Serokell commit policy, or the MR is set to squash the commits

Description

Adds support for textDocument/completion in the language server. Besides what's described in the changelog, I also added a stub for supporting file completions (when we will be able to provide a list of LIGO files) as well as a stub for type-aware completion.

• Scope completion simply uses the scope available from get-scope.
• Keywords and operators use the information available from the front-end.
• File completion uses a regex hack which I hope we'll be able to improve in the future, but for now it's disabled regardless.
• Field completions traverse the CST and use the information available from scopes to provide what's available given the inferred types.

The algorithm for field completions deserves some explanation:

We want to know which dot (.) appears before the cursor and is at the same time the closest to it. While traversing the tree, we calculate the distance from every dot we find to the given Position.t in order to find it, keeping the one that has the smallest distance. For record fields, which are not available from scopes, we then calculate which fields appear before this dot and recursively resolve the field path by looking up the struct name, listing its fields, and continuing until there are no more fields. For module fields, we simply look up the module in the scope and display its definitions provided they are tagged as module fields by scopes.

In addition, we also run the same algorithm for calculating the last lexeme that appears before the cursor, and take that a node is of interest if, and only if, both the dot and the lexeme are contained within this node's region.

There is a simple system for displaying the most likely suggestions first to the user based on the context, it's better described in the code comments.

Finally, there are three changes in the scopes:

• Module aliases now remember which module they are aliased to.
• Definitions now remember in which module they were defined.
• We now try to figure out what is the type of some declaration (local variable, global variable, module field, function parameter).

The first one allows us to support completion from module aliases, and the second one allows us to suggest the proper module path to insert when prefixing some name.

JsLIGO projections and module paths are different from CameLIGO's and PascaLIGO's (these two are the same), so there is first a "linearization" pass which transforms fields (assuming they are in the form _._._._ where each wildcard is a name) in order for the algorithm to work. In the future, we should handle it better using the typed AST.

Component

• compiler
• website
• webide
• vscode-plugin
• debugger

Types of changes

• Bug fix (non-breaking change which fixes an issue)
• New feature (non-breaking change which adds functionality)
• Breaking change (fix or feature that would cause existing functionality to not work as expected)
• Performance improvement (non-breaking change that improves performance)
• None (change with no changelog)

Changelog

Added support for completion in the LIGO Language Server. Supported completions include:

• Variable, module, and type names.
• Record fields.
• Module fields.
• Keywords and operators.

Checklist:

• Changes follow the existing coding style (use dune @fmt to check).
• Tests for the changes have been added (for bug fixes / feature).
• Documentation has been updated.
• Changelog description has been added (if appropriate).
• Start titles under ## Changelog section with #### (if appropriate).
• There is no image or uploaded file in changelog
• Examples in changed behaviour have been added to the changelog (for breaking change / feature).