Building a Development Environment for Monkey: Part 2 - An LSP for Hover, Definition, Completion and Diagnostics

Intro

In the previous blog, the first entry of the series, we taught editors what Monkey looks like by adding syntax highlighting to Neovim using Tree-sitter. Syntax highlighting makes our source-code pretty but it only goes so far.

The next planned step in building the development environment is teaching editors what Monkey means, by introducing diagnostics, hover, go-to-definition and completion. That layer is the LSP.

This blog covers the actual steps I took to build an extremely basic but extremely helpful version. It includes the walls I hit and how I had to go and extend the already existing interpreter to help me implement LSP features.

You can find the full docs for Monkey and full LSP implementation in the Monkey repository.

---

What the LSP actually is (and what we're building)

Language Server is a server that provides language-specific functions that can communicate with development tooling, for example editors, over a protocol that enables inter-process communication. LSP (Language Server Protocol) on the other hand standardizes the way editors communicate with Language Servers.

Thanks to this protocol, we know exactly what editors send to Language Servers and the responses they expect to receive back.

The messages the editor and server exchange looks like the following.

Content-Length: ...\r\n
\r\n
{
    "jsonrpc": "2.0",
    "id": 1,
    "method": "textDocument/completion",
    "params": {
        ...
    }
}

All messages have two parts, separated by the \r\n separator:

1. Headers: consists header fields separated by \r\n. Currently Content-Length and Content-Type headers are supported.
2. Content: is the main body of the message which is just json, specifically JSON-RPC 2.0.

The messages that the Language Server receives from the editors can be of two types: request and notification. We can pick and choose what to handle and what to ignore. Some of them are absolutely necessary to handle.

But before we talk about the specifics of the messages, let's actually read them first. That is handled by the rpc package.

---

Step 1 - The RPC layer

The RPC layer deals with reading and writing LSP messages from and to the LS clients, often editors. The LSP communication mostly happens using the stdin and stdout files, but not limited to it.

Because of this, we will abstract functions using io.Reader and io.Writer interfaces from the standard lib. This will be very handy when it comes to unit testing as well. This practice is mentioned in 100 Go Mistakes and How to Avoid Them book under mistake #46, "Using a filename as a function input".

The writer half of it is pretty simple:

1. accept an argument of content which is a byte array (presumably JSON)
2. frame it with the header section of the message that includes Content-Length (the length of the byte array argument)
3. write the whole message to our writer interface

When it comes to reading, we can't just do json.Decode(io.Reader), an LSP message is not just JSON. It's framed as follows:

Content-Length: 42\r\n
\r\n
<42 bytes of JSON>

First attempt: bufio.Scanner with a custom SplitFunc

Following Learn By Building: Language Server Protocol, the first attempt uses bufio.Scanner and SplitFunc to neatly read each of our messages from the input as tokens.

scanner := bufio.NewScanner(os.Stdin)
scanner.Split(Split)

// type SplitFunc func(data []byte, atEOF bool) (advance int, token []byte, err error)
func Split(data []byte, _ bool) (advance int, token []byte, err error) {
    header, content, found := bytes.Cut(data, []byte{'\r', '\n', '\r', '\n'})
    if !found { return 0, nil, nil }

    // Content-Length: <number>
    contentLengthBytes := header[len("Content-Length: "):]
    contentLength, err := strconv.Atoi(string(contentLengthBytes))
    if err != nil { return 0, nil, err }

    if len(content) < contentLength {
        return 0, nil, nil
    }

    totalLength := len(header) + 4 + contentLength
    return totalLength, data[:totalLength], nil
}

This implementation reads the input until a full message has arrived, which is decided by the Split function, which advances depending on if the full message has been received.

This worked fine - until it didn't.

The problem

bufio.Scanner has a default token size limit of 64 KiB. Since an entire LSP message is one "token" under our SplitFunc, a large message (say, a big didOpen with a huge file) would blow up with:

bufio.Scanner: token too long

This shortcoming is mentioned in go doc bufio.scanner as follows, it even suggests a solution.

Scanning stops unrecoverably at EOF, the first I/O error, or a token too large to fit in the Scanner.Buffer. When a scan stops, the reader may have advanced arbitrarily far past the last token. Programs that need more control over error handling or large tokens, or must run sequential scans on a reader, should use bufio.Reader instead.

It is possible to change the token size limit and the initial buffer size that are set by default.

scanner := bufio.NewScanner(io.Reader)
scanner.Buffer(
    make([]byte, 64*1024), // initial buffer
    1024*1024,             // maximum token size: 1 MiB
)

The problem with this approach is that we're just pulling those numbers out of nowhere. Let's move on to the solution suggested in the Go docs.

The solution: bufio.Reader + io.ReadFull

This solution allows us to first read the headers line by line using bufio.Reader, which in-turn allows us to handle errors at a more granular level. After reading all the headers, we parse out our Content-Length, then allocate a buffer with size that number and use io.ReadFull to read the content part of the message until the buffer is full or an error occurs, then we return the content that we just read.

The following is the implementation.
rpc/reader.go

type Reader struct {
    rd *bufio.Reader
}

func NewReader(reader io.Reader) *Reader {
    return &Reader{
        rd: bufio.NewReader(reader),
    }
}

func (r *Reader) ReadMessage() ([]byte, error) {
    contentLength, err := r.readHeaders()
    if err != nil {
        return nil, err
    }

    content := make([]byte, contentLength)
    _, err = io.ReadFull(r.rd, content)
    if err != nil {
        if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
            return nil, ErrIncompleteMessage
        }
        return nil, err
    }
    return content, nil
}

