Finish drop command implementation

9 files changed, 597 insertions, 53 deletions

diff --git a/bpkg/drop-options.cli b/bpkg/drop-options.cli
index d1a3769..ca67c14 100644
--- a/bpkg/drop-options.cli
+++ b/bpkg/drop-options.cli
@@ -35,6 +35,12 @@ namespace bpkg
        for that."
     };
 
+    bool --no|-n
+    {
+      "Assume the answer to all prompts is \cb{no}. Only makes sense together
+       with \cb{--print-only|-p}."
+    };
+
     bool --drop-dependent
     {
       "Don't warn about or ask for confirmation of dropping dependent
diff --git a/bpkg/drop.cxx b/bpkg/drop.cxx
index e2fd455..6728d09 100644
--- a/bpkg/drop.cxx
+++ b/bpkg/drop.cxx
@@ -5,9 +5,10 @@
 #include <bpkg/drop>
 
 #include <map>
+#include <list>
+#include <vector>
 #include <iostream>   // cout
-
-#include <butl/utility> // reverse_iterate()
+#include <functional> // reference_wrapper
 
 #include <bpkg/types>
 #include <bpkg/package>
@@ -28,45 +29,277 @@ using namespace butl;
 
 namespace bpkg
 {
-  using package_map = map<string, shared_ptr<selected_package>>;
+  enum class drop_reason
+  {
+    user,        // User selection.
+    dependent,   // Dependent of a user or another dependent.
+    prerequisite // Prerequisite of a user, dependent, or another prerequisite.
+  };
+
+  struct drop_package
+  {
+    shared_ptr<selected_package> package;
+    drop_reason reason;
+  };
 
-  static void
-  collect_dependent (database& db,
-                     package_map& m,
-                     const shared_ptr<selected_package>& p,
-                     bool w)
+  // List of packages that are dependent on the user selection.
+  //
+  struct dependent_name
   {
-    using query = query<package_dependent>;
+    string name;
+    string prq_name; // Prerequisite package name.
+  };
+  using dependent_names = vector<dependent_name>;
+
+  // A "dependency-ordered" list of packages and their prerequisites.
+  // That is, every package on the list only possibly depending on the
+  // ones after it. In a nutshell, the usage is as follows: we first add
+  // the packages specified by the user (the "user selection"). We then
+  // collect all the dependent packages of the user selection, if any.
+  // These will either have to be dropped as well or we cannot continue.
+  // If the user gave the go ahead to drop the dependents, then, for our
+  // purposes, this list of dependents can from now own be treated as if
+  // it was a part of the user selection. The next step is to collect all
+  // the non-held prerequisites of the user selection with the goal of
+  // figuring out which ones will no longer be needed and offering to
+  // drop them as well. This part is a bit tricky and has to be done in
+  // three steps: We first collect all the prerequisites that we could
+  // possibly be dropping. We then order all the packages. And, finally,
+  // we filter out prerequisites that we cannot drop. See the comment to
+  // the call to collect_prerequisites() for details on why it has to be
+  // done this way.
+  //
+  struct drop_packages: list<reference_wrapper<drop_package>>
+  {
+    // Collect a package to be dropped, by default, as a user selection.
+    //
+    bool
+    collect (shared_ptr<selected_package> p, drop_reason r = drop_reason::user)
+    {
+      string n (p->name); // Because of move(p) below.
+      return map_.emplace (move (n), data_type {end (), {move (p), r}}).second;
+    }
+
+    // Collect all the dependets of the user selection retutning the list
+    // of their names. Dependents of dependents are collected recursively.
+    //
+    dependent_names
+    collect_dependents (database& db)
+    {
+      dependent_names dns;
+
+      for (const auto& pr: map_)
+      {
+        const drop_package& dp (pr.second.package);
+
+        // Unconfigured package cannot have any dependents.
+        //
+        if (dp.reason == drop_reason::user &&
+            dp.package->state == package_state::configured)
+          collect_dependents (db, dns, dp.package);
+      }
 
-    bool found (false);
+      return dns;
+    }
 
-    for (auto& pd: db.query<package_dependent> (query::name == p->name))
+    void
+    collect_dependents (database& db,
+                        dependent_names& dns,
+                        const shared_ptr<selected_package>& p)
     {
-      string& dn (pd.name);
+      using query = query<package_dependent>;
 
-      if (m.find (dn) == m.end ())
+      for (auto& pd: db.query<package_dependent> (query::name == p->name))
       {
-        shared_ptr<selected_package> dp (db.load<selected_package> (dn));
-        m.emplace (move (dn), dp);
+        const string& dn (pd.name);
+
+        if (map_.find (dn) == map_.end ())
+        {
+          shared_ptr<selected_package> dp (db.load<selected_package> (dn));
+          dns.push_back (dependent_name {dn, p->name});
+          collect (dp, drop_reason::dependent);
+          collect_dependents (db, dns, dp);
+        }
+      }
+    }
 
-        collect_dependent (db, m, dp, w);
+    // Collect prerequisites of the user selection and its dependents,
+    // returning true if any were collected. Prerequisites of prerequisites
+    // are collected recursively.
+    //
+    bool
+    collect_prerequisites (database& db)
+    {
+      bool r (false);
 
-        if (w)
-          warn << "dependent package " << dp->name << " to be dropped as well";
+      for (const auto& pr: map_)
+      {
+        const drop_package& dp (pr.second.package);
 
-        found = true;
+        // Unconfigured package cannot have any prerequisites.
+        //
+        if ((dp.reason == drop_reason::user ||
+             dp.reason == drop_reason::dependent) &&
+            dp.package->state == package_state::configured)
+          r = collect_prerequisites (db, dp.package) || r;
       }
+
+      return r;
     }
 
-    if (w && found)
-      info << "because dropping " << p->name;
-  }
+    bool
+    collect_prerequisites (database& db, const shared_ptr<selected_package>& p)
+    {
+      bool r (false);
+
+      for (const auto& pair: p->prerequisites)
+      {
+        const string& pn (pair.first.object_id ());
+
+        if (map_.find (pn) == map_.end ())
+        {
+          shared_ptr<selected_package> pp (db.load<selected_package> (pn));
+
+          if (!pp->hold_package) // Prune held packages.
+          {
+            collect (pp, drop_reason::prerequisite);
+            collect_prerequisites (db, pp);
+            r = true;
+          }
+        }
+      }
+
+      return r;
+    }
+
+    // Order the previously-collected package with the specified name
+    // returning its positions.
+    //
+    iterator
+    order (const string& name)
+    {
+      // Every package that we order should have already been collected.
+      //
+      auto mi (map_.find (name));
+      assert (mi != map_.end ());
+
+      // If this package is already in the list, then that would also
+      // mean all its prerequisites are in the list and we can just
+      // return its position.
+      //
+      iterator& pos (mi->second.position);
+      if (pos != end ())
+        return pos;
+
+      // Order all the prerequisites of this package and compute the
+      // position of its "earliest" prerequisite -- this is where it
+      // will be inserted.
+      //
+      drop_package& dp (mi->second.package);
+      const shared_ptr<selected_package>& p (dp.package);
+
+      // Unless this package needs something to be before it, add it to
+      // the end of the list.
+      //
+      iterator i (end ());
+
+      // Figure out if j is before i, in which case set i to j. The goal
+      // here is to find the position of our "earliest" prerequisite.
+      //
+      auto update = [this, &i] (iterator j)
+      {
+        for (iterator k (j); i != j && k != end ();)
+          if (++k == i)
+            i = j;
+      };
+
+      // Only configured packages have prerequisites.
+      //
+      if (p->state == package_state::configured)
+      {
+        for (const auto& pair: p->prerequisites)
+        {
+          const string& pn (pair.first.object_id ());
+
+          // The prerequisites may not necessarily be in the map (e.g.,
+          // a held package that we prunned).
+          //
+          if (map_.find (pn) != map_.end ())
+            update (order (pn));
+        }
+      }
+
+      return pos = insert (i, dp);
+    }
+
+    // Remove prerequisite packages that we cannot possibly drop, returning
+    // true if any remain.
+    //
+    bool
+    filter_prerequisites (database& db)
+    {
+      bool r (false);
+
+      // Iterate from "more" to "less"-dependent.
+      //
+      for (auto i (begin ()); i != end (); )
+      {
+        const drop_package& dp (*i);
+
+        if (dp.reason == drop_reason::prerequisite)
+        {
+          const shared_ptr<selected_package>& p (dp.package);
+
+          bool keep (true);
+
+          // Get our dependents (which, BTW, could only have been before us
+          // on the list). If they are all in the map, then we can be dropped.
+          //
+          using query = query<package_dependent>;
+
+          for (auto& pd: db.query<package_dependent> (query::name == p->name))
+          {
+            if (map_.find (pd.name) == map_.end ())
+            {
+              keep = false;
+              break;
+            }
+          }
+
+          if (!keep)
+          {
+            i = erase (i);
+            map_.erase (p->name);
+            continue;
+          }
+
+          r = true;
+        }
+
+        ++i;
+      }
+
+      return r;
+    }
+
+  private:
+    struct data_type
+    {
+      iterator position;    // Note: can be end(), see collect().
+      drop_package package;
+    };
+
+    map<string, data_type> map_;
+  };
 
   int
   drop (const drop_options& o, cli::scanner& args)
   {
     tracer trace ("drop");
 
+    if (o.yes () && o.no ())
+      fail << "both --yes|-y and --no|-n specified";
+
     const dir_path& c (o.directory ());
     level4 ([&]{trace << "configuration: " << c;});
 
@@ -77,25 +310,24 @@ namespace bpkg
     database db (open (c, trace));
 
     // Note that the session spans all our transactions. The idea here is
-    // that selected_package objects in the satisfied_packages list below
-    // will be cached in this session. When subsequent transactions modify
-    // any of these objects, they will modify the cached instance, which
-    // means our list will always "see" their updated state.
-    //
-    // @@ Revise.
+    // that drop_package objects in the drop_packages list below will be
+    // cached in this session. When subsequent transactions modify any of
+    // these objects, they will modify the cached instance, which means
+    // our list will always "see" their updated state.
     //
     session s;
 
-    // Assemble the list of packages we will need to drop. Comparing pointers
-    // is valid because of the session above.
+    // Assemble the list of packages we will need to drop.
     //
-    package_map pkgs;
-    vector<string> names;
+    drop_packages pkgs;
+    bool drop_prq (false);
     {
       transaction t (db.begin ());
 
-      // The first step is to load all the packages specified by the user.
+      // The first step is to load and collect all the packages specified
+      // by the user.
       //
+      strings names;
       while (args.more ())
       {
         string n (args.next ());
@@ -110,40 +342,171 @@ namespace bpkg
           fail << "unable to drop broken package " << n <<
             info << "use 'pkg-purge --force' to remove";
 
-        if (pkgs.emplace (n, move (p)).second)
+        if (pkgs.collect (move (p)))
           names.push_back (move (n));
       }
 
       // The next step is to see if there are any dependents that are not
-      // already on the list. We will have to drop those as well.
+      // already on the list. We will either have to drop those as well or
+      // abort.
       //
-      for (const string& n: names)
+      dependent_names dnames (pkgs.collect_dependents (db));
+      if (!dnames.empty () && !o.drop_dependent ())
       {
-        const shared_ptr<selected_package>& p (pkgs[n]);
+        {
+          diag_record dr (text);
 
-        // Unconfigured package cannot have any dependents.
-        //
-        if (p->state != package_state::configured)
-          continue;
+          dr << "following dependent packages will have to be dropped "
+             << "as well:";
 
-        collect_dependent (db, pkgs, p, !o.drop_dependent ());
-      }
+          for (const dependent_name& dn: dnames)
+              dr << text << dn.name
+                 << " (because dropping " << dn.prq_name << ")";
+        }
 
-      // If we've found dependents, ask the user to confirm.
-      //
-      if (!o.drop_dependent () && names.size () != pkgs.size ())
-      {
         if (o.yes ())
           fail << "refusing to drop dependent packages with just --yes" <<
             info << "specify --drop-dependent to confirm";
 
-        if (!yn_prompt ("drop dependent packages? [y/N]", 'n'))
+        if (o.no () || !yn_prompt ("drop dependent packages? [y/N]", 'n'))
           return 1;
       }
 
+      // Collect all the prerequisites that are not held. These will be
+      // the candidates to drop as well. Note that we cannot make the
+      // final decision who we can drop until we have the complete and
+      // ordered list of all the packages that we could potentially be
+      // dropping. The ordered part is important: we will have to decide
+      // about the "more dependent" prerequisite before we can decide
+      // about the "less dependent" one since the former could be depending
+      // on the latter and, if that's the case and "more" cannot be dropped,
+      // then neither can "less".
+      //
+      pkgs.collect_prerequisites (db);
+
+      // Now that we have collected all the packages we could possibly be
+      // dropping, arrange them in the "dependency order", that is, with
+      // every package on the list only possibly depending on the ones
+      // after it.
+      //
+      // First order the user selection so that we stay as close to the
+      // order specified by the user as possible. Then order the dependent
+      // packages. Since each of them depends on one or more packages from
+      // the user selection, it will be inserted before the first package
+      // on which it depends.
+      //
+      for (const string& n: names)
+        pkgs.order (n);
+
+      for (const dependent_name& dn: dnames)
+        pkgs.order (dn.name);
+
+      // Filter out prerequisites that we cannot possibly drop (e.g., they
+      // have dependents other than the ones we are dropping). If there are
+      // some that we can drop, ask the user for confirmation.
+      //
+      if (pkgs.filter_prerequisites (db) && !(drop_prq = o.yes ()) && !o.no ())
+      {
+        {
+          diag_record dr (text);
+
+          dr << "following prerequisite packages were automatically "
+             << "built and will no longer be necessary:";
+
+          for (const drop_package& dp: pkgs)
+          {
+            if (dp.reason == drop_reason::prerequisite)
+              dr << text << dp.package->name;
+          }
+        }
+
+        drop_prq = yn_prompt ("drop prerequisite packages? [Y/n]", 'y');
+      }
+
       t.commit ();
     }
 
+    // Print what we are going to do, then ask for the user's confirmation.
+    //
+    if (o.print_only () || !(o.yes () || o.no ()))
+    {
+      for (const drop_package& dp: pkgs)
+      {
+        // Skip prerequisites if we weren't instructed to drop them.
+        //
+        if (dp.reason == drop_reason::prerequisite && !drop_prq)
+          continue;
+
+        const shared_ptr<selected_package>& p (dp.package);
+
+        if (o.print_only ())
+          cout << "drop " << p->name << endl;
+        else if (verb)
+          text << "drop " << p->name;
+      }
+
+      if (o.print_only ())
+        return 0;
+    }
+
+    // Ask the user if we should continue.
+    //
+    if (o.no () || !(o.yes () || yn_prompt ("continue? [Y/n]", 'y')))
+      return 1;
+
+    // All that's left to do is first disfigure configured packages and
+    // then purge all of them. We do both left to right (i.e., from more
+    // dependent to less dependent). For disfigure this order is required.
+    // For purge, it will be the order closest to the one specified by the
+    // user.
+    //
+    for (const drop_package& dp: pkgs)
+    {
+      // Skip prerequisites if we weren't instructed to drop them.
+      //
+      if (dp.reason == drop_reason::prerequisite && !drop_prq)
+        continue;
+
+      const shared_ptr<selected_package>& p (dp.package);
+
+      if (p->state != package_state::configured)
+        continue;
+
+      // Each package is disfigured in its own transaction, so that we
+      // always leave the configuration in a valid state.
+      //
+      transaction t (db.begin ());
+      pkg_disfigure (c, t, p); // Commits the transaction.
+      assert (p->state == package_state::unpacked);
+
+      if (verb)
+        text << "disfigured " << p->name;
+    }
+
+    if (o.disfigure_only ())
+      return 0;
+
+    // Purge.
+    //
+    for (const drop_package& dp: pkgs)
+    {
+      // Skip prerequisites if we weren't instructed to drop them.
+      //
+      if (dp.reason == drop_reason::prerequisite && !drop_prq)
+        continue;
+
+      const shared_ptr<selected_package>& p (dp.package);
+
+      assert (p->state == package_state::fetched ||
+              p->state == package_state::unpacked);
+
+      transaction t (db.begin ());
+      pkg_purge (c, t, p); // Commits the transaction, p is now transient.
+
+      if (verb)
+        text << "purged " << p->name;
+    }
+
     return 0;
   }
 }
