blob: 8c1d7793c906a7317b739be9636ffa2a1f59ff84 [file] [log] [blame]
/*
* Copyright (c) 2018 Oracle and/or its affiliates. All rights reserved.
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License v. 2.0, which is available at
* http://www.eclipse.org/legal/epl-2.0.
*
* This Source Code may also be made available under the following Secondary
* Licenses when the conditions for such availability set forth in the
* Eclipse Public License v. 2.0 are satisfied: GNU General Public License,
* version 2 with the GNU Classpath Exception, which is available at
* https://www.gnu.org/software/classpath/license.html.
*
* SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
*/
// Diff -- text file difference utility.
package com.sun.ejte.ccl.filediff;
import java.io.*;
//import com.sun.ejte.ccl.reporter.*;
/** This is the info kept per-file. */
class fileInfo {
static final int MAXLINECOUNT = 20000;
DataInputStream file; /* File handle that is open for read. */
public int maxLine; /* After input done, # lines in file. */
node symbol[]; /* The symtab handle of each line. */
int other[]; /* Map of line# to line# in other file */
/* ( -1 means don't-know ). */
/* Allocated AFTER the lines are read. */
/**
* Normal constructor with one filename; file is opened and saved.
*/
fileInfo( String filename ) {
symbol = new node [ MAXLINECOUNT+2 ];
other = null; // allocated later!
try {
file = new DataInputStream(
new FileInputStream( filename));
} catch (IOException e) {
System.err.println("Diff can't read file " +
filename );
System.err.println("Error Exception was:" + e );
System.exit(1);
}
}
// This is done late, to be same size as # lines in input file.
void alloc() {
other = new int[symbol.length + 2];
}
};
/**
* USAGE: diff oldfile newfile
*
* This program assumes that "oldfile" and "newfile" are text files.
* The program writes to stdout a description of the changes which would
* transform "oldfile" into "newfile".
*
* The printout is in the form of commands, each followed by a block of
* text. The text is delimited by the commands, which are:
*
* DELETE AT n
* ..deleted lines
*
* INSERT BEFORE n
* ..inserted lines
*
* n MOVED TO BEFORE n
* ..moved lines
*
* n CHANGED FROM
* ..old lines
* CHANGED TO
* ..newer lines
*
* The line numbers all refer to the lines of the oldfile, as they are
* numbered before any commands are applied.
* The text lines are printed as-is, without indentation or prefixing. The
* commands are printed in upper case, with a prefix of ">>>>", so that
* they will stand out. Other schemes may be preferred.
* Files which contain more than MAXLINECOUNT lines cannot be processed.
* This can be fixed by changing "symbol" to a Vector.
* Ignoring I/O, and ignoring the symbol table, it should take O(N) time.
* This implementation takes fixed space, plus O(U) space for the symbol
* table (where U is the number of unique lines). Methods exist to change
* the fixed space to O(N) space.
*/
public class Diff {
/** block len > any possible real block len */
final int UNREAL=Integer.MAX_VALUE;
// private static SimpleReporterAdapter stat=new SimpleReporterAdapter();
/** Keeps track of information about file1 and file2 */
fileInfo oldinfo, newinfo;
/** blocklen is the info about found blocks. It will be set to 0, except
* at the line#s where blocks start in the old file. At these places it
* will be set to the # of lines in the block. During printout ,
* this # will be reset to -1 if the block is printed as a MOVE block
* (because the printout phase will encounter the block twice, but
* must only print it once.)
* The array declarations are to MAXLINECOUNT+2 so that we can have two
* extra lines (pseudolines) at line# 0 and line# MAXLINECOUNT+1
* (or less).
*/
int blocklen[];
/**
* main - entry point when used standalone.
* NOTE: no routines return error codes or throw any local
* exceptions. Instead, any routine may complain
* to stderr and then exit with error to the system.
*/
public static void main(String argstrings[])
{
if ( argstrings.length != 2 ) {
System.err.println("Usage: diff oldfile newfile" );
System.exit(1);
}
Diff d = new Diff();
d.doDiff(argstrings[0], argstrings[1]);
return;
}
/** Construct a Diff object. */
Diff() {
}
/** Do one file comparison. Called with both filenames. */
public void doDiff(String oldFile, String newFile) {
//stat.addDescription("This is test suite for AVK");
println( ">>>> Difference of file \"" + oldFile +
"\" and file \"" + newFile + "\".\n");
oldinfo = new fileInfo(oldFile);
newinfo = new fileInfo(newFile);
/* we don't process until we know both files really do exist. */
try {
inputscan( oldinfo );
inputscan( newinfo );
} catch (IOException e) {
System.err.println("Read error: " + e);
}
/* Now that we've read all the lines, allocate some arrays.
*/
blocklen = new int[ (oldinfo.maxLine>newinfo.maxLine?
oldinfo.maxLine : newinfo.maxLine) + 2 ];
oldinfo.alloc();
newinfo.alloc();
/* Now do the work, and print the results. */
transform();
printout();
//stat.printSummary("appverificationID");
}
/**
* inputscan Reads the file specified by pinfo.file.
* --------- Places the lines of that file in the symbol table.
* Sets pinfo.maxLine to the number of lines found.
*/
void inputscan( fileInfo pinfo ) throws IOException
{
String linebuffer;
pinfo.maxLine = 0;
while ((linebuffer = pinfo.file.readLine()) != null) {
storeline( linebuffer, pinfo );
}
}
/**
* storeline Places line into symbol table.
* --------- Expects pinfo.maxLine initted: increments.
* Places symbol table handle in pinfo.ymbol.
* Expects pinfo is either oldinfo or newinfo.
*/
void storeline( String linebuffer, fileInfo pinfo )
{
int linenum = ++pinfo.maxLine; /* note, no line zero */
if ( linenum > fileInfo.MAXLINECOUNT ) {
System.err.println( "MAXLINECOUNT exceeded, must stop." );
System.exit(1);
}
pinfo.symbol[ linenum ] =
node.addSymbol( linebuffer, pinfo == oldinfo, linenum );
}
/*
* transform
* Analyzes the file differences and leaves its findings in
* the global arrays oldinfo.other, newinfo.other, and blocklen.
* Expects both files in symtab.
* Expects valid "maxLine" and "symbol" in oldinfo and newinfo.
*/
void transform()
{
int oldline, newline;
int oldmax = oldinfo.maxLine + 2; /* Count pseudolines at */
int newmax = newinfo.maxLine + 2; /* ..front and rear of file */
for (oldline=0; oldline < oldmax; oldline++ )
oldinfo.other[oldline]= -1;
for (newline=0; newline < newmax; newline++ )
newinfo.other[newline]= -1;
scanunique(); /* scan for lines used once in both files */
scanafter(); /* scan past sure-matches for non-unique blocks */
scanbefore(); /* scan backwards from sure-matches */
scanblocks(); /* find the fronts and lengths of blocks */
}
/*
* scanunique
* Scans for lines which are used exactly once in each file.
* Expects both files in symtab, and oldinfo and newinfo valid.
* The appropriate "other" array entries are set to the line# in
* the other file.
* Claims pseudo-lines at 0 and XXXinfo.maxLine+1 are unique.
*/
void scanunique()
{
int oldline, newline;
node psymbol;
for( newline = 1; newline <= newinfo.maxLine; newline++ ) {
psymbol = newinfo.symbol[ newline ];
if ( psymbol.symbolIsUnique()) { // 1 use in each file
oldline = psymbol.linenum;
newinfo.other[ newline ] = oldline; // record 1-1 map
oldinfo.other[ oldline ] = newline;
}
}
newinfo.other[ 0 ] = 0;
oldinfo.other[ 0 ] = 0;
newinfo.other[ newinfo.maxLine + 1 ] = oldinfo.maxLine + 1;
oldinfo.other[ oldinfo.maxLine + 1 ] = newinfo.maxLine + 1;
}
/*
* scanafter
* Expects both files in symtab, and oldinfo and newinfo valid.
* Expects the "other" arrays contain positive #s to indicate
* lines that are unique in both files.
* For each such pair of places, scans past in each file.
* Contiguous groups of lines that match non-uniquely are
* taken to be good-enough matches, and so marked in "other".
* Assumes each other[0] is 0.
*/
void scanafter()
{
int oldline, newline;
for( newline = 0; newline <= newinfo.maxLine; newline++ ) {
oldline = newinfo.other[ newline ];
if ( oldline >= 0 ) { /* is unique in old & new */
for(;;) { /* scan after there in both files */
if ( ++oldline > oldinfo.maxLine ) break;
if ( oldinfo.other[ oldline ] >= 0 ) break;
if ( ++newline > newinfo.maxLine ) break;
if ( newinfo.other[ newline ] >= 0 ) break;
/* oldline & newline exist, and
aren't already matched */
if ( newinfo.symbol[ newline ] !=
oldinfo.symbol[ oldline ] ) break; // not same
newinfo.other[newline] = oldline; // record a match
oldinfo.other[oldline] = newline;
}
}
}
}
/**
* scanbefore
* As scanafter, except scans towards file fronts.
* Assumes the off-end lines have been marked as a match.
*/
void scanbefore()
{
int oldline, newline;
for( newline = newinfo.maxLine + 1; newline > 0; newline-- ) {
oldline = newinfo.other[ newline ];
if ( oldline >= 0 ) { /* unique in each */
for(;;) {
if ( --oldline <= 0 ) break;
if ( oldinfo.other[ oldline ] >= 0 ) break;
if ( --newline <= 0 ) break;
if ( newinfo.other[ newline ] >= 0 ) break;
/* oldline and newline exist,
and aren't marked yet */
if ( newinfo.symbol[ newline ] !=
oldinfo.symbol[ oldline ] ) break; // not same
newinfo.other[newline] = oldline; // record a match
oldinfo.other[oldline] = newline;
}
}
}
}
/**
* scanblocks - Finds the beginnings and lengths of blocks of matches.
* Sets the blocklen array (see definition).
* Expects oldinfo valid.
*/
void scanblocks()
{
int oldline, newline;
int oldfront = 0; // line# of front of a block in old, or 0
int newlast = -1; // newline's value during prev. iteration
for( oldline = 1; oldline <= oldinfo.maxLine; oldline++ )
blocklen[ oldline ] = 0;
blocklen[ oldinfo.maxLine + 1 ] = UNREAL; // starts a mythical blk
for( oldline = 1; oldline <= oldinfo.maxLine; oldline++ ) {
newline = oldinfo.other[ oldline ];
if ( newline < 0 ) oldfront = 0; /* no match: not in block */
else{ /* match. */
if ( oldfront == 0 ) oldfront = oldline;
if ( newline != (newlast+1)) oldfront = oldline;
++blocklen[ oldfront ];
}
newlast = newline;
}
}
/* The following are global to printout's subsidiary routines */
// enum{ idle, delete, insert, movenew, moveold,
// same, change } printstatus;
public static final int
idle = 0, delete = 1, insert = 2, movenew = 3, moveold = 4,
same = 5, change = 6;
int printstatus;
boolean anyprinted;
int printoldline, printnewline; // line numbers in old & new file
/**
* printout - Prints summary to stdout.
* Expects all data structures have been filled out.
*/
void printout()
{
printstatus = idle;
anyprinted = false;
for( printoldline = printnewline = 1; ; ) {
if ( printoldline > oldinfo.maxLine ) { newconsume(); break;}
if ( printnewline > newinfo.maxLine ) { oldconsume(); break;}
if ( newinfo.other[ printnewline ] < 0 ) {
if ( oldinfo.other[ printoldline ] < 0 )
showchange();
else
showinsert();
}
else if ( oldinfo.other[ printoldline ] < 0 )
showdelete();
else if ( blocklen[ printoldline ] < 0 )
skipold();
else if ( oldinfo.other[ printoldline ] == printnewline )
showsame();
else
showmove();
}
if ( anyprinted == true )
{
println( ">>>> End of differences." );
//stat.addStatus("appverification bookstore", stat.FAIL);
}
else
{
println( ">>>> Files are identical." );
//stat.addStatus("appverification bookstore", stat.PASS);
}
}
/*
* newconsume Part of printout. Have run out of old file.
* Print the rest of the new file, as inserts and/or moves.
*/
void newconsume()
{
for(;;) {
if ( printnewline > newinfo.maxLine )
break; /* end of file */
if ( newinfo.other[ printnewline ] < 0 ) showinsert();
else showmove();
}
}
/**
* oldconsume Part of printout. Have run out of new file.
* Process the rest of the old file, printing any
* parts which were deletes or moves.
*/
void oldconsume()
{
for(;;) {
if ( printoldline > oldinfo.maxLine )
break; /* end of file */
printnewline = oldinfo.other[ printoldline ];
if ( printnewline < 0 ) showdelete();
else if ( blocklen[ printoldline ] < 0 ) skipold();
else showmove();
}
}
/**
* showdelete Part of printout.
* Expects printoldline is at a deletion.
*/
void showdelete()
{
if ( printstatus != delete )
{
println("Following test didn't get run-------->");
//println( ">>>>>>>>>>>>>>>>> DELETE AT " + printoldline);
}
printstatus = delete;
oldinfo.symbol[ printoldline ].showSymbol();
anyprinted = true;
printoldline++;
}
/*
* showinsert Part of printout.
* Expects printnewline is at an insertion.
*/
void showinsert()
{
if ( printstatus == change ) println( ">>>>>>>>>>>>> CHANGED TO" );
else if ( printstatus != insert )
println( ">>>>>>>>>>>>>>>> INSERT BEFORE " + printoldline );
printstatus = insert;
newinfo.symbol[ printnewline ].showSymbol();
anyprinted = true;
printnewline++;
}
/**
* showchange Part of printout.
* Expects printnewline is an insertion.
* Expects printoldline is a deletion.
*/
void showchange()
{
if ( printstatus != change )
println( ">>>>>>>>>>>>>>>>>>>>> " + printoldline + " CHANGED FROM");
printstatus = change;
oldinfo.symbol[ printoldline ].showSymbol();
anyprinted = true;
printoldline++;
}
/**
* skipold Part of printout.
* Expects printoldline at start of an old block that has
* already been announced as a move.
* Skips over the old block.
*/
void skipold()
{
printstatus = idle;
for(;;) {
if ( ++printoldline > oldinfo.maxLine )
break; /* end of file */
if ( oldinfo.other[ printoldline ] < 0 )
break; /* end of block */
if ( blocklen[ printoldline ]!=0)
break; /* start of another */
}
}
/**
* skipnew Part of printout.
* Expects printnewline is at start of a new block that has
* already been announced as a move.
* Skips over the new block.
*/
void skipnew()
{
int oldline;
printstatus = idle;
for(;;) {
if ( ++printnewline > newinfo.maxLine )
break; /* end of file */
oldline = newinfo.other[ printnewline ];
if ( oldline < 0 )
break; /* end of block */
if ( blocklen[ oldline ] != 0)
break; /* start of another */
}
}
/**
* showsame Part of printout.
* Expects printnewline and printoldline at start of
* two blocks that aren't to be displayed.
*/
void showsame()
{
int count;
printstatus = idle;
if ( newinfo.other[ printnewline ] != printoldline ) {
System.err.println("BUG IN LINE REFERENCING");
System.exit(1);
}
count = blocklen[ printoldline ];
printoldline += count;
printnewline += count;
}
/**
* showmove Part of printout.
* Expects printoldline, printnewline at start of
* two different blocks ( a move was done).
*/
void showmove()
{
int oldblock = blocklen[ printoldline ];
int newother = newinfo.other[ printnewline ];
int newblock = blocklen[ newother ];
if ( newblock < 0 ) skipnew(); // already printed.
else if ( oldblock >= newblock ) { // assume new's blk moved.
blocklen[newother] = -1; // stamp block as "printed".
println( ">>>> " + newother +
" THRU " + (newother + newblock - 1) +
" MOVED TO BEFORE " + printoldline );
for( ; newblock > 0; newblock--, printnewline++ )
newinfo.symbol[ printnewline ].showSymbol();
anyprinted = true;
printstatus = idle;
} else /* assume old's block moved */
skipold(); /* target line# not known, display later */
}
/** Convenience wrapper for println */
public void println(String s) {
System.out.println(s);
}
}; // end of main class!
/**
* Class "node". The symbol table routines in this class all
* understand the symbol table format, which is a binary tree.
* The methods are: addSymbol, symbolIsUnique, showSymbol.
*/
class node{ /* the tree is made up of these nodes */
node pleft, pright;
int linenum;
static final int freshnode = 0,
oldonce = 1, newonce = 2, bothonce = 3, other = 4;
int /* enum linestates */ linestate;
String line;
static node panchor = null; /* symtab is a tree hung from this */
/**
* Construct a new symbol table node and fill in its fields.
* @param string A line of the text file
*/
node( String pline)
{
pleft = pright = null;
linestate = freshnode;
/* linenum field is not always valid */
line = pline;
}
/**
* matchsymbol Searches tree for a match to the line.
* @param String pline, a line of text
* If node's linestate == freshnode, then created the node.
*/
static node matchsymbol( String pline )
{
int comparison;
node pnode = panchor;
if ( panchor == null ) return panchor = new node( pline);
for(;;) {
comparison = pnode.line.compareTo(pline);
if ( comparison == 0 ) return pnode; /* found */
if ( comparison < 0 ) {
if ( pnode.pleft == null ) {
pnode.pleft = new node( pline);
return pnode.pleft;
}
pnode = pnode.pleft;
}
if ( comparison > 0 ) {
if ( pnode.pright == null ) {
pnode.pright = new node( pline);
return pnode.pright;
}
pnode = pnode.pright;
}
}
/* NOTE: There are return stmts, so control does not get here. */
}
/**
* addSymbol(String pline) - Saves line into the symbol table.
* Returns a handle to the symtab entry for that unique line.
* If inoldfile nonzero, then linenum is remembered.
*/
static node addSymbol( String pline, boolean inoldfile, int linenum )
{
node pnode;
pnode = matchsymbol( pline ); /* find the node in the tree */
if ( pnode.linestate == freshnode ) {
pnode.linestate = inoldfile ? oldonce : newonce;
} else {
if (( pnode.linestate == oldonce && !inoldfile ) ||
( pnode.linestate == newonce && inoldfile ))
pnode.linestate = bothonce;
else pnode.linestate = other;
}
if (inoldfile) pnode.linenum = linenum;
return pnode;
}
/**
* symbolIsUnique Arg is a ptr previously returned by addSymbol.
* -------------- Returns true if the line was added to the
* symbol table exactly once with inoldfile true,
* and exactly once with inoldfile false.
*/
boolean symbolIsUnique()
{
return (linestate == bothonce );
}
/**
* showSymbol Prints the line to stdout.
*/
void showSymbol()
{
System.out.println(line);
}
}