Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/Patch.java @ 682:f568330dd9c0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Compile with Java5, ensure generics are fine for other compilers, too
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Mon, 22 Jul 2013 22:47:06 +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 }