Learning Lisp - making sense of xrefs in SLIME

#learninglisp #lisp #slime #xrefs

This is a post in an ongoing series I decided to write on my journey learning Lisp. Read the brief intro to understand if this is for you.

The following was written by a beginner, with predictable consequences for how correct the contents may actually be.

After setting up a very basic and rudimentary Emacs/SLIME environment (post on that coming up soon), one of the first things I started testing out was my ability to navigate code - specifically, the Go to declaration functionality I use every 5 seconds of my day. There is little that's more important to my ability to learn about code.

xref & TAGS

Emacs has the builtin xref facility, short for "cross-references", which deals with, well, cross-referencing - things like "find definition", "find references", etc. However, from what I could tell, this seemed to require running one of several tools on the codebase I was interested in, which generates a TAGS file that contains metadata necessary for such navigation to work. This was very different from what I'm used to from "mainstream" development, where these things are usually done internally by the IDE.

First attempts

Given that, I was expecting this kind of navigation to not work out of the box. In other words, after I set SLIME up, typed e.g. (with-open-file in the REPL, and pressed M-., the mapping for xref-find-definitions, (or so I thought), nothing would happen.

I was wrong - instead, a new buffer opened at the definition of the with-open-file macro, inside the SBCL source code, which is the Lisp implementation I'm using.

This surprised me, so I proceeded to try the reverse, the equivalent of Find uses in IDEA. A quick Google search told me that the SLIME keybinding for that was C-c C-w c (notice how I'm conflating SLIME with xrefs - this was part of my mistake, but I didn't know any better at this point), but running that on the same symbol resulted in "No references found". It was pointed out to me that this keybinding was in fact only effective for functions, while with-open-file is a macro, but even switching to C-c C-w m didn't help.

This was strange, and after being encouraged to do so, I went digging to find out why.

The mistake

First and foremost, credit where credit's due - this SO answer helped me immeasurably.

It turns out that my conception of what was going on was incorrect form the start, which was the source of a large part of my confusion. When SLIME is active, M-. is not, in fact, bound to xref-find-definitions, but to slime-edit-definition instead. What this means is that SLIME hijacks M-. to completely remove the native xrefs facilities from the picture, and does its own thing instead.

To understand what exactly it does, you need to understand what SLIME and Swank actually are.

SLIME, Swank & Jupyter Notebooks

A useful (though likely imprecise) way to understand what SLIME and Swank are is the think of Jupyter notebooks. In them, you have two fundamental parts - the "frontend", which is the actual notebook and the part you interact with, and the "backend" (kernel in Jupyter parlance) which is a process to which the commands from the notebook get sent so they can be evaluated, and results are sent back. Each kernel represents a language (Python being the default, but a large number of other kernels are also available).

In this metaphor, SLIME is the Jupyter notebook, and Swank is the kernel. A different comparison might be to an editor and an LSP server. However, I prefer the Jupyter analogy, since a large part of what you can do via Swank is actually to interact with the running Lisp image, evaluating code, thereby affecting the process as its running - something that those of us coming from more mainstream languages find completely unimaginable.

As such, when you browse the code of SLIME, you will quickly find that slime-edit-definition delegates to swank:find-definitions-for-emacs.

Swank backends

The hunt continues in swank.el, where the essential part is the call to find-definitions.

This brings us to swank/backend.lisp, from which we can gleam that find-definitions is actually implemented on a per-lisp-implementation basis - different implementations provide different ways to access the information that's needed (some don't even provide the implementation at all!). Swank abstracts over these specifics and exposes a unified API for SLIME to use.

How it works

At this point, we've already learned a lot - namely, that it's the implementation (i.e. the running lisp process) that's responsible for providing the source locations, and anything else we might be interested in. Clearly, the only way it can learn that information is when we're actually compiling a file, and that's exactly how it works.

In the case of SBCL, it uses sb-introspect:find-definition-sources-by-name, which seems to use a in-memory database represented by info. This is updated during the compilation process.

One final question remains - why don't some of the operations, like "Show callers", work on internal SBCL symbols? The answer is that, by default, SBCL is built without the :sb-xref-for-internals flag, which means that it deliberately doesn't store the necessary data for internal functions, thereby saving 5-6MB of space. Calls to functions that need this data, therefore, come up empty.

Takeaways

Apart from having a much better understanding of how things work under the hood, I confess there's another part of this that I'm nothing short of astounded by.

I have somewhere around two weeks of spending my evenings reading about Lisp under my belt. I've written 0 lines of code, I'm at chapter 9 of Peter Seibel's Practical Common Lisp. I have as close to 0 experience about anything as you could possibly have, yet I was able to answer a question about the inner workings of something that spans three different pieces of software in about two hours of clicking through GitHub. I didn't even clone the repo's, cause I started this hunt out thinking that cross-referencing didn't work reliably in my setup.

I find it completely un-friggin-imaginable that I would even attempt something similar in another language. Just imagining that I would want to answer a question that would require me to traverse the source code of the Java compiler, IDEA and the Java LSP Server makes me instantly want to kill myself. And in that case, at least I would have some vague mental image of what was what - at the outset, I know at least a little bit of what the Java compiler/IDEA/LSP are, what their capabilities are, etc. But here, I had absolutely no clue about anything going in, actually had a few misconceptions that were throwing me off the scent, no tooling, no experience, no nothing.

That software of such complexity can be reduced to something that a complete beginner can traverse and find answers in in a matter of hours speaks volumes to why I want to learn this language in the first place.

Recap

When using SLIME, the standard xref facilities of emacs are completely bypassed - no TAGS involved
SLIME communicates with Swank, which provides a unified API for the functionalities it needs, such as finding definitions. This is implemented in an implementation-specific way for each Lisp implementation. The relationship between SLIME and Swank can be thought of as the relationship between Jupyter and its kernels
Most Lisp implementations track source code information and relationships in some way, and provide implementation-specific functions to expose this information. These are then used in the swank adapters.
Specifically SBCL doesn't collect this data for its own internal functions by default - this can be changed by building it with :sb-xref-for-internals

A previous version incorrectly listed the author of Practical Common Lisp as Paul Graham. Thanks to @vindarel for pointing this out!