#
#
# patch "database.cc"
#  from [7a4405968e4cf9fa63f6eae6f5ea99c8c535d30f]
#    to [73e1ff5267346362c8e78501a242a695f715c105]
# 
# patch "database.hh"
#  from [98befdf9afa2b46b4e4542c0950c036defa488f9]
#    to [b64b02b9a2527a475360ad20edfefbe705220b87]
# 
# patch "graph.cc"
#  from [86243bb8a207752b460cfd68dff6abc98c307e9b]
#    to [a3dd162873e3af5f00dab61160ef617850953771]
# 
# patch "graph.hh"
#  from [9849fd1ce316f39677da9e81cf9716c676b02494]
#    to [480c7937c852b3f28093bca1f42b6d650df596f5]
# 
# patch "revision.cc"
#  from [ca25b6d7baaae299e272001bc7e4a8ffeb9b946e]
#    to [be90c9703d54c9860a9bae8b233d5698e6b8e087]
# 
# patch "roster.cc"
#  from [dfb22c69788162515c92abc16b52eee9c1e4f75e]
#    to [beafb1f44ceec187d07239c3f202850bddfa8aef]
# 
# patch "roster.hh"
#  from [0df1174eb4998443af6c94143f46eb3f8b383f31]
#    to [395efe568c9d1d40b50dde17d11a160a22a51298]
# 
# patch "vocab.cc"
#  from [842d7558aa658249160db34543481792f4a7a081]
#    to [77490ecc652abc35eed9ed350df7371ebd5010a1]
# 
# patch "vocab.hh"
#  from [2bd8cac9e74aecc7e0de12a440d08fd9153bfdfa]
#    to [8bd9123edb30504b7220d5da35de033de5bd376e]
#
============================================================
--- database.cc	7a4405968e4cf9fa63f6eae6f5ea99c8c535d30f
+++ database.cc	73e1ff5267346362c8e78501a242a695f715c105
@@ -1814,7 +1814,7 @@ void
 
 
 void
-database::get_revision_ancestry(rev_ancestry_map & graph)
+database::get_revision_ancestry(ancestry_map & graph)
 {
   // FIXME: possibly update the callers to acquire a shared_ptr<... const>?
   // This might require some COW trickiness, though, if we want to preserve
@@ -3293,6 +3293,17 @@ database::ensure_ancestry_maps_loaded()
     }
 }
 
