diff options
author | Brian Gaeke <gaeke@uiuc.edu> | 2004-04-12 22:53:24 +0000 |
---|---|---|
committer | Brian Gaeke <gaeke@uiuc.edu> | 2004-04-12 22:53:24 +0000 |
commit | 0df5f9fb7ebd0d4e8e068d642587e9d036f00885 (patch) | |
tree | 1262636c286a51243dec57747d034cd2d05ec989 | |
parent | 5f0b51547ca71f496208ac23b92481132efa0def (diff) |
Add the Spiff fp-aware diff utility from Bellcore
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12875 91177308-0d34-0410-b5e6-96231b3b80d8
38 files changed, 6986 insertions, 0 deletions
diff --git a/utils/Spiff/LICENSE.TXT b/utils/Spiff/LICENSE.TXT new file mode 100644 index 0000000000..8684d4047d --- /dev/null +++ b/utils/Spiff/LICENSE.TXT @@ -0,0 +1,18 @@ +The copyright below applies to Spiff 1.0 as redistributed as part of LLVM +and/or its test suite. + +------------------------------------------------------------------------------ + +COPYRIGHT + +Our lawyers advise the following: + + Copyright (c) 1988 Bellcore + All Rights Reserved + Permission is granted to copy or use this program, EXCEPT that it + may not be sold for profit, the copyright notice must be reproduced + on copies, and credit should be given to Bellcore where it is due. + BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM. + +Given that all of the above seems to be very reasonable, there should be no +reason for anyone to not play by the rules. diff --git a/utils/Spiff/Makefile b/utils/Spiff/Makefile new file mode 100644 index 0000000000..c0fd230156 --- /dev/null +++ b/utils/Spiff/Makefile @@ -0,0 +1,6 @@ +LEVEL = ../.. +TOOLNAME = spiff + +include $(LEVEL)/Makefile.common + +CPPFLAGS += -DATT -DNOCHATTER diff --git a/utils/Spiff/README b/utils/Spiff/README new file mode 100644 index 0000000000..e559b500f3 --- /dev/null +++ b/utils/Spiff/README @@ -0,0 +1,264 @@ +INSTALLATION + 1) Change makefile settings to reflect + ATT vs. BSD software + termio vs. termcap + MGR vs. no MGR (MGR is a BELLCORE produced + window manager that is also available + free to the public.) + 2) Then, just say "make". + If you want to "make install", you should first + change definition of INSDIR in the makefile + + 3) to test the software say + + spiff Sample.1 Sample.2 + + spiff should find 4 differences and + you should see the words "added", "deleted", "changed", + and "altered" as well as four number in stand-out mode. + + spiff Sample.1 Sample.2 | cat + + should produce the same output, only the differences + should be underlined However, on many terminals the underlining + does not appear. So try the command + + spiff Sample.1 Sample.2 | cat -v + + or whatever the equivalent to cat -v is on your system. + + A more complicated test set is found in Sample.3 and Sample.4 + These files show how to use embedded commands to do things + like change the commenting convention and tolerances on the + fly. Be sure to run the command with the -s option to spiff: + + spiff -s 'command spiffword' Sample.3 Sample.4 + + These files by no means provide an exhaustive test of + spiff's features. But they should give you some idea if things + are working right. + + This code (or it's closely related cousins) has been run on + Vaxen running 4.3BSD, a CCI Power 6, some XENIX machines, and some + other machines running System V derivatives as well as + (thanks to eugene@ames.arpa) Cray, Amdahl and Convex machines. + + 4) Share and enjoy. + +AUTHOR'S ADDRESS + Please send complaints, comments, praise, bug reports, etc to + Dan Nachbar + Bell Communications Research (also known as BELLCORE) + 445 South St. Room 2B-389 + Morristown, NJ 07960 + + nachbar@bellcore.com + or + bellcore!nachbar + or + (201) 829-4392 (praise only, please) + +OVERVIEW OF OPERATION + +Each of two input files is read and stored in core. +Then it is parsed into a series of tokens (literal strings and +floating point numbers, white space is ignored). +The token sequences are stored in core as well. +After both files have been parsed, a differencing algorithm is applied to +the token sequences. The differencing algorithm +produces an edit script, which is then passed to an output routine. + +SIZE LIMITS AND OTHER DEFAULTS + file implementing limit name default value +maximum number of lines lines.h _L_MAXLINES 10000 + per file +maximum number of tokens token.h K_MAXTOKENS 50000 + per file +maximum line length misc.h Z_LINELEN 1024 +maximum word length misc.h Z_WORDLEN 20 + (length of misc buffers for + things like literal + delimiters. + NOT length of tokens which + can be virtually any length) +default absolute tolerance tol.h _T_ADEF "1e-10" +default relative tolerance tol.h _T_RDEF "1e-10" +maximum number of commands command.h _C_CMDMAX 100 + in effect at one time +maximum number of commenting comment.h W_COMMAX 20 + conventions that can be + in effect at one time + (not including commenting + conventions that are + restricted to beginning + of line) +maximum number of commenting comment.h W_BOLMAX 20 + conventions that are + restricted to beginning of + line that are in effect at + one time +maximum number of literal comment.h W_LITMAX 20 + string conventions that + can be in effect at one time +maximum number of tolerances tol.h _T_TOLMAX 10 + that can be in effect at one + time + + +DIFFERENCES BETWEEN THE CURRENT VERSION AND THE ENCLOSED PAPER + +The files paper.ms and paper.out contain the nroff -ms input and +output respectively of a paper on spiff that was given the Summer '88 +USENIX conference in San Francisco. Since that time many changes +have been made to the code. Many flags have changed and some have +had their meanings reversed, see the enclosed man page for the current +usage. Also, there is no longer control over the +granularity of object used when applying the differencing algorithm. +The current version of spiff always applies the differencing +in terms of individual tokens. The -t flag controls how the edit script +is printed. This arrangement more closely reflects the original intent +of having multiple differencing granularities. + +PERFORMANCE + +Spiff is big and slow. It is big because all the storage is +in core. It is a straightforward but boring task to move the temporary +storage into a file. Someone who cares is invited to take on the job. +Spiff is slow because whenever a choice had to be made between +speed of operation and ease of coding, speed of operation almost always lost. +As the program matures it will almost certainly get smaller and faster. +Obvious performance enhancements have been avoided in order to make the +program available as soon as possible. + +COPYRIGHT + +Our lawyers advise the following: + + Copyright (c) 1988 Bellcore + All Rights Reserved + Permission is granted to copy or use this program, EXCEPT that it + may not be sold for profit, the copyright notice must be reproduced + on copies, and credit should be given to Bellcore where it is due. + BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM. + +Given that all of the above seems to be very reasonable, there should be no +reason for anyone to not play by the rules. + + +NAMING CONVENTIONS USED IN THE CODE + +All symbols (functions, data declarations, macros) are named as follows: + + L_foo -- for names exported to other modules + and possibly used inside the module as well. + _L_foo -- for names used by more than one routine + within a module + foo -- for names used inside a single routine. + +Each module uses a different value for "L" -- + module files letter used implements + spiff.c Y top level routines + misc.[ch] Z various routines used throughout + strings.[ch] S routines for handling strings + edit.h E list of changes found and printed + tol.[ch] T tolerances for real numbers + token.[ch] K storage for objects + float.[ch] F manipulation of floats + floatrep.[ch] R representation of floats + line.[ch] L storage for input lines + parse.[ch] P parse for input files + command.[ch] C storage and recognition of commands + comment.[ch] W comment list maintenance + compare.[ch] X comparisons of a single token + exact.[ch] Q exact match differencing algorithm + miller.[ch] G miller/myers differencing algorithm + output.[ch] O print listing of differences + flagdefs.h U define flag bits that are used in + several of the other modules. + These #defines could have been + included in misc.c, but were separated + out because of their explicit + communication function. + visual.[ch] V screen oriented display for MGR + window manager, also contains + dummy routines for people who don't + have MGR + +I haven't cleaned up visual.c yet. It probably doesn't even compile +in this version anyway. But since most people don't have mgr, this +isn't urgent. + +NON-OBVIOUS DATA STRUCTURES + +The Floating Point Representation + +Floating point numbers are stored in a struct R_flstr +The fractional part is often called the mantissa. + +The structure consists of + a flag for the sign of the factional part + the exponent in binary + a character string containing the fractional part + +The structure could be converted to a float via + atof(strcat(".",mantissa)) * (10^exponent) + +To be properly formed, the mantissa string must: + start with a digit between 1 and 9 (i.e. no leading zeros) + except for the zero, in which case the mantissa is exactly "0" + for the special case of zero, the exponent is always 0, and the + sign is always positive. (i.e. no negative 0) + +In other words, (except for the value 0) +the mantissa is a fractional number ranging +between 0.1 (inclusive) and 1.0 (exclusive). +The exponent is interpreted as a power of 10. + +Lines +there are three sets of lines: +implemented in line.c and line.h + real_lines -- + the lines as they come from the file + content_lines -- + a subset of reallines that excluding embedded commands +implemented in token.c and token.h + token_lines -- + a subset of content_lines consisting of those lines that + have tokens that begin on them (literals can go on for + more than one line) + i.e. content_lines excluding comments and blank lines. + + +THE STATE OF THE CODE +Things that should be added + visual mode should handle tabs and wrapped lines + handling huge files in chunks when in using the ordinal match + algorithm. right now you have to parse and then diff the + whole thing before you get any output. often, you run out of memory. + +Things that would be nice to add + output should optionally be expressed in real line numbers + (i.e. including command lines) + at present, all storage is in core. there should + be a compile time decision to allow temporary storage + in files rather than core. + that way the user could decide how to handle the + speed/space tradeoff + a front end that looked like diff should be added so that + one could drop spiff into existing shell scripts + the parser converts floats into their internal form even when + it isn't necessary. + in the miller/myer code, the code should check for matching + end sequences. it currently looks matching beginning + sequences. + +Minor programming improvements (programming botches) + some of the #defines should really be enumerated types + all the routines in strings.c that alter the data at the end of + a pointer but return void should just return the correct + data. the current arrangement is a historical artifact + of the days when these routines returned a status code. + but then the code was never examined, + so i made them void . . . + comments should be added to the miller/myer code + in visual mode, ask for font by name rather than number diff --git a/utils/Spiff/command.c b/utils/Spiff/command.c new file mode 100644 index 0000000000..6c9da47ac9 --- /dev/null +++ b/utils/Spiff/command.c @@ -0,0 +1,193 @@ +/* Copyright (c) 1988 Bellcore +** All Rights Reserved +** Permission is granted to copy or use this program, EXCEPT that it +** may not be sold for profit, the copyright notice must be reproduced +** on copies, and credit should be given to Bellcore where it is due. +** BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM. +*/ + + +#ifndef lint +static char rcsid[]= "$Header$"; +#endif + + +#include "misc.h" +#include "tol.h" +#include "comment.h" +#include "command.h" +#include "strings.h" +#include "parse.h" + +/* +** storage for the string that signals an embedded command +*/ +static char _C_cmdword[Z_WORDLEN]; + +/* +** storage for the command script +*/ +static int _C_nextcmd = 0; +static char *_C_cmds[_C_CMDMAX]; + + +/* +** add a string to the command buffer +*/ +void +C_addcmd(str) +char *str; +{ + S_savestr(&_C_cmds[_C_nextcmd++],str); + return; +} + +/* +** execute a single command +*/ +static void +_C_do_a_cmd(str) +char *str; +{ + /* + ** place holder for the beginning of the string + */ + char *beginning = str; + + S_skipspace(&str); + + /* + ** set the command string to allow embedded commands + */ + if (!S_wordcmp(str,"command")) + { + S_nextword(&str); + if (strlen(str) >= Z_WORDLEN) + { + Z_fatal("command word is too long"); + } + S_wordcpy(_C_cmdword,str); + } + /* + ** set the tolerances + */ + else if (!S_wordcmp(str,"tol")) + { + S_nextword(&str); + T_tolline(str); + } + /* + ** add a comment specification + */ + else if (!S_wordcmp(str,"comment")) + { + S_nextword(&str); + if (strlen(str) >= Z_WORDLEN) + { + Z_fatal("command word is too long"); + } + W_addcom(str,0); + } + else if (!S_wordcmp(str,"nestcom")) + { + S_nextword(&str); + if (strlen(str) >= Z_WORDLEN) + { + Z_fatal("command word is too long"); + } + W_addcom(str,1); + } + /* + ** add a literal string specification + */ + else if (!S_wordcmp(str,"literal")) + { + S_nextword(&str); + if (strlen(str) >= Z_WORDLEN) + { + Z_fatal("command word is too long"); + } + W_addlit(str); + } + else if (!S_wordcmp(str,"resetcomments")) + { + W_clearcoms(); + } + else if (!S_wordcmp(str,"resetliterals")) + { + W_clearlits(); + } + else if (!S_wordcmp(str,"beginchar")) + { + S_nextword(&str); + W_setbolchar(*str); + } + else if (!S_wordcmp(str,"endchar")) + { + S_nextword(&str); + W_seteolchar(*str); + } + else if (!S_wordcmp(str,"addalpha")) + { + S_nextword(&str); + P_addalpha(str); + } + else if ((0 == strlen(str)) || !S_wordcmp(str,"rem") + || ('#' == *str)) + { + /* do nothing */ + } + else + { + (void) sprintf(Z_err_buf, + "don't understand command %s\n", + beginning); + Z_fatal(Z_err_buf); + } + return; +} + +/* +** execute the commands in the command buffer +*/ +void +C_docmds() +{ + int i; + for (i=0;i<_C_nextcmd;i++) + { + _C_do_a_cmd(_C_cmds[i]); + } + return; +} + +/* +** disable embedded command key word recognition +*/ +void +C_clear_cmd() +{ + _C_cmdword[0] = '\0'; + return; +} + +#define inline spiff_inline +int +C_is_cmd(inline) +char *inline; +{ + char *ptr; + /* + ** see if this is a command line + ** and if so, do the command right away + */ + if (('\0' != _C_cmdword[0]) && (!S_wordcmp(inline,_C_cmdword))) + { + ptr = inline; + S_nextword(&ptr); + _C_do_a_cmd(ptr); + return(1); + } + return(0); +} + diff --git a/utils/Spiff/command.h b/utils/Spiff/command.h new file mode 100644 index 0000000000..2fa0723ef5 --- /dev/null +++ b/utils/Spiff/command.h @@ -0,0 +1,18 @@ +/* Copyright (c) 1988 Bellcore +** All Rights Reserved +** Permission is granted to copy or use this program, EXCEPT that it +** may not be sold for profit, the copyright notice must be reproduced +** on copies, and credit should be given to Bellcore where it is due. +** BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM. +*/ + +#ifndef C_INCLUDED +extern int C_is_cmd(); +extern void C_clear_cmd(); +extern void C_addcmd(); +extern void C_docmds(); + +#define _C_CMDMAX 100 + +#define C_INCLUDED +#endif diff --git a/utils/Spiff/comment.c b/utils/Spiff/comment.c new file mode 100644 index 0000000000..f9a3827589 --- /dev/null +++ b/utils/Spiff/comment.c @@ -0,0 +1,307 @@ +/* Copyright (c) 1988 Bellcore +** All Rights Reserved +** Permission is granted to copy or use this program, EXCEPT that it +** may not be sold for profit, the copyright notice must be reproduced +** on copies, and credit should be given to Bellcore where it is due. +** BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM. +*/ + + +#ifndef lint +static char rcsid[]= "$Header$"; +#endif + + +#include "misc.h" +#include "comment.h" +#include "strings.h" + +/* +** storage for the comment specifiers that can appear +** anywhere on a line +*/ +static int _W_nextcom = 0; +_W_comstruct _W_coms[_W_COMMAX]; + +/* +** storage for comment specifiers that are examined only at the +** beginning of each line +*/ +static int _W_nextbol = 0; +_W_bolstruct _W_bols[_W_BOLMAX]; + +/* +** storage for delimiters of literal strings +*/ +static int _W_nextlit = 0; +_W_litstruct _W_lits[_W_LITMAX]; + +/* +** storage for characters to specify beginning and end of line +** in the comment and literal commands +*/ +char _W_bolchar = '^'; +char _W_eolchar = '$'; + + +/* +** build up a list of comment delimiters +*/ +void +W_addcom(str,nestflag) +char *str; +int nestflag; +{ + /* + ** check for comments that begin at the beginning of line + */ + if (*str == _W_bolchar) + { + if (_W_nextbol >= _W_BOLMAX) + Z_fatal("too many beginning of line comment delimiter sets"); + + str++; /*skip the bol char */ + S_wordcpy(_W_bols[_W_nextbol].begin,str); + + S_nextword(&str); + + if (*str == _W_eolchar) + { + (void) strcpy(_W_bols[_W_nextbol].end,"\n"); + } + else + { + S_wordcpy(_W_bols[_W_nextbol].end,str); + } + + S_nextword(&str); + S_wordcpy(_W_bols[_W_nextbol].escape,str); + + /* + ** + */ + if (nestflag) + Z_complain("begining of line comment won't nest"); + + _W_nextbol++; + } + else + { + if (_W_nextcom >= _W_COMMAX) + Z_fatal("too many comment delimiter sets"); + + S_wordcpy(_W_coms[_W_nextcom].begin,str); + + S_nextword(&str); + + if (*str == _W_eolchar) + { + (void) strcpy(_W_coms[_W_nextbol].end,"\n"); + } + else + { + S_wordcpy(_W_coms[_W_nextbol].end,str); + } + + S_nextword(&str); + S_wordcpy(_W_coms[_W_nextcom].escape,str); + + _W_coms[_W_nextcom].nestbit = nestflag; + + _W_nextcom++; + } + return; +} + + +/* +** clear the comment delimiter storage +*/ +void +W_clearcoms() +{ + _W_nextcom = 0; + _W_nextbol = 0; + return; +} + +/* +** build up the list of literal delimiters +*/ +void +W_addlit(str) +char *str; +{ + if (_W_nextlit >= _W_LITMAX) + Z_fatal("too many literal delimiter sets"); + + S_wordcpy(_W_lits[_W_nextlit].begin,str); + + S_nextword(&str); + S_wordcpy(_W_lits[_W_nextlit].end,str); + + S_nextword(&str); + S_wordcpy(_W_lits[_W_nextlit].escape,str); + + _W_nextlit++; + return; +} + +/* +** clear the literal delimiter storage +*/ +void +W_clearlits() +{ + _W_nextlit = 0; + return; +} + + + +static _W_bolstruct bol_scratch; + +static void +_W_copybol(to,from) +W_bol to,from; +{ + (void) strcpy(to->begin,from->begin); + (void) strcpy(to->end,from->end); + (void) strcpy(to->escape,from->escape); +} + +W_bol +W_isbol(str) +char *str; +{ + int i; + + for(i=0;i<_W_nextbol;i++) + { + if(!S_wordcmp(str,_W_bols[i].begin)) + { + _W_copybol(&bol_scratch,&_W_bols[i]); + return(&bol_scratch); + } + } + return(W_BOLNULL); +} + +W_is_bol(ptr) +W_bol ptr; +{ + int i; + + for(i=0;i<_W_nextbol;i++) + { + if(!S_wordcmp(ptr->begin,_W_bols[i].begin) && + !S_wordcmp(ptr->end,_W_bols[i].end) && + !S_wordcmp(ptr->escape,_W_bols[i].escape)) + { + return(1); + } + + } + return(0); +} + + +static _W_litstruct lit_scratch; + +static void +_W_copylit(to,from) +W_lit to,from; +{ + (void) strcpy(to->begin,from->begin); + (void) strcpy(to->end,from->end); + (void) strcpy(to->escape,from->escape); +} + +W_lit +W_islit(str) +char *str; +{ + int i; + + for(i=0;i<_W_nextlit;i++) + { + if(!S_wordcmp(str,_W_lits[i].begin)) + { + _W_copylit(&lit_scratch,&_W_lits[i]); + return(&lit_scratch); + } + } + return(W_LITNULL); +} + +W_is_lit(ptr) +W_lit ptr; +{ + int i; + + for(i=0;i<_W_nextlit;i++) + { + if(!S_wordcmp(ptr->begin,_W_lits[i].begin) && + !S_wordcmp(ptr->end,_W_lits[i].end) && + !S_wordcmp(ptr->escape,_W_lits[i].escape)) + { + return(1); + } + + } + return(0); +} + +static _W_comstruct com_scratch; + +static void +_W_copycom(to,from) +W_com to,from; +{ + (void) strcpy(to->begin,from->begin); + (void) strcpy(to->end,from->end); + (void) strcpy(to->escape,from->escape); + to->nestbit = from->nestbit; +} + +W_com +W_iscom(str) +char *str; +{ + int i; + + for(i=0;i<_W_nextcom;i++) + { + if(!S_wordcmp(str,_W_coms[i].begin)) + { + _W_copycom(&com_scratch,&_W_coms[i]); + return(&com_scratch); + } + } + return(W_COMNULL); +} + +W_is_com(ptr) +W_com ptr; +{ + int i; + + for(i=0;i<_W_nextcom;i++) + { + if(!S_wordcmp(ptr->begin,_W_coms[i].begin) && + !S_wordcmp(ptr->end,_W_coms[i].end) && + !S_wordcmp(ptr->escape,_W_coms[i].escape) && + ptr->nestbit == _W_coms[i].nestbit) + { + return(1); + } + + } + return(0); +} + +W_is_nesting(ptr) +W_com ptr; +{ + return(ptr->nestbit); +} diff --git a/utils/Spiff/comment.h b/utils/Spiff/comment.h new file mode 100644 index 0000000000..01d8423021 --- /dev/null +++ b/utils/Spiff/comment.h @@ -0,0 +1,84 @@ +/* Copyright (c) 1988 Bellcore +** All Rights Reserved +** Permission is granted to copy or use this program, EXCEPT that it +** may not be sold for profit, the copyright notice must be reproduced +** on copies, and credit should be given to Bellcore where it is due. +** BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM. +*/ + +#ifndef W_INCLUDED + +#include <stdio.h> + +#define _W_COMWORD 16 +#define _W_COMMAX 20 +#define _W_BOLMAX 20 +#define _W_LITMAX 20 + +/* +** these three data structures used to be much +** different. eventually, the differences +** have disappeared as the code has evolved. +** obviously, they should now be collapsed. +** someday . . . +*/ +typedef struct { + char begin[_W_COMWORD]; + char end[_W_COMWORD]; + char escape[_W_COMWORD]; +} _W_bolstruct, *W_bol; + +typedef struct { + char begin[_W_COMWORD]; + char end[_W_COMWORD]; + char escape[_W_COMWORD]; + int nestbit; +} _W_comstruct, *W_com; + +typedef struct { + char begin[_W_COMWORD]; + char end[_W_COMWORD]; + char escape[_W_COMWORD]; +} _W_litstruct, *W_lit; + +#define W_bolbegin(ptr) (ptr->begin) +#define W_bolend(ptr) (ptr->end) +#define W_bolescape(ptr) (ptr->escape) + +#define W_litbegin(ptr) (ptr->begin) +#define W_litend(ptr) (ptr->end) +#define W_litescape(ptr) (ptr->escape) + +#define W_combegin(ptr) (ptr->begin) +#define W_comend(ptr) (ptr->end) +#define W_comescape(ptr) (ptr->escape) + +extern char _W_bolchar; +extern char _W_eolchar; + +#define W_setbolchar(x) (_W_bolchar = x) +#define W_seteolchar(x) (_W_eolchar = x) + +extern W_bol W_isbol(); +extern W_lit W_islit(); +extern W_com W_iscom(); + +extern int W_is_bol(); +extern int W_is_lit(); +extern int W_is_com(); + +extern _W_bolstruct _W_bols[]; +extern _W_litstruct _W_lits[]; +extern _W_comstruct _W_coms[]; + +extern void W_clearcoms(); +extern void W_clearlits(); +extern void W_addcom(); +extern void W_addlit(); + +#define W_BOLNULL ((W_bol)0) +#define W_COMNULL ((W_com)0) +#define W_LITNULL ((W_lit)0) + +#define W_INCLUDED +#endif diff --git a/utils/Spiff/compare.c b/utils/Spiff/co |