func (r *Reader) readHeaders() (int, error) {
    // Omitted for brevity, this function reads from the input line-by-line with '\n' as the delimiter, handling reading all the headers and handling errors in a more granular way, check source.
}

The folks at Microsoft implemented their own version in typescript-go in a very similar way to this.

We now have a way of reading and writing LSP messages, but we don't exactly know what they look like, when we receive them, when or what we should respond with.

---

Step 2 - Protocol types (the boring part) and handlers

The next work is basically converting Typescript types specified in the LSP spec into Go structs in the protocol package. LSP is a big spec, so we will only include the minimum required types to achieve our goals.

Go's type system

One of the more frustrating parts of implementing LSP in Go is that the language's type system doesn't always map neatly onto the shape of the specification. LSP makes extensive use of inheritance-like relationships, optional fields, and union types using TypeScript, while Go has no direct equivalent of TypeScript's extends or tagged unions. Embedding and interfaces can approximate some of these relationships, but they don't always express the same structure.

For example, my base request type contains only the fields common to every request:

type Request struct {
    Message
    ID     int64  `json:"id"`
    Method string `json:"method"`
}

type HoverRequest struct {
    Request
    Params HoverParams `json:"params"`
}

The problem is that Request isn't really a complete LSP request on its own; its params depend on which concrete request it represents. It doesn't even signal that there should be one more field named params. In TypeScript, this relationship can be modeled more naturally through interfaces and extension. In Go, it becomes a collection of concrete types built around an incomplete base type, with the connection between them handled by the implementation.

Lifecycle message Initialize and server capabilities

We start by defining Request Message, Response Message and Notification Message types as structs. These comprise all types of messages exchanged between the client and the server, every other types extend these.

The lifecycle messages, as mentioned in the spec, begin with a request of method Initialize sent from the client to the server.

This is the very first message that we expect to receive and it includes a capabilities field which includes details of if and how the client supports features such as hover, completion etc. We are expected to return a response including the server information and also the InitializeResult type, which includes its very own capabilities, i.e capabilities the server supports or implements. In our case we return the following:

{
    "result": {
        "capabilities": {
            "textDocumentSync": 1,
            "hoverProvider": true,
            "definitionProvider": true,
            "completionProvider": {}
        },
        "serverInfo": {
            "name": "monkey-lsp",
            "version": "0.0.1"
        }
    }
}

With our response, we tell our client that we support the following:

1. Document sync of type 1 (full document sync). This means that the client will send the full text document each time there's a change. Type 1 may seem inefficient compared to type 2 (incremental document sync) but let's save that more complicated task for future me.
2. Hover provider: true, this tells the client that we can handle a hover request.
3. Definition provider: true, to tell the client that we can handle a definition request.
4. Completion provider is set to an empty object because it has some optional configurations that we could set inside, which we won't bother with for now.
5. Server info includes the name and the version of our Language Server.

Note: The client doesn't ask the server for something that the server has not specified in its capabilities. So, the client won't bombard our server with all types of requests.

The rest is mechanical translation. We now know the requests that we can expect from the client thanks to the server capabilities so we can define the request and response Go types for them by referring to the LSP spec. All the types are specified in the protocol package.

