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@74: package org.tmatesoft.hg.repo;
tikhomirov@0: 
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@74: import org.tmatesoft.hg.internal.DataAccess;
tikhomirov@74: import org.tmatesoft.hg.internal.DataAccessProvider;
tikhomirov@74: 
tikhomirov@10: 
tikhomirov@0: /**
tikhomirov@74:  * XXX move to .internal?
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<IndexEntry> 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@10: 	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@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@49: 	// Unlike its counterpart, Revlog#getLocalRevisionNumber, doesn't fail with exception if node not found,
tikhomirov@49: 	// returns a predefined constant instead
tikhomirov@49: 	/*package-local*/ 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@49: 		return Integer.MIN_VALUE;
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@2: 	public void iterate(int start, int end, boolean needData, Revlog.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<PatchRecord> patches = new LinkedList<PatchRecord>();
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<IndexEntry> res = new ArrayList<IndexEntry>();
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@37: 	/*package-local for HgBundle; until moved to better place*/static byte[] apply(byte[] baseRevisionContent, int outcomeLen, List<PatchRecord> 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@36: 	/*package-local*/ static class PatchRecord { // copy of struct frag from mpatch.c
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@3: 		int start, end, len;
tikhomirov@3: 		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@36: 		/*package-local*/ 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@36: 		
tikhomirov@36: 		
tikhomirov@3: 	}
tikhomirov@0: }