[Monotone-commits-diffs] net.venge.monotone.min-selector: f58076256509782554b20faa665282ba12c82abf

[code]

revision:            f58076256509782554b20faa665282ba12c82abf
date:                2012-04-26T18:45:04
author:              Richard Hopkins <address@hidden>
branch:              net.venge.monotone.min-selector
changelog:
Implement 'min(A') selector

This is basically the same as 'max(A)', and 'erase_ancestors': the only
difference is that we use the forward ancestry and prune by max height
instead of min height.

The recently added tests now pass. We can now find the initial commit
for monotone - go Graydon!

mtn log --no-files --no-graph --revision="min(b:net.venge.monotone)"

manifest:
format_version "1"

new_manifest [2a9327afed0505d4a54fa022ccc57d2d61373eb5]

old_revision [ca439d72274c8f9d0ef0138abb777bd1410a456e]

patch "src/ancestry.cc"
 from [8b3388b690a5f4878bd29d752c3e6e073411739e]
   to [e673b17a5d2fad2716f7f4efe33c2ca11c7c31f9]

patch "src/revision.hh"
 from [740c4dd4ee350fcf06af3ba707cef3dadecb46f8]
   to [8d93883e8a6de779aa199d9b2e1aa58589f0626c]

patch "src/selectors.cc"
 from [588c6b5fd3ded29f5f778a78e707352564acbc02]
   to [19a82c64f44ab5433354299f84598174cb15f510]
============================================================
--- src/ancestry.cc	8b3388b690a5f4878bd29d752c3e6e073411739e
+++ src/ancestry.cc	e673b17a5d2fad2716f7f4efe33c2ca11c7c31f9
@@ -374,6 +374,121 @@ erase_ancestors(database & db, set<revis
   erase_ancestors_and_failures(db, revisions, p);
 }
 
+static void
+accumulate_strict_descendants(database & db,
+                              revision_id const & start,
+                              set<revision_id> & all_descendants,
+                              multimap<revision_id, revision_id> const & graph,
+                              rev_height const & max_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();
+      frontier.pop_back();
+      pair<gi, gi> parents = graph.equal_range(rid);
+      for (gi i = parents.first; i != parents.second; ++i)
+        {
+          revision_id const & parent = i->second;
+          if (all_descendants.find(parent) == all_descendants.end())
+            {
+              // prune if we're above max_height
+              rev_height h;
+              db.get_rev_height(parent, h);
+              if (h <= max_height)
+                {
+                  all_descendants.insert(parent);
+                  frontier.push_back(parent);
+                }
+            }
+        }
+    }
+}
+
+// this call is equivalent to running:
+//   erase(remove_if(candidates.begin(), candidates.end(), p));
+//   erase_descendants(candidates, db);
+// 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.
+
+void
+erase_descendants_and_failures(database & db,
+                               std::set<revision_id> & candidates,
+                               is_failure & p,
+                               multimap<revision_id, revision_id> *graph_cache_ptr)
+{
+  // Load up the ancestry graph
+  multimap<revision_id, revision_id> graph;
+
+  if (candidates.empty())
+    return;
+
+  if (graph_cache_ptr == NULL)
+    graph_cache_ptr = &graph;
+  if (graph_cache_ptr->empty())
+  {
+    db.get_forward_ancestry(*graph_cache_ptr);
+  }
+
+  // Keep a set of all descendants that we've traversed -- to avoid
+  // combinatorial explosion.
+  set<revision_id> all_descendants;
+
+  rev_height max_height;
+  db.get_rev_height(*candidates.begin(), max_height);
+  for (std::set<revision_id>::const_iterator it = candidates.begin(); it != candidates.end(); it++)
+    {
+      rev_height h;
+      db.get_rev_height(*it, h);
+      if (h > max_height)
+        max_height = h;
+    }
+
+  vector<revision_id> todo(candidates.begin(), candidates.end());
+  std::random_shuffle(todo.begin(), todo.end());
+
+  size_t predicates = 0;
+  while (!todo.empty())
+    {
+      revision_id rid = todo.back();
+      todo.pop_back();
+      // check if this one has already been eliminated
+      if (all_descendants.find(rid) != all_descendants.end())
+        continue;
+      // and then whether it actually should stay in the running:
+      ++predicates;
+      if (p(rid))
+        {
+          candidates.erase(rid);
+          continue;
+        }
+      // okay, it is good enough that all its descendants should be
+      // eliminated
+      accumulate_strict_descendants(db, rid, all_descendants, *graph_cache_ptr, max_height);
+    }
+
+  // now go and eliminate the ancestors
+  for (set<revision_id>::const_iterator i = all_descendants.begin();
+       i != all_descendants.end(); ++i)
+    candidates.erase(*i);
+
+  L(FL("called predicate %s times") % predicates);
+}
+
+// This function looks at a set of revisions, and for every pair A, B in that
+// set such that A is an descendant of B, it erases A.
+
+void
+erase_descendants(database & db, set<revision_id> & revisions)
+{
+  no_failures p;
+  erase_descendants_and_failures(db, revisions, p);
+}
+
 // This function takes a revision A and a set of revision Bs, calculates the
 // ancestry of each, and returns the set of revisions that are in A's ancestry
 // but not in the ancestry of any of the Bs.  It tells you 'what's new' in A
============================================================
--- src/revision.hh	740c4dd4ee350fcf06af3ba707cef3dadecb46f8
+++ src/revision.hh	8d93883e8a6de779aa199d9b2e1aa58589f0626c
@@ -162,6 +162,15 @@ void
                              std::multimap<revision_id, revision_id> *inverse_graph_cache_ptr = NULL);
 
 void
+erase_descendants(database & db, std::set<revision_id> & revisions);
+
+void
+erase_descendants_and_failures(database & db,
+                               std::set<revision_id> & revisions,
+                               is_failure & p,
+                               std::multimap<revision_id, revision_id> *inverse_graph_cache_ptr = NULL);
+
+void
 ancestry_difference(database & db, revision_id const & a,
                     std::set<revision_id> const & bs,
                     std::set<revision_id> & new_stuff);
============================================================
--- src/selectors.cc	588c6b5fd3ded29f5f778a78e707352564acbc02
+++ src/selectors.cc	19a82c64f44ab5433354299f84598174cb15f510
@@ -559,6 +559,13 @@ public:
         erase_ancestors(project.db, ret);
         return ret;
       }
+    else if (name == "min")
+      {
+        diagnose_wrong_arg_count("min", 1, args.size());
+        set<revision_id> ret = args[0]->complete(project);
+        erase_descendants(project.db, ret);
+        return ret;
+      }
     else if (name == "ancestors")
       {
         diagnose_wrong_arg_count("ancestors", 1, args.size());