Implement traversal pruning in process_libraries()

8 files changed, 503 insertions, 421 deletions

diff --git a/libbuild2/cc/common.cxx b/libbuild2/cc/common.cxx
index 79e53bb..4b4aef8 100644
--- a/libbuild2/cc/common.cxx
+++ b/libbuild2/cc/common.cxx
@@ -39,6 +39,12 @@ namespace build2
     // 3. dependency libs (prerequisite_targets, left to right, depth-first)
     // 4. dependency libs (*.libs variables).
     //
+    // If either proc_opt or proc_lib return false, then any further
+    // processing of this library or its dependencies is skipped. This can be
+    // used to "prune" the graph traversal in case of duplicates. Note that
+    // proc_opt is called twice for each library so carefully consider from
+    // which to return false.
+    //
     // The first argument to proc_lib is a pointer to the last element of an
     // array that contains the current library dependency chain all the way to
     // the library passed to process_libraries(). The first element of this
@@ -82,12 +88,12 @@ namespace build2
       lflags lf,
       const function<bool (const target&,
                            bool la)>& proc_impl,            // Implementation?
-      const function<void (const target* const*,            // Can be NULL.
+      const function<bool (const target* const*,            // Can be NULL.
                            const small_vector<reference_wrapper<
                              const string>, 2>&,            // Library "name".
                            lflags,                          // Link flags.
                            bool sys)>& proc_lib,            // System library?
-      const function<void (const target&,
+      const function<bool (const target&,
                            const string& type,              // cc.type
                            bool com,                        // cc. or x.
                            bool exp)>& proc_opt,            // *.export.
@@ -108,457 +114,467 @@ namespace build2
           chain->push_back (nullptr);
       }
 
-      // See what type of library this is (C, C++, etc). Use it do decide
-      // which x.libs variable name to use. If it's unknown, then we only
-      // look into prerequisites. Note: lookup starting from rule-specific
-      // variables (target should already be matched).
+      // Add the library to the chain.
       //
-      const string* t (cast_null<string> (l.state[a][c_type]));
-
-      bool impl (proc_impl && proc_impl (l, la));
-      bool cc (false), same (false);
+      if (self && proc_lib)
+        chain->push_back (&l);
 
       auto& vp (top_bs.ctx.var_pool);
-      lookup c_e_libs;
-      lookup x_e_libs;
 
-      if (t != nullptr)
+      do // Breakout loop.
       {
-        cc   = (*t == "cc");
-        same = (!cc && *t == x);
-
-        // Note that we used to treat *.export.libs set on the liba/libs{}
-        // members as *.libs overrides rather than as member-specific
-        // interface dependencies. This difference in semantics proved to be
-        // surprising so now we have separate *.export.impl_libs for that.
-        // Note that in this case options come from *.export.* variables.
-        //
-        // Note also that we only check for *.*libs. If one doesn't have any
-        // libraries but needs to set, say, *.loptions, then *.*libs should be
-        // set to NULL or empty (this is why we check for the result being
-        // defined).
+        // See what type of library this is (C, C++, etc). Use it do decide
+        // which x.libs variable name to use. If it's unknown, then we only
+        // look into prerequisites. Note: lookup starting from rule-specific
+        // variables (target should already be matched).
         //
-        c_e_libs = l[impl ? c_export_impl_libs : c_export_libs];
+        const string* t (cast_null<string> (l.state[a][c_type]));
 
-        if (!cc)
-          x_e_libs = l[same
-                       ? (impl ? x_export_impl_libs : x_export_libs)
-                       : vp[*t + (impl ? ".export.impl_libs" : ".export.libs")]];
+        bool impl (proc_impl && proc_impl (l, la));
+        bool cc (false), same (false);
 
-        // Process options first.
-        //
-        if (proc_opt)
+        lookup c_e_libs;
+        lookup x_e_libs;
+
+        if (t != nullptr)
         {
-          // If all we know is it's a C-common library, then in both cases we
-          // only look for cc.export.*.
+          cc   = (*t == "cc");
+          same = (!cc && *t == x);
+
+          // Note that we used to treat *.export.libs set on the liba/libs{}
+          // members as *.libs overrides rather than as member-specific
+          // interface dependencies. This difference in semantics proved to be
+          // surprising so now we have separate *.export.impl_libs for that.
+          // Note that in this case options come from *.export.* variables.
           //
-          if (cc)
-            proc_opt (l, *t, true, true);
-          else
+          // Note also that we only check for *.*libs. If one doesn't have any
+          // libraries but needs to set, say, *.loptions, then *.*libs should
+          // be set to NULL or empty (this is why we check for the result
+          // being defined).
+          //
+          c_e_libs = l[impl ? c_export_impl_libs : c_export_libs];
+
+          if (!cc)
+            x_e_libs = l[same
+                         ? (impl ? x_export_impl_libs : x_export_libs)
+                         : vp[*t + (impl ? ".export.impl_libs" : ".export.libs")]];
+
+          // Process options first.
+          //
+          if (proc_opt)
           {
-            if (impl)
+            // If all we know is it's a C-common library, then in both cases
+            // we only look for cc.export.*.
+            //
+            if (cc)
             {
-              // Interface and implementation: as discussed above, we can have
-              // two situations: overriden export or default export.
-              //
-              if (c_e_libs.defined () || x_e_libs.defined ())
+              if (!proc_opt (l, *t, true, true)) break;
+            }
+            else
+            {
+              if (impl)
               {
-                // NOTE: should this not be from l.vars rather than l? Or
-                // perhaps we can assume non-common values will be set on
-                // libs{}/liba{}.
-                //
-                // Note: options come from *.export.* variables.
+                // Interface and implementation: as discussed above, we can
+                // have two situations: overriden export or default export.
                 //
-                proc_opt (l, *t, false, true);
-                proc_opt (l, *t, true, true);
+                if (c_e_libs.defined () || x_e_libs.defined ())
+                {
+                  // NOTE: should this not be from l.vars rather than l? Or
+                  // perhaps we can assume non-common values will be set on
+                  // libs{}/liba{}.
+                  //
+                  // Note: options come from *.export.* variables.
+                  //
+                  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;
+                }
               }
               else
               {
-                // For default export we use the same options as were used to
-                // build the library.
+                // Interface: only add *.export.* (interface dependencies).
                 //
-                proc_opt (l, *t, false, false);
-                proc_opt (l, *t, true, false);
+                if (!proc_opt (l, *t, false, true) ||
+                    !proc_opt (l, *t, true,  true)) break;
               }
             }
-            else
-            {
-              // Interface: only add *.export.* (interface dependencies).
-              //
-              proc_opt (l, *t, false, true);
-              proc_opt (l, *t, true, true);
-            }
           }
         }
-      }
-
-      // Determine if an absolute path is to a system library. Note that
-      // we assume both paths to be normalized.
-      //
-      auto sys = [] (const dir_paths& sysd, const string& p) -> bool
-      {
-        size_t pn (p.size ());
-
-        for (const dir_path& d: sysd)
-        {
-          const string& ds (d.string ()); // Can be "/", otherwise no slash.
-          size_t dn (ds.size ());
-
-          if (pn > dn &&
-              p.compare (0, dn, ds) == 0 &&
-              (path::traits_type::is_separator (ds[dn - 1]) ||
-               path::traits_type::is_separator (p[dn])))
-            return true;
-        }
-
-        return false;
-      };
-
-      // Next process the library itself if requested.
-      //
-      small_vector<reference_wrapper<const string>, 2> proc_lib_name; // Reuse.
-
-      if (self && proc_lib)
-      {
-        chain->push_back (&l);
 
-        // Note that while normally the path is assigned, in case of an import
-        // stub the path to the DLL may not be known and so the path will be
-        // empty (but proc_lib() will use the import stub).
+        // Determine if an absolute path is to a system library. Note that
+        // we assume both paths to be normalized.
         //
-        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).
-                ? cast_false<bool> (l.vars[c_system])
-                : !p.empty () && sys (top_sysd, p.string ()));
+        auto sys = [] (const dir_paths& sysd, const string& p) -> bool
+        {
+          size_t pn (p.size ());
 
-        proc_lib_name = {p.string ()};
-        proc_lib (&chain->back (), proc_lib_name, lf, s);
-      }
+          for (const dir_path& d: sysd)
+          {
+            const string& ds (d.string ()); // Can be "/", otherwise no slash.
+            size_t dn (ds.size ());
+
+            if (pn > dn &&
+                p.compare (0, dn, ds) == 0 &&
+                (path::traits_type::is_separator (ds[dn - 1]) ||
+                 path::traits_type::is_separator (p[dn])))
+              return true;
+          }
 
