Prune library graph traversal for recursively-binless libraries

3 files changed, 213 insertions, 57 deletions

diff --git a/libbuild2/cc/common.cxx b/libbuild2/cc/common.cxx
index d1cee6f..8cce132 100644
--- a/libbuild2/cc/common.cxx
+++ b/libbuild2/cc/common.cxx
@@ -96,10 +96,10 @@ namespace build2
                            const small_vector<reference_wrapper<
                              const string>, 2>&,            // Library "name".
                            lflags,                          // Link flags.
-                           const string* type,              // cc.type
+                           const string* type,              // whole cc.type
                            bool sys)>& proc_lib,            // System library?
       const function<bool (const target&,
-                           const string& type,              // cc.type
+                           const string& lang,              // lang from cc.type
                            bool com,                        // cc. or x.
                            bool exp)>& proc_opt,            // *.export.
       bool self /*= false*/,                     // Call proc_lib on l?
@@ -136,25 +136,45 @@ namespace build2
         // performance we use lookup_original() directly and only look in the
         // target (so no target type/pattern-specific).
         //
-        const string* t (
+        const string* pt (
           cast_null<string> (
             l.state[a].lookup_original (c_type, true /* target_only */).first));
 
+        // cc.type value format is <lang>[,...].
+        //
+        size_t p;
+        const string& t (pt != nullptr
+                         ? ((p = pt->find (',')) == string::npos
+                            ? *pt
+                            : string (*pt, 0, p))
+                         : string ());
+
+        // Why are we bothering with impl for binless libraries since all
+        // their dependencies are by definition interface? Well, for one, it
+        // could be that it is dynamically-binless (e.g., binless on some
+        // platforms or in some configurations and binful on/in others). In
+        // this case it would be helpful to have a uniform semantics so that,
+        // for example, *.libs are used for liba{} regardless of whether it is
+        // binless or not. On the other hand, having to specify both
+        // *.export.libs=-lm and *.libs=-lm (or *.export.impl_libs) for an
+        // always-binless library is sure not very intuitive. Not sure if we
+        // can win here.
+        //
         bool impl (proc_impl && proc_impl (l, la));
         bool cc (false), same (false);
 
-        if (t != nullptr)
+        if (!t.empty ())
         {
-          cc   = (*t == "cc");
-          same = (!cc && *t == x);
+          cc   = (t == "cc");
+          same = (!cc && t == x);
         }
 
-        const scope& bs (t == nullptr || cc ? top_bs : l.base_scope ());
+        const scope& bs (t.empty () || cc ? top_bs : l.base_scope ());
 
         lookup c_e_libs;
         lookup x_e_libs;
 
-        if (t != nullptr)
+        if (!t.empty ())
         {
           // Note that we used to treat *.export.libs set on the liba/libs{}
           // members as *.libs overrides rather than as member-specific
@@ -173,8 +193,6 @@ namespace build2
           //
           // See also deduplicate_export_libs() if changing anything here.
           //
-          // @@ PERF: do target_only (helps a bit in non-installed case)?
-          //
           {
             const variable& v (impl ? c_export_impl_libs : c_export_libs);
             c_e_libs = l.lookup_original (v, false, &bs).first;
@@ -185,7 +203,7 @@ namespace build2
             const variable& v (
               same
               ? (impl ? x_export_impl_libs : x_export_libs)
-              : vp[*t + (impl ? ".export.impl_libs" : ".export.libs")]);
+              : vp[t + (impl ? ".export.impl_libs" : ".export.libs")]);
             x_e_libs = l.lookup_original (v, false, &bs).first;
           }
 
@@ -198,7 +216,7 @@ namespace build2
             //
             if (cc)
             {
-              if (!proc_opt (l, *t, true, true)) break;
+              if (!proc_opt (l, t, true, true)) break;
             }
             else
             {
@@ -215,24 +233,24 @@ namespace build2
                   //
                   // Note: options come from *.export.* variables.
                   //
-                  if (!proc_opt (l, *t, false, true) ||
-                      !proc_opt (l, *t, true,  true)) break;
+                  if (!proc_opt (l, t, false, true) ||
+                      !proc_opt (l, t, true,  true)) break;
                 }
                 else
                 {
                   // For default export we use the same options as were used
                   // to build the library.
                   //
-                  if (!proc_opt (l, *t, false, false) ||
-                      !proc_opt (l, *t, true,  false)) break;
+                  if (!proc_opt (l, t, false, false) ||
+                      !proc_opt (l, t, true,  false)) break;
                 }
               }
               else
               {
                 // Interface: only add *.export.* (interface dependencies).
                 //
-                if (!proc_opt (l, *t, false, true) ||
-                    !proc_opt (l, *t, true,  true)) break;
+                if (!proc_opt (l, t, false, true) ||
+                    !proc_opt (l, t, true,  true)) break;
               }
             }
           }
