tikhomirov@181: /*
tikhomirov@181:  * Copyright (c) 2011 TMate Software Ltd
tikhomirov@181:  *  
tikhomirov@181:  * This program is free software; you can redistribute it and/or modify
tikhomirov@181:  * it under the terms of the GNU General Public License as published by
tikhomirov@181:  * the Free Software Foundation; version 2 of the License.
tikhomirov@181:  *
tikhomirov@181:  * This program is distributed in the hope that it will be useful,
tikhomirov@181:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@181:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@181:  * GNU General Public License for more details.
tikhomirov@181:  *
tikhomirov@181:  * For information on how to redistribute this software under
tikhomirov@181:  * the terms of a license other than GNU General Public License
tikhomirov@181:  * contact TMate Software at support@hg4j.com
tikhomirov@181:  */
tikhomirov@181: package org.tmatesoft.hg.internal;
tikhomirov@181: 
tikhomirov@181: import static org.tmatesoft.hg.core.Nodeid.NULL;
tikhomirov@181: 
tikhomirov@192: import java.util.ArrayList;
tikhomirov@181: import java.util.Collections;
tikhomirov@181: import java.util.HashMap;
tikhomirov@181: import java.util.HashSet;
tikhomirov@181: import java.util.LinkedList;
tikhomirov@181: import java.util.List;
tikhomirov@192: import java.util.ListIterator;
tikhomirov@181: import java.util.Map;
tikhomirov@181: import java.util.Map.Entry;
tikhomirov@202: import java.util.Set;
tikhomirov@181: 
tikhomirov@181: import org.tmatesoft.hg.core.HgBadStateException;
tikhomirov@181: import org.tmatesoft.hg.core.HgException;
tikhomirov@181: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@181: import org.tmatesoft.hg.repo.HgChangelog;
tikhomirov@181: import org.tmatesoft.hg.repo.HgRemoteRepository;
tikhomirov@181: import org.tmatesoft.hg.repo.HgRemoteRepository.Range;
tikhomirov@181: import org.tmatesoft.hg.repo.HgRemoteRepository.RemoteBranch;
tikhomirov@181: import org.tmatesoft.hg.util.CancelSupport;
tikhomirov@181: import org.tmatesoft.hg.util.CancelledException;
tikhomirov@181: import org.tmatesoft.hg.util.ProgressSupport;
tikhomirov@181: 
tikhomirov@181: /**
tikhomirov@181:  *
tikhomirov@181:  * @author Artem Tikhomirov
tikhomirov@181:  * @author TMate Software Ltd.
tikhomirov@181:  */
tikhomirov@181: public class RepositoryComparator {
tikhomirov@181: 
tikhomirov@181: 	private final HgChangelog.ParentWalker localRepo;
tikhomirov@181: 	private final HgRemoteRepository remoteRepo;
tikhomirov@181: 	private List<Nodeid> common;
tikhomirov@181: 
tikhomirov@181: 	public RepositoryComparator(HgChangelog.ParentWalker pwLocal, HgRemoteRepository hgRemote) {
tikhomirov@181: 		localRepo = pwLocal;
tikhomirov@181: 		remoteRepo = hgRemote;
tikhomirov@181: 	}
tikhomirov@181: 	
tikhomirov@181: 	public RepositoryComparator compare(Object context) throws HgException, CancelledException {
tikhomirov@181: 		ProgressSupport progressSupport = ProgressSupport.Factory.get(context);
tikhomirov@181: 		CancelSupport cancelSupport = CancelSupport.Factory.get(context);
tikhomirov@181: 		cancelSupport.checkCancelled();
tikhomirov@181: 		progressSupport.start(10);
tikhomirov@181: 		common = Collections.unmodifiableList(findCommonWithRemote());
tikhomirov@192: 		// sanity check
tikhomirov@192: 		for (Nodeid n : common) {
tikhomirov@192: 			if (!localRepo.knownNode(n)) {
tikhomirov@192: 				throw new HgBadStateException("Unknown node reported as common:" + n);
tikhomirov@192: 			}
tikhomirov@192: 		}
tikhomirov@181: 		progressSupport.done();
tikhomirov@181: 		return this;
tikhomirov@181: 	}
tikhomirov@181: 	
tikhomirov@181: 	public List<Nodeid> getCommon() {
tikhomirov@181: 		if (common == null) {
tikhomirov@181: 			throw new HgBadStateException("Call #compare(Object) first");
tikhomirov@181: 		}
tikhomirov@181: 		return common;
tikhomirov@181: 	}
tikhomirov@192: 	
tikhomirov@192: 	/**
tikhomirov@192: 	 * @return revisions that are children of common entries, i.e. revisions that are present on the local server and not on remote.
tikhomirov@192: 	 */
tikhomirov@192: 	public List<Nodeid> getLocalOnlyRevisions() {
tikhomirov@192: 		return localRepo.childrenOf(getCommon());
tikhomirov@192: 	}
tikhomirov@192: 	
tikhomirov@192: 	/**
tikhomirov@192: 	 * Similar to @link {@link #getLocalOnlyRevisions()}, use this one if you need access to changelog entry content, not 
tikhomirov@192: 	 * only its revision number. 
tikhomirov@192: 	 * @param inspector delegate to analyze changesets, shall not be <code>null</code>
tikhomirov@192: 	 */
tikhomirov@192: 	public void visitLocalOnlyRevisions(HgChangelog.Inspector inspector) {
tikhomirov@192: 		if (inspector == null) {
tikhomirov@192: 			throw new IllegalArgumentException();
tikhomirov@192: 		}
tikhomirov@192: 		// one can use localRepo.childrenOf(getCommon()) and then iterate over nodeids, but there seems to be
tikhomirov@192: 		// another approach to get all changes after common:
tikhomirov@192: 		// find index of earliest revision, and report all that were later
tikhomirov@192: 		final HgChangelog changelog = localRepo.getRepo().getChangelog();
tikhomirov@192: 		int earliestRevision = Integer.MAX_VALUE;
tikhomirov@192: 		List<Nodeid> commonKnown = getCommon();
tikhomirov@192: 		for (Nodeid n : commonKnown) {
tikhomirov@192: 			if (!localRepo.hasChildren(n)) {
tikhomirov@192: 				// there might be (old) nodes, known both locally and remotely, with no children
tikhomirov@192: 				// hence, we don't need to consider their local revision number
tikhomirov@192: 				continue;
tikhomirov@192: 			}
tikhomirov@192: 			int lr = changelog.getLocalRevision(n);
tikhomirov@192: 			if (lr < earliestRevision) {
tikhomirov@192: 				earliestRevision = lr;
tikhomirov@192: 			}
tikhomirov@192: 		}
tikhomirov@203: 		if (earliestRevision == Integer.MAX_VALUE) {
tikhomirov@203: 			// either there are no common nodes (known locally and at remote)
tikhomirov@203: 			// or no local children found (local is up to date). In former case, perhaps I shall bit return silently,
tikhomirov@203: 			// but check for possible wrong repo comparison (hs says 'repository is unrelated' if I try to 
tikhomirov@203: 			// check in/out for a repo that has no common nodes.
tikhomirov@203: 			return;
tikhomirov@203: 		}
tikhomirov@192: 		if (earliestRevision < 0 || earliestRevision >= changelog.getLastRevision()) {
tikhomirov@192: 			throw new HgBadStateException(String.format("Invalid index of common known revision: %d in total of %d", earliestRevision, 1+changelog.getLastRevision()));
tikhomirov@192: 		}
tikhomirov@192: 		changelog.range(earliestRevision+1, changelog.getLastRevision(), inspector);
tikhomirov@192: 	}
tikhomirov@181: 
tikhomirov@181: 	private List<Nodeid> findCommonWithRemote() throws HgException {
tikhomirov@181: 		List<Nodeid> remoteHeads = remoteRepo.heads();
tikhomirov@181: 		LinkedList<Nodeid> resultCommon = new LinkedList<Nodeid>(); // these remotes are known in local
tikhomirov@181: 		LinkedList<Nodeid> toQuery = new LinkedList<Nodeid>(); // these need further queries to find common
tikhomirov@181: 		for (Nodeid rh : remoteHeads) {
tikhomirov@181: 			if (localRepo.knownNode(rh)) {
tikhomirov@181: 				resultCommon.add(rh);
tikhomirov@181: 			} else {
tikhomirov@181: 				toQuery.add(rh);
tikhomirov@181: 			}
tikhomirov@181: 		}
tikhomirov@181: 		if (toQuery.isEmpty()) {
tikhomirov@181: 			return resultCommon; 
tikhomirov@181: 		}
tikhomirov@181: 		LinkedList<RemoteBranch> checkUp2Head = new LinkedList<RemoteBranch>(); // branch.root and branch.head are of interest only.
tikhomirov@181: 		// these are branches with unknown head but known root, which might not be the last common known,
tikhomirov@181: 		// i.e. there might be children changeset that are also available at remote, [..?..common-head..remote-head] - need to 
tikhomirov@181: 		// scroll up to common head.
tikhomirov@181: 		while (!toQuery.isEmpty()) {
tikhomirov@181: 			List<RemoteBranch> remoteBranches = remoteRepo.branches(toQuery);	//head, root, first parent, second parent
tikhomirov@181: 			toQuery.clear();
tikhomirov@181: 			while(!remoteBranches.isEmpty()) {
tikhomirov@181: 				RemoteBranch rb = remoteBranches.remove(0);
tikhomirov@181: 				// I assume branches remote call gives branches with head equal to what I pass there, i.e.
tikhomirov@181: 				// that I don't need to check whether rb.head is unknown.
tikhomirov@181: 				if (localRepo.knownNode(rb.root)) {
tikhomirov@181: 					// we known branch start, common head is somewhere in its descendants line  
tikhomirov@181: 					checkUp2Head.add(rb);
tikhomirov@181: 				} else {
tikhomirov@181: 					// dig deeper in the history, if necessary
tikhomirov@181: 					if (!NULL.equals(rb.p1) && !localRepo.knownNode(rb.p1)) {
tikhomirov@181: 						toQuery.add(rb.p1);
tikhomirov@181: 					}
tikhomirov@181: 					if (!NULL.equals(rb.p2) && !localRepo.knownNode(rb.p2)) {
tikhomirov@181: 						toQuery.add(rb.p2);
tikhomirov@181: 					}
tikhomirov@181: 				}
tikhomirov@181: 			}
tikhomirov@181: 		}
tikhomirov@181: 		// can't check nodes between checkUp2Head element and local heads, remote might have distinct descendants sequence
tikhomirov@181: 		for (RemoteBranch rb : checkUp2Head) {
tikhomirov@181: 			// rb.root is known locally
tikhomirov@181: 			List<Nodeid> remoteRevisions = remoteRepo.between(rb.head, rb.root);
tikhomirov@181: 			if (remoteRevisions.isEmpty()) {
tikhomirov@181: 				// head is immediate child
tikhomirov@181: 				resultCommon.add(rb.root);
tikhomirov@181: 			} else {
tikhomirov@181: 				// between gives result from head to root, I'd like to go in reverse direction
tikhomirov@181: 				Collections.reverse(remoteRevisions);
tikhomirov@181: 				Nodeid root = rb.root;
tikhomirov@181: 				while(!remoteRevisions.isEmpty()) {
tikhomirov@181: 					Nodeid n = remoteRevisions.remove(0);
tikhomirov@181: 					if (localRepo.knownNode(n)) {
tikhomirov@181: 						if (remoteRevisions.isEmpty()) {
tikhomirov@181: 							// this is the last known node before an unknown
tikhomirov@181: 							resultCommon.add(n);
tikhomirov@181: 							break;
tikhomirov@181: 						}
tikhomirov@181: 						if (remoteRevisions.size() == 1) {
tikhomirov@181: 							// there's only one left between known n and unknown head
tikhomirov@181: 							// this check is to save extra between query, not really essential
tikhomirov@181: 							Nodeid last = remoteRevisions.remove(0);
tikhomirov@181: 							resultCommon.add(localRepo.knownNode(last) ? last : n);
tikhomirov@181: 							break;
tikhomirov@181: 						}
tikhomirov@181: 						// might get handy for next between query, to narrow search down
tikhomirov@181: 						root = n;
tikhomirov@181: 					} else {
tikhomirov@181: 						remoteRevisions = remoteRepo.between(n, root);
tikhomirov@181: 						Collections.reverse(remoteRevisions);
tikhomirov@181: 						if (remoteRevisions.isEmpty()) {
tikhomirov@181: 							resultCommon.add(root);
tikhomirov@181: 						}
tikhomirov@181: 					}
tikhomirov@181: 				}
tikhomirov@181: 			}
tikhomirov@181: 		}
tikhomirov@181: 		// TODO ensure unique elements in the list
tikhomirov@181: 		return resultCommon;
tikhomirov@181: 	}
tikhomirov@181: 
tikhomirov@181: 	// somewhat similar to Outgoing.findCommonWithRemote() 
tikhomirov@181: 	public List<BranchChain> calculateMissingBranches() throws HgException {
tikhomirov@181: 		List<Nodeid> remoteHeads = remoteRepo.heads();
tikhomirov@181: 		LinkedList<Nodeid> common = new LinkedList<Nodeid>(); // these remotes are known in local
tikhomirov@181: 		LinkedList<Nodeid> toQuery = new LinkedList<Nodeid>(); // these need further queries to find common
tikhomirov@181: 		for (Nodeid rh : remoteHeads) {
tikhomirov@181: 			if (localRepo.knownNode(rh)) {
tikhomirov@181: 				common.add(rh);
tikhomirov@181: 			} else {
tikhomirov@181: 				toQuery.add(rh);
tikhomirov@181: 			}
tikhomirov@181: 		}
tikhomirov@181: 		if (toQuery.isEmpty()) {
tikhomirov@181: 			return Collections.emptyList(); // no incoming changes
tikhomirov@181: 		}
tikhomirov@181: 		LinkedList<BranchChain> branches2load = new LinkedList<BranchChain>(); // return value
tikhomirov@181: 		// detailed comments are in Outgoing.findCommonWithRemote
tikhomirov@181: 		LinkedList<RemoteBranch> checkUp2Head = new LinkedList<RemoteBranch>();
tikhomirov@181: 		// records relation between branch head and its parent branch, if any
tikhomirov@181: 		HashMap<Nodeid, BranchChain> head2chain = new HashMap<Nodeid, BranchChain>();
tikhomirov@181: 		while (!toQuery.isEmpty()) {
tikhomirov@181: 			List<RemoteBranch> remoteBranches = remoteRepo.branches(toQuery);	//head, root, first parent, second parent
tikhomirov@181: 			toQuery.clear();
tikhomirov@181: 			while(!remoteBranches.isEmpty()) {
tikhomirov@181: 				RemoteBranch rb = remoteBranches.remove(0);
tikhomirov@181: 				BranchChain chainElement = head2chain.get(rb.head);
tikhomirov@181: 				if (chainElement == null) {
tikhomirov@181: 					chainElement = new BranchChain(rb.head);
tikhomirov@181: 					// record this unknown branch to download later
tikhomirov@181: 					branches2load.add(chainElement);
tikhomirov@184: 					// the only chance we'll need chainElement in the head2chain is when we know this branch's root 
tikhomirov@184: 					head2chain.put(rb.head, chainElement);
tikhomirov@181: 				}
tikhomirov@181: 				if (localRepo.knownNode(rb.root)) {
tikhomirov@181: 					// we known branch start, common head is somewhere in its descendants line  
tikhomirov@181: 					checkUp2Head.add(rb);
tikhomirov@181: 				} else {
tikhomirov@181: 					chainElement.branchRoot = rb.root;
tikhomirov@181: 					// dig deeper in the history, if necessary
tikhomirov@202: 					boolean hasP1 = !NULL.equals(rb.p1), hasP2 = !NULL.equals(rb.p2);  
tikhomirov@202: 					if (hasP1 && !localRepo.knownNode(rb.p1)) {
tikhomirov@181: 						toQuery.add(rb.p1);
tikhomirov@181: 						head2chain.put(rb.p1, chainElement.p1 = new BranchChain(rb.p1));
tikhomirov@181: 					}
tikhomirov@202: 					if (hasP2 && !localRepo.knownNode(rb.p2)) {
tikhomirov@181: 						toQuery.add(rb.p2);
tikhomirov@181: 						head2chain.put(rb.p2, chainElement.p2 = new BranchChain(rb.p2));
tikhomirov@181: 					}
tikhomirov@202: 					if (!hasP1 && !hasP2) {
tikhomirov@202: 						// special case, when we do incoming against blank repository, chainElement.branchRoot
tikhomirov@202: 						// is first unknown element (revision 0). We need to add another fake BranchChain
tikhomirov@202: 						// to fill the promise that terminal BranchChain has branchRoot that is known both locally and remotely
tikhomirov@202: 						BranchChain fake = new BranchChain(NULL);
tikhomirov@202: 						fake.branchRoot = NULL;
tikhomirov@202: 						chainElement.p1 = chainElement.p2 = fake;
tikhomirov@202: 					}
tikhomirov@181: 				}
tikhomirov@181: 			}
tikhomirov@181: 		}
tikhomirov@181: 		for (RemoteBranch rb : checkUp2Head) {
tikhomirov@181: 			Nodeid h = rb.head;
tikhomirov@181: 			Nodeid r = rb.root;
tikhomirov@181: 			int watchdog = 1000;
tikhomirov@184: 			assert head2chain.containsKey(h);
tikhomirov@181: 			BranchChain bc = head2chain.get(h);
tikhomirov@184: 			assert bc != null : h.toString();
tikhomirov@181: 			// if we know branch root locally, there could be no parent branch chain elements.
tikhomirov@181: 			assert bc.p1 == null;
tikhomirov@181: 			assert bc.p2 == null;
tikhomirov@181: 			do {
tikhomirov@181: 				List<Nodeid> between = remoteRepo.between(h, r);
tikhomirov@181: 				if (between.isEmpty()) {
tikhomirov@181: 					bc.branchRoot = r;
tikhomirov@181: 					break;
tikhomirov@181: 				} else {
tikhomirov@181: 					Collections.reverse(between);
tikhomirov@181: 					for (Nodeid n : between) {
tikhomirov@181: 						if (localRepo.knownNode(n)) {
tikhomirov@181: 							r = n;
tikhomirov@181: 						} else {
tikhomirov@181: 							h = n;
tikhomirov@181: 							break;
tikhomirov@181: 						}
tikhomirov@181: 					}
tikhomirov@181: 					Nodeid lastInBetween = between.get(between.size() - 1);
tikhomirov@181: 					if (r.equals(lastInBetween)) {
tikhomirov@181: 						bc.branchRoot = r;
tikhomirov@181: 						break;
tikhomirov@181: 					} else if (h.equals(lastInBetween)) { // the only chance for current head pointer to point to the sequence tail
tikhomirov@181: 						// is when r is second from the between list end (iow, head,1,[2],4,8...,root)
tikhomirov@181: 						bc.branchRoot = r;
tikhomirov@181: 						break;
tikhomirov@181: 					}
tikhomirov@181: 				}
tikhomirov@181: 			} while(--watchdog > 0);
tikhomirov@181: 			if (watchdog == 0) {
tikhomirov@181: 				throw new HgBadStateException(String.format("Can't narrow down branch [%s, %s]", rb.head.shortNotation(), rb.root.shortNotation()));
tikhomirov@181: 			}
tikhomirov@181: 		}
tikhomirov@181: 		return branches2load;
tikhomirov@181: 	}
tikhomirov@181: 
tikhomirov@202: 	// root and head (and all between) are unknown for each chain element but last (terminal), which has known root (revision
tikhomirov@202: 	// known to be locally and at remote server
tikhomirov@202: 	// alternative would be to keep only unknown elements (so that promise of calculateMissingBranches would be 100% true), but that 
tikhomirov@202: 	// seems to complicate the method, while being useful only for the case when we ask incoming for an empty repository (i.e.
tikhomirov@202: 	// where branch chain return all nodes, -1..tip.
tikhomirov@181: 	public static final class BranchChain {
tikhomirov@181: 		// when we construct a chain, we know head which is missing locally, hence init it right away.
tikhomirov@181: 		// as for root (branch unknown start), we might happen to have one locally, and need further digging to find out right branch start  
tikhomirov@181: 		public final Nodeid branchHead;
tikhomirov@181: 		public Nodeid branchRoot;
tikhomirov@181: 		// either of these can be null, or both.
tikhomirov@181: 		// although RemoteBranch has either both parents null, or both non-null, when we construct a chain
tikhomirov@181: 		// we might encounter that we locally know one of branch's parent, hence in the chain corresponding field will be blank.
tikhomirov@181: 		public BranchChain p1;
tikhomirov@181: 		public BranchChain p2;
tikhomirov@181: 
tikhomirov@181: 		public BranchChain(Nodeid head) {
tikhomirov@181: 			assert head != null;
tikhomirov@181: 			branchHead = head;
tikhomirov@181: 		}
tikhomirov@181: 		public boolean isTerminal() {
tikhomirov@202: 			return p1 == null && p2 == null; // either can be null, see comment above. Terminal is only when no way to descent
tikhomirov@181: 		}
tikhomirov@181: 		
tikhomirov@202: 		// true when this BranchChain is a branch that spans up to very start of the repository
tikhomirov@202: 		// Thus, the only common revision is NULL, recorded in a fake BranchChain object shared between p1 and p2
tikhomirov@202: 		/*package-local*/ boolean isRepoStart() {
tikhomirov@202: 			return p1 == p2 && p1 != null && p1.branchHead == p1.branchRoot && NULL.equals(p1.branchHead);
tikhomirov@202: 		}
tikhomirov@202: 
tikhomirov@181: 		@Override
tikhomirov@181: 		public String toString() {
tikhomirov@181: 			return String.format("BranchChain [%s, %s]", branchRoot, branchHead);
tikhomirov@181: 		}
tikhomirov@181: 
tikhomirov@181: 		public void dump() {
tikhomirov@181: 			System.out.println(toString());
tikhomirov@181: 			internalDump("  ");
tikhomirov@181: 		}
tikhomirov@181: 
tikhomirov@181: 		private void internalDump(String prefix) {
tikhomirov@181: 			if (p1 != null) {
tikhomirov@181: 				System.out.println(prefix + p1.toString());
tikhomirov@181: 			}
tikhomirov@181: 			if (p2 != null) {
tikhomirov@181: 				System.out.println(prefix + p2.toString());
tikhomirov@181: 			}
tikhomirov@181: 			prefix += "  ";
tikhomirov@181: 			if (p1 != null) {
tikhomirov@181: 				p1.internalDump(prefix);
tikhomirov@181: 			}
tikhomirov@181: 			if (p2 != null) {
tikhomirov@181: 				p2.internalDump(prefix);
tikhomirov@181: 			}
tikhomirov@181: 		}
tikhomirov@181: 	}
tikhomirov@181: 
tikhomirov@181: 	/**
tikhomirov@181: 	 * @return list of nodeids from branchRoot to branchHead, inclusive. IOW, first element of the list is always root of the branch 
tikhomirov@181: 	 */
tikhomirov@181: 	public List<Nodeid> completeBranch(final Nodeid branchRoot, final Nodeid branchHead) throws HgException {
tikhomirov@181: 		class DataEntry {
tikhomirov@181: 			public final Nodeid queryHead;
tikhomirov@181: 			public final int headIndex;
tikhomirov@181: 			public List<Nodeid> entries;
tikhomirov@181: 
tikhomirov@181: 			public DataEntry(Nodeid head, int index, List<Nodeid> data) {
tikhomirov@181: 				queryHead = head;
tikhomirov@181: 				headIndex = index;
tikhomirov@181: 				entries = data;
tikhomirov@181: 			}
tikhomirov@181: 		};
tikhomirov@181: 
tikhomirov@181: 		List<Nodeid> initial = remoteRepo.between(branchHead, branchRoot);
tikhomirov@181: 		Nodeid[] result = new Nodeid[1 + (1 << initial.size())];
tikhomirov@181: 		result[0] = branchHead;
tikhomirov@181: 		int rootIndex = -1; // index in the result, where to place branche's root.
tikhomirov@181: 		if (initial.isEmpty()) {
tikhomirov@181: 			rootIndex = 1;
tikhomirov@181: 		} else if (initial.size() == 1) {
tikhomirov@181: 			rootIndex = 2;
tikhomirov@181: 		}
tikhomirov@181: 		LinkedList<DataEntry> datas = new LinkedList<DataEntry>();
tikhomirov@181: 		// DataEntry in datas has entries list filled with 'between' data, whereas 
tikhomirov@181: 		// DataEntry in toQuery keeps only nodeid and its index, with entries to be initialized before 
tikhomirov@181: 		// moving to datas. 
tikhomirov@181: 		LinkedList<DataEntry> toQuery = new LinkedList<DataEntry>();
tikhomirov@181: 		//
tikhomirov@181: 		datas.add(new DataEntry(branchHead, 0, initial));
tikhomirov@181: 		int totalQueries = 1;
tikhomirov@181: 		HashSet<Nodeid> queried = new HashSet<Nodeid>();
tikhomirov@181: 		while(!datas.isEmpty()) {
tikhomirov@181: 			// keep record of those planned to be queried next time we call between()
tikhomirov@181: 			// although may keep these in queried, if really don't want separate collection
tikhomirov@181: 			HashSet<Nodeid> scheduled = new HashSet<Nodeid>();  
tikhomirov@181: 			do {
tikhomirov@181: 				DataEntry de = datas.removeFirst();
tikhomirov@181: 				// populate result with discovered elements between de.qiueryRoot and branch's head
tikhomirov@181: 				for (int i = 1, j = 0; j < de.entries.size(); i = i << 1, j++) {
tikhomirov@181: 					int idx = de.headIndex + i;
tikhomirov@181: 					result[idx] = de.entries.get(j);
tikhomirov@181: 				}
tikhomirov@181: 				// form next query entries from new unknown elements
tikhomirov@181: 				if (de.entries.size() > 1) {
tikhomirov@181: 					/* when entries has only one element, it means de.queryRoot was at head-2 position, and thus
tikhomirov@181: 					 * no new information can be obtained. E.g. when it's 2, it might be case of [0..4] query with
tikhomirov@181: 					 * [1,2] result, and we need one more query to get element 3.   
tikhomirov@181: 					 */
tikhomirov@181: 					for (int i =1, j = 0; j < de.entries.size(); i = i<<1, j++) {
tikhomirov@181: 						int idx = de.headIndex + i;
tikhomirov@181: 						Nodeid x = de.entries.get(j);
tikhomirov@181: 						if (!queried.contains(x) && !scheduled.contains(x) && (rootIndex == -1 || rootIndex - de.headIndex > 1)) {
tikhomirov@181: 							/*queries for elements right before head is senseless, but unless we know head's index, do it anyway*/
tikhomirov@181: 							toQuery.add(new DataEntry(x, idx, null));
tikhomirov@181: 							scheduled.add(x);
tikhomirov@181: 						}
tikhomirov@181: 					}
tikhomirov@181: 				}
tikhomirov@181: 			} while (!datas.isEmpty());
tikhomirov@181: 			if (!toQuery.isEmpty()) {
tikhomirov@181: 				totalQueries++;
tikhomirov@181: 			}
tikhomirov@181: 			// for each query, create an between request range, keep record Range->DataEntry to know range's start index  
tikhomirov@181: 			LinkedList<HgRemoteRepository.Range> betweenBatch = new LinkedList<HgRemoteRepository.Range>();
tikhomirov@181: 			HashMap<HgRemoteRepository.Range, DataEntry> rangeToEntry = new HashMap<HgRemoteRepository.Range, DataEntry>();
tikhomirov@181: 			for (DataEntry de : toQuery) {
tikhomirov@181: 				queried.add(de.queryHead);
tikhomirov@181: 				HgRemoteRepository.Range r = new HgRemoteRepository.Range(branchRoot, de.queryHead);
tikhomirov@181: 				betweenBatch.add(r);
tikhomirov@181: 				rangeToEntry.put(r, de);
tikhomirov@181: 			}
tikhomirov@181: 			if (!betweenBatch.isEmpty()) {
tikhomirov@181: 				Map<Range, List<Nodeid>> between = remoteRepo.between(betweenBatch);
tikhomirov@181: 				for (Entry<Range, List<Nodeid>> e : between.entrySet()) {
tikhomirov@181: 					DataEntry de = rangeToEntry.get(e.getKey());
tikhomirov@181: 					assert de != null;
tikhomirov@181: 					de.entries = e.getValue();
tikhomirov@181: 					if (rootIndex == -1 && de.entries.size() == 1) {
tikhomirov@181: 						// returned sequence of length 1 means we used element from [head-2] as root
tikhomirov@181: 						int numberOfElementsExcludingRootAndHead = de.headIndex + 1;
tikhomirov@181: 						rootIndex = numberOfElementsExcludingRootAndHead + 1;
tikhomirov@181: 						System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, numberOfElementsExcludingRootAndHead);
tikhomirov@181: 					}
tikhomirov@181: 					datas.add(de); // queue up to record result and construct further requests
tikhomirov@181: 				}
tikhomirov@181: 				betweenBatch.clear();
tikhomirov@181: 				rangeToEntry.clear();
tikhomirov@181: 			}
tikhomirov@181: 			toQuery.clear();
tikhomirov@181: 		}
tikhomirov@181: 		if (rootIndex == -1) {
tikhomirov@181: 			throw new HgBadStateException("Shall not happen, provided between output is correct"); // FIXME
tikhomirov@181: 		}
tikhomirov@181: 		result[rootIndex] = branchRoot;
tikhomirov@181: 		boolean resultOk = true;
tikhomirov@181: 		LinkedList<Nodeid> fromRootToHead = new LinkedList<Nodeid>();
tikhomirov@181: 		for (int i = 0; i <= rootIndex; i++) {
tikhomirov@181: 			Nodeid n = result[i];
tikhomirov@181: 			if (n == null) {
tikhomirov@181: 				System.out.printf("ERROR: element %d wasn't found\n",i);
tikhomirov@181: 				resultOk = false;
tikhomirov@181: 			}
tikhomirov@181: 			fromRootToHead.addFirst(n); // reverse order
tikhomirov@181: 		}
tikhomirov@181: 		System.out.println("Total queries:" + totalQueries);
tikhomirov@181: 		if (!resultOk) {
tikhomirov@181: 			throw new HgBadStateException("See console for details"); // FIXME
tikhomirov@181: 		}
tikhomirov@181: 		return fromRootToHead;
tikhomirov@181: 	}
tikhomirov@192: 
tikhomirov@192: 	/**
tikhomirov@192: 	 *  returns in order from branch root to head
tikhomirov@192: 	 *  for a non-empty BranchChain, shall return modifiable list
tikhomirov@192: 	 */
tikhomirov@192: 	public List<Nodeid> visitBranches(BranchChain bc) throws HgException {
tikhomirov@192: 		if (bc == null) {
tikhomirov@192: 			return Collections.emptyList();
tikhomirov@192: 		}
tikhomirov@192: 		List<Nodeid> mine = completeBranch(bc.branchRoot, bc.branchHead);
tikhomirov@202: 		if (bc.isTerminal() || bc.isRepoStart()) {
tikhomirov@192: 			return mine;
tikhomirov@192: 		}
tikhomirov@192: 		List<Nodeid> parentBranch1 = visitBranches(bc.p1);
tikhomirov@192: 		List<Nodeid> parentBranch2 = visitBranches(bc.p2);
tikhomirov@192: 		// merge
tikhomirov@192: 		LinkedList<Nodeid> merged = new LinkedList<Nodeid>();
tikhomirov@192: 		ListIterator<Nodeid> i1 = parentBranch1.listIterator(), i2 = parentBranch2.listIterator();
tikhomirov@192: 		while (i1.hasNext() && i2.hasNext()) {
tikhomirov@192: 			Nodeid n1 = i1.next();
tikhomirov@192: 			Nodeid n2 = i2.next();
tikhomirov@192: 			if (n1.equals(n2)) {
tikhomirov@192: 				merged.addLast(n1);
tikhomirov@192: 			} else {
tikhomirov@192: 				// first different => add both, and continue adding both tails sequentially 
tikhomirov@192: 				merged.add(n2);
tikhomirov@192: 				merged.add(n1);
tikhomirov@192: 				break;
tikhomirov@192: 			}
tikhomirov@192: 		}
tikhomirov@192: 		// copy rest of second parent branch
tikhomirov@192: 		while (i2.hasNext()) {
tikhomirov@192: 			merged.add(i2.next());
tikhomirov@192: 		}
tikhomirov@192: 		// copy rest of first parent branch
tikhomirov@192: 		while (i1.hasNext()) {
tikhomirov@192: 			merged.add(i1.next());
tikhomirov@192: 		}
tikhomirov@192: 		//
tikhomirov@192: 		ArrayList<Nodeid> rv = new ArrayList<Nodeid>(mine.size() + merged.size());
tikhomirov@192: 		rv.addAll(merged);
tikhomirov@192: 		rv.addAll(mine);
tikhomirov@192: 		return rv;
tikhomirov@192: 	}
tikhomirov@192: 
tikhomirov@202: 	public void collectKnownRoots(BranchChain bc, Set<Nodeid> result) {
tikhomirov@202: 		if (bc == null) {
tikhomirov@202: 			return;
tikhomirov@202: 		}
tikhomirov@202: 		if (bc.isTerminal()) {
tikhomirov@202: 			result.add(bc.branchRoot);
tikhomirov@202: 			return;
tikhomirov@202: 		}
tikhomirov@202: 		if (bc.isRepoStart()) {
tikhomirov@202: 			return;
tikhomirov@202: 		}
tikhomirov@202: 		collectKnownRoots(bc.p1, result);
tikhomirov@202: 		collectKnownRoots(bc.p2, result);
tikhomirov@202: 	}
tikhomirov@181: }