// JavaAnalyzer class interface: check for balanced symbols /XREF
//
// CONSTRUCTION: with a BufferedReader object
// ******************PUBLIC OPERATIONS***********************
// int checkBalance( )   --> Print mismatches
//                           return number of errors
// void generateCrossReference( ) --> Name says it all ...
// ******************ERRORS**********************************
// Error checking on comments and quotes is performed


// main generates both cross-reference and checks for balanced symbols.
// It is simple to comment out one of the two.

import java.io.*;
import DataStructures.*;
import Exceptions.*;
import Supporting.*;
import Supporting.Comparable;

/**
 * Symbol is the class that will be placed on the stack.
 */
class Symbol
{
    char  token;
    int   theLine;

    Symbol( char tok, int line )
    {
        token   = tok;
        theLine = line;
    }
}


/**
 * The basic object that will be stored in a search tree
 * for the cross-reference generator.
 * It implements the Comparable interface by providing
 * compares and lessThan.
 */
class IdNode implements Comparable
{
    String word;    // An identifier
    Queue  lines;   // Lines where it occurs

        // Constructor
    IdNode( String theWord, int currentLine )
    {
        word = new String( theWord );
        lines = new QueueAr( );
        lines.enqueue( new Integer( currentLine ) );
    }

        // Ordering methods
    public boolean lessThan( Comparable rhs )
    {
        return word.compareTo( ( (IdNode) rhs ).word ) < 0;
    }

    public int compares( Comparable rhs )
    {
        return word.compareTo( ( (IdNode) rhs ).word );
    }
}

/**
 * Class to perform symbol matching and cross reference
 * generation for Java programs.
 */
class JavaAnalyzer
{
    /**
     * Constructor.
     * @param inStream the stream containing a program.
     */
    public JavaAnalyzer( PushbackReader inStream )
    {
        errors = 0;
        ch = '\0';
        currentLine = 1;
        in = inStream;
        pendingTokens = new StackAr( );
        currentIdNode = new IdNode( "", 1 );
    }


    /**
     * Print an error message for unbalanced symbols.
     * @return number of errors detected.
     */
    public int checkBalance( )
    {
        Symbol match = null;

        errors = 0; currentLine = 1;
        while( getNextSymbol( ) )
        {
            char   lastChar = ch;
            Symbol lastSymbol = new Symbol( lastChar, currentLine );

            switch( lastChar )
            {
              case '(': case '[': case '{':
                pendingTokens.push( lastSymbol );
                break;
        
              case ')': case ']': case '}':
                try
                {
                    match = (Symbol) pendingTokens.topAndPop( );
                    checkMatch( match, lastSymbol );
                }
                catch( Underflow e )
                {
                    errors++;
                    System.out.println( "Extraneous " + lastChar +
                                        " at line " + currentLine );
                }
                break;

              default: // Cannot happen
                break;
            }
        }

        while( !pendingTokens.isEmpty( ) )
        {
            errors++;
            try
              { match = (Symbol) pendingTokens.topAndPop( ); }
            catch( Underflow e ) { } // Cannot happen
            System.out.println( "Unmatched " + match.token +
                                " at line "  + match.theLine );
        }
        return errors;
    }

    private static final int SLASH_SLASH = 0;
    private static final int SLASH_STAR  = 1;

    private PushbackReader in;    // The input stream
    private char ch;              // Current character
    private int currentLine;      // Current line
    private Stack pendingTokens;  // Open symbols pending
    private int errors;           // Number of errors seen
    private IdNode currentIdNode; // For Xref generator


    /**
     * nextChar sets ch based on the next character in the input stream.
     * putBackChar puts the character back onto the stream.
     * It should only be used once after a nextChar.
     * Both routines adjust currentLine if necessary.
     */

    private boolean nextChar( )
    {
        try
        {
            int readVal = in.read( );
            if( readVal == -1 )
                return false;
            ch = (char) readVal;
            if( ch == '\n' )
                currentLine++;
            return true;
        }
        catch( IOException e )
          { return false; }
    }

    private void putBackChar( )
    {
        if( ch == '\n' )
            currentLine--;
        try 
          { in.unread( (int) ch ); }
        catch( IOException e ) { }
    }


    /**
     * Precondition: We are about to process a comment; have already seen
     *                 comment-start token
     * Postcondition: Stream will be set immediately after
     *                 comment-ending token
     */
    private void skipComment( int start )
    {
        if( start == SLASH_SLASH )
        {
            while( nextChar( ) && ( ch != '\n' ) )
                ;
            return;
        }

            // Look for a */ sequence
        boolean state = false;   // True if we have seen *

        while( nextChar( ) )
        {
            if( state && ch == '/' )
                return;
            state = ( ch == '*' );
        }
        errors++;
        System.out.println( "Unterminated comment!" );
    }

    /**
     * Precondition: We are about to process a quote; have already seen
     *                   beginning quote.
     * Postcondition: Stream will be set immediately after
     *                   matching quote
     */
    private void skipQuote( char quoteType )
    {
        while( nextChar( ) )
        {
            if( ch == quoteType )
                return;
            if( ch == '\n' )
            {
                errors++;
                System.out.println( "Missing closed quote at line " +
                                    currentLine );
                return;
            }
            else if( ch == '\\' )
                nextChar( );
        }
    }

