Re: diff and patch

On Tue, 17 Jun 2025 22:36:55 -0000 (UTC), Rich wrote:

Mark Summerfield <m.n.summerfield@gmail.com> wrote:

I want these functions:
 
    proc diff {old new} -> # diff data "ddata"
    proc patch {old ddata} -> # new
 
where old and new are strings.
 
I thought the Tcllib's rcs module could do this but I can't figure it
out.
 
Is this possible using the rcs module or using the struct::list
module's LCS functions?

 
The core of the diff algorithm is LCS.  You want the LCS functions from
struct::list.
 
But, you don't get a "diff" from the LCS procs, you get the LCS data,
you then have to convert that into a "diff" format of your choice.
 
You likely want to look at the various "diff in tcl" pages on the wiki.
A starting point: https://wiki.tcl-lang.org/page/diff+in+Tcl

As far as I can see the rcs module depends on an external diff tool
whereas I want to do everything in Tcl.

I have come up with two functions but unfortunately they only work for
some examples and not others. The problem when it occurs at all happens in
the 'added' case.

I've made a repo of it: https://github.com/mark-summerfield/diffpatch

The file diffpatch-1.tm contains `lcs_diff {old_list new_list}` which
returns a `delta` (a list of lists) and `lcs_patch {old_list delta}` which
is supposed to return `new_list` but sometimes fails.

The file `test_diffpatch.tcl` has 4 old-new pairs of lists and shows what
happens and what goes wrong.

As far as I can tell the problem is that when adding (inserting) the index
to insert at is sometimes right and sometimes wrong but I don't know how
to fix this.

Here are the functions (I still don't know how to make them appear as code
in the newsreader), i.e., what's in diffpatch-1.tcl:

```

    # returns a delta (a list of lists) which can be passed to lcs_patch
    proc lcs_diff {old_lst new_lst} {
        set lcs [::struct::list longestCommonSubsequence $old_lst
$new_lst]
        set delta [list]
        foreach d [::struct::list lcsInvert $lcs [llength $old_lst] \
                                                [llength $new_lst]] {
            lassign $d what left right
            switch $what {
                added {lappend delta [list i [lindex $left 0] \
                                            [lrange $new_lst {*}$right]]}
                deleted {lappend delta [list d $left]}
                changed {lappend delta [list r $left \
                                            [lrange $new_lst {*}$right]]}
            }
        }
        return $delta
    }

    # given old_lst and an lcs_diff delta reconstructs and returns new_lst
    proc lcs_patch {old_lst delta} {
        set new_lst [lmap x $old_lst {expr {$x}}]
        foreach d $delta {
            lassign $d what left right
            #puts "DEBUG what='$what' left='$left' right='$right'"
            switch $what {
                i {set new_lst [linsert $new_lst $left {*}$right]}
                d {set new_lst [lremove $new_lst {*}$left]}
                r {set new_lst [lreplace $new_lst {*}$left {*}$right]}
            }
        }
        return $new_lst
    }

```

here's what's in `test_diffpatch.tcl`:

```

tcl::tm::path add [file normalize [file dirname [info script]]]

package require diffpatch
package require struct::list 1

proc test1 {} {
    set debug [expr {!$::argc}]
    lcs_check a $::ax $::ay $debug
    lcs_check b $::bx $::by $debug
    lcs_check c $::cx $::cy $debug
    lcs_check d $::dx $::dy $debug
}

proc lcs_check {name x y debug} {
    set delta [lcs_diff $x $y]
    set z [lcs_patch $x $delta]
    if {$debug} {
        puts "${name} ######################"
        puts "${name}x={$x}\n${name}y={$y}\ndelta={$delta}\n${name}z={$z}"
    }
    if {[struct::list equal $y $z]} {
        puts "***** OK   ${name}y == ${name}z *****"
    } else {
        puts "***** FAIL ${name}y != ${name}z *****"
    }
}

set ax {foo bar baz quux}
set ay {foo baz bar quux}
set bx {q a b x c d}
set by {a b y c d f}
set cx {the quick brown fox jumped over the lazy dogs}
set cy {the quick red fox jumped over the very busy dogs}
set dx {private Thread currentThread;}
set dy {private volatile Thread currentThread;}

test1

```

and here's the output:

```
$ ./test_diffpatch.tcl

a ######################
ax={foo bar baz quux}
ay={foo baz bar quux}
delta={{d {1 1}} {i 2 bar}}
az={foo baz bar quux}
***** OK   ay == az *****

b ######################
bx={q a b x c d}
by={a b y c d f}
delta={{d {0 0}} {r {3 3} y} {i 5 f}}
bz={a b x y d f}
***** FAIL by != bz *****

c ######################
cx={the quick brown fox jumped over the lazy dogs}
cy={the quick red fox jumped over the very busy dogs}
delta={{r {2 2} red} {r {7 7} {very busy}}}
cz={the quick red fox jumped over the very busy dogs}
***** OK   cy == cz *****

d ######################
dx={private Thread currentThread;}
dy={private volatile Thread currentThread;}
delta={{i 0 volatile}}
dz={volatile private Thread {currentThread;}}
***** FAIL dy != dz *****


```