tikhomirov@432: /* tikhomirov@628: * Copyright (c) 2011-2013 TMate Software Ltd tikhomirov@432: * tikhomirov@432: * This program is free software; you can redistribute it and/or modify tikhomirov@432: * it under the terms of the GNU General Public License as published by tikhomirov@432: * the Free Software Foundation; version 2 of the License. tikhomirov@432: * tikhomirov@432: * This program is distributed in the hope that it will be useful, tikhomirov@432: * but WITHOUT ANY WARRANTY; without even the implied warranty of tikhomirov@432: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the tikhomirov@432: * GNU General Public License for more details. tikhomirov@432: * tikhomirov@432: * For information on how to redistribute this software under tikhomirov@432: * the terms of a license other than GNU General Public License tikhomirov@432: * contact TMate Software at support@hg4j.com tikhomirov@432: */ tikhomirov@432: package org.tmatesoft.hg.repo; tikhomirov@432: tikhomirov@432: import static org.tmatesoft.hg.repo.HgRepository.TIP; tikhomirov@432: tikhomirov@652: import java.util.ArrayList; tikhomirov@432: import java.util.Arrays; tikhomirov@652: import java.util.BitSet; tikhomirov@432: import java.util.Collection; tikhomirov@645: import java.util.Collections; tikhomirov@432: import java.util.HashSet; tikhomirov@432: import java.util.LinkedList; tikhomirov@432: import java.util.List; tikhomirov@432: tikhomirov@432: import org.tmatesoft.hg.core.Nodeid; tikhomirov@657: import org.tmatesoft.hg.internal.ArrayHelper; tikhomirov@656: import org.tmatesoft.hg.internal.IntMap; tikhomirov@432: import org.tmatesoft.hg.repo.Revlog.ParentInspector; tikhomirov@432: tikhomirov@432: /** tikhomirov@432: * Helper class to deal with parent-child relationship between revisions en masse. tikhomirov@432: * Works in terms of {@link Nodeid nodeids}, there's no need to deal with revision indexes. tikhomirov@432: * For a given revision, answers questions like "who's my parent and what are my immediate children". tikhomirov@432: * tikhomirov@432: *

Comes handy when multiple revisions are analyzed and distinct {@link Revlog#parents(int, int[], byte[], byte[])} tikhomirov@432: * queries are ineffective. tikhomirov@432: * tikhomirov@432: *

Next code snippet shows typical use: tikhomirov@432: *

tikhomirov@432:  *   HgChangelog clog = repo.getChangelog();
tikhomirov@432:  *   ParentWalker<HgChangelog> pw = new ParentWalker<HgChangelog>(clog);
tikhomirov@432:  *   pw.init();
tikhomirov@432:  *   
tikhomirov@432:  *   Nodeid me = Nodeid.fromAscii("...");
tikhomirov@432:  *   List immediateChildren = pw.directChildren(me);
tikhomirov@432:  * 
tikhomirov@432: * tikhomirov@432: * tikhomirov@432: *

Perhaps, later may add alternative way to access (and reuse) map instance, Revlog#getParentWalker(), tikhomirov@432: * that instantiates and initializes ParentWalker, and keep SoftReference to allow its reuse. tikhomirov@432: * tikhomirov@433: * @see HgRevisionMap tikhomirov@432: * tikhomirov@432: * @author Artem Tikhomirov tikhomirov@432: * @author TMate Software Ltd. tikhomirov@432: */ tikhomirov@432: public final class HgParentChildMap implements ParentInspector { tikhomirov@432: tikhomirov@646: // IMPORTANT: Nodeid instances shall be shared between all arrays tikhomirov@646: tikhomirov@657: private final T revlog; tikhomirov@432: private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering tikhomirov@657: private Nodeid[] sorted; // for binary search, just an origin of the actual value in use, the one inside seqWrapper tikhomirov@652: private Nodeid[] firstParent; // parents by natural order (i.e. firstParent[A] is parent of revision with index A) tikhomirov@432: private Nodeid[] secondParent; tikhomirov@656: private IntMap heads; tikhomirov@656: private BitSet headsBitSet; // 1 indicates revision got children, != null only during init; tikhomirov@657: private HgRevisionMap revisionIndexMap; tikhomirov@657: private ArrayHelper seqWrapper; tikhomirov@432: tikhomirov@432: tikhomirov@432: public HgParentChildMap(T owner) { tikhomirov@432: revlog = owner; tikhomirov@432: } tikhomirov@432: tikhomirov@432: public HgRepository getRepo() { tikhomirov@432: return revlog.getRepo(); tikhomirov@432: } tikhomirov@432: tikhomirov@432: public void next(int revisionNumber, Nodeid revision, int parent1Revision, int parent2Revision, Nodeid nidParent1, Nodeid nidParent2) { tikhomirov@432: if (parent1Revision >= revisionNumber || parent2Revision >= revisionNumber) { tikhomirov@432: throw new IllegalStateException(); // sanity, revisions are sequential tikhomirov@432: } tikhomirov@432: int ix = revisionNumber; tikhomirov@432: sequential[ix] = sorted[ix] = revision; tikhomirov@432: if (parent1Revision != -1) { tikhomirov@432: firstParent[ix] = sequential[parent1Revision]; tikhomirov@656: headsBitSet.set(parent1Revision); tikhomirov@432: } tikhomirov@432: if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1 tikhomirov@432: secondParent[ix] = sequential[parent2Revision]; tikhomirov@656: headsBitSet.set(parent2Revision); tikhomirov@432: } tikhomirov@432: } tikhomirov@432: tikhomirov@628: /** tikhomirov@628: * Prepare the map tikhomirov@628: * @throws HgInvalidControlFileException if failed to access revlog index/data entry. Runtime exception tikhomirov@628: * @throws HgRuntimeException subclass thereof to indicate other issues with the library. Runtime exception tikhomirov@628: */ tikhomirov@628: public void init() throws HgRuntimeException { tikhomirov@432: final int revisionCount = revlog.getRevisionCount(); tikhomirov@432: firstParent = new Nodeid[revisionCount]; tikhomirov@652: // TODO [post 1.1] Branches/merges are less frequent, and most of secondParent would be -1/null, hence tikhomirov@432: // IntMap might be better alternative here, but need to carefully analyze (test) whether this brings tikhomirov@656: // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant). tikhomirov@656: // FWIW: in cpython's repo, with 70k+ revisions, there are 2618 values in secondParent tikhomirov@432: secondParent = new Nodeid[revisionCount]; tikhomirov@432: // tikhomirov@432: sequential = new Nodeid[revisionCount]; tikhomirov@657: sorted = new Nodeid[revisionCount]; tikhomirov@656: headsBitSet = new BitSet(revisionCount); tikhomirov@432: revlog.indexWalk(0, TIP, this); tikhomirov@657: seqWrapper = new ArrayHelper(sequential); tikhomirov@657: // HgRevisionMap doesn't keep sorted, try alternative here. tikhomirov@657: // reference this.sorted (not only from ArrayHelper) helps to track ownership in hprof/mem dumps tikhomirov@657: seqWrapper.sort(sorted, false, true); tikhomirov@656: // no reason to keep BitSet, number of heads is usually small tikhomirov@656: IntMap _heads = new IntMap(headsBitSet.size() - headsBitSet.cardinality()); tikhomirov@656: int index = 0; tikhomirov@656: while (index < sequential.length) { tikhomirov@656: index = headsBitSet.nextClearBit(index); tikhomirov@656: // nextClearBit(length-1) gives length when bit is set, tikhomirov@656: // however, last revision can't be a parent of any other, and tikhomirov@656: // the last bit would be always 0, and no AIOOBE tikhomirov@656: _heads.put(index, sequential[index]); tikhomirov@656: index++; tikhomirov@656: } tikhomirov@656: headsBitSet = null; tikhomirov@656: heads = _heads; tikhomirov@432: } tikhomirov@432: tikhomirov@432: private void assertSortedIndex(int x) { tikhomirov@432: if (x < 0) { tikhomirov@432: throw new HgInvalidStateException(String.format("Bad index", x)); tikhomirov@432: } tikhomirov@432: } tikhomirov@432: tikhomirov@432: /** tikhomirov@432: * Tells whether supplied revision is from the walker's associated revlog. tikhomirov@432: * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known. tikhomirov@432: * @param nid revision to check, not null tikhomirov@432: * @return true if revision matches any revision in this revlog tikhomirov@432: */ tikhomirov@432: public boolean knownNode(Nodeid nid) { tikhomirov@657: return seqWrapper.binarySearchSorted(nid) >= 0; tikhomirov@432: } tikhomirov@432: tikhomirov@432: /** tikhomirov@432: * null if none. only known nodes (as per #knownNode) are accepted as arguments tikhomirov@432: */ tikhomirov@432: public Nodeid firstParent(Nodeid nid) { tikhomirov@657: int x = seqWrapper.binarySearchSorted(nid); tikhomirov@432: assertSortedIndex(x); tikhomirov@657: int i = seqWrapper.getReverseIndex(x); tikhomirov@432: return firstParent[i]; tikhomirov@432: } tikhomirov@432: tikhomirov@432: // never null, Nodeid.NULL if none known tikhomirov@432: public Nodeid safeFirstParent(Nodeid nid) { tikhomirov@432: Nodeid rv = firstParent(nid); tikhomirov@432: return rv == null ? Nodeid.NULL : rv; tikhomirov@432: } tikhomirov@432: tikhomirov@432: public Nodeid secondParent(Nodeid nid) { tikhomirov@657: int x = seqWrapper.binarySearchSorted(nid); tikhomirov@432: assertSortedIndex(x); tikhomirov@657: int i = seqWrapper.getReverseIndex(x); tikhomirov@432: return secondParent[i]; tikhomirov@432: } tikhomirov@432: tikhomirov@432: public Nodeid safeSecondParent(Nodeid nid) { tikhomirov@432: Nodeid rv = secondParent(nid); tikhomirov@432: return rv == null ? Nodeid.NULL : rv; tikhomirov@432: } tikhomirov@432: tikhomirov@432: public boolean appendParentsOf(Nodeid nid, Collection c) { tikhomirov@657: int x = seqWrapper.binarySearchSorted(nid); tikhomirov@432: assertSortedIndex(x); tikhomirov@657: int i = seqWrapper.getReverseIndex(x); tikhomirov@432: Nodeid p1 = firstParent[i]; tikhomirov@432: boolean modified = false; tikhomirov@432: if (p1 != null) { tikhomirov@432: modified = c.add(p1); tikhomirov@432: } tikhomirov@432: Nodeid p2 = secondParent[i]; tikhomirov@432: if (p2 != null) { tikhomirov@432: modified = c.add(p2) || modified; tikhomirov@432: } tikhomirov@432: return modified; tikhomirov@432: } tikhomirov@432: tikhomirov@432: // XXX alternative (and perhaps more reliable) approach would be to make a copy of allNodes and remove tikhomirov@432: // nodes, their parents and so on. tikhomirov@432: tikhomirov@432: // @return ordered collection of all children rooted at supplied nodes. Nodes shall not be descendants of each other! tikhomirov@432: // Nodeids shall belong to this revlog tikhomirov@650: public List childrenOf(Collection roots) { tikhomirov@645: if (roots.isEmpty()) { tikhomirov@645: return Collections.emptyList(); tikhomirov@645: } tikhomirov@432: HashSet parents = new HashSet(); tikhomirov@432: LinkedList result = new LinkedList(); tikhomirov@432: int earliestRevision = Integer.MAX_VALUE; tikhomirov@432: assert sequential.length == firstParent.length && firstParent.length == secondParent.length; tikhomirov@432: // first, find earliest index of roots in question, as there's no sense tikhomirov@432: // to check children among nodes prior to branch's root node tikhomirov@432: for (Nodeid r : roots) { tikhomirov@657: int x = seqWrapper.binarySearchSorted(r); tikhomirov@432: assertSortedIndex(x); tikhomirov@657: int i = seqWrapper.getReverseIndex(x); tikhomirov@432: if (i < earliestRevision) { tikhomirov@432: earliestRevision = i; tikhomirov@432: } tikhomirov@432: parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a == tikhomirov@432: } tikhomirov@432: for (int i = earliestRevision + 1; i < sequential.length; i++) { tikhomirov@432: if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) { tikhomirov@432: parents.add(sequential[i]); // to find next child tikhomirov@432: result.add(sequential[i]); tikhomirov@432: } tikhomirov@432: } tikhomirov@432: return result; tikhomirov@432: } tikhomirov@432: tikhomirov@432: /** tikhomirov@432: * @return revisions that have supplied revision as their immediate parent tikhomirov@432: */ tikhomirov@432: public List directChildren(Nodeid nid) { tikhomirov@657: int x = seqWrapper.binarySearchSorted(nid); tikhomirov@432: assertSortedIndex(x); tikhomirov@657: int start = seqWrapper.getReverseIndex(x); tikhomirov@657: nid = sequential[start]; // canonical instance tikhomirov@653: if (!hasChildren(start)) { tikhomirov@653: return Collections.emptyList(); tikhomirov@653: } tikhomirov@656: ArrayList result = new ArrayList(5); tikhomirov@432: for (int i = start + 1; i < sequential.length; i++) { tikhomirov@432: if (nid == firstParent[i] || nid == secondParent[i]) { tikhomirov@432: result.add(sequential[i]); tikhomirov@432: } tikhomirov@432: } tikhomirov@432: return result; tikhomirov@432: } tikhomirov@432: tikhomirov@432: /** tikhomirov@432: * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog. tikhomirov@432: * @return true if there's any node in this revlog that has specified node as one of its parents. tikhomirov@432: */ tikhomirov@432: public boolean hasChildren(Nodeid nid) { tikhomirov@657: int x = seqWrapper.binarySearchSorted(nid); tikhomirov@432: assertSortedIndex(x); tikhomirov@657: int i = seqWrapper.getReverseIndex(x); tikhomirov@652: return hasChildren(i); tikhomirov@432: } tikhomirov@659: tikhomirov@659: /** tikhomirov@645: * @return all revisions this map knows about tikhomirov@645: */ tikhomirov@645: public List all() { tikhomirov@645: return Arrays.asList(sequential); tikhomirov@645: } tikhomirov@646: tikhomirov@646: /** tikhomirov@646: * Find out whether a given node is among descendants of another. tikhomirov@646: * tikhomirov@646: * @param root revision to check for being (grand-)*parent of a child tikhomirov@646: * @param wannaBeChild candidate descendant revision tikhomirov@646: * @return true if wannaBeChild is among children of root tikhomirov@646: */ tikhomirov@646: public boolean isChild(Nodeid root, Nodeid wannaBeChild) { tikhomirov@657: int x = seqWrapper.binarySearchSorted(root); tikhomirov@646: assertSortedIndex(x); tikhomirov@657: final int start = seqWrapper.getReverseIndex(x); tikhomirov@657: root = sequential[start]; // canonical instance tikhomirov@652: if (!hasChildren(start)) { tikhomirov@652: return false; // root got no children at all tikhomirov@652: } tikhomirov@657: int y = seqWrapper.binarySearchSorted(wannaBeChild); tikhomirov@652: if (y < 0) { tikhomirov@652: return false; // not found tikhomirov@646: } tikhomirov@657: final int end = seqWrapper.getReverseIndex(y); tikhomirov@657: wannaBeChild = sequential[end]; // canonicalize tikhomirov@652: if (end <= start) { tikhomirov@652: return false; // potential child was in repository earlier than root tikhomirov@652: } tikhomirov@646: HashSet parents = new HashSet(); tikhomirov@646: parents.add(root); tikhomirov@646: for (int i = start + 1; i < end; i++) { tikhomirov@646: if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) { tikhomirov@646: parents.add(sequential[i]); // collect ancestors line tikhomirov@646: } tikhomirov@646: } tikhomirov@646: return parents.contains(firstParent[end]) || parents.contains(secondParent[end]); tikhomirov@646: } tikhomirov@652: tikhomirov@652: /** tikhomirov@652: * @return elements of this map that do not have a child recorded therein. tikhomirov@652: */ tikhomirov@652: public Collection heads() { tikhomirov@656: return heads.values(); tikhomirov@652: } tikhomirov@657: tikhomirov@657: /** tikhomirov@657: * @return map of revision to indexes tikhomirov@657: */ tikhomirov@657: public HgRevisionMap getRevisionMap() { tikhomirov@657: if (revisionIndexMap == null) { tikhomirov@657: revisionIndexMap = new HgRevisionMap(revlog); tikhomirov@657: revisionIndexMap.init(seqWrapper); tikhomirov@657: } tikhomirov@657: return revisionIndexMap; tikhomirov@657: } tikhomirov@652: tikhomirov@652: private boolean hasChildren(int sequentialIndex) { tikhomirov@656: return !heads.containsKey(sequentialIndex); tikhomirov@652: } tikhomirov@432: }