Software

ComplexityParser

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.

Download

The current 1.0 version can be downloaded from gitlab :

https://gitlab.inria.fr/complexityparser/complexityparser/-/archive/v1.0/complexityparser-v1.0.zip.

You can also clone this repository using git.

The examples suite is in the examples/ directory and is available for download as a zipfile:

https://gitlab.inria.fr/complexityparser/complexityparser/-/archive/v1.0/complexityparser-1.0.zip?path=examples.

Compile

With maven

To compile this program using maven, execute the command

mvn package

Run

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:

  1. on the left, the analyzed code
  2. in the center, the parse tree of this code
  3. 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.

The 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).

Dependencies

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.

Authors

Emmanuel Hainry, Emmanuel Jeandel, Romain Péchoux, Olivier Zeyen, Nishigandha Yadav

References

  1. 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.

  2. Emmanuel Hainry and Romain Péchoux. Objects in polynomial time. In APLAS 2015, LNCS, pages 387–404. Springer, 2015.

  3. Emmanuel Hainry and Romain Péchoux. A type-based complexity analysis of object oriented programs. Information and Computation, 261:78–115, 2018.