@@ -273,12 +291,12 @@ namespace build2
           const file* f;
           const path& p ((f = l.is_a<file> ()) ? f->path () : empty_path);
 
-          bool s (t != nullptr // If cc library (matched or imported).
+          bool s (pt != nullptr // If cc library (matched or imported).
                   ? cast_false<bool> (l.vars[c_system])
                   : !p.empty () && sys (top_sysd, p.string ()));
 
           proc_lib_name = {p.string ()};
-          if (!proc_lib (&chain->back (), proc_lib_name, lf, t, s))
+          if (!proc_lib (&chain->back (), proc_lib_name, lf, pt, s))
             break;
         }
 
@@ -292,17 +310,17 @@ namespace build2
         {
           // Use the search dirs corresponding to this library scope/type.
           //
-          sysd = (t == nullptr || cc)
+          sysd = (t.empty () || cc)
           ? &top_sysd // Imported library, use importer's sysd.
           : &cast<dir_paths> (
             bs.root_scope ()->vars[same
                                    ? x_sys_lib_dirs
-                                   : bs.ctx.var_pool[*t + ".sys_lib_dirs"]]);
+                                   : bs.ctx.var_pool[t + ".sys_lib_dirs"]]);
         };
 
         auto find_linfo = [top_li, t, cc, &bs, &l, &li] ()
         {
-          li = (t == nullptr || cc)
+          li = (t.empty () || cc)
           ? top_li
           : optional<linfo> (link_info (bs, link_type (l).type)); // @@ PERF
         };
@@ -353,7 +371,7 @@ namespace build2
         // If it is not a C-common library, then it probably doesn't have any
         // of the *.libs.
         //
