tikhomirov@10: /* tikhomirov@74: * Copyright (c) 2010-2011 TMate Software Ltd tikhomirov@74: * tikhomirov@74: * This program is free software; you can redistribute it and/or modify tikhomirov@74: * it under the terms of the GNU General Public License as published by tikhomirov@74: * the Free Software Foundation; version 2 of the License. tikhomirov@74: * tikhomirov@74: * This program is distributed in the hope that it will be useful, tikhomirov@74: * but WITHOUT ANY WARRANTY; without even the implied warranty of tikhomirov@74: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the tikhomirov@74: * GNU General Public License for more details. tikhomirov@74: * tikhomirov@74: * For information on how to redistribute this software under tikhomirov@74: * the terms of a license other than GNU General Public License tikhomirov@74: * contact TMate Software at support@svnkit.com tikhomirov@0: */ tikhomirov@77: package org.tmatesoft.hg.internal; tikhomirov@0: tikhomirov@80: import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION; tikhomirov@74: import static org.tmatesoft.hg.repo.HgRepository.TIP; tikhomirov@5: tikhomirov@3: import java.io.File; tikhomirov@2: import java.io.IOException; tikhomirov@2: import java.util.ArrayList; tikhomirov@2: import java.util.Collections; tikhomirov@3: import java.util.LinkedList; tikhomirov@2: import java.util.List; tikhomirov@3: import java.util.zip.DataFormatException; tikhomirov@2: import java.util.zip.Inflater; tikhomirov@0: tikhomirov@74: import org.tmatesoft.hg.core.Nodeid; tikhomirov@80: import org.tmatesoft.hg.repo.HgRepository; tikhomirov@74: tikhomirov@10: tikhomirov@0: /** tikhomirov@0: * ? Single RevlogStream per file per repository with accessor to record access session (e.g. with back/forward operations), tikhomirov@0: * or numerous RevlogStream with separate representation of the underlaying data (cached, lazy ChunkStream)? tikhomirov@74: * tikhomirov@0: * @see http://mercurial.selenic.com/wiki/Revlog tikhomirov@0: * @see http://mercurial.selenic.com/wiki/RevlogNG tikhomirov@74: * tikhomirov@74: * @author Artem Tikhomirov tikhomirov@74: * @author TMate Software Ltd. tikhomirov@0: */ tikhomirov@0: public class RevlogStream { tikhomirov@2: tikhomirov@2: private List index; // indexed access highly needed tikhomirov@2: private boolean inline = false; tikhomirov@3: private final File indexFile; tikhomirov@10: private final DataAccessProvider dataAccess; tikhomirov@3: tikhomirov@10: // if we need anything else from HgRepo, might replace DAP parameter with HgRepo and query it for DAP. tikhomirov@77: public RevlogStream(DataAccessProvider dap, File indexFile) { tikhomirov@10: this.dataAccess = dap; tikhomirov@3: this.indexFile = indexFile; tikhomirov@3: } tikhomirov@2: tikhomirov@9: /*package*/ DataAccess getIndexStream() { tikhomirov@10: return dataAccess.create(indexFile); tikhomirov@0: } tikhomirov@0: tikhomirov@9: /*package*/ DataAccess getDataStream() { tikhomirov@3: final String indexName = indexFile.getName(); tikhomirov@3: File dataFile = new File(indexFile.getParentFile(), indexName.substring(0, indexName.length() - 1) + "d"); tikhomirov@10: return dataAccess.create(dataFile); tikhomirov@9: } tikhomirov@9: tikhomirov@2: public int revisionCount() { tikhomirov@2: initOutline(); tikhomirov@2: return index.size(); tikhomirov@2: } tikhomirov@22: tikhomirov@22: public int dataLength(int revision) { tikhomirov@22: // XXX in fact, use of iterate() instead of this implementation may be quite reasonable. tikhomirov@22: // tikhomirov@22: final int indexSize = revisionCount(); tikhomirov@22: DataAccess daIndex = getIndexStream(); // XXX may supply a hint that I'll need really few bytes of data (although at some offset) tikhomirov@22: if (revision == TIP) { tikhomirov@22: revision = indexSize - 1; tikhomirov@22: } tikhomirov@22: try { tikhomirov@22: int recordOffset = inline ? (int) index.get(revision).offset : revision * REVLOGV1_RECORD_SIZE; tikhomirov@22: daIndex.seek(recordOffset + 12); // 6+2+4 tikhomirov@22: int actualLen = daIndex.readInt(); tikhomirov@22: return actualLen; tikhomirov@22: } catch (IOException ex) { tikhomirov@22: ex.printStackTrace(); // log error. FIXME better handling tikhomirov@22: throw new IllegalStateException(ex); tikhomirov@22: } finally { tikhomirov@22: daIndex.done(); tikhomirov@22: } tikhomirov@22: } tikhomirov@22: tikhomirov@80: public byte[] nodeid(int revision) { tikhomirov@80: final int indexSize = revisionCount(); tikhomirov@80: if (revision == TIP) { tikhomirov@80: revision = indexSize - 1; tikhomirov@80: } tikhomirov@80: if (revision < 0 || revision >= indexSize) { tikhomirov@80: throw new IllegalArgumentException(Integer.toString(revision)); tikhomirov@80: } tikhomirov@80: DataAccess daIndex = getIndexStream(); tikhomirov@80: try { tikhomirov@80: int recordOffset = inline ? (int) index.get(revision).offset : revision * REVLOGV1_RECORD_SIZE; tikhomirov@80: daIndex.seek(recordOffset + 32); tikhomirov@80: byte[] rv = new byte[20]; tikhomirov@80: daIndex.readBytes(rv, 0, 20); tikhomirov@80: return rv; tikhomirov@80: } catch (IOException ex) { tikhomirov@80: ex.printStackTrace(); tikhomirov@80: throw new IllegalStateException(); tikhomirov@80: } finally { tikhomirov@80: } tikhomirov@80: } tikhomirov@80: tikhomirov@49: // Perhaps, RevlogStream should be limited to use of plain int revisions for access, tikhomirov@49: // while Nodeids should be kept on the level up, in Revlog. Guess, Revlog better keep tikhomirov@49: // map of nodeids, and once this comes true, we may get rid of this method. tikhomirov@80: // Unlike its counterpart, {@link Revlog#getLocalRevisionNumber()}, doesn't fail with exception if node not found, tikhomirov@80: /** tikhomirov@80: * @return integer in [0..revisionCount()) or {@link HgRepository#BAD_REVISION} if not found tikhomirov@80: */ tikhomirov@77: public int findLocalRevisionNumber(Nodeid nodeid) { tikhomirov@22: // XXX this one may be implemented with iterate() once there's mechanism to stop iterations tikhomirov@22: final int indexSize = revisionCount(); tikhomirov@22: DataAccess daIndex = getIndexStream(); tikhomirov@22: try { tikhomirov@24: byte[] nodeidBuf = new byte[20]; tikhomirov@22: for (int i = 0; i < indexSize; i++) { tikhomirov@22: daIndex.skip(8); tikhomirov@22: int compressedLen = daIndex.readInt(); tikhomirov@22: daIndex.skip(20); tikhomirov@24: daIndex.readBytes(nodeidBuf, 0, 20); tikhomirov@24: if (nodeid.equalsTo(nodeidBuf)) { tikhomirov@22: return i; tikhomirov@22: } tikhomirov@22: daIndex.skip(inline ? 12 + compressedLen : 12); tikhomirov@22: } tikhomirov@22: } catch (IOException ex) { tikhomirov@22: ex.printStackTrace(); // log error. FIXME better handling tikhomirov@22: throw new IllegalStateException(ex); tikhomirov@22: } finally { tikhomirov@22: daIndex.done(); tikhomirov@22: } tikhomirov@80: return BAD_REVISION; tikhomirov@22: } tikhomirov@22: tikhomirov@2: tikhomirov@9: private final int REVLOGV1_RECORD_SIZE = 64; tikhomirov@9: tikhomirov@3: // should be possible to use TIP, ALL, or -1, -2, -n notation of Hg tikhomirov@3: // ? boolean needsNodeid tikhomirov@77: public void iterate(int start, int end, boolean needData, Inspector inspector) { tikhomirov@2: initOutline(); tikhomirov@2: final int indexSize = index.size(); tikhomirov@3: if (indexSize == 0) { tikhomirov@3: return; tikhomirov@3: } tikhomirov@5: if (end == TIP) { tikhomirov@3: end = indexSize - 1; tikhomirov@3: } tikhomirov@5: if (start == TIP) { tikhomirov@5: start = indexSize - 1; tikhomirov@5: } tikhomirov@2: if (start < 0 || start >= indexSize) { tikhomirov@2: throw new IllegalArgumentException("Bad left range boundary " + start); tikhomirov@2: } tikhomirov@2: if (end < start || end >= indexSize) { tikhomirov@2: throw new IllegalArgumentException("Bad right range boundary " + end); tikhomirov@2: } tikhomirov@2: // XXX may cache [start .. end] from index with a single read (pre-read) tikhomirov@2: tikhomirov@9: DataAccess daIndex = null, daData = null; tikhomirov@9: daIndex = getIndexStream(); tikhomirov@3: if (needData && !inline) { tikhomirov@9: daData = getDataStream(); tikhomirov@2: } tikhomirov@2: try { tikhomirov@24: byte[] nodeidBuf = new byte[20]; tikhomirov@3: byte[] lastData = null; tikhomirov@5: int i; tikhomirov@5: boolean extraReadsToBaseRev = false; tikhomirov@5: if (needData && index.get(start).baseRevision < start) { tikhomirov@5: i = index.get(start).baseRevision; tikhomirov@5: extraReadsToBaseRev = true; tikhomirov@5: } else { tikhomirov@5: i = start; tikhomirov@5: } tikhomirov@9: tikhomirov@22: daIndex.seek(inline ? (int) index.get(i).offset : i * REVLOGV1_RECORD_SIZE); tikhomirov@5: for (; i <= end; i++ ) { tikhomirov@9: long l = daIndex.readLong(); tikhomirov@49: @SuppressWarnings("unused") tikhomirov@2: long offset = l >>> 16; tikhomirov@49: @SuppressWarnings("unused") tikhomirov@2: int flags = (int) (l & 0X0FFFF); tikhomirov@9: int compressedLen = daIndex.readInt(); tikhomirov@9: int actualLen = daIndex.readInt(); tikhomirov@9: int baseRevision = daIndex.readInt(); tikhomirov@9: int linkRevision = daIndex.readInt(); tikhomirov@9: int parent1Revision = daIndex.readInt(); tikhomirov@9: int parent2Revision = daIndex.readInt(); tikhomirov@24: // Hg has 32 bytes here, uses 20 for nodeid, and keeps 12 last bytes empty tikhomirov@24: daIndex.readBytes(nodeidBuf, 0, 20); tikhomirov@9: daIndex.skip(12); tikhomirov@2: byte[] data = null; tikhomirov@2: if (needData) { tikhomirov@2: byte[] dataBuf = new byte[compressedLen]; tikhomirov@2: if (inline) { tikhomirov@9: daIndex.readBytes(dataBuf, 0, compressedLen); tikhomirov@2: } else { tikhomirov@9: daData.seek(index.get(i).offset); tikhomirov@9: daData.readBytes(dataBuf, 0, compressedLen); tikhomirov@2: } tikhomirov@2: if (dataBuf[0] == 0x78 /* 'x' */) { tikhomirov@3: try { tikhomirov@33: Inflater zlib = new Inflater(); // XXX Consider reuse of Inflater, and/or stream alternative tikhomirov@3: zlib.setInput(dataBuf, 0, compressedLen); tikhomirov@3: byte[] result = new byte[actualLen*2]; // FIXME need to use zlib.finished() instead tikhomirov@3: int resultLen = zlib.inflate(result); tikhomirov@3: zlib.end(); tikhomirov@3: data = new byte[resultLen]; tikhomirov@3: System.arraycopy(result, 0, data, 0, resultLen); tikhomirov@3: } catch (DataFormatException ex) { tikhomirov@3: ex.printStackTrace(); tikhomirov@3: data = new byte[0]; // FIXME need better failure strategy tikhomirov@3: } tikhomirov@2: } else if (dataBuf[0] == 0x75 /* 'u' */) { tikhomirov@2: data = new byte[dataBuf.length - 1]; tikhomirov@2: System.arraycopy(dataBuf, 1, data, 0, data.length); tikhomirov@2: } else { tikhomirov@2: // XXX Python impl in fact throws exception when there's not 'x', 'u' or '0' tikhomirov@3: // but I don't see reason not to return data as is tikhomirov@2: data = dataBuf; tikhomirov@2: } tikhomirov@3: // XXX tikhomirov@3: if (baseRevision != i) { // XXX not sure if this is the right way to detect a patch tikhomirov@3: // this is a patch tikhomirov@3: LinkedList patches = new LinkedList(); tikhomirov@3: int patchElementIndex = 0; tikhomirov@3: do { tikhomirov@36: PatchRecord pr = PatchRecord.read(data, patchElementIndex); tikhomirov@36: patches.add(pr); tikhomirov@36: patchElementIndex += 12 + pr.len; tikhomirov@3: } while (patchElementIndex < data.length); tikhomirov@3: // tikhomirov@5: byte[] baseRevContent = lastData; tikhomirov@6: data = apply(baseRevContent, actualLen, patches); tikhomirov@3: } tikhomirov@3: } else { tikhomirov@3: if (inline) { tikhomirov@9: daIndex.skip(compressedLen); tikhomirov@3: } tikhomirov@2: } tikhomirov@5: if (!extraReadsToBaseRev || i >= start) { tikhomirov@24: inspector.next(i, actualLen, baseRevision, linkRevision, parent1Revision, parent2Revision, nodeidBuf, data); tikhomirov@5: } tikhomirov@3: lastData = data; tikhomirov@2: } tikhomirov@2: } catch (IOException ex) { tikhomirov@3: throw new IllegalStateException(ex); // FIXME need better handling tikhomirov@3: } finally { tikhomirov@9: daIndex.done(); tikhomirov@9: if (daData != null) { tikhomirov@9: daData.done(); tikhomirov@9: } tikhomirov@2: } tikhomirov@2: } tikhomirov@0: tikhomirov@2: private void initOutline() { tikhomirov@2: if (index != null && !index.isEmpty()) { tikhomirov@2: return; tikhomirov@2: } tikhomirov@2: ArrayList res = new ArrayList(); tikhomirov@9: DataAccess da = getIndexStream(); tikhomirov@2: try { tikhomirov@9: int versionField = da.readInt(); tikhomirov@9: da.readInt(); // just to skip next 2 bytes of offset + flags tikhomirov@2: final int INLINEDATA = 1 << 16; tikhomirov@2: inline = (versionField & INLINEDATA) != 0; tikhomirov@2: long offset = 0; // first offset is always 0, thus Hg uses it for other purposes tikhomirov@9: while(true) { tikhomirov@9: int compressedLen = da.readInt(); tikhomirov@5: // 8+4 = 12 bytes total read here tikhomirov@49: @SuppressWarnings("unused") tikhomirov@9: int actualLen = da.readInt(); tikhomirov@9: int baseRevision = da.readInt(); tikhomirov@5: // 12 + 8 = 20 bytes read here tikhomirov@2: // int linkRevision = di.readInt(); tikhomirov@2: // int parent1Revision = di.readInt(); tikhomirov@2: // int parent2Revision = di.readInt(); tikhomirov@2: // byte[] nodeid = new byte[32]; tikhomirov@2: if (inline) { tikhomirov@9: res.add(new IndexEntry(offset + REVLOGV1_RECORD_SIZE * res.size(), baseRevision)); tikhomirov@9: da.skip(3*4 + 32 + compressedLen); // Check: 44 (skip) + 20 (read) = 64 (total RevlogNG record size) tikhomirov@2: } else { tikhomirov@5: res.add(new IndexEntry(offset, baseRevision)); tikhomirov@9: da.skip(3*4 + 32); tikhomirov@2: } tikhomirov@10: if (da.isEmpty()) { tikhomirov@9: // fine, done then tikhomirov@22: res.trimToSize(); tikhomirov@9: index = res; tikhomirov@9: break; tikhomirov@10: } else { tikhomirov@10: // start reading next record tikhomirov@10: long l = da.readLong(); tikhomirov@10: offset = l >>> 16; tikhomirov@9: } tikhomirov@2: } tikhomirov@2: } catch (IOException ex) { tikhomirov@9: ex.printStackTrace(); // log error tikhomirov@9: // too bad, no outline then. tikhomirov@2: index = Collections.emptyList(); tikhomirov@9: } finally { tikhomirov@9: da.done(); tikhomirov@2: } tikhomirov@9: tikhomirov@3: } tikhomirov@3: tikhomirov@2: tikhomirov@2: // perhaps, package-local or protected, if anyone else from low-level needs them tikhomirov@5: // 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? tikhomirov@2: private static class IndexEntry { tikhomirov@4: 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)) tikhomirov@5: //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 tikhomirov@5: public final int baseRevision; tikhomirov@2: tikhomirov@5: public IndexEntry(long o, int baseRev) { tikhomirov@2: offset = o; tikhomirov@5: baseRevision = baseRev; tikhomirov@2: } tikhomirov@2: } tikhomirov@3: tikhomirov@3: // mpatch.c : apply() tikhomirov@3: // FIXME need to implement patch merge (fold, combine, gather and discard from aforementioned mpatch.[c|py]), also see Revlog and Mercurial PDF tikhomirov@77: public/*for HgBundle; until moved to better place*/static byte[] apply(byte[] baseRevisionContent, int outcomeLen, List patch) { tikhomirov@3: int last = 0, destIndex = 0; tikhomirov@43: if (outcomeLen == -1) { tikhomirov@43: outcomeLen = baseRevisionContent.length; tikhomirov@43: for (PatchRecord pr : patch) { tikhomirov@43: outcomeLen += pr.start - last + pr.len; tikhomirov@43: last = pr.end; tikhomirov@43: } tikhomirov@43: outcomeLen -= last; tikhomirov@43: last = 0; tikhomirov@43: } tikhomirov@43: byte[] rv = new byte[outcomeLen]; tikhomirov@3: for (PatchRecord pr : patch) { tikhomirov@43: System.arraycopy(baseRevisionContent, last, rv, destIndex, pr.start-last); tikhomirov@3: destIndex += pr.start - last; tikhomirov@43: System.arraycopy(pr.data, 0, rv, destIndex, pr.data.length); tikhomirov@3: destIndex += pr.data.length; tikhomirov@3: last = pr.end; tikhomirov@3: } tikhomirov@43: System.arraycopy(baseRevisionContent, last, rv, destIndex, baseRevisionContent.length - last); tikhomirov@3: return rv; tikhomirov@3: } tikhomirov@3: tikhomirov@35: // @see http://mercurial.selenic.com/wiki/BundleFormat, in Changelog group description tikhomirov@77: public static class PatchRecord { tikhomirov@52: /* tikhomirov@52: Given there are pr1 and pr2: tikhomirov@52: pr1.start to pr1.end will be replaced with pr's data (of pr1.len) tikhomirov@52: pr1.end to pr2.start gets copied from base tikhomirov@52: */ tikhomirov@77: public int start, end, len; tikhomirov@77: public byte[] data; tikhomirov@3: tikhomirov@36: // TODO consider PatchRecord that only records data position (absolute in data source), and acquires data as needed tikhomirov@36: private PatchRecord(int p1, int p2, int length, byte[] src) { tikhomirov@36: start = p1; tikhomirov@36: end = p2; tikhomirov@36: len = length; tikhomirov@36: data = src; tikhomirov@3: } tikhomirov@36: tikhomirov@36: /*package-local*/ static PatchRecord read(byte[] data, int offset) { tikhomirov@36: final int x = offset; // shorthand tikhomirov@36: int p1 = ((data[x] & 0xFF)<< 24) | ((data[x+1] & 0xFF) << 16) | ((data[x+2] & 0xFF) << 8) | (data[x+3] & 0xFF); tikhomirov@36: int p2 = ((data[x+4] & 0xFF) << 24) | ((data[x+5] & 0xFF) << 16) | ((data[x+6] & 0xFF) << 8) | (data[x+7] & 0xFF); tikhomirov@36: int len = ((data[x+8] & 0xFF) << 24) | ((data[x+9] & 0xFF) << 16) | ((data[x+10] & 0xFF) << 8) | (data[x+11] & 0xFF); tikhomirov@36: byte[] dataCopy = new byte[len]; tikhomirov@36: System.arraycopy(data, x+12, dataCopy, 0, len); tikhomirov@36: return new PatchRecord(p1, p2, len, dataCopy); tikhomirov@36: } tikhomirov@36: tikhomirov@77: public /*for HgBundle*/ static PatchRecord read(DataAccess da) throws IOException { tikhomirov@36: int p1 = da.readInt(); tikhomirov@36: int p2 = da.readInt(); tikhomirov@36: int len = da.readInt(); tikhomirov@36: byte[] src = new byte[len]; tikhomirov@36: da.readBytes(src, 0, len); tikhomirov@36: return new PatchRecord(p1, p2, len, src); tikhomirov@36: } tikhomirov@77: } tikhomirov@77: tikhomirov@77: // 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 tikhomirov@77: // instantly - e.g. calculate hash, or comparing two revisions tikhomirov@77: public interface Inspector { tikhomirov@77: // XXX boolean retVal to indicate whether to continue? tikhomirov@77: // TODO specify nodeid and data length, and reuse policy (i.e. if revlog stream doesn't reuse nodeid[] for each call) tikhomirov@77: void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[/*20*/] nodeid, byte[] data); tikhomirov@3: } tikhomirov@0: }