-      const scope& bs (t == nullptr || cc ? top_bs : l.base_scope ());
-      optional<optional<linfo>> li;              // Calculate lazily.
-      const dir_paths* sysd (nullptr);           // Resolve lazily.
+          return false;
+        };
 
-      // Find system search directories corresponding to this library, i.e.,
-      // from its project and for its type (C, C++, etc).
-      //
-      auto find_sysd = [&top_sysd, t, cc, same, &bs, &sysd, this] ()
-      {
-        // Use the search dirs corresponding to this library scope/type.
+        // Next process the library itself if requested.
         //
-        sysd = (t == nullptr || 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"]]);
-      };
-
-      auto find_linfo = [top_li, t, cc, &bs, &l, &li] ()
-      {
-        li = (t == nullptr || cc)
-        ? top_li
-        : optional<linfo> (link_info (bs, link_type (l).type));
-      };
+        small_vector<reference_wrapper<const string>, 2> proc_lib_name;//Reuse.
 
-      // Only go into prerequisites (implementation) if instructed and we are
-      // not using explicit export. Otherwise, interface dependencies come
-      // from the lib{}:*.export.impl_libs below.
-      //
-      if (impl && !c_e_libs.defined () && !x_e_libs.defined ())
-      {
-        assert (top_li); // Must pick a member if implementation (see above).
-
-        for (const prerequisite_target& pt: l.prerequisite_targets[a])
+        if (self && proc_lib)
         {
-          // Note: adhoc prerequisites are not part of the library metadata
-          // protocol (and we should check for adhoc first to avoid races).
+          // Note that while normally the path is assigned, in case of an
+          // import stub the path to the DLL may not be known and so the path
+          // will be empty (but proc_lib() will use the import stub).
           //
-          if (pt.adhoc || pt == nullptr)
-            continue;
-
-          bool la;
           const file* f;
+          const path& p ((f = l.is_a<file> ()) ? f->path () : empty_path);
 
-          if ((la = (f = pt->is_a<liba>  ())) ||
-              (la = (f = pt->is_a<libux> ())) ||
-              (      f = pt->is_a<libs>  ()))
-          {
-            if (sysd == nullptr) find_sysd ();
-            if (!li) find_linfo ();
+          bool s (t != nullptr // If cc library (matched or imported).
+                  ? cast_false<bool> (l.vars[c_system])
+                  : !p.empty () && sys (top_sysd, p.string ()));
 
-            process_libraries (a, bs, *li, *sysd,
-                               *f, la, pt.data,
-                               proc_impl, proc_lib, proc_opt, true,
-                               cache, chain);
-          }
+          proc_lib_name = {p.string ()};
+          if (!proc_lib (&chain->back (), proc_lib_name, lf, s))
+            break;
         }
-      }
 
-      // Process libraries (recursively) from *.export.*libs (of type names)
-      // handling import, etc.
-      //
-      // If it is not a C-common library, then it probably doesn't have any of
-      // the *.libs.
-      //
-      if (t != nullptr)
-      {
-        optional<dir_paths> usrd; // Extract lazily.
+        const scope& bs (t == nullptr || cc ? top_bs : l.base_scope ());
+        optional<optional<linfo>> li;    // Calculate lazily.
+        const dir_paths* sysd (nullptr); // Resolve lazily.
+
+        // Find system search directories corresponding to this library, i.e.,
+        // from its project and for its type (C, C++, etc).
+        //
+        auto find_sysd = [&top_sysd, t, cc, same, &bs, &sysd, this] ()
+        {
+          // Use the search dirs corresponding to this library scope/type.
+          //
+          sysd = (t == nullptr || 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"]]);
+        };
 
-        // Determine if a "simple path" is a system library.
+        auto find_linfo = [top_li, t, cc, &bs, &l, &li] ()
+        {
+          li = (t == nullptr || cc)
+          ? top_li
+          : optional<linfo> (link_info (bs, link_type (l).type));
+        };
+
+        // Only go into prerequisites (implementation) if instructed and we
+        // are not using explicit export. Otherwise, interface dependencies
+        // come from the lib{}:*.export.impl_libs below.
         //
-        auto sys_simple = [&sysd, &sys, &find_sysd] (const string& p) -> bool
+        if (impl && !c_e_libs.defined () && !x_e_libs.defined ())
         {
-          bool s (!path::traits_type::absolute (p));
+          assert (top_li); // Must pick a member if implementation (see above).
 
-          if (!s)
+          for (const prerequisite_target& pt: l.prerequisite_targets[a])
           {
-            if (sysd == nullptr) find_sysd ();
+            // Note: adhoc prerequisites are not part of the library metadata
+            // protocol (and we should check for adhoc first to avoid races).
+            //
+            if (pt.adhoc || pt == nullptr)
+              continue;
 
-            s = sys (*sysd, p);
-          }
+            bool la;
+            const file* f;
 
-          return s;
-        };
+            if ((la = (f = pt->is_a<liba>  ())) ||
+                (la = (f = pt->is_a<libux> ())) ||
+                (      f = pt->is_a<libs>  ()))
+            {
+              if (sysd == nullptr) find_sysd ();
+              if (!li) find_linfo ();
 
-        // Determine the length of the library name fragment as well as
-        // whether it is a system library. Possible length values are:
-        //
-        // 1 - just the argument itself (-lpthread)
-        // 2 - argument and next element (-l pthread, -framework CoreServices)
-        // 0 - unrecognized/until the end (-Wl,--whole-archive ...)
+              process_libraries (a, bs, *li, *sysd,
+                                 *f, la, pt.data,
+                                 proc_impl, proc_lib, proc_opt, true,
+                                 cache, chain);
+            }
+          }
+        }
+
+        // Process libraries (recursively) from *.export.*libs (of type names)
+        // handling import, etc.
         //
-        // See similar code in find_system_library().
+        // If it is not a C-common library, then it probably doesn't have any
+        // of the *.libs.
         //
-        auto sense_fragment = [&sys_simple, this] (const string& l) ->
-          pair<size_t, bool>
+        if (t != nullptr)
         {
-          size_t n;
-          bool s (true);
+          optional<dir_paths> usrd; // Extract lazily.
 
-          if (tsys == "win32-msvc")
+          // Determine if a "simple path" is a system library.
+          //
+          auto sys_simple = [&sysd, &sys, &find_sysd] (const string& p) -> bool
           {
-            if (l[0] == '/')
-            {
-              // Some other option (e.g., /WHOLEARCHIVE:<name>).
-              //
-              n = 0;
-            }
-            else
+            bool s (!path::traits_type::absolute (p));
+
+            if (!s)
             {
-              // Presumably a path.
-              //
-              n = 1;
-              s = sys_simple (l);
+              if (sysd == nullptr) find_sysd ();
+              s = sys (*sysd, p);
             }
-          }
-          else
+
+            return s;
+          };
+
+          // Determine the length of the library name fragment as well as
+          // whether it is a system library. Possible length values are:
+          //
+          // 1 - just the argument itself (-lpthread)
+          // 2 - argument and next element (-l pthread, -framework CoreServices)
+          // 0 - unrecognized/until the end (-Wl,--whole-archive ...)
+          //
+          // See similar code in find_system_library().
+          //
+          auto sense_fragment = [&sys_simple, this] (const string& l) ->
+            pair<size_t, bool>
           {
-            if (l[0] == '-')
+            size_t n;
+            bool s (true);
+
+            if (tsys == "win32-msvc")
             {
-              // -l<name>, -l <name>
-              //
-              if (l[1] == 'l')
+              if (l[0] == '/')
               {
-                n = l.size () == 2 ? 2 : 1;
+                // Some other option (e.g., /WHOLEARCHIVE:<name>).
+                //
+                n = 0;
               }
-              // -framework <name> (Mac OS)
-              //
-              else if (tsys == "darwin" && l == "-framework")
+              else
               {
-                n = 2;
+                // Presumably a path.
+                //
+                n = 1;
+                s = sys_simple (l);
               }
-              // Some other option (e.g., -Wl,--whole-archive).
-              //
-              else
-                n = 0;
             }
             else
             {
-              // Presumably a path.
-              //
-              n = 1;
-              s = sys_simple (l);
+              if (l[0] == '-')
+              {
+                // -l<name>, -l <name>
+                //
+                if (l[1] == 'l')
+                {
+                  n = l.size () == 2 ? 2 : 1;
+                }
+                // -framework <name> (Mac OS)
+                //
+                else if (tsys == "darwin" && l == "-framework")
+                {
+                  n = 2;
+                }
+                // Some other option (e.g., -Wl,--whole-archive).
+                //
+                else
+                  n = 0;
+              }
+              else
+              {
+                // Presumably a path.
+                //
+                n = 1;
+                s = sys_simple (l);
+              }
             }
-          }
 
-          return make_pair (n, s);
-        };
+            return make_pair (n, s);
+          };
 