-        if (t != nullptr)
+        if (!t.empty ())
         {
           optional<dir_paths> usrd; // Extract lazily.
 
@@ -453,6 +471,9 @@ namespace build2
             {
               const name& n (*i);
 
+              // Note: see also recursively-binless logic in link_rule if
+              //       changing anything in simple library handling.
+              //
               if (n.simple ())
               {
                 // This is something like -lpthread or shell32.lib so should
@@ -619,6 +640,9 @@ namespace build2
           }
           else
           {
+            // Note: see also recursively-binless logic in link_rule if
+            //       changing anything here.
+
             if (impl)
             {
               // Interface and implementation: as discussed above, we can have
@@ -645,7 +669,7 @@ namespace build2
                 //
                 if (proc_lib)
                 {
-                  const variable& v (same ? x_libs : vp[*t + ".libs"]);
+                  const variable& v (same ? x_libs : vp[t + ".libs"]);
                   proc_impl (l.lookup_original (c_libs, false, &bs).first);
                   proc_impl (l.lookup_original (v, false, &bs).first);
                 }
@@ -778,7 +802,7 @@ namespace build2
           fail << "unable to find library " << pk;
       }
 
-      // If this is lib{}/libu*{}, pick appropriate member unless we were
+      // If this is lib{}/libul{}, pick appropriate member unless we were
       // instructed not to.
       //
       if (li)
diff --git a/libbuild2/cc/init.cxx b/libbuild2/cc/init.cxx
index 5c15835..75b32bb 100644
--- a/libbuild2/cc/init.cxx
+++ b/libbuild2/cc/init.cxx
@@ -133,15 +133,19 @@ namespace build2
       vp.insert<string> ("cc.runtime");
       vp.insert<string> ("cc.stdlib");
 
-      // Target type, for example, "C library" or "C++ library". Should be set
-      // on the target as a rule-specific variable by the matching rule to the
-      // name of the module (e.g., "c", "cxx"). Currenly only set for
-      // libraries and is used to decide which *.libs to use during static
-      // linking.
-      //
-      // It can also be the special "cc" value which means a C-common library
-      // but specific language is not known. Used in the import installed
-      // logic.
+      // Library target type in the <lang>[,<type>...] form where <lang> is
+      // "c" (C library), "cxx" (C++ library), or "cc" (C-common library but
+      // the specific language is not known). Currently recognized <type>
+      // values are "binless" (library is binless) and "recursively-binless"
+      // (library and all its prerequisite libraries are binless). Note that
+      // another indication of a binless library is an empty path, which could
+      // easier/faster to check. Note also that there should be no whitespaces
+      // of any kind and <lang> is always first.
+      //
+      // This value should be set on the library target as a rule-specific
+      // variable by the matching rule. Currently <lang> is used to decide
+      // which *.libs to use during static linking. The "cc" language is used
+      // in the import installed logic.
       //
       // Note that this variable cannot be set via the target type/pattern-
       // specific mechanism (see process_libraries()).
diff --git a/libbuild2/cc/link-rule.cxx b/libbuild2/cc/link-rule.cxx
index ffb7dfb..f766f84 100644
--- a/libbuild2/cc/link-rule.cxx
+++ b/libbuild2/cc/link-rule.cxx
@@ -833,6 +833,10 @@ namespace build2
         //
         if (const libul* ul = pt->is_a<libul> ())
         {
+          // @@ Isn't libul{} member already picked or am I missing something?
+          //    If not, then we may need the same in recursive-binless logic.
+          //
+          assert (false); // @@ TMP
           ux = &link_member (*ul, a, li)->as<libux> ();
         }
         else if ((ux = pt->is_a<libue> ()) ||
@@ -849,6 +853,19 @@ namespace build2
       return nullptr;
     };
 
+    // Given the cc.type value return true if the library is recursively
+    // binless.
+    //
+    static inline bool
+    recursively_binless (const string& type)
+    {
+      size_t p (type.find ("recursively-binless"));
+      return (p != string::npos  &&
+              type[p - 1] == ',' && // <lang> is first.
+              (type[p += 19] == '\0' || type[p] == ','));
+    }
+
+
     recipe link_rule::
     apply (action a, target& xt, match_extra&) const
     {
@@ -869,11 +886,6 @@ namespace build2
       otype ot (lt.type);
       linfo li (link_info (bs, ot));
 
-      // Set the library type (C, C++, etc) as rule-specific variable.
-      //
-      if (lt.library ())
-        t.state[a].assign (c_type) = string (x);
-
       bool binless (lt.library ()); // Binary-less until proven otherwise.
       bool user_binless (lt.library () && cast_false<bool> (t[b_binless]));
 
@@ -1220,6 +1232,121 @@ namespace build2
       //
       match_members (a, t, pts, start);
 
+      // Check if we have any binful utility libraries.
+      //
+      bool rec_binless; // Recursively-binless.
+      if (binless)
+      {
+        if (const libux* l = find_binful (a, t, li))
+        {
+          binless = false;
+
+          if (user_binless)
+            fail << t << " cannot be binless due to binful " << *l
+                 << " prerequisite";
+        }
+
+        // See if we are recursively-binless.
+        //
+        if (binless)
+        {
+          rec_binless = true;
+
+          for (const target* pt: t.prerequisite_targets[a])
+          {
+            if (pt == nullptr || unmark (pt) != 0) // See above.
+              continue;
+
+            const file* ft;
+            if ((ft = pt->is_a<libs> ()) ||
+                (ft = pt->is_a<liba> ()) ||
+                (ft = pt->is_a<libux> ()))
+            {
+              if (ft->path ().empty ()) // Binless.
+              {
+                // The same lookup as in process_libraries().
+                //
+                if (const string* t = cast_null<string> (
+                      ft->state[a].lookup_original (
+                        c_type, true /* target_only */).first))
+                {
+                  if (recursively_binless (*t))
+                    continue;
+                }
+              }
+
+              rec_binless = false;
+              break;
+            }
+          }
+
+          // Another thing we must check is for the presence of any simple
+          // libraries (-lpthread, shell32.lib, etc) in *.export.libs. See
+          // process_libraries() for details.
+          //
+          if (rec_binless)
+          {
+            auto find = [&t, &bs] (const variable& v) -> lookup
+            {
+              return t.lookup_original (v, false, &bs).first;
+            };
+
+            auto has_simple = [] (lookup l)
+            {
+              if (const auto* ns = cast_null<vector<name>> (l))
+              {
+                for (auto i (ns->begin ()), e (ns->end ()); i != e; ++i)
+                {
+                  if (i->pair)
+                    ++i;
+                  else if (i->simple ()) // -l<name>, etc.
+                    return true;
+                }
+              }
+
+              return false;
+            };
+
+            if (lt.shared_library ()) // process_libraries()::impl == false
+            {
+              if (has_simple (find (x_export_libs)) ||
+                  has_simple (find (c_export_libs)))
+                rec_binless = false;
+            }
+            else // process_libraries()::impl == true
+            {
+              lookup x (find (x_export_impl_libs));
+              lookup c (find (c_export_impl_libs));
+
+              if (x.defined () || c.defined ())
+              {
+                if (has_simple (x) || has_simple (c))
+                  rec_binless = false;
+              }
+              else
+              {
+                if (has_simple (find (x_libs)) || has_simple (find (c_libs)))
+                  rec_binless = false;
+              }
+            }
+          }
+        }
+      }
+
+      // Set the library type (C, C++, binless) as rule-specific variable.
+      //
+      if (lt.library ())
+      {
+        string v (x);
+
+        if (rec_binless)
+          v += ",recursively-binless";
+        else if (binless)
+          v += ",binless";
+
+        t.state[a].assign (c_type) = move (v);
+      }
+
       // If we have any update during match prerequisites, now is the time to
       // update them. Note that we have to do it before any further matches
       // since they may rely on these prerequisites already being updated (for
@@ -1236,20 +1363,6 @@ namespace build2
       if (update_match)
         update_during_match_prerequisites (trace, a, t, 2 /* mask */);
 
-      // Check if we have any binful utility libraries.
-      //
-      if (binless)
-      {
-        if (const libux* l = find_binful (a, t, li))
-        {
-          binless = false;
-
-          if (user_binless)
-            fail << t << " cannot be binless due to binful " << *l
-                 << " prerequisite";
-        }
-      }
-
       // Now that we know for sure whether we are binless, derive file name(s)
       // and add ad hoc group members. Note that for binless we still need the
       // .pc member (whose name depends on the libray prefix) so we take care
@@ -1950,7 +2063,7 @@ namespace build2
         const target* const* lc,
         const small_vector<reference_wrapper<const string>, 2>& ns,
         lflags f,
-        const string* type, // cc.type
+        const string* type, // Whole cc.type in the <lang>[,...] form.
         bool)
       {
         // Note: see also make_header_sidebuild().
@@ -1971,6 +2084,13 @@ namespace build2
         // that range of elements to the end of args. See GitHub issue #114
         // for details.
         //
+        // One case where we can prune the graph is if the library is
+        // recursively-binless. It's tempting to wish that we can do the same
+        // just for binless, but alas that's not the case: we have to hoist
+        // its binful interface dependency because, for example, it must
+        // appear after the preceding static library of which this binless
+        // library is a dependency.
+        //
         // From the process_libraries() semantics we know that this callback
         // is always called and always after the options callbacks.
         //
@@ -1982,8 +2102,13 @@ namespace build2
         {
           // Hoist the elements corresponding to this library to the end.
           // Note that we cannot prune the traversal since we need to see the
-          // last occurrence of each library.
+          // last occurrence of each library, unless the library is
+          // recursively-binless (in which case there will be no need to
+          // hoist since there can be no libraries among the elements).
           //
+          if (type != nullptr && recursively_binless (*type))
+            return false;
+
           d.ls.hoist (d.args, *al);
           return true;
         }
@@ -2029,7 +2154,10 @@ namespace build2
           // install or both not. We can only do this if the library is build
           // by our link_rule.
           //
-          else if (d.for_install && type != nullptr && *type != "cc")
+          else if (d.for_install &&
+                   type != nullptr &&
+                   *type != "cc" &&
+                   type->compare (0, 3, "cc,") != 0)
           {
             auto& md (l->data<link_rule::match_data> ());
             assert (md.for_install); // Must have been executed.