#
#
# patch "cmd_ws_commit.cc"
#  from [bd3ff76b370c79e138868481e65d1ec37dcf94b8]
#    to [05710522221057dc17eb116b8c287eaa6c80ac67]
# 
# patch "work.cc"
#  from [766cbbfd5b78c442ed6fc650846daa55f9d42768]
#    to [7733b065fc6a91cce5294772f7d0878f4aecb014]
# 
# patch "work.hh"
#  from [d6167a82e9e8fefa17d892c09af2ed0c78f8ded5]
#    to [5a0e04454d2d53a40b766653b30d097dd987373c]
#
============================================================
--- cmd_ws_commit.cc	bd3ff76b370c79e138868481e65d1ec37dcf94b8
+++ cmd_ws_commit.cc	05710522221057dc17eb116b8c287eaa6c80ac67
@@ -8,6 +8,7 @@
 // PURPOSE.
 
 #include "base.hh"
+#include <deque>
 #include <iostream>
 #include <map>
 
@@ -16,6 +17,7 @@
 #include "file_io.hh"
 #include "restrictions.hh"
 #include "revision.hh"
+#include "selectors.hh"
 #include "transforms.hh"
 #include "work.hh"
 #include "charset.hh"
@@ -1471,7 +1473,288 @@ CMD(refresh_inodeprints, "refresh_inodep
   work.maybe_update_inodeprints(db);
 }
 
+CMD_GROUP(bisect, "bisect", "", CMD_REF(informative),
+          N_("Search revisions to find where a change first appeared"),
+          N_("This command subdivides a set of revisions into good and bad sets "
+             "and successively narrows the set to find the revision that introduced "
+             "some change"));
 
