Add ${c,cxx}.deduplicate_export_libs() function

This function deduplicates interface library dependencies by removing
libraries that are also interface dependencies of the specified
libraries. This can result in significantly better build performance for
heavily interface-interdependent library families (for example, like Boost).

Typical usage:

import intf_libs = ...
import intf_libs += ...
...
import intf_libs += ...
intf_libs = $cxx.deduplicate_export_libs($intf_libs)

4 files changed, 154 insertions, 0 deletions

diff --git a/libbuild2/cc/common.cxx b/libbuild2/cc/common.cxx
index 934ea38..b3a5724 100644
--- a/libbuild2/cc/common.cxx
+++ b/libbuild2/cc/common.cxx
@@ -165,6 +165,8 @@ namespace build2
           // these variables are not overridable) and pass the base scope we
           // have already resolved.
           //
+          // See also deduplicate_export_libs() if changing anything here.
+          //
           // @@ PERF: do target_only (helps a bit in non-installed case)?
           //
           {
diff --git a/libbuild2/cc/functions.cxx b/libbuild2/cc/functions.cxx
index 7f9a6c2..6d54c49 100644
--- a/libbuild2/cc/functions.cxx
+++ b/libbuild2/cc/functions.cxx
@@ -399,6 +399,65 @@ namespace build2
               fail << t << " is not an object file target";
           }});
 
+      // $<module>.deduplicate_export_libs(<names>)
+      //
+      // Deduplicate interface library dependencies by removing libraries that
+      // are also interface dependencies of the specified libraries. This can
+      // result in significantly better build performance for heavily
+      // interface-interdependent library families (for example, like Boost).
+      // Typical usage:
+      //
+      // import intf_libs  = ...
+      // import intf_libs += ...
+      // ...
+      // import intf_libs += ...
+      // intf_libs = $cxx.deduplicate_export_libs($intf_libs)
+      //
+      // Notes:
+      //
+      // 1. We only consider unqualified absolute/normalized target names (the
+      //    idea is that the installed case will already be deduplicated).
+      //
+      // 2. We assume all the libraries listed are of the module type and only
+      //    look for cc.export.libs and <module>.export.libs.
+      //
+      // 3. No member/group selection/linkup: we resolve *.export.libs on
+      //    whatever is listed.
+      //
+      // Note that this function is not pure.
+      //
+      f.insert (".deduplicate_export_libs", false).
+        insert<const char*, names> (
+          [] (const scope* bs,
+              vector_view<value> vs,
+              const function_overload& f) -> value
+          {
+            const char* x (*reinterpret_cast<const char* const*> (&f.data));
+
+            if (bs == nullptr)
+              fail << f.name << " called out of scope";
+
+            const scope* rs (bs->root_scope ());
+
+            if (rs == nullptr)
+              fail << f.name << " called out of project";
+
+            const module* m (rs->find_module<module> (x));
+
+            if (m == nullptr)
+              fail << f.name << " called without " << x << " module loaded";
+
+            // We can assume the argument is present due to function's types
+            // signature.
+            //
+            names& r (vs[0].as<names> ());
+            m->deduplicate_export_libs (*bs,
+                                        vector<name> (r.begin (), r.end ()),
+                                        r);
+            return value (move (r));
+          },
+          x);
+
       // $<module>.find_system_library(<name>)
       //
       // Return the library path if the specified library exists in one of the
diff --git a/libbuild2/cc/link-rule.cxx b/libbuild2/cc/link-rule.cxx
index 4497382..76d8418 100644
--- a/libbuild2/cc/link-rule.cxx
+++ b/libbuild2/cc/link-rule.cxx
@@ -34,6 +34,92 @@ namespace build2
     using namespace bin;
     using build2::to_string;
 
+    bool link_rule::
+    deduplicate_export_libs (const scope& bs,
+                             const vector<name>& ns,
+                             names& r,
+                             vector<reference_wrapper<const name>>* seen) const
+    {
+      bool top (seen == nullptr);
+
+      vector<reference_wrapper<const name>> seen_storage;
+      if (top)
+        seen = &seen_storage;
+
+      // The plan is as follows: resolve the target names in ns into targets
+      // and then traverse their interface dependencies recursively removing
+      // duplicates from the list r.
+      //
+      for (auto i (ns.begin ()), e (ns.end ()); i != e; ++i)
+      {
+        if (i->pair)
+        {
+          ++i;
+          continue;
+        }
+
+        const name& n (*i);
+
+        if (n.qualified () ||
+            !(n.dir.absolute () && n.dir.normalized ()) ||
+            !(n.type == "lib" || n.type == "liba" || n.type != "libs"))
+          continue;
+
+        if (!top)
+        {
+          // Check if we have already seen this library among interface
+          // dependencies of our interface dependencies.
+          //
+          if (find (seen->begin (), seen->end (), n) != seen->end ())
+            continue;
+
+          // Remove duplicates. Because we only consider absolute/normalized
+          // target names, we can just compare their names.
+          //
+          for (auto i (r.begin ()); i != r.end (); )
+          {
+            if (i->pair)
+              i += 2;
+            else if (*i == n)
+              i = r.erase (i);
+            else
+              ++i;
+          }
+
+          // @@ TODO: we could optimize this further by returning false if
+          //    there are no viable candidates (e.g., only pairs/qualified/etc
+          //    left).
+          //
+          if (r.empty ())
+            return false;
+        }
+
+        if (const target* t = search_existing (n, bs, dir_path () /* out */))
+        {
+          // The same logic as in process_libraries().
+          //
+          const scope& bs (t->base_scope ());
+
+          if (lookup l = t->lookup_original (c_export_libs, false, &bs).first)
+          {
+            if (!deduplicate_export_libs (bs, cast<vector<name>> (l), r, seen))
+              return false;
+          }
+
+          if (lookup l = t->lookup_original (x_export_libs, false, &bs).first)
+          {
+            if (!deduplicate_export_libs (bs, cast<vector<name>> (l), r, seen))
+              return false;
+          }
+        }
+
+        if (!top)
+          seen->push_back (n);
+      }
+
+      return true;
+    }
+
     optional<path> link_rule::
     find_system_library (const strings& l) const
     {
diff --git a/libbuild2/cc/link-rule.hxx b/libbuild2/cc/link-rule.hxx
index 3d801d6..0fc1790 100644
--- a/libbuild2/cc/link-rule.hxx
+++ b/libbuild2/cc/link-rule.hxx
@@ -214,6 +214,13 @@ namespace build2
       append_binless_modules (strings&, sha256*,
                               const scope&, action, const file&) const;
 
+      bool
+      deduplicate_export_libs (
+        const scope&,
+        const vector<name>&,
+        names&,
+        vector<reference_wrapper<const name>>* = nullptr) const;
+
       optional<path>
       find_system_library (const strings&) const;