Handling Requests and Notifications

Our server uses the rpc package to first read the received message. It then figures out if the message is of a request or notification type depending if the message includes an ID, only requests include IDs. Then call their respective handlers depending on the method by passing content (and the ID in case of requests) to them. These handlers use the Go structs we defined above to read the incoming content of the message, do some work and then return a response using the proper LSP types.

We can now make sense of the shapes of the data we receive and send. We are now done with the building blocks and we can move on to what to do with those nicely structured messages we receive in the following steps.

---

Step 3 - State, Documents, and Diagnostics

Before we can do anything with the document open in the editor, we need to know about its current state on the server. We do this in the analysis package.

Document sync

Our server needs a way of knowing about the state of the current text document content in the editor. For this very reason, we have 3 helpful notifications for document synchronization in the spec.

• DidOpen is sent from client to server to signal a newly opened text document. It includes the following relevant fields to us: uri, version and text.
• DidChange is sent from the client to the server to signal changes to a text document. It includes the following fields: textDocument (identifier) and contentChanges.
• DidClose is sent from the client to the server when the document gets closed in the client. It will only include textDocument (identifier).

We will store the state of the opened text document in our editor buffers using the following structures.

package analysis

type Document struct {
    Version int
    URI     string
    Content string

    AST     *ast.Program
    parser  *parser.Parser
}

type State struct {
    // key is URI of the text document
    Documents map[string]*Document
}

Document represents an opened text document with the information we receive in the DidOpen notification. It also includes AST and parser field imported from our interpreter used to parse the Content. The server will have a single State object and is able store and process multiple open documents.

The server updates it's state whenever it receives the three document sync notifications listed above.

• DidOpen and DidChange either create a new document or update an existing one identified by its uri.
• DidClose deletes a document from the server state using the given uri.

Diagnostics

The DidOpen and DidChange notifications are good set of events on when to send some diagnostics back to the client, they could be errors, warnings, information etc. The server can publish a diagnostics notification to the client (see spec).

Diagnostics notification the client expects has the following shape:

type PublishDiagnosticsParams struct {
    URI         string       `json:"uri"`
    Version     int          `json:"version"`
    Diagnostics []Diagnostic `json:"diagnostics"`
}

type Diagnostic struct {
    Range    Range  `json:"range"`    // has `start` & `end` Position: {Line, Character} fields
    Severity int    `json:"severity"` // 0-4 (Error, Warning, Information, Hint)
    Source   string `json:"source"`
    Message  string `json:"message"`
}

Our original interpreter's parser is already capable of reporting syntax errors as strings as it parses our source-code. But as we have seen above, diagnostics are more encompassing than errors with more information than just a message.

There's another problem though, diagnostics requires Range which is used by the editor to show exactly where in the source code a specific diagnostic message applies by usually underlining the specified range with different colors depending on the severity, red for errors and yellow for warnings, for example.

The Monkey parser reports errors faced in the parsing process as it's dealing with tokens, if the token is unexpected or incorrect, it adds an error to a list. It would be helpful to know the range of this problematic token for our LSP diagnostics implementation, but we have no way of knowing in our current implementation.

Extending Monkey tokens

As the original interpreter is limited, we need to add starting and ending positions to all Monkey tokens. We also need a way to store diagnostics that includes the message, range and severity.

The idea is to track and update where the current position of the lexer is on every byte read. Line number always increases when \n is met, while character number increases on each byte read then resets when we hit \n.

token/token.go

package token

type Token struct {
    Type    TokenType
    Literal string
    Range   Range // New - includes Start & End, both include Line and Character number
}

lexer/lexer.go

type Lexer struct {
    input        string
    position     int  // current position in input (points to current char)
    readPosition int  // current reading position in input (after current char)
    ch           byte // current char under examination

    line      uint // New - current line
    character uint // New - current column
}

func New(input string) *Lexer {
    l := &Lexer{
        input:     input,
        line:      1,
        character: 0, // we begin at 0 since we call readChar below, which advances our cursor and sets this to 1
    }
    l.readChar()
    return l
}

func (l *Lexer) readChar() {
    if l.ch == '\n' {
        l.line++
        l.character = 1
    } else {
        l.character++
    }

    if l.readPosition >= len(l.input) {
        l.ch = 0 // ASCII code for the "NUL" character
    } else {
        l.ch = l.input[l.readPosition]
    }
    l.position = l.readPosition
    l.readPosition++
}

