Merge branch 'history-command' into 'main'

Add history undo, redo, and rollback features

See merge request apt-team/apt!518

6 files changed, 380 insertions, 24 deletions

diff --git a/apt-pkg/history.cc b/apt-pkg/history.cc
index 4e838a016..dc48c5464 100644
--- a/apt-pkg/history.cc
+++ b/apt-pkg/history.cc
@@ -16,6 +16,7 @@
 #include <apt-pkg/tagfile.h>
 
 #include <algorithm>
+#include <cassert>
 #include <cctype>
 
 #include <glob.h>
diff --git a/apt-pkg/history.h b/apt-pkg/history.h
index 08e7be388..899d59b24 100644
--- a/apt-pkg/history.h
+++ b/apt-pkg/history.h
@@ -20,38 +20,58 @@
 namespace APT::History
 {
 
+/**
+ * @enum class Kind
+ * @brief Represents the possible actions of APT transactions in history.
+ */
 enum class Kind
 {
    Install,
    Reinstall,
    Upgrade,
    Downgrade,
+   InstallEnd = Downgrade,
    Remove,
    Purge,
 };
 
-// KindToString - Take a kind and return its
-// string representation.
-//
-// NOTE: Non-localized English version
+/**
+ * Get the string parsing specific string representation 
+ * of a @ref Kind.
+ *
+ * @param kind An action kind.
+ * @return A string representation.
+ *
+ * @note This string representation is not localized.
+ */
 std::string KindToString(const Kind &kind);
 
+/**
+ * @struct Change
+ * @brief Represents a package change.
+ */
 struct Change
 {
    Kind kind;
    std::string package;
    std::string currentVersion;
    std::string candidateVersion;
-   bool automatic = false;
+   bool automatic = false; ///< If the change was automatically performed.
 
    private:
    void *d; // pointer for future extension;
 };
 
+static inline bool IsRemoval(const Kind &kind) { return kind > Kind::InstallEnd; }
+
+/**
+ * @struct Entry
+ * @brief Represents an entry in the APT history log.
+ */
 struct Entry
 {
    // Strings instead of string_view to avoid reference errors
-   std::string startDate;
+   std::string startDate;  
    std::string endDate;
    std::string cmdLine;
    std::string comment;
@@ -66,15 +86,34 @@ struct Entry
 // History is defined as the collection of entries in the history log(s).
 typedef std::vector<Entry> HistoryBuffer;
 
-// ParseSection - Take a tag section and parse it as a
-// history log entry.
+/**
+ * Parse a tag section as history log entry.
+ *
+ * @param section A tag section.
+ * @return A history log entry.
+ */
 APT_PUBLIC Entry ParseSection(const pkgTagSection &section);
-// ParseFile - Take a file descriptor and parse it as a history
-// log to the given buffer.
-// NOTE: Caller is responsible for closing the file descriptor.
+
+/**
+ * Parse a file descriptor to a history buffer.
+ *
+ * @param fd A file descriptor.
+ * @param buf A history buffer.
+ * @return true if successful, false otherwise.
+ *
+ * @note Caller is responsible for closing the file descriptor.
+ */
 APT_PUBLIC bool ParseFile(FileFd &fd, HistoryBuffer &buf);
+
 // ParseLogDir - Parse the apt history log directory to the buffer.
+/**
+ * Parse the APT history log directory to a buffer.
+ *
+ * @param buf A history buffer.
+ * @return true if successful, false otherwise.
+ */
 APT_PUBLIC bool ParseLogDir(HistoryBuffer &buf);
+
 } // namespace APT::History
 
 #endif
diff --git a/apt-private/private-history.cc b/apt-private/private-history.cc
index 05c908471..cf4540772 100644
--- a/apt-private/private-history.cc
+++ b/apt-private/private-history.cc
@@ -1,19 +1,29 @@
 // Include files
 #include <config.h>
 
+#include <apt-pkg/algorithms.h>
+#include <apt-pkg/cachefile.h>
+#include <apt-pkg/cacheset.h>
 #include <apt-pkg/cmndline.h>
 #include <apt-pkg/configuration.h>
+#include <apt-pkg/depcache.h>
 #include <apt-pkg/error.h>
 #include <apt-pkg/fileutl.h>
 #include <apt-pkg/history.h>
+#include <apt-pkg/pkgcache.h>
 #include <apt-pkg/tagfile.h>
 
+#include <apt-private/private-cachefile.h>
 #include <apt-private/private-history.h>
+#include <apt-private/private-install.h>
 
+#include <cassert>
 #include <iomanip>
 #include <iostream>
+#include <span>
 #include <stdexcept>
 #include <string>
+#include <unordered_map>
 
 #include <glob.h>
 #include <apti18n.h> // for coloring
@@ -21,6 +31,73 @@
 
 using namespace APT::History;
 
+// =============================================================================
+// Internal API extensions
+// =============================================================================
+
+//
+
+static Kind ReflectKind(const Kind &kind)
+{
+   switch (kind)
+   {
+   case Kind::Install:
+   case Kind::Reinstall:
+      return Kind::Remove;
+   case Kind::Upgrade:
+      return Kind::Downgrade;
+   case Kind::Downgrade:
+      return Kind::Upgrade;
+   case Kind::Remove:
+   case Kind::Purge:
+      return Kind::Install;
+   default:
+      assert(false);
+      return kind;
+   }
+}
+
+std::vector<Change> APT::Internal::FlattenChanges(const Entry &entry)
+{
+   std::vector<Change> flattened;
+
+   size_t total_size = 0;
+   for (const auto &[_, changes] : entry.changeMap)
+      total_size += changes.size();
+   flattened.reserve(total_size);
+
+   for (const auto &[_, changes] : entry.changeMap)
+      flattened.insert(flattened.end(), changes.begin(), changes.end());
+   return flattened;
+}
+
+Change APT::Internal::InvertChange(const Change &change)
+{
+   Change inverse = change;
+   inverse.kind = ReflectKind(change.kind);
+
+   // tailor change after what action was performed
+   switch (change.kind)
+   {
+   case Kind::Upgrade:
+      std::swap(inverse.currentVersion, inverse.candidateVersion);
+      break;
+   case Kind::Downgrade:
+      std::swap(inverse.currentVersion, inverse.candidateVersion);
+      break;
+   default:
+      break;
+   }
+
+   return inverse;
+}
+
+// =============================================================================
+// Output formatting
+// =============================================================================
+
+//
+
 // ShortenCommand - Take a command and shorten it such that it adheres
 // to the given maximum length.
 static std::string ShortenCommand(const std::string &cmd, const std::size_t maxLen)
@@ -108,7 +185,12 @@ static std::string GetKindString(const Entry &entry)
    return kindGroup;
 }
 
