ComplexityParser1 is a static complexity analyzer for Java programs based on tier-based typing following 2 and 3. If a program is typable, this guarantees its runtime to be polynomial on the condition that it halts. The type inference is automatic; its complexity is linear in the size of the input program in practice.
The code is under the Apache 2.0 License.
The current 1.0 version can be downloaded from gitlab :
You can also clone this repository using git.
The examples suite is in the
examples/ directory and is available for download as a zipfile:
To compile this program using maven, execute the command
Compilation will create an executable jar inside the
target/ folder that can be run with
java -jar target/complexity-1.0.jar
Once the application has opened, you are presented with 3 panels:
- on the left, the analyzed code
- in the center, the parse tree of this code
- on the right, the results of the typing inference.
The code in the left panel can be edited directly. When you click on the update button or press the
F6 key the code will be analyzed, the parse tree will be updated and the right panel will show information about (successful or unsuccessful) typing operations and the final result. If the
Final Result is 0 or 1, it means that the typing was successful: the code is polytime provided it halts. If the
Final Result is
None, the typing failed.
File > Open menu or the
Ctrl - o shortcut can be used to open a file and analyze it instead of writing the code in the left panel. The code in the left panel can still be edited but it will have no effect on the loaded file (no changes are or can be saved).
This program uses the ANTLR framework to generate a parser, this is the only dependency and it will be downloaded automatically if you compile the program with maven.
Emmanuel Hainry, Emmanuel Jeandel, Romain Péchoux, Olivier Zeyen, Nishigandha Yadav
Emmanuel Hainry, Emmanuel Jeandel, Romain Péchoux, and Olivier Zeyen. ComplexityParser: an automatic tool for certifying poly-time complexity of Java programs. In International Colloquium on Theoretical Aspects of Computing (ICTAC), LNCS, volume 12819, 2021.
Emmanuel Hainry and Romain Péchoux. Objects in polynomial time. In APLAS 2015, LNCS, pages 387–404. Springer, 2015.
Emmanuel Hainry and Romain Péchoux. A type-based complexity analysis of object oriented programs. Information and Computation, 261:78–115, 2018.