jpaul - Java Program Analysis Utilities Library

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: 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
• Getting started
• Javadoc: current, 2.5.1, 2.5, 2.4.1, 2.3,
• Mailing Lists
• Projects that use jpaul
• The jpaul Team
• Acknowledgements
• Project webpage on SourceForge
• Online interface for bug reports and feature requests

• 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-/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 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 (read-only) 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
  
  

• jpaul users list: jpaul-users@lists.sourceforge.net Archives/Subscribe/Unsubscribe

• jpaul developers list: jpaul-devel@lists.sourceforge.net Archives/Subscribe/Unsubscribe

• 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!