You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jackrabbit.apache.org by tr...@apache.org on 2013/08/10 07:53:54 UTC
svn commit: r1512568 [32/39] - in /jackrabbit/commons/filevault/trunk: ./
parent/ vault-cli/ vault-cli/src/ vault-cli/src/main/
vault-cli/src/main/appassembler/ vault-cli/src/main/assembly/
vault-cli/src/main/java/ vault-cli/src/main/java/org/ vault-cl...
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DefaultDocumentSource.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DefaultDocumentSource.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DefaultDocumentSource.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DefaultDocumentSource.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,103 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+/**
+ * Provides a default document source
+ */
+public class DefaultDocumentSource implements DocumentSource {
+
+ /**
+ * some location information
+ */
+ private final String location;
+
+ /**
+ * the author
+ */
+ private final String author;
+
+ /**
+ * the date
+ */
+ private final long date;
+
+ /**
+ * the revision
+ */
+ private final String revision;
+
+ /**
+ * Creates a new default document source
+ *
+ * @param location some location information
+ * @param author the author of the document
+ * @param date some date of the document
+ * @param revision some revision of the document
+ */
+ public DefaultDocumentSource(String location, String author, long date, String revision) {
+ this.location = location;
+ this.author = author;
+ this.date = date;
+ this.revision = revision;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public String getLocation() {
+ return location;
+ }
+
+ /**
+ * Returns the revision information.
+ *
+ * {@inheritDoc}
+ */
+ public String getLabel() {
+ return revision;
+ }
+
+ /**
+ * Returns the author
+ * @return the author
+ */
+ public String getAuthor() {
+ return author;
+ }
+
+ /**
+ * Returns the date
+ * @return the date
+ */
+ public long getDate() {
+ return date;
+ }
+
+ /**
+ * Returns the revision
+ * @return the revision
+ */
+ public String getRevision() {
+ return revision;
+ }
+
+
+ public String toString() {
+ return author + ", " + revision;
+ }
+}
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Diff.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Diff.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Diff.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Diff.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,875 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+import java.util.HashMap;
+
+public class Diff {
+
+ /**
+ * Prepare to find differences between two arrays. Each element of
+ * the arrays is translated to an "equivalence number" based on
+ * the result of <code>equals</code>. The original Object arrays
+ * are no longer needed for computing the differences. They will
+ * be needed again later to print the results of the comparison as
+ * an edit script, if desired.
+ */
+ public Diff(Object[] a, Object[] b) {
+ HashMap h = new HashMap(a.length + b.length);
+ filevec[0] = new FileData(a, h);
+ filevec[1] = new FileData(b, h);
+ }
+
+ /**
+ * 1 more than the maximum equivalence value used for this or its
+ * sibling file.
+ */
+ private int equiv_max = 1;
+
+ /**
+ * When set to true, the comparison uses a heuristic to speed it up.
+ * With this heuristic, for files with a constant small density
+ * of changes, the algorithm is linear in the file size.
+ */
+ public boolean heuristic = false;
+
+ /**
+ * When set to true, the algorithm returns a guarranteed minimal
+ * set of changes. This makes things slower, sometimes much slower.
+ */
+ public boolean no_discards = false;
+
+ private int[] xvec, yvec; /* Vectors being compared. */
+ private int[] fdiag; /* Vector, indexed by diagonal, containing
+ the X coordinate of the point furthest
+ along the given diagonal in the forward
+ search of the edit matrix. */
+ private int[] bdiag; /* Vector, indexed by diagonal, containing
+ the X coordinate of the point furthest
+ along the given diagonal in the backward
+ search of the edit matrix. */
+ private int fdiagoff, bdiagoff;
+ private final FileData[] filevec = new FileData[2];
+ private int cost;
+
+ /**
+ * Find the midpoint of the shortest edit script for a specified
+ * portion of the two files.
+ * <p/>
+ * We scan from the beginnings of the files, and simultaneously from the ends,
+ * doing a breadth-first search through the space of edit-sequence.
+ * When the two searches meet, we have found the midpoint of the shortest
+ * edit sequence.
+ * <p/>
+ * The value returned is the number of the diagonal on which the midpoint lies.
+ * The diagonal number equals the number of inserted lines minus the number
+ * of deleted lines (counting only lines before the midpoint).
+ * The edit cost is stored into COST; this is the total number of
+ * lines inserted or deleted (counting only lines before the midpoint).
+ * <p/>
+ * This function assumes that the first lines of the specified portions
+ * of the two files do not match, and likewise that the last lines do not
+ * match. The caller must trim matching lines from the beginning and end
+ * of the portions it is going to specify.
+ * <p/>
+ * Note that if we return the "wrong" diagonal value, or if
+ * the value of bdiag at that diagonal is "wrong",
+ * the worst this can do is cause suboptimal diff output.
+ * It cannot cause incorrect diff output.
+ */
+
+ private int diag(int xoff, int xlim, int yoff, int ylim) {
+ final int[] fd = fdiag; // Give the compiler a chance.
+ final int[] bd = bdiag; // Additional help for the compiler.
+ final int[] xv = xvec; // Still more help for the compiler.
+ final int[] yv = yvec; // And more and more . . .
+ final int dmin = xoff - ylim; // Minimum valid diagonal.
+ final int dmax = xlim - yoff; // Maximum valid diagonal.
+ final int fmid = xoff - yoff; // Center diagonal of top-down search.
+ final int bmid = xlim - ylim; // Center diagonal of bottom-up search.
+ int fmin = fmid, fmax = fmid; // Limits of top-down search.
+ int bmin = bmid, bmax = bmid; // Limits of bottom-up search.
+ // True if southeast corner is on an odd diagonal with respect to the northwest.
+ final boolean odd = (fmid - bmid & 1) != 0;
+
+ fd[fdiagoff + fmid] = xoff;
+ bd[bdiagoff + bmid] = xlim;
+
+ for (int c = 1; ; ++c) {
+ int d; /* Active diagonal. */
+ boolean big_snake = false;
+
+ /* Extend the top-down search by an edit step in each diagonal. */
+ if (fmin > dmin)
+ fd[fdiagoff + --fmin - 1] = -1;
+ else
+ ++fmin;
+ if (fmax < dmax)
+ fd[fdiagoff + ++fmax + 1] = -1;
+ else
+ --fmax;
+ for (d = fmax; d >= fmin; d -= 2) {
+ int x, y, oldx, tlo = fd[fdiagoff + d - 1], thi = fd[fdiagoff + d + 1];
+
+ if (tlo >= thi)
+ x = tlo + 1;
+ else
+ x = thi;
+ oldx = x;
+ y = x - d;
+ while (x < xlim && y < ylim && xv[x] == yv[y]) {
+ ++x;
+ ++y;
+ }
+ if (x - oldx > 20)
+ big_snake = true;
+ fd[fdiagoff + d] = x;
+ if (odd && bmin <= d && d <= bmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) {
+ cost = 2 * c - 1;
+ return d;
+ }
+ }
+
+ /* Similar extend the bottom-up search. */
+ if (bmin > dmin)
+ bd[bdiagoff + --bmin - 1] = Integer.MAX_VALUE;
+ else
+ ++bmin;
+ if (bmax < dmax)
+ bd[bdiagoff + ++bmax + 1] = Integer.MAX_VALUE;
+ else
+ --bmax;
+ for (d = bmax; d >= bmin; d -= 2) {
+ int x, y, oldx, tlo = bd[bdiagoff + d - 1], thi = bd[bdiagoff + d + 1];
+
+ if (tlo < thi)
+ x = tlo;
+ else
+ x = thi - 1;
+ oldx = x;
+ y = x - d;
+ while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1]) {
+ --x;
+ --y;
+ }
+ if (oldx - x > 20)
+ big_snake = true;
+ bd[bdiagoff + d] = x;
+ if (!odd && fmin <= d && d <= fmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) {
+ cost = 2 * c;
+ return d;
+ }
+ }
+
+ /*
+ Heuristic: check occasionally for a diagonal that has made
+ lots of progress compared with the edit distance.
+ If we have any such, find the one that has made the most
+ progress and return it as if it had succeeded.
+
+ With this heuristic, for files with a constant small density
+ of changes, the algorithm is linear in the file size.
+ */
+
+ if (c > 200 && big_snake && heuristic) {
+ int best = 0;
+ int bestpos = -1;
+
+ for (d = fmax; d >= fmin; d -= 2) {
+ int dd = d - fmid;
+ if ((fd[fdiagoff + d] - xoff) * 2 - dd > 12 * (c + (dd > 0 ? dd : -dd))) {
+ if (fd[fdiagoff + d] * 2 - dd > best
+ && fd[fdiagoff + d] - xoff > 20
+ && fd[fdiagoff + d] - d - yoff > 20) {
+ int k;
+ int x = fd[fdiagoff + d];
+
+ // We have a good enough best diagonal;
+ // now insist that it end with a significant snake.
+ for (k = 1; k <= 20; k++)
+ if (xvec[x - k] != yvec[x - d - k])
+ break;
+
+ if (k == 21) {
+ best = fd[fdiagoff + d] * 2 - dd;
+ bestpos = d;
+ }
+ }
+ }
+ }
+ if (best > 0) {
+ cost = 2 * c - 1;
+ return bestpos;
+ }
+
+ best = 0;
+ for (d = bmax; d >= bmin; d -= 2) {
+ int dd = d - bmid;
+ if ((xlim - bd[bdiagoff + d]) * 2 + dd > 12 * (c + (dd > 0 ? dd : -dd))) {
+ if ((xlim - bd[bdiagoff + d]) * 2 + dd > best
+ && xlim - bd[bdiagoff + d] > 20
+ && ylim - (bd[bdiagoff + d] - d) > 20) {
+ // We have a good enough best diagonal;
+ // now insist that it end with a significant snake.
+ int k;
+ int x = bd[bdiagoff + d];
+
+ for (k = 0; k < 20; k++)
+ if (xvec[x + k] != yvec[x - d + k])
+ break;
+ if (k == 20) {
+ best = (xlim - bd[bdiagoff + d]) * 2 + dd;
+ bestpos = d;
+ }
+ }
+ }
+ }
+ if (best > 0) {
+ cost = 2 * c - 1;
+ return bestpos;
+ }
+ }
+ }
+ }
+
+ /**
+ * Compare in detail contiguous subsequences of the two files
+ * which are known, as a whole, to match each other.
+ * <p/>
+ * The results are recorded in the vectors filevec[N].changed_flag, by
+ * storing a 1 in the element for each line that is an insertion or deletion.
+ * <p/>
+ * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
+ * <p/>
+ * Note that XLIM, YLIM are exclusive bounds.
+ * All line numbers are origin-0 and discarded lines are not counted.
+ */
+ private void compareseq(int xoff, int xlim, int yoff, int ylim) {
+ /* Slide down the bottom initial diagonal. */
+ while (xoff < xlim && yoff < ylim && xvec[xoff] == yvec[yoff]) {
+ ++xoff;
+ ++yoff;
+ }
+ /* Slide up the top initial diagonal. */
+ while (xlim > xoff && ylim > yoff && xvec[xlim - 1] == yvec[ylim - 1]) {
+ --xlim;
+ --ylim;
+ }
+
+ /* Handle simple cases. */
+ if (xoff == xlim)
+ while (yoff < ylim)
+ filevec[1].changed_flag[1 + filevec[1].realindexes[yoff++]] = true;
+ else if (yoff == ylim)
+ while (xoff < xlim)
+ filevec[0].changed_flag[1 + filevec[0].realindexes[xoff++]] = true;
+ else {
+ /* Find a point of correspondence in the middle of the files. */
+
+ int d = diag(xoff, xlim, yoff, ylim);
+ int c = cost;
+ int f = fdiag[fdiagoff + d];
+ int b = bdiag[bdiagoff + d];
+
+ if (c == 1) {
+ /*
+ This should be impossible, because it implies that
+ one of the two subsequences is empty,
+ and that case was handled above without calling `diag'.
+ Let's verify that this is true.
+ */
+ throw new IllegalArgumentException("Empty subsequence");
+ } else {
+ /* Use that point to split this problem into two subproblems. */
+ compareseq(xoff, b, yoff, b - d);
+ /*
+ This used to use f instead of b,
+ but that is incorrect!
+ It is not necessarily the case that diagonal d
+ has a snake from b to f.
+ */
+ compareseq(b, xlim, b - d, ylim);
+ }
+ }
+ }
+
+ /**
+ * Discard lines from one file that have no matches in the other file.
+ */
+ private void discard_confusing_lines() {
+ filevec[0].discard_confusing_lines(filevec[1]);
+ filevec[1].discard_confusing_lines(filevec[0]);
+ }
+
+ private boolean inhibit = false;
+
+ /**
+ * Adjust inserts/deletes of blank lines to join changes
+ * as much as possible.
+ */
+ private void shift_boundaries() {
+ if (inhibit)
+ return;
+ filevec[0].shift_boundaries(filevec[1]);
+ filevec[1].shift_boundaries(filevec[0]);
+ }
+
+ /**
+ * Scan the tables of which lines are inserted and deleted,
+ * producing an edit script in reverse order.
+ */
+ private Change build_reverse_script() {
+ Change script = null;
+ final boolean[] changed0 = filevec[0].changed_flag;
+ final boolean[] changed1 = filevec[1].changed_flag;
+ final int len0 = filevec[0].buffered_lines;
+ final int len1 = filevec[1].buffered_lines;
+
+ /* Note that changedN[len0] does exist, and contains 0. */
+
+ int i0 = 0, i1 = 0;
+
+ while (i0 < len0 || i1 < len1) {
+ if (changed0[1 + i0] || changed1[1 + i1]) {
+ int line0 = i0, line1 = i1;
+
+ /* Find # lines changed here in each file. */
+ while (changed0[1 + i0]) ++i0;
+ while (changed1[1 + i1]) ++i1;
+
+ /* Record this change. */
+ script = new Change(line0, line1, i0 - line0, i1 - line1, script);
+ }
+
+ /* We have reached lines in the two files that match each other. */
+ i0++;
+ i1++;
+ }
+
+ return script;
+ }
+
+ /**
+ * Scan the tables of which lines are inserted and deleted,
+ * producing an edit script in forward order.
+ */
+ private Change build_script() {
+ Change script = null;
+ final boolean[] changed0 = filevec[0].changed_flag;
+ final boolean[] changed1 = filevec[1].changed_flag;
+ final int len0 = filevec[0].buffered_lines;
+ final int len1 = filevec[1].buffered_lines;
+ int i0 = len0, i1 = len1;
+
+ /* Note that changedN[-1] does exist, and contains 0. */
+
+ while (i0 >= 0 || i1 >= 0) {
+ if (changed0[i0] || changed1[i1]) {
+ int line0 = i0, line1 = i1;
+
+ /* Find # lines changed here in each file. */
+ while (changed0[i0]) --i0;
+ while (changed1[i1]) --i1;
+
+ /* Record this change. */
+ script = new Change(i0, i1, line0 - i0, line1 - i1, script);
+ }
+
+ /* We have reached lines in the two files that match each other. */
+ i0--;
+ i1--;
+ }
+
+ return script;
+ }
+
+ /**
+ * Report the differences of two files. DEPTH is the current directory depth.
+ */
+ public Change diff_2(final boolean reverse) {
+
+ /*
+ Some lines are obviously insertions or deletions
+ because they don't match anything. Detect them now,
+ and avoid even thinking about them in the main comparison algorithm.
+ */
+
+ discard_confusing_lines();
+
+ // Now do the main comparison algorithm, considering just the
+ // undiscarded lines.
+
+ xvec = filevec[0].undiscarded;
+ yvec = filevec[1].undiscarded;
+
+ int diags =
+ filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines + 3;
+ fdiag = new int[diags];
+ fdiagoff = filevec[1].nondiscarded_lines + 1;
+ bdiag = new int[diags];
+ bdiagoff = filevec[1].nondiscarded_lines + 1;
+
+ compareseq(0, filevec[0].nondiscarded_lines,
+ 0, filevec[1].nondiscarded_lines);
+ fdiag = null;
+ bdiag = null;
+
+ // Modify the results slightly to make them prettier
+ // in cases where that can validly be done.
+
+ shift_boundaries();
+
+ // Get the results of comparison in the form of a chain
+ // of `struct change's -- an edit script.
+
+ if (reverse)
+ return build_reverse_script();
+ else
+ return build_script();
+ }
+
+ /**
+ * The result of comparison is an "edit script": a chain of change objects.
+ * Each change represents one place where some lines are deleted
+ * and some are inserted.
+ * <p/>
+ * LINE0 and LINE1 are the first affected lines in the two files (origin 0).
+ * DELETED is the number of lines deleted here from file 0.
+ * INSERTED is the number of lines inserted here in file 1.
+ * <p/>
+ * If DELETED is 0 then LINE0 is the number of the line before
+ * which the insertion was done; vice versa for INSERTED and LINE1.
+ */
+ public static class Change {
+ /**
+ * Previous or next edit command.
+ */
+ public Change nextChange;
+ /**
+ * # lines of file 1 changed here.
+ */
+ public final int inserted;
+ /**
+ * # lines of file 0 changed here.
+ */
+ public final int deleted;
+ /**
+ * Line number of 1st deleted line.
+ */
+ public final int line0;
+ /**
+ * Line number of 1st inserted line.
+ */
+ public final int line1;
+
+ /**
+ * Cons an additional entry onto the front of an edit script OLD.
+ * LINE0 and LINE1 are the first affected lines in the two files (origin 0).
+ * DELETED is the number of lines deleted here from file 0.
+ * INSERTED is the number of lines inserted here in file 1.
+ * <p/>
+ * If DELETED is 0 then LINE0 is the number of the line before
+ * which the insertion was done; vice versa for INSERTED and LINE1.
+ */
+ Change(int line0, int line1, int deleted, int inserted, Change old) {
+ this.line0 = line0;
+ this.line1 = line1;
+ this.inserted = inserted;
+ this.deleted = deleted;
+ this.nextChange = old;
+ }
+ }
+
+ /**
+ * Data on one input file being compared.
+ */
+ class FileData {
+
+ /**
+ * Allocate changed array for the results of comparison.
+ */
+ void clear() {
+ /* Allocate a flag for each line of each file, saying whether that line
+ is an insertion or deletion.
+ Allocate an extra element, always zero, at each end of each vector.
+ */
+ changed_flag = new boolean[buffered_lines + 2];
+ }
+
+ /**
+ * Return equiv_count[I] as the number of lines in this file
+ * that fall in equivalence class I.
+ *
+ * @return the array of equivalence class counts.
+ */
+ int[] equivCount() {
+ int[] equiv_count = new int[equiv_max];
+ for (int i = 0; i < buffered_lines; ++i)
+ ++equiv_count[equivs[i]];
+ return equiv_count;
+ }
+
+ /**
+ * Discard lines that have no matches in another file.
+ * <p/>
+ * A line which is discarded will not be considered by the actual
+ * comparison algorithm; it will be as if that line were not in the file.
+ * The file's `realindexes' table maps virtual line numbers
+ * (which don't count the discarded lines) into real line numbers;
+ * this is how the actual comparison algorithm produces results
+ * that are comprehensible when the discarded lines are counted.
+ * <p/>
+ * When we discard a line, we also mark it as a deletion or insertion
+ * so that it will be printed in the output.
+ *
+ * @param f the other file
+ */
+ void discard_confusing_lines(FileData f) {
+ clear();
+ /* Set up table of which lines are going to be discarded. */
+ final byte[] discarded = discardable(f.equivCount());
+
+ /*
+ Don't really discard the provisional lines except when they occur
+ in a run of discardables, with nonprovisionals at the beginning
+ and end.
+ */
+ filterDiscards(discarded);
+
+ /* Actually discard the lines. */
+ discard(discarded);
+ }
+
+ /**
+ * Mark to be discarded each line that matches no line of another file.
+ * If a line matches many lines, mark it as provisionally discardable.
+ *
+ * @param counts The count of each equivalence number for the other file.
+ * @return 0=nondiscardable, 1=discardable or 2=provisionally discardable
+ * for each line
+ */
+
+ private byte[] discardable(final int[] counts) {
+ final int end = buffered_lines;
+ final byte[] discards = new byte[end];
+ final int[] equivs = this.equivs;
+ int many = 5;
+ int tem = end / 64;
+
+ /*
+ Multiply MANY by approximate square root of number of lines.
+ That is the threshold for provisionally discardable lines.
+ */
+ while ((tem = tem >> 2) > 0)
+ many *= 2;
+
+ for (int i = 0; i < end; i++) {
+ int nmatch;
+ if (equivs[i] == 0)
+ continue;
+ nmatch = counts[equivs[i]];
+ if (nmatch == 0)
+ discards[i] = 1;
+ else if (nmatch > many)
+ discards[i] = 2;
+ }
+ return discards;
+ }
+
+ /**
+ * Don't really discard the provisional lines except when they occur
+ * in a run of discardables, with nonprovisionals at the beginning
+ * and end.
+ */
+
+ private void filterDiscards(final byte[] discards) {
+ final int end = buffered_lines;
+
+ for (int i = 0; i < end; i++) {
+ /* Cancel provisional discards not in middle of run of discards. */
+ if (discards[i] == 2)
+ discards[i] = 0;
+ else if (discards[i] != 0) {
+ /* We have found a nonprovisional discard. */
+ int j;
+ int length;
+ int provisional = 0;
+
+ /*
+ Find end of this run of discardable lines.
+ Count how many are provisionally discardable.
+ */
+ for (j = i; j < end; j++) {
+ if (discards[j] == 0)
+ break;
+ if (discards[j] == 2)
+ ++provisional;
+ }
+
+ /* Cancel provisional discards at end, and shrink the run. */
+ while (j > i && discards[j - 1] == 2) {
+ discards[--j] = 0;
+ --provisional;
+ }
+
+ /*
+ Now we have the length of a run of discardable lines
+ whose first and last are not provisional.
+ */
+ length = j - i;
+
+ /*
+ If 1/4 of the lines in the run are provisional,
+ cancel discarding of all provisional lines in the run.
+ */
+ if (provisional * 4 > length) {
+ while (j > i)
+ if (discards[--j] == 2)
+ discards[j] = 0;
+ } else {
+ int consec;
+ int minimum = 1;
+ int tem = length / 4;
+
+ /*
+ MINIMUM is approximate square root of LENGTH/4.
+ A subrun of two or more provisionals can stand
+ when LENGTH is at least 16.
+ A subrun of 4 or more can stand when LENGTH >= 64.
+ */
+ while ((tem = tem >> 2) > 0)
+ minimum *= 2;
+ minimum++;
+
+ /*
+ Cancel any subrun of MINIMUM or more provisionals
+ within the larger run.
+ */
+ for (j = 0, consec = 0; j < length; j++)
+ if (discards[i + j] != 2)
+ consec = 0;
+ else if (minimum == ++consec)
+ /* Back up to start of subrun, to cancel it all. */
+ j -= consec;
+ else if (minimum < consec)
+ discards[i + j] = 0;
+
+ /*
+ Scan from beginning of run
+ until we find 3 or more nonprovisionals in a row
+ or until the first nonprovisional at least 8 lines in.
+ Until that point, cancel any provisionals.
+ */
+ for (j = 0, consec = 0; j < length; j++) {
+ if (j >= 8 && discards[i + j] == 1)
+ break;
+ if (discards[i + j] == 2) {
+ consec = 0;
+ discards[i + j] = 0;
+ } else if (discards[i + j] == 0)
+ consec = 0;
+ else
+ consec++;
+ if (consec == 3)
+ break;
+ }
+
+ /* I advances to the last line of the run. */
+ i += length - 1;
+
+ /* Same thing, from end. */
+ for (j = 0, consec = 0; j < length; j++) {
+ if (j >= 8 && discards[i - j] == 1)
+ break;
+ if (discards[i - j] == 2) {
+ consec = 0;
+ discards[i - j] = 0;
+ } else if (discards[i - j] == 0)
+ consec = 0;
+ else
+ consec++;
+ if (consec == 3)
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Actually discard the lines.
+ *
+ * @param discards flags lines to be discarded
+ */
+ private void discard(final byte[] discards) {
+ final int end = buffered_lines;
+ int j = 0;
+ for (int i = 0; i < end; ++i)
+ if (no_discards || discards[i] == 0) {
+ undiscarded[j] = equivs[i];
+ realindexes[j++] = i;
+ } else
+ changed_flag[1 + i] = true;
+ nondiscarded_lines = j;
+ }
+
+ FileData(Object[] data, HashMap h) {
+ buffered_lines = data.length;
+
+ equivs = new int[buffered_lines];
+ undiscarded = new int[buffered_lines];
+ realindexes = new int[buffered_lines];
+
+ for (int i = 0; i < data.length; ++i) {
+ Integer ir = (Integer) h.get(data[i]);
+ if (ir == null)
+ h.put(data[i], new Integer(equivs[i] = equiv_max++));
+ else
+ equivs[i] = ir.intValue();
+ }
+ }
+
+ /**
+ * Adjust inserts/deletes of blank lines to join changes
+ * as much as possible.
+ * <p/>
+ * We do something when a run of changed lines include a blank
+ * line at one end and have an excluded blank line at the other.
+ * We are free to choose which blank line is included.
+ * `compareseq' always chooses the one at the beginning,
+ * but usually it is cleaner to consider the following blank line
+ * to be the "change". The only exception is if the preceding blank line
+ * would join this change to other changes.
+ *
+ * @param f the file being compared against
+ */
+
+ void shift_boundaries(FileData f) {
+ final boolean[] changed = changed_flag;
+ final boolean[] other_changed = f.changed_flag;
+ int i = 0;
+ int j = 0;
+ int i_end = buffered_lines;
+ int preceding = -1;
+ int other_preceding = -1;
+
+ for (; ;) {
+ int start, end, other_start;
+
+ /*
+ Scan forwards to find beginning of another run of changes.
+ Also keep track of the corresponding point in the other file.
+ */
+
+ while (i < i_end && !changed[1 + i]) {
+ while (other_changed[1 + j++])
+ /*
+ Non-corresponding lines in the other file
+ will count as the preceding batch of changes.
+ */
+ other_preceding = j;
+ i++;
+ }
+
+ if (i == i_end)
+ break;
+
+ start = i;
+ other_start = j;
+
+ for (; ;) {
+ /* Now find the end of this run of changes. */
+
+ while (i < i_end && changed[1 + i]) i++;
+ end = i;
+
+ /*
+ If the first changed line matches the following unchanged one,
+ and this run does not follow right after a previous run,
+ and there are no lines deleted from the other file here,
+ then classify the first changed line as unchanged
+ and the following line as changed in its place.
+ */
+
+ /*
+ You might ask, how could this run follow right after another?
+ Only because the previous run was shifted here.
+ */
+
+ if (end != i_end
+ && equivs[start] == equivs[end]
+ && !other_changed[1 + j]
+ && end != i_end
+ && !((preceding >= 0 && start == preceding)
+ || (other_preceding >= 0
+ && other_start == other_preceding))) {
+ changed[1 + end++] = true;
+ changed[1 + start++] = false;
+ ++i;
+ /*
+ Since one line-that-matches is now before this run
+ instead of after, we must advance in the other file
+ to keep in synch.
+ */
+ ++j;
+ } else
+ break;
+ }
+
+ preceding = i;
+ other_preceding = j;
+ }
+ }
+
+ /**
+ * Number of elements (lines) in this file.
+ */
+ final int buffered_lines;
+
+ /**
+ * Vector, indexed by line number, containing an equivalence code for
+ * each line. It is this vector that is actually compared with that
+ * of another file to generate differences.
+ */
+ private final int[] equivs;
+
+ /**
+ * Vector, like the previous one except that
+ * the elements for discarded lines have been squeezed out.
+ */
+ final int[] undiscarded;
+
+ /**
+ * Vector mapping virtual line numbers (not counting discarded lines)
+ * to real ones (counting those lines). Both are origin-0.
+ */
+ final int[] realindexes;
+
+ /**
+ * Total number of nondiscarded lines.
+ */
+ int nondiscarded_lines;
+
+ /**
+ * Array, indexed by real origin-1 line number,
+ * containing true for a line that is an insertion or a deletion.
+ * The results of comparison are stored here.
+ */
+ boolean[] changed_flag;
+
+ }
+}
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DiffWriter.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DiffWriter.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DiffWriter.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DiffWriter.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,129 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.io.Writer;
+
+/**
+ * Implements a writer that provides an additional method {@link #writeNewLine()}
+ * that can be used for writing line separators which can be defined. A
+ * {@link PrintWriter} would actually be better, but it does not support
+ * defining the line separator to use.
+ */
+public class DiffWriter extends Writer {
+
+ /**
+ * native line separator
+ */
+ public static final String LS_NATIVE = System.getProperty("line.separator");
+
+ /**
+ * unix line separator
+ */
+ public static final String LS_UNIX = "\n";
+
+ /**
+ * windows line separator
+ */
+ public static final String LS_WINDOWS = "\r\n";
+
+ /**
+ * the wrapped writer
+ */
+ private final Writer out;
+
+ /**
+ * the line seperator to use for {@link #writeNewLine()}
+ */
+ private String lineSeparator = LS_NATIVE;
+
+ /**
+ * {@inheritDoc}
+ */
+ public DiffWriter(Writer out) {
+ this.out = out;
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @param lineSeparator the line seperator to use for {@link #writeNewLine()}
+ */
+ public DiffWriter(Writer out, String lineSeparator) {
+ this.out = out;
+ this.lineSeparator = lineSeparator;
+ }
+
+ /**
+ * Writes a new line according to the defined line separator
+ * @throws IOException if an I/O error occurs
+ */
+ public void writeNewLine() throws IOException {
+ write(lineSeparator);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void write(int c) throws IOException {
+ out.write(c);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void write(char[] cbuf) throws IOException {
+ out.write(cbuf);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void write(char[] cbuf, int off, int len) throws IOException {
+ out.write(cbuf, off, len);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void write(String str) throws IOException {
+ out.write(str);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void write(String str, int off, int len) throws IOException {
+ out.write(str, off, len);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void flush() throws IOException {
+ out.flush();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void close() throws IOException {
+ out.close();
+ }
+}
\ No newline at end of file
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Document.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Document.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Document.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Document.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+/**
+ * A document represents a list of elements and have a source.
+ */
+public class Document {
+
+ /**
+ * the source information of this document
+ */
+ private final DocumentSource source;
+
+ /**
+ * the array of elements that form this document
+ */
+ private final Element[] elements;
+
+ /**
+ * Create a new document with the given source and element factory
+ * @param source the source
+ * @param factory the element factory
+ */
+ public Document(DocumentSource source, ElementsFactory factory) {
+ this.source = source;
+ this.elements = factory.getElements();
+ }
+
+ /**
+ * Return the source of this document
+ * @return the source.
+ */
+ public DocumentSource getSource() {
+ return source;
+ }
+
+ /**
+ * Return the elements of this document
+ * @return the elements.
+ */
+ public Element[] getElements() {
+ return elements;
+ }
+
+ /**
+ * Create a <em>diff</em> between this document and the given one.
+ *
+ * @param right the other document to diff to.
+ * @return a diff.
+ */
+ public DocumentDiff diff(Document right) {
+ return new DocumentDiff(this, right);
+ }
+
+ /**
+ * Create a <em>diff</em> between the given document and this one.
+ * @param left the other document.
+ * @return a diff
+ */
+ public DocumentDiff reverseDiff(Document left) {
+ return new DocumentDiff(left, this);
+ }
+
+ /**
+ * Create a <em>tree-way-diff</em> using this document as base.
+ *
+ * @param left the left document
+ * @param right the right document
+ * @return a diff3
+ */
+ public DocumentDiff3 diff3(Document left, Document right) {
+ return new DocumentDiff3(this, left, right);
+ }
+
+ /**
+ * Elements form a document.
+ */
+ public static interface Element {
+
+ /**
+ * Returns the string representation of this element. If the elements
+ * were generated originally from a string they should return the
+ * exact string again.
+ * @return the string of this element.
+ */
+ String getString();
+ }
+
+ /**
+ * The annotated element include the document source. This can be used
+ * to create an annotated document.
+ */
+ public static interface AnnotatedElement extends Element {
+
+ /**
+ * Returns the document source of this element.
+ * @return the source of this element.
+ */
+ DocumentSource getDocumentSource();
+
+ }
+}
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,363 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+import java.io.IOException;
+import java.io.StringWriter;
+import java.io.Writer;
+import java.util.ArrayList;
+
+/**
+ * The document diff is used to create a <em>diff</em> between 2 documents.
+ * It provides 2 possibilites to use the differences: either using the
+ * {@link ChangeListener} which is called for each line of the document, or
+ * using the {@link Hunk}s that form the differences of this diff.
+ */
+public class DocumentDiff {
+
+ /**
+ * the left document
+ */
+ private Document left;
+
+ /**
+ * the right document
+ */
+ private Document right;
+
+ /**
+ * the change script
+ */
+ private final Diff.Change change;
+
+ /**
+ * the hunks
+ */
+ private Hunk hunks;
+
+ /**
+ * the number of changes
+ */
+ private int numDelta = 0;
+
+ /**
+ * Create a new diff from the given 2 documents
+ * @param left the left document
+ * @param right the right document
+ */
+ public DocumentDiff(Document left, Document right) {
+ this.left = left;
+ this.right = right;
+ Document.Element[] leftElems = left.getElements();
+ Document.Element[] rightElems = right.getElements();
+ change = new Diff(leftElems, rightElems).diff_2(false);
+ init();
+ }
+
+ /**
+ * Returns the number of changed elements. each insertion and each deletion
+ * counts as 1 change. if elements were modified the greate change is counted.
+ * eg: if you change 'foo' to 'bar' this is actually 1 deletion and 1 insertion
+ * but counts as 1 change. if you change 'foo\nbar\n' to 'hello' this counts
+ * as 2 changes since this includes 2 deletions.
+ *
+ * @return the number of changed elements.
+ */
+ public int getNumDeltaElements() {
+ return numDelta;
+ }
+
+ /**
+ * Returns the linked list of hunks
+ * @return the hunks.
+ */
+ public Hunk getHunks() {
+ return hunks;
+ }
+
+ /**
+ * Same as {@link #write(Writer, int)} but to a string buffer.
+ *
+ * @param buf the buffer
+ * @param numContextLines the number of context lines.
+ */
+ public void write(StringBuffer buf, int numContextLines) {
+ try {
+ StringWriter out = new StringWriter();
+ write(new DiffWriter(out), numContextLines);
+ out.close();
+ buf.append(out.getBuffer());
+ } catch (IOException e) {
+ throw new IllegalStateException(e.toString());
+ }
+ }
+
+ /**
+ * Same as {@link #write(DiffWriter, int)} but to a string buffer.
+ *
+ * @param buf the buffer
+ * @param lineSeparator the line separator to use
+ * @param numContextLines the number of context lines.
+ */
+ public void write(StringBuffer buf, String lineSeparator, int numContextLines) {
+ try {
+ StringWriter out = new StringWriter();
+ write(new DiffWriter(out, lineSeparator), numContextLines);
+ out.close();
+ buf.append(out.getBuffer());
+ } catch (IOException e) {
+ throw new IllegalStateException(e.toString());
+ }
+ }
+
+ /**
+ * Same as {@link #write(DiffWriter, int)} but wraps the given writer
+ * with a default diff writer.
+ *
+ * @param out the writer
+ * @param numContextLines the number of context lines.
+ * @throws IOException if an I/O error occurs
+ */
+ public void write(Writer out, int numContextLines) throws IOException {
+ DiffWriter dw = new DiffWriter(out);
+ write(dw, numContextLines);
+ dw.flush();
+ }
+
+ /**
+ * Writes the differences to the given writer in a unified diff
+ * format. the context lines specify how many unmodified lines should
+ * sourround the actual difference.
+ *
+ * @param out the writer
+ * @param numContextLines the number of context lines.
+ * @throws IOException if an I/O error occurs
+ */
+ public void write(DiffWriter out, int numContextLines) throws IOException {
+ if (hunks != null) {
+ if (left.getSource() != null && right.getSource() != null) {
+ out.write("--- ");
+ out.write(left.getSource().getLocation());
+ out.writeNewLine();
+ out.write("+++ ");
+ out.write(right.getSource().getLocation());
+ out.writeNewLine();
+ } else {
+ out.write("--- .mine");
+ out.writeNewLine();
+ out.write("+++ .theirs");
+ out.writeNewLine();
+ }
+ Hunk hunk = hunks;
+ while (hunk != null) {
+ hunk = hunk.write(out, numContextLines);
+ }
+ }
+ }
+
+ /**
+ * init the hunks and the delta counter.
+ */
+ private void init() {
+ Diff.Change c = change;
+ int leftPos = 0;
+ int rightPos = 0;
+ Hunk first = new Hunk(null, null, 0, null);
+ Hunk hunk = first;
+ while (c != null) {
+ numDelta += Math.max(c.deleted, c.inserted);
+ if (leftPos < c.line0) {
+ // add unmodified hunk
+ int len = c.line0 - leftPos;
+ hunk = new Hunk(
+ new Range(left, leftPos, leftPos + len),
+ new Range(right, rightPos, rightPos + len),
+ Hunk.UNMODIFIED,
+ hunk);
+ leftPos+= len;
+ rightPos+= len;
+ }
+ // add hunk
+ hunk = new Hunk(
+ new Range(left, leftPos, leftPos + c.deleted),
+ new Range(right, rightPos, rightPos + c.inserted),
+ (c.deleted > 0 ? Hunk.DELETED : 0)|
+ (c.inserted > 0 ? Hunk.INSERTED : 0),
+ hunk);
+ leftPos+=c.deleted;
+ rightPos+=c.inserted;
+ c = c.nextChange;
+ }
+ // last hunk
+ if (leftPos < left.getElements().length) {
+ int len = left.getElements().length - leftPos;
+ new Hunk(
+ new Range(left, leftPos, leftPos + len),
+ new Range(right, rightPos, rightPos + len),
+ Hunk.UNMODIFIED,
+ hunk);
+ }
+ // and record the first valid hunk
+ hunks = first.next();
+ }
+
+ /**
+ * Iterate over all changes and invoke the respective methods in the given
+ * listener. the context lines specify how many unmodified lines should
+ * sourround the respective change.
+ *
+ * @param listener the change listener
+ * @param numContextLines the number of context lines
+ */
+ public void showChanges(ChangeListener listener, int numContextLines) {
+ Diff.Change c = change;
+ Document.Element[] lines0 = left.getElements();
+ Document.Element[] lines1 = right.getElements();
+ listener.onDocumentsStart(left, right);
+ while (c != null) {
+ Diff.Change first = c;
+ int start0 = Math.max(c.line0 - numContextLines, 0);
+ int end0 = Math.min(c.line0 + c.deleted + numContextLines, lines0.length);
+ int start1 = Math.max(c.line1 - numContextLines, 0);
+ int end1 = Math.min(c.line1 + c.inserted + numContextLines, lines1.length);
+ while (c != null) {
+ if (c.line0 <= end0) {
+ end0 = Math.min(c.line0 + c.deleted + numContextLines, lines0.length);
+ end1 = Math.min(c.line1 + c.inserted + numContextLines, lines1.length);
+ c = c.nextChange;
+ } else {
+ break;
+ }
+ }
+ listener.onChangeStart(start0, end0 - start0 - 1, start1, end1 - start1 - 1);
+ //dump(fmt, first, c, numContextLines);
+ while (first != c) {
+ while (start0 < first.line0) {
+ listener.onUnmodified(start0, start1, lines0[start0]);
+ start0++;
+ start1++;
+ }
+ for (int i = 0; i < first.deleted; i++) {
+ listener.onDeleted(start0, first.line1, lines0[start0]);
+ start0++;
+ }
+ for (int i = 0; i < first.inserted; i++) {
+ listener.onInserted(first.line0, start1, lines1[start1]);
+ start1++;
+ }
+ first = first.nextChange;
+ }
+ for (int i = 0; i < numContextLines && start0 < lines0.length; i++) {
+ listener.onUnmodified(start0, start1, lines0[start0]);
+ start0++;
+ start1++;
+ }
+ listener.onChangeEnd();
+ }
+ listener.onDocumentsEnd(left, right);
+ }
+
+ /**
+ * Returns an element factory that provides the elements of the merged
+ * result of this diff where the left document is dominant.
+ * @return the merged elements.
+ */
+ public ElementsFactory getMergedLeft() {
+ return new MergeElementFactory(true);
+ }
+
+ /**
+ * Returns an element factory that provides the elements of the merged
+ * result of this diff where the right document is dominant.
+ * @return the merged elements.
+ */
+ public ElementsFactory getMergedRight() {
+ return new MergeElementFactory(false);
+ }
+
+ /**
+ * element factory that provides the merged result.
+ */
+ private class MergeElementFactory implements ElementsFactory {
+
+ /**
+ * if <code>true</code>, do the merge reverse
+ */
+ boolean reverse;
+
+ /**
+ * Create a new element factory.
+ * @param reverse if <code>true</code>, do the merge revese
+ */
+ public MergeElementFactory(boolean reverse) {
+ this.reverse = reverse;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Document.Element[] getElements() {
+ Diff.Change c = change;
+ Document.Element[] lines0 = left.getElements();
+ Document.Element[] lines1 = right.getElements();
+ ArrayList elems = new ArrayList();
+ while (c != null) {
+ Diff.Change first = c;
+ int start0 = 0;
+ int end0 = lines0.length;
+ int start1 = 0;
+ int end1 = lines1.length;
+ while (c != null) {
+ if (c.line0 <= end0) {
+ end0 = lines0.length;
+ end1 = lines1.length;
+ c = c.nextChange;
+ } else {
+ break;
+ }
+ }
+ while (first != c) {
+ while (start0 < first.line0) {
+ elems.add(lines0[start0]);
+ start0++;
+ start1++;
+ }
+ for (int i = 0; i < first.deleted; i++) {
+ if (reverse) {
+ elems.add(lines0[start0]);
+ }
+ start0++;
+ }
+ for (int i = 0; i < first.inserted; i++) {
+ if (!reverse) {
+ elems.add(lines1[start1]);
+ }
+ start1++;
+ }
+ first = first.nextChange;
+ }
+ while (start0 < lines0.length) {
+ elems.add(lines0[start0]);
+ start0++;
+ start1++;
+ }
+ }
+ return (Document.Element[]) elems.toArray(new Document.Element[elems.size()]);
+ }
+ }
+
+}
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff3.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff3.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff3.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentDiff3.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,410 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+import java.io.IOException;
+import java.io.StringWriter;
+
+/**
+ * Implements a tree-way diff between a base document and 2 dervied ones.
+ * The result of the diff operation is a list of {@link Hunk3} that can
+ * record the changes and conflicts.
+ */
+public class DocumentDiff3 {
+
+ /**
+ * the base document
+ */
+ private final Document base;
+
+ /**
+ * the left document
+ */
+ private final Document left;
+
+ /**
+ * the right documents
+ */
+ private final Document right;
+
+ /**
+ * the script of changes from the base to the left document
+ */
+ private final Diff.Change leftChanges;
+
+ /**
+ * the script of changes from the base to the right document
+ */
+ private final Diff.Change rightChanges;
+
+ /**
+ * the chain of {@link Hunk3}s of this diff. this hunk here is just a
+ * sentinel so that the chain is never empty.
+ */
+ private final Hunk3 hunks = new Hunk3(null, null, null, null);
+
+ /**
+ * flag that indicates that this diff has conflicts
+ */
+ private boolean hasConflicts;
+
+ /**
+ * Creates a new document diff 3 object.
+ * @param base the base document
+ * @param left the left document
+ * @param right the right document
+ */
+ public DocumentDiff3(Document base, Document left, Document right) {
+ this.base = base;
+ this.left = left;
+ this.right = right;
+ Document.Element[] baseElems = base.getElements();
+ Document.Element[] leftElems = left.getElements();
+ Document.Element[] rightElems = right.getElements();
+ leftChanges = new Diff(baseElems, leftElems).diff_2(false);
+ rightChanges = new Diff(baseElems, rightElems).diff_2(false);
+ initHunks();
+ }
+
+ /**
+ * Returns a chain of {@link Hunk3}s that contain the modifications.
+ * @return a chain of {@link Hunk3}s.
+ */
+ public Hunk3 getHunks() {
+ return hunks.next();
+ }
+
+ /**
+ * Indicates if any of the hunks has a conflict.
+ * @return <code>true</code> if any of the hunks has a conflict.
+ */
+ public boolean hasConflicts() {
+ return hasConflicts;
+ }
+
+ /**
+ * Writes the resulting document to the given string buffer. this may include
+ * conflicting regions.
+ *
+ * @param buf the string buffer to write to
+ * @param lineSeparator the line separator to use
+ * @param showBase if set to <code>true</code> the base section of a conflict
+ * is also included in the output.
+ */
+ public void write(StringBuffer buf, String lineSeparator, boolean showBase) {
+ try {
+ StringWriter w = new StringWriter();
+ write(new DiffWriter(w, lineSeparator), showBase);
+ buf.append(w.getBuffer());
+ } catch (IOException e) {
+ throw new IllegalStateException(e.toString());
+ }
+ }
+
+ /**
+ * Writes the resulting document to the given write. this may include
+ * conflicting regions.
+ *
+ * @param w the writer to write to
+ * @param showBase if set to <code>true</code> the base section of a conflict
+ * is also included in the output.
+ * @throws IOException if an I/O error occurs
+ */
+ public void write(DiffWriter w, boolean showBase) throws IOException {
+ for (Hunk3 hunk = hunks.next(); hunk != null; hunk = hunk.next()) {
+ hunk.write(w, showBase);
+ }
+ w.flush();
+ }
+
+ /**
+ * initializes the hunks
+ */
+ private void initHunks() {
+ MyChange[] changes = {
+ wrap(leftChanges),
+ wrap(rightChanges)
+ };
+ int basePos = 0;
+ Hunk3 hunk = hunks; // the last hunk
+ while (changes[0] != null || changes[1] != null) {
+ MyChange[] using = {null, null};
+ MyChange[] lastUsing = {null, null};
+
+ int baseIdx;
+ if (changes[0] == null) {
+ baseIdx = 1;
+ } else if (changes[1] == null) {
+ baseIdx = 0;
+ } else {
+ // use the change that is smaller
+ baseIdx = changes[0].low0 < changes[1].low0 ? 0 : 1;
+ }
+ int highIdx = baseIdx;
+ int highMark = changes[highIdx].high0;
+
+ // add the change to the using set and unchain it
+ using[highIdx] = lastUsing[highIdx] = changes[highIdx];
+ changes[highIdx] = changes[highIdx].next;
+ lastUsing[highIdx].next = null;
+
+ int otherIdx = highIdx^1;
+ MyChange other = changes[otherIdx];
+
+ // search for region that ends in a 'void' of changes
+ // i.e. when the end of the 'other' is greater than the high mark.
+ //
+ // a a a
+ // a a b a b
+ // b b a
+ // b
+ while (other != null && other.low0 <= highMark) {
+ // add this change to the using set
+ if (using[otherIdx] == null) {
+ using[otherIdx] = other;
+ } else {
+ using[otherIdx].next = other;
+ }
+ lastUsing[otherIdx] = other;
+
+ // advance other and unchain it
+ changes[otherIdx] = changes[otherIdx].next;
+ other.next = null;
+
+ // if the high mark is beyond the end of the other diff
+ // we're finished
+ if (other.high0 > highMark) {
+ // switch roles
+ highIdx ^= 1;
+ highMark = other.high0;
+ }
+ otherIdx = highIdx^1;
+ other = changes[otherIdx];
+ }
+
+ // now build the hunks from the set of changes in 'using'
+ // first deal with the stuff that was common before the first change
+ int lowMark = using[baseIdx].low0;
+ if (basePos < lowMark) {
+ hunk = new Hunk3(
+ new Range(base, basePos, lowMark),
+ null,
+ null,
+ hunk);
+ basePos = lowMark;
+ //System.out.println(hunks.getLast().toString());
+ }
+
+ // get the ranges for the changsets
+ int[] deltaLow = {0,0};
+ if (using[baseIdx^1] != null) {
+ deltaLow[baseIdx^1] = using[baseIdx^1].low0 - using[baseIdx].low0;
+ }
+ int[] deltaHigh = {0,0};
+ if (using[highIdx^1] != null) {
+ deltaHigh[highIdx^1] = using[highIdx].high0 - using[highIdx^1].high0;
+ }
+ Range leftRange = null;
+ Range rightRange = null;
+ if (using[0] != null) {
+ leftRange = new Range(left, using[0].low1 - deltaLow[0], lastUsing[0].high1 + deltaHigh[0]);
+ }
+ if (using[1] != null) {
+ rightRange = new Range(right, using[1].low1 - deltaLow[1], lastUsing[1].high1 + deltaHigh[1]);
+ }
+ // check if the conflict is really one
+ boolean conflict = false;
+ if (leftRange != null && rightRange != null) {
+ if (leftRange.len() == rightRange.len()) {
+ for (int i=0; i< leftRange.len(); i++) {
+ if (!left.getElements()[leftRange.low + i].equals(right.getElements()[rightRange.low + i])) {
+ // yes, it is
+ conflict = true;
+ break;
+ }
+ }
+ // if all lines match, we can discard one of the ranges
+ if (!conflict) {
+ rightRange = null;
+ }
+ } else {
+ conflict = true;
+ }
+ }
+ // get the range for the base
+ int baseHigh = using[highIdx].high0;
+ Range baseRange = new Range(base, basePos, baseHigh);
+ basePos = baseHigh;
+ // and create new hunk
+ hunk = new Hunk3(baseRange, leftRange, rightRange, hunk);
+ hasConflicts |= conflict;
+ //System.out.println(hunks.getLast().toString());
+ } /* while */
+
+ // deal with last hunk
+ if (basePos < base.getElements().length) {
+ new Hunk3(
+ new Range(base, basePos, base.getElements().length),
+ null,
+ null,
+ hunk);
+ //System.out.println(hunks.getLast().toString());
+ }
+ }
+
+ /**
+ * Wraps a chain of {@link Diff.Change}s with a list of {@link MyChange}s.
+ * this is rather a convencience wrapping so that the algorithm above is
+ * easier to understand.
+ *
+ * @param df the chain of changes
+ * @return the wrapped chain of changes
+ */
+ private MyChange wrap(Diff.Change df) {
+ // init sentinel
+ MyChange first = null;
+ MyChange c = null;
+ while (df != null) {
+ c = new MyChange(df.line0, df.line1, df.deleted, df.inserted, c);
+ if (first == null) {
+ first = c;
+ }
+ df = df.nextChange;
+ }
+ return first;
+ }
+
+ /**
+ * Dumps a chain of my changes.
+ * @param c the change
+ * @param left the left doc
+ * @param right the right doc
+ */
+ private void dump(MyChange c, Document left, Document right) {
+ while (c != null) {
+ if (c.isInsert()) {
+ for (int i=0; i<c.high1-c.low1; i++) {
+ dump(0, c.low0 + i, c.low1 + i, "+", c.low1 + i, right);
+ }
+ } else if (c.isDelete()) {
+ for (int i=0; i<c.high0-c.low0; i++) {
+ dump(0, c.low0 + i, c.low1 + i, "-", c.low0 + i, left);
+ }
+ } else {
+ for (int i=0; i<c.high1-c.low1; i++) {
+ dump(0, c.low0 + i, c.low1 + i, "~", c.low1 + i, right);
+ }
+ }
+ c = c.next;
+ }
+ }
+
+ /**
+ * prints a element line
+ * @param b the base line number
+ * @param l the left line number
+ * @param r the right line number
+ * @param prefix the prefix
+ * @param i the index
+ * @param doc the document
+ */
+ private void dump(int b, int l, int r, String prefix, int i, Document doc) {
+ StringBuffer buf = new StringBuffer();
+ buf.append("(").append(b);
+ buf.append(", ").append(l);
+ buf.append(", ").append(r);
+ buf.append(") ").append(prefix);
+ buf.append(doc.getElements()[i]);
+ System.out.println(buf);
+ }
+
+ /**
+ * Wrapper class for the {@link Diff.Change}. This is mainly used to
+ * make the merge algorithm easier, but might result in a performace
+ * drop if the change list is huge.
+ */
+ private static class MyChange {
+
+ /**
+ * the low line in the left document
+ */
+ private final int low0;
+
+ /**
+ * the low line in the right document
+ */
+ private final int low1;
+
+ /**
+ * the high line in the left document
+ */
+ private final int high0;
+
+ /**
+ * the high line in the right document
+ */
+ private final int high1;
+
+ /**
+ * the next change
+ */
+ private MyChange next;
+
+ /**
+ * Constructs a new change and adds it the the previous one.
+ * @param low0 the low line of the left document
+ * @param low1 the low line of the right document
+ * @param len0 the length of the change in the left document
+ * @param len1 the length of the change in the right document
+ * @param prev the previous change
+ */
+ public MyChange(int low0, int low1, int len0, int len1, MyChange prev) {
+ this.low0 = low0;
+ this.low1 = low1;
+ this.high0 = low0 + len0;
+ this.high1 = low1 + len1;
+ if (prev != null) {
+ prev.next = this;
+ }
+ }
+
+ /**
+ * Checks if this is a deletion.
+ * @return <code>true</code> if this is a deletion.
+ */
+ public boolean isDelete() {
+ return low1 == high1;
+ }
+
+ /**
+ * Checks if this is an insertion
+ * @return <code>false</code> if this is an insertion.
+ */
+ public boolean isInsert() {
+ return low0 == high0;
+ }
+
+ /**
+ * Returns a debug string for this change.
+ * @return a debug string for this change.
+ */
+ public String toString() {
+ return "(" + low0 + "-" + high0 + "),(" + low1 + "-" + high1 + ")";
+ }
+ }
+
+}
\ No newline at end of file
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentSource.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentSource.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentSource.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/DocumentSource.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,35 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+/**
+ * <code>DocumentSource</code>...
+ */
+public interface DocumentSource {
+
+ /**
+ * Returns a label of the source.
+ * @return a label of the source.
+ */
+ String getLabel();
+
+ /**
+ * Returns some location information of the source.
+ * @return some location information.
+ */
+ String getLocation();
+}
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/ElementsFactory.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/ElementsFactory.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/ElementsFactory.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/ElementsFactory.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+/**
+ * The elements factory provides elements for a document
+ */
+public interface ElementsFactory {
+
+ /**
+ * Provides the elements
+ * @return an array of elements
+ */
+ public Document.Element[] getElements();
+}
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/FileDocumentSource.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/FileDocumentSource.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/FileDocumentSource.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/FileDocumentSource.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,43 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+import java.io.File;
+
+/**
+ * <code>FileDocumentSource</code>...
+ */
+public class FileDocumentSource implements DocumentSource {
+
+ private final File file;
+
+ public FileDocumentSource(File file) {
+ this.file = file;
+ }
+
+ public File getFile() {
+ return file;
+ }
+
+ public String getLabel() {
+ return file.getName();
+ }
+
+ public String getLocation() {
+ return file.getPath();
+ }
+}
\ No newline at end of file
Added: jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Hunk.java
URL: http://svn.apache.org/viewvc/jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Hunk.java?rev=1512568&view=auto
==============================================================================
--- jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Hunk.java (added)
+++ jackrabbit/commons/filevault/trunk/vault-diff/src/main/java/org/apache/jackrabbit/vault/util/diff/Hunk.java Sat Aug 10 05:53:42 2013
@@ -0,0 +1,228 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.jackrabbit.vault.util.diff;
+
+import java.io.IOException;
+
+/**
+ * A hunk records a block of diff between the left and the right document.
+ * it represents either a insertion, deletion, change or identiy. several
+ * hunks are chained in a linked list.
+ */
+public class Hunk {
+
+ /**
+ * type indicates an unmodified block
+ */
+ public static final int UNMODIFIED = 0;
+
+ /**
+ * type indicates an inserted block
+ */
+ public static final int INSERTED = 1;
+
+ /**
+ * type indicates a deleted block
+ */
+ public static final int DELETED = 2;
+
+ /**
+ * type indicates a changed block
+ */
+ public static final int CHANGED = INSERTED | DELETED;
+
+ /**
+ * the range in the left document
+ */
+ public final Range left;
+
+ /**
+ * the rnage in the right document
+ */
+ public final Range right;
+
+ /**
+ * the hunk type
+ */
+ public final int type;
+
+ /**
+ * the previous hunk
+ */
+ private Hunk prev;
+
+ /**
+ * the next hunk
+ */
+ private Hunk next;
+
+ /**
+ * Creates a new hunk and adds it to the previous hunk
+ * @param left the left range
+ * @param right the right range
+ * @param type the hunk type
+ * @param prev the previous hunk
+ */
+ public Hunk(Range left, Range right, int type, Hunk prev) {
+ this.left = left;
+ this.right = right;
+ this.prev = prev;
+ this.type = type;
+ if (prev != null) {
+ prev.next = this;
+ }
+ }
+
+ /**
+ * Returns the previous hunk of this chain
+ * @return the previous hunk.
+ */
+ public Hunk prev() {
+ return prev;
+ }
+
+ /**
+ * Returns the next hunk of this chain
+ * @return the next hunk.
+ */
+ public Hunk next() {
+ return next;
+ }
+
+ /**
+ * Writes a unified diff to the given writer and returns the next hunk to
+ * continue the output.
+ *
+ * @param out the writer
+ * @param numContextLines the number of context lines to include in the
+ * diff blocks. do not change during iteration!
+ * @return the next hunk or <code>null</code>.
+ * @throws IOException if an I/O error occurs.
+ */
+ public Hunk write(DiffWriter out, int numContextLines) throws IOException {
+ if (type == UNMODIFIED) {
+ //writeData(out, left, " ");
+ return next;
+ } else {
+ Hunk last = next;
+ Hunk prevLast = this;
+
+ // search hunk that is big enough to hold 2 x numContextLines or is
+ // the last hunk.
+ while (last != null) {
+ if (last.type == UNMODIFIED
+ &&
+ (last.left.len() > 2*numContextLines || last.next == null)) {
+ break;
+ }
+ prevLast = last;
+ last = last.next;
+ }
+
+ // get new ranges for diff line
+ Range prevRange;
+ if (prev == null) {
+ // this is the very first hunk, so no previous context lines
+ prevRange = new Range(left.doc, left.low, left.low);
+ } else {
+ // the search above ensures that the previous one never overlaps
+ // this hunk. we just need to guard the very first hunk
+ prevRange = new Range(left.doc, Math.max(left.low - numContextLines, 0), left.low);
+ }
+
+ Range lastRange;
+ if (last == null) {
+ // if we did not find a last hunk, create an empty range
+ // with the bounds of the hunk previous to the last
+ lastRange = new Range(left.doc, prevLast.left.high, prevLast.left.high);
+ } else {
+ // we are not allowed to enlarge the range
+ lastRange = new Range(left.doc, last.left.low, Math.min(last.left.high, last.left.low + numContextLines));
+ }
+
+ // handle special case where our diff differs from the GNU diff
+ // i reckon this is a bug in {@link Diff} where the line number
+ // of a deletion or insertion is 1 too big.
+ int prevLen0 = prevRange.len();
+ int lastLen0 = lastRange.len();
+ int prevLen1 = prevRange.len();
+ int lastLen1 = lastRange.len();
+ if (left.len() == 0 && numContextLines == 0) {
+ prevLen0 = 1;
+ lastLen0--;
+ }
+ if (right.len() == 0 && numContextLines == 0) {
+ prevLen1 = 1;
+ lastLen1--;
+ }
+ Range newLeft = new Range(left.doc,
+ left.low - prevLen0,
+ prevLast.left.high + lastLen0);
+ Range newRight = new Range(right.doc,
+ right.low - prevLen1,
+ prevLast.right.high + lastLen1);
+ out.write("@@ -");
+ out.write(newLeft.toRangeString());
+ out.write(" +");
+ out.write(newRight.toRangeString());
+ out.write(" @@");
+ out.writeNewLine();
+
+ // output previous context line
+ writeData(out, prevRange, " ");
+ Hunk h = this;
+ while (h != last) {
+ h.writeBody(out);
+ h = h.next;
+ }
+ writeData(out, lastRange, " ");
+ return last;
+ }
+ }
+
+ /**
+ * Writes the body of this hunk
+ * @param out the writer
+ * @throws IOException if an I/O error occurs.
+ */
+ private void writeBody(DiffWriter out) throws IOException {
+ if (type == UNMODIFIED) {
+ writeData(out, left, " ");
+ }
+ if ((type & DELETED) != 0) {
+ writeData(out, left, "-");
+ }
+ if ((type & INSERTED) != 0) {
+ writeData(out, right, "+");
+ }
+ }
+
+ /**
+ * Write the actual lines
+ * @param out the writer
+ * @param range the range
+ * @param prefix the prefix
+ * @throws IOException if an I/O error occurs
+ */
+ private static void writeData(DiffWriter out, Range range, String prefix)
+ throws IOException {
+ for (int i=range.low; i<range.high; i++) {
+ out.write(prefix);
+ out.write(range.doc.getElements()[i].getString());
+ }
+ }
+}
\ No newline at end of file