Add reverse_execute_prerequisites() variant

4 files changed, 154 insertions, 14 deletions

diff --git a/libbuild2/algorithm.cxx b/libbuild2/algorithm.cxx
index 64d4689..217e7af 100644
--- a/libbuild2/algorithm.cxx
+++ b/libbuild2/algorithm.cxx
@@ -2404,9 +2404,9 @@ namespace build2
                          const timestamp& mt, const execute_filter& ef,
                          size_t n)
   {
-    context& ctx (t.ctx);
+    assert (a == perform_update_id);
 
-    assert (ctx.current_mode == execution_mode::first);
+    context& ctx (t.ctx);
 
     size_t busy (ctx.count_busy ());
     size_t exec (ctx.count_executed ());
@@ -2441,7 +2441,7 @@ namespace build2
     wg.wait ();
 
     bool e (mt == timestamp_nonexistent);
-    const target* rt (tt != nullptr ? nullptr : &t);
+    const target* rt (nullptr);
 
     for (size_t i (0); i != n; ++i)
     {
@@ -2479,18 +2479,113 @@ namespace build2
 
       if (p.adhoc ())
         p.target = nullptr; // Blank out.
-      else
+      else if (tt != nullptr)
       {
         if (rt == nullptr && pt.is_a (*tt))
           rt = &pt;
       }
     }
 
-    assert (rt != nullptr);
+    assert (tt == nullptr || rt != nullptr);
+
+    return pair<optional<target_state>, const target*> (
+      e ? optional<target_state> () : rs, rt);
+  }
+
+  pair<optional<target_state>, const target*>
+  reverse_execute_prerequisites (const target_type* tt,
+                                 action a, const target& t,
+                                 const timestamp& mt, const execute_filter& ef,
+                                 size_t n)
+  {
+    assert (a == perform_update_id);
+
+    context& ctx (t.ctx);
+
+    size_t busy (ctx.count_busy ());
+    size_t exec (ctx.count_executed ());
+
+    auto& pts (t.prerequisite_targets[a]);
+
+    if (n == 0)
+      n = pts.size ();
+
+    // Pretty much as reverse_execute_members() but hairier.
+    //
+    target_state rs (target_state::unchanged);
+
+    wait_guard wg (ctx, busy, t[a].task_count);
+
+    for (size_t i (n); i != 0; )
+    {
+      const target*& pt (pts[--i]);
+
+      if (pt == nullptr) // Skipped.
+        continue;
+
+      target_state s (execute_async (a, *pt, busy, t[a].task_count));
+
+      if (s == target_state::postponed)
+      {
+        rs |= s;
+        pt = nullptr;
+      }
+    }
+
+    wg.wait ();
+
+    bool e (mt == timestamp_nonexistent);
+    const target* rt (nullptr);
+
+    for (size_t i (n); i != 0; )
+    {
+      prerequisite_target& p (pts[--i]);
+
+      if (p == nullptr)
+        continue;
+
+      const target& pt (*p.target);
+
+      ctx.sched.wait (exec, pt[a].task_count, scheduler::work_none);
+
+      target_state s (pt.executed_state (a));
+      rs |= s;
+
+      // Should we compare the timestamp to this target's?
+      //
+      if (!e && (p.adhoc () || !ef || ef (pt, i)))
+      {
+        // If this is an mtime-based target, then compare timestamps.
+        //
+        if (const mtime_target* mpt = pt.is_a<mtime_target> ())
+        {
+          if (mpt->newer (mt, s))
+            e = true;
+        }
+        else
+        {
+          // Otherwise we assume the prerequisite is newer if it was changed.
+          //
+          if (s == target_state::changed)
+            e = true;
+        }
+      }
+
+      if (p.adhoc ())
+        p.target = nullptr; // Blank out.
+      else if (tt != nullptr)
+      {
+        // Note that here we need last.
+        //
+        if (pt.is_a (*tt))
+          rt = &pt;
+      }
+    }
+
+    assert (tt == nullptr || rt != nullptr);
 
     return pair<optional<target_state>, const target*> (
-      e ? optional<target_state> () : rs,
-      tt != nullptr ? rt : nullptr);
+      e ? optional<target_state> () : rs, rt);
   }
 
   target_state
