Mercurial > hg4j

annotate src/org/tmatesoft/hg/internal/RevisionDescendants.java @ 449:5787e912f60e smartgit3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Speed up changeset phase detection when no parent cache is avalable
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 07 Jun 2012 16:01:09 +0200
parents
children 03fd8d079e9c
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.HgBadStateException;
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.core.HgInvalidControlFileException;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 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
24 import org.tmatesoft.hg.repo.HgChangelog;
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);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 repo.getChangelog().walk(rootRevIndex+1, tipRevIndex, new HgChangelog.ParentInspector() {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 // 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
59
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 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
61 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
62 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
63 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
64 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
65 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
66 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
67 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
68 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 if (p2x >= 0) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 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
71 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
72 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 //
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 int rx = revisionIndex -rootRevIndex;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 if (rx != i) {
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 throw new HgBadStateException();
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 // current revision is descentand if any of its parents is descendant
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 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
80 i++;
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 });
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 }
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 // 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
86 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
87 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
88 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 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
91 // 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
92 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
93 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 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
96 assert isCandidate(revisionIndex);
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 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
98 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
99 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
100 }
5787e912f60e Speed up changeset phase detection when no parent cache is avalable
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 }