+CMD(reset, "reset", "", CMD_REF(bisect), "",
+    N_("Resets the current search information allowing a new search to be started"),
+    N_("All current search information is discarded"),
+    options::opts::none)
+{
+  workspace work(app);
+  work.remove_bisect_info();
+  P(F("bisect reset"));
+}
+
+CMD(bisect_status, "status", "", CMD_REF(bisect), "",
+    N_("Reports on the current status of the search"),
+    N_("Lists the number of revisions remaining to be searched"),
+    options::opts::none)
+{
+  workspace work(app);
+  vector<bisect::entry> bisect;
+  work.get_bisect_info(bisect);
+
+  for (vector<bisect::entry>::const_iterator i = bisect.begin();
+       i != bisect.end(); ++i)
+    {
+      switch (i->first)
+        {
+        case bisect::good:
+          std::cerr << "   good " << i->second << std::endl;
+          break;
+        case bisect::bad:
+          std::cerr << "    bad " << i->second << std::endl;
+          break;
+        case bisect::skipped:
+          std::cerr << "skipped " << i->second << std::endl;
+          break;
+        }
+    }
+  
+  // report the number of revs marked as good
+  // report the number of revs marked as bad
+  // report the number of revs marked as skipped
+  // report the number of remaining revs
+  // if --verbose report the number of remaining revs after each good/bad/skip operation
+}
+
+// FIXME: this is copied from cmd_diff_log.cc
+class revision_loader
+{
+ private:
+  database & db;
+  enum load_direction { ancestors, descendants };
+
+  void
+  load_revs(load_direction const direction, set<revision_id> & revs)
+  {
+    std::deque<revision_id> next(revs.begin(), revs.end());
+
+    while (!next.empty())
+      {
+        revision_id const & rid(next.front());
+        MM(rid);
+
+        set<revision_id> relatives;
+        MM(relatives);
+
+        if (direction == ancestors)
+          db.get_revision_parents(rid, relatives);
+        else if (direction == descendants)
+          db.get_revision_children(rid, relatives);
+        else
+          I(false);
+
+        for (set<revision_id>::const_iterator i = relatives.begin();
+             i != relatives.end(); ++i)
+          {
+            if (null_id(*i))
+              continue;
+            pair<set<revision_id>::iterator, bool> res = revs.insert(*i);
+            if (res.second)
+              next.push_back(*i);
+          }
+
+        next.pop_front();
+      }
+  }
+
+ public:
+  revision_loader(database & db) : db(db) {}
+
+  void
+  load_ancestors(set<revision_id> & revs)
+  {
+    load_revs(ancestors, revs);
+  }
+
+  void
+  load_descendants(set<revision_id> & revs)
+  {
+    load_revs(descendants, revs);
+  }
+
+};
+
+
+static void
+bisect_update(app_state & app, bisect::type type)
+{
+  database db(app);
+  workspace work(app);
+  project_t project(db);
+  revision_loader loader(db);
+
+  revision_id rev;
+
+  E(app.opts.revision_selectors.size() < 2, origin::user,
+    F("bisect allows only one revision selector"));
+
+  // FIXME: ensure workspace is clean for bisecting
+
+  if (app.opts.revision_selectors.size() == 0)
+    {
+      // update insists on a single parent workspace so this probably should too
+      // should bisect also insist on a clean workspace?
+      parent_map parents;
+      work.get_parent_rosters(db, parents);
+      E(parents.size() == 1, origin::user,
+        F("this command can only be used in a single-parent workspace"));
+
+      rev = parent_id(*parents.begin());
+    }
+  else if (app.opts.revision_selectors.size() == 1)
+    {
+      set<revision_id> rids;
+      MM(rids);
+      complete(app.opts, app.lua, project, 
+               (*app.opts.revision_selectors.begin())(), rids);
+
+      diagnose_ambiguous_expansion(project, 
+                                   (*app.opts.revision_selectors.begin())(),
+                                   rids);
+
+      I(rids.size() == 1);
+      rev = *rids.begin();
+    }
+  else
+    I(false);
+
+  // FIXME: this should possibly be delated until it's known whether the new
+  // addition is sensible or not. i.e. ignore nonsense revs and don't change
+  // the bisect info
+
+  vector<bisect::entry> bisect;
+  work.get_bisect_info(bisect);
+  bisect.push_back(make_pair(type, rev));
+  work.put_bisect_info(bisect);
+
+  set<revision_id> first_good, good, first_bad, bad, skipped;
+  for (vector<bisect::entry>::const_iterator i = bisect.begin();
+       i != bisect.end(); ++i)
+    {
+      switch (i->first)
+        {
+        case bisect::good:
+          if (first_good.empty())
+            first_good.insert(i->second);
+          good.insert(i->second);
+          break;
+        case bisect::bad:
+          if (first_bad.empty())
+            first_bad.insert(i->second);
+          bad.insert(i->second);
+          break;
+        case bisect::skipped:
+          skipped.insert(i->second);
+          break;
+        }
+    }
+
+  if (good.empty() && !bad.empty())
+    {
+      P(F("%d bad revisions selected; specify good revisions to start search")
+        % bad.size());
+      return;
+    }
+  else if (!good.empty() && bad.empty())
+    {
+      P(F("%d good revisions selected; specify bad revisions to start search")
+        % good.size());
+      return;
+    }
+
+  P(F("%d good revisions; %d bad revisions; %d skipped revisions")
+    % good.size() % bad.size() % skipped.size());
+
+  // the initial set of revisions to be searched are those from the first
+  // good revision to the first bad revision. this clamps the search set
+  // between these two revisions.
+
+  loader.load_descendants(first_good);
+  loader.load_ancestors(first_bad);
+  
+  set<revision_id> search;
+  set_intersection(first_bad.begin(), first_bad.end(),
+                   first_good.begin(), first_good.end(),
+                   inserter(search, search.end()));
+  P(F("%d revisions in initial search set") % search.size());
+
+  // good revisions and their ancestors are removed from the search set. 
+  // bad revisions and their descendants are removed from the search set.
+  // skipped revisions are removed from the search set.
+
+  loader.load_ancestors(good);
+  loader.load_descendants(bad);
+
+  P(F("removing %d known good revisions") % good.size());
+  P(F("removing %d known bad revisions") % bad.size());
+  P(F("removing %d skipped revisions") % skipped.size());
+
+  set<revision_id> removed;
+  removed.insert(good.begin(), good.end());
+  removed.insert(bad.begin(), bad.end());
+  removed.insert(skipped.begin(), skipped.end());
+
+  set<revision_id> remaining;
+  set_difference(search.begin(), search.end(),
+                 removed.begin(), removed.end(),
+                 inserter(remaining, remaining.end()));
+
+  P(F("%d remaining revisions") % remaining.size());
+
+  // bisection is done by toposorting the remaining revs and using the
+  // midpoint of the result as the next revision to test
+
+  vector<revision_id> candidates;
+  toposort(db, remaining, candidates);
+
+  for (vector<revision_id>::const_iterator i = candidates.begin();
+       i != candidates.end(); ++i)
+    P(F("candidate %s") % describe_revision(project, *i));
+
+  E(candidates.size() > 0, origin::user,
+    F("no remaining candidate revisions"));
+
+  revision_id target = candidates[candidates.size()/2];
+  P(F("updating %s") % describe_revision(project, target));
+}
+
+CMD(skip, "skip", "", CMD_REF(bisect), "",
+    N_("Excludes the current revision or specified revisions from the search set"),
+    N_("Excluded revisions are removed from the set being searched. Revisions "
+       "that cannot be tested for some reason should be excluded"),
+    options::opts::revision)
+{
+  if (args.size() != 0)
+    throw usage(execid);
+  bisect_update(app, bisect::skipped);
+}
+
+CMD(bad, "bad", "", CMD_REF(bisect), "",
+    N_("Marks the current revision or specified revisions as bad"),
+    N_("Bad revisions are included in the set being searched"),
+    options::opts::revision)
+{
+  if (args.size() != 0)
+    throw usage(execid);
+  bisect_update(app, bisect::bad);
+}
+
+CMD(good, "good", "", CMD_REF(bisect), "",
+    N_("Marks the current revision or specified revisions as good"),
+    N_("Good revisions are excluded from the set being searched"),
+    options::opts::revision)
+{
+  if (args.size() != 0)
+    throw usage(execid);
+  bisect_update(app, bisect::good);
+}
+
 // Local Variables:
 // mode: C++
 // fill-column: 76
