dep-graph-queries is an optimization for queries we run on top of the clj-kondo analysis. The best way to understand it is with an example. Consider finding a var-definition from a var-usage. The var-usage has a :name and a :to, the namespace of the var-definition. Before, to find the definition we had to search through all of the analysis. That is, since clojure-lsp indexes the analysis by filename, we had to look at each file’s var-definitions in turn, looking for one whose :ns matched the usage’s :to. Now we keep an additional index—called the “dep-graph”—alongside the analysis, which is indexed by namespace instead of filename. To find a var-definition, we start with the var-usage’s :to namespace. We use the dep-graph to figure out which files define that namespace. Then, using the regular analysis, we look at only the var definitions in those few files. Looking at only a few files improves performance by orders of magnitude over looking at every file. It also means that over time query performance will tend to stay proportional to the average number of dependencies between files, instead of proportional to the total number of files. As projects grow the average grows much more slowly than the total. This new index is called the dep-graph because in addition to ns -> filename, it also includes ns -> dependent-nses and ns -> dependency-nses. Having quick access to the dependencies between namespaces is useful for other kinds of queries. For example to go the other direction, to find the var-usages from a var-definition, first we look up all the namespaces that depend on the namespace that defines the var. Those are the namespaces (and in turn the files) that could have var-usages in them. This greatly reduces the number of files whose analysis we need to look at in order to find all the var-usages. The dep-graph is all built from clj-kondos namespace-usages and namespace-definitions, so it’s really just a more convenient and more efficient way of using data we were already getting from clj-kondo. So as always, many thanks to your hard work on clj-kondo @U04V15CAJ. 🙇

@jacob.maine Makes sense!

@jacob.maine Thank you for the explanation. Is there a recommended way to access the dep-graph data of my project directly? I'm looking over the clojure-lsp code to try to get an idea, but if you could point me in the right direction it would be appreciated 🙏

@UPWHQK562 sure… first a question. How do you use clojure-lsp? Some common answers are: • “I don’t know—it seems to be connected to my editor.” • “I make debug builds and connect to the clojure-lsp nREPL.” • “I use the clojure-lsp command line tool.” • “I include clojure-lsp in my project’s deps, and use the tools in the clojure-lsp.api namespace.”

(so many usages possibilities for clojure-lsp 💜)

@jacob.maine At present I connect my editor to the brew-installed binary. But I'm interested in experimenting with the API. I'm building a project that also makes use of clj-kondo's analysis data and I'm wondering if I can make use of some of clojure-lsp's solutions to improve my stuff. I'm looking at clojure-lsp.api now. It doesn't look like diagnostics gives me the dep-graph data. BTW, the source links in the https://cljdoc.org/d/com.github.clojure-lsp/clojure-lsp/2022.09.01-15.27.31/api/clojure-lsp.api page are broken. Shall I make a ticket for that? And also thanks very much to everyone involved in maintaining LSP and its underlying tooling too 🙂

> I'm looking at clojure-lsp.api now. It doesn't look like diagnostics gives me the dep-graph data. Yeah, the dep-graph is intended to be internal ATM, maybe https://github.com/clojure-lsp/clojure-lsp/issues/744 would be useful for you as we could have access to that data via the dump > BTW, the source links in the https://cljdoc.org/d/com.github.clojure-lsp/clojure-lsp/2022.09.01-15.27.31/api/clojure-lsp.api page are broken. Shall I make a ticket for that? Yes, please

@UPWHQK562 let me point you to a few spots in the code so you can explore, but also give you some caveats. The dep-graph is built and queried from clojure-lsp.dep-graph. It’s updated as files are updated, and its current value is stored in what clojure-lsp calls the “components”. There are different versions of the components depending on whether you use the nREPL, clojure-lsp.api or something else, which is why I was asking about that. If you plan to use clojure-lsp.api, you can get the current dep-graph from (:dep-graph @clojure-lsp.internal-api/db*). (It’s not very convenient, because as @UKFSJSM38 said, it’s intended to be internal.) If you have your own copy of the clj-kondo analysis and were hoping to use the clojure-lsp code to construct a dep-graph, that’s a little tricky. We massage the analysis into our own structure with clojure-lsp.kondo/normalize-analysis before using it to construct the dep-graph with clojure-lsp.dep-graph/refresh-analysis. (You can see the massaged analysis in (:analysis @clojure-lsp.internal-api/db*).) The sequence of steps is a little tricky, so let me know if you’re going down this route and want suggestions. I’ll also say that this isn’t the only way to get dep-graph style data. The data all exists in clj-kondo’s namespace-usages and namespace-definitions, so you can look there. Or you can go a totally different route and use clojure.tools.namespace. That project can pull namespace data out of files and put it into a graph structure. We don’t use any of that code, but it was an inspiration for how to use a Clojure hashmap to represent a graph data structure.

