#
#
# add_dir "tests/db_check_branch_leaves"
# 
# add_file "tests/db_check_branch_leaves/__driver__.lua"
#  content [283652fe9b2ccf7d834f74e28aed18efb29ccb59]
# 
# patch "database.cc"
#  from [026b0f32727c3e31be115a47a4b8de251078151a]
#    to [25a7d09b691fa29743249d4151dc27bab18c7923]
# 
# patch "database.hh"
#  from [c7ae2340052b1205f3615f416adb1c58917abfd5]
#    to [654c356dcdbe48064357eaa66fb6e7c9b5a9d9b5]
# 
# patch "database_check.cc"
#  from [55d80d4456c96b241ceabd77be9872cfb7285ab6]
#    to [eb2f10d33d8a4b345982a09ccb29a3d4235c06ab]
# 
# patch "migrate_ancestry.cc"
#  from [87b81a3b30c9299f5919f8f89b154843a7171989]
#    to [790cf2e18a4653af131bdb350e9c3ee4e223e294]
# 
# patch "monotone.texi"
#  from [c3207d84cdb530e1ef24a756ae2ddcc5c3bd0a24]
#    to [e5901e819adff1d28d8e6476ea33af0b89417047]
#
============================================================
--- tests/db_check_branch_leaves/__driver__.lua	283652fe9b2ccf7d834f74e28aed18efb29ccb59
+++ tests/db_check_branch_leaves/__driver__.lua	283652fe9b2ccf7d834f74e28aed18efb29ccb59
@@ -0,0 +1,67 @@
+-- db check checks branch_leaves table
+
+-- a bug in mtn 0.46 caused extra entries to be left in the
+-- branch_leaves table; this shows that 'db check' identifies that,
+-- and 'regenerate_caches' fixes it.
+
+mtn_setup()
+
+-- create two heads on testbranch, one head on otherbranch
+addfile("file1", "rev_A")
+commit("testbranch", "rev_A")
+base = base_revision()
+
+writefile("file1", "rev_a")
+commit("testbranch", "rev_a")
+rev_a = base_revision()
+
+revert_to(base)
+
+addfile("file2", "rev_b")
+commit("testbranch", "rev_b")
+rev_b = base_revision()
+
+writefile("file2", "rev_c")
+commit("otherbranch", "rev_c")
+rev_c = base_revision()
+
+-- db should be ok
+check(mtn("db", "check"), 0, false, false)
+
+-- branch names are stored as binary blobs in the database;
+-- these values are from sqlite3 test.db .dump branch_leaves.
+testbranch_name = "X'746573746272616E6368'"
+otherbranch_name = "X'6F746865726272616E6368'"
+
+-- add an extra head on 'testbranch' in branch_leaves
+check(mtn("db", "execute", "INSERT INTO branch_leaves (branch, revision_id) VALUES (" .. testbranch_name .. ", x'" .. base .. "');"), false, false)
+
+-- delete 'otherbranch' from branch_leaves
+check(mtn("db", "execute", "DELETE FROM branch_leaves WHERE branch=" .. otherbranch_name .. ";"), false, false)
+
+-- add an extra branch in branch_leaves; it doesn't matter that the
+-- name is not actually binary
+check(mtn("db", "execute", "INSERT INTO branch_leaves (branch, revision_id) VALUES ('bogusbranch', x'" .. base .. "');"), false, false)
+
+-- db is not ok
+check(mtn("db", "check"), 1, false, true)
+check(qgrep("cached branch 'bogusbranch' not used", "stderr"))
+check(qgrep("branch 'otherbranch' not cached", "stderr"))
+check(qgrep("branch 'testbranch' wrong head count", "stderr"))
+
+-- fix it
+check(mtn("db", "regenerate_caches"), 0, false, false)
+
+check(mtn("db", "check"), 0, false, false)
+
+-- double check
+check(mtn("automate", "heads", "testbranch"), 0, true, false)
+check(readfile("stdout") == rev_a .. "\n" .. rev_b .. "\n")
+
+check(mtn("automate", "heads", "otherbranch"), 0, true, false)
+check(readfile("stdout") == rev_c .. "\n")
+
+check(mtn("automate", "heads", "bogusbranch"), 0, true, false)
+check(readfile("stdout") == "")
+
+-- end of file
============================================================
--- database.cc	026b0f32727c3e31be115a47a4b8de251078151a
+++ database.cc	25a7d09b691fa29743249d4151dc27bab18c7923
@@ -1,3 +1,4 @@
+// Copyright (C) 2010 Stephen Leake <address@hidden>
 // Copyright (C) 2002 Graydon Hoare <address@hidden>
 //
 // This program is made available under the GNU GPL version 2.0 or
