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@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@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@218: if (BAD_REVISION == 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@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@29: public void init() { tikhomirov@29: final RevlogStream stream = Revlog.this.content; tikhomirov@29: final int revisionCount = stream.revisionCount(); tikhomirov@200: firstParent = new Nodeid[revisionCount]; tikhomirov@200: // although branches/merges are less frequent, and most of secondParent would be -1/null, some sort of tikhomirov@200: // SparseOrderedList might be handy, provided its inner structures do not overweight simplicity of an array tikhomirov@200: secondParent = new Nodeid[revisionCount]; tikhomirov@200: // tikhomirov@200: sequential = new Nodeid[revisionCount]; tikhomirov@200: sorted = new Nodeid[revisionCount]; tikhomirov@200: tikhomirov@77: RevlogStream.Inspector insp = new RevlogStream.Inspector() { tikhomirov@200: 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@200: sequential[ix] = sorted[ix] = nid; tikhomirov@29: if (parent1Revision != -1) { tikhomirov@200: assert parent1Revision < ix; tikhomirov@200: firstParent[ix] = sequential[parent1Revision]; tikhomirov@183: } tikhomirov@200: if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1 tikhomirov@200: assert parent2Revision < ix; tikhomirov@200: secondParent[ix] = sequential[parent2Revision]; tikhomirov@29: } tikhomirov@200: ix++; tikhomirov@29: } tikhomirov@29: }; tikhomirov@197: stream.iterate(0, TIP, false, insp); 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@200: throw new HgBadStateException(); tikhomirov@200: } tikhomirov@29: } tikhomirov@31: tikhomirov@31: // FIXME need to decide whether Nodeid(00 * 20) is always known or not tikhomirov@200: // right now Nodeid.NULL is not recognized as known if passed to this method, tikhomirov@200: // caller is supposed to make explicit check 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 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 childrenOf(List roots) { tikhomirov@171: HashSet parents = new HashSet(); tikhomirov@200: LinkedList result = new LinkedList(); 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@200: * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog. tikhomirov@192: * @return true 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@200: // FIXME 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@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 null 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: }