Code indexing: How language servers understand our code

00:00:02.840 Thank you.

00:00:06.540 Hello, everybody, and welcome to Code Indexing: How Language Servers Understand Our Code. My name is Vinicius Stock, or Vinnie for short. I'm part of the Ruby Developer Experience team at Shopify. We work on different aspects of the developer experience for Ruby. For example, you might have watched Emily's or Alex's talk about gradual typing, which we are involved with. You may have also seen Stan's talk yesterday about building a debugger; we contribute to Ruby Debug.

00:00:20.699 In this talk, I want to tell you about the Ruby Language Server Protocol (LSP), another tool that our team is working on. If you want to know a little bit more about my work, you can find me at @vinistock on Twitter and GitHub.

00:00:43.079 To start off, what is a language server? As the specification describes, a language server is a background process that runs on the developer's machine to provide features for any editor for a particular programming language. It does so using static analysis, so it doesn't have access to the runtime of the language.

00:00:55.500 The idea is that the editor, acting as the client, spawns the language server process and keeps handles for standard input and standard output to communicate with the language server using JSON. For example, if a user is interacting with the editor and requests to go to the definition of something, the editor translates that action into a JSON request; in this case, a definition request.

00:01:06.960 The language server is then responsible for fulfilling that request by finding where the definition exists, returning it as a JSON response to the editor, and finally, the editor uses that response to perform the action that was requested—jumping to the definition location. All interactions between the editor and language servers are structured like this: the user takes an action, the editor translates it into a JSON request, and then the language server fulfills the request.

00:01:21.659 Since they use JSON to communicate, a language server can connect to any editor as long as the editor supports the Language Server Protocol. This, in my opinion, has a major advantage—it allows us to collaborate in improving the developer experience for everyone, regardless of which editor you use. So, if someone using Visual Studio Code adds a new feature, it's not only going to be for VS Code; everyone will benefit from it.

00:01:42.120 I'm afraid I won't have enough time to delve into the fundamentals of language servers and why they were created in this talk. However, if you're interested in learning more, I invite you to check out my talk from the last edition of RubyConf, where I explained some of that in more detail.

00:02:01.620 The Ruby LSP is an implementation of the Language Server Protocol for Ruby. Here on the slide, we have two different repositories. The first one is the VS Code extension for the Ruby LSP, and the second one is the language server gem. I want to stress that the server can connect to any editor that supports the protocol; it's not only specific to Visual Studio Code, and the server is built with 100% pure Ruby—it doesn't use any other languages. So, if you want to check out that repository on GitHub, you can follow along with some of the examples that we're going to see in this talk.

00:02:24.900 These are the features currently supported in the Ruby LSP. I won't show every one of them but let me give you a few examples. We support document symbol, which allows you to fuzzy search declarations inside the current file and also populates the outline tab on the left. We have integrations with RuboCop to display violations in the editor using diagnostics. You can also fix the violations using quick actions, also known as quick fixes, which is a code action. You can fix all of them at once with format on save.

00:02:59.880 In another use of code actions, we have the extract variable refactor, so if you select any piece of code and instruct the Ruby LSP to extract it to a variable, it will do it for you. The last feature I want to highlight as an example is code lenses for tests. We have code lenses for running tests, which are integrated with the Test Controller in VS Code, so they reflect the results in the testing panel. We also have a debug code lens that launches Ruby Debug interactively in the editor.

00:03:29.760 But to explore code indexing, we're going to discuss another feature that's not on the list: going to definition. Going to definition is not the only feature that requires indexing the code base, but it serves as a good example of why we need to do so. Let's consider this Foo class and assess that the user is requesting to go to the definition of the constant 'bar' exactly at that character in 'bar'. When that happens, the editor sends the language server a request that looks something like this: it retrieves the URI of the text document—the file path (foo.rb)—and obtains the position where the user clicked. In this case, line two, character five, corresponds to the 'a' character in 'bar'.

00:03:43.800 The editor expects a response indicating another location—the location of the definition declaration. This includes the URI of the file because the declaration may be in a different file, such as bar.rb, and the range where the declaration exists in that file. For instance, from line 0 to 4 in this case. Both the request and the response for going to the definition are simple requests for locations. Thus, we need to figure out what happens in between: how do we transition from the position where the user clicked to the declaration location?

00:04:03.600 There are two main problems we need to solve before we can implement go to definition. First, consider the request we receive from the editor: we only know the position where the user clicked, but we don't know if they clicked on a method call, a variable, or a constant. So, the first part of the problem is figuring out what's under the cursor—what is the target of going to the definition? After we determine that the user is trying to go to the definition of a constant named 'bar', the second part of the problem arises: where is 'bar' defined?

