tikhomirov@31: /*
tikhomirov@74:  * Copyright (c) 2011 TMate Software Ltd
tikhomirov@74:  *  
tikhomirov@74:  * This program is free software; you can redistribute it and/or modify
tikhomirov@74:  * it under the terms of the GNU General Public License as published by
tikhomirov@74:  * the Free Software Foundation; version 2 of the License.
tikhomirov@74:  *
tikhomirov@74:  * This program is distributed in the hope that it will be useful,
tikhomirov@74:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@74:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@74:  * GNU General Public License for more details.
tikhomirov@74:  *
tikhomirov@74:  * For information on how to redistribute this software under
tikhomirov@74:  * the terms of a license other than GNU General Public License
tikhomirov@102:  * contact TMate Software at support@hg4j.com
tikhomirov@31:  */
tikhomirov@74: package org.tmatesoft.hg.console;
tikhomirov@31: 
tikhomirov@171: import static org.tmatesoft.hg.core.Nodeid.NULL;
tikhomirov@171: 
tikhomirov@176: import java.io.File;
tikhomirov@176: import java.net.URL;
tikhomirov@173: import java.util.Arrays;
tikhomirov@173: import java.util.Collections;
tikhomirov@173: import java.util.Comparator;
tikhomirov@31: import java.util.HashSet;
tikhomirov@173: import java.util.Iterator;
tikhomirov@173: import java.util.LinkedHashMap;
tikhomirov@31: import java.util.LinkedList;
tikhomirov@31: import java.util.List;
tikhomirov@173: import java.util.Map.Entry;
tikhomirov@173: 
tikhomirov@176: import org.tmatesoft.hg.core.HgBadStateException;
tikhomirov@176: import org.tmatesoft.hg.core.HgException;
tikhomirov@74: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@176: import org.tmatesoft.hg.internal.ConfigFile;
tikhomirov@176: import org.tmatesoft.hg.internal.Internals;
tikhomirov@97: import org.tmatesoft.hg.repo.HgChangelog;
tikhomirov@176: import org.tmatesoft.hg.repo.HgLookup;
tikhomirov@176: import org.tmatesoft.hg.repo.HgRemoteRepository;
tikhomirov@171: import org.tmatesoft.hg.repo.HgRemoteRepository.RemoteBranch;
tikhomirov@74: import org.tmatesoft.hg.repo.HgRepository;
tikhomirov@74: 
tikhomirov@31: 
tikhomirov@31: /**
tikhomirov@74:  * WORK IN PROGRESS, DO NOT USE
tikhomirov@173:  * hg incoming counterpart
tikhomirov@74:  * 
tikhomirov@74:  * @author Artem Tikhomirov
tikhomirov@74:  * @author TMate Software Ltd.
tikhomirov@31:  */
tikhomirov@31: public class Incoming {
tikhomirov@31: 
tikhomirov@31: 	public static void main(String[] args) throws Exception {
tikhomirov@176: 		if (Boolean.FALSE.booleanValue()) {
tikhomirov@173: 			new SequenceConstructor().test();
tikhomirov@173: 			return;
tikhomirov@173: 		}
tikhomirov@74: 		Options cmdLineOpts = Options.parse(args);
tikhomirov@74: 		HgRepository hgRepo = cmdLineOpts.findRepository();
tikhomirov@31: 		if (hgRepo.isInvalid()) {
tikhomirov@31: 			System.err.printf("Can't find repository in: %s\n", hgRepo.getLocation());
tikhomirov@31: 			return;
tikhomirov@31: 		}
tikhomirov@176: 		String key = "svnkit";
tikhomirov@176: 		ConfigFile cfg = new Internals().newConfigFile();
tikhomirov@176: 		cfg.addLocation(new File(System.getProperty("user.home"), ".hgrc"));
tikhomirov@176: 		String server = cfg.getSection("paths").get(key);
tikhomirov@176: 		if (server == null) {
tikhomirov@176: 			throw new HgException(String.format("Can't find server %s specification in the config", key));
tikhomirov@176: 		}
tikhomirov@176: 		HgRemoteRepository hgRemote = new HgLookup().detect(new URL(server));
tikhomirov@176: 		//
tikhomirov@31: 		// in fact, all we need from changelog is set of all nodeids. However, since ParentWalker reuses same Nodeids, it's not too expensive
tikhomirov@31: 		// to reuse it here, XXX although later this may need to be refactored
tikhomirov@98: 		final HgChangelog.ParentWalker pw = hgRepo.getChangelog().new ParentWalker();
tikhomirov@31: 		pw.init();
tikhomirov@31: 		//
tikhomirov@176: 		List<RemoteBranch> missingBranches = calculateMissingBranches(hgRepo, hgRemote);
tikhomirov@176: 		LinkedList<Nodeid> missing = new LinkedList<Nodeid>();
tikhomirov@176: 		for (RemoteBranch rb : missingBranches) {
tikhomirov@176: 			List<Nodeid> completeBranch = completeBranch(hgRemote, rb);
tikhomirov@176: 			// FIXME ensure topologically sorted result
tikhomirov@176: 			missing.addAll(completeBranch);
tikhomirov@31: 		}
tikhomirov@176: 		// Collections.reverse(missing); // useful to test output, from newer to older
tikhomirov@176: 		for (Nodeid n : missing) {
tikhomirov@31: 			if (pw.knownNode(n)) {
tikhomirov@31: 				System.out.println("Erroneous to fetch:" + n);
tikhomirov@31: 			} else {
tikhomirov@31: 				System.out.println(n);
tikhomirov@31: 			}
tikhomirov@31: 		}
tikhomirov@31: 	}
tikhomirov@176: 	
tikhomirov@176: 	private static List<RemoteBranch> calculateMissingBranches(HgRepository hgRepo, HgRemoteRepository hgRemote) {
tikhomirov@176: 		// FIXME implement
tikhomirov@31: 		//
tikhomirov@176: 		// sample 0..52
tikhomirov@176: 		Nodeid head = Nodeid.fromAscii("30bd389788464287cee22ccff54c330a4b715de5");
tikhomirov@176: 		Nodeid root = Nodeid.fromAscii("dbd663faec1f0175619cf7668bddc6350548b8d6");
tikhomirov@176: 		Nodeid p1 = NULL, p2 = NULL;
tikhomirov@176: 		RemoteBranch fake = new RemoteBranch(head, root, p1, p2);
tikhomirov@176: 		return Collections.singletonList(fake);
tikhomirov@31: 	}
tikhomirov@31: 
tikhomirov@176: 	// RemoteBranch not necessarily a 'true' remote branch. I use this structure to keep root, head, and root's parents, any
tikhomirov@176: 	// of them can be known locally, parent might be only one (when I split 'true' RemoteBranch in between because of locally known node 
tikhomirov@176: 	private static List<Nodeid> completeBranch(HgRemoteRepository hgRemote, RemoteBranch rb) throws HgException {
tikhomirov@176: 		class DataEntry {
tikhomirov@176: 			public final Nodeid queryHead;
tikhomirov@176: 			public final int headIndex;
tikhomirov@176: 			public List<Nodeid> entries;
tikhomirov@31: 
tikhomirov@176: 			public DataEntry(Nodeid head, int index, List<Nodeid> data) {
tikhomirov@176: 				queryHead = head;
tikhomirov@176: 				headIndex = index;
tikhomirov@176: 				entries = data;
tikhomirov@176: 			}
tikhomirov@176: 		};
tikhomirov@176: 
tikhomirov@176: 		List<Nodeid> initial = hgRemote.between(rb.head, rb.root);
tikhomirov@176: 		Nodeid[] result = new Nodeid[1 << initial.size()];
tikhomirov@176: 		result[0] = rb.head;
tikhomirov@176: 		int rootIndex = -1; // index in the result, where to place branche's root.
tikhomirov@176: 		LinkedList<DataEntry> datas = new LinkedList<DataEntry>();
tikhomirov@176: 		// DataEntry in datas has entries list filled with 'between' data, whereas 
tikhomirov@176: 		// DataEntry in toQuery keeps only nodeid and its index, with entries to be initialized before 
tikhomirov@176: 		// moving to datas. 
tikhomirov@176: 		LinkedList<DataEntry> toQuery = new LinkedList<DataEntry>();
tikhomirov@176: 		//
tikhomirov@176: 		datas.add(new DataEntry(rb.head, 0, initial));
tikhomirov@176: 		int totalQueries = 1;
tikhomirov@176: 		HashSet<Nodeid> queried = new HashSet<Nodeid>();
tikhomirov@176: 		while(!datas.isEmpty()) {
tikhomirov@176: 			do {
tikhomirov@176: 				DataEntry de = datas.removeFirst();
tikhomirov@176: 				// populate result with discovered elements between de.qiueryRoot and branch's head
tikhomirov@176: 				for (int i = 1, j = 0; j < de.entries.size(); i = i << 1, j++) {
tikhomirov@176: 					int idx = de.headIndex + i;
tikhomirov@176: 					result[idx] = de.entries.get(j);
tikhomirov@176: 				}
tikhomirov@176: 				// form next query entries from new unknown elements
tikhomirov@176: 				if (de.entries.size() > 1) {
tikhomirov@176: 					/* when entries has only one element, it means de.queryRoot was at head-2 position, and thus
tikhomirov@176: 					 * no new information can be obtained. E.g. when it's 2, it might be case of [0..4] query with
tikhomirov@176: 					 * [1,2] result, and we need one more query to get element 3.   
tikhomirov@176: 					 */
tikhomirov@176: 					for (int i =1, j = 0; j < de.entries.size(); i = i<<1, j++) {
tikhomirov@176: 						int idx = de.headIndex + i;
tikhomirov@176: 						Nodeid x = de.entries.get(j);
tikhomirov@176: 						if (!queried.contains(x) && (rootIndex == -1 || rootIndex - de.headIndex > 1)) {
tikhomirov@176: 							/*queries for elements right before head is senseless, but unless we know head's index, do it anyway*/
tikhomirov@176: 							toQuery.add(new DataEntry(x, idx, null));
tikhomirov@176: 						}
tikhomirov@176: 					}
tikhomirov@176: 				}
tikhomirov@176: 			} while (!datas.isEmpty());
tikhomirov@176: 			if (!toQuery.isEmpty()) {
tikhomirov@176: 				totalQueries++;
tikhomirov@176: 			}
tikhomirov@176: 			for (DataEntry de : toQuery) {
tikhomirov@176: 				if (!queried.contains(de.queryHead)) {
tikhomirov@176: 					queried.add(de.queryHead);
tikhomirov@176: 					List<Nodeid> between = hgRemote.between(de.queryHead, rb.root);
tikhomirov@176: 					if (rootIndex == -1 && between.size() == 1) {
tikhomirov@176: 						// returned sequence of length 1 means we used element from [head-2] as root
tikhomirov@176: 						int numberOfElementsExcludingRootAndHead = de.headIndex + 1;
tikhomirov@176: 						rootIndex = numberOfElementsExcludingRootAndHead + 1;
tikhomirov@176: 						System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, numberOfElementsExcludingRootAndHead);
tikhomirov@176: 					}
tikhomirov@176: 					de.entries = between;
tikhomirov@176: 					datas.add(de); // queue up to record result and construct further requests
tikhomirov@176: 				}
tikhomirov@176: 			}
tikhomirov@176: 			toQuery.clear();
tikhomirov@31: 		}
tikhomirov@176: 		if (rootIndex == -1) {
tikhomirov@176: 			throw new HgBadStateException("Shall not happen, provided between output is correct"); // FIXME
tikhomirov@31: 		}
tikhomirov@176: 		result[rootIndex] = rb.root;
tikhomirov@176: 		boolean resultOk = true;
tikhomirov@176: 		LinkedList<Nodeid> fromRootToHead = new LinkedList<Nodeid>();
tikhomirov@176: 		for (int i = 0; i <= rootIndex; i++) {
tikhomirov@176: 			Nodeid n = result[i];
tikhomirov@176: 			if (n == null) {
tikhomirov@176: 				System.out.printf("ERROR: element %d wasn't found\n",i);
tikhomirov@176: 				resultOk = false;
tikhomirov@176: 			}
tikhomirov@176: 			fromRootToHead.addFirst(n); // reverse order
tikhomirov@31: 		}
tikhomirov@176: 		if (!resultOk) {
tikhomirov@176: 			throw new HgBadStateException("See console for details"); // FIXME
tikhomirov@176: 		}
tikhomirov@176: 		return fromRootToHead;
tikhomirov@31: 	}
tikhomirov@31: 
tikhomirov@173: 	private static class SequenceConstructor {
tikhomirov@173: 
tikhomirov@173: 		private int[] between(int root, int head) {
tikhomirov@173: 			if (head <= (root+1)) {
tikhomirov@173: 				return new int[0];
tikhomirov@173: 			}
tikhomirov@173: 			System.out.printf("[%d, %d]\t\t", root, head);
tikhomirov@173: 			int size = 1 + (int) Math.floor(Math.log(head-root - 1) / Math.log(2));
tikhomirov@173: 			int[] rv = new int[size];
tikhomirov@173: 			for (int v = 1, i = 0; i < rv.length; i++) {
tikhomirov@173: 				rv[i] = root + v;
tikhomirov@173: 				v = v << 1;
tikhomirov@173: 			}
tikhomirov@173: 			System.out.println(Arrays.toString(rv));
tikhomirov@173: 			return rv;
tikhomirov@173: 		}
tikhomirov@173: 
tikhomirov@173: 		public void test() {
tikhomirov@176: 			int root = 0, head = 126;
tikhomirov@176: 			int[] data = between(root, head); // max number of elements to recover is 2**data.length-1, when head is exactly
tikhomirov@176: 			// 2**data.length element of the branch.  
tikhomirov@176: 			// In such case, total number of elements in the branch (including head and root, would be 2**data.length+1
tikhomirov@176: 			int[] finalSequence = new int[1 + (1 << data.length >>> 5)]; // div 32 - total bits to integers, +1 for possible modulus
tikhomirov@173: 			int exactNumberOfElements = -1; // exact number of meaningful bits in finalSequence
tikhomirov@173: 			LinkedHashMap<Integer, int[]> datas = new LinkedHashMap<Integer, int[]>();
tikhomirov@173: 			datas.put(root, data);
tikhomirov@173: 			int totalQueries = 1;
tikhomirov@173: 			HashSet<Integer> queried = new HashSet<Integer>();
tikhomirov@173: 			int[] checkSequence = null;
tikhomirov@173: 			while(!datas.isEmpty()) {
tikhomirov@173: 				LinkedList<int[]> toQuery = new LinkedList<int[]>();
tikhomirov@173: 				do {
tikhomirov@173: 					Iterator<Entry<Integer, int[]>> it = datas.entrySet().iterator();
tikhomirov@173: 					Entry<Integer, int[]> next = it.next();
tikhomirov@173: 					int r = next.getKey();
tikhomirov@173: 					data = next.getValue();
tikhomirov@173: 					it.remove();
tikhomirov@173: 					populate(r, head, data, finalSequence);
tikhomirov@173: 					if (checkSequence != null) {
tikhomirov@173: 						boolean match = true;
tikhomirov@173: //						System.out.println("Try to match:");
tikhomirov@173: 						for (int i = 0; i < checkSequence.length; i++) {
tikhomirov@173: //							System.out.println(i);
tikhomirov@173: //							System.out.println("control:" + toBinaryString(checkSequence[i], ' '));
tikhomirov@173: //							System.out.println("present:" + toBinaryString(finalSequence[i], ' '));
tikhomirov@173: 							if (checkSequence[i] != finalSequence[i]) {
tikhomirov@173: 								match = false;
tikhomirov@173: 							} else {
tikhomirov@173: 								match &= true;
tikhomirov@173: 							}
tikhomirov@173: 						}
tikhomirov@173: 						System.out.println(match ? "Match, on query:" + totalQueries : "Didn't match");
tikhomirov@173: 					}
tikhomirov@176: 					if (data.length > 1) { 
tikhomirov@176: 						/*queries for elements next to head is senseless, hence data.length check above and head-x below*/
tikhomirov@173: 						for (int x : data) {
tikhomirov@176: 							if (!queried.contains(x) && head - x > 1) { 
tikhomirov@173: 								toQuery.add(new int[] {x, head});
tikhomirov@173: 							}
tikhomirov@173: 						}
tikhomirov@173: 					}
tikhomirov@173: 				} while (!datas.isEmpty()) ;
tikhomirov@173: 				if (!toQuery.isEmpty()) {
tikhomirov@173: 					System.out.println();
tikhomirov@173: 					totalQueries++;
tikhomirov@173: 				}
tikhomirov@173: 				Collections.sort(toQuery, new Comparator<int[]>() {
tikhomirov@173: 
tikhomirov@173: 					public int compare(int[] o1, int[] o2) {
tikhomirov@173: 						return o1[0] < o2[0] ? -1 : (o1[0] == o2[0] ? 0 : 1);
tikhomirov@173: 					}
tikhomirov@173: 				});
tikhomirov@173: 				for (int[] x : toQuery) {
tikhomirov@173: 					if (!queried.contains(x[0])) {
tikhomirov@173: 						queried.add(x[0]);
tikhomirov@173: 						data = between(x[0], x[1]);
tikhomirov@173: 						if (exactNumberOfElements == -1 && data.length == 1) {
tikhomirov@173: 							exactNumberOfElements = x[0] + 1;
tikhomirov@173: 							System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, exactNumberOfElements);
tikhomirov@173: 							// get a bit sequence of exactNumberOfElements, 0111..110
tikhomirov@173: 							// to 'and' it with finalSequence later
tikhomirov@173: 							int totalInts = (exactNumberOfElements + 2 /*heading and tailing zero bits*/) >>> 5;
tikhomirov@173: 							int trailingBits = (exactNumberOfElements + 2) & 0x1f;
tikhomirov@173: 							if (trailingBits != 0) {
tikhomirov@173: 								totalInts++;
tikhomirov@173: 							}
tikhomirov@173: 							checkSequence = new int[totalInts];
tikhomirov@173: 							Arrays.fill(checkSequence, 0xffffffff);
tikhomirov@173: 							checkSequence[0] &= 0x7FFFFFFF;
tikhomirov@173: 							if (trailingBits == 0) {
tikhomirov@173: 								checkSequence[totalInts-1] &= 0xFFFFFFFE;
tikhomirov@173: 							} else if (trailingBits == 1) {
tikhomirov@173: 								checkSequence[totalInts-1] = 0;
tikhomirov@173: 							} else {
tikhomirov@173: 								// trailingBits include heading and trailing zero bits
tikhomirov@173: 								int mask = 0x80000000 >> trailingBits-2; // with sign!
tikhomirov@173: 								checkSequence[totalInts - 1] &= mask;
tikhomirov@173: 							}
tikhomirov@173: 							for (int e : checkSequence) {
tikhomirov@173: 								System.out.print(toBinaryString(e, ' '));
tikhomirov@173: 							}
tikhomirov@173: 							System.out.println();
tikhomirov@173: 						}
tikhomirov@173: 						datas.put(x[0], data);
tikhomirov@173: 					}
tikhomirov@173: 				}
tikhomirov@173: 			}
tikhomirov@173: 
tikhomirov@173: 			System.out.println("Total queries:" + totalQueries);
tikhomirov@173: 			for (int x : finalSequence) {
tikhomirov@173: 				System.out.print(toBinaryString(x, ' '));
tikhomirov@173: 			}
tikhomirov@173: 		}
tikhomirov@173: 		
tikhomirov@173: 		private void populate(int root, int head, int[] data, int[] finalSequence) {
tikhomirov@173: 			for (int i = 1, x = 0; root+i < head; i = i << 1, x++) {
tikhomirov@173: 				int value = data[x];
tikhomirov@173: 				int value_check = root+i;
tikhomirov@174: 				if (value != value_check) {
tikhomirov@174: 					throw new IllegalStateException();
tikhomirov@174: 				}
tikhomirov@173: 				int wordIx = (root + i) >>> 5;
tikhomirov@173: 				int bitIx = (root + i) & 0x1f;
tikhomirov@173: 				finalSequence[wordIx] |= 1 << (31-bitIx);
tikhomirov@173: 			}
tikhomirov@173: 		}
tikhomirov@173: 		
tikhomirov@173: 		private static String toBinaryString(int x, char byteSeparator) {
tikhomirov@173: 			StringBuilder sb = new StringBuilder(4*8+4);
tikhomirov@173: 			sb.append(toBinaryString((byte) (x >>> 24)));
tikhomirov@173: 			sb.append(byteSeparator);
tikhomirov@173: 			sb.append(toBinaryString((byte) ((x & 0x00ff0000) >>> 16)));
tikhomirov@173: 			sb.append(byteSeparator);
tikhomirov@173: 			sb.append(toBinaryString((byte) ((x & 0x00ff00) >>> 8)));
tikhomirov@173: 			sb.append(byteSeparator);
tikhomirov@173: 			sb.append(toBinaryString((byte) (x & 0x00ff)));
tikhomirov@173: 			sb.append(byteSeparator);
tikhomirov@173: 			return sb.toString();
tikhomirov@173: 		}
tikhomirov@173: 
tikhomirov@173: 		private static String toBinaryString(byte b) {
tikhomirov@173: 			final String nibbles = "0000000100100011010001010110011110001001101010111100110111101111";
tikhomirov@173: 			assert nibbles.length() == 16*4;
tikhomirov@173: 			int x1 = (b >>> 4) & 0x0f, x2 = b & 0x0f;
tikhomirov@173: 			x1 *= 4; x2 *= 4; // 4 characters per nibble
tikhomirov@173: 			return nibbles.substring(x1, x1+4).concat(nibbles.substring(x2, x2+4));
tikhomirov@173: 		}
tikhomirov@173: 	}
tikhomirov@31: }