kitaev@213: /*
kitaev@213:  * Copyright (c) 2011 TMate Software Ltd
kitaev@213:  *  
kitaev@213:  * This program is free software; you can redistribute it and/or modify
kitaev@213:  * it under the terms of the GNU General Public License as published by
kitaev@213:  * the Free Software Foundation; version 2 of the License.
kitaev@213:  *
kitaev@213:  * This program is distributed in the hope that it will be useful,
kitaev@213:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
kitaev@213:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
kitaev@213:  * GNU General Public License for more details.
kitaev@213:  *
kitaev@213:  * For information on how to redistribute this software under
kitaev@213:  * the terms of a license other than GNU General Public License
kitaev@213:  * contact TMate Software at support@hg4j.com
kitaev@213:  */
kitaev@213: package org.tmatesoft.hg.console;
kitaev@213: 
kitaev@213: import java.util.Arrays;
kitaev@213: import java.util.Collections;
kitaev@213: import java.util.Comparator;
kitaev@213: import java.util.HashSet;
kitaev@213: import java.util.Iterator;
kitaev@213: import java.util.LinkedHashMap;
kitaev@213: import java.util.LinkedList;
kitaev@213: import java.util.List;
kitaev@213: import java.util.Map.Entry;
kitaev@213: 
kitaev@213: import org.tmatesoft.hg.core.HgIncomingCommand;
kitaev@213: import org.tmatesoft.hg.core.HgRepoFacade;
kitaev@213: import org.tmatesoft.hg.core.Nodeid;
kitaev@213: import org.tmatesoft.hg.repo.HgLookup;
kitaev@213: import org.tmatesoft.hg.repo.HgRemoteRepository;
kitaev@213: 
kitaev@213: 
kitaev@213: /**
kitaev@213:  * <em>hg incoming</em> counterpart
kitaev@213:  * 
kitaev@213:  * @author Artem Tikhomirov
kitaev@213:  * @author TMate Software Ltd.
kitaev@213:  */
kitaev@213: public class Incoming {
kitaev@213: 
kitaev@213: 	public static void main(String[] args) throws Exception {
kitaev@213: 		if (Boolean.FALSE.booleanValue()) {
kitaev@213: 			new SequenceConstructor().test();
kitaev@213: 			return;
kitaev@213: 		}
kitaev@213: 		Options cmdLineOpts = Options.parse(args);
kitaev@213: 		HgRepoFacade hgRepo = new HgRepoFacade();
kitaev@213: 		if (!hgRepo.init(cmdLineOpts.findRepository())) {
kitaev@213: 			System.err.printf("Can't find repository in: %s\n", hgRepo.getRepository().getLocation());
kitaev@213: 			return;
kitaev@213: 		}
kitaev@213: 		HgRemoteRepository hgRemote = new HgLookup().detectRemote(cmdLineOpts.getSingle(""), hgRepo.getRepository());
kitaev@213: 		if (hgRemote.isInvalid()) {
kitaev@213: 			System.err.printf("Remote repository %s is not valid", hgRemote.getLocation());
kitaev@213: 			return;
kitaev@213: 		}
kitaev@213: 		HgIncomingCommand cmd = hgRepo.createIncomingCommand();
kitaev@213: 		cmd.against(hgRemote);
kitaev@213: 		//
kitaev@213: 		List<Nodeid> missing = cmd.executeLite(null);
kitaev@213: 		Collections.reverse(missing); // useful to test output, from newer to older
kitaev@213: 		Outgoing.dump("Nodes to fetch:", missing);
kitaev@213: 		System.out.printf("Total: %d\n\n", missing.size());
kitaev@213: 		//
kitaev@213: 		// Complete
kitaev@213: 		final ChangesetDumpHandler h = new ChangesetDumpHandler(hgRepo.getRepository());
kitaev@213: 		h.complete(false); // this option looks up index of parent revision, done via repo.changelog (which doesn't have any of these new revisions)
kitaev@213: 		// this can be fixed by tracking all nodeid->revision idx inside ChangesetDumpHandler, and refer to repo.changelog only when that mapping didn't work
kitaev@213: 		h.verbose(cmdLineOpts.getBoolean("-v", "--verbose"));
kitaev@213: 		cmd.executeFull(h);
kitaev@213: 	}
kitaev@213: 	
kitaev@213: 
kitaev@213: 	/*
kitaev@213: 	 * This is for investigation purposes only
kitaev@213: 	 */
kitaev@213: 	private static class SequenceConstructor {
kitaev@213: 
kitaev@213: 		private int[] between(int root, int head) {
kitaev@213: 			if (head <= (root+1)) {
kitaev@213: 				return new int[0];
kitaev@213: 			}
kitaev@213: 			System.out.printf("[%d, %d]\t\t", root, head);
kitaev@213: 			int size = 1 + (int) Math.floor(Math.log(head-root - 1) / Math.log(2));
kitaev@213: 			int[] rv = new int[size];
kitaev@213: 			for (int v = 1, i = 0; i < rv.length; i++) {
kitaev@213: 				rv[i] = root + v;
kitaev@213: 				v = v << 1;
kitaev@213: 			}
kitaev@213: 			System.out.println(Arrays.toString(rv));
kitaev@213: 			return rv;
kitaev@213: 		}
kitaev@213: 
kitaev@213: 		public void test() {
kitaev@213: 			int root = 0, head = 126;
kitaev@213: 			int[] data = between(root, head); // max number of elements to recover is 2**data.length-1, when head is exactly
kitaev@213: 			// 2**data.length element of the branch.  
kitaev@213: 			// In such case, total number of elements in the branch (including head and root, would be 2**data.length+1
kitaev@213: 			int[] finalSequence = new int[1 + (1 << data.length >>> 5)]; // div 32 - total bits to integers, +1 for possible modulus
kitaev@213: 			int exactNumberOfElements = -1; // exact number of meaningful bits in finalSequence
kitaev@213: 			LinkedHashMap<Integer, int[]> datas = new LinkedHashMap<Integer, int[]>();
kitaev@213: 			datas.put(root, data);
kitaev@213: 			int totalQueries = 1;
kitaev@213: 			HashSet<Integer> queried = new HashSet<Integer>();
kitaev@213: 			int[] checkSequence = null;
kitaev@213: 			while(!datas.isEmpty()) {
kitaev@213: 				LinkedList<int[]> toQuery = new LinkedList<int[]>();
kitaev@213: 				do {
kitaev@213: 					Iterator<Entry<Integer, int[]>> it = datas.entrySet().iterator();
kitaev@213: 					Entry<Integer, int[]> next = it.next();
kitaev@213: 					int r = next.getKey();
kitaev@213: 					data = next.getValue();
kitaev@213: 					it.remove();
kitaev@213: 					populate(r, head, data, finalSequence);
kitaev@213: 					if (checkSequence != null) {
kitaev@213: 						boolean match = true;
kitaev@213: //						System.out.println("Try to match:");
kitaev@213: 						for (int i = 0; i < checkSequence.length; i++) {
kitaev@213: //							System.out.println(i);
kitaev@213: //							System.out.println("control:" + toBinaryString(checkSequence[i], ' '));
kitaev@213: //							System.out.println("present:" + toBinaryString(finalSequence[i], ' '));
kitaev@213: 							if (checkSequence[i] != finalSequence[i]) {
kitaev@213: 								match = false;
kitaev@213: 							} else {
kitaev@213: 								match &= true;
kitaev@213: 							}
kitaev@213: 						}
kitaev@213: 						System.out.println(match ? "Match, on query:" + totalQueries : "Didn't match");
kitaev@213: 					}
kitaev@213: 					if (data.length > 1) { 
kitaev@213: 						/*queries for elements next to head is senseless, hence data.length check above and head-x below*/
kitaev@213: 						for (int x : data) {
kitaev@213: 							if (!queried.contains(x) && head - x > 1) { 
kitaev@213: 								toQuery.add(new int[] {x, head});
kitaev@213: 							}
kitaev@213: 						}
kitaev@213: 					}
kitaev@213: 				} while (!datas.isEmpty()) ;
kitaev@213: 				if (!toQuery.isEmpty()) {
kitaev@213: 					System.out.println();
kitaev@213: 					totalQueries++;
kitaev@213: 				}
kitaev@213: 				Collections.sort(toQuery, new Comparator<int[]>() {
kitaev@213: 
kitaev@213: 					public int compare(int[] o1, int[] o2) {
kitaev@213: 						return o1[0] < o2[0] ? -1 : (o1[0] == o2[0] ? 0 : 1);
kitaev@213: 					}
kitaev@213: 				});
kitaev@213: 				for (int[] x : toQuery) {
kitaev@213: 					if (!queried.contains(x[0])) {
kitaev@213: 						queried.add(x[0]);
kitaev@213: 						data = between(x[0], x[1]);
kitaev@213: 						if (exactNumberOfElements == -1 && data.length == 1) {
kitaev@213: 							exactNumberOfElements = x[0] + 1;
kitaev@213: 							System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, exactNumberOfElements);
kitaev@213: 							// get a bit sequence of exactNumberOfElements, 0111..110
kitaev@213: 							// to 'and' it with finalSequence later
kitaev@213: 							int totalInts = (exactNumberOfElements + 2 /*heading and tailing zero bits*/) >>> 5;
kitaev@213: 							int trailingBits = (exactNumberOfElements + 2) & 0x1f;
kitaev@213: 							if (trailingBits != 0) {
kitaev@213: 								totalInts++;
kitaev@213: 							}
kitaev@213: 							checkSequence = new int[totalInts];
kitaev@213: 							Arrays.fill(checkSequence, 0xffffffff);
kitaev@213: 							checkSequence[0] &= 0x7FFFFFFF;
kitaev@213: 							if (trailingBits == 0) {
kitaev@213: 								checkSequence[totalInts-1] &= 0xFFFFFFFE;
kitaev@213: 							} else if (trailingBits == 1) {
kitaev@213: 								checkSequence[totalInts-1] = 0;
kitaev@213: 							} else {
kitaev@213: 								// trailingBits include heading and trailing zero bits
kitaev@213: 								int mask = 0x80000000 >> trailingBits-2; // with sign!
kitaev@213: 								checkSequence[totalInts - 1] &= mask;
kitaev@213: 							}
kitaev@213: 							for (int e : checkSequence) {
kitaev@213: 								System.out.print(toBinaryString(e, ' '));
kitaev@213: 							}
kitaev@213: 							System.out.println();
kitaev@213: 						}
kitaev@213: 						datas.put(x[0], data);
kitaev@213: 					}
kitaev@213: 				}
kitaev@213: 			}
kitaev@213: 
kitaev@213: 			System.out.println("Total queries:" + totalQueries);
kitaev@213: 			for (int x : finalSequence) {
kitaev@213: 				System.out.print(toBinaryString(x, ' '));
kitaev@213: 			}
kitaev@213: 		}
kitaev@213: 		
kitaev@213: 		private void populate(int root, int head, int[] data, int[] finalSequence) {
kitaev@213: 			for (int i = 1, x = 0; root+i < head; i = i << 1, x++) {
kitaev@213: 				int value = data[x];
kitaev@213: 				int value_check = root+i;
kitaev@213: 				if (value != value_check) {
kitaev@213: 					throw new IllegalStateException();
kitaev@213: 				}
kitaev@213: 				int wordIx = (root + i) >>> 5;
kitaev@213: 				int bitIx = (root + i) & 0x1f;
kitaev@213: 				finalSequence[wordIx] |= 1 << (31-bitIx);
kitaev@213: 			}
kitaev@213: 		}
kitaev@213: 		
kitaev@213: 		private static String toBinaryString(int x, char byteSeparator) {
kitaev@213: 			StringBuilder sb = new StringBuilder(4*8+4);
kitaev@213: 			sb.append(toBinaryString((byte) (x >>> 24)));
kitaev@213: 			sb.append(byteSeparator);
kitaev@213: 			sb.append(toBinaryString((byte) ((x & 0x00ff0000) >>> 16)));
kitaev@213: 			sb.append(byteSeparator);
kitaev@213: 			sb.append(toBinaryString((byte) ((x & 0x00ff00) >>> 8)));
kitaev@213: 			sb.append(byteSeparator);
kitaev@213: 			sb.append(toBinaryString((byte) (x & 0x00ff)));
kitaev@213: 			sb.append(byteSeparator);
kitaev@213: 			return sb.toString();
kitaev@213: 		}
kitaev@213: 
kitaev@213: 		private static String toBinaryString(byte b) {
kitaev@213: 			final String nibbles = "0000000100100011010001010110011110001001101010111100110111101111";
kitaev@213: 			assert nibbles.length() == 16*4;
kitaev@213: 			int x1 = (b >>> 4) & 0x0f, x2 = b & 0x0f;
kitaev@213: 			x1 *= 4; x2 *= 4; // 4 characters per nibble
kitaev@213: 			return nibbles.substring(x1, x1+4).concat(nibbles.substring(x2, x2+4));
kitaev@213: 		}
kitaev@213: 	}
kitaev@213: }