-        auto proc_int = [&l, cache, chain,
-                         &proc_impl, &proc_lib, &proc_lib_name, &proc_opt,
-                         &sysd, &usrd,
-                         &find_sysd, &find_linfo, &sense_fragment,
-                         &bs, a, &li, impl, this] (const lookup& lu)
-        {
-          const vector<name>* ns (cast_null<vector<name>> (lu));
-          if (ns == nullptr || ns->empty ())
-            return;
-
-          for (auto i (ns->begin ()), e (ns->end ()); i != e; )
+          auto proc_int = [&l, cache, chain,
+                           &proc_impl, &proc_lib, &proc_lib_name, &proc_opt,
+                           &sysd, &usrd,
+                           &find_sysd, &find_linfo, &sense_fragment,
+                           &bs, a, &li, impl, this] (const lookup& lu)
           {
-            const name& n (*i);
+            const vector<name>* ns (cast_null<vector<name>> (lu));
+            if (ns == nullptr || ns->empty ())
+              return;
 
-            if (n.simple ())
+            for (auto i (ns->begin ()), e (ns->end ()); i != e; )
             {
-              // This is something like -lpthread or shell32.lib so should be
-              // a valid path. But it can also be an absolute library path
-              // (e.g., something that may come from our .{static/shared}.pc
-              // files).
-              //
-              if (proc_lib)
-              {
-                pair<size_t, bool> r (sense_fragment (n.value));
+              const name& n (*i);
 
-                proc_lib_name.clear ();
-                for (auto e1 (r.first != 0 ? i + r.first : e);
-                     i != e && i != e1 && i->simple ();
-                     ++i)
+              if (n.simple ())
+              {
+                // This is something like -lpthread or shell32.lib so should
+                // be a valid path. But it can also be an absolute library
+                // path (e.g., something that may come from our
+                // .{static/shared}.pc files).
+                //
+                if (proc_lib)
                 {
-                  proc_lib_name.push_back (i->value);
+                  pair<size_t, bool> r (sense_fragment (n.value));
+
+                  proc_lib_name.clear ();
+                  for (auto e1 (r.first != 0 ? i + r.first : e);
+                       i != e && i != e1 && i->simple ();
+                       ++i)
+                  {
+                    proc_lib_name.push_back (i->value);
+                  }
+
+                  proc_lib (nullptr, proc_lib_name, 0, r.second);
+                  continue;
                 }
-
-                proc_lib (nullptr, proc_lib_name, 0, r.second);
-                continue;
               }
-            }
-            else
-            {
-              // This is a potentially project-qualified target.
-              //
-              if (sysd == nullptr) find_sysd ();
-              if (!li) find_linfo ();
-
-              const mtime_target& t (
-                resolve_library (a,
-                                 bs,
-                                 n,
-                                 (n.pair ? (++i)->dir : dir_path ()),
-                                 *li,
-                                 *sysd, usrd,
-                                 cache));
-
-              if (proc_lib)
+              else
               {
-                // This can happen if the target is mentioned in *.export.libs
-                // (i.e., it is an interface dependency) but not in the
-                // library's prerequisites (i.e., it is not an implementation
-                // dependency).
+                // This is a potentially project-qualified target.
                 //
-                // Note that we used to just check for path being assigned but
-                // on Windows import-installed DLLs may legally have empty
-                // paths.
-                //
-                const char* w (nullptr);
-                if (t.ctx.phase == run_phase::match)
+                if (sysd == nullptr) find_sysd ();
+                if (!li) find_linfo ();
+
+                const mtime_target& t (
+                  resolve_library (a,
+                                   bs,
+                                   n,
+                                   (n.pair ? (++i)->dir : dir_path ()),
+                                   *li,
+                                   *sysd, usrd,
+                                   cache));
+
+                if (proc_lib)
                 {
-                  size_t o (t.state[a].task_count.load (memory_order_consume) -
-                            t.ctx.count_base ());
-
-                  if (o != target::offset_applied &&
-                      o != target::offset_executed)
-                    w = "not matched";
+                  // This can happen if the target is mentioned in
+                  // *.export.libs (i.e., it is an interface dependency) but
+                  // not in the library's prerequisites (i.e., it is not an
+                  // implementation dependency).
+                  //
+                  // Note that we used to just check for path being assigned
+                  // but on Windows import-installed DLLs may legally have
+                  // empty paths.
+                  //
+                  const char* w (nullptr);
+                  if (t.ctx.phase == run_phase::match)
+                  {
+                    size_t o (
+                      t.state[a].task_count.load (memory_order_consume) -
+                      t.ctx.count_base ());
+
+                    if (o != target::offset_applied &&
+                        o != target::offset_executed)
+                      w = "not matched";
+                  }
+                  else if (t.mtime () == timestamp_unknown)
+                    w = "out of date";
+
+                  if (w != nullptr)
+                    fail   << (impl ? "implementation" : "interface")
+                           << " dependency " << t << " is " << w <<
+                      info << "mentioned in *.export." << (impl ? "impl_" : "")
+                           << "libs of target " << l <<
+                      info << "is it a prerequisite of " << l << "?";
                 }
-                else if (t.mtime () == timestamp_unknown)
-                  w = "out of date";
-
-                if (w != nullptr)
-                  fail   << (impl ? "implementation" : "interface")
-                         << " dependency " << t << " is " << w <<
-                    info << "mentioned in *.export." << (impl ? "impl_" : "")
-                         << "libs of target " << l <<
-                    info << "is it a prerequisite of " << l << "?";
+
+                // Process it recursively.
+                //
+                // @@ Where can we get the link flags? Should we try to find
+                //    them in the library's prerequisites? What about
+                //    installed stuff?
+                //
+                process_libraries (a, bs, *li, *sysd,
+                                   t, t.is_a<liba> () || t.is_a<libux> (), 0,
+                                   proc_impl, proc_lib, proc_opt, true,
+                                   cache, chain);
               }
 
-              // Process it recursively.
-              //
-              // @@ Where can we get the link flags? Should we try to find
-              //    them in the library's prerequisites? What about installed
-              //    stuff?
-              //
-              process_libraries (a, bs, *li, *sysd,
-                                 t, t.is_a<liba> () || t.is_a<libux> (), 0,
-                                 proc_impl, proc_lib, proc_opt, true,
-                                 cache, chain);
+              ++i;
             }
+          };
 
-            ++i;
-          }
-        };
-
-        // Process libraries from *.libs (of type strings).
-        //
-        auto proc_imp = [&proc_lib, &proc_lib_name,
-                         &sense_fragment] (const lookup& lu)
-        {
-          const strings* ns (cast_null<strings> (lu));
-          if (ns == nullptr || ns->empty ())
-            return;
-
-          for (auto i (ns->begin ()), e (ns->end ()); i != e; )
+          // Process libraries from *.libs (of type strings).
+          //
+          auto proc_imp = [&proc_lib, &proc_lib_name,
+                           &sense_fragment] (const lookup& lu)
           {
-            // This is something like -lpthread or shell32.lib so should be a
-            // valid path.
-            //
-            pair<size_t, bool> r (sense_fragment (*i));
+            const strings* ns (cast_null<strings> (lu));
+            if (ns == nullptr || ns->empty ())
+              return;
 
-            proc_lib_name.clear ();
-            for (auto e1 (r.first != 0 ? i + r.first : e);
-                 i != e && i != e1;
-                 ++i)
+            for (auto i (ns->begin ()), e (ns->end ()); i != e; )
             {
-              proc_lib_name.push_back (*i);
+              // This is something like -lpthread or shell32.lib so should be
+              // a valid path.
+              //
+              pair<size_t, bool> r (sense_fragment (*i));
+
+              proc_lib_name.clear ();
+              for (auto e1 (r.first != 0 ? i + r.first : e);
+                   i != e && i != e1;
+                   ++i)
+              {
+                proc_lib_name.push_back (*i);
+              }
+
+              proc_lib (nullptr, proc_lib_name, 0, r.second);
             }
+          };
 
-            proc_lib (nullptr, proc_lib_name, 0, r.second);
+          // Note: the same structure as when processing options above.
+          //
+          // If all we know is it's a C-common library, then in both cases we
+          // only look for cc.export.*libs.
+          //
+          if (cc)
+          {
+            if (c_e_libs) proc_int (c_e_libs);
           }
-        };
-
-        // Note: the same structure as when processing options above.
-        //
-        // If all we know is it's a C-common library, then in both cases we
-        // only look for cc.export.*libs.
-        //
-        if (cc)
-        {
-          if (c_e_libs) proc_int (c_e_libs);
-        }
-        else
-        {
-          if (impl)
+          else
           {
-            // Interface and implementation: as discussed above, we can have
-            // two situations: overriden export or default export.
-            //
-            if (c_e_libs.defined () || x_e_libs.defined ())
+            if (impl)
             {
-              if (c_e_libs) proc_int (c_e_libs);
-              if (x_e_libs) proc_int (x_e_libs);
+              // Interface and implementation: as discussed above, we can have
+              // two situations: overriden export or default export.
+              //
+              if (c_e_libs.defined () || x_e_libs.defined ())
+              {
+                if (c_e_libs) proc_int (c_e_libs);
+                if (x_e_libs) proc_int (x_e_libs);
+              }
+              else
+              {
+                // For default export we use the same options/libs as were
+                // used to build the library. Since libraries in (non-export)
+                // *.libs are not targets, we don't need to recurse.
+                //
+                if (proc_lib)
+                {
+                  proc_imp (l[c_libs]);
+                  proc_imp (l[same ? x_libs : vp[*t + ".libs"]]);
+                }
+              }
             }
             else
             {
-              // For default export we use the same options/libs as were used
-              // to build the library. Since libraries in (non-export) *.libs
-              // are not targets, we don't need to recurse.
+              // Interface: only add *.export.* (interface dependencies).
               //
-              if (proc_lib)
-              {
-                proc_imp (l[c_libs]);
-                proc_imp (l[same ? x_libs : vp[*t + ".libs"]]);
-              }
+              if (c_e_libs) proc_int (c_e_libs);
+              if (x_e_libs) proc_int (x_e_libs);
             }
           }
-          else
-          {
-            // Interface: only add *.export.* (interface dependencies).
-            //
-            if (c_e_libs) proc_int (c_e_libs);
-            if (x_e_libs) proc_int (x_e_libs);
-          }
         }
