Incrementalization of Analyses for Next Generation IDEs

To support developers in their day–to–day work, Integrated Develoment En- vironments (IDEs) incorporate more and more ways to help developers focus on the inherent complexities of developing increasingly larger software systems. The complexity of developing large software systems can be categorized into inherent complexity that stems from the complexity of the problem domain and accidential complexity that stems from the shortcomings of the tools and methods used to tackle the problem. For example: To reduce the complexity of having to know exactly, which methods a certain class provides, IDEs offer autocompletion. To alert developers to errors and potential errors in their use of the programming language, IDEs connect the lists of warnings and errors with their source locations. To ease navigation in bigger projects, structural views of the program, such as the type hierarchy are presented. Development environments thus enable developers to be more productive and help them to find bugs earlier in the development cycle by using codified expert knowledge. In these environments, static anlyses are used to extract information from the program under development. Static analyses detect properties of pro- grams without running them. In the past, static analyses were mostly integrated into compilers with the goal to check for errors and to produce faster or smaller code. Integrating static analyses into the IDE opens up new areas of application. Among these are domain specific analyses, optional type systems and checks for structural properties. Domain specific analyses check properties specific to the program under development. For example, that the use of a framework conforms to the specifications. Optional type systems are type systems that do not influence the runtime semantics. This allows to have multiple type systems (e.g. confined types and the builtin Java type system) to coexist and to be checked by static analyses. If these analyses are available to developers, a wider range of software defects can be detected. By integrating the analyses into the IDE, faster and better feedback can be delivered. This enables developers to incorporate the analyses in their daily workflow, as it preserves the immediacy. To gain full advantage of IDE integration, the analyses need to be integrated into the incremental build process of the IDE and the rulebases should be modularly modifiable to fit the program under inspection. One exam- ple for an open, modular approach to achieve this is Magellan. Magellan is a build process integrated open static analysis platform that tackles the problems of integrating static analyses with the IDE and in particular with the incremental build process. To benefit from this integration, analyses running on such platforms need to work in an incremental fashion. In this thesis, approaches for incrementalizing static analyses for integrated open static analysis platforms are analyzed. Incrementalizing a static analysis means, that the analyses uses the result from a previous build and the changes made to the program as additional input to reconcile the result from the previous build. The result is equal to an analysis of the full build. The approaches can be categorized into manual incrementalization and automatic incrementalization. Manual incrementalization uses a general pur- pose language, such as Java, to implement a static analysis that achieves the incrementalization using a special purpose algorithm. Automatic incremen- talization means, that the analysis is written with the full build in mind, and the underlying mechanisms of the language or framework has a builtin mechanism to reconcile the results for the changed program. Currently, incremental analyses are developed in an ad hoc fashion, choos- ing the approach the developer is most familiar with. If the appraoch taken is not the best for the problem at hand, then either the development will take longer or the analysis will run slower then necessary. To investigate the properties of analyses that influence the recommended appraoches to incrementalization, three static analyses have been selected. The analyses were implemented twice; once using the manual approach and once using the automatic approach. The three selected analysis represent analyses that check for data flow properties, control flow properties and structural properties of the inspected program. The analysis that checks for data flow properties searches for violations of an optional type system for confined types. The analysis that checks for control flow properties incrementally computes the call graph using the rapid type analysis (RTA). Finally, the static analysis that checks for structural properties searches for violations of structural dependencies between concerns in the program. The results indicate, that analyses incorporating query engines to be used by the user of the analysis need to use automatic incrementalization at least for this purpose. Analyses that can be configured only in narrow, predictable ways lend themselves to manual incrementalization. Then the domain knowl- edge allows for domainspecific optimizations that cannot easily be integrated into the frameworks for automatic incrementalization