--- 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]);
 		}
 	}
 

--- 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<Nodeid> draftPhaseRoots;
 	private List<Nodeid> 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<Nodeid> parents2consider = new HashSet<Nodeid>(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<Nodeid> 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<Nodeid> 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;
 	}
 }

--- /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);
+	}
+}