jpaul - Java Program Analysis Utilities Library
Credo: "Papers have been written enough, let us see
systems!" - Reinhard Wilhelm
jpaul is a Java implementation of several algorithms
that are widely used in program analysis. Compiler writers often
reimplement a (relatively small) set of algorithms: graph algorithms,
dataflow engines, set constraint solvers etc. The goal of the
jpaul project is to have these algorithms implemented
independently of any compiler infrastructure project.
jpaul emphasizes (in order): correctness,
flexibility, ease-of-use, and asymptotic complexity (we are not very
interested in cutting-edge low level optimizations). The intended
audience consists of program analysis researchers in need of a
correct, elegant, and fast way of prototyping their analysis ideas.
jpaul is implemented in Generic Java (JDK 1.5); you
don't need any other package in order to use jpaul.
For development, jpaul has very common dependencies:
The entire code is released under the terms of the (Modified) BSD Licence. In the spirit of
scientific honesty, researchers who use jpaul are
encouraged to acknowledge jpaul explicitly in their
scientific publications; here is a
suggested BibTeX entry.
Version 2.5.1 released on April 5, 2006! -
Notes; Download Area
- Graph algorithms - package jpaul.Graphs:
- Generic definition of a directed graph (digraph) as a set of
root vertices and a navigator that describes the arcs of
the graph. This design allows the use of our library even for graphs
whose arcs are not explicitly stored in the vertices.
- General digraph algorithms: dfs traversals, reachability, shortest
- Strongly connected components (SCCs): given a digraph, we can
construct its topologically sorted component digraph - a digraph whose
vertices are the SCCs of the original graph.
- Basic block representation of a digraph.
- Directed binary trees (special digraphs). Utilities for iterating
efficiently over such trees in pre-/in-/post-order.
- Generic and efficient solver for systems of inequality constraints
over lattices - package jpaul.Constraints.
Generalization of classical set constraint solvers. Allows the user
to define its own kinds of constraints. As an example of the
constraint solver framework, we also implemented a set constraint
solver - package jpaul.Constraints.SetConstraints.
- Generic NFAs and regular expressions - package jpaul.RegExps:
- Conversion from NFA to regular expressions
- Useful data structures - package jpaul.DataStructs:
- Binary and ternary relations
- Classes for the factory pattern
- Copy-on-write data structures
- Work sets for fixed-point computations
- Other goodies - package jpaul.Misc
- Easiest way: To use jpaul, it
suffices to download the
file and add it to your CLASSPATH. Click here
for the download site.
Note for Eclipse users (courtesy Adam Kiezun): you may
add the downloaded
.jar file to your Eclipse project, select the
.jar and choose "
Build Path >
to Build Path" from the context menu. This will allow you to
use the jpaul code and also to see the
jpaul code you're using in Eclipse.
Alternatively, if you want to do changes inside
jpaul, you may download the file
jpaul-<version>-src.zip from here.
It contains all files of the project, including
jpaul.jar, Java source files, Javadoc, tests, etc.
- Anonymous (read-only) CVS access to the source code:
cvs -z3 -d:pserver:email@example.com:/cvsroot/jpaul co jpaul
Press Enter if prompted for a password.
- Full developer CVS access: First, make yourself an account on SourceForge, and contact the project admin (Alex
Salcianu) to obtain the right to edit the source. Next, you can
start with the following commands:
cvs -z3 -d:ext:firstname.lastname@example.org:/cvsroot/jpaul co
There are two mailing lists:
Projects that use jpaul
- Alex Salcianu uses jpaul extensively in the jppa (Java Pointer and Purity
Analysis) project. In particular, jpaul was used to
reimplement an inter-procedural, compositional pointer analysis for
Java. The implementation using jpaul is not only
cleaner and more flexible, but also faster than the original one: the
constraint solver from jpaul has a better grasp on
the "big picture" and can perfom optimizations that were impossible in
the original implementation.
- Adam Kiezun uses
the graph package of jpaul in a project that performs
generics-related refactorings in Eclipse - see his OOPSLA'05
demo. An early adopter, Adam has been a happy user of
jpaul ever since :)
- Please drop me an
email if you are a jpaul user. I would be happy to
hear your feedback and list your project here!
The jpaul Team
jpaul was started by Alex Salcianu in February
2005. Adam Kiezun
provided many useful comments and formally joined the
jpaul team in January 2006.
jpaul contains pieces of code contributed by the
following people: Suhabe
Bugrara (the initial version of the
prj.el script) and C. Scott Ananian (the initial versions of
UnionFind). Some of
the code from this project was initially developed for the MIT FLEX compiler
Copyright (c) 2005 - Alexandru Salcianu