Add support for try_match(), use to handle deleted headers

8 files changed, 184 insertions, 73 deletions

diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx
index 864f90c..361c80f 100644
--- a/build2/algorithm.cxx
+++ b/build2/algorithm.cxx
@@ -168,6 +168,7 @@ namespace build2
       // First lock for this operation.
       //
       t.action = a;
+      t.rule = nullptr;
       t.dependents.store (0, memory_order_release);
       offset = target::offset_touched;
     }
@@ -192,6 +193,7 @@ namespace build2
           assert (a > t.action);
         }
       case target::offset_touched:
+      case target::offset_tried:
       case target::offset_matched:
       case target::offset_applied:
         {
@@ -206,6 +208,7 @@ namespace build2
             }
 
             t.action = a;
+            t.rule = nullptr;
             offset = target::offset_touched; // Back to just touched.
           }
           else
@@ -283,7 +286,7 @@ namespace build2
   // Return the matching rule and the recipe action.
   //
   pair<const pair<const string, reference_wrapper<const rule>>*, action>
-  match_impl (action a, target& t, const rule* skip, bool f)
+  match_impl (action a, target& t, const rule* skip, bool try_match)
   {
     // Clear the resolved targets list before calling match(). The rule is
     // free to modify this list in match() (provided that it matches) in order
@@ -439,7 +442,7 @@ namespace build2
       }
     }
 
-    if (f)
+    if (!try_match)
     {
       diag_record dr;
       dr << fail << "no rule to " << diag_do (a, t);
@@ -473,8 +476,14 @@ namespace build2
 
   // If step is true then perform only one step of the match/apply sequence.
   //
-  static target_state
-  match_impl (action a, target_lock& l, bool step = false)
+  // If try_match is true, then indicate whether there is a rule match with
+  // the first half of the result.
+  //
+  static pair<bool, target_state>
+  match_impl (action a,
+              target_lock& l,
+              bool step = false,
+              bool try_match = false)
   {
     assert (l.target != nullptr);
     target& t (*l.target);
@@ -485,17 +494,33 @@ namespace build2
       //
       switch (l.offset)
       {
+      case target::offset_tried:
+        {
+          if (try_match)
+            return make_pair (false, target_state::unknown);
+
+          // Fall through (to issue diagnostics).
+        }
       case target::offset_touched:
         {
           // Match.
           //
-          auto mr (match_impl (a, t, nullptr));
+          auto mr (match_impl (a, t, nullptr, try_match));
+
+          if (mr.first == nullptr) // Not found (try_match == true).
+          {
+            l.offset = target::offset_tried;
+            return make_pair (false, target_state::unknown);
+          }
+
           t.rule = mr.first;
           t.action = mr.second; // In case overriden.
           l.offset = target::offset_matched;
 
           if (step)
-            return target_state::unknown; // t.state_ not set yet.
+            // t.state_ is not yet set.
+            //
+            return make_pair (true, target_state::unknown);
 
           // Fall through.
         }
@@ -523,14 +548,18 @@ namespace build2
       l.offset = target::offset_applied;
     }
 
-    return t.state_;
+    return make_pair (true, t.state_);
   }
 
-  target_state
+  // If try_match is true, then indicate whether there is a rule match with
+  // the first half of the result.
+  //
+  pair<bool, target_state>
   match (action a,
          const target& ct,
          size_t start_count,
-         atomic_count* task_count)
+         atomic_count* task_count,
+         bool try_match)
   {
     // If we are blocking then work our own queue one task at a time. The
     // logic here is that we may have already queued other tasks before this
@@ -555,17 +584,22 @@ namespace build2
 
     if (l.target == nullptr)
     {
-      // Already matched, executed, or busy.
+      // Already applied, executed, or busy.
       //
       if (l.offset >= target::offset_busy)
-        return target_state::busy;
+        return make_pair (true, target_state::busy);
 
       // Fall through.
     }
-    else if (l.offset != target::offset_applied) // Nothing to do if applied.
+    else
     {
+      assert (l.offset < target::offset_applied); // Shouldn't lock otherwise.
+
+      if (try_match && l.offset == target::offset_tried)
+        return make_pair (false, target_state::unknown);
+
       if (task_count == nullptr)
-        return match_impl (a, l);
+        return match_impl (a, l, /*step*/ false, try_match);
 
       // Pass "disassembled" lock since the scheduler queue doesn't support
       // task destruction. Also pass our diagnostics stack (this is safe since
@@ -574,27 +608,27 @@ namespace build2
       //
       if (sched.async (start_count,
                        *task_count,
-                       [a] (target& t,
-                            size_t offset,
-                            const diag_frame* ds)
+                       [a, try_match] (target& t,
+                                       size_t offset,
+                                       const diag_frame* ds)
                        {
                          diag_frame df (ds);
                          phase_lock pl (run_phase::match);
                          {
                            target_lock l {&t, offset}; // Reassemble.
-                           match_impl (a, l);
+                           match_impl (a, l, /*step*/ false, try_match);
                            // Unlock withing the match phase.
                          }
                        },
                        ref (*l.release ()),
                        l.offset,
                        diag_frame::stack))
-        return target_state::postponed; // Queued.
+        return make_pair (true, target_state::postponed); // Queued.
 
       // Matched synchronously, fall through.
     }
 
-    return ct.matched_state (a, false);
+    return ct.try_matched_state (a, false);
   }
 
   group_view
