/*   Copyright 2004 The Apache Software Foundation
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package tools.util;

// Diff -- text file difference utility.
// See full docu-comment at beginning of Diff class.

// $Id$

import java.io.*;
import java.util.Vector;

/**
 * This is the info kept per-file.
 */
class fileInfo
{

    static final int MAXLINECOUNT = 20000;

    //DataInputStream file;	/* File handle that is open for read.  */
    File file;
    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
     * Tests whether file actually exists
     */
    fileInfo(String filename)
    {
        symbol = new node[MAXLINECOUNT + 2];
        other = null;		// allocated later!
        file = new File(filename);
    }

    // This is done late, to be same size as # lines in input file.
    void alloc()
    {
        other = new int[symbol.length + 2];
    }
}

;

/**
 * diff         Text file difference utility.
 * ----         Copyright 1987, 1989 by Donald C. Lindsay,
 * School of Computer Science,  Carnegie Mellon University.
 * Copyright 1982 by Symbionics.
 * Use without fee is permitted when not for direct commercial
 * advantage, and when credit to the source is given. Other uses
 * require specific permission.
 *
 * Converted from C to Java by Ian F. Darwin, ian@darwinsys.com, January, 1997.
 * Copyright 1997, Ian F. Darwin.
 *
 * Conversion is NOT FULLY TESTED.
 *
 * 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.
 * The algorithm is taken from Communications of the ACM, Apr78 (21, 4, 264-),
 * "A Technique for Isolating Differences Between Files."
 * 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.
 * Note that this is not the only interesting file-difference algorithm. In
 * general, different algorithms draw different conclusions about the
 * changes that have been made to the oldfile. This algorithm is sometimes
 * "more right", particularly since it does not consider a block move to be
 * an insertion and a (separate) deletion. However, on some files it will be
 * "less right". This is a consequence of the fact that files may contain
 * many identical lines (particularly if they are program source). Each
 * algorithm resolves the ambiguity in its own way, and the resolution
 * is never guaranteed to be "right". However, it is often excellent.
 * This program is intended to be pedagogic.  Specifically, this program was
 * the basis of the Literate Programming column which appeared in the
 * Communications of the ACM (CACM), in the June 1989 issue (32, 6,
 * 740-755).
 * By "pedagogic", I do not mean that the program is gracefully worded, or
 * that it showcases language features or its algorithm. I also do not mean
 * that it is highly accessible to beginners, or that it is intended to be
 * read in full, or in a particular order. Rather, this program is an
 * example of one professional's style of keeping things organized and
 * maintainable.
 * The program would be better if the "print" variables were wrapped into
 * a struct. In general, grouping related variables in this way improves
 * documentation, and adds the ability to pass the group in argument lists.
 * This program is a de-engineered version of a program which uses less
 * memory and less time.  The article points out that the "symbol" arrays
 * can be implemented as arrays of pointers to arrays, with dynamic
 * allocation of the subarrays.  (In C, macros are very useful for hiding
 * the two-level accesses.) In Java, a Vector would be used. This allows an
 * extremely large value for MAXLINECOUNT, without dedicating fixed arrays.
 * (The "other" array can be allocated after the input phase, when the exact
 * sizes are known.) The only slow piece of code is the "strcmp" in the tree
 * descent: it can be speeded up by keeping a hash in the tree node, and
 * only using "strcmp" when two hashes happen to be equal.
 *
 * Change Log
 * ----------
 * 1Jan97 Ian F. Darwin: first working rewrite in Java, based entirely on
 * D.C.Lindsay's reasonable C version.
 * Changed comments from /***************** to /**, shortened, added
 * whitespace, used tabs more, etc.
 * 6jul89 D.C.Lindsay, CMU: fixed portability bug. Thanks, Gregg Wonderly.
 * Just changed "char ch" to "int ch".
 * Also added comment about way to improve code.
 * 10jun89 D.C.Lindsay, CMU: posted version created.
 * Copyright notice changed to ACM style, and Dept. is now School.
 * ACM article referenced in docn.
 * 26sep87 D.C.Lindsay, CMU: publication version created.
 * Condensed all 1982/83 change log entries.
 * Removed all command line options, and supporting code. This
 * simplified the input code (no case reduction etc). It also
 * simplified the symbol table, which was capable of remembering
 * offsets into files (instead of strings), and trusting (!) hash
 * values to be unique.
 * Removed dynamic allocation of arrays: now fixed static arrays.
 * Removed speed optimizations in symtab package.
 * Removed string compression/decompression code.
 * Recoded to Unix standards from old Lattice/MSDOS standards.
 * (This affected only the #include's and the IO.)
 * Some renaming of variables, and rewording of comments.
 * 1982/83 D.C.Lindsay, Symbionics: created.
 *
 * @author	Ian F. Darwin, Java version
 * @version	Java version 0.9, 1997
 * @author	D. C. Lindsay, C version (1982-1987)
 */
public class Diff
{

    /**
     * block len > any possible real block len
     */
    final int UNREAL = Integer.MAX_VALUE;

    /**
     * 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[];

    /**
     * Controls how trailing whitespace lines is handled
     */
    boolean trimLines;

    /**
     * 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(false);
        d.doDiff(argstrings[0], argstrings[1]);
        return;
    }

    /**
     * Construct a Diff object.
     */
    public Diff(boolean trimLines)
    {
        this.trimLines = trimLines;
    }

    /**
     * Construct a Diff object.
     */
    public Diff()
    {
        this.trimLines = false;
    }

    /**
     * Do one file comparison. Called with both filenames.
     */
    public void doDiff(String oldFile, String newFile)
    {
        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();
    }

    public String compareFiles(String oldFile, String newFile)
        throws IOException
    {
        //println("Diff of \"" + oldFile + "\" and \"" + newFile);
        oldinfo = new fileInfo(oldFile);
        newinfo = new fileInfo(newFile);
        /* we don't process until we know both files really do exist. */
        inputscan(oldinfo);
        inputscan(newinfo);

        /* 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();
        return printout();
    }


    /**
     * 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
    {
        pinfo.maxLine = 0;

        BufferedReader reader = new BufferedReader(new FileReader(pinfo.file));
        Vector v = new Vector();

        while (true)
        {
            String s = reader.readLine();
            if (s == null) break;
            v.addElement(s);
        }
        reader.close();
        // Discard all trailing lines that are only whitespaces..
        if (trimLines)
        {
            int i = v.size();
            while (--i >= 0)
                if (Util.isWhiteSpace((String) v.get(i)))
                    v.removeElementAt(i);
        }

        int i = 0;
        while (i < v.size())
            storeline((String) v.get(i++), 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.
     */
    String printout()
    {
        printstatus = idle;
        anyprinted = false;
        PrintStream _sysout = System.out;
        _sysout.flush();
        String ret;
        try
        {
            ByteArrayOutputStream bout = new ByteArrayOutputStream();
            System.setOut(new PrintStream(bout));
            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)
                ret = bout.toString();
            else
                ret = null;
        }
        finally
        {
            System.setOut(_sysout);
        }

        return ret;
    }

    /*
     * 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(">>>> 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);
    }
}