-      }
+      } while (false); // Breakout loop end.
 
       // Remove this library from the chain.
       //
diff --git a/libbuild2/cc/common.hxx b/libbuild2/cc/common.hxx
index a62b91b..f15bf23 100644
--- a/libbuild2/cc/common.hxx
+++ b/libbuild2/cc/common.hxx
@@ -292,10 +292,10 @@ namespace build2
         bool,
         lflags,
         const function<bool (const target&, bool)>&,
-        const function<void (const target* const*,
+        const function<bool (const target* const*,
                              const small_vector<reference_wrapper<const string>, 2>&,
                              lflags, bool)>&,
-        const function<void (const target&, const string&, bool, bool)>&,
+        const function<bool (const target&, const string&, bool, bool)>&,
         bool = false,
         library_cache* = nullptr,
         small_vector<const target*, 16>* = nullptr) const;
diff --git a/libbuild2/cc/compile-rule.cxx b/libbuild2/cc/compile-rule.cxx
index 0f4ece3..b2fdba9 100644
--- a/libbuild2/cc/compile-rule.cxx
+++ b/libbuild2/cc/compile-rule.cxx
@@ -418,7 +418,8 @@ namespace build2
     void compile_rule::
     append_library_options (appended_libraries& ls, T& args,
                             const scope& bs,
-                            action a, const file& l, bool la, linfo li) const
+                            action a, const file& l, bool la, linfo li,
+                            library_cache* lib_cache) const
     {
       struct data
       {
@@ -439,16 +440,16 @@ namespace build2
         // even if set on liba{}/libs{}, unlike loptions.
         //
         if (!exp) // Ignore libux.
-          return;
+          return true;
 
         // Suppress duplicates.
         //
         // Compilation is the simple case: we can add the options on the first
-        // occurrence of the library and ignore all subsequent occurrences.
-        // See GitHub issue #114 for details.
+        // occurrence of the library and ignore (and prune) all subsequent
+        // occurrences. See GitHub issue #114 for details.
         //
         if (find (d.ls.begin (), d.ls.end (), &l) != d.ls.end ())
-          return;
+          return false;
 
         const variable& var (
           com
@@ -464,11 +465,13 @@ namespace build2
         //
         if (com)
           d.ls.push_back (&l);
+
+        return true;
       };
 
       process_libraries (a, bs, li, sys_lib_dirs,
                          l, la, 0, // lflags unused.
-                         imp, nullptr, opt);
+                         imp, nullptr, opt, false /* self */, lib_cache);
     }
 
     void compile_rule::
