A benchmark for Rust call-graph generators

The Rust community is seeing a growing number of static analysis projects such as rls [1] and rustfix [2] that provide users with rich and actionable functionality to fix problems or navigate through their large codebases. Underpinning many static analysis techniques are call graphs; graphs that capture the calling relationship between functions in the source code and are particularly useful for building functionality such as "goto definition" or "vulnerability analysis".

While these analyses are useful, there are problems with the guarantees existing tools can provide us. For example, projects or users that rely on the LLVM call graph produced by LLVM optimizer [3] will quickly see that calls of dynamic nature, i.e., dynamic dispatch and function pointer calls, are missing [4]. To quantify these sources and better understand what guarantees call graph generators for Rust programs are able to provide, we developed the “rust-callgraph-benchmark” [5].

The benchmark is a collection of hopefully all the possible ways to call a function or a method within and across package boundaries in Rust. This benchmark aims to enable call-graph generator implementers to assess the soundness of call-graphs generated by their tools. It can also serve as documentation of all the possible ways functions and methods may be called in Rust code.

Our next goal is to create a sound call-graph generator for Rust programs that will enable more sophisticated analyses in the Rust ecosystem setting, continuing the work started with RustPräzi [6].

Given our limited experience with Rust we would be grateful if you could provide any kind of feedback. All comments and pull requests with ways to call a function that we have missed are very welcomed. You can find a short list of several of the calls (with links to the well documented code) that are covered in the benchmark in the following README [7]. We have also tried to evaluate call-graph generator cargo-call-stack [8], but we were not able to run it successfully on our benchmark. If you are aware of other call-graph generators please let us know.

[1] https://github.com/rust-lang/rls

[2] https://github.com/rust-lang/rustfix

[3] http://llvm.org/docs/CommandGuide/opt.html

[4] https://github.com/ktrianta/rust-callgraph-benchmark/tree/master/evaluations

[5] https://github.com/ktrianta/rust-callgraph-benchmark

[6] https://users.rust-lang.org/t/announcing-rustprazi-a-tool-to-build-an-entire-call-graph-of-crates-io/22696

[7] https://github.com/ktrianta/rust-callgraph-benchmark/blob/master/src/README.md

[8] https://crates.io/crates/cargo-call-stack/0.1.0

9 Likes

cc @matklad and the rust-analyzer team