diff --git a/bpkg/pkg-purge b/bpkg/pkg-purge
index 399606d..9a11288 100644
--- a/bpkg/pkg-purge
+++ b/bpkg/pkg-purge
@@ -14,6 +14,14 @@ namespace bpkg
   int
   pkg_purge (const pkg_purge_options&, cli::scanner& args);
 
+  // Purge the package, remove it from the database, and commit the
+  // transaction. If this fails, set the package state to broken.
+  //
+  void
+  pkg_purge (const dir_path& configuration,
+             transaction&,
+             const shared_ptr<selected_package>&);
+
   // Remove package's filesystem objects (the source directory and, if
   // the archive argument is true, the package archive). If this fails,
   // set the package state to broken, commit the transaction, and fail.
diff --git a/bpkg/pkg-purge.cxx b/bpkg/pkg-purge.cxx
index b90136a..9b63c15 100644
--- a/bpkg/pkg-purge.cxx
+++ b/bpkg/pkg-purge.cxx
@@ -66,6 +66,26 @@ namespace bpkg
     }
   }
 
+  void
+  pkg_purge (const dir_path& c,
+             transaction& t,
+             const shared_ptr<selected_package>& p)
+  {
+    assert (p->state == package_state::fetched ||
+            p->state == package_state::unpacked);
+
+    tracer trace ("pkg_purge");
+
+    database& db (t.database ());
+    tracer_guard tg (db, trace);
+
+    assert (!p->out_root);
+    pkg_purge_fs (c, t, p, true);
+
+    db.erase (p);
+    t.commit ();
+  }
+
   int
   pkg_purge (const pkg_purge_options& o, cli::scanner& args)
   {
diff --git a/tests/repository/1/satisfy/libbiz-1.0.0.tar.gz b/tests/repository/1/satisfy/libbiz-1.0.0.tar.gz
new file mode 100644
index 0000000..42e3db4
--- /dev/null
+++ b/tests/repository/1/satisfy/libbiz-1.0.0.tar.gz
diff --git a/tests/repository/1/satisfy/t4d/libbiz-1.0.0.tar.gz b/tests/repository/1/satisfy/t4d/libbiz-1.0.0.tar.gz
new file mode 120000
index 0000000..70c2fda
--- /dev/null
+++ b/tests/repository/1/satisfy/t4d/libbiz-1.0.0.tar.gz
@@ -0,0 +1 @@
+../libbiz-1.0.0.tar.gz
\ No newline at end of file
diff --git a/tests/repository/1/satisfy/t4d/libfox-1.0.0.tar.gz b/tests/repository/1/satisfy/t4d/libfox-1.0.0.tar.gz
new file mode 120000
index 0000000..dcfd7aa
--- /dev/null
+++ b/tests/repository/1/satisfy/t4d/libfox-1.0.0.tar.gz
@@ -0,0 +1 @@
+../libfox-1.0.0.tar.gz
\ No newline at end of file
diff --git a/tests/repository/1/satisfy/t4d/repositories b/tests/repository/1/satisfy/t4d/repositories
new file mode 100644
index 0000000..f0e1983
--- /dev/null
+++ b/tests/repository/1/satisfy/t4d/repositories
@@ -0,0 +1,3 @@
+: 1
+location: ../t4c
+:
diff --git a/tests/test.sh b/tests/test.sh
index 932b0d6..18643cc 100755
--- a/tests/test.sh
+++ b/tests/test.sh
@@ -140,7 +140,7 @@ function stat ()
   local s=`$bpkg pkg-status -d $cfg $1`
 
   if [ "$s" != "$2" ]; then
-    error "status: '"$s"', expected: '"$2"'"
+    error "status $1: '"$s"', expected: '"$2"'"
   fi
 }
 
