Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Code indexing: How language servers understand ...

Code indexing: How language servers understand our code

Language servers are a way of providing IDE features to any editor. Specialized functionality for navigating and understanding our Ruby code can greatly improve the developer experience and is highly aligned with the goal of making the developer happy.

In the context of the Ruby LSP, let’s dive into how language servers can build up knowledge about codebases using indexing and how it is used to implement features such as go to definition.

Vinicius Stock

May 31, 2023
Tweet

More Decks by Vinicius Stock

Other Decks in Programming

Transcript

  1. Vinicius Stock Senior dev @ Ruby DX team Shopify Twitter:

    @vinistock GitHub: @vinistock https://vinistock.com
  2. Semantic highlighting Document symbol Document link Hover Folding range Selection

    range Formatting On type formatting Diagnostic Code actions Document highlight Inlay hints Path completion Code Lens
  3. Semantic highlighting Document symbol Document link Hover Folding range Selection

    range Formatting On type formatting Diagnostic Code actions Document highlight Inlay hints Path completion Code Lens
  4. Semantic highlighting Document symbol Document link Hover Folding range Selection

    range Formatting On type formatting Diagnostic Code actions Document highlight Inlay hints Path completion Code Lens
  5. { "params": { "textDocument": { "uri": "file: / / /

    foo.rb" }, "position": { "line": 2, "character": 5 } } }
  6. { "uri": "file: / / / bar.rb" "range": { "start":

    { "line": 0, "character": 0 } "end": { "line": 5, "character": 2 } } }
  7. class Foo def process Bar.baz end end How do we

    determine what’s under the cursor? How do we find the definition?
  8. We want to search an AST to find the node

    at the requested position
  9. 0 class Foo 1 def process 2 Bar.baz 3 end

    4 end CLASS CONST (Foo) BODY DEF IDENT (process) BODY CALL CONST (Bar) IDENT (baz)
  10. "position": { "line": 2,"character": 5 } source = "class Foo\n

    def process\n Bar.baz…" line + character = > string index
  11. "position": { "line": 2,"character": 5 } source = "class Foo\n

    def process\n Bar.baz…" line + character = > string index { "line": 2,"character": 5 } = > 28
  12. 1. Go through AST 2. Use target and candidate pointers

    3. Compare proximity to requested index
  13. 0 class Foo 1 def process 2 Bar.baz 3 end

    4 end CLASS CONST (Foo) BODY DEF IDENT (process) BODY CALL CONST (Bar) IDENT (baz)
  14. until queue.empty? # … break if index < loc.start_char tloc

    = target.location if loc.end_char - loc.start_char < = tloc.end_char - tloc.start_char target = candidate end end
  15. class IndexVisitor < SyntaxTree : : Visitor attr_reader :constants def

    initialize @constants = [] end def visit_class(node) @constants < < node super end end
  16. visitor = IndexVisitor.new visitor.visit(ast) visitor.constants # = > [ #

    #<ClassDeclaration …>, # #<ClassDeclaration …> # ]
  17. class Index include Singleton def initialize @knowledge = {} end

    def add(path, constants) constants.each do |const| end end end
  18. class Index include Singleton def initialize @knowledge = {} end

    def add(path, constants) constants.each do |const| @knowledge[const.name] = { } end end end
  19. class Index include Singleton def initialize @knowledge = {} end

    def add(path, constants) constants.each do |const| @knowledge[const.name] = { file: path, location: const.location } end end end
  20. { "Foo" = > { path: "/foo.rb", location: #<Location start_line=1,

    end_line=2, start_column=4, end_column=6, > } }
  21. class Index def process(uri) path = URI(uri).path content = File.read(path)

    ast = SyntaxTree.parse(content) visitor = IndexVisitor.new visitor.visit(ast) end end
  22. class Index def process(uri) path = URI(uri).path content = File.read(path)

    ast = SyntaxTree.parse(content) visitor = IndexVisitor.new visitor.visit(ast) add(path, visitor.constants) end end
  23. Remove related entries Index the new file Ruby file modified

    Deleted Added Remove and index Changed
  24. class Index def synchronize(changes) changes.each do |change| case change[:type] when

    "deleted" remove_entries_for(change[:uri]) end end end end
  25. class Index def synchronize(changes) changes.each do |change| case change[:type] when

    "deleted" remove_entries_for(change[:uri]) when "created" process(change[:uri]) end end end end
  26. class Index def synchronize(changes) changes.each do |change| case change[:type] when

    "deleted" remove_entries_for(change[:uri]) when "created" process(change[:uri]) when "changed" remove_entries_for(change[:uri]) process(change[:uri]) end end end end
  27. class Index def remove_entries_for(uri) path = URI(uri).path @knowledge.each do |const,

    loc| if loc[:file] = = path @knowledge.delete(const) end end end end
  28. class Definition < BaseRequest def run target = @document.locate_node(@position) file,

    location = case target when SyntaxTree : : Const Index.instance.fetch(target.value) end # … end end
  29. class Definition < BaseRequest def run # … { uri:

    "file : / / # { file}" range: { start: { line: location.start_line, character: location.start_column }, end: { line: location.end_line, character: location.end_column } } } end end
  30. • Use parallelism to build index • Cache the index

    • Include the missing parts (modules, constants, methods…) • Add the option to control what is indexed
  31. > lib > my_gem foo.rb > .ruby-lsp > lib >

    my_gem foo.indexed Last modified: 3 days ago Last modified: 1 minute ago