diff options
author | Shawn O. Pearce <spearce@spearce.org> | 2010-09-02 12:53:27 -0700 |
---|---|---|
committer | Chris Aniszczyk <caniszczyk@gmail.com> | 2010-09-06 21:37:11 -0500 |
commit | 67263e2056108e471d684c3cef9e719724b51220 (patch) | |
tree | e4ea7623e4b0884b542c77167ab456e3643eb5ed /org.eclipse.jgit/src/org/eclipse/jgit/diff | |
parent | 18aadc826dae7c6308c2a6c68d48ab75c8dd9b6d (diff) | |
download | jgit-67263e2056108e471d684c3cef9e719724b51220.tar.gz jgit-67263e2056108e471d684c3cef9e719724b51220.zip |
Refactor diff sequence API
Instead of making the sequence itself responsible for the equivalence
function, use an external function that is supplied by the caller.
This cleans up the code because we now say cmp.equals(a, ai, b, bi)
instead of a.equals(ai, b, bi).
This refactoring also removes the odd concept of creating different
types of sequences to have different behaviors for whitespace
ignoring. Instead DiffComparator now supports singleton functions
that apply a particular equivalence algorithm to a type of sequence.
Change-Id: I559f494d81cdc6f06bfb4208f60780c0ae251df9
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
Diffstat (limited to 'org.eclipse.jgit/src/org/eclipse/jgit/diff')
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java | 38 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java | 22 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java | 85 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextComparator.java | 290 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreAllWhitespace.java | 127 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreTrailingWhitespace.java | 111 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreWhitespaceChange.java | 129 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/Sequence.java | 40 | ||||
-rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/diff/SequenceComparator.java (renamed from org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreLeadingWhitespace.java) | 106 |
9 files changed, 401 insertions, 547 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java index 8e92c8995c..e36aaf17fb 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java @@ -78,8 +78,8 @@ import org.eclipse.jgit.lib.ObjectReader; import org.eclipse.jgit.lib.ProgressMonitor; import org.eclipse.jgit.lib.Repository; import org.eclipse.jgit.patch.FileHeader; -import org.eclipse.jgit.patch.HunkHeader; import org.eclipse.jgit.patch.FileHeader.PatchType; +import org.eclipse.jgit.patch.HunkHeader; import org.eclipse.jgit.revwalk.FollowFilter; import org.eclipse.jgit.revwalk.RevTree; import org.eclipse.jgit.revwalk.RevWalk; @@ -118,7 +118,7 @@ public class DiffFormatter { private int abbreviationLength = 7; - private RawText.Factory rawTextFactory = RawText.FACTORY; + private RawTextComparator comparator = RawTextComparator.DEFAULT; private int binaryFileThreshold = DEFAULT_BINARY_FILE_THRESHOLD; @@ -207,20 +207,20 @@ public class DiffFormatter { } /** - * Set the helper that constructs difference output. + * Set the line equivalence function for text file differences. * - * @param type - * the factory to create different output. Different types of - * factories can produce different whitespace behavior, for - * example. - * @see RawText#FACTORY - * @see RawTextIgnoreAllWhitespace#FACTORY - * @see RawTextIgnoreLeadingWhitespace#FACTORY - * @see RawTextIgnoreTrailingWhitespace#FACTORY - * @see RawTextIgnoreWhitespaceChange#FACTORY + * @param cmp + * The equivalence function used to determine if two lines of + * text are identical. The function can be changed to ignore + * various types of whitespace. + * @see RawTextComparator#DEFAULT + * @see RawTextComparator#WS_IGNORE_ALL + * @see RawTextComparator#WS_IGNORE_CHANGE + * @see RawTextComparator#WS_IGNORE_LEADING + * @see RawTextComparator#WS_IGNORE_TRAILING */ - public void setRawTextFactory(RawText.Factory type) { - rawTextFactory = type; + public void setDiffComparator(RawTextComparator cmp) { + comparator = cmp; } /** @@ -869,9 +869,9 @@ public class DiffFormatter { type = PatchType.BINARY; } else { - res.a = rawTextFactory.create(aRaw); - res.b = rawTextFactory.create(bRaw); - editList = new MyersDiff(res.a, res.b).getEdits(); + res.a = new RawText(comparator, aRaw); + res.b = new RawText(comparator, bRaw); + editList = diff(res.a, res.b); type = PatchType.UNIFIED; switch (ent.getChangeType()) { @@ -892,6 +892,10 @@ public class DiffFormatter { return res; } + private EditList diff(RawText a, RawText b) { + return new MyersDiff<RawText>(comparator, a, b).getEdits(); + } + private void assertHaveRepository() { if (db == null) throw new IllegalStateException(JGitText.get().repositoryIsRequired); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java index 6a4b44bff1..270ed92743 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java @@ -101,30 +101,38 @@ import org.eclipse.jgit.util.LongList; * * So the overall runtime complexity stays the same with linear space, * albeit with a larger constant factor. + * + * @param <S> + * type of sequence. */ -public class MyersDiff { +public class MyersDiff<S extends Sequence> { /** * The list of edits found during the last call to {@link #calculateEdits()} */ protected EditList edits; + /** Comparison function for sequences. */ + protected SequenceComparator<S> cmp; + /** * The first text to be compared. Referred to as "Text A" in the comments */ - protected Sequence a; + protected S a; /** * The second text to be compared. Referred to as "Text B" in the comments */ - protected Sequence b; + protected S b; /** * The only constructor * + * @param cmp comparison method for this execution. * @param a the text A which should be compared * @param b the text B which should be compared */ - public MyersDiff(Sequence a, Sequence b) { + public MyersDiff(SequenceComparator<S> cmp, S a, S b) { + this.cmp = cmp; this.a = a; this.b = b; calculateEdits(); @@ -436,7 +444,7 @@ if (k < beginK || k > endK) class ForwardEditPaths extends EditPaths { final int snake(int k, int x) { for (; x < endA && k + x < endB; x++) - if (!a.equals(x, b, k + x)) + if (!cmp.equals(a, x, b, k + x)) break; return x; } @@ -478,7 +486,7 @@ if (k < beginK || k > endK) class BackwardEditPaths extends EditPaths { final int snake(int k, int x) { for (; x > beginA && k + x > beginB; x--) - if (!a.equals(x - 1, b, k + x - 1)) + if (!cmp.equals(a, x - 1, b, k + x - 1)) break; return x; } @@ -529,7 +537,7 @@ if (k < beginK || k > endK) try { RawText a = new RawText(new java.io.File(args[0])); RawText b = new RawText(new java.io.File(args[1])); - MyersDiff diff = new MyersDiff(a, b); + MyersDiff diff = new MyersDiff(RawTextComparator.DEFAULT, a, b); System.out.println(diff.getEdits().toString()); } catch (Exception e) { e.printStackTrace(); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java index ad81de58c9..07d28572ad 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java @@ -65,26 +65,7 @@ import org.eclipse.jgit.util.RawParseUtils; * line number 1. Callers may need to subtract 1 prior to invoking methods if * they are converting from "line number" to "element index". */ -public class RawText implements Sequence { - /** Creates a RawText instance. */ - public static interface Factory { - /** - * Construct a RawText instance for the content. - * - * @param input - * the content array. - * @return a RawText instance wrapping this content. - */ - RawText create(byte[] input); - } - - /** Creates RawText that does not treat whitespace specially. */ - public static final Factory FACTORY = new Factory() { - public RawText create(byte[] input) { - return new RawText(input); - } - }; - +public class RawText extends Sequence { /** Number of bytes to check for heuristics in {@link #isBinary(byte[])} */ private static final int FIRST_FEW_BYTES = 8000; @@ -107,9 +88,24 @@ public class RawText implements Sequence { * through cached arrays is safe. */ public RawText(final byte[] input) { + this(RawTextComparator.DEFAULT, input); + } + + /** + * Create a new sequence from an existing content byte array. + * + * The entire array (indexes 0 through length-1) is used as the content. + * + * @param cmp + * comparator that will later be used to compare texts. + * @param input + * the content array. The array is never modified, so passing + * through cached arrays is safe. + */ + public RawText(RawTextComparator cmp, byte[] input) { content = input; lines = RawParseUtils.lineMap(content, 0, content.length); - hashes = computeHashes(); + hashes = computeHashes(cmp); } /** @@ -126,6 +122,7 @@ public class RawText implements Sequence { this(IO.readFully(file)); } + /** @return total number of items in the sequence. */ public int size() { // The line map is always 2 entries larger than the number of lines in // the file. Index 0 is padded out/unused. The last index is the total @@ -134,30 +131,6 @@ public class RawText implements Sequence { return lines.size() - 2; } - public boolean equals(final int i, final Sequence other, final int j) { - return equals(this, i + 1, (RawText) other, j + 1); - } - - private static boolean equals(final RawText a, final int ai, - final RawText b, final int bi) { - if (a.hashes[ai] != b.hashes[bi]) - return false; - - int as = a.lines.get(ai); - int bs = b.lines.get(bi); - final int ae = a.lines.get(ai + 1); - final int be = b.lines.get(bi + 1); - - if (ae - as != be - bs) - return false; - - while (as < ae) { - if (a.content[as++] != b.content[bs++]) - return false; - } - return true; - } - /** * Write a specific line to the output stream, without its trailing LF. * <p> @@ -197,35 +170,17 @@ public class RawText implements Sequence { return content[end - 1] != '\n'; } - private int[] computeHashes() { + private int[] computeHashes(RawTextComparator cmp) { final int[] r = new int[lines.size()]; for (int lno = 1; lno < lines.size() - 1; lno++) { final int ptr = lines.get(lno); final int end = lines.get(lno + 1); - r[lno] = hashLine(content, ptr, end); + r[lno] = cmp.hashRegion(content, ptr, end); } return r; } /** - * Compute a hash code for a single line. - * - * @param raw - * the raw file content. - * @param ptr - * first byte of the content line to hash. - * @param end - * 1 past the last byte of the content line. - * @return hash code for the region <code>[ptr, end)</code> of raw. - */ - protected int hashLine(final byte[] raw, int ptr, final int end) { - int hash = 5381; - for (; ptr < end; ptr++) - hash = (hash << 5) ^ (raw[ptr] & 0xff); - return hash; - } - - /** * Determine heuristically whether a byte array represents binary (as * opposed to text) content. * diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextComparator.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextComparator.java new file mode 100644 index 0000000000..2f31618c3e --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextComparator.java @@ -0,0 +1,290 @@ +/* + * Copyright (C) 2009-2010, Google Inc. + * Copyright (C) 2008-2009, Johannes E. Schindelin <johannes.schindelin@gmx.de> + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.diff; + +import static org.eclipse.jgit.util.RawCharUtil.isWhitespace; +import static org.eclipse.jgit.util.RawCharUtil.trimLeadingWhitespace; +import static org.eclipse.jgit.util.RawCharUtil.trimTrailingWhitespace; + +/** Equivalence function for {@link RawText}. */ +public abstract class RawTextComparator extends SequenceComparator<RawText> { + /** No special treatment. */ + public static final RawTextComparator DEFAULT = new RawTextComparator() { + @Override + public boolean equals(RawText a, int ai, RawText b, int bi) { + ai++; + bi++; + + if (a.hashes[ai] != b.hashes[bi]) + return false; + + int as = a.lines.get(ai); + int bs = b.lines.get(bi); + final int ae = a.lines.get(ai + 1); + final int be = b.lines.get(bi + 1); + + if (ae - as != be - bs) + return false; + + while (as < ae) { + if (a.content[as++] != b.content[bs++]) + return false; + } + return true; + } + + @Override + public int hashRegion(final byte[] raw, int ptr, final int end) { + int hash = 5381; + for (; ptr < end; ptr++) + hash = (hash << 5) ^ (raw[ptr] & 0xff); + return hash; + } + }; + + /** Ignores all whitespace. */ + public static final RawTextComparator WS_IGNORE_ALL = new RawTextComparator() { + @Override + public boolean equals(RawText a, int ai, RawText b, int bi) { + ai++; + bi++; + + if (a.hashes[ai] != b.hashes[bi]) + return false; + + int as = a.lines.get(ai); + int bs = b.lines.get(bi); + int ae = a.lines.get(ai + 1); + int be = b.lines.get(bi + 1); + + ae = trimTrailingWhitespace(a.content, as, ae); + be = trimTrailingWhitespace(b.content, bs, be); + + while (as < ae && bs < be) { + byte ac = a.content[as]; + byte bc = b.content[bs]; + + while (as < ae - 1 && isWhitespace(ac)) { + as++; + ac = a.content[as]; + } + + while (bs < be - 1 && isWhitespace(bc)) { + bs++; + bc = b.content[bs]; + } + + if (ac != bc) + return false; + + as++; + bs++; + } + + return as == ae && bs == be; + } + + @Override + public int hashRegion(byte[] raw, int ptr, int end) { + int hash = 5381; + for (; ptr < end; ptr++) { + byte c = raw[ptr]; + if (!isWhitespace(c)) + hash = (hash << 5) ^ (c & 0xff); + } + return hash; + } + }; + + /** Ignores leading whitespace. */ + public static final RawTextComparator WS_IGNORE_LEADING = new RawTextComparator() { + @Override + public boolean equals(RawText a, int ai, RawText b, int bi) { + ai++; + bi++; + + if (a.hashes[ai] != b.hashes[bi]) + return false; + + int as = a.lines.get(ai); + int bs = b.lines.get(bi); + int ae = a.lines.get(ai + 1); + int be = b.lines.get(bi + 1); + + as = trimLeadingWhitespace(a.content, as, ae); + bs = trimLeadingWhitespace(b.content, bs, be); + + if (ae - as != be - bs) + return false; + + while (as < ae) { + if (a.content[as++] != b.content[bs++]) + return false; + } + return true; + } + + @Override + public int hashRegion(final byte[] raw, int ptr, int end) { + int hash = 5381; + ptr = trimLeadingWhitespace(raw, ptr, end); + for (; ptr < end; ptr++) { + hash = (hash << 5) ^ (raw[ptr] & 0xff); + } + return hash; + } + }; + + /** Ignores trailing whitespace. */ + public static final RawTextComparator WS_IGNORE_TRAILING = new RawTextComparator() { + @Override + public boolean equals(RawText a, int ai, RawText b, int bi) { + ai++; + bi++; + + if (a.hashes[ai] != b.hashes[bi]) + return false; + + int as = a.lines.get(ai); + int bs = b.lines.get(bi); + int ae = a.lines.get(ai + 1); + int be = b.lines.get(bi + 1); + + ae = trimTrailingWhitespace(a.content, as, ae); + be = trimTrailingWhitespace(b.content, bs, be); + + if (ae - as != be - bs) + return false; + + while (as < ae) { + if (a.content[as++] != b.content[bs++]) + return false; + } + return true; + } + + @Override + public int hashRegion(final byte[] raw, int ptr, int end) { + int hash = 5381; + end = trimTrailingWhitespace(raw, ptr, end); + for (; ptr < end; ptr++) { + hash = (hash << 5) ^ (raw[ptr] & 0xff); + } + return hash; + } + }; + + /** Ignores trailing whitespace. */ + public static final RawTextComparator WS_IGNORE_CHANGE = new RawTextComparator() { + @Override + public boolean equals(RawText a, int ai, RawText b, int bi) { + ai++; + bi++; + + if (a.hashes[ai] != b.hashes[bi]) + return false; + + int as = a.lines.get(ai); + int bs = b.lines.get(bi); + int ae = a.lines.get(ai + 1); + int be = b.lines.get(bi + 1); + + ae = trimTrailingWhitespace(a.content, as, ae); + be = trimTrailingWhitespace(b.content, bs, be); + + while (as < ae && bs < be) { + byte ac = a.content[as]; + byte bc = b.content[bs]; + + if (ac != bc) + return false; + + if (isWhitespace(ac)) + as = trimLeadingWhitespace(a.content, as, ae); + else + as++; + + if (isWhitespace(bc)) + bs = trimLeadingWhitespace(b.content, bs, be); + else + bs++; + } + return as == ae && bs == be; + } + + @Override + public int hashRegion(final byte[] raw, int ptr, int end) { + int hash = 5381; + end = trimTrailingWhitespace(raw, ptr, end); + while (ptr < end) { + byte c = raw[ptr]; + hash = (hash << 5) ^ (c & 0xff); + if (isWhitespace(c)) + ptr = trimLeadingWhitespace(raw, ptr, end); + else + ptr++; + } + return hash; + } + }; + + @Override + public int hash(RawText seq, int ptr) { + return seq.hashes[ptr + 1]; + } + + /** + * Compute a hash code for a region. + * + * @param raw + * the raw file content. + * @param ptr + * first byte of the region to hash. + * @param end + * 1 past the last byte of the region. + * @return hash code for the region <code>[ptr, end)</code> of raw. + */ + public abstract int hashRegion(byte[] raw, int ptr, int end); +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreAllWhitespace.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreAllWhitespace.java deleted file mode 100644 index 855a872428..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreAllWhitespace.java +++ /dev/null @@ -1,127 +0,0 @@ -/* - * Copyright (C) 2009-2010, Google Inc. - * Copyright (C) 2008-2009, Johannes E. Schindelin <johannes.schindelin@gmx.de> - * and other copyright owners as documented in the project's IP log. - * - * This program and the accompanying materials are made available - * under the terms of the Eclipse Distribution License v1.0 which - * accompanies this distribution, is reproduced below, and is - * available at http://www.eclipse.org/org/documents/edl-v10.php - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or - * without modification, are permitted provided that the following - * conditions are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * - Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * - Neither the name of the Eclipse Foundation, Inc. nor the - * names of its contributors may be used to endorse or promote - * products derived from this software without specific prior - * written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND - * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, - * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF - * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -package org.eclipse.jgit.diff; - -import static org.eclipse.jgit.util.RawCharUtil.isWhitespace; -import static org.eclipse.jgit.util.RawCharUtil.trimTrailingWhitespace; - -/** - * A version of {@link RawText} that ignores all whitespace. - */ -public class RawTextIgnoreAllWhitespace extends RawText { - /** Creates RawText that ignores all whitespace. */ - @SuppressWarnings("hiding") - public static final Factory FACTORY = new Factory() { - public RawText create(byte[] input) { - return new RawTextIgnoreAllWhitespace(input); - } - }; - - /** - * Create a new sequence from an existing content byte array. - * <p> - * The entire array (indexes 0 through length-1) is used as the content. - * - * @param input - * the content array. The array is never modified, so passing - * through cached arrays is safe. - */ - public RawTextIgnoreAllWhitespace(byte[] input) { - super(input); - } - - @Override - public boolean equals(final int i, final Sequence other, final int j) { - return equals(this, i + 1, (RawText) other, j + 1); - } - - private static boolean equals(final RawText a, final int ai, - final RawText b, final int bi) { - if (a.hashes[ai] != b.hashes[bi]) - return false; - - int as = a.lines.get(ai); - int bs = b.lines.get(bi); - int ae = a.lines.get(ai + 1); - int be = b.lines.get(bi + 1); - - ae = trimTrailingWhitespace(a.content, as, ae); - be = trimTrailingWhitespace(b.content, bs, be); - - while (as < ae && bs < be) { - byte ac = a.content[as]; - byte bc = b.content[bs]; - - while (as < ae - 1 && isWhitespace(ac)) { - as++; - ac = a.content[as]; - } - - while (bs < be - 1 && isWhitespace(bc)) { - bs++; - bc = b.content[bs]; - } - - if (ac != bc) - return false; - - as++; - bs++; - } - - return as == ae && bs == be; - } - - @Override - protected int hashLine(final byte[] raw, int ptr, final int end) { - int hash = 5381; - for (; ptr < end; ptr++) { - byte c = raw[ptr]; - if (!isWhitespace(c)) - hash = (hash << 5) ^ (c & 0xff); - } - return hash; - } -} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreTrailingWhitespace.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreTrailingWhitespace.java deleted file mode 100644 index 5e69eaabd7..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreTrailingWhitespace.java +++ /dev/null @@ -1,111 +0,0 @@ -/* - * Copyright (C) 2009-2010, Google Inc. - * Copyright (C) 2008-2009, Johannes E. Schindelin <johannes.schindelin@gmx.de> - * and other copyright owners as documented in the project's IP log. - * - * This program and the accompanying materials are made available - * under the terms of the Eclipse Distribution License v1.0 which - * accompanies this distribution, is reproduced below, and is - * available at http://www.eclipse.org/org/documents/edl-v10.php - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or - * without modification, are permitted provided that the following - * conditions are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * - Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * - Neither the name of the Eclipse Foundation, Inc. nor the - * names of its contributors may be used to endorse or promote - * products derived from this software without specific prior - * written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND - * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, - * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF - * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -package org.eclipse.jgit.diff; - -import static org.eclipse.jgit.util.RawCharUtil.trimTrailingWhitespace; - -/** - * A version of {@link RawText} that ignores trailing whitespace. - */ -public class RawTextIgnoreTrailingWhitespace extends RawText { - /** Creates RawText that ignores only trailing whitespace. */ - @SuppressWarnings("hiding") - public static final Factory FACTORY = new Factory() { - public RawText create(byte[] input) { - return new RawTextIgnoreTrailingWhitespace(input); - } - }; - - /** - * Create a new sequence from an existing content byte array. - * <p> - * The entire array (indexes 0 through length-1) is used as the content. - * - * @param input - * the content array. The array is never modified, so passing - * through cached arrays is safe. - */ - public RawTextIgnoreTrailingWhitespace(byte[] input) { - super(input); - } - - @Override - public boolean equals(final int i, final Sequence other, final int j) { - return equals(this, i + 1, (RawText) other, j + 1); - } - - private static boolean equals(final RawText a, final int ai, - final RawText b, final int bi) { - if (a.hashes[ai] != b.hashes[bi]) - return false; - - int as = a.lines.get(ai); - int bs = b.lines.get(bi); - int ae = a.lines.get(ai + 1); - int be = b.lines.get(bi + 1); - - ae = trimTrailingWhitespace(a.content, as, ae); - be = trimTrailingWhitespace(b.content, bs, be); - - if (ae - as != be - bs) - return false; - - while (as < ae) { - if (a.content[as++] != b.content[bs++]) - return false; - } - return true; - } - - @Override - protected int hashLine(final byte[] raw, int ptr, int end) { - int hash = 5381; - end = trimTrailingWhitespace(raw, ptr, end); - for (; ptr < end; ptr++) { - hash = (hash << 5) ^ (raw[ptr] & 0xff); - } - return hash; - } -}
\ No newline at end of file diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreWhitespaceChange.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreWhitespaceChange.java deleted file mode 100644 index 2d1b9772fe..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreWhitespaceChange.java +++ /dev/null @@ -1,129 +0,0 @@ -/* - * Copyright (C) 2009-2010, Google Inc. - * Copyright (C) 2008-2009, Johannes E. Schindelin <johannes.schindelin@gmx.de> - * and other copyright owners as documented in the project's IP log. - * - * This program and the accompanying materials are made available - * under the terms of the Eclipse Distribution License v1.0 which - * accompanies this distribution, is reproduced below, and is - * available at http://www.eclipse.org/org/documents/edl-v10.php - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or - * without modification, are permitted provided that the following - * conditions are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * - Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * - Neither the name of the Eclipse Foundation, Inc. nor the - * names of its contributors may be used to endorse or promote - * products derived from this software without specific prior - * written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND - * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, - * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF - * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -package org.eclipse.jgit.diff; - -import static org.eclipse.jgit.util.RawCharUtil.isWhitespace; -import static org.eclipse.jgit.util.RawCharUtil.trimLeadingWhitespace; -import static org.eclipse.jgit.util.RawCharUtil.trimTrailingWhitespace; - -/** - * A version of {@link RawText} that ignores changes in the amount of - * whitespace, as well as trailing whitespace. - */ -public class RawTextIgnoreWhitespaceChange extends RawText { - /** Creates RawText that ignores only whitespace changes. */ - @SuppressWarnings("hiding") - public static final Factory FACTORY = new Factory() { - public RawText create(byte[] input) { - return new RawTextIgnoreWhitespaceChange(input); - } - }; - - /** - * Create a new sequence from an existing content byte array. - * <p> - * The entire array (indexes 0 through length-1) is used as the content. - * - * @param input - * the content array. The array is never modified, so passing - * through cached arrays is safe. - */ - public RawTextIgnoreWhitespaceChange(byte[] input) { - super(input); - } - - @Override - public boolean equals(final int i, final Sequence other, final int j) { - return equals(this, i + 1, (RawText) other, j + 1); - } - - private static boolean equals(final RawText a, final int ai, - final RawText b, final int bi) { - if (a.hashes[ai] != b.hashes[bi]) - return false; - - int as = a.lines.get(ai); - int bs = b.lines.get(bi); - int ae = a.lines.get(ai + 1); - int be = b.lines.get(bi + 1); - - ae = trimTrailingWhitespace(a.content, as, ae); - be = trimTrailingWhitespace(b.content, bs, be); - - while (as < ae && bs < be) { - byte ac = a.content[as]; - byte bc = b.content[bs]; - - if (ac != bc) - return false; - - if (isWhitespace(ac)) - as = trimLeadingWhitespace(a.content, as, ae); - else - as++; - - if (isWhitespace(bc)) - bs = trimLeadingWhitespace(b.content, bs, be); - else - bs++; - } - return as == ae && bs == be; - } - - @Override - protected int hashLine(final byte[] raw, int ptr, int end) { - int hash = 5381; - end = trimTrailingWhitespace(raw, ptr, end); - while (ptr < end) { - byte c = raw[ptr]; - hash = (hash << 5) ^ (c & 0xff); - if (isWhitespace(c)) - ptr = trimLeadingWhitespace(raw, ptr, end); - else - ptr++; - } - return hash; - } -}
\ No newline at end of file diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/Sequence.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/Sequence.java index 34f3f443f1..4e01c17da5 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/Sequence.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/Sequence.java @@ -1,4 +1,5 @@ /* + * Copyright (C) 2010, Google Inc. * Copyright (C) 2008-2009, Johannes E. Schindelin <johannes.schindelin@gmx.de> * and other copyright owners as documented in the project's IP log. * @@ -44,41 +45,20 @@ package org.eclipse.jgit.diff; /** - * Arbitrary sequence of elements with fast comparison support. - * <p> + * Arbitrary sequence of elements. + * * A sequence of elements is defined to contain elements in the index range * <code>[0, {@link #size()})</code>, like a standard Java List implementation. - * Unlike a List, the members of the sequence are not directly obtainable, but - * element equality can be tested if two Sequences are the same implementation. - * <p> - * An implementation may chose to implement the equals semantic as necessary, - * including fuzzy matching rules such as ignoring insignificant sub-elements, - * e.g. ignoring whitespace differences in text. - * <p> + * Unlike a List, the members of the sequence are not directly obtainable. + * * Implementations of Sequence are primarily intended for use in content * difference detection algorithms, to produce an {@link EditList} of * {@link Edit} instances describing how two Sequence instances differ. + * + * To be compared against another Sequence of the same type, a supporting + * {@link SequenceComparator} must also be supplied. */ -public interface Sequence { +public abstract class Sequence { /** @return total number of items in the sequence. */ - public int size(); - - /** - * Determine if the i-th member is equal to the j-th member. - * <p> - * Implementations must ensure <code>equals(thisIdx,other,otherIdx)</code> - * returns the same as <code>other.equals(otherIdx,this,thisIdx)</code>. - * - * @param thisIdx - * index within <code>this</code> sequence; must be in the range - * <code>[ 0, this.size() )</code>. - * @param other - * another sequence; must be the same implementation class, that - * is <code>this.getClass() == other.getClass()</code>. - * @param otherIdx - * index within <code>other</code> sequence; must be in the range - * <code>[ 0, other.size() )</code>. - * @return true if the elements are equal; false if they are not equal. - */ - public boolean equals(int thisIdx, Sequence other, int otherIdx); + public abstract int size(); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreLeadingWhitespace.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/SequenceComparator.java index df4805a4c8..5ec23510ec 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextIgnoreLeadingWhitespace.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/SequenceComparator.java @@ -1,6 +1,5 @@ /* - * Copyright (C) 2009-2010, Google Inc. - * Copyright (C) 2008-2009, Johannes E. Schindelin <johannes.schindelin@gmx.de> + * Copyright (C) 2010, Google Inc. * and other copyright owners as documented in the project's IP log. * * This program and the accompanying materials are made available @@ -44,68 +43,53 @@ package org.eclipse.jgit.diff; -import static org.eclipse.jgit.util.RawCharUtil.trimLeadingWhitespace; - /** - * A version of {@link RawText} that ignores leading whitespace. + * Equivalence function for a {@link Sequence} compared by difference algorithm. + * + * Difference algorithms can use a comparator to compare portions of two + * sequences and discover the minimal edits required to transform from one + * sequence to the other sequence. + * + * Indexes within a sequence are zero-based. + * + * @param <S> + * type of sequence the comparator supports. */ -public class RawTextIgnoreLeadingWhitespace extends RawText { - /** Creates RawText that ignores only leading whitespace. */ - @SuppressWarnings("hiding") - public static final Factory FACTORY = new Factory() { - public RawText create(byte[] input) { - return new RawTextIgnoreLeadingWhitespace(input); - } - }; - +public abstract class SequenceComparator<S extends Sequence> { /** - * Create a new sequence from an existing content byte array. - * <p> - * The entire array (indexes 0 through length-1) is used as the content. + * Compare two items to determine if they are equivalent. * - * @param input - * the content array. The array is never modified, so passing - * through cached arrays is safe. + * It is permissible to compare sequence {@code a} with itself (by passing + * {@code a} again in position {@code b}). + * + * @param a + * the first sequence. + * @param ai + * item of {@code ai} to compare. + * @param b + * the second sequence. + * @param bi + * item of {@code bi} to compare. + * @return true if the two items are identical according to this function's + * equivalence rule. */ - public RawTextIgnoreLeadingWhitespace(byte[] input) { - super(input); - } - - @Override - public boolean equals(final int i, final Sequence other, final int j) { - return equals(this, i + 1, (RawText) other, j + 1); - } - - private static boolean equals(final RawText a, final int ai, - final RawText b, final int bi) { - if (a.hashes[ai] != b.hashes[bi]) - return false; - - int as = a.lines.get(ai); - int bs = b.lines.get(bi); - int ae = a.lines.get(ai + 1); - int be = b.lines.get(bi + 1); + public abstract boolean equals(S a, int ai, S b, int bi); - as = trimLeadingWhitespace(a.content, as, ae); - bs = trimLeadingWhitespace(b.content, bs, be); - - if (ae - as != be - bs) - return false; - - while (as < ae) { - if (a.content[as++] != b.content[bs++]) - return false; - } - return true; - } - - @Override - protected int hashLine(final byte[] raw, int ptr, int end) { - int hash = 5381; - ptr = trimLeadingWhitespace(raw, ptr, end); - for (; ptr < end; ptr++) { - hash = (hash << 5) ^ (raw[ptr] & 0xff); - } - return hash; - } -}
\ No newline at end of file + /** + * Get a hash value for an item in a sequence. + * + * If two items are equal according to this comparator's + * {@link #equals(Sequence, int, Sequence, int)} method, then this hash + * method must produce the same integer result for both items. + * + * It is not required for two items to have different hash values if they + * are are unequal according to the {@code equals()} method. + * + * @param seq + * the sequence. + * @param ptr + * the item to obtain the hash for. + * @return hash the hash value. + */ + public abstract int hash(S seq, int ptr); +} |