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@177: import java.util.HashMap; 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@177: import java.util.Map; 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@177: import org.tmatesoft.hg.repo.HgRemoteRepository.Range; 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 missingBranches = calculateMissingBranches(hgRepo, hgRemote); tikhomirov@176: LinkedList missing = new LinkedList(); tikhomirov@176: for (RemoteBranch rb : missingBranches) { tikhomirov@176: List 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 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 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 entries; tikhomirov@31: tikhomirov@176: public DataEntry(Nodeid head, int index, List data) { tikhomirov@176: queryHead = head; tikhomirov@176: headIndex = index; tikhomirov@176: entries = data; tikhomirov@176: } tikhomirov@176: }; tikhomirov@176: tikhomirov@176: List 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 datas = new LinkedList(); 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 toQuery = new LinkedList(); tikhomirov@176: // tikhomirov@176: datas.add(new DataEntry(rb.head, 0, initial)); tikhomirov@176: int totalQueries = 1; tikhomirov@176: HashSet queried = new HashSet(); tikhomirov@176: while(!datas.isEmpty()) { tikhomirov@177: // keep record of those planned to be queried next time we call between() tikhomirov@177: // although may keep these in queried, if really don't want separate collection tikhomirov@177: HashSet scheduled = new HashSet(); 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@177: if (!queried.contains(x) && !scheduled.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@177: scheduled.add(x); tikhomirov@176: } tikhomirov@176: } tikhomirov@176: } tikhomirov@176: } while (!datas.isEmpty()); tikhomirov@176: if (!toQuery.isEmpty()) { tikhomirov@176: totalQueries++; tikhomirov@176: } tikhomirov@177: // for each query, create an between request range, keep record Range->DataEntry to know range's start index tikhomirov@177: LinkedList betweenBatch = new LinkedList(); tikhomirov@177: HashMap rangeToEntry = new HashMap(); tikhomirov@176: for (DataEntry de : toQuery) { tikhomirov@177: queried.add(de.queryHead); tikhomirov@177: HgRemoteRepository.Range r = new HgRemoteRepository.Range(rb.root, de.queryHead); tikhomirov@177: betweenBatch.add(r); tikhomirov@177: rangeToEntry.put(r, de); tikhomirov@177: } tikhomirov@177: if (!betweenBatch.isEmpty()) { tikhomirov@177: Map> between = hgRemote.between(betweenBatch); tikhomirov@177: for (Entry> e : between.entrySet()) { tikhomirov@177: DataEntry de = rangeToEntry.get(e.getKey()); tikhomirov@177: assert de != null; tikhomirov@177: de.entries = e.getValue(); tikhomirov@177: if (rootIndex == -1 && de.entries.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: datas.add(de); // queue up to record result and construct further requests tikhomirov@176: } tikhomirov@177: betweenBatch.clear(); tikhomirov@177: rangeToEntry.clear(); 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 fromRootToHead = new LinkedList(); 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@177: System.out.println("Total queries:" + totalQueries); 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 datas = new LinkedHashMap(); tikhomirov@173: datas.put(root, data); tikhomirov@173: int totalQueries = 1; tikhomirov@173: HashSet queried = new HashSet(); tikhomirov@173: int[] checkSequence = null; tikhomirov@173: while(!datas.isEmpty()) { tikhomirov@173: LinkedList toQuery = new LinkedList(); tikhomirov@173: do { tikhomirov@173: Iterator> it = datas.entrySet().iterator(); tikhomirov@173: Entry 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() { 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: }