@@ -476,7 +479,7 @@ namespace build2
                             const scope& bs,
                             action a, const file& l, bool la, linfo li) const
     {
-      append_library_options<strings> (ls, args, bs, a, l, la, li);
+      append_library_options<strings> (ls, args, bs, a, l, la, li, nullptr);
     }
 
     template <typename T>
@@ -486,6 +489,7 @@ namespace build2
                             action a, const target& t, linfo li) const
     {
       appended_libraries ls;
+      library_cache lc;
 
       for (prerequisite_member p: group_prerequisite_members (a, t))
       {
@@ -505,7 +509,7 @@ namespace build2
               (la = (f = pt->is_a<libux> ())) ||
               (     (f = pt->is_a<libs> ())))
           {
-            append_library_options (ls, args, bs, a, *f, la, li);
+            append_library_options (ls, args, bs, a, *f, la, li, &lc);
           }
         }
       }
@@ -521,13 +525,16 @@ namespace build2
                              target& t,
                              linfo li) const
     {
+      //@@ TODO: implement duplicate suppression and prunning. Reuse above
+      //         machinery.
+
       auto imp = [] (const target& l, bool la) {return la && l.is_a<libux> ();};
 
       auto opt = [&m, this] (
         const target& l, const string& t, bool com, bool exp)
       {
         if (!exp)
-          return;
+          return true;
 
         const variable& var (
           com
@@ -537,13 +544,15 @@ namespace build2
              : l.ctx.var_pool[t + ".export.poptions"]));
 
         append_prefixes (m, l, var);
+        return true;
       };
 
       // The same logic as in append_library_options().
       //
       const function<bool (const target&, bool)> impf (imp);