@@ -609,10 +643,11 @@ namespace build2
     switch (l.offset)
     {
     case target::offset_touched:
+    case target::offset_tried:
       {
         // Match (locked).
         //
-        if (match_impl (a, l, true) == target_state::failed)
+        if (match_impl (a, l, true).second == target_state::failed)
           throw failed ();
 
         if ((r = g.group_members (a)).members != nullptr)
@@ -628,7 +663,7 @@ namespace build2
       {
         // Apply (locked).
         //
-        if (match_impl (a, l, true) == target_state::failed)
+        if (match_impl (a, l, true).second == target_state::failed)
           throw failed ();
 
         if ((r = g.group_members (a)).members != nullptr)
@@ -926,9 +961,9 @@ namespace build2
             memory_order_acq_rel,  // Synchronize on success.
             memory_order_acquire)) // Synchronize on failure.
       {
-        // Overriden touch/match-only or noop recipe.
+        // Overriden touch/tried/match-only or noop recipe.
         //
-        if (tc == touc || tc == matc || t.state_ == target_state::unchanged)
+        if ((tc >= touc && tc <= matc) || t.state_ == target_state::unchanged)
         {
           t.state_ = target_state::unchanged;
           t.task_count.store (exec, memory_order_release);
@@ -963,11 +998,11 @@ namespace build2
         if (tc >= busy) return target_state::busy;
         else if (tc != exec)
         {
-          // This can happen if we touched/matched (a noop) recipe which then
-          // got overridden as part of group resolution but not all the way to
-          // applied. In this case we treat it as noop.
+          // This can happen if we touched/tried/matched (a noop) recipe which
+          // then got overridden as part of group resolution but not all the
+          // way to applied. In this case we treat it as noop.
           //
-          assert ((tc == touc || tc == matc) && t.action > a);
+          assert ((tc >= touc && tc <= matc) && t.action > a);
           continue;
         }
       }
@@ -998,7 +1033,7 @@ namespace build2
             memory_order_acq_rel,  // Synchronize on success.
             memory_order_acquire)) // Synchronize on failure.
       {
-        if (tc == touc || tc == matc || t.state_ == target_state::unchanged)
+        if ((tc >= touc && tc <= matc) || t.state_ == target_state::unchanged)
         {
           t.state_ = target_state::unchanged;
           t.task_count.store (exec, memory_order_release);
@@ -1014,7 +1049,7 @@ namespace build2
         if (tc >= busy) sched.wait (exec, t.task_count, scheduler::work_none);
         else if (tc != exec)
         {
-          assert ((tc == touc || tc == matc) && t.action > a);
+          assert ((tc >= touc && tc <= matc) && t.action > a);
           continue;
         }
       }
diff --git a/build2/algorithm.hxx b/build2/algorithm.hxx
index e8b9823..dbc7d9b 100644
--- a/build2/algorithm.hxx
+++ b/build2/algorithm.hxx
@@ -173,6 +173,11 @@ namespace build2
   // state translating target_state::failed to the failed exception unless
   // instructed otherwise.
   //
+  // The try_match() version doesn't issue diagnostics if there is no rule
+  // match (but fails as match() for all other errors, like rule ambiguity,
+  // inability to apply, etc). The first half of the result indicated whether
+  // there was a rule match.
+  //
   // The unmatch argument allows optimizations that avoid calling execute().
   // If it is unmatch::unchanged then only unmatch the target if it is known
   // to be unchanged after match. If it is unmatch::safe, then unmatch the
@@ -185,6 +190,9 @@ namespace build2
   target_state
   match (action, const target&, bool fail = true);
 
+  pair<bool, target_state>
+  try_match (action, const target&, bool fail = true);
+
   bool
   match (action, const target&, unmatch);
 
@@ -208,13 +216,13 @@ namespace build2
   match_recipe (target_lock&, recipe);
 
   // Match a "delegate rule" from withing another rules' apply() function
-  // avoiding recursive matches (thus the third argument). Unless fail is
-  // false, fail if not rule is found. Otherwise return empty recipe. Note
-  // that unlike match(), this function does not increment the dependents
+  // avoiding recursive matches (thus the third argument). Unless try_match is
+  // true, fail if not rule is found. Otherwise return empty recipe. Note that
+  // unlike match(), this function does not increment the dependents
   // count. See also the companion execute_delegate().
   //
   recipe
-  match_delegate (action, target&, const rule&, bool fail = true);
+  match_delegate (action, target&, const rule&, bool try_match = false);
 
   // The standard prerequisite search and match implementations. They call
   // search() and then match() for each prerequisite in a loop omitting out of
diff --git a/build2/algorithm.ixx b/build2/algorithm.ixx
index 03b4604..03728db 100644
--- a/build2/algorithm.ixx
+++ b/build2/algorithm.ixx
@@ -180,43 +180,69 @@ namespace build2
     // We don't allow locking a target that has already been matched.
     //
     target_lock r (lock_impl (a, t, scheduler::work_none));
-    assert (!r || r.offset == target::offset_touched);
+    assert (!r                                 ||
+            r.offset == target::offset_touched ||
+            r.offset == target::offset_tried);
     return r;
   }
 
   pair<const pair<const string, reference_wrapper<const rule>>*, action>
