# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1302046456 -7200
# Node ID 62665d8f06861e5d1ac46a28259560001316a91f
# Parent  e10225dafacede3af3759a0b39daa10626ae80ea
Complete logic to discover all branches missing locally. Most of wire protocol in HgRemoteRepository

diff -r e10225daface -r 62665d8f0686 cmdline/org/tmatesoft/hg/console/Incoming.java
--- a/cmdline/org/tmatesoft/hg/console/Incoming.java	Sat Apr 02 23:05:28 2011 +0200
+++ b/cmdline/org/tmatesoft/hg/console/Incoming.java	Wed Apr 06 01:34:16 2011 +0200
@@ -20,6 +20,7 @@
 
 import java.io.File;
 import java.net.URL;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
@@ -29,6 +30,7 @@
 import java.util.LinkedHashMap;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.ListIterator;
 import java.util.Map;
 import java.util.Map.Entry;
 
@@ -79,37 +81,202 @@
 		final HgChangelog.ParentWalker pw = hgRepo.getChangelog().new ParentWalker();
 		pw.init();
 		//
-		List<RemoteBranch> missingBranches = calculateMissingBranches(hgRepo, hgRemote);
-		LinkedList<Nodeid> missing = new LinkedList<Nodeid>();
-		for (RemoteBranch rb : missingBranches) {
-			List<Nodeid> completeBranch = completeBranch(hgRemote, rb);
-			// FIXME ensure topologically sorted result
-			missing.addAll(completeBranch);
+		List<BranchChain> missingBranches0 = calculateMissingBranches(pw, hgRemote);
+		for (BranchChain bc : missingBranches0) {
+			bc.dump();
+			
+			List<Nodeid> missing = visitBranches(hgRemote, bc);
+			// Collections.reverse(missing); // useful to test output, from newer to older
+			for (Nodeid n : missing) {
+				if (pw.knownNode(n)) {
+					System.out.println("Erroneous to fetch:" + n);
+				} else {
+					System.out.println(n);
+				}
+			}
+			System.out.println("Branch done");
 		}
-		// Collections.reverse(missing); // useful to test output, from newer to older
-		for (Nodeid n : missing) {
-			if (pw.knownNode(n)) {
-				System.out.println("Erroneous to fetch:" + n);
-			} else {
-				System.out.println(n);
+		
+	}
+	
+	private static class BranchChain {
+		// when we construct a chain, we know head which is missing locally, hence init it right away.
+		// as for root (branch unknown start), we might happen to have one locally, and need further digging to find out right branch start  
+		public final Nodeid branchHead;
+		public Nodeid branchRoot;
+		// either of these can be null, or both.
+		// although RemoteBranch has either both parents null, or both non-null, when we construct a chain
+		// we might encounter that we locally know one of branch's parent, hence in the chain corresponding field will be blank.
+		public BranchChain p1;
+		public BranchChain p2;
+
+		public BranchChain(Nodeid head) {
+			assert head != null;
+			branchHead = head;
+		}
+		public boolean isTerminal() {
+			return p1 == null || p2 == null;
+		}
+		
+		@Override
+		public String toString() {
+			return String.format("BranchChain [%s, %s]", branchRoot, branchHead);
+		}
+		void dump() {
+			System.out.println(toString());
+			internalDump("  ");
+		}
+		void internalDump(String prefix) {
+			if (p1 != null) {
+				System.out.println(prefix + p1.toString());
+			}
+			if (p2 != null) {
+				System.out.println(prefix + p2.toString());
+			}
+			prefix += "  ";
+			if (p1 != null) {
+				p1.internalDump(prefix);
+			}
+			if (p2 != null) {
+				p2.internalDump(prefix);
 			}
 		}
 	}
 	
-	private static List<RemoteBranch> calculateMissingBranches(HgRepository hgRepo, HgRemoteRepository hgRemote) {
-		// FIXME implement
+	private static List<Nodeid> visitBranches(HgRemoteRepository hgRemote, BranchChain bc) throws HgException {
+		if (bc == null) {
+			return Collections.emptyList();
+		}
+		List<Nodeid> mine = completeBranch(hgRemote, bc.branchRoot, bc.branchHead);
+		if (bc.isTerminal()) {
+			return mine;
+		}
+		List<Nodeid> parentBranch1 = visitBranches(hgRemote, bc.p1);
+		List<Nodeid> parentBranch2 = visitBranches(hgRemote, bc.p2);
+		// merge
+		LinkedList<Nodeid> merged = new LinkedList<Nodeid>();
+		ListIterator<Nodeid> i1 = parentBranch1.listIterator(), i2 = parentBranch2.listIterator();
+		while (i1.hasNext() && i2.hasNext()) {
+			Nodeid n1 = i1.next();
+			Nodeid n2 = i2.next();
+			if (n1.equals(n2)) {
+				merged.addLast(n1);
+			} else {
+				// first different => add both, and continue adding both tails sequentially 
+				merged.add(n2);
+				merged.add(n1);
+				break;
+			}
+		}
+		// copy rest of second parent branch
+		while (i2.hasNext()) {
+			merged.add(i2.next());
+		}
+		// copy rest of first parent branch
+		while (i1.hasNext()) {
+			merged.add(i1.next());
+		}
 		//
-		// sample 0..52
-		Nodeid head = Nodeid.fromAscii("30bd389788464287cee22ccff54c330a4b715de5");
-		Nodeid root = Nodeid.fromAscii("dbd663faec1f0175619cf7668bddc6350548b8d6");
-		Nodeid p1 = NULL, p2 = NULL;
-		RemoteBranch fake = new RemoteBranch(head, root, p1, p2);
-		return Collections.singletonList(fake);
+		ArrayList<Nodeid> rv = new ArrayList<Nodeid>(mine.size() + merged.size());
+		rv.addAll(merged);
+		rv.addAll(mine);
+		return rv;
+	}
+	
+	// somewhat similar to Outgoing.findCommonWithRemote() 
+	private static List<BranchChain> calculateMissingBranches(HgChangelog.ParentWalker pwLocal, HgRemoteRepository hgRemote) throws HgException {
+		List<Nodeid> remoteHeads = hgRemote.heads();
+		LinkedList<Nodeid> common = new LinkedList<Nodeid>(); // these remotes are known in local
+		LinkedList<Nodeid> toQuery = new LinkedList<Nodeid>(); // these need further queries to find common
+		for (Nodeid rh : remoteHeads) {
+			if (pwLocal.knownNode(rh)) {
+				common.add(rh);
+			} else {
+				toQuery.add(rh);
+			}
+		}
+		if (toQuery.isEmpty()) {
+			return Collections.emptyList(); // no incoming changes
+		}
+		LinkedList<BranchChain> branches2load = new LinkedList<BranchChain>(); // return value
+		// detailed comments are in Outgoing.findCommonWithRemote
+		LinkedList<RemoteBranch> checkUp2Head = new LinkedList<RemoteBranch>();
+		// records relation between branch head and its parent branch, if any
+		HashMap<Nodeid, BranchChain> head2chain = new HashMap<Nodeid, Incoming.BranchChain>();
+		while (!toQuery.isEmpty()) {
+			List<RemoteBranch> remoteBranches = hgRemote.branches(toQuery);	//head, root, first parent, second parent
+			toQuery.clear();
+			while(!remoteBranches.isEmpty()) {
+				RemoteBranch rb = remoteBranches.remove(0);
+				BranchChain chainElement = head2chain.get(rb.head);
+				if (chainElement == null) {
+					chainElement = new BranchChain(rb.head);
+					// record this unknown branch to download later
+					branches2load.add(chainElement);
+				}
+				if (pwLocal.knownNode(rb.root)) {
+					// we known branch start, common head is somewhere in its descendants line  
+					checkUp2Head.add(rb);
+				} else {
+					chainElement.branchRoot = rb.root;
+					// dig deeper in the history, if necessary
+					if (!NULL.equals(rb.p1) && !pwLocal.knownNode(rb.p1)) {
+						toQuery.add(rb.p1);
+						head2chain.put(rb.p1, chainElement.p1 = new BranchChain(rb.p1));
+					}
+					if (!NULL.equals(rb.p2) && !pwLocal.knownNode(rb.p2)) {
+						toQuery.add(rb.p2);
+						head2chain.put(rb.p2, chainElement.p2 = new BranchChain(rb.p2));
+					}
+				}
+			}
+		}
+		for (RemoteBranch rb : checkUp2Head) {
+			Nodeid h = rb.head;
+			Nodeid r = rb.root;
+			int watchdog = 1000;
+			BranchChain bc = head2chain.get(h);
+			assert bc != null;
+			// if we know branch root locally, there could be no parent branch chain elements.
+			assert bc.p1 == null;
+			assert bc.p2 == null;
+			do {
+				List<Nodeid> between = hgRemote.between(h, r);
+				if (between.isEmpty()) {
+					bc.branchRoot = r;
+					break;
+				} else {
+					Collections.reverse(between);
+					for (Nodeid n : between) {
+						if (pwLocal.knownNode(n)) {
+							r = n;
+						} else {
+							h = n;
+							break;
+						}
+					}
+					Nodeid lastInBetween = between.get(between.size() - 1);
+					if (r.equals(lastInBetween)) {
+						bc.branchRoot = r;
+						break;
+					} else if (h.equals(lastInBetween)) { // the only chance for current head pointer to point to the sequence tail
+						// is when r is second from the between list end (iow, head,1,[2],4,8...,root)
+						bc.branchRoot = r;
+						break;
+					}
+				}
+			} while(--watchdog > 0);
+			if (watchdog == 0) {
+				throw new HgBadStateException(String.format("Can't narrow down branch [%s, %s]", rb.head.shortNotation(), rb.root.shortNotation()));
+			}
+		}
+		return branches2load;
 	}
 
-	// RemoteBranch not necessarily a 'true' remote branch. I use this structure to keep root, head, and root's parents, any
-	// of them can be known locally, parent might be only one (when I split 'true' RemoteBranch in between because of locally known node 
-	private static List<Nodeid> completeBranch(HgRemoteRepository hgRemote, RemoteBranch rb) throws HgException {
+	/**
+	 * @return list of nodeids from branchRoot to branchHead, inclusive. IOW, first element of the list is always root of the branch 
+	 */
+	private static List<Nodeid> completeBranch(HgRemoteRepository hgRemote, final Nodeid branchRoot, final Nodeid branchHead) throws HgException {
 		class DataEntry {
 			public final Nodeid queryHead;
 			public final int headIndex;
@@ -122,17 +289,22 @@
 			}
 		};
 
-		List<Nodeid> initial = hgRemote.between(rb.head, rb.root);
-		Nodeid[] result = new Nodeid[1 << initial.size()];
-		result[0] = rb.head;
+		List<Nodeid> initial = hgRemote.between(branchHead, branchRoot);
+		Nodeid[] result = new Nodeid[1 + (1 << initial.size())];
+		result[0] = branchHead;
 		int rootIndex = -1; // index in the result, where to place branche's root.
+		if (initial.isEmpty()) {
+			rootIndex = 1;
+		} else if (initial.size() == 1) {
+			rootIndex = 2;
+		}
 		LinkedList<DataEntry> datas = new LinkedList<DataEntry>();
 		// DataEntry in datas has entries list filled with 'between' data, whereas 
 		// DataEntry in toQuery keeps only nodeid and its index, with entries to be initialized before 
 		// moving to datas. 
 		LinkedList<DataEntry> toQuery = new LinkedList<DataEntry>();
 		//
-		datas.add(new DataEntry(rb.head, 0, initial));
+		datas.add(new DataEntry(branchHead, 0, initial));
 		int totalQueries = 1;
 		HashSet<Nodeid> queried = new HashSet<Nodeid>();
 		while(!datas.isEmpty()) {
@@ -171,7 +343,7 @@
 			HashMap<HgRemoteRepository.Range, DataEntry> rangeToEntry = new HashMap<HgRemoteRepository.Range, DataEntry>();
 			for (DataEntry de : toQuery) {
 				queried.add(de.queryHead);
-				HgRemoteRepository.Range r = new HgRemoteRepository.Range(rb.root, de.queryHead);
+				HgRemoteRepository.Range r = new HgRemoteRepository.Range(branchRoot, de.queryHead);
 				betweenBatch.add(r);
 				rangeToEntry.put(r, de);
 			}
@@ -197,7 +369,7 @@
 		if (rootIndex == -1) {
 			throw new HgBadStateException("Shall not happen, provided between output is correct"); // FIXME
 		}
-		result[rootIndex] = rb.root;
+		result[rootIndex] = branchRoot;
 		boolean resultOk = true;
 		LinkedList<Nodeid> fromRootToHead = new LinkedList<Nodeid>();
 		for (int i = 0; i <= rootIndex; i++) {
diff -r e10225daface -r 62665d8f0686 cmdline/org/tmatesoft/hg/console/Outgoing.java
--- a/cmdline/org/tmatesoft/hg/console/Outgoing.java	Sat Apr 02 23:05:28 2011 +0200
+++ b/cmdline/org/tmatesoft/hg/console/Outgoing.java	Wed Apr 06 01:34:16 2011 +0200
@@ -120,12 +120,12 @@
 		for (RemoteBranch rb : checkUp2Head) {
 			// rb.root is known locally
 			List<Nodeid> remoteRevisions = hgRemote.between(rb.head, rb.root);
-				// between gives result from head to root, I'd like to go in reverse direction
-			Collections.reverse(remoteRevisions);
 			if (remoteRevisions.isEmpty()) {
 				// head is immediate child
 				common.add(rb.root);
 			} else {
+				// between gives result from head to root, I'd like to go in reverse direction
+				Collections.reverse(remoteRevisions);
 				Nodeid root = rb.root;
 				while(!remoteRevisions.isEmpty()) {
 					Nodeid n = remoteRevisions.remove(0);
diff -r e10225daface -r 62665d8f0686 cmdline/org/tmatesoft/hg/console/Remote.java
--- a/cmdline/org/tmatesoft/hg/console/Remote.java	Sat Apr 02 23:05:28 2011 +0200
+++ b/cmdline/org/tmatesoft/hg/console/Remote.java	Wed Apr 06 01:34:16 2011 +0200
@@ -125,7 +125,7 @@
 		urlConnection.setRequestProperty("Accept", "application/mercurial-0.1");
 		urlConnection.setRequestProperty("Authorization", "Basic " + authInfo);
 		urlConnection.setSSLSocketFactory(sslContext.getSocketFactory());
-		byte[] body = "pairs=30bd389788464287cee22ccff54c330a4b715de5-dbd663faec1f0175619cf7668bddc6350548b8d6".getBytes();
+		byte[] body = "pairs=f5aed108754e817d2ca374d1a4f6daf1218dcc91-9429c7bd1920fab164a9d2b621d38d57bcb49ae0".getBytes();
 		urlConnection.setRequestMethod("POST");
 		urlConnection.setRequestProperty("Content-Length", String.valueOf(body.length));
 		urlConnection.setRequestProperty("Content-Type", "application/x-www-form-urlencoded");
diff -r e10225daface -r 62665d8f0686 src/org/tmatesoft/hg/repo/HgRemoteRepository.java
--- a/src/org/tmatesoft/hg/repo/HgRemoteRepository.java	Sat Apr 02 23:05:28 2011 +0200
+++ b/src/org/tmatesoft/hg/repo/HgRemoteRepository.java	Wed Apr 06 01:34:16 2011 +0200
@@ -27,6 +27,7 @@
 import java.net.URLConnection;
 import java.security.cert.CertificateException;
 import java.security.cert.X509Certificate;
+import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Iterator;
@@ -59,6 +60,7 @@
 	private final URL url;
 	private final SSLContext sslContext;
 	private final String authInfo;
+	private final boolean debug = Boolean.FALSE.booleanValue();
 
 	HgRemoteRepository(URL url) throws HgException {
 		if (url == null) {
@@ -104,9 +106,29 @@
 		}
 	}
 	
-	public List<Nodeid> heads() {
-		return Collections.singletonList(Nodeid.fromAscii("71ddbf8603e8e09d54ac9c5fe4bb5ae824589f1d"));
-//		return Collections.emptyList();
+	public List<Nodeid> heads() throws HgException {
+		try {
+			URL u = new URL(url, url.getPath() + "?cmd=heads");
+			HttpURLConnection c = setupConnection(u.openConnection());
+			c.connect();
+			if (debug) {
+				dumpResponseHeader(u, c);
+			}
+			InputStreamReader is = new InputStreamReader(c.getInputStream(), "US-ASCII");
+			StreamTokenizer st = new StreamTokenizer(is);
+			st.ordinaryChars('0', '9');
+			st.wordChars('0', '9');
+			st.eolIsSignificant(false);
+			LinkedList<Nodeid> parseResult = new LinkedList<Nodeid>();
+			while (st.nextToken() != StreamTokenizer.TT_EOF) {
+				parseResult.add(Nodeid.fromAscii(st.sval));
+			}
+			return parseResult;
+		} catch (MalformedURLException ex) {
+			throw new HgException(ex);
+		} catch (IOException ex) {
+			throw new HgException(ex);
+		}
 	}
 	
 	public List<Nodeid> between(Nodeid tip, Nodeid base) throws HgException {
@@ -155,12 +177,9 @@
 			} else {
 				c.connect();
 			}
-			System.out.printf("%d ranges, method:%s \n", ranges.size(), c.getRequestMethod());
-			System.out.printf("Query (%d bytes):%s\n", u.getQuery().length(), u.getQuery());
-			System.out.println("Response headers:");
-			final Map<String, List<String>> headerFields = c.getHeaderFields();
-			for (String s : headerFields.keySet()) {
-				System.out.printf("%s: %s\n", s, c.getHeaderField(s));
+			if (debug) {
+				System.out.printf("%d ranges, method:%s \n", ranges.size(), c.getRequestMethod());
+				dumpResponseHeader(u, c);
 			}
 			InputStreamReader is = new InputStreamReader(c.getInputStream(), "US-ASCII");
 			StreamTokenizer st = new StreamTokenizer(is);
@@ -213,8 +232,47 @@
 		}
 	}
 
-	public List<RemoteBranch> branches(List<Nodeid> nodes) {
-		return Collections.emptyList();
+	public List<RemoteBranch> branches(List<Nodeid> nodes) throws HgException {
+		StringBuilder sb = new StringBuilder(20 + nodes.size() * 41);
+		sb.append("nodes=");
+		for (Nodeid n : nodes) {
+			sb.append(n.toString());
+			sb.append('+');
+		}
+		if (sb.charAt(sb.length() - 1) == '+') {
+			// strip last space 
+			sb.setLength(sb.length() - 1);
+		}
+		try {
+			URL u = new URL(url, url.getPath() + "?cmd=branches&" + sb.toString());
+			HttpURLConnection c = setupConnection(u.openConnection());
+			c.connect();
+			if (debug) {
+				dumpResponseHeader(u, c);
+			}
+			InputStreamReader is = new InputStreamReader(c.getInputStream(), "US-ASCII");
+			StreamTokenizer st = new StreamTokenizer(is);
+			st.ordinaryChars('0', '9');
+			st.wordChars('0', '9');
+			st.eolIsSignificant(false);
+			ArrayList<Nodeid> parseResult = new ArrayList<Nodeid>(nodes.size() * 4);
+			while (st.nextToken() != StreamTokenizer.TT_EOF) {
+				parseResult.add(Nodeid.fromAscii(st.sval));
+			}
+			if (parseResult.size() != nodes.size() * 4) {
+				throw new HgException(String.format("Bad number of nodeids in result (shall be factor 4), expected %d, got %d", nodes.size()*4, parseResult.size()));
+			}
+			ArrayList<RemoteBranch> rv = new ArrayList<RemoteBranch>(nodes.size());
+			for (int i = 0; i < nodes.size(); i++) {
+				RemoteBranch rb = new RemoteBranch(parseResult.get(i*4), parseResult.get(i*4 + 1), parseResult.get(i*4 + 2), parseResult.get(i*4 + 3));
+				rv.add(rb);
+			}
+			return rv;
+		} catch (MalformedURLException ex) {
+			throw new HgException(ex);
+		} catch (IOException ex) {
+			throw new HgException(ex);
+		}
 	}
 
 	// WireProtocol wiki: roots = a list of the latest nodes on every service side changeset branch that both the client and server know about. 
@@ -234,6 +292,15 @@
 		return (HttpURLConnection) urlConnection;
 	}
 
+	private void dumpResponseHeader(URL u, HttpURLConnection c) {
+		System.out.printf("Query (%d bytes):%s\n", u.getQuery().length(), u.getQuery());
+		System.out.println("Response headers:");
+		final Map<String, List<String>> headerFields = c.getHeaderFields();
+		for (String s : headerFields.keySet()) {
+			System.out.printf("%s: %s\n", s, c.getHeaderField(s));
+		}
+	}
+
 	public static final class Range {
 		/**
 		 * Root of the range, earlier revision