tikhomirov@449: /*
tikhomirov@628:  * Copyright (c) 2012-2013 TMate Software Ltd
tikhomirov@449:  *  
tikhomirov@449:  * This program is free software; you can redistribute it and/or modify
tikhomirov@449:  * it under the terms of the GNU General Public License as published by
tikhomirov@449:  * the Free Software Foundation; version 2 of the License.
tikhomirov@449:  *
tikhomirov@449:  * This program is distributed in the hope that it will be useful,
tikhomirov@449:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@449:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@449:  * GNU General Public License for more details.
tikhomirov@449:  *
tikhomirov@449:  * For information on how to redistribute this software under
tikhomirov@449:  * the terms of a license other than GNU General Public License
tikhomirov@449:  * contact TMate Software at support@hg4j.com
tikhomirov@449:  */
tikhomirov@449: package org.tmatesoft.hg.internal;
tikhomirov@449: 
tikhomirov@648: import java.util.ArrayList;
tikhomirov@449: import java.util.BitSet;
tikhomirov@449: 
tikhomirov@449: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@449: import org.tmatesoft.hg.repo.HgChangelog;
tikhomirov@471: import org.tmatesoft.hg.repo.HgInvalidStateException;
tikhomirov@449: import org.tmatesoft.hg.repo.HgRepository;
tikhomirov@628: import org.tmatesoft.hg.repo.HgRuntimeException;
tikhomirov@449: 
tikhomirov@449: /**
tikhomirov@449:  * Represent indicators which revisions are descendants of the supplied root revision
tikhomirov@449:  * This is sort of lightweight alternative to ParentWalker#childrenOf 
tikhomirov@449:  * 
tikhomirov@449:  * @author Artem Tikhomirov
tikhomirov@449:  * @author TMate Software Ltd.
tikhomirov@449:  */
tikhomirov@449: public class RevisionDescendants {
tikhomirov@449: 
tikhomirov@449: 	private final HgRepository repo;
tikhomirov@449: 	private final int rootRevIndex;
tikhomirov@449: 	private final int tipRevIndex; // this is the last revision we cache to
tikhomirov@449: 	private final BitSet descendants;
tikhomirov@648: 	private RevisionSet revset;
tikhomirov@449: 
tikhomirov@449: 	// in fact, may be refactored to deal not only with changelog, but any revlog (not sure what would be the usecase, though)
tikhomirov@628: 	public RevisionDescendants(HgRepository hgRepo, int revisionIndex) throws HgRuntimeException {
tikhomirov@449: 		repo = hgRepo;
tikhomirov@449: 		rootRevIndex = revisionIndex;
tikhomirov@449: 		// even if tip moves, we still answer correctly for those isCandidate()
tikhomirov@449: 		tipRevIndex = repo.getChangelog().getLastRevision(); 
tikhomirov@449: 		if (revisionIndex < 0 || revisionIndex > tipRevIndex) {
tikhomirov@449: 			String m = "Revision to build descendants for shall be in range [%d,%d], not %d";
tikhomirov@449: 			throw new IllegalArgumentException(String.format(m, 0, tipRevIndex, revisionIndex));
tikhomirov@449: 		}
tikhomirov@449: 		descendants = new BitSet(tipRevIndex - rootRevIndex + 1);
tikhomirov@449: 	}
tikhomirov@449: 	
tikhomirov@628: 	public void build() throws HgRuntimeException {
tikhomirov@449: 		final BitSet result = descendants;
tikhomirov@449: 		result.set(0);
tikhomirov@450: 		if (rootRevIndex == tipRevIndex) {
tikhomirov@450: 			return;
tikhomirov@450: 		}
tikhomirov@471: 		repo.getChangelog().indexWalk(rootRevIndex+1, tipRevIndex, new HgChangelog.ParentInspector() {
tikhomirov@449: 			// TODO ParentRevisionInspector, with no parent nodeids, just indexes?
tikhomirov@449: 
tikhomirov@449: 			private int i = 1; // above we start with revision next to rootRevIndex, which is at offset 0
tikhomirov@449: 			public void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2) {
tikhomirov@449: 				int p1x = parent1 - rootRevIndex;
tikhomirov@449: 				int p2x = parent2 - rootRevIndex;
tikhomirov@449: 				boolean p1IsDescendant = false, p2IsDescendant = false;
tikhomirov@449: 				if (p1x >= 0) { // parent1 is among descendants candidates
tikhomirov@449: 					assert p1x < result.size();
tikhomirov@449: 					p1IsDescendant = result.get(p1x);
tikhomirov@449: 				}
tikhomirov@449: 				if (p2x >= 0) {
tikhomirov@449: 					assert p2x < result.size();
tikhomirov@449: 					p2IsDescendant = result.get(p2x);
tikhomirov@449: 				}
tikhomirov@449: 				//
tikhomirov@471: 				int rx = revisionIndex - rootRevIndex;
tikhomirov@449: 				if (rx != i) {
tikhomirov@471: 					throw new HgInvalidStateException(String.format("Sanity check failed. Revision %d. Expected:%d, was:%d", revisionIndex, rx, i));
tikhomirov@449: 				}
tikhomirov@471: 				// current revision is descendant if any of its parents is descendant
tikhomirov@449: 				result.set(rx, p1IsDescendant || p2IsDescendant);
tikhomirov@449: 				i++;
tikhomirov@449: 			}
tikhomirov@449: 		});
tikhomirov@449: 	}
tikhomirov@449: 
tikhomirov@449: 	// deliberately doesn't allow TIP
tikhomirov@449: 	public boolean isCandidate(int revIndex) {
tikhomirov@449: 		return (revIndex >= rootRevIndex && revIndex <= tipRevIndex) ;
tikhomirov@449: 	}
tikhomirov@449: 
tikhomirov@449: 	public boolean hasDescendants() { // isEmpty is better name?
tikhomirov@449: 		// bit at rootRevIndex is always set
tikhomirov@449: 		return descendants.nextSetBit(rootRevIndex+1) != -1;
tikhomirov@449: 	}
tikhomirov@449: 
tikhomirov@472: 	/**
tikhomirov@472: 	 * Tells whether specified revision is on a descent line from the root revision.
tikhomirov@472: 	 * <p>NOTE, root revision itself is considered to be its own descendant.
tikhomirov@472: 	 * 
tikhomirov@472: 	 * @param revisionIndex revision index to check, shall pass {@link #isCandidate(int)}
tikhomirov@472: 	 * @return <code>true</code> if revision is descendant of or is the same as root revision
tikhomirov@472: 	 */
tikhomirov@449: 	public boolean isDescendant(int revisionIndex) {
tikhomirov@449: 		assert isCandidate(revisionIndex);
tikhomirov@449: 		int ix = revisionIndex - rootRevIndex;
tikhomirov@449: 		assert ix < descendants.size();
tikhomirov@449: 		return descendants.get(ix);
tikhomirov@449: 	}
tikhomirov@648: 
tikhomirov@648: 	public RevisionSet asRevisionSet() {
tikhomirov@648: 		if (revset == null) {
tikhomirov@648: 			final ArrayList<Nodeid> revisions = new ArrayList<Nodeid>(descendants.cardinality());
tikhomirov@648: 			repo.getChangelog().indexWalk(rootRevIndex, tipRevIndex, new HgChangelog.RevisionInspector() {
tikhomirov@648: 
tikhomirov@648: 				public void next(int revisionIndex, Nodeid revision, int linkedRevisionIndex) throws HgRuntimeException {
tikhomirov@648: 					if (isDescendant(revisionIndex)) {
tikhomirov@648: 						revisions.add(revision);
tikhomirov@648: 					}
tikhomirov@648: 				}
tikhomirov@648: 			});
tikhomirov@648: 			assert revisions.size() == descendants.cardinality();
tikhomirov@648: 			revset = new RevisionSet(revisions);
tikhomirov@648: 		}
tikhomirov@648: 		return revset;
tikhomirov@648: 	}
tikhomirov@449: }