-  match_impl (action, target&, const rule* skip, bool fail = true);
+  match_impl (action, target&, const rule* skip, bool try_match = false);
 
   recipe
   apply_impl (target&,
               const pair<const string, reference_wrapper<const rule>>&,
               action);
 
-  target_state
-  match (action, const target&, size_t, atomic_count*);
+  pair<bool, target_state>
+  match (action, const target&, size_t, atomic_count*, bool try_match = false);
 
   inline target_state
   match (action a, const target& t, bool fail)
   {
     assert (phase == run_phase::match);
 
-    target_state s (match (a, t, 0, nullptr));
+    target_state r (match (a, t, 0, nullptr).second);
 
-    if (fail && s == target_state::failed)
+    if (r != target_state::failed)
+    {
+      dependency_count.fetch_add (1, memory_order_relaxed);
+      t.dependents.fetch_add (1, memory_order_release);
+    }
+    else if (fail)
       throw failed ();
 
-    dependency_count.fetch_add (1, memory_order_relaxed);
-    t.dependents.fetch_add (1, memory_order_release);
+    return r;
+  }
+
+  inline pair<bool, target_state>
+  try_match (action a, const target& t, bool fail)
+  {
+    assert (phase == run_phase::match);
+
+    pair<bool, target_state> r (match (a, t, 0, nullptr, /*try_match*/ true));
 
-    return s;
+    if (r.first)
+    {
+      if (r.second != target_state::failed)
+      {
+        dependency_count.fetch_add (1, memory_order_relaxed);
+        t.dependents.fetch_add (1, memory_order_release);
+      }
+      else if (fail)
+        throw failed ();
+    }
+
+    return r;
   }
 
+
   inline bool
   match (action a, const target& t, unmatch um)
   {
     assert (phase == run_phase::match);
 
-    target_state s (match (a, t, 0, nullptr));
+    target_state s (match (a, t, 0, nullptr).second);
 
     if (s == target_state::failed)
       throw failed ();
@@ -255,7 +281,7 @@ namespace build2
                bool fail)
   {
     assert (phase == run_phase::match);
-    target_state r (match (a, t, sc, &tc));
+    target_state r (match (a, t, sc, &tc).second);
 
     if (fail && !keep_going && r == target_state::failed)
       throw failed ();
@@ -275,10 +301,10 @@ namespace build2
   }
 
   inline recipe
