Mercurial > hg4j

annotate src/org/tmatesoft/hg/internal/RevisionDescendants.java @ 587:a52f4cc56f9c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Minimize vectors re-allocating when merging patches
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 26 Apr 2013 20:04:17 +0200
parents 2a0b09eec376
children 6526d8adbc0f
rev   line source
449
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2012 TMate Software Ltd
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.internal;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 import java.util.BitSet;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 import org.tmatesoft.hg.core.Nodeid;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22 import org.tmatesoft.hg.repo.HgChangelog;
471
7bcfbc255f48 Merge changes from smartgit3 branch into 1.1 stream
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 450
diff changeset
23 import org.tmatesoft.hg.repo.HgInvalidControlFileException;
7bcfbc255f48 Merge changes from smartgit3 branch into 1.1 stream
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 450
diff changeset
24 import org.tmatesoft.hg.repo.HgInvalidStateException;
449
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 import org.tmatesoft.hg.repo.HgRepository;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 /**
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 * Represent indicators which revisions are descendants of the supplied root revision
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 * This is sort of lightweight alternative to ParentWalker#childrenOf
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 *
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 * @author Artem Tikhomirov
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 * @author TMate Software Ltd.
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 */
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 public class RevisionDescendants {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 private final HgRepository repo;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 private final int rootRevIndex;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 private final int tipRevIndex; // this is the last revision we cache to
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39 private final BitSet descendants;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 // in fact, may be refactored to deal not only with changelog, but any revlog (not sure what would be the usecase, though)
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 public RevisionDescendants(HgRepository hgRepo, int revisionIndex) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 repo = hgRepo;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 rootRevIndex = revisionIndex;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 // even if tip moves, we still answer correctly for those isCandidate()
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 tipRevIndex = repo.getChangelog().getLastRevision();
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 if (revisionIndex < 0 || revisionIndex > tipRevIndex) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 String m = "Revision to build descendants for shall be in range [%d,%d], not %d";
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 throw new IllegalArgumentException(String.format(m, 0, tipRevIndex, revisionIndex));
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 descendants = new BitSet(tipRevIndex - rootRevIndex + 1);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 public void build() throws HgInvalidControlFileException {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 final BitSet result = descendants;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 result.set(0);
450
03fd8d079e9c Share PhasesHelper instance among few HgChangesets (mostly affects HgChangesetTreeHandler case)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 449
diff changeset
57 if (rootRevIndex == tipRevIndex) {
03fd8d079e9c Share PhasesHelper instance among few HgChangesets (mostly affects HgChangesetTreeHandler case)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 449
diff changeset
58 return;
03fd8d079e9c Share PhasesHelper instance among few HgChangesets (mostly affects HgChangesetTreeHandler case)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 449
diff changeset
59 }
471
7bcfbc255f48 Merge changes from smartgit3 branch into 1.1 stream
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 450
diff changeset
60 repo.getChangelog().indexWalk(rootRevIndex+1, tipRevIndex, new HgChangelog.ParentInspector() {
449
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 // TODO ParentRevisionInspector, with no parent nodeids, just indexes?
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 private int i = 1; // above we start with revision next to rootRevIndex, which is at offset 0
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 public void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 int p1x = parent1 - rootRevIndex;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 int p2x = parent2 - rootRevIndex;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 boolean p1IsDescendant = false, p2IsDescendant = false;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 if (p1x >= 0) { // parent1 is among descendants candidates
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 assert p1x < result.size();
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 p1IsDescendant = result.get(p1x);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 if (p2x >= 0) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 assert p2x < result.size();
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 p2IsDescendant = result.get(p2x);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 //
471
7bcfbc255f48 Merge changes from smartgit3 branch into 1.1 stream
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 450
diff changeset
77 int rx = revisionIndex - rootRevIndex;
449
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 if (rx != i) {
471
7bcfbc255f48 Merge changes from smartgit3 branch into 1.1 stream
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 450
diff changeset
79 throw new HgInvalidStateException(String.format("Sanity check failed. Revision %d. Expected:%d, was:%d", revisionIndex, rx, i));
449
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 }
471
7bcfbc255f48 Merge changes from smartgit3 branch into 1.1 stream
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 450
diff changeset
81 // current revision is descendant if any of its parents is descendant
449
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 result.set(rx, p1IsDescendant || p2IsDescendant);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 i++;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 });
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 // deliberately doesn't allow TIP
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 public boolean isCandidate(int revIndex) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 return (revIndex >= rootRevIndex && revIndex <= tipRevIndex) ;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 public boolean hasDescendants() { // isEmpty is better name?
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 // bit at rootRevIndex is always set
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 return descendants.nextSetBit(rootRevIndex+1) != -1;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97
472
2a0b09eec376 Tests for issue 31
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
98 /**
2a0b09eec376 Tests for issue 31
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
99 * Tells whether specified revision is on a descent line from the root revision.
2a0b09eec376 Tests for issue 31
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
100 * <p>NOTE, root revision itself is considered to be its own descendant.
2a0b09eec376 Tests for issue 31
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
101 *
2a0b09eec376 Tests for issue 31
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
102 * @param revisionIndex revision index to check, shall pass {@link #isCandidate(int)}
2a0b09eec376 Tests for issue 31
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
103 * @return <code>true</code> if revision is descendant of or is the same as root revision
2a0b09eec376 Tests for issue 31
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
104 */
449
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 public boolean isDescendant(int revisionIndex) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 assert isCandidate(revisionIndex);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 int ix = revisionIndex - rootRevIndex;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 assert ix < descendants.size();
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 return descendants.get(ix);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 }