diff --git a/libbuild2/algorithm.hxx b/libbuild2/algorithm.hxx
index b472603..00d4fdd 100644
--- a/libbuild2/algorithm.hxx
+++ b/libbuild2/algorithm.hxx
@@ -678,8 +678,8 @@ namespace build2
   // case if they are up to something tricky (like recursively linking liba{}
   // prerequisites).
   //
-  // Note that because we use mtime, this function should normally only be
-  // used in the perform_update action (which is straight).
+  // Note that because we use mtime, this function can only be used for the
+  // perform_update action.
   //
   using execute_filter = function<bool (const target&, size_t pos)>;
 
@@ -689,6 +689,18 @@ namespace build2
                          const execute_filter& = nullptr,
                          size_t count = 0);
 
+  // As above, but execute prerequisites in reverse.
+  //
+  // Sometime it may be advantageous to execute prerequisites in reverse, for
+  // example, to have more immediate incremental compilation or more accurate
+  // progress. See cc::link_rule for background.
+  //
+  optional<target_state>
+  reverse_execute_prerequisites (action, const target&,
+                                 const timestamp&,
+                                 const execute_filter& = nullptr,
+                                 size_t count = 0);
+
   // Another version of the above that does two extra things for the caller:
   // it determines whether the action needs to be executed on the target based
   // on the passed timestamp and finds a prerequisite of the specified type
diff --git a/libbuild2/algorithm.ixx b/libbuild2/algorithm.ixx
index c57e117..1b3a5cd 100644
--- a/libbuild2/algorithm.ixx
+++ b/libbuild2/algorithm.ixx
@@ -834,6 +834,12 @@ namespace build2
                          const timestamp&, const execute_filter&,
                          size_t);
 
+  LIBBUILD2_SYMEXPORT pair<optional<target_state>, const target*>
+  reverse_execute_prerequisites (const target_type*,
+                                 action, const target&,
+                                 const timestamp&, const execute_filter&,
+                                 size_t);
+
   inline optional<target_state>
   execute_prerequisites (action a, const target& t,
                          const timestamp& mt, const execute_filter& ef,
@@ -842,6 +848,14 @@ namespace build2
     return execute_prerequisites (nullptr, a, t, mt, ef, n).first;
   }
 
+  inline optional<target_state>
+  reverse_execute_prerequisites (action a, const target& t,
+                                 const timestamp& mt, const execute_filter& ef,
+                                 size_t n)
+  {
+    return reverse_execute_prerequisites (nullptr, a, t, mt, ef, n).first;
+  }
+
   template <typename T>
   inline pair<optional<target_state>, const T&>
   execute_prerequisites (action a, const target& t,
diff --git a/libbuild2/cc/link-rule.cxx b/libbuild2/cc/link-rule.cxx
index 50c56a4..2e644cc 100644
--- a/libbuild2/cc/link-rule.cxx
+++ b/libbuild2/cc/link-rule.cxx
@@ -2470,14 +2470,33 @@ namespace build2
       // Note that execute_prerequisites() blanks out all the ad hoc
       // prerequisites so we don't need to worry about them from now on.
       //
+      // There is an interesting trade-off between the straight and reverse
+      // execution. With straight we may end up with inaccurate progress if
+      // most of our library prerequisites (typically specified last) are
+      // already up to date. In this case, the progress will first increase
+      // slowly as we compile this target's source files and then jump
+      // straight to 100% as we "realize" that all the libraries (and all
+      // their prerequisites) are already up to date.
+      //
+      // Switching to reverse fixes this but messes up incremental building:
+      // now instead of starting to compile source files right away, we will
+      // first spend some time making sure all the libraries are up to date
+      // (which, in case of an error in the source code, will be a complete
+      // waste).
+      //
+      // There doesn't seem to be an easy way to distinguish between
+      // incremental and from-scratch builds and on balance fast incremental
+      // builds feel more important.
+      //
       target_state ts;
 
-      if (optional<target_state> s =
-          execute_prerequisites (a,
-                                 t,
-                                 mt,
-                                 [] (const target&, size_t) {return false;}))
+      if (optional<target_state> s = execute_prerequisites (
+            a, t,
+            mt,
+            [] (const target&, size_t) {return false;}))
+      {
         ts = *s;
+      }
       else
       {
         // An ad hoc prerequisite renders us out-of-date. Let's update from