And I should clarify—clojure-lsp doesn’t have any built-in file watching. So when I say that the dep-graph is updated as files are updated, that only happens when clojure-lsp is instructed to re-analyze files. When used from an editor, the editor sends notifications saying that a file has been updated. We react by re-analyzing the file. But, when you’re using it from clojure-lsp.api, the analysis and dep-graph are really just loaded once as we run the initial analysis.

@jacob.maine Thank you for all the detail. I will check out all of those routes over the next little while and will likely have some followup questions. From the sound of it, the second paragraph - constructing a dep-graph from my own clj-kondo analysis - is what will be most fitting to my use case. I'm running analysis on many Clojure projects and storing them in a normalized SQL DB at the moment. I don't think that storing it in a map how LSP does it is something I could benefit from, but if there are parts of the data structures or even the names used which I could adopt, I would like to do that. I'm not totally sure what steps I'll need to take next and it's not something I'm going to actually start implementing now, but the dep-graph feature sounds quite useful and I'd like to start doing the exploration. Thanks for the pointer to #744, @UKFSJSM38. That definitely is something I have some interest in and will be keeping an eye on.

@UPWHQK562 if you’re storing analysis in a SQL DB you likely already have a dep-graph. That is, assuming you have a namespace_usages table with from and to columns, then given a namespace ‘x’, you can get dependencies with SELECT to FROM namespace_usages WHERE from = 'x'; and dependents with SELECT from FROM namespace_usages WHERE to = 'x';. In fact, I expect that many of your queries wouldn’t benefit from a dep-graph at all, because that information is already built into your indexes. For example, after finding a var usage x/y, all you have to do to find the definition is SELECT row, col FROM var_definitions WHERE ns = 'x' AND name = 'y'. clojure-lsp on the other hand has to go through several more hoops to figure out which files define x, and then to filter those file’s var-definitions. We have to do that only because the top-level keys in our analysis hashmap are filenames. That is, we index only on filename (and secondarily on bucket). You can bypass that because, presumably, you have indexes on both filename and ns. In fact, in many respects clojure-lsp needs a dep-graph only because it doesn’t use a SQL DB. If we had access to a relational algebra with indexing and a query optimization engine, we’d probably use it for most of the stuff we use the dep-graph for. If you tilt your head and look at clojure-lsp.dep-graph and clojure-lsp.queries from a certain perspective, all those Clojure hashmap lookups, filters and maps could be re-written as SQL statements. Several months ago I experimented with converting clojure-lsp to store clj-kondo analysis in a Datalog database, which offers the same thing as a SQL database—normalization, indexing and expressive queries. It definitely made queries faster. The problem with it was that file updates were much slower—after analyzing a file, we had retract all the file’s existing data, re-insert the new data, and let the indices rebuild. That was much slower than associng the new analysis into the existing analysis hashmap, clobbering what was there before. clojure-lsp needs to optimize for write speed because much of what it does revolves around reacting as a user is typing. If we didn’t have that requirement, if we just needed to do a single analysis run, a normalized, indexed database would almost certainly make more sense

@jacob.maine Yes, you are right, I do already have my own version of a dep-graph that is likely more optimized for certain reads, especially those spanning multiple projects, but I still think there would be some value in adopting parts of the LSP code and structure where it would fit. My project is new while the solutions in clojure-lsp are more mature and have benefited from community involvement. If I can get a deeper understanding of how LSP does things and use it to guide the needs of my project, I think it could be worthwhile. One last quick question for now... I recently saw one of your tickets related to the use of the positional attributes row, col, name-col, etc., but I can't seem to find it now. Do you happen to recall which issue it was?

Yeah, definitely—there’s a lot of Clojure knowledge built into clojure-lsp. It’s a good resource for that, even if you’re just reading code and borrowing ideas. I’m not sure which PR you mean. Maybe https://github.com/clojure-lsp/clojure-lsp/pull/1188 one or https://github.com/clojure-lsp/clojure-lsp/pull/1180 one?

Yes, it's that first one. Thank you. I think that's enough data for my brain for now 🙂 I'll have a good look around the code and maybe start a new thread sometime with followup questions.

:thumbsup: happy to chat further, whenever you have questions