# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1316842145 -7200
# Node ID 3f40262153a4d9fd52fc3f4a0aeb6e7a622ef53f
# Parent  2f2ab5c27f414f08b7971f8894b499a25d8e6b81
Recognize closed branches

diff -r 2f2ab5c27f41 -r 3f40262153a4 cmdline/org/tmatesoft/hg/console/Main.java
--- a/cmdline/org/tmatesoft/hg/console/Main.java	Sat Sep 24 04:06:27 2011 +0200
+++ b/cmdline/org/tmatesoft/hg/console/Main.java	Sat Sep 24 07:29:05 2011 +0200
@@ -86,7 +86,7 @@
 
 	public static void main(String[] args) throws Exception {
 		Main m = new Main(args);
-		m.buildFileLog();
+//		m.buildFileLog();
 //		m.testConsoleLog();
 //		m.testTreeTraversal();
 //		m.testRevisionMap();
@@ -97,7 +97,7 @@
 //		m.testCatAtCsetRevision();
 //		m.testMergeState();
 //		m.testFileStatus();
-//		m.dumpBranches();
+		m.dumpBranches();
 //		m.inflaterLengthException();
 //		m.dumpIgnored();
 //		m.dumpDirstate();
@@ -362,15 +362,16 @@
 		System.out.println("1:" + (System.currentTimeMillis() - start0));
 		for (HgBranches.BranchInfo bi : b.getAllBranches()) {
 			System.out.print(bi.getName());
-//			if (bi.isClosed()) {
-//				System.out.print("!");
-//			}
 //			System.out.print(" ");
 //			System.out.print(bi.getStart());
 			System.out.print(" ");
-			System.out.println(bi.getHeads());
+			System.out.print(bi.getHeads());
+			if (bi.isClosed()) {
+				System.out.print(" x ");
+			}
+			System.out.println();
 		}
-		b.writeCache();
+//		b.writeCache();
 //		final long start = System.currentTimeMillis();
 //		for (int i = 0; i < 10; i++) {
 //			b.collect(ProgressSupport.Factory.get(null));
diff -r 2f2ab5c27f41 -r 3f40262153a4 src/org/tmatesoft/hg/repo/HgBranches.java
--- a/src/org/tmatesoft/hg/repo/HgBranches.java	Sat Sep 24 04:06:27 2011 +0200
+++ b/src/org/tmatesoft/hg/repo/HgBranches.java	Sat Sep 24 07:29:05 2011 +0200
@@ -22,11 +22,10 @@
 import java.io.FileReader;
 import java.io.FileWriter;
 import java.io.IOException;
-import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
-import java.util.HashSet;
+import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
@@ -63,6 +62,7 @@
 		BufferedReader br = null;
 		final Pattern spacePattern = Pattern.compile(" ");
 		try {
+			final LinkedHashMap<String, List<Nodeid>> branchHeads = new LinkedHashMap<String, List<Nodeid>>();
 			br = new BufferedReader(new FileReader(branchheadsCache));
 			String line = br.readLine();
 			if (line == null || line.trim().length() == 0) {
@@ -74,18 +74,22 @@
 			//
 			while ((line = br.readLine()) != null) {
 				String[] elements = spacePattern.split(line.trim());
-				if (elements.length < 2) {
+				if (elements.length != 2) {
 					// bad entry
 					continue;
 				}
-				Nodeid[] branchHeads = new Nodeid[elements.length - 1];
-				for (int i = 0; i < elements.length - 1; i++) {
-					branchHeads[i] = Nodeid.fromAscii(elements[i]);
-				}
 				// I assume split returns substrings of the original string, hence copy of a branch name
 				String branchName = new String(elements[elements.length-1]);
-				BranchInfo bi = new BranchInfo(branchName, branchHeads);
-				branches.put(branchName, bi);
+				List<Nodeid> heads = branchHeads.get(elements[1]);
+				if (heads == null) {
+					branchHeads.put(branchName, heads = new LinkedList<Nodeid>());
+				}
+				heads.add(Nodeid.fromAscii(elements[0]));
+			}
+			for (Map.Entry<String, List<Nodeid>> e : branchHeads.entrySet()) {
+				Nodeid[] heads = e.getValue().toArray(new Nodeid[e.getValue().size()]);
+				BranchInfo bi = new BranchInfo(e.getKey(), heads);
+				branches.put(e.getKey(), bi);
 			}
 			return lastInCache;
 		} catch (IOException ex) {
@@ -171,10 +175,14 @@
 			final HgChangelog.ParentWalker pw = repo.getChangelog().new ParentWalker();
 			pw.init();
 			ps.worked(repo.getChangelog().getRevisionCount());
+			// first revision branch found at
 			final HashMap<String, Nodeid> branchStart = new HashMap<String, Nodeid>();
+			// last revision seen for the branch
 			final HashMap<String, Nodeid> branchLastSeen = new HashMap<String, Nodeid>();
+			// revisions from the branch that have no children at all
 			final HashMap<String, List<Nodeid>> branchHeads = new HashMap<String, List<Nodeid>>();
-			final HashSet<String> closedBranches = new HashSet<String>();
+			// revisions that are immediate children of a node from a given branch 
+			final HashMap<String, List<Nodeid>> branchHeadCandidates = new HashMap<String, List<Nodeid>>();
 			HgChangelog.Inspector insp = new HgChangelog.Inspector() {
 				
 				public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) {
@@ -182,29 +190,39 @@
 					if (!branchStart.containsKey(branchName)) {
 						branchStart.put(branchName, nodeid);
 						branchHeads.put(branchName, new LinkedList<Nodeid>());
-					}
-					branchLastSeen.remove(branchName);
-					if ("1".equals(cset.extras().get("close"))) {
-						branchHeads.get(branchName).add(nodeid); // XXX what if it still has children?
-								closedBranches.add(branchName);
+						branchHeadCandidates.put(branchName, new LinkedList<Nodeid>());
 					} else {
-						if (pw.hasChildren(nodeid)) {
-							// children may be in another branch
-							// and unless we later came across another element from this branch,
-							// we need to record all these as valid heads
-							// XXX what about next case: head1 with children in different branch, and head2 without children
-							// head1 would get lost
-							branchLastSeen.put(branchName, nodeid);
-						} else {
-							// no more children known for this node, it's (one of the) head of the branch
-							branchHeads.get(branchName).add(nodeid);
+						final List<Nodeid> headCandidates = branchHeadCandidates.get(branchName);
+						if (headCandidates.remove(nodeid)) {
+							// no need to keep parent, as we found at least 1 child thereof to be at the same branch
+							branchLastSeen.remove(branchName);
 						}
 					}
+					List<Nodeid> immediateChildren = pw.directChildren(nodeid);
+					if (immediateChildren.size() > 0) {
+						// 1) children may be in another branch
+						// and unless we later came across another element from this branch,
+						// we need to record all these as potential heads
+						//
+						// 2) head1 with children in different branch, and head2 in this branch without children
+						branchLastSeen.put(branchName, nodeid);
+						branchHeadCandidates.get(branchName).addAll(immediateChildren);
+					} else {
+						// no more children known for this node, it's (one of the) head of the branch
+						branchHeads.get(branchName).add(nodeid);
+					}
 					ps.worked(1);
 				}
 			}; 
 			repo.getChangelog().range(lastCached == -1 ? 0 : lastCached+1, HgRepository.TIP, insp);
+//			System.out.println("HEAD CANDIDATES>>>");
+//			for (String bn : branchHeadCandidates.keySet()) {
+//				System.out.println(bn + ":" + branchHeadCandidates.get(bn).toString());
+//			}
+//			System.out.println("HEAD CANDIDATES<<<");
+			// those last seen revisions from the branch that had no children from the same branch are heads.
 			for (String bn : branchLastSeen.keySet()) {
+				// these are inactive branches? - there were children, but not from the same branch?
 				branchHeads.get(bn).add(branchLastSeen.get(bn));
 			}
 			for (String bn : branchStart.keySet()) {
@@ -229,14 +247,19 @@
 						} // else - oldHead still head for the branch
 					}
 					heads.addAll(branchHeads.get(bn));
-					bi = new BranchInfo(bn, bi.getStart(), heads.toArray(new Nodeid[0]), bi.isClosed() && closedBranches.contains(bn));
+					bi = new BranchInfo(bn, bi.getStart(), heads.toArray(new Nodeid[0]));
 				} else {
 					Nodeid[] heads = branchHeads.get(bn).toArray(new Nodeid[0]);
-					bi = new BranchInfo(bn, branchStart.get(bn), heads, closedBranches.contains(bn));
+					bi = new BranchInfo(bn, branchStart.get(bn), heads);
 				}
 				branches.put(bn, bi);
 			}
 		}