-      const function<void (const target&, const string&, bool, bool)> optf (opt);
+      const function<bool (const target&, const string&, bool, bool)> optf (opt);
 
+      library_cache lib_cache;
       for (prerequisite_member p: group_prerequisite_members (a, t))
       {
         if (include (a, t, p) != include_type::normal) // Excluded/ad hoc.
@@ -562,7 +571,8 @@ namespace build2
 
           process_libraries (a, bs, li, sys_lib_dirs,
                              pt->as<file> (), la, 0, // lflags unused.
-                             impf, nullptr, optf);
+                             impf, nullptr, optf, false /* self */,
+                             &lib_cache);
         }
       }
     }
@@ -6212,6 +6222,9 @@ namespace build2
         //
         auto imp = [] (const target&, bool) { return false; };
 
+        //@@ TODO: implement duplicate suppression and prunning? Reuse
+        //         above machinery.
+
         // The same logic as in append_libraries().
         //
         struct data
@@ -6227,21 +6240,21 @@ namespace build2
           lflags,
           bool)
         {
-          // It's unfortunate we have no way to bail out.
+          // Prune any further traversal if we already found it.
           //
           if (d.lt != nullptr)
-            return;
+            return false;
 
           const target* l (lc != nullptr ? *lc : nullptr); // Can be lib{}.
 
           if (l == nullptr)
-            return;
+            return true;
 
           // Feels like we should only consider non-utility libraries with
           // utilities being treated as "direct" use.
           //
           if (l->is_a<libux> ())
-            return;
+            return true;
 
           // Since the library is searched and matched, all the headers should
           // be in prerequisite_targets.
@@ -6249,8 +6262,11 @@ namespace build2
           const auto& pts (l->prerequisite_targets[d.a]);
           if (find (pts.begin (), pts.end (), &d.ht) != pts.end ())
             d.lt = l;
+
+          return d.lt == nullptr;
         };
 
+        library_cache lib_cache;
         for (prerequisite_member p: group_prerequisite_members (a, t))
         {
           if (include (a, t, p) != include_type::normal) // Excluded/ad hoc.
@@ -6277,10 +6293,13 @@ namespace build2
               // which won't pick the liba/libs{} member (naturally) but will
               // just match the lib{} group.
               //
-              process_libraries (
-                a, bs, nullopt, sys_lib_dirs,
-                *f, la, 0, // lflags unused.
-                imp, lib, nullptr, true /* self */);
+              process_libraries (a, bs, nullopt, sys_lib_dirs,
+                                 *f, la, 0, // lflags unused.
+                                 imp, lib, nullptr, true /* self */,
+                                 &lib_cache);
+
+              if (lt != nullptr)
+                break;
             }
           }
         }
diff --git a/libbuild2/cc/compile-rule.hxx b/libbuild2/cc/compile-rule.hxx
index e4347f8..d085c8e 100644
--- a/libbuild2/cc/compile-rule.hxx
+++ b/libbuild2/cc/compile-rule.hxx
@@ -80,7 +80,8 @@ namespace build2
       void
       append_library_options (appended_libraries&, T&,
                               const scope&,
-                              action, const file&, bool, linfo) const;
+                              action, const file&, bool, linfo,
+                              library_cache*) const;
 
       template <typename T>
       void