00:04:21.480 That's where code indexing comes into play, but we'll start with part one: locating targets. Our approach is to search the AST of the current file, where the user clicked, to discover which node exists at the clicked position. Essentially, the language server must have the AST of the file. We must have already parsed the file, and we'll search the nodes to find which one exists under the cursor.

00:04:36.960 I'd like to draw your attention to something first: here we have our Foo class on the left alongside a simplified AST that we would obtain from parsing this Foo class. When we're searching for the relevant node that exists under the requested position, it's not sufficient to merely check whether the node's location covers the requested position, as more than one node may cover it. For instance, if we review the class node, covering lines 0 to 4, it fully encompasses line number two—the 'a' character in 'bar'. The method definition for process also spans from line 1 to 3, thus covering the 'a' character in 'bar' as well.

00:05:03.000 Finally, the actual target—the constant 'bar'—also covers the requested location, but in a much more specific manner. So, several nodes may encompass the requested position, but what we seek is the most specific node in the AST that still covers the user's requested position. The first step is converting the position we receive from the editor into a string index. We need to do this because while the editor sends us line and character information, the language server maintains only our Ruby code in a string format. Hence, we need to determine where line number two and character five corresponds to in the string.

00:05:22.139 I won't delve into the details of how to perform this algorithm, as that's outside the scope of this discussion. The general idea involves going through the string, counting the line breaks until we reach the right line, and then adding the number of characters to that count. Once we have the string index, we'll identify which node exists at that specific index. We'll accomplish this by analyzing all the nodes in our AST to locate the correct target.

00:05:55.860 We establish two pointers: the target, in red, and the candidate, which is the node we're currently evaluating, in blue. We'll compare the proximity of these nodes to the user-requested index to ascertain which is the more specific target. To visualize this algorithm within our full class, we start with the target being the first node in the tree, the class node, and then we begin comparing it against all other nodes, the candidates represented in blue.

00:06:08.700 For instance, the constant 'Foo' does not encompass the 'a' character in 'bar', so it cannot be the correct target for our go-to definition. We move on to compare with the class body, which covers the 'a' character and is thus more specific than simply the class node. Therefore, we update our target to be the class body.

00:06:31.620 Next, we compare it with the method definition for 'process', which also contains the 'a' character, therefore it also becomes the new target. However, we must check the name of the method—the identifier 'process'—which does not encompass anything on line two, so that can't be the correct target. Following that, we evaluate the body of the method, which does cover the requested position and is more specific than the method definition; hence we update the target again.

00:06:51.960 We repeat this process for the method call 'bar.baz', which likewise covers and is more specific. Finally, we examine the constant 'bar', which while covering, is more specific than 'bar.baz'. Thus, we update the target once more. Finally, we check the identifier of the method 'baz' to see if it encompasses the 'a' character in 'bar'. It does not, which leads us to conclude that 'bar' is indeed the right target for go to definition.

00:07:17.460 In code, we can implement this as a locate method that takes the initial node we're searching within and the index requested by the user during the action. We start by creating a queue of nodes with the child nodes of the initial node in the AST provided, and we designate the target as the first node.

00:07:43.860 Then, until the queue is empty, meaning we have checked all the nodes in the AST, we make comparisons and return the identified target at the end of the loop. Delving into the loop for each iteration means popping the first node from our queue to be the candidate—the blue pointer. We then push the candidate's child nodes into the queue for thorough traversal of all the nodes and avoid missing any.

00:08:02.760 Next, we begin comparisons. If the location of the candidate does not cover the user-requested index, that candidate cannot possibly be the correct target as it’s not under the right position. If the candidate’s start location has surpassed the user index, this means we should have already identified the right target by now, so we should break the loop and return what we have stored in target.

00:08:21.260 If neither of these scenarios holds true, we proceed to check if the candidate is more specific than the target. Since we know the candidate encompasses the expected position, we need to determine if it's a more accurate target than what we've previously established. We'll do that by evaluating the range of characters in the source code: if the range is shorter, we deem the candidate to be more specific and update the target accordingly. We repeat this process until we ascertain which is the correct target.

00:08:55.920 This allows us to search for a target based on the string index in any AST we possess. Now that we have identified which one is the target, we arrive at the second part: determining where the definition is located. This is where code indexing comes into play. To jump to the correct definition of 'bar', we must know everything available in the code base as 'bar' may not be defined within the same file where the go-to definition request was made.

