Chopachops Report
This page is under construction...
Introdution
ChopaChops is a project for slicing and chopping in program graphs. Starting from the
Java program source code, this tool can generate graphs with relation information.
Objectives
Work already done - PackageGraphs
On the moment I took the project, much work was already done.
ChopaChops could already do things like:
- Java parsing to an haskell abstract syntax tree
- Creation of Package Graphs, which contains class-based relations like:
- Imports
- Inheritance
- Implementation
- Nesting
- Visualization of these relations in a graph
- Metrics on graphs
- Implementation of slicing and chopping on the graphs
My Extension - Call Graphs
Starting from the work done, I extended the libraries, adding some method-based relations:
- Method invocation
- Method nesting in classes
Call Graphs in haskell
-- | Call Graphs are labeled relations
type CallGraph
= LRel CGNode CGNode CGEdgeType
-- | A node may be either a Class or a Method
data CGNode = CGClass ClassName
| CGMethod ClassName MethodName [ParameterType]
...
-- | Function to create a CallGraph for an AST
java2ccg :: (Term a, MonadPlus m)
=> CGNode -- Current node
-> Declarations -- Declarations context
-> a -- Term to convert to Call Graph
-> m CallGraph
-- | Function to convert a Call Graph to dot format, ready to feed the GraphViz tool
cg2dot :: String -> CallGraph -> String
Declarations Environment
I provide a basic API for
Declarations
manipulation
Here is an extract of it:
emptyDec :: Declarations
appendDec :: Declarations -> Declarations -> Declarations
addGlobalDec :: Declarations -> (ClassName, MemberName) -> TypeName -> Declarations
...
-- | General funcion for getting a variable's/member's type
getType :: (MonadPlus m) => Declarations -> ClassName -> MemberName -> m TypeName
-- | Generic function to collect global variable declarations, providing the AST
collectMembers :: (Term a, MonadPlus m) => ClassName -> a -> m Declarations
Type Inference System
To determine which classes were getting method invocations, it was necessary to buid a type inference system.
To accomplish that task I used strafunsky to do generic AST traversals.
So, I came up wit a function called
findTypeOf
which has the flollowing type signature:
findTypeOf :: (Term a, MonadPlus m) => Declarations -> ClassName -> a -> m TypeName
This function (tries) to find out the type of any entity, provided it is an instance of
Term
. We have to provide the environment (
Declarations
) and the class name on wich we are trying to find the type of an entity.
The Tool - ChopaChopsOnline
ChopaChopsOnline is a tool, developed with
WASH
, wich interfaces the developed librarires with the user. Basicaly, it is a web
, wich can be run from a Web Server.
The user, with this tool, can perform operations like:
- Upload zip archives, containing Java source files (all other filetypes are simply discarded)
- Visualize both Package and Call Graphs
- Visualize some graph metrics such as:
- Tree impurity
- Level count (strongly connected components)
- Non singleton levels
- Size of the largest level
- ...
- Perform slicing and chopping on these graphs (Package and Call graphs), given the sources and sinks sets
Web interface:
Chopping:
Example
- Class Foo:
- Class Bar:
- Callgraph:
Future Work
Although much progress has been done regarding program slicing, I must state that this project is far from being a complete approach to Java Program Slicing.
So, there is still much work to do in the future, to extend this tool.
I will enumerate some ways to evolve, although there may be others:
- Extend the type inference system to support more types
- Compute more graph metrics
- Continue to move to lower level relations:
Problems
- Hard to understand big graphs (real world java programs)
- Type inference system not fully implemented
- Not working with compiled classes
- Does not handle some java features
- Inheritance / Implementation
- Static methods
- Exception handling
Conclusion
- Nice progresses towards full program slicing in Java
- At the moment there is no support for many Java features
- Easy to extend
- Part of the UMinho Haskell Library
- ChopaChopsOnline (tools)
- CallGraph?
- Much work to be done in the future...