diff --git a/libbuild2/cc/link-rule.cxx b/libbuild2/cc/link-rule.cxx
index 98b6b9e..6e378e9 100644
--- a/libbuild2/cc/link-rule.cxx
+++ b/libbuild2/cc/link-rule.cxx
@@ -1665,7 +1665,8 @@ namespace build2
     append_libraries (appended_libraries& ls, strings& args,
                       const scope& bs, action a,
                       const file& l, bool la, lflags lf, linfo li,
-                      bool self, bool rel) const
+                      bool self, bool rel,
+                      library_cache* lib_cache) const
     {
       struct data
       {
@@ -1719,7 +1720,8 @@ namespace build2
           // Hoist the elements corresponding to this library to the end.
           //
           d.ls.hoist (d.args, *al);
-          return;
+          return true; // @@ Can we prune here???. But also sha256 version?
+                       // Also in pkgconfig.cxx!
         }
 
         if (l == nullptr)
@@ -1847,6 +1849,8 @@ namespace build2
       done:
         if (al != nullptr)
           al->end = d.args.size (); // Close.
+
+        return true;
       };
 
       auto opt = [&d, this] (const target& lt,
@@ -1867,12 +1871,12 @@ namespace build2
         // the exp checks below.
         //
         if (d.li.type == otype::a || !exp)
-          return;
+          return true;
 
         // Suppress duplicates.
         //
         if (d.ls.append (l, d.args.size ()).end != appended_library::npos)
-          return;
+          return true;
 
         // If we need an interface value, then use the group (lib{}).
         //
@@ -1887,16 +1891,21 @@ namespace build2
 
           append_options (d.args, *g, var);
         }
+
+        return true;
       };
 
-      process_libraries (
-        a, bs, li, sys_lib_dirs, l, la, lf, imp, lib, opt, self);
+      process_libraries (a, bs, li, sys_lib_dirs,
+                         l, la,
+                         lf, imp, lib, opt, self,
+                         lib_cache);
     }
 
     void link_rule::
     append_libraries (sha256& cs, bool& update, timestamp mt,
                       const scope& bs, action a,
-                      const file& l, bool la, lflags lf, linfo li) const
+                      const file& l, bool la, lflags lf, linfo li,
+                      library_cache* lib_cache) const
     {
       // Note that we don't do any duplicate suppression here: there is no way
       // to "hoist" things once they are hashed and hashing only the first
@@ -1941,7 +1950,7 @@ namespace build2
           {
             for (ptrdiff_t i (-1); lc[i] != nullptr; --i)
               if (!lc[i]->is_a<libux> ())
-                return;
+                return true;
           }
 
           // We also don't need to do anything special for linking a utility
@@ -1954,10 +1963,10 @@ namespace build2
           // append_libraries().
           //
           if (d.li.type == otype::a && !lu)
-            return;
+            return true;
 
           if (l->mtime () == timestamp_unreal) // Binless.
-            return;
+            return true;
 
           // Check if this library renders us out of date.
           //
@@ -1976,6 +1985,8 @@ namespace build2
           d.cs.append (f);
           hash_path (d.cs, l->path (), d.out_root);
         }
+
+        return true;
       };
 
       auto opt = [&d, this] (const target& l,
@@ -1984,7 +1995,7 @@ namespace build2
                              bool exp)
       {
         if (d.li.type == otype::a || !exp)
-          return;
+          return true;
 
         if (const target* g = exp && l.is_a<libs> () ? l.group : &l)
         {
@@ -1997,17 +2008,22 @@ namespace build2
 
           append_options (d.cs, *g, var);
         }
+
+        return true;
       };
 
-      process_libraries (
-        a, bs, li, sys_lib_dirs, l, la, lf, imp, lib, opt, true);
+      process_libraries (a, bs, li, sys_lib_dirs,
+                         l, la,
+                         lf, imp, lib, opt, true /* self */,
+                         lib_cache);
     }
 
     void link_rule::
     rpath_libraries (rpathed_libraries& ls, strings& args,
                      const scope& bs,
                      action a, const file& l, bool la,
-                     linfo li, bool link, bool self) const
+                     linfo li, bool link, bool self,
+                     library_cache* lib_cache) const
     {
       // Use -rpath-link only on targets that support it (Linux, *BSD). Note
       // that we don't really need it for top-level libraries.
@@ -2058,8 +2074,11 @@ namespace build2
         // We don't rpath system libraries. Why, you may ask? There are many
         // good reasons and I have them written on a napkin somewhere...
         //
+        // We also assume system libraries can only depend on other system
+        // libraries and so can prune the traversal.
+        //
         if (sys)
-          return;
+          return false;
 
         auto append = [&d] (const string& f)
         {
@@ -2075,21 +2094,22 @@ namespace build2
         if (l != nullptr)
         {
           if (!l->is_a<libs> ())
-            return;
+            return true;
 
           if (l->mtime () == timestamp_unreal) // Binless.
-            return;
+            return true;
 
           // Suppress duplicates.
           //
           // We handle rpath similar to the compilation case by adding the
-          // options on the first occurrence and ignoring all the subsequent.
+          // options on the first occurrence and ignoring (and pruning) all
+          // the subsequent.
           //
-          if (find (d.ls.begin (), d.ls.end (), l) == d.ls.end ())
-          {
-            append (ns[0]);
-            d.ls.push_back (l);
-          }
+          if (find (d.ls.begin (), d.ls.end (), l) != d.ls.end ())
+            return false;
+
+          append (ns[0]);
+          d.ls.push_back (l);
         }
         else
         {
@@ -2103,7 +2123,7 @@ namespace build2
             size_t p (path::traits_type::find_extension (f));
 
             if (p == string::npos)
-              return;
+              break;
 
             ++p; // Skip dot.
 
@@ -2120,8 +2140,9 @@ namespace build2
               append (f);
           }
         }
-      };
 
+        return true;
+      };
 
       if (self && !link && !la)
       {
@@ -2141,7 +2162,7 @@ namespace build2
 
       process_libraries (a, bs, li, sys_lib_dirs,
                          l, la, 0 /* lflags */,
-                         imp, lib, nullptr);
+                         imp, lib, nullptr, false /* self */, lib_cache);
     }
 
     void link_rule::
@@ -2150,6 +2171,7 @@ namespace build2
                      const target& t, linfo li, bool link) const
     {
       rpathed_libraries ls;
+      library_cache lc;
 
       for (const prerequisite_target& pt: t.prerequisite_targets[a])
       {
@@ -2163,7 +2185,7 @@ namespace build2
             (la = (f = pt->is_a<libux> ())) ||
             (      f = pt->is_a<libs>  ()))
         {
-          rpath_libraries (ls, args, bs, a, *f, la, li, link, true);
+          rpath_libraries (ls, args, bs, a, *f, la, li, link, true, &lc);
         }
       }
     }