00:09:07.580 In fact, it might not even be defined in your project; it could be sourced from a gem. Thus, we need a complete index object that knows about all the classes, methods, modules available in your workspace, allowing us to query the index to see if the sought-after item exists—and if so, where it is defined.

00:09:25.920 However, we can't populate the index with every definition request; that would be excessively slow and unmanageable. Instead, we want to initialize the index when we activate the language server and ensure we synchronize any file modifications so that the index is always up-to-date with the current information in the code base. We'll examine the two components of indexing, but we’ll start with initial indexing at boot and focus only on classes for the sake of brevity.

00:09:48.020 For initial indexing, we want to read the contents of all Ruby files available in the load path, parse them into an AST, and then use a visitor to extract all class declarations found within that AST. Finally, we will feed that class data to our index, which will maintain the necessary information for us to access during a go-to definition request.

00:10:15.780 The first step will involve implementing the visitor—this component will extract class declarations from any specific AST. For that, we'll utilize the syntax tree library. SyntaxTree is the gem that forms the basis for the Ruby LSP. If you haven't used it, it's a gem with mini parsing and AST utilities specifically designed for Ruby.

00:10:33.480 One feature of this gem is the visitor implementation, allowing you to inherit from SyntaxTree::Visitor to gain all the visiting functionality automatically, while you simply need to define custom logic for the nodes you’re interested in. For our scenario, we'll focus on class definitions; thus, we can initialize this visitor with an empty list of constants where we will accumulate our classes.

00:10:51.240 Each time we encounter a class within the visitor, we'll simply push it into our list of constants. Although this is a straightforward visitor implementation, it will already be capable of extracting any class declarations found within an AST.

00:11:07.200 Afterward, we need a way to store these declarations, which leads us to the implementation of our index. The goal here is to create a singleton object that maintains a knowledge hash to store all of those classes. The add method will take a file path and all of the constants we discover within that file, ensuring we insert that information in the hash in a more convenient format.

00:11:25.420 So whether we consider the constant name as the key, or the associated value as the file where the constant was defined and its location within that file, our knowledge hash might look like this: for example, 'foo' as the key (the name of the class), the path where we discovered it (foo.rb), and the location inside that file for the declaration.

00:11:43.660 With a method in place to extract class declarations and a storage mechanism established, we can conduct the initial indexing of the code base. Our intention is to traverse all files in the load path and process them using our index. One detail worth mentioning is that we'll construct URIs rather than simply relying on file paths, as this will have relevance later on.

00:12:04.560 We will then implement the process function that extracts the file path from the URI, reads the file's contents, parses them into an AST, uses the visitor to extract all of the class declarations from that AST, and finally invokes our add method to push everything into the knowledge object’s hash for easy access during reindexed requests.

00:12:23.040 Now that we've established a method to perform initial indexing, we need to synchronously handle file modification after initializing the index. We need to manage these modifications because if a file undergoes changes, the classes that exist within the application may have been affected. For instance, deleting a file would remove everything defined within it while modifications could either delete classes or possibly introduce new ones.

00:12:56.240 Fortunately, we don’t have to implement file watching ourselves. Language servers can request the editor to monitor files, so anytime a file has been altered, it will notify the language server. Hence, for every Ruby file modification, we need to trigger an action according to the type of modification that occurred.

00:13:15.920 If the file has been deleted, we want to remove related entries from the index for the specific file path. If a new file is added, that might contain new classes we need to recognize, so we must index that newly added file. For any existing file that’s modified, we cannot ascertain if classes have been deleted or added, so we must update the information within the index.

00:13:42.000 In this scenario, we remove stale information first and then proceed to re-index the file to capture the latest changes. One method to handle this notification could involve using a case statement with a notification titled 'workspace did change watched files'. Every time we receive this notification, we communicate with the index to synchronize the changes.

00:14:01.780 Within this function, changes parameter reflects an array of file modifications including the type of modification and the file URI. For our synchronize implementation, we would iterate through each file change, executing actions depending on the type of modification reported. If a file was deleted, we would remove the corresponding entries from our index for that file URI.

00:14:18.560 If the file was added, we could leverage our process implementation to index the new file. Handling modifications means performing dual tasks—removing stale data first and then re-indexing to obtain the most up-to-date information in the index.

00:14:36.960 One alternative approach would involve going through the knowledge hash and removing all constants that correspond with the URI of the removed files. This method allows us to carry out both the initial indexing when we launch the language server and synchronize it when the user alters files.

00:14:54.600 At this point, we're finally ready to implement go to definition, leveraging what we've constructed in the previous two parts. The procedure entails locating the target based on the position relayed from the editor. We then find the target in the index to determine where the corresponding declaration exists, after which we relay that information back to the editor.