@@ -2995,6 +2996,12 @@ database::delete_existing_heights()
   imp->execute(query("DELETE FROM heights"));
 }
 
+void
+database::delete_existing_branch_leaves()
+{
+  imp->execute(query("DELETE FROM branch_leaves"));
+}
+
 /// Deletes one revision from the local database.
 /// @see kill_rev_locally
 void
@@ -3039,16 +3046,23 @@ void
 }
 
 void
-database::recalc_branch_leaves(cert_value const & name)
+database::compute_branch_leaves(cert_value const & branch_name, set<revision_id> & revs)
 {
-  imp->execute(query("DELETE FROM branch_leaves WHERE branch = ?") % blob(name()));
+  imp->execute(query("DELETE FROM branch_leaves WHERE branch = ?") % blob(branch_name()));
+  get_revisions_with_cert(cert_name("branch"), branch_name, revs);
+  erase_ancestors(*this, revs);
+}
+
+void
+database::recalc_branch_leaves(cert_value const & branch_name)
+{
+  imp->execute(query("DELETE FROM branch_leaves WHERE branch = ?") % blob(branch_name()));
   set<revision_id> revs;
-  get_revisions_with_cert(cert_name("branch"), name, revs);
-  erase_ancestors(*this, revs);
+  compute_branch_leaves(branch_name, revs);
   for (set<revision_id>::const_iterator i = revs.begin(); i != revs.end(); ++i)
     {
       imp->execute(query("INSERT INTO branch_leaves (branch, revision_id) "
-                         "VALUES (?, ?)") % blob(name()) % blob((*i).inner()()));
+                         "VALUES (?, ?)") % blob(branch_name()) % blob((*i).inner()()));
     }
 }
 
@@ -3608,6 +3622,14 @@ database::record_as_branch_leaf(cert_val
         }
     }
 