@@ -2835,6 +2857,7 @@ namespace build2
       const file* def (nullptr); // Cached if present.
       {
         sha256 cs;
+        library_cache lc;
 
         for (const prerequisite_target& p: t.prerequisite_targets[a])
         {
@@ -2882,7 +2905,7 @@ namespace build2
             //
             if (la || ls)
             {
-              append_libraries (cs, update, mt, bs, a, *f, la, p.data, li);
+              append_libraries (cs, update, mt, bs, a, *f, la, p.data, li, &lc);
               f = nullptr; // Timestamp checked by hash_libraries().
             }
             else
@@ -3181,6 +3204,8 @@ namespace build2
       bool seen_obj (false);
       {
         appended_libraries als;
+        library_cache lc;
+
         for (const prerequisite_target& p: t.prerequisite_targets[a])
         {
           const target* pt (p.target);
@@ -3210,7 +3235,8 @@ namespace build2
                 (ls = (f = pt->is_a<libs>  ())))))
           {
             if (la || ls)
-              append_libraries (als, sargs, bs, a, *f, la, p.data, li);
+              append_libraries (
+                als, sargs, bs, a, *f, la, p.data, li, true, true, &lc);
             else
             {
               // Do not hoist libraries over object files since such object
diff --git a/libbuild2/cc/link-rule.hxx b/libbuild2/cc/link-rule.hxx
index f990415..fd12e89 100644
--- a/libbuild2/cc/link-rule.hxx
+++ b/libbuild2/cc/link-rule.hxx
@@ -174,19 +174,22 @@ namespace build2
       append_libraries (appended_libraries&, strings&,
                         const scope&, action,
                         const file&, bool, lflags, linfo,
-                        bool = true, bool = true) const;
+                        bool = true, bool = true,
+                        library_cache* = nullptr) const;
 
       void
       append_libraries (sha256&, bool&, timestamp,
                         const scope&, action,
-                        const file&, bool, lflags,  linfo) const;
+                        const file&, bool, lflags,  linfo,
+                        library_cache* = nullptr) const;
 
       using rpathed_libraries = small_vector<const file*, 256>;
 
       void
       rpath_libraries (rpathed_libraries&, strings&,
                        const scope&,
-                       action, const file&, bool, linfo, bool, bool) const;
+                       action, const file&, bool, linfo, bool, bool,
+                       library_cache* = nullptr) const;
 
       void
       rpath_libraries (strings&,
diff --git a/libbuild2/cc/pkgconfig.cxx b/libbuild2/cc/pkgconfig.cxx
index 7061491..c3a9028 100644
--- a/libbuild2/cc/pkgconfig.cxx
+++ b/libbuild2/cc/pkgconfig.cxx
@@ -1662,7 +1662,7 @@ namespace build2
             if (al != nullptr && al->end != appended_library::npos)
             {
               d.ls.hoist (d.args, *al);
-              return;
+              return true;
             }
 
             if (l != nullptr)
@@ -1680,6 +1680,8 @@ namespace build2
 
             if (al != nullptr)
               al->end = d.args.size (); // Close.
+
+            return true;
           };
 
           auto opt = [&d] (const target& lt, const string&, bool, bool)
@@ -1693,7 +1695,9 @@ namespace build2
             // See link_rule::append_libraries().
 
             if (d.ls.append (l, d.args.size ()).end != appended_library::npos)
-              return;
+              return true;
+
+            return true;
           };
 
           // Pretend we are linking an executable using what would be normal,
diff --git a/libbuild2/cc/windows-rpath.cxx b/libbuild2/cc/windows-rpath.cxx
index 7b572df..d4d2dc6 100644
--- a/libbuild2/cc/windows-rpath.cxx
+++ b/libbuild2/cc/windows-rpath.cxx
@@ -53,6 +53,9 @@ namespace build2
     {
       timestamp r (timestamp_nonexistent);
 
+      //@@ TODO: implement duplicate suppression and prunning. Reuse
+      //         rpath_libraries()'s machinery.
+
       // We need to collect all the DLLs, so go into implementation of both
       // shared and static (in case they depend on shared).
       //
@@ -69,9 +72,9 @@ namespace build2
         // We don't rpath system libraries.
         //
         if (sys)
-          return;
+          return false;
 
-        // Skip static libraries.
+        // Ignore static libraries.
         //
         if (l != nullptr)
         {
@@ -110,8 +113,11 @@ namespace build2
             }
           }
         }
+
+        return true;
       };
 
+      library_cache lib_cache;
       for (const prerequisite_target& pt: t.prerequisite_targets[a])
       {
         if (pt.adhoc || pt == nullptr)
@@ -125,7 +131,8 @@ namespace build2
             (     f = pt->is_a<libs>  ()))
           process_libraries (a, bs, li, sys_lib_dirs,
                              *f, la, pt.data,
-                             imp, lib, nullptr, true);
+                             imp, lib, nullptr, true /* self */,
+                             &lib_cache);
       }
 
       return r;
@@ -142,6 +149,8 @@ namespace build2
     {
       windows_dlls r;
 
+      //@@ TODO: implement duplicate suppression and prunning.
+
       auto imp = [] (const target&, bool) {return true;};
 
       auto lib = [&r, &bs] (
@@ -153,7 +162,7 @@ namespace build2
         const file* l (lc != nullptr ? &(*lc)->as<file> () : nullptr);
 
         if (sys)
-          return;
+          return false;
 
         if (l != nullptr)
         {
@@ -209,8 +218,11 @@ namespace build2
             }
           }
         }
+
+        return true;
       };
 
+      library_cache lib_cache;
       for (const prerequisite_target& pt: t.prerequisite_targets[a])
       {
         if (pt.adhoc || pt == nullptr)
@@ -224,7 +236,8 @@ namespace build2
             (      f = pt->is_a<libs>  ()))
           process_libraries (a, bs, li, sys_lib_dirs,
                              *f, la, pt.data,
-                             imp, lib, nullptr, true);
+                             imp, lib, nullptr, true /* self */,
+                             &lib_cache);
       }
 
       return r;