implement Diff; # diff - differential file comparison## Uses an algorithm due to Harold Stone, which finds# a pair of longest identical subsequences in the two# files.## The major goal is to generate the match vector J.# J[i] is the index of the line in file1 corresponding# to line i file0. J[i] = 0 if there is no# such line in file1.## Lines are hashed so as to work in core. All potential# matches are located by sorting the lines of each file# on the hash (called value). In particular, this# collects the equivalence classes in file1 together.# Subroutine equiv replaces the value of each line in# file0 by the index of the first element of its # matching equivalence in (the reordered) file1.# To save space equiv squeezes file1 into a single# array member in which the equivalence classes# are simply concatenated, except that their first# members are flagged by changing sign.## Next the indices that point into member are unsorted into# array class according to the original order of file0.## The cleverness lies in routine stone. This marches# through the lines of file0, developing a vector klist# of "k-candidates". At step i a k-candidate is a matched# pair of lines x,y (x in file0 y in file1) such that# there is a common subsequence of lenght k# between the first i lines of file0 and the first y # lines of file1, but there is no such subsequence for# any smaller y. x is the earliest possible mate to y# that occurs in such a subsequence.## Whenever any of the members of the equivalence class of# lines in file1 matable to a line in file0 has serial number # less than the y of some k-candidate, that k-candidate # with the smallest such y is replaced. The new # k-candidate is chained (via pred) to the current# k-1 candidate so that the actual subsequence can# be recovered. When a member has serial number greater# that the y of all k-candidates, the klist is extended.# At the end, the longest subsequence is pulled out# and placed in the array J by unravel.## With J in hand, the matches there recorded are# check'ed against reality to assure that no spurious# matches have crept in due to hashing. If they have,# they are broken, and "jackpot " is recorded--a harmless# matter except that a true match for a spuriously# mated line may now be unnecessarily reported as a change.## Much of the complexity of the program comes simply# from trying to minimize core utilization and# maximize the range of doable problems by dynamically# allocating what is needed and reusing what is not.# The core requirements for problems larger than somewhat# are (in words) 2*length(file0) + length(file1) +# 3*(number of k-candidates installed), typically about# 6n words for files of length n. ## include "sys.m"; sys: Sys; include "bufio.m"; bufio : Bufio;Iobuf : import bufio; include "draw.m"; draw: Draw;include "readdir.m"; readdir : Readdir;include "string.m"; str : String;include "arg.m"; Diff : module { init: fn(ctxt: ref Draw->Context, argv: list of string);}; stderr: ref Sys->FD; mode : int; # '\0', 'e', 'f', 'h' bflag : int; # ignore multiple and trailing blanks rflag : int; # recurse down directory trees mflag : int; # pseudo flag: doing multiple files, one dir REG,BIN: con iota; HALFINT : con 16;Usage : con "usage: diff [ -efbwr ] file1 ... file2"; cand : adt { x : int; y : int; pred : int;}; line : adt { serial : int; value : int;}; out : ref Iobuf;file := array[2] of array of line;sfile := array[2] of array of line; # shortened by pruning common prefix and suffixslen := array[2] of int;ilen := array[2] of int;pref, suff, clen : int; # length of prefix and suffixfirstchange : int;clist : array of cand; # merely a free storage pot for candidatesJ : array of int; # will be overlaid on classixold, ixnew : array of int;input := array[2] of ref Iobuf ;file1, file2 : string;tmpname := array[] of {"/tmp/diff1", "/tmp/diff2"};whichtmp : int;anychange := 0; init(nil: ref Draw->Context, args: list of string){ sys = load Sys Sys->PATH; stderr = sys->fildes(2); draw = load Draw Draw->PATH; bufio = load Bufio Bufio->PATH; readdir = load Readdir Readdir->PATH; str = load String String->PATH; if (bufio==nil) fatal(sys->sprint("cannot load %s: %r", Bufio->PATH)); if (readdir==nil) fatal(sys->sprint("cannot load %s: %r", Readdir->PATH)); if (str==nil) fatal(sys->sprint("cannot load %s: %r", String->PATH)); arg := load Arg Arg->PATH; if (arg==nil) fatal(sys->sprint("cannot load %s: %r", Arg->PATH)); fsb, tsb : Sys->Dir; arg->init(args); while((o := arg->opt()) != 0) case o { 'e' or 'f' => mode = o; 'w' => bflag = 2; 'b' => bflag = 1; 'r' => rflag = 1; 'm' => mflag = 1; * => fatal(Usage); } tmp := arg->argv(); arg = nil; j := len tmp; if (j < 2) fatal(Usage); arr := array[j] of string; for(i:=0;i<j;i++){ arr[i]= hd tmp; tmp = tl tmp; } (i,tsb)=sys->stat(arr[j-1]); if (i == -1) fatal(sys->sprint("can't stat %s: %r", arr[j-1])); if (j > 2) { if (!(tsb.qid.qtype&Sys->QTDIR)) fatal(Usage); mflag = 1; } else { (i,fsb)=sys->stat(arr[0]); if (i == -1) fatal(sys->sprint("can't stat %s: %r", arr[0])); if ((fsb.qid.qtype&Sys->QTDIR) && (tsb.qid.qtype&Sys->QTDIR)) mflag = 1; } out=bufio->fopen(sys->fildes(1),Bufio->OWRITE); for (i = 0; i < j-1; i++) { diff(arr[i], arr[j-1], 0); rmtmpfiles(); } rmtmpfiles(); out.flush(); if (anychange) raise "fail:some";} ############################# diffreg from here .... # shellsort CACM #201 sort(a : array of line, n : int){ w : line; m := 0; for (i := 1; i <= n; i *= 2) m = 2*i - 1; for (m /= 2; m != 0; m /= 2) { for (j := 1; j <= n-m ; j++) { ai:=j; aim:=j+m; do { if (a[aim].value > a[ai].value || a[aim].value == a[ai].value && a[aim].serial > a[ai].serial) break; w = a[ai]; a[ai] = a[aim]; a[aim] = w; aim=ai; ai-=m; } while (ai > 0 && aim >= ai); } }} unsort(f : array of line, l : int) : array of int { i : int; a := array[l+1] of int; for(i=1;i<=l;i++) a[f[i].serial] = f[i].value; return a;} prune() { for(pref=0;pref< ilen[0]&&pref< ilen[1]&& file[0][pref+1].value==file[1][pref+1].value; pref++ ) ; for(suff=0;suff< ilen[0]-pref&&suff< ilen[1]-pref&& file[0][ilen[0]-suff].value==file[1][ilen[1]-suff].value; suff++) ; for(j:=0;j<2;j++) { sfile[j] = file[j][pref:]; slen[j]= ilen[j]-pref-suff; for(i:=0;i<=slen[j];i++) sfile[j][i].serial = i; }} equiv(a: array of line, n:int , b: array of line, m: int, c : array of int) { i := 1; j := 1; while(i<=n && j<=m) { if(a[i].value < b[j].value) a[i++].value = 0; else if(a[i].value == b[j].value) a[i++].value = j; else j++; } while(i <= n) a[i++].value = 0; b[m+1].value = 0; # huh ? j = 1; while(j <= m) { c[j] = -b[j].serial; while(b[j+1].value == b[j].value) { j++; c[j] = b[j].serial; } j++; } c[j] = -1;} newcand(x, y, pred : int) : int { if (clen==len clist){ q := array[clen*2] of cand; q[0:]=clist; clist= array[clen*2] of cand; clist[0:]=q; q=nil; } clist[clen].x=x; clist[clen].y=y; clist[clen].pred=pred; return clen++;} search(c : array of int, k,y : int) : int { if(clist[c[k]].y < y) # quick look for typical case return k+1; i := 0; j := k+1; while((l:=(i+j)/2) > i) { t := clist[c[l]].y; if(t > y) j = l; else if(t < y) i = l; else return l; } return l+1;} stone(a : array of int ,n : int, b: array of int , c : array of int) : int { oldc, oldl, tc, l ,y : int; k := 0; c[0] = newcand(0,0,0); for(i:=1; i<=n; i++) { j := a[i]; if(j==0) continue; y = -b[j]; oldl = 0; oldc = c[0]; do { if(y <= clist[oldc].y) continue; l = search(c, k, y); if(l!=oldl+1) oldc = c[l-1]; if(l<=k) { if(clist[c[l]].y <= y) continue; tc = c[l]; c[l] = newcand(i,y,oldc); oldc = tc; oldl = l; } else { c[l] = newcand(i,y,oldc); k++; break; } } while((y=b[j+=1]) > 0); } return k;} unravel(p : int) { for(i:=0; i<=ilen[0]; i++) { if (i <= pref) J[i] = i; else if (i > ilen[0]-suff) J[i] = i+ ilen[1]-ilen[0]; else J[i] = 0; } for(q:=clist[p];q.y!=0;q=clist[q.pred]) J[q.x+pref] = q.y+pref;} output() { i1: int; m := ilen[0]; J[0] = 0; J[m+1] = ilen[1]+1; if (mode != 'e') { for (i0 := 1; i0 <= m; i0 = i1+1) { while (i0 <= m && J[i0] == J[i0-1]+1) i0++; j0 := J[i0-1]+1; i1 = i0-1; while (i1 < m && J[i1+1] == 0) i1++; j1 := J[i1+1]-1; J[i1] = j1; change(i0, i1, j0, j1); } } else { for (i0 := m; i0 >= 1; i0 = i1-1) { while (i0 >= 1 && J[i0] == J[i0+1]-1 && J[i0]) i0--; j0 := J[i0+1]-1; i1 = i0+1; while (i1 > 1 && J[i1-1] == 0) i1--; j1 := J[i1-1]+1; J[i1] = j1; change(i1 , i0, j1, j0); } } if (m == 0) change(1, 0, 1, ilen[1]); out.flush();} diffreg(f,t : string) { k : int; (b0, b0type) := prepare(0, f); if (b0==nil) return; (b1, b1type) := prepare(1, t); if (b1==nil) { b0=nil; return; } if (b0type == BIN || b1type == BIN) { if (cmp(b0, b1)) { out.puts(sys->sprint("Binary files %s %s differ\n", f, t)); anychange = 1; } b0 = nil; b1 = nil; return; } clen=0; prune(); file[0]=nil; file[1]=nil; sort(sfile[0],slen[0]); sort(sfile[1],slen[1]); member := array[slen[1]+2] of int; equiv(sfile[0], slen[0],sfile[1],slen[1], member); class:=unsort(sfile[0],slen[0]); sfile[0]=nil; sfile[1]=nil; klist := array[slen[0]+2] of int; clist = array[1] of cand; k = stone(class, slen[0], member, klist); J = array[ilen[0]+2] of int; unravel(klist[k]); clist=nil; klist=nil; class=nil; member=nil; ixold = array[ilen[0]+2] of int; ixnew = array[ilen[1]+2] of int; b0.seek(big 0, 0); b1.seek(big 0, 0); check(b0, b1); output(); ixold=nil; ixnew=nil; b0=nil; b1=nil; } ######################## diffio starts here... # hashing has the effect of# arranging line in 7-bit bytes and then# summing 1-s complement in 16-bit hunks readhash(bp : ref Iobuf) : int { sum := 1; shift := 0; buf := bp.gets('\n'); if (buf == nil) return 0; buf = buf[0:len buf -1]; p := 0; case bflag { # various types of white space handling 0 => while (p< len buf) { sum += (buf[p] << (shift &= (HALFINT-1))); p++; shift += 7; } 1 => # coalesce multiple white-space for (space := 0; p< len buf; p++) { if (buf[p]==' ' || buf[p]=='\t') { space++; continue; } if (space) { shift += 7; space = 0; } sum += (buf[p] << (shift &= (HALFINT-1))); p++; shift += 7; } * => # strip all white-space while (p< len buf) { if (buf[p]==' ' || buf[p]=='\t') { p++;Lines 1–500 of 854. Load more
implement Diff; # diff - differential file comparison # # Uses an algorithm due to Harold Stone, which finds # a pair of longest identical subsequences in the two # files. # # The major goal is to generate the match vector J. # J[i] is the index of the line in file1 corresponding # to line i file0. J[i] = 0 if there is no # such line in file1. # # Lines are hashed so as to work in core. All potential # matches are located by sorting the lines of each file # on the hash (called value). In particular, this # collects the equivalence classes in file1 together. # Subroutine equiv replaces the value of each line in # file0 by the index of the first element of its # matching equivalence in (the reordered) file1. # To save space equiv squeezes file1 into a single # array member in which the equivalence classes # are simply concatenated, except that their first # members are flagged by changing sign. # # Next the indices that point into member are unsorted into # array class according to the original order of file0. # # The cleverness lies in routine stone. This marches # through the lines of file0, developing a vector klist # of "k-candidates". At step i a k-candidate is a matched # pair of lines x,y (x in file0 y in file1) such that # there is a common subsequence of lenght k # between the first i lines of file0 and the first y # lines of file1, but there is no such subsequence for # any smaller y. x is the earliest possible mate to y # that occurs in such a subsequence. # # Whenever any of the members of the equivalence class of # lines in file1 matable to a line in file0 has serial number # less than the y of some k-candidate, that k-candidate # with the smallest such y is replaced. The new # k-candidate is chained (via pred) to the current # k-1 candidate so that the actual subsequence can # be recovered. When a member has serial number greater # that the y of all k-candidates, the klist is extended. # At the end, the longest subsequence is pulled out # and placed in the array J by unravel. # # With J in hand, the matches there recorded are # check'ed against reality to assure that no spurious # matches have crept in due to hashing. If they have, # they are broken, and "jackpot " is recorded--a harmless # matter except that a true match for a spuriously # mated line may now be unnecessarily reported as a change. # # Much of the complexity of the program comes simply # from trying to minimize core utilization and # maximize the range of doable problems by dynamically # allocating what is needed and reusing what is not. # The core requirements for problems larger than somewhat # are (in words) 2*length(file0) + length(file1) + # 3*(number of k-candidates installed), typically about # 6n words for files of length n. # # include "sys.m"; sys: Sys; include "bufio.m"; bufio : Bufio; Iobuf : import bufio; include "draw.m"; draw: Draw; include "readdir.m"; readdir : Readdir; include "string.m"; str : String; include "arg.m"; Diff : module { init: fn(ctxt: ref Draw->Context, argv: list of string); }; stderr: ref Sys->FD; mode : int; # '\0', 'e', 'f', 'h' bflag : int; # ignore multiple and trailing blanks rflag : int; # recurse down directory trees mflag : int; # pseudo flag: doing multiple files, one dir REG, BIN: con iota; HALFINT : con 16; Usage : con "usage: diff [ -efbwr ] file1 ... file2"; cand : adt { x : int; y : int; pred : int; }; line : adt { serial : int; value : int; }; out : ref Iobuf; file := array[2] of array of line; sfile := array[2] of array of line; # shortened by pruning common prefix and suffix slen := array[2] of int; ilen := array[2] of int; pref, suff, clen : int; # length of prefix and suffix firstchange : int; clist : array of cand; # merely a free storage pot for candidates J : array of int; # will be overlaid on class ixold, ixnew : array of int; input := array[2] of ref Iobuf ; file1, file2 : string; tmpname := array[] of {"/tmp/diff1", "/tmp/diff2"}; whichtmp : int; anychange := 0; init(nil: ref Draw->Context, args: list of string) { sys = load Sys Sys->PATH; stderr = sys->fildes(2); draw = load Draw Draw->PATH; bufio = load Bufio Bufio->PATH; readdir = load Readdir Readdir->PATH; str = load String String->PATH; if (bufio==nil) fatal(sys->sprint("cannot load %s: %r", Bufio->PATH)); if (readdir==nil) fatal(sys->sprint("cannot load %s: %r", Readdir->PATH)); if (str==nil) fatal(sys->sprint("cannot load %s: %r", String->PATH)); arg := load Arg Arg->PATH; if (arg==nil) fatal(sys->sprint("cannot load %s: %r", Arg->PATH)); fsb, tsb : Sys->Dir; arg->init(args); while((o := arg->opt()) != 0) case o { 'e' or 'f' => mode = o; 'w' => bflag = 2; 'b' => bflag = 1; 'r' => rflag = 1; 'm' => mflag = 1; * => fatal(Usage); } tmp := arg->argv(); arg = nil; j := len tmp; if (j < 2) fatal(Usage); arr := array[j] of string; for(i:=0;i<j;i++){ arr[i]= hd tmp; tmp = tl tmp; } (i,tsb)=sys->stat(arr[j-1]); if (i == -1) fatal(sys->sprint("can't stat %s: %r", arr[j-1])); if (j > 2) { if (!(tsb.qid.qtype&Sys->QTDIR)) fatal(Usage); mflag = 1; } else { (i,fsb)=sys->stat(arr[0]); if (i == -1) fatal(sys->sprint("can't stat %s: %r", arr[0])); if ((fsb.qid.qtype&Sys->QTDIR) && (tsb.qid.qtype&Sys->QTDIR)) mflag = 1; } out=bufio->fopen(sys->fildes(1),Bufio->OWRITE); for (i = 0; i < j-1; i++) { diff(arr[i], arr[j-1], 0); rmtmpfiles(); } rmtmpfiles(); out.flush(); if (anychange) raise "fail:some"; } ############################# diffreg from here .... # shellsort CACM #201 sort(a : array of line, n : int) { w : line; m := 0; for (i := 1; i <= n; i *= 2) m = 2*i - 1; for (m /= 2; m != 0; m /= 2) { for (j := 1; j <= n-m ; j++) { ai:=j; aim:=j+m; do { if (a[aim].value > a[ai].value || a[aim].value == a[ai].value && a[aim].serial > a[ai].serial) break; w = a[ai]; a[ai] = a[aim]; a[aim] = w; aim=ai; ai-=m; } while (ai > 0 && aim >= ai); } } } unsort(f : array of line, l : int) : array of int { i : int; a := array[l+1] of int; for(i=1;i<=l;i++) a[f[i].serial] = f[i].value; return a; } prune() { for(pref=0;pref< ilen[0]&&pref< ilen[1]&& file[0][pref+1].value==file[1][pref+1].value; pref++ ) ; for(suff=0;suff< ilen[0]-pref&&suff< ilen[1]-pref&& file[0][ilen[0]-suff].value==file[1][ilen[1]-suff].value; suff++) ; for(j:=0;j<2;j++) { sfile[j] = file[j][pref:]; slen[j]= ilen[j]-pref-suff; for(i:=0;i<=slen[j];i++) sfile[j][i].serial = i; } } equiv(a: array of line, n:int , b: array of line, m: int, c : array of int) { i := 1; j := 1; while(i<=n && j<=m) { if(a[i].value < b[j].value) a[i++].value = 0; else if(a[i].value == b[j].value) a[i++].value = j; else j++; } while(i <= n) a[i++].value = 0; b[m+1].value = 0; # huh ? j = 1; while(j <= m) { c[j] = -b[j].serial; while(b[j+1].value == b[j].value) { j++; c[j] = b[j].serial; } j++; } c[j] = -1; } newcand(x, y, pred : int) : int { if (clen==len clist){ q := array[clen*2] of cand; q[0:]=clist; clist= array[clen*2] of cand; clist[0:]=q; q=nil; } clist[clen].x=x; clist[clen].y=y; clist[clen].pred=pred; return clen++; } search(c : array of int, k,y : int) : int { if(clist[c[k]].y < y) # quick look for typical case return k+1; i := 0; j := k+1; while((l:=(i+j)/2) > i) { t := clist[c[l]].y; if(t > y) j = l; else if(t < y) i = l; else return l; } return l+1; } stone(a : array of int ,n : int, b: array of int , c : array of int) : int { oldc, oldl, tc, l ,y : int; k := 0; c[0] = newcand(0,0,0); for(i:=1; i<=n; i++) { j := a[i]; if(j==0) continue; y = -b[j]; oldl = 0; oldc = c[0]; do { if(y <= clist[oldc].y) continue; l = search(c, k, y); if(l!=oldl+1) oldc = c[l-1]; if(l<=k) { if(clist[c[l]].y <= y) continue; tc = c[l]; c[l] = newcand(i,y,oldc); oldc = tc; oldl = l; } else { c[l] = newcand(i,y,oldc); k++; break; } } while((y=b[j+=1]) > 0); } return k; } unravel(p : int) { for(i:=0; i<=ilen[0]; i++) { if (i <= pref) J[i] = i; else if (i > ilen[0]-suff) J[i] = i+ ilen[1]-ilen[0]; else J[i] = 0; } for(q:=clist[p];q.y!=0;q=clist[q.pred]) J[q.x+pref] = q.y+pref; } output() { i1: int; m := ilen[0]; J[0] = 0; J[m+1] = ilen[1]+1; if (mode != 'e') { for (i0 := 1; i0 <= m; i0 = i1+1) { while (i0 <= m && J[i0] == J[i0-1]+1) i0++; j0 := J[i0-1]+1; i1 = i0-1; while (i1 < m && J[i1+1] == 0) i1++; j1 := J[i1+1]-1; J[i1] = j1; change(i0, i1, j0, j1); } } else { for (i0 := m; i0 >= 1; i0 = i1-1) { while (i0 >= 1 && J[i0] == J[i0+1]-1 && J[i0]) i0--; j0 := J[i0+1]-1; i1 = i0+1; while (i1 > 1 && J[i1-1] == 0) i1--; j1 := J[i1-1]+1; J[i1] = j1; change(i1 , i0, j1, j0); } } if (m == 0) change(1, 0, 1, ilen[1]); out.flush(); } diffreg(f,t : string) { k : int; (b0, b0type) := prepare(0, f); if (b0==nil) return; (b1, b1type) := prepare(1, t); if (b1==nil) { b0=nil; return; } if (b0type == BIN || b1type == BIN) { if (cmp(b0, b1)) { out.puts(sys->sprint("Binary files %s %s differ\n", f, t)); anychange = 1; } b0 = nil; b1 = nil; return; } clen=0; prune(); file[0]=nil; file[1]=nil; sort(sfile[0],slen[0]); sort(sfile[1],slen[1]); member := array[slen[1]+2] of int; equiv(sfile[0], slen[0],sfile[1],slen[1], member); class:=unsort(sfile[0],slen[0]); sfile[0]=nil; sfile[1]=nil; klist := array[slen[0]+2] of int; clist = array[1] of cand; k = stone(class, slen[0], member, klist); J = array[ilen[0]+2] of int; unravel(klist[k]); clist=nil; klist=nil; class=nil; member=nil; ixold = array[ilen[0]+2] of int; ixnew = array[ilen[1]+2] of int; b0.seek(big 0, 0); b1.seek(big 0, 0); check(b0, b1); output(); ixold=nil; ixnew=nil; b0=nil; b1=nil; } ######################## diffio starts here... # hashing has the effect of # arranging line in 7-bit bytes and then # summing 1-s complement in 16-bit hunks readhash(bp : ref Iobuf) : int { sum := 1; shift := 0; buf := bp.gets('\n'); if (buf == nil) return 0; buf = buf[0:len buf -1]; p := 0; case bflag { # various types of white space handling 0 => while (p< len buf) { sum += (buf[p] << (shift &= (HALFINT-1))); p++; shift += 7; } 1 => # coalesce multiple white-space for (space := 0; p< len buf; p++) { if (buf[p]==' ' || buf[p]=='\t') { space++; continue; } if (space) { shift += 7; space = 0; } sum += (buf[p] << (shift &= (HALFINT-1))); p++; shift += 7; } * => # strip all white-space while (p< len buf) { if (buf[p]==' ' || buf[p]=='\t') { p++;