+  // This check is needed for this case:
+  //
+  //  r1 (branch1)
+  //  |
+  //  r2 (branch2)
+  //  |
+  //  r3 (branch1)
+
   if (!all_parents_were_leaves)
     {
       for (set<revision_id>::const_iterator r = current_leaves.begin();
============================================================
--- database.hh	c7ae2340052b1205f3615f416adb1c58917abfd5
+++ database.hh	654c356dcdbe48064357eaa66fb6e7c9b5a9d9b5
@@ -1,3 +1,4 @@
+// Copyright (C) 2010 Stephen Leake <address@hidden>
 // Copyright (C) 2002 Graydon Hoare <address@hidden>
 //
 // This program is made available under the GNU GPL version 2.0 or
@@ -312,9 +313,10 @@ public:
   outdated_indicator get_branch_leaves(cert_value const & value,
                                        std::set<revision_id> & revisions);
 
-private:
-  void recalc_branch_leaves(cert_value const & value);
-public:
+  // used by check_db, regenerate_caches
+  void compute_branch_leaves(cert_value const & branch_name, std::set<revision_id> & revs);
+  void recalc_branch_leaves(cert_value const & branch_name);
+  void delete_existing_branch_leaves();
 
   // Used through project.cc
   outdated_indicator get_revision_certs(revision_id const & ident,
============================================================
--- database_check.cc	55d80d4456c96b241ceabd77be9872cfb7285ab6
+++ database_check.cc	eb2f10d33d8a4b345982a09ccb29a3d4235c06ab
@@ -1,3 +1,4 @@
+// Copyright (C) 2010 Stephen Leake <address@hidden>
 // Copyright (C) 2005 Derek Scherger <address@hidden>
 //
 // This program is made available under the GNU GPL version 2.0 or
@@ -133,6 +134,14 @@ struct checked_height {
   checked_height(): found(false), unique(false), sensible(true) {}
 };
 
+struct checked_branch {
+  bool used;
+  bool heads_ok;
+  bool cached;
+
+  checked_branch(): used(false), heads_ok(false), cached(false) {}
+};
+
 /*
  * check integrity of the SQLite database
  */
@@ -597,6 +606,62 @@ static void
 }
 
 static void
+check_branch_leaves(database & db, map<string, checked_branch> & checked_branches)
+{
+  // We don't assume db.get_branches is right, because that uses
+  // branch_leaves, and we are checking to see if branch_leaves is ok.
+
+  vector<cert> all_branch_certs;
+  set<string> seen_branches;
+  vector<string> cached_branches;
+
+  db.get_branches (cached_branches);
+
+  L(FL("checking %d branches") % cached_branches.size());
+
+  db.get_revision_certs(branch_cert_name, all_branch_certs);
+
+  // we assume cached_branches is close enough for the ticker.
+  ticker ticks(_("branches"), "b", cached_branches.size());
+
+  for (vector<cert>::const_iterator i = all_branch_certs.begin(); i != all_branch_certs.end(); ++i)
+    {
+      string const name = i->value();
+
+      std::pair<set<string>::iterator, bool> inserted = seen_branches.insert(name);
+
+      if (inserted.second)
+        {
+          checked_branches[name].used = true;
+
+          checked_branches[name].cached =
+            find(cached_branches.begin(), cached_branches.end(), name) != cached_branches.end();
+
+          set<revision_id> cached_leaves;
+          set<revision_id> computed_leaves;
+
+          db.get_branch_leaves(i->value, cached_leaves);
+          db.compute_branch_leaves(i->value, computed_leaves);
+
+          checked_branches[name].heads_ok = cached_leaves == computed_leaves;
+          ++ticks;
+        }
+    }
+
+  for (vector<string>::const_iterator i = cached_branches.begin(); i != cached_branches.end(); ++i)
+    {
+      string const name = *i;
+
+      if (seen_branches.find(name) == seen_branches.end())
+        {
+          checked_branches[name].used = false;
+          checked_branches[name].cached = true;
+          checked_branches[name].heads_ok = false;
+        }
+    }
+}
+
+static void
 report_files(map<file_id, checked_file> const & checked_files,
              size_t & missing_files,
              size_t & unreferenced_files)
@@ -893,6 +958,32 @@ report_heights(map<revision_id, checked_
     }
 }
 
+static void
+report_branches(map<string, checked_branch> const & checked_branches,
+                size_t & extra_branches,
+                size_t & bad_branches,
+                size_t & missing_branches)
+{
+  for (map<string, checked_branch>::const_iterator i = checked_branches.begin(); i != checked_branches.end(); ++i)
+    {
+      if (!i->second.used)
+        {
+          extra_branches++;
+          P(F("cached branch '%s' not used") % i->first);
+        }
+      else if (!i->second.cached)
+        {
+          missing_branches++;
+          P(F("branch '%s' not cached") % i->first);
+        }
+      else if (!i->second.heads_ok)
+        {
+          bad_branches ++;
+          P(F("branch '%s' wrong head count") % i->first);
+        }
+    }
+}
+
 void
 check_db(database & db)
 {
@@ -902,6 +993,7 @@ check_db(database & db)
   map<revision_id, checked_revision> checked_revisions;
   map<key_id, checked_key> checked_keys;
   map<revision_id, checked_height> checked_heights;
+  map<string, checked_branch> checked_branches;
 
   size_t missing_files = 0;
   size_t unreferenced_files = 0;
@@ -931,6 +1023,10 @@ check_db(database & db)
   size_t duplicate_heights = 0;
   size_t incorrect_heights = 0;
 
+  size_t extra_branches = 0;
+  size_t bad_branches = 0;
+  size_t missing_branches = 0;
+
   transaction_guard guard(db, false);
 
   check_db_integrity_check(db);
@@ -945,6 +1041,7 @@ check_db(database & db)
   check_certs(db, checked_revisions, checked_keys, total_certs);
   check_heights(db, checked_heights);
   check_heights_relation(db, checked_heights);
+  check_branch_leaves(db, checked_branches);
 
   report_files(checked_files, missing_files, unreferenced_files);
 
@@ -968,8 +1065,10 @@ check_db(database & db)
   report_heights(checked_heights,
                  missing_heights, duplicate_heights, incorrect_heights);
 
+  report_branches(checked_branches, extra_branches, bad_branches, missing_branches);
+
   // NOTE: any new sorts of problems need to have added:
-  //   -- a message here, that tells the use about them
+  //   -- a message here, that tells the user about them
   //   -- entries in one _or both_ of the sums calculated at the end
   //   -- an entry added to the manual, which describes in detail why the
   //      error occurs and what it means to the user
@@ -1024,6 +1123,13 @@ check_db(database & db)
   if (incorrect_heights > 0)
     W(F("%d incorrect heights") % incorrect_heights);
 
+  if (extra_branches > 0)
+    W(F("%d branches cached but not used") % extra_branches);
+  if (bad_branches > 0)
+    W(F("%d branches with incorrect head count") % bad_branches);
+  if (missing_branches > 0)
+    W(F("%d branches missing from branch cache") % missing_branches);
+
   size_t total = missing_files + unreferenced_files +
     unreferenced_rosters + incomplete_rosters +
     missing_revisions + incomplete_revisions +
@@ -1034,7 +1140,9 @@ check_db(database & db)
     missing_certs + mismatched_certs +
     unchecked_sigs + bad_sigs +
     missing_keys +
-    missing_heights + duplicate_heights + incorrect_heights;
+    missing_heights + duplicate_heights + incorrect_heights +
+    extra_branches + bad_branches + missing_branches;
+
   // unreferenced files and rosters and mismatched certs are not actually
   // serious errors; odd, but nothing will break.
   size_t serious = missing_files +
@@ -1046,15 +1154,17 @@ check_db(database & db)
     missing_certs +
     unchecked_sigs + bad_sigs +
     missing_keys +
-    missing_heights + duplicate_heights + incorrect_heights;
+    missing_heights + duplicate_heights + incorrect_heights+
+    extra_branches + bad_branches + missing_branches;
 
-  P(F("check complete: %d files; %d rosters; %d revisions; %d keys; %d certs; %d heights")
+  P(F("check complete: %d files; %d rosters; %d revisions; %d keys; %d certs; %d heights; %d branches")
     % checked_files.size()
     % checked_rosters.size()
     % checked_revisions.size()
     % checked_keys.size()
     % total_certs
-    % checked_heights.size());
+    % checked_heights.size()
+    % checked_branches.size());
   P(F("total problems detected: %d (%d serious)") % total % serious);
   if (serious)
     {
============================================================
--- migrate_ancestry.cc	87b81a3b30c9299f5919f8f89b154843a7171989
+++ migrate_ancestry.cc	790cf2e18a4653af131bdb350e9c3ee4e223e294
@@ -1,3 +1,4 @@
+// Copyright (C) 2010 Stephen Leake <address@hidden>
 // Copyright (C) 2004 Graydon Hoare <address@hidden>
 //
 // This program is made available under the GNU GPL version 2.0 or
@@ -986,31 +987,58 @@ regenerate_caches(database & db)
 
   db.ensure_open_for_cache_reset();
 
-  transaction_guard guard(db);
+  {
+    transaction_guard guard(db);
 
-  db.delete_existing_rosters();
-  db.delete_existing_heights();
+    db.delete_existing_rosters();
+    db.delete_existing_heights();
 
-  vector<revision_id> sorted_ids;
-  allrevs_toposorted(db, sorted_ids);
+    vector<revision_id> sorted_ids;
+    allrevs_toposorted(db, sorted_ids);
 
-  ticker done(_("regenerated"), "r", 5);
-  done.set_total(sorted_ids.size());
+    ticker done(_("regenerated"), "r", 5);
+    done.set_total(sorted_ids.size());
 
-  for (std::vector<revision_id>::const_iterator i = sorted_ids.begin();
-       i != sorted_ids.end(); ++i)
-    {
-      revision_t rev;
-      revision_id const & rev_id = *i;
-      db.get_revision(rev_id, rev);
-      db.put_roster_for_revision(rev_id, rev);
-      db.put_height_for_revision(rev_id, rev);
-      ++done;
-    }
+    for (std::vector<revision_id>::const_iterator i = sorted_ids.begin();
+         i != sorted_ids.end(); ++i)
+      {
+        revision_t rev;
+        revision_id const & rev_id = *i;
+        db.get_revision(rev_id, rev);
+        db.put_roster_for_revision(rev_id, rev);
+        db.put_height_for_revision(rev_id, rev);
+        ++done;
+      }
 
-  guard.commit();
+    guard.commit();
+  }
 
   P(F("finished regenerating cached rosters and heights"));
+
+  P(F("regenerating cached branches"));
+  {
+    transaction_guard guard(db);
+
+    db.delete_existing_branch_leaves();
+
+    vector<cert> all_branch_certs;
+    db.get_revision_certs(branch_cert_name, all_branch_certs);
+    set<string> seen_branches;
+    for (vector<cert>::const_iterator i = all_branch_certs.begin(); i != all_branch_certs.end(); ++i)
+      {
+        string const name = i->value();
+
+        std::pair<set<string>::iterator, bool> inserted = seen_branches.insert(name);
+
+        if (inserted.second)
+          {
+            db.recalc_branch_leaves (i->value);
+          }
+      }
+    guard.commit();
+  }
+  P(F("finished regenerating cached branches"));
+
 }
 
 // Local Variables:
============================================================
--- monotone.texi	c3207d84cdb530e1ef24a756ae2ddcc5c3bd0a24
+++ monotone.texi	e5901e819adff1d28d8e6476ea33af0b89417047
@@ -6384,6 +6384,12 @@ @section Database
 using @command{pubkey} on that database to create a public key packet,
 which can be loaded into your database with @command{read}.
 
address@hidden branches not used or with incorrect head count or missing
+in the cache of branch heads. This is a serious problem; it suggests
+the presence of a bug in monotone's caching system, but does not
+involve data loss; please report this on the monotone mailing
+list. You can fix it by running @command{db regenerate_caches}.
+
 @end itemize
 
 This command also verifies that the @sc{sha1} hash of every file, manifest,