    /**
     * Get the next opening or closing symbol.
     * Return false if end of file.
     * Skip past comments and character and string constants
     */
    private boolean getNextSymbol( )
    {
        while( nextChar( ) )
        {
            if( ch == '/' )
                processSlash( );
            else if( ch == '\'' || ch == '"' )
                skipQuote( ch );
            else if( ch == '\\' )  // Extra case, not in text
                nextChar( );
            else if( ch == '(' || ch == '[' || ch == '{' ||
                     ch == ')' || ch == ']' || ch == '}' )
                return true;
        }
        return false;       // End of file
    }


    /**
     * Print an error message if clSym does not match opSym.
     * Update Error.
     */
    private void checkMatch( Symbol opSym, Symbol clSym )
    {
        if( opSym.token == '(' && clSym.token != ')' ||
            opSym.token == '[' && clSym.token != ']' ||
            opSym.token == '{' && clSym.token != '}' )
        {
            System.out.println( "Found " + clSym.token + " on line " +
                  currentLine + "; does not match " + opSym.token
                  + " at line " + opSym.theLine );
            errors++;
        }
    }

    /**
     * After the opening slash is seenm deal with next character.
     * If it is a comment starter, process it; otherwise putback
     * the next character if it is not a newline.
     */
    private void processSlash( )
    {
        if( nextChar( ) )
        {
            if( ch == '*' )
            {
                // Javadoc comment
                if( nextChar( ) && ch != '*' )
                    putBackChar( );
                skipComment( SLASH_STAR );
            }
            else if( ch == '/' )
                skipComment( SLASH_SLASH );
            else if( ch != '\n' )
                putBackChar( );
        }
    }

    /**
     * Return true if ch can be part of a Java identifier
     */
    private boolean isIdChar( char ch )
    {
        return ch == '_' || Character.isUpperCase( ch ) ||
               Character.isLowerCase( ch ) || Character.isDigit( ch );
    }

    /**
     * Return an identifier read from input stream
     * First character is already read into ch
     */
    private String getString( )
    {
        String tmpString = "";
             
        for( tmpString += ch; nextChar( ); tmpString += ch )
            if( !isIdChar( ch ) )
            {
                putBackChar( );
                break;
            }

        return tmpString; 
    }

    /**
     * Return next identifier, skipping comments
     * string constants, and character constants.
     * Place identifier in current.word and return false
     * only if end of stream is reached.
     */
    private boolean getNextID( )
    {
        while( nextChar( ) )
        {
            if( ch == '/' )
                processSlash( );
            else if( ch == '\\' )
                nextChar( );
            else if( ch == '\'' || ch == '"' )
                skipQuote( ch );
            else if( !Character.isDigit( ch ) && isIdChar( ch ) )
            {
                currentIdNode.word = getString( );
                return true;
            }
        }
        return false;       // End of file
    }


    /**
     * Output the cross reference.
     */
    public void generateCrossReference( )
    {
        BinarySearchTree theIdentifiers = new BinarySearchTree( );

            // Insert identifiers into the search tree
        while( getNextID( ) )
        {
            try
            {
                IdNode thisNode = (IdNode) theIdentifiers.find( currentIdNode );
                thisNode.lines.enqueue( new Integer( currentLine ) );
            }
            catch( ItemNotFound e )
            {
                try
                {
                    theIdentifiers.insert(
                           new IdNode( currentIdNode.word, currentLine ) );
                }
                catch( DuplicateItem ex ) { } // Cannot happen
            }
        }

            // Iterate through search tree and output
            // identifiers and their line number
        try
        {
            InOrder itr = new InOrder( theIdentifiers );
            for( itr.first( ); itr.isValid( ); itr.advance( ) )
            {
                IdNode thisNode = (IdNode) itr.retrieve( );

                    // Print identifier and first line where it occurs
                System.out.print( thisNode.word + ": " +
                                  (Integer) thisNode.lines.dequeue( ) );

                    // Print all other lines on which it occurs
                while( !thisNode.lines.isEmpty( ) )
                    System.out.print( ", " + (Integer) thisNode.lines.dequeue( ) );
                System.out.println( );
            }
        }
        catch( ItemNotFound e ) { }   // Empty tree
        catch( Underflow e ) { }      // Cannot happen
    }

    /**
     * main routine for balanced symbol checker and Xref.
     * Slightly different from text.
     */
    public static void main( String [ ] args )
    {

        JavaAnalyzer p;

        if( args.length == 0 )
        {

            p = new JavaAnalyzer( new PushbackReader( new InputStreamReader( System.in ) ) );
            if( p.checkBalance( ) == 0 )
                System.out.println( "No errors!" );

            return;
        }

        for( int i = 0; i < args.length; i++ )
        {
            try 
            {
                FileReader f = new FileReader( args[ i ] );

                System.out.println( args[ i ] + ": " );
                p = new JavaAnalyzer( new PushbackReader( f ) );
                if( p.checkBalance( ) == 0 ) 
                    System.out.println( "   ...no errors!" );
                f.close( );

                    // Do cross-reference
                f = new FileReader( args[ i ] );
                p = new JavaAnalyzer( new PushbackReader( f ) );
                p.generateCrossReference( );  /* Comment this line to remove xref */
                f.close( );
            }
            catch( IOException e )
              { System.err.println( e + args[ i ] ); }

        }
    }
}