README

Diff/AST: A Fine-Grained Source Code Differencing Tool

The tool is currently able to recognize Python, Java, Verilog, Fortran, and C/C++ via dedicated parsers. It compares abstract syntax trees (ASTs) node by node, while populardiff tools compare any (text) files line by line. The algorithm is based onan algorithm for computingtree edit distance (TED) between two ordered labeled trees. The TED between two trees is the minimum (weighted) number of edit operations to transform one tree into another. Unfortunately, however, applying TED algorithms directly to wild ASTs is not feasible in general becausetheir computational complexity is essentially, at best, quadratic according to the number of AST nodes. Therefore Diff/AST makes moderate use of a TED algorithm in a divide-and-conquer manner backed by elaborated heuristics to approximate tree edit distances. Nevertheless, Diff/AST still requires much time for non-trivial massive inputs. Thus it always caches the results.

Diff/AST is able to export ASTs, changes between them, and other syntactic/semantic information asfacts inXML orN-Triples. In particular, facts in N-Triples format can be loaded into an RDF store such asVirtuoso to build afactbase or a database of facts. Factbases are intended to be queried for software engineering tasks such ascode comprehension,debugging,change pattern mining, andcode homology analysis.

Diff/AST is an experimental implementation of the tree differencing algorithm reported in the following paper:

Masatomo Hashimoto and Akira Mori, "Diff/TS: A Tool for Fine-Grained Structural Change Analysis," InProc. 15th Working Conference on Reverse Engineering, 2008, pp. 279-288, DOI:10.1109/WCRE.2008.44.

Screenshots

You can see the results of comparing some pairs of source files taken fromsampleshere.

Quick start

You can instantly try Diff/AST by utilizingDocker anda ready-made container image.

$ docker pull codinuum/diffast

The following command line executes Diff/AST within a container to compare sample Java programs and then saves the results inresults (host) directory.

$ ./cca.py diffast -c results samples/java/0/Test.java samples/java/1/Test.java

If you want to inspect the AST differences in a viewer window, you have to initialize a submodulediffviewer first.

$ git submodule init$ git submodule update

Seediffviewer/README.md to build the viewer. Once you heve built the viewer, you can run the viewer as follows.

$ diffviewer/run.py -c results samples/java/0/Test.java samples/java/1/Test.java

You can also run both at once.

$ ./cca.py diffast -c results --view samples/java/0/Test.java samples/java/1/Test.java

Installing parsers and Diff/AST

Requirements

• OCaml (>=4.14)

• OPAM

Installation

The following will installparsesrc anddiffast.

$ opam install diffast

Building parsers and Diff/AST

You can also build parsers and Diff/AST in person.

Requirements

• OCaml (>=4.14)

• Dune

• OPAM (for installing required packages)

Compilation

The following will create./dist/bin/{parsesrc,diffast}. $ opam install bytesrw camlp-streams camlzip cryptokit csv dune dune-site git-unix markup menhir sedlex uuidm vlt $ dune build --relocatable --prefix ./dist

Using with Git

If you have built Diff/AST, you can use it with Git. Add the following lines to your.gitconfig. Note thatPATH_TO_THIS_REPO should be replaced by your local path to this repository.

[diff]    tool = diffast[difftool]    prompt = false[difftool "diffast"]    cmd = PATH_TO_THIS_REPO/git_ext_diff "$LOCAL" "$REMOTE"[alias]    diffast = difftool

Then you should be able to usegit diffast likegit diff. You will be prompted to launch diffast for each source file comparison. Other file comparisons will be ignored.

Building docker image

The following command line creates a docker image nameddiffast.

$ docker build -t diffast .

License

Apache License, Version 2.0

1. vlt>= "0.2.4"
2. diffast-etc= version
3. diffast-git= version
4. diffast-api= version
5. diffast-core= version
6. diffast-misc= version
7. logs
8. fmt
9. mtime>= "2.0"
10. cmdliner
11. dune>= "3.17"
12. ocaml>= "4.14"

1. odocwith-doc

1. diffast

None