| /* |
| * Copyright (c) 2017, 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); |
| } |
| } |
