Mercurial > hg4j

annotate src/org/tmatesoft/hg/internal/Patch.java @ 583:47dfa0ec7e35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Effective revlog patching
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 24 Apr 2013 15:39:53 +0200
parents 243202f1bda5
children ed243b668502
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
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 /**
419
7f136a3fa671 Clean javadoc to fix obvious warnings
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 330
diff changeset
24 * @see http://mercurial.selenic.com/wiki/BundleFormat
7f136a3fa671 Clean javadoc to fix obvious warnings
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 330
diff changeset
25 * in Changelog group description
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 *
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 532
diff changeset
27 * 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
28 * 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
29 *
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 * @author Artem Tikhomirov
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 * @author TMate Software Ltd.
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 */
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 public final class Patch {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 private final IntVector starts, ends;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 private final ArrayList<byte[]> data;
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
36
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
37 private static byte[] generate(int c) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
38 byte[] rv = new byte[c];
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
39 for (int i = 0; i < c; i++) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
40 byte x = (byte) ('a' + i);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
41 rv[i] = x;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
42 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
43 return rv;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
44 }
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 public static void main(String[] args) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
47 Patch p1 = new Patch(), p2 = new Patch();
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
48 // simple cases (one element in either patch)
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
49 // 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
50 // 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
51 // II: (1,1,10) & (3,11,15)
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
52 // 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
53 // 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
54 // IV: (15, 25, 10) & (10, 30, 20)
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
55 //
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
56 // cycle with insideP2
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
57 //
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
58 // cycle with insideP1
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
59 //
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
60 // multiple elements in patches (offsets)
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
61 p1.add(15, 25, generate(10));
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
62 p2.add(10, 30, generate(20));
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
63 System.out.println("p1: " + p1);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
64 System.out.println("p2: " + p2);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
65 Patch r = p1.apply(p2);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
66 System.out.println("r: " + r);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
67 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
68
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 public Patch() {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 starts = new IntVector();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 ends = new IntVector();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 data = new ArrayList<byte[]>();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
75 public String toString() {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
76 StringBuilder sb = new StringBuilder();
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
77 Formatter f = new Formatter(sb);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
78 for (int i = 0; i < count(); i++) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
79 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
80 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
81 return sb.toString();
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
82 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
83
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 public int count() {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 return data.size();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 // 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
89 public int patchSizeDelta() {
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 int rv = 0;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 int prevEnd = 0;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 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
93 final int start = starts.get(i);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 final int len = data.get(i).length;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 rv += start - prevEnd; // would copy from original
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 rv += len; // and add new
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 prevEnd = ends.get(i);
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 rv -= prevEnd;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 return rv;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 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
104 if (outcomeLen == -1) {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 outcomeLen = baseRevisionContent.length() + patchSizeDelta();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 int prevEnd = 0, destIndex = 0;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 byte[] rv = new byte[outcomeLen];
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 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
110 final int start = starts.get(i);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 baseRevisionContent.seek(prevEnd);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 // 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
113 baseRevisionContent.readBytes(rv, destIndex, start - prevEnd);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 destIndex += start - prevEnd;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 // 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
116 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
117 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
118 destIndex += d.length;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 prevEnd = ends.get(i);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
120 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121 baseRevisionContent.seek(prevEnd);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
122 // 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
123 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
124 return rv;
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 public void clear() {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 starts.clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 ends.clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 data.clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 }
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 /**
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 * 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
135 * 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
136 */
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137 public void read(DataAccess da) throws IOException {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
138 clear();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
139 while (!da.isEmpty()) {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
140 readOne(da);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
141 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
142 }
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 * 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
146 */
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
147 public void readOne(DataAccess da) throws IOException {
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
148 int s = da.readInt();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
149 int e = da.readInt();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
150 int len = da.readInt();
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
151 byte[] src = new byte[len];
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
152 da.readBytes(src, 0, len);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
153 starts.add(s);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
154 ends.add(e);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
155 data.add(src);
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
156 }
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
157
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
158 /**
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
159 * @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
160 */
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
161 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
162 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
163 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
164 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
165 }
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
166 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
167 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
168 }
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 /*package-local*/ void serialize(DataSerializer out) throws IOException {
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 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
172 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
173 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
174 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
175 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
176 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
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 }
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
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
180 private void add(Patch p, int i) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
181 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
182 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
183
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 532
diff changeset
184 /*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
185 // FIXME if start == end(-1), merge data
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
186 if (start == end && d.length == 0) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
187 System.currentTimeMillis();
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
188 return;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
189 }
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
190 starts.add(start);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
191 ends.add(end);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
192 data.add(d);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
193 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
194
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
195 // copies [start..end) bytes from the d
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
196 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
197 byte[] r = new byte[end-start];
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
198 System.arraycopy(d, start, r, 0, r.length);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
199 return r;
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
200 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
201
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
202 /**
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
203 * Modify this patch with subsequent patch
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
204 */
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
205 public /*SHALL BE PUBLIC ONCE TESTING ENDS*/ Patch apply(Patch another) {
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
206 Patch r = new Patch();
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
207 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
208 // 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
209 int p1EntryStart = 0, p1EntryEnd = 0, p1EntryLen = 0;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
210 byte[] p1Data = null;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
211 boolean insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
212 int p2 = 0, p1 = 0;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
213 final int p2Max = another.count(), p1Max = this.count();
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
214 L0: for (; p2 < p2Max; p2++) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
215 int p2EntryStart = another.starts.get(p2);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
216 int p2EntryEnd = another.ends.get(p2);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
217 final int p2EntryRange = p2EntryEnd - p2EntryStart;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
218 final byte[] p2Data = another.data.get(p2);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
219 boolean insideP2entry = false;
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
220 // 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
221 // shall ultimately start in terms of p1
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
222 int p2EntrySavedStart = -1;
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
223 ///
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
224
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
225 L1: while (p1 < p1Max) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
226 if (!insideP1entry) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
227 p1EntryStart = starts.get(p1);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
228 p1EntryEnd = ends.get(p1);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
229 p1Data = data.get(p1);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
230 p1EntryLen = p1Data.length;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
231 }// else keep values
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
232
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
233 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
234 final int p1EntryAppliedStart = p1TotalAppliedDelta + p1EntryStart;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
235 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
236
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
237 if (insideP2entry) {
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
238 if (p2EntryEnd <= p1EntryAppliedStart) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
239 r.add(p2EntrySavedStart, p2EntryEnd - p1TotalAppliedDelta, p2Data);
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
240 insideP2entry = false;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
241 continue L0;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
242 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
243 if (p2EntryEnd >= p1EntryAppliedEnd) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
244 // 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
245 // 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
246 insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
247 p1++;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
248 p1TotalAppliedDelta += p1EntryDelta;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
249 continue L1;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
250 }
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
251 // p1EntryAppliedStart < p2EntryEnd < p1EntryAppliedEnd
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
252 // 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
253 // to leave p1 intact here, to avoid delta/range recalculation
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
254 r.add(p2EntrySavedStart, p1EntryStart, p2Data);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
255 // consume part of p1 overlapped by current p2
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
256 final int p1DataPartShift = p2EntryEnd - p1EntryAppliedStart;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
257 // p2EntryEnd < p1EntryAppliedEnd ==> p2EntryEnd < p1EntryAppliedStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
258 // ==> p2EntryEnd - p1EntryAppliedStart < p1EntryLen
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
259 assert p1DataPartShift < p1EntryLen;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
260 p1EntryLen -= p1DataPartShift;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
261 p1Data = subarray(p1Data, p1DataPartShift, p1Data.length);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
262 p1TotalAppliedDelta += p1DataPartShift;
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
263 insideP1entry = true;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
264 insideP2entry = false;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
265 continue L0;
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
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
268 if (p1EntryAppliedStart < p2EntryStart) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
269 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
270 // completely independent, copy and continue
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
271 r.add(p1EntryStart, p1EntryEnd, p1Data);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
272 insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
273 p1++;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
274 // fall-through to get p1TotalAppliedDelta incremented
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
275 } 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
276 // remember, p1EntryDelta may be negative
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
277 // shall break j'th entry into few
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
278 // fix p1's end/length
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
279 // p1EntryAppliedStart < p2EntryStart < p1EntryAppliedEnd, or, alternatively
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
280 // p2EntryStart is from (p1EntryAppliedStart .. p1EntryAppliedStart + p1EntryLen)
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
281 int p1DataPartEnd = p2EntryStart - p1EntryAppliedStart;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
282 assert p1DataPartEnd < p1EntryLen;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
283 r.add(p1EntryStart, p1EntryEnd, subarray(p1Data, 0, p1DataPartEnd));
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
284 if (p2EntryEnd <= p1EntryAppliedEnd) { // p2 fits completely into p1
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
285 r.add(p1EntryEnd, p1EntryEnd, p2Data);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
286 // 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
287 insideP1entry = true;
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
288 p1EntryStart = p1EntryEnd;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
289 p1EntryLen -= p1DataPartEnd;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
290 p1EntryLen -= p2EntryRange;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
291 // p2EntryEnd <= p1EntryAppliedEnd ==> p2EntryEnd <= p1EntryAppliedStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
292 // -p2EntryStart ==> p2EntryRange <= p1EntryAppliedStart-p2EntryStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
293 // p1EntryAppliedStart-p2EntryStart = -p1DataPartEnd ==> p2EntryRange <= p1EntryLen - p1DataEndPart
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
294 // +p1DataEndPart ==> p2EntryRange + p1DataEndPart <= p1EntryLen
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
295 assert p1EntryLen >= 0;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
296 // 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
297 // however changing <= to < in p2EntryEnd <= p1EntryAppliedEnd above leads to errors
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
298 p1Data = subarray(p1Data, p1DataPartEnd+p2EntryRange, p1Data.length);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
299 // 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
300 p1TotalAppliedDelta += (p1EntryDelta - p1EntryLen);
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
301 continue L0;
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
302 } else {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
303 // p1 is consumed, take next
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
304 insideP1entry = false;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
305 p1++;
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
306 insideP2entry = true;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
307 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
308 // 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
309 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
310 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
311 } else { // p1EntryAppliedStart >= p2EntryStart
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
312 if (p2EntryEnd < p1EntryAppliedStart) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
313 // newer patch completely fits between two older patches
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
314 r.add(p2EntryStart - p1TotalAppliedDelta, p2EntryEnd - p1TotalAppliedDelta, p2Data);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
315 // 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
316 continue L0; // next p2
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
317 } else { // p2EntryEnd >= p1EntryAppliedStart
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
318 // SKETCH: I or IV:
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
319 // p2 start is outside of p1 range.
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
320 //
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
321 // 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
322 int p2DataPartEnd = p1EntryAppliedStart - p2EntryStart;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
323 if (p2EntryEnd < p1EntryAppliedEnd) {
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
324 // 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
325 insideP1entry = true;
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
326 // 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
327 r.add(p1EntryStart - p2DataPartEnd, p1EntryEnd, p2Data);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
328 p1EntryStart = p1EntryEnd;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
329 // see how much of p1 is left for insertion
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
330 int p1DataPartEnd = p2EntryEnd - p1EntryAppliedStart; // #1
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
331 // Similar, although incorrect: p1DataPartEnd == p2Data.length - p2DataPartEnd; // #2
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
332 // #1(p2EntryStart + p2DataLen) - p1EntryAppliedStart
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
333 // #2 p2DataLen - (p1EntryAppliedStart - p2EntryStart)
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
334 // 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
335 //
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
336 // p1EntryAppliedStart <= p2EntryEnd < p1EntryAppliedStart + p1EntryLen
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
337 // -p1EntryAppliedStart (to compare against p1DataPartEnd) ==> 0 <= p1DataPartEnd < p1EntryLen
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
338 assert p1DataPartEnd < p1EntryLen;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
339 assert p1DataPartEnd >= 0;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
340 p1EntryLen -= p1DataPartEnd;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
341 p1Data = subarray(p1Data, p1DataPartEnd, p1Data.length);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
342
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
343 // p1TotalAppliedDelta XXX
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
344 p1TotalAppliedDelta += (p1EntryDelta - p1EntryLen);
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
345 continue L0; // next p2;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
346 } else {
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
347 // p2EntryEnd >= p1EntryAppliedEnd
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
348 // 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
349 insideP1entry = false;
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
350 // p1 consumed
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
351 p1++;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
352 insideP2entry = true;
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
353 // 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
354 p2EntrySavedStart = p1EntryStart - p2DataPartEnd;
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
355 // fall-through to get p1TotalAppliedDelta incremented
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
356 }
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
357 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
358 }
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
359 p1TotalAppliedDelta += p1EntryDelta;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
360 } // while (p1 < p1Max)
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
361 {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
362 // 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
363 // regardless of whether insideP2 is .t
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
364 int s = p2EntrySavedStart != -1 ? p2EntrySavedStart : p2EntryStart - p1TotalAppliedDelta;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
365 // 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
366 // 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
367 r.add(s, p2EntryEnd - p1TotalAppliedDelta, p2Data);
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
368 }
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
369 }
330
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
370 if (p1 < p1Max && insideP1entry) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
371 r.add(p1EntryStart, p1EntryEnd, p1Data);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
372 p1++;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
373 }
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
374 while (p1 < p1Max) {
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
375 r.add(this, p1);
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
376 p1++;
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
377 };
9747a786a34d Patch merging algorithm complete trial
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 329
diff changeset
378 return r;
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
379 }
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
380
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
381 /**
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
382 * Combine consecutive regions into one.
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
383 * 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
384 * @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
385 */
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
386 public Patch normalize() {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
387 Patch rv = null;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
388 for (int i = 1, x = data.size(); i < x; i++) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
389 if (starts.get(i) == ends.get(i-1)) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
390 if (rv == null) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
391 rv = new Patch();
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
392 rv.copyOf(this, 0, i-1);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
393 // } 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
394 // // "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
395 // // if the last region is the one already merged,
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
396 // // 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
397 // continue;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
398 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
399 byte[] d1 = data.get(i-1);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
400 byte[] d = data.get(i);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
401 byte[] nd;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
402 if (d1.length > 0 && d.length > 0) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
403 nd = new byte[d1.length + d.length];
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
404 System.arraycopy(d1, 0, nd, 0, d1.length);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
405 System.arraycopy(d, 0, nd, d1.length, d.length);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
406 } else {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
407 nd = d1.length == 0 ? d : d1 ;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
408 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
409 rv.add(starts.get(i-1), ends.get(i), nd);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
410 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
411 // 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
412 } else {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
413 if (rv != null) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
414 rv.add(this, i-1);
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 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
417 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
418 if (rv == null) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
419 return this;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
420 } else {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
421 int last = count() - 1;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
422 if (starts.get(last) != ends.get(last-1)) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
423 rv.add(this, last);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
424 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
425 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
426 return rv;
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
427 }
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 private void copyOf(Patch another, int fromIndex, int upToIndex) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
430 while(fromIndex < upToIndex) {
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
431 add(another, fromIndex++);
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
432 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
433 }
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 534
diff changeset
434
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
435 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
436
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
437 public void serialize(DataSerializer out) throws IOException {
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
438 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
439 }
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
440
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
441 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
442 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
443 }
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
444 }
329
694ebabb5cb3 Refactor revlog patch mechanism, towards patch merging
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
445 }