Introduce target::task_count

9 files changed, 192 insertions, 136 deletions

diff --git a/build2/algorithm b/build2/algorithm
index cb84231..09e0c4d 100644
--- a/build2/algorithm
+++ b/build2/algorithm
@@ -167,7 +167,8 @@ namespace build2
   // and "now" execution, that is, side-stepping the normal target-
   // prerequisite relationship (so no dependents count is decremented)
   // and execution order (so this function will never return postponed
-  // target state).
+  // target state). It will also wait for the completion if the target
+  // is busy.
   //
   target_state
   execute_direct (action, target&);
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
diff --git a/build2/algorithm.ixx b/build2/algorithm.ixx
index f8e3191..cf234d8 100644
--- a/build2/algorithm.ixx
+++ b/build2/algorithm.ixx
@@ -3,7 +3,6 @@
 // license   : MIT; see accompanying LICENSE file
 
 #include <build2/rule>
-#include <build2/prerequisite>
 #include <build2/context>
 
 namespace build2
@@ -173,83 +172,12 @@ namespace build2
     search_and_match_prerequisite_members (ml, a, t, &s);
   }
 
-  target_state
-  execute_impl (action, target&);
-
-  inline target_state
-  execute (action a, target& t)
-  {
-    // text << "E " << t << ": " << t.dependents << " " << dependency_count;
-
-    if (dependency_count != 0) // Re-examination of a postponed target?
-    {
-      assert (t.dependents != 0);
-      --t.dependents;
-      --dependency_count;
-    }
-
-    // Don't short-circuit to the group state since we need to execute the
-    // member's recipe to keep the dependency counts straight.
-    //
-    switch (target_state ts = t.state (false))
-    {
-    case target_state::unchanged:
-    case target_state::changed:
-      return ts;
-    default:
-      {
-        // 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().
-        //
-        if (current_mode == execution_mode::last && t.dependents != 0)
-          return (t.raw_state = target_state::postponed);
-
-        return execute_impl (a, t);
-      }
-    }
-  }
-
   inline target_state
   execute_delegate (const recipe& r, action a, target& t)
   {
     return r (a, t);
   }
 
-  inline target_state
-  execute_direct (action a, target& t)
-  {
-    // Here we don't care about the counts so short-circuit state is ok.
-    //
-    switch (target_state ts = t.state ())
-    {
-    case target_state::unchanged:
-    case target_state::changed: return ts;
-    default: return execute_impl (a, t);
-    }
-  }
-
   // If the first argument is NULL, then the result is treated as a boolean
   // value.
   //
diff --git a/build2/context b/build2/context
index d6f79af..da2ced5 100644
--- a/build2/context
+++ b/build2/context
@@ -243,7 +243,7 @@ namespace build2
   // execution with the expectation of it reaching 0. Used as a sanity
   // check.
   //
-  extern uint64_t dependency_count;
+  extern atomic_count dependency_count;
 
   // Variable override value cache.
   //
diff --git a/build2/context.cxx b/build2/context.cxx
index e15294a..400f68c 100644
--- a/build2/context.cxx
+++ b/build2/context.cxx
@@ -56,7 +56,7 @@ namespace build2
 
   execution_mode current_mode;
 
-  uint64_t dependency_count;
+  atomic_count dependency_count;
 
   variable_override_cache var_override_cache;
 
diff --git a/build2/operation.cxx b/build2/operation.cxx
index 5815834..19f1ff7 100644
--- a/build2/operation.cxx
+++ b/build2/operation.cxx
@@ -173,6 +173,8 @@ namespace build2
     // Re-examine postponed targets. This is the only reliable way to
     // find out whether the target has changed.
     //
