tikhomirov@13: /* 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@74: tikhomirov@218: import static org.tmatesoft.hg.repo.HgRepository.TIP; tikhomirov@218: tikhomirov@232: import java.io.ByteArrayOutputStream; tikhomirov@157: import java.io.IOException; tikhomirov@218: import java.util.ArrayList; tikhomirov@218: import java.util.Arrays; tikhomirov@157: tikhomirov@157: import org.tmatesoft.hg.core.HgBadStateException; tikhomirov@74: import org.tmatesoft.hg.core.Nodeid; tikhomirov@157: import org.tmatesoft.hg.internal.DataAccess; tikhomirov@266: import org.tmatesoft.hg.internal.DigestHelper; tikhomirov@320: import org.tmatesoft.hg.internal.EncodingHelper; tikhomirov@232: import org.tmatesoft.hg.internal.Experimental; tikhomirov@312: import org.tmatesoft.hg.internal.IterateControlMediator; tikhomirov@218: import org.tmatesoft.hg.internal.Lifecycle; tikhomirov@304: import org.tmatesoft.hg.internal.Pool2; tikhomirov@77: import org.tmatesoft.hg.internal.RevlogStream; tikhomirov@312: import org.tmatesoft.hg.util.CancelSupport; tikhomirov@232: import org.tmatesoft.hg.util.Path; tikhomirov@312: import org.tmatesoft.hg.util.ProgressSupport; tikhomirov@74: tikhomirov@2: tikhomirov@2: /** tikhomirov@2: * tikhomirov@74: * @author Artem Tikhomirov tikhomirov@74: * @author TMate Software Ltd. tikhomirov@2: */ tikhomirov@2: public class HgManifest extends Revlog { tikhomirov@218: private RevisionMapper revisionMap; tikhomirov@285: tikhomirov@285: public enum Flags { tikhomirov@285: Exec, Link; tikhomirov@285: tikhomirov@285: static Flags parse(String flags) { tikhomirov@285: if ("x".equalsIgnoreCase(flags)) { tikhomirov@285: return Exec; tikhomirov@285: } tikhomirov@285: if ("l".equalsIgnoreCase(flags)) { tikhomirov@285: return Link; tikhomirov@285: } tikhomirov@285: if (flags == null) { tikhomirov@285: return null; tikhomirov@285: } tikhomirov@285: throw new IllegalStateException(flags); tikhomirov@285: } tikhomirov@285: tikhomirov@285: static Flags parse(byte[] data, int start, int length) { tikhomirov@285: if (length == 0) { tikhomirov@285: return null; tikhomirov@285: } tikhomirov@285: if (length == 1) { tikhomirov@285: if (data[start] == 'x') { tikhomirov@285: return Exec; tikhomirov@285: } tikhomirov@285: if (data[start] == 'l') { tikhomirov@285: return Link; tikhomirov@285: } tikhomirov@285: // FALL THROUGH tikhomirov@285: } tikhomirov@285: throw new IllegalStateException(new String(data, start, length)); tikhomirov@285: } tikhomirov@285: tikhomirov@285: String nativeString() { tikhomirov@285: if (this == Exec) { tikhomirov@285: return "x"; tikhomirov@285: } tikhomirov@285: if (this == Link) { tikhomirov@285: return "l"; tikhomirov@285: } tikhomirov@285: throw new IllegalStateException(toString()); tikhomirov@285: } tikhomirov@285: } tikhomirov@2: tikhomirov@13: /*package-local*/ HgManifest(HgRepository hgRepo, RevlogStream content) { tikhomirov@21: super(hgRepo, content); tikhomirov@13: } tikhomirov@13: tikhomirov@218: /** tikhomirov@218: * tikhomirov@218: * @param start changelog (not manifest!) revision to begin with tikhomirov@218: * @param end changelog (not manifest!) revision to stop, inclusive. tikhomirov@218: * @param inspector can't be null tikhomirov@218: */ tikhomirov@19: public void walk(int start, int end, final Inspector inspector) { tikhomirov@196: if (inspector == null) { tikhomirov@196: throw new IllegalArgumentException(); tikhomirov@196: } tikhomirov@218: int start0 = fromChangelog(start); tikhomirov@218: int end0 = fromChangelog(end); tikhomirov@300: if (end0 < start0) { tikhomirov@300: // there are tool-constructed repositories that got order of changeset revisions completely different from that of manifest tikhomirov@300: int x = end0; tikhomirov@300: end0 = start0; tikhomirov@300: start0 = x; tikhomirov@300: } tikhomirov@218: content.iterate(start0, end0, true, new ManifestParser(inspector)); tikhomirov@19: } tikhomirov@218: tikhomirov@254: /** tikhomirov@254: * "Sparse" iteration of the manifest tikhomirov@254: * tikhomirov@254: * @param inspector tikhomirov@254: * @param localRevisions local changeset revisions to visit tikhomirov@254: */ tikhomirov@254: public void walk(final Inspector inspector, int... localRevisions) { tikhomirov@254: if (inspector == null || localRevisions == null) { tikhomirov@254: throw new IllegalArgumentException(); tikhomirov@254: } tikhomirov@254: int[] manifestLocalRevs = new int[localRevisions.length]; tikhomirov@254: boolean needsSort = false; tikhomirov@254: for (int i = 0; i < localRevisions.length; i++) { tikhomirov@254: final int manifestLocalRev = fromChangelog(localRevisions[i]); tikhomirov@254: manifestLocalRevs[i] = manifestLocalRev; tikhomirov@254: if (i > 0 && manifestLocalRevs[i-1] > manifestLocalRev) { tikhomirov@254: needsSort = true; tikhomirov@254: } tikhomirov@254: } tikhomirov@254: if (needsSort) { tikhomirov@254: Arrays.sort(manifestLocalRevs); tikhomirov@254: } tikhomirov@254: content.iterate(manifestLocalRevs, true, new ManifestParser(inspector)); tikhomirov@254: } tikhomirov@254: tikhomirov@232: // manifest revision number that corresponds to the given changeset tikhomirov@218: /*package-local*/ int fromChangelog(int revisionNumber) { tikhomirov@218: if (HgInternals.wrongLocalRevision(revisionNumber)) { tikhomirov@218: throw new IllegalArgumentException(String.valueOf(revisionNumber)); tikhomirov@218: } tikhomirov@257: if (revisionNumber == HgRepository.WORKING_COPY || revisionNumber == HgRepository.BAD_REVISION) { tikhomirov@257: throw new IllegalArgumentException("Can't use constants like WORKING_COPY or BAD_REVISION"); tikhomirov@257: } tikhomirov@257: // revisionNumber == TIP is processed by RevisionMapper tikhomirov@218: if (revisionMap == null) { tikhomirov@218: revisionMap = new RevisionMapper(getRepo()); tikhomirov@218: content.iterate(0, TIP, false, revisionMap); tikhomirov@218: } tikhomirov@218: return revisionMap.at(revisionNumber); tikhomirov@218: } tikhomirov@218: tikhomirov@232: /** tikhomirov@232: * Extracts file revision as it was known at the time of given changeset. tikhomirov@232: * tikhomirov@232: * @param revisionNumber local changeset index tikhomirov@232: * @param file path to file in question tikhomirov@232: * @return file revision or null if manifest at specified revision doesn't list such file tikhomirov@232: */ tikhomirov@232: @Experimental(reason="Perhaps, HgDataFile shall own this method") tikhomirov@232: public Nodeid getFileRevision(int revisionNumber, final Path file) { tikhomirov@232: int rev = fromChangelog(revisionNumber); tikhomirov@232: final Nodeid[] rv = new Nodeid[] { null }; tikhomirov@232: content.iterate(rev, rev, true, new RevlogStream.Inspector() { tikhomirov@232: tikhomirov@232: public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) { tikhomirov@232: ByteArrayOutputStream bos = new ByteArrayOutputStream(); tikhomirov@232: try { tikhomirov@232: byte b; tikhomirov@232: while (!data.isEmpty() && (b = data.readByte()) != '\n') { tikhomirov@232: if (b != 0) { tikhomirov@232: bos.write(b); tikhomirov@232: } else { tikhomirov@232: String fname = new String(bos.toByteArray()); tikhomirov@232: bos.reset(); tikhomirov@232: if (file.toString().equals(fname)) { tikhomirov@232: byte[] nid = new byte[40]; tikhomirov@232: data.readBytes(nid, 0, 40); tikhomirov@232: rv[0] = Nodeid.fromAscii(nid, 0, 40); tikhomirov@232: break; tikhomirov@232: } tikhomirov@232: // else skip to the end of line tikhomirov@232: while (!data.isEmpty() && (b = data.readByte()) != '\n') tikhomirov@232: ; tikhomirov@232: } tikhomirov@232: } tikhomirov@232: } catch (IOException ex) { tikhomirov@232: throw new HgBadStateException(ex); tikhomirov@232: } tikhomirov@232: } tikhomirov@232: }); tikhomirov@232: return rv[0]; tikhomirov@232: } tikhomirov@232: tikhomirov@19: public interface Inspector { tikhomirov@222: boolean begin(int mainfestRevision, Nodeid nid, int changelogRevision); tikhomirov@285: /** tikhomirov@285: * @deprecated switch to {@link Inspector2#next(Nodeid, Path, Flags)} tikhomirov@285: */ tikhomirov@285: @Deprecated tikhomirov@19: boolean next(Nodeid nid, String fname, String flags); tikhomirov@222: boolean end(int manifestRevision); tikhomirov@2: } tikhomirov@267: tikhomirov@285: @Experimental(reason="Explore Path alternative for filenames and enum for flags") tikhomirov@285: public interface Inspector2 extends Inspector { tikhomirov@285: boolean next(Nodeid nid, Path fname, Flags flags); tikhomirov@267: } tikhomirov@267: tikhomirov@268: /** tikhomirov@268: * When Pool uses Strings directly, tikhomirov@268: * ManifestParser creates new String instance with new char[] value, and does byte->char conversion. tikhomirov@268: * For cpython repo, walk(0..10k), there are over 16 million filenames, of them only 3020 unique. tikhomirov@268: * This means there are 15.9 million useless char[] instances and byte->char conversions tikhomirov@268: * tikhomirov@285: * When String (Path) is wrapped into {@link PathProxy}, there's extra overhead of byte[] representation tikhomirov@285: * of the String, but these are only for unique Strings (Paths) (3020 in the example above). Besides, I save tikhomirov@268: * useless char[] and byte->char conversions. tikhomirov@268: */ tikhomirov@285: private static class PathProxy { tikhomirov@267: private byte[] data; tikhomirov@268: private int start; tikhomirov@268: private final int hash, length; tikhomirov@285: private Path result; tikhomirov@267: tikhomirov@285: public PathProxy(byte[] data, int start, int length) { tikhomirov@267: this.data = data; tikhomirov@267: this.start = start; tikhomirov@267: this.length = length; tikhomirov@267: tikhomirov@268: // copy from String.hashCode(). In fact, not necessarily match result of String(data).hashCode tikhomirov@268: // just need some nice algorithm here tikhomirov@267: int h = 0; tikhomirov@267: byte[] d = data; tikhomirov@267: for (int i = 0, off = start, len = length; i < len; i++) { tikhomirov@267: h = 31 * h + d[off++]; tikhomirov@267: } tikhomirov@267: hash = h; tikhomirov@267: } tikhomirov@267: tikhomirov@267: @Override tikhomirov@267: public boolean equals(Object obj) { tikhomirov@285: if (false == obj instanceof PathProxy) { tikhomirov@267: return false; tikhomirov@267: } tikhomirov@285: PathProxy o = (PathProxy) obj; tikhomirov@267: if (o.result != null && result != null) { tikhomirov@267: return result.equals(o.result); tikhomirov@267: } tikhomirov@268: if (o.length != length || o.hash != hash) { tikhomirov@267: return false; tikhomirov@267: } tikhomirov@267: for (int i = 0, x = o.start, y = start; i < length; i++) { tikhomirov@267: if (o.data[x++] != data[y++]) { tikhomirov@267: return false; tikhomirov@267: } tikhomirov@267: } tikhomirov@267: return true; tikhomirov@267: } tikhomirov@267: @Override tikhomirov@267: public int hashCode() { tikhomirov@267: return hash; tikhomirov@267: } tikhomirov@267: tikhomirov@285: public Path freeze() { tikhomirov@267: if (result == null) { tikhomirov@320: result = Path.create(EncodingHelper.fromManifest(data, start, length)); tikhomirov@268: // release reference to bigger data array, make a copy of relevant part only tikhomirov@285: // use original bytes, not those from String above to avoid cache misses due to different encodings tikhomirov@268: byte[] d = new byte[length]; tikhomirov@268: System.arraycopy(data, start, d, 0, length); tikhomirov@268: data = d; tikhomirov@268: start = 0; tikhomirov@267: } tikhomirov@267: return result; tikhomirov@267: } tikhomirov@267: } tikhomirov@196: tikhomirov@312: private static class ManifestParser implements RevlogStream.Inspector, Lifecycle { tikhomirov@196: private final Inspector inspector; tikhomirov@285: private final Inspector2 inspector2; tikhomirov@304: private Pool2 nodeidPool, thisRevPool; tikhomirov@304: private final Pool2 fnamePool; tikhomirov@266: private byte[] nodeidLookupBuffer = new byte[20]; // get reassigned each time new Nodeid is added to pool tikhomirov@312: private final ProgressSupport progressHelper; tikhomirov@312: private IterateControlMediator iterateControl; tikhomirov@262: tikhomirov@196: public ManifestParser(Inspector delegate) { tikhomirov@196: assert delegate != null; tikhomirov@196: inspector = delegate; tikhomirov@285: inspector2 = delegate instanceof Inspector2 ? (Inspector2) delegate : null; tikhomirov@304: nodeidPool = new Pool2(); tikhomirov@304: fnamePool = new Pool2(); tikhomirov@304: thisRevPool = new Pool2(); tikhomirov@312: progressHelper = ProgressSupport.Factory.get(delegate); tikhomirov@196: } tikhomirov@268: tikhomirov@196: public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess da) { tikhomirov@196: try { tikhomirov@312: if (!inspector.begin(revisionNumber, new Nodeid(nodeid, true), linkRevision)) { tikhomirov@312: iterateControl.stop(); tikhomirov@312: return; tikhomirov@312: } tikhomirov@285: Path fname = null; tikhomirov@285: Flags flags = null; tikhomirov@196: Nodeid nid = null; tikhomirov@267: int i; tikhomirov@267: byte[] data = da.byteArray(); tikhomirov@312: for (i = 0; i < actualLen; i++) { tikhomirov@267: int x = i; tikhomirov@267: for( ; data[i] != '\n' && i < actualLen; i++) { tikhomirov@267: if (fname == null && data[i] == 0) { tikhomirov@285: PathProxy px = fnamePool.unify(new PathProxy(data, x, i - x)); tikhomirov@268: // if (cached = fnamePool.unify(px))== px then cacheMiss, else cacheHit tikhomirov@268: // cpython 0..10k: hits: 15 989 152, misses: 3020 tikhomirov@268: fname = px.freeze(); tikhomirov@267: x = i+1; tikhomirov@196: } tikhomirov@196: } tikhomirov@267: if (i < actualLen) { tikhomirov@267: assert data[i] == '\n'; tikhomirov@267: int nodeidLen = i - x < 40 ? i-x : 40; // if > 40, there are flags tikhomirov@267: DigestHelper.ascii2bin(data, x, nodeidLen, nodeidLookupBuffer); // ignore return value as it's unlikely to have NULL in manifest tikhomirov@267: nid = new Nodeid(nodeidLookupBuffer, false); // this Nodeid is for pool lookup only, mock object tikhomirov@267: Nodeid cached = nodeidPool.unify(nid); tikhomirov@267: if (cached == nid) { tikhomirov@267: // buffer now belongs to the cached nodeid tikhomirov@267: nodeidLookupBuffer = new byte[20]; tikhomirov@267: } else { tikhomirov@267: nid = cached; // use existing version, discard the lookup object tikhomirov@267: } // for cpython 0..10k, cache hits are 15 973 301, vs 18871 misses. tikhomirov@267: thisRevPool.record(nid); // memorize revision for the next iteration. tikhomirov@267: if (nodeidLen + x < i) { tikhomirov@267: // 'x' and 'l' for executable bits and symlinks? tikhomirov@267: // hg --debug manifest shows 644 for each regular file in my repo tikhomirov@285: // for cpython 0..10k, there are 4361062 flag checks, and there's only 1 unique flag tikhomirov@285: flags = Flags.parse(data, x + nodeidLen, i-x-nodeidLen); tikhomirov@285: } else { tikhomirov@285: flags = null; tikhomirov@267: } tikhomirov@312: boolean good2go; tikhomirov@285: if (inspector2 == null) { tikhomirov@285: String flagString = flags == null ? null : flags.nativeString(); tikhomirov@312: good2go = inspector.next(nid, fname.toString(), flagString); tikhomirov@285: } else { tikhomirov@312: good2go = inspector2.next(nid, fname, flags); tikhomirov@312: } tikhomirov@312: if (!good2go) { tikhomirov@312: iterateControl.stop(); tikhomirov@312: return; tikhomirov@285: } tikhomirov@267: } tikhomirov@196: nid = null; tikhomirov@285: fname = null; tikhomirov@285: flags = null; tikhomirov@196: } tikhomirov@312: if (!inspector.end(revisionNumber)) { tikhomirov@312: iterateControl.stop(); tikhomirov@312: return; tikhomirov@312: } tikhomirov@262: // tikhomirov@262: // keep only actual file revisions, found at this version tikhomirov@262: // (next manifest is likely to refer to most of them, although in specific cases tikhomirov@262: // like commit in another branch a lot may be useless) tikhomirov@262: nodeidPool.clear(); tikhomirov@304: Pool2 t = nodeidPool; tikhomirov@262: nodeidPool = thisRevPool; tikhomirov@264: thisRevPool = t; tikhomirov@313: iterateControl.checkCancelled(); tikhomirov@312: progressHelper.worked(1); tikhomirov@196: } catch (IOException ex) { tikhomirov@196: throw new HgBadStateException(ex); tikhomirov@196: } tikhomirov@196: } tikhomirov@312: tikhomirov@312: public void start(int count, Callback callback, Object token) { tikhomirov@312: CancelSupport cs = CancelSupport.Factory.get(inspector, null); tikhomirov@312: iterateControl = new IterateControlMediator(cs, callback); tikhomirov@312: progressHelper.start(count); tikhomirov@312: } tikhomirov@312: tikhomirov@312: public void finish(Object token) { tikhomirov@312: progressHelper.done(); tikhomirov@312: } tikhomirov@196: } tikhomirov@218: tikhomirov@218: private static class RevisionMapper implements RevlogStream.Inspector, Lifecycle { tikhomirov@218: tikhomirov@218: private final int changelogRevisions; tikhomirov@218: private int[] changelog2manifest; tikhomirov@218: private final HgRepository repo; tikhomirov@218: tikhomirov@218: public RevisionMapper(HgRepository hgRepo) { tikhomirov@218: repo = hgRepo; tikhomirov@218: changelogRevisions = repo.getChangelog().getRevisionCount(); tikhomirov@218: } tikhomirov@218: tikhomirov@257: // respects TIP tikhomirov@218: public int at(int revisionNumber) { tikhomirov@257: if (revisionNumber == TIP) { tikhomirov@257: revisionNumber = changelogRevisions - 1; tikhomirov@257: } tikhomirov@218: if (changelog2manifest != null) { tikhomirov@218: return changelog2manifest[revisionNumber]; tikhomirov@218: } tikhomirov@218: return revisionNumber; tikhomirov@218: } tikhomirov@218: tikhomirov@218: public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) { tikhomirov@218: if (changelog2manifest != null) { tikhomirov@220: // next assertion is not an error, rather assumption check, which is too development-related to be explicit exception - tikhomirov@220: // I just wonder if there are manifests that have two entries pointing to single changeset. It seems unrealistic, though - tikhomirov@220: // changeset records one and only one manifest nodeid tikhomirov@220: assert changelog2manifest[linkRevision] == -1 : String.format("revision:%d, link:%d, already linked to revision:%d", revisionNumber, linkRevision, changelog2manifest[linkRevision]); tikhomirov@218: changelog2manifest[linkRevision] = revisionNumber; tikhomirov@218: } else { tikhomirov@218: if (revisionNumber != linkRevision) { tikhomirov@218: changelog2manifest = new int[changelogRevisions]; tikhomirov@218: Arrays.fill(changelog2manifest, -1); tikhomirov@218: for (int i = 0; i < revisionNumber; changelog2manifest[i] = i, i++) tikhomirov@218: ; tikhomirov@218: changelog2manifest[linkRevision] = revisionNumber; tikhomirov@218: } tikhomirov@218: } tikhomirov@218: } tikhomirov@218: tikhomirov@218: public void start(int count, Callback callback, Object token) { tikhomirov@218: if (count != changelogRevisions) { tikhomirov@218: assert count < changelogRevisions; // no idea what to do if manifest has more revisions than changelog tikhomirov@218: // the way how manifest may contain more revisions than changelog, as I can imagine, is a result of tikhomirov@218: // some kind of an import tool (e.g. from SVN or CVS), that creates manifest and changelog independently. tikhomirov@218: // Note, it's pure guess, I didn't see such repository yet (although the way manifest revisions tikhomirov@218: // in cpython repo are numbered makes me think aforementioned way) tikhomirov@218: changelog2manifest = new int[changelogRevisions]; tikhomirov@218: Arrays.fill(changelog2manifest, -1); tikhomirov@218: } tikhomirov@218: } tikhomirov@218: tikhomirov@218: public void finish(Object token) { tikhomirov@218: if (changelog2manifest == null) { tikhomirov@218: return; tikhomirov@218: } tikhomirov@218: // I assume there'd be not too many revisions we don't know manifest of tikhomirov@218: ArrayList undefinedChangelogRevision = new ArrayList(); tikhomirov@218: for (int i = 0; i < changelog2manifest.length; i++) { tikhomirov@218: if (changelog2manifest[i] == -1) { tikhomirov@218: undefinedChangelogRevision.add(i); tikhomirov@218: } tikhomirov@218: } tikhomirov@218: for (int u : undefinedChangelogRevision) { tikhomirov@218: Nodeid manifest = repo.getChangelog().range(u, u).get(0).manifest(); tikhomirov@220: // FIXME calculate those missing effectively (e.g. cache and sort nodeids to speed lookup tikhomirov@218: // right away in the #next (may refactor ParentWalker's sequential and sorted into dedicated helper and reuse here) tikhomirov@218: changelog2manifest[u] = repo.getManifest().getLocalRevision(manifest); tikhomirov@218: } tikhomirov@218: } tikhomirov@218: } tikhomirov@2: }