avaCGs: Version-Aware Call Graphs for Efficient Version-Range Queries

Abstract

Developers employ version ranges to specify a range of valid versions for software libraries their projects depend on. While this can yield benefits like automatic adoption of library updates, it complicates method reachability analysis: a sound whole-program analysis must consider method invocations of every library release within that range. Such releases might themselves introduce transitive ranged dependencies to a project, leading to a combinatorial blow-up in the number of configurations to analyze. If developers wanted to soundly determine whether a critical method might be reachable via a ranged library dependency, they would have to build the individual call graphs for every release within that range, and perform reachability analysis on each one of them. As call-graph construction is an expensive operation, this approach is rarely practical. To enable direct version-range queries, we introduce artifact version-aware call graphs (avaCGs) that comprise call graph information about all versions of a software artifact in a single graph structure. Further, we propose a novel approach that incrementally computes call graphs based on Rapid Type Analysis (RTA), implement it for the JVM platform, and show that it yields identical results to full RTA call-graph builds. Our evaluation shows that on our benchmarks, avaCGs can improve the performance of reachability queries by up to 9.58x, while our incremental construction is up to 79% faster compared to full builds for each release. We also observe that for real-world libraries hosted on Maven Central, almost 80% of all releases do not change the RTA call graph compared to their previous release, further justifying the use of incremental approaches.