Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/HgBranches.java @ 236:883300108179

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Speed up branches calculation when cached branch information is available
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 09 Jun 2011 06:13:43 +0200
parents 8de327242aa0
children 4b661efb9374
comparison
equal deleted inserted replaced
235:fd845a53f53d 236:883300108179
14 * the terms of a license other than GNU General Public License 14 * the terms of a license other than GNU General Public License
15 * contact TMate Software at support@hg4j.com 15 * contact TMate Software at support@hg4j.com
16 */ 16 */
17 package org.tmatesoft.hg.repo; 17 package org.tmatesoft.hg.repo;
18 18
19 import java.io.BufferedReader;
20 import java.io.File;
21 import java.io.FileReader;
22 import java.io.IOException;
19 import java.util.ArrayList; 23 import java.util.ArrayList;
20 import java.util.Arrays; 24 import java.util.Arrays;
21 import java.util.Collections; 25 import java.util.Collections;
22 import java.util.HashMap; 26 import java.util.HashMap;
23 import java.util.HashSet; 27 import java.util.HashSet;
28 import java.util.LinkedHashSet;
24 import java.util.LinkedList; 29 import java.util.LinkedList;
25 import java.util.List; 30 import java.util.List;
26 import java.util.Map; 31 import java.util.Map;
27 import java.util.TreeMap; 32 import java.util.TreeMap;
33 import java.util.regex.Pattern;
28 34
29 import org.tmatesoft.hg.core.Nodeid; 35 import org.tmatesoft.hg.core.Nodeid;
30 import org.tmatesoft.hg.repo.HgChangelog.RawChangeset; 36 import org.tmatesoft.hg.repo.HgChangelog.RawChangeset;
31 import org.tmatesoft.hg.util.ProgressSupport; 37 import org.tmatesoft.hg.util.ProgressSupport;
32 38
42 48
43 HgBranches(HgRepository hgRepo) { 49 HgBranches(HgRepository hgRepo) {
44 repo = hgRepo; 50 repo = hgRepo;
45 } 51 }
46 52
53 private int readCache() {
54 File branchheadsCache = new File(repo.getRepositoryRoot(), "branchheads.cache");
55 int lastInCache = -1;
56 if (!branchheadsCache.canRead()) {
57 return lastInCache;
58 }
59 BufferedReader br = null;
60 final Pattern spacePattern = Pattern.compile(" ");
61 try {
62 br = new BufferedReader(new FileReader(branchheadsCache));
63 String line = br.readLine();
64 if (line == null || line.trim().length() == 0) {
65 return lastInCache;
66 }
67 String[] cacheIdentity = spacePattern.split(line.trim());
68 lastInCache = Integer.parseInt(cacheIdentity[1]);
69 // XXX may want to check if nodeid of cset from repo.getChangelog() of lastInCache index match cacheIdentity[0]
70 //
71 while ((line = br.readLine()) != null) {
72 String[] elements = line.trim().split(" ");
73 if (elements.length < 2) {
74 // bad entry
75 continue;
76 }
77 Nodeid[] branchHeads = new Nodeid[elements.length - 1];
78 for (int i = 0; i < elements.length - 1; i++) {
79 branchHeads[i] = Nodeid.fromAscii(elements[i]);
80 }
81 // I assume split returns substrings of the original string, hence copy of a branch name
82 String branchName = new String(elements[elements.length-1]);
83 BranchInfo bi = new BranchInfo(branchName, branchHeads);
84 branches.put(branchName, bi);
85 }
86 return lastInCache;
87 } catch (IOException ex) {
88 ex.printStackTrace(); // XXX log error, but otherwise do nothing
89 } finally {
90 if (br != null) {
91 try {
92 br.close();
93 } catch (IOException ex) {
94 ex.printStackTrace(); // ignore
95 }
96 }
97 }
98 return -1; // deliberately not lastInCache, to avoid anything but -1 when 1st line was read and there's error is in lines 2..end
99 }
100
47 void collect(final ProgressSupport ps) { 101 void collect(final ProgressSupport ps) {
102 branches.clear();
48 ps.start(1 + repo.getChangelog().getRevisionCount() * 2); 103 ps.start(1 + repo.getChangelog().getRevisionCount() * 2);
49 final HgChangelog.ParentWalker pw = repo.getChangelog().new ParentWalker(); 104 //
50 pw.init(); 105 int lastCached = readCache();
51 ps.worked(repo.getChangelog().getRevisionCount()); 106 /*
52 final HashMap<String, Nodeid> branchStart = new HashMap<String, Nodeid>(); 107 * Next code was supposed to fill missing aspects of the BranchInfo, but is too slow
53 final HashMap<String, Nodeid> branchLastSeen = new HashMap<String, Nodeid>(); 108 *
54 final HashMap<String, List<Nodeid>> branchHeads = new HashMap<String, List<Nodeid>>(); 109 if (lastCached != -1 && lastCached <= repo.getChangelog().getLastRevision()) {
55 final HashSet<String> closedBranches = new HashSet<String>(); 110 LinkedList<BranchInfo> incompleteBranches = new LinkedList<HgBranches.BranchInfo>(branches.values());
56 HgChangelog.Inspector insp = new HgChangelog.Inspector() { 111 for (BranchInfo bi : incompleteBranches) {
57 112 LinkedList<Nodeid> closedHeads = new LinkedList<Nodeid>();
58 public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) { 113 for (Nodeid h : bi.getHeads()) {
59 String branchName = cset.branch(); 114 if ("1".equals(repo.getChangelog().changeset(h).extras().get("close"))) {
60 if (!branchStart.containsKey(branchName)) { 115 closedHeads.add(h);
61 branchStart.put(branchName, nodeid); 116 }
62 branchHeads.put(branchName, new LinkedList<Nodeid>()); 117 }
63 } 118 HashSet<Nodeid> earliest = new HashSet<Nodeid>(bi.getHeads());
64 branchLastSeen.remove(branchName); 119 HashSet<Nodeid> visited = new HashSet<Nodeid>();
65 if ("1".equals(cset.extras().get("close"))) { 120 ArrayList<Nodeid> parents = new ArrayList<Nodeid>(2);
66 branchHeads.get(branchName).add(nodeid); // XXX what if it still has children? 121 HashSet<Nodeid> candidate = new HashSet<Nodeid>();
67 closedBranches.add(branchName); 122 do {
123 candidate.clear();
124 for (Nodeid e : earliest) {
125 parents.clear();
126 if (pw.appendParentsOf(e, parents)) {
127 // at least one parent
128 Nodeid p1 = parents.get(0);
129 if (p1 != null && !visited.contains(p1) && bi.getName().equals(repo.getChangelog().changeset(p1).branch())) {
130 visited.add(p1);
131 candidate.add(p1);
132 }
133 Nodeid p2 = parents.size() > 1 ? parents.get(1) : null;
134 if (p2 != null && !visited.contains(p2) && bi.getName().equals(repo.getChangelog().changeset(p2).branch())) {
135 visited.add(p2);
136 candidate.add(p2);
137 }
138 }
139 }
140 if (!candidate.isEmpty()) {
141 earliest.clear();
142 earliest.addAll(candidate);
143 }
144 } while (!candidate.isEmpty());
145 // earliest can't be empty, we've started with non-empty heads.
146 Nodeid first = null;
147 if (earliest.size() == 1) {
148 first = earliest.iterator().next();
68 } else { 149 } else {
69 if (pw.hasChildren(nodeid)) { 150 int earliestRevNum = Integer.MAX_VALUE;
70 // children may be in another branch 151 for (Nodeid e : earliest) {
71 // and unless we later came across another element from this branch, 152 int x = repo.getChangelog().getLocalRevision(e);
72 // we need to record all these as valid heads 153 if (x < earliestRevNum) {
73 // XXX what about next case: head1 with children in different branch, and head2 without children 154 earliestRevNum = x;
74 // head1 would get lost 155 first = e;
75 branchLastSeen.put(branchName, nodeid); 156 }
157 }
158 }
159 assert first != null;
160 System.out.println("Updated branch " + bi.getName());
161 branches.put(bi.getName(), new BranchInfo(bi.getName(), first, bi.getHeads().toArray(new Nodeid[0]), closedHeads.size() == bi.getHeads().size()));
162 }
163 }
164 */
165 if (lastCached != repo.getChangelog().getLastRevision()) {
166 final HgChangelog.ParentWalker pw = repo.getChangelog().new ParentWalker();
167 pw.init();
168 ps.worked(repo.getChangelog().getRevisionCount());
169 final HashMap<String, Nodeid> branchStart = new HashMap<String, Nodeid>();
170 final HashMap<String, Nodeid> branchLastSeen = new HashMap<String, Nodeid>();
171 final HashMap<String, List<Nodeid>> branchHeads = new HashMap<String, List<Nodeid>>();
172 final HashSet<String> closedBranches = new HashSet<String>();
173 HgChangelog.Inspector insp = new HgChangelog.Inspector() {
174
175 public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) {
176 String branchName = cset.branch();
177 if (!branchStart.containsKey(branchName)) {
178 branchStart.put(branchName, nodeid);
179 branchHeads.put(branchName, new LinkedList<Nodeid>());
180 }
181 branchLastSeen.remove(branchName);
182 if ("1".equals(cset.extras().get("close"))) {
183 branchHeads.get(branchName).add(nodeid); // XXX what if it still has children?
184 closedBranches.add(branchName);
76 } else { 185 } else {
77 // no more children known for this node, it's (one of the) head of the branch 186 if (pw.hasChildren(nodeid)) {
78 branchHeads.get(branchName).add(nodeid); 187 // children may be in another branch
79 } 188 // and unless we later came across another element from this branch,
80 } 189 // we need to record all these as valid heads
81 ps.worked(1); 190 // XXX what about next case: head1 with children in different branch, and head2 without children
82 } 191 // head1 would get lost
83 }; 192 branchLastSeen.put(branchName, nodeid);
84 repo.getChangelog().all(insp); 193 } else {
85 for (String bn : branchLastSeen.keySet()) { 194 // no more children known for this node, it's (one of the) head of the branch
86 branchHeads.get(bn).add(branchLastSeen.get(bn)); 195 branchHeads.get(branchName).add(nodeid);
87 } 196 }
88 for (String bn : branchStart.keySet()) { 197 }
89 Nodeid[] heads = branchHeads.get(bn).toArray(new Nodeid[0]); 198 ps.worked(1);
90 BranchInfo bi = new BranchInfo(bn, branchStart.get(bn), heads, closedBranches.contains(bn)); 199 }
91 branches.put(bn, bi); 200 };
201 repo.getChangelog().range(lastCached == -1 ? 0 : lastCached+1, HgRepository.TIP, insp);
202 for (String bn : branchLastSeen.keySet()) {
203 branchHeads.get(bn).add(branchLastSeen.get(bn));
204 }
205 for (String bn : branchStart.keySet()) {
206 BranchInfo bi = branches.get(bn);
207 if (bi != null) {
208 // although heads from cache shall not intersect with heads after lastCached,
209 // use of LHS doesn't hurt (and makes sense e.g. if cache is not completely correct in my tests)
210 LinkedHashSet<Nodeid> heads = new LinkedHashSet<Nodeid>(bi.getHeads());
211 for (Nodeid oldHead : bi.getHeads()) {
212 // XXX perhaps, need pw.canReach(Nodeid from, Collection<Nodeid> to)
213 List<Nodeid> newChildren = pw.childrenOf(Collections.singletonList(oldHead));
214 if (!newChildren.isEmpty()) {
215 // likely not a head any longer,
216 // check if any new head can be reached from old one, and, if yes,
217 // do not consider that old head as head.
218 for (Nodeid newHead : branchHeads.get(bn)) {
219 if (newChildren.contains(newHead)) {
220 heads.remove(oldHead);
221 break;
222 }
223 }
224 } // else - oldHead still head for the branch
225 }
226 heads.addAll(branchHeads.get(bn));
227 bi = new BranchInfo(bn, bi.getStart(), heads.toArray(new Nodeid[0]), bi.isClosed() && closedBranches.contains(bn));
228 } else {
229 Nodeid[] heads = branchHeads.get(bn).toArray(new Nodeid[0]);
230 bi = new BranchInfo(bn, branchStart.get(bn), heads, closedBranches.contains(bn));
231 }
232 branches.put(bn, bi);
233 }
92 } 234 }
93 ps.done(); 235 ps.done();
94 } 236 }
95 237
96 public List<BranchInfo> getAllBranches() { 238 public List<BranchInfo> getAllBranches() {
106 private final String name; 248 private final String name;
107 private final List<Nodeid> heads; 249 private final List<Nodeid> heads;
108 private final boolean closed; 250 private final boolean closed;
109 private final Nodeid start; 251 private final Nodeid start;
110 252
253 // XXX in fact, few but not all branchHeads might be closed, and isClosed for whole branch is not
254 // possible to determine.
111 BranchInfo(String branchName, Nodeid first, Nodeid[] branchHeads, boolean isClosed) { 255 BranchInfo(String branchName, Nodeid first, Nodeid[] branchHeads, boolean isClosed) {
112 name = branchName; 256 name = branchName;
113 start = first; 257 start = first;
114 heads = Collections.unmodifiableList(new ArrayList<Nodeid>(Arrays.asList(branchHeads))); 258 heads = Collections.unmodifiableList(new ArrayList<Nodeid>(Arrays.asList(branchHeads)));
115 closed = isClosed; 259 closed = isClosed;
116 } 260 }
261
262 // incomplete branch, there's not enough information at the time of creation. shall be replaced with
263 // proper BI in #collect()
264 BranchInfo(String branchName, Nodeid[] branchHeads) {
265 this(branchName, Nodeid.NULL, branchHeads, false);
266 }
117 267
118 public String getName() { 268 public String getName() {
119 return name; 269 return name;
120 } 270 }
121 public boolean isClosed() { 271 /*public*/ boolean isClosed() {
122 return closed; 272 return closed;
123 } 273 }
124 public List<Nodeid> getHeads() { 274 public List<Nodeid> getHeads() {
125 return heads; 275 return heads;
126 } 276 }
127 // public Nodeid getTip() { 277 // public Nodeid getTip() {
128 // } 278 // }
129 public Nodeid getStart() { 279 /*public*/ Nodeid getStart() {
130 // first node where branch appears 280 // first node where branch appears
131 return start; 281 return start;
132 } 282 }
133 } 283 }
134 } 284 }