tikhomirov@22: /*
tikhomirov@388:  * Copyright (c) 2010-2012 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@102:  * contact TMate Software at support@hg4j.com
tikhomirov@2:  */
tikhomirov@74: package org.tmatesoft.hg.repo;
tikhomirov@2: 
tikhomirov@80: import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION;
tikhomirov@405: import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
tikhomirov@74: import static org.tmatesoft.hg.repo.HgRepository.TIP;
tikhomirov@56: 
tikhomirov@157: import java.io.IOException;
tikhomirov@157: import java.nio.ByteBuffer;
tikhomirov@317: import java.util.ArrayList;
tikhomirov@56: import java.util.Arrays;
tikhomirov@29: import java.util.Collection;
tikhomirov@171: import java.util.HashSet;
tikhomirov@171: import java.util.LinkedList;
tikhomirov@171: import java.util.List;
tikhomirov@29: 
tikhomirov@157: import org.tmatesoft.hg.core.HgBadStateException;
tikhomirov@157: import org.tmatesoft.hg.core.HgException;
tikhomirov@354: import org.tmatesoft.hg.core.HgInvalidControlFileException;
tikhomirov@347: import org.tmatesoft.hg.core.HgInvalidRevisionException;
tikhomirov@74: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@307: import org.tmatesoft.hg.internal.ArrayHelper;
tikhomirov@157: import org.tmatesoft.hg.internal.DataAccess;
tikhomirov@324: import org.tmatesoft.hg.internal.Experimental;
tikhomirov@355: import org.tmatesoft.hg.internal.Preview;
tikhomirov@77: import org.tmatesoft.hg.internal.RevlogStream;
tikhomirov@324: import org.tmatesoft.hg.util.Adaptable;
tikhomirov@157: import org.tmatesoft.hg.util.ByteChannel;
tikhomirov@157: import org.tmatesoft.hg.util.CancelSupport;
tikhomirov@157: import org.tmatesoft.hg.util.CancelledException;
tikhomirov@355: import org.tmatesoft.hg.util.LogFacility;
tikhomirov@157: import org.tmatesoft.hg.util.ProgressSupport;
tikhomirov@74: 
tikhomirov@74: 
tikhomirov@2: /**
tikhomirov@157:  * Base class for all Mercurial entities that are serialized in a so called revlog format (changelog, manifest, data files).
tikhomirov@157:  * 
tikhomirov@157:  * Implementation note:
tikhomirov@157:  * Hides actual actual revlog stream implementation and its access methods (i.e. RevlogStream.Inspector), iow shall not expose anything internal
tikhomirov@157:  * in public methods.
tikhomirov@157:  *   
tikhomirov@74:  * @author Artem Tikhomirov
tikhomirov@74:  * @author TMate Software Ltd.
tikhomirov@2:  */
tikhomirov@74: abstract class Revlog {
tikhomirov@2: 
tikhomirov@115: 	private final HgRepository repo;
tikhomirov@21: 	protected final RevlogStream content;
tikhomirov@2: 
tikhomirov@115: 	protected Revlog(HgRepository hgRepo, RevlogStream contentStream) {
tikhomirov@2: 		if (hgRepo == null) {
tikhomirov@74: 			throw new IllegalArgumentException();
tikhomirov@74: 		}
tikhomirov@115: 		if (contentStream == null) {
tikhomirov@74: 			throw new IllegalArgumentException();
tikhomirov@2: 		}
tikhomirov@115: 		repo = hgRepo;
tikhomirov@115: 		content = contentStream;
tikhomirov@115: 	}
tikhomirov@115: 	
tikhomirov@115: 	// invalid Revlog
tikhomirov@115: 	protected Revlog(HgRepository hgRepo) {
tikhomirov@115: 		repo = hgRepo;
tikhomirov@115: 		content = null;
tikhomirov@2: 	}
tikhomirov@2: 
tikhomirov@2: 	public final HgRepository getRepo() {
tikhomirov@115: 		return repo;
tikhomirov@2: 	}
tikhomirov@2: 
tikhomirov@135: 	public final int getRevisionCount() {
tikhomirov@21: 		return content.revisionCount();
tikhomirov@21: 	}
tikhomirov@80: 	
tikhomirov@135: 	public final int getLastRevision() {
tikhomirov@135: 		return content.revisionCount() - 1;
tikhomirov@135: 	}
tikhomirov@354: 
tikhomirov@354: 	/**
tikhomirov@388: 	 * Map revision index to unique revision identifier (nodeid).
tikhomirov@354: 	 *  
tikhomirov@388: 	 * @param revision index of the entry in this revlog, may be {@link HgRepository#TIP}
tikhomirov@354: 	 * @return revision nodeid of the entry
tikhomirov@354: 	 * 
tikhomirov@354: 	 * @throws HgInvalidRevisionException if supplied argument doesn't represent revision index in this revlog
tikhomirov@354: 	 * @throws HgInvalidControlFileException if access to revlog index/data entry failed
tikhomirov@354: 	 */
tikhomirov@366: 	public final Nodeid getRevision(int revision) throws HgInvalidRevisionException, HgInvalidControlFileException {
tikhomirov@328: 		// XXX cache nodeids? Rather, if context.getCache(this).getRevisionMap(create == false) != null, use it
tikhomirov@80: 		return Nodeid.fromBinary(content.nodeid(revision), 0);
tikhomirov@80: 	}
tikhomirov@317: 	
tikhomirov@328: 	/**
tikhomirov@328: 	 * FIXME need to be careful about (1) ordering of the revisions in the return list; (2) modifications (sorting) of the argument array 
tikhomirov@328: 	 */
tikhomirov@366: 	public final List<Nodeid> getRevisions(int... revisions) throws HgInvalidRevisionException, HgInvalidControlFileException {
tikhomirov@317: 		ArrayList<Nodeid> rv = new ArrayList<Nodeid>(revisions.length);
tikhomirov@317: 		Arrays.sort(revisions);
tikhomirov@317: 		getRevisionsInternal(rv, revisions);
tikhomirov@317: 		return rv;
tikhomirov@317: 	}
tikhomirov@317: 	
tikhomirov@366: 	/*package-local*/ void getRevisionsInternal(final List<Nodeid> retVal, int[] sortedRevs) throws HgInvalidRevisionException, HgInvalidControlFileException {
tikhomirov@317: 		// once I have getRevisionMap and may find out whether it is avalable from cache,
tikhomirov@317: 		// may use it, perhaps only for small number of revisions
tikhomirov@317: 		content.iterate(sortedRevs, false, new RevlogStream.Inspector() {
tikhomirov@317: 			
tikhomirov@317: 			public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) {
tikhomirov@317: 				retVal.add(Nodeid.fromBinary(nodeid, 0));
tikhomirov@317: 			}
tikhomirov@317: 		});
tikhomirov@317: 	}
tikhomirov@37: 
tikhomirov@243: 	/**
tikhomirov@368: 	 * Get local index of the specified revision.
tikhomirov@347: 	 * If unsure, use {@link #isKnown(Nodeid)} to find out whether nodeid belongs to this revlog.
tikhomirov@243: 	 * 
tikhomirov@243: 	 * For occasional queries, this method works with decent performance, despite its O(n/2) approach.
tikhomirov@243: 	 * Alternatively, if you need to perform multiple queries (e.g. at least 15-20), {@link RevisionMap} may come handy.
tikhomirov@347: 	 * 
tikhomirov@243: 	 * @param nid revision to look up 
tikhomirov@347: 	 * @return revision local index in this revlog
tikhomirov@347: 	 * @throws HgInvalidRevisionException if supplied nodeid doesn't identify any revision from this revlog  
tikhomirov@354: 	 * @throws HgInvalidControlFileException if access to revlog index/data entry failed
tikhomirov@243: 	 */
tikhomirov@367: 	public final int getRevisionIndex(Nodeid nid) throws HgInvalidControlFileException, HgInvalidRevisionException {
tikhomirov@367: 		int revision = content.findRevisionIndex(nid);
tikhomirov@80: 		if (revision == BAD_REVISION) {
tikhomirov@393: 			// using toString() to identify revlog. HgDataFile.toString includes path, HgManifest and HgChangelog instances 
tikhomirov@393: 			// are fine with default (class name)
tikhomirov@393: 			// Perhaps, more tailored description method would be suitable here
tikhomirov@393: 			throw new HgInvalidRevisionException(String.format("Can't find revision %s in %s", nid.shortNotation(), this), nid, null);
tikhomirov@49: 		}
tikhomirov@49: 		return revision;
tikhomirov@49: 	}
tikhomirov@367: 	
tikhomirov@367: 	/**
tikhomirov@367: 	 * @deprecated use {@link #getRevisionIndex(Nodeid)} instead
tikhomirov@367: 	 */
tikhomirov@367: 	@Deprecated
tikhomirov@367: 	public final int getLocalRevision(Nodeid nid) throws HgInvalidControlFileException, HgInvalidRevisionException {
tikhomirov@367: 		return getRevisionIndex(nid);
tikhomirov@367: 	}
tikhomirov@367: 
tikhomirov@49: 
tikhomirov@354: 	/**
tikhomirov@354: 	 * Note, {@link Nodeid#NULL} nodeid is not reported as known in any revlog.
tikhomirov@354: 	 * 
tikhomirov@354: 	 * @param nodeid
tikhomirov@354: 	 * @return
tikhomirov@354: 	 * @throws HgInvalidControlFileException if access to revlog index/data entry failed
tikhomirov@354: 	 */
tikhomirov@354: 	public final boolean isKnown(Nodeid nodeid) throws HgInvalidControlFileException {
tikhomirov@367: 		final int rn = content.findRevisionIndex(nodeid);
tikhomirov@218: 		if (BAD_REVISION == rn) {
tikhomirov@39: 			return false;
tikhomirov@39: 		}
tikhomirov@49: 		if (rn < 0 || rn >= content.revisionCount()) {
tikhomirov@49: 			// Sanity check
tikhomirov@354: 			throw new HgBadStateException(String.format("Revision index %d found for nodeid %s is not from the range [0..%d]", rn, nodeid.shortNotation(), content.revisionCount()-1));
tikhomirov@49: 		}
tikhomirov@49: 		return true;
tikhomirov@39: 	}
tikhomirov@49: 
tikhomirov@37: 	/**
tikhomirov@394: 	 * Access to revision data as is, equivalent to <code>rawContent(getRevisionIndex(nodeid), sink)</code>
tikhomirov@394: 	 * 
tikhomirov@394: 	 * @param nodeid revision to retrieve
tikhomirov@394: 	 * @param sink data destination
tikhomirov@394: 	 * 
tikhomirov@394: 	 * @throws HgInvalidRevisionException if supplied argument doesn't represent revision index in this revlog
tikhomirov@394: 	 * @throws HgInvalidControlFileException if access to revlog index/data entry failed
tikhomirov@394: 	 * @throws CancelledException if content retrieval operation was cancelled
tikhomirov@394: 	 * 
tikhomirov@394: 	 * @see #rawContent(int, ByteChannel)
tikhomirov@37: 	 */
tikhomirov@394: 	protected void rawContent(Nodeid nodeid, ByteChannel sink) throws HgInvalidControlFileException, CancelledException, HgInvalidRevisionException {
tikhomirov@367: 		rawContent(getRevisionIndex(nodeid), sink);
tikhomirov@37: 	}
tikhomirov@29: 	
tikhomirov@37: 	/**
tikhomirov@394: 	 * Access to revision data as is (decompressed, but otherwise unprocessed, i.e. not parsed for e.g. changeset or manifest entries).
tikhomirov@394: 	 *  
tikhomirov@416: 	 * @param revisionIndex index of this revlog change (not a changelog revision index), non-negative. From predefined constants, only {@link HgRepository#TIP} makes sense.
tikhomirov@394: 	 * @param sink data destination
tikhomirov@394: 	 * 
tikhomirov@394: 	 * @throws HgInvalidRevisionException if supplied argument doesn't represent revision index in this revlog
tikhomirov@394: 	 * @throws HgInvalidControlFileException if access to revlog index/data entry failed
tikhomirov@394: 	 * @throws CancelledException if content retrieval operation was cancelled
tikhomirov@37: 	 */
tikhomirov@416: 	protected void rawContent(int revisionIndex, ByteChannel sink) throws HgInvalidControlFileException, CancelledException, HgInvalidRevisionException {
tikhomirov@157: 		if (sink == null) {
tikhomirov@157: 			throw new IllegalArgumentException();
tikhomirov@157: 		}
tikhomirov@394: 		try {
tikhomirov@394: 			ContentPipe insp = new ContentPipe(sink, 0, repo.getContext().getLog());
tikhomirov@394: 			insp.checkCancelled();
tikhomirov@416: 			content.iterate(revisionIndex, revisionIndex, true, insp);
tikhomirov@394: 			insp.checkFailed();
tikhomirov@394: 		} catch (IOException ex) {
tikhomirov@416: 			HgInvalidControlFileException e = new HgInvalidControlFileException(String.format("Access to revision %d content failed", revisionIndex), ex, null);
tikhomirov@416: 			e.setRevisionIndex(revisionIndex);
tikhomirov@394: 			// FIXME e.setFileName(content.getIndexFile() or this.getHumanFriendlyPath()) - shall decide whether 
tikhomirov@394: 			// protected abstract getPath() with impl in HgDataFile, HgManifest and HgChangelog or path is data of either Revlog or RevlogStream
tikhomirov@394: 			// Do the same (add file name) below
tikhomirov@394: 			throw e;
tikhomirov@394: 		} catch (HgInvalidControlFileException ex) {
tikhomirov@394: 			throw ex;
tikhomirov@394: 		} catch (HgException ex) {
tikhomirov@394: 			HgInvalidControlFileException e = new HgInvalidControlFileException(ex.getClass().getSimpleName(), ex, null);
tikhomirov@416: 			e.setRevisionIndex(revisionIndex);
tikhomirov@394: 			throw e;
tikhomirov@394: 		}
tikhomirov@37: 	}
tikhomirov@37: 
tikhomirov@56: 	/**
tikhomirov@405: 	 * Fills supplied arguments with information about revision parents.
tikhomirov@56: 	 * 
tikhomirov@56: 	 * @param revision - revision to query parents, or {@link HgRepository#TIP}
tikhomirov@405: 	 * @param parentRevisions - int[2] to get local revision numbers of parents (e.g. {6, -1}), {@link HgRepository#NO_REVISION} indicates parent not set
tikhomirov@56: 	 * @param parent1 - byte[20] or null, if parent's nodeid is not needed
tikhomirov@56: 	 * @param parent2 - byte[20] or null, if second parent's nodeid is not needed
tikhomirov@347: 	 * @throws HgInvalidRevisionException
tikhomirov@405: 	 * @throws HgInvalidControlFileException FIXME
tikhomirov@347: 	 * @throws IllegalArgumentException
tikhomirov@56: 	 */
tikhomirov@366: 	public void parents(int revision, int[] parentRevisions, byte[] parent1, byte[] parent2) throws HgInvalidRevisionException, HgInvalidControlFileException {
tikhomirov@56: 		if (revision != TIP && !(revision >= 0 && revision < content.revisionCount())) {
tikhomirov@347: 			throw new HgInvalidRevisionException(revision);
tikhomirov@56: 		}
tikhomirov@56: 		if (parentRevisions == null || parentRevisions.length < 2) {
tikhomirov@56: 			throw new IllegalArgumentException(String.valueOf(parentRevisions));
tikhomirov@56: 		}
tikhomirov@56: 		if (parent1 != null && parent1.length < 20) {
tikhomirov@56: 			throw new IllegalArgumentException(parent1.toString());
tikhomirov@56: 		}
tikhomirov@56: 		if (parent2 != null && parent2.length < 20) {
tikhomirov@56: 			throw new IllegalArgumentException(parent2.toString());
tikhomirov@56: 		}
tikhomirov@77: 		class ParentCollector implements RevlogStream.Inspector {
tikhomirov@56: 			public int p1 = -1;
tikhomirov@56: 			public int p2 = -1;
tikhomirov@56: 			public byte[] nodeid;
tikhomirov@56: 			
tikhomirov@157: 			public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess da) {
tikhomirov@56: 				p1 = parent1Revision;
tikhomirov@56: 				p2 = parent2Revision;
tikhomirov@56: 				this.nodeid = new byte[20];
tikhomirov@56: 				// nodeid arg now comes in 32 byte from (as in file format description), however upper 12 bytes are zeros.
tikhomirov@56: 				System.arraycopy(nodeid, nodeid.length > 20 ? nodeid.length - 20 : 0, this.nodeid, 0, 20);
tikhomirov@56: 			}
tikhomirov@56: 		};
tikhomirov@56: 		ParentCollector pc = new ParentCollector();
tikhomirov@56: 		content.iterate(revision, revision, false, pc);
tikhomirov@405: 		// although next code looks odd (NO_REVISION *is* -1), it's safer to be explicit
tikhomirov@405: 		parentRevisions[0] = pc.p1 == -1 ? NO_REVISION : pc.p1;
tikhomirov@405: 		parentRevisions[1] = pc.p2 == -1 ? NO_REVISION : pc.p2;
tikhomirov@56: 		if (parent1 != null) {
tikhomirov@405: 			if (parentRevisions[0] == NO_REVISION) {
tikhomirov@56: 				Arrays.fill(parent1, 0, 20, (byte) 0);
tikhomirov@56: 			} else {
tikhomirov@56: 				content.iterate(parentRevisions[0], parentRevisions[0], false, pc);
tikhomirov@56: 				System.arraycopy(pc.nodeid, 0, parent1, 0, 20);
tikhomirov@56: 			}
tikhomirov@56: 		}
tikhomirov@56: 		if (parent2 != null) {
tikhomirov@405: 			if (parentRevisions[1] == NO_REVISION) {
tikhomirov@56: 				Arrays.fill(parent2, 0, 20, (byte) 0);
tikhomirov@56: 			} else {
tikhomirov@56: 				content.iterate(parentRevisions[1], parentRevisions[1], false, pc);
tikhomirov@56: 				System.arraycopy(pc.nodeid, 0, parent2, 0, 20);
tikhomirov@56: 			}
tikhomirov@56: 		}
tikhomirov@56: 	}
tikhomirov@317: 	
tikhomirov@324: 	@Experimental
tikhomirov@366: 	public void walk(int start, int end, final Revlog.Inspector inspector) throws HgInvalidRevisionException, HgInvalidControlFileException {
tikhomirov@324: 		int lastRev = getLastRevision();
tikhomirov@324: 		if (start == TIP) {
tikhomirov@324: 			start = lastRev;
tikhomirov@324: 		}
tikhomirov@324: 		if (end == TIP) {
tikhomirov@324: 			end = lastRev;
tikhomirov@324: 		}
tikhomirov@356: 		final RevisionInspector revisionInsp = Adaptable.Factory.getAdapter(inspector, RevisionInspector.class, null);
tikhomirov@356: 		final ParentInspector parentInsp = Adaptable.Factory.getAdapter(inspector, ParentInspector.class, null);
tikhomirov@324: 		final Nodeid[] allRevisions = parentInsp == null ? null : new Nodeid[end - start + 1]; 
tikhomirov@324: 
tikhomirov@324: 		content.iterate(start, end, false, new RevlogStream.Inspector() {
tikhomirov@324: 			
tikhomirov@324: 			public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) {
tikhomirov@324: 				Nodeid nid = Nodeid.fromBinary(nodeid, 0);
tikhomirov@324: 				if (revisionInsp != null) {
tikhomirov@324: 					revisionInsp.next(revisionNumber, nid, linkRevision);
tikhomirov@324: 				}
tikhomirov@324: 				if (parentInsp != null) {
tikhomirov@324: 					Nodeid p1 = parent1Revision == -1 ? Nodeid.NULL : allRevisions[parent1Revision];
tikhomirov@324: 					Nodeid p2 = parent2Revision == -1 ? Nodeid.NULL : allRevisions[parent2Revision];
tikhomirov@324: 					allRevisions[revisionNumber] = nid;
tikhomirov@324: 					parentInsp.next(revisionNumber, nid, parent1Revision, parent2Revision, p1, p2);
tikhomirov@324: 				}
tikhomirov@324: 			}
tikhomirov@324: 		});
tikhomirov@324: 	}
tikhomirov@324: 
tikhomirov@324: 	/**
tikhomirov@324: 	 * MARKER 
tikhomirov@324: 	 */
tikhomirov@324: 	@Experimental
tikhomirov@324: 	public interface Inspector {
tikhomirov@324: 	}
tikhomirov@324: 
tikhomirov@324: 	@Experimental
tikhomirov@324: 	public interface RevisionInspector extends Inspector {
tikhomirov@368: 		void next(int revisionIndex, Nodeid revision, int linkedRevisionIndex);
tikhomirov@324: 	}
tikhomirov@324: 
tikhomirov@324: 	@Experimental
tikhomirov@324: 	public interface ParentInspector extends Inspector {
tikhomirov@327: 		// XXX document whether parentX is -1 or a constant (BAD_REVISION? or dedicated?)
tikhomirov@367: 		void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2);
tikhomirov@324: 	}
tikhomirov@324: 	
tikhomirov@29: 	/*
tikhomirov@29: 	 * XXX think over if it's better to do either:
tikhomirov@29: 	 * pw = getChangelog().new ParentWalker(); pw.init() and pass pw instance around as needed
tikhomirov@29: 	 * or
tikhomirov@29: 	 * add Revlog#getParentWalker(), static class, make cons() and #init package-local, and keep SoftReference to allow walker reuse.
tikhomirov@29: 	 * 
tikhomirov@29: 	 *  and yes, walker is not a proper name
tikhomirov@29: 	 */
tikhomirov@324: 	public final class ParentWalker implements ParentInspector {
tikhomirov@200: 
tikhomirov@200: 		
tikhomirov@200: 		private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
tikhomirov@200: 		private Nodeid[] sorted; // for binary search
tikhomirov@200: 		private int[] sorted2natural;
tikhomirov@200: 		private Nodeid[] firstParent;
tikhomirov@200: 		private Nodeid[] secondParent;
tikhomirov@200: 
tikhomirov@200: 		// Nodeid instances shall be shared between all arrays
tikhomirov@29: 
tikhomirov@29: 		public ParentWalker() {
tikhomirov@29: 		}
tikhomirov@29: 		
tikhomirov@192: 		public HgRepository getRepo() {
tikhomirov@192: 			return Revlog.this.getRepo();
tikhomirov@192: 		}
tikhomirov@192: 		
tikhomirov@324: 		public void next(int revisionNumber, Nodeid revision, int parent1Revision, int parent2Revision, Nodeid nidParent1, Nodeid nidParent2) {
tikhomirov@324: 			if (parent1Revision >= revisionNumber || parent2Revision >= revisionNumber) {
tikhomirov@324: 				throw new IllegalStateException(); // sanity, revisions are sequential
tikhomirov@324: 			}
tikhomirov@324: 			int ix = revisionNumber;
tikhomirov@324: 			sequential[ix] = sorted[ix] = revision;
tikhomirov@324: 			if (parent1Revision != -1) {
tikhomirov@324: 				firstParent[ix] = sequential[parent1Revision];
tikhomirov@324: 			}
tikhomirov@324: 			if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1
tikhomirov@324: 				secondParent[ix] = sequential[parent2Revision];
tikhomirov@324: 			}
tikhomirov@324: 		}
tikhomirov@324: 		
tikhomirov@366: 		public void init() throws HgInvalidControlFileException {
tikhomirov@324: 			final int revisionCount = Revlog.this.getRevisionCount();
tikhomirov@200: 			firstParent = new Nodeid[revisionCount];
tikhomirov@393: 			// TODO [post 1.0] Branches/merges are less frequent, and most of secondParent would be -1/null, hence 
tikhomirov@393: 			// IntMap might be better alternative here, but need to carefully analyze (test) whether this brings
tikhomirov@393: 			// real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant)
tikhomirov@200: 			secondParent = new Nodeid[revisionCount];
tikhomirov@200: 			//
tikhomirov@200: 			sequential = new Nodeid[revisionCount];
tikhomirov@200: 			sorted = new Nodeid[revisionCount];
tikhomirov@324: 			Revlog.this.walk(0, TIP, this);
tikhomirov@200: 			Arrays.sort(sorted);
tikhomirov@200: 			sorted2natural = new int[revisionCount];
tikhomirov@200: 			for (int i = 0; i < revisionCount; i++) {
tikhomirov@200: 				Nodeid n = sequential[i];
tikhomirov@200: 				int x = Arrays.binarySearch(sorted, n);
tikhomirov@200: 				assertSortedIndex(x);
tikhomirov@200: 				sorted2natural[x] = i;
tikhomirov@200: 			}
tikhomirov@29: 		}
tikhomirov@29: 		
tikhomirov@200: 		private void assertSortedIndex(int x) {
tikhomirov@200: 			if (x < 0) {
tikhomirov@403: 				throw new HgBadStateException(String.format("Bad index", x));
tikhomirov@200: 			}
tikhomirov@29: 		}
tikhomirov@31: 		
tikhomirov@393: 		/**
tikhomirov@393: 		 * Tells whether supplied revision is from the walker's associated revlog.
tikhomirov@393: 		 * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known. 
tikhomirov@393: 		 * @param nid revision to check, not <code>null</code>
tikhomirov@393: 		 * @return <code>true</code> if revision matches any revision in this revlog
tikhomirov@393: 		 */
tikhomirov@31: 		public boolean knownNode(Nodeid nid) {
tikhomirov@200: 			return Arrays.binarySearch(sorted, nid) >= 0;
tikhomirov@31: 		}
tikhomirov@29: 
tikhomirov@200: 		/**
tikhomirov@200: 		 * null if none. only known nodes (as per #knownNode) are accepted as arguments
tikhomirov@200: 		 */
tikhomirov@29: 		public Nodeid firstParent(Nodeid nid) {
tikhomirov@200: 			int x = Arrays.binarySearch(sorted, nid);
tikhomirov@200: 			assertSortedIndex(x);
tikhomirov@200: 			int i = sorted2natural[x];
tikhomirov@200: 			return firstParent[i];
tikhomirov@29: 		}
tikhomirov@49: 
tikhomirov@49: 		// never null, Nodeid.NULL if none known
tikhomirov@49: 		public Nodeid safeFirstParent(Nodeid nid) {
tikhomirov@49: 			Nodeid rv = firstParent(nid);
tikhomirov@49: 			return rv == null ? Nodeid.NULL : rv;
tikhomirov@49: 		}
tikhomirov@29: 		
tikhomirov@29: 		public Nodeid secondParent(Nodeid nid) {
tikhomirov@200: 			int x = Arrays.binarySearch(sorted, nid);
tikhomirov@200: 			assertSortedIndex(x);
tikhomirov@200: 			int i = sorted2natural[x];
tikhomirov@200: 			return secondParent[i];
tikhomirov@29: 		}
tikhomirov@29: 
tikhomirov@49: 		public Nodeid safeSecondParent(Nodeid nid) {
tikhomirov@49: 			Nodeid rv = secondParent(nid);
tikhomirov@49: 			return rv == null ? Nodeid.NULL : rv;
tikhomirov@49: 		}
tikhomirov@49: 
tikhomirov@29: 		public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) {
tikhomirov@200: 			int x = Arrays.binarySearch(sorted, nid);
tikhomirov@200: 			assertSortedIndex(x);
tikhomirov@200: 			int i = sorted2natural[x];
tikhomirov@200: 			Nodeid p1 = firstParent[i];
tikhomirov@29: 			boolean modified = false;
tikhomirov@29: 			if (p1 != null) {
tikhomirov@29: 				modified = c.add(p1);
tikhomirov@191: 			}
tikhomirov@200: 			Nodeid p2 = secondParent[i];
tikhomirov@191: 			if (p2 != null) {
tikhomirov@191: 				modified = c.add(p2) || modified;
tikhomirov@29: 			}
tikhomirov@29: 			return modified;
tikhomirov@29: 		}
tikhomirov@171: 
tikhomirov@171: 		// XXX alternative (and perhaps more reliable) approach would be to make a copy of allNodes and remove 
tikhomirov@171: 		// nodes, their parents and so on.
tikhomirov@171: 		
tikhomirov@200: 		// @return ordered collection of all children rooted at supplied nodes. Nodes shall not be descendants of each other!
tikhomirov@200: 		// Nodeids shall belong to this revlog
tikhomirov@200: 		public List<Nodeid> childrenOf(List<Nodeid> roots) {
tikhomirov@171: 			HashSet<Nodeid> parents = new HashSet<Nodeid>();
tikhomirov@200: 			LinkedList<Nodeid> result = new LinkedList<Nodeid>();
tikhomirov@200: 			int earliestRevision = Integer.MAX_VALUE;
tikhomirov@200: 			assert sequential.length == firstParent.length && firstParent.length == secondParent.length;
tikhomirov@200: 			// first, find earliest index of roots in question, as there's  no sense 
tikhomirov@200: 			// to check children among nodes prior to branch's root node
tikhomirov@200: 			for (Nodeid r : roots) {
tikhomirov@200: 				int x = Arrays.binarySearch(sorted, r);
tikhomirov@200: 				assertSortedIndex(x);
tikhomirov@200: 				int i = sorted2natural[x];
tikhomirov@200: 				if (i < earliestRevision) {
tikhomirov@200: 					earliestRevision = i;
tikhomirov@200: 				}
tikhomirov@200: 				parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a ==
tikhomirov@200: 			}
tikhomirov@200: 			for (int i = earliestRevision + 1; i < sequential.length; i++) {
tikhomirov@200: 				if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) {
tikhomirov@200: 					parents.add(sequential[i]); // to find next child
tikhomirov@200: 					result.add(sequential[i]);
tikhomirov@171: 				}
tikhomirov@171: 			}
tikhomirov@200: 			return result;
tikhomirov@171: 		}
tikhomirov@192: 		
tikhomirov@192: 		/**
tikhomirov@308: 		 * @return revisions that have supplied revision as their immediate parent
tikhomirov@308: 		 */
tikhomirov@308: 		public List<Nodeid> directChildren(Nodeid nid) {
tikhomirov@308: 			LinkedList<Nodeid> result = new LinkedList<Nodeid>();
tikhomirov@308: 			int x = Arrays.binarySearch(sorted, nid);
tikhomirov@308: 			assertSortedIndex(x);
tikhomirov@308: 			nid = sorted[x]; // canonical instance
tikhomirov@308: 			int start = sorted2natural[x];
tikhomirov@308: 			for (int i = start + 1; i < sequential.length; i++) {
tikhomirov@308: 				if (nid == firstParent[i] || nid == secondParent[i]) {
tikhomirov@308: 					result.add(sequential[i]);
tikhomirov@308: 				}
tikhomirov@308: 			}
tikhomirov@308: 			return result;
tikhomirov@308: 		}
tikhomirov@308: 		
tikhomirov@308: 		/**
tikhomirov@200: 		 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog.
tikhomirov@192: 		 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents. 
tikhomirov@192: 		 */
tikhomirov@200: 		public boolean hasChildren(Nodeid nid) {
tikhomirov@200: 			int x = Arrays.binarySearch(sorted, nid);
tikhomirov@200: 			assertSortedIndex(x);
tikhomirov@200: 			int i = sorted2natural[x];
tikhomirov@200: 			assert firstParent.length == secondParent.length; // just in case later I implement sparse array for secondParent
tikhomirov@200: 			assert firstParent.length == sequential.length;
tikhomirov@200: 			// to use == instead of equals, take the same Nodeid instance we used to fill all the arrays.
tikhomirov@200: 			final Nodeid canonicalNode = sequential[i];
tikhomirov@200: 			i++; // no need to check node itself. child nodes may appear in sequential only after revision in question
tikhomirov@200: 			for (; i < sequential.length; i++) {
tikhomirov@393: 				// TODO [post 1.0] likely, not very effective. 
tikhomirov@200: 				// May want to optimize it with another (Tree|Hash)Set, created on demand on first use, 
tikhomirov@200: 				// however, need to be careful with memory usage
tikhomirov@200: 				if (firstParent[i] == canonicalNode || secondParent[i] == canonicalNode) {
tikhomirov@200: 					return true;
tikhomirov@200: 				}
tikhomirov@200: 			}
tikhomirov@200: 			return false;
tikhomirov@192: 		}
tikhomirov@29: 	}
tikhomirov@157: 
tikhomirov@243: 	/**
tikhomirov@243: 	 * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of 
tikhomirov@367: 	 * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls.
tikhomirov@243: 	 * 
tikhomirov@368: 	 * {@link Revlog#getRevisionIndex(Nodeid)} with straightforward lookup approach performs O(n/2)
tikhomirov@368: 	 * {@link RevisionMap#revisionIndex(Nodeid)} is log(n), plus initialization is O(n) (just once).
tikhomirov@243: 	 */
tikhomirov@324: 	public final class RevisionMap implements RevisionInspector {
tikhomirov@243: 		/*
tikhomirov@368: 		 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex
tikhomirov@243: 		 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171)
tikhomirov@243: 		 * for complete changelog iteration. 
tikhomirov@243: 		 */
tikhomirov@243: 		
tikhomirov@243: 		/*
tikhomirov@324: 		 * XXX 3 * (x * 4) bytes. Can I do better?
tikhomirov@324: 		 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural.
tikhomirov@324: 		 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind) 
tikhomirov@243: 		 */
tikhomirov@243: 		private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
tikhomirov@243: 		private Nodeid[] sorted; // for binary search
tikhomirov@243: 		private int[] sorted2natural;
tikhomirov@243: 
tikhomirov@243: 		public RevisionMap() {
tikhomirov@243: 		}
tikhomirov@243: 		
tikhomirov@243: 		public HgRepository getRepo() {
tikhomirov@243: 			return Revlog.this.getRepo();
tikhomirov@243: 		}
tikhomirov@324: 		
tikhomirov@367: 		public void next(int revisionIndex, Nodeid revision, int linkedRevision) {
tikhomirov@367: 			sequential[revisionIndex] = sorted[revisionIndex] = revision;
tikhomirov@324: 		}
tikhomirov@243: 
tikhomirov@243: 		/**
tikhomirov@243: 		 * @return <code>this</code> for convenience.
tikhomirov@243: 		 */
tikhomirov@366: 		public RevisionMap init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgInvalidControlFileException{
tikhomirov@243: 			// XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
tikhomirov@324: 			final int revisionCount = Revlog.this.getRevisionCount();
tikhomirov@243: 			sequential = new Nodeid[revisionCount];
tikhomirov@243: 			sorted = new Nodeid[revisionCount];
tikhomirov@324: 			Revlog.this.walk(0, TIP, this);
tikhomirov@307: 			// next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
tikhomirov@307: 			// the way sorted2natural was build is O(n*log n).  
tikhomirov@307: 			final ArrayHelper ah = new ArrayHelper();
tikhomirov@307: 			ah.sort(sorted);
tikhomirov@307: 			// note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based 
tikhomirov@307: 			sorted2natural = ah.getReverse();
tikhomirov@243: 			return this;
tikhomirov@243: 		}
tikhomirov@243: 		
tikhomirov@367: 		public Nodeid revision(int revisionIndex) {
tikhomirov@367: 			return sequential[revisionIndex];
tikhomirov@243: 		}
tikhomirov@367: 		public int revisionIndex(Nodeid revision) {
tikhomirov@274: 			if (revision == null || revision.isNull()) {
tikhomirov@243: 				return BAD_REVISION;
tikhomirov@243: 			}
tikhomirov@243: 			int x = Arrays.binarySearch(sorted, revision);
tikhomirov@243: 			if (x < 0) {
tikhomirov@243: 				return BAD_REVISION;
tikhomirov@243: 			}
tikhomirov@307: 			return sorted2natural[x]-1;
tikhomirov@243: 		}
tikhomirov@367: 		/**
tikhomirov@367: 		 * @deprecated use {@link #revisionIndex(Nodeid)} instead
tikhomirov@367: 		 */
tikhomirov@367: 		@Deprecated
tikhomirov@367: 		public int localRevision(Nodeid revision) {
tikhomirov@367: 			return revisionIndex(revision);
tikhomirov@367: 		}
tikhomirov@243: 	}
tikhomirov@243: 
tikhomirov@277: 	protected abstract static class ErrorHandlingInspector implements RevlogStream.Inspector, CancelSupport {
tikhomirov@157: 		private Exception failure;
tikhomirov@277: 		private CancelSupport cancelSupport;
tikhomirov@157: 		
tikhomirov@277: 		protected void setCancelSupport(CancelSupport cs) {
tikhomirov@277: 			assert cancelSupport == null; // no reason to set it twice
tikhomirov@277: 			cancelSupport = cs;
tikhomirov@157: 		}
tikhomirov@157: 
tikhomirov@157: 		protected void recordFailure(Exception ex) {
tikhomirov@157: 			assert failure == null;
tikhomirov@157: 			failure = ex;
tikhomirov@157: 		}
tikhomirov@157: 
tikhomirov@394: 		// TODO consider if IOException in addition to HgException is of any real utility
tikhomirov@157: 		public void checkFailed() throws HgException, IOException, CancelledException {
tikhomirov@157: 			if (failure == null) {
tikhomirov@157: 				return;
tikhomirov@157: 			}
tikhomirov@157: 			if (failure instanceof IOException) {
tikhomirov@157: 				throw (IOException) failure;
tikhomirov@157: 			}
tikhomirov@157: 			if (failure instanceof CancelledException) {
tikhomirov@157: 				throw (CancelledException) failure;
tikhomirov@157: 			}
tikhomirov@157: 			if (failure instanceof HgException) {
tikhomirov@157: 				throw (HgException) failure;
tikhomirov@157: 			}
tikhomirov@157: 			throw new HgBadStateException(failure);
tikhomirov@157: 		}
tikhomirov@277: 
tikhomirov@277: 		public void checkCancelled() throws CancelledException {
tikhomirov@277: 			if (cancelSupport != null) {
tikhomirov@277: 				cancelSupport.checkCancelled();
tikhomirov@277: 			}
tikhomirov@277: 		}
tikhomirov@277: 	}
tikhomirov@277: 
tikhomirov@277: 	protected static class ContentPipe extends ErrorHandlingInspector implements RevlogStream.Inspector, CancelSupport {
tikhomirov@277: 		private final ByteChannel sink;
tikhomirov@277: 		private final int offset;
tikhomirov@355: 		private final LogFacility logFacility;
tikhomirov@277: 
tikhomirov@277: 		/**
tikhomirov@277: 		 * @param _sink - cannot be <code>null</code>
tikhomirov@277: 		 * @param seekOffset - when positive, orders to pipe bytes to the sink starting from specified offset, not from the first byte available in DataAccess
tikhomirov@355: 		 * @param log optional facility to put warnings/debug messages into, may be null.
tikhomirov@277: 		 */
tikhomirov@355: 		public ContentPipe(ByteChannel _sink, int seekOffset, LogFacility log) {
tikhomirov@277: 			assert _sink != null;
tikhomirov@277: 			sink = _sink;
tikhomirov@277: 			setCancelSupport(CancelSupport.Factory.get(_sink));
tikhomirov@277: 			offset = seekOffset;
tikhomirov@355: 			logFacility = log;
tikhomirov@277: 		}
tikhomirov@277: 		
tikhomirov@277: 		protected void prepare(int revisionNumber, DataAccess da) throws HgException, IOException {
tikhomirov@277: 			if (offset > 0) { // save few useless reset/rewind operations
tikhomirov@277: 				da.seek(offset);
tikhomirov@277: 			}
tikhomirov@277: 		}
tikhomirov@277: 
tikhomirov@277: 		public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess da) {
tikhomirov@277: 			try {
tikhomirov@277: 				prepare(revisionNumber, da); // XXX perhaps, prepare shall return DA (sliced, if needed)
tikhomirov@277: 				final ProgressSupport progressSupport = ProgressSupport.Factory.get(sink);
tikhomirov@355: 				ByteBuffer buf = ByteBuffer.allocate(actualLen > 8192 ? 8192 : actualLen);
tikhomirov@356: 				Preview p = Adaptable.Factory.getAdapter(sink, Preview.class, null);
tikhomirov@355: 				if (p != null) {
tikhomirov@355: 					progressSupport.start(2 * da.length());
tikhomirov@355: 					while (!da.isEmpty()) {
tikhomirov@355: 						checkCancelled();
tikhomirov@355: 						da.readBytes(buf);
tikhomirov@355: 						p.preview(buf);
tikhomirov@355: 						buf.clear();
tikhomirov@355: 					}
tikhomirov@355: 					da.reset();
tikhomirov@355: 					prepare(revisionNumber, da);
tikhomirov@355: 					progressSupport.worked(da.length());
tikhomirov@355: 					buf.clear();
tikhomirov@355: 				} else {
tikhomirov@355: 					progressSupport.start(da.length());
tikhomirov@355: 				}
tikhomirov@277: 				while (!da.isEmpty()) {
tikhomirov@277: 					checkCancelled();
tikhomirov@277: 					da.readBytes(buf);
tikhomirov@355: 					buf.flip(); // post: position == 0
tikhomirov@277: 					// XXX I may not rely on returned number of bytes but track change in buf position instead.
tikhomirov@355: 					
tikhomirov@355: 					int consumed = sink.write(buf);
tikhomirov@355: 					if ((consumed == 0 || consumed != buf.position()) && logFacility != null) {
tikhomirov@355: 						logFacility.warn(getClass(), "Bad data sink when reading revision %d. Reported %d bytes consumed, byt actually read %d", revisionNumber, consumed, buf.position());
tikhomirov@355: 					}
tikhomirov@355: 					if (buf.position() == 0) {
tikhomirov@355: 						throw new HgBadStateException("Bad sink implementation (consumes no bytes) results in endless loop");
tikhomirov@355: 					}
tikhomirov@355: 					buf.compact(); // ensure (a) there's space for new (b) data starts at 0
tikhomirov@277: 					progressSupport.worked(consumed);
tikhomirov@277: 				}
tikhomirov@277: 				progressSupport.done(); // XXX shall specify whether #done() is invoked always or only if completed successfully.
tikhomirov@277: 			} catch (IOException ex) {
tikhomirov@277: 				recordFailure(ex);
tikhomirov@277: 			} catch (CancelledException ex) {
tikhomirov@277: 				recordFailure(ex);
tikhomirov@277: 			} catch (HgException ex) {
tikhomirov@277: 				recordFailure(ex);
tikhomirov@277: 			}
tikhomirov@277: 		}
tikhomirov@157: 	}
tikhomirov@2: }