============================================================
--- work.cc	766cbbfd5b78c442ed6fc650846daa55f9d42768
+++ work.cc	7733b065fc6a91cce5294772f7d0878f4aecb014
@@ -54,6 +54,7 @@ static char const update_file_name[] = "
 static char const user_log_file_name[] = "log";
 static char const revision_file_name[] = "revision";
 static char const update_file_name[] = "update";
+static char const bisect_file_name[] = "bisect";
 
 static void
 get_revision_path(bookkeeping_path & m_path)
@@ -97,6 +98,13 @@ get_update_path(bookkeeping_path & updat
   L(FL("update path is %s") % update_path);
 }
 
+static void
+get_bisect_path(bookkeeping_path & bisect_path)
+{
+  bisect_path = bookkeeping_root / bisect_file_name;
+  L(FL("bisect path is %s") % bisect_path);
+}
+
 //
 
 bool
@@ -599,6 +607,104 @@ workspace::print_option(utf8 const & opt
     E(false, origin::user, F("'%s' is not a recognized workspace option") % opt);
 }
 
+// _MTN/bisect handling.
+
+namespace syms
+{
+    symbol const good("good");
+    symbol const bad("bad");
+    symbol const skipped("skipped");
+};
+
+void
+workspace::get_bisect_info(vector<bisect::entry> & bisect)
+{
+  bookkeeping_path bisect_path;
+  get_bisect_path(bisect_path);
+  
+  if (!file_exists(bisect_path))
+    return;
+
+  data dat;
+  read_data(bisect_path, dat);
+
+  string name("bisect");
+  basic_io::input_source src(dat(), name, origin::workspace);
+  basic_io::tokenizer tok(src);
+  basic_io::parser parser(tok);
+
+  while (parser.symp())
+    {
+      string rev;
+      bisect::type type;
+      if (parser.symp(syms::good))
+        {
+          parser.sym();
+          parser.hex(rev);
+          type = bisect::good;
+        }
+      else if (parser.symp(syms::bad))
+        {
+          parser.sym();
+          parser.hex(rev);
+          type = bisect::bad;
+        }
+      else if (parser.symp(syms::skipped))
+        {
+          parser.sym();
+          parser.hex(rev);
+          type = bisect::skipped;
+        }
+      else
+        I(false);
+
+      revision_id rid = 
+        decode_hexenc_as<revision_id>(rev, parser.tok.in.made_from);
+      bisect.push_back(make_pair(type, rid));
+    }
+}
+
+void
+workspace::put_bisect_info(vector<bisect::entry> const & bisect)
+{
+  bookkeeping_path bisect_path;
+  get_bisect_path(bisect_path);
+
+  basic_io::stanza st;
+  for (vector<bisect::entry>::const_iterator i = bisect.begin(); 
+       i != bisect.end(); ++i)
+    {
+      switch (i->first)
+        {
+        case bisect::good:
+          st.push_binary_pair(syms::good, i->second.inner());
+          break;
+
+        case bisect::bad:
+          st.push_binary_pair(syms::bad, i->second.inner());
+          break;
+
+        case bisect::skipped:
+          st.push_binary_pair(syms::skipped, i->second.inner());
+          break;
+        }
+    }
+
+  basic_io::printer pr;
+  pr.print_stanza(st);
+  data dat(pr.buf, origin::internal);
+
+  write_data(bisect_path, dat);
+}
+
+void
+workspace::remove_bisect_info()
+{
+  bookkeeping_path bisect_path;
+  get_bisect_path(bisect_path);
+  delete_file(bisect_path);
+}
+
 // local dump file
 
 void
============================================================
--- work.hh	d6167a82e9e8fefa17d892c09af2ed0c78f8ded5
+++ work.hh	5a0e04454d2d53a40b766653b30d097dd987373c
@@ -81,6 +81,12 @@ bool directory_is_workspace(system_path 
 
 bool directory_is_workspace(system_path const & dir);
 
+namespace bisect
+{
+    enum type { good, bad, skipped };
+    typedef std::pair<type, revision_id> entry;
+};
+
 struct workspace
 {
   // This is a public flag because it's set from monotone.cc using a
@@ -223,6 +229,13 @@ public:
   static void set_options(options const & opts, bool branch_is_sticky);
   static void print_option(utf8 const & opt, std::ostream & output);
 
+  // the "bisect" infromation file is a file that records current status
+  // information for the bisect search.
+
+  void get_bisect_info(std::vector<bisect::entry> & bisect);
+  void put_bisect_info(std::vector<bisect::entry> const & bisect);
+  void remove_bisect_info();
+
   // the "workspace format version" is a nonnegative integer value, stored
   // in _MTN/format as an unadorned decimal number.  at any given time
   // monotone supports actual use of only one workspace format.