+    // Note: must be serial.
+    //
     for (target& t: psp)
     {
       switch (execute (a, t))
diff --git a/build2/target b/build2/target
index 1a300f7..fb8fd08 100644
--- a/build2/target
+++ b/build2/target
@@ -33,13 +33,17 @@ namespace build2
   //
   enum class target_state: uint8_t
   {
-    // The order of the enumerators is arranged so that their integral
-    // values indicate whether one "overrides" the other in the merge
-    // operator (see below).
+    // The order of the enumerators is arranged so that their integral values
+    // indicate whether one "overrides" the other in the "merge" operator|
+    // (see below).
+    //
+    // Note that postponed is "greater" than unchanged since it may result in
+    // the changed state.
     //
     unknown,
     unchanged,
     postponed,
+    busy,
     changed,
     failed,
     group       // Target's state is the group's state.
@@ -63,10 +67,8 @@ namespace build2
   // though you shouldn't be returning postponed directly. If there is an
   // error, then the recipe should throw rather than returning failed.
   //
-  // The return value of the recipe is used to update the target state except
-  // if the state is set to target_state::group by the recipe. Note that in
-  // this case the returned by the recipe value is still used as the resulting
-  // target state so it should match the group's state.
+  // The return value of the recipe is used to update the target state. If it
+  // is target_state::group then the target's state is the group's state.
   //
   // Note that max size for the "small capture optimization" in std::function
   // ranges (in pointer sizes) from 0 (GCC prior to 5) to 2 (GCC 5) to 6 (VC
@@ -394,30 +396,50 @@ namespace build2
 
     // Target state.
     //
+  protected:
+    friend target_state execute_impl (action, target&);
+
+    target_state state_;
+
   public:
-    target_state raw_state = target_state::unknown;
 
-    // By default we go an extra step and short-circuit to the target state
-    // even if the raw state is not group provided the recipe is group_recipe.
-    // This is normally what you want or need, as in inject_prerequisites()
-    // in the cc module. But sometimes not, as in execute().
+    // Atomic task count that is used during execution to (atomically) track a
+    // subset of the target's state as well as the number of its sub-tasks
+    // (execution of prerequisites).
+    //
+    // The task starts unexecuted and can then transition to postponed or
+    // executing. Postponed can transition to executing. And executing
+    // transitions (via a decrement) to executed. Once it is executed, then
+    // state_ becomes immutable.
+    //
+    static const size_t count_unexecuted = 0;
+    static const size_t count_postponed  = 1;
+    static const size_t count_executed   = 2;
+    static const size_t count_executing  = 3;
+
+    atomic_count task_count;
+
+    // @@ MT TODO: when can be called.
     //
     target_state
-    state (bool shortcircuit = true) const
+    state () const
     {
-      if (raw_state == target_state::group)
-        return group->raw_state;
+      // We go an extra step and short-circuit to the target state even if the
+      // raw state is not group provided the recipe is group_recipe.
+
+      if (state_ == target_state::group)
+        return group->state_;
 
-      if (group == nullptr || !shortcircuit)
-        return raw_state;
+      if (group == nullptr)
+        return state_;
 
       if (recipe_function* const* f = recipe_.target<recipe_function*> ())
       {
         if (*f == &group_action)
-          return group->raw_state;
+          return group->state_;
       }
 
-      return raw_state;
+      return state_;
     }
 
     // Number of direct targets that depend on this target in the current
@@ -433,7 +455,7 @@ namespace build2
     // should have been decremented to 0 naturally, as part of the previous
     // action execution.
     //
-    size_t dependents;
+    atomic_count dependents;
 
     // Auxilary data storage.
     //
@@ -1106,7 +1128,7 @@ namespace build2
     timestamp
     mtime (bool load = true) const
     {
-      const mtime_target* t (raw_state == target_state::group
+      const mtime_target* t (state_ == target_state::group
                              ? static_cast<const mtime_target*> (group)
                              : this);
 
diff --git a/build2/target.cxx b/build2/target.cxx
index b250597..f7387c7 100644
--- a/build2/target.cxx
+++ b/build2/target.cxx
@@ -31,8 +31,16 @@ namespace build2
 
   // target_state
   //
-  static const char* const target_state_[] = {
-    "unknown", "unchanged", "postponed", "changed", "failed", "group"};
+  static const char* const target_state_[] =
+  {
+    "unknown",
+    "unchanged",
+    "postponed",
+    "busy",
+    "changed",
+    "failed",
+    "group"
+  };
 
   ostream&
   operator<< (ostream& os, target_state ts)
@@ -99,7 +107,7 @@ namespace build2
     action = a;
     recipe_ = move (r);
 
-    raw_state = target_state::unknown;
+    state_ = target_state::unknown;
 
     // If this is a noop recipe, then mark the target unchanged so that we
     // don't waste time executing the recipe.
@@ -107,9 +115,15 @@ namespace build2
     if (recipe_function** f = recipe_.target<recipe_function*> ())
     {
       if (*f == &noop_action)
-        raw_state = target_state::unchanged;
+        state_ = target_state::unchanged;
     }
 
+    //@@ MT can this be a relaxed save?
+    //
+    task_count = state_ == target_state::unknown
+      ? count_unexecuted
+      : count_executed;
+
     // This one is tricky: we don't want to reset the dependents count
     // if we are merely overriding with a "stronger" recipe.
     //
diff --git a/build2/types b/build2/types
index b9f3ce9..7afc24e 100644
--- a/build2/types
+++ b/build2/types
@@ -19,6 +19,7 @@
 #include <initializer_list>
 
 #include <mutex>
+#include <atomic>
 #include <future>
 
 #include <butl/ft/shared_mutex>
@@ -78,6 +79,8 @@ namespace build2
 
   // Concurrency.
   //
+  using atomic_count = std::atomic<size_t>; // Matches scheduler::atomic_count.
+
   using std::future;
 
 #if   defined(__cpp_lib_shared_mutex)