Columnar output for package lists similar to 'ls'

This change makes it a bit easier to quickly grasp the changes
about to be performed by apt.

It displays package lists in a columnar format by default,
similar to what `ls` produces for files.

A new long option `--no-list-columns` and an associated
`APT::Get::List-Columns` config setting control the behavior.

Usage example, with 60 column wide terminal:

```
$ sudo apt upgrade                                          |
Reading package lists... Done                               |
Building dependency tree... Done                            |
Reading state information... Done                           |
Calculating upgrade... Done                                 |
The following packages were automatically installed and are |
no longer required:                                         |
  libappindicator1 libindicator7                            |
  libdbusmenu-gtk4 linux-image-5.14.0-4-amd64               |
Use 'sudo apt autoremove' to remove them.                   |
The following packages have been kept back:                 |
  criu        linux-headers-amd64 nvidia-settings           |
  libxnvctrl0 nvidia-modprobe     xwayland                  |
0 upgraded, 0 newly installed, 0 to remove and 6 not upgrade|
d.                                                          |
```

The effect becomes more pronounced with more packages (e.g. when
doing a dist-upgrade).

7 files changed, 111 insertions, 12 deletions

diff --git a/apt-private/private-cmndline.cc b/apt-private/private-cmndline.cc
index 79881d034..cbab22031 100644
--- a/apt-private/private-cmndline.cc
+++ b/apt-private/private-cmndline.cc
@@ -184,7 +184,8 @@ static bool addArgumentsAPTGet(std::vector<CommandLine::Args> &Args, char const
       addArg(0, "show-progress", "DpkgPM::Progress", 0);
       addArg('f', "fix-broken", "APT::Get::Fix-Broken", 0);
       addArg(0, "purge", "APT::Get::Purge", 0);
-      addArg('V',"verbose-versions","APT::Get::Show-Versions",0);
+      addArg('V',"verbose-versions", "APT::Get::Show-Versions",0);
+      addArg(0, "list-columns", "APT::Get::List-Columns", 0);
       addArg(0, "autoremove", "APT::Get::AutomaticRemove", 0);
       addArg(0, "auto-remove", "APT::Get::AutomaticRemove", 0);
       addArg(0, "reinstall", "APT::Get::ReInstall", 0);
diff --git a/apt-private/private-output.cc b/apt-private/private-output.cc
index 93b942458..f04c35b8a 100644
--- a/apt-private/private-output.cc
+++ b/apt-private/private-output.cc
@@ -316,6 +316,83 @@ void ListSingleVersion(pkgCacheFile &CacheFile, pkgRecords &records,	/*{{{*/
    out << output;
 }
 									/*}}}*/
+// ShowWithColumns - Show a list in the style of ls			/*{{{*/
+// ---------------------------------------------------------------------
+/* This prints out a vector of strings with the given indent and in as
+   many columns as will fit the screen width.
+   
+   The output looks like:
+  abiword                debootstrap                  gir1.2-upowerglib-1.0
+  abiword-common         dh-make                      google-chrome-beta
+  abiword-plugin-grammar dmeventd                     gstreamer1.0-clutter-3.0
+  binfmt-support         dmsetup                      hostname
+  console-setup          evolution-data-server        iproute2
+  console-setup-linux    evolution-data-server-common
+  coreutils              ffmpeg
+ */
+struct columnInfo
+{
+   bool ValidLen;
+   size_t LineWidth;
+   vector<size_t> RemainingWidths;
+};
+void ShowWithColumns(ostream &out, vector<string> const &List, size_t Indent, size_t ScreenWidth)
+{
+   constexpr size_t MinColumnWidth = 2;
+   constexpr size_t ColumnSpace = 1;
+
+   size_t const ListSize = List.size();
+   size_t const MaxScreenCols = (ScreenWidth - Indent) /
+         MinColumnWidth;
+   size_t const MaxNumCols = min(MaxScreenCols, ListSize);
+
+   vector<columnInfo> ColumnInfo(MaxNumCols);
+   for (size_t I = 0; I < MaxNumCols; ++I) {
+      ColumnInfo[I].ValidLen = true;
+      ColumnInfo[I].LineWidth = (I + 1) * MinColumnWidth;
+      ColumnInfo[I].RemainingWidths.resize(I + 1, MinColumnWidth);
+   }
+
+   for (size_t I = 0; I < ListSize; ++I) {
+      for (size_t J = 0; J < MaxNumCols; ++J) {
+         auto& Col = ColumnInfo[J];
+         if (!Col.ValidLen)
+            continue;
+
+         size_t Idx = I / ((ListSize + J) / (J + 1));
+         size_t RealColLen = List[I].size() + (Idx == J ? 0 : ColumnSpace);
+         if (Col.RemainingWidths[Idx] < RealColLen) {
+            Col.LineWidth += RealColLen - Col.RemainingWidths[Idx];
+            Col.RemainingWidths[Idx] = RealColLen;
+            Col.ValidLen = Col.LineWidth < ScreenWidth;
+         }
+      }
+   }
+   size_t NumCols = MaxNumCols;
+   while (NumCols > 1 && !ColumnInfo[NumCols - 1].ValidLen)
+      --NumCols;
+
+   size_t NumRows = ListSize / NumCols + (ListSize % NumCols != 0);
+   auto const &LineFormat = ColumnInfo[NumCols - 1];
+   for (size_t Row = 0; Row < NumRows; ++Row) {
+      size_t Col = 0;
+      size_t I = Row;
+      out << string(Indent, ' ');
+      while (true) {
+         out << List[I];
+
+         size_t CurLen = List[I].size();
+         size_t MaxLen = LineFormat.RemainingWidths[Col++];
+         I += NumRows;
+         if (I >= ListSize)
+            break;
+
+         out << string(MaxLen - CurLen, ' ');
+      }
+      out << endl;
+   }
+}
+									/*}}}*/
 // ShowBroken - Debugging aide						/*{{{*/
 // ---------------------------------------------------------------------
 /* This prints out the names of all the packages that are broken along
diff --git a/apt-private/private-output.h b/apt-private/private-output.h
index c3e73d592..dcffd1880 100644
--- a/apt-private/private-output.h
+++ b/apt-private/private-output.h
@@ -10,6 +10,7 @@
 #include <functional>
 #include <iostream>
 #include <string>
+#include <vector>
 
 // forward declaration
 class pkgCacheFile;
@@ -35,6 +36,8 @@ void ListSingleVersion(pkgCacheFile &CacheFile, pkgRecords &records,
 APT_PUBLIC void ShowBroken(std::ostream &out, CacheFile &Cache, bool const Now);
 APT_PUBLIC void ShowBroken(std::ostream &out, pkgCacheFile &Cache, bool const Now);
 
+APT_PUBLIC void ShowWithColumns(std::ostream &out, const std::vector<std::string> &List, size_t Indent, size_t ScreenWidth);
+
 template<class Container, class PredicateC, class DisplayP, class DisplayV> bool ShowList(std::ostream &out, std::string const &Title,
       Container const &cont,
       PredicateC Predicate,
@@ -44,7 +47,9 @@ template<class Container, class PredicateC, class DisplayP, class DisplayV> bool
    size_t const ScreenWidth = (::ScreenWidth > 3) ? ::ScreenWidth - 3 : 0;
    int ScreenUsed = 0;
    bool const ShowVersions = _config->FindB("APT::Get::Show-Versions", false);
+   bool const ListColumns = _config->FindB("APT::Get::List-Columns", true);
    bool printedTitle = false;
+   std::vector<std::string> PackageList;
 
    for (auto const &Pkg: cont)
    {
@@ -67,24 +72,32 @@ template<class Container, class PredicateC, class DisplayP, class DisplayV> bool
       else
       {
 	 std::string const PkgName = PkgDisplay(Pkg);
-	 if (ScreenUsed == 0 || (ScreenUsed + PkgName.length()) >= ScreenWidth)
-	 {
-	    out << std::endl << "  ";
-	    ScreenUsed = 0;
-	 }
-	 else if (ScreenUsed != 0)
+	 if (ListColumns)
+	    PackageList.push_back(PkgName);
+	 else
 	 {
-	    out << " ";
-	    ++ScreenUsed;
+	    if (ScreenUsed == 0 || (ScreenUsed + PkgName.length()) >= ScreenWidth)
+	    {
+	       out << std::endl
+		   << "  ";
+	       ScreenUsed = 0;
+	    }
+	    else if (ScreenUsed != 0)
+	    {
+	       out << " ";
+	       ++ScreenUsed;
+	    }
+	    out << PkgName;
+	    ScreenUsed += PkgName.length();
 	 }
-	 out << PkgName;
-	 ScreenUsed += PkgName.length();
       }
    }
 
    if (printedTitle == true)
    {
       out << std::endl;
+      if (ListColumns)
+	 ShowWithColumns(out, PackageList, 2, ScreenWidth);
       return false;
    }
    return true;
diff --git a/completions/bash/apt b/completions/bash/apt
index 59a8eaa94..7c4b44a1a 100644
--- a/completions/bash/apt
+++ b/completions/bash/apt
@@ -73,7 +73,7 @@ _apt()
         case ${command-} in
             install|reinstall|remove|purge|upgrade|dist-upgrade|full-upgrade|autoremove|autopurge)
                 COMPREPLY=( $( compgen -W '--show-progress
-                  --fix-broken --purge --verbose-versions --auto-remove
+                  --fix-broken --purge --verbose-versions --no-list-columns --auto-remove
                   -s --simulate --dry-run
                   --download
                   --fix-missing
diff --git a/doc/apt-get.8.xml b/doc/apt-get.8.xml
index da1e91997..807345a3d 100644
--- a/doc/apt-get.8.xml
+++ b/doc/apt-get.8.xml
@@ -410,6 +410,12 @@
      Configuration Item: <literal>APT::Get::Show-Versions</literal>.</para></listitem>
      </varlistentry>
 
+     <varlistentry><term><option>--no-list-columns</option></term>
+     <listitem><para>Display package lists without arranging them in columns. By
+     default, package lists are printed in the style of the "ls" command.
+     Configuration Item: <literal>APT::Get::List-Columns</literal>.</para></listitem>
+     </varlistentry>
+
      <varlistentry><term><option>-a</option></term>
                    <term><option>--host-architecture</option></term>
      <listitem><para>This option controls the architecture packages are built for
diff --git a/doc/examples/configure-index b/doc/examples/configure-index
index da4998b4d..9a2bcbf1c 100644
--- a/doc/examples/configure-index
+++ b/doc/examples/configure-index
@@ -104,6 +104,7 @@ APT
 
      Show-Upgraded "<BOOL>";
      Show-Versions "<BOOL>";
+     List-Columns "<BOOL>";
      Upgrade "<BOOL>";
      Only-Upgrade "<BOOL>";
      Upgrade-Allow-New "<BOOL>";
diff --git a/test/integration/framework b/test/integration/framework
index 0570d5c8e..57d6849da 100644
--- a/test/integration/framework
+++ b/test/integration/framework
@@ -444,6 +444,7 @@ _setupprojectenvironment() {
 	echo "Dir::Etc \"etc/apt\";" >> aptconfig.conf
 	echo "Dir::Log \"var/log/apt\";" >> aptconfig.conf
 	echo "APT::Get::Show-User-Simulation-Note \"false\";" >> aptconfig.conf
+	echo "APT::Get::List-Columns \"false\";" >> aptconfig.conf
 	echo "Dir::Bin::Methods \"${TMPWORKINGDIRECTORY}/rootdir/usr/lib/apt/methods\";" >> aptconfig.conf
 	# either store apt-key were we can access it, even if we run it as a different user
 	#cp "${APTCMDLINEBINDIR}/apt-key" "${TMPWORKINGDIRECTORY}/rootdir/usr/bin/"