# HG changeset patch # User Artem Tikhomirov # Date 1339077669 -7200 # Node ID 5787e912f60ed109e6da407430149c3a4b1bd64c # Parent 2e402c12ebc6c1ba6ba1ad7c2cf3a52a678b222b Speed up changeset phase detection when no parent cache is avalable diff -r 2e402c12ebc6 -r 5787e912f60e cmdline/org/tmatesoft/hg/console/Main.java --- a/cmdline/org/tmatesoft/hg/console/Main.java Wed Jun 06 21:23:57 2012 +0200 +++ b/cmdline/org/tmatesoft/hg/console/Main.java Thu Jun 07 16:01:09 2012 +0200 @@ -45,6 +45,7 @@ import org.tmatesoft.hg.internal.PathGlobMatcher; import org.tmatesoft.hg.internal.PhasesHelper; import org.tmatesoft.hg.internal.RelativePathRewrite; +import org.tmatesoft.hg.internal.RevisionDescendants; import org.tmatesoft.hg.internal.StreamLogFacility; import org.tmatesoft.hg.repo.HgBranches; import org.tmatesoft.hg.repo.HgChangelog; @@ -95,7 +96,10 @@ public static void main(String[] args) throws Exception { Main m = new Main(args); - m.dumpPhases(); + m.testRevisionDescendants(); + for (int i : new int[] {1,2,3}) { + m.dumpPhases(); + } // m.buildFileLog(); // m.testConsoleLog(); // m.testTreeTraversal(); @@ -118,22 +122,53 @@ // m.bunchOfTests(); } - // hg/test-phases + // -R {junit-test-repos}/branches-1 + private void testRevisionDescendants() throws Exception { + int[] roots = new int[] {0, 1, 2, 3, 4, 5}; + RevisionDescendants[] result = new RevisionDescendants[roots.length]; + for (int i = 0; i < roots.length; i++) { + result[i] = new RevisionDescendants(hgRepo, roots[i]); + result[i].build(); + } + for (int i = 0; i < roots.length; i++) { + System.out.printf("For root %d descendats are:", roots[i]); + for (int j = roots[i], x = hgRepo.getChangelog().getLastRevision(); j <= x; j++) { + if (result[i].isDescendant(j)) { + System.out.printf("%3d ", j); + } + } + System.out.printf(", isEmpty:%b\n", !result[i].hasDescendants()); + } + } + + // -R ${system_property:user.home}/hg/test-phases/ // TODO as junit test private void dumpPhases() throws Exception { + HgPhase[] result1 = new HgPhase[hgRepo.getChangelog().getRevisionCount()]; + HgPhase[] result2 = new HgPhase[hgRepo.getChangelog().getRevisionCount()]; + final long start1 = System.nanoTime(); HgChangelog.ParentWalker pw = hgRepo.getChangelog().new ParentWalker(); pw.init(); + final long start1bis = System.nanoTime(); PhasesHelper ph = new PhasesHelper(hgRepo, pw); - System.out.println("With ParentWalker(simulates HgChangeset case)"); for (int i = 0, l = hgRepo.getChangelog().getLastRevision(); i <= l; i++) { - HgPhase phase = ph.getPhase(i, null); - System.out.printf("rev:%3d, phase:%s\n", i, phase); + result1[i] = ph.getPhase(i, null); } + final long start2 = System.nanoTime(); ph = new PhasesHelper(hgRepo); - System.out.println("Without ParentWalker"); for (int i = 0, l = hgRepo.getChangelog().getLastRevision(); i <= l; i++) { - HgPhase phase = ph.getPhase(i, null); - System.out.printf("rev:%3d, phase:%s\n", i, phase); + result2[i] = ph.getPhase(i, null); + } + final long end = System.nanoTime(); + System.out.printf("With ParentWalker(simulates log command for whole repo): %d ms (pw init: %,d ns)\n", (start2 - start1)/1000, start1bis - start1); + printPhases(result1); + System.out.printf("Without ParentWalker (simulates log command for single file): %d ms\n", (end - start2)/1000); + printPhases(result2); + } + + private static void printPhases(HgPhase[] phase) { + for (int i = 0; i < phase.length; i++) { + System.out.printf("rev:%3d, phase:%s\n", i, phase[i]); } } diff -r 2e402c12ebc6 -r 5787e912f60e src/org/tmatesoft/hg/internal/PhasesHelper.java --- a/src/org/tmatesoft/hg/internal/PhasesHelper.java Wed Jun 06 21:23:57 2012 +0200 +++ b/src/org/tmatesoft/hg/internal/PhasesHelper.java Thu Jun 07 16:01:09 2012 +0200 @@ -18,16 +18,13 @@ import static org.tmatesoft.hg.repo.HgPhase.Draft; import static org.tmatesoft.hg.repo.HgPhase.Secret; -import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; -import java.util.Arrays; import java.util.Collections; import java.util.HashMap; -import java.util.HashSet; import java.util.LinkedList; import java.util.List; @@ -47,21 +44,20 @@ */ public final class PhasesHelper { - private final HgRepository hgRepo; + private final HgRepository repo; private final HgChangelog.ParentWalker parentHelper; private Boolean repoSupporsPhases; private List draftPhaseRoots; private List secretPhaseRoots; - private int[] earliestRevIndex = new int[HgPhase.values().length]; + private RevisionDescendants[][] phaseDescendants = new RevisionDescendants[HgPhase.values().length][]; - public PhasesHelper(HgRepository repo) { - this(repo, null); + public PhasesHelper(HgRepository hgRepo) { + this(hgRepo, null); } - public PhasesHelper(HgRepository repo, HgChangelog.ParentWalker pw) { - hgRepo = repo; + public PhasesHelper(HgRepository hgRepo, HgChangelog.ParentWalker pw) { + repo = hgRepo; parentHelper = pw; - Arrays.fill(earliestRevIndex, BAD_REVISION); } public boolean isCapableOfPhases() throws HgInvalidControlFileException { @@ -82,8 +78,9 @@ if (!isCapableOfPhases()) { return HgPhase.Undefined; } - if (csetRev == null || csetRev.isNull()) { - csetRev = hgRepo.getChangelog().getRevision(csetRevIndex); + // csetRev is only used when parentHelper is available + if (parentHelper != null && (csetRev == null || csetRev.isNull())) { + csetRev = repo.getChangelog().getRevision(csetRevIndex); } for (HgPhase phase : new HgPhase[] {HgPhase.Secret, HgPhase.Draft }) { @@ -91,49 +88,21 @@ if (roots.isEmpty()) { continue; } - if (roots.contains(csetRev)) { - return phase; - } if (parentHelper != null) { + if (roots.contains(csetRev)) { + return phase; + } if (parentHelper.childrenOf(roots).contains(csetRev)) { return phase; } } else { // no parent helper - // search all descendants - int earliestRootRevIndex = getEarliestPhaseRevision(phase); - if (earliestRootRevIndex > csetRevIndex) { - // this phase started later than our changeset was added, try another phase - continue; - } - /* - * TODO descendants() method to build a BitSet with 1 at index of those that are descendants - * wrap it into a class with root nodeid to - * (a) collect only for a subset of repository, - * (b) be able to answer isDescendant(int csetRevIndex) using absolute indexing (i.e bitAt(csetRevIndex - rootRevIndex)) - */ - final HashSet parents2consider = new HashSet(roots); - final boolean[] result = new boolean[] { false }; - hgRepo.getChangelog().walk(earliestRootRevIndex, csetRevIndex, new HgChangelog.ParentInspector() { - - public void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2) { - boolean descendant = false; - if (!nidParent1.isNull() && parents2consider.contains(nidParent1)) { - parents2consider.add(revision); - descendant = true; - } - if (!nidParent2.isNull() && parents2consider.contains(nidParent2)) { - parents2consider.add(revision); - descendant = true; - } - if (descendant && revisionIndex == csetRevIndex) { - // revision of interest descends from one of the roots - result[0] = true; - } + // search all descendants.RevisuionDescendats includes root as well. + for (RevisionDescendants rd : getPhaseDescendants(phase)) { + // isCandidate is to go straight to another root if changeset was added later that the current root + if (rd.isCandidate(csetRevIndex) && rd.isDescendant(csetRevIndex)) { + return phase; } - }); - if (result[0]) { - return phase; } } } @@ -141,18 +110,9 @@ } - - private int[] toIndexes(List roots) throws HgInvalidControlFileException { - int[] rv = new int[roots.size()]; - for (int i = 0; i < rv.length; i++) { - rv[i] = hgRepo.getChangelog().getRevisionIndex(roots.get(i)); - } - return rv; - } - private Boolean readRoots() throws HgInvalidControlFileException { // FIXME shall access phaseroots through HgRepository#repoPathHelper - File phaseroots = new File(HgInternals.getRepositoryDir(hgRepo), "store/phaseroots"); + File phaseroots = new File(HgInternals.getRepositoryDir(repo), "store/phaseroots"); try { if (!phaseroots.exists()) { return Boolean.FALSE; @@ -166,7 +126,7 @@ continue; } if (lc.length != 2) { - HgInternals.getContext(hgRepo).getLog().warn(getClass(), "Bad line in phaseroots:%s", line); + HgInternals.getContext(repo).getLog().warn(getClass(), "Bad line in phaseroots:%s", line); continue; } int phaseIndex = Integer.parseInt(lc[0]); @@ -193,15 +153,31 @@ } return Collections.emptyList(); } - - private int getEarliestPhaseRevision(HgPhase phase) throws HgInvalidControlFileException { + + + private RevisionDescendants[] getPhaseDescendants(HgPhase phase) throws HgInvalidControlFileException { int ordinal = phase.ordinal(); - if (earliestRevIndex[ordinal] == BAD_REVISION) { - int[] rootIndexes = toIndexes(getPhaseRoots(phase)); - Arrays.sort(rootIndexes); - // instead of MAX_VALUE may use clog.getLastRevision() + 1 - earliestRevIndex[ordinal] = rootIndexes.length == 0 ? Integer.MAX_VALUE : rootIndexes[0]; + if (phaseDescendants[ordinal] == null) { + phaseDescendants[ordinal] = buildPhaseDescendants(phase); } - return earliestRevIndex[ordinal]; + return phaseDescendants[ordinal]; + } + + private RevisionDescendants[] buildPhaseDescendants(HgPhase phase) throws HgInvalidControlFileException { + int[] roots = toIndexes(getPhaseRoots(phase)); + RevisionDescendants[] rv = new RevisionDescendants[roots.length]; + for (int i = 0; i < roots.length; i++) { + rv[i] = new RevisionDescendants(repo, roots[i]); + rv[i].build(); + } + return rv; + } + + private int[] toIndexes(List roots) throws HgInvalidControlFileException { + int[] rv = new int[roots.size()]; + for (int i = 0; i < rv.length; i++) { + rv[i] = repo.getChangelog().getRevisionIndex(roots.get(i)); + } + return rv; } } diff -r 2e402c12ebc6 -r 5787e912f60e src/org/tmatesoft/hg/internal/RevisionDescendants.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/tmatesoft/hg/internal/RevisionDescendants.java Thu Jun 07 16:01:09 2012 +0200 @@ -0,0 +1,101 @@ +/* + * Copyright (c) 2012 TMate Software Ltd + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * For information on how to redistribute this software under + * the terms of a license other than GNU General Public License + * contact TMate Software at support@hg4j.com + */ +package org.tmatesoft.hg.internal; + +import java.util.BitSet; + +import org.tmatesoft.hg.core.HgBadStateException; +import org.tmatesoft.hg.core.HgInvalidControlFileException; +import org.tmatesoft.hg.core.Nodeid; +import org.tmatesoft.hg.repo.HgChangelog; +import org.tmatesoft.hg.repo.HgRepository; + +/** + * Represent indicators which revisions are descendants of the supplied root revision + * This is sort of lightweight alternative to ParentWalker#childrenOf + * + * @author Artem Tikhomirov + * @author TMate Software Ltd. + */ +public class RevisionDescendants { + + private final HgRepository repo; + private final int rootRevIndex; + private final int tipRevIndex; // this is the last revision we cache to + private final BitSet descendants; + + // in fact, may be refactored to deal not only with changelog, but any revlog (not sure what would be the usecase, though) + public RevisionDescendants(HgRepository hgRepo, int revisionIndex) { + repo = hgRepo; + rootRevIndex = revisionIndex; + // even if tip moves, we still answer correctly for those isCandidate() + tipRevIndex = repo.getChangelog().getLastRevision(); + if (revisionIndex < 0 || revisionIndex > tipRevIndex) { + String m = "Revision to build descendants for shall be in range [%d,%d], not %d"; + throw new IllegalArgumentException(String.format(m, 0, tipRevIndex, revisionIndex)); + } + descendants = new BitSet(tipRevIndex - rootRevIndex + 1); + } + + public void build() throws HgInvalidControlFileException { + final BitSet result = descendants; + result.set(0); + repo.getChangelog().walk(rootRevIndex+1, tipRevIndex, new HgChangelog.ParentInspector() { + // TODO ParentRevisionInspector, with no parent nodeids, just indexes? + + private int i = 1; // above we start with revision next to rootRevIndex, which is at offset 0 + public void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2) { + int p1x = parent1 - rootRevIndex; + int p2x = parent2 - rootRevIndex; + boolean p1IsDescendant = false, p2IsDescendant = false; + if (p1x >= 0) { // parent1 is among descendants candidates + assert p1x < result.size(); + p1IsDescendant = result.get(p1x); + } + if (p2x >= 0) { + assert p2x < result.size(); + p2IsDescendant = result.get(p2x); + } + // + int rx = revisionIndex -rootRevIndex; + if (rx != i) { + throw new HgBadStateException(); + } + // current revision is descentand if any of its parents is descendant + result.set(rx, p1IsDescendant || p2IsDescendant); + i++; + } + }); + } + + // deliberately doesn't allow TIP + public boolean isCandidate(int revIndex) { + return (revIndex >= rootRevIndex && revIndex <= tipRevIndex) ; + } + + public boolean hasDescendants() { // isEmpty is better name? + // bit at rootRevIndex is always set + return descendants.nextSetBit(rootRevIndex+1) != -1; + } + + public boolean isDescendant(int revisionIndex) { + assert isCandidate(revisionIndex); + int ix = revisionIndex - rootRevIndex; + assert ix < descendants.size(); + return descendants.get(ix); + } +}