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, easeofuse, and asymptotic complexity (we are not very
interested in cuttingedge 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:
ant and
junit.
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.
NEWS:
Version 2.5.1 released on April 5, 2006! 
Release
Notes; Download Area
Current Features
 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
paths, etc.
 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/postorder.
 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
 Copyonwrite data structures
 Work sets for fixedpoint computations
 Other goodies  package jpaul.Misc
Getting Started
 Easiest way: To use jpaul, it
suffices to download the
jpaul<version>.jar
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
>
Add
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 (readonly) CVS access to the source code:
cvs z3 d:pserver:anonymous@jpaul.cvs.sourceforge.net:/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:
export CVS_RSH=ssh
cvs z3 d:ext:developername@jpaul.cvs.sourceforge.net:/cvsroot/jpaul co
jpaul
Mailing Lists
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 interprocedural, 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
genericsrelated 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.
Acknowledgements
jpaul contains pieces of code contributed by the
following people: Suhabe
Bugrara (the initial version of the RegExps
package),
Darko Marinov
(the Emacs prj.el
script) and C. Scott Ananian (the initial versions of
ReverseListIterator
and UnionFind
). Some of
the code from this project was initially developed for the MIT FLEX compiler
infrastructure.
Hosted by
Copyright (c) 2005  Alexandru Salcianu