@@ -968,6 +968,8 @@ EOF
 test rep-create repository/1/satisfy/t4a
 test rep-create repository/1/satisfy/t4b
 test rep-create repository/1/satisfy/t4c
+test rep-create repository/1/satisfy/t4d
+
 test cfg-create --wipe
 test rep-add $rep/satisfy/t4c
 test rep-fetch
@@ -1132,6 +1134,7 @@ test rep-fetch
 test build -y libbaz
 stat libfoo "configured 1.1.0"
 
+
 ##
 ## drop
 ##
@@ -1141,14 +1144,153 @@ fail drop -p               # package name expected
 fail drop -p libfoo        # unknown package
 fail drop -p libfoo/1.0.0  # unknown package
 
-# dependents
-#
 test cfg-create --wipe
 test rep-add $rep/satisfy/t4c
 test rep-fetch
 test build -y libbaz
+
+test drop -p -y libfoo libbaz libbar <<EOF
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+# dependents
+#
 fail drop -y libfoo
 fail drop -y libfoo libbar
 fail drop -y libfoo libbaz
-test drop -y libfoo libbaz libbar
-test drop -y --drop-dependent libfoo
+
+test drop -p -y --drop-dependent libfoo <<EOF
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+test drop -p --drop-dependent libfoo libbaz <<EOF
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+test drop -p --drop-dependent libbaz libfoo <<EOF
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+# prerequisites
+#
+test drop -p -y libbaz <<EOF
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+test drop -p -n libbaz <<EOF
+drop libbaz
+EOF
+
+test drop -p -n libbar libbaz <<EOF
+drop libbaz
+drop libbar
+EOF
+
+test drop -p -n libbaz libbar <<EOF
+drop libbaz
+drop libbar
+EOF
+
+# prerequisites and dependents
+#
+test drop -p -y --drop-dependent libbar <<EOF
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+test cfg-create --wipe
+test rep-add $rep/satisfy/t4d
+test rep-fetch
+test build -y libbiz
+
+test drop -p -y libbiz <<EOF
+drop libbiz
+drop libbaz
+drop libbar
+drop libfoo
+drop libfox
+EOF
+
+test drop -p -y libfox libbiz <<EOF
+drop libbiz
+drop libfox
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+test drop -p -y --drop-dependent libfox <<EOF
+drop libbiz
+drop libfox
+drop libbaz
+drop libbar
+drop libfoo
+EOF
+
+test drop -p -y --drop-dependent libbaz <<EOF
+drop libbiz
+drop libbaz
+drop libbar
+drop libfoo
+drop libfox
+EOF
+
+test drop -p -y --drop-dependent libbar <<EOF
+drop libbiz
+drop libbaz
+drop libbar
+drop libfoo
+drop libfox
+EOF
+
+test drop -p -y --drop-dependent libfoo <<EOF
+drop libbiz
+drop libbaz
+drop libbar
+drop libfoo
+drop libfox
+EOF
+
+test drop -p -n --drop-dependent libfox libbaz <<EOF
+drop libbiz
+drop libfox
+drop libbaz
+EOF
+
+test drop -p -n --drop-dependent libbaz libfox <<EOF
+drop libbiz
+drop libbaz
+drop libfox
+EOF
+
+test drop -p -n --drop-dependent libfox libbar <<EOF
+drop libbiz
+drop libfox
+drop libbaz
+drop libbar
+EOF
+
+test drop -p -n --drop-dependent libbar libfox <<EOF
+drop libbiz
+drop libbaz
+drop libbar
+drop libfox
+EOF
+
+test drop -y --drop-dependent libbar
+stat libfox/1.0.0 "available"
+stat libfoo/1.1.0 "unknown"
+stat libbar/1.1.0 "unknown"
+stat libbaz/1.1.0 "unknown"
+stat libbiz/1.0.0 "available"