Git Product home page Git Product logo

hdiff's Introduction

hdiff: Hash-based Diffing for AST's

This README provides some general info on the library. For detailed information on the algorithm, check our ICFP Paper. If you want even more details, please check my PhD thesis

The hdiff tool computes provides your usual differencing functions:

diff  :: a -> a -> Patch a

apply :: Patch a -> a -> Maybe a

The difference with respect to the other tree differencing tools out there is that HDiff.Patch a is a pattern-expression based patch. A picture is worth 1024 words: Take the following files:

   O.while                 A.while

a := n;                | a := 1;
while n > 0 do {       | while n > 0 do {
  n := n - 1;          |   a := a * n;
  a := a * n;          |   n := n - 1;
}                      | }
res := n;              | res := n;

Running hdiff examples/While/Factorial/{O,A}.while to compute their differences will the following patch:

[0] := n;       -|+  [0] := 1;
while [1] do {  -|+  while [1] do {
  [2];          -|+    [3];
  [3];          -|+    [2];
}               -|+  }
[4];            -|+  [4];

Everything to the left of -|+ is called the pattern, or deletion context. Everything to the right ot -|+ is called the expression, or insertion context. The square brackets denote metavariables, which is how hdiff copies information over. If we overlay the deletion context above over O.while, we will get an assignment of variables that we can use in the insertion context to produce A.while.

In reality, the output is a bit more complicated since it includes information about where each individual change happened. In this case, there are five changes:

  1. Copy of identifier a
  2. Change n into 1
  3. Copy condition of while loop
  4. Permute statements inside while loop
  5. Copy rest of the prorgam

The actual output is more like the following:

{-# [Cpy #0] #-} := {-# {- n -}{+ 1 +} #-}
while {-# [Cpy #1] #-} do {
  {-# [Prm #2 <=> #3]
      [Prm #3 <=> #2]  #-}
}
{-# [Cpy #4] #-}

Everything inside a {-# ... #-} is a change that happens in its own individual scope. Some changes are copies, some changes involve permutations and some changes delete match on something and insert something else.

But in reality, you will see the following ugly output because we have not implemented pretty-printing yet.

(Seq
 (:
  (Assign {-# [Cpy #7 ] #-} {-# {{- (Var "n") -} {+ (IntConst 1) +}} #-})
  (:
   (While
    {-# [Cpy #4 ] #-}
    (Seq {-# (: [Prm #2 <=> #3 ] (: [Prm #3 <=> #2 ] [])) #-}))
   {-# [Cpy #6 ] #-})))

Just like line-based diff, hdiff can be configured in many ways. Please, refer to hdiff --help for all the modes and options.

To see the result of a merge run with --verbose or -v; to see the patch produced by a merge run with --debug.

hdiff's People

Contributors

victorcmiraldo avatar ryanglscott avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.