tikhomirov@22: /*
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@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@74: import static org.tmatesoft.hg.repo.HgRepository.TIP;
tikhomirov@56: 
tikhomirov@157: import java.io.IOException;
tikhomirov@157: import java.nio.ByteBuffer;
tikhomirov@56: import java.util.Arrays;
tikhomirov@29: import java.util.Collection;
tikhomirov@29: import java.util.Collections;
tikhomirov@29: import java.util.HashMap;
tikhomirov@171: import java.util.HashSet;
tikhomirov@29: import java.util.LinkedHashSet;
tikhomirov@171: import java.util.LinkedList;
tikhomirov@171: import java.util.List;
tikhomirov@29: import java.util.Map;
tikhomirov@29: import java.util.Set;
tikhomirov@29: 
tikhomirov@157: import org.tmatesoft.hg.core.HgBadStateException;
tikhomirov@157: import org.tmatesoft.hg.core.HgException;
tikhomirov@74: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@157: import org.tmatesoft.hg.internal.DataAccess;
tikhomirov@77: import org.tmatesoft.hg.internal.RevlogStream;
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@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@135: 	
tikhomirov@135: 	public final Nodeid getRevision(int revision) {
tikhomirov@80: 		// XXX cache nodeids?
tikhomirov@80: 		return Nodeid.fromBinary(content.nodeid(revision), 0);
tikhomirov@80: 	}
tikhomirov@37: 
tikhomirov@135: 	public final int getLocalRevision(Nodeid nid) {
tikhomirov@49: 		int revision = content.findLocalRevisionNumber(nid);
tikhomirov@80: 		if (revision == BAD_REVISION) {
tikhomirov@49: 			throw new IllegalArgumentException(String.format("%s doesn't represent a revision of %s", nid.toString(), this /*XXX HgDataFile.getPath might be more suitable here*/));
tikhomirov@49: 		}
tikhomirov@49: 		return revision;
tikhomirov@49: 	}
tikhomirov@49: 
tikhomirov@39: 	// Till now, i follow approach that NULL nodeid is never part of revlog
tikhomirov@135: 	public final boolean isKnown(Nodeid nodeid) {
tikhomirov@49: 		final int rn = content.findLocalRevisionNumber(nodeid);
tikhomirov@49: 		if (Integer.MIN_VALUE == rn) {
tikhomirov@39: 			return false;
tikhomirov@39: 		}
tikhomirov@49: 		if (rn < 0 || rn >= content.revisionCount()) {
tikhomirov@49: 			// Sanity check
tikhomirov@49: 			throw new IllegalStateException();
tikhomirov@49: 		}
tikhomirov@49: 		return true;
tikhomirov@39: 	}
tikhomirov@49: 
tikhomirov@37: 	/**
tikhomirov@37: 	 * Access to revision data as is (decompressed, but otherwise unprocessed, i.e. not parsed for e.g. changeset or manifest entries) 
tikhomirov@37: 	 * @param nodeid
tikhomirov@37: 	 */
tikhomirov@157: 	protected void rawContent(Nodeid nodeid, ByteChannel sink) throws HgException, IOException, CancelledException {
tikhomirov@157: 		rawContent(getLocalRevision(nodeid), sink);
tikhomirov@37: 	}
tikhomirov@29: 	
tikhomirov@37: 	/**
tikhomirov@37: 	 * @param revision - repo-local index of this file change (not a changelog revision number!)
tikhomirov@37: 	 */
tikhomirov@157: 	protected void rawContent(int revision, ByteChannel sink) throws HgException, IOException, CancelledException {
tikhomirov@157: 		if (sink == null) {
tikhomirov@157: 			throw new IllegalArgumentException();
tikhomirov@157: 		}
tikhomirov@157: 		ContentPipe insp = new ContentPipe(sink, 0);
tikhomirov@157: 		insp.checkCancelled();
tikhomirov@37: 		content.iterate(revision, revision, true, insp);
tikhomirov@157: 		insp.checkFailed();
tikhomirov@37: 	}
tikhomirov@37: 
tikhomirov@56: 	/**
tikhomirov@56: 	 * XXX perhaps, return value Nodeid[2] and boolean needNodeids is better (and higher level) API for this query?
tikhomirov@56: 	 * 
tikhomirov@56: 	 * @param revision - revision to query parents, or {@link HgRepository#TIP}
tikhomirov@56: 	 * @param parentRevisions - int[2] to get local revision numbers of parents (e.g. {6, -1})
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@56: 	 * @return
tikhomirov@56: 	 */
tikhomirov@56: 	public void parents(int revision, int[] parentRevisions, byte[] parent1, byte[] parent2) {
tikhomirov@56: 		if (revision != TIP && !(revision >= 0 && revision < content.revisionCount())) {
tikhomirov@56: 			throw new IllegalArgumentException(String.valueOf(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@56: 		parentRevisions[0] = pc.p1;
tikhomirov@56: 		parentRevisions[1] = pc.p2;
tikhomirov@56: 		if (parent1 != null) {
tikhomirov@56: 			if (parentRevisions[0] == -1) {
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@56: 			if (parentRevisions[1] == -1) {
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@56: 
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@29: 	public final class ParentWalker {
tikhomirov@29: 		private Map<Nodeid, Nodeid> firstParent;
tikhomirov@29: 		private Map<Nodeid, Nodeid> secondParent;
tikhomirov@171: 		private final LinkedHashSet<Nodeid> allNodes = new LinkedHashSet<Nodeid>(); // childrenOf rely on ordering
tikhomirov@29: 
tikhomirov@29: 		public ParentWalker() {
tikhomirov@29: 			firstParent = secondParent = Collections.emptyMap();
tikhomirov@29: 		}
tikhomirov@29: 		
tikhomirov@29: 		public void init() {
tikhomirov@29: 			final RevlogStream stream = Revlog.this.content;
tikhomirov@29: 			final int revisionCount = stream.revisionCount();
tikhomirov@29: 			firstParent = new HashMap<Nodeid, Nodeid>(revisionCount);
tikhomirov@29: 			secondParent = new HashMap<Nodeid, Nodeid>(firstParent.size() >> 1); // assume branches/merges are less frequent
tikhomirov@29: 			
tikhomirov@77: 			RevlogStream.Inspector insp = new RevlogStream.Inspector() {
tikhomirov@29: 				final Nodeid[] sequentialRevisionNodeids = new Nodeid[revisionCount];
tikhomirov@29: 				int ix = 0;
tikhomirov@157: 				public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess da) {
tikhomirov@29: 					if (ix != revisionNumber) {
tikhomirov@29: 						// XXX temp code, just to make sure I understand what's going on here
tikhomirov@29: 						throw new IllegalStateException();
tikhomirov@29: 					}
tikhomirov@29: 					if (parent1Revision >= revisionNumber || parent2Revision >= revisionNumber) {
tikhomirov@29: 						throw new IllegalStateException(); // sanity, revisions are sequential
tikhomirov@29: 					}
tikhomirov@29: 					final Nodeid nid = new Nodeid(nodeid, true);
tikhomirov@29: 					sequentialRevisionNodeids[ix++] = nid;
tikhomirov@29: 					allNodes.add(nid);
tikhomirov@29: 					if (parent1Revision != -1) {
tikhomirov@29: 						firstParent.put(nid, sequentialRevisionNodeids[parent1Revision]);
tikhomirov@183: 					}
tikhomirov@183: 					if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1  
tikhomirov@183: 						secondParent.put(nid, sequentialRevisionNodeids[parent2Revision]);
tikhomirov@29: 					}
tikhomirov@29: 				}
tikhomirov@29: 			};
tikhomirov@29: 			stream.iterate(0, -1, false, insp);
tikhomirov@29: 		}
tikhomirov@29: 		
tikhomirov@29: 		public Set<Nodeid> allNodes() {
tikhomirov@29: 			return Collections.unmodifiableSet(allNodes);
tikhomirov@29: 		}
tikhomirov@31: 		
tikhomirov@31: 		// FIXME need to decide whether Nodeid(00 * 20) is always known or not
tikhomirov@31: 		public boolean knownNode(Nodeid nid) {
tikhomirov@31: 			return allNodes.contains(nid);
tikhomirov@31: 		}
tikhomirov@29: 
tikhomirov@29: 		// null if none
tikhomirov@29: 		public Nodeid firstParent(Nodeid nid) {
tikhomirov@29: 			return firstParent.get(nid);
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@29: 			return secondParent.get(nid);
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@29: 			Nodeid p1 = firstParent(nid);
tikhomirov@29: 			boolean modified = false;
tikhomirov@29: 			if (p1 != null) {
tikhomirov@29: 				modified = c.add(p1);
tikhomirov@191: 			}
tikhomirov@191: 			Nodeid p2 = secondParent(nid);
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@171: 		// @return ordered collection of all children rooted at supplied nodes. Nodes shall not be descendants of each other! 
tikhomirov@171: 		public List<Nodeid> childrenOf(List<Nodeid> nodes) {
tikhomirov@171: 			HashSet<Nodeid> parents = new HashSet<Nodeid>();
tikhomirov@171: 			LinkedHashSet<Nodeid> result = new LinkedHashSet<Nodeid>();
tikhomirov@171: 			LinkedList<Nodeid> orderedResult = new LinkedList<Nodeid>();
tikhomirov@171: 			for(Nodeid next : allNodes) {
tikhomirov@171: 				// i assume allNodes is sorted, hence do not check any parents unless we hit any common known node first 
tikhomirov@171: 				if (nodes.contains(next)) {
tikhomirov@171: 					parents.add(next);
tikhomirov@171: 				} else {
tikhomirov@171: 					if (parents.isEmpty()) {
tikhomirov@171: 						// didn't scroll up to any known yet
tikhomirov@171: 						continue;
tikhomirov@171: 					}
tikhomirov@171: 					// record each and every node reported after first common known node hit  
tikhomirov@171: 					orderedResult.addLast(next);
tikhomirov@171: 					if (parents.contains(firstParent(next)) || parents.contains(secondParent(next))) {
tikhomirov@171: 						result.add(next);
tikhomirov@171: 						parents.add(next); // to find next's children
tikhomirov@171: 					}
tikhomirov@171: 				}
tikhomirov@171: 			}
tikhomirov@171: 			// leave only those of interest in ordered sequence 
tikhomirov@171: 			orderedResult.retainAll(result);
tikhomirov@171: 			return orderedResult;
tikhomirov@171: 		}
tikhomirov@29: 	}
tikhomirov@157: 
tikhomirov@157: 	protected static class ContentPipe implements RevlogStream.Inspector, CancelSupport {
tikhomirov@157: 		private final ByteChannel sink;
tikhomirov@157: 		private final CancelSupport cancelSupport;
tikhomirov@157: 		private Exception failure;
tikhomirov@157: 		private final int offset;
tikhomirov@157: 
tikhomirov@157: 		/**
tikhomirov@157: 		 * @param _sink - cannot be <code>null</code>
tikhomirov@157: 		 * @param seekOffset - when positive, orders to pipe bytes to the sink starting from specified offset, not from the first byte available in DataAccess
tikhomirov@157: 		 */
tikhomirov@157: 		public ContentPipe(ByteChannel _sink, int seekOffset) {
tikhomirov@157: 			assert _sink != null;
tikhomirov@157: 			sink = _sink;
tikhomirov@157: 			cancelSupport = CancelSupport.Factory.get(_sink);
tikhomirov@157: 			offset = seekOffset;
tikhomirov@157: 		}
tikhomirov@157: 		
tikhomirov@157: 		protected void prepare(int revisionNumber, DataAccess da) throws HgException, IOException {
tikhomirov@157: 			if (offset > 0) { // save few useless reset/rewind operations
tikhomirov@157: 				da.seek(offset);
tikhomirov@157: 			}
tikhomirov@157: 		}
tikhomirov@157: 
tikhomirov@157: 		public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess da) {
tikhomirov@157: 			try {
tikhomirov@157: 				prepare(revisionNumber, da); // XXX perhaps, prepare shall return DA (sliced, if needed)
tikhomirov@157: 				final ProgressSupport progressSupport = ProgressSupport.Factory.get(sink);
tikhomirov@157: 				ByteBuffer buf = ByteBuffer.allocate(512);
tikhomirov@157: 				progressSupport.start(da.length());
tikhomirov@157: 				while (!da.isEmpty()) {
tikhomirov@157: 					cancelSupport.checkCancelled();
tikhomirov@157: 					da.readBytes(buf);
tikhomirov@157: 					buf.flip();
tikhomirov@157: 					// XXX I may not rely on returned number of bytes but track change in buf position instead.
tikhomirov@157: 					int consumed = sink.write(buf); 
tikhomirov@157: 					// FIXME in fact, bad sink implementation (that consumes no bytes) would result in endless loop. Need to account for this 
tikhomirov@157: 					buf.compact();
tikhomirov@157: 					progressSupport.worked(consumed);
tikhomirov@157: 				}
tikhomirov@157: 				progressSupport.done(); // XXX shall specify whether #done() is invoked always or only if completed successfully.
tikhomirov@157: 			} catch (IOException ex) {
tikhomirov@157: 				recordFailure(ex);
tikhomirov@157: 			} catch (CancelledException ex) {
tikhomirov@157: 				recordFailure(ex);
tikhomirov@157: 			} catch (HgException ex) {
tikhomirov@157: 				recordFailure(ex);
tikhomirov@157: 			}
tikhomirov@157: 		}
tikhomirov@157: 		
tikhomirov@157: 		public void checkCancelled() throws CancelledException {
tikhomirov@157: 			cancelSupport.checkCancelled();
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@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@157: 	}
tikhomirov@2: }