001    /*
002     * Copyright (C) 2000-2001 Iowa State University
003     * 
004     * This file is part of mjc, the MultiJava Compiler, and the JML Project.
005     * 
006     * This program is free software; you can redistribute it and/or modify it under
007     * the terms of the GNU General Public License as published by the Free Software
008     * Foundation; either version 2 of the License, or (at your option) any later
009     * version.
010     * 
011     * This program is distributed in the hope that it will be useful, but WITHOUT
012     * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
013     * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
014     * details.
015     * 
016     * You should have received a copy of the GNU General Public License along with
017     * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
018     * Place, Suite 330, Boston, MA 02111-1307 USA
019     * 
020     * $Id: Diff.java,v 1.4 2005/08/21 20:35:42 jkiniry Exp $
021     */
022    
023    package junitutils;
024    
025    import java.util.StringTokenizer;
026    import java.util.ArrayList;
027    
028    /**
029     * Class for calculating a (somewhat) detailed comparison of two strings.
030     * 
031     * @author Curtis Clifton
032     * @version $Revision: 1.4 $
033     */
034    
035    public class Diff {
036    
037      //---------------------------------------------------------------------
038      // CONSTRUCTORS
039      //---------------------------------------------------------------------
040      /**
041       * Calculate a difference between the given strings.
042       * 
043       * @param oldTextLabel a label for the <code>oldText</code> parameter
044       * @param oldText a value to be compared
045       * @param newTextLabel a label for the <code>newText</code> parameter
046       * @param newText a value to be compared
047       */
048      //@ requires oldTextLabel != null;
049      //@ requires oldText != null;
050      //@ requires newTextLabel != null;
051      //@ requires newText != null;
052      public Diff(String oldTextLabel, String oldText, String newTextLabel,
053          String newText) {
054        this.oldText = oldText;
055        this.newText = newText;
056        calculate(oldTextLabel, newTextLabel);
057      }
058    
059      //---------------------------------------------------------------------
060      // OPERATIONS
061      //---------------------------------------------------------------------
062    
063      /**
064       * Sets the values of areDifferent and result according to a comparison
065       * between oldText and newText
066       * 
067       * @param oldTextLabel a label for the <code>oldText</code> parameter
068       * @param newTextLabel a label for the <code>newText</code> parameter
069       */
070      //@ requires oldTextLabel != null;
071      //@ requires newTextLabel != null;
072      private void calculate(String oldTextLabel, String newTextLabel) {
073        // Accumulate the diff in resultSB
074        StringBuffer resultSB = new StringBuffer(newText.length());
075    
076        String[] oldTextLines = splitByLine(oldText);
077        String[] newTextLines = splitByLine(newText);
078    
079        // match by lines
080        int oPos = 0;
081        int nPos = 0;
082        int lastOldMatch = -1;
083        int lastNewMatch = -1;
084        if (oldTextLines.length > 0 && newTextLines.length > 0)
085         while (oPos < oldTextLines.length || nPos < newTextLines.length) {
086          // this is a pretty dumb algorithm that doesn't handle
087          // things like the insertion of a single new line in one
088          // string or grouping
089          if (oPos >= oldTextLines.length) oPos = oldTextLines.length-1;
090          if (nPos >= newTextLines.length) nPos = newTextLines.length-1;
091          boolean matched = false;
092          for (int i = lastOldMatch+1; i<=oPos; ++i) {
093            if (oldTextLines[i].equals(newTextLines[nPos])) {
094              // Got a match
095              for (int j=lastOldMatch+1; j<i; ++j)
096                resultSB.append((j+1) + OLD_CH + oldTextLines[j] + NEWLINE);
097              for (int j=lastNewMatch+1; j<nPos; ++j)
098                resultSB.append((j+1) + NEW_CH + newTextLines[j] + NEWLINE);
099              lastOldMatch = i;
100              lastNewMatch = nPos;
101              oPos = i+1;
102              nPos++;
103              matched = true;
104              break;
105            }
106          }
107          if (matched) continue;
108          for (int i = lastNewMatch+1; i<=nPos; ++i) {
109            if (newTextLines[i].equals(oldTextLines[oPos])) {
110              // Got a match
111              for (int j=lastOldMatch+1; j<oPos; ++j)
112                resultSB.append((j+1) + OLD_CH + oldTextLines[j] + NEWLINE);
113              for (int j=lastNewMatch+1; j<i; ++j)
114                resultSB.append((j+1) + NEW_CH + newTextLines[j] + NEWLINE);
115              lastOldMatch = oPos;
116              lastNewMatch = i;
117              oPos++;
118              nPos = i + 1;
119              matched = true;
120              break;        }
121          }
122          if (matched) continue;
123          oPos++;
124          nPos++;
125        }
126        // If we reached the end of one array before the other, then this
127        // will print the remainders.
128        for (oPos=lastOldMatch+1; oPos < oldTextLines.length; oPos++) {
129          resultSB.append((oPos + 1) + OLD_CH + oldTextLines[oPos] + NEWLINE);
130        } // end of for ()
131        for (nPos=lastNewMatch+1; nPos < newTextLines.length; nPos++) {
132          resultSB.append((nPos + 1) + NEW_CH + newTextLines[nPos] + NEWLINE);
133        } // end of for ()
134    
135        if (resultSB.length() > 0) {
136          // Some diffs accumulated, so the strings are different
137          areDifferent = true;
138    
139          // Prepend a key to the results.
140          result = NEWLINE + OLD_CH + oldTextLabel + NEWLINE + NEW_CH
141              + newTextLabel + NEWLINE + NEWLINE + resultSB.toString();
142        } else {
143          // No diffs accumulated, so the strings must be the same
144          areDifferent = false;
145          result = "";
146        }
147      }
148    
149      //@ requires text != null;
150      //@ ensures \result != null;
151      //@ ensures \nonnullelements(\result);
152      private String[] splitByLine(String text) {
153        // thanks to Windows ridiculous two character newlines it is
154        // hard to detect blank lines, so we don't bother trying
155        StringTokenizer toker = new StringTokenizer(text, DELIM, false);
156        ArrayList lines = new ArrayList(oldText.length() / 60);
157        while (toker.hasMoreTokens()) {
158          String tok = toker.nextToken();
159          lines.add(tok);
160        }
161        String[] result = new String[lines.size()];
162        lines.toArray(result);
163        return result;
164      }
165    
166      /**
167       * Returns true if strings on which this was constructed are different.
168       */
169      //@ private behavior
170      //@ ensures \result == areDifferent;
171      public /*@ pure @*/ boolean areDifferent() {
172        return areDifferent;
173      }
174    
175      /**
176       * Returns the differences between the given strings.
177       *  
178       */
179      //@ private normal_behavior
180      //@ ensures \result == result;
181      //@ pure
182      public String result() {
183        return result;
184      }
185    
186      //---------------------------------------------------------------------
187      // PRIVILEGED DATA
188      //---------------------------------------------------------------------
189    
190      /** This is the supplied old text, to be compared against the new text */
191      //@ non_null
192      private String oldText;
193    
194      /** This is the supplied new text, to be compared against the old text */
195      //@ non_null
196      private String newText;
197    
198      /** This is set to true if the oldText and newText are not the same */
199      private boolean areDifferent = false;
200    
201      /**
202       * This output String holds the description of the differences between the old
203       * and new text.
204       */
205      //@ non_null
206      private String result = "";
207    
208      //@ private invariant areDifferent <=!=> result.equals("");
209    
210      /** This string holds line delimiters */
211      //@ non_null
212      private static final String DELIM = "\n\r\f";
213    
214      /** This is the system new line character */
215      //@ non_null
216      private static final String NEWLINE = System.getProperty("line.separator");
217    
218      /** This string is used to mark lines of old text */
219      //@ non_null
220      private static final String OLD_CH = "< ";
221    
222      /** This string is used to mark lines of new text */
223      //@ non_null
224      private static final String NEW_CH = "> ";
225    }