hg4j: src/org/tmatesoft/hg/internal/Patch.java annotate

annotate src/org/tmatesoft/hg/internal/Patch.java @ 705:b4242b7e7dfe

Merge command: implement conflict resolution alternatives

author	Artem Tikhomirov <tikhomirov.artem@gmail.com>
date	Thu, 15 Aug 2013 18:43:50 +0200
parents	7c0d2ce340b8
children

rev	line source
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	1 /*
533 e6f72c9829a6 Generate patches using diff algorithm Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 532 diff changeset	2 * Copyright (c) 2011-2013 TMate Software Ltd
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	3 *
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	4 * This program is free software; you can redistribute it and/or modify
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	5 * it under the terms of the GNU General Public License as published by
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	6 * the Free Software Foundation; version 2 of the License.
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	7 *
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	8 * This program is distributed in the hope that it will be useful,
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	11 * GNU General Public License for more details.
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	12 *
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	13 * For information on how to redistribute this software under
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	14 * the terms of a license other than GNU General Public License
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	15 * contact TMate Software at support@hg4j.com
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	16 */
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	17 package org.tmatesoft.hg.internal;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	18
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	19 import java.io.IOException;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	20 import java.util.ArrayList;
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	21 import java.util.Formatter;
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	22
618 7c0d2ce340b8 Refactor approach how content finds it way down to a commit revision Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 587 diff changeset	23 import org.tmatesoft.hg.core.HgIOException;
7c0d2ce340b8 Refactor approach how content finds it way down to a commit revision Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 587 diff changeset	24
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	25 /**
419 7f136a3fa671 Clean javadoc to fix obvious warnings Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 330 diff changeset	26 * @see http://mercurial.selenic.com/wiki/BundleFormat
7f136a3fa671 Clean javadoc to fix obvious warnings Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 330 diff changeset	27 * in Changelog group description
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	28 *
533 e6f72c9829a6 Generate patches using diff algorithm Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 532 diff changeset	29 * range [start..end) in original source gets replaced with data of length (do not keep, use data.length instead)
e6f72c9829a6 Generate patches using diff algorithm Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 532 diff changeset	30 * range [end(i)..start(i+1)) is copied from the source
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	31 *
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	32 * @author Artem Tikhomirov
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	33 * @author TMate Software Ltd.
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	34 */
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	35 public final class Patch {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	36 private final IntVector starts, ends;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	37 private final ArrayList<byte[]> data;
584 ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	38 private final boolean shallNormalize;
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	39
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	40 private static byte[] generate(int c) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	41 byte[] rv = new byte[c];
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	42 for (int i = 0; i < c; i++) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	43 byte x = (byte) ('a' + i);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	44 rv[i] = x;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	45 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	46 return rv;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	47 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	48
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	49 public static void main(String[] args) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	50 Patch p1 = new Patch(), p2 = new Patch();
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	51 // simple cases (one element in either patch)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	52 // III: (1,10 20) & (5,15,15) p2End from [p1End..p1AppliedEnd] (i.e. within p1 range but index is past p2 end index)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	53 // II: (1,10,7) & (3,15,15) insideP2 = true and no more p1 entries
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	54 // II: (1,1,10) & (3,11,15)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	55 // independent: (1,10,10) & (15,25,10); (15, 25, 10) & (1, 10, 10)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	56 // I: (15, 25, 10) & (10, 20, 10). result: [10, 20, 10] [20, 25, 5]
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	57 // IV: (15, 25, 10) & (10, 30, 20)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	58 //
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	59 // cycle with insideP2
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	60 //
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	61 // cycle with insideP1
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	62 //
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	63 // multiple elements in patches (offsets)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	64 p1.add(15, 25, generate(10));
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	65 p2.add(10, 30, generate(20));
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	66 System.out.println("p1: " + p1);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	67 System.out.println("p2: " + p2);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	68 Patch r = p1.apply(p2);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	69 System.out.println("r: " + r);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	70 }
584 ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	71
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	72 public Patch() {
587 a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	73 this(16, false);
a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	74 }
a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	75
a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	76 public Patch(boolean normalizeOnChange) {
a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	77 this(16, normalizeOnChange);
584 ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	78 }
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	79
587 a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	80 public Patch(int sizeHint, boolean normalizeOnChange) {
584 ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	81 shallNormalize = normalizeOnChange;
587 a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	82 starts = new IntVector(sizeHint, -1);
a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	83 ends = new IntVector(sizeHint, -1);
a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	84 data = new ArrayList<byte[]>(sizeHint);
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	85 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	86
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	87 public String toString() {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	88 StringBuilder sb = new StringBuilder();
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	89 Formatter f = new Formatter(sb);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	90 for (int i = 0; i < count(); i++) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	91 f.format("[%d, %d, %d] ", starts.get(i), ends.get(i), data.get(i).length);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	92 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	93 return sb.toString();
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	94 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	95
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	96 public int count() {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	97 return data.size();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	98 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	99
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	100 // number of bytes this patch will add (or remove, if negative) from the base revision
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	101 public int patchSizeDelta() {
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	102 int rv = 0;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	103 int prevEnd = 0;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	104 for (int i = 0, x = data.size(); i < x; i++) {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	105 final int start = starts.get(i);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	106 final int len = data.get(i).length;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	107 rv += start - prevEnd; // would copy from original
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	108 rv += len; // and add new
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	109 prevEnd = ends.get(i);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	110 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	111 rv -= prevEnd;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	112 return rv;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	113 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	114
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	115 public byte[] apply(DataAccess baseRevisionContent, int outcomeLen) throws IOException {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	116 if (outcomeLen == -1) {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	117 outcomeLen = baseRevisionContent.length() + patchSizeDelta();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	118 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	119 int prevEnd = 0, destIndex = 0;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	120 byte[] rv = new byte[outcomeLen];
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	121 for (int i = 0, x = data.size(); i < x; i++) {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	122 final int start = starts.get(i);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	123 baseRevisionContent.seek(prevEnd);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	124 // copy source bytes that were not modified (up to start of the record)
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	125 baseRevisionContent.readBytes(rv, destIndex, start - prevEnd);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	126 destIndex += start - prevEnd;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	127 // insert new data from the patch, if any
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	128 byte[] d = data.get(i);
532 688c1ab113bb Introduce explicit reference to base patch in bundle's group element, use it when cloning to fix defect when few revisions list null,null parents Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 530 diff changeset	129 System.arraycopy(d, 0, rv, destIndex, d.length);
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	130 destIndex += d.length;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	131 prevEnd = ends.get(i);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	132 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	133 baseRevisionContent.seek(prevEnd);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	134 // copy everything in the source past last record's end
420 6c22bdc0bdfd Respect long offsets in revlogs Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 419 diff changeset	135 baseRevisionContent.readBytes(rv, destIndex, (baseRevisionContent.length() - prevEnd));
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	136 return rv;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	137 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	138
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	139 public void clear() {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	140 starts.clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	141 ends.clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	142 data.clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	143 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	144
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	145 /**
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	146 * Initialize instance from stream. Any previous patch information (i.e. if instance if reused) is cleared first.
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	147 * Read up to the end of DataAccess and interpret data as patch records.
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	148 */
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	149 public void read(DataAccess da) throws IOException {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	150 clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	151 while (!da.isEmpty()) {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	152 readOne(da);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	153 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	154 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	155
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	156 /**
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	157 * Caller is responsible to ensure stream got some data to read
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	158 */
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	159 public void readOne(DataAccess da) throws IOException {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	160 int s = da.readInt();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	161 int e = da.readInt();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	162 int len = da.readInt();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	163 byte[] src = new byte[len];
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	164 da.readBytes(src, 0, len);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	165 starts.add(s);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	166 ends.add(e);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	167 data.add(src);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	168 }
534 243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	169
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	170 /**
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	171 * @return how many bytes the patch would take if written down using BundleFormat structure (start, end, length, data)
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	172 */
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	173 public int serializedLength() {
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	174 int totalDataLen = 0;
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	175 for (byte[] d : data) {
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	176 totalDataLen += d.length;
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	177 }
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	178 int prefix = 3 * 4 * count(); // 3 integer fields per entry * sizeof(int) * number of entries
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	179 return prefix + totalDataLen;
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	180 }
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	181
618 7c0d2ce340b8 Refactor approach how content finds it way down to a commit revision Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 587 diff changeset	182 /package-local/ void serialize(DataSerializer out) throws HgIOException {
534 243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	183 for (int i = 0, x = data.size(); i < x; i++) {
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	184 final int start = starts.get(i);
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	185 final int end = ends.get(i);
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	186 byte[] d = data.get(i);
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	187 out.writeInt(start, end, d.length);
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	188 out.write(d, 0, d.length);
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	189 }
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	190 }
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	191
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	192 private void add(Patch p, int i) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	193 add(p.starts.get(i), p.ends.get(i), p.data.get(i));
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	194 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	195
533 e6f72c9829a6 Generate patches using diff algorithm Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 532 diff changeset	196 /package-local/ void add(int start, int end, byte[] d) {
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	197 if (start == end && d.length == 0) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	198 System.currentTimeMillis();
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	199 return;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	200 }
584 ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	201 int last;
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	202 if (shallNormalize && (last = starts.size()) > 0) {
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	203 last--;
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	204 if (ends.get(last) == start) {
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	205 byte[] d1 = data.get(last);
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	206 byte[] nd;
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	207 if (d1.length > 0 && d.length > 0) {
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	208 nd = new byte[d1.length + d.length];
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	209 System.arraycopy(d1, 0, nd, 0, d1.length);
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	210 System.arraycopy(d, 0, nd, d1.length, d.length);
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	211 } else {
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	212 nd = d1.length == 0 ? d : d1 ;
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	213 }
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	214 ends.set(last, end);
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	215 data.set(last, nd);
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	216 return;
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	217 }
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	218 // fall-through
ed243b668502 Conditionally enable effective patch merge alternative for revlog reading Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 583 diff changeset	219 }
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	220 starts.add(start);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	221 ends.add(end);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	222 data.add(d);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	223 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	224
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	225 // copies [start..end) bytes from the d
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	226 private static byte[] subarray(byte[] d, int start, int end) {
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	227 byte[] r = new byte[end-start];
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	228 System.arraycopy(d, start, r, 0, r.length);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	229 return r;
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	230 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	231
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	232 /**
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	233 * Modify this patch with subsequent patch
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	234 */
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	235 public /SHALL BE PUBLIC ONCE TESTING ENDS/ Patch apply(Patch another) {
587 a52f4cc56f9c Minimize vectors re-allocating when merging patches Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 584 diff changeset	236 Patch r = new Patch(count() + another.count() * 2, shallNormalize);
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	237 int p1TotalAppliedDelta = 0; // value to add to start and end indexes of the older patch to get their values as if
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	238 // in the patched text, iow, directly comparable with respective indexes from the newer patch.
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	239 int p1EntryStart = 0, p1EntryEnd = 0, p1EntryLen = 0;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	240 byte[] p1Data = null;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	241 boolean insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	242 int p2 = 0, p1 = 0;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	243 final int p2Max = another.count(), p1Max = this.count();
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	244 L0: for (; p2 < p2Max; p2++) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	245 int p2EntryStart = another.starts.get(p2);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	246 int p2EntryEnd = another.ends.get(p2);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	247 final int p2EntryRange = p2EntryEnd - p2EntryStart;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	248 final byte[] p2Data = another.data.get(p2);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	249 boolean insideP2entry = false;
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	250 // when we iterate p1 elements within single p2, we need to remember where p2
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	251 // shall ultimately start in terms of p1
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	252 int p2EntrySavedStart = -1;
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	253 ///
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	254
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	255 L1: while (p1 < p1Max) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	256 if (!insideP1entry) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	257 p1EntryStart = starts.get(p1);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	258 p1EntryEnd = ends.get(p1);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	259 p1Data = data.get(p1);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	260 p1EntryLen = p1Data.length;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	261 }// else keep values
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	262
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	263 final int p1EntryDelta = p1EntryLen - (p1EntryEnd - p1EntryStart); // number of actually inserted(+) or deleted(-) chars
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	264 final int p1EntryAppliedStart = p1TotalAppliedDelta + p1EntryStart;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	265 final int p1EntryAppliedEnd = p1EntryAppliedStart + p1EntryLen; // end of j'th patch entry in the text which is source for p2
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	266
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	267 if (insideP2entry) {
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	268 if (p2EntryEnd <= p1EntryAppliedStart) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	269 r.add(p2EntrySavedStart, p2EntryEnd - p1TotalAppliedDelta, p2Data);
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	270 insideP2entry = false;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	271 continue L0;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	272 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	273 if (p2EntryEnd >= p1EntryAppliedEnd) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	274 // when p2EntryEnd == p1EntryAppliedEnd, I assume p1TotalAppliedDelta can't be used for p2EntryEnd to get it to p1 range, but rather shall be
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	275 // augmented with current p1 entry and at the next p1 entry (likely to hit p1EntryAppliedStart > p2EntryEnd above) would do the rest
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	276 insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	277 p1++;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	278 p1TotalAppliedDelta += p1EntryDelta;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	279 continue L1;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	280 }
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	281 // p1EntryAppliedStart < p2EntryEnd < p1EntryAppliedEnd
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	282 // can add up to p1EntryEnd here (not only to p1EntryStart), but decided
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	283 // to leave p1 intact here, to avoid delta/range recalculation
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	284 r.add(p2EntrySavedStart, p1EntryStart, p2Data);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	285 // consume part of p1 overlapped by current p2
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	286 final int p1DataPartShift = p2EntryEnd - p1EntryAppliedStart;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	287 // p2EntryEnd < p1EntryAppliedEnd ==> p2EntryEnd < p1EntryAppliedStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	288 // ==> p2EntryEnd - p1EntryAppliedStart < p1EntryLen
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	289 assert p1DataPartShift < p1EntryLen;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	290 p1EntryLen -= p1DataPartShift;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	291 p1Data = subarray(p1Data, p1DataPartShift, p1Data.length);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	292 p1TotalAppliedDelta += p1DataPartShift;
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	293 insideP1entry = true;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	294 insideP2entry = false;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	295 continue L0;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	296 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	297
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	298 if (p1EntryAppliedStart < p2EntryStart) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	299 if (p1EntryAppliedEnd <= p2EntryStart) { // p1EntryAppliedEnd in fact index of the first char after patch
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	300 // completely independent, copy and continue
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	301 r.add(p1EntryStart, p1EntryEnd, p1Data);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	302 insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	303 p1++;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	304 // fall-through to get p1TotalAppliedDelta incremented
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	305 } else { // SKETCH: II or III - p2 start inside p1 range
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	306 // remember, p1EntryDelta may be negative
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	307 // shall break j'th entry into few
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	308 // fix p1's end/length
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	309 // p1EntryAppliedStart < p2EntryStart < p1EntryAppliedEnd, or, alternatively
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	310 // p2EntryStart is from (p1EntryAppliedStart .. p1EntryAppliedStart + p1EntryLen)
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	311 int p1DataPartEnd = p2EntryStart - p1EntryAppliedStart;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	312 assert p1DataPartEnd < p1EntryLen;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	313 r.add(p1EntryStart, p1EntryEnd, subarray(p1Data, 0, p1DataPartEnd));
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	314 if (p2EntryEnd <= p1EntryAppliedEnd) { // p2 fits completely into p1
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	315 r.add(p1EntryEnd, p1EntryEnd, p2Data);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	316 // p2 consumed, p1 has p1EntryLen - p1DataPartEnd - p2EntryRange bytes left to insert
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	317 insideP1entry = true;
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	318 p1EntryStart = p1EntryEnd;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	319 p1EntryLen -= p1DataPartEnd;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	320 p1EntryLen -= p2EntryRange;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	321 // p2EntryEnd <= p1EntryAppliedEnd ==> p2EntryEnd <= p1EntryAppliedStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	322 // -p2EntryStart ==> p2EntryRange <= p1EntryAppliedStart-p2EntryStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	323 // p1EntryAppliedStart-p2EntryStart = -p1DataPartEnd ==> p2EntryRange <= p1EntryLen - p1DataEndPart
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	324 // +p1DataEndPart ==> p2EntryRange + p1DataEndPart <= p1EntryLen
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	325 assert p1EntryLen >= 0;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	326 // p1EntryLen==0 with insideP1entry == true is nor really good here (gives empty patch elements x;x;0),
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	327 // however changing <= to < in p2EntryEnd <= p1EntryAppliedEnd above leads to errors
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	328 p1Data = subarray(p1Data, p1DataPartEnd+p2EntryRange, p1Data.length);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	329 // augment total delta with p1EntryDelta part already consumed (p1EntryLen is pure insertion left for the next step)
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	330 p1TotalAppliedDelta += (p1EntryDelta - p1EntryLen);
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	331 continue L0;
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	332 } else {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	333 // p1 is consumed, take next
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	334 insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	335 p1++;
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	336 insideP2entry = true;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	337 p2EntrySavedStart = p1EntryEnd; // this is how far we've progressed in p1
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	338 // fall-through to get p1TotalAppliedDelta updated with consumed p1
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	339 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	340 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	341 } else { // p1EntryAppliedStart >= p2EntryStart
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	342 if (p2EntryEnd < p1EntryAppliedStart) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	343 // newer patch completely fits between two older patches
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	344 r.add(p2EntryStart - p1TotalAppliedDelta, p2EntryEnd - p1TotalAppliedDelta, p2Data);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	345 // SHALL NOT increment p1TotalAppliedDelta as we didn't use any of p1
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	346 continue L0; // next p2
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	347 } else { // p2EntryEnd >= p1EntryAppliedStart
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	348 // SKETCH: I or IV:
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	349 // p2 start is outside of p1 range.
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	350 //
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	351 // p2DataPartEnd: this is how many bytes prior to p1EntryStart is replaced by p2Data
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	352 int p2DataPartEnd = p1EntryAppliedStart - p2EntryStart;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	353 if (p2EntryEnd < p1EntryAppliedEnd) {
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	354 // SKETCH: I: copy p2, strip p1 to start from p2EntryEnd, next i (p2)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	355 insideP1entry = true;
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	356 // replace whole p1 (extended to the left by (p2 \ p1) front bytes)
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	357 r.add(p1EntryStart - p2DataPartEnd, p1EntryEnd, p2Data);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	358 p1EntryStart = p1EntryEnd;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	359 // see how much of p1 is left for insertion
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	360 int p1DataPartEnd = p2EntryEnd - p1EntryAppliedStart; // #1
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	361 // Similar, although incorrect: p1DataPartEnd == p2Data.length - p2DataPartEnd; // #2
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	362 // #1(p2EntryStart + p2DataLen) - p1EntryAppliedStart
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	363 // #2 p2DataLen - (p1EntryAppliedStart - p2EntryStart)
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	364 // but this works only in assumption that p2EntryEnd-p2EntryStart == p2Data.length
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	365 //
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	366 // p1EntryAppliedStart <= p2EntryEnd < p1EntryAppliedStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	367 // -p1EntryAppliedStart (to compare against p1DataPartEnd) ==> 0 <= p1DataPartEnd < p1EntryLen
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	368 assert p1DataPartEnd < p1EntryLen;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	369 assert p1DataPartEnd >= 0;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	370 p1EntryLen -= p1DataPartEnd;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	371 p1Data = subarray(p1Data, p1DataPartEnd, p1Data.length);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	372
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	373 // p1TotalAppliedDelta XXX
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	374 p1TotalAppliedDelta += (p1EntryDelta - p1EntryLen);
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	375 continue L0; // next p2;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	376 } else {
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	377 // p2EntryEnd >= p1EntryAppliedEnd
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	378 // SKETCH IV: skip (rest of) p1 completely, continue the same unless found p1 with start or end past p2EntryEnd.
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	379 insideP1entry = false;
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	380 // p1 consumed
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	381 p1++;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	382 insideP2entry = true;
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	383 // extend to the left of p1 by p2 \ p1 front bytes
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	384 p2EntrySavedStart = p1EntryStart - p2DataPartEnd;
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	385 // fall-through to get p1TotalAppliedDelta incremented
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	386 }
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	387 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	388 }
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	389 p1TotalAppliedDelta += p1EntryDelta;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	390 } // while (p1 < p1Max)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	391 {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	392 // no more p1 entries, shall close p2 (if it's handled, code above jumps directly to L0)
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	393 // regardless of whether insideP2 is .t
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	394 int s = p2EntrySavedStart != -1 ? p2EntrySavedStart : p2EntryStart - p1TotalAppliedDelta;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	395 // p2EntrySavedStart != -1 when we started p2 entry processing, but not completed
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	396 // if we handled last p1 entry but didn't start with p2 entry processing, it's -1 and regular p1 delta shall be used
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	397 r.add(s, p2EntryEnd - p1TotalAppliedDelta, p2Data);
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	398 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	399 }
330 9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	400 if (p1 < p1Max && insideP1entry) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	401 r.add(p1EntryStart, p1EntryEnd, p1Data);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	402 p1++;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	403 }
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	404 while (p1 < p1Max) {
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	405 r.add(this, p1);
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	406 p1++;
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	407 };
9747a786a34d Patch merging algorithm complete trial Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 329 diff changeset	408 return r;
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	409 }
534 243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	410
583 47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	411 /**
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	412 * Combine consecutive regions into one.
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	413 * XXX NOW only combines two subsequent regions, seems enough for quick test
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	414 * @return <code>this</code> or new instance of consecutive regions found
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	415 */
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	416 public Patch normalize() {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	417 Patch rv = null;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	418 for (int i = 1, x = data.size(); i < x; i++) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	419 if (starts.get(i) == ends.get(i-1)) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	420 if (rv == null) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	421 rv = new Patch();
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	422 rv.copyOf(this, 0, i-1);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	423 // } else if (ends.get(i-1) == rv.ends.get(rv.ends.size()-1)) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	424 // // "JUST IN CASE" code, i++ below prevents us from getting here
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	425 // // if the last region is the one already merged,
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	426 // // ignore this occurrence (otherwise data(i-1) would get copied again)
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	427 // continue;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	428 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	429 byte[] d1 = data.get(i-1);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	430 byte[] d = data.get(i);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	431 byte[] nd;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	432 if (d1.length > 0 && d.length > 0) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	433 nd = new byte[d1.length + d.length];
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	434 System.arraycopy(d1, 0, nd, 0, d1.length);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	435 System.arraycopy(d, 0, nd, d1.length, d.length);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	436 } else {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	437 nd = d1.length == 0 ? d : d1 ;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	438 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	439 rv.add(starts.get(i-1), ends.get(i), nd);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	440 i++; // skip i-th element (effectively means we detect only pairs)
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	441 // without this ++, element(i-1) is added to rv once "else" below is hit on the next step
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	442 } else {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	443 if (rv != null) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	444 rv.add(this, i-1);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	445 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	446 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	447 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	448 if (rv == null) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	449 return this;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	450 } else {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	451 int last = count() - 1;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	452 if (starts.get(last) != ends.get(last-1)) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	453 rv.add(this, last);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	454 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	455 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	456 return rv;
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	457 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	458
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	459 private void copyOf(Patch another, int fromIndex, int upToIndex) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	460 while(fromIndex < upToIndex) {
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	461 add(another, fromIndex++);
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	462 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	463 }
47dfa0ec7e35 Effective revlog patching Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 534 diff changeset	464
534 243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	465 public class PatchDataSource implements DataSerializer.DataSource {
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	466
618 7c0d2ce340b8 Refactor approach how content finds it way down to a commit revision Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 587 diff changeset	467 public void serialize(DataSerializer out) throws HgIOException {
534 243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	468 Patch.this.serialize(out);
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	469 }
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	470
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	471 public int serializeLength() {
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	472 return Patch.this.serializedLength();
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	473 }
243202f1bda5 Commit: refactor revision creation code from clone command to work separately, fit into existing library structure Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 533 diff changeset	474 }
329 694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	475 }

Mercurial > hg4j

annotate src/org/tmatesoft/hg/internal/Patch.java @ 705:b4242b7e7dfe