-  match_delegate (action a, target& t, const rule& r, bool fail)
+  match_delegate (action a, target& t, const rule& r, bool try_match)
   {
     assert (phase == run_phase::match);
-    auto mr (match_impl (a, t, &r, fail));
+    auto mr (match_impl (a, t, &r, try_match));
     return mr.first != nullptr
       ? apply_impl (t, *mr.first, mr.second)
       : empty_recipe;
diff --git a/build2/cc/compile.cxx b/build2/cc/compile.cxx
index 9e720ed..c1f4e08 100644
--- a/build2/cc/compile.cxx
+++ b/build2/cc/compile.cxx
@@ -1938,6 +1938,7 @@ namespace build2
       // date then we use the same restart and skip logic to switch to the
       // compiler run.
       //
+      size_t skip_count (0);
 
       // Update and add a header file to the list of prerequisite targets.
       // Depending on the cache flag, the file is assumed to either have come
@@ -1946,7 +1947,7 @@ namespace build2
       //
       auto add = [&trace, &pfx_map, &so_map,
                   act, &t, li,
-                  &dd, &updating,
+                  &dd, &updating, &skip_count,
                   &bs, this]
         (path f, bool cache, timestamp mt) -> bool
       {
@@ -2167,14 +2168,24 @@ namespace build2
 
         // Match to a rule.
         //
-        build2::match (act, *pt);
+        // If we are reading the cache, then it is possible the file has since
+        // been removed (think of a header in /usr/local/include that has been
+        // uninstalled and now we need to use one from /usr/include). This
+        // will lead to the match failure which we translate to a restart.
+        //
+        if (!cache)
+          build2::match (act, *pt);
+        else if (!build2::try_match (act, *pt).first)
+        {
+          dd.write (); // Invalidate this line.
+          updating = true;
+          return true;
+        }
 
         // Update.
         //
         bool restart (update (trace, act, *pt, mt));
 
-        updating = updating || restart;
-
         // Verify/add it to the dependency database. We do it after update in
         // order not to add bogus files (non-existent and without a way to
         // update).
@@ -2185,7 +2196,9 @@ namespace build2
         // Add to our prerequisite target list.
         //
         t.prerequisite_targets.push_back (pt);
+        skip_count++;
 
+        updating = updating || restart;
         return restart;
       };
 
@@ -2201,7 +2214,6 @@ namespace build2
 
       const path* drmp (nullptr); // Points to drm.path () if active.
 
-      size_t skip_count (0);
       for (bool restart (true); restart; cache = false)
       {
         restart = false;
@@ -2241,7 +2253,6 @@ namespace build2
             // updated, then the cached data is stale).
             //
             restart = add (path (move (*l)), true, mt);
-            skip_count++;
 
             if (restart)
             {
@@ -2405,7 +2416,6 @@ namespace build2
                   else
                   {
                     restart = add (path (move (f)), false, pmt);
-                    skip_count++;
 
                     // If the header does not exist (good_error) then restart
                     // must be true. Except that it is possible that someone
@@ -2476,7 +2486,6 @@ namespace build2
                     }
 
                     restart = add (path (move (f)), false, pmt);
-                    skip_count++;
 
                     if (restart)
                     {
diff --git a/build2/depdb.hxx b/build2/depdb.hxx
index da45a4a..520642e 100644
--- a/build2/depdb.hxx
+++ b/build2/depdb.hxx
@@ -144,6 +144,11 @@ namespace build2
     void
     write (char, bool nl = true);
 
+    // Mark the previously read line as to be overwritte.
+    //
+    void
+    write () {if (state_ != state::write) change ();}
+
     // Read the next line and compare it to the expected value. If it matches,
     // return NULL. Otherwise, overwrite it and return the old value (which
     // could also be NULL). This strange-sounding result semantics is used to
diff --git a/build2/target.cxx b/build2/target.cxx
index 40c73c0..7ff995d 100644
--- a/build2/target.cxx
+++ b/build2/target.cxx
@@ -117,7 +117,7 @@ namespace build2
     return *r;
   }
 
-  target_state target::
+  pair<bool, target_state> target::
   state (action_type a) const
   {
     assert (phase == run_phase::match);
@@ -147,15 +147,15 @@ namespace build2
       for (; e == lock; e = task_count.load (memory_order_acquire))
         this_thread::yield ();
 
-      if (e >= busy)
-        return target_state::unchanged; // Override in progress.
+      if (e >= busy) // Override in progress.
+        return make_pair (true, target_state::unchanged);
 
       // Unlike lock_impl(), we are only called after being matched for this
       // action so if we see executed, then it means executed for this action
       // (or noop).
       //
       if (e == exec)
-        return group_state () ? group->state_ : state_;
+        return make_pair (true, group_state () ? group->state_ : state_);
 
       // Try to grab the spin-lock.
       //
@@ -174,17 +174,24 @@ namespace build2
     // We have the spin-lock. Quickly get the matched action and unlock.
     //
     action_type ma (action);
-    bool failed (state_ == target_state::failed);
+    bool mf (state_ == target_state::failed);
     task_count.store (e, memory_order_release);
 
     if (ma > a) // Overriden.
-      return failed ? target_state::failed: target_state::unchanged;
+      return make_pair (true, // Override may have failed but we had the rule.
+                        mf ? target_state::failed: target_state::unchanged);
 
     // Otherwise we should have a matched target.
     //
-    assert (ma == a && (e == b + target::offset_applied || e == exec));
+    assert (ma == a);
 
-    return group_state () ? group->state_ : state_;
+    if (e == b + target::offset_tried)
+      return make_pair (false, target_state::unknown);
+    else
+    {
+      assert (e == b + target::offset_applied || e == exec);
+      return make_pair (true, group_state () ? group->state_ : state_);
+    }
   }
 
   pair<lookup, size_t> target::
diff --git a/build2/target.hxx b/build2/target.hxx
index 0309dd6..62e7779 100644
--- a/build2/target.hxx
+++ b/build2/target.hxx
@@ -460,16 +460,18 @@ namespace build2
     // the target is synchronized, then we can access and modify (second case)
     // its state etc.
     //
-    static const size_t offset_touched  = 1; // Has been locked.
-    static const size_t offset_matched  = 2; // Rule has been matched.
-    static const size_t offset_applied  = 3; // Rule has been applied.
-    static const size_t offset_executed = 4; // Recipe has been executed.
-    static const size_t offset_locked   = 5; // Fast (spin) lock.
-    static const size_t offset_busy     = 6; // Slow (wait) lock.
+    static const size_t offset_touched  = 1; // Target has been locked.
+    static const size_t offset_tried    = 2; // Rule match has been tried.
+    static const size_t offset_matched  = 3; // Rule has been matched.
+    static const size_t offset_applied  = 4; // Rule has been applied.
+    static const size_t offset_executed = 5; // Recipe has been executed.
+    static const size_t offset_locked   = 6; // Fast (spin) lock.
+    static const size_t offset_busy     = 7; // Slow (wait) lock.
 
-    static size_t count_base     () {return 4 * (current_on - 1);}
+    static size_t count_base     () {return 5 * (current_on - 1);}
 
     static size_t count_touched  () {return offset_touched  + count_base ();}
+    static size_t count_tried    () {return offset_tried    + count_base ();}
     static size_t count_matched  () {return offset_matched  + count_base ();}
     static size_t count_applied  () {return offset_applied  + count_base ();}
     static size_t count_executed () {return offset_executed + count_base ();}
@@ -485,6 +487,11 @@ namespace build2
     target_state
     matched_state (action a, bool fail = true) const;
 
+    // See try_match().
+    //
+    pair<bool, target_state>
+    try_matched_state (action a, bool fail = true) const;
+
     // This function should only be called during execution if we have
     // observed (synchronization-wise) that this target has been executed.
     //
@@ -516,7 +523,10 @@ namespace build2
     // Version that should be used during match after the target has been
     // matched for this action (see the recipe override).
     //
-    target_state
+    // Indicate whether there is a rule match with the first half of the
+    // result (see try_match()).
+    //
+    pair<bool, target_state>
     state (action a) const;
 
     // Return true if the state comes from the group. Target must be at least
@@ -558,7 +568,7 @@ namespace build2
     bool
     unchanged (action_type a) const
     {
-      return state (a) == target_state::unchanged;
+      return state (a).second == target_state::unchanged;
     }
 
     // Targets to which prerequisites resolve for this recipe. Note that
diff --git a/build2/target.ixx b/build2/target.ixx
index 459265b..9b4b9d8 100644
--- a/build2/target.ixx
+++ b/build2/target.ixx
@@ -92,9 +92,20 @@ namespace build2
   {
     // Note that the target could be being asynchronously re-matched.
     //
-    target_state r (state (a));
+    pair<bool, target_state> r (state (a));
 
-    if (fail && r == target_state::failed)
+    if (fail && (!r.first || r.second == target_state::failed))
+      throw failed ();
+
+    return r.second;
+  }
+
+  inline pair<bool, target_state> target::
+  try_matched_state (action_type a, bool fail) const
+  {
+    pair<bool, target_state> r (state (a));
+
+    if (fail && r.first && r.second == target_state::failed)
       throw failed ();
 
     return r;