UAST
In the near future, a component for finding errors based on a unified abstract syntax tree (UAST for short) will be integrated into Svace.
Motivation
Svace has a component for static analysis based on an Abstract Syntax Tree (AST) for C, C++, Java, Kotlin and Go programming languages.
Analysis structure can be generally represented like this:
- During the controlled build stage, the compiler for the corresponding language is run, generating the AST for the source program;
- Acquired AST is analysed by detectors.
- In case with Java and Kotlin languages detectors are written in modified version of their compilers.
- In case with Go
Goawhich is our own development.
- Warnings are then written into files in
svresformat, which is then imported to Svace during the main analysis stage.
This structure is quite fiddly:
- A separate code base is required for each language.
- Duplication of source code. It is often necessary to implement an AST-based detector that works for several languages at once. In the current scheme, you have to implement and maintain such detectors for each language separately (
BAD_COPY_PASTEcan serve as a good example. It is written for C, C++, Java and Kotlin, but all the implementations are different from each other).
In order to eliminate the described inconveniences, we add the UAST component to the analyzer, which will analyze unified abstract syntax tree for different programming languages.
UAST analysis internals
UAST consists of two stages:
- Translation source program’s AST into UAST format and generation of intermediate files. Happens with execution of
svace buildcommand; - Reading intermediate files and their subsequent analysis. Happens with execution of
svace analyzecommand;
Thus, all the detectors are present in the same code base, which allows a simpler creation of new detectors and simpler support of said detectors.
UAST usage can also ease addition of new programming languages into the analyzer. For example, if Python which is being added to Svace, was added the old way, then in order to implement AST analysis, we would have to add another language to the scheme above.
The analysis operates with three basic entities:
- Nodes of the unified AST;
- Symbols — different named entities including variables, functions, classes, etc. Every single unique named entity is directly linked with a single unique symbol.
- Types. Types are implied in terms of static typing, which means every symbol is linked with a single type.
At the current moment UAST analysis is implemented for Java, Kotlin and Python. In the future it will also be implemented for Go programming language.
In case with Java and Kotlin translation is implemented via compiler plugins for said languages. That’s why translator has all the information compiler has, thus no information is lost.
For the Python language, translation is implemented via a standard library module ast. Also, as this language has dynamic typing, information about types is not calculated and not used during the analysis.
Limitations
UAST analysis works only within bounds of a single file. The cause to this is that this analysis has to be fast and lightweight.
Because of this UAST analysis is not capable of finding errors, the origin of which is located in several files.