jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tri...@apache.org
Subject 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...
Date Sat, 10 Aug 2013 05:53:54 GMT
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



Mime
View raw message