00:15:15.360 Implementing the go-to-definition request involves initializing it with the current document where the user clicked and the position where the go to definition action occurred. Executing this request will utilize our previously established algorithm from part one to identify the correct target.

00:15:39.660 In scenarios where the target is a constant, we might check if it's among the indexed classes. Thus, we can refer to our index and obtain the file path and the information regarding the declaration's location. The last step is returning the expected response we noted earlier—a hash containing the URI of the file where the declaration resides and the precise location of that declaration within the file.

00:15:56.220 Thus, we’ve completed our go to definition implementation. The principal issues we needed to resolve were locating the targets and managing the indexes, both of which present considerable complexity. However, following solutions to these two challenges, the process of implementing the request becomes quite straightforward.

00:16:14.340 Currently, this functionality is not yet released in the Ruby LSP. Unfortunately, most of the prototype work you've seen has been conference-driven development for the sake of this presentation. However, I do have a demo to illustrate that the prototype works. Here you can see the Ruby LSP navigating through classes in the Ruby Debug project.

00:16:28.440 First, we jump to the LineTracer class and then transition to the parent class, Tracer. Thank you!

00:17:08.960 As I mentioned, go to definition is not the only feature that necessitates indexing the code base.

00:17:12.960 I have a few other examples using screenshots from TypeScript to illustrate other functionalities that rely on code indexing. For instance, signature help showcases the signature and documentation for a method you're currently invoking, meaning it necessitates knowledge of the method signatures to provide this feature.

00:17:40.520 Workspace symbols resemble document symbols but are scoped for the entire workspace, allowing you to fuzzy search any declaration, including those in dependencies. Consequently, it necessitates knowledge of everything available within the project.

00:17:54.520 Furthermore, hover functionalities displaying documentation signatures or even types on hover also require an index to correlate each piece of documentation with respective methods and classes.

00:18:07.540 Even autocomplete requires awareness of the available methods, constants, and classes in your project to deliver suggestions effectively. The approach is remarkably akin to that used by type checkers.

00:18:26.260 Type checkers need to index the entire code base to identify method definitions accurately or to flag possible mistakes. The key difference lies in the fact that a type checker likely wouldn't access the index solely based on the string names of constants or methods, but would first execute type checking before potentially utilizing an entity representation to consult the index.

00:18:43.420 Nonetheless, the code indexing process remains quite similar in both cases. Even in this implementation, devoid of type checking, numerous enhancements can still be undertaken. For instance, we haven't implemented support for everything; our current support is limited to class indexing. We could expand this to encompass modules and methods as well.

00:19:03.840 Constructing the index is notably resource-intensive and slow; therefore, we can aim to improve the indexing process by building it in parallel. In our explorations on the Shopify core monolith, we discovered that the initial implementation required over five minutes to index everything, indicating significant potential for improvement.

00:19:24.320 To further enhance performance, we can cache the index so that repeated builds from scratch are unnecessary. This way, each time the user opens the editor, they aren't burdened by the cost of re-indexing all files.

00:19:45.440 Instead, we maintain a cache and only reboot the indexing for files altered since the last session. Additionally, providing users options to determine which paths in their applications will be indexed can greatly enhance efficiency.

00:20:07.240 For example, if there is a gem that lacks relevance for going to definitions—such as a linter or a formatter—then those classes may not need indexing in your project. This exclusion would expedite the initial indexing for all users.

00:20:27.560 One potential implementation for the index cache could mimic the project structure, perhaps under a .ruby-lsp folder, maintaining versions of each indexed file. Upon startup, we can review all cached files, and if their last modified timestamp doesn't align, then the information contained within those indexed files is outdated, and we would need to re-index them.

00:20:49.840 This could be developed as a separate gem—not necessarily needing complete integration within the Ruby LSP. There are various other gems that could potentially benefit from index implementations; type prof and steep both serve as type checkers, necessitating the indexing of the code base to deliver their functionalities.

00:21:11.200 While IRB doesn’t currently utilize an index, it could certainly see improvements in autocomplete results with one. Meanwhile, rdoc employs a form of indexing to establish correlations between documentation and each method or class. Therefore, all these gems might benefit from a shared index implementation, and there are likely more examples beyond those I’ve outlined.

00:21:27.800 I hope you will give the Ruby LSP a try. Our team is making a concerted effort to modernize developer tooling for Ruby, as we firmly believe that enriching developer experience is crucial in ensuring developer satisfaction.

00:21:48.440 I hope you’ll join us in our collaboration to enhance the developer experience for everyone. Thank you.