#
#
# patch "database.cc"
#  from [471ebf3192b0509022c32cdc759607c5652d47a9]
#    to [1a84359f097bcaaaf02321ca820c8a1c5aba17d6]
# 
# patch "revision.cc"
#  from [563793f4cf2d265fafa9ac422ab9adc854448fe0]
#    to [f65fbe7ba0fe0508668a5b353f1e5b532e096402]
#
============================================================
--- database.cc	471ebf3192b0509022c32cdc759607c5652d47a9
+++ database.cc	1a84359f097bcaaaf02321ca820c8a1c5aba17d6
@@ -1904,20 +1904,33 @@ database::get_rev_height(revision_id con
 database::get_rev_height(revision_id const & id,
                          rev_height & height)
 {
+  typedef std::map<revision_id, rev_height> height_map;
+  static height_map height_cache;
+
   if (null_id(id))
     {
       height = rev_height::root_height();
       return;
     }
 
-  results res;
-  fetch(res, one_col, one_row,
-        query("SELECT height FROM heights WHERE revision = ?")
-        % text(id.inner()()));
+  height_map::const_iterator i = height_cache.find(id);
+  if (i == height_cache.end())
+    {
+      results res;
+      fetch(res, one_col, one_row,
+            query("SELECT height FROM heights WHERE revision = ?")
+            % text(id.inner()()));
 
-  I(res.size() == 1);
-  
-  height = rev_height(res[0][0]);
+      I(res.size() == 1);
+
+      height = rev_height(res[0][0]);
+      height_cache.insert(make_pair(id, height));
+    }
+  else
+    {
+      height = i->second;
+    }
+
   I(height.valid());
 }
 
============================================================
--- revision.cc	563793f4cf2d265fafa9ac422ab9adc854448fe0
+++ revision.cc	f65fbe7ba0fe0508668a5b353f1e5b532e096402
@@ -415,12 +415,15 @@ accumulate_strict_ancestors(revision_id 
 static void
 accumulate_strict_ancestors(revision_id const & start,
                             set<revision_id> & all_ancestors,
-                            multimap<revision_id, revision_id> const & inverse_graph)
+                            multimap<revision_id, revision_id> const & inverse_graph,
+                            app_state & app,
+                            rev_height const & min_height)
 {
   typedef multimap<revision_id, revision_id>::const_iterator gi;
 
   vector<revision_id> frontier;
   frontier.push_back(start);
+
   while (!frontier.empty())
     {
       revision_id rid = frontier.back();
@@ -431,8 +434,14 @@ accumulate_strict_ancestors(revision_id 
           revision_id const & parent = i->second;
           if (all_ancestors.find(parent) == all_ancestors.end())
             {
-              all_ancestors.insert(parent);
-              frontier.push_back(parent);
+              // prune if we're below min_height
+              rev_height h;
+              app.db.get_rev_height(parent, h);
+              if (h >= min_height)
+                {
+                  all_ancestors.insert(parent);
+                  frontier.push_back(parent);
+                }
             }
         }
     }
@@ -443,17 +452,7 @@ accumulate_strict_ancestors(revision_id 
 //   erase_ancestors(candidates, app);
 // however, by interleaving the two operations, it can in common cases make
 // many fewer calls to the predicate, which can be a significant speed win.
-//
-// FIXME: once we have heights, we should use them here.  The strategy will
-// be, to calculate the minimum height of all the candidates, and teach
-// accumulate_ancestors to stop at a certain height, and teach the code that
-// removes items from the candidate set to occasionally rescan the candidate
-// set to get a new minimum height (perhaps, whenever we remove the minimum
-// height candidate).
-//
-// Note: The strategy outlined above does only work well for small sets of
-// candidates, because of the overhead induced by fetching heights for all
-// members of the set.
+
 void
 erase_ancestors_and_failures(std::set<revision_id> & candidates,
                              is_failure & p,
@@ -463,6 +462,9 @@ erase_ancestors_and_failures(std::set<re
   // Load up the ancestry graph
   multimap<revision_id, revision_id> inverse_graph;
   
+  if (candidates.empty())
+    return;
+  
   if (inverse_graph_cache_ptr == NULL)
     inverse_graph_cache_ptr = &inverse_graph;
   if (inverse_graph_cache_ptr->empty())
@@ -478,6 +480,16 @@ erase_ancestors_and_failures(std::set<re
   // combinatorial explosion.
   set<revision_id> all_ancestors;
 
+  rev_height min_height;
+  app.db.get_rev_height(*candidates.begin(), min_height);
+  for (std::set<revision_id>::const_iterator it = candidates.begin(); it != candidates.end(); it++)
+    {
+      rev_height h;
+      app.db.get_rev_height(*it, h);
+      if (h < min_height)
+        min_height = h;
+    }
+
   vector<revision_id> todo(candidates.begin(), candidates.end());
   std::random_shuffle(todo.begin(), todo.end());
 
@@ -498,7 +510,7 @@ erase_ancestors_and_failures(std::set<re
         }
       // okay, it is good enough that all its ancestors should be
       // eliminated
-      accumulate_strict_ancestors(rid, all_ancestors, *inverse_graph_cache_ptr);
+      accumulate_strict_ancestors(rid, all_ancestors, *inverse_graph_cache_ptr, app, min_height);
     }
 
   // now go and eliminate the ancestors