+struct db_height_store : height_store
+{
+  db_height_store(database & db) : db(db) {}
+  virtual void get_height(revision_id const & rid, rev_height & height) const
+  {
+    db.get_rev_height(rid, height);
+  }
+  
+  mutable database & db;
+};
+
 void
 database::get_uncommon_ancestors(revision_id const & a,
                                  revision_id const & b,
@@ -3300,8 +3311,9 @@ database::get_uncommon_ancestors(revisio
                                  set<revision_id> & b_uncommon_ancs)
 {
   ensure_ancestry_maps_loaded();
+  db_height_store heights(*this);
   // call the generic (and testable) function in graph.cc
-  ::get_uncommon_ancestors(a, b, *child_to_parent_map,
+  ::get_uncommon_ancestors(a, b, *child_to_parent_map, heights,
                            a_uncommon_ancs, b_uncommon_ancs);
 }
 
============================================================
--- database.hh	98befdf9afa2b46b4e4542c0950c036defa488f9
+++ database.hh	b64b02b9a2527a475360ad20edfefbe705220b87
@@ -293,7 +293,7 @@ public:
   // --== The ancestry graph ==--
   //
 public:
-  void get_revision_ancestry(rev_ancestry_map & graph);
+  void get_revision_ancestry(ancestry_map & graph);
 
   void get_revision_parents(revision_id const & ident,
                            std::set<revision_id> & parents);
============================================================
--- graph.cc	86243bb8a207752b460cfd68dff6abc98c307e9b
+++ graph.cc	a3dd162873e3af5f00dab61160ef617850953771
@@ -1,17 +1,28 @@
 #include <map>
 #include <vector>
 #include <set>
+#include <utility>
+#include <list>
+#include <stack>
+#include <queue>
 #include <boost/shared_ptr.hpp>
 
 #include "sanity.hh"
 #include "graph.hh"
 #include "safe_map.hh"
+#include "numeric_vocab.hh"
 
 using boost::shared_ptr;
 using std::string;
 using std::vector;
 using std::set;
 using std::pair;
+using std::map;
+using std::multimap;
+using std::make_pair;
+using std::list;
+using std::stack;
+using std::priority_queue;
 
 ////////////////////////////////////////////////////////////////////////
 // get_reconstruction_path
@@ -239,6 +250,42 @@ UNIT_TEST(graph, random_get_reconstructi
 #endif // BUILD_UNIT_TESTS
 
 
+// graph is a parent->child map
+void toposort_ancestry(ancestry_map const & graph,
+                           vector<revision_id> & revisions)
+{
+  typedef multimap<revision_id, revision_id>::const_iterator gi;
+  typedef map<revision_id, int>::iterator pi;
+  
+  revisions.clear();
+  // determine the number of parents for each rev
+  map<revision_id, int> pcount;
+  for (gi i = graph.begin(); i != graph.end(); ++i)
+    pcount.insert(make_pair(i->first, 0));
+  for (gi i = graph.begin(); i != graph.end(); ++i)
+    ++(pcount[i->second]);
+
+  // find the set of graph roots
+  list<revision_id> roots;
+  for (pi i = pcount.begin(); i != pcount.end(); ++i)
+    if(i->second==0)
+      roots.push_back(i->first);
+
+  while (!roots.empty())
+    {
+      revision_id cur = roots.front();
+      roots.pop_front();
+      if (!null_id(cur))
+        revisions.push_back(cur);
+      
+      for(gi i = graph.lower_bound(cur);
+          i != graph.upper_bound(cur); i++)
+        if(--(pcount[i->second]) == 0)
+          roots.push_back(i->second);
+    }
+}
+
+
 ////////////////////////////////////////////////////////////////////////
 // get_uncommon_ancestors
 ////////////////////////////////////////////////////////////////////////
@@ -398,8 +445,7 @@ static bool
 // true reachability.
 
 static bool
-member(revision_id const & i, 
-       set<revision_id> const & s)
+member(revision_id const & i, set<revision_id> const & s)
 {
   return s.find(i) != s.end();
 }
@@ -438,18 +484,22 @@ our_ua_candidate_set_is_complete(revisio
       revision_id r = stk.top();
       stk.pop();
 
-      if (seen.find(r) != seen.end())
+      if (member(r, seen))
         continue;
       safe_insert(seen, r);
 
       if (null_id(r))
         continue;
 
-      if (their_candidates.find(r) != their_candidates.end())
+      if (member(r, their_candidates))
+      {
         continue;
+      }
 
-      if (our_candidates.find(r) != our_candidates.end())
+      if (!member(r, our_candidates))
+      {
         return false;
+      }
 
       typedef ancestry_map::const_iterator ci;
       pair<ci,ci> range = child_to_parent_map.equal_range(r);
@@ -467,13 +517,13 @@ struct ua_qentry
   rev_height height;
   revision_id rev;
   ua_qentry(revision_id const & r, 
-            database & db) : rev(r)
+            height_store const & heights) : rev(r)
   {
-    db.get_rev_height(rev, height);
+    heights.get_height(rev, height);
   }
   bool operator<(ua_qentry const & other) const 
   {
-    return heght < other.height
+    return height < other.height
       || height == other.height && rev < other.rev;
   }
 };
@@ -481,21 +531,27 @@ step_ua_candidate_search(revision_id con
 void
 step_ua_candidate_search(revision_id const & our_base_rid,            
                          ancestry_map const & child_to_parent_map,
+                         height_store const & heights,
                          set<revision_id> & our_candidates,
                          set<revision_id> const & their_candidates,
                          priority_queue<ua_qentry> & our_queue,
-                         database & db,
                          bool & complete_p,
                          size_t iter,
                          size_t next_check)
 {
   if (!complete_p)
     {
+      if (our_queue.empty())
+      {
+        complete_p = true;
+        return;
+      }
+      
       ua_qentry qe = our_queue.top();
       our_queue.pop();
 
       if (our_candidates.find(qe.rev) != our_candidates.end())
-        continue;
+        return;
       safe_insert(our_candidates, qe.rev);
 
       typedef ancestry_map::const_iterator ci;
@@ -503,7 +559,7 @@ step_ua_candidate_search(revision_id con
       for (ci i = range.first; i != range.second; ++i)
         {
           if (i->first == qe.rev)
-            our_queue.push(ua_qentry(i->second, db));
+            our_queue.push(ua_qentry(i->second, heights));
         }
 
       if (iter == next_check)
@@ -521,7 +577,7 @@ constrained_transitive_closure(revision_
                                set<revision_id> & ancs)
 {
   stack<revision_id> stk;
-  stk.push_back(begin);
+  stk.push(begin);
   while (!stk.empty())
     {
       revision_id r = stk.top();
@@ -547,12 +603,12 @@ get_uncommon_ancestors(revision_id const
 void
 get_uncommon_ancestors(revision_id const & left_rid, revision_id const & right_rid,
                        ancestry_map const & child_to_parent_map,
+                       height_store const & heights,
                        std::set<revision_id> & left_uncommon_ancs,
-                       std::set<revision_id> & right_uncommon_ancs,
-                       database & db)
+                       std::set<revision_id> & right_uncommon_ancs)
 {
   set<revision_id> candidates;
-
+  
   {
     // Phase 1: build the candidate sets and union them.
     
@@ -562,8 +618,8 @@ get_uncommon_ancestors(revision_id const
     priority_queue<ua_qentry> left_queue;
     priority_queue<ua_qentry> right_queue;
     
-    left_queue.push(ua_qentry(left_rid, db));
-    right_queue.push(ua_qentry(right_rid, db));
+    left_queue.push(ua_qentry(left_rid, heights));
+    right_queue.push(ua_qentry(right_rid, heights));
     
     bool right_complete = false;
     bool left_complete = false;
@@ -573,13 +629,13 @@ get_uncommon_ancestors(revision_id const
     
     while (!(right_complete && left_complete))
       {
-        step_ua_candidate_search(left_rid, child_to_parent_map,
+        step_ua_candidate_search(left_rid, child_to_parent_map, heights,
                                  left_candidates, right_candidates, left_queue, 
-                                 db, left_complete, iter, next_check);
+                                 left_complete, iter, next_check);
         
-        step_ua_candidate_search(right_rid, child_to_parent_map,
+        step_ua_candidate_search(right_rid, child_to_parent_map, heights,
                                  right_candidates, left_candidates, right_queue, 
-                                 db, right_complete, iter, next_check);
+                                 right_complete, iter, next_check);
         
         if (iter == next_check)
           next_check <<= 1;
@@ -602,18 +658,18 @@ get_uncommon_ancestors(revision_id const
     constrained_transitive_closure(right_rid, candidates, 
                                    child_to_parent_map, right_ancs);
 
-    left_uncommon_ancestors.clear();
-    right_uncommon_ancestors.clear();
+    left_uncommon_ancs.clear();
+    right_uncommon_ancs.clear();
 
     set_difference(left_ancs.begin(), left_ancs.end(),
                    right_ancs.begin(), right_ancs.end(),
-                   inserter(left_uncommon_ancestors, 
-                            left_uncommon_ancestors.begin()));
+                   inserter(left_uncommon_ancs, 
+                            left_uncommon_ancs.begin()));
 
     set_difference(right_ancs.begin(), right_ancs.end(),
                    left_ancs.begin(), left_ancs.end(),
-                   inserter(right_uncommon_ancestors, 
-                            right_uncommon_ancestors.begin()));    
+                   inserter(right_uncommon_ancs, 
+                            right_uncommon_ancs.begin()));    
   }
 
 }
@@ -643,6 +699,43 @@ get_all_ancestors(revision_id const & st
     }
 }
 
+struct mock_height_store : height_store
+{
+  mock_height_store(ancestry_map const & child_to_parent_map)
+  {
+    // assign sensible heights
+    height_map.clear();
+    
+    // toposort expects parent->child
+    ancestry_map parent_to_child;
+    for (ancestry_map::const_iterator i = child_to_parent_map.begin();
+      i != child_to_parent_map.end(); i++)
+    {
+      parent_to_child.insert(make_pair(i->second, i->first));
+    }
+    vector<revision_id> topo_revs;
+    toposort_ancestry(parent_to_child, topo_revs);
+    
+    // this is ugly but works. just give each one a sequential number.
+    rev_height top = rev_height::root_height();
+    u32 num = 1;
+    for (vector<revision_id>::const_iterator r = topo_revs.begin();
+      r != topo_revs.end(); r++, num++)
+    {
+      height_map.insert(make_pair(*r, top.child_height(num)));
+    }
+  }
+
+  virtual void get_height(revision_id const & rev, rev_height & h) const
+  {
+    MM(rev);
+    h = safe_get(height_map, rev);
+  }
+
+  map<revision_id, rev_height> height_map;
+};
+
+
 static void
 run_a_get_uncommon_ancestors_test(ancestry_map const & child_to_parent_map,
                                   revision_id const & left, revision_id const & right)
@@ -659,16 +752,18 @@ run_a_get_uncommon_ancestors_test(ancest
   set_difference(true_right_ancestors.begin(), true_right_ancestors.end(),
                  true_left_ancestors.begin(), true_left_ancestors.end(),
                  inserter(true_right_uncommon_ancestors, true_right_uncommon_ancestors.begin()));
-      
+
+  mock_height_store heights(child_to_parent_map);
+    
   set<revision_id> calculated_left_uncommon_ancestors, calculated_right_uncommon_ancestors;
   MM(calculated_left_uncommon_ancestors);
   MM(calculated_right_uncommon_ancestors);
-  get_uncommon_ancestors(left, right, child_to_parent_map,
+  get_uncommon_ancestors(left, right, child_to_parent_map, heights,
                          calculated_left_uncommon_ancestors,
                          calculated_right_uncommon_ancestors);
   I(calculated_left_uncommon_ancestors == true_left_uncommon_ancestors);
   I(calculated_right_uncommon_ancestors == true_right_uncommon_ancestors);
-  get_uncommon_ancestors(right, left, child_to_parent_map,
+  get_uncommon_ancestors(right, left, child_to_parent_map, heights,
                          calculated_right_uncommon_ancestors,
                          calculated_left_uncommon_ancestors);
   I(calculated_left_uncommon_ancestors == true_left_uncommon_ancestors);
@@ -702,26 +797,26 @@ UNIT_TEST(graph, get_uncommon_ancestors_
 
   ancestry_map child_to_parent_map;
   revision_id left(fake_id()), right(fake_id());
-  revision_id one(fake_id()), eight(fake_id()), three(fake_id()), nine(fake_id());
-  safe_insert(child_to_parent_map, make_pair(left, one));
-  safe_insert(child_to_parent_map, make_pair(one, eight));
-  safe_insert(child_to_parent_map, make_pair(eight, nine));
-  safe_insert(child_to_parent_map, make_pair(right, three));
-  safe_insert(child_to_parent_map, make_pair(three, nine));
+  revision_id one(fake_id()), two(fake_id()), eight(fake_id()), three(fake_id()), nine(fake_id());
+  child_to_parent_map.insert(make_pair(left, one));
+  child_to_parent_map.insert(make_pair(one, eight));
+  child_to_parent_map.insert(make_pair(eight, nine));
+  child_to_parent_map.insert(make_pair(right, three));
+  child_to_parent_map.insert(make_pair(three, nine));
 
   revision_id middle(fake_id());
-  safe_insert(child_to_parent_map, make_pair(left, two));
-  safe_insert(child_to_parent_map, make_pair(right, two));
+  child_to_parent_map.insert(make_pair(left, two));
+  child_to_parent_map.insert(make_pair(right, two));
   // We insert a _lot_ of revisions at the ellipsis, to make sure that
   // whatever sort of step-size is used on the expansion, we can't take the
   // entire middle portion in one big gulp and make the test pointless.
   for (int i = 0; i != 1000; ++i)
     {
       revision_id next(fake_id());
-      safe_insert(child_to_parent_map, make_pair(middle, next));
+      child_to_parent_map.insert(make_pair(middle, next));
       middle = next;
     }
-  safe_insert(child_to_parent_map, make_pair(middle, eight));
+    child_to_parent_map.insert(make_pair(middle, eight));
 
   run_a_get_uncommon_ancestors_test(child_to_parent_map, left, right);
 }
@@ -779,33 +874,42 @@ make_random_graph(size_t num_nodes,
                   randomizer & rng)
 {
   set<revision_id> heads;
+  set<revision_id> joined_nodes;
 
   for (size_t i = 0; i != num_nodes; ++i)
     {
       revision_id new_rid = revision_id(fake_id());
-      nodes.push_back(new_rid);
       set<revision_id> parents;
       if (heads.empty() || rng.bernoulli(new_root_freq))
-        parents.insert(revision_id());
-      else if (rng.bernoulli(merge_node_freq) && heads.size() > 1)
         {
-          // maybe we'll pick the same node twice and end up not doing a
-          // merge, oh well...
-          parents.insert(pick_node_from_set(heads));
-          parents.insert(pick_node_from_set(heads));
+          // don't create any edges, this node is lonely
         }
-      else
+      else 
         {
-          parents.insert(pick_node_or_ancestor(heads, child_to_parent_map));
+          if (rng.bernoulli(merge_node_freq) && heads.size() > 1)
+            {
+              // maybe we'll pick the same node twice and end up not doing a
+              // merge, oh well...
+              parents.insert(pick_node_from_set(heads, rng));
+              parents.insert(pick_node_from_set(heads, rng));
+            }
+          else
+            {
+              parents.insert(pick_node_or_ancestor(heads, child_to_parent_map, rng));
+            }
+          for (set<revision_id>::const_iterator j = parents.begin();
+               j != parents.end(); ++j)
+            {
+              heads.erase(*j);
+              joined_nodes.insert(new_rid);
+              joined_nodes.insert(*j);
+              child_to_parent_map.insert(std::make_pair(new_rid, *j));
+            }
         }
-      for (set<revision_id>::const_iterator j = parents.begin();
-           j != parents.end(); ++j)
-        {
-          heads.erase(*j);
-          child_to_parent_map.insert(std::make_pair(new_rid, *j));
-        }
       safe_insert(heads, new_rid);
     }
+  
+  copy(joined_nodes.begin(), joined_nodes.end(), back_inserter(nodes));
 }
 
 static void
@@ -819,8 +923,8 @@ run_a_get_uncommon_ancestors_random_test
   for (size_t i = 0; i != iterations; ++i)
     {
       L(FL("get_uncommon_ancestors: random test %s-%s") % num_nodes % i);
-      revision_id left = idx(nodes, uniform(nodes.size()));
-      revision_id right = idx(nodes, uniform(nodes.size()));
+      revision_id left = idx(nodes, rng.uniform(nodes.size()));
+      revision_id right = idx(nodes, rng.uniform(nodes.size()));
       run_a_get_uncommon_ancestors_test(child_to_parent_map, left, right);
     }
 }
============================================================
--- graph.hh	9849fd1ce316f39677da9e81cf9716c676b02494
+++ graph.hh	480c7937c852b3f28093bca1f42b6d650df596f5
@@ -17,11 +17,13 @@
 // (e.g., in revision.cc); FIXME it would be good to move them in here as
 // opportunity permits.
 
-#include <map>
 #include <string>
 #include <set>
 #include <vector>
+#include <utility>
+
 #include "vocab.hh"
+#include "rev_height.hh"
 
 struct reconstruction_graph
 {
@@ -39,13 +41,23 @@ typedef std::multimap<revision_id, revis
 
 typedef std::multimap<revision_id, revision_id> ancestry_map;
 
+void toposort_ancestry(ancestry_map const & graph,
+                          std::vector<revision_id> & revisions);
+                          
+struct height_store
+{
+  virtual void get_height(revision_id const & rid, rev_height & height) const = 0;
+  virtual ~height_store() {};
+};
+
 void
 get_uncommon_ancestors(revision_id const & left_rid, revision_id const & right_rid,
                        ancestry_map const & child_to_parent_map,
+                       height_store const & heights,
                        std::set<revision_id> & left_uncommon_ancs,
                        std::set<revision_id> & right_uncommon_ancs);
-                       
 
+
 #endif // __GRAPH__HH__
 
 
============================================================
--- revision.cc	ca25b6d7baaae299e272001bc7e4a8ffeb9b946e
+++ revision.cc	be90c9703d54c9860a9bae8b233d5698e6b8e087
@@ -1730,9 +1730,9 @@ allrevs_toposorted(vector<revision_id> &
                    app_state & app)
 {
   // get the complete ancestry
-  rev_ancestry_map graph;
+  ancestry_map graph;
   app.db.get_revision_ancestry(graph);
-  toposort_rev_ancestry(graph, revisions);
+  toposort_ancestry(graph, revisions);
 }
 
 void
============================================================
--- roster.cc	dfb22c69788162515c92abc16b52eee9c1e4f75e
+++ roster.cc	beafb1f44ceec187d07239c3f202850bddfa8aef
@@ -59,21 +59,6 @@ template <> void
 }
 
 template <> void
-dump(set<revision_id> const & revids, string & out)
-{
-  out.clear();
-  bool first = true;
-  for (set<revision_id>::const_iterator i = revids.begin();
-       i != revids.end(); ++i)
-    {
-      if (!first)
-        out += ", ";
-      first = false;
-      out += i->inner()();
-    }
-}
-
-template <> void
 dump(marking_t const & marking, string & out)
 {
   ostringstream oss;
============================================================
--- roster.hh	0df1174eb4998443af6c94143f46eb3f8b383f31
+++ roster.hh	395efe568c9d1d40b50dde17d11a160a22a51298
@@ -165,7 +165,6 @@ typedef std::map<node_id, marking_t> mar
 
 typedef std::map<node_id, marking_t> marking_map;
 
-template <> void dump(std::set<revision_id> const & revids, std::string & out);
 template <> void dump(marking_t const & marking, std::string & out);
 template <> void dump(marking_map const & marking_map, std::string & out);
 
============================================================
--- vocab.cc	842d7558aa658249160db34543481792f4a7a081
+++ vocab.cc	77490ecc652abc35eed9ed350df7371ebd5010a1
@@ -15,6 +15,7 @@ using std::string;
 #include "vocab.hh"
 
 using std::string;
+using std::set;
 
 // verifiers for various types of data
 
@@ -230,6 +231,22 @@ void dump(manifest_data const & d, strin
 template
 void dump(manifest_data const & d, string &);
 
+template <> void
+dump(set<revision_id> const & revids, string & out)
+{
+  out.clear();
+  bool first = true;
+  for (set<revision_id>::const_iterator i = revids.begin();
+       i != revids.end(); ++i)
+    {
+      if (!first)
+        out += ", ";
+      first = false;
+      out += i->inner()();
+    }
+}
+
+
 #ifdef BUILD_UNIT_TESTS
 
 #include "unit_tests.hh"
============================================================
--- vocab.hh	2bd8cac9e74aecc7e0de12a440d08fd9153bfdfa
+++ vocab.hh	8bd9123edb30504b7220d5da35de033de5bd376e
@@ -15,6 +15,7 @@
 #include <utility>
 #include <string>
 #include <iosfwd>
+#include <set>
 
 // the purpose of this file is to wrap things which are otherwise strings
 // in a bit of typesafety, set up enumerations and tuple-types, and
@@ -158,6 +159,7 @@ null_id(revision_id const & i)
   return i.inner()().empty();
 }
 
+template <> void dump(std::set<revision_id> const & revids, std::string & out);
 
 hexenc<id>
 fake_id();