Introduce target::task_count

1 files changed, 122 insertions, 36 deletions

diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx
index 734c545..f173af6 100644
--- a/build2/algorithm.cxx
+++ b/build2/algorithm.cxx
@@ -10,6 +10,7 @@
 #include <build2/file> // import()
 #include <build2/search>
 #include <build2/context>
+#include <build2/scheduler>
 #include <build2/filesystem>
 #include <build2/diagnostics>
 #include <build2/prerequisite>
@@ -386,46 +387,131 @@ namespace build2
     return r;
   }
 
-  target_state
+  inline target_state
   execute_impl (action a, target& t)
   {
-    // Implementation with some multi-threading ideas in mind.
+    // Task count should be count_executing.
     //
-    switch (t.raw_state)
+    assert (t.state_ == target_state::unknown);
+
+    auto g (
+      make_exception_guard (
+        [a, &t]()
+        {
+          t.state_ = target_state::failed;
+
+          if (verb != 0)
+            info << "while " << diag_doing (a, t);
+        }));
+
+    target_state ts (t.recipe (a) (a, t));
+    assert (ts != target_state::unknown && ts != target_state::failed);
+
+    t.state_ = ts;
+    if (ts == target_state::group)
+      ts = t.group->state_;
+
+    // Decrement the task count (to count_executed) and wake up any threads
+    // that might be waiting for this target.
+    //
+    size_t tc (t.task_count--);
+    assert (tc == target::count_executing);
+    sched.resume (t.task_count);
+
+    return ts;
+  }
+
+  target_state
+  execute (action a, target& t)
+  {
+    // text << "E " << t << ": " << t.dependents << " " << dependency_count;
+
+    size_t d (0);
+    if (dependency_count != 0) // Re-examination of a postponed target?
     {
-    case target_state::group: // Means group's state is unknown.
-    case target_state::unknown:
-    case target_state::postponed:
-      {
-        auto g (
-          make_exception_guard (
-            [a, &t]()
-            {
-              t.raw_state = target_state::failed;
+      // Note that re-examination only happens during serial execution so
+      // dependency_count can only become 0 if we have skew counts.
+      //
+      // Note: memory order can probably be relaxed.
+      //
+      size_t g (dependency_count--);
+      d = t.dependents--;
+      assert (g != 0 && d != 0);
+      d--;
+    }
 
-              if (verb != 0)
-                info << "while " << diag_doing (a, t);
-            }));
+    // Handle the "last" execution mode.
+    //
+    // This gets interesting when we consider interaction with
+    // groups. It seem to make sense to treat group members as
+    // dependents of the group, so, for example, if we try to
+    // clean the group via three of its members, only the last
+    // attempt will actually execute the clean. This means that
+    // when we match a group member, inside we should also match
+    // the group in order to increment the dependents count. This
+    // seems to be a natural requirement: if we are delegating to
+    // the group, we need to find a recipe for it, just like we
+    // would for a prerequisite.
+    //
+    // Note that below we are going to change the group state
+    // to postponed. This is not a mistake: until we execute
+    // the recipe, we want to keep returning postponed. And
+    // once the recipe is executed, it will reset the state
+    // to group (see group_action()). To put it another way,
+    // the execution of this member is postponed, not of the
+    // group.
+    //
+    // One important invariant to keep in mind: the return
+    // value from execute() should always be the same as what
+    // would get returned by a subsequent call to state().
+    //
+    size_t tc (target::count_unexecuted);
+    if (current_mode == execution_mode::last && d != 0)
+    {
+      // Try to atomically change unexecuted to postponed.
+      //
+      if (t.task_count.compare_exchange_strong (tc, target::count_postponed))
+        tc = target::count_postponed;
+    }
+    else
+    {
+      // Try to atomically change unexecuted to executing. But it can also be
+      // postponed to executing.
+      //
+      if (t.task_count.compare_exchange_strong (tc, target::count_executing) ||
+          (tc == target::count_postponed &&
+           t.task_count.compare_exchange_strong (tc, target::count_executing)))
+        return execute_impl (a, t);
+    }
 
-        target_state ts (t.recipe (a) (a, t));
-        assert (ts != target_state::unknown && ts != target_state::failed);
+    switch (tc)
+    {
+    case target::count_unexecuted: assert (false);
+    case target::count_postponed:  return target_state::postponed;
+    case target::count_executed:   return t.state ();
+    default:                       return target_state::busy;
+    }
+  }
 
-        // Set the target's state unless it should be the group's state.
-        //
-        if (t.raw_state != target_state::group)
-          t.raw_state = ts;
+  target_state
+  execute_direct (action a, target& t)
+  {
+    size_t tc (target::count_unexecuted);
+    if (t.task_count.compare_exchange_strong (tc, target::count_executing))
+      return execute_impl (a, t);
 
-        return ts;
-      }
-    case target_state::unchanged:
-    case target_state::changed:
-      // Should have been handled by inline execute().
-      assert (false);
-    case target_state::failed:
-      break;
+    // If the target is busy, wait for it.
+    //
+    switch (tc)
+    {
+    case target::count_unexecuted:
+    case target::count_postponed:  assert (false);
+    case target::count_executed:   break;
+    default:                       sched.wait (target::count_executed,
+                                               t.task_count);
     }
 
-    throw failed ();
+    return t.state ();
   }
 
   target_state
@@ -522,14 +608,14 @@ namespace build2
   target_state
   group_action (action a, target& t)
   {
-    target_state r (execute (a, *t.group));
-
-    // Indicate to the standard execute() logic that this target's
-    // state comes from the group.
+    // If the group is busy, we wait, similar to prerequisites.
     //
-    t.raw_state = target_state::group;
+    if (execute (a, *t.group) == target_state::busy)
+      sched.wait (target::count_executed, t.group->task_count);
 
-    return r;
+    // Indicate to execute() that this target's state comes from the group.
+    //
+    return target_state::group;
   }
 
   target_state