tikhomirov@329: /* tikhomirov@419: * Copyright (c) 2011-2012 TMate Software Ltd tikhomirov@329: * tikhomirov@329: * This program is free software; you can redistribute it and/or modify tikhomirov@329: * it under the terms of the GNU General Public License as published by tikhomirov@329: * the Free Software Foundation; version 2 of the License. tikhomirov@329: * tikhomirov@329: * This program is distributed in the hope that it will be useful, tikhomirov@329: * but WITHOUT ANY WARRANTY; without even the implied warranty of tikhomirov@329: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the tikhomirov@329: * GNU General Public License for more details. tikhomirov@329: * tikhomirov@329: * For information on how to redistribute this software under tikhomirov@329: * the terms of a license other than GNU General Public License tikhomirov@329: * contact TMate Software at support@hg4j.com tikhomirov@329: */ tikhomirov@329: package org.tmatesoft.hg.internal; tikhomirov@329: tikhomirov@329: import java.io.IOException; tikhomirov@329: import java.util.ArrayList; tikhomirov@330: import java.util.Formatter; tikhomirov@329: tikhomirov@329: /** tikhomirov@419: * @see http://mercurial.selenic.com/wiki/BundleFormat tikhomirov@419: * in Changelog group description tikhomirov@329: * tikhomirov@329: * range [start..end] in original source gets replaced with data of length (do not keep, use data.length instead) tikhomirov@329: * range [end(i)..start(i+1)] is copied from the source tikhomirov@329: * tikhomirov@329: * @author Artem Tikhomirov tikhomirov@329: * @author TMate Software Ltd. tikhomirov@329: */ tikhomirov@329: public final class Patch { tikhomirov@329: private final IntVector starts, ends; tikhomirov@329: private final ArrayList data; tikhomirov@330: tikhomirov@330: private static byte[] generate(int c) { tikhomirov@330: byte[] rv = new byte[c]; tikhomirov@330: for (int i = 0; i < c; i++) { tikhomirov@330: byte x = (byte) ('a' + i); tikhomirov@330: rv[i] = x; tikhomirov@330: } tikhomirov@330: return rv; tikhomirov@330: } tikhomirov@330: tikhomirov@330: public static void main(String[] args) { tikhomirov@330: Patch p1 = new Patch(), p2 = new Patch(); tikhomirov@330: // simple cases (one element in either patch) tikhomirov@330: // III: (1,10 20) & (5,15,15) p2End from [p1End..p1AppliedEnd] (i.e. within p1 range but index is past p2 end index) tikhomirov@330: // II: (1,10,7) & (3,15,15) insideP2 = true and no more p1 entries tikhomirov@330: // II: (1,1,10) & (3,11,15) tikhomirov@330: // independent: (1,10,10) & (15,25,10); (15, 25, 10) & (1, 10, 10) tikhomirov@330: // I: (15, 25, 10) & (10, 20, 10). result: [10, 20, 10] [20, 25, 5] tikhomirov@330: // IV: (15, 25, 10) & (10, 30, 20) tikhomirov@330: // tikhomirov@330: // cycle with insideP2 tikhomirov@330: // tikhomirov@330: // cycle with insideP1 tikhomirov@330: // tikhomirov@330: // multiple elements in patches (offsets) tikhomirov@330: p1.add(15, 25, generate(10)); tikhomirov@330: p2.add(10, 30, generate(20)); tikhomirov@330: System.out.println("p1: " + p1); tikhomirov@330: System.out.println("p2: " + p2); tikhomirov@330: Patch r = p1.apply(p2); tikhomirov@330: System.out.println("r: " + r); tikhomirov@330: } tikhomirov@330: tikhomirov@329: public Patch() { tikhomirov@329: starts = new IntVector(); tikhomirov@329: ends = new IntVector(); tikhomirov@329: data = new ArrayList(); tikhomirov@329: } tikhomirov@329: tikhomirov@330: public String toString() { tikhomirov@330: StringBuilder sb = new StringBuilder(); tikhomirov@330: Formatter f = new Formatter(sb); tikhomirov@330: for (int i = 0; i < count(); i++) { tikhomirov@330: f.format("[%d, %d, %d] ", starts.get(i), ends.get(i), data.get(i).length); tikhomirov@330: } tikhomirov@330: return sb.toString(); tikhomirov@330: } tikhomirov@330: tikhomirov@329: public int count() { tikhomirov@329: return data.size(); tikhomirov@329: } tikhomirov@329: tikhomirov@329: // number of bytes this patch will add (or remove, if negative) from the base revision tikhomirov@329: private int patchSizeDelta() { tikhomirov@329: int rv = 0; tikhomirov@329: int prevEnd = 0; tikhomirov@329: for (int i = 0, x = data.size(); i < x; i++) { tikhomirov@329: final int start = starts.get(i); tikhomirov@329: final int len = data.get(i).length; tikhomirov@329: rv += start - prevEnd; // would copy from original tikhomirov@329: rv += len; // and add new tikhomirov@329: prevEnd = ends.get(i); tikhomirov@329: } tikhomirov@329: rv -= prevEnd; tikhomirov@329: return rv; tikhomirov@329: } tikhomirov@329: tikhomirov@329: public byte[] apply(DataAccess baseRevisionContent, int outcomeLen) throws IOException { tikhomirov@329: if (outcomeLen == -1) { tikhomirov@329: outcomeLen = baseRevisionContent.length() + patchSizeDelta(); tikhomirov@329: } tikhomirov@329: int prevEnd = 0, destIndex = 0; tikhomirov@329: byte[] rv = new byte[outcomeLen]; tikhomirov@329: for (int i = 0, x = data.size(); i < x; i++) { tikhomirov@329: final int start = starts.get(i); tikhomirov@329: baseRevisionContent.seek(prevEnd); tikhomirov@329: // copy source bytes that were not modified (up to start of the record) tikhomirov@329: baseRevisionContent.readBytes(rv, destIndex, start - prevEnd); tikhomirov@329: destIndex += start - prevEnd; tikhomirov@329: // insert new data from the patch, if any tikhomirov@329: byte[] d = data.get(i); tikhomirov@532: System.arraycopy(d, 0, rv, destIndex, d.length); tikhomirov@329: destIndex += d.length; tikhomirov@329: prevEnd = ends.get(i); tikhomirov@329: } tikhomirov@329: baseRevisionContent.seek(prevEnd); tikhomirov@329: // copy everything in the source past last record's end tikhomirov@420: baseRevisionContent.readBytes(rv, destIndex, (baseRevisionContent.length() - prevEnd)); tikhomirov@329: return rv; tikhomirov@329: } tikhomirov@329: tikhomirov@329: public void clear() { tikhomirov@329: starts.clear(); tikhomirov@329: ends.clear(); tikhomirov@329: data.clear(); tikhomirov@329: } tikhomirov@329: tikhomirov@329: /** tikhomirov@329: * Initialize instance from stream. Any previous patch information (i.e. if instance if reused) is cleared first. tikhomirov@329: * Read up to the end of DataAccess and interpret data as patch records. tikhomirov@329: */ tikhomirov@329: public void read(DataAccess da) throws IOException { tikhomirov@329: clear(); tikhomirov@329: while (!da.isEmpty()) { tikhomirov@329: readOne(da); tikhomirov@329: } tikhomirov@329: } tikhomirov@329: tikhomirov@329: /** tikhomirov@329: * Caller is responsible to ensure stream got some data to read tikhomirov@329: */ tikhomirov@329: public void readOne(DataAccess da) throws IOException { tikhomirov@329: int s = da.readInt(); tikhomirov@329: int e = da.readInt(); tikhomirov@329: int len = da.readInt(); tikhomirov@329: byte[] src = new byte[len]; tikhomirov@329: da.readBytes(src, 0, len); tikhomirov@329: starts.add(s); tikhomirov@329: ends.add(e); tikhomirov@329: data.add(src); tikhomirov@329: } tikhomirov@329: tikhomirov@330: private void add(Patch p, int i) { tikhomirov@330: add(p.starts.get(i), p.ends.get(i), p.data.get(i)); tikhomirov@330: } tikhomirov@330: tikhomirov@330: private void add(int start, int end, byte[] d) { tikhomirov@330: starts.add(start); tikhomirov@330: ends.add(end); tikhomirov@330: data.add(d); tikhomirov@330: } tikhomirov@330: tikhomirov@330: private static byte[] subarray(byte[] d, int start, int end) { tikhomirov@330: byte[] r = new byte[end-start+1]; tikhomirov@330: System.arraycopy(d, start, r, 0, r.length); tikhomirov@330: return r; tikhomirov@329: } tikhomirov@329: tikhomirov@329: /** tikhomirov@329: * Modify this patch with subsequent patch tikhomirov@330: */ tikhomirov@330: private /*SHALL BE PUBLIC ONCE TESTING ENDS*/ Patch apply(Patch another) { tikhomirov@329: Patch r = new Patch(); tikhomirov@330: int p1TotalAppliedDelta = 0; // value to add to start and end indexes of the older patch to get their values as if tikhomirov@330: // in the patched text, iow, directly comparable with respective indexes from the newer patch. tikhomirov@330: int p1EntryStart = 0, p1EntryEnd = 0, p1EntryLen = 0; tikhomirov@330: byte[] p1Data = null; tikhomirov@330: boolean insideP1entry = false; tikhomirov@330: int p2 = 0, p1 = 0; tikhomirov@330: final int p2Max = another.count(), p1Max = this.count(); tikhomirov@330: L0: for (; p2 < p2Max; p2++) { tikhomirov@330: int p2EntryStart = another.starts.get(p2); tikhomirov@330: int p2EntryEnd = another.ends.get(p2); tikhomirov@330: final int p2EntryRange = p2EntryEnd - p2EntryStart; tikhomirov@330: final byte[] p2Data = another.data.get(p2); tikhomirov@330: boolean insideP2entry = false; tikhomirov@330: int p2EntryStartOffset = -1; tikhomirov@330: /// tikhomirov@330: p1EntryStart = p1EntryEnd = p1EntryLen = 0; tikhomirov@330: p1Data = null; tikhomirov@329: tikhomirov@330: L1: while (p1 < p1Max) { tikhomirov@330: if (!insideP1entry) { tikhomirov@330: p1EntryStart = starts.get(p1); tikhomirov@330: p1EntryEnd = ends.get(p1); tikhomirov@330: p1Data = data.get(p1); tikhomirov@330: p1EntryLen = p1Data.length; tikhomirov@330: }// else keep values tikhomirov@330: tikhomirov@330: final int p1EntryDelta = p1EntryLen - (p1EntryEnd - p1EntryStart); // number of actually inserted(+) or deleted(-) chars tikhomirov@330: final int p1EntryAppliedStart = p1TotalAppliedDelta + p1EntryStart; tikhomirov@330: final int p1EntryAppliedEnd = p1EntryAppliedStart + p1EntryLen; // end of j'th patch entry in the text which is source for p2 tikhomirov@330: tikhomirov@330: if (insideP2entry) { tikhomirov@330: if (p2EntryEnd < p1EntryAppliedStart) { tikhomirov@330: r.add(p2EntryStart - p2EntryStartOffset, p2EntryEnd - p1TotalAppliedDelta, p2Data); tikhomirov@330: insideP2entry = false; tikhomirov@330: continue L0; tikhomirov@330: } tikhomirov@330: if (p2EntryEnd >= p1EntryAppliedEnd) { tikhomirov@330: // when p2EntryEnd == p1EntryAppliedEnd, I assume p1TotalAppliedDelta can't be used for p2EntryEnd to get it to p1 range, but rather shall be tikhomirov@330: // augmented with current p1 entry and at the next p1 entry (likely to hit p1EntryAppliedStart > p2EntryEnd above) would do the rest tikhomirov@330: insideP1entry = false; tikhomirov@330: p1++; tikhomirov@330: p1TotalAppliedDelta += p1EntryDelta; tikhomirov@330: continue L1; tikhomirov@330: } tikhomirov@330: // p1EntryAppliedStart <= p2EntryEnd < p1EntryAppliedEnd tikhomirov@330: r.add(p2EntryStart - p2EntryStartOffset, p2EntryEnd - p1TotalAppliedDelta, p2Data); tikhomirov@330: p1EntryStart = p2EntryEnd - p1TotalAppliedDelta; tikhomirov@330: final int p1DataPartShift = p2EntryEnd - p1EntryAppliedStart + 1; tikhomirov@330: if (p1DataPartShift >= p1EntryLen) { tikhomirov@330: p1EntryLen = 0; tikhomirov@330: p1Data = new byte[0]; tikhomirov@329: } else { tikhomirov@330: p1EntryLen -= p1DataPartShift; tikhomirov@330: p1Data = subarray(p1Data, p1DataPartShift, p1Data.length); tikhomirov@330: } tikhomirov@330: insideP1entry = true; tikhomirov@330: insideP2entry = false; tikhomirov@330: continue L0; tikhomirov@330: } tikhomirov@330: tikhomirov@330: if (p1EntryAppliedStart < p2EntryStart) { tikhomirov@330: if (p1EntryAppliedEnd <= p2EntryStart) { // p1EntryAppliedEnd in fact index of the first char *after* patch tikhomirov@330: // completely independent, copy and continue tikhomirov@330: r.add(p1EntryStart, p1EntryEnd, p1Data); tikhomirov@330: insideP1entry = false; tikhomirov@330: p1++; tikhomirov@330: // fall-through to get p1TotalAppliedDelta incremented tikhomirov@330: } else { // SKETCH: II or III tikhomirov@330: // remember, p1EntryDelta may be negative tikhomirov@330: // shall break j'th entry into few tikhomirov@330: // fix p1's end/length tikhomirov@330: // p1EntryAppliedStart < p2EntryStart < p1EntryAppliedEnd tikhomirov@330: int s = p2EntryStart - p1TotalAppliedDelta; // p2EntryStart in p1 scale. Is within p1 range tikhomirov@330: if (s > p1EntryEnd) { tikhomirov@330: s = p1EntryEnd; tikhomirov@330: } tikhomirov@330: int p1DataPartEnd = p2EntryStart - p1EntryAppliedStart; // index, not count. <= (p1EntryEnd-p1EntryStart). tikhomirov@330: // add what left from p1 tikhomirov@330: if (p1DataPartEnd < p1EntryLen) { tikhomirov@330: r.add(p1EntryStart, s, subarray(p1Data, 0, p1DataPartEnd)); tikhomirov@330: } else { tikhomirov@330: p1DataPartEnd = p1EntryLen-1; // record factual number of p1 bytes we consumed. tikhomirov@330: r.add(p1EntryStart, s, p1Data); tikhomirov@330: } tikhomirov@330: p1TotalAppliedDelta += p1DataPartEnd - (s - p1EntryStart); // (s2 - (s1+delta)) - (s2 - delta - s1) = s2-s1-delta-s2+delta+s1 = 0, unless p1DataPartEnd >= p1Data.length tikhomirov@330: p1EntryLen -= (p1DataPartEnd+1); tikhomirov@330: if (p2EntryEnd < p1EntryAppliedEnd) { tikhomirov@330: // SKETCH: III tikhomirov@330: insideP1entry = true; tikhomirov@330: // p2 completely fits into changes of p1 tikhomirov@330: int e = p2EntryEnd - p1TotalAppliedDelta; // p2EntryEnd in p1 scale tikhomirov@330: if (e > p1EntryEnd) { tikhomirov@330: // any index past p1 end shall be calculated with respect to p1 end, thus it's unsafe to go past p1 end (there may be more p1 entries there) tikhomirov@330: e = p1EntryEnd; tikhomirov@330: } tikhomirov@330: r.add(s, e, p2Data); // add p2 tikhomirov@330: // modify p1 leftover tikhomirov@330: p1EntryStart = e; tikhomirov@330: if (p2EntryRange >= p1EntryLen) { tikhomirov@330: p1EntryLen = 0; tikhomirov@330: p1Data = new byte[0]; tikhomirov@330: } else { tikhomirov@330: p1Data = subarray(p1Data, p1DataPartEnd + p2EntryRange, p1Data.length-1 /*up to the last one*/); tikhomirov@330: p1EntryLen -= p2EntryRange; tikhomirov@330: } tikhomirov@330: // p2 is handled, but there are leftovers of p1 tikhomirov@330: continue L0; tikhomirov@330: } else { // p2EntryEnd >= p1EntryAppliedEnd tikhomirov@330: // SKETCH: II tikhomirov@330: insideP1entry = false; tikhomirov@330: p1++; tikhomirov@330: if (p1EntryAppliedStart + p1EntryDelta >= p2EntryEnd) { tikhomirov@330: // here we know next p1 entry would be past p2 entry and thus can put p2 right away tikhomirov@330: r.add(p2EntryStart - p1TotalAppliedDelta, p1EntryEnd, p2Data); tikhomirov@330: p1TotalAppliedDelta += p1EntryDelta; tikhomirov@330: continue L0; tikhomirov@330: } else { tikhomirov@330: // there are chances there are more p1 entries till p2 ends tikhomirov@330: insideP2entry = true; tikhomirov@330: p2EntryStartOffset = p1TotalAppliedDelta; tikhomirov@330: // p2EntryEnd is past delta, no chances for p1Data leftovers to be in use tikhomirov@330: // p2 processing is not over, need to fix end, depending on what else fits into p2 range (if nothing, can put p2.end right away) tikhomirov@330: // fall-through to get p1TotalAppliedDelta incremented; tikhomirov@330: } tikhomirov@330: } tikhomirov@330: } tikhomirov@330: } else { // p1EntryAppliedStart >= p2EntryStart tikhomirov@330: if (p2EntryEnd < p1EntryAppliedStart) { tikhomirov@330: // newer patch completely fits between two older patches tikhomirov@330: r.add(p2EntryStart - p1TotalAppliedDelta, p2EntryEnd - p1TotalAppliedDelta, p2Data); tikhomirov@330: // SHALL NOT increment p1TotalAppliedDelta as we didn't use any of p1 tikhomirov@330: continue L0; // next p2 tikhomirov@330: } else { // p2EntryEnd >= p1EntryAppliedStart tikhomirov@330: // SKETCH: I or IV tikhomirov@330: // p2EntryEnd is either < p1EntryAppliedEnd or past it tikhomirov@330: if (p2EntryEnd <= p1EntryAppliedEnd) { tikhomirov@330: // SKETCH: I: copy p2, strip p1 to start from p2EntryEnd, next i (p2) tikhomirov@330: insideP1entry = true; tikhomirov@330: int e = p2EntryEnd - p1TotalAppliedDelta; tikhomirov@330: if (e > p1EntryEnd) { tikhomirov@330: e = p1EntryEnd; // added by analogy with above. Is needed? tikhomirov@330: } tikhomirov@330: r.add(p2EntryStart - p1TotalAppliedDelta, e, p2Data); tikhomirov@330: p1EntryStart = e; tikhomirov@330: int p1DataShift = p2EntryEnd - p1EntryAppliedStart; tikhomirov@330: if (p1DataShift >= p1EntryLen) { tikhomirov@330: p1EntryLen = 0; tikhomirov@330: p1Data = new byte[0]; tikhomirov@330: } else { tikhomirov@330: p1EntryLen -= p1DataShift; tikhomirov@330: p1Data = subarray(p1Data, p1DataShift, p1Data.length - 1); tikhomirov@330: } tikhomirov@330: // p1TotalAppliedDelta would get incremented once this modified p1 is handled tikhomirov@330: continue L0; // next p2; tikhomirov@330: } else { tikhomirov@330: // p2EntryEnd > p1EntryAppliedEnd tikhomirov@330: // SKETCH IV: skip (rest of) p1 completely, continue the same unless found p1 with start or end past p2EntryEnd. tikhomirov@330: insideP1entry = false; tikhomirov@330: p1++; tikhomirov@330: insideP2entry = true; tikhomirov@330: p2EntryStartOffset = p1TotalAppliedDelta; tikhomirov@330: // fall-through to get p1TotalAppliedDelta incremented tikhomirov@330: } tikhomirov@329: } tikhomirov@329: } tikhomirov@330: p1TotalAppliedDelta += p1EntryDelta; tikhomirov@330: } // while (p1 < p1Max) tikhomirov@330: { tikhomirov@330: // no more p1 entries, shall close p2 (if it's handled, code above jumps directly to L0) tikhomirov@330: // regardless of whether insideP2 is .t tikhomirov@330: int s = p2EntryStart; tikhomirov@330: // p2EntryStartOffset != -1 when we started p2 entry processing, but not completed tikhomirov@330: // if we handled last p1 entry but didn't start with p2 entry processing, it's -1 and regular p1 delta shall be used tikhomirov@330: s -= p2EntryStartOffset == -1 ? p1TotalAppliedDelta : p2EntryStartOffset; tikhomirov@330: r.add(s, p2EntryEnd - p1TotalAppliedDelta, p2Data); tikhomirov@329: } tikhomirov@329: } tikhomirov@330: if (p1 < p1Max && insideP1entry) { tikhomirov@330: r.add(p1EntryStart, p1EntryEnd, p1Data); tikhomirov@330: p1++; tikhomirov@330: } tikhomirov@330: while (p1 < p1Max) { tikhomirov@330: r.add(this, p1); tikhomirov@330: p1++; tikhomirov@330: }; tikhomirov@330: return r; tikhomirov@329: } tikhomirov@329: }