+		final HgChangelog clog = repo.getChangelog();
+		final HgChangelog.RevisionMap rmap = clog.new RevisionMap().init();
+		for (BranchInfo bi : branches.values()) {
+			bi.validate(clog, rmap);
+		}
 		ps.done();
 	}
 
@@ -295,29 +318,70 @@
 
 	public static class BranchInfo {
 		private final String name;
-		private final List<Nodeid> heads;
-		private final boolean closed;
+		private List<Nodeid> heads;
+		private boolean closed;
 		private final Nodeid start;
 
 		// XXX in fact, few but not all branchHeads might be closed, and isClosed for whole branch is not
 		// possible to determine.
-		BranchInfo(String branchName, Nodeid first, Nodeid[] branchHeads, boolean isClosed) {
+		BranchInfo(String branchName, Nodeid first, Nodeid[] branchHeads) {
 			name = branchName;
 			start = first;
-			heads = Collections.unmodifiableList(new ArrayList<Nodeid>(Arrays.asList(branchHeads)));
-			closed = isClosed;
+			heads = Arrays.asList(branchHeads);
 		}
 		
 		// incomplete branch, there's not enough information at the time of creation. shall be replaced with
 		// proper BI in #collect()
 		BranchInfo(String branchName, Nodeid[] branchHeads) {
-			this(branchName, Nodeid.NULL, branchHeads, false);
+			this(branchName, Nodeid.NULL, branchHeads);
+		}
+		
+		void validate(HgChangelog clog, HgChangelog.RevisionMap rmap) {
+			int[] localCset = new int[heads.size()];
+			int i = 0;
+			for (Nodeid h : heads) {
+				localCset[i++] = rmap.localRevision(h);
+			}
+			// [0] tipmost, [1] tipmost open
+			final Nodeid[] tipmost = new Nodeid[] {null, null};
+			final boolean[] allClosed = new boolean[] { true };
+			clog.range(new HgChangelog.Inspector() {
+				
+				public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) {
+					assert heads.contains(nodeid);
+					tipmost[0] = nodeid;
+					if (!"1".equals(cset.extras().get("close"))) {
+						tipmost[1] = nodeid;
+						allClosed[0] = false;
+					}
+				}
+			}, localCset);
+			closed = allClosed[0];
+			Nodeid[] outcome = new Nodeid[localCset.length];
+			i = 0;
+			if (!closed && tipmost[1] != null) { 
+				outcome[i++] = tipmost[1];
+				if (i < outcome.length && !tipmost[0].equals(tipmost[1])) {
+					outcome[i++] = tipmost[0];
+				}
+			} else {
+				outcome[i++] = tipmost[0];
+			}
+			for (Nodeid h : heads) {
+				if (!h.equals(tipmost[0]) && !h.equals(tipmost[1])) {
+					outcome[i++] = h;
+				}
+			}
+			heads = Arrays.asList(outcome);
 		}
 
 		public String getName() {
 			return name;
 		}
-		/*public*/ boolean isClosed() {
+		/**
+		 * @return <code>true</code> if all heads of this branch are marked as closed
+		 */
+		public boolean isClosed() {
 			return closed;
 		}
 		public List<Nodeid> getHeads() {
diff -r 2f2ab5c27f41 -r 3f40262153a4 src/org/tmatesoft/hg/repo/Revlog.java
--- a/src/org/tmatesoft/hg/repo/Revlog.java	Sat Sep 24 04:06:27 2011 +0200
+++ b/src/org/tmatesoft/hg/repo/Revlog.java	Sat Sep 24 07:29:05 2011 +0200
@@ -357,6 +357,23 @@
 		}
 		
 		/**
+		 * @return revisions that have supplied revision as their immediate parent
+		 */
+		public List<Nodeid> directChildren(Nodeid nid) {
+			LinkedList<Nodeid> result = new LinkedList<Nodeid>();
+			int x = Arrays.binarySearch(sorted, nid);
+			assertSortedIndex(x);
+			nid = sorted[x]; // canonical instance
+			int start = sorted2natural[x];
+			for (int i = start + 1; i < sequential.length; i++) {
+				if (nid == firstParent[i] || nid == secondParent[i]) {
+					result.add(sequential[i]);
+				}
+			}
+			return result;
+		}
+		
+		/**
 		 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog.
 		 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents. 
 		 */
diff -r 2f2ab5c27f41 -r 3f40262153a4 test-data/test-repos.jar
Binary file test-data/test-repos.jar has changed
diff -r 2f2ab5c27f41 -r 3f40262153a4 test/org/tmatesoft/hg/test/TestBranches.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/org/tmatesoft/hg/test/TestBranches.java	Sat Sep 24 07:29:05 2011 +0200
@@ -0,0 +1,73 @@
+/*
+ * Copyright (c) 2011 TMate Software Ltd
+ *  
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * For information on how to redistribute this software under
+ * the terms of a license other than GNU General Public License
+ * contact TMate Software at support@hg4j.com
+ */
+package org.tmatesoft.hg.test;
+
+import static org.junit.Assert.*;
+
+import org.junit.Assert;
+import org.junit.Test;
+import org.tmatesoft.hg.repo.HgBranches;
+import org.tmatesoft.hg.repo.HgBranches.BranchInfo;
+import org.tmatesoft.hg.repo.HgRepository;
+
+/**
+ *
+ * @author Artem Tikhomirov
+ * @author TMate Software Ltd.
+ */
+public class TestBranches {
+
+	@Test
+	public void testClosedInactiveBranches() throws Exception {
+		HgRepository repo = Configuration.get().find("branches-1");
+		HgBranches branches = repo.getBranches();
+		BranchInfo b1 = branches.getBranch("branch1");
+		assertNotNull(b1);
+		assertTrue(b1.isClosed());
+		assertEquals(2, b1.getHeads().size());
+		// order is important!
+		assertEquals("131e84b878d25b5eab7f529ebb35e57b2a439db7", b1.getHeads().get(0).toString());
+		assertEquals("c993cda1f5a7afd771efa87fe95fb7c5f73169e6", b1.getHeads().get(1).toString());
+		//
+		BranchInfo b2 = branches.getBranch("branch2");
+		assertNotNull(b2);
+		assertFalse(b2.isClosed());
+		assertEquals(2, b2.getHeads().size());
+		assertEquals("537f548adfd7eb9ce2a73ed7e7ca163eb1b61401", b2.getHeads().get(0).toString());
+		assertEquals("e698babd9479b1c07e0ed3155f5e290ee15affed", b2.getHeads().get(1).toString());
+		//
+		BranchInfo b3 = branches.getBranch("branch3");
+		assertNotNull(b3);
+		assertFalse(b3.isClosed());
+		assertEquals(1, b3.getHeads().size());
+		assertEquals("b103f33723f37c7bb4b81d74a66135d6fdaf0ced", b3.getHeads().get(0).toString());
+		//
+		BranchInfo b4 = branches.getBranch("branch4");
+		assertNotNull(b4);
+		assertFalse(b4.isClosed());
+//		assertEquals(2, b4.getHeads().size());
+		assertEquals("fceabd402f0193fb30605aed0ee3a9d5feb99f60", b4.getHeads().get(0).toString());
+		// FIXME second branch is not present when HgBranches builds cache itself!!!
+//		assertEquals("892b6a504be7835f1748ba632fe15a9389d4479b", b4.getHeads().get(1).toString());
+		//
+		BranchInfo b5 = branches.getBranch("branch5");
+		assertNotNull(b5);
+		assertFalse(b5.isClosed());
+		assertEquals(1, b5.getHeads().size());
+		assertEquals("9cb6ad32b9074021356c38050e2aab6addba4393", b5.getHeads().get(0).toString());
+	}
+}