0001: /*
0002: * Copyright (C) 2001, 2002 Robert MacGrogan
0003: *
0004: * This library is free software; you can redistribute it and/or
0005: * modify it under the terms of the GNU Lesser General Public
0006: * License as published by the Free Software Foundation; either
0007: * version 2.1 of the License, or (at your option) any later version.
0008: *
0009: * This library is distributed in the hope that it will be useful,
0010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0012: * Lesser General Public License for more details.
0013: *
0014: * You should have received a copy of the GNU Lesser General Public
0015: * License along with this library; if not, write to the Free Software
0016: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0017: *
0018: *
0019: * $Archive: SourceJammer$
0020: * $FileName: diff3.java$
0021: * $FileID: 4282$
0022: *
0023: * Last change:
0024: * $AuthorName: Rob MacGrogan$
0025: * $Date: 4/23/03 5:23 PM$
0026: * $Comment: Replaced GPL header with LGPL header.$
0027: *
0028: * $KeyWordsOff: $
0029: */
0030:
0031: package JLibDiff;
0032:
0033: import java.util.*;
0034: import java.io.*;
0035:
0036: import org.sourcejammer.util.FileUtil;
0037: import org.sourcejammer.util.TextLineReader2;
0038:
0039: /**
0040: * The <code>diff3</code> class compares three files or three BufferedReaders.
0041: * after comparison, the vector will represente a list of Hunk3
0042: * corresponding with blocks of difference.
0043: * <p>
0044: * to generate Hunk3, one can instanciate as follows the class <code>diff3</code>:
0045: * <p><blockquote><pre>
0046: * diff3 d = new diff3(file1,file2,file3);
0047: * </pre></blockquote><p>
0048: * which is equivalent to:
0049: * <p><blockquote><pre>
0050: * diff3 d = new diff3();
0051: * d.diffFile(file1,file2,file3);
0052: * </pre></blockquote><p>
0053: * To compaire three BufferedReader we have to instanciate as follows:
0054: * <p><blockquote><pre>
0055: * diff3 d = new diff3();
0056: * d.diffBuffer(BufferedReader1,BufferedReader2,BufferedReader3);
0057: * </pre></blockquote><p>
0058: * The class <code>diff3</code> includes methods for examining, printing
0059: * or saveing blocks of difference:(Hunk3).
0060: * Here are some more examples of how <code>diff3</code> can be used:
0061: * <p><blockquote><pre>
0062: * diff3 d = new diff3(file1,file2,file3);
0063: * d.print();
0064: * d.save("diff.txt");
0065: * </pre></blockquote><p>
0066: * Example using BufferedReader and ED_format:
0067: * <p><blockquote><pre>
0068: * BufferedReader in0=new BufferedReader(new FileReader(file1));
0069: * BufferedReader in1=new BufferedReader(new FileReader(file2));
0070: * BufferedReader in2=new BufferedReader(new FileReader(file3));
0071: * diff3 d = new diff3();
0072: * d.diffBuffer(in0,in1,in2);
0073: * d.print_ED();
0074: * d.save_ED("diff.txt");
0075: * </pre></blockquote><p>
0076: *
0077: *
0078: *
0079: * @see diff.diff3#getHunk3()
0080: * @see diff.diff3#hunk3At()
0081: * @see diff.diff3#numberOfHunk3()
0082: * @see diff.diff3#print()
0083: * @see diff.diff3#save()
0084: */
0085: public class diff3 implements Hunk3Visitable {
0086:
0087: Vector v = new Vector();
0088: private TextLineReader2 reader0 = null;
0089: private TextLineReader2 reader1 = null;
0090:
0091: /**
0092: * Allocates a new <code>diff3</code> containing no Hunks.
0093: */
0094: public diff3() {
0095: }
0096:
0097: /**
0098: * Allocates a new <code>diff3</code> which contains Hunk3 corresponding
0099: * to the differences between the three files passed in arguments.
0100: *
0101: * @param s0 first file.
0102: * @param s1 second file.
0103: * @param s2 therd file.
0104: */
0105: public diff3(String s0, String s1, String s2) throws IOException {
0106: diffFile(s0, s1, s2);
0107: }
0108:
0109: public TextLineReader2 getFile0Lines() {
0110: return reader0;
0111: }
0112:
0113: /**
0114: * Compaires three files and updates the vector of Hunk3.
0115: *
0116: * @param s0 first file.
0117: * @param s1 second file.
0118: * @param s2 therd file.
0119: */
0120: public void diffFile(String s0, String s1, String s2)
0121: throws IOException {
0122:
0123: diff d01 = new diff();
0124: diff d02 = new diff();
0125: diff d12 = new diff();
0126: //d01.diffFile(s0, s1);
0127: d02.diffFile(s0, s2);
0128:
0129: d12.diffFile(s1, s2);
0130: Vector v01, v02, v12;
0131: //v01 = d01.getHunk();
0132: v02 = d02.getHunk();
0133: v12 = d12.getHunk();
0134:
0135: //Initialize text line readers for 0 and 1.
0136: byte[] byFile0 = FileUtil.readBytesFromFileSys(s0);
0137: reader0 = new TextLineReader2(byFile0);
0138: reader0.init();
0139:
0140: byte[] byFile1 = FileUtil.readBytesFromFileSys(s1);
0141: reader1 = new TextLineReader2(byFile1);
0142: reader1.init();
0143:
0144: v = getHunk3(v02, v12);
0145: //v=buildDiff3(v01, v02,v12);
0146: //processHunks(v, s0, s1, s2);
0147: Iterator itr = v.iterator();
0148: while (itr.hasNext()) {
0149: Hunk3 h = (Hunk3) itr.next();
0150: System.out.print("--" + h.getType());
0151: System.out
0152: .print(" " + h.lowLine(0) + ", " + h.highLine(0));
0153: System.out
0154: .print("; " + h.lowLine(1) + ", " + h.highLine(1));
0155: System.out.println("; " + h.lowLine(2) + ", "
0156: + h.highLine(2));
0157: }
0158: }
0159:
0160: private void processHunks(Vector vec, String file0, String file1,
0161: String file2) throws IOException {
0162: byte[] byFile0 = FileUtil.readBytesFromFileSys(file0);
0163: reader0 = new TextLineReader2(byFile0);
0164: reader0.init();
0165:
0166: byte[] byFile1 = FileUtil.readBytesFromFileSys(file1);
0167: TextLineReader2 reader1 = new TextLineReader2(byFile1);
0168: reader1.init();
0169:
0170: byte[] byFile2 = FileUtil.readBytesFromFileSys(file2);
0171: TextLineReader2 reader2 = new TextLineReader2(byFile2);
0172: reader2.init();
0173:
0174: Iterator itr = vec.iterator();
0175: while (itr.hasNext()) {
0176: Hunk3 hunk = (Hunk3) itr.next();
0177:
0178: //Determine type of hunk based on ranges.
0179: Hunk3Type type = new Hunk3Type();
0180: int range0 = hunk.highLine(0) - hunk.lowLine(0);
0181: int range1 = hunk.highLine(1) - hunk.lowLine(1);
0182: int range2 = hunk.highLine(2) - hunk.lowLine(2);
0183:
0184: //Check for file(s) that have changed.
0185: if (areRangesEqual(reader0, hunk.lowLine(0), hunk
0186: .highLine(0), reader1, hunk.lowLine(1), hunk
0187: .highLine(1))) {
0188: //0 and 1 are the same, so 2 must be different.
0189: type.setInFileType(Hunk3Type.FILE_TWO);
0190: } else if (areRangesEqual(reader0, hunk.lowLine(0), hunk
0191: .highLine(0), reader2, hunk.lowLine(2), hunk
0192: .highLine(2))) {
0193: //0 and 2 are the same, so 1 must be different.
0194: type.setInFileType(Hunk3Type.FILE_ONE);
0195: } else if (areRangesEqual(reader1, hunk.lowLine(1), hunk
0196: .highLine(1), reader2, hunk.lowLine(2), hunk
0197: .highLine(2))) {
0198: //1 and 2 are the same.
0199: type.setInFileType(Hunk3Type.BOTH_FILES_SAME);
0200: } else {
0201: //All files must be different
0202: type.setInFileType(Hunk3Type.BOTH_FILES_DIFFERENT);
0203: }
0204: hunk.setType(type);
0205: } //end while
0206:
0207: //
0208: // if (range0 == 1){
0209: // if (range1 > 1 &&
0210: // areRangesEqual(reader0, hunk.lowLine(0), hunk.highLine(0),
0211: // reader2, hunk.lowLine(2), hunk.highLine(2)) ){
0212: // //Addition to file 1, so . . .
0213: // type.setDifferenceType(Hunk3Type.ADD);
0214: // type.setInFileType(Hunk3Type.FILE_ONE);
0215: // hunk.setFile1Lines(rangeToArrayList(reader1, hunk.lowLine(1), hunk.highLine(1)));
0216: // }
0217: // else if (range1 == 0 &&
0218: // range2 > 0){
0219: // //Addition to file 2, so . . .
0220: // type.setDifferenceType(Hunk3Type.ADD);
0221: // type.setInFileType(Hunk3Type.FILE_TWO);
0222: // hunk.setFile2Lines(rangeToArrayList(reader2, hunk.lowLine(2), hunk.highLine(2)));
0223: // }
0224: // else if (areRangesEqual(reader1, hunk.lowLine(1), hunk.highLine(1),
0225: // reader2, hunk.lowLine(2), hunk.highLine(2))){
0226: // //same addition to both files.
0227: // type.setDifferenceType(Hunk3Type.ADD);
0228: // type.setInFileType(Hunk3Type.BOTH_FILES_SAME);
0229: // hunk.setFile1Lines(rangeToArrayList(reader1, hunk.lowLine(1), hunk.highLine(1)));
0230: // }
0231: // else{
0232: // //different addition to both files.
0233: // type.setDifferenceType(Hunk3Type.ADD);
0234: // type.setInFileType(Hunk3Type.BOTH_FILES_DIFFERENT);
0235: // hunk.setFile1Lines(rangeToArrayList(reader1, hunk.lowLine(1), hunk.highLine(1)));
0236: // hunk.setFile2Lines(rangeToArrayList(reader2, hunk.lowLine(2), hunk.highLine(2)));
0237: // }
0238: // }
0239: // else if (range0 > 0){
0240: // if (range1 == 0 && range2 == 0){
0241: // //removed from to both files.
0242: // type.setDifferenceType(Hunk3Type.REMOVE);
0243: // type.setInFileType(Hunk3Type.BOTH_FILES_SAME);
0244: // hunk.setFile0Lines(rangeToArrayList(reader0, hunk.lowLine(0), hunk.highLine(0)));
0245: // }
0246: // else if (areRangesEqual(reader0, hunk.lowLine(0), hunk.highLine(0),
0247: // reader1, hunk.lowLine(1), hunk.highLine(1))){
0248: // //File 0 and 1 are the same.
0249: // if (range2 == 0){
0250: // //Remove from 2.
0251: // type.setDifferenceType(Hunk3Type.REMOVE);
0252: // type.setInFileType(Hunk3Type.FILE_TWO);
0253: // hunk.setFile0Lines(rangeToArrayList(reader0, hunk.lowLine(0), hunk.highLine(0)));
0254: // }
0255: // else{
0256: // //Must be a change in 2.
0257: // type.setDifferenceType(Hunk3Type.CHANGE);
0258: // type.setInFileType(Hunk3Type.FILE_TWO);
0259: // hunk.setFile0Lines(rangeToArrayList(reader0, hunk.lowLine(0), hunk.highLine(0)));
0260: // hunk.setFile2Lines(rangeToArrayList(reader2, hunk.lowLine(2), hunk.highLine(2)));
0261: // }
0262: // }//end if 0 and 1 are the same.
0263: // else if (areRangesEqual(reader0, hunk.lowLine(0), hunk.highLine(0),
0264: // reader2, hunk.lowLine(2), hunk.highLine(2))){
0265: // //File 0 and 2 are the same.
0266: // if (range1 == 0){
0267: // //Remove from 1.
0268: // type.setDifferenceType(Hunk3Type.REMOVE);
0269: // type.setInFileType(Hunk3Type.FILE_ONE);
0270: // hunk.setFile0Lines(rangeToArrayList(reader0, hunk.lowLine(0), hunk.highLine(0)));
0271: // }
0272: // else{
0273: // //Must be a change in 1.
0274: // type.setDifferenceType(Hunk3Type.CHANGE);
0275: // type.setInFileType(Hunk3Type.FILE_ONE);
0276: // hunk.setFile0Lines(rangeToArrayList(reader0, hunk.lowLine(0), hunk.highLine(0)));
0277: // hunk.setFile1Lines(rangeToArrayList(reader1, hunk.lowLine(1), hunk.highLine(1)));
0278: // }
0279: // }//end if 0 and 2 are the same.
0280: // else{
0281: // //Must be a change in all both files.
0282: // type.setDifferenceType(Hunk3Type.CHANGE);
0283: // if (areRangesEqual(reader1, hunk.lowLine(1), hunk.highLine(1),
0284: // reader2, hunk.lowLine(2), hunk.highLine(2))){
0285: // type.setInFileType(Hunk3Type.BOTH_FILES_SAME);
0286: // }
0287: // else{
0288: // type.setInFileType(Hunk3Type.BOTH_FILES_DIFFERENT);
0289: // hunk.setFile2Lines(rangeToArrayList(reader2, hunk.lowLine(2), hunk.highLine(2)));
0290: // }
0291: // hunk.setFile0Lines(rangeToArrayList(reader0, hunk.lowLine(0), hunk.highLine(0)));
0292: // hunk.setFile1Lines(rangeToArrayList(reader1, hunk.lowLine(1), hunk.highLine(1)));
0293: // }
0294: // hunk.setType(type);
0295: // }
0296: // }//end while
0297: }
0298:
0299: private boolean areRangesEqual(TextLineReader2 reader1,
0300: int startLine1, int endLine1, TextLineReader2 reader2,
0301: int startLine2, int endLine2) {
0302: boolean equal = false;
0303: boolean continueLooking = true;
0304: int range = endLine2 - startLine2;
0305: if (range == endLine1 - startLine1) {
0306: int counter = 0;
0307: while (continueLooking) {
0308: String line1 = reader1.getLine(startLine1 + counter);
0309: String line2 = reader2.getLine(startLine2 + counter);
0310: if (!line2.equals(line1)) {
0311: continueLooking = false;
0312: }
0313: counter++;
0314: if (counter > range) {
0315: continueLooking = false;
0316: equal = true;
0317: }
0318: }
0319: }
0320: return equal;
0321: }
0322:
0323: private ArrayList rangeToArrayList(TextLineReader2 reader,
0324: int startLine, int endLine) {
0325: ArrayList lines = new ArrayList();
0326: for (int i = startLine; i < endLine; i++) {
0327: lines.add(reader.getLine(i));
0328: }
0329: return lines;
0330: }
0331:
0332: private int addSingleFileChangeHunks(Vector buildDiff3,
0333: Vector singleFile, Vector v12, int startIndex,
0334: int endIndex, int diff12Index, DiffType type) {
0335:
0336: for (int i = startIndex; i <= endIndex; i++) {
0337: Hunk hunk = (Hunk) singleFile.get(i);
0338: OverlapTestResult result = findOverlapIndex(hunk, v12,
0339: diff12Index);
0340: //Assume we'll find it.
0341: diff12Index = result.nearestIndex;
0342: Hunk hunk12 = (Hunk) v12.get(diff12Index);
0343:
0344: Hunk3 h3 = new Hunk3();
0345: System.out.println("[diff] type=" + type);
0346: h3.diff = type;
0347: h3.setRange(hunk.lowLine(0), hunk.highLine(0), hunk
0348: .lowLine(1), hunk.highLine(1), hunk12.lowLine(1),
0349: hunk12.highLine(1));
0350: buildDiff3.add(h3);
0351: }
0352: return diff12Index;
0353: }
0354:
0355: private Vector buildDiff3(Vector v01, Vector v02, Vector v12) {
0356:
0357: Vector buildDiff3 = new Vector();
0358: //Loop through v1.
0359: int iDiff01Index = 0;
0360: int iDiff02Index = 0;
0361: int iDiff12Index = 0;
0362:
0363: boolean continueBuilding = true;
0364: while (continueBuilding) {
0365: Hunk hunk1 = (Hunk) v01.get(iDiff01Index);
0366:
0367: //Look for overlap in v2.
0368: int matchIndex;
0369: OverlapTestResult overlapTest = findOverlapIndex(hunk1,
0370: v02, iDiff02Index);
0371:
0372: //Do we have any unmatched hunks from 2 to add?
0373: int addUpToIndex = overlapTest.nearestIndex;
0374: if (overlapTest.overlapFound) {
0375: addUpToIndex--;
0376: }
0377: if (addUpToIndex >= iDiff02Index) {
0378: //Add uncontested hunk from file 2.
0379: iDiff12Index = addSingleFileChangeHunks(buildDiff3,
0380: v02, v12, iDiff02Index, addUpToIndex,
0381: iDiff12Index, DiffType.DIFF_3RD);
0382: iDiff02Index = addUpToIndex;
0383: }
0384:
0385: if (!overlapTest.overlapFound) {
0386: //Add uncontested hunk from file 1.
0387: iDiff12Index = addSingleFileChangeHunks(buildDiff3,
0388: v01, v12, iDiff01Index, iDiff01Index,
0389: iDiff12Index, DiffType.DIFF_2ND);
0390: iDiff01Index++;
0391: } else {
0392: //Overlap found.
0393: iDiff02Index = overlapTest.nearestIndex;
0394: Hunk hunk2 = (Hunk) v02.get(iDiff02Index);
0395: if (doHunkRangesMatch(hunk1, hunk2)) {
0396: //Hunks refer to exact same region of file 0.
0397: Hunk3 h3 = new Hunk3();
0398: h3.diff = DiffType.DIFF_ALL;
0399: h3.setRange(hunk1.lowLine(0), hunk1.highLine(0),
0400: hunk1.lowLine(1), hunk1.highLine(1), hunk2
0401: .lowLine(1), hunk2.highLine(1));
0402:
0403: buildDiff3.add(h3);
0404: iDiff01Index++;
0405: } else {
0406: OverLapBuildResult result = buildOverLapHunk(v01,
0407: v02, v12, iDiff01Index, iDiff02Index,
0408: iDiff12Index);
0409: buildDiff3.add(result.hunk3);
0410: iDiff01Index = result.nextIndex01;
0411: iDiff02Index = result.nextIndex02;
0412: }
0413: }
0414: if (iDiff01Index >= v01.size()) {
0415: continueBuilding = false;
0416: }
0417: }
0418:
0419: return buildDiff3;
0420: }
0421:
0422: private OverLapBuildResult buildOverLapHunk(Vector v01, Vector v02,
0423: Vector v12, int index01, int index02, int diff12Index) {
0424:
0425: OverLapBuildResult returnVal = new OverLapBuildResult();
0426: OverlapIndexes overlap = getEndOfOverlap(v01, v02, index01,
0427: index02);
0428: int lastIndex01 = overlap.endIndex01;
0429: int lastIndex02 = overlap.endIndex02;
0430:
0431: Hunk3 rtn = new Hunk3();
0432:
0433: Hunk h1Begin = (Hunk) v01.get(index01);
0434: Hunk h2Begin = (Hunk) v02.get(index02);
0435: Hunk h1End = (Hunk) v01.get(lastIndex01);
0436: Hunk h2End = (Hunk) v02.get(lastIndex02);
0437:
0438: int iBegin0 = -1;
0439: int iEnd0 = -1;
0440: int iBegin1 = -1;
0441: int iEnd1 = -1;
0442: int iBegin2 = -1;
0443: int iEnd2 = -1;
0444:
0445: if (hunk1HasLowest0(h1Begin, h2Begin)) {
0446: iBegin0 = h1Begin.lowLine(0);
0447: iBegin1 = h1Begin.lowLine(1);
0448:
0449: OverlapTestResult result = findOverlapIndex(h1Begin, v12,
0450: diff12Index);
0451: if (result.overlapFound) {
0452: Hunk h = (Hunk) v12.get(result.nearestIndex);
0453: iBegin2 = h.lowLine(1);
0454: } else {
0455: //No overlap, so h1Begin must match h2Begin.
0456: iBegin2 = h2Begin.lowLine(1);
0457: }
0458: } else {
0459: iBegin0 = h2Begin.lowLine(0);
0460: iBegin2 = h2Begin.lowLine(1);
0461:
0462: OverlapTestResult result = findOverlapIndex(h2Begin, v12,
0463: diff12Index);
0464: if (result.overlapFound) {
0465: Hunk h = (Hunk) v12.get(result.nearestIndex);
0466: iBegin1 = h.lowLine(0);
0467: } else {
0468: //No overlap, so h1Begin must match h2Begin.
0469: iBegin1 = h1Begin.lowLine(1);
0470: }
0471: }
0472:
0473: if (hunk1HasHighest0(h1End, h2End)) {
0474: iEnd0 = h1End.highLine(0);
0475: iEnd1 = h1End.highLine(1);
0476:
0477: OverlapTestResult result = findOverlapIndex(h1End, v12,
0478: diff12Index);
0479: if (result.overlapFound) {
0480: Hunk h = (Hunk) v12.get(result.nearestIndex);
0481: iEnd2 = h.highLine(1);
0482:
0483: OverlapTestResult result2 = findOverlapIndex(h2End,
0484: v12, diff12Index);
0485: if (result.overlapFound) {
0486: Hunk htest = (Hunk) v12.get(result2.nearestIndex);
0487: if (htest.highLine(1) > iEnd2) {
0488: iEnd2 = htest.highLine(1);
0489: }
0490: }
0491: } else {
0492: //No overlap, so h1End must match h2End.
0493: iEnd2 = h2End.lowLine(1);
0494: }
0495: } else {
0496: iEnd0 = h2End.highLine(0);
0497: iEnd2 = h2End.highLine(1);
0498:
0499: OverlapTestResult result = findOverlapIndex(h2End, v12,
0500: diff12Index);
0501: if (result.overlapFound) {
0502: Hunk h = (Hunk) v12.get(result.nearestIndex);
0503: iEnd1 = h.highLine(0);
0504:
0505: OverlapTestResult result2 = findOverlapIndex(h1End,
0506: v12, diff12Index);
0507: if (result.overlapFound) {
0508: Hunk htest = (Hunk) v12.get(result2.nearestIndex);
0509: if (htest.highLine(0) > iEnd1) {
0510: iEnd1 = htest.highLine(0);
0511: }
0512: }
0513: } else {
0514: //No overlap, so h1End must match h2End.
0515: iEnd2 = h2End.lowLine(1);
0516: }
0517: }
0518:
0519: rtn.diff = DiffType.DIFF_ALL;
0520: rtn.setRange(iBegin0, iEnd0, iBegin1, iEnd1, iBegin2, iEnd2);
0521:
0522: returnVal.hunk3 = rtn;
0523: returnVal.nextIndex01 = lastIndex01 + 1;
0524: returnVal.nextIndex02 = lastIndex02 + 1;
0525:
0526: return returnVal;
0527: }
0528:
0529: private boolean hunk1HasLowest0(Hunk h1, Hunk h2) {
0530: boolean h1Lowest = false;
0531: if (h1.lowLine(0) < h2.lowLine(0)) {
0532: h1Lowest = true;
0533: } else {
0534: h1Lowest = false;
0535: }
0536: return h1Lowest;
0537: }
0538:
0539: private boolean hunk1HasHighest0(Hunk h1, Hunk h2) {
0540: boolean h1Highest = false;
0541: if (h1.highLine(0) > h2.highLine(0)) {
0542: h1Highest = true;
0543: } else {
0544: h1Highest = false;
0545: }
0546: return h1Highest;
0547: }
0548:
0549: // private void addOverLapHunks(Vector buildDiff3, Vector v01, Vector v02, Vector v12,
0550: // int index01, int index02){
0551: // OverlapIndexes overlap = getEndOfOverlap(v01, v02, index01, index02);
0552: //
0553: // boolean keepBuilding = true;
0554: // while(keepBuilding){
0555: // Hunk h1 = (Hunk)v01.get(index01);
0556: // int subIndex02 = index02;
0557: // Hunk h2 = (Hunk)v02.get(subIndex02);
0558: // boolean check = true;
0559: // while(check){
0560: //
0561: // int begin01 = h1.lowLine(0);
0562: // int end01 = h1.highLine(0);
0563: // int begin02 = h2.lowLine(0);
0564: // int end02= h2.highLine(0);
0565: //
0566: // Range range1 = new Range(begin01, end01);
0567: // Range range2 = new Range(begin02, end02);
0568: // Range intersection = range1.intersection(range2);
0569: // Range before2 = null;
0570: // Range after2 = null;
0571: // Range before1 = null;
0572: // Range after1 = null;
0573: //
0574: // Hunk3 firstHunk = null;
0575: //
0576: // if (begin01 < begin02){
0577: // before2 = new Range(begin01, begin02 - 1);
0578: // firstHunk = new Hunk3();
0579: // firstHunk.diff = DiffType.DIFF_2ND;
0580: // firstHunk.setRange(h1.lowLine(0),
0581: // h1.highLine(0),
0582: // h1.lowLine(1),
0583: // h1.highLine(1),
0584: // )
0585: // }
0586: // else if (begin02 < begin01){
0587: // before1 = new Range(begin02, begin01 - 1);
0588: // }
0589: //
0590: //
0591: //
0592: // if (end01 > end02){
0593: // after2 = new Range(end02 + 1, end01);
0594: // }
0595: // else if (end02 > end01){
0596: // after1 = new Range(end01 + 1, end02);
0597: // }
0598: //
0599: //
0600: //
0601: //
0602: // subIndex02++;
0603: // if (subIndex02 > overlap.endIndex02){
0604: // check = false;
0605: // }
0606: // else{
0607: // h2 = (Hunk)v02.get(subIndex02);
0608: // }
0609: // }
0610: //
0611: // }
0612: // }
0613:
0614: private OverlapIndexes getEndOfOverlap(Vector v01, Vector v02,
0615: int index01, int index02) {
0616: OverlapIndexes result = new OverlapIndexes();
0617:
0618: boolean keepBuilding = true;
0619: Hunk h1 = (Hunk) v01.get(index01);
0620: Hunk h2 = (Hunk) v02.get(index02);
0621: while (keepBuilding) {
0622: int search01 = index01;
0623: int search02 = index02;
0624: boolean overlap01Found = false;
0625: boolean overlap02Found = false;
0626: h1 = (Hunk) v01.get(search01);
0627: while (doHunksOverlap(h1, (Hunk) v02.get(search02 + 1))) {
0628: search02++;
0629: overlap02Found = true;
0630: }
0631: h2 = (Hunk) v02.get(search02);
0632: while (doHunksOverlap((Hunk) v01.get(search01 + 1), h2)) {
0633: search01++;
0634: overlap01Found = true;
0635: }
0636:
0637: index01 = search01;
0638: index02 = search02;
0639:
0640: if (overlap01Found || overlap02Found) {
0641: keepBuilding = true;
0642: } else {
0643: keepBuilding = false;
0644: }
0645: }
0646: result.endIndex01 = index01;
0647: result.endIndex02 = index02;
0648: return result;
0649: }
0650:
0651: private OverlapTestResult findOverlapIndex(Hunk hunk,
0652: Vector diffVector, int startIndex) {
0653: OverlapTestResult result = new OverlapTestResult();
0654: int begin0 = hunk.lowLine(0);
0655: int end0 = hunk.highLine(0);
0656:
0657: boolean continueSearching = true;
0658:
0659: int searchIndex = startIndex;
0660: while (continueSearching) {
0661: Hunk checkHunk = (Hunk) diffVector.get(searchIndex);
0662: if (doHunksOverlap(hunk, checkHunk)) {
0663: result.nearestIndex = searchIndex;
0664: result.overlapFound = true;
0665: continueSearching = false;
0666: } else if (isHunkOneBeforeHunkTwo(hunk, checkHunk)) {
0667: //We've gone past the point where there can be a match.
0668: result.nearestIndex = searchIndex - 1;
0669: result.overlapFound = false;
0670: continueSearching = false;
0671: } else {
0672: searchIndex++;
0673: if (searchIndex >= diffVector.size()) {
0674: result.nearestIndex = searchIndex - 1;
0675: result.overlapFound = false;
0676: continueSearching = false;
0677: }
0678: }
0679: }
0680: return result;
0681: }
0682:
0683: /**
0684: * Returns true if Hunk 1 refers to a region of file 0 entirely before the
0685: * region reference by hunk 2.
0686: */
0687: private boolean isHunkOneBeforeHunkTwo(Hunk h1, Hunk h2) {
0688: boolean h1BeforeH2 = false;
0689: int end1 = h1.highLine(0);
0690: int start2 = h2.lowLine(0);
0691:
0692: if (end1 < start2) {
0693: h1BeforeH2 = true;
0694: }
0695: return h1BeforeH2;
0696: }
0697:
0698: /**
0699: * Returns true if both hunks reflect the exact same change to both files.
0700: */
0701: private boolean doHunksMatch(Hunk h1, Hunk h2) {
0702: boolean match = false;
0703: if (doHunkRangesMatch(h1, h2)) {
0704: //Are hunks of same type?
0705: if (h1 instanceof HunkAdd && h2 instanceof HunkAdd) {
0706: HunkAdd add1 = (HunkAdd) h1;
0707: HunkAdd add2 = (HunkAdd) h2;
0708: if (add1.getNewContents().equals(add2.getNewContents())) {
0709: match = true;
0710: }
0711: } //end if HunkAdd
0712: else if (h1 instanceof HunkDel && h2 instanceof HunkDel) {
0713: HunkDel del1 = (HunkDel) h1;
0714: HunkDel del2 = (HunkDel) h2;
0715: if (del1.getOldContents().equals(del2.getOldContents())) {
0716: match = true;
0717: }
0718: } //end if HunkDel
0719: else {
0720: //Must be change
0721: HunkChange chg1 = (HunkChange) h1;
0722: HunkChange chg2 = (HunkChange) h2;
0723: if (chg1.getNewContents().equals(chg2.getNewContents())) {
0724: match = true;
0725: }
0726: }
0727: }
0728: return match;
0729: }
0730:
0731: /**
0732: * Returns true if both hunks point to the exact same regions file 0.
0733: */
0734: private boolean doHunkRangesMatch(Hunk h1, Hunk h2) {
0735: boolean match = false;
0736:
0737: int start01 = h1.lowLine(0);
0738: int end01 = h1.highLine(0);
0739: int start02 = h2.lowLine(0);
0740: int end02 = h2.highLine(0);
0741:
0742: if (start01 == start02 && end01 == end02) {
0743:
0744: match = true;
0745: }
0746: return match;
0747: }
0748:
0749: private boolean doHunksOverlap(Hunk h1, Hunk h2) {
0750: boolean overlap = false;
0751:
0752: int start1 = h1.lowLine(0);
0753: int end1 = h1.highLine(0);
0754: int start2 = h2.lowLine(0);
0755: int end2 = h2.highLine(0);
0756:
0757: if (isNumWithinRange(start1, start2, end2)
0758: || isNumWithinRange(end1, start2, end2)) {
0759: overlap = true;
0760: }
0761:
0762: return overlap;
0763: }
0764:
0765: private boolean isNumWithinRange(int num, int startRange,
0766: int endRange) {
0767: if (num >= startRange && num <= endRange) {
0768: return true;
0769: } else {
0770: return false;
0771: }
0772: }
0773:
0774: private Vector getHunk3(Vector v0, Vector v1) {
0775:
0776: Hunk currentHunk[] = new Hunk[2];
0777: Hunk previousHunk[] = new Hunk[2];
0778: Hunk current[] = new Hunk[2];
0779:
0780: int high_water_mark;
0781: int high_water_thread, base_water_thread, other_thread;
0782:
0783: Hunk high_water_diff, other_diff;
0784:
0785: Hunk3 result;
0786: Hunk3 tmpblock;
0787: Hunk3 last_diff3;
0788: Hunk3 zero_diff3 = null;
0789:
0790: Vector v = new Vector();
0791:
0792: result = null;
0793:
0794: last_diff3 = zero_diff3;
0795:
0796: if (v0.size() != 0)
0797: current[0] = (Hunk) v0.elementAt(0);
0798: else
0799: current[0] = null;
0800: if (v1.size() != 0)
0801: current[1] = (Hunk) v1.elementAt(0);
0802: else
0803: current[1] = null;
0804:
0805: while (current[0] != null || current[1] != null) {
0806: currentHunk[0] = null;
0807: currentHunk[1] = null;
0808: previousHunk[0] = null;
0809: previousHunk[1] = null;
0810:
0811: if (current[0] == null)
0812: base_water_thread = 1;
0813: else if (current[1] == null)
0814: base_water_thread = 0;
0815: else if (current[0].lowLine(1) > current[1].lowLine(1))
0816: base_water_thread = 1;
0817: else
0818: base_water_thread = 0;
0819: high_water_thread = base_water_thread;
0820: high_water_diff = current[high_water_thread];
0821:
0822: high_water_mark = high_water_diff.highLine(1);
0823: previousHunk[high_water_thread] = high_water_diff;
0824: currentHunk[high_water_thread] = high_water_diff;
0825: current[high_water_thread] = high_water_diff.next;
0826: (previousHunk[high_water_thread]).next = null;
0827: other_thread = high_water_thread ^ 0x1;
0828: other_diff = current[other_thread];
0829:
0830: while (other_diff != null
0831: && other_diff.lowLine(1) <= high_water_mark + 1) {
0832: if (currentHunk[other_thread] != null)
0833: (previousHunk[other_thread]).next = other_diff;
0834: else
0835: currentHunk[other_thread] = other_diff;
0836: previousHunk[other_thread] = other_diff;
0837: current[other_thread] = (current[other_thread]).next;
0838: other_diff.next = null;
0839: if (high_water_mark < other_diff.highLine(1)) {
0840: high_water_thread ^= 1;
0841: high_water_diff = other_diff;
0842: high_water_mark = other_diff.highLine(1);
0843: }
0844: other_thread = high_water_thread ^ 0x1;
0845: other_diff = current[other_thread];
0846: } //end while other diff not null
0847: tmpblock = using_to_diff3_block(currentHunk, previousHunk,
0848: base_water_thread, high_water_thread, last_diff3);
0849: if (tmpblock != null) {
0850: System.out.println("[diff] type=" + tmpblock.diff);
0851: v.addElement(tmpblock);
0852: last_diff3 = tmpblock;
0853: }
0854: }
0855: return v;
0856: }
0857:
0858: private Hunk3 using_to_diff3_block(Hunk using[], Hunk last_using[],
0859: int low_thread, int high_thread, Hunk3 last_diff3) {
0860:
0861: int d, i;
0862: int low[] = new int[2];
0863: int high[] = new int[2];
0864: Hunk3 result = new Hunk3();
0865:
0866: int lowc = using[low_thread].lowLine(1);
0867: int highc = last_using[high_thread].highLine(1);
0868:
0869: for (d = 0; d < 2; d++)
0870: if (using[d] != null) {
0871: low[d] = lowc - using[d].lowLine(1)
0872: + using[d].lowLine(0);
0873: high[d] = highc - last_using[d].highLine(1)
0874: + last_using[d].highLine(0);
0875: } else {
0876: if (last_diff3 == null) {
0877: low[d] = lowc;
0878: high[d] = highc;
0879: } else {
0880: low[d] = lowc - last_diff3.highLine(2)
0881: + last_diff3.highLine(d);
0882: high[d] = highc - last_diff3.highLine(2)
0883: + last_diff3.highLine(d);
0884: }
0885: }
0886: result.setRange(low[0], high[0], low[1], high[1], lowc, highc);
0887: for (d = 0; d < 2; d++) {
0888: }
0889: for (d = 0; d < 2; d++) {
0890: Hunk u = using[d];
0891: int lo = low[d];
0892: int hi = high[d];
0893: for (i = 0; i + lo < ((u != null) ? u.lowLine(1) : hi + 1); i++) {
0894: }
0895: //for()
0896: {
0897: }
0898:
0899: }
0900: Hunk3Type type = new Hunk3Type();
0901: if (using[0] == null) {
0902: result.diff = DiffType.DIFF_2ND;
0903: type.setInFileType(Hunk3Type.FILE_ONE);
0904: if (using[1] instanceof HunkAdd)
0905: type.setDifferenceType(Hunk3Type.REMOVE);
0906: else if (using[1] instanceof HunkDel)
0907: type.setDifferenceType(Hunk3Type.ADD);
0908: else
0909: type.setDifferenceType(Hunk3Type.CHANGE);
0910: } else if (using[1] == null) {
0911: result.diff = DiffType.DIFF_1ST;
0912: type.setInFileType(Hunk3Type.BOTH_FILES_SAME);
0913: if (using[0] instanceof HunkAdd)
0914: type.setDifferenceType(Hunk3Type.ADD);
0915: else if (using[0] instanceof HunkDel)
0916: type.setDifferenceType(Hunk3Type.REMOVE);
0917: else
0918: type.setDifferenceType(Hunk3Type.CHANGE);
0919: } else {
0920: if (areHunksEquivelent(using[0], using[1])
0921: && areRangesSame(result.lowLine(0), result
0922: .highLine(0), result.lowLine(1), result
0923: .highLine(1))) {
0924: result.diff = DiffType.DIFF_3RD;
0925: type.setInFileType(Hunk3Type.FILE_TWO);
0926: if (using[0] instanceof HunkAdd)
0927: type.setDifferenceType(Hunk3Type.ADD);
0928: else if (using[0] instanceof HunkDel)
0929: type.setDifferenceType(Hunk3Type.REMOVE);
0930: else
0931: type.setDifferenceType(Hunk3Type.CHANGE);
0932: } else {
0933: result.diff = DiffType.DIFF_ALL;
0934: type.setInFileType(Hunk3Type.BOTH_FILES_DIFFERENT);
0935: //for now, let's always call this a change.
0936: type.setDifferenceType(Hunk3Type.CHANGE);
0937: }
0938: }
0939: result.setType(type);
0940: return result;
0941: }
0942:
0943: private boolean areRangesSame(int start0, int end0, int start1,
0944: int end1) {
0945: boolean equal = false;
0946: int numLines = (end0 + 1) - start0;
0947: if (((end1 + 1) - start1) == numLines) {
0948: for (int i = 0; i < numLines; i++) {
0949: String line0 = reader0.getLine(start0 + i);
0950: String line1 = reader1.getLine(start1 + i);
0951: if (line0.equals(line1)) {
0952: equal = true;
0953: } else {
0954: equal = false;
0955: break;
0956: }
0957: }
0958: }
0959: return equal;
0960: }
0961:
0962: private boolean areHunksEquivelent(Hunk h1, Hunk h2) {
0963: boolean equal = false;
0964: if (areHunksEquivelent(h1, h2, 1)) {
0965: equal = true;
0966: }
0967: return equal;
0968: }
0969:
0970: private boolean areHunksEquivelent(Hunk h1, Hunk h2, int fileNum) {
0971: boolean equal = false;
0972: int numLines = h1.numLines(fileNum);
0973: if (h2.numLines(fileNum) == numLines) {
0974: for (int i = 0; i < numLines; i++) {
0975: String line1 = h1.relNum(fileNum, i);
0976: String line2 = h2.relNum(fileNum, i);
0977: if ((line1 == null && line2 == null)
0978: || line1.equals(line2)) {
0979: equal = true;
0980: } else {
0981: equal = false;
0982: break;
0983: }
0984: }
0985: }
0986: return equal;
0987: }
0988:
0989: /**
0990: * Returns a vector containing Hunk3.
0991: */
0992: public Vector getHunk3() {
0993: return v;
0994: }
0995:
0996: /**
0997: * Return the hunk3 at the specified index.
0998: *
0999: * @param i index of the Hunk that will be returned.
1000: */
1001: public Hunk3 hunk3At(int i) {
1002: return (Hunk3) v.elementAt(i);
1003: }
1004:
1005: /**
1006: * Returns the number of hunk3 in the vector.
1007: */
1008: public int numberOfHunk3() {
1009: return v.size();
1010: }
1011:
1012: /**
1013: * Print Hunk3 with normal format.
1014: */
1015: public void print() {
1016: for (Enumeration e = v.elements(); e.hasMoreElements();)
1017: System.out.print(((Hunk3) e.nextElement()).convert());
1018: }
1019:
1020: /**
1021: * Save Hunk3 with normal format at the specified file.
1022: *
1023: * @param file file in which Hunks will be saved.
1024: */
1025: public void save(String file) throws IOException {
1026: PrintWriter out = new PrintWriter(new BufferedWriter(
1027: new FileWriter(file)));
1028: for (Enumeration e = v.elements(); e.hasMoreElements();)
1029: out.write(((Hunk3) e.nextElement()).convert());
1030: out.flush();
1031: out.close();
1032: }
1033:
1034: public void accept(Hunk3Visitor visitor) {
1035: Iterator itr = v.iterator();
1036: while (itr.hasNext()) {
1037: Hunk3 hunk = (Hunk3) itr.next();
1038: hunk.accpet(visitor);
1039: if (!visitor.continueVisit()) {
1040: break;
1041: }
1042: }
1043: }
1044:
1045: private class OverlapTestResult {
1046: public int nearestIndex = -1;
1047: public boolean overlapFound = false;
1048: }
1049:
1050: private class OverlapIndexes {
1051: public int endIndex01 = -1;
1052: public int endIndex02 = -1;
1053: }
1054:
1055: private class OverLapBuildResult {
1056: public Hunk3 hunk3;
1057: public int nextIndex01;
1058: public int nextIndex02;
1059: }
1060:
1061: private class Range {
1062: public Range(int begin, int end) {
1063: beginRange = begin;
1064: endRange = end;
1065: }
1066:
1067: public boolean isValid() {
1068: if (beginRange <= endRange && beginRange >= 0
1069: && endRange >= 0) {
1070: return true;
1071: } else {
1072: return false;
1073: }
1074: }
1075:
1076: public Range intersection(Range range) {
1077: int begin = range.beginRange;
1078: int end = range.endRange;
1079: if (this .beginRange > range.beginRange) {
1080: begin = this .beginRange;
1081: }
1082: if (this .endRange < range.endRange) {
1083: end = this .endRange;
1084: }
1085: Range intersection = new Range(begin, end);
1086: if (intersection.isValid()) {
1087: return intersection;
1088: } else {
1089: return null;
1090: }
1091: }
1092:
1093: public int beginRange = -1;
1094: public int endRange = -1;
1095: }
1096:
1097: }
|