sexp-diff

8.12

sexp-diff🔗ℹ

Vincent St-Amour <stamourv@racket-lang.org>
and William J. Bowman <wjb@williamjbowman.com>

This package provides an S-expression-aware diffing tool based on Levenshtein-like tree edit distance.

procedure
(sexp-diff e1
e2
[ #:old-marker old-marker
#:new-marker new-marker]) → sexp?
  e1 : sexp?
  e2 : sexp?
  old-marker : (or/c any/c (-> any/c list?)) = '#:old
  new-marker : (or/c any/c (-> any/c list?)) = '#:new

Produces a tree that corresponds to the common structure of e1 and e2, with e1-specific parts tagged with old-marker and e2-specific parts tagged with new-marker.

If either old-marker or new-marker is a procedure?, then it will be called on the node instead of inserted as a literal in the tree. This can be used to replace the node with a new s-expression whose head is the marker, rather than inserting the marker as a sibling of the node, enabling the marker to be interpreted as a function in some DSL. It may make more sense to use this feature in stx-diff.

Examples:

> (sexp-diff
   '(define (f x) (+ (* x 2) 1))
   '(define (f x) (- (* x 2) 3 1)))
'((define (f x) (#:new - #:old + (* x 2) #:new 3 1)))
> (sexp-diff
   '(define (f x) (+ (* x 2) 4 1))
   '(define (f x) (- (* x 2) 5 3 1)))
'((define (f x) (#:new - #:old + (* x 2) #:new 5 #:new 3 #:old 4 1)))
> (sexp-diff
   '(define (f x) (+ (* x 2) 4 4 1))
   '(define (f x) (- (* x 2) 5 5 3 1)))
'((define (f x)
    (#:new - #:old + (* x 2) #:new 5 #:new 5 #:new 3 #:old 4 #:old 4 1)))
> (sexp-diff
   #:old-marker '#:expected #:new-marker '#:actual
   '(1 2 3 4)
   '(1 2 2 4))
'((1 #:actual 2 2 #:expected 3 4))
> (sexp-diff
   #:old-marker (lambda (x) `((highlight:old ,x)))
   #:new-marker (lambda (x) `((highlight:new ,x)))
   '(1 2 3 4)
   '(1 2 2 4))
'((1 (highlight:new 2) 2 (highlight:old 3) 4))
> (sexp-diff
   '((1) 2 3 4)
   '([1] 2 2 4))
'(((1) #:new 2 2 #:old 3 4))

procedure
(stx-diff e1
e2
[ #:old-marker old-marker
#:new-marker new-marker]) → syntax?
  e1 : syntax?
  e2 : syntax?
  old-marker : (or/c any/c (-> any/c syntax?)) = '#:old
  new-marker : (or/c any/c (-> any/c syntax?)) = '#:new

Produces a syntax object that corresponds to the common structure of e1 and e2, with e1-specific parts tagged with old-marker and e2-specific parts tagged with new-marker.

The algorithm ignores syntax properties and source location when determining equality, instead comparing up to free-identifier=?, but attempts to reconstruct source locations and syntax properties in the generated syntax object.

If either old-marker or new-marker is a procedure?, then it is in essence a macro that will transformer node instead of inserting a a literal as a sibling in the syntax object. The marker procedure must return a syntax object that represents a list.

Examples:

> (stx-diff
   #'(define (f x) (+ (* x 2) 1))
   #'(define (f x) (- (* x 2) 3 1)))
#<syntax:eval:92:13 ((define (f x) (#:new - #:old + (* x 2) #:new 3 1)))>
> (stx-diff
   #'(define (f x) (+ (* x 2) 4 1))
   #'(define (f x) (- (* x 2) 5 3 1)))
#<syntax:eval:95:13 ((define (f x) (#:new - #:old + (* x 2) #:new 5 #:new 3 #:old 4 1)))>
> (stx-diff
   #'((1) 2 3 4)
   #'([1] 2 2 4))
#<syntax:eval:103:14 (((1) #:new 2 2 #:old 3 4))>
> (define x1 #'((1) 2 3 4))
> (define x2 #'([1] 2 2 4))
> x1
#<syntax:eval:104:24 ((1) 2 3 4)>
> x2
#<syntax:eval:105:24 ((1) 2 2 4)>
> (syntax-parse (stx-diff x1 x2)
    [((any ...))
     (map (lambda (x)
            (format "~a:~a" (syntax-line x) (syntax-column x)))
          (attribute any))])
'("105:25" "#f:#f" "105:29" "105:31" "#f:#f" "104:31" "105:33")
> (syntax-parse (stx-diff x1 x2)
    [((head any ...))
     (syntax-property #'head 'paren-shape)])
#\[