Now that our tokens each have their positions known, we can collect the diagnostics as follows during parsing:
token.go

// New type
type Diagnostic struct {
    Range    Range
    Message  string
    Severity DiagnosticSeverity
}

parser.go

type Parser struct {
    l           *lexer.Lexer
    diagnostics []token.Diagnostic // updated field

    // ...
}

// ...

// An example of how we collect diagnostics
func (p *Parser) parseIntegerLiteral() ast.Expression {
    literal := &ast.IntegerLiteral{Token: p.curToken}

    value, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
    if err != nil {
        msg := fmt.Sprintf("could not parse %q as integer", p.curToken.Literal)
        p.diagnostics = append(p.diagnostics, token.Diagnostic{
            Message:  msg,
            Range:    p.curToken.Range,
            Severity: token.Error,
        })
        return nil
    }

    literal.Value = value
    return literal
}

Lines and Characters: 0 vs 1-based numbering

There was a decision we needed to make above: LSP positions are 0-based. But editors usually show lines and characters as 1-based numbers. I opted to use 1-based numbering for the Lexer and the Language Server's state analyzer.
We convert from 0 to 1-based numbers at the protocol boundary in translate.go and convert from 1 to 0-based when it's the other way around. Every diagnostic, hover, and definition range passes through that same conversion.

Syntax diagnostics are fairly easy. But hover, go-to-definition, and completion need to know what an identifier means - which let it refers to, whether it's a parameter or builtin.

There is no way to answer that without building a small semantic model of the program.

---

Step 4 - Static analysis: symbols, scopes, and the features built on them (the fun part)

Now that we have diagnostics, specifically errors, correctly being reported back to our editor and we can move on to implementing our three language features: hover, definition and completion.

This step is without a doubt the most interesting and challenging part of the entire project for me, but at the end, also very rewarding.

Let us look at what the shapes of requests and expected responses for each look like below.

Hover (see spec):

// REQUEST
{
    // ...
    "method": "textDocument/hover",
    "params": {
        "textDocument": { "uri": "file:///tmp/main.monkey" },
        "position": { "line": 2, "character": 5 }
    }
}

