Mercurial > jhg

comparison src/org/tmatesoft/hg/internal/RevlogStream.java @ 77:c677e1593919

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved RevlogStream implementation into .internal
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Mon, 24 Jan 2011 05:33:47 +0100
parents src/org/tmatesoft/hg/repo/RevlogStream.java@6f1b88693d48
children 4222b04f34ee
comparison
equal deleted inserted replaced
76:658fa6b3a371 77:c677e1593919
1 /*
2 * Copyright (c) 2010-2011 TMate Software Ltd
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 2 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * For information on how to redistribute this software under
14 * the terms of a license other than GNU General Public License
15 * contact TMate Software at support@svnkit.com
16 */
17 package org.tmatesoft.hg.internal;
18
19 import static org.tmatesoft.hg.repo.HgRepository.TIP;
20
21 import java.io.File;
22 import java.io.IOException;
23 import java.util.ArrayList;
24 import java.util.Collections;
25 import java.util.LinkedList;
26 import java.util.List;
27 import java.util.zip.DataFormatException;
28 import java.util.zip.Inflater;
29
30 import org.tmatesoft.hg.core.Nodeid;
31
32
33 /**
34 * ? Single RevlogStream per file per repository with accessor to record access session (e.g. with back/forward operations),
35 * or numerous RevlogStream with separate representation of the underlaying data (cached, lazy ChunkStream)?
36 *
37 * @see http://mercurial.selenic.com/wiki/Revlog
38 * @see http://mercurial.selenic.com/wiki/RevlogNG
39 *
40 * @author Artem Tikhomirov
41 * @author TMate Software Ltd.
42 */
43 public class RevlogStream {
44
45 private List<IndexEntry> index; // indexed access highly needed
46 private boolean inline = false;
47 private final File indexFile;
48 private final DataAccessProvider dataAccess;
49
50 // if we need anything else from HgRepo, might replace DAP parameter with HgRepo and query it for DAP.
51 public RevlogStream(DataAccessProvider dap, File indexFile) {
52 this.dataAccess = dap;
53 this.indexFile = indexFile;
54 }
55
56 /*package*/ DataAccess getIndexStream() {
57 return dataAccess.create(indexFile);
58 }
59
60 /*package*/ DataAccess getDataStream() {
61 final String indexName = indexFile.getName();
62 File dataFile = new File(indexFile.getParentFile(), indexName.substring(0, indexName.length() - 1) + "d");
63 return dataAccess.create(dataFile);
64 }
65
66 public int revisionCount() {
67 initOutline();
68 return index.size();
69 }
70
71 public int dataLength(int revision) {
72 // XXX in fact, use of iterate() instead of this implementation may be quite reasonable.
73 //
74 final int indexSize = revisionCount();
75 DataAccess daIndex = getIndexStream(); // XXX may supply a hint that I'll need really few bytes of data (although at some offset)
76 if (revision == TIP) {
77 revision = indexSize - 1;
78 }
79 try {
80 int recordOffset = inline ? (int) index.get(revision).offset : revision * REVLOGV1_RECORD_SIZE;
81 daIndex.seek(recordOffset + 12); // 6+2+4
82 int actualLen = daIndex.readInt();
83 return actualLen;
84 } catch (IOException ex) {
85 ex.printStackTrace(); // log error. FIXME better handling
86 throw new IllegalStateException(ex);
87 } finally {
88 daIndex.done();
89 }
90 }
91
92 // Perhaps, RevlogStream should be limited to use of plain int revisions for access,
93 // while Nodeids should be kept on the level up, in Revlog. Guess, Revlog better keep
94 // map of nodeids, and once this comes true, we may get rid of this method.
95 // Unlike its counterpart, Revlog#getLocalRevisionNumber, doesn't fail with exception if node not found,
96 // returns a predefined constant instead
97 public int findLocalRevisionNumber(Nodeid nodeid) {
98 // XXX this one may be implemented with iterate() once there's mechanism to stop iterations
99 final int indexSize = revisionCount();
100 DataAccess daIndex = getIndexStream();
101 try {
102 byte[] nodeidBuf = new byte[20];
103 for (int i = 0; i < indexSize; i++) {
104 daIndex.skip(8);
105 int compressedLen = daIndex.readInt();
106 daIndex.skip(20);
107 daIndex.readBytes(nodeidBuf, 0, 20);
108 if (nodeid.equalsTo(nodeidBuf)) {
109 return i;
110 }
111 daIndex.skip(inline ? 12 + compressedLen : 12);
112 }
113 } catch (IOException ex) {
114 ex.printStackTrace(); // log error. FIXME better handling
115 throw new IllegalStateException(ex);
116 } finally {
117 daIndex.done();
118 }
119 return Integer.MIN_VALUE;
120 }
121
122
123 private final int REVLOGV1_RECORD_SIZE = 64;
124
125 // should be possible to use TIP, ALL, or -1, -2, -n notation of Hg
126 // ? boolean needsNodeid
127 public void iterate(int start, int end, boolean needData, Inspector inspector) {
128 initOutline();
129 final int indexSize = index.size();
130 if (indexSize == 0) {
131 return;
132 }
133 if (end == TIP) {
134 end = indexSize - 1;
135 }
136 if (start == TIP) {
137 start = indexSize - 1;
138 }
139 if (start < 0 || start >= indexSize) {
140 throw new IllegalArgumentException("Bad left range boundary " + start);
141 }
142 if (end < start || end >= indexSize) {
143 throw new IllegalArgumentException("Bad right range boundary " + end);
144 }
145 // XXX may cache [start .. end] from index with a single read (pre-read)
146
147 DataAccess daIndex = null, daData = null;
148 daIndex = getIndexStream();
149 if (needData && !inline) {
150 daData = getDataStream();
151 }
152 try {
153 byte[] nodeidBuf = new byte[20];
154 byte[] lastData = null;
155 int i;
156 boolean extraReadsToBaseRev = false;
157 if (needData && index.get(start).baseRevision < start) {
158 i = index.get(start).baseRevision;
159 extraReadsToBaseRev = true;
160 } else {
161 i = start;
162 }
163
164 daIndex.seek(inline ? (int) index.get(i).offset : i * REVLOGV1_RECORD_SIZE);
165 for (; i <= end; i++ ) {
166 long l = daIndex.readLong();
167 @SuppressWarnings("unused")
168 long offset = l >>> 16;
169 @SuppressWarnings("unused")
170 int flags = (int) (l & 0X0FFFF);
171 int compressedLen = daIndex.readInt();
172 int actualLen = daIndex.readInt();
173 int baseRevision = daIndex.readInt();
174 int linkRevision = daIndex.readInt();
175 int parent1Revision = daIndex.readInt();
176 int parent2Revision = daIndex.readInt();
177 // Hg has 32 bytes here, uses 20 for nodeid, and keeps 12 last bytes empty
178 daIndex.readBytes(nodeidBuf, 0, 20);
179 daIndex.skip(12);
180 byte[] data = null;
181 if (needData) {
182 byte[] dataBuf = new byte[compressedLen];
183 if (inline) {
184 daIndex.readBytes(dataBuf, 0, compressedLen);
185 } else {
186 daData.seek(index.get(i).offset);
187 daData.readBytes(dataBuf, 0, compressedLen);
188 }
189 if (dataBuf[0] == 0x78 /* 'x' */) {
190 try {
191 Inflater zlib = new Inflater(); // XXX Consider reuse of Inflater, and/or stream alternative
192 zlib.setInput(dataBuf, 0, compressedLen);
193 byte[] result = new byte[actualLen*2]; // FIXME need to use zlib.finished() instead
194 int resultLen = zlib.inflate(result);
195 zlib.end();
196 data = new byte[resultLen];
197 System.arraycopy(result, 0, data, 0, resultLen);
198 } catch (DataFormatException ex) {
199 ex.printStackTrace();
200 data = new byte[0]; // FIXME need better failure strategy
201 }
202 } else if (dataBuf[0] == 0x75 /* 'u' */) {
203 data = new byte[dataBuf.length - 1];
204 System.arraycopy(dataBuf, 1, data, 0, data.length);
205 } else {
206 // XXX Python impl in fact throws exception when there's not 'x', 'u' or '0'
207 // but I don't see reason not to return data as is
208 data = dataBuf;
209 }
210 // XXX
211 if (baseRevision != i) { // XXX not sure if this is the right way to detect a patch
212 // this is a patch
213 LinkedList<PatchRecord> patches = new LinkedList<PatchRecord>();
214 int patchElementIndex = 0;
215 do {
216 PatchRecord pr = PatchRecord.read(data, patchElementIndex);
217 patches.add(pr);
218 patchElementIndex += 12 + pr.len;
219 } while (patchElementIndex < data.length);
220 //
221 byte[] baseRevContent = lastData;
222 data = apply(baseRevContent, actualLen, patches);
223 }
224 } else {
225 if (inline) {
226 daIndex.skip(compressedLen);
227 }
228 }
229 if (!extraReadsToBaseRev || i >= start) {
230 inspector.next(i, actualLen, baseRevision, linkRevision, parent1Revision, parent2Revision, nodeidBuf, data);
231 }
232 lastData = data;
233 }
234 } catch (IOException ex) {
235 throw new IllegalStateException(ex); // FIXME need better handling
236 } finally {
237 daIndex.done();
238 if (daData != null) {
239 daData.done();
240 }
241 }
242 }
243
244 private void initOutline() {
245 if (index != null && !index.isEmpty()) {
246 return;
247 }
248 ArrayList<IndexEntry> res = new ArrayList<IndexEntry>();
249 DataAccess da = getIndexStream();
250 try {
251 int versionField = da.readInt();
252 da.readInt(); // just to skip next 2 bytes of offset + flags
253 final int INLINEDATA = 1 << 16;
254 inline = (versionField & INLINEDATA) != 0;
255 long offset = 0; // first offset is always 0, thus Hg uses it for other purposes
256 while(true) {
257 int compressedLen = da.readInt();
258 // 8+4 = 12 bytes total read here
259 @SuppressWarnings("unused")
260 int actualLen = da.readInt();
261 int baseRevision = da.readInt();
262 // 12 + 8 = 20 bytes read here
263 // int linkRevision = di.readInt();
264 // int parent1Revision = di.readInt();
265 // int parent2Revision = di.readInt();
266 // byte[] nodeid = new byte[32];
267 if (inline) {
268 res.add(new IndexEntry(offset + REVLOGV1_RECORD_SIZE * res.size(), baseRevision));
269 da.skip(3*4 + 32 + compressedLen); // Check: 44 (skip) + 20 (read) = 64 (total RevlogNG record size)
270 } else {
271 res.add(new IndexEntry(offset, baseRevision));
272 da.skip(3*4 + 32);
273 }
274 if (da.isEmpty()) {
275 // fine, done then
276 res.trimToSize();
277 index = res;
278 break;
279 } else {
280 // start reading next record
281 long l = da.readLong();
282 offset = l >>> 16;
283 }
284 }
285 } catch (IOException ex) {
286 ex.printStackTrace(); // log error
287 // too bad, no outline then.
288 index = Collections.emptyList();
289 } finally {
290 da.done();
291 }
292
293 }
294
295
296 // perhaps, package-local or protected, if anyone else from low-level needs them
297 // XXX think over if we should keep offset in case of separate data file - we read the field anyway. Perhaps, distinct entry classes for Inline and non-inline indexes?
298 private static class IndexEntry {
299 public final long offset; // for separate .i and .d - copy of index record entry, for inline index - actual offset of the record in the .i file (record entry + revision * record size))
300 //public final int length; // data past fixed record (need to decide whether including header size or not), and whether length is of compressed data or not
301 public final int baseRevision;
302
303 public IndexEntry(long o, int baseRev) {
304 offset = o;
305 baseRevision = baseRev;
306 }
307 }
308
309 // mpatch.c : apply()
310 // FIXME need to implement patch merge (fold, combine, gather and discard from aforementioned mpatch.[c|py]), also see Revlog and Mercurial PDF
311 public/*for HgBundle; until moved to better place*/static byte[] apply(byte[] baseRevisionContent, int outcomeLen, List<PatchRecord> patch) {
312 int last = 0, destIndex = 0;
313 if (outcomeLen == -1) {
314 outcomeLen = baseRevisionContent.length;
315 for (PatchRecord pr : patch) {
316 outcomeLen += pr.start - last + pr.len;
317 last = pr.end;
318 }
319 outcomeLen -= last;
320 last = 0;
321 }
322 byte[] rv = new byte[outcomeLen];
323 for (PatchRecord pr : patch) {
324 System.arraycopy(baseRevisionContent, last, rv, destIndex, pr.start-last);
325 destIndex += pr.start - last;
326 System.arraycopy(pr.data, 0, rv, destIndex, pr.data.length);
327 destIndex += pr.data.length;
328 last = pr.end;
329 }
330 System.arraycopy(baseRevisionContent, last, rv, destIndex, baseRevisionContent.length - last);
331 return rv;
332 }
333
334 // @see http://mercurial.selenic.com/wiki/BundleFormat, in Changelog group description
335 public static class PatchRecord {
336 /*
337 Given there are pr1 and pr2:
338 pr1.start to pr1.end will be replaced with pr's data (of pr1.len)
339 pr1.end to pr2.start gets copied from base
340 */
341 public int start, end, len;
342 public byte[] data;
343
344 // TODO consider PatchRecord that only records data position (absolute in data source), and acquires data as needed
345 private PatchRecord(int p1, int p2, int length, byte[] src) {
346 start = p1;
347 end = p2;
348 len = length;
349 data = src;
350 }
351
352 /*package-local*/ static PatchRecord read(byte[] data, int offset) {
353 final int x = offset; // shorthand
354 int p1 = ((data[x] & 0xFF)<< 24) | ((data[x+1] & 0xFF) << 16) | ((data[x+2] & 0xFF) << 8) | (data[x+3] & 0xFF);
355 int p2 = ((data[x+4] & 0xFF) << 24) | ((data[x+5] & 0xFF) << 16) | ((data[x+6] & 0xFF) << 8) | (data[x+7] & 0xFF);
356 int len = ((data[x+8] & 0xFF) << 24) | ((data[x+9] & 0xFF) << 16) | ((data[x+10] & 0xFF) << 8) | (data[x+11] & 0xFF);
357 byte[] dataCopy = new byte[len];
358 System.arraycopy(data, x+12, dataCopy, 0, len);
359 return new PatchRecord(p1, p2, len, dataCopy);
360 }
361
362 public /*for HgBundle*/ static PatchRecord read(DataAccess da) throws IOException {
363 int p1 = da.readInt();
364 int p2 = da.readInt();
365 int len = da.readInt();
366 byte[] src = new byte[len];
367 da.readBytes(src, 0, len);
368 return new PatchRecord(p1, p2, len, src);
369 }
370 }
371
372 // FIXME byte[] data might be too expensive, for few usecases it may be better to have intermediate Access object (when we don't need full data
373 // instantly - e.g. calculate hash, or comparing two revisions
374 public interface Inspector {
375 // XXX boolean retVal to indicate whether to continue?
376 // TODO specify nodeid and data length, and reuse policy (i.e. if revlog stream doesn't reuse nodeid[] for each call)
377 void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[/*20*/] nodeid, byte[] data);
378 }
379 }