-// PrintHistory - Take a history vector and print it.
+// =============================================================================
+// Output printing
+// =============================================================================
+
+//
+
 static void PrintHistoryVector(const HistoryBuffer buf, int columnWidth)
 {
    // Calculate the width of the ID column, esentially the number of digits
@@ -201,6 +283,174 @@ static void PrintDetailedEntry(const HistoryBuffer &buf, const size_t id)
    }
 }
 
+// =============================================================================
+// Transaction helpers
+// =============================================================================
+
+//
+
+class TransactionController
+{
+   public:
+   TransactionController(CacheFile &cache) : Cache(cache),
+					     Fix(Cache.GetDepCache()),
+					     InstallAction(Cache, &Fix, false),
+					     RemoveAction(Cache, &Fix),
+					     HeldBackPackages()
+   {
+   }
+
+   bool AppendChange(const Change &change)
+   {
+      auto pkg = Cache->FindPkg(change.package);
+      if (pkg.end())
+	 return _error->Error(_("Could not find package %s"), change.package.data());
+      if (IsRemoval(change.kind))
+      {
+	 auto ver = pkg.CurrentVer();
+	 if (ver == nullptr)
+	 {
+	    _error->Warning(_("Tried to remove %s, but it is not installed"), change.package.data());
+	    return true;
+	 }
+
+	 RemoveAction(ver);
+	 return true;
+      }
+
+      auto ver = pkg.VersionList();
+      for (; not ver.end(); ++ver)
+	 if (strcmp(ver.VerStr(), change.currentVersion.data()) == 0)
+	    break;
+      if (ver.end())
+	 return _error->Error(_("Could not find given version %s of %s"), change.currentVersion.data(),
+			      change.package.data());
+      InstallAction(ver);
+      return true;
+   }
+
+   bool CommitChanges()
+   {
+      InstallAction.doAutoInstall();
+      OpTextProgress Progress(*_config);
+      bool const resolver_fail = Fix.Resolve(true, &Progress);
+      if (resolver_fail == false && Cache->BrokenCount() == 0)
+	 return false;
+      if (CheckNothingBroken(Cache) == false)
+	 return false;
+      return InstallPackages(Cache, HeldBackPackages, false, true);
+   }
+
+   private:
+   // This must be a reference for lifetime safety
+   CacheFile &Cache;
+   pkgProblemResolver Fix;
+   TryToInstall InstallAction;
+   TryToRemove RemoveAction;
+   APT::PackageVector HeldBackPackages;
+};
+
+static bool ParseId(const char *str, size_t &id, size_t max)
+{
+   try
+   {
+      id = std::stoi(str);
+   }
+   catch (const std::invalid_argument &e)
+   {
+      return _error->Error(_("'%s' not a valid ID."), str);
+   }
+   if (max < id)
+      return _error->Error(_("Transaction ID '%ld' out of bounds."), id);
+
+   return true;
+}
+
+// =============================================================================
+// Entrypoints
+// =============================================================================
+
+//
+
+bool DoHistoryUndo(CommandLine &Cmd)
+{
+   HistoryBuffer buf = {};
+   if (not ParseLogDir(buf))
+      return _error->Error(_("Could not read %s"),
+			   _config->FindFile("Dir::Log::History").data());
+   size_t id = 0;
+   if (not ParseId(*(Cmd.FileList + 1), id, buf.size() - 1))
+      return false;
+
+   CacheFile Cache;
+   if (Cache.BuildCaches(true) == false)
+      return false;
+   TransactionController Controller(Cache);
+
+   for (const auto &change : APT::Internal::FlattenChanges(buf[id]))
+      if (not Controller.AppendChange(APT::Internal::InvertChange(change)))
+	 return false;
+
+   return Controller.CommitChanges();
+}
+
+bool DoHistoryRollback(CommandLine &Cmd)
+{
+   HistoryBuffer buf = {};
+   if (not ParseLogDir(buf))
+      return _error->Error(_("Could not read %s"),
+			   _config->FindFile("Dir::Log::History").data());
+
+   size_t rollbackId = 0;
+   if (not ParseId(*(Cmd.FileList + 1), rollbackId, buf.size()))
+      return false;
+   CacheFile Cache;
+   if (Cache.BuildCaches(true) == false)
+      return false;
+   TransactionController Controller(Cache);
+
+   // Map to keep the effective change of each package
+   std::unordered_map<std::string, Change> effectiveChangeMap;
+   // Plus 1 for zero indexing
+   size_t numChanges = buf.size() - (rollbackId + 1);
+   std::span<Entry> bufSpan(buf.end() - numChanges, numChanges);
+   // Iterate in reverse to process changes LIFO
+   for (auto it = bufSpan.rbegin(); it != bufSpan.rend(); ++it)
+      for (const auto &change : APT::Internal::FlattenChanges(*it))
+	 effectiveChangeMap[change.package] = APT::Internal::InvertChange(change);
+
+   for (const auto &[_, change] : effectiveChangeMap)
+   {
+      if (not Controller.AppendChange(change))
+	 return false;
+   }
+
+   return Controller.CommitChanges();
+}
+
+bool DoHistoryRedo(CommandLine &Cmd)
+{
+   HistoryBuffer buf = {};
+   if (not ParseLogDir(buf))
+      return _error->Error(_("Could not read %s"),
+			   _config->FindFile("Dir::Log::History").data());
+
+   size_t id = 0;
+   if (not ParseId(*(Cmd.FileList + 1), id, buf.size() - 1))
+      return false;
+
+   CacheFile Cache;
+   if (Cache.BuildCaches(true) == false)
+      return false;
+   TransactionController Controller(Cache);
+
+   for (const auto &change : APT::Internal::FlattenChanges(buf[id]))
+      if (not Controller.AppendChange(change))
+	 return false;
+
+   return Controller.CommitChanges();
+}
+
 bool DoHistoryList(CommandLine &Cmd)
 {
    HistoryBuffer buf = {};
@@ -226,16 +476,8 @@ bool DoHistoryInfo(CommandLine &Cmd)
    size_t id = 0;
    for (size_t i = 1; i < Cmd.FileSize(); i++)
    {
-      try
-      {
-	 id = std::stoi(*(Cmd.FileList + i));
-      }
-      catch (const std::invalid_argument &e)
-      {
-	 return _error->Error(_("'%s' not a valid ID."), *(Cmd.FileList + i));
-      }
-      if (buf.size() <= id)
-	 return _error->Error(_("Transaction ID '%ld' out of bounds."), id);
+      if (not ParseId(*(Cmd.FileList + i), id, buf.size() - 1))
+	 return false;
       PrintDetailedEntry(buf, id);
    }
 
diff --git a/apt-private/private-history.h b/apt-private/private-history.h
index dfe0340f1..84556a09f 100644
--- a/apt-private/private-history.h
+++ b/apt-private/private-history.h
@@ -6,6 +6,36 @@
 #include <apt-pkg/macros.h>
 #include <apt-pkg/tagfile.h>
 
-APT_PUBLIC bool DoHistoryList(CommandLine &Cmd);
 APT_PUBLIC bool DoHistoryInfo(CommandLine &Cmd);
+APT_PUBLIC bool DoHistoryList(CommandLine &Cmd);
+APT_PUBLIC bool DoHistoryRedo(CommandLine &Cmd);
+APT_PUBLIC bool DoHistoryRollback(CommandLine &Cmd);
+APT_PUBLIC bool DoHistoryUndo(CommandLine &Cmd);
+
+namespace APT::Internal
+{
+using namespace History;
+/** 
+ * Flatten the changes contained within a history entry.
+ *
+ * This function extracts and returns a flat list of all changes
+ * from the given entry, preserving their order if applicable.
+ *
+ * @param entry A history entry containing a map of changes.
+ * @return A vector containing all individual changes from the entry.
+ */
+std::vector<Change> FlattenChanges(const Entry &entry);
+
+/** 
+ * Invert a change.
+ *
+ * This function inverts a change's effective action and version
+ * such that a change followed by its inverse has no effective change.
+ *
+ * @param change A transactional change.
+ * @return The given change's inverse.
+ */
+Change InvertChange(const Change &change);
+
+} // namespace APT::Internal
 #endif
diff --git a/cmdline/apt.cc b/cmdline/apt.cc
index 545b6d0b4..9acde0b32 100644
--- a/cmdline/apt.cc
+++ b/cmdline/apt.cc
@@ -95,6 +95,9 @@ static std::vector<aptDispatchWithHelp> GetCommands()			/*{{{*/
       // history stuff
       {"history-list", &DoHistoryList, _("show list of history")},
       {"history-info", &DoHistoryInfo, _("show info on specific transactions")},
+      {"history-redo", &DoHistoryRedo, _("redo transactions")},
+      {"history-undo", &DoHistoryUndo, _("undo transactions")},
+      {"history-rollback", &DoHistoryRollback, _("rollback transactions")},
 
       // misc
       {"edit-sources", &EditSources, _("edit the source information file")},
diff --git a/test/integration/test-history b/test/integration/test-history
index 76dc04630..e10dab08e 100755
--- a/test/integration/test-history
+++ b/test/integration/test-history
@@ -69,6 +69,48 @@ testsuccessequal "ID Command line             Date and Time          Action    C
 0  dummy                    dummy                  Install   1                        
 1  dummy                    dummy                  Install   1                        " normalizedlist
 
+################################################################################
+# Read previous history for manipulation
+################################################################################
+
+# Test history
+# 0 - Install pkg1
+# 1 - Install pkg2
+# 2 - Remove pkg1 (undo ID 0)
+# 3 - Install pkg1 (undo ID 2)
+# 4 - Remove pkg1 (redo ID 2)
+# 5 - Install pkg1 (rollback to ID 1)
+# 6 - Remove pkg1 (rollback to ID 2)
+
+testdpkginstalled pkg1
+# undo the first package install
+apt history-undo 0 -y >> /dev/null
+testdpkgnotinstalled pkg1
+# ...which generates a new id that we also undo
+apt history-undo 2 -y >>/dev/null
+testdpkginstalled pkg1
+
+# redo the removal
+apt history-redo 2 -y >> /dev/null
+testdpkgnotinstalled pkg1
+
+# rollback to ID 1 and it should be installed
+apt history-rollback 1 -y >> /dev/null 
+testdpkginstalled pkg1
+# rollback to ID 2 and it should be removed
+apt history-rollback 2 -y >> /dev/null
+testdpkgnotinstalled pkg1
+# rollback to ID 0 and it should be installed
+apt history-rollback 0 -y >> /dev/null
+testdpkginstalled pkg1
+# rollback to ID 4 and it should be removed
+apt history-rollback 4 -y >> /dev/null
+testdpkgnotinstalled pkg1
+
+################################################################################
+# Reset history log
+################################################################################
+
 msgmsg "Actionless group"
 cat > rootdir/var/log/apt/history.log << EOF
 Start-Date: dummy
@@ -86,4 +128,3 @@ End time: dummy
 Requested by: 
 Command line: install nothing
 Packages changed:" normalizedinfo
-