tikhomirov@181: /* tikhomirov@628: * Copyright (c) 2011-2013 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@423: import java.util.Arrays; 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@215: import org.tmatesoft.hg.core.HgRemoteConnectionException; tikhomirov@181: import org.tmatesoft.hg.core.Nodeid; tikhomirov@181: import org.tmatesoft.hg.repo.HgChangelog; tikhomirov@423: import org.tmatesoft.hg.repo.HgInvalidStateException; tikhomirov@628: import org.tmatesoft.hg.repo.HgParentChildMap; 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@628: import org.tmatesoft.hg.repo.HgRuntimeException; 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@206: private final boolean debug = Boolean.parseBoolean(System.getProperty("hg4j.remote.debug")); tikhomirov@432: private final HgParentChildMap localRepo; tikhomirov@181: private final HgRemoteRepository remoteRepo; tikhomirov@181: private List common; tikhomirov@645: private List remoteHeads; tikhomirov@181: tikhomirov@432: public RepositoryComparator(HgParentChildMap pwLocal, HgRemoteRepository hgRemote) { tikhomirov@181: localRepo = pwLocal; tikhomirov@181: remoteRepo = hgRemote; tikhomirov@181: } tikhomirov@181: tikhomirov@215: public RepositoryComparator compare(ProgressSupport progressSupport, CancelSupport cancelSupport) throws HgRemoteConnectionException, CancelledException { 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@423: throw new HgInvalidStateException("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 getCommon() { tikhomirov@181: if (common == null) { tikhomirov@423: throw new HgInvalidStateException("Call #compare(Object) first"); tikhomirov@181: } tikhomirov@181: return common; tikhomirov@181: } tikhomirov@192: tikhomirov@645: public List getRemoteHeads() { tikhomirov@645: assert remoteHeads != null; tikhomirov@645: return remoteHeads; tikhomirov@645: } tikhomirov@645: 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 getLocalOnlyRevisions() { tikhomirov@645: final List c = getCommon(); tikhomirov@645: if (c.isEmpty()) { tikhomirov@645: return localRepo.all(); tikhomirov@645: } else { tikhomirov@652: RevisionSet localHeads = new RevisionSet(localRepo.heads()); tikhomirov@652: final List commonChildren = localRepo.childrenOf(c); tikhomirov@652: final RevisionSet rsCommonChildren = new RevisionSet(commonChildren); tikhomirov@652: RevisionSet headsNotFromCommon = localHeads.subtract(rsCommonChildren); tikhomirov@652: if (headsNotFromCommon.isEmpty()) { tikhomirov@652: return commonChildren; tikhomirov@652: } tikhomirov@652: RevisionSet all = new RevisionSet(localRepo.all()); tikhomirov@652: final RevisionSet rsCommon = new RevisionSet(c); tikhomirov@652: RevisionSet rsAncestors = all.ancestors(headsNotFromCommon, localRepo); tikhomirov@652: // #ancestors gives only parents, we need terminating children as well tikhomirov@652: rsAncestors = rsAncestors.union(headsNotFromCommon); tikhomirov@652: final RevisionSet rsAncestorsCommon = all.ancestors(rsCommon, localRepo); tikhomirov@652: RevisionSet outgoing = rsAncestors.subtract(rsAncestorsCommon).subtract(rsCommon); tikhomirov@652: return outgoing.union(rsCommonChildren).asList(); tikhomirov@645: } 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 null tikhomirov@192: */ tikhomirov@628: public void visitLocalOnlyRevisions(HgChangelog.Inspector inspector) throws HgRuntimeException { 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 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@367: int lr = changelog.getRevisionIndex(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@423: throw new HgInvalidStateException(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@215: private List findCommonWithRemote() throws HgRemoteConnectionException { tikhomirov@645: remoteHeads = remoteRepo.heads(); tikhomirov@181: LinkedList resultCommon = new LinkedList(); // these remotes are known in local tikhomirov@181: LinkedList toQuery = new LinkedList(); // 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 checkUp2Head = new LinkedList(); // 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 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@274: if (!rb.p1.isNull() && !localRepo.knownNode(rb.p1)) { tikhomirov@181: toQuery.add(rb.p1); tikhomirov@181: } tikhomirov@274: if (!rb.p2.isNull() && !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 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@215: public List calculateMissingBranches() throws HgRemoteConnectionException { tikhomirov@181: List remoteHeads = remoteRepo.heads(); tikhomirov@181: LinkedList common = new LinkedList(); // these remotes are known in local tikhomirov@181: LinkedList toQuery = new LinkedList(); // 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 branches2load = new LinkedList(); // return value tikhomirov@181: // detailed comments are in Outgoing.findCommonWithRemote tikhomirov@181: LinkedList checkUp2Head = new LinkedList(); tikhomirov@181: // records relation between branch head and its parent branch, if any tikhomirov@181: HashMap head2chain = new HashMap(); tikhomirov@181: while (!toQuery.isEmpty()) { tikhomirov@181: List 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@274: boolean hasP1 = !rb.p1.isNull(), hasP2 = !rb.p2.isNull(); tikhomirov@202: if (hasP1 && !localRepo.knownNode(rb.p1)) { tikhomirov@181: toQuery.add(rb.p1); tikhomirov@209: // we might have seen parent node already, and recorded it as a branch chain tikhomirov@209: // we shall reuse existing BC to get it completely initializer (head2chain map tikhomirov@209: // on second put with the same key would leave first BC uninitialized. tikhomirov@209: tikhomirov@209: // It seems there's no reason to be affraid (XXX although shall double-check) tikhomirov@209: // that BC's chain would get corrupt (its p1 and p2 fields assigned twice with different values) tikhomirov@209: // as parents are always the same (and likely, BC that is common would be the last unknown) tikhomirov@209: BranchChain bc = head2chain.get(rb.p1); tikhomirov@209: if (bc == null) { tikhomirov@209: head2chain.put(rb.p1, bc = new BranchChain(rb.p1)); tikhomirov@209: } tikhomirov@210: chainElement.p1 = bc; tikhomirov@181: } tikhomirov@202: if (hasP2 && !localRepo.knownNode(rb.p2)) { tikhomirov@181: toQuery.add(rb.p2); tikhomirov@209: BranchChain bc = head2chain.get(rb.p2); tikhomirov@209: if (bc == null) { tikhomirov@209: head2chain.put(rb.p2, bc = new BranchChain(rb.p2)); tikhomirov@209: } tikhomirov@209: chainElement.p2 = bc; 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 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@423: throw new HgInvalidStateException(String.format("Can't narrow down branch [%s, %s]", rb.head.shortNotation(), rb.root.shortNotation())); tikhomirov@181: } tikhomirov@181: } tikhomirov@206: if (debug) { tikhomirov@207: System.out.println("calculateMissingBranches:"); tikhomirov@206: for (BranchChain bc : branches2load) { tikhomirov@206: bc.dump(); tikhomirov@206: } tikhomirov@206: } 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@274: return p1 == p2 && p1 != null && p1.branchHead == p1.branchRoot && p1.branchHead.isNull(); 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@206: 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@210: } else if (p2 != null) { tikhomirov@210: System.out.println(prefix + "NONE?!"); tikhomirov@181: } tikhomirov@181: if (p2 != null) { tikhomirov@181: System.out.println(prefix + p2.toString()); tikhomirov@210: } else if (p1 != null) { tikhomirov@210: System.out.println(prefix + "NONE?!"); 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@295: public List completeBranch(final Nodeid branchRoot, final Nodeid branchHead) throws HgRemoteConnectionException { tikhomirov@181: class DataEntry { tikhomirov@181: public final Nodeid queryHead; tikhomirov@181: public final int headIndex; tikhomirov@181: public List entries; tikhomirov@181: tikhomirov@181: public DataEntry(Nodeid head, int index, List data) { tikhomirov@181: queryHead = head; tikhomirov@181: headIndex = index; tikhomirov@181: entries = data; tikhomirov@181: } tikhomirov@181: }; tikhomirov@181: tikhomirov@181: List 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 datas = new LinkedList(); 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 toQuery = new LinkedList(); tikhomirov@181: // tikhomirov@181: datas.add(new DataEntry(branchHead, 0, initial)); tikhomirov@181: int totalQueries = 1; tikhomirov@181: HashSet queried = new HashSet(); 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 scheduled = new HashSet(); 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 betweenBatch = new LinkedList(); tikhomirov@181: HashMap rangeToEntry = new HashMap(); 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> between = remoteRepo.between(betweenBatch); tikhomirov@181: for (Entry> 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@207: if (debug) { tikhomirov@207: System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, numberOfElementsExcludingRootAndHead); tikhomirov@207: } 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@425: throw new HgInvalidStateException("Shall not happen, provided between output is correct"); tikhomirov@181: } tikhomirov@181: result[rootIndex] = branchRoot; tikhomirov@181: boolean resultOk = true; tikhomirov@181: LinkedList fromRootToHead = new LinkedList(); tikhomirov@423: IntVector missing = new IntVector(); tikhomirov@181: for (int i = 0; i <= rootIndex; i++) { tikhomirov@181: Nodeid n = result[i]; tikhomirov@181: if (n == null) { tikhomirov@423: missing.add(i); tikhomirov@181: resultOk = false; tikhomirov@181: } tikhomirov@181: fromRootToHead.addFirst(n); // reverse order tikhomirov@181: } tikhomirov@207: if (debug) { tikhomirov@207: System.out.println("Total queries:" + totalQueries); tikhomirov@207: } tikhomirov@181: if (!resultOk) { tikhomirov@423: assert missing.size() > 0; tikhomirov@423: // TODO post-1.0 perhaps, there's better alternative than HgInvalidStateException, e.g. HgDataFormatException? tikhomirov@423: throw new HgInvalidStateException(String.format("Missing elements with indexes: %s", Arrays.toString(missing.toArray()))); 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@295: public List visitBranches(BranchChain bc) throws HgRemoteConnectionException { tikhomirov@192: if (bc == null) { tikhomirov@192: return Collections.emptyList(); tikhomirov@192: } tikhomirov@192: List mine = completeBranch(bc.branchRoot, bc.branchHead); tikhomirov@202: if (bc.isTerminal() || bc.isRepoStart()) { tikhomirov@192: return mine; tikhomirov@192: } tikhomirov@192: List parentBranch1 = visitBranches(bc.p1); tikhomirov@192: List parentBranch2 = visitBranches(bc.p2); tikhomirov@192: // merge tikhomirov@192: LinkedList merged = new LinkedList(); tikhomirov@192: ListIterator 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 rv = new ArrayList(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 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: }