// RESPONSE
{
    // ...
    "result": { // optional
        "contents": {
            "kind": "markdown",
            "value": "```

monkey\nlet x = 42;\n

```"
        }
    }
}

In Neovim it is triggered with K and it shows an information on whatever is being hovered over.
We receive the document URI and exact position where the hover happens. We are expected to return a response with an optional content (markdown in our case) that has some information on the token under the cursor.

Definition (see spec):

// REQUEST
{
    // ...
    "method": "textDocument/definition",
    "params": {
        "textDocument": { "uri": "file:///tmp/main.monkey" },
        "position": { "line": 2, "character": 5 }
    }
}

// RESPONSE
{
    // ...
    "result": { // optional
        "uri": "file:///tmp/main.monkey",
        "range": {
            "start": { "line": 1, "character": 4 },
            "end": { "line": 1, "character": 5 }
        }
    }
}

In Neovim this is commonly triggered with g + d and it moves the cursor to the position in the code-base where the identifier under the cursor is defined.
We receive similar request params as Hover and we are expected to return an optional result including a file URI and a range (start and end position).

Completion (see spec):

// REQUEST
{
    // ...
    "method": "textDocument/completion",
    "params": {
        "textDocument": { "uri": "file:///tmp/main.monkey" },
        "position": { "line": 2, "character": 5 }
    }
}

// RESPONSE
{
    // ...
    "result": { // optional
        "items": [ { "label": "foobar", "kind": 6 } ]
    }
}

This request is triggered by typing in our editor. The request's content is similar to the above two, except here the position we receive is of the cursor's so it's one character off to the right of the text we are typing. The response includes an optional return field which includes a list of candidates to apply completion.

Our server as a response to these requests has to answer: what identifier is under the cursor?
If your intuition is to first find the AST nodes at the positions we get from the requests, then you're spot on!

But we immediately hit the wall here since our original interpreter's AST nodes do not have ranges defined to help us search the AST for what node exists at a specific position. We go back to our interpreter to extend it for the second time.

Adding Start() and End() on every AST node

Same trick as tokens, applied one level up. Every node already wraps a token or more so adding Start() and End() that return the token's range makes it trivial to walk the AST tree and find the smallest node containing a given position. The changes are as follows:
ast/ast.go

type Node interface {
    TokenLiteral() string
    String()       string
    Start()        token.Position // New
    End()          token.Position // New
}

Adding ranges to Monkey tokens earlier makes implementing these methods rather trivial. For example, If Expression AST nodes implement these as follows:

type IfExpression struct {
    Token       token.Token
    Condition   Expression
    Consequence *BlockStatement // BlockStatement implements Start() & End() itself
    Alternative *BlockStatement
}

func (ie *IfExpression) Start() token.Position { return ie.Token.Range.Start }  // New
func (ie *IfExpression) End() token.Position { // New
    if ie.Alternative != nil {
        return ie.Alternative.EndToken.Range.End
    }
    return ie.Consequence.EndToken.Range.End
}

Now we have a way of grabbing AST nodes from a parsed source code given a position in it using Depth First Search and the Start() and End() methods we just introduced.

Let's move on with our implementations for the three language features.

Implementing our language features and the problems we face

Hover

We can handle this request depending on the node under the cursor as follows:

• String Literal: Show the length and size of the string in bytes.
• Integer Literal: Show the hexadecimal, octal and binary representation of the number.
• Boolean Literal: Show just the value.
• Identifier: Show the type (variable, parameter or built-in function), name, and the position where it is defined.

We can implement the first three fairly simply, but the fourth one needs significantly more brain power to come up with a good enough solution for it. Consider the following scenario.

let num = 1;
puts(num);

Problem: If we hover over num on the second line, it should report back the position where the original is defined at, which we have no way of knowing currently.
The obvious and naive solution would be to traverse the AST again and to find the closest definition of this identifier to the position where the hover happened, in order to respect Monkey scopes. But this is inefficient to do on every hover request, we can do better.

Definition

We basically need to first find the node in the AST and if it's an Identifier node, we return the range where this identifier is defined.

Problem: We face the same exact problem as we mentioned above, we have no immediate way of knowing where this identifier is originally defined at in our source-code.

Completion

Completion needs more work to implement, we do the following in order:

1. get the full identifier that is in the process of being typed
2. know the deepest scope or function enclosing this identifier
3. build a list of candidate identifiers (identifiers that have current identifier as prefix) for the completion that are defined in the deepest scope enclosing the identifier and then unwind to go up the scopes up until the root scope where built-in functions and keywords are defined.

Problem: The two problems above were only about finding and searching for the closest definition of an identifier, but here we have a problem an order of magnitude bigger: we need to find multiple identifiers, but also that are in scope of the identifier before the cursor.

Before solving the problems listed above, we must do static analysis to help us solve these issues more efficiently.

Static analysis, symbols, symbol tables and diagnostics

Static analysis deals with inspecting the source code for semantic errors, style violations etc. In our case, we analyze our AST to collect our identifiers and all function scopes for quick access.

This will help us solve the problems mentioned in the previous section efficiently, since the analysis just happens once on text document open or update it allows every hover, definition or completion use the results of the latest static analysis.

We introduce a few more types in the analysis package.

analysis/scope.go

package analysis

// ...

type symbolType string

const (
    variable  symbolType = "variable"
    parameter symbolType = "parameter"
    builtin   symbolType = "builtin"
)

type symbol struct {
    Name       string
    Type       symbolType
    Range      Range
    Identifier *ast.Identifier
    Used       bool
}

type symbolTable struct {
    Outer   *symbolTable
    Symbols map[string]*symbol
}

• symbol represents all identifier definitions including variables, parameters and names of built-in functions.
• symbolTable stores symbols, the keys are their names and the values are the symbols themselves. It also has symbolTable.Outer field which will allow us to store symbols defined in the outer scope of the current symbol table.

We use the above to add some very important fields to Document struct.
analysis/state.go

type Document struct {
    // Version, URI, Content, AST, parser ... old fields

    rootScope      *symbolTable                          // New
    identifierUses map[*ast.Identifier]*symbol           // New 
    functionScopes map[*ast.FunctionLiteral]*symbolTable // New
}

• rootScope stores our initial/root symbol table initialized with symbols of built-in functions.
• identifierUses stores a map of pointers of all identifier nodes to their respective symbols.
• functionScopes stores a map of pointers of all function literal nodes to their respective symbol tables.

Now for the main player that makes sense of all the types we have mentioned above.
analysis/analyzer.go (some sections are removed for brevity)

package analysis

import (
    "fmt"

    "github.com/SegniAT/monkey-language-interpreter/ast"
    "github.com/SegniAT/monkey-language-interpreter/token"
)

// analyze builds the document's symbol table, resolves every identifier into
// the Uses map, records every function scope in the Scopes map and returns
// semantic diagnostics for undefined, redeclared and unused names.
func (d *Document) analyze() []token.Diagnostic {
    d.rootScope = newRootScope()
    d.identifierUses = make(map[*ast.Identifier]*symbol)
    d.functionScopes = make(map[*ast.FunctionLiteral]*symbolTable)

    var diags []token.Diagnostic
    d.visit(d.AST, d.rootScope, &diags)
    diags = append(diags, d.unusedDiagnostics()...)

    return diags
}

func (d *Document) visit(node ast.Node, scope *symbolTable, diags *[]token.Diagnostic) {
    if node == nil { return }

    switch node := node.(type) {
    // cases *ast.Program and *ast.BlockStatement:

    case *ast.LetStatement:
        if scope.define(node.Name.Value, variable, node.Name) {
            *diags = append(*diags, token.Diagnostic{
                Message:  fmt.Sprintf("redeclaration of %s", node.Name.Value),
                Range:    node.Name.Token.Range,
                Severity: token.Error,
            })
        }
        d.visit(node.Value, scope, diags)

    case *ast.FunctionLiteral:
        child := newChildScope(scope)
        d.functionScopes[node] = child
        for _, param := range node.Parameters {
            if child.define(param.Value, parameter, param) {
                *diags = append(*diags, token.Diagnostic{
                    Message:  fmt.Sprintf("redeclaration of %s", param.Value),
                    Range:    param.Token.Range,
                    Severity: token.Error,
                })
            }
        }
        d.visit(node.Body, child, diags)

    // multipe cases removed for brevity

    case *ast.Identifier:
        if sym, ok := scope.lookup(node.Value); ok {
            sym.Used = true
            d.identifierUses[node] = sym
        } else {
            *diags = append(*diags, token.Diagnostic{
                Message:  fmt.Sprintf("undefined variable: %s", node.Value),
                Range:    node.Token.Range,
                Severity: token.Error,
            })
        }

        // *ast.IntegerLiteral, *ast.Boolean and *ast.StringLiteral are leaves.
    }
}

• *Document.analyze gets called on events textDocument/didOpen and textDocument/didChange in order to analyze the latest source-code and return it's diagnostics.
• *symbolTable.define adds a new symbol to the symbol table and returns true if it is re-declared in the same scope.
• *symbolTable.lookup searches for a symbol by name in the proper scopes, starting from the current symbol table (scope) up to the root symbol table.
• *Document.analyze initializes some fields and starts the tree walker that populates the newly added Document fields and returns diagnostics.

*Document.visit is the main function that walks our AST and does several distinct actions depending on the type of the node it encounters:

• *ast.LetStatement: we define a new symbol using the node's name. If it is a re-declaration we add a new error diagnostic to our global diagnostics list.
• *ast.FunctionLiteral:
  1. We first create a new child symbol table using the current as parent.
  2. We save this child scope's pointer into *Document.functionScopes using the function literal AST node's pointer as key.
  3. We loop over the parameters and define symbols for each, if there's a re-declaration we add a new error diagnostic.
  4. We visit the function's body with our newly defined scope as input.
• *ast.Identifier: We lookup if a symbol exists with similar name, if so, we store the identifier to *Document.identifierUses using the node pointer as key and the found symbol pointer as a value. We also set *symbol.Used to true, we will find this useful later. If no symbol is found, we add an error "undefined variable" diagnostic to our global diagnostics list.

One last extra but useful thing is the method *Document.unusedDiagnosticscalled in *Document.analyze, its purpose is straight-forward: it collects warning diagnostics by going through every single symbol defined in all scopes of the source-code for unused symbols.

Note: Remember that we set a symbol's Used field to true when we come across an identifier in *Document.visit and if an identifier with the same name is found in the relevant scope/s.

We now have done all the work to finally implement our language features.

Hover, definition and completion implementation

Let's get straight to implementing our solutions now that we have overcome the latest blockers.

Hover

Source: analysis/state.go *State.Hover()

We first find the node at the specified position and then handle the request depending on the type of the node. The problem was that in case of hovering over identifiers, we did not have a good way to know the position where it is defined at.

We can now figure this out easily thanks to *Document.identifierUses. We use it to look-up the node's symbol and get the range off of it.

Definition

Source: analysis/state.go *State.Definition()

For Definition, we first find the AST node at the given position and we make sure that it's of an identifier type or we return early. We then look-up it's symbol in *Document.identifierUses and if we find a symbol we return it's range.

Completion

Source: analysis/state.go *State.Completion()

Completion does more work than the other two. After finding the exact identifier node, the next step is finding the deepest function node that encloses this identifier. From *document.functionScopes, we can get that function's symbol table, which also includes a pointer to its outer scope's symbol table. For each level of eligible scope, we go through the unique names of identifiers registered and check if the identifier being typed is a prefix to them, if it is we add it as one option for completion.

LSP has an option to differentiate what type of completion an item is, in our case we have three: Variable, Function and Keyword.
Most of our completion items will be of type Variable, even functions are defined using a let statement by assigning them to variables. Only built-in functions will have completion type Function and Keyword is for Monkey keywords such as if, let etc.

A design trade-off I hit while writing the analyzer

Our static analyzer has one flaw right now. For a let statement, it registers a symbol with the variable's name before visiting the right-hand side. This leads to failing to report "undefined variable" in the following case:

let a = a;

Suppose we fixed that by defining the symbol after visiting the right-hand side. Now consider:

let fib = fn(x) {
    if (x < 2) { return x; }
    return fib(x - 1) + fib(x - 2);  // fib not yet defined → error
};

Reporting an "undefined variable 'fib'" error here will hinder us from ever using recursion. Our interpreter can technically run the code without any problems but our Language Server will always report this as an error to our editor.

I chose to go with the current approach, i.e defining before visiting the right-hand side, because recursion is a first-class Monkey feature and self-reference is a footgun the programmer will notice immediately. Worth calling out as an explicit trade-off.

We are finally done with all the language features!

---

The let crash (a Go interface gotcha)

Excited, after implementing all the cool features of our Language Server I went right to testing. But I soon found out a bug that made my server crash.

Opening a file containing or typing the following:

let

If there ever is a let keyword alone without an identifier in the source-code, it crashes the server. I went digging through the stack-traces and finally figured out the problem! It was the following function in Monkey's parser.
parser/parser.go

func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    case token.LET:
        return p.parseLetStatement()
    case token.RETURN:
        return p.parseReturnStatement()
    default:
        return p.parseExpressionStatement()
    }
}

When parseLetStatement returns (*ast.LetStatement)(nil), that pointer is wrapped in the ast.Statement interface, and an interface holding a typed nil pointer is not nil. Every downstream if stmt != nil check succeeds, and the first field access panics.

This exact mistake is mentioned in the Go Mistakes and How to Avoid Them book under mistake #45, Returning a nil receiver.

The solution is to return nil explicitly at the call site. We return a nil interface, not a nil receiver converted into a non-nil interface.
parser/parser.go

func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    case token.LET:
        if stmt := p.parseLetStatement(); stmt != nil {
            return stmt
        }
        return nil // Explicitly returns untyped nil
    case token.RETURN:
        if stmt := p.parseReturnStatement(); stmt != nil {
            return stmt
        }
        return nil
    default:
        if stmt := p.parseExpressionStatement(); stmt != nil {
            return stmt
        }
        return nil
    }
}

---

Step 5 - Concurrency

The main loop of our server currently is single-threaded. While a hover request is being served, no notifications are being read. A slow request made the editor feel laggy, even worse, a long completion while the user typed meant didChange was queued behind it.

The solution to this is to dispatch request handlers in goroutines:
server/server.go

// ...
if isRequest {
    // Spin up a goroutine for read-only requests
    go func(reqID int64, reqMethod string, reqContent []byte) {
        defer func() {
            if r := recover(); r != nil {
                // ... logs error
            }
        }()

        s.HandleRequest(reqID, reqMethod, reqContent)
    }(*msg.ID, msg.Method, content)
} else {
    // Run notifications synchronously to guarantee state mutation order
    s.HandleNotification(msg.Method, content)
}
// ...

This solution however introduces a problem of its own. Now didChange notification (which mutates AST, identifierUses, functionScopes fields on Document) races against hover request (which reads identifierUses). Go's runtime map access detector could catch it, and could cause the server to fatally crash with a concurrent map read and map write message.

We must add a locking mechanism to our server's state to access and update these fields safely. We add a global sync.RWMutex to analysis.State.

analysis/state.go State

// ...
type State struct {
    mu        sync.RWMutex         // New
    Documents map[string]*Document
}
// ...

Write-lock on DidOpen, DidChange, DidClose.
Sources: analysis/state.go *State.DidOpen,
analysis/state.go *State.DidChange,
analysis/state.go *State.Close

func (s *State) DidOpen(...) []token.Diagnostic {
    s.mu.Lock()
    defer s.mu.Unlock()
    // ...
}

// DidChange and Close are similar to the above.

Read-lock on Hover, Definition, Completion.
Sources: analysis/state.go *State.Hover,
analysis/state.go *State.Definition,
analysis/state.go *State.Completion

func (s *State) Hover(...) *Hover {
    s.mu.RLock()
    defer s.mu.RUnlock()
    // ...
}

// Definition and Completion are similar to the above.

These additions solve the data race mentioned above.

---

Step 6 - Hooking up our server to Neovim

We should first add the monkey file type to Neovim, we have done the same in part 1 when adding our Tree-sitter to Neovim.

vim.filetype.add({ extension = { monkey = "monkey" } })

The final step is to configure and enable our LSP.

vim.lsp.config("monkey", {
    name="monkey-lsp",
    cmd= { "/path-to-LSP-binary/monkey" },
    filetypes = { "monkey" }
})

vim.lsp.enable("monkey")

---

Testing

All packages are extensively unit tested to ensure reliability.

• Unit tests for the RPC reader
• Analyzer tests: scopes, undefined vars, re-declaration, unused variables, closure capture.
• Manual testing in Neovim:
  • K for hover
  • gd for go-to-definition.
  • <CTRL + x><CTRL + o> for completion.
  • Typing let alone to confirm the nil-interface crash is fixed.

---

Showcase

Let's now look at the final result of our hard work!

Diagnostics on text document open and change

Re-declaration of variables

Notice how variables are function scoped by the way the second sum variable is not being reported as a re-declaration. Also note that this diagnosis also catches parameter re-declarations as well.

Undefined variables

result is undefined in the above code snippet.

Unused variables

We can use an underscore (_) to ignore unused variables so that the LSP won't complain about them, inspired by Go.

Hover

Hovering over a builtin function puts, a string, a parameter, a variable, a number and a boolean shows different types of information.

Definition

This request is triggered with <g><r><d> key combination in my current Neovim setup.

Completion

The completion request is triggered automatically in my Neovim, but it can also be triggered manually with <C-x><C-o>.

---

Conclusion

Part 1 taught editors what Monkey looks like. This post taught them what Monkey means. Between the two, we went from syntax highlighting to hover, go-to-definition, completion, and diagnostics - all from scratch, in a language that had none of them two posts ago.

The timeline this post actually followed: RPC framing, protocol types and handlers, document state and diagnostics, extending the interpreter with token ranges, adding AST node ranges, static analysis, the three language features, concurrency and locking, and finally wiring it all into Neovim.

Two lessons that stuck with me:

1. Editor features aren't a single feature. Diagnostics looked trivial until I realized the parser had no way to point at a range in the file. Hover looked trivial until I realized the AST had no node positions. Everything looked fine until I made the server concurrent and noticed a possible data race. Each feature I added exposed a missing layer in the layer below it. None of those trips back to the interpreter were in the original plan. All of them were necessary.

2. The protocol boundary is where conventions get translated. LSP is 0-indexed; editors are 1-indexed. The protocol deals in wire types; the analyzer deals in analysis.Hover and analysis.Location. Every one of those conversions lives in exactly one place - translate.go. It keeps the analyzer free of protocol concerns and the protocol layer free of analysis concerns, and it's the architectural decision I'd keep if I had to rewrite this from scratch.

What's next: Once Monkey has enough of a dev environment to be pleasant to write in, I want to see what it actually feels like to solve a real Advent of Code problem with it. That's Part 3.

---

References

• LSP specification (3.18)
• Part 1: Tree-sitter grammar for Monkey
• monkey-language-interpreter repository (includes LSP implementation in /lsp)
• Go docs: bufio.Reader, io.ReadFull, sync.RWMutex
• Go Mistakes and How to Avoid Them : the